起因

系列里"从内存映射里划一块"“DMA 池"“后备缓冲"这类说法出现过无数次，但那根负责"划"的手指——分配器本身——一直没有正面写过。这是基础篇里最大的一块地基：没有它，Vec/Box 用不了，网络包缓冲、字体资源、文件目录列表全都没有出处。这篇补上：从 UEFI 内存映射出发做一个物理页帧分配器，在其上搭内核堆，再划出 DMA 专用池，最后说清楚实时层为什么一分钱内存都不能现场要。这门手艺本身没有新东西可发明：位图、空闲链、伙伴系统全是六十年前就定型的方法，Knuth 的《计算机程序设计艺术》第一卷 1968 年就把这摊事讲透了；DMA 必须低地址连续内存的执念则来自 IBM PC 的 8237 控制器——24 位地址线顶到 16MB，“设备只认低地址"这个约束一路遗传到今天的 PCIe 设备。功夫全花在选哪门老手艺最配这台机器。

一、原材料：把 UEFI 内存映射变成可用区表

ExitBootServices 之前拿到的内存映射是分配器的全部家底。先把类型翻译成"能用/不能用”：

处理三步，全是纯数组操作：先按起始地址排序——UEFI 不保证映射有序；再合并物理上首尾相接的同类区段——前一段 start+len 恰好等于后一段 start 才合，中间夹着洞的坚决不合，洞里可能是 MMIO；最后显式减去保留区：内核映像自身、AP 唤醒用的 1MB 以下实模式蹦床页、HPET 等 MMIO。产出一张排好序、互不重叠的 [(start, len)] 可用区表——之后页帧分配器只认这张表，UEFI 的原始映射就此封存。

坑：GOP 帧缓冲不一定出现在内存映射里，必须拿 Handoff 里的 GOP 五元组显式排除，否则第一次"恰好"分到显存上写分配数据，屏幕花掉的同时堆也废了。

坑：物理地址上限别硬编码。 CPUID.80000008H:EAX[7:0] 给出物理地址位数，位图大小按它算，不按 4GB 假设。

二、页帧分配器：位图 + 首次适应

为什么选位图不选 buddy/空闲链：专用系统内存量固定（4~16GB），16GB/4KB/8B = 512KB 位图，换来的是 O(1) 的占用查询和最好的可调试性——内存布局一眼看全。首次适应的 O(n) 扫描在稳态分配频率下完全够用：稳态的爆发由各处的池子吸收，页帧分配器只负责"开新池"这个低频动作。

分配方向：从高地址向低地址扫描。低地址留干净，给"必须连续/必须低于 4GB"的特殊需求让路。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

pub struct FrameAllocator {
    bitmap: &'static mut [u64],   // 每位一页，1=占用
    base: PhysAddr,               // 位图对应的起始物理地址
    total: usize,
    free: usize,
}

impl FrameAllocator {
    /// 单页：从高往低找 0 位，置 1 返回
    pub fn alloc_frame(&mut self) -> Option<PhysAddr> { ... }
    /// 连续 n 页；limit 限定物理上限（DMA 例外需求用）
    pub fn alloc_contiguous(&mut self, n: usize, limit: PhysAddr) -> Option<PhysAddr> { ... }
    pub fn free_frame(&mut self, p: PhysAddr) { ... }
}

位图本身的放置：初始化期从最高可用区顶部切一段，DMA 池紧接着切——都发生在分配器正式开门营业之前。

扫描实现别逐位循环：按 u64 字扫，!word 之后用 leading_zeros() 从高位往低位找空闲页（我们高地址向下，字也从最后一个往前遍历；反过来低地址方向就是 trailing_zeros()），整字全 1 直接跳过。alloc_contiguous 找"连续 n 个 0"用朴素游程：从 limit 之下逐页累计，碰到 1 就清零重来——n 不大（DMA 池一次几十页）时这就够，别为此上树状结构。地址换算固定两条：idx = (p - base) >> 12，p = base + (idx << 12)；位图管辖范围之外的地址一律拒绝——free 一个不属于分配器的指针，等于往别人内存里埋雷。

坑：释放越界/双重释放在位图上等于静默破坏。 free_frame 里先查该位原值，为 1 才允许清 0，否则拒绝并记一条 ERROR——这是日志系统的第一个用户。

统计常驻：free/total/峰值高水位放一个结构体，开机自检报告直接读它。

三、内核堆：页帧之上的一级分配

页帧粒度 4KB，业务要的是 8B~几百 KB。内核堆 = 从页帧分配器按需扩容的一级分配器，结构用显式空闲链 + 头尾冗余（Knuth 式，支持 O(1) 前向合并）：

