ukalloc

内存 评论

ukalloc

论文描述

(机翻)

Unikraft的内存分配子系统由三层组成 :

( 1) 符合POSIX的外部API，

(2) 称为ukalloc的内部分配API

(3) 一个或多个后端分配器实现。

外部接口受向后兼容性的激励，以促进将现有应用程序移植到Unikraft。对于c语言，外部API由修改后的标准库公开，该标准库可以是nolibc (最小，特定于Unikraft的libc实现)，newlib或musl。外部分配接口充当特定于Unikraft的内部分配接口的兼容性包装器，该接口反过来将分配请求重定向到适当的分配器后端 (每个分配器都有其自己的独立内存区域)。因此，内部分配接口用作多路复用工具，该多路复用工具使同一单核内存在多个内存分配后端。

Unikraft 的分配接口公开了 POSIX 接口的 uk_ 前缀版本：uk_malloc()、uk_calloc() 等。与 POSIX 相比，这些函数需要调用者指定应使用哪个分配后端来满足请求。 uk_malloc() 定义为：

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

struct uk_alloc * 参数表示分配后端。 此结构包含引用分配器的 POSIX 分配接口实现的函数指针：malloc()、calloc()、posix_memalign() 等。请注意，与大多数内部分配接口一样，uk_malloc() 被设计为内联 方法以避免分配路径中的任何额外的函数调用开销。

分配器必须指定一个初始化函数，该函数在引导过程的早期由 ukboot 调用。 初始化函数被传递一个指向堆的第一个可用字节的 void * 基指针，以及一个指定堆大小的 size_t len 参数。 他们必须完全初始化分配器并将分配器注册到 ukalloc 接口。 一旦初始化函数返回，分配器就被认为准备好满足内存分配。 引导过程设置内存分配器和内存源之间的关联。

unikraft支持5个分配器后端：a buddy system, the Two-Level Segregated Fits (TLSF) real-time memory allocator, tinyalloc, Mimalloc (version 1.6.1) and the Oscar secure memory allocator.

一种特殊情况是垃圾收集 (GC) 内存分配器，它需要一个线程来执行 GC。我们可以用两个分配器来实现这些，一个用于初始化 GC 线程的早期启动时间，然后是主 GC 分配器，它在其线程启动后立即接管；我们将此解决方案用于 Mimalloc，因为它具有 pthread 依赖项

源码分析

目录结构

ukalloc的目录结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
.
│--alloc.c
│--Config.uk
│--exportsyms.uk
│--libstats.c
│--libstats.ld
│--libstats.localsyms.uk
│--Makefile.uk
│--stats.c
│
└─include
    └─uk
       └─alloc.h
       └─alloc_impl.h

alloc.h

首先是定义了一些复杂函数类型，声明了函数返回值与参数列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef void* (*uk_alloc_malloc_func_t)
		(struct uk_alloc *a, __sz size);
typedef void* (*uk_alloc_calloc_func_t)
		(struct uk_alloc *a, __sz nmemb, __sz size);
typedef int   (*uk_alloc_posix_memalign_func_t)
		(struct uk_alloc *a, void **memptr, __sz align, __sz size);
typedef void* (*uk_alloc_memalign_func_t)
		(struct uk_alloc *a, __sz align, __sz size);
typedef void* (*uk_alloc_realloc_func_t)
		(struct uk_alloc *a, void *ptr, __sz size);
typedef void  (*uk_alloc_free_func_t)
		(struct uk_alloc *a, void *ptr);
typedef void* (*uk_alloc_palloc_func_t)
		(struct uk_alloc *a, unsigned long num_pages);
typedef void  (*uk_alloc_pfree_func_t)
		(struct uk_alloc *a, void *ptr, unsigned long num_pages);
typedef int   (*uk_alloc_addmem_func_t)
		(struct uk_alloc *a, void *base, __sz size);
typedef __ssz (*uk_alloc_getsize_func_t)
		(struct uk_alloc *a);
typedef long  (*uk_alloc_getpsize_func_t)
		(struct uk_alloc *a);

