堆基础

堆

堆（heap）是一种数据结构，在程序运行的过程中，堆可以提供动态分配的内存，允许程序申请大小未知的内存

堆是程序虚拟地址空间中的一块连续的线性区域，它由低地址向高地址方向增长（和栈的增长方向相反），管理堆的程序也称为堆管理器

参考文章：

1. 堆概述 - CTF Wiki
2. 狼组安全团队公开知识库

目前 Linux 标准发行版中使用的堆分配器是 Glibc 中的堆分配器：ptmalloc2

堆的基本操作是分配和回收，ptmalloc2 主要通过 malloc() 和 free() 函数来分配和释放内存块

---

堆的基本操作

malloc

函数声明：void *malloc(size_t size)

size 是内存块的大小，以字节为单位

malloc() 的作用是分配所需的内存空间（不会对内存空间进行初始化），并返回一个指向它的指针；如果请求失败，则返回 NULL

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

• 当 size 为负数时，由于在大多数系统上，size_t 是无符号数（这一点非常重要），所以程序就会申请很大的内存空间，但通常来说都会失败，因为系统没有那么多的内存可以分配

以一个简单的例子来看看 malloc() 函数和堆：

#include<stdio.h>
#include<stdlib.h>

int main()
{
    void *ptr = malloc(0x10);
    free(ptr);
    return 0;
}

通过 GDB 调试可以看到，在执行 malloc() 函数前，程序的地址空间里是没有堆的：

执行 malloc() 函数后：

可见程序中最开始是没有堆这部分空间的，在用户通过 malloc() 申请内存后才会出现，并且会一次性申请很大空间的堆段（0x555555559000 ~ 0x55555557a000）

注意：新版本的 Glibc 对堆结构的管理有些区别，上图是在 Glibc 2.37 的 Kali Linux 2024.1 中进行的测试

而在 Glibc 2.23 的 Ubuntu 16.04 中是这样的：

---

calloc

函数声明：void *calloc(size_t nitems, size_t size)

nitems 为要被分配的元素个数；size 为元素的大小

calloc() 在功能上与 malloc() 几乎相同，区别在于 calloc() 申请内存空间后会将其全部初始化为 0

使用 calloc() 函数时需要注意，如果分配的内存块过大，可能会导致内存不足的问题

---

realloc

函数声明：void *realloc(void *ptr, size_t size)

ptr 是一个指向要重新分配内存的内存块的指针；size 是内存块的新的大小，以字节为单位

realloc() 的作用是重新调整之前通过 malloc() 或 calloc() 所分配的 ptr 所指向的内存块的大小，并返回一个指向重新分配大小的内存的指针；如果请求失败，则返回 NULL

• 如果 ptr 为空指针，则会分配一个新的内存块，且函数返回一个指向它的指针，相当于 malloc()

• 如果 size = 0，且 ptr 指向一个已存在的内存块，则 ptr 所指向的内存块会被释放，并返回一个空指针，相当于 free()

另外，针对重新申请的大小与之前申请内存的大小的关系，又有三种不同的情况：

1. 如果重新申请的大小 > 之前申请内存的大小，且当前内存段后面有需要的内存空间，则直接扩展这段内存空间，realloc() 将返回原指针

2. 如果重新申请的大小 > 之前申请内存的大小，且当前内存段后面的空闲空间不够，那么就使用堆中的第一个能够满足这一要求的内存块，将目前的数据复制到新的位置，并将原来的数据块释放掉，返回新的内存块地址，相当于 free() + malloc()

3. 如果重新申请的大小 < 之前申请内存的大小，堆块会直接缩小，被削减的内存会释放，这里的释放与 free() 不同

---

free

函数声明：void free(void *ptr)

ptr 是一个指向要释放内存的内存块的指针

free() 的作用是释放之前通过 malloc()、calloc() 或 realloc() 所分配的内存空间，该函数不返回任何值

• 如果传递的参数 ptr 是一个空指针，则不会执行任何动作

• 当参数 ptr 已经被释放之后，再次释放会出现乱七八糟的效果（Double Free）

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

还是以上面的例子来看，执行 free() 之后堆段并不会消失：

但是堆中的内容发生了变化：

我们申请的空间变成了 Free chunk

注意：新版本的 Glibc 对堆结构的管理有些区别，上图是在 Glibc 2.37 的 Kali Linux 2024.1 中进行的测试

而在 Glibc 2.23 的 Ubuntu 16.04 中是这样的：

通过 free() 释放的堆块不会立刻被回收，它们会变成 Free chunk 并加上了一种 xxx bin 的名字，例如上图 Glibc 2.23 中的 fastbins（fast bin）

