哈嘍，我是子牙，一個(gè)很卷的硬核男人

最近這段時(shí)間一直在備課Linux內(nèi)核的內(nèi)存模塊，每每研究完一小塊知識(shí)點(diǎn)，我就發(fā)自內(nèi)心的感嘆：太復(fù)雜了！但是就是這個(gè)只要研究過(guò)Linux內(nèi)核內(nèi)存都會(huì)感嘆復(fù)雜的玩意，已存在了30多年（從Linux2.3引入，時(shí)間大概是1999年），可想而知這套內(nèi)存模塊設(shè)計(jì)的有多優(yōu)秀！

我也問(wèn)了下ChatGPT，這30多年來(lái)，這座當(dāng)今科技世界的地基Linux內(nèi)核的核心：內(nèi)存模塊，經(jīng)歷了哪些變化。

圖片

看完了我久久不能平靜！不是激動(dòng)，是愁哇：這么復(fù)雜的玩意，我怎么教別人才能聽(tīng)得懂消化得了呢？早上突發(fā)奇想：不如換個(gè)思維，如果我們來(lái)設(shè)計(jì)Linux內(nèi)核內(nèi)存模塊，我們會(huì)怎么去做呢？將自己代入，去了解大師的杰作，應(yīng)該會(huì)有意想不到的效果吧！

OK，起筆，成文。愿你enjoy

一、內(nèi)存管理算法

我問(wèn)了下ChatGPT：歷史上存在的管理大塊內(nèi)存的算法有哪些，它給的答案：

圖片

先說(shuō)內(nèi)存池，這個(gè)是離大家最近的。如果你研究過(guò)底層項(xiàng)目如Java虛擬機(jī)、Python虛擬機(jī)、Redis、MySQL……里面一定會(huì)用到內(nèi)存池，可以減少對(duì)OS內(nèi)存的申請(qǐng)與釋放，提升性能。通過(guò)垃圾回收線程回收內(nèi)存或者完成內(nèi)存規(guī)整，減少內(nèi)存碎片。不過(guò)這個(gè)算法是依托OS內(nèi)存實(shí)現(xiàn)的，我們?nèi)绻獙?shí)現(xiàn)OS，這個(gè)用不了。

456提到的段頁(yè)，是硬件層面提供的，即CPU層面的段機(jī)制與頁(yè)機(jī)制，很早以前是通過(guò)段頁(yè)來(lái)管理大塊內(nèi)存，因?yàn)槟菚r(shí)候內(nèi)存不大，自32位CPU以后，就不再使用這幾種方式管理內(nèi)存了。想研究明白的小伙伴可自行研究或者學(xué)習(xí)我的手寫(xiě)OS課程，里面有教。

位圖跟鏈表，在不考慮非常復(fù)雜的場(chǎng)景的情況下，其實(shí)是最好的選擇。我著重講講位圖，我自己寫(xiě)的OS就是使用的位圖，對(duì)鏈表感興趣的自行研究。

圖片

位圖的核心思想是：一個(gè)比特映射一個(gè)4K物理頁(yè)，一個(gè)比特兩個(gè)值：0跟1，如果這個(gè)4K頁(yè)是空閑的，對(duì)應(yīng)的比特位置0，如果這個(gè)4K頁(yè)分配出去了，這個(gè)比特位置為1。

圖片

如果位圖十全十美，就沒(méi)有伙伴系統(tǒng)算法存在的必要了，那位圖的缺陷是什么呢？這就要說(shuō)到，優(yōu)秀的內(nèi)存管理算法的職責(zé)是什么：大塊內(nèi)存環(huán)境下，可以高效的分配內(nèi)存；內(nèi)存不夠的時(shí)候，支持異步回收；內(nèi)存極度緊張的時(shí)候，支持同步回收；支持內(nèi)存規(guī)整，合并內(nèi)存碎片；還有留有擴(kuò)展余地，支持硬件的不斷更新，比如當(dāng)前內(nèi)存條的熱插拔……

