前言

CPU、IO、磁盤(pán)、內(nèi)存，可以說(shuō)是影響計(jì)算機(jī)性能的幾大關(guān)鍵因素。今天，我們就來(lái)探究一下內(nèi)存的那些事兒。

提示：本文內(nèi)容較長(zhǎng)，閱讀大約需要35分鐘，建議收藏起來(lái)慢慢看。

內(nèi)存為進(jìn)程的運(yùn)行提供物理空間，同時(shí)作為快速CPU和慢速磁盤(pán)之間的適配器，可以說(shuō)是個(gè)非常重要的角色。

通過(guò)本文你將了解到以下內(nèi)容：

本文均圍繞Linux操作系統(tǒng)展開(kāi)，話不多說(shuō)，我們開(kāi)始吧！

虛擬內(nèi)存機(jī)制

當(dāng)要學(xué)習(xí)一個(gè)新知識(shí)點(diǎn)時(shí)，比較好的過(guò)程是先理解出現(xiàn)這個(gè)技術(shù)點(diǎn)的背景原因，同期其他解決方案，新技術(shù)點(diǎn)解決了什么問(wèn)題以及它存在哪些不足和改進(jìn)之處，這樣整個(gè)學(xué)習(xí)過(guò)程是閉環(huán)的。

內(nèi)存為什么需要管理

老子的著名觀點(diǎn)是無(wú)為而治，簡(jiǎn)單說(shuō)就是不過(guò)多干預(yù)而充分依靠自覺(jué)就可以有條不紊地運(yùn)作，理想是美好的，現(xiàn)實(shí)是殘酷的。

Linux系統(tǒng)如果以一種原始簡(jiǎn)單的方式管理內(nèi)存是存在一些問(wèn)題：

進(jìn)程空間隔離問(wèn)題

假如現(xiàn)在有ABC三個(gè)進(jìn)程運(yùn)行在Linux的內(nèi)存空間，設(shè)定OS給進(jìn)程A分配的地址空間是0-20M，進(jìn)程B地址空間30-80M，進(jìn)程C地址空間90-120M。

雖然分配給每個(gè)進(jìn)程的空間是無(wú)交集的，但仍然無(wú)法避免進(jìn)程在某些情況下出現(xiàn)訪問(wèn)異常的情況，如下圖所示：

比如，進(jìn)程A訪問(wèn)了屬于進(jìn)程B的空間，進(jìn)程B訪問(wèn)了屬于進(jìn)程C的空間，甚至修改了空間的值，這樣就會(huì)造成混亂和錯(cuò)誤，實(shí)際中是不允許發(fā)生的。

所以，我們需要的是每個(gè)進(jìn)程有獨(dú)立且隔離的安全空間。

內(nèi)存效率低下問(wèn)題

機(jī)器的內(nèi)存是有限資源，而進(jìn)程數(shù)量是動(dòng)態(tài)且無(wú)法確定的，這樣就會(huì)出現(xiàn)幾個(gè)必須要考慮的問(wèn)題：

• 如果已經(jīng)啟動(dòng)的進(jìn)程們占據(jù)了幾乎所有內(nèi)存空間，沒(méi)有新內(nèi)存可分配了，此時(shí)新進(jìn)程將無(wú)法啟動(dòng)。

• 已經(jīng)啟動(dòng)的進(jìn)程有時(shí)候是在睡大覺(jué)，也就是給了內(nèi)存也不用，占著茅坑不拉屎。

• 連續(xù)內(nèi)存實(shí)在是很珍貴，大部分時(shí)候我們都無(wú)法給進(jìn)程分配它想要的連續(xù)內(nèi)存，離散化內(nèi)存才是我們需要面對(duì)的現(xiàn)實(shí)。

定位調(diào)試和編譯運(yùn)行問(wèn)題

由于程序運(yùn)行時(shí)的位置是不確定的，我們?cè)诙ㄎ粏?wèn)題、調(diào)試代碼、編譯執(zhí)行時(shí)都會(huì)存在很多問(wèn)題。

我們希望每個(gè)進(jìn)程有一致且完整的地址空間，同樣的起始位置放置了堆、棧以及代碼段等，從而簡(jiǎn)化編譯和執(zhí)行過(guò)程中的鏈接器、加載器的使用。

換句話說(shuō)，如果所有進(jìn)程的空間地址分配都是一樣的，那么Linux在設(shè)計(jì)編譯和調(diào)試工具時(shí)就非常簡(jiǎn)單了，否則每個(gè)進(jìn)程都可能是定制化的。

綜上，面對(duì)眾多問(wèn)題，我們需要一套內(nèi)存管理機(jī)制。

中間層的引入

大家一定聽(tīng)過(guò)這句計(jì)算機(jī)諺語(yǔ)：

Any problem in computer science can be solved by another layer of indirection.

計(jì)算機(jī)科學(xué)領(lǐng)域的任何問(wèn)題都可以通過(guò)增加一個(gè)中間層來(lái)解決，解決內(nèi)存問(wèn)題也不例外。

Linux的虛擬內(nèi)存機(jī)制簡(jiǎn)單來(lái)說(shuō)就是在物理內(nèi)存和進(jìn)程之間請(qǐng)了個(gè)管家，內(nèi)存管家上任之后做了以下幾件事情：

• 給每個(gè)進(jìn)程分配完全獨(dú)立的虛擬空間，每個(gè)進(jìn)程終于有只屬于自己的活動(dòng)場(chǎng)地了
• 進(jìn)程使用的虛擬空間最終還要落到物理內(nèi)存上，因此設(shè)置了一套完善的虛擬地址和物理地址的映射機(jī)制
• 引入缺頁(yè)異常機(jī)制實(shí)現(xiàn)內(nèi)存的惰性分配，啥時(shí)候用啥時(shí)候再給
• 引入swap機(jī)制把不活躍的數(shù)據(jù)換到磁盤(pán)上，讓每塊內(nèi)存都用在刀刃上
• 引入OOM機(jī)制在內(nèi)存緊張的情況下干掉那些內(nèi)存殺手
• ......

虛擬內(nèi)存下數(shù)據(jù)讀寫(xiě)問(wèn)題

引入虛擬機(jī)制后，進(jìn)程在獲取CPU資源讀取數(shù)據(jù)時(shí)的流程也發(fā)生了一些變化。

