Vi Linux内存 之 伙伴系统（一）

    Buddy System，伙伴系统，linux中用来分配、释放内存页块的经典算法。数据结构struct zone中有个free_area数组。存放着本zone的空闲页块链表，注意这是一组链表，而不是一个链表。我们常常需要按“块”分配连续多个内存页面，因此需要用链表来保存长度为1、2、4、8、…、直至2^MAX_ORDER-1的页块。通常MAX_ORDER为11，则free_area中一共保存了11个链表。最大可分配的内存块是1024个页面，共4MB的内存空间。

    那么什么是伙伴呢？如果同一个链表中的两个页块满足下面这三个条件，我们就称这两个页块为伙伴：

1)  两个块的大小相同，假设为b。

2)  两个块的物理地址连续。

3) 伙伴中第一个块的起始物理地址是2*b*PAGE_SIZE的整数倍。即第0块和第1块是伙伴，第2块和第3块是伙伴，但是第1块和第2块不是伙伴。这样规定的目的是确保一对伙伴中的两个块可以合并成更高一级的大块。

    分配   

    ULK中通过一个例子介绍了伙伴系统的分配流程。假设我们需要申请2⁸（256）个连续的页，算法首先查找2⁸链表，如果没有找到，继续查找2⁹（512）链表，如果查找成功，分配其中的256个页面，将剩余的256个页面作为一块插入到2⁸链表。如果在2⁹链表中查找仍然失败，内核继续查找下一个更大块的链表2¹⁰（1024），如果查找成功，分配其中的256个页面，将剩余768个页面中的高地址区的512个页面作为一块插入到2⁹链表，低地址区的256个页面作为一块插入到2⁸链表。如果在2¹⁰链表中查找仍然失败，则放弃查找并报错。

            

    释放

    页块释放是分配的逆过程。释放一个页块时，先在其对应的free_area链表中查找是否有伙伴存在，如果没有伙伴，直接将页块插入链表头。如果有，则将其从链表上摘下，合并成一个更大的块，然后继续查找合并后的块在更大一级链表中是否有伙伴存在，直至不能合并或者已经合并至最大的块为止。

    从上面的释放过程可知，伙伴中两个页块的状态只可能有2种情况：都被分配出去，或是伙伴中的一个被分配出去。如果都没有被分配出去，那么必然会合并成更大的页块。

    算法

    如果是老版本的内核，数据结构free_area中还有一个map成员。每个order的链表都对应一个位图，位图中的每一个比特位对应一对伙伴的状态。位图的设计比较复杂，追求简洁的linux内核已经抛弃了位图，取而代之的是巧妙的位运算。

    下面介绍新版本kernel中伙伴系统的算法：

    假设物理内存一组页面的PFN为0、1、2、3、4、5、……。

n         如果要把这组页面插入order为0的链表，那么0和1是伙伴，2和3是伙伴，……。

n         如果要把这组页面插入order为1的链表，那么[0-1]与[2-3]是伙伴，[4-5]与[6-7]是伙伴，……。

n         如果要把这组页面插入order为2的链表，那么[0-3]与[4-7]是伙伴，[8-11]与[12-15]是伙伴，……。

n         如果要把这组页面插入order为3的链表，那么[0-7]与[8-15]是伙伴，[16-23]与[24-31]是伙伴，……。

    以此类推，如果在order级别为O的链表中，给出页块B1，那么其伙伴B2的计算公式为：

    公式一：B2 = B1 ^ (1 << O)

    例如：B1=8，O=1，那么B2=8^(1<<1)=10，即[8-9]与[10-11]是伙伴。

    任意的一对伙伴B，如果合并成order+1级链表的节点，我们称合并后的节点是这对伙伴的父节点P，那么P的计算公式为：

    公式二：P = B & ~(1 << O)

    例如：B=10，O=1，那么其父节点P=10&~(1<< 1)=8，即[8-9]与[10-11]这对伙伴合并后的父节点为[8-11]。

    公式中的B1、B2、P分别代表页块索引，一个页块的索引是其第一个页面的页号（PFN）。

    公式的原理其实就是低order位屏蔽。比如order为3，那么伙伴[0-7]与[8-15]的页号只有第四位（1<<3）是不同的，低三位是相同的。所以公式一只是简单对页块索引的1<位做异或操作而已。同理，合并伙伴时相当于又左移了一位，这就要求原1<位也要清0，这也就是公式二完成的动作。比如order为3的伙伴[0-7]与[8-15]要合并成上一级order为4的链表，那么需要将第四位（1<<3）清0，这样伙伴中无论页块索引是0还是8，清0后均为0，也就得到了order为4的页块[0-15]的索引。由于是低order位屏蔽，所以页块索引一定是order位对齐的，即是2^order的整数倍。

    通过上面的公式不难看出，如果order的最大取值为MAX_ORDER-1，那么参与运算的最高位是第MAX_ORDER位，与更高的位无关。这样一来，我们就可以进一步简化运算，将与公式无关的高位也屏蔽掉。由于参与运算的是[0-MAX_ORDER]位，表示的数值范围最大到2^MAX_ORDER-1（即（1 << MAX_ORDER）–1），所以公式运算前，可以把页块索引，也就是页块第一个页面的页号和最大值2^MAX_ORDER-1做与操作。比如最大的order为10，运算之前就可以把页块索引与上0x7FF。

    Linux内核巧妙的通过上面的公式替代了原来复杂的位图运算，即节省了位图占用的空间，又简化了算法，提高了效率。