伙伴算法内存块分配器的协作图:

结构体
struct	xwmm_bma_orderlist
	阶链表更多...

struct	xwmm_bma_bcb
	块控制块更多...

struct	xwmm_bma
	伙伴算法内存块分配器更多...

宏定义
#define	XWMM_BMA_MAX_ORDER ((xwu8_t)126)

#define	XWMM_BMA_COMBINED ((xwu8_t)127)

#define	XWMM_BMA_ORDER_MASK ((xwu8_t)0x7F)

#define	XWMM_BMA_INUSED ((xwu8_t)0x80)

#define	XWMM_BMA_ORDERLIST_SIZE(bo) sizeof(struct xwmm_bma_orderlist[(bo) + 1U])

#define	XWMM_BMA_BCB_SIZE(bo) sizeof(struct xwmm_bma_bcb[1U << (bo)])

#define	XWMM_BMA_RAWOBJ_DEF(name, blkodr)
	定义伙伴算法内存块分配器结构体的RAW内存空间，用于初始化伙伴算法内存块分配器结构体

函数
xwer_t	xwmm_bma_init (struct xwmm_bma bma, const char name, xwptr_t origin, xwsz_t size, xwsz_t blksize, xwsz_t blkodr)
	XWMM API：初始化伙伴算法内存块分配器

xwer_t	xwmm_bma_alloc (struct xwmm_bma bma, xwsq_t order, void *membuf)
	XWMM API：申请一块连续的内存

xwer_t	xwmm_bma_free (struct xwmm_bma bma, void mem)
	XWMM API：释放内存块

xwer_t	xwmm_bma_malloc (struct xwmm_bma bma, xwsz_t size, void *membuf)
	XWMM API：申请指定大小的连续内存

xwer_t	xwmm_bma_realloc (struct xwmm_bma bma, xwsz_t size, void *membuf)
	XWMM API：调整内存大小

xwer_t	xwmm_bma_memalign (struct xwmm_bma bma, xwsz_t alignment, xwsz_t size, void *membuf)
	XWMM API：申请对齐的内存

xwer_t	xwmm_bma_malloc_usable_size (struct xwmm_bma bma, void mem, xwsz_t *size)
	XWMM API：返回该块内存实际可用字节数

详细描述

伙伴算法分配器在分配时，会将内存不断地二等分，直到切割到能满足内存的最小尺寸为止。释放时会检查与之相邻并等长的内存块（称为伙伴）是否空闲，如果是，就和“伙伴”合并成更大的内存块，然后继续检测合并后的内存块是否也存在空闲的伙伴，一直向上合并到不能合并为止。

优点：
- 支持释放操作；
- 支持大小不固定的内存申请操作；
- 内存碎片的大小只会是单位内存块大小的2的n次方倍，内存碎片更容易被合并。
缺点：
- 代码稍微复杂；
- 因为存在合并与切割的循环，申请与释放操作的所需要的时间不是特别稳定；
- 内存大小固定为2的指数，如果申请的内存过小，会造成内存浪费。
适用性：对内存复用性要求高的应用场合。
上下文的安全性：在任何上下文（中断、中断底半部、线程）都是安全的。

宏定义说明

◆ XWMM_BMA_MAX_ORDER

#define XWMM_BMA_MAX_ORDER ((xwu8_t)126)

最大的阶

在文件 bma.h 第 44 行定义.

◆ XWMM_BMA_COMBINED

#define XWMM_BMA_COMBINED ((xwu8_t)127)

块已被合并

在文件 bma.h 第 45 行定义.

◆ XWMM_BMA_ORDER_MASK

#define XWMM_BMA_ORDER_MASK ((xwu8_t)0x7F)

阶的掩码

在文件 bma.h 第 46 行定义.

◆ XWMM_BMA_INUSED

#define XWMM_BMA_INUSED ((xwu8_t)0x80)

块正在被使用

在文件 bma.h 第 47 行定义.

◆ XWMM_BMA_ORDERLIST_SIZE

#define XWMM_BMA_ORDERLIST_SIZE ( bo ) sizeof(struct xwmm_bma_orderlist[(bo) + 1U])

在文件 bma.h 第 49 行定义.

◆ XWMM_BMA_BCB_SIZE

#define XWMM_BMA_BCB_SIZE ( bo ) sizeof(struct xwmm_bma_bcb[1U << (bo)])

在文件 bma.h 第 50 行定义.

◆ XWMM_BMA_RAWOBJ_DEF

#define XWMM_BMA_RAWOBJ_DEF	(	name,
		blkodr
	)

