3_xv6的页表.md

操作系统通过页表来向每个进程提供私有的地址空间和内存。页表决定了内存地址的含义，哪些物理内存可以访问。xv6使用页表分隔不同进程的地址空间，并把它们多路复用到单一的物理内存。xv6还使用页表实现了一些技巧：把同一块内存映射到多个地址空间(a trampoline page)，使用未映射的页来保护内核和用户的栈。

分页硬件

RISC-V页表硬件通过把虚拟地址映射到物理地址的方式来把它们连接在一起。

xv6运行Sv39的分页方式，这种分页方式只使用64位虚拟地址里的低39位，高25位并未使用。在这39位有效位里，低12位是offset，剩下27位是index，这意味着每个页表在逻辑上对应着2²⁷个PTE(页表入口)。每个PTE占用64位，低54位有效，高10位是保留位。在这54位有效位里，低10位是flags，高44位是PPN(物理页号)。虚拟地址所对应的物理地址是56位的，它的高44位来自于PTE的PPN，它的低12位来自于虚拟地址的offset。

Sv39的页表在物理内存里实际存在的形式是三级树(three-level tree)。树根是个4K的页，包含了512个PTE，每个PTE都对应了第二级的1个页，每个页都包含了第三级的512个PTE。虚拟地址的27位index里，高9位用来选择树根的PTE，中间9位用来选择二级页表页的PTE，低9位用来选择最终的PTE。

通常情况下，大部分的虚拟地址都是没有映射的。

PTE有10位的flag，可以在kernel/riscv.h看到xv6对于它们的定义。PTE_V的意思是此条PTE是否存在(1:存在，0:不存在)；PTE_R、PTE_W、PTE_X分别代表所对应的页是否可读、写、执行。PTE_U代表用户模式下是否可以访问此页。

内核需要把根页表页的物理地址放到satp寄存器里，硬件才能使用页表。每个CPU都有一个satp寄存器。这意味着每个CPU都可以有自己私有的地址空间，进而运行各自的进程。

内核地址空间

内核有自己的页表。当进程进入内核，xv6切换到内核页表，当从内核返回用户空间，又切换到用户进程的页表。内核的内存是私有的。

文件kernel/memlayout.h描述了内核内存的布局。

QEMU模拟了一个包含I/O设备的计算机。设备的控制寄存器被映射在物理内存0~0x80000000之间。内核通过读写那些内存与设备交互。

内核的大部分虚拟地址都使用的是恒等映射。对于即需要读写虚拟页又需要通过PTE管理物理页的内核来说，这样的直接映射降低了复杂性。只有两处虚拟地址不是直接映射的：

• trampoline页。它被映射在虚拟空间的顶端，它也被用户页表映射在用户空间的同样位置。它被内核虚拟地址空间映射了两次：一次是直接映射，一次是虚拟空间的顶端。
• 内核栈所在的页。每个进程都有自己的内核栈，它被映射在高位，这样在它下面xv6可以保留一个未映射的守护页(guard page)。守护页的PTE是无效的，这就确保了即使内核让内核栈溢出，也仅仅是触发一个错误让内核panic。如果没有守护页，栈溢出将导致执行不正确的指令。与其这样，让内核panic是个更好的选择。

把内核栈和守护页直接映射不可取，因为守护页所对应的物理地址将难以被使用。

对于内核的trampoline页和代码页，使用的权限是PTE_R和PTE_X，因为内核要从那些页里读取和执行指令。对于其它页则使用PTE_R和PTE_W，因为内核要从那些页里读写内存。对于保护页，则要将其设置为无效的。

创建地址空间

管理地址空间和页表的代码主要在kernel/vm.c。核心数据结构是pagetable_t，它是RISC-V根页表页的指针；它要么是内核的页表，要么是某个进程的页表。核心函数是walk，它用来查找一个虚拟地址的PTE，或者用来查找mappages，mappages用来为新的映射安装PTE。以kvm开头的函数用来管理内核页表，以uvm开头的函数则用来管理用户页表，其它函数即可以管理内核页表也可以管理用户页表。copyout用来把数据复制到用户虚拟地址(由系统调用的参数提供)，copyin则是进行相反方向的复制；它们都定义在vm.c里，因为它们需要严格地转换这些地址以找到对应的物理地址。

在启动的早期，main函数调用了kvminit函数来创建内核的页表。此时还没有开启分页，使用的是物理地址。kvminit首先分配了一个物理页用以保存根页表页。然后调用kvmmap来保存内核所需的转换。这些转换包括了内核的指令和数据，至到PHYSTOP的物理内存，和实际设备的内存范围。