CPU并不再直接和物理內(nèi)存打交道，而是把地址轉(zhuǎn)換的活外包給了MMU，MMU是一種硬件電路，其速度很快，主要工作是進(jìn)行內(nèi)存管理，地址轉(zhuǎn)換只是它承接的業(yè)務(wù)之一。

頁(yè)表的存儲(chǔ)和檢索問(wèn)題

每個(gè)進(jìn)程都會(huì)有自己的頁(yè)表Page Table，頁(yè)表存儲(chǔ)了進(jìn)程中虛擬地址到物理地址的映射關(guān)系，所以就相當(dāng)于一張地圖，MMU收到CPU的虛擬地址之后開(kāi)始查詢頁(yè)表，確定是否存在映射以及讀寫(xiě)權(quán)限是否正常，如下圖所示：

當(dāng)機(jī)器的物理內(nèi)存越來(lái)越大，頁(yè)表這個(gè)地圖也將非常大，于是問(wèn)題出現(xiàn)了：

• 對(duì)于4GB的虛擬地址且大小為4KB頁(yè)，一級(jí)頁(yè)表將有2^20個(gè)表項(xiàng)，頁(yè)表占有連續(xù)內(nèi)存并且存儲(chǔ)空間大
• 多級(jí)頁(yè)表可以有效降低頁(yè)表的存儲(chǔ)空間以及內(nèi)存連續(xù)性要求，但是多級(jí)頁(yè)表同時(shí)也帶來(lái)了查詢效率問(wèn)題

我們以2級(jí)頁(yè)表為例，MMU要先進(jìn)行兩次頁(yè)表查詢確定物理地址，在確認(rèn)了權(quán)限等問(wèn)題后，MMU再將這個(gè)物理地址發(fā)送到總線，內(nèi)存收到之后開(kāi)始讀取對(duì)應(yīng)地址的數(shù)據(jù)并返回。

MMU在2級(jí)頁(yè)表的情況下進(jìn)行了2次檢索和1次讀寫(xiě)，那么當(dāng)頁(yè)表變?yōu)镹級(jí)時(shí)，就變成了N次檢索+1次讀寫(xiě)。

可見(jiàn)，頁(yè)表級(jí)數(shù)越多查詢的步驟越多，對(duì)于CPU來(lái)說(shuō)等待時(shí)間越長(zhǎng)，效率越低，這個(gè)問(wèn)題還需要優(yōu)化才行。

本段小結(jié) 敲黑板 劃重點(diǎn)
頁(yè)表存在于進(jìn)程的內(nèi)存之中，MMU收到虛擬地址之后查詢Page Table來(lái)獲取物理地址。
單級(jí)頁(yè)表對(duì)連續(xù)內(nèi)存要求高，于是引入了多級(jí)頁(yè)表。
多級(jí)頁(yè)表也是一把雙刃劍，在減少連續(xù)存儲(chǔ)要求且減少存儲(chǔ)空間的同時(shí)降低了查詢效率。

MMU和TLB這對(duì)黃金搭檔

CPU覺(jué)得MMU干活雖然賣力氣，但是效率有點(diǎn)低，不太想繼續(xù)外包給它了，這一下子把MMU急壞了。

MMU于是找來(lái)了一些精通統(tǒng)計(jì)的朋友，經(jīng)過(guò)一番研究之后發(fā)現(xiàn)CPU用的數(shù)據(jù)經(jīng)常是一小搓，但是每次MMU都還要重復(fù)之前的步驟來(lái)檢索，害，就知道埋頭干活了，也得講究方式方法呀！

找到瓶頸之后，MMU引入了新武器，江湖人稱快表的TLB，別看TLB容量小，但是正式上崗之后干活還真是不含糊。

當(dāng)CPU給MMU傳新虛擬地址之后，MMU先去問(wèn)TLB那邊有沒(méi)有，如果有就直接拿到物理地址發(fā)到總線給內(nèi)存，齊活。

TLB容量比較小，難免發(fā)生Cache Miss，這時(shí)候MMU還有保底的老武器頁(yè)表 Page Table，在頁(yè)表中找到之后MMU除了把地址發(fā)到總線傳給內(nèi)存，還把這條映射關(guān)系給到TLB，讓它記錄一下刷新緩存。

TLB容量不滿的時(shí)候就直接把新記錄存儲(chǔ)了，當(dāng)滿了的時(shí)候就開(kāi)啟了淘汰大法把舊記錄清除掉，來(lái)保存新記錄，仿佛完美解決了問(wèn)題。

本段小結(jié) 敲黑板 劃重點(diǎn)
MMU也是個(gè)聰明的家伙，集成了TLB來(lái)存儲(chǔ)CPU最近常用的頁(yè)表項(xiàng)來(lái)加速尋址，TLB找不到再去全量頁(yè)表尋址，可以認(rèn)為T(mén)LB是MMU的緩存。

缺頁(yè)異常來(lái)了

假如目標(biāo)內(nèi)存頁(yè)在物理內(nèi)存中沒(méi)有對(duì)應(yīng)的頁(yè)幀，或者存在但無(wú)對(duì)應(yīng)權(quán)限，CPU 就無(wú)法獲取數(shù)據(jù)，這種情況下CPU就會(huì)報(bào)告一個(gè)缺頁(yè)錯(cuò)誤。

由于CPU沒(méi)有數(shù)據(jù)就無(wú)法進(jìn)行計(jì)算，CPU罷工了用戶進(jìn)程也就出現(xiàn)了缺頁(yè)中斷，進(jìn)程會(huì)從用戶態(tài)切換到內(nèi)核態(tài)，并將缺頁(yè)中斷交給內(nèi)核的 Page Fault Handler 處理。

缺頁(yè)中斷會(huì)交給PageFaultHandler處理，其根據(jù)缺頁(yè)中斷的不同類型會(huì)進(jìn)行不同的處理：

• Hard Page Fault
  也被稱為Major Page Fault，翻譯為硬缺頁(yè)錯(cuò)誤/主要缺頁(yè)錯(cuò)誤，這時(shí)物理內(nèi)存中沒(méi)有對(duì)應(yīng)的頁(yè)幀，需要CPU打開(kāi)磁盤(pán)設(shè)備讀取到物理內(nèi)存中，再讓MMU建立VA和PA的映射。

