背景

Read the fucking source code! --By 魯迅
A picture is worth a thousand words. --By 高爾基

說明：

Kernel版本：4.14
ARM64處理器，Contex-A53，雙核
使用工具：Source Insight 3.5， Visio

1. 概述

本文將描述memory compaction，記憶體碎片整理技術，
記憶體碎片分為內碎片和外碎片：

內碎片：記憶體頁里邊的碎片；
外碎片：記憶體頁之間的碎片，可能會造成連續物理頁面分配失敗，

memory compaction就是通過將正在使用的可移動頁面遷移到另一個地方以獲得連續的空閑頁面的方法，針對記憶體碎片，內核中定義了migrate_type用于描述遷移型別：

MIGRATE_UNMOVABLE：不可移動，對應于內核分配的頁面；
MIGRATE_MOVABLE：可移動，對應于從用戶空間分配的記憶體或檔案；
MIGRATE_RECLAIMABLE：不可移動，可以進行回收處理；

先來一張memory compaction的概況圖：

上圖對應的是struct page的操作，而針對物理記憶體的操作如下圖所示：

在之前的文章中提到過pageblock，我們看到圖中zone區域是以pageblock為單位上下掃描的，pageblock的大小定義如下（未使用huge table情況下），與Buddy System管理中的最大塊大小一致：

/* If huge pages are not used, group by MAX_ORDER_NR_PAGES */
#define pageblock_order		(MAX_ORDER-1)

#define pageblock_nr_pages	(1UL << pageblock_order)

好了，已經有一個初步印象了，那就進一步的分析吧，

1. 資料結構

1.1 `compact_priority`

