离职前夕清理公司硬盘数据的时候,偶然发现原来自己去年三月份的时候还写过一个 non-intrusive buddy allocator 呢。因为时间太过久远加上之前写的时候没有加上该有的注释,导致花了一番功夫才看懂核心算法再写什么,更别说几个看起来完全不明觉厉的 offset-to-address 的计算。

于是我想,应该有必要整理一下,万一哪天真的需要呢?

Theory

Non-intrusive 的做法是,不在实际分配的内存中加入 meta-data,而是将 buddy-allocator 自身做成一个 allocation bookkeeper。

考虑到 allocator 要求管理的内存块必须是$2^k, k \in Z$大小,我们可以把一块内存对应的 bookkeeping 做成一棵 perfect binary tree。以大小为 8K 的内存块为例,对应的 perfect binary tree 结构如下:

每一个节点对应内存块中的一个可用区域(考虑从上往下的映射);最下层叶子节点对应完整的内存块,每个叶子节点对应一个最小的内存单元;父节点对应的内存区域包含子节点对应的内存区域。

而 perfect binary tree 又可以用数组来表示(实际上是特殊的 complete binary tree),一方面可以提升内存利用率(没有额外的前后继指针),又可以提高访问性能(减少动态分配以及连续内存带来的 cache-locality)。

Implementation

为了实现方便以及让分配、释放算法看起来更加简洁,作如下两个设定

  • 定义 maximum consecutive block (MCB) 为一个能被直接管理的最大的连续内存区域,大小仍然要满足$2^k$的要求
  • 用 bookkeeper tree 中的每个节点去保存对应内存区域的 MCB 的大小

于是得到对于每一个节点的递归定义

$$M(i)=\begin{cases}\max\left\{M(LC(i)),M(RC(i))\right\} & \text{otherwise}\\M(LC(i))+M(RC(i)) & M(LC(i))=M(RC(i))\end{cases}$$

上面 $M(i)$ 表示节点 $i$ 的 MCB 值,也即实际保存在节点里的值;$LC(i)$ 和 $RC(i)$ 分别表示节点 $i$ 的左子节点和右子节点。

仍然以前面 8K 大小的内存块举例,假设我们要从内存块里分配出大小 1K 的内存,那么这棵树的状态则变成如下样子:

后面实现过程中会发现这个定义解决掉了很多麻烦。

implementing allocation

分配算法大体顺序如下:

  1. 比较请求分配的内存大小和根节点的值,确认是否还有足够的空间可以分配。如果根节点的大小小于请求大小,很明显没有空间了。
  2. 如果空间足够,则沿着根节点向下搜索,采用 last-fit strategy,即最后一个满足要求的节点,找到目标节点。因为父节点覆盖的内存区域是包括子节点的,所以要使用 last-fit。
    实际上我们可以利用一个性质来简化第2步的逻辑:如果存在满足要求的节点,那么具有这个大小的节点所在的 depth/height 是固定的,和树当前状态无关(得益于前面 MCB 的定义)。于是我们可以在一棵假想的、全新的树上遍历,结合实际的树的信息去判断左右的走向。
  3. 将目标节点标记为0,然后回溯向上到根节点,修正路径上节点的信息。
  4. 假设目标节点在数组中的序号为 $i$,那么利用公式 $\text{offset} = (i+1) \cdot \text{block_size_needed} - \text{total_block_size}$ 算出分配的内存的起始序号相对于完整内存块的偏移量(其实就是内存块对应的第一个叶子节点在整个叶子节点中的序号)。
    至于这个公式怎么来的,后面再说。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
size_t BinManager::Allocate(size_t slots_required)
{
assert(slots_required != 0);
if (slots_required == 0) {
return noffset;
}

size_t slots_needed = buddy_util::NearestUpperPowerOf2(slots_required);
if (max_consecutive_slot_[0] < slots_needed) {
return noffset;
}

size_t index = 0;
for (auto node_slots = total_slot_count_;
node_slots != slots_needed;
node_slots >>= 1) {
if (max_consecutive_slot_[buddy_util::LeftChild(index)] >= slots_needed) {
index = buddy_util::LeftChild(index);
} else {
index = buddy_util::RightChild(index);
}
}

// The relative distance from first slot in the bin just now allocated to the
// first slot in the underlying raw memory chunk.
size_t offset = (index + 1) * slots_needed - total_slot_count_;

max_consecutive_slot_[index] = 0;
while (index) {
index = buddy_util::Parent(index);
max_consecutive_slot_[index] = std::max(
max_consecutive_slot_[buddy_util::LeftChild(index)],
max_consecutive_slot_[buddy_util::RightChild(index)]);
}

return offset;
}

