0%

Linux内存管理(五)伙伴系统和slab分配器

原图

声明本文转载自知乎兰新宇内存相关文章

内存池

空闲链表(free list)

将内存中所有的空闲内存块通过链表的形式组织起来,就形成了最基础的free list。内存分配时,扫描free list的各个空闲内存块,从中找到一个大小满足要求的内存块,并将该内存块从free list中移除。内存释放时,释放的内存块被重新插入到free list中。

假设现在内存的使用情况是这样的:

灰色部分代表已经被分配的内存块,白色部分代表空闲的内存块,大小分别是48字节,16字节和96字节。如果此时内存分配的申请是12个字节,那么将有以下三种策略可以选择:

  • First fit(最先适配),就是从free list头部开始扫描,直到遇到第一个满足大小的空闲内存块,这里第一个48字节的内存块就可以满足要求。这种方法的优点是相对快一些,尤其是满足要求的空闲内存块位于链表前部的时候,但是在控制碎片数量上不是最优的。

  • Best fit(最佳适配),就是遍历free list的所有空闲内存块,从中找到和所申请的内存大小最接近的空闲内存块,这里第二个16字节的内存块是最接近12字节的。

  • Worst fit(最差适配),也是遍历free list的所有空闲内存块,如果找不到大小刚好匹配的,就从最大的空闲内存块中分配。初看起来很反直觉是不是?但假设接下来的内存申请是64个字节,那只有worst fit的这种方法才能满足需求,所以其价值体现在:分配之后剩下的空闲内存块很可能仍然足够大。

以上讨论的是内存分配的情况,接下来看看内存释放的操作是怎样的。假设从第80字节到第100字节中间的20字节内存被释放了,那么它将和前面相邻的空闲内存块合并:

接下来从第100字节到第112字节中间的12字节内存也被释放了,那么它将同时和前后相邻的空闲内存块合并:

不过,既然用到了链表,那就需要指针,而指针本身也是要占用内存空间的。而且在内存释放时,要判断被释放的内存块前后的内存块是不是也是空闲的,这就需要每个内存块有一个空闲状态的标志位。可以采用的一种方式是bitmap,假设以4个字节为最小分配单位,那么每4字节需要一个bit,因此额外消耗的内存为1/32。

内存池(memory pool)

空闲链表的分配方式简单,但分配效率不高,运行一段时间后容易产生大量的内存碎片,从而恶化了内存利用率。

如果能将一大块内存分成多个小内存(称为内存池),不同的内存池又按照不同的「尺寸」分成大小相同的内存块(比如分别按照32, 64, 128……字节),同一内存池中的空闲内存块按照free list的方式连接。

每次分配的时候,选择和申请的的内存在「尺寸」上最接近的内存池,比如申请60字节的内存,就直接从单个内存块大小为64字节的内存池的free list上分配。

这样减少了free list链表的长度,能够缩短每次内存分配所需的线性搜索的时间,特别适合对实时性要求比较高的系统(比如RTOS)。但要想取得好的效果,需要结合系统实际的内存分配需求,对内存池的大小进行合理的划分。比如一个系统常用的是256字节以下的内存申请,那设置过多的256字节以上的内存池,就会造成内存资源的闲置和浪费。

似乎不是很好把控到底怎样划分内存池最为合适?下文将要介绍的Linux中的buddy分配系统,将基于普通的内存池进行优化,以更贴合大型操作系统对内存管理的需求。

Buddy分配算法

上文介绍了内存池,它的分配快速,但这种“事先就划分好”的方法对系统的适应性较差,不同「尺寸」的内存池之间不能“互通有无”。而buddy分配系统在普通内存池的基础上,允许两个大小相同且相邻的内存块合并,合并之后的内存块的「尺寸」增大,因而将被移动到另一个内存池的free list上。

来看下面这个例子,内存共有1024字节,由32, 64, 128, 256, 512字节为「尺寸」的5个free list组织起来,最小分配单位为32字节(对应位图中的1个bit)。假设现在0到448字节的内存已使用,448到1024字节的内存为空闲(字母编号从A开始,表示分配顺序)。

