Linux堆內存管理深入分析（下）

Linux堆內存管理深入分析
(下半部)
作者@走位，阿裡聚安全

0 前言回顧

在上一篇文章中（鏈接見文章底部），詳細介紹了堆內存管理中涉及到的基本概念以及相互關系，同時也著重介紹了堆中chunk分配和釋放策略中使用到的隱式鏈表技術。通過前面的介紹，我們知道使用隱式鏈表來管理內存chunk總會涉及到內存的遍歷，效率極低。對此glibc malloc引入了顯示鏈表技術來提高堆內存分配和釋放的效率。
所謂的顯示鏈表就是我們在數據結構中常用的鏈表，而鏈表本質上就是將一些屬性相同的“結點”串聯起來，方便管理。在glibc malloc中這些鏈表統稱為bin，鏈表中的“結點”就是各個chunk，結點的共同屬性就是：1)均為free chunk；2)同一個鏈表中各個chunk的大小相等(有一個特例，詳情見後文)。

1 bin介紹

如前文所述，bin是一種記錄free chunk的鏈表數據結構。系統針對不同大小的free chunk，將bin分為了4類：1) Fast bin; 2) Unsorted bin; 3) Small bin; 4) Large bin。
在glibc中用於記錄bin的數據結構有兩種，分別如下所示：
fastbinsY: 這是一個數組，用於記錄所有的fast bins；
bins: 這也是一個數組，用於記錄除fast bins之外的所有bins。事實上，一共有126個bins，分別是：
bin 1 為unsorted bin;
bin 2 到63為small bin;
bin 64到126為large bin。
其中具體數據結構定義如下：
struct malloc_state
{
……
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
……
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2]; // #define NBINS 128
……
};
這裡mfastbinptr的定義：typedef struct malloc_chunk *mfastbinptr;
mchunkptr的定義：typedef struct malloc_chunk* mchunkptr;
畫圖更直觀：

圖1-1 bins分類
那麼處於bins中個各個free chunk是如何鏈接在一起的呢？回顧malloc_chunk的數據結構：
struct 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; /* 這兩個指針只在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;
};
其中的fd和bk指針就是指向當前chunk所屬的鏈表中forward或者backward chunk。

2 Fast bin

既然有fast bin，那就肯定有fast chunk——chunk size為16到80字節的chunk就叫做fast chunk。為了便於後文描述，這裡對chunk大小做如下約定：
1) 只要說到chunk size，那麼就表示該malloc_chunk的實際整體大小；
2) 而說到chunk unused size，就表示該malloc_chunk中刨除諸如prev_size, size, fd和bk這類輔助成員之後的實際可用的大小。因此，對free chunk而言，其實際可用大小總是比實際整體大小少16字節。
在內存分配和釋放過程中，fast bin是所有bin中操作速度最快的。下面詳細介紹fast bin的一些特性：
1) fast bin的個數——10個
2)每個fast bin都是一個單鏈表(只使用fd指針)。為什麼使用單鏈表呢？因為在fast bin中無論是添加還是移除fast chunk，都是對“鏈表尾”進行操作，而不會對某個中間的fast chunk進行操作。更具體點就是LIFO(後入先出)算法：添加操作(free內存)就是將新的fast chunk加入鏈表尾，刪除操作(malloc內存)就是將鏈表尾部的fast chunk刪除。需要注意的是，為了實現LIFO算法，fastbinsY數組中每個fastbin元素均指向了該鏈表的rear end（尾結點），而尾結點通過其fd指針指向前一個結點，依次類推，如圖2-1所示。
3) chunk size：10個fast bin中所包含的fast chunk size是按照步進8字節排列的，即第一個fast bin中所有fast chunk size均為16字節，第二個fast bin中為24字節，依次類推。在進行malloc初始化的時候，最大的fast chunk size被設置為80字節(chunk unused size為64字節)，因此默認情況下大小為16到80字節的chunk被分類到fast chunk。詳情如圖2-1所示。
4) 不會對free chunk進行合並操作。鑒於設計fast bin的初衷就是進行快速的小內存分配和釋放，因此系統將屬於fast bin的chunk的P(未使用標志位)總是設置為1，這樣即使當fast bin中有某個chunk同一個free chunk相鄰的時候，系統也不會進行自動合並操作，而是保留兩者。雖然這樣做可能會造成額外的碎片化問題，但瑕不掩瑜。
5) malloc(fast chunk)操作：即用戶通過malloc請求的大小屬於fast chunk的大小范圍(注意：用戶請求size加上16字節就是實際內存chunk size)。在初始化的時候fast bin支持的最大內存大小以及所有fast bin鏈表都是空的，所以當最開始使用malloc申請內存的時候，即使申請的內存大小屬於fast chunk的內存大小(即16到80字節)，它也不會交由fast bin來處理，而是向下傳遞交由small bin來處理，如果small bin也為空的話就交給unsorted bin處理：
/* Maximum size of memory handled in fastbins. */
static INTERNAL_SIZE_T global_max_fast;
/* offset 2 to use otherwise unindexable first 2 bins */
/*這裡SIZE_SZ就是sizeof(size_t)，在32位系統為4，64位為8，fastbin_index就是根據要malloc的size來快速計算該size應該屬於哪一個fast bin，即該fast bin的索引。因為fast bin中chunk是從16字節開始的，所有這裡以8字節為單位(32位系統為例)有減2*8 = 16的操作！*/
#define fastbin_index(sz) \
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE (80 * SIZE_SZ / 4)
#define NFASTBINS (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)
那麼fast bin 是在哪？怎麼進行初始化的呢？當我們第一次調用malloc(fast bin)的時候，系統執行_int_malloc函數，該函數首先會發現當前fast bin為空，就轉交給small bin處理，進而又發現small bin 也為空，就調用malloc_consolidate函數對malloc_state結構體進行初始化，malloc_consolidate函數主要完成以下幾個功能：
a. 首先判斷當前malloc_state結構體中的fast bin是否為空，如果為空就說明整個malloc_state都沒有完成初始化，需要對malloc_state進行初始化。
b. malloc_state的初始化操作由函數malloc_init_state(av)完成，該函數先初始化除fast bin之外的所有的bins(構建雙鏈表，詳情見後文small bins介紹)，再初始化fast bins。
然後當再次執行malloc(fast chunk)函數的時候，此時fast bin相關數據不為空了，就開始使用fast bin(見下面代碼中的※1部分)：
static void *
_int_malloc (mstate av, size_t bytes)
{
……
/*
If the size qualifies as a fastbin, first check corresponding bin.
This code is safe to execute even if av is not yet initialized, so we
can try it without checking, which saves some time on this fast path.
*/
//第一次執行malloc(fast chunk)時這裡判斷為false，因為此時get_max_fast ()為0
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
※1 idx = fastbin_index (nb);
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp = *fb;
do
{
victim = pp;
if (victim == NULL)
break;
}
※2 while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))!= victim);
if (victim != 0)
{
if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
{
errstr = "malloc(): memory corruption (fast)";
errout:
malloc_printerr (check_action, errstr, chunk2mem (victim));
return NULL;
}
check_remalloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
得到第一個來自於fast bin的chunk之後，系統就將該chunk從對應的fast bin中移除，並將其地址返回給用戶，見上面代碼※2處。
6) free(fast chunk)操作：這個操作很簡單，主要分為兩步：先通過chunksize函數根據傳入的地址指針獲取該指針對應的chunk的大小；然後根據這個chunk大小獲取該chunk所屬的fast bin，然後再將此chunk添加到該fast bin的鏈尾即可。整個操作都是在_int_free函數中完成。
在main arena中Fast bins(即數組fastbinsY)的整體操作示意圖如下圖所示：

