我們知道物理內(nèi)存是以頁為單位進行管理的，每個內(nèi)存頁大小默認是4K（大頁除外）。申請物理內(nèi)存時，一般都是按順序分配的，但釋放內(nèi)存的行為是隨機的。隨著系統(tǒng)運行時間變長后，將會出現(xiàn)以下情況：

如上圖所示，當用戶需要申請地址連續(xù)的 3 個內(nèi)存頁時，雖然系統(tǒng)中空閑的內(nèi)存頁數(shù)量足夠，但由于空閑的內(nèi)存頁相對分散，從而導致分配失敗。這些地址不連續(xù)的內(nèi)存頁被稱為：內(nèi)存碎片。

要解決這個問題也比較簡單，只需要把空閑的內(nèi)存塊移動到一起即可。如下圖所示：

網(wǎng)絡上有句很有名的話：理想很美好，現(xiàn)實很骨感。

內(nèi)存整理也是這樣，看起來很簡單，但實現(xiàn)起來就不那么簡單了。因為在內(nèi)存整理后，需要修正進程的虛擬內(nèi)存與物理內(nèi)存之間的映射關系。如下圖所示：

但由于 Linux 內(nèi)核有個名為?內(nèi)存頁反向映射?的功能，所以內(nèi)存整理就變得簡單起來。

接下來，我們將會分析內(nèi)存碎片整理的原理與實現(xiàn)。

內(nèi)存碎片整理原理

內(nèi)存碎片整理的原理比較簡單：在內(nèi)存碎片整理開始前，會在內(nèi)存區(qū)的頭和尾各設置一個指針，頭指針從頭向尾掃描可移動的頁，而尾指針從尾向頭掃描空閑的頁，當他們相遇時終止整理。下面說說內(nèi)存隨便整理的過程（原理參考了內(nèi)核文檔）：

初始時內(nèi)存狀態(tài)：

在上圖中，白色塊表示空閑的內(nèi)存頁，而紅色塊表示已分配出去的內(nèi)存頁。在初始狀態(tài)時，內(nèi)存中存在多個碎片。如果此時要申請 3 個地址連續(xù)的內(nèi)存頁，那么將會申請失敗。

內(nèi)存碎片整理掃描開始：

頭部指針從頭掃描可移動頁，而尾部指針從從尾掃描空閑頁。在整理時，將可移動頁的內(nèi)容復制到空閑頁中。復制完成后，將可移動內(nèi)存頁釋放即可。

最后結(jié)果：

經(jīng)過內(nèi)存碎片整理后，如果現(xiàn)在要申請 3 個地址連續(xù)的內(nèi)存頁，就能申請成功了。

內(nèi)存碎片整理實現(xiàn)

接下來，我們將會分析內(nèi)存碎片整理的實現(xiàn)過程。

注：本文使用的是 Linux-2.6.36 版本的內(nèi)存

1. 內(nèi)存碎片整理時機

當要申請多個地址聯(lián)系的內(nèi)存頁時，如果申請失敗，將會進行內(nèi)存碎片整理。其調(diào)用鏈如下：

alloc_pages_node()
└→?__alloc_pages()
???└→?__alloc_pages_nodemask()
??????└→?__alloc_pages_slowpath()
?????????└→?__alloc_pages_direct_compact()

當調(diào)用?alloc_pages_node()?函數(shù)申請多個地址連續(xù)的內(nèi)存頁失敗時，將會觸發(fā)調(diào)用?__alloc_pages_direct_compact()?函數(shù)來進行內(nèi)存碎片整理。我們來看看?__alloc_pages_direct_compact()?函數(shù)的實現(xiàn)：

static?struct?page?*
__alloc_pages_direct_compact(gfp_t?gfp_mask,?
?????????????????????????????unsigned?int?order,?
?????????????????????????????struct?zonelist?*zonelist,?
?????????????????????????????enum?zone_type?high_zoneidx,?
?????????????????????????????nodemask_t?*nodemask,?
?????????????????????????????int?alloc_flags,
?????????????????????????????struct?zone?*preferred_zone,
?????????????????????????????int?migratetype,?
?????????????????????????????unsigned?long?*did_some_progress)
{
????struct?page?*page;

????//?1.?如果申請一個內(nèi)存頁，那么就沒有整理碎片的必要（這說明是內(nèi)存不足，而不是內(nèi)存碎片導致）
????if?(!order?||?compaction_deferred(preferred_zone))
????????return?NULL;

????//?2.?開始進行內(nèi)存碎片整理
????*did_some_progress?=?try_to_compact_pages(zonelist,?order,?gfp_mask,?nodemask);

????if?(*did_some_progress?!=?COMPACT_SKIPPED)?{
????????...
????????//?3.?整理完內(nèi)存碎片后，繼續(xù)嘗試申請內(nèi)存塊
????????page?=?get_page_from_freelist(gfp_mask,?nodemask,?order,?zonelist,?
??????????????????????????????????????high_zoneidx,?alloc_flags,?preferred_zone,?
??????????????????????????????????????migratetype);
????????if?(page)?{
????????????...
????????????return?page;
????????}
????????...
????}

????return?NULL;
}

