作者 | 趙青窕

審校 | 孫淑娟

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

基本概念

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

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

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

水線：每個zone存在三個水線，若當(dāng)前zone中空閑頁高于WMARK_HIGH，則當(dāng)前zone區(qū)的空閑內(nèi)存較多；若空閑頁低于WMARK_LOW，則交換守護(hù)進(jìn)程開始將內(nèi)存交換到磁盤上；若空閑頁低于WMARK_MIN，則內(nèi)存回收系統(tǒng)還需要大量回收內(nèi)存。

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

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

內(nèi)存申請

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

kmalloc_large函數(shù)實(shí)現(xiàn)如下，Buddy算法中，內(nèi)存的分配和釋放均離不開order，我們可以看到，在該函數(shù)內(nèi)部通過size來計算出對應(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會調(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提供的對外申請內(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;
};

各個成員含義如下：

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

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

• 臟頁面判斷

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

• 水位處理

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

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

假如通過水線檢測，發(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í)行下一個循環(huán)操作；若支持，就調(diào)用node_reclaim執(zhí)行內(nèi)存回收的工作。

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

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

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

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

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

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

對于設(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)比較簡單，就是遍歷free_area以便找到合適的內(nèi)存塊，下圖是__rmqueue_smallest的實(shí)現(xiàn)，增加了注釋方便大家理解。

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

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

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

3.慢速分配

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

• 重新計算內(nèi)存分配上下文；
• 如果設(shè)置了__GFP_KSWAPD_RECLAIM，則會調(diào)用函數(shù)wake_all_kswapds來喚醒負(fù)責(zé)換出內(nèi)存頁的守護(hù)進(jìn)程kswapds；
• 因更新了內(nèi)存分配上下文，因此再次使用快速分配嘗試內(nèi)存分配。若分配成功，則退出本次分配；否則繼續(xù)進(jìn)行下一步操作；
• 若申請內(nèi)存時，設(shè)置了__GFP_DIRECT_RECLAIM，且非pfmemalloc情況下，會通過函數(shù)__alloc_pages_direct_compact進(jìn)行內(nèi)存壓縮后，再次嘗試分配頁面。若分配成功則退出；否則進(jìn)入下一步；
• 接下來的操作代碼中采用了retry代碼標(biāo)簽，這個過程比較繁瑣，其本質(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ìn)程后，再分配內(nèi)存；
• 在retry過程中，仍會調(diào)用wake_all_kswapds來喚醒kswapds，防止意外休眠。

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

至此內(nèi)存分配函數(shù)就完成了。從上面的描述可以看出，當(dāng)內(nèi)存足夠時，通常情況下快速分配就足夠了。只有在內(nèi)存不夠時，會進(jìn)行慢速分配，慢速分配里面進(jìn)行內(nèi)存回收，整理等操作后再進(jìn)行分配。若此時還沒有足夠的內(nèi)存可以分配，說明內(nèi)存耗盡，可能是因?yàn)閮?nèi)存泄漏導(dǎo)致內(nèi)存不足，這個時候就需要去定位內(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 接受兩個參數(shù)，分別是虛擬地址和需要釋放的頁面數(shù)，該函數(shù)內(nèi)部利用virt_to_page把虛擬地址轉(zhuǎn)化成Buddy算法需要的struct page結(jié)構(gòu)體。

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

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

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

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

1.order為0的情況

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

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

2.order不為0的情況

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

此時，我們來思考一個問題，有些特殊內(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.
 */

其對應(yīng)的代碼處理如下圖所示，其代碼主要目的有兩點(diǎn)，其一是保證可以充分地進(jìn)行頁塊的合并，從而盡量減少內(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添加到對應(yīng)的鏈表中。

總結(jié)

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

作者介紹

趙青窕，51CTO社區(qū)編輯，從事多年驅(qū)動開發(fā)。研究興趣包含安全OS和網(wǎng)絡(luò)安全領(lǐng)域，發(fā)表過網(wǎng)絡(luò)相關(guān)專利。