linux kernel記憶體碎片防治技術

從buddy申請記憶體頁，如果找不到合適的頁，則會進行兩步調整記憶體的工作，compact和reclaim。前者是為了整合碎片，以得到更大的連續記憶體；後者是回收不一定必須佔用記憶體的緩衝記憶體。這裡重點瞭解comact，整個流程大致如下：

__alloc_pages_nodemask

    -> __alloc_pages_slowpath

        -> __alloc_pages_direct_compact

            -> try_to_compact_pages

                -> compact_zone_order

                    -> compact_zone

                        -> isolate_migratepages

                        -> migrate_pages

                        -> release_freepages

並不是所有申請不到記憶體的場景都會compact，首先要滿足order大於0，並且gfp_mask攜帶__GFP_FS和__GFP_IO；另外，需要zone的剩餘記憶體情況滿足一定條件，kernel稱之為“碎片指數”（fragmentation index），這個值在0~1000之間，預設碎片指數大於500時才能進行compact，可以透過proc檔案extfrag_threshold來調整這個預設值。fragmentation index透過fragmentation_index函式來計算：

1. /*
2.  * Index is between 0 and 1000
3.  *
4.  * 0 => allocation would fail due to lack of memory
5.  * 1000 => allocation would fail due to fragmentation
6.  */
7. return 1000 – div_u64( (1000+(div_u64(info->free_pages * 1000ULL, requested))), info->free_blocks_total)

在整合記憶體碎片的過程中，碎片頁只會在本zone的內部移動，將位於zone低地址的頁儘量移到zone的末端。申請新的頁面位置透過compaction_alloc函式實現。

移動過程又分為同步和非同步，記憶體申請失敗後第一次compact將會使用非同步，後續reclaim之後將會使用同步。同步過程只移動當面未被使用的頁，非同步過程將遍歷並等待所有MOVABLE的頁使用完成後進行移動。

按照可移動性將記憶體頁分為以下三個型別：

UNMOVABLE：在記憶體中位置固定，不能隨意移動。kernel分配的記憶體基本屬於這個型別；

RECLAIMABLE：不能移動，但可以刪除回收。例如檔案對映記憶體；

MOVABLE：可以隨意移動，使用者空間的記憶體基本屬於這個型別。

申請記憶體時，根據可移動性，首先在指定型別的空閑頁中申請記憶體，每個zone的空閑記憶體組織方式如下：

1. struct zone {
2. ……
3. struct free_area    free_area[MAX_ORDER];
4. ……
5. }
6. struct free_area {
7. struct list_head free_list[MIGRATE_TYPES];
8. unsigned long nr_free;
9. };

當在指定型別的free_area申請不到記憶體時，可以從備用型別挪用，挪用之後的記憶體就會釋放到新指定的型別串列中，kernel把這個過程稱為“盜用”。

備用型別優先順序串列如下定義：

1. static int fallbacks[MIGRATE_TYPES][4] = {
2. [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,     MIGRATE_RESERVE },
3. [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,     MIGRATE_RESERVE },
4. #ifdef CONFIG_CMA
5. [MIGRATE_MOVABLE] = { MIGRATE_CMA,         MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },
6. [MIGRATE_CMA] = { MIGRATE_RESERVE }, /* Never used */
7. #else
8. [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE,   MIGRATE_RESERVE },
9. #endif
10. [MIGRATE_RESERVE] = { MIGRATE_RESERVE }, /* Never used */
11. #ifdef CONFIG_MEMORY_ISOLATION
12. [MIGRATE_ISOLATE] = { MIGRATE_RESERVE }, /* Never used */
13. #endif
14. };

值得註意的是並不是所有場景都適合按可移動性組織頁，當記憶體大小不足以分配到各種型別時，就不適合啟用可移動性。有個全域性變數來表示是否啟用，在記憶體初始化時設定：

1. void __ref build_all_zonelists(pg_data_t *pgdat, struct zone *zone)
2. {
3. ……
4. if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES))
5. page_group_by_mobility_disabled = 1;
6. else
7. page_group_by_mobility_disabled = 0;
8. ……
9. }

如果page_group_by_mobility_disabled，則所有記憶體都是不可移動的。其中有個引數決定了每個記憶體區域至少擁有的頁，pageblock_nr_pages，它的定義如下：

#define pageblock_order HUGETLB_PAGE_ORDER

1. #else /* CONFIG_HUGETLB_PAGE */
2. /* If huge pages are not used, group by MAX_ORDER_NR_PAGES */
3. #define pageblock_order (MAX_ORDER–1)
4. #endif /* CONFIG_HUGETLB_PAGE */
5. #define pageblock_nr_pages (1UL << pageblock_order)

在系統初始化期間，所有頁都被標記為MOVABLE：

1. void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
2. unsigned long start_pfn, enum memmap_context context)
3. {
4. ……
5. if ((z->zone_start_pfn <= pfn)
6. && (pfn < zone_end_pfn(z))
7. && !(pfn & (pageblock_nr_pages – 1)))
8. set_pageblock_migratetype(page, MIGRATE_MOVABLE);
9. ……
10. }

其它可移動性型別的頁都是後來產生的，也就是前面說的“盜取”。在這種情況發生時，通常會“盜取”fallback中更高優先順序、更大塊連續的頁，從而避免小碎片的產生。

1. /* Remove an element from the buddy allocator from the fallback list */
2. static inline struct page *
3. __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
4. {
5. ……
6. /* Find the largest possible block of pages in the other list */
7. for (current_order = MAX_ORDER–1; current_order >= order;
8. —current_order) {
9. for (i = 0;; i++) {
10. migratetype = fallbacks[start_migratetype][i];
11. ……
12. }

可以透過/proc/pageteypeinfo檢視當前系統各種型別的頁分佈。