本文共 8493 字，大约阅读时间需要 28 分钟。

1 slab综述

1.1 slab分配器产生的背景

类似 task_struct mm_struct 等结构被内核中被频繁分配和释放，同时创建和销毁这些结构会产生一定的开销(overhead)。二者累计起来导致大量开销的产生。

Buddy分配器只能分配2^n个页面，对于小于一个页面的内存请求则没有办法。

1.2 对象缓存(object cache)

Slab的基本思想是使用对象缓存去处理需要频繁分配和释放的对象。对象缓存类似于内存池，通过将一系列的对象维持在已创建的状态(constructed state)减少开销。

实例： 一个典型的结构

struct foo {		kmutex_t foo_lock;		kcondvar_t foo_cv;		struct bar *foo_barlist;		int foo_refcnt;}; 创建结构foofoo = kmem_alloc(sizeof (struct foo),KM_SLEEP);mutex_init(&foo->foo_lock, ...);cv_init(&foo->foo_cv, ...);foo->foo_refcnt = 0;foo->foo_barlist = NULL;使用结构foouse foo;销毁结构fooASSERT(foo->foo_barlist == NULL);ASSERT(foo->foo_refcnt == 0);cv_destroy(&foo->foo_cv);mutex_destroy(&foo->foo_lock);kmem_free(foo);

通过对象缓存我们可以直接使用对象，免去了创建 销毁的开销。

1.3 slab分配器的结构

slab分配器分为 cache slab object 三级。cache是一系列同类型的object的集合，有task_struct 的cache，mm_struct的cache。图的下一层是slab，为了方便管理，slab被分成了三种 a. 空闲的slab b. 部分空闲的slab c. 全满的slab。内核只会从部分空闲的slab中分配对象。 slab由一个或多个连续的物理页构成，图中的slabs由连续的slab组成。

2 高速caches

2.1 slabtop命令和/proc/slabinfo

使用slabtop命令或者打印 /proc/slabinfo可以显示系统的slab使用状况。

slabtop的输出：cat /proc/slabinfo的输出：

2.2 通用缓存和专用缓存

为了减少内碎片的产生，slab进一步把缓存分成了通用和专用两部分

2.2.1 通用缓存(general cache)

1 kmem_cache:

kmem_cache是缓存cache_cache的name字段的值。cache_cache用于存储缓存描述符。在创建一个新的缓存时，内核从cache_cache中取出一个对象存储缓存描述符kmem_cache_s。

2 kmalloc使用的缓存

kmalloc使用的缓存又分为Size-N cache 和 Size-N DMA cache。每个cache的大小是2的N次方（N从5到17），即从32字节到131072字节。

2.2.2 专用缓存(specific cache)

专用缓存用于频繁创建销毁的结构。由kmem_cache_create创建一个缓存。kmem_cache_shrink 回收缓存的空间。kmem_cache_destroy 销毁一个缓存。

2.3 缓存描述符(caches descriptor)

