剖析Buddy算法中內(nèi)存的申請(qǐng)和釋放

作者：趙青窕 2022-07-28 08:00:00

內(nèi)存的合理利用一直是系統(tǒng)的頭等大事。目前系統(tǒng)中，除了采用Buddy和slab管理內(nèi)存外，還會(huì)采用內(nèi)存水線檢測(cè)處理，PCP機(jī)制，CMA機(jī)制等進(jìn)行內(nèi)存的優(yōu)化。在本文中，我們將從Buddy算法中內(nèi)存的申請(qǐng)和釋放，來探索內(nèi)存的奧秘。

作者 | 趙青窕

審校 | 孫淑娟

基本概念

zone：有的地方把zone稱為管理區(qū)，每個(gè)node下會(huì)劃分成不同的zone。有的系統(tǒng)會(huì)劃分成3個(gè)zone區(qū)，有的會(huì)劃分成2個(gè)zone區(qū)。zone區(qū)的個(gè)數(shù)會(huì)因平臺(tái)，內(nèi)核，系統(tǒng)的位數(shù)等有差異。

free_area：每個(gè)zone區(qū)根據(jù)2的order次方(order的范圍從0到MAX_ORDER)進(jìn)一步劃分，劃分后的每個(gè)小區(qū)域通過free_area[order]表示。

如下圖紅色方框中所示，按照紅色方框從左到右分別是node，zone和free_area。

水線：每個(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)存。

order：每個(gè)zone區(qū)根據(jù)order，把內(nèi)存按照2的order繼續(xù)劃分為不同的area。

PCP鏈表：該鏈表中的每一個(gè)成員大小均是2的0次方個(gè)頁(yè)面，每次申請(qǐng)和釋放1個(gè)頁(yè)面，都會(huì)優(yōu)先考慮PCP。當(dāng)PCP為空時(shí)，會(huì)從Buddy中申請(qǐng)；當(dāng)PCP中頁(yè)面比較多，超過限制時(shí)，會(huì)把頁(yè)面釋放到Buddy中。

內(nèi)存申請(qǐng)

比較常用的內(nèi)存申請(qǐng)函數(shù)是kmalloc，當(dāng)申請(qǐng)的內(nèi)存大于KMALLOC_MAX_CACHE_SIZE時(shí)，會(huì)通過函數(shù)kmalloc_large從Buddy中申請(qǐng)內(nèi)存，否則從slab中申請(qǐng)內(nèi)存。本文中暫不分析從slab申請(qǐng)內(nèi)存的情況。

kmalloc_large函數(shù)實(shí)現(xiàn)如下，Buddy算法中，內(nèi)存的分配和釋放均離不開order，我們可以看到，在該函數(shù)內(nèi)部通過size來計(jì)算出對(duì)應(yīng)的order，就很好地把Buddy和slab連接在一起了。

static __always_inline void *kmalloc_large(size_t size, gfp_t flags)
{
  unsigned int order = get_order(size);
  return kmalloc_order_trace(size, flags, order);
}

函數(shù)kmalloc_order_trace會(huì)調(diào)用函數(shù)alloc_pages，進(jìn)而調(diào)用函數(shù)struct page *__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid, nodemask_t *nodemask)來實(shí)現(xiàn)內(nèi)存的分配。實(shí)際上，Buddy提供的對(duì)外申請(qǐng)內(nèi)存函數(shù)是alloc_pages，但其內(nèi)部實(shí)現(xiàn)大部分情況下均是通過__alloc_pages_nodemask來實(shí)現(xiàn)。該函數(shù)分三步進(jìn)行處理，分別如下：

構(gòu)建內(nèi)存分配的上下文結(jié)構(gòu)，內(nèi)核中采用結(jié)構(gòu)體struct alloc_context來表示
快速分配
慢速分配

1.內(nèi)存分配上下文結(jié)構(gòu)

內(nèi)存分析上下文采用結(jié)構(gòu)體struct alloc_context來表示，其結(jié)構(gòu)體定義如下：

/*
 * Structure for holding the mostly immutable allocation parameters passed
 * between functions involved in allocations, including the alloc_pages*
 * family of functions.
 *
 * nodemask, migratetype and high_zoneidx are initialized only once in
 * __alloc_pages_nodemask() and then never change.
 *
 * zonelist, preferred_zone and classzone_idx are set first in
 * __alloc_pages_nodemask() for the fast path, and might be later changed
 * in __alloc_pages_slowpath(). All other functions pass the whole strucure
 * by a const pointer.
 */
