堆中的bin
2026-03-12 10:20:23 #Heap #bins # 二进制安全

bin是什么？

在 Glibc 的 ptmalloc 分配器中，Bin 是用于管理空闲内存块（Free Chunk）的核心数据结构。

从实现角度来看，Bin 并非物理容器，而是维护在 malloc_state（也称为 Arena）结构体中的指针数组。这些指针指向由空闲 Chunk 组成的链表（Linked List）。

当用户通过 free() 释放内存时，分配器会根据 Chunk 的大小将其插入（Link）到对应的 Bin 链表中；当用户 malloc() 时，分配器从 Bin 中取出（Unlink）合适的 Chunk 并返回给用户。

Malloc_state

在 glibc 的内存管理器（ptmalloc）中，malloc_state 是一个至关重要的结构体，它被通俗地称为 Arena（分配区）。

简单来说，malloc_state 记录了一个分配区内所有内存管理的核心信息，包括空闲块的链表、Top Chunk 的位置以及统计数据。

glic-2.35的malloc_state结构体源代码[1]如下：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);

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

  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;

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

Arena的分类：主和从

在一个多线程程序中，为了减少锁竞争，glibc 会创建多个 Arena：

（1）Main Arena (主分配区): 进程中只有一个。它直接管理通过 sbrk（堆区扩展）和 mmap 分配的内存。它是一个全局变量。

（2）Thread Arena (从分配区): 当多个线程竞争内存分配时，glibc 会为新线程创建额外的 Arena。这些从分配区主要通过 mmap 分配的一块被称为 heap_info 的大内存中切分。

malloc_state核心结构解析

以下是 malloc.c 中该结构体的主要成员及其功能：

成员名称 功能描述
mutex 互斥锁。每个 Arena 都有自己的锁，保证在多线程环境下对该分配区的操作是原子性的。
fastbinsY Fast Bins 数组。存储小块内存（16B-80B）的单向链表头指针。
top Top Chunk 指针。指向当前 Arena 顶部的空闲空间，如果所有 Bin 都找不到合适的块，就从这里切割。
last_remainder 剩余块指针。当一个小的申请从一个大的空闲块中切出后，剩余部分如果不能进 Bin，就存放在这里以备下次快速分配。
bins 常规 Bins 数组。存储 Unsorted Bin、Small Bins 和 Large Bins 的双向链表。
binmap 位图。用于快速查找哪个 Bin 索引下存在空闲块，提高搜索效率。
next 链表指针。将进程中所有的 malloc_state 实例连接成一个循环链表，方便分配器寻找空闲的 Arena。
system_mem 统计量。记录该 Arena 从系统中获取的总内存量。

工作流程概览

当你调用 malloc(size) 时，分配器会经历以下关于 malloc_state 的查找过程：

（1）寻找 Arena: 线程首先尝试获取它最后一次使用的那个 Arena 的锁。如果被占用，它会遍历 Arena 链表（通过 next 指针）寻找一个未上锁的。

（2）检查 Fastbins: 如果申请的大小属于 Fast Bin 范围，直接查看 fastbinsY 数组。

（3）检查 Bins: 如果 Fast Bin 没命中，则查找 bins 数组（Unsorted -> Small -> Large）。

（4）使用 Top Chunk: 如果所有 Bin 都空了，则计算 top 指针指向的剩余空间。

（5）系统调用: 如果连 Top Chunk 都不够了，则通过 sbrk (Main Arena) 或 mmap (Thread Arena) 向内核申请更多物理内存。

安全意义

在二进制漏洞利用中，malloc_state 对于攻击者来说非常重要。

  • libc 地址泄露: 由于 main_arena 是 libc.so 中的一个全局变量，泄露了 malloc_state 的地址（比如泄露了 Unsorted Bin 的指针）就能绕过 ASLR，计算出 libc 的基地址。
  • 控制流篡改: 攻击者通过堆溢出伪造 malloc_state 中的指针，可以诱导 malloc 返回任意地址（如栈地址或 GOT 表地址），实现任意代码执行。

