内核已经能处理时钟中断和键盘事件，但新增数据仍依赖静态数组。
页表、任务栈或文件缓存需要动态取得内存时，必须知道哪些物理地址可以使用、哪些已经分配，以及释放是否有效。
本篇把第 04 篇取得的 E820 内存图转换成 4 KiB 物理页分配器。

实验仍使用单 CPU、64 MiB RAM 的 qemu32 模拟机，分页保持关闭。
分配器管理固定上限内的页框，返回物理地址；它不建立虚拟地址映射，也不提供任意字节大小的 malloc。
实测初始空闲页数为 16087，客体耗尽全部页面、验证每页数据并释放后，空闲数恢复为 16087。

E820 可用内存还需要扣除内核占用

E820 描述固件报告的系统地址范围。
内核已经装入内存，却不意味着固件会把这段地址从 type 1 区域里扣掉。
若直接把所有 type 1 页面交给调用者，分配结果可能覆盖正在运行的代码或栈。

ACPI 6.5 第 15 章定义了 BIOS 内存图接口和范围类型。
其中 type 1 表示可用 RAM；其他类型不能在本实验中直接当作普通空闲页。
低地址区域也可能有固件或引导程序用途，规范 §15.2要求调用方考虑这些特殊用途。

本篇采用明确的实验策略：保留低于 1 MiB 的全部地址，再保留内核完整运行区。
这会舍弃一部分原本可利用的低端 RAM，但使引导代码、BootInfo、E820 缓冲区和 VGA 等低地址用途都不会进入分配池。
“低于 1 MiB 全部保留”是当前内核的选择，不是 E820 对每个低地址字节的统一分类。

kernel/bootinfo.h 提取了此前的 40 字节 BootInfo 定义，字段布局不变。
内存图位于 0x5100，记录步长为 24 字节；初始化验证地址、步长以及 1 到 32 的记录数范围。
stage2 已把旧式 20 字节记录补为 24 字节，并把缺失的扩展属性规范化为 1。

1
2
3
4
5
6
struct e820 {
    uint64_t base, length;
    uint32_t type, attributes;
};
_Static_assert(sizeof(struct e820) == 24,
               "normalized E820 stride");

记录中的地址和长度仍然是 64 位。
32 位内核和 64 MiB 管理上限都不能成为提前截断字段的理由：高地址记录截成 32 位后，可能错误地落回低地址。

两个位图分别记录可分配资格和当前占用

64 MiB 除以 4 KiB，共有 16384 个页框。
一个页框对应一个 bit，每个位图需要 2048 字节。
实现使用两个静态位图，总计 4096 字节，放在 BSS 中。

1
2
3
4
5
6
7
#define PAGE_BYTES 4096u
#define MEMORY_CAP (64u * 1024u * 1024u)
#define FRAMES (MEMORY_CAP / PAGE_BYTES)

static uint8_t eligible[FRAMES / 8];
static uint8_t allocated[FRAMES / 8];
static uint32_t free_pages, next_frame;

eligible 位图中页号 n 对应的 bit 为 1，表示第 n 页通过内存图和内核保留规则，允许被分配。
allocated 位图中页号 n 对应的 bit 为 1，表示这页目前已由分配器交出，尚未释放。
可用页必须同时满足 eligible=1 和 allocated=0。

eligible allocated 含义
0 0 保留或不受管理，不能分配
1 0 空闲且允许分配
1 1 已分配，可以由持有者释放
0 1 正常操作不应产生的状态

只有一个“忙碌”位图时，永久保留页和暂时分配页容易混在一起。
两张图使释放函数能检查页面是否原本就有分配资格，避免一次错误释放把内核页变为空闲页。
位操作的字节索引是 n / 8，字节内位置是 n % 8；物理地址则是 n * PAGE_BYTES。

先验证区间，再做截取和取整

初始化先清空两张位图，所有页面默认不具备分配资格。
它首先检查整张图的长度与加法合法性，之后才处理 64 MiB 上限。
零长度或地址加法溢出会令 map_build 返回失败，真实初始化通过断言停机。

1
2
3
4
for (unsigned i = 0; i < count; ++i)
    if (!map[i].length ||
        map[i].length > UINT64_MAX - map[i].base)
        return 0;

判断 length > UINT64_MAX - base 不需要先执行可能溢出的加法。
例如 base=UINT64_MAX-7、length=16 必须在此被拒绝。
如果因为 base 已经超过管理上限就提前跳过，这张畸形图反而会被接受。

合法记录使用半开区间 [base, base+length)。
起点不小于 64 MiB 的记录不贡献页面；其余记录把终点截到 64 MiB，再转成 32 位数值。
经过这个步骤，后面的页对齐加法不会接近 32 位上限。

可用区只能释放完整落在区间内的页面，因此向内取整。
保留区必须覆盖所有与它相交的页面，因此向外取整。
源码中的 first、last 是页号，遍历范围同样是左闭右开。

