O/S使用页表硬件可以使用的许多巧妙技巧之一是延迟分配用户空间堆内存。 Xv6应用程序使用sbrk()系统调用向内核请求堆内存。 在我们给出的内核中，sbrk()分配物理内存并将其映射到进程的虚拟地址空间。 内核为大型请求分配和映射内存可能需要很长时间。 例如，考虑一个千兆字节由262,144个4096字节的页组成; 这是一个巨大的分配数量，即使每一个都是便宜的。 此外，一些程序分配的内存比它们实际使用的内存要多(例如，实现稀疏数组)，或者在使用之前分配内存。 为了让sbrk()在这些情况下更快地完成，复杂的内核会延迟分配用户内存。 也就是说，sbrk()不分配物理内存，只是记住分配了哪些用户地址，并在用户页表中将这些地址标记为无效。 当进程第一次尝试使用任何给定的惰性分配内存页时，CPU会生成一个页错误，内核会通过分配物理内存、置零和映射来处理这个错误。 在本实验中，您将向xv6添加这个惰性分配特性。

在你开始编码之前，阅读xv6书的第4章(特别是4.6章)，以及你可能要修改的相关文件:
kernel/trap.c
kernel/vm.c
kernel/sysproc.c

Eliminate allocation from sbrk() (easy)

要求：

您的第一个任务是从sbrk(n)系统调用实现中删除页面分配，该实现是sysproc.c中的sys_sbrk()函数。 sbrk(n)系统调用将进程的内存大小增加n个字节，然后返回新分配的区域的起始值(即旧的大小)。 新的sbrk(n)应该只增加进程的大小(myproc()->sz) n，并返回原来的大小。 它不应该分配内存——因此您应该删除对growproc()的调用(但您仍然需要增加进程的大小!)

试着猜猜这个修改的结果会是什么:什么会被打破?

进行此修改，启动xv6，并向shell输入echo hi。 你应该看到这样的东西:
init: starting sh
$ echo hi
usertrap(): unexpected scause 0x000000000000000f pid=3
sepc=0x0000000000001258 stval=0x0000000000004008
va=0x0000000000004000 pte=0x0000000000000000
panic: uvmunmap: not mapped

"usertrap():…"消息来自trap.c中的用户trap处理程序; 它捕获了一个不知道如何处理的异常。 请确保您理解为什么发生此页面错误。 “stval = 0 x0 . . 04008”表示导致页面错误的虚拟地址为0x4008。

代码：

/*
sysproc.c

结合proc.c中的growproc()函数，修改sys_proc()
*/
uint64
sys_sbrk(void)
{
  int n;

  if(argint(0, &n) < 0)
    return -1;  
  struct proc* p = myproc();
  uint64 addr = p->sz;
  uint64 newSize = addr + n;
  if(newSize >= MAXVA)
    return addr;
  if(n < 0 ){//处理负参数
    if(newSize > addr){
      newSize = 0;
      uvmunmap(p->pagetable, 0, PGROUNDUP(addr)/PGSIZE, 1);
    }
    else{
      uvmunmap(p->pagetable, PGROUNDUP(newSize), (PGROUNDUP(addr)-PGROUNDUP(newSize))/PGSIZE, 1);
    }
  }
  p->sz = newSize;
  //if(growproc(n)<0)
  //  return -1;
  return addr;
}

结果：

Lazy allocation (moderate)

要求：

修改trap.c中的代码，在错误地址上映射新分配的物理内存页，然后返回到用户空间，让进程继续执行，从而从用户空间响应页面错误。 您应该在产生“usertrap():…”消息的printf调用之前添加代码。 修改任何其他xv6内核代码，以使echo hi工作。

提示：

通过查看usertrap()中的r_cause()是13或15，可以检查一个错误是否是页面错误。
r_stval()返回RISC-V stval寄存器，其中包含导致页面错误的虚拟地址。
从vm.c中的uvmalloc()中窃取代码，这是sbrk()调用的(通过growproc())。 你需要调用kalloc()和mapages()。
使用PGROUNDDOWN(va)将故障虚拟地址舍入到页面边界。
uvmunmap()将panic; 修改它，使其在某些页面没有映射时不会出现panic。
如果内核崩溃，在kernel/kernel.asm中查找sepc
使用pgtbl lab中的vmprint函数打印页表的内容。
如果你看到错误“incomplete type proc”，包括“spinlock.h”，然后是“proc.h”。
如果一切顺利，您的lazy allocation代码应该会导致echo hi工作。 您应该至少得到一个页面错误(因此是惰性分配)，或者可能得到两个。

代码：

/*
trap.c

参考vm.c中的uvmalloc()，修改usertrap()
*/
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
  } else if(r_scause() == 13 || r_scause() == 15){//检查一个错误是否是页面错误
    uint64 va = r_stval();//r_stval()返回RISC-V stval寄存器，其中包含导致页面错误的虚拟地址
    if(p->sz <= va){//地址高于sbrk申请的地址
        p->killed = 1;
    } else if(va < p->trapframe->sp){//地址低于栈顶地址 无效页
        p->killed = 1;
    } else{
      va = PGROUNDDOWN(va);//使用PGROUNDDOWN(va)将故障虚拟地址舍入到页面边界
      char *mem = kalloc();//参考vm.c的uvmalloc()，调用kalloc()和mapages()。
      if(mem == 0){//如果kalloc()在页面错误处理程序中失败，终止当前进程
        p->killed = 1;
      } else{
        memset(mem, 0, PGSIZE);
        if(mappages(p->pagetable, va, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
            kfree(mem);
            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();
}

/*
vm.c

修改uvmunmap()，页表未映射时跳过
*/
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");
    if((*pte & PTE_V) == 0)
    continue;//panic("uvmunmap: not mapped"); 必须改成continue，否则可能进入do_free
    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 (moderate)

要求：

我们已经为您提供了lazytests，这是一个xv6用户程序，用于测试一些可能会给lazy allocation分配器带来压力的特定情况。 修改内核代码，以便所有的惰性测试和用户测试都能通过。

处理负的sbrk()参数。
如果进程在高于sbrk()分配的任何虚拟内存地址上发生页故障，则终止进程。
正确处理fork()中的父到子内存副本。
处理进程将有效地址从sbrk()传递给系统调用(例如read或write)，但尚未为该地址分配内存的情况。
正确处理内存不足:如果kalloc()在页面错误处理程序中失败，终止当前进程。
处理用户堆栈下面的无效页上的错误。
如果你的内核通过了lazytests和usertests，你的解决方案是可以接受的:

代码：

/*
处理负的sbrk()参数。  

见5.1修改的sysproc.c第55行后
*/

/*
如果进程在高于sbrk()分配的任何虚拟内存地址上发生页故障，则终止进程。 

见5.2修改的trap.c第74行后
*/ 

/*
正确处理内存不足:如果kalloc()在页面错误处理程序中失败，终止当前进程。  

见5.2修改的trap.c第81行后
*/

/*
处理用户堆栈下面的无效页上的错误。  

见5.2修改的trap.c第76行后
*/

/*
vm.c

正确处理fork()中的父到子内存copy。
修改uvmcopy(),页表不存在或未映射直接跳过
类似5.2中对vm.c中uvmunmap()的处理。
*/
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)
      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;
    }
  }
  return 0;

 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}

/*
vm.v

处理进程将有效地址从sbrk()传递给系统调用(例如read或write)，但尚未为该地址分配内存的情况。 
参考vm.c中uvmalloc() 
类似5.2中对vm.c中usertrap()的处理。
*/
#include "spinlock.h"//添加头文件，要按照顺序
#include "proc.h"

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(p->sz <= va0)
        return -1;
      uint64 mem = kalloc();
      if(mem == 0){
          return -1;
      }
      memset(mem, 0, PGSIZE);
      if(mappages(pagetable, va0, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
        kfree(mem);
        return -1;
      }
      pa0 = mem;
    }  
    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;
}

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(p->sz <= va0)
        return -1;
      uint64 mem = kalloc();
      if(mem == 0){
          return -1;
      }
      memset(mem, 0, PGSIZE);
      if(mappages(pagetable, va0, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
        kfree(mem);
        return -1;
      }
      pa0 = mem;
    }  
    n = PGSIZE - (dstva - va0);
    if(n > len)
      n = len;
    memmove((void *)(pa0 + (srcva - va0)), src, n);

    len -= n;
    src += n;
    dstva = va0 + PGSIZE;
  }
  return 0;
}

结果：