Slab Allocator
slab分配器基本思想：将内核中经常使用的对象放到高速缓存中，并且由系统保持为初始的可利用状态。
slab分配器目的：缓存空闲的对象，保留基本结构，从而能够重复使用它们。
每一个高速缓存包括若干slab，slab由连续的页面帧组成，他们被划分成许多小的块以存放由高速缓存所管理的数据结构和对象。不同数据结构之间的关系如下图所示（slab分配器布局）。
slab分配器三个基本目标：
- 减少伙伴系统分配小块内存时产生的内部碎片。
- 把经常使用的对象缓存起来，减少分配、初始化以及释放对象的时间开销。
- 调整对象以更好地使用L1和L2硬件高速缓存。
为了解决伙伴分配器产生的内部碎片，系统维护两个高速缓存集，这些高速缓存集由小内存缓存组成（大小从25B到217B）。还有一个高速缓存集供DMA设备使用。这些高速缓存集叫做size-N and size-N(DMA)，N是分配器的尺寸。函数 kmalloc() 负责分配这些高速缓存。
下图所示，由伙伴分配器分配的页面如何存储用颜色填充的对象，这些用颜色填充的对象对齐L1 CPU cache。
分配器的API：
1、 Caches（高速缓存）
对于要缓存的每种类型的对象都存在一个缓存。执行 cat /proc/slabinfo 可以得到运行系统中完整的高速缓存列表。这个文件包含高速缓存的基本信息。
其中每一列对应struct kmem_cache_s结构中的一个字段，含义如下：
书中给出的图
为加快分配、释放对象和slab自身的速度，高速缓存中的slab被组织成3个链表：slabs_full，slabs_partial，slabs_free。
- slabs_full：其中所有对象都在使用中。
- slabs_partial：其中有空闲对象，所以分配对象时它是主要的候选。
- slabs_free：其中没有已分配的对象，因此它主要用于slab销毁。
1.1、 高速缓存描述符（Cache Descriptor）
struct kmem_cache_s {
/* 1) each alloc & free */
/* full, partial first, then free */ //对分配和释放对象很重要的成员
struct list_head slabs_full; //其中所有对象都在使用中。
struct list_head slabs_partial; //其中有空闲对象，所以分配对象时它是主要的候选。
struct list_head slabs_free; //其中没有已分配的对象，因此它主要用于slab销毁。
unsigned int objsize; //slab中每一个对象的大小
unsigned int flags; /* constant flags */ //标志位，决定分配器如何处理高速缓存
unsigned int num; /* # of objs per slab */ //每一个slab中包含的对象个数
spinlock_t spinlock; //并发控制锁，避免并发访问高速缓存描述符
#ifdef CONFIG_SMP
unsigned int batchcount;
#endif
/* 2) slab additions /removals */
/* order of pgs per slab (2^n) */ //从高速缓存中分配和释放slab时将用到的字段
unsigned int gfporder;
/* force GFP flags, e.g. GFP_DMA */
unsigned int gfpflags;
size_t colour; /* cache colouring range */
unsigned int colour_off; /* colour offset */
unsigned int colour_next; /* cache colouring */
kmem_cache_t *slabp_cache;
unsigned int growing;
unsigned int dflags; /* dynamic flags */
/* constructor func */
void (*ctor)(void *, kmem_cache_t *, unsigned long);
/* de-constructor func */
void (*dtor)(void *, kmem_cache_t *, unsigned long);
unsigned long failures;
/* 3) cache creation/removal */ //在创建高速缓存时设置
char name[CACHE_NAMELEN];
struct list_head next;
#ifdef CONFIG_SMP
/* 4) per-cpu data */
cpucache_t *cpudata[NR_CPUS];
#endif
#if STATS //在编译时设置CONFIG_SLAB_DEBUG
unsigned long num_active;
unsigned long num_allocations;
unsigned long high_mark;
unsigned long grown;
unsigned long reaped;
unsigned long errors;
#ifdef CONFIG_SMP
atomic_t allochit;
atomic_t allocmiss;
atomic_t freehit;
atomic_t freemiss;
#endif
#endif
};
1.2、高速缓存静态标志位（Cache Static Flags）
第一组是内部标志位，仅由slab分配器使用。
第二组在创建高速缓存时设置，这些标志位决定分配器如何处理slab，如何存储对象。
第三组在编译选项CONFIG_SLAB_DEBUG设置后才有效，它们决定对slab和对象做哪些附加的检查，主要与新建的高速缓存相关。
1.3、高速缓存动态标志位（Cache Dynamic Flags）
dflag中只有一个标志位DFLAG_GROWN，在kmem_cache_grow()中设置，kmem_cache_reap()就不会选择该高速缓存进行回收。kmeme_cache_reap()将跳过设置了该标志位的高速缓存，并清除该标志位。
1.4、高速缓存分配标志位（Cache Allocation Flags）
下表列出的这些标志位，在为slab分配页面时对应的GFP page flag。
有少量的flags可能传递给构造函数和析构函数。如下所示：
1.5、Cache Coloring（缓存着色）
在cache创建期间，可以计算出一个slab可以容纳多少对象，还可以计算出会waste多少字节。根据wastage，可以为cache descriptor计算出两个数值：
- colour: this is the number of defferent offsets that can be used.
- colour_off: this is the multiple to offset each object in the slab.
1.6、创建高速缓存（Cache Creation)
kmem_cache_create()用于创建高速缓存并把他们添加到高速缓存链表中。
- Perform basic sanity checks for bad usage.
- Perform debugging checks if CONFIG SLAB DEBUG is set.
- Allocate a kmem cache t from the cache cache slab cache.
- Align the object size to the word size.
- Calculate how many objects will fit on a slab.
- Align the object size to the hardware cache.
- Calculate color offsets.
- Initialize remaining fields in the cache descriptor.
- Add the new cache to the cache chain.
1.7、回收高速缓存（Cache Reaping）
一个slab空闲时，系统将其放到slab_free链表中，以备将来使用。当kswapd发现内存紧张时，调用kmem_cache_reap()释放内存。对每一个已经检查过的高速缓存中，回收器做如下事：
- Check flags for SLAB NO REAP and skip if set.
- If the cache is growing, skip it.
- If the cache has grown recently or is currently growing, DFLGS GROWN will be
set. If this flag is set, the slab is skipped, but the flag is cleared so that it will
be a r eap candidate the next time. - Count the number of free slabs in slabs free and calculate how many pages
that would free in the variable pages. - If the cache has constructors or large slabs, adjust pages to make it less likely
for the cache to be selected. - If the number of pages that would be freed exceeds REAP PERFECT, fre e h alf
of the slabs in slabs free. - Otherwise, scan the rest of the caches and select the one that would free the
most pages for freeing half of its slabs in slabs free.
1.8、收缩高速缓存（Cache Shrinking）
- 删除per-CPU高速缓存中所有的对象。
- 删除slabs_free中所有slab，除非设置了增长标志位
kmem cache shrink() removes all slabs from slabs_free and returns the number of pages freed as a result. This is the principal function exported for use by the slab allocator users.
kmem cache shrink() frees all slabs from slabs_free and then verifies that slabss_partial and slabs_full are empty. This is for internal use only and is important during cache destruction when it doesn’t matter how many pages are freed, just that the cache is empty.
1.9、销毁高速缓存（Cache Destroying）
一个模块卸载时，Linux销毁与之相关的所有高速缓存。使用kmem_cache_destroy()函数。销毁一个高速缓存的步骤如下：
- Delete the cache from the cache chain.
- Shrink the cache to delete all slabs.
- Free any p er-CPU caches (kfree()).
- Delete the cache descriptor from the cache cache.
2、Slabs的结构和管理
// /mm/slab.c
/*
* slab_t
*
* Manages the objs in a slab. Placed either at the beginning of mem allocated
* for a slab, or allocated from an general cache.
* Slabs are chained into three list: fully used, partial, fully free slabs.
*/
typedef struct slab_s {
struct list_head list;
unsigned long colouroff; //slab中相对于第一个对象基地址的着色偏移。第一个对象的地址是s_mem + colouroff
void *s_mem; /* including colour offset */ //slab中第一个对象的起始地址
unsigned int inuse; /* num of objs active in slab */ //slab中活动的对象数目
kmem_bufctl_t free; //用于存储空闲对象的位置
} slab_t;
typedef unsigned int kmem_bufctl_t;
slab中给定的slab管理器或者对象，没有明显的方法判断它属于哪一个slab或者高速缓存。这里通过struct page里的list字段中的next和prev字段来跟踪对象属于哪一个高速缓存或slab。
SET_PAGE_CACHE()和SET_PAGE_SLAB()函数使用page->list中的next和prev字段来跟踪对象属于哪一个高速缓存或者slab。也可以通过GET_PAGE_CACHE()和GET_PAGE_SLAB()从页面中得到高速缓存或者slab描述符。这些关系如下图所示。
slab描述符的位置由创建高速缓存时对象的大小决定，slab描述符可以存储在slab内，也可以存储在slab外。struct slab_t可以存储在页面帧的首部。
2.1、存储slab描述符（Storing the Slab Descriptor）
对象大于阀值时，就需要设置CFGS_OFF_SLAB，slab描述符保存在slab之外的某个指定大小的高速缓存中，在需要的时候，从kmem_cache_slabmgmt()函数中进行分配。
还可以将slab manager存储在slab的起始处。起始处要留有足够的空间存储slat_t和无符号整型数组kmem_bufctl_t（这个数组用于跟踪下一个可用对象的索引）。实际的对象保存在kmem_bufctl_t数组后。on-slab类型和off-slab类型的图示：
2.2、创建slab（Slab Creation）
高速缓存在创建时，是一个空的高速缓存，slabs_full，slabs_partial，slabs_free也都是空的。通过调用kmem_cache_grow()给高速缓存分配新的slab。在slabs_partial没有对象或者slabs_free中没有slab时也会调用该函数。
调用函数kmem_cache_grow()给高速缓存分配新的slab，调用图如下所示：
该函数完成的任务如下：
- Perform basic sanity checks to guard against bad usage.
- Calculate color offset for objects in this slab.
- Allocate memory for the slab and acquire a slab descriptor.
- Link the pages used for the slab to the slab and cache descriptors described
- Initialize objects in the slab.
- Add the slab to the cache.
2.3、跟踪空闲对象
kmem_bufctl_t是一个简单的对象索引整形数组。得到kmem_bufctl_t数组：
#define slab_bufctl(slabp) \
((kmem_bufctl_t *)(((slab_t*)slabp)+1))
slab中下一个空闲对象的索引存储在slab->free中，分配或者释放对象时，slab->free字段基于kmem_bufctl_t中的信息更新。
2.4、初始化kmem_bufctl_t数组
当高速缓存增长时初始化slab中的对象和kmem_bufctl_t数组。数组被填充为每一个对象的索引，从1开始以标记BUFCTL_END结束。数值0存储在slab_t->free中。对于第n个对象，其下一个空闲对象索引将被存储在em_bufctl_t[n]中，这样排列的数组是一个先进后出队列（LIFO）。
2.5、查找下一个空闲对象
下一个空闲对象索引在kmem_bufctl_t[slab->free]。
2.6、更新kmem_bufctl_t
kmem_cache_free_one()中释放一个对象时才需要更新数组kmem_bufctl_t。更新数组的代码的例子如下：
// /mm/slab.c
unsigned int objnr = (objp - slabp->s_mem)/cachep->objsize;
slab_bufctl(slabp)[objnr] = slabp->free;
slabp->free = objnr;
2.7、计算slab中对象的数量
kmem_cache_estimate()函数计算在单个slab上可以存放多少对象。该函数返回可能存储的对象个数以及浪费的字节数。
基本的计算步骤：
- 初始化wastage为整个slab的大小，例如PAGE_SIZEpfg_order；
- 减去slab描述符所占用的空间；
- 计算可能存储的对象个数。slab描述符存储在slab内部，还要考虑kmem_bufctl_t的大小。持续增加i直至slab被填充；
- 返回对象的个数和浪费的字节数。
2.8、销毁slab
- 有析构函数可用的话，调用slab中所有对象的析构函数。
- 若允许调试，检查red marking和poison pattern。
- 释放slab使用的页面。
3、对象
3.1、初始化slab中的对象
kmem_cache_init_objs()负责初始化对象。遍历slab中所有对象，调用构造函数，并为它初始化kmem_bufctl。
3.2、分配对象
kmem_cache_alloc()负责分配一个对象给调用者。
3.3、释放对象
kmem_cache_free()用于释放对象。在UP中，对象直接返回slab；而在SMP中，对象返回给per-CPU高速缓存。若对象由可用的析构函数的话，函数会调用。析构函数负责把对象状态返回到初始化状态。
参考文献：
[1] 白洛. 深入理解Linux虚拟内存管理. 2006-1
[2] Mel Gorman. Understanding the Linux Virtual Memory Manager. 2004-5-9