Eliminate allocation from sbrk()实验

没有实验，只谈现象

这是Fans教授在课上提到的现象，在基础理论一文的Lazy Allocation一节我也具体剖析过，看完不难理解：只增加了虚拟内存，uvmunmap释放了虚拟内存指向的不存在的物理内存。

Lazy allocation实验

实验目的

实现一个简单的Lazy allocation，要求进程使用sbrk进行内存分配时不要直接满足，引入懒分配策略等到进程使用到了再申请物理内存，如果设计是成功的，那么shell能够正常运行echo hi命令。

具体实现

这是一个简单的Lazy allocation实现，在基础理论已经实现并且做了剖析讨论，看过基础理论或者课程的可以直接跳到第三个实验。具体步骤是在kernel/sysproc.c中sbrk函数增加虚拟内存，取消物理内存分配 

1
2
3
 myproc()->sz=myproc()->sz+n;//new
//if(growproc(n) < 0)
//  return -1;
这个改动会得到page fault，因此需要在kernel/trap.c加以处理： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
else if(r_scause()==15||r_scause()==13){   //pagefault或者load page fault
    uint64 va=r_stval();
    printf("page fault stval=%p\n",va);
    uint64 pa=(uint64)kalloc();  //触发page fault才分配物理内存
    if(pa==0){
      p->killed=1;
    }
    else{   
      memset((void*)pa,0,PGSIZE);
        if(mappages(p->pagetable,PGROUNDDOWN(va),PGSIZE,pa,PTE_U|PTE_R|PTE_W)!=0){        
          kfree((void*)pa);
           p->killed=1;
      }
    }
  }
因为按需分配物理内存，不能保证虚拟内存一定有存在映射关系的物理内存，取消映射时不能直接panic：kernel/vm.c的uvmunmap函数： 
1
2
3
if(PTE_FLAGS(*pte) == PTE_V)
    //panic("uvmunmap: not mapped");
    continue;
完整Commit参考：Lazy test2 Done

Lazytests and Usertests实验

实验目的

本节主要在第二节的基础上，解决以下问题: 1. 处理sbrk()参数为负的情况。
2. 如果某个进程在高于sbrk()分配的任何虚拟内存地址上出现页错误，则终止该进程。
3. 在fork()中正确处理父到子内存拷贝。
4. 处理这种情形：进程从sbrk()向系统调用（如read或write）传递有效地址，但尚未分配该地址的内存。
5. 处理用户栈下面的无效页面上发生的错误。

具体实现

