内存碎片

一 定义：

在小对象对内存的频繁的动态申请和释放的过程中，由于释放后留下的空洞不够新对象的分配，导致不连续的内存可用空间无法被应用程序获得，造成可用内存迅速备耗尽。这样就造成了内存碎片的产生。

内存分配程序浪费内存的基本方式有三种：即额外开销、内部碎片以及外部碎片（图 1）。内存分配程序需要存储一些描述其分配状态的数据。这些存储的信息包括任何一个空闲内存块的位置、大小和所有权，以及其它内部状态详情。一般来说，一个运行时间分配程序存放这些额外信息最好的地方是它管理的内存。内存分配程序需要遵循一些基本的内存分配规则。例如，所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址。内存分配程序把仅仅预定大小的内存块分配给客户，可能还有其它原因。当某个客户请求一个 43 字节的内存块时，它可能会获得 44字节、48字节 甚至更多的字节。由所需大小四舍五入而产生的多余空间就叫内部碎片。
　　外部碎片的产生是当已分配内存块之间出现未被使用的差额时，就会产生外部碎片。例如，一个应用程序分配三个连续的内存块，然后使中间的一个内存块空闲。内存分配程序可以重新使用中间内存块供将来进行分配，但不太可能分配的块正好与全部空闲内存一样大。倘若在运行期间，内存分配程序不改变其实现法与四舍五入策略，则额外开销和内部碎片在整个系统寿命期间保持不变。虽然额外开销和内部碎片会浪费内存，因此是不可取的，但外部碎片才是嵌入系统开发人员真正的敌人，造成系统失效的正是分配问题。

显然，如果为了存放很少的字节而给它分配一个整页框，这显然是一种浪费。取而代之的正确方法就是引入一种新的数据结构来描述在同一页框中如何分配小内存区。但这样也引出了一个新的问题，即传说中的内部碎片（internal fragmentation）。内部碎片的产生主要是由于请求内存的大小与分配给它的大小不匹配而造成的，例如为某一数据结构分配一个页，该数据结构只有几个字节，那么有上千字节的空间被当做碎片给浪费掉；即使多个此数据结构通过一定规则挤进一个页面，那么也还有若干字节的空间被浪费。

下面，我们引出本故事的主角 —— slab分配器

这里先给出slab分配器的一些特性，下面的文字可能晦涩难懂，大家可以先把后面的数据结构和相关算法掌握了再回过头来浏览：

（1）所存放数据的类型可以影响内存区的分配方式。例如，当给用户态进程分配一个页框时，内核调用get_zeroed_page()函数用0 填充这个页。slab 分配器概念扩充了这种思想，并把内存区看作对象（object），这些对象由一组数据结构和几个叫做构造（constructor）或析构（destructor）的函数（或方法）组成。前者初始化内存区，而后者回收内存区。为了避免重复初始化对象，slab分配器并不丢弃已分配的对象，而是释放但把它们保存在内存中。于是，slab分配器具有了想当一部分缓存的功能，当以后又要请求新的对象时，就可以从内存获取而不用重新初始化。

（2）内核函数倾向于反复请求同一类型的内存区。例如，只要内核创建一个新进程，它就要为一些固定大小的数据结构分配内存区。当进程结束时，包含这些数据结构的内存区还可以被重新使用。因为进程的创建和撤消非常频繁，在没有slab分配器时，内核把时间浪费在反复分配和回收那些包含同一内存区的页框上；slab分配器把那些页框保存在高速缓存中并很快地重新使用它们。

（3）对内存区的请求可以根据它们发生的频率来分类。对于预期频繁请求一个特定大小的内存区而言，可以通过创建一组具有适当大小的专用对象来高效地处理，由此以避免内碎片的产生。另一种情况，对于很少遇到的内存区大小，可以通过基于一系列几何分布大小（如早期Linux 版本所使用的2的幂次方大小）的对象的分配模式来处理，即使这种方法会导致内碎片的产生。

（4）在引入的对象大小不是几何分布的情况下，也就是说，数据结构的起始地址不是物理地址值的2 的幂次方，事情反倒好办。这可以借助处理器硬件高速缓存而导致较好的性能。

