内存管理伙伴系统分析

linux内存管理系统分析之3

内存管理的伙伴系统

伙伴系统是linux内核中内存管理系统的基础。它负责以页为单位管理系统中的内存，申请分配、释放回收、避免内存碎片、虚拟内存中的页换出换入等活动。实际上来分析这个系统有点学术，但是对于修炼“内功”大有裨益，说不定什么时候就派上了大用场。下面会比较详细的分析内存伙伴系统。

还是和之前分析过程一样，我们首先概述一下这个系统中涉及到的主要数据结构，如下图所示，（1）在没有内存域中（ZONE），有一个per CPU变量pageset，这个结构管理这个域的单页分配工作，内核中分配单个页可能是最频繁的一项操作，如此频繁的操作如果直接从伙伴系统中分配单个页面，可能会引起伙伴系统频繁的拆分和合并大页，对系统性能造成比较大的冲击。所以用pageset这种机制做了个缓冲。（2）接下来就是fera_area，也就是伙伴系统，这里将page按不同阶链接在一起，一般MAX_ORDER等于11，也就是最大能分配2^11=2048个页面。（3）还需要说明一下的是每个阶不止一个page列表，为了避免内存碎片，内核引入了一个迁移列表的机制，就是将同一个类型的内存放在一个链表上，避免不可移动的页面被到处地方分配，引起内存碎片。

关于迁移列表机制的可以避免内存碎片的原理可以根据下面的例子来理解。比如下图中，每一个格子代表一个page，蓝色表示被分配了，很明显，系统只分配了很小的一部分内存，但是如果我想再分配连续的8个页面已经不可能了。

但是如果我们把内存区域按内存的用途分为不同的区域，比如将系统中不能搬移的页面限制到只能在上半部分分配，如下图所示。这样下班部分给可移动的页面使用，这样就避免了不可移动页面被分配到这个的内存空间中造成内存碎片。如下图所示，同样的内存使用情况，下图可以分配出来连续8页面的空间。

伙伴系统初始化

伙伴系统初始化除了给内存节点和内存域中相应的字段进行初始化工作外，最关键的工作就是分配得到一个page结构数组，因为在伙伴系统需要用page结构来表示每一个内存页。这个工作在自举内存分配器完成初始化之后就立即完成了。

最后内存节点中node_mem_map指向了该内存节点page数组的起始地址

free_area_init_node函数将内存节点各个域做相应的初始化，并初始化page数据结构。

在mem_init函数中，bootmem系统将逐一检查bitmap上空闲页面的位置，并将这些空闲的页面归还到伙伴系统中，同时将bootmem系统的bitmap也释放掉。

 
/*
* mem_init() marks the free areas in the mem_map and tells us how much
* memory is free.  This is done after various parts of the system have
* claimed their memory after the kernel image.
*/ 
void __init mem_init(void)
{
    unsigned int codesize, datasize, initsize;
    int i, node;
 
#ifndef CONFIG_DISCONTIGMEM
    max_mapnr   = virt_to_page(high_memory) - mem_map;
#endif 
 
    /* this will put all unused low memory onto the freelists */ 
    for_each_online_node(node)
    {
        pg_data_t *pgdat = NODE_DATA(node);
        /*内存节点中的内存不一定连续，可以释放掉表示这些空洞的page数据结构*/ 
        free_unused_memmap_node(node, &meminfo);
 
        if (pgdat->node_spanned_pages != 0)
            /*这个地方比较关键，检查bootmem中的bitmap将没有分配掉的页面还给伙伴系统*/ 
            totalram_pages += free_all_bootmem_node(pgdat);
    }
 
#ifdef CONFIG_SA1111
    /* now that our DMA memory is actually so designated, we can free it */ 
    totalram_pages += free_area(PHYS_PFN_OFFSET,
                                __phys_to_pfn(__pa(swapper_pg_dir)), NULL);
#endif 
 
}
 

free_unused_memmap_node函数释放掉内存节点中空洞空间的page数据结构。如下图所示，系统在分配内存节点的mem_map时是按照这个内存节点起始地址到末尾地址分配的，这个地址空间中可能有空洞，这个空洞地址对应的page数据结构是可以释放掉的（图中蓝色的部分）。有一个问题是，如果zone空间中有空洞，系统怎么可以避免将这些空洞作为有效的地址分配出去呢？实际上伙伴系统分配地址全部依赖这个地址对应的page数据结构挂在伙伴系统，如果对应地址的page数据结构不存在于伙伴系统中，自然也就不会分配该地址空间的内存出去。

