本文为原创，转载请注明：http://www.cnblogs.com/tolimit/
之前的文章已经介绍了伙伴系统，这篇我们主要看看源码中是如何初始化伙伴系统、从伙伴系统中分配页框，返回页框于伙伴系统中的。
我们知道，每个管理区都有自己的伙伴系统管理属于这个管理区的页框，这也说明了，在伙伴系统初始化时，管理区必须要已经存在(初始化完成)了。在管理区描述符(struct zone)中，struct free_area就专门用于描述伙伴系统的。在一个管理区中，伙伴系统一共维护着包含1,2,4,8,16,...,512,1024个连续页框的链表，当我需要从此管理区分配8个页框时，伙伴系统会从包含8个连续页框的链表取出一个结点(一个结点就是一个连续的8个页框)，然后分配给我。这时如果8个连续页框的链表为空，则会从16个连续页框的链表取出一个结点将其分为两个8个连续页框的结点，并把它们放入8页框的链表，然后再分配其中一个结点给我。而当回收页框时，会尝试与前后连续页框组成更大的页框块，加入到更高级的页框页表中，比如，我释放了8个页框，伙伴系统会尝试将我释放这连续的8个页框与前8个页框或者后8个页框合并，一直尝试合并到不能合并为止，并加入相应的链表中。
而注意的是，在系统中，需要向伙伴系统申请页框时，页框的数量都是以2的次方计算的，也就是申请页框的数量一定是1,2,4,8,16,32,64......1024这些数中的一个。释放时也是这样的道理，不过一般而言，会从伙伴系统中申请页框操作最频繁的模块可能就是slab/slub和建立进程的线性区了。
/* 内存管理区描述符 */
struct zone { ........ /* 实现每CPU页框高速缓存，里面包含每个CPU的单页框的链表 */
struct per_cpu_pageset __percpu *pageset; ........ /* 对应于伙伴系统中MIGRATE_RESEVE链的页块的数量 */
int nr_migrate_reserve_block; ........ /* 标识出管理区中的空闲页框块，用于伙伴系统 */
/* MAX_ORDER为11，分别代表包含大小为1,2,4,8,16,32,64,128,256,512,1024个连续页框的链表，具体见下面 */
struct free_area free_area[MAX_ORDER]; ...... } /* 伙伴系统的一个块，描述1,2,4,8,16,32,64,128,256,512或1024个连续页框的块 */
struct free_area {
/* 指向这个块中所有空闲小块的第一个页描述符，这些小块会按照MIGRATE_TYPES类型存放在不同指针里 */
struct list_head free_list[MIGRATE_TYPES];
/* 空闲小块的个数 */
unsigned long nr_free;
};
/* 每CPU高速缓存描述符 */
struct per_cpu_pageset {
/* 核心结构，高速缓存页框结构 */
struct per_cpu_pages pcp;
#ifdef CONFIG_NUMA
s8 expire;
#endif
#ifdef CONFIG_SMP
s8 stat_threshold;
s8 vm_stat_diff[NR_VM_ZONE_STAT_ITEMS];
#endif
}; struct per_cpu_pages {
/* 当前CPU高速缓存中页框个数 */
int count; /* number of pages in the list */
/* 上界，当此CPU高速缓存中页框个数大于high，则会将batch个页框放回伙伴系统 */
int high; /* high watermark, emptying needed */
/* 在高速缓存中将要添加或被删去的页框个数，当链表中页框数量多个上界时会将batch个页框放回伙伴系统，当链表中页框数量为0时则从伙伴系统中获取batch个页框 */
int batch; /* chunk size for buddy add/remove */ /* Lists of pages, one per migrate type stored on the pcp-lists */
/* 页框的链表，如果需要冷高速缓存，从链表尾开始获取页框，如果需要热高速缓存，从链表头开始获取页框 */
struct list_head lists[MIGRATE_PCPTYPES];
};
在各个页框块链表中又有几个以MIGRATE_TYPES区分的小链表，MIGRATE_TYPES类型如下：
- MIGRATE_UNMOVABLE：页框内容不可移动,在内存中位置必须固定，无法移动到其他地方，核心内核分配的大部分页面都属于这一类。
- MIGRATE_RECLAIMABLE：页框内容可回收,不能直接移动，但是可以回收，因为还可以从某些源重建页面，比如映射文件的数据属于这种类别，kswapd会按照一定的规则，周期性的回收这类页面。
-
MIGRATE_MOVABLE：页框内容可移动，属于用户空间应用程序的页属于此类页面，它们是通过页表映射的，因此我们只需要更新页表项，并把数据复制到新位置就可以了，当然要注意，一个页面可能被多个进程共享，对应着多个页表项。
- MIGRATE_PCPTYPES：用来表示每CPU页框高速缓存的数据结构中的链表的迁移类型数目。
- MIGRATE_CMA： 预留一段的内存给驱动使用，但当驱动不用的时候，伙伴系统可以分配给用户进程用作匿名内存或者页缓存。而当驱动需要使用时，就将进程占用的内存通过回收或者迁移的方式将之前占用的预留内存腾出来，供驱动使用。
- MIGRATE_ISOLATE：不能从这个链表分配页框，因为这个链表专门用于NUMA结点移动物理内存页，将物理内存页内容移动到使用这个页最频繁的CPU。
/* 这几个链表主要用于反内存碎片 */
enum {
MIGRATE_UNMOVABLE, /* 页框内容不可移动,在内存中位置必须固定，无法移动到其他地方，核心内核分配的大部分页面都属于这一类。 */
MIGRATE_RECLAIMABLE, /* 页框内容可回收,不能直接移动，但是可以回收，因为还可以从某些源重建页面，比如映射文件的数据属于这种类别，kswapd会按照一定的规则，周期性的回收这类页面。 */
MIGRATE_MOVABLE, /* 页框内容可移动，属于用户空间应用程序的页属于此类页面，它们是通过页表映射的，因此我们只需要更新页表项，并把数据复制到新位置就可以了
* 当然要注意，一个页面可能被多个进程共享，对应着多个页表项。
*/
MIGRATE_PCPTYPES, /* 用来表示每CPU页框高速缓存的数据结构中的链表的迁移类型数目 */
MIGRATE_RESERVE = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
MIGRATE_CMA, /* 预留一段的内存给驱动使用，但当驱动不用的时候，伙伴系统可以分配给用户进程用作匿名内存或者页缓存。而当驱动需要使用时，就将进程占用的内存通过回收或者迁移的方式将之前占用的预留内存腾出来，供驱动使用。 */
#endif
#ifdef CONFIG_MEMORY_ISOLATION
MIGRATE_ISOLATE, /* 不能从这个链表分配页框，因为这个链表专门用于NUMA结点移动物理内存页，将物理内存页内容移动到使用这个页最频繁的CPU */
#endif
MIGRATE_TYPES
};
很简单地看出，相应类型的页要从相应的链表中获取，而它们之间也是有一定的优先级顺序的：
static int fallbacks[MIGRATE_TYPES][] = {
[MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
#ifdef CONFIG_CMA
[MIGRATE_MOVABLE] = { MIGRATE_CMA, MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
[MIGRATE_CMA] = { MIGRATE_RESERVE }, /* Never used */
#else
[MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
#endif
[MIGRATE_RESERVE] = { MIGRATE_RESERVE }, /* Never used */
#ifdef CONFIG_MEMORY_ISOLATION
[MIGRATE_ISOLATE] = { MIGRATE_RESERVE }, /* Never used */
#endif
};
以MIGRATE_RECLAIMABLE为例，如果我需要申请这种页框，当然会优先从这类页框的链表中获取，如果没有，我会依次尝试从MIGRATE_UNMOVABLE -> MIGRATE_MOVABLE -> MIGRATE_RESERVE链进行分配。
之前的文章也有提到页描述符，它用于描述一个物理页框，所有的页描述符保存在mem_map数组中，通过页框号可以直接获取它对应的页描述符(以页框号做mem_map数组下标获取的就是对应的页描述符)，通过页描述符我们可以确定物理页框所在位置，所以在伙伴系统中，保存在链表中的结点，就是这组连续页框的首个页框的页描述符。
初始化伙伴系统
在初始化伙伴系统之前，所有的node和zone的描述符都已经初始化完毕，同时物理内存中所有的页描述符页相应的初始化为了MIGRATE_MOVABLE类型的页。
初始化过程中首先将所有管理区的伙伴系统链表置空，这些工作处于start_kernel() -> setup_arch() -> x86_init.paging.pagetable_init()中进行：
//以下代码处于free_area_init_core()函数中 /* 将管理区ZONE的伙伴系统置空 */
static void __meminit zone_init_free_lists(struct zone *zone)
{
unsigned int order, t; for (order = ; order < MAX_ORDER; order++)
for (type = ; type < MIGRATE_TYPES; type++) {
INIT_LIST_HEAD(&zone->free_area[order].free_list[t]);
zone->free_area[order].nr_free = ;
}
} void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
unsigned long start_pfn, enum memmap_context context)
{
........
/* 该区所有页都设置为MIGRATE_MOVABLE */
if ((z->zone_start_pfn <= pfn) && (pfn < zone_end_pfn(z)) && !(pfn & (pageblock_nr_pages - )))
set_pageblock_migratetype(page, MIGRATE_MOVABLE); ........
}
初始化高端内存区
在伙伴系统的初始化过程中，X86下高端内存和低端内存的伙伴系统初始化是分开来进行的，顺序是从高端内存区到低端内存区，在初始化伙伴系统之前，系统中的node、zone、page都已经初始化完成了，基本上伙伴系统的初始化就是将所有不用的页框释放回伙伴系统中。我们先看看高端内存区的伙伴系统初始化，主要在set_highmem_pages_init(void)函数中：
/* 所有高端内存管理区初始化，将所有node的所有zone的managed_pages置为0，并将他们的页框回收到页框分配器中 */
void __init set_highmem_pages_init(void)
{
struct zone *zone;
int nid; /* 将所有node的所有zone的managed_pages置为0，即将所有管理区的所管理页数量设置为0 */
reset_all_zones_managed_pages(); /* 遍历所有管理区，这里只初始化高端内存区 */
for_each_zone(zone) {
unsigned long zone_start_pfn, zone_end_pfn; /* 如果不是高端内存区，则下一个 */
/* 判断方法: 当前zone描述符地址 - 所属node的zone描述符数组基地址 == 高端内存区偏移量 */
if (!is_highmem(zone))
continue; /* 该管理区开始页框号 */
zone_start_pfn = zone->zone_start_pfn;
/* 该管理区结束页框号 */
zone_end_pfn = zone_start_pfn + zone->spanned_pages; /* 该管理区所属的node结点号 */
nid = zone_to_nid(zone);
printk(KERN_INFO "Initializing %s for node %d (%08lx:%08lx)\n",
zone->name, nid, zone_start_pfn, zone_end_pfn); /* 将start_pfn到end_pfn中所有页框回收，并放入页框分配器 */
add_highpages_with_active_regions(nid, zone_start_pfn,
zone_end_pfn);
}
}
我们具体看add_highpages_with_active_regions函数：
/* 将start_pfn到end_pfn中所有页框回收，并放入页框分配器 */
void __init add_highpages_with_active_regions(int nid,
unsigned long start_pfn, unsigned long end_pfn)
{
phys_addr_t start, end;
u64 i; /* 遍历所有memblock.memory，此结构有e820传递的数据初始化成，每个node会是其中一个这种结构 */
for_each_free_mem_range(i, nid, &start, &end, NULL) {
/* 修正后第一个页框号，因为有可能页框号不在node上 */
unsigned long pfn = clamp_t(unsigned long, PFN_UP(start),
start_pfn, end_pfn);
/* 修正后最后一个页框号 */
unsigned long e_pfn = clamp_t(unsigned long, PFN_DOWN(end),
start_pfn, end_pfn);
for ( ; pfn < e_pfn; pfn++)
if (pfn_valid(pfn))
/* 这里会将页框回收到页框分配器中 */
free_highmem_page(pfn_to_page(pfn));
}
}
继续
void free_highmem_page(struct page *page)
{ __free_reserved_page(page);
/* 系统中总页数量++ */
totalram_pages++;
/* 页所属的管理区的managed_pages++ */
page_zone(page)->managed_pages++;
/* 高端内存页数量++ */
totalhigh_pages++;
} static inline void __free_reserved_page(struct page *page)
{
ClearPageReserved(page);
/* page->_count = 1 */
init_page_count(page);
/* 释放到伙伴系统中，之后给出详细代码 */
__free_page(page);
}
到这里整个高端内存区的伙伴系统就初始化完成了，关于__free_page()函数我们之后会说明，这个函数是伙伴系统的是否单个页框的API。
初始化低端内存区(ZONE_DMA、ZONE_NORMAL)
在系统初始化阶段会先启用一个bootmem分配器，此分配器是专门用于启动阶段的，一个bootmem分配器管理着一个node结点的所有内存，也就是在numa架构中多个node有多个bootmem，他们被链入bdata_list链表中保存。而伙伴系统的初始化就是将bootmem管理的所有物理页框释放到伙伴系统中去。
我们先看看bootmem的struct bootmem_data结构：
/* bootmem分配器结点(管理着一整块连续内存，可以管理一个node中所有的物理内存)，启动时使用 */
typedef struct bootmem_data {
/* 此块内存开始页框号 */
unsigned long node_min_pfn;
/* 此块内存结束页框号，如果是32位系统下此保存的是 ZONE_NORMAL最后一个页框号 */
unsigned long node_low_pfn;
/* 指向位图内存区，node中所有ZONE_HIGHMEM之前的页框都在这里面有一个位，每次需要分配内存时就会扫描找出一个空闲页框，空洞的内存也会占用位，不过空洞的内存应该设置为已分配 */
void *node_bootmem_map;
/* 上次分配距离末尾的偏移量 */
unsigned long last_end_off;
unsigned long hint_idx;
/* 链入bdata_list结构链表 */
struct list_head list;
} bootmem_data_t;
bootmem分配器核心就是node_bootmem_map这个位图，每一位代表这个node的一个页，当需要分配时就会扫描这个位图，然后获取一段物理页框进行分配，一般都会从开始处向后进行分配，并没有什么特殊的算法在其中。而伙伴系统初始化时页会根据这个位图，将位图中空闲的页释放回到伙伴系统中，而已经分配出去的页则不会在初始化阶段释放回伙伴系统，不过有可能会在系统运行过程中释放回伙伴系统中，我们具体看看是如何实现初始化的：
/* 释放所有启动后不需要的内存到页框分配器 */
unsigned long __init free_all_bootmem(void)
{
unsigned long total_pages = ;
/* 系统会为每个node分配一个这种结构，这个管理着node中所有页框，可以叫做bootmem分配器 */
bootmem_data_t *bdata; /* 设置所有node的所有zone的managed_pages = 0，该函数在启动时只会调用一次，如果初始化高端内存的伙伴系统时调用过，这里就不会再次调用了 */
reset_all_zones_managed_pages(); /* 遍历所有需要释放的启动内存数据块 */
list_for_each_entry(bdata, &bdata_list, list)
/* 释放bdata启动内存块中所有页框到页框分配器 */
total_pages += free_all_bootmem_core(bdata); /* 所有内存页数量 */
totalram_pages += total_pages; /* 返回总共释放的页数量 */
return total_pages;
}
继续，主要看free_all_bootmem_core()函数：
/* 释放bdata启动内存块中所有页框到页框分配器 */
static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata)
{
struct page *page;
unsigned long *map, start, end, pages, count = ; /* 此bootmem没有位图，也就是没有管理内存 */
if (!bdata->node_bootmem_map)
return ; /* 此bootmem的位图 */
map = bdata->node_bootmem_map;
/* 此bootmem包含的开始页框 */
start = bdata->node_min_pfn;
/* 此bootmem包含的结束页框 */
end = bdata->node_low_pfn; bdebug("nid=%td start=%lx end=%lx\n",
bdata - bootmem_node_data, start, end); /* 释放 bdata->node_min_pfn 到 bdata->node_low_pfn 之间空闲的页框到伙伴系统 */
while (start < end) {
unsigned long idx, vec;
unsigned shift; /* 一次循环检查long所占位数长度的页框数量(32或64) */
idx = start - bdata->node_min_pfn;
shift = idx & (BITS_PER_LONG - ); /* 做个整理，因为有可能start并不是按long位数对其的，有可能出现在了vec的中间位数 */
vec = ~map[idx / BITS_PER_LONG]; if (shift) {
vec >>= shift;
if (end - start >= BITS_PER_LONG)
vec |= ~map[idx / BITS_PER_LONG + ] <<
(BITS_PER_LONG - shift);
} /* 如果检查的这一块内存块全是空的，则一次性释放 */
if (IS_ALIGNED(start, BITS_PER_LONG) && vec == ~0UL) {
/* 这一块长度的内存块都为空闲的，计算这块内存的order，如果这块内存块长度是8个页框，那order就是3(2的3次方) */
int order = ilog2(BITS_PER_LONG); /* 从start开始，释放2的order次方的页框到伙伴系统 */
__free_pages_bootmem(pfn_to_page(start), order);
/* count用来记录总共释放的页框 */
count += BITS_PER_LONG;
/* 开始位置向后移动 */
start += BITS_PER_LONG;
} else {
/* 内存块中有部分是页框是空的，一页一页释放 */
unsigned long cur = start; start = ALIGN(start + , BITS_PER_LONG);
while (vec && cur != start) {
if (vec & ) {
/* 获取页框描述符，页框号实际上就是页描述符在mem_map的偏移量 */
page = pfn_to_page(cur);
/* 将此页释放到伙伴系统 */
__free_pages_bootmem(page, );
count++;
}
vec >>= ;
++cur;
}
}
}
在__free_pages_bootmem()中也是调用了__free_pages()将页释放到伙伴系统中：
void __init __free_pages_bootmem(struct page *page, unsigned int order)
{
/* 需要释放的页数量 */
unsigned int nr_pages = << order;
struct page *p = page;
unsigned int loop; /* 预取指令，该指令用于把将要使用到的数据从内存提前装入缓存中，以减少访问主存的指令执行时的延迟 */
prefetchw(p);
for (loop = ; loop < (nr_pages - ); loop++, p++) {
/* 预取下一个页描述符 */
prefetchw(p + );
__ClearPageReserved(p);
/* 设置page->_count = 0 */
set_page_count(p, );
}
__ClearPageReserved(p);
set_page_count(p, ); /* 管理区的managed_pages加上这些页数量 */
page_zone(page)->managed_pages += nr_pages;
/* 将首页框的_count设置为1，代表被使用，因为被使用的页框才能够释放 */
set_page_refcounted(page);
/* 释放到管理区的伙伴系统 */
__free_pages(page, order);
}
到这里，高端内存和低端内存的初始化就已经完成了。所以未使用的页框都已经放入伙伴系统*伙伴系统进行管理。之后我们会详细说明申请页框和释放页框的相关的操作。
申请页框
对于申请单个页框而言，系统会从每CPU高速缓存维护的单页框链表中进行分配，而对于申请多个页框，系统则从伙伴系统中进行分配，可以说每CPU高速缓存算是伙伴系统中的一小部分，专门用于分配单个页框，因为系统希望尽量让那些刚释放掉的单页框分配出去，这样可以有效地提高缓存命中率，因为释放掉的页框可能还处于缓存中，而刚分配的页框一般都会马上使用，系统就不用对这些页框换进换出缓存了。因为每个CPU都有自己的高速缓存，所以这个结构就叫每CPU高速缓存。
伙伴系统提供了多个接口供其他模块申请页框使用，如下：
- struct page * alloc_pages (gfp_mask, order)：向伙伴系统请求连续的2的order次方个页框，返回第一个页描述符。
- struct page * alloc_page (gfp_mask)：相当于struct page * alloc_pages(gfp_mask, 0)。
- void * __get_free_pages (gfp_mask, order)：该函数类似于alloc_pages()，但返回第一个所分配页的线性地址。
- void * __get_free_page (gfp_mask)：相当于void * __get_free_pages (gfp_mask, 0)。
对于gfp_mask掩码，有如下这些：
/* 允许内核对等待空闲页框的当前进程进行阻塞 */
#define __GFP_WAIT ((__force gfp_t)___GFP_WAIT)
/* 允许内核访问保留的页框池 */
#define __GFP_HIGH ((__force gfp_t)___GFP_HIGH)
/* 允许内核在低端内存页上执行IO传输 */
#define __GFP_IO ((__force gfp_t)___GFP_IO)
/* 如果清0，则不允许内核执行依赖于文件系统的操作 */
#define __GFP_FS ((__force gfp_t)___GFP_FS)
/* 所请求的页框可能是"冷"的 */
#define __GFP_COLD ((__force gfp_t)___GFP_COLD)
/* 一次内存分配失败将不会产生警告 */
#define __GFP_NOWARN ((__force gfp_t)___GFP_NOWARN)
#define __GFP_REPEAT ((__force gfp_t)___GFP_REPEAT)
/* 同上 */
#define __GFP_NOFAIL ((__force gfp_t)___GFP_NOFAIL)
/* 一次分配失败后不再重试 */
#define __GFP_NORETRY ((__force gfp_t)___GFP_NORETRY)
#define __GFP_MEMALLOC ((__force gfp_t)___GFP_MEMALLOC)
/* 属于扩展页的页框 */
#define __GFP_COMP ((__force gfp_t)___GFP_COMP)
/* 任何返回的页框必须被填满0 */
#define __GFP_ZERO ((__force gfp_t)___GFP_ZERO)
而这些类型进行一些组合，会产生如下的一些掩码：
/* 原子分配，分配期间不会进行阻塞 */
#define GFP_ATOMIC (__GFP_HIGH)
#define GFP_NOIO (__GFP_WAIT)
#define GFP_NOFS (__GFP_WAIT | __GFP_IO)
#define GFP_KERNEL (__GFP_WAIT | __GFP_IO | __GFP_FS)
#define GFP_TEMPORARY (__GFP_WAIT | __GFP_IO | __GFP_FS | \
__GFP_RECLAIMABLE)
#define GFP_USER (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL)
#define GFP_HIGHUSER (__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL | \
__GFP_HIGHMEM)
#define GFP_HIGHUSER_MOVABLE (__GFP_WAIT | __GFP_IO | __GFP_FS | \
__GFP_HARDWALL | __GFP_HIGHMEM | \
__GFP_MOVABLE)
#define GFP_IOFS (__GFP_IO | __GFP_FS)
#define GFP_TRANSHUGE (GFP_HIGHUSER_MOVABLE | __GFP_COMP | \
__GFP_NOMEMALLOC | __GFP_NORETRY | __GFP_NOWARN | \
__GFP_NO_KSWAPD)
好了，我们主要看申请页框的接口，这些接口最后都会调用到__alloc_pages_nodemask()函数，这里我只用alloc_pages()函数进行讲解，我们先看从alloc_pages()如何到__alloc_pages_nodemask()函数的：
/* 分配页框
* gfp_mask: 标志
* order: 需求2的次方个数页框
*/
#define alloc_pages(gfp_mask, order) \
alloc_pages_node(numa_node_id(), gfp_mask, order) static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
unsigned int order)
{
/* Unknown node is current node */
if (nid < )
nid = numa_node_id(); /* 根据node号获取此node相应的zonelist，因为如果此node上没法分配出多余的内存，会从zonelist的其他node的zone中分配 */
return __alloc_pages(gfp_mask, order, node_zonelist(nid, gfp_mask));
} static inline struct page *
__alloc_pages(gfp_t gfp_mask, unsigned int order,
struct zonelist *zonelist)
{
/* 最后调用到的函数 */
return __alloc_pages_nodemask(gfp_mask, order, zonelist, NULL);
}
在node中会有多个zonelist，这个zonelist的作用是将所有的zone按相对于此node的优先级进行排序，链表头4个就是此node的ZONE_MOVABLE、ZONE_HIGHMEM、ZONE_NORMAL、ZONE_DMA，之后是排在此node之后的node的这4个管理区。然后再是排在此node之前的node的这4个管理区。在分配时就按照这个顺序，直到分配出相应数量的页框为止。
在同一个node中的管理区中分配也有一定的顺序，当我需要从高端内存区申请内存时，系统会按照 ZONE_HIGHMEM -> ZONE_NORMAL -> ZONE_DMA 顺序为我尝试分配，而当我需要从ZONE_NORMAL区申请内存时，系统会按照ZONE_NORMAL -> ZONE_DMA 顺序为我尝试分配，当我需要从ZONE_DMA区申请内存时，系统只会从ZONE_DMA区为我分配。在NUMA架构里也是一样，只会在其他node上的相应的管理区中分配内存。
接下来我们要着重说明__alloc_pages_nodemask()函数。
__alloc_pages_nodemask()
此函数可以说是页框分配的心脏，里面组织了整个分配过程中遇到各种问题时的处理情况。
伙伴系统的页框分配方式主要有两种：快速分配和慢速分配。
- 快速分配：会根据zonelist链表的优先级顺序，以zone的low阀值从相应zone的伙伴系统中分配连续页框。
- 慢速分配：在快速分配失败之后执行，页会根据zonelist链表的优先级顺序，以zone的min阀值从相遇zone的伙伴系统中分配连续页框，如果失败，会唤醒kswapd内核线程，进行页框的回收、页框的异步压缩和轻同步压缩，以及oom等操作来使系统获得更多的空闲页框，并且在这些操作的过程中会调用快速分配尝试获取内存。
伙伴系统分配可用页框给申请者时，首先会根据zonelist对每个可用的zone进行快速分配，成功则返回第一个页框的页描述符，如果所有zone的快速分配都不成功，则会zonelist中的zone进行慢速分配，慢速分配中会进行内存回收、内存压缩和唤醒kswapd线程也同时进行内存的回收工作，之后再尝试继续分配。我们先看看__alloc_pages_nodemask()源码：
/* gfp_mask: 上层要求分配内存时使用的标志
* order: 需要的连续页框的order值，如果是1个页框，则为0
* zonelist: 合适的zone列表
* nodemask: node结点掩码，用于判断允许从哪些node上分配
*/
struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
struct zonelist *zonelist, nodemask_t *nodemask)
{
enum zone_type high_zoneidx = gfp_zone(gfp_mask);
/* preferred_zone指向第一个合适的管理区 */
struct zone *preferred_zone;
struct zoneref *preferred_zoneref;
struct page *page = NULL;
/* 从gfp_mask中获取选定的页框类型，当中只会检查__GFP_MOVABLE和__GFP_RECLAIMABLE */
int migratetype = gfpflags_to_migratetype(gfp_mask);
unsigned int cpuset_mems_cookie;
/* 这个需要注意一下，之后分配是会根据这个flags进行一定的操作，默认是使用zone的低阀值判断是否需要进行内存回收 */
int alloc_flags = ALLOC_WMARK_LOW|ALLOC_CPUSET|ALLOC_FAIR;
int classzone_idx; gfp_mask &= gfp_allowed_mask; lockdep_trace_alloc(gfp_mask); /* 如果设置了__GFP_WAIT，就检查当前进程是否需要调度，如果要则会进行调度
* 大多数情况的分配都会有__GFP_WAIT标志
*/
might_sleep_if(gfp_mask & __GFP_WAIT); /* 检查gfp_mask和order是否符合要求，就是跟fail_page_alloc里面每一项对比检查 */
if (should_fail_alloc_page(gfp_mask, order))
return NULL; /* 检查结点的管理区链表是否为空 */
if (unlikely(!zonelist->_zonerefs->zone))
return NULL; /* 如果使能了CMA，选定的页框类型是可迁移的页框，就在标志上加上ALLOC_CMA */
if (IS_ENABLED(CONFIG_CMA) && migratetype == MIGRATE_MOVABLE)
alloc_flags |= ALLOC_CMA; retry_cpuset:
/* 这里只是表明在这个顺序锁中是个读者 */
cpuset_mems_cookie = read_mems_allowed_begin(); /* The preferred zone is used for statistics later */
/* 获取链表中第一个管理区，每一次retry_cpuset就是在一个管理区中进行分配
* preferred_zone指向第一个合适的管理区
*/
preferred_zoneref = first_zones_zonelist(zonelist, high_zoneidx,
nodemask ? : &cpuset_current_mems_allowed,
&preferred_zone);
if (!preferred_zone)
goto out; /* 管理区的类型的偏移量，0是 ZONE_DMA , 1是 ZONE_NORMAL , 2是 ZONE_HIGHMEM , 3是 ZONE_MOVABLE */
classzone_idx = zonelist_zone_idx(preferred_zoneref); /* 第一次尝试分配页框，这里是快速分配
* 快速分配时以low阀值为标准
* 遍历zonelist，尝试获取2的order次方个连续的页框
* 在遍历zone时，如果此zone当前空闲内存减去需要申请的内存之后，空闲内存是低于low阀值，那么此zone会进行快速内存回收
*/
page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order,
zonelist, high_zoneidx, alloc_flags,
preferred_zone, classzone_idx, migratetype); if (unlikely(!page)) {
/* 如果没有分配到所需连续的页框，这里会尝试第二次分配，这次是慢速分配，并且同样分配时不允许进行IO操作
* 如果当前进程current->flags标志了PF_MEMALLOC_NOIO标志，表示进程获取内存时禁止IO操作，则返回清除了__GFP_IO和__GFP_FS的gfp_mask
* 而gfp_mask绝大多数情况都是允许__GFP_IO和__GFP_FS标志的
*/
gfp_mask = memalloc_noio_flags(gfp_mask);
/* 如果之前没有分配成功，这里尝试进入慢速分配，在这个函数中，会尝试唤醒页框回收线程，然后再进行分配
* 慢速分配首先会唤醒kswapd线程进行内存回收
* 然后如果标记了忽略阀值，则从保留的内存里回收
* 然后进行内存压缩
* 最后再尝试直接内存回收
*/
page = __alloc_pages_slowpath(gfp_mask, order,
zonelist, high_zoneidx, nodemask,
preferred_zone, classzone_idx, migratetype);
} trace_mm_page_alloc(page, order, gfp_mask, migratetype); out:
/* 如果都没有分配成功，这里会不停尝试重新分配，获取下一个zonelist的zone */
if (unlikely(!page && read_mems_allowed_retry(cpuset_mems_cookie)))
goto retry_cpuset;
/* 返回第一个页描述符 */
return page;
}
快速分配的函数是get_page_from_freelist()，可以说这个函数是最基本的获取页框函数，只要需要获取页框，就一定要调用这个函数，即使在慢速分配过程中想要获取页框，也需要调用这个函数进行获取。我们看看：
/* 从管理区链表中遍历所有管理区，获取指定连续的页框数
* 在遍历管理区时，如果此zone当前空闲内存减去需要申请的内存之后，空闲内存是低于low阀值，那么此zone会进行快速内存回收
* 第一轮循环会尝试只从preferred_zone这个zone中获取连续页框，如果无法获取，会进入第二轮循环
* 第二轮循环会遍历整个zonelist中的zone，从里面获取连续页框
*/
static struct page *
get_page_from_freelist(gfp_t gfp_mask, nodemask_t *nodemask, unsigned int order,
struct zonelist *zonelist, int high_zoneidx, int alloc_flags,
struct zone *preferred_zone, int classzone_idx, int migratetype)
{
struct zoneref *z;
struct page *page = NULL;
struct zone *zone;
nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
int zlc_active = ; /* set if using zonelist_cache */
int did_zlc_setup = ; /* just call zlc_setup() one time */
/* 是否考虑脏页过多的判断值，如果脏页过多，则不在此zone进行分配 */
bool consider_zone_dirty = (alloc_flags & ALLOC_WMARK_LOW) &&
(gfp_mask & __GFP_WRITE);
int nr_fair_skipped = ;
bool zonelist_rescan; zonelist_scan:
zonelist_rescan = false; /* 遍历结点中的管理区，如果要求从高端内存分配，则顺序为ZONE_HighMen -> ZONE_NORMAL -> ZONE_DMA
* 如果没要求从高端内存分配，则顺序为ZONE_NORMAL -> ZONE_DMA
*/
for_each_zone_zonelist_nodemask(zone, z, zonelist,
high_zoneidx, nodemask) {
unsigned long mark; if (IS_ENABLED(CONFIG_NUMA) && zlc_active &&
!zlc_zone_worth_trying(zonelist, z, allowednodes))
continue; /* 检查此管理区是否属于该CPU所允许分配的管理区 */
if (cpusets_enabled() &&
(alloc_flags & ALLOC_CPUSET) &&
!cpuset_zone_allowed_softwall(zone, gfp_mask))
continue; /* 公平分配，标记了ALLOC_FAIR的情况，会只从preferred_zone这个zone所在node
* 所以第一轮循环，会只尝试从preferred_zone所在node进行分配
* 而第二轮循环，会遍历整个zonelist里的包含的其他node的zone
*/
if (alloc_flags & ALLOC_FAIR) {
/* 判断zone和preferred_zone是否属于同一个node，不属于则跳出循环，因为后面的页不会属于此node了 */
if (!zone_local(preferred_zone, zone))
break;
/* 此zone属于此node，看看ZONE_FAIR_DEPLETED标记有没有置位，置位了说明此zone可用于其他zone的页框数量已经用尽 */
if (test_bit(ZONE_FAIR_DEPLETED, &zone->flags)) {
nr_fair_skipped++;
continue;
}
} /* 如果gfp_mask中允许进行脏页回写，那么如果此zone在内存中有过多的脏页，则跳过此zone，不对此zone进行处理
* 这里大概意思是脏页过多，kswapd会将这些脏页进行回写，这里就不将这些脏页进行回写了，会增加整个zone的压力
*/
if (consider_zone_dirty && !zone_dirty_ok(zone))
continue; /* 选择阀值，阀值保存在管理区的watermark中，分别有alloc_min alloc_low alloc_high三种，选择任何一种都会要求分配后空闲页框数量不能少于阀值，默认是alloc_low */
mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK]; /* 根据阀值查看管理区中是否有足够的空闲页框，空闲内存数量保存在 zone->vm_stat[NR_FREE_PAGES]，这里的检查算法是: 分配后剩余的页框数量是否大于阀值加上此zone保留的内存数量，高于则返回true
* 三个阀值的大小关系是min < low < high
* high一般用于判断zone是否平衡
* 快速分配时，用的阀值是low
* 慢速分配中，用的阀值是min
* 在准备oom进程时，用的阀值是high
* 分配后剩余的页框数量低于或等于阀值加上此zone保留的内存数量，那么进行快速内存回收
*/
if (!zone_watermark_ok(zone, order, mark,
classzone_idx, alloc_flags)) {
/* 没有足够的空闲页框 */
int ret; BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
/* 如果分配标志中有 ALLOC_NO_WATERMARKS标志，代表无视阀值，直接分配 */
if (alloc_flags & ALLOC_NO_WATERMARKS)
goto try_this_zone; if (IS_ENABLED(CONFIG_NUMA) &&
!did_zlc_setup && nr_online_nodes > ) {
/* NUMA系统中如果使用了zlc(zonelist_cache)，则取出此zonelist允许的node列表 */
allowednodes = zlc_setup(zonelist, alloc_flags);
zlc_active = ;
did_zlc_setup = ;
} /*
* 判断是否对此zone进行内存回收，如果开启了内存回收，则会对此zone进行内存回收，否则，通过距离判断是否进行内存回收
* zone_allows_reclaim()函数实际上就是判断zone所在node是否与preferred_zone所在node的距离 < RECLAIM_DISTANCE(30或10)
* 当内存回收未开启的情况下，只会对距离比较近的zone进行回收
*/
if (zone_reclaim_mode == ||
!zone_allows_reclaim(preferred_zone, zone))
goto this_zone_full; if (IS_ENABLED(CONFIG_NUMA) && zlc_active &&
!zlc_zone_worth_trying(zonelist, z, allowednodes))
continue; /*
* 这里就叫做快速回收，因为这里会选择尽量快的回收方式
* 回收到了2^order数量的页框时，才会返回真，即使回收了，没达到这个数量，也返回假
*/
ret = zone_reclaim(zone, gfp_mask, order);
switch (ret) {
case ZONE_RECLAIM_NOSCAN: /* 没有进行回收 */
/* did not scan */
continue;
case ZONE_RECLAIM_FULL: /* 没有找到可回收的页面，也就是回收到的页框数量为0 */
/* scanned but unreclaimable */
continue;
default:
/* 回收到了一些或者回收到了2^order个页框，都会执行到这 */ /* did we reclaim enough */
/* 回收到了一些页，这里继续检查阀值是否足够分配连续页框，足够则跳到 try_this_zone 尝试在此zone中分配 */
if (zone_watermark_ok(zone, order, mark,
classzone_idx, alloc_flags))
goto try_this_zone; /* 如果是按照min阀值进行分配的(在慢速分配中会尝试)，或者从此zone回收到一些页框了(但不足以分配)，则跳到this_zone_full，标记此zone */
if (((alloc_flags & ALLOC_WMARK_MASK) == ALLOC_WMARK_MIN) ||
ret == ZONE_RECLAIM_SOME)
goto this_zone_full; continue;
}
} try_this_zone:
/* 尝试从这个zone获取连续页框
* 只有当此zone中空闲页框数量 - 本次需要分配的数量 > 此zone的low阀值，这样才能执行到这
* 如果本意从preferred_zone分配内存，但是preferred_zone没有足够内存，到到了此zone进行分配，那么分配的页数量会统计到此zone的NR_ALLOC_BATCH
*/
page = buffered_rmqueue(preferred_zone, zone, order,
gfp_mask, migratetype);
/* 分配到了连续页框，跳出循环 */
if (page)
break;
this_zone_full:
if (IS_ENABLED(CONFIG_NUMA) && zlc_active)
/* 在zonelist的zonelist_cache中标记此node为满状态 */
zlc_mark_zone_full(zonelist, z);
} /* 分配到了连续页框 */
if (page) {
/* 如果分配时有 ALLOC_NO_WATERMARKS 标记则记录到页描述符中 */
page->pfmemalloc = !!(alloc_flags & ALLOC_NO_WATERMARKS);
/* 将连续页框中第一个页的页描述符返回 */
return page;
} /* 这里是失败时才会到这 */
/* 如果第一次ALLOC_FAIR分配没有能够分配到内存，第二次尝试非ALLOC_FAIR分配
* 第二次会遍历zonelist中其他node上的zone
* 而第一次公平分配不会
*/
if (alloc_flags & ALLOC_FAIR) {
alloc_flags &= ~ALLOC_FAIR;
/* nr_fair_skipped不为0，说明此node有些zone的batch页已经用尽，这里要增加一些给它 */
if (nr_fair_skipped) {
zonelist_rescan = true;
/* 重新设置除目标zone之外，node中在此目标zone前面的zone的batch页数量大小
* 设置为: batch页数量 = high阀值 - 低阀值 - 当前batch数量
*/
reset_alloc_batches(preferred_zone);
}
if (nr_online_nodes > )
zonelist_rescan = true;
} if (unlikely(IS_ENABLED(CONFIG_NUMA) && zlc_active)) {
/* 禁止zonelist_cache，zonelist_cache用于快速扫描的，它标记着哪个node有空闲内存哪个node没有，扫描时就跳过某些node */
zlc_active = ;
zonelist_rescan = true;
} /* 跳回去，尝试再次扫描一遍zonelist，这里最多只会进行一次再次扫描，因为第二次就不会把 zonelist_rescan 设置为true了 */
if (zonelist_rescan)
goto zonelist_scan; return NULL;
}
在快速分配中，如果条件允许会以low阀值遍历两次zonelist中的zone，整个快速分配的流程是：从zonelist中取出一个zone，检查此zone标志判断是否可通过此zone分配内存，如果 zone的空闲内存 - 需要申请的内存 < 阀值 ，伙伴系统则会将zone的一些快速内存回收，然后再次判断阀值和空闲内存与申请内存大小直接的关系，如果 zone的空闲内存 - 需要申请的内存 > 阀值，则调用buffered_rmqueue()函数从此zone中的分配内存，否则，选取下一个zone继续执行这段操作。当zonelist中的所有zone都遍历完成后，还是没有分配到内存，如果条件允许会再次遍历一遍。由于在慢速过程中也会调用此函数进行快速内存分配，所以阀值是由调用者传进来，因为不同情况使用的阀值是不同的，比如第一次快速分配过程中，会使用zone的low阀值进行分配，而进入慢速分配过程中，会使用min阀值进行分配。
对于zone_reclaim函数这里就不详细进行分析了，我们记得在伙伴系统中有一个每CPU高速缓存，里面保存着以migratetype分类的单页框的双向链表，当申请内存者只需要一个页框时，内核会从每CPU高速缓存中相应类型的单页框链表中获取一个页框交给申请者，这样的好处是，但释放单个页框时会放入每CPU高速缓存链表，如果这时有需要申请单个页框，就把这个刚刚释放的页框交付出去，因为这个页框可能还存在于cache中，处理时就可直接处理cache而不用把这个页框再放入cache中，提高了cache的命中率，这样的页框就称为“热”页。每CPU高速缓存维护的这些所有类型的单页框双向链表时，把刚释放的页框从链表头插入，申请“热”页时就从链表头拿出页框，申请“冷”页时则从链表位拿出。我们看看buffered_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) != ); again:
if (likely(order == )) {
/* 这里是只需要分配一个页框，会从每CPU高速缓存中分配 */
struct per_cpu_pages *pcp;
struct list_head *list; local_irq_save(flags);
/* 获取此zone的每CPU高速缓存 */
pcp = &this_cpu_ptr(zone->pageset)->pcp;
/* 获取需要的类型的页框的高速缓存链表，高速缓存中也区分migratetype类型的链表，链表中保存的页框对应的页描述符 */
list = &pcp->lists[migratetype];
if (list_empty(list)) {
/* 如果当前migratetype的每CPU高速缓存链表中没有空闲的页框，从伙伴系统中获取batch个页框加入到这个链表中，batch保存在每CPU高速缓存描述符中，在rmqueue_bulk中是每次要1个页框，要batch次，也就是这些页框是离散的 */
pcp->count += rmqueue_bulk(zone, ,
pcp->batch, list,
migratetype, cold);
if (unlikely(list_empty(list)))
goto failed;
} if (cold)
/* 需要冷的高速缓存，则从每CPU高速缓存的双向链表的后面开始分配 */
page = list_entry(list->prev, struct page, lru);
else
/* 需要热的高速缓存，则从每CPU高速缓存的双向链表的前面开始分配，因为释放时会从链表头插入，所以链表头是热的高速缓存 */
page = list_entry(list->next, struct page, lru);
/* 从每CPU高速缓存链表中拿出来 */
list_del(&page->lru);
pcp->count--;
} else {
/* 需要多个页框，从伙伴系统中分配，但是申请多个页框时是有可能会发生失败的情况的，而分配时又表明__GFP_NOFAIL不允许发生失败，所以这里给出一个警告 */
if (unlikely(gfp_flags & __GFP_NOFAIL)) {
WARN_ON_ONCE(order > );
}
spin_lock_irqsave(&zone->lock, flags);
/* 从伙伴系统中获取连续页框，返回第一个页的页描述符 */
page = __rmqueue(zone, order, migratetype);
spin_unlock(&zone->lock);
if (!page)
goto failed;
/* 统计，减少zone的free_pages数量统计，因为里面使用加法，所以这里传进负数 */
__mod_zone_freepage_state(zone, -( << order),
get_freepage_migratetype(page));
} __mod_zone_page_state(zone, NR_ALLOC_BATCH, -( << order));
if (atomic_long_read(&zone->vm_stat[NR_ALLOC_BATCH]) <= &&
!test_bit(ZONE_FAIR_DEPLETED, &zone->flags))
set_bit(ZONE_FAIR_DEPLETED, &zone->flags); __count_zone_vm_events(PGALLOC, zone, << order);
/* 统计 */
zone_statistics(preferred_zone, zone, gfp_flags);
local_irq_restore(flags); VM_BUG_ON_PAGE(bad_range(zone, page), page);
/* 检查所有分配的连续页框是否为空闲页 */
if (prep_new_page(page, order, gfp_flags))
goto again;
/* 返回第一个页描述符 */
return page; failed:
/* 分配失败 */
local_irq_restore(flags);
return NULL;
}
对于每CPU高速缓存，有可能出现的情况就是链表为空(太多人申请1个页框)，这时候每CPU高速缓存会向伙伴系统连续申请batch次单个页框放入自己的链表中，这里发生在rmqueue_bulk()中。而如果一次申请多个页框，则直接从伙伴系统中获取，也就是__rmqueue()函数。而对于rmqueue_bulk()来说，其核心函数也是__rmqueue()，因为rmqueue_bulk()中也是调用了batch次__rmqueue()获取batch个单页框。
/* 从伙伴系统中获取2的order次方个页框，返回第一个页框的描述符
* zone: 管理区描述符
* order: 需要页面的2的次方数
* migratetype: 从此类型中获取，这时传入的时需求的页框类型
*/
static struct page *__rmqueue(struct zone *zone, unsigned int order,
int migratetype)
{
struct page *page; retry_reserve:
/* 直接从migratetype类型的链表中获取了2的order次方个页框 */
page = __rmqueue_smallest(zone, order, migratetype); /* 如果page为空，没有在需要的migratetype类型中分配获得页框，说明当前需求类型(migratetype)的页框没有空闲，会根据fallback数组中定义好的优先级从其他类型的页框中获取页框，一次移动一个pageblock */
if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
/* 根据fallbacks数组从其他migratetype类型的链表中获取内存 */
page = __rmqueue_fallback(zone, order, migratetype); /* 从其他类型的空闲页框链表中也没有获得页框，设定为默认类型的页框，重试一次 */
if (!page) {
/* 定义从页框属性为MIGRATE_RESERVE的空闲链表中查找 */
migratetype = MIGRATE_RESERVE;
/* 重试尝试从MIGRATE_RESERVE类型的链表中找出空闲内存 */
goto retry_reserve;
}
} trace_mm_page_alloc_zone_locked(page, order, migratetype);
return page;
}
在__rmqueue中，可能会进行两次分配，首先会调用__rmqueue_smallest()进行分配，如果分配失败，则会调用__rmqueue_fallback()进行分配，为什么要这样，就是与前面说的migratetype类型有关，首先调用__rmqueue_smallest()，此函数只会从传入的migratetype类型的链表中进行分配，并不会到其他migratetype类型的链表中获取页框进行分配，而__rmqueue_fallback()则是尝试从将一个其他migratetype类型的pageblock转为我们需要的类型的pageblock，然后尝试进行分配，而最后，我们看当__rmqueue_fallback()函数都无法进行分配时，会将migratetype设置为MIGRATE_RESERVE类型，从此类型中尝试分配，首先先看__rm_queue_smallest()，其实现如下：
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; /* 循环遍历这层之后的空闲链表 */
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);
/* 将首页框的private设置为0 */
rmv_page_order(page);
area->nr_free--;
/* 如果从更高级的页框的链表中分配，这里会将多余的页框放回伙伴系统的链表中，比如我们只需要2个页框，但是这里是从8个连续页框的链表分配给我们的，那其他6个就要拆分为2和4个分别放入链表中 */
expand(zone, page, order, current_order, area, migratetype);
/* 设置页框的类型与migratetype一致 */
set_freepage_migratetype(page, migratetype);
return page;
} return NULL;
}
__rmqueue_smallest()函数中只会对migratetype类型的链表进行操作，并且会从需要的order值开始向上遍历，直到成功分配连续页框或者无法分配连续页框为止，比如order为8，也就是需要连续的256个页框，那会尝试从order为8的空闲页框块链表中申请内存，如果失败，order就会变为9，从连续512个页框的空闲页框块链表中尝试分配，如果还是失败，order就会达到最大的10，然后从连续1024个页框的空闲页框块链表中尝试分配。这里需要注意，如果分配到内存的order与最初的order不相等，比如最初传入的是8，而能够成功分配的是10，那么就会对连续页框进行拆分，这时候会拆为256,256,512这三块连续页框，把512放入order为9的free_list，把一个256放入order为8的free_list，剩余了一个256用于分配。
而当__rm_queue_smallest()无法分配到页框时，说明zone的mirgratetype类型的连续页框不足以分配本次1 << order个连续页框，那么就会调用__rmqueue_fallback()进行分配，在__rmqueue_fallback()函数中，主要根据fallbacks表，尝试将其他migratetype类型的pageblock中的空闲页移动到目标类型的mirgratetype类型的空闲页框块链表中，看代码：
/* Remove an element from the buddy allocator from the fallback list */
/* 根据fallbacks数组中定义的优先级，从其他migratetype类型的链表中获取连续页框，返回第一个页框的页描述符
* start_migratetype是申请页框时需要但是又缺少的类型
*/
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 */
/* 遍历不同order的链表，如果需要分配2个连续页框，则会遍历1024,512,256,128,64,32,16,8,4,2,1这几个链表，注意这里是倒着遍历的 */
for (current_order = MAX_ORDER-;
current_order >= order && current_order <= MAX_ORDER-;
--current_order) {
for (i = ;; i++) { /* 遍历order链表中对应fallbacks优先级的类型链表 */ /* 根据fallbacks和i获取migratetype,start_migratetype是申请页框时需要的类型 */
/*static int fallbacks[MIGRATE_TYPES][4] = {
* [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
* [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
*#ifdef CONFIG_CMA
* [MIGRATE_MOVABLE] = { MIGRATE_CMA, MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
* [MIGRATE_CMA] = { MIGRATE_RESERVE },
*#else
* [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
*#endif
* [MIGRATE_RESERVE] = { MIGRATE_RESERVE },
*#ifdef CONFIG_MEMORY_ISOLATION
* [MIGRATE_ISOLATE] = { MIGRATE_RESERVE },
*#endif
*};
*/
migratetype = fallbacks[start_migratetype][i]; /* MIGRATE_RESERVE handled later if necessary */
/* 这里不能分配MIGRATE_RESERVE类型的内存，这部分内存是保留使用，最后其他的migratetype都没有内存可分配才会分配MIGRATE_RESERVE类型的内存 */
if (migratetype == MIGRATE_RESERVE)
break; /* 当前order的链表，current_order从10 ~ order */
area = &(zone->free_area[current_order]);
/* 链表为空，说明这个链表页没有内存 */
if (list_empty(&area->free_list[migratetype]))
continue; /* 有空余的内存，即将分配 */
/* 从链表中获取第一个节点，但是注意，这里分配的内存可能大于我们需要的数量(从其他order链表中获取的连续页框)，之后会调用expand把多余的放回去 */
page = list_entry(area->free_list[migratetype].next,
struct page, lru);
area->nr_free--; /* 在当前start_migratetype中没有足够的页进行分配时，则会将获取到的migratetype类型的pageblock中的所有空闲页框移动到start_migratetype中，返回获取的页框本来所属的类型
* 只有系统禁止了page_group_by_mobility_disabled或者order > pageblock_order / 2，才会这样做
* 在调用前，page一定是migratetype类型的
* 里面的具体做法是:
* page是属于migratetype类型的pageblock中的一个页，然后函数中会根据page获取其所在的pageblock
* 从pageblock开始的第一页遍历到此pageblock的最后一页
* 然后根据page->_mapcount是否等于-1，如果等于-1，说明此页在伙伴系统中，不等于-1则下一页
* 对page->_mapcount == -1的页获取order值，order值保存在page->private中，然后将这一段连续空闲页框移动到start_type类型的free_list中
* 对这段连续空闲页框首页设置为start_type类型，这样就能表示此段连续空闲页框都是此类型了，通过page->index = start_type设置
* 继续遍历，直到整个pageblock遍历结束，这样整个pageblock中的空闲页框都被移动到start_type类型中了
*/
new_type = try_to_steal_freepages(zone, page,
start_migratetype,
migratetype); /* 从伙伴系统中拿出来，因为在try_to_steal_freepages已经将新的页框放到了需要的start_mirgatetype的链表中
* 并且此order并不一定是所需要order的上级，因为order是倒着遍历了，比如我们需要32个MIGRATE_UNMOVABLE页框，但是移动的是1024个MIGRATE_MOVABLE页框到MIGRATE_UNMOVABLE的order=10的链表中。
*/
list_del(&page->lru);
/* 设置page->_mapcount = -1 并且 page->private = 0 */
rmv_page_order(page); /* 如果有多余的页框，则把多余的页框放回伙伴系统中 */
expand(zone, page, order, current_order, area,
new_type); /* 设置获取的页框的类型为新的类型，因为在try_to_steal_freepages()中cma类型是直接返回的，而其他类型都会在里面被设置，page->index = new_type
* 到这里，page已经是一个2^oder连续页框的内存段，之后就把它返回到申请者就好
*/
set_freepage_migratetype(page, new_type); trace_mm_page_alloc_extfrag(page, order, current_order,
start_migratetype, migratetype, new_type); return page;
}
} return NULL;
}
此函数中主要就是从其他migratetype类型的空闲块链表中获取一个空闲块，然后将此空闲块所在的pageblock中的所有空闲页都移动到当前migratetype类型的空闲块链表中，不过只有当系统的page_group_by_mobility_disable被禁止时，或者order > pageblock_order / 2时，才允许这样做(pageblock_order为最大页的大小，或者1024)。
整个快速分配大概就是这样，如果申请1个页框则会从每CPU高速缓存分配，如果申请的是多个页框则从伙伴系统中分配。如果都不成功，那就进入慢速分配了。
对于慢速分配，我也只做一个抛砖引玉，里面涉及的流程既长又复杂，涉及到内存压缩(同步和异步)、直接内存回收和kswapd线程唤醒。这里就不做详细说明了，如果要需要的朋友，可以跟我说，我看看要不要单独拿一篇出来进行说明。
/* 慢速分配页框 */
static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
struct zonelist *zonelist, enum zone_type high_zoneidx,
nodemask_t *nodemask, struct zone *preferred_zone,
int classzone_idx, int migratetype)
{
const gfp_t wait = gfp_mask & __GFP_WAIT;
struct page *page = NULL;
int alloc_flags;
unsigned long pages_reclaimed = ;
unsigned long did_some_progress;
enum migrate_mode migration_mode = MIGRATE_ASYNC;
bool deferred_compaction = false;
int contended_compaction = COMPACT_CONTENDED_NONE; /* order不能大于10或11 */
if (order >= MAX_ORDER) {
WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
return NULL;
} /* 调用者指定了GFP_THISNODE标志，表示不能进行内存回收
* 上层调用者应当在指定了GFP_THISNODE失败后，使用其他标志进行分配
*/
if (IS_ENABLED(CONFIG_NUMA) &&
(gfp_mask & GFP_THISNODE) == GFP_THISNODE)
goto nopage; restart:
/* 如果调用者的标志没有禁止kswapd线程标志，则会唤醒这个线程用于页框回收，这里会唤醒所有node结点中的kswap线程，每个node都有一个自己的kswap线程
* 里面会遍历zonelist链表的zone区域，只有zone区域的空闲页框数量低于高警戒值才会唤醒zone对应的node的kswapd线程
*/
if (!(gfp_mask & __GFP_NO_KSWAPD))
wake_all_kswapds(order, zonelist, high_zoneidx,
preferred_zone, nodemask); /* 根据传入标志确定其他的一些标志
* 这里会默认使用min阀值进行内存分配
* 如果gfp_mask是GFP_ATOMIC，那么这个alloc_flags应该是__GFP_HIGH | __GFP_HARDER
*
* 如果标记有__GFP_MEMALLOC，或者
* 处于软中断中，并且当前进程被设为允许使用保留内存，或者
* 不在中断中，并且当前进程 被设置为允许使用保留内存 或者是正在被oom的进程
* 那么就会标记ALLOC_NO_WATERMARKS，表示忽略阀值进行分配
*/
alloc_flags = gfp_to_alloc_flags(gfp_mask); /* 如果不受CPUSET的限制，则找出优先用于分配的管理区 */
if (!(alloc_flags & ALLOC_CPUSET) && !nodemask) {
struct zoneref *preferred_zoneref;
preferred_zoneref = first_zones_zonelist(zonelist, high_zoneidx,
NULL, &preferred_zone);
classzone_idx = zonelist_zone_idx(preferred_zoneref);
} rebalance:
/* This is the last chance, in general, before the goto nopage. */
/* 这里会用min阀值再次尝试获取页框，如果这次尝试还是没申请到页框，就要走漫长的步骤了 */
page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,
high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,
preferred_zone, classzone_idx, migratetype); if (page)
goto got_pg; /* Allocate without watermarks if the context allows */
/* 如果标记了不关注阀值进行分配，这样会有可能使用预留的内存进行分配
* 如果标记有__GFP_MEMALLOC，或者
* 处于软中断中，并且当前进程被设为允许使用保留内存，或者
* 不在中断中，并且当前进程 被设置为允许使用保留内存 或者是正在被oom的进程
* 那么就会进行这种分配
* 而平常可能用到的GFP_ATOMIC，则不是这种分配，GFP_ATOMIC会在zone_watermark_ok()中通过降低阀值进行判断，它不会用到预留的内存
*/
if (alloc_flags & ALLOC_NO_WATERMARKS) {
/* 这里就是还是没有获取到，尝试忽略阀值再次进行获取页框 */
zonelist = node_zonelist(numa_node_id(), gfp_mask); /* 尝试获取页框，这里不调用zone_watermark_ok()，也就是忽略了阀值，使用管理区预留的页框
* 当没有获取到时，如果标记有__GFP_NOFAIL，则进行循环不停地分配，直到获取到页框
*/
page = __alloc_pages_high_priority(gfp_mask, order,
zonelist, high_zoneidx, nodemask,
preferred_zone, classzone_idx, migratetype);
if (page) {
goto got_pg;
}
} /* Atomic allocations - we can't balance anything */
/* 还是没有分配到，如果调用者不希望等待获取内存，就返回退出 */
if (!wait) {
WARN_ON_ONCE(gfp_mask & __GFP_NOFAIL);
goto nopage;
} /* Avoid recursion of direct reclaim */
/* 调用者本身就是内存回收进程，不能执行后面的内存回收流程，是为了防止死锁 */
if (current->flags & PF_MEMALLOC)
goto nopage; /* Avoid allocations with no watermarks from looping endlessly */
if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))
goto nopage; /* 通过压缩看能否有多余的页框，通过页面迁移实现，这里的内存压缩是异步模式，要进入这里，有个前提就是分配内存的标志中必须允许阻塞(__GFP_WAIT)，大多数情况分配都允许阻塞
* 只会对MIRGATE_MOVABLE和MIGRATE_CMA类型的页进行移动，并且不允许阻塞
* 对zonelist的每个zone进行一次异步内存压缩
*/
page = __alloc_pages_direct_compact(gfp_mask, order, zonelist,
high_zoneidx, nodemask, alloc_flags,
preferred_zone,
classzone_idx, migratetype,
migration_mode, &contended_compaction,
&deferred_compaction);
if (page)
goto got_pg; /* Checks for THP-specific high-order allocations */
if ((gfp_mask & GFP_TRANSHUGE) == GFP_TRANSHUGE) {
if (deferred_compaction)
goto nopage; if (contended_compaction == COMPACT_CONTENDED_LOCK)
goto nopage; if (contended_compaction == COMPACT_CONTENDED_SCHED
&& !(current->flags & PF_KTHREAD))
goto nopage;
} /* 设置第二次内存压缩为轻同步模式，当第一次内存压缩后还是没有分配到足够页框时会使用
* 轻同步内存压缩两有一种情况会发生
* 在申请内存时内存不足，通过第一次异步内存压缩后，还是不足以分配连续页框后
* 1.明确禁止处理透明大页的时候，可以进行轻同步内存压缩
* 2.如果是内核线程，可以进行轻同步内存压缩(即使没有禁止处理透明大页的情况)
*/
if ((gfp_mask & GFP_TRANSHUGE) != GFP_TRANSHUGE ||
(current->flags & PF_KTHREAD))
migration_mode = MIGRATE_SYNC_LIGHT; /* Try direct reclaim and then allocating */
/* 进行直接内存回收 */
page = __alloc_pages_direct_reclaim(gfp_mask, order,
zonelist, high_zoneidx,
nodemask,
alloc_flags, preferred_zone,
classzone_idx, migratetype,
&did_some_progress);
if (page)
goto got_pg; /* 还是没有分配到内存 */
if (!did_some_progress) {
/* 如果是文件系统操作，并且允许重试，就是这次一定要分配到内存 */
if (oom_gfp_allowed(gfp_mask)) {
if (oom_killer_disabled)
goto nopage;
/* Coredumps can quickly deplete all memory reserves */
if ((current->flags & PF_DUMPCORE) &&
!(gfp_mask & __GFP_NOFAIL))
goto nopage;
/* 杀死其他进程后再尝试，里面会使用high阀值进行尝试分配
* 是希望通过杀死进程获取比较多的内存?
*/
page = __alloc_pages_may_oom(gfp_mask, order,
zonelist, high_zoneidx,
nodemask, preferred_zone,
classzone_idx, migratetype);
if (page)
goto got_pg; /* 分配禁止失败 */
if (!(gfp_mask & __GFP_NOFAIL)) {
/* 要求的数量太多，没办法 */
if (order > PAGE_ALLOC_COSTLY_ORDER)
goto nopage;
/* 是从DMA区域要内存，实在没太多内存 */
if (high_zoneidx < ZONE_NORMAL)
goto nopage;
} goto restart;
}
} /* 回收到了一部分，这里检查是否继续尝试回收 */
pages_reclaimed += did_some_progress;
if (should_alloc_retry(gfp_mask, order, did_some_progress,
pages_reclaimed)) {
/* 需要，这里会阻塞一段时间，然后重试 */
/* Wait for some write requests to complete then retry */
wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/);
goto rebalance;
} else {
/* 如果是在内核线程中，或者分配的不是透明大页的情况下，会对zonelist中的每个zone进行轻同步内存压缩，否则还是异步模式
* 此模式下允许进行大多数操作的阻塞，但不会对隔离出来需要移动的脏页进行回写操作，也不会等待正在回写的脏页回写完成，会阻塞去获取锁
* 回收的数量保存在did_some_progress中，有可能回收到了页框，但是并不够分配
*/
page = __alloc_pages_direct_compact(gfp_mask, order, zonelist,
high_zoneidx, nodemask, alloc_flags,
preferred_zone,
classzone_idx, migratetype,
migration_mode, &contended_compaction,
&deferred_compaction);
if (page)
goto got_pg;
} nopage:
/* 没有分配到内存 */
warn_alloc_failed(gfp_mask, order, NULL);
return page;
got_pg:
/* 分配到了 */
if (kmemcheck_enabled)
kmemcheck_pagealloc_alloc(page, order, gfp_mask); return page;
}
不过需要注意的是，慢速内存分配中使用的是min阀值， 而在慢速内存分配过程中，还有一个oom分配，这里面会使用zone的high阀值进行内存分配，实际上也就是杀死一些进程，让zone的空闲内存达到high阀值。
最后整理一下，如果一次分配，从开始到最后都没有成功，所走的路径是：
- 遍历zonelist，从zonelist中获取一个zone
- 检查zone如果分配后，空闲页框是否会低于allow_low
- 对此zone回收一些文件映射页和slab使用的页
- 再次检查zone如果分配后，空闲页框是否会低于allow_low
- 尝试从此zone分配页框(1个页优先从每CPU高速缓存分配，连续页框优先从需要的类型(migratetype)分配，如果不行再从其他migratetype分配)
- free_order小于11的情况, free_order++, 再次尝试第5步.如果free_order大于等于11, 则走第7步
- 跳到第1步，遍历zonelist结束则到下一步
- 再重新遍历zonelist一次，如果重新遍历过则到下一步
- 进入慢速分配
- 唤醒所有kswapd内核线程
- 再次尝试一次1~7步骤进行分配
- 如果有ALLOC_NO_WATERMARKS，则尝试分配预留的内存
- 进行异步内存压缩，然后尝试分配内存
- 尝试调用__alloc_pages__direct_reclaim()进行内存回收，然后尝试分配内存
- 使用oom杀掉oom_score较大的进程，每个进程都有一个oom_score(在/proc/PID/oom_score)
- 尝试轻同步内存压缩，然后尝试分配内存
- 压缩后再次尝试1~7步骤进行分配
补充
pageblock
在内核中，会被内存分为一小块一小块，这每个一小块叫做一个pageblock，在pageblock中所有页框都是空闲的情况下，它们都是属于同一种类型的页框。在内核里页框被分为以下几种类型:
/* 这几个链表主要用于内存压缩时做判断 */
enum {
MIGRATE_UNMOVABLE, /* 页框内容不可移动,在内存中位置必须固定，无法移动到其他地方，核心内核分配的大部分页面都属于这一类。 */
MIGRATE_RECLAIMABLE, /* 页框内容可回收,不能直接移动，但是可以回收，因为还可以从某些源重建页面，比如映射文件的数据属于这种类别，kswapd会按照一定的规则回收这类页面。 */
MIGRATE_MOVABLE, /* 页框内容可移动，属于用户空间应用程序的页属于此类页面，它们是通过页表映射的，因此我们只需要更新页表项，并把数据复制到新位置就可以了
* 当然要注意，一个页面可能被多个进程共享，对应着多个页表项。
*/
MIGRATE_PCPTYPES, /* 用来表示每CPU页框高速缓存的数据结构中的链表的迁移类型数目 */
MIGRATE_RESERVE = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
MIGRATE_CMA, /* 预留一段的内存给驱动使用，但当驱动不用的时候，伙伴系统可以分配给用户进程用作匿名内存或者页缓存。而当驱动需要使用时，就将进程占用的内存通过回收或者迁移的方式将之前占用的预留内存腾出来，供驱动使用。 */
#endif
#ifdef CONFIG_MEMORY_ISOLATION
MIGRATE_ISOLATE, /* 不能从这个链表分配页框，因为这个链表专门用于NUMA结点移动物理内存页，将物理内存页内容移动到使用这个页最频繁的CPU */
#endif
MIGRATE_TYPES
};
在每个内存管理区的伙伴系统中，都维护着以这些类型区分开的空闲页框段链表，如下：
/* 内存管理区描述符 */
struct zone { ....../* 标识出管理区中的空闲页框块，用于伙伴系统 */
/* MAX_ORDER为11，分别代表包含大小为1,2,4,8,16,32,64,128,256,512,1024个连续页框的链表，具体见下面 */
struct free_area free_area[MAX_ORDER]; ...... } /* 伙伴系统的一个块，描述1,2,4,8,16,32,64,128,256,512或1024个连续页框的块 */
struct free_area {
/* 指向这个块中所有空闲小块的第一个页描述符，这些小块会按照MIGRATE_TYPES类型存放在不同指针里 */
struct list_head free_list[MIGRATE_TYPES];
/* 空闲小块的个数 */
unsigned long nr_free;
};
在每个管理区的伙伴系统初始化过程中，会把所有空闲页框都设置为MIGRATE_MOVABLE类型，并放入到对应管理区的free_list[MIGRATE_MOVABLE]这个链表中，而根据释放页框函数(见linux内存源码分析 - 伙伴系统(释放页框))可以看出，在初始化过程中，释放的所有页框几乎都放到了free_area[10].free_list[MIGRATE_MOVABLE]这个链表中来，其他链表几乎为空。在这里思考一下，在初始化伙伴系统完成后，除了内核正在使用的页框(这些页框类型为MIGRATE_UNMOVABLE)，其他所有空闲页框都被设置为可移动页框(MIGRATE_MOVABLE)，其他类型的页框几乎都为空。再去看看内核分配页框函数，里面提到了一个fallbacks:
static int fallbacks[MIGRATE_TYPES][] = {
[MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
#ifdef CONFIG_CMA
[MIGRATE_MOVABLE] = { MIGRATE_CMA, MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
[MIGRATE_CMA] = { MIGRATE_RESERVE }, /* Never used */
#else
[MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
#endif
[MIGRATE_RESERVE] = { MIGRATE_RESERVE }, /* Never used */
#ifdef CONFIG_MEMORY_ISOLATION
[MIGRATE_ISOLATE] = { MIGRATE_RESERVE }, /* Never used */
#endif
};
在这个表中，表明了不同类型的页框空缺时，会从其他那些类型的页框中获取。举个例子，在伙伴系统初始化完成后，几乎所有空闲页框都是MIGRATE_MOVABLE。注意这一行
[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
而当我们映射一个文件时，申请页框时会表明我们需要申请MIGRATE_RECLAIMABLE类型的页框，但是这种类型的页框空缺的，伙伴系统会先去MIGRATE_UNMOVABLE类型的链表中获取一段连续空闲页框，如果MIGRATE_UNMOVABLE类型也为空缺的，会再往下，从MIGRATE_MOVABLE类型获取一段连续页框，这种类型在初始化之后是最多的，在获取这段连续页框成功后，会把这段页框设置为我们需要的MIGRATE_RECLAIMABLE类型。这整个过程对整个内存压缩有着至关重要的关系，说到这个从其他类型的free_list中获取页框，就必须要说到pageblock，pageblock中对内存压缩来说最重要的就两个变量：
#ifdef CONFIG_HUGETLB_PAGE #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE /* Huge page sizes are variable */
extern int pageblock_order; #else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */ /* Huge pages are a constant size */
#define pageblock_order HUGETLB_PAGE_ORDER #endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */ #else /* CONFIG_HUGETLB_PAGE */ /* If huge pages are not used, group by MAX_ORDER_NR_PAGES */
#define pageblock_order (MAX_ORDER-1) #endif /* CONFIG_HUGETLB_PAGE */ #define pageblock_nr_pages (1UL << pageblock_order)
pageblock_nr_pages和pageblock_order，pageblock_order有两种情况：2的pageblock_order次方等于大页大小，或者pageblock_order=MAX_ORDER。也就是一个pageblock的大小要么等于大页的大小，要么等于一个free_list[10]链表中一个1024个连续页框的大小。在默认不是用大页的情况下，一个pageblock就是1024个连续页框大小，内核会将内存简单地分为一个一个pageblock，每个pageblock为1024个连续页框，0~1023为一个pageblock，1024~2047为一个pageblock。当从其他类型页框的free_list中拿去一段连续页框时，是以一个pageblock为单位的，也就是说，这个pageblock中的所有页框都会被设置为我们需要的页框类型，如下图：
这里只用了order为10的连续空闲页框链表说例子。而如果在一个pageblock中有部分页已经被使用的情况，这种情况是有可能发生的，因为在检索目标类型的free_are[ORDER]时，ORDER是从大到小进行搜索的，如果ORDER=10的时候没有空闲的连续页框供于使用，则会到ORDER=9的free_list[目标类型]进行查找，这样的话就有可能导致一个pageblokc中可能有512个页框是处于使用中的，而另外512个是空闲的。在这种情况下， 如果此块pageblock被移动到新类型的页框数量大于等于此块pageblock的页框总数量的一半，则会把pageblock设置为新的类型，否则不设置。这样就会有一种情况，就是当一些页正在使用时，这些页所属的pageblock被移动到了其他类型的伙伴系统中，会导致pageblock的类型与正在使用的页的类型不一致。内核为了解决这种情况，会在页释放的时候检查释放的页是否与所属pageblock的类型一致，不一致则将释放页的类型更改为与pageblock一致的类型。
从以上总结出来，当从不同类型的伙伴系统中获取连续页框时，是一pageblock为单位，而每个pageblock标记了这块pageblock都属于同一种类型，即使有些正在使用的页不能在pageblock移动时立即更改类型，但这些页也会在被释放时检查是否与所属pageblock一致，并进行更改。这里我们具体看看代码，我们从__rmqueue函数进行分析：
/* 从伙伴系统中获取2的order次方个页框，返回第一个页框的描述符
* zone: 管理区描述符
* order: 需要页面的2的次方数
* migratetype: 从此类型中获取，这时传入的时需求的页框类型
*/
static struct page *__rmqueue(struct zone *zone, unsigned int order,
int migratetype)
{
struct page *page; retry_reserve:
/* 直接从migratetype类型的链表中获取了2的order次方个页框 */
page = __rmqueue_smallest(zone, order, migratetype); /* 如果page为空，没有在需要的migratetype类型中分配获得页框，说明当前需求类型(migratetype)的页框没有空闲，会根据fallback数组中定义好的优先级从其他类型的页框中获取页框 */
if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
/* 根据fallbacks数组从其他migratetype类型的链表中获取内存 */
page = __rmqueue_fallback(zone, order, migratetype); /* 从其他类型的空闲页框链表中也没有获得页框，设定为MIGRATE_RESERVE类型，从保留页框里尝试获取 */
if (!page) {
/* 定义从页框属性为MIGRATE_RESERVE的空闲链表中查找 */
migratetype = MIGRATE_RESERVE;
/* 重试尝试从MIGRATE_RESERVE类型的链表中找出空闲内存 */
goto retry_reserve;
}
} trace_mm_page_alloc_zone_locked(page, order, migratetype);
return page;
}
可以看到在_rmqueue中，当无法从目标类型的链表中获取连续页框时，就会调用__rmqueue_fallback()，尝试从其他类型的pageblock中将空闲页框移动到目录类型的空闲页框块链表中，进入到__rmqueue_fallback()中看看：
/* 根据fallbacks数组中定义的优先级，从其他migratetype类型的链表中获取连续页框，返回第一个页框的页描述符
* start_migratetype是申请页框时需要但是又缺少的类型
*/
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-;
current_order >= order && current_order <= MAX_ORDER-;
--current_order) { /* 遍历不同order的链表，如果需要分配2个连续页框，则会遍历1024,512,256,128,64,32,16,8,4,2,1这几个链表，注意这里是倒着遍历的 */
for (i = ;; i++) { /* 遍历order链表中对应fallbacks优先级的类型链表 */ /* 根据fallbacks和i获取migratetype,start_migratetype是申请页框时需要的类型 */
/*static int fallbacks[MIGRATE_TYPES][4] = {
* [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
* [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },
*#ifdef CONFIG_CMA
* [MIGRATE_MOVABLE] = { MIGRATE_CMA, MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
* [MIGRATE_CMA] = { MIGRATE_RESERVE },
*#else
* [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
*#endif
* [MIGRATE_RESERVE] = { MIGRATE_RESERVE },
*#ifdef CONFIG_MEMORY_ISOLATION
* [MIGRATE_ISOLATE] = { MIGRATE_RESERVE },
*#endif
*};
*/
migratetype = fallbacks[start_migratetype][i]; /* MIGRATE_RESERVE handled later if necessary */
/* 这里不能分配MIGRATE_RESERVE类型的内存，这部分内存是保留使用，最后其他的migratetype都没有内存可分配才会分配MIGRATE_RESERVE类型的内存 */
if (migratetype == MIGRATE_RESERVE)
break; /* 当前order的链表，current_order从10 ~ order */
area = &(zone->free_area[current_order]);
/* 链表为空，说明这个链表页没有内存 */
if (list_empty(&area->free_list[migratetype]))
continue; /* 有空余的内存，即将分配 */
/* 从链表中获取第一个节点，但是注意，这里分配的内存可能大于我们需要的数量(从其他order链表中获取的连续页框)，之后会调用expand把多余的放回去 */
page = list_entry(area->free_list[migratetype].next,
struct page, lru);
area->nr_free--; /* 在当前start_migratetype中没有足够的页进行分配时，则会从migratetype获取order或者pageblock相等数量的页框放到start_migratetype中的order链表中，返回获取的页框本来所属的类型
* 代码中不建议把过低order数量的页框进行移动，最小移动单位是一个pageblock，它的大小是1024个页框或者一个大页的大小。如果order过小则可能不会移动
*/
new_type = try_to_steal_freepages(zone, page,
start_migratetype,
migratetype); /* 从伙伴系统中拿出来，因为在try_to_steal_freepages已经将新的页框放到了需要的start_mirgatetype的链表中
* 并且此order并不一定是所需要order的上级，因为order是倒着遍历了，比如我们需要32个MIGRATE_UNMOVABLE页框，但是移动的是1024个MIGRATE_MOVABLE页框到MIGRATE_UNMOVABLE的order=10的链表中。
*/
list_del(&page->lru);
/* 设置page->_mapcount = -1 并且 page->private = 0 */
rmv_page_order(page); /* 如果有多余的页框，则把多余的页框放回伙伴系统中 */
expand(zone, page, order, current_order, area,
new_type); /* 设置获取的页框的类型为新的类型，因为在try_to_steal_freepages()中cma类型是直接返回的，而其他类型都会在里面被设置，page->index = new_type
* 到这里，page已经是一个2^oder连续页框的内存段，之后就把它返回到申请者就好
*/
set_freepage_migratetype(page, new_type); trace_mm_page_alloc_extfrag(page, order, current_order,
start_migratetype, migratetype, new_type); return page;
}
} return NULL;
}
在__rmqueue_fallback()，根据fallbacks表，遍历后面类型的空闲页框块链表，从找到一块合适的，然后获取对应的pageblock，将pageblock中所有空闲页框都移动到当前类型的空闲页框链表中，主要通过调用try_to_steal_freepages()函数实现将其他类型的pageblock中所有空闲页框移动到当前类型的空闲页框链表中：
/* 在当前start_migratetype中没有足够的页进行分配时，则会将获取到的migratetype类型的pageblock中的所有空闲页框移动到start_migratetype中，返回获取的页框本来所属的类型
* 在调用前，page一定是migratetype类型的
* 里面的具体做法是:
* page是属于migratetype类型的pageblock中的一个页，然后函数中会根据page获取其所在的pageblock
* 从pageblock开始的第一页遍历到此pageblock的最后一页
* 然后根据page->_mapcount是否等于-1，如果等于-1，说明此页在伙伴系统中，不等于-1则下一页
* 对page->_mapcount == -1的页获取order值，order值保存在page->private中，然后将这一段连续空闲页框移动到start_type类型的free_list中
* 对这段连续空闲页框首页设置为start_type类型，这样就能表示此段连续空闲页框都是此类型了，通过page->index = start_type设置
* 继续遍历，直到整个pageblock遍历结束，这样整个pageblock中的空闲页框都被移动到start_type类型中了
*/
static int try_to_steal_freepages(struct zone *zone, struct page *page,
int start_type, int fallback_type)
{
/* page是当前遍历到的migratetype当中order页的首页描述符，并不是我们需要的migratetype中的页
* order是当前遍历到的migratetype当中order，并不是当前需要分配的order
*/
int current_order = page_order(page); /* 如果是CMA类型则不做处理 */
if (is_migrate_cma(fallback_type))
return fallback_type; /* Take ownership for orders >= pageblock_order */
/* 如果当前需要的order值大于默认一个内存块的order值(这个值为MAX_ORDER-1或者大页的大小)，就算出需要多少块pageblock才能达到order，然后把这些pageblock都设置为start_type
* 这种情况发生在pageblock_order等于大页的大小，而内核配置了CONFIG_FORCE_ORDER，导致order >= pageblock_order
*/
if (current_order >= pageblock_order) {
/* 计算出需要的pageblock的块数，然后将每一块都设置为需要的类型，这种情况下并没有把它们从旧类型的伙伴系统移到需要类型的伙伴系统中，在外面函数会将其移出来 */
change_pageblock_range(page, current_order, start_type);
return start_type;
} /* 如果order大于pageblock_order的一半，或者类型是MIGRATE_RECLAIMABLE，或者内核关闭了页可迁移的特性，则从此页所属的mirgatetype和order链表中获取页框放到start_type中
* 如果oder小于pageblock_order / 2并且start_type != MIGRATE_RECLAIMABLE并且page_group_by_mobility_disabled == false，就不会移动页框。
*/
if (current_order >= pageblock_order / ||
start_type == MIGRATE_RECLAIMABLE ||
page_group_by_mobility_disabled) {
int pages; /* 这个page所在的pageblock必定属于fallback_type类型
* 将这个page所在的pageblock中所有空闲页框移动到start_type类型的free_list链表中，order不变，返回移动的页数量，但是已经在使用的页会被跳过，并且这些已经被使用的页不会被更改为新的类型
* 具体做法:
* 从pageblock开始的第一页遍历到此pageblock的最后一页
* 然后根据page->_mapcount是否等于-1，如果等于-1，说明此页在伙伴系统中，不等于-1则下一页
* 对page->_mapcount == -1的页获取order值，order值保存在page->private中，然后将这一段连续空闲页框移动到start_type类型的free_list中
* 对这段连续空闲页框首页设置为start_type类型，这样就能表示此段连续空闲页框都是此类型了，通过page->index = start_type设置
* 继续遍历，直到整个pageblock遍历结束，这样整个pageblock中的空闲页框都被移动到start_type类型中了
*/
pages = move_freepages_block(zone, page, start_type); /* Claim the whole block if over half of it is free */
/* 如果这块pageblock中的页数量大于pageblock的页数量的一半，则设置这块pageblock为新的migratetype类型，如果小于，则不会把此pageblock设置为新的类型
* 如果不将pageblock设置为新的类型，会导致一种情况: 空闲页的migratetype类型与pageblock的migratetype类型不一致
* 对于这种情况，在这些正在使用的块被释放时，会被检查是否与所属pageblock的类型一致，不一致则会设置为一致
* 一个zone的每个pageblock的状态占4位，保存在zone->pageblock_flags指向的一个位图中
*/
if (pages >= ( << (pageblock_order-)) ||
page_group_by_mobility_disabled) {
set_pageblock_migratetype(page, start_type);
return start_type;
}
}
/* 返回是从哪个migratetype中移动的页框 */
return fallback_type;
move_freepages_block()：
/* 将page所在的pageblock中所有空闲页框移动到新的类型链表中
* 比如一段连续页框块，order为8，那么就会移动zone->free_area[8].free_list[新的类型]这个空闲页框块中
*/
int move_freepages_block(struct zone *zone, struct page *page,
int migratetype)
{
unsigned long start_pfn, end_pfn;
struct page *start_page, *end_page; /* 根据page
* 将start_pfn设置为page所在pageblock的起始页框
* 将end_pfn设置为page所在pageblock的结束页框
* start_page指向start_pfn对应的页描述符
* end_page指向end_page对应的页描述符
*/
start_pfn = page_to_pfn(page);
start_pfn = start_pfn & ~(pageblock_nr_pages-);
start_page = pfn_to_page(start_pfn);
end_page = start_page + pageblock_nr_pages - ;
end_pfn = start_pfn + pageblock_nr_pages - ; /* Do not cross zone boundaries */
/* 检查开始页框是否属于zone中，如果不属于，则用page作为开始页框
* 因为有可能pageblock中一半在上一个zone中，一半在本zone中
*/
if (!zone_spans_pfn(zone, start_pfn))
start_page = page;
/* 同上如果结束页框不属于zone，不过这里直接返回0 */
if (!zone_spans_pfn(zone, end_pfn))
return ; /* 将此pageblock中的空闲页框全部移动到新的migratetype类型的伙伴系统链表中 */
return move_freepages(zone, start_page, end_page, migratetype);
}
move_freepages():
/* 将此段页框中的空闲页框移动到新的migratetype类型的伙伴系统链表中 */
int move_freepages(struct zone *zone,
struct page *start_page, struct page *end_page,
int migratetype)
{
struct page *page;
unsigned long order;
int pages_moved = ; #ifndef CONFIG_HOLES_IN_ZONE
VM_BUG_ON(page_zone(start_page) != page_zone(end_page));
#endif
/* 遍历这组页框 */
for (page = start_page; page <= end_page;) {
/* Make sure we are not inadvertently changing nodes */
VM_BUG_ON_PAGE(page_to_nid(page) != zone_to_nid(zone), page); /* 检查页框和页框号是否属于内存，如果不正确则跳过 */
if (!pfn_valid_within(page_to_pfn(page))) {
page++;
continue;
} /* 如果页框不在伙伴系统中则跳到下一页，通过判断page->_mapcount是否等于-128 */
if (!PageBuddy(page)) {
page++;
continue;
} /* 获取此页框的order号，保存在page->private中 */
order = page_order(page);
/* 从伙伴系统中拿出来，并放到新的migratetype类型中的order链表中 */
list_move(&page->lru,
&zone->free_area[order].free_list[migratetype]);
/* 将这段空闲页框的首页设置为新的类型page->index = migratetype */
set_freepage_migratetype(page, migratetype);
/* 跳过此order个页框数量 */
page += << order;
/* 记录拿出来了多少个页框 */
pages_moved += << order;
}
/* 返回一共拿出来的页框 */
return pages_moved;
}