memory compaction 原理、實現與分析
作者簡介
趙金生，linux 內核愛好者, 就職於杭州某大型安防公司，擔任 Linux BSP 軟件工程師。對進程調度，內存管理有所瞭解。希望能通過對 linux 的學習，提升產品軟件性能及穩定性。該文章爲私人學習總結，不存在公司網絡安全問題。
一
memory compaction 簡介
隨着系統的運行，經過不同用戶的分配請求後，頁框會變得十分分散，導致此段頁框被這些正在使用的零散頁框分爲一小段一小段非連續頁框，這使得在需要分配內存時很難找到物理上連續的頁框。
現代處理器不再限於使用傳統的 4K 大小的頁框；它們可以在進程的部分地址空間中支持大得多的頁 (huge pages)。使用巨頁會帶來真正的性能優勢，主要原因是減小了對處理器的轉換後備緩衝區（translation lookaside buffer）的壓力。但是使用巨頁要求系統能夠找到物理上連續的內存區域，這些區域不僅要足夠大，而且還必須確保按適當方式滿足字節對齊的要求。
在一個已經運行了一段時間的系統上會產生大量的不連續的 page， 要想找到符合這些高階 (high-order) 條件的內存空間非常具有挑戰性，memory compaction 的作用就是解決 high-order 內存分配失敗問題，與 buddy system 機制做一個互補。
二
memory compaction 原理
內存碎片整理以 pageblock 爲單位。
在內存碎片整理開始前，會在 zone 的頭和尾各設置一個指針，頭指針從頭向尾掃描可移動的頁，而尾指針從尾向頭掃描空閒的頁，當他們相遇時終止整理。
簡單示意圖：需要明確的是：實際情況並不是與圖示的情況完全一致。頭指針每次掃描一個符合要求的 pageblock 裏的所有頁框，當 pageblock 不爲 MIGRATE_MOVABLE、MIGRATE_CMA、MIGRATE_RECLAIMABLE 時會跳過這些 pageblock，當掃描完這個 pageblock 後有可移動的頁框時，會變爲尾指針以 pageblock 爲單位向前掃描可移動頁框數量的空閒頁框，但是在 pageblock 中也是從開始頁框向結束頁框進行掃描，最後會將前面的頁框內容複製到這些空閒頁框中。
這裏的移動是將頁框中的數據 copy 拷貝到可移動的空閒頁框當中，此時原有的 movable page 變成 free page。所以並不是頁框自身的移動而是數據的移動。
通過下圖的操作就可以分配出一個 order = 2 或者是 order = 3 的連續的可用空間，可用於滿足更 high-order 的內存分配。當然，這裏展示的流程和真實系統比起來已經大大簡化了。實際的內存域會大得多，這意味着掃描的工作量也會大很多，但由此獲得的空閒區也可能更大。
實際的內存碎片，還有一個問題就是在整理算法中會將掃描中識別爲不滿足整理要求的內存塊標識爲 “可忽略”(“skip”，即不執行規整)。作爲一種優化，目的是防止運行沒必要的規整操作。
比如系統正在對 zone 進行內存碎片整理，首先，會從可移動頁框開始位置向後掃描一個 pageblock，得到一些可移動頁框，然後空閒頁框從開始位置向前掃描一個 pageblock，得到一些空閒頁框，然後將可移動頁框移動到空閒頁框中，之後再繼續循環掃描。對一個 pageblock 進行掃描後，如果無法從此 pageblock 隔離出一個要求的頁框，這時候就會將此 pageblock 標記爲跳過 (skip)。
假設內存碎片整理可移動頁掃描是從 zone 的第一個頁框開始，掃描完一個 pageblock 後，沒有隔離出可移動頁框，則標記此 pageblock 的跳過標記 PB_migrate_skip，然後將 zone->compact_cached_migrate_pfn 設置爲此 pageblock 的結束頁框。
這樣，在下次對此 zone 進行內存碎片整理時，就會直接從此 pageblock 的下一個 pageblock 開始，把此 pageblock 跳過了。同理，對於空閒頁掃描也是一樣。這樣就必須更新 zone pageblock 的起始地址與結束地址：
以上就是內存碎片整理的基本原理了。
三
memory compaction 如何實現
3.1、數據結構
在內存碎片整理中，可以移動的頁框有 MIGRATE_RECLAIMABLE、MIGRATE_MOVABLE 與 MIGRATE_CMA 這三種類型的頁框。
而因爲內存碎片整理分爲同步和異步。在異步過程中，只會移動 MIGRATE_MOVABLE 和 MIGRATE_CMA 這兩種類型的頁框。因爲這兩種類型的頁框處理，是不會涉及到 IO 操作的。而在同步過程中，這三種類型的頁框都會進行移動，因爲 MIGRATE_RECLAIMABLE 基本上都是文件頁，在移動過程中，有可能要將髒頁回寫，會涉及到 IO 操作，也就是在同步過程中，是會涉及到 IO 操作的。
1、migrate_mode 遷移模式：
enum migrate_mode {
MIGRATE_ASYNC,
MIGRATE_SYNC_LIGHT,
MIGRATE_SYNC,
};2、compact_priority
enum compact_priority {
COMPACT_PRIO_SYNC_FULL,
MIN_COMPACT_PRIORITY = COMPACT_PRIO_SYNC_FULL,
COMPACT_PRIO_SYNC_LIGHT,
MIN_COMPACT_COSTLY_PRIORITY = COMPACT_PRIO_SYNC_LIGHT,
DEF_COMPACT_PRIORITY = COMPACT_PRIO_SYNC_LIGHT,
COMPACT_PRIO_ASYNC,
INIT_COMPACT_PRIORITY = COMPACT_PRIO_ASYNC
};3、compact_result 用於壓縮處理函數的返回值
enum compact_result {
/* For more detailed tracepoint output - internal to compaction */
COMPACT_NOT_SUITABLE_ZONE,//trace用於調試輸出或內部使用
/*
* compaction didn't start as it was not possible or direct reclaim
* was more suitable
*/
COMPACT_SKIPPED,//跳過壓縮，因爲無法執行壓縮或直接回收更合適
/* compaction didn't start as it was deferred due to past failures */
COMPACT_DEFERRED,
/* compaction not active last round */
COMPACT_INACTIVE = COMPACT_DEFERRED,
/* For more detailed tracepoint output - internal to compaction */
COMPACT_NO_SUITABLE_PAGE,
/* compaction should continue to another pageblock */
COMPACT_CONTINUE,
/*
* The full zone was compacted scanned but wasn't successfull to compact
* suitable pages.
*/
COMPACT_COMPLETE,//已完成所有區域的壓縮，但是尚未確保可以通過壓縮分配的頁面
/*
* direct compaction has scanned part of the zone but wasn't successfull
* to compact suitable pages.
*/
COMPACT_PARTIAL_SKIPPED,
/* compaction terminated prematurely due to lock contentions */
COMPACT_CONTENDED,
/*
* direct compaction terminated after concluding that the allocation
* should now succeed
*/
COMPACT_SUCCESS,//在確保可分配頁面安全後，直接壓縮結束
};4、compact_control 需要進行內存碎片整理時，總是需要初始化該結構體
struct compact_control {
/* 掃描到的空閒頁的頁的鏈表 */
struct list_head freepages; /* List of free pages to migrate to */
/* 掃描到的可移動的頁的鏈表 */
struct list_head migratepages; /* List of pages being migrated */
/* 空閒頁鏈表中的頁數量 */
unsigned long nr_freepages; /* Number of isolated free pages */
/* 可移動頁鏈表中的頁數量 */
unsigned long nr_migratepages; /* Number of pages to migrate */
/* 空閒頁框掃描所在頁框號 */
unsigned long free_pfn; /* isolate_freepages search base */
/* 可移動頁框掃描所在頁框號 */
unsigned long migrate_pfn; /* isolate_migratepages search base */
/* 內存碎片整理使用的模式: 同步，輕同步，異步 */
enum migrate_mode mode; /* Async or sync migration mode */
/* 是否忽略pageblock的PB_migrate_skip標誌對需要跳過的pageblock進行掃描 ，並且也不會對pageblock設置跳過
* 只有兩種情況會使用
* 1.調用alloc_contig_range()嘗試分配一段指定了開始頁框號和結束頁框號的連續頁框時；
* 2.通過寫入1到sysfs中的/vm/compact_memory文件手動實現同步內存碎片整理。
*/
bool ignore_skip_hint; /* Scan blocks even if marked skip */
/* 本次內存碎片整理是否隔離到了空閒頁框，會影響zone的空閒頁掃描起始位置 */
bool finished_update_free; /* True when the zone cached pfns are
* no longer being updated
*/
/* 本次內存碎片整理是否隔離到了可移動頁框，會影響zone的可移動頁掃描起始位置 */
bool finished_update_migrate;
/* 申請內存時需要的頁框的order值 */
int order; /* order a direct compactor needs */
const gfp_t gfp_mask; /* gfp mask of a direct compactor */
/* 掃描的管理區 */
struct zone *zone;
/* 保存結果，比如異步模式下是否因爲需要阻塞而結束了本次內存碎片整理 */
int contended; /* Signal need_sched() or lock
* contention detected during
* compaction
*/
};5、Node zone 掃描推遲
struct zone
{
.....
unsigned int compact_considered;
unsigned int compact_defer_shift;
int compact_order_failed;
......
}當一個 zone 要進行內存碎片整理時，首先會判斷本次整理需不需要推遲，如果本次內存碎片整理使用的 order 值小於 zone 內存碎片整理失敗最大 order 值 compact_order_failed 時，不用進行推遲，可以直接進行內存碎片整理；
當 order 值大於 zone 內存碎片整理失敗最大 order 值 compact_order_failed，會增加內存碎片整理推遲計數器 compact_considered，如果內存碎片整理推遲計數器 compact_considered 未達到內存碎片整理推遲閥值 defer_limit，則會跳過本次內存碎片整理，如果達到了，那就需要進行內存碎片整理。
總結：也就是當 order 小於 zone 內存碎片整理失敗最大 order 值時，不用進行推遲，而 order 大於 zone 內存碎片整理失敗最大 order 值時，才考慮是否進行推遲, 此時推遲就是 continue 掃描 node 當中的下一個 zone 區域，這裏並不是想下文一下設置 zone SKIP 標誌。
6、Pageblock skip
struct zone
{
......
unsigned long compact_cached_free_pfn;
/* pfn where async and sync compaction migration scanner should start */
unsigned long compact_cached_migrate_pfn[2];
......
}3.2、源碼分析
內存碎片整理移動發生條件：
-
內存分配不足時觸發 direct compact 整理內存
-
Kswapd 內存回收後喚醒 kcompactd 內核線程執行 compact 操作，獲取連續內存
-
手動設置 echo 1 > /proc/sys/vm/compact_memory
分析的重點就放在內存分配不足的情況，入口函數從 try_to_compact_pages 開始
對源碼詳細分析參見代碼：https://github.com/linuxzjs/linux-4.14
重點分析 5 個關鍵函數：
1、compaction_suitable
/* 判斷該zone是否可以做內存碎片壓縮整理 */
enum compact_result compaction_suitable(struct zone *zone, int order,
unsigned int alloc_flags,
int classzone_idx)
{
enum compact_result ret;
int fragindex;
/*
* 根據watermask判斷zone中離散的page是否滿足2^order的內存分配請求，如果滿足則繼續對zone進行內存的compact整理zone的內存碎片
* 說明該zone時可以做內存碎片的壓縮整理的。
*/
ret = __compaction_suitable(zone, order, alloc_flags, classzone_idx,zone_page_state(zone, NR_FREE_PAGES));
/* 如果return返回值爲COMPACT_CONTINUE，且order > PAGE_ALLOC_COSTLY_ORDER(3)則進入一下判斷當中 */
if (ret == COMPACT_CONTINUE && (order > PAGE_ALLOC_COSTLY_ORDER)) {
/*
* 爲了確定zone區域是否執行壓縮，找到所請求區域zone和順序的碎片係數。
* 如果碎片係數值返回-1000，則存在要分配的頁面，因此不需要壓縮。
* 在其他情況下，該值在0到500的範圍內，並且如果它小於sysctl_extfrag_threshold，則直接return COMPACT_NOT_SUITABLE_ZONE不執行壓縮
*/
fragindex = fragmentation_index(zone, order);
if (fragindex >= 0 && fragindex <= sysctl_extfrag_threshold)
ret = COMPACT_NOT_SUITABLE_ZONE;
}
.....
return ret;
}由此可以知道，判斷是否執行內存的碎片整理，需要滿足以下三個條件：在__compaction_suitable 當中可以得出：
-
減去申請的頁面，空閒頁面數將低於水印值；或者雖然大於等於水印值，但是沒有一個足夠大的連續的空閒頁塊；
-
空閒頁面減去兩倍的申請頁面，高於水印值；在 fragmentation_index 中：
-
申請的 order 大於 PAGE_ALLOC_COSTLY_ORDER 時，計算碎片指數 fragindex 來判斷；
2、compact_finished
通過該函數判斷 zone 區域碎片整理 compact 是否完成
static enum compact_result __compact_finished(struct zone *zone,struct compact_control *cc)
{
unsigned int order;
/* 獲取zone的移動類型 */
const int migratetype = cc->migratetype;
.....
/* Compaction run completes if the migrate and free scanner meet */
/* 當cc->free_pfn <= cc->migrate_pfn空閒掃描於可移動頁面掃描相遇則說明zone碎片掃描壓縮完成 */
if (compact_scanners_met(cc)) {
/* Let the next compaction start anew. */
/* 重置壓縮掃描起始地址於結束地址的位置 */
reset_cached_positions(zone);
/* 如果是直接壓縮模式則設置compact_blockskip_flush = true，清除PG_migrate_skip的skip屬性 */
if (cc->direct_compaction)
zone->compact_blockskip_flush = true;
/*
* 如果whole_zone = 1說明zone是從頭開始掃描，掃描zone整個區域 return COMPACT_COMPLETE，表示zone掃描完成
* 如果whole_zone = 0說明zone是從局部開始掃描的，也就是在zone的更新的free_page或者是migrate_page當中掃描
* 也就是也就是局部的pageblock的掃描，return COMPACT_PARTIAL_SKIPPED表示跳過該pageblock，掃描下一個pageblock
*/
if (cc->whole_zone)
return COMPACT_COMPLETE;
else
return COMPACT_PARTIAL_SKIPPED;
}
/* 執行壓縮時，將返回COMPACT_CONTINUE以強制壓縮整個塊，這個於手動模式有關
* echo 1> /proc/sys/vm/compact_memory
*/
if (is_via_compact_memory(cc->order))
return COMPACT_CONTINUE;
/* 如果掃描完成，則進入判斷當中，做進一步判斷驗證 */
if (cc->finishing_block) {
/* 再次檢查遷移掃描程序與pageblock是否對齊，如果對齊則說明頁面壓縮已經完成重置cc->finishing_block = false
* 如果沒有對齊則，並返回COMPACT_CONTINUE以繼續掃描進行zone的頁面掃描壓縮操作
*/
if (IS_ALIGNED(cc->migrate_pfn, pageblock_nr_pages))
cc->finishing_block = false;
else
return COMPACT_CONTINUE;
}
/* Direct compactor: Is a suitable page free? */
/*
* 從當前order開始掃描，order -> MAX_ORDER進行，
*/
for (order = cc->order; order < MAX_ORDER; order++) {
/* 根據order獲取free_area */
struct free_area *area = &zone->free_area[order];
bool can_steal;
/* Job done if page is free of the right migratetype */
/* 如果該area->free_list[migratetype])不爲NULL，不爲空則COMPACT_SUCCESS壓縮掃描成功 */
if (!list_empty(&area->free_list[migratetype]))
return COMPACT_SUCCESS;
/* 如果定義了CONFIG_CMA如果移動類型爲MIGRATE_MOVABLE可移動類型，且area->free_list[MIGRATE_CMA])不爲空則return COMPACT_SUCCESS */
#ifdef CONFIG_CMA
/* MIGRATE_MOVABLE can fallback on MIGRATE_CMA */
if (migratetype == MIGRATE_MOVABLE &&
!list_empty(&area->free_list[MIGRATE_CMA]))
return COMPACT_SUCCESS;
#endif
/* 如果area->free_list[migratetype]以及area->free_list[MIGRATE_CMA])均爲空則取對應的migratetype的fallback當中尋找合適可用的page
* 判斷是否能夠完成頁面的壓縮。
*/
if (find_suitable_fallback(area, order, migratetype,
true, &can_steal) != -1) {
/* movable pages are OK in any pageblock */
/* 如果可移動類型爲MIGRATE_MOVABLE則直接return COMPACT_SUCESS
* 說明只要是可以移動的page都可用作頁面壓縮功能。
*/
if (migratetype == MIGRATE_MOVABLE)
return COMPACT_SUCCESS;
/* 如果正在執行aync異步壓縮，或者如果遷移掃描程序已完成一頁代碼塊，則返回COMPACT_SUCCESS */
if (cc->mode == MIGRATE_ASYNC ||
IS_ALIGNED(cc->migrate_pfn,
pageblock_nr_pages)) {
return COMPACT_SUCCESS;
}
/* 如果fallback當中沒有找到合適可用的page則設置cc->finishing_block = true;return COMPACT_CONTINUE zone還需要繼續掃描，
* skip到下一個pageblock或者是下一個zone
*/
cc->finishing_block = true;
return COMPACT_CONTINUE;
}
}
/* 如果從order -> max_order都沒有找到可用的page用作直接的頁面遷移壓縮則return COMPACT_NO_SUITABLE_PAGE表明沒有可用的頁面用於壓縮 */
return COMPACT_NO_SUITABLE_PAGE;
}3、isolate_migratepages
在 zone 當中以 pageblock 爲單位，掃描找到 migratepage 可移動頁，並將 page 添加 struct compact_control *cc 的 migratepages 鏈表當中，便於後邊做頁面內容的拷貝移動。其實隔離的作用就是將可移動頁面拿出來，單獨存放，與之前的 pageblock 分開
4、isolate_freepages
freepages 的過程與 migratepages 的過程基本上是完全一致的，隔離結束的條件基本上也是一致的。
不同點就是 freepage 在找到 pageblock 的 page 進行 isolate 隔離操作前會判斷這個 page 是如何組成的，是一個複合 page 還是非複合頁，如果不是要獲取這個 page 的 order，如果該 page 是由 2^order 個單獨的 page 組合起來的還要將這個 page 拆分成單獨的 page 也就是 order = 0 的這種情況，然後將單獨的 page 移動到 freepages 鏈表上，並設置 page 新的類型爲 MIGRATE_MOVABLE 供後續使用。
5、migrate_pages
當完成 freepages、migratepages 完成隔離後就調 migrate_pages 完成兩個鏈表的頁面遷移。
err = migrate_pages(&cc->migratepages, compaction_alloc,
compaction_free, (unsigned long)cc, cc->mode,
MR_COMPACTION);compact_alloc 函數，從 zone 區域當中掃描 freepages 並提填充到 cc->freepages 鏈表當中，再從 cc->freepages 鏈表中取出一個空閒頁
static struct page *compaction_alloc(struct page *migratepage,
unsigned long data, int **result)
{
struct compact_control *cc = (struct compact_control *)data;
struct page *freepage;
/*
* Isolate free pages if necessary, and if we are not aborting due to
* contention.
*/
/* 如果cc中的空閒頁框鏈表爲空 */
if (list_empty(&cc->freepages)) {
if (!cc->contended)
isolate_freepages(cc);/* 從cc->free_pfn開始向前獲取空閒頁 */
if (list_empty(&cc->freepages))
return NULL;
}
/* 從cc->freepages鏈表取出一個空閒的freepages */
freepage = list_entry(cc->freepages.next, struct page, lru);
/* 將該page從lru鏈表當中刪除 */
list_del(&freepage->lru);
cc->nr_freepages--;
/* 返回空閒頁框 */
return freepage;
}
static void compaction_free(struct page *page, unsigned long data)
{
struct compact_control *cc = (struct compact_control *)data;
list_add(&page->lru, &cc->freepages);
cc->nr_freepages++;
}這裏先避開 PageHuge 不談，migrate_pages 通過調用 unmap_and_move、__unmap_and_move、move_to_new_page、try_to_unmap 完成頁面最終的整理工作。這裏面涉及的 rmap 反向映射這裏不再展開。
四
memory compaction 總結
分析過 reclaim 內存回收代碼就會發現，在內存回收當中同樣會 wakeup_kcompactd 觸發 compaction 碎片整理機制，在 kswpad 異步內存回收當中存在同樣的操作。同時與 kswapd 機制類似目前內核在 node 節點當中也引入了 kcompactd 線程機制，定時的休眠喚醒該內核線程完成內存碎片的整理，在新的 patch 當中更是將 kswapd 與 kcompactd 結合起來共同完成內存碎片的整理。內存回收工作。(END)
更多精彩，盡在 "Linux 閱碼場"
參考資料：
https://lwn.net/Articles/368869/
https://lwn.net/Articles/157066/
https://lwn.net/Articles/817905/
https://lore.kernel.org/patchwork/patch/575291/
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/uH8yOqPYQWJf0eJl12zI2Q