頁面遷移其實是伙伴管理算法中的一部分，鑒于其特殊性，特地另行分析。它是2007年的時候，2.6.24內核版本開發時，新增碎片減少策略(the fragmentation reduction strategy)所引入的。該策略也稱之為反碎片技術(anti-gragmentation)。

根據《深入linux內核架構》的描述，反碎片的由來是因為Linux內存管理長期存在一個問題：系統啟動并長期運行后，物理內存將會產生很多碎片。暫且假設內存頁面數為60，則長期運行后，其頁面的使用情況可能將會如下圖(灰色為已分配)。

雖然其未被分配的頁面仍有25%，但能夠申請到的最大頁面僅為一頁。不過這對用戶空間是沒有影響的，主要是由于用戶態的內存是通過頁面映射而得到的。所以不在乎具體的物理頁面分布，其仍是可以將其映射為連續的一塊內存提供給用戶態程序使用。于是用戶態可以感知的內存則如下。

但是對于內核態，碎片則是個嚴肅的問題，因為大部分物理內存都直接映射到內核的永久映射區里面。如果真的存在碎片，將真的如第一張圖所示，無法映射到比一頁更大的內存，這長期是linux的短板之一。于是為了解決該問題，則引入了反碎片。

linux內核在內存管理時，將已分配的頁面劃分為三種類型：

不可移動頁

——該類型頁面在內存中位置固定，不可移動。內核核心大部分內存屬于該類型；

可回收頁

——不能夠直接移動，但是可以刪除，而內容則可以從某些源重新生成。如文件數據映射的頁面則歸屬此類；

可移動頁

——可以隨意移動，分配給用戶態程序運行的用戶空間頁面則為該類。由于是通過頁面映射而得，將其復制到新位置后，更新映射表項，重新映射，應用程序是不感知的。

頁面的可遷移性則取決于它屬于哪一類。而內核使用的反碎片技術則是基于將具有相同可移動性的頁分組的思想來實現的。當出現碎片的情況時，可移動頁面將會遷移，將為申請者騰出所需的連續頁面空間，由此避免了空閑頁面空間過于零碎而無法申請到大塊連續內存。也由此，不可移動頁面不允許在可移動頁面中申請，避免因不可遷移而導致碎片。

其中具體遷移類型在頭文件include/linux/mmzone.h中定義了：

【file:/include/linux/mmzone.h】

enum {

MIGRATE_UNMOVABLE,

MIGRATE_RECLAIMABLE,

MIGRATE_MOVABLE,

MIGRATE_PCPTYPES,/* the number of types on the pcp lists */

MIGRATE_RESERVE = MIGRATE_PCPTYPES,

#ifdef CONFIG_CMA

/*

* MIGRATE_CMA migration type is designed to mimic the way

* ZONE_MOVABLE works. Only movable pages can be allocated

* from MIGRATE_CMA pageblocks and page allocator never

* implicitly change migration type of MIGRATE_CMA pageblock.

*

* The way to use it is to change migratetype of a range of

* pageblocks to MIGRATE_CMA which can be done by

* __free_pageblock_cma() function. What is important though

* is that a range of pageblocks must be aligned to

* MAX_ORDER_NR_PAGES should biggest page be bigger then

* a single pageblock.

*/

MIGRATE_CMA,

#endif

#ifdef CONFIG_MEMORY_ISOLATION

MIGRATE_ISOLATE,/* can't allocate from here */

#endif

MIGRATE_TYPES

};

各類型的說明則為：

MIGRATE_UNMOVABLE

——在內存當中有固定的位置，不能移動。內核的核心分配的內存大多屬于這種類型；

MIGRATE_RECLAIMABLE

——不能直接移動，但可以刪除，其內容頁可以從其他地方重新生成，例如，映射自文件的數據屬于這種類型，針對這種頁，內核有專門的頁面回收處理；

MIGRATE_MOVABLE

——可以隨意移動，用戶空間應用程序所用到的頁屬于該類別。它們通過頁表來映射，如果他們復制到新的位置，頁表項也會相應的更新，應用程序不會注意到任何改變；

MIGRATE_PCPTYPES

——是per_cpu_pageset，即用來表示每CPU頁框高速緩存的數據結構中的鏈表的遷移類型數目；

MIGRATE_RESERVE

——保留頁，是在前三種的列表中都沒用可滿足分配的內存塊時，就可以從MIGRATE_RESERVE分配；

MIGRATE_CMA

——連續內存分配，用于避免預留大塊內存導致系統可用內存減少而實現的，即當驅動不使用內存時，將其分配給用戶使用，而需要時則通過回收或者遷移的方式將內存騰出來。

MIGRATE_ISOLATE

