3.5 代码（物理内存分配）

分配器(allocator)位于kalloc.c(kernel/kalloc.c:1)中。分配器的数据结构是可供分配的物理内存页的空闲列表。每个空闲页的列表元素是一个struct run(kernel/kalloc.c:17)。分配器从哪里获得内存来填充该数据结构呢？它将每个空闲页的run结构存储在空闲页本身，因为在那里没有存储其他东西。空闲列表受到自旋锁（spin lock）的保护(kernel/kalloc.c:21-24)。列表和锁被封装在一个结构体中，以明确锁在结构体中保护的字段。现在，忽略锁以及对acquire和release的调用；第6章将详细查看有关锁的细节。

[!TIP] 对于互斥锁，如果资源已经被占用，资源申请者只能进入睡眠状态。但是自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁，"自旋"一词就是因此而得名。

自旋锁比较适用于锁使用者保持锁时间比较短的情况。正是由于自旋锁使用者一般保持锁时间非常短，因此选择自旋而不是睡眠是非常必要的，自旋锁的效率远高于互斥锁。

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

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

函数kfree (kernel/kalloc.c:47)首先将内存中的每一个字节设置为1。这将导致使用释放后的内存的代码（使用“悬空引用”）读取到垃圾信息而不是旧的有效内容，从而希望这样的代码更快崩溃。然后kfree将页面前置（头插法）到空闲列表中：它将pa转换为一个指向struct run的指针r，在r->next中记录空闲列表的旧开始，并将空闲列表设置为等于r。

kalloc删除并返回空闲列表中的第一个元素。