kvmmap调用mappages来把映射关系保存到页表里。对于每个要映射的虚拟地址，mappages通过walk来找到对应PTE的地址。然后初始化PTE来保存相关的物理页号，所需的权限(RXV或RWV两种组合)。

walk在查找虚拟地址的PTE的时候模仿了分页硬件(paging hardware)。它是三级页表逐层查找。如果查到的PTE无效，说明所需的页不存在；如果参数alloc设置为1，walk会分配新的页表页，并把它的物理地址放在PTE里。最终返回的是第三级的PTE的地址。

如上代码依赖于物理地址和虚拟地址的直接映射。

main调用kvminithart来使内核页表生效。它把根页表页的物理地址保存在satp寄存器里。然后CPU就要开始地址转换了。由于内核使用了一致性映射，当前虚拟地址的下一条指令将会映射在正确的物理地址上。

每个进程都会分配到一个内核栈。宏KSTACK用以生成每个内核栈的虚拟地址，它还为栈保护页(stack-guard pages)预留了空间。kvmmap把PTE加到内核页表里，kvminithart重载satp寄存器这样硬件才能识别新的PTE。

每个RISC-V核都把页表缓存在TLB里。指令sfence.vma用以刷新当前核的TLB以使新的页表生效。

物理内存分配

内核必须在运行的时候(run-time)，为页表、用户内存、内核栈、管道缓存分配或释放物理内存。

xv6使用内核之后到PHYSTOP之间的物理内存进行运行时(run-time)的分配。它一次性地分配和释放整个4K的页。它通过把空闲页插入一个链表里来保持对这些页的持续追踪。分配就是从链表里移除一个页，释放就是把空闲页再加到链表里。

物理内存分配器

分配器(allocator)定义在kernel/kalloc.c里。分配器的数据结构是由空闲物理页组成的链表。每个空闲页在列表里都是struct run。因为空闲页里什么都没有，所以空闲页的run数据结构就保存在空闲页自身里。这个空闲列表使用自旋锁进行保护。

main函数调用kinit来初始化分配器。kinit通过保存所有空闲页来初始化链表。xv6其实是可以通过分析配置信息来获取真实内存的大小的，但它没有这么做，而是假定系统只有128M的内存。kinit调用freerange来把空闲内存加到链表里，freerange是通过调用kfree把每个空闲页逐一加到链表里来实现此功能的。由于PTE只能指向4K对齐的物理地址，所以freerange使用宏PGROUNDUP来确保空闲内存是4K对齐的。分配器刚开始是无内存可用的，对kfree的调用使得它拥有了可以管理的内存。

分配器有时把地址作为整数以执行一些算法，有时把它们作为指针以读写内存，这就使得分配器的代码里充满了强制类型转换。另外，分配和释放实际上也是改变了内存的类型。

kfree首先把内存的每个字节都填充为1，这是为了让之前使用它的代码不能再读取到有效的内容，期望这些代码能尽早崩溃以发现问题所在。然后kfree再把页加到空闲列表里，它把pa转换为到struct run的指针，把原空闲列表指向r->next，并使空闲列表等价于r。kalloc移除并返回空闲列表的第一个元素。

进程地址空间

当xv6在进程间切换的时候，进程的页表也会跟着切换。进程的用户空间从0到MAXVA，共计256G的内存(2³⁸)。

当进程申请更多内存的时候，xv6首先用kalloc分配一个物理页。然后把这个物理页的PTE加到进程的页表里。xv6会设置该PTE对应的标志位(W,X,R,U,V)。

我们可以看到页表有如下好处：1，不同进程的页表把用户地址映射到不同的物理页上，这样每个进程都有自己私有的用户内存。2，从进程的角度看虚拟地址是连续的，但实际上它所对应的物理地址却不必是连续的。3，内核把包含了trampoline代码的页映射到用户地址空间的顶部，这样单一的物理页就可以出现在所有的地址空间了。

栈是一个单独的页，它的内容来自于exec。在栈的最顶端，是命令行参数，和它们的指针数组。在这些参数的下面，是main的入口。

在栈的下面有一个保护页，它被设置为无效的，这样栈溢出的时候就会产生一个page-fault的异常。而真实世界的操作系统则可能会在栈溢出的时候给它分配更多的内存。

sbrk

已放在第一章。

exec

已放在第一章。