Zephyr内存管理之共享Heap

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

本文分析说明Zephyr共享堆机制。

Shared Multi Heap：多堆共享， 将一组不同功能/属性的堆聚合在一起管理，驱动程序或应用程序可以使用不透明的值指示要从这些堆中分配那种特定功能/属性的内存。例如驱动会根据是否使用DMA请求cache或no-cache的内存，应用会根据对内存访问速度的要求请求Soc内部RAM内存或外部的SDRAM内存，在zephyr中可以事先定义好cache堆，no-cache堆，RAM堆，SDRAM堆并添加到多堆管理器，驱动和应用使用共享多堆分配器分配自己想要的功能/属性内存。

Zephyr中在多堆共享的实现上分为两个层级：

  • 多堆管理器：对多各堆进行管理
  • 多堆共享分配器：提供分配选择函数，包装多堆管理器

多堆管理器

接口定义文件：zephyr/include/zephyr/sys/multi_heap.h
实现文件：zephyr/lib/os/multi_heap.c

接口说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//堆选择器回调，根据配置cfg,分配内存的大小size和对齐长度align从mheap中选出匹配的堆
typedef void *(*sys_multi_heap_fn_t)(struct sys_multi_heap *mheap, void *cfg,
				     size_t align, size_t size);

//初始化一个多堆heap，并注册堆选择器choice_fn
void sys_multi_heap_init(struct sys_multi_heap *heap,
			 sys_multi_heap_fn_t choice_fn);

//将堆heap和对应的用户数据user_data添加到多堆管理器mheap中
void sys_multi_heap_add_heap(struct sys_multi_heap *mheap, struct sys_heap *heap, void *user_data);

//按照配置cfg从多堆mheap中分配大小为bytes的内存
void *sys_multi_heap_alloc(struct sys_multi_heap *mheap, void *cfg, size_t bytes);

//按照配置cfg从多堆mheap中分配大小为bytes的内存，分配的内存需要按align长度对齐
void *sys_multi_heap_aligned_alloc(struct sys_multi_heap *mheap,
				   void *cfg, size_t align, size_t bytes);

//根据内存的地址addr，从多堆mheap中找出该内存属于哪个堆
const struct sys_multi_heap_rec *sys_multi_heap_get_heap(const struct sys_multi_heap *mheap,
							 void *addr);

//释放从多堆mheap中分配出的内存block
void sys_multi_heap_free(struct sys_multi_heap *mheap, void *block);

实现原理

多堆通过下面结构体进行管理，最大可以管理8个堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//最多管理8个堆
#define MAX_MULTI_HEAPS 8

//堆信息记录
struct sys_multi_heap_rec {
	struct sys_heap *heap;	//指向被管理的堆
	void *user_data;		//用户数据
};

struct sys_multi_heap {
	int nheaps;					//已管理堆的数量
	sys_multi_heap_fn_t choice;	//堆选择器指针，由sys_multi_heap_init注册
	struct sys_multi_heap_rec heaps[MAX_MULTI_HEAPS];	//堆信息
};

sys_multi_heap_init对堆管理器进行初始化，并注册堆选择器

1
2
3
4
5
void sys_multi_heap_init(struct sys_multi_heap *heap, sys_multi_heap_fn_t choice_fn)
{
	heap->nheaps = 0;
	heap->choice = choice_fn;
}

sys_multi_heap_add_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 sys_multi_heap_add_heap(struct sys_multi_heap *mheap,
			struct sys_heap *heap, void *user_data)
{
	//判断多堆是否已经满了
	__ASSERT_NO_MSG(mheap->nheaps < ARRAY_SIZE(mheap->heaps));

	//记录堆信息
	mheap->heaps[mheap->nheaps].heap = heap;
	mheap->heaps[mheap->nheaps++].user_data = user_data;

	//将堆信息按照，堆的起始地址进行排序，排序是为了sys_multi_heap_get_heap能够通过简单的比较起始地址找到对应的堆
	for (int i = 0; i < mheap->nheaps; i++) {
		struct sys_multi_heap_rec swap;
		int lowest = -1;
		uintptr_t lowest_addr = UINTPTR_MAX;

		for (int j = i; j < mheap->nheaps; j++) {
			uintptr_t haddr = (uintptr_t)mheap->heaps[j].heap->heap;

			if (haddr < lowest_addr) {
				lowest = j;
				lowest_addr = haddr;
			}
		}
		swap = mheap->heaps[i];
		mheap->heaps[i] = mheap->heaps[lowest];
		mheap->heaps[lowest] = swap;
	}
}

sys_multi_heap_get_heap根据内存地址，找到内存所属于的堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const struct sys_multi_heap_rec *sys_multi_heap_get_heap(const struct sys_multi_heap *mheap,
							 void *addr)
{
	uintptr_t haddr, baddr = (uintptr_t) addr;
	int i;

	//由于在加入堆的时候，堆是按照其起始地址顺序添加，因此从小到大找
	//一旦找到堆起始地址大于内存地址的，那么该内存就在前一个堆中， 所以后面使用的是i-1作为序号
	for (i = 0; i < mheap->nheaps; i++) {
		haddr = (uintptr_t)mheap->heaps[i].heap->heap;
		if (baddr < haddr) {
			break;
		}
	}

	/* Now i stores the index of the heap after our target (even
	 * if it's invalid and our target is the last!)
	 * FIXME: return -ENOENT when a proper heap is not found
	 */
	return &mheap->heaps[i-1];
}

目前的实现有两个问题：

  1. 没有堆被管理时，sys_multi_heap_get_heap会挂掉
  2. 内存地址不在被管理的堆范围内也会有堆被给出