核心单元：malloc_chunk

Bin管理的对象是malloc_chunk。理解其字段是理解 Bin 运作机制的前提。

1
2
3
4
5
6
7
8
9
10
11
struct malloc_chunk {
  INTERNAL_SIZE_T      mchunk_prev_size;  /* 前一 Chunk 大小（仅当前一 Chunk 空闲时有效） */
  INTERNAL_SIZE_T      mchunk_size;       /* 当前 Chunk 大小（包含 AMP 标志位） */

  struct malloc_chunk* fd;                /* Forward pointer: 指向链表中下一个 Chunk */
  struct malloc_chunk* bk;                /* Backward pointer: 指向链表中上一个 Chunk */

  /* 仅用于 Large Bin 的扩展字段 */
  struct malloc_chunk* fd_nextsize;       /* 指向下一个不同大小的 Chunk */
  struct malloc_chunk* bk_nextsize;       /* 指向前一个不同大小的 Chunk */
};

复用机制： 这里的 fd、bk 等指针仅在 Chunk 处于 Free（空闲） 状态并存在于 Bin 中时才有意义。当 Chunk 被分配给用户时，这些内存空间被用作 User Data。

Bin的分类与数据结构特性

ptmalloc 根据 chunk 的大小（Size）和操作策略（Policy），将 Bin 划分为四类。

Fast Bins、Unsorted Bin、Small Bins、Large Bins。

Fast Bins

这是为了优化小内存分配性能而设计的结构。

  • 数据结构： 单向链表 (Singly Linked List)。
  • 存储位置： malloc_state.fastbinsY 数组。
  • 操作策略： LIFO (Last In, First Out)。最近释放的 chunk 会被插入链表头部，下次申请时最先被取出。
  • 合并策略 (Coalescing)： 不执行合并。即使两个 Fast Bin chunk 物理相邻，它们也不会合并成一个更大的 chunk。这通过保持 chunk 的 P (PREV_INUSE) 标志位为 1 来实现。
  • 范围： 默认覆盖 16 到 80 字节（32位系统）或 16 到 160 字节（64位系统），具体取决于 SIZE_SZ。
  • 技术细节： 由于是单向链表，Fast Bin chunk 只有 fd 指针指向下一个节点，bk 指针无定义。

image-20260202234907703

Unsorted Bin

这是 chunk 被释放后的第一个缓冲区，也是唯一的非分类容器。

  • 数据结构： 双向环形链表 (Doubly Linked Circular List)。
  • 存储位置： malloc_state.bins[1]。
  • 功能逻辑： 当一个 chunk 被释放（且大小超出 Fast Bin 范围）时，它首先被插入 Unsorted Bin 的头部。
  • 遍历逻辑： 在 malloc 过程中，如果 Fast Bin 无法满足请求，分配器会遍历 Unsorted Bin。在遍历过程中，分配器会将每个遇到的 chunk 重新分类（Resort） 并放入对应的 Small Bin 或 Large Bin 中。
  • 利用价值： 利用了时间局部性原理。如果程序释放了一个 chunk 随后立即申请相同大小的 chunk，可以直接从这里复用，避免了复杂的查找逻辑。

image-20260203014103804

Small Bins

用于管理固定大小的中小块内存，采用精确匹配策略。

  • 数据结构： 双向环形链表。
  • 存储位置： malloc_state.bins[2] 到 malloc_state.bins[63]。
  • 大小映射： 每个 Small Bin 对应一个精确的固定大小，步长为 16 字节。例如，Bin 2 存储 32 字节，Bin 3 存储 48 字节，依此类推。
  • 操作策略： FIFO (First In, First Out)。插入到头部，从尾部摘取。
  • 合并策略： 不执行合并。Small Bins 中的 chunk 都是固定大小的，相邻的空闲 chunk 不会被合并，它们保持各自独立的状态。这样可以确保分配时的效率，避免额外的合并开销。

