Linux堆內存管理深入分析（上）
小編語：本文曾發佈於阿里聚安全博客當中，是一篇非常詳細、完整的linux堆管理介紹文章，適合linux初學者。因此發布到知乎的專欄里，希望能給喜歡linux的小夥伴們帶來一點幫助。
0、前言
近年來，漏洞挖掘越來越火，各種漏洞挖掘、利用的分析文章層出不窮。從大方向來看，主要有基於棧溢出的漏洞利用和基於堆溢出的漏洞利用兩種。國內關於棧溢出的資料相對較多，這裡就不累述了，但是關於堆溢出的漏洞利用資料就很少了。鄙人以為主要是堆溢出漏洞的門檻較高，需要先吃透相應操作系統的堆內存管理機制，而這部分內容一直是一個難點。因此本系列文章主要從Linux系統堆內存管理機制出發，逐步介紹諸如基本堆溢出漏洞、基於unlink的堆溢出漏洞利用、double free、use-after-free等等常見的堆溢出漏洞利用技術。
前段時間偶然學習了這篇文章：
Understanding glibc malloc
該文是我近段時間以來讀到的最好文章之一，文章淺顯易懂，條例清晰，作為初學者的我從中學到了很多linux堆內存管理相關的知識。但是估計由於篇幅的限制，該文對很多難點一帶而過，造成部分知識點理解上的困難。因此我決定以該文為藍本，結合其他參考資料和自己的理解，寫一篇足夠詳細、完整的linux堆管理介紹文章，希冀能夠給其他初學者獻上微末之力。
所以就內容來源而言，本文主要由兩部分組成：一部分是翻譯的上面提及的文章；另一部分是筆者結合其他參考資料和自己的理解添加的補充說明。鑒於筆者知識能力上的不足，如有問題歡迎各位大牛斧正！
同樣的，鑒於篇幅過長，我將文章分成了上下兩部分，上部分主要介紹堆內存管理中的一些基本概念以及相互關係，同時也著重介紹了堆中chunk分配和釋放策略中使用到的隱式鏈表技術。後半部分主要介紹glibc malloc為了提高堆內存分配和釋放的效率，引入的顯示鏈表技術，即binlist的概念和核心原理。
其中使用到的源碼在：
sploitfun/lsploits
1、堆內存管理簡介
當前針對各大平台主要有如下幾種堆內存管理機制：
dlmalloc – General purpose allocator
ptmalloc2 – glibc
jemalloc – FreeBSD and Firefox
tcmalloc – Google
libumem – Solaris
本文主要學習介紹在linux glibc使用的ptmalloc2實現原理。
本來linux默認的是dlmalloc，但是由於其不支持多線程堆管理，所以後來被支持多線程的prmalloc2代替了。
當然在linux平台*malloc本質上都是通過系統調用brk或者mmap實現的。
關於這部分內容，一定要學習這篇文章：
Syscalls used by malloc.
鑒於篇幅，本文就不加以詳細說明了，只是為了方便後面對堆內存管理的理解，截取其中函數調用關係圖：
圖1-1 函數調用關係圖
系統內存分布圖：
圖1-2系統內存分布圖
2、實驗演示
試想有如下代碼：
/* Per thread arena example. */n#include <stdio.h>n#include <stdlib.h>n#include <pthread.h>n#include <unistd.h>n#include <sys/types.h>nvoid* threadFunc(void* arg) {n printf("Before malloc in thread 1n");n getchar();n char* addr = (char*) malloc(1000);n printf("After malloc and before free in thread 1n");n getchar();n free(addr);n printf("After free in thread 1n");n getchar();n}nint main() {n pthread_t t1;n void* s;n int ret;n char* addr;n printf("Welcome to per thread arena example::%dn",getpid());n printf("Before malloc in main threadn");n getchar();n addr = (char*) malloc(1000);n printf("After malloc and before free in main threadn");n getchar();n free(addr);n printf("After free in main threadn");n getchar();n ret = pthread_create(&t1, NULL, threadFunc, NULL);n if(ret)n {n printf("Thread creation errorn");n return -1;n }n ret = pthread_join(t1, &s);n if(ret)n {n printf("Thread join errorn");n return -1;n }n return 0;n}n
下面我們依次分析其各個階段的堆內存分布狀況。
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。
3、Arena介紹
3.1 Arena數量限制
在第2章中我們提到main thread和thread1有自己獨立的arena，那麼是不是無論有多少個線程，每個線程都有自己獨立的arena呢？答案是否定的。事實上，arena的個數是跟系統中處理器核心個數相關的，如下表所示：
For 32 bit systems:n Number of arena = 2 * number of cores + 1.nFor 64 bit systems:n Number of arena = 8 * number of cores + 1.n
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進行重複利用呢？
1)首先，glibc malloc循環遍歷所有可用的arenas，在遍歷的過程中，它會嘗試lock該arena。如果成功lock(該arena當前對應的線程並未使用堆內存則表示可lock)，比如將main arena成功lock住，那麼就將main arena返回給用戶，即表示該arena被線程3共享使用。
2)而如果沒能找到可用的arena，那麼就將線程3的malloc操作阻塞，直到有可用的arena為止。
3)現在，如果線程3再次調用malloc的話，glibc malloc就會先嘗試使用最近訪問的arena(此時為main arena)。如果此時main arena可用的話，就直接使用，否則就將線程3阻塞，直到main arena再次可用為止。
這樣線程3與主線程就共享main arena了。至於其他更複雜的情況，以此類推。
4、堆管理介紹
4.1 整體介紹
在glibc malloc中針對堆管理，主要涉及到以下3種數據結構：
1. heap_info: 即Heap Header，因為一個thread arena（注意：不包含main thread）可以包含多個heaps，所以為了便於管理，就給每個heap分配一個heap header。那麼在什麼情況下一個thread arena會包含多個heaps呢?在當前heap不夠用的時候，malloc會通過系統調用mmap申請新的堆空間，新的堆空間會被添加到當前thread arena中，便於管理。
typedef struct _heap_infon{n mstate ar_ptr; /* Arena for this heap. */n struct _heap_info *prev; /* Previous heap. */n size_t size; /* Current size in bytes. */n size_t mprotect_size; /* Size in bytes that has been mprotectedn PROT_READ|PROT_WRITE. */n /* Make sure the following data is properly aligned, particularlyn that sizeof (heap_info) + 2 * SIZE_SZ is a multiple ofn MALLOC_ALIGNMENT. */n char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];n} heap_info;n
2. malloc_state: 即Arena Header，每個thread只含有一個Arena Header。Arena Header包含bins的信息、top chunk以及最後一個remainder chunk等(這些概念會在後文詳細介紹):
struct malloc_staten{n /* Serialize access. */n mutex_t mutex;n /* Flags (formerly in max_fast). */n int flags;n /* Fastbins */n mfastbinptr fastbinsY[NFASTBINS];n /* Base of the topmost chunk -- not otherwise kept in a bin */n mchunkptr top;n /* The remainder from the most recent split of a small request */n mchunkptr last_remainder;n /* Normal bins packed as described above */n mchunkptr bins[NBINS * 2 - 2];n /* Bitmap of bins */n unsigned int binmap[BINMAPSIZE];n /* Linked list */n struct malloc_state *next;n /* Linked list for free arenas. */n struct malloc_state *next_free;n /* Memory allocated from the system in this arena. */n INTERNAL_SIZE_T system_mem;n INTERNAL_SIZE_T max_system_mem;n};n
3. malloc_chunk: 即Chunk Header，一個heap被分為多個chunk，至於每個chunk的大小，這是根據用戶的請求決定的，也就是說用戶調用malloc(size)傳遞的size參數「就是」chunk的大小(這裡給「就是」加上引號，說明這種表示並不準確，但是為了方便理解就暫時這麼描述了，詳細說明見後文)。每個chunk都由一個結構體malloc_chunk表示：
struct malloc_chunk {n /* #define INTERNAL_SIZE_T size_t */n INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */n INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */n struct malloc_chunk* fd; /* double links -- used only if free. 這兩個指針只在free chunk中存在*/n struct malloc_chunk* bk;n /* Only used for large blocks: pointer to next larger size. */n struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */n struct malloc_chunk* bk_nextsize;n};n
可能有很多讀者會疑惑：該結構體裡面並沒有一個類似於data的欄位來表示用戶申請到的堆內存空間啊？且該結構體明確含有2個size_t類型的成員，4個指針，這不就意味著malloc_chunk的大小是固定的了么？那它又如何能夠根據用戶的請求分配不同大小的內存呢？要想回答清楚這個問題，需要我們完全理解整個glibc malloc的堆內存管理機制，同時，本文的主要目的之一就是希冀解釋清楚這個概念，鑒於這部分內容較多，我將在後文的第5章加以詳細介紹。
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。
4.2 heap segment與arena關係
首先，通過內存分布圖理清malloc_state與heap_info之間的組織關係。
下圖是只有一個heap segment的main arena和thread arena的內存分布圖：
圖4-1 只含一個heap segment的main arena與thread arena圖
下圖是一個thread arena中含有多個heap segments的情況：
圖4-2 一個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，這樣就構成了一個單鏈表，方便後續管理。
5、對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這種數據結構是如何設計出來的，以及這樣設計的優缺點。
PS:鑒於時間和精力有限，後文介紹的演變歷程並沒有加以嚴格考證，筆者只是按照一些參考書籍、自己的理解以及便於文章內容安排做出的「善意的捏造」，如有錯誤，歡迎大家斧正！
5.1 隱式鏈表技術
前文說過，任何堆內存管理器都是以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在內存分布中是相鄰的，即提高了內存分配的局部性。
作者：走位@阿里聚安全，更多阿里的安全技術文章，請持續關注阿里聚安全的安全專欄，或訪問阿里聚安全博客
推薦閱讀：