MIT 6.s081 Lab lazy allocation

---

Lab: xv6 lazy page allocation (mit.edu)

Page-fault exceptions

当CPU无法将虚拟地址转换成物理地址时，生成一个page-fault excecption，称为缺页异常。RISC-V中存在三种类型的缺页异常：load(load指令)/store(store指令)/instruction(指令所在的虚拟地址无法转换成物理地址)。scause寄存器中保存了异常类型，stval寄存器保存无法转换的虚拟地址。

Copy-on-write fork的基本方式是父进程和子进程初始共享相同的物理页，并将PTE设置为只读的，当子进程或父进程执行store指令对物理页进行写操作是，RISC-V抛出一个缺页异常，为发生异常的虚拟地址对应的物理页创建一个副本，并将PTE映射到该副本中，修改操作类型为可读可写，之后再对副本进行写操作。由于子进程在fork后通常会执行exec系统调用，因此在exec时子进程会产生缺页异常，内核处理这些异常并创建对应的副本，而不需要复制所有的物理页。

另一种处理缺页异常的机制称为lazy allocation，主要分为两步。第一步，在用户进程调用sbrk以扩充地址空间时，内核仅仅改变其虚拟地址空间，在页表中将这些新的虚拟地址对应的PTE置为无效，而不需要真正分配物理页。第二步，在进程访问这些新的虚拟地址产生缺页异常时，内核分配物理页并将其映射到页表中。这样做的好处是可以节省内存分配。

另一种处理缺页异常的机制称为paging from disk。当用户进程需要更多内存，而RAM中目前没有更多的可用页面进行分配时，内核从当前的内存中选择一些页面，将其调出内存，暂时保存在磁盘上，并将对应的PTE设置为无效。当进程对这些页面进行读写访问时，由于PTE无效，会产生缺页异常，内核对访问的虚拟地址进行检查，如果这一虚拟地址所在的页面当前保存在磁盘上，则选择内存中的某些页面调出内存，将需要的物理页调回内存，更新PTE并返回到用户进程继续执行。这种机制在应用程序的局部性较好时具有比较高的效率。

Eliminate allocation from sbrk()

修改系统调用sbrk(n)，当n>0时，sbrk会为进程分配n个字节，然后返回新分配区域的地址。在lazy allocation中，只有内存真正被使用时才会分配物理页，因此新的sbrk(n)只增加进程的虚拟内存大小，而不会影响其实际映射的物理页，并且返回新增加区域的起始虚拟地址。

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;
}

lazy allocation

修改trap.c的代码，当用户空间发生缺页中断时，为进程新分配一个物理页并映射到发生缺页的虚拟地址处，然后返回用户代码继续执行。

缺页中断对应scause寄存器的值为13或15，分别代表读/写，stval寄存器中保存造成缺页中断的虚拟地址va。当va超出了当前进程的内存大小时，说明出现了非法的地址访问，直接kill整个进程。

在fork中，为子进程创建页表时，通过uvmcopy将父进程的用户地址空间的内存拷贝到子进程的用户地址空间，而在lazy allocation中，如果父进程页表中的某一项PTE不存在或者该PTE对应的物理页不存在，说明在父进程中没有对该页面的访问，因此在对子进程的页表初始化时也不需要分配这些表项，而是等到真正访问时再进行分配。

在为进程新分配物理页失败时，说明当前系统的物理内存已经被占满，直接kill进程并释放对应的物理内存。

在xv6中，栈的最低一页作为guardpage，用于检测用户栈分配时出现stack overflow错误，对于guard page中的地址，不应该读写，也不应该为其分配物理页，如果出现缺页的位置在guard page中，说明出现了栈溢出，应该kill掉整个进程，根据xv6进程地址空间的排布，对应的判断条件为PGROUNDDOWN(va) == r_sp()。

完整的缺页中断处理代码如下：

