伙伴分配器的一个极简实现

伙伴分配器的一个极简实现

(感谢网友 @我的上铺叫路遥 投稿)

提起buddy system相信很多人不会陌生,它是一种经典的内存分配算法,大名鼎鼎的Linux底层的内存管理用的就是它。这里不探讨内核这么复杂实现,而仅仅是将该算法抽象提取出来,同时给出一份及其简洁的源码实现,以便定制扩展。

伙伴分配的实质就是一种特殊的“分离适配”,即将内存按2的幂进行划分,相当于分离出若干个块大小一致的空闲链表,搜索该链表并给出同需求最佳匹配的大小。其优点是快速搜索合并(O(logN)时间复杂度)以及低外部碎片(最佳适配best-fit);其缺点是内部碎片,因为按2的幂划分块,如果碰上66单位大小,那么必须划分128单位大小的块。但若需求本身就按2的幂分配,比如可以先分配若干个内存池,在其基础上进一步细分就很有吸引力了。

可以在维基百科上找到该算法的描述,大体如是:

分配内存:

1.寻找大小合适的内存块(大于等于所需大小并且最接近2的幂,比如需要27,实际分配32)

1.如果找到了,分配给应用程序。
2.如果没找到,分出合适的内存块。

1.对半分离出高于所需大小的空闲内存块
2.如果分到最低限度,分配这个大小。
3.回溯到步骤1(寻找合适大小的块)
4.重复该步骤直到一个合适的块

释放内存:

1.释放该内存块

1.寻找相邻的块,看其是否释放了。
2.如果相邻块也释放了,合并这两个块,重复上述步骤直到遇上未释放的相邻块,或者达到最高上限(即所有内存都释放了)。

上面这段文字对你来说可能看起来很费劲,没事,我们看个内存分配和释放的示意图你就知道了:

上图中,首先我们假设我们一个内存块有1024K,当我们需要给A分配70K内存的时候,

  1. 我们发现1024K的一半大于70K,然后我们就把1024K的内存分成两半,一半512K。
  2. 然后我们发现512K的一半仍然大于70K,于是我们再把512K的内存再分成两半,一半是128K。
  3. 此时,我们发现128K的一半小于70K,于是我们就分配为A分配128K的内存。

后面的,B,C,D都这样,而释放内存时,则会把相邻的块一步一步地合并起来(合并也必需按分裂的逆操作进行合并)。

我们可以看见,这样的算法,用二叉树这个数据结构来实现再合适不过了。

我在网上分别找到cloudwuwuwenbin写的两份开源实现和测试用例。实际上后一份是对前一份的精简和优化,本文打算从后一份入手讲解,因为这份实现真正体现了“极简”二字,追求突破常规的,极致简单的设计。网友对其评价甚高,甚至可用作教科书标准实现,看完之后回过头来看cloudwu的代码就容易理解了。

分配器的整体思想是,通过一个数组形式的完全二叉树来监控管理内存,二叉树的节点用于标记相应内存块的使用状态,高层节点对应大的块,低层节点对应小的块,在分配和释放中我们就通过这些节点的标记属性来进行块的分离合并。如图所示,假设总大小为16单位的内存,我们就建立一个深度为5的满二叉树,根节点从数组下标[0]开始,监控大小16的块;它的左右孩子节点下标[1~2],监控大小8的块;第三层节点下标[3~6]监控大小4的块……依此类推。

在分配阶段,首先要搜索大小适配的块,假设第一次分配3,转换成2的幂是4,我们先要对整个内存进行对半切割,从16切割到4需要两步,那么从下标[0]节点开始深度搜索到下标[3]的节点并将其标记为已分配。第二次再分配3那么就标记下标[4]的节点。第三次分配6,即大小为8,那么搜索下标[2]的节点,因为下标[1]所对应的块被下标[3~4]占用了。

