<内存池基础>Slab内存分配器(论文翻译)

笔者最近在整理一些内存管理相关的基础知识，这篇文章的影响还是蛮大的，就翻译了一下，笔者英文水准有限，如有翻译不妥的地方，还望指正。本文共计2万余字，阅读请合理安排时间。如果对您有些许帮助，请推荐给自己的朋友，感谢关注、点赞和收藏。

作者信息

Jeff Bonwick 是 SunOS 的内核黑客。 他喜欢删除大而慢的旧代码，并用小而快的新代码替换它。 他仍然无法相信他会为此获得报酬。 作者获得了特拉华大学数学学士学位（1987 年）和斯坦福大学统计学硕士学位（1990 年）。 可以通过 bonwick@eng.sun.com 以电子方式联系

简介

本文介绍了SunOS5.4内核分配器的总体框架设计。这种分配器基于一组对象缓存原语，通过在使用之间保留它们的状态来降低分配复杂对象的成本。这些相同的原语被证明对于管理无状态内存(例如数据页和临时缓冲区)同样有效，应为它们既节省空间效率又高效。分配器的对象缓存动态响应全局内存压力，并采用对象着色器方案来提高系统的整体缓存利用率和总线平衡。分配器还具有几个统计和调试功能，可以检测整个系统的各种问题。

1.介绍

对象的分配和释放是内核中最常见的操作之一。因此，一个快速的内核分配器是必不可少的。然而，在许多情况下，初始化和销毁对象的成本超过了为其分配和释放内存的成本。因此分配器的改进是有益的，通过缓存经常使用的对象可以实现更大的收益，以便于在使用之间保留它们的基本结构。

本篇论文首先讨论对象缓存，因为这需要的接口将塑造分配器的其余部分。下一节将详细描述实现。第四节描述了缓冲区地址分配对系统整体高速缓存利用率和总线平衡的影响，并展示了一个简单的着色器方案如何可以改善两者。第5节将该分配器的性能与其它几个著名的内核内存分配器进行了比较，发现它在空间和时间上普遍优越。最后，第6节描述了分配器的调试功能，它可以检测整个系统的各种问题。

2. 对象缓存

对象缓存是一种处理频繁分配和释放对象的技术。这个想法是在使用之间保留对象初始化状态的不变部分-它的构造状态，因此每次使用对象时都不必销毁和重新创建它。例如，包含互斥锁的对象只需要一次mutex_init()-首次分配对象。然后可以多次释放和重新分配对象，而不会每次都产生mutex_destroy()和mutex_init()的开销。对象的嵌入式锁、条件变量、引用计数、其他对象的列表和只读数据通常都符合构造状态。

缓存很重要，因为构造对象的成本可能比为其分配内存的成本要高的多。例如，在运行SunOS5.4开发内核的SPARCstation-2上，此处介绍的分配器将分配和释放的成本从33us减少到5.7us。如下表所示，大部分节省是由于对象缓存:(流式分配与性能耗费(usec))

缓存在多线程环境中特别有用，其中许多最频繁分配的对象包含一个或多个嵌入式锁、条件变量和其它可构造状态。

对象缓存的设计的简单伪代码思路如下:

一个对象的构造状态只初始化一次(在对象第一次被放入到缓存中时)。填充缓存后，分配和释放对象是快速而简单的操作。

2.1 一个例子

思考一下如下的数据结构:

假设foo结构没有未完成的引用(foo_refcnt==0)以及其所有挂起的bar(无论它们是什么事件)都已经完成(foo_barlist == NULL),才能被释放。那么动态分配的生命周期是如下这个样子:

这其中，在每次使用foo对象时，我们都要执行一系列的操作，这些操作过程是很昂贵的。所有的这些开销(除了上面"use foo"之外)都可以通过对象缓存来消除。

2.2 对象缓存:中央分配器

对象缓存可以在没有任何中央分配器的情况下实现--任何子系统都可以有上述算法的私有实现，但是，这种方法有几个缺点:

1.在对象缓存中，想要保留内存在对象缓存中、想要将内存归还给系统以及想要申请内存块之间进行平衡。一些内存池的设计是无法处理这种情况。因为他们对系统整体内存没有一个较为清晰的认知，同样，系统也可能并不清楚这些内存池的存在，因此无法回收这些内存。

2.由于私有缓存绕过了中央分配器，它们也绕过了分配器所拥有的标记信息以及debug能力。这使得程序更难维护和调试

3.对一个常见问题会有许多相同解决方案的实例，会增加内核代码大小和维护成本

与标准的kmem_alloc(9F)/kmem_free(9F) 接口相比，对象缓存需要分配器与客户端之间更大程度的配合。下一节将开发一个接口来支持中央分配器中构造的对象缓存。

2.3 对象缓存接口

这里介绍的接口有两个需要注意的地方

