Heap Exploitation - 基础知识

堆

程序运行过程中，堆可以提供动态分配的内存，允许程序申请大小未定的内存。堆其实就是程序虚拟空间的一块连续的线性区域，它由低地址向高地址生长，并称管理堆的程序为：堆管理器

堆管理器位于程序与内核之间，主要进行以下的工作：

1. 响应用户的申请内存请求，向操作系统申请内存，并将其返回给用户程序。为了保持用户程序的高效性，内核一般都会分配一块很大的连续内存，让堆管理器通过某种算法对其进行管理。只有当堆空间不足时，才会与操作系统进行再次交互
2. 管理用户释放的内存，用户释放的内存并不是直接返回给操作系统，而是由堆管理器进行管理，这样释放的内存可以来响应用户新申请的内存的请求

目前Linux标准发行版中使用的堆分配器是glibc中的堆分配器：ptmalloc2。ptmalloc2主要是通过malloc/free来分配和释放内存块。

堆和栈

堆

• 程序员分配释放，程序员不释放就操作系统回收，分配方式类似于链表。程序自己申请，比如malloc和new这样的。

• 操作系统有个记录空闲地址的链表，申请后就遍历这个链表，找空间大于申请空间的堆结点，找到第一个就把这个节点从那个空闲链表删除，把这一段空闲空间分配给程序。一般来说找到的不一定正好等于申请的大小，多余的就被系统放进空闲链表中。

• 堆向高地址伸展，就和上面说的一样，因为是空闲链表，所以是不连续的。

• 堆是程序员申请的，速度比较慢，容易产生内存碎片。

栈

• 栈的话是编译器自动分配释放，存放函数的参数值、局部变量等，操作方式就和数据结构的栈类似，先进后出这样。比如函数中声明一个局部变量int b，那系统就给b开辟空间。
• 栈空间大于申请空间就可以。
• 栈由高地址向低地址伸展，是连续的内存区域。
• 栈是系统分配，速度比较快。

ptmalloc

分配器

分配器处于内核和用户程序之间。分配器的主要作用：应用户的分配请求，向操作系统申请内存，然后将内存返回给用户程序。为了保证高效，分配器一般都会预先分配一块大于用户请求的内存，然后管理这块内存。用户释放掉的内存也不是立即返回给操作系统的，分配器会管理这些释放掉的空闲空间以应对用户以后的内存分配请求。分配器不仅需要管理分配的内存块，还需要管理空间的内存块。当响应用户的请求时，分配器会首先在空闲空间中寻找一块合适的内存返回给用户，在空闲空间中找不到的情况下才会重新分配一块新的内存。

ptmalloc实现

• 长生命周期的大内存分配使用mmap
• 短生命周期的内存分配使用sbrk
• 尽量只缓存临时使用的空闲小内存块，大内存块或者是生命周期较长的大内存块释放时直接归还给操作系统
• 长期存储的程序不合适用ptmalloc管理
• 空闲的小内存块只会在malloc和free的时候进行合并。

堆的基本操作

malloc

在glibc的malloc.c中对malloc的说明如下：

/*
  malloc(size_t n)
  Returns a pointer to a newly allocated chunk of at least n bytes, or null
  if no space is available. Additionally, on failure, errno is
  set to ENOMEM on ANSI C systems.
  If n is zero, malloc returns a minumum-sized chunk. (The minimum
  size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
  systems.)  On most systems, size_t is an unsigned type, so calls
  with negative arguments are interpreted as requests for huge amounts
  of space, which will often fail. The maximum supported value of n
  differs across systems, but is in all cases less than the maximum
  representable value of a size_t.
*/

翻译一下就是，malloc函数返回对应大小字节的指针。一些异常情况下，当n=0时，返回当前系统允许的堆的最小内存块；当n为负数时，由于在大多数系统上，size_t是无符号整数，所以程序就会申请很大的内存空间，而由于一般来说系统没有那么多的内存能分配，所以通常会失败。

free

在 glibc 的 malloc.c中对free 的说明如下

/*
      free(void* p)
      Releases the chunk of memory pointed to by p, that had been previously
      allocated using malloc or a related routine such as realloc.
      It has no effect if p is null. It can have arbitrary (i.e., bad!)
      effects if p has already been freed.
      Unless disabled (using mallopt), freeing very large spaces will
      when possible, automatically trigger operations that give
      back unused memory to the system, thus reducing program footprint.
*/

就是说free函数会释放p所指向的内存块，这个内存块有可能是通过malloc或者realloc得到的。一些异常情况下，p如果是空指针不执行任何操作；但如果p已经被释放了，再次释放会出现一些不明觉厉的效果，就是double free；除了被禁用（mallopt）的情况下，当释放很大的内存空间时，程序会将这些内存空间还给系统以便减少程序使用的内存空间。

系统调用

malloc和free函数实际上是我们申请和释放内存的会使用到的，这些函数背后的系统调用主要是 (s)brk 函数以及 mmap, munmap 函数，它们来与系统进行交互，如下图所示

(s)brk

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

在堆未初始化时，program_break指向bss段的末尾，通过调用brk()和sbrk()来移动program_break使得堆增长。

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

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

函数定义

#include <unistd.h>
int brk(void* end_data_segment);
void *sbrk(intptr_t increment)

brk()的参数是一个指针，用于设置program_break指向的位置。sbrk()的参数increment（可以是负值）用来和program-break相加调整program_break的值。

mmap

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

多线程支持

在原来的dlmalloc实现中，因为所有线程共享一个堆，所以当两个线程要申请内存时，只有一个线程可以进入临界区申请内存，另一个线程则必须等待到临界区中不再有线程才能申请。在glibc的ptmalloc实现中，支持了多线程的快速访问，所有线程共享多个堆。

堆的结构

主要分为：

宏观结构：

• 包含堆的宏观信息，可以通过这些数据结构索引堆的基本信息
• 主要是堆块之间的链接

微观结构

• 用于处理堆分配与回收的内存块
• 主要还是怎么处理堆的分配与回收中的内存块
• malloc、free

微观结构

堆的利用与这些结构密切相关

malloc_chunk

chunk是glibc管理内存的基本单位，整个堆会在初始化后被当作是一个free chunk，称为top chunk。

结构

在程序执行的过程中，称由malloc申请的内存为chunk，这块内存在ptmalloc内部用malloc chunk保存，当chunk被free后，会被加入相应的空闲管理列表。

无论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 head，用来保存chunk信息，方便后续对chunk进行分配与释放。这部分包含prev_size和size，大小为size_t，在32位程序中size_t为32位无符号整数，在64位程序中为64位无符号整数。所以堆中实际分配的内存会比用户申请的大两倍size_t。另一部分由chunk所处的状态决定，一般称为user data。如果是已分配的chunk，会被用来存储数据，如果是被释放的空闲chunk，则包含fd、bk、fd_nextsize、bk_nextsize，并保存bin中链表的指针，大小为size_t字节。

默认情况下INTFRNAL_SIZE_T的大小在64位系统下是8字节，32位系统下是4字节。

对每个字段的解释：

• 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。简单来说就是size记录当前chunk的大小，在32位程序中是8字节对齐的，64位程序中则是16字节对齐。该字段的低三位不影响chunk，从高到低分别表示

  • NON_MAIN_ARENA（A位）：记录当前chunk是否不属于主线程，不属于为1，属于为0
  • IS_MAPPED（M位）：记录当前chunk是否是由mmap分配的
  • PREV_INUSE（P位）：记录前一个chunk是否被分配。一般来说，堆中第一个被分配的内存块的size字段的P位都会被设置为1，以便于防止前面的非法内存。为0时表示被释放，可以通过prev_size获取上一个chunk的大小和地址，方便进行空闲chunk的合并。

• fd，bk：chunk处于分配状态时，从fd开始是用户的数据，chunk空闲时，会被添加到对应的空闲管理链表中，仅在当前chunk处于释放状态时有效。字段含义如下：

  • fd指向下一个（非物理相邻）空闲的chunk
  • bk指向上一个（非物理相邻）空闲的chunk
  • 通过fd和bk可以将空闲的chunk加入到空闲的chunk块链表进行统一管理

• fd_nextsize，bk_nextsize：与fd和bk相似，仅在处于释放状态时有效’否则就是用户使用的空间，不同的是它们仅用于large bins

  • fd_nextsize指向前一个与当前chunk大小不同的第一个空闲块，不包含bin的头指针
  • bk_nextsize指向后一个与当前chunk大小不同的第一个空闲块，不包含bin的头指针
  • 一般情况下，large chunk在fd的遍历中，按从大到小的顺序排列，避免挨个遍历

一个被分配的chunk结构如下，申请的chunk经malloc()函数返回给用户的内存指针实际上是指向user data的mem指针，指向user data的起始处。

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of previous chunk, if unallocated (P clear)  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of chunk, in bytes                     |A|M|P|
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             User data starts here...                          .
        .                                                               .
        .             (malloc_usable_size() bytes)                      .
next    .                                                               |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             (size of chunk, but used for application data)    |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of next chunk, in bytes                |A|0|1|
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

当一个chunk被分配后，实际上它的下一个chunk的prev_size是无效的，那么下一个chunk的prev_size就可以被当前的chunk使用，这就是chunk的空间复用。

被释放的chunk被记录在链表中，结构如下：

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of previous chunk, if unallocated (P clear)  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`head:' |             Size of chunk, in bytes                     |A|0|P|
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Forward pointer to next chunk in list             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Back pointer to previous chunk in list            |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Unused space (may be 0 bytes long)                .
        .                                                               .
 next   .                                                               |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`foot:' |             Size of chunk, in bytes                           |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |             Size of next chunk, in bytes                |A|0|0|
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

一般来说，物理相邻的两个空闲chunk会被合并为一个chunk，堆管理器会通过prev_size和size将两个物理相邻的空闲chunk块合并。

malloc chunk是如何节省内存的

• prev_size在上一个chunk为释放状态时才有效，否则会加入上一个chunk的user data部分。节省一个SIZE_SZ大小的内存
• size最后三位被用来标记chunk的状态
• fd和bk指针仅在释放状态下有效，节省了SIZE_SZ * 2 大小的内存
• fd_nextsize和bk_nextsize仅在large bins中有效

chunk堆相关的宏

主要涉及到一些chunk大小、对齐、转换的宏。

太多了，用到再说。。。。。。

bin

用户释放掉的chunk不会直接归还给系统，而是由ptmalloc统一管理heap和mmap映射区域中空闲的chunk，当用户再一次申请分配内存时，ptmalloc分配器就会在空闲的chunk中找一块合适的给用户，这样可以避免频繁的进行系统调用，降低内存分配的开销。

bin是一种链表结构，用于管理被释放的空闲chunk，当用户释放chunk后，会根据chunk的大小以及使用状态将其存储在不同的bin中。用户再申请内存时，系统会检索bin来分配合适的chunk给用户。bin分为四类：fastbin、small bin、large bin、unsorted bin，在glibc2.26以后 ，还加入了tcache。

ptmalloc将small bin、large bin、unsorted bin维护在同一个数组中，这些bin对应的数据结构在malloc_state中

#define NBINS 128
/* Normal bins packed as described above */
mchunkptr bins[ NBINS * 2 - 2 ];

bins主要用于索引不同的bin的fd和dk

为了简化使用，每个bin的header都是malloc_chunk类型。为了节省空间和提高局限性，只分配bin的fd/bk指针，然后使用repositioning tricks将这些指针视为一个malloc_chunk*字段。

32位系统中，bins的前4项含义如下：

• bin[0]：bin1的fb/bin2的prev_size
• bin[1]：bin1的bk/bin2的size
• bin[2]：bin2的fd/bin3的prev_size
• bin[3]：bin2的bk/bin3的size

bin2的prev_size、size和bin1的fd、bk重合，由于一般使用fd、bk来索引链表，所以实际上后一个bin和前一个bin虽然共用部分数据，但是记录的就是前一个bin的链表数据。

数组中的bin依次如下：

• 第一个为unsorted bin，没有进行排序，比较杂
• 索引从2到63的bin为small bin，同一个small bin链表中的chunk的大小相同。两个相邻索引的small bin链表中chunk相差的字节数在32位为8字节，64位中为16字节。
• small bins后面的bin被称作是large bins。large bins中的每一个bin都包含一定范围内的chunk，其中的chunk按fd指针的顺序从大到小排列，相同大小的chunk按照最近使用顺序排列。

并且，任意两个物理相邻的空闲chunk不能在一起

ptmalloc为了提高分配的速度，会把一些小的chunk先放到fast bins的容器内，并且fast bin容器中的chunk使用标记总是被置位的

bin中的宏：用到再说。。。。。。

Fast Bin

程序会经常申请或释放一些比较小的内存块，如果将较小的chunk释放后与相邻空闲的chunk合并，那么下次申请较小的chunk时又要分割，为了防止这种情况的发生，就有了Fast bin。对应变量就是malloc state中的fastbinsY

/*
   Fastbins

    An array of lists holding recently freed small chunks.  Fastbins
    are not doubly linked.  It is faster to single-link them, and
    since chunks are never removed from the middles of these lists,
    double linking is not necessary. Also, unlike regular bins, they
    are not even processed in FIFO order (they use faster LIFO) since
    ordering doesn't much matter in the transient contexts in which
    fastbins are normally used.

    Chunks in fastbins keep their inuse bit set, so they cannot
    be consolidated with other free chunks. malloc_consolidate
    releases all chunks in fastbins and consolidates them with
    other free chunks.
 */
typedef struct malloc_chunk *mfastbinptr;

/*
    This is in malloc_state.
    /* Fastbins */
    mfastbinptr fastbinsY[ NFASTBINS ];
*/

glibc采用单向链表堆每个bin进行组织，并且每个bin采用LIFO的方式，最近释放的chunk会被更早的分配。也就是说，如果申请的chunk小于fastbin的最大大小时，ptmalloc就会先判断fastbin中是否有大小合适的空闲块。有就会直接用，没有就会进行别的操作。

同一大小的 chunk 会在同一条链上，不同大小的 chunk 在不同的链上

不同平台大小不同，列一个索引，当 malloc 的大小在这个范围内的时候会首先去 fast bin 中找

fastbinsY[]	x86（size_t=4）	x64（size_t=8）
0	0x10	0x20
1	0x18	0x30
2	0x20	0x40
3	0x28	0x50
4	0x30	0x60
5	0x38	0x70
6	0x40	0x80

32位系统中，一般fast bin默认支持的最大chunk的大小是64字节，但是支持的chunk的数据空间大小为80字节，最多支持10个bin。

#define NFASTBINS (fastbin_index(request2size(MAX_FAST_SIZE)) + 1)

#ifndef DEFAULT_MXFAST
#define DEFAULT_MXFAST (64 * SIZE_SZ / 4)
#endif

/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE (80 * SIZE_SZ / 4)

/*
   Since the lowest 2 bits in max_fast don't matter in size comparisons,
   they are used as flags.
 */

/*
   FASTCHUNKS_BIT held in max_fast indicates that there are probably
   some fastbin chunks. It is set true on entering a chunk into any
   fastbin, and cleared only in malloc_consolidate.

   The truth value is inverted so that have_fastchunks will be true
   upon startup (since statics are zero-filled), simplifying
   initialization checks.
 */
//判断分配区是否有 fast bin chunk，1表示没有
#define FASTCHUNKS_BIT (1U)

#define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)
#define clear_fastchunks(M) catomic_or(&(M)->flags, FASTCHUNKS_BIT)
#define set_fastchunks(M) catomic_and(&(M)->flags, ~FASTCHUNKS_BIT)

/*
   NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous
   regions.  Otherwise, contiguity is exploited in merging together,
   when possible, results from consecutive MORECORE calls.

   The initial value comes from MORECORE_CONTIGUOUS, but is
   changed dynamically if mmap is ever used as an sbrk substitute.
 */