Deallocation

释放的过程就相对简单。

输入是前面 allocation 过程得到的 offset,首先转换利用上面的公式的变形(上面公式中的 block_size_needed 等于叶子节点的大小,为1),转换得到原来的 $i$,然后从 $i$ 指向的叶子节点开始,向上搜索,碰到的第一个标记为0的节点就是要找的目标节点,恢复其大小(前面提到的性质)。

接着仍然向上回溯到根节点,修正路径上的节点信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void BinManager::Free(size_t offset)
{
// The value of noffset can be regarded as positive infinity.
assert(offset < total_slot_count_);
if (offset >= total_slot_count_) {
return;
}

// Since multiple indices can be mapped into a single offset, we backtrace to
// locate the bin from bottom.
// The first bin we meet in the path whose slot count is 0 is the target.
// Incorrect |offset| may cause undesired deallocation for yet another bin.
size_t node_slot_count = 1;
size_t index = offset + total_slot_count_ - 1;
while (max_consecutive_slot_[index]) {
// Reached the root. The |offset| is incorret.
if (index == 0) {
return;
}

node_slot_count <<= 1;
index = buddy_util::Parent(index);
}

max_consecutive_slot_[index] = node_slot_count;
while (index != 0) {
index = buddy_util::Parent(index);
node_slot_count <<= 1;

size_t lc_slots = max_consecutive_slot_[buddy_util::LeftChild(index)];
size_t rc_slots = max_consecutive_slot_[buddy_util::RightChild(index)];

// Merge adjacent bins if possible.
if (lc_slots + rc_slots == node_slot_count) {
max_consecutive_slot_[index] = node_slot_count;
} else {
max_consecutive_slot_[index] = std::max(lc_slots, rc_slots);
}
}
}

Derivation of the Formula

最后解释一下怎么得到公式 $\text{offset} = (i+1) \cdot \text{block_size_needed} - \text{total_block_size}$。

首先做如下假设

  • 拥有的总内存块 total_block_size 为 $2^n$
  • 请求的内存大小 block_size_needed 是 $2^k$
  • 目标节点在数组中的序号是 $j$
  • perfect binary tree 对应的数组下标从1开始,i.e. 根节点在数组中的序号是1。这个假设是必要的,因为可以让左右子节点的公式更加简单

基于上述假设,我们就有

  1. 目标节点所在的高度一定是 $k$ (叶子节点位于高度0)。于是目标节点覆盖的第一个子节点的序号是 $j \cdot 2^k$。只需要不断的访问左子节点,直到叶子
  2. 第一个叶子节点的序号是 $ 2^n $
  3. 算得两个叶子节点的偏移量 $ \text{offset} = j \cdot 2^k - 2^n $
  4. 因为实现时数组下标 $i$ 从0开始,所以我们有 $ j = i + 1$
  5. 带入(3)中的式子,得到 $\text{offset} = (i+1) \cdot 2^k - 2^n $

公式就这样出来了,基本没有什么太复杂的东西。

假设数组从1开始也是一个常用的技巧,可以极大地简化运算和推导。所以你会看到算法导论里的数组一直都是从1开始的,因为是在可以极大的简化分析。而最后也只需要一个线性变换就拿到了实际环境下的公式。

安利时刻

对于非侵入式的 allocator 来说,前面实现的分配/释放只起到了 bookkeeping 的作用。你还需要自己提供一个能够分配/释放真实内存的模块,并利用前面实现的 buddy allocator 去管理。

一个完整的实现可以参考这里

这个实现里核心的部分是

  • MemoryBin:提供真实、连续的内存块,由一个个 slot 组成,每个 slot 大小可以设置,默认是 4KB
  • BinManager:基于 buddy allocator 的 bookkeeper,管理的基本单位是 MemoryBin 中的 slot
  • BuddyAllocator:前两个类的一个 facade,透露给外部用户的接口层