你必须非常努力，才能看起来毫不费力！
分类： LINUX
2008-10-15 10:39:32
级别： 初级
林 昊翔 (), Linux 内核爱好者
秦 君 (), 软件工程师, IBM
2008 年 7 月 16 日
多年以来，Linux 内核使用一种称为 SLAB 的内核对象缓冲区分配器。但是，随着系统规模的不断增大，SLAB 逐渐暴露出自身的诸多不足。SLUB 是 Linux 内核 2.6.22 版本中引入的一种新型分配器，它具有设计简单、代码精简、额外内存占用率小、扩展性高，性能优秀、方便调试等特点。本文先介绍 SLAB 分配器的基本原理，然后分析其不足之处并详细介绍 SLUB 的设计思想，最后介绍 SLUB 接口 API 函数及对象分配/释放函数的具体实现。
Linux 内核在运行过程中，常常会需要经常使用一些内核的数据结构（对象）。例如，当进程的某个线程第一次打开一个文件的时候，内核需要为该文件分配一个称为 file 的数据结构；当该文件被最终关闭的时候，内核必须释放此文件所关联的 file 数据结构。这些小块存储空间并不只在某个内核函数的内部使用，否则就可以使用当前线程的内核栈空间。同时，这些小块存储空间又是动态变化的，不可能像物理内存页面管理使用的 page 结构那样，有多大内存就有多少个 page 结构，形成一个静态长度的队列。而且由于内核无法预测运行中各种不同的内核对象对缓冲区的需求，因此不适合为每一种可能用到的对象建立一个“缓冲池”，因为那样的话很可能出现有些缓冲池已经耗尽而有些缓冲池中却又大量空闲缓冲区的现象。因此，内核只能采取更全局性的方法。
我们可以看出，内核对象的管理与用户进程中的堆管理比较相似，核心问题均是：如何高效地管理内存空间，使得可以快速地进行对象的分配和回收并减少内存碎片。但是内核不能简单地采用用户进程的基于堆的内存分配算法，这是因为内核对其对象的使用具有以下特殊性：
如何有效地管理缓冲区空间，长期以来都是一个热门的研究课题。90 年代初期，在 Solaris 2.4 操作系统中，采用了一种称为“slab”（原意是大块的混凝土）的缓冲区分配和管理方法，在相当程度上满足了内核的特殊需求。
|
多年以来，Linux 内核使用一种称为 SLAB 的内核对象缓冲区分配器。SLAB 分配器源于 Solaris 2.4 的分配算法，工作于物理内存页框分配器之上，管理特定大小对象的缓存，进行快速而高效的内存分配。
SLAB 分配器为每种使用的内核对象建立单独的缓冲区。Linux 内核已经采用了伙伴系统（Buddy System）管理物理内存页框，因此 SLAB 分配器直接工作于伙伴系统之上。每种缓冲区由多个 slab 组成，每个 slab就是一组连续的物理内存页框，被划分成了固定数目的对象。根据对象大小的不同，缺省情况下一个 slab 最多可以由 1024 个物理内存页框构成。出于对齐等其它方面的要求，slab 中分配给对象的内存可能大于用户要求的对象实际大小，这会造成一定的内存浪费。
由于内核对象在使用前和释放后可能需要做某些特殊处理，缓冲区拥有自己的“构造函数（constructor）”和“析构函数（destructor）”，类似于C++ 等面向对象编程语言中的概念（不过最新版本的 SLAB 分配器取消了析构函数）。创建新 slab 时内核调用构造函数初始化每个对象，释放 slab 时则调用析构函数。这就是内核数据结构被称为对象的原因。
内核使用 kmem_cache 数据结构管理缓冲区。由于 kmem_cache 自身也是一种内核对象，所以需要一个专门的缓冲区。所有缓冲区的 kmem_cache 控制结构被组织成以 cache_chain 为队列头的一个双向循环队列，同时 cache_cache 全局变量指向kmem_cache 对象缓冲区的 kmem_cache 对象。每个 slab 都需要一个类型为 struct slab 的描述符数据结构管理其状态，同时还需要一个 kmem_bufctl_t（被定义为无符号整数）的结构数组来管理空闲对象。如果对象不超过 1/8 个物理内存页框的大小，那么这些 slab 管理结构直接存放在 slab 的内部，位于分配给 slab 的第一个物理内存页框的起始位置；否则的话，存放在 slab 外部，位于由 kmalloc 分配的通用对象缓冲区中。
slab 中的对象有 2 种状态：已分配或空闲。为了有效地管理 slab，根据已分配对象的数目，slab 可以有 3 种状态，动态地处于缓冲区相应的队列中：
NUMA（Non Uniform Memory Access） 系统中，每个节点都会拥有这 3 种 slab 队列，struct kmem_list3结构用于维护相关队列。SLAB 分配器优先从 Partial 队列里的 slab 中分配对象。当 slab 的最后一个已分配对象被释放时，该 slab 从 Partial 队列转移到 Empty 队列；当 slab 的最后一个空闲对象被分配时，该 slab 从Partial 队列转移到Full 队列里。缓冲区中空闲对象总数不足时，则分配更多的 slab；但是如果空闲对象比较富余，Empty 队列的部分 slab 将被定期回收。
为了充分利用硬件高速缓存，SLAB 分配器允许对象在一级硬件高速缓存中对齐（创建缓冲区时，设置 SLAB_HWCACHE_ALIGN 标志）；同时使用着色（color）策略，使得同一缓冲区内不同 slab 中相同编号的对象的地址相互错开，避免它们被放入同一物理高速缓存行而造成频繁换入/换出的性能损失。
为了支持多处理器同时分配对象，缓冲区为每个处理器维护一个本地缓存。处理器直接从本地缓存中分配对象，从而避免了锁的使用；当本地缓存为空时，从 slab 中批量分配对象到本地缓存。
|
SLAB 分配器多年以来一直位于 Linux 内核的内存管理部分的核心地带，内核黑客们一般不愿意主动去更改它的代码，因为它实在是非常复杂，而且在大多数情况下，它的工作完成的相当不错。但是，随着大规模多处理器系统和 NUMA系统的广泛应用，SLAB 分配器逐渐暴露出自身的严重不足：
为了解决以上 SLAB 分配器的不足之处，内核开发人员 Christoph Lameter 在 Linux 内核 2.6.22 版本中引入一种新的解决方案：SLUB 分配器。SLUB 分配器特点是简化设计理念，同时保留 SLAB 分配器的基本思想：每个缓冲区由多个小的 slab 组成，每个 slab 包含固定数目的对象。SLUB 分配器简化了kmem_cache，slab 等相关的管理数据结构，摒弃了SLAB 分配器中众多的队列概念，并针对多处理器、NUMA 系统进行优化，从而提高了性能和可扩展性并降低了内存的浪费。为了保证内核其它模块能够无缝迁移到 SLUB 分配器，SLUB 还保留了原有 SLAB 分配器所有的接口 API 函数。
本文所列的数据结构和源代码均摘自 Linux 内核 2.6.25 版本。
每个内核对象缓冲区都是由 kmem_cache 类型的数据结构来描述的，表 1 列出了它的字段（省略了统计和调试相关的字段）。
| 类型 | 名称 | 描述 |
| unsigned long | flags | 描述缓冲区属性的一组标志 |
| int | size | 分配给对象的内存大小（可能大于对象的实际大小） |
| int | objsize | 对象的实际大小 |
| int | offset | 存放空闲对象指针的位移 |
| int | order | 表示一个 slab 需要 2^order 个物理页框 |
| kmem_cache_node | local_node | 创建缓冲区的节点的 slab 信息 |
| int | objects | 一个 slab 中的对象总个数 |
| gfp_t | allocflags | 创建一个 slab 时使用的一组额外标志 |
| int | refcount | 缓冲区计数器。当用户请求创建新的缓冲区时，SLUB 分配器重用已创建的相似大小的缓冲区，从而减少缓冲区的个数。 |
| void (*)(…) | ctor | 创建 slab 时用于初始化每个对象的构造函数 |
| int | inuse | 元数据的位移 |
| int | align | 对齐 |
| const char * | name | 缓冲区名字 |
| struct list_head | list | 包含所有缓冲区描述结构的双向循环队列，队列头为 slab_caches |
| int | remote_node_defrag_ratio | 该值越小，越倾向从本节点中分配对象 |
| struct kmem_cache_node * [] | node | 为每个节点创建的 slab 信息的数据结构（创建缓冲区的节点除外，使用 local_node 字段） |
| struct kmem_cache_cpu * [] | cpu_slab | 为每个处理器创建的 slab 信息的数据结构 |
我们可以看到，SLUB 分配器的 kmem_cache 结构相对 SLAB 而言简化了不少，而且没有了队列的相关字段。值得注意的是 SLUB 分配器具有缓冲区合并的功能：当内核执行绪请求创建新的缓冲区 C2 时，SLUB 分配器会先搜索已创建的缓冲区，如果发现某缓冲区 C1 的对象大小略大于 C2，则重用 C1。测试表明，这项功能减少了大约 50% 的缓冲区数目，从而减少了 slab 碎片并提高了内存利用率。
在 SLUB 分配器中，一个 slab 就是一组连续的物理内存页框，被划分成了固定数目的对象。slab 没有额外的空闲对象队列（这与 SLAB 不同），而是重用了空闲对象自身的空间。slab 也没有额外的描述结构，因为 SLUB 分配器在代表物理页框的 page 结构中加入 freelist，inuse 和 slab 的 union 字段，分别代表第一个空闲对象的指针，已分配对象的数目和缓冲区 kmem_cache 结构的指针，所以 slab 的第一个物理页框的 page 结构就可以描述自己。
每个处理器都有一个本地的活动 slab，由 kmem_cache_cpu 结构描述。表 2 列出它的字段（省略了统计相关的字段）。
| 类型 | 名称 | 描述 |
| void ** | freelist | 空闲对象队列的指针，即第一个空闲对象的指针 |
| struct page * | page | slab 的第一个物理页框描述符 |
| int | node | 处理器所在 NUMA 节点号，值 -1 用于调试 |
| unsigned int | offset | 用于存放下一个空闲对象指针的位移，以字（word）为单位 |
| unsigned int | objsize | 对象实际大小，与 kmem_cache 结构 objsize 字段一致 |
在 SLUB 中，没有单独的 Empty slab 队列。每个 NUMA 节点使用 kmem_cache_node 结构维护一个处于 Partial 状态的 slab 队列。表 3 列出它的字段（省略了调试相关的字段）。
| 类型 | 名称 | 描述 |
| spinlock_t | list_lock | 保护 nr_partial 和 partial 字段的自旋锁 |
| unsigned long | nr_partial | 本节点 Partial slab 的数目 |
| atomic_long_t | nr_slabs | 本节点 slab 的总数 |
| struct list_head | partial | Partial slab 的双向循环队列 |
创建处理器活动 slab时，第一个空闲对象的指针被复制到 kmem_cache_cpu 结构的 freelist 字段中。虽然对象分配和释放的操作只针对处理器本地的活动 slab，但是在某些特殊的情况下会为当前处理器创建新的活动 slab 并把原先未用完的活动 slab 加到 NUMA 节点 的Partial 队列中（例如，在处理器 A 上运行的某内核执行绪申请对象，但是 A 的活动 slab 中已经没有空闲对象，因此必须创建新的 slab。但是创建 slab 的操作可能导致睡眠，所以当创建操作完成后该执行绪可能被调度到处理器 B 上，这将停止使用 B 原有的活动 slab，并将其加入 B 所在节点的 Partial 队列中）。相较 SLAB 而言，处于Partial 状态的 slab 的数目比较少，因此合理有效地利用了内存。当本地 slab 没有空闲对象时，SLUB 分配器优先从处理器所在节点的 Partial 队列中分配一个 slab 作为新的本地活动 slab，其次从其它节点中分配 slab。
内核执行绪申请对象时，直接从所在处理器的kmem_cache_cpu 结构的 freelist 字段获得第一个空闲对象的地址，然后更新 freelist 字段，使其指向下一个空闲对象。释放对象时，如果对象属于所在处理器的活动 slab 中，直接将其添加到空闲对象队列的队首，并更新 freelist 字段；否则的话，对象一定属于某 Partial slab 中。如果释放操作使得该 Partial slab 转变成 Empty 状态，则释放该 slab。可见 SLUB 分配器不需要复杂的缓冲区内存回收机制。
SLUB 的调试代码总是可用，一旦激活“slab_debug”选项，用户就可以很方便地选择单个或一组指定的缓冲区进行动态调试。
内核函数常常需要临时分配一块任意大小的物理地址连续的内存空间，如果请求不频繁的话，则没有必要创建单独的缓冲区。Linux 内核为这种请求准备了一组特定大小的通用对象缓冲区。调用 kmalloc 函数就可以得到符合请求大小的内存空间，调用 kfree 则释放该内存空间。kmalloc 工作于 SLUB 分配器之上。内核初始化时，创建一组共 13 个通用对象的缓冲区。kmalloc_caches 数组存放了这些缓冲区的 kmem_cache 数据结构。由于 kmem_cache 数据结构是通过 kmalloc 来分配的，故而只能用静态分配的 kmem_cache 结构数组来描述通用对象的缓冲区。其中 kmalloc_caches[0] 代表的缓冲区专门分配 kmem_cache_node 结构。kmalloc_caches[1] 缓冲区对象大小为64，kmalloc_caches[2] 缓冲区对象大小为192，其余第 i（3-12）号缓冲区对象大小为 2^i。如果请求分配超过物理页面大小的对象，直接调用页框分配器。为了满足老式 ISA 设备的需要，内核还使用 DMA 内存创建了 13 个通用对象的缓冲区，用 kmalloc_caches_dma 数组存放相应的 kmem_cache 结构。
|
为了保证内核其它模块能够无缝迁移到 SLUB 分配器，SLUB保留了原有 SLAB 分配器所有的接口 API 函数。表 4 列出主要的 API 函数：
| 函数 | 描述 |
| kmem_cache_create | 创建新的缓冲区。 |
| kmem_cache_destroy | 销毁缓冲区。因为存在重用缓冲区的情况，只有当 kmem_cache 结构的 refcount 字段为 0时才真正销毁。 |
| kmem_cache_alloc | 从处理器本地的活动 slab 中分配对象。 |
| kmem_cache_alloc_node | 如果指定的 NUMA 节点与本处理器所在节点不一致，则先从指定节点上获取 slab，替换处理器活动 slab，然后分配对象。 |
| kmem_cache_free | 释放对象。如果对象属于某 Partial slab 且释放操作使这个 slab转变成Empty 状态，则释放该 slab。 |
| kmem_ptr_validate | 检查给定对象的指针是否合法。 |
| kmem_cache_size | 返回对象实际大小。 |
| kmem_cache_shrink | 检查各个节点的 Partial 队列，回收实际处于 Empty 状态的 slab，并将剩余的 slab 按已分配对象的数目排序。 |
| kmalloc | 从通用缓冲区中分配一个对象。 |
| kmalloc_node | 从通用缓冲区中分配一个属于指定 NUMA 节点的对象。 |
| kfree | 释放一个通用对象。 |
| ksize | 返回分配给对象的内存大小（可能大于对象的实际大小） |
下面介绍 kmem_cache_alloc，kmem_cache_alloc_node 和 kmem_cache_free 三个函数的实现细节。kmem_cache_alloc 和 kmem_cache_alloc_node 函数都是直接调用 slab_alloc 函数，只是 kmem_cache_alloc 传入的 node 参数为 -1；kmem_cache_free 则调用 slab_free 函数。
static __always_inline void *slab_alloc(struct kmem_cache *s,
gfp_t gfpflags, int node, void *addr)
{
void **object;
struct kmem_cache_cpu *c;
unsigned long flags;
local_irq_save(flags);
c = get_cpu_slab(s, smp_processor_id()); (a)
if (unlikely(!c->freelist || !node_match(c, node)))
object = __slab_alloc(s, gfpflags, node, addr, c); (b)
else {
object = c->freelist; (c)
c->freelist = object[c->offset];
stat(c, ALLOC_FASTPATH);
}
local_irq_restore(flags);
if (unlikely((gfpflags & __GFP_ZERO) && object))
memset(object, 0, c->objsize);
return object; (d)
}
|
static void *__slab_alloc(struct kmem_cache *s,
gfp_t gfpflags, int node, void *addr, struct kmem_cache_cpu *c)
{
void **object;
struct page *new;
gfpflags &= ~__GFP_ZERO;
if (!c->page) (a)
goto new_slab;
slab_lock(c->page);
if (unlikely(!node_match(c, node))) (b)
goto another_slab;
stat(c, ALLOC_REFILL);
load_freelist:
object = c->page->freelist;
if (unlikely(!object)) (c)
goto another_slab;
if (unlikely(SlabDebug(c->page)))
goto debug;
c->freelist = object[c->offset]; (d)
c->page->inuse = s->objects;
c->page->freelist = NULL;
c->node = page_to_nid(c->page);
unlock_out:
slab_unlock(c->page);
stat(c, ALLOC_SLOWPATH);
return object;
another_slab:
deactivate_slab(s, c); (e)
new_slab:
new = get_partial(s, gfpflags, node); (f)
if (new) {
c->page = new;
stat(c, ALLOC_FROM_PARTIAL);
goto load_freelist;
}
if (gfpflags & __GFP_WAIT) (g)
local_irq_enable();
new = new_slab(s, gfpflags, node); (h)
if (gfpflags & __GFP_WAIT)
local_irq_disable();
if (new) {
c = get_cpu_slab(s, smp_processor_id());
stat(c, ALLOC_SLAB);
if (c->page)
flush_slab(s, c);
slab_lock(new);
SetSlabFrozen(new);
c->page = new;
goto load_freelist;
}
if (!(gfpflags & __GFP_NORETRY) &&
(s->flags & __PAGE_ALLOC_FALLBACK)) {
if (gfpflags & __GFP_WAIT)
local_irq_enable();
object = kmalloc_large(s->objsize, gfpflags); (i)
if (gfpflags & __GFP_WAIT)
local_irq_disable();
return object;
}
return NULL;
debug:
if (!alloc_debug_processing(s, c->page, object, addr))
goto another_slab;
c->page->inuse++;
c->page->freelist = object[c->offset];
c->node = -1;
goto unlock_out;
}
|
static __always_inline void slab_free(struct kmem_cache *s,
struct page *page, void *x, void *addr)
{
void **object = (void *)x;
struct kmem_cache_cpu *c;
unsigned long flags;
local_irq_save(flags);
c = get_cpu_slab(s, smp_processor_id());
debug_check_no_locks_freed(object, c->objsize);
if (likely(page == c->page && c->node >= 0)) { (a)
object[c->offset] = c->freelist;
c->freelist = object;
stat(c, FREE_FASTPATH);
} else
__slab_free(s, page, x, addr, c->offset); (b)
local_irq_restore(flags);
}
|
static void __slab_free(struct kmem_cache *s, struct page *page,
void *x, void *addr, unsigned int offset)
{
void *prior;
void **object = (void *)x;
struct kmem_cache_cpu *c;
c = get_cpu_slab(s, raw_smp_processor_id());
stat(c, FREE_SLOWPATH);
slab_lock(page);
if (unlikely(SlabDebug(page)))
goto debug;
checks_ok:
prior = object[offset] = page->freelist; (a)
page->freelist = object;
page->inuse--;
if (unlikely(SlabFrozen(page))) {
stat(c, FREE_FROZEN);
goto out_unlock;
}
if (unlikely(!page->inuse)) (b)
goto slab_empty;
if (unlikely(!prior)) { (c)
add_partial(get_node(s, page_to_nid(page)), page, 1);
stat(c, FREE_ADD_PARTIAL);
}
out_unlock:
slab_unlock(page);
return;
slab_empty:
if (prior) { (d)
remove_partial(s, page);
stat(c, FREE_REMOVE_PARTIAL);
}
slab_unlock(page);
stat(c, FREE_SLAB);
discard_slab(s, page);
return;
debug:
if (!free_debug_processing(s, page, x, addr))
goto out_unlock;
goto checks_ok;
}
|
|
SLUB 是 Linux Kernel 2.6.22 版本引入的一种新的内核对象缓冲区分配器，它具有设计简单、代码精简、额外内存占用率小、扩展性高，性能优秀、方便调试等特点。测试表明，SLUB 相对 SLAB 的性能提升大约在 5-10%，可以预见在不久的将来，SLUB 分配器一定能彻底取代 SLAB。
|
林昊翔，计算机科学硕士，毕业于清华大学计算机系，Linux 内核爱好者 | ||
|
秦君，现在 IBM 中国软件开发实验室 Lotus 开发中心工作，目前从事 Lotus Quickr 的开发工作。 | ||
