一文搞定伙伴分配器

伙伴分配器

1.伙伴分配器原理

2.伙伴分配器的優(yōu)缺點(diǎn)

3.伙伴分配器的分配釋放流程

4.伙伴分配器的數(shù)據(jù)結(jié)構(gòu)

5.備用區(qū)域列表

6.伙伴分配器的結(jié)構(gòu)

7.內(nèi)存區(qū)域水線

8.伙伴分配器分配過程分析

linux內(nèi)存三大分配器：引導(dǎo)內(nèi)存分配器，伙伴分配器，slab分配器

伙伴分配器

當(dāng)系統(tǒng)內(nèi)核初始化完畢后，使用頁(yè)分配器管理物理頁(yè)，當(dāng)使用的頁(yè)分配器是伙伴分配器，伙伴分配器的特點(diǎn)是算法簡(jiǎn)單且高效，支持內(nèi)存節(jié)點(diǎn)和區(qū)域，為了預(yù)防內(nèi)存碎片，把物理內(nèi)存根據(jù)可移動(dòng)性分組，針對(duì)分配單頁(yè)做了性能優(yōu)化，為了減少處理器的鎖競(jìng)爭(zhēng)，在內(nèi)存區(qū)域增加1個(gè)每處理器頁(yè)集合。

1.伙伴分配器原理

連續(xù)的物理頁(yè)稱為頁(yè)塊（page block）。階（order）是伙伴分配器的一個(gè)專業(yè)術(shù)語(yǔ)，是頁(yè)的數(shù)量單位，2^n 個(gè)連續(xù)頁(yè)稱為n階頁(yè)塊。物理內(nèi)存被分成11個(gè)order:0 ~ 10,每個(gè)order中連續(xù)page的個(gè)數(shù)是2order,如果一個(gè)order中可用的memory size小于期望分配的size，那么更大order的內(nèi)存塊會(huì)被對(duì)半切分，切分之后的兩個(gè)小塊互為buddies。其中一個(gè)子塊用于分配，另一個(gè)空閑的。這些塊在必要時(shí)會(huì)連續(xù)減半，直到達(dá)到所需大小的memory 塊為止，當(dāng)一個(gè)block被釋放之后，會(huì)檢查它的buddies是否也是空閑的，如果是，那么這對(duì)buddies將會(huì)被合并。
滿足以下條件 的兩個(gè)n階頁(yè)塊稱為伙伴：
1）兩個(gè)頁(yè)塊是相鄰的，即物理地址是連續(xù)的；
2）頁(yè)塊的第一頁(yè)的物理頁(yè)號(hào)必須是2^n 的整數(shù)倍；
3）如果合并成（n+1）階頁(yè)塊，第一頁(yè)的物理頁(yè)號(hào)必須是2^(n+1) 的整數(shù)倍。

2.伙伴分配器的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：由于將物理內(nèi)存按照PFN將不同的page放入到不同order中，根據(jù)需要分配內(nèi)存的大小，計(jì)算當(dāng)前這次分配應(yīng)該在哪個(gè)order中去找空閑的內(nèi)存塊，如果當(dāng)前order中沒有空閑，則到更高階的order中去查找，因此分配的效率比boot memory的線性掃描bitmap要快很多。
缺點(diǎn)：
1）釋放page的時(shí)候調(diào)用方必須記住之前該page分配的order，然后釋放從該page開始的2order 個(gè)page，這對(duì)于調(diào)用者來(lái)說有點(diǎn)不方便
2）因?yàn)閎uddy allocator每次分配必須是2order 個(gè)page同時(shí)分配，這樣當(dāng)實(shí)際需要內(nèi)存大小小于2order 時(shí)，就會(huì)造成內(nèi)存浪費(fèi)，所以Linux為了解決buddy allocator造成的內(nèi)部碎片問題，后面會(huì)引入slab分配器。

3.伙伴分配器的分配釋放流程

伙伴分配器分配和釋放物理頁(yè)的數(shù)量單位為階。分配n階頁(yè)塊的過程如下：
1）查看是否有空閑的n階頁(yè)塊，如果有直接分配；否則，繼續(xù)執(zhí)行下一步；
2）查看是否存在空閑的（n+1）階頁(yè)塊，如果有，把（n+1）階頁(yè)塊分裂為兩個(gè)n階頁(yè)塊，一個(gè)插入空閑n階頁(yè)塊鏈表，另一個(gè)分配出去；否則繼續(xù)執(zhí)行下一步。
3）查看是否存在空閑的（n+2）階頁(yè)塊，如果有把（n+2）階頁(yè)塊分裂為兩個(gè)（n+1）階頁(yè)塊，一個(gè)插入空閑（n+1）階頁(yè)塊鏈表，另一個(gè)分裂為兩個(gè)n階頁(yè)塊，一個(gè)插入空間n階頁(yè)塊鏈表，另一個(gè)分配出去；如果沒有，繼續(xù)查看更高階是否存在空閑頁(yè)塊。

