在上篇文章 《深入理解 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 int order, gfp_t gfp_flags,
unsigned int alloc_flags)
{
// 初始化 struct page，清除一些頁面屬性標記
post_alloc_hook(page, order, gfp_flags);
// 設定復合頁
if (order && (gfp_flags & __GFP_COMP))
prep_compound_page(page, order);
if (alloc_flags & ALLOC_NO_WATERMARKS)
// 使用 set_page_XXX(page) 方法設定 page 的 PG_XXX 標志位
set_page_pfmemalloc(page);
else
// 使用 clear_page_XXX(page) 方法清除 page 的 PG_XXX 標志位
clear_page_pfmemalloc(page);
}
5.3.1 初始化 struct page
由于現在我們拿到的 struct page 結構是剛剛從伙伴系統中申請出來的，里面可能包含一些無用的標記（上一次被使用過的，還沒清理），所以需要將這些無用標記清理掉，并且在此基礎上根據 gfp_flags 掩碼對 struct page 進行初始化的準備作業，
比如通過 set_page_private 將 struct page 里的 private 指標所指向的內容清空，private 指標在內核中的使用比較復雜，它會在不同場景下指向不同的內容，
set_page_private(page, 0);
將頁面的使用計數設定為 1 ，表示當前物理記憶體頁正在被使用，
set_page_refcounted(page);
如果 gfp_flags 掩碼中設定了 ___GFP_ZERO，這時就需要將這些 page 初始化為零頁，
由于初始化頁面的準備作業和本文的主線內容并沒有多大的關聯，所以筆者這里只做簡單介紹，大家大概了解一下初始化做了哪些準備作業即可，
5.3.2 設定復合頁 compound_page
復合頁 compound_page 本質上就是通過兩個或者多個物理上連續的記憶體頁 page 組裝成的一個在邏輯上看起來比普通記憶體頁 page 更大的頁，它底層的依賴本質還是一個一個的普通記憶體頁 page，
我們都知道 Linux 管理記憶體的最小單位是 page，每個 page 描述 4K 大小的物理記憶體，但在一些內核使用場景中，比如 slab 記憶體池中，往往會向伙伴系統一次性申請多個普通記憶體頁 page，然后將這些記憶體頁 page 劃分為多個大小相同的小記憶體塊，這些小記憶體塊被 slab 記憶體池統一管理，
slab 記憶體池底層其實依賴的是多個普通記憶體頁，但是內核期望將這多個記憶體頁統一成一個邏輯上的記憶體頁來統一管理，這個邏輯上的記憶體頁就是本小節要介紹的復合頁，
而在 Linux 記憶體管理的架構中都是統一通過 struct page 來管理記憶體，復合頁卻是通過兩個或者多個物理上連續的記憶體頁 page 組裝成的一個邏輯頁，那么復合頁的管理與普通頁的管理如何統一呢？
這就引出了本小節的主題——復合頁 compound_page，下面我們就來看下 Linux 如果通過統一的 struct page 結構來描述這些復合頁（compound_page）：
雖然復合頁（compound_page）是由多個物理上連續的普通 page 組成的，但是在內核的視角里它還是被當做一個特殊記憶體頁來看待，
下圖所示，是由 4 個連續的普通記憶體頁 page 組成的一個 compound_page：
組成復合頁的第一個 page 我們稱之為首頁（Head Page），其余的均稱之為尾頁（Tail Page），
我們來看一下 struct page 中關于描述 compound_page 的相關欄位：
struct page {
// 首頁 page 中的 flags 會被設定為 PG_head 表示復合頁的第一頁
unsigned long flags;
// 其余尾頁會通過該欄位指向首頁
unsigned long compound_head;
// 用于釋放復合頁的解構式，保存在首頁中
unsigned char compound_dtor;
// 該復合頁有多少個 page 組成，order 還是分配階的概念，在首頁中保存
// 本例中的 order = 2 表示由 4 個普通頁組成
unsigned char compound_order;
// 該復合頁被多少個行程使用，記憶體頁反向映射的概念，首頁中保存
atomic_t compound_mapcount;
// 復合頁使用計數，首頁中保存
atomic_t compound_pincount;
}
首頁對應的 struct page 結構里的 flags 會被設定為 PG_head，表示這是復合頁的第一頁，
另外首頁中還保存關于復合頁的一些額外資訊，比如：
- 用于釋放復合頁的解構式會保存在首頁 struct page 結構里的 compound_dtor 欄位中
- 復合頁的分配階 order 會保存在首頁中的 compound_order 中以及用于指示復合頁的參考計數 compound_pincount，以及復合頁的反向映射個數（該復合頁被多少個行程的頁表所映射）compound_mapcount 均在首頁中保存，
關于 struct page 的 flags 欄位的介紹，以及記憶體頁反向映射原理，大家可以回看下筆者 《深入理解 Linux 物理記憶體管理》中的 “ 6.4 物理記憶體頁屬性和狀態的標志位 flag ” 和 “ 6.1 匿名頁的反向映射 ” 小節，
復合頁中的所有尾頁都會通過其對應的 struct page 結構中的 compound_head 指向首頁，這樣通過首頁和尾頁就組裝成了一個完整的復合頁 compound_page ，
在我們理解了 compound_page 的組織結構之后，我們在回過頭來看 "6.3 記憶體分配成功之后初始化 page" 小節中的 prep_new_page 函式：
當內核向伙伴系統申請復合頁 compound_page 的時候，會在 gfp_flags 掩碼中設定 __GFP_COMP 標識，表次本次記憶體分配要分配一個復合頁，復合頁中的 page 個數由分配階 order 決定，
當內核向伙伴系統申請了 2 ^ order 個記憶體頁 page 時，大家注意在伙伴系統的視角中記憶體還是一頁一頁的，伙伴系統并不知道有復合頁的存在，當我們申請成功之后，需要在 prep_new_page 函式中將這 2 ^ order 個記憶體頁 page 按照前面介紹的邏輯組裝成一個 復合頁 compound_page，
void prep_compound_page(struct page *page, unsigned int order)
{
int i;
int nr_pages = 1 << order;
// 設定首頁 page 中的 flags 為 PG_head
__SetPageHead(page);
// 首頁之后的 page 全部是尾頁，回圈遍歷設定尾頁
for (i = 1; i < nr_pages; i++)
prep_compound_tail(page, i);
// 最后設定首頁相關屬性
prep_compound_head(page, order);
}
static void prep_compound_tail(struct page *head, int tail_idx)
{
// 由于復合頁中的 page 全部是連續的，直接使用偏移即可獲得對應尾頁
struct page *p = head + tail_idx;
// 設定尾頁標識
p->mapping = TAIL_MAPPING;
// 尾頁 page 結構中的 compound_head 指向首頁
set_compound_head(p, head);
}
static __always_inline void set_compound_head(struct page *page, struct page *head)
{
WRITE_ONCE(page->compound_head, (unsigned long)head + 1);
}
static void prep_compound_head(struct page *page, unsigned int order)
{
// 設定首頁相關屬性
set_compound_page_dtor(page, COMPOUND_PAGE_DTOR);
set_compound_order(page, order);
atomic_set(compound_mapcount_ptr(page), -1);
atomic_set(compound_pincount_ptr(page), 0);
}
6. 伙伴系統的實作
現在內核通過前邊介紹的 get_page_from_freelist 函式，回圈遍歷 zonelist 終于找到了符合記憶體分配條件的物理記憶體區域 zone，接下來就會通過 rmqueue 函式進入到該物理記憶體區域 zone 對應的伙伴系統中實際分配物理記憶體，
/*
* Allocate a page from the given zone. Use pcplists for order-0 allocations.
*/
static inline
struct page *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;
if (likely(order == 0)) {
// 當我們申請一個物理頁面（order = 0）時，內核首先會從 CPU 高速快取串列 pcplist 中直接分配，而不會走伙伴系統，提高記憶體分配速度
page = rmqueue_pcplist(preferred_zone, zone, gfp_flags,
migratetype, alloc_flags);
goto out;
}
// 加鎖并關閉中斷，防止并發訪問
spin_lock_irqsave(&zone->lock, flags);
// 當申請頁面超過一個 （order > 0）時，則從伙伴系統中進行分配
do {
page = NULL;
if (alloc_flags & ALLOC_HARDER) {
// 如果設定了 ALLOC_HARDER 分配策略，則從伙伴系統的 HIGHATOMIC 遷移型別的 freelist 中獲取
page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
}
if (!page)
// 從伙伴系統中申請分配階 order 大小的物理記憶體塊
page = __rmqueue(zone, order, migratetype, alloc_flags);
} while (page && check_new_pages(page, order));
// 解鎖
spin_unlock(&zone->lock);
if (!page)
goto failed;
// 重新統計記憶體區域中的相關統計指標
zone_statistics(preferred_zone, zone);
// 打開中斷
local_irq_restore(flags);
out:
return page;
failed:
// 分配失敗
local_irq_restore(flags);
return NULL;
}
6.1 從 CPU 高速快取串列中獲取記憶體頁
內核對只分配一頁物理記憶體的情況做了特殊處理，當只請求一頁記憶體時，內核會借助 CPU 高速快取冷熱頁串列 pcplist 加速記憶體分配的處理，此時分配的記憶體頁將來自于 pcplist 而不是伙伴系統，
pcp 是 per_cpu_pageset 的縮寫，內核會為每個 CPU 分配一個高速快取串列，關于這部分內容，筆者已經在 《深入理解 Linux 物理記憶體管理》一文中的 “ 5.7 物理記憶體區域中的冷熱頁 ” 小節非常詳細的為大家介紹過了，忘記的同學可以在回看下，
在 NUMA 記憶體架構下，每個物理記憶體區域都歸屬于一個特定的 NUMA 節點，NUMA 節點中包含了一個或者多個 CPU，NUMA 節點中的每個記憶體區域會關聯到一個特定的 CPU 上.
而每個 CPU 都有自己獨立的高速快取，所以每個 CPU 對應一個 per_cpu_pageset 結構，用于管理這個 CPU 高速快取中的冷熱頁，
所謂的熱頁就是已經加載進 CPU 高速快取中的物理記憶體頁，所謂的冷頁就是還未加載進 CPU 高速快取中的物理記憶體頁，冷頁是熱頁的后備選項
每個 CPU 都可以訪問系統中的所有物理記憶體頁，盡管訪問速度不同，因此特定的物理記憶體區域 struct zone 不僅要考慮到所屬 NUMA 節點中相關的 CPU，還需要照顧到系統中的其他 CPU，
在 Linux 內核中，系統會經常請求和釋放單個頁面，如果針對每個 CPU，都為其預先分配一個用于快取單個記憶體頁面的高速快取頁串列，用于滿足本地 CPU 發出的單頁記憶體請求，就能提升系統的性能，所以在 struct zone 結構中持有了系統中所有 CPU 的高速快取頁串列 per_cpu_pageset，
struct zone {
struct per_cpu_pages __percpu *per_cpu_pageset;
}
struct per_cpu_pages {
int count; /* pcplist 里的頁面總數 */
int high; /* pcplist 里的高水位線，count 超過 high 時，內核會釋放 batch 個頁面到伙伴系統中*/
int batch; /* pcplist 里的頁面來自于伙伴系統，batch 定義了每次從伙伴系統獲取或者歸還多少個頁面*/
// CPU 高速快取串列 pcplist，每個遷移型別對應一個 pcplist
struct list_head lists[NR_PCP_LISTS];
};
當內核嘗試從 pcplist 中獲取一個物理記憶體頁時，會首先獲取運行當前行程的 CPU 對應的高速快取串列 pcplist，然后根據指定的具體頁面遷移型別 migratetype 獲取對應遷移型別的 pcplist，
當獲取到符合條件的 pcplist 之后，內核會呼叫 __rmqueue_pcplist 從 pcplist 中摘下一個物理記憶體頁回傳，
/* Lock and remove page from the per-cpu list */
static struct page *rmqueue_pcplist(struct zone *preferred_zone,
struct zone *zone, gfp_t gfp_flags,
int migratetype, unsigned int alloc_flags)
{
struct per_cpu_pages *pcp;
struct list_head *list;
struct page *page;
unsigned long flags;
// 關閉中斷
local_irq_save(flags);
// 獲取運行當前行程的 CPU 高速快取串列 pcplist
pcp = &this_cpu_ptr(zone->pageset)->pcp;
// 獲取指定頁面遷移型別的 pcplist
list = &pcp->lists[migratetype];
// 從指定遷移型別的 pcplist 中移除一個頁面，用于記憶體分配
page = __rmqueue_pcplist(zone, migratetype, alloc_flags, pcp, list);
if (page) {
// 統計記憶體區域內的相關資訊
zone_statistics(preferred_zone, zone);
}
// 開中斷
local_irq_restore(flags);
return page;
}
pcplist 中快取的記憶體頁面其實全部來自于伙伴系統，當 pcplist 中的頁面數量 count 為 0 （表示此時 pcplist 里沒有快取的頁面）時，內核會呼叫 rmqueue_bulk 從伙伴系統中獲取 batch 個物理頁面添加到 pcplist，從伙伴系統中獲取頁面的程序參照本文 "3. 伙伴系統的記憶體分配原理" 小節中的內容，
隨后內核會將 pcplist 中的第一個物理記憶體頁從鏈表中摘下回傳，count 計數減一，
/* Remove page from the per-cpu list, caller must protect the list */
static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,
unsigned int alloc_flags,
struct per_cpu_pages *pcp,
struct list_head *list)
{
struct page *page;
do {
// 如果當前 pcplist 中的頁面為空，那么則從伙伴系統中獲取 batch 個頁面放入 pcplist 中
if (list_empty(list)) {
pcp->count += rmqueue_bulk(zone, 0,
pcp->batch, list,
migratetype, alloc_flags);
if (unlikely(list_empty(list)))
return NULL;
}
// 獲取 pcplist 上的第一個物理頁面
page = list_first_entry(list, struct page, lru);
// 將該物理頁面從 pcplist 中摘除
list_del(&page->lru);
// pcplist 中的 count 減一
pcp->count--;
} while (check_new_pcp(page));
return page;
}
6.2 從伙伴系統中獲取記憶體頁
在本文 "3. 伙伴系統的記憶體分配原理" 小節中筆者詳細為大家介紹了伙伴系統的整個記憶體分配原理，那么在本小節中，我們將正式進入伙伴系統中，來看下伙伴系統在內核中是如何實作的，
在前面介紹的 rmqueue 函式中，涉及到伙伴系統入口函式的有兩個：
-
__rmqueue_smallest 函式主要是封裝了整個伙伴系統關于記憶體分配的核心流程，該函式中的代碼正是 “3. 伙伴系統的記憶體分配原理” 小節所講的核心內容，
-
__rmqueue 函式封裝的是伙伴系統的整個完整流程，底層呼叫了 __rmqueue_smallest 函式，它主要實作的是當伙伴系統 free_area 中對應的遷移串列 free_list[MIGRATE_TYPE] 無法滿足記憶體分配需求時， 記憶體分配在伙伴系統中的 fallback 流程，這一點筆者也在 “3. 伙伴系統的記憶體分配原理” 小節中詳細介紹過了，
當我們向內核申請的記憶體頁超過一頁（order > 0）時，內核就會進入伙伴系統中為我們申請記憶體，
如果記憶體分配策略 alloc_flags 指定了 ALLOC_HARDER 時，就會呼叫 __rmqueue_smallest 直接進入伙伴系統，從 free_list[MIGRATE_HIGHATOMIC] 鏈表中分配 order 大小的物理記憶體塊，
如果分配失敗或者 alloc_flags 沒有指定 ALLOC_HARDER 則會通過 __rmqueue 進入伙伴系統，這里會處理分配失敗之后的 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 },
};
6.2.1 __rmqueue_smallest 伙伴系統的核心實作
我們還是以 “3. 伙伴系統的記憶體分配原理” 小節中，介紹伙伴系統記憶體分配核心原理時，所舉的示例為大家剖析伙伴系統的核心原始碼實作，
假設當前伙伴系統中只有 order = 3 的空閑鏈表 free_area[3] ，其中只有一個空閑的記憶體塊，包含了連續的 8 個 page，其余剩下的分配階 order 對應的空閑鏈表中均是空的，
現在我們向伙伴系統申請一個 page 大小的記憶體（對應的分配階 order = 0），經過前面的介紹我們知道當申請一個 page 大小的記憶體時，內核是從 pcplist 中進行分配的，但是這里筆者為了方便給大家介紹伙伴系統，所以我們暫時讓它走伙伴系統的流程，
內核會在伙伴系統中從當前分配階 order 開始，依次遍歷 free_area[order] 里對應的指定頁面遷移型別 free_list[MIGRATE_TYPE] 鏈表，直到找到一個合適尺寸的記憶體塊為止，
在本示例中，內核會在伙伴系統中首先查看 order = 0 對應的空閑鏈表 free_area[0] 中是否有空閑記憶體塊可供分配，如果有，則將該空閑記憶體塊從 free_area[0] 摘下回傳，記憶體分配成功，
如果沒有，隨后內核會根據前邊介紹的記憶體分配邏輯，繼續升級到 free_area[1] , free_area[2] 鏈表中尋找空閑記憶體塊，直到查找到 free_area[3] 發現有一個可供分配的記憶體塊，這個記憶體塊中包含了 8 個連續的空閑 page，然后將這 8 個 連續的空閑 page 組成的記憶體塊依次進行減半分裂，將每次分裂出來的后半部分記憶體塊插入到對應尺寸的 free_area 中，如下圖所示：
/*
* Go through the free lists for the given migratetype and remove
* the smallest available page from the freelists
*/
static __always_inline
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
int migratetype)
{
unsigned int current_order;
struct free_area *area;
struct page *page;
/* 從當前分配階 order 開始在伙伴系統對應的 free_area[order] 里查找合適尺寸的記憶體塊*/
for (current_order = order; current_order < MAX_ORDER; ++current_order) {
// 獲取當前 order 在伙伴系統中對應的 free_area[order]
// 對應上圖 free_area[3]
area = &(zone->free_area[current_order]);
// 從 free_area[order] 中對應的 free_list[MIGRATE_TYPE] 鏈表中獲取空閑記憶體塊
page = get_page_from_free_area(area, migratetype);
if (!page)
// 如果當前 free_area[order] 中沒有空閑記憶體塊則繼續向上查找
// 對應上圖 free_area[0]，free_area[1]，free_area[2]
continue;
// 如果在當前 free_area[order] 中找到空閑記憶體塊，則從 free_list[MIGRATE_TYPE] 鏈表中摘除
// 對應上圖步驟 1：將記憶體塊從 free_area[3] 中摘除
del_page_from_free_area(page, area);
// 將摘下來的記憶體塊進行減半分裂并插入對應的尺寸的 free_area 中
// 對應上圖步驟 [2,3], [4,5], [6,7]
expand(zone, page, order, current_order, area, migratetype);
// 設定頁面的遷移型別
set_pcppage_migratetype(page, migratetype);
// 記憶體分配成功回傳，對應上圖步驟 8
return page;
}
// 記憶體分配失敗回傳 null
return NULL;
}
下面我們來看下減半分裂程序的實作，expand 函式中的引數在本節示例中：low = 指定分配階 order = 0，high = 最后遍歷到的分配階 order = 3，
static inline void expand(struct zone *zone, struct page *page,
int low, int high, struct free_area *area,
int migratetype)
{
// size = 8，表示當前要進行減半分裂的記憶體塊是由 8 個連續 page 組成的，
// 剛剛從 free_area[3] 上摘下
unsigned long size = 1 << high;
// 依次進行減半分裂，直到分裂出指定 order 的記憶體塊出來
// 對應上圖中的步驟 2，4，6
// 初始 high = 3 ,low = 0
while (high > low) {
// free_area 要降到下一階，此時變為 free_area[2]
area--;
// 分配階要降級 high = 2
high--;
// 記憶體塊尺寸要減半，由 8 變成 4，表示要分裂出由 4 個連續 page 組成的兩個記憶體塊，
// 參考上圖中的步驟 2
size >>= 1;
// 標記為保護頁，當其伙伴被釋放時，允許合并，參見 《4.伙伴系統的記憶體回收原理》小節
if (set_page_guard(zone, &page[size], high, migratetype))
continue;
// 將本次減半分裂出來的第二個記憶體塊插入到對應 free_area[high] 中
// 參見上圖步驟 3，5，7
add_to_free_area(&page[size], area, migratetype);
// 設定記憶體塊的分配階 high
set_page_order(&page[size], high);
// 本次分裂出來的第一個記憶體塊繼續回圈進行減半分裂直到 high = low
// 即已經分裂出來了指定 order 尺寸的記憶體塊無需在進行分裂了，直接回傳
// 參見上圖步驟 2，4，6
}
}
6.2.2 __rmqueue 伙伴系統的 fallback 實作
當我們向內核申請的記憶體頁面超過一頁（order > 0 ），并且記憶體分配策略 alloc_flags 中并沒有設定 ALLOC_HARDER 的時候，記憶體分配流程就會進入 __rmqueue 走常規的伙伴系統分配流程，
static __always_inline struct page *
__rmqueue(struct zone *zone, unsigned int order, int migratetype,
unsigned int alloc_flags)
{
struct page *page;
retry:
// 首先進入伙伴系統到指定頁面遷移型別的 free_list[migratetype] 獲取空閑記憶體塊
// 這里走的就是上小節中介紹的伙伴系統核心流程
page = __rmqueue_smallest(zone, order, migratetype);
if (unlikely(!page)) {
..... 當伙伴系統中沒有足夠指定遷移型別 migratetype 的空閑記憶體塊時，就會進入這個分支 .....
// 如果遷移型別是 MIGRATE_MOVABLE 則優先 fallback 到 CMA 區中分配記憶體
if (migratetype == MIGRATE_MOVABLE)
page = __rmqueue_cma_fallback(zone, order);
// 走常規的伙伴系統 fallback 流程，核心原理參見《3.伙伴系統的記憶體分配原理》小節
if (!page && __rmqueue_fallback(zone, order, migratetype,
alloc_flags))
goto retry;
}
// 記憶體分配成功
return page;
}
從上述 __rmqueue 函式的原始碼實作中我們可以看出，該函式處理了伙伴系統記憶體分配的例外流程，即呼叫 __rmqueue_smallest 進入伙伴系統分配記憶體時，發現伙伴系統各個分配階 free_area[order] 中對應的遷移串列 free_list[MIGRATE_TYPE] 無法滿足記憶體分配需求時，__rmqueue_smallest 函式就會回傳 null，伙伴系統記憶體分配失敗，
隨后內核就會進入伙伴系統的 fallback 流程，這里對 MIGRATE_MOVABLE 遷移型別做了一下特殊處理，當伙伴系統中 free_list[MIGRATE_MOVABLE] 沒有足夠空閑記憶體塊時，會優先降級到 CMA 區域內進行分配，
static __always_inline struct page *__rmqueue_cma_fallback(struct zone *zone,
unsigned int order)
{
return __rmqueue_smallest(zone, order, MIGRATE_CMA);
}
如果我們指定的頁面遷移型別并非 MIGRATE_MOVABLE 或者降級 CMA 之后仍然分配失敗，內核就會進入 __rmqueue_fallback 走常規的 fallback 流程，該函式封裝的正是筆者在 “3. 伙伴系統的記憶體分配原理” 小節的后半部分介紹的 fallback 邏輯：
在 __rmqueue_fallback 函式中，內核會根據預先定義的相關 fallback 規則開啟記憶體分配的 fallback 流程，fallback 規則在內核中用一個 int 型別的二維陣串列示，其中第一維表示需要進行 fallback 的頁面遷移型別，第二維表示 fallback 的優先級，后續內核會按照這個優先級 fallback 到具體的 free_list[fallback_migratetype] 中去分配記憶體，
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 中獲取，如果仍然無法滿足記憶體分配，才會失敗退出，
static __always_inline bool
__rmqueue_fallback(struct zone *zone, int order, int start_migratetype,
unsigned int alloc_flags)
{
// 最侄訓 fall back 到伙伴系統的哪個 free_area 中分配記憶體
struct free_area *area;
// fallback 和正常的分配流程正好相反，是從最高階的free_area[MAX_ORDER - 1] 開始查找空閑記憶體塊
int current_order;
// 最初指定的記憶體分配階
int min_order = order;
struct page *page;
// 最終計算出 fallback 到哪個頁面遷移型別 free_list 上
int fallback_mt;
// 是否可以從 free_list[fallback] 中竊取記憶體塊到 free_list[start_migratetype] 中
// start_migratetype 表示我們最初指定的頁面遷移型別
bool can_steal;
// 如果設定了 ALLOC_NOFRAGMENT 表示不希望引入記憶體碎片
// 在這種情況下內核會更加傾向于分配一個盡可能大的記憶體塊，避免向其他鏈表引入記憶體碎片
if (alloc_flags & ALLOC_NOFRAGMENT)
// pageblock_order 用于定義系統支持的巨型頁對應的分配階
// 默認為最大分配階 - 1 = 9
min_order = pageblock_order;
// fallback 記憶體分配流程從最高階 free_area 開始查找空閑記憶體塊（頁面遷移型別為 fallback 型別）
for (current_order = MAX_ORDER - 1; current_order >= min_order;
--current_order) {
// 獲取伙伴系統中最高階的 free_area
area = &(zone->free_area[current_order]);
// 按照上述的記憶體分配 fallback 規則查找最合適的 fallback 遷移型別
fallback_mt = find_suitable_fallback(area, current_order,
start_migratetype, false, &can_steal);
// 如果沒有合適的 fallback_mt，則繼續降級到下一個分配階 free_area 中查找
if (fallback_mt == -1)
continue;
// can_steal 會在 find_suitable_fallback 的程序中被設定
// 當我們指定的頁面遷移型別為 MIGRATE_MOVABLE 并且無法從其他 fallback 遷移型別串列中竊取頁面 can_steal = false 時
// 內核會更加傾向于 fallback 分配最小的可用頁面，即尺寸和指定order最接近的頁面數量而不是尺寸最大的
// 因為這里的條件是分配可移動的頁面型別，天然可以避免永久記憶體碎片，無需按照最大的尺寸分配
if (!can_steal && start_migratetype == MIGRATE_MOVABLE
&& current_order > order)
goto find_smallest;
// can_steal = true，則開始從 free_list[fallback] 串列中竊取頁面
goto do_steal;
}
return false;
find_smallest:
// 該分支目的在于尋找尺寸最貼近指定 order 大小的最小可用頁面
// 從指定 order 開始 fallback
for (current_order = order; current_order < MAX_ORDER;
current_order++) {
area = &(zone->free_area[current_order]);
fallback_mt = find_suitable_fallback(area, current_order,
start_migratetype, false, &can_steal);
if (fallback_mt != -1)
break;
}
do_steal:
// 從上述流程獲取到的伙伴系統 free_area 中獲取 free_list[fallback_mt]
page = get_page_from_free_area(area, fallback_mt);
// 從 free_list[fallback_mt] 中竊取頁面到 free_list[start_migratetype] 中
steal_suitable_fallback(zone, page, alloc_flags, start_migratetype,
can_steal);
// 回傳到 __rmqueue 函式中進行 retry 重試流程，此時 free_list[start_migratetype] 中已經有足夠的記憶體頁面可供分配了
return true;
}
從上述記憶體分配 fallback 原始碼實作中，我們可以看出記憶體分配 fallback 流程正好和正常的分配流程相反：
-
伙伴系統正常記憶體分配流程先是從低階到高階依次查找空閑記憶體塊，然后將高階中的記憶體塊依次減半分裂到低階 free_list 鏈表中，
-
伙伴系統 fallback 記憶體分配流程則是先從最高階開始查找，找到一塊空閑記憶體塊之后，先遷移到最初指定的 free_list[start_migratetype] 鏈表中，然后在指定的 free_list[start_migratetype] 鏈表中執行減半分裂，
6.2.3 fallback 核心邏輯實作
本小節我們來看下內核定義的 fallback 規則具體的流程實作，fallback 規則定義如下，筆者在之前的章節中已經多次提到過了，這里不在重復解釋，我們重點關注它的 fallback 流程實作，
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 },
};
find_suitable_fallback 函式中封裝了頁面遷移型別整個的 fallback 程序：
-
fallback 規則定義在 fallbacks[MIGRATE_TYPES][3] 二維陣列中，第一維表示要進行 fallback 的頁面遷移型別 migratetype，第二維 migratetype 遷移型別可以 fallback 到哪些遷移型別中，這些可以 fallback 的頁面遷移型別按照優先級排列，
-
該函式的核心邏輯是在
for (i = 0;; i++)回圈中按照 fallbacks[migratetype][i] 陣列定義的 fallback 優先級，依次在 free_area[order] 中對應的 free_list[fallback] 串列中查找是否有空閑的記憶體塊，
- 如果當前 free_list[fallback] 串列中沒有空閑記憶體塊，則繼續在 for 回圈中降級到下一個 fallback 頁面遷移型別中去查找，也就是 for 回圈中的 fallbacks[migratetype][i] ，直到找到空閑記憶體塊為止，否則回傳 -1，
int find_suitable_fallback(struct free_area *area, unsigned int order,
int migratetype, bool only_stealable, bool *can_steal)
{
int i;
// 最終選取的 fallback 頁面遷移型別
int fallback_mt;
// 當前 free_area[order] 中以無空閑頁面，則回傳失敗
if (area->nr_free == 0)
return -1;
*can_steal = false;
// 按照 fallback 優先級，回圈在 free_list[fallback] 中查詢是否有空閑記憶體塊
for (i = 0;; i++) {
// 按照優先級獲取 fallback 頁面遷移型別
fallback_mt = fallbacks[migratetype][i];
if (fallback_mt == MIGRATE_TYPES)
break;
// 如果當前 free_list[fallback] 為空則繼續回圈降級查找
if (free_area_empty(area, fallback_mt))
continue;
// 判斷是否可以從 free_list[fallback] 竊取頁面到指定 free_list[migratetype] 中
if (can_steal_fallback(order, migratetype))
*can_steal = true;
if (!only_stealable)
return fallback_mt;
if (*can_steal)
return fallback_mt;
}
return -1;
}
// 這里竊取頁面的目的是從 fallback 型別的 freelist 中拿到一個高階的大記憶體塊
// 之所以要竊取盡可能大的記憶體塊是為了避免引入記憶體碎片
// 但 MIGRATE_MOVABLE 型別的頁面本身就可以避免永久記憶體碎片
// 所以 fallback MIGRATE_MOVABLE 型別的頁面時，會跳轉到 find_smallest 分支只需要選擇一個合適的 fallback 記憶體塊即可
static bool can_steal_fallback(unsigned int order, int start_mt)
{
if (order >= pageblock_order)
return true;
if (order >= pageblock_order / 2 ||
start_mt == MIGRATE_RECLAIMABLE ||
start_mt == MIGRATE_UNMOVABLE ||
page_group_by_mobility_disabled)
return true;
// 跳轉到 find_smallest 分支選擇一個合適的 fallback 記憶體塊
return false;
}
can_steal_fallback 函式中定義了是否可以從 free_list[fallback] 竊取頁面到指定 free_list[migratetype] 中，邏輯如下：
- 如果我們指定的記憶體分配階 order 大于等于 pageblock_order，則回傳 true，pageblock_order 表示系統中支持的巨型頁對應的分配階，默認為伙伴系統中的最大分配階減一，我們可以通過
cat /proc/pagetypeinfo命令查看，
-
如果我們指定的頁面遷移型別為 MIGRATE_RECLAIMABLE 或者 MIGRATE_UNMOVABLE，則不管我們要申請的頁面尺寸有多大，內核都會允許竊取頁面 can_steal = true ，因為它們最侄訓 fallback 到 MIGRATE_MOVABLE 可移動頁面型別中，這樣造成記憶體碎片的情況會少一些，
-
當內核全域變數 page_group_by_mobility_disabled 設定為 1 時，則所有物理記憶體頁面都是不可移動的，這時內核也允許竊取頁面，
在系統初始化期間，所有頁都被標記為 MIGRATE_MOVABLE 可移動的頁面型別，其他的頁面遷移型別都是后來通過 __rmqueue_fallback 竊取產生的，而是否能夠竊取 fallback 遷移型別串列中的頁面，就是本小節介紹的內容，
7. 記憶體釋放原始碼實作
在 《深入理解 Linux 物理記憶體分配全鏈路實作》 中的 “1. 內核物理記憶體分配介面” 小節中我們介紹了內核分配物理記憶體的相關介面：
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)
內核釋放物理記憶體的相關介面，這也是本小節的重點：
void __free_pages(struct page *page, unsigned int order);
void free_pages(unsigned long addr, unsigned int order);
- __free_pages ： 同 alloc_pages 函式對應，用于釋放 2 的 order 次冪個記憶體頁，釋放的物理記憶體區域起始地址由該區域中的第一個 page 實體指標表示，也就是引數里的 struct page *page 指標，
void __free_pages(struct page *page, unsigned int order)
{
if (put_page_testzero(page))
free_the_page(page, order);
}
- free_pages：同 __get_free_pages 函式對應，與 __free_pages 函式的區別是在釋放物理記憶體時，使用了虛擬記憶體地址而不是 page 指標，
void free_pages(unsigned long addr, unsigned int order)
{
if (addr != 0) {
// 校驗虛擬記憶體地址 addr 的有效性
VM_BUG_ON(!virt_addr_valid((void *)addr));
// 將虛擬記憶體地址 addr 轉換為 page，最侄訓是呼叫 __free_pages
__free_pages(virt_to_page((void *)addr), order);
}
}
在我們釋放記憶體時需要非常謹慎小心，只能釋放屬于你自己的頁，傳遞了錯誤的 struct page 指標或者錯誤的虛擬記憶體地址，或者傳遞錯了 order 值都可能會導致系統的崩潰，在內核空間中，內核是完全信賴自己的，這點和用戶空間不同，
另外內核也提供了 __free_page 和 free_page 兩個宏，專門用于釋放單個物理記憶體頁，
#define __free_page(page) __free_pages((page), 0)
#define free_page(addr) free_pages((addr), 0)
我們可以看出無論是內核定義的這些用于釋放記憶體的宏或是輔助函式，它們最侄訓呼叫 __free_pages，這里正是釋放記憶體的核心所在，
static inline void free_the_page(struct page *page, unsigned int order)
{
if (order == 0)
// 如果釋放一頁的話，則直接釋放到 CPU 高速快取串列 pcplist 中
free_unref_page(page);
else
// 如果釋放多頁的話，則進入伙伴系統回收這部分記憶體
__free_pages_ok(page, order);
}
從這里我們看到伙伴系統回收記憶體的流程和伙伴系統分配記憶體的流程是一樣的，在最開始首先都會檢查本次釋放或者分配的是否只是一個物理記憶體頁（order = 0），如果是則直接釋放到 CPU 高速快取串列 pcplist 中，如果不是則將記憶體釋放回伙伴系統中，
struct zone {
struct per_cpu_pages __percpu *per_cpu_pageset;
}
struct per_cpu_pages {
int count; /* pcplist 里的頁面總數 */
int high; /* pcplist 里的高水位線，count 超過 high 時，內核會釋放 batch 個頁面到伙伴系統中*/
int batch; /* pcplist 里的頁面來自于伙伴系統，batch 定義了每次從伙伴系統獲取或者歸還多少個頁面*/
// CPU 高速快取串列 pcplist，每個遷移型別對應一個 pcplist
struct list_head lists[NR_PCP_LISTS];
};
7.1 釋放記憶體至 CPU 高速快取串列 pcplist 中
/*
* Free a 0-order page
*/
void free_unref_page(struct page *page)
{
unsigned long flags;
// 獲取要釋放的物理記憶體頁對應的物理頁號 pfn
unsigned long pfn = page_to_pfn(page);
// 關閉中斷
local_irq_save(flags);
// 釋放物理記憶體頁至 pcplist 中
free_unref_page_commit(page, pfn);
// 開啟中斷
local_irq_restore(flags);
}
首先內核會通過 page_to_pfn 函式獲取要釋放記憶體頁對應的物理頁號，而物理頁號 pfn 的計算邏輯會根據記憶體模型的不同而不同，關于 page_to_pfn 在不同記憶體模型下的計算邏輯，大家可以回看下筆者之前文章 《深入理解 Linux 物理記憶體管理》中的 “ 2. 從 CPU 角度看物理記憶體模型 ” 小節，
最后通過 free_unref_page_commit 函式將記憶體頁釋放至 CPU 高速快取串列 pcplist 中，這里大家需要注意的是在釋放的程序中是不會回應中斷的，
static void free_unref_page_commit(struct page *page, unsigned long pfn)
{
// 獲取記憶體頁所在物理記憶體區域 zone
struct zone *zone = page_zone(page);
// 運行當前行程的 CPU 高速快取串列 pcplist
struct per_cpu_pages *pcp;
// 頁面的遷移型別
int migratetype;
migratetype = get_pcppage_migratetype(page);
// 內核這里只會將 UNMOVABLE,MOVABLE,RECLAIMABLE 這三種頁面遷移型別放入 pcplist 中，其余的遷移型別均釋放回伙伴系統
if (migratetype >= MIGRATE_PCPTYPES) {
if (unlikely(is_migrate_isolate(migratetype))) {
// 釋放回伙伴系統
free_one_page(zone, page, pfn, 0, migratetype);
return;
}
// 內核這里會將 HIGHATOMIC 型別頁面當做 MIGRATE_MOVABLE 型別處理
migratetype = MIGRATE_MOVABLE;
}
// 獲取運行當前行程的 CPU 高速快取串列 pcplist
pcp = &this_cpu_ptr(zone->pageset)->pcp;
// 將要釋放的物理記憶體頁添加到 pcplist 中
list_add(&page->lru, &pcp->lists[migratetype]);
// pcplist 頁面計數加一
pcp->count++;
// 如果 pcp 中的頁面總數超過了 high 水位線，則將 pcp 中的 batch 個頁面釋放回伙伴系統中
if (pcp->count >= pcp->high) {
unsigned long batch = READ_ONCE(pcp->batch);
// 釋放 batch 個頁面回伙伴系統中
free_pcppages_bulk(zone, batch, pcp);
}
}
這里筆者需要強調的是，內核只會將 UNMOVABLE，MOVABLE，RECLAIMABLE 這三種頁面遷移型別放入 CPU 高速快取串列 pcplist 中，其余的遷移型別均需釋放回伙伴系統，
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 // 不代表任何區域，只是單純的標識遷移型別這個列舉
};
關于頁面遷移型別的介紹，可回看本文 "1. 伙伴系統的核心資料結構" 小節的內容，
通過 this_cpu_ptr 獲取運行當前行程的 CPU 高速快取串列 pcplist，然后將要釋放的物理記憶體頁添加到對應遷移型別的 pcp->lists[migratetype]，
在 CPU 高速快取串列 per_cpu_pages 中，每個遷移型別對應一個 pcplist ，
如果當前 pcplist 中的頁面數量 count 超過了規定的水位線 high 的值，說明現在 pcplist 中的頁面太多了，需要從 pcplist 中釋放 batch 個物理頁面到伙伴系統中，這個程序稱之為惰性合并，
根據本文 "4. 伙伴系統的記憶體回收原理" 小節介紹的內容，我們知道，單記憶體頁直接釋放回伙伴系統會發生很多合并的動作，這里的惰性合并策略阻止了大量的無效合并操作，
7.2 伙伴系統回收記憶體原始碼實作
當我們要釋放的記憶體頁超過一頁（order > 0 ）時，內核會將這些記憶體頁回收至伙伴系統中，釋放記憶體時伙伴系統的入口函式為 __free_pages_ok：
static void __free_pages_ok(struct page *page, unsigned int order)
{
unsigned long flags;
int migratetype;
// 獲取釋放記憶體頁對應的物理頁號 pfn
unsigned long pfn = page_to_pfn(page);
// 在將記憶體頁回收至伙伴系統之前，需要將記憶體頁 page 相關的無用屬性清理一下
if (!free_pages_prepare(page, order, true))
return;
// 獲取頁面遷移型別，后續會將記憶體頁釋放至伙伴系統中的 free_list[migratetype] 中
migratetype = get_pfnblock_migratetype(page, pfn);
// 關中斷
local_irq_save(flags);
// 進入伙伴系統，釋放記憶體
free_one_page(page_zone(page), page, pfn, order, migratetype);
// 開中斷
local_irq_restore(flags);
}
__free_pages_ok 函式的邏輯比較容易理解，核心就是在將記憶體頁回收至伙伴系統之前，需要將這些記憶體頁的 page 結構清理一下，將無用的屬性至空，將清理之后干凈的 page 結構回收至伙伴系統中，這里大家需要注意的是在伙伴系統回收記憶體的時候也是不回應中斷的，
static void free_one_page(struct zone *zone,
struct page *page, unsigned long pfn,
unsigned int order,
int migratetype)
{
// 加鎖
spin_lock(&zone->lock);
// 正式進入伙伴系統回收記憶體，《4.伙伴系統的記憶體回收原理》小節介紹的邏輯全部封裝在這里
__free_one_page(page, pfn, zone, order, migratetype);
// 釋放鎖
spin_unlock(&zone->lock);
}
之前我們在 "4. 伙伴系統的記憶體回收原理" 小節中介紹的伙伴系統記憶體回收的全部邏輯就封裝在 __free_one_page 函式中，筆者這里建議大家在看下面相關原始碼實作的內容之前再去回顧下 5.3 小節的內容，
下面我們還是以 5.3 小節中所舉的具體例子來剖析內核如何將記憶體釋放回伙伴系統中的完整實作程序，
在開始之前，筆者還是先把當前伙伴系統中空閑記憶體頁的真實物理視圖給大家貼出來方便大家對比，后面在查找需要合并的伙伴的時候需要拿這張圖來做對比才能清晰的理解：
以下是系統中空閑記憶體頁在當前伙伴系統中的組織視圖，現在我們需要將 page10 釋放回伙伴系統中：
經過 “4. 伙伴系統的記憶體回收原理” 小節的內容介紹我們知道，在將記憶體塊釋放回伙伴系統時，內核需要從記憶體塊的當前階（本例中 order = 0）開始在伙伴系統 free_area[order] 中查找能夠合并的伙伴，
伙伴的定義筆者已經在 “2. 到底什么是伙伴” 小節中詳細為大家介紹過了，伙伴的核心就是兩個尺寸大小相同并且在物理上連續的兩個空閑記憶體塊，記憶體塊可以由一個物理記憶體頁組成的也可以是由多個物理記憶體頁組成的，
如果在當前階 free_area[order] 中找到了伙伴，則將釋放的記憶體塊和它的伙伴記憶體塊兩兩合并成一個新的記憶體塊，隨后繼續到高階中去查找新記憶體塊的伙伴，直到沒有伙伴可以合并為止，
/*
* Freeing function for a buddy system allocator.
*/
static inline void __free_one_page(struct page *page,
unsigned long pfn,
struct zone *zone, unsigned int order,
int migratetype)
{
// 釋放記憶體塊與其伙伴記憶體塊合并之后新記憶體塊的 pfn
unsigned long combined_pfn;
// 伙伴記憶體塊的 pfn
unsigned long uninitialized_var(buddy_pfn);
// 伙伴記憶體塊的首頁 page 指標
struct page *buddy;
// 伙伴系統中的最大分配階
unsigned int max_order;
continue_merging:
// 從釋放記憶體塊的當前分配階開始一直向高階合并記憶體塊，直到不能合并為止
// 在本例中當前分配階 order = 0，我們要釋放 page10
while (order < max_order - 1) {
// 在 free_area[order] 中查找伙伴記憶體塊的 pfn
// 上圖步驟一中伙伴的 pfn 為 11
// 上圖步驟二中伙伴的 pfn 為 8
// 上圖步驟三中伙伴的 pfn 為 12
buddy_pfn = __find_buddy_pfn(pfn, order);
// 根據偏移 buddy_pfn - pfn 計算伙伴記憶體塊中的首頁 page 地址
// 步驟一伙伴首頁為 page11，步驟二伙伴首頁為 page8，步驟三伙伴首頁為 page12
buddy = page + (buddy_pfn - pfn);
// 檢查伙伴 pfn 的有效性
if (!pfn_valid_within(buddy_pfn))
// 無效停止合并
goto done_merging;
// 按照前面介紹的伙伴定義檢查是否為伙伴
if (!page_is_buddy(page, buddy, order))
// 不是伙伴停止合并
goto done_merging;
// 將伙伴記憶體塊從當前 free_area[order] 串列中摘下，對比步驟一到步驟四
del_page_from_free_area(buddy, &zone->free_area[order]);
// 合并后新記憶體塊首頁 page 的 pfn
combined_pfn = buddy_pfn & pfn;
// 合并后新記憶體塊首頁 page 指標
page = page + (combined_pfn - pfn);
// 以合并后的新記憶體塊為基礎繼續向高階 free_area 合并
pfn = combined_pfn;
// 繼續向高階 free_area 合并，直到不能合并為止
order++;
}
done_merging:
// 表示在當前伙伴系統 free_area[order] 中沒有找到伙伴記憶體塊，停止合并
// 設定記憶體塊的分配階 order，存盤在第一個 page 結構中的 private 屬性中
set_page_order(page, order);
// 將最終合并的記憶體塊插入到伙伴系統對應的 free_are[order] 中，上圖中步驟五
add_to_free_area(page, &zone->free_area[order], migratetype);
}
根據上圖展示的在記憶體釋放程序中被釋放記憶體塊從當前階 free_area[order] 開始查找其伙伴并依次向高階 free_area 合并的程序以及結合筆者原始碼中提供的詳細注釋，整個記憶體釋放的程序還是不難理解的，
這里筆者想重點來講的是，內核如何在 free_area 鏈表中查找伙伴記憶體塊，以及如何判斷兩個記憶體塊是否為伙伴關系，下面我們來一起看下這部分內容：
7.3 如何查找伙伴
static inline unsigned long
__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
{
return page_pfn ^ (1 << order);
}
內核會通過 __find_buddy_pfn 函式根據當前釋放記憶體塊的 pfn，以及當前釋放記憶體塊的分配階 order 來確定其伙伴記憶體塊的 pfn，
首先通過 1 << order 左移操作確定要查找伙伴記憶體塊的分配階，因為伙伴關系最重要的一點就是它們必須是大小相等的兩個記憶體塊，然后巧妙地通過與要釋放記憶體塊的 pfn 進行異或操作就得到了伙伴記憶體塊的 pfn ，
7.4 如何判斷兩個記憶體塊是否是伙伴
另外一個重要的輔助函式就是 page_is_buddy，內核通過該函式來判斷給定兩個記憶體塊是否為伙伴關系，筆者在 "2. 到底什么是伙伴" 小節中明確的給出了伙伴的定義，page_is_buddy 就是相關的內核實作：
-
伙伴系統所管理的記憶體頁必須是可用的，不能處于記憶體空洞中，通過 page_is_guard 函式判斷，
-
伙伴必須是空閑的記憶體塊，這些記憶體塊必須存在于伙伴系統中，組成記憶體塊的記憶體頁 page 結構中的 flag 標志設定了 PG_buddy 標記，通過 PageBuddy 判斷這些記憶體頁是否在伙伴系統中，
-
兩個互為伙伴的記憶體塊必須擁有相同的分配階 order，也就是它們之間的大小尺寸必須一致，通過
page_order(buddy) == order判斷 -
互為伙伴關系的記憶體塊必須處于相同的物理記憶體區域 zone 中，通過
page_zone_id(page) == page_zone_id(buddy)判斷，
同時滿足上述四點的兩個記憶體塊即為伙伴關系，下面是內核中關于判斷是否為伙伴關系的原始碼實作：
static inline int page_is_buddy(struct page *page, struct page *buddy,
unsigned int order)
{
if (page_is_guard(buddy) && page_order(buddy) == order) {
if (page_zone_id(page) != page_zone_id(buddy))
return 0;
return 1;
}
if (PageBuddy(buddy) && page_order(buddy) == order) {
if (page_zone_id(page) != page_zone_id(buddy))
return 0;
return 1;
}
return 0;
}
總結
在本文的開頭，筆者首先為大家介紹了伙伴系統的核心資料結構，目的是在介紹核心原理之前，先為大家構建起伙伴系統的整個骨架，從整體上先認識一下伙伴系統的全域樣貌，
然后又為大家闡述了伙伴系統中的這個伙伴到底是什么概念 ，以及如何通過 __find_buddy_pfn 來查找記憶體塊的伙伴，如果通過 page_is_buddy 來判斷兩個記憶體塊是否為伙伴關系，
在我們明白了伙伴系統的這些基本概念以及全域框架結構之后，筆者詳細剖析了伙伴系統的記憶體分配原理及其實作，其中重點著墨了從高階 freelist 鏈表到低階 freelist 鏈表的減半分裂程序實作，以及記憶體分配失敗之后，伙伴系統的 fallback 程序實作，
最后又詳細剖析了伙伴系統記憶體回收的原理以及實作，其中重點著墨了從低階 freelist 到高階 freelist 的合并程序，
好了，到這里關于伙伴系統的全部內容就結束了，感謝大家的收看，我們下篇文章見~~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/542988.html
標籤：Linux