# 内存，第 2 部分：实现内存分配器 > 原文：<https://github.com/angrave/SystemProgramming/wiki/Memory%2C-Part-2%3A-Implementing-a-Memory-Allocator> ## 内存分配器教程 内存分配器需要跟踪当前分配的字节以及可供使用的字节。本页介绍了构建分配器的实现和概念细节，即实现`malloc`和`free`的实际代码。 ## 这个页面讨论了块的链接 - 我是不是要为它们设置 malloc 内存？ 虽然从概念上讲我们正在考虑创建链表和块列表，但我们不需要“malloc memory”来创建它们！相反，我们将整数和指针写入我们已经控制的内存中，以便以后可以从一个地址一直跳到另一个地址。此内部信息代表一些开销。因此，即使我们从系统请求了 1024 KB 的连续内存，我们也无法将其全部提供给正在运行的程序。 ## 在块中思考 我们可以将堆内存视为每个块分配或未分配的块列表。我们不是存储明确的指针列表，而是存储有关块大小 _ 的信息，作为块 _ 的一部分。因此，概念上存在空闲块的列表，但它是隐式的，即以块大小信息的形式存储，作为每个块的一部分。 我们可以通过添加块的大小从一个块导航到下一个块。例如，如果要指向块的开头的指针`p`，则`next_block`位于`((char *)p) + *(size_t *) p`，如果要以字节为单位存储块的大小。转换为`char *`可确保以字节为单位计算指针算法。转换为`size_t *`确保将`p`的内存读取为大小值，并且如果`p`是`void *`或`char *`类型则必须。 调用程序永远不会看到这些值;它们是内存分配器的内部实现。 例如，假设您的分配器被要求保留 80 个字节（`malloc(80)`）并且需要 8 个字节的内部标头数据。分配器需要找到至少 88 字节的未分配空间。更新堆数据后，它将返回指向块的指针。但是，返回的指针不指向块的开头，因为这是存储内部大小数据的位置！相反，我们将返回块的开始+ 8 个字节。在实现中，请记住指针算法取决于类型。例如，`p += 8`添加`8 * sizeof(p)`，不一定是 8 个字节！ ## 实现 malloc 最简单的实现使用第一个拟合：从第一个块开始，假设它存在，并迭代直到找到表示足够大小的未分配空间的块，或者我们已经检查了所有块。 如果找不到合适的块，则应该再次调用`sbrk()`以充分扩展堆的大小。快速实现可能会对其进行大量扩展，因此我们不需要在不久的将来请求更多的堆内存。 找到空闲块时，它可能比我们需要的空间大。如果是这样，我们将在隐式列表中创建两个条目。第一个条目是分配的块，第二个条目是剩余的空间。 如果块正在使用或可用，有两种简单的方法可以注意。第一种是将它作为一个字节存储在头信息中，同时将其与大小和第二个一起存储，以将其编码为大小中的最低位！因此，块大小信息将仅限于偶数值： ``` // Assumes p is a reasonable pointer type, e.g. 'size_t *'. isallocated = (*p) & 1; realsize = (*p) & ~1; // mask out the lowest bit ``` ## 对齐和四舍五入的考虑因素 许多架构期望多字节基元与 2 ^ n 的某个倍数对齐。例如，通常需要将 4 字节类型与 4 字节边界（以及 8 字节边界上的 8 字节类型）对齐。如果多字节基元没有存储在合理的边界上（例如从奇数地址开始），那么性能会受到很大影响，因为它可能需要两个存储器读取请求而不是一个。在一些架构上，惩罚甚至更大 - 程序将因[总线错误](http://en.wikipedia.org/wiki/Bus_error#Unaligned_access)而崩溃。 由于`malloc`不知道用户将如何使用分配的内存（双精度数组？字符数组？），返回程序的指针需要针对最坏情况进行对齐，这是与体系结构相关的。 从 glibc 文档中，glibc `malloc`使用以下启发式：“malloc 为您提供的块保证对齐，以便它可以保存任何类型的数据。在 GNU 系统上，地址始终是 8 的倍数系统，以及 64 位系统上 16 个的倍数。“ 例如，如果您需要计算需要多少 16 字节单位，请不要忘记向上舍入 - ``` int s = (requested_bytes + tag_overhead_bytes + 15) / 16 ``` 额外的常量确保不完整的单位被四舍五入。请注意，实际代码更有可能符号大小，例如`sizeof(x) - 1`，而不是编码数值常数 15。 [如果您对此感兴趣，可以参考以下关于内存对齐的精彩文章](http://www.ibm.com/developerworks/library/pa-dalign/) ## 关于内部碎片的说明 当您提供的块大于其分配大小时，会发生内部碎片。假设我们有一个大小为 16B 的空闲块（不包括元数据）。如果它们分配 7 个字节，您可能需要向上舍入到 16B 并返回整个块。 当你实现合并和拆分时，这会变得非常险恶（下一节）。如果你没有实现任何一个，那么你可能最终返回一个大小为 64B 的块用于 7B 分配！这个分配有一个 _ 批次 _ 的开销，这是我们试图避免的。 ## 实施免费 当调用`free`时，我们需要重新应用偏移量以返回到块的“实际”开始（还记得我们没有给用户指向块的实际开始吗？），即到哪里我们存储了大小信息。 一个简单的实现只会将块标记为未使用。如果我们将块分配状态存储在最小的位中，那么我们只需要清除该位： ```c *p = (*p) & ~1; // Clear lowest bit ``` 但是，我们还有一些工作要做：如果当前块和下一个块（如果存在）都是空闲的，我们需要将这些块合并为一个块。同样，我们也需要检查前一个块。如果存在并表示未分配的内存，那么我们需要将块合并为单个大块。 为了能够使用先前的空闲块合并空闲块，我们还需要找到前一个块，因此我们也将块的大小存储在块的末尾。这些被称为“边界标签”（ref Knuth73）。由于块是连续的，因此一个块的末尾位于下一个块的开头旁边。因此，当前块（除第一个之外）可以进一步查看几个字节以查找前一个块的大小。有了这些信息，您现在可以向后跳！ ## 性能 通过以上描述，可以构建存储器分配器。它的主要优点是简单 - 与其他分配器相比至少简单！分配存储器是最坏情况的线性时间操作（搜索链接列表用于足够大的空闲块）并且解除分配是恒定时间（不需要将 3 个块合并到单个块中）。使用此分配器可以尝试不同的放置策略。例如，您可以从最后一个冻结块的位置开始搜索，或者从上次分配的位置开始搜索。如果你确实存储了指向块的指针，你需要非常小心它们始终保持有效（例如，当合并块或其他 malloc 或免费调用改变堆结构时） ## 明确的自由列表分配器 通过实现明确的双向链接的空闲节点列表，可以实现更好的性能。在这种情况下，我们可以立即遍历下一个空闲块和前一个空闲块。这可以将搜索时间减半，因为链接列表仅包括未分配的块。 第二个优点是我们现在可以控制链表的排序。例如，当一个块被释放时，我们可以选择将它插入到链表的开头而不是总是在它的邻居之间。这将在下面讨论。 我们在哪里存储链表的指针？一个简单的技巧是要意识到块本身没有被使用并将下一个和前一个指针存储为块的一部分（尽管现在你必须确保空闲块总是足够大以容纳两个指针）。 我们仍然需要实现边界标记（即使用大小的隐式列表），这样我们就可以正确地释放块并将它们与它们的两个邻居合并。因此，显式空闲列表需要更多代码和复杂性。 使用显式链接列表，使用快速简单的“查找优先”算法来查找第一个足够大的链接。但是，由于可以修改链接顺序，因此这对应于不同的放置策略。例如，如果链接从最大到最小维护，那么这将产生“最适合”的放置策略。 ### 显式链表插入策略 新冻结的块可以轻松插入两个可能的位置：开头或地址顺序（通过使用边界标签首先找到邻居）。 在开头插入会创建一个 LIFO（后进先出）策略：最近的 free'd 空间将被重用。研究表明碎片比使用地址顺序更糟糕。 以地址顺序插入（“地址排序策略”）插入空闲块，以便按递增的地址顺序访问块。此策略需要更多时间来释放块，因为必须使用边界标记（大小数据）来查找下一个和以前的未分配块。但是，碎片化程度较低。 ## 案例研究：Buddy Allocator（隔离列表的一个例子） 隔离分配器是将堆分成不同区域的分配器，这些区域由不同的子分配器处理，具体取决于分配请求的大小。大小被分组为类（例如，2 的幂），并且每个大小由不同的子分配器处理，并且每个大小维护其自己的空闲列表。 众所周知的这种类型的分配器是伙伴分配器。我们将讨论二进制伙伴分配器，它将分配分成大小为 2 ^ n（n = 1,2,3，...）的一些基本单位字节数的块，但其他也存在（例如 Fibonacci 分裂 - 你能不能看看为什么命名？）。基本概念很简单：如果没有大小为 2 ^ n 的空闲块，则转到下一级并窃取该块并将其拆分为两个。如果相同大小的两个相邻块变为未分配，则它们可以一起合并成一个大小为两倍的单个块。 好友分配器很快，因为可以从 free'd 块的地址计算要合并的相邻块，而不是遍历大小标记。最终性能通常需要少量汇编程序代码才能使用专用 CPU 指令来查找最低的非零位。 Buddy 分配器的主要缺点是它们受 _ 内部碎片 _ 的影响，因为分配被四舍五入到最接近的块大小。例如，68 字节的分配将需要 128 字节的块。 ### 进一步阅读和参考 * 参见[软件技术基础和理论计算机科学 1999 年会议论文](http://books.google.com/books?id=0uHME7EfjQEC&lpg=PP1&pg=PA85#v=onepage&q&f=false)（谷歌书籍，第 85 页） * ThanksForTheMemory UIUC 讲座幻灯片（ [pptx](https://subversion.ews.illinois.edu/svn/sp17-cs241/_shared/wikifiles/CS241-05-ThanksForTheMemorySlides.pptx) ）（ [pdf](https://subversion.ews.illinois.edu/svn/sp17-cs241/_shared/wikifiles/CS241-05-ThanksForTheMemorySlides.pdf) ）和 * [维基百科的好友内存分配页面](http://en.wikipedia.org/wiki/Buddy_memory_allocation) ## 其他分配器 还有许多其他分配方案。例如 [SLUB](http://en.wikipedia.org/wiki/SLUB_%28software%29) （维基百科） - Linux 内核内部使用的三个分配器之一。