这是我自学 MIT6.S081 操作体系课程的 lab 代码笔记第五篇：Lazy page allocation。此 lab 大致耗时：5小时。

课程地址：pdos.csail.mit.edu/6.S081/2020…
Lab 地址：pdos.csail.mit.edu/6.S081/2020…
我的代码地址：github.com/Miigon/my-x…
Commits: github.com/Miigon/my-x…

本文中代码注释是编写博客的时分参加的，原库房中的代码或许缺少注释或代码不完全相同。

Lab 5: Lazy Page Allocation

One of the many neat tricks an O/S can play with page table hardware is lazy allocation of user-space heap memory. Xv6 applications ask the kernel for heap memory using the sbrk() system call. In the kernel we’ve given you, sbrk() allocates physical memory and maps it into the process’s virtual address space. It can take a long time for a kernel to allocate and map memory for a large request. Consider, for example, that a gigabyte consists of 262,144 4096-byte pages; that’s a huge number of allocations even if each is individually cheap. In addition, some programs allocate more memory than they actually use (e.g., to implement sparse arrays), or allocate memory well in advance of use. To allow sbrk() to complete more quickly in these cases, sophisticated kernels allocate user memory lazily. That is, sbrk() doesn’t allocate physical memory, but just remembers which user addresses are allocated and marks those addresses as invalid in the user page table. When the process first tries to use any given page of lazily-allocated memory, the CPU generates a page fault, which the kernel handles by allocating physical memory, zeroing it, and mapping it. You’ll add this lazy allocation feature to xv6 in this lab.

完成一个内存页懒分配机制，在调用 sbrk() 的时分，不当即分配内存，而是只作记录。在访问到这一部分内存的时分才进行实践的物理内存分配。

本次 lab 分为三个部分，但其实都是属于同一个试验的不同步骤，所以本文将三点集合到一同：

Eliminate allocation from sbrk() (easy)
Lazy allocation (moderate)
Lazytests and Usertests (moderate)

Lazy allocation & Tests

首要修正 sys_sbrk，使其不再调用 growproc()，而是只修正 p->sz 的值而不分配物理内存。

// kernel/sysproc.c
uint64
sys_sbrk(void)
{
  int addr;
  int n;
  struct proc *p = myproc();
  if(argint(0, &n) < 0)
    return -1;
  addr = p->sz;
  if(n < 0) {
    uvmdealloc(p->pagetable, p->sz, p->sz+n); // 假如是缩小空间，则马上开释
  }
  p->sz += n; // 懒分配
  return addr;
}

修正 usertrap 用户态 trap 处理函数，为缺页反常添加检测，假如为缺页反常（(r_scause() == 13 || r_scause() == 15)），且产生反常的地址是因为懒分配而没有映射的话，就为其分配物理内存，并在页表树立映射：

// kernel/trap.c
//
// handle an interrupt, exception, or system call from user space.
// called from trampoline.S
//
void
usertrap(void)
{
  // ......
    syscall();
  } else if((which_dev = devintr()) != 0){
    // ok
  } else {
    uint64 va = r_stval();
    if((r_scause() == 13 || r_scause() == 15) && uvmshouldtouch(va)){ // 缺页反常，并且产生反常的地址进行过懒分配
      uvmlazytouch(va); // 分配物理内存，并在页表创建映射
    } else { // 假如不是缺页反常，或者是在非懒加载地址上产生缺页反常，则抛出过错并杀死进程
      printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
      printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
      p->killed = 1;
    }
  }
  // ......
}

uvmlazytouch 函数负责分配实践的物理内存并树立映射。懒分配的内存页在被 touch 后就能够被使用了。
uvmshouldtouch 用于检测一个虚拟地址是不是一个需要被 touch 的懒分配内存地址，具体检测的是：

