Kernel那些事儿之内存管理(7) --- Slab（上）

前面讲的buddy system算法，分配内存的最小单位是一个页面（例如 4K）。这对于大的内存申请比较适用。可是实际生活中，Kernel经常需要分配小的内存空间，比如几十个字节，这个时候怎么办呢？

不同的人可能会想到不同的解决办法。

1. 对于财大气粗的富人一族，办法很简单：申请一个页面，只用其中的几十字节，剩下的直接丢掉。

2. 对于锱铢必较的穷人一族，就不敢这么挥霍了：申请一个页面，然后记录好页面内哪些内存区用了，哪些还没用，没用的部分可以用来满足其他的内存分配请求。总之务必做到物尽其用。

很不幸，Kernel是个穷人。为了管理小的内存区域，Kernel按照穷人的办法，引入了slab机制。

Slab机制的思想很简单，把内存页面分成一个一个的object，然后以一个object为单位向外提供内存空间。

这样做还带来了一个额外的好处：slab实际充当了cache的角色。Slab会把释放的object放在自己内部结构中，而不是立即返还给buddy system。这样对于新的内存申请，slab就可以把自己留着的object再分配出去，而不用和buddy system打交道。

讲了这么多，是时候看看slab allocator长什么样子了。

Slab机制中主要有三个组成部分:

1) cache 描述符，用来存放管理信息；

2) slab，由一个或多个连续页面组成，里面放着一个个的object；

3) object，被管理的内存单元。

注意，一个cache中存放的都是相同类型的object。

1. Cache 描述符

每个cache是由结构体kmem_cache来表示的。

 381 struct kmem_cache {382 /* 1) per-cpu data, touched during every alloc/free */383     struct array_cache *array[NR_CPUS];384 /* 2) Cache tunables. Protected by cache_chain_mutex */385     unsigned int batchcount;386     unsigned int limit;387     unsigned int shared;388389     unsigned int buffer_size;390     u32 reciprocal_buffer_size;391 /* 3) touched by every alloc & free from the backend */392393     unsigned int flags;     /* constant flags */394     unsigned int num;       /* # of objs per slab */395396 /* 4) cache_grow/shrink */397     /* order of pgs per slab (2^n) */398     unsigned int gfporder;399400     /* force GFP flags, e.g. GFP_DMA */401     gfp_t gfpflags;402403     size_t colour;          /* cache colouring range */404     unsigned int colour_off;    /* colour offset */405     struct kmem_cache *slabp_cache;406     unsigned int slab_size;407     unsigned int dflags;        /* dynamic flags */408409     /* constructor func */410     void (*ctor)(struct kmem_cache *, void *);411412 /* 5) cache creation/removal */413     const char *name;414     struct list_head next;415416 /* 6) statistics */...450     struct kmem_list3 *nodelists[MAX_NUMNODES];454 };

从源代码的注释中可以看出，这个结构体的内容被分为六个部分。其中第六部分，是与debugging相关的统计信息，略去不讲。

前两个部分是与per-cpu相关的信息。

• array: 这是per-cpu的object cache。其原理和我们之前讲的per-cpu page frame cache是一样的，未雨绸缪的机制。

• batchcount：每次填充和缩减object cache时，申请和释放的object的个数。

• limit：每个per-cpu object cache的大小，也就是其最多可以预存多少个object。

• shared: 每个cache中，除了为每个CPU准备的per-cpu object cache，还有一个所有CPU共享的object cache。该cache的大小（即其limit值）为 (cachep->shared*cachep->batchcount)。
  

• buffer_size: 正如前面提到的，一个cache中存放的都是相同类型的object，既然是相同类型，其大小肯定一样。buffer_size就是指定了该cache中每个object的大小。

第三和第四部分是与slab管理相关的信息。

• flags: 定义了cache的一些全局属性，例如 CFLGS_OFF_SLAB 决定了该cache中slab描述符的位置。

• num: 一个slab中包含的object的个数。

