ptmalloc 内存分配器

ptmalloc 是 glibc 的默认内存分配器,也是最流行的内存分配器之一,起源于 Doug Lea 的 dlmalloc。由 Wolfram Gloger 改进得到可以支持多线程。

  • ptmalloc(pthreads malloc)由 Wolfram Gloger 基于 dlmalloc 开发,核心改动是引入多个 arena,让不同线程可以并行分配。
  • 它的第二版 ptmalloc2 基于 dlmalloc 2.7.0,在 2000 年代初并入 glibc,此后一直作为 glibc 的 malloc 实现,并在 glibc 中独立演进。
  • glibc 2.26(2017 年)引入了每线程缓存 tcache,大幅提升了小对象分配的速度。

本文的源码分析基于 glibc 2.39 的 malloc/malloc.c 与 malloc/arena.c,默认讨论 x86-64 平台(SIZE_SZ = 8,对齐 MALLOC_ALIGNMENT = 16)。

#整体结构

ptmalloc 的数据结构可以分为四层:

层次结构作用
线程tcache_perthread_struct每线程缓存,无锁,最快
arenastruct malloc_state分配区,自带一把互斥锁,管理 bins 和 top chunk
heapheap_info / 主 arena 的 brk 区arena 从操作系统拿到的连续内存
chunkstruct malloc_chunk分配与回收的基本单位

一次 malloc 大致按以下顺序寻找内存,越往后越慢:

1
tcache  →  fastbin  →  smallbin  →  unsorted bin  →  largebin  →  binmap 中更大的 bin  →  top chunk  →  sysmalloc (brk / mmap)

#chunk

#内存布局

chunk 是 ptmalloc 中内存管理的基本单位,定义如下:

1
2
3
4
5
6
7
8
9
10
11
struct malloc_chunk {
INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T mchunk_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 头部的一种"视图",同一块内存在使用中和空闲时有不同的解释:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    使用中的 chunk                           空闲的 chunk
chunk -> +-------------------------+ chunk -> +-------------------------+
| prev_size (若前块空闲) | | prev_size |
+-------------------------+ +-------------------------+
| size |A|M|P| | | size |A|M|P| |
mem -> +-------------------------+ +-------------------------+
| | | fd |
| 用户数据 | | bk |
| | | fd_nextsize (仅 large) |
| | | bk_nextsize (仅 large) |
| | | ... |
next chunk-> +-------------------------+ next chunk->+-------------------------+
| (可被本块复用的 prev_size)| | prev_size = 本块大小 |
+-------------------------+ +-------------------------+
| size |A|M|0| | | size |A|M|0| |

几个关键点:

  • malloc 返回给用户的指针 mem 是 chunk 地址加 2 * SIZE_SZ(16 字节)。
  • 边界标记(boundary tag):空闲 chunk 会把自己的大小写进下一个 chunk 的 prev_size 字段,这样释放时就能 O(1) 找到前一个 chunk 并与之合并。反过来,当本 chunk 使用中时,下一个 chunk 的 prev_size 字段没有用处,可以被本 chunk 的用户数据占用。所以一个使用中的 chunk 实际额外开销只有 8 字节。
  • 最小 chunk 大小 MINSIZE 为 32 字节(要能放下 prev_size、size、fd、bk),所以 malloc(0) 也会返回一个 32 字节的 chunk。

#size 的低三位

chunk 大小总是 16 的倍数,所以 size 的低 3 位被用作标志位:

标志值含义
PREV_INUSE (P)0x1前一个 chunk 正在使用(为 0 时 prev_size 才有效)
IS_MMAPPED (M)0x2本 chunk 由 mmap 直接分配
NON_MAIN_ARENA (A)0x4本 chunk 不属于主 arena

注意:位于 tcache 和 fastbin 中的 chunk 虽然空闲,但不会清除下一个 chunk 的 PREV_INUSE 位,因此也不会被相邻 chunk 合并。这正是它们快的原因,也是碎片的来源之一。

#arena:多线程的关键

#为什么需要 arena

dlmalloc 只有一个全局的 malloc_state,多线程使用时只能加一把全局锁,所有线程的分配都被串行化。ptmalloc 的核心改进是允许存在多个 arena,每个 arena 有自己的锁和自己的 bins,不同线程可以在不同的 arena 上并发分配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct malloc_state
{
__libc_lock_define (, mutex); /* Serialize access. */
int flags;
int have_fastchunks;
mfastbinptr fastbinsY[NFASTBINS]; /* Fastbins */
mchunkptr top; /* Base of the topmost chunk */
mchunkptr last_remainder; /* The remainder from the most recent split */
mchunkptr bins[NBINS * 2 - 2]; /* Normal bins */
unsigned int binmap[BINMAPSIZE]; /* Bitmap of bins */
struct malloc_state *next; /* Linked list */
struct malloc_state *next_free; /* Linked list for free arenas */
INTERNAL_SIZE_T attached_threads; /* Number of threads attached */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};

#主 arena 与非主 arena

