📚 课程目录第3章 slab分配器数据结构

3. slab分配器数据结构：kmem_cache结构体、slab结构体、对象描述符与空闲链表

slab分配器的核心在于其精巧的数据结构设计。理解 kmem_cache、slab 以及对象描述符与空闲链表之间的关系，是掌握slab分配器运作机制的基石。本节将逐一剖析这些关键数据结构，并通过SVG图直观展示它们的组织与协作方式。

3.1 kmem_cache结构体：缓存描述符

kmem_cache 是slab分配器中最上层的管理结构，每个 kmem_cache 实例负责管理一种特定大小的内存对象。它包含了创建、销毁、分配和回收对象所需的所有元数据。

  核心作用： 一个 kmem_cache 相当于一个“对象工厂”，它维护着多个slab，并负责从这些slab中高效地分配和回收固定大小的对象。

以下是 kmem_cache 结构体中的关键字段及其功能：

字段名	类型	功能描述
`name`	`const char *`	缓存名称，用于/proc/slabinfo等调试接口标识。
`object_size`	`unsigned int`	缓存管理的每个对象的大小（字节）。
`align`	`unsigned int`	对象对齐要求，通常为硬件缓存行大小或指针大小。
`flags`	`unsigned long`	控制缓存行为的标志位，如 `SLAB_HWCACHE_ALIGN`、`SLAB_PANIC`。
`num`	`unsigned int`	每个slab中可容纳的对象数量。
`gfporder`	`unsigned int`	每个slab占用的连续物理页框阶数（2^gfporder页）。
`ctor`	`void (ctor)(void )`	对象构造函数指针，在对象首次分配时调用以初始化。
`slabs_full`	`struct list_head`	完全分配（无空闲对象）的slab链表。
`slabs_partial`	`struct list_head`	部分分配（有部分空闲对象）的slab链表。
`slabs_free`	`struct list_head`	完全空闲（所有对象均空闲）的slab链表。
`cpu_cache`	`struct array_cache *`	指向Per-CPU对象缓存数组的指针，用于无锁快速分配。

设计意图： 三个slab链表（full、partial、free）是slab分配器实现高效内存回收的关键。分配时优先从 slabs_partial 中查找，避免扫描完全空闲的slab；回收时，若slab变为完全空闲，则将其移至 slabs_free 链表，便于后续销毁或合并。

3.2 slab结构体：物理页框的管理单元

slab 结构体是连接 kmem_cache 与物理内存页框的桥梁。它描述了一段连续的物理内存（由一个或多个页框组成），并管理着其中存放的对象。

slab结构体通常被放置在所管理的物理页框的起始位置（或通过特定偏移计算得出），以减少内存碎片。其关键字段如下：

list：链表节点，用于将slab链接到所属 kmem_cache 的 slabs_full、slabs_partial 或 slabs_free 链表中。
colouroff：着色偏移量，用于将不同slab的起始对象错开缓存行，减少CPU缓存行颠簸。
s_mem：指向slab中第一个对象（或对象区起始地址）的指针。
inuse：当前slab中已分配出去的对象数量。
free：指向空闲对象链表中第一个空闲对象的索引或指针。

注意： 在较新内核版本中，slab描述符的管理方式有所演进。部分实现将slab描述符从页框内部移出，使用单独的slab描述符缓存，以减少对页框空间的占用。但上述核心字段语义保持不变。

3.3 对象描述符与空闲链表

在slab内部，空闲对象通过一个隐式的单向链表进行管理。这个链表不占用额外的内存空间，而是利用对象自身的内存区域来存储指向下一个空闲对象的指针。这种设计被称为“嵌入式空闲链表”（Embedded Freelist）。

对象描述符并非一个独立的数据结构，而是指代slab中每个对象的管理元数据。在大多数实现中，空闲链表的指针就存储在对象自身的起始位置。当一个对象被分配出去后，其起始位置存储的是用户数据；当对象空闲时，其起始位置存储的是指向下一个空闲对象的指针。

/* 嵌入式空闲链表的工作原理示意 */
/* 假设对象大小为 64 字节，空闲链表指针存储在对象前 8 字节 */

/* 初始状态：所有对象空闲，形成链表 */
/* 对象0 (空闲): [指针 -> 对象1] [填充...] */
/* 对象1 (空闲): [指针 -> 对象2] [填充...] */
/* 对象2 (空闲): [指针 -> NULL]  [填充...] */

/* 分配一个对象：从链表头（对象0）取出 */
/* 返回对象0的地址，链表头更新为对象1 */
/* 对象0 (已分配): [用户数据...] */

/* 回收对象0：将其插入链表头 */
/* 对象0 (空闲): [指针 -> 对象1] [填充...] */
/* 链表头更新为对象0 */

这种设计的优势在于：

零额外开销：空闲链表指针复用对象空间，无需为链表节点分配额外内存。
分配/回收O(1)：分配只需从链表头取出一个对象，回收只需将对象插入链表头，操作均为常数时间。
良好的缓存局部性：最近回收的对象更可能被再次分配，增加了CPU缓存命中的概率。

3.4 数据结构关系总览

下面的SVG图展示了 kmem_cache、slab 以及对象空闲链表之间的整体关系。

3.5 数据结构协作流程

当一个分配请求到达 kmem_cache 时，数据结构的协作流程如下：

检查Per-CPU缓存：首先尝试从 cpu_cache (array_cache) 中无锁分配。如果命中，直接返回对象，流程结束。
扫描slab链表：如果Per-CPU缓存为空，则遍历 slabs_partial 链表，查找有空闲对象的slab。
检查slabs_free链表：如果 slabs_partial 为空，则从 slabs_free 链表中取出一个完全空闲的slab。
分配新slab：如果所有链表都为空，则调用页框分配器（如buddy system）分配 2^gfporder 个连续页框，初始化一个新的slab，并将其加入 slabs_partial 链表。
从slab中分配对象：从选中的slab中，根据 free 指针取出空闲链表头的对象，更新 inuse 计数和 free 指针。
更新slab状态：如果分配后slab变满，将其从 slabs_partial 链表移动到 slabs_full 链表。

  性能关键点： 整个分配路径在热路径上（Per-CPU缓存命中）是O(1)且无锁的。即使在slab链表层面，由于链表操作和对象分配都是常数时间，整体分配效率依然非常高。这种分层设计是slab分配器能够成为通用对象缓存首选方案的重要原因。