（5）硬件高速缓存的高性能又是尽可能地限制对伙伴系统分配器调用的另一个理由，因为对伙伴系统函数的每次调用都“弄脏”硬件高速缓存，所以增加了对内存的平均访问时间。内核函数对硬件高速缓存的影响就是所谓的函数“足迹（footprint）”，其定义为函数结束时重写高速缓存的百分比。显而易见，大的“足迹”导致内核函数刚执行之后较慢的代码执行，因为硬件高速缓存此时填满了无用的信息。

slab 分配器把对象分组放进高速缓存。每个高速缓存都是同种类型对象的一种“储备”。例如，当一个文件被打开时，存放相应“打开文件”对象所需的内存区是从一个叫做filp（“文件指针”）的slab 分配器的高速缓存中得到的。

包含高速缓存的主内存区被划分为多个slab，每个slab 由一个或多个连续的页框组成，这些页框中既包含已分配的对象，也包含空闲的对象。我们将在以后有关回收页框的博文中看到，内核周期性地扫描高速缓存并释放空slab 对应的页框。

1 数据结构

每个高速缓存都是由kmem_cache_t（等价于struct kmem_cache_s类型）类型的数据结构来描述的；kmem_cache_t 描述符的lists 字段又是一个kmem_list3结构体，而kmem_list3中的slabs_partial、slabs_full、slabs_free分别包含空闲和非空闲对象的slab 描述符双向循环链表；不包含空闲对象的slab 描述符双向循环链表；只包含空闲对象的slab 描述符双向循环链表；高速缓存中的每个slab 都有自己的类型为slab 的描述符, 其中的colouroff字段表示slab中第一个对象的偏移；s_mem字段表示slab中第一个对象（或者已被分配, 或者空闲）的地址；inuse字段表示当前正在使用的（非空闲）slab 中的对象个数；最后free字段表示slab中下一个空闲对象的下标，如果没有剩下空闲对象则为BUFCTL_END。

数据结构全图如下所示：

在系统初始化期间内核调用kmem_cache_init()和kmem_cache_sizes_init()来建立搭建一个高速缓存平台，我们只是简单地提一提相关的流程。首先，初始化一个kmem_cache_t类型的cache_cache缓存，取名叫做kmem_cache：
static kmem_cache_t cache_cache = {
.lists = LIST3_INIT(cache_cache.lists),
.batchcount = 1,
.limit = BOOT_CPUCACHE_ENTRIES,
.objsize = sizeof(kmem_cache_t),
.flags = SLAB_NO_REAP,
.spinlock = SPIN_LOCK_UNLOCKED,
.name = "kmem_cache",
#if DEBUG
.reallen = sizeof(kmem_cache_t),
#endif
};

这个缓存用来分配kmem_cache_t类型的slab对象，也就是给缓存自身分配缓存的，所以叫做cache_cache，缓存中的缓存。初始化好cache_cache以后，将它作为第一个元素插到cache_chain循环链表中。

随后，初始化另外一些高速缓存包含用作通用用途的类型的slab对象。内存区大小的范围一般包括13个几何分布的内存区。一个叫做malloc_sizes的表（其元素类型为cache_sizes）分别指向26个高速缓存描述符，与其相关的内存区大小为32, 64, 128, 256, 512,1024, 2048, 4096, 8192, 16384, 32768, 65536 和131072 字节。对于每种大小，都有两个高速缓存：一个适用于ISA DMA 分配，另一个适用于常规分配。其kmem_cache_t.name取名类似size-64或size-64(DMA)。

以上操作完成后，整个slab高速缓存平台就搭建好了，我们就可以用kmem_cache_create()函数来创建各个专用对象的缓存了。这个函数首先根据参数确定处理新高速缓存的最佳方法（例如，是在slab 的内部还是外部包含slab 描述符）。然后它从cache_cache普通高速缓存中为新的高速缓存分配一个高速缓存描述符kmem_cache_t：
(kmem_cache_t *) kmem_cache_alloc(&cache_cache, SLAB_KERNEL);
并把这个描述符插入到高速缓存描述符的cache_chain链表中（当获得了用于保护链表避免被同时访问的cache_chain_sem 信号量后，插入操作完成）。