__alloc_pages_direct_compact()?函數(shù)是內(nèi)存碎片整理的入口，其主要完成 3 個步驟：

先判斷申請的內(nèi)存塊是否只有一個內(nèi)存頁，如果是，那么就沒有整理碎片的必要（這說明是內(nèi)存不足，而不是內(nèi)存碎片導致）。

如果需要進行內(nèi)存碎片整理，那么調(diào)用?try_to_compact_pages()?函數(shù)進行內(nèi)存碎片整理。

整理完內(nèi)存碎片后，調(diào)用?get_page_from_freelist()?函數(shù)繼續(xù)嘗試申請內(nèi)存塊。

2. 內(nèi)存碎片整理過程

由于內(nèi)存碎片整理的具體實現(xiàn)在?try_to_compact_pages()?函數(shù)中進行，所以我們繼續(xù)來看看?try_to_compact_pages()?函數(shù)的實現(xiàn)：

unsigned?long
try_to_compact_pages(struct?zonelist?*zonelist,?int?order,?gfp_t?gfp_mask,
?????????????????????nodemask_t?*nodemask)
{
????...
????//?1.?遍歷所有內(nèi)存區(qū)（由于內(nèi)核會把物理內(nèi)存分成多個內(nèi)存區(qū)進行管理）
????for_each_zone_zonelist_nodemask(zone,?z,?zonelist,?high_zoneidx,?nodemask)?{
????????...
????????//?2.?對內(nèi)存區(qū)進行內(nèi)存碎片整理
????????status?=?compact_zone_order(zone,?order,?gfp_mask);
????????...
????}

????return?rc;
}

可以看出，try_to_compact_pages()?函數(shù)最終會調(diào)用?compact_zone_order()?函數(shù)來進行內(nèi)存碎片整理。我們只能進行來分析?compact_zone_order()?函數(shù)：

static?unsigned?long
compact_zone_order(struct?zone?*zone,?int?order,?gfp_t?gfp_mask)
{
????struct?compact_control?cc?=?{
????????.nr_freepages?=?0,
????????.nr_migratepages?=?0,
????????.order?=?order,
????????.migratetype?=?allocflags_to_migratetype(gfp_mask),
????????.zone?=?zone,
????};
????INIT_LIST_HEAD(&cc.freepages);
????INIT_LIST_HEAD(&cc.migratepages);

????return?compact_zone(zone,?&cc);
}

到這里，我們還沒有看到內(nèi)存碎片整理的具體實現(xiàn)（調(diào)用鏈可真深啊 ^_^！），compact_zone_order()?函數(shù)也是構(gòu)造了一些參數(shù)，然后繼續(xù)調(diào)用?compact_zone()?來進行內(nèi)存碎片整理：

static?int?compact_zone(struct?zone?*zone,?struct?compact_control?*cc)
{
????...
????while?((ret?=?compact_finished(zone,?cc))?==?COMPACT_CONTINUE)?{
????????...
????????//?1.?收集可移動的內(nèi)存頁列表
????????if?(!isolate_migratepages(zone,?cc))
????????????continue;
????????...
????????//?2.?將可移動的內(nèi)存頁列表遷移到空閑列表中
????????migrate_pages(&cc->migratepages,?compaction_alloc,?(unsigned?long)cc,?0);
????????...
????}
????...
????return?ret;
}

在?compact_zone()?函數(shù)里，我們終于看到內(nèi)存碎片整理的邏輯了。compact_zone()?函數(shù)主要完成 2 個步驟：

調(diào)用?isolate_migratepages()?函數(shù)收集可移動的內(nèi)存頁列表。

調(diào)用?migrate_pages()?函數(shù)將可移動的內(nèi)存頁列表遷移到空閑列表中。

這兩個函數(shù)非常重要，我們分別來分析它們是怎么實現(xiàn)的。

isolate_migratepages() 函數(shù)

isolate_migratepages()?函數(shù)用于收集可移動的內(nèi)存頁列表，我們來看看其實現(xiàn)：

static?unsigned?long
isolate_migratepages(struct?zone?*zone,?struct?compact_control?*cc)
{
????unsigned?long?low_pfn,?end_pfn;
????struct?list_head?*migratelist?=?&cc->migratepages;
????...

????//?1.?掃描內(nèi)存區(qū)所有的內(nèi)存頁
????for?(;?low_pfn?lru,?migratelist);?
????????...
????????cc->nr_migratepages++;
????????...
????}
????...
????return?cc->nr_migratepages;
}

isolate_migratepages()?函數(shù)主要完成 5 個步驟，分別是：

