相对与页框慢速分配，快速分配而言。页框释放函数非常简单，主要的函数就是__free_pages()和__free_page()。很明显，类似于之前page分配的上层函数，也是层层wrapper。这里__free_page()是__free_pages()的包装。

#define __free_page(page) __free_pages((page), 0)

void __free_pages(struct page *page, unsigned int order)
{
        if (put_page_testzero(page)) {
                if (order == 0)
                        free_hot_cold_page(page, 0);
                else
                        __free_pages_ok(page, order);
        }
}

通过代码我们发现当要释放的页order==0，直接使用per-cpu缓存释放，大于0使用__free_pages_ok(page, order)释放。

这里kernel使用free_hot_cold_page() 方式释放order为0的页,这个函数只将不可移动页，可回收页和可移动页放入每个CPU页框高速缓存中，如果迁移类型不再这个范围，那么这个页要回收到伙伴系统中！这里的策略是：热页加入表头,冷页加入表尾。这个部分不在本文中叙述，查看代码便知。

来看__free_pages_ok()函数，这个函数也是一个wrapper函数，主要用来检查参数是否正确，做一些释放page前的准备工作。当一切就绪后就会调用free_one_page()函数。大致调用关系是：

static void __free_pages_ok(struct page *page, unsigned int order)
{
....
    free_one_page(page_zone(page), page, pfn, order, migratetype);
....
}
static void free_one_page(struct zone *zone,
                struct page *page, unsigned long pfn,
                unsigned int order,
                int migratetype)
{
    unsigned long nr_scanned;
    spin_lock(&zone->lock);
...
    __free_one_page(page, pfn, zone, order, migratetype);
    spin_unlock(&zone->lock);
}

在调用__free_one_page()之前，kernel换回更新当前zone下面page状态：更新当前内存管理区的空闲页面数，也就是更新zone下面的vm_stat数组，这个数组用于统计当前内存信息。

在核心函数__free_one_page()中，这个函数主要完成page的回收，完成页的合并，首先要获取要释放page的page index

static inline void __free_one_page(struct page *page,
        unsigned long pfn,
        struct zone *zone, unsigned int order,
        int migratetype)
{
    unsigned long page_idx;
    unsigned long combined_idx;
    unsigned long uninitialized_var(buddy_idx);
    struct page *buddy;
    int max_order = MAX_ORDER;

...
    page_idx = pfn & ((1 << max_order) - 1);
...
    while (order < max_order - 1) {
        buddy_idx = __find_buddy_index(page_idx, order);
        buddy = page + (buddy_idx - page_idx);
        if (!page_is_buddy(page, buddy, order))
            break;
        if (page_is_guard(buddy)) {
            clear_page_guard_flag(buddy);
            set_page_private(buddy, 0);
            if (!is_migrate_isolate(migratetype)) {
                __mod_zone_freepage_state(zone, 1 << order,
                              migratetype);
            }
        } else {
            list_del(&buddy->lru);
            zone->free_area[order].nr_free--;
            rmv_page_order(buddy);
        }
        combined_idx = buddy_idx & page_idx;
        page = page + (combined_idx - page_idx);
        page_idx = combined_idx;
        order++;
    }
    set_page_order(page, order);

    if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
        struct page *higher_page, *higher_buddy;
        combined_idx = buddy_idx &amp; page_idx;
        higher_page = page + (combined_idx - page_idx);
        buddy_idx = __find_buddy_index(combined_idx, order + 1);
        higher_buddy = higher_page + (buddy_idx - combined_idx);
        if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
            list_add_tail(&page->lru,
                &zone->free_area[order].free_list[migratetype]);
            goto out;
        }
    list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
out:
    zone->free_area[order].nr_free++;
}

然遍历当前order到max-order所有阶，使用__page_find_buddy()找到当前page_idx的伙伴buddy_idx，然后根据idx偏移量，找到目标buddy。后将这个buddy从list删除，更新nr_free数量。删除buddy标记。最后使用 buddy_idx & page_idx 获取合并后的combined_idx。由于page永远都指向要释放页框块的首页框描述符，所以讲这个combined_idx赋值给page_idx。最后将order+1，然后通过set_page_order()设置这个page的各种信息。

在最新的源码里面，还会判断是否这个page是否是最大的页，如果找到则继续合并，并将合并后page放到list tail中，最后将当前order下的nr_order++。

最后我们来看__find_buddy_index()函数

static inline unsigned long
__find_buddy_index(unsigned long page_idx, unsigned int order)
{
      return page_idx ^ (1 << order);
}

这个函数用来查找buddy的index，这个函数非常简单。

综上所述，所以整个页框分配的核心就是那个while循环，我们可以把页框释放当成页框分裂的逆过程，也就是回收order大于0的页：
举例：

page_idx = 10 -> buddy_idx = 11 -> combined_idx = 10
page_idx = 10 -> buddy_idx = 8 -> combined_idx = 8
page_idx = 8 -> buddy_idx = 12 -> combined_idx = 8
page_idx = 8 -> buddy_idx = 0 -> combined_idx = 0
->无法继续进行->结束

这就是那些位操作的实际含义，page_idx以二倍速率寻找buddy page然后合并，至此伙伴系统回收页框完毕。

参考：

http://blog.csdn.net/vanbreaker/article/details/7624628

在快速分配函数中，大部分代码都是一些具体策略的实现，包括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的伙伴系统，这个时候迁移类型是指定的，如图：

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

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