针对五个问题逐步实现：

  1. 正数增加虚拟内存，负数仍然和原来一致即可，即调用growproc函数进行解除映射；kernel/sysproc.c 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    uint64
    sys_sbrk(void)
    {
      int addr;
      int n;
      if(argint(0, &n) < 0)
        return -1;
      addr = myproc()->sz;
      if(n<0){  //缩减内存
        if(myproc()->sz+n<0||growproc(n)<0) //缩减完不能是负数
        return -1;
      }
      else
        myproc()->sz=myproc()->sz+n;//虚拟内存增加
        //if(growproc(n) < 0)
        //  return -1;
      return addr;
    }

  2. 将第二个和第五个问题一起讨论：有两种页面错误不应该是页懒分配引起的，页懒分配处理的page fault发生的位置一定是用户进程的进程空间，也即内核分配的虚拟地址空间，包括代码段、数据段、BSS段、堆栈段、trapframe、trampoline等。 用户进程空间 注意这个图是整个内存的用户空间分布，一个段可能被多个用户进程使用。

    因此一个进程中，页懒分配的虚拟地址的下边界应该guard page以上，具体而言应该是栈顶指针sp以上。上边界是MAXVA，但因为进程维护了sz大小字段，因此每个进程不超过p->sz；因此在kernel/trap.c增加判断： 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    else if(r_scause()==15||r_scause()==13){
      uint64 va=r_stval();
      printf("page fault stval=%p\n",va);
      if(va>p->sz||va<PGROUNDDOWN(p->trapframe->sp)){  //新增：for address higher than lazy allocation or lower than stack
        //printf("Not Suit pagefault\n"); 
        exit(-1);
      }
      //printf("page fault stval=%p\n",va);
      uint64 pa=(uint64)kalloc();
      if(pa==0){
        p->killed=1;
      }
      else{
        memset((void*)pa,0,PGSIZE);
        if(mappages(p->pagetable,PGROUNDDOWN(va),PGSIZE,pa,PTE_U|PTE_R|PTE_W)!=0){        
          kfree((void*)pa);
          p->killed=1;
        }
      }
    }

  3. 对于第三个fork的拷贝问题，实际上就是kernel/sysproc.c的fork函数中，uvmcopy函数会尝试调用walk去解析页表，而在页懒分配中出现页表项无效、不存在均是合理的，因此不应该报panic，uvmcopy修改为： 

    1
    2
    3
    4
    5
    6
    if((pte = walk(old, i, 0)) == 0)
      //panic("uvmcopy: pte should exist");
      continue;
    if((*pte & PTE_V) == 0)
      continue;
      //panic("uvmcopy: page not present");
    对应的，uvmunmap也修改：在实验2只注释了if((*pte & PTE_V) == 0)的情况，为了通过test3在这里调用也是需要continue的。 
    1
    2
    3
    if((pte = walk(pagetable, a, 0)) == 0)
        //panic("uvmunmap: walk");
        continue;

  4. 最后是一些系统调用的影响，例如write和read。write和read作为系统调用，和其他系统调用不同的是，其他系统调用没有从用户端向内核传递参数，回想我们剖析的那个sysinfo调用，用户态调用函数，向内核通过寄存器a7传递了系统调用号，内核陷入找到对应的系统调用函数就开始处理了，最后系统将内核获取到的sysinfo参数通过copyout传递给用户空间；write和read多了一步，它需要告诉内核需要从哪里读什么数据，或者写什么数据到哪里，因此还会涉及copyin。用户传递参数给内核，但是内核并不能通过页表找到它的物理内存（因为用户态没有分配），因此内核要完成这样一部分工作：遇到没有分配内存、分配标志位有效位PTE_V为0的情况需要对其分配内存。

    因此可以知道，copyin、copyout中的页表索引也需要修改，它们都是通过函数workaddr将虚拟地址va转换成物理地址，但是·解析到pte == 0以及(*pte & PTE_V) == 0都是直接return了，因此这里需要修改成分配内存： 

    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
    uint64
    walkaddr(pagetable_t pagetable, uint64 va)
    {
      pte_t *pte;
      uint64 pa;

      if(va >= MAXVA)
        return 0;

      if(pte == 0){
        if(lazy_alloc(va,pagetable)<0){
          return 0;
        } 
      }
      //return 0;

      if((*pte & PTE_V) == 0){
        if(lazy_alloc(va,pagetable)<0){
          return 0;
        }  
      }
      //return 0;

      if((*pte & PTE_U) == 0)
        return 0;
      pa = PTE2PA(*pte);
      return pa+off;
    }
    其中lazy_alloc函数实现，不要忘记在kernel/defs.h添加声明: 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int lazy_alloc(uint64 va,pagetable_t pagetable){
      if(va>PGROUNDDOWN(myproc()->trapframe->sp)&&va<myproc()->sz){
        uint64 pa = (uint64)kalloc();
        if(pa==0)
          return -1;
        memset((void*)pa,0,PGSIZE);
        if(mappages(pagetable,PGROUNDDOWN(va),PGSIZE,pa,PTE_U|PTE_R|PTE_W)<0){
          kfree((void*)pa);
          return -1;
        }
        return 0;
      }                                                                      
      return -1;
    }

至此，整个lab也做完了，运行： 

1
2
lazytests
usertests
如果能正常运行就OK啦，咋这里的usertests故障率低了那么多，莫非是上节实验没做好~

评估结果

完整commit请参考:Lazy test3 Done