30 張圖帶你領略 glibc 內存管理精髓

大家好，我是雨樂。

最近在逛知乎的時候，看到篇帖子，如下：

看了下面所有的回答，要麼是沒有回答到點上，要麼是回答不夠深入，所以，藉助本文，深入講解 C/C++ 內存管理。

1 寫在前面

源碼分析本身就很枯燥乏味，尤其是要將其寫成通俗易懂的文章，更是難上加難。

本文儘可能的從讀者角度去進行分析，重點寫大家關心的點，必要的時候，會貼出部分源碼，以加深大家的理解，儘可能的通過本文，讓大家理解內存分配釋放的本質原理。

接下來的內容，乾貨滿滿，對於你我都是一次收穫的過程。主要從內存佈局、glibc 內存管理、malloc 實現以及 free 實現幾個點來帶你領略 glibc 內存管理精髓。最後，針對項目中的問題，指出瞭解決方案。大綱內容如下：

主要內容

2 背景

幾年前，在上家公司做了一個項目，暫且稱之爲 SeedService 吧。SeedService 從 kafka 獲取 feed 流的轉、評、贊信息，加載到內存。因爲每天數據不一樣，所以 kafka 的 topic 也是按天來切分，整個 server 內部，類似於雙指針實現，當天 0 點釋放頭一天的數據。

項目上線，一切運行正常。

但是幾天之後，進程開始無緣無故的消失。開始定位問題，最終發現是因爲內存暴增導致 OOM，最終被操作系統 kill 掉。

弄清楚了進程消失的原因之後，開始着手分析內存泄漏。在解決了幾個內存泄露的潛在問題以後，發現系統在高壓力高併發環境下長時間運行仍然會發生內存暴增的現象，最終進程因 OOM 被操作系統殺掉。

由於內存管理不外乎三個層面，用戶管理層，C 運行時庫層，操作系統層，在操作系統層發現進程的內存暴增，同時又確認了用戶管理層沒有內存泄露，因此懷疑是 C 運行時庫的問題，也就是 Glibc 的內存管理方式導致了進程的內存暴增。

問題縮小到 glibc 的內存管理方面，把下面幾個問題弄清楚，才能解決 SeedService 進程消失的問題：

• glibc 在什麼情況下不會將內存歸還給操作系統？

• glibc 的內存管理方式有哪些約束? 適合什麼樣的內存分配場景？

• 我們的系統中的內存管理方式是與 glibc 的內存管理的約束相悖的？

• glibc 是如何管理內存的？

帶着上面這些問題，大概用了將近一個月的時間分析了 glibc 運行時庫的內存管理代碼，今天將當時的筆記整理了出來，希望能夠對大家有用。

3 基礎

Linux 系統在裝載 elf 格式的程序文件時，會調用 loader 把可執行文件中的各個段依次載入到從某一地址開始的空間中。

用戶程序可以直接使用系統調用來管理 heap 和 mmap 映射區域，但更多的時候程序都是使用 C 語言提供的 malloc() 和 free() 函數來動態的分配和釋放內存。stack 區域是唯一不需要映射，用戶卻可以訪問的內存區域，這也是利用堆棧溢出進行攻擊的基礎。

3.1 進程內存佈局

計算機系統分爲 32 位和 64 位，而 32 位和 64 位的進程佈局是不一樣的，即使是同爲 32 位系統，其佈局依賴於內核版本，也是不同的。

在介紹詳細的內存佈局之前，我們先描述幾個概念：

• 棧區（Stack）— 存儲程序執行期間的本地變量和函數的參數，從高地址向低地址生長

• 堆區（Heap）動態內存分配區域，通過 malloc、new、free 和 delete 等函數管理

• 未初始化變量區（BSS）— 存儲未被初始化的全局變量和靜態變量

• 數據區（Data）— 存儲在源代碼中有預定義值的全局變量和靜態變量

• 代碼區（Text）— 存儲只讀的程序執行代碼，即機器指令

3.1.1 32 位進程內存佈局

經典佈局

在 Linux 內核 2.6.7 以前，進程內存佈局如下圖所示。

32 位經典佈局

在該內存佈局示例圖中，mmap 區域與棧區域相對增長，這意味着堆只有 1GB 的虛擬地址空間可以使用，繼續增長就會進入 mmap 映射區域， 這顯然不是我們想要的。這是由於 32 模式地址空間限制造成的，所以內核引入了另一種虛擬地址空間的佈局形式。但對於 64 位系統，因爲提供了巨大的虛擬地址空間，所以 64 位系統就採用的這種佈局方式。

默認佈局

如上所示，由於經典內存佈局具有空間侷限性，因此在內核 2.6.7 以後，就引入了下圖這種默認進程佈局方式。

32 位默認佈局

從上圖可以看到，棧至頂向下擴展，並且棧是有界的。堆至底向上擴展，mmap 映射區域至頂向下擴展，mmap 映射區域和堆相對擴展，直至耗盡虛擬地址空間中的剩餘區域，這種結構便於 C 運行時庫使用 mmap 映射區域和堆進行內存分配。

3.1.2 64 位進程內存佈局

如之前所述，64 位進程內存佈局方式由於其地址空間足夠，且實現方便，所以採用的與 32 位經典內存佈局的方式一致，如下圖所示:

64 位進程佈局

3.2 操作系統內存分配函數

在之前介紹內存佈局的時候，有提到過，heap 和 mmap 映射區域是可以提供給用戶程序使用的虛擬內存空間。那麼我們該如何獲得該區域的內存呢？

操作系統提供了相關的系統調用來完成內存分配工作。

• 對於 heap 的操作，操作系統提供了 brk() 函數，c 運行時庫提供了 sbrk() 函數。

• 對於 mmap 映射區域的操作，操作系統提供了 mmap() 和 munmap() 函數。

sbrk()，brk() 或者 mmap() 都可以用來向我們的進程添加額外的虛擬內存。而 glibc 就是使用這些函數來向操作系統申請虛擬內存，以完成內存分配的。

❝

