代码：物理内存分配器

分配器位于 kalloc.c 中。分配器的数据结构是一个可供分配的物理内存页面的空闲列表。每个空闲页的列表元素是一个 struct run。分配器从哪里获得内存来存放该数据结构？它将每个空闲页的 run 结构存储在空闲页本身中，因为那里没有存储其他东西。空闲列表由一个自旋锁保护。列表和锁被包装在一个结构中，以明确锁保护结构中的字段。现在，忽略锁和对 acquire 和 release 的调用；第 6 章将详细研究锁定。

函数 main 调用 kinit 来初始化分配器。kinit 初始化空闲列表以容纳内核末尾和 PHYSTOP 之间的每一页。Xv6 应该通过解析硬件提供的配置信息来确定有多少物理内存可用。相反，xv6 假设机器有 128 兆字节的 RAM。kinit 调用 freerange，通过对每页调用 kfree 将内存添加到空闲列表中。一个 PTE 只能引用一个在 4096 字节边界上对齐的物理地址（是 4096 的倍数），所以 freerange 使用 PGROUNDUP 来确保它只释放对齐的物理地址。分配器开始时没有内存；这些对 kfree 的调用给了它一些来管理。

分配器有时将地址视为整数以对其执行算术运算（例如，在 freerange 中遍历所有页面），有时使用地址作为指针来读写内存（例如，操作存储在每个页面中的 run 结构）；这种地址的双重用途是分配器代码充满 C 类型转换的主要原因。

函数 kfree 首先将被释放的内存中的每个字节设置为值 1。这将导致在释放后使用内存的代码（使用“悬空引用”）读取垃圾而不是旧的有效内容；希望这会使此类代码更快地崩溃。然后 kfree 将页面前置到空闲列表中：它将 pa 转换为指向 struct run 的指针，将旧的空闲列表的开头记录在 r->next 中，并将空闲列表设置为 r。kalloc 删除并返回空闲列表中的第一个元素。