本文出現(xiàn)的內(nèi)核代碼來(lái)自Linux4.19，如果有興趣，讀者可以配合代碼閱讀本文。

一、Linux物理內(nèi)存外碎片化概述

什么是Linux物理內(nèi)存碎片化？Linux物理內(nèi)存碎片化包括兩種：

1.物理內(nèi)存內(nèi)碎片：指分配給用戶的內(nèi)存空間中未被使用的部分。

例如進(jìn)程需要使用3K bytes物理內(nèi)存，于是向系統(tǒng)申請(qǐng)了大小等于3Kbytes的內(nèi)存，但是由于Linux內(nèi)核伙伴系統(tǒng)算法最小顆粒是4K bytes，所以分配的是4Kbytes內(nèi)存，那么其中1K bytes未被使用的內(nèi)存就是內(nèi)存內(nèi)碎片。

Linux物理內(nèi)存內(nèi)碎片

?

2.物理內(nèi)存外碎片化：指系統(tǒng)中無(wú)法利用的小內(nèi)存塊。

例如系統(tǒng)剩余內(nèi)存為16K bytes，但是這16K bytes內(nèi)存是由4個(gè)4K bytes的頁(yè)面組成，即16K內(nèi)存物理頁(yè)幀號(hào)#1不連續(xù)。在系統(tǒng)剩余16K bytes內(nèi)存的情況下，系統(tǒng)卻無(wú)法成功分配大于4K的連續(xù)物理內(nèi)存，該情況就是內(nèi)存外碎片導(dǎo)致，本文中闡述的就是物理內(nèi)存外碎片化。

注：#1物理頁(yè)幀號(hào)：Linux物理內(nèi)存是通過(guò)頁(yè)面進(jìn)行管理，并對(duì)每個(gè)頁(yè)面進(jìn)行編號(hào)，稱為頁(yè)幀號(hào)，如果是連續(xù)的兩個(gè)物理頁(yè)面，其頁(yè)幀號(hào)是連續(xù)的。

Linux物理內(nèi)存外碎片

二、Linux物理內(nèi)存管理框架

闡述物理內(nèi)存外碎片化的來(lái)龍去脈前，先得明白Linux是如何管理物理內(nèi)存的？Linux內(nèi)核采用的是buddy system allocation，即著名的伙伴系統(tǒng)分配器。

1.設(shè)計(jì)思路

伙伴系統(tǒng)分配器的核心思路：將系統(tǒng)的空閑頁(yè)面分為11個(gè)塊鏈表，每個(gè)塊鏈表分別管理著1,2,4,8,16,32,64,128,256,512和1024個(gè)物理頁(yè)幀號(hào)連續(xù)的頁(yè)面。每個(gè)頁(yè)面大小為4K bytes，buddy管理的塊大小范圍從4K bytes到4M bytes，以2的倍數(shù)遞增。

Linux物理內(nèi)存管理框架圖

2.管理邏輯

Linux對(duì)物理頁(yè)面管理的框架如上圖，由于本文闡述的是物理內(nèi)存外碎片，所以關(guān)于伙伴系統(tǒng)本文只做簡(jiǎn)單分析，不涉及具體的細(xì)節(jié)并不闡述關(guān)于per cpu pageset等內(nèi)容，如果讀者有興趣，可以參考內(nèi)核源碼。

Linux將物理內(nèi)存分為不同的node和zone來(lái)管理：

• node：為了支持NUMA結(jié)構(gòu)，即CPU對(duì)不同內(nèi)存簇的訪問(wèn)速度不同，Linux設(shè)計(jì)了node結(jié)構(gòu)，將物理內(nèi)存分為多個(gè)內(nèi)存節(jié)點(diǎn)管理；對(duì)于UMA結(jié)構(gòu)，只有一個(gè)node節(jié)點(diǎn)。
• zone：為兼容不同的平臺(tái)的硬件限制，例如80x86的體系結(jié)構(gòu)的硬件總線訪問(wèn)等問(wèn)題，Linux將node節(jié)點(diǎn)下的內(nèi)存分為多個(gè)zone；目前在ARM平臺(tái)，多個(gè)zone管理已非必要。

zone管理單元下的內(nèi)存通過(guò)free_area數(shù)組將內(nèi)存分成11個(gè)塊鏈表進(jìn)行管理：

free_area數(shù)組總共有11個(gè)索引，每個(gè)索引管理著不同大小的塊鏈表。

