Linux内核之块分配器
作者简介：
余华兵，2005年毕业于华中科技大学计算机学院，取得硕士学位。毕业后的十余年一直在网络通信行业从事软件设计和开发工作，研究方向包括IPv4协议栈、IPv6协议栈和Linux内核。
目录
3.8块分配器
3.8.1编程接口3.8.2SLAB分配器3.8.3SLUB分配器3.8.4SLOB分配器
3.8 块分配器
为了解决小块内存的分配问题，Linux 内核提供了块分配器，最早实现的块分配器是SLAB 分配器。
SLAB 分配器的作用不仅仅是分配小块内存，更重要的作用是针对经常分配和释放的对象充当缓存。SLAB 分配器的核心思想是：为每种对象类型创建一个内存缓存，每个内存缓存由多个大块（slab，原意是大块的混凝土）组成，一个大块是一个或多个连续的物理页，每个大块包含多个对象。SLAB 采用了面向对象的思想，基于对象类型管理内存，每种对象被划分为一类，例如进程描述符（task_struct）是一个类，每个进程描述符实例是一个对象。
内存缓存的组成如图3.21所示。
SLAB 分配器在某些情况下表现不太好，所以 Linux 内核提供了两个改进的块分配器。
（1）在配备了大量物理内存的大型计算机上，SLAB 分配器的管理数据结构的内存开销比较大，所以设计了 SLUB 分配器。
（2）在小内存的嵌入式设备上，SLAB 分配器的代码太多、太复杂，所以设计了一个3.8 块分配器精简的 SLOB 分配器。SLOB 是“Simple List Of Blocks”的缩写，意思是简单的块链表。
目前 SLUB 分配器已成为默认的块分配器。
3.8.1 编程接口
3 种块分配器提供了统一的编程接口。
为了方便使用，块分配器在初始化的时候创建了一些通用的内存缓存，对象的长度大多数是 
字节，从普通区域分配页的内存缓存的名称是“kmalloc-”（size 是对象的长度），从 DMA 区域分配页的内存缓存的名称是“dma-kmalloc-”，执行命令“cat /proc/slabinfo”可以看到这些通用的内存缓存。
通用的内存缓存的编程接口如下。
（1）分配内存。
（2）重新分配内存。
（3）释放内存。
使用通用的内存缓存的缺点是：块分配器需要找到一个对象的长度刚好大于或等于请求的内存长度的通用内存缓存，如果请求的内存长度和内存缓存的对象长度相差很远，浪费比较大，例如申请 36 字节，实际分配的内存长度是 64 字节，浪费了 28 字节。所以有时候使用者需要创建专用的内存缓存，编程接口如下。
（1）创建内存缓存。
（2）从指定的内存缓存分配对象。
（3）释放对象。
（4）销毁内存缓存。
3.8.2 SLAB 分配器
1．数据结构
内存缓存的数据结构如图 3.22 所示。
（1）每个内存缓存对应一个 kmem_cache 实例。
成员 gfporder 是 slab 的阶数，成员 num 是每个 slab 包含的对象数量，成员 object_size是对象原始长度，成员 size 是包括填充的对象长度。
（2）每个内存节点对应一个 kmem_cache_node 实例。
kmem_cache_node 实例包含 3 条 slab 链表：链表 slabs_partial 把部分对象空闲的 slab链接起来，链表 slabs_full 把没有空闲对象的 slab 链接起来，链表 slabs_free 把所有对象空闲的 slab 链接起来。成员 total_slabs 是 slab 数量。
每个 slab 由一个或多个连续的物理页组成，页的阶数是 kmem_cache.gfporder，如果阶数大于 0，组成一个复合页。slab 被划分为多个对象，大多数情况下 slab 长度不是对象长度的整数倍，slab 有剩余部分，可以用来给 slab 着色：“把 slab 的第一个对象从 slab 的起始位置偏移一个数值，偏移值是处理器的一级缓存行长度的整数倍，不同 slab 的偏移值不同，使不同 slab 的对象映射到处理器不同的缓存行”，所以我们看到在 slab 的前面有一个着色部分。
page 结构体的相关成员如下。
1）成员 flags 设置标志位 PG_slab，表示页属于 SLAB 分配器。
2）成员 s_mem 存放 slab 第一个对象的地址。
4）成员 lru 作为链表节点加入其中一条 slab 链表。
5）成员 slab_cache 指向 kmem_cache 实例。
6）成员 freelist 指向空闲对象链表。
这里解答思考题：kfree 函数怎么知道对象属于哪个通用的内存缓存？分为 5 步。
-
根据对象的虚拟地址得到物理地址，因为块分配器使用的虚拟地址属于直接映射的内核虚拟地址空间，虚拟地址=物理地址+常量，把虚拟地址转换成物理地址很方便。
-
根据物理地址得到物理页号。
-
根据物理页号得到 page 实例。
-
如果是复合页，需要得到首页的 page 实例。
-
根据 page 实例的成员 slab_cache 得到 kmem_cache 实例。
（3）kmem_cache 实例的成员 cpu_slab 指向 array_cache 实例，每个处理器对应一个array_cache 实例，称为数组缓存，用来缓存刚刚释放的对象，分配时首先从当前处理器的数组缓存分配，避免每次都要从 slab 分配，减少链表操作和锁操作，提高分配速度。
成员limit 是数组大小，成员avail 是数组entry 存放的对象数量，数组entry 存放对象的地址。
每个对象的内存布局如图 3.23 所示。
（1）红色区域 1：长度是 8 字节，写入一个魔幻数，如果值被修改，说明对象被改写。
（2）真实对象：长度是 kmem_cache.obj_size，偏移是 kmem_cache.obj_offset。
（3）填充：用来对齐的填充字节。
（4）红色区域 2：长度是 8 字节，写入一个魔幻数，如果值被修改，说明对象被改写。
（5）最后一个使用者：在 64 位系统上长度是 8 字节，存放最后一个调用者的地址，用来确定对象被谁改写。
对象的长度是 kmem_cache.size。红色区域 1、红色区域 2 和最后一个使用者是可选的，当想要发现内存分配和使用的错误，打开调试配置宏 CONFIG_DEBUG_SLAB 的时候，对象才包含这 3 个成员。
kmem_cache.obj_size 是调用者指定的对象长度，kmem_cache.size 是对象实际占用的内存长度，通常比前者大，原因是为了提高访问对象的速度，需要把对象的地址和长度都对齐到某个值，对齐值的计算步骤如下。
（1）如果创建内存缓存时指定了标志位 SLAB_HWCACHE_ALIGN，要求和处理器的一级缓存行的长度对齐，计算对齐值的方法如下。
-
如果对象的长度大于一级缓存行的长度的一半，对齐值取一级缓存行的长度。
-
如果对象的长度小于或等于一级缓存行的长度的一半，对齐值取（一级缓存行的长度/
），把个对象放在一个一级缓存行里面，需要为 n 找到一个合适的值。 -
如果对齐值小于指定的对齐值，取指定的对齐值。
举例说明：假设指定的对齐值是 4 字节，一级缓存行的长度是 32 字节，对象的长度是12 字节，那么对齐值是 16 字节，对象占用的内存长度是 16 字节，把两个对象放在一个一级缓存行里面。
(2)如果对齐值小于 ARCH_SLAB_MINALIGN，那么取 ARCH_SLAB_MINALIGN。ARCH_SLAB_MINALIGN 是各种处理器架构定义的最小对齐值，默认值是 8。
（3）把对齐值向上调整为指针长度的整数倍。
2．空闲对象链表
每个 slab 需要一个空闲对象链表，从而把所有空闲对象链接起来，空闲对象链表是用数组实现的，数组的元素个数是 slab 的对象数量，数组存放空闲对象的索引。假设一个 slab
包含 4 个对象，空闲对象链表的初始状态如图 3.24 所示。
page->freelist 指向空闲对象链表，数组中第 n 个元素存放的对象索引是 n，如果打开了SLAB 空闲链表随机化的配置宏 CONFIG_SLAB_FREELIST_RANDOM，数组中第 n 个元素存放的对象索引是随机的。
page->active 为 0，有两重意思。
（1）存放空闲对象索引的第一个数组元素的索引是 0。
（2）已分配对象的数量是 0。
第一次分配对象，从 0 号数组元素取出空闲对象索引 0，page->active 增加到 1，空闲对象链表如图 3.25 所示。
当所有对象分配完毕后，page->active 增加到 4，等于 slab 的对象数量，空闲对象链表如图 3.26 所示。
当释放索引为 0 的对象以后，page->active 减 1 变成 3，3 号数组元素存放空闲对象索引 0，空闲对象链表如图 3.27 所示。
空闲对象链表的位置有 3 种选择。
（1）使用一个对象存放空闲对象链表，此时 kmem_cache.flags 设置了标志位 CFLGS_OBJFREELIST_SLAB。
（2）把空闲对象链表放在 slab 外面，此时 kmem_cache.flags 设置了标志位 CFLGS_OFF_SLAB。
（3）把空闲对象链表放在 slab 尾部。如果 kmem_cache.flags 没有设置上面两个标志位，就表示把空闲对象链表放在 slab 尾部。
如果使用一个对象存放空闲对象链表，默认使用最后一个对象。如果打开了 SLAB 空闲链表随机化的配置宏 CONFIG_SLAB_FREELIST_RANDOM，这个对象是随机选择的。
假设一个 slab 包含 4 个对象，使用 1 号对象存放空闲对象链表，初始状态如图 3.28 所示。
这种方案会不会导致可以分配的对象减少一个呢？答案是不会，存放空闲对象链表的对象可以被分配。这种方案采用了巧妙的方法。
（1）必须把存放空闲对象链表的对象索引放在空闲对象数组的最后面，保证这个对象是最后一个被分配出去的。
（2）分配最后一个空闲对象，page->active增加到 4，page->freelist 变成空指针，所有对象被分配出去，已经不需要空闲对象链表，如图 3.29 所示。
（3）在所有对象分配完毕后，假设现在释放 2 号对象，slab 使用 2 号对象存放空闲对象链表，page->freelist 指向 2 号对象，把对象索引 2 存放在空闲对象数组的最后面，如图 3.30 所示。
如果把空闲对象链表放在 slab 外面，需要为空闲对象链表创建一个内存缓存，kmem_cache.freelist_cache 指向空闲对象链表的内存缓存，如图 3.31 所示。
如果 slab 尾部的剩余部分足够大，可以把空闲对象链表放在 slab 尾部，如图 3.32所示。
创建内存缓存的时候，确定空闲对象链表的位置的方法如下。
（1）首先尝试使用一个对象存放空闲对象链表。
1）如果指定了对象的构造函数，那么这种方案不适合。
2）如果指定了标志位 SLAB_TYPESAFE_BY_RCU，表示使用 RCU 技术延迟释放 slab，那么这种方案不适合。
3）计算出 slab 长度和 slab 的对象数量，空闲对象链表的长度等于（slab 的对象数量 *对象索引长度）。如果空闲对象链表的长度大于对象长度，那么这种方案不适合。
（2）接着尝试把空闲对象链表放在 slab 外面，计算出 slab 长度和 slab 的对象数量。如果 slab 的剩余长度大于或等于空闲对象链表的长度，应该把空闲对象链表放在 slab 尾部，不应该使用这种方案。
（3）最后尝试把空闲对象链表放在 slab 尾部。
3．计算 slab 长度
函数 calculate_slab_order 负责计算 slab 长度，从 0 阶到 kmalloc()函数支持的最大阶数（KMALLOC_MAX_ORDER），尝试如下。
（1）计算对象数量和剩余长度。
（2）如果对象数量是 0，那么不合适。
（3）如果对象数量大于允许的最大 slab 对象数量，那么不合适。允许的最大 slab 对象数量是 SLAB_OBJ_MAX_NUM，等于（
× 8 − 1），freelist_idx_t 是对象索引的数据类型。
（4）对于空闲对象链表在 slab 外面的情况，如果空闲对象链表的长度大于对象长度的一半，那么不合适。
（5）如果 slab 是可回收的（设置了标志位 SLAB_RECLAIM_ACCOUNT），那么选择这个阶数。
（6）如果阶数大于或等于允许的最大 slab 阶数（slab_max_order），那么选择这个阶数。尽量选择低的阶数，因为申请高阶页块成功的概率低。
（7）如果剩余长度小于或等于 slab 长度的 1/8，那么选择这个阶数。
slab_max_order：允许的最大 slab 阶数。如果内存容量大于 32MB，那么默认值是 1，否则默认值是 0。可以通过内核参数“slab_max_order”指定。
4．着色
slab 是一个或多个连续的物理页，起始地址总是页长度的整数倍，不同 slab 中相同偏移的位置在处理器的一级缓存中的索引相同。如果 slab 的剩余部分的长度超过一级缓存行的长度，剩余部分对应的一级缓存行没有被利用；如果对象的填充字节的长度超过一级缓存行的长度，填充字节对应的一级缓存行没有被利用。这两种情况导致处理器的某些缓存行被过度使用，另一些缓存行很少使用。
在 slab 的剩余部分的长度超过一级缓存行长度的情况下，为了均匀利用处理器的所有一级缓存行，slab 着色（slab coloring）利用 slab 的剩余部分，使不同 slab 的第一个对象的偏移不同。
着色是一个比喻，和颜色无关，只是表示 slab 中的第一个对象需要移动一个偏移值，使对象放到不同的一级缓存行里。
内存缓存中着色相关的成员如下。
（1）kmem_cache.colour_off 是颜色偏移，等于处理器的一级缓存行的长度，如果小于对齐值，那么取对齐值。
（2）kmem_cache.colour 是着色范围，等于（slab 的剩余长度/颜色偏移）。
192 3.8 块分配器
（3）kmem_cache.node[n]->colour_next 是下一种颜色，初始值是 0。
在内存节点 n 上创建新的 slab，计算 slab 的颜色偏移的方法如下。
（1）把kmem_cache.node[n]->colour_next 加1，如果大于或等于着色范围，那么把值设置为0。
(2)slab 的颜色偏移 = kmem_cache.node[n]->colour_next * kmem_cache.colour_off。
slab 对应的 page 结构体的成员 s_mem 存放第一个对象的地址，等于（slab 的起始地址 +slab 的颜色偏移）。
5．每处理器数组缓存
如图 3.33 所示，内存缓存为每个处理器创建了一个数组缓存（结构体 array_cache）。释放对象时，把对象存放到当前处理器对应的数组缓存中；分配对象的时候，先从当前处理器的数组缓存分配对象，采用后进先出（Last In First Out，LIFO）的原则，这种做法可以提高性能。
（1）刚释放的对象很可能还在处理器的缓存中，可以更好地利用处理器的缓存。
（2）减少链表操作。
（3）避免处理器之间的互斥，减少自旋锁操作。
结构体 array_cache 如下。
（1）成员 entry 是存放对象地址的数组。
（2）成员 avail 是数组存放的对象的数量。
（3）成员 limit 是数组的大小，和结构体 kmem_cache 的成员 limit 的值相同，是根据对象长度猜测的一个值。
（4）成员 batchcount 是批量值，和结构体 kmem_cache 的成员 batchcount 的值相同，批量值是数组大小的一半。
分配对象的时候，先从当前处理器的数组缓存分配对象。如果数组缓存是空的，那么批量分配对象以重新填充数组缓存，批量值就是数组缓存的成员 batchcount。
释放对象的时候，如果数组缓存是满的，那么先把数组缓存中的对象批量归还给 slab，批量值就是数组缓存的成员 batchcount，然后把正在释放的对象存放到数组缓存中。
6．对 NUMA 的支持
我们看看 SLAB 分配器怎么支持 NUMA 系统。如图 3.34 所示，内存缓存针对每个内存节点创建一个 kmem_cache_node 实例。
kmem_cache_node 实例的成员 shared 指向共享数组缓存，成员 alien 指向远程节点数组缓存，每个节点一个远程节点数组缓存。这两个成员有什么用处呢？用来分阶段释放从其他节点借用的对象，先释放到远程节点数组缓存，然后转移到共享数组缓存，最后释放到远程节点的 slab。
假设处理器 0 属于内存节点 0，处理器 1 属于内存节点 1。处理器 0 申请分配对象的时候，首先从节点 0 分配对象，如果分配失败，从节点 1 借用对象。
处理器 0 释放从节点 1 借用的对象时，需要把对象放到节点 0 的 kmem_cache_node 实例中与节点 1 对应的远程节点缓存数组中，先看是不是满了，如果是满的，那么必须先清空：把对象转移到节点 1 的共享数组缓存中，如果节点 1 的共享数组缓存满了，那么把剩下的对象直接释放到 slab。
分配和释放本地内存节点的对象时，也会使用共享数组缓存。
（1）申请分配对象时，如果当前处理器的数组缓存是空的，共享数组缓存里面的对象可以用来重填。
（2）释放对象时，如果当前处理器的数组缓存是满的，并且共享数组缓存有空闲空间，那么可以转移一部分对象到共享数组缓存，不需要把对象批量归还给 slab，然后把正在释放的对象添加到当前处理器的数组缓存中。
全局变量 use_alien_caches 用来控制是否使用远程节点数组缓存分阶段释放从其他节点分配的对象，默认值是 1，可以在引导内核时使用内核参数“noaliencache”指定。
当包括填充的对象长度不超过页长度的时候，使用共享数组缓存，数组大小是
（kmem_cache.shared * kmem_cache.batchcount），kmem_cache.batchcount 是批量值，kmem_cache.shared 用来控制共享数组缓存的大小，当前代码实现指定的值是 8。
7．内存缓存合并
为了减少内存开销和增加对象的缓存热度，块分配器会合并相似的内存缓存。在创建内存缓存的时候，从已经存在的内存缓存中找到一个相似的内存缓存，和原始的创建者共享这个内存缓存。3 种块分配器都支持内存缓存合并。
假设正在创建的内存缓存是 t。
如果合并控制变量 slab_nomerge 的值是 1，那么不能合并。默认值是 0，如果想要禁止合并，可以在引导内核时使用内核参数“slab_nomerge”指定。
如果 t 指定了对象构造函数，不能合并。
如果 t 设置了阻止合并的标志位，那么不能合并。阻止合并的标志位是调试和使用 RCU技术延迟释放 slab，其代码如下：
#define SLAB_NEVER_MERGE (SLAB_RED_ZONE | SLAB_POISON | SLAB_STORE_USER|SLAB_TRACE | SLAB_TYPESAFE_BY_RCU | SLAB_NOLEAKTRACE |SLAB_FAILSLAB | SLAB_KASAN)
遍历每个内存缓存 s，判断 t 是否可以和 s 合并。
（1）如果 s 设置了阻止合并的标志位，那么 t 不能和 s 合并。
（2）如果 s 指定了对象构造函数，那么 t 不能和 s 合并。
（3）如果 t 的对象长度大于 s 的对象长度，那么 t 不能和 s 合并。
（4）如果 t 的下面 4 个标志位和 s 不相同，那么 t 不能和 s 合并。
SLAB_NOTRACK | SLAB_ACCOUNT)
（5）如果对齐值不兼容，即s 的对象长度不是t 的对齐值的整数倍，那么t 不能和s 合并。
（6）如果 s 的对象长度和 t 的对象长度的差值大于或等于指针长度，那么 t 不能和 s 合并。
（7）SLAB 分配器特有的检查项：如果 t 的对齐值不是 0，并且 t 的对齐值大于 s 的对齐值，或者 s 的对齐值不是 t 的对齐值的整数倍，那么 t 不能和 s 合并。
（8）顺利通过前面 7 项检查，说明 t 和 s 可以合并。
找到可以合并的内存缓存以后，把引用计数加 1，对象的原始长度取两者的最大值，然后把内存缓存的地址返回给调用者。
8．回收内存
对于所有对象空闲的 slab，没有立即释放，而是放在空闲 slab 链表中。只有内存节点上空闲对象的数量超过限制，才开始回收空闲 slab，直到空闲对象的数量小于或等于限制。
如图 3.35 所示，结构体 kmem_cache_node的成员slabs_free是空闲slab链表的头节点，成员 free_objects 是空闲对象的数量，成员 free_limit 是空闲对象的数量限制。
节点 n 的空闲对象的数量限制 = （1 + 节点的处理器数量）* kmem_cache.batchcount +kmem_cache.num。
SLAB 分配器定期回收对象和空闲 slab，实现方法是在每个处理器上向全局工作队列添加 1 个延迟工作项，工作项的处理函数是 cache_reap。
每个处理器每隔 2 秒针对每个内存缓存执行。
（1）回收节点 n（假设当前处理器属于节点 n）对应的远程节点数组缓存中的对象。
（2）如果过去 2 秒没有从当前处理器的数组缓存分配对象，那么回收数组缓存中的对象。
每个处理器每隔 4 秒针对每个内存缓存执行。
（1）如果过去 4 秒没有从共享数组缓存分配对象，那么回收共享数组缓存中的对象。
（2）如果过去 4 秒没有从空闲 slab 分配对象，那么回收空闲 slab。
9．调试
出现内存改写时，我们需要定位出是谁改写。SLAB 分配器提供了调试功能，我们可以打开调试配置宏 CONFIG_DEBUG_SLAB，此时对象增加 3 个字段：红色区域 1、红色区域 2 和最后一个使用者，如图 3.36 所示。
分配对象时，把对象毒化：把最后 1 字节以外的每个字节设置为 0x5a，把最后一个字节设置为 0xa5；把对象前后的红色区域设置为宏 RED_ACTIVE 表示的魔幻数；字段“最后一个使用者”保存调用函数的地址。
释放对象时，检查对象：如果对象前后的红色区域都是宏 RED_ACTIVE 表示的魔幻数，说明正常；如果对象前后的红色区域都是宏 RED_INACTIVE 表示的魔幻数，说明重复释放；其他情况，说明写越界。
释放对象时，把对象毒化：把最后 1 字节以外的每个字节设置为 0x6b，把最后 1 字节设置为 0xa5；把对象前后的红色区域都设置为 RED_INACTIVE，字段“最后一个使用者”保存调用函数的地址。
再次分配对象时，检查对象：如果对象不符合“最后 1 字节以外的每个字节是 0x6b，最后 1 字节是 0xa5”，说明对象被改写；如果对象前后的红色区域不是宏 RED_INACTIVE表示的魔幻数，说明重复释放或者写越界。
3.8.3 SLUB 分配器
SLUB 分配器继承了 SLAB 分配器的核心思想，在某些地方做了改进。
（1）SLAB 分配器的管理数据结构开销大，早期每个 slab 有一个描述符和跟在后面的空闲对象数组。SLUB 分配器把 slab 的管理信息保存在 page 结构体中，使用联合体重用 page
结构体的成员，没有使 page 结构体的大小增加。现在 SLAB 分配器反过来向 SLUB 分配器学习，抛弃了 slab 描述符，把 slab 的管理信息保存在 page 结构体中。
（2）SLAB 分配器的链表多，分为空闲 slab 链表、部分空闲 slab 链表和满 slab 链表，管理复杂。SLUB 分配器只保留部分空闲 slab 链表。
（3）SLAB 分配器对 NUMA 系统的支持复杂，每个内存节点有共享数组缓存和远程节点数组缓存，对象在这些数组缓存之间转移，实现复杂。SLUB 分配器做了简化。
（4）SLUB 分配器抛弃了效果不明显的 slab 着色。
1．数据结构
SLUB 分配器内存缓存的数据结构如图 3.37 所示。
（1）每个内存缓存对应一个 kmem_cache 实例。
成员 size 是包括元数据的对象长度，成员 object_size 是对象原始长度。
成员 oo 存放最优 slab 的阶数和对象数，低 16 位是对象数，高 16 位是 slab 的阶数，即 oo 等于（（slab 的阶数 << 16）| 对象数）。最优 slab 是剩余部分最小的 slab。
成员 min 存放最小 slab 的阶数和对象数，格式和 oo 相同。最小 slab 只需要足够存放一个对象。当设备长时间运行以后，内存碎片化，分配连续物理页很难成功，如果分配最优 slab 失败，就分配最小 slab。
（2）每个内存节点对应一个 kmem_cache_node 实例。
链表 partial 把部分空闲的 slab 链接起来，成员 nr_partial 是部分空闲 slab 的数量。
（3）每个 slab 由一个或多个连续的物理页组成，页的阶数是最优 slab 或最小 slab 的阶第 3 章 内存管理数，如果阶数大于 0，组成一个复合页。
slab 被划分为多个对象，如果 slab 长度不是对象长度的整数倍，尾部有剩余部分。尾部也可能有保留部分，kmem_cache 实例的成员 reserved 存放保留长度。
在创建内存缓存的时候，如果指定标志位 SLAB_TYPESAFE_BY_RCU，要求使用 RCU延迟释放 slab，在调用函数 call_rcu 把释放 slab 的函数加入 RCU 回调函数队列的时候，需要提供一个 rcu_head 实例，slab 提供的 rcu_head 实例的位置分两种情况。
1）如果 page 结构体的成员 lru 的长度大于或等于 rcu_head 结构体的长度，那么重用成员 lru。
2）如果 page 结构体的成员 lru 的长度小于 rcu_head 结构体的长度，那么必须在 slab尾部为 rcu_head 结构体保留空间，保留长度是 rcu_head 结构体的长度。
page 结构体的相关成员如下。
1）成员 flags 设置标志位 PG_slab，表示页属于 SLUB 分配器。
2）成员 freelist 指向第一个空闲对象。
3）成员 inuse 表示已分配对象的数量。
4）成员 objects 是对象数量。
5）成员 frozen 表示 slab 是否被冻结在每处理器 slab 缓存中。如果 slab 在每处理器 slab缓存中，它处于冻结状态；如果 slab 在内存节点的部分空闲 slab 链表中，它处于解冻状态。
6）成员 lru 作为链表节点加入部分空闲 slab 链表。
7）成员 slab_cache 指向 kmem_cache 实例。
（4）kmem_cache 实例的成员 cpu_slab 指向 kmem_cache_cpu 实例，每个处理器对应一个 kmem_cache_cpu 实例，称为每处理器 slab 缓存。
SLAB 分配器的每处理器数组缓存以对象为单位，而 SLUB 分配器的每处理器 slab 缓存以 slab 为单位。
成员 freelist 指向当前使用的 slab 的空闲对象链表，成员 page 指向当前使用的 slab 对应的 page 实例，成员 partial 指向每处理器部分空闲 slab 链表。
对象有两种内存布局，区别是空闲指针的位置不同。
第一种内存布局如图 3.38 所示，空闲指针在红色区域 2 的后面。
第二种内存布局如图 3.39 所示，空闲指针重用真实对象的第一个字。
kmem_cache.offset 是空闲指针的偏移，空闲指针的地址等于（真实对象的地址 + 空闲指针偏移）。
红色区域 1 的长度 = kmem_cache.red_left_pad = 字长对齐到指定的对齐值
红色区域 2 的长度 = 字长 −（对象长度 % 字长）
当开启 SLUB 分配器的调试配置宏 CONFIG_SLUB_DEBUG 的时候，对象才包含红色区域 1、红色区域 2、分配用户跟踪和释放用户跟踪这 4 个成员。
以下 3 种情况下选择第一种内存布局。
（1）指定构造函数。
（2）指定标志位 SLAB_TYPESAFE_BY_RCU，要求使用 RCU 延迟释放 slab。
（3）指定标志位 SLAB_POISON，要求毒化对象。
其他情况下使用第二种内存布局。
2．空闲对象链表
以对象使用第一种内存布局为例说明，一个 slab 的空闲对象链表的初始状态如图 3.40所示，page->freelist 指向第一个空闲对象中的真实对象，前一个空闲对象中的空闲指针指向后一个空闲对象中的真实对象，最后一个空闲对象中的空闲指针是空指针。如果打开了SLAB 空闲链表随机化的配置宏 CONFIG_SLAB_FREELIST_RANDOM，每个对象在空闲对象链表中的位置是随机的。
分配一个对象以后，page->freelist 指向下一个空闲对象中的真实对象，空闲对象链表如图 3.41 所示。
3．计算 slab 长度
SLUB 分配器在创建内存缓存的时候计算了两种 slab 长度：最优 slab 和最小 slab。最优 slab 是剩余部分比例最小的 slab，最小 slab 只需要足够存放一个对象。当设备长时间运行以后，内存碎片化，分配连续物理页很难成功，如果分配最优 slab 失败，就分配最小 slab。
计算最优 slab 的长度时，有 3 个重要的控制参数。
（1）slub_min_objects：slab 的最小对象数量，默认值是 0，可以在引导内核时使用内核参数“slub_min_objects”设置。
（2）slub_min_order：slab 的最小阶数，默认值是 0，可以在引导内核时使用内核参数“slub_min_order”设置。
（3）slub_max_order：slab 的最大阶数，默认值是页分配器认为昂贵的阶数 3，可以在引导内核时使用内核参数“slub_max_order”设置。
函数 calculate_order 负责计算最优 slab 的长度，其算法如下：
函数 slab_order 负责计算阶数，输入参数是（对象长度 size，最小对象数量 min_objects，最大阶数 max_order，剩余部分比例 fraction，保留长度 reserved），其算法如下：
4．每处理器 slab 缓存
SLAB分配器的每处理器缓存以对象为单位，而SLUB分配器的每处理器缓存以slab为单位。
如图 3.42 所示，内存缓存为每个处理器创建了一个 slab 缓存。
（1）使用结构体 kmem_cache_cpu 描述 slab 缓存，成员 page 指向当前使用的 slab 对应的 page 实例，成员 freelist 指向空闲对象链表，成员 partial 指向部分空闲 slab 链表。
（2）当前使用的 slab 对应的 page 实例：成员 frozen 的值为 1，表示当前 slab 被冻结在每处理器 slab 缓存中；成员 freelist 被设置为空指针。
（3）部分空闲 slab 链表：只有打开配置宏 CONFIG_SLUB_CPU_PARTIAL，才会使用部分空闲 slab 链表（如果打开了调试配置宏 CONFIG_SLUB_DEBUG，还要求没有设置 slab调试标志位），目前默认打开了这个配置宏。为了和内存节点的空闲 slab 链表区分，我们把每处理器 slab 缓存中的空闲 slab 链表称为每处理器空闲 slab 链表。
链表中每个 slab 对应的 page 实例的成员 frozen 的值为 1，表示 slab 被冻结在每处理器slab 缓存中；成员 next 指向下一个 slab 对应的 page 实例。
链表中第一个 slab 对应的 page 实例的成员 pages 存放链表中 slab 的数量，成员 pobjects存放链表中空闲对象的数量；后面的 slab 没有使用这两个成员。
kmem_cache 实例的成员 cpu_partial 决定了链表中空闲对象的最大数量，是根据对象长度估算的值。
分配对象时，首先从当前处理器的 slab 缓存分配，如果当前有一个 slab 正在使用并且有空闲对象，那么分配一个对象；如果 slab 缓存中的部分空闲 slab 链表不是空的，那么取
第一个 slab 作为当前使用的 slab；其他情况下，需要重填当前处理器的 slab 缓存。
（1）如果内存节点的部分空闲 slab 链表不是空的，那么取第一个 slab 作为当前使用的slab，并且重填 slab 缓存中的部分空闲 slab 链表，直到取出的所有 slab 的空闲对象总数超过限制 kmem_cache.cpu_partial 的一半为止。
（2）否则，创建一个新的 slab，作为当前使用的 slab。
什么情况下会把 slab 放到每处理器部分空闲 slab 链表中？
释放对象的时候，如果对象所属的 slab 以前没有空闲对象，并且没有冻结在每处理器slab 缓存中，那么把 slab 放到当前处理器的部分空闲 slab 链表中。如果发现当前处理器的部分空闲 slab 链表中空闲对象的总数超过限制 kmem_cache.cpu_partial，先把链表中的所有slab 归还到内存节点的部分空闲 slab 链表中。
这种做法的好处是：把空闲对象非常少的 slab 放在每处理器空闲 slab 链表中，优先从空闲对象非常少的 slab 分配对象，减少内存浪费。
5．对 NUMA 的支持
我们看看 SLUB 分配器怎么支持 NUMA 系统。
（1）内存缓存针对每个内存节点创建一个 kmem_cache_node 实例。
（2）分配对象时，如果当前处理器的 slab 缓存是空的，需要重填当前处理器的 slab 缓存。首先从本地内存节点的部分空闲 slab 链表中取 slab，如果本地内存节点的部分空闲 slab链表是空的，那么从其他内存节点的部分空闲 slab 链表借用 slab。
kmem_cache 实例的成员 remote_node_defrag_ratio 称为远程节点反碎片比例，用来控制从远程节点借用部分空闲 slab 和从本地节点取部分空闲 slab 的比例，值越小，从本地节点取部分空闲 slab 的倾向越大。默认值是 1000，可以通过文件“/sys/kernel/slab/<内存缓存名称>/remote_node_defrag_ratio”设置某个内存缓存的远程节点反碎片比例，用户设置的范围是[0, 100]，内存缓存保存的比例值是乘以 10 以后的值。
函数 get_any_partial 负责从其他内存节点借用部分空闲 slab，算法如下：
6．回收内存
对于所有对象空闲的 slab，如果内存节点的部分空闲 slab 的数量大于或等于最小部分空闲 slab 数量，那么直接释放，否则放在部分空闲 slab 链表的尾部。
最小部分空闲 slab 数量 kmem_cache.min_partial 的计算方法是：（log2 对象长度）/2，并且把限制在范围[5,10]。
7．调试
如果我们需要使用 SLUB 分配器的调试功能，首先需要打开调试配置宏 CONFIG_DEBUG_SLUB，然后有如下两种选择。
（1）打开配置宏 CONFIG_SLUB_DEBUG_ON，为所有内存缓存打开所有调试选项。
（2）在引导内核时使用内核参数“slub_debug”。
slub_debug=<调试选项> 为所有内存缓存打开调试选项slub_debug=<调试选项>,<内存缓存名称> 只为指定的内存缓存打开调试选项
调试选项如下所示。
1）F：在分配和释放时执行昂贵的一致性检查（对应标志位 SLAB_CONSISTENCY_CHECKS）
2）Z：红色区域（对应标志位 SLAB_RED_ZONE）
3）P：毒化对象（对应标志位 SLAB_POISON）
4）U：分配/释放用户跟踪（对应标志位 SLAB_STORE_USER）
5）T：跟踪分配和释放（对应标志位 SLAB_TRACE），只在一个内存缓存上使用。
6）A：注入分配对象失败的错误（对应标志位 SLAB_FAILSLAB，需要打开配置宏CONFIG_FAILSLAB）
7）O：为可能导致更高的最小 slab 阶数的内存缓存关闭调试。
8）-：关闭所有调试选项，在内核配置了 CONFIG_SLUB_DEBUG_ON 时有用处。
如果没有指定调试选项（即“slub_debug=”），表示打开所有调试选项。
3.8.4 SLOB 分配器
SLOB 分配器最大的特点就是简洁，代码只有 600 多行，特别适合小内存的嵌入式设备。
1．数据结构
SLOB 分配器内存缓存的数据结构如图 3.43 所示。
（1）每个内存缓存对应一个 kmem_cache 实例。
成员 object_size 是对象原始长度，成员 size 是包括填充的对象长度，align 是对齐值。
（2）所有内存缓存共享 slab，所有对象长度小于 256 字节的内存缓存共享小对象 slab链表中的 slab，所有对象长度小于 1024 字节的内存缓存共享中等对象 slab 链表中的 slab，所有对象长度小于 1 页的内存缓存共享大对象 slab 链表中的 slab。对象长度大于或等于 1页的内存缓存，直接从页分配器分配页，不需要经过 SLOB 分配器。
每个 slab 的长度是一页，page 结构体的相关成员如下。
1）成员 flags 设置标志位 PG_slab，表示页属于 SLOB 分配器；设置标志位 PG_slob_free，表示 slab 在 slab 链表中。
2）成员 freelist 指向第一个空闲对象。
3）成员 units 表示空闲单元的数量。
4）成员 lru 作为链表节点加入 slab 链表。
SLOB 分配器的分配粒度是单元，也就是说，分配长度必须是单元的整数倍，单元是数据类型 slobidx_t 的长度，通常是 2 字节。数据类型 slobidx_t 的定义如下：
mm/slob.ctypedef s16 slobidx_t;typedef s32 slobidx_t;
2．空闲对象链表
我们看看 SLOB 分配器怎么组织空闲对象。在 SLOB 分配器中，对象更准确的说法是块（block），因为多个对象长度不同的内存缓存可能从同一个 slab 分配对象，一个 slab 可能出现大小不同的块。
空闲块的内存布局分为如下两种情况。
（1）对于长度大于一个单元的块，第一个单元存放块长度，第二个单元存放下一个空闲块的偏移。
（2）对于只有一个单元的块，该单元存放下一个空闲块的偏移的相反数，也就是说，是一个负数。
长度和偏移都是单元数量，偏移的基准是页的起始地址。
已经分配出去的块：如果是使用 kmalloc()从通用内存缓存分配的块，使用块前面的 4字节存放申请的字节数，因为使用 kfree()释放时需要知道块的长度。如果是从专用内存缓存分配的块，从 kmem_cache 结构体的成员 size 可以知道块的长度。
假设页长度是 4KB，单元是 2 字节，一个 slab 的空闲对象链表的初始状态如图 3.44 所示。
slab 只有一个空闲块，第一个单元存放长度 2048，第二个单元存放下一个空闲块的偏移 2048，
slab 对应的 page 结构体的成员 freelist 指向第一个空闲块，成员 units 存放空闲单元数量 2048。
假设一个对象长度是 32 字节的内存缓存从这个 slab 分配了一个对象，空闲对象链表如图 3.45 所示，slab 的前面 32 字节被分配，空闲块从第 32 字节开始，第一个单元存放长度2032，第二个单元存放下一个空闲块的偏移 2048，slab 对应的 page 结构体的成员 freelist指向这个空闲块，成员 units 存放空闲单元数量 2032。
3．分配对象
分配对象时，根据对象长度选择不同的策略。
（1）如果对象长度小于 256 字节，那么从小对象 slab 链表中查找 slab 分配。
（2）如果对象长度小于 1024 字节，那么从中等对象 slab 链表中查找 slab 分配。
（3）如果对象长度小于 1 页，那么从大对象 slab 链表中查找 slab 分配。
（4）如果对象长度大于或等于 1 页，那么直接从页分配器分配页，不需要经过 SLOB分配器。
对于前面 3 种情况，遍历 slab 链表，对于空闲单元数量（page.units）大于或等于对象长度的 slab，遍历空闲对象链表，当找到一个合适的空闲块时，处理方法是：如果空闲块的长度等于对象长度，那么把这个空闲块从空闲对象链表中删除；如果空闲块的长度大于对象长度，那么把这个空闲块分裂为两部分，一部分分配出去，剩下部分放在空闲对象链表中。
如果分配对象以后，slab 的空闲单元数量变成零，那么从 slab 链表中删除，并且清除标志位 PG_slob_free。
为了减少平均查找时间，从某个 slab 分配对象以后，把 slab 链表的头节点移到这个 slab的前面，下一次分配对象的时候从这个 slab 开始查找。
如果遍历完 slab 链表，没有找到合适的空闲块，那么创建新的 slab。
审核编辑：汤梓红
-
内核
+关注
关注
3文章
1372浏览量
40273 -
Linux
+关注
关注
87文章
11291浏览量
209307 -
分配器
+关注
关注
0文章
193浏览量
25746
原文标题：《Linux内核深度解析》选载之块分配器
文章出处：【微信号：LinuxDev，微信公众号：Linux阅码场】欢迎添加关注！文章转载请注明出处。
发布评论请先 登录
相关推荐
音视频/信号分配器,音视频/信号分配器是什么意思
VGA分配器,VGA分配器是什么意思
分配器,什么是分配器
linux内存管理中的SLAB分配器详解
深入剖析SLUB分配器和SLAB分配器的区别
工商网监
评论