• gfporder：指定了一个slab包含的连续页面数，即一个slab包含 2^gfporder 个连续页面。

• gfpflags: slab包含的页面也是从buddy system中分配的。gfpflags 指定了当为slab申请页面时所使用的GFP标志。
  

• colour, colour_off 以及kmem_list3中的colour_next：这三个成员用于slab coloring 机制中。

• slabp_cache：slab描述符有两个可能的存放位置：internal 或 external。Internal是说slab描述符和slab包含的object一起，存放在slab页面中；External是说slab描述符存放在slab页面之外。这里的slabp_cache就指定了 external的slab描述符存放的位置。

• slab_size：slab描述符加上object描述符所占用的空间大小。

• ctor：object的构造函数。当新创建一个slab时，意味着新创建了num个object，此时就会对每个object执行该构造函数。

第五部分是cache的全局信息。

• name：cache的名字。该名字会出现在 /proc/slabinfo 中。

• next：系统中所有的cache都会链接在链表 cache_chain中。

在该结构体的最后，是成员nodelists，其类型为 struct kmem_list3 的指针数组。一个cache中所包含的所有slab，都组织在了这里面。

 287 /*288  * The slab lists for all objects.289  */290 struct kmem_list3 {291     struct list_head slabs_partial; /* partial list first, better asm code */292     struct list_head slabs_full;293     struct list_head slabs_free;294     unsigned long free_objects;295     unsigned int free_limit;296     unsigned int colour_next;   /* Per-node cache coloring */297     spinlock_t list_lock;298     struct array_cache *shared; /* shared per node */299     struct array_cache **alien; /* on other nodes */300     unsigned long next_reap;    /* updated without locking */301     int free_touched;       /* updated without locking */302 };

• 一个slab可能的状态有三个：full, free and partial。这三种类型的slab分别组织在了三个链表中：slabs_full, slabs_free, slabs_partial.

• free_objects: 所有slab中空闲object的总数。

• free_limit：所有slab中空闲object的总数不得超过free_limit，即不允许 free_objects > free_limit.

• shared: 每个CPU有一个自己的object cache。这里又有一个object cache，不过是供所有CPU共享的。

• next_reap, free_touched: 这两个是由内存回收机制使用的，暂时不讲。
  

2. Slab描述符

cache中每个slab是由结构体 slab 来表示的。

 221 struct slab {222     struct list_head list;223     unsigned long colouroff;224     void *s_mem;        /* including colour offset */225     unsigned int inuse; /* num of objs active in slab */226     kmem_bufctl_t free;227     unsigned short nodeid;228 };

• list：根据slab的类型，通过list把slab挂在kmem_list3中的链表slabs_full, slabs_free 或 slabs_partial上。

• colouroff：该slab中第一个object的页内偏移。

• s_mem：该slab中第一个object的地址。

• inuse：该slab中有多少object已经被分配出去了。

• free：该slab中下一个空闲的object的索引。如果没有空闲的object，该值为BUFCTL_END。

3. Object描述符

每个object也有一个描述符，类型为kmem_bufctl_t。这个描述符就简单多了，因为它实际上就是无符号整型。

208 typedef unsigned int kmem_bufctl_t;

所有的object描述符紧挨着slab描述符存放，两者总是基情满满的粘在一块。所以，和slab描述符一样，object描述符也有两个可能的存放位置：

• External object 描述符：存放在slab页面之外，具体位置由cache描述符中的slabp_cache指出。

• Internal object 描述符：存放在slab页面之内。

第 k 个object描述符描述第 k 个object，且只有该object为空闲时才有意义，此时它包含了该slab中下一个空闲object的索引。这样，同一个slab中所有的空闲object 就形成了一个简单的链表。该链表中最后一个object描述符值为BUFCTL_END，表示链尾。

4. Object cache

前面讲buddy system时，讲过一个“未雨绸缪”的机制。当时说过，这是Kernel的一个惯用伎俩，这不，在这里我们又看到了这个伎俩。

