堆的简介

堆の简介

快要去比赛了，总结一波堆的知识

堆结构介绍

常见的内存管理库有：

• tcmalloc：谷歌开源的内存管理库
• jemalloc：FreeBSD开发人员所开发
• ptmalloc&ptmalloc 2：基于dlmalloc 2.7.x开发
• ptmalloc中，实现了malloc()、free()和其他函数以对内存进行管理。

glibc使用ptmalloc对内存空间进行管理，在2.3.x版本后集成了ptmalloc 2。

ptmalloc中用户请求的空间由chunk这一数据结构来表示

malloc_chunk 的结构如下

/*
  This struct declaration is misleading (but accurate and necessary).
  It declares a "view" into memory allowing access to necessary
  fields at known offsets from a given base. See explanation below.
*/
struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

chunk指针指向的是chunk的起始位置，但这个位置并不是用户能够写入或读取的起始位置，在已分配的chunk中，用户实际使用的区域从mem指针指向的区域开始。一个chunk（未分配的）中的信息从上往下依次是，前一个chunk的大小 本chunk的大小，最低位，图中P表示前一个chunk是否处于使用中

prv_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。

堆管理方式

ptmalloc采用bin来对空闲的chunk进行管理 bin是一种记录空闲chunk的链表数据结构，是一个将chunk连接起来的链表，它根据chunk的大小进行管理，共四类：

• fast bin
• unsorted bin
• small bin
• large bin

当chunk被释放时，ptmalloc会将属于chunk根据一定的规则放入相应的bin中。

在glibc中用于记录bin的数据结构有两种，分别如下所示：

• fastbinsY: 这是一个数组，用于记录所有的fast bins；

• bins: 这也是一个数组，用于记录除fast bins之外的所有bins。

  一共有126个bins

• bins[1]为unsorted bin

• bins[2-63]为small bin

• bins[64-126]为large bin

• 使用fastbinY数组来维护fast bin。

• 这些bin都位于libc中，因此可以利用链表的结构在特定条件下泄漏libc地址。

  

main_arena

又称为主分配区。

每个进程只有一个主分配区，可有多个非主分配区。

程序每次申请内存时，都要对主分配区加锁，在多线程环境下，对主分配区的竞争可能会非常激烈，因此在ptmalloc中加入了非主分配区来提高malloc的效率

主分配区能够访问进程的heap和mmap区域并向操作系统申请虚拟内存，而非主分配区只能访问mmap区域。

fast bin

单向链表，通过chunk的size进行索引。

fast bin主要用于提高小内存申请的分配效率

默认情况下，对于 SIZE_SZ 为 4B 的平台， 小于 64B 的 chunk 分配请求；对于 SIZE_SZ 为8B 的平台，小于 128B 的 chunk 分配请求，首先查找fast bins

首先会查找 fast bins 中是否有所需大小的 chunk存在（精确匹配），如果存在，就直接返回属于fastbin中的chunk被释放后，这个chunk将会被加入到对应索引值idx的fastbin链表中

fast bin使用LIFO和大小完全匹配的规则

添加操作(free内存)就是将新的fast chunk加入链表尾，删除操作(malloc内存)就是将链表尾部的fast chunk删除。 每个fast bin都是一个单链表(只使用fd指针)。因为在fast bin中无论是添加还是移除fast chunk，都是对“链表尾”进行操作，而不会对某个中间的fast chunk进行操作

在进行分配时，除去原子性方面的安全检查，只对chunk的size域检查。

small bin

双向链表结构

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

small bins 中一共有 62 个循环双向链表，每个链表中存储的 chunk 大小都一致。比如对于 32 位系统来说，下标 2 对应的双向链表中存储的 chunk 大小为均为 16 字节。每个链表都有链表头结点，这样可以方便对于链表内部结点的管理。此外，small bins 中每个 bin 对应的链表采用 FIFO 的规则，所以同一个链表中先被释放的 chunk 会先被分配出去。在分配chunk时，对双向链表进行安全检查。

分配的过程中，会寻找最小的符合申请大小的chunk，对合适的chunk进行分割后，剩余的部分将会被放到unsorted bin中如果small bin还未初始化，会调用相关函数对fast bin中的chunk进行合并并放到unsorted bin中。

large bin

chunk大小范围为：大于512B（SIZE_SZ=4B）或1024B（SIZE_SZ=8B） large bin将它的63个bin按照每组的个数32、16、8、4、2、1分为6组，每组组内的各bin的chunk大小符合等差数列。 在分配的过程中，会寻找最小的符合申请大小的chunk，对合适的chunk进行分割后，剩余的部分将会被放到unsorted bin中。

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

unsorted bin

unsortedbin的chunk链表头存放在bins[1]中

双向链表，可看作是small bin和large bin的缓存进行分配的时候，如果当前选择的unsorted bin中的chunk不符合条件，则该chunk会被放入到相应的bin中，然后继续查找。如果unsorted bin中存在上一次分割剩下的chunk，则先匹配该chunk。 分配过程中，会对size进行检查。

malloc函数

在ptmalloc中具体由_int_malloc实现 实际申请空间计算方法： 用户申请的空间加上chunk信息所需空间，再减去后一个chunk的复用空间，地址以2 * SIZE_SZ进行对齐

如果计算结果小于MIN_CHUNK_SIZE，则按系统规定的最小值进行申请。

申请时按照以下顺序查找空闲chunk (tcache)(注：glibc 2.27新加入的机制） fast bin small bin unsorted bin large bin top chunk

free函数

在用户释放一个堆块的时候，程序会更具堆块的大小以及堆块的位置的不同做出不同的操作，先判断当前这个块大小是否小于fastbin的最大值，如果小于fastbin的最大值，并且不临近topchunk的时候，就将这个块，链入到fastbin对应的链中，并不修改后一块的标志位。

如果不是fastbin或者临近topchunk的时候

这时候程序会先检测前项是否是释放状态，如果前项是释放状态，则将前项和当前chunk合并，同时检测后项状态 如果后项是topchunk，则直接将当前的chunk并到topchunk中 如果后项不是topchunk的时候，也会将后项合并到当前，chunk中，并且会修改后块的标志位，然后将这一块链到 unsortedbin上。 在合并中，会触发unlink操作

unlink函数

在free时，如果free的chunk的前一chunk是空闲的，将调用unlink函数将前一chunk从bin中取出。

堆溢出漏洞

造成的原因主要是在堆上对数据进行写入、读取、复制等操作时，未对数据长度、范围等进行良好的处理，导致对非当前chunk进行了操作。 通过堆溢出漏洞，能够覆盖关键数据结构、破坏对结构等。

• Previous
  Windows内存安全保护机制
• Next
  wireshark分析