這裏要提到一個很重要的概念，內存的延遲分配，只有在真正訪問一個地址的時候才建立這個地址的物理映射，這是 Linux 內存管理的基本思想之一。Linux 內核在用戶申請內存的時候，只是給它分配了一個線性區（也就是虛擬內存），並沒有分配實際物理內存；只有當用戶使用這塊內存的時候，內核纔會分配具體的物理頁面給用戶，這時候才佔用寶貴的物理內存。內核釋放物理頁面是通過釋放線性區，找到其所對應的物理頁面，將其全部釋放的過程。

❞

內存分配

進程的內存結構，在內核中，是用 mm_struct 來表示的，其定義如下：

struct mm_struct {
 ...
 unsigned long (*get_unmapped_area) (struct file *filp,
 unsigned long addr, unsigned long len,
 unsigned long pgoff, unsigned long flags);
 ...
 unsigned long mmap_base; /* base of mmap area */
 unsigned long task_size; /* size of task vm space */
 ...
 unsigned long start_code, end_code, start_data, end_data;
 unsigned long start_brk, brk, start_stack;
 unsigned long arg_start, arg_end, env_start, env_end;
 ...
}

在上述 mm_struct 結構中：

• [start_code,end_code) 表示代碼段的地址空間範圍。

• [start_data,end_start) 表示數據段的地址空間範圍。

• [start_brk,brk) 分別表示 heap 段的起始空間和當前的 heap 指針。

• [start_stack,end_stack) 表示 stack 段的地址空間範圍。

• mmap_base 表示 memory mapping 段的起始地址。

C 語言的動態內存分配基本函數是 malloc()，在 Linux 上的實現是通過內核的 brk 系統調用。brk() 是一個非常簡單的系統調用， 只是簡單地改變 mm_struct 結構的成員變量 brk 的值。

mm_struct

3.2.1 Heap 操作

在前面有提過，有兩個函數可以直接從堆 (Heap) 申請內存，brk()函數爲系統調用，sbrk()爲 c 庫函數。

系統調用通常提過一種最小的功能，而庫函數相比系統調用，則提供了更復雜的功能。在 glibc 中，malloc 就是調用 sbrk() 函數將數據段的下界移動以來代表內存的分配和釋放。sbrk() 函數在內核的管理下，將虛擬地址空間映射到內存，供 malloc() 函數使用。

下面爲 brk() 函數和 sbrk() 函數的聲明。

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

void *sbrk(intptr_t increment);

❝

需要說明的是，當 sbrk() 的參數 increment 爲 0 時候，sbrk() 返回的是進程當前 brk 值。increment 爲正數時擴展 brk 值，當 increment 爲負值時收縮 brk 值。

❞

3.2.2 MMap 操作

在 LINUX 中我們可以使用 mmap 用來在進程虛擬內存地址空間中分配地址空間，創建和物理內存的映射關係。

共享內存

mmap() 函數將一個文件或者其它對象映射進內存。文件被映射到多個頁上，如果文件的大小不是所有頁的大小之和，最後一個頁不被使用的空間將會清零。

munmap 執行相反的操作，刪除特定地址區域的對象映射。

函數的定義如下：

#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);

· 映射關係分爲以下兩種：

• 文件映射: 磁盤文件映射進程的虛擬地址空間，使用文件內容初始化物理內存。

• 匿名映射: 初始化全爲 0 的內存空間

映射關係是否共享，可以分爲:

• 私有映射 (MAP_PRIVATE)

• 多進程間數據共享，修改不反應到磁盤實際文件，是一個 copy-on-write（寫時複製）的映射方式。

• 共享映射 (MAP_SHARED)

• 多進程間數據共享，修改反應到磁盤實際文件中。

因此，整個映射關係總結起來分爲以下四種:

• 私有文件映射 多個進程使用同樣的物理內存頁進行初始化，但是各個進程對內存文件的修改不會共享，也不會反應到物理文件中

• 私有匿名映射

• mmap 會創建一個新的映射，各個進程不共享，這種使用主要用於分配內存 (malloc 分配大內存會調用 mmap)。例如開闢新進程時，會爲每個進程分配虛擬的地址空間，這些虛擬地址映射的物理內存空間各個進程間讀的時候共享，寫的時候會 copy-on-write。

• 共享文件映射

• 多個進程通過虛擬內存技術共享同樣的物理內存空間，對內存文件的修改會反應到實際物理文件中，也是進程間通信 (IPC) 的一種機制。

• 共享匿名映射

• 這種機制在進行 fork 的時候不會採用寫時複製，父子進程完全共享同樣的物理內存頁，這也就實現了父子進程通信 (IPC)。

這裏值得注意的是，mmap 只是在虛擬內存分配了地址空間，只有在第一次訪問虛擬內存的時候才分配物理內存。

在 mmap 之後，並沒有在將文件內容加載到物理頁上，只有在虛擬內存中分配了地址空間。當進程在訪問這段地址時，通過查找頁表，發現虛擬內存對應的頁沒有在物理內存中緩存，則產生 "缺頁"，由內核的缺頁異常處理程序處理，將文件對應內容，以頁爲單位 (4096) 加載到物理內存，注意是隻加載缺頁，但也會受操作系統一些調度策略影響，加載的比所需的多。

❝

下面的內容將是本文的重點中的重點，對於瞭解內存佈局以及後面 glibc 的內存分配原理至關重要，必要的話，可以多閱讀幾次。

❞

4 概述

在前面，我們有提到在堆上分配內存有兩個函數，分別爲 brk() 系統調用和 sbrk()c 運行時庫函數，在內存映射區分配內存有 mmap 函數。

現在我們假設一種情況，如果每次分配，都直接使用 brk(),sbrk() 或者 mmap() 函數進行多次內存分配。如果程序頻繁的進行內存分配和釋放，都是和操作系統直接打交道，那麼性能可想而知。

這就引入了一個概念，「內存管理」。

本節大綱如下：

4.1 內存管理

內存管理是指軟件運行時對計算機內存資源的分配和使用的技術。其最主要的目的是如何高效，快速的分配，並且在適當的時候釋放和回收內存資源。

一個好的內存管理器，需要具有以下特點：1、跨平臺、可移植 通常情況下，內存管理器向操作系統申請內存，然後進行再次分配。所以，針對不同的操作系統，內存管理器就需要支持操作系統兼容，讓使用者在跨平臺的操作上沒有區別。