该伎俩思想很简单：提前分配好一些资源放在一个per-cpu cache中。这样做可以减少不同CPU之间对锁的竞争，也可以减少对slab中各种链表的操作。

object cache由结构体 array_cache 来表示。

 264 struct array_cache {265     unsigned int avail;266     unsigned int limit;267     unsigned int batchcount;268     unsigned int touched;269     spinlock_t lock;270     void *entry[];  275 };

• avail：该object cache中可用object的个数。同时也作为该cache中第一个空槽的索引，这一点有点像stack中的栈顶指针。所以object cache是一个LIFO的数据结构。

• limit：该object cache的大小。

• batchcount：填充或缩减cache时的chunck size。

• touched：如果该object cache最近被使用过，则touched置为1.

• entry：这是一个dummy array。object cache中所有的object紧跟着该描述符存放。

正如slab描述符和object描述符一样，object cache描述符和其包含的objects也是基情满满的黏在一起的，这些objects 紧跟在描述符后面，其地址由描述符中的entry指出。

注意，这里所说的object，其实是object的地址。

前面讲过，每个CPU都有一个object cache，放在cache描述符的成员变量 array中。除此之外，还有一个所有CPU共享的object cache，放在kmem_list3结构体的成员变量shared中。

这个共享cache的存在，使得从一个CPU的object cache中往另外一个CPU的object cache中移动object的任务变得简单了许多。

至此，我们讲完了slab机制所使用的所有结构体，这些结构体的相互关系大约是这个样子。

5. Slab coloring

如果不考虑slab coloring，一个cache中，由于所有的object大小相同，所以不同slab中相同索引的object，其offset相同。这本不是什么问题，但是如果考虑进hardware cache，具有相同offset的objects很可能会被放在同一个 cache line中，这个很影响性能的。

Slab coloring正是为了解决这个问题引入的。其思想是：在各个slab的开始位置，插入大小不等的一点空间，这样各个slab中相同索引的object就会有不同的offset了。而插入的这个空间，就称为该slab的color。

那要插入的这些空间又是从哪来的呢？一个slab，被分成一个个object后，很有可能会留下一点空间，这些空间不足够再分出一个object，所以只能浪费掉了。就像你拿一块布去做衣服，再好的裁缝，总也会留下点布头、下脚料啥的。

可是Kernel就连这点下脚料都不放过，把它们分成不同的color供slab使用。可见‘物尽其用’这四个字，Kernel真是做到极致了。

让我们来看一下cache中object是怎么存放的。假设一个cache中所有的object都是对齐的，也就是说所有object的内存地址是某个数 (假设为 aln) 的整数倍。

我们定义这样几个变量：

• num: 一个slab中object的个数。

• osize: 每个object的大小。

• dsize: slab描述符和object描述符一共所占空间的大小。如果是external的slab，则该值为0。

• free: 该slab中没有用到的空间的大小，即下脚料的大小。free 肯定是小于 osize的，否则该slab就能再安排出一个object了。不过 free 是可以比 aln 大的。

那么一个slab的大小可以表示为：

slab length = (num * osize) + dsize + free

所谓slab coloring，其实就是把一部分free的空间，从slab的尾部移到slab头部，同时还要满足对齐要求。所以可用的color数为 (free/aln) 。cache描述符中的成员变量 colour，保存的正是这个值。

这些个color会在不同的slab之间平均地分布。下一个要使用的color值保存在结构体kmem_list3的成员变量colour_next中。当创建一个新的slab时，新slab会用colour_next作为自己的color，然后colour_next递增加1。如果增加到了最大值 cachep->colour，那么colour_next变成0，重新开始。这样可以保证，每个slab和其前一个slab，使用的是不同的color。

另外，aln的值会保存在cache描述符中的成员变量colour_off中；而slab描述符中的colouroff，保存的是 (color * aln) + dsize的值，即第一个object的偏移。