# glibc 堆概述：
# 1. 内存管理与堆：
# 概述：
内存管理是堆计算机的内存资源进行管理，这要求在程序请求时能够动态分配内存的一部分，并在程序不需要时释放分配的内存。CTF 竞赛中常见的 ptmalloc2 就是 glibc 实现的内存管理机制，它继承了 dlmalloc，并提供了对多线程的支持。
堆是程序虚拟内存中由低地址向高地址增长的线性区域。一般只有当用户向操作系统申请内存时，这片区域才会被内核分配出来，并且处于效率和页对齐的考虑，通常会分配相当大的连续内存。程序再次申请时便会从这片内存中分配，直到堆空间不能满足时才会再次增长。堆的位置一般在 BSS 段高地址处。
# brk () 和 sbrk ()：
堆的属性是可读可写的，大小通过 brk () 和 sbrk () 函数进行控制。在堆未初始化时，program_break 指向 BSS 段的末尾，通过调用 brk () 和 sbrk () 来移动 program_break 使得堆增长。在堆初始化时，如果开启了 ASLR，则堆的起始地址 start_brk 会在 BSS 段之后的随机位移出，如果没有开启，则 start_brk 会紧接着 BSS 段。
两个函数相关内容如下：
1 |
|
brk () 函数的参数是一个指针，用于设置 program_break 指向的位置。sbrk () 函数的参数 increment (可以是负值) 用于与 program_break 相加来调整 program_break 的值。成功执行后 brk () 函数会返回 0 ，sbrk () 函数会返回上一次 program_break 值（可以设置参数 increment 为 0 来获得当前 program_break 的值）。
# mmap () 和 unmmap ()：
当用户申请内存过大时，ptmalloc2 会选择通过 mmap () 函数创建匿名映射段供用户使用，并通过 unmmap () 函数回收。
# glibc 中的堆：
通常来说，系统中的堆指的是主线程中 main_arena 所管理的区域。但 glibc 会同时维持多个区域来供多线程使用，每个线程都有属于自己的内存（成为 arena），这些连续的内存也可以成为堆。
glibc 的想法是：当用户申请堆块时，从堆中按顺序分配堆块交给用户，用户保存指向这些堆块的指针；当用户释放堆块时，glibc 会将释放的堆块组织成链表；当两块相堆块都为释放状态时将之合并成一个新的堆块；由此解决内存碎片的问题。用户正在使用中的堆块叫作 allocated chunk，被释放的堆块叫做 free chunk，由 free chunk 组成的链表叫 bin。** 我们称呼当前 chunk 低地址处相邻的 chunk 为上一个（后面的）chunk，高地址相邻处的 chunk 为下一个（前面的）chunk。** 为了方便管理，glibc 将不同大小范围的 chunk 组织成不同的 bin 。如 fast bin 、small bin 、large bin 等，在这些链表中的 chunk 分别叫作 fast chunk 、small chunk 和 large chunk 。
# 2. 重要概念和结构体：
# arena：
arena 包含一片或数片连续的内存，堆块将会从这片区域划分给用户。主线程的 arena 被称为 main_arena，它包含 start_brk 和 brk 之间的这片连续内存。
主线程的 arena 只有堆，子线程的 arena 可以有数片连续内存。如果主线程的堆大小不够分的话可以通过 brk () 调用来扩展，但是子线程分配的映射段大小是固定的，不可以扩展，所以子线程分配出来的一段映射段不够用的话就需要再次使用 mmap () 来分配新的内存。
# heap_info 结构体：
如之前所说，子线程的 arena 可以有多片连续内存，这些内存被称为 heap。每一个 heap 都有自己的 heap header 。其定义如下，heap header 是通过链表相连接的，并且 heap header 里面保存了指向其他所属的 arena 的指针。
1 | typedef struct _heap_info |
# malloc_state 结构体：
每个线程只有一个 arena header，里面保存了 bin、top chunk 等信息。主线程的 main_arena 保存在 libc.so 的数据段里，其他线程的 arena 则保存在给该 arena 分配的 heap 里面。malloc_state 定义如下：
1 | struct malloc_state |
# malloc_chunk 结构体：
chunk 是 glibc 管理内存的基本单位，整个堆在初始化后会被当成一个 free chunk，称之为 top chunk ，每次用户请求内存时，如果 bins 中没有合适的 chunk ，malloc 就会从 top chunk 中进行划分，如果 top chunk 的大小不够，则调用 brk () 扩展堆的大小，然后从新生成的 top chunk 中进行切分。用户释放内存时，glibc 会先根据情况将释放的 chunk 与其他相邻的 free chunk 合并，然后加入合适的 bin 中。
下图展示了堆块申请和释放的过程。首先，用户连续申请了三个堆块 A、B、C，此时释放 chunk B ，由于它与 top chunk 不相邻，所以会被放入 bin 中，成为一个 free chunk。现在再次申请一个与 B 相同大小的堆块，则 malloc 将从 bin 中取出 chunk B ，回到一开始的状态，bin 的表头也会指向 null。。但如果用户连续释放 chunk A 和 chunk B ，由于他们相邻且都是 free chunk ，那么就会被合并成一个大的 chunk 放入 bin 中。
对以上知识有了简单的印象之后，就可以看看 chunk 的信息是怎么被 glibc 记录的，下面是 malloc chunk 的结构体定义：
1 | struct malloc_chunk { |
在默认情况下，INTERNAL_SIZE_T 的大小在 64 位系统下是 8 字节，32 位系统下是 4 字节。以下是关于 malloc_chunk 的各个成员的功能：
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 的起始处，也就是 mem 处的地址。
当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域无效，所以下一个 chunk 的该部分也可以被当前 chunk 使用。这就是 chunk 中的空间复用。
1 | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
被释放的 chunk 被记录在链表中（可能是循环双向链表，也可能是单向链表）。具体结构如下:
1 | chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
# 3. 各类 bin 介绍：
chunk 被释放时，glibc 会将它们重新组织起来，构成不同的 bin 链表，当用户再次申请时，就从中寻找合适的 chunk 返回用户。不同大小区间 chunk 被划分到不同的 bin 中，再加上一种特殊的 bin，一共有四种：Fast bin 、Samll bin 、 Large bin 、和 Unsorted bin 。这些 bin 记录在 malloc_state 结构中。
- fastbinsY ：这是一个 bin 数组，里面有 NFASTBINS 个 fast bin。
- bins：也是一个 bin 数组，一共有 126 个 bin ，按顺序分别是：
- bin 1 为 unsorted bin
- bin 2 到 bin 63 为 small bin
- bin 64 到 bin 126 为 large bin
# fast bin ：
在实践中，程序申请和释放的堆块往往都比较小，所以 glibc 对这类 bin 使用单链表结构，并采用 LIFO（后进先出）的分配策略。为了加快速度，fast bin 里的 chunk 不会进行合并操作，所以下一个 chunk 的 PRV_INUSE 始终标记为 1，使其处于使用状态。同一个 fast bin 里 chunk 大小相同，并且在 fastbinY 数组里按照从小到大的顺序排列，序号为 0 的 fast bin 中容纳的 chunk 大小为 4SIZE_SZ 字节，随着序号增加，所容纳的 chunk 递增 2SIZE_SZ 字节。
# unsorted bin：
一定大小的 chunk 被释放时，在进入 small bin 或者 large bin 之前，会先加入 unsorted bin 。在实践中，一个释放的 chunk 常常很快就会被重新使用，所以将其先加入 unsorted bin 可以加快分配的速度。 unsorted bin 使用双链表结构，并采用 FIFO（先进先出）的分配策略。与 fastbinY 不同，unsorted bin 中的 chunk 大小可能是不同的，并且由于是双向链表结构，一个 bin 会占用 bins 的两个元素。
# small bin：
同一个 small bin 里 chunk 的大小相同，采用双链表结构，使用频率介于 fast bin 和 large bin 之间。small bin 在 bins 里居第 2 到 63 位，共 62 个。根据排序，每个 small bin 的大小为 2SIZE_SZinx（idx 表示 bins 数组的下标）。在 64 位系统下，最小的 small chunk 为 2*8*2=32 字节，最大的 small chunk 为 2*8*63=1008 字节。由于 small bin 和 fast bin 有重合的部分，所以这些 chunk 在某些情况下会被加入 small bin 中。
# large bin：
large bin 在 bins 里居 64 到 126 位，共 63 个，被分成了 6 组，每组 bin 所能容纳的 chunk 按顺序排成等差数列，公差分别如下：
1 | 32 bins of size 64 |
32 位系统下第一个 large bin 的 chunk 最小为 512 字节，第二个 large bin 的额 chunk 最小为 512+64 字节（处于 [512，512+64] 之间的 chunk 都属于第一个 large bin），以此类推。64 位系统也是一样的，第一个 large bin 的 chunk 最小为 1024 字节，第二个 large bin 的 chunk 最小为 1024+64 字节（处于 [1024，1024+64] 之间的 chunk 都属于第一个 large bin）以此类推。
large bin 也是采用双链表结构，里面的 chunk 从头节点的 fd 指针开始，按大小顺序进行排列。为了加快检索速度，fd_nextsize 和 bk_nextsize 指针用于指向第一个与自己大小不同的 chunk 时，所以也只有在加入了大小不同的 chunk 时，这两个指针才会被修改。
# 参考资料：
《CTF 竞赛权威指南 pwn 篇》