void
usertrap(void)
{
	//......
  if(r_scause() == 8){
    // system call
  } else if (r_scause() == 13 || r_scause() == 15) {
    // Kill a process if it page-faults on a virtual memory address higher than any allocated with sbrk()
    // virtual address that caused the page fault
    uint64 va = r_stval();
    if (va < p->sz && PGROUNDDOWN(va) != r_sp() && 
          ((pte = walk(p->pagetable, va, 0)) == 0 || (*pte & PTE_V) == 0)) {
      char *mem = kalloc();
      if (mem == 0) {
        printf("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("mappage failed when handling page fault\n");
          kfree(mem);
          uvmdealloc(p->pagetable, PGROUNDDOWN(va), PGSIZE);
        }
      }
    } else {
      printf("illegal va: %p", va);
      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;
    }
  } else if((which_dev = devintr()) != 0){
    // ok
  } 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;
  }

  if(p->killed)
    exit(-1);

  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2)
    yield();

  usertrapret();
}

当进程将虚拟地址作为参数传递给系统调用以供内核读写(copyin&copyout)时，如果该虚拟地址刚刚通过sbrk分配，但是并没有映射到某个物理页，此时并不会触发缺页中断，而是会引起读写错误，对于这种情况应该首先检测虚拟地址是否存在对应的物理页面，如果对应的页面不存在，则先进行物理页面的分配，然后再进行读写，对应的代码如下：

// Copy from kernel to user.
// Copy len bytes from src to virtual address dstva in a given page table.
// Return 0 on success, -1 on error.
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;
  pte_t *pte;
  struct proc *p = myproc();
  if (dstva < p->sz && PGROUNDDOWN(dstva) != r_sp() && (((pte = walk(p->pagetable, dstva, 0))==0) || ((*pte & PTE_V)==0))) {
    if (dstva >= p->sz || PGROUNDDOWN(dstva) == r_sp()) {
      printf("illegal va in copyin\n");
      p->killed = 1;
      exit(-1);
    }
    char *mem = kalloc();
    if (mem == 0) {
      printf("out of memory when copyin\n");
      p->killed = 1;
      exit(-1);
    } else {
      memset(mem, 0, PGSIZE);
      if (mappages(p->pagetable, PGROUNDDOWN(dstva), PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0) {
        printf("mappage failed when handling copyin page fault\n");
        kfree(mem);
        uvmdealloc(p->pagetable, PGROUNDDOWN(dstva), PGSIZE);
      }
    }
  }

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (dstva - va0);
    if(n > len)
      n = len;
    memmove((void *)(pa0 + (dstva - va0)), src, n);

    len -= n;
    src += n;
    dstva = va0 + PGSIZE;
  }
  return 0;
}

// Copy from user to kernel.
// Copy len bytes to dst from virtual address srcva in a given page table.
// Return 0 on success, -1 on error.
int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  uint64 n, va0, pa0;
  pte_t *pte;

  struct proc *p = myproc();
  if (srcva < p->sz && PGROUNDDOWN(srcva) != r_sp() && ((pte = walk(p->pagetable, srcva, 0)) == 0 || (*pte & PTE_V) == 0)) {
    char *mem = kalloc();
    if (mem == 0) {
      printf("out of memory when copyin\n");
      p->killed = 1;
    } else {
      memset(mem, 0, PGSIZE);
      if (mappages(p->pagetable, PGROUNDDOWN(srcva), PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0) {
        printf("mappage failed when handling copyin page fault\n");
        kfree(mem);
        uvmdealloc(p->pagetable, PGROUNDDOWN(srcva), PGSIZE);
      }
    }
  }
  while(len > 0){
    va0 = PGROUNDDOWN(srcva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (srcva - va0);
    if(n > len)
      n = len;
    memmove(dst, (void *)(pa0 + (srcva - va0)), n);

    len -= n;
    dst += n;
    srcva = va0 + PGSIZE;
  }
  return 0;
}

完成以上修改后，顺利通过lazytests和usertests。