• 分配：首次适应，找到的块剩余 ≥64B 才分裂
• 释放：改状态 → 尝试与后块合并 → 用 footer 定位前块再向前合并
• magic 用于踩坏/double-free 检测，崩在堆上至少知道是谁
• 单次上限 1MB、对齐最高 16B——更大的或更苛的（对齐、物理连续）需求是静态池和 DMA 池的事，堆不接这种活

然后是最有性价比的一步——接上 core 的分配器接口，Vec/Box/String 立刻可用：

1
2
3
4
5
6
7

unsafe impl GlobalAlloc for Heap {
    unsafe fn alloc(&self, l: Layout) -> *mut u8 { ... }
    unsafe fn dealloc(&self, p: *mut u8, l: Layout) { ... }
}

#[global_allocator]
static HEAP: Heap = Heap::new();

坑：对齐 >16 的 Layout 不走堆。 EHCI 的 32B 对齐 QH/qTD、FPGA 卡的命令环是 DMA 池的事，堆只服务服务层的一般对象。

坑：OOM 在这个系统里没有"杀手"可以求救。 设计纪律是关键路径开机预留（各池初始化期一次到位），堆只给界面字符串、文件列表这类"缺了也不断电停产"的东西用，耗尽返回 null 并记 ERROR。

坑：realloc 别玩花活，alloc+copy+dealloc 三段式最不容易错。

四、分配权归属：两级调度与双核下的铁律

分配器架构定了，更要紧的是"谁允许分配”：

锁的实现是短临界区自旋锁，但按归属表稳态下根本无竞争——锁是给"抓违规"的断言用的，不是给性能用的。初始化顺序上，页帧分配器在 SMP 唤醒（SIPI）之前建好，运行期归属 Core1，天然无竞争。

坑：ISR 里调用一个"内部会 alloc 的函数"是最隐蔽的违规——比如格式化字符串往 String 里拼。实时层的日志走固定缓冲（日志篇展开）。

栈的保护要诚实：沿用固件 identity 分页、不重建页表（CPU 自举篇的决策），就没有 guard page 可用。替代手段：TSS 每类中断固定大小专用栈 + 初始化时填 0xAA 花纹、周期扫描算"栈最深用到哪”（高水位线），自检报告里盯余量；递归在实时层直接禁掉。要真正的页保护得走"重建页表"那条升级线，那是另一篇文章的事。

五、DMA 池：给设备的一块自留地

设备 DMA 有两个要求堆给不了：物理连续、（很多设备）32 位以内可达。EHCI 的 QH/qTD 要 32B 对齐连续（HCCPARAMS bit0 为 1 才支持 64 位指针，即便支持也统一低 4GB 简化）；老网卡常见 32 位限制；自研 FPGA 卡的 PCIe 逻辑为了简单也常按 32 位地址设计。

所以开机就从"低于 4GB 的连续物理区"一刀切出 16~32MB 的 DMA 池，池内分级空闲链：

x86 的一个福利：DMA 与 CPU 缓存硬件一致（snooping），不需要 ARM 上那套 flush/invalidate 仪式；帧缓冲的 WC 优化另议（显示篇）。

池子和堆的关系一句话：设备侧的一切（队列、环、包缓冲）进池；服务侧的一切进堆。 FPGA 运动控制卡的命令环/状态环在初始化期从池里切出来后归属就固定了——实时核 ISR 写命令环、FPGA 回 MSI、状态环由服务核消费，全是预分配内存上的无锁操作，运行期一分钱分配都没有。这个"初始化期切池、运行期零分配"的模式，就是以后所有 PCIe 卡适配层的标准姿势——系统层提供池子和环模板，卡写在应用层。

总结

实战清单：类型表过滤+合并+显式排除得可用区表；位图页帧分配器（高地址向下的首次适应 + limit 连续分配）；Knuth 头尾冗余空闲链堆 + #[global_allocator]；分配权归属表进代码审查清单；低 4GB 一刀切 DMA 池 + 分级子分配；栈高水位 0xAA 花纹监控。跑通标志：十万次随机大小 alloc/dealloc 全程 0xA5 校验通过；Vec<u8>/Box 在服务核正常工作；满负荷跑 1 小时后 free 计数回到基线（无泄漏）；栈高水位余量 > 50%。

下一篇：把这套地基第一次用在真设备上——U 盘的 USB 大容量存储驱动。

参考链接

• OSDev Wiki: Page Frame Allocation / Heap
• Writing an OS in Rust — allocator 设计（自由链/伙伴分配的对照阅读）
• 本系列：UEFI固件层实战（内存映射出处）、CPU自举实战（TSS 专用栈）、调度模型、CPU信息与多核实战