1.对象的描述(名称、大小、内存对齐方式、构造函数与析构函数)属于客户端，而不是中央分配器。例如，分配器不应该只是知道sizeof是一个有用的池大小。这样的假设是脆弱的[Grunwald93A]并且无法预测其它设备驱动程序、流模块、及文件系统。

2.内存管理的策略是属于中央分配器--而不是它的客户端。客户端指向快速分配和释放对象。他们不必担心如何有效的管理底层的内存

遵循第一条规范，对象缓存的创建必须是客户端调用的，并且必须包含完整的对象信息

创建对象缓冲，每个对象的大小都在对齐便捷上对齐。对齐将始终四舍五入到最小允许值，因此只要不需要特殊内存对齐，那么内存对齐可以为0.name用于标记缓存中对象名字，构造函数时在缓存中构造对象的函数；析构函数时在缓存中释放对象。构造函数及析构函数采用大小参数，以便他们可以支持类似缓存的系列，例如流式传输信息。kmem_cache_create返回一个不透明的对象缓存的指针。

下面遵循第二条规范，客户端可以调用两个函数，一个是分配一个是释放

从对象缓存中获取一个对象，对象已经是处于其构造状态。flags是KM_SLEEP及KM_BOSLEEP，表示如果当前没有可用的内存是不是等待。

将对象放回对象缓存中，对象还是处于其构造状态。

最后，如果不需要对象缓存了，那么就可以调用该函数进行销毁

销毁缓存，将内存归还给系统，确保所有的分配的对象都是在对象缓存中。

这些接口允许我们构建一个非常适合其客户需求的灵活分配器。 从这个意义上说，它是一个“自定义”分配器。 但是，它不必像大多数自定义分配器那样使用其客户端的编译时知识来构建 [Bozman84A, Grunwald93A, Margolin71]，也不必像在自适应拟合方法中那样不断猜测 [Bozman84B, Leverett82, Oldehoeft85 ]。 相反，对象缓存接口允许客户端动态指定他们需要的分配服务。

2.4一个案例

这个案例展示了在2.1节中介绍的“foo”对象使用对象缓存。构造函数与析构函数如下:

在对象缓存中创建foo对象如下:

分配、使用和释放foo对象

这样foo对象分配的更快，因为分配器通常只会从缓存中获取已经构建的foo。foo_constructor和foo_destructor分别用来填充缓冲区以及释放缓冲区对应对象的内存

上面的例子说明了对象缓存的一个好处：它通过少执行构造函数与析构函数来减少系统的性能消耗。

3. Slab分配器实现

本节详细描述了 SunOS 5.4 内核内存分配器或“slab allo-cator”的实现。 （这个名字来源于分配器的主要数据结构之一，slab。这个名字一直存在于 Sun 中，因为它比“object”或“cache”更有区别。slab 将在第 3.2 节中讨论 .)

其中对象、缓冲区及块在本文会交替使用。这取决于我们目前是在介绍那一部分的内存相关的知识。

3.1. 缓存

每一个缓存在设计之时，分为前端与后端，尽量的将前后端进行解耦：

前端是分配器的接口层，它将对象移入与移出缓存，在需要更多的对象时，将调用后端申请内存出来。

后端通过缓存管理实际的内存的流动。内存流入由(kmem_cache_grow())从VM系统获取内存，从中生成对象并将这些对象放到缓存中。当 VM 系统想要收回一些内存时（例如，在分页开始时），会调用 outflux (kmem_cache_reap())。请注意，所有后端活动仅由内存压力触发。 当缓存需要更多对象时，内存会流入，而当系统的其余部分需要更多页面时，内存就会流出； 没有任何限制或者标记。 滞后控制由工作集算法提供，如第 3.4 节所述。

Slab分配器不是一个单一的实体，是一个独立缓存的松散组合。缓存没有共享的状态，因此Slab分配器可以对每一个缓存进行锁定，而不用使用全局锁来保护整个缓存区域(内核堆)。每个缓存锁定通过允许同时访问任意数量的不同缓存来提高拓展性。

每个缓存都维护自身的信息：总分配、分配多少及空闲缓冲区数量等。每个缓存的这些信息提供了对整个系统行为的监察。它们指示系统的那部分消耗内存最多，并可以检测识别内存泄漏。它们还可指明各种子系统中的活动水准，因此Slab分配器可以分配一个较为精准的内存值(例如，数据流信息是数据流的直接描述信息)。

Slab分配器在使用上类似于“CustoMalloc”[Grunwald93A]、''QuickFit'' [Weinstock88] 和 ''Zone'' [VanSciver88] 分配器，所有这些分配器都维护不同的最常请求的空闲列表缓冲区大小。Grunwald和Weinstock的论文都证明了定制的隔离存储分配器的可行性，并且通常在空间和时间上都是最优的。Slab分配器属于这一类，但它的有点是它的定制是在运行时客户端驱动的，而不是在编译时就确定的(区域分配器也是如此)。

