2萬字|30張圖帶你領略glibc內存管理精髓(因為OOM導致了上千萬損失)

2021 年 11 月 4 日
筆記
C++, 內存對象

前言

大家好，我是雨樂。

5年前，在上家公司的時候，因為進程OOM造成了上千萬的損失，當時用了一個月的時間來分析glibc源碼，最終將問題徹底解決。

最近在逛知乎的時候，發現不少人有對malloc/free有類似的疑惑，恰好自己有閱讀過這方面的源碼，所以將之前的源碼閱讀筆記整理了下，用了大概3周的時間寫了這篇文章，分析glibc的內存管理精髓，相信對c/c++從業者都會有用。

由於本文涉及知識點較多，因此為了方便閱讀，提供了PDF版本，可以留言獲取

提綱

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位進程內存布局

基於內核版本的不同，在32位系統中，進程內的布局也不一樣。

3.1.1.1 經典布局

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

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

3.1.1.2 默認布局

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

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

3.1.2 64位進程內存布局

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

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 的值。

3.2.1 Heap操作

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

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

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

 #include 
 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;
  };

每一個進程只有一個主分配區和若干個非主分配區。主分配區由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，這幾個指針的含義在上面已經有解釋，在此不再贅述。

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的個數都不等，如下圖所示：

5.3.1 fast bin

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

在前面malloc_state定義中

 mfastbinptr fastbins[NFASTBINS]; // NFASTBINS  = 10

fast bin的個數是10個
每個fast bin都是一個單鏈表(只使用fd指針)。這是因為fast bin無論是添加還是移除chunk都是在鏈表尾進行操作，也就是說，對fast bin中chunk的操作，採用的是LIFO(後入先出)算法：添加操作(free內存)就是將新的fast chunk加入鏈表尾，刪除操作(malloc內存)就是將鏈表尾部的fast chunk刪除。
chunk size：10個fast bin中所包含的chunk size以8個位元組逐漸遞增，即第一個fast bin中chunk size均為16個位元組，第二個fast bin的chunk size為24位元組，以此類推，最後一個fast bin的chunk size為80位元組。
不會對free chunk進行合併操作。這是因為fast bin設計的初衷就是小內存的快速分配和釋放，因此系統將屬於fast bin的chunk的P(未使用標誌位)總是設置為1，這樣即使當fast bin中有某個chunk同一個free chunk相鄰的時候，系統也不會進行自動合併操作，而是保留兩者。
malloc操作：在malloc的時候，如果申請的內存大小範圍在fast bin的範圍內，則先在fast bin中查找，如果找到了，則返回。否則則從small bin、unsorted bin以及large bin中查找。
free操作：先通過chunksize函數根據傳入的地址指針獲取該指針對應的chunk的大小；然後根據這個chunk大小獲取該chunk所屬的fast bin，然後再將此chunk添加到該fast bin的鏈尾即可。

下面是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結構圖如下：

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。

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一致，此處不再贅述。

上述幾種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函數調用流程圖：

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

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的分配遠比上面的要複雜的多，要考慮到各種情況，比如指針異常越界等，將這些判斷條件也加入到流程圖中，如下圖所示：

7 內存釋放(free)

malloc進行內存分配，那麼與malloc相對的就是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調用的詳細流程圖如下：

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++中的最重要的特性，指針及動態內存管理在給編程帶來極大的靈活性的同時，也給開發人員帶來了許多困擾。

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

先寫到這裡吧。

10 參考

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

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

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

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

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

Tags: C++ 內存對象