pwn学习-堆入门

什么是堆

堆是虚拟地址空间的一块连续的线性区域提供动态分配的内存，允许程序申请大小未知的内存在用户与操作系统之间，作为动态内存管理的中间人响应用户的申请内存请求，向操作系统申请内存然后将其返回给用户程序管理用户所释放的内存，适时归还给操作系统

堆管理器

各种堆管理器

dlmalloc – General purpose allocator
ptmalloc2 – glibc
jemalloc – FreeBSD and Firefox
tcmalloc – Google libumem – Solaris

堆管理器并非由操作系统实现，而是由libc.so.6链接库实现。封装了一些系统调用，为用户提供方便的动态内存分配接口的同时，力求高效地管理由系统调用申请来的内存。

arena

堆的申请

在我们常见的操作中，堆是用malloc函数申请使用的。

堆的申请我们一般用malloc函数进行申请使用。

堆chunk

malloc chunk我们称运行过程中被malloc分配的内存为一个chunk，这块内存在ptmalloc中用malloc_chunk结构体表示，当程序申请的chunk被free时，会被加入相应的空闲管理列表中。(0x21-0x10剩下的是topchunk)

用户申请内存的单位，也是堆管理器管理内存的基本单位 malloc()返回的指针指向一个chunk的数据区域