定义了uk_alloc_stats的结构体，用于统计当前分配的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct uk_alloc_stats {
	__sz last_alloc_size; /* size of the last allocation  上次分配的大小*/  
	__sz max_alloc_size; /* biggest satisfied allocation size  最大满足的分配大小*/
	__sz min_alloc_size; /* smallest satisfied allocation size  最小满足的分配大小*/

	__u64 tot_nb_allocs; /* total number of satisfied allocations 满足的分配总数*/
	__u64 tot_nb_frees;  /* total number of satisfied free operations  满足的自由操作总数*/
	__s64 cur_nb_allocs; /* current number of active allocations  当前活动分配的数量*/
	__s64 max_nb_allocs; /* maximum number of active allocations  最大活动分配的数量*/

	__ssz cur_mem_use; /* current used memory by allocations  当前使用的内存分配*/
	__ssz max_mem_use; /* maximum amount of memory used by allocations  分配内存使用的最大量*/

	__u64 nb_enomem; /* number of times failing allocation requests  分配请求失败的次数*/
};

内存分配器 uk_alloc

定义了uk_alloc结构体（分配器，用于封装各类分配行为），并且是以链表的形式存在着。

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
struct uk_alloc {
	/* memory allocation  内存分配*/
	uk_alloc_malloc_func_t malloc;
	uk_alloc_calloc_func_t calloc;
	uk_alloc_realloc_func_t realloc;
	uk_alloc_posix_memalign_func_t posix_memalign;
	uk_alloc_memalign_func_t memalign;
	uk_alloc_free_func_t free;

#if CONFIG_LIBUKALLOC_IFMALLOC
	uk_alloc_free_func_t free_backend;  /*free函数后端*/
	uk_alloc_malloc_func_t malloc_backend;  /*malloc函数后端*/
#endif

	/* page allocation interface  页分配接口*/
	uk_alloc_palloc_func_t palloc;
	uk_alloc_pfree_func_t pfree;
	/* optional interfaces, but recommended  可选接口，但是建议选*/
	uk_alloc_getsize_func_t maxalloc; /* biggest alloc req. (bytes)  最大分配需求（字节）*/
	uk_alloc_getsize_func_t availmem; /* total memory available (bytes)  总可用内存*/
	uk_alloc_getpsize_func_t pmaxalloc; /* biggest alloc req. (pages)  最大分配需求（页）*/
	uk_alloc_getpsize_func_t pavailmem; /* total pages available  总可用页*/
	/* optional interface  可选接口*/
	uk_alloc_addmem_func_t addmem;

#if CONFIG_LIBUKALLOC_IFSTATS
	struct uk_alloc_stats _stats;
#endif

	/* internal */
	struct uk_alloc *next; /*指针*/
	__u8 priv[];
};

可以看到在源码注释中，将uk_alloc中的结构体大致分成了两个部分，一部分是memory allocation interface，另一部分是page allocation interface。

wrapper functions

后面的内容都是wrapper functions，也就是对uk_alloc结构体以及uk_alloc_stats结构体中方法的包装，用于给外部库进行调用。举个例子，当前的uk_malloc函数其实就是对uk_alloc分配器中malloc方法的封装调用行为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);
}

alloc_impl.h

填充函数

该文件首先定义了填充函数，当只实现了API函数的一个子集时兼容性函数可以被分配器实现用来填充’ struct uk_alloc ‘中的回调函数。

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
/**
 * Compatibility functions that can be used by allocator implementations to
 * fill out callback functions in `struct uk_alloc` when just a subset of the
 * API functionality is actually implemented.
 * 当只实现了API函数的一个子集时兼容性函数可以被分配器实现用来填充' struct uk_alloc '中的回调函数。
 */

/* Functions that can be used by allocators that implement palloc(),
 * pfree() and potentially pavail(), pmaxalloc() only
 * 函数只能被实现了palloc(), pfree(), potentially pavail(), pmaxalloc()的allocator调用，没有直接实现malloc等函数，在源码中对应着伙伴算法(ukallocbbuddy)的填充函数
 */
void *uk_malloc_ifpages(struct uk_alloc *a, __sz size);
void *uk_realloc_ifpages(struct uk_alloc *a, void *ptr, __sz size);
int uk_posix_memalign_ifpages(struct uk_alloc *a, void **memptr,
				__sz align, __sz size);