现在我们要申请128字节的内存,那么首先应该查看「尺寸」为128字节的free list,但很可惜没有,那再看看256字节的free list,还是没有,只能再往上找,到512字节的free list这儿,终于有了一个空闲的内存块A'。

那么将A'划分为256字节的E和E',再将内存块E划分成128字节的F和F',内存块F即是我们需要的内存。之后,在此过程中产生的E'和F'将分别被挂接到「尺寸」为256字节和128字节的free list上,位图中bits的值也会相应变化。

接下来释放128字节的内存块C,由于C相邻的两个内存块都不是空闲状态,因此不能合并,之后C也将被挂接到「尺寸」为128字节的free list上。

然后释放64字节的内存块D,分配器根据位图可知,右侧的D'也是空闲的,且D和D'的大小相同,因此D和D'将合并。按理合并后的空闲内存块C'为128字节,应该被添加到「尺寸」为128字节的free list上,但因为左侧的C也是空闲的,且C和C'的大小相同,因此C和C'还将合并形成B',合并后的空闲内存块将被挂接到「尺寸」为256字节的free list上。

在buddy分配系统中,从物理上,内存块按地址从小到大排列;从逻辑上,内存块通过free list组织。通过对相邻内存块的合并,增加了内存使用的灵活性,减少了内存碎片。

但是实现合并有一个前提,就是内存块的尺寸必须是2的幂次方(称为"order"),这也是buddy系统划分内存块的依据。此外,每次内存释放都要查找左右的buddy是否可以合并,还可能需要在free list之间移动,也是一笔不小的开销。

Slab

Linux中的buddy分配器是以page frame为最小粒度的,而现实的应用多是以内核objects(比如描述文件的"struct inode")的大小来申请和释放内存的,这些内核objects的大小通常从几十字节到几百字节不等,远远小于一个page的大小。

那可不可以把一个page frame再按照buddy的原理,以更小的尺寸(比如128字节,256字节)组织起来,形成一个二级分配系统呢?这就是slab分配器。

cache和slab

在slab分配器中,每一类objects拥有一个"cache"(比如inode_cache, dentry_cache)。之所以叫做"cache",是因为每分配一个object,都从包含若干空闲的同类objects的区域获取,释放时也直接回到这个区域,这样可以缓存和复用相同的objects,加快分配和释放的速度。

object从"cache"获取内存,那"cache"的内存又是从哪里来的呢?还是得从buddy分配器来。slab层直接面向程序的分配需求,相当于是前端,而buddy系统则成为slab分配器的后端。

由于"cache"的内存是从buddy系统获得的,因此在物理上是连续的。如果一个"cache"中objects的数目较多,那么"cache"的体积较大,需要占用的连续物理内存较多。当object的数量增加或减少时,也不利于动态调整。因此,一个"cache"分成了若干个slabs。

数据结构

一个"cache"在Linux中由"struct kmem_cache"结构体描述:

1
2
3
4
5
6
7
8
9
10
11
struct kmem_cache {
unsigned int gfporder; /* order of pages per slab (2^n) */
gfp_t allocflags; /* force GFP flags */

unsigned int num; /* objects per slab */
int object_size;
unsigned int colour_off; /* colour offset */
size_t colour; /* cache colouring range */

struct list_head list; /* cache creation & removal */
}

一个slab由一个或多个page frame组成(通常为一个),根据buddy系统的限制,在数量上必须是2的幂次方,"gfporder"实际就定义了一个"cache"中每个slab的大小。

既然涉及到page frame的分配,那自然离不开GFP flags,比如要求从DMA中分配,就需要指定"GFP_DMA"。

   s,数量由"num"表示,每个object的大小由"object_size"给出。一个object可能跨越2个page frames。

如果object的内存地址能按一定字节数(比如总线宽度)或者按硬件cache line的大小对齐,将可以提高读写性能。此外,不同slabs中具有相同偏移的objects,大概率会落在同一cache line上,造成cache line的争用,所以最好加上不同的填充,以错开对cache line的使用。这些偏移和填充,共同构成了slab的coloring机制。