通常来说，当堆块释放后，如果与另一个被释放的堆块或者 top chunk 相邻，则这些空间会被合并（但是 fast bin 是个特例，不会轻易合并）

---

内存分配背后的系统调用

无论是 malloc 函数还是 free 函数，我们动态申请和释放内存时，都经常会使用，但是它们并不是真正与系统交互的函数

这些函数背后的系统调用主要是 brk 函数以及 mmap 函数

1. brk 是将 DATA 数据段的最高地址指针 _edata 往高地址推（_edata 指向数据段的最高地址）

2. mmap 是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存

brk 和 mmap 这两种方式分配的都是虚拟内存，没有分配物理内存

在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系

• malloc 小于 128k（0x20000 字节）的内存时，使用 brk 分配内存
• malloc 大于等于 128k（0x20000 字节）的内存时，使用 mmap 分配内存，在堆和栈之间找一块空闲内存分配

第一次执行 malloc 可能出现的系统调用如下：

注意：

brk 会直接拓展原来的堆，mmap 会单独映射一块内存

mmap 分配的内存与 libc 基地址之前存在固定的偏移，因此可以推算出 libc 的基地址

---

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 填充的内存，并且这块内存仅被调用进程所使用

• 在执行 mmap 之前，只有 .so 文件的 mmap 段
• 执行 mmap 之后，我们申请的内存与已经存在的内存段结合在了一起，构成了新的 mmap 段

---

堆的结构

微观结构

malloc_chunk

chunk 也叫块，在内存中表示的意思就是一块内存，这块内存在 ptmalloc2 内部用 malloc_chunk 结构体来表示

在程序的执行过程中，我们称由 malloc() 申请的内存为 chunk，chunk 也是堆的最小操作单元

参考文章：堆相关数据结构 - CTF Wiki

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;
};

一些参数的解释：

• prev_size

  1. 如果该 chunk 的物理相邻的前一地址 chunk（两个指针的地址差值为前一个 chunk 的大小）是空闲的话，那么 prev_size 记录的是前一个 chunk 的大小（包括 chunk 头）

  2. 否则，prev_size 可以用来存储物理相邻的前一个 chunk 的数据。这里的前一个 chunk 指的是较低地址的 chunk

• size

  1. size 表示该 chunk 的大小，大小必须是 2 * SIZE_SZ 的整数倍。如果申请的内存大小不是 2 * SIZE_SZ 的整数倍，会被转换成满足大小的最小的 2 * SIZE_SZ 的倍数

  2. 32 位系统中，SIZE_SZ 是 4；64 位系统中，SIZE_SZ 是 8。 该字段的低三个比特位对 chunk 的大小没有影响，它们从高到低分别表示

  3. 一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存；当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并

参数	意义
（A）NON_MAIN_ARENA	记录当前 chunk 是否不属于主线程，1 表示不属于，0 表示属于
（M）IS_MAPPED	记录当前 chunk 是否是由 mmap 分配的
（P）PREV_INUSE	记录前一个 chunk 块是否被分配，0 表示空闲，1 表示使用中

• fd、bk

  1. chunk 处于分配状态时，从 fd 字段开始是用户的数据。chunk 空闲时，会被添加到对应的空闲管理链表中

  2. 通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理

参数	意义
fd	指向下一个（非物理相邻）空闲的 chunk
bk	指向上一个（非物理相邻）空闲的 chunk

• fd_nextsize、bk_nextsize

  1. 只有 chunk 空闲的时候才使用，不过其用于较大的 chunk（large chunk）

  2. 一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历

参数	意义
fd_nextsize	指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针
bk_nextsize	指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针

注意：

无论一个 chunk 的大小如何，处于分配状态还是释放状态，它们都使用一个统一的结构

虽然在分配状态和释放状态下，chunk 都是同一个数据结构，但是它们的表现形式是不一样的

• chunk 处于分配状态（Allocated chunk）：

前两个字段称为 chunk header，后面的部分称为 user data

每次 malloc 申请得到的内存指针，其实指向 user data 的起始处

chunk 中的空间复用：

当一个 chunk 处于使用状态时，它的下一个 chunk 的 prev_size 域无效，所以下一个 chunk 的该部分也可以被当前 chunk 使用

• chunk 处于释放状态（Freed chunk）（可能是循环双向链表，也可能是单向链表）：

如果一个 chunk 处于 free 状态，那么会有两个位置记录其相应的大小：

1. 该 chunk 本身的 size 字段会记录
2. 该 chunk 后面的一个 chunk 会记录

