xv6内核扩展3：页表

Inspect a user-process page table 检查用户进程页表

To help you understand RISC-V page tables, your first task is to explain the page table for a user process. 为了帮助你理解 RISC-V 页表，你的第一个任务是解释用户进程的页表。

Run make qemu and run the user program pgtbltest. The print_pgtbl functions prints out the page-table entries for the first 10 and last 10 pages of the pgtbltest process using the pgpte system call that we added to xv6 for this lab. The output looks as follows: 运行 make qemu 并运行用户程序 pgtbltest 。 print_pgtbl 函数使用我们为这个实验添加到 xv6 中的 pgpte 系统调用，打印出 pgtbltest 进程前 10 页和最后 10 页的页表项。输出如下：

va 0 pte 0x21FCF45B pa 0x87F3D000 perm 0x5B
va 1000 pte 0x21FCE85B pa 0x87F3A000 perm 0x5B
...
va 0xFFFFD000 pte 0x0 pa 0x0 perm 0x0
va 0xFFFFE000 pte 0x21FD80C7 pa 0x87F60000 perm 0xC7
va 0xFFFFF000 pte 0x20001C4B pa 0x80007000 perm 0x4B

For every page table entry in the print_pgtbl output, explain what it logically contains and what its permission bits are. Figure 3.4 in the xv6 book might be helpful, although note that the figure might have a slightly different set of pages than process that's being inspected here. Note that xv6 doesn't place the virtual pages consecutively in physical memory. 对于 print_pgtbl 输出中的每一页表项，解释它逻辑上包含的内容及其权限位。xv6 书中的图 3.4 可能有助于理解，但请注意，该图的页表可能与这里检查的进程的页表略有不同。请注意，xv6 不会将虚拟页连续地放置在物理内存中。

此处我们运行程序，打印结果如下：

$ pgtbltest
print_pgtbl starting
va 0x0 pte 0x21FC885B pa 0x87F22000 perm 0x5B
va 0x1000 pte 0x21FC7C5B pa 0x87F1F000 perm 0x5B
va 0x2000 pte 0x21FC7817 pa 0x87F1E000 perm 0x17
va 0x3000 pte 0x21FC7407 pa 0x87F1D000 perm 0x7
va 0x4000 pte 0x21FC70D7 pa 0x87F1C000 perm 0xD7
va 0x5000 pte 0x0 pa 0x0 perm 0x0
va 0x6000 pte 0x0 pa 0x0 perm 0x0
va 0x7000 pte 0x0 pa 0x0 perm 0x0
va 0x8000 pte 0x0 pa 0x0 perm 0x0
va 0x9000 pte 0x0 pa 0x0 perm 0x0
va 0x3FFFFF6000 pte 0x0 pa 0x0 perm 0x0
va 0x3FFFFF7000 pte 0x0 pa 0x0 perm 0x0
va 0x3FFFFF8000 pte 0x0 pa 0x0 perm 0x0
va 0x3FFFFF9000 pte 0x0 pa 0x0 perm 0x0
va 0x3FFFFFA000 pte 0x0 pa 0x0 perm 0x0
va 0x3FFFFFB000 pte 0x0 pa 0x0 perm 0x0
va 0x3FFFFFC000 pte 0x0 pa 0x0 perm 0x0
va 0x3FFFFFD000 pte 0x0 pa 0x0 perm 0x0
va 0x3FFFFFE000 pte 0x21FD08C7 pa 0x87F42000 perm 0xC7
va 0x3FFFFFF000 pte 0x2000184B pa 0x80006000 perm 0x4B
...

这里我们也将提及的图3.4放上来：

将上面的perm转为二进制并省略一些位，我们可以翻译成如下内容：

MAX_VA
==================
-X-RV (4B)
--WRV (C7)

...some pte == 0x0...

U-WRV (D7)
--WRV (7)
U-WRV (17)
UX-RV (5B)
UX-RV (5B)
==================
0

首先最上方在MAX_VA的两个PTE，首先不在用户空间，其次一个为RX，一个为RW，很明显分别为trampoline与trapframe。

接下来我们从下往上看，最下方两个PTE都为用户空间可执行可读内容，很明显是text部分，有两页代表代码大小是要大于4KB的。

然后是一页的用户空间可读可写部分，也能确认为用户data部分。

再往上看到有一页是U=0的，此页在用户页表存在但是不可访问，代表它是guard page。

最后上方的用户空间可读可写页则为实际的用户栈，向低地址增长。

剩下的大量pte 0x0则为未映射页，访问会触发缺页。

Speed up system calls 加快系统调用

Some operating systems (e.g., Linux) speed up certain system calls by sharing data in a read-only region between userspace and the kernel. This eliminates the need for kernel crossings when performing these system calls. To help you learn how to insert mappings into a page table, your task is to implement this optimization for the getpid() system call in xv6. 某些操作系统（例如 Linux）通过在用户空间和内核之间共享只读区域来加快某些系统调用。这消除了执行这些系统调用时需要内核调用的需求。为了帮助你学习如何将映射插入到页表中，你的任务是实现 xv6 中 getpid() 系统调用的这种优化。

When each process is created, map one read-only page at USYSCALL (a virtual address defined in memlayout.h). At the start of this page, store a struct usyscall (also defined in memlayout.h), and initialize it to store the PID of the current process. For this lab, ugetpid() has been provided on the userspace side and will automatically use the USYSCALL mapping. You will receive full credit for this part of the lab if the ugetpid test case passes when running pgtbltest. 每当创建一个进程时，在 USYSCALL（在 memlayout.h 中定义的虚拟地址）映射一个只读页面。在这个页面的起始处存储一个 struct usyscall （也在 memlayout.h 中定义），并将其初 始化为存储当前进程的 PID。在这个实验中， ugetpid() 已经在用户空间侧提供，并将自动使用 USYSCALL 映射。如果你在运行 pgtbltest 时 ugetpid 测试用例通过，你将获得这个实验这一部分的满分。 Some hints: 一些提示：

• Choose permission bits that allow userspace to only read the page. 选择允许用户空间只读该页面的权限位。
• There are a few things that need to be done over the lifecycle of a new page. For inspiration, understand the trapframe handling in kernel/proc.c. 在新页面的生命周期中，有一些事情需要完成。为了获得灵感，了解 kernel/proc.c 中的 trapframe 处理。

Which other xv6 system call(s) could be made faster using this shared page? Explain how. 还有哪些 xv6 系统调用可以使用这个共享页面变得更快？解释原因。

这一部分要求使用共享区域来加快系统调用，按照以下步骤实现：

1. 给进程信息增加struct usyscall *usyscall成员。
2. 在给进程分配页表的方法proc_pagetable()中：
   • 给usyscall内容分配一页的存储空间。
   • 如果分配失败需要free内存（包括之前分配给TRAPFRAME与TRAMPOLINE的）。
   • 设置usyscall->pid = p->pid。
   • map p->usyscall到USYSCALL上，需要设置PTE_R和PTE_U使用户可以只读访问。
3. 在free页表的方法proc_freetable()中也需要unmap分配的内容。因为此方法会自动处理分配的物理内存，所以我们无需手动处理。

结果如下

ugetpid_test starting
pid: 3 (manually printed)
upid: 3 (manually printed)
ugetpid_test: OK

对于追问“还有哪些 xv6 系统调用可以使用这个共享页面变得更快”，凡是只需要返回“每进程固定/几乎固定的小数据”，且安全地给用户只读暴露的，都适合放到 USYSCALL 页中，从而避免陷入内核，比如uptime(), getppid()等。

Print a page table 打印一个页表

To help you visualize RISC-V page tables, and perhaps to aid future debugging, your next task is to write a function that prints the contents of a page table. 为了帮助你可视化 RISC-V 页表，或许也能帮助未来的调试，你的下一个任务是编写一个函数，用于打印页表的内容。

We added a system call kpgtbl(), which calls vmprint() in vm.c. It takes a pagetable_t argument, and your job is to print that pagetable in the format described below. 我们添加了一个系统调用 kpgtbl() ，它调用 vmprint() 中的 vm.c 。它接受一个 pagetable_t 参数，你的任务是按照以下格式打印该页表。 When you run print_kpgtbl() test, your implementation should print the following output: 当你运行 print_kpgtbl() 测试时，你的实现应该打印以下输出：