标准的非缓存分配例程kmem_alloc(9F) 和kmem_free(9F) 在内部使用对象缓存。 在启动时，系统会以大约 10-20% 的增量创建一组大约 30 个缓存，大小从 8 字节到 9K 不等。 kmem_alloc() 只是从最近大小的缓存中执行 kmem_cache_alloc()。 大于 9K 的分配（很少见）由后端直接处理。

3.2. Slabs

Slab是 Slab分配器中的主要的单位。例如，当分配器需要增加缓存时，它会立即获取整个Slab对象，类似的，Slab分配器通过放弃一个完整的Slab来回收未使用的内存(收缩内存)。

一个Slab由一个或多个连续内存页面组成，这些页面被分割成相等大小的块，引用计数指示标记这些块中有多少已被分配。使用这种简捷的数据结构来管理内存有如下几个好处:

(1) 回收未使用的内存是简捷的。 当slab引用计数变为零时，关联的页面可以返回给VM系统。 因此，一个简单的引用计数取代了大多数其他分配器 [Knuth68, Korn85, Standish80] 中的复杂树、位图和合并算法。

(2) 分配和释放内存是快速、恒定时间的操作。 我们所要做的就是将对象移入或移出空闲列表并更新引用计数。

(3) 不太可能出现严重的内存碎片（freelist 上未使用的缓冲区）。 随着时间的推移，许多分配器会积累一些小的、不可用的缓冲区。 当分配器拆分现有的空闲缓冲区以满足较小的请求时，就会发生这种情况。 例如，正确的 32 字节和 40 字节分配顺序可能会导致大量空闲的 8 字节缓冲区积累——即使从未请求过 8 字节缓冲区 [Standish80]。 隔离存储分配器不会有这种情况，因为填充其 8 字节空闲列表的唯一方法是实际分配和释放 8 字节缓冲区。 任何 32 字节和 40 字节分配序列——无论多么复杂——只能导致 32 字节和 40 字节空闲列表的填充。 由于先前的分配可以很好地预测未来的分配[Weinstock88]，因此这些缓冲区很可能会再次使用。

slab 减少外部碎片化的另一个原因是，slab 中的所有对象都属于同一类型，因此它们具有相同的生命周期。 由于单个长期分配[Barrett93，Hanson90]，整个页面的生命周期都将变长。

[Note] 支持 kmem_alloc() 的通用缓存是一个明显的例外，但它们在 SunOS 5.4 中只占相对较小的一部分—所有主要的内存使用现在都使用 kmem_cache_alloc()。

(4)内部碎片(每个缓冲区浪费的空间)是最小的。每个缓冲区的大小都完全正确(即缓存的对象大小)，因此唯一浪费的空间是slab末尾未使用的部分。例如，假设有4096个字节的页，那么400个字节的对象缓存中的每个slab将包含10个缓冲区，剩下96个字节。我们可以将其视为相当于每400字节的缓冲区中浪费9.6字节的空间，或2.4%的内部碎片。

一般来说，如果一个slab包含n个缓冲区，那么内部分片最多为1/n;因此，分配器实际上可以通过控制Slab的尺寸来控制内部碎片的数量。然而，较大的slab更可能导致外部碎片，因为能够回收slab的可能性随着每个slab的缓冲区数量的增加而降低。SunOS 5.4实现将内部碎片化限制在12.5%(1/8)，因为这被发现是内部和外部碎片化之间权衡的经验最佳点。

3.2.1. Slab Layout — Logical

每个slab的内容由一个kmem_slab数据结构管理，该结构维护slab在缓存中的链接、它的引用计数和它的空闲缓冲区列表。 反过来，slab 中的每个缓冲区都由一个 kmem_bufctl 结构管理，该结构保存 freelist 链接、缓冲区地址和指向控制Slab的反向指针。 如图所示，slab 看起来像这样（未显示 bufctl-to-slab 反向指针）：

3.2.2. Slab布局针对小对象

对于小于1/8页的对象，slab是通过分配一个页面，将slab数据放在末尾，并将其余的划分为大小相等的缓冲区来构建的:

每个缓冲区在空闲列表中用作自己的 bufctl。 实际上只需要链接，因为其他所有内容都是可计算的。 这些是小缓冲区的基本优化——否则我们最终会为 bufctl 分配几乎与缓冲区本身一样多的内存。

freelist 链接位于缓冲区的末尾，而不是开头，以便于调试。 这是由观察驱动得到的经验，即数据结构的开头通常比结尾更活跃。 如果缓冲区在被释放后被修改，如果堆结构（freelist 链接）仍然完好无损，则更容易诊断问题。