值:

xwu8_t name[sizeof(struct xwmm_bma) + \

XWMM_BMA_ORDERLIST_SIZE(blkodr) + XWMM_BMA_BCB_SIZE(blkodr)]

XWMM_BMA_BCB_SIZE

#define XWMM_BMA_BCB_SIZE(bo)

Definition bma.h:50

XWMM_BMA_ORDERLIST_SIZE

#define XWMM_BMA_ORDERLIST_SIZE(bo)

Definition bma.h:49

xwu8_t

uint8_t xwu8_t

Definition type.h:194

xwmm_bma

伙伴算法内存块分配器

Definition bma.h:82

xwmm_bma::blkodr

xwsq_t blkodr

Definition bma.h:86

定义伙伴算法内存块分配器结构体的RAW内存空间，用于初始化伙伴算法内存块分配器结构体

参数

[in]	name	内存数组名
[in]	blkodr	伙伴算法内存块分配器中单位内存块的数量，以2的blkodr次方形式表示

在文件 bma.h 第 58 行定义.

函数说明

◆ xwmm_bma_init()

xwer_t xwmm_bma_init	(	struct xwmm_bma *	bma,
		const char *	name,
		xwptr_t	origin,
		xwsz_t	size,
		xwsz_t	blksize,
		xwsz_t	blkodr
	)

XWMM API：初始化伙伴算法内存块分配器

参数

[in]	bma	伙伴算法内存块分配器的指针
[in]	name	名字
[in]	origin	内存区域的起始地址
[in]	size	内存区域的大小
[in]	blksize	伙伴算法内存块分配器中单位内存块的大小
[in]	blkodr	伙伴算法内存块分配器中单位内存块的数量，以2的blkodr次方形式表示

返回: 错误码

返回值

-ESIZE 内存区域大小不匹配

注解

单位内存块的数量只能是2的n次方，即 2, 4, 8, 16, 32, 64, 128, ... ，对应的 blkodr 分别为 1, 2, 3, 4, 5, 6, 7, ... ；
内存区域大小必须满足关系： size == (blksize * (1 << blkodr)) 。

同步/异步：同步
上下文：中断、中断底半部、线程
重入性：不可重入

<Size error

< 块正在被使用

< 块已被合并

< 块正在被使用

<No error

在文件 bma.c 第 63 行定义.

{
        xwer_t rc;
        xwsz_t num;
        xwsz_t i;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
 
        num = 1U << blkodr;
        if (size != (num * blksize)) {
                rc = -ESIZE;
                xwmm_bmalogf(ERR, "Size of memory(0x%lX, 0x%lX) is error!\n",
                             origin, size);
                goto err_size;
        }
        bma->name = name;
        bma->zone.origin = origin;
        bma->zone.size = blksize * num;
        bma->blksize = blksize;
        bma->blkodr = blkodr;
        xwos_splk_init(&bma->lock);
        bma->orderlists = (struct xwmm_bma_orderlist *)&bma[(xwsz_t)1];
        bma->bcbs = (struct xwmm_bma_bcb *)&bma->orderlists[(xwsz_t)1 + blkodr];
        xwmm_bmalogf(DEBUG,
                     "memory:(0x%lX,0x%lX),orderlists:0x%lX,bcbs:0x%lX,"
                     "blocksize:0x%lX, blockorder:0x%lX\n",
                     origin, size, (xwptr_t)bma->orderlists, (xwptr_t)bma->bcbs,
                     bma->blksize, bma->blkodr);
 
        for (i = 0; i < num; i++) {
                bma->bcbs[i].order = XWMM_BMA_INUSED | XWMM_BMA_COMBINED;
        }
        bma->bcbs[0].order = (xwu8_t)blkodr | XWMM_BMA_INUSED;
 
        for (i = 0; i <= blkodr; i++) {
                xwlib_bclst_init_head(&bma->orderlists[i].head);
        }
        xwmm_bma_orderlist_add(bma, &bma->orderlists[blkodr], blkodr, &bma->bcbs[0]);
        return XWOK;
 
err_size:
        return rc;
}

函数调用图:

◆ xwmm_bma_alloc()

xwer_t xwmm_bma_alloc	(	struct xwmm_bma *	bma,
		xwsq_t	order,
		void **	membuf
	)

XWMM API：申请一块连续的内存

参数

[in]	bma	伙伴算法内存块分配器对象的指针
[in]	order	块数量的阶，内存块大小： `((1 << order) * bma->blksize)`
[out]	membuf	指向地址缓存的指针，通过此指针缓存返回申请到的内存的首地址

