伙伴算法内存块分配器

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

结构体
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_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：释放内存块

详细描述

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

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

宏定义说明

XWMM_BMA_COMBINED

#define XWMM_BMA_COMBINED   ((xwu8_t)127)

块已被合并

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

XWMM_BMA_INUSED

#define XWMM_BMA_INUSED   ((xwu8_t)0x80)

块正在被使用

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

XWMM_BMA_MAX_ORDER

#define XWMM_BMA_MAX_ORDER   ((xwu8_t)126)

最大的阶

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

XWMM_BMA_ORDER_MASK

#define XWMM_BMA_ORDER_MASK   ((xwu8_t)0x7F)

阶的掩码

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

XWMM_BMA_RAWOBJ_DEF

#define XWMM_BMA_RAWOBJ_DEF	(		name,
			blkodr
	)

值:

        xwu8_t name[sizeof(struct xwmm_bma) + \
                    sizeof(struct xwmm_bma_orderlist[(blkodr) + 1U]) + \
                    sizeof(struct xwmm_bma_bcb[1U << (blkodr)])]

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

参数

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

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

函数说明

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 第 311 行定义.

{
        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 第 402 行定义.

{
        struct xwmm_bma_bcb * bcb;
        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;
        }
        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_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 第 62 行定义.

{
        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;
}

函数调用图: