CTF pwn的环境主要是linux，一般用到的是堆内存管理机制叫做ptmalloc。
因为很久没有做过相关赛题了，已经忘了很多，于是准备把ptmalloc再整理一下。
Linux进程地址空间
32位
这种布局是 Linux 内核 2.6.7 以前的默认进程内存布局形式，mmap 区域与栈区域相对增 长，这意味着堆只有 1GB 的虚拟地址空间可以使用，继续增长就会进入 mmap 映射区域。
0x4000,0000—->2^30—–>1G
栈至顶向下扩展，并且栈是有界的。堆至底向上扩展，mmap 映射区域至顶向下扩展，mmap映射区域和堆相对扩展，直至耗尽虚拟地址空间中的剩余区域，这种结构便于c运行时库使用 mmap 映射区域和堆进行内存分配。上图的布局形式是在内核 2.6.7 以后才引入的，这是 32 位模式下进程的默认内存布局形式。
64位
内存分配背后的系统调用
无论是 malloc 函数还是 free 函数，我们动态申请和释放内存时，都经常会使用，但是它们并不是真正与系统交互的函数。这些函数背后的系统调用主要是 (s)brk 函数以及 mmap, munmap 函数。
如下图所示，我们主要考虑对堆进行申请内存块的操作。
(s)brk
对于堆的操作，操作系统提供了 brk 函数，glibc 库提供了 sbrk 函数，我们可以通过增加 brk (program break location, the program break is the address of the first location beyond the current end of the data region, https://en.wikipedia.org/wiki/Sbrk)的大小来向操作系统申请内存。
初始时，堆的起始地址 start_brk 以及堆的当前末尾 brk 指向同一地址。根据是否开启ASLR，两者的具体位置会有所不同
- 不开启 ASLR 保护时，start_brk 以及 brk 会指向 data/bss 段的结尾。
- 开启 ASLR 保护时，start_brk 以及 brk 也会指向同一位置，只是这个位置是在 data/bss 段结尾后的随机偏移处。
mmap
malloc 会使用 mmap来创建独立的匿名映射段。匿名映射的目的主要是可以申请以0填充的内存，并且这块内存仅被调用进程所使用。
多线程支持
在原来的 dlmalloc 实现中，当两个线程同时调用malloc时，只有一个线程可以进入临界区，因为freelist数据结构是在所有可用线程之间共享的。因此，内存分配在多线程应用程序中需要时间，导致性能下降。
而在ptmalloc2中，当两个线程同时调用malloc时，会立即分配内存，因为每个线程维护一个单独的堆段，因此维护这些堆的freelist数据结构也是分开的。
这种为每个线程维护单独的堆和freelist数据结构的行为称为per thread arena。
在新的实现中，所有的线程共享多个堆。
这里给出一个例子。
1 | /* Per thread arena example. */ |
第一次申请之前， 没有任何任何堆段。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
第一次申请后， 从下面的输出可以看出，堆段被建立了，并且它就紧邻着数据段，这说明malloc的背后是用brk函数来实现的。同时，需要注意的是，我们虽然只是申请了1000个字节，但是我们却得到了0x0806c000-0x0804b000=0x21000个字节的堆。这说明虽然程序可能只是向操作系统申请很小的内存，但是为了方便，操作系统会把很大的内存分配给程序。这样的话，就避免了多次内核态与用户态的切换，提高了程序的效率。我们称这一块连续的内存区域为 arena。此外，我们称由主线程申请的内存为 main_arena。 后续的申请的内存会一直从这个 arena 中获取，直到空间不足。当 arena 空间不足时，它可以通过增加brk的方式来增加堆的空间。类似地，arena 也可以通过减小 brk 来缩小自己的空间。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
在主线程释放内存后，我们从下面的输出可以看出，其对应的 arena 并没有进行回收，而是交由glibc来进行管理。当后面程序再次申请内存时，在 glibc 中管理的内存充足的情况下，glibc 就会根据堆分配的算法来给程序分配相应的内存。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
在第一个线程malloc之前，我们可以看到并没有出现与线程1相关的堆，但是出现了与线程1相关的栈。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
第一个线程malloc后， 我们可以从下面输出看出线程1的堆段被建立了。而且它所在的位置为内存映射段区域，同样大小也是132KB(b7500000-b7521000)。因此这表明该线程申请的堆时，背后对应的函数为mmap函数。同时，我们可以看出实际真的分配给程序的内存为1M(b7500000-b7600000)。而且，只有132KB的部分具有可读可写权限，这一块连续的区域成为thread arena。
注意：
当用户请求的内存大于128KB时，并且没有任何arena有足够的空间时，那么系统就会执行mmap函数来分配相应的内存空间。这与这个请求来自于主线程还是从线程无关。
ptmalloc在开始时，若请求的空间小于 mmap 分配阈值(mmap threshold，默认值为 128KB)时，主分配区会调用 sbrk()增加一块大小为 (128 KB + chunk_size) align 4KB 的空间作为 heap。非主分配区会调用 mmap 映射一块大小为 HEAP_MAX_SIZ(E 32位系统上默认为1MB，64位系统上默认为64MB)的空间作为sub-heap。
当用户请求内存分配时，首先会在这个区域内找一块合适的chunk给用户。当用户释放了heap 中的chunk时，ptmalloc又会使用fast bins 和 bins 来组织空闲 chunk。以备用户的下一次分配。
若需要分配的 chunk 大小小于 mmap 分配阈值，而 heap 空间又不够，则此时主分配区会通过 sbrk()调用来增加 heap 大小，非主分配区会调用mmap映射一块新的sub-heap，也就是增加top chunk的大小，每次heap增加的值都会对齐到4KB。
当用户的请求超过mmap 分配阈值，并且主分配区使用sbrk()分配失败的时候，或是非主分配区在 top chunk 中不能分配到需要的内存时，ptmalloc 会尝试使用 mmap()直接映射一 块内存到进程内存空间。使用 mmap()直接映射的 chunk 在释放时直接解除映射，而不再属于进程的内存空间。任何对该内存的访问都会产生段错误。而在 heap 中或是 sub-heap 中分 配的空间则可能会留在进程内存空间内，还可以再次引用(当然是很危险的)。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
在第一个线程释放内存后， 我们可以从下面的输出看到，这样释放内存同样不会把内存重新给系统。
1 | sploitfun@sploitfun-VirtualBox:~/ptmalloc.ppt/mthread$ ./mthread |
Arena
在我们之前介绍的例子中，无论是主线程还是新创建的线程，在第一次申请内存时，都会有独立的arena。那么会不会每个线程都有独立的arena呢？下面我们就具体介绍。
arena 数量
对于不同系统，arena数量的约束如下
1 | For 32 bit systems: |
显然，不是每一个线程都会有对应的 arena。至于为什么64位系统，要那么设置，我也没有想明白。此外，因为每个系统的核数是有限的，当线程数大于核数的二倍（超线程技术）时，就必然有线程处于等待状态，所以没有必要为每个线程分配一个arena。
区别
与 thread 不同的是，main_arena 并不在申请的 heap 中，而是一个全局变量，在 libc.so 的数据段。
heap_info
程序刚开始执行时，每个线程是没有 heap 区域的。当其申请内存时，就需要一个结构来记录对应的信息，而heap_info 的作用就是这个。而且当该heap的资源被使用完后，就必须得再次申请内存了。此外，一般申请的heap 是不连续的，因此需要记录不同heap之间的链接结构。
该数据结构是专门为从 Memory Mapping Segment 处申请的内存准备的，即为非主线程准备的。
主线程可以通过 sbrk() 函数扩展 program break location 获得（直到触及Memory Mapping Segment），只有一个heap，没有 heap_info 数据结构。
malloc_state
该结构用于管理堆，记录每个 arena 当前申请的内存的具体状态，比如说是否有空闲chunk，有什么大小的空闲chunk 等等。无论是 thread arena 还是 main arena，它们都只有一个 malloc state 结构。由于 thread 的 arena 可能有多个，malloc state结构会在最新申请的arena中。
注意，main arena 的 malloc_state 并不是 heap segment 的一部分，而是一个全局变量，存储在 libc.so 的数据段。
chunk
以下结构体代表在内存中的一块特定堆块(chunk)，有些结构体成员对于已分配和未分配的堆块有着不同的意义。
1 | struct malloc_chunk { |
Allocated chunk
一个使用中的chunk(使用中，就是指还没有被free掉)在内存中的样子如图所示。
在图中，chunk 指针指向一个 chunk 的开始，一个 chunk 中包含了用户请求的内存区域和相关的控制信息。
图中的 mem 指针才是真正返回给用户的内存指针。
chunk 的第二个域的最低一位为 P，它表示前一个块是否在使用中，P 为 0 则表示前一个 chunk 为空闲（并非指链表中的前一个堆块，而是连续内存中的前一块内存），这时 chunk 的第一个域 prev_size 才有效，prev_size 表示前一个 chunk 的 size，程序可以使用这个值来找到前一个 chunk 的开始地址。
当 P 为 1 时，表示前一个 chunk 正在使用中，prev_size无效，程序也就不可以得到前一个 chunk 的大小。不能对前一个 chunk 进行任何操作。ptmalloc 分配的第一个块总是将 P 设为 1，以防止程序引用到不存在的区域。
Chunk的第二个域的倒数第二个位为M，他表示当前chunk是从哪个内存区域获得的虚拟内存。M 为 1 表示该 chunk 是从 mmap 映射区域分配的，否则是从 heap 区域分配的。
Chunk 的第二个域倒数第三个位为 A，表示该 chunk 属于主分配区或者非主分配区，如果属于非主分配区，将该位置为 1，否则置为 0。
Free chunk
空闲 chunk 在内存中的结构如图所示。
当 chunk 空闲时，其 M 状态不存在，只有 AP 状态。
原本是用户数据区的地方存储了四个指针，指针 fd 指向后一个空闲的 chunk，而 bk 指向前一个空闲的 chunk，ptmalloc 通过这两个指针将大小相近的 chunk 连成一个双向链表。
对于 large bin 中的空闲 chunk，还有两个指针，fd_nextsize 和 bk_nextsize，这两个指针用于加快在 large bin 中查找最近匹配的空闲 chunk。
不同的 chunk 链表又是通过 bins 或者 fastbins 来组织的
chunk 中的空间复用
为了使得 chunk 所占用的空间最小，ptmalloc 使用了空间复用，一个 chunk 或者正在被使用，或者已经被 free 掉，所以 chunk 的中的一些域可以在使用状态和空闲状态表示不同的意义，来达到空间复用的效果。
以 32 位系统为例，空闲时，一个 chunk 中至少需要 4 个 size_t(4B)大小的空间，用来存储 prev_size，size，fd 和 bk (见上图)，也就是 16B， chunk 的大小要对齐到 8B。
当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域肯定是无效的。所以实际上，这个空间也可以被当前 chunk 使用。
这听起来有点不可思议， 但确实是合理空间复用的例子。故而实际上，一个使用中的 chunk 的大小的计算公式应该是: in_use_size = (用户请求大小+ 8 - 4 ) align to 8B，这里加 8 是因为需要存储 prev_size 和 size， 但又因为向下一个 chunk“借”了 4B，所以要减去 4。
最后，因为空闲的 chunk 和使用中的 chunk 使用的是同一块空间。所以肯定要取其中最大者作为实际的分配空间。即最终的分配空间 chunk_size = max(in_use_size, 16)。这就是当用户请求内存分配时，ptmalloc 实际需要分配的内存大小。
bins
bin是一个由空闲(未分配)堆块组成的(双向或单向)链表。Bins根据所包含的区块大小进行区分：
- Fast bin
- Unsorted bin
- Small bin
- Large bin
用户 free 掉的内存并不是都会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。
当用户进行下一次分配请求时，ptmalloc 会首先试图在空闲的 chunk 中挑选一块给用户，这样就避免了频繁的系统调用，降低了内存分配的开销。
ptmalloc 将相似大小的 chunk 用双向链表链接起来，这样的一个链表被称为一个 bin。
Ptmalloc 一共 维护了 128 个 bin（实际上bin[0]和bin[127]都不存在，bin[1]是unsorted bins)，并使用一个数组来存储这些 bin(如下图所示)。
数组中的 bin 依次介绍如下
- 第一个为 unsorted bin，字如其面，这里面的 chunk 没有进行排序，存储的 chunk 比较杂。
- 索引从 2 到 63 的 bin 称为 small bin，同一个 small bin 链表中的 chunk 的大小相同。两个相邻索引的 small bin 链表中的 chunk 大小相差的字节数为2个机器字长，即32位相差8字节，64位相差16字节。
- small bins 后面的 bin 被称作 large bins。large bins 中的每一个 bin 都包含一定范围内的 chunk，其中的chunk 按 fd 指针的顺序从大到小排列。相同大小的chunk同样按照最近使用顺序排列。
当空闲的 chunk 被链接到 bin 中的时候，ptmalloc 会把表示该 chunk 是否处于使用中的 标志 P 设为 0(注意，这个标志实际上处在下一个 chunk 中)，同时 ptmalloc 还会检查它前后的 chunk 是否也是空闲的，如果是的话，ptmalloc 会首先把它们合并为一个大的 chunk， 然后将合并后的 chunk 放到 unstored bin中。
此外，上述这些bin的排布都会遵循一个原则：任意两个物理相邻的空闲chunk不能在一起。
需要注意的是，并不是所有的 chunk 被释放后就立即被放到 bin 中。ptmalloc 为了提高分配的速度，会把一些小的 chunk 先放到 fast bins 的容器内。而且，fastbin 容器中的 chunk 的使用标记总是被置位的，所以不满足上面的原则。
- Fast bins 是小内存块的高速缓存，当一些大小小于等于64 字节的 chunk 被回收时，首先会放入 fast bins 中，在分配小内存时，首先会查看 fast bins 中是否有合适的内存块，如果存在，则直接返回 fast bins 中的内存块，以加快分配速度。
- Usorted bin 只有一个，回收的chunk块必须先放到unsorted bin中，分配内存时会查看unsorted bin中是否有 合适的chunk，如果找到满足条件的chunk，则直接返回给用户，否则将unsorted bin的所有chunk 放入 small bins 或是 large bins 中。
- Small bins 用于存储大小小于512B或1024B固定大小的chunk，共 62 个 bin，最小的 chunk 大小为 16 字节或 32 字节，每个 bin 的大小相差 8 字节或是 16 字节，当分配小内存块时，采用精确匹配的方式从 small bins 中查找合适的 chunk。
- Large bins 用于存储大于等于 512B 或 1024B 的空闲 chunk，这些 chunk 使用双向链表的形式按大小顺序排序，分配内存时按最近匹配方式从 large bins 中分配 chunk。
Small bin
ptmalloc使用small bins管理空闲小chunk，每个small bin中的chunk的大小与bin的index 有如下关系:
Chunk_size=2 * SIZE_SZ * index
在 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，…… 1008B。
ptmalloc 维护了 62 个双向环形链表(每个链表都具有链表头节点，加头节点的最大作用就是便于对链表内节点的统一处理，即简化编程)，每一个链表内的各空闲 chunk 的大小 一致，因此当应用程序需要分配某个字节大小的内存空间时直接在对应的链表内取就可以了，这样既可以很好的满足应用程序的内存空间申请请求而又不会出现太多的内存碎片。我们可以用如下图来表示在 SIZE_SZ 为 4B 的平台上 ptmalloc 对 512B 字节以下的空闲 chunk 组织方式(所谓的分箱机制)。
small bins 中每个 bin 对应的链表采用 FIFO 的规则，所以同一个链表中先被释放的 chunk 会先被分配出去。
Large bins
在 SIZE_SZ 为 4B 的平台上，大于等于 512B 的空闲 chunk，或者，在 SIZE_SZ 为 8B 的平 台上，大小大于等于 1024B 的空闲 chunk，由 sorted bins 管理。Large bins 一共包括 63 个 bin， 每个 bin 中的 chunk 大小不是一个固定公差的等差数列，而是分成 6 组 bin，每组 bin 是一个 固定公差的等差数列，每组的 bin 数量依次为 32、16、8、4、2、1，公差依次为 64B、512B、 4096B、32768B、262144B 等。
以 SIZE_SZ 为 4B 的平台为例，第一个 large bin 的起始 chunk 大小为 512B，共 32 个 bin， 公差为 64B，等差数列满足如下关系:
Chunk_size=512 + 64 * index
第二个 large bin 的起始 chunk 大小为第一组 bin 的结束 chunk 大小，满足如下关系:
1 | Chunk_size=512 + 64 * 32 + 512 * index |
同理，我们可计算出每个 bin 的起始 chunk 大小和结束 chunk 大小。
Unsorted bins
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 链表头。
此外，Unsorted Bin 在使用的过程中，采用的遍历顺序是 FIFO 。
Fast bins
Fast bins主要是用于高小内存的分配效率，采用LIFO，默认情况下，对于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 的平台，fast bins 有 7 个 chunk 空闲链表(bin)，每个 bin 的 chunk 大小依次为 16B，24B，32B，40B，48B，56B，64B;对 于SIZE_SZ为8B的平台，fast bins有7个chunk空闲链表(bin)，每个bin的chunk大小依 次为 32B，48B，64B，80B，96B，112B，128B。
默认情况下（32位系统为例）， fastbin 中默认支持最大的 chunk 的数据空间大小为 64 字节。但是其可以支持的chunk的数据空间最大为80字节。除此之外， fastbin 最多可以支持的 bin 的个数为 10 个，从数据空间为8字节开始一直到80字节
需要特别注意的是，fastbin 范围的 chunk 的 inuse 始终被置为 1。因此它们不会和其它被释放的chunk合并。
top chunk
程序第一次进行 malloc 的时候，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。其实，所谓的top chunk 就是处于当前堆的物理地址最高的 chunk。这个 chunk 不属于任何一个 bin，它的作用在于当所有的bin都无法满足用户请求的大小时，如果其大小不小于指定的大小，就进行分配，并将剩下的部分作为新的top chunk。否则，就对heap进行扩展后再进行分配。在main arena中通过sbrk扩展heap，而在thread arena中通过mmap分配新的heap。
需要注意的是，top chunk 的 prev_inuse 比特位始终为1，否则其前面的chunk就会被合并到top chunk中。
初始情况下，我们可以将 unsorted chunk 作为 top chunk。
mmaped chunk
当需要分配的 chunk 足够大，而且 fast bins 和 bins 都不能满足要求，甚至 top chunk 本身也不能满足分配需求时，ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空间。这样分配的 chunk 在被 free 时将直接解除映射，于是就将内存归还给了操作系统，再次对这样的内存区的引用将导致segmentation fault错误。这样的chunk也不会包含在任何bin中。
Last remainder
Last remainder 是另外一种特殊的 chunk，就像 top chunk 和 mmaped chunk 一样，不会在任何 bins 中找到这种 chunk。当需要分配一个 small chunk，但在small bins 中找不到合适 的 chunk，如果 last remainder chunk 的大小大于所需的 small chunk 大小，last remainder chunk 被分裂成两个 chunk，其中一个 chunk 返回给用户，另一个 chunk 变成新的 last remainder chuk。