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

語言: CN / TW / HK

點選進入“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 無需維護多個堆,因此也無需 heap_info。當空間耗盡時,與 thread arena 不同,main arena 可以通過 sbrk 拓展 段,直至堆段「碰」到記憶體對映段;

  • 與 thread arena 不同,main arena 的 arena header 不是儲存在通過 sbrk 申請的堆段裡,而是作為一個全域性變數,可以在 libc.so 的資料段中找到。

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。

注意

  • malloc_chunk 中的其餘結構成員,如 fd、 bk,沒有使用的必要而拿來儲存使用者資料;

  • 使用者請求的大小被轉換為內部實際大小,因為需要額外空間儲存 malloc_chunk,此外還需要考慮對齊。

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個名額!

掃描二維碼-免費領取

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