笔记 / Heap

堆概述

笔记取自于堆概述 - CTF Wiki和堆相关数据结构 - CTF Wiki

堆的基本操作

malloc

malloc 函数返回对应大小字节的内存块的指针

  • 当 n=0 时，返回当前系统允许的堆的最小内存块

  • 当 n 为负数时，由于在大多数系统上， size_t 是无符号数，所以程序就会申请很大的内存空间，但通常因为系统没有那么多内存可以分配，故都会失败

free

free 函数会释放由 p 所指向的内存块

  • 当 p 为空指针时，函数不执行任何操作

  • 当 p 已经被释放之后，再次释放会造成 double free

  • 除了被禁用 ( mallopt ) 的情况下，当释放很大的内存空间时，程序会将这些内存空间还给系统，以便于减小程序所使用的内存空间

内存分配背后的系统调用

当我们动态申请和释放内存时，使用函数背后的系统调用主要是 (s)brk 函数以及 mmap ， munmap 函数

(s)brk

初始时，堆的起始地址 start_brk 以及堆的当前末尾 brk 指向同一地址。

注意 sbrk(0) 只是查看当前 brk ， brk(addr) 可以修改 brk ，也就是扩展或收缩堆，当 brk 大于 start_brk 时，进程就有了真正的 heap 映射

mmap/munmap

mmap 是在进程虚拟地址空间里单独找一块区域映射出来

munmap 解除映射关系

多线程支持

在 dlmalloc 实现中，所有线程共用一个堆，当两个线程同时要申请内存时，只有一个线程可以进入临界区申请内存，而另外一个线程则必须等待直到临界区中不再有线程

在 ptmalloc 实现中，多个线程可以使用多个 arena ，支持了多线程的快速访问

这里需要知道， malloc 背后的内存来源有两类，一类是 brk 扩展出来的 [heap] ，一类是 mmap 建立的匿名映射

主线程通常通过 brk 来建立 main_arena ，子线程通常通过 mmap 来建立 thread_arena

free 通常只是把 chunk 还给 glibc ，而不一定马上还给操作系统

同时，当用户请求的内存大于 128KB ，并且没有任何 arena 有足够的空间时，那么系统就会执行 mmap 函数来分配相应的内存空间，这与这个请求来自于主线程还是从线程无关

以及，虽然程序可能只是向操作系统申请很小的内存，但是为了方便，操作系统会把很大的内存分配给程序。这样的话，就避免了多次内核态与用户态的切换，提高了程序的效率

堆相关数据结构

[!TIP]

建议搭配上一篇堆基础一起食用

我们来看 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 中的空间复用。

具体流程如下：

  1. 检查 req 是否过大，防止越界或整数溢出
  2. req 是用户数据大小，不包含 chunk 管理结构
  3. 因为可以复用下一个 chunk 的 prev_size，
    所以只需要额外加 SIZE_SZ
  4. 如果计算出来太小，就提升到 MINSIZE
  5. 如果够大，就按照 2 * SIZE_SZ 对齐
  6. 得到真正的 chunk size