struct kmem_cache_s {	//指向本地CPU高速缓存的指针	struct array_cache	*array[NR_CPUS];	//本地缓存一次搬运的空闲对象的个数	unsigned int		batchcount;	//本地缓存的空闲对象的最大个数	unsigned int		limit;	struct kmem_list3	lists;	//对象的大小	unsigned int		objsize;	//缓存的静态Flags	unsigned int	 	flags;	/* constant flags */	//每个slab中对象的个数	unsigned int		num;	/* # of objs per slab */	//缓存中空闲对象的上限	unsigned int		free_limit; /* upper limit of objects in the lists */	//保护描述符的自旋锁	spinlock_t		spinlock;/* 3) cache_grow/shrink */	//一个slab中包含2^gforder个连续的页	unsigned int		gfporder;	//分配页框时使用的Flags	unsigned int		gfpflags;	size_t			colour;		/* cache colouring range */	unsigned int		colour_off;	/* colour offset */	unsigned int		colour_next;	/* cache colouring */	//如果使用off-slab的方式存储slab描述符，则该字段指向存储slab描述符的缓存	kmem_cache_t		*slabp_cache;	//slab的大小	unsigned int		slab_size;	//缓存的动态Flags	unsigned int		dflags;		/* dynamic flags */	//缓存的构造函数	void (*ctor)(void *, kmem_cache_t *, unsigned long);	//缓存的析构函数	void (*dtor)(void *, kmem_cache_t *, unsigned long);	//缓存的名字	const char		*name;	//指向下一个缓存的指针	struct list_head	next;};struct kmem_list3 {	//slabs_partial slab_full slab_free三个双链表	struct list_head	slabs_partial;		struct list_head	slabs_full;	//只包含空闲对象的slab双链表	struct list_head	slabs_free;	//缓存中空闲对象的个数	unsigned long	free_objects;	int		free_touched;	unsigned long	next_reap;	//指向共享本地缓存的指针	struct array_cache	*shared;};

2.3.1 着色相关的字段

关于这几个字段的详细说明请看最后一部分

size_t colour; /* cache colouring range /

unsigned int colour_off; / colour offset /

unsigned int colour_next; / cache colouring */

2.4 缓存的接口

每个缓存有两组接口，分为前端和后端（front end & back end）

前端负责对象的分配和释放，后端负责扩大或回收缓存的内存。

2.5 缓存的创建

kmem_cache_t *

kmem_cache_create (const char name, size_t size, size_t align,

unsigned long flags, void (ctor)(void, kmem_cache_t , unsigned long),

void (dtor)(void, kmem_cache_t *, unsigned long))参数：name: 显示在/proc/slabinfo的缓存名size: 对象的大小alian: 为了与硬件缓存的cache line对齐的偏移量flags:SLAB_POISON：用一个魔数（a5a5a5a5)填充每一个slab，从而可以得到未初始化内存的应用SLAB_NO_REAP：不回收该缓存的空间SLAB_HWCACHE_ALIGN： 将对象与cache line对齐ctor: 缓存的构造dtor: 缓存的析构

Step1: sanity check。检测缓存名是否空，是否处于中断上下文，对象尺寸是否过大或过小，是否只有析构而没有构造。

Step2: 计算对象对齐所使用的偏移量（alignment）。Step3: 从通用缓存（general cache）cache_cache 中获取一个存放缓存描述符的对象。Step4: 调用memset函数用全0填充获得的对象。清楚对象的旧数据。Step5: 判断slab管理单元的存储位置 on-slab Or off-slab，判断条件是 size >= (PAGE_SIZE>>3)Step6: 计算每个slab包含的对象个数，以及每个slab的大小。Step7: 处理off-slab的情况。如果flag是off-slab，但是单个slab的剩余空间大于slab描述符和对象描述的大小(slab_size)。则将flag置为on-slab且left_over - slab_size.将对齐偏移量colour_off 置为缓存行大小。计算cache描述符的其他字段。调用kmem_find_general_cachep获取存储slab描述符的缓存。Step8 处理本地高速缓存cpucache。 总之，创建过程大致上做了两件事，首先获取一个描述缓存的对象，其次计算缓存描述符各个字段的值。

2.6 缓存内存空间的回收

内核使用kmem_cache_shrink回收缓存使用的内存，其调用图如下：

Step1 : __cache_shrink首先调用drain_cpu_caches回收所有本地缓存的内存空间。Step2 : 遍历双向链表slabs_free，销毁所有的free slab。这里可以看到内核只回收只包含空闲对象的slab的内存。

---

3 本地高速缓存(Local Cache)

为了更有效地利用硬件缓存，应该尽量使用一个CPU上的数据。于是，内核采用per-cpu的本地缓存。通过使用本地缓存，每个CPU只访问本地的缓存，减少了条件竞争的发生，也就减少了自旋锁的使用。

3.1 本地缓存描述符

