本文记录了 Lab: xv6 lazy page allocation 的实验过程

Lab: xv6 lazy page allocation

在开始实验之前

阅读 xv6 book 的第四章，尤其是 4.6 节
相关代码：kernel/trap.c，kernel/vm.c，kernel/sysproc.c

1
2
3

git fetch
git checkout lazy
make clean

Eliminate allocation from sbrk() (easy)

Make sure you understand why this page fault occurs.

在内核启动，加载 sh 后；初始的 p->sz 为 16384 bytes，即 0x400；如果将 growproc() 去掉，那么如果进程需要更多的内存空间时，由于没有给它分配物理空间，因此当访问 0x0000000000004008 时就会产生缺页中断。所以 stval 寄存器就回保存这个值。输入 echo hi 后，查看 p-> sz 变为了 81920（0x14000），说明 OS 给它增加了 16 个物理页。

实验代码

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)

按照提示完成即可

实验步骤

在 kernel/defs.h 中添加

1 2	// vm.c uint64 lazyalloc(struct proc *p, uint64 va);

修改 kernle/trap.c 的 usertrap 代码，使得它可以处理缺页中断

void
usertrap(void)
{
  // ...
  } else if((which_dev = devintr()) != 0){
    // ok
  } else if(r_scause() == 13 || r_scause() == 15){
    // respond to a page fault from user space
    uint64 va = r_stval();
    if(lazyalloc(p, PGROUNDDOWN(va)) == 0){
      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;
  }
  // ...
}

在 kernel/vm.c 中修改 uvmunmap 函数，使得它在缺页时内核不会 panic；实现 lazyalloc 函数（参考 uvmalloc 函数）

#include "spinlock.h"
#include "proc.h"
// ...
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  // ...
  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;
  }
}
// ...
uint64
lazyalloc(struct proc *p, uint64 va)
{
  char *mem = kalloc();
  if(mem == 0){ // no free physical page to allocate, kill the process
    uvmdealloc(p->pagetable, va, va + PGSIZE);
    return 0;
  }
  memset(mem, 0, PGSIZE);
  if(mappages(p->pagetable, va, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
    kfree(mem);
    uvmdealloc(p->pagetable, va, va + PGSIZE);
    return 0;
  }
  return (uint64)mem;
}

测试

1 2	make qemu echo hi

Lazytests and Usertests (moderate)

完善 Lazy memory allocator，使得可以通过 lazytests and usertests

在 sbrk() 中增加处理 n 为负数的情况，使用 uvmdealloc 函数减少进程的内存空间
如果发生缺页中断的虚拟地址高于 p->sz，则结束这个进程
修改 fork() 调用的 uvmcopy，当页表项不存在或者页无效时，不必发出 panic
处理当系统调用（read/write）访问了一个有效的地址，但这个地址的内存还没有被分配的情况。此时由于在内核中执行，不会进入 usertrap 处理这个 fault
当处理缺页中断时，如果 kalloc 没有剩余的内存可以分配时，结束当前进程
处理访问低于用户栈地址的无效页错误，用户栈地址在 p->trapframe->sp

实验步骤

修改 sbrk()

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

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  myproc()->sz += n;
  if(n < 0){ // decrease process's memory
    uvmdealloc(myproc()->pagetable, addr, myproc()->sz);
  }
  return addr;
}

在 lazyalloc 函数的开头处增加判断 va 是否有效的情况

uint64
lazyalloc(struct proc *p, uint64 va)
{
  // 1. page-faults on a virtual memory address higher than any allocated, kill this process
  // 2. faults on the invalid page below the user stack, kill this process
  if(va >= p->sz || va < p->trapframe->sp){ 
    return 0;
  }
  // ...
}

由于 Lazy Allocate 的特点，去掉 vm.c 中的因为缺页而导致内核 panic 的语句

int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  // ...
  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0)
      continue; // if pte don't exist, no need panic
      // panic("uvmcopy: pte should exist");
    if((*pte & PTE_V) == 0)
      continue; // if page invalid, no need panic
      // panic("uvmcopy: page not present");
    // ...
  }
}

最后解决在内核中执行系统调用时访问了一个有效地址，但是还未给这个地址分配内存空间的情况。由于 vm.c 中的 walkaddr 函数的功能是在用户页表中查找虚拟地址 va，返回对应的物理地址；因此我们需要修改这部分代码。

uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  uint64 pa;

  if(va >= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  if(pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0){
    if((pa = lazyalloc(myproc(), PGROUNDDOWN(va))) == 0) return 0;
    return pa;
  }
  pa = PTE2PA(*pte);
  return pa;
}

测试

make qemu
echo hi
lazytests
usertests

1	make grade

Diff

diff --git a/kernel/defs.h b/kernel/defs.h
index 4b9bbc0..569839c 100644
--- a/kernel/defs.h
+++ b/kernel/defs.h
@@ -171,6 +171,7 @@ uint64          walkaddr(pagetable_t, uint64);
 int             copyout(pagetable_t, uint64, char *, uint64);
 int             copyin(pagetable_t, char *, uint64, uint64);
 int             copyinstr(pagetable_t, char *, uint64, uint64);
+uint64          lazyalloc(struct proc *p, uint64 va);
 
 // plic.c
 void            plicinit(void);
diff --git a/kernel/sysproc.c b/kernel/sysproc.c
index e8bcda9..51abbca 100644
--- a/kernel/sysproc.c
+++ b/kernel/sysproc.c
@@ -47,8 +47,10 @@ sys_sbrk(void)
   if(argint(0, &n) < 0)
     return -1;
   addr = myproc()->sz;
-  if(growproc(n) < 0)
-    return -1;
+  myproc()->sz += n;
+  if(n < 0){ // decrease process's memory
+    uvmdealloc(myproc()->pagetable, addr, myproc()->sz);
+  }
   return addr;
 }
 
diff --git a/kernel/trap.c b/kernel/trap.c
index a63249e..4487ce5 100644
--- a/kernel/trap.c
+++ b/kernel/trap.c
@@ -67,6 +67,11 @@ usertrap(void)
     syscall();
   } else if((which_dev = devintr()) != 0){
     // ok
+  } else if(r_scause() == 13 || r_scause() == 15){  // respond to a page fault from user space
+    uint64 va = r_stval();
+    if(lazyalloc(p, PGROUNDDOWN(va)) == 0){
+      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());
diff --git a/kernel/vm.c b/kernel/vm.c
index bccb405..87d0718 100644
--- a/kernel/vm.c
+++ b/kernel/vm.c
@@ -5,6 +5,8 @@
 #include "riscv.h"
 #include "defs.h"
 #include "fs.h"
+#include "spinlock.h"
+#include "proc.h"
 
 /*
  * the kernel's page table.
@@ -101,12 +103,10 @@ walkaddr(pagetable_t pagetable, uint64 va)
     return 0;
 
   pte = walk(pagetable, va, 0);
-  if(pte == 0)
-    return 0;
-  if((*pte & PTE_V) == 0)
-    return 0;
-  if((*pte & PTE_U) == 0)
-    return 0;
+  if(pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0){
+    if((pa = lazyalloc(myproc(), PGROUNDDOWN(va))) == 0) return 0;
+    return pa;
+  }
   pa = PTE2PA(*pte);
   return pa;
 }
@@ -181,9 +181,9 @@ uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
 
   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){
@@ -315,9 +315,9 @@ uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
 
   for(i = 0; i < sz; i += PGSIZE){
     if((pte = walk(old, i, 0)) == 0)
-      panic("uvmcopy: pte should exist");
+      continue; // if pte don't exist, no need panic
     if((*pte & PTE_V) == 0)
-      panic("uvmcopy: page not present");
+      continue; // if page invalid, no need panic
     pa = PTE2PA(*pte);
     flags = PTE_FLAGS(*pte);
     if((mem = kalloc()) == 0)
@@ -440,3 +440,24 @@ copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
     return -1;
   }
 }
+uint64
+lazyalloc(struct proc *p, uint64 va)
+{
+  // 1. page-faults on a virtual memory address higher than any allocated, kill this process
+  // 2. faults on the invalid page below the user stack, kill this process
+  if(va >= p->sz || va < p->trapframe->sp){
+    return 0;
+  }
+  char *mem = kalloc();
+  if(mem == 0){ // no free physical page to allocate, kill the process
+    uvmdealloc(p->pagetable, va, va + PGSIZE);
+    return 0;
+  }
+  memset(mem, 0, PGSIZE);
+  if(mappages(p->pagetable, va, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
+    kfree(mem);
+    uvmdealloc(p->pagetable, va, va + PGSIZE);
+    return 0;
+  }
+  return (uint64)mem;
+}

Lab xv6 lazy page allocation

文章目录

Lab: xv6 lazy page allocation

Eliminate allocation from sbrk() (easy)

实验代码

Lazy allocation (moderate)

实验步骤

测试

Lazytests and Usertests (moderate)

实验步骤

测试

Diff