深入理解 glibc malloc：記憶體分配器實現原理

點選進入“PHP開源社群”

免費獲取進階面試、文件、影片資源

前言

堆記憶體（Heap Memory）是一個很有意思的領域。你可能和我一樣，也困惑於下述問題很久了：

• 如何從核心申請堆記憶體？

• 誰管理它？核心、庫函式，還是應用本身？

• 記憶體管理效率怎麼這麼高？！

• 堆記憶體的管理效率可以進一步提高嗎？

最近，我終於有時間去深入瞭解這些問題。下面就讓我來談談我的調研成果。

開源社群公開了很多現成的記憶體分配器（Memory Allocators，以下簡稱為 分配器 ）：

• dlmalloc – 第一個被廣泛使用的通用動態記憶體分配器；

• ptmalloc2 – glibc 內建分配器的原型；

• jemalloc – FreeBSD ＆ Firefox 所用分配器；

• tcmalloc – Google 貢獻的分配器；

• libumem – Solaris 所用分配器；

• …

每一種分配器都宣稱自己快（fast）、可拓展（scalable）、效率高（memory efficient）！但是並非所有的分配器都適用於我們的應用。記憶體吞吐量大（memory hungry）的應用程式，其效能很大程度上取決於分配器的效能。

在這篇文章中，我只談「glibc malloc」分配器。為了方便大家理解「glibc malloc」，我會聯絡最新的原始碼。

歷史 ：ptmalloc2 基於 dlmalloc 開發，其引入了多執行緒支援，於 2006 年釋出。釋出之後，ptmalloc2 整合進了 glibc 原始碼，此後其所有修改都直接提交到了 glibc malloc 裡。因此，ptmalloc2 的原始碼和 glibc malloc 的原始碼有很多不一致的地方。（譯者注：1996 年出現的 dlmalloc 只有一個主分配區，該分配區為所有執行緒所爭用，1997 年釋出的 ptmalloc 在 dlmalloc 的基礎上引入了非主分配區的概念。）

1. 申請堆的系統呼叫

我在之前的文章中提到過， malloc 內部通過  brk 或  mmap 系統呼叫向核心申請堆區。

譯者注 ：在記憶體管理領域，我們一般用「堆」指代用於分配動態記憶體的虛擬地址空間，而用「棧」指代用於分配靜態記憶體的虛擬地址空間。具體到虛擬記憶體佈局（Memory Layout），堆維護在通過  brk 系統呼叫申請的「Heap」及通過  mmap 系統呼叫申請的「Memory Mapping Segment」中；而棧維護在通過彙編棧指令動態調整的「Stack」中。在 Glibc 裡，「Heap」用於分配較小的記憶體及主執行緒使用的記憶體。

下圖為 Linux 核心 v2.6.7 之後，32 位模式下的虛擬記憶體佈局方式。

2. 多執行緒支援

Linux 的早期版本採用 dlmalloc 作為它的預設分配器，但是因為 ptmalloc2 提供了多執行緒支援，所以 後來 Linux 就轉而採用 ptmalloc2 了。多執行緒支援可以提升分配器的效能，進而間接提升應用的效能。

在 dlmalloc 中，當兩個執行緒同時 malloc 時，只有一個執行緒能夠訪問臨界區（critical section）——這是因為所有執行緒 共享 用以快取已釋放記憶體的「空閒列表資料結構」（freelist data structure），所以使用 dlmalloc 的多執行緒應用會在  malloc 上耗費過多時間，從而導致整個應用效能的下降。

在 ptmalloc2 中，當兩個執行緒同時呼叫 malloc 時，記憶體均會得以立即分配——每個執行緒都維護著單獨的堆，各個堆被獨立的空閒列表資料結構管理，因此各個執行緒可以併發地從空閒列表資料結構中申請記憶體。這種為每個執行緒維護獨立堆與空閒列表資料結構的行為就「per thread arena」。

2.1. 案例程式碼

/* Per thread arena example. */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/types.h>


void* threadFunc(void* arg) {
    printf("Before malloc in thread 1\n");
    getchar();
    char* addr = (char*) malloc(1000);
    printf("After malloc and before free in thread 1\n");
    getchar();
    free(addr);
    printf("After free in thread 1\n");
    getchar();
}