• Soft Page Fault
  也被稱為Minor Page Fault，翻譯為軟缺頁(yè)錯(cuò)誤/次要缺頁(yè)錯(cuò)誤，這時(shí)物理內(nèi)存中是存在對(duì)應(yīng)頁(yè)幀的，只不過(guò)可能是其他進(jìn)程調(diào)入的，發(fā)出缺頁(yè)異常的進(jìn)程不知道而已，此時(shí)MMU只需要建立映射即可，無(wú)需從磁盤(pán)讀取寫(xiě)入內(nèi)存，一般出現(xiàn)在多進(jìn)程共享內(nèi)存區(qū)域。

• Invalid Page Fault
  翻譯為無(wú)效缺頁(yè)錯(cuò)誤，比如進(jìn)程訪問(wèn)的內(nèi)存地址越界訪問(wèn)，又比如對(duì)空指針解引用內(nèi)核就會(huì)報(bào)segment fault錯(cuò)誤中斷進(jìn)程直接掛掉。

不同類型的Page Fault出現(xiàn)的原因也不一樣，常見(jiàn)的幾種原因包括：

• 非法操作訪問(wèn)越界
  這種情況產(chǎn)生的影響也是最大的，也是Coredump的重要來(lái)源，比如空指針解引用或者權(quán)限問(wèn)題等都會(huì)出現(xiàn)缺頁(yè)錯(cuò)誤。

• 使用malloc新申請(qǐng)內(nèi)存
  malloc機(jī)制是延時(shí)分配內(nèi)存，當(dāng)使用malloc申請(qǐng)內(nèi)存時(shí)并未真實(shí)分配物理內(nèi)存，等到真正開(kāi)始使用malloc申請(qǐng)的物理內(nèi)存時(shí)發(fā)現(xiàn)沒(méi)有才會(huì)啟動(dòng)申請(qǐng)，期間就會(huì)出現(xiàn)Page Fault。

• 訪問(wèn)數(shù)據(jù)被swap換出
  物理內(nèi)存是有限資源，當(dāng)運(yùn)行很多進(jìn)程時(shí)并不是每個(gè)進(jìn)程都活躍，對(duì)此OS會(huì)啟動(dòng)內(nèi)存頁(yè)面置換將長(zhǎng)時(shí)間未使用的物理內(nèi)存頁(yè)幀放到swap分區(qū)來(lái)騰空資源給其他進(jìn)程，當(dāng)存在于swap分區(qū)的頁(yè)面被訪問(wèn)時(shí)就會(huì)觸發(fā)Page Fault從而再置換回物理內(nèi)存。

本段小結(jié) 敲黑板 劃重點(diǎn)
缺頁(yè)異常在虛擬機(jī)制下是必然會(huì)出現(xiàn)的，原因非常多，沒(méi)什么大不了的，在缺頁(yè)異常的配合下合法的內(nèi)存訪問(wèn)才能得到響應(yīng)。

我們基本弄清楚了為什么需要內(nèi)存管理、虛擬內(nèi)存機(jī)制主要做什么、虛擬機(jī)制下數(shù)據(jù)的讀寫(xiě)流程等等。

內(nèi)存分配

虛擬機(jī)制下每個(gè)進(jìn)程都有獨(dú)立的地址空間，并且地址空間被劃分為了很多部分，如圖為32位系統(tǒng)中虛擬地址空間分配：

64位系統(tǒng)也是類似的，只不過(guò)對(duì)應(yīng)的空間都擴(kuò)大為128TB。

下面來(lái)看看各個(gè)段各自特點(diǎn)和相互聯(lián)系：

• text段包含了當(dāng)前運(yùn)行進(jìn)程的二進(jìn)制代碼，所以又被稱為代碼段，在32位和64位系統(tǒng)中代碼段的起始地址都是確定的，并且大小也是確定的。

• data段存儲(chǔ)已初始化的全局變量，和text段緊挨著，中間沒(méi)有空隙，因此起始地址也是固定的，大小也是確定的。

• bss段存儲(chǔ)未初始化的全局變量，和data段緊挨著，中間沒(méi)有空隙，因此起始地址也是固定的，大小也是確定的。

• heap段和bss段并不是緊挨著的，中間會(huì)有一個(gè)隨機(jī)的偏移量，heap段的起始地址也被稱為start_brk，由于heap段是動(dòng)態(tài)的，頂部位置稱為program break brk。

• 在heap段上方是內(nèi)存映射段，該段是mmap系統(tǒng)調(diào)用映射出來(lái)的，該段的大小也是不確定的，并且?jiàn)A在heap段和stack段中間，該段的起始地址也是不確定的。

• stack段算是用戶空間地址最高的一部分了，它也并沒(méi)有和內(nèi)核地址空間緊挨著，中間有隨機(jī)偏移量，同時(shí)一般stack段會(huì)設(shè)置最大值RLIMIT_STACK(比如8MB)，在之下再加上一個(gè)隨機(jī)偏移量就是內(nèi)存映射段的起始地址了。

看到這里，大家可能暈了我們抓住幾點(diǎn)：

• 進(jìn)程虛擬空間的各個(gè)段，并非緊挨著，也就是有的段的起始地址并不確定，大小也并不確定
• 隨機(jī)的地址是為了防止黑客的攻擊，因?yàn)楣潭ǖ牡刂繁还綦y度低很多

我把heap段、stack段、mmap段再細(xì)化一張圖：

從圖上我們可以看到各個(gè)段的布局關(guān)系和隨機(jī)偏移量的使用，多看幾遍就清楚啦！

內(nèi)存區(qū)域的組織

從前面可以看到進(jìn)程虛擬空間就是一塊塊不同區(qū)域的集合，這些區(qū)域就是我們上面的段，每個(gè)區(qū)域在Linux系統(tǒng)中使用vm_area_struct這個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)表示的。

內(nèi)核為每個(gè)進(jìn)程維護(hù)了一個(gè)單獨(dú)的任務(wù)結(jié)構(gòu)task_strcut，該結(jié)構(gòu)中包含了進(jìn)程運(yùn)行時(shí)所需的全部信息，其中有一個(gè)內(nèi)存管理(memory manage)相關(guān)的成員結(jié)構(gòu)mm_struct：

struct?mm_struct??*mm;
struct?mm_struct??*active_mm;

結(jié)構(gòu)mm_strcut的成員非常多，其中g(shù)pd和mmap是我們需要關(guān)注的：