struct malloc_chunk {
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

Chunk是有他的神奇之处的，chunk虽然由一个统一的结构体声明，但是在被使用时和空闲时却又有两种不同的状态

prev_size:如果前一个chunk 是空闲的，该域表示前一个 chunk 的大小，如果前一个 chunk 不空闲,该域无意义
size:当前 chunk 的大小，并且记录了当前chunk和前一个 chunk 的一些属性,二进制后三位。
FD，记录了下一个被free的chunk(used onlyiffree)
BK，记录了上一个被free的chunk(used only iffree)5:fd_nextsize和bk_nextsize,largebin使用，记录了上/下一个被free chunk的size;

Ptmalloc使用chunk 实现内存管理，对chunk的管理基于独特的边界标记法;重要的是对地址的对齐。

在不同的平台下，每个chunk的最小大小，地址对齐方式是不同的，ptmalloc依赖平台定义的 size_t长度，对于 32 位平台，size.t长度为 4字节，对 64 位平台，size_t长度可能为4字节，也可能为8字节

在LinuxX86 64上size t为8字节;在64位平台上，一个使用中的chunk 的大小的计算公式应该是:in_use_size=(用户请求大小+16-8)align to 16B，这里加 16 是因为需要存储prev_size 和 size，但又因为向下一个 chunk”借”了8B，所以要减去8，每分配一个chunk 的 overhead 为8B,即 SIZE SZ的大小;所以最小的chunk也应该是0x20，这样size字段的低三位永远不会被使用低三位就被用来当作flag位。

用户请求大小：程序实际需要的内存大小。

chunk 的大小必须是 8 的倍数，这是因为 x86 平台要求地址对齐，64位则是16字节对齐

原本是用来存用户数据的存储了四个指针，指针 fd 指向了后一个空闲的 chunk，而 bk 指向前一个空闲的 chunk

这些 chunk 可以不相邻

ptmalloc 通过这种方法，将多个大小相近的 chunk 连成一个双向链表。又形成了一个新的数据结构 bin（后面再说）。

而 fd_nextsize 和 bk_nextsize，这两个指针用于加快在 large bin 中查找最近匹配的空闲 chunk。不同的 chunk 链表又是通过 bins 或者 fastbins 来组织的

fd_nextsize ：在large bin中指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针
bk_nextsize：在large bin中指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针

为了使 chunk 空间足够小，不浪费，ptmalloc 使用了空间复用。之前我们说过：一共有两个位置记录了一个 chunk 的大小

当一个 chunk 在使用的时候，它的下一个 chunk 的 previous_size 记录了这个 chunk 的大小，由于这个记录没有什么用。所以当前 chunk 可以使用下一个 chunk 的 previous_size 空间，由于是连续的所以用起来也十分方便

堆的大小对齐 堆的大小必须是2*SIZE SZ的整数倍

如果申请的内存大小不是2*SIZE_ SZ的整数倍，会被转成满足大小的最小的2*SIZE_ SZ的倍数; 32位系统中，SIZE_ SZ=4, 64位系统中SIZE_ SE=8;也就是32位系统堆大小为8的倍数，64位系统堆大小为16的位数，8对应的2进制为1000，所以不管size如何变换对应的低3位固定为0; 为了不浪费这3个比特位，它们从高到低分别被用来示:

NON_ MIAN_ ARENA,记录当前chunk是否不属于主线程，1表示不属于，0表示属于。
IS_MAPPED，记录当前chunk是否是由mmap分配的。
PREV_INUSE，记录前一个chunk块是否被分配(空闲)。一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。

presize和size被称为chunk头

prev_size + size + FD + BK = 8+8+8+8=32

fd,bd：

如果前一个邻接 chunk块空闲，那么当前 chunk块结构体内的 prev_size 字段记录的是前一个邻接 chunk块的大小。这就是由当前chunk指针获得前一个空闲chunk地址的依据。宏 prev_chunk(p)就是依赖这个假设实现的。
如果前一个邻接 chunk 在使用中，则当前 chunk的 prev_size 的空间被前一个 chunk借用中，其中的值是前一个chunk的内存内容，对当前chunk 没有任何意义。

堆的释放:堆的释放一般都用free函数实现;但是free后chunk去哪里了呢?在bins中。

堆释放后的管理：堆释放后，会被添加到相应的bins中进行管理:这里涉及道的结构体是mallocstate

分箱式管理：对于空闲的 chunk，ptmalloc 采用分箱式内存管理方式，根据空闲chunk的大小和处于的状态将其放在四个不同的bin中，这四个空闲chunk的容器包括 fast bins, unsorted bin, smallbins 和large bins.

bin

管理 arena 中空闲 chunk 的结构，以数组的形式存在，数组元素为相应大小的 chunk 链表的链表头，存在于 arena 的 malloc state 中
unsorted bin,fast bins,small bins,large bins,(tcache glibc 2.27)

Fast bin

Fast bins 主要是用于提高小内存的分配效率，默认情况下对于SIZE SZ为4B 的平台，小于 64B 的 chunk 分配请求,对于SIZE SZ为8B 的平台，小于128B 的chunk分配请求，首先会查找 fast bins 中是否有所需大小的chunk 存在(精确匹配)，如果存在，就直接返回。

Fast bins 可以看着是 small bins 的一小部分 cache，默认情况下，fast bins只 cache了small bins 的前7个大小的空闲 chunk，也就是说，对于SIZE_SZ为4B 的平台，fastbins有7个chunk空闲链表(bin)，每个bin的chunk大小依次为16B，24B，32B，40B，48B，56B，64B;对于SIZESZ为8B的平台，fastbins有7个chunk空闲链表(bin)，每个bin的chunk大小依次为32B，48B，64B,80B， 96B，112B，128B

改成0x30

在unsorted bin里了

Fast Bin分类的chunk的大小为32~128(0x80) 字节，如果chunk在被释放时发现其大小满足这个要求，则将该chunk放入Fast Bin,且在被释放后不修改下一个chunk的PREV INUSE标志位。Fast Bin 在堆管理器中以单链表的形式存储，不同大小的Fast Bin存储在对应大小的单链表结构中，其单链表的存取机制是LIFO (后进先出)。一个最新被加入Fast Bin的chunk,其fd指针指向上一次加入Fast Bin的chunk。

Unsorted bin

Unsorted bin 可以看作是 small bins 和 large bins 的cache，只有一个unsorted bin，以双向链表管理空闲chunk，空闲chunk不排序，所有的chunk 在回收时都要先放到 unsorted bin中，分配时，如果在unsorted bin中没有合适的 chunk，就会把 unsorted bin 中的所有 chunk分别加入到所属的 bin 中，然后再在 bin 中分配合适的chunk。Bins 数组中的元素 bin[1]用于存储 unsorted bin的 chunk 链表头(缓冲作用)

管理刚刚释放还未分类的 chunk可以视为空闲 chunk 回归其所属 bin 之前的缓冲区

bin[1]

Unsorted Bin相当于Ptmalloc2堆管理器的垃圾桶。chunk被释放后，会先加入Unsorted Bin中，等待下次分配使用。在堆管理器的Unsroted Bin不为空时，用户申请非Fast Bin大小的内存会先从Unsorted Bin中查找，如果找到符合该申请大小要求的chunk (等于或者大于) ,则直接分配或者分割该chunk。

small bins

ptmalloc使用small bins管理空闲小chunk，每个small bin中的chunk的大小与bin的index有如下关系:Chunk size=2SlZE SZindex在SIZE SZ为4B 的平台上，small bins 中的 chunk大小是以 8B为公差的等差数列，最大的chunk大小为504B最小的chunk大小为16B，所以实际共62个bin。分别为16B、24B、32B，””，504B。在SIZE SZ为8B 的平台上，small bins 中的 chunk 大小是以 16B 为公差的等差数列，最大的 chunk 大小为 1008B，最小的 chunk 大小为 32B所以实际共62个bin。分别为32B、48B、64B，力力

bins[2] ~ bins[63] 62 个循环双向链表 FIFO 管理 16、24、32、40、 …… 、504 Bytes 的 free chunks（32位下）每个链表中存储的 chunk 大小都一致

Small Bin保存大小为32 ~ 1024 (0x400) 字节的chunk, 每个放入其中的chunk为双链表结构，不同大小的chunk存储在对应的链接中。由于是双链表结构，所以其速度比Fast Bin慢- -些。链表的存取方式为FIFO (先进先出)。

large bins

bins[64] ~ bins[126] 63 个循环双向链表 FIFO 管理大于 504 Bytes 的 free chunks（32位下）

大于1024 (0x400) 字节的的chunk使用Large Bin进行管理。Large Bin的结构相对于其他Bin是最复杂的，速度也是最慢的，相同大小的L arge Bin使用fd和bk指针连接，不同大小的L arge Bin通过fd_nextsize和bk_nextsize按大小排序连接。

malloc

它根据用户申请的内存块大小以及相应大小 chunk 通常使用的频度（fastbin chunk, small chunk, large chunk），依次实现了不同的分配方法。它由小到大依次检查不同的 bin 中是否有相应的空闲块可以满足用户请求的内存。当所有的空闲 chunk 都无法满足时，它会考虑 top chunk。当 top chunk 也无法满足时，堆分配器才会进行内存块申请。