圖2-1 fast bin示意圖

3 Unsorted bin

當釋放較小或較大的chunk的時候，如果系統沒有將它們添加到對應的bins中(為什麼，在什麼情況下會發生這種事情呢？詳情見後文)，系統就將這些chunk添加到unsorted bin中。為什麼要這麼做呢？這主要是為了讓“glibc malloc機制”能夠有第二次機會重新利用最近釋放的chunk(第一次機會就是fast bin機制)。利用unsorted bin，可以加快內存的分配和釋放操作，因為整個操作都不再需要花費額外的時間去查找合適的bin了。
Unsorted bin的特性如下：
1) unsorted bin的個數： 1個。unsorted bin是一個由free chunks組成的循環雙鏈表。
2) Chunk size: 在unsorted bin中，對chunk的大小並沒有限制，任何大小的chunk都可以歸屬到unsorted bin中。這就是前言說的特例了，不過特例並非僅僅這一個，後文會介紹。

4 Small bin

小於512字節的chunk稱之為small chunk，small bin就是用於管理small chunk的。就內存的分配和釋放速度而言，small bin比larger bin快，但比fast bin慢。
Small bin的特性如下：
1) small bin個數：62個。每個small bin也是一個由對應free chunk組成的循環雙鏈表。同時Small bin采用FIFO(先入先出)算法：內存釋放操作就將新釋放的chunk添加到鏈表的front end(前端)，分配操作就從鏈表的rear end(尾端)中獲取chunk。
2) chunk size: 同一個small bin中所有chunk大小是一?樣的，且第一個small bin中chunk大小為16字節，後續每個small bin中chunk的大小依次增加8字節，即最後一個small bin的chunk為16 + 62 * 8 = 512字節。
3) 合並操作：相鄰的free chunk需要進行合並操作，即合並成一個大的free chunk。具體操作見下文free(small chunk)介紹。
4) malloc(small chunk)操作：類似於fast bins，最初所有的small bin都是空的，因此在對這些small bin完成初始化之前，即使用戶請求的內存大小屬於small chunk也不會交由small bin進行處理，而是交由unsorted bin處理，如果unsorted bin也不能處理的話，glibc malloc就依次遍歷後續的所有bins，找出第一個滿足要求的bin，如果所有的bin都不滿足的話，就轉而使用top chunk，如果top chunk大小不夠，那麼就擴充top chunk，這樣就一定能滿足需求了(還記得上一篇文章中在Top Chunk中留下的問題麼？答案就在這裡)。注意遍歷後續bins以及之後的操作同樣被large bin所使用，因此，將這部分內容放到large bin的malloc操作中加以介紹。
那麼glibc malloc是如何初始化這些bins的呢？因為這些bin屬於malloc_state結構體，所以在初始化malloc_state的時候就會對這些bin進行初始化，代碼如下：
malloc_init_state (mstate av)
{
int i;
mbinptr bin;
/* Establish circular links for normal bins */
for (i = 1; i < NBINS; ++i)
{
bin = bin_at (av, i);
bin->fd = bin->bk = bin;
}
……
}
注意在malloc源碼中，將bins數組中的第一個成員索引值設置為了1，而不是我們常用的0(在bin_at宏中，自動將i進行了減1處理…)。從上面代碼可以看出在初始化的時候glibc malloc將所有bin的指針都指向了自己——這就代表這些bin都是空的。
過後，當再次調用malloc(small chunk)的時候，如果該chunk size對應的small bin不為空，就從該small bin鏈表中取得small chunk，否則就需要交給unsorted bin及之後的邏輯來處理了。
5) free(small chunk)：當釋放small chunk的時候，先檢查該chunk相鄰的chunk是否為free，如果是的話就進行合並操作：將這些chunks合並成新的chunk，然後將它們從small bin中移除，最後將新的chunk添加到unsorted bin中。

