Linux伙伴算法

    最近一直在学习Linux内存管理的知识，以《独辟蹊径品内核：Linux内核源代码导读》为学习的教材，并且参考了一些网络上的文章，再结合自己的理解整理出了如下的文章。由于笔者能力有限，文中难免存在不足，如果发现错误之处，希望能帮助我及时纠正错误之处。

1、伙伴算法的用途

管理物理内存，解决外碎片问题。

2、满足以下条件的两个块称为伙伴

l 两个块具有相同的大小，记作b

l 它们的物理地址是连续的

l 第一块的第一个页框的物理地址是2*b*2^12的倍数

3、伙伴算法管理结构

伙伴算法把物理内存分为11个组，第0、1、...10组分别包含2^0、2^1、...2^10个连续物理页面的内存。在zone结构中，有一个free_area数组，数组的每一个成员代表一个组，相关定义如下：

#define MAX_ORDER 11

struct zone {

    ...

struct free_area free_area[MAX_ORDER];

    ...

}

struct free_area {

struct list_head free_list;

/*该组类别块空闲的个数*/

unsigned long nr_free;

};

    由此可知伙伴算法管理结构如下图所示：

4、伙伴算法的初始化和释放

1) 伙伴算法初始化过程

    在start_kernel->

             mem_init-> 

       free_all_bootmem_node->

            free_all_bootmem_core->

                 __free_pages_bootmem->

                               __free_pages->

                                __free_pages_ok->

                                       free_one_page->

                                         __free_one_page函数中，通过对每一个页面进行释放，从而完成对伙伴算法的初始化工作。

2) 伙伴算法的具体释放过程

l 伙伴算法释放的思想

当释放2^order页大小内存时，查看它的伙伴是否空闲，如果空闲就将伙伴从该组链表中删除，并且将这两个空闲的伙伴内存区域合并成一个更高阶的空闲内存区域，依次这样操作下去。

l __free_one_page函数分析如下

static inline void __free_one_page(struct page *page,

struct zone *zone, unsigned int order)

{

    unsigned long page_idx;

    int order_size = 1 << order;

    int migratetype = get_pageblock_migratetype(page);

 

    /*用PFN作为mem_map数组下标就可以索引到对应的page结构*/

    page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);

    __mod_zone_page_state(zone, NR_FREE_PAGES, order_size);

  

    /*这个循环主要查看当前释放块伙伴是否空闲，如果空闲则合并它们*/

    while (order < MAX_ORDER-1) { 

    unsigned long combined_idx;

    struct page *buddy;

    /*找到释放块的伙伴*/

    buddy = __page_find_buddy(page, page_idx, order);

    /*判断释放块的伙伴是否空闲*/

    if (!page_is_buddy(page, buddy, order))

        break;

    list_del(&buddy->lru);

    zone->free_area[order].nr_free--;

    rmv_page_order(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);

    list_add(&page->lru,

    &zone->free_area[order].free_list[migratetype]);

    zone->free_area[order].nr_free++;

}

5、伙伴算法的内存分配

1) 伙伴算法内存分配的过程

当内核收到alloc_pages系列函数的分配请求时，首先需要确定是从哪一个节点上分配，然后再确定需要从节点的哪一个zone上分配，最后再根据伙伴算法，确定从zone的哪一个free_area数组成员上分配。在内存不足的情况下，还要回收内存，如果内存还是不够，还要调度kswapd把必要的内存存储到交换分区中。内存分配模块总是试图从代价最小的节点上分配，而对zone的确定则根据alloc_pages()系列函数的gfp_mask用以下规则确定：

l 如果gfp_mask参数设置了__GFP_DMA位，则只能从ZONE_DMA中分配。

l 如果gfp_mask参数设置了__GFP_HIGHMEM位，则能够从ZONE_DMA、ZONE_NORMAL、ZONE__HIGHMEM中分配。

l 如果__GFP_DMA和__GFP_HIGHMEM都没有设置，则能够从ZONE_DMA和ZONE_NORMAL中分配。

当然，如果没有指定__GFP_DMA标志，则会尽量避免使用ZONE_DMA区的内存，只有当指定的区内存不足，而ZONE_DMA区又有充足的内存时，才会从ZONE_DMA中分配。

2) 伙伴算法的具体内存分配过程

l 伙伴算法内存分配的思想

    举例说明：假设请求分配4个页面，根据该算法先到第2(2^2=4)个组中寻找空闲块，如果该组没有空闲块就到第3(2^3=8)个组中寻找，假设在第3个组中找到空闲块，就把其中的4个页面分配出去，剩余的4个页面放到第2个组中。如果第三个组还是没有空闲块，就到第4(2^4=16)个组中寻找，如果在该组中找到空闲块，把其中的4个页面分配出去，剩余的12个页面被分成两部分，其中的8个页面放到第3个组，另外4个页面放到第2个组...依次类推。

l alloc_pages系列函数最终会调用__rmqueue函数从free_area中取出内存页面，__rmqueue函数具体分析如下：

//返回申请到的内存空间首页的struct page结构指针

static struct page *__rmqueue(struct zone *zone, unsigned int order)

{

    struct free_area * area;

    unsigned int current_order;

    struct page *page;

    /*查询zone中从order到MAX_ORDER-1的各指数值对应的空闲内存区域*/

    for (current_order = order; current_order < MAX_ORDER; ++current_order) {

    /*连续2^current_order页空闲内存区域的描述结构指针*/

    area = zone->free_area + current_order;

    /*如果该空闲内存区域为空，则继续查看2^(current_order+1)页空闲内存区域*/

    if (list_empty(&area->free_list))

        continue;

            

    /*得到该空闲内存区域的首页struct page结构指针*/

    page = list_entry(area->free_list.next, struct page, lru);

    /*将page所指的连续2^current_order页的空闲区域从其所在的链表中删除*/

    list_del(&page->lru);

    rmv_page_order(page);

    area->nr_free--;

    __mod_zone_page_state(zone, NR_FREE_PAGES, - (1UL << order));

    /*

     *如果分配的内存比要申请的内存大，则需要把大块剩余的那一部分

     *分解并放到对应的队列中去

     */

    expand(zone, page, order, current_order, area);

    return page;

    }

    return NULL;

}

    这个函数根据order从最合适的free_area队列中分配，如果不成功就从更大的块中找，找到一个合适的块后把它摘下来，最后需要把大块剩余的那一部分分解并放到对应的队列中去，这个工作是expand函数完成的。