内核使用array_cache结构描述一个本地缓存，其包含4个字段：avail: 本地缓存中可使用的对象个数limit: 本地缓存中对象的最大值batchcount: 本地缓存一次搬运的对象个数touched: 如果本地缓存被使用过，则将其置1

3.2 向本地缓存添加和删除对象

类似于Slab中slab描述符和对象的关系，本地缓存之后就存储的是对象指针。所以通过对指向本地缓存的指针加一，我们就可以获取本地缓存中第一个对象的指针。该工作由内联函数 ac_entry 完成。另外，本地缓存是一个后进先出（LIFO）的结构，这样avail既可以作为本地缓存中可用对象的个数，也可以作为访问对象的下标。

获取本地缓存中第一个可用的对象指针

向本地缓存中增加一个对象

向本地缓存中删除一个对象

3.3 开启本地缓存

开启本地缓存的工作由 enable_cpucache() 完成。这个函数的主要工作是

1 根据缓存(kmem_cache)中的对象的大小，判断本地缓存的limit的大小。2 调用 do_tune_cpucache 给本地缓存分配空间。值的注意的是，本地缓存的空间由kmalloc分配，也就是说本地缓存属于通用缓存的Size-N cache

3.4 共享的本地缓存

list3结构中的shared 字段指向一个由所有CPU共享的本地缓存。

---

4 slab

4.1 slab和cache的关系

4.2 slab描述符

struct slab {	//slab双向链表，该链表有三种 部分空闲链表parial 全部空闲链表free 全满链表full 	struct list_head	list;	//slab使用的colour	unsigned long colouroff;	//slab的第一个对象的地址	void *s_mem; 	//正在使用中的对象个数	unsigned int inuse;		/* num of objs active in slab */	//kmem_bufctl_t数组的首元素        //kmem_bufctl_t实际上是一个unsigned short类型	kmem_bufctl_t free;};typedef unsigned short kmem_bufctl_t;

4.3 on-slab 和 off-slab

slab描述符有两个存储位置，第一种是on-slab, 对象和slab描述符共同存储在slab中，第二种是off-slab, 将slab描述符存储在通用缓存中(general cache).

4.4 kmem_getpages和 cache_grow

当创建新的slab, 内核通过kmem_getpages给slab 分配一组__连续__的页面。

cache_grow 给缓存分配一个新的slab

4.5 kmem_freepages 和 slab_destroy

kmem_freepages 释放slab所使用的连续页框。

slab_destroy 销毁slab中所有的对象，并将其所占用的内存空间还给系统。在这之前，slab必须从cache中移除。

---

5 对象

5.1 kmem_bufctl_t数组

为了以一种快速且简便的方法在部分空闲的链表中找到一个空闲的objetct, 使用kmem_bufctl_t数组存储空闲对象的index，bufctl_end标志该数组的结束。这种方法的关键是，对于对象N，下一个空闲对象的index 会存储在kmem_buf_ctl[N]中。

5.2 分配一个对象

内核通过 kmem_cache_allloc 获得一个空闲对象。

该函数首先试图从本地高速缓存中获得一个空闲对象。当本地缓存中没有空闲对象时，调用 cache_alloc_refill() 函数重新填充本地缓存并获得一个对象。

5.3 释放一个对象

释放对象的工作由 kmem_cache_free 完成。

该函数首先检查本地缓存是否有足够的空间存储一个被释放的对象 ( avail < limit )。如果有足够的空间则将该对象放入本地缓存。当本地缓存中没有空闲对象时，调用 cache_alloc_refill 函数重新填充本地缓存并获得一个空闲对象

---

6. 对象着色和对齐

6.1 直接映射缓存中的冲突不命中

1. 直接映射缓存的cache line

2. 实例分析

