内存管理串讲

这篇是内存分配器系列的索引和串讲。每个分配器都有单独的文章细讲,这里只抓主线:它们要解决什么问题、用了哪些共同的招式、各自在哪里做了不同的取舍。

#什么是内存管理

"内存管理"这个词覆盖的范围很广,从硬件到语言运行时可以分成好几层,每一层都在为上一层提供"分配一块内存"的服务:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
┌──────────────────────────────────────────────────────────┐
│ 应用 / 语言运行时 new、malloc、GC 堆、对象池 │
├──────────────────────────────────────────────────────────┤
│ 用户态分配器 ptmalloc / jemalloc / tcmalloc / ... │ ← 以字节为单位
├──────────────────────── 系统调用 ─────────────────────────┤
│ brk / sbrk / mmap / munmap / madvise │
├──────────────────────────────────────────────────────────┤
│ 内核虚拟内存 VMA、页表、缺页异常、THP │ ← 以页为单位映射
├──────────────────────────────────────────────────────────┤
│ 内核对象分配器 Slab / SLUB / SLOB (kmalloc) │ ← 内核里的"malloc"
├──────────────────────────────────────────────────────────┤
│ 内核页分配器 Buddy System (alloc_pages) │ ← 以 2^k 个物理页为单位
├──────────────────────────────────────────────────────────┤
│ 物理内存 NUMA node → zone → page frame │
└──────────────────────────────────────────────────────────┘

本系列关注其中的两类"分配器":

  • 内核态:Buddy System 管理物理页,Slab 家族在页之上切出小对象,供内核自己使用。
  • 用户态:malloc/free 的实现。它向内核批发大块虚拟内存(brk、mmap),再零售给应用。

两类分配器的问题本质相同:给定一串事先未知的分配/释放请求,在线地决定每个对象放在哪里。它们不能移动已经分配出去的对象(不同于带压缩的 GC),所以一旦放错位置,留下的碎片只能等对象自己释放。

#内存管理的目标

一个分配器至少要在以下几个维度上权衡,而这些目标经常互相冲突:

目标含义典型冲突
速度快速路径应只有几十条指令,且尽量不加锁越快的策略往往越浪费空间
空间利用率碎片少、元数据开销小为减少碎片做的搜索和合并会变慢
可扩展性多线程/多核下吞吐线性增长,无锁争用线程私有缓存会囤积内存
局部性一起分配的对象放在一起,减少 cache / TLB miss和"按尺寸隔离"有时矛盾
归还内存释放后 RSS 能降下来频繁归还再申请会引发系统调用和缺页
安全与调试越界写、double free、UAF 不易被利用,能检测泄漏校验和隔离都有开销

其中最核心的是碎片,分为两种:

  • 内部碎片:分出去的块比请求的大。比如请求 33 字节却给了 48 字节,多出的 15 字节用户用不到。来源是对齐、尺寸取整和块头开销。
  • 外部碎片:空闲内存的总量足够,但被切成了许多不连续的小块,满足不了一个大请求。
1
2
外部碎片:总空闲 = 4 页,但没有 2 页连续的空间
[used][free][used][free][used][free][used][free]

Wilson 等人 1995 年的综述 Dynamic Storage Allocation: A Survey and Critical Review 认为,减少碎片带来的浪费应当是分配器的首要目标:一个只做 bump、从不复用的 malloc 最快,但内存会无限增长。不过在多核时代,可扩展性和局部性的分量越来越重,后面会看到,现代分配器往往愿意多花一点内存来换取无锁的快速路径。

#常用的内存管理思想

各种分配器看上去千差万别,拆开来看用的都是下面这些招式的组合。

#空闲链表与放置策略

最朴素的做法是把所有空闲块串成一条链表,分配时遍历链表找一块足够大的:

  • First fit:找到第一个够大的就用。简单,但低地址容易积累碎片。
  • Next fit:从上次停下的位置继续找。速度稍快,实测碎片更多。
  • Best fit:找最小的够用块。直觉上浪费最少,Wilson 的实验也表明在真实负载下 best fit 和按地址排序的 first fit 碎片最少。

问题在于遍历是O(n)O(n) 的,这就引出了下面的各种索引结构。

#分割、合并与边界标签

找到的块比请求大时,把多余部分分割出来放回空闲链表;释放时如果相邻块也空闲,就合并成一个大块,以对抗外部碎片。

合并需要从一个块快速找到它物理上的前后邻居。Knuth 提出的边界标签(boundary tag)在每个块的头尾都写上大小:

