DLmalloc内存分配器

作者： Doug Lea [本文的德文改编和翻译存在于1996年12月的unix / mail中 。这篇文章现已过时，并未反映当前版本的malloc的详细信息。

介绍

内存分配器在基础架构软件工程中是一种有趣的案例研究。 我从1987年开始编写一个内存分配器，并一直维护着它（在许多志愿者贡献者的帮助下）。 此分配器实现了标准C的例程malloc() ， free()和realloc() ，以及一些实用的辅助例程。 分配器从未被赋予特定名称， 大多数人只称它为Doug Lea的Malloc ，或简称为dlmalloc 。

此分配器的代码已放置在公共域中（可从ftp://g.oswego.edu/pub/misc/malloc.c获得 ），并且显然被广泛使用：它成为了某些版本的Linux的malloc的默认实现；它被编译成一些常用的软件包（用于覆盖原生malloc），并且已经在各种PC环境以及嵌入式系统中使用，当然还有许多我甚至都不知道的地方。

在编写了一些几乎完全依赖于分配动态内存的C ++程序之后，我编写了第一个分配器版本。 我发现它们的运行速度要慢得多，而且内存消耗总量比我预期的要多得多。 这是由于我运行的系统上的内存分配器的特性（主要是SunO和BSD的当时版本）。 为了解决这个问题，我首先在C ++中编写了许多专用分配器，通常是通过为各种类重载operator new 。 其中一些在关于C ++分配技术的论文中有所描述，该论文已被改编成1989 C ++ Report文章一些容器类的存储分配技术 。

但是，我很快就意识到，为每一个往往是动态分配和大量使用的类构建一个自己特殊的分配器不是一个好的策略。（从1986年到1991年，我是libg ++的主要作者，GNU C ++库。）需要一个更广泛的解决方案 - 在正常的C ++和C加载下编写一个足够好的分配器，这样程序员就不会想要编写专用分配器，除非在非常特殊的条件下。

本文介绍了此分配器的一些主要设计目标，算法和实现注意事项。 可以在代码分发中找到更详细的文档。

目标

一个好的内存分配器需要平衡许多目标：

• 最大化兼容性 分配器应与其他分配器兼容; 特别是它应该遵守ANSI / POSIX惯例。

• 最大化可移植性 依赖于尽可能少的依赖于系统的功能（例如系统调用），同时仍然为仅在某些系统上出现的其他有用功能提供可选支持；符合对齐和寻址规则的所有已知系统约束。

• 最小化空间 分配器不应该浪费空间：它应该从系统中获得尽可能少的内存，并且应该以最小化碎片的方式保持内存，碎片-程序未使用的连续内存块中的“漏洞”。

• 最大限度地缩短时间 在一般情况下， malloc() ， free()和realloc例程应该尽可能快。

• 最大化可调性 用户可以静态地（通过#define等）或动态地（通过诸如mallopt控制命令）控制可选特征和行为。

• 最大化寻址 分配通常一起使用的内存块。 这有助于在程序执行期间最小化页面和缓存未命中。

• 最大化错误检测 通用分配器似乎并不能用作通用内存错误测试工具，如Purify 。 但是，分配器应该提供一些方法来检测由于覆盖内存，多个释放等而导致的损坏。

• 最小化异常 使用默认设置配置的分配器应该在高依赖于动态分配的实际负载中运行良好 – 这些程序包括窗口工具包，GUI应用程序，编译器，解释器，开发工具，网络（数据包）密集程序，图形密集型程序包， Web浏览器，字符串处理应用程序等。

Paul Wilson及其同事撰写了一篇关于分配技术的优秀调查报告，更详细地讨论了其中的一些目标。 参见1995年9月的国际内存管理研讨会上的 Paul R. Wilson，Mark S. Johnstone，Michael Neely和David Boles，“动态存储分配：调查与评论”（也可通过ftp获得 ）。 （请注意，他们描述的我的分配器版本不是最新版本。）

正如他们所讨论的那样，最大限度地通过减少浪费（通常是由于碎片）来减少空间占用必须是任何分配器的主要目标。

对于一个极端的例子， malloc()的最快版本中总是分配系统上可用的下一个顺序内存位置，而free()的相应最快版本是no-op。 但是，这样的实现几乎不可接受：它会导致程序快速耗尽内存，因为它永远不会回收未使用的空间。 在一些负载下，在实践中使用的一些分配器中看到的浪费几乎可以是极端的。 正如威尔逊还指出的那样，浪费可以通过货币方式来衡量：在全球范围内，糟糕的分配方案可能会让人们花费数十亿美元的内存芯片。

虽然时空问题占主导地位，但这种权衡和妥协几乎是无止境的。 以下是众多示例中的一小部分：

• 通过强制分配器跳过字节以便对齐块来适应最坏情况的对齐要求会增加浪费。
• 大多数动态可调性的规定（例如设置调试模式）可能因为增加间接级别和增加分支数量而严重影响时间效率。
• 旨在捕获错误的一些规定限制了适用范围。 例如，以前的版本2.6.6，无论平台如何，malloc内部处理的分配大小参数和传递的有符号整型一样，并将非正参数视为大小为零的请求。 （但是，从V2.6.6开始，负参数会导致null失败返回，以符合POSIX标准。）
• 适应其他分配器的奇怪特性以保持与它们的插件兼容可能降低灵活性和性能。 对于最奇怪的例子，一些早期版本的Unix分配器允许程序员重新分配已经被释放内存。 直到1993年，为了兼容性，我允许这样做。 （然而，当这个“特征”被删除时，没有人抱怨过。）
• 一些（但绝不是全部）可以改善小型程序的时间和/或空间的启发性会导致目前在典型系统中占主导地位的大型程序的时间和/或空间特性更加不可接受。

沿着这些方向的任何妥协都不是完美的。 然而，多年来，分配器已经发展到可以接受大多数用户认为可以接受的权衡。 继续影响这个malloc发展的驱动力包括：

• 其他人对malloc表现的实证研究（包括Wilson等人的上述论文，以及其他人引用的论文）。 这些论文发现，这个malloc的版本越来越多地同时被列为最具时间和空间效率的内存分配器。 但是，每个都揭示了进一步改进的弱点或机会。
• 目标工作负载的变化。 对malloc实现最敏感的程序类型的性质不断变化。一个最主要的例子是， X或其他窗口系统的存储器特性日益占主导地位。
• 系统和处理器的变化。使代码易于为典型处理器优化的实现细节和微调会随时间而变化。 此外，操作系统（包括Linux和Solaris）本身也在不断发展，例如，使内存映射成为系统级分配的偶然选择。
• 来自用户和贡献者的建议，体验报告和代码。 该代码是在几位常规志愿者贡献者的帮助下发展起来的。 最近的大多数变化是由使用Linux提供的版本的人发起的，并且很大程度上由Wolfram Gloger为Linux版本实现，然后由我集成。

算法

自最早的版本以来，malloc算法的两个核心元素保持不变：

边界标签

存储块在块之前和之后随身携带大小信息字段。 这允许两个重要的功能：

• 两个边界未使用的块可以合并为一个更大的块。 这最小化了不可用的小块的数量。
• 可以从任何已知块开始前向或后向地遍历所有块。

原始版本以这种方式完全实现了边界标记。 更新的版本省略了程序正在使用的块上的预告片字段。 这本身就是一个小小的权衡：当块是活动的时候不会使用这些字段，因此不需要存在。 消除它们可以减少开销和浪费。 但是，缺少这些字段会使得无法检查用户是否错误地覆盖应该具有已知值的字段，从而削弱了错误检测。

分档

可用块保留在箱中，按大小分组。 存在很宽大的（128）固定宽度的箱，其大小呈对数间隔。 大小小于512字节的容器每个只能容纳一个大小（间隔8个字节，简化了8字节对齐的强制执行）。 搜索可用的块以最小优先， 最合适的顺序进行处理。 如Wilson等人所示，与其他一般方法（例如首次拟合）相比，最佳拟合方案（各种类型和近似）倾向于在实际负载上产生最少的碎片。

在1995年发布的版本之前，块在块中未被分类，因此最合适的策略只是近似的。 更新的版本改为按容器内的大小排序块，其中的关系由最久-第一规则打破。

因此，该算法的一般分类最好是首先进行合并 ：释放的块与相邻的块合并，并保存在按大小顺序搜索的箱中。

这种方法导致每个块的固定簿记开销。 因为大小信息和bin链接都必须保存在每个可用块中，所以在具有32位指针的系统中最小可分配块是16字节，在具有64位指针的系统中是24字节。 这些最小尺寸比大多数人想要看到的要大 - 它们可能导致严重的浪费，例如在分配许多微小链表节点的应用程序中。 但是，至少16字节是任何需要8字节对齐的系统的特征，其中任何 malloc都存在簿记开销。

这个基本算法可以非常快。 即使它依赖于搜索机制来找到最佳匹配，使用索引技术，利用特殊情况和仔细编码导致平均情况只需要几十条指令，当然取决于机器和分配模式。

虽然通过边界标签进行合并并通过分箱进行最佳拟合表示算法的主要思想，但进一步的考虑会导致许多启发式改进。 它们包括地点保护，荒野保护，内存映射和缓存。

寻址保护

由程序在大约相同时间分配的块通常具有相似的参考模式和共存的寿命。 维护位置可以最大限度地减少页面错误和缓存未命中，从而对现代处理器的性能产生巨大影响。 如果寻址是唯一的目标，分配器可能总是将每个连续的块分配给尽可能接近前一个块。 然而，这种最近拟合 （通常近似拟合 ）策略可能导致非常糟糕的碎片化。 在当前版本的malloc中，next-fit版本仅在受限制的上下文中使用，该上下文在与其他目标冲突最少的情况下维护位置：如果没有精确所需大小的块，则最近；如果它足够大，则使用（和resplit）分裂空间; 否则最佳使用。 这种限制使用消除了无法分配完全可用的现有块的情况; 从而消除了至少这种形式的碎片。 并且，因为这种下一个拟合形式比最适合的bin-search更快，所以它加速了平均malloc 。

荒野保护

“荒野”（由Kiem-Phong Vo命名）块表示与系统分配的最顶层地址接壤的空间。 因为它位于边界，所以它是唯一可以任意扩展（通过Unix中的sbrk ）超过其原有大小的块（除非sbrk失败，因为所有内存已经耗尽）。

处理荒野块的一种方法是以与任何其他块相同的方式处理它。 （直到1994年，这种技术在大多数版本的malloc中使用）。 虽然这简化并加速了实现，但是它可以毫无顾虑地导致一些非常糟糕的最坏情况空间特征：在其他问题中，如果在存在另一个可用块时使用了wilderness块，则会增加后续请求导致无法避免的sbrk 。

目前使用更好的策略：将荒野块视为比其他所有块更“大”，因为它可以这样做（达到系统限制）并在最佳扫描中使用它。 这导致仅在没有其他块存在时才使用荒野块，进一步避免可预防的碎片。

内存映射

除了通过sbrk扩展通用分配区域之外，大多数Unix版本支持系统调用，例如mmap ，它分配一个单独的非连续内存区域供程序使用。 这在malloc提供了第二个选项来满足内存请求。 请求并返回mmap块可以进一步减少下游碎片，因为释放的内存映射不会创建需要管理的“漏洞”。 但是，由于与mmap相关的内置限制和开销，在非常有限的情况下才值得这样做。 例如，在所有当前系统中，映射区域必须是页面对齐的。 此外，调用mmap和mfree比分割现有的内存块要慢得多。 由于这些原因，当前版本的malloc仅在（1）请求大于（动态可调）阈值大小（当前默认为1MB）和（2）请求的空间在现有领域尚不可用时才依赖mmap其必须通过sbrk获得。

部分原因是因为mmap并不总是适用于大多数程序，当前版本的malloc还支持修剪主要活动区域，这实现了内存映射的一种效果 - 将未使用的空间释放回系统。 当长期存在的程序包含分配大量内存的短暂峰值，然后是具有更适度要求的更长的山谷时，可以通过将荒野块的未使用部分释放回系统来改善整体系统性能。 （在几乎所有版本的Unix中， sbrk都可以与负参数一起使用以实现此效果。）释放空间允许底层操作系统减少交换空间要求并重用内存映射表。 但是，与mmap ，调用本身可能很昂贵，因此仅在尾随未使用的内存超过可调阈值时才会尝试。

高速缓存

在基本算法的最简单版本中，每个释放的块立即与邻居合并以形成最大可能的未使用块。 类似地，仅在明确请求时才创建块（通过拆分较大的块）。

拆分和合并块的操作需要时间。 通过使用两种缓存策略中的任何一种，有时可以避免这种时间开销：

延期合并

而不是合并释放的块，而是将它们保持为当前大小，希望很快就会出现另一个相同大小的请求。 这样可以节省合并，后续拆分以及查找要拆分的非精确匹配块所需的时间。

预分配

不是逐个拆分新的块，而是一次预先拆分多个块。 这通常比一次一个地做得快。

因为分配器中的基本数据结构允许在任何时候，在malloc ， free或realloc中的任何一个中进行合并，所以相应的高速缓存启发法很容易应用。

缓存的有效性显然取决于相对于跟踪缓存块所需工作的拆分，合并和搜索的成本。 此外，有效性不太明显取决于决定何时缓存而非合并它们所使用的策略。

在连续分配和释放仅几种大小的块的程序中，缓存可能是一个好主意。 例如，如果您编写一个分配和释放许多树节点的程序，您可能会认为值得缓存一些节点，假设您知道快速执行此操作的方法。 但是，在不了解程序的情况下， malloc无法知道为了满足更大的请求而合并缓存的小块是否是一个好主意，或者是否应该从其他地方获取更大的请求。 分配器很难对此事做出更明智的猜测。 例如，分配器确定通过合并块将获得多少总连续空间同样只需合并它们然后重新分离它们也是同样昂贵的。

以前版本的分配器使用了一些搜索顺序启发式算法，这些启发式算法对缓存进行了充分的猜测，尽管偶尔会出现最糟糕的最坏情况结果。 但是随着时间的推移，这些启发式算法在实际载荷下似乎越来越有效。 这可能是因为严重依赖malloc的实际程序越来越倾向于使用更多种类的块大小。 例如，在C ++程序中，这可能对应于程序使用越来越多的类的趋势。 不同的类往往有不同的规模。 [注意：更新版本的malloc DO缓存，但只有很小的块。

Lookasides

在某些应用程序中仍然存在一种非常需要但在此分配器中未实现的缓存 - 非常小的块。 如上所述，基本算法强加了最小的块大小，对于非常小的请求可能非常浪费。例如，具有4字节指针的系统上的链表可能会分配仅包含两个指针的节点，只需要8个字节。 由于最小块大小为16字节，因此仅分配列表节点的用户程序将承受100％的开销。

在仍然保持便携式对齐的同时消除此问题将要求分配器不施加任何开销。 存在实现这一点的技术。 例如，可以通过地址比较来检查块以查看它们是否属于更大的聚合空间。 但是，这样做可能会带来巨大的成本; 事实上，这个分配器的成本是不可接受的。 块没有以其他方式跟踪地址，因此除非任意限制，否则检查可能会导致随机搜索内存。 此外，支持需要采用一个或多个策略来控制是否以及如何合并小块。

这些问题和限制导致程序员应该例行编写自己的专用内存管理例程的极少数情况之一（例如，通过C ++重载operator new() ）。 依赖于大量但近似已知数量的非常小块的程序可能会发现构建非常简单的分配器是有利可图的。 例如，可以使用嵌入的freelist从固定数组中分配块，以及在阵列耗尽时依赖malloc作为备份的规定。 更灵活一点，这些可以基于GNU gcc和libg ++提供的C或C ++版本的obstack 。 道格利亚 最后修改时间：Tue Apr 4 06:57:17 EDT 2000