一文搞定伙伴分配器

伙伴分配器

1.伙伴分配器原理

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

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

4.伙伴分配器的數據結構

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

6.伙伴分配器的結構

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

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

linux內存三大分配器：引導內存分配器，伙伴分配器，slab分配器

伙伴分配器

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

1.伙伴分配器原理

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

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

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

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

伙伴分配器分配和釋放物理頁的數量單位為階。分配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.伙伴分配器的數據結構

分區(qū)的伙伴分配器專注于某個內存節(jié)點的某個區(qū)域。內存區(qū)域的結構體成員free_area用來維護空閑頁塊，數組下標對應頁塊的階數。

內核源碼結構：

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

內核使用GFP_ZONE_TABLE 定義了區(qū)域類型映射表的標志組合，其中GFP_ZONES_SHIFT是區(qū)域類型占用的位數，GFP_ZONE_TABLE 把每種標志組合映射到32位整數的某個位置，偏移是（標志組合*區(qū)域類型位數），從這個偏移開始的GFP_ZONES_SHIFT個二進制存放區(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)
)
//根據flags標志獲取首選區(qū)域
#define?___GFP_DMA??0x01u
#define?___GFP_HIGHMEM??0x02u
#define?___GFP_DMA32??0x04u
#define?___GFP_MOVABLE??0x08u

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

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

6.伙伴分配器的結構

內核源碼如下：

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

?int?nr_zones;//該節(jié)點包含的內存區(qū)域數量
......
}
//struct?zone在linux內存管理（一）中
struct?zonelist?{
?struct?zoneref?_zonerefs[MAX_ZONES_PER_ZONELIST?+?1];
};
struct?zoneref?{
?struct?zone?*zone;//指向內存區(qū)域數據結構
?int?zone_idx;//成員zone指向內存區(qū)域的類型
};
enum?{
?ZONELIST_FALLBACK,//包含所有內存節(jié)點的的備用區(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,//只包含當前節(jié)點的備用區(qū)域列表（NUMA專用）
#endif
?MAX_ZONELISTS//表示備用區(qū)域列表數量
};

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

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

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

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

#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的數據結構：

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

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

可以通過/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.伙伴分配器分配過程分析

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

/*?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?//允許內存耗盡
#else
#define?ALLOC_OOM??ALLOC_NO_WATERMARKS//允許內存耗盡
#endif
#define?ALLOC_HARDER??0x10?//試圖更努力分配
#define?ALLOC_HIGH???0x20?//調用者是高優(yōu)先級
#define?ALLOC_CPUSET??0x40?//檢查?cpuset?是否允許進程從某個內存節(jié)點分配頁
#define?ALLOC_CMA???0x80?//允許從CMA（連續(xù)內存分配器）遷移類型分配

上面是alloc_pages的第一個參數分配標志位，表示分配的允許情況，alloc_pages的第二個參數表示分配的階數

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?*/?//快速路徑分配函數
?page?=?get_page_from_freelist(alloc_mask,?order,?alloc_flags,?&ac);
?if?(likely(page))
??goto?out;
?...
?//快速路徑分配失敗，會調用下面的慢速分配函數
?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;
}

從伙伴分配器的核心函數__alloc_pages_nodemask可以看到函數主要兩部分，一是執(zhí)行快速分配函數get_page_from_freelist，二是執(zhí)行慢速分配函數__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;

?//掃描備用區(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)?&&?//如果設置了ALLOC_CPUSET
???!__cpuset_zone_allowed(zone,?gfp_mask))?//如果cpu設置了不允許從當前區(qū)域分配內存
????continue;???????//那么不允許從這個區(qū)域分配，進入下個循環(huán)
??
??if?(ac->spread_dirty_pages)?{//如果設置了寫標志位，表示要分配寫緩存
???//那么要檢查內存臟頁數量是否超出限制，超過限制就不能從這個區(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ū)域空閑頁-申請頁數）是否小于水線
??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é)點回收功能或者當前節(jié)點和首選節(jié)點距離大于回收距離
???if?(node_reclaim_mode?==?0?||
???????!zone_allows_reclaim(ac->preferred_zoneref->zone,?zone))
????continue;

???//從節(jié)點回收“沒有映射到進程虛擬地址空間的內存頁”，然后檢查水線
???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://滿足上面的條件了，開始分配
??//從當前區(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
????*/
???//如果這是一個高階的內存并且是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)維護的各種大小的隊列，就像上面伙伴系統(tǒng)原理里講的那樣。這里調用 rmqueue 就很好理解了，就是找到合適大小的那個隊列，把頁面取下來。接下來的調用鏈是 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;

從當前的 order，也即指數開始，在伙伴系統(tǒng)的 free_area 找 2^order 大小的頁塊。如果鏈表的第一個不為空，就找到了；如果為空，就到更大的 order 的頁塊鏈表里面去找。找到以后，除了將頁塊從鏈表中取下來，我們還要把多余部分放到其他頁塊鏈表里面。expand 就是干這個事情的。area–就是伙伴系統(tǒng)那個表里面的前一項，前一項里面的頁塊大小是當前項的頁塊大小除以 2，size 右移一位也就是除以 2，list_add 就是加到鏈表上，nr_free++ 就是計數加 1。
然后看看慢速分配函數__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是否允許當前進程從哪些內存節(jié)點申請頁
?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.
??*/
?//把分配標志位轉化為內部的分配標志位
?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.
??*/
?//獲取首選的內存區(qū)域，因為在快速路徑中使用了不同的節(jié)點掩碼，避免再次遍歷不合格的區(qū)域。
?ac->preferred_zoneref?=?first_zones_zonelist(ac->zonelist,
?????ac->high_zoneidx,?ac->nodemask);
?if?(!ac->preferred_zoneref->zone)
??goto?nopage;
?
?//異步回收頁，喚醒kswapd內核線程進行頁面回收
?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
??*/
?//調整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.
??*/
?//申請階數大于0，不可移動的位于高階的，忽略水位線的
?if?(can_direct_reclaim?&&
???(costly_order?||
??????(order?>?0?&&?ac->migratetype?!=?MIGRATE_MOVABLE))
???&&?!gfp_pfmemalloc_allowed(gfp_mask))?{
??//直接頁面回收，然后進行頁面分配
??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);

?//如果調用者承若給我們緊急內存使用，我們就忽略水線
?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.
??*/
?//如果可以忽略內存策略，則重置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?*/
?//嘗試使用可能調整的區(qū)域備用列表和分配標志
?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?*/
?//直接頁面回收，然后進行頁面分配
?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?*/
?//進行頁面壓縮，然后進行頁面分配
?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?*/
?//如果調用者要求不要重試，則放棄
?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)
??*/
?//如果申請階數大于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允許修改內存節(jié)點申請就修改
?if?(check_retry_cpuset(cpuset_mems_cookie,?ac))
??goto?retry_cpuset;

?/*?Reclaim?has?failed?us,?start?killing?things?*/
?//使用oom選擇一個進程殺死
?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?*/
?//如果當前進程是oom選擇的進程，并且忽略了水線，則放棄申請
?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殺手正在取得進展，再試一次
?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
???*/
??//允許它們訪問內存?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;
}