近期的在看 pwn 的一些東西，發現無論是實際場景中，還是 CTF 中，堆的利用越來越多，又由于各種環境下堆的實現都不太一樣，因此就讓皂皂翻譯這篇文章, 我也對本文作了潤色修改，以饗讀者。
原文：https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/comment-page-1/
我一直在執著于堆的一些問題。比如以下幾個
雖然之前經常在想這些問題，但是光想并沒有什么卵用。正好，最近我找到了點時間來好好思考這些問題。所以現在我就來分享一下這些知識的總結。此外，還有很多可用的內存分配器：
每種內存分配器都說他們是最快的、可擴展并且具有高效的內存使用！！但是并非所有的分配器都適合我們自己的應用程序。內存消耗大的應用性能很大程度依賴于內存分配器的性能。本文中，我只討論 "glibc malloc” 內存分配器。并希望今后能涉及到其他內存分配器的討論。本文中為了更好的理解 ”glibc malloc”,我會聯系它最近的源碼來談。好，下面系好你的安全帶，我們開啟探索 glibc malloc 的旅程！！
歷史： ptmalloc2 來自于 dlmalloc 的分支。此后，添加線程支持并于 2006 年發布。正式發布后，patmalloc2 集成到 glibc 源碼中。隨著源碼集成，代碼修改便直接在 glibc malloc 源碼里進行。因此 ptmalloc2 與 glibc 之間的 malloc 實現有很多不同。
系統調用：在之前的文章可見malloc的內部調用不是 brk 就是 mmap 系統調用。
線程化：在早期的 Linux 里，dlmalloc 被用做默認的內存分配器。但之后因為 ptmalloc2 添加了線程支持，ptmalloc2 成為了 Linux 默認內存分配器。線程支持可幫助提升內存分配器以及應用程序的性能。在 dlmalloc 里，當兩個線程同時調用 malloc 時，只有一個線程能進入到臨界段，因為這里的空閑列表數據結構是所有可用線程共用的。因此內存分配器要在多線程應用里耗費時間，從而導致性能降低。然而在 ptmalloc2 里，當兩個線程同時調用 malloc 時，會立即分配內存。因為每個線程維護一個單獨的堆分段，因此空閑列表數據結構正在維護的這些堆也是獨立的。這種維護獨立堆以及每一個線程享有空閑列表數據結構的行為被稱為 Per Thread Arena。
#!c
/* 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;
}
輸出分析：
在主線程 malloc 之前：在以下輸出里我們可以看到，由于 thread1 尚未創建，這里尚無堆分段，也沒有線程棧。
#!bash
[email protected]:~/ptmalloc.ppt/mthread$ ./mthread
Welcome to per thread arena example::6501
Before malloc in main thread
...
[email protected]:~/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]:~/ptmalloc.ppt/mthread$
在主線程 malloc 之后: 在下面的輸出里我們可以看到，堆正好被創建在數據段附近（0804b000-0806c000），這表明堆的空間是由調用高級別的中斷所創建（即，使用 brk 系統調用）。還要注意的是，即使用戶只發出了 1000 bytes 請求，就會創建 132 KB 大小的堆內存。這個堆內存的連續區域被稱為「arena」。這個 arena 是由主線程創建，則被稱為main arena。進一步的分配請求會繼續使用這個 arena 直到 arena 空閑空間耗盡。當 arena 耗盡空閑空間 時，它能在線程調用高級別的中斷的位置時建立（調整建立開始塊的 size 以包含額外空間之后）。類似地，arena 也能在 top chunk 有大量空閑空間時回收。
注：top chunk 是一個 arena 里最多的塊。關于它的更多細節，請看以下 "Top Chunk" 部分
#!bash
[email protected]:~/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]:~/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]:~/ptmalloc.ppt/mthread$
在主線程 Free 之后： 在以下輸出里我們可以看到，當分配內存區域被釋放時，其后內存不會被立即釋放給操作系統。分配內存區域（1000 bytes 大小）只釋放給 "glibc malloc" 庫，在這里的釋放掉的 Chunk 會被添加到 main arenas 中（在 glibc malloc 里，freelist 這種數據結構被稱為 bins 譯者注：freelist 是一種單向鏈表）。此后當用戶申請內存時，glibc malloc 不會從內核中獲得新的堆內存，而是盡量在 bins 里找到一個空閑塊(Free Chunk)。只有當沒有空閑塊存在時，glibc malloc 才會從繼續內核中申請內存。
#!bash
[email protected]:~/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]:~/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]:~/ptmalloc.ppt/mthread$
在線程1 malloc 之前：在以下輸出中我們可以看到，這里沒有 thread1 的堆但現在 thread1 的每一線程棧已被創建。
#!bash
[email protected]:~/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
...
[email protected]:~/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]:~/ptmalloc.ppt/mthread$
在線程1 malloc 之后：在以下輸出里我們可以看到，thread1 的堆被創建了。且在內存映射段區域出現（b7500000-b7521000 大小為 132 KB），這表明堆內存通過使用 mmap 系統調用而不是主線程（使用 sbrk）創建。這里再一次看到，即使用戶只請求 1000 bytes，1MB 大小的堆內存還是會被映射到進程地址空間中。而1 MB 以外只有 132KB 被設置有讀寫權限，并同時成為該線程的堆。這塊內存（132KB）區域被稱為thread arena。
注：當用戶申請的內存大小超過 128KB（ malloc(132*1024) ）并且當一個 arena 里沒有足夠的空間來滿足用戶的請求時，內存是使用 mmap 系統調用來分配的（不使用 sbrk） 無論這個請求是來自于 main arena 還是 thread arena。
#!bash
[email protected]:~/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]:~/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]:~/ptmalloc.ppt/mthread$
在線程1 free 掉后：在以下輸出我們可以看到，釋放分配內存區域的過程中并不會把堆釋放到操作系統。取而代之的是這塊被分配的內存區域（1000 bytes 大小）還是 被釋放 到了 "glibc malloc" 里，并將這個釋放塊添加到 thread arenas 的 bins 里。
#!bash
[email protected]:~/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]:~/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]:~/ptmalloc.ppt/mthread$
Arena的數量：在以上示例中，我們看到了主線程包含 main arena 同時 thread 1 包含了它自己的 thread arena。所以不論線程數量，在線程與 arena 之間可以有一對一的映射嗎？當然沒有。一個 arena 應用程序可以包含更多數量的線程（相較于 Cores 的數量），在這樣的情況下，每個線程擁有一個 arena 顯得有些不值。因此，應用程序的arena 數量的限制是基于系統里現有的 Cores 的數量。
#!bash
For 32 bit systems:
Number of arena = 2 * number of cores.
For 64 bit systems:
Number of arena = 8 * number of cores.
示例：我們來看一個多線程應用（4線程 ---||- 主線程 + 3個用戶線程）在一個單核的 32 位系統上運行。這里線程數量（4）> 2 * 核心數量（2）。因此，"glibc malloc" 認定 Multiple Arena 被所有可用進程共享。但它是怎樣共享的呢？
當主線程，第一次調用 malloc 時，在沒有任何競爭的情況下，已經創建了 main arena。
當 thread 1 和 thread 2 第一次調用 malloc 時，會為這些線程創建一個新的 arena 并且是在無任何競爭的情況下被使用。直到所有線程和 arena 有一對一映射時。
當 thread 3 第一次調用 malloc 時， arena 限制的數量被算出。這里超過了 arena 數量的限制，因此嘗試重用 現存的 arena （main arena 或 arena 1 或 arena 2）
重用:
一旦遍歷了所有可用的 arena，就會盡量去鎖定可用的 arena。
如果鎖定成功（我們假設說 main arena 被鎖定成功），就向用戶返回該 arena。
如果沒有 arena 是空閑的，請看接下來的 arena 代碼區。
現在當 thread 3 第二次調用 malloc 時，malloc 會盡量使用上次訪問的 arena （main arena）。如果 main arena 是空閑的， thread 3 會一直使用該 arena 并屏蔽其他線程的申請直到 main arena 被釋放。 main arena 就是如此這般在主線程和 thread 3 間共享。
在 “glibc malloc”源代碼里主要發現以下三種數據結構：
heap_info – 堆頭 – 單個 thread arena 有多個堆。每個堆有它自己的頭。為什么需要多個堆？每個 thread arena 開始都只有一個堆，但當這個堆耗盡空間時，新的堆（并不連續的）能 mmap 到這個 arena 里。
malloc_state – Arena 頭 – 單個 thread arena 有多個堆，但是對于所有這些堆來說，只存在一個 arena 頭。arena 頭 包含 bins、top chunk、最后剩余塊……
malloc_chunk – 塊頭 – 一個堆基于用戶請求被分為很多塊。每個塊有它自己的塊頭。
注：
Main arena 沒有多重堆，因此沒有 heap_info 結構。當main arena 耗盡空間時，sbrk 堆被擴展（連續區域）直到它轉儲到內存映射分段中。
不像 thread arena，main arena 的 Arena 頭不是 sbrk 堆分段的一部分。它是一個全局變量，因此可以在 libc 里找到它以及數據分段。
main arena 和 thread arena 的形象化視圖（單個堆分段）：
thread arena 的形象化視圖（多個堆分段）：
Chunk ：在堆里的塊可以是以下幾種類型中的一種：
size: 這部分包含了此處 Allocated 塊的容量大小，該部分最后 3 bits 包含了關鍵信息。 PREV_INUSE (P) – 這一 bit 在前一個塊被分配時就被設置。 IS_MMAPPED (M) – 這一 bit 在塊即在 mmap 時被設置。 NON_MAIN_ARENA (N) – 這一 bit 在塊分配給 thread arena 時設置。
注意:
其他 malloc_chunk （比如 fd -- forward point，bk-- back point）的部分不會用于分配塊。因此用戶數據在這個區域。
由于存儲 malloc_chunk 需要一些額外的空間，用戶請求的容量大小轉換成了可用的大小。轉化通過不設置可用容量的最后 3 bits 的方式進行，因此它用于存儲關鍵信息。
Free Chunk（空閑塊）:
prev_size： 兩個空閑塊是不能毗連在一起的。當兩個塊都空閑時，它就會與一個單獨的空閑塊連接。因此前一個塊及當前這個釋放的塊會被分配，同時 prev_size 包含前一個塊的用戶數據。 size: 這個部分包含有空閑塊的 size。 fd: 前指針 – 同一容器里指向下一塊的指針（不是指向物理內存內的下一塊）。 Bins：Bins 是 freelist 數據結構。用以支持 Free Chunk。基于塊的大小，有幾種可用的 bins：
Fast bin 快速bin Unsorted bin 無序bin Small bin 小bin Large bin 大bin
被用來支持這些 bin 的數據結構有：
fastbinsY: 該數組支持 fast bins bins: 該數組支持 unsorted，small 以及 large 容器。總共 126 個容器被劃分為以下幾種： Bin 1 – Unsorted bin Bin 2 to Bin 63 – Small bin Bin 64 to Bin 126 – Large bin
Fast Bin: 大小在 16 到 80 bytes 的塊叫做 fast chunk 。支持 fast chunk 的 bin 叫做 fast bins。在上述的這些 bin 里，fast bins 在內存分配和重新分配上更快。（譯者注：只有 fast bin 是 LIFO 其他的 bin 都是 FIFO）
bin 數量 - 10
每個 fast bin 包含 free chunk 的一個單向鏈表。既然在 fast bins 里，在列表中間塊不會被移除，單向鏈接列表被使用。添加和刪除都在列表末尾之前進行 - LIFO（后進先出）。
Chunk size – 8 bytes apart 塊大小（size） - 8 bytes 累加
Fast bins 包含大小為 8 bytes 累加的塊的 binlist 。即，第一個 fast bin(index 0) 包含 16 bytes 塊的binlist，第二個 fast bin (index 1)包含 24 bytes 以此類推……（譯者注：binlist 是 bin 的一個鏈表） 在一個獨有的 fast bin 內的塊大小是一樣的。
在 malloc 初始化 過程中，最大的 fast bin 的大小設置為 64 (!80) bytes。因此通過塊的默認大小設置為 16 到 64 就可以將其劃分為 fast chunks 了。 不能合并 - 空閑的兩個塊可以相鄰，但不能合并為一個空閑塊。不能合并導致產生外存儲碎片，但它可以大大提速！！ malloc(fast chunk) –
初始狀態 fast bin 的最大容積 以及 fast bin 目錄是空的，因此即使用戶請求一個 fast chunk，服務它的是 small bin code 而不是 fast bin code。
之后當它不再為空時， 計算 fast bin 目錄以檢索其對應的 binlist。
來自以上被檢索 binlist 的第一個塊會被移除并返回給用戶。
free(fast chunk) –
計算 Fast bin 目錄以檢索其對應的 binlist。 該空閑塊被添加到以上檢索 binlist 的最前位置。
Unsorted Bin: 當小或者大的塊被釋放而非把他們添加到各自 bin 里時，它會被添加到 unsorted bin 里。 該途徑給了 "glibc malloc" 第二個機會再次利用最近釋放的塊。因此內存分配以及回收的速度都會有所提升（因為 unsorted bin）由于排除了用于查找合適容器的時間。
Number of bins – 1
Unsorted bin 包含空閑塊的一個循環雙向鏈表（也稱為 binlist 容器列表）。 塊的大小 - 沒有大小限制，任何大小的塊都屬于此容器。
Small Bin: 小于 512 bytes 的塊叫做 small chunk。 支持 small chunks 的容器叫做 small bins。 Small bins 在內存分配和回收時比 large bins 快（比 fast bins 慢）。
Number of bins – 62
Chunk Size – 8 bytes 遞增
合并 - 空閑的兩個塊不能毗鄰，會被合并為一個空閑塊。合并消除了外存儲碎片但是運行大大減速！！
malloc(small chunk) – * 初始狀態下所有 small bins 都是 NULL，因此即使用戶請求一個 small chunk，提供服務的是 unsorted bin code 而不是 small bin code。 * 在第一次調用 malloc 期間，在 malloc_state 里發現的 small bin 和 large bin 數據結構（bins 容器）被初始化（即，bins 會指向它自己表示他們是空的）。 * 之后當 small bin 處于非空狀態時，其對應 binlist 中的最后一個塊會被移除并返回給用戶。 free(small chunk) – * 釋放塊時，查看其前一個或下一個塊是否空閑，如果空閑就合并（即，從他們各自的鏈表里解除塊的鏈接，然后在 unsorted bin 的鏈表最開端添加新的統一的塊）。
Large Bin: 大小大于等于 512 bytes 的塊稱為 large chunk。支持 large chunks 的 bins 叫作 large bins。Large bins 在內存分配和回收中比 small bins 要慢。
Number of bins – 63 每個 large bin 包含空閑塊的一個循環雙向鏈表（也稱為 binlist ）。在 large bins 里，塊在任何位置（前端或中間或尾部）被添加或移除后，開始使用雙向鏈表。 這 63 bins 以外：
不同于 small bin，在 large bin 里的塊大小是不同的。因此他們以降序排列。最大的塊在最前端而最小的塊被排到 binlist 的末尾。
合并 - 空閑的兩個塊不能相鄰，而是合并為一個空閑塊。
malloc(large chunk) –
初始化狀態下所有 large bins 都是 NULL，因此即使用戶請求一個 large chunk，是下一個最大的 bin code 提供服務，而不是 large bin code。
同樣在第一次調用 malloc 期間，在 malloc_state 里發現的 small bin 和 large bin 數據結構（bins）被初始化。即，bins 會指向它自己表示它們是空的。
此后當 large bin 不為空時，如果最大塊的大小（在它的容器列表里）比用戶請求的大小還大， binlist 會從尾部到頭部，來查找一個大小接近或等于用戶請求大小的合適的塊。一旦找到，這個塊將分裂為兩個塊。
用戶塊（擁有用戶請求的大小）-返回給用戶。
剩余塊（擁有剩余容量的大小）-添加到 unsorted bin。
如果最大塊的大小（在它的容器列表里）小于用戶請求的大小，那么盡量使用下一個最大（非空）bin 為用戶的請求提供服務。下一個最大的 bin code 會掃描容器映射來查找下一個最大的非空 bin ，如果找到任何一個，從 binlist 里檢索到了一個合適的塊，分裂并返回給用戶。如果沒找到，嘗試使用Top Chunk為用戶請求提供服務。
free(large chunk) – 它的程序與空閑（small chunk）類似。
Top Chunk: 在一個 arena 頂部邊框的塊叫做開始塊(Top Chunk)。它不屬于任何容器。在任一 bin 里，Top Chunk被用于在沒有空閑塊時為用戶請求提供服務。
用戶塊（擁有用戶請求的大小） 剩余塊（擁有剩余容量的大小）
剩余塊變成新的頂部。如果開始塊大小比用戶請求的大小要少，開始塊使用 sbrk (main arena) 或 mmap (thread arena)系統調用來擴展。
最后剩余塊：是來自一個小請求的最近一次分裂的剩余。最后剩余塊幫助引用地址（即，small chunks 的連續 malloc 請求可能在被分配時結束）彼此間更靠近。
但是除了在一個 arena 里可利用的的眾多塊，哪些塊有資格成為最后剩余塊呢？
當一個用戶請求 small chunk 時, 不能通過 small bin 以及 unsorted bin 提供服務，這時會掃描 bin 映射會以查找下一個最大（非空）bin 。就像之前所說，一旦找到下一個最大（非空）bin ，它將分裂成兩塊，用戶塊返回給用戶，同時剩余塊添加到 unsorted bin。此外，它會變成新的最后剩余塊。
引用地址是怎樣歸檔的？
現在當用戶隨后請求的一個 small chunk 并且最后剩余塊是 unsorted bin 里唯一的塊時，最后剩余塊會分裂成兩塊，用戶塊會返回給用戶同時剩余的那個塊會添加到 unsorted bin。此外，它還會成為新的一個最后剩余塊。如此后續的內存分配會相繼結束。