free_all_bootmem_node函数则是bootmem系统检查哪些页面已经分配，哪些页面还没有分配，并将没有分配的页面释放到伙伴系统中，并在最后将bootmem系统的bitmap位图所占用的页面也归还到伙伴系统，到此处，bootmem系统就被废除了，而伙伴系统中真正开始有可供分配的页面了。

伙伴系统分配内存

从伙伴系统中分配内存，可以从__alloc_pages_internal函数开始分析这个过程。在伙伴系统分配内存页的时候主要的函数调用过程如下，根据这个调用关系，逐一分析一下各个函数的处理流程。

__alloc_pages_internal函数主要有5个重要的步骤，也就是传说的alloc_pages五剑式。第一剑式，随意而为。也就是随便搞搞，漫不经心，并不使出自己的实力，一方面迷惑敌人，一方面保留自己的实力。

第一次试图分配page页面，使用low warter marker做检查，这个分配
并没有发狠力，只是普通分配内存而已
page = get_page_from_freelist(gfp_mask | __GFP_HARDWALL, nodemask, order,
                              zonelist, high_zoneidx, ALLOC_WMARK_LOW | ALLOC_CPUSET);
if (page)
    goto got_pg;

第二剑式叫平步青云，这个时候alloc_pages使出了四成的功力，平步而上逐步发力。

开始在分配内存的标志中增加ALLOC_WMARK_MIN和ALLOC_HARDER以及ALLOC_HIGH的标志
ALLOC_WMARK_MIN表示使用最小的水线，
ALLOC_HARDER和ALLOC_HIGH都表示在检查水线的时候适当降低标准
alloc_flags = ALLOC_WMARK_MIN;
if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)
    alloc_flags |= ALLOC_HARDER;
if (gfp_mask &__GFP_HIGH)
    alloc_flags |= ALLOC_HIGH;
if (wait)
    alloc_flags |= ALLOC_CPUSET;
 
/*
* Go through the zonelist again. Let __GFP_HIGH and allocations
* coming from realtime tasks go deeper into reserves.
*
* This is the last chance, in general, before the goto nopage.
* Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
* See also cpuset_zone_allowed() comment in kernel/cpuset.c.
*/ 
page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
                              high_zoneidx, alloc_flags);
if (page)
    goto got_pg;