返回: 错误码

返回值

-EFAULT	空指针
-ERANGE	order无效
-ENOMEM	内存不足

注解

同步/异步：同步
上下文：中断、中断底半部、线程
重入性：可重入

<No error

在文件 bma.c 第 312 行定义.

{
        xwer_t rc;
        xwreg_t flag;
        xwsq_t o;
        struct xwmm_bma_orderlist * ol;
        struct xwmm_bma_bcb * bcb;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
        XWOS_VALIDATE((membuf), "nullptr", -EFAULT);
        XWOS_VALIDATE((order <= (xwsq_t)XWSSQ_MAX), "out-of-range", -ERANGE);
 
        ol = NULL;
        bcb = err_ptr(-ENOENT);
        xwos_splk_lock_cpuirqsv(&bma->lock, &flag);
        for (o = order; o <= bma->blkodr; o++) {
                ol = &bma->orderlists[o];
                bcb = xwmm_bma_orderlist_choose(bma, ol);
                if (!is_err(bcb)) {
                        break;
                }
        }
        if (is_err(bcb)) { // cppcheck-suppress [misra-c2012-14.4]
                xwos_splk_unlock_cpuirqrs(&bma->lock, flag);
                rc = -ENOMEM;
                *membuf = NULL;
        } else {
                xwmm_bmalogf(DEBUG,
                             "[ALLOC] bcb(idx:0x%lX,odr:0x%X)\n",
                             (((xwptr_t)bcb - (xwptr_t)xwmm_bma->bcbs) /
                              sizeof(struct xwmm_bma_bcb)),
                             bcb->order);
                xwmm_bma_divide_block(bma, bcb, order, ol);
                xwos_splk_unlock_cpuirqrs(&bma->lock, flag);
                rc = XWOK;
                *membuf = xwmm_bma_bcb_to_mem(bma, bcb);
        }
        return rc;
}

函数调用图:

这是这个函数的调用关系图:

◆ xwmm_bma_free()

xwer_t xwmm_bma_free	(	struct xwmm_bma *	bma,
		void *	mem
	)

XWMM API：释放内存块

参数

[in]	bma	伙伴算法内存块分配器对象的指针
[in]	mem	内存块的首地址指针

返回: 错误码

返回值

XWOK	没有错误
-EINVAL	参数错误
-ERANGE	内存块不属于指定的伙伴算法内存块分配器对象

注解

同步/异步：同步
上下文：中断、中断底半部、线程
重入性：可重入

< 块正在被使用

<No error

在文件 bma.c 第 403 行定义.

{
        struct xwmm_bma_bcb * bcb;
        xwptr_t unaligned;
        xwreg_t flag;
        xwer_t rc;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
        XWOS_VALIDATE((mem), "nullptr", -EFAULT);
 
        if ((((xwptr_t)mem < bma->zone.origin) ||
             ((xwptr_t)mem >= (bma->zone.origin + bma->zone.size)))) {
                rc = -ERANGE;
                goto err_range;
        }
        unaligned = ((xwptr_t)mem - bma->zone.origin) % (xwptr_t)bma->blksize;
        mem = (void *)((xwptr_t)mem - unaligned);
        bcb = xwmm_bma_mem_to_bcb(bma, mem);
        if (is_err(bcb)) {  // cppcheck-suppress [misra-c2012-14.4]
                rc = ptr_err(bcb);
                goto err_invalmem;
        }
        xwmm_bmalogf(DEBUG,
                     "[FREE] mem:0x%lX,bcb(idx:0x%lX,odr:0x%X)\n",
                     (xwptr_t)mem,
                     (((xwptr_t)bcb - (xwptr_t)xwmm_bma->bcbs) /
                      sizeof(struct xwmm_bma_bcb)),
                     bcb->order);
        if (0 == (XWMM_BMA_INUSED & bcb->order)) {
                rc = -EINVAL;
                goto err_invalmem;
        }
        xwos_splk_lock_cpuirqsv(&bma->lock, &flag);
        xwmm_bma_combine(bma, bcb);
        xwos_splk_unlock_cpuirqrs(&bma->lock, flag);
        return XWOK;
 
err_invalmem:
err_range:
        return rc;
}

函数调用图:

这是这个函数的调用关系图:

◆ xwmm_bma_malloc()

xwer_t xwmm_bma_malloc	(	struct xwmm_bma *	bma,
		xwsz_t	size,
		void **	membuf
	)

XWMM API：申请指定大小的连续内存

参数

