[[410691]]

一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內核愛好者,就職于杭州某大型安防公司，擔任Linux BSP軟件工程師。對進程調度，內存管理有所了解。希望能通過對linux的學習，提升產品軟件性能及穩定性。該文章為私人學習總結，不存在公司網絡安全問題。       

本文轉載自微信公眾號「Linux閱碼場」，可以通過以下二維碼關注。轉載本文請聯系Linux閱碼場公眾號。