Small Bins 结构示意图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
malloc_state.bins[] 数组:
  bins[0]: (未使用)
  bins[1]: Unsorted Bin
  bins[2]: Small Bin 2 (32字节) → [Chunk A] ↔ [Chunk B] ↔ [Chunk C] ↔ (环回)
  bins[3]: Small Bin 3 (48字节) → [Chunk D] ↔ [Chunk E] ↔ (环回)
  bins[4]: Small Bin 4 (64字节) → [Chunk F] ↔ (环回)
  bins[5]: Small Bin 5 (80字节) → (空)
  ...
  bins[63]: Small Bin 63 (1008字节)

详细的双向环形链表结构:
Small Bin 2 (32字节):
  HEAD → Chunk A ↔ Chunk B ↔ Chunk C → BACK
         ↑                           ↓
         └───────────────────────────┘
         (环形链表)

FIFO 操作示意:
初始状态: HEAD → [A] ↔ [B] ↔ [C] → BACK
插入新chunk D: HEAD → [D] ↔ [A] ↔ [B] ↔ [C] → BACK  (插入头部)
摘取chunk: HEAD → [D] ↔ [A] ↔ [B] → BACK, 返回 [C]  (从尾部摘取)

Large Bins

用于管理大块内存，支持范围分配和最佳匹配策略。

  • 数据结构： 双向环形链表 + 跳表逻辑 (Skip-list logic)。
  • 存储位置： malloc_state.bins[64] 到 malloc_state.bins[126]。
  • 大小映射： 范围映射 (Range Mapping)。每个 Large Bin 存储一定范围大小的 chunks。例如，Bin 64 存储 1024 字节及以上的 chunk（具体范围取决于复杂的计算公式）。
  • 排序机制： 链表中的 chunk 按照大小（Size）从大到小排序。
  • 性能优化： 为了避免在长链表中线性查找合适的大小，Large Bin chunk 使用了 fd_nextsize 和 bk_nextsize 字段。这两个指针构成了一个子链表，仅连接大小不同的 chunk。这允许分配器快速跳过相同大小的 chunk，直接定位到满足大小需求的 chunk。

Large Bins 结构示意图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
malloc_state.bins[] 数组 (Large Bins 部分):
  bins[64]: Large Bin 64 → [Chunk A(2048B)] ↔ [Chunk B(1536B)] ↔ [Chunk C(1024B)] ↔ (环回)
  bins[65]: Large Bin 65 → [Chunk D(3072B)] ↔ [Chunk E(2560B)] ↔ (环回)
  bins[66]: Large Bin 66 → (空)
  ...
  bins[126]: Large Bin 126 → [Chunk Z(大尺寸)] ↔ (环回)

双向链表 + 跳表结构详细示意:
Large Bin 64:
  主链表 (fd/bk):    [2048B] ↔ [1536B] ↔ [1024B]  (按大小降序)
  跳表链表 (fd_nextsize/bk_nextsize): 
                     [2048B] → [1536B] → [1024B]  (仅连接不同大小)

跳表工作原理:
查找 1500B chunk 时:
  [2048B] → 太大，跳到 [1536B] → 太大，跳到 [1024B] → 太小
  最终选择最合适的 [1536B] 进行分割

现代架构补充：Tcache（Thread Local Cache）

自 Glibc 2.26 版本引入，Tcache 位于 malloc_state 之外，是线程私有的堆缓存结构。

  • 并发控制： 无锁 (Lock-free)。每个线程拥有独立的 tcache_perthread_struct，通过线程局部存储 (TLS) 实现，完全避免锁竞争。
  • 数据结构： 单向链表，LIFO 策略（结构上类似 Fast Bin，但独立于 Fast Bin）。
  • 优先级： 最高。malloc 时最先检查 Tcache，free 时最先放入 Tcache。
  • 限制： 有容量限制（默认每个 size 链表最多存 7 个 chunk，可通过 tcache_count 宏调整）。
  • 尺寸范围： 覆盖小块内存（24-1032字节，64位系统），与 Fast Bin 部分重叠但优先级更高。