[in]	bma	伙伴算法内存块分配器对象的指针
[in]	size	申请的大小
[out]	membuf	指向缓冲区的指针，通过此缓冲区返回申请到的内存的首地址

返回: 错误码

返回值

XWOK	没有错误
-EFAULT	空指针
-ENOMEM	内存不足

注解

同步/异步：同步
上下文：中断、中断底半部、线程
重入性：可重入

此函数向内存池申请大小为 size 的内存：
- 若申请成功，通过 *membuf 返回申请到的内存地址，返回错误码为 XWOK ；
- 若申请失败，通过 *membuf 返回 NULL ，返回值为负的错误码。
内存不会被初始化；
当 size 为 0 ，通过 *membuf 返回 NULL ，返回错误码为 XWOK ；

<No error

在文件 bma.c 第 446 行定义.

{
        xwer_t rc;
        xwsz_t nrblk;
        xwssq_t p2;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
        XWOS_VALIDATE((membuf), "nullptr", -EFAULT);
 
        if ((xwsz_t)0 == size) {
                rc = XWOK;
                *membuf = NULL;
        } else {
                nrblk = XWBOP_DIV_ROUND_UP(size, bma->blksize);
                p2 = xwbop_fls(xwsz_t, nrblk);
                while ((p2 < 0) || ((bma->blksize << (xwsz_t)p2) < size)) {
                        p2++;
                }
                rc = xwmm_bma_alloc(bma, (xwsq_t)p2, membuf);
        }
        return rc;
}

函数调用图:

这是这个函数的调用关系图:

◆ xwmm_bma_realloc()

xwer_t xwmm_bma_realloc	(	struct xwmm_bma *	bma,
		xwsz_t	size,
		void **	membuf
	)

XWMM API：调整内存大小

参数

[in]	bma	伙伴算法内存块分配器对象的指针
[in]	size	申请的大小，当size == 0，realloc等价于free
[in,out]	membuf	指向缓冲区的指针，此缓冲区 (I) 作为输入时，当*membuf == NULL，realloc等价于malloc (O) 作为输出时，通过此缓冲区返回申请到的内存的首地址

返回: 错误码

返回值

XWOK	没有错误
-EFAULT	空指针
-ENOMEM	内存不足
-ERANGE	内存地址不在内存池的范围内

注解

同步/异步：同步
上下文：中断、中断底半部、线程
重入性：可重入

此API类似于C11标准中的 realloc() 函数：
- 当 *membuf 为 NULL ，此函数等价于 xwmm_bma_mealloc(mp, size, membuf) ；
- 当 *membuf 不为 NULL 且 size 为 0 ，此函数等价于 xwmm_bma_free(mp, *membuf) ，并且通过 *membuf 返回 NULL ；
- 当 *membuf 不为 NULL 且 size 比之前的小，此函数不重新申请内存，直接返回原来的 *membuf 以及 XWOK ；
- 当 *membuf 不为 NULL 且 size 比之前的大，此函数会尝试重新申请内存：
  - 如果申请失败，原来的内存不会受影响，且通过 *membuf 返回 NULL 以及错误码；
  - 如果申请成功，会将旧内存空间的内容移动到新内存空间内，然后返回新的 *membuf 以及 XWOK 。

<No error

< 阶的掩码

<No error

在文件 bma.c 第 470 行定义.

{
        struct xwmm_bma_bcb * bcb;
        xwptr_t unaligned;
        xwsz_t oldsize;
        xwer_t rc;
        void * oldm;
        void * newm;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
        XWOS_VALIDATE((membuf), "nullptr", -EFAULT);
 
        oldm = *membuf;
        if (NULL == oldm) {
                rc = xwmm_bma_malloc(bma, size, membuf);
        } else if ((xwsz_t)0 == size) {
                rc = xwmm_bma_free(bma, oldm);
                if (XWOK == rc) {
                        *membuf = NULL;
                }
        } else {
                if ((((xwptr_t)oldm < bma->zone.origin) ||
                     ((xwptr_t)oldm >= (bma->zone.origin + bma->zone.size)))) {
                        rc = -ERANGE;
                } else {
                        unaligned = (((xwptr_t)oldm - bma->zone.origin) %
                                     (xwptr_t)bma->blksize);
                        oldm = (void *)((xwptr_t)oldm - unaligned);
                        bcb = xwmm_bma_mem_to_bcb(bma, oldm);
                        oldsize = bcb->order & XWMM_BMA_ORDER_MASK;
                        oldsize = (1U << oldsize);
                        if (size <= oldsize) {
                                rc = XWOK;
                        } else {
                                rc = xwmm_bma_malloc(bma, size, &newm);
                                if (XWOK == rc) {
                                        // cppcheck-suppress [misra-c2012-17.7]
                                        memcpy(newm, oldm, size);
                                        *membuf = newm;
                                        xwmm_bma_free(bma, oldm);
                                } else {
                                        *membuf = NULL;
                                }
                        }
                }
        }
        return rc;
}