第三剑式就是放力搏击，alloc_pages已经使出了他六成的功力

 
从代码中可以看到PF_MEMALLOC标志表示是在页换出过程中申请内存，系统必须
鼎力支持，所以系统使用了ALLOC_NO_WATERMARKS标志，完全不检查水线
rebalance:
if (((p->flags &PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
        && !in_interrupt())
{
    if (!(gfp_mask & __GFP_NOMEMALLOC))
    {
nofail_alloc:
        /* go through the zonelist yet again, ignoring mins */ 
        page = get_page_from_freelist(gfp_mask, nodemask, order,
                                      zonelist, high_zoneidx, ALLOC_NO_WATERMARKS);
        if (page)
            goto got_pg;
        if (gfp_mask & __GFP_NOFAIL)
        {
            congestion_wait(WRITE, HZ / 50);
            goto nofail_alloc;
        }
    }
    goto nopage;
}

第四剑式叫吸星剑法，也就是不光要使用自己的内功，还要从别人处借用内力。这和任我行的吸星大法有异曲同工之妙，但是总所周知吸星大法虽然强大，但对自己有很多的损伤。

通过同步到释放内存来获取内存页
/*
* The task's cpuset might have expanded its set of allowable nodes
*/ 
cpuset_update_task_memory_state();
p->flags |= PF_MEMALLOC;
reclaim_state.reclaimed_slab = 0;
p->reclaim_state = &reclaim_state;
 
did_some_progress = try_to_free_pages(zonelist, order, gfp_mask);
 
p->reclaim_state = NULL;
p->flags &= ~PF_MEMALLOC;

第五剑式必须是避邪剑法了，改剑法天下无敌，只可惜预成此功，必先xx，alloc_pages经过上面的折腾如果还是分配不到内存，那就割掉系统中的某个进程，释放出来的内存页用来做分配。这是很残忍的，但是应该也是最后的狠招了。这种机制叫做omm killer(out of memory killer)。

get_page_from_freelist函数是具体的分配页面的函数，这个函数的工作根据水线检查系统的内存是不是够分配，如果够就开始分配内存。

/*
* Return 1 if free pages are above 'mark'. This takes into account the order
* of the allocation.
*/ 
int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
                      int classzone_idx, int alloc_flags)
{
    /* free_pages my go negative - that's OK */ 
    long min = mark;
    long free_pages = zone_page_state(z, NR_FREE_PAGES) - (1 << order) + 1;
    int o;
 
    if (alloc_flags & ALLOC_HIGH)
        min -= min / 2;
    if (alloc_flags & ALLOC_HARDER)
        min -= min / 4;
 
    if (free_pages <= min + z->lowmem_reserve[classzone_idx])
        return 0;
    for (o = 0; o < order; o++)
    {
        /* At the next order, this order's pages become unavailable */ 
        free_pages -= z->free_area[o].nr_free << o;
 
        /* Require fewer higher order pages to be free */ 
        min >>= 1;
 
        if (free_pages <= min)
            return 0;
    }
    return 1;
}

zone_watermark_ok函数根据水线来检查一个内存域中有没有足够的页面来分配，不光检查总的页面数量，而且检查高阶的内存页面是不是足够。

 
/*
* Really, prep_compound_page() should be called from __rmqueue_bulk().  But
* we cheat by calling it from here, in the order > 0 path.  Saves a branch
* or two.
*/ 
static struct page *buffered_rmqueue(struct zone *preferred_zone,
                                     struct zone *zone, int order, gfp_t gfp_flags)
{
    unsigned long flags;
    struct page *page;
    int cold = !!(gfp_flags &__GFP_COLD);
    int cpu;
    int migratetype = allocflags_to_migratetype(gfp_flags);
 
again:
    cpu  = get_cpu();
    /*单个页面从冷热页机制中分配*/ 
    if (likely(order == 0))
    {
        struct per_cpu_pages *pcp;
 
        pcp = &zone_pcp(zone, cpu)->pcp;
        local_irq_save(flags);
        /*当前pcp中无page，一次分配batch个页面到pcp中*/ 
        if (!pcp->count)
        {
            pcp->count = rmqueue_bulk(zone, 0,
                                      pcp->batch, &pcp->list, migratetype);
            if (unlikely(!pcp->count))
                goto failed;
        }
 
        /* Find a page of the appropriate migrate type */ 
        /*从列表中找到合适迁移类型的*/ 
        if (cold)
        {
            list_for_each_entry_reverse(page, &pcp->list, lru)
            if (page_private(page) == migratetype)
                break;
        }
        else 
        {
            list_for_each_entry(page, &pcp->list, lru)
            if (page_private(page) == migratetype)
                break;
        }
 
        /* Allocate more to the pcp list if necessary */ 
        /*没有找到合适的迁移类型的页面，就再次分配batch个页面到pcp中*/ 
        if (unlikely(&page->lru == &pcp->list))
        {
            pcp->count += rmqueue_bulk(zone, 0,
                                       pcp->batch, &pcp->list, migratetype);
            page = list_entry(pcp->list.next, struct page, lru);
        }
 
        list_del(&page->lru);
        pcp->count--;
    }
    else 
    {
        /*对于非单个页面的情况直接从伙伴系统分配*/ 
        spin_lock_irqsave(&zone->lock, flags);
        page = __rmqueue(zone, order, migratetype);
        spin_unlock(&zone->lock);
        if (!page)
            goto failed;
    }
 
    __count_zone_vm_events(PGALLOC, zone, 1 << order);
    zone_statistics(preferred_zone, zone);
    local_irq_restore(flags);
    put_cpu();
 
    VM_BUG_ON(bad_range(zone, page));
    if (prep_new_page(page, order, gfp_flags))
        goto again;
    return page;
 
failed:
    local_irq_restore(flags);
    put_cpu();
    return NULL;
}
 

__rmqueue从伙伴系统中分配页面过程，其中涉及到迁移列表的问题。

/*
* Do the hard work of removing an element from the buddy allocator.
* Call me with the zone->lock already held.
*/ 
static struct page *__rmqueue(struct zone *zone, unsigned int order,
                              int migratetype)
{
    struct page *page;
    /*从本迁移类型上分配内存页面*/ 
    page = __rmqueue_smallest(zone, order, migratetype);
 
    /*试图从其它的迁移类型上分配页面*/ 
    if (unlikely(!page))
        page = __rmqueue_fallback(zone, order, migratetype);
 
    return page;
}

内存释放返回伙伴系统

内存释放会伙伴系统的过程相对于获取内存要简单一点，主要分两种情况，一种情况就是释放单个页面，另外一种情况释放多个页面。主要函数调用过程如下。

释放单个页面的时候系统首先将页面释放到冷热页系统中，如果冷热页系统超过了一定数目个页面，再将这些页面一次释放batch个回到伙伴系统。

如果不是释放单个页面而是释放多个页面，就将这些页面直接释放到伙伴系统，但是这个中间涉及到一个低级向高阶合并的过程。这个也是伙伴系统的一个精髓的东西。其合并算法在__free_one_page可以看到。

 

andy yixin deng

2013-03-16 南京

mail: andy.yx.deng#gmail.com