Zephyr内存管理之Heap

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

本文介绍Zephyr Heap内存管理的实现。

Heap分配器是一个Zephyr内核对象，Heap管理的是一片固定大小的连续内存区域，用户可以在Heap管理的内存区域中动态分配任意长度的内存。在Zephyr中lib/os/heap.c提供了底层的Heap内存管理算法，称作为sys_heap，该层级的API无法支持多线程。kernel/kheap.c建立在sys_heap之上实现了k_heap，k_heap提供多线程和同步等待内存管理功能，当线程在heap内存不足时申请heap内存，可以等待其它线程释放内存。

sys_heap

作为最基础的内存分配管理算法，sys_heap并不是只能提供给Zephyr Kernel使用，因此sys_heap的源代码并没有放置在kernel/下，而是放在下列几个位置：

  • include/sys/sys_heap.h : sys_heap对外数据结构和API
  • lib/os/heap.h ：sys_heap内部数据结构和chuck管理函数
  • lib/os/heap.c ：sys_heap实现代码
  • lib/os/heap-validate.c ：sys_heap验证代码

chuck

sys_heap将内存以chuck的形式进行管理，chuck的基本单位在代码内的定义是CHUNK_UNIT大小为8字节。一个chuck由1一个以上的CHUNK_UNIT组成。注意，当Heap小于256K时，CHUNK_UNIT为4，但实际上很上出现hea小于256K的情况，因此本文均已CHUNK_UNIT=8进行说明分析
chunk在heap内的位置以Chunk ID标识，Chunk ID以CHUNK_UNIT为单位进行计算：


上图的chunk的Chunk ID为3。

heap内的chuck分为两种形式，一种是已分配chunk，一种是空闲chunk，的结构如下：


已分配的chunk是指通过该chunk已被提供给用户使用，已分配chunk的chunk header占用8个字节，开始4字节存储相邻的前一个chunk的大小，后4字节的高31位保存当前chunk的CHUNK_UNIT数量，最低位保存当前chunk是否被使用，1表示在使用，chunk header之后mem指向的位置是实际用户可访问的内存起始地址。

空闲chunk是指未被分配给用户使用的chunk，空闲chunk的chunk header占用16个字节，开始8字节的定义和已分配chunk一致，但使用标识为0，表示该chunk未使用。空闲的chunk会被加入到空闲链表，其header的最后8个字节保存其的空闲链表中前后chunk的Chunk ID。

chunk的操作

对chunk有分割和合并两种操作，当分配内存时如果有大小刚合适的空闲chunk则直接使用该chunk，将使用标记从0变为1，如果没有大小刚合适的空闲chunk，会将一个较大的chunk中分为2个chunk，其中一个的大小和要分配的内存匹配。当释放内存时chunk变为空闲，为了避免内存碎片如果有两个相邻的空闲chunk将被合并为一个空闲chunk。

chunk的操作函数

为了方便之后理解代码，列出chunk的基本操作函数
split_chunks(struct z_heap *h, chunkid_t lc, chunkid_t rc) 分割chunk
void merge_chunks(struct z_heap *h, chunkid_t lc, chunkid_t rc) 合并chunk
static inline void set_chunk_used(struct z_heap *h, chunkid_t c, bool used) 标记chunk使用情况
static inline void set_chunk_size(struct z_heap *h, chunkid_t c, size_t size)设置chunk的大小
static inline void set_prev_free_chunk(struct z_heap *h, chunkid_t c, chunkid_t prev)设置chunk在空闲链表中前一个free chunk的CHUNK ID
static inline void set_next_free_chunk(struct z_heap *h, chunkid_t c, chunkid_t next)设置chunk在空闲链表中后一个free chunk的CHUNK ID
static inline void set_left_chunk_size(struct z_heap *h, chunkid_t c, size_t size)设置chunk前一个相邻chunk的chunk size
static inline chunkid_t prev_free_chunk(struct z_heap *h, chunkid_t c)获取chunk在空闲链表中前一个free chunk的CHUNK ID
static inline chunkid_t next_free_chunk(struct z_heap *h, chunkid_t c)获取chunk在空闲链表中后一个free chunk的CHUNK ID
static inline chunkid_t left_chunk(struct z_heap *h, chunkid_t c)获取前一个相邻chunk(left chunk)
static inline chunkid_t right_chunk(struct z_heap *h, chunkid_t c)获取后一个相邻的chunk(right chunk)
static inline size_t bytes_to_chunksz(struct z_heap *h, size_t bytes)将字节转为chunk所需的chunk unit数量

sys_heap初始化

