聊聊 C 語言中的 malloc 申請內存的內部原理

大家好，我是飛哥！

我們今天來深入地瞭解一下 malloc 函數的內部工作原理。

操作系統爲應爲應用層提供了 mmap、brk 等系統調用來申請內存。但是這些系統調用在很多的時候，我們並不會直接使用。原因有以下兩個

系統調用管理的內存粒度太大。系統調用申請內存都是整頁 4KB 起，但是我們平時編程的時候經常需要申請幾十字節的小對象。如果使用 mmap 未免碎片率也太大了。
頻繁的系統調用的開銷比較大。和函數調用比起來，系統的調用的開銷非常的大。如果每次申請內存都發起系統調用，那麼我們的應用程序將慢如牛。

所以，現代編程語言的做法都是自己在應用層實現了一個內存分配器。其思想都和內核自己用的 SLAB 內存分配器類似。都是內存分配器預先向操作系統申請一些內存，然後自己構造一個內存池。當我們申請內存的時候，直接由分配器從預先申請好的內存池裏申請。當我們釋放內存的時候，分配器會將這些內存管理起來，並通過一些策略來判斷是否將其回收給操作系統。

通過這種方式既靈活地管理了各種不同大小的小對象，也避免了用戶頻率地調用 mmap 系統調用所造成的開銷。常見的內存分配器有 glibc 中的 ptmalloc、Google 的 tcmalloc、Facebook 的 jemalloc 等等。我們在學校裏學習 C 語言時候使用的 malloc 函數的底層就是 glibc 的 ptmalloc 內存分配器實現的。

我們今天就以最經（古）典（老）的 ptmalloc 內存分配器講起，帶大家深入地瞭解 malloc 函數的內部工作原理。

本文中需要用到 glibc 源碼，下載地址是 http://ftp.gnu.org/gnu/glibc/ 。本文使用的源碼版本是 2.12.1。

一、ptmalloc 內存分配器定義

1.1 分配區 arena

在 ptmalloc 中，使用分配區 arena 管理從操作系統中批量申請來的內存。之所以要有多個分配區，原因是多線程在操作一個分配區的時候需要加鎖。在線程比較多的時候，在鎖上浪費的開銷會比較多。爲了降低鎖開銷，ptmalloc 支持多個分配區。這樣在單個分配區上鎖的競爭開銷就會小很多。

在 ptmalloc 中存在一個全局的主分配區，是用靜態變量的方式定義的。

//file:malloc/malloc.c
static struct malloc_state main_arena;

分配區的數據類型是 struct malloc_state，其定義如下：

//file:malloc/malloc.c
struct malloc_state {
 // 鎖，用來解決在多線程分配時的競爭問題
 mutex_t mutex;

 // 分配區下管理內存的各種數據結構
 ...

 /* Linked list */
 struct malloc_state *next;
}

在分配區中，首先有一個鎖。這是因爲多個分配區只是能降低鎖競爭的發生，但不能完全杜絕。所以還需要一個鎖來應對多線程申請內存時的競爭問題。接下來就是分配區中內存管理的各種數據結構。這部分下個小節我們再詳細看。

再看下 next 指針。通過這個指針，ptmalloc 把所有的分配區都以一個鏈表組織了起來，方便後面的遍歷。

1.2 內存塊 chunk

在每個 arena 中，最基本的內存分配的單位是 malloc_chunk，我們簡稱 chunk。它包含 header 和 body 兩部分。這是 chunk 在 glibc 中的定義：

// file:malloc/malloc.c
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;
};

我們在開發中每次調用 malloc 申請內存的時候，分配器都會給我們分配一個大小合適的 chunk 出來，把 body 部分的 user data 的地址返回給我們。這樣我們就可以向該地址寫入和讀取數據了。強烈推薦關注本公衆號「開發內功修煉」。

如果我們在開發中調用 free 釋放內存的話，其對應的 chunk 對象其實並不會歸還給內核。而是由 glibc 又組織管理了起來。其 body 部分的 fd、bk 字段分別是指向上一個和下一個空閒的 chunk（ chunk 在使用的時候是沒有這兩個字段的，這塊內存在不同場景下的用途不同），用來當雙向鏈表指針來使用。

1.3 空閒內存塊鏈表 bins

glibc 會將相似大小的空閒內存塊 chunk 都串起來。這樣等下次用戶再來分配的時候，先找到鏈表，然後就可以從鏈表中取下一個元素快速分配。這樣的一個鏈表被稱爲一個 bin。ptmalloc 中根據管理的內存塊的大小，總共有 fastbins、smallbins、largebins 和 unsortedbins 四類。

這四類 bins 分別定義在 struct malloc_state 的不同成員裏。

//file:malloc/malloc.c
struct malloc_state {

 /* Fastbins */
 mfastbinptr      fastbins[NFASTBINS];

 /* Base of the topmost chunk -- not otherwise kept in a bin */
 mchunkptr        top;

 /* The remainder from the most recent split of a small request */
 mchunkptr        last_remainder;

 /* Normal bins packed as described above */
 mchunkptr        bins[NBINS * 2];

 /* Bitmap of bins */
 unsigned int     binmap[BINMAPSIZE];
}

fastbins 是用來管理尺寸最小空閒內存塊的鏈表。其管理的內存塊的最大大小是 MAX_FAST_SIZE。

#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)

SIZE_SZ 這個宏指的是指針的大小，在 32 位系統下，SIZE_SZ 等於 4 。在 64 位系統下，它等於 8。因爲現在都是 64 位系統，所以本文中後面的例子中我們都是以 SIZE_SZ 爲 8 來舉例。所以在 64 位系統下，MAX_FAST_SIZE = 80 * 8 / 4 = 160 字節。

bins 是用來管理空閒內存塊的主要鏈表數組。其鏈表總數爲 2\ * NBINS 個，NBINS 的大小是 128，所以這裏總共有 256 個空閒鏈表。

//file:malloc/malloc.c
#define NBINS             128

smallbins、largebins 和 unsortedbins 都使用的是這個數組。

另外 top 成員是用來保存着特殊的 top chunk。當所有的空閒鏈表中都申請不到合適的大小的時候，會來這裏申請。

1）fastbins

其中 fastbins 成員定義的是尺寸最小的元素的鏈表。它存在的原因是，用戶的應用程序中絕大多數的內存分配是小內存，這組 bin 是用於提高小內存的分配效率的。

fastbin 中有多個鏈表，每個 bin 鏈表管理的都是固定大小的 chunk 內存塊。在 64 位系統下，每個鏈表管理的 chunk 元素大小分別是 32 字節、48 字節、......、128 字節等不同的大小。

glibc 中提供了 fastbin_index 函數可以快速地根據要申請的內存大小找到 fastbins 下對應的數組下標。

