linux动态内存管理（堆基础）
终于到了堆，这里是学pwn的分水岭，是新人杀手，每一届都会有很多人在这被劝退改方向，因为堆确实很玄学。
导入
我们之前学过，栈上存储的是一个函数的局部变量，bss存储全局变量。如果用户向程序输入一个几千字的留言怎么办，开一个二维大数组？首先长度会有限制如果开的
数组字节过长那么对于程序而言就会造成空间浪费，如果想要回收这段没用的空间要如何呢？在libc中，我们可以通过malloc(size)来给用户分配一段长度为size的
内存，通过free(ptr)来释放这段内存区域。这些数据，被统一的存放在了堆中，维护这些数据的运行机制在glibc中，称之为ptmalloc。
0x01 堆题与栈题的区别
- 1、堆的漏洞比栈有更多的形式和利用方式，堆漏洞所需要的条件比栈更少。
- 2、一般情况下栈溢出起码需要16个字节，也就是至少溢出到返回地址才能利用，但是堆的话只需要一个字节就可完成利用。栈的话基本都会关闭一两个保护机制，堆的话一般全开。
0x02 堆的结构
在内存中，堆是以一个个堆块构成的，这些堆块称之为chunk。在64位系统中，堆块的大小是8字节对齐的，我们申请一个15字节长度的堆块，实际到我们手中的用户可
控的数据区域大小为16字节。但是实际可以说是16字节对齐，假设申请了0x58个字节的chunk，实际到手的却是是0x60的大小
一个堆块除了用户数据区外，还有头部字段，头部字段的长度为16字节。同时在64位系统中，一个堆块最小长度为32字节（包括头部），也就是说，我们分配一个1字节
的堆块，他的实际长度是32字节（0x20）。（最小的chunk）
下面是chunk的图：
prev_size 和size字段分别代表前一个chunk的大小以及当前chunk的大小，大小都是8字节，两个一共16字节，称之为chunk的头部字段。后面的user data区域是
用户可以输入数据的地方。为了节省空间，将size的最低三个bit设置为三个标志位，从高到低分别为non_main_arena、is_mmap、prev_inuse 。
- non_main_arena用来记录当前chunk是否不属于主线程，1表示不属于，0表示属于。
- is_mmap表示当前chunk是否由mmap分配的，1表示属于，0表示不属于。
- prev_inuse用来表示前面紧邻的那个chunk是否正在使用，0表示前面的chunk已经被释放，1表示正在被用户使用
- prev_size 和size字段分别代表前一个chunk的大小以及当前chunk的大小，大小都是8字节
这里注意prevsize记录前面一个chunk的大小。这里注意，prevsize只有在前面的chunk被free掉的时候才生效，也就是说，只有在prev_inuse为0的时候，系统才把prev_size字段当作prevsize。如果chunk正在被使用，那么他会把下一个chunk的prevsize字段当作userdata。充分利用空间。例如也就是说，如果我们申请一个0x80长度大小的区域，系统实际给我们0x90大小（0x10头部），如果我们申请0x88大小的区域，系统同样也会给我们0x90大小的区域（算头部），剩下的8字节，使用nextchunk的prevsize区域。因为，只有当一个chunk被释放的时候，nextchunk的prevsize才真正代表前一个chunk的大小
0x03 特殊的堆块：topchunk
最开始时，程序的堆还未被使用，整个的堆区域属于一个很大的堆块叫做topchunk。当已经被使用的空间不够时，程序就会从topchunk中分割一块出来个程序使用。
0x04 堆块的管理
0x04(1) bin的类型
bins的类型图：
为了保证程序的快速运行，而且方便系统内存管理，所以ptmalloc将释放后的堆块根据其大小分成不同的bin。
- fastbin：大小范围：0x20 - 0x80
- smallbin:大小范围：0x90 - 0x400
- Large bin:大小范围：0x410 以上
- unsortedbin ：未被归类的bin，临时存储用，存放的堆块大小不一定多大
fastbin
- 1、管理fastbin free chunk，单链表结构，FILO（最后一个进入fastbin链表的，会被放在头部）。
- 2、总共有十个fastbin链表，每个链表中fastbin的size一样，0x10递增
- 3、大小属于fastbin的chunk被free掉时，不会改变nextchunk的previnuse位，也就是说不会被合并。
Unsortedbin
- 1、管理 unsorted chunk，只有一个双向链表
- 2、所有大小大于fastbin的chunk都会先被暂时放入unsortedbin中,链表中的chunk大小不一
Smallbin
- 1、管理small chunk，由62个双向链表组成，每个链表中的chunk大小一样，大小以0x10递增。（长得和unsortedbin差不多偷个懒就不画图了.）
largebin
- 1、管理large chunk，63个双向链表，FIFO先进先出。
- 2、同一个双线链表中chunk大小可以不一样，但是在一定范围内，bins大小从小到大排列。
0x04(2) chunk free后的内容
chunk被free之后的样子如图。
由于chunk被free了，所以按常理说用户不应该能够访问到这个chunk。于是乎在userdata区域存放一些用于管理内存的指针信息。
0x04(3) bin中的指针类型
如上图参考位置：
- fastbin：单链表结构，只有fd
- small &unsortedbin：双向链表结构，fd和bk都有
- largebin：双向链表，fdbk都有，同时还有fd nextsize 和 bk nextsize
0x05 堆块的合并操作
如果我们free掉一个堆块，（可能）会触发向前合并和向后合并。（两个相邻的都为0则合并，朝已经是0的方向合并）
向前合并：
- 检查当前chunk的previnuse位，如果为0，则根据当前chunk的prev size找到prev chunk的头，两个堆块合并
向后合并：
- 检查当前chunk的next chunk 的prev inuse位（因为一个堆块的状态由他后面chunk的previnuse位决定，所以确定nextchunk的状态需要检查next next chunk的previnuse位，怎么找？size就行），然后根据nextchunk的状态决定是否合并。
0x06 arena
arena是一块结构体，用于管理bins。主线程创建的arena称之为main_arena,其他的叫threadarena
如图：
malloc调用机制
在fastbin范围内：检查对应的bin链表中有没有chunk，
- 有，分配给用户，完成
在smallbin范围内：检查对应大小的bin链表中有没有chunk，
- 有，取出来给程序，完成。
如果不在smallbin范围内，或者smallbin里面也没有：unsortedbin中：有的话，从尾部取出第一个chunk，看看大小是否满足需求。
满足，切分后大小是否大于minsize？
- 大于，切分块，返回给用户，剩下的块放进unsortedbin
- 小于等于minsize，直接返回给用户，完成
- 不满足，把这个块放入small/largebin对应的链表中，继续遍历下一个块。
如果unsortedbin中所有的块也不能满足需求：
largebin范围：检查对应的bin链表中有没有符合的chunk。
- 有，找到满足需求最小的chunk，切分块返回，剩下的放进unsortedbin中。
largebin也不行？再次遍历small/large找best fit的chunk
- 还是没有，那就从topchunk中切割
topchunk也不够？
- mmap系统调用。
free调用机制：
free的chunk大小属于fastbin吗？
- 是，放进fastbin，完成。
是mmap分配的吗？
- 是，调用munmap回收，完成
前一个chunk空闲吗？
- 是，向前合并。
后一个chunk是free的吗？
- 是，向后合并。放进unsortedbin，完成。
后一个chunk是topchunk吗？
- 是，和topchunk合并，完成。
总结：
想要做出ctf的堆题，必须要对堆的管理机制了如指掌，需要大量刷题。
