一文搞定伙伴分配器

伙伴分配器

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

1.伙伴分配器原理

連續(xù)的物理頁稱為頁塊（page block）。階（order）是伙伴分配器的一個專業(yè)術(shù)語，是頁的數(shù)量單位，2^n 個連續(xù)頁稱為n階頁塊。物理內(nèi)存被分成11個order:0 ~ 10,每個order中連續(xù)page的個數(shù)是2order,如果一個order中可用的memory size小于期望分配的size，那么更大order的內(nèi)存塊會被對半切分，切分之后的兩個小塊互為buddies。其中一個子塊用于分配，另一個空閑的。這些塊在必要時會連續(xù)減半，直到達(dá)到所需大小的memory 塊為止，當(dāng)一個block被釋放之后，會檢查它的buddies是否也是空閑的，如果是，那么這對buddies將會被合并。
滿足以下條件 的兩個n階頁塊稱為伙伴：
1）兩個頁塊是相鄰的，即物理地址是連續(xù)的；
2）頁塊的第一頁的物理頁號必須是2^n 的整數(shù)倍；
3）如果合并成（n+1）階頁塊，第一頁的物理頁號必須是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)該在哪個order中去找空閑的內(nèi)存塊，如果當(dāng)前order中沒有空閑，則到更高階的order中去查找，因此分配的效率比boot memory的線性掃描bitmap要快很多。
缺點(diǎn)：
1）釋放page的時候調(diào)用方必須記住之前該page分配的order，然后釋放從該page開始的2order 個page，這對于調(diào)用者來說有點(diǎn)不方便
2）因?yàn)閎uddy allocator每次分配必須是2order 個page同時分配，這樣當(dāng)實(shí)際需要內(nèi)存大小小于2order 時，就會造成內(nèi)存浪費(fèi)，所以Linux為了解決buddy allocator造成的內(nèi)部碎片問題，后面會引入slab分配器。

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

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

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

分區(qū)的伙伴分配器專注于某個內(nèi)存節(jié)點(diǎn)的某個區(qū)域。內(nèi)存區(qū)域的結(jié)構(gòu)體成員free_area用來維護(hù)空閑頁塊，數(shù)組下標(biāo)對應(yīng)頁塊的階數(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ù)的某個位置，偏移是（標(biāo)志組合*區(qū)域類型位數(shù)），從這個偏移開始的GFP_ZONES_SHIFT個二進(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ū)域這個東西很重要，但是我現(xiàn)在也不能完完全全的了解他，只知道他可以加快我們申請內(nèi)存的速度，下面的快速路徑會用到他。
如果首選的內(nèi)存節(jié)點(diǎn)或區(qū)域不能滿足分配請求，可以從備用的內(nèi)存區(qū)域借用物理頁。借用必須遵守相應(yīng)的規(guī)則。
借用規(guī)則：
1）一個內(nèi)存節(jié)點(diǎn)的某個區(qū)域類型可以從另外一個內(nèi)存節(jié)點(diǎn)的相同區(qū)域類型借用物理頁，比如節(jié)點(diǎn)0的普通區(qū)域可以從節(jié)點(diǎn)為1的普通區(qū)域借用物理頁。
2）高區(qū)域類型的可以從地區(qū)域類型借用物理頁，比如普通區(qū)域可以從DMA區(qū)域借用物理頁
3）地區(qū)域類型的不可以從高區(qū)域類型借用物理頁，比如DMA區(qū)域不可以從普通區(qū)域借用物理頁
內(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個備用區(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)只有一個備用區(qū)域的列表，按照區(qū)域類型從高到低順序排列。假設(shè)UMA系統(tǒng)中包含普通區(qū)域和DMA區(qū)域，則備用區(qū)域列表為:(普通區(qū)域、MDA區(qū)域)。NUMA系統(tǒng)中每個內(nèi)存節(jié)點(diǎn)有兩個備用區(qū)域列表:一個包含所有節(jié)點(diǎn)的內(nèi)存區(qū)域，另一個僅包含當(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)距離從小到大排序, 然后在每個節(jié)點(diǎn)里面根據(jù)區(qū)域類型從高到低排序。
優(yōu)點(diǎn)是優(yōu)先選擇距離近的內(nèi)存, 缺點(diǎn)是在高區(qū)域耗盡以前使用低區(qū)域。
b.區(qū)域優(yōu)先順序
先根據(jù)區(qū)域類型從高到低排序, 然后在每個區(qū)域類型里面根據(jù)節(jié)點(diǎn)距離從小到大排序。
優(yōu)點(diǎn)是減少低區(qū)域耗盡的概率, 缺點(diǎn)是不能保證優(yōu)先選擇距離近的內(nèi)存。
默認(rèn)的排序方法就是自動選擇最優(yōu)的排序方法：比如是64位系統(tǒng)，因?yàn)樾枰狣MA和DMA32區(qū)域的備用相對少，所以選擇節(jié)點(diǎn)優(yōu)先順序；如果是32位系統(tǒng)，選擇區(qū)域優(yōu)先順序。

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

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

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

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

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

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)核請求分配 (2^(i-1)，2^i]數(shù)目的頁塊時，按照 2^i 頁塊請求處理。如果對應(yīng)的頁塊鏈表中沒有空閑頁塊，那我們就在更大的頁塊鏈表中去找。當(dāng)分配的頁塊中有多余的頁時，伙伴系統(tǒng)會根據(jù)多余的頁塊大小插入到對應(yīng)的空閑頁塊鏈表中。
例如，要請求一個 128 個頁的頁塊時，先檢查 128 個頁的頁塊鏈表是否有空閑塊。如果沒有，則查 256 個頁的頁塊鏈表；如果有空閑塊的話，則將 256 個頁的頁塊分成兩份，一份使用，一份插入 128 個頁的頁塊鏈表中。如果還是沒有，就查 512 個頁的頁塊鏈表；如果有的話，就分裂為 128、128、256 三個頁塊，一個 128 的使用，剩余兩個插入對應(yīng)頁塊鏈表。
伙伴分配器進(jìn)行頁分配的時候首先調(diào)用alloc_pages，alloc_pages 會調(diào)用 alloc_pages_current，alloc_pages_current會調(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)先級
#define?ALLOC_CPUSET??0x40?//檢查?cpuset?是否允許進(jìn)程從某個內(nèi)存節(jié)點(diǎn)分配頁
#define?ALLOC_CMA???0x80?//允許從CMA（連續(xù)內(nèi)存分配器）遷移類型分配

