内存管理导览

内存 评论

unikraft内存管理导览

unikraft内存管理调用层次

内存分配管理在unikraft中的层次：

1
2
3
4
5
6
7
unikraft memory allocation system

POSIX Compliant external API | plat    nolibc/newlib/musl  |  linuxxu,xen,kvm
---------------------------------	   -------------------
internal allocation API 			   ukalloc(acts as multiplexer)
---------------------------------	   -------------------
backend allocator implementation

概况：

以uk_前缀开头的函数为internal API并暴露给POSIX接口层，例如有uk_malloc( ), uk_calloc( )等等 。与POSIX不同的是，这些函数需要调用者(posix layer?)去指定要使用怎样的allocator后端。

例如uk_malloc( )的定义：

1
static inline void *uk_malloc(struct uk_alloc *a, size_t size);

其中结构体uk_alloc * 参数就代表了allocator的后端。这个结构体内包含了指针指向对于posix接口层(malloc( ), calloc( ), posix_memalign( )等)的具体实现。值得注意的是，热点函数比如internal allocation APIs都采用了内联函数inline的修饰符，来减少函数调用的开销。

ukallocbbuddy, ukallocregion等allocator，分配的内存在不同的地址空间。通过链表串起来，再通过ukalloc这个选择器来具体选择。

在boot时初始化过程中，初始化函数堆中第一个可用的字节会被传递一个void *的base pointer和一个size_t的长度(定义堆的大小)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ukboot/boot.c
    /* try to use memory region to initialize allocator
		 * if it fails, we will try  again with the next region.
		 * As soon we have an allocator, we simply add every
		 * subsequent region to it
		 */
		if (!a) {
#if CONFIG_LIBUKBOOT_INITBBUDDY
			a = uk_allocbbuddy_init(md.base, md.len);
#elif CONFIG_LIBUKBOOT_INITREGION
			a = uk_allocregion_init(md.base, md.len);
#elif CONFIG_LIBUKBOOT_INITMIMALLOC
			a = uk_mimalloc_init(md.base, md.len);
#elif CONFIG_LIBUKBOOT_INITTLSF
			a = uk_tlsf_init(md.base, md.len);
#elif CONFIG_LIBUKBOOT_INITTINYALLOC
			a = uk_tinyalloc_init(md.base, md.len);
#endif
		} else {
			uk_alloc_addmem(a, md.base, md.len);
		}

根据unikraft 论文,uk_alloc共有五个allocator后端:”a buddy system, the Two-Level Segregated Fits [53] (TLSF) real-time memory allocator, tinyalloc [67], Mimalloc [42] (version1.6.1) and the Oscar [12] secure memory allocator”, 实际上在只实现了2个 ukallocbbuddy 和 ukallocregion ; 实际运行时只使用ukallocbbuddy(写死的)

以malloc为例对内存分配函数调用关系的梳理：

最上层为unikraft提供的标准c库(newlib或musl)，对应用层直接提供的malloc

1
2
3
4
5
6
{lib-newlib/mem.c}
/* Forward to libucallocator calls */
void *malloc(size_t size)
{
	return uk_malloc(uk_alloc_get_default(), size);
}

uk_malloc在internal源语层，是一个wrapper function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{ukalloc/include/uk/alloc.h}
static inline void *uk_do_malloc(struct uk_alloc *a, __sz size)
{
	UK_ASSERT(a);
	return a->malloc(a, size);
}

static inline void *uk_malloc(struct uk_alloc *a, __sz size)
{
	if (unlikely(!a)) {
		errno = ENOMEM;
		return __NULL;
	}
	return uk_do_malloc(a, size);
}

a->malloc对于有页表功能的实现方式，interface是如下定义的。在一个页内的malloc在uk层实现，页分配palloc则是由pallloc_func传入，具体在allocbuddy这个内存管理算法中去实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
{ukalloc/include/uk/alloc_impl.h}
#define uk_alloc_init_palloc(a, palloc_func, pfree_func, pmaxalloc_func, \
			     pavailmem_func, addmem_func)		\
	do {								\
		(a)->malloc         = uk_malloc_ifpages;		\
		(a)->calloc         = uk_calloc_compat;			\
		(a)->realloc        = uk_realloc_ifpages;		\
		(a)->posix_memalign = uk_posix_memalign_ifpages;	\
		(a)->memalign       = uk_memalign_compat;		\
		(a)->free           = uk_free_ifpages;			\
		(a)->palloc         = (palloc_func);			\
		(a)->pfree          = (pfree_func);			\
		(a)->pavailmem      = (pavailmem_func);			\
		(a)->availmem       = (pavailmem_func != NULL)		\
				      ? uk_alloc_availmem_ifpages : NULL; \
		(a)->pmaxalloc      = (pmaxalloc_func);			\
		(a)->maxalloc       = (pmaxalloc_func != NULL)		\
				      ? uk_alloc_maxalloc_ifpages : NULL; \
		(a)->addmem         = (addmem_func);			\
									\
		uk_alloc_stats_reset((a));				\
		uk_alloc_register((a));					\
	} while (0)

