Zephyr内存管理之Pool

Creative Commons
本作品采用知识共享署名
发表于 | 分类于 | | 阅读次数：

本文通过分析代码介绍Zephyr Pool内存管理的实现。

sys_pool为Zephyr中Pool的内存分配管理算法，支持创建用户和内核两种模式的Pool，在Zephyr内存管理之Heap一文中已提到过在早期的Zephyr中内核使用Pool进行动态内存管理，k_malloc/k_free等函数都是使用的Pool管理内存。在最新的Zephyr中已经通过默认配置CONFIG_MEM_POOL_HEAP_BACKEND=y，将内核的动态内存管理变为Heap来实现。虽然Pool已经从Zephyr的Kernel中移除，但Zephyr的内置的minimal stdlib动态分配内存和Lvgl的porting依然使用的是Pool，因此分析Pool的内存管理原理还是有实际意义。

Pool管理的是一片固定大小的连续内存区域，用户可以在Pool管理的内存区域中动态分配指定长度的内存。sys_pool采用伙伴系统内存内存管理算法，sys_pool本身时是线程安全的管理算法。其代码在下列几个位置：

  • include/sys/mempool_base.h : sys_pool基础的数据结构，宏和函数
  • lib/os/mempool.h ：sys_pool对外的数据结构和函数
  • lib/os/mempool.c ：sys_pool实现代码

Block

使用伙伴管理系统的Pool中内存以Block的形式进行管理，从Pool中分配内存就是取出一个可用的Block，在初始化Block时会指定最大的Block和最先的Block，每次分配内存的过程就是从较大的Block向较小的Block进行分割，直到分割出来的大小和分配内存大小一致。从Pool中能够分配最大内存不能超过最大的Block，分配的内存小于最小的Block就会给与最小的Block。在Zephyr中伙伴系统的数量是4，也就是说一次分割会将大的Block分为4个小的Block，然后取出其中一个Block进行分配或者进行下一次分割。

在Pool中最大的Block处于level 0，每分割一次level增加1，在每个level中对block依次编号，一个block的位置和大小可以由level和block编号唯一确认。一个Block的数据结构如下：

1
2
3
4
5
struct sys_mem_pool_block {
	struct sys_mem_pool *pool;
	uint32_t level : 4;
	uint32_t block : 28;
};

pool 指向block所属的pool控制块。
level block的level，占4bit，最大为15，最大的block最多可以被分为$4^{15}=65536$个block
block block的编号，占28bit

任意一个被分配的block的最开始都会放置一个struct sys_mem_pool_block用于管理该block，从该结构体之后的内存才是分配出的可用内存。Pool中空闲的block会在最开始放置sys_dnode_t，将该Block放入空闲链表。

Pool管理

Pool定义

在使用Pool前需要先定义Pool，定义Pool主要是完成Pool内存的分配和Pool管理结构的分配，在mempool.h中提供了下面宏定义一个Pool：

1
#define SYS_MEM_POOL_DEFINE(name, ignored, minsz, maxsz, nmax, align, section)

name, pool的名字
ignored, 忽略字段无意义
minsz, pool中最小的block size，长度必须是4的倍数且大于0
maxsz, pool中最大的block size，长度必须是minsz的倍数，且倍数是4的幂(1,4,16,64,…)
nmax, 最大block的数量, pool管理的内存空间maxsz*nmax
align, pool buffer起始地址对齐，必须是2的幂，且必须 要大于等于4
section, pool放置的section名

使用SYS_MEM_POOL_DEFINE定义Pool代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define SYS_MEM_POOL_DEFINE(name, ignored, minsz, maxsz, nmax, align, section) \
	char __aligned(WB_UP(align)) Z_GENERIC_SECTION(section)		\
		_mpool_buf_##name[WB_UP(maxsz) * nmax			\
				  + _MPOOL_BITS_SIZE(maxsz, minsz, nmax)]; \
	struct sys_mem_pool_lvl Z_GENERIC_SECTION(section)		\
		_mpool_lvls_##name[Z_MPOOL_LVLS(maxsz, minsz)];		\
	Z_GENERIC_SECTION(section) struct sys_mem_pool name = {		\
		.base = {						\
			.buf = _mpool_buf_##name,			\
			.max_sz = WB_UP(maxsz),				\
			.n_max = nmax,					\
			.n_levels = Z_MPOOL_LVLS(maxsz, minsz),		\
			.levels = _mpool_lvls_##name,			\
			.flags = SYS_MEM_POOL_USER			\
		}							\
	};

  • 定义一个align对齐的全局数组作为Pool buffer。该数组前maxsz*nmax字节为Pool内存分配区，的该数组的末尾还有一段bitmap用于标记block是否被使用。
  • 根据内存分配区的大小计算出block level总数n_levels，定义一个含有n_levels个struct sys_mem_pool_lvl的结构体数组，用于管理不同level的block。
  • 定义一个结构体变量struct sys_mem_pool，该结构体变量用于管理和存储Pool的信息。