來(lái)看看位圖的優(yōu)缺點(diǎn)：

圖片

那Linux內(nèi)核中有沒(méi)有用位圖呢？用了！在伙伴算法未完成初始化之前，一直用的是位圖。即在未執(zhí)行完paging_init函數(shù)前，使用的是bootmem分配器，它的底層就是位圖。

接下來(lái)咱們就講今天的重頭戲：伙伴系統(tǒng)+Slab分配器。

二、頁(yè)幀（page frame）

Linux內(nèi)核中對(duì)內(nèi)存的控制，除了實(shí)現(xiàn)了硬件層面的，還有軟件層面的。硬件層面的，控制位在實(shí)現(xiàn)頁(yè)表的時(shí)候就已經(jīng)實(shí)現(xiàn)了。

圖片

那軟件層面的控制位保存在哪里呢？Linux內(nèi)核引入了所謂的頁(yè)幀，即每個(gè)4K物理頁(yè)，在Linux內(nèi)核中都有一個(gè)page對(duì)象與之一一對(duì)應(yīng)。這個(gè)page對(duì)象，描述了一個(gè)4K頁(yè)的信息如：匿名頁(yè)還是文件頁(yè)、page cache對(duì)應(yīng)文件信息、私有還是共享、已被分配還是空閑、是否是臟頁(yè)、被映射的次數(shù)及映射到哪些進(jìn)程的頁(yè)表中……

圖片

三、伙伴系統(tǒng)結(jié)構(gòu)

伙伴系統(tǒng)結(jié)構(gòu)，簡(jiǎn)而言之就是：Linux內(nèi)核用一個(gè)pglist_data對(duì)象描述一個(gè)NUMA節(jié)點(diǎn)，用N個(gè)zone對(duì)象分區(qū)管理NUMA節(jié)點(diǎn)中的內(nèi)存，用前面提到的page對(duì)象管理每一個(gè)4K物理頁(yè)，如圖：

圖片

每個(gè)NUMA節(jié)點(diǎn)中的內(nèi)存稱(chēng)為本地內(nèi)存，與之相鄰的節(jié)點(diǎn)稱(chēng)為相鄰節(jié)點(diǎn)，cpu1所在的NUMA節(jié)點(diǎn)比cpu2所在的NUMA節(jié)點(diǎn)離cpu0所在的NUMA節(jié)點(diǎn)更近，所以在某些分配策略下，cpu0所在的NUMA節(jié)點(diǎn)內(nèi)存耗盡，就會(huì)優(yōu)先從cpu1所在節(jié)點(diǎn)分配，以此內(nèi)推……這些都是理解伙伴系統(tǒng)很重要的知識(shí)點(diǎn)。

總結(jié)一下：Linux內(nèi)核是基于NUMA架構(gòu)實(shí)現(xiàn)的，每一個(gè)NUMA節(jié)點(diǎn)，內(nèi)核中都有一個(gè)pglist_data對(duì)象與之對(duì)象。每個(gè)NUMA節(jié)點(diǎn)中的內(nèi)存，都會(huì)用N個(gè)zone進(jìn)行管理，64位Linux，最多會(huì)有三個(gè)zone：ZONE_DMA、ZONE_DMA32、ZONE_NORMAL。每個(gè)4K物理頁(yè)，內(nèi)核中都有一個(gè)page對(duì)象與之對(duì)應(yīng)，描述其相關(guān)使用信息及控制信息。

伙伴系統(tǒng)最終的結(jié)構(gòu)長(zhǎng)什么樣呢？如圖：

圖片

四、分配內(nèi)存

現(xiàn)在結(jié)構(gòu)有了，我們要寫(xiě)分配內(nèi)存的函數(shù)了，要怎么寫(xiě)呢？比如我要5個(gè)4K物理頁(yè)。

首先，肯定是定位我要在哪個(gè)NUMA節(jié)點(diǎn)上分配內(nèi)存，這在Linux內(nèi)核中對(duì)應(yīng)的就是mempolicy?？蛇x的方案有：

1. 當(dāng)前運(yùn)行代碼的CPU所在的NUMA節(jié)點(diǎn)，根據(jù)該NUMA節(jié)點(diǎn)內(nèi)存耗盡的處理策略衍生出兩個(gè)分配策略：default policy、local policy。默認(rèn)策略（default policy）的方案是內(nèi)存不足，會(huì)經(jīng)過(guò)運(yùn)算選擇合適的NUMA節(jié)點(diǎn)去要內(nèi)存。局部策略（local policy）的方案是分不到內(nèi)存就死給你看
2. Linux內(nèi)核支持綁定一個(gè)進(jìn)程到某個(gè)NUMA節(jié)點(diǎn)，意味著這個(gè)進(jìn)程只有分配內(nèi)存都是從這個(gè)NUMA節(jié)點(diǎn)分配，如果分配不到就會(huì)經(jīng)歷內(nèi)存規(guī)整、同步回收、MEM killer、OOM。對(duì)應(yīng)的策略就是綁定策略（bind policy）
3. Linux內(nèi)核支持你配置一個(gè)NUMA節(jié)點(diǎn)作為優(yōu)先分配節(jié)點(diǎn)，因?yàn)樗械倪M(jìn)程都優(yōu)先在這個(gè)NUMA節(jié)點(diǎn)上分配內(nèi)存，所以耗盡是遲早的事，如果耗盡了，就會(huì)經(jīng)過(guò)運(yùn)算從其他NUMA節(jié)點(diǎn)分配內(nèi)存，這個(gè)策略就是首選策略（preferred policy），這個(gè)也是Linux內(nèi)核的默認(rèn)策略
4. 咱們中國(guó)講究中庸對(duì)吧，沒(méi)想到國(guó)外也信奉這個(gè)，對(duì)于的策略是遠(yuǎn)程策略（interleave policy），即在所有的NUMA節(jié)點(diǎn)上均勻分配內(nèi)存，這個(gè)也是創(chuàng)建進(jìn)程的默認(rèn)策略。言外之意，如果不后期配置，我們創(chuàng)建的進(jìn)程的內(nèi)存分配策略是在所有NUMA節(jié)點(diǎn)中均勻分配

現(xiàn)在我們選定了NUMA node0，接下來(lái)就要去選擇zone了：

1. 受上面講的選擇NUMA節(jié)點(diǎn)對(duì)應(yīng)的分配策略影響，選擇zone會(huì)考慮首選節(jié)點(diǎn)及備選節(jié)點(diǎn)，對(duì)應(yīng)的就是ZONELIST_FALLBACK、ZONELIST_NOFALLBACK。一般用的都是ZONELIST_FALLBACK，當(dāng)前NUMA節(jié)點(diǎn)分不到內(nèi)存，去其他NUMA節(jié)點(diǎn)分配。default policy、preferred policy、interleave policy對(duì)應(yīng)的是它
2. 每個(gè)NUMA節(jié)點(diǎn)最多會(huì)有3個(gè)ZONE，比如64位Linux內(nèi)核對(duì)應(yīng)的ZONE；DMA、DMA32、NORMAL，那選擇zone時(shí)可以指定在哪個(gè)ZONE中分配。如果不指定的話，默認(rèn)是從NORMAL中分配。那都從NORMAL中分配，這個(gè)ZONE會(huì)很快用光的，但是其他ZONE如DMA、DMA32還是空閑的，所以Linux內(nèi)核引入了降級(jí)機(jī)制（或者叫回退機(jī)制），即NORMAL分配不到內(nèi)存了，去當(dāng)前NUMA節(jié)點(diǎn)的低端內(nèi)存去分配內(nèi)存。但是DMA、DMA32也要考慮給DMA預(yù)留內(nèi)存，不能幫助高端內(nèi)存把自己區(qū)域內(nèi)存耗盡，就有了lowmem_reserve
3. 如果NORMAL分配不到內(nèi)存，一開(kāi)始是不會(huì)采用回退機(jī)制，想想也不合理對(duì)吧，就像你缺錢(qián)，你不可能一上來(lái)就去借錢(qián)，肯定想到的是家里有啥能賣(mài)的先給賣(mài)了，不夠再說(shuō)，Linux內(nèi)核也是同樣的邏輯，先回收，回收不到再說(shuō)。那合適觸發(fā)回收呢？是同步回收還是異步回收？要不要觸發(fā)killer、OOM？這些都是由水位線（watermark）決定的，之前寫(xiě)過(guò)這方面的文章 傳送門(mén)

