MIT 6s081 lab 5: xv6 lazy page allocation

Page faults

Basic

通过page fault可以实现一系列的虚拟内存功能：

• lazy allocation
• copy-on-write fork
• demand paging
• memory mapped files

虚拟内存的两个主要的优点：

1、隔离性：每个应用程序拥有自己的地址空间，因此不可能修改其他应用程序的内存数据，同时用户空间和内核空间也具备隔离性

2、抽象，处理器和指令可以使用虚拟地址，内核会定义从虚拟地址到物理地址的映射关系

page fault可以使得地址映射关系变得动态，内核可以更新page table，内核将会有巨大的灵活性

内核使用三个重要信息来响应page fault：

• 出错的虚拟内存地址（存放在STVAL寄存器中）
• 出错的原因（存放在SCAUSE寄存器中）
• 引起page fault时的程序计数器值，代表page fault发生的位置（存放在SEPC寄存器）

page fault同样使用trap机制来进入内核空间。

Lazy page allocation

sbrk是XV6提供的系统调用，它使得用户应用程序能扩大自己的heap。当一个应用程序启动的时候，sbrk指向的是heap的最底端，同时也是stack的最顶端。这个位置通过代表进程的数据结构中的sz字段表示.

当sbrk实际发生或者被调用的时候，内核会分配一些物理内存，并将这些内存映射到用户应用程序的地址空间，然后将内存内容初始化为0，再返回sbrk系统调用。这样，应用程序可以通过多次sbrk系统调用来增加它所需要的内存。类似的，应用程序还可以通过给sbrk传入负数作为参数，来减少或者压缩它的地址空间。

在XV6中，sbrk的实现默认是eager allocation。这表示了，一旦调用了sbrk，内核会立即分配应用程序所需要的物理内存。但是实际上，对于应用程序来说很难预测自己需要多少内存，所以通常来说，应用程序倾向于申请多于自己所需要的内存。

利用lazy allocation，核心思想非常简单，sbrk系统调基本上不做任何事情，唯一需要做的事情就是提升p->sz，将p->sz增加n，其中n是需要新分配的内存page数量。但是内核在这个时间点并不会分配任何物理内存。之后在某个时间点，应用程序使用到了新申请的那部分内存，这时会触发page fault，这时再分配需要的物理内存，然后再去执行

lab5:xv6 lazy page allocation

作业地址：Lab: xv6 lazy page allocation (mit.edu)

Eliminate allocation from sbrk() (easy)

根据提示，修改sys_sbrk函数，删去growproc(n)的调用，但要修改myproc()->sz

uint64
sys_sbrk(void)
{
  int addr;
  int n;

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

Lazy allocation (moderate)

根据指导书提示，修改usertrap函数，参考uvmalloc()函数，添加对page fault的处理，注意要使用PGROUNDDOWN(va)来对齐，建立完整的一页

void
usertrap(void)
{
  int which_dev = 0;

  if((r_sstatus() & SSTATUS_SPP) != 0)
    panic("usertrap: not from user mode");

  // send interrupts and exceptions to kerneltrap(),
  // since we're now in the kernel.
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();
  
  // save user program counter.
  p->trapframe->epc = r_sepc();
  
  if(r_scause() == 8){
    // system call

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

    // sepc points to the ecall instruction,
    // but we want to return to the next instruction.
    p->trapframe->epc += 4;

    // an interrupt will change sstatus &c registers,
    // so don't enable until done with those registers.
    intr_on();

    syscall();
  } else if((which_dev = devintr()) != 0){
    // ok
  }  // lab5 add begin
  else if(r_scause() == 13 || r_scause() == 15) // page fault 
  {
      uint64 va = r_stval(); // get the virtual address that caused the page fault.
      // printf("page fault %p\n", va);
      if(va <= p->sz) {
        char * pa = kalloc(); // alloc physial memory ，分配一页物理内存
        if(pa == 0){ // 申请失败
          p->killed = 1; // 杀死进程
        }
        else{
          memset(pa, 0, PGSIZE); //清空物理内存
          if(mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)pa, PTE_W|PTE_R|PTE_U) != 0){ //建立从va下取整开始一页的映射
            kfree(pa); // 分配失败，释放物理内存
            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;
  }

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

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

  usertrapret();
}

Lazytests and Usertests (moderate)

1、首先要处理sbrk传入的参数为负数的情况

uint64
sys_sbrk(void)
{
  int addr;
  int n;
 
  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  if(n < 0){ //如果删除内存，就直接删除，但有可能之前就没有分配
     if(growproc(n) < 0) // 修改uvmunmap函数，walk不到也不管，没有建立映射也不管
      return -1;
  }
  else{
    myproc()->sz += n;
  }
  return addr;
}

同时要修改uvmunmap函数，删除的部分内存**有可能之前就没有分配对应的页表，也可能分配了页表，但没有插入页表项，**所以需要把panic("uvmunmap: walk")和panic("uvmunmap: not mapped")注释掉，改成continue

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)
      // panic("uvmunmap: walk");
      continue;
    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;
  }
}

2、当page-faults发生的虚拟地址比之前sbrk申请的内存地址还要高，说明出现了错误，需要杀死进程，同时需要处理虚拟地址空间小于最开始栈顶指针的位置的情况，这种情况也需要杀死进程。

修改usertrap()函数：