int main() {
    pthread_t t1;
    void* s;
    int ret;
    char* addr;


    printf("Welcome to per thread arena example::%d\n",getpid());
    printf("Before malloc in main thread\n");
    getchar();
    addr = (char*) malloc(1000);
    printf("After malloc and before free in main thread\n");
    getchar();
    free(addr);
    printf("After free in main thread\n");
    getchar();
    ret = pthread_create(&t1, NULL, threadFunc, NULL);
    if(ret)
    {
        printf("Thread creation error\n");
        return -1;
    }
    ret = pthread_join(t1, &s);
    if(ret)
    {
        printf("Thread join error\n");
        return -1;
    }
    return 0;
}

2.2. 案例輸出

2.2.1. 在主執行緒 malloc 之前

從如下的輸出結果中我們可以看到，這裡還 沒有 堆段 也沒有 每個執行緒的棧，因為 thread1 還沒有建立！

[email protected]VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
...
[email protected]VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
b7e05000-b7e07000 rw-p 00000000 00:00 0 
...
[email protected]VirtualBox:~/ptmalloc.ppt/mthread$

2.2.2. 在主執行緒 malloc 之後

從如下的輸出結果中我們可以看到，堆段已經產生，並且其地址區間正好在資料段（0x0804b000 - 0x0806c000）上面，這表明堆記憶體是移動「Program Break」的位置產生的（也即通過 brk 中斷）。此外，請注意，儘管使用者只申請了 1000 位元組的記憶體，但是實際產生了 132KB 的堆。這個連續的堆區域被稱為「 arena 」。因為這個 arena 是被主執行緒建立的，因此其被稱為「 main arena 」。接下來的申請會繼續分配這個 arena 的 132KB 中剩餘的部分。當分配完畢時，它可以通過繼續移動 Program Break 的位置擴容。擴容後，「top chunk」的大小也隨之調整，以將這塊新增的空間圈進去；相應地，arena 也可以在 top chunk 過大時縮小。

注意 ：top chunk 是一個 arena 位於最頂層的 chunk。有關 top chunk 的更多資訊詳見後續章節「top chunk」部分。

[email protected]VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
...
[email protected]VirtualBox:~/lsploits/hof/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0          [heap]
b7e05000-b7e07000 rw-p 00000000 00:00 0 
...
[email protected]VirtualBox:~/ptmalloc.ppt/mthread$

2.2.3. 在主執行緒 free 之後

從如下的輸出結果中我們可以看到，當分配的記憶體區域 free 掉時，其並不會立即歸還給作業系統，而僅僅是移交給了作為庫函式的分配器。這塊  free 掉的記憶體新增在了「main arenas bin」中（在 glibc malloc 中，空閒列表資料結構被稱為「 bin 」）。隨後當用戶請求記憶體時，分配器就不再向核心申請新堆了，而是先試著各個「bin」中查詢空閒記憶體。只有當 bin 中不存在空閒記憶體時，分配器才會繼續向核心申請記憶體。

[email protected]VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
...
[email protected]VirtualBox:~/lsploits/hof/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0          [heap]
b7e05000-b7e07000 rw-p 00000000 00:00 0 
...
[email protected]VirtualBox:~/ptmalloc.ppt/mthread$

2.2.4. 在 thread1 malloc 之前

從如下的輸出結果中我們可以看到，此時 thread1 的堆尚不存在，但其棧已產生。

[email protected]VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
...
sploitfu[email protected]VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0          [heap]
b7604000-b7605000 ---p 00000000 00:00 0 
b7605000-b7e07000 rw-p 00000000 00:00 0          [stack:6594]
...
[email protected]VirtualBox:~/ptmalloc.ppt/mthread$

2.2.5. 在 thread1 malloc 之後

從如下的輸出結果中我們可以看到，thread1 的堆段(b7500000 - b7521000，132KB)建立在了記憶體對映段中，這也表明了堆記憶體是使用 mmap 系統呼叫產生的，而非同主執行緒一樣使用  sbrk 系統呼叫。類似地，儘管使用者只請求了 1000B，但是對映到程地址空間的堆記憶體足有 1MB。這 1MB 中，只有 132KB 被設定了讀寫許可權，併成為該執行緒的堆記憶體。這段連續記憶體（132KB）被稱為「 thread arena 」。

