0x01 堆內存管理簡介
當前針對各大平台主要有如下幾種堆內存管理機制：
dlmalloc – General purpose allocatorptmalloc2 – glibcjemalloc – FreeBSD and Firefoxtcmalloc – Googlelibumem – Solaris本文主要學習介紹在linux glibc使用的ptmalloc2實現原理。
本來linux默認的是dlmalloc，但是由於其不支持多線程堆管理，所以後來被支持多線程的prmalloc2代替了。
當然在linux平台*malloc本質上都是通過系統調用brk或者mmap實現的。關於這部分內容，一定要學習下面這篇文章：
https://sploitfun.wordpress.com/2015/02/11/syscalls-used-by-malloc/
鑒於篇幅，本文就不加以詳細說明了，只是為了方便後面對堆內存管理的理解，截取其中函數調用關系圖：
圖1-1 函數調用關系圖
系統內存分布圖：
圖1-2系統內存分布圖
試想有如下代碼：
#!cpp/* Per thread arena example. */#include#include #include #include #include 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;}
下面我們依次分析其各個階段的堆內存分布狀況。
1. Before malloc in main thread:
在程序調用malloc之前程序進程中是沒有heap segment的，並且在創建在創建線程前，也是沒有線程堆棧的。
2. After malloc?in main thread:
在主線程中調用malloc之後，就會發現系統給程序分配了堆棧，且這個堆棧剛好在數據段之上：
這就說明它是通過brk系統調用實現的。並且，還可以看出雖然我們只申請了1000字節的數據，但是系統卻分配了132KB大小的堆，這是為什麼呢？原來這132KB的堆空間叫做arena，此時因為是主線程分配的，所以叫做main arena(每個arena中含有多個chunk，這些chunk以鏈表的形式加以組織)。由於132KB比1000字節大很多，所以主線程後續再聲請堆空間的話，就會先從這132KB的剩余部分中申請，直到用完或不夠用的時候，再通過增加program break location的方式來增加main arena的大小。同理，當main arena中有過多空閒內存的時候，也會通過減小program break location的方式來縮小main arena的大小。
3. After free in main thread:
在主線程調用free之後：從內存布局可以看出程序的堆空間並沒有被釋放掉，原來調用free函數釋放已經分配了的空間並非直接“返還”給系統，而是由glibc 的malloc庫函數加以管理。它會將釋放的chunk添加到main arenas的bin(這是一種用於存儲同類型free chunk的雙鏈表數據結構，後問會加以詳細介紹)中。在這裡，記錄空閒空間的freelist數據結構稱之為bins。之後當用戶再次調用malloc申請堆空間的時候，glibc malloc會先嘗試從bins中找到一個滿足要求的chunk，如果沒有才會向操作系統申請新的堆空間。如下圖所示：
4. Before malloc in thread1:
在thread1調用malloc之前：從輸出結果可以看出thread1中並沒有heap segment，但是此時thread1自己的棧空間已經分配完畢了：
5. After malloc in thread1:
在thread1調用malloc之後：從輸出結果可以看出thread1的heap segment已經分配完畢了，同時從這個區域的起始地址可以看出，它並不是通過brk分配的，而是通過mmap分配，因為它的區域為b7500000-b7600000共1MB，並不是同程序的data segment相鄰。同時，我們還能看出在這1MB中，根據內存屬性分為了2部分：0xb7500000-0xb7520000共132KB大小的空間是可讀可寫屬性；後面的是不可讀寫屬性。原來，這裡只有可讀寫的132KB空間才是thread1的堆空間，即thread1 arena。
6. 在thread1調用free之後：同main thread。
0x03 Arena介紹在第2章中我們提到main thread和thread1有自己獨立的arena，那麼是不是無論有多少個線程，每個線程都有自己獨立的arena呢？答案是否定的。事實上，arena的個數是跟系統中處理器核心個數相關的，如下表所示：
#!cppFor 32 bit systems: Number of arena = 2 * number of cores + 1.For 64 bit systems: Number of arena = 8 * number of cores + 1.3.2 多Arena的管理
假設有如下情境：一台只含有一個處理器核心的PC機安裝有32位操作系統，其上運行了一個多線程應用程序，共含有4個線程——主線程和三個用戶線程。顯然線程個數大於系統能維護的最大arena個數（2*核心數 + 1= 3），那麼此時glibc malloc就需要確保這4個線程能夠正確地共享這3個arena，那麼它是如何實現的呢？
當主線程首次調用malloc的時候，glibc malloc會直接為它分配一個main arena，而不需要任何附加條件。
當用戶線程1和用戶線程2首次調用malloc的時候，glibc malloc會分別為每個用戶線程創建一個新的thread arena。此時，各個線程與arena是一一對應的。但是，當用戶線程3調用malloc的時候，就出現問題了。因為此時glibc malloc能維護的arena個數已經達到上限，無法再為線程3分配新的arena了，那麼就需要重復使用已經分配好的3個arena中的一個(main arena, arena 1或者arena 2)。那麼該選擇哪個arena進行重復利用呢？
首先，glibc malloc循環遍歷所有可用的arenas，在遍歷的過程中，它會嘗試lock該arena。如果成功lock(該arena當前對應的線程並未使用堆內存則表示可lock)，比如將main arena成功lock住，那麼就將main arena返回給用戶，即表示該arena被線程3共享使用。而如果沒能找到可用的arena，那麼就將線程3的malloc操作阻塞，直到有可用的arena為止。現在，如果線程3再次調用malloc的話，glibc malloc就會先嘗試使用最近訪問的arena(此時為main arena)。如果此時main arena可用的話，就直接使用，否則就將線程3阻塞，直到main arena再次可用為止。這樣線程3與主線程就共享main arena了。至於其他更復雜的情況，以此類推。
0x04 堆管理介紹在glibc malloc中針對堆管理，主要涉及到以下3種數據結構：
1. heap_info: 即Heap Header，因為一個thread arena（注意：不包含main thread）可以包含多個heaps，所以為了便於管理，就給每個heap分配一個heap header。那麼在什麼情況下一個thread arena會包含多個heaps呢?在當前heap不夠用的時候，malloc會通過系統調用mmap申請新的堆空間，新的堆空間會被添加到當前thread arena中，便於管理。
#!cpptypedef struct _heap_info{ mstate ar_ptr; /* Arena for this heap. */ struct _heap_info *prev; /* Previous heap. */ size_t size; /* Current size in bytes. */ size_t mprotect_size; /* Size in bytes that has been mprotected PROT_READ|PROT_WRITE. */ /* Make sure the following data is properly aligned, particularly that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of MALLOC_ALIGNMENT. */ char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];} heap_info;
2. malloc_state: 即Arena Header，每個thread只含有一個Arena Header。Arena Header包含bins的信息、top chunk以及最後一個remainder chunk等(這些概念會在後文詳細介紹):
#!cppstruct malloc_state{ /* Serialize access. */ mutex_t mutex; /* Flags (formerly in max_fast). */ int flags; /* Fastbins */ mfastbinptr fastbinsY[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 - 2]; /* Bitmap of bins */ unsigned int binmap[BINMAPSIZE]; /* Linked list */ struct malloc_state *next; /* Linked list for free arenas. */ struct malloc_state *next_free; /* Memory allocated from the system in this arena. */ INTERNAL_SIZE_T system_mem; INTERNAL_SIZE_T max_system_mem;};
3. malloc_chunk: 即Chunk Header，一個heap被分為多個chunk，至於每個chunk的大小，這是根據用戶的請求決定的，也就是說用戶調用malloc(size)傳遞的size參數“就是”chunk的大小(這裡給“就是”加上引號，說明這種表示並不准確，但是為了方便理解就暫時這麼描述了，詳細說明見後文)。每個chunk都由一個結構體malloc_chunk表示：
#!cppstruct malloc_chunk { /* #define INTERNAL_SIZE_T size_t */ 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. 這兩個指針只在free chunk中存在*/ 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;};
可能有很多讀者會疑惑：該結構體裡面並沒有一個類似於data的字段來表示用戶申請到的堆內存空間啊？且該結構體明確含有2個size_t類型的成員，4個指針，這不就意味著malloc_chunk的大小是固定的了麼？那它又如何能夠根據用戶的請求分配不同大小的內存呢？要想回答清楚這個問題，需要我們完全理解整個glibc malloc的堆內存管理機制，同時，本文的主要目的之一就是希冀解釋清楚這個概念，鑒於這部分內容較多，我將在後文的第5章加以詳細介紹。
4.2 heap segment與arena關系NOTE:
1. Main thread不含有多個heaps所以也就不含有heap_info結構體。當需要更多堆空間的時候，就通過擴展sbrk的heap segment來獲取更多的空間，直到它碰到內存mapping區域為止。 2. 不同於thread arena，main arena的arena header並不是sbrk heap segment的一部分，而是一個全局變量！因此它屬於libc.so的data segment。
首先，通過內存分布圖理清malloc_state與heap_info之間的組織關系。
下圖是只有一個heap segment的main arena和thread arena的內存分布圖：
圖4-1 只含一個heap segment的main arena與thread arena圖
下圖是一個thread arena中含有多個heap segments的情況：
圖4-1 一個thread arena含有多個heap segments的內存分布圖
從上圖可以看出，thread arena只含有一個malloc_state(即arena header)，卻有兩個heap_info(即heap header)。由於兩個heap segments是通過mmap分配的內存，兩者在內存布局上並不相鄰而是分屬於不同的內存區間，所以為了便於管理，libc malloc將第二個heap_info結構體的prev成員指向了第一個heap_info結構體的起始位置（即ar_ptr成員），而第一個heap_info結構體的ar_ptr成員指向了malloc_state，這樣就構成了一個單鏈表，方便後續管理。
0x05 對chunk的理解在glibc malloc中將整個堆內存空間分成了連續的、大小不一的chunk，即對於堆內存管理而言chunk就是最小操作單位。Chunk總共分為4類：1)allocated chunk; 2)free chunk; 3)top chunk; 4)Last remainder chunk。從本質上來說，所有類型的chunk都是內存中一塊連續的區域，只是通過該區域中特定位置的某些標識符加以區分。為了簡便，我們先將這4類chunk簡化為2類：allocated chunk以及free chunk，前者表示已經分配給用戶使用的chunk，後者表示未使用的chunk。
眾所周知，無論是何種堆內存管理器，其完成的核心目的都是能夠高效地分配和回收內存塊(chunk)。因此，它需要設計好相關算法以及相應的數據結構，而數據結構往往是根據算法的需要加以改變的。既然是算法，那麼算法肯定有一個優化改進的過程，所以本文將根據堆內存管理器的演變歷程，逐步介紹在glibc malloc中chunk這種數據結構是如何設計出來的，以及這樣設計的優缺點。
5.1 隱式鏈表技術PS:鑒於時間和精力有限，後文介紹的演變歷程並沒有加以嚴格考證，筆者只是按照一些參考書籍、自己的理解以及便於文章內容安排做出的“善意的捏造”，如有錯誤，歡迎大家斧正！
前文說過，任何堆內存管理器都是以chunk為單位進行堆內存管理的，而這就需要一些數據結構來標志各個塊的邊界，以及區分已分配塊和空閒塊。大多數堆內存管理器都將這些邊界信息作為chunk的一部分嵌入到chunk內部，典型的設計如下所示：
圖5-1 簡單的allocated chunk格式
圖5-2 簡單的free chunk格式
堆內存中要求每個chunk的大小必須為8的整數倍，因此chunk size的後3位是無效的，為了充分利用內存，堆管理器將這3個比特位用作chunk的標志位，典型的就是將第0比特位用於標記該chunk是否已經被分配。這樣的設計很巧妙，因為我們只要獲取了一個指向chunk size的指針，就能知道該chunk的大小，即確定了此chunk的邊界，且利用chunk size的第0比特位還能知道該chunk是否已經分配，這樣就成功地將各個chunk區分開來。注意在allocated chunk中padding部分主要是用於地址對齊的(也可用於對付外部碎片)，即讓整個chunk的大小為8的整數倍。
通過上面的設計，我們就能將整個堆內存組織成一個連續的已分配或未分配chunk序列:
圖5-3 簡單的chunk序列
上面的這種結構就叫做隱式鏈表。該鏈表隱式地由每個chunk的size字段鏈接起來，在進行分配操作的時候，堆內存管理器可以通過遍歷整個堆內存的chunk，分析每個chunk的size字段，進而找到合適的chunk。
細心的讀者可能發現：這種隱式鏈表效率其實是相當低的，特別是在內存回收方面，它難以進行相鄰多個free chunk的合並操作。我們知道，如果只對free chunk進行分割，而不進行合並的話，就會產生大量小的、無法繼續使用的內部碎片，直至整個內存消耗殆盡。因此堆內存管理器設計了帶邊界標記的chunk合並技術。
1.帶邊界標記的合並技術
試想如下場景：假設我們要釋放的chunk為P，它緊鄰的前一個chunk為FD，緊鄰的後一個chunk為BK，且BK與FD都為free chunk。將P於BK合並在一起是很容易的，因為可以通過P的size字段輕松定位到BK的開始位置，進而獲取BK的size等等，但是將P於FD合並卻很難，我們必須從頭遍歷整個堆，找到FD，然後加以合並，這就意味著每次進行chunk釋放操作消耗的時間與堆的大小成線性關系。為了解決這個問題，Knuth提出了一種聰明而通用的技術——邊界標記。
Knuth在每個chunk的最後添加了一個腳部(Footer)，它就是該chunk 頭部(header)的一個副本，我們稱之為邊界標記：
圖5-4 改進版的chunk格式之Knuth邊界標記
顯然每個chunk的腳部都在其相鄰的下一個chunk的頭部的前4個字節處。通過這個腳部，堆內存管理器就可以很容易地得到前一個chunk的起始位置和分配狀態，進而加以合並了。
但是，邊界標記同時帶來了一個問題：它要求每個塊都包含一個頭部和腳部，如果應用程序頻繁地進行小內存的申請和釋放操作的話(比如1，2個字節)，就會造成很大的性能損耗。同時，考慮到只有在對free chunk進行合並的時候才需要腳部，也就是說對於allocated chunk而言它並不需要腳部，因此我們可以對這個腳部加以優化——將前一個chunk的已分配/空閒標記位存儲在當前chunk的size字段的第1，或2比特位上，這樣如果我們通過當前chunk的size字段知道了前一個chunk為free chunk，那麼就可得出結論：當前chunk地址之前的4個字節為前一個free chunk的腳部，我們可以通過該腳部獲取前一個chunk的起始位置；如果當前chunk的size字段的標記位表明前一個chunk是allocated chunk的話，那麼就可得出另一個結論：前一個chunk沒有腳部，即當前chunk地址之前的4個字節為前一個allocated chunk的payload或padding的最後部分。新的chunk格式圖如下：
圖5-5 改進版的Knuth邊界標記allocated chunk格式
圖5-6 改進版的Knuth邊界標記free chunk格式
2.再進化——支持多線程
隨著技術的發展，特別是堆內存管理器添加對多線程的支持，前述的chunk格式已經難以滿足需求，比如，我們需要標志位來標記當前chunk是否屬於非主線程即thread arena，以及該chunk由mmap得來還是通過brk實現等等。但此時chunk size只剩下一個比特位未使用了，怎麼辦呢？這需要對chunk格式進行大手術！
首先思考：是否有必要同時保存當前chunk和前一個chunk的已分配/空閒標記位？答案是否定的，因為我們只需要保存前一個chunk的分配標志位就可以了，至於當前chunk的分配標志位，可以通過查詢下一個chunk的size字段得到。那麼size字段中剩下的兩個比特位就可以用於滿足多線程的標志需求了：
圖5-7 多線程版本Knuth邊界標記allocated chunk格式
圖5-8 多線程版本Knuth邊界標記free chunk格式
這裡的P,M,N的含義如下：
PREV_INUSE(P): 表示前一個chunk是否為allocated。IS_MMAPPED(M)：表示當前chunk是否是通過mmap系統調用產生的。NON_MAIN_ARENA(N)：表示當前chunk是否是thread arena。再進一步，發現沒必要保存chunk size的副本，也就是說Footer的作用並不大，但是如果前一個chunk是free的話，在合並的時候我們又需要知道前一個chunk的大小，怎麼辦呢？將Footer從尾部移到首部，同時其不再保存當前chunk的size，而是前一個free chunk的size不就行了。同樣的，為了提高內存利用率，如果前一個chunk是allocated chunk的話，這個Footer就作為allocated chunk的payload或padding的一部分，結構圖如下：
圖5-9 當前glibc malloc allocated chunk格式
圖5-10 當前glibc malloc free chunk格式
至此，glibc malloc堆內存管理器中使用的隱式鏈表技術就介紹完畢了。現在我們再回過頭去看malloc_chunk結構體就很好理解了：該結構體通過每個chunk的prev_size和size構成了隱式鏈表，而後續的fd, bk等指針並不是作用於隱式鏈表的，而是用於後文會介紹的用於加快內存分配和釋放效率的顯示鏈表bin(還記得bin麼？用於記錄同一類型free chunk的鏈表)，並且這些指針跟prev_size一樣只在free chunk中存在。關於顯示鏈表bin的原理比較復雜，讓我們帶著疑惑，暫時略過這部分信息，等介紹完所有chunk之後再加以詳細介紹。
5.2 Top Chunk當一個chunk處於一個arena的最頂部(即最高內存地址處)的時候，就稱之為top chunk。該chunk並不屬於任何bin，而是在系統當前的所有free chunk(無論那種bin)都無法滿足用戶請求的內存大小的時候，將此chunk當做一個應急消防員，分配給用戶使用。如果top chunk的大小比用戶請求的大小要大的話，就將該top chunk分作兩部分：1）用戶請求的chunk；2）剩余的部分成為新的top chunk。否則，就需要擴展heap或分配新的heap了——在main arena中通過sbrk擴展heap，而在thread arena中通過mmap分配新的heap。
5.3 Last Remainder Chunk要想理解此chunk就必須先理解glibc malloc中的bin機制。如果你已經看了第二部分文章，那麼下面的原理就很好理解了，否則建議你先閱讀第二部分文章。對於Last remainder chunk，我們主要有兩個問題：1)它是怎麼產生的；2)它的作用是什麼？
先回答第一個問題。還記得第二部分文章中對small bin的malloc機制的介紹麼？當用戶請求的是一個small chunk，且該請求無法被small bin、unsorted bin滿足的時候，就通過binmaps遍歷bin查找最合適的chunk，如果該chunk有剩余部分的話，就將該剩余部分變成一個新的chunk加入到unsorted bin中，另外，再將該新的chunk變成新的last remainder chunk。
然後回答第二個問題。此類型的chunk用於提高連續malloc(small chunk)的效率，主要是提高內存分配的局部性。那麼具體是怎麼提高局部性的呢？舉例說明。當用戶請求一個small chunk，且該請求無法被small bin滿足，那麼就轉而交由unsorted bin處理。同時，假設當前unsorted bin中只有一個chunk的話——就是last remainder chunk，那麼就將該chunk分成兩部分：前者分配給用戶，剩下的部分放到unsorted bin中，並成為新的last remainder chunk。這樣就保證了連續malloc(small chunk)中，各個small chunk在內存分布中是相鄰的，即提高了內存分配的局部性。
