linux伙伴算法 釋放塊時的漏洞

yxjfish

《深入理解linux內(nèi)核》上描述：
__free_pages_bulk()函數(shù)按照伙伴系統(tǒng)的策略釋放頁框。它使用3個基本輸入?yún)��?shù)：
page：被釋放塊中所包含的第一個頁框描述符的地址。
zone：管理區(qū)描述符的地址。
order：塊大小的對數(shù)。

__free_pages_bulk()首先聲明和初始化一些局部變量：
struct page * base = zone->zone_mem_map;
unsigned long buddy_idx, page_idx = page - base;
struct page * buddy, * coalesced;
int order_size = 1 << order;

page_idx局部變量包含塊中第一個頁框的下標，這是相對于管理區(qū)中的第一個頁框而言的。order_size 局部變量用于增加管理區(qū)中空閑頁框的計數(shù)器：
zone->free_pages += order_size;

現(xiàn)在函數(shù)開始執(zhí)行循環(huán)，最多循環(huán) (10-order) 次，每次都盡量把一個塊和它的伙伴進行合并。函數(shù)以最小的塊開始，然后向上移動到頂部：
while (order < 10) {
    buddy_idx = page_idx ^ (1 << order);
    buddy = base + buddy_idx;
    if (!page_is_buddy(buddy, order))
        break;
    list_del(&buddy->lru);
    zone->free_area[order].nr_free--;
    ClearPagePrivate(buddy);
    buddy->private = 0;
    page_idx &= buddy_idx;   /* 合并 */
    order++;
}

實際上，使用（1 << order）掩碼的異或轉(zhuǎn)換page_idx第order位的值。因此，如果這個位原先是0，buddy_idx就等于page_idx + order_size；相反，如果這個位原先是1，buddy_idx就等于page_idx – order_size。

問題：
    假如page_index為0x010100（20頁框），而此時order為4（16個頁面），在page頁面的后面有16個頁面空閑（0x100100），而page前面沒有空閑的空間，但是通過該算法得到的buddy_index為0x00100（4頁框），即page的前面16頁面，此時則不會進行合并。
    伙伴算法應該合并釋放page之前或者之后的buddy，但是實現(xiàn)的過程中為什么只是選擇一邊合并，而忽略另一邊呢？

塑料袋

假如page_index為0x010100（20頁框），而此時order為4（16個頁面），在page頁面的后面有16個頁面空閑（0x100100），而page前面沒有空閑的空間，但是通過該算法得到的buddy_index為0x00100（4頁框），即page的前面16頁面，此時則不會進行合并。

因為不會有這種情況，order=4時，idx必為0,16,32,48........

yxjfish

假如page_index為0x100000（32個頁面），order為4（16個頁面），page的前16個頁面（0x10000）空閑，后16個頁面沒有空閑（0x110000），此時buddy_index為0x110000（48個頁面），按照道理應該和前16個頁面合并，但是按照上述算法并沒有！2# 塑料袋


   

yxjfish

謝謝您的提醒，我知道原因了：
假如page_index為0x100000（32個頁面），order為4（16個頁面），page的前16個頁面（0x10000）空閑，后16個頁面沒有空閑（0x110000），此時buddy_index為0x110000（48個頁面），按照道理應該和前16個頁面合并，但是按照上述算法并沒有，這是因為這種情況下是不能合并了，如果合并的話違反了一個原則“每個塊的第一個物理頁面的物理地址是該塊大小的整數(shù)倍”。
3# yxjfish