在上篇文章 《深入理解 Linux 物理記憶體分配全鏈路實現》 中，筆者為大家詳細介紹了 Linux 記憶體分配在內核中的整個鏈路實現： 但是當內核執行到 get_page_from_freelist 函數，準備進入伙伴系統執行具體記憶體分配動作的相關邏輯，筆者考慮到文章篇幅的原因，並沒有過多的著墨，算是 ...
在上篇文章 《深入理解 Linux 物理記憶體分配全鏈路實現》 中，筆者為大家詳細介紹了 Linux 記憶體分配在內核中的整個鏈路實現：
但是當內核執行到 get_page_from_freelist 函數，準備進入伙伴系統執行具體記憶體分配動作的相關邏輯，筆者考慮到文章篇幅的原因，並沒有過多的著墨，算是留下了一個小尾巴。
那麼本文筆者就為大家完整地介紹一下伙伴系統這部分的內容，我們將基於內核 5.4 版本的源碼來詳細的討論一下伙伴系統在內核中的設計與實現。
1. 伙伴系統的核心數據結構
如上圖所示，內核會為 NUMA 節點中的每個物理記憶體區域 zone 分配一個伙伴系統用於管理該物理記憶體區域 zone 里的空閑記憶體頁。
而伙伴系統的核心數據結構就封裝在 struct zone 里，關於 struct zone 結構體的詳細介紹感興趣的朋友可以回看下筆者之前的文章 《深入理解 Linux 物理記憶體管理》中第五小節 “ 5. 內核如何管理 NUMA 節點中的物理記憶體區域 ” 的內容。
在本小節中，我們聚焦於伙伴系統相關的數據結構介紹~~
struct zone {
// 被伙伴系統所管理的物理記憶體頁個數
atomic_long_t managed_pages;
// 伙伴系統的核心數據結構
struct free_area free_area[MAX_ORDER];
}
struct zone 結構中的 managed_pages 用於表示該記憶體區域內被伙伴系統所管理的物理記憶體頁數量。
而 managed_pages 的計算方式之前也介紹過了，它是通過 present_pages （不包含記憶體空洞）減去內核為應對緊急情況而預留的物理記憶體頁 reserved_pages 得到的。
從這裡可以看出伙伴系統所管理的空閑物理記憶體頁並不包含緊急預留記憶體
伙伴系統的真正核心數據結構就是這個 struct free_area 類型的數組 free_area[MAX_ORDER] 。MAX_ORDER 就是筆者在《深入理解 Linux 物理記憶體分配全鏈路實現》 “ 的第一小節 "1. 內核物理記憶體分配介面 ” 中介紹的分配階 order 的最大值減 1。
伙伴系統所分配的物理記憶體頁全部都是物理上連續的，並且只能分配 2 的整數冪個頁，這裡的整數冪在內核中稱之為分配階 order。
在我們調用物理記憶體分配介面時，均需要指定這個分配階 order，意思是從伙伴系統申請多少個物理記憶體頁，假設我們指定分配階為 order，那麼就會從伙伴系統中申請 2 的 order 次冪個物理記憶體頁。
伙伴系統會將物理記憶體區域中的空閑記憶體根據分配階 order 劃分出不同尺寸的記憶體塊，並將這些不同尺寸的記憶體塊分別用一個雙向鏈表組織起來。
比如：分配階 order 為 0 時，對應的記憶體塊就是一個 page。分配階 order 為 1 時，對應的記憶體塊就是 2 個 pages。依次類推，當分配階 order 為 n 時，對應的記憶體塊就是 2 的 order 次冪個 pages。
MAX_ORDER - 1 就是內核中規定的分配階 order 的最大值，定義在 /include/linux/mmzone.h 文件中，最大分配階 MAX_ORDER - 1 = 10，也就是說一次，最多只能從伙伴系統中申請 1024 個記憶體頁，對應 4M 大小的連續物理記憶體。
/* Free memory management - zoned buddy allocator. */
#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
數組 free_area[MAX_ORDER] 中的索引表示的就是分配階 order，用於指定對應雙向鏈表組織管理的記憶體塊包含多少個 page。
我們可以通過 cat /proc/buddyinfo 命令來查看 NUMA 節點中不同記憶體區域 zone 的伙伴系統當前狀態：
上圖展示了不同記憶體區域伙伴系統的 free_area[MAX_ORDER] 數組中，不同分配階對應的記憶體塊個數，從左到右依次是 0 階，1 階， ........ ，10 階對應的雙向鏈表中包含的記憶體塊個數。
以上內容展示的只是伙伴系統的一個基本骨架，有了這個基本骨架之後，下麵筆者繼續按照一步一圖的方式，來為大家揭開伙伴系統的完整樣貌。
我們先從 free_area[MAX_ORDER] 數組的類型 struct free_area 結構開始談起~~~
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};
struct list_head {
// 雙向鏈表
struct list_head *next, *prev;
};
根據前邊的內容我們知道 free_area[MAX_ORDER] 數組描述的只是伙伴系統的一個基本骨架，數組中的每一個元素統一組織存儲了相同尺寸的記憶體塊。記憶體塊的尺寸分為 0 階，1 階 ，........ ，10 階，一共 MAX_ORDER 個尺寸。
struct free_area 主要描述的就是相同尺寸的記憶體塊在伙伴系統中的組織結構， nr_free 則表示的是該尺寸的記憶體塊在當前伙伴系統中的個數，這個值會隨著記憶體的分配而減少，隨著記憶體的回收而增加。
註意：nr_free 表示的可不是空閑記憶體頁 page 的個數，而是空閑記憶體塊的個數，對於 0 階的記憶體塊來說 nr_free 確實表示的是單個記憶體頁 page 的個數，因為 0 階記憶體塊是由一個 page 組成的，但是對於 1 階記憶體塊來說，nr_free 則表示的是 2 個 page 集合的個數，以此類推對於 n 階記憶體塊來說，nr_free 表示的是 2 的 n 次方 page 集合的個數
這些相同尺寸的記憶體塊在 struct free_area 結構中是通過 struct list_head 結構類型的雙向鏈表統一組織起來的。
按理來說，內核只需要將這些相同尺寸的記憶體塊在 struct free_area 中用一個雙向鏈表串聯起來就行了。
但是我們從源碼中卻看到內核是用多個雙向鏈表來組織這些相同尺寸的記憶體塊的，這些雙向鏈表組成一個數組 free_list[MIGRATE_TYPES]，該數組中雙向鏈表的個數為 MIGRATE_TYPES。
我們從 MIGRATE_TYPES 的字面意思上可以看出，內核會根據物理記憶體頁的遷移類型將這些相同尺寸的記憶體塊近一步通過不同的雙向鏈表重新組織起來。
free_area 是將相同尺寸的記憶體塊組織起來，free_list 是在 free_area 的基礎上近一步根據頁面的遷移類型將這些相同尺寸的記憶體塊劃分到不同的雙向鏈表中管理
而物理記憶體頁面的遷移類型 MIGRATE_TYPES 定義在 /include/linux/mmzone.h 文件中：
enum migratetype {
MIGRATE_UNMOVABLE, // 不可移動
MIGRATE_MOVABLE, // 可移動
MIGRATE_RECLAIMABLE, // 可回收
MIGRATE_PCPTYPES, // 屬於 CPU 高速緩存中的類型，PCP 是 per_cpu_pageset 的縮寫
MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES, // 緊急記憶體
#ifdef CONFIG_CMA
MIGRATE_CMA, // 預留的連續記憶體 CMA
#endif
#ifdef CONFIG_MEMORY_ISOLATION
MIGRATE_ISOLATE, /* can't allocate from here */
#endif
MIGRATE_TYPES // 不代表任何區域，只是單純表示一共有多少個遷移類型
};
MIGRATE_UNMOVABLE 表示不可移動的頁面類型，這種類型的物理記憶體頁面是固定的不能隨意移動，內核所需要的核心記憶體大多數是從 MIGRATE_UNMOVABLE 類型的頁面中進行分配，這部分記憶體一般位於內核虛擬地址空間中的直接映射區。
在內核虛擬地址空間的直接映射區中，虛擬記憶體地址與物理記憶體地址都是直接映射的，虛擬記憶體地址通過減去一個固定的偏移量就可以直接得到物理記憶體地址，由於這種直接映射的關係，所以這部分記憶體是不能移動的，因為一旦移動虛擬記憶體地址就會發生變化，這樣一來虛擬記憶體地址減去固定的偏移得到的物理記憶體地址就不一樣了。
MIGRATE_MOVABLE 表示可以移動的記憶體頁類型，這種頁面類型一般用於在進程用戶空間中分配，因為在用戶空間中虛擬記憶體與物理記憶體都是通過頁表來動態映射的，物理頁移動之後，只需要改變頁表中的映射關係即可，而虛擬記憶體地址並不需要改變。一切對進程來說都是透明的。
MIGRATE_RECLAIMABLE 表示不能移動，但是可以直接回收的頁面類型，比如前面提到的文件緩存頁，它們就可以直接被回收掉，當再次需要的時候可以從磁碟中繼續讀取生成。或者一些生命周期比較短的記憶體頁，比如 DMA 緩存區中的記憶體頁也是可以被直接回收掉。
MIGRATE_PCPTYPES 則表示 CPU 高速緩存中的頁面類型，PCP 是 per_cpu_pageset 的縮寫，每個 CPU 對應一個 per_cpu_pageset 結構，裡面包含了高速緩存中的冷頁和熱頁。這部分的詳細內容感興趣的可以回看下筆者的這篇文章 《深入理解 Linux 物理記憶體管理》中的 “ 5.7 物理記憶體區域中的冷熱頁 ” 小節。
MIGRATE_CMA 表示屬於 CMA 區域中的記憶體頁類型，CMA 的全稱是 contiguous memory allocator，顧名思義它是一個分配連續物理記憶體頁面的分配器用於分配連續的物理記憶體。
大家可能好奇了，我們這節講到的伙伴系統分配的不也是連續的物理記憶體嗎？為什麼又會多出個 CMA 呢？
原因還是前邊我們多次提到的記憶體碎片對記憶體分配的巨大影響，隨著系統的長時間運行，不可避免的會產生記憶體碎片，這些記憶體碎片會導致在記憶體充足的情況下卻依然找不到一片足夠大的連續物理記憶體，伙伴系統在這種情況下就會失敗，而連續的物理記憶體分配對於內核來說又是剛需，比如：一些 DMA 設備只能訪問連續的物理記憶體，內核對於大頁的支持也需要連續的物理記憶體。
所以為瞭解決這個問題，內核會在系統剛剛啟動的時候，這時記憶體還很充足，先預留一部分連續的物理記憶體，這部分物理記憶體就是 CMA 區域，這部分記憶體可以被進程正常的使用，當有連續記憶體分配需求時，內核會通過頁面回收或者遷移的方式將這部分記憶體騰出來給 CMA 分配。
CMA 的初始化是在伙伴系統初始化之前就已經完成的
MIGRATE_ISOLATE 則是一個虛擬區域，用於跨越 NUMA 節點移動物理記憶體頁，內核可以將物理記憶體頁移動到使用該頁最頻繁的 CPU 所在的 NUMA 節點中。
在介紹完這些物理頁面的遷移類型 MIGRATE_TYPES 之後，大家可能不禁有疑問，內核為啥會設定這麼多的頁面遷移類型呢 ？
答案還是為瞭解決前面我們反覆提到的記憶體碎片問題，當系統長時間運行之後，隨著不同尺寸記憶體的分配和釋放，就會引起記憶體碎片，這些碎片會導致內核在明明還有足夠記憶體的前提下，仍然無法找到一塊足夠大的連續記憶體分配。如下圖所示：
上圖中顯示的這 7 個空閑的記憶體頁以碎片的形式存在於記憶體中，這就導致明明還有 7 個空閑的記憶體頁，但是最大的連續記憶體區域只有 1 個記憶體頁，當內核想要申請 2 個連續的記憶體頁時就會導致失敗。
很長時間以來，物理記憶體碎片一直是 Linux 操作系統的弱點，所以內核在 2.6.24 版本中引入了以下方式來避免記憶體碎片。
如果這些記憶體頁是可以遷移的，內核就會將空閑的記憶體頁遷移至一起，已分配的記憶體頁遷移至一起，形成了一整塊足夠大的連續記憶體區域。
如果這些記憶體頁是可以回收的，內核也可以通過回收頁面的方式，整理出一塊足夠大的空閑連續記憶體區域。
在我們清楚了以上介紹的基礎知識之後，再回過頭來看伙伴系統的這些核心數據結構，是不是就變得容易理解了~~
struct zone {
// 被伙伴系統所管理的物理頁數
atomic_long_t managed_pages;
// 伙伴系統的核心數據結構
struct free_area free_area[MAX_ORDER];
}
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};
首先伙伴系統會將物理記憶體區域 zone 中的空閑記憶體頁按照分配階 order 將相同尺寸的記憶體塊組織在 free_area[MAX_ORDER] 數組中：
隨後在 struct free_area 結構中伙伴系統近一步根據這些相同尺寸記憶體塊的頁面遷移類型 MIGRATE_TYPES，將相同遷移類型的物理頁面組織在 free_list[MIGRATE_TYPES] 數組中，最終形成了完整的伙伴系統結構：
我們可以通過 cat /proc/pagetypeinfo 命令可以查看當前各個記憶體區域中的伙伴系統中不同頁面遷移類型以及不同 order 尺寸的記憶體塊個數。
page block order 表示系統中支持的巨型頁對應的分配階，pages per block 表示巨型頁中包含的 pages 個數。
好了，現在我們已經清楚了伙伴系統的數據結構全貌，接下來筆者會在這個基礎上繼續為大家介紹伙伴系統的核心工作原理~~
2. 到底什麼是伙伴
我們前面一直在談伙伴系統，那麼伙伴這個概念到底在內核中是什麼意思呢？其實下麵這張伙伴系統的結構圖已經把伙伴的概念很清晰的表達出來了。
伙伴在我們日常生活中含義就是形影不離的好朋友，在內核中也是如此，內核中的伙伴指的是大小相同並且在物理記憶體上是連續的兩個或者多個 page。
比如在上圖中，free_area[1] 中組織的是分配階 order = 1 的記憶體塊，記憶體塊中包含了兩個連續的空閑 page。這兩個空閑 page 就是伙伴。
free_area[10] 中組織的是分配階 order = 10 的記憶體塊，記憶體塊中包含了 1024 個連續的空閑 page。這 1024 個空閑 page 就是伙伴。
再比如上圖中的 page0 和 page 1 是伙伴，page2 到 page 5 是伙伴，page6 和 page7 又是伙伴。但是 page0 和 page2 就不能成為伙伴，因為它們的物理記憶體是不連續的。同時 (page0 到 page3) 和 (page4 到 page7) 所組成的兩個記憶體塊又能構成一個伙伴。伙伴必須是大小相同並且在物理記憶體上是連續的兩個或者多個 page。
3. 伙伴系統的記憶體分配原理
在 《深入理解 Linux 物理記憶體分配全鏈路實現》 一文中的第二小節 " 2. 物理記憶體分配內核源碼實現 "，筆者介紹瞭如下四個記憶體分配的介面，內核可以通過這些介面向伙伴系統申請記憶體：
struct page *alloc_pages(gfp_t gfp, unsigned int order)
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
unsigned long get_zeroed_page(gfp_t gfp_mask)
unsigned long __get_dma_pages(gfp_t gfp_mask, unsigned int order)
首先我們可以根據記憶體分配介面函數中的 gfp_t gfp_mask ，找到記憶體分配指定的 NUMA 節點和物理記憶體區域 zone ，然後找到物理記憶體區域 zone 對應的伙伴系統。
隨後內核通過介面中指定的分配階 order，可以定位到伙伴系統的 free_area[order] 數組，其中存放的就是分配階為 order 的全部記憶體塊。
最後內核進一步通過 gfp_t gfp_mask 掩碼中指定的頁面遷移類型 MIGRATE_TYPE，定位到 free_list[MIGRATE_TYPE]，這裡存放的就是符合記憶體分配要求的所有記憶體塊。通過遍歷這個雙向鏈表就可以輕鬆獲得要分配的記憶體。
比如我們向內核申請 ( 2 ^ (order - 1)，2 ^ order ] 之間大小的記憶體，並且這塊記憶體我們指定的遷移類型為 MIGRATE_MOVABLE 時，內核會按照 2 ^ order 個記憶體頁進行申請。
隨後內核會根據 order 找到伙伴系統中的 free_area[order] 對應的 free_area 結構，併進一步根據頁面遷移類型定位到對應的 free_list[MIGRATE_MOVABLE]，如果該遷移類型的 free_list 中沒有空閑的記憶體塊時，內核會進一步到上一級鏈表也就是 free_area[order + 1] 中尋找。
如果 free_area[order + 1] 中對應的 free_list[MIGRATE_MOVABLE] 鏈表中還是沒有，則繼續迴圈到更高一級 free_area[order + 2] 尋找，直到在 free_area[order + n] 中的 free_list[MIGRATE_MOVABLE] 鏈表中找到空閑的記憶體塊。
但是此時我們在 free_area[order + n] 鏈表中找到的空閑記憶體塊的尺寸是 2 ^ (order + n) 大小，而我們需要的是 2 ^ order 尺寸的記憶體塊，於是內核會將這 2 ^ (order + n) 大小的記憶體塊逐級減半分裂，將每一次分裂後的記憶體塊插入到相應的 free_area 數組裡對應的 free_list[MIGRATE_MOVABLE] 鏈表中，並將最後分裂出的 2 ^ order 尺寸的記憶體塊分配給進程使用。
下麵筆者舉一個具體的例子來為大家說明伙伴系統的整個記憶體分配過程：
為了清晰地給大家展現伙伴系統的記憶體分配過程，我們暫時忽略 MIGRATE_TYPES 相關的組織結構
我們假設當前伙伴系統中只有 order = 3 的空閑鏈表 free_area[3]，其餘剩下的分配階 order 對應的空閑鏈表中均是空的。 free_area[3] 中僅有一個空閑的記憶體塊，其中包含了連續的 8 個 page。
現在我們向伙伴系統申請一個 page 大小的記憶體（對應的分配階 order = 0），那麼內核會在伙伴系統中首先查看 order = 0 對應的空閑鏈表 free_area[0] 中是否有空閑記憶體塊可供分配。
隨後內核會根據前邊介紹的記憶體分配邏輯，繼續升級到 free_area[1] , free_area[2] 鏈表中尋找空閑記憶體塊，直到查找到 free_area[3] 發現有一個可供分配的記憶體塊。這個記憶體塊中包含了 8 個 連續的空閑 page，但是我們只要一個 page 就夠了，那該怎麼辦呢？
於是內核先將 free_area[3] 中的這個空閑記憶體塊從鏈表中摘下，然後減半分裂成兩個記憶體塊，分裂出來的這兩個記憶體塊分別包含 4 個 page（分配階 order = 2）。
上圖分裂出的兩個記憶體塊，黃色的代表原有記憶體塊的前半部分，綠色代表原有記憶體塊的後半部分。
隨後內核會將分裂出的後半部分（圖中綠色部分，order = 2），插入到 free_rea[2] 鏈表中。
前半部分（圖中黃色部分，order = 2）繼續減半分裂，分裂出來的這兩個記憶體塊分別包含 2 個 page（分配階 order = 1）。如下圖中第 4 步所示，前半部分為黃色，後半部分為紫色。同理按照前邊的分裂邏輯，內核會將後半部分記憶體塊（紫色部分，分配階 order = 1）插入到 free_area[1] 鏈表中。
前半部分（圖中黃色部分，order = 1）在上圖中的第 6 步繼續減半分裂，分裂出來的這兩個記憶體塊分別包含 1 個 page（分配階 order = 0），前半部分為青色，後半部分為黃色。
後半部分插入到 frea_area[0] 鏈表中，前半部分返回給進程，這時記憶體分配成功，流程結束。
以上流程就是伙伴系統的核心記憶體分配過程，下麵我們再把記憶體頁面的遷移屬性 MIGRATE_TYPES 考慮進來，來看一下完整的伙伴系統記憶體分配流程：
現在我們加上了記憶體 MIGRATE_TYPES 的組織結構，其實分配流程還是和核心流程一樣的，只不過上面提到的那些高階 order 的減半分裂情形都發生在各個 free_area[order] 中固定的 free_list[MIGRATE_TYPE] 里罷了。
比如我們要求分配的記憶體遷移屬性要求是 MIGRATE_MOVABLE 類型，那麼減半分裂流程分別發生在 free_area[2] ，free_area[1] ，free_area[0] 對應的 free_list[MIGRATE_MOVABLE] 中，多了一個 free_list 的維度，僅此而已。
不過筆者這裡想重點著墨的地方是記憶體分配的一種異常情形，比如我們想要分配特定遷移類型的記憶體，但是當前伙伴系統所有 free_area[order] 里對應的 free_list[MIGRATE_TYPE] 均無法滿足記憶體分配的需求（沒有足夠特定遷移類型的空閑記憶體塊）。那麼這種場景下內核會怎麼處理呢？
其實同樣的問題我們在 《深入理解 Linux 物理記憶體管理》 一文中也遇到過，當時筆者介紹記憶體 NUMA 架構的時候提到，如果當前 NUMA 節點無法滿足記憶體分配時，內核會跨越 NUMA 節點從其他節點上分配記憶體。
typedef struct pglist_data {
// NUMA 節點中的物理記憶體區域個數
int nr_zones;
// NUMA 節點中的物理記憶體區域
struct zone node_zones[MAX_NR_ZONES];
// NUMA 節點的備用列表
struct zonelist node_zonelists[MAX_ZONELISTS];
} pg_data_t;
每個 NUMA 節點的 struct pglist_data 結構中都會包含一個 node_zonelists，其中包含了當前NUMA 節點以及備用 NUMA 節點的所有記憶體區域以及對應的伙伴系統，當前 NUMA 節點記憶體不足時，內核會從 node_zonelists 中的備用 NUMA 節點中分配記憶體。
這裡也是同樣的道理，當伙伴系統中指定的遷移列表 free_list[MIGRATE_TYPE] 無法滿足記憶體分配需求時，內核根據不同遷移類型定義了不同的 fallback 規則：
/*
* This array describes the order lists are fallen back to when
* the free lists for the desirable migrate type are depleted
*
* The other migratetypes do not have fallbacks.
*/
static int fallbacks[MIGRATE_TYPES][3] = {
[MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_TYPES },
[MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_TYPES },
};
比如：MIGRATE_UNMOVABLE 類型的 free_list 記憶體不足時，內核會 fallback 到 MIGRATE_RECLAIMABLE 中去獲取，如果還是不足，則再次降級到 MIGRATE_MOVABLE 中獲取，如果仍然無法滿足記憶體分配，才會失敗退出。
正常的分配流程先是從低階到高階依次查找空閑記憶體塊，然後將高階中的記憶體塊依次減半分裂到低階 free_list 鏈表中。
記憶體分配 fallback 流程則剛好是相反的，它是先從備用 fallback 類型的遷移列表中的最高階開始查找，找到一塊空閑記憶體塊之後，先遷移到最初指定的 free_list[MIGRATE_TYPE] 鏈表中，然後在指定的 free_list[MIGRATE_TYPE] 鏈表執行減半分裂。
內核這裡的 fallback 策略是：如果無法避免分配遷移類型不同的記憶體塊，那麼就分配一個儘可能大的記憶體塊（從最高階開始查找），避免向其他鏈表引入記憶體碎片。
筆者還是以上邊的例子說明，當我們向伙伴系統申請 MIGRATE_UNMOVABLE 遷移類型的記憶體時，假設內核在伙伴系統中的 free_area[0] 到 free_area[10] 中的所有 free_list[MIGRATE_UNMOVABLE] 鏈表中均無法找到一個空閑的記憶體塊。
那麼就會 fallback 到 MIGRATE_RECLAIMABLE 類型，從最高階 free_area[10] 中的 free_list[MIGRATE_RECLAIMABLE] 鏈表開始查找，如果找到一個空閑的記憶體塊，則首先會遷移到對應的 order 的 free_list[MIGRATE_UNMOVABLE] 鏈表，然後流程繼續回到核心流程，在各個 free_area[order] 對應的 free_list[MIGRATE_UNMOVABLE] 鏈表中執行減半分裂。
這裡大家只需要理解一下 fallback 的大概流程，詳細內容筆者會在後面介紹伙伴系統實現的章節詳細解析~~~
4. 伙伴系統的記憶體回收原理
記憶體有分配就會有釋放，本小節我們就來看下如何將記憶體塊釋放回伙伴系統中。在上個小節中筆者為大家介紹了伙伴系統記憶體分配的完整流程，核心就是從高階 free_list 中尋找空閑記憶體塊，然後依次減半分裂。
伙伴系統中的記憶體回收剛好和記憶體分配的過程相反，核心則是從低階 free_list 中尋找釋放記憶體塊的伙伴，如果沒有伙伴則將要釋放的記憶體塊插入到對應分配階 order 的 free_list中。如果存在伙伴，則將釋放記憶體塊與它的伙伴合併，作為一個新的記憶體塊繼續到更高階的 free_list 中迴圈重覆上述過程，直到不能合併為止。
伙伴的概念我們已經在本文 《 2. 到底什麼是伙伴 》小節中介紹過了，核心就是兩個伙伴記憶體塊必須是大小相同並且在物理記憶體上是連續的。
下麵筆者還是舉一個具體的例子來為大家展現伙伴系統記憶體回收的過程：
為了清晰地給大家展現伙伴系統的記憶體回收過程，我們暫時忽略 MIGRATE_TYPES 相關的組織結構
假設當前伙伴系統的狀態如上圖所示，現在我們需要向伙伴系統釋放一個記憶體頁（order = 0），編號為10。
這裡筆者先來解釋下上圖伙伴系統中所管理的物理記憶體頁後邊編號的含義：我們知道伙伴系統中所管理的全部是連續的物理記憶體，既然是連續的，那麼每個記憶體頁 page 都會有一個固定的偏移（類似數組中的下標）。
這一點我們在前邊的文章 《深入理解 Linux 物理記憶體管理》的 “ 4.2 NUMA 節點描述符 pglist_data 結構 ” 小節中已經介紹過了，在每個 NUMA 節點中，內核通過一個 node_mem_map 數組來組織節點內的物理記憶體頁 page。
typedef struct pglist_data {
// NUMA 節點id
int node_id;
// 指向 NUMA 節點內管理所有物理頁 page 的數組
struct page *node_mem_map;
}
上圖伙伴系統中所管理的記憶體頁 page 只是被伙伴系統組織之後的視圖，下麵是物理記憶體頁在物理記憶體上的真實視圖（包含要被釋放的記憶體頁 10）：
有了這些基本概念之後，我回過頭來在看 page10 釋放回伙伴系統的整個過程：
下麵的流程需要大家時刻對比記憶體頁在物理記憶體上的真實視圖，不要被伙伴系統的組織視圖所干擾。
由於我們要釋放的記憶體塊只包含了一個物理記憶體頁 page10，所以它的分配階 order = 0，首先內核需要在伙伴系統 free_area[0] 中查找與 page10 大小相等並且連續的記憶體塊（伙伴）。
從物理記憶體的真實視圖中我們可以看到 page11 是 page10 的伙伴，於是將 page11 從 free_area[0] 上摘下並與 page10 合併組成一個新的記憶體塊（分配階 order = 1）。隨後內核會在 free_area[1] 中查找新記憶體塊的伙伴：
我們繼續對比物理記憶體頁的真實視圖，發現在 free_area[1] 中 page8 和 page9 組成的記憶體塊與 page10 和 page11 組成的記憶體塊是伙伴，於是繼續將這兩個記憶體塊（分配階 order = 1）繼續合併成一個新的記憶體塊（分配階 order = 2）。隨後內核會在 free_area[2] 中查找新記憶體塊的伙伴：
繼續對比物理記憶體頁的真實視圖，發現在 free_area[2] 中 page12，page13，page14，page15 組成的記憶體塊與 page8，page9，page10，page11 組成的新記憶體塊是伙伴，於是將它們從 free_area[2] 上摘下繼續合併成一個新的記憶體塊（分配階 order = 3），隨後內核會在 free_area[3] 中查找新記憶體塊的伙伴：
對比物理記憶體頁的真實視圖，我們發現在 free_area[3] 中的記憶體塊（page20 到 page 27）與新合併的記憶體塊（page8 到 page15）雖然大小相同但是物理上並不連續，所以它們不是伙伴，不能在繼續向上合併了。於是內核將 page8 到 pag15 組成的記憶體塊（分配階 order = 3）插入到 free_area[3] 中，至此記憶體釋放過程結束。
到這裡關於伙伴系統記憶體分配以及回收的核心原理筆者就為大家全部介紹完了，記憶體分配和釋放的過程剛好是相反的過程。
記憶體分配是從高階先查找到空閑記憶體塊，然後依次減半分裂，將分裂後的記憶體塊插入到低階的 free_list 中，將最後分裂出來的記憶體塊分配給進程。
記憶體釋放是先從低階開始查找釋放記憶體塊的伙伴，如果找到，則兩兩合併成一個新的記憶體塊，隨後繼續到高階中去查找新記憶體塊的伙伴，直到沒有伙伴可以合併。
一個是高階到低階分裂，一個是低階到高階合併。
5. 進入伙伴系統的前奏
現在我們已經清楚了伙伴系統的所有核心原理，但是乾講原理總覺得 talk is cheap，還是需要 show 一下 code，所以接下來筆者會帶大家看一下內核中伙伴系統的實現源碼，真刀真槍的來一下。
但真正進入伙伴系統之前，內核還是做了很多鋪墊工作，為了給大家解釋清楚這些內容，我們還是需要重新回到上篇文章 《深入理解 Linux 物理記憶體分配全鏈路實現》 “5. __alloc_pages 記憶體分配流程總覽” 小節中留下的尾巴，正式來介紹下 get_page_from_freelist 函數。
在上篇文章 “3. 物理記憶體分配內核源碼實現” 小節中，筆者為大家介紹了 Linux 物理記憶體分配的完整流程，我們知道物理記憶體分配總體上分為兩個路徑，內核首先嘗試的是在快速路徑下分配記憶體，如果不行的話，內核會走慢速路徑分配記憶體。
無論是快速路徑還是慢速路徑下的記憶體分配都需要最終調用 get_page_from_freelist 函數進行最終的記憶體分配。只不過，不同路徑下 get_page_from_freelist 函數的記憶體分配策略以及需要考慮的記憶體水位線會有所不同，其中慢速路徑下的記憶體分配策略會更加激進一些，這一點我們在上篇文章的相關章節內容介紹中體會很深。
在每次調用 get_page_from_freelist 函數之前，內核都會根據新的記憶體分配策略來重新初始化 struct alloc_context 結構，alloc_context 結構體中包含了記憶體分配所需要的所有核心參數。詳細初始化過程可以回看上篇文章的 “3.3 prepare_alloc_pages” 小節的內容。
struct alloc_context {
// 運行進程 CPU 所在 NUMA 節點以及其所有備用 NUMA 節點中允許記憶體分配的記憶體區域
struct zonelist *zonelist;
// NUMA 節點狀態掩碼
nodemask_t *nodemask;
// 記憶體分配優先順序最高的記憶體區域 zone
struct zoneref *preferred_zoneref;
// 物理記憶體頁的遷移類型分為：不可遷移，可回收，可遷移類型，防止記憶體碎片
int migratetype;
// 記憶體分配最高優先順序的記憶體區域 zone
enum zone_type highest_zoneidx;
// 是否允許當前 NUMA 節點中的臟頁均衡擴散遷移至其他 NUMA 節點
bool spread_dirty_pages;
};
這裡最核心的兩個參數就是 zonelist 和 preferred_zoneref。preferred_zoneref 表示當前本地 NUMA 節點（優先順序最高），其中 zonelist 我們在 《深入理解 Linux 物理記憶體管理》的 “ 4.3 NUMA 節點物理記憶體區域的劃分 ” 小節中詳細介紹過，zonelist 裡面包含了當前 NUMA 節點在內的所有備用 NUMA 節點的所有物理記憶體區域，用於當前 NUMA 節點沒有足夠空閑記憶體的情況下進行跨 NUMA 節點分配。
typedef struct pglist_data {
// NUMA 節點中的物理記憶體區域個數
int nr_zones;
// NUMA 節點中的物理記憶體區域
struct zone node_zones[MAX_NR_ZONES];
// NUMA 節點的備用列表
struct zonelist node_zonelists[MAX_ZONELISTS];
} pg_data_t;
struct pglist_data 里的 node_zonelists 是一個全集，而 struct alloc_context 里的 zonelist 是在記憶體分配過程中，根據指定的記憶體分配策略從全集 node_zonelists 過濾出來的一個子集（允許進行本次記憶體分配的所有 NUMA 節點及其記憶體區域）。
get_page_from_freelist 的核心邏輯其實很簡單，就是遍歷 struct alloc_context 里的 zonelist，挨個檢查各個 NUMA 節點中的物理記憶體區域是否有足夠的空閑記憶體可以滿足本次的記憶體分配要求，如果可以滿足則進入該物理記憶體區域的伙伴系統中完整真正的記憶體分配動作。
下麵我們先來看一下 get_page_from_freelist 函數的完整邏輯：
/*
* get_page_from_freelist goes through the zonelist trying to allocate
* a page.
*/
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;
// 當前遍歷到的記憶體區域 zone 引用
struct zone *zone;
// 最近遍歷的NUMA節點
struct pglist_data *last_pgdat = NULL;
// 最近遍歷的NUMA節點中包含的臟頁數量是否在內核限制範圍內
bool last_pgdat_dirty_ok = false;
// 如果需要避免記憶體碎片，則 no_fallback = true
bool no_fallback;
retry:
// 是否需要避免記憶體碎片
no_fallback = alloc_flags & ALLOC_NOFRAGMENT;
z = ac->preferred_zoneref;
// 開始遍歷 zonelist，查找可以滿足本次記憶體分配的物理記憶體區域 zone
for_next_zone_zonelist_nodemask(zone, z, ac->highest_zoneidx,
ac->nodemask) {
// 指向分配成功之後的記憶體
struct page *page;
// 記憶體分配過程中設定的水位線
unsigned long mark;
// 檢查記憶體區域所在 NUMA 節點是否在進程所允許的 CPU 上
if (cpusets_enabled() &&
(alloc_flags & ALLOC_CPUSET) &&
!__cpuset_zone_allowed(zone, gfp_mask))
continue;
// 每個 NUMA 節點中包含的臟頁數量都有一定的限制。
// 如果本次記憶體分配是為 page cache 分配的 page，用於寫入數據（不久就會變成臟頁）
// 這裡需要檢查當前 NUMA 節點的臟頁比例是否在限制範圍內允許的
// 如果沒有超過臟頁限制則可以進行分配，如果已經超過 last_pgdat_dirty_ok = false
if (ac->spread_dirty_pages) {
if (last_pgdat != zone->zone_pgdat) {
last_pgdat = zone->zone_pgdat;
last_pgdat_dirty_ok = node_dirty_ok(zone->zone_pgdat);
}
if (!last_pgdat_dirty_ok)
continue;
}
// 如果內核設置了避免記憶體碎片標識，在本地節點無法滿足記憶體分配的情況下(因為需要避免記憶體碎片)
// 這輪迴圈會遍歷 remote 節點（跨NUMA節點）
if (no_fallback && nr_online_nodes > 1 &&
zone != ac->preferred_zoneref->zone) {
int local_nid;
// 如果本地節點分配記憶體失敗是因為避免記憶體碎片的原因，那麼會繼續回到本地節點進行 retry 重試同時取消 ALLOC_NOFRAGMENT（允許引入碎片）
local_nid = zone_to_nid(ac->preferred_zoneref->zone);
if (zone_to_nid(zone) != local_nid) {
// 內核認為保證本地的局部性會比避免記憶體碎片更加重要
alloc_flags &= ~ALLOC_NOFRAGMENT;
goto retry;
}
}
// 獲取本次記憶體分配需要考慮到的記憶體水位線，快速路徑下是 WMARK_LOW, 慢速路徑下是 WMARK_MIN
mark = wmark_pages(zone, alloc_flags & ALLOC_WMARK_MASK);
// 檢查當前遍歷到的 zone 里剩餘的空閑記憶體容量是否在指定水位線 mark 之上
// 剩餘記憶體容量在水位線之下返回 false
if (!zone_watermark_fast(zone, order, mark,
ac->highest_zoneidx, alloc_flags,
gfp_mask)) {
int ret;
// 如果本次記憶體分配策略是忽略記憶體水位線，那麼就在本次遍歷到的zone里嘗試分配記憶體
if (alloc_flags & ALLOC_NO_WATERMARKS)
goto try_this_zone;
// 如果本次記憶體分配不能忽略記憶體水位線的限制，那麼就會判斷當前 zone 所屬 NUMA 節點是否允許進行記憶體回收
if (!node_reclaim_enabled() ||
!zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
// 不允許進行記憶體回收則繼續遍歷下一個 NUMA 節點的記憶體區域
continue;
// 針對當前 zone 所在 NUMA 節點進行記憶體回收
ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
switch (ret) {
case NODE_RECLAIM_NOSCAN:
// 返回該值表示當前 NUMA 節點沒有必要進行回收。比如快速分配路徑下就不處理頁面回收的問題
continue;
case NODE_RECLAIM_FULL:
// 返回該值表示通過掃描之後發現當前 NUMA 節點並沒有可以回收的記憶體頁
continue;
default:
// 該分支表示當前 NUMA 節點已經進行了記憶體回收操作
// zone_watermark_ok 判斷記憶體回收是否回收了足夠的記憶體能否滿足記憶體分配的需要
if (zone_watermark_ok(zone, order, mark,
ac->highest_zoneidx, alloc_flags))
goto try_this_zone;
continue;
}
}
try_this_zone:
// 這裡就是伙伴系統的入口，rmqueue 函數中封裝的就是伙伴系統的核心邏輯
// 從伙伴系統中獲取記憶體
page = rmqueue(ac->preferred_zoneref->zone, zone, order,
gfp_mask, alloc_flags, ac->migratetype);
if (page) {
// 分配記憶體成功，初始化記憶體頁 page
prep_new_page(page, order, gfp_mask, alloc_flags);
return page;
} else {
....... 省略 .....
}
}
// 記憶體分配失敗
return NULL;
}
與本文主題無關的非核心步驟大家通過筆者的註釋簡單瞭解即可，下麵我們只介紹與本文主題相關的核心步驟。
雖然 get_page_from_freelist 函數的代碼比較冗長，但是其核心邏輯比較簡單，主幹框架就是通過 for_next_zone_zonelist_nodemask 來遍歷當前 NUMA 節點以及備用節點的所有記憶體區域（zonelist），然後逐個通過 zone_watermark_fast 檢查這些記憶體區域 zone 中的剩餘空閑記憶體容量是否在指定的水位線 mark 之上。如果滿足水位線的要求則直接調用 rmqueue 進入伙伴系統分配記憶體，分配成功之後通過 prep_new_page 初始化分配好的記憶體頁 page。
如果當前正在遍歷的 zone 中剩餘空閑記憶體容量在指定的水位線 mark 之下，就需要通過 node_reclaim 觸發記憶體回收，隨後通過 zone_watermark_ok 檢查經過記憶體回收之後，內核是否回收到了足夠的記憶體以滿足本次記憶體分配的需要。如果記憶體回收到了足夠的記憶體則 zone_watermark_ok = true 隨後跳轉到 try_this_zone 分支在本記憶體區域 zone 中分配記憶體。否則繼續遍歷下一個 zone。
5.1 獲取記憶體區域 zone 里指定的記憶體水位線
get_page_from_freelist 函數中的記憶體分配邏輯是要考慮記憶體水位線的，滿足記憶體分配要求的物理記憶體區域 zone 中的剩餘空閑記憶體容量必須在指定記憶體水位線之上。否則內核則認為記憶體不足不能進行記憶體分配。
在上篇文章 《深入理解 Linux 物理記憶體分配全鏈路實現》 中的 “3.2 記憶體分配的心臟 __alloc_pages” 小節的介紹中，我們知道在快速路徑下，記憶體分配策略中的水位線設置為 WMARK_LOW：
// 記憶體區域中的剩餘記憶體需要在 WMARK_LOW 水位線之上才能進行記憶體分配，否則失敗（初次嘗試快速記憶體分配）
unsigned int alloc_flags = ALLOC_WMARK_LOW;
在上篇文章 “4. 記憶體慢速分配入口 alloc_pages_slowpath” 小節的介紹中，我們知道在慢速路徑下，記憶體分配策略中的水位線又被調整為了 WMARK_MIN：
// 在慢速記憶體分配路徑中，會進一步放寬對記憶體分配的限制，將記憶體分配水位線調低到 WMARK_MIN
// 也就是說記憶體區域中的剩餘記憶體需要在 WMARK_MIN 水位線之上就可以進行記憶體分配了
unsigned int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;
如果記憶體分配仍然失敗，則內核會將記憶體分配策略中的水位線調整為 ALLOC_NO_WATERMARKS，表示再記憶體分配時，可以忽略水位線的限制，再一次進行重試。
不同的記憶體水位線會影響到記憶體分配邏輯，所以在通過 for_next_zone_zonelist_nodemask 遍歷 NUMA 節點中的物理記憶體區域的一開始就需要獲取該記憶體區域指定水位線的具體數值，內核通過 wmark_pages 巨集來獲取：
#define wmark_pages(z, i) (z->_watermark[i] + z->watermark_boost)
struct zone {
// 物理記憶體區域中的水位線
unsigned long _watermark[NR_WMARK];
// 優化記憶體碎片對記憶體分配的影響，可以動態改變記憶體區域的基準水位線。
unsigned long watermark_boost;
}
關於記憶體區域 zone 中水位線的相關內容介紹，大家可以回看下筆者之前的文章 《深入理解 Linux 物理記憶體管理》 中 “ 5.2 物理記憶體區域中的水位線 ” 小節。
5.2 檢查 zone 中剩餘記憶體容量是否滿足水位線要求
在我們通過 wmark_pages 獲取到當前記憶體區域 zone 的指定水位線 mark 之後，我們就需要近一步判斷當前 zone 中剩餘的空閑記憶體容量是否在水位線 mark 之上，這是保證記憶體分配順利進行的必要條件。
內核中判斷水位線的邏輯封裝在 zone_watermark_fast 和 __zone_watermark_ok 函數中，其中核心邏輯在 __zone_watermark_ok 里，zone_watermark_fast 只是用來快速檢測分配階 order = 0 情況下的相關水位線情況。
下麵我們先來看下 zone_watermark_fast 的邏輯：
static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
unsigned long mark, int highest_zoneidx,
unsigned int alloc_flags, gfp_t gfp_mask)
{
long free_pages;
// 獲取當前記憶體區域中所有空閑的物理記憶體頁
free_pages = zone_page_state(z, NR_FREE_PAGES);
// 快速檢查分配階 order = 0 情況下相關水位線，空閑記憶體需要刨除掉為 highatomic 預留的緊急記憶體
if (!order) {
long usable_free;
long reserved;
// 可供本次記憶體分配使用的符合要求的真實可用記憶體，初始為 free_pages
// free_pages 為空閑記憶體頁的全集其中也包括了不能為本次記憶體分配提供記憶體的空閑記憶體
usable_free = free_pages;
// 獲取本次不能使用的空閑記憶體頁數量
reserved = __zone_watermark_unusable_free(z, 0, alloc_flags);
// 計算真正可供記憶體分配的空閑頁數量：空閑記憶體頁全集 - 不能使用的空閑頁
usable_free -= min(usable_free, reserved);
// 如果可用的空閑記憶體頁數量大於記憶體水位線與預留記憶體之和
// 那麼表示物理記憶體區域中的可用空閑記憶體能夠滿足本次記憶體分配的需要
if (usable_free > mark + z->lowmem_reserve[highest_zoneidx])
return true;
}
// 近一步檢查記憶體區域伙伴系統中是否有足夠的 order 階的記憶體塊可供分配
if (__zone_watermark_ok(z, order, mark, highest_zoneidx, alloc_flags,
free_pages))
return true;
........ 省略無關代碼 .......
// 水位線檢查失敗
return false;
}
首先會通過 zone_page_state 來獲取當前 zone 中剩餘空閑記憶體頁的總體容量 free_pages。
筆者在 《深入理解 Linux 物理記憶體管理》的 “ 5. 內核如何管理 NUMA 節點中的物理記憶體區域 ” 小節中為大家介紹 struct zone 結構體的時候提過，每個記憶體區域 zone 里有一個 vm_stat 用來存放與 zone 相關的各種統計變數。
struct zone {
// 該記憶體區域記憶體使用的統計信息
atomic_long_t vm_stat[NR_VM_ZONE_STAT_ITEMS];
}
內核可以通過 zone_page_state 來訪問 vm_stat 從而獲取對應的統計量，free_pages 就是其中的一個統計變數。但是這裡大家需要註意的是 free_pages 表示的當前 zone 里剩餘空閑記憶體頁的一個總量，是一個全集的概念。其中還包括了記憶體區域的預留記憶體 lowmem_reserve 以及為 highatomic 預留的緊急記憶體。這些預留記憶體都有自己特定的用途，普通記憶體的申請不會用到預留記憶體。
流程如果進入到 if (!order) 分支的話表示本次記憶體分配只是申請一個（order = 0）空閑的記憶體頁，在這裡會快速的檢測相關水位線情況是否滿足，如果滿足就會快速返回。
這裡涉及到兩個重要的局部變數，筆者需要向大家交代一下：
-
usable_free：表示可供本次記憶體分配使用的空閑記憶體頁總量。前邊我們提到 free_pages 表示的是剩餘空閑記憶體頁的一個全集，裡邊還包括很多不能進行普通記憶體分配的空閑記憶體頁，比如預留記憶體和緊急記憶體。
-
reserved：表示本次記憶體分配不能使用到的空閑記憶體頁數量，這一部分的記憶體頁數量計算是通過 __zone_watermark_unusable_free 函數完成的。最後使用 free_pages 減去 reserved 就可以得到真正的 usable_free 。
static inline long __zone_watermark_unusable_free(struct zone *z,
unsigned int order, unsigned int alloc_flags)
{
// ALLOC_HARDER 的設置表示可以使用 high-atomic 緊急預留記憶體
const bool alloc_harder = (alloc_flags & (ALLOC_HARDER|ALLOC_OOM));
long unusable_free = (1 << order) - 1;
// 如果沒有設置 ALLOC_HARDER 則不能使用 high_atomic 緊急預留記憶體
if (likely(!alloc_harder))
// 不可用記憶體的數量需要統計上 high-atomic 這部分記憶體
unusable_free += z->nr_reserved_highatomic;
#ifdef CONFIG_CMA
// 如果沒有設置 ALLOC_CMA 則表示本次記憶體分配不能從 CMA 區域獲取
if (!(alloc_flags & ALLOC_CMA))
// 不可用記憶體的數量需要統計上 CMA 區域中的空閑記憶體頁
unusable_free += zone_page_state(z, NR_FREE_CMA_PAGES);
#endif
// 返回不可用記憶體的數量，表示本次記憶體分配不能使用的記憶體容量
return unusable_free;
}
如果 usable_free > mark + z->lowmem_reserve[highest_zoneidx] 條件為 true 表示當前可用剩餘記憶體頁容量在水位線 mark 之上，可以進行記憶體分配，返回 true。
我們在 《深入理解 Linux 物理記憶體管理》的 " 5.2 物理記憶體區域中的水位線 " 小節中介紹水位線相關的計算邏輯的時候提過，水位線的計算是需要刨去 lowmem_reserve 預留記憶體的，也就是水位線的值並不包含 lowmem_reserve 記憶體在內。
所以這裡在判斷可用記憶體是否滿足水位線的關係時需要加上這部分 lowmem_reserve ，才能得到正確的結果。
如果本次記憶體分配申請的是高階記憶體塊（ order > 0），則會進入 __zone_watermark_ok 函數中，近一步判斷伙伴系統中是否有足夠的高階記憶體塊能夠滿足 order 階的記憶體分配：
bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
int highest_zoneidx, unsigned int alloc_flags,
long free_pages)
{
// 保證記憶體分配順利進行的最低水位線
long min = mark;
int o;
const bool alloc_harder = (alloc_flags & (ALLOC_HARDER|ALLOC_OOM));
// 獲取真正可用的剩餘空閑記憶體頁數量
free_pages -= __zone_watermark_unusable_free(z, order, alloc_flags);
// 如果設置了 ALLOC_HIGH 則水位線降低二分之一，使記憶體分配更加努力激進一些
if (alloc_flags & ALLOC_HIGH)
min -= min / 2;
if (unlikely(alloc_harder)) {
// 在要進行 OOM 的情況下記憶體分配會比普通的 ALLOC_HARDER 策略更加努力激進一些，所以這裡水位線會降低二分之一
if (alloc_flags & ALLOC_OOM)
min -= min / 2;
else
// ALLOC_HARDER 策略下水位線只會降低四分之一
min -= min / 4;
}
// 檢查當前可用剩餘記憶體是否在指定水位線之上。
// 記憶體的分配必須保證可用剩餘記憶體容量在指定水位線之上，否則不能進行記憶體分配
if (free_pages <= min + z->lowmem_reserve[highest_zoneidx])
return false;
// 流程走到這裡，對應記憶體分配階 order = 0 的情況下就已經 OK 了
// 剩餘空閑記憶體在水位線之上，那麼肯定能夠分配一頁出來
if (!order)
return true;
// 但是對於 high-order 的記憶體分配，這裡還需要近一步檢查伙伴系統
// 根據伙伴系統記憶體分配的原理，這裡需要檢查高階 free_list 中是否有足夠的空閑記憶體塊可供分配
for (o = order; o < MAX_ORDER; o++) {
// 從當前分配階 order 對應的 free_area 中檢查是否有足夠的記憶體塊
struct free_area *area = &z->free_area[o];
int mt;
// 如果當前 free_area 中的 nr_free = 0 表示對應 free_list 中沒有合適的空閑記憶體塊
// 那麼繼續到高階 free_area 中查找
if (!area->nr_free)
continue;
// 檢查 free_area 中所有的遷移類型 free_list 是否有足夠的記憶體塊
for (mt = 0; mt < MIGRATE_PCPTYPES; mt++) {
if (!free_area_empty(area, mt))
return true;
}
#ifdef CONFIG_CMA
// 如果記憶體分配指定需要從 CMA 區域中分配連續記憶體
// 那麼就需要檢查 MIGRATE_CMA 對應的 free_list 是否是空
if ((alloc_flags & ALLOC_CMA) &&
!free_area_empty(area, MIGRATE_CMA)) {
return true;
}
#endif
// 如果設置了 ALLOC_HARDER，則表示可以從 HIGHATOMIC 區中的緊急預留記憶體中分配，檢查對應 free_list
if (alloc_harder && !free_area_empty(area, MIGRATE_HIGHATOMIC))
return true;
}
// 伙伴系統中的剩餘記憶體塊無法滿足 order 階的記憶體分配
return false;
}
在 __zone_watermark_ok 函數的開始需要計算出真正可用的剩餘記憶體 free_pages 。
// 獲取真正可用的剩餘空閑記憶體頁數量
free_pages -= __zone_watermark_unusable_free(z, order, alloc_flags);
緊接著內核會根據 ALLOC_HIGH 以及 ALLOC_HARDER 標識來決定是否降低水位線的要求。在 《深入理解 Linux 物理記憶體分配全鏈路實現》 一文中的 “3.1 記憶體分配行為標識掩碼 ALLOC_* ” 小節中筆者曾詳細的為大家介紹過這些 ALLOC_* 相關的掩碼，當時筆者提了一句，當記憶體分配策略設置為 ALLOC_HIGH 或者 ALLOC_HARDER 時，會使記憶體分配更加的激進，努力一些。
當時大家可能會比較懵，怎樣才算是激進？怎樣才算是努力呢？
其實答案就在這裡，當記憶體分配策略 alloc_flags 設置了 ALLOC_HARDER 時，水位線的要求會降低原來的四分之一，相當於放款了記憶體分配的限制。比原來更加努力使記憶體分配成功。
當記憶體分配策略 alloc_flags 設置了 ALLOC_HIGH 時，水位線的要求會降低原來的二分之一，相當於更近一步放款了記憶體分配的限制。比原來更加激進些。
在調整完水位線之後，還是一樣的邏輯，需要判斷當前可用剩餘記憶體容量是否在水位線之上，如果是，則水位線檢查完畢符合記憶體分配的要求。如果不是，則返回 false 不能進行記憶體分配。
// 記憶體的分配必須保證可用剩餘記憶體容量在指定水位線之上，否則不能進行記憶體分配
free_pages <= min + z->lowmem_reserve[highest_zoneidx])
在水位線 OK 之後，對於 order = 0 的記憶體分配情形下，就已經 OK 了，可以放心直接進行記憶體分配了。
但是對於 high-order 的記憶體分配情形，這裡還需要近一步檢查伙伴系統是否有足夠的空閑記憶體塊可以滿足本次 high-order 的記憶體分配。
根據本文 《3. 伙伴系統的記憶體分配原理》小節中，為大家介紹的伙伴系統記憶體分配原理，內核需要從當前分配階 order 開始一直向高階 free_area 中查找對應的 free_list 中是否有足夠的記憶體塊滿足 order 階的記憶體分配要求。
-
如果有，那麼水位線相關的校驗工作到此結束，內核會直接去伙伴系統中申請 order 階的記憶體塊。
-
如果沒有，則水位線校驗失敗，伙伴系統無法滿足本次的記憶體分配要求。
5.3 記憶體分配成功之後初始化 page
經過 zone_watermark_ok 的校驗，現在記憶體水位線符合記憶體分配的要求，並且伙伴系統中有足夠的空閑記憶體塊可供記憶體分配申請，現在可以放心調用 rmqueue 函數進入伙伴系統進行記憶體分配了。
rmqueue 函數封裝的正是伙伴系統的核心邏輯，這一部分的源碼實現筆者放在下一小節中介紹，這裡我們先關註記憶體分配成功之後，對於記憶體頁 page 的初始化邏輯。
當通過 rmqueue 函數從伙伴系統中成功申請到分配階為 order 大小的記憶體塊時，內核需要調用 prep_new_page 函數初始化這部分記憶體塊，之後才能返回給進程使用。
static void prep_new_page(struct page *page, unsigned in
