一篇圖解Linux內(nèi)存碎片整理
我們知道物理內(nèi)存是以頁為單位進(jìn)行管理的，每個(gè)內(nèi)存頁大小默認(rèn)是4K（大頁除外）。申請(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)存頁時(shí)，雖然系統(tǒng)中空閑的內(nèi)存頁數(shù)量足夠，但由于空閑的內(nèi)存頁相對(duì)分散，從而導(dǎo)致分配失敗。這些地址不連續(xù)的內(nèi)存頁被稱為：內(nèi)存碎片。
要解決這個(gè)問題也比較簡(jiǎn)單，只需要把空閑的內(nèi)存塊移動(dòng)到一起即可。如下圖所示：
網(wǎng)絡(luò)上有句很有名的話：理想很美好，現(xiàn)實(shí)很骨感。
內(nèi)存整理也是這樣，看起來很簡(jiǎn)單，但實(shí)現(xiàn)起來就不那么簡(jiǎn)單了。因?yàn)樵趦?nèi)存整理后，需要修正進(jìn)程的虛擬內(nèi)存與物理內(nèi)存之間的映射關(guān)系。如下圖所示：
但由于 Linux 內(nèi)核有個(gè)名為 內(nèi)存頁反向映射 的功能，所以內(nèi)存整理就變得簡(jiǎn)單起來。
接下來，我們將會(huì)分析內(nèi)存碎片整理的原理與實(shí)現(xiàn)。
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ??
內(nèi)存碎片整理原理
內(nèi)存碎片整理的原理比較簡(jiǎn)單：在內(nèi)存碎片整理開始前，會(huì)在內(nèi)存區(qū)的頭和尾各設(shè)置一個(gè)指針，頭指針從頭向尾掃描可移動(dòng)的頁，而尾指針從尾向頭掃描空閑的頁，當(dāng)他們相遇時(shí)終止整理。下面說說內(nèi)存隨便整理的過程（原理參考了內(nèi)核文檔）：
初始時(shí)內(nèi)存狀態(tài)：
在上圖中，白色塊表示空閑的內(nèi)存頁，而紅色塊表示已分配出去的內(nèi)存頁。在初始狀態(tài)時(shí)，內(nèi)存中存在多個(gè)碎片。如果此時(shí)要申請(qǐng) 3 個(gè)地址連續(xù)的內(nèi)存頁，那么將會(huì)申請(qǐng)失敗。
內(nèi)存碎片整理掃描開始：
頭部指針從頭掃描可移動(dòng)頁，而尾部指針從從尾掃描空閑頁。在整理時(shí)，將可移動(dòng)頁的內(nèi)容復(fù)制到空閑頁中。復(fù)制完成后，將可移動(dòng)內(nèi)存頁釋放即可。
最后結(jié)果：
經(jīng)過內(nèi)存碎片整理后，如果現(xiàn)在要申請(qǐng) 3 個(gè)地址連續(xù)的內(nèi)存頁，就能申請(qǐng)成功了。
內(nèi)存碎片整理實(shí)現(xiàn)
接下來，我們將會(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)存頁時(shí)，如果申請(qǐng)失敗，將會(huì)進(jìn)行內(nèi)存碎片整理。其調(diào)用鏈如下：
當(dāng)調(diào)用 alloc_pages_node() 函數(shù)申請(qǐng)多個(gè)地址連續(xù)的內(nèi)存頁失敗時(shí)，將會(huì)觸發(fā)調(diào)用 __alloc_pages_direct_compact() 函數(shù)來進(jìn)行內(nèi)存碎片整理。我們來看看 __alloc_pages_direct_compact() 函數(shù)的實(shí)現(xiàn)：
__alloc_pages_direct_compact() 函數(shù)是內(nèi)存碎片整理的入口，其主要完成 3 個(gè)步驟：
先判斷申請(qǐng)的內(nèi)存塊是否只有一個(gè)內(nèi)存頁，如果是，那么就沒有整理碎片的必要（這說明是內(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ù)來看看 try_to_compact_pages() 函數(shù)的實(shí)現(xiàn)：
可以看出，try_to_compact_pages() 函數(shù)最終會(huì)調(diào)用 compact_zone_order() 函數(shù)來進(jìn)行內(nèi)存碎片整理。我們只能進(jìn)行來分析 compact_zone_order() 函數(shù)：
到這里，我們還沒有看到內(nèi)存碎片整理的具體實(shí)現(xiàn)（調(diào)用鏈可真深啊 ^_^?。?，compact_zone_order() 函數(shù)也是構(gòu)造了一些參數(shù)，然后繼續(xù)調(diào)用 compact_zone() 來進(jìn)行內(nèi)存碎片整理：
在 compact_zone() 函數(shù)里，我們終于看到內(nèi)存碎片整理的邏輯了。compact_zone() 函數(shù)主要完成 2 個(gè)步驟：
調(diào)用 isolate_migratepages() 函數(shù)收集可移動(dòng)的內(nèi)存頁列表。
調(diào)用 migrate_pages() 函數(shù)將可移動(dòng)的內(nèi)存頁列表遷移到空閑列表中。
這兩個(gè)函數(shù)非常重要，我們分別來分析它們是怎么實(shí)現(xiàn)的。
isolate_migratepages() 函數(shù)
isolate_migratepages() 函數(shù)用于收集可移動(dòng)的內(nèi)存頁列表，我們來看看其實(shí)現(xiàn)：
isolate_migratepages() 函數(shù)主要完成 5 個(gè)步驟，分別是：
掃描內(nèi)存區(qū)所有的內(nèi)存頁（與內(nèi)存碎片整理原理一致）。
通過內(nèi)存頁的編號(hào)獲取內(nèi)存頁對(duì)象。
判斷內(nèi)存頁是否可移動(dòng)內(nèi)存頁，如果不是可移動(dòng)內(nèi)存頁，那么就跳過。
將內(nèi)存頁從 LRU 隊(duì)列中刪除，這樣可避免被其他進(jìn)程回收這個(gè)內(nèi)存頁。
添加到可移動(dòng)內(nèi)存頁列表中。
當(dāng)完成這 5 個(gè)步驟后，內(nèi)核就收集到可移動(dòng)的內(nèi)存頁列表。
migrate_pages() 函數(shù)
migrate_pages() 函數(shù)負(fù)責(zé)將可移動(dòng)的內(nèi)存頁列表遷移到空閑列表中，我們來分析一下其實(shí)現(xiàn)過程：
migrate_pages() 函數(shù)的邏輯很簡(jiǎn)單，主要完成 2 個(gè)步驟：
遍歷可移動(dòng)內(nèi)存頁列表，這個(gè)列表就是通過 isolate_migratepages() 函數(shù)收集的可移動(dòng)內(nèi)存頁列表。
調(diào)用 unmap_and_move() 函數(shù)將可移動(dòng)內(nèi)存頁遷移到空閑內(nèi)存頁中。
可以看出，具體的內(nèi)存遷移過程在 unmap_and_move() 函數(shù)中實(shí)現(xiàn)。我們來看看 unmap_and_move() 函數(shù)的實(shí)現(xiàn)：
由于 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)存頁。根據(jù)內(nèi)存碎片整理算法，會(huì)從內(nèi)存區(qū)最后開始掃描，找到合適的空閑內(nèi)存頁。
由于將可移動(dòng)內(nèi)存頁遷移到空閑內(nèi)存頁后，進(jìn)程的虛擬內(nèi)存映射將會(huì)發(fā)生變化。所以，這里要調(diào)用 try_to_unmap() 函數(shù)來解開所有使用了當(dāng)前可移動(dòng)內(nèi)存頁的映射。
調(diào)用 move_to_new_page() 函數(shù)將可移動(dòng)內(nèi)存頁的數(shù)據(jù)復(fù)制到空閑內(nèi)存頁中。在 move_to_new_page() 函數(shù)中，還會(huì)重新建立進(jìn)程的虛擬內(nèi)存映射，這樣使用了當(dāng)前可移動(dòng)內(nèi)存頁的進(jìn)程就能夠正常運(yùn)行。
至此，內(nèi)存碎片整理的過程已經(jīng)分析完畢。
不過細(xì)心的讀者可能發(fā)現(xiàn)，在文中并沒有分析重新構(gòu)建虛擬內(nèi)存映射的過程。是的，因?yàn)橹匦聵?gòu)建虛擬內(nèi)存映射要涉及到 內(nèi)存頁反向映射 的知識(shí)點(diǎn)，后續(xù)的文章會(huì)介紹這個(gè)知識(shí)點(diǎn)，所以這里就不作詳細(xì)分析了。
總結(jié)
從上面的分析可知，內(nèi)存碎片整理 是為了解決：在申請(qǐng)多個(gè)地址連續(xù)的內(nèi)存頁時(shí)，空閑內(nèi)存頁數(shù)量充足，但還是分配失敗的情況。
但由于內(nèi)存碎片整理需要消耗大量的 CPU 時(shí)間，所以我們?cè)谏暾?qǐng)內(nèi)存時(shí)，可以通過指定 __GFP_WAIT 標(biāo)志位（不等待）來避免內(nèi)存碎片整理過程。
原文作者：Linux內(nèi)核那些事