4.伙伴分配器的數(shù)據(jù)結(jié)構(gòu)

分區(qū)的伙伴分配器專注于某個(gè)內(nèi)存節(jié)點(diǎn)的某個(gè)區(qū)域。內(nèi)存區(qū)域的結(jié)構(gòu)體成員free_area用來(lái)維護(hù)空閑頁(yè)塊，數(shù)組下標(biāo)對(duì)應(yīng)頁(yè)塊的階數(shù)。

內(nèi)核源碼結(jié)構(gòu)：

struct?free_area?{
?struct?list_head?free_list[MIGRATE_TYPES];
?unsigned?long??nr_free;
};

內(nèi)核使用GFP_ZONE_TABLE 定義了區(qū)域類型映射表的標(biāo)志組合，其中GFP_ZONES_SHIFT是區(qū)域類型占用的位數(shù)，GFP_ZONE_TABLE 把每種標(biāo)志組合映射到32位整數(shù)的某個(gè)位置，偏移是（標(biāo)志組合*區(qū)域類型位數(shù)），從這個(gè)偏移開始的GFP_ZONES_SHIFT個(gè)二進(jìn)制存放區(qū)域類型。

#define?GFP_ZONE_TABLE?(?
?(ZONE_NORMAL?<<?0?*?GFP_ZONES_SHIFT)???????????
?|?(OPT_ZONE_DMA?<<?___GFP_DMA?*?GFP_ZONES_SHIFT)?????????
?|?(OPT_ZONE_HIGHMEM?<<?___GFP_HIGHMEM?*?GFP_ZONES_SHIFT)????????
?|?(OPT_ZONE_DMA32?<<?___GFP_DMA32?*?GFP_ZONES_SHIFT)?????????
?|?(ZONE_NORMAL?<<?___GFP_MOVABLE?*?GFP_ZONES_SHIFT)?????????
?|?(OPT_ZONE_DMA?<<?(___GFP_MOVABLE?|?___GFP_DMA)?*?GFP_ZONES_SHIFT)????
?|?(ZONE_MOVABLE?<<?(___GFP_MOVABLE?|?___GFP_HIGHMEM)?*?GFP_ZONES_SHIFT)
?|?(OPT_ZONE_DMA32?<<?(___GFP_MOVABLE?|?___GFP_DMA32)?*?GFP_ZONES_SHIFT)
)
//根據(jù)flags標(biāo)志獲取首選區(qū)域
#define?___GFP_DMA??0x01u
#define?___GFP_HIGHMEM??0x02u
#define?___GFP_DMA32??0x04u
#define?___GFP_MOVABLE??0x08u

5.備用區(qū)域列表

備用區(qū)域這個(gè)東西很重要，但是我現(xiàn)在也不能完完全全的了解他，只知道他可以加快我們申請(qǐng)內(nèi)存的速度，下面的快速路徑會(huì)用到他。
如果首選的內(nèi)存節(jié)點(diǎn)或區(qū)域不能滿足分配請(qǐng)求，可以從備用的內(nèi)存區(qū)域借用物理頁(yè)。借用必須遵守相應(yīng)的規(guī)則。
借用規(guī)則：
1）一個(gè)內(nèi)存節(jié)點(diǎn)的某個(gè)區(qū)域類型可以從另外一個(gè)內(nèi)存節(jié)點(diǎn)的相同區(qū)域類型借用物理頁(yè)，比如節(jié)點(diǎn)0的普通區(qū)域可以從節(jié)點(diǎn)為1的普通區(qū)域借用物理頁(yè)。
2）高區(qū)域類型的可以從地區(qū)域類型借用物理頁(yè)，比如普通區(qū)域可以從DMA區(qū)域借用物理頁(yè)
3）地區(qū)域類型的不可以從高區(qū)域類型借用物理頁(yè)，比如DMA區(qū)域不可以從普通區(qū)域借用物理頁(yè)
內(nèi)存節(jié)點(diǎn)的結(jié)構(gòu)體pg_data_t實(shí)例已定義備用區(qū)域列表node_zonelists。

6.伙伴分配器的結(jié)構(gòu)

內(nèi)核源碼如下：

typedef?struct?pglist_data?{
?struct?zone?node_zones[MAX_NR_ZONES];//內(nèi)存區(qū)域數(shù)組
?struct?zonelist?node_zonelists[MAX_ZONELISTS];//MAX_ZONELISTS個(gè)備用區(qū)域數(shù)組

?int?nr_zones;//該節(jié)點(diǎn)包含的內(nèi)存區(qū)域數(shù)量
......
}
//struct?zone在linux內(nèi)存管理（一）中
struct?zonelist?{
?struct?zoneref?_zonerefs[MAX_ZONES_PER_ZONELIST?+?1];
};
struct?zoneref?{
?struct?zone?*zone;//指向內(nèi)存區(qū)域數(shù)據(jù)結(jié)構(gòu)
?int?zone_idx;//成員zone指向內(nèi)存區(qū)域的類型
};
enum?{
?ZONELIST_FALLBACK,//包含所有內(nèi)存節(jié)點(diǎn)的的備用區(qū)域列表
#ifdef?CONFIG_NUMA
?/*
??*?The?NUMA?zonelists?are?doubled?because?we?need?zonelists?that
??*?restrict?the?allocations?to?a?single?node?for?__GFP_THISNODE.
??*/
?ZONELIST_NOFALLBACK,//只包含當(dāng)前節(jié)點(diǎn)的備用區(qū)域列表（NUMA專用）
#endif
?MAX_ZONELISTS//表示備用區(qū)域列表數(shù)量
};

