Linux内存管理之伙伴系统（内存释放）

发布时间：2014-09-05 16:36:49作者：知识屋

Linux内核伙伴系统中页面释放，主函数为free_pages()

一、上层操作

www.zhishiwu.com
/*用虚拟地址进行释放*/
void free_pages(unsigned long addr, unsigned int order)
{
    if (addr != 0) {
        VM_BUG_ON(!virt_addr_valid((void *)addr));
        __free_pages(virt_to_page((void *)addr), order);/*具体的释放函数*/
    }
}
www.zhishiwu.com
/*释放页面*/
void __free_pages(struct page *page, unsigned int order)
{
    if (put_page_testzero(page)) {/*count值减一为0时释放*/
        /*调试*/
        trace_mm_page_free_direct(page, order);
        if (order == 0)
            free_hot_page(page);/*释放单个页面*/
        else
            __free_pages_ok(page, order);
    }
}
二、释放单个页面

释放单个页面free_hot_page()调用free_hot_cold_page()函数

www.zhishiwu.com
static void free_hot_cold_page(struct page *page, int cold)
{
    struct zone *zone = page_zone(page);
    struct per_cpu_pages *pcp;
    unsigned long flags;
    int migratetype;
    int wasMlocked = __TestClearPageMlocked(page);
    /*调试代码*/
    kmemcheck_free_shadow(page, 0);

    if (PageAnon(page))
        page->mapping = NULL;
    if (free_pages_check(page))
        return;

    if (!PageHighMem(page)) {
      debug_check_no_locks_freed(page_address(page), PAGE_SIZE);
        debug_check_no_obj_freed(page_address(page), PAGE_SIZE);
    }
    /*x86下为空*/
    arch_free_page(page, 0);
    /*调试用*/
    kernel_map_pages(page, 1, 0);
    /*获得zone对应cpu的pcp*/
    pcp = &zone_pcp(zone, get_cpu())->pcp;
    /*获得页面的migratetype*/
    migratetype = get_pageblock_migratetype(page);
    set_page_private(page, migratetype);/*设置私有位为参数*/
    local_irq_save(flags);/*保存中断*/
    if (unlikely(wasMlocked))
        free_page_mlock(page);
    __count_vm_event(PGFREE);

    /*
     * We only track unmovable, reclaimable and movable on pcp lists.
     * Free ISOLATE pages back to the allocator because they are being
     * offlined but treat RESERVE as movable pages so we can get those
     * areas back if necessary. Otherwise, we may have to free
     * excessively into the page allocator
     */
    if (migratetype >= MIGRATE_PCPTYPES) {
        if (unlikely(migratetype == MIGRATE_ISOLATE)) {
            /*释放到伙伴系统*/
            free_one_page(zone, page, 0, migratetype);
            goto out;
        }
        migratetype = MIGRATE_MOVABLE;
    }

    if (cold)/*加入到pcp链表尾部*/
        list_add_tail(&page->lru, &pcp->lists[migratetype]);
    else/*加入到pcp链表头部*/
        list_add(&page->lru, &pcp->lists[migratetype]);
    pcp->count++;/*pcp计数加一*/
    if (pcp->count >= pcp->high) {/*当pcp中页面数量超过他的最高值时，
        释放pcp->batch个页面到伙伴系统中*/
        free_pcppages_bulk(zone, pcp->batch, pcp);
        pcp->count -= pcp->batch;/*页面数减去释放的页面数量*/
    }

out:
    local_irq_restore(flags);/*回复中断*/
    put_cpu();
}
从pcp中释放页面到伙伴系统中

free_pcppages_bulk()