堆管理器会通过 prev_size 字段以及 size 字段合并两个物理相邻的空闲 chunk 块

---

top chunk

程序第一次进行 malloc 的时候，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk，简而言之，**top chunk 就是处于当前堆的物理地址最高的 chunk**

top chunk 不属于任何一个 bin，它的作用在于：

1. 当所有的 bin 都无法满足用户请求的大小时，如果 top chunk 不小于用户请求的大小，就从 top chunk 中进行分配，并将剩下的部分作为新的 top chunk
2. 否则，就对 heap 进行扩展后再进行分配（在 main arena 中通过 sbrk 扩展 heap，而在 thread arena 中通过 mmap 分配新的 heap）

• 初始情况下，可以将 unsorted chunk 作为 top chunk
• top chunk 的 PREV_INUSE 位始终为 1（否则其前面的 chunk 就会被合并到 top chunk 中）

---

last remainder chunk

在用户使用 malloc 请求分配内存时，ptmalloc2 找到的 chunk 可能并不和申请的内存大小一致，这时候就将分割之后的剩余部分称之为 last remainder chunk

• unsorted bin 也会存这一块
• top chunk 分割剩下的部分不会作为 last remainder

---

宏观结构

arena

无论是主线程还是新创建的线程，在第一次申请内存时，都会有独立的 arena，arena 就是用来管理线程中的这些堆的，也可以理解为堆管理器所持有的内存池

• 一个线程只有一个 arnea，并且这些线程的 arnea 都是独立的不是相同的

但也不是每一个线程都会有对应的 arena，对于不同系统，arena 数量的约束如下：

For 32 bit systems:
     Number of arena = 2 * number of cores.
For 64 bit systems:
     Number of arena = 8 * number of cores.

因为每个系统的核数是有限的，当线程数大于核数的二倍（超线程技术）时，就必然有线程处于等待状态，所以没有必要为每个线程分配一个 arena

• 主线程的 arnea 称为 main_arena，子线程的 arnea 称为 thread_arena

• 主线程无论一开始 malloc 多少空间，只要 size < 128KB，kernel 都会分配 132KB 具有读写权限的 heap segment，这部分称为 main_arena

例如这张图中：

heap segment 地址为 0x555555559000 ~ 0x55555557a000，具有 rw 权限，总共：(0x55555557a000 - 0x555555559000)B / 1024 = 132KB

注意：

main_arena 并不在申请的 heap 中，而是一个全局变量，在 libc.so 的数据段中

后续申请的内存会一直从这个 arena 中获取，直到空间不足

当 arena 空间不足时，它可以通过增加 brk 的方式来增加堆的空间；类似地，arena 也可以通过减小 brk 来缩小自己的空间

即使将所有 main_arena 所分配出去的内存块 free 完，也不会立即还给 kernel，而是交由 Glibc 来管理。当后面程序再次申请内存时，在 Glibc 中管理的内存充足的情况下，Glibc 就会根据堆分配的算法来给程序分配相应的内存

---

heap_info

程序刚开始执行时，每个线程是没有 heap 区域的。当其申请内存时，就需要 heap_info 这个结构来记录对应的信息

当该 heap 的资源被使用完后，就必须得再次申请内存了。此外，一般申请的 heap 是不连续的，因此需要记录不同 heap 之间的链接结构

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

• 主线程可以通过 sbrk() 函数扩展 program break location 获得（直到触及 Memory Mapping Segment），只有一个 heap，没有 heap_info 数据结构

heap_info 的主要结构如下：

#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 表示当前堆的大小
• pad 确保分配的空间是按照 MALLOC_ALIGN_MASK + 1 对齐的

---

malloc_state

malloc_state 结构用于管理堆，记录每个 arena 当前申请的内存的具体状态，例如：是否有空闲 chunk，空闲 chunk 的大小等等

• 无论是 thread_arena 还是 main_arena，它们都只有一个 malloc state 结构
• 由于 thread 的 arena 可能有多个，malloc state 结构会在最新申请的 arena 中

malloc_state 的结构如下：

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;
};

• libc_lock_define(, mutex)
  该变量用于控制程序串行访问同一个分配区，当一个线程获取了分配区之后，其它线程要想访问该分配区，就必须等待该线程分配完成后才能够使用。
• flags
flags 记录了分配区的一些标志，比如 bit0 记录了分配区是否有 fast bin chunk，bit1 标识分配区是否能返回连续的虚拟地址空间。具体如下：

/*
   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.
 */

#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.
 */

#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)

