返回文章列表

用 Rust 从零实现一个内存分配器:从 bump 到 free list

332 字·3 分钟阅读
Rust从零造轮子内存

每次 Box::new 都悄悄调用了 malloc。但绝大多数人从没想过 malloc 里发生了什么。

这篇不是要教你怎么优化内存,而是把"分配"这件事拆开。写完你会发现:分配器的核心矛盾只有一个——怎么在连续的内存里,给大小不一的请求找到合适的空位。

Rust 给这件事留了一个干净的接口:GlobalAlloc。实现它,就能替换掉整个程序的分配器。


分配器要回答的三个问题

任何分配器,最终都要处理这三件事:

  1. allocate:给我 size 字节,对齐到 align,返回一个指针
  2. deallocate:这块内存我不要了,还给你
  3. 追踪:哪些内存被用了,哪些空着

前两个是接口,第三个是全部难度所在。

先看 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 这些名字,你就知道它们真正解决的问题不是"更快地找块",而是"让多个线程不要把时间花在等锁上"。