在释放阶段,我们依次释放上述第一次和第二次分配的块,即先释放[3]再释放[4],当释放下标[4]节点后,我们发现之前释放的[3]是相邻的,于是我们立马将这两个节点进行合并,这样一来下次分配大小8的时候,我们就可以搜索到下标[1]适配了。若进一步释放下标[2],同[1]合并后整个内存就回归到初始状态。

还是看一下源码实现吧,首先是伙伴分配器的数据结构:

struct buddy2 {
  unsigned size;
  unsigned longest[1];
};

这里的成员size表明管理内存的总单元数目(测试用例中是32),成员longest就是二叉树的节点标记,表明所对应的内存块的空闲单位,在下文中会分析这是整个算法中最精妙的设计。此处数组大小为1表明这是可以向后扩展的(注:在GCC环境下你可以写成longest[0],不占用空间,这里是出于可移植性考虑),我们在分配器初始化的buddy2_new可以看到这种用法。

struct buddy2* buddy2_new( int size ) {
  struct buddy2* self;
  unsigned node_size;
  int i;

  if (size < 1 || !IS_POWER_OF_2(size))
    return NULL;

  self = (struct buddy2*)ALLOC( 2 * size * sizeof(unsigned));
  self->size = size;
  node_size = size * 2;

  for (i = 0; i < 2 * size - 1; ++i) {
    if (IS_POWER_OF_2(i+1))
      node_size /= 2;
    self->longest[i] = node_size;
  }
  return self;
}

整个分配器的大小就是满二叉树节点数目,即所需管理内存单元数目的2倍。一个节点对应4个字节,longest记录了节点所对应的的内存块大小。

内存分配的alloc中,入参是分配器指针和需要分配的大小,返回值是内存块索引。alloc函数首先将size调整到2的幂大小,并检查是否超过最大限度。然后进行适配搜索,深度优先遍历,当找到对应节点后,将其longest标记为0,即分离适配的块出来,并转换为内存块索引offset返回,依据二叉树排列序号,比如内存总体大小32,我们找到节点下标[8],内存块对应大小是4,则offset = (8+1)*4-32 = 4,那么分配内存块就从索引4开始往后4个单位。

int buddy2_alloc(struct buddy2* self, int size) {
  unsigned index = 0;
  unsigned node_size;
  unsigned offset = 0;

  if (self==NULL)
    return -1;

  if (size <= 0)
    size = 1;
  else if (!IS_POWER_OF_2(size))
    size = fixsize(size);

  if (self->longest[index] < size)
    return -1;

  for(node_size = self->size; node_size != size; node_size /= 2 ) {
    if (self->longest[LEFT_LEAF(index)] >= size)
      index = LEFT_LEAF(index);
    else
      index = RIGHT_LEAF(index);
  }

  self->longest[index] = 0;
  offset = (index + 1) * node_size - self->size;

  while (index) {
    index = PARENT(index);
    self->longest[index] =
      MAX(self->longest[LEFT_LEAF(index)], self->longest[RIGHT_LEAF(index)]);
  }

  return offset;
}

在函数返回之前需要回溯,因为小块内存被占用,大块就不能分配了,比如下标[8]标记为0分离出来,那么其父节点下标[0]、[1]、[3]也需要相应大小的分离。将它们的longest进行折扣计算,取左右子树较大值,下标[3]取4,下标[1]取8,下标[0]取16,表明其对应的最大空闲值。

在内存释放的free接口,我们只要传入之前分配的内存地址索引,并确保它是有效值。之后就跟alloc做反向回溯,从最后的节点开始一直往上找到longest为0的节点,即当初分配块所适配的大小和位置。我们将longest恢复到原来满状态的值。继续向上回溯,检查是否存在合并的块,依据就是左右子树longest的值相加是否等于原空闲块满状态的大小,如果能够合并,就将父节点longest标记为相加的和(多么简单!)。