• fastbinsY[NFASTBINS]
  存放每个 fast chunk 链表头部的指针
• top
  指向分配区的 top chunk
• last_reminder
  最新的 chunk 分割之后剩下的那部分
• bins
  用于存储 unstored bin，small bin 和 large bin 的 chunk 链表
• binmap
ptmalloc2 用 1 个 bit 来标识某一个 bin 中是否包含空闲 chunk

注意：

main_arena 的 malloc_state 并不是 heap segment 的一部分，而是一个全局变量，存储在 libc.so 的数据段

---

bin 的种类

Glibc 为了让 malloc 可以更快找到合适大小的 chunk，用户 free 释放掉的 chunk 不会马上归还给系统，而是将该 chunk 根据大小加入到合适的 bin 中

当用户再一次通过 malloc 请求分配内存时，ptmalloc2 会试图在空闲的 chunk 中挑选一块合适的空间给用户，这样可以避免频繁的系统调用，降低内存分配的开销

bin 的中文意思为垃圾桶，就像要删除的文件会先放入 Windows 的回收站一样不会立即删除，很生动形象了

ptmalloc2 会根据空闲的 chunk 的大小以及使用状态，将 chunk 初步放入相应的 bin 中，bin 的种类主要分为：

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

Glibc 提供了两个数组：fastbinsY[] 和 bins[] 用来存放这些 bin

具体来说，可分为：

• 10 个 fast bin，存储在 fastbinsY[] 中
• 1 个 unsorted bin，存储在 bins[1] 中
• 62 个 small bin，存储在 bins[2] 至 bins[63] 中
• 63 个 large bin，存储在 bins[64] 至 bins[126] 中

其中虽然定义了 bins[128]，但是 bins[0] 和 bins[127] 其实是不存在的

chunk 在 bin 上以链表的形式存放：（fast bin 是单链表，其他的 bin 都是双链表）

---

fast bin

fast bin 非常像高速缓存 cache，为了减少一些较小的 chunk 在合并、分割以及中间检查的过程中的开销，ptmalloc2 中专门设计了 fast bin，对应的变量就是 malloc state 中的 fastbinsY[] 数组，用于提高小内存分配效率

• fast bin 存储在 fastbinsY[] 处，是 10 个单链表（最后 3 个链表保留未使用）
• fast bin 的 chunk 大小（含 chunk 头部）为：16 ~ 64 字节（64 位为 32 ~ 128 字节）
• 相邻 bin 存放的大小相差 8 字节（64 位为 16 字节）
• 采取 LIFO 策略（最近释放的 chunk 会更早地被分配）
• chunk 的 PREV_INUSE 位（下一个物理相邻的 chunk 的 P 位）总为 1，释放到 fastbin 的 chunk 不会被清除 PREV_INUSE 标志位

如果遇到以下两种情况，ptmalloc2 会首先判断 fast bin 中相应的 bin 中是否有对应大小的空闲块，如果有的话，就会直接从这个 bin 中获取 chunk；如果没有的话，ptmalloc2 才会做接下来的一系列操作：

• 在 32 位系统中（SIZE_SZ = 4），用户需要的 chunk 大小 < 64 字节
• 在 64 位系统中（SIZE_SZ = 8），用户需要的 chunk 大小 < 128 字节

关于 fast bin 的大小定义如下：

#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)

在 32 位系统中，fast bin 默认支持最大的 chunk 的数据空间大小为 64 字节：

DEFAULT_MXFAST = (64 * 4 / 4) = 64

但是其可以支持的 chunk 的数据空间最大为 80 字节：

MAX_FAST_SIZE = (80 * 4 / 4) = 80

fast bin 最多可以支持的 bin 的个数为 10 个，在 32 位系统中，用户数据空间从第 8 字节开始一直到第 80 字节（不包括 prev_size 和 size 字段的 8 字节）

注意：

fast bin 中的 chunk 的 PREV_INUSE 位（下一个物理相邻的 chunk 的 P 位）始终被置为 1，因此它们不会和其它被释放的 chunk 合并，这也是为什么前面说 fast bin 是个特例，不会轻易合并

但是，当释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后的大小 > FASTBIN_CONSOLIDATION_THRESHOLD 时，说明内存碎片较多，此时就需要把 fast bin 中的 chunk 都进行合并，以减少内存碎片对系统的影响

---

unsorted bin

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

大小超过 fast bin 阈值的 chunk 被释放时会加入到这里，这使得 ptmalloc2 可以复用最近释放的chunk，从而提升效率