   先看一段引发冲突的代码实例：

float foo(float x[8], float y[8]){	float sum = 0.0;	int i;    for (i = 0; i < 8; i++)	    sum += x[i]*y[i];	return sum;}

代码 6-1

假设一个大小为32字节 一个字块是16字节（可以容纳4个浮点数）。则cache共有两个cache line。数组x被存储在内存的前32个字节，数组紧跟在x之后，地址开始在32字节。组索引 = 主存块号 mod 缓存块数在运行时，循环开始使用x[0] , 缓存不命中。x[0] - x[3]被加载到字块0。然后开始使用y[0],缓存不命中。y[0] - y[3]也被加载到字块0，导致字块0的值被覆盖。这样，以后每次使用x[i]或者y[i]都会导致缓存不命中。高速缓存反复加载驱逐同一个缓存行。导致很低的cache命中率。

一种简单的修改这种问题的方法是在数组X后填充4个字节。将x重新定义为float[12]。这样，主存字块0：x[0] - x[3] 主存字块1：x[4] - x[7]主存字块3：y[0] - y[3] 主存字块4：y[4] - y[7]。这样，在使用x[0]时，不命中，x[0] - x[3]被加载到字块0。然后，使用y[0]，不命中，y[0] - y[3]被加载到字块1。随后，x[1] - x[3] 和 y[1] - y[3]都命中。这样，命中率被大大降低。这种现象被称为cache抖动。

6.2 cache着色

如果将一个slab比作是上一部分的数组X和数组Y，我们应该就容易理解为什么要进行cache着色。放置相同类型object的slabs之间更容易发生这种现象。通过在一个slab的头部插入偏移，而减少cache抖动的现象。

那么问题是我们应该怎么计算slab中的着色偏移呢？如何确定使用的着色值的个数呢？

解决这些问题，我们要回顾第一部分讲到的cache描述符和slab描述符的几个字段。

kmem_cache_s:size_t			colour;		/* cache colouring range */unsigned int		colour_off;	/* colour offset */unsigned int		colour_next;	/* cache colouring */slab:unsigned long		colouroff;

代码 6-2

在每个cache描述符中有一个colour_off字段，该值是cache中每个slab的基准偏移。即slab中的着色偏移都是由基准偏移得到。

而colour字段相当于一个着色计数器（从0开始），cache内第一个slab的着色计数器为0，第二个计数器为1，...。以此类推，显然计数器不能无限大，计数器最大等于 cachep-> colour。该值是和每个slab中的空闲空间left_over有关的。是通过公式 cachep->colour = left_over/cachep->colour_off 计算得出的。

而每一个slab的着色偏移都是通过公式 colouroff = 当前slab的着色计数器 * 基准偏移。举例来说如果基准偏移为64字节（一般为硬件cacheline大小），那么第一个slab的着色偏移为0，第二个slab的着色偏移为1 * 64 = 64，第三个slab的着色偏移为2 * 64 = 128。

每当cache要申请一个新的slab时，colour_next就派上了用场。colour_next存储的是将要创建的slab的着色计数器。在cache_grow中，该值会被用来计算新的slab的着色偏移。只要colour_next 大于colour , 那么colour_next就会被置为0。见代码6-3。

cachep->colour = left_over/cachep->colour_off;          offset = cachep->colour_next;cachep->colour_next++;if (cachep->colour_next >= cachep->colour)	cachep->colour_next = 0;offset *= cachep->colour_off;

代码 6-3

图 6-1 插入着色和对齐偏移之后的slab结构

6.3 cache对齐

假设对象A的一个字段大小为16字节，对象A为32字节。 cache块大小为32字节。如果将A存储在地址0处，则A位于主存的字块0，A映射到cache line 0。这样只需要和cache交互一次就可以取出该字段的值。如果将A存储在地址8处，则A映射到主存的字块0和字块1，A映射到cache line0 和 cache line 1。要取出字段值，需要与cache 交互两次。所以，对象需要32字节对齐。

参考文献

1. 深入理解Linux内核
2. 深入理解计算机系统
3. The Slab Allocator: An Object-Caching Kernel Memory Allocator，Bonwick, Jeff，Proceedings of the USENIX Summer Technical Conference - Volume 1，1994