前言

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

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

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

通過本文你將了解到以下內容：

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

虛擬內存機制

當要學習一個新知識點時，比較好的過程是先理解出現這個技術點的背景原因，同期其他解決方案，新技術點解決了什么問題以及它存在哪些不足和改進之處，這樣整個學習過程是閉環的。

內存為什么需要管理

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

Linux系統如果以一種原始簡單的方式管理內存是存在一些問題：

進程空間隔離問題

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

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

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

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

內存效率低下問題

機器的內存是有限資源，而進程數量是動態且無法確定的，這樣就會出現幾個必須要考慮的問題：

• 如果已經啟動的進程們占據了幾乎所有內存空間，沒有新內存可分配了，此時新進程將無法啟動。

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

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

定位調試和編譯運行問題

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

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

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

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

中間層的引入

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

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

計算機科學領域的任何問題都可以通過增加一個中間層來解決，解決內存問題也不例外。

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

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

虛擬內存下數據讀寫問題

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

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

頁表的存儲和檢索問題

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

當機器的物理內存越來越大，頁表這個地圖也將非常大，于是問題出現了：

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

我們以2級頁表為例，MMU要先進行兩次頁表查詢確定物理地址，在確認了權限等問題后，MMU再將這個物理地址發送到總線，內存收到之后開始讀取對應地址的數據并返回。

MMU在2級頁表的情況下進行了2次檢索和1次讀寫，那么當頁表變為N級時，就變成了N次檢索+1次讀寫。

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

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

MMU和TLB這對黃金搭檔

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

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

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

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

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

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

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

缺頁異常來了

假如目標內存頁在物理內存中沒有對應的頁幀，或者存在但無對應權限，CPU 就無法獲取數據，這種情況下CPU就會報告一個缺頁錯誤。

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

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

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

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

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

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

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

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

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

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

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

內存分配

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

64位系統也是類似的，只不過對應的空間都擴大為128TB。

下面來看看各個段各自特點和相互聯系：

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

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

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

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

• 在heap段上方是內存映射段，該段是mmap系統調用映射出來的，該段的大小也是不確定的，并且夾在heap段和stack段中間，該段的起始地址也是不確定的。

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

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

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

我把heap段、stack段、mmap段再細化一張圖：

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

內存區域的組織

從前面可以看到進程虛擬空間就是一塊塊不同區域的集合，這些區域就是我們上面的段，每個區域在Linux系統中使用vm_area_struct這個數據結構來表示的。

內核為每個進程維護了一個單獨的任務結構task_strcut，該結構中包含了進程運行時所需的全部信息，其中有一個內存管理(memory manage)相關的成員結構mm_struct：

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

結構mm_strcut的成員非常多，其中gpd和mmap是我們需要關注的：

• pgd指向第一級頁表的基地址，是實現虛擬地址和物理地址的重要部分
• mmap指向一個雙向鏈表，鏈表節點是vm_area_struct結構體，vm_area_struct描述了虛擬空間中的一個區域
• mm_rb指向一個紅黑樹的根結點，節點結構也是vm_area_struct

我們看下vm_area_struct的結構體定義，后面要用到，注意看哈：

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

我們同時注意到vm_area_struct的結構體定義中有rb_node的相關成員，不過有的版本內核是AVL-Tree，這樣就和mm_struct對應起來了：

這樣vm_area_struct通過雙向鏈表和紅黑樹兩種數據結構串聯起來，實現了兩種不同效率的查找，雙向鏈表用于遍歷vm_area_struct，紅黑樹用于快速查找符合條件的vm_area_struct。

內存分配器概述

有內存分配和回收的地方就可能有內存分配器。

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

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

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

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

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

常見用戶態內存分配器

進程的內存分配器工作于內核和用戶程序之間，主要是為了實現用戶態的內存管理。

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

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

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

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

• dlmalloc

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

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

• ptmalloc2

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

• tcmalloc

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

• jemalloc

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

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

glibc malloc原理分析

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

我們先來看下malloc的特點：

• malloc 申請分配指定size個字節的內存空間，返回類型是 void* 類型，但是此時的內存只是虛擬空間內的連續內存，無法保證物理內存連續
• mallo并不關心進程用申請的內存來存儲什么類型的數據，void*類型可以強制轉換為任何其它類型的指針，從而做到通用性