可见啊,slab cache除了和硬件cache一样都使用了“缓存”的思想,它还在实现中充分利用了硬件cache提供的特性,以进一步提高运行效率。但付出的代价就是,不管对齐还是填充,都需要额外的字节,这对内存资源也会造成一定的消耗。

统计信息

可通过"slabtop"命令查看当前系统的slab分配情况:

如上图所示,系统中slab分配器一共占据了46059.92KB内存,包括115个"caches",12126个"slabs"(平均每个cache拥有105个slabs),170077个"objects"(平均每个slabs拥有14个objects)。在所有的objects中,最小的为0.02KB,最大的为4096KB,平均值是0.27KB。

此外,还有细分的每类objects的信息,比如从"inode cache"可以得知打开了9150个文件,从"vm_area_struct"可以得知所有进程一共使用了2140个VMA。并且,还能大致知道每类object的控制结构的大小,比如一个"struct dentry"大约占据0.19KB的内存空间。

虽然没有per-slab包含的pages数目信息,不过完全可以通过"OBJ/SLAB"乘以"SIZE"计算出来。比如通过这种方法算出来"dentry"的就是大约4KB,说明每个"dentry"的slab包含一个page frame。

其更重要的意义是体现在调试的时候:当你发现当前内存资源比较紧张,通过"/proc/meminfo"查到是"Slab"占据了较大内存,根据"slabtop"就可以快速知道是哪一类object消耗的最多(比如建立了过多的socket)。

"slabtop"其实和可以显示CPU和内存占用率的"top"命令是类似的,都是动态地显示目前资源占用率最高的,只不过"top"针对的是进程,而"slabtop"针对的是"caches"。如果要获取全部"caches"的信息,应查看"/proc/slabinfo"文件。

创建和初始化

创建一个新的"cache"的函数接口是kmem_cache_create(),主要就是为"kmem_cache"的控制结构分配内存空间并初始化。而这个控制结构本身也是一个内核object,按理也应该从slab cache中获取,那第一个"kmem_cache"从哪里来?这就形成了一个“先有鸡还是先有蛋”的问题,解决的办法是在slab子系统生效之前的启动阶段,用一段特殊的boot cache来分配。

"cache"创建后,一开始不含有任何的slab,也就没有任何空闲的objects,只有当产生分配一个新的object的需求时,才开始创建slab。创建一个slab除了需要分配容纳objects的内存(相当于user data),还需要生成管理这个slab的控制信息(相当于meta data,这里称为slab descriptor)。

一个slab区域包括若干个大小相同的objects,以及它们的coloring消耗的字节。一个"cache"的多个slabs通过双向链表连接,因而需要存储链表指针的空间。

根据object的大小不同,slab descriptor本身占据的内存可以位于其管理的slab内存区域内部,也可以位于外部(off-slab) 。当位于内部时,链表指针存储在一个slab区域的末尾。

1
2
3
4
5
6
7
8
if (OFF_SLAB(cachep)) {
/* Slab management obj is off-slab */
freelist = kmem_cache_alloc_node(cachep->freelist_cache, ...);
}
else {
/* We will use last bytes at the slab for freelist */
freelist = addr + (PAGE_SIZE << cachep->gfporder) - cachep->freelist_size;
}

分配object

内核编程中如果需要申请在物理上连续的内存,最常用的函数就是kmalloc()了,而它的底层实现依靠的正是slab cache。

1
2
3
4
5
6
7
8
9
static __always_inline void *__do_kmalloc(size_t size, gfp_t flags, ...)
{
if (unlikely(size > KMALLOC_MAX_CACHE_SIZE))
return NULL;
struct kmem_cache *cachep = kmalloc_slab(size, flags);
void * ret = slab_alloc(cachep, flags, ...);

return ret;
}

如果传入的参数是"sizeof(struct inode)"这样的,可能刚好有object大小完全匹配的cache。如果参数是一个普通的整数(比如100),那就需要遍历cache,并进行一定的计算,以寻找最合适的。

第一级分配(fast path)

每个"kmem_cache"除了包含多个slabs外,还包含一组"cpu_cache",这是一种per-CPU的cache,是slab的cache。这么说可能有点绕口,其实就是一个软件层面的二级cache。拿硬件cache来类比,"cpu_cache"就是L1 cache,slab就是L2 cache。

1
2
3
4
5
6
7
struct array_cache __percpu *cpu_cache;

struct array_cache {
unsigned int avail;
unsigned int limit;
void *entry[];
};

"entry[]"表示了一个遵循LIFO顺序的数组(Last In, First Out),"avail"和"limit"分别指定了当前可用objects的数目和允许容纳的最大数目。

每当object试图从slab中分配内存时,都先从所在CPU对应的"entry[]"数组中获取。per-CPU的设计可以减少SMP系统对全局slab的锁的竞争,一些CPU bound的线程尤其适合使用CPU bound的内存分配。

1
2
3
4
5
6
7
8
9
10
11
12
13
void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
{
void *objp;

struct array_cache *ac = cpu_cache_get(cachep);
if (likely(ac->avail)) {
objp = ac->entry[--ac->avail];
return objp;
}

objp = cache_alloc_refill(cachep, flags);
...
}

第二级分配(slow path)

如果在申请时数组为空,那么就需要从全局的slab中refill,那选择哪个slab呢?为了减少内存碎片,一个cache的slabs在每个内存node中(per-node),根据使用状态被分成了三类:

  • 全部分配完,没有空闲objects的full slabs。
  • 分配了一部分,尚有部分空闲的partial slabs。
  • 完全空闲可用的free slabs。
1
2
3
4
5
6
7
8
struct kmem_cache_node *node[MAX_NUMNODES];

struct kmem_cache_node {
struct list_head slabs_partial;
struct list_head slabs_full;
struct list_head slabs_free;
...
}

应首先从partial slabs中选择,等partial slabs都满了,成为了full slab,这时再从free slabs中选择。

又是per CPU,又是per node,在大型系统中,这是一笔不小的开销。

第三级分配(very slow path)

如果一个cache连free slab都没有了,那就需要新增一个slab来“扩容”了。新增slab的方法在上文已经介绍过了,最终是向buddy系统申请,回到这篇文章描述的page level分配器的代码路径。

释放object

释放时也归还到所在CPU的"cpu_cache"数组,如果释放导致数组溢出,则数组中的一部分entries将被返还到全局的slab中。

1
2
3
4
5
6
7
8
9
10
11
void ___cache_free(struct kmem_cache *cachep, void *objp, ..)
{
struct array_cache *ac = cpu_cache_get(cachep);

if (ac->avail >= ac->limit) {
// 归还到对应的slab
cache_flusharray(cachep, ac);
}

ac->entry[ac->avail++] = objp;
}

我们平时常调用的接口是kfree(),只有一个表示地址的参数,那如何知道应该归还到哪个slab中?寻找的方法是首先根据object的虚拟地址找到object所在的page frame,进而找到这个page frame所在compound page的中的head page,而head page中的"slab_cache"指针就指向了这个object所属的slab。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void kfree(const void *objp)
{
struct kmem_cache *c = virt_to_cache(objp);
__cache_free(c, (void *)objp, _RET_IP_);
...
}

struct kmem_cache *virt_to_cache(const void *obj)
{
struct page *page = virt_to_head_page(obj);
return page->slab_cache;
}

struct page *virt_to_head_page(const void *x)
{
// object所在的page frame
struct page *page = virt_to_page(x);
// 所在compound page的head page
return compound_head(page);
}

借助这条路径,进而还可以知道一个object的大小。

1
2
3
4
5
size_t __ksize(const void *objp)
{
struct kmem_cache *c= virt_to_cache(objp);
size_t size = c ? c->object_size : 0;
}

小结

至此,slab分配器的原理和在Linux中的实现就粗略的介绍完了,可以借助下面这张图来一览它的构成,包括kernel object, page frame和slab cache的关系,物理内存的组织和分配等。