函数调用图:

◆ xwmm_bma_memalign()

xwer_t xwmm_bma_memalign	(	struct xwmm_bma *	bma,
		xwsz_t	alignment,
		xwsz_t	size,
		void **	membuf
	)

XWMM API：申请对齐的内存

参数

[in]	bma	伙伴算法内存块分配器对象的指针
[in]	alignment	内存的起始地址对齐的字节数，只能是2的n次方
[in]	size	申请的大小
[out]	membuf	指向缓冲区的指针，通过此缓冲区返回申请到的内存的首地址

返回: 错误码

返回值

XWOK	没有错误
-EFAULT	空指针
-ENOMEM	内存不足

注解

同步/异步：同步
上下文：中断、中断底半部、线程
重入性：可重入

此API类似于C标准中的 aligned_alloc() 函数：
- alignment 如果比 XWMM_ALIGNMENT 小，会被扩大为 XWMM_ALIGNMENT ：
- alignment 只能是2的n次方：
- 若size小于 alignment ， size 会被扩大为 alignment ，
- 若size大于 alignment ， size 会向上对齐到2的n次方，此时也一定为 alignment 的整数倍。
申请内存失败时，此函数不会修改 *membuf 的值。

< 内存管理对齐的字节数

<No error

在文件 bma.c 第 520 行定义.

{
        xwssq_t p2;
        xwer_t rc;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
        XWOS_VALIDATE((membuf), "nullptr", -EFAULT);
 
        if (alignment < XWMM_ALIGNMENT) {
                alignment = XWMM_ALIGNMENT;
        }
        p2 = xwbop_fls(xwsz_t, alignment);
        if (((xwsz_t)1 << (xwsz_t)p2) != alignment) {
                rc = -EINVAL;
                goto err_notp2;
        }
        if ((xwsz_t)0 == size) {
                rc = XWOK;
                *membuf = NULL;
                goto nothing;
        }
 
        if (size <= alignment) {
                size = alignment;
        } else {
                p2 = xwbop_fls(xwsz_t, size);
                while (((xwsz_t)1 << (xwsz_t)p2) < size) {
                        p2++;
                }
                size = ((xwsz_t)1 << p2);
        }
        rc = xwmm_bma_malloc(bma, size, membuf);
 
nothing:
err_notp2:
        return rc;
}

函数调用图:

◆ xwmm_bma_malloc_usable_size()

xwer_t xwmm_bma_malloc_usable_size	(	struct xwmm_bma *	bma,
		void *	mem,
		xwsz_t *	size
	)

XWMM API：返回该块内存实际可用字节数

参数

[in]	bma	伙伴算法内存块分配器对象的指针
[in]	mem	内存块的起始地址
[out]	size	指向缓冲区的指针，通过此缓冲区返回内存快实际大小

返回: 错误码

返回值

XWOK	没有错误
-EFAULT	空指针
-ERANGE	内存块不在BMA空间

注解

同步/异步：同步
上下文：中断、中断底半部、线程
重入性：可重入

此API类似于GNUC中的 malloc_usable_size() 函数。

<No error

< 阶的掩码

在文件 bma.c 第 559 行定义.

{
        struct xwmm_bma_bcb * bcb;
        xwptr_t unaligned;
        xwsz_t realsize;
        xwer_t rc;
 
        XWOS_VALIDATE((bma), "nullptr", -EFAULT);
        XWOS_VALIDATE((size), "nullptr", -EFAULT);
 
        if ((((xwptr_t)mem < bma->zone.origin) ||
             ((xwptr_t)mem >= (bma->zone.origin + bma->zone.size)))) {
                rc = -ERANGE;
        } else {
                rc = XWOK;
                unaligned = (((xwptr_t)mem - bma->zone.origin) % (xwptr_t)bma->blksize);
                mem = (void *)((xwptr_t)mem - unaligned);
                bcb = xwmm_bma_mem_to_bcb(bma, mem);
                realsize = bcb->order & XWMM_BMA_ORDER_MASK;
                realsize = (1U << realsize);
                *size = realsize;
        }
        return rc;
}

函数调用图: