物理页分配器每次交出 4096 字节，队列节点、字符串和小结构体却通常用不满一页。
本篇在已经建立恒等映射的物理页内实现 kmalloc 和 kfree，按请求长度分配空间，并在释放时合并相邻空闲块。
堆最多持有四个独立页面，返回地址按 16 字节对齐，单次请求上限为 4076 字节。

实验继续运行在单 CPU、64 MiB RAM 的 qemu32 环境中，所有代码位于 ring 0。
正常镜像验证不同大小的读写、真实耗尽和回收；独立故障镜像破坏对象尾部标记，记录拒绝结果后主动进入诊断停机。
尾部标记由软件检查，越界写入发生时不会因此自动产生硬件异常。

页分配和字节分配各自管理什么

page_alloc() 依据 E820 和保留区规则选择可用物理页，返回物理地址。
它只记录页面归属，不知道页内有几个对象，也不知道其中某个对象申请了多少字节。
如果一个 17 字节对象独占一页，剩余空间仍然被这次页分配占用。

堆从页分配器取得整页，再用块头描述页内区间。
同一页可以同时容纳多个对象，释放一个对象后，其他对象继续有效。

分页还提供了另一项必要条件：这些物理字节必须能被当前虚拟地址访问。
第 11 篇保留低 64 MiB 恒等映射，本篇取到的页面位于该窗口内，可以用同值线性地址访问。
如果以后撤销恒等映射，堆就必须改用明确建立的虚拟映射，不能继续把物理地址直接转换成指针。

这里的地址转换依赖本实验的编译器、32 位 x86 目标和内存布局约定。
WG14 N1570 §6.3.2.3、§7.20.1.4描述了整数与指针转换，以及可选 uintptr_t 类型的有效指针往返能力。
它们不保证任意物理地址整数都能在任意 C 实现中变成可访问对象，也不把内核的物理内存操作变成严格可移植 C。

四张页分别作为 arena

arena 是堆管理的一段连续区域。
本篇用 arenas[4] 保存四个页基址，每个非零元素独立管理 4096 字节。
初始数组为空，只有搜索走到尚未使用的槽位时，才向物理页分配器申请页面。

连续调用四次 page_alloc() 不构成物理连续性的接口保证。
即使某次运行恰好取得相邻页，本实现也不跨页分配或合并。

arenas[0] → 一张页：[已用块][空闲块][已用块]
arenas[1] → 一张页：[空闲块                  ]
arenas[2] → 0，尚未取得页面
arenas[3] → 0，尚未取得页面

四页总共提供 16 KiB 原始空间，但不能满足一次 8 KiB 请求。
需要跨页大对象时，应另行设计连续虚拟区域或专门的大块分配路径。

块跨度与请求长度必须分别保存

块头由四个 32 位字段组成，静态断言要求其大小恰好为 16 字节：

1 2	`struct block { uint32_t span, requested, used, tag; }; _Static_assert(sizeof(struct block) == HEADER, "aligned heap header");`

span 包含整个块，从块头起点一直到下一块起点。
requested 只表示调用者申请的字节数；used 为 0 或 1；tag 用于检查元数据是否出现预期外变化。

块起点 b
│ 16 字节块头 │ requested 字节载荷 │ 4 字节尾标记 │ 对齐余量 │
              ↑ 返回给调用者的 p  ↑ p + requested
│←                         span                          →│

页起点和块跨度共同保证每个块头按 16 字节对齐，载荷地址加 16 后仍然对齐。
这只是当前接口承诺；不能由此推导它支持任意更高对齐要求的类型，或满足所有平台 ABI。

N1570 §6.2.8把对齐描述为对象地址需要满足的约束。
对齐检查通过，也不等于任意字节数组自动获得所有类型的有效类型与访问语义；该问题还受 §6.5 的规则约束。
本实验使用映射好的物理页和既定目标工具链，不把一个对齐的静态字符数组宣称为通用可移植分配器。

先检查整数加法，再向上取整

申请 n 字节时，至少需要块头 16 字节、载荷 n 字节和尾标记 4 字节。
为了把总长度向上取整到 16 的倍数，还会先加 15。
这些加法本身可能溢出，不能先算出结果，再根据已经回绕的结果判断是否合法。

1
2
3