——用于跨越NUMA節點移動物理內存頁，該索引的頁不能分配，在大型系統上，它有益于將物理內存頁移動到接近于是用該頁最頻繁地CPU；

MIGRATE_TYPES

——表示遷移類型的數目。

至于遷移類型的頁面管理實際上采用的還是伙伴管理算法的管理方式，內存管理區zone的結構里面的free_area是用于管理各階內存頁面，而其里面的free_list則是對各遷移類型進行區分的鏈表。回顧內存頁面釋放的函數__free_pages，其將空閑頁面掛回去的時候，是做了遷移類型區分的。也就是意味著頁面遷移類型是伴隨著伙伴管理算法的內存管理構建，根據遷移類型進行分而治之初始化。

那么各種遷移類型的頁面分配是如何運轉的？

頁面分配函數入口__alloc_pages()：

【file:/include/linux/gfp.h】

static inline struct page *

__alloc_pages(gfp_t gfp_mask, unsigned int order,

struct zonelist *zonelist)

{

return __alloc_pages_nodemask(gfp_mask, order, zonelist, NULL);

}

其首入參在__alloc_pages_nodemask()里面會經過allocflags_to_migratetype(gfp_mask)轉換獲取到申請頁面的類型。該遷移類型會在其內部調用函數__rmqueue()中使用。

【file:/mm/page_alloc.c】

/*

* Do the hard work of removing an element from the buddy allocator.

* Call me with the zone->lock already held.

*/

static struct page *__rmqueue(struct zone *zone, unsigned int order,

int migratetype)

{

struct page *page;

retry_reserve:

page = __rmqueue_smallest(zone, order, migratetype);

if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {

page = __rmqueue_fallback(zone, order, migratetype);

/*

* Use MIGRATE_RESERVE rather than fail an allocation. goto

* is used because __rmqueue_smallest is an inline function

* and we want just one call site

*/

if (!page) {

migratetype = MIGRATE_RESERVE;

goto retry_reserve;

}

}

trace_mm_page_alloc_zone_locked(page, order, migratetype);

return page;

}

前面分析可以知道__rmqueue_smallest()僅是在指定遷移類型下自底向上進行各階遍歷查找所需的空閑頁面，而據上代碼其如果在指定遷移類型下分配失敗，且類型不為MIGRATE_RESERVE時，將會調用__rmqueue_fallback()進行分配。

接下來看一下__rmqueue_fallback()實現：

【file:/mm/page_alloc.c】

/* Remove an element from the buddy allocator from the fallback list */

static inline struct page *

__rmqueue_fallback(struct zone *zone, int order, int start_migratetype)

{

struct free_area *area;

int current_order;

struct page *page;

int migratetype, new_type, i;

/* Find the largest possible block of pages in the other list */

for (current_order = MAX_ORDER-1; current_order >= order;

--current_order) {

for (i = 0;; i++) {

migratetype = fallbacks[start_migratetype][i];

/* MIGRATE_RESERVE handled later if necessary */

if (migratetype == MIGRATE_RESERVE)

break;

area = &(zone->free_area[current_order]);

if (list_empty(&area->free_list[migratetype]))

continue;

page = list_entry(area->free_list[migratetype].next,

struct page, lru);

area->nr_free--;

new_type = try_to_steal_freepages(zone, page,

start_migratetype,

migratetype);

/* Remove the page from the freelists */

list_del(&page->lru);

rmv_page_order(page);

expand(zone, page, order, current_order, area,

new_type);

trace_mm_page_alloc_extfrag(page, order, current_order,

start_migratetype, migratetype, new_type);

return page;

}

}

return NULL;

}

可以看到其異于通常的伙伴管理算法，內存頁面是由最高階開始進行查找的，而查找的遷移類型是根據fallbacks備選類型中進行遍歷獲得并止于MIGRATE_RESERVE類型。由此獲得的階號和遷移類型查找zone->free_area[]->free_list[]空閑頁面管理鏈表，如果查找到的話，則將其摘除，否則進入下一類型查找，最后所有類型都查找不到的時候，才會降階查找。

其中fallbacks[][]是已確定的類型順序結構，其定義為：

【file:/mm/page_alloc.c】

/*

* This array describes the order lists are fallen back to when

* the free lists for the desirable migrate type are depleted

*/

static int fallbacks[MIGRATE_TYPES][4] = {

[MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },

[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RESERVE },

#ifdef CONFIG_CMA

[MIGRATE_MOVABLE] = { MIGRATE_CMA, MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },

[MIGRATE_CMA] = { MIGRATE_RESERVE }, /* Never used */

#else

[MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },

#endif

[MIGRATE_RESERVE] = { MIGRATE_RESERVE }, /* Never used */

#ifdef CONFIG_MEMORY_ISOLATION

[MIGRATE_ISOLATE] = { MIGRATE_RESERVE }, /* Never used */

#endif

};

