淺析armlinux-Buddy(伙伴)算法-釋放合并回收函數__free_pages_ok()
文章來源:http://gliethttp.cublog.cn

Buddy(伙伴算法)最讓人為之激動的在于它釋放回收頁面過程中將小內存合并成大內存進而減少碎片的功能,
下面讓我們來看看釋放頁面的函數__free_pages_ok()的具體實現.
static void __free_pages_ok (struct page *page, unsigned int order)
{unsigned long index, page_idx, mask, flags;
free_area_t *area;
struct page *base;
zone_t *zone;

    if (PageLRU(page))//檢測該page是否在page lists中
        lru_cache_del(page);//如果在page lists中,那么調用該函數將其移出

    if (page->buffers)
        BUG();
    if (page->mapping)
        BUG();
//檢測(page - mem_map) < max_mapnr是否超過page管理單元總數
//即page是否在有效的mem_map~mem_map+max_mapnr范圍之內
    if (!VALID_PAGE(page))
        BUG();
    if (PageLocked(page))
        BUG();
    if (PageActive(page))
        BUG();
    page->flags &= ~((1<<PG_referenced) | (1<<PG_dirty));//釋放page標志位,進而釋放該order頁
    if (current->flags & PF_FREE_PAGES)//需要釋放1個頁面到進程的local_pages中
        goto local_freelist;
back_local_freelist:
    zone = page_zone(page);//該page位于DMA、NORMAL或者HIGHMEM之中的一個zone內
//order 0  1  2  3   4   5   6    7    8    9
//mask -1 -2 -4 -8 -16 -32 -64 -128 -256 -512
//-maks 1  2  4  8  16  32  64  128  256  512
//~mask 0  1  3  7  15  31  63  127  255  511
//具體理解請參見《 我看Buddy(伙伴)算法－到底是怎么計算"伙伴"地址的》[http://gliethttp.cublog.cn]
    mask = (~0UL) << order;
    base = zone->zone_mem_map;//該管理zone所有4k頁面的起始mem_map虛擬地址
    page_idx = page - base;//計算該page是第幾個頁《對于結構體指針+、-常數的理解(page_to_pfn和pfn_to_page)》
    if (page_idx & ~mask)//該page一定是(1 << order)字節對齊的
        BUG();
    index = page_idx >> (1 + order);//使用buddy算法,求得該page對應的map管理位圖值page_idx >> order)/2
    area = zone->free_area + order;//獲取該zone對應的free_area[order]

    spin_lock_irqsave(&zone->lock, flags);
//order 0  1  2  3   4   5   6    7    8    9
//mask -1 -2 -4 -8 -16 -32 -64 -128 -256 -512
//-maks 1  2  4  8  16  32  64  128  256  512
//~mask 0  1  3  7  15  31  63  127  255  511
    zone->free_pages -= mask;//將釋放的空閑頁數目,加到該zone的free_pages中去
    while (mask + (1 << (MAX_ORDER-1))) {//當order=9時,即mask <<= 1;到達9時,mask = -512,此時while(0),退出
        struct page *buddy1, *buddy2;
        if (area >= zone->free_area + MAX_ORDER)
            BUG();
//對index進行(^)異或運算,返回0,表示伙伴不在當前area內,或序伙伴忙,或許伙伴被拆到了其他area空閑著
//一個index管理2個稱為伙伴的相鄰頁塊
//請參考《我看Buddy(伙伴)算法－到底是怎么"找朋友"的》[http://gliethttp.cublog.cn]
        if (!__test_and_change_bit(index, area->map))
            break;
        buddy1 = base + (page_idx ^ -mask);//求得它的伙伴對應的struct page單元,對邊界位(1<<order)進行異或操作
        buddy2 = base + page_idx;//自己的struct page單元

        if (BAD_RANGE(zone,buddy1))//確定該struct page單元是合法的
            BUG();
        if (BAD_RANGE(zone,buddy2))//確定該struct page單元是合法的
            BUG();
        list_del(&buddy1->list);//將伙伴buddy1從空閑鏈表中刪除
        mask <<= 1;//去order+1執行和上面同樣的Buddy伙伴合并算法
        area++;//area指向order+1下一個高次area
        index >>= 1;//計算order+1對應的位圖管理位索引號index = page_idx >> (1 + 1 + ... + order);
        page_idx &= mask;//調整page_idx成(1<<order)頁對齊,即:調整page_idx成伙伴中"比較小的那個小伙伴"對應的地址
    }
//將經過Buddy伙伴合并后的頁,添加到相應order對應的area對應的free_list中
    list_add(&(base + page_idx)->list, &area->free_list);
    spin_unlock_irqrestore(&zone->lock, flags);
    return;
local_freelist:
    if (current->nr_local_pages)
        goto back_local_freelist;//如果local_pages已經有了,那么可以將page是釋放到area->free_list中
    if (in_interrupt())//在中斷中,也需要將page是釋放到area->free_list中
        goto back_local_freelist;
//current->nr_local_pages == 0同時不在中斷中,那么將該page是釋放到current->local_pages中
    list_add(&page->list, &current->local_pages);
    page->index = order;//標示該page后面還有有多少個可用頁面
    current->nr_local_pages++;
}
//----------------------------------------
#define BAD_RANGE(zone, page)\
(\
    (((page) - mem_map) >= ((zone)->zone_start_mapnr+(zone)->size))[url=]\\//[/url]超過該zone->size管理上限偏移
    || (((page) - mem_map) < (zone)->zone_start_mapnr)\\//小于該zone管理起始偏移
    || ((zone) != page_zone(page))\\//非本page對應的zone
)