还可以调用kmem_cache_destroy()撤销一个高速缓存并将它从cache_chain链表上删除。这个函数主要用于模块中，即模块装入时创建自己的高速缓存，卸载时撤销高速缓存。为了避免浪费内存空间，内核必须在撤销高速缓存本身之前就撤销其所有的slab。kmem_cache_shrink()函数通过反复调用slab_destroy()撤销高速缓存中所有的slab。

所有普通和专用高速缓存的名字都可以在运行期间通过读取/proc/slabinfo文件得到。这个文件也指明每个高速缓存中空闲对象的个数和已分配对象的个数。当创建一个新的slab高速缓存时，kmem_cache_create()函数决定本地高速缓存的大小（将这个值存放在高速缓存描述符的limit字段中），范围从1（相对于非常大的对象）到120（相对于小对象）。

高速缓存描述符的array 字段是一组指向array_cache数据结构的指针，系统中的每个CPU 对应于一个元素。每个array_cache 数据结构是空闲对象的本地高速缓存的一个描述符，它的字段如下：
struct array_cache {
unsigned int avail;
unsigned int limit;
unsigned int batchcount;
unsigned int touched;
};

注意，本地高速缓存描述符并不包含本地高速缓存本身的地址；事实上，本地高速缓存是一个数组，正好位于描述符之后，它没有数组名称，我们只是通过((void**)(array_cache+1))运算得到其首地址。还有一点千万别混淆了，本地高速缓存数组存放的是指向已释放对象的指针，而不是对象本身，对象本身总是位于高速缓存的slab 中。这一切，图中都画得很清晰了。

当创建一个新的slab高速缓存时，kmem_cache_create()函数决定本地高速缓存的大小（将这个值存放在高速缓存描述符的limit字段中）、分配本地高速缓存，并将它们的指针存放在高速缓存描述符的array字段。这个大小取决于存放在slab高速缓存中对象的大小，范围从1（相对于非常大的对象）到120（相对于小对象）。此外，batchcount字段的初始值，也就是从一个本地高速缓存的块里添加或删除的对象的个数，被初始化为本地高速缓存大小的一半（系统管理员通过写入/proc/slabinfo文件可以为每个高速缓存调整本地高速缓存的大小以及batchcount 字段的值。）

在多处理器系统中，小对象使用的slab 高速缓存同样包含一个附加的本地高速缓存，它的地址被存放在高速缓存描述符的lists.shared字段中。共享的本地高速缓存正如它的名字暗示的那样，被所有CPU共享，它使得将空闲对象从一个本地高速缓存移动到另一个高速缓存的任务更容易。它的初始大小等于batchcount字段的值的8倍。

2 slab体系中如何分配、释放页框

当slab 分配器创建新的slab 时，它得依靠页框管理器来获得一组连续的空闲页框。为了达到此目的，它调用kmem_getpages()函数得到对应连续页框头儿的线性地址，在80x86系统上该函数本质上等价于如下代码片段：
void * kmem_getpages(kmem_cache_t *cachep, int flags)
{
struct page *page;
int i;

flags |= cachep->gfpflags;
page = alloc_pages(flags, cachep->gfporder);
if (!page)
return NULL;
i = (1 << cachep->gfporder);

while (i--)
SetPageSlab(page++);
return page_address(page);
}

内存分配请求的大小由高速缓存描述符的gfporder字段指定，该字段将高速缓存中slab的大小编码（注意不可能从ZONE_HIGHMEM 内存管理区分配页框，因为kmem_getpages()函数返回由page_address()函数产生的线性地址；正如在前面博文的“高端内存页框的内核映射”一节解释的那样，该函数为未映射的高端内存页框返回NULL。）。

在相反的操作中，通过调用kmem_freepages()函数可以释放分配给slab 的页框（参见本章后面“从高速缓存中释放slab”一节）：
void kmem_freepages(kmem_cache_t *cachep, void *addr)
函数的具体代码省略，这个函数从线性地址addr开始释放页框，这些页框曾分配给由cachep标识的高速缓存中的slab。

3 给高速缓存分配、释放slab

一个新创建的高速缓存没有包含任何slab，因此也没有空闲的对象。只有当以下两个条件都为真时，才给高速缓存分配slab：
• 已发出一个分配新对象的请求。
• 高速缓存不包含任何空闲对象。

当这些情况发生时，slab 分配器通过调用cache_grow()函数给高速缓存分配一个新的slab：
static int cache_grow (kmem_cache_t * cachep, int flags, int nodeid)

而这个函数调用kmem_getpages()从分区页框分配器获得一组页框来存放一个单独的slab，然后又调用alloc_slabmgmt()获得一个新的slab描述符。如果高速缓存描述符的CFLGS_OFF_SLAB标志置位，则从高速缓存描述符的slabp_cache字段指向的普通高速缓存中分配这个新的slab 描述符；否则，从slab 的第一个页框中分配这个slab 描述符。

给定一个页框，内核必须确定它是否被slab 分配器使用，如果是，就迅速得到相应高速缓存和slab描述符的地址。因此，cache_grow()扫描分配给新slab的页框的所有页描述符，并将高速缓存描述符和slab描述符的地址分别赋给页描述符中lru字段的next和prev子字段。这项工作不会出错，因为只有当页框空闲时伙伴系统的函数才会使用lru字段，而只要涉及伙伴系统，slab 分配器函数所处理的页框就不空闲并将PG_slab标志置位。相反的问题——在高速缓存中给定一个slab，用哪些页框来实现它？这个问题可以通过使用slab 描述符的s_mem字段和高速缓存描述符的gfporder 字段（slab 的大小）来回答。

接着，cache_grow()调用cache_init_objs()，它将构造方法（如果定义了的话）在新slab 上添加对象。

最后，cache_grow()调用list_add_tail()来将新得到的slab 描述符*slabp，添加到高速缓存描述符*cachep的全空slab 链表的末端，并更新高速缓存中的空闲对象计数器：
list_add_tail(&slabp->list, &cachep->lists->slabs_free);
cachep->lists->free_objects += cachep->num;

下面再来谈谈逆向操作，在两种条件下才能撤销slab：
• slab 高速缓存中有太多的空闲对象。
• 被周期性调用的定时器函数确定是否有完全未使用的slab 能被释放。

在两种情况下，调用slab_destroy()函数撤销一个slab，并释放相应的页框到分区页框分配器：

这个函数检查高速缓存是否为它的对象提供了析构方法（dtor 字段不为NULL），如果是，就使用析构方法释放slab 中的所有对象。objp 局部变量记录当前已检查的对象。接下来，又调用kmem_freepages()，该函数把slab 使用的所有连续页框返回给伙伴系统。最后，如果slab 描述符存放在slab 的外面，那么，就从slab 描述符的高速缓存释放这个slab 描述符。

4 高速缓存内存布局

每个对象都有类型为kmem_bufctl_t的一个描述符，不过这个对象描述符只不过是一个无符号整数（16位），只有在对象空闲时才有意义。对象描述符存放在一个数组中，位于相应的slab 描述符之后，不明白的请仔细琢磨琢磨数据结构图。

数组中的第一个对象描述符描述slab中的第一个对象，依次类推。它包含的是下一个空闲对象在slab中的下标，因此实现了slab内部空闲对象的一个简单链表。空闲对象链表中的最后一个元素的对象描述符用常规值BUFCTL_END（0xffff）标记。例如，某个slab中有16个对象，其中只有1、3、5号对象空闲。那么1号对象描述符的值为3，3号对象描述符的值为5，5号对象描述符的值为BUFCTL_END。

slab 分配器所管理的对象可以在内存中进行对齐，也就是说，存放它们的内存单元的起始物理地址是一个给定常量的倍数，通常是2的倍数。这个常量就叫对齐因子（alignment factor）。

slab分配器所允许的最大对齐因子是4096，即页框大小。这就意味着通过访问对象的物理地址或线性地址就可以对齐对象。在这两种情况下，只有最低的12 位才可以通过对齐来改变。

