堆中的bin
2026-02-03 01:41:07 #bin #Heap # 二进制安全

bin是什么？

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

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

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

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 字节（具体取决于 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 对应一个精确的固定大小。例如，Bin 2 存储 32 字节，Bin 3 存储 48 字节（步长通常为 16 字节）。
  • 操作策略： FIFO (First In, First Out)。插入到头部，从尾部摘取。
  • 合并策略： 严格执行合并。相邻的空闲 chunk 会合并，生成的更大的 chunk 可能进入 Large Bin 或 Unsorted Bin。

Large Bins

用于管理大块内存。

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

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

自 Glibc 2.26 引入，位于 malloc_state 之外，是线程私有的堆数据结构。

  • 并发控制： 无锁 (Lock-free)。每个线程拥有独立的 tcache_perthread_struct。
  • 数据结构： 单向链表，LIFO 策略（结构上类似 Fast Bin）。
  • 优先级： 最高。malloc 时最先检查 Tcache，free 时最先放入 Tcache。
  • 限制： 有容量限制（默认每个 size 链表最多存 7 个 chunk）。

技术参数对比表

特性 Fast Bin Small Bin Large Bin Unsorted Bin
链表拓扑 单向 (fd) 双向环形 (fd/bk) 双向环形 (fd/bk) + NextSize 双向环形 (fd/bk)
分配顺序 LIFO FIFO Sorted Best-Fit 遍历过程中的 Exact Fit
尺寸精度 精确大小 精确大小 范围大小 混合大小
合并逻辑 不合并 (P=1) 自动合并 自动合并 自动合并
索引计算 显式索引转换 $$Index = Size / 16$$ 复杂的范围分段函数 固定 Index 1

内存布局视角的安全影响

在二进制安全领域，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. https://elixir.bootlin.com/glibc/glibc-2.35/source/malloc/malloc.c#L1830 ↩︎

Prev
2026-02-03 01:41:07 #bin #Heap # 二进制安全