現(xiàn)在zone也選中了：NORMAL，接下來(lái)就是真正的去拿物理頁(yè)了。如何拿物理頁(yè)呢？這里門(mén)道也蠻多的。想出這套算法的人，真乃奇才！把這套算法完美的實(shí)現(xiàn)出來(lái)的人，也不簡(jiǎn)單。

要想理解如何拿物理頁(yè)，得知道伙伴系統(tǒng)底層是如何管理物理頁(yè)的。每個(gè)ZONE中有一個(gè)數(shù)組free_area用來(lái)管理物理頁(yè)，這個(gè)數(shù)組有12個(gè)元素，每個(gè)元素是個(gè)鏈表，數(shù)組下標(biāo)就是階，比如index=0對(duì)應(yīng)的鏈表中的每個(gè)元素就是一個(gè)4K物理頁(yè)，index=1對(duì)應(yīng)的鏈表中的每個(gè)元素就是兩個(gè)4K物理頁(yè)，以此類(lèi)推。

圖片

回答最初的問(wèn)題：如何拿到5個(gè)4K物理頁(yè)呢，就是去index=3對(duì)應(yīng)的鏈表中去分配。如果這個(gè)鏈表中是空的呢？那就往上找index=4的，index=4對(duì)應(yīng)的鏈表中每個(gè)元素是16個(gè)4K物理頁(yè)，會(huì)將這個(gè)元素拆成兩個(gè)元素放到index=3的鏈表中，然后去分配。至此，就完成了內(nèi)存分配。

對(duì)了，為了提升內(nèi)存分配速度，Linux內(nèi)核中還引入了PCP，即Per-CPU Pages，每個(gè)CPU都有自己的一組本地緩存頁(yè)（pages），這些頁(yè)可以被該CPU上運(yùn)行的進(jìn)程快速分配和回收，而不需要加鎖操作，從而減少了對(duì)全局內(nèi)存池的爭(zhēng)用，提高了性能。但是只有當(dāng)分配一個(gè)4K頁(yè)的時(shí)候，才從PCP中分配。

總結(jié)來(lái)說(shuō)，在NUMA節(jié)點(diǎn)環(huán)境下要想拿到物理內(nèi)存，得先確定從哪個(gè)NUMA節(jié)點(diǎn)拿，再確定在選定的NUMA節(jié)點(diǎn)中的哪個(gè)ZONE中去拿，最后確定要怎么拿，這條線是主線，理解了這條主線，再結(jié)合Linux內(nèi)核提供的機(jī)制，你就能理解完整的Linux內(nèi)核內(nèi)存模塊。

這就是內(nèi)存的全部嗎？當(dāng)然不是！還有很多很多：slab、匿名頁(yè)、文件頁(yè)、頁(yè)回收、頁(yè)遷移、vma、反向映射…但是你先得非常了解本文分享的這些，你才能理解后面的那些，本文分享的這些，是Linux內(nèi)核內(nèi)存模塊基礎(chǔ)中的基礎(chǔ)。