struct alloc_context {
  struct zonelist *zonelist;
  nodemask_t *nodemask;
  struct zoneref *preferred_zoneref;
  int migratetype;
  enum zone_type high_zoneidx;
  bool spread_dirty_pages;
};

各個(gè)成員含義如下：

zonelist：用于分配內(nèi)存的zone區(qū)列鏈表。在內(nèi)存分配時(shí)，內(nèi)核會(huì)通過函數(shù)numa_node_id()來獲取當(dāng)前CPU的NUMA ID，進(jìn)而根據(jù)這個(gè)ID號(hào)獲取對(duì)應(yīng)的zonelist。內(nèi)存的分配實(shí)際上就是在zonelist找合適的內(nèi)存進(jìn)行分配，該成員在后面兩步中具有關(guān)鍵作用；
nodemask：用來指定從哪一個(gè)node中進(jìn)行內(nèi)存分配。若沒有指定，則會(huì)在所有節(jié)點(diǎn)中嘗試分配，通常情況下該值為NULL；
high_zoneidx：該成員從字面意思看就是最高的zone區(qū)id號(hào)，其實(shí)它表示的是在分配時(shí)，所能分配的最高zone區(qū)。通常一般是從HIGH區(qū)---->NORMAL---->DMA的方式進(jìn)行分配。內(nèi)存的需求方在請(qǐng)求進(jìn)行內(nèi)存分配時(shí)，會(huì)通過gfp_mask來對(duì)該成員進(jìn)行設(shè)置，Buddy在內(nèi)存分配及逆行內(nèi)存分配時(shí)需要通過函數(shù)gfp_zone(gfp_mask)來提取gfp_mask中對(duì)應(yīng)的high_zoneidx；
migratetype：該成員指明了需要內(nèi)存的頁(yè)面遷移類型。Buddy進(jìn)行內(nèi)存分配時(shí)需要通過函數(shù)gfpflags_to_migratetype(gfp_mask)來獲取內(nèi)存請(qǐng)求方的具體需求；
preferred_zone：結(jié)合成員high_zoneidx和zonelist，計(jì)算出首先從那個(gè)zone區(qū)開始進(jìn)行內(nèi)存的分配，即第一個(gè)將要被遍歷的zone，內(nèi)核中是通過函數(shù)first_zones_zonelist來計(jì)算該成員的；
spread_dirty_pages：當(dāng)申請(qǐng)內(nèi)存時(shí)，采用了標(biāo)志__GFP_WRITE，則說明此次申請(qǐng)的物理頁(yè)面將會(huì)生成臟頁(yè)，內(nèi)核中就是通過語(yǔ)句ac->spread_dirty_pages = (gfp_mask & __GFP_WRITE)來設(shè)置該成員的。

從上面的結(jié)構(gòu)體struct alloc_context的說明可以看出，該結(jié)構(gòu)體具體細(xì)化了內(nèi)存分配的各種需求，其具體實(shí)現(xiàn)如下圖中紅色方框所示：

2.快速分配

在完成第一步后，就可以通過函數(shù)get_page_from_freelist進(jìn)行一次快速分配。該函數(shù)才是內(nèi)存分配真正的開始位置，接下來我將詳細(xì)說明該過程，為了簡(jiǎn)化描述，同時(shí)為了讓大家容易理解，暫時(shí)不考慮CPUSET的情況。

該函數(shù)本質(zhì)就是從preferred_zone開始，遍歷zonelist，其每一次遍歷時(shí)，處理流程如下：

臟頁(yè)面判斷

每個(gè)node節(jié)點(diǎn)會(huì)對(duì)臟頁(yè)數(shù)進(jìn)行限制，當(dāng)超過限制后，將無法申請(qǐng)具有__GFP_WRITE標(biāo)志的內(nèi)存塊，需要跳出當(dāng)前zone區(qū)，轉(zhuǎn)而掃描下一個(gè)zone區(qū)，其內(nèi)核處理代碼如下圖所示，圖中進(jìn)行了標(biāo)注，方便大家理解。

水位處理

前面小節(jié)中有提到每個(gè)zone中存在三個(gè)水線，在內(nèi)存申請(qǐng)時(shí)，默認(rèn)采用WMARK_LOW，使用函數(shù)zone_watermark_fast進(jìn)行水線判斷。

