本文档译自 bitsquid 引擎开发博客文章"Allocation Adventures 3：The Buddy Allocator"，作者 Niklas Frykholm，原文参见此处
概述 - Overview
内存分配器的工作是从操作系统获取一大块内存，然后切分它，把分出来的小块给独立的内存分配器使用：
void *A = malloc(10);
void *B = malloc(100);
void *C = malloc(20);
------------------------------------------------------
| A | free | B | C | free |
------------------------------------------------------
分配器需要快速地处理分配请求，即找到一块合适的空闲内存。它还需要快速释放内存，即让之前使用的内存块可用于新的分配。最后，它需要防止碎片化——稍后会详细讨论这个问题。
假设我们将所有空闲块放在一个链表中，并通过在链表中搜索合适大小的块来分配内存。这使得分配成为一个 O(n) 的操作，其中 n 是空闲块的总数。我们可能有成千上万的空闲块，并且在链表中查找将导致缓存丢失，因此为了创建一个更好的分配器，我们需要一个更快的方法。
此外，当空闲内存被分割成小块而不能有效使用时，就会出现碎片：
------------------------------------------------------
| A | free | B | C | free |
------------------------------------------------------
在这里，我们可能没法处理一些大的分配请求，因为剩余的空闲内存被分成了两部分。在实际场景中，内存可能会被分割成数千个片段。
防止碎片的第一步是确保我们有一些方法将空闲内存块合并在一起。否则，就算分配内存块后释放了它们也将使内存缓冲区一直处于碎片状态，无法处理任何大型请求：
-------------------------------------------------------
| free | free | free | free | free | free |
-------------------------------------------------------
合并需要是一个快速的操作，因此扫描整个缓冲区以寻找相邻的空闲块不是一个好选择。
注意，即使我们合并所有邻近的空闲块，我们仍然可能得到碎片，因为当它们之间有一块已分配的内存时，我们不能合并空闲块：
-----------------------------------------------------------
| free | A | free | B | free | C | free | D | free |
-----------------------------------------------------------
防止造成这种割裂的有效技术有：
- 为长期分配和短期分配分别使用单独的分配器，这样短期分配就不会在长期分配之间产生“洞”。
- 将较小的分配放在缓冲区的单独部分，这样它们就不会干扰大的分配。
- 使内存块可重定位（即使用“句柄”而不是指针）。
- 直接从操作系统分配整个页面，并依靠页面映射来防止碎片。
如果你的页面大小较小，并遵循本系列前面的建议，尝试分配一些大的资源，而不是许多小的资源，那么最后一种方法可能会非常有效。另一方面，较小的页面大小意味着更多的 TLB 丢失。但话又说回来，如果你有很好的数据局部性，也许这并不重要?......这将考验你判断的功力！（或许我该提供一些实际数据，但好麻烦......）
许多分配器使用的三种技术是就地链表（或者叫侵入式链表）、前置信息和后置信息。
侵入式链表是一种在不使用任何额外内存的情况下存储空闲内存块链表的技术。其思想是，由于块中的内存是空闲的，我们可以直接将指向上一个内存块的指针 prev 和下一个内存块的指针 next 存储在块本身中，这意味着我们不需要任何额外的存储空间。
前置信息是位于分配的内存之前的一小段数据。包含有关该内存的一些信息。分配器将为前置信息分配额外的内存，并在分配时用信息填充它：
void *A = malloc(100);
------------------------
| pre | A | post|
------------------------
在 C 语言中，我们非常需要一个前置信息，因为当用户在指针 p 上调用 free(void *p) 时，我们不知道在 p 处分配的内存块有多大。这些信息需要来自某个地方，前置信息是一个合理的选择，因为它很容易从 free() 代码访问：
struct Preamble
{
unsigned size;
...
};
void free(void *p)
{
Preamble *pre = (Preamble *)p - 1;
unsigned size = pre->size;
}
请注意，我们还有其他选项。还可以使用哈希表来存储每个指针的大小。我们可以在内存缓冲区中为特定大小的分配保留特定区域，并使用指针比较来查找特定指针的区域（以及大小）。但是哈希表是昂贵的，并且只有在不同大小的数据数量有限的情况下，为特定大小的数据分配特定的区域才真正有效。所以前置信息是一个常见的选择。
不过他们真的很烦人！因为它们增加了内存分配的大小，并且扰乱了对齐。例如，假设用户想要分配 4K 内存，而我们的操作系统使用 4K 页面。如果不使用前置信息，我们可以直接从操作系统分配一个页面并返回它。但如果我们需要保存一个四字节的前置信息，那么我们必须从操作系统中分配 8K，这样我们才有地方放额外的四个字节。太烦人了！
更令人恼火的是，在大多数情况下，存储大小是没有意义的，因为调用者已经知道了它。例如，在 C++ 中，当我们：
delete x;
运行时知道 x 的实际类型，否则它将无法正确调用析构函数。但是由于它知道类型，所以它也知道该类型的大小，并且可以在释放内存时将该信息提供给分配器。
类似地，如果内存属于 std::vector，因为 vector 类有一个容量字段，用于存储缓冲区的大小，因此大小也是已知的。
事实上，你可以争辩说，无论何时你有一个指针，运行时的某些部分肯定知道内存分配有多大，不然的话，运行时如何使用内存而不引起访问冲突呢？
因此，我们可以想象一个平行世界，我们将使用 free(void*, size t) 而不是 free(void*)，并且在释放内存块时要求调用者显式传递大小。那个世界将是分配者的天堂。但是，唉，这不是我们生活的世界。
（你可以在子系统中执行这种平行世界，但我不确定在更大的项目中全面执行它是否是一个好主意。违背编程语言的本质可能会很痛苦。）
类似地，后置信息是放在已分配内存块末尾的一段数据。它主要用于合并。如上所述，当你释放一个内存块时，你希望将其与它的邻居合并。但是，你怎么知道你的邻居是什么情况，它们是否空闲呢？对于处于当前块右侧的邻居，事情可能稍微简单些，因为这邻居将从当前块的结束处开始，你可以轻松地找到并访问它的前置信息。
左侧的邻居比较棘手。因为你不知道你的邻居有多大，所以你也不知道要在哪里找到它的前置信息。后置信息解决了这一问题，因为左侧邻居的后置信息总是紧靠着当前块的左边。
同样，前置信息和后置信息的替代方法是使用一些分布较为集中的数据结构，其中包含有关你可以查询的块的信息。挑战在于如何使这样的查询高效。
如果你要求所有分配都以 16 字节对齐，那么同时拥有一个前置信息和一个后置信息将可能为你的分配增加 32 字节的开销。特别是如果你有很多小的分配，这会看起来像个花生?。你可以通过使用 slab 或块分配器进行分配来解决这个问题，或者更好的方法是完全避免它们，去尝试进行更少、更大的分配，正如本系列中已经提到的那样。
伙伴分配器 - The buddy allocator
通过对一些一般分配问题的简短介绍，现在是时候看看伙伴分配器了。
伙伴分配器通过反复将内存块分成两半来创建两个更小的“小伙伴”，直到我们得到所需大小的块。
如果我们从一个从操作系统分配的 512k 块开始，我们可以将它分割成两个 256k 的伙伴。然后我们可以将其中的一个进一步分割成两个 128k 的伙伴，以此类推。
在分配时，我们检查是否有大小合适的空闲块。如果没有，我们将一个更大的块分割多次，以获得一个合适大小的块。如果我们想要 32k，我们把 128k 的块分成 64k 的块然后把其中一个分成 32k 的块。
在此结束时，分配器的状态看起来像这样：
Buddy allocator after 32 K allocation:
-----------------------------------------------------------------
512 | S |
-----------------------------------------------------------------
256 | S | F |
-----------------------------------------------------------------
128 | S | F |
---------------------------------
64 | S | F | S - split
----------------- F - free
32 | A | F | A - allocated
---------
如你所见，这种分割方法意味着块大小将始终是 2 的幂。如果你尝试分配较小的块，比如 13k，那么分配将四舍五入到最接近的 2 次方，即分配一个 16k 块。
所以这里发生了大量的分裂。这种碎片被称为内部碎片，因为它是块内部的内存浪费，而不是块之间的空间浪费。
合并伙伴分配器非常简单。每当一个块被释放时，我们检查它的伙伴是否也被释放。如果是，我们将这两个伙伴合并到他们曾经分离的单个块中。我们继续递归地这样做，所以如果一个空闲块也有一个空闲的伙伴，它们就会合并成一个更大的块，以此类推。
伙伴分配器在防止外部碎片方面做得很好，因为无论何时释放一些东西时，我们都有很好的机会进行合并，如果我们不能合并，那么“洞”应该很快被类似大小的分配填充。你仍然可以想象最坏的情况。例如，如果我们先分配每个叶节点，然后释放这些分配的一部分节点，我们最终会得到一个相当碎片化的内存。但这种情况在实践中应该是罕见的：
最糟糕的分配情形, 16K 的块大小
-----------------------------------------------------------------
512 | S |
-----------------------------------------------------------------
256 | S | S |
-----------------------------------------------------------------
128 | S | S | S | S |
-----------------------------------------------------------------
64 | S | S | S | S | S | S | S | S |
-----------------------------------------------------------------
32 | S | S | S | S | S | S | S | S | S | S | S | S | S | S | S | S |
-----------------------------------------------------------------
16 |A|F|A|F|A|F|A|F|A|F|A|F|A|F|A|F|A|F|A|F|A|F|A|F|A|F|A|F|A|F|A|F|
-----------------------------------------------------------------
我知道我说得很含糊。这是因为通常很难对分配器在防止碎片方面有多“好”做出有意义的评价。你可以说它在某种内存分配模式下做得有多好，但每个程序都有不同的内存分配模式。
伙伴分配器的实现 - Implementing the buddy allocator
关于算法和数据结构的文章通常很少提及实现细节。例如，你可以找到大量描述伙伴分配器背后的高级思想的文章，就像我在上面概述的那样，但是关于如何实现这个该死的东西的信息并不多！
这很遗憾，因为实现细节真的很重要。例如，经常会看到有人仔细地实现 A* 算法，但他们对开集和闭集使用的数据结构完全消除了算法的性能优势。
让我们来看更多细节。
我们从分配开始。我们如何找到一个请求大小的空闲块？我们可以使用上面描述的技术：我们把不同大小的空闲块分别放在一个侵入式链表中。要找到一个空闲的块，我们只需从该大小的块列表中取出第一个元素，将其从列表中移除并返回。
如果没有合适大小的块，我们取下一个更大的块并将其拆分。我们使用我们得到的两个块中的一个，并将另一个块放到相应大小的空闲列表中。如果更大的块列表也是空的，我们可以去更大的块，以此类推。
为了让事情变得简单，让我们引入层级的概念。我们说最开始的单个块，代表整个缓冲区，它在第 0 层。当我们把它分开时，我们在第 1 层得到两个块。继续把它们分开，我们得到第 2 层的四个块，以此类推。
现在我们可以编写在第 n 层分配块的伪代码：
if 第 n 层的空闲块列表是空的（没有空闲块） {
向 n - 1 层索取一个块（同样使用这个算法）;
在第 n 层把块一分为二;
把分开的两个块插入第 n 层的空闲块列表中，然后从列表中移除一个块，返回它;
}
为此，我们需要的唯一数据结构是指向每层第一个空闲块的指针列表：
static const int MAX_LEVELS = 32;
void* _free_lists[MAX_LEVELS];
列表的 prev 和 next 指针直接存储在空闲块中（别忘了我们使用侵入式链表）。我们还可以注意到分配器的一些数学性质：
total_size == (1 << num_levels) * leaf_size
size_of_level(n) == total_size / (1 << n)
max_blocks_of_level(n) = (1 << n)
请注意，MAX_LEVELS = 32 可能已经足够了，在 leaf_size 至少为 16 字节的情况下（因为必须要为侵入式链表的 prev 和 next 指针留出空间，所以最小块至少有两个指针的大小，并且我们假设是 64 位系统。），它已超出了 4 GB 的总大小。
还请注意，我们可以为伙伴分配器中的每个块创建一个唯一的块索引，即 (1 << level) + index_in_level - 1。级别 0 的节点索引为 0。级别 1 的两个节点将分别具有索引 1 和 2，以此类推：
块索引示例
-----------------------------------------------------------------
512 | 0 |
-----------------------------------------------------------------
256 | 1 | 2 |
-----------------------------------------------------------------
128 | 3 | 4 | 5 | 6 |
-----------------------------------------------------------------
64 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
-----------------------------------------------------------------
32 |15 |16 |17 |18 |19 |20 |21 |22 |23 |24 |25 |26 |27 |28 |29 |30 |
-----------------------------------------------------------------
索引中条目的总数为 (1 << num_levels) - 1。如果我们想分配一些内存，这就是我们所需要一切。（为简单起见，下面我们忽略 - 1 的部分，将其四舍五入为 (1 << num_level)）
那么解分配又该如何写呢？
棘手的部分是合并。做合并本身很简单，我们只需要取两个块，把它们从 n 层的空闲列表中移除然后把合并后的块插入 n - 1 层的空闲列表中。
真正难的地方在于什么时候该合并。也就是说，当我们释放一个块时，如何知道它的伙伴是否也空闲呢？
首先，我们要注意到我们可以轻松地算出伙伴的地址。假如我们有一个块 p，已知在第 n 层。我们可以计算它在此层中的索引为：
index_in_level_of(p, n) == (p - _buffer_start) / block_size_of_level(n)
如果计算出的层内索引 i 是偶数，则伙伴位于索引 i + 1 处，否则伙伴位于 i - 1 处，我们可以使用上面的公式来求解给定指针的层内索引。
已知伙伴的地址，我们叫它 buddy_ptr，我们怎么知道它是不是空闲的？我们可以遍历第 n 层的空闲列表，如果我们在那里找到它，我们就知道它是空闲的，否则就不是。但是可能有成千上万的块，遍历一个巨大的列表即使对缓存来说也很困难。
为了做得更好，我们需要存储一些额外的信息。
我们可以像前面讨论的那样使用前置信息和后置信息，但那将是一个遗憾。伙伴分配器有很好的，均匀的块大小，比如 4k、8k 等等，我并不想因为前置或后置信息而把它弄得不整齐。
但是我们能做的是为每个块存储一个比特，告诉我们这个块是空闲的还是已分配的。我们可以使用如上所述的块索引来访问这个区域。这将总共需要 (1 << num_level) 个比特。由于整个树的大小是 (1 << num_levels) * leaf_size，我们可以看到，存储这些位的额外开销是 1/8/leaf_size（译注：即每个块的元数据与块本身的大小之比，若 leaf_size = 16，则开销为 0.7%）。而如果将 leaf_size 设置为 128 字节（更小的分配最好由 slab 分配器处理），则该表的开销仅为 0.1%，还算不错。
但事实上我们还可以做得更好。每个块只需要"半"个比特就够了。这听起来不太可能，但方法是这样的：
对于每两个块，即一对伙伴 A 和 B，我们存储一个比特，它的值是 (is_A_free) XOR (is_B_free)。我们可以通过每次释放或分配一个伙伴时翻转它来轻松地维护该位的状态。过程如下。
在一开始没有任何分配时，它的初值是 1 XOR 1 = 0。
当我们开始考虑分配时，由于我们一次只分配一个块，所以另一个伙伴肯定是空闲的，它的值是 1 XOR 0 = 1 或 0 XOR 1 = 1，都是 1，因此只需要把初值翻转。如果还有下一次分配，这样两个伙伴都不空闲，它的值只能是 0 XOR 0 = 0，那么，也只需要翻转上一次的结果就可以。
容易看出，释放只是分配的逆过程，所以也只是简单翻转即可。
重点来了。当我们释放后，开始考虑合并时，我们可以肯定至少有一个是空闲的，毕竟只有块被释放时，我们才会考虑合并，这排除了比特是 0 XOR 0 = 0 的可能。这意味如果它是 0，那么说明两个块都是空闲的（1 XOR 1 = 0）。如果它是 1，那么只有刚刚释放的块是空闲的（1 XOR 0 = 1 或 0 XOR 1 = 1）。
因此，我们可以为一对伙伴只提供一个比特，那么开销为 1/16/leaf_size。
细心的读者可能会注意到我一直在作弊。
一直以来，我都假设我们知道要释放的块是第几层。否则，我们无法计算伙伴的地址或它在节点树中的索引。
但是要知道传进来的指针属于第几层，我们必须知道它分配的块的大小。因此，只有当用户在释放块时，显式传递这个块的大小，才真正有效。例如，使用我们前面讨论过的 free(void*, size t) 那样的接口。
如果我们想要支持更简单和更常见的API，free(void *p)，分配器需要以某种方式存储每个分配的大小。
同样，可以用前置信息的方式，但是我们仍不想这样做。
我们可以用 (p - _buffer_start) / leaf_size 作为索引在一个数组里存储块大小。注意，这与块索引不同。我们不能使用块索引，因为我们不知道层数。相反，这是一个大小为 1 << (num levels - 1) 的索引数组，伙伴分配器可能返回的任何指针都能按照上面的式子映射到数组的某个元素。
我们不需要在索引中存储完整的大小（这需要花费 32 比特），只需要存储层级。这是大概是 5 比特的开销（假设最大层级是 32）。由于这里数组元素的总数是块索引总数的一半，这相当于每个块 2.5 位。
但我们还可以做的更好。
我们可以使用块索引并存储单个比特来跟踪该层级的块是否被分割，而不是显式地存储层级。
为了找到一个已分配块所属的层级，我们可以使用这个算法：
n = num_levels - 1;
while n > 0
if block_has_been_split(ptr, n - 1)
return n;
n = n - 1;
return 0;
由于最小块不能再分割，所以我们只需要 1 << (num_levels - 1) 个比特。这意味着分割索引的成本与合并索引的成本相同，每个块 0.5 比特。令人惊讶的是，我们可以在每个块的总开销只有 1 比特的情况下完成所有这些。
节省内存的好处是，虽然我们现在必须循环一比特才能找到分配的大小，但是 num_level 通常很小（通常小于等于 32），并且由于每个条目只有 1 比特，因此缓存使用率相当高。此外，使用这种方法可以很容易地同时提供一个 free(void*) 和一个 free(void*, size t) 接口。后者可以被更复杂的调用者使用，来避免计算块大小时的循环。
内存排布 - Memory arrangements
我们在哪里存储每个块的 1 比特元数据？我们可以另外开一个单独的缓冲区，但它不是那么优雅。这意味着我们的分配器必须从系统请求两个缓冲区，一个用于数据，另一个用于元数据。
相反，让我们把元数据放在缓冲区本身，在开始时我们可以很容易地找到它。我们将用于存储元数据的块标记为已分配的，这样它们就不会被其他分配使用：
保留元数据后内存的初始状态:
-----------------------------------------------------------------
512 | S |
-----------------------------------------------------------------
256 | S | F |
-----------------------------------------------------------------
128 | S | F |
---------------------------------
64 | S | S |
-----------------
32 | S | S | S | F |
-----------------
16 |A|A|A|A|A|F|
-------------
********** Metadata
请注意，在分配元数据时，我们可以偷点懒，不必将分配四舍五入到最接近的 2 的幂，然后取相应块。相反，我们需要多少最小块就取多少最小块。这是因为当我们分配元数据时，我们知道分配器是完全空的，所以我们保证能够分配相邻的最小块。在上面的例子中，我们只需要为元数据使用 5 * 16 = 80 KB，而不是四舍五入到 128 KB。
（这里元数据的大小被大大夸大了，只是让你更好地了解我的意思。实际上，由于图中的树只有六层，所以元数据一共只有 1 * (1 << 6)= 64 位，也就是 8 字节，而不是 80KB。）
注意，在以这种方式分配元数据时必须小心一点，因为你是在为内存分配函数所依赖的元数据分配内存。这是一个先有鸡还是先有蛋的问题。你必须为这个初始分配编写一个特殊的分配例程，或者非常小心地编写分配代码，以便优雅地处理这种情况。
我们可以用同样的技术来处理另一个棘手的问题。
伙伴分配器的大小必须是最小块大小的 2 次幂，这有点令人恼火。假设我们碰巧有 400K 的内存。我们希望可以使用所有的内存，而不仅仅是前 256K。
我们可以用同样的方法。对于 400K 内存，我们可以创建一个 512K 的伙伴分配器，并将它的前 144K 标记为“已分配”。我们还偏移了缓冲区的开始位置，以便可用内存的开始位置与内存中缓冲区的开始位置一致。像这样：
-----------------------------------------------------------------
512 | S |
-----------------------------------------------------------------
256 | S | F |
-----------------------------------------------------------------
128 | S | S |
---------------------------------
64 | S | S | S | F |
---------------------------------
32 | S | S | S | S | S | F |
-------------------------
16 |A|A|A|A|A|A|A|A|A|A|
---------------------
******************* Unusable, unallocated memory
MET * Metadata
^
+-- Usable memory starts here
同样，在编写执行初始分配的代码时，需要小心一些，避免写入未分配的内存并导致访问冲突。
伙伴分配器的缓冲区增长 - The buddy allocator and growing buffers
正如上一篇文章中提到的，伙伴分配器非常适合分配动态增长的缓冲区，因为我们想要的是分配的大小增加一倍，这正是伙伴分配器的层级结构。
当缓冲区需要增长时，我们只需从伙伴分配器往上分配一层，并设置缓冲区的容量，以便它填充所有的空间。
注意，这完全避免了内部碎片问题，这是伙伴分配器解决的最大问题之一。没有内部碎片，因为动态缓冲区将利用所有可用空间。
在下一篇文章中，我将展示所有这些是如何联系在一起的。