通常情况下，如果内存单元的物理地址是字大小（即计算机的内部内存总线的宽度）对齐的， 那么， 微机对内存单元的存取会非常快。因此， 缺省情况下，kmem_cache_create()函数根据BYTES_PER_WORD宏所指定的字大小来对齐对象。对于80x86 处理器，这个宏产生的值为4，因为字长是32 位。

当创建一个新的slab高速缓存时，就可以让它所包含的对象在第一级硬件高速缓存中对齐。为了做到这点，设置SLAB_HWCACHE_ALIGN高速缓存描述符标志。kmem_cache_create()函数按如下方式处理请求：
如果对象的大小大于高速缓存行（cache line）的一半，就在RAM中根据L1_CACHE_BYTES的倍数（也就是行的开始）对齐对象。
否则，对象的大小就是L1_CACHE_BYTES的因子取整。这可以保证一个小对象不会横跨两个高速缓存行。

显然，slab 分配器在这里所做的事情就是以内存空间换取访问时间，即通过人为地增加对象的大小来获得较好的高速缓存性能，由此也引起额外的内碎片。

5 slab着色

在CPU中，同一硬件高速缓存行可以映射RAM中不同的块（不一定是一页，块，作为硬件高速缓存的单位）。我们已看到，相同大小的对象存放在高速缓存内相同的偏移量处。在不同的slab 内具有相同偏移量的对象最终很可能映射在同一高速缓存行中，这个结论是根据硬件特性得出的，实在搞不懂算了，记住这个绕口的结论就OK了。高速缓存的硬件可能因此而花费内存周期在同一高速缓存行与RAM内存单元之间来来往往传送两个对象，而其他的高速缓存行并未充分使用。slab 分配器通过一种叫做slab 着色（slab coloring）的策略，尽量降低高速缓存的这种不愉快行为：把叫做颜色（color）的不同随机数分配给slab。

在讨论slab着色之前，我们再回顾一下高速缓存内对象的布局。让我们考虑某个高速缓存，它的对象在RAM中被对齐。这就意味着对象的地址肯定是某个给定正数值（比如说aln，我们设aln=0x100）的倍数。连对齐的约束也考虑在内，在slab 内放置对象就有很多种可能的方式。方式的选择取决于对下列变量所做的决定：

num：可以在slab 中存放的对象个数（其值在高速缓存描述符的num 字段中）。
osize：对象的大小，包括对齐的字节。
dsize：slap描述符的大小加上所有对象描述符的大小，就等于硬件高速缓存行大小的最小倍数。如果slab 描述符和对象描述符都存放在slap 的外部，那么这个值等于0。
free：在slab 内未用字节（没有分配给任一对象的字节）的个数。

一个slab 中的总字节长度可以表示为如下表达式：
slab 的长度 = (num × osize)+dsize +free

free 总是小于osize，因为否则的话，就有可能把另外的对象放在slab 内。不过，free 可以大于aln。

slab 分配器利用空闲未用的字节free 来对slab着色。术语“着色”只是用来再细分slab，并允许内存分配器把对象展开在不同的线性地址之中。这样的话，内核从微处理器的硬件高速缓存中可能获得最好性能。

具有不同颜色的slab 把slab 的第一个对象存放在不同的内存单元，同时满足对齐约束。可用颜色的个数是free/aln（这个值存放在高速缓存描述符的colour 字段）。因此，第一个颜色表示为0，最后一个颜色表示为(free/aln)－1。（一种特殊情况是，如果free 比aln 小，那么colour 被设为0，不过所有slab 都使用颜色0，因此颜色真正的个数为1。

如果用颜色col 对一个slab 着色，那么，第一个对象的偏移量（相对于slab 的起始地址）就等于col × aln+dsize 字节。图8-6 显示了slab 内对象的布局对slab 颜色的依赖情况。着色本质上导致把slab 中的一些空闲区域从末尾移到开始。

只有当free 足够大时，着色才起作用。显然，如果对象没有请求对齐，或者如果slab 内的未用字节数小于所请求的对齐（free ≤ aln），那么，唯一可能着色的slab 就是具有颜色0 的slab，也就是说，把这个slab 的第一个对象的偏移量赋为0。

