wikipedia：http://en.wikipedia.org/wiki/buddy_memory_allocation
the buddy memory
allocation technique is a algorithm that divides memory into partitions to try
to satisfy a memory request as suitably as possible. this system makes use of splitting memory into halves to try to
give a best-fit. according to , the buddy system was invented in 1963 by,
who won the 1990 , and was first described by (published 1965). buddy
memory allocation is relatively easy to implement. it supports limited but
efficient splitting and .
它支援有限但是高效的分割和記憶體塊合并。
how it works:
there are various forms of the buddy system, but
binary buddies, in which each block is subdivided into two smaller blocks, are
the simplest and most common variety. every memory block in this system
has an order, where the order is an integer ranging from 0 to a
specified upper limit. the size of a block
of order n is proportional to 2n, so that the blocks are
exactly twice the size of blocks that are one order lower. power-of-two block
sizes make address computation simple, because all buddies are aligned on memory
address boundaries that are powers of two. when a larger block is split, it is
divided into two smaller blocks, and each
smaller block becomes a unique buddy to the other. a split block can only
be merged with its unique buddy block, which then reforms the larger block they
were split from.
starting off, the size of the smallest possible block is determined, i.e. the
smallest memory block that can be allocated. if no lower limit existed at all
(e.g., bit-sized allocations were possible), there would be a lot of memory and
computational overhead for the system to keep track of which parts of the memory
are allocated and unallocated. however, a rather low limit may be desirable, so
that the average memory waste per allocation (concerning allocations that are,
in size, not multiples of the smallest block) is minimized. typically the lower
limit would be small enough to minimize the average wasted space per allocation,
but large enough to avoid excessive overhead. the smallest block size is then
taken as the size of an order-0 block, so that all higher orders are expressed
as power-of-two multiples of this size.
the then has to
decide on, or to write code to obtain, the highest possible order that can fit
in the remaining available memory space. since the total available memory in a
given computer system may not be a power-of-two multiple of the minimum block
size, the largest block size may not span the entire memory of the system. for
instance, if the system had 2000k of physical memory and the order-0 block size
was 4k, the upper limit on the order would be 8, since an order-8 block (256
order-0 blocks, 1024k) is the biggest block that will fit in memory.
consequently it is impossible to allocate the entire physical memory in a single
chunk; the remaining 976k of memory would have to be allocated in smaller
blocks.
提起buddy
system相信很多人不會陌生，它是一種經典的記憶體配置設定算法，大名鼎鼎的linux底層的記憶體管理用的就是它。這裡不探讨核心這麼複雜實作，而僅僅是将該算法抽象提取出來，同時給出一份及其簡潔的源碼實作，以便定制擴充。
夥伴配置設定的實質就是一種特殊的“分離适配”，即将記憶體按2的幂進行劃分，相當于分離出若幹個塊大小一緻的空閑連結清單，搜尋該連結清單并給出同需求最佳比對的大小。其優點是快速搜尋合并（o(logn)時間複雜度）以及低外部碎片（最佳适配best-fit）；其缺點是内部碎片，因為按2的幂劃分塊，如果碰上66機關大小，那麼必須劃分128機關大小的塊。但若需求本身就按2的幂配置設定，比如可以先配置設定若幹個記憶體池，在其基礎上進一步細分就很有吸引力了。
可以在上找到該算法的描述，大體如是：
as you can see, what happens when a memory request is made is as follows:
if memory is to be allocated
look for a memory slot of a suitable size (the minimal
2k block that is larger or equal to that of the requested
memory)
if it is found, it is allocated to the program
if not, it tries to make a suitable memory slot. the system does so by
trying the following:
split a free memory slot larger than the requested memory size into
half
if the lower limit is reached, then allocate that amount of
memory
go back to step 1 (look for a memory slot of a suitable size)
repeat this process until a suitable memory slot is found
if memory is to be freed
free the block of memory
look at the neighboring block - is it
free too?
if it is, combine the two, and go back to step 2 and repeat this process
until either the upper limit is reached (all memory is freed), or until a
non-free neighbour block is encountered
配置設定記憶體：
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的代碼就容易了解了。
配置設定器的整體思想是，通過一個數組形式的完全二叉樹來監控管理記憶體，二叉樹的節點用于标記相應記憶體塊的使用狀态，高層節點對應大的塊，低層節點對應小的塊，在配置設定和釋放中我們就通過這些節點的标記屬性來進行塊的分離合并。如圖所示，假設總大小為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]合并後整個記憶體就回歸到初始狀态。
還是看一下源碼實作吧，首先是夥伴配置設定器的資料結構：
1
2
3
4
<code>struct</code>
<code>buddy2 {</code>
<code> </code><code>unsigned size;</code>
<code> </code><code>unsigned longest[1];</code>
<code>};</code>
這裡的成員size表明管理記憶體的總單元數目（測試用例中是32），成員longest就是二叉樹的節點标記，表明所對應的記憶體塊的空閑機關，在下文中會分析這是整個算法中最精妙的設計。此處數組大小為1表明這是可以向後擴充的（注：在gcc環境下你可以寫成longest[0]，不占用空間，這裡是出于可移植性考慮），我們在配置設定器初始化的buddy2_new可以看到這種用法。
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<code>buddy2* buddy2_new(</code><code>int</code>
<code>size ) {</code>
<code> </code><code>struct</code>
<code>buddy2* self;</code>
<code> </code><code>unsigned node_size;</code>
<code> </code><code>int</code>
<code>i;</code>
<code> </code><code>if</code>
<code>(size < 1 || !is_power_of_2(size))</code>
<code> </code><code>return</code>
<code>null;</code>
<code> </code><code>self = (</code><code>struct</code>
<code>buddy2*)alloc( 2 * size *</code><code>sizeof</code><code>(unsigned));</code>
<code> </code><code>self->size = size;</code>
<code> </code><code>node_size = size * 2;</code>
<code> </code><code>for</code>
<code>(i = 0; i < 2 * size - 1; ++i) {</code>
<code> </code><code>if</code>
<code>(is_power_of_2(i+1))</code>
<code> </code><code>node_size /= 2;</code>
<code> </code><code>self->longest[i] = node_size;</code>
<code> </code><code>}</code>
<code> </code><code>return</code>
<code>self;</code>
<code>}</code>
整個配置設定器的大小就是滿二叉樹節點數目，即所需管理記憶體單元數目的2倍。一個節點對應4個位元組，longest記錄了節點所對應的的記憶體塊大小。
記憶體配置設定的alloc中，入參是配置設定器指針和需要配置設定的大小，傳回值是記憶體塊索引。alloc函數首先将size調整到2的幂大小，并檢查是否超過最大限度。然後進行适配搜尋，深度優先周遊，當找到對應節點後，将其longest标記為0，即分離适配的塊出來，并轉換為記憶體塊索引offset傳回，依據二叉樹排列序号，比如記憶體總體大小32，我們找到節點下标[8]，記憶體塊對應大小是4，則offset
= (8+1)*4-32 = 4，那麼配置設定記憶體塊就從索引4開始往後4個機關。
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
<code>int</code> <code>buddy2_alloc(</code><code>struct</code>
<code>buddy2* self,</code><code>int</code>
<code>size) {</code>
<code> </code><code>unsigned index = 0;</code>
<code> </code><code>unsigned offset = 0;</code>
<code>(self==null)</code>
<code>-1;</code>
<code>(size <= 0)</code>
<code> </code><code>size = 1;</code>
<code> </code><code>else</code>
<code>if</code> <code>(!is_power_of_2(size))</code>
<code> </code><code>size = fixsize(size);</code>
<code>(self->longest[index] < size)</code>
<code> </code><code>for</code><code>(node_size = self->size; node_size != size; node_size /= 2 ) {</code>
<code>(self->longest[left_leaf(index)] >= size)</code>
<code> </code><code>index = left_leaf(index);</code>
<code> </code><code>else</code>
<code> </code><code>index = right_leaf(index);</code>
<code> </code><code>self->longest[index] = 0;</code>
<code> </code><code>offset = (index + 1) * node_size - self->size;</code>
<code> </code><code>while</code>
<code>(index) {</code>
<code> </code><code>index = parent(index);</code>
<code> </code><code>self->longest[index] =</code>
<code> </code><code>max(self->longest[left_leaf(index)], self->longest[right_leaf(index)]);</code>
<code>offset;</code>
在函數傳回之前需要回溯，因為小塊記憶體被占用，大塊就不能配置設定了，比如下标[8]标記為0分離出來，那麼其父節點下标[0]、[1]、[3]也需要相應大小的分離。将它們的longest進行折扣計算，取左右子樹較大值，下标[3]取4，下标[1]取8，下标[0]取16，表明其對應的最大空閑值。
在記憶體釋放的free接口，我們隻要傳入之前配置設定的記憶體位址索引，并確定它是有效值。之後就跟alloc做反向回溯，從最後的節點開始一直往上找到longest為0的節點，即當初配置設定塊所适配的大小和位置。我們将longest恢複到原來滿狀态的值。繼續向上回溯，檢查是否存在合并的塊，依據就是左右子樹longest的值相加是否等于原空閑塊滿狀态的大小，如果能夠合并，就将父節點longest标記為相加的和（多麼簡單！）。
<code>void</code>
<code>buddy2_free(</code><code>struct</code>
<code>offset) {</code>
<code> </code><code>unsigned node_size, index = 0;</code>
<code> </code><code>unsigned left_longest, right_longest;</code>
<code> </code><code>assert</code><code>(self && offset >= 0 && offset < size);</code>
<code> </code><code>node_size = 1;</code>
<code> </code><code>index = offset + self->size - 1;</code>
<code>(; self->longest[index] ; index = parent(index)) {</code>
<code> </code><code>node_size *= 2;</code>
<code>(index == 0)</code>
<code> </code><code>return</code><code>;</code>
<code> </code><code>self->longest[index] = node_size;</code>
<code> </code><code>left_longest = self->longest[left_leaf(index)];</code>
<code> </code><code>right_longest = self->longest[right_leaf(index)];</code>
<code>(left_longest + right_longest == node_size)</code>
<code> </code><code>self->longest[index] = node_size;</code>
<code> </code><code>self->longest[index] = max(left_longest, right_longest);</code>
上面兩個成對alloc/free接口的時間複雜度都是o(logn)，保證了程式運作性能。然而這段程式設計的獨特之處就在于使用權重來标記記憶體空閑狀态，而不是一般的有限狀态機，實際上longest既可以表示權重又可以表示狀态，狀态機就毫無必要了，所謂“少即是多”嘛！反觀cloudwu的實作，将節點标記為unused/used/split/full四個狀态機，反而會帶來額外的條件判斷和管理實作，而且還不如數值那樣精确。從邏輯流程上看，wuwenbin的實作簡潔明了如同教科書一般，特别是左右子樹的走向，記憶體塊的分離合并，塊索引到節點下标的轉換都是一步到位，不像cloudwu充斥了大量二叉樹的深度和長度的間接計算，讓代碼變得晦澀難讀，這些都是longest的功勞。一個“極簡”的設計往往在于你想不到的突破正常思維的地方。
這份代碼唯一的缺陷就是longest的大小是4位元組，記憶體消耗大。但上有人提議用logn來儲存值，這樣就能實作uint8_t大小了，看，又是一個“極簡”的設計！
轉自：http://coolshell.cn/articles/10427.html
![圖解HTTP讀書筆記（一）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)