• pgd指向第一級(jí)頁(yè)表的基地址，是實(shí)現(xiàn)虛擬地址和物理地址的重要部分
• mmap指向一個(gè)雙向鏈表，鏈表節(jié)點(diǎn)是vm_area_struct結(jié)構(gòu)體，vm_area_struct描述了虛擬空間中的一個(gè)區(qū)域
• mm_rb指向一個(gè)紅黑樹(shù)的根結(jié)點(diǎn)，節(jié)點(diǎn)結(jié)構(gòu)也是vm_area_struct

我們看下vm_area_struct的結(jié)構(gòu)體定義，后面要用到，注意看哈：

vm_area_start作為鏈表節(jié)點(diǎn)串聯(lián)在一起，每個(gè)vm_area_struct表示一個(gè)虛擬內(nèi)存區(qū)域，由其中的vm_start和vm_end指向了該區(qū)域的起始地址和結(jié)束地址，這樣多個(gè)vm_area_struct就將進(jìn)程的多個(gè)段組合在一起了。

我們同時(shí)注意到vm_area_struct的結(jié)構(gòu)體定義中有rb_node的相關(guān)成員，不過(guò)有的版本內(nèi)核是AVL-Tree，這樣就和mm_struct對(duì)應(yīng)起來(lái)了：

這樣vm_area_struct通過(guò)雙向鏈表和紅黑樹(shù)兩種數(shù)據(jù)結(jié)構(gòu)串聯(lián)起來(lái)，實(shí)現(xiàn)了兩種不同效率的查找，雙向鏈表用于遍歷vm_area_struct，紅黑樹(shù)用于快速查找符合條件的vm_area_struct。

內(nèi)存分配器概述

有內(nèi)存分配和回收的地方就可能有內(nèi)存分配器。

以glibc為例，我們先捋一下：

• 在用戶態(tài)層面，進(jìn)程使用庫(kù)函數(shù)malloc分配的是虛擬內(nèi)存，并且系統(tǒng)是延遲分配物理內(nèi)存的，由缺頁(yè)中斷來(lái)完成分配
• 在內(nèi)核態(tài)層面，內(nèi)核也需要物理內(nèi)存，并且使用了另外一套不同于用戶態(tài)的分配機(jī)制和系統(tǒng)調(diào)用函數(shù)

從而就引出了，今天的主線圖：

從圖中我們來(lái)闡述幾個(gè)重點(diǎn)：

• 伙伴系統(tǒng)和slab屬于內(nèi)核級(jí)別的內(nèi)存分配器，同時(shí)為內(nèi)核層面內(nèi)存分配和用戶側(cè)面內(nèi)存分配提供服務(wù)，算是終極boss的趕腳
• 內(nèi)核有自己?jiǎn)为?dú)的內(nèi)存分配函數(shù)kmalloc/vmalloc，和用戶態(tài)的不一樣，畢竟是中樞機(jī)構(gòu)嘛
• 用戶態(tài)的進(jìn)程通過(guò)庫(kù)函數(shù)malloc來(lái)玩轉(zhuǎn)內(nèi)存，malloc調(diào)用了brk/mmap這兩個(gè)系統(tǒng)調(diào)用，最終觸達(dá)到伙伴系統(tǒng)實(shí)現(xiàn)內(nèi)存分配
• 內(nèi)存分配器分為兩大類：用戶態(tài)和內(nèi)核態(tài)，用戶態(tài)分配和釋放內(nèi)存最終還是通過(guò)內(nèi)核態(tài)來(lái)實(shí)現(xiàn)的，用戶態(tài)分配器更加貼合進(jìn)程需求，有種社區(qū)居委會(huì)的感覺(jué)

常見(jiàn)用戶態(tài)內(nèi)存分配器

進(jìn)程的內(nèi)存分配器工作于內(nèi)核和用戶程序之間，主要是為了實(shí)現(xiàn)用戶態(tài)的內(nèi)存管理。

分配器響應(yīng)進(jìn)程的內(nèi)存分配請(qǐng)求，向操作系統(tǒng)申請(qǐng)內(nèi)存，找到合適的內(nèi)存后返回給用戶程序，當(dāng)進(jìn)程非常多或者頻繁內(nèi)存分配釋放時(shí)，每次都找內(nèi)核老大哥要內(nèi)存/歸還內(nèi)存，可以說(shuō)十分麻煩。

總麻煩大哥，也不是個(gè)事兒，于是分配器決定自己搞管理！

• 分配器一般都會(huì)預(yù)先分配一塊大于用戶請(qǐng)求的內(nèi)存，然后管理這塊內(nèi)存
• 進(jìn)程釋放的內(nèi)存并不會(huì)立即返回給操作系統(tǒng)，分配器會(huì)管理這些釋放掉的內(nèi)存從而快速響應(yīng)后續(xù)的請(qǐng)求

說(shuō)到管理能力，每個(gè)人每個(gè)國(guó)家都有很大差別，分配器也不例外，要想管好這塊內(nèi)存也挺難的，場(chǎng)景很多要求很多，于是就出現(xiàn)了很多分配器：

• dlmalloc

dlmalloc是一個(gè)著名的內(nèi)存分配器，最早由Doug Lea在1980s年代編寫(xiě)，由于早期C庫(kù)的內(nèi)置分配器在某種程度上的缺陷，dlmalloc出現(xiàn)后立即獲得了廣泛應(yīng)用，后面很多優(yōu)秀分配器中都能看到dlmalloc的影子，可以說(shuō)是鼻祖了。

http://gee.cs.oswego.edu/dl/html/malloc.html

• ptmalloc2

ptmalloc是在dlmalloc的基礎(chǔ)上進(jìn)行了多線程改造，認(rèn)為是dlmalloc的擴(kuò)展版本，它也是目前glibc中使用的默認(rèn)分配器，不過(guò)后續(xù)各自都有不同的修改。因此，ptmalloc2和glibc中默認(rèn)分配器也并非完全一樣。

• tcmalloc

tcmalloc 出身于 Google，全稱是 thread-caching malloc，所以 tcmalloc 最大的特點(diǎn)是帶有線程緩存，tcmalloc 非常出名，目前在 Chrome、Safari 等知名產(chǎn)品中都有所應(yīng)有。
tcmalloc 為每個(gè)線程分配了一個(gè)局部緩存，對(duì)于小對(duì)象的分配，可以直接由線程局部緩存來(lái)完成，對(duì)于大對(duì)象的分配場(chǎng)景，tcmalloc 嘗試采用自旋鎖來(lái)減少多線程的鎖競(jìng)爭(zhēng)問(wèn)題。

