你好！这里是风筝的博客，
欢迎和我一起交流。
我们知道，在一个通用操作系统里，频繁申请内存释放内存都会出现一个非常著名的内存管理问题：内存碎片。
学过操作系统的都知道，有很多行之有效的方法（比如：记录现存的空闲连续页框块的情况，以尽量避免为满足小块的请求而分割大的空闲块；小内存单独分配，大内存系统自动分配）可以很大程度上避免出现内存碎片，其中伙伴算法被证明是非常行之有效的一套内存管理方法，因此也被相当多的操作系统所采用。
伙伴算法的原理也比较简单，可以学习一下：
伙伴算法将内存分成若干个块，以Linux为例，把所有的空闲页框分组为 11 条链表，每一块链表分别包含大小为2^0 个，2^1 个，2^2 个，2^3 个…到2^10 个连续的页框。在第11条链表中，2^10 个连续的页框的最大请求对应着 4MB 大小的连续RAM 块。每一块的第一个页框的物理地址是该块大小的整数倍。例如，大小为 16个页框的块，其起始地址是 16 * 2^12 （2^12 = 4096，这是一个常规页的大小）的倍数。每个链表中元素的个数在系统初始化时决定，在执行过程中，动态变化。
如图所示：
假设要申请一个256个页框的块（2^8），先从256个页框的链表（第9条链表）中查找空闲块，如果没有，就去下一个更大当页块，即512个页框的链表中找，找到了则将页框块分为2个256个页框的块，一个分配给应用，另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块，继续向1024个页框的链表查找，如果仍然没有，则返回错误。页框块在释放时，会主动将两个连续的页框块合并为一个较大的页框块。
简而言之，就是在分配内存时，首先从空闲的内存中搜索比申请的内存大的最小的内存块。如果这样的内存块存在，则将这块内存标记为“已用”，同时将该内存分配给应用程序。如果这样的内存不存在，则操作系统将寻找更大块的空闲内存，然后将这块内存平分成两部分，一部分返回给程序使用，另一部分作为空闲的内存块等待下一次被分配。
所以伙伴算法一直在对页框做拆开合并拆开合并的动作。Buddy算法厉害就厉害在运用了世界上任何正整数都可以由2^n的和组成。这也是Buddy算法管理空闲页表的本质。
假设要释放一个256个页框的块，算法就把其插入到256个页框的链表中，然后检查与该内存相邻的内存，如果存在同样大小为256个页框的并且空闲的内存，而且由同一个大块分裂而来（互为伙伴），就将这两块内存合并成512个页框，然后插入到512个页框的链表中，如果不存在，就没有后面的合并操作。然后再进一步检查，如果合并后的512个页框的内存存在大小为512个页框的相邻且空闲的内存，则将两者合并，然后插入到1024个页框的链表中。
何谓“伙伴”?
由同一大块分裂出来的小块就称之“互为伙伴”。
例如：假设p为大小为pow(2,k)的空闲块的初始地址，且p MOD pow(2,k+1)=0，则初始地址为p和p+pow(2,k)的两个空闲块互为伙伴。在伙伴系统中回收空闲块时，只当其伙伴为空闲块时才归并成大块。也就是说，若有两个空闲块，即使大小相同且地址相邻，但不是由同一大块分裂出来的，也不归并在一起。
简而言之，就是当程序释放内存时，操作系统首先将该内存回收，然后检查与该内存相邻的内存是否是同样大小并且同样处于空闲的状态，同时由同一个大块分裂而来（互为伙伴），如果是，则需在相应子表中找到其伙伴并删除，然后将这两块内存合并，然后程序递归进行同样的检查，试图再次合并相邻的块，以再次试图形成更大的块，最后插入到相应的子表中去。
这样能以最合适的分配方法将内存分配出去，使得系统可以避免外部碎片的产生（缺点就是产生了内部碎片）
内部碎片的产生：因为所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址或者因为MMU的分页机制的限制，决定内存分配算法仅能把预定大小的内存块分配给客户。
假设当请求一个65 字节的内存块时，因为没有适合大小的内存，所以它会获得128字节等稍大一点的字节，因此由所需大小四舍五入而产生的多余空间就叫内部碎片。
假设系统中有 1MB 大小的内存需要动态管理，按照伙伴算法的要求：需要将这1M大小的内存进行划分。这里，我们将这1M的内存分为 64K、64K、128K、256K、和512K 共五个部分，如下图t0时刻所示:
t1时刻，如果有一个程序A想要申请一块45K大小的内存，则系统会将第一块64K的内存块分配给该程序（产生内部碎片为代价）
t2时刻，程序B向系统申请一块68K大小的内存，系统会将128K内存分配给该程序
t3时刻，程序C要申请一块大小为35K的内存。系统将空闲的64K内存分配给该程序
t4时刻，程序D需要一块大小为90K的内存。当程序提出申请时，系统本该分配给程序D一块128K大小的内存，但此时内存中已经没有空闲的128K内存块了，于是根据伙伴算法的原理，系统会将256K大小的内存块平分，将其中一块分配给程序D，另一块作为空闲内存块保留，等待以后使用
t5时刻，程序C释放了它申请的64K内存。在内存释放的同时，系统还负责检查与之相邻并且同样大小的内存是否也空闲，由于此时程序A并没有释放它的内存，所以系统只会将程序C的64K内存回收
t6时刻，程序A也释放掉由它申请的64K内存，系统随机发现与之相邻且大小相同的一段内存块恰好也处于空闲状态。于是，将两者合并成128K内存
t7时刻，程序B释放掉它的128k，系统也将这块内存与相邻的128K内存合并成256K的空闲内存
t8时刻，程序D也释放掉它的内存，经过三次合并后，系统得到了一块1024K的完整内存
–
最后，我们可以简单追一下Linux4.9的源码，Linux也是采用了伙伴算法：
Linux内核管理物理内存是通过分页机制实现的，它将整个内存划分成无数个4k大小的页，从而分配和回收内存的基本单位便是内存页了。利用分页管理有助于灵活分配内存地址，因为分配时不必要求必须有大块的连续内存[3]，系统可以东一页、西一页的凑出所需要的内存供进程使用。虽然如此，但是实际上系统使用内存时还是倾向于分配连续的内存块，因为分配连续内存时，页表不需要更改，因此能降低TLB的刷新率（频繁刷新会在很大程度上降低访问速度）。
鉴于上述需求，内核分配物理页面时为了尽量减少不连续情况，采用了“伙伴”关系来管理空闲页面。
伙伴系统完成了初始化（将内存的按照 order 添加到 zonelist 后），就可以利用伙伴系统进行分配内存了，对于物理页的分配，伙伴系统分配的单位都是 2^order 次幂。
这些分配的宏函数都位于：include/linux/gfp.h 中
对于 alloc_pages(mask, order)：分配2^order页并返回一个struct page的实例，表示分配的内存块的起始页
#define alloc_pages(gfp_mask, order) \
alloc_pages_node(numa_node_id(), gfp_mask, order)
alloc_page(mask)：
#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)
get_zeroed_page(mask)：
unsigned long get_zeroed_page(gfp_t gfp_mask)
{
return __get_free_pages(gfp_mask | __GFP_ZERO, 0);
}
EXPORT_SYMBOL(get_zeroed_page);
__get_free_pages(mask, order)：
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
{
struct page *page;
/*
* __get_free_pages() returns a 32-bit address, which cannot represent
* a highmem page
*/
VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);
page = alloc_pages(gfp_mask, order);
if (!page)
return 0;
return (unsigned long) page_address(page);
}
EXPORT_SYMBOL(__get_free_pages);
__get_free_page(mask)：
#define __get_free_page(gfp_mask) \
__get_free_pages((gfp_mask), 0)
__get_dma_pages(gfp_mask, order)
#define __get_dma_pages(gfp_mask, order) \
__get_free_pages((gfp_mask) | GFP_DMA, (order))
上述的所有接口调用，最终都集合到了 alloc_pages 接口：
alloc_pages 函数的参数比alloc_pages()多了一个nid，它用来指定节点id，如果nid小于0，则说明在当前节点上分配页框。正确获取到节点id后，接下来调用__alloc_pages()。
函数调用过程如下：
alloc_pages ->
alloc_pages_node ->
__alloc_pages ->
__alloc_pages_nodemask
__alloc_pages_nodemask函数在Linux代码里当注释为：This is the ‘heart’ of the zoned buddy allocator.
可想而知是多么的核心了！
/*
* This is the 'heart' of the zoned buddy allocator.
*/
struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
struct zonelist *zonelist, nodemask_t *nodemask)
{
struct page *page;
unsigned int alloc_flags = ALLOC_WMARK_LOW;
gfp_t alloc_mask = gfp_mask; /* The gfp_t that was actually used for allocation */
struct alloc_context ac = {
.high_zoneidx = gfp_zone(gfp_mask),/*根据gfp_mask确定分配页所处的zone*/
.zonelist = zonelist,
.nodemask = nodemask,
.migratetype = gfpflags_to_migratetype(gfp_mask),/*根据gfp_mask得到迁移类分配页的型*/
};
if (cpusets_enabled()) {
alloc_mask |= __GFP_HARDWALL;
alloc_flags |= ALLOC_CPUSET;
if (!ac.nodemask)
ac.nodemask = &cpuset_current_mems_allowed;
}
gfp_mask &= gfp_allowed_mask;
lockdep_trace_alloc(gfp_mask);
might_sleep_if(gfp_mask & __GFP_DIRECT_RECLAIM);//设置了__GFP_DIRECT_RECLAIM，则调用该函数的进程可能休眠
if (should_fail_alloc_page(gfp_mask, order))
return NULL;
if (unlikely(!zonelist->_zonerefs->zone))
return NULL;
if (IS_ENABLED(CONFIG_CMA) && ac.migratetype == MIGRATE_MOVABLE)
alloc_flags |= ALLOC_CMA;
/* Dirty zone balancing only done in the fast path */
ac.spread_dirty_pages = (gfp_mask & __GFP_WRITE);
/*从zonelist中找到zone_idx与high_zoneidx相同的zone，也就是之前认定的zone*/
ac.preferred_zoneref = first_zones_zonelist(ac.zonelist,
ac.high_zoneidx, ac.nodemask);
if (!ac.preferred_zoneref->zone) {
page = NULL;
goto no_zone;
}
/* First allocation attempt */
page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);//开始分配内存
if (likely(page))
goto out;
no_zone://没有zone当情况
alloc_mask = memalloc_noio_flags(gfp_mask);
ac.spread_dirty_pages = false;
if (unlikely(ac.nodemask != nodemask))
ac.nodemask = nodemask;
//如果上面没有分配到空间，调用下面函数慢速分配，允许等待和回收
page = __alloc_pages_slowpath(alloc_mask, order, &ac);
out:
if (memcg_kmem_enabled() && (gfp_mask & __GFP_ACCOUNT) && page &&
unlikely(memcg_kmem_charge(page, gfp_mask, order) != 0)) {
__free_pages(page, order);
page = NULL;
}
if (kmemcheck_enabled && page)
kmemcheck_pagealloc_alloc(page, order, gfp_mask);
trace_mm_page_alloc(page, order, alloc_mask, ac.migratetype);
return page;
}
可以看出，重要的还是get_page_from_freelist函数，从free的page里分配出内存来使用，如果分配失败，则才会调用__alloc_pages_slowpath分配。
__alloc_pages_slowpath函数会调用wakeup_all_kswapd，该函数唤醒负责换出页的内核守护进程。交换守护进程通过缩减内核缓存和页面回收来获得更多的空闲内存，缩减内核缓存和页面回涉及到页面写回或者换出很少使用的页面。这两种措施都是由守护进程发起的。唤醒守护进程后，内核开始重新尝试从内存zones中查找合适的内存块，会再次在__alloc_pages_slowpath函数里面调用get_page_from_freelist函数！
static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
const struct alloc_context *ac)
{
struct zoneref *z = ac->preferred_zoneref;
struct zone *zone;
struct pglist_data *last_pgdat_dirty_limit = NULL;
/*从认定的zonelist开始遍历，直到找到一个拥有足够空间的zone，
* 例如，如果high_zoneidx对应的ZONE_HIGHMEM，则遍历顺序为HIGHMEM-->NORMAL-->DMA，
* 如果high_zoneidx对应ZONE_NORMAL，则遍历顺序为NORMAL-->DMA*/
for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,//从zonelist给定的ac->high_zoneidx开始查找，返回的是zone
ac->nodemask) {
struct page *page;
unsigned long mark;
if (cpusets_enabled() &&
(alloc_flags & ALLOC_CPUSET) &&
!__cpuset_zone_allowed(zone, gfp_mask))
continue;
if (ac->spread_dirty_pages) {
if (last_pgdat_dirty_limit == zone->zone_pgdat)
continue;
if (!node_dirty_ok(zone->zone_pgdat)) {
last_pgdat_dirty_limit = zone->zone_pgdat;
continue;
}
}
/*通过alloc_flags来确定是使用何种水位，pages_min?pages_low?pages_high?
选择了一种水位，就要求分配后的空闲不低于该水位才能进行分配*/
mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];//从flags取出水位
if (!zone_watermark_fast(zone, order, mark,//快速检查该zone是否值得进一步去查找空闲内存
ac_classzone_idx(ac), alloc_flags)) {
int ret;
/* Checked here to keep the fast path fast */
BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
if (alloc_flags & ALLOC_NO_WATERMARKS)
goto try_this_zone;
if (node_reclaim_mode == 0 ||
!zone_allows_reclaim(ac->preferred_zoneref->zone, zone))//如果不允许回收
continue;
ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);//通过zone_reclaim进行一些页面回收
switch (ret) {
case NODE_RECLAIM_NOSCAN:
/* did not scan */
continue;
case NODE_RECLAIM_FULL:
/* scanned but unreclaimable */
continue;
default:
/* did we reclaim enough */
if (zone_watermark_ok(zone, order, mark,
ac_classzone_idx(ac), alloc_flags))//此时水位OK
goto try_this_zone;//包括水位各种条件都满足之后，可以在此zone进行页面分配工作
continue;
}
}
try_this_zone:
page = buffered_rmqueue(ac->preferred_zoneref->zone, zone, order,//从此zone分配内存
gfp_mask, alloc_flags, ac->migratetype);
if (page) {
prep_new_page(page, order, gfp_mask, alloc_flags);
if (unlikely(order && (alloc_flags & ALLOC_HARDER)))
reserve_highatomic_pageblock(page, zone, order);
return page;
}
}
return NULL;
}
该函数主要是遍历各个内存管理区列表zonelist以尝试页面申请。其中for_each_zone_zonelist_nodemask()则是用于遍历zonelist的，每个内存管理区尝试申请前，在正常情况下需要进行一系列的验证，保证当前zone有足够的可用页面供分配。那么什么是非正常情况呢？即使携带ALLOC_NO_WATERMARKS标识的，所以这里就分为两种情况。这里涉及到一个watermark,俗称分配水位，水位有三种
#define ALLOC_WMARK_MIN WMARK_MIN
#define ALLOC_WMARK_LOW WMARK_LOW
#define ALLOC_WMARK_HIGH WMARK_HIGH
在分配之前一般会指定满足那个水位才允许分配，或者不管水位直接分配。这就对应ALLOC_NO_WATERMARKS标识。
在zone结构中，有vm_stat字段，是一个数组，记录各个状态的页面的数量，其中就包含空闲页面，对应NR_FREE_PAGES，携带watermark标识的分配，需要验证空闲页面是否大于对应的水位，只有在大于水位了才允许分配，否则需要根据情况对页面进行回收reclaim，如果无法回收或者回收后仍然不满足条件，则直接返回了。在一些急迫的事务中，可以指定ALLOC_NO_WATERMARKS，这样会不会对水位进行验证，直接调用buffered_rmqueue分配页面。
更多关于watermark可以参考：Linux内存管理 (1)物理内存初始化
当watermark满足时，调用buffered_rmqueue函数在当前满足条件的zone进行内存分配。
buffered_rmqueue并不直接从伙伴系统分配，为了加速分配流程，每个CPU也会维护页框高速缓存,通过per_cpu_pageset管理：
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
};
结构体中，per_cpu_pages 维护了各种性质的页面链表，性质基本是根据可移动性来决定的：
struct per_cpu_pages {
int count; /* number of pages in the list */
int high; /* high watermark, emptying needed */
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];/*链表数组，每个迁移类型维护一个数组*/
};
结构体注释写的很清楚了：
count代表链表中所有页面的数量；
high和清空相关；
batch是当缓存不足时，每次从伙伴系统申请多少页面填充进来。
核心分配逻辑如下：
static inline
struct page *buffered_rmqueue(struct zone *preferred_zone,
struct zone *zone, unsigned int order,
gfp_t gfp_flags, unsigned int alloc_flags,
int migratetype)
{
unsigned long flags;
struct page *page;
bool cold = ((gfp_flags & __GFP_COLD) != 0);
if (likely(order == 0)) {//如果只申请一页，那么就从当前cpu的高速缓存内存中申请
struct per_cpu_pages *pcp;
struct list_head *list;
/* 这里需要关中断，因为内存回收过程可能发送核间中断，强制每个核从每CPU
缓存中释放页面。而且中断处理函数也会分配单页。 */
local_irq_save(flags);
do {
pcp = &this_cpu_ptr(zone->pageset)->pcp;//获取zoon的当前处理器的高速缓存内存描述结构指针
list = &pcp->lists[migratetype];
if (list_empty(list)) {/*如果链表为空，则表示没有可分配的页，需要从伙伴系统中分配2^batch个页给list*/
pcp->count += rmqueue_bulk(zone, 0,//调用此函数从伙伴系统中分配batch空闲内存到高速缓存
pcp->batch, list,
migratetype, cold);
if (unlikely(list_empty(list)))
goto failed;
}
/* 如果需要的是冷页，即分配的页面不需要考虑硬件缓存(注意不是每CPU页面缓存)
，则取出链表的最后一个节点返回给上层*/
if (cold)
page = list_last_entry(list, struct page, lru);
else
/* 如果使需要热页，即要考虑硬件缓存，则取出链表的第一个页面，这个页面是最近刚释放到每CPU
* 缓存的，缓存热度更高 */
page = list_first_entry(list, struct page, lru);
list_del(&page->lru);//由于被分配出去了，所以高速缓存内存中不再包含这页内存，所以从链表里删除这一项
pcp->count--;//相应的当前页数也要减少
} while (check_new_pcp(page));
} else {/*当order为大于1时，不从pcp中分配，直接考虑从伙伴系统中分配*/
/*
* We most definitely don't want callers attempting to
* allocate greater than order-1 page units with __GFP_NOFAIL.
*/
WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));
spin_lock_irqsave(&zone->lock, flags);
do {
page = NULL;
if (alloc_flags & ALLOC_HARDER) {//通知伙伴系统放宽检查限制
/*从指定order开始从小到达遍历,优先从指定的迁移类型链表中分配页面*/
page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
if (page)
trace_mm_page_alloc_zone_locked(page, order, migratetype);
}
if (!page)
/*从管理区的伙伴系统中选择合适的内存块进行分配*/
page = __rmqueue(zone, order, migratetype);
} while (page && check_new_pages(page, order));//这里进行安全性检查，并进行一些善后工作。如果页面标志破坏，返回的页面出现了问题，则返回试图分配其他页面
spin_unlock(&zone->lock);
if (!page)
goto failed;
/* 已经分配了1 << order个页面，这里进行管理区空闲页面统计计数*/
__mod_zone_freepage_state(zone, -(1 << order),
get_pcppage_migratetype(page));
}
__count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
zone_statistics(preferred_zone, zone, gfp_flags);
local_irq_restore(flags);
VM_BUG_ON_PAGE(bad_range(zone, page), page);
return page;
failed:
local_irq_restore(flags);
return NULL;
}
当只请求一个页面时，每个CPU都维护着一个迁移页面链表，在指定的mingratetype迁移页面链表查找是否有空闲页面，就分配一个页面，同时更新迁移链表中的计数，最后请求冷/热页面。
当某个物理内存页面在CPU_Cache理，CPU访问该页的数据可以快速直接从Cache里面读取，此时该页面则称为“热（Hot）页面”，反之，页面不在CPU_Cache中，则称为“冷（Cold）页面”。
在多CPU系统中，每个CPU都有自己的Cache，因此冷/热页面按CPU来管理，每个cpu都维持着一个冷/热页面内存池。
若申请多个页面时，从伙伴系统中进行内存分配。核心函数为：__rmqueue，在zone分配2^order个物理地址连续当页面。
static struct page *__rmqueue(struct zone *zone, unsigned int order,
int migratetype)
{
struct page *page;
#ifdef CONFIG_CMA
if (migratetype == MIGRATE_MOVABLE)
page = __rmqueue_cma_prev(zone, order, migratetype);
else
#endif
page = __rmqueue_smallest(zone, order, migratetype);//开始分配
if (unlikely(!page))//如果申请不到page
page = __rmqueue_fallback(zone, order, migratetype);//从fallback链表中分配指定的order和migrate页面
trace_mm_page_alloc_zone_locked(page, order, migratetype);
return page;
}
在numa系统中，内核总是首先尝试从进程所在的CPU节点上分配内存，这样内存性能更好。但是这种分配策略并不能保证每次都能成功。
对于不能从本节点分配内存的情况，每个节点都提供一个fallback链表。该链表包含其他节点及区域，可以作为内存分配的替代选择。
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) {//由指定的伙伴管理算法链表order阶开始
area = &(zone->free_area[current_order]);
page = list_first_entry_or_null(&area->free_list[migratetype],
struct page, lru);
if (!page)//说明这里没有空闲区域可以分配
continue;
list_del(&page->lru);//将空闲页面块通过list_del()从链表中摘除出来
rmv_page_order(page);/*移除page中order的变量*/
area->nr_free--;/*空闲块数减一*/
expand(zone, page, order, current_order, area, migratetype);//将其对等拆分开
set_pcppage_migratetype(page, migratetype);
return page;
}
return NULL;
}
函数很简单，实现了伙伴算法当核心功能：
首先for()循环其由指定的伙伴管理算法链表order阶开始，如果该阶的链表不为空，则直接通过list_del()从该链表中获取空闲页面以满足申请需要；
如果该阶的链表为空，则往更高一阶的链表查找，直到找到链表不为空的一阶，直到找到了最高阶仍为空链表，则申请失败；
若在找到链表不为空的一阶后，将空闲页面块通过list_del()从链表中摘除出来，然后通过expand()将其对等拆分切割，并将拆分出来的一半空闲部分插入更低order的链表中，直到拆分至恰好满足申请需要的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) {//low表示所需块大小,high表示实际大小
area--;//先把一般的内存页恢复，对应的free_area[n]也要减少，这样才可以访问到其free_list链表
high--;//面说的current_order的值，我们也要相应减少
size >>= 1;//内存块减半切割
VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);//看看size这么大内存区域的首页是否在该内存zoon的范围下，不是则系统崩溃
if (set_page_guard(zone, &page[size], high, migratetype))
continue;
list_add(&page[size].lru, &area->free_list[migratetype]);//如果无误，我们就把这一段空间恢复为空闲区域中
area->nr_free++;/*空闲块加一*/
set_page_order(&page[size], high);/*设置相关order*/
}
}
low对应所属页面块大小的order，high对应当前空闲zone的order，当当前分配到的页面块大于所需的内存块，那就将内存块对半切割，对应参数也自减一，然后标记为保护页。
如果可以友好释放，那就将该页面插入低一级的order链表，否则继续切割内存块。
如果__rmqueue_smallest不能分配到page当话，则会调用__rmqueue_fallback函数分配。
其主要是向其他迁移类型中获取内存。较正常的伙伴算法不同，不是在本节点zone区域分配，而是在fallback链表中。
其向迁移类型的内存申请内存页面时，是从最高阶开始查找的，主要是从大块内存中申请可以避免更少的碎片。如果尝试完所有的手段仍无法获得内存页面，则会从MIGRATE_RESERVE列表中获取。
参考：【Linux 内核】内存管理（二）伙伴算法
Linux物理内存页面分配
linux伙伴系统接口alloc_page分析1里面还分析了__alloc_pages_slowpath函数
转载：https://blog.csdn.net/Guet_Kite/article/details/101309502