Heap管理的是一片连续内存，并以CHUNK_UNIT为最小单位对内存进行管理。Heap以chunk的形象对内存进行管理，Heap初始化将连续内存切为3个chunk，分别是一个Heap header chunk，一个空闲chunk，一个end chunk。其中空闲chunk中包含了heap所有可供分配的内存。在Header header chunk的末尾放置了桶，用于管理空闲chunk的链表。为了减少Heap内碎片的产生，在释放内存后，空闲chunk会被根据大小加入到对应的桶中，当分配内存时会先去合适的桶中找出合适大小空闲chunk，只有在找不到合适大小的空闲chunk，才会对大的chunk进行分裂动作。桶的数据结构如下：

1
2
3
struct z_heap_bucket {
	chunkid_t next;
};

next 是桶链表中第一个节点的chunk id，如果没有空闲next的值为0。
初始化完后Heap呈现为下面形式

sys_heap初始化分析如下

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
void sys_heap_init(struct sys_heap *heap, void *mem, size_t bytes)
{
    //保留end mark chunk
	bytes -= heap_footer_bytes(bytes);

	//计算Heap管理内存的总结CHUNK_UNIT数量
	uintptr_t addr = ROUND_UP(mem, CHUNK_UNIT);
	uintptr_t end = ROUND_DOWN((uint8_t *)mem + bytes, CHUNK_UNIT);
	size_t buf_sz = (end - addr) / CHUNK_UNIT;

    //给header chunk赋值
	struct z_heap *h = (struct z_heap *)addr;   //header chunk放置在heap的最开始
	heap->heap = h;
	h->chunk0_hdr_area = 0;     //header chunk的chunk header预留
	h->len = buf_sz;            //len当作放置的是总计CHUNK_UNIT的数量
	h->avail_buckets = 0;       //此时还没有桶，桶标记为0

    //计算总计需要桶的数量
	int nb_buckets = bucket_idx(h, buf_sz) + 1;
    //计算heap header chunk的大小
	size_t chunk0_size = chunksz(sizeof(struct z_heap) +
				     nb_buckets * sizeof(struct z_heap_bucket));

    //初始化桶
	for (int i = 0; i < nb_buckets; i++) {
		h->buckets[i].next = 0;
	}

	//设置heap header chunk的chunk header
	set_chunk_size(h, 0, chunk0_size);
	set_chunk_used(h, 0, true);

	//设置第一个free chunk的chunk header
	set_chunk_size(h, chunk0_size, buf_sz - chunk0_size);
	set_left_chunk_size(h, chunk0_size, chunk0_size);

	//设置第一个end marker chunk的chunk header
	set_chunk_size(h, buf_sz, 0);
	set_left_chunk_size(h, buf_sz, buf_sz - chunk0_size);
	set_chunk_used(h, buf_sz, true);

    //将free chunk加入到桶中
	free_list_add(h, chunk0_size);
}

从sys_heap分配内存

分配内存会先从桶中找到或者分割出合适的chunk，通过要分配的size计算出匹配的桶在链表中遍历找出匹配chunk，为了让分配内存花费时间是确定的，Zephyr可以通过CONFIG_SYS_HEAP_ALLOC_LOOPS配置指定查询的次数，而不是无限制的查找下去，只要查找到有 大于或者等于需求chunk大小的chunk就立即退出查找，不会去找最匹配的空闲chunk。如果在匹配的桶中没有找到合适的空闲chunk，就选择大于匹配桶的最小非空桶中第一个空闲chunk来使用。如果选择出来的空闲chunk将从桶中移除，如果比需求的chunk大，那么对空闲chunk进行分割，分割出来的left chunk用于分配内存，right chunk作为新的空闲chunk按照其大小重新加入到桶中。

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
void *sys_heap_alloc(struct sys_heap *heap, size_t bytes)
{
	if (bytes == 0) {
		return NULL;
	}

	struct z_heap *h = heap->heap;
    //将size换算为chunk大小
	size_t chunk_sz = bytes_to_chunksz(h, bytes);

    //分配chunk，也就是从桶中找到匹配的chunk
	chunkid_t c = alloc_chunk(h, chunk_sz);
	if (c == 0) {
		return NULL;
	}

	//如果找到的chunk比要分配的大进行分割chunk操作
	if (chunk_size(h, c) > chunk_sz) {
		split_chunks(h, c, c + chunk_sz);
        //分割出来的right chunk放入桶中
		free_list_add(h, c + chunk_sz);
	}

    //分割出来的left chunk被标记为被使用
	set_chunk_used(h, c, true);

    //跳过chunk header, 将可用内存指针返回
	return chunk_mem(h, c);
}

