物理内存管理:伙伴系统page分裂函数分析

April 14th, 2015 by JasonLe's Tech Leave a reply »

快速分配函数中,大部分代码都是一些具体策略的实现,包括watermark,NUMA,公平分配ALLOC_FAIR等。真正与buddy system有关的就是buffered_rmqueue()函数。

我们看到当进入到这个函数,会先对order进行一个判断,如果order==0,则kernel不会从伙伴系统分配,而是从per-cpu缓存加速请求的处理。如果缓存为空就要调用rmqueue_bulk()函数填充缓存,道理还是从伙伴系统中移出一页,添加到缓存。

当传入的order>0时,则调用_rmqueue()从伙伴系统中选择适合的内存块,有可能会将大的内存块分裂成为小的内存块,用来满足分配请求。

static inline
struct page *buffered_rmqueue(struct zone *preferred_zone,
            struct zone *zone, unsigned int order,
            gfp_t gfp_flags, int migratetype)
{
    unsigned long flags;
    struct page *page;
    bool cold = ((gfp_flags & __GFP_COLD) != 0);

again:
    if (likely(order == 0)) {
...
    } else {
        if (unlikely(gfp_flags & __GFP_NOFAIL)) {
            WARN_ON_ONCE(order > 1);
        }
        spin_lock_irqsave(&zone->lock, flags);
        page = __rmqueue(zone, order, migratetype);
        spin_unlock(&zone->lock);
        if (!page)
            goto failed;
        __mod_zone_freepage_state(zone, -(1 << order),
                      get_freepage_migratetype(page));
    }
...
}
...
static struct page *__rmqueue(struct zone *zone, unsigned int order,
                        int migratetype)
{
    struct page *page;

retry_reserve:
    page = __rmqueue_smallest(zone, order, migratetype);

    if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
        page = __rmqueue_fallback(zone, order, migratetype);

        if (!page) {
            migratetype = MIGRATE_RESERVE;
            goto retry_reserve;
        }
    }

    trace_mm_page_alloc_zone_locked(page, order, migratetype);
    return page;
}

上面说的buffered_rmqueue()是进入伙伴系统的前置函数,而__rmqueue是进入伙伴系统的最后一个包装函数,通过这个函数,__rmqueue_smallest()会扫描当前zone下面的空闲区域。

如果不能通过这种方式分配出空闲页,那么系统会调用__rmqueue_fallback()来遍历不同的迁移类型,试图找出不同的迁移类型中空闲的page。这里我们不会仔细分析,但是我们看一下__rmqueue_fallback()的遍历头就能发现端倪。kernel会从start_migratetype迁移类型考虑备用列表的不同迁移类型,具体可以查看http://lxr.free-electrons.com/source/mm/page_alloc.c#L1036

这里找到一篇叙述迁移页的博客《通过迁移类型分组来实现反碎片》,讲的很清楚!

static inline struct page *
__rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
{
    struct free_area *area;
    unsigned int current_order;
    struct page *page;
    int migratetype, new_type, i;

    /* Find the largest possible block of pages in the other list */
    for (current_order = MAX_ORDER-1;
                current_order >= order && current_order <= MAX_ORDER-1;
                --current_order) {
        for (i = 0;; i++) {
            migratetype = fallbacks[start_migratetype][i];

...

__rmqueue_smallest()函数传入的参数有order,kernel会遍历当前zone下面从指定order到MAX_ORDER的伙伴系统,这个时候迁移类型是指定的,如图:
buddy

static inline
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
                        int migratetype)
{
    unsigned int current_order;
    struct free_area *area;
    struct page *page;

    /* Find a page of the appropriate size in the preferred list */
    for (current_order = order; current_order < MAX_ORDER; ++current_order) {
        area = &(zone->free_area[current_order]);
        if (list_empty(&area->free_list[migratetype]))
            continue;

        page = list_entry(area->free_list[migratetype].next,
                            struct page, lru);
        list_del(&page->lru);
        rmv_page_order(page);
        area->nr_free--;
        expand(zone, page, order, current_order, area, migratetype);
        set_freepage_migratetype(page, migratetype);
        return page;
    }

    return NULL;
}

我们看到kernel会提取出当前zone下面的struct free_area,我们知道struct free_area是上图整体的一个结构,然后我们按照order可以找到指定的free_list结构,这个结构链接了所有系统中空闲page。

找到这个page,则将这个page从list上面删除,然后rmv_page_order()可也将page的标志位PG_buddy位删除,表示这个页不包含于buddy system。

将这个page所在的nr_free自减,之后调用expand()函数,这个函数存在的意义就是在高阶order分配了一个较小的page,但同时低阶order又没有合适的页分配。

static inline void expand(struct zone *zone, struct page *page,
    int low, int high, struct free_area *area,
    int migratetype)
{
    unsigned long size = 1 << high;

    while (high > low) {
        area--;
        high--;
        size >>= 1;
.....
        list_add(&page[size].lru, &area->free_list[migratetype]);
        area->nr_free++;
        set_page_order(&page[size], high);
    }
}

进入到expand()函数,这个函数是从current_order到请求order倒序遍历,函数的核心是通过current_order折半分裂,分裂完之后,将空闲的page挂到相同的order阶上面的free_area,然后nr_free++,set_page_order()作用是对于回收到伙伴系统的的内存的一个struct page实例中的private设置分配阶,并且设置PG_buddy。

 

完成伙伴系统的高阶page分裂。

 

PLKA: Page190

物理内存管理:伙伴系统数据结构分析