www.zhishiwu.com
are in same zone, and of same order.
* count is the number of pages to free.
*
* If the zone was previously in an "all pages pinned" state then look to
* see if this freeing clears that state.
*
* And clear the zone's pages_scanned counter, to hold off the "all pages are
* pinned" detection logic.
*/
/*从PCP中释放count个页面到伙伴系统中*/
static void free_pcppages_bulk(struct zone *zone, int count,
                    struct per_cpu_pages *pcp)
{
    int migratetype = 0;
    int batch_free = 0;
    /*
     * 虽然管理区可以按照CPU节点分类，但是也可以跨CPU节点进行内存分配，
     * 因此这里需要用自旋锁保护管理区
     * 使用每CPU缓存的目的，也是为了减少使用这把锁。
     */
    spin_lock(&zone->lock);
    /* all_unreclaimable代表了内存紧张程度，释放内存后，将此标志清除*/
    zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);
    zone->pages_scanned = 0;/* pages_scanned代表最后一次内存紧张以来，页面回收过程已经扫描的页数。
    目前正在释放内存，将此清0，待回收过程随后回收时重新计数*/

    /*增加管理区空闲页数*/
    __mod_zone_page_state(zone, NR_FREE_PAGES, count);
    while (count) {
        struct page *page;
        struct list_head *list;

        /*
         * Remove pages from lists in a round-robin fashion. A
         * batch_free count is maintained that is incremented when an
         * empty list is encountered. This is so more pages are freed
         * off fuller lists instead of spinning excessively around empty
         * lists
         */
        do {/*从pcp的三类链表中找出不空的一个，释放*/
            batch_free++;/*参看英文注释*/
            if (++migratetype == MIGRATE_PCPTYPES)
                migratetype = 0;
            list = &pcp->lists[migratetype];
        } while (list_empty(list));

        do {
            page = list_entry(list->prev, struct page, lru);
            /* must delete as __free_one_page list manipulates */
            list_del(&page->lru);
            /*释放单个页面到伙伴系统，注意这里的分类回收*/
            __free_one_page(page, zone, 0, migratetype);
            trace_mm_page_pcpu_drain(page, 0, migratetype);
        } while (--count && --batch_free && !list_empty(list));
    }
    spin_unlock(&zone->lock);
}
三、释放多个页面

释放多个页面__free_pages_ok()函数

www.zhishiwu.com
int i;
int bad = 0;
int wasMlocked = __TestClearPageMlocked(page);
/*调试用，和相关宏有关*/
kmemcheck_free_shadow(page, order);

for (i = 0 ; i < (1 << order) ; ++i)/*页面相关检查*/
    bad += free_pages_check(page + i);
if (bad)
    return;

if (!PageHighMem(page)) {
    debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);
   debug_check_no_obj_freed(page_address(page),
                   PAGE_SIZE << order);
}
/*X86体系下为空*/
arch_free_page(page, order);
/*调试，相关宏定义*/
kernel_map_pages(page, 1 << order, 0);

local_irq_save(flags);/*flags的暂存，关中断*/
if (unlikely(wasMlocked))
    free_page_mlock(page);
__count_vm_events(PGFREE, 1 << order);
/*传入参数，进行具体的释放工作，将1<<order的页面释放
到伙伴系统中*/
free_one_page(page_zone(page), page, order,
                get_pageblock_migratetype(page));/*获得内存块的类型*/