具體分析一下try_to_steal_freepages()函數實現：

【file:/mm/page_alloc.c】

/*

* If breaking a large block of pages, move all free pages to the preferred

* allocation list. If falling back for a reclaimable kernel allocation, be

* more aggressive about taking ownership of free pages.

*

* On the other hand, never change migration type of MIGRATE_CMA pageblocks

* nor move CMA pages to different free lists. We don't want unmovable pages

* to be allocated from MIGRATE_CMA areas.

*

* Returns the new migratetype of the pageblock (or the same old migratetype

* if it was unchanged).

*/

static int try_to_steal_freepages(struct zone *zone, struct page *page,

int start_type, int fallback_type)

{

int current_order = page_order(page);

/*

* When borrowing from MIGRATE_CMA, we need to release the excess

* buddy pages to CMA itself.

*/

if (is_migrate_cma(fallback_type))

return fallback_type;

/* Take ownership for orders >= pageblock_order */

if (current_order >= pageblock_order) {

change_pageblock_range(page, current_order, start_type);

return start_type;

}

if (current_order >= pageblock_order / 2 ||

start_type == MIGRATE_RECLAIMABLE ||

page_group_by_mobility_disabled) {

int pages;

pages = move_freepages_block(zone, page, start_type);

/* Claim the whole block if over half of it is free */

if (pages >= (1 << (pageblock_order-1)) ||

page_group_by_mobility_disabled) {

set_pageblock_migratetype(page, start_type);

return start_type;

}

}

return fallback_type;

}

該函數主要實現了內存頁面的遷移類型的變更，將__rmqueue_fallback()查找到滿足需要的內存頁面空間類型轉為申請的類型。其中MIGRATE_CMA類型不做類型轉換，此外類型轉換的頁面數量為pageblock_nr_pages為單位的倍數，還有就是對于階較低的內存頁面(小于pageblock_order/2)、類型不為MIGRATE_RECLAIMABLE且未開啟頁面遷移的情況下，是不做類型轉換的。完了，在__rmqueue_fallback()里面根據其轉換后的類型通過expand()擴展到對應的遷移類型伙伴管理系統中。

小結一下，__rmqueue_fallback()是自高往低階遍歷fallbacks遷移類型表，查找滿足分配需要的內存頁面，然后將查找到的內存頁面進行類型變更后合并到所申請的類型中，以實現類型遷移。值得注意的是，之所以內存遷移都是以內存塊的高階進行的，主要就是為了反碎片化，避免當前類型無法滿足需要的時候，過于頻繁地向備選類型進行小片內存申請和做遷移而導致備選類型的內存頁面產生大量水平，將問題控制在所申請的內存類型中。

最后看一下set_pageblock_migratetype()的實現：

【file:/mm/page_alloc.c】

/**

* set_pageblock_flags_mask - Set the requested group of flags for a pageblock_nr_pages block of pages

* @page: The page within the block of interest

* @start_bitidx: The first bit of interest

* @end_bitidx: The last bit of interest

* @flags: The flags to set

*/

void set_pageblock_flags_mask(struct page *page, unsigned long flags,

unsigned long end_bitidx,

unsigned long mask)

{

struct zone *zone;

unsigned long *bitmap;

unsigned long pfn, bitidx, word_bitidx;

unsigned long old_word, word;

BUILD_BUG_ON(NR_PAGEBLOCK_BITS != 4);

zone = page_zone(page);

pfn = page_to_pfn(page);

bitmap = get_pageblock_bitmap(zone, pfn);

bitidx = pfn_to_bitidx(zone, pfn);

word_bitidx = bitidx / BITS_PER_LONG;

bitidx &= (BITS_PER_LONG-1);

VM_BUG_ON_PAGE(!zone_spans_pfn(zone, pfn), page);

bitidx += end_bitidx;

mask <<= (BITS_PER_LONG - bitidx - 1);

flags <<= (BITS_PER_LONG - bitidx - 1);

word = ACCESS_ONCE(bitmap[word_bitidx]);

for (;;) {

old_word = cmpxchg(&bitmap[word_bitidx], word, (word & ~mask) | flags);

if (word == old_word)

break;

word = old_word;

}

}

其中get_pageblock_bitmap()用于取得zone結構體中pageblock_flags成員，而后面則是基于此做位圖操作。通過該函數，可以看到內存頁面的類型管理是通過其所屬的zone的結構體中的pageblock_flags所管理的位圖進行標識該頁面的遷移類型。