// MORECORE是否返回连续的内存区域。
// 主分配区中的MORECORE其实为sbr()，默认返回连续虚拟地址空间
// 非主分配区使用mmap()分配大块虚拟内存，然后进行切分来模拟主分配区的行为
// 而默认情况下mmap映射区域是不保证虚拟地址空间连续的，所以非主分配区默认分配非连续虚拟地址空间。
#define NONCONTIGUOUS_BIT (2U)

#define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)
#define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0)
#define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT)
#define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)

/* ARENA_CORRUPTION_BIT is set if a memory corruption was detected on the
   arena.  Such an arena is no longer used to allocate chunks.  Chunks
   allocated in that arena before detecting corruption are not freed.  */

#define ARENA_CORRUPTION_BIT (4U)

#define arena_is_corrupt(A) (((A)->flags & ARENA_CORRUPTION_BIT))
#define set_arena_corrupt(A) ((A)->flags |= ARENA_CORRUPTION_BIT)

/*
   Set value of max_fast.
   Use impossibly small value if 0.
   Precondition: there are no existing fastbin chunks.
   Setting the value clears fastchunk bit but preserves noncontiguous bit.
 */

#define set_max_fast(s)                                                        \
    global_max_fast =                                                          \
        (((s) == 0) ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
#define get_max_fast() global_max_fast

ptmalloc 默认情况下会调用 set_max_fast(s) 将全局变量 global_max_fast 设置为 DEFAULT_MXFAST，也就是设置 fast bins 中 chunk 的最大值。当 MAX_FAST_SIZE 被设置为 0 时，系统就不会支持 fastbin 。

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

当释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后的大小大于 FASTBIN_CONSOLIDATION_THRESHOLD 时，内存碎片可能比较多了，就需要把 fast bins 中的 chunk 都进行合并，以减少内存碎片对系统的影响。

/*
   FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
   that triggers automatic consolidation of possibly-surrounding
   fastbin chunks. This is a heuristic, so the exact value should not
   matter too much. It is defined at half the default trim threshold as a
   compromise heuristic to only attempt consolidation if it is likely
   to lead to trimming. However, it is not dynamically tunable, since
   consolidation reduces fragmentation surrounding large chunks even
   if trimming is not used.
 */

#define FASTBIN_CONSOLIDATION_THRESHOLD (65536UL)

Small Bin

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

Small bins中有62个循环双向链表，每个链表中存储的chunk大小一致。Small bins中每个bin对应的链表采用FIFO规则，所以先被释放的chunk会被先分配出去。

fast bin和small bin中的chunk大小会有一部分重合，fast bin中的chunk有一部分是会被放到small bin中的。

Large Bin

large bin中一共包括了63个bin，每个bin中chunk大小不一致。63个bin被分为了6组，每组bin中chunk大小的公差一致。

Unsorted Bin

可以视为空闲chunk回归之前的缓冲区，双向循环链表，存放所有不满足fast bin且未被整理的chunk。malloc的时候如果在其他bin中没有找到合适的就会在Unsorted Bin找并且根据大小放到对应的bin里面。

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

• 较大的chunk被分割后。如果剩下的部分大于MINSIZE，就会被分配到Unsorted Bin中
• 释放一个不属于 fast bin 的 chunk，并且该 chunk 不和 top chunk 紧邻时，该 chunk 会被首先放到 unsorted bin 中

tcache

libc2.26以后出现的，FILO结构，最大位0x410。

每个tcache bin最多能有七个，prev_inuse不置零，不参与合并。指针直接指向chunk的userdata部分。

Top Chunk

程序在第一次进行malloc时，heap会被分为两块，一块给用户，另一块是top chunk，其实就是处于当前堆的物理地址最高的chunk。这个chunk不属于任何一个bin，作用是当所有的bin都无法满足用户请求大小时，如果大小不小于指定大小就进行分配，并将剩下的大小作为新的top chunk。否则对heap进行拓展后再进行分配。在 main arena 中通过 sbrk 扩展 heap，而在 thread arena 中通过 mmap 分配新的 heap。

prev_inuse为1，不参与合并。

mmaped chunk

当需要分配的chunk要很大时，并且fast bin和bins以及top chunk也不能满足需求时，普陶，ptmalloc就会使用mmap直接使用内存映射来将页映射到进程空间。这样分配的chunk会在free时直接解除映射还给操作系统，再次引用就会引起segmentation fault错误。这种chunk不包含在任何bin中。

last remainder

Last remainder是另外一种特殊的chunk，就像top chunk和mmaped chunk一样，不会在任何bins中找到这种chunk。ptmalloc2找到的chunk可能并不和申请的内存大小一致，分割后的剩余部分称为last remainder chunk，unsorted bin也会存。top chunk 分割剩下的部分不会作为 last remainder。

宏观结构

arena

在第一次申请内存时，都会有独立的arena。

一个线程申请的一个或多个堆包含很多信息，Arena就是管理线程中这些堆。

主线程arena包含start brk和brk之间的这片连续内存称为堆。

特性

• 一个线程只有一个arnea，并且这些线程的arnea都是独立的不是相同的
• 主线程创建的堆称为：main arena（主分配区），不同的线程维护不同的堆称为：per thread arena（线程分配区）

多线程管理

32位系统中：Number of arena = 2 * number of cores + 1.
64位系统中：Number of arena = 8 * number of cores + 1

当线程个数大于系统能维护的最大分配区个数，比如说一台只有一个核心处理器的机器要运行一个有四个线程的应用程序，那么glibc malloc就要确保4个线程能够正确地共享三个分配区。

• 首先，glibc malloc会遍历所有的可用分配区，遍历的过程中会尝试锁该分配区。当一个分配区对应的线程未使用堆内存则表示可锁。那么如果该分配区可锁，就可以直接被使用。
• 没找到的话，那么等待寻找的线程的malloc就会阻塞，直到有可以用的为止。
• 阻塞解除时，会先尝试使用最近访问的主分配区，如果可用那么就会直接使用，否则会再次阻塞。

如果没有主分配区，所有线程的操作都在主分配区上进行，互相竞争锁会影响分配效率。所以增加了非主分配区支持，使用环形链表管理主分配区和非主分配区，提高malloc的分配效率。申请小块内存时，ptmalloc在整理时会进行加锁的操作。线程很多时就会导致等待时间加长，性能下降。

heap_info

子线程的arena可以有多片连续内存，称为heap，每一个heap都有自己的heap header（堆信息结构体），heap header 是通过链表相连接的。

heap_info的作用是在线程申请内存时记录heap区域的信息，并且当该heap的资源被使用完之后，就必须要再次申请内存。一般来说，申请的heap是不连续的，因此需要记录不同heap之间的链接结构。

该数据结构是专门为从 Memory Mapping Segment 处申请的内存准备的，即为非主线程准备的。

主要结构：

#define HEAP_MIN_SIZE (32 * 1024)
#ifndef HEAP_MAX_SIZE
# ifdef DEFAULT_MMAP_THRESHOLD_MAX
#  define HEAP_MAX_SIZE (2 * DEFAULT_MMAP_THRESHOLD_MAX)
# else
#  define HEAP_MAX_SIZE (1024 * 1024) /* must be a power of two */
# endif
#endif

/* HEAP_MIN_SIZE and HEAP_MAX_SIZE limit the size of mmap()ed heaps
   that are dynamically created for multi-threaded programs.  The
   maximum size must be a power of two, for fast determination of
   which heap belongs to a chunk.  It should be much larger than the
   mmap threshold, so that requests with a size just below that
   threshold can be fulfilled without creating too many heaps.  */

/***************************************************************************/

/* A heap is a single contiguous memory region holding (coalesceable)
   malloc_chunks.  It is allocated with mmap() and always starts at an
   address aligned to HEAP_MAX_SIZE.  */

typedef struct _heap_info
{
  mstate ar_ptr; /* Arena for this heap. */
  struct _heap_info *prev; /* Previous heap. */
  size_t size;   /* Current size in bytes. */
  size_t mprotect_size; /* Size in bytes that has been mprotected
                           PROT_READ|PROT_WRITE.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

描述堆的基本信息，包括：

• 堆所属的arena地址
• 线程申请的堆用完后会再次申请，prev就记录了上一个heap_info的地址，可以看到每个heap_info是通过单向链表进行链接的。
• size为堆的大小
• 最后一部分对齐

malloc_state

记录每个arena当前申请的内存的具体状态，是否有空闲chunk或者空闲chunk大小为多少等等。无论是thread arena还是main arena都只有一个malloc state结构。主线程的arena保存在libc.so数据段里，其他线程的arena保存在给该arena分配的heap里。

struct malloc_state {
    /* Serialize access.  */
    __libc_lock_define(, mutex);

    /* Flags (formerly in max_fast).  */
    int flags;

    /* Fastbins */
    mfastbinptr fastbinsY[ NFASTBINS ];

    /* Base of the topmost chunk -- not otherwise kept in a bin */
    mchunkptr top;

    /* The remainder from the most recent split of a small request */
    mchunkptr last_remainder;

    /* Normal bins packed as described above */
    mchunkptr bins[ NBINS * 2 - 2 ];

    /* Bitmap of bins, help to speed up the process of determinating if a given bin is definitely empty.*/
    unsigned int binmap[ BINMAPSIZE ];

    /* Linked list, points to the next arena */
    struct malloc_state *next;

    /* Linked list for free arenas.  Access to this field is serialized
       by free_list_lock in arena.c.  */
    struct malloc_state *next_free;

    /* Number of threads attached to this arena.  0 if the arena is on
       the free list.  Access to this field is serialized by
       free_list_lock in arena.c.  */
    INTERNAL_SIZE_T attached_threads;

    /* Memory allocated from the system in this arena.  */
    INTERNAL_SIZE_T system_mem;
    INTERNAL_SIZE_T max_system_mem;
};

• glibc中的arena就是用该结构体表示的
• last_remainder：当次arena中产生last_remainder时，此成员被初始化，并且指向arena中的last_remainder
• bins数组：存储的是该领域管理的smallbins，unsortedbin，largebins
• binmap变量：系统查看有哪些垃圾箱链中有块时，不可能去fastbinsY和箱数组一个一个的遍历。通过binmap变量，采用二进制存储，将二进制位与数组的索引相对，系统查找箱链时可以通过按位与来查询，这样更高效。虽然unsigned int的二进制位比数组总元素少，但是系统不会有那么多的bin链，不需要考虑这个问题。

几个结构之间的关系

想象你正在组织一场音乐会，这个音乐会需要为观众提供座位。你是音乐会的经理，负责分配座位并管理这个过程。

• Arena（堆区）：音乐会大厅就像一个 Arena，代表整个音乐会场地。在这个大厅里，观众可以坐下，享受音乐会。
• Heap_info：音乐会大厅被划分成多个区域，每个区域都有一组座位。每个区域都由一个 Heap_info 结构来描述，其中包含了关于该区域的信息，比如座位数量、座位的位置等。每个 Heap_info 代表一个区域。
• Malloc_state：你是音乐会经理，负责管理每个区域的座位分配。你的助手是 Malloc_state，他帮助你记录哪些座位已经被分配，哪些还没有。他会维护一个详细的列表，以便在观众进入音乐会大厅时，能够快速找到一个合适的座位。
• Malloc_chunk：观众就像是需要座位的内存分配请求。每位观众需要一个座位（内存块），你的助手（Malloc_state）会根据已经分配的座位和空余的座位来分配给观众。已分配的座位（malloc_chunk）会被记录在 Malloc_state 中的列表中，以确保不会为同一个座位分配给多个观众。

参考

• 堆相关数据结构 - CTF Wiki (ctf-wiki.org)

• 基础操作 - CTF Wiki (ctf-wiki.org)

• 堆相关知识 (yuque.com)

• 堆漏洞挖掘:02—堆的glibc实现与Arena（struct malloc_state、struct _heap_info）_glibc thread arena-CSDN博客

• 《CTF实战 - 技术、解题与进阶》