  • 主 arena(main_arena)是一个静态全局变量,它通过 brk/sbrk 扩展进程的数据段来获取内存,可以连续地向上增长。
  • 非主 arena 不能再用 brk,而是通过 mmap 申请一块块 heap。每个 heap 开头是一个 heap_info 结构,多个 heap 通过 prev 指针串成链表:
1
2
3
4
5
6
7
8
9
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. */
size_t pagesize; /* Page size used when allocating the arena. */
char pad[-3 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

heap 的最大大小 HEAP_MAX_SIZE 为 2 * DEFAULT_MMAP_THRESHOLD_MAX,在 64 位上是 64MB,并且每个 heap 都按 HEAP_MAX_SIZE 对齐。heap 一开始只 mprotect 出需要的部分为可读写,随着使用逐步扩展(grow_heap),收缩时再改回 PROT_NONE(shrink_heap)。

#从 chunk 找到 arena

free(p) 时需要知道 chunk 属于哪个 arena。ptmalloc 的做法和 jemalloc 的 chunk、mimalloc 的 segment 如出一辙,利用对齐:

1
2
3
4
5
6
7
8
9
10
11
12
static inline heap_info *
heap_for_ptr (void *ptr)
{
size_t max_size = heap_max_size ();
return PTR_ALIGN_DOWN (ptr, max_size);
}

static inline struct malloc_state *
arena_for_chunk (mchunkptr ptr)
{
return chunk_main_arena (ptr) ? &main_arena : heap_for_ptr (ptr)->ar_ptr;
}

先看 NON_MAIN_ARENA 位:不是主 arena 的 chunk,把地址向下对齐到 64MB 就得到所在 heap 的 heap_info,再从中读出 ar_ptr。

#线程如何选择 arena

每个线程用一个 TLS 变量 thread_arena 记住自己上一次使用的 arena。分配时(arena_get)先尝试这个 arena;第一次分配或者需要换 arena 时调用 arena_get2:

  1. 先从空闲 arena 链表(free_list,即线程已退出、没人使用的 arena)中取一个;
  2. 如果 arena 总数还没到上限,调用 _int_new_arena 新建一个;
  3. 否则调用 reused_arena,从 next_to_use 开始轮询所有 arena,找到第一个能 trylock 成功的;如果都被锁住了,就阻塞在下一个 arena 上。

arena 数量上限默认为:

1
#define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))

即 64 位系统上为 CPU 核数 × 8。可以通过环境变量 MALLOC_ARENA_MAX、tunable glibc.malloc.arena_max 或 mallopt(M_ARENA_MAX, n) 修改。

线程多的服务(例如 Java 应用通过 JNI 调用大量 native 代码)常常会创建大量 arena,每个 arena 都会缓存自己的空闲内存,彼此之间不能共享,导致 RSS 远高于实际使用量。这是生产环境中 glibc malloc "内存泄漏"的常见原因,通常通过把 MALLOC_ARENA_MAX 设为 2~4 来缓解,代价是锁争用增加。

#bins:空闲 chunk 的组织

每个 arena 用多种 bin 组织空闲 chunk。以 x86-64 为例:

名称数量大小范围(chunk 大小)结构特点
fastbin10(默认用 7 个)32 ~ 128 字节单链表,LIFO不合并,不清 PREV_INUSE
unsorted bin1任意双链表刚释放的 chunk 的"缓冲区"
small bin6232 ~ 1008 字节,间隔 16双链表,FIFO每个 bin 只放一种大小
large bin63≥ 1024 字节双链表 + nextsize 链表每个 bin 是一个大小范围,内部按大小降序排列

bins[NBINS * 2 - 2] 数组(NBINS = 128)中,bin 1 是 unsorted bin,bin 2~63 是 small bin,bin 64~126 是 large bin。每个 bin 只存 fd/bk 两个指针,并被巧妙地当作一个伪 chunk 的头部来用,从而省去链表头的特殊处理。

large bin 的间隔按几何级数增长(下面是源码注释中的通用划分,第一行对应 small bin):

1
2
3
4
5
6
7
64 bins of size       8   (64 位上为 16)
32 bins of size 64
16 bins of size 512
8 bins of size 4096
4 bins of size 32768
2 bins of size 262144
1 bin of size what's left

为了快速找到"比当前 bin 大的第一个非空 bin",arena 还维护了一个位图 binmap,每一位表示对应 bin 是否可能非空。

#top chunk 与 last remainder

  • top chunk 是 arena 当前内存区域最高处的那块空闲内存,不属于任何 bin。所有 bin 都满足不了请求时,从 top chunk 切一块;top chunk 不够时,再向操作系统要内存来扩展它。
  • last remainder 是最近一次为小请求分割大 chunk 后剩下的部分。连续的小请求会优先从它上面继续切,以提升局部性。

#tcache:每线程缓存

glibc 2.26 引入的 tcache 是 ptmalloc 最重要的现代改进。每个线程有一个 tcache_perthread_struct:

1
2
3
4
5
6
7
8
9
10
11
typedef struct tcache_entry
{
struct tcache_entry *next;
uintptr_t key; /* This field exists to detect double frees. */
} tcache_entry;

typedef struct tcache_perthread_struct
{
uint16_t counts[TCACHE_MAX_BINS];
tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;
  • 共 TCACHE_MAX_BINS = 64 个 bin,对应 chunk 大小 32 ~ 1040 字节(用户请求最大约 1032 字节),间隔 16 字节。
  • 每个 bin 默认最多缓存 TCACHE_FILL_COUNT = 7 个 chunk,可通过 tunable glibc.malloc.tcache_count 调整。
  • tcache 是线程私有的,完全不需要加锁。next 指向的是用户数据区(mem),而不是 chunk 头。

tcache 不仅在 free 时被填充,在 _int_malloc 从 fastbin、smallbin 或 unsorted bin 中找到合适 chunk 时,还会把同样大小的其他 chunk 顺手搬进 tcache,直到填满。这样下一次同样大小的分配就不需要再加锁了。

#malloc 流程

#__libc_malloc

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
void *
__libc_malloc (size_t bytes)
{
...
size_t tbytes = checked_request2size (bytes);
size_t tc_idx = csize2tidx (tbytes);

MAYBE_INIT_TCACHE ();

if (tc_idx < mp_.tcache_bins && tcache != NULL && tcache->counts[tc_idx] > 0)
return tcache_get (tc_idx); /* 1. tcache 命中,直接返回 */

if (SINGLE_THREAD_P)
return _int_malloc (&main_arena, bytes);

arena_get (ar_ptr, bytes); /* 2. 选 arena 并加锁 */
victim = _int_malloc (ar_ptr, bytes);
/* Retry with another arena only if we were able to find a usable arena before. */
if (!victim && ar_ptr != NULL)
{
ar_ptr = arena_get_retry (ar_ptr, bytes);
victim = _int_malloc (ar_ptr, bytes);
}
if (ar_ptr != NULL)
__libc_lock_unlock (ar_ptr->mutex);
return victim;
}

(为了突出主干,省略了初始化、内存标签和断言相关的代码。)

#_int_malloc

_int_malloc 是分配的核心,设请求对齐后的 chunk 大小为 nb:

  1. fastbin:若 nb 在 fastbin 范围内,且对应 fastbin 非空,弹出链表头。若同一 fastbin 里还有 chunk,把它们搬进 tcache,然后返回。

  2. small bin:若 nb 在 small bin 范围内,且对应 small bin 非空,从链表尾部取一个(FIFO)。同样把剩余的同尺寸 chunk 搬进 tcache,然后返回。

  3. 整理 fastbin:若是 large 请求,并且 arena 中有 fastbin chunk,先调用 malloc_consolidate 把所有 fastbin chunk 合并后放进 unsorted bin,以减少碎片。

  4. 处理 unsorted bin:循环取出 unsorted bin 中的每个 chunk(最多 MAX_ITERS = 10000 次):

    • 如果是小请求,并且 unsorted bin 中只有 last remainder 这一个 chunk,且它足够大,直接切分它,剩余部分继续作为 last remainder。
    • 如果大小恰好等于 nb:tcache 未满就放进 tcache 并继续循环(之后再从 tcache 返回),否则直接返回。
    • 否则把这个 chunk 归位到对应的 small bin 或 large bin(large bin 要保持有序,并维护 fd_nextsize/bk_nextsize)。

    这一步是 ptmalloc 的"延迟分类":free 时只把 chunk 扔进 unsorted bin,等到下一次 malloc 才真正归类,给了刚释放的 chunk 一次被立刻复用的机会。

  5. large bin:若是 large 请求,在对应 large bin 中找最小的、能满足请求的 chunk(best-fit),切分后把剩余部分放进 unsorted bin。

  6. binmap 搜索:利用 binmap 找下一个更大的非空 bin,取其中的 chunk 切分,剩余部分放进 unsorted bin(小请求时同时设为 last remainder)。

  7. top chunk:从 top chunk 切分。如果 top chunk 不够:

    • 若 arena 中还有 fastbin chunk,先 malloc_consolidate 再回到第 4 步重试;
    • 否则调用 sysmalloc 向操作系统要内存。

#sysmalloc

  • 若 nb ≥ mmap_threshold(默认 128KB)且 mmap 数量未超过 M_MMAP_MAX(默认 65536),直接用 mmap 分配一个独立的 chunk,打上 IS_MMAPPED 标志。
  • 否则扩展 top chunk:主 arena 调用 sbrk(失败时退回 mmap);非主 arena 先尝试 grow_heap 扩展当前 heap,不行就 new_heap 新建一个 heap。

#free 流程

__libc_free → _int_free:

  1. mmap chunk:直接 munmap 还给操作系统。同时这里有一个动态阈值机制:如果释放的 mmap chunk 大于当前 mmap_threshold(且不超过 DEFAULT_MMAP_THRESHOLD_MAX,64 位上为 32MB),就把 mmap_threshold 调大到这个 chunk 的大小,并把 trim_threshold 设为它的两倍。这样反复申请释放同样大小的大块内存时,后续就会走 brk/heap 而不是每次都 mmap/munmap。手动设置过相关参数后,动态调整会被关闭。

    1
    2
    3
    4
    5
    6
    7
    if (!mp_.no_dyn_threshold
    && chunksize_nomask (p) > mp_.mmap_threshold
    && chunksize_nomask (p) <= DEFAULT_MMAP_THRESHOLD_MAX)
    {
    mp_.mmap_threshold = chunksize (p);
    mp_.trim_threshold = 2 * mp_.mmap_threshold;
    }
  2. tcache:若对应 tcache bin 未满(< 7 个),放入 tcache,直接返回,不加锁。

  3. fastbin:若大小在 fastbin 范围内,压入 fastbin 链表头(用原子操作,不加 arena 锁),不合并。

  4. 合并并放入 unsorted bin:加 arena 锁,检查前后相邻的 chunk:

    • 前一个 chunk 空闲(本 chunk 的 PREV_INUSE 为 0)则向前合并;
    • 后一个 chunk 空闲则向后合并;如果后一个就是 top chunk,直接并入 top。
    • 合并后的 chunk 放进 unsorted bin。
  5. 回收内存:若合并后的 chunk 大小超过 FASTBIN_CONSOLIDATION_THRESHOLD(64KB),先 malloc_consolidate 整理 fastbin,然后:

    • 主 arena:如果 top chunk 超过 trim_threshold(默认 128KB),调用 systrim 用 sbrk 负增长把内存还给操作系统;
    • 非主 arena:调用 heap_trim 收缩或释放 heap。

主 arena 只能从 top chunk 收缩,也就是只能释放堆顶的内存。只要堆顶附近还有一个存活的小对象,下面再多的空闲内存也还不回去。此时可以调用 malloc_trim(0):它不仅会收缩 top,还会遍历所有 arena,对空闲 chunk 中完整的页调用 madvise(MADV_DONTNEED) 释放物理内存。

#安全加固

ptmalloc 的链表元数据和用户数据混在一起,因此一直是堆漏洞利用的主要目标。glibc 近年加入了多项缓解措施:

  • 完整性检查:各处有大量 malloc_printerr 检查,例如 unlink 时检查 P->fd->bk == P && P->bk->fd == P,fastbin 入链时检查链表头不是同一个 chunk(防止最简单的 double free)。

  • tcache double free 检测(2.29):放入 tcache 时把 e->key 设为 tcache_key,再次释放时若发现 key 匹配,就遍历该 bin 确认是否 double free。自 2.34 起 tcache_key 是进程启动时生成的随机值。

  • safe-linking(2.32):tcache 和 fastbin 的单链表指针不再明文存储,而是与存储位置的地址做异或:

    1
    2
    3
    #define PROTECT_PTR(pos, ptr) \
    ((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))
    #define REVEAL_PTR(ptr) PROTECT_PTR (&ptr, ptr)

    攻击者在不知道堆地址的情况下无法伪造有效的 next 指针,同时也会检查解码后的指针是否对齐。

  • 移除 hook(2.34):__malloc_hook、__free_hook 等全局函数指针被移除,它们曾是最常用的劫持目标。

#常用调优参数

参数默认值(64 位)说明
M_MMAP_THRESHOLD / glibc.malloc.mmap_threshold128KB(动态调整,上限 32MB)超过该大小直接 mmap
M_TRIM_THRESHOLD / glibc.malloc.trim_threshold128KB(动态调整)top chunk 超过该值时收缩堆
M_TOP_PAD / glibc.malloc.top_pad0(实际向 OS 申请时还会按页对齐)扩展堆时额外多申请的大小
M_MMAP_MAX / glibc.malloc.mmap_max65536mmap 分配的最大数量
M_ARENA_MAX / glibc.malloc.arena_max核数 × 8arena 数量上限
M_ARENA_TEST / glibc.malloc.arena_test8arena 数超过该值后才开始检查上限
M_MXFAST / glibc.malloc.mxfast128 字节fastbin 的最大 chunk 大小(上限 160 字节)
glibc.malloc.tcache_count7每个 tcache bin 的最大缓存数
glibc.malloc.tcache_max1032 字节tcache 能缓存的最大请求大小

tunable 可以通过环境变量设置,例如:

1
GLIBC_TUNABLES=glibc.malloc.arena_max=2:glibc.malloc.tcache_count=0 ./app

此外 malloc_stats()、malloc_info() 和 mallinfo2() 可以输出各 arena 的使用情况,排查内存问题时非常有用。

#与其他分配器的对比

ptmallocjemallocTCMallocmimalloc
线程本地缓存tcache(2.26 起,每 bin 7 个)tcacheper-CPU cache线程直接拥有 page
并发单元arena(核数 × 8),线程轮询绑定arena(核数 × 4),round-robin 绑定全局中心缓存 + pageheap线程本地 heap,无锁
元数据位置内联在 chunk 头分离(page map / bitmap)分离(pagemap)分离(page 元数据)
空闲块组织按大小分 bin,相邻块合并按 size class 隔离,不合并小对象按 sizeclass 隔离每 page 三条空闲链表
归还内存只能从堆顶收缩 / malloc_trim基于衰减时间的 purge后台线程按速率释放空 page / segment 回收

ptmalloc 最大的特点是继承了 dlmalloc 的边界标记与合并机制:元数据内联、相邻空闲块合并、best-fit 分配,内存利用率在单线程下相当好。但这也带来了几个固有问题:

  • 元数据与用户数据相邻,越界写容易破坏堆结构,安全性较差;
  • 堆只能从顶部收缩,长期运行的服务容易出现"释放了但 RSS 不降"的情况;
  • 多 arena 之间不共享空闲内存,线程多时内存膨胀明显。

现代分配器(jemalloc、tcmalloc、mimalloc)普遍采用"按尺寸隔离 + 元数据分离 + 对齐寻址"的设计,在多线程场景下通常更快、更省内存。

#参考资料

  • glibc 源码:malloc/malloc.c、malloc/arena.c
  • glibc wiki: MallocInternals
  • The GNU C Library: Memory Allocation Tunables
  • Wolfram Gloger. ptmalloc