分配器为构造对象保留一个附加字，以便链接不会覆盖任何构造状态。

3.2.2. Slab布局针对大对象

上述方案对小对象有效，但对大对象无效。 由于嵌入的Slab数据，它只能在 4K 页面上放置一个 2K 缓冲区。 此外，对于大型（多页）slab，我们失去了从缓冲区地址确定slab 数据地址的能力。 因此，对于大型对象，物理布局与逻辑布局相同。 所需的slab 和bufctl 数据结构来自它们自己的（小对象！）缓存。 每个缓存的自缩放哈希表提供缓冲区到 bufctl 的转换。

3.3. 空闲列表管理

每个缓存都维护着一个包含所有slab 的循环双向链表。 slab 列表是部分排序的，首先是空的slabs（分配的所有缓冲区），然后是部分slabs（分配了一些缓冲区，一些空闲），最后是完整的slabs（所有缓冲区空闲，refcnt == 0）。 缓存的 freelist 指针指向它的第一个非空slab。 反过来，每个slab都有自己的可用缓冲区空闲列表。 这种两级 freelist 结构简化了内存回收。 当分配器回收一个slab时，它不必从缓存的freelist中取消链接每个缓冲区——它只是取消链接slab。

3.4. 回收内存

当 kmem_cache_free() 发现slab 引用计数为零时，它不会立即回收内存。 相反，它只是将slab 移动到所有完整slab 所在的freelist 的尾部。 这确保了除非所有部分slab都已耗尽，否则不会分解完整的slab。

当系统内存不足时，它会要求分配器尽可能多地释放内存。 分配器有义务，但保留一组最近使用的 15 秒内的slab数据，以防止抖动。 测量表明，系统性能对板工作集间隔相当不敏感。 这大概是因为两个极端——零工作集（按需回收所有完整的板）和无限工作集（从不回收任何东西）——都是合理的，尽管这两个不是最优的策略。

4. 硬件缓存处理

现代硬件依赖于良好的缓存利用率，因此在设计软件时考虑缓存效果非常重要。 对于内存分配器，有两大类缓存效应需要考虑：缓冲区地址的分布和分配器本身的缓存足迹。 后一个话题受到了一些关注 [Chen93, Grunwald93B]，但缓冲区地址分配对缓存利用率和总线平衡的影响在很大程度上未被认识到。

4.1缓冲区地址的分布影响缓存利用率

中等大小缓冲区的地址分布会影响系统的整体缓存利用率。 特别是，二次幂分配器——所有缓冲区都是 2 n 字节并且是 2 n 字节对齐的——是最坏的。*例如，假设每个 inode(约等于300 字节)都被分配了一个 512 字节缓冲区，512 字节对齐，并且仅经常引用 inode 的前十几个字段（48 字节）。 然后大部分与 inode 相关的内存流量将位于 0 到 47 模 512 之间的地址。因此，靠近 512 字节边界的高速缓存行将被大量加载，而其余的则处于闲置状态。 实际上，只有 9% (48/512) 的缓存可供 inode 使用。 完全关联的缓存不会遇到这个问题，但是当前的硬件趋势是更简单而不是更复杂的缓存。

[Note] 这种分配器很常见，因为它们易于实现。 例如，4.4BSD 和 SVr4 都采用二次方方法 [McKusick88, Lee89]。

当然，inode没有什么特别之处。内核包含许多其他中等大小的数据结构(例如100-500字节)，它们具有相同的基本特性:它们有很多，它们只包含一些经常使用的字段，这些字段被分组在结构的开头或附近。数据结构演进方式的这种构件以前没有被认为是分配器设计中的一个重要因素。

4.2. 缓冲区地址分配对总线平衡的影响

在跨多条主总线交错内存的机器上，上述效果也会对总线利用率产生重大影响。 例如，SPARCcenter 2000 在两条主总线 [Cekleov92] 上采用 256 字节交错。 继续上面的例子，我们看到任何 2 的幂分配器将每个 inode 的前半部分（热部分）映射到总线 0，将后半部分映射到总线 1。因此几乎所有与 inode 相关的缓存未命中都由总线提供服务 0. 这种情况会因未命中率过高而加剧，因为所有的 inode 都在争夺一小部分缓存。

这些影响可能是戏剧性的。 在一个在 SunOS 5.4 开发内核下运行 LADDIS 的 SPARCcenter 2000 上，用slab分配器替换旧的分配器（二的幂的伙伴系统 [Lee89]）将总线不平衡从 43% 减少到仅 17%。 此外，主缓存未命中率下降了 13%。

4.3 Slab地址着色

