說說Buddy算法的那些事

作者：趙青窕 2022-07-19 13:31:18

在本文中，我將重點(diǎn)介紹Buddy算法（又稱為伙伴算法），該算法是以頁(yè)為單位進(jìn)行管理的。

作者 | 趙青窕

審校 | 孫淑娟

內(nèi)核內(nèi)存管理比較復(fù)雜，主要包含了Buddy算法，vmalloc管理，slab算法，kmapper及與初始化階段物理內(nèi)存管理相關(guān)的兩個(gè)模塊memblock和bootmem。除了上述模塊外，還有內(nèi)存遷移，水線檢測(cè)，kmemleak，內(nèi)存信息統(tǒng)計(jì)，PCP等輔助內(nèi)容。在本文中，我將重點(diǎn)介紹Buddy算法（又稱為伙伴算法），該算法是以頁(yè)為單位進(jìn)行管理的。

Buddy算法介紹

目前，內(nèi)核中的Buddy算法采用下圖的方式管理內(nèi)存。我把Buddy算法分為如下圖所示的三部分，在區(qū)域一中，核心的數(shù)據(jù)結(jié)構(gòu)是struct zone;在區(qū)域二中核心的數(shù)據(jù)結(jié)構(gòu)是struct free_area free_area[MAX_ORDER];在區(qū)域三中，page鏈表是核心內(nèi)容。接下來，我將詳細(xì)介紹這三個(gè)板塊，并通過分配函數(shù)來說明Buddy的工作細(xì)節(jié)。

圖 1 Buddy框架

1.區(qū)域

通常用zone代表不同的內(nèi)存管理區(qū)，即把內(nèi)存劃分成不同的組，每個(gè)組就是一個(gè)zone。

在內(nèi)核中，每個(gè)zone通過結(jié)構(gòu)體struct zone來表示，其結(jié)構(gòu)體中主要成員如下：

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;
}

標(biāo)識(shí)內(nèi)存水線的成員unsigned long watermark[NR_WMARK]，其中NR_WMARK定義如下：

enum zone_watermarks {
  WMARK_MIN,
  WMARK_LOW,
  WMARK_HIGH,
  NR_WMARK
};

從上面定義可知，每個(gè)zone存在三個(gè)水線，若當(dāng)前zone中空閑頁(yè)高于WMARK_HIGH，則當(dāng)前zone區(qū)的空閑內(nèi)存較多;若空閑頁(yè)低于WMARK_LOW，則交換守護(hù)進(jìn)程開始將內(nèi)存交換到磁盤上;若空閑頁(yè)低于WMARK_MIN，則內(nèi)存回收系統(tǒng)還需要大量回收內(nèi)存。在使用Buddy進(jìn)行內(nèi)存申請(qǐng)時(shí)，會(huì)進(jìn)行水線判斷，從而進(jìn)行相應(yīng)的操作;

伙伴系統(tǒng)管理相關(guān)的成員

unsigned long   zone_start_pfn;    
unsigned long   managed_pages;     
unsigned long   spanned_pages;     
unsigned long   present_pages;
struct free_area  free_area[MAX_ORDER]

前四個(gè)是相應(yīng)zone區(qū)對(duì)應(yīng)的頁(yè)號(hào)信息，free_area是伙伴算法中的關(guān)鍵成員，也是區(qū)域一和區(qū)域二銜接的關(guān)鍵成員，每個(gè)zone區(qū)會(huì)劃分為MAX_ORDER個(gè)組，數(shù)組free_area中的每個(gè)成員就代表一個(gè)組。

成員const char *name指明了對(duì)應(yīng)zone區(qū)的名稱，通常情況下為dma，Normal或highmem，其中highmem不會(huì)出現(xiàn)在64位的系統(tǒng)中;下面是典型的32位系統(tǒng)中的zone劃分方式：

ZONE_DMA（0~16M）:DMA內(nèi)存分配區(qū);

ZONE_NORMAL（16MB~896MB）：普通映射的內(nèi)存區(qū)域;

ZONE_HIGHMEM（896MB~）：高端內(nèi)存區(qū)域，其中的頁(yè)不能永久映射到內(nèi)核地址空間;內(nèi)核一般不使用，如果要使用，通過kmap做動(dòng)態(tài)映射;

指向zone區(qū)對(duì)應(yīng)node的指針成員struct pglist_data *zone_pgdat，node是內(nèi)存管理中的一個(gè)重要成員。對(duì)于UMA架構(gòu)，僅有一個(gè)node，所有的zone均屬于同一個(gè)node，但對(duì)于NUMA架構(gòu)，會(huì)有多個(gè)不同的node，每個(gè)node又劃分為不同的zone，所有zone區(qū)也是通過struct pglist_data組織在一起的。

2.free_area和頁(yè)面鏈表

在內(nèi)存管理和分配過程中，有一個(gè)重要參數(shù)order，當(dāng)我們采用kmalloc申請(qǐng)大內(nèi)存時(shí)，最后會(huì)調(diào)用函數(shù)__alloc_pages_nodemask來進(jìn)行內(nèi)存申請(qǐng)。該函數(shù)需要一個(gè)參數(shù)order，當(dāng)order = 0時(shí)，表示要申請(qǐng)的內(nèi)存大小是1（2的0次方）個(gè)頁(yè)面;當(dāng)order = 1時(shí)，表示要申請(qǐng)的內(nèi)存大小是2（2的1次方）個(gè)頁(yè)面。