UMA系統(tǒng)只有一個(gè)備用區(qū)域的列表，按照區(qū)域類型從高到低順序排列。假設(shè)UMA系統(tǒng)中包含普通區(qū)域和DMA區(qū)域，則備用區(qū)域列表為:(普通區(qū)域、MDA區(qū)域)。NUMA系統(tǒng)中每個(gè)內(nèi)存節(jié)點(diǎn)有兩個(gè)備用區(qū)域列表:一個(gè)包含所有節(jié)點(diǎn)的內(nèi)存區(qū)域，另一個(gè)僅包含當(dāng)前節(jié)點(diǎn)的內(nèi)存區(qū)域。

ZONELIST_FALLBACK（包含所有內(nèi)存節(jié)點(diǎn)的備用區(qū)域）列表有兩種排序方法:
a.節(jié)點(diǎn)優(yōu)先順序
先根據(jù)節(jié)點(diǎn)距離從小到大排序, 然后在每個(gè)節(jié)點(diǎn)里面根據(jù)區(qū)域類型從高到低排序。
優(yōu)點(diǎn)是優(yōu)先選擇距離近的內(nèi)存, 缺點(diǎn)是在高區(qū)域耗盡以前使用低區(qū)域。
b.區(qū)域優(yōu)先順序
先根據(jù)區(qū)域類型從高到低排序, 然后在每個(gè)區(qū)域類型里面根據(jù)節(jié)點(diǎn)距離從小到大排序。
優(yōu)點(diǎn)是減少低區(qū)域耗盡的概率, 缺點(diǎn)是不能保證優(yōu)先選擇距離近的內(nèi)存。
默認(rèn)的排序方法就是自動(dòng)選擇最優(yōu)的排序方法：比如是64位系統(tǒng)，因?yàn)樾枰狣MA和DMA32區(qū)域的備用相對(duì)少，所以選擇節(jié)點(diǎn)優(yōu)先順序；如果是32位系統(tǒng)，選擇區(qū)域優(yōu)先順序。

7.內(nèi)存區(qū)域水線

首選的內(nèi)存區(qū)域什么情況下從備用區(qū)域借用物理頁(yè)呢？每個(gè)內(nèi)存區(qū)域有3個(gè)水線：
a.高水線（high）：如果內(nèi)存區(qū)域的空閑頁(yè)數(shù)大于高水線，說明內(nèi)存區(qū)域的內(nèi)存非常充足；
b.低水線（low）：如果內(nèi)存區(qū)域的空閑頁(yè)數(shù)小于低水線，說明內(nèi)存區(qū)域的內(nèi)存輕微不足；
c.最低水線（min）：如果內(nèi)存區(qū)域的空閑頁(yè)數(shù)小于最低水線，說明內(nèi)存區(qū)域的內(nèi)存嚴(yán)重不足。
而且每個(gè)區(qū)域的水位線是初始化的時(shí)候通過每個(gè)區(qū)域的物理頁(yè)情況計(jì)算出來(lái)的。計(jì)算后存到struct zone的watermark數(shù)組中，使用的時(shí)候直接通過下面的宏定義獲?。?/p>

#define?min_wmark_pages(z)?(z->watermark[WMARK_MIN])
#define?low_wmark_pages(z)?(z->watermark[WMARK_LOW])
#define?high_wmark_pages(z)?(z->watermark[WMARK_HIGH])

struct zone的數(shù)據(jù)結(jié)構(gòu)：

spanned_pages?=?zone_end_pfn?-?zone_start_pfn;//區(qū)域結(jié)束的物理頁(yè)減去起始頁(yè)=當(dāng)前區(qū)域跨越的總頁(yè)數(shù)（包括空洞）
present_pages?=?spanned_pages?-?absent_pages(pages?in?holes)//當(dāng)前區(qū)域跨越的總頁(yè)數(shù)-空洞頁(yè)數(shù)=當(dāng)前區(qū)域可用物理頁(yè)數(shù)
managed_pages?=?present_pages?-?reserved_pages//當(dāng)前區(qū)域可用物理頁(yè)數(shù)-預(yù)留的頁(yè)數(shù)=伙伴分配器管理物理頁(yè)數(shù)

最低水線以下的內(nèi)存稱為緊急保留內(nèi)存，一般用于內(nèi)存回收，其他情況不可以動(dòng)用緊急保留內(nèi)存，在內(nèi)存嚴(yán)重不足的緊急情況下，給承諾"分給我們少量的緊急保留內(nèi)存使用，我可以釋放更多的內(nèi)存"的進(jìn)程使用。

