Buddy Algorithm

Buddy Algorithm出現在mm/page_alloc.c文件中的__free_one_page函數。先上我的手繪圖：

將代碼作了簡化，勾勒出Buddy算法如下：

while () {
    buddy_idx = page_idx ^ (1 << order);
    combined_idx = buddy_idx & page_idx;
    page_idx = combined_idx;
    order++;
}

以下是實例分析的數據：

page_idx = 255
buddy_idx = 11111111b ^ (1 << 2) = 11111011b = 251
combined_idx = 251
page_idx = 251

page_idx = 251
buddy_idx = 11111011b ^ (1 << 3) = 11110011b = 243
combined_idx = 243
page_idx = 243

page_idx = 243
buddy_idx = 11110011b ^ (1 << 4) = 11100011b = 227
combined_idx = 227
page_idx = 227

page_idx = 227
buddy_idx = 11100011b ^ (1 << 5) = 11000011b = 195
combined_idx = 195
page_idx = 195

195, 131, 3 ...

page_idx = 3
buddy_idx = 11b ^ (1 << 8) = 100000011b = 259
combined_idx = 3
page_idx = 3

page_idx = 3, buddy_idx = 515
...

--
page_idx = 16
buddy_idx = 00010000b ^ (1 << 2) = 00010100b = 20
combined_idx = 16
page_idx = 16

page_idx = 16
buddy_idx = 00010000b ^ (1 << 3) = 00011000b = 24
combined_idx = 16
page_idx = 16

page_idx = 16
buddy_idx = 00010000b ^ (1 << 4) = 0
combined_idx = 0
page_idx = 0

page_idx = 0
buddy_idx = 0 ^ (1 << 5) = 32
combined_idx = 0
page_idx = 0

64, 128..