if (!n || n > SIZE_MAX - HEADER - 4 - 15) return 0;
uint32_t need = (n + HEADER + 4 + 15) & ~15u;
if (need > PAGE_BYTES) return 0;

这里几个附加量都是固定小常数，所以一次上界比较覆盖了整个加法链。
超过一页的结果也直接失败，尚未进入临界区，更没有修改堆状态。

请求 n	含头与尾的长度	对齐后的 need
1	21	32
15	35	48
16	36	48
17	37	48
4076	4096	4096

最小非空对象占用 32 字节，单页因此最多容纳 128 个最小块。
4077 字节已经放不进一页，哪怕另外三张页完全空闲也必须返回失败。
测试包含 SIZE_MAX 和 SIZE_MAX - 20，后者专门覆盖总量向上取整之前的加法边界。

用跨度串起块序列

本实现没有额外分配空闲链表节点，也没有在块头保存 next 指针。
从页内偏移零开始，以 off += b->span 到达下一块，直到刚好覆盖整页。

搜索按 arena 槽位顺序进行，每页又按地址递增顺序进行。
第一个未使用且 span >= need 的块被选中，即 first fit。
算法不试图寻找余量最小的块，因而释放后可能产生暂时不能满足较大请求的碎片。

申请新 arena 时，先调用 page_alloc()，成功后才写入槽位，并初始化一个覆盖全页的空闲块。
失败则直接退出，原来已经取得的 arena 继续保留。
由于每个请求都能放入单页，一次分配不需要先取得多页再处理部分成功回滚。

每次有效大小的分配会先检查全部现有 arena，随后才搜索可用块。
最多四页、每页最多 128 块的限制使这条路径有明确上界，但它仍是线性遍历。
对象规模或中断延迟要求增长后，才需要考虑空闲索引、大小分类等结构。

first-fit 在交替分配释放不同大小对象后，可能产生总量充足但无法满足单次较大请求的外部碎片（external fragmentation）。本实现的合并逻辑可以回收物理相邻的空闲块，但不能跨 arena 合并，也不能移动已分配对象来整理空间（即不具备 compaction 能力）。

剩余 32 字节可以分裂，16 字节不能

找到可用块后，只有剩余空间至少容纳一个最小块，才建立第二个块头。
否则整块分配给当前对象，额外空间继续计入 span。

uint32_t span = b->span;
if (span - need >= MIN_BLOCK) {
    header((void *)((char *)b + need), span - need, 0, 0);
    span = need;
}
header(b, span, n, 1);

申请 4044 字节时，need=4064，余下恰好 32 字节还能满足一次 1 字节请求。
申请 4060 字节时，need=4080，只余 16 字节，因此实际块跨度保持 4096。

16 字节只能放块头，放不下非空载荷与尾标记，把它留成独立空闲块会破坏最小块约定。
即使整块被占用，调用者也只能写入最初请求的 n 字节。
分配器保留的余量不属于调用者，尾标记仍紧挨请求末端。

尾标记紧贴请求末端

17 字节对象的尾标记位于 p + 17，这个地址不保证按四字节对齐。
源码通过已有字节复制函数写入和读出检查值，避免构造未对齐的 uint32_t * 解引用。

1
2
3

uint32_t tail = CANARY;
answer = (char *)b + HEADER;
memcpy((char *)answer + n, &tail, 4);

如果把标记放到对齐后块容量的末尾，p[17] 可能只改到填充区，检查仍然通过。
紧贴 requested 的布局可以在后续检查中发现本实验的一字节尾部破坏。
载荷最后一个合法字节是 p[16]，p[17] 已经越过接口允许范围。

canary 值固定为 0xcafebabe，这里只承担调试诊断。
它不能阻止写入，也不能保证发现跨过标记的写入、恰好写回原值的破坏或释放后访问。
第 11 篇的页故障由 CPU 在访问当时触发，本篇的标记损坏由下一次堆检查发现，两者时机不同。

释放前从可信边界查找地址

kfree(p) 不能直接把 p - 16 当块头读取。
调用者可能传入零、VGA 地址、载荷内部地址，甚至完全没有映射的数值。
先解引用推测出来的块头，会让非法释放在验证之前造成内存访问错误。

