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

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

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

圖片

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

OK，起筆，成文。愿你enjoy

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

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

圖片

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

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

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

圖片

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

圖片

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

來看看位圖的優(yōu)缺點：

圖片

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

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

二、頁幀（page frame）

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

圖片

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

圖片

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

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

圖片

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

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

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

圖片

四、分配內(nèi)存

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

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

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

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

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

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

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

圖片

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

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

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

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