掃描內(nèi)存區(qū)所有的內(nèi)存頁（與內(nèi)存碎片整理原理一致）。

通過內(nèi)存頁的編號獲取內(nèi)存頁對象。

判斷內(nèi)存頁是否可移動內(nèi)存頁，如果不是可移動內(nèi)存頁，那么就跳過。

將內(nèi)存頁從 LRU 隊列中刪除，這樣可避免被其他進程回收這個內(nèi)存頁。

添加到可移動內(nèi)存頁列表中。

當完成這 5 個步驟后，內(nèi)核就收集到可移動的內(nèi)存頁列表。

migrate_pages() 函數(shù)

migrate_pages()?函數(shù)負責將可移動的內(nèi)存頁列表遷移到空閑列表中，我們來分析一下其實現(xiàn)過程：

int?migrate_pages(struct?list_head?*from,?new_page_t?get_new_page,
??????????????????unsigned?long?private,?int?offlining)
{
????...

????for?(pass?=?0;?pass??2,?offlining);
????????????switch(rc)?{
????????????case?-ENOMEM:
????????????????goto?out;
????????????case?-EAGAIN:
????????????????retry++;
????????????????break;
????????????case?0:
????????????????break;
????????????default:
????????????????nr_failed++;
????????????????break;
????????????}
????????}
????}
????...
????return?nr_failed?+?retry;
}

migrate_pages()?函數(shù)的邏輯很簡單，主要完成 2 個步驟：

遍歷可移動內(nèi)存頁列表，這個列表就是通過?isolate_migratepages()?函數(shù)收集的可移動內(nèi)存頁列表。

調(diào)用?unmap_and_move()?函數(shù)將可移動內(nèi)存頁遷移到空閑內(nèi)存頁中。

可以看出，具體的內(nèi)存遷移過程在?unmap_and_move()?函數(shù)中實現(xiàn)。我們來看看?unmap_and_move()?函數(shù)的實現(xiàn)：

static?int
unmap_and_move(new_page_t?get_new_page,?unsigned?long?private,
???????????????struct?page?*page,?int?force,?int?offlining)
{
????...
????//?1.?從內(nèi)存區(qū)中找到一個空閑的內(nèi)存頁
????struct?page?*newpage?=?get_new_page(page,?private,?&result);
????...

????//?2.?解開所有使用了當前可移動內(nèi)存頁的進程的虛擬內(nèi)存映射（涉及到內(nèi)存頁反向映射）
????try_to_unmap(page,?TTU_MIGRATION|TTU_IGNORE_MLOCK|TTU_IGNORE_ACCESS);

skip_unmap:
????//?3.?將可移動內(nèi)存頁的數(shù)據(jù)復制到空閑內(nèi)存頁中
????if?(!page_mapped(page))
????????rc?=?move_to_new_page(newpage,?page,?remap_swapcache);
????...
????return?rc;
}

由于?unmap_and_move()?函數(shù)的實現(xiàn)比較復雜，所以我們對其進行了簡化。可以看出，unmap_and_move()?函數(shù)主要完成 3 個工作：

從內(nèi)存區(qū)中找到一個空閑的內(nèi)存頁。根據(jù)內(nèi)存碎片整理算法，會從內(nèi)存區(qū)最后開始掃描，找到合適的空閑內(nèi)存頁。

由于將可移動內(nèi)存頁遷移到空閑內(nèi)存頁后，進程的虛擬內(nèi)存映射將會發(fā)生變化。所以，這里要調(diào)用?try_to_unmap()?函數(shù)來解開所有使用了當前可移動內(nèi)存頁的映射。

調(diào)用?move_to_new_page()?函數(shù)將可移動內(nèi)存頁的數(shù)據(jù)復制到空閑內(nèi)存頁中。在?move_to_new_page()?函數(shù)中，還會重新建立進程的虛擬內(nèi)存映射，這樣使用了當前可移動內(nèi)存頁的進程就能夠正常運行。

至此，內(nèi)存碎片整理的過程已經(jīng)分析完畢。

不過細心的讀者可能發(fā)現(xiàn)，在文中并沒有分析重新構(gòu)建虛擬內(nèi)存映射的過程。是的，因為重新構(gòu)建虛擬內(nèi)存映射要涉及到?內(nèi)存頁反向映射?的知識點，后續(xù)的文章會介紹這個知識點，所以這里就不作詳細分析了。

總結(jié)

從上面的分析可知，內(nèi)存碎片整理?是為了解決：在申請多個地址連續(xù)的內(nèi)存頁時，空閑內(nèi)存頁數(shù)量充足，但還是分配失敗的情況。

但由于內(nèi)存碎片整理需要消耗大量的 CPU 時間，所以我們在申請內(nèi)存時，可以通過指定?__GFP_WAIT?標志位（不等待）來避免內(nèi)存碎片整理過程。

編輯：黃飛

?