• jemalloc

jemalloc 是由 Jason Evans 在 FreeBSD 項(xiàng)目中引入的新一代內(nèi)存分配器。
它是一個(gè)通用的 malloc 實(shí)現(xiàn)，側(cè)重于減少內(nèi)存碎片和提升高并發(fā)場(chǎng)景下內(nèi)存的分配效率，其目標(biāo)是能夠替代 malloc。
jemalloc 應(yīng)用十分廣泛，在 Firefox、Redis、Rust、Netty 等出名的產(chǎn)品或者編程語(yǔ)言中都有大量使用。
具體細(xì)節(jié)可以參考 Jason Evans 發(fā)表的論文 《A Scalable Concurrent malloc Implementation for FreeBSD》

論文鏈接：https://www.bsdcan.org/2006/papers/jemalloc.pdf

glibc malloc原理分析

我們?cè)谑褂胢alloc進(jìn)行內(nèi)存分配，malloc只是glibc提供的庫(kù)函數(shù)，它仍然會(huì)調(diào)用其他函數(shù)從而最終觸達(dá)到物理內(nèi)存，所以是個(gè)很長(zhǎng)的鏈路。

我們先來(lái)看下malloc的特點(diǎn)：

• malloc 申請(qǐng)分配指定size個(gè)字節(jié)的內(nèi)存空間，返回類型是 void* 類型，但是此時(shí)的內(nèi)存只是虛擬空間內(nèi)的連續(xù)內(nèi)存，無(wú)法保證物理內(nèi)存連續(xù)
• mallo并不關(guān)心進(jìn)程用申請(qǐng)的內(nèi)存來(lái)存儲(chǔ)什么類型的數(shù)據(jù)，void*類型可以強(qiáng)制轉(zhuǎn)換為任何其它類型的指針，從而做到通用性

/*?malloc?example?*/
#include?
#include?

