用 Rust 从零实现一个内存分配器:从 bump 到 free list
每次
Box::new都悄悄调用了malloc。但绝大多数人从没想过malloc里发生了什么。
这篇不是要教你怎么优化内存,而是把"分配"这件事拆开。写完你会发现:分配器的核心矛盾只有一个——怎么在连续的内存里,给大小不一的请求找到合适的空位。
Rust 给这件事留了一个干净的接口:GlobalAlloc。实现它,就能替换掉整个程序的分配器。
分配器要回答的三个问题
任何分配器,最终都要处理这三件事:
- allocate:给我
size字节,对齐到align,返回一个指针 - deallocate:这块内存我不要了,还给你
- 追踪:哪些内存被用了,哪些空着
前两个是接口,第三个是全部难度所在。
先看 Rust 的接口长什么样:
use std::alloc::{GlobalAlloc, Layout};
use std::ptr;
pub struct BumpAllocator;
unsafe impl GlobalAlloc for BumpAllocator {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 { /* ... */ }
unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) { /* ... */ }
}Layout 同时携带了 size 和 align,比 C 的 malloc(size) 更严谨——因为对齐是分配器躲不掉的责任。
对齐:为什么不能简单返回指针
先解释对齐为什么重要。CPU 访问内存是按字长来的,一个 u64 如果落在奇数地址上,某些架构会直接崩,另一些会慢好几倍。
对齐规则很简单:返回的地址必须是 align 的整数倍。
假设当前空闲空间从地址 1000 开始,现在要分配一个对齐到 8 的对象,起始地址必须是 1008(1000 不是 8 的倍数)。这中间的 8 个字节就浪费了——叫对齐填充(padding)。
fn align_up(addr: usize, align: usize) -> usize {
(addr + align - 1) & !(align - 1)
}align 一定是 2 的幂,所以这里可以 & !(align - 1) 做位运算,比除法快得多。
分配器的代码里到处都是这种"用位运算代替除法"的写法,因为对齐是个 2 的幂,而这个操作每次分配都要做。
第一版:bump 分配器(最简单)
bump 分配器的想法是:维护一个"当前指针",每次分配就往前走 size 字节,对齐后返回旧位置。
use std::cell::UnsafeCell;
use std::sync::atomic::{AtomicUsize, Ordering};
const HEAP_SIZE: usize = 1 << 20; // 1 MiB
pub struct BumpAllocator {
heap: UnsafeCell<[u8; HEAP_SIZE]>,
next: AtomicUsize,
end: usize,
}
impl BumpAllocator {
pub const fn new() -> Self {
Self {
heap: UnsafeCell::new([0; HEAP_SIZE]),
next: AtomicUsize::new(0),
end: HEAP_SIZE,
}
}
}用 UnsafeCell 包住堆内存,是因为我们要在 &self 的情况下往里写——这正是 UnsafeCell 存在的意义,也是所有分配器的共同前提。
unsafe impl GlobalAlloc for BumpAllocator {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
let base = self.heap.get() as usize;
let mut cur = self.next.load(Ordering::Relaxed);
// 先对齐
let aligned = align_up(cur, layout.align());
let new_cur = aligned + layout.size();
if new_cur > self.end {
return ptr::null_mut(); // OOM
}
self.next.store(new_cur, Ordering::Relaxed);
(base + aligned) as *mut u8
}
unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
// 什么都不做
}
}dealloc 是空的。因为 bump 分配器只前进不回收。
这听起来很蠢,但它在特定场景下非常有用:
- 编译器的临时内存(整个编译阶段结束一次性释放)
- 请求级的内存池(一个 HTTP 请求处理完,整块丢掉)
- 游戏引擎的每帧临时数据
优势是分配快到极致(一次加法 + 一次比较),而且天然无碎片。
劣势也很硬:内存不能回收,一定要用一次才行。
pub fn reset(&self) {
self.next.store(0, Ordering::Relaxed);
}reset 是它"释放全部内存"的方式——但要保证所有指针都不再被使用。
第二版:free list 分配器(能回收)
要支持任意释放,就必须记录"哪些块空着"。free list 的做法是把空闲块本身当作链表节点——空闲内存的头部存着下一个空闲块的地址。
#[repr(C)]
struct FreeNode {
size: usize,
next: *mut FreeNode,
}#[repr(C)] 是为了保证 size 在 next 前面,这样内存布局可预测。
分配时从链表里找一块足够大的:
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
let size = layout.size().max(std::mem::size_of::<FreeNode>());
let align = layout.align();
let mut prev: *mut FreeNode = ptr::null_mut();
let mut cur = self.head.load(Ordering::Relaxed);
while !cur.is_null() {
let addr = cur as usize;
let aligned = align_up(addr, align);
// 对齐后的块还能装下请求大小吗
if aligned + size <= addr + (*cur).size {
// 从链表里摘掉
let next = (*cur).next;
if prev.is_null() {
self.head.store(next, Ordering::Relaxed);
} else {
(*prev).next = next;
}
return aligned as *mut u8;
}
prev = cur;
cur = (*cur).next;
}
ptr::null_mut()
}这段是首次适配(first fit):找到第一块够大的就用。它的变体还有:
- 最佳适配(best fit):找最接近请求大小的块,浪费最少,但要遍历全部
- 最差适配(worst fit):找最大的块,试图保留大块
实际工程里首次适配 + 地址有序插入,性能通常最好。
释放:合并相邻空闲块
释放最麻烦的地方是碎片。如果你反复分配释放大小不一的块,内存会变成"用一点、空一点、再用一点"的马赛克。free list 里的空闲块彼此不相邻,最后明明总量够,却找不到一块连续的大空间。
解法是释放时把相邻的空闲块合并:
unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) {
let node = ptr as *mut FreeNode;
let mut cur = self.head.load(Ordering::Relaxed);
let mut prev: *mut FreeNode = ptr::null_mut();
// 找到插入位置(按地址排序)
while !cur.is_null() && (cur as usize) < (node as usize) {
prev = cur;
cur = (*cur).next;
}
(*node).next = cur;
// 和后一个块相邻则合并
if !cur.is_null() && (node as usize) + (*node).size == cur as usize {
(*node).size += (*cur).size;
(*node).next = (*cur).next;
}
// 和前一个块相邻则合并
if !prev.is_null() && (prev as usize) + (*prev).size == node as usize {
(*prev).size += (*node).size;
(*prev).next = (*node).next;
} else if prev.is_null() {
self.head.store(node, Ordering::Relaxed);
} else {
(*prev).next = node;
}
}保持 free list 按地址有序,是能在 O(n) 里完成合并的前提。如果链表无序,合并就得先扫描全表。
碎片的本质不是"空间不够",而是"空间不连续"。合并相邻空闲块是分配器对抗碎片最基本的手段。
分配器的真正难点:并发
上面两个版本在单线程下都能跑,但 GlobalAlloc 是全局的、可能被多线程同时调用的。裸指针链表在这里是灾难——两个线程同时改 next,链表直接断裂。
真实分配器用各种手段解决:
| 方案 | 思路 | 代表 |
|---|---|---|
| 全局大锁 | 加一把 Mutex | 最简单,但热点 |
| 线程本地缓存 | 每个线程一小块 tcache | 避免锁,tcmalloc/jemalloc |
| 分区/arena | 按线程或大小分不同堆 | mimalloc |
| 无锁结构 | 原子操作维护 free list | 难写,ABA 问题 |
工业界的主流是线程本地缓存 + 定期归还:绝大多数分配/释放根本碰不到全局锁,只在本地缓存不够或太多时才和中央堆交互。
这也是为什么"换一个分配器"经常能直接提升吞吐——不是算法更聪明,而是锁竞争更少。
结论
自己写分配器,收获的不是"我要替换掉系统 malloc",而是理解了这几件事:
对齐是分配器的硬约束;bump 分配器快但不可回收;free list 靠把空闲块串成链表实现回收;碎片要靠地址有序 + 相邻合并来对抗;并发才是真难点。
下次看到 jemalloc、mimalloc 这些名字,你就知道它们真正解决的问题不是"更快地找块",而是"让多个线程不要把时间花在等锁上"。