伙伴分配器的一個極簡實(shí)現(xiàn)
提起buddy system相信很多人不會陌生，它是一種經(jīng)典的內(nèi)存分配算法，大名鼎鼎的Linux底層的內(nèi)存管理用的就是它。這里不探討內(nèi)核這么復(fù)雜實(shí)現(xiàn)，而僅僅是將該算法抽象提取出來，同時給出一份及其簡潔的源碼實(shí)現(xiàn)，以便定制擴(kuò)展。
伙伴分配的實(shí)質(zhì)就是一種特殊的“分離適配”，即將內(nèi)存按2的冪進(jìn)行劃分，相當(dāng)于分離出若干個塊大小一致的空閑鏈 表，搜索該鏈表并給出同需求最佳匹配的大小。其優(yōu)點(diǎn)是快速搜索合并（O(logN)時間復(fù)雜度）以及低外部碎片（最佳適配best-fit）；其缺點(diǎn)是內(nèi) 部碎片，因?yàn)榘?的冪劃分塊，如果碰上66單位大小，那么必須劃分128單位大小的塊。但若需求本身就按2的冪分配，比如可以先分配若干個內(nèi)存池，在其基 礎(chǔ)上進(jìn)一步細(xì)分就很有吸引力了。
可以在維基百科上找到該算法的描述，大體如是：
分配內(nèi)存：
1.尋找大小合適的內(nèi)存塊（大于等于所需大小并且最接近2的冪，比如需要27，實(shí)際分配32）
- .如果找到了，分配給應(yīng)用程序。
- 如果沒找到，分出合適的內(nèi)存塊。
- .對半分離出高于所需大小的空閑內(nèi)存塊
- .如果分到最低限度，分配這個大小。
- 回溯到步驟1（尋找合適大小的塊）
- .重復(fù)該步驟直到一個合適的塊
釋放內(nèi)存：
1.釋放該內(nèi)存塊
- 尋找相鄰的塊，看其是否釋放了。
- 如果相鄰塊也釋放了，合并這兩個塊，重復(fù)上述步驟直到遇上未釋放的相鄰塊，或者達(dá)到最高上限（即所有內(nèi)存都釋放了）。
上面這段文字對你來說可能看起來很費(fèi)勁，沒事，我們看個內(nèi)存分配和釋放的示意圖你就知道了：
上圖中，首先我們假設(shè)我們一個內(nèi)存塊有1024K，當(dāng)我們需要給A分配70K內(nèi)存的時候，
- 我們發(fā)現(xiàn)1024K的一半大于70K，然后我們就把1024K的內(nèi)存分成兩半，一半512K。
- 然后我們發(fā)現(xiàn)512K的一半仍然大于70K，于是我們再把512K的內(nèi)存再分成兩半，一半是128K。
- 此時，我們發(fā)現(xiàn)128K的一半小于70K，于是我們就分配為A分配128K的內(nèi)存。
后面的，B，C，D都這樣，而釋放內(nèi)存時，則會把相鄰的塊一步一步地合并起來（合并也必需按分裂的逆操作進(jìn)行合并）。
我們可以看見，這樣的算法，用二叉樹這個數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)再合適不過了。
我在網(wǎng)上分別找到cloudwu和wuwenbin寫的兩份開源實(shí)現(xiàn)和測試用例。實(shí)際上后一份是對前一份的精簡和優(yōu)化，本文打算從后一份入手講解，因?yàn)檫@份實(shí)現(xiàn)真正體現(xiàn)了“極簡”二字，追求突破常規(guī)的，極致簡單的設(shè)計(jì)。網(wǎng)友對其評價甚高，甚至可用作教科書標(biāo)準(zhǔn)實(shí)現(xiàn)，看完之后回過頭來看cloudwu的代碼就容易理解了。
分配器的整體思想是，通過一個數(shù)組形式的完全二叉樹來監(jiān)控管理內(nèi)存，二叉樹的節(jié)點(diǎn)用于標(biāo)記相應(yīng)內(nèi)存塊的使用狀態(tài)，高層節(jié)點(diǎn)對應(yīng)大的塊，低層節(jié)點(diǎn)對應(yīng) 小的塊，在分配和釋放中我們就通過這些節(jié)點(diǎn)的標(biāo)記屬性來進(jìn)行塊的分離合并。如圖所示，假設(shè)總大小為16單位的內(nèi)存，我們就建立一個深度為5的滿二叉樹，根 節(jié)點(diǎn)從數(shù)組下標(biāo)[0]開始，監(jiān)控大小16的塊；它的左右孩子節(jié)點(diǎn)下標(biāo)[1~2]，監(jiān)控大小8的塊；第三層節(jié)點(diǎn)下標(biāo)[3~6]監(jiān)控大小4的塊……依此類推。
在分配階段，首先要搜索大小適配的塊，假設(shè)第一次分配3，轉(zhuǎn)換成2的冪是4，我們先要對整個內(nèi)存進(jìn)行對半切割，從16切割到4需要兩步，那么從下標(biāo) [0]節(jié)點(diǎn)開始深度搜索到下標(biāo)[3]的節(jié)點(diǎn)并將其標(biāo)記為已分配。第二次再分配3那么就標(biāo)記下標(biāo)[4]的節(jié)點(diǎn)。第三次分配6，即大小為8，那么搜索下標(biāo) [2]的節(jié)點(diǎn)，因?yàn)橄聵?biāo)[1]所對應(yīng)的塊被下標(biāo)[3~4]占用了。
在釋放階段，我們依次釋放上述第一次和第二次分配的塊，即先釋放[3]再釋放[4]，當(dāng)釋放下標(biāo)[4]節(jié)點(diǎn)后，我們發(fā)現(xiàn)之前釋放的[3]是相鄰的， 于是我們立馬將這兩個節(jié)點(diǎn)進(jìn)行合并，這樣一來下次分配大小8的時候，我們就可以搜索到下標(biāo)[1]適配了。若進(jìn)一步釋放下標(biāo)[2]，同[1]合并后整個內(nèi)存 就回歸到初始狀態(tài)。
還是看一下源碼實(shí)現(xiàn)吧，首先是伙伴分配器的數(shù)據(jù)結(jié)構(gòu)：
- struct buddy2 {
- unsigned size;
- unsigned longest[1];
- };
這里的成員size表明管理內(nèi)存的總單元數(shù)目（測試用例中是32），成員longest就是二叉樹的節(jié)點(diǎn)標(biāo)記，表明所對應(yīng)的內(nèi)存塊的空閑單位，在下文中會分析這是整個算法中最精妙的設(shè)計(jì)。此處數(shù)組大小為1表明這是可以向后擴(kuò)展的（注：在GCC環(huán)境下你可以寫成longest[0]，不占用空間，這里是出于可移植性考慮），我們在分配器初始化的buddy2_new可以看到這種用法。
- truct 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;
- }
整個分配器的大小就是滿二叉樹節(jié)點(diǎn)數(shù)目，即所需管理內(nèi)存單元數(shù)目的2倍。一個節(jié)點(diǎn)對應(yīng)4個字節(jié)，longest記錄了節(jié)點(diǎn)所對應(yīng)的的內(nèi)存塊大小。
內(nèi)存分配的alloc中，入?yún)⑹欠峙淦髦羔樅托枰峙涞拇笮。祷刂凳莾?nèi)存塊索引。alloc函數(shù)首先將size調(diào)整到2的冪大小，并檢查是否超過最大限度。然后進(jìn)行適配搜索，深度優(yōu)先遍歷，當(dāng)找到對應(yīng)節(jié)點(diǎn)后，將其longest標(biāo)記為0，即分離適配的塊出來，并轉(zhuǎn)換為內(nèi)存塊索引offset返回，依據(jù)二叉樹排列序號，比如內(nèi)存總體大小32，我們找到節(jié)點(diǎn)下標(biāo)[8]，內(nèi)存塊對應(yīng)大小是4，則offset = (8+1)*4-32 = 4，那么分配內(nèi)存塊就從索引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;
- }
在函數(shù)返回之前需要回溯，因?yàn)樾K內(nèi)存被占用，大塊就不能分配了，比如下標(biāo)[8]標(biāo)記為0分離出來，那么其父節(jié)點(diǎn)下標(biāo)[0]、[1]、[3]也需要相應(yīng)大小的分離。將它們的longest進(jìn)行折扣計(jì)算，取左右子樹較大值，下標(biāo)[3]取4，下標(biāo)[1]取8，下標(biāo)[0]取16，表明其對應(yīng)的最大空閑值。
在內(nèi)存釋放的free接口，我們只要傳入之前分配的內(nèi)存地址索引，并確保它是有效值。之后就跟alloc做反向回溯，從最后的節(jié)點(diǎn)開始一直往上找到longest為0的節(jié)點(diǎn)，即當(dāng)初分配塊所適配的大小和位置。我們將longest恢復(fù)到原來滿狀態(tài)的值。繼續(xù)向上回溯，檢查是否存在合并的塊，依據(jù)就是左右子樹longest的值相加是否等于原空閑塊滿狀態(tài)的大小，如果能夠合并，就將父節(jié)點(diǎn)longest標(biāo)記為相加的和（多么簡單！）。
- 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接口的時間復(fù)雜度都是O(logN)，保證了程序運(yùn)行性能。然而這段程序設(shè)計(jì)的獨(dú)特之處就在于使用加權(quán)來標(biāo)記內(nèi)存空閑狀態(tài)，而不是一般的有限狀態(tài)機(jī)，實(shí)際上longest既可以表示權(quán)重又可以表示狀態(tài)，狀態(tài)機(jī)就毫無必要了，所謂“少即是多”嘛！反 觀cloudwu的實(shí)現(xiàn)，將節(jié)點(diǎn)標(biāo)記為UNUSED/USED/SPLIT/FULL四個狀態(tài)機(jī)，反而會帶來額外的條件判斷和管理實(shí)現(xiàn)，而且還不如數(shù)值那 樣精確。從邏輯流程上看，wuwenbin的實(shí)現(xiàn)簡潔明了如同教科書一般，特別是左右子樹的走向，內(nèi)存塊的分離合并，塊索引到節(jié)點(diǎn)下標(biāo)的轉(zhuǎn)換都是一步到 位，不像cloudwu充斥了大量二叉樹的深度和長度的間接計(jì)算，讓代碼變得晦澀難讀，這些都是longest的功勞。一個“極簡”的設(shè)計(jì)往往在于你想不到的突破常規(guī)思維的地方。
這份代碼唯一的缺陷就是longest的大小是4字節(jié)，內(nèi)存消耗大。但cloudwu的博客上有人提議用logN來保存值，這樣就能實(shí)現(xiàn)uint8_t大小了，看，又是一個“極簡”的設(shè)計(jì)！
說實(shí)話，很難在網(wǎng)上找到比這更簡約更優(yōu)雅的buddy system實(shí)現(xiàn)了——至少在Google上如此。
原文鏈接：
譯文鏈接：
