堆入门 | moyaoxueの小屋

type

status

date

slug

堆结构

chunk

chunk具体结构

prev_size, 如果该 chunk 的 物理相邻的前一地址 chunk（两个指针的地址差值为前一 chunk 大小） 是空闲的话，那该字段记录的是前一个 chunk 的大小 (包括 chunk 头)。否则，该字段可以用来存储物理相邻的前一个 chunk 的数据。这里的前一 chunk 指的是较低地址的 chunk 。

size ，该 chunk 的大小，大小必须是 MALLOC_ALIGNMENT 的整数倍。如果申请的内存大小不是 MALLOC_ALIGNMENT 的整数倍，会被转换满足大小的最小的 MALLOC_ALIGNMENT 的倍数，这通过 request2size() 宏完成。32 位系统中， MALLOC_ALIGNMENT 可能是 4 或 8 ；64 位系统中，MALLOC_ALIGNMENT 是 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 的 prev_size 域无效，所以下一个 chunk 的该部分也可以被当前 chunk 使用。这就是 chunk 中的空间复用。

malloced chunk

free chunk

top chunk：

从未被使用过的内存区域

bin

ptmalloc 采用分箱式方法对空闲的 chunk 进行管理。首先，它会根据空闲的 chunk 的大小以及使用状态将 chunk 初步分为 4 类：fast bins，small bins，large bins，unsorted bin。每类中仍然有更细的划分，相似大小的 chunk 会用双向链表链接起来。也就是说，在每类 bin 的内部仍然会有多个互不相关的链表来保存不同大小的 chunk。

unsorted bin

fast bins

smal bins

large bins

(tcache)

对于 small bins，large bins，unsorted bin 来说，ptmalloc 将它们维护在同一个数组中。这些 bin 对应的数据结构在 malloc_state 中，如下

这里是为啥：https://ctf-wiki.org/pwn/linux/user-mode/heap/ptmalloc2/heap-structure/#_4:~:text=此外，上述这些 bin 的排布都会遵循一个原则：任意两个物理相邻的空闲 chunk 不能在一起。

fastbin

glibc 采用单向链表对其中的每个 bin 进行组织，并且每个 bin 采取 LIFO 策略，最近释放的 chunk 会更早地被分配当用户需要的 chunk 的大小小于 fastbin 的最大大小时， ptmalloc 会首先判断 fastbin 中相应的 bin 中是否有对应大小的空闲块，如果有的话，就会直接从这个 bin 中获取 chunk。如果没有的话，ptmalloc 才会做接下来的一系列操作。索引：

fastbin 范围的 chunk 的 inuse 始终被置为 1。因此它们不会和其它被释放的 chunk 合并

但是当释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后的大小大于 FASTBIN_CONSOLIDATION_THRESHOLD 时，内存碎片可能比较多了，我们就需要把 fast bins 中的 chunk 都进行合并，以减少内存碎片对系统的影响。malloc_consolidate 函数可以将 fastbin 中所有能和其它 chunk 合并的 chunk 合并在一起。

Small Bin

small bins 中每个 chunk 的大小与其所在的 bin 的 index 的关系为：chunk_size = 2 * SIZE_SZ *index，具体如下

下标	SIZE_SZ=4（32 位）	SIZE_SZ=8（64 位）
2	16	32
3	24	48
4	32	64
5	40	80
x	24x	28x
63	504	1008

small bins 中一共有 62 个循环双向链表，每个链表中存储的 chunk 大小都一致。small bins 中每个 bin 对应的链表采用 FIFO 的规则，所以同一个链表中先被释放的 chunk 会先被分配出去。 fastbin 与 small bin 中 chunk 的大小有很大一部分重合，fast bin 中的 chunk 是有可能被放到 small bin 中去的

large bin

large bins 中一共包括 63 个 bin，每个 bin 中的 chunk 的大小不一致，而且处于一定区间范围内。此外，这 63 个 bin 被分成了 6 组，每组 bin 中的 chunk 大小之间的公差一致，具体如下：

组	数量	公差
1	32	64B
2	16	512B
3	8	4096B
4	4	32768B
5	2	262144B
6	1	不限制

这里我们以 32 位平台的 large bin 为例，第一个 large bin 的起始 chunk 大小为 512 字节，位于第一组，所以该 bin 可以存储的 chunk 的大小范围为 [512,512+64)。

关于 large bin 的宏如下，这里我们以 32 位平台下，第一个 large bin 的起始 chunk 大小为例，为 512 字节，那么 512>>6 = 8，所以其下标为 56+8=64。

Unsorted Bin

unsorted bin 可以视为空闲 chunk 回归其所属 bin 之前的缓冲区