页内malloc的实现

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
{ukalloc/alloc.c}
// 页内malloc的实现
void *uk_malloc_ifpages(struct uk_alloc *a, __sz size)
{
	__uptr intptr;
	unsigned long num_pages;
	struct metadata_ifpages *metadata;
	__sz realsize = sizeof(*metadata) + size;

	UK_ASSERT(a);
	/* check for invalid size and overflow */
	if (!size || realsize < size)
		return __NULL;

	num_pages = size_to_num_pages(realsize);
	intptr = (__uptr)uk_palloc(a, num_pages);

	if (!intptr)
		return __NULL;

	metadata = (struct metadata_ifpages *) intptr;
	metadata->num_pages = num_pages;
	metadata->base = (void *) intptr;

	return (void *)(intptr + sizeof(*metadata));
}

进入到allocator后端，uk_alloc_init_palloc interface在buddy.c中realize

1
2
3
4
5
{ukallocbbuddy/bbuddy.c}
/* initialize and register allocator interface */
uk_alloc_init_palloc(a, bbuddy_palloc, bbuddy_pfree,
					bbuddy_pmaxalloc, bbuddy_pavailmem,
					bbuddy_addmem);

页分配bbuddy_palloc在buddy内存算法中的实现

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
{{ukallocbbuddy/bbuddy.c}}
static void *bbuddy_palloc(struct uk_alloc *a, unsigned long num_pages)
{
	struct uk_bbpalloc *b;
	size_t i;
	chunk_head_t *alloc_ch, *spare_ch;
	chunk_tail_t *spare_ct;

	UK_ASSERT(a != NULL);
	b = (struct uk_bbpalloc *)&a->priv;

	size_t order = (size_t)num_pages_to_order(num_pages);

	/* Find smallest order which can satisfy the request. */
	for (i = order; i < FREELIST_SIZE; i++) {
		if (!FREELIST_EMPTY(b->free_head[i]))
			break;
	}
	if (i == FREELIST_SIZE)
		goto no_memory;

	/* Unlink a chunk. */
	alloc_ch = b->free_head[i];
	b->free_head[i] = alloc_ch->next;
	alloc_ch->next->pprev = alloc_ch->pprev;

	/* We may have to break the chunk a number of times. */
	while (i != order) {
		/* Split into two equal parts. */
		i--;
		spare_ch = (chunk_head_t *)((char *)alloc_ch
					    + (1UL << (i + __PAGE_SHIFT)));
		spare_ct = (chunk_tail_t *)((char *)spare_ch
					    + (1UL << (i + __PAGE_SHIFT))) - 1;

		/* Create new header for spare chunk. */
		spare_ch->level = i;
		spare_ch->next = b->free_head[i];
		spare_ch->pprev = &b->free_head[i];
		spare_ct->level = i;

		/* Link in the spare chunk. */
		spare_ch->next->pprev = &spare_ch->next;
		b->free_head[i] = spare_ch;
	}
	map_alloc(b, (uintptr_t)alloc_ch, 1UL << order);

	uk_alloc_stats_count_palloc(a, (void *) alloc_ch, num_pages);
	return ((void *)alloc_ch);

no_memory:
	uk_pr_warn("%"__PRIuptr": Cannot handle palloc request of order %"__PRIsz": Out of memory\n",
		   (uintptr_t)a, order);

	uk_alloc_stats_count_penomem(a, num_pages);
	errno = ENOMEM;
	return NULL;
}

而在lib/ukboot中的boot.c启动程序中，有着plat层调用allocator的函数

1
257  rc = ukplat_memallocator_set(a);

也可以看出plat层找到了很多内存块，然后交给ukalloc初始化

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
/* 遍历plat层找到的内存块 */
ukplat_memregion_foreach(&md, UKPLAT_MEMRF_ALLOCATABLE) {
#if CONFIG_UKPLAT_MEMRNAME
		uk_pr_debug("Try memory region: %p - %p (flags: 0x%02x, name: %s)...\n",
			    md.base, (void *)((size_t)md.base + md.len),
			    md.flags, md.name);
#else
		uk_pr_debug("Try memory region: %p - %p (flags: 0x%02x)...\n",
			    md.base, (void *)((size_t)md.base + md.len),
			    md.flags);
#endif

		/* try to use memory region to initialize allocator
		 * if it fails, we will try  again with the next region.
		 * As soon we have an allocator, we simply add every
		 * subsequent region to it
		 */
    
    	/* 将内存块交给allocator管理 */
		if (!a) {
#if CONFIG_LIBUKBOOT_INITBBUDDY
			a = uk_allocbbuddy_init(md.base, md.len);
#elif CONFIG_LIBUKBOOT_INITREGION
			a = uk_allocregion_init(md.base, md.len);
#elif CONFIG_LIBUKBOOT_INITMIMALLOC
			a = uk_mimalloc_init(md.base, md.len);
#elif CONFIG_LIBUKBOOT_INITTLSF
			a = uk_tlsf_init(md.base, md.len);
#elif CONFIG_LIBUKBOOT_INITTINYALLOC
			a = uk_tinyalloc_init(md.base, md.len);
#endif
		} else {
			uk_alloc_addmem(a, md.base, md.len);
		}
	}
	if (unlikely(!a))
		uk_pr_warn("No suitable memory region for memory allocator. Continue without heap\n");
	else {
		rc = ukplat_memallocator_set(a);
		if (unlikely(rc != 0))
			UK_CRASH("Could not set the platform memory allocator\n");
	}
#endif

unikraft内存管理调用图

可以参考此图对涉及内存调用的地方进行逐一阅读

image-20221016224520962

TenonOSunikraft-learning

个人简介。