2、浪費空間小 內存管理器管理內存，如果內存浪費比較大，那麼顯然這就不是一個優秀的內存管理器。通常說的內存碎片，就是浪費空間的罪魁禍首，若內存管理器中有大量的內存碎片，它們是一些不連續的小塊內存，它們總量可能很大，但無法使用，這顯然也不是一個優秀的內存管理器。

3、速度快 之所以使用內存管理器，根本原因就是爲了分配 / 釋放快。

4、調試功能 作爲一個 C/C++ 程序員，內存錯誤可以說是我們的噩夢，上一次的內存錯誤一定還讓你記憶猶新。內存管理器提供的調試功能，強大易用，特別對於嵌入式環境來說，內存錯誤檢測工具缺乏，內存管理器提供的調試功能就更是不可或缺了。

4.2 管理方式

內存管理的管理方式，分爲 手動管理 和 自動管理 兩種。

所謂的手動管理，就是使用者在申請內存的時候使用 malloc 等函數進行申請，在需要釋放的時候，需要調用 free 函數進行釋放。一旦用過的內存沒有釋放，就會造成內存泄漏，佔用更多的系統內存；如果在使用結束前釋放，會導致危險的懸掛指針，其他對象指向的內存已經被系統回收或者重新使用。

自動管理內存由編程語言的內存管理系統自動管理，在大多數情況下不需要使用者的參與，能夠自動釋放不再使用的內存。

4.2.1 手動管理

手動管理內存是一種比較傳統的內存管理方式，C/C++ 這類系統級的編程語言不包含狹義上的自動內存管理機制，使用者需要主動申請或者釋放內存。經驗豐富的工程師能夠精準的確定內存的分配和釋放時機，人肉的內存管理策略只要做到足夠精準，使用手動管理內存的方式可以提高程序的運行性能，也不會造成內存安全問題。

但是，畢竟這種經驗豐富且能精準確定內存和分配釋放實際的使用者還是比較少的，只要是人工處理，總會帶來一些錯誤，內存泄漏和懸掛指針基本是 C/C++ 這類語言中最常出現的錯誤，手動的內存管理也會佔用工程師的大量精力，很多時候都需要思考對象應該分配到棧上還是堆上以及堆上的內存應該何時釋放，維護成本相對來說還是比較高的，這也是必然要做的權衡。

4.2.2 自動管理

自動管理內存基本是現代編程語言的標配，因爲內存管理模塊的功能非常確定，所以我們可以在編程語言的編譯期或者運行時中引入自動的內存管理方式，最常見的自動內存管理機制就是垃圾回收，不過除了垃圾回收之外，一些編程語言也會使用自動引用計數輔助內存的管理。

自動的內存管理機制可以幫助工程師節省大量的與內存打交道的時間，讓使用者將全部的精力都放在覈心的業務邏輯上，提高開發的效率；在一般情況下，這種自動的內存管理機制都可以很好地解決內存泄漏和懸掛指針的問題，但是這也會帶來額外開銷並影響語言的運行時性能。

4.1 常見的內存管理器

1 ptmalloc：ptmalloc 是隸屬於 glibc(GNU Libc)的一款內存分配器，現在在 Linux 環境上，我們使用的運行庫的內存分配 (malloc/new) 和釋放 (free/delete) 就是由其提供。

2 BSD Malloc：BSD Malloc 是隨 4.2 BSD 發行的實現，包含在 FreeBSD 之中，這個分配程序可以從預先確實大小的對象構成的池中分配對象。它有一些用於對象大小的 size 類，這些對象的大小爲 2 的若干次冪減去某一常數。所以，如果您請求給定大小的一個對象，它就簡單地分配一個與之匹配的 size 類。這樣就提供了一個快速的實現，但是可能會浪費內存。

3 Hoard：編寫 Hoard 的目標是使內存分配在多線程環境中進行得非常快。因此，它的構造以鎖的使用爲中心，從而使所有進程不必等待分配內存。它可以顯著地加快那些進行很多分配和回收的多線程進程的速度。

4 TCMalloc：Google 開發的內存分配器，在不少項目中都有使用，例如在 Golang 中就使用了類似的算法進行內存分配。它具有現代化內存分配器的基本特徵：對抗內存碎片、在多核處理器能夠 scale。據稱，它的內存分配速度是 glibc2.3 中實現的 malloc 的數倍。

5 glibc 之內存管理 (ptmalloc)

因爲本次事故就是用的運行庫函數 new/delete 進行的內存分配和釋放，所以本文將着重分析 glibc 下的內存分配庫 ptmalloc。

本節大綱如下：

在 c/c++ 中，我們分配內存是在堆上進行分配，那麼這個堆，在 glibc 中是怎麼表示的呢？

我們先看下堆的結構聲明:

typedef struct _heap_info
{
  mstate ar_ptr;            /* Arena for this heap. */
  struct _heap_info *prev;  /* Previous heap. */
  size_t size;              /* Current size in bytes. */
  size_t mprotect_size;     /* Size in bytes that has been mprotected
                             PROT_READ|PROT_WRITE.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];

在堆的上述定義中，ar_ptr 是指向分配區的指針，堆之間是以鏈表方式進行連接，後面我會詳細講述進程佈局下，堆的結構表示圖。

在開始這部分之前，我們先了解下一些概念。

5.1 分配區 (arena)

❝

ptmalloc 對進程內存是通過一個個 Arena 來進行管理的。

❞

在 ptmalloc 中，分配區分爲主分配區 (arena) 和非主分配區(narena)，分配區用 struct malloc_state 來表示。主分配區和非主分配區的區別是 主分配區可以使用 sbrk 和 mmap 向 os 申請內存，而非分配區只能通過 mmap 向 os 申請內存。

當一個線程調用 malloc 申請內存時，該線程先查看線程私有變量中是否已經存在一個分配區。如果存在，則對該分配區加鎖，加鎖成功的話就用該分配區進行內存分配；失敗的話則搜索環形鏈表找一個未加鎖的分配區。如果所有分配區都已經加鎖，那麼 malloc 會開闢一個新的分配區加入環形鏈表並加鎖，用它來分配內存。釋放操作同樣需要獲得鎖才能進行。

需要注意的是，非主分配區是通過 mmap 向 os 申請內存，一次申請 64MB，一旦申請了，該分配區就不會被釋放，爲了避免資源浪費，ptmalloc 對分配區是有個數限制的。

❝

對於 32 位系統，分配區最大個數 = 2 * CPU 核數 + 1

對於 64 位系統，分配區最大個數 = 8 * CPU 核數 + 1

❞

堆管理結構：

struct malloc_state {
 mutex_t mutex;                 /* Serialize access. */
 int flags;                       /* Flags (formerly in max_fast). */
 #if THREAD_STATS
 /* Statistics for locking. Only used if THREAD_STATS is defined. */
 long stat_lock_direct, stat_lock_loop, stat_lock_wait;
 #endif
 mfastbinptr fastbins[NFASTBINS];    /* Fastbins */
 mchunkptr top;
 mchunkptr last_remainder;
 mchunkptr bins[NBINS * 2];
 unsigned int binmap[BINMAPSIZE];   /* Bitmap of bins */
 struct malloc_state *next;           /* Linked list */
 INTERNAL_SIZE_T system_mem;
 INTERNAL_SIZE_T max_system_mem;
 };