unsorted bin 处于我们之前所说的 bin 数组下标 1 处。故而 unsorted bin 只有一个链表。unsorted bin 中的空闲 chunk 处于乱序状态，主要有两个来源

当一个较大的 chunk 被分割成两半后，如果剩下的部分大于 MINSIZE，就会被放到 unsorted bin 中。

释放一个不属于 fast bin 的 chunk，并且该 chunk 不和 top chunk 紧邻时，该 chunk 会被首先放到 unsorted bin 中。

Unsorted Bin 在使用的过程中，采用的遍历顺序是 FIFO

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。

内存分配

如下图所示，我们主要考虑对堆进行申请内存块的操作。

(s)brk

对于堆的操作，操作系统提供了 brk 函数，glibc 库提供了 sbrk 函数，我们可以通过增加 brk 的大小来向操作系统申请内存。

初始时，堆的起始地址 start_brk 以及堆的当前末尾 brk 指向同一地址。根据是否开启 ASLR，两者的具体位置会有所不同

不开启 ASLR 保护时，start_brk 以及 brk 会指向 data/bss 段的结尾。

开启 ASLR 保护时，start_brk 以及 brk 也会指向同一位置，只是这个位置是在 data/bss 段结尾后的随机偏移处。

具体效果如下图所示

mmap

malloc 会使用 mmap 来创建独立的匿名映射段。匿名映射的目的主要是可以申请以 0 填充的内存，并且这块内存仅被调用进程所使用。

虽然程序可能只是向操作系统申请很小的内存，但是为了方便，操作系统会把很大的内存分配给程序。这样的话，就避免了多次内核态与用户态的切换，提高了程序的效率。我们称这一块连续的内存区域为 arena。此外，我们称由主线程申请的内存为 main_arena。后续的申请的内存会一直从这个 arena 中获取，直到空间不足。当 arena 空间不足时，它可以通过增加 brk 的方式来增加堆的空间。类似地，arena 也可以通过减小 brk 来缩小自己的空间。

堆行为（申请内存）

unlink

unlink 用来将一个双向链表（只存储空闲的 chunk）中的一个元素取出来，可能在以下地方使用

malloc

从恰好大小合适的 large bin 中获取 chunk。

这里需要注意的是 fastbin 与 small bin 就没有使用 unlink，这就是为什么漏洞会经常出现在它们这里的原因。
依次遍历处理 unsorted bin 时也没有使用 unlink 。

从比请求的 chunk 所在的 bin 大的 bin 中取 chunk。

free

后向合并，合并物理相邻低地址空闲 chunk。
前向合并，合并物理相邻高地址空闲 chunk（除了 top chunk）

malloc_consolidate

后向合并，合并物理相邻低地址空闲 chunk。
前向合并，合并物理相邻高地址空闲 chunk（除了 top chunk）

realloc

前向扩展，合并物理相邻高地址空闲 chunk（除了 top chunk）

smallbin Unlink

P 最后的 fd 和 bk 指针并没有发生变化，但是当我们去遍历整个双向链表时，已经遍历不到对应的链表了。这一点没有变化还是很有用处的，因为我们有时候可以使用这个方法来泄漏地址

libc 地址

P 位于双向链表头部，bk 泄漏
P 位于双向链表尾部，fd 泄漏
双向链表只包含一个空闲 chunk 时，P 位于双向链表中，fd 和 bk 均可以泄漏

泄漏堆地址，双向链表包含多个空闲 chunk

P 位于双向链表头部，fd 泄漏
P 位于双向链表中，fd 和 bk 均可以泄漏
P 位于双向链表尾部，bk 泄漏

注意

这里的头部指的是 bin 的 fd 指向的 chunk，即双向链表中最新加入的 chunk。

这里的尾部指的是 bin 的 bk 指向的 chunk，即双向链表中最先加入的 chunk。

堆的第一个 chunk 所记录的 prev_inuse 位默认为 1

__libc_malloc

首先检查是否有内存分配函数的钩子函数（__malloc_hook），这个主要用于用户自定义的堆分配函数，方便用户快速修改堆分配函数并进行测试。这里需要注意的是，用户申请的字节一旦进入申请内存函数中就变成了无符号整数（即存在house of force之类的洞）

接着会寻找一个 arena 来试图分配内存。

然后调用 _int_malloc 函数去申请对应的内存。

如果分配失败的话，ptmalloc 会尝试再去寻找一个可用的 arena，并分配内存。

如果申请到了 arena，那么在退出之前还得解锁。

判断目前的状态是否满足以下条件

要么没有申请到内存

要么是 mmap 的内存

要么申请到的内存必须在其所分配的 arena 中

最后返回内存。

_int_malloc