从多堆中分配内存，直接调用堆选择器进行选择分配

1
2
3
4
5
6
7
8
9
10
void *sys_multi_heap_alloc(struct sys_multi_heap *mheap, void *cfg, size_t bytes)
{
	return mheap->choice(mheap, cfg, 0, bytes);
}

void *sys_multi_heap_aligned_alloc(struct sys_multi_heap *mheap,
				   void *cfg, size_t align, size_t bytes)
{
	return mheap->choice(mheap, cfg, align, bytes);
}

释放多堆分配器中分配的内存

1
2
3
4
5
6
7
8
9
10
11
void sys_multi_heap_free(struct sys_multi_heap *mheap, void *block)
{
	const struct sys_multi_heap_rec *heap;
	//找到属于哪个堆
	heap = sys_multi_heap_get_heap(mheap, block);

	//将内存释放回堆
	if (heap != NULL) {
		sys_heap_free(heap->heap, block);
	}
}

多堆共享分配器

多堆共享分配器对多堆管理器进行封装提供一个按属性分配内存的共享分配器
接口定义文件：zephyr/include/zephyr/multi_heap/shared_multi_heap.h
实现文件：zephyr/lib/os/shared_multi_heap.c

接口说明

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
enum smh_reg_attr {
	SMH_REG_ATTR_CACHEABLE,			//cache属性
	SMH_REG_ATTR_NON_CACHEABLE,		//non cache属性
	SMH_REG_ATTR_NUM,
};

//堆属性，用于指定堆的起始地址，大小和访问属性
struct shared_multi_heap_region {
	unsigned int attr;	//堆属性，使用enum smh_reg_attr
	uintptr_t addr;	//堆的起始地址
	size_t size;	//堆大小
};

//初始化多堆共享分配器
int shared_multi_heap_pool_init(void);

//将指定的堆region和user_data加入到多堆共享分配器中
int shared_multi_heap_add(struct shared_multi_heap_region *region, void *user_data);

//从多堆共享分配器中分配属性为attr，大小为bytes的内存
void *shared_multi_heap_alloc(unsigned int attr, size_t bytes);

//从多堆共享分配器中分配属性为attr，大小为bytes按照align对齐的内存
//void *shared_multi_heap_aligned_alloc(unsigned int attr, size_t align, size_t bytes);

//释放内存到多堆共享管理器中
void shared_multi_heap_free(void *block);

实现说明

共享多堆分配器使用多堆管理器实现

1
2
3
4
5
6
7
8
//使用一个多堆管理器
static struct sys_multi_heap shared_multi_heap;

//按属性建立堆信息记录数组，每种属性最多8个堆
static struct sys_heap heap_pool[MAX_SHARED_MULTI_HEAP_ATTR][MAX_MULTI_HEAPS];

//记录指定属性的堆有多少个
static unsigned int attr_cnt[MAX_SHARED_MULTI_HEAP_ATTR];

shared_multi_heap_pool_init初始化共享多堆分配器，就是用smh_choice注册初始化一个多堆管理器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int shared_multi_heap_pool_init(void)
{
	static atomic_t state;
	//避免重复初始化控制
	if (!atomic_cas(&state, 0, 1)) {
		return -EALREADY;
	}

	//初始化多堆管理器shared_multi_heap
	sys_multi_heap_init(&shared_multi_heap, smh_choice);

	atomic_set(&state, 1);

	return 0;
}

分配内存时会调用到smh_choice

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
static void *smh_choice(struct sys_multi_heap *mheap, void *cfg, size_t align, size_t size)
{
	struct sys_heap *h;
	unsigned int attr;
	void *block;

	//获取attr并进行范围判断
	attr = (unsigned int)(long) cfg;

	if (attr >= MAX_SHARED_MULTI_HEAP_ATTR || size == 0) {
		return NULL;
	}


	block = NULL;

	for (size_t hdx = 0; hdx < attr_cnt[attr]; hdx++) {
		//从属性匹配的堆中选出heap
		h = &heap_pool[attr][hdx];

		if (h->heap == NULL) {
			return NULL;
		}

		//从选出的heap中分配内存，如果分配不到，就找下一个属性配置的堆进行分配
		block = sys_heap_aligned_alloc(h, align, size);
		if (block != NULL) {
			break;
		}
	}

	return block;
}

shared_multi_heap_add添加堆到多堆共享分配器中

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
int shared_multi_heap_add(struct shared_multi_heap_region *region, void *user_data)
{
	static int n_heaps;
	struct sys_heap *h;
	unsigned int slot;

	if (region->attr >= MAX_SHARED_MULTI_HEAP_ATTR) {
		return -EINVAL;
	}

	//多堆共享分配器中所有的属性的堆总和不能超过MAX_MULTI_HEAPS
	if (n_heaps++ >= MAX_MULTI_HEAPS) {
		return -ENOMEM;
	}

	//初始化堆并将堆添加到多堆管理器中
	slot = attr_cnt[region->attr];
	h = &heap_pool[region->attr][slot];

	sys_heap_init(h, (void *) region->addr, region->size);
	sys_multi_heap_add_heap(&shared_multi_heap, h, user_data);

	//记录指定属性的堆的数量
	attr_cnt[region->attr]++;

	return 0;
}

从多堆中分配shared_multi_heap_alloc/shared_multi_heap_aligned_alloc和释放shared_multi_heap_free很简单，就是调用到sys_multi_heap_alloc/sys_multi_heap_aligned_alloc和sys_multi_heap_free, 而分配最终会调用到smh_choice

参考

https://docs.zephyrproject.org/latest/kernel/memory_management/shared_multi_heap.html