malloc_state

每一個進程只有一個主分配區和若干個非主分配區。主分配區由 main 線程或者第一個線程來創建持有。主分配區和非主分配區用環形鏈表連接起來。分配區內有一個變量 mutex 以支持多線程訪問。

環形鏈表鏈接的分配區

在前面有提到，在每個分配區中都有一個變量 mutex 來支持多線程訪問。每個線程一定對應一個分配區，但是一個分配區可以給多個線程使用，同時一個分配區可以由一個或者多個的堆組成，同一個分配區下的堆以鏈表方式進行連接，它們之間的關係如下圖：

線程 - 分配區 - 堆

一個進程的動態內存，由分配區管理，一個進程內有多個分配區，一個分配區有多個堆，這就組成了複雜的進程內存管理結構。

需要注意幾個點：

• 主分配區通過 brk 進行分配，非主分配區通過 mmap 進行分配

• 非主分配區雖然是 mmap 分配，但是和大於 128K 直接使用 mmap 分配沒有任何聯繫。大於 128K 的內存使用 mmap 分配，使用完之後直接用 ummap 還給系統

• 每個線程在 malloc 會先獲取一個 area，使用 area 內存池分配自己的內存，這裏存在競爭問題

• 爲了避免競爭，我們可以使用線程局部存儲，thread cache（tcmalloc 中的 tc 正是此意），線程局部存儲對 area 的改進原理如下：

• 如果需要在一個線程內部的各個函數調用都能訪問、但其它線程不能訪問的變量（被稱爲 static memory local to a thread 線程局部靜態變量），就需要新的機制來實現。這就是 TLS。

• thread cache 本質上是在 static 區爲每一個 thread 開闢一個獨有的空間，因爲獨有，不再有競爭

• 每次 malloc 時，先去線程局部存儲空間中找 area，用 thread cache 中的 area 分配存在 thread area 中的 chunk。當不夠時纔去找堆區的 area。

5.2 chunk

ptmalloc 通過 malloc_chunk 來管理內存，給 User data 前存儲了一些信息，使用邊界標記區分各個 chunk。

chunk 定義如下:

struct malloc_chunk {  
  INTERNAL_SIZE_T      prev_size;    /* Size of previous chunk (if free).  */  
  INTERNAL_SIZE_T      size;         /* Size in bytes, including overhead. */  
  
  struct malloc_chunk* fd;           /* double links -- used only if free. */  
  struct malloc_chunk* bk;  
  
  /* Only used for large blocks: pointer to next larger size.  */  
  struct malloc_chunk* fd_nextsize;      /* double links -- used only if free. */  
  struct malloc_chunk* bk_nextsize; 
};

• prev_size: 如果前一個 chunk 是空閒的，則該域表示前一個 chunk 的大小，如果前一個 chunk 不空閒，該域無意義。

一段連續的內存被分成多個 chunk，prev_size 記錄的就是相鄰的前一個 chunk 的 size，知道當前 chunk 的地址，減去 prev_size 便是前一個 chunk 的地址。prev_size 主要用於相鄰空閒 chunk 的合併。

• size ：當前 chunk 的大小，並且記錄了當前 chunk 和前一個 chunk 的一些屬性，包括前一個 chunk 是否在使用中，當前 chunk 是否是通過 mmap 獲得的內存，當前 chunk 是否屬於非主分配區。

• fd 和 bk ：指針 fd 和 bk 只有當該 chunk 塊空閒時才存在，其作用是用於將對應的空閒 chunk 塊加入到空閒 chunk 塊鏈表中統一管理，如果該 chunk 塊被分配給應用程序使用，那麼這兩個指針也就沒有用（該 chunk 塊已經從空閒鏈中拆出）了，所以也當作應用程序的使用空間，而不至於浪費。

• fd_nextsize 和 bk_nextsize: 當前的 chunk 存在於 large bins 中時， large bins 中的空閒 chunk 是按照大小排序的，但同一個大小的 chunk 可能有多個，增加了這兩個字段可以加快遍歷空閒 chunk ，並查找滿足需要的空閒 chunk ， fd_nextsize 指向下一個比當前 chunk 大小大的第一個空閒 chunk ， bk_nextszie 指向前一個比當前 chunk 大小小的第一個空閒 chunk 。（同一大小的 chunk 可能有多塊，在總體大小有序的情況下，要想找到下一個比自己大或小的 chunk，需要遍歷所有相同的 chunk，所以纔有 fd_nextsize 和 bk_nextsize 這種設計） 如果該 chunk 塊被分配給應用程序使用，那麼這兩個指針也就沒有用（該 chunk 塊已經從 size 鏈中拆出）了，所以也當作應用程序的使用空間，而不至於浪費。

正如上面所描述，在 ptmalloc 中，爲了儘可能的節省內存，使用中的 chunk 和未使用的 chunk 在結構上是不一樣的。

在上圖中：

• chunk 指針指向 chunk 開始的地址

• mem 指針指向用戶內存塊開始的地址。

• p=0 時，表示前一個 chunk 爲空閒，prev_size 纔有效

