一文解析Linux內(nèi)存碎片整理原理

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

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

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

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

內(nèi)存整理也是這樣，看起來(lái)很簡(jiǎn)單，但實(shí)現(xiàn)起來(lái)就不那么簡(jiǎn)單了。因?yàn)樵趦?nèi)存整理后，需要修正進(jìn)程的虛擬內(nèi)存與物理內(nèi)存之間的映射關(guān)系。如下圖所示：

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

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

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

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

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

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

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

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

最后結(jié)果：

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

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

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

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

1. 內(nèi)存碎片整理時(shí)機(jī)

當(dāng)要申請(qǐng)多個(gè)地址聯(lián)系的內(nèi)存頁(yè)時(shí)，如果申請(qǐng)失敗，將會(huì)進(jìn)行內(nèi)存碎片整理。其調(diào)用鏈如下：

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

當(dāng)調(diào)用?alloc_pages_node()?函數(shù)申請(qǐng)多個(gè)地址連續(xù)的內(nèi)存頁(yè)失敗時(shí)，將會(huì)觸發(fā)調(diào)用?__alloc_pages_direct_compact()?函數(shù)來(lái)進(jìn)行內(nèi)存碎片整理。我們來(lái)看看?__alloc_pages_direct_compact()?函數(shù)的實(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.?如果申請(qǐng)一個(gè)內(nèi)存頁(yè)，那么就沒有整理碎片的必要（這說明是內(nèi)存不足，而不是內(nèi)存碎片導(dǎo)致）
????if?(!order?||?compaction_deferred(preferred_zone))
????????return?NULL;

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

????if?(*did_some_progress?!=?COMPACT_SKIPPED)?{
????????...
????????//?3.?整理完內(nèi)存碎片后，繼續(xù)嘗試申請(qǐng)內(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 個(gè)步驟：

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

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

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

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

由于內(nèi)存碎片整理的具體實(shí)現(xiàn)在?try_to_compact_pages()?函數(shù)中進(jìn)行，所以我們繼續(xù)來(lái)看看?try_to_compact_pages()?函數(shù)的實(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)核會(huì)把物理內(nèi)存分成多個(gè)內(nèi)存區(qū)進(jìn)行管理）
????for_each_zone_zonelist_nodemask(zone,?z,?zonelist,?high_zoneidx,?nodemask)?{
????????...
????????//?2.?對(duì)內(nèi)存區(qū)進(jìn)行內(nèi)存碎片整理
????????status?=?compact_zone_order(zone,?order,?gfp_mask);
????????...
????}

????return?rc;
}

可以看出，try_to_compact_pages()?函數(shù)最終會(huì)調(diào)用?compact_zone_order()?函數(shù)來(lái)進(jìn)行內(nèi)存碎片整理。我們只能進(jìn)行來(lá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)存碎片整理的具體實(shí)現(xiàn)（調(diào)用鏈可真深啊 ^_^?。?，compact_zone_order()?函數(shù)也是構(gòu)造了一些參數(shù)，然后繼續(xù)調(diào)用?compact_zone()?來(lái)進(jìn)行內(nèi)存碎片整理：

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

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

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

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

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

isolate_migratepages() 函數(shù)

isolate_migratepages()?函數(shù)用于收集可移動(dòng)的內(nèi)存頁(yè)列表，我們來(lái)看看其實(shí)現(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)存頁(yè)
????for?(;?low_pfn?lru,?migratelist);?
????????...
????????cc->nr_migratepages++;
????????...
????}
????...
????return?cc->nr_migratepages;
}

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

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

通過內(nèi)存頁(yè)的編號(hào)獲取內(nèi)存頁(yè)對(duì)象。

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

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

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

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

migrate_pages() 函數(shù)

migrate_pages()?函數(shù)負(fù)責(zé)將可移動(dòng)的內(nèi)存頁(yè)列表遷移到空閑列表中，我們來(lái)分析一下其實(shí)現(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ù)的邏輯很簡(jiǎn)單，主要完成 2 個(gè)步驟：

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

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

可以看出，具體的內(nèi)存遷移過程在?unmap_and_move()?函數(shù)中實(shí)現(xiàn)。我們來(lái)看看?unmap_and_move()?函數(shù)的實(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ū)中找到一個(gè)空閑的內(nèi)存頁(yè)
????struct?page?*newpage?=?get_new_page(page,?private,?&result);
????...

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

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

由于?unmap_and_move()?函數(shù)的實(shí)現(xiàn)比較復(fù)雜，所以我們對(duì)其進(jìn)行了簡(jiǎn)化?？梢钥闯?，unmap_and_move()?函數(shù)主要完成 3 個(gè)工作：

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

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

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

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

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

總結(jié)

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

但由于內(nèi)存碎片整理需要消耗大量的 CPU 時(shí)間，所以我們?cè)谏暾?qǐng)內(nèi)存時(shí)，可以通過指定?__GFP_WAIT?標(biāo)志位（不等待）來(lái)避免內(nèi)存碎片整理過程。

編輯：黃飛

?