level

一个Pool的level由其定义时的maxsz和minsz决定，maxsz通过4分裂变为minsz的次数就是一个Pool的level数，例如maxsz每次分成等分的4块，连续分裂3次后变为minsz，即maxsz/4/4/4 = minsz，那么level就是3。
Pool为每个level的block提供一个被名为struct sys_mem_pool_lvl的管理结构，该结构中包含一个free_list和一个bitmap，对应level的空闲的block将加入到free_list，当block被使用时会从free_list中取出，被取出的block在bitmap中对应的bit将被置1表示已经被使用。

1
2
3
4
5
6
7
struct sys_mem_pool_lvl {
	union {
		uint32_t *bits_p;
		uint32_t bits[sizeof(uint32_t *)/4];
	};
	sys_dlist_t free_list;
};

bits：block使用情况的bitmap，当level管理的block小于等于32个时使用bits存储bitmap
bits_p：bits_p和bits共用4字节空间， 当level管理的block大于32个的时候bits已经无法直接存储，因此当作bits_p用，放置一个指针，指向在Pool buffer末尾更大的bitmap。某个level的block bitmap能够在bits中直接存储，这个level被称作inline level。
free_list：对应level下的空闲block将会加入到该双向链表中进行管理

Pool buffer管理结构

Pool buffer的管理结构如下，定义的时候将对其中的struct sys_mem_pool_base进行初始化

1
2
3
4
struct sys_mem_pool {
	struct sys_mem_pool_base base;
	struct sys_mutex mutex;
};

base：用于存储和管理Pool的信息
mutex：内存分配和释放操作时上锁，保证sys_pool操作的线程安全。

1
2
3
4
5
6
7
8
9
struct sys_mem_pool_base {
	void *buf;
	size_t max_sz;
	uint16_t n_max;
	uint8_t n_levels;
	int8_t max_inline_level;
	struct sys_mem_pool_lvl *levels;
	uint8_t flags;
};

buf：指向Pool buffer
max_sz：最大block的大小
n_max：最大block的数量，实际管理的pool buffer大小就是n_max*max_sz
n_levels：Pool的level
max_inline_level：最大的inline level，超过该max_inline_level的level bitmap存放在pool buffer后面的bitmap。
levels：指向struct sys_mem_pool_lvl管理结构数组。
flags：Pool属性，SYS_MEM_POOL_KERNEL和SYS_MEM_POOL_USER可选，当选择kernel时在pool内存管理操作时会锁irq保护。由于目前Pool不再被用于内核，而使用SYS_MEM_POOL_DEFINE定义的pool都将使用SYS_MEM_POOL_USER。

Pool初始化

Pool初始化主要是完成free_list的建立和max_inline_level的确认，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
static inline void sys_mem_pool_init(struct sys_mem_pool *p)
{
	z_sys_mem_pool_base_init(&p->base);
}


void z_sys_mem_pool_base_init(struct sys_mem_pool_base *p)
{
	int i;
	size_t buflen = p->n_max * p->max_sz, sz = p->max_sz;
	uint32_t *bits = (uint32_t *)((uint8_t *)p->buf + buflen);

	p->max_inline_level = -1;

	//为每一级level进行初始化
	for (i = 0; i < p->n_levels; i++) {
		//计算当前level的总计block数量
		size_t nblocks = buflen / sz;

		//初始化当前level block的链表
		sys_dlist_init(&p->levels[i].free_list);

		//如果当前level的block <= 32，归为在线level管理，否则放入bitmap,一个bit对应一个block
		if (nblocks <= sizeof(p->levels[i].bits)*8) {
			p->max_inline_level = i;    //更新max_inline_level
		} else {
			//计算levels的bit在bitmap中的位置
			p->levels[i].bits_p = bits;
			bits += (nblocks + 31)/32;
		}
		
		//计算下一个level的block size大小
		sz = WB_DN(sz / 4);
	}

	//如果有多个最大block, 需要加入到free_list内
	for (i = 0; i < p->n_max; i++) {
		//计算每个block在pool中的地址
		void *block = block_ptr(p, p->max_sz, i);
		//将顶级的block加入到顶级level list中
		sys_dlist_append(&p->levels[0].free_list, block);
	}
}

分配内存