1
2
3
4
5
6
unsigned first = reserve
    ? start / PAGE_BYTES
    : (start + PAGE_BYTES - 1) / PAGE_BYTES;
unsigned last = reserve
    ? (end + PAGE_BYTES - 1) / PAGE_BYTES
    : end / PAGE_BYTES;

例如可用区 [0x200001, 0x20a000) 只允许页首从 0x201000 到 0x209000 的页面。
0x200000 页缺了第一个字节，不能整页交出去。
若保留区是 [0x203fff, 0x204001)，虽然只有两个字节，也必须同时保留 0x203000 和 0x204000 两页。

保留记录覆盖可用记录

本实现仅接受 type == 1 && attributes == 1 的记录来增加可分配页。
其他类型、未知类型及不兼容属性都会进入保留遍历。
ACPI 6.5 将扩展属性 bit 0 定义为 reserved、must be 1，并没有把它命名为 Enabled；这里只接受属性值恰好为 1，是实验采用的保守兼容策略。

仅检查 attributes & 1 会同时接受值为 9 的记录。
该值还带有 bit 3，涉及错误日志内存；当前分配器没有处理这种用途的逻辑，因此整段按保留处理。
对于属性值 0，也不把相关页面释放成普通 RAM。

初始化分成两遍：先设置所有接受的可用页，再清除所有保留范围相交的页。
因此交换一条可用记录与一条保留记录的顺序，不会改变最终结果。
这是本实现的重叠处理规则，不声称 ACPI 规定了这种遍历次序。

1
2
3
4
5
6
7
8
9
eligible 全 0
    ↓
第一遍：接受的 type 1 区间，向内取整后置 1
    ↓
第二遍：其余区间，向外取整后清 0
    ↓
清除低于 1 MiB 和内核运行区相交的页
    ↓
统计 eligible 中的 1，得到 free_pages

多条可用记录重叠时，只会重复设置相同 bit，不会重复计数。
free_pages 在所有保留规则执行完之后统一统计，也避免了边遍历区间边累加造成的重复计算。

内核边界必须包含 BSS、位图和栈

链接脚本中的 __file_end 位于 .data 后面，只能描述文件装载部分。
.bss 和 .stack 都标记为 NOLOAD，仍然占用运行内存。
若用内核二进制文件大小计算保留范围，位图和栈就可能被分配器交给其他用途。

1
2
3
4
5
6
7
8
9
10
11
12
13
__file_end = .;
.bss (NOLOAD) : {
    __bss_start = .;
    *(.bss*) *(COMMON)
    __bss_end = .;
} :data
.stack (NOLOAD) : {
    . = ALIGN(16);
    __stack_bottom = .;
    . += 16384;
    __stack_top = .;
} :data
__kernel_end = .;

本次链接结果是 __kernel_start=0x100000、__kernel_end=0x108d70，运行区占用 36208 字节。
链接脚本仍断言运行区不超过此前加载协议的 65536 字节上限。
尾端所在页面也必须完整保留，因此第一个可能交出的内核后页面是 0x109000，能否分配还取决于 E820 图。

两张静态位图位于 BSS，已经由这个运行区间保护。
若以后把元数据改为动态存储，就需要在初始化中单独保留其页面，不能继续依赖当前链接位置。

分配最低空闲页，释放时验证状态

对外接口只有三个函数，地址类型为 uint32_t。
页零已经保留，因此分配返回 0 可以明确表示耗尽。
释放成功返回 1；无效地址或当前没有分配所有权时返回 0，空闲计数不变。

1
2
3
uint32_t page_alloc(void);
int page_free(uint32_t address);
uint32_t page_free_count(void);

page_alloc 从 next_frame 开始向上扫描。
发现 eligible=1 && allocated=0 后，设置占用位、减少空闲计数，并把候选位置移到下一页。
成功返回的地址总是 4 KiB 对齐，新页面的内容不保证清零。

next_frame 保持最低可能空闲位置的提示。
释放更低的页号时，函数将提示降低到该页；因此跳过提示之前的位置不会漏掉低地址空闲页，分配结果仍是最低空闲页。
连续耗尽过程中不必每次从页号零重新查找，避免累计扫描退化为平方级。

释放函数首先检查地址低于管理上限且按页对齐，然后检查两张位图。
核心状态变化如下，外围的中断保护与完整版本一致保留在附件源码中。

1
2
3
4
5
6
7
8
9
if (address < MEMORY_CAP && address % PAGE_BYTES == 0) {
    unsigned n = address / PAGE_BYTES;
    if (bit(eligible, n) && bit(allocated, n)) {
        clear(allocated, n);
        ++free_pages;
        if (n < next_frame) next_frame = n;
        ok = 1;
    }
}

检查能拒绝保留页释放，也能拒绝释放后尚未再次分配的 double free。
但接口只接收地址，无法识别页面被释放、重新分配后，旧持有者又提交相同地址的 ABA 情况。
调用方仍必须遵守页面生命周期；位图不记录对象身份或分配代次。

临界区恢复调用前的 IF

