bins 结构

fastbin

• 结构：单向链表
• 来源：free 时直接进入 fastbin
• 用途：快速分配和释放小块内存
• chunk size 范围：
  • 通常为 0x20 ~ 0x80（包含头部，具体范围随 glibc 版本变化，部分新版本为到 0x70）
  • size 字段实际为 chunk_size + 标志位
• 特点：
  • 释放后立即进入 fastbin，不合并相邻空闲块
  • 链表长度无限制（不是 7，7 是 tcache 的最大数目）
  • 只支持单向链表（每个 chunk 的 fd 指向下一个 chunk）

tcache

• 结构：单向链表
• 来源：free 时直接进入 tcache（优先于 fastbin）
• 用途：线程本地缓存，加速小块内存分配和释放
• chunk size 范围：
  • 仅支持小于等于 0x410（1040字节）的 chunk（包含头部，实际范围依 glibc 版本不同）
  • size 字段为 chunk_size + 标志位
• 特点：
  • 每个 size 类别最多存储 7 个 chunk（超出则进入 unsorted bin）
  • 不合并相邻空闲块
  • 只支持单向链表（每个 chunk 的 fd 指向下一个 chunk）
  • 属于线程本地数据结构，各线程 tcache 独立，提升多线程性能

unsorted bin

• 结构：双向链表（fd/bk）
• 来源：
  • 当一个较大的 chunk 被分割成两半后，如果剩下的部分大于 MINSIZE，就会被放到 unsorted bin 中。
  • 释放一个不属于 fast bin 的 chunk，并且该 chunk 不和 top chunk 紧邻时，该 chunk 会被首先放到 unsorted bin 中。关于 top chunk 的解释，请参考下面的介绍。
  • 当进行 malloc_consolidate 时，可能会把合并后的 chunk 放到 unsorted bin 中，如果不是和 top chunk 近邻的话。
• 用途：存放刚释放的非 fastbin chunk（大于 fastbin 范围）
• 特点：
  • 不按大小排序，先进后出（FIFO）
  • 后续 malloc 时会根据大小转移到 smallbin 或 largebin
  • 所有非 fastbin 的 chunk 释放时都先进入 unsorted bin

unsorted bin 转化

• malloc 请求触发归类
  当你 malloc 时，会优先在 unsorted bin 中查找是否有足够大的 chunk。
  如果 unsorted bin 中有 chunk 不足以分配请求的大小，这些 chunk 会被按大小归类，分别转移到 smallbin 或 largebin。
  chunk size ≤ smallbin 最大值，进入 smallbin
  chunk size > smallbin 最大值，进入 largebin
  这个过程中，所有遍历到但不满足分配条件的 chunk 都会被“搬家”到对应的 bin。

• free 时合并触发归类
  当你 free 一个不是 fastbin 范围的 chunk 时，如果它的前后相邻 chunk也是空闲的（即不是 fastbin chunk），ptmalloc2 会自动进行合并（consolidation）。
  合并后的新 chunk 会进入 unsorted bin。
  后续 malloc 时，unsorted bin 的 chunk 会被按上述规则转移到 smallbin 或 largebin。

smallbin

• 结构：双向循环链表
• 来源：从 unsorted bin 转移过来
• chunk size 范围：大于 fastbin 最大 size（通常为 0x90）到 0x400（含头部）
• 特点：
  • 每个 smallbin 存储相同大小的 chunk
  • 按大小分 bin，方便分配
  • 释放时支持合并相邻空闲块

largebin

• 结构：双向循环链表
• 来源：从 unsorted bin 转移过来
• chunk size 范围：大于 0x400
• 特点：
  • 按 chunk size 升序排列
  • 支持合并相邻空闲块

概览表

chunk -> if (size <= 0x400) tcache -> if (size <= 0x80) fastbin -> if (0x80 <= size <= 0x400) unsorted bin -> 后续转 smallbin 或 largebin

main_arena

main_arena 是 glibc 堆管理的核心结构之一，属于 malloc_state 结构体的一个实例。它记录了堆分配器的各种数据，包括所有 bin 的链表头指针、堆空间的边界、锁等，是 glibc 堆分配的“大本营”。

结构与作用

• 在 glibc 2.23 及以前，整个进程的堆只用一个 main_arena 管理。
• glibc 2.24 及以后，为了提升多线程性能，引入了多个 arena，每个线程可能拥有独立的 arena，但主线程始终用 main_arena。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

struct malloc_state
{
  /* Serialize access.  */
  mutex_t 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 */
  unsigned int binmap[BINMAPSIZE];
  /* Linked list */
  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;
};

• fastbinsY：fastbin 的链表头数组
• top：当前堆空间的顶部 chunk（未分配区域）
• last_remainder：最近一次分配后剩余的 chunk
• bins：smallbin/largebin/unsorted bin 的链表头数组
• binmap：bin 使用状态的位图
• next：多 arena 时指向下一个 arena
• next_free：空闲 arena 的链表
• attached_threads：当前 arena 绑定的线程数
• system_mem：当前 arena 分配的总内存
• max_system_mem：arena 分配的最大内存限制

申请大小修正

在 glibc 的 malloc 实现中，实际分配的 chunk 大小会通过内部宏进行对齐和修正，确保满足堆管理元数据和内存对齐的要求。常见宏如下：

1
2
3
4
5
6

/* pad request bytes into a usable size -- internal version */

#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

解释

• SIZE_SZ：chunk 头部元数据占用的字节数（通常为 8 字节，即 size_t）。
• MALLOC_ALIGN_MASK：用于内存对齐的掩码（比如 0xf，保证 16 字节对齐）。
• MINSIZE：最小 chunk 大小（一般为 0x20）。

整体流程

1. 加上头部和对齐字节：req + SIZE_SZ + MALLOC_ALIGN_MASK
2. 和最小大小比较：如果不足最小 chunk 大小，则用 MINSIZE
3. 否则按对齐掩码进行对齐：保证分配的 chunk 满足堆管理及 CPU 对齐要求

示例

假如申请 1 字节，实际分配会变成：

1
2
3

request2size(1) = ((1 + 8 + 15) < 32) ? 32 : ((1 + 8 + 15) & ~15)
               = (24 < 32) ? 32 : (24 & ~15)
               = 32

也就是最小 chunk 大小。

consolidation（合并）机制

ptmalloc2/glibc 堆管理器在释放 chunk 时，会自动检测相邻 chunk 是否空闲，并合并以减少碎片：

• fastbin：释放后不立即合并，等到 malloc_consolidate() 或下一次非 fastbin 分配时再统一合并。
• unsorted bin / smallbin / largebin：释放时即合并相邻空闲 chunk，合并后的新 chunk 会进入 unsorted bin，后续再分类进 smallbin/largebin。

top chunk

top chunk 是当前堆空间最后一个未分配的 chunk：

• 每次 malloc 时，若没有合适的空闲块，会从 top chunk 切割一块出去。
• 当 top chunk 空间不足时，ptmalloc2 会调用 sbrk 或 mmap 扩展堆。
• top chunk 不在任何 bin 链表中，单独管理。