从Pool中分配内存，就是从Pool中找到和要分配内存大小匹配的Block，如果没有匹配的Block就从大的Block分裂出来匹配的Block，分配内存代码分析如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void *sys_mem_pool_alloc(struct sys_mem_pool *p, size_t size)
{
	struct sys_mem_pool_block *blk;
	uint32_t level, block;
	char *ret;
	
	//多线程保护
	sys_mutex_lock(&p->mutex, K_FOREVER);

	//分配的内存以block管理，在最开始放置block header信息，后面跟随的是可用内存
	size += WB_UP(sizeof(struct sys_mem_pool_block));
	
	//按照计算的size分配block
	if (z_sys_mem_pool_block_alloc(&p->base, size, &level, &block,
				      (void **)&ret)) {
		ret = NULL;
		goto out;
	}

	//更新分配的block信息
	blk = (struct sys_mem_pool_block *)ret;
	blk->level = level;
	blk->block = block;
	blk->pool = p;
	
	//刨除block header部分内容，返回实际可用的内存地址
	ret += WB_UP(sizeof(struct sys_mem_pool_block));
out:
	sys_mutex_unlock(&p->mutex);
	return ret;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
int z_sys_mem_pool_block_alloc(struct sys_mem_pool_base *p, size_t size,
			      uint32_t *level_p, uint32_t *block_p, void **data_p)
{
	int i, from_l, alloc_l = -1;
	unsigned int key;
	void *data = NULL;
	size_t lsizes[LVL_ARRAY_SZ(p->n_levels)];

	//从level 0开始查找，找出和size大小最匹配的block所在的level
	lsizes[0] = p->max_sz;
	for (i = 0; i < p->n_levels; i++) {
		if (i > 0) {
			lsizes[i] = WB_DN(lsizes[i-1] / 4);
		}

		if (lsizes[i] < size) {
            //找到大小匹配的Block，退出查找,次数alloc_l是匹配Block所在level
			break;
		}

		alloc_l = i;
	}

	//要分配的size，比最大的block还大，没有匹配上，无法分配内存
	if (alloc_l < 0) {
		*data_p = NULL;
		return -ENOMEM;
	}

	key = pool_irq_lock(p);
	//从最适合的level找有没有空闲的block，如果没有，向上一层找，如果上层没有继续再向上找，直到发现有空闲的block
	for (i = alloc_l; i >= 0; i--) {
		data = block_alloc(p, i, lsizes[i]);

		//此时找到的block 的level可能会比alloc_l小很多，因此要进行block的分割
		if (data != NULL) {
			for (from_l = i; from_l < alloc_l; from_l++) {
				//分割block，并取出第一个，后面三个加入到分割后所属level的list内
				//会将第一个block一直分割下去直到得到对应level的block
				data = block_break(p, data, from_l, lsizes);
				pool_irq_unlock(p, key);
				key = pool_irq_lock(p);
			}
			break;
		}
	}
	pool_irq_unlock(p, key);

	//输出block地址
	*data_p = data;

	if (data == NULL) {
		return -ENOMEM;
	}

	//输出block level
	*level_p = alloc_l;
	//输出block 所处pool中的对应level的number
	*block_p = block_num(p, data, lsizes[alloc_l]);

	return 0;
}

分割block的流程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void *block_break(struct sys_mem_pool_base *p, void *block, int l,
				size_t *lsizes)
{
	int i, bn;
    //计算出要分割的block的Block number
	bn = block_num(p, block, lsizes[l]);
    //将该block的在bitmap内的bit置1, 被分割的block就是已被使用的block
	set_alloc_bit(p, l + 1, 4*bn);

    //只使用分割后的第一个block，后面3个block被放入free_list内备用
	for (i = 1; i < 4; i++) {
		int lsz = lsizes[l + 1];
		void *block2 = (lsz * i) + (char *)block;

		sys_dlist_append(&p->levels[l + 1].free_list, block2);
	}

	return block;
}

释放内存

释放内存时，即使将Block退回到Pool，如果其伙伴block空闲就进行合并，不空闲就放入free_list，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void sys_mem_pool_free(void *ptr)
{
	struct sys_mem_pool_block *blk;
	struct sys_mem_pool *p;

	if (ptr == NULL) {
		return;
	}

	//通过内存计算出block的地址
	ptr = (char *)ptr - WB_UP(sizeof(struct sys_mem_pool_block));
	
	//取block
	blk = (struct sys_mem_pool_block *)ptr;
	p = blk->pool;

	//多线程保护
	sys_mutex_lock(&p->mutex, K_FOREVER);
	//释放对应的block
	z_sys_mem_pool_block_free(&p->base, blk->level, blk->block);
	sys_mutex_unlock(&p->mutex);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void z_sys_mem_pool_block_free(struct sys_mem_pool_base *p, uint32_t level,
			      uint32_t block)
{
	size_t lsizes[LVL_ARRAY_SZ(p->n_levels)];
	uint32_t i;

	//计算每个level的block size
	lsizes[0] = p->max_sz;
	for (i = 1; i <= level; i++) {
		lsizes[i] = WB_DN(lsizes[i-1] / 4);
	}

	//释放block
	block_free(p, level, lsizes, block);
}
1
2
3
4
5
6
7
8
9
10
11
static void *block_alloc(struct sys_mem_pool_base *p, int l, size_t lsz)
{
	sys_dnode_t *block;
	//检查对应level中是否有空闲的block
	block = sys_dlist_get(&p->levels[l].free_list);
	if (block != NULL) {
		//有空闲的block，在bitmap中将该block mark为被使用
		set_alloc_bit(p, l, block_num(p, block, lsz));
	}
	return block;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
static void *block_break(struct sys_mem_pool_base *p, void *block, int l,
				size_t *lsizes)
{
	int i, bn;
	//计算要分割的block处于的位置
	bn = block_num(p, block, lsizes[l]);
	//将要分割的block标注为已使用
	set_alloc_bit(p, l + 1, 4*bn);

	//分割后第一个block被返回，剩余的3个block被加入到free_list中，因此i从1开始
	for (i = 1; i < 4; i++) {
		int lsz = lsizes[l + 1];
		void *block2 = (lsz * i) + (char *)block;

		sys_dlist_append(&p->levels[l + 1].free_list, block2);
	}

	return block;
}


static unsigned int bfree_recombine(struct sys_mem_pool_base *p, int level,
				    size_t *lsizes, int bn, unsigned int key)
{
	while (level >= 0) {
		//计算block的实际地址
		int i, lsz = lsizes[level];
		void *block = block_ptr(p, lsz, bn);

		/* Detect common double-free occurrences */
		__ASSERT(alloc_bit_is_set(p, level, bn),
			 "mempool double-free detected at %p", block);

		/* Put it back */
		//将block标注为未使用，并放回到对应level的free_list中
		clear_alloc_bit(p, level, bn);
		sys_dlist_append(&p->levels[level].free_list, block);

		/* Relax the lock (might result in it being taken, which is OK!) */
		pool_irq_unlock(p, key);
		key = pool_irq_lock(p);

		/* Check if we can recombine its superblock, and repeat */
		//检查当前level已经到顶级说明无法合并
		//检查当前level中其它相邻的block正在被使用，也无法合并
		//无法合并的直接退出
		if (level == 0 || partner_alloc_bits(p, level, bn) != 0) {
			return key;
		}

		//可以合并的，将block从free_list中取出，全部取出就是合并
		for (i = 0; i < 4; i++) {
			int b = (bn & ~3) + i;

			sys_dlist_remove(block_ptr(p, lsz, b));
		}

		/* Free the larger block */
		//输出合并互的信息，合并一直会从当前level向顶级level循环，直到顶级或者无法合并才会返回
		level = level - 1;
		bn = bn / 4;
	}
	__ASSERT(0, "out of levels");
	return -1;
}

Pool的使用

本小结简单分析Zephyr的内置的minimal stdlib如何使用Pool，代码参考lib/libc/minimal/source/stdlib/malloc.c, 为了简化分析，本文只分析非用户模式下的情况

1.定义Pool

非用户模式下Pool的buffer放到.data段中，管理的内存大小通过CONFIG_MINIMAL_LIBC_MALLOC_ARENA_SIZE配置

1
2
3
4
#define POOL_SECTION .data

SYS_MEM_POOL_DEFINE(z_malloc_mem_pool, NULL, 16,
		    CONFIG_MINIMAL_LIBC_MALLOC_ARENA_SIZE, 1, 4, POOL_SECTION);

2.初始化Pool

在系统初始化时，通过malloc_prepare初始化Pool，优先顺序属于APPLICATION级别的，这也说明后面的malloc/free也只能在驱动和kernel初始化完成后才能使用

1
2
3
4
5
6
7
8
9
10
static int malloc_prepare(struct device *unused)
{
	ARG_UNUSED(unused);

	sys_mem_pool_init(&z_malloc_mem_pool);

	return 0;
}

SYS_INIT(malloc_prepare, APPLICATION, CONFIG_KERNEL_INIT_PRIORITY_DEFAULT);

3. malloc/free

malloc/free非常简单，直接封装pool的分配和释放函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void *malloc(size_t size)
{
	void *ret;

	ret = sys_mem_pool_alloc(&z_malloc_mem_pool, size);
	if (ret == NULL) {
		errno = ENOMEM;
	}

	return ret;
}

void free(void *ptr)
{
	sys_mem_pool_free(ptr);
}

参考

https://docs.zephyrproject.org/latest/reference/kernel/memory/pools.html