浅析armlinux-Buddy(伙伴)算法-释放合并回收函数__free_pages_ok()

浅析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<
        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<
    }
//将经过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))超过该zone->size管理上限偏移
    || (((page) - mem_map) < (zone)->zone_start_mapnr)\\//小于该zone管理起始偏移
    || ((zone) != page_zone(page))\\//非本page对应的zone
)