Slab分配器包含一个简单的着色方案，可以在整个缓存中均匀分配缓冲区，从而实现出色的缓存利用率和总线平衡。 这个概念很简单：每次创建一个新的slab时，缓冲区地址从slab基数（总是页面对齐）的偏移量（颜色）略有不同。 例如，对于具有 8 字节对齐的 200 字节对象的缓存，第一个板的缓冲区将位于相对于Slabj基础的地址 0、200、400...。 下一个平板的缓冲区将位于偏移量 8、208、408，... 等等。 最大的Slab偏移量由Slab中未使用的空间量决定。 在这个例子中，假设 4K 页面，我们可以在 4096 字节的Slab中容纳 20 200 字节的缓冲区。 缓冲区占用 4000 字节，kmem_slab 数据占用 32 字节，剩余 64 字节可用于着色。 因此最大slab颜色为64，slab颜色序列为0,8,16,24,32,40,48,56,64,0,8,...

这种着色方案的一个特别好的特性是中等大小的二次幂缓冲区接收最大量的着色，因为它们是最差的。 例如，虽然 128 字节完美地进入 4096，但它几乎接近 4096 - 32，这是实际可用的（因为嵌入的Slab数据）。

4.4. 竞争管理

分配器的竞争管理策略决定了它的动态缓存足迹。 这些策略分为三大类：顺序拟合方法、伙伴方法和隔离存储方法 [Standish80]。

顺序拟合分配器通常必须搜索多个节点以找到合适的缓冲区。 从本质上讲，此类方法注定要占用大量缓存：它们必须检查大量通常彼此相距不远的节点。 这不仅会导致缓存未命中，还会导致 TLB 未命中。 伙伴系统分配器 [Knuth68, Lee89] 的合并阶段具有相似的属性。

隔离存储分配器，例如slab 分配器，为不同的缓冲区大小维护单独的空闲列表。 这些分配器通常具有良好的缓存局部性，因为分配缓冲区非常简单。 分配器所要做的就是确定正确的空闲列表（通过计算、表查找或将其作为参数提供）并从中获取缓冲区。 释放缓冲区同样简单。 只有少数几个要加载的指针，因此缓存占用空间很小。

slab 分配器还有一个额外的优势，即对于中小型缓冲区，大多数相关信息——slab 数据、bufctl 和缓冲区本身——都驻留在一个页面上。 因此，单个 TLB 条目涵盖了大部分操作。

5. 性能

本节将slab分配器的性能与其他三个著名的内核内存分配器进行比较：

SunOS 4.1.3，基于 [Stephenson83]，一种顺序拟合方法；

4.4BSD, based on [McKusick88], a power-of- two segregated-storage method;

SVr4，基于 [Lee89]，一种二次幂伙伴系统方法。 在所有以前的 SunOS 5.x 版本中都使用了这个分配器。

为了公平比较，这些分配器中的每一个都被移植到同一个 SunOS 5.4 基本系统中。 这确保我们只比较分配器，而不是整个操作系统。

5.1. 速度对比

在 SPARCstation-2 上，在各种分配器下分配和释放缓冲区所需的时间如下：

内存分配+耗费时间

[Note] 4.4BSD 分配器提供函数式和预处理器宏接口。 这些测量值适用于功能版本。 一般不考虑非二进制接口，因为这些接口不能在不暴露实现的情况下导出到驱动程序。 4.4BSD 分配器是在没有定义 KMEMSTATS 的情况下编译的（默认情况下它是打开的）以获得尽可能快的代码。

mutex_enter()/mutex_exit() 对花费 1.0 μsec，因此分配和释放缓冲区所需的锁定施加了 2.0 μsec 的下限。 slab 和 4.4BSD 分配器都非常接近这个限制，因为它们在常见情况下所做的工作很少。 kmem_alloc() 的 4.4BSD 实现稍微快一些，因为它要做的记帐更少（它从不回收内存）。 但是，slab 分配器的 kmem_cache_alloc() 接口甚至更快，因为它不必确定要使用哪个空闲列表（缓存）——缓存描述符作为参数传递给 kmem_cache_alloc()。 无论如何，slab 和 4.4BS Dallocator 之间的速度差异很小。 这是意料之中的，因为所有隔离存储方法在操作上都是相似的。 任何好的隔离存储实现都应该实现出色的性能。

SVr4 分配器比大多数伙伴系统慢，但仍提供合理的、可预测的速度。 SunOS 4.1.3 分配器与大多数顺序匹配方法一样，速度相对较慢且变化很大。

对象缓存的好处在上面的数字中是不可见的，因为它们只衡量分配器本身的成本。 下表显示了对象缓存对 SunOS 5.4 内核中一些最频繁分配的影响（SPARCstation-2 计时，以微秒为单位）：

对象缓存的优点

本节中提供的所有数字都单独衡量了分配器的性能。 分配器对整体系统性能的影响将在 5.3 节中讨论。

5.2. 内存利用率对比