Tcache 结构示意图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
线程私有 Tcache (tcache_perthread_struct):
  counts[TCACHE_MAX_BINS]: 记录每个bin中的chunk数量

  entries[TCACHE_MAX_BINS]: 单向链表数组
    entries[0]: 24字节 → [Chunk A] → [Chunk B] → [Chunk C] → NULL  (3个chunk)
    entries[1]: 32字节 → [Chunk D] → [Chunk E] → NULL                (2个chunk)
    entries[2]: 40字节 → [Chunk F] → [Chunk G] → [Chunk H] → [Chunk I] → [Chunk J] → [Chunk K] → [Chunk L] → NULL  (7个chunk, 已满)
    entries[3]: 48字节 → NULL                                         (0个chunk, 空)
    ...
    entries[TCACHE_MAX_BINS-1]: 最大尺寸

LIFO 操作示意:
初始状态: entries[1] → [D] → [E] → NULL
释放新chunk F: entries[1] → [F] → [D] → [E] → NULL  (插入头部)
分配请求: 返回 [F], entries[1] → [D] → [E] → NULL   (从头部取出)

多线程独立性:
线程1 Tcache: entries[0] → [A] → [B] → NULL
线程2 Tcache: entries[0] → [C] → [D] → NULL
线程3 Tcache: entries[0] → NULL
(每个线程完全独立，无需锁竞争)

技术参数对比表

特性 Tcache Fast Bin Small Bin Large Bin Unsorted Bin
链表拓扑 单向 (fd) 单向 (fd) 双向环形 (fd/bk) 双向环形 (fd/bk) + NextSize 双向环形 (fd/bk)
分配顺序 LIFO LIFO FIFO Sorted Best-Fit 遍历过程中的 Exact Fit
尺寸精度 精确大小 精确大小 精确大小 范围大小 混合大小
合并逻辑 不合并 (P=1) 不合并 (P=1) 不合并 自动合并 自动合并
索引计算 直接尺寸映射 (size/16) 显式索引转换 $$Index = Size / 16$$ 复杂的范围分段函数 固定 Index 1
并发控制 无锁 (Thread-Local) 有锁 有锁 有锁 有锁
优先级 最高 (先检查/后释放) 中等 低 低 中等
容量限制 默认7个/chunk (可配置) 无限制 无限制 无限制 无限制
存储位置 线程私有 (TLS) malloc_state.fastbinsY malloc_state.bins[2-63] malloc_state.bins[64-126] malloc_state.bins[1]
安全特性 双重释放检测 (Double Free) 无 无 无 无

内存布局视角的安全影响

在二进制安全领域，Bin 的链表结构特性直接导致了特定的漏洞利用原语（Primitives）：

  1. 单向链表攻击 (Fastbin/Tcache): 由于只校验 fd，攻击者可以通过篡改 fd 指针，将其指向任意地址（如 Stack 或 GOT 表），下次 malloc 时即可获得该地址的控制权。
  2. 双向链表解链 (Unlink Exploit): 在 Small/Large Bin 中，当一个 chunk 被取出时，会执行 FD->bk = BK 和 BK->fd = FD。如果攻击者控制了 fd 和 bk，这实际上是一个任意地址写（Arbitrary Write） 操作。
  3. Unsorted Bin 泄露: 由于 Unsorted Bin 是双向循环链表，链表头部的 bk 指针指向 main_arena 结构体内部。通过读取未被清空的 bk 指针，攻击者可以计算出 libc 的基地址（ASLR Bypass）。

参考文献

  1. Glibc 2.35 malloc_state 结构体定义：https://elixir.bootlin.com/glibc/glibc-2.35/source/malloc/malloc.c#L1830 ↩︎

Prev
2026-03-12 10:20:23 #Heap #bins # 二进制安全
Next