想象我來設計Linux內核內存
哈嘍，我是子牙，一個很卷的硬核男人
最近這段時間一直在備課Linux內核的內存模塊，每每研究完一小塊知識點，我就發自內心的感嘆：太復雜了！但是就是這個只要研究過Linux內核內存都會感嘆復雜的玩意，已存在了30多年（從Linux2.3引入，時間大概是1999年），可想而知這套內存模塊設計的有多優秀！
我也問了下ChatGPT，這30多年來，這座當今科技世界的地基Linux內核的核心：內存模塊，經歷了哪些變化。
圖片
看完了我久久不能平靜！不是激動，是愁哇：這么復雜的玩意，我怎么教別人才能聽得懂消化得了呢？早上突發奇想：不如換個思維，如果我們來設計Linux內核內存模塊，我們會怎么去做呢？將自己代入，去了解大師的杰作，應該會有意想不到的效果吧！
OK，起筆，成文。愿你enjoy
一、內存管理算法
我問了下ChatGPT：歷史上存在的管理大塊內存的算法有哪些，它給的答案：
圖片
先說內存池，這個是離大家最近的。如果你研究過底層項目如Java虛擬機、Python虛擬機、Redis、MySQL……里面一定會用到內存池，可以減少對OS內存的申請與釋放，提升性能。通過垃圾回收線程回收內存或者完成內存規整，減少內存碎片。不過這個算法是依托OS內存實現的，我們如果要實現OS，這個用不了。
456提到的段頁，是硬件層面提供的，即CPU層面的段機制與頁機制，很早以前是通過段頁來管理大塊內存，因為那時候內存不大，自32位CPU以后，就不再使用這幾種方式管理內存了。想研究明白的小伙伴可自行研究或者學習我的手寫OS課程，里面有教。
位圖跟鏈表，在不考慮非常復雜的場景的情況下，其實是最好的選擇。我著重講講位圖，我自己寫的OS就是使用的位圖，對鏈表感興趣的自行研究。
圖片
位圖的核心思想是：一個比特映射一個4K物理頁，一個比特兩個值：0跟1，如果這個4K頁是空閑的，對應的比特位置0，如果這個4K頁分配出去了，這個比特位置為1。
圖片
如果位圖十全十美，就沒有伙伴系統算法存在的必要了，那位圖的缺陷是什么呢？這就要說到，優秀的內存管理算法的職責是什么：大塊內存環境下，可以高效的分配內存；內存不夠的時候，支持異步回收；內存極度緊張的時候，支持同步回收；支持內存規整，合并內存碎片；還有留有擴展余地，支持硬件的不斷更新，比如當前內存條的熱插拔……
來看看位圖的優缺點：
圖片
那Linux內核中有沒有用位圖呢？用了！在伙伴算法未完成初始化之前，一直用的是位圖。即在未執行完paging_init函數前，使用的是bootmem分配器，它的底層就是位圖。
接下來咱們就講今天的重頭戲：伙伴系統+Slab分配器。
二、頁幀（page frame）
Linux內核中對內存的控制，除了實現了硬件層面的，還有軟件層面的。硬件層面的，控制位在實現頁表的時候就已經實現了。
圖片
那軟件層面的控制位保存在哪里呢？Linux內核引入了所謂的頁幀，即每個4K物理頁，在Linux內核中都有一個page對象與之一一對應。這個page對象，描述了一個4K頁的信息如：匿名頁還是文件頁、page cache對應文件信息、私有還是共享、已被分配還是空閑、是否是臟頁、被映射的次數及映射到哪些進程的頁表中……
圖片
三、伙伴系統結構
伙伴系統結構，簡而言之就是：Linux內核用一個pglist_data對象描述一個NUMA節點，用N個zone對象分區管理NUMA節點中的內存，用前面提到的page對象管理每一個4K物理頁，如圖：
圖片
每個NUMA節點中的內存稱為本地內存，與之相鄰的節點稱為相鄰節點，cpu1所在的NUMA節點比cpu2所在的NUMA節點離cpu0所在的NUMA節點更近，所以在某些分配策略下，cpu0所在的NUMA節點內存耗盡，就會優先從cpu1所在節點分配，以此內推……這些都是理解伙伴系統很重要的知識點。
總結一下：Linux內核是基于NUMA架構實現的，每一個NUMA節點，內核中都有一個pglist_data對象與之對象。每個NUMA節點中的內存，都會用N個zone進行管理，64位Linux，最多會有三個zone：ZONE_DMA、ZONE_DMA32、ZONE_NORMAL。每個4K物理頁，內核中都有一個page對象與之對應，描述其相關使用信息及控制信息。
伙伴系統最終的結構長什么樣呢？如圖：
圖片
四、分配內存
現在結構有了，我們要寫分配內存的函數了，要怎么寫呢？比如我要5個4K物理頁。
首先，肯定是定位我要在哪個NUMA節點上分配內存，這在Linux內核中對應的就是mempolicy。可選的方案有：
- 當前運行代碼的CPU所在的NUMA節點，根據該NUMA節點內存耗盡的處理策略衍生出兩個分配策略：default policy、local policy。默認策略（default policy）的方案是內存不足，會經過運算選擇合適的NUMA節點去要內存。局部策略（local policy）的方案是分不到內存就死給你看
- Linux內核支持綁定一個進程到某個NUMA節點，意味著這個進程只有分配內存都是從這個NUMA節點分配，如果分配不到就會經歷內存規整、同步回收、MEM killer、OOM。對應的策略就是綁定策略（bind policy）
- Linux內核支持你配置一個NUMA節點作為優先分配節點，因為所有的進程都優先在這個NUMA節點上分配內存，所以耗盡是遲早的事，如果耗盡了，就會經過運算從其他NUMA節點分配內存，這個策略就是首選策略（preferred policy），這個也是Linux內核的默認策略
- 咱們中國講究中庸對吧，沒想到國外也信奉這個，對于的策略是遠程策略（interleave policy），即在所有的NUMA節點上均勻分配內存，這個也是創建進程的默認策略。言外之意，如果不后期配置，我們創建的進程的內存分配策略是在所有NUMA節點中均勻分配
現在我們選定了NUMA node0，接下來就要去選擇zone了：
- 受上面講的選擇NUMA節點對應的分配策略影響，選擇zone會考慮首選節點及備選節點，對應的就是ZONELIST_FALLBACK、ZONELIST_NOFALLBACK。一般用的都是ZONELIST_FALLBACK，當前NUMA節點分不到內存，去其他NUMA節點分配。default policy、preferred policy、interleave policy對應的是它
- 每個NUMA節點最多會有3個ZONE，比如64位Linux內核對應的ZONE；DMA、DMA32、NORMAL，那選擇zone時可以指定在哪個ZONE中分配。如果不指定的話，默認是從NORMAL中分配。那都從NORMAL中分配，這個ZONE會很快用光的，但是其他ZONE如DMA、DMA32還是空閑的，所以Linux內核引入了降級機制（或者叫回退機制），即NORMAL分配不到內存了，去當前NUMA節點的低端內存去分配內存。但是DMA、DMA32也要考慮給DMA預留內存，不能幫助高端內存把自己區域內存耗盡，就有了lowmem_reserve
- 如果NORMAL分配不到內存，一開始是不會采用回退機制，想想也不合理對吧，就像你缺錢，你不可能一上來就去借錢，肯定想到的是家里有啥能賣的先給賣了，不夠再說，Linux內核也是同樣的邏輯，先回收，回收不到再說。那合適觸發回收呢？是同步回收還是異步回收？要不要觸發killer、OOM？這些都是由水位線（watermark）決定的，之前寫過這方面的文章 傳送門
現在zone也選中了：NORMAL，接下來就是真正的去拿物理頁了。如何拿物理頁呢？這里門道也蠻多的。想出這套算法的人，真乃奇才！把這套算法完美的實現出來的人，也不簡單。
要想理解如何拿物理頁，得知道伙伴系統底層是如何管理物理頁的。每個ZONE中有一個數組free_area用來管理物理頁，這個數組有12個元素，每個元素是個鏈表，數組下標就是階，比如index=0對應的鏈表中的每個元素就是一個4K物理頁，index=1對應的鏈表中的每個元素就是兩個4K物理頁，以此類推。
圖片
回答最初的問題：如何拿到5個4K物理頁呢，就是去index=3對應的鏈表中去分配。如果這個鏈表中是空的呢？那就往上找index=4的，index=4對應的鏈表中每個元素是16個4K物理頁，會將這個元素拆成兩個元素放到index=3的鏈表中，然后去分配。至此，就完成了內存分配。
對了，為了提升內存分配速度，Linux內核中還引入了PCP，即Per-CPU Pages，每個CPU都有自己的一組本地緩存頁（pages），這些頁可以被該CPU上運行的進程快速分配和回收，而不需要加鎖操作，從而減少了對全局內存池的爭用，提高了性能。但是只有當分配一個4K頁的時候，才從PCP中分配。
總結來說，在NUMA節點環境下要想拿到物理內存，得先確定從哪個NUMA節點拿，再確定在選定的NUMA節點中的哪個ZONE中去拿，最后確定要怎么拿，這條線是主線，理解了這條主線，再結合Linux內核提供的機制，你就能理解完整的Linux內核內存模塊。
這就是內存的全部嗎？當然不是！還有很多很多：slab、匿名頁、文件頁、頁回收、頁遷移、vma、反向映射…但是你先得非常了解本文分享的這些，你才能理解后面的那些，本文分享的這些，是Linux內核內存模塊基礎中的基礎。