• p=1 時，表示前一個 chunk 正在使用，prev_size 無效 p 主要用於內存塊的合併操作；ptmalloc 分配的第一個塊總是將 p 設爲 1, 以防止程序引用到不存在的區域

• M=1 爲 mmap 映射區域分配；M=0 爲 heap 區域分配

• A=0 爲主分配區分配；A=1 爲非主分配區分配。

與非空閒 chunk 相比，空閒 chunk 在用戶區域多了四個指針，分別爲 fd,bk,fd_nextsize,bk_nextsize，這幾個指針的含義在上面已經有解釋，在此不再贅述。

空閒 chunk

5.3 空閒鏈表 (bins)

用戶調用 free 函數釋放內存的時候，ptmalloc 並不會立即將其歸還操作系統，而是將其放入空閒鏈表 (bins) 中，這樣下次再調用 malloc 函數申請內存的時候，就會從 bins 中取出一塊返回，這樣就避免了頻繁調用系統調用函數，從而降低內存分配的開銷。

在 ptmalloc 中，會將大小相似的 chunk 鏈接起來，叫做 bin。總共有 128 個 bin 供 ptmalloc 使用。

根據 chunk 的大小，ptmalloc 將 bin 分爲以下幾種：

• fast bin

• unsorted bin

• small bin

• large bin

從前面 malloc_state 結構定義，對 bin 進行分類，可以分爲 fast bin 和 bins，其中 unsorted bin、small bin 以及 large bin 屬於 bins。

在 glibc 中，上述 4 中 bin 的個數都不等，如下圖所示：

bin

5.3.1 fast bin

程序在運行時會經常需要申請和釋放一些較小的內存空間。當分配器合併了相鄰的幾個小的 chunk 之後, 也許馬上就會有另一個小塊內存的請求, 這樣分配器又需要從大的空閒內存中切分出一塊, 這樣無疑是比較低效的, 故而, malloc 中在分配過程中引入了 fast bins。

在前面 malloc_state 定義中

mfastbinptr fastbins[NFASTBINS]; // NFASTBINS  = 10

1. fast bin 的個數是 10 個

2. 每個 fast bin 都是一個單鏈表 (只使用 fd 指針)。這是因爲 fast bin 無論是添加還是移除 chunk 都是在鏈表尾進行操作，也就是說，對 fast bin 中 chunk 的操作，採用的是 LIFO(後入先出) 算法：添加操作 (free 內存) 就是將新的 fast chunk 加入鏈表尾，刪除操作 (malloc 內存) 就是將鏈表尾部的 fast chunk 刪除。

3. chunk size：10 個 fast bin 中所包含的 chunk size 以 8 個字節逐漸遞增，即第一個 fast bin 中 chunk size 均爲 16 個字節，第二個 fast bin 的 chunk size 爲 24 字節，以此類推，最後一個 fast bin 的 chunk size 爲 80 字節。

4. 不會對 free chunk 進行合併操作。這是因爲 fast bin 設計的初衷就是小內存的快速分配和釋放，因此係統將屬於 fast bin 的 chunk 的 P(未使用標誌位) 總是設置爲 1，這樣即使當 fast bin 中有某個 chunk 同一個 free chunk 相鄰的時候，系統也不會進行自動合併操作，而是保留兩者。

5. malloc 操作：在 malloc 的時候，如果申請的內存大小範圍在 fast bin 的範圍內，則先在 fast bin 中查找，如果找到了，則返回。否則則從 small bin、unsorted bin 以及 large bin 中查找。

6. free 操作：先通過 chunksize 函數根據傳入的地址指針獲取該指針對應的 chunk 的大小；然後根據這個 chunk 大小獲取該 chunk 所屬的 fast bin，然後再將此 chunk 添加到該 fast bin 的鏈尾即可。

下面是 fastbin 結構圖：

fastbin

5.3.2 unsorted bin

unsorted bin 的隊列使用 bins 數組的第一個，是 bins 的一個緩衝區，加快分配的速度。當用戶釋放的內存大於 max_fast 或者 fast bins 合併後的 chunk 都會首先進入 unsorted bin 上。

在 unsorted bin 中，chunk 的 size 沒有限制，也就是說任何大小 chunk 都可以放進 unsorted bin 中。這主要是爲了讓 “glibc malloc 機制” 能夠有第二次機會重新利用最近釋放的 chunk(第一次機會就是 fast bin 機制)。利用 unsorted bin，可以加快內存的分配和釋放操作，因爲整個操作都不再需要花費額外的時間去查找合適的 bin 了。　　 用戶 malloc 時，如果在 fast bins 中沒有找到合適的 chunk, 則 malloc 會先在 unsorted bin 中查找合適的空閒 chunk，如果沒有合適的 bin，ptmalloc 會將 unsorted bin 上的 chunk 放入 bins 上，然後到 bins 上查找合適的空閒 chunk。

與 fast bin 所不同的是，unsortedbin 採用的遍歷順序是 FIFO。

unsorted bin 結構圖如下：

unsorted bin

5.3.3 small bin

大小小於 512 字節的 chunk 被稱爲 small chunk，而保存 small chunks 的 bin 被稱爲 small bin。數組從 2 開始編號，前 62 個 bin 爲 small bins，small bin 每個 bin 之間相差 8 個字節，同一個 small bin 中的 chunk 具有相同大小。　　 每個 small bin 都包括一個空閒區塊的雙向循環鏈表（也稱 binlist）。free 掉的 chunk 添加在鏈表的前端，而所需 chunk 則從鏈表後端摘除。　　 兩個毗連的空閒 chunk 會被合併成一個空閒 chunk。合併消除了碎片化的影響但是減慢了 free 的速度。　　 分配時，當 samll bin 非空後，相應的 bin 會摘除 binlist 中最後一個 chunk 並返回給用戶。

在 free 一個 chunk 的時候，檢查其前或其後的 chunk 是否空閒，若是則合併，也即把它們從所屬的鏈表中摘除併合併成一個新的 chunk，新 chunk 會添加在 unsorted bin 鏈表的前端。

small bin 也採用的是 FIFO 算法，即內存釋放操作就將新釋放的 chunk 添加到鏈表的 front end(前端)，分配操作就從鏈表的 rear end(尾端) 中獲取 chunk。

