内存管理串讲
这篇是内存分配器系列的索引和串讲。每个分配器都有单独的文章细讲,这里只抓主线:它们要解决什么问题、用了哪些共同的招式、各自在哪里做了不同的取舍。
#什么是内存管理
"内存管理"这个词覆盖的范围很广,从硬件到语言运行时可以分成好几层,每一层都在为上一层提供"分配一块内存"的服务:
1 | ┌──────────────────────────────────────────────────────────┐ |
本系列关注其中的两类"分配器":
- 内核态:Buddy System 管理物理页,Slab 家族在页之上切出小对象,供内核自己使用。
- 用户态:
malloc/free的实现。它向内核批发大块虚拟内存(brk、mmap),再零售给应用。
两类分配器的问题本质相同:给定一串事先未知的分配/释放请求,在线地决定每个对象放在哪里。它们不能移动已经分配出去的对象(不同于带压缩的 GC),所以一旦放错位置,留下的碎片只能等对象自己释放。
#内存管理的目标
一个分配器至少要在以下几个维度上权衡,而这些目标经常互相冲突:
| 目标 | 含义 | 典型冲突 |
|---|---|---|
| 速度 | 快速路径应只有几十条指令,且尽量不加锁 | 越快的策略往往越浪费空间 |
| 空间利用率 | 碎片少、元数据开销小 | 为减少碎片做的搜索和合并会变慢 |
| 可扩展性 | 多线程/多核下吞吐线性增长,无锁争用 | 线程私有缓存会囤积内存 |
| 局部性 | 一起分配的对象放在一起,减少 cache / TLB miss | 和"按尺寸隔离"有时矛盾 |
| 归还内存 | 释放后 RSS 能降下来 | 频繁归还再申请会引发系统调用和缺页 |
| 安全与调试 | 越界写、double free、UAF 不易被利用,能检测泄漏 | 校验和隔离都有开销 |
其中最核心的是碎片,分为两种:
- 内部碎片:分出去的块比请求的大。比如请求 33 字节却给了 48 字节,多出的 15 字节用户用不到。来源是对齐、尺寸取整和块头开销。
- 外部碎片:空闲内存的总量足够,但被切成了许多不连续的小块,满足不了一个大请求。
1 | 外部碎片:总空闲 = 4 页,但没有 2 页连续的空间 |
Wilson 等人 1995 年的综述 Dynamic Storage Allocation: A Survey and Critical Review 认为,减少碎片带来的浪费应当是分配器的首要目标:一个只做 bump、从不复用的 malloc 最快,但内存会无限增长。不过在多核时代,可扩展性和局部性的分量越来越重,后面会看到,现代分配器往往愿意多花一点内存来换取无锁的快速路径。
#常用的内存管理思想
各种分配器看上去千差万别,拆开来看用的都是下面这些招式的组合。
#空闲链表与放置策略
最朴素的做法是把所有空闲块串成一条链表,分配时遍历链表找一块足够大的:
- First fit:找到第一个够大的就用。简单,但低地址容易积累碎片。
- Next fit:从上次停下的位置继续找。速度稍快,实测碎片更多。
- Best fit:找最小的够用块。直觉上浪费最少,Wilson 的实验也表明在真实负载下 best fit 和按地址排序的 first fit 碎片最少。
问题在于遍历是 的,这就引出了下面的各种索引结构。
#分割、合并与边界标签
找到的块比请求大时,把多余部分分割出来放回空闲链表;释放时如果相邻块也空闲,就合并成一个大块,以对抗外部碎片。
合并需要从一个块快速找到它物理上的前后邻居。Knuth 提出的边界标签(boundary tag)在每个块的头尾都写上大小:
1 | ┌──────┬───────────────────┬──────┐┌──────┬───────────┬──────┐ |
#分离适配与尺寸类别
与其维护一条大链表,不如按大小分成多条链表(bins),每条只放一定尺寸范围的块,这叫分离适配(segregated fit)。分配时直接去对应的 bin 取,接近。
更进一步,可以把所有请求都向上取整到一组固定的尺寸类别(size class),同一类别的对象放在同一批页面里,且不再分割合并。这就是 jemalloc、TCMalloc、mimalloc 以及 Slab 的做法,叫做简单分离存储(simple segregated storage):
- 优点:分配释放极快;同一页面内对象等大,元数据可以只记一个"尺寸类别";不同尺寸的对象不会互相切碎对方。
- 代价:取整带来内部碎片。尺寸类别通常按"每个 2 的幂区间再分 4 档"的方式设计,把内部碎片控制在 20% 左右以内;而某一类别的页面只能装这一类对象,空闲页无法被其他尺寸复用,这又是另一种形式的外部碎片。
#伙伴系统
伙伴系统(buddy system)只分配 大小的块。一个 的块对半分裂成两个 的"伙伴";释放时,如果伙伴也空闲,就合并回。
伙伴的地址可以直接算出来,不需要边界标签:
合并因此非常便宜,代价是最坏接近 50% 的内部碎片(请求 要给)。所以伙伴系统适合管理页这种粗粒度资源,小对象则交给上层的分配器。Linux 的页分配器、早期 jemalloc 中 chunk 内部的 run 都用了伙伴算法。
#对象缓存
Bonwick 在 Slab Allocator 中观察到,内核里大量分配的是同类型的对象(inode、task_struct……),并且初始化它们往往比分配内存本身更贵。于是 Slab 为每种对象类型建一个缓存,释放的对象保持已构造状态放回缓存,下次直接复用。
这个思想在用户态演化为对象池、free list 和 per-size-class 缓存,几乎所有现代分配器都有它的影子。
#Bump pointer 与区域分配
在一大块连续内存上维护一个指针,分配就是 p += size,不支持单独释放,整块用完后一次性丢弃。这是最快的分配方式,也叫 arena/region 分配,常见于编译器、请求级内存池,以及 GC 中的 TLAB(线程本地分配缓冲区)。
通用 malloc 不能这样做,但会在局部使用:比如 ptmalloc 从 top chunk 切块、TCMalloc 从 span 里切出新对象,本质上都是 bump。mimalloc 则特意不用 bump pointer,而是把新页面一次性串成空闲链表,以保证快速路径只有一种形态。
#多级缓存与线程本地
多核下,一把全局锁会成为瓶颈。主流解法是分层缓存:
1 | 快 / 无锁 / 容量小 |
越靠上越快,但缓存在各线程里的空闲内存别人用不到。各分配器的差异很大程度上就在于:每一层放多少,什么时候在层间搬运,搬运的批量是多少。
降低锁争用的另一条路是多 arena:准备多个独立的分配区,把线程分散绑定上去(ptmalloc、jemalloc)。这样锁的数量变多、每把锁的争用变少,同时还能缓解伪共享(false sharing),即两个线程的对象落在同一条 cache line 上导致的缓存行抖动。
#元数据放在哪里
每个块的大小、所属 bin 等信息存在哪里,是区分新老分配器的一个重要标志:
- 内联:放在块头(dlmalloc、ptmalloc)。释放时
ptr - 16就能拿到,实现简单;但用户越界写会直接破坏分配器结构,这也是大量堆利用技巧的来源。 - 分离:放在独立的页表或位图里(jemalloc、TCMalloc、mimalloc、SLUB 的
struct slab)。更安全,元数据也更紧凑,缓存友好。
分离元数据要求能从任意指针快速找到它。常用技巧是对齐寻址:让大块内存按固定大小对齐(jemalloc 的 chunk、mimalloc 的 4MiB segment、ptmalloc 非主 arena 的 heap),ptr & ~(align - 1) 就是块头。另一种是基数树(radix tree)式的 page map(TCMalloc),按页号索引。
#向操作系统归还内存
free 不等于把内存还给内核。用户态分配器一般会缓存空闲页以备再用,只在合适时机通过 munmap、madvise(MADV_DONTNEED) 或 madvise(MADV_FREE) 归还。还得太勤,会频繁触发系统调用和缺页;还得太懒,RSS 降不下来。jemalloc 的衰减时间(decay)、TCMalloc 的后台按速率释放都是在这两者之间找平衡。
再往深一层,还要考虑大页:THP 能大幅降低 TLB miss,但只要 2MiB 里有一个小对象活着,这个大页就无法归还。Temeraire 就是专门围绕这一点重新设计 TCMalloc 的页分配器。
#内核态的内存管理
内核里的分配有两个特点:不能像用户态那样靠缺页懒分配(很多场景要求物理连续、不可睡眠);另外内核自己就是"操作系统",没有更下层可以批发。因此内核分配器分成两层:
1 | kmalloc / kmem_cache_alloc ──→ Slab 家族(SLUB) |
#Buddy System
Linux 的物理内存按 NUMA node 划分,每个 node 再分成若干 zone(ZONE_DMA、ZONE_NORMAL 等)。每个 zone 有一个 free_area[] 数组,第 项挂着所有大小为 页的空闲块, 通常最大为 10,即 4KiB 页下最大 4MiB。
- 分配 order:从
free_area[k]取;为空则向更高阶借一块,对半分裂,把多出的一半挂回低阶。 - 释放 order:计算伙伴的页帧号
pfn ^ (1 << k),若伙伴空闲且同阶,就摘下来合并,继续向上尝试。
在此基础上,Linux 还做了几项工程优化:
- 按迁移类型分组:每个
free_area[k]再按 unmovable、movable、reclaimable 分开存放,避免不可移动页散落各处导致高阶分配失败。 - per-CPU 页列表(PCP):小阶的分配和释放先走每 CPU 的页缓存,批量和 zone 交互,减少 zone 锁争用。这和用户态分配器的 tcache 是同一个思路。
#Slab Allocator
Slab Allocator 由 Jeff Bonwick 1994 年在 SunOS 5.4 中提出,后被 Linux 采用。它在伙伴系统之上为每种对象建立一个 `kmem_cache`:- 一个 cache 由若干 slab 组成,每个 slab 是一页或几页连续内存,切成等大的对象。
- slab 按满、部分空闲、全空三种状态挂在三条链表上,分配优先使用部分空闲的 slab。
- 对象缓存:释放的对象保持构造好的状态,省去重复初始化。
- slab 着色:不同 slab 的首个对象偏移不同的 cache line 数,让对象均匀分布到各个 cache set,减少冲突。
kmalloc 则是在这套机制上建了一组按 2 的幂(及少量中间尺寸)划分的通用 cache,如 kmalloc-64、kmalloc-128。
slab 的思想在用户态的缓存系统里也很常见。Memcached 和 Meta 的 CacheLib 都把内存切成固定大小的 slab,按对象尺寸分给各个 slab class,区别在于满了以后不是再申请内存,而是淘汰旧对象,并在 slab class 之间搬移整块 slab 来平衡容量。
#SLUB:Slab 的简化
随着 NUMA 机器的核数增长,Slab 的队列(per-CPU 数组、per-node shared 数组、三条 slab 链表、着色)带来了可观的内存开销和复杂度。Christoph Lameter 在 Linux 2.6.22 中引入 SLUB,主要改动如下:
- 去掉满 slab 和空 slab 链表,每个 node 只保留部分空闲链表;空 slab 直接还给伙伴系统。
- 每 CPU 持有一个"当前 slab",直接从它的空闲链表上分配;空闲链表指针存在空闲对象内部,不需要额外的数组。
- slab 的元数据复用
struct page(新内核中为struct slab),不再有独立的 slab 头。 - 合并尺寸和标志相近的 cache(cache merging),减少 cache 数量。
- 去掉着色。
SLUB 自 2.6.23 起成为默认实现,并且在后续版本中逐渐成为唯一的实现。
#SLOB
SLOB(Simple List Of Blocks)是为极小内存的嵌入式设备准备的:所有对象放在一条 first fit 空闲链表里,代码量和元数据都极少,但碎片多、扩展性差。随着嵌入式设备的内存越来越大,SLOB 在 Linux 6.4 中被移除;之后 SLAB 也在 6.8 中被移除,内核里只剩 SLUB。
#用户态的内存管理
用户态分配器从内核拿内存有两条路:
| 方式 | 说明 | 适用 |
|---|---|---|
brk / sbrk | 移动堆顶,扩展或收缩紧接在数据段后的那段连续区域 | 小块、频繁的分配;只能从顶部收缩 |
mmap | 映射一段匿名内存,可在任意位置、独立释放 | 大块分配、多线程的独立堆 |
拿到的都是虚拟内存,物理页在首次访问时才通过缺页异常分配。glibc 默认把大于 M_MMAP_THRESHOLD(初始 128KiB,会随释放的大块动态上调)的请求直接交给 mmap,其余在堆上切分。
下面按时间顺序看几个代表性的 malloc 实现,可以清晰地看到设计重心的转移:单线程的空间效率 → 多线程的可扩展性 → 整机乃至整个集群的效率。
1 | 1987 dlmalloc 单线程,边界标签 + 分箱 + best fit |
#dlmalloc
dlmalloc 是 Doug Lea 1987 年为 C/C++ 程序写的通用分配器,后来成为许多 libc 和嵌入式系统的基础。它的两大核心自最初版本起就没有变过:- 边界标签:每个 chunk 头部存大小,借此和相邻 chunk 合并、前后遍历。
- 分箱:128 个 bin,小于 512 字节的每 8 字节一个 bin(精确尺寸),更大的按近似对数间隔,bin 内按大小排序以实现 best fit。
在此之上还有一系列启发式优化:优先从最近分割剩下的块(last remainder)分配以保持局部性,尽量保留堆顶的"荒野"(wilderness)块,大块直接 mmap。
dlmalloc 的局限也很明显:全局只有一个堆,多线程时只能靠一把大锁串行化。
#ptmalloc
ptmalloc 是 Wolfram Gloger 在 dlmalloc 基础上加入多线程支持的版本,glibc 的 malloc 就由它演化而来,也是绝大多数 Linux 程序实际在用的分配器。在 dlmalloc 的 chunk 与 bins 之上,它主要增加了:- arena:多个独立的分配区,各自一把锁。主 arena 使用
brk堆,其余 arena 用mmap出来的、按 64MiB 对齐的 heap。线程优先复用上次的 arena,加锁失败就换一个,arena 数上限默认为核数 × 8(64 位)。 - fastbin:小块释放后不立即合并,单链表 LIFO 复用,延迟到合适的时机批量合并。
- unsorted bin:刚释放的块先进这里,下次 malloc 顺便分拣,给"释放后马上同尺寸再分配"一个快速通道。
- tcache(glibc 2.26):每线程、每 bin 最多 7 个块的无锁缓存,成为新的最快路径。
ptmalloc 的问题大多源自它的 dlmalloc 血统:元数据内联导致安全性差(因此有了 safe-linking 等加固);堆只能从顶部收缩,长期运行的服务经常出现"free 了但 RSS 不降";arena 之间不共享空闲内存,线程多时内存膨胀明显(常用 MALLOC_ARENA_MAX 来限制)。
#jemalloc
jemalloc 由 Jason Evans 为 FreeBSD 编写,在 2006 年 BSDCan 的论文中提出,后来被 Firefox、Redis 等广泛采用,Facebook 也在其上做了大量改进。它和 dlmalloc 系的分歧在于:- 多 arena + round-robin 绑定:arena 数为 CPU 数 × 4,线程轮流分配到各个 arena,比哈希更均匀。
- 按尺寸类别隔离:small、large、huge 三级;small 对象按尺寸类别放进 run(后来叫 slab),用位图记录空闲情况,不做分割合并。
- 元数据分离:chunk 头部的 page map 记录每页的状态,用户数据区里没有分配器结构,越界写更难破坏堆。
- 对齐的 chunk:由指针掩码 O(1) 找到所属 chunk 和 arena。
论文中的版本还没有线程缓存,后续版本陆续加入了 tcache、基于衰减时间的 purge、用 extent 取代 chunk,以及受 Temeraire 启发的大页感知页分配器(HPA)。
#TCMalloc
TCMalloc(Thread-Caching Malloc)是 Google 的分配器,最早随 gperftools 发布,2020 年开源了内部持续演进的新版本。Beyond malloc efficiency to fleet efficiency 一文先介绍了它的结构:
- 前端:per-CPU cache(新版借助 Linux 的 rseq 实现无锁的每 CPU 操作,取代了早期的每线程缓存)。
- 中端:transfer cache 在 CPU 之间批量转移对象,central freelist 按 span 管理同一尺寸类别的对象。
- 后端:pageheap 以页为单位管理 span,向操作系统申请和归还内存。
这篇 OSDI’21 论文的重点是 Temeraire,一个大页感知的 pageheap。它的出发点是:在仓库级计算机上,malloc 自身只占很小一部分 CPU 时间,但对象放在哪里决定了整个应用的 TLB miss 率。所以哪怕 malloc 本身变慢一点,只要能把小对象紧密地装进少量大页、让其余大页完整地保持空闲或归还,整机吞吐也会提升。
#mimalloc
mimalloc 是微软研究院 2019 年为 Lean、Koka 等引用计数语言的运行时设计的分配器,以代码小、速度快著称。它的核心思想是**空闲链表分片**(free list sharding):- 线程直接拥有一个个 64KiB 的 page,每个 page 只装一种尺寸的对象;
- 每个 page 有三条空闲链表:
free供分配,local_free收本线程的释放,thread_free用 CAS 收其他线程的释放; - 快速路径只从
free取,free空了才进入慢路径,把另外两条链表并过来。这样慢路径以确定的节奏执行,正好用来处理延迟释放、引用计数递减等杂务; - page 放在 4MiB 对齐的 segment 中,
free时用指针掩码找到元数据。
和 TCMalloc 的"线程缓存里放对象"不同,mimalloc 的"线程缓存"是整个 page,所以没有在线程缓存和中心缓存之间来回搬运对象的开销,局部性也更好。
#横向对比
把这些分配器放进前面"多级缓存"的框架里,可以发现它们的结构其实是趋同的:
| 本地层 | 中心层 | 页级 | 向 OS 申请 | |
|---|---|---|---|---|
| SLUB | kmem_cache_cpu 当前 slab | per-node 部分空闲链表 | Buddy System | — |
| dlmalloc | — | 全局 bins | top chunk | brk / mmap |
| ptmalloc | tcache | 各 arena 的 fastbin / small / large bins | top chunk / heap | brk / mmap |
| jemalloc | tcache | arena 的 bin(slab) | extent | mmap |
| TCMalloc | per-CPU cache | transfer cache + central freelist | pageheap(Temeraire) | mmap |
| mimalloc | 线程 heap 拥有的 page | 无(跨线程释放走 thread_free) | segment | mmap |
几个比较明显的趋势:
- 按尺寸隔离取代了分割合并:除了 dl/ptmalloc,其他分配器的小对象都不再分割合并,合并只在页级以上发生。
- 元数据从块头移到了别处:安全性和缓存效率都更好,代价是需要对齐或 page map 来查找。
- 快速路径越来越短:从加锁查 bin,到无锁的线程缓存,再到 per-CPU + rseq、单分支的 page 内链表。
- 优化目标从 malloc 本身扩大到整个系统:大页、NUMA、整机 RSS,Temeraire 甚至以整个集群的效率为目标。
#怎么选
对大多数程序来说,glibc 自带的 ptmalloc 已经够用。出现以下情况时,可以考虑换分配器:
- 多线程服务的 RSS 持续上涨,或者
free后内存不回落 → 先试MALLOC_ARENA_MAX=2和malloc_trim,不行再换 jemalloc 或 TCMalloc。 - malloc 在 profile 里占比很高,且分配以小对象为主 → mimalloc、TCMalloc 通常快速路径更短。
- 需要分析内存去向 → jemalloc 和 TCMalloc 都自带堆 profiling 和丰富的统计接口。
替换成本很低,大多数情况下不用改代码,LD_PRELOAD 一下即可对比:
1 | LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libjemalloc.so.2 ./app |
分配器的表现高度依赖负载,网上的 benchmark 只能作为参考。务必用自己的程序和真实流量对比吞吐、尾延迟和 RSS,并且观察足够长的时间,因为碎片问题往往在运行几天后才会显现。
#参考资料
- Paul R. Wilson, Mark S. Johnstone, Michael Neely, David Boles. Dynamic Storage Allocation: A Survey and Critical Review. IWMM 1995.
- Jeff Bonwick. The Slab Allocator: An Object-Caching Kernel Memory Allocator. USENIX Summer 1994.
- Doug Lea. A Memory Allocator. https://gee.cs.oswego.edu/dl/html/malloc.html
- Jason Evans. A Scalable Concurrent malloc(3) Implementation for FreeBSD. BSDCan 2006.
- A.H. Hunter et al. Beyond malloc efficiency to fleet efficiency: a hugepage-aware memory allocator. OSDI 2021.
- Daan Leijen, Benjamin Zorn, Leonardo de Moura. Mimalloc: Free List Sharding in Action. MSR-TR-2019-18.
- glibc wiki: MallocInternals. https://sourceware.org/glibc/wiki/MallocInternals
- Linux kernel documentation: Memory Management. https://docs.kernel.org/mm/