注意 ：當用戶請求超過 128KB(比如  malloc(132*1024) ) 大小並且此時 arena 中沒有足夠的空間來滿足使用者的請求時，記憶體將通過  mmap 系統呼叫（不再是  sbrk ）分配，而不論請求是發自 main arena 還是 thread arena。

[email protected]VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
After malloc and before free in thread 1
...
[email protected]VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0          [heap]
b7500000-b7521000 rw-p 00000000 00:00 0 
b7521000-b7600000 ---p 00000000 00:00 0 
b7604000-b7605000 ---p 00000000 00:00 0 
b7605000-b7e07000 rw-p 00000000 00:00 0          [stack:6594]
...
[email protected]VirtualBox:~/ptmalloc.ppt/mthread$

2.2.6. 在 thread1 free 之後

從如下的輸出結果中我們可以看到， free 不會把記憶體歸還給作業系統，而是移交給分配器，然後新增在了「thread arenas bin」中。

[email protected]VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread 
Welcome to per thread arena example::6501
Before malloc in main thread
After malloc and before free in main thread
After free in main thread
Before malloc in thread 1
After malloc and before free in thread 1
After free in thread 1
...
[email protected]VirtualBox:~/ptmalloc.ppt/mthread$ cat /proc/6501/maps
08048000-08049000 r-xp 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
08049000-0804a000 r--p 00000000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804a000-0804b000 rw-p 00001000 08:01 539625     /home/sploitfun/ptmalloc.ppt/mthread/mthread
0804b000-0806c000 rw-p 00000000 00:00 0          [heap]
b7500000-b7521000 rw-p 00000000 00:00 0 
b7521000-b7600000 ---p 00000000 00:00 0 
b7604000-b7605000 ---p 00000000 00:00 0 
b7605000-b7e07000 rw-p 00000000 00:00 0          [stack:6594]
...
[email protected]VirtualBox:~/ptmalloc.ppt/mthread$

3. Arena

3.1. Arena 的數量

在以上的例子中我們可以看到，主執行緒包含 main arena 而 thread 1 包含它自己的 thread arena。所以執行緒和 arena 之間是否存在一一對映關係，而不論執行緒的數量有多大？當然不是，部分極端的應用甚至執行比處理器核數還多的執行緒，在這種情況下，每個執行緒都擁有一個 arena 開銷過高且意義不大。所以，arena 數量其實是限於系統核數的。

For 32 bit systems:
Number of arena = 2 * number of cores.
For 64 bit systems:
Number of arena = 8 * number of cores.

3.2. Multiple Arena

舉例而言：讓我們來看一個執行在單核計算機上的 32 位作業系統上的多執行緒應用（4 執行緒，主執行緒 + 3 個執行緒）的例子。這裡執行緒數量（4）> 2 * 核心數（1），所以分配器中可能有 Arena（也即標題所稱「multiple arenas」）會被所有執行緒共享。那麼是如何共享的呢？

• 當主執行緒第一次呼叫 malloc 時，已經建立的 main arena 會被沒有任何競爭地使用；

• 當 thread 1 和 thread 2 第一次呼叫 malloc 時，一塊新的 arena 將被建立，且將被沒有任何競爭地使用。此時執行緒和 arena 之間存在一一對映關係；

• 當 thread3 第一次呼叫 malloc 時，arena 的數量限制被計算出來，結果顯示已超出，因此嘗試複用已經存在的 arena（也即 Main arena 或 Arena 1 或 Arena 2）；

• 複用：

• 一旦遍歷到可用 arena，就開始自旋申請該 arena 的鎖；

• 如果上鎖成功（比如說 main arena 上鎖成功），就將該 arena 返回使用者；

• 如果沒找到可用 arena，thread 3 的 malloc 將被阻塞，直到有可用的 arena 為止。

• 當thread 3 呼叫 malloc 時(第二次了)，分配器會嘗試使用上一次使用的 arena（也即，main arena），從而儘量提高快取命中率。當 main arena 可用時就用，否則 thread 3 就一直阻塞，直至 main arena 空閒。因此現在 main arena 實際上是被 main thread 和 thread 3 所共享。

