(感謝網友 @我的上鋪叫路遙 投稿)
提起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記憶體的時候，
- 我們發現1024K的一半大于70K，然後我們就把1024K的記憶體分成兩半，一半512K。
- 然後我們發現512K的一半仍然大于70K，于是我們再把512K的記憶體再分成兩半，一半是128K。
- 此時，我們發現128K的一半小于70K，于是我們就配置設定為A配置設定128K的記憶體。
後面的，B，C，D都這樣，而釋放記憶體時，則會把相鄰的塊一步一步地合并起來(合并也必需按分裂的逆操作進行合并)。
我們可以看見，這樣的算法，用二叉樹這個資料結構來實作再合适不過了。
我在網上分别找到cloudwu和wuwenbin寫的兩份開源實作和測試用例。實際上後一份是對前一份的精簡和優化，本文打算從後一份入手講解，因為這份實作真正展現了“極簡”二字，追求突破正常的，極緻簡單的設計。網友對其評價甚高，甚至可用作教科書标準實作，看完之後回過頭來看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上如此。