Vi Linux内存 之 Slab分配器（一）

    内核中的页分配器，申请、释放内存都是以页为单位的，而通常情况下使用的是几十个字节的小块内存，不可能都按页申请释放。为了解决这一问题，linux采用了slab机制。Slab最早用于solaris2.4中，Linux在此基础上做了改进。

       Slab引入了面向对象程序设计中“对象”的概念，将每个“结构”（struct）所占的存储空间称为“对象”（object）。将一个或多个页面组合在一起形成一个slab，slab中的内存区按对象大小进行分割，一个slab中包含多个对象，从而实现以对象为单位申请、释放内存。

       Slab的组织结构如图所示：

 

       Slab机制的顶层为一个双向链表，每个节点称为一个cache，意为对象的缓存。Cache分为两类：供slab分配器本身使用的general cache和供内核其他部分使用的specific cache。general cache包括：

1)        第一个cache节点保存的就是struct kmem_cache的对象。

2)        Kmalloc使用的对象按照大小分属不同的cache，32、64、128、……，每种大小对应两个cache节点，一个用于DMA，一个用于普通分配。通过kmalloc分配的对象叫作general purpose object。

    可见general cache是按照大小进行划分的，结构不同的对象，只要大小在同一个级别内，它们就会在同一个general cache中。

       Specific cache指系统为特定结构创建的对象，比如struct file，此类cache中的对象来源于同一个结构。

       Cache的nodelists指针指向slab三链结构struct kmem_list3，内含三条slab链表：满（full）、部分满（partial）、空（free）。满表示slab中全部是分配出去的对象。部分满表示slab中既有分配出去的对象，又有空闲的对象。空表示slab中全部是空闲的对象。

       Cache的array指针指向local cache结构struct array_cache，其entry指针指向一个数组，保存指向空闲对象的指针。对多CPU系统来说，访问slab链表时需要加锁，影响了对象分配、释放的效率，为了减少竞争资源的次数，引入了slab local cache（slab本地缓存）的概念，每个cpu拥有自己的local cache，local cache中存放的空闲对象只供本CPU使用，这与页分配器的per-cpu page cache类似。分配、释放对象时首先访问的是这个local cache，而不是slab三链，这样就减少了锁的开销。

       Slab三链还有一个shared指针，指向shared local cache，其结构与普通的local cache结构相同，它是为所有cpu共享的。如果在cpu本地local cache中分配对象失败，将从shared local cache中搬运空闲对象到local cache，shared local cache中也没有空闲对象时，再去访问slab三链。引入shared local cache的目的是：考虑下面的情景，CPU A收到大量的网络报文，分配struct sk_buff对象，报文处理完成后，由CPU B发出，释放sk_buff对象，这就造成CPU A的local cache耗尽，需要从slab三链中分配对象，而CPU B的local cache过多，需要释放对象到slab三链中。shared local cache相当于一个大缓冲池，有了它，上面这种情景就不需要访问slab三链，只需访问shared local cache即可，这要简单得多。

    要想使slab系统运作起来，除了slab中保存的对象之外，当然还需要一些管理控制对象。Slab管理对象包含：struct slab对象和一个kmem_bufctl_t型（无符号整型）数组，它们的存储位置是相连的。在后文的叙述中，将这两个统称为“slab管理对象”，而将slab中保存的对象称为“slab对象”。根据slab管理对象和slab对象的存储位置，可以将slab分为：

1)        内置式slab：on-slab, slab with Internal Descriptors，指slab管理对象和slab对象存储在一起，即都位于一个slab中。这个slab可能位于general cache，也可能位于specific cache中。

2)        外置式slab：off-slab, slab with External Descriptors。指slab管理对象和slab对象分开存储，位于不同的slab中。Slab管理对象位于general cache中，而slab对象可能位于general cache，也可能位于specific cache中。通常小于512的小对象采用内置式slab，大于等于512的大对象采用外置式slab。

    通过kmem_bufctl_t数组实现链表的功能，将slab中的对象串联起来。每个数组元素存放的是下一个空闲对象在数组中的索引。 

    最后看一下slab着色。CPU访问内存时使用哪个cache line是通过低地址的若干位确定的，比如cache line大小为32，那么是从bit5开始的若干位。因此相距很远的内存地址，如果这些位的地址相同，还是会被映射到同一个cache line。Slab cache中存放的是相同大小的对象，如果没有着色区，那么同一个cache内，不同slab中具有相同slab内部偏移的对象，其低地址的若干位是相同的，映射到同一个cache line。如图所示。

    如此一来，访问cache line冲突的对象时，就会出现cache miss，不停的在cache line和内存之间来回切换，与此同时，其他的cache line可能无所事事，严重影响了cache的效率。解决这一问题的方法是通过着色区使对象的slab内偏移各不相同，从而避免cache line冲突。如图所示：

   

 

    着色貌似很好的解决了问题，实质不然，当slab数目不多时，着色工作的很好，当slab数目很多时，着色发生了循环，仍然存在cache line冲突的问题。如图所示。第一与第四，第二与第五，第三与第六，这些slab的cache line是冲突的。

 

    可见slab算法并不完美，也过于复杂，于是追求简洁完美的Linux引入了新的对象缓冲机制slub，后面会详细介绍。

    本文主要讲解slab原理，接下来将详细走读slab代码，与之互为补充。