MIT 6.S081 Lab5: xv6 lazy page allocation

Posted on Edited on In

很多情况都用到了Lazy allocation, 比如:

  • paging from disk
  • COW fork
  • automatically extending stack
  • memory-mapped files

xv6使用sbrk()申请物理地址空间并将其映射到进程的虚拟地址空间(向内核请求堆内存)。这个lab视频上也给了很多提示，重要的是理解并掌握原理。

实际上复杂的内核会在分配栈空间时做这样的处理, sbrk没有分配物理地址空间，只是记住分配了哪些用户地址，并在用户地址将这些地址标记为无效(invalid)。当进程尝试第一次使用任何给定Lazy Allocation的页面时，CPU会产生Page Fault的异常，该异常错误的类型会存放到scause寄存器，而stval寄存器中从存放着不能被translate的虚拟地址。
scause

Page Fault的类型:

  • load page faults, load指令不能translate地址
  • store page faults，store指令不能translate地址
  • instruction page faults，指令地址未能被tanslate

    1. Eliminate allocation from sbrk()

    1.1 Description

    将growproc函数注释掉，不分配物理地址空间，只增加进程内存的大小。

    1.2 Implementation

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

      if(argint(0, &n) < 0)
        return -1;
      addr = myproc()->sz;

      myproc()->sz += n;
      // if(growproc(n) < 0)  // Not need to allocate pysical memory.
      //   return -1;
      return addr;  // return the old size of process
    }

    2. Lazy allocation

    2.1 Description

    比如说要实现Lazy allocation, 在sbrk()系统调用时page fault异常发生，sepc寄存器保证在修补完页表之后到跳转回异常发生时执行指令的位置重新执行指令(原本的疑虑是在usertrapret()中sepc会+4即跳转到当前指令的下一条指令，实际上在lab3中才有自增4这条语句= =)。若没有空闲的物理内存，则返回错误，并且kill进程。如果sbrk()缩减堆内存，page fault就不会发生。

uvmunmap产生panic的原因是因为sbrk()已经分配物理内存但该物理内存未被使用。

在printf之前修改代码，使得echo hi正确执行。
Some hint:

  • You can check whether a fault is a page fault by seeing if r_scause() is 13 or 15 in usertrap().
  • r_stval() returns the RISC-V stval register, which contains the virtual address that caused the page fault.
  • Steal code from uvmalloc() in vm.c, which is what sbrk() calls (via growproc()). You’ll need to call kalloc() and mappages().
  • Use PGROUNDDOWN(va) to round the faulting virtual address down to a page boundary.
  • uvmunmap() will panic; modify it to not panic if some pages aren’t mapped.
  • If the kernel crashes, look up sepc in kernel/kernel.asm
  • Use your vmprint function from pgtbl lab to print the content of a page table.
  • If you see the error “incomplete type proc”, include “spinlock.h” then “proc.h”.

    2.2 Implementation

    kernel/trap:usertrap
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    else if (r_scause() == 13 || r_scause() == 15) {
        // check whether a fault is a page fault
        uint64 va = r_stval();
        printf("page fault: %p\n", va);
        // lazy allocation before printf information.
        char* mem = kalloc();  // allocate one page of physical memory. 
        if (mem == 0) {
          p->killed = 1;
        } else {
          memset(mem, 0, PGSIZE);  // set all zeros.
          if (mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)mem, PTE_W|PTE_R|PTE_U) != 0) {
            kfree(mem);
            p->killed = 1;
          }
        }
    }
    kernel/vm.c:uvmunmap, 如果这一部分不用continue来处理，在接下来的code，刚分配的物理内存就会被释放掉。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
        if((pte = walk(pagetable, a, 0)) == 0)
            panic("uvmunmap: walk");
        if((*pte & PTE_V) == 0)
            // panic("uvmunmap: not mapped");
            continue;
        if(PTE_FLAGS(*pte) == PTE_V)
            panic("uvmunmap: not a leaf");
        if(do_free){
            uint64 pa = PTE2PA(*pte);
            kfree((void*)pa);
        }
        *pte = 0;
    }

    3. Lazytests and Usertests

    3.1 Description

    如果sbrk()缩减堆空间大小而不是扩大，注意proc.sz为无符号整型数，和一个int型数相加，有符号数会向无符号数发生隐式地转换。还需要注意uvmunmap的walk panic，已经改变sz但未分配物理地址，在释放就会出现panic，只需要执行continue即可。out of memory测试。同时xv6book中第三章有说guard page的PTE_V未设置，注意参考第三章给出的用户地址空间的布局。xv6中为用户栈分配了一个页

Some hints:

  • Handle negative sbrk() arguments.
  • Kill a process if it page-faults on a virtual memory address higher than any allocated with sbrk().
  • Handle the parent-to-child memory copy in fork() correctly.
  • Handle the case in which a process passes a valid address from sbrk() to a system call such as read or write, but the memory for that address has not yet been allocated.
  • Handle out-of-memory correctly: if kalloc() fails in the page fault handler, kill the current process.
  • Handle faults on the invalid page below the user stack.

    3.2 Implementation

总结