また夏を追う

最近的笔记

Lab3 Page Tables

✏️ 🔧 13 min read

警告

本文最后更新已超过 135 天。 内容可能已经过时，请注意参考时效性。

你说的 easy 不是 easy，我说的 hard 是什么 hard😭，实验难度 easy, easy, hard，结果第一题差点把我送走了……MIT，你坏事做尽 😭

实验准备

把第三章看懂（条件很简单，也很 tm 难，第三章应该是我目前为止没有把英文原本读完的一章了，实在是看不下去啊 😭），可以读中文版，也可以阅读*《现代操作系统：原理与实现》*（处理器架构有所不同但无伤大雅）。

其实把网站上橙色部分都做完就行。

不如给网站：Lab: page tables (mit.edu)

请务必完成前置要求，否则你根本不知道应该修改什么（或者是不知道为什么要修改）

还有要记住的就是：fllow the hints

Speed up your system calls

在进程被创建的同时创建一个只读页面，以便内核与用户程序的交互，这样就可以不需要每次系统调用的时候都去请求读写了，典型的一种空间换时间的提高速度的方法。这里只要求优化getpid()这个系统调用。

官方能不能把函数在那个文件都说一下啊！一个一个去找真的很累啊焯

首先，我们可以《很轻易》的在 user/ulib.c 中找到 ugetpid() 的定义：

#ifdef LAB_PGTBL
int
ugetpid(void)
{
  struct usyscall *u = (struct usyscall *)USYSCALL;
  return u->pid;
}
#endif

会发现这是灰的，但是没事！注意到第一行有一个 LIB_PGTBL，也就是当你在做 PGTBL这个实验的时候，这个函数是可以被使用的，否则就不行。

分析这个函数，可以发现用了一个 struct usyscall ，还好 MIT 告诉我们在哪里可以找到这个： kernel/memlayout.h，我们可以在里面找到一起出现的一个常量 USYSCALL。

我们可以发现，这个 u 指向的位置就是 USYSCALL 的地址，也就是说 USYSCALL 处应当存储一个 struct usyscall 才可以，根据对 ugetpid() 的描述，我们知道 USYSCALL 就存在需要我们创建的只读页表之中。

我们查看 USYSCALL 的定义：

//   USYSCALL (shared with kernel)
//   TRAPFRAME (p->trapframe, used by the trampoline)
//   TRAMPOLINE (the same page as in the kernel)
#define TRAMPOLINE (MAXVA - PGSIZE)
#define TRAPFRAME (TRAMPOLINE - PGSIZE)
#define USYSCALL (TRAPFRAME - PGSIZE)

可以发现 USYSCALL 在跳板下两个 PGSIZE 的位置（可以看教材中的图来确定位置，虽然这对实验没什么作用）

接下来跟着提示来：

  • 可以在 kernel/proc.c 中的 proc_pagetable() 中执行映射
  • 页面必须是只读的（且用户可操作）
  • 在 allocproc() 初始化进程时，开辟这个页面（初始化）
  • 需要在 freeproc() 中释放这个页面（当进程被 kill 时）

那不妨从开辟页面开始：

static struct proc*
allocproc(void) {
// ...
found:
  // Allocate a trapframe page.
  if ((p->trapframe = (struct trapframe*)kalloc()) == 0) {
    freeproc(p);
    release(&p->lock);
    return 0;
  }


  // Add
  if ((p->usyscall = (struct usyscall*)kalloc()) == 0) {
    freeproc(p);
    release(&p->lock);
    return 0;
  }
  p->usyscall->pid = p->pid;
  // ...
    return 0;
  }

这里的代码是仿照开辟 trapframe 页面的代码写的，当然，我们在这之前，还需要在 kernel/proc.h 中为 struct proc 添加一个成员变量 stryct usyscall* usyscall，以储存这个页面的地址。

在开辟完页面后，我们还需要将 pid 存进这个页面中，也就是 struct usyscall 的 pid 中。

然后，我们需要将新开辟的页面映射到物理内存上（开辟页面一律指在虚拟内存中开辟），在proc_pagetable() 中添加：

pagetable_t
proc_pagetable(struct proc* p) {
  pagetable_t pagetable;
  //...


  // map the trampoline code (for system call return)
  // at the highest user virtual address.
  // only the supervisor uses it, on the way
  // to/from user space, so not PTE_U.
  if (mappages(pagetable, TRAMPOLINE, PGSIZE,
    (uint64)trampoline, PTE_R | PTE_X) < 0) {
    uvmfree(pagetable, 0);
    return 0;
  }
  // ...


  if (mappages(pagetable, USYSCALL, PGSIZE,
    (uint64)(p->usyscall), PTE_R | PTE_U) < 0) {
    uvmunmap(pagetable, TRAPFRAME, 1, 0);
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
  }


  return pagetable;
}