由于不完美的匹配（内部碎片）、空闲列表上未使用的缓冲区（外部碎片）以及分配器内部数据结构的开销，分配器消耗的内存通常比其客户端实际请求的要多。 请求的内存与消耗的内存的比率是分配器的内存利用率。 互补比是内存浪费或总碎片。 良好的内存利用率是必不可少的，因为内核堆会消耗物理内存。

分配器的空间效率比它的速度更难描述，因为它依赖于工作负载。 我们能做的最好的事情是在一组固定的工作负载下测量各种分配器的内存利用率。 为此，每个分配器都受到以下工作负载序列的影响：

(1) 系统启动。 这会在重新启动后在控制台登录提示符处测量系统的内存利用率。

(2) 负载的短暂峰值，由以下简单程序生成：

这将创建 256 个进程，每个进程都创建一个套接字。 这导致对各种内核数据结构的需求暂时激增。

(3) 寻找。 这是另一个微不足道的尖峰生成器：

(4) Kenbus 。 这是一个标准的分时基准。 Kenbus 会产生大量并发活动，从而对用户和内核内存产生大量需求。

在每个步骤之后测量内存利用率。 下表总结了 16MB SPARCstation-1 的结果。 平板分配器明显优于其他分配器，最终得到最接近竞争对手的一半碎片（结果是累积的，因此“kenbus”列表示完成所有四个步骤后的碎片）：

总碎片(碎片数据)

最后一列显示了 kenbus 结果，它以每分钟执行的脚本 (s/m) 为单位测量峰值吞吐量。 在这个 16MB 系统上，Kenbus 的性能主要受内存限制，这就是为什么 SunOS 4.1.3 分配器比 4.4BSD 分配器取得了更好的结果，尽管速度明显较慢。 平板分配器以 11% 的优势提供了最佳性能，因为它既快速又节省空间。

为了掌握现实生活中的性能，作者在他的个人台式机（一台 32MB SPARCstation-2）上使用了这些分配器中的每一个一周。 这台机器主要用于阅读电子邮件、运行简单的命令和脚本，以及连接到测试机器和计算服务器。 这个明显不受控制的实验的结果是：

桌面使用一周的结果

这些数字与上述合成工作负载的结果一致。 在这两种情况下，slab 分配器都会产生大约一半的 SunOS 4.1.3 碎片，这反过来又会产生大约一半的 SVr4 和 4.4BSD 碎片。

5.3. 系统整体性能

内核内存分配器以多种方式影响整体系统性能。 在前面的部分中，我们考虑了几个单独因素的影响：对象缓存、硬件缓存和总线影响、速度和内存利用率。 我们现在转向最重要的指标：有趣工作负载的底线性能。 在 SunOS 5.4 中，基于 SVr4 的分配器被这里描述的slab 分配器所取代。 下表显示了几个关键领域的净性能改进。

使用 Slab 分配器提高系统性能

(1) DeskBench 和 kenbus 都是 16MB 内存限制的，所以这里的大部分改进是由于slab分配器的空间效率。

(2) TPC-B 工作负载导致内核内存分配非常少，因此分配器的速度在这里不是一个重要因素。 该测试在具有足够内存的大型服务器上运行，它从未分页（在任一分配器下），因此空间效率也不是一个因素。 4% 的性能提升完全归功于更好的缓存利用率（主缓存未命中减少 5%，二级缓存未命中减少 2%）。

(3) Parallel make 在一个从不分页的大型服务器上运行。 此工作负载会产生大量分配器流量，因此此处的改进归因于Slab分配器的速度、对象缓存以及系统较低的整体缓存未命中率（主缓存未命中率降低 5%，二级缓存未命中率降低 4%）。

(4) 终端服务器也运行在从不分页的大型服务器上。 该基准测试将 25% 的时间用于使用旧分配器的内核，而 20% 用于使用新分配器。 因此，5% 的底线改进是由于内核时间减少了 20%。

6. 调试功能

破坏内核堆的编程错误——例如修改释放的内存、释放缓冲区两次、释放未初始化的指针或写入缓冲区末尾之外——通常很难调试。 幸运的是，经过彻底检测的内核内存分配器可以检测到许多此类问题。

本节描述了slab分配器的调试特性。 通过在 kadb（内核调试器）下引导并设置适当的标志，可以在任何 SunOS 5.4 内核（不仅仅是特殊调试版本）中启用这些功能。* 当分配器检测到问题时，它会在系统控制台上提供详细的诊断信息。

[Note] 这些调试功能的可用性不会增加大多数分配的成本。 指示是否存在哈希表的每个缓存标志字（即缓存的对象是否大于页面的 1/8）也包含调试标志。 单个测试同时检查所有这些标志，因此常见情况（小对象，无调试）不受影响

6.1. Auditing