small bin

5.3.4 large bin

大小大於等於 512 字節的 chunk 被稱爲 large chunk，而保存 large chunks 的 bin 被稱爲 large bin，位於 small bins 後面。large bins 中的每一個 bin 分別包含了一個給定範圍內的 chunk，其中的 chunk 按大小遞減排序，大小相同則按照最近使用時間排列。

兩個毗連的空閒 chunk 會被合併成一個空閒 chunk。

small bins 的策略非常適合小分配，但我們不能爲每個可能的塊大小都有一個 bin。對於超過 512 字節（64 位爲 1024 字節）的塊，堆管理器改爲使用 “large bin”。

63 large bin 中的每一個都與 small bin 的操作方式大致相同，但不是存儲固定大小的塊，而是存儲大小範圍內的塊。每個 large bin 的大小範圍都設計爲不與 small bin 的塊大小或其他 large bin 的範圍重疊。換句話說，給定一個塊的大小，這個大小對應的正好是一個 small bin 或 large bin。

在這 63 個 largebins 中：第一組的 32 個 largebin 鏈依次以 64 字節步長爲間隔，即第一個 largebin 鏈中 chunksize 爲 1024-1087 字節，第二個 large bin 中 chunk size 爲 1088~1151 字節。第二組的 16 個 largebin 鏈依次以 512 字節步長爲間隔；第三組的 8 個 largebin 鏈以步長 4096 爲間隔；第四組的 4 個 largebin 鏈以 32768 字節爲間隔；第五組的 2 個 largebin 鏈以 262144 字節爲間隔；最後一組的 largebin 鏈中的 chunk 大小無限制。

在進行 malloc 操作的時候，首先確定用戶請求的大小屬於哪一個 large bin，然後判斷該 large bin 中最大的 chunk 的 size 是否大於用戶請求的 size。如果大於，就從尾開始遍歷該 large bin，找到第一個 size 相等或接近的 chunk，分配給用戶。如果該 chunk 大於用戶請求的 size 的話，就將該 chunk 拆分爲兩個 chunk：前者返回給用戶，且 size 等同於用戶請求的 size；剩餘的部分做爲一個新的 chunk 添加到 unsorted bin 中。

如果該 large bin 中最大的 chunk 的 size 小於用戶請求的 size 的話，那麼就依次查看後續的 large bin 中是否有滿足需求的 chunk，不過需要注意的是鑑於 bin 的個數較多 (不同 bin 中的 chunk 極有可能在不同的內存頁中)，如果按照上一段中介紹的方法進行遍歷的話 (即遍歷每個 bin 中的 chunk)，就可能會發生多次內存頁中斷操作，進而嚴重影響檢索速度，所以 glibc malloc 設計了 Binmap 結構體來幫助提高 bin-by-bin 檢索的速度。Binmap 記錄了各個 bin 中是否爲空，通過 bitmap 可以避免檢索一些空的 bin。如果通過 binmap 找到了下一個非空的 large bin 的話，就按照上一段中的方法分配 chunk，否則就使用 top chunk（在後面有講）來分配合適的內存。

large bin 的 free 操作與 small bin 一致，此處不再贅述。

large bin

上述幾種 bin，組成了進程中最核心的分配部分：bins，如下圖所示：

5.4 特殊 chunk

上節內容講述了幾種 bin 以及各種 bin 內存的分配和釋放特點，但是，僅僅上面幾種 bin 還不能夠滿足，比如假如上述 bins 不能滿足分配條件的時候，glibc 提出了另外幾種特殊的 chunk 供分配和釋放，分別爲 top chunk，mmaped chunk 和 last remainder chunk。

5.4.1 top trunk

top chunk 是堆最上面的一段空間，它不屬於任何 bin，當所有的 bin 都無法滿足分配要求時，就要從這塊區域裏來分配，分配的空間返給用戶，剩餘部分形成新的 top chunk，如果 top chunk 的空間也不滿足用戶的請求，就要使用 brk 或者 mmap 來向系統申請更多的堆空間（主分配區使用 brk、sbrk，非主分配區使用 mmap）。

在 free chunk 的時候，如果 chunk size 不屬於 fastbin 的範圍，就要考慮是不是和 top chunk 挨着，如果挨着，就要 merge 到 top chunk 中。

5.4.2 mmaped chunk

當分配的內存非常大（大於分配閥值，默認 128K）的時候，需要被 mmap 映射，則會放到 mmaped chunk 上，當釋放 mmaped chunk 上的內存的時候會直接交還給操作系統。（chunk 中的 M 標誌位置 1）

5.4.3 last remainder chunk

Last remainder chunk 是另外一種特殊的 chunk，這個特殊 chunk 是被維護在 unsorted bin 中的。

如果用戶申請的 size 屬於 small bin 的，但是又不能精確匹配的情況下，這時候採用最佳匹配（比如申請 128 字節，但是對應的 bin 是空，只有 256 字節的 bin 非空，這時候就要從 256 字節的 bin 上分配），這樣會 split chunk 成兩部分，一部分返給用戶，另一部分形成 last remainder chunk，插入到 unsorted bin 中。

當需要分配一個 small chunk, 但在 small bins 中找不到合適的 chunk，如果 last remainder chunk 的大小大於所需要的 small chunk 大小，last remainder chunk 被分裂成兩個 chunk，其中一個 chunk 返回給用戶，另一個 chunk 變成新的 last remainder chunk。

last remainder chunk 主要通過提高內存分配的局部性來提高連續 malloc（產生大量 small chunk）的效率。

5.5 chunk 切分

chunk 釋放時，其長度不屬於 fastbins 的範圍，則合併前後相鄰的 chunk。首次分配的長度在 large bin 的範圍，並且 fast bins 中有空閒 chunk，則將 fastbins 中的 chunk 與相鄰空閒的 chunk 進行合併，然後將合併後的 chunk 放到 unsorted bin 中，如果 fastbin 中的 chunk 相鄰的 chunk 並非空閒無法合併，仍舊將該 chunk 放到 unsorted bin 中，即能合併的話就進行合併，但最終都會放到 unsorted bin 中。

