slub源码分析

    从linux-2.6.23开内，SLUB取代了SLAB作为默认的内存分配机制，那么,SLUB究竟有哪些有点呢？

一 SLAB被SLUB替代的原因

    SLAB 分配器多年以来一直位于 Linux 内核的内存管理部分的核心地带，内核黑客们一般不愿意主动去更改它的代码，因为它实在是非常复杂，而且在大多数情况下，它的工作完成的相当不错。但是，随着大规模多处理器系统和 NUMA系统的广泛应用，SLAB 分配器逐渐暴露出自身的严重不足：

1. 较多复杂的队列管理。在 SLAB 分配器中存在众多的队列，例如针对处理器的本地对象缓存队列，slab 中空闲对象队列，每个 slab 处于一个特定状态的队列中，甚至缓冲区控制结构也处于一个队列之中。有效地管理这些不同的队列是一件费力且复杂的工作。
2. slab 管理数据和队列的存储开销比较大。每个 slab 需要一个 struct slab 数据结构和一个管理所有空闲对象的 kmem_bufctl_t（4 字节的无符号整数）的数组。当对象体积较少时，kmem_bufctl_t 数组将造成较大的开销（比如对象大小为32字节时，将浪费 1/8 的空间）。为了使得对象在硬件高速缓存中对齐和使用着色策略，还必须浪费额外的内存。同时，缓冲区针对节点和处理器的队列也会浪费不少内存。测试表明在一个 1000 节点/处理器的大规模 NUMA 系统中，数 GB 内存被用来维护队列和对象的引用。
3. 缓冲区内存回收比较复杂。
4. 对 NUMA 的支持非常复杂。SLAB 对 NUMA 的支持基于物理页框分配器，无法细粒度地使用对象，因此不能保证处理器级缓存的对象来自同一节点。
5. 冗余的 Partial 队列。SLAB 分配器针对每个节点都有一个 Partial 队列，随着时间流逝，将有大量的 Partial slab 产生，不利于内存的合理使用。
6. 性能调优比较困难。针对每个 slab 可以调整的参数比较复杂，而且分配处理器本地缓存时，不得不使用自旋锁。
7. 调试功能比较难于使用

    总结起来，SLAB太过复杂，光是用在这套机制的管理上开销就很大(时间和空间)，导致性能较差，而且，代码很难维护。

二 SLUB涉及的主要数据结构

1 kmem_cache: slab的描述结构，即每一个slab对应一个kmem_cache数据结构来描述

2 page：每一个物理页框(page frame)对应的描述结构，一般称作页

3 object: 某一类特定的对象，比如进程描述符task_struct, 文件指针FILE等等

4 kmem_cache_cpu:每一个cpu对应的一个结构，起始他也是一个slab，可以理解为每

  cpu的slab，主要是为了smp时多个核可以并行访问自己的slab。

5 kmem_cache_node: 每个内存节点(node)的slab描述，在 SLUB 中，没有单独的 Empty slab 队列。每个 NUMA 节点使用 kmem_cache_node 结构维护一个处于 Partial 状态的 slab 队列。(这个理解有点模糊)

三 各结构之间的关系

1 每个page至少包含两个object，否则内核将会按页分配内存。

2 一个slab至少占用一个page，否则，将会出现同一页中至少有两种不同类型的object。

3 每一个slab还指向一个kmem_cache_node和一个kmem_cache_cpu结构(UP情况下)

4 内核在启动初始化的过程中，默认初始化11个slab,即kmem_caches[12]数组。

四 SLUB初始化

在start_kernel函数中调用下面函数对11个slab进行初始化，这里只是初始化数据结构，并没有真正的申请物理页框。

void __init kmem_cache_init(void)
{
 int i;
 int caches = 0;

 init_alloc_cpu();

 /* Able to allocate the per node structures */
 slab_state = PARTIAL;

 /* Caches that are not of the two-to-the-power-of size */
 if (KMALLOC_MIN_SIZE <= 64) {
  create_kmalloc_cache(&kmalloc_caches[1],
    "kmalloc-96", 96, GFP_KERNEL);
  caches++;
 }
 if (KMALLOC_MIN_SIZE <= 128) {
  create_kmalloc_cache(&kmalloc_caches[2],
    "kmalloc-192", 192, GFP_KERNEL);
  caches++;
 }

 for (i = KMALLOC_SHIFT_LOW; i < PAGE_SHIFT; i++) {
  create_kmalloc_cache(&kmalloc_caches[i],
   "kmalloc", 1 << i, GFP_KERNEL);
  caches++;
 }

... ... ... ...

}

五 SLUB的内存分配(UP情况下)

 先大体讲一下整个分配的过程：

1 根据申请的内存大小，假设为size字节，如果size > PAGE_SIZE/2, 就直接分配一页，否则，到kmem_caches[12]中寻找最合适的slab。

2 因为在SLUB的初始化的时候，并没有真正的分配页框，所以在第一次申请内存的时候才去做这个操作。首先，检查每cpu的slab的freelist，即kmem_cache_cpu.freelist，因为是第一次肯定是空的

3 再去检查每个node的partial链表，即kmem_cache_node.partial,此时肯定也是空的。

4 从buddy系统中分配2^order个页框，order是在kmem_cache中指定的，并把这些页框初始化成大小为size的object，并初始化响应的数据结构。

5 将分配到的2^order个页框第一个页框对应的page->freelist=object，即指向第一个object对象。并将page结构中的inuse赋值为这个页框包含的object的数量

6 分配出第一个object,然后将page->freelist=NULL, 将每cpu的slab的freelist赋值为第二个object的地址。(kmem_cache_cpu.freelist = object[offset])

以后再有这种大小的object的请求，就会直接从每cpu的slab的freelist上分配。

六 SLUB的内存释放

假设释放地址为x的某个object。

1 通过虚拟地址或先行地址x,可以得到该object属于哪个page，进而通过page->slab可以得到该object属于哪个slab。

2 如果当前slab的page指针，即kmem_cache_cpu.page等于要释放的object属于的page,那么，就直接把object释放到kmem_cache_cpu.freelist中。

3 否则，page->inuse--,然后把object属于的page添加到kmem_cache_node的partial中。

以上部分就是我对SLUB算法的简单的理解。

    红字部分是我不理解的，只是看代码是这样做的，哪位大哥能给解释下，同样的是，为什么每次分配的时候回去查看这个partial链表，我就是有点想不通，partial到底扮演了什么角色。