3.3. Multiple Heaps

在「glibc malloc」中主要有 3 種資料結構：

• heap_info ——Heap Header—— 一個 thread arena 可以維護多個堆。每個堆都有自己的堆 Header（注：也即頭部元資料）。什麼時候 Thread Arena 會維護多個堆呢？一般情況下，每個 thread arena 都只維護一個堆，但是當這個堆的空間耗盡時，新的堆（而非連續記憶體區域）就會被 mmap 到這個 aerna 裡；

• malloc_state ——Arena header—— 一個 thread arena 可以維護多個堆，這些堆另外共享同一個 arena header。Arena header 描述的資訊包括：bins、top chunk、last remainder chunk 等；

• malloc_chunk ——Chunk header—— 根據使用者請求，每個堆被分為若干 chunk。每個 chunk 都有自己的 chunk header。

main arena 和 thread arena 的圖示如下（單堆段）：

thread arena 的圖示如下（多堆段）：

4. Chunk

堆段中存在的 chunk 型別如下：

• Allocated chunk;

• Free chunk;

• Top chunk;

• Last Remainder chunk.

4.1. Allocated chunk

「 Allocated chunck 」就是已經分配給使用者的 chunk，其圖示如下：

圖中左方三個箭頭依次表示：

• chunk：該 Allocated chunk 的起始地址；

• mem：該 Allocated chunk 中使用者可用區域的起始地址（ = chunk + sizeof(malloc_chunk) ）；

• next_chunk：下一個 chunck（無論型別）的起始地址。

圖中結構體內部各欄位的含義依次為：

• prev_size：若上一個 chunk 可用，則此欄位賦值為上一個 chunk 的大小；否則，此欄位被用來儲存上一個 chunk 的使用者資料；

• size：此欄位賦值本 chunk 的大小，其最後三位包含標誌資訊：

• PREV_INUSE § – 置「1」表示上個 chunk 被分配；

• IS_MMAPPED (M) – 置「1」表示這個 chunk 是通過 mmap 申請的（較大的記憶體）；

• NON_MAIN_ARENA (N) – 置「1」表示這個 chunk 屬於一個 thread arena。

4.2. Free chunk

「 Free chunck 」就是使用者已釋放的 chunk，其圖示如下：

圖中結構體內部各欄位的含義依次為：

• prev_size: 兩個相鄰 free chunk 會被合併成一個，因此該欄位總是儲存前一個 allocated chunk 的使用者資料；

• size: 該欄位儲存本 free chunk 的大小；

• fd: Forward pointer —— 本欄位指向同一 bin 中的下個 free chunk（free chunk 連結串列的前驅指標）；

• bk: Backward pointer —— 本欄位指向同一 bin 中的上個 free chunk（free chunk 連結串列的後繼指標）。

5. Bins

「 bins 」 就是空閒列表資料結構。它們用以儲存 free chunks。根據其中 chunk 的大小，bins 被分為如下幾種型別：

• Fast bin;

• Unsorted bin;

• Small bin;

• Large bin.

儲存這些 bins 的欄位為：

• fastbinsY: 這個陣列用以儲存 fast bins；

• bins: 這個陣列用於儲存 unsorted bin、small bins 以及 large bins，共計可容納 126 個，其中：

• Bin 1: unsorted bin;

• Bin 2 - 63: small bins;

• Bin 64 - 126: large bins.

5.1. Fast Bin

大小為 16 ~ 80 位元組的 chunk 被稱為「 fast chunk 」。在所有的 bins 中，fast bins 路徑享有最快的記憶體分配及釋放速度。

• 數量 ：10

• 每個 fast bin 都維護著一條 free chunk 的單鏈表，採用單鏈表是因為連結串列中所有 chunk 的大小相等，增刪 chunk 發生在連結串列頂端即可；—— LIFO

• chunk 大小 ：8 位元組遞增

• fast bins 由一系列所維護 chunk 大小以 8 位元組遞增的 bins 組成。也即， fast bin[0] 維護大小為 16 位元組的 chunk、 fast bin[1] 維護大小為 24 位元組的 chunk。依此類推……

