深入理解 glibc malloc:內存分配器實現原理
前言
堆內存(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 的基礎上引入了非主分配區的概念。)
- 申請堆的系統調用
我在之前的文章中提到過,malloc
內部通過brk
或mmap
系統調用向內核申請堆區。
譯者注:在內存管理領域,我們一般用「堆」指代用於分配動態內存的虛擬地址空間,而用「棧」指代用於分配靜態內存的虛擬地址空間。具體到虛擬內存佈局(Memory Layout),堆維護在通過
brk
系統調用申請的「Heap」及通過mmap
系統調用申請的「Memory Mapping Segment」中;而棧維護在通過彙編棧指令動態調整的「Stack」中。在 Glibc 裏,「Heap」用於分配較小的內存及主線程使用的內存。下圖爲 Linux 內核 v2.6.7 之後,32 位模式下的虛擬內存佈局方式。
- 多線程支持
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 還沒有創建!
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
...
sploitfun@sploitfun-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
...
sploitfun@sploitfun-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」部分。
sploitfun@sploitfun-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
...
sploitfun@sploitfun-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
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$
2.2.3. 在主線程 free 之後
從如下的輸出結果中我們可以看到,當分配的內存區域free
掉時,其並不會立即歸還給操作系統,而僅僅是移交給了作爲庫函數的分配器。這塊free
掉的內存添加在了「main arenas bin」中(在 glibc malloc 中,空閒列表數據結構被稱爲「bin」)。隨後當用戶請求內存時,分配器就不再向內核申請新堆了,而是先試着各個「bin」中查找空閒內存。只有當 bin 中不存在空閒內存時,分配器纔會繼續向內核申請內存。
sploitfun@sploitfun-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
...
sploitfun@sploitfun-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
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$
2.2.4. 在 thread1 malloc 之前
從如下的輸出結果中我們可以看到,此時 thread1 的堆尚不存在,但其棧已產生。
sploitfun@sploitfun-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
...
sploitfun@sploitfun-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]
...
sploitfun@sploitfun-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。
ploitfun@sploitfun-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
...
sploitfun@sploitfun-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]
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$
2.2.6. 在 thread1 free 之後
從如下的輸出結果中我們可以看到,free
不會把內存歸還給操作系統,而是移交給分配器,然後添加在了「thread arenas bin」中。
sploitfun@sploitfun-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
...
sploitfun@sploitfun-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]
...
sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$
- 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 的圖示如下(多堆段):
- 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 鏈表的後繼指針)。
- 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 最終將被分配得彼此靠近。
劉翔, 童薇, 劉景寧, 馮丹, 陳勁龍. 動態內存分配器研究綜述 [J]. 計算機學報, 2018,41(10):2359-2378.
譯者:貓科龍
https://blog.csdn.net/maokelong95/article/details/51989081
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/IKWZlJP-fZkj1G2NbvfjHQ