buddy分配器原理

buddy 分配器是 linux 内核中的经典分配器，学习 linux 内存管理的肯定绕不开它，甚至学习其他 linux 子系统的也会学学它，因为实在是太经典了。作者想从根本理解 buddy 分配器的原理，所以找来了 buddy 分配器最初提出的文章：A fast storage allocator 和 knuth 在The Art of Computer Programming, Fundamental Algorithms, Volume 1. 中深入分析 buddy 分配器一节（2.5 节）阅读，下面内容算是这两处内容的笔记了。

是什么

buddy 分配器每次只能分配二次幂大小的块，如 1，2，4，8，16 等，如果请求分配的大小不是二次幂大小，则向上对齐到二次幂大小。

那什么是 buddy 呢？设 $k \gt 0$，当把一个大小为 $2^k$ 划分为两个 $2^{k-1}$ 大小的块 $P$ 和 $L$，那么称 $P$ 和 $L$​ 为 buddy。

那这个分配器和 buddy 有什么关系呢？这个就要看这个分配器的基本原理了，假设总的内存空间大小为 $2^m$，地址空间范围从 $[0, 2^m)$：

分配：当需要分配 $2^k$ 大小内存时（$0 \le k \le m$），如果没有直接找到有 $2^k$ 大小的块，那就找更大的块，然后把更大的块平分成两个相等大小的块（按前面的定义，这两个块就是 buddy了），一直平分直到有一块被分为 $2^k$ 的大小为止；

释放：当释放这块内存时，如果它的 buddy 是空闲的，并且大小也是 $2^k$ 且 $k \lt m$ 时，则将它们合并成一个大小为 $2^{k+1}$ 的块，重复执行这个合并流程，直到不能合并为止。

根据这个分配释放过程的描述，很明显看到这个分配器和 buddy 之间密不可分的联系了。

那如果内存总大小不是二次幂大小呢？只需要将其大小 round down 到 $2^m$ 就可以，其余地址大于等于 $2^m$ 的内存将其标为不可用或已分配就可以。

怎么做

根据上面的描述，要实现这个算法，有以下几点问题要解决：

1. 如何找到 $2^k$ 大小的内存块？

2. 如何找到一个块的 buddy？

3. 如何知道这个块是空闲的？

4. 如何知道这个块的大小？

如何找到 $2^k$ 大小的内存块？

buddy 分配器通过双向链表来管理内存块，设有 $m+1$ 个链表，这 $m+1$ 个链表的表头为 AVAIL[0]，AVAIL[1]，AVAIL[2]，… ，AVAIL[m]，它们分别管理块大小为 1，2，4，… ，$2^m$ 的内存。内存块的管理结构有两个链接字段 LINKF 和 LINKB，它们是双向链表中的向前和向后链接。定义

$$AVAILF[k] = LINKF(LOC(AVAIL(k))) = AVAIL[k] 链表的下一个节点\\ \tag{1} AVAILB[k] = LINKB(LOC(AVAIL(k))) = AVAIL[k] 链表的前一个节点$$

所以，要查找一个 $2^k$ 大小的内存块，就查找 AVAIL[k] 的链表，看该链表是否为空，如果不为空，则找到，如果为空且 $k \lt m$，那么继续查找 AVAIL[k+1] 直到找到，如果最终发现所有 $\gt k$ 的链表都是空的，那就表示没有内存可用了。

如何找到一个块的 buddy？

要计算一个块的buddy的地址，需要知道这个块地址以及该块的大小。首先，一个 $2^k$ 大小的块的地址肯定是 $2^k$ 的倍数，即地址在二进制表示下右边至少有 $k$ 个 0。这一点可以用数学归纳法严格证明：

1. 当 $k = m$ 时，该块的地址只能是 0，所以上述论述成立。
2. 设 $k = n (n \in \mathbb{N}, 0 \lt n \le m)$ 时，上述论述成立，当 $k = n - 1$ 时，其地址是通过 $2^n$ 大小的块折半得到的，而 $2^n$ 大小的块的地址是 $2^n$ 的倍数，假设这个倍数为 $x(x \in \mathbb{N})$ ，那么这个 $2^n$ 的内存块的地址范围可以表示为 $[x*2^n, (x+1)*2^n)$，它折半之后的内存块的地址为 $x*2^n$ 或 $x*2^{n-1}$，这两个地址都是 $2^{n-1}$ 的倍数，论述成立。
3. 由 1、2 得知，论述在 $0 \le k \le m$ 时成立。

因此：

Therefore a block of size, say, 32 has an address of the form $xx ... x00000$ (where the $x$’s represent either 0 or 1); if it is split, the newly formed buddy blocks have the addresses $xx ... x00000$ and $xx ... x10000$.

更加一般地，令 $buddy_k(x) = 大小为 2^k 的地址 x 的 buddy 的地址$，那么：

$$buddy_k(x) = \begin{cases} x + 2^k, &\text{if }x \space mod \space 2^{k+1} = 0;\\ x - 2^k, &\text{if }x \space mod \space 2^{k+1} = 2^k. \end{cases} \tag{2}$$