• free_area[0]管理的內(nèi)存單位為2^0頁(yè)面，即4K byte內(nèi)存；
• free_area[1]管理的內(nèi)存單位為2^1的物理頁(yè)幀號(hào)連續(xù)頁(yè)面，即8K bytes內(nèi)存；
• 以此類推；

free_area管理的內(nèi)存還細(xì)分為各種類型，例如不可移動(dòng)頁(yè)面和可移動(dòng)頁(yè)面等，每種類型的頁(yè)面類型對(duì)應(yīng)一個(gè)free_list鏈表，該鏈表就鏈接著頁(yè)面結(jié)構(gòu)體。

當(dāng)分配頁(yè)面時(shí)，伙伴系統(tǒng)拿頁(yè)面的步驟如下：（不考慮內(nèi)存慢速路徑）

• 根據(jù)分配頁(yè)面類型，找到對(duì)應(yīng)的內(nèi)存節(jié)點(diǎn)node和內(nèi)存管理單元zone；
• 根據(jù)分配頁(yè)面大小，找到的對(duì)應(yīng)大小的free_area結(jié)構(gòu)體；
• 根據(jù)分配頁(yè)面類型，找到對(duì)應(yīng)的free_list鏈表，分配頁(yè)面；

當(dāng)向伙伴系統(tǒng)釋放頁(yè)面時(shí)，buddy釋放頁(yè)面的步驟如下：

• 根據(jù)分配頁(yè)面類型，找到對(duì)應(yīng)的內(nèi)存節(jié)點(diǎn)node和內(nèi)存管理單元zone；
• 判斷是否有物理頁(yè)幀號(hào)相連的空閑內(nèi)存塊，可以跟被釋放的內(nèi)存塊合并成更大的塊內(nèi)存，合并的條件：
• 物理幀必須都是連續(xù)的；
• 相同的類型和相同的大小；
• 合并后塊內(nèi)存的第一個(gè)頁(yè)面的物理地址滿足”2*塊大小*4K”的倍數(shù)。

• 根據(jù)釋放頁(yè)面的大小或者合并的大小，找到的對(duì)應(yīng)大小的free_area結(jié)構(gòu)體；
• 根據(jù)釋放頁(yè)面的類型，找到對(duì)應(yīng)的free_list鏈表，釋放頁(yè)面；

?資料直通車：Linux內(nèi)核源碼技術(shù)學(xué)習(xí)路線+視頻教程內(nèi)核源碼

學(xué)習(xí)直通車：Linux內(nèi)核源碼內(nèi)存調(diào)優(yōu)文件系統(tǒng)進(jìn)程管理設(shè)備驅(qū)動(dòng)/網(wǎng)絡(luò)協(xié)議棧

三、Linux針對(duì)物理內(nèi)存外碎片化的措施

從“二、Linux物理內(nèi)存管理架構(gòu)”，可以發(fā)現(xiàn)伙伴系統(tǒng)內(nèi)存管理框架是可以有效改善物理內(nèi)存外碎片的，因?yàn)榛锇橄到y(tǒng)有如下兩個(gè)管理邏輯，可以減少了外碎片化的產(chǎn)生：

• 小塊內(nèi)存在小塊鏈表分配，減少大塊鏈表被污染的概率；
• 內(nèi)存釋放時(shí)會(huì)嘗試整合成大塊內(nèi)存的邏輯，有助于大塊內(nèi)存的合成；

除此之外，內(nèi)核還支持以下措施改善物理內(nèi)存外碎片化（只列舉主要的機(jī)制）：

1.memory compaction

（1）內(nèi)存規(guī)整原理

Linux物理頁(yè)面規(guī)整機(jī)制，類似于磁盤整理，主要是應(yīng)用了內(nèi)核的頁(yè)面遷移機(jī)制，是一種將可移動(dòng)頁(yè)面進(jìn)行遷移后騰出連續(xù)物理內(nèi)存的方法。

假設(shè)存在一個(gè)非常小的內(nèi)存域如下：

藍(lán)色表示空閑的頁(yè)面，白色表示已經(jīng)被分配的頁(yè)面，可以看到如上內(nèi)存域的空閑頁(yè)面（藍(lán)色）非常零散，無(wú)法分配大于兩頁(yè)的連續(xù)物理內(nèi)存。

下面演示一下內(nèi)存規(guī)整的簡(jiǎn)化工作原理，內(nèi)核會(huì)運(yùn)行兩個(gè)獨(dú)立的掃描動(dòng)作：第一個(gè)掃描從內(nèi)存域的底部開始，一邊掃描一邊將已分配的可移動(dòng)（MOVABLE）頁(yè)面記錄到一個(gè)列表中：