本实现先验证由 arena 数组描述的现有块序列，再遍历合法块头。
只有 p 恰好等于某个块头加 16，且该块仍处于使用状态，才允许释放。

if ((uintptr_t)p == (uintptr_t)b + HEADER) {
    if (!b->used) goto done;
    /* 合并相邻空闲块，然后返回成功。 */
}

单纯满足 16 字节对齐仍然不够，载荷内部的对齐地址不会被当作新对象。
测试用对象内部地址、0xb8000 和零验证拒绝分支，并检查拒绝前后的页内容指纹与空闲页数相同。

已经释放且尚未复用的指针再次传入也会被拒绝。
如果合并改变了原来的块边界，第二次释放可能表现为“找不到合法载荷地址”，不一定能分类成“重复释放”。

先校验全堆，再修改一个块

遍历本身也依赖元数据，损坏的 span 可能导致越界、停滞或者错误地解释载荷。
valid() 要求 span 不小于 32、为 16 的倍数，并且不超过 PAGE_BYTES - off。
这个减法形式在已知 off 位于页内时检查剩余容量，避免先计算一个不可信的结束地址。

校验还要求 used 只能为 0 或 1，tag 必须与当前字段和块地址重新计算的值一致。
已用块的 requested 必须非零，并能在 span 内放下块头和四字节尾标记；随后读取尾标记比较。
空闲块则要求 requested 为零。

1 2	`return 0x48454150u ^ (uintptr_t)b ^ b->span ^ b->requested ^ b->used;`

XOR tag 能发现本实验中没有同步更新 tag 的跨度改动，但不是密码学完整性保护。
知道计算方式的写入者可以伪造一致字段，异或也存在碰撞。
arena 数组本身和底层映射属于当前实现信任的内核状态，这个检查器不覆盖任意内核内存破坏。

只要任意现有块校验失败，kmalloc 与 kfree 都拒绝继续操作，包括针对其他完好块的请求。
这一选择避免沿着损坏的布局继续修改状态，代价是一个块的损坏会阻止整个小堆正常工作。
测试会故意翻转尾标记或 span，验证拒绝不改变页内容，再恢复该字节或字段以继续其他用例。

向右合并，再向左合并

释放时，搜索过程已经保留本页的前一块 previous。
当前块的后继则由当前起点加 span 得到；只有后继仍在页内且为空闲块，才将它的跨度加入。
随后把当前块设为空闲，如果 previous 也空闲，再把合并后的跨度加入 previous。

1
2
3

释放 B 前：[A 空闲][B 已用][C 空闲][D 已用]
先合右侧：[A 空闲][B+C 空闲     ][D 已用]
再合左侧：[A+B+C 空闲          ][D 已用]

这两个合并都发生在同一个 arena 内，物理相邻但属于不同 arena 的块也不会合并。
合并后，旧内部块头不必全部擦除，因为新的跨度会越过它们，后续遍历不再把它们当边界。
恰好命中旧载荷地址的指针也不会绕过这条边界遍历规则。

first fit 测试先分配三个 17 字节对象，释放中间对象，再要求同大小分配复用该地址。
随后交错释放，验证向左右合并后能恢复较大的连续空闲区间。
后面的最大对象分配还会检验四页分别恢复为完整空闲块，避免仅凭释放返回成功判断空间已经合并。

原始指针接口仍存在地址复用限制：对象 A 释放后，对象 B 可能取得同一地址。
此时保存的 A 旧指针与 B 当前指针具有相同地址值，kfree 无法知道调用者意图释放哪一代对象。
这是 stale-pointer ABA 情形；当前实现不具备通用 use-after-free 检测能力。

临界区恢复进入前的 IF

分配和释放都会遍历、验证并修改多个块，不能让普通可屏蔽中断在修改中途重新进入同一堆操作。
入口保存 EFLAGS 后执行 CLI，所有出口恢复保存值。
直接在出口无条件 STI 会破坏原本就关闭中断的调用者状态。

堆内部调用 page_alloc() 时，页分配器也会保存并恢复 IF。
内层进入时 IF 已经为零，因此内层恢复后仍然为零，只有外层退出时才恢复更早的状态。
测试分别检查 IF=0、IF=1 下的分配，以及 IF=1 下的释放，确认返回后 IF 保留。
当时 PIC 仍全部屏蔽，因此这些标志检查不构成真实时钟抢占压力测试。