void buddy2_free(struct buddy2* self, int offset) {
  unsigned node_size, index = 0;
  unsigned left_longest, right_longest;

  assert(self && offset >= 0 && offset < size);

  node_size = 1;
  index = offset + self->size - 1;

  for (; self->longest[index] ; index = PARENT(index)) {
    node_size *= 2;
    if (index == 0)
      return;
  }

  self->longest[index] = node_size;

  while (index) {
    index = PARENT(index);
    node_size *= 2;

    left_longest = self->longest[LEFT_LEAF(index)];
    right_longest = self->longest[RIGHT_LEAF(index)];

    if (left_longest + right_longest == node_size)
      self->longest[index] = node_size;
    else
      self->longest[index] = MAX(left_longest, right_longest);
  }
}

上面两个成对alloc/free接口的时间复杂度都是O(logN),保证了程序运行性能。然而这段程序设计的独特之处就在于使用加权来标记内存空闲状态,而不是一般的有限状态机,实际上longest既可以表示权重又可以表示状态,状态机就毫无必要了,所谓“少即是多”嘛!反观cloudwu的实现,将节点标记为UNUSED/USED/SPLIT/FULL四个状态机,反而会带来额外的条件判断和管理实现,而且还不如数值那样精确。从逻辑流程上看,wuwenbin的实现简洁明了如同教科书一般,特别是左右子树的走向,内存块的分离合并,块索引到节点下标的转换都是一步到位,不像cloudwu充斥了大量二叉树的深度和长度的间接计算,让代码变得晦涩难读,这些都是longest的功劳。一个“极简”的设计往往在于你想不到的突破常规思维的地方。

这份代码唯一的缺陷就是longest的大小是4字节,内存消耗大。但cloudwu的博客上有人提议用logN来保存值,这样就能实现uint8_t大小了,看,又是一个“极简”的设计!

说实话,很难在网上找到比这更简约更优雅的buddy system实现了——至少在Google上如此。

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

好烂啊有点差凑合看看还不错很精彩 (29 人打了分,平均分: 3.79 )
Loading...

