前言

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

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

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

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

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

虛擬內(nèi)存機制

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

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

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

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

進程空間隔離問題

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

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

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

所以，我們需要的是每個進程有獨立且隔離的安全空間。

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

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

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

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

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

定位調(diào)試和編譯運行問題

由于程序運行時的位置是不確定的，我們在定位問題、調(diào)試代碼、編譯執(zhí)行時都會存在很多問題。

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

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

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

中間層的引入

大家一定聽過這句計算機諺語：

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

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

Linux的虛擬內(nèi)存機制簡單來說就是在物理內(nèi)存和進程之間請了個管家，內(nèi)存管家上任之后做了以下幾件事情：

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

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

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

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

頁表的存儲和檢索問題

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

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

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

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

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

可見，頁表級數(shù)越多查詢的步驟越多，對于CPU來說等待時間越長，效率越低，這個問題還需要優(yōu)化才行。

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

MMU和TLB這對黃金搭檔

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

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

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

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

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

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

本段小結(jié) 敲黑板 劃重點
MMU也是個聰明的家伙，集成了TLB來存儲CPU最近常用的頁表項來加速尋址，TLB找不到再去全量頁表尋址，可以認(rèn)為TLB是MMU的緩存。

缺頁異常來了

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

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

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

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

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

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

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

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

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

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

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

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

內(nèi)存分配

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

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

下面來看看各個段各自特點和相互聯(lián)系：

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

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

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

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

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

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

看到這里，大家可能暈了我們抓住幾點：

• 進程虛擬空間的各個段，并非緊挨著，也就是有的段的起始地址并不確定，大小也并不確定
• 隨機的地址是為了防止黑客的攻擊，因為固定的地址被攻擊難度低很多

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

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

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

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

內(nèi)核為每個進程維護了一個單獨的任務(wù)結(jié)構(gòu)task_strcut，該結(jié)構(gòu)中包含了進程運行時所需的全部信息，其中有一個內(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指向第一級頁表的基地址，是實現(xiàn)虛擬地址和物理地址的重要部分
• mmap指向一個雙向鏈表，鏈表節(jié)點是vm_area_struct結(jié)構(gòu)體，vm_area_struct描述了虛擬空間中的一個區(qū)域
• mm_rb指向一個紅黑樹的根結(jié)點，節(jié)點結(jié)構(gòu)也是vm_area_struct

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

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

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

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

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

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

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

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

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

從圖中我們來闡述幾個重點：

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

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

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

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

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

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

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

• dlmalloc

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

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

• ptmalloc2

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

• tcmalloc

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

• jemalloc

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

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

glibc malloc原理分析

我們在使用malloc進行內(nèi)存分配，malloc只是glibc提供的庫函數(shù)，它仍然會調(diào)用其他函數(shù)從而最終觸達到物理內(nèi)存，所以是個很長的鏈路。

我們先來看下malloc的特點：

• malloc 申請分配指定size個字節(jié)的內(nèi)存空間，返回類型是 void* 類型，但是此時的內(nèi)存只是虛擬空間內(nèi)的連續(xù)內(nèi)存，無法保證物理內(nèi)存連續(xù)
• mallo并不關(guān)心進程用申請的內(nèi)存來存儲什么類型的數(shù)據(jù)，void*類型可以強制轉(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作為庫函數(shù)和用戶交互的部分，如果不深究原理，掌握上面這些就可以使用malloc了，但是對于我們這些追求極致的人來說，還遠(yuǎn)遠(yuǎn)不夠。

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

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

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

畫外音：我原來以為sbrk是brk的什么safe版本，還真是無知了

#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是一對函數(shù)，一個負(fù)責(zé)申請，一個負(fù)責(zé)釋放
• mmap有兩個功能：實現(xiàn)文件映射到內(nèi)存區(qū)域 和 分配匿名內(nèi)存區(qū)域，在malloc中使用的就是匿名內(nèi)存分配，從而為程序存放數(shù)據(jù)開辟空間

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

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

那么，malloc是如何解決這些問題的？

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

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

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

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

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

malloc一共維護了128個bin，并使用一個數(shù)組來存儲這些bin。

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

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

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

malloc有兩種特殊類型的bin：

• fast bin

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

fast bin存儲在fastbinY數(shù)組中，一共有10個，每個fast bin都是一個單鏈表，每個單鏈表中的chunk大小是一樣的，多個鏈表的chunk大小不同，這樣在找特定大小的chunk的時候就不用挨個找，只需要計算出對應(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)

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

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

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

• unsorted bin

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

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

在進行 malloc 操作的時候，如果在 fast bins 中沒有找到合適的 chunk，則malloc 會先在 unsorted bin 中查找合適的空閑 chunk。

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

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

• top chunk

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

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

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

• last remainder chunk

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

當(dāng)進程分配一個small chunk，在small bins中找不到合適的chunk，這時last remainder chunk就上場了。

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

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

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

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

在上圖中有幾個點需要說明：

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

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

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

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

當(dāng)用戶申請的內(nèi)存比較小時，分配過程會比較復(fù)雜，我們再嘗試梳理下該情況下的分配流程：

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

1. 將進程需要分配的內(nèi)存轉(zhuǎn)換為對應(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都沒有合適的chunk，那么就對fast bin中的相鄰chunk進行合并，合并后的更大的chunk放到unsorted bin中，跳轉(zhuǎn)到第5步。
5. 如果chunk_size屬于small bins，unsorted bin 中只有一個 chunk，并且該 chunk 大于等于需要分配的大小，此時將該 chunk 進行切割，一部分返回給用戶，另外一部分形成新的last remainder chunk分配結(jié)束，否則將 unsorted bin 中的 chunk 放入 small bins 或者 large bins，進入第6步。
6. 現(xiàn)在看chunk_size屬于比較大的，因此在large bins進行搜索，滿足要求則返回，否則跳到第7步。
7. 至此fast bin和另外三組bin都無法滿足要求，就輪到top chunk了，在top chunk滿足則返回，否則跳到第8步。
8. 如果chunk_size大于等于mmap分配閾值，使用mmap向內(nèi)核伙伴系統(tǒng)申請內(nèi)存，chunk_size小于mmap閾值則使用brk來擴展top chunk滿足要求。

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

內(nèi)存回收

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

頁面回收

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

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

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

文件頁回收

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

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

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

反向映射技術(shù)最早并沒有在內(nèi)核中出現(xiàn)，從誕生到被廣泛推廣也經(jīng)歷了很多波折，并且細(xì)節(jié)很多，要展開說估計還得萬八千字，所以我找了一篇關(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算法進行回收，Linux采用的方法是維護2個雙向鏈表，一個是包含了最近使用頁面的active list，另一個是包含了最近不使用頁面的inactive list。

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

匿名頁回收

匿名頁沒有對應(yīng)的文件形成映射，因此也就沒有像磁盤那樣的低速備份。

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

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

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

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

kswapd線程和waterMark

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

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

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

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

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

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

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

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

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

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

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

OOM機制

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

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

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

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

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

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

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

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

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

總結(jié)

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

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

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

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

最后，感謝大家的耐心閱讀！如果覺得文章有用，麻煩幫忙點個贊。