int?main?()
{
??int?i,n;
??char?*?buffer;
??scanf?("%d",?&i);

??buffer?=?(char*)?malloc?(i+1);
??if?(buffer==NULL)?exit?(1);

??for?(n=0;?n'a';
??buffer[i]='';
??free?(buffer);
??return?0;
}

上面是malloc作為庫(kù)函數(shù)和用戶交互的部分，如果不深究原理，掌握上面這些就可以使用malloc了，但是對(duì)于我們這些追求極致的人來(lái)說(shuō)，還遠(yuǎn)遠(yuǎn)不夠。

繼續(xù)看下 malloc是如何觸達(dá)到物理內(nèi)存的：

#include?
int?brk(void?*addr);
void?*sbrk(intptr_t?increment);

• brk函數(shù)將break指針直接設(shè)置為某個(gè)地址，相當(dāng)于絕對(duì)值
• sbrk將break指針從當(dāng)前位置移動(dòng)increment所指定的增量，相當(dāng)于相對(duì)值
• 本質(zhì)上brk和sbrk作用是一樣的都是移動(dòng)break指針的位置來(lái)擴(kuò)展內(nèi)存

畫(huà)外音：我原來(lái)以為sbrk是brk的什么safe版本，還真是無(wú)知了

#include?
void?*mmap(void?*addr,?size\_t?length,?int?prot,?int?flags,?int?fd,?off\_t?offset);
int?munmap(void?*addr,?size_t?length);

• mmap和munmap是一對(duì)函數(shù)，一個(gè)負(fù)責(zé)申請(qǐng)，一個(gè)負(fù)責(zé)釋放
• mmap有兩個(gè)功能：實(shí)現(xiàn)文件映射到內(nèi)存區(qū)域 和 分配匿名內(nèi)存區(qū)域，在malloc中使用的就是匿名內(nèi)存分配，從而為程序存放數(shù)據(jù)開(kāi)辟空間

malloc底層數(shù)據(jù)結(jié)構(gòu)

malloc的核心工作就是組織管理內(nèi)存，高效響應(yīng)進(jìn)程的內(nèi)存使用需求，同時(shí)保證內(nèi)存的使用率，降低內(nèi)存碎片化。

那么，malloc是如何解決這些問(wèn)題的？

malloc為了解決這些問(wèn)題，采用了多種數(shù)據(jù)結(jié)構(gòu)和策略來(lái)實(shí)現(xiàn)內(nèi)存分配，這就是我們接下來(lái)研究的事情：

• 什么樣的數(shù)據(jù)結(jié)構(gòu)
• 什么樣的組織策略

事情沒(méi)有一蹴而就，我們很難理解內(nèi)存分配器設(shè)計(jì)者面臨的復(fù)雜問(wèn)題，因此當(dāng)我們看到malloc底層復(fù)雜的設(shè)計(jì)邏輯時(shí)難免沒(méi)有頭緒，所以要忽略細(xì)節(jié)抓住主線多看幾遍。

malloc將內(nèi)存分成了大小不同的chunk，malloc將相似大小的chunk用雙向鏈表鏈接起來(lái)，這樣一個(gè)鏈表被稱為一個(gè)bin。

這些空閑的不同大小的內(nèi)存塊chunk通過(guò)bin來(lái)組織起來(lái)，換句話說(shuō)bin是空閑內(nèi)存塊chunk的容器。

malloc一共維護(hù)了128個(gè)bin，并使用一個(gè)數(shù)組來(lái)存儲(chǔ)這些bin。

malloc中128個(gè)bin的bins數(shù)組存儲(chǔ)的chunk情況如下：

• bins[0]目前沒(méi)有使用
• bins[1]的鏈表稱為unsorted_list，用于維護(hù)free釋放的chunk。
• bins[2,63]總計(jì)長(zhǎng)度為62的區(qū)間稱為small_bins，用于維護(hù)＜512B的內(nèi)存塊，其中每個(gè)bin中對(duì)應(yīng)的鏈表中的chunk大小相同，相鄰bin的大小相差8字節(jié)，范圍為16字節(jié)到504字節(jié)。

• bins[64,126]總計(jì)長(zhǎng)度為63的區(qū)間稱為large_bins，用于維護(hù)大于等于512字節(jié)的內(nèi)存塊，每個(gè)元素對(duì)應(yīng)的鏈表中的chunk大小不同，數(shù)組下標(biāo)越大鏈表中chunk的內(nèi)存越大，large bins中的每一個(gè)bin分別包含了一個(gè)給定范圍內(nèi)的chunk，其中的chunk按大小遞減排序，最后一組的largebin鏈中的chunk大小無(wú)限制，該bins的使用頻率低于small bins。

malloc有兩種特殊類型的bin：

• fast bin

malloc對(duì)于釋放的內(nèi)存并不會(huì)立刻進(jìn)行合并，如何將剛釋放的兩個(gè)相鄰小chunk合并為1個(gè)大chunk，此時(shí)進(jìn)程分配仍然是小chunk則可能還需要分割大chunk，來(lái)來(lái)回回確實(shí)很低效，于是出現(xiàn)了fast bin。

fast bin存儲(chǔ)在fastbinY數(shù)組中，一共有10個(gè)，每個(gè)fast bin都是一個(gè)單鏈表，每個(gè)單鏈表中的chunk大小是一樣的，多個(gè)鏈表的chunk大小不同，這樣在找特定大小的chunk的時(shí)候就不用挨個(gè)找，只需要計(jì)算出對(duì)應(yīng)鏈表的索引即可，提高了效率。

//?http://gee.cs.oswego.edu/pub/misc/malloc-2.7.2.c
/*?The?maximum?fastbin?request?size?we?support?*/
#define?MAX_FAST_SIZE?????80
#define?NFASTBINS??(fastbin_index(request2size(MAX_FAST_SIZE))+1)

多個(gè)fast bin鏈表存儲(chǔ)的chunk大小有16, 24, 32, 40, 48, 56, 64, 72, 80, 88字節(jié)總計(jì)10種大小。

fast bin是除tcache外優(yōu)先級(jí)最高的，如果fastbin中有滿足需求的chunk就不需要再到small bin和large bin中尋找。當(dāng)在fast bin中找到需要的chunk后還將與該chunk大小相同的所有chunk放入tcache，目的就是利用局部性原理提高下一次內(nèi)存分配的效率。

對(duì)于不超過(guò)max_fast的chunk被釋放后，首先會(huì)被放到 fast bin中，當(dāng)給用戶分配的 chunk 小于或等于 max_fast 時(shí)，malloc 首先會(huì)在 fast bin 中查找相應(yīng)的空閑塊，找不到再去找別的bin。

• unsorted bin

當(dāng)小塊或大塊內(nèi)存被釋放時(shí)，它們會(huì)被添加到 unsorted bin 里，相當(dāng)于malloc給了最近被釋放的內(nèi)存被快速二次利用的機(jī)會(huì)，在內(nèi)存分配的速度上有所提升。

當(dāng)用戶釋放的內(nèi)存大于max_fast或者fast bins合并后的chunk都會(huì)首先進(jìn)入unsorted bin上，unsorted bin中的chunk大小沒(méi)有限制。

在進(jìn)行 malloc 操作的時(shí)候，如果在 fast bins 中沒(méi)有找到合適的 chunk，則malloc 會(huì)先在 unsorted bin 中查找合適的空閑 chunk。

unsorted bin里面的chunk是最近回收的，但是并不能全部再被快速利用，因此在遍歷unsorted bins的過(guò)程中會(huì)把不同大小的chunk再分配到small bins或者large bins。

malloc在chunk和bin的結(jié)構(gòu)之上，還有兩種特殊的chunk：

• top chunk

top chunk不屬于任何bin，它是始終位于堆內(nèi)存的頂部。

當(dāng)所有的bin里的chunk都無(wú)法滿足分配要求時(shí)，malloc會(huì)從top chunk分配內(nèi)存，如果大小不合適會(huì)進(jìn)行分割，剩余部分形成新的top chunk。

如果top chunk也無(wú)法滿足用戶的請(qǐng)求，malloc只能向系統(tǒng)申請(qǐng)更多的堆空間，所以top chunk可以認(rèn)為是各種bin的后備力量，尤其在分配大內(nèi)存時(shí)，large bins也無(wú)法滿足時(shí)大哥就得頂上了。

• last remainder chunk

當(dāng)unsorted bin只有1個(gè)chunk，并且這個(gè)chunk是上次剛剛被使用過(guò)的內(nèi)存塊，那么它就是last remainder chunk。

當(dāng)進(jìn)程分配一個(gè)small chunk，在small bins中找不到合適的chunk，這時(shí)last remainder chunk就上場(chǎng)了。

• 如果last remainder chunk大于所需的small chunk大小，它會(huì)被分裂成兩個(gè)chunk，其中一個(gè)chunk返回給用戶，另一個(gè)chunk變成新的last remainder chunk。

這種特殊chunk主要用于分配內(nèi)存非常小的情況下，當(dāng)fast bin和small bin都無(wú)法滿足時(shí)，還會(huì)再次從last remainder chunk進(jìn)行分配，這樣就很好地利用了程序局部性原理。

malloc內(nèi)存分配流程

前面我們了解到malloc為了實(shí)現(xiàn)內(nèi)存的分配，采用了一些數(shù)據(jù)結(jié)構(gòu)和組織策略。接著，我們?cè)賮?lái)看看實(shí)際的內(nèi)存分配流程以及這些數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系。

在上圖中有幾個(gè)點(diǎn)需要說(shuō)明：

• 內(nèi)存釋放后，size小于max_fast則放到fast bin中，size大于max_fast則放到unsorted bin中，fast bin和unsorted bin可以看作是剛釋放內(nèi)存的容器，目的是給這些釋放內(nèi)存二次被利用的機(jī)會(huì)。

• fast bin中的fast chunk被設(shè)置為不可合并，但是如果一直不合并也就爆了，因此會(huì)定期合并fast chunk到unsorted bin中。

• unsorted bin很特殊，可以認(rèn)為是個(gè)中間過(guò)渡bin，在large bin分割chunk時(shí)也會(huì)將下腳料chunk放到unsorted bin中等待后續(xù)合并以及再分配到small bin和large bin中。

• 由于small bin和large bin鏈表很多并且大小各不相同，遍歷查找合適chunk過(guò)程是很耗時(shí)的，為此引入binmap結(jié)構(gòu)來(lái)加速查找，binmap記錄了bins的是否為空等情況，可以提高效率。