fastbins，small bin 中都沒有合適的 chunk，top chunk 的長度也不能滿足需要，則對 fast bin 中的 chunk 進行合併。

5.6 chunk 合併

前面講了相鄰的 chunk 可以合併成一個大的 chunk，反過來，一個大的 chunk 也可以分裂成兩個小的 chunk。chunk 的分裂與從 top chunk 中分配新的 chunk 是一樣的。需要注意的一點是：分裂後的兩個 chunk 其長度必須均大於 chunk 的最小長度（對於 64 位系統是 32 字節），即保證分裂後的兩個 chunk 仍舊是可以被分配使用的，否則則不進行分裂，而是將整個 chunk 返回給用戶。

6 內存分配 (malloc)

glibc 運行時庫分配動態內存，底層用的是 malloc 來實現 (new 最終也是調用 malloc)，下面是 malloc 函數調用流程圖：

malloc

在此，將上述流程圖以文字形式表示出來，以方便大家理解：

1. 獲取分配區的鎖，爲了防止多個線程同時訪問同一個分配區，在進行分配之前需要取得分配區域的鎖。線程先查看線程私有實例中是否已經存在一個分配區，如果存在嘗試對該分配區加鎖，如果加鎖成功，使用該分配區分配內存，否則，該線程搜索分配區循環鏈表試圖獲得一個空閒（沒有加鎖）的分配區。如果所有的分配區都已經加鎖，那麼 ptmalloc 會開闢一個新的分配區，把該分配區加入到全局分配區循環鏈表和線程的私有實例中並加鎖，然後使用該分配區進行分配操作。開闢出來的新分配區一定爲非主分配區，因爲主分配區是從父進程那裏繼承來的。開闢非主分配區時會調用 mmap() 創建一個 sub-heap，並設置好 top chunk。

2. 將用戶的請求大小轉換爲實際需要分配的 chunk 空間大小。

3. 判斷所需分配 chunk 的大小是否滿足 chunk_size <= max_fast (max_fast 默認爲 64B)， 如果是的話，則轉下一步，否則跳到第 5 步。

4. 首先嚐試在 fast bins 中取一個所需大小的 chunk 分配給用戶。如果可以找到，則分配結束。否則轉到下一步。

5. 判斷所需大小是否處在 small bins 中，即判斷 chunk_size < 512B 是否成立。如果 chunk 大小處在 small bins 中，則轉下一步，否則轉到第 6 步。

6. 根據所需分配的 chunk 的大小，找到具體所在的某個 small bin，從該 bin 的尾部摘取一個恰好滿足大小的 chunk。若成功，則分配結束，否則，轉到下一步。

7. 到了這一步，說明需要分配的是一塊大的內存，或者 small bins 中找不到合適的 chunk。於是，ptmalloc 首先會遍歷 fast bins 中的 chunk，將相鄰的 chunk 進行合併，並鏈接到 unsorted bin 中，然後遍歷 unsorted bin 中的 chunk，如果 unsorted bin 只有一個 chunk，並且這個 chunk 在上次分配時被使用過，並且所需分配的 chunk 大小屬於 small bins，並且 chunk 的大小大於等於需要分配的大小，這種情況下就直接將該 chunk 進行切割，分配結束，否則將根據 chunk 的空間大小將其放入 small bins 或是 large bins 中，遍歷完成後，轉入下一步。

8. 到了這一步，說明需要分配的是一塊大的內存，或者 small bins 和 unsorted bin 中都找不到合適的 chunk，並且 fast bins 和 unsorted bin 中所有的 chunk 都清除乾淨了。從 large bins 中按照 “smallest-first，best-fit” 原則，找一個合適的 chunk，從中劃分一塊所需大小的 chunk，並將剩下的部分鏈接回到 bins 中。若操作成功，則分配結束，否則轉到下一步。

9. 如果搜索 fast bins 和 bins 都沒有找到合適的 chunk，那麼就需要操作 top chunk 來進行分配了。判斷 top chunk 大小是否滿足所需 chunk 的大小，如果是，則從 top chunk 中分出一塊來。否則轉到下一步。

10. 到了這一步，說明 top chunk 也不能滿足分配要求，所以，於是就有了兩個選擇: 如果是主分配區，調用 sbrk()，增加 top chunk 大小；如果是非主分配區，調用 mmap 來分配一個新的 sub-heap，增加 top chunk 大小；或者使用 mmap() 來直接分配。在這裏，需要依靠 chunk 的大小來決定到底使用哪種方法。判斷所需分配的 chunk 大小是否大於等於 mmap 分配閾值，如果是的話，則轉下一步，調用 mmap 分配， 否則跳到第 12 步，增加 top chunk 的大小。

11. 使用 mmap 系統調用爲程序的內存空間映射一塊 chunk_size align 4kB 大小的空間。然後將內存指針返回給用戶。

12. 判斷是否爲第一次調用 malloc，若是主分配區，則需要進行一次初始化工作，分配一塊大小爲 (chunk_size + 128KB) align 4KB 大小的空間作爲初始的 heap。若已經初始化過了，主分配區則調用 sbrk() 增加 heap 空間，分主分配區則在 top chunk 中切割出一個 chunk，使之滿足分配需求，並將內存指針返回給用戶。

將上面流程串起來就是：

❝

根據用戶請求分配的內存的大小，ptmalloc 有可能會在兩個地方爲用戶分配內存空間。在第一次分配內存時，一般情況下只存在一個主分配區，但也有可能從父進程那裏繼承來了多個非主分配區，在這裏主要討論主分配區的情況，brk 值等於 start_brk，所以實際上 heap 大小爲 0，top chunk 大小也是 0。這時，如果不增加 heap 大小，就不能滿足任何分配要求。所以，若用戶的請求的內存大小小於 mmap 分配閾值， 則 ptmalloc 會初始 heap。然後在 heap 中分配空間給用戶，以後的分配就基於這個 heap 進行。若第一次用戶的請求就大於 mmap 分配閾值，則 ptmalloc 直接使用 mmap()分配一塊內存給用戶，而 heap 也就沒有被初始化，直到用戶第一次請求小於 mmap 分配閾值的內存分配。第一次以後的分配就比較複雜了，簡單說來，ptmalloc 首先會查找 fast bins，如果不能找到匹配的 chunk，則查找 small  bins。若仍然不滿足要求，則合併 fast bins，把 chunk 加入 unsorted bin，在 unsorted bin 中查找，若仍然不滿足要求，把 unsorted bin 中的 chunk 全加入 large bins 中，並查找 large bins。在 fast bins 和 small bins 中的查找都需要精確匹配， 而在 large  bins 中查找時，則遵循 “smallest-first，best-fit” 的原則，不需要精確匹配。若以上方法都失敗了，則 ptmalloc 會考慮使用 top chunk。若 top chunk 也不能滿足分配要求。而且所需 chunk 大小大於 mmap 分配閾值，則使用 mmap 進行分配。否則增加 heap，增大 top chunk。以滿足分配要求。