假如通過水線檢測(cè)，發(fā)現(xiàn)內(nèi)存不夠，則會(huì)判斷當(dāng)前申請(qǐng)內(nèi)存的請(qǐng)求是否采用ALLOC_NO_WATERMARKS，若采用，則說明當(dāng)前剩余內(nèi)存多少與當(dāng)前申請(qǐng)沒有任何關(guān)系，會(huì)調(diào)用rmqueue進(jìn)行內(nèi)存分配；若沒有ALLOC_NO_WATERMARKS聲明，則進(jìn)行下一步reclaim操作；

假如通過水線檢測(cè)，發(fā)現(xiàn)當(dāng)前還有足夠內(nèi)存，則調(diào)用函數(shù)rmqueue進(jìn)行內(nèi)存分配。

reclaim操作

reclaim操作首先是通過函數(shù)zone_allows_reclaim來判斷當(dāng)前的node是否支撐reclaim操作，如果不支持，就退出當(dāng)前循環(huán)，執(zhí)行下一個(gè)循環(huán)操作；若支持，就調(diào)用node_reclaim執(zhí)行內(nèi)存回收的工作。

當(dāng)函數(shù)node_reclaim返回值是NODE_RECLAIM_NOSCAN或者NODE_RECLAIM_FULL時(shí)，表示當(dāng)前雖然內(nèi)存不夠，但我無能為力了。這種情況下，只能退出循環(huán)，執(zhí)行下一個(gè)操作；當(dāng)返回值是其余的情況時(shí)，就會(huì)重新進(jìn)行水位檢測(cè)，若此時(shí)內(nèi)存足夠，則調(diào)用rmqueue進(jìn)行內(nèi)存分配，否則退出循環(huán)，執(zhí)行下一個(gè)循環(huán)操作。

假如當(dāng)前系統(tǒng)使用的是非NUMA，則不會(huì)進(jìn)行reclaim操作，當(dāng)水位線檢測(cè)發(fā)現(xiàn)內(nèi)存不夠時(shí)，會(huì)跳出循環(huán)，嘗試下一個(gè)zone；假如當(dāng)前系統(tǒng)是NUMA，才會(huì)進(jìn)行上述描述中的判斷，來決定是否進(jìn)行內(nèi)存回收。

rmqueue內(nèi)存分配處理

在內(nèi)存分配時(shí)，分兩種情況進(jìn)行處理，分別是order = 0及order != 0。

當(dāng)order = 0時(shí)，會(huì)首先從PCP鏈表中進(jìn)行內(nèi)存申請(qǐng)，其具體流程如下：

當(dāng)order != 0，即要申請(qǐng)多頁(yè)，下面是其處理過程，根據(jù)實(shí)際情況調(diào)用__rmqueue_smallest，__rmqueue_cma或者_(dá)_rmqueue進(jìn)行內(nèi)存的分配。

對(duì)于設(shè)置了ALLOC_HARDER的情況，先嘗試通過函數(shù)__rmqueue_smallest來分配MIGRATE_HIGHATOMIC類型的內(nèi)存塊，具體實(shí)現(xiàn)就是從zone->free_area[order]中根據(jù)需要的內(nèi)存類型進(jìn)行分配。該函數(shù)實(shí)現(xiàn)比較簡(jiǎn)單，就是遍歷free_area以便找到合適的內(nèi)存塊，下圖是__rmqueue_smallest的實(shí)現(xiàn)，增加了注釋方便大家理解。

假如通過上面的__rmqueue_smallest沒有找到合適的內(nèi)存塊，在申請(qǐng)內(nèi)存時(shí)，使用標(biāo)志__GFP_CMA申請(qǐng)的MIGRATE_MOVABLE，則再次使用函數(shù)__rmqueue_cma申請(qǐng)內(nèi)存，實(shí)際上__rmqueue_cma內(nèi)部是調(diào)用__rmqueue_smallest(zone, order, MIGRATE_CMA)實(shí)現(xiàn)的。

若上面的兩步__rmqueue_smallest，__rmqueue_cma均失敗，則會(huì)調(diào)用__rmqueue。該函數(shù)內(nèi)部實(shí)際上也是通過__rmqueue_smallest實(shí)現(xiàn)的，當(dāng)__rmqueue_smallest只會(huì)從指定的migtatetype中進(jìn)行分配，當(dāng)分配失敗后，會(huì)通過函數(shù)__rmqueue_fallback從后備fallbacks中找到一個(gè)遷移類型頁(yè)塊，將其遷移到目標(biāo)遷移類型中后重新進(jìn)行分配。

