Chapter 3 Page tables
页表是操作系统保证每个进程有独立的地址空间和内存的最常用的机制。页表决定内存地址代表什么，决定哪部分物理地址可以访问，使 xv6 可以分隔不同进程的地址空间，并将它们映射在一块物理内存上。页表是常用的设计，因为它实现了很多 tricks ，如 xv6 的一些 tricks ：将同一块内存（trampoline page）映射到许多地址空间；用一个非映射页保护内核和用户栈。本节学习 RISC-V 硬件提供的页表和xv6如何使用它们。
分页硬件
RISC-V指令（ user和kernel ）操作虚拟地址（\(virtual\ addresses\)）。用物理地址（\(physical\ addresses\)）索引机器的 RAM 或者物理内存。RISC-V 的页表硬件通过将每个虚拟地址映射到物理地址将两者联系起来。
xv6 运行在 Sv39 RISC-V 上，\(64\) 位的虚拟地址最多可以使用低 \(39\) 位，高 \(25\) 位不使用。在 Sv39 配置中，一个 RISC-V 页表在逻辑上可以当作一个有 \(2^{27}\) 个页表项（PTE,page table entries）的数组。每个 PTE 有 \(44\) 位的物理页号和一些flags。分页硬件使用 \(39\) 位虚拟地址中的高 \(27\) 位在页表中索引到一个 PTE，从 PTE 中取出 \(44\) 位的 PPN 做高位，原虚拟地址的低 \(12\) 位做低位，组成 \(56\) 位的物理地址。OS 对于虚拟地址到物理地址的转换是以 \(4096\) ( \(2^{12}\) ) 字节的对齐块为粒度的（所有的页目录页地址或页地址都是 \(4096\) 的倍数，低 \(12\) 位都是 \(0\)，方便 PTE 向 PA 的转换）。这样的一块称为一页。
在 Sv39 RISC-V 中，虚拟地址的高 \(25\) 位不用作地址转换。物理地址也有增长的空间：在 PTE 格式中，物理页号还有 \(10\) 位的增长空间。RISC-V 设计者基于科技预测选择了这些数字。Sv48 有 \(48\) 位虚拟地址。
如图所示，RISC-V CPU 将虚拟地址和物理地址的转换分成三步。存储在物理内存中的页表作为三级树，树根是一个 \(4096\) 字节的页表，含有 \(512\) 个 PTEs，每个 PTE 含有树中下一级页表所在页的物理地址。这些页也含有 \(512\) 个 PTEs，用于树中的最后一级。分页硬件用 \(27\) 位的高 \(9\) 位选择一级页表页中的一个 PTE，中间 \(9\) 位用于索引二级页表中的 PTE,后 \(9\) 位用于索引三级页表的 PTE。（Sv48 RISC-V 中页表分四级，虚拟地址的 \(39-47\) 位索引最顶级）
在地址转换过程中，三个 PTEs 任意一个没有出现，则分页硬件产生一个 page-fault exception，由内核处理异常。
相比一级结构设计，三级结构提高了记录 PTEs 的内存效率（\(memory-efficient\)）（大部分地址空间没有使用的话，不需要分配PTEs）。通常大范围的虚拟地址没有映射，三级结构能忽略整个页目录。例如，如果一个应用只使用了从 \(0\) 开始的很少的地址，那么一级页目录中的 \(1\) 到 \(511\) 个页表项是无用的，内核没有必要为这 \(511\) 个中间页目录分配页，而且，内核也没有必要为这 \(511\) 个中间页目录对应的三级页目录分配页，如此，三级设计节省了二级页目录 \(511\) 页，节省了三级页目录 \(511 * 512\) 页。
尽管在执行 l/w 指令时，CPU 在硬件中采用三级结构，但存在明显的缺点：CPU 必须从内存取出三个 PTEs 完成虚拟地址到物理地址的转换。为了避免从物理内存中取出 PTE 的开销，RISC-V CPU 将 PTEs 缓存在 TLB（\(Translation\ Look-aside\ Buffer\)）中。
每个页表项含有 flag 位，指示相关的虚拟地址如何被使用。PTE_V 指示 PTE 是否存在：如果没有设置，使用该页将会导致异常。PTE_R 指示指令是否被允许读该页。PTE_W 指示指令是否被允许写该页。PTE_X 指示 CPU 是否可能将页的内容作为指令并执行。PTE_U 指示用户mode的指令是否可以访问该页：如果没有设置，则该 PTE 只能被 supervisor-mode 使用。（flags和其他分页硬件相关的指令定义在 kernel/riscv.h）
为了硬件使用页表，内核必须将一级页表页的物理地址写到satp寄存器。每个CPU有自己的satp寄存器。CPU使用自己的satp指向的页表对所有的后续指令产生的地址进行地址转换。每个CPU有自己的satp，所以不同的CPUs能运行不同的进程，每个进程用自己的页表定义独立的地址空间。
通常内核将所有的物理地址映射到它的页表，所以它能通过l/w指令读写物理内存的任何位置。因为页目录在物理内存，内核能通过使用标准的store指令写PTE的虚拟地址，从而编程页目录中的PTE的内容。
一些术语的注释。物理内存指的是DRAM中的存储单元。物理内存的一个字节有一个地址，称为物理地址。指令只能使用虚拟地址，分页硬件负责转换为物理地址，然后发给DRAM硬件读写存储。不像物理内存和虚拟地址，虚拟内存不是一个物理对象，而是指内核提供的管理物理内存和虚拟地址的抽象机制的集合。
（地址转换是由硬件处理的，并非操作系统，MMU是硬件的一部分）
内核地址空间
xv6为每个进程维护了一个页表，描述每个进程的用户地址空间，外加一个单独的页表定义内核地址空间。内核配置它的地址空间布局，以可预料的虚拟地址访问物理内存和各种硬件资源。下图展示了内核虚拟地址到物理地址的布局。（kernel/memlayout.h描述了xv6内核内存布局）。右图完全是由硬件决定的。
QEMU模拟一个包括RAM（物理内存）的计算机，RAM从物理地址0x80000000到物理地址0x86400000（xv6中称为PHYSTOP）。QEMU模拟也包括I/O设备，如硬盘接口。QEMU将设备接口暴露给软件，作为物理地址空间中低于0x80000000的内存映射（memory-mapped）控制寄存器（内存映射IO，MMIO，使用访存指令进行外设的访问）。内核可以读写这些特殊的物理地址和外设交互，如reads和writes是和外设硬件通信，而不是和RAM。（Chapter4 解释xv6如何和外设交互）
内核对于RAM和内存映射设备寄存器使用直接映射：映射资源的虚拟地址和物理地址相等。例如 ，内核本身虚拟地址和物理地址都位于KERNBASE=0x80000000。直接映射简化了读写物理内存的内核代码。例如，当fork为子进程分配用户内存时，分配器返回那个内存的物理地址；当copy父进程的用户内存到子进程时，fork直接使用那个物理地址作为虚拟地址。
有一些内核的虚拟地址不是直接映射的：
- trampoline page。它被映射在虚拟地址空间的顶部；用户页表有相同的映射。（下章详解trampoline page）。关于页表的有趣的使用：一个物理页（存有trampoline code）在内核的虚拟地址空间被映射了两次：一次是虚拟地址空间的顶部，一次是直接映射（看图是映射在可kernel text区域）。
- kernel stack pages。每个进程有自己的内核栈，被映射在高地址空间，所以xv6可以在kernel stack下方留下一个保护页（guard page）。保护页的PTE是无效的（没有设置PTE_V，所以保护页不会消耗真正的内存），所以如果内核栈溢出，会产生一个异常并且内核会panic。没有保护页则栈溢出会覆盖写内核内存，造成错误的操作。相比之下panic更好。
内核通过高地址内存映射使用栈，也可以通过直接映射地址使用。另一个设计是只有直接映射，使用直接映射地址处的栈。然而，这样安排，提供保护页将涉及到指向物理内存的未映射的虚拟地址（保护页很难设置），这很难用。
内核对于映射trampoline和kernel text的页使用PTE_R和PTE_X权限，内核从这些页读取并执行指令。内核用PTE_R和PTE_W权限映射其他页，所以能读写这些页的内存。保护页映射是无效的。（kernel text为避免bug不能写，kernel data只需要读写，无法执行）
Code: creating an address space
大多数操作地址空间和页表的xv6代码在kernel/vm.c中。主要数据结构是pagetable_t，实际是一个指向RISC-V一级页表页的指针，可能是内核页表，也可能是任一个进程页表。主要函数是walk，查找一个虚拟地址的PTE；还有mappages，对于新的映射插入PTEs。函数名以kvm开头的操作内核页表，以uvm开头的操作用户页表，其他函数两者都用。copyout和copyin向系统调用参数提供的用户地址空间传输数据，它们在vm.c中，因为为了找到相应的物理内存它们需要转换用户地址空间。
boot之后，main调用kvminit（kernel/vm.c:54）使用kvmmake（kernel/vm.c:20）创建内核页表。这个调用在xv6开启RISC-V的分页之前，此时地址直接指向物理地址。kvmmake首次分配一页物理内存作为一级页表页。然后调用kvmmap完成内核需要的地址转换：包括内核指令，数据，上界地址为PHYSTOP的物理内存，以及实际对应的是外设的内存（MMIO）。proc_mapstacks（kernel/proc.c:33）为每个进程分配一个内核栈，它调用kvmmap将每个栈映射到KSTACK（为无效的栈保护页预留了地址空间）生成的虚拟地址。
kvmmap（kernel/vm.c:127）调用mappages（kernel/vm.c:138），将一片虚拟地址及其对应物理地址的映射放在一张页表中。它以页为间隔（va映射后，下一个映射的是va+PGSIZE），依次为每个虚拟地址做映射：对于每个要映射的虚拟地址，mappages调用walk找到该虚拟地址的PTE，然后设置PTE的值：对应的物理页号，相应的权限（PTE_W,PTE_X,PTE_R），PTE_V标识该PTE是否有效（kernel/vm.c:153）。
walk（kernel/vm.c:81）模仿RISC-V分页硬件，用来查询一个虚拟地址的PTE（返回指向PTE的指针）。walk每次递减9位，查找下级页表或三级页表的PTE，如果PTE无效，则所查找的页没有被分配；如果设置了alloc参数，walk分配一个新的页并将物理地址放在PTE中。最终返回的是该虚拟地址对应的三级页表中PTE的地址。
上述代码依赖于直接被映射到内核虚拟地址空间的物理内存。例如，当walk按照页表级别依次下降检索时，它从PTE中取出下级页表的物理地址（kernel/vm.c:89），然后用这个地址作为虚拟地址查找下级页表的PTE。
main调用kvminithart（kernel/vm.c:62）配置内核页表：将一级页表页的物理地址写到寄存器satp，之后CPU使用内核页表进行地址转换（写入satp寄存器后，MMU可以使用刚才设置的内核页表。csrw satp指令执行后，下一条指令的地址转换将会发生，在此之前，没有启动页表，地址转换没有发生，执行这条指令后，PC+4，PC将采用虚拟地址转换，在这条指令之前，使用物理地址，没有页表和地址映射，在此之后，有了虚拟地址的概念，下一条指令，下一个值的地址是虚拟地址，而不是物理地址。之后每个地址都会使用页表进行转换，所以如果页表设置错误：覆盖内核数据，映射错误，地址不能转换，page-fault，最终造成内核停止或者死机）。因为内核使用一个确定的映射，所以下一个指令的虚拟地址将会映射到正确的物理内存地址。
每个RISC-V CPU在TLB（Translation Look-aside Buffer）中缓存页表项，当xv6改变一个页表时，必须通知CPU使缓存在TLB中的相应的TLB entries失效，否则之后TLB可能使用一个旧的缓存映射，指向一个已经分配给另一个进程的物理页，结果就是一个进程可能破坏写其他进程的内存。RISC-V有一个指令sfence.vma刷新当前CPU的TLB，xv6执行sfence.vma的情况：重新加载satp寄存器后，xv6在kvminithart中执行这个指令；在返回用户空间之前切换到用户页表的trampoline code中（kernel/trampoline.S:79）。
为了避免刷新整个TLB，RISC-V CPUs支持address space identifiers(ASIDs)。内核能只刷新特定空间的TLB entries。
物理内存分配
内核必须在运行时为页表，用户内存，内核栈，管道缓冲区分配和释放物理内存。
xv6使用位于内核末端和PHYSTOP之间的物理内存做运行时分配，以完整的4096字节即一页为单位进行分配和释放，它通过将空闲页组织成链表进行跟踪管理。从链表中取出一页即为分配，加入一空闲页即为释放。
Code: Pyhsical memory allocator
分配器代码在kalloc.c（kernel/kalloc.c:1）中，分配器的数据结构是一个可分配的空闲物理内存页的list，每一个空闲页的list项是一个struct run（kernel/kalloc.c:17）。分配器从哪里获得指向那个数据结构的内存：每个free page本身只存储了free page的run结构体，没有存储其他信息。free list被一个spin lock保护（kernel/kalloc.c:21-24），list和lock放在一个结构体里使结构更清晰。（Chapter6涉及锁的细节，本章不关心）。
main调用kinit初始化分配器（kernel/kalloc.c:27）。kinit设置空闲列表链接从the end of the kernel到PHYSTOP。xv6应该通过解析硬件提供的配置信息决定有多少物理内存可用，但是xv6假设机器有128MB大小的RAM可用。kinit调用freerange，freerange通过对以页为单位调用kfree向free list增加内存。一个PTE只能指向以4096B为界对齐的物理地址（该地址是4096的倍数），所以freerange使用PGROUNDUP确保释放的是对齐的物理地址。分配器开始并没有内存，调用kfree后才有可以管理的内存。
分配器有时将地址作为整数数字方便运算（如freerange中的运算），有时将地址作为指针为了读写内存（如，操作存储在每页中的run structure）；对地址的双重使用是分配器代码充满C类型转换的主要原因。另一原因是释放和分配本质上改变了内存的类型。
kfree（kernel/kalloc.c:47）首先将free掉的内存的每个字节设置为1，这使得使用释放掉的内存（使用"dangling references"）的代码读取的是垃圾信息，而不是过期的信息；预期这些代码会更快的崩溃。kfree将页加入free list的前端：将pa类型转化成一个struct run指针，r->next指向旧的free list的起始，将free list指向r。kmalloc移除并返回free list的第一项。
进程地址空间
每个进程有独立的页表，当xv6切换进程时，也需要改变页表。一个进程的用户空间从虚拟地址0开始到MAXVA（kernel/riscv.h:360），一个进程的地址原则上可以有256GB。
当一个进程向xv6请求更多的用户内存时，xv6使用kalloc分配物理页，然后向进程的页表添加指向新的物理页的PTEs，xv6为这些PTEs设置PTE_W, PTE_X, PTE_R, PTE_U, PTE_V标志，大多数进程不会使用整个用户地址空间，xv6对于不使用的PTEs清除PTE_V标志。
关于页表使用的好的例子：首先，不同的进程页表将用户空间转换到不同的物理内存页，所以每个进程有独立私有的用户内存。其次，每个进程将它的内存视作从0开始的连续虚拟地址，然而进程的物理内存可能是不连续的。最后，内核将存有trampoline code那一页映射到用户地址空间的最顶部，这个单独的物理内存页映射在了所有（进程）的地址空间。
上图展示了xv6的一个执行进程的用户内存布局的细节。栈是单独的一页，以exec创建的初始内容作为展示：栈的顶部包含命令行参数的字符串以及指向它们的指针数组；下面是允许程序从main开始启动的值（返回的PC值），好像函数main(argc, argv)刚被调用一样。
为了检测一个用户栈是否溢出（使用超出分配的栈内存），xv6将一个不可访问（清楚PTE_V标志）的保护页（guard page）放在栈的下面。如果用户栈溢出，进程尝试使用栈下面的地址，硬件将产生一个page-fault exception，因为保护页对于运行在user-mode的进程是不可访问的。现代操作系统可能在栈溢出时自动为用户栈分配更多的内存。
Code: sbrk
sbrk系统调用：减少或者增加进程的内存。通过函数growproc（kernel/proc.c:253）实现，growproc通过参数正负决定调用uvmalloc或者uvmdealloc。uvmalloc（kernel/vm.c:221）调用kalloc分配物理内存，调用mappages加入PTEs到用户页表。uvmdealloc调用uvmunmap（kernel/vm.c），uvmunmap调用walk找到PTEs，调用kfree释放PTEs指向的物理内存。
xv6使用进程的页表，不仅定义硬件如何映射虚拟地址，而且是物理内存页分配给进程的唯一记录。这也是释放用户内存（uvmunmap）需要检查用户页表的原因（只有通过页表确定应该释放哪些物理页）。
Code: exec
exec系统调用：创建地址空间的用户部分。它用文件系统中存储的文件初始化地址空间的用户部分。exec（kernel/exec.c:13）使用namei打开一个named binary path（Chapter8详解）。然后读取ELF header。（xv6应用程序采用ELF格式，kernel/elf.h）。一个ELF二进制的组成：ELF header，strct elfhdr（kernel/elf.h:6），以及一系列program section headers，struct proghdr（kernel/elf.h:25）。每个proghdr定义了应用必须被导入内存的那一部分；xv6程序只有一个program section header，但其他系统对于指令和数据可能有多个sections。
第一步，检查文件是否包含一个ELF二进制。一个ELF二进制以4B的"magic number"开头0x7F, 'E', 'L', 'F'，或者ELF_MAGIC（kernel/elf.h:3）。如果ELF header有正确的magic number，exec会认为二进制的格式是正确的。
exec通过proc_pagetable（kernel/exec.c:38）分配一个新的没有用户映射的页表，通过uvmalloc（kernel/exec.c:52）为每个ELF segment分配内存，通过loadseg（kernel/exec.c:10）将每个segment导入内存，loadseg使用walkaddr找到分配的内存的物理地址，向该地址写入ELF segment的每一页，readi从文件读取。
/init的program section header，用exec创建的第一个用户程序，如下（objdump -p _init）：
_init: file format elf64-little
Program Header:
LOAD off 0x0000000000000078 vaddr 0x0000000000000000 paddr 0x0000000000000000 align 2**3
filesz 0x0000000000000988 memsz 0x00000000000009a0 flags rwx
program section header的filesz可能小于memsz，指示两者的差距用0填充（对于C全局变量）而不是从文件中读取。对于/init，filesz有2112B，memsz有2136B，因此uvmalloc分配足够的物理内存即2136B，但只从文件/init中读取2112B。
exec分配并初始化用户栈。只分配一页栈页。exec将参数字符串组一次复制一个字符串到栈顶，在ustack中记录指向它们的指针。传给main的argv[]的最后一项设为null指针。ustack的前三项是假的（？）PC，argc，argv指针。
exec将一个不可访问的页放在了栈页的下面，使用超过一页的进程将会fault。不可访问的页允许exec处理非常大的参数，这种情况下，exec使用copyout函数（kernel/vm.c:347）向栈中复制参数时会感知到目的页是不可访问的，最终会返回-1。
准备新的内存镜像期间，如果exec检测到一个error（如一个无效的program segment），它会跳转到labelbad，释放新的镜像，返回-1。exec只有确保系统调用成功才可以释放旧的镜像：如果旧的镜像释放了，系统调用不可能返回-1。exec的error只会发生在镜像创建过程中。一旦镜像创建完成，exec就释放旧的页表，托管到新的页表。
exec将ELF文件导入ELF文件指定的内存地址。用户或者进程可以将ELF文件导入它们想导入的任何地址。因此exec是有风险的，因为ELF文件的地址可能故意或者无意的指向内核，对于没有防备的内核可能造成从崩溃，到恶意破坏内核隔离性（如安全漏洞security exploit）机制等后果。xv6用一系列checks避免这些风险，如：if(ph.vaddr + ph.memsz < ph.vaddr) 检查和运算是否溢出（大于64位可以表示的整数）。这个危险是：一个用户可能构建一个ELF二进制：pa.vaddr指向一个用户选择的地址，ph.memsz足够大，这样两者的和会溢出为0x1000，看起来像一个合法的值。
早期版本的xv6，用户地址空间包含内核（但在user-mode不能进行读写），用户可以选择一个与内核内存相对应的地址，将ELF二进制数据传输到内核。在RISC-V版本的xv6，这不可能发生，因为内核有自己独立的页表，loadseg将数据导入进程的页表，而不是内核的页表。
对于内核开发者来说很容易忽略重要的检查，现实世界中内核有一段很长的missing checks历史，用户程序利用checks的缺失获得内核特权。xv6没有完成提供给内核的用户级数据的校验工作。恶意的用户程序可能能利用检验缺失绕过xv6的隔离
Real world
和大多数操作系统一样，xv6使用分页硬件完成内存保护和映射。大多数操作系统结合分页和page-fault异常（Chapter 4学习），对分页的使用比xv6更先进。
xv6做的简化：内核在虚拟地址和物理地址间使用直接映射；假设物理RAM在地址0x8000000，内核期望在这里被导入。QEMU完成这个工作，但真实硬件证明这是一个bad idea：真实硬件的RAM和外设在不可预知的物理地址，所以如果RAM不在xv6期望能导入内核的地址0x8000000。。。。更严谨的内核设计者将任意硬件物理内存布局转换为可预知的内核虚拟地址布局。
RISC-V支持物理地址级别的保护，但是xv6没有使用这个特性。
在大内存机器上使用RISC-V支持的“super pages”是有意义的。当物理内存很小时，小页有意义：可以以更合适的粒度进行页分配和页与硬盘的交换。如：一个程序只用8KB内存，给它4MB的物理内存大页是浪费的。大页在RAM容量大时有意义，可以减少页表操作的开销。
xv6内核缺少像malloc一样的分配器，为小对象提供内存，避免内核使用需要动态分配的复杂的数据结构。内存分配是一个长期热门的话题，其基本的问题是：如何有效使用有限的内存；如何为未知的未来需求做准备。
今天，相比空间效率人们更关心速度；此外，更复杂的内核可能会分配许多不同大小的小块，而不是像xv6一样只分配4096B的块；一个真正的内核分配器需要同时处理小的分配，也需要处理大的分配。
课程里好的提问：
为什么要写walk函数，硬件可以完成映射？（为什么xv6需要walk函数）
- 当设置初始页表时，需要编程三级页表，需要模拟三级页表。
- syscall实验中，当
copysysinfo结构时，内核有自己的页表，每个用户地址空间有自己的页表。比如sysinfo struct指针存在于用户空间，内核需要将它转换为自己可以读写的地址，比如copyin, copyout内核转换用户虚拟地址，使用用户页表获取物理地址。然后内核获得一个可以用来读写的内存地址。
为什么硬件不开放walk函数，比如设置一个特权指令，返回物理地址？
需要以不同的方式设置页表。避免在copyin, copyinstr中的walk。后续讨论。
虚拟地址的转换完全在OS的控制之下
例如：如果一个页表项是无效的，硬件会返回page-fault，操作系统会更新页表，然后重新执行这个指令。
非常好的问题：开启虚拟地址转换之后（csrw satp），再使用walk函数，如何获取物理地址（需要设置PTE）
内核页表的设置是恒等映射的。这是walk可以正常运行的原因。更新页表是内核操作的，所以获取到的pagetable虚拟地址的值也是物理地址，通过PA2PTE成为pte所指向地址的内容。