page table 0x0000000087f22000
..0x0000000000000000: pte 0x0000000021fc7801 pa 0x0000000087f1e000
.. ..0x0000000000000000: pte 0x0000000021fc7401 pa 0x0000000087f1d000
.. .. ..0x0000000000000000: pte 0x0000000021fc7c5b pa 0x0000000087f1f000
.. .. ..0x0000000000001000: pte 0x0000000021fc705b pa 0x0000000087f1c000
.. .. ..0x0000000000002000: pte 0x0000000021fc6cd7 pa 0x0000000087f1b000
.. .. ..0x0000000000003000: pte 0x0000000021fc6807 pa 0x0000000087f1a000
.. .. ..0x0000000000004000: pte 0x0000000021fc64d7 pa 0x0000000087f19000
..0x0000003fc0000000: pte 0x0000000021fc8401 pa 0x0000000087f21000
.. ..0x0000003fffe00000: pte 0x0000000021fc8001 pa 0x0000000087f20000
.. .. ..0x0000003fffffd000: pte 0x0000000021fd4813 pa 0x0000000087f52000
.. .. ..0x0000003fffffe000: pte 0x0000000021fd00c7 pa 0x0000000087f40000
.. .. ..0x0000003ffffff000: pte 0x0000000020001c4b pa 0x0000000080007000

The first line displays the argument to vmprint. After that there is a line for each PTE, including PTEs that refer to page-table pages deeper in the tree. Each PTE line is indented by a number of " .." that indicates its depth in the tree. Each PTE line shows its virtual addresss, the pte bits, and the physical address extracted from the PTE. Don't print PTEs that are not valid. In the above example, the top-level page-table page has mappings for entries 0 and 255. The next level down for entry 0 has only index 0 mapped, and the bottom-level for that index 0 has a few entries mapped. 第一行显示 vmprint 的参数。之后，每行显示一个 PTE，包括那些指向树中更深层的页表页的 PTE。每个 PTE 行通过若干个 " .." 进行缩进，表示其在树中的深度。每个 PTE 行显示其虚拟地址、pte 位以及从 PTE 中提取的物理地址。不要打印无效的 PTE。在上述示例中，最顶层的页表页为条目 0 和 255 提供了映射。条目 0 的下一级只有索引 0 被映射，而该索引 0 的底层有几个条目被映射。 Your code might emit different physical addresses than those shown above. The number of entries and the virtual addresses should be the same. 你的代码可能会发出与上面显示的不同物理地址。条目数量和虚拟地址应该是相同的。

Some hints: 一些提示：

• Use the macros at the end of the file kernel/riscv.h. 使用文件 kernel/riscv.h 末尾的宏。
• The function freewalk may be inspirational. 函数 freewalk 可能会带来启发。
• Use %p in your printf calls to print out full 64-bit hex PTEs and addresses as shown in the example. 在您的 printf 调用中使用 %p 来打印完整的 64 位十六进制 PTE 和地址，如示例所示。
• For every leaf page in the vmprint output, explain what it logically contains and what its permission bits are, and how it relates to the output of the earlier print_pgtbl() exercise above. Figure 3.4 in the xv6 book might be helpful, although note that the figure might have a slightly different set of pages than the process that's being inspected here. 对于 vmprint 输出中的每一页叶节点，解释其逻辑包含的内容、权限位，以及它如何与上面较早的 print_pgtbl() 练习的输出相关联。xv6 书中的图 3.4 可能会有帮助，尽管请注意，该图的页面集可能与此处检查的进程略有不同。

这个任务相对来说也不是很复杂，我的solution通过以下步骤实现：

1. 实现printprefix(int nrecur)，根据recursion的数量打印".."前缀。
2. 实现printentry(uint64 va, pte_t pte, uint64 pa, int nrecur)打印一整个entry。
3. 实现printptes(pagetable_t pagetable, int nrecur, int prevva)，递归打印pte，其中有几个要点：
   • 根据nrecur计算当前的level。
   • accumva设定为除去结尾的offset的剩余累计va，计算当前accumva为((prevva << 9) + i)，当前va为accumva << (level * 9 + PGSHIFT)，PGSHIFT为offset。
   • 设定下一次递归nrecur+1，prevva = accumva。
4. 实现vmprint(pagetable_t pagetable)，即打印完当前pagetable后调用printptes()。