_int_malloc 是内存分配的核心函数，其核心思路有如下

它根据用户申请的内存块大小以及相应大小 chunk 通常使用的频度（fastbin chunk, small chunk, large chunk），依次实现了不同的分配方法。

它由小到大依次检查不同的 bin 中是否有相应的空闲块可以满足用户请求的内存。

当所有的空闲 chunk 都无法满足时，它会考虑 top chunk。

当 top chunk 也无法满足时，堆分配器才会进行内存块申请。

large bin 行为

large bin

当 fast bin、small bin 中的 chunk 都不能满足用户请求 chunk 大小时，就会考虑是不是 large bin。但是，其实在 large bin 中并没有直接去扫描对应 bin 中的 chunk，而是先利用 malloc_consolidate

函数处理 fast bin 中的 chunk，将有可能能够合并的 chunk 先进行合并后放到 unsorted bin 中，不能够合并的就直接放到 unsorted bin 中，然后再在下面的大循环中进行相应的处理。为什么不直接从相应的 bin 中取出 large chunk 呢？这是 ptmalloc 的机制，它会在分配 large chunk 之前对堆中碎片 chunk 进行合并，以便减少堆中的碎片。

遍历 unsorted bin

在接下来的这个循环中，主要做了以下的操作

按照 FIFO 的方式逐个将 unsorted bin 中的 chunk 取出来

如果是 small request，则考虑是不是恰好满足，是的话，直接返回
如果不是的话，放到对应的 bin 中

尝试从 large bin 中分配用户所需的内存

该部分是一个大循环，这是为了尝试重新分配 small bin chunk，这是因为我们虽然会首先使用 large bin，top chunk 来尝试满足用户的请求，但是如果没有满足的话，由于我们在上面没有分配成功 small bin，我们并没有对 fast bin 中的 chunk 进行合并，所以这里会进行 fast bin chunk 的合并，进而使用一个大循环来尝试再次分配 small bin chunk。

先考虑 unsorted bin，再考虑 last remainder

unsorted bin 的遍历顺序为 bk

一系列检查（libc 2.31）

remainder

当分配器在内存分配时，如果找到的某个空闲内存块的大小（size） 大于用户请求的大小（nb）且差值足够大（大于等于最小块大小 MINSIZE），就会将这个块拆分成两部分：

第一部分：满足用户请求的内存块（nb 大小的块，通常称为 victim）。

第二部分：剩余的未使用的部分，称为 remainder。

把取出来的 chunk 放到对应的 large bin 中

如果请求的 chunk 在 large chunk 范围内，就在对应的 bin 中从小到大进行扫描，找到第一个合适的

真正取出chunk：

使用 top chunk

如果所有的 bin 中的 chunk 都没有办法直接满足要求（即不合并），或者说都没有空闲的 chunk。那么我们就只能使用 top chunk 了

如果堆内存不够，就需要使用 sysmalloc 来申请内存

_libc_calloc

calloc 与 malloc 的区别：

行为上 calloc 在分配后会自动进行清空

对照源码发现

__libc_malloc：如果启用tcache且条件符合则returntcache_get，而calloc没有这段逻辑，即calloc根本不会尝试从tcache中取堆块，这点需要注意

sysmalloc

该函数用于当前堆内存不足时，需要向系统申请更多的内存。

主要关注一下 pagesize，其

pagesize=4096=0x1000

考虑 mmap

正如开头注释所言如果满足如下任何一种条件

没有分配堆。

申请的内存大于 mp_.mmap_threshold，并且 mmap 的数量小于最大值，就可以尝试使用 mmap

堆行为（释放内存）

__libc_free

类似于 malloc，free 函数也有一层封装，命名格式与 malloc 基本类似。代码如下

如果检查都合格的话，判断当前的 bin 是不是在 fast bin 范围内，在的话就插入到 fastbin 头部，即成为对应 fastbin 链表的第一个 free chunk。

合并非 mmap 的空闲 chunk

只有不是 fast bin 的情况下才会触发 unlink

合并的主要顺序为：

先考虑物理低地址空闲块

后考虑物理高地址空闲块

合并后的 chunk 指向合并的 chunk 的低地址。

注意double free会检查 prev_inuse 位

后向合并 - 合并低地址 chunk

需要注意的是，如果下一块不是 top chunk ，则合并高地址的 chunk ，并将合并后的 chunk 放入到 unsorted bin 中

下一块是 top chunk - 合并到 top chunk

向系统返还内存

malloc_state

malloc_consolidate

该函数主要有两个功能

若 fastbin 未初始化，即 global_max_fast 为 0，那就初始化 malloc_state。

如果已经初始化的话，就合并 fastbin 中的 chunk。