或者：

$$buddy_k(x) = x {\oplus} 2^k \tag{3}$$

如何知道这个块是空闲的？

定义内存块地址为 $P$ ，其管理结构中大小为一位的字段 $TAG$：

$$\begin{aligned} TAG(P) &= 0 = 如果 P 已经不在空闲链表中（被分配或预留）\\ TAG(P) &= 1 = 如果 P 还在空闲链表中（可用于分配） \end{aligned} \tag{4}$$

如何知道这个块的大小？

定义内存块地址为 $P$ ，其管理结构中大小为一位的字段 $KVAL$：即如果 $P$ 的大小为 $2^k$，则 $KVAL(P) = k$。

---

至此，此节的四个问题已解决。

初始状态

buddy 分配器的初始状态如下：

1. 只有一个内存块，其地址为 0，大小为 $2^m$：

   $$\begin{aligned} AVAILF[m] &= AVAILB[m] = 0\\ LINKF[0] &= LINKB[0] = LOC(AVAIL[m])\\ TAG(0) &= 1\\ KVAL(0) &= m \end{aligned} \tag{5}$$

2. 其它链表都是空的：

   $$\begin{aligned} AVAILF[k] = AVAILB[k] = LOC(AVAIL[k])，其中 0 \le k \lt m. \end{aligned} \tag{6}$$

接下来就是要描述算法是怎么进行分配和释放了。

分配

分配一个 $2^k$ 的内存块算法如下：

1. 从链表中找空闲内存块：令 $j$ 是在 $k \le j \le m$ 范围内的最小整数，使得 $AVAILF[j] \neq LOC(AVAIL[j])$ ，也就是大小为 $2^j$ 的链表不是空的。如果不存在这样的 $j$，表示没有足够大小的已知可用内存来满足分配需求了，算法不成功地终止。

2. 从链表中摘一个内存块：

   $$\begin{aligned} &L \larr AVAILF[j]\\ &P \larr LINKF(L)\\ &AVAILF[j] \larr P\\ &LINKB(P) \larr LOC(AVAIL[j])\\ &TAG(L) \larr 0 \end{aligned}$$

3. 需要拆分？：如果 $j = k$，则算法终止，返回 $L$

4. 拆分：

   $$\begin{aligned} &j \larr j - 1\\ &P \larr L + 2^j\\ &TAG(P) \larr 1\\ &KVAL(P) \larr j\\ &LINKF(P) \larr LINKB(P) \larr LOC(AVAIL[j])\\ &AVAILF[j] \larr AVAILB[j] \larr P \end{aligned}$$

   执行完以上步骤之后，就把一大块不用的一半链接到原来是空的 $AVAIL[j]$ 链表中了。然后再返回第 3 步。

至此，分配流程结束。观察到，以上流程中并未对 $KVAL(L)$ 做出更改，这相当于 $KVAL$ 离开了 buddy 系统之后就和内存块大小无关了，同时也意味着释放一个内存块时，该内存块的大小是由要释放的用户来传入，这可能可以支持释放部分内存的操作。$KVAL$ 用于快速判断 buddy 的大小合不合适合并。

释放

释放起始地址为 $L$，大小为 $2^k$ 的内存块算法如下：

1. 是否需要和 buddy 合并：令 $P \larr buddy_k(L)$，如果是以下三种情况，则不能合并，转到第 3 步，否则继续往下执行：

   1. 大小已经是最大的：$k = m$
   2. $P$ 也被占用了：$TAG(P) = 0$
   3. $P$ 还在 buddy 链表中，但是其大小和 $L$ 不一样：$TAG(P) = 1 且 KVAL(P) \neq k$

2. 合并 buddy：

   $$\begin{aligned} &LINKF(LINKB(P)) \larr LINKF(P)\\ &LINKB(LINKF(P)) \larr LINKB(P) \end{aligned}$$

   执行完上述两步之后，$P$ 就从 $AVAIL[k]$ 中摘出来了。

   然后令 $k \larr k+1$，且如果 $P \lt L$，则 $L \larr P$。返回第 1 步。

3. 将内存块放到链表中：

   $$\begin{aligned} &TAG(L) \larr 1\\ &P \larr AVAILF[k]\\ &LINKF(L) \larr P\\ &LINKB(P) \larr L\\ &KVAL(L) \larr k\\ &LINKB(L) \larr LOC(AVAIL[k])\\ &AVAILF[k] \larr L \end{aligned}$$

   执行完以上操作之后就将 $L$ 放到了 $AVAIL[k]$ 链表中。

---

启示

在 A fast storage allocator 最后一节提到了对 buddy 分配器的一个启发式优化点：可以不用每次可以合并成更大块时都做合并的动作，可以将合并的操作留到某个启发式的时机来做，比如：当返回的特定大小的块已经达到一定数量，或者当最大大小的块的数量少于所需的最小数量，或者当这些数量的某种简单函数满足时。用于控制合并时机启发式策略的具体形式取决于系统何时预见可能由于对更大块的需求成比例增加而导致问题。