另外第二掃描是從內(nèi)存域的頂部開始，掃描可以作為頁(yè)面遷移目標(biāo)的空閑頁(yè)面位置，然后也記錄到一個(gè)列表里面：

等兩個(gè)掃描在域中間相遇，意味著掃描結(jié)束，然后將左邊掃描得到的已分配的頁(yè)面遷移到右邊空閑的頁(yè)面中，左邊就形成了一段連續(xù)的物理內(nèi)存，完成頁(yè)面規(guī)整。

（2）使用方法

如果想打開內(nèi)存規(guī)整，內(nèi)核需要打開相關(guān)的配置（默認(rèn)為y）

打開如上配置后，內(nèi)存規(guī)整的觸發(fā)是自動(dòng)的，觸發(fā)內(nèi)存規(guī)整的途徑如下：當(dāng)進(jìn)程嘗試分配高階內(nèi)存無(wú)法滿足并且完成direct_reclaim#1（暫不分析costly_order情況）后，系統(tǒng)會(huì)根據(jù)內(nèi)存剩余判斷是否觸發(fā)內(nèi)存規(guī)整；

注：#1direct_reclaim：進(jìn)程分配內(nèi)存時(shí)發(fā)現(xiàn)內(nèi)存不足從而啟動(dòng)直接回收內(nèi)存操作，這種模式下分配和回收是同步的關(guān)系，也就是說(shuō)分配內(nèi)存的進(jìn)程會(huì)因?yàn)榈却齼?nèi)存回收而被阻塞。

內(nèi)核也提供了接口給用戶觸發(fā)規(guī)整動(dòng)作，接口如下：

/proc/sys/vm/compact_memory

只要往這個(gè)節(jié)點(diǎn)寫值即可觸發(fā)對(duì)系統(tǒng)所有node管理的內(nèi)存做內(nèi)存規(guī)整。

2.kcompactd

（1）kcompact設(shè)計(jì)原理

kcompactd是一個(gè)內(nèi)核規(guī)整的后臺(tái)進(jìn)程，它跟memory compaction的區(qū)別在于：

memory compaction的觸發(fā)途徑是內(nèi)存分配進(jìn)入direct_reclaim（暫不分析costly_order情況）后系統(tǒng)會(huì)根據(jù)內(nèi)存剩余判斷是否觸發(fā)內(nèi)存規(guī)整，或者用戶手動(dòng)觸發(fā)；

kcompactd在喚醒kswapd或者kswapd進(jìn)入休眠時(shí)，主動(dòng)觸發(fā)內(nèi)存規(guī)整。

kcompactd的觸發(fā)路徑如下：主要有如下兩個(gè)途徑：

喚醒kswapd之前觸發(fā)規(guī)整，觸發(fā)的條件是：本次分配不支持direct_reclaim，node內(nèi)存節(jié)點(diǎn)是平衡的，并且kswapd失敗的次數(shù)大于MAX_RECLAIM_RETRIES（默認(rèn)16）。

kswapd即將進(jìn)入睡眠時(shí)：

（2）使用方法

如果想打開內(nèi)存規(guī)整，內(nèi)核需要打開相關(guān)的配置（默認(rèn)為y）

3.其他優(yōu)化的思路

內(nèi)核經(jīng)過(guò)不斷的優(yōu)化，那為何Linux為何還有物理內(nèi)存外碎片化呢？那是因?yàn)槲锢韮?nèi)存外碎片化雖然是可以不斷優(yōu)化的，但卻無(wú)法得到根除。目前的內(nèi)核，我覺(jué)得導(dǎo)致物理外碎片化還有以下兩個(gè)主要原因：

• 不可移動(dòng)頁(yè)面污染了內(nèi)存環(huán)境，導(dǎo)致頁(yè)面規(guī)整失敗；
• 隨著系統(tǒng)不斷申請(qǐng)和釋放的頁(yè)面，導(dǎo)致伙伴系統(tǒng)分配的物理內(nèi)存頁(yè)幀號(hào)越發(fā)隨機(jī)，從而導(dǎo)致內(nèi)存被隔斷的概率越高，碎片化的程度越高，在3.2闡述。

針對(duì)以上兩個(gè)原因，以下的優(yōu)化措施可能達(dá)到一定的優(yōu)化效果：

（1）減少UNMOVABLE頁(yè)面污染內(nèi)存環(huán)境

• 限制不可以移動(dòng)頁(yè)面偷頁(yè)行為