可以通過/proc/zoneinfo看到系統(tǒng)zone的水位線和物理頁(yè)情況

jian@ubuntu:~/share/linux-4.19.40-note$?cat?/proc/zoneinfo?
Node?0,?zone??????DMA
??pages?free?????3912
????????min??????7
????????low??????8
????????high?????10
????????scanned??0
????????spanned??4095
????????present??3997
????????managed??3976
...
Node?0,?zone????DMA32
??pages?free?????6515
????????min??????1497
????????low??????1871
????????high?????2245
????????scanned??0
????????spanned??1044480
????????present??782288
????????managed??762172
??...
Node?0,?zone???Normal
??pages?free?????2964
????????min??????474
????????low??????592
????????high?????711
????????scanned??0
????????spanned??262144
????????present??262144
????????managed??241089
??...

8.伙伴分配器分配過程分析

當(dāng)向內(nèi)核請(qǐng)求分配 (2^(i-1)，2^i]數(shù)目的頁(yè)塊時(shí)，按照 2^i 頁(yè)塊請(qǐng)求處理。如果對(duì)應(yīng)的頁(yè)塊鏈表中沒有空閑頁(yè)塊，那我們就在更大的頁(yè)塊鏈表中去找。當(dāng)分配的頁(yè)塊中有多余的頁(yè)時(shí)，伙伴系統(tǒng)會(huì)根據(jù)多余的頁(yè)塊大小插入到對(duì)應(yīng)的空閑頁(yè)塊鏈表中。
例如，要請(qǐng)求一個(gè) 128 個(gè)頁(yè)的頁(yè)塊時(shí)，先檢查 128 個(gè)頁(yè)的頁(yè)塊鏈表是否有空閑塊。如果沒有，則查 256 個(gè)頁(yè)的頁(yè)塊鏈表；如果有空閑塊的話，則將 256 個(gè)頁(yè)的頁(yè)塊分成兩份，一份使用，一份插入 128 個(gè)頁(yè)的頁(yè)塊鏈表中。如果還是沒有，就查 512 個(gè)頁(yè)的頁(yè)塊鏈表；如果有的話，就分裂為 128、128、256 三個(gè)頁(yè)塊，一個(gè) 128 的使用，剩余兩個(gè)插入對(duì)應(yīng)頁(yè)塊鏈表。
伙伴分配器進(jìn)行頁(yè)分配的時(shí)候首先調(diào)用alloc_pages，alloc_pages 會(huì)調(diào)用 alloc_pages_current，alloc_pages_current會(huì)調(diào)用__alloc_pages_nodemask函數(shù)，他是伙伴分配器的核心函數(shù)：

/*?The?ALLOC_WMARK?bits?are?used?as?an?index?to?zone->watermark?*/
#define?ALLOC_WMARK_MIN??WMARK_MIN?//使用最低水線
#define?ALLOC_WMARK_LOW??WMARK_LOW?//使用低水線
#define?ALLOC_WMARK_HIGH?WMARK_HIGH?//使用高水線
#define?ALLOC_NO_WATERMARKS?0x04???//完全不檢查水線
#define?ALLOC_WMARK_MASK?(ALLOC_NO_WATERMARKS-1)//得到水位線的掩碼
#ifdef?CONFIG_MMU
#define?ALLOC_OOM??0x08?//允許內(nèi)存耗盡
#else
#define?ALLOC_OOM??ALLOC_NO_WATERMARKS//允許內(nèi)存耗盡
#endif
#define?ALLOC_HARDER??0x10?//試圖更努力分配
#define?ALLOC_HIGH???0x20?//調(diào)用者是高優(yōu)先級(jí)
#define?ALLOC_CPUSET??0x40?//檢查?cpuset?是否允許進(jìn)程從某個(gè)內(nèi)存節(jié)點(diǎn)分配頁(yè)
#define?ALLOC_CMA???0x80?//允許從CMA（連續(xù)內(nèi)存分配器）遷移類型分配

上面是alloc_pages的第一個(gè)參數(shù)分配標(biāo)志位，表示分配的允許情況，alloc_pages的第二個(gè)參數(shù)表示分配的階數(shù)

static?inline?struct?page?*
alloc_pages(gfp_t?gfp_mask,?unsigned?int?order)
{
?return?alloc_pages_current(gfp_mask,?order);
}

struct?page?*alloc_pages_current(gfp_t?gfp,?unsigned?order)
{
?struct?mempolicy?*pol?=?&default_policy;
?struct?page?*page;

?if?(!in_interrupt()?&&?!(gfp?&?__GFP_THISNODE))
??pol?=?get_task_policy(current);

?if?(pol->mode?==?MPOL_INTERLEAVE)
??page?=?alloc_page_interleave(gfp,?order,?interleave_nodes(pol));
?else
??page?=?__alloc_pages_nodemask(gfp,?order,
????policy_node(gfp,?pol,?numa_node_id()),
????policy_nodemask(gfp,?pol));

?return?page;
}