• 指定 fast bin 中所有 chunk 大小相同；

• 在 malloc 初始化過程中，最大的 fast bin 的大小被設定為 64 而非 80 位元組。因為預設情況下只有大小 16 ~ 64 的 chunk 被歸為 fast chunk 。

• 無需合併 —— 兩個相鄰 chunk 不會被合併。雖然這可能會加劇記憶體碎片化，但也大大加速了記憶體釋放的速度！

• malloc(fast chunk)

• 初始情況下 fast chunck 最大尺寸以及 fast bin 相應資料結構均未初始化，因此即使使用者請求記憶體大小落在 fast chunk 相應區間，服務使用者請求的也將是 small bin 路徑而非 fast bin 路徑；

• 初始化後，將在計算 fast bin 索引後檢索相應 bin；

• 相應 bin 中被檢索的第一個 chunk 將被摘除並返回給使用者。

• free(fast chunk)

• 計算 fast bin 索引以索引相應 bin；

• free 掉的 chunk 將被新增到上述 bin 的頂端。

5.2. Unsorted Bin

當 small chunk 和 large chunk 被 free 掉時，它們並非被新增到各自的 bin 中，而是被新增在 「 unsorted bin 」 中。這使得分配器可以重新使用最近  free 掉的 chunk，從而消除了尋找合適 bin 的時間開銷，進而加速了記憶體分配及釋放的效率。

譯者注：經 @kwdecsdn 提醒，這裡應補充說明「Unsorted Bin 中的 chunks 何時移至 small/large chunk 中」。在記憶體分配的時候，在前後檢索 fast/small bins 未果之後，在特定條件下，會將 unsorted bin 中的 chunks 轉移到合適的 bin 中去，small/large。

• 數量 ：1

• unsorted bin 包括一個用於儲存 free chunk 的雙向迴圈連結串列（又名 binlist）；

• chunk 大小 ：無限制，任何大小的 chunk 均可新增到這裡。

5.3. Small Bin

大小小於 512 位元組的 chunk 被稱為 「 small chunk 」，而儲存 small chunks 的 bin 被稱為 「 small bin 」。在記憶體分配回收的速度上，small bin 比 large bin 更快。

• 數量 ：62

• 每個 small bin 都維護著一條 free chunk 的雙向迴圈連結串列。採用雙向連結串列的原因是，small bins 中的 chunk 可能會從連結串列中部摘除。這裡新增項放在連結串列的頭部位置，而從連結串列的尾部位置移除項。—— FIFO

• chunk 大小 ：8 位元組遞增

• Small bins 由一系列所維護 chunk 大小以 8 位元組遞增的 bins 組成。舉例而言， small bin[0] （Bin 2）維護著大小為 16 位元組的 chunks、 small bin[1] （Bin 3）維護著大小為 24 位元組的 chunks ，依此類推……

• 指定 small bin 中所有 chunk 大小均相同，因此無需排序；

• 合併 —— 相鄰的 free chunk 將被合併，這減緩了記憶體碎片化，但是減慢了 free 的速度；

• malloc(small chunk)

• 初始情況下，small bins 都是 NULL，因此儘管使用者請求 small chunk ，提供服務的將是 unsorted bin 路徑而不是 small bin 路徑；

• 第一次呼叫 malloc 時，維護在 malloc_state 中的 small bins 和 large bins 將被初始化，它們都會指向自身以表示其為空；

• 此後當 small bin 非空，相應的 bin 會摘除其中最後一個 chunk 並返回給使用者；

• free(small chunk)

• free chunk 的時候，檢查其前後的 chunk 是否空閒，若是則合併，也即把它們從所屬的連結串列中摘除併合併成一個新的 chunk，新 chunk 會新增在 unsorted bin 的前端。

5.4. Large Bin

大小大於等於 512 位元組的 chunk 被稱為「 large chunk 」，而儲存 large chunks 的 bin 被稱為 「 large bin 」。在記憶體分配回收的速度上，large bin 比 small bin 慢。

• 數量 ：63

