large chunk分配過程調試 - 網安 - 專業的網絡安全產業、社區、知識平臺

最近研究ubuntu18.04.5下chunk分配過程，由于large chunk的分配最為復雜，對于深入學習掌握堆塊的分配和釋放算法要求比較高，理解起來具有一定的難度，具有一般的參考意義，故拿來進行分析。

一、代碼簡介

#include<stdio.h>
#include<stdlib.h>
int main(){
 
    int *p1 =malloc(8);
    int *p2 =malloc(8);
    fprintf(stderr,"malloc two fastbin chunk: p1=%p p2=%p\n",p1,p2);     
    void * p3 = malloc(0x500); //malloc large chunk from top chunk
    void * p4 = malloc(0x8); //void the freed large chunk consolidated with top chunk
    void * p5 = malloc(0x600); //malloc another large chunk
    void * p6 = malloc(0x8); //void the freed large chunk consolidated with top chunk
    free(p3);                  //free p3 into unsortedbin
    free(p5);                  //free p5 into unsortedbin
    void * p7 = malloc(0x550); //malloc large chunk, remove p3 p5 into largebin
    fprintf(stderr,"malloc large chunk:p7=%p\n",p7);
}

由于64位機上tcache bin存放的chunk的大小不超過1032字節，為了避免釋放后的chunk進入tcache,申請和釋放大于1032字節的large chunk,這樣在釋放后進入unsortedbin而不是tcache。

先malloc 1個大小為0x500的chunk p3 ，再malloc 1個大小為0x600的chunk p5，為防止這兩個large chunk釋放后互相合并、與top chunk合并，需要在malloc 第1個chunk和第2個chunk之后，各malloc 1個大小為0x8的chunk，分別為p4、p6。然后，先后釋放第1個chunk p3、第2個chunk p5（釋放到unsortedbin中），再malloc 1個大小為0x550的chunk。

二、申請large chunk過程調試

編譯程序：

在 free(p3)處設置斷點，運行程序，命中斷點，然后單步執行free(p5)，執行完之后，可以看到chunk p3、chunk p5已經釋放到unsortedbin。

（一）在各種bin中搜索合適大小的chunk時，將p3、p5從unsortedbin移到largebin中。

使用s命令進入 malloc.c進行單步調試。

執行到3530行處的_int_malloc（）函數，在3591行處設置斷點，運行命中斷點。

3591行代碼的作用是檢查fastbin（小于0x80字節）中是否有合適的chunk，顯然沒有，繼續執行到3649行。

3649行代碼的作用是檢查smallbin（小于0x400字節）中是否有合適的chunk，顯然沒有，繼續執行到3711行。

3711、3712行代碼的作用是計算large bin的idx，判斷fastbins中是否有釋放的chunk。如果有，調用malloc_consolidate()整理fastbins，并放入unsorted bin。malloc_consolidate()先向后合并空閑的chunk，再向前合并空閑的chunk，最后將合并的chunk放入unsorted bin。

接下來是判斷tcachebin中是否有合適的chunk,也沒有。程序執行到3739行處進入大的外層for循環，包含了_int_malloc()函數之后的所有過程。緊接著是內層的第一個while循環，它會遍歷unsorted bin中的每一個chunk，如果大小正好合適，就將其取出，否則就將其放入small bin 或者large bin。這是唯一的將chunk 放進smallbin或者largebin的過程。

搜索到unsortedbin中第1個chunk，即victim。

bck為victim后面的chunk，即unsortedbin中第2個chunk。

進行victim大小合法性檢查（大于2 * SIZE_SZ，且小于 av->system_mem）后，計算victim的大小。

程序執行到3759行，當請求的chunk屬于smallbin、unsortedbin只有一個chunk為lastremainder并且滿足拆分條件時，就將其拆分。這里不滿足條件。

程序執行到3788、3789行，將victim從unsortedbin中取出。

如果victim的大小正好等于請求chunk的大小，則將victim返回給用戶。這里不滿足條件。

如果chunk大小不合適，就將其插入對應的bin中。插入過程也就是雙鏈表插入節點的過程。其中插入largebin的操作最為復雜，因為涉及到修改fd_nextsize和bk_nextsize指針。

這里victim大小為0x500，屬于large chunk，下面的調試顯示了將unsortedbin中的0x555555756290處的victim插入largebin的過程。首先根據victim大小計算在largebin中的index，然后得到對應largebin的頭結點，并搜索到頭結點指向的chunk，再判斷largebin是否為空。

此時largenbin為空，修改victim的fd_nextsize和bk_nextsize指向victim自身。

最后修改bk和fd指針，將victim摻入到largebin中。

然后再次執行3742行處的while循環，按照以上過程，將unsortedbin中0x5555557567c0處的大小為0x600字節的chunk放入另外1個largebin。

程序執行到這里，p3、p5兩個chunk分別移到對應大小的largebin中，第一個循環結束。

（二）遍歷largebin，找到合適大小的chunk，進行切分操作，將用戶申請的chunk返回給用戶，剩余部分移到unsortedbin中。

由于用戶申請的是large chunk，程序進行搜索largebin的過程，為加快搜索速度，反向遍歷nextsize鏈表，找到第一個不小于nb的chunk。

根據前面計算的largebin idx，計算出largebin的頭結點0x7ffff7dce0e0 ，這個頭結點指向大小為0x500的chunk(0x555555756290)，顯然這個大小小于用戶申請的大小，3919至3921行的判斷條件不滿足。

程序執行3987行，對idx進行加1操作，并計算出下一個largebin的頭結點。

接下來，進入內層第二個for循環。根據binmap來搜索bin，因為申請的chunk大小所對應bin沒有找到合適的chunk，所以就從下一個bin中搜索（large bin中的chunk大小在一定范圍之內，各個bin之間按照一定的等差數列增加大小）。

根據idx取得對應的bin，地址為0x7ffff7dce0f0，還沒有到達0x5555557567c0處的chunk p5（大小為0x600）所在的largebin（ 0x7ffff7dce110 ）。

在內層第二個循環內部，尋找第一個不為空的block，再根據bit位找到合適的bin，此時bit=64，map=272。

找到next_bin，地址為0x7ffff7dce100 ，仍沒有到達0x7ffff7dce110 處的largebin。繼續while循環，此時bit=128。

繼續尋找next_bin，地址為0x7ffff7dce110 ，即搜索到chunk p5（大小為0x600）所在的largebin，此時bit=256 ，已經不滿足(bit & map) == 0的條件，跳出while循環。

取出largebin（ 0x7ffff7dce110 ）中的chunk p5（大小為0x600）為victim。

4021行處的代碼判斷搜索到的largebin是否為空，這里顯然不為空，條件不成立。

程序執行到4030行代碼處，計算victim的大小。

驗證完victim的大小大于請求chunk的大小后，將victim的大小減去請求chunk的大小，并進行unlink操作，將victim從largebin中解鏈。

如果victim中剩余部分的大小小于MINSIZE，則將整個victim返回給用戶，顯然不成立。可以看到，unlink操作后，0x600字節大小的largebin中已經沒有victim。

對victim進行切分操作，將0x550大小的chunk返回給用戶，并將剩余部分remainder插入unsortedbin。內層第二個循環到此結束。