伙伴分配器的一个极简实现》的相关评论

  1. 依据二叉树排列序号,比如内存总体大小32,我们找到节点下标[8],内存块对应大小是4,则offset = (8+1)*4-32 = 4,那么分配内存块就从索引4开始往后4个单位。

    这点看不明白,能否再解释一下,这里说的内存总大小32,根据上面的所说是要建立深度为6的二叉树吧

  2. @noob
    该二叉树是数组,从下标[0]开始,每level层的第一个左子树下标是2^level-1。
    假设总大小为16,31个节点,5层。现在需要将下标转换成索引offset(即alloc出来的地址),有如下映射关系:[index]->offset
    size = 16:[0]->0
    size = 8:[1]->0;[2]->8
    size = 4:[3]->0;[4]->4;[5]->8;[6]->12
    size = 2:略
    size = 1:略
    可建立如下公式:offset = (index + 1) * size – 16,直观上看图就可理解。

  3. @noob
    对于满二叉树而言,因为每level的第一左子树的下标为2^level-1,所以如果我们得到[index]节点的所在level,那么offset的计算可以归结为(index-2^level+1) * node_size = (index+1)*node_size – node_size*2^level。其中size的计算为2^(max_depth-level),所以node_size * 2^level = 2^max_depth = size。
    综上所述,可得公式offset=(index+1)*node_size – size。
    PS:式中索引的下标均从0开始,size为内存总大小,node_size为内存块对应大小。

  4. 谢谢 @Leo和@Terence 的解释, @Terence说的”其中size的计算为2^(max_depth-level)” 应该是 “其中node_size的计算为2^(max_depth-level)”吧

  5. 例子中的内存申请和释放示意图中,有个错误:
    当申请d时,返回的offset应为0(即为上一步a释放的空间),而不是在B后面的空间。

  6. 明白了 这只是分配器用的数据结构
    实际的内存池还需要另外分配
    事先先定义好内存池分配的最小单位结构 比如1024 byte
    然后用alloc返回的offset与之对应
    是这样吗

  7. @Tw
    赞同,如果按照作者这个算法,总是会选择左子树管理的内存区域,即使在右子树中有一个较小但同样满足条件的区块也会选择左子树。
    这个是buddy2_alloc函数中17-22行的for循环决定的。
    我觉得图中的分配方式更优,应该尽量使用更小的内存块而不是把一个大块拆小,只要把for循环的内容改一下即可:当左子树管理的大小和右子树管理的大小都大于所要分配的size时,选两者之间较小的一个。
    欢迎讨论和指正~

  8. 即使是第一次了解伙伴分配器,也一下子就理解了,很好的文章。Markwenss 提出小块优先原则后,方法是否还有改进的空间,我有一个想法。
    例如在self->size=32的情况下,由于释放造成的碎片化,很可能出现在前16字节中有一块连续的8字节被申请,而后16字节中却有一块连续的4字节被申请,那么此时如果要再申请一块四字节的内存,最好的结果是遍历到后16字节里的那处4字节空缺处,这样的结果是,整个内存空间中剩下两片八字节大小的“叶子”,而如果使用Markwenss的选较小方法,结果会是,整个空间中剩下一片八字节的“叶子”和两片不连续的四字节大小的“叶子”。
    如果想针对这种情况,进一步地让小块优先分配。我的感觉是需要修改两处:
    1. 每个节点的longest需要确实反映子叶上的空间情况,所以不适用取最大的折扣计算,改为子叶一级的相加运算。(会带来性能的下降吗?会,虽然比较运算和加法运算其实性能是一样的,但是会增加一个CPU通用寄存器的使用,这点需要论证,因为在现代CPU中cache已不再那么紧张,而且有的CPU应该允许直接将相加的结果作为右值;)
    2. 在for循环遍历时,如果申请大小为a, 遍历到某两片节点的空间情况分别为m和n, 那么使用m%(a*2), n%(a*2), 比较两个余数,取较小的那片叶子。 典型的案例是: 当申请量是两个字节,一开始遍历到index是1和2,当时的m=12, n=14 ,因为14%4 > 12%4 , 所以选择index=2 的那条branch更优,如果m和n的余数相同,则再使用Markwenss的方法取优;当然如果m=n,就在一开始使用取左策略. (这一点会带来低于原作性能的毛病,但是考虑到碎片化的问题,这样一点性能为代价应该是很值得考虑的)
    PS:释放空间的部分,还没有列出。

    另外,在释放空间free的update节点状态部分,因为分叉的节点有且仅有两片”叶子”,所以在更新节点时,不明白为什么要先找到parent,再找left,right ;为什么不直接看index是否为奇偶数,从而立即得到和自己相邻那片”叶子”的索引? 所以觉得这部分本可以更简单,但是想不通为什么不这样做。

    我觉得继续优化会是一件很有趣的事情,希望进一步讨论和指正。

  9. 是不是图文不太对应呢? 总内存是16字节, 完全二叉树节点个数是32个, 文中貌似混淆了.

    根据node index计算memory offset的计算公式从图中很容易理解:
    [8]节点占用2字节, 与[7],[9],[10],[11],[12]节点共同占据了16字节, 所以[8]节点的内存偏移就是16字节的第2字节位置开始的2字节.

    计算公式推导在3楼很清晰了.

  10. @Kan ,我认为修改longest为两个子节点longest直接相加是不行的,原因是不能保证子节点一定有足够的“连续”空间。

    比如说,左子节点的最左部有2个空闲单位,右子节点最右部有2个空闲单位,中间是被占用的,相加出来为4,但是没有办法分配出4个连续的空闲单位。单凭一个longest统计无法知道子节点空闲区域是在左部还是右部,在分配时无法通过longest知道子节点是否有足够的连续空间,除非一个一个便历,这样会导致时间复杂度变成O(n)。如果不用求和的话,另外一个余数判断也就用不上了。

    至于Free的部分,可以这么改,而且不用if找相邻叶子也就是将(index+1)^1-1就可以了。。我写的时候一直在纠结边界条件,没想那么多。。而且这么改不见得更好理解,对性能改进也不大,算LEFT_LEAF和RIGHT_LEAF在X86只需要一条LEA指令就够了。。

    然后,关于分配时怎么选更优,我觉得像 @markwenssh 的贪心法可以,但它存在的问题 @Kan 也说了。我觉得随机法估计也能达到不错的效果,随机法应该不会太容易碰到最坏情况。。单纯的longest实在是信息不足,没有其他信息的话,难以做到更优的决策了。。

  11. @markwenssh

    markwenssh :@Tw 赞同,如果按照作者这个算法,总是会选择左子树管理的内存区域,即使在右子树中有一个较小但同样满足条件的区块也会选择左子树。这个是buddy2_alloc函数中17-22行的for循环决定的。我觉得图中的分配方式更优,应该尽量使用更小的内存块而不是把一个大块拆小,只要把for循环的内容改一下即可:当左子树管理的大小和右子树管理的大小都大于所要分配的size时,选两者之间较小的一个。欢迎讨论和指正~

    个人认为优先选择小块是个不错的改进!

  12. @wuwenbin
    没有作者对longest的理解深刻。所以longest是一个必要条件,赞同。除非增加一个成员,但管理的空间将*2.。
    作为最精简伙伴系统,小块优先确实偏题了。
    性能部分只是自己有一点confuse,”抑或”和LEA,恩。。确实优化的空间已经不大。
    感谢作者及时的回复和分享。

  13. 有个问题,如果在左子树的最右边有一个16的空闲块,右子树的最左边有16的空闲块,这两个块是没办法合并成32的块的。

  14. @aaaaaaaa
    我也有过同样的质疑。如果有一个用户故意编写一个频繁申请但只是部分释放的程序(在程序全身而退之前有点像mem_leak),然后进行压力测试。就很容易出现你所说的情况。最坏的可能是,50%的内存空闲,但由于每个碎片都不在一个branch里,导致申请不到较大的内存。而这个疑问我觉得比较合适的解释有两个:
    1. 如果要避免这种情况发生,势必会在申请时增加相当大的负担,因为需要忽视所有节点带来的方便,而不得不采用遍历每一个颗粒,比如总大小32,你申请16,原来只有两种可能,现在变成了17种可能。而且前一次的申请结果与后一次的申请也会被独立开来,没有联系,带来的性能损失是难以想象的。所以,这么做会让伙伴系统,这个被全世界所有天才认可和历经考验的策略,失去它原本的优势。伙伴系统的诞生,估计主要就是为了解决性能问题。而且,说句实话,应用层也要多少负些责任,那种类似mem_leak的程序如果存在,只能说明应用程序的作者缺乏良好的编程习惯。
    2. 再换一种角度,假设出现上面出现的极端情况时,反过来想,在这时,释放任何一块内存(无论释放哪一个!),都会立即使得有申请需求活过来,此时发生revive的概率是100%,所以从概率角度看,@aaaaaaaa反应的问题其实也没那么严重呢。再观察一下linux的伙伴系统源码和这些年历经的那些patch(linux是全世界所有天才程序员的杰作,但它的伙伴系统比较复杂),你会发现它在申请不到的时候做了一些等待处理,比如尝试回收一些不用的到swap分区,从而让出内存,或者尝试等待某个revive的机会,毕竟这时候碎片和并在一起的概率很大。

    在这里顺便补充,因为内存分配器是一个调用非常非常频繁的程序,一点性能的提高就能带来很大的收益,而linux的slab又比较晦涩,所以作者才会考虑最精简的longest让大家很容易读懂,但是正是因为这个longest,导致这段程序不可能达到我们想要的优化。所以如果必须用longest,这个程序除了再优化一点性能,别的应该没有修改的空间了。但是如果不用longest呢?比如它的缺点也是有的,管理空间大,而且难以实现好的碎片优化。如果是几个G的内存怎么办,是否考虑只用一个宽度是8字节或者16字节管理单元,每个比特代表每一个内存颗粒(linux里是一个page)。然后通过移位,考虑直接使用汇编语言,先二分法,再整除等手段快速寻找到合适的二叉树节点?可能要走起新一篇文章了。。。

  15. @aaaaaaaa
    这种情况多余了,因为分配的时候总是从左子树开始的,因此想要分配32的内存块那就是右子树啦(因为现在右子树的左子树看起来16的内存块都还没有被分配出去呢)。

  16. fixsize函数把一个size align到2的幂大小,有个小问题,如果输入是2返回时4,实际应该是2,在移位之前应该size–

  17. 然后我们发现512K的一半仍然大于70K,于是我们再把512K的内存再分成两半,一半是128K。
    是我理解错了,还是写错了呢?应该还有个256的过程吧?

  18. 这离实际的buddy的距离还是比较远的。比如对于16个单位的buddy,只能提供2个8单位的内存分配,并且不能扩展内存。linux实现的buddy是用双向链表实现的

  19. ojl :
    然后我们发现512K的一半仍然大于70K,于是我们再把512K的内存再分成两半,一半是128K。
    是我理解错了,还是写错了呢?应该还有个256的过程吧?

    ddddd

  20. “比如内存总体大小32,我们找到节点下标[8],内存块对应大小是4,则offset = (8+1)*4-32 = 4,那么分配内存块就从索引4开始往后4个单位。”前面的图只能分配16个内存块大小么不是,32个节点有一个是给size用的,其余31个下标表示节点索引,值表示能分配的块数,为什么不直接返回节点下标呢?

  21. 求解释,怎么管理内存所需要的空间比实际内存大那么多呢;如果要管理一个2G或更大的内存,总共岂不是需要好几G内存空间,还是我理解错了?

  22. 印象中glibc是为每一个2^i大小的块单独分配一页内存,这样的话就省去了不同大小的块在同一块内存分配所导致的split/merge操作了(复杂度降低到O1),所有的页面通过一个哈希表来维护。

  23. fixsize的移位操作实现得挺精妙的!
    先把低位全变成1,然后+1进位,就得到结果。

    而把低位变成1的过程,又通过先右移位,把次高位和高位都保证为1;
    然后移两位,这样就有2*2, 最高4位为1。
    依此类推。

  24. buddy2_free中offset需要确保它是有效值,那12,13行
    if (index == 0)
    return;
    是多余的,不可能命中的

  25. 皓哥:恰好我写了个关于伙伴系统的内存分配动态演示图,直观地解释了伙伴系统,免费下载地址:http://download.csdn.net/download/justme0/6838083
    欢迎指教。

  26. 大家好,来的晚了,在buddy2_new函数中,node_size = size * 2;是没有必要的,大家觉得呢 ?

  27. @oyjh
    如果可以用math库的话
    unsigned fixsize(unsigned x) {
    if (IS_POWER_OF_2(x))
    return x;
    else
    return 1lu << unsigned(ceil(log(x) / log(2)));
    }

  28. 没有别人吐槽buddy2_free第五行的那个size没法编译吗。。。应该是self->size吧。

  29. @lzy
    实际的linux系统采用的buddy算法最小分配1M的内存,1G的内存最多被拆分成1024块,需要2M的管理内存

  30. Kan :
    例如在self->size=32的情况下,由于释放造成的碎片化,很可能出现在前16字节中有一块连续的8字节被申请,而后16字节中却有一块连续的4字节被申请,那么此时如果要再申请一块四字节的内存,最好的结果是遍历到后16字节里的那处4字节空缺处,这样的结果是,整个内存空间中剩下两片八字节大小的“叶子”,而如果使用Markwenss的选较小方法,结果会是,整个空间中剩下一片八字节的“叶子”和两片不连续的四字节大小的“叶子”。

    写反了吧?按@Markwenss的方法,才是“遍历到后16字节里的那处4字节空缺处,这样的结果是,整个内存空间中剩下两片八字节大小的叶子”。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注