通过把当前颜色存放在高速缓存描述符的colour_next字段，就可以在一个给定对象类型的slab 之间平等地发布各种颜色。cache_grow()函数把colour_next所表示的颜色赋给一个新的slab，并递增这个字段的值。当colour_next的值变为colour后，又从0 开始。这样，每个新创建的slab 都与前一个slab 具有不同的颜色，直到最大可用颜色。此外，cache_grow()函数从高速缓存描述符的colour_off字段获得值aln，根据slab内对象的个数计算dsize，最后把col×aln+dsize的值存放到slab描述符的colouroff字段中。

6 分配slab对象

好啦，前面把数据结构以及slab分配器的内存布局等概念理清了。最关键的是如何使用这个如此优秀的工具。我们是通过调用kmem_cache_alloc()函数获得新对象。参数cachep指向高速缓存描述符，新空闲对象必须从该高速缓存描述符获得，而参数flag表示传递给分区页框分配器函数的标志，该高速缓存的所有slab 应当是满的。

该函数本质上等价于下列代码：
void * kmem_cache_alloc(kmem_cache_t *cachep, int flags)
{
unsigned long save_flags;
void *objp;
struct array_cache *ac;

local_irq_save(save_flags);
ac = cache_p->array[smp_processor_id()];
if (ac->avail) {
ac->touched = 1;
objp = ((void **)(ac+1))[--ac->avail];
} else
objp = cache_alloc_refill(cachep, flags);
local_irq_restore(save_flags);
return objp;
}

函数首先试图从本地高速缓存获得一个空闲对象。如果有空闲对象，avail字段就包含指向最后被释放的对象的项在本地高速缓存中的下标。因为本地高速缓存数组正好存放在ac 描述符后面，所以((void**)(ac+1))[--ac->avail]获得那个空闲对象的地址并递减ac->avail 的值。当本地高速缓存中没有空闲对象时，调用cache_alloc_refill()函数重新填充本地高速缓存并获得一个空闲对象。

cache_alloc_refill()函数本质上执行如下步骤：
1. 将本地高速缓存描述符的地址存放在ac 局部变量中：
ac = cachep->array[smp_processor_id()];
2. 获得cachep->spinlock。
3. 如果slab高速缓存包含共享本地高速缓存，并且该共享本地高速缓存包含一些空闲对象，函数就通过从共享本地高速缓存中上移ac->batchcount个指针来重新填充CPU 的本地高速缓存。然后，函数跳到第6 步。
4. 函数试图填充本地高速缓存， 填充值为高速缓存的slab中包含的多达ac->batchcount 个空闲对象的指针：

a) 查看高速缓存描述符的slabs_partial和slabs_free链表，并获得slab 描述符的地址slabp，该slab描述符的相应slab或者部分被填充，或者为空。如果不存在这样的描述符，则函数转到第5 步。
b) 对于slab 中的每个空闲对象，函数增加slab 描述符的inuse字段，将对象的地址插入本地高速缓存，并更新free字段使得它存放了slab 中下一个空闲对象的下标：

slabp->inuse++;
((void**)(ac+1))[ac->avail++] =
slabp->s_mem + slabp->free * cachep->obj_size;
slabp->free = ((kmem_bufctl_t*)(slabp+1))[slabp->free];

c) 如果必要，将清空的slab 插入到适当的链表上，可以是slab_full链表，也可以是slab_partial 链表。

5. 在这一步，被加到本地高速缓存上的指针个数被存放在ac->avail字段：函数递减同样数量的kmem_list3 结构的free_objects 字段来说明这些对象不再空闲。
6. 释放cachep->spinlock。
7. 如果现在ac->avail 字段大于0（一些高速缓存再填充的情况发生了），函数将ac->touched 字段设为1，并返回最后插入到本地高速缓存的空闲对象指针：
return ((void**)(ac+1))[--ac->avail];
8. 否则，没有发生任何高速缓存再填充情况：调用cache_grow()获得一个新slab，从而获得了新的空闲对象。
9. 如果cache_grow()失败了，则函数返回NULL；否则它返回到第1 步重复该过程。