• 32 個 bins 所維護的 chunk 大小以 64B 遞增，也即 large chunk[0] (Bin 65) 維護著大小為 512B ~ 568B 的 chunk 、 large chunk[1] (Bin 66) 維護著大小為 576B ~ 632B 的 chunk，依此類推……

• 16 個 bins 所維護的 chunk 大小以 512 位元組遞增；

• 8 個 bins 所維護的 chunk 大小以 4096 位元組遞增；

• 4 個 bins 所維護的 chunk 大小以 32768 位元組遞增；

• 2 個 bins 所維護的 chunk 大小以 262144 位元組遞增；

• 1 個 bin 維護所有剩餘 chunk 大小；

• 每個 large bin 都維護著一條 free chunk 的雙向迴圈連結串列。採用雙向連結串列的原因是，large bins 中的 chunk 可能會從連結串列中的任意位置插入及刪除。

• 這 63 個 bins

• 不像 small bin ，large bin 中所有 chunk 大小不一定相同，各 chunk 大小遞減儲存。最大的 chunk 儲存頂端，而最小的 chunk 儲存在尾端；

• 合併 —— 兩個相鄰的空閒 chunk 會被合併；

• malloc(large chunk)

• User chunk（使用者請求大小）—— 返回給使用者；

• Remainder chunk （剩餘大小）—— 新增到 unsorted bin。

• 初始情況下，large bin 都會是 NULL，因此儘管使用者請求 large chunk ，提供服務的將是 next largetst bin 路徑而不是 large bin 路勁 。

• 第一次呼叫 malloc 時，維護在 malloc_state 中的 small bin 和 large bin 將被初始化，它們都會指向自身以表示其為空；

• 此後當 large bin 非空，如果相應 bin 中的最大 chunk 大小大於使用者請求大小，分配器就從該 bin 頂端遍歷到尾端，以找到一個大小最接近使用者請求的 chunk。一旦找到，相應 chunk 就會被切分成兩塊：

• 如果相應 bin 中的最大 chunk 大小小於使用者請求大小，分配器就會掃描 binmaps，從而查詢最小非空 bin。如果找到了這樣的 bin，就從中選擇合適的 chunk 並切割給使用者；反之就使用 top chunk 響應使用者請求。

• free(large chunk) —— 類似於 small chunk 。

5.5. Top Chunk

一個 arena 中最頂部的 chunk 被稱為「 top chunk 」。它不屬於任何 bin 。當所有 bin 中都沒有合適空閒記憶體時，就會使用 top chunk 來響應使用者請求。

當 top chunk 的大小比使用者請求的大小大的時候，top chunk 會分割為兩個部分：

• User chunk，返回給使用者；

• Remainder chunk，剩餘部分，將成為新的 top chunk。

當 top chunk 的大小比使用者請求的大小小的時候，top chunk 就通過 sbrk （main arena）或  mmap （ thread arena）系統呼叫擴容。

5.6. Last Remainder Chunk

「 last remainder chunk 」即最後一次 small request 中因分割而得到的剩餘部分，它有利於改進引用區域性性，也即後續對 small chunk 的  malloc 請求可能最終被分配得彼此靠近。

那麼 arena 中的若干 chunks，哪個有資格成為 last remainder chunk 呢？

當用戶請求 small chunk 而無法從 small bin 和 unsorted bin 得到服務時，分配器就會通過掃描 binmaps 找到最小非空 bin。正如前文所提及的，如果這樣的 bin 找到了，其中最合適的 chunk 就會分割為兩部分：返回給使用者的 User chunk 、新增到 unsorted bin 中的 Remainder chunk。這一 Remainder chunk 就將成為 last remainder chunk。

那麼引用區域性性是如何達成的呢？

當用戶的後續請求 small chunk，並且 last remainder chunk 是 unsorted bin 中唯一的 chunk，該 last remainder chunk 就將分割成兩部分：返回給使用者的 User chunk、新增到 unsorted bin 中的 Remainder chunk（也是 last remainder chunk）。因此後續的請求的 chunk 最終將被分配得彼此靠近。

如果你年滿18週歲以上，又覺得學【PHP】太難？想嘗試其他程式語言，那麼我推薦你學Python，現有價值499元Python零基礎課程限時免費領取，限10個名額！

點選“檢視原文”獲取更多