从桶中找到匹配chunk的函数

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
static chunkid_t alloc_chunk(struct z_heap *h, size_t sz)
{
    //根据chunk大小，计算所在桶的index
	int bi = bucket_idx(h, sz);
	struct z_heap_bucket *b = &h->buckets[bi];

	if (bi > bucket_idx(h, h->len)) {
		return 0;
	}

    //如果桶中有空闲chunk，开始遍历查找
	if (b->next) {
		chunkid_t first = b->next;
        //查找的次数不能超过CONFIG_SYS_HEAP_ALLOC_LOOPS
		int i = CONFIG_SYS_HEAP_ALLOC_LOOPS;
		do {
			chunkid_t c = b->next;
            //只要找到的空闲chunk大于或等于目标chunk，退出查找
			if (chunk_size(h, c) >= sz) {
                //将找到的空闲chunk从桶中移除
				free_list_remove_bidx(h, c, bi);
				return c;
			}
			b->next = next_free_chunk(h, c);
			CHECK(b->next != 0);
		} while (--i && b->next != first);
	}

	//如果没有在匹配的桶中找到匹配的chunk，将从非空的最小桶中取出第一个chunk来使用
    //bmask为比匹配桶bi大的所有桶的标记
	size_t bmask = h->avail_buckets & ~((1 << (bi + 1)) - 1);

    //有效桶中有比bi大的桶
	if ((bmask & h->avail_buckets) != 0) {
        //取出比bi大的桶中最小的一个，bmask是比bi大的所有桶的标记，__builtin_ctz是计算从低位开始连续0的个数，因此刚好是比bi大的桶中最小的一个
		int minbucket = __builtin_ctz(bmask & h->avail_buckets);

        //直接取出第一个chunk
		chunkid_t c = h->buckets[minbucket].next;

        //将chunk移除桶
		free_list_remove_bidx(h, c, minbucket);
		CHECK(chunk_size(h, c) >= sz);
		return c;
	}

	return 0;
}

释放sys_heap内存

提供给外部使用者的内存地址，是跳过了chunk header的内存地址，因此释放内存时会先通过mem减去CHUNK_UNIT并计算出chunk id。对chunk进行释放时先检查right chunk是否空闲，如果空闲将和right chunk进行合并，再检查其left chunk是否空闲，如果空闲再和left chunk进行合并。被合并的left/right chunk会从对应的桶中移除，最后合并完成的chunk将根据其大小重新加入新桶中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void sys_heap_free(struct sys_heap *heap, void *mem)
{
	if (mem == NULL) {
		return; /* ISO C free() semantics */
	}
	struct z_heap *h = heap->heap;
    //从mem的大小计算出使用chunk id
	chunkid_t c = mem_to_chunkid(h, mem);

	//将chunk标记为空闲
	set_chunk_used(h, c, false);

    //释放chunk
	free_chunk(h, c);
}

释放chunk就是对chunk的合并及对桶的更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static void free_chunk(struct z_heap *h, chunkid_t c)
{
	//right chunk是空闲的
	if (!chunk_used(h, right_chunk(h, c))) {
		//将right chunk从桶中移除
        free_list_remove(h, right_chunk(h, c));
        //合并右chunk
		merge_chunks(h, c, right_chunk(h, c));
	}

	//left chunk是空闲的
	if (!chunk_used(h, left_chunk(h, c))) {
        //left chunk从桶中移除
		free_list_remove(h, left_chunk(h, c));
        //合并左chunk
		merge_chunks(h, left_chunk(h, c), c);
        //左chunk的id是合并后的chunk id
		c = left_chunk(h, c);
	}
    //将合并后的chunk加入到桶中
	free_list_add(h, c);
}

kheap

sys_heap提供的是基本的内存分配算法，无多线程安全。kheap对sys_heap进行包装提供多线程安全的API，以及同步分配等待的特性。从struct k_heap的结构就可以看出来：

1
2
3
4
5
struct k_heap {
	struct sys_heap heap;   //使用的sys_heap
	_wait_q_t wait_q;       // waitq, 用于在分配时无内存进行等待
	struct k_spinlock lock; // 分配/释放内存时上锁，保证多线程访问安全
};

kheap初始化

kheap初始化分为静态和动态两种，静态初始化使用下面宏定义K_HEAP, 在k_heap section中放置bytes大小的全局变量

1
2
3
4
5
6
7
8
#define K_HEAP_DEFINE(name, bytes)				\
	char __aligned(sizeof(void *)) kheap_##name[bytes];	\
	Z_STRUCT_SECTION_ITERABLE(k_heap, name) = {		\
		.heap = {					\
			.init_mem = kheap_##name,		\
			.init_bytes = (bytes),			\
		 },						\
	}

然后代码中注册system init函数