struct?page?*
__alloc_pages_nodemask(gfp_t?gfp_mask,?unsigned?int?order,?int?preferred_nid,
???????nodemask_t?*nodemask)
{
?...
?/*?First?allocation?attempt?*/?//快速路徑分配函數(shù)
?page?=?get_page_from_freelist(alloc_mask,?order,?alloc_flags,?&ac);
?if?(likely(page))
??goto?out;
?...
?//快速路徑分配失敗，會(huì)調(diào)用下面的慢速分配函數(shù)
?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;
?}

?trace_mm_page_alloc(page,?order,?alloc_mask,?ac.migratetype);

?return?page;
}

從伙伴分配器的核心函數(shù)__alloc_pages_nodemask可以看到函數(shù)主要兩部分，一是執(zhí)行快速分配函數(shù)get_page_from_freelist，二是執(zhí)行慢速分配函數(shù)__alloc_pages_slowpath。現(xiàn)在先看快速分配函數(shù)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;

?//掃描備用區(qū)域列表中每一個(gè)滿足條件的區(qū)域：區(qū)域類型小于等于首選區(qū)域類型
?for_next_zone_zonelist_nodemask(zone,?z,?ac->zonelist,?ac->high_zoneidx,
????????ac->nodemask)?{
??struct?page?*page;
??unsigned?long?mark;

??if?(cpusets_enabled()?&&???//如果編譯了cpuset功能??
???(alloc_flags?&?ALLOC_CPUSET)?&&?//如果設(shè)置了ALLOC_CPUSET
???!__cpuset_zone_allowed(zone,?gfp_mask))?//如果cpu設(shè)置了不允許從當(dāng)前區(qū)域分配內(nèi)存
????continue;???????//那么不允許從這個(gè)區(qū)域分配，進(jìn)入下個(gè)循環(huán)
??
??if?(ac->spread_dirty_pages)?{//如果設(shè)置了寫標(biāo)志位，表示要分配寫緩存
???//那么要檢查內(nèi)存臟頁(yè)數(shù)量是否超出限制，超過限制就不能從這個(gè)區(qū)域分配
???if?(last_pgdat_dirty_limit?==?zone->zone_pgdat)
????continue;

???if?(!node_dirty_ok(zone->zone_pgdat))?{
????last_pgdat_dirty_limit?=?zone->zone_pgdat;
????continue;
???}
??}

??mark?=?zone->watermark[alloc_flags?&?ALLOC_WMARK_MASK];//檢查允許分配水線
??//判斷（區(qū)域空閑頁(yè)-申請(qǐng)頁(yè)數(shù)）是否小于水線
??if?(!zone_watermark_fast(zone,?order,?mark,
???????????ac_classzone_idx(ac),?alloc_flags))?{
???int?ret;

???/*?Checked?here?to?keep?the?fast?path?fast?*/
???BUILD_BUG_ON(ALLOC_NO_WATERMARKS?<?NR_WMARK);
???//如果沒有水線要求，直接選擇該區(qū)域
???if?(alloc_flags?&?ALLOC_NO_WATERMARKS)
????goto?try_this_zone;

???//如果沒有開啟節(jié)點(diǎn)回收功能或者當(dāng)前節(jié)點(diǎn)和首選節(jié)點(diǎn)距離大于回收距離
???if?(node_reclaim_mode?==?0?||
???????!zone_allows_reclaim(ac->preferred_zoneref->zone,?zone))
????continue;

???//從節(jié)點(diǎn)回收“沒有映射到進(jìn)程虛擬地址空間的內(nèi)存頁(yè)”，然后檢查水線
???ret?=?node_reclaim(zone->zone_pgdat,?gfp_mask,?order);
???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))
?????goto?try_this_zone;

????continue;
???}
??}

try_this_zone://滿足上面的條件了，開始分配
??//從當(dāng)前區(qū)域分配頁(yè)
??page?=?rmqueue(ac->preferred_zoneref->zone,?zone,?order,
????gfp_mask,?alloc_flags,?ac->migratetype);
??if?(page)?{
???//分配成功，初始化頁(yè)
???prep_new_page(page,?order,?gfp_mask,?alloc_flags);

???/*
????*?If?this?is?a?high-order?atomic?allocation?then?check
????*?if?the?pageblock?should?be?reserved?for?the?future
????*/
???//如果這是一個(gè)高階的內(nèi)存并且是ALLOC_HARDER，需要檢查以后是否需要保留
???if?(unlikely(order?&&?(alloc_flags?&?ALLOC_HARDER)))
????reserve_highatomic_pageblock(page,?zone,?order);

???return?page;
??}?else?{
#ifdef?CONFIG_DEFERRED_STRUCT_PAGE_INIT
???/*?Try?again?if?zone?has?deferred?pages?*/
???//如果分配失敗，延遲分配
???if?(static_branch_unlikely(&deferred_pages))?{
????if?(_deferred_grow_zone(zone,?order))
?????goto?try_this_zone;
???}
#endif
??}
?}

