云风的 BLOG: Buddy memory allocation (伙伴内存分配器)

今天吃晚饭的时候想到，我需要一个定制的内存分配器。主要是为了解决共享内存中的字符串池的管理。

这个内存分配器需要是非入侵式的，即不在要分配的内存块中写 cookie 。

而我的需求中，需要被管理的内存块都是很规则的，成 2 的整数次幂的长度。buddy memory allocation 刚好适用。

算法很简单，就是每次把一个正内存块对半切分，一直切到需要的大小分配出去。回收的时候，如果跟它配对的块也是未被使用的，就合并成一个大的块。标准算法下，分配和释放的时间复杂度都是 O(log N) ，N 不会特别大。算法的优点是碎片率很小。而且很容易做成非入侵式的，不用在被管理的内存上保存 cookie 。只需要额外开辟一个二叉树记录内存使用状态即可。

我吃完饭简单 google 了一下，没有立刻找到满足我要求的现成代码。心里估算了一下，C 代码量应该在 200 行以下，我大概可以在 1 小时内写完。所以就毫不犹豫的实现了一份。

然后，自然是开源了。有兴趣的同学可以去 github 拿一份。这样就省得到再需要时再造轮子了。嘿嘿。

btw, 当然这块代码有许多值得优化的地方，比如可以把里面的递归优化成循环回溯。这个算法我读初中时经常写。因为初一那个时候参加信息学奥赛时用的 basic 不支持局部变量，全部变量都是全局的，很难实现递归。所以早期我都不用递归遍历二叉树的，感觉写起来好麻烦。

不过循环回溯遍历树应该是比递归快不少的，因为减少了许多不必要的环境变量压栈，对不支持 closure 的 C 语言尤其是。

这个库用起来很简单。它并不实际管理内存（它不侵入被管理的内存）。你可以设想你另外有一大块内存是由许多最小单位块合起来的。你可以假设最小单位是 1K 。那么用 buddy_new(10) 就可以帮你管理 1024K 内存。

buddy_alloc 可以请求若干个最小单位块，返回一个序号。然后用户可以自己去大内存上索引出来用。用完调用 buddy_free 归还即可。

为了调试方便，我还提供了 buddy_dump 打印二叉树的细节，可以直观的看出那些内存区域未被使用，哪些已经被占用。

ps. 果然，写这篇 blog 花掉的时间比完成这些代码时间更长。代码也如我所料的没有超过 200 行。看看，把东西描述清楚就是比实现一个东西要花更长的时间，这就是项目人多反而做的慢的原因之一吧。

12 月 21 日:

感觉用了递归很不爽, 所以重写了实现, 改用完全二叉树储存, 去掉了递归. 并且(也是主要原因) 减少了内存占用.

如果需要优化的话, 应该加一组 free list , 这个再说。我自己的需求中，时间性能并不太敏感。

12 月 25 日: 楼下有 wuwenbin 提到可以在节点中保存最大连续空闲区域来优化分配过程. 这样代码更短小, 速度也可以快一点. 唯一的缺憾是内存略微消耗的多一点点. 实现在 https://github.com/wuwenbin/buddy2

Comments

如果使用数组而不是链表实现，那么有个限制就是合并策略必须是相邻的元素之间，这仍旧会导致外部碎片。

Posted by: Leo | (35) May 4, 2013 12:24 PM

这里有一个无分支的实现
static inline uint32_t
next_pow_of_2(uint32_t x) {
x -= 1;
x |= x>>1;
x |= x>>2;
x |= x>>4;
x |= x>>8;
x |= x>>16;
return x+1;
}

Posted by: hhh2000 | (34) March 23, 2013 03:56 PM

我已经实现了1字节版本。真是太精妙了，教科书一样，@wuwenbin怎么想到的哦！

Posted by: Scan | (33) February 24, 2013 11:53 PM

@wuwenbin
他的实现里面，如果把longest改为存储log2，则只需要一个字节就可以了，内存占用上和云风你的方案是一样的。

Posted by: Scan | (32) February 24, 2013 11:51 PM

非常不适应结构体向后扩展数据的做法.
struct buddy {
int level;
uint8_t tree[1];
};

Posted by: pthread_t | (31) May 18, 2012 04:57 PM

Posted by: pthread_t | (30) May 18, 2012 04:57 PM

风云，能不能在代码中给点注释啊? 看得吃力。。

Posted by: frankiejun | (29) March 6, 2012 09:30 AM

哈哈，~拿去学习下了，感谢

Posted by: ash | (28) January 4, 2012 10:41 AM

伙伴系统 linux kernel的内存管理算法就是伙伴系统

Posted by: 王杰 | (27) December 31, 2011 03:34 PM

挺不错的！

Posted by: 靠谱号 | (26) December 28, 2011 01:07 PM

为何不用《感悟》里的smallobject_allocator :-)

Posted by: breaker | (25) December 27, 2011 01:54 PM

单栏主题还是蛮好看的。

Posted by: hawkhost | (24) December 27, 2011 12:38 PM

这个东西在acm中就叫线段树

Posted by: Anonymous | (23) December 27, 2011 11:33 AM

树形slab应该比buddy更好吧

Posted by: skywind | (22) December 26, 2011 03:13 AM

@wuwenbin

这样是好一些. 我加到主帖里去.

btw, 前面回复是笔误. 分配的时间复杂度是 log n 不是 n log n

Posted by: Cloud | (21) December 25, 2011 10:13 PM

还有一个简单的优化办法：
不在节点上存储标记，改为存储这个节点表示的可用的连续内存中最长的那一段内存的长度。
维护这个域很简单，最终的实现代码比云风的版本短的多，我的实现仅有131 sloc。
在空间消耗上，可能会比云风的实现耗用更多的内存。因为要在每个节点上存储长度，不像标记那样几个bit就够用。我的实现版本每个节点有4个字节，耗用空间是云风版本的4倍。如果不需要划分太多内存块的话，也可以减少空间占用。
在时间效率上，应该会比云风的实现快的多，同是nlogn的，但是代码少，判断的分支也少，每一次访问某个节点可以立刻决定分配左节点还是右节点，不需要回溯。
我的实现代码在：https://github.com/wuwenbin/buddy2

Posted by: wuwenbin | (20) December 25, 2011 03:58 PM

google有什么好，一会儿无法搜索，一会儿又可以，真的是气死人。不知他们公司在搞什么鬼。

Posted by: asfrewa | (19) December 22, 2011 09:39 PM

风云原来如此呀呃

Posted by: QQ分组 | (18) December 22, 2011 08:49 PM

想想是举手之劳的优化,就不偷懒了. 加上. 现在不会退化到 O(n) 的时间复杂度了.

Posted by: Cloud | (17) December 22, 2011 01:39 AM

@Tiger Soldier

可以通过设置标记把整个子树标记起来(加一个颜色标记), 减少时间复杂度. 这是个优化, 我没有做. 有空可以加上, 把复杂度减到 O(logN) 左右.

另外可以把闲置空间串起来, 加快分配.

Posted by: Cloud | (16) December 22, 2011 01:22 AM

分配的复杂度是O(logN)的么？看了一下代码，感觉在最坏情况下（所有申请都是请求最小单元，也就是所有叶子都被标记为USED，分配一个最小单元需要遍历整棵树，复杂度是O(N)的。