slab分配器对内存的利用率是比较高的,因为充分借助了各种缓存机制,分配和释放的速度也比较理想。存在的缺点就是要为内核中众多的objects维护独立的cache,这会带来相当的管理上的开销。

kmalloc

内核中常用的kmalloc()函数的核心实现是slab机制。类似于伙伴系统机制,在内存块中按照$ 2^{order} $字节来创建多个slab描述符,如16字节、32字节、64字节、128字节等大小,系统会分别创建kmalloc-16、kmalloc-32、kmalloc-64等slab描述符,在系统启动时这在create_kmalloc_caches()函数中完成。例如,要分配30字节的一个小内存块,可以用“kmalloc(30,GFP_KERNEL)实现,之后系统会从kmalloc-32 slab描述符中分配一个对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static __always_inline void *kmalloc(size_t size, gfp_t flags)
{
if (__builtin_constant_p(size)) {
#ifndef CONFIG_SLOB
unsigned int index;
#endif
if (size > KMALLOC_MAX_CACHE_SIZE)
return kmalloc_large(size, flags);
#ifndef CONFIG_SLOB
index = kmalloc_index(size);

if (!index)
return ZERO_SIZE_PTR;

return kmem_cache_alloc_trace(
kmalloc_caches[kmalloc_type(flags)][index],
flags, size);
#endif
}
return __kmalloc(size, flags);
}

kmalloc_index可以用于查找使用的是哪个slab缓冲区,这很形象的展示了kmalloc的设计思想。

1
#define kmalloc_index(s) __kmalloc_index(s, true)
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
static __always_inline unsigned int __kmalloc_index(size_t size,
bool size_is_constant)
{
if (!size)
return 0;

if (size <= KMALLOC_MIN_SIZE)
return KMALLOC_SHIFT_LOW;

if (KMALLOC_MIN_SIZE <= 32 && size > 64 && size <= 96)
return 1;
if (KMALLOC_MIN_SIZE <= 64 && size > 128 && size <= 192)
return 2;
if (size <= 8) return 3;
if (size <= 16) return 4;
if (size <= 32) return 5;
if (size <= 64) return 6;
if (size <= 128) return 7;
if (size <= 256) return 8;
if (size <= 512) return 9;
if (size <= 1024) return 10;
if (size <= 2 * 1024) return 11;
if (size <= 4 * 1024) return 12;
if (size <= 8 * 1024) return 13;
if (size <= 16 * 1024) return 14;
if (size <= 32 * 1024) return 15;
if (size <= 64 * 1024) return 16;
if (size <= 128 * 1024) return 17;
if (size <= 256 * 1024) return 18;
if (size <= 512 * 1024) return 19;
if (size <= 1024 * 1024) return 20;
if (size <= 2 * 1024 * 1024) return 21;
if (size <= 4 * 1024 * 1024) return 22;
if (size <= 8 * 1024 * 1024) return 23;
if (size <= 16 * 1024 * 1024) return 24;
if (size <= 32 * 1024 * 1024) return 25;

if ((IS_ENABLED(CONFIG_CC_IS_GCC) || CONFIG_CLANG_VERSION >= 110000)
&& !IS_ENABLED(CONFIG_PROFILE_ALL_BRANCHES) && size_is_constant)
BUILD_BUG_ON_MSG(1, "unexpected size in kmalloc_index()");
else
BUG();

/* Will never be reached. Needed because the compiler may complain */
return -1;
}

与vmalloc区别(都是分配内核空间内存):

  • kmalloc分配物理连续的地址,而vmalloc分配虚拟地址连续的空间
  • kmalloc可以通过gfp_mask标志控制分配内存时不能休眠,因此可以用于中断上下文(softirq和tasklet也处于中断上下文),而vmalloc的调用可能引起睡眠不能用于中断上下文
  • kmalloc性能更好(内核空间更多实用这个函数),而vmalloc为了把物理上不连续的页转换为虚拟地址空间上连续的页,需要建立专门的页表项,会导致TLB抖动等问题,性能不佳(主要用于用户空间分配内存)

参考文献

https://zhuanlan.zhihu.com/p/106106008