Linux內(nèi)存分配中支持fallback機(jī)制，又叫偷頁(yè)機(jī)制。該機(jī)制是為了規(guī)避同個(gè)zone管理單位頁(yè)面類型剩余不平衡的問(wèn)題，例如同個(gè)zone，A頁(yè)面類型空閑內(nèi)存較多，B頁(yè)面類型空閑內(nèi)存卻非常緊缺，如果沒(méi)有偷頁(yè)機(jī)制，分配B頁(yè)面類型就會(huì)進(jìn)入內(nèi)存分配慢速路徑。有了偷頁(yè)機(jī)制，在同個(gè)zone管理單位，如果UNMOVABLE類型無(wú)空閑頁(yè)面，但是MOVABLE類型頁(yè)面還有空閑頁(yè)面，偷頁(yè)機(jī)制支持在list_head[UNMOVABLE]分配不到頁(yè)面的情況下，向list_head[MOVABLE]分配頁(yè)面。

以下數(shù)組明確了各種頁(yè)面類型可偷的頁(yè)面類型，例如第一行表示UNMOVABLE頁(yè)面可以偷RECLAIMABLE和MOVABLE類型的頁(yè)面，其他類似。

如果不可移動(dòng)頁(yè)面頻繁的偷頁(yè)會(huì)導(dǎo)致不可移動(dòng)頁(yè)面很快污染了內(nèi)存環(huán)境，特別污染了可移動(dòng)頁(yè)面的內(nèi)存，對(duì)內(nèi)存規(guī)整成功率的影響比較大?；谝陨锨闆r，可以在偷頁(yè)的機(jī)制上加上分配大小限制的判斷，不可移動(dòng)頁(yè)面只有大塊內(nèi)存分配才允許偷頁(yè)，以此減少不可移動(dòng)頁(yè)面對(duì)內(nèi)存環(huán)境的污染。

• 不可移動(dòng)類型頁(yè)面偷頁(yè)后主動(dòng)償還

該方法主要是不可移動(dòng)頁(yè)面偷頁(yè)后的一種補(bǔ)償方法。如果發(fā)生不可移動(dòng)頁(yè)面偷頁(yè)后，我們將該頁(yè)面記錄到一個(gè)列表，等后續(xù)不可移動(dòng)頁(yè)面類型存在空閑頁(yè)面時(shí)，將所偷的頁(yè)面遷移回不可移動(dòng)頁(yè)面中，從而降低不可移動(dòng)頁(yè)面的污染。

（2）降低分配頁(yè)幀號(hào)的隨機(jī)性

假設(shè)有一塊小內(nèi)存域如下，以下兩種內(nèi)存分配方式哪種會(huì)導(dǎo)致嚴(yán)重的內(nèi)存碎片化？

• 頁(yè)面從頭部開始分配，直到尾部；
• 頁(yè)面隨機(jī)從任何位置分配。

明顯是第二種內(nèi)存分配方式的對(duì)內(nèi)存外碎片化更不友好，而這點(diǎn)也是伙伴系統(tǒng)目前沒(méi)有解決的問(wèn)題?；锇橄到y(tǒng)雖然將內(nèi)存規(guī)劃成各種大小的內(nèi)存塊，以讓小內(nèi)存分配在小塊鏈表分配，盡量不污染大塊內(nèi)存鏈表，但是卻沒(méi)辦法保證小塊內(nèi)存具體是在物理內(nèi)存的哪個(gè)頁(yè)幀范圍分配。隨著系統(tǒng)的運(yùn)行越久，小塊內(nèi)存的分配的物理頁(yè)幀號(hào)越發(fā)隨機(jī)，那么其導(dǎo)致碎片化的概率就會(huì)越高。

• 預(yù)留法

根據(jù)這種情況，可以通過(guò)預(yù)留的方式進(jìn)行相應(yīng)的優(yōu)化。

預(yù)留一定的內(nèi)存專門用于小塊內(nèi)存分配，經(jīng)過(guò)這個(gè)優(yōu)化措施后，可以有效降低小塊內(nèi)存分配的物理頁(yè)幀號(hào)的隨機(jī)性，從而降低小塊內(nèi)存污染內(nèi)存環(huán)境的概率。

預(yù)留一定的內(nèi)存專門用于大塊內(nèi)存分配，經(jīng)過(guò)該優(yōu)化措施后，預(yù)留的內(nèi)存被小塊內(nèi)存污染的概率就會(huì)降低，可以提升預(yù)留內(nèi)存分配大塊內(nèi)存的成功率。

原文作者：內(nèi)核工匠

?