上面是alloc_pages的第一個參數(shù)分配標(biāo)志位，表示分配的允許情況，alloc_pages的第二個參數(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;
?...
?//快速路徑分配失敗，會調(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ū)域列表中每一個滿足條件的區(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;???????//那么不允許從這個區(qū)域分配，進(jìn)入下個循環(huán)
??
??if?(ac->spread_dirty_pages)?{//如果設(shè)置了寫標(biāo)志位，表示要分配寫緩存
???//那么要檢查內(nèi)存臟頁數(shù)量是否超出限制，超過限制就不能從這個區(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ū)域空閑頁-申請頁數(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)存頁”，然后檢查水線
???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ū)域分配頁
??page?=?rmqueue(ac->preferred_zoneref->zone,?zone,?order,
????gfp_mask,?alloc_flags,?ac->migratetype);
??if?(page)?{
???//分配成功，初始化頁
???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
????*/
???//如果這是一個高階的內(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;
}

每一個 zone，都有伙伴系統(tǒng)維護(hù)的各種大小的隊(duì)列，就像上面伙伴系統(tǒng)原理里講的那樣。這里調(diào)用 rmqueue 就很好理解了，就是找到合適大小的那個隊(duì)列，把頁面取下來。接下來的調(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 大小的頁塊。如果鏈表的第一個不為空，就找到了；如果為空，就到更大的 order 的頁塊鏈表里面去找。找到以后，除了將頁塊從鏈表中取下來，我們還要把多余部分放到其他頁塊鏈表里面。expand 就是干這個事情的。area–就是伙伴系統(tǒng)那個表里面的前一項(xiàng)，前一項(xiàng)里面的頁塊大小是當(dāng)前項(xiàng)的頁塊大小除以 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;
?//后面可能會檢查cpuset是否允許當(dāng)前進(jìn)程從哪些內(nèi)存節(jié)點(diǎn)申請頁
?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;
?
?//異步回收頁，喚醒kswapd內(nèi)核線程進(jìn)行頁面回收
?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后可能會立即申請成功，所以先嘗試一下
?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.
??*/
?//申請階數(shù)大于0，不可移動的位于高階的，忽略水位線的
?if?(can_direct_reclaim?&&
???(costly_order?||
??????(order?>?0?&&?ac->migratetype?!=?MIGRATE_MOVABLE))
???&&?!gfp_pfmemalloc_allowed(gfp_mask))?{
??//直接頁面回收，然后進(jìn)行頁面分配
??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?*/
?//如果頁回收線程意外睡眠則再次喚醒
?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?*/
?//如果不可以直接回收，則申請失敗
?if?(!can_direct_reclaim)
??goto?nopage;

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

?/*?Try?direct?reclaim?and?then?allocating?*/
?//直接頁面回收，然后進(jìn)行頁面分配
?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)行頁面壓縮，然后進(jìn)行頁面分配
?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
??*/
?//不要重試代價高昂的高階分配，除非它們是__GFP_RETRY_MAYFAIL
?if?(costly_order?&&?!(gfp_mask?&?__GFP_RETRY_MAYFAIL))
??goto?nopage;
?
?//重新嘗試回收頁
?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)
??*/
?//如果申請階數(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)申請就修改
?if?(check_retry_cpuset(cpuset_mems_cookie,?ac))
??goto?retry_cpuset;

?/*?Reclaim?has?failed?us,?start?killing?things?*/
?//使用oom選擇一個進(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)程，并且忽略了水線，則放棄申請
?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
???*/
??//允許它們訪問內(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;
}