當(dāng)用戶申請(qǐng)的內(nèi)存比較小時(shí)，分配過(guò)程會(huì)比較復(fù)雜，我們?cè)賴L試梳理下該情況下的分配流程：

查找合適空閑內(nèi)存塊的過(guò)程涉及循環(huán)過(guò)程，因此把各個(gè)步驟標(biāo)記順序來(lái)表述過(guò)程。

1. 將進(jìn)程需要分配的內(nèi)存轉(zhuǎn)換為對(duì)應(yīng)空閑內(nèi)存塊的大小，記做chunk_size。
2. 當(dāng)chunk_size小于等于max_fast，則在fast bin中搜索合適的chunk，找到則返回給用戶，否則跳到第3步。
3. 當(dāng)chunk_size<=512字節(jié)，那么可能在small bin的范圍內(nèi)有合適的chunk，找到合適的則返回，否則跳到第4步。
4. 在fast bin和small bin都沒(méi)有合適的chunk，那么就對(duì)fast bin中的相鄰chunk進(jìn)行合并，合并后的更大的chunk放到unsorted bin中，跳轉(zhuǎn)到第5步。
5. 如果chunk_size屬于small bins，unsorted bin 中只有一個(gè) chunk，并且該 chunk 大于等于需要分配的大小，此時(shí)將該 chunk 進(jìn)行切割，一部分返回給用戶，另外一部分形成新的last remainder chunk分配結(jié)束，否則將 unsorted bin 中的 chunk 放入 small bins 或者 large bins，進(jìn)入第6步。
6. 現(xiàn)在看chunk_size屬于比較大的，因此在large bins進(jìn)行搜索，滿足要求則返回，否則跳到第7步。
7. 至此fast bin和另外三組bin都無(wú)法滿足要求，就輪到top chunk了，在top chunk滿足則返回，否則跳到第8步。
8. 如果chunk_size大于等于mmap分配閾值，使用mmap向內(nèi)核伙伴系統(tǒng)申請(qǐng)內(nèi)存，chunk_size小于mmap閾值則使用brk來(lái)擴(kuò)展top chunk滿足要求。

特別地，搜索合適chunk的過(guò)程中，fast bins 和small bins需要大小精確匹配，而在large bins中遵循“smallest-first，best-fit”的原則，不需要精確匹配，因此也會(huì)出現(xiàn)較多的碎片。

內(nèi)存回收

內(nèi)存回收的必要性顯而易見(jiàn)，試想一直分配不回收，當(dāng)進(jìn)程們需要新大塊內(nèi)存時(shí)，肯定就沒(méi)內(nèi)存可用了。為此，內(nèi)存回收必須要搞起來(lái)。

頁(yè)面回收

內(nèi)存回收就是釋放掉比如緩存和緩沖區(qū)的內(nèi)存，通常他們被稱為文件頁(yè)page cache，對(duì)于通過(guò)mmap生成的用于存放程序數(shù)據(jù)而非文件數(shù)據(jù)的內(nèi)存頁(yè)稱為匿名頁(yè)。

• 文件頁(yè) 有外部的文件介質(zhì)形成映射關(guān)系
• 匿名頁(yè) 沒(méi)有外部的文件形成映射關(guān)系

這兩種物理頁(yè)面在某些情況下是可以回收的，但是處理方式并不同。

文件頁(yè)回收

page cache常被用于緩沖磁盤(pán)文件的數(shù)據(jù)，讓磁盤(pán)數(shù)據(jù)放到內(nèi)存中來(lái)實(shí)現(xiàn)CPU的快速訪問(wèn)。

page cache中有非常多page frame，要回收這些page frame需要確定這些物理頁(yè)是否還在用，為了解決這個(gè)問(wèn)題出現(xiàn)了反向映射技術(shù)。

正向映射是通過(guò)虛擬地址根據(jù)頁(yè)表找到物理內(nèi)存，反向映射就是通過(guò)物理地址找到哪些虛擬地址使用它，也就是當(dāng)我們?cè)跊Q定page frame是否可以回收時(shí)，需要使用反向映射來(lái)查看哪些進(jìn)程被映射到這塊物理頁(yè)了，進(jìn)一步判斷是否可以回收。

反向映射技術(shù)最早并沒(méi)有在內(nèi)核中出現(xiàn)，從誕生到被廣泛推廣也經(jīng)歷了很多波折，并且細(xì)節(jié)很多，要展開(kāi)說(shuō)估計(jì)還得萬(wàn)八千字，所以我找了一篇關(guān)于反向映射很棒的文章：

https://cclinuxer.github.io/2020/11/Linux%E5%8F%8D%E5%90%91%E6%98%A0%E5%B0%84%E6%9C%BA%E5%88%B6/

找到可以回收的page frame之后內(nèi)核使用LRU算法進(jìn)行回收，Linux采用的方法是維護(hù)2個(gè)雙向鏈表，一個(gè)是包含了最近使用頁(yè)面的active list，另一個(gè)是包含了最近不使用頁(yè)面的inactive list。

• active_list 活躍內(nèi)存頁(yè)鏈表，這里存放的是最近被訪問(wèn)過(guò)的內(nèi)存頁(yè)，屬于安全區(qū)。
• inactive_list 不活躍內(nèi)存頁(yè)鏈表，這里存放的是很少被訪問(wèn)的內(nèi)存頁(yè)，屬于毒區(qū)。

匿名頁(yè)回收

匿名頁(yè)沒(méi)有對(duì)應(yīng)的文件形成映射，因此也就沒(méi)有像磁盤(pán)那樣的低速備份。

在回收匿名頁(yè)的時(shí)候，需要先保存匿名頁(yè)上的內(nèi)容到特定區(qū)域，這樣才能避免數(shù)據(jù)丟失保證后續(xù)的訪問(wèn)。

匿名頁(yè)在進(jìn)程中是非常普遍的，動(dòng)態(tài)分配的堆內(nèi)存都可以說(shuō)是匿名頁(yè)，Linux為回收匿名頁(yè)，特地開(kāi)辟了swap space來(lái)存儲(chǔ)內(nèi)存上的數(shù)據(jù)，關(guān)于swap機(jī)制的文章太多了，這算是個(gè)常識(shí)的東西了，所以本文不啰嗦啦！

內(nèi)核傾向于回收page cache中的物理頁(yè)面，只有當(dāng)內(nèi)存很緊張并且內(nèi)核配置允許swap機(jī)制時(shí)，才會(huì)選擇回收匿名頁(yè)。