1
2
3
4
5
┌──────┬───────────────────┬──────┐┌──────┬───────────┬──────┐
│ size │ payload │ size ││ size │ payload │ size │
└──────┴───────────────────┴──────┘└──────┴───────────┴──────┘
↑ 当前块 ↑ 下一块 = 当前块 + size
上一块的尾部 size 就在当前块头部前面,于是前后都能 O(1) 找到
dlmalloc 和 ptmalloc 都使用这一机制,并做了优化:已分配块的尾部标签可以省掉,只用头部的一个 bit 记录"前一块是否在使用"。

#分离适配与尺寸类别

与其维护一条大链表,不如按大小分成多条链表(bins),每条只放一定尺寸范围的块,这叫分离适配(segregated fit)。分配时直接去对应的 bin 取,接近O(1)O(1)。

更进一步,可以把所有请求都向上取整到一组固定的尺寸类别(size class),同一类别的对象放在同一批页面里,且不再分割合并。这就是 jemalloc、TCMalloc、mimalloc 以及 Slab 的做法,叫做简单分离存储(simple segregated storage):

  • 优点:分配释放极快;同一页面内对象等大,元数据可以只记一个"尺寸类别";不同尺寸的对象不会互相切碎对方。
  • 代价:取整带来内部碎片。尺寸类别通常按"每个 2 的幂区间再分 4 档"的方式设计,把内部碎片控制在 20% 左右以内;而某一类别的页面只能装这一类对象,空闲页无法被其他尺寸复用,这又是另一种形式的外部碎片。

#伙伴系统

伙伴系统(buddy system)只分配2k2^k 大小的块。一个2k+12^{k+1} 的块对半分裂成两个2k2^k 的"伙伴";释放时,如果伙伴也空闲,就合并回2k+12^{k+1}。

伙伴的地址可以直接算出来,不需要边界标签:

buddy(addr,k)=addr⊕2k\text{buddy}(addr, k) = addr \oplus 2^k

合并因此非常便宜,代价是最坏接近 50% 的内部碎片(请求2k+12^k + 1 要给2k+12^{k+1})。所以伙伴系统适合管理页这种粗粒度资源,小对象则交给上层的分配器。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
2
3
4
5
6
7
8
9
           快 / 无锁 / 容量小
线程或 CPU 本地缓存 tcache、per-CPU cache、thread heap
↓ 批量补充 / 批量归还
中心缓存 arena bins、central freelist、node partial list
↓ 按页申请
页级分配器 top chunk、extent、pageheap、buddy
↓ 系统调用
操作系统 brk、mmap
慢 / 加锁 / 容量大

越靠上越快,但缓存在各线程里的空闲内存别人用不到。各分配器的差异很大程度上就在于:每一层放多少,什么时候在层间搬运,搬运的批量是多少。

降低锁争用的另一条路是多 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
2
3
4
kmalloc / kmem_cache_alloc    ──→  Slab 家族(SLUB)
│ 整页不够时申请新 slab
alloc_pages / __get_free_pages ──→ Buddy System
vmalloc ──→ 从 Buddy 拿离散页,在内核虚拟地址空间里拼成连续区域

#Buddy System

Linux 的物理内存按 NUMA node 划分,每个 node 再分成若干 zone(ZONE_DMA、ZONE_NORMAL 等)。每个 zone 有一个 free_area[] 数组,第kk 项挂着所有大小为2k2^k 页的空闲块,kk 通常最大为 10,即 4KiB 页下最大 4MiB。

  • 分配 orderkk:从 free_area[k] 取;为空则向更高阶借一块,对半分裂,把多出的一半挂回低阶。
  • 释放 orderkk:计算伙伴的页帧号 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
2
3
4
5
6
7
1987  dlmalloc      单线程,边界标签 + 分箱 + best fit
↓ 加 arena
1990s ptmalloc 多 arena,成为 glibc malloc;2017 年加入 tcache
2005 jemalloc FreeBSD;按尺寸隔离 + 元数据分离 + 多 arena
2005 tcmalloc Google;线程缓存 → 中心缓存 → pageheap
2019 mimalloc Microsoft;空闲链表分片,线程直接拥有 page
2021 Temeraire TCMalloc 的大页感知 pageheap,优化整个集群

#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 申请
SLUBkmem_cache_cpu 当前 slabper-node 部分空闲链表Buddy System—
dlmalloc—全局 binstop chunkbrk / mmap
ptmalloctcache各 arena 的 fastbin / small / large binstop chunk / heapbrk / mmap
jemalloctcachearena 的 bin(slab)extentmmap
TCMallocper-CPU cachetransfer cache + central freelistpageheap(Temeraire)mmap
mimalloc线程 heap 拥有的 page无(跨线程释放走 thread_free)segmentmmap

几个比较明显的趋势:

  • 按尺寸隔离取代了分割合并:除了 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
2
3
LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libjemalloc.so.2 ./app
LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libtcmalloc.so.4 ./app
LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libmimalloc.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/