MIT 6.s081 Lab5: xv6 lazy page allocation

MIT 6.s081
,

xv6 中 sbrk 的实现默认是 eager allocation，也就是一旦用户进程申请了内存，那么内核马上就会分配。但实际上，用户进程难以估量自己需要多少内存，所以往往会额外申请，导致内存消耗增加，并且有部分内存永远不会被用到。

所以可以用 lazy page allocation 来解决这个问题，sbrk 只用来记住分配了哪些用户地址（即更新 sz），而不先分配内存，直到产生了 page fault 再分配内存。

Lazytests and Usertests

partⅠ和 partⅡ 的话，Frans 教授在课上讲过了，这里就不重复了。partⅢ 就是实现 Frans 教授说的要对 xv6 做进一步的修改，这些修改都已经写在 Hints 中了：

  1. 处理 sbrk 的参数为负数的情况；
  2. 如果发生 page fault 的地址比 sbrk 分配的地址还大的时候，杀死进程；
  3. 处理用户进程通过系统调用传递了一个正确的地址，但是这个地址还没有被分配内存的情况（即修改copyin 和 copyout 等函数）。
  4. 如果发生 page fault 后没有可用内存了，杀死进程；
  5. 如果发生 page fault 的地址访问到了 guard page，杀死进程。

第一个要修改的地方在 kernel/sysproc.c#sys_sbrk 中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  if (n > 0)
    myproc()->sz = myproc()->sz + n; // just add sz, but not allocate memory.
  else {
    myproc()->sz = uvmdealloc(myproc()->pagetable, myproc()->sz, myproc()->sz + n);
  }
  return addr;
}

在前两个部分中，我们在 kernel/trap.c#usertrap 中添加了代码，那么对它进行进一步的修改，添加了一个 pgfhandler 函数，用来处理指定虚拟地址发生的 page fault：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// ...
} else if((which_dev = devintr()) != 0){
  // ok
} else if(r_scause() == 15 || r_scause() == 13) {
  // load page fault or store page fault
  uint64 va = r_stval(); // va is the address that cause the page fault
  if (pgfhandler(va) == -1) { // if can't handle the page fault, kill the process
    p->killed = 1;
  }
}
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;
}

在这个函数中，我们判断是否能够进行 page fault handle，如果不行就杀死这个进程。做了以下判断：

  1. 该虚拟地址是否在堆中；
  2. 该虚拟地址是否访问到了 guard page；
  3. 是否还有物理内存可以分配；
  4. 新分配的页是否已经映射了，防止报 remap。

如果可以处理，那么就进行处理，否则返回 0，在 usertrap 中将 p->killed 标识为 1（如果在这里面标识为 1 的话会杀死初始进程）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int
pgfhandler(uint64 va) {
  struct proc *p = myproc();
  if (va >= p->sz || PGROUNDUP(va) == p->kstack) {
    // if va is a invalid address, kill the process.
    return -1;
  } else {
    uint64 ka = (uint64) kalloc();
    if (ka == 0) {
      // if there is no memory can use, kill the process.
      return -1;
    } else {
      memset((void *) ka, 0, PGSIZE);
      va = PGROUNDDOWN(va);
      pte_t * pte;
      // avoid remap panic.
      if ((pte = walk(p->pagetable, va, 0)) != 0 && (*pte & PTE_V) != 0) {
        kfree((void *) ka);
        return -1;
      }
      // map new page above.
      if(mappages(p->pagetable, va, PGSIZE, ka, PTE_W|PTE_U|PTE_R) != 0) {
        kfree((void *) ka);
        return -1;
      }
    }
  }
  return 0;
}

注意要把 kernel/vm.c#uvmunmap 和 kernel/vm.c/uvmcopy 函数中的 panic 去掉，直接 continue 即可，因为使用了 lazy allocation 之后，在 unmap 的时候会出现 walk 不出来或者本来就没有 map 的情况，不能 panic，在 uvmcopy 的时候也会出现 walk 不出来，或者复制到了一个无效的 pte。代码就不贴出来了。

最后一步，修改 kernel/vm.c#copyin, kernel/vm.c#copyinstr, kernel/vm.c#copyout，将需要访问的用户空间地址做一个预处理，也就是调用 pgfhandler 先进行一波缺页处理，否则这些函数可能访问到没有分配的内存。

总结

本次 lab 相对简单，尤其是 Frans 教授上课已经把前两部分讲了，也很详细的讲了 page fault 是如何处理的。就是有一些细节要注意，我最开始就没想到要处理 copyin 和 copyout。