genesis的空间站
0%

Lab Lazy

发表于
本文字数： 4.1k 阅读时长 ≈ 4 分钟

Lab Lazy

前置知识

一、原理

  1. 因为绝大多数情况，程序并不会全部使用它一开始申请的内存，所以eager allocation常常会出现浪费，为了避免这种情况，可以使用lazy allocation。
  2. 在lazy allocation中，每次程序申请page的时候，并不会直接给它分配page，而是表面上给它在列表中分配相应虚拟page，但并不给它分配实际物理page。这样，当程序使用这个page时，一定会发生找不到物理page的page fault。此时便可以分配page了。

task: Eliminate allocation from sbrk

  1. 这是一个很简单的task，只需要实现sbrk中只增加sz不分配page的操作就好了。
  2. 因为后续task会增加更多的限制，不妨在这里就先考虑周全。
  3. 首先，n可正可负，当n为负数时，需要释放page
  4. 其次，sz在变化n后，不能超过堆顶MAXVA，也不能把不属于该进程的负数区释放掉
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    //sysproc.c
    uint64
    sys_sbrk(void)
    {
      int addr;
      int n;

      if(argint(0, &n) < 0)
        return -1;
      struct proc *p = myproc();
      addr = p->sz;
    //  if(growproc(n) < 0)
    //    return -1;
      if (p->sz + n < 0 || p->sz + n > MAXVA)//是否在堆中
        return -1;
      if (n < 0) {
        uvmdealloc(p->pagetable, p->sz, p->sz + n);
      }
      p->sz += n;
      return addr;
    }

task: Lazy allocation

  1. 在上一个task，我们只修改了sz，并没有真正分配物理页，因此首先需要在page fault跳转到的usertrap中分配page。注意，从xv6book中我们可以知道，只有load和store page fault的出现才意味着lazy需要allocation
  2. 在这个lab中，无论是内存耗尽还是映射失败，都需要立刻kill进程
    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
    //trap.c/ usertrap()
    ...
     else if((which_dev = devintr()) != 0){
        // ok
      } else if ((r_scause() == 13) || (r_scause() == 15)) {//load 13; store 15
        // 返回出错的虚拟地址
        uint64 va = r_stval();
        // 不能添加printf, 否则答案不正确
        if ((va >= p->sz) || (va < p->trapframe->sp)) {//越过了申请页表的指针或不在堆的范围内
          p->killed = 1;
        } else {
          uint64 ka = (uint64) kalloc();
          if (ka == 0) {//物理page申请失败
            p->killed = 1;
          } else {
            memset((void*)ka, 0, PGSIZE);
            va = PGROUNDDOWN(va);//page取整
            if(mappages(p->pagetable, va, PGSIZE, ka, PTE_W|PTE_R|PTE_U) != 0) {//映射失败
              kfree((void*)ka);
              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;
      }
    ...
  3. 这时候，echo hi 会报panic，这是因为在没有lazy的xv6中，取消映射一个没有分配物理地址的page或者一个没有映射的页表显然是不合法的，但是加上lazy后，这些情况便会出现在lazy中，(比如，你增加了sz却没有分配page，最后释放的这些假page一定没有物理地址)，因此我们需要取消这些panic生成。注意，头文件该加就加，小心顺序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //vm.c/ 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;//just ok
    //      panic("uvmunmap: not mapped");
    ...
  4. 关于为何需要continue walk出错后还需要continue页表无效，可以看到walk函数的实现，for循环中只循环前两层页表，因此当前两层页表索引出现无效时会返回0，但是它不会检查最后一层指向的PTE是否无效而是会直接返回，因此需要做两层检查。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //walk
    pte_t *
    walk(pagetable_t pagetable, uint64 va, int alloc)
    {
      if(va >= MAXVA)
        panic("walk");

      for(int level = 2; level > 0; level--) {//2 level
        pte_t *pte = &pagetable[PX(level, va)];
        if(*pte & PTE_V) {
          pagetable = (pagetable_t)PTE2PA(*pte);
        } else {
          if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
            return 0;
          memset(pagetable, 0, PGSIZE);
          *pte = PA2PTE(pagetable) | PTE_V;
        }
      }
      return &pagetable[PX(0, va)];
    }

Task: Lazytests and Usertests

  1. 当我们调用fork函数时，在将parent页表拷贝给child时，当遇到和uvmunmap中的“假page”的时候，不需要拷贝，也不能触发panic，直接跳过就好。因为你会发现如果继续执行的话，uvmcopy函数会为child的”假page”分配物理页，这显然是不对的。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    //vm.c/ 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)//this is why we continue
          goto err;
        memmove(mem, (char*)pa, PGSIZE);
        if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
          kfree(mem);
          goto err;
        }
      }
      return 0;
  2. 最后，在调用syscall read, write时，会进入到kernel中，此时不能直接使用user虚拟地址，需要通过walkaddr函数来模拟一个MMU，此时如果找到一个没有被分配物理页的page，那么就给它分配一个。注意，按理说，sys_read()->readi()->either_copyout()->copyout()->walkaddr(),因此可以修改walkaddr，也可以修改copyout和copyin，我尝试修改walkaddr，但不知为何usertests不过，后来只能退而求其次。(难道是没有及时kill进程吗，等有空了试试)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    //vm.c/ copyin(),copyout()
      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_R|PTE_U) != 0) {
                kfree((void *)pa0);
                p->killed = 1;
              }
            }
          }
        }