在本 lab 中，我们将进行页表机制的探索。
Preparation
切换到对应分支
1$ git fetch
2$ git checkout pgtbl
3$ make clean
Task1: Speed up system calls
该任务要求我们在进程虚拟地址空间中添加一个固定项：USYSCALL，该页的开头字段为当前进程 pid，这样一来 getpid() 就不用陷入内核，而是直接通过访问虚拟地址即可获取，从而加快速度。
用户层函数 ugetpid() 已经为我们实现好了，我们只需要关注内核中，更具体来讲，是新建进程时初始化虚拟地址空间动作中发生的事。
进程会在两个时候被创建，一个是 userinit()(kernel/proc.c)时，一个是调用 fork() 时。进程的创建会调用 kernel/proc.c 中的 allocproc()，然后通过 proc_pagetable() 来初始化页表。
我们要做的很简单。
第一步，在页表初始化时加入一个 {USYSCALL => PHYPAGE} 的 PTE。USYSCALL 在 kernel/memlayout.h 中定义（就是 TRAPFRAME 的前一页），而 PHYPAGE 则需要我们调用 kalloc()(kernel/kalloc.c) 进行空闲页分配。
第二步，也就是正确完成页表初始化后，将 pid 写入 PHYPAGE。
#ifdef LAB_PGTBL是灰的不要紧，make时会自动帮我们 define。
PHYPAGE 的分配操作只能在 allocproc() 中进行，因为一旦分配失败，我们需要释放当前进程。为了让同一 PHYPAGE 能被 proc_pagetable() 访问，我在 struct proc 中添加了 usyscall 字段（这些都是参考了 trapframe 的初始化流程）。
1static struct proc*
2allocproc(void)
3{
4 ...
5found:
6 ...
7 // Allocate a trapframe page and a usyscall page.
8 if((p->trapframe = (struct trapframe *)kalloc()) == 0 ||
9 (p->usyscall = (struct usyscall *)kalloc()) == 0){
10 ...
11 }
12
13 // An empty user page table.
14 p->pagetable = proc_pagetable(p);
15 if(p->pagetable == 0){
16 ...
17 }
18
19 p->usyscall->pid = p->pid;
20 ...
21}
添加 PTE 的操作很简单，页表相关操作都在 kernel/vm.c 中，我们需要关注 mempages() 函数，该函数就是为指定页表添加 PTE。唯一需要关注的就是符号控制位，根据我们的需求，该页面为只读型，而且能被用户层函数访问，那么只赋予 PTE_R|PTE_U 即可。有效位会在 mappages() 内部添加，无需操心。
如果添加失败，需要把已经添加的表项清空，并且释放页表，参考上面的代码即可。
1pagetable_t
2proc_pagetable(struct proc *p)
3{
4 ...
5 // map the trapframe just below TRAPFRAME, for speeding up getpid()
6 if (mappages(pagetable, USYSCALL, PGSIZE,
7 (uint64)p->usyscall, PTE_R | PTE_U) < 0) {
8 uvmunmap(pagetable, TRAMPOLINE, 1, 0);
9 uvmunmap(pagetable, TRAPFRAME, 1, 0);
10 uvmfree(pagetable, 0);
11 return 0;
12 }
13 ...
14}
当然，不仅要考虑分配，还要考虑释放的操作。如果到这一步就急匆匆地 make qemu; ./pgtbltest，那你马上就会得到一个 panic: freewalk leaf。这是因为我们没有在清空页表时清空我们已分配的 PHYPAGE，而这一步在 freeproc() 函数中实现。
1static void
2freeproc(struct proc *p)
3{
4 if(p->trapframe)
5 kfree((void*)p->trapframe);
6 p->trapframe = 0;
7
8 if (p->usyscall) // (!new)
9 kfree((void*)p->usyscall); // (!new)
10 p->usyscall = 0; // (!new)
11
12 if(p->pagetable)
13 proc_freepagetable(p->pagetable, p->sz);
14 p->pagetable = 0;
15 p->sz = 0;
16 p->pid = 0;
17 p->parent = 0;
18 p->name[0] = 0;
19 p->chan = 0;
20 p->killed = 0;
21 p->xstate = 0;
22 p->state = UNUSED;
23}
当然还要关注页表对应页的释放操作，proc_freepagetable()(kernel/proc.c) 的注释讲的很清楚：Free a process’s page table, and free the physical memory it refers to. 并且它也给了提示：要调用 uvmunmap()。所以新增一行即可，实际的释放操作会在 uvmunmap() 中完成：
1void
2proc_freepagetable(pagetable_t pagetable, uint64 sz)
3{
4 uvmunmap(pagetable, TRAMPOLINE, 1, 0);
5 uvmunmap(pagetable, TRAPFRAME, 1, 0);
6 uvmunmap(pagetable, USYSCALL, 1, 0); // (!new)
7 uvmfree(pagetable, sz);
8}
Task2: Print a page table
现在我们需要按照给定格式，在 kernel/exec.c:119 插入 if(p->pid==1) vmprint(p->pagetable) 来输出初始进程的页表，以可视化并有助于 debug。
参考 kernel/vm.c 中的 freewalk()，我们主要关注的是它以怎样的方式遍历页目录结构——获取表项，得到物理地址，根据标志位判断这一物理地址是页表还是数据页，决定是否需要进一步深入。
在 xv6 中，每个页表项的低位为标志位，如下图所示：
kernel/riscv.h中已经为我们定义好了若干标志位，直接使用即可。
1void
2freewalk(pagetable_t pagetable)
3{
4 ...
5 for(int i = 0; i < 512; i++){
6 pte_t pte = pagetable[i];
7 if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
8 // this PTE points to a lower-level page table.
9 uint64 child = PTE2PA(pte);
10 freewalk((pagetable_t)child);
11 ...
12 }
13 ...
14 }
15 ...
16}
不难发现，判断的条件就是 (pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X) == 0，PTE_V 位意味着该页表项中的物理地址是已分配的，PTE_R|PTE_W|PTE_X 意味着这一物理地址对应的是页表，而非数据项。
此外，我们还需要根据当前页表的 level 来打印，毕竟 level 越低，前面的 .. 越多，所以还需要一个额外的 vmprintwalk() 函数。
那么先在 kernel/def.h 中添加函数签名，然后修改 kernel/exec.c，最后就是在 kernel/vm.c 下加入两个函数的代码了。
1void
2vmprint(pagetable_t pagetable)
3{
4 printf("page table %p\n", pagetable); // 用 %p 来进行十六进制格式化
5 vmprintwalk(pagetable, 2);
6}
7
8void
9vmprintwalk(pagetable_t pagetable, int level)
10{
11 // there are 2^9 = 512 PTEs in a page table.
12 for (int i = 0; i < 512; i++) {
13 pte_t pte = pagetable[i];
14 if (pte & PTE_V) {
15 uint64 child = PTE2PA(pte);
16 for (int i = 0; i < 2-level; i++) {
17 printf(".. ");
18 }
19 printf("..%d: pte %p pa %p\n", i, pte, child);
20 if (level && (pte & (PTE_R|PTE_W|PTE_X)) == 0) {
21 vmprintwalk((pagetable_t)child, level-1); // 这里需要用类型转换，否则编译报错
22 }
23 }
24 }
25}
Task3: Detecting which pages have been accessed
该任务要求我们利用跟踪哪些页被访问过，并且通过用户层函数 pgaccess() 来获取自从上一次调用以来被访问过的页。
既然如此，那每个页表项就需要一个「访问位」咯，根据上面那张图，我们可以在 kernel/riscv.h 中添加一行 #define PTE_A (1L << 6)，方便进行位运算。
lab 已经贴心地为我们做好了所有准备工作，包括修改 usys.pl、注册系统调用等，所以我们只需要在 kernel/sysproc.c 中实现 sys_pgaccess() 函数即可。
查看 user/user.h 中 pgaccess() 的函数签名我们发现，我们需要接收三个参数，分别是一个虚拟地址 vba，一个整型 npages，和一个指针 vp，用 argaddr() 与 argint() 处理得到参数后，检查一下地址是否越界——pgaccess 的作用是追踪 vba 开始 npages 个页面的被访问情况，那么最大的地址一定不能超过 MAXVA，否则直接返回 -1。
然后根据得到的基地址，逐页查页表，检查指向数据页的那个页表项的 PTE_A 位，如果为 1，则将 vp 指针指向内存的第 i 个 bit 置 1。这就是一个简单的检查某页是否被访问过的流程。
根据
sys_sysinfo()的知识，这里必须用copyout()拷贝数据到vp指向的内存。
那么如何根据页表找到最终的页表项呢？kernel/vm.c 中为我们提供了 walk() 的 API，它根据虚拟地址，返回指向数据页的那个页表项的指针。还有一个叫 walkaddr() 的，是直接返回物理页的起始地址，后面有用，这里暂时用不到。
1int
2sys_pgaccess(void)
3{
4 uint64 vba; // virtual base address
5 int npages;
6 uint64 vp;
7 if (argaddr(0, &vba) < 0 || argint(1, &npages) < 0 || argaddr(2, &vp) < 0) {
8 return -1;
9 }
10
11 // 检查地址是否溢出虚拟内存空间
12 vba = PGROUNDDOWN(vba);
13 if (vba + npages*PGSIZE > MAXVA) {
14 return -1;
15 }
16
17 unsigned int abits = 0;
18 struct proc* p = myproc();
19 pagetable_t pagetable = p->pagetable;
20
21 for (int i = 0; i < npages; i++) {
22 uint64 va = vba + i*PGSIZE;
23 pte_t* pte = walk(pagetable, va, 0); // 直接用会报 error: implicit declaration of function ‘walk’
24 // 需要在 kernel/def.h 中添加声明
25 if (*pte & PTE_A) {
26 abits |= 1 << i;
27 *pte &= ~PTE_A; // 由于是上一次调用以来的访问情况，故每次调用都要解除访问
28 }
29 }
30
31 copyout(pagetable, vp, (char*)&abits, sizeof(abits));
32 return 0;
33}
现在还有一个问题，PTE_A 位是我们新增的，也就是说 lab 并没有实现在什么地方将其置 1，就需要我们找一个合适的位置去置位，不然 *pte & PTE_A 将毫无意义。
前面提到的 walkaddr() 可以解决该问题。毕竟每次访问物理页的时候必然要经过这个调用，它返回的物理页起始地址，那肯定是要有人去访问的——就算没人访页，那也视为去访问了——所以，u know，在返回前置位即可。毕竟，这是访问物理页的唯一通道。
如果加在
walk()里，那么sys_pgaccess()检查的每一页，都会因为调用了walk()而置PTE_A=1，这肯定是不行的。
1uint64
2walkaddr(pagetable_t pagetable, uint64 va)
3{
4 pte_t *pte;
5 uint64 pa;
6
7 if(va >= MAXVA)
8 return 0;
9
10 pte = walk(pagetable, va, 0);
11 if(pte == 0)
12 return 0;
13 if((*pte & PTE_V) == 0)
14 return 0;
15 if((*pte & PTE_U) == 0)
16 return 0;
17 *pte |= PTE_A; // (!new)
18 pa = PTE2PA(*pte);
19 return pa;
20}
测试结果
1$ make grade
2...
3== Test pgtbltest ==
4$ make qemu-gdb
5(3.4s)
6== Test pgtbltest: ugetpid ==
7 pgtbltest: ugetpid: OK
8== Test pgtbltest: pgaccess ==
9 pgtbltest: pgaccess: OK
10== Test pte printout ==
11$ make qemu-gdb
12pte printout: OK (1.0s)
13== Test answers-pgtbl.txt == answers-pgtbl.txt: OK
14== Test usertests ==
15$ make qemu-gdb
16(125.0s)
17== Test usertests: all tests ==
18 usertests: all tests: OK
19== Test time ==
20time: OK
21Score: 46/46
最后的工作
git commit -am ""将所有修改提交到本地;- 执行
make handin。由于 lab0 保存了 APIKey，故直接成功提交；
可选的挑战再说吧，没有什么想做的欲望。