(转)Linux SLUB 分配器详解

原文网址：https://www.ibm.com/developerworks/cn/linux/l-cn-slub/

多年以来，Linux 内核使用一种称为 SLAB 的内核对象缓冲区分配器。但是，随着系统规模的不断增大，SLAB 逐渐暴露出自身的诸多不足。SLUB 是 Linux 内核 2.6.22 版本中引入的一种新型分配器，它具有设计简单、代码精简、额外内存占用率小、扩展性高，性能优秀、方便调试等特点。本文先介绍 SLAB 分配器的基本原理，然后分析其不足之处并详细介绍 SLUB 的设计思想，最后介绍 SLUB 接口 API 函数及对象分配/释放函数的具体实现。

内核对象缓冲区管理

Linux 内核在运行过程中，常常会需要经常使用一些内核的数据结构（对象）。例如，当进程的某个线程第一次打开一个文件的时候，内核需要为该文件分配一个称为 file 的数据结构；当该文件被最终关闭的时候，内核必须释放此文件所关联的 file 数据结构。这些小块存储空间并不只在某个内核函数的内部使用，否则就可以使用当前线程的内核栈空间。同时，这些小块存储空间又是动态变化的，不可能像物理 内存页面管理使用的 page 结构那样，有多大内存就有多少个 page 结构，形成一个静态长度的队列。而且由于内核无法预测运行中各种不同的内核对象对缓冲区的需求，因此不适合为每一种可能用到的对象建立一个“缓冲池”，因 为那样的话很可能出现有些缓冲池已经耗尽而有些缓冲池中却又大量空闲缓冲区的现象。因此，内核只能采取更全局性的方法。

我们可以看出，内核对象的管理与用户进程中的堆管理比较相似，核心问题均是：如何高效地管理内存空间，使得可以快速地进行对象的分配和回收并减少内存碎片。但是内核不能简单地采用用户进程的基于堆的内存分配算法，这是因为内核对其对象的使用具有以下特殊性：

1. 内核使用的对象种类繁多，应该采用一种统一的高效管理方法。
2. 内核对某些对象（如 task_struct）的使用是非常频繁的，所以用户进程堆管理常用的基于搜索的分配算法比如First-Fit（在堆中搜索到的第一个满足请求的内存 块）和 Best-Fit（使用堆中满足请求的最合适的内存块）并不直接适用，而应该采用某种缓冲区的机制。
3. 内核对象中相当一部分成员需要某些特殊的初始化（例如队列头部）而并非简单地清成全 0。如果能充分重用已被释放的对象使得下次分配时无需初始化，那么可以提高内核的运行效率。
4. 分配器对内核对象缓冲区的组织和管理必须充分考虑对硬件高速缓存的影响。
5. 随着共享内存的多处理器系统的普及，多处理器同时分配某种类型对象的现象时常发生，因此分配器应该尽量避免处理器间同步的开销，应采用某种 Lock-Free 的算法。

如何有效地管理缓冲区空间，长期以来都是一个热门的研究课题。90 年代初期，在 Solaris 2.4 操作系统中，采用了一种称为“slab”（原意是大块的混凝土）的缓冲区分配和管理方法，在相当程度上满足了内核的特殊需求。

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 种状态，动态地处于缓冲区相应的队列中：

1. Full 队列，此时该 slab 中没有空闲对象。
2. Partial 队列，此时该 slab 中既有已分配的对象，也有空闲对象。
3. Empty 队列，此时该 slab 中全是空闲对象。

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 中批量分配对象到本地缓存。

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 分配器的不足之处，内核开发人员 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 列出了它的字段（省略了统计和调试相关的字段）。

表 1. kmem_cache 数据结构

类型	名称	描述
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 列出它的字段（省略了统计相关的字段）。

表 2. kmem_cache_cpu 数据结构

类型	名称	描述
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 列出它的字段（省略了调试相关的字段）。

表 3. kmem_cache_node 数据结构

类型	名称	描述
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 分配器，SLUB保留了原有 SLAB 分配器所有的接口 API 函数。表 4 列出主要的 API 函数：

表 4. SLUB 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 函数。

清单 1. slab_alloc

1. 获取本处理器的 kmem_cache_cpu 数据结构。
2. 假如当前活动 slab 没有空闲对象，或本处理器所在节点与指定节点不一致，则调用 __slab_alloc 函数。
3. 获得第一个空闲对象的指针，然后更新指针使其指向下一个空闲对象。
4. 返回对象地址。

清单 2. __slab_alloc

1. 如果没有本地活动 slab，转到 (f) 步骤获取 slab 。
2. 如果本处理器所在节点与指定节点不一致，转到 (e) 步骤。
3. 检查处理器活动 slab 没有空闲对象，转到 (e) 步骤。
4. 此时活动 slab 尚有空闲对象，将 slab 的空闲对象队列指针复制到 kmem_cache_cpu 结构的 freelist 字段，把 slab 的空闲对象队列指针设置为空，从此以后只从 kmem_cache_cpu 结构的 freelist 字段获得空闲对象队列信息。
5. 取消当前活动 slab，将其加入到所在 NUMA 节点的 Partial 队列中。
6. 优先从指定 NUMA 节点上获得一个 Partial slab。
7. 加入 gfpflags 标志置有 __GFP_WAIT，开启中断，故后续创建 slab 操作可以睡眠。
8. 创建一个 slab，并初始化所有对象。
9. 如果内存不足，无法创建 slab，调用 kmalloc_large（实际调用物理页框分配器）分配对象。

清单 3. slab_free

1. 如果对象属于处理器当前活动的 slab，或处理器所在 NUMA 节点号不为 -1（调试使用的值），将对象放回空闲对象队列。
2. 否则调用 __slab_free 函数。

清单 4. __slab_free

1. 执行本函数表明对象所属 slab 并不是某个活动 slab。保存空闲对象队列的指针，将对象放回此队列，最后把已分配对象数目减一。
2. 如果已分配对象数为 0，说明 slab 处于 Empty 状态，转到 (d) 步骤。
3. 如果原空闲对象队列的指针为空，说明 slab 原来的状态为 Full，那么现在的状态应该是 Partial，将该 slab 加到所在节点的 Partial 队列中。
4. 如果 slab 状态转为 Empty，且先前位于节点的 Partial 队列中，则将其剔出并释放所占内存空间。

总结

SLUB 是 Linux Kernel 2.6.22 版本引入的一种新的内核对象缓冲区分配器，它具有设计简单、代码精简、额外内存占用率小、扩展性高，性能优秀、方便调试等特点。测试表明，SLUB 相对 SLAB 的性能提升大约在 5-10%，可以预见在不久的将来，SLUB 分配器一定能彻底取代 SLAB。