1
SYS_INIT(statics_init, PRE_KERNEL_1, CONFIG_KERNEL_INIT_PRIORITY_OBJECTS);

Zephyr启动时在PRE_KERNEL_1阶段自动调用statics_init对heap进行初始化

1
2
3
4
5
6
7
8
static int statics_init(struct device *unused)
{
	ARG_UNUSED(unused);
	Z_STRUCT_SECTION_FOREACH(k_heap, h) {   //变量k_heap section找出静态定义的heap对其初始化
		k_heap_init(h, h->heap.init_mem, h->heap.init_bytes);
	}
	return 0;
}

动态初始化，可以在代码执行过程中对任意内存使用k_heap_init进行初始化成heap

1
2
3
4
5
void k_heap_init(struct k_heap *h, void *mem, size_t bytes)
{
	z_waitq_init(&h->wait_q);   //初始化waitq
	sys_heap_init(&h->heap, mem, bytes);    //将指定内存初始化成sys_heap
}

kheap分配内存

kheap分配内存是对sys_heap进行包装，有内存是直接进行分配，没有内存时按照设置的超时参数进行等待

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
void *k_heap_alloc(struct k_heap *h, size_t bytes, k_timeout_t timeout)
{
	int64_t now, end = z_timeout_end_calc(timeout);
	void *ret = NULL;
    //多线程保护
	k_spinlock_key_t key = k_spin_lock(&h->lock);

    //irq中分配内存不允许等待
	__ASSERT(!arch_is_in_isr() || K_TIMEOUT_EQ(timeout, K_NO_WAIT), "");

	while (ret == NULL) {
        //从sys_heap分配内存
		ret = sys_heap_alloc(&h->heap, bytes);

		now = z_tick_get();
        //如果分配到或者等待超时，退出等待
		if ((ret != NULL) || ((end - now) <= 0)) {
			break;
		}

        //等待其它线程释放内存
		(void) z_pend_curr(&h->lock, key, &h->wait_q,
				   K_TICKS(end - now));
		key = k_spin_lock(&h->lock);
	}

	k_spin_unlock(&h->lock, key);
	return ret;
}

kheap释放内存

kheap释放内存是对sys_heap进行包装，当释放内存时会让等待分配内存的线程全部退出等待

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void k_heap_free(struct k_heap *h, void *mem)
{
    //多线程保护
	k_spinlock_key_t key = k_spin_lock(&h->lock);

    //释放内存
	sys_heap_free(&h->heap, mem);

    //让所有等待从该heap分配内存的线程都退出等待
	if (z_unpend_all(&h->wait_q) != 0) {
		z_reschedule(&h->lock, key);
	} else {
		k_spin_unlock(&h->lock, key);
	}
}

kernel 内存分配

Zephyr中k_malloc/k_free是通过原本是通过pool来管理的，但Zephyr现在已经决定将废弃k_mem_pool，最新的代码k_mem_pool其后端可通过配置CONFIG_MEM_POOL_HEAP_BACKEND=y用heap实现。
在mempool_heap.h中可以看到struct k_mem_pool使用的时strut k_heap。对POOL的定义也是使用K_HEAP_DEFINE完成

1
2
3
4
5
6
7
8
9
10
11
12
struct k_mem_pool {
	struct k_heap *heap;
};

#define Z_MEM_POOL_DEFINE(name, minsz, maxsz, nmax, align)		\
		K_HEAP_DEFINE(poolheap_##name,				\
			      ((maxsz) * (nmax))			\
			      + 8 * ((maxsz) * (nmax) / (minsz))	\
			      + 15 * sizeof(void *));			\
		struct k_mem_pool name = {				\
			.heap = &poolheap_##name			\
		}

kernel pool的分配和释放

kernel pool的分配和释放是通过k_mem_pool_alloc和k_mem_pool_free_id完成，在CONFIG_MEM_POOL_HEAP_BACKEND=y的情况下这两个函数直接包装的是k_heap_alloc和k_heap_free

内核内存分配函数

在内核中k_malloc分配的内存将_HEAP_MEM_POOL中取得,配置CONFIG_HEAP_MEM_POOL_SIZE可以指定内核可用的heap pool大小

1
2
3
K_MEM_POOL_DEFINE(_heap_mem_pool, CONFIG_HEAP_MEM_POOL_MIN_SIZE,
		  CONFIG_HEAP_MEM_POOL_SIZE, 1, 4);
#define _HEAP_MEM_POOL (&_heap_mem_pool)

k_malloc的调用流程

k_malloc->k_mem_pool_malloc->k_mem_pool_alloc->k_heap_alloc

k_free的调用流程

k_free->k_mem_pool_free_id->k_heap_free

参考

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