7 释放Slab对象

kmem_cache_free()函数释放一个曾经由slab分配器分配给某个内核函数的对象。它的参数为cachep和objp，前者是高速缓存描述符的地址，而后者是将被释放对象的地址：

void kmem_cache_free(kmem_cache_t *cachep, void *objp)
{
unsigned long flags;
struct array_cache *ac;

local_irq_save(flags);
ac = cachep->array[smp_processor_id()];
if (ac->avail == ac->limit)
cache_flusharray(cachep, ac);
((void**)(ac+1))[ac->avail++] = objp;
local_irq_restore(flags);
}

函数首先检查本地高速缓存是否有空间给指向一个空闲对象的额外指针。如果有，该指针就被加到本地高速缓存然后函数返回。否则，它首先调用cache_flusharray()来清空本地高速缓存，然后将指针加到本地高速缓存。

cache_flusharray()函数执行如下操作：
1. 获得cachep->spinlock自旋锁。
2. 如果slab高速缓存包含一个共享本地高速缓存，并且如果该共享本地高速缓存还没有满，函数就通过从CPU的本地高速缓存中上移ac->batchcount个指针来重新填充共享本地高速缓存。
3. 调用free_block()函数将当前包含在本地高速缓存中的ac->batchcount个对象归还给slab 分配器。对于在地址objp处的每个对象，函数执行如下步骤：

a) 增加高速缓存描述符的lists.free_objects字段。
b) 确定包含对象的slab 描述符的地址：
slabp = (struct slab *)(virt_to_page(objp)->lru.prev);
（请记住，slab 页的描述符的lru.prev 字段指向相应的slab 描述符。）
c) 从它的slab 高速缓存链表（cachep->lists.slabs_partial 或是cachep->lists.slabs_full）上删除slab 描述符。
d) 计算slab 内对象的下标：
objnr = (objp - slabp->s_mem) / cachep->objsize;
e) 将slabp->free的当前值存放在对象描述符中，并将对象的下标放入slabp->free（最后被释放的对象将再次成为首先被分配的对象）：
((kmem_bufctl_t *)(slabp+1))[objnr] = slabp->free;
slabp->free = objnr;
f) 递减slabp->inuse 字段。
g) 如果slabp->inuse等于0（也就是slab 中所有对象空闲），并且整个slab 高速缓存中空闲对象的个数(cachep->lists.free_objects)大于cachep->free_limit字段中存放的限制，那么函数将slab 的页框释放到分区页框分配器：
cachep->lists.free_objects -= cachep->num;
lab_destroy(cachep, slabp);
存放在cachep->free_limit 字段中的值通常等于cachep->num+(1+N)×cachep->batchcount，其中N 代表系统中CPU 的个数。
h) 否则，如果slab->inuse 等于0，但整个slab 高速缓存中空闲对象的个数小于cachep->free_limit，函数就将slab描述符插入到cachep->lists.slabs_free链表中。
i) 最后，如果slab->inuse大于0，slab 被部分填充，则函数将slab 描述符插入到cachep->lists.slabs_partial 链表中。

4. 释放cachep->spinlock 自旋锁。
5. 通过减去被移到共享本地高速缓存或被释放到slab分配器的对象的个数来更新本地高速缓存描述符的avail 字段。
6. 移动本地高速缓存数组起始处的那个本地高速缓存中的所有指针。这一步是必需的，因为已经把第一个对象指针从本地高速缓存上删除，因此剩下的指针必须上移。

8 通用对象

前面讲了，初始化阶段建立了一些高速缓存包含用作通用用途的类型的slab对象。如果对存储区的请求不频繁，就用一组普通高速缓存来处理，普通高速缓存中的对象具有几何分布的大小，范围为32～131072 字节。

调用kmalloc()函数就可以得到这种类型的对象，函数等价于下列代码片段：
void * kmalloc(size_t size, int flags)
{
struct cache_sizes *csizep = malloc_sizes;
kmem_cache_t * cachep;
for (; csizep->cs_size; csizep++) {
if (size > csizep->cs_size)
continue;
if (flags & _ _GFP_DMA)
cachep = csizep->cs_dmacachep;
else
cachep = csizep->cs_cachep;
return kmem_cache_alloc(cachep, flags);
}
return NULL;
}

