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

由于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。

编译程序：

在 free(p3)处设置断点，运行程序，命中断点，然后单步执行free(p5)，执行完之后，可以看到chunk p3、chunk p5已经释放到unsortedbin.

使用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中，第一个循环结束。

由于用户申请的是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上进行分配。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课