void uk_free_ifpages(struct uk_alloc *a, void *ptr);
__ssz uk_alloc_availmem_ifpages(struct uk_alloc *a);
__ssz uk_alloc_maxalloc_ifpages(struct uk_alloc *a);

#if CONFIG_LIBUKALLOC_IFMALLOC
void *uk_malloc_ifmalloc(struct uk_alloc *a, __sz size);
void *uk_realloc_ifmalloc(struct uk_alloc *a, void *ptr, __sz size);
int uk_posix_memalign_ifmalloc(struct uk_alloc *a, void **memptr,
				     __sz align, __sz size);
void uk_free_ifmalloc(struct uk_alloc *a, void *ptr);
#endif

/* Functionality that is provided based on malloc() and posix_memalign()
	基于malloc()和posix_memalign()提供的功能 
	没有直接实现palloc等函数，在源码中对应着内存池(ukallocpool)的填充函数
	*/
void *uk_calloc_compat(struct uk_alloc *a, __sz num, __sz len);
void *uk_realloc_compat(struct uk_alloc *a, void *ptr, __sz size);
void *uk_memalign_compat(struct uk_alloc *a, __sz align, __sz len);
void *uk_palloc_compat(struct uk_alloc *a, unsigned long num_pages);
void uk_pfree_compat(struct uk_alloc *a, void *ptr, unsigned long num_pages);
long uk_alloc_pavailmem_compat(struct uk_alloc *a);
long uk_alloc_pmaxalloc_compat(struct uk_alloc *a);

stats统计功能

随后定义了uk_alloc_stats的计算函数与计算宏

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
static inline void _uk_alloc_stats_refresh_minmax(struct uk_alloc_stats *stats)
static inline void _uk_alloc_stats_count_alloc(struct uk_alloc_stats *stats,
					       void *ptr, __sz size)
static inline void _uk_alloc_stats_count_free(struct uk_alloc_stats *stats,
					      void *ptr, __sz size)
#if CONFIG_LIBUKALLOC_IFSTATS_GLOBAL
#define _uk_alloc_stats_global_count_alloc(ptr, size) \
	_uk_alloc_stats_count_alloc(&_uk_alloc_stats_global, (ptr), (size))
#define _uk_alloc_stats_global_count_free(ptr, freed_size) \
	_uk_alloc_stats_count_free(&_uk_alloc_stats_global, (ptr), (freed_size))
#else /* !CONFIG_LIBUKALLOC_IFSTATS_GLOBAL */
#define _uk_alloc_stats_global_count_alloc(ptr, size) \
	do {} while (0)
#define _uk_alloc_stats_global_count_free(ptr, freed_size) \
	do {} while (0)
#endif /* !CONFIG_LIBUKALLOC_IFSTATS_GLOBAL */

/*
 * The following macros should be used to instrument an allocator for
 * statistics:
 以下宏应该被用来测量统计信息的分配器:
 */
/* NOTE: If ptr is NULL, an ENOMEM event is counted 
	如果ptr是NULL，则统计一个ENOMEM事件*/
#define uk_alloc_stats_count_alloc(a, ptr, size)			\
	do {								\
		_uk_alloc_stats_count_alloc(&((a)->_stats),		\
					    (ptr), (size));		\
		_uk_alloc_stats_global_count_alloc((ptr), (size));	\
	} while (0)
#define uk_alloc_stats_count_palloc(a, ptr, num_pages)			\
	uk_alloc_stats_count_alloc((a), (ptr),				\
				   ((__sz) (num_pages)) << __PAGE_SHIFT)

#define uk_alloc_stats_count_enomem(a, size)			\
	uk_alloc_stats_count_alloc((a), NULL, (size))
#define uk_alloc_stats_count_penomem(a, num_pages)			\
	uk_alloc_stats_count_enomem((a),				\
				    ((__sz) (num_pages)) << __PAGE_SHIFT)

/* Note: if ptr is NULL, nothing is counted 
	如果ptr是NULL，什么都不会被统计*/