至此快速分配結(jié)束，若已經(jīng)分配到內(nèi)存，則會(huì)退出分配流程，否則進(jìn)行下一步操作：慢速分配。

3.慢速分配

慢速分配是通過函數(shù)__alloc_pages_slowpath來實(shí)現(xiàn)的。從快速分配發(fā)現(xiàn)無法分配到需要的內(nèi)存，緊接著內(nèi)核通過慢速分配對(duì)內(nèi)存進(jìn)行整理，嘗試找到合適的內(nèi)存。其整理過程包含：

重新計(jì)算內(nèi)存分配上下文；
如果設(shè)置了__GFP_KSWAPD_RECLAIM，則會(huì)調(diào)用函數(shù)wake_all_kswapds來喚醒負(fù)責(zé)換出內(nèi)存頁(yè)的守護(hù)進(jìn)程kswapds；
因更新了內(nèi)存分配上下文，因此再次使用快速分配嘗試內(nèi)存分配。若分配成功，則退出本次分配；否則繼續(xù)進(jìn)行下一步操作；
若申請(qǐng)內(nèi)存時(shí)，設(shè)置了__GFP_DIRECT_RECLAIM，且非pfmemalloc情況下，會(huì)通過函數(shù)__alloc_pages_direct_compact進(jìn)行內(nèi)存壓縮后，再次嘗試分配頁(yè)面。若分配成功則退出；否則進(jìn)入下一步；
接下來的操作代碼中采用了retry代碼標(biāo)簽，這個(gè)過程比較繁瑣，其本質(zhì)就是采用各種內(nèi)存優(yōu)化手段盡量促使本次分配成功，優(yōu)化手段主要有以下四種：
通過函數(shù)__alloc_pages_direct_reclaim嘗試進(jìn)行內(nèi)存回收后，再分配內(nèi)存；
通過函數(shù)__alloc_pages_direct_compact嘗試進(jìn)行內(nèi)存整合后，再分配內(nèi)存；
通過函數(shù)__alloc_pages_may_oom嘗試殺掉一些優(yōu)先級(jí)不高的進(jìn)程后，再分配內(nèi)存；
在retry過程中，仍會(huì)調(diào)用wake_all_kswapds來喚醒kswapds，防止意外休眠。

這四種方式都會(huì)伴隨著調(diào)用函數(shù)get_page_from_freelist來進(jìn)行內(nèi)存分配。

至此內(nèi)存分配函數(shù)就完成了。從上面的描述可以看出，當(dāng)內(nèi)存足夠時(shí)，通常情況下快速分配就足夠了。只有在內(nèi)存不夠時(shí)，會(huì)進(jìn)行慢速分配，慢速分配里面進(jìn)行內(nèi)存回收，整理等操作后再進(jìn)行分配。若此時(shí)還沒有足夠的內(nèi)存可以分配，說明內(nèi)存耗盡，可能是因?yàn)閮?nèi)存泄漏導(dǎo)致內(nèi)存不足，這個(gè)時(shí)候就需要去定位內(nèi)存泄漏問題了。

內(nèi)存釋放

Buddy中內(nèi)存釋放入口函數(shù)是free_pages。該函數(shù)的實(shí)現(xiàn)如下，從下面的函數(shù)中可以看出最后是通過free_unref_page或者_(dá)_free_pages_ok來實(shí)現(xiàn)的，其余的部分均合法性判斷。

void free_pages(unsigned long addr, unsigned int order)
{
  if (addr != 0) {
    VM_BUG_ON(!virt_addr_valid((void *)addr));
    __free_pages(virt_to_page((void *)addr), order);
  }
}

void __free_pages(struct page *page, unsigned int order)
{
  if (put_page_testzero(page))
    free_the_page(page, order);
}

static inline void free_the_page(struct page *page, unsigned int order)
{
  if (order == 0)   /* Via pcp? */
    free_unref_page(page);
  else
    __free_pages_ok(page, order);
}

函數(shù)free_pages 接受兩個(gè)參數(shù)，分別是虛擬地址和需要釋放的頁(yè)面數(shù)，該函數(shù)內(nèi)部利用virt_to_page把虛擬地址轉(zhuǎn)化成Buddy算法需要的struct page結(jié)構(gòu)體。