• unsorted bin 处于 bins[1] 处，因此 unsorted bin 只有 1 个双向循环链表
• unsorted bin 中的空闲 chunk 处于乱序状态
• **unsorted bin 在使用的过程中，采用的遍历顺序是 FIFO**（插入的时候插入到 unsorted bin 的头部，取出的时候从链表尾获取）
• 在 malloc 分配时，如果在 fast bin、small bin 中找不到对应大小的 chunk，就会尝试从 unsorted bin 中寻找 chunk。如果取出来的 chunk 大小刚好满足，就会直接返回给用户；如果在 unsorted bin 中没有合适的 chunk，就会把 unsorted bin 中的所有 chunk 分别加入到所属的 bin 中，然后再在 bin 中分配合适的 chunk

当 free 的 chunk 大小 >= 144 字节时，为了效率，Glibc 并不会马上将 chunk 放到相对应的 bin 中，而会先放到 unsorted bin

下次 malloc 时会先查找 unsorted bin 中是否有合适的 chunk，找不到才会去对应的 bin 中寻找，此时会顺便把 unsorted bin 的 chunk 放到对应的 bin 中，但 small bin 除外，为了效率，反⽽先从 small bin 找

---

small bin

chunk size 小于 0x200 字节（64 位为 0x400 字节）的 chunk 叫做 small chunk，而 small bin 存放的就是这些 small chunk

• small bin 存储在 bins[2] 至 bins[63] 处，是 62 个双向循环链表（每个链表都有链表头结点，这样可以方便对于链表内部结点的管理）
• fast bin 的 chunk 大小（含 chunk 头部）为：16 ~ 496 字节（64 位为 32 ~ 1008 字节）
• 相邻 bin 存放的大小相差 8 字节（64 位为 16 字节）
• 每个链表中存储的 chunk 大小都一致
• 采取 FIFO 策略（最近释放的 chunk 会被最后分配），这点和 fast bin 相反
• 同样与 fast bin 相反的是：相邻的空闲 chunk 会被合并

small bin 中每个 chunk 的大小与其所在的 bin 的 index 的关系为：

chunk_size = 2 * SIZE_SZ * index

small bin 的大小再分成 62 个 bin，大小从 16 字节（64 位为 32 字节）开始，每次固定增加 8 字节（64 位为 16 字节）：

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

注意：

fast bin 中的 chunk 是有可能被放到 small bin 中去的

---

large bin

large bin 存放的是大于等于 0x200 字节（64 位为 0x400 字节）的 chunk

• large bin 存储在 bins[64] 至 bins[126] 处，是 63 个双向循环链表
• 每个 bin 中的 chunk 的大小不一致（按大小降序排列）
• 采取 FIFO 策略
• 插入和删除可以发生在任意位置
• 相邻空闲 chunk 会被合并

large bin 的 freed chunk 会多两个指针 fd_nextsize、bk_nextsize，分别指向前一块和后一块 large chunk

large bin 的大小再分成 63 个 bin，但大小不再是固定大小增加，而是按照公差分为 6 组：

组	bin 的数量	公差
1	32	0x40
2	16	0x200
3	8	0x1000
4	4	0x8000
5	2	0x40000
6	1	不限制，大小和 large bin 剩余的大小相同

---

tcache

tcache 是 libc2.26（Ubuntu 17.10）之后引进的一种新机制，类似于 fast bin 一样的东西，目的是提升堆管理的性能，但提升性能的同时舍弃了很多安全检查，也因此有了很多新的利用方式

• 每条链上最多可以有 7 个 chunk
• malloc 的时候优先去 tcache 找
• free 的时候当 tcache 满了才放入 fastbin 或 unsorted bin

基本工作方式：

• malloc 时，会先 malloc 一块内存用来存放 tcache_perthread_struct

• free 内存，且 size 小于 small bin size 时

  1. 先放到对应的 tcache 中，直到 tcache 被填满（默认是 7 个）
  2. tcache 被填满之后，再次 free 的内存和之前一样被放到 fast bin 或者 unsorted bin 中
  3. tcache 中的 chunk 不会合并（不取消 PREV_INUSE 位）

• malloc 内存，且 size 在 tcache 范围内

  1. 先从 tcache 取 chunk，直到 tcache 为空
  2. tcache 为空后，从 bin 中找
  3. tcache 为空时，如果 fast bin、small bin、unsorted bin 中有 size 符合的 chunk，会先把 fast bin、small bin、unsorted bin 中的 chunk 放到 tcache 中，直到填满；之后再从 tcache 中取；因此 chunk 在 bin 中和 tcache 中的顺序会反过来

---