1. 处于 [0, p->sz)地址规模之中（进程请求的内存规模）
2. 不是栈的 guard page（具体见 xv6 book，栈页的低一页故意留成不映射，作为岗兵用于捕捉 stack overflow 过错。懒分配不应该给这个地址分配物理页和树立映射，而应该直接抛出反常）
   （处理 usertests 中的 stacktest 失利的问题）
3. 页表项不存在

// kernel/vm.c
// touch a lazy-allocated page so it's mapped to an actual physical page.
void uvmlazytouch(uint64 va) {
  struct proc *p = myproc();
  char *mem = kalloc();
  if(mem == 0) {
    // failed to allocate physical memory
    printf("lazy alloc: out of memory\n");
    p->killed = 1;
  } else {
    memset(mem, 0, PGSIZE);
    if(mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
      printf("lazy alloc: failed to map page\n");
      kfree(mem);
      p->killed = 1;
    }
  }
  // printf("lazy alloc: %p, p->sz: %p\n", PGROUNDDOWN(va), p->sz);
}
// whether a page is previously lazy-allocated and needed to be touched before use.
int uvmshouldtouch(uint64 va) {
  pte_t *pte;
  struct proc *p = myproc();
  return va < p->sz // within size of memory for the process
    && PGROUNDDOWN(va) != r_sp() // not accessing stack guard page (it shouldn't be mapped)
    && (((pte = walk(p->pagetable, va, 0))==0) || ((*pte & PTE_V)==0)); // page table entry does not exist
}

因为懒分配的页，在刚分配的时分是没有对应的映射的，所以要把一些原本在遇到无映射地址时会 panic 的函数的行为改为直接疏忽这样的地址。

uvmummap()：取消虚拟地址映射

// kernel/vm.c
// 修正这个处理了 proc_freepagetable 时的 panic
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  uint64 a;
  pte_t *pte;
  if((va % PGSIZE) != 0)
    panic("uvmunmap: not aligned");
  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    if((pte = walk(pagetable, a, 0)) == 0) {
      continue; // 假如页表项不存在，越过当时地址 （原本是直接panic）
    }
    if((*pte & PTE_V) == 0){
      continue; // 假如页表项不存在，越过当时地址 （原本是直接panic）
    }
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }
}

uvmcopy()：将父进程的页表以及内存复制到子进程

// kernel/vm.c
// 修正这个处理了 fork 时的 panic
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  char *mem;
  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0)
      continue; // 假如一个页不存在，则认为是懒加载的页，疏忽即可
    if((*pte & PTE_V) == 0)
      continue; // 假如一个页不存在，则认为是懒加载的页，疏忽即可
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    if((mem = kalloc()) == 0)
      goto err;
    memmove(mem, (char*)pa, PGSIZE);
    if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
      kfree(mem);
      goto err;
    }
  }
  return 0;
 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}

copyin() 和 copyout()：内核/用户态之间互相复制数据

因为这里或许会访问到懒分配可是还没实践分配的页，所以要加一个检测，确保 copy 之前，用户态地址对应的页都有被实践分配和映射。

// kernel/vm.c
// 修正这个处理了 read/write 时的过错 (usertests 中的 sbrkarg 失利的问题)
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;
  if(uvmshouldtouch(dstva))
    uvmlazytouch(dstva);
  // ......
}
int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  uint64 n, va0, pa0;
  if(uvmshouldtouch(srcva))
    uvmlazytouch(srcva);
  // ......
}

至此修正完成，在 xv6 中运转 lazytests 和 usertests 都应该能够成功了。
假如在某一步呈现了 remap 或者 leaf 之类的 panic，或许是因为页表项没有开释干净。能够从之前 pgtbl 试验中借用打印页表的函数 vmprint 的代码，并在或许有关的体系调用中打出，便利对页表进行调试。

tip. 假如 usertests 某一步失利了，能够用 usertests [测验称号] 直接单独运转某个之前失利过的测验，例如 usertests stacktest 能够直接运转栈 guard page 的测验，而不必等候其他测验漫长的运转。