__free_pages函數(shù)先將對(duì)應(yīng)的struct page->_refcount 減去1，之后檢測(cè)_refcount是否為0，若為0，繼續(xù)進(jìn)行釋放操作，否則不進(jìn)行內(nèi)存釋放操作。通過該函數(shù)__free_pages可以看到，不管是否進(jìn)行了內(nèi)存釋放操作，該函數(shù)都可以正常退出且沒有返回值。假如內(nèi)存釋放操作異常，就會(huì)引發(fā)內(nèi)存泄漏問題，且代碼中沒有任何日志和錯(cuò)誤碼，這種泄漏通常很難排查。

free_the_page是真正的內(nèi)存釋放函數(shù)，該函數(shù)根據(jù)order的不同，分別進(jìn)行兩種不同的處理：

order為0的情況
order不為0的情況

接下來我們分別來了解這兩種情況的處理方式。

1.order為0的情況

函數(shù)內(nèi)存會(huì)根據(jù)order是否為0來進(jìn)行相應(yīng)的操作，對(duì)于order = 0的情況，此處是調(diào)用函數(shù)free_unref_page。有些內(nèi)核中會(huì)調(diào)用函數(shù)free_hot_cold_page(page, false)來實(shí)現(xiàn)，但不管調(diào)用哪一個(gè)函數(shù)，其內(nèi)部均是進(jìn)行相應(yīng)的判斷后，通過把page插入PCP鏈表相應(yīng)位置處實(shí)現(xiàn)。實(shí)際上內(nèi)核在把內(nèi)存釋放到PCP鏈表時(shí)，會(huì)進(jìn)行PCP鏈表成員個(gè)數(shù)pcp->count的判斷，當(dāng)pcp->count >= pcp->high時(shí)，會(huì)調(diào)用函數(shù)free_pcppages_bulk釋放一部分PCP中的頁(yè)面到 Buddy 子系統(tǒng)中。

此處我們需要注意，并不是所有order = 0的內(nèi)存全部釋放到PCP鏈表中，在結(jié)構(gòu)體struct page中有個(gè)成員index，該成員指明了該部分內(nèi)存的類型，若類型為MIGRATE_ISOLATE，則其內(nèi)存(實(shí)際上是一個(gè)頁(yè)面)會(huì)釋放到Buddy中，若類型對(duì)應(yīng)的數(shù)據(jù)大于或等于MIGRATE_PCPTYPES，則釋放到類型為MIGRATE_MOVABLE的PCP鏈表中，其余的釋放到對(duì)應(yīng)類型的PCP鏈表中。下圖是order = 0時(shí)的核心處理代碼，圖中已經(jīng)標(biāo)注了各個(gè)關(guān)鍵地方，供大家參考。

2.order不為0的情況

當(dāng)order不為0時(shí)，會(huì)通過函數(shù)__free_pages_ok調(diào)用free_one_page來實(shí)現(xiàn)。其核心代碼如下圖所示，圖中對(duì)代碼進(jìn)行了標(biāo)注，從其代碼我們可以發(fā)現(xiàn)其實(shí)現(xiàn)是通過while循環(huán)來查找可以合并的頁(yè)塊，查找的方式就是按照order的次序挨個(gè)查找，其整個(gè)流程就是查找--->確認(rèn)--->刪除--->合并。

此時(shí)，我們來思考一個(gè)問題，有些特殊內(nèi)存區(qū)是無法進(jìn)行合并的，在內(nèi)核代碼中特別表明了如下注釋：

/* If we are here, it means order is >= pageblock_order.
 * We want to prevent merge between freepages on isolate
 * pageblock and normal pageblock. Without this, pageblock
 * isolation could cause incorrect freepage or CMA accounting.
 *
 * We don't want to hit this code for the more frequent
 * low-order merging.
 */

其對(duì)應(yīng)的代碼處理如下圖所示，其代碼主要目的有兩點(diǎn)，其一是保證可以充分地進(jìn)行頁(yè)塊的合并，從而盡量減少內(nèi)存碎片化；其二是保證特殊用途的內(nèi)存塊不受影響。

最后根據(jù)實(shí)際情況，通過函數(shù)list_add(&page->lru, &zone->free_area[order].free_list[migratetype])或者函數(shù)list_add_tail(&page->lru,&zone->free_area[order].free_list[migratetype])把合并后的page添加到對(duì)應(yīng)的鏈表中。

總結(jié)

不同平臺(tái)，不同內(nèi)核版本的系統(tǒng)，在內(nèi)存處理上或許會(huì)存在或多或少的差異，但其核心思想是相同的。通過本文，我們可以詳細(xì)地了解Buddy中內(nèi)存申請(qǐng)和釋放的處理方式，以及當(dāng)內(nèi)存不足時(shí)，Buddy是如何處理的。