❞

當然了，glibc 中 malloc 的分配遠比上面的要複雜的多，要考慮到各種情況，比如指針異常ΩΩ越界等，將這些判斷條件也加入到流程圖中，如下圖所示：

malloc(需要高清大圖，留言區留言或者私信我)

由於圖片過大，會被公衆號壓縮，所以即使點開大圖，也看不清楚，如果需要高清大圖的，可以後臺留言或者公衆號私信

7 內存釋放 (free)

malloc 進行內存分配，那麼與 malloc 相對的就是 free，進行內存釋放，下面是 free 函數的基本流程圖：

free

對上述流程圖進行描述，如下：

1. 獲取分配區的鎖，保證線程安全。

2. 如果 free 的是空指針，則返回，什麼都不做。

3. 判斷當前 chunk 是否是 mmap 映射區域映射的內存，如果是，則直接 munmap() 釋放這塊內存。前面的已使用 chunk 的數據結構中，我們可以看到有 M 來標識是否是 mmap 映射的內存。

4. 判斷 chunk 是否與 top chunk 相鄰，如果相鄰，則直接和 top chunk 合併（和 top chunk 相鄰相當於和分配區中的空閒內存塊相鄰）。否則，轉到步驟 8

5. 如果 chunk 的大小大於 max_fast（64b），則放入 unsorted bin，並且檢查是否有合併，有合併情況並且和 top chunk 相鄰，則轉到步驟 8；沒有合併情況則 free。

6. 如果 chunk 的大小小於 max_fast（64b），則直接放入 fast bin，fast bin 並沒有改變 chunk 的狀態。沒有合併情況，則 free；有合併情況，轉到步驟 7

7. 在 fast bin，如果當前 chunk 的下一個 chunk 也是空閒的，則將這兩個 chunk 合併，放入 unsorted bin 上面。合併後的大小如果大於 64B，會觸發進行 fast bins 的合併操作，fast bins 中的 chunk 將被遍歷，並與相鄰的空閒 chunk 進行合併，合併後的 chunk 會被放到 unsorted bin 中，fast bin 會變爲空。合併後的 chunk 和 topchunk 相鄰，則會合併到 topchunk 中。轉到步驟 8

8. 判斷 top chunk 的大小是否大於 mmap 收縮閾值（默認爲 128KB），如果是的話，對於主分配區，則會試圖歸還 top chunk 中的一部分給操作系統。free 結束。

如果將 free 函數內部各種條件加入進去，那麼 free 調用的詳細流程圖如下：

free(需要高清大圖，留言區留言或者私信我)

由於圖片過大，會被公衆號壓縮，所以即使點開大圖，也看不清楚，如果需要高清大圖的，可以後臺留言或者公衆號私信

8 問題分析以及解決

通過前面對 glibc 運行時庫的分析，基本就能定位出原因，是因爲我們調用了 free 進行釋放，但僅僅是將內存返還給了 glibc 庫，而 glibc 庫卻沒有將內存歸還操作系統，最終導致系統內存耗盡，程序因爲 OOM 被系統殺掉。

有以下兩種方案：

• 禁用 ptmalloc 的 mmap 分配 閾 值 動 態 調 整 機 制 。通 過 mallopt() 設置 M_TRIM_THRESHOLD，M_MMAP_THRESHOLD，M_TOP_PAD 和 M_MMAP_MAX 中的任意一個，關閉 mmap 分配閾值動態調整機制，同時需要將 mmap 分配閾值設置爲 64K，大於 64K 的內存分配都使用 mmap 向系統分配，釋放大於 64K 的內存將調用 munmap 釋放回系統。但是，這種方案的 缺點是每次內存分配和申請，都是直接向操作系統申請，效率低。

• 預 估 程 序 可 以 使 用 的 最 大 物 理 內 存 大 小 ， 配 置 系 統 的 /proc/sys/vm/overcommit_memory，/proc/sys/vm/overcommit_ratio，以及使用 ulimt –v 限制程序能使用虛擬內存空間大小，防止程序因 OOM 被殺掉。這種方案的 缺點是如果預估的內存小於進程實際佔用，那麼仍然會出現 OOM，導致進程被殺掉。

• tcmalloc

最終採用 tcmalloc 來解決了問題，後面有機會的話，會寫一篇 tcmalloc 內存管理的相關文章。

9 結語

業界語句說法，是否瞭解內存管理機制，是辨別 C/C++ 程序員和其他的高級語言程序員的重要區別。作爲 C/C++ 中的最重要的特性，指針及動態內存管理在給編程帶來極大的靈活性的同時，也給開發人員帶來了許多困擾。

瞭解底層內存實現，有時候會有意想不到的效果哦。

先寫到這裏吧。

❝

由於本文涉及知識點較多，因此爲了方便閱讀，提供了 PDF 版本，可以公衆號留言、私信，也可以加本人****微信 (下面二維碼) 獲取；另外還有批量電子書，後臺回覆 [pdf] 免費獲取。

❞

10 參考

1、https://sourceware.org/glibc/wiki/MallocInternals

2、https://titanwolf.org/Network/Articles/Article?AID=99524c69-cb90-4d61-bb28-01c0864d0ccc

3、https://blog.fearcat.in/a?ID=00100-535db575-0d98-4287-92b6-4d7d9604b216

4、https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/

5、https://sploitfun.wordpress.com/2015/02/11/syscalls-used-by-malloc

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/pdv5MMUQ9ACpeCpyGnxb1Q