Polaris内核堆剖析:Slab分配器从GlobalAlloc到空闲链表的逐行解读

原创2026-11-15 10:21:59628 阅读

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>>,只存放"部分空闲"的页。

两点值得注意:

  1. 链表来自 intrusive-collections 依赖(见 Cargo.toml 的 intrusive-collections = "0.10.3"),节点内嵌在 SlabHeader.link 中,链表本身不占用堆内存;
  2. 锁是 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 链表摘除
}

完整路径拆开看:

  1. 锁住 partial 链表(src/mm/slab.rs#L94);
  2. 若链表为空,先 refill() 进货,并把新页 push_front 入链(src/mm/slab.rs#L96-L102);
  3. 取链表头部那一页(src/mm/slab.rs#L104-L105);
  4. 从该页空闲链表摘头,used 加一(即上面 ①②);
  5. 若摘完发现该页已无空闲槽位,就用侵入式游标 cursor.remove() 把整页从 partial 链表移除(③④);
  6. 返回槽位地址。

全程就是"一次自旋锁 + 两次指针操作",没有扫描、没有每槽元数据——这就是 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):

  1. 先原子"圈地":BIG_ALLOC_PTR 从 BIG_ALLOC_START 起步(该常量定义在 src/arch/x86_64/mod.rs#L141,位于 PFN 数据库之后 1 TiB 处),fetch_add((pages + 1) * PAGE_SIZE) 一步圈定连续虚拟区间;
  2. 逐页落实:每页都向 PMM 申请物理页,再通过 KERNEL_ADDRESS_SPACE 映射到刚圈定的地址,页表项带 PRESENT | WRITABLE 标志(映射函数见 src/mm/virt.rs#L39-L41);
  3. 页首做头: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 内核内存管理骨架,非常适合作为学习操作系统内存分配器原理的入门教材。

登录后查看全文
Polaris