990      阿裏雲  技術社區[雲棲]

Linux堆內存管理深入分析(上)

0 前言

近年來，漏洞挖掘越來越火，各種漏洞挖掘、利用的分析文章層出不窮。從大方向來看，主要有基於棧溢出的漏洞利用和基於堆溢出的漏洞利用兩種。國內關於棧溢出的資料相對較多，這裏就不累述了，但是關於堆溢出的漏洞利用資料就很少了。鄙人以為主要是堆溢出漏洞的門檻較高，需要先吃透相應操作係統的堆內存管理機製，而這部分內容一直是一個難點。因此本係列文章主要從Linux係統堆內存管理機製出發，逐步介紹諸如基本堆溢出漏洞、基於unlink的堆溢出漏洞利用、double free、use-after-free等等常見的堆溢出漏洞利用技術。

前段時間偶然學習了這篇文章：

https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/comment-page-1/

該文是我近段時間以來讀到的最好文章之一，文章淺顯易懂，條例清晰，作為初學者的我從中學到了很多linux堆內存管理相關的知識。但是估計由於篇幅的限製，該文對很多難點一帶而過，造成部分知識點理解上的困難。因此我決定以該文為藍本，結合其他參考資料和自己的理解，寫一篇足夠詳細、完整的linux堆管理介紹文章，希冀能夠給其他初學者獻上微末之力。所以就內容來源而言，本文主要由兩部分組成：一部分是翻譯的上麵提及的文章；另一部分是筆者結合其他參考資料和自己的理解添加的補充說明。鑒於筆者知識能力上的不足，如有問題歡迎各位大牛斧正！

同樣的，鑒於篇幅過長，我將文章分成了上下兩部分，上部分主要介紹堆內存管理中的一些基本概念以及相互關係，同時也著重介紹了堆中chunk分配和釋放策略中使用到的隱式鏈表技術。後半部分主要介紹glibc malloc為了提高堆內存分配和釋放的效率，引入的顯示鏈表技術，即binlist的概念和核心原理。其中使用到的源碼在：

https://github.com/sploitfun/lsploits/tree/master/glibc

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實現的。關於這部分內容，一定要學習下麵這篇文章：

https://sploitfun.wordpress.com/2015/02/11/syscalls-used-by-malloc/

鑒於篇幅，本文就不加以詳細說明了，隻是為了方便後麵對堆內存管理的理解，截取其中函數調用關係圖：

圖1-1 函數調用關係圖

係統內存分布圖：

圖1-2係統內存分布圖

2 實驗演示

試想有如下代碼：

下麵我們依次分析其各個階段的堆內存分布狀況。

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的個數是跟係統中處理器核心個數相關的，如下表所示：

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中，便於管理。

2. malloc_state: 即Arena Header，每個thread隻含有一個Arena Header。Arena Header包含bins的信息、top chunk以及最後一個remainder chunk等(這些概念會在後文詳細介紹):

3. malloc_chunk: 即Chunk Header，一個heap被分為多個chunk，至於每個chunk的大小，這是根據用戶的請求決定的，也就是說用戶調用malloc(size)傳遞的size參數“就是”chunk的大小(這裏給“就是”加上引號，說明這種表示並不準確，但是為了方便理解就暫時這麼描述了，詳細說明見後文)。每個chunk都由一個結構體malloc_chunk表示：

可能有很多讀者會疑惑：該結構體裏麵並沒有一個類似於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的含義如下：

再進一步，發現沒必要保存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在內存分布中是相鄰的，即提高了內存分配的局部性。

最後更新：2017-04-10 22:01:15

  上一篇： 保證數據一致性的常見做法

  下一篇： [實踐] Android5.1.1源碼 - 讓某個APP以解釋執行模式運行