Use superpages 使用超级页

RISC-V 分页硬件支持两兆字节的页以及普通的 4096 字节页。较大页面的通用概念称为超级页，并且（由于 RISC-V 支持多种尺寸）2M 页面称为兆页。操作系统通过在一级页表项（PTE）中设置 PTE_V 和 PTE_R 位，并将物理页号设置为指向两兆字节物理内存区域的起始位置来创建超级页。这个物理地址必须是两兆字节对齐的（即，是两兆字节的倍数）。你可以在 RISC-V 特权手册中搜索兆页和超级页来了解这些内容；特别是第 112 页的顶部。使用超级页可以减少页表使用的物理内存量，并可以减少 TLB 缓存的未命中。对于某些程序，这会导致性能大幅提升。

你的工作是修改 xv6 内核以使用超级页。具体来说，如果用户程序调用 sbrk()的参数为 2 兆字节或更多，并且新创建的地址范围包含一个或多个以 2 兆字节对齐且至少为 2 兆字节大小的区域，内核应使用单个超级页（而不是数百个普通页）。如果运行 pgtbltest 时 superpg_fork 和 superpg_free 测试用例通过，你将获得这部分实验的满分。

Some hints: 一些提示：

• 在 user/pgtbltest.c 中读取 superpg_fork 和 superpg_free 。
• 一个好的起点是 sys_sbrk 中的 kernel/sysproc.c ，它是由 sbrk 系统调用触发的。跟踪代码路径到 growproc 函数，该函数为 sbrk 急切地分配内存。
• 你的内核需要能够分配和释放 2 兆字节的区域。修改 kalloc.c 以预留几个 2 兆字节的物理内存区域，并创建 superalloc()和 superfree()函数。你只需要少量 2 兆字节的内存块。
• 当进程拥有超级页时，在它进行分叉操作时必须分配超级页，在它退出时必须释放超级页；你需要修改 uvmcopy() 和 uvmunmap() 。
• 当 sbrk 部分释放超级页（例如释放超级页的最后 4096 字节）时，你需要将超级页"降级"为普通页。
• 真实操作系统会动态地将一组页提升为超级页。以下参考资料解释了为什么这是一个好主意以及更严肃的设计中有什么困难：Juan Navarro、Sitaram Iyer、Peter Druschel 和 Alan Cox。实用、透明的操作系统对超级页的支持。SIGOPS 操作系统评论，36(SI):89-104，2002 年 12 月。这份参考资料总结了不同操作系统对超级页实现的概述：对超级页管理机制和策略的全面分析。

实现过程：

• memlayout.h中增加define SUPERSTOP (KERNBASE + 30 * 1024 * 1024)，假设我们在此使用30页superpage。
• 增加freesuperlist，在boot时分配30页superpage。
• 增加superalloc()和superfree()，基本上是原kalloc()和kfree()的superpage版本，更改为使用freesuperlist。
• 修改walk()返回levelout，即原pte的level，并在alloc==2时分配superpage。
• 修改mappages()在对齐&待分配内存足够大时分配superpage。
• 修改uvmunmap()，在对齐&待释放内存足够大时free superpage，在levelout==1但不够大时释放部分superpage。
• 修改uvmalloc()在对齐&足够大时分配superpage。
• 修改uvmcopy()以复制superpage。

结果：

superpg_fork starting
usertrap(): unexpected scause 0xf pid=69
            sepc=0x2ec stval=0x5001 // normal behavior
superpg_fork: OK
superpg_free starting
usertrap(): unexpected scause 0xd pid=70
            sepc=0x40a stval=0xfff001 // normal behavior
superpg_free: OK
pgtbltest: all tests succeeded

最终结果：

== Test pgtbltest == 
$ make qemu-gdb
(8.0s) 
== Test   pgtbltest: ugetpid == 
  pgtbltest: ugetpid: OK 
== Test   pgtbltest: print_kpgtbl == 
  pgtbltest: print_kpgtbl: OK 
== Test   pgtbltest: superpg == 
  pgtbltest: superpg: OK 
== Test answers-pgtbl.txt == 
answers-pgtbl.txt: OK 
== Test usertests == 
$ make qemu-gdb
(88.5s) 
== Test time == 
time: OK 
Score: 41/41