?return?NULL;
}

每一個(gè) zone，都有伙伴系統(tǒng)維護(hù)的各種大小的隊(duì)列，就像上面伙伴系統(tǒng)原理里講的那樣。這里調(diào)用 rmqueue 就很好理解了，就是找到合適大小的那個(gè)隊(duì)列，把頁(yè)面取下來(lái)。接下來(lái)的調(diào)用鏈?zhǔn)?rmqueue->__rmqueue->__rmqueue_smallest。在這里，我們能清楚看到伙伴系統(tǒng)的邏輯。

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]);
????page?=?list_first_entry_or_null(&area->free_list[migratetype],
??????????????struct?page,?lru);
????if?(!page)
??????continue;
????list_del(&page->lru);
????rmv_page_order(page);
????area->nr_free--;
????expand(zone,?page,?order,?current_order,?area,?migratetype);
????set_pcppage_migratetype(page,?migratetype);
????return?page;
??}


??return?NULL;

從當(dāng)前的 order，也即指數(shù)開始，在伙伴系統(tǒng)的 free_area 找 2^order 大小的頁(yè)塊。如果鏈表的第一個(gè)不為空，就找到了；如果為空，就到更大的 order 的頁(yè)塊鏈表里面去找。找到以后，除了將頁(yè)塊從鏈表中取下來(lái)，我們還要把多余部分放到其他頁(yè)塊鏈表里面。expand 就是干這個(gè)事情的。area–就是伙伴系統(tǒng)那個(gè)表里面的前一項(xiàng)，前一項(xiàng)里面的頁(yè)塊大小是當(dāng)前項(xiàng)的頁(yè)塊大小除以 2，size 右移一位也就是除以 2，list_add 就是加到鏈表上，nr_free++ 就是計(jì)數(shù)加 1。
然后看看慢速分配函數(shù)__alloc_pages_slowpath：

