MIT 6.S081 Lab: page tables

23 Jul 2022

God helps those who help themselves.

开始学习MIT的操作系统6.S081课程的第三个Lab。Lab内容为学习内核如何操作用户进程页表。

Speed up system calls

一些操作系统(例如Linux)通过在用户空间和内核之间共享只读区域(read-only region)中的数据来加速某些系统调用。这就消除了执行这些系统调用时的内核交叉(kernel crossings 例如内核将系统调用的返回结果写到用户空间)。为了学习如何将映射插入到页表中，第一个任务是为xv6中的getpid()系统调用实现这种优化。

在创建每个进程时，在USYSCALL(在memlayout.h中定义的VA位置)映射一个只读页。在这个页的开始，存储一个struct usycall(也定义在memlayout.h中)，并初始化它来存储当前进程的PID。对于这个实验室，ugetpid()的代码已经在用户空间侧提供，它将使用USYSCALL虚拟地址。

我的做法是,

在 kernel/proc.h 为 struct proc 增加一个字段 uint64 speedUp 记录这个加速只读页的物理地址。

在 kernel/proc.c 的 allocproc 函数为 speedUp 字段调用 kalloc 分配物理页，并初始化内容（进程PID）。

  // Allocate a page for syscall speed-up
  if((p->speedUp = (uint64)kalloc()) == 0) {
 freeproc(p);
 release(&p->lock);
 return 0;
  }
  ((struct usyscall *)p->speedUp)->pid = p->pid;

在 kernel/proc.c 的 proc_pagetable 函数中通过调用 mappages 增加 VA USYSCALL 到 PA p->speedUp 的映射。这里要小心错误处理。

  // map one readonly page at USYSCALL, for ugetpid in ulib.c
  if(mappages(pagetable, USYSCALL, PGSIZE,
           (uint64)(p->speedUp), PTE_U | PTE_R ) < 0) {
 uvmunmap(pagetable, TRAPFRAME, 1, 0);
 uvmunmap(pagetable, TRAMPOLINE, 1, 0);
 uvmfree(pagetable, 0);
 return 0;
  }

在释放进程资源时，需要注意对于SpeedUp物理页的释放与页表的释放。g页表的释放主要是页表中去掉（unmap）映射（USYSCALL TRAMPOLINE TRAPFRAME）后，调用 uvmfree 释放页表的物理页。函数 uvmfree 的实现值得一看，主要流程是 unmap 映射 process memory 后，通过 freewalk 函数深度优先搜索这个页表（因为页表实现是一个树）。freewalk的 precondition 就是所有叶映射已经去除(All leaf mappings must already have been removed.)，然后实现上递归地释放这棵树的非叶节点。
```
  // in freeproc function
  if(p->speedUp)
 kfree((void*)p->speedUp);
  p->speedUp = 0;
```
```
// Free a process's page table, and free the
// physical memory it refers to.
void
proc_freepagetable(pagetable_t pagetable, uint64 sz)
{
  uvmunmap(pagetable, USYSCALL, 1, 0);
  uvmunmap(pagetable, TRAMPOLINE, 1, 0);
  uvmunmap(pagetable, TRAPFRAME, 1, 0);
  uvmfree(pagetable, sz);
}
```

Print a page table

定义一个名为vmprint()的函数，其接受一个pagetable_t参数，并按照LAB描述的格式打印该pagetable。在 kernel/exec.c 的 exec 函数返回 argc 之前插入 if(p->pid==1) vmprint(p->pagetable)，以打印第一个进程的页表。

我的实现方式是深度优先搜索页表，根据 PTE_R | PTE_W | PTE_X 判断当前 PTE 是一个 Page Directory 还是一个叶映射，

static void
printTAB(pagetable_t tab, int pre)
{
  for(int i = 0; i < 512; ++i){
    pte_t pte = tab[i];
    uint64 pa = PTE2PA(pte);
    
    if((pte & PTE_V) == 0)
      continue;

    for(int j = 0; j < pre; ++j)
        printf(" ..");
    printf("%d: pte %p pa %p\n", i, pte, pa);
    if((pte & (PTE_R|PTE_W|PTE_X)) == 0){
      // this PTE points to a lower-level page table.
      printTAB((pagetable_t)pa, pre+1);
    }
  }
}

// Print a page table
void
vmprint(pagetable_t pagetable)
{
  printf("page table %p\n", pagetable);
  printTAB(pagetable, 1);
}

Detecting which pages have been accessed

一些垃圾收集器(GC)可以从页面的被访问(读或写)信息中受益。当前任务是向xv6添加一个新特性。该特性通过检查RISC-V页表中的访问位 PTE_A 以获取该页访问信息，并将其报告给用户空间。RISC-V 硬件 page walker 在解析TLB丢失时在PTE中标记这些位。

需要的工作是实现系统调用 pgaccess ，报告哪些页面被访问。这个系统调用接受三个参数。首先，它接受需要要检查的第一个用户页的起始虚拟地址。其次，它接受需要检查的页数。最后，它需要一个缓冲区（用户空间虚拟地址），调用的返回结果会存储到这个地址开始的位掩码中(位掩码是一种每页使用一位的数据结构，其中第一页对应于最低有效位)。

几个比较需要注意的点是，

为了输出位掩码结果，更容易的做法是在内核中存储一个临时缓冲区，并在填充正确的位之后(通过调用copyout)将其复制到用户空间。
需要设置允许扫描的页数上限。
查阅 RISC-V 手册以便在 kernel/riscv.h 中定义 PTE_A 宏。检查PTE_A 是否设置后，一定要清除 PTE_A。否则，将无法确定自上次调用pgaccess 以后是否访问了该页面(即，该位将永远设置)。

具体代码就是处理参数后通过调用 walk 获取 PTE 的内容，以读取PTE_A。

// in kernel/sysproc.c
#ifdef LAB_PGTBL
#define NPAGE_LIMITS 32
int
sys_pgaccess(void)
{
  uint64 va, buf;
  int npage;
  uint32 bitmasks = 0;

  if(argaddr(0, &va) < 0)
    return -1;
  if(argint(1, &npage) < 0 || npage > 64)
    return -1;
  if(argaddr(2, &buf) < 0)
    return -1;
  
  
  for(int i = 0; i < npage; ++i){
    pte_t * ptr = walk(myproc()->pagetable, va + i * PGSIZE, 0);
    if((*ptr) & PTE_A) {
      bitmasks |= (1 << i);
      // clear access bit
      *ptr &= (~PTE_A);
    }
  }

  // write bitmask to buf
  copyout(myproc()->pagetable, buf, (char *)&bitmasks, 4);
  return 0;
}
#endif

Conclusion

Lab的内容很简单。收获比较大的是内核如何遍历用户空间的页表，如何在页表中实现 VA -> PA 的映射与去映射，分配与释放用户页表，深刻理解页表也需要驻留内存的现实。

Reference

operating-system