位图、空闲计数和候选位置属于同一次状态变更。
单 CPU 下，保存 EFLAGS 后关闭可屏蔽中断，可以避免中断处理路径在中途重入分配器。
退出时恢复原来的 flags，不能直接无条件执行 sti。

1
2
3
4
5
6
7
8
9
10
11
12
static uint32_t irq_save(void)
{
    uint32_t flags;
    __asm__ volatile("pushfl; popl %0; cli"
                     : "=r"(flags) : : "memory");
    return flags;
}
static void irq_restore(uint32_t flags)
{
    __asm__ volatile("pushl %0; popfl"
                     : : "r"(flags) : "memory", "cc");
}

分配、释放和空闲计数快照都使用这组函数。
客体测试分别在 IF=0 和 IF=1 的状态下调用，并检查返回后 IF 保持原值。
这只覆盖当前单 CPU 实验；关闭本 CPU 中断不提供 SMP 互斥，也不能据此宣称支持多核分配。

初始化与日常分配的约束不同。
map_build 会清空状态，只能在尚无活动分配的初始化阶段使用；合成内存图测试完成后，再使用真实 E820 图重新初始化。
它没有提供运行中热替换内存图的接口。

客体测试覆盖耗尽和完整恢复

合成图先验证区间算法，真实固件图随后验证页面读写。
两者调用同一个初始化实现，但合成的溢出、高地址和重叠记录不是 SeaBIOS 实际返回的异常记录。
合成测试还包括记录顺序交换、未知类型、不兼容属性、64 MiB 边界截取与零长度拒绝。

真实图测试先分配两页并写入不同值，确认地址不同、按页对齐且数据可读回。
随后检查未对齐地址、页零、内核地址和管理上限地址被拒绝，并验证重复释放不增加计数。
这些检查完成后恢复初始空闲数，再进入耗尽阶段。

耗尽循环为每页全部 1024 个 uint32_t 写入 address ^ j。
分配返回 0 后，检查分配页数等于初始空闲数；释放最后一页，再分配必须取回同一页，之后再次返回 0。
最终扫描占用位图，逐页验证全部模式并释放，空闲数必须恢复到初值。

测试直接复用占用位图查找待释放页，没有另建 64 KiB 的页面地址数组。
因此测试元数据不会把内核运行区撑破既有 64 KiB 上限。
写入测试使用的物理地址可以直接转换为指针，是因为当前平坦段模型下分页关闭；未来启用分页后，这种转换必须满足映射条件。

本次固定模拟机返回 6 条 E820 记录，串口结果包括：

1
2
3
4
5
6
E820 records=6 free=16087 kernel_end=0x108d70
allocator preserves IF=0 and IF=1 OK
unique/write/free OK; invalid/double free rejected
exhausted=16087 one-page reuse OK
all-page patterns OK recovered=16087
MEMORY OK

物理页分配器完成耗尽、逐页模式校验与恢复的客体画面

check-memory 在 memory_demo_done 断点读取客体位图、计数和 CR0，检查分页仍关闭、占用位全部清零、保留页没有取得分配资格。
截图发生在键盘界面清屏之前；检查随后继续运行到 keyboard_ready，确认内存实验没有阻断原来的输入入口。
画面中的成功行来自客体，截图也来自 QEMU 显示设备，不是宿主绘制的结果示意图。

下载与复现

下载第 10 篇完整源码，解压目录前缀为 os-day-10。
源码冻结提交为 a741ef8100940da4d0fbb20deabfd8454ee9f1ed，实现位于 examples/build-an-os。
继续使用第 01 篇已经准备好的 localhost/build-an-os:day01 容器镜像。

1
2
3
unzip os-day-10-source.zip
cd os-day-10/examples/build-an-os
podman run --rm -v "$PWD:/work" -w /work localhost/build-an-os:day01 make check-memory

完整回归使用相同目录和镜像执行 make check。
本篇源码附件在独立解压目录中执行完整回归并通过，包含原有保护模式、BSS、控制台、异常、时钟、键盘和读盘故障检查，以及新增的物理页检查。
本篇产物保存在 build/memory-serial.txt、build/memory-gdb.txt、build/memory-vga.txt 与 build/day10-screen.png；具体检查边界记录在 docs/day10-evidence.md。
这里的实测结论限于 QEMU、单 CPU、64 MiB、分页关闭的配置，不涵盖真实硬件、DMA 或多核并发。

练习

  1. 把合成图中的两字节保留范围移动到一个页边界之后，预测保留页数，再通过客体断言核对向外取整结果。
  2. 在已分配若干页后释放较低地址页，验证下一次分配返回该页，并解释为什么提示不需要环形扫描。
  3. 给新分配页面增加可选的清零入口，保留现有原始接口；检查耗尽与恢复测试，并说明清零和取得页面所有权的先后关系。

上一篇：09 - 键盘与事件队列。

下一篇：11 - 分页与页故障，使用物理页建立分页结构，区分页框所有权与虚拟地址映射。