#define uk_alloc_stats_count_free(a, ptr, freed_size)			\
	do {								\
		_uk_alloc_stats_count_free(&((a)->_stats),		\
					   (ptr), (freed_size));	\
		_uk_alloc_stats_global_count_free((ptr), (freed_size));	\
	} while (0)
#define uk_alloc_stats_count_pfree(a, ptr, num_pages)			\
	uk_alloc_stats_count_free((a), (ptr),				\
				  ((__sz) (num_pages)) << __PAGE_SHIFT)

#define uk_alloc_stats_reset(a)						\
	memset(&(a)->_stats, 0, sizeof((a)->_stats))

内存分配器的构造器

随后定义了两种构造器，一个为uk_alloc_init_malloc，直接实现了malloc等内存分配函数，使用了uk_palloc_compat等页分配填充函数对分配器进行构造。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define uk_alloc_init_malloc(a, malloc_f, calloc_f, realloc_f, free_f,	\
			     posix_memalign_f, memalign_f, maxalloc_f,	\
			     availmem_f, addmem_f)			\
	do {								\
		(a)->malloc         = (malloc_f);			\
		(a)->calloc         = (calloc_f);			\
		(a)->realloc        = (realloc_f);			\
		(a)->posix_memalign = (posix_memalign_f);		\
		(a)->memalign       = (memalign_f);			\
		(a)->free           = (free_f);				\
		(a)->palloc         = uk_palloc_compat;			\
		(a)->pfree          = uk_pfree_compat;			\
		(a)->availmem       = (availmem_f);			\
		(a)->pavailmem      = (availmem_f != NULL)		\
				      ? uk_alloc_pavailmem_compat : NULL; \
		(a)->maxalloc       = (maxalloc_f);			\
		(a)->pmaxalloc      = (maxalloc_f != NULL)		\
				      ? uk_alloc_pmaxalloc_compat : NULL; \
		(a)->addmem         = (addmem_f);			\
									\
		uk_alloc_stats_reset((a));				\
		uk_alloc_register((a));					\
	} while (0)

另一个为uk_alloc_init_palloc，直接实现了palloc，pfree等页分配函数，使用了uk_malloc_ifpages等内存分配填充函数对分配器进行构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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)

alloc.c

对alloc_impl中定义的函数进行具体实现。具体体现在实现填充函数这一块儿。

首先是定义了一个结构体叫metadata_ifpages，这个结构体是一个内存分配的元数据，里面的两个成员变量分别为分配内存基址(base)和需要分配的内存页数(num_pages)

1
2
3
4
struct metadata_ifpages {
	unsigned long	num_pages;
	void		*base;
};

填充函数的具体实现

allocbbuddy作为后端实现

如果后端实现了allocbbuddy，那么malloc，free等函数作为填充函数，这里以malloc为例，具体的填充函数名为uk_malloc_ifpages，可以发现其实uk_malloc_ifpages就是对已经后端实现的uk_palloc的封装

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
/*
	用内存分配器a，分配大小为size的内存
*/
void *uk_malloc_ifpages(struct uk_alloc *a, __sz size)
{
    /* 要分配的内存基址的地址 */
	__uptr intptr;
    /* 要分配的内存页数 */
	unsigned long num_pages;
	struct metadata_ifpages *metadata;
    /* 因为元数据也需要占用空间，所以实际分配的总地址空间是元数据的size+实际需要分配的空间的size */
	__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);
    /* 使用uk_palloc(已经在ukallocbbuddy中实现)分配页数，并返回分配的空间基址 */
	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));
}
ukallocpool作为后端实现

而如果内存分配算法后端实现为ukallocpool，那么palloc、pavailmem等页分配函数则会被填充，这里以pavailmem为例，具体填充函数名为uk_alloc_pavailmem_compat，可以发现其实也是对具体实现函数的封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 返回当前可用的内存页数 */
long uk_alloc_pavailmem_compat(struct uk_alloc *a)
{
	__ssz mem;

	UK_ASSERT(a);
	
    /* 计算当前可用的内存大小 */
	mem = uk_alloc_availmem(a);
	if (mem < 0)
		return (long) mem;
	
    /* 除以页的大小，返回对应的内存页数 */
	return (long) (mem >> __PAGE_SHIFT);
}

TenonOSunikraft-learning

个人简介。