Polaris内核堆剖析:Slab分配器从GlobalAlloc到空闲链表的逐行解读
Polaris内核堆剖析:Slab分配器从GlobalAlloc到空闲链表的逐行解读
Polaris 是一个用 Rust 编写的 64 位类 UNIX 内核(WIP),它的堆内存完全由一个自研的 Slab 分配器接管:小对象走 8 个规格档位,大对象走逐页映射。本文带你从 Rust 全局分配器接口 GlobalAlloc 出发,逐行拆解 src/mm/slab.rs 中空闲链表的构建、取槽、还槽与整页回收机制——如果你想学习内核内存管理原理,不到 260 行的这份实现是一个极佳的范本。
🧭 一、先看全局:Polaris 堆内存的两条通道
在 src/mm/slab.rs#L159-L171 中,SlabAllocator 通过 #[global_allocator] 注册为整个内核的全局分配器,所有 Box、Vec、String 等来自 alloc 的分配最终都会走到这里:
pub static ALLOCATOR: SlabAllocator = SlabAllocator {
slabs: [Slab::new(16), Slab::new(32), Slab::new(64),
Slab::new(128), Slab::new(256), Slab::new(512),
Slab::new(1024), Slab::new(2048)],
};
一次分配请求在 src/mm/slab.rs#L219-L239 被分流到两条通道:
| 通道 | 适用对象 | 机制 | 代码位置 |
|---|---|---|---|
| 📦 Slab 通道 | 1 ~ 2048 字节 | 8 个 2 的幂规格 + 空闲链表 | src/mm/slab.rs#L93-L117 |
| 🐘 big 通道 | 大于 2048 字节 | 连续虚拟区间 + 逐页映射 | src/mm/slab.rs#L175-L201 |
规格档位从 16 B 到 2048 B 按 2 的幂翻倍,这样最坏内部碎片只浪费不到一半,同时 find 第一个"装得下"的档位就完成了 O(1) 级别的路由——没有复杂的最佳适配扫描。
📦 二、三个核心数据结构:槽位、门牌与规格表
2.1 FreeSlot:空闲链表的"节点"
整个 Slab 分配器最精巧的一笔在这里(src/mm/slab.rs#L26-L29):
#[repr(transparent)]
struct FreeSlot {
next: *mut FreeSlot,
}
#[repr(transparent)] 保证它在内存中的布局就是一个裸指针。这意味着:
- 槽位空闲时,槽位自己的内存被借用为
next指针,指向链表中下一个空闲槽位; - 槽位被分配出去后,这段内存就是用户数据,无需任何额外空间。
链表的"指针"直接寄生在空闲内存本身,这是经典 Slab/伙伴式分配器 O(1) 摘除的关键。
2.2 SlabHeader:每个物理页的"门牌"
每分配一个物理页,页首都会写入一个 SlabHeader:
| 字段 | 类型 | 作用 |
|---|---|---|
link |
LinkedListLink |
让本页挂入 partial 链表(侵入式) |
slab |
*const Slab |
反向指针,指回所属规格档位 |
free |
Cell<*mut FreeSlot> |
该页空闲链表的头指针 |
used |
Cell<usize> |
已占用槽位计数 |
其中 slab 反向指针是释放路径的钥匙:dealloc 手里只有一个裸指针,靠"页首 → 所属 Slab"就能找回正确的 free 实现。Cell 则提供了无引用的内部可变性,配合手写 SpinLock 完成并发保护。
2.3 Slab:一个规格档位 = 一条 partial 链表
Slab 结构体只有两个字段:
ent_size:本档位的槽位大小;partial:SpinLock<LinkedList<SlabPageAdapter>>,只存放"部分空闲"的页。
两点值得注意:
- 链表来自 intrusive-collections 依赖(见 Cargo.toml 的
intrusive-collections = "0.10.3"),节点内嵌在SlabHeader.link中,链表本身不占用堆内存; - 锁是 src/locks/spinlock.rs 中的自研
SpinLock:加锁时先关中断,再 CAS +spin_loop自旋,保证 SMP 多核安全且不阻塞。
页内布局由 slot_offset() 决定:
fn slot_offset(&self) -> usize {
align_up(size_of::<SlabHeader>(), self.ent_size)
}
也就是把页首 SlabHeader 对齐到 ent_size 的整数倍,保证第一个槽位天然满足对齐要求:
┌──────────┬──────────┬──────────┬─────────┬─────────┐
│ SlabHeader │ slot 0 │ slot 1 │ ... │ slot N │
└──────────┴──────────┴──────────┴─────────┴─────────┘
对齐到 ent_size 后,槽位区开始(页内 4096 字节)
🪜 三、refill 逐行解读:一个物理页如何变成一串槽位
当某个规格档位的 partial 链表空了,refill() 负责从物理页分配器(PMM)"进货":
第 1 步:向 PMM 要一个物理页(src/mm/slab.rs#L61-L68)
let phys = match PMM.lock().as_mut()
.and_then(|p| p.alloc(PageUsage::KernelHeap)) { ... }
PMM 是 src/mm/phys.rs#L26 中的全局物理页分配器,内部是位图 + 页框数据库,alloc 采用带 last_freed_hint 提示的快速首适应扫描(src/mm/phys.rs#L58-L79)。要不到页就返回空指针,分配失败向上传递。
第 2 步:换算成内核虚拟地址(src/mm/slab.rs#L70)
let page = (phys + HHDM_OFFSET.load(Ordering::Relaxed)) as *mut SlabHeader;
HHDM_OFFSET 是高位直接映射(High Half Direct Mapping)的偏移量,在内核内存初始化时于 src/arch/x86_64/mminit.rs#L253 写入。物理地址加上这个偏移,就能直接在内核态访问该页——这就是"直接映射"省掉显式 map 调用的原因。
第 3 步:把整页槽位串成一条空闲链表(src/mm/slab.rs#L76-L80)
let first = (page as *mut u8).byte_add(offset) as *mut FreeSlot;
for i in 0..slots - 1 {
(*first.byte_add(i * self.ent_size)).next = first.byte_add((i + 1) * self.ent_size);
}
(*first.byte_add((slots - 1) * self.ent_size)).next = null_mut();
这里再次体现了 2.1 节的技巧:空闲槽位的自身内存被当作 next 指针写入,依次指向下一个槽位,最后以 null 收尾。slots = (PAGE_SIZE - offset) / ent_size 算出一页能切出多少个槽。
第 4 步:写入页首"门牌"(src/mm/slab.rs#L82-L87)。注意用的是 page.write(...) 而不是赋值——因为这块内存是刚拿到的裸物理页,用 write 避免对未初始化内存的读。
⚙️ 四、alloc 逐行解读:O(1) 从链表头部取槽
Slab::alloc 的核心只有五行:
let slot = page.free.get();
debug_assert!(!slot.is_null());
page.free.set(unsafe { (*slot).next }); // ① 摘头
page.used.set(page.used.get() + 1); // ② 计数 +1
if page.free.get().is_null() { // ③ 整页用满
cursor.remove(); // ④ 从 partial 链表摘除
}
完整路径拆开看:
- 锁住
partial链表(src/mm/slab.rs#L94); - 若链表为空,先
refill()进货,并把新页push_front入链(src/mm/slab.rs#L96-L102); - 取链表头部那一页(src/mm/slab.rs#L104-L105);
- 从该页空闲链表摘头,
used加一(即上面 ①②); - 若摘完发现该页已无空闲槽位,就用侵入式游标
cursor.remove()把整页从 partial 链表移除(③④); - 返回槽位地址。
全程就是"一次自旋锁 + 两次指针操作",没有扫描、没有每槽元数据——这就是 Slab 分配器对小对象分配的核心优势。对齐方面也很省心:槽位地址天然按 ent_size 对齐,而 ent_size 是 2 的幂且不小于 layout.align(),所以对齐要求自动满足,代码里仅用 debug_assert! 兜底(src/mm/slab.rs#L231)。
🔁 五、free 逐行解读:还槽、挂链与整页归还
释放入口在 GlobalAlloc::dealloc:
if ptr as usize == align_down(ptr as usize, PAGE_SIZE) {
big_dealloc(ptr);
} else {
let page = align_down(ptr as usize, PAGE_SIZE) as *mut SlabHeader;
(*(*page).slab).free(page, ptr);
}
逻辑很漂亮:指针是 4K 对齐的说明它是 big 通道的页首,否则 align_down 直接落回所在页的页首,再顺着 SlabHeader.slab 反向指针找到所属规格档位,调用 Slab::free。不需要任何分配元数据,页边界本身就是元数据。
Slab::free 先做头部插入(src/mm/slab.rs#L131-L135):
(*slot).next = page_ref.free.get(); // 指向当前链头
page_ref.free.set(slot); // 本槽成为新链头
let used = page_ref.used.get() - 1; // 计数 -1
随后根据 (was_linked, now_empty) 两个标志分三种情况处理(src/mm/slab.rs#L139-L151):
| 情况 | 判断条件 | 动作 |
|---|---|---|
| 🧹 整页被释放 | used == 0 |
若该页挂在 partial 链表上则摘除,再减去 HHDM_OFFSET 换回物理地址,交还 PMM |
| 📎 该页原本是"满页" | was_linked == false 且 used > 0 |
push_front 重新挂回 partial 链表 |
| 📂 页内部分空闲 | 其余情况 | 只做空闲链表头部插入,页面维持现状 |
归还 PMM 时(src/mm/slab.rs#L145-L146),PageAllocator::free 会先减引用计数、归零后再清位图位并更新 last_freed_hint——页框数据库的引用计数机制让同一物理页可被安全复用。
🚦 六、GlobalAlloc 入口:一次分配请求的完整分流
把前面的碎片拼起来,alloc() 的路由逻辑一目了然:
let effective = layout.size().max(layout.align());
if let Some(slab) = ALLOCATOR.slabs.iter()
.find(|slab| slab.ent_size >= effective)
{
return slab.alloc(); // 小对象 → Slab 通道
}
let num_pages = divide_up(layout.size(), PAGE_SIZE);
big_alloc(num_pages) // 大对象 → 逐页映射通道
一个值得玩味的细节:effective = size.max(align)。它把对齐要求折算进大小来选档位,而不是单独维护对齐逻辑——因为如前所述,槽位天然按 ent_size 对齐,而档位大小总是 2 的幂,这一招就把对齐问题"顺手"解决了。
🐘 七、大对象通道:big_alloc / big_dealloc
超过 2048 字节的请求交给 big 通道(src/mm/slab.rs#L173-L216):
- 先原子"圈地":
BIG_ALLOC_PTR从BIG_ALLOC_START起步(该常量定义在 src/arch/x86_64/mod.rs#L141,位于 PFN 数据库之后 1 TiB 处),fetch_add((pages + 1) * PAGE_SIZE)一步圈定连续虚拟区间; - 逐页落实:每页都向 PMM 申请物理页,再通过
KERNEL_ADDRESS_SPACE映射到刚圈定的地址,页表项带PRESENT | WRITABLE标志(映射函数见 src/mm/virt.rs#L39-L41); - 页首做头:
pages + 1中的第一页专门用来存"页数"这个 u64 头,数据区从base + PAGE_SIZE开始返回(src/mm/slab.rs#L195-L200)。
释放时 big_dealloc 从页首读回页数,逐页 unmap 并归还 PMM——与 Slab 通道"整页归还"的逻辑殊途同归。
💡 八、设计亮点与可改进之处
| 设计选择 | 收益 | 可改进空间 |
|---|---|---|
| 8 个 2 的幂档位 | 路由简单,最坏内部碎片 < 50% | 可加更细的档位表降低小对象浪费 |
| 空闲指针寄生于槽位自身 | O(1) 摘除,零额外内存 | — |
| 只维护 partial 链表,整页空闲立即还 PMM | 代码极简(全文不足 260 行) | 可增设"全空闲页"缓存,减少 PMM 往返 |
| 无每槽分配元数据 | 释放只需一个指针 | — |
big_alloc 先圈虚拟区间再分配物理页 |
保证虚拟地址连续 | 物理页申请失败时不回滚已圈区间,可能泄漏虚拟区间 |
| 每个档位一把自旋锁 | 实现简单、SMP 安全 | 高并发下同档位分配会串行化,可考虑每 CPU 缓存 |
📚 九、延伸阅读:相关文件清单
想顺着这条链路继续往下读,可以从这些文件入手:
| 文件 | 说明 |
|---|---|
| src/mm/slab.rs | 本文主角:Slab 分配器 + big 通道完整实现 |
| src/mm/phys.rs | PMM 物理页分配器:位图、页框数据库与引用计数 |
| src/mm/virt.rs | 内核地址空间与页表 map/unmap |
| src/mm/mod.rs | 内存管理模块总览(含 vmb、fault、stack 等) |
| src/locks/spinlock.rs | 关中断 + CAS 自旋的自研自旋锁 |
| src/arch/x86_64/mminit.rs | 内核内存初始化与 HHDM 偏移写入 |
| src/main.rs | 内核入口与用户 ELF 加载流程 |
一句话总结:Polaris 的 Slab 分配器用"规格档位 + 寄生式空闲链表 + 反向页首指针"三个极简构件,把内核堆的分配/释放压进 O(1) 的指针操作里;配合 PMM 的位图与引用计数,构成了一套麻雀虽小、五脏俱全的 Rust 内核内存管理骨架,非常适合作为学习操作系统内存分配器原理的入门教材。