在Auditing模式下，分配器将其活动记录在循环事务日志中。 它将这些信息存储在 bufctl 结构的扩展版本中，其中包括线程指针、高分辨率时间戳和事务的堆栈跟踪。 当任何其他方法检测到损坏时，可以确定受影响缓冲区的先前所有者（可能的问题）。

6.2. 释放内存验证

大对象缓存使用的 buffer-to-bufctl 哈希表可用作调试功能：如果 kmem_cache_free() 中的哈希查找失败，则调用者必须尝试释放虚假地址。 分配器可以通过将“大对象”阈值更改为零来验证所有释放的地址。

6.3. 使用检测内存释放的功能

当一个对象被释放时，分配器应用它的析构函数并用模式 0xdeadbeef 填充它。 下次分配该对象时，分配器会验证它是否仍然包含 deadbeef 模式。 然后它用 0xbaddcafe 填充对象并应用其构造函数。 deadbeef 和 baddcafe 模式被选择为在调试会话中易于人类识别。 它们分别代表释放的内存和未初始化的数据。

6.4. Redzone Checking

Redzone 检查检测超过缓冲区末尾的写入。 分配器通过在每个缓冲区的末尾添加一个保护字来检查红区违规，并在释放缓冲区时验证它是否未被修改。

6.5. Synchronous Unmapping

通常，slab 工作集算法会保留完整的slab 一段时间。 在同步取消映射模式下，分配器会立即销毁完整的slab。 kmem_slab_destroy() 将底层内存返回给后端页面供应商，后者会取消映射页面。 对该slab 中任何对象的任何后续引用都将导致内核数据错误。

6.6. 页缓冲模式

在每页缓冲区模式下，每个缓冲区都被分配一个完整的页面（或多个页面），以便每个缓冲区在释放时都可以取消映射。 板分配器通过增加所有缓存的对齐到系统页面大小来实现这一点。 （此功能需要大量的物理内存）

6.7. 内存泄漏检测

审计提供的时间戳使得在用户级别实现粗略的内核内存泄漏检测器变得容易。 用户级程序所要做的就是定期扫描 arena（通过 /dev/kmem），寻找新的持久分配的外观。 例如，一个小时前分配的任何缓冲区现在仍在分配，这可能是泄漏。

6.8. 案例

这个例子说明了slab分配器对修改空闲节点的响应：

其他错误的处理方式类似。 事实证明，这些功能有助于在 SunOS 5.4 开发期间调试各种问题.

7. 未来的方向

7.1. 其它类型的内存管理

slab 分配器通过例程 kmem_getpages() 和 kmem_freepages() 从 segkmem 获取其页面； 它对底层段驱动程序、资源映射、翻译设置等没有任何假设。由于分配器尊重这个防火墙，插入备用后端页面供应商将是简单的。 “getpages”和“freepages”例程可以作为附加参数提供给 kmem_cache_create()。 这将允许我们使用单个分配器管理多种类型的内存（例如普通内核内存、设备内存、可分页内核内存、NVRAM 等）。

7.2. Per-Processor内存分配

McKenney 和 Slingwine [McKenney93] 的每处理器分配技术非常适合在Slab分配器之上。 它们定义了递减速度和局部性的四层分配层次结构：per-CPU、全局、coalesce-to page 和 coalesce-to-VM-block。 后三个分别与slab分配器的前端、后端和页面供应商层密切对应。 即使在没有锁竞争的情况下，每个处理器的小型空闲列表也可以通过消除锁定成本和减少失效流量来提高性能。

7.3. 用户级别的应用

Slab分配器也可以用作用户级内存分配器。 后端页面供应商可以是 mmap(2) 或 sbrk(2)。

8. 结束语

Slab分配器是一种简单、快速且节省空间的内核内存分配器。 它所基于的对象缓存接口降低了分配和释放复杂对象的成本，并使分配器能够按大小和生命周期分布来隔离对象。 Slabs 利用对象大小和生命周期隔离来分别减少内部和外部碎片。 Slabs 还通过使用简单的引用计数而不是合并来简化回收。 Slab分配器在其客户端和 VM 系统之间建立推/拉关系，从而无需任意限制或水印来管理回收。 分配器的着色方案在整个缓存中均匀分配缓冲区，提高系统的整体缓存利用率和总线平衡。 在几个重要领域，slab 分配器提供了明显更好的系统性能。

致谢

Neal Nuckolls 首先建议分配器应该在使用之间保留对象的状态，就像我们旧的流分配器所做的那样（它现在直接使用slab 分配器）。 Steve Kleiman 建议使用 VM 压力来规范回收。 Gordon Irlam 指出了二次方对齐对缓存利用率的负面影响； Adrian Cockcroft 假设这可能解释了我们在某些机器上看到的总线不平衡（确实如此）。