static?inline?struct?page?*
__alloc_pages_slowpath(gfp_t?gfp_mask,?unsigned?int?order,
??????struct?alloc_context?*ac)
{
?bool?can_direct_reclaim?=?gfp_mask?&?__GFP_DIRECT_RECLAIM;
?const?bool?costly_order?=?order?>?PAGE_ALLOC_COSTLY_ORDER;
?struct?page?*page?=?NULL;
?unsigned?int?alloc_flags;
?unsigned?long?did_some_progress;
?enum?compact_priority?compact_priority;
?enum?compact_result?compact_result;
?int?compaction_retries;
?int?no_progress_loops;
?unsigned?int?cpuset_mems_cookie;
?int?reserve_flags;

?/*
??*?We?also?sanity?check?to?catch?abuse?of?atomic?reserves?being?used?by
??*?callers?that?are?not?in?atomic?context.
??*/
?if?(WARN_ON_ONCE((gfp_mask?&?(__GFP_ATOMIC|__GFP_DIRECT_RECLAIM))?==
????(__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)))
??gfp_mask?&=?~__GFP_ATOMIC;

retry_cpuset:
?compaction_retries?=?0;
?no_progress_loops?=?0;
?compact_priority?=?DEF_COMPACT_PRIORITY;
?//后面可能會(huì)檢查cpuset是否允許當(dāng)前進(jìn)程從哪些內(nèi)存節(jié)點(diǎn)申請(qǐng)頁(yè)
?cpuset_mems_cookie?=?read_mems_allowed_begin();

?/*
??*?The?fast?path?uses?conservative?alloc_flags?to?succeed?only?until
??*?kswapd?needs?to?be?woken?up,?and?to?avoid?the?cost?of?setting?up
??*?alloc_flags?precisely.?So?we?do?that?now.
??*/
?//把分配標(biāo)志位轉(zhuǎn)化為內(nèi)部的分配標(biāo)志位
?alloc_flags?=?gfp_to_alloc_flags(gfp_mask);

?/*
??*?We?need?to?recalculate?the?starting?point?for?the?zonelist?iterator
??*?because?we?might?have?used?different?nodemask?in?the?fast?path,?or
??*?there?was?a?cpuset?modification?and?we?are?retrying?-?otherwise?we
??*?could?end?up?iterating?over?non-eligible?zones?endlessly.
??*/
?//獲取首選的內(nèi)存區(qū)域，因?yàn)樵诳焖俾窂街惺褂昧瞬煌墓?jié)點(diǎn)掩碼，避免再次遍歷不合格的區(qū)域。
?ac->preferred_zoneref?=?first_zones_zonelist(ac->zonelist,
?????ac->high_zoneidx,?ac->nodemask);
?if?(!ac->preferred_zoneref->zone)
??goto?nopage;
?
?//異步回收頁(yè)，喚醒kswapd內(nèi)核線程進(jìn)行頁(yè)面回收
?if?(gfp_mask?&?__GFP_KSWAPD_RECLAIM)
??wake_all_kswapds(order,?gfp_mask,?ac);

?/*
??*?The?adjusted?alloc_flags?might?result?in?immediate?success,?so?try
??*?that?first
??*/
?//調(diào)整alloc_flags后可能會(huì)立即申請(qǐng)成功，所以先嘗試一下
?page?=?get_page_from_freelist(gfp_mask,?order,?alloc_flags,?ac);
?if?(page)
??goto?got_pg;

?/*
??*?For?costly?allocations,?try?direct?compaction?first,?as?it's?likely
??*?that?we?have?enough?base?pages?and?don't?need?to?reclaim.?For?non-
??*?movable?high-order?allocations,?do?that?as?well,?as?compaction?will
??*?try?prevent?permanent?fragmentation?by?migrating?from?blocks?of?the
??*?same?migratetype.
??*?Don't?try?this?for?allocations?that?are?allowed?to?ignore
??*?watermarks,?as?the?ALLOC_NO_WATERMARKS?attempt?didn't?yet?happen.
??*/
?//申請(qǐng)階數(shù)大于0，不可移動(dòng)的位于高階的，忽略水位線的
?if?(can_direct_reclaim?&&
???(costly_order?||
??????(order?>?0?&&?ac->migratetype?!=?MIGRATE_MOVABLE))
???&&?!gfp_pfmemalloc_allowed(gfp_mask))?{
??//直接頁(yè)面回收，然后進(jìn)行頁(yè)面分配
??page?=?__alloc_pages_direct_compact(gfp_mask,?order,
??????alloc_flags,?ac,
??????INIT_COMPACT_PRIORITY,
??????&compact_result);
??if?(page)
???goto?got_pg;

??/*
???*?Checks?for?costly?allocations?with?__GFP_NORETRY,?which
???*?includes?THP?page?fault?allocations
???*/
??if?(costly_order?&&?(gfp_mask?&?__GFP_NORETRY))?{
???/*
????*?If?compaction?is?deferred?for?high-order?allocations,
????*?it?is?because?sync?compaction?recently?failed.?If
????*?this?is?the?case?and?the?caller?requested?a?THP
????*?allocation,?we?do?not?want?to?heavily?disrupt?the
????*?system,?so?we?fail?the?allocation?instead?of?entering
????*?direct?reclaim.
????*/
???if?(compact_result?==?COMPACT_DEFERRED)
????goto?nopage;

???/*
????*?Looks?like?reclaim/compaction?is?worth?trying,?but
????*?sync?compaction?could?be?very?expensive,?so?keep
????*?using?async?compaction.
????*/
???//同步壓縮非常昂貴，所以繼續(xù)使用異步壓縮
???compact_priority?=?INIT_COMPACT_PRIORITY;
??}
?}

retry:
?/*?Ensure?kswapd?doesn't?accidentally?go?to?sleep?as?long?as?we?loop?*/
?//如果頁(yè)回收線程意外睡眠則再次喚醒
?if?(gfp_mask?&?__GFP_KSWAPD_RECLAIM)
??wake_all_kswapds(order,?gfp_mask,?ac);

?//如果調(diào)用者承若給我們緊急內(nèi)存使用，我們就忽略水線
?reserve_flags?=?__gfp_pfmemalloc_flags(gfp_mask);
?if?(reserve_flags)
??alloc_flags?=?reserve_flags;

?/*
??*?Reset?the?nodemask?and?zonelist?iterators?if?memory?policies?can?be
??*?ignored.?These?allocations?are?high?priority?and?system?rather?than
??*?user?oriented.
??*/
?//如果可以忽略內(nèi)存策略，則重置nodemask和zonelist
?if?(!(alloc_flags?&?ALLOC_CPUSET)?||?reserve_flags)?{
??ac->nodemask?=?NULL;
??ac->preferred_zoneref?=?first_zones_zonelist(ac->zonelist,
?????ac->high_zoneidx,?ac->nodemask);
?}

?/*?Attempt?with?potentially?adjusted?zonelist?and?alloc_flags?*/
?//嘗試使用可能調(diào)整的區(qū)域備用列表和分配標(biāo)志
?page?=?get_page_from_freelist(gfp_mask,?order,?alloc_flags,?ac);
?if?(page)
??goto?got_pg;

?/*?Caller?is?not?willing?to?reclaim,?we?can't?balance?anything?*/
?//如果不可以直接回收，則申請(qǐng)失敗
?if?(!can_direct_reclaim)
??goto?nopage;

?/*?Avoid?recursion?of?direct?reclaim?*/
?if?(current->flags?&?PF_MEMALLOC)
??goto?nopage;

?/*?Try?direct?reclaim?and?then?allocating?*/
?//直接頁(yè)面回收，然后進(jìn)行頁(yè)面分配
?page?=?__alloc_pages_direct_reclaim(gfp_mask,?order,?alloc_flags,?ac,
???????&did_some_progress);
?if?(page)
??goto?got_pg;

?/*?Try?direct?compaction?and?then?allocating?*/
?//進(jìn)行頁(yè)面壓縮，然后進(jìn)行頁(yè)面分配
?page?=?__alloc_pages_direct_compact(gfp_mask,?order,?alloc_flags,?ac,
?????compact_priority,?&compact_result);
?if?(page)
??goto?got_pg;

?/*?Do?not?loop?if?specifically?requested?*/
?//如果調(diào)用者要求不要重試，則放棄
?if?(gfp_mask?&?__GFP_NORETRY)
??goto?nopage;

?/*
??*?Do?not?retry?costly?high?order?allocations?unless?they?are
??*?__GFP_RETRY_MAYFAIL
??*/
?//不要重試代價(jià)高昂的高階分配，除非它們是__GFP_RETRY_MAYFAIL
?if?(costly_order?&&?!(gfp_mask?&?__GFP_RETRY_MAYFAIL))
??goto?nopage;
?
?//重新嘗試回收頁(yè)
?if?(should_reclaim_retry(gfp_mask,?order,?ac,?alloc_flags,
?????did_some_progress?>?0,?&no_progress_loops))
??goto?retry;

?/*
??*?It?doesn't?make?any?sense?to?retry?for?the?compaction?if?the?order-0
??*?reclaim?is?not?able?to?make?any?progress?because?the?current
??*?implementation?of?the?compaction?depends?on?the?sufficient?amount
??*?of?free?memory?(see?__compaction_suitable)
??*/
?//如果申請(qǐng)階數(shù)大于0，判斷是否需要重新嘗試壓縮
?if?(did_some_progress?>?0?&&
???should_compact_retry(ac,?order,?alloc_flags,
????compact_result,?&compact_priority,
????&compaction_retries))
??goto?retry;


?/*?Deal?with?possible?cpuset?update?races?before?we?start?OOM?killing?*/
?//如果cpuset允許修改內(nèi)存節(jié)點(diǎn)申請(qǐng)就修改
?if?(check_retry_cpuset(cpuset_mems_cookie,?ac))
??goto?retry_cpuset;

?/*?Reclaim?has?failed?us,?start?killing?things?*/
?//使用oom選擇一個(gè)進(jìn)程殺死
?page?=?__alloc_pages_may_oom(gfp_mask,?order,?ac,?&did_some_progress);
?if?(page)
??goto?got_pg;

?/*?Avoid?allocations?with?no?watermarks?from?looping?endlessly?*/
?//如果當(dāng)前進(jìn)程是oom選擇的進(jìn)程，并且忽略了水線，則放棄申請(qǐng)
?if?(tsk_is_oom_victim(current)?&&
?????(alloc_flags?==?ALLOC_OOM?||
??????(gfp_mask?&?__GFP_NOMEMALLOC)))
??goto?nopage;

?/*?Retry?as?long?as?the?OOM?killer?is?making?progress?*/
?//如果OOM殺手正在取得進(jìn)展，再試一次
?if?(did_some_progress)?{
??no_progress_loops?=?0;
??goto?retry;
?}

nopage:
?/*?Deal?with?possible?cpuset?update?races?before?we?fail?*/
?if?(check_retry_cpuset(cpuset_mems_cookie,?ac))
??goto?retry_cpuset;

?/*
??*?Make?sure?that?__GFP_NOFAIL?request?doesn't?leak?out?and?make?sure
??*?we?always?retry
??*/
?if?(gfp_mask?&?__GFP_NOFAIL)?{
??/*
???*?All?existing?users?of?the?__GFP_NOFAIL?are?blockable,?so?warn
???*?of?any?new?users?that?actually?require?GFP_NOWAIT
???*/
??if?(WARN_ON_ONCE(!can_direct_reclaim))
???goto?fail;

??/*
???*?PF_MEMALLOC?request?from?this?context?is?rather?bizarre
???*?because?we?cannot?reclaim?anything?and?only?can?loop?waiting
???*?for?somebody?to?do?a?work?for?us
???*/
??WARN_ON_ONCE(current->flags?&?PF_MEMALLOC);

??/*
???*?non?failing?costly?orders?are?a?hard?requirement?which?we
???*?are?not?prepared?for?much?so?let's?warn?about?these?users
???*?so?that?we?can?identify?them?and?convert?them?to?something
???*?else.
???*/
??WARN_ON_ONCE(order?>?PAGE_ALLOC_COSTLY_ORDER);

??/*
???*?Help?non-failing?allocations?by?giving?them?access?to?memory
???*?reserves?but?do?not?use?ALLOC_NO_WATERMARKS?because?this
???*?could?deplete?whole?memory?reserves?which?would?just?make
???*?the?situation?worse
???*/
??//允許它們?cè)L問內(nèi)存?zhèn)溆昧斜?
??page?=?__alloc_pages_cpuset_fallback(gfp_mask,?order,?ALLOC_HARDER,?ac);
??if?(page)
???goto?got_pg;

??cond_resched();
??goto?retry;
?}
fail:
?warn_alloc(gfp_mask,?ac->nodemask,
???"page?allocation?failure:?order:%u",?order);
got_pg:
?return?page;
}