回收匿名頁(yè)意味著將數(shù)據(jù)放到了低速設(shè)備，一旦被訪問(wèn)性能損耗也很大，因此現(xiàn)在大內(nèi)存的物理機(jī)器經(jīng)常關(guān)閉swap來(lái)提高性能。

kswapd線程和waterMark

NUMA架構(gòu)下每個(gè)CPU都有自己的本地內(nèi)存來(lái)加速訪問(wèn)避免總線擁擠，在本地內(nèi)存不足時(shí)又可以訪問(wèn)其他Node的內(nèi)存，但是訪問(wèn)速度會(huì)下降。

每個(gè)CPU加本地內(nèi)存被稱作Node，一個(gè)node又被劃分為多個(gè)zone，每個(gè)zone有自己一套內(nèi)存水位標(biāo)記，來(lái)記錄本zone的內(nèi)存水平，同時(shí)每個(gè)node有一個(gè)kswapd內(nèi)核線程來(lái)回收內(nèi)存。

Linux內(nèi)核中有一個(gè)非常重要的內(nèi)核線程kswapd，負(fù)責(zé)在內(nèi)存不足的情況下回收頁(yè)面，系統(tǒng)初始化時(shí)，會(huì)為每一個(gè)NUMA內(nèi)存節(jié)點(diǎn)創(chuàng)建一個(gè)名為kswapd的內(nèi)核線程。

在內(nèi)存不足時(shí)內(nèi)核通過(guò)wakeup_kswapd()函數(shù)喚醒kswapd內(nèi)核線程來(lái)回收頁(yè)面，以便釋放一些內(nèi)存，kswapd的回收方式又被稱為background reclaim。

Linux內(nèi)核使用水位標(biāo)記（watermark）的概念來(lái)描述這個(gè)壓力情況。

Linux為內(nèi)存的使用設(shè)置了三種內(nèi)存水位標(biāo)記，high、low、min，當(dāng)內(nèi)存處于不同階段會(huì)觸發(fā)不同的內(nèi)存回收機(jī)制，來(lái)保證內(nèi)存的供應(yīng)，如下圖所示：

他們所標(biāo)記的分別含義為：

• 水位線在high以上表示內(nèi)存剩余較多，目前內(nèi)存使用壓力不大，kswapd處于休眠狀態(tài)

• 水位線在high-low的范圍表示目前雖然還有剩余內(nèi)存但是有點(diǎn)緊張，kswapd開(kāi)始工作進(jìn)行內(nèi)存回收

• 水位線在low-min表示剩余可用內(nèi)存不多了壓力山大，min是最小的水位標(biāo)記，當(dāng)剩余內(nèi)存達(dá)到這個(gè)狀態(tài)時(shí)，就說(shuō)明內(nèi)存面臨很大壓力。

• 水位線低于min這部分內(nèi)存，就會(huì)觸發(fā)直接回收內(nèi)存。

OOM機(jī)制

OOM(Out Of Memory)是Linux內(nèi)核在可用內(nèi)存較少或者某個(gè)進(jìn)程瞬間申請(qǐng)并使用超額的內(nèi)存，此時(shí)空閑的物理內(nèi)存是遠(yuǎn)遠(yuǎn)不夠的，此時(shí)就會(huì)觸發(fā)OOM。

為了保證其他進(jìn)程兄弟們能正常跑，內(nèi)核會(huì)讓OOM Killer根據(jù)設(shè)置參數(shù)和策略選擇認(rèn)為最值得被殺死的進(jìn)程，殺掉它然后釋放內(nèi)存來(lái)保證大盤(pán)的穩(wěn)定。

OOM Killer這個(gè)殺手很多時(shí)候不夠智慧，經(jīng)常會(huì)遇到進(jìn)程A是個(gè)重要程序，正在歡快穩(wěn)定的跑著，此時(shí)殺出來(lái)個(gè)進(jìn)程B，瞬間要申請(qǐng)大量?jī)?nèi)存，Linux發(fā)現(xiàn)滿足不了這個(gè)程咬金，于是就祭出大招OOM Killer，但是結(jié)果卻是把進(jìn)程A給殺了。

在oom的源碼中可以看到，作者關(guān)于如何選擇最優(yōu)進(jìn)程的一些說(shuō)明：

https://github.com/torvalds/linux/blob/master/mm/oom_kill.c

oom_killer在選擇最優(yōu)進(jìn)程時(shí)決策并不完美，只是做到了"還行"，根據(jù)策略對(duì)進(jìn)程打分，選擇分?jǐn)?shù)最高的進(jìn)程殺掉。

具體的計(jì)算在oom_badness函數(shù)中進(jìn)行的，如下為分?jǐn)?shù)的計(jì)算：

其中涉及進(jìn)程正在使用的物理內(nèi)存RSS+swap分區(qū)+頁(yè)面緩沖，再對(duì)比總內(nèi)存大小，同時(shí)還有一些配置來(lái)避免殺死最重要的進(jìn)程。

進(jìn)程設(shè)置OOM_SCORE_ADJ_MIN時(shí)，說(shuō)明該進(jìn)程為不可被殺死，返回的得分就非常低，從而被oom killer豁免。

總結(jié)

本文首先介紹虛擬內(nèi)存機(jī)制產(chǎn)生的原因，以及Linux虛擬內(nèi)存機(jī)制的基本原理、同時(shí)引入了實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)和段頁(yè)機(jī)制。

其次重點(diǎn)介紹了內(nèi)存分配器、并以glibc的malloc為藍(lán)本講述該內(nèi)存分配器采用何種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)空閑內(nèi)存管理。

最后闡述內(nèi)存回收的原理，介紹了匿名頁(yè)和文件頁(yè)的回收差異性，同時(shí)介紹了kswapd內(nèi)核線程和內(nèi)存watermark機(jī)制。

由于篇幅和能力所限，本文只能給出一條主線來(lái)展示內(nèi)存如何被組織、使用、回收等。如果不是內(nèi)核開(kāi)發(fā)人員，單純的業(yè)務(wù)開(kāi)發(fā)人員足以應(yīng)付面試和日常工作。

最后，感謝大家的耐心閱讀！如果覺(jué)得文章有用，麻煩幫忙點(diǎn)個(gè)贊。