【转】 linux slub分配器浅析
2011-07-18 09:45 转载自 分享 最终编辑 kouu
在《linux内存管理浅析》中提到内核管理自己使用的内存时，使用了SLAB对象池。SLAB确实是比较复杂，所以一直以来都没有深入看一看。
不过现在，linux内核中，SLAB已经被它的简化版--SLUB所代替。最近抽时间看了一下SLUB的代码，略记一些自己的理解。
尽管SLUB是在内核里面实现的，用户态的对象池其实也可以借鉴这样的做法。
SLUB的总体思想还是跟SLAB类似，对象池里面的内存都是以“大块”为单位来进行分配与回收的。然后每个“大块”又按对象的大小被分割成“小块”，使用者对于对象的分配与回收都是以“小块”为单位来进行的。
SLUB的结构如下图：
另外，kmem_cache还有以下一些参数（后面会解释到）： int size; /* 每个对象占用的空间 */ int objsize; /* 对象的大小 */
int offset; /* 对象所占用的空间中，存放next指针的偏移 */ int refcount; /* 引用计数 */
int inuse; /* 对象除next指针外所占用的大小 */ int align; /* 对齐字节数 */ void (*ctor)(void *); /* 构造函数 */
unsigned long min_partial; /* kmem_cache_node中保存的最小page数 */ struct kmem_cache_order_objects oo; /* 首选的page分配策略（分配多少个连续页面，能划分成多少个对象） */
struct kmem_cache_order_objects min; /* 次选的page分配策略 */
（另外还有一些成员，或支持了一些选项、或支持了DEBUG、或是为周期性的内存回收服务。这里就不列举了。）
大体结构
kmem_cache是对象池管理器，每一个kmem_cache管理一种类型的对象。所有的管理器通过双向链表由表头slab_caches串连起来。
这一点跟之前的SLAB是一样的。
kmem_cache的内存管理工作是通过成员kmem_cache_node来完成的。在NUMA环境下（非均质存储结构），一个kmem_cache维护了一组kmem_cache_node，分别对应每一个内存节点。kmem_cache_node只负责管理对应内存节点下的内存。（如果不是 NUMA环境，那么kmem_cache_node只有一个。）
而实际的内存还是靠page结构来管理的，kmem_cache_node通过partial指针串连起一组page（nr_partial代表链表长度），它们就代表了对象池里面的内存。page结构不仅代表了内存，结构里面还有一些union变量用来记录其对应内存的对象分配情况（仅当page被加入到SLUB分配器后有效，其他情况下这些变量有另外的解释）。
原先的SLAB则要复杂一些，SLAB里面的page仅仅是管理内存，不维护“对象”的概念。而是由额外的SLAB控制结构（slab）来管理对象，并通过slab结构的一些指针数组来划定对象的边界。
前面说过，对象池里面的内存是以“大块”为单位来进行分配与回收的，page就是这样的大块。page内部被划分成若干个小块，每一块用于容纳一个对象。这些对象是以链表的形式来存储的，page->freelist就是链表头，只有未被分配的对象才会放在链表中。对象的next指针存放在其偏移量为kmem_cache->offset的位置。（见上面的图）
而在SLAB中，“大块”则是提供控制信息的slab结构。page结构只表示内存，它仅是slab所引用的资源。
每一个page并不只代表一个页面，而是2^order个连续的页面，这里的order值是由kmem_cache里面的oo或min来确定的。分配页面时，首先尝试使用oo里面的order值，分配较合适大小的连续页面（这个值是在kmem_cache创建的时候计算出来的，使用这个值时需要分配一定的连续页面，以使得内存分割成“小块”后剩余的边角废料较少）。如果分配不成功（运行时间长了，内存碎片多了，分配大量连续页面就不容易了），则使用min里面的order值，分配满足对象大小的最少量的连续页面（这个值也是创建kmem_cache时计算出来的）。
kmem_cache_node通过partial指针串连的一组page，这些page必须是没被占满的（一个page被划分成page->objects个对象大小的空间，这些空间中有page->inuse个已
经被使用。如果page->objects==page->inuse，则page为full）。如果一个page为full，则它会被从链表中移除。而如果page是free的（page->inuse==0），一般情况下它也会被释放，除非这里的nr_partial（链表长度）小于kmem_cache里面的min_partial。（既然是池，就应该有一定的存量，min_partial就代表最低存量。这个值也是在创建kmem_cache时计算出来的，对象的size较大时，会得到较大的min_partial值。因为较大的size值在分配page时会需要更多连续页面，而分配连续页面不如单个的页面容易，所以应该多缓存一些。）
而原先的SLAB则有三个链表，分别维护“full”、“partial”、“free”的slab。“free”和“partial”在SLUB里面合而为一，成了前面的partial链表。而“full”的page就不维护了。其实也不需要维护，因为page已经full了，不能再满足对象的分配，只能响应对象的回收。而在对象回收时，通过对象的地址就能得到对应的page结构（page结构的地址是与内存地址相对应的，见《linux内存管理浅析》）。维护full的page可以便于查看分配器的状态，所以在DEBUG模式下，kmem_cache_node里面还是会提供一个full链表。
分配与释放
对象的分配与释放并不是直接在kmem_cache_node上面操作的，而是在kmem_cache_cpu上。一个kmem_cache维护了一组kmem_cache_cpu，分别对应系统中的每一个CPU。kmem_cache_cpu相当于为每一个CPU提供了一个分配缓存，以避免CPU总是去kmem_cache_node上面做操作，而产生竞争。并且kmem_cache_cpu能让被它缓存的对象固定在一个CPU上，从而提高CPU的cache命中率。kmem_cache_cpu只提供了一个page的缓存。
原先的SLAB是为每个CPU提供了一个array_cache结构来缓存对象。对象在array_cache结构中的组织形式跟它在slab中的组织形式是不一样的，这也就增加了复杂性。而SLUB则都是通过page结构来组织对象的，组织形式都一样。
进行对象分配的时候，首先尝试在kmem_cache_cpu上去分配。如果分配不成功，再去kmem_cache_node上move一个page到kmem_cache_cpu上面来。分配不成功的原因有两个：kmem_cache_cpu上的page已经full了、或者现在需要分配的node跟kmem_cache_cpu上缓存page对应的node不相同。对于page已full的情况，page被从kmem_cache_cpu上移除掉（或者DEBUG模式下，被移动到对应kmem_cache_node的full链表上）；而如果是node不匹配的情况，则kmem_cache_cpu上缓存page会先被move回到其对应kmem_cache_node的partial链表上（再进一步，如果page是free的，且partial链表的长度已经不小于min_partial了，则page被释放）。
反过来，释放对象的时候，通过对象的地址能找到它所对应的page的地址，将对象放归该page即可。但是里面也有一些特殊逻辑，如果page正被kmem_cache_cpu缓存，就没有什么需要额外处理的了；否则，在将对象放归page时，需要对page加锁（因为其他CPU也可能正在该page上分配或释放对象）。另外，如果对象在回收之前该page是f
ull的，则对象释放后该page就成partial的了，它还应该被添加到对应的kmem_cache_node的partial链表中。而如果对象回收之后该page成了free的，则它应该被释放掉。
对象的释放还有一个细节，既然对象会放回到对应的page上去，那如果这个page正在被其他的CPU cache呢（其他CPU的kmem_cache_cpu正指使用这个page）？其实没关系，kmem_cache_cpu和page各自有一个freelist指针，当page被一个CPU cache时，page的freelist上的所有对象全部移动到kmem_cache_cpu的freelist上面去（其实就是一个指针赋值），page的freelist变成NULL。而释放的时候是释放到page的freelist上去。两个freelist互不影响。但是这个地方貌似有个问题，如果一个被cache的page的freelist由于object的释放而变成非NULL，那么这个page就可能再被cache到其他CPU的kmem_cache_cpu上面去，于是多个kmem_cache_cpu可能cache同一个page。这将导致一个CPU内部的缓存可能cache到其他CPU上的object（因为CPU缓存跟object并不是对齐的），从而一个CPU上的object写操作可能引起另一个CPU的缓存失效。
在kmem_cache被创建的时候，SLUB会根据各种各样的信息，计算出对象池的合理布局（见上面的图）。objsize是对象本身的大小；这个大小经过对齐处理以后就成了inuse；紧贴inuse的后面可能会存放对象的next指针（由offset来标记），从而将对象实际占用的大小扩大到size。
其实，这里的offset并不总是指向inuse后面的位置（否则offset就可以用inuse来代替了）。offset有两种可能的取值，一是 inuse、一是0。这里的offset指定了next指针的位置，而next是为了将对象串连在空闲链表中。那么，需要用到next指针的时候，对象必定是空闲的，对象里面的空间是未被使用的。于是正好，对象里的第一个字长的空间就拿来当next指针好了，此时offset就是0。但是在一些特殊情况下，对象里面的空间不能被复用作next指针，比如对象提供了构造函数ctor，那么对象的空间是被构造过的。此时，offset就等于inuse，next指针只好存放在对象的空间之后。
vs slab
相比SLAB，SLUB还有一个比较有意思的特性。当创建新的对象池时，如果发现原先已经创建的某个kmem_cache的size刚好等于或略大于新的size，则新的kmem_cache不会被创建，而是复用这个大小差不多kmem_cache。所以kmem_cache里面还维护了一个refcount（引用计数），表示它被复用的次数。
另外，SLUB也去掉了SLAB中很有意思的一个特性，Coloring（着色）。
什么是着色呢？一个内存“大块”，在按对象大小划分成“小块”的时候，可能并不是那么刚好，还会空余一些边边角角。着色就是利用这些边边角角来做文章，使得“小块”的起始地址并不总是等于“大块”内的0地址，而是在0地址与空余大小之间浮动。这样就使得同一种类型的各个对象，其地址的低几位存在更多的变化。
为什么要这样做呢？这是考虑到了CPU的cache。在学习操作系统原理的时候我们都听说过，为提高CPU对内存的访存效率，CPU提供了cache。于是就有了从内存到cache
之间的映射。当CPU指令要求访问一个内存地址的时候，CPU会先看看这个地址是否已经被缓存了。
内存到cache的映射是怎么实现的呢？或者说CPU怎么知道某个内存地址有没有被缓存呢？
一种极端的设计是“全相连映射”，任何内存地址都可以映射到任何的cache位置上。那么CPU拿到一个地址时，它可能被缓存的cache位置就太多了，需要维护一个庞大的映射关系表，并且花费大量的查询时间，才能确定一个地址是否被缓存。这是不太可取的。
于是，cache的映射总是会有这样的限制，一个内存地址只可以被映射到某些个cache位置上。而一般情况下，内存地址的低几位又决定了内存被cache的位置（如：cache_location = address % cache_size）。
好了，回到SLAB的着色，着色可以使同一类型的对象其低几位地址相同的概率减小，从而使得这些对象在cache中映射冲突的概率降低。
这有什么用呢？其实同一种类型的很多对象被放在一起使用的情况是很多的，比如数组、链表、vector、等等情况。当我们在遍历这些对象集合的时候，如果每一个对象都能被CPU缓存住，那么这段遍历代码的处理效率势必会得到提升。这就是着色的意义所在。
SLUB把着色给去掉了，是因为对内存使用更加抠门了，尽可能的把边边角角减少到最小，也就干脆不要着色了。还有就是，既然kmem_cache可以被size差不多的多种对象所复用，复用得越多，着色也就越没意义了。
