作者 | 趙青窕
審校 | 孫淑娟
內核內存管理比較復雜，主要包含了Buddy算法，vmalloc管理，slab算法，kmapper及與初始化階段物理內存管理相關的兩個模塊memblock和bootmem。除了上述模塊外，還有內存遷移，水線檢測，kmemleak，內存信息統計，PCP等輔助內容。在本文中，我將重點介紹Buddy算法（又稱為伙伴算法），該算法是以頁為單位進行管理的。
Buddy算法介紹
目前，內核中的Buddy算法采用下圖的方式管理內存。我把Buddy算法分為如下圖所示的三部分，在區域一中，核心的數據結構是struct zone;在區域二中核心的數據結構是struct free_area free_area[MAX_ORDER];在區域三中，page鏈表是核心內容。接下來，我將詳細介紹這三個板塊，并通過分配函數來說明Buddy的工作細節。
圖 1 Buddy框架
1.區域
通常用zone代表不同的內存管理區，即把內存劃分成不同的組，每個組就是一個zone。
在內核中，每個zone通過結構體struct zone來表示，其結構體中主要成員如下：
struct zone {
unsigned long watermark[NR_WMARK];
unsigned long zone_start_pfn;
unsigned long managed_pages;
unsigned long spanned_pages;
unsigned long present_pages;
struct free_area free_area[MAX_ORDER];
const char *name;
struct pglist_data *zone_pgdat;
}
- 標識內存水線的成員unsigned long watermark[NR_WMARK]，其中NR_WMARK定義如下：
enum zone_watermarks {
WMARK_MIN,
WMARK_LOW,
WMARK_HIGH,
NR_WMARK
};
從上面定義可知，每個zone存在三個水線，若當前zone中空閑頁高于WMARK_HIGH，則當前zone區的空閑內存較多;若空閑頁低于WMARK_LOW，則交換守護進程開始將內存交換到磁盤上;若空閑頁低于WMARK_MIN，則內存回收系統還需要大量回收內存。在使用Buddy進行內存申請時，會進行水線判斷，從而進行相應的操作;
- 伙伴系統管理相關的成員
unsigned long zone_start_pfn;
unsigned long managed_pages;
unsigned long spanned_pages;
unsigned long present_pages;
struct free_area free_area[MAX_ORDER]
前四個是相應zone區對應的頁號信息，free_area是伙伴算法中的關鍵成員，也是區域一和區域二銜接的關鍵成員，每個zone區會劃分為MAX_ORDER個組，數組free_area中的每個成員就代表一個組。
- 成員const char *name指明了對應zone區的名稱，通常情況下為dma，Normal或highmem，其中highmem不會出現在64位的系統中;下面是典型的32位系統中的zone劃分方式：
ZONE_DMA（0~16M）:DMA內存分配區;
ZONE_NORMAL（16MB~896MB）：普通映射的內存區域;
ZONE_HIGHMEM（896MB~）：高端內存區域，其中的頁不能永久映射到內核地址空間;內核一般不使用，如果要使用，通過kmap做動態映射;
- 指向zone區對應node的指針成員struct pglist_data *zone_pgdat，node是內存管理中的一個重要成員。對于UMA架構，僅有一個node，所有的zone均屬于同一個node，但對于NUMA架構，會有多個不同的node，每個node又劃分為不同的zone，所有zone區也是通過struct pglist_data組織在一起的。
2.free_area和頁面鏈表
在內存管理和分配過程中，有一個重要參數order，當我們采用kmalloc申請大內存時，最后會調用函數__alloc_pages_nodemask來進行內存申請。該函數需要一個參數order，當order = 0時，表示要申請的內存大小是1（2的0次方）個頁面;當order = 1時，表示要申請的內存大小是2（2的1次方）個頁面。
次方在Buddy算法中，把內存按照2的冪次方（即2的order次方，order的范圍從0到MAX_ORDER）劃分成不同的組，每個組分別用對應的free_area[order]表示，例如free_area[0]對應的就是由內存塊大小為2的0次方的頁塊組成的組，free_area[1]對應的就是內存由塊大小為2的1次方的頁塊組成的組，而結構體結構區域正是通過成員free_area把圖1中的區域一和區域二串聯在一起。
結構體struct free_area定義如下（不同平臺或者不同內核會有差異，但核心思想相同）：
struct free_area {
struct list_head free_list[MIGRATE_TYPES];
unsigned long nr_free;
};
從該結構可以看出，每一個free_area又根據MIGRATE_TYPES劃分為不同的組，每組分別通過鏈表free_list把同一類頁塊串聯在一起，這樣free_list就把圖1中的區域二和區域三串聯在一起了，從而間接的把區域一和區域三關聯在一起了。
結構體結構 page比較復雜，其中有一個成員結構list_head lru，通過該成員把圖1中區域三中的頁塊同區域二中對應的free_list鏈接在一起。
Buddy內存分配與釋放
在此，我將通過一個示例來簡要地展示Buddy內存分配的核心思想。當通過Buddy分配一個物理頁（即order = 0）時，會從對應zone區中free_area[0]管理的區域分配一個頁面（暫時先不考慮PCP的情況），并將該頁面從 free_area[0] 鏈表中移除;當free_area[0] 上沒有可用的物理頁時，Buddy會在free_area[1]上查找，若存在可用的物理頁，則將該頁塊從free_area[1] 的鏈表中移除，同時把該頁塊拆分成兩塊，其中一塊插入到free_area[0]中，另一塊傳遞給內存請求者;倘若free_area[1]上也沒有可用頁，則會繼續向上查找。
下圖2所示是沒有對應oder = 0的頁塊情況，因此把order = 1中的一個頁塊進行拆分，一半返回給order = 1的鏈表，一半返回給請求者。假如order = 1中沒有需要的頁塊，在內存分配過程中會繼續從order = 3中進行查找，直到找到頁塊或者遍歷完所有order。
圖 2 分配物理頁面示意圖
實際上，在整個內存分配過程中，會伴隨很多特殊情況處理。Buddy算法在進行內存分配時，會根據水線設置，來進行內存回收或者喚醒內核線程kswapd，或者是采用CPU的冷熱頁面隊列進行內存分配，或者是進行頁面移動等。假如已經嘗試頁面移動，kswapd已經喚出了一些頁面，同時也進行了內存回收，依然沒有可分配的內存，此時就會觸發out_of_memory。總之，這些特殊情況的處理方式均離不開圖1所示的Buddy框架。
下圖是我根據我本地的代碼整理的采用kmalloc申請大內存時的調用過程（使用kmalloc申請小內存時不通過Buddy），其中最關鍵的內存分配函數是prepare_alloc_pages，get_page_from_freelist，rmqueue 和__alloc_pages_slowpath。感興趣的朋友可以結合圖1所示的框架查看這幾個函數的具體實現。
當向系統釋放一個物理頁的時候，會通過struct page來推導出該page對應的zone區（比如該page屬于NORMAL區）和對應的page類型，緊接著將根據對應的order進行頁的合并（即圖1中區域三的部分進行合并），最后將合并后的塊插入到新的order中去，這個合并過程一直持續下去，直到不能合并或者已經合并到最大的order處。例如當釋放的物理頁得到其屬于NORMAL區的free_area[0]，此時free_area[0]中存在頁面可以和釋放的頁面合并，從而把合并后的添加到free_area[1]中，這個合并操作會一直持續下去，直到合并完為止。這個過程實際上就是圖2的反過程。
總結
內存的管理比較復雜，本文主要介紹了Buddy的核心思想，但這僅僅是內存管理的冰山一角，卻是比較基礎且核心的內容，因此了解Buddy整體架構是非常有必要的。
作者介紹
趙青窕，51CTO社區編輯，從事多年驅動開發。研究興趣包含安全OS和網絡安全領域，發表過網絡相關專利。