该函数使用malloc_sizes表为所请求的大小分配最近的2 的幂次方大小的内存。然后，调用kmem_cache_alloc()分配对象，传递的参数或者为适用于ISA DMA 页框的高速缓存描述符，还是为适用于“常规”页框的高速缓存描述符，这取决于调用者是否指定了_ _GFP_DMA 标志。

调用kmalloc()所获得的对象可以通过调用kfree()来释放：

void kfree(const void *objp)
{
kmem_cache_t * c;
unsigned long flags;
if (!objp)
return;
local_irq_save(flags);
c = (kmem_cache_t *)(virt_to_page(objp)->lru.next);
kmem_cache_free(c, (void *)objp);
local_irq_restore(flags);
}

通过读取内存区所在的第一个页框描述符的lru.next 子字段，就可确定出合适的高速缓存描述符。通过调用kmem_cache_free()来释放相应的内存区。

9 内存池

内存池（memory pool）是Linux 2.6 的一个新特性，主要供一些驱动程序使用。基本上讲，一个内存池允许一个内核成分, 如块设备子系统, 仅在内存不足的紧急情况下分配一些动态内存来使用。

一个内存池常常叠加在slab 分配器之上 —— 也就是说，它被用来保存slab 对象的储备。但是一般而言，内存池能被用来分配任何一种类型的动态内存，从整个页框到使用kmalloc()分配的小内存区。因此，我们一般将内存池处理的内存单元看作“内存元素”。

内存池由mempool_t 对象描述，它的字段如下所示。
typedef struct mempool_s {
spinlock_t lock;
int min_nr; /* nr of elements at *elements */
int curr_nr; /* Current nr of elements at *elements */
void **elements;

void *pool_data;
mempool_alloc_t *alloc;
mempool_free_t *free;
wait_queue_head_t wait;
} mempool_t;

min_nr字段存放了内存池中元素的初始个数。换句话说，存放在该字段中的值代表了内存元素的个数，内存池的拥有者确信能从内存分配器得到这个数目。curr_nr字段总是低于或等于min_nr，它存放了内存池中当前包含的内存元素个数。内存元素自身被一个指针数组引用，指针数组的地址存放在elements 字段中。

alloc和free方法与基本的内存分配器进行交互，分别用于获得和释放一个内存元素。两个方法可以是拥有内存池的内核成分提供的定制函数。
当内存元素是slab对象时，alloc和free方法一般由mempool_alloc_slab()和mempool_free_slab()函数实现，它们只是分别调用kmem_cache_alloc()和kmem_cache_free()函数。在这种情况下，mempool_t对象的pool_data字段存放了slab 高速缓存描述符的地址。

mempool_create()函数创建一个新的内存池；它接收的参数为内存元素的个数min_nr、实现alloc和free方法的函数的地址和赋给pool_data 字段的任意值。该函数分别为mempool_t对象和指向内存元素的指针数组分配内存，然后反复调用alloc方法来得到min_nr个内存元素。相反地，mempool_destroy()函数释放池中所有内存元素，然后释放元素数组和mempool_t对象自己。

为了从内存池分配一个元素，内核调用mempool_alloc()函数，将mempool_t对象的地址和内存分配标志传递给它。函数本质上依据参数所指定的内存分配标志，试图通过调用alloc方法从基本内存分配器分配一个内存元素。如果分配成功，函数返回获得的内存元素而不触及内存池。否则，如果分配失败，就从内存池获得内存元素。当然，在内存不足的情况下过多的分配会用尽内存池：在这种情况下，如果_ _GFP_WAIT标志没有置位，则mempool_alloc()阻塞当前进程直到有一个内存元素被释放到内存池中。

相反地，为了释放一个元素到内存池，内核调用mempool_free()函数。如果内存池未满（curr_min小于min_nr），则函数将元素加到内存池中。否则，mempool_free()调用free方法来释放元素到基本内存分配器。