堆基础
/网上太多关于这方面的文章了，这里不再重新造轮子了，直接引用ctf wiki以及其他的一些文章的说明，自己再添点东西就好。
0x01 何为堆
在程序运行过程中，堆可以提供动态分配的内存，允许程序申请大小未知的内存。堆其实就是程序虚拟地址空间的一块连续的线性区域，它由低地址向高地址方向增长。我们一般称管理堆的那部分程序为堆管理器。
堆管理器处于用户程序与内核中间，主要做以下工作
- 响应用户的申请内存请求，向操作系统申请内存，然后将其返回给用户程序。同时，为了保持内存管理的高效性，内核一般都会预先分配很大的一块连续的内存，然后让堆管理器通过某种算法管理这块内存。只有当出现了堆空间不足的情况，堆管理器才会再次与操作系统进行交互。
- 管理用户所释放的内存。一般来说，用户释放的内存并不是直接返还给操作系统的，而是由堆管理器进行管理。这些释放的内存可以来响应用户新申请的内存的请求。
Linux 中早期的堆分配与回收由 Doug Lea 实现，但它在并行处理多个线程时，会共享进程的堆内存空间。因此，为了安全性，一个线程使用堆时，会进行加锁。然而，与此同时，加锁会导致其它线程无法使用堆，降低了内存分配和回收的高效性。同时，如果在多线程使用时，没能正确控制，也可能影响内存分配和回收的正确性。Wolfram Gloger 在 Doug Lea 的基础上进行改进使其可以支持多线程，这个堆分配器就是 ptmalloc 。在 glibc-2.3.x. 之后，glibc 中集成了 ptmalloc2。
目前 Linux 标准发行版中使用的堆分配器是 glibc 中的堆分配器：ptmalloc2。ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。
需要注意的是，在内存分配与使用的过程中，Linux 有这样的一个基本内存管理思想，只有当真正访问一个地址的时候，系统才会建立虚拟页面与物理页面的映射关系。 所以虽然操作系统已经给程序分配了很大的一块内存，但是这块内存其实只是虚拟内存。只有当用户使用到相应的内存时，系统才会真正分配物理页面给用户使用。
0x02 堆的基本操作
这里主要说下基本的堆操作（包括堆的分配，回收，堆分配背后的系统调用）以及堆目前的多线程支持等。
malloc
1 | malloc(size_t n) |
malloc 函数返回对应大小字节的内存块的指针。此外，该函数还对一些异常情况进行了处理
- 当 n=0 时，返回当前系统允许的堆的最小内存块。
- 当 n 为负数时，由于在大多数系统上，size_t 是无符号数（这一点非常重要），所以程序就会申请很大的内存空间，但通常来说都会失败，因为系统没有那么多的内存可以分配。
free
1 | free(void* p) |
free 函数会释放由 p 所指向的内存块。这个内存块有可能是通过 malloc 函数得到的，也有可能是通过相关的函数 realloc 得到的。
此外，该函数也同样对异常情况进行了处理
- 当 p 为空指针时，函数不执行任何操作。
- 当 p 已经被释放之后，再次释放会出现乱七八糟的效果，这其实就是
double free。 - 除了被禁用 (mallopt) 的情况下，当释放很大的内存空间时，程序会将这些内存空间还给系统，以便于减小程序所使用的内存空间。
内存分配背后的系统调用
在前面提到的函数中，无论是 malloc 函数还是 free 函数，我们动态申请和释放内存时，都经常会使用，但是它们并不是真正与系统交互的函数。这些函数背后的系统调用主要是 (s)brk 函数以及 mmap, munmap 函数。
如下图所示，我们主要考虑对堆进行申请内存块的操作。
(s)brk
对于堆的操作，操作系统提供了 brk 函数，glibc 库提供了 sbrk 函数，我们可以通过增加 brk 的大小来向操作系统申请内存。初始时，堆的起始地址 start_brk 以及堆的当前末尾 brk 指向同一地址。根据是否开启 ASLR，两者的具体位置会有所不同
- 不开启 ASLR 保护时，start_brk 以及 brk 会指向 data/bss 段的结尾。
- 开启 ASLR 保护时，start_brk 以及 brk 也会指向同一位置，只是这个位置是在 data/bss 段结尾后的随机偏移处。
具体效果如下图（这个图片与网上流传的基本一致，这里是因为要画一张大图，所以自己单独画了下）所示
示例：
在每一次执行完操作后，都执行了 getchar() 函数，这是为了方便查看程序真正的映射。
1 | /* sbrk and brk example */ |
在第一次调用brk()之前
可以看出，并没有出现堆。此时：
start_brk = end_data = brk = 0x0x230d000
第一次调用brk()——增加内存
已经出现了堆段。
1 | brk(curr_brk+4096); |
通过增加brk的大小来向OS申请内存，较之前申请了0x1000即4096字节的内存空间。此时：
start_brk = end_data = 0x0230d000
brk = 0x0230e000
其中，关于堆的那一行
- 0x0230d000是相应堆的起始地址
- rw-p表明堆具有可读可写权限，并且属于隐私数据
- 00000000 表明文件偏移，由于这部分内容并不是从文件中映射得到的，所以为0
- 00:00是主从 (Major/mirror) 的设备号，这部分内容也不是从文件中映射得到的，所以也都为0
- 0表示着Inode 号。由于这部分内容并不是从文件中映射得到的，所以为0
第二次调用brk()——减少内存
1 | brk(tmp_brk); |
通过减少brk的大小，使堆的内存空间减至初始的大小。此时：
start_brk = end_data = brk = 0x0x230d000
恢复为了之前的状态，没有heap段。
mmap
malloc 会使用 mmap 来创建独立的匿名映射段。匿名映射的目的主要是可以申请以 0 填充的内存，并且这块内存仅被调用进程所使用。
示例：
1 | /* Private anonymous mapping example using mmap syscall */ |
在执行 mmap 之前
可以从下面的输出看到，目前只有. so文件的mmap段：
mmap 后
从下面的输出可以看出，我们申请的内存与已经存在的内存段结合在了一起构成了7f2a92624000到7f2a92645000的mmap段：
munmap
从下面的输出，我们可以看到我们原来申请的内存段已经没有了，内存段又恢复了原来的样子了：
多线程支持
在原来的 dlmalloc 实现中，当两个线程同时要申请内存时，只有一个线程可以进入临界区申请内存，而另外一个线程则必须等待直到临界区中不再有线程。这是因为所有的线程共享一个堆。在 glibc 的 ptmalloc 实现中，比较好的一点就是支持了多线程的快速访问。在新的实现中，所有的线程共享多个堆。
示例：
1 | /* Per thread arena example. */ |
注意在gcc编译时加上-lpthread参数，否则会编译出错，因为pthread不是Linux下的默认的库，也就是在链接的时候，无法找到phread库中函数的入口地址，于是链接会失败。
第一次申请之前
没有heap段。
第一次申请后
heap段被建立了，并且它就紧邻着数据段，这说明malloc的背后是用brk()函数来实现的。同时需要注意的是，我们虽然只是申请了 1000 个字节，但是我们却得到了|0x01291000-0x012b2000|=0x21000 个字节的堆。这说明虽然程序可能只是向操作系统申请很小的内存，但是为了方便，操作系统会把很大的内存分配给程序。这样的话，就避免了多次内核态与用户态的切换，提高了程序的效率。我们称这一块连续的内存区域为arena。此外，我们称由主线程申请的内存为main_arena。后续的申请的内存会一直从这个arena 中获取，直到空间不足。当arena空间不足时，它可以通过增加brk的方式来增加堆的空间。类似地，arena也可以通过减小brk来缩小自己的空间。
在主线程释放内存后
对应的arena并没有进行回收，而是交由glibc来进行管理。当后面程序再次申请内存时，在glibc中管理的内存充足的情况下，glibc就会根据堆分配的算法来给程序分配相应的内存。
在第一个线程 malloc 之前
可以看到并没有出现与线程1相关的堆，但是出现了与线程1相关的栈。
第一个线程 malloc 后
可以看出线程1的堆段被建立了，而且它所在的位置为内存映射段区域，同样大小也是132KB(7fd1a0000000-7fd1a0021000)。因此这表明该线程申请的堆时，背后对应的函数为mmap函数。同时可以看出实际真的分配给程序的内存为64M(7fd1a0000000-7fd1a4000000)，而且只有132KB的部分具有可读可写权限，这一块连续的区域成为thread arena。
注意：
当用户请求的内存大于 128KB 时，并且没有任何 arena 有足够的空间时，那么系统就会执行 mmap 函数来分配相应的内存空间。这与这个请求来自于主线程还是从线程无关。
在第一个线程释放内存后
可以看到，这样释放内存同样不会把内存重新给系统。
0x03 堆相关数据结构
与堆相关的数据结构主要分为
- 宏观结构，包含堆的宏观信息，可以通过这些数据结构索引堆的基本信息。
- 微观结构，用于具体处理堆的分配与回收中的内存块。
微观结构
malloc_chunk
概述
在程序的执行过程中，称由malloc()申请的内存为chunk。这块内存在ptmalloc内部用malloc_chunk结构体来表示。当程序申请的 chunk 被 free 后，会被加入到相应的空闲管理列表中。
无论一个chunk的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构。虽然它们使用了同一个数据结构，但根据是否被释放，它们的表现形式会有所不同。
malloc_chunk的结构如下：
1 | struct malloc_chunk { |
首先，这里给出一些必要的解释 INTERNAL_SIZE_T，SIZE_SZ，MALLOC_ALIGN_MASK：
1 | /* The corresponding word size. */ |
一般来说，size_t 在 64 位中是 64 位无符号整数，32 位中是 32 位无符号整数。
每个字段的具体的解释如下：
- prev_size, 如果该 chunk 的物理相邻的前一地址 chunk（两个指针的地址差值为前一 chunk 大小）是空闲的话，那该字段记录的是前一个 chunk 的大小 (包括 chunk 头)。否则，该字段可以用来存储物理相邻的前一个 chunk 的数据。这里的前一 chunk 指的是较低地址的 chunk 。
- size，该 chunk 的大小，大小必须是 2 SIZE_SZ 的整数倍。如果申请的内存大小不是 2 SIZE_SZ 的整数倍，会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。32 位系统中，SIZE_SZ 是 4；64 位系统中，SIZE_SZ 是 8。 该字段的低三个比特位对 chunk 的大小没有影响，它们从高到低分别表示
- NON_MAIN_ARENA，记录当前 chunk 是否不属于主线程，1 表示不属于，0 表示属于。
- IS_MAPPED，记录当前 chunk 是否是由 mmap 分配的。
- PREV_INUSE，记录前一个 chunk 块是否被分配。一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。
- fd，bk。 chunk 处于分配状态时，从 fd 字段开始是用户的数据。chunk 空闲时，会被添加到对应的空闲管理链表中，其字段的含义如下
- fd 指向下一个（非物理相邻）空闲的 chunk
- bk 指向上一个（非物理相邻）空闲的 chunk
- 通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理
- fd_nextsize， bk_nextsize，也是只有 chunk 空闲的时候才使用，不过其用于较大的 chunk（large chunk）。
- fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
- bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
- 一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。
一个已经分配的 chunk 的样子如下。我们称前两个字段称为 chunk header，后面的部分称为 user data。每次 malloc 申请得到的内存指针，其实指向 user data 的起始处。
当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域无效，所以下一个 chunk 的该部分也可以被当前 chunk 使用。这就是 chunk 中的空间复用。
1 | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
被释放的 chunk 被记录在链表中（可能是循环双向链表，也可能是单向链表）。具体结构如下：
1 | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
可以发现，如果一个 chunk 处于 free 状态，那么会有两个位置记录其相应的大小
- 本身的 size 字段会记录，
- 它后面的 chunk 会记录。
一般情况下，物理相邻的两个空闲 chunk 会被合并为一个 chunk 。堆管理器会通过 prev_size 字段以及 size 字段合并两个物理相邻的空闲 chunk 块。
！！！一些关于堆的约束，后面详细考虑！！！
1 | /* |
…