local_irq_restore(flags);/*恢复中断*/
www.zhishiwu.com
static void free_one_page(struct zone *zone, struct page *page, int order,
                int migratetype)
{
    spin_lock(&zone->lock);/*获得管理区的自旋锁*/
    zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);/* 只要是释放了页面，都需要将此两个标志清0，表明内存不再紧张的事实*/
    zone->pages_scanned = 0;
    /*管理区空闲页面计数*/
    __mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
    /*释放到指定的伙伴系统类型链表*/
    __free_one_page(page, zone, order, migratetype);
    spin_unlock(&zone->lock);/*释放锁*/
}
www.zhishiwu.com
etype)
{
    unsigned long page_idx;

    if (unlikely(PageCompound(page)))/*要释放的页是巨页的一部分*/
        /* 解决巨页标志，如果巨页标志有问题，则退出*/
        if (unlikely(destroy_compound_page(page, order)))
            return;

    VM_BUG_ON(migratetype == -1);
    /*将页面转化为全局页面数组的下标*/
    page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
    /* 如果被释放的页不是所释放阶的第一个页，则说明参数有误*/
    VM_BUG_ON(page_idx & ((1 << order) - 1));
    /* 校验页块是否有效，检查是否有空洞，页块中的页面是否都在同一个zone中 */
    VM_BUG_ON(bad_range(zone, page));

    while (order < MAX_ORDER-1) {
        unsigned long combined_idx;
        struct page *buddy;
        /*找出page页面的伙伴
         查找待释放页块的伙伴,其中伙伴系统中每个块
         都有一个对应同样大小的"伙伴块"(由2的指数原理知)*/
        buddy = __page_find_buddy(page, page_idx, order);
        if (!page_is_buddy(page, buddy, order))/*检查页面是否为伙伴*/
            break;

        /* Our buddy is free, merge with it and move up one order. */
        list_del(&buddy->lru);
        zone->free_area[order].nr_free--;
         /* 为下面的合并做准备，清除伙伴的PG_buddy标志位，并设置伙伴的private成员为
            0 */
        rmv_page_order(buddy);
        /* 利用伙伴算法公式计算合并后父节点的页块索引*/
        /*实际上是这样的，这个要配合上面的找buddy
        *算法一起看，找出的buddy时在原来的下标中往上或向下走
        *(1<<order个位置
        *而这里的函数是找出合并后的新块的首地址
        *也就是说如果上面是加，这里的基地址不变
        *而如果上面是减，这里往下减1<<order
        *其中这里的标号不是物理地址，也不是和mem_map
        *直接关联，而是运用于buddy算法，也就是这里的
        *构造出来的特定的表示，他使得这里的伙伴的寻找
        *和伙伴的合并实现的很巧妙
        */
        combined_idx = __find_combined_index(page_idx, order);
        page = page + (combined_idx - page_idx);
        page_idx = combined_idx;
        order++;
    }
    set_page_order(page, order);/*设置page的私有属性，伙伴系统通过这个值来
                            确定页面所属的order*/
    list_add(&page->lru,
        &zone->free_area[order].free_list[migratetype]);/*伙伴系统中每一种order有5中空闲链表*/
    zone->free_area[order].nr_free++;/*对应order的空闲块加一*/
}
四、关于伙伴的操作

4.1，查找伙伴

www.zhishiwu.com
static inline struct page *
__page_find_buddy(struct page *page, unsigned long page_idx, unsigned int order)
{
    /*伙伴的计算原理，
    *实际上，使用(1<<order)掩码的异或(XOR)转换page_idx第order位
    *的值。因此，如果这个位原来是0，buddy_idx就等于page_idx+order
    *相反，如果这个位原先是1，buddy_idx就等于page_idx-order
    *此计算出来的伙伴为在mem_map中的下标
    */
    unsigned long buddy_idx = page_idx ^ (1 << order);
    /*返回伙伴块的页面基址*/
    return page + (buddy_idx - page_idx);
}
4.2，检查是否为伙伴

www.zhishiwu.com
static inline int page_is_buddy(struct page *page, struct page *buddy,
                                int order)
{
    if (!pfn_valid_within(page_to_pfn(buddy)))/*验证此buddy的有效性*/
        return 0;

    if (page_zone_id(page) != page_zone_id(buddy))/*验证page和他的buddy是否在同一个zone中*/
        return 0;
    /*验证相关位和buddy的order值*/
    /* 通过检查PG_buddy 标志位判断buddy是否在伙伴系统中，并且buddy是否在order级的
     链表中，page的private成员存放页块所在链表的order。*/
    if (PageBuddy(buddy) && page_order(buddy) == order) {
        VM_BUG_ON(page_count(buddy) != 0);
        return 1;
    }
    return 0;
}
总结：伙伴系统内存释放或称主要流程

1，如果释放的是单个页面，需要根据页面类型考虑是否释放到伙伴系统中，同时，将其加入到pcp链表中。如果pcp链表中内存过多，调用free_pcppages_bulk()函数将大块内存放回伙伴系统中；

2，如果释放的是多个页面，直接调用__free_one_page()释放到伙伴系统中。

3，释放到伙伴系统中时，需要考虑和伙伴的合并情况。

（免责声明：文章内容如涉及作品内容、版权和其它问题，请及时与我们联系，我们将在第一时间删除内容，文章内容仅供参考）