5 Large bin

大於512字節的chunk稱之為large chunk，large bin就是用於管理這些large chunk的。
Large bin的特性如下：
1) large bin的數量：63個。Large bin類似於small bin，只是需要注意兩點：一是同一個large bin中每個chunk的大小可以不一樣，但必須處於某個給定的范圍(特例2) ；二是large chunk可以添加、刪除在large bin的任何一個位置。
在這63個large bins中，前32個large bin依次以64字節步長為間隔，即第一個large bin中chunk size為512~575字節，第二個large bin中chunk size為576 ~ 639字節。緊隨其後的16個large bin依次以512字節步長為間隔；之後的8個bin以步長4096為間隔；再之後的4個bin以32768字節為間隔；之後的2個bin以262144字節為間隔；剩下的chunk就放在最後一個large bin中。
鑒於同一個large bin中每個chunk的大小不一定相同，因此為了加快內存分配和釋放的速度，就將同一個large bin中的所有chunk按照chunk size進行從大到小的排列：最大的chunk放在鏈表的front end，最小的chunk放在rear end。
2) 合並操作：類似於small bin。
3) malloc(large chunk)操作：
初始化完成之前的操作類似於small bin，這裡主要討論large bins初始化完成之後的操作。首先確定用戶請求的大小屬於哪一個large bin，然後判斷該large bin中最大的chunk的size是否大於用戶請求的size(只需要對比鏈表中front end的size即可)。如果大於，就從rear end開始遍歷該large bin，找到第一個size相等或接近的chunk，分配給用戶。如果該chunk大於用戶請求的size的話，就將該chunk拆分為兩個chunk：前者返回給用戶，且size等同於用戶請求的size；剩余的部分做為一個新的chunk添加到unsorted bin中。
如果該large bin中最大的chunk的size小於用戶請求的size的話，那麼就依次查看後續的large bin中是否有滿足需求的chunk，不過需要注意的是鑒於bin的個數較多(不同bin中的chunk極有可能在不同的內存頁中)，如果按照上一段中介紹的方法進行遍歷的話(即遍歷每個bin中的chunk)，就可能會發生多次內存頁中斷操作，進而嚴重影響檢索速度，所以glibc malloc設計了Binmap結構體來幫助提高bin-by-bin檢索的速度。Binmap記錄了各個bin中是否為空，通過bitmap可以避免檢索一些空的bin。如果通過binmap找到了下一個非空的large bin的話，就按照上一段中的方法分配chunk，否則就使用top chunk來分配合適的內存。
4) Free(large chunk)：類似於small chunk。
了解上面知識之後，再結合下圖5-1，就不難理解各類bins的處理邏輯了：

6 總結

至此glibc malloc中涉及到的所有顯示鏈表技術已經介紹完畢。鑒於篇幅和精力有限，本文沒能詳細介紹完所有的技術細節，但是我相信帶著這些知識點再去研究glibc malloc的話，定能起到事半功倍的效果。
另外，就我個人所了解到的基於堆溢出攻擊而言，掌握以上知識，已經足夠理解絕大部分堆溢出攻擊技術了。因此，後面的文章將會結合這些知識詳細介紹各個攻擊技術的實現原理。
老規矩：如有錯誤，歡迎斧正！

上期文章回顧

【Linux堆內存管理深入分析(上)】
作者：走位@阿裡聚安全，更多安全技術文章，請點擊阿裡聚安全博客