首页
论坛
课程
招聘
[原创]large chunk分配过程调试
2021-9-3 21:22 9241

[原创]large chunk分配过程调试

2021-9-3 21:22
9241

最近研究ubuntu18.04.5下chunk分配过程,由于large chunk的分配最为复杂,对于深入学习掌握堆块的分配和释放算法要求比较高,理解起来具有一定的难度,具有一般的参考意义,故拿来进行分析。

一、代码简介

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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。内层第二个循环到此结束。
图片描述
图片描述
图片描述
图片描述
图片描述

 

如果上面的操作还不能满足要求,就只能从top chunk上进行分配。


【看雪培训】《Adroid高级研修班》2022年夏季班招生中!

收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回