Lab 5 Lazy allocation

Eliminate allocation from sbrk()

在sys_sbrk()中修改sbrk(n)系统调用的页面分配代码，把进程內存大小增加n个字节，返回值是新分配区域开始的部分。不应该分配内存，所以把growproc()删除。

  1. uint64
  2. sys_sbrk(void)
  3. {
  4.   int addr;
  5.   int n;
  7.   if(argint(0, &n) < 0)
  8.     return -1;
  9.   addr = myproc()->sz;
  10.   myproc()->sz = myproc()->sz + n;
  11.   //if(growproc(n) < 0)
  12.   //  return -1;
  13.   return addr;
  14. }

Lazy allocation

需要在usertrap()中查看r_cause()的返回值，这里我们需要做的是判断是否出现了page fault，所以当这个值等于13或15时，发生了page fault。

然后此时发生错误的虚拟地址可以用r_stval()来读取，然后我们打印一个错误信息。通过kalloc()来分配內存，如果失败，则杀死当前的进程。否则，分配一段空间，将出错的虚拟地址向下舍入到页面边界，使用mappages()函数来进行映射，如果失败了，kfree()掉kalloc()分配的內存，然后杀死进程。因为当前的uvmunmap()会导致系统panic崩溃，所以进行修改，PTE标志位V为0时。这个page不用做任何事情，所以可以直接跳到下一个page。

  1. // in usertrap()
  2.   else if(r_scause() == 13 || r_scause() == 15){
  3.     // page fault
  4.     uint64 va = r_stval();
  5.     printf("page fault %p\n", va);
  6.     uint64 ka = (uint64)kalloc();
  7.     if(ka == 0){
  8.       p->killed = 1;
  9.     }
  10.     else{
  11.       memset((void *)ka, 0, PGSIZE);
  12.       va = PGROUNDDOWN(va);
  13.       if(mappages(p->pagetable, va, PGSIZE, ka, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
  14.         kfree((void *)ka);
  15.         p->killed = 1;
  16.       }
  17.     }
  18.   }
// in uvmunmap()
  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    if((pte = walk(pagetable, a, 0)) == 0)
      panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0)
      continue;
    //  panic("uvmunmap: not mapped");
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }

Lazytests and Usertests

该实验需要处理sbrk()为负的情况，于是，当sbrk()为正时，我们沿用前面的策略，将进程內存大小增加n个字节；当sbrk()为负时，我们使用函数uvmdealloc()来取消内存的分配。

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;
  }
  else{
    myproc()->sz = uvmdealloc(myproc()->pagetable, addr, addr + n);
  }
  //if(growproc(n) < 0)
  //  return -1;
  return addr;
}

在usertrap()中，我们需要考虑进程在高于分配地址的情况和进程在栈底以下的情况，这种情况下不能顺利执行，需要杀死进程。

// in usertrap()
    else if(r_scause() == 13 || r_scause() == 15){
    // page fault
    uint64 va = r_stval();
    //printf("page fault %p\n", va);
    if((va >= p->sz) || (va < p->trapframe->sp)){
      p->killed = 1;
    } else {
      uint64 ka = (uint64)kalloc();
      if(ka == 0){
        p->killed = 1;
      }
      else{
        memset((void *)ka, 0, PGSIZE);
        va = PGROUNDDOWN(va);
        if(mappages(p->pagetable, va, PGSIZE, ka, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
          kfree((void *)ka);
          p->killed = 1;
        }
      }
    }
  }

在uvmdealloc()中，通过调用uvmunmap()，使用walk来查找对应的PTE。实际上，walk()函数中只对level为2和1时进行循环执行，如果level为0，仍然有可能出现虚拟地址对应的PTE不存在的情况，所以需要继续检查PTE_V标志位，由此来确定是否虚拟地址无效，所以这里需要两个continue。

// in uvmunmap()
  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    if((pte = walk(pagetable, a, 0)) == 0)
      continue;
    //  panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0)
      continue;
    //  panic("uvmunmap: not mapped");
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }

同理，在uvmcopy()中也是如此。

// in uvmcopy
    for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0)
      continue;
    //  panic("uvmcopy: pte should exist");
    if((*pte & PTE_V) == 0)
      continue;
    //  panic("uvmcopy: page not present");
    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;
    }
  }

对于系统调用read或write的情况，发生了trap，此时的r_scause()为8，不进入r_scause()为13或15的page fault判断，但此时仍需要处理该情况。r_scause()为8时会在syscall()后直接返回用户空间，所以在处理过程中是在内核态除法page fault的，而read和write会在内核中调用copyin()和copyout()来进行用户态和内核态页表的拷贝，所以可以在这两个函数中添加对page fault的处理机制。

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;
  struct proc *p = myproc();

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0){
      if((va0 >= p->sz) || (va0 < p->trapframe->sp)){
        return -1;
      }
      else{
        pa0 = (uint64)kalloc();
        if(pa0 == 0){
          p->killed = 1;
        }
        else{
          memset((void *)pa0, 0, PGSIZE);
          va0 = PGROUNDDOWN(va0);
          if(mappages(p->pagetable, va0, PGSIZE, pa0, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
            kfree((void *)pa0);
            p->killed = 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;
}

int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  uint64 n, va0, pa0;
  struct proc *p = myproc();

  while(len > 0){
    va0 = PGROUNDDOWN(srcva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0){
      if((va0 >= p->sz) || (va0 < p->trapframe->sp)){
        return -1;
      }
      else{
        pa0 = (uint64)kalloc();
        if(pa0 == 0){
          p->killed = 1;
        }
        else{
          memset((void *)pa0, 0, PGSIZE);
          va0 = PGROUNDDOWN(va0);
          if(mappages(p->pagetable, va0, PGSIZE, pa0, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
            kfree((void *)pa0);
            p->killed = 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;
}