堆数据结构探究

学习堆的过程中，涉及到的数据结构比较复杂，这些数据结构能够理清楚，堆漏洞利用也就会得心应手。个人觉得还是扎扎实实把笔记做过去比较实在。

1.堆的最基本数据单元——chunk

chunk是堆的最小结构单元，chunk块在被使用时和未被使用时有两种不同的状态。

 

chunk块在未被使用时，previous size表示上一个空闲chunk块的大小（注意这里说的是上一个空闲chunk块的大小，如果上一个chunk块处于使用状态，这里的previous size域可以被复用），size of chunk表示该chunk块的大小。fd指针表示下一个空闲的chunk，bk指针指向上一个空闲的chunk，依靠这两个指针，可以把空闲的链表以双链表的形式放置在bins中。fd_nextchunk和bk_prechunk分别为了方便在large bins中快速地管理chunk块。在一个chunk块中，previous size，size of chunk，fd指针，bk指针是一定要有的，参考地址以Size_t大小对齐，所以32位下至少要分配16个字节来存放空闲chunk块，64位下至少要分配32个字节来存放空闲chunk块。

32位下，分配chunk块大小计算公式：

in use chunk=用户请求的的大小（数据域）+8 （previous chunk和size ofchunk）- 4（复用下个空闲chunk的previous），但是由于chunk块最小大小要是16个字节，所以当in use chunk小于16个字节的时候，也会分配16个字节的chunk。一个使用中的，没用被free的chunk如下所示：

 

接下来介绍一下size of chunk域的P标志位。P标志位表示前一个chunk是否空闲，如果前一个chunk空闲的话，P置位为0，如果前一个chunk不空闲的话，P位置位为1。ptmalloc分配的第一个chunk块，P标志位一定置位为1，以防指针应用到其他比较危险的内存地址处。

2.空闲堆块的管理模块——bins

bin的英文意思是垃圾桶的意思，在这里也很形象。bins存放的就是被释放的chunk块，如果每次free的chunk块都返还给操作系统，然后下次需要地时候再调用malloc函数进行分配，那这样做是非常消耗资源，非常低效的。所以ptmalloc就有了bins来管理被free的chunk块，下次再有需要malloc的时候，首先在bins中的chunk块中寻找有没有适合的堆块，这样一来，极大地降低了内存开销。

ptmalloc一共维护了128个bin，这些bins中，fastbins是以单链表的形式存放的，其他的bins都是以双链表形式存放的。fastbins有这样的机制，是为了更快速地管理小堆块，小于64字节的堆块在释放之后会率先存储到fastbins中。

 

如图所示，bins是一个数组，chunk块在bin上以链表的形式存放。

我们在释放堆块的时候，是添加到bin的头部，重新申请堆块的时候，会从bin的尾部申请堆块。use after free和double free的时候就要留意一下堆块重新利用时候的顺序。

bins重新分配堆块的时候，规则是：

fastbins——>smallbins——>合并fastbins chunk块添加到unsorted bin中，查找unsorted bins中是否有适合的chunk——>large bins——>top chunk

 

暂时总结这么多，内存管理的有些机制还没有理的很清楚，比如sbrk和mmap。后面有时间再补充，先记录下来，加深印象，这部分内容可以去看《glibc内存管理ptmalloc源码分析》以及malloc.c的源码进行学习。