页表是最流行的机制，操作系统通过它为每个进程提供自己的私有地址空间和内存。页表决定了内存地址的含义，以及物理内存的哪些部分可以被访问。它们允许xv6隔离不同进程的地址空间，并将它们复用到一个物理内存中。页面表是一种流行的设计，因为它们提供了一种间接的级别，允许操作系统执行许多技巧。xv6执行一些技巧:在几个地址空间中映射相同的内存(一个trampoline页面),并用一个未映射的页面保护内核和用户堆栈。本章的其余部分解释了RISC-V硬件提供的页表以及xv6如何使用它们。
提醒一下，RISC-V指令(用户和内核)操纵虚拟地址。机器的RAM或物理内存是用物理地址索引的。RISC-V页表硬件通过将每个虚拟地址映射到一个物理地址来连接这两种地址。 xv6运行在Sv39 RISC-V上，这意味着只使用64位虚拟地址的底部39位；最高25位未使用。在这个Sv39配置中，RISC-V页表在逻辑上是227 (134，217，728)个页表项(pte)的数组。每个PTE包含一个44位的物理页号(PPN)和一些标志。分页硬件通过使用39位中的最高27位来索引页表以找到PTE，并生成56位物理地址来翻译虚拟地址，该物理地址的最高44位来自PTE中的PPN，其最低12位从原始虚拟地址复制。数字3.1 用一个简单的pte数组的页表逻辑视图展示了这个过程(见图3.2 更完整的故事)。页表使操作系统能够以4096的对齐块的粒度控制虚拟到物理地址的转换 212字节。这样的块被称为页面。 在Sv39 RISC-V中，虚拟地址的前25位不用于翻译。物理地址也有增长的空间:在PTE格式中，物理页号还有再增长10位的空间。RISC-V的设计者根据技术预测选择了这些数字。239字节等于512GB，这应该足够运行应用程序的地址空间了
图3.1: RISC-V虚拟和物理地址，带有一个简化的逻辑页表。
在RISC-V计算机上。256是足够的物理内存空间，在不久的将来可以容纳许多I/O设备和DRAM芯片。如果需要更多，RISC-V设计人员已经用48位虚拟地址定义了Sv48[1]. 如图所示3.2 显示，RISC-V CPU通过三个步骤将虚拟地址转换为物理地址。页表以三级树的形式存储在物理内存中。树的根是包含512个pte的4096字节页表页，pte包含树的下一级中页表页的物理地址。这些页面中的每一页包含树中最后一级的512个pte。分页硬件使用27位中的最高9位来选择根页表页中的PTE，中间9位来选择树的下一级中的页表页中的PTE，以及最低9位来选择最终的PTE。(在Sv48 RISC-V中，页表有四级，虚拟地址的39到47位索引到顶级。) 如果翻译一个地址所需的三个pte中的任何一个不存在，分页硬件就会抛出一个缺页异常，让内核来处理这个异常(参见第12章)4). 图形的三层结构3.2 与Figure的单级设计相比，提供了一种节省内存的记录pte的方法3.1. 在大范围虚拟地址没有映射的常见情况下，三级结构可以省略整个页面目录。例如，如果一个应用程序只使用从地址零开始的几个页面，那么顶层页面目录的条目1到511是无效的，内核不必为511个中间页面目录分配页面。此外，内核也不必为这511个中间页面目录的底层页面目录分配页面。因此，在这个例子中，三级设计为中间页目录节省了511页，为底层页目录节省了511×512页。 尽管作为执行加载或存储指令的一部分，CPU遍历硬件中的三级结构，但是三级的潜在缺点是CPU必须从存储器加载三个pte来执行加载/存储指令中的虚拟地址到物理地址的转换。为了避免从物理内存加载pte的开销，RISC-V CPU将页表条目缓存在翻译后备缓冲区(TLB)中。
图3.2: RISC-V地址转换细节。
每个PTE包含标志位，告诉分页硬件如何允许使用相关联的虚拟地址。PTE_V指示PTE是否存在:如果没有设置，对页面的引用会导致异常(即不允许)。PTE_R控制是否允许指令读取页面。PTE_W控制是否允许指令写入页面。PTE_X控制CPU是否可以将页面内容解释为指令并执行它们。PTE_U控制是否允许用户模式下的指令访问页面；如果未设置PTE_U，PTE只能在管理员模式下使用。数字3.2 展示了它是如何工作的。标志和所有其他与页面硬件相关的结构在(kernel/riscv.h) 为了告诉硬件使用页表，内核必须将根页表页的物理地址写入satp寄存器。每个CPU都有自己的satp。CPU将使用由它自己的satp指向的页表来翻译由后续指令产生的所有地址。每个CPU都有自己的satp，因此不同的CPU可以运行不同的进程，每个进程都有一个由自己的页表描述的私有地址空间。 通常，内核将所有的物理内存映射到它的页表中，这样它就可以使用加载/存储指令读写物理内存中的任何位置。由于页面目录位于物理内存中，内核可以通过使用标准存储指令写入PTE的虚拟地址，对页面目录中的PTE内容进行编程。 关于术语的几点说明？物理内存是指DRAM中的存储单元。物理内存的一个字节有一个地址，称为物理地址。指令只使用虚拟地址，分页硬件将其转换为物理地址，然后发送到DRAM硬件进行读取
或者写存储。与物理内存和虚拟地址不同，虚拟内存不是物理对象，而是指内核提供的管理物理内存和虚拟地址的抽象和机制的集合。
图3.3:左边是xv6的内核地址空间。RWX是指PTE读、写和执行权限。右边是xv6期望看到的RISC-V物理地址空间。
内核地址空间 Xv6为每个进程维护一个页表，描述每个进程的用户地址空间，另外还有一个页表描述内核的地址空间。内核配置其地址空间的布局，以便在可预测的虚拟地址上访问物理内存和各种硬件资源。数字3.3 展示了这种布局如何将内核虚拟地址映射到物理地址。文件(kernel/memlayout.h)声明xv6内核内存布局的常量。
QEMU模拟包含RAM(物理内存)的计算机，从物理地址0x80000000开始，至少延续到0x86400000，xv6称之为PHYSTOP。QEMU模拟还包括I/O设备，如磁盘接口。QEMU将设备接口作为物理地址空间中0x80000000以下的内存映射控制寄存器向软件公开。内核可以通过读/写这些特殊的物理地址与设备进行交互；这种读写与设备硬件通信，而不是与RAM通信。回4 解释xv6如何与设备交互。 内核使用“直接映射”来获取RAM和内存映射设备寄存器也就是说，将资源映射到与物理地址相等的虚拟地址。例如，内核本身在虚拟地址空间和物理内存中都位于KERNBASE=0x80000000。直接映射简化了读写物理内存的内核代码。例如，当fork为子进程分配用户内存时，分配器返回该内存的物理地址；fork在将父用户内存复制到子用户内存时，直接使用该地址作为虚拟地址。 有几个内核虚拟地址不是直接映射的:
蹦床页面。它被映射在虚拟地址空间的顶部；用户页表具有相同的映射。回4 讨论了蹦床页面的角色，但是我们在这里看到了一个有趣的页表用例；一个物理页面(保存trampoline代码)在内核的虚拟地址空间中被映射两次:一次在虚拟地址空间的顶部，一次使用直接映射。 内核堆栈页面。每个进程都有自己的内核堆栈，它被映射到较高的位置，这样在它下面xv6就可以留下一个未映射的保护页。保护页的PTE无效(即PTE_V未设置)，因此如果内核溢出内核堆栈，很可能会导致异常，内核将会死机。如果没有保护页，溢出的堆栈将会覆盖其他内核内存，从而导致不正确的操作。恐慌崩溃更可取。
虽然内核通过高内存映射来使用堆栈，但是内核也可以通过直接映射的地址来访问它们。另一种设计可能只有直接映射，并在直接映射的地址使用堆栈。然而，在这种安排中，提供保护页将涉及取消映射虚拟地址，否则虚拟地址将引用物理存储器，这将难以使用。 内核用权限PTE_R和PTE_X映射trampoline的页面和内核文本。内核从这些页面读取并执行指令。内核用权限PTE_R和PTE_W映射其他页面，这样它就可以读写这些页面中的内存。保护页的映射无效。
代码:创建地址空间 操纵地址空间和页表的大部分xv6代码驻留在vm.c中(ker-nel/vm.c:1)。中央数据结构是pagetable_t，它实际上是指向RISC-V的指针
根页-表页；pagetable_t可以是内核页表，也可以是每个进程的页表之一。核心函数是walk和mappages，前者为虚拟地址查找PTE，后者为新映射安装PTE。以kvm开始的函数操纵内核页表；以uvm开始的函数操纵用户页表；其他函数用于两者。copyout和copyin将数据复制到作为系统调用参数提供的用户虚拟地址，以及从这些地址复制数据；它们位于vm.c中，因为它们需要显式地转换这些地址，以便找到相应的物理内存。 在引导序列的早期，main调用kvminit(内核/虚拟机:54)使用kvmmake创建内核的页面表(内核/虚拟机:20)。这个调用发生在xv6在RISC-V上启用分页之前，所以地址直接指向物理内存。Kvmmake首先分配一页物理内存来保存根页表页。然后它调用kvmmap来安装内核需要的翻译。翻译包括内核的指令和数据，物理内存直到物理停止，内存范围实际上是设备。过程_映射堆栈(内核/处理器c:33)为每个进程分配一个内核堆栈。它调用kvmmap将每个堆栈映射到KSTACK生成的虚拟地址，这就为无效的堆栈保护页面留出了空间。 kvmmap(内核/虚拟机:127)调用地图页面(内核/虚拟机:138)这将一系列虚拟地址到相应系列物理地址的映射安装到页表中。它以页面间隔为范围内的每个虚拟地址分别执行此操作。对于每个要映射的虚拟地址，mappages调用walk来查找该地址的PTE地址。然后，它初始化PTE以保存相关的物理页码、所需的权限(PTE_W、PTE_X和/或PTE_R)和PTE_V，以将PTE标记为有效(内核/虚拟机:153)。 步行(内核/虚拟机:81)模拟RISC-V分页硬件，因为它查找虚拟地址的PTE(见图3.2).walk每次下降3级页表9位。它使用每一级的9位虚拟地址来查找下一级页表或最终页的PTE(内核/虚拟机:87)。如果PTE无效，那么所需的页面还没有被分配；如果设置了alloc参数，walk将分配一个新的页表页，并将其物理地址放在PTE中。它返回树中最低层的PTE的地址(内核/虚拟机:97)。 上面的代码依赖于直接映射到内核虚拟地址空间的物理内存。例如，当walk降低页表的级别时，它从PTE中提取下一级页表的(物理)地址(内核/虚拟机:89)，然后使用该地址作为虚拟地址来提取下一级的PTE(内核/虚拟机:87)。 主调用kvminithart(内核/虚拟机:62)安装内核页表。它将根页表页的物理地址写入寄存器satp。此后，CPU将使用内核页表来转换地址。由于内核使用身份映射，下一条指令的虚拟地址将映射到正确的物理内存地址。 每个RISC-V CPU在翻译后备缓冲器(TLB)中缓存页表条目，当xv6更改页表时，它必须告诉CPU使相应的缓存TLB条目无效。如果没有，那么在以后的某个时候，TLB可能会使用一个旧的缓存映射，指向一个在此期间已经分配给另一个进程的物理页面，结果，一个进程可能会在另一个进程的内存上乱涂乱画。RISC-V有一个指令sfence.vma，用于刷新当前CPU的TLB。Xv6在重载satp寄存器后执行kvminithart中的sfence.vma，并在切换到
返回用户空间前的用户页表(内核/蹦床。史:79)。 为了避免刷新整个TLB，RISC-V CPU可以支持地址空间标识符(ASIDs)[1]. 然后，内核可以只刷新特定地址空间的TLB条目。
物理内存分配 内核必须在运行时为页表、用户内存、内核堆栈和管道缓冲区分配和释放物理内存。 xv6使用内核末尾和PHYSTOP之间的物理内存进行运行时分配。它一次分配和释放整个4096字节的页面。它通过将一个链表穿过页面本身来跟踪哪些页面是空闲的。分配包括从链表中删除一个页面；释放包括将被释放的页面添加到列表中。
代码:物理内存分配器 分配器驻留在kalloc.c中(kernel/kalloc.c:1)。分配器的数据结构是可供分配的物理内存页面的自由列表。每个自由页的列表元素都是一个结构运行(kernel/kalloc.c:17)。分配器从哪里获得内存来保存数据结构呢？它将每个自由页面的运行结构存储在自由页面本身中，因为那里没有存储任何其他内容。自由列表受旋转锁保护(kernel/kalloc.c:21-24)。列表和锁包装在一个结构中，以明确锁保护结构中的字段。现在，忽略锁以及获取和释放的调用；回6 将详细研究锁定。 函数main调用kinit来初始化分配器(kernel/kalloc.c:27)。kinit初始化空闲列表来保存内核末尾和PHYSTOP之间的每一页。xv6应该通过解析硬件提供的配置信息来确定有多少物理内存可用。相反，xv6假设机器有128兆内存。kinit调用freerange，通过对kfree的每页调用将内存添加到空闲列表中。PTE只能引用在4096字节边界上对齐的物理地址(是4096的倍数)，因此freerange使用PGROUNDUP来确保它只释放对齐的物理地址。分配器启动时没有内存；这些对kfree的调用给了它一些管理的空间。 分配器有时将地址视为整数，以便对其执行算术运算(例如，在freerange中遍历所有页面)，有时将地址用作读写内存的指针(例如，操纵存储在每个页面中的run结构)；地址的这种双重用途是分配器代码充满C类型转换的主要原因。另一个原因是释放和分配本质上改变了内存的类型。 函数kfree(kernel/kalloc.c:47)首先将内存中被释放的每个字节设置为1。这将导致在释放内存后使用内存的代码(使用“悬空引用”)读取垃圾，而不是旧的有效内容；希望这将导致这样的代码打破得更快。然后kfree将页面预先添加到自由列表中:它将pa强制转换为指向struct run的指针，在r->next中记录自由列表的旧开始，并将自由列表设置为r，kalloc移除并返回自由列表中的第一个元素。
MAXVA
页面大小 �
以nul结尾的字符串argv[argc]
argv[0] main的argv参数 main的主返回PC的argc参数
0
图3.4:一个进程的用户地址空间及其初始堆栈。
进程地址空间 每个进程都有一个单独的页表，当xv6在进程间切换时，也会改变页表。如图所示2.3 显示，一个进程的用户内存从虚拟地址零开始，可以增长到MAXVA(kernel/riscv.h:360)，原则上允许一个进程寻址256千兆字节的内存。 当一个进程向xv6请求更多的用户内存时，xv6首先使用kalloc来分配物理页面。然后，它将指向新物理页面的pte添加到进程的页面表中。Xv6设置这些PTE中的PTE_W、PTE_X、PTE_R、PTE_U和PTE_V标志。大多数进程不使用整个用户地址空间；xv6在未使用的PTE中清除PTE_V。 我们在这里看到一些使用页表的好例子。首先，不同进程的页表将用户地址转换为不同的物理内存页，这样每个进程都有私有的用户内存。其次，每个进程都将其内存视为从零开始的连续虚拟地址，而进程的物理内存可以是不连续的。第三，内核在用户地址空间的顶部映射一个带有trampoline代码的页面，因此在所有地址空间中都会出现一个物理内存页面。 数字3.4 更详细地展示了xv6中正在执行的进程的用户内存布局。堆栈是一个单独的页面，显示的是由exec创建的初始内容。包含命令行参数的字符串以及指向它们的指针数组位于堆栈的最顶端。在它下面是允许程序在main启动的值，就像函数main(argc，argv)刚刚被调用一样。 为了检测用户堆栈溢出分配的堆栈内存，xv6通过清除PTE_U标志将一个不可访问的保护页放在堆栈的正下方。如果用户堆栈溢出，进程试图使用堆栈下的地址，硬件将生成一个缺页异常，因为
用户模式下运行的程序无法访问保护页。实际操作系统可能会在用户堆栈溢出时自动为其分配更多内存。
代码:sbrk Sbrk是一个进程收缩或增长内存的系统调用。系统调用由函数growproc实现(内核/处理器c:253)。growproc调用uvmalloc或uvmdealloc，取决于n是正数还是负数。uvmalloc(内核/虚拟机:221)用kalloc分配物理内存，用mappages将pte添加到用户页表中。uvmdealloc调用uvmunmap(内核/虚拟机:166)，它使用walk来查找pte和kfree来释放它们所引用的物理内存。 xv6不仅使用进程的页表来告诉硬件如何映射用户虚拟地址，还将它作为分配给该进程的物理内存页的唯一记录。这就是为什么释放用户内存(在uvmunmap中)需要检查用户页表的原因。
代码:exec Exec是创建地址空间用户部分的系统调用。它从存储在文件系统中的文件初始化地址空间的用户部分。高级管理人员(kernel/exec.c:13)使用namei打开命名的二进制路径(内核/exec.c:26)，这将在第章中解释8. 然后，它读取ELF标头。Xv6应用程序以广泛使用的ELF格式描述，在(kernel/elf.h)。一个ELF二进制文件包含一个ELF头，struct elfhdr(kernel/elf.h:6)，后跟一系列程序段头，struct proghdr(kernel/elf.h:25)。每个proghdr描述了必须加载到内存中的应用程序的一部分；xv6程序只有一个程序段头，但是其他系统可能有单独的指令和数据段。 第一步是快速检查文件是否包含ELF二进制文件。ELF二进制以四字节的“幻数”0x7F、“E”、“L”、“F”或ELF_MAGIC开始(kernel/elf.h:3)。如果ELF头有正确的幻数，exec就认为二进制文件是格式良好的。 Exec使用proc_pagetable分配一个没有用户映射的新页表(内核/exec.c:38)，用uvmalloc为每个ELF段分配内存(内核/exec.c:52)，并用loadseg将每个段加载到内存中(内核/exec.c:10)。loadseg使用walkaddr来查找所分配内存的物理地址，在该地址上写入ELF段的每一页，并从文件中读取。 用exec创建的第一个用户程序/init的程序段标题如下所示:
user/_init:文件格式elf64-littleriscv
程序标题: 卸载0x 000000000000000 B0 vaddr 0x 0000000000000000 paddr 0x 000000000000000000 align 2 * * 3 filesz 0x 0000000000000840 memsz 0x 00000000000000000858 flags rwx
堆栈关闭0x 0000000000000000 vaddr 0x 00000000000000000 paddr 0x 000000000000000000 align 2 * * 4 filesz 0x 000000000000000 memsz 0x 000000000000000000标志rw-
程序段头的filesz可能小于memsz，这表明它们之间的间隙应该用零填充(对于C全局变量),而不是从文件中读取。对于/init，filesz是2112字节，memsz是2136字节，因此uvmalloc分配了足够的物理内存来容纳2136字节，但只从文件/init中读取2112字节。 现在，exec分配并初始化用户堆栈。它只分配一个堆栈页面。Exec将参数字符串一次一个地复制到堆栈的顶部，并将指向它们的指针记录在ustack中。它在将要传递给main的argv列表的末尾放置一个空指针。ustack中的前三个条目是伪返回程序计数器、argc和argv指针。 Exec将一个不可访问的页面放在堆栈页面的正下方，这样试图使用多个页面的程序将会出错。这个不可访问的页面还允许exec处理太大的参数；在这种情况下，复制(内核/虚拟机:347)函数将注意到目标页面不可访问，并将返回-1。 在准备新的内存映像的过程中，如果exec检测到一个错误，比如一个无效的程序段，它就跳到标签bad，释放新的映像，并返回-1。Exec必须等待释放旧映像，直到它确信系统调用会成功:如果旧映像不在了，系统调用就不能向它返回-1。exec中唯一的错误发生在创建映像的过程中。一旦映像完成，exec就可以提交新的页表(内核/执行代码:113)释放旧的(内核/执行代码:117)。 Exec将ELF文件中的字节加载到ELF文件指定地址的内存中。用户或进程可以将他们想要的任何地址放入ELF文件中。因此exec是有风险的，因为ELF文件中的地址可能会有意或无意地指向内核。疏忽大意的内核的后果可能从崩溃到恶意破坏内核的隔离机制(例如，安全漏洞)。Xv6执行许多检查来避免这些风险。例如，if(ph.vaddr + ph.memsz < ph.vaddr)检查总和是否溢出64位整数。危险在于，用户可以用指向用户选择的地址的ph.vaddr和足够大的ph.memsz构造ELF二进制文件，使得总和溢出到0x1000，这看起来像是一个有效值。在xv6的旧版本中，用户地址空间也包含内核(但在用户模式下不可读/可写)，用户可以选择一个对应于内核内存的地址，从而将ELF二进制文件中的数据复制到内核中。在xv6的RISC-V版本中，这种情况不会发生，因为内核有自己独立的页表；loadseg加载到进程的页表中，而不是内核的页表中。 内核开发人员很容易忽略一个关键的检查，而现实世界中的内核有很长一段遗漏检查的历史，用户程序可以利用这些遗漏检查来获得内核特权。很可能xv6没有完成验证提供给内核的用户级数据的完整工作，恶意用户程序可能会利用这一点绕过xv6的隔离。
现实世界 像大多数操作系统一样，xv6使用分页硬件进行内存保护和映射。大多数操作系统通过结合分页和缺页异常，比xv6更复杂地使用分页，我们将在第5章讨论4. Xv6通过内核使用虚拟地址和物理地址之间的直接映射，并假设在内核预期加载的地址0x8000000处有物理RAM，从而得到了简化。这在QEMU中是可行的，但是在真实的硬件上却不是一个好主意；真实的硬件将RAM和设备放置在不可预测的物理地址，因此(例如)在xv6期望能够存储内核的0x8000000处可能没有RAM。更严重的内核设计利用页表将任意的硬件物理内存布局转换成可预测的内核虚拟地址布局。 RISC-V支持物理地址级别的保护，但是xv6不使用该特性。在具有大量内存的机器上，使用RISC-V对“超级页面”的支持可能是有意义的当物理内存很小时，小页面是有意义的，它允许细粒度地分配和分页到磁盘。例如，如果一个程序只使用8千字节的内存，那么给它一整页4兆字节的超级物理内存就是浪费。较大的页面在 具有大量RAM的机器，并且可以减少页表操作的开销。 xv6内核缺少可以为小对象提供内存的类似malloc的分配器，这使得内核无法使用需要动态分配的复杂数据结构。内存分配是一个长期的热门话题，基本问题是有效利用有限的内存和为未知的未来请求做准备[8]. 今天人们更关心速度而不是空间效率。此外，更复杂的内核可能会分配许多不同大小的小块，而不是(像xv6中那样)只分配4096字节的块；一个真正的内核分配器需要 处理小额分配和大额分配。
练习 解析RISC-V的设备树，找出计算机拥有的物理内存量。 编写一个用户程序，通过调用sbrk(1)将其地址空间增加一个字节。运行程序，并在调用sbrk之前和之后调查程序的页表。内核分配了多少空间？新内存的PTE包含什么？ 修改xv6，为内核使用超级页面。 修改xv6以便当用户程序取消引用一个空指针时，它会收到一个异常。也就是说，修改xv6，以便不为用户程序映射虚拟地址0。 exec的Unix实现传统上包括对shell脚本的特殊处理。如果要执行的文件以文本#开头！，那么第一行被当作一个程序来运行以解释文件。例如，如果调用exec首先运行myprog arg1和myprog的行是#！/interp，然后exec用命令行/interp myprog arg1运行/interp。在xv6中实现对该约定的支持。 为内核实现地址空间随机化。