圖解|Linux記憶體背後的那些神祕往事

前言

大家好，我的朋友們！

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：

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》

論文連結：http://www.bsdcan.org/2006/papers/jemalloc.pdf

glibc malloc原理分析

我們在使用malloc進行記憶體分配，malloc只是glibc提供的庫函式，它仍然會呼叫其他函式從而最終觸達到實體記憶體，所以是個很長的鏈路。

我們先看下malloc的特點：

• malloc 申請分配指定size個位元組的記憶體空間，返回型別是 void* 型別，但是此時的記憶體只是虛擬空間內的連續記憶體，無法保證實體記憶體連續

• mallo並不關心程序用申請的記憶體來儲存什麼型別的資料，void*型別可以強制轉換為任何其它型別的指標，從而做到通用性

/* malloc example */
#include <stdio.h>
#include <stdlib.h>

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

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

  for (n=0; n<i; n++)
    buffer[n]=rand()%26+'a';
  buffer[i]='\0';
  free (buffer);
  return 0;
}

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

繼續我看下 malloc是如何觸達到實體記憶體的：

#include <unistd.h>
int brk(void *addr);
void *sbrk(intptr_t increment);

• brk函式將break指標直接設定為某個地址，相當於絕對值

• sbrk將break指標從當前位置移動increment所指定的增量，相當於相對值

• 本質上brk和sbrk作用是一樣的都是移動break指標的位置來擴充套件記憶體

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

#include <sys/mman.h>
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是否可以回收時，需要使用反向對映來檢視哪些程序被對映到這塊物理頁了，進一步判斷是否可以回收 。

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

http://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的原始碼中可以看到，作者關於如何選擇最優程序的一些說明：

http://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機制。

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

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