这里需要注意两点：

  1. 由于是只读的，我们需要添加 PTE_R ，但注意到注释中有解释，若想在用户空间中调用，需要添加 PTE_U
  2. 在映射失败时，需要取消映射，但我们需要把前两个都取消了，为什么能想到，不妨看看上面两个 if 后面都跟着什么（顺序需要从后往前取消，因为后一个是依赖于前一个的）

最后就是删除这个页面：

static void
freeproc(struct proc* p) {
  if (p->trapframe)
    kfree((void*)p->trapframe);
  p->trapframe = 0;


  //Add
  if (p->usyscall)
    kfree((void*)p->usyscall);
  p->usyscall = 0;
  // ...
}

同样是仿照如何删除 trapframe 页面。但这里我们还需要在 proc_freepagetable 中释放页面映射的物理地址：

void
proc_freepagetable(pagetable_t pagetable, uint64 sz) {
  // ...
  // Add
  uvmunmap(pagetable, USYSCALL, 1, 0);
  // ...
}

取消虚拟内存到物理内存的映射即可。

回答一下网页上的问题：还有哪些系统调用是可以通过这种方式加速的？

这个问题很简单，这种方法本质上只是内核为用户共享了一个只读页面，因此那些需要读取内核信息的系统调用都可以使用这种方式来加速。

Print a page table

在 kernel/vm.c 中实现一个遍历进程的页表的函数 vmprint(pagetable_t pagetable)，当进程的pid == 1 时执行。

实现的方式可以参照同文件下的函数 freewalk()。

void
vmprint(pagetable_t pagetable, int level) {
  if (!level)
    printf("page table %p\n", pagetable);
  for (int i = 0;i < 512;i++) {
    pte_t pte = pagetable[i];
    if ((pte & PTE_V) && (pte & (PTE_R | PTE_W | PTE_X)) == 0) {
      // this PTE points to a lower-level page table.
      uint64 child = PTE2PA(pte);
      if (level == 0)
        printf("..%d: pte %p pa %p\n", i, pte, child);
      else if (level == 1)
        printf(".. ..%d: pte %p pa %p\n", i, pte, child);
      vmprint((pagetable_t)child, level + 1);
    }
    else if ((pte & PTE_V)) {
      printf(".. .. ..%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
    }
  }
}

显然，我们还需要在 kernel/defs.h 中注册这个函数。

最后，在 kernel/exec.c 中 return argc 之前调用即可。(这个难度确实是 easy，没骗人)

Explain the output of vmprint in terms of Fig 3-4 from the text. What does page 0 contain? What is in page 2? When running in user mode, could the process read/write the memory mapped by page 1? What does the third to last page contain?

或许可以画个图来描述？

Flow Chart

方框中数字表示索引，长方形的解释可以参见教材中的插图：

Flow Chart

参照教材中对PTE的解释，我们来分析后面的问题：

Explanation

0x0000000021fda00f 分析后十位：0000001111，可以发现是可读可写，且可被用户访问的。

Detecting which pages have been accessed

这个题一点也不 hard 。。

从一个用户页表地址开始，搜索所有被访问过的页表并返回一个bitmap 来显示这些页是否被访问过（一个比特串，从右往左数，第 位若为 则代表第 个页面被访问过）。

需要在 kernel/sysproc.c 中实现这个函数。

当然，我们可以继续跟着提示做（这个题因为有提示所以一点都不难了）

int
sys_pgaccess(void) {
  // lab pgtbl: your code here.
  uint64 buf, abits, ret = 0;
  int size;
  pte_t* pte_addr;
  pte_t pte;
  if (argaddr(0, &buf) < 0 || argaddr(2, &abits))
    return -1;
  if (argint(1, &size) < 0)
    return -1;
  pagetable_t pagetable = myproc()->pagetable;
  for (int i = 0;i < size;i++) {
    pte_addr = walk(pagetable, buf, 0);
    pte = *pte_addr;
    if (pte & PTE_A) {
      *pte_addr = pte & (~PTE_A);
      ret |= (1 << i);
    }
    buf += PGSIZE;
  }
  if (copyout(pagetable, abits, (char*)&ret, sizeof(ret)) < 0)
    return -1;
  return 0;
}

主要注意四点：

  1. 我们需要在 kernel/defs.h 中注册 walk() 函数才可以使用（不知道为什么这个函数是存在的但是没被注册）
  2. PTE_A 这个值是需要在 kernel/riscv.h 中定义的，具体是第几位可以看上面关于 PTE 中 FLAGS 的图。
  3. 计数后需要把页面设置为未访问，也就是把那一位设为 0 ，与上掩码的反码就可以了。
  4. 为什么 ret 不是自加而是要这么运算呢，请注意要求返回的结果是 bitmap。

如果你中途出错的话，或许可以使用vmprint()来 debug。

最终成绩

Final Grade

最后记得 git add . && git commit -m "finish"

其实我觉得这部分 xv6的教材讲的比较简略，可以看 《现代操作系统：原理与实现》 做进一步了解（不知道CSAPP行不行，我还没看到那）

🕸️ 关系图谱