次方在Buddy算法中，把內(nèi)存按照2的冪次方（即2的order次方，order的范圍從0到MAX_ORDER）劃分成不同的組，每個(gè)組分別用對(duì)應(yīng)的free_area[order]表示，例如free_area[0]對(duì)應(yīng)的就是由內(nèi)存塊大小為2的0次方的頁(yè)塊組成的組，free_area[1]對(duì)應(yīng)的就是內(nèi)存由塊大小為2的1次方的頁(yè)塊組成的組，而結(jié)構(gòu)體結(jié)構(gòu)區(qū)域正是通過成員free_area把圖1中的區(qū)域一和區(qū)域二串聯(lián)在一起。

結(jié)構(gòu)體struct free_area定義如下（不同平臺(tái)或者不同內(nèi)核會(huì)有差異，但核心思想相同）：

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

從該結(jié)構(gòu)可以看出，每一個(gè)free_area又根據(jù)MIGRATE_TYPES劃分為不同的組，每組分別通過鏈表free_list把同一類頁(yè)塊串聯(lián)在一起，這樣free_list就把圖1中的區(qū)域二和區(qū)域三串聯(lián)在一起了，從而間接的把區(qū)域一和區(qū)域三關(guān)聯(lián)在一起了。

結(jié)構(gòu)體結(jié)構(gòu) page比較復(fù)雜，其中有一個(gè)成員結(jié)構(gòu)list_head lru，通過該成員把圖1中區(qū)域三中的頁(yè)塊同區(qū)域二中對(duì)應(yīng)的free_list鏈接在一起。

Buddy內(nèi)存分配與釋放

在此，我將通過一個(gè)示例來簡(jiǎn)要地展示Buddy內(nèi)存分配的核心思想。當(dāng)通過Buddy分配一個(gè)物理頁(yè)（即order = 0）時(shí)，會(huì)從對(duì)應(yīng)zone區(qū)中free_area[0]管理的區(qū)域分配一個(gè)頁(yè)面（暫時(shí)先不考慮PCP的情況），并將該頁(yè)面從 free_area[0] 鏈表中移除;當(dāng)free_area[0] 上沒有可用的物理頁(yè)時(shí)，Buddy會(huì)在free_area[1]上查找，若存在可用的物理頁(yè)，則將該頁(yè)塊從free_area[1] 的鏈表中移除，同時(shí)把該頁(yè)塊拆分成兩塊，其中一塊插入到free_area[0]中，另一塊傳遞給內(nèi)存請(qǐng)求者;倘若free_area[1]上也沒有可用頁(yè)，則會(huì)繼續(xù)向上查找。

下圖2所示是沒有對(duì)應(yīng)oder = 0的頁(yè)塊情況，因此把order = 1中的一個(gè)頁(yè)塊進(jìn)行拆分，一半返回給order = 1的鏈表，一半返回給請(qǐng)求者。假如order = 1中沒有需要的頁(yè)塊，在內(nèi)存分配過程中會(huì)繼續(xù)從order = 3中進(jìn)行查找，直到找到頁(yè)塊或者遍歷完所有order。

圖 2 分配物理頁(yè)面示意圖

實(shí)際上，在整個(gè)內(nèi)存分配過程中，會(huì)伴隨很多特殊情況處理。Buddy算法在進(jìn)行內(nèi)存分配時(shí)，會(huì)根據(jù)水線設(shè)置，來進(jìn)行內(nèi)存回收或者喚醒內(nèi)核線程kswapd，或者是采用CPU的冷熱頁(yè)面隊(duì)列進(jìn)行內(nèi)存分配，或者是進(jìn)行頁(yè)面移動(dòng)等。假如已經(jīng)嘗試頁(yè)面移動(dòng)，kswapd已經(jīng)喚出了一些頁(yè)面，同時(shí)也進(jìn)行了內(nèi)存回收，依然沒有可分配的內(nèi)存，此時(shí)就會(huì)觸發(fā)out_of_memory。總之，這些特殊情況的處理方式均離不開圖1所示的Buddy框架。

下圖是我根據(jù)我本地的代碼整理的采用kmalloc申請(qǐng)大內(nèi)存時(shí)的調(diào)用過程（使用kmalloc申請(qǐng)小內(nèi)存時(shí)不通過Buddy），其中最關(guān)鍵的內(nèi)存分配函數(shù)是prepare_alloc_pages，get_page_from_freelist，rmqueue 和__alloc_pages_slowpath。感興趣的朋友可以結(jié)合圖1所示的框架查看這幾個(gè)函數(shù)的具體實(shí)現(xiàn)。

當(dāng)向系統(tǒng)釋放一個(gè)物理頁(yè)的時(shí)候，會(huì)通過struct page來推導(dǎo)出該page對(duì)應(yīng)的zone區(qū)（比如該page屬于NORMAL區(qū)）和對(duì)應(yīng)的page類型，緊接著將根據(jù)對(duì)應(yīng)的order進(jìn)行頁(yè)的合并（即圖1中區(qū)域三的部分進(jìn)行合并），最后將合并后的塊插入到新的order中去，這個(gè)合并過程一直持續(xù)下去，直到不能合并或者已經(jīng)合并到最大的order處。例如當(dāng)釋放的物理頁(yè)得到其屬于NORMAL區(qū)的free_area[0]，此時(shí)free_area[0]中存在頁(yè)面可以和釋放的頁(yè)面合并，從而把合并后的添加到free_area[1]中，這個(gè)合并操作會(huì)一直持續(xù)下去，直到合并完為止。這個(gè)過程實(shí)際上就是圖2的反過程。