我要感谢 Cathy Bonwick、Roger Faulkner、Steve Kleiman、Tim Marsland、Rob Pike、Andy Roach、Bill Shannon 和 Jim Voll 对本文草稿版本的深思熟虑的评论。 还要感谢 David Robinson、Chaitanya Tikku 和 Jim Voll 提供了一些测量结果，并感谢 Ashok Singhal 提供了测量缓存和总线活动的工具。

最重要的是，我感谢 Cathy 在这个项目期间忍受了我。

参考文献

[Barrett93] David A. Barrett and Benjamin G.Zorn, Using Lifetime Predictors to Improve MemoryAllocation Performance. Proceedings of the 1993 SIGPLAN Conference on Programming Language Design and Implementation, pp. 187-196 (1993)

[Boehm88] H. Boehm and M. Weiser, Garbage Collection in an Uncooperative Environment. Software - Practice and Experience, v. 18, no. 9, pp 807-820 (1988)

[Bozman84A] G. Bozman, W. Buco, T. Daly, and W. Tetzlaff, Analysis of Free Storage Algorithms --Revisited. IBM Systems Journal, v. 23, no. 1, pp. 44-64 (1984)

[Bozman84B] G. Bozman, The Software Lookaside Buffer Reduces Search Overhead with Linked Lists.Communications of the ACM, v. 27, no. 3, pp. 222-227 (1984)

[Cekleov92] Michel Cekleov, Jean-Marc Frailong and Pradeep Sindhu, Sun-4D Architecture. Revision 1.4, 1992

[Chen93] J. Bradley Chen and Brian N. Bershad, The Impact of Operating System Structure on Memory System Performance. Proceedings of the Fourteenth ACM Symposium on Operating Systems Principles, v. 27, no. 5, pp. 120-133 (1993)

[Grunwald93A] Dirk Grunwald and Benjamin Zorn, CustoMalloc: Efficient Synthesized Memory Allocators. Software - Practice and Experience, v.23, no. 8, pp. 851-869 (1993)

[Grunwald93B] Dirk Grunwald, Benjamin Zorn and Robert Henderson, Improving the Cache Locality of Memory Allocation. Proceedings of the 1993 SIGPLAN Conference on Programming Language Design and Implementation, pp. 177-186 (1993)

[Hanson90] David R. Hanson, Fast Allocation andDeallocation of Memory Based on Object Lifetimes.Software - Practice and Experience, v. 20, no. 1, pp.5-12 (1990)

[Knuth68] Donald E. Knuth, The Art of Computer Programming, Vol I, Fundamental Algorithms. Addison-Wesley, Reading, MA, 1968

[Korn85] David G. Korn and Kiem-Phong Vo, In Search of a Better Malloc. Proceedings of the Summer 1985 Usenix Conference, pp. 489-506

[Lee89] T. Paul Lee and R. E. Barkley, A Watermark-based Lazy Buddy System for Kernel Memory Allocation. Proceedings of the Summer 1989 Usenix Conference, pp. 1-13

[Leverett82] B. W. Leverett and P. G. Hibbard, An Adaptive System for Dynamic Storage Allocation. Software - Practice and Experience, v. 12, no. 3, pp. 543-555 (1982)

[Margolin71] B. Margolin, R. Parmelee, and M.Schatzoff, Analysis of Free Storage Algorithms. IBM Systems Journal, v. 10, no. 4, pp. 283-304 (1971)

[McKenney93] Paul E. McKenney and Jack Slingwine, Efficient Kernel Memory Allocation on Shared-Memory Multiprocessors. Proceedings of the Winter 1993 Usenix Conference, pp. 295-305

[McKusick88] Marshall Kirk McKusick and Michael J. Karels, Design of a General Purpose Memory Allocator for the 4.3BSD UNIX Kernel. Proceedings of the Summer 1988 Usenix Conference, pp. 295-303

[Oldehoeft85] Rodney R. Oldehoeft and Stephen J.Allan, Adaptive Exact-Fit Storage Management.Communications of the ACM, v. 28, pp. 506-511(1985)

[Standish80] Thomas Standish, Data Structure Techniques. Addison-Wesley, Reading, MA, 1980

[Stephenson83] C. J. Stephenson, Fast Fits: New Methods for Dynamic Storage Allocation. Proceedings of the Ninth ACM Symposium on Operating Systems Principles, v. 17, no. 5, pp. 30-32 (1983)

[VanSciver88] James Van Sciver and Richard F. Rashid, Zone Garbage Collection. Proceedings of the Summer 1990 Usenix Mach Workshop, pp. 1-15

[Weinstock88] Charles B. Weinstock and William A. Wulf, QuickFit: An Efficient Algorithm for Heap Storage Allocation. ACM SIGPLAN Notices, v.23, no. 10, pp. 141-144 (1988)

[Zorn93] Benjamin Zorn, The Measured Cost of Conservative Garbage Collection. Software - Practice and Experience, v. 23, no. 7, pp. 733-756(1993).