这项保护只适用于当前单 CPU 的普通可屏蔽中断交错。
CLI 不屏蔽 NMI，也不能排除另一个 CPU 同时访问内存；扩展到 SMP 需要额外同步机制。
临界区内也没有日志输出或主动切换任务，遍历期间关闭中断的时间由当前有界堆规模限制。

真实耗尽，再归还页面

底层失败用例先取得一个最小堆对象，再不断调用 page_alloc()，直到真实空闲页数降到零。
每张临时页面用开头四字节保存前一张页地址，形成可逆的回收链，不额外申请记录数组。
此时请求 4076 字节：已有 arena 因小对象占用而放不下，新 arena 又无法取得物理页，必须失败。

断言检查失败前后堆指纹相同，且只有原来的第一个 arena 存在。
之后沿临时页链逐张归还，释放最小堆对象，确认页数恢复到“初始值减一”。
减去的一页仍属于堆，说明普通 kfree 不会把空 arena 自动交回页分配器。

堆容量耗尽采用另一条路径：连续申请 1 字节对象，实际得到 512 个有效返回值，第 513 次失败。
这个数对应 4 × 4096 / 32，不是单独打印计算结果。
全部释放后，再成功申请四个 4076 字节对象，证明各页的碎片已经合并到整页。

演示专用 release()（仅供本篇演示收尾使用，不属于 kmalloc/kfree 公开接口）只在全部对象释放之后运行。
它先要求每个 arena 恰好是一个空闲整页块，再调用 page_free() 并清空槽位。
正常 kfree 保留页面与演示收尾归还四页，分别承担日常复用和测试资源收支的职责。

不同大小分配、拒绝检查与耗尽回收的客体画面

GDB 在 heap_demo_done 检查 512 次分配计数、拒绝计数、四个 arena 已清空以及页位图。
最终仍有 18 页属于第 11 篇的活动页目录和页表，脚本核对它们的实际地址都在占用位图内。
堆回收不能释放这些供分页硬件继续使用的页面，也不能把整个分配器恢复到分页前的计数。

独立故障镜像显示延迟检测

heapfault 变体完成正常演示后，重新申请 17 字节对象，执行 p[17] ^= 1。
这次写入修改紧邻载荷的检查值；调用拒绝检查确认 kfree 失败且堆内容未被释放路径改变。
随后打印 D12 TAIL DAMAGE rejected unchanged，再主动触发带说明的断言。

尾部损坏被拒绝后主动诊断停机的客体画面

这里停机来自演示代码主动调用 panic，不是 canary 自动触发的 CPU 异常。
检查脚本先验证 panic 的 HLT 指令位置，再用独立运行的 QEMU monitor 检查 HLT=1。
正常镜像则继续到 keyboard_ready，两种实验入口分别保存截图和串口记录。

下载与复现

下载第 12 篇完整源码，解压目录前缀为 os-day-12。
源码冻结提交为 62894e1b7459dd28dfd84d8528aacbcd99ccae55，实现位于 examples/build-an-os。
沿用第 01 篇的 localhost/build-an-os:day01 工具链镜像：

unzip os-day-12-source.zip
cd os-day-12/examples/build-an-os
podman run --rm -v "$PWD:/work" -w /work localhost/build-an-os:day01 make check-heap
podman run --rm -v "$PWD:/work" -w /work localhost/build-an-os:day01 make check

两条命令顺序运行，检查脚本共享 GDB 的 1234 端口。
check-heap 覆盖正常堆实验与独立尾损坏停机，make check 执行累计版本的回归入口。
本篇定向 QEMU 检查、完整 make check 与源码附件独立解压后的累计检查均退出 0，正常分配与故障变体分别通过。
实现边界、累计回归与运行数据记录在源码内 docs/day12-evidence.md。

正常堆实验的串口标识包括：

physical-page failure unchanged; recovery OK
sizes/patterns first-fit split/coalesce OK
overflow/invalid/double/tail/metadata reject OK
IF=0/1 preserved; exhausted=512 recovered=4 pages
HEAP OK retained paging tables=18

对应日志保存在 build/heap-*-serial.txt、build/heap-*-gdb.txt 和 build/heap-halted-registers.txt。