else if(r_scause() == 13 || r_scause() == 15) // page fault 
  {
      uint64 va = r_stval(); // get the virtual address that caused the page fault.
      // printf("page fault %p\n", va);
      if(va <= p->sz && va >= p->trapframe->sp) {
        char * pa = kalloc(); // alloc physial memory ，分配一页物理内存
        if(pa == 0){ // 申请失败
          p->killed = 1; // 杀死进程
        }
        else{
          memset(pa, 0, PGSIZE); //清空物理内存
          if(mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)pa, PTE_W|PTE_R|PTE_U) != 0){ //建立从va下取整开始一页的映射
            kfree(pa); // 分配失败，释放物理内存
            p->killed = 1;
          }
        }
      }
      else p->killed = 1; // 此时出现异常的va高于p->sz，说明有问题，直接kill process
  }

3、需要处理fork时，对用户进程的页表的处理，修改uvmcopy函数（和修改uvmunmap函数类似），**有可能有的虚拟地址并没有建立页表，也有可能有的地址建立了页表，但没有添加页表项。**因此将panic("uvmcopy: pte should exist")和panic("uvmcopy: page not present")改为continue

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)
      // panic("uvmcopy: pte should exist");
      continue;
    if((*pte & PTE_V) == 0)
      // panic("uvmcopy: page not present");
      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;
}

4、需要处理read、write、pipe的系统调用，传入的虚拟地址可能是有效的（高于一开始的栈顶指针，低于sbrk分配的内存地址），但并没有分配对应的物理内存，此时需要及时地进行分配。

修改sys_read

uint64
sys_read(void)
{
  struct file *f;
  int n;
  uint64 p;

  if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argaddr(1, &p) < 0)
    return -1;

  // 判断一下addr虚拟地址对应的物理地址空间是否被申请，如果没有被申请，则申请。
  if(p <= myproc()->sz && p >= myproc()->trapframe->sp && walkaddr(myproc()->pagetable, p) == 0) {
      printf("debug: %p %d\n", p, n);
      // 如果这个虚拟地址p没有映射，那就建立映射
      char * pa = kalloc(); // alloc physial memory ，分配一页物理内存
      if(pa == 0){ // 申请失败
        myproc()->killed = 1;
        return -1;
      }
      else{
        memset(pa, 0, PGSIZE); //清空物理内存
        if(mappages(myproc()->pagetable, PGROUNDDOWN(p), PGSIZE, (uint64)pa, PTE_W|PTE_R|PTE_U) != 0){ //建立从va下取整开始一页的映射
          kfree(pa); // 分配失败，释放物理内存
          myproc()->killed = 1;
          return -1;
        }
      }
  }

  return fileread(f, p, n);
}

修改sys_write

uint64
sys_write(void)
{
  struct file *f;
  int n;
  uint64 p;
 
  if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argaddr(1, &p) < 0)
    return -1;

  if(p <= myproc()->sz && p >= myproc()->trapframe->sp && walkaddr(myproc()->pagetable, p) == 0) {
      // printf("debug: %p %d\n", p, n);
      // 如果这个虚拟地址p没有映射，那就建立映射
      char * pa = kalloc(); // alloc physial memory ，分配一页物理内存
      if(pa == 0){ // 申请失败
        myproc()->killed = 1;
        return -1;
      }
      else{
        memset(pa, 0, PGSIZE); //清空物理内存
        if(mappages(myproc()->pagetable, PGROUNDDOWN(p), PGSIZE, (uint64)pa, PTE_W|PTE_R|PTE_U) != 0){ //建立从va下取整开始一页的映射
          kfree(pa); // 分配失败，释放物理内存
          myproc()->killed = 1;
          return -1;
        }
      }
  }

  return filewrite(f, p, n);
}

修改sys_pipe

uint64
sys_pipe(void)
{
  uint64 fdarray; // user pointer to array of two integers
  struct file *rf, *wf;
  int fd0, fd1;
  struct proc *p = myproc();

  if(argaddr(0, &fdarray) < 0)
    return -1;

  // 这里同理，要加判断
  if(fdarray <= myproc()->sz && fdarray >= myproc()->trapframe->sp && walkaddr(myproc()->pagetable, fdarray) == 0) {
      // printf("debug: %p %d\n", p, n);
      // 如果这个虚拟地址p没有映射，那就建立映射
      char * pa = kalloc(); // alloc physial memory ，分配一页物理内存
      if(pa == 0){ // 申请失败
        myproc()->killed = 1;
        return -1;
      }
      else{
        memset(pa, 0, PGSIZE); //清空物理内存
        if(mappages(myproc()->pagetable, PGROUNDDOWN(fdarray), PGSIZE, (uint64)pa, PTE_W|PTE_R|PTE_U) != 0){ //建立从va下取整开始一页的映射
          kfree(pa); // 分配失败，释放物理内存
          myproc()->killed = 1;
          return -1;
        }
      }
  }
...
}

测试：

== Test running lazytests == 
$ make qemu-gdb
(4.5s) 
== Test   lazy: map == 
  lazy: map: OK 
== Test   lazy: unmap == 
  lazy: unmap: OK 
== Test usertests == 
$ make qemu-gdb
(78.4s) 
== Test   usertests: pgbug == 
  usertests: pgbug: OK 
...
...
== Test   usertests: forktest == 
  usertests: forktest: OK 
== Test time == 
time: OK 
Score: 119/119