//file:malloc/malloc.c
#define fastbin_index(sz) \
  ((((unsigned int)(sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

例如要申請的內存塊大小是 32 字節，fastbin_index(32) 計算後可知應該到下標位 0 的空閒內存鏈表裏去找。再比如要申請的內存塊大小是 64 字節，fastbin_index(64) 計算後得知數組下標爲 2。

2）smallbins

smallbins 是在 malloc_state 下的 bins 成員中管理的。

smallbins 數組總共有 64 個鏈表指針，是由 NSMALLBINS 來定義的。

//file:malloc/malloc.c
#define NSMALLBINS         64

和 fastbin 一樣，同一個 small bin 中的 chunk 具有相同的大小。small bin 在 64 位系統上，兩個相鄰的 small bin 中的 chunk 大小相差 16 字節 (MALLOC_ALIGNMENT 是 2 個 SIZE_SZ，一個 SIZE_SZ 大小是 8)。

//file:malloc/malloc.c
#define MALLOC_ALIGNMENT       (2 * SIZE_SZ)
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT

管理的 chunk 大小範圍定義在 in_smallbin_range 中能看到。只要小於 MIN_LARGE_SIZE 的都屬於 small bin 的管理範圍。

#define MIN_LARGE_SIZE    (NSMALLBINS * SMALLBIN_WIDTH)
#define in_smallbin_range(sz)  \
  ((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE)

通過上面的源碼可以看出 MIN_LARGE_SIZE 的大小等於 64 * 16 = 1024。所以 small bin 管理的內存塊大小是從 32 字節、48 字節、......、1008 字節。（在 glibc 64 位系統中沒有管理 16 字節的空閒內存，是 32 字節起的）

另外 glibc 也提供了根據申請的字節大小快速算出其在 small bin 中的下標的函數 smallbin_index。

//file:malloc/malloc.c
#define smallbin_index(sz) \
  (SMALLBIN_WIDTH == 16 ? (((unsigned)(sz)) >> 4) : (((unsigned)(sz)) >> 3))

例如要申請的內存塊大小是 32 smallbin_index(32) 計算後可知應該到下標位 2 的空閒內存鏈表裏去找。再比如要申請的內存塊大小是 64 smallbin_index(64) 計算後得知數組下標爲 3。

2）largebins

largebins 和 smallbins 的區別是它管理的內存塊比較大。其管理的內存是 1024 起的。

而且每兩個相鄰的 largebin 之間管理的內存塊大小不再是固定的等差數列。這是爲了用較少的鏈表數來更大塊空閒內存的管理。

largebin_index_64 函數用來根據要申請的內存大小計算出其在 large bins 中的下標。

//file:malloc/malloc.c
#define largebin_index_64(sz)                                                \
(((((unsigned long)(sz)) >>  6) <= 48)?  48 + (((unsigned long)(sz)) >>  6): \
 ((((unsigned long)(sz)) >>  9) <= 20)?  91 + (((unsigned long)(sz)) >>  9): \
 ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
 ((((unsigned long)(sz)) >> 15) <=  4)? 119 + (((unsigned long)(sz)) >> 15): \
 ((((unsigned long)(sz)) >> 18) <=  2)? 124 + (((unsigned long)(sz)) >> 18): \
     126)

4）unsortedbins

unsortedbins 比較特殊，它管理的內存塊不再是和 smallbins 或 largebins 中那樣是相同或者相近大小的。而是不固定，是被當做緩存區來用的。

當用戶釋放一個堆塊之後，會先進入 unsortedbin。再次分配堆塊時，ptmalloc 會優先檢查這個鏈表中是否存在合適的堆塊，如果找到了，就直接返回給用戶 (這個過程可能會對 unsortedbin 中的堆塊進行切割)。若沒有找到合適的，系統也會順帶清空這個鏈表上的元素，把它放到合適的 smallbin 或者 large bin 中。

5）top chunk

另外還有有個獨立於 fastbins、smallbins、largebins 和 unsortedbins 之外的一個特殊的 chunk 叫 top chunk。

如果沒有空閒的 chunk 可用的時候，或者需要分配的 chunk 足夠大，當各種 bins 都不滿足需求，會從 top chunk 中嘗試分配。

二、malloc 的工作過程

在前面的小節裏我們看到，glibc 在分配區 arena 中分別用 fastbins、bins（保存着 smallbins、largebins 和 unsortedbins）以及 top chunk 來管理着當前已經申請到的所有空閒內存塊。

有了這些組織手段後，當用戶要分配內存的時候，malloc 函數就可以根據其大小，從合適的 bins 中查找合適的 chunk。

假如用戶要申請 30 字節的內存，那就直接找到 32 字節這個 bin 鏈表，從鏈表頭部摘下來一個 chunk 直接用。
假如用戶要申請 500 字節的內存，那就找到 512 字節的 bin 鏈表，摘下來一個 chunk 使用
......

當用戶用完需要釋放的時候，glibc 再根據其內存塊大小，放到合適的 bin 下管理起來。下次再給用戶申請時備用。

另外還有就是爲 ptmalloc 管理的 chunk 可能會發生拆分或者合併。當需要申請小內存塊，但是沒有大小合適的時候，會將大的 chunk 拆成多個小 chunk。如果申請大內存塊的時候，而系統中又存在大量的小 chunk 的時候，又會發生合併，以降低碎片率。

這樣不管如何申請和釋放，都不會導致嚴重的碎片問題發生。這就是 glibc 內存分配器的主要管理。瞭解了主要原理後，我們再來看下 malloc 函數的實現中，具體是怎麼樣來分配處理內存分配的。

malloc 在 glibc 中的實現函數名是 public_mALLOc。

//file:malloc/malloc.c
Void_t*
public_mALLOc(size_t bytes)
{
 // 選一個分配區 arena 出來，併爲其加鎖
 arena_lookup(ar_ptr);
 arena_lock(ar_ptr, bytes);

 // 從分配區申請內存
 victim = _int_malloc(ar_ptr, bytes);

 // 如果選中的分配區沒有申請成功，則換一個分配區申請
 ......

 // 釋放鎖並返回
 mutex_unlock(&ar_ptr->mutex);
 return victim;
}

在 public_mALLOc 中主要的邏輯就是選擇分配區和鎖操作，這是爲了避免多線程衝突。真正的內存申請核心邏輯都在 _int_malloc 函數中。這個函數非常的長。爲了清晰可見，我們把它的骨幹邏輯列出來。

//file:malloc/malloc.c
static Void_t*
_int_malloc(mstate av, size_t bytes)
{
 // 對用戶請求的字節數進行規範化
 INTERNAL_SIZE_T nb; /* normalized request size */
 checked_request2size(bytes, nb);

 // 1.從 fastbins 中申請內存
 if ((unsigned long)(nb) <= (unsigned long)(get_max_fast ())) {
  ...
 }

 // 2.從 smallbins 中申請內存
 if (in_smallbin_range(nb)) {
  ...
 }

 for(;;) {
  // 3.遍歷搜索 unsorted bins
  while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
   // 判斷是否對 chunk 進行切割
   ...

   // 判斷是否精準匹配，若匹配可以直接返回
   ...

   // 若不精準匹配，則將 chunk 放到對應的 bins 中
   // 如果屬於 smallbins，則插入到 smallbins 中
   // 如果屬於 largebins，則插入到 largebins 中
   ...

   // 避免遍歷 unsorted bin 佔用過多時間
   if (++iters >= MAX_ITERS)
    break;
  }

  // 4.如果屬於 large 範圍或者之前的 fastbins/smallbins/unsorted bins 請求都失敗
  //   則從 large bin 中尋找 chunk，可能會涉及到切割
  ...


  // 5.嘗試從 top chunk 中申請
  //   可能會涉及對 fastbins 中 chunk 的合併
 use_top:
  victim = av->top;
     size = chunksize(victim);
  ...

  // 最後，分配區中沒申請到，則向操作系統申請
  void *p = sYSMALLOc(nb, av);
 }
}

在一進入函數的時候，首先是調用 checked_request2size 對用戶請求的字節數進行規範化。因爲分配區中管理的都是 32、64 等對齊的字節數的內存。如果用戶請求 30 字節，那麼 ptmalloc 會對齊一下，然後按 32 字節爲其申請。

接着是從分配區的各種 bins 中嘗試爲用戶分配內存。總共包括以下幾次的嘗試。

1 如果申請字節數小於 fast bins 管理的內存塊最大字節數，則嘗試從 fastbins 中申請內存，申請成功就返回
2 如果申請字節數小於 small bins 管理的內存，則嘗試從 smallbins 中申請內存，申請成功就返回
3 嘗試從 unsorted bins 中申請內存，申請成功就返回
4 嘗試從 large bins 中申請內存，申請成功就返回
5 如果前面的步驟申請都沒成功，嘗試從 top chunk 中申請內存並返回
6 從操作系統中使用 mmap 等系統調用申請內存

在這些分配嘗試中，一旦某一步申請成功了，就會返回。後面的步驟就不需要進行了。

最後在 top chunk 中也沒有足夠的內存的時候，就會調用 sYSMALLOc 來向操作系統發起內存申請。

//file:malloc/malloc.c
static Void_t* sYSMALLOc(INTERNAL_SIZE_T nb, mstate av)
{
 ...
 mm = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));
 ...
}

在 sYSMALLOc 中，是通過 mmap 等系統調用來申請內存的。

另外還有就是穿插在這些的嘗試中間，可能會涉及到 chunk 的切分，將大塊的 chunk 切分成較小的返回給用戶。也可能涉及到多個小 chunk 的合併，用來降低內存碎片率。

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