前言

大家好，我的朋友們！

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

內存為進程的運行提供物理空間，同時作為快速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：

structmm_struct*mm;
structmm_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*類型可以強制轉換為任何其它類型的指針，從而做到通用性

/*mallocexample*/
#include
#include

intmain()
{
inti,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);
return0;
}

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

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

#include
intbrk(void*addr);
void*sbrk(intptr_tincrement);

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

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

#include
void*mmap(void*addr,size\_tlength,intprot,intflags,intfd,off\_toffset);
intmunmap(void*addr,size_tlength);

• 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
/*Themaximumfastbinrequestsizewesupport*/
#defineMAX_FAST_SIZE80
#defineNFASTBINS(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機制。

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

最后，感謝大家的耐心閱讀，有疑問請直接交流。

審核編輯 ：李倩