/*?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作為庫函數和用戶交互的部分，如果不深究原理，掌握上面這些就可以使用malloc了，但是對于我們這些追求極致的人來說，還遠遠不夠。

繼續看下 malloc是如何觸達到物理內存的：

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

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

畫外音：我原來以為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是一對函數，一個負責申請，一個負責釋放
• mmap有兩個功能：實現文件映射到內存區域 和 分配匿名內存區域，在malloc中使用的就是匿名內存分配，從而為程序存放數據開辟空間

malloc底層數據結構

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

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

malloc為了解決這些問題，采用了多種數據結構和策略來實現內存分配，這就是我們接下來研究的事情：

• 什么樣的數據結構
• 什么樣的組織策略

事情沒有一蹴而就，我們很難理解內存分配器設計者面臨的復雜問題，因此當我們看到malloc底層復雜的設計邏輯時難免沒有頭緒，所以要忽略細節抓住主線多看幾遍。

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

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

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

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

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

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

malloc有兩種特殊類型的bin：

• fast bin

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

fast bin存儲在fastbinY數組中，一共有10個，每個fast bin都是一個單鏈表，每個單鏈表中的chunk大小是一樣的，多個鏈表的chunk大小不同，這樣在找特定大小的chunk的時候就不用挨個找，只需要計算出對應鏈表的索引即可，提高了效率。

//?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字節總計10種大小。

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

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

• unsorted bin

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

當用戶釋放的內存大于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的結構之上，還有兩種特殊的chunk：

• top chunk

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

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

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

• last remainder chunk

當unsorted bin只有1個chunk，并且這個chunk是上次剛剛被使用過的內存塊，那么它就是last remainder chunk。

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

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

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

malloc內存分配流程

前面我們了解到malloc為了實現內存的分配，采用了一些數據結構和組織策略。接著，我們再來看看實際的內存分配流程以及這些數據結構之間的關系。

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

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

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

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

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

當用戶申請的內存比較小時，分配過程會比較復雜，我們再嘗試梳理下該情況下的分配流程：

查找合適空閑內存塊的過程涉及循環過程，因此把各個步驟標記順序來表述過程。

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

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

內存回收

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

頁面回收

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

• 文件頁 有外部的文件介質形成映射關系
• 匿名頁 沒有外部的文件形成映射關系

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

文件頁回收

page cache常被用于緩沖磁盤文件的數據，讓磁盤數據放到內存中來實現CPU的快速訪問。

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

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

反向映射技術最早并沒有在內核中出現，從誕生到被廣泛推廣也經歷了很多波折，并且細節很多，要展開說估計還得萬八千字，所以我找了一篇關于反向映射很棒的文章：

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之后內核使用LRU算法進行回收，Linux采用的方法是維護2個雙向鏈表，一個是包含了最近使用頁面的active list，另一個是包含了最近不使用頁面的inactive list。

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

匿名頁回收

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

在回收匿名頁的時候，需要先保存匿名頁上的內容到特定區域，這樣才能避免數據丟失保證后續的訪問。

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

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

回收匿名頁意味著將數據放到了低速設備，一旦被訪問性能損耗也很大，因此現在大內存的物理機器經常關閉swap來提高性能。

kswapd線程和waterMark

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

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

Linux內核中有一個非常重要的內核線程kswapd，負責在內存不足的情況下回收頁面，系統初始化時，會為每一個NUMA內存節點創建一個名為kswapd的內核線程。

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

Linux內核使用水位標記（watermark）的概念來描述這個壓力情況。

Linux為內存的使用設置了三種內存水位標記，high、low、min，當內存處于不同階段會觸發不同的內存回收機制，來保證內存的供應，如下圖所示：

他們所標記的分別含義為：

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

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

• 水位線在low-min表示剩余可用內存不多了壓力山大，min是最小的水位標記，當剩余內存達到這個狀態時，就說明內存面臨很大壓力。

• 水位線低于min這部分內存，就會觸發直接回收內存。

OOM機制

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

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

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

在oom的源碼中可以看到，作者關于如何選擇最優進程的一些說明：

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

oom_killer在選擇最優進程時決策并不完美，只是做到了"還行"，根據策略對進程打分，選擇分數最高的進程殺掉。

具體的計算在oom_badness函數中進行的，如下為分數的計算：

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

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

總結

本文首先介紹虛擬內存機制產生的原因，以及Linux虛擬內存機制的基本原理、同時引入了實現的數據結構和段頁機制。

其次重點介紹了內存分配器、并以glibc的malloc為藍本講述該內存分配器采用何種數據結構來實現空閑內存管理。

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

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

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