/*
 * Determines how hard direct compaction should try to succeed.
 * Lower value means higher priority, analogically to reclaim 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
};

本結構用于描述memory compact的幾種不同方式：

COMPACT_PRIO_SYNC_FULL/MIN_COMPACT_PRIORITY：最高優先級，壓縮和遷移以同步的方式完成；
COMPACT_PRIO_SYNC_LIGHT/MIN_COMPACT_COSTLY_PRIORITY/DEF_COMPACT_PRIORITY：中優先級，壓縮以同步方式處理，遷移以異步方式處理；
COMPACT_PRIO_ASYNC/INIT_COMPACT_PRIORITY：最低優先級，壓縮和遷移以異步方式處理，

1.2 `compact_result`

本結構用于描述壓縮處理函式的回傳值：

/* Return values for compact_zone() and try_to_compact_pages() */
/* When adding new states, please adjust include/trace/events/compaction.h */
enum compact_result {
	/* For more detailed tracepoint output - internal to compaction */
	COMPACT_NOT_SUITABLE_ZONE,
	/*
	 * 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,
};

1.3 `migrate_mode`

本結構用于描述migrate程序中的不同模式，主要針對同步和異步的處理，

/*
 * MIGRATE_ASYNC means never block
 * MIGRATE_SYNC_LIGHT in the current implementation means to allow blocking
 *	on most operations but not ->writepage as the potential stall time
 *	is too significant
 * MIGRATE_SYNC will block when migrating pages
 * MIGRATE_SYNC_NO_COPY will block when migrating pages but will not copy pages
 *	with the CPU. Instead, page copy happens outside the migratepage()
 *	callback and is likely using a DMA engine. See migrate_vma() and HMM
 *	(mm/hmm.c) for users of this mode.
 */
enum migrate_mode {
	MIGRATE_ASYNC,
	MIGRATE_SYNC_LIGHT,
	MIGRATE_SYNC,
	MIGRATE_SYNC_NO_COPY,
};

1.4 `compact_control`

compact_control結構體用于在執行compact的時候，維護兩個掃描器，對應freepages和migratepages，最終將migratepages中的頁拷貝到freepages中去，具體的欄位注釋足夠詳盡，不細說了，

/*
 * compact_control is used to track pages being migrated and the free pages
 * they are being migrated to during memory compaction. The free_pfn starts
 * at the end of a zone and migrate_pfn begins at the start. Movable pages
 * are moved to the end of a zone during a compaction run and the run
 * completes when free_pfn <= migrate_pfn
 */
struct compact_control {
	struct list_head freepages;	/* List of free pages to migrate to */
	struct list_head migratepages;	/* List of pages being migrated */
	struct zone *zone;
	unsigned long nr_freepages;	/* Number of isolated free pages */
	unsigned long nr_migratepages;	/* Number of pages to migrate */
	unsigned long total_migrate_scanned;
	unsigned long total_free_scanned;
	unsigned long free_pfn;		/* isolate_freepages search base */
	unsigned long migrate_pfn;	/* isolate_migratepages search base */
	unsigned long last_migrated_pfn;/* Not yet flushed page being freed */
	const gfp_t gfp_mask;		/* gfp mask of a direct compactor */
	int order;			/* order a direct compactor needs */
	int migratetype;		/* migratetype of direct compactor */
	const unsigned int alloc_flags;	/* alloc flags of a direct compactor */
	const int classzone_idx;	/* zone index of a direct compactor */
	enum migrate_mode mode;		/* Async or sync migration mode */
	bool ignore_skip_hint;		/* Scan blocks even if marked skip */
	bool ignore_block_suitable;	/* Scan blocks considered unsuitable */
	bool direct_compaction;		/* False from kcompactd or /proc/... */
	bool whole_zone;		/* Whole zone should/has been scanned */
	bool contended;			/* Signal lock or sched contention */
	bool finishing_block;		/* Finishing current pageblock */
};

2. 呼叫流程

光看上文的資料結構，會比較零散，看看整體的流程吧，
在內核中，有三種方式來操作memory compact：

在記憶體分配程序中，由于分配請求不能滿足，直接觸發記憶體compact處理；
在沒有足夠記憶體的情況下，kcompactd守護執行緒在后臺喚醒，執行compact處理；
手動觸發，通過echo 1 > /proc/sys/vm/compact_memory來觸發；

圖來了：

實際操作一把：
cat /proc/pagetypeinfo如下圖：

3. `compact`處理

這個處理的程序還是很復雜的，下圖顯示了大概的程序：

下邊將針對各個子模塊更深入點分析，

compaction_suitable

判斷是否執行記憶體的碎片整理，需要滿足以下三個條件：

除去申請的頁面，空閑頁面數將低于水印值，或者雖然大于等于水印值，但是沒有一個足夠大的空閑頁塊；
空閑頁面減去兩倍的申請頁面（兩倍表明有足夠多的的空閑頁面作為遷移目標），高于水印值；
申請的order大于PAGE_ALLOC_COSTLY_ORDER時，計算碎片指數fragindex，根據值來判斷；

isolate_migratepages
isolate_migratepages函式中，遷移掃描器以pageblock為單位，掃描可移動頁，最終把可移動的頁添加到struct compact_control結構中的migratepages鏈表中，如下圖所示：

isolate_freepages的邏輯與isolate_migratepages類似，也是對頁進行隔離處理，最終添加cc->freepages鏈表中，

當空閑掃描器和遷移掃描器完成掃描之后，那就是時候將兩個鏈表中的頁做一下migrate操作了，

migrate_pages

呼叫compact_alloc函式，從cc->freepages鏈表中取出一個空閑頁；
呼叫__unmap_and_move來把可移動頁移動到空閑頁處；
_unmap_and_move函式涉及到反向映射，以及頁快取等，留在以后再深入看，這個函式兩個關鍵作用：1）呼叫try_to_unmap洗掉行程頁表中舊的映射關系，在需要訪問的時候再重新映射到新的物理地址上；2）呼叫move_to_new_page函式將舊頁移動到新的物理頁上，其中在匯編檔案arch/arm64/lib/copy_page.S中copy_page函式完成拷貝，

compact_finished
compact_finished函式主要用于檢查compact是否完成，
compaction_deferred/compaction_defer_reset/defer_compaction
上述這三個函式與記憶體碎片推遲compact有關，這三個函式是在try_to_compact_pages中呼叫，當free pages除去申請頁面數高于水位值，且申請或備用的遷移型別至少有一個足夠大的空閑頁面時，可以認為compact成功，在沒有成功時，可能需要推遲幾次來處理，
struct zone結構中與之有關的欄位如下：

struct zone {
...
	/*
	 * On compaction failure, 1<<compact_defer_shift compactions
	 * are skipped before trying again. The number attempted since
	 * last failure is tracked with compact_considered.
	 */
	unsigned int		compact_considered; //記錄推遲次數
	unsigned int		compact_defer_shift; //（1 << compact_defer_shift）=推遲次數，最大為6
	int			           compact_order_failed; //記錄碎片整理失敗時的申請order值
...
};