xv6 lazy page allocation

这个 lab 要实现页的按需分配。主要考虑的场景是应用程序通过 sbrk 系统调用向操作系统申请大量的堆内存，此时内核需要花费大量的时间来分配物理内存，将物理内存映射到虚拟内存，另外应用程序可能是一开始就申请很大一块内存，但是并不是一开始就使用所有的内存，例如创建一个稀疏矩阵。所以为了 sbrk 系统调用更快速的完成应用程序的需求，我们可以在分配内存时只记录申请的大小，但是不真正申请物理内存并映射，而是当应用程序访问到相应的虚拟地址触发缺页中断时才分配并映射物理内存。

Lazy allocation

这里要我们实现按需分配，即在发生缺页中断后分配并映射物理内存。

根据下面的提示实现：

通过 r_scause 的值来判断是否是缺页中断。
r_stval 保存发生缺页中断的虚拟地址。
参考 uvmalloc 分配物理地址并完成映射。
使用 PGROUNDDOWN(va) 取得对应 va 下界。
修改 uvmunmap 使其在某些页没有映射的情况下不会 panic。
处理 sbrk 参数为负数时的情况，即应用程序归还内存的情况。
当发生缺页中断的虚拟地址超过 sbrk 分配的界限时 kill 掉进程。
处理 fork 系统调用时子进程拷贝父进程的情况。
处理当进程使用 sbrk() 返回的有效地址作为系统调用参数时，但是该地址并未真正分配的情况。
处理内存不够的情况，直接 kill 进程。
处理在用户栈空间以下无效地址产生的中断。

首先我们看一下 sbrk 系统调用的实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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

  if(argint(0, &n) < 0) // 获取系统调用参数
    return -1;
  addr = myproc()->sz;
  if(n < 0) { // 参数为负数的情况直接归还内存
    if(growproc(n) < 0)
      return -1;
  } else { // 只将内存空间范围增加，并不实际分配和映射
    myproc()->sz += n;
  }
  return addr;
}

在看发生缺页中断时的处理：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


//trap.c: usertrap()

if(r_scause() == 13 || r_scause() == 15) { // 根据 r_scause 的值判断是不是缺页中断
  uint64 va = r_stval(); // 获取发生中断的虚拟地址
  if(va>= p->sz || va < p->trapframe->sp) { // 判断是不是合法的地址
    p->killed = 1;
  } else {
    uint64 a = PGROUNDDOWN(va);
    char* mem = kalloc(); // 分配物理页
    if(mem == 0){ // 判断是否内存不足
      p->killed = 1;
    } else {
      memset(mem, 0, PGSIZE);
      if(mappages(p->pagetable, a, 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;
}

按需分配就有并未分配映射的内存需要回收的情况，所以需要修改 uvmunmap：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
  if((pte = walk(pagetable, a, 0)) == 0) // 没有找到对应 pte，说明没有虚地址映射，继续处理下一页
    // 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){
    uint64 pa = PTE2PA(*pte);
    kfree((void*)pa);
  }
  *pte = 0;
}

fork 系统调用子进程拷贝父进程的地址空间，使用的是 uvmcopy ，所以需要修改 uvmcopy ，遇到地址没有映射的情况暂时不处理，等发生中断时处理。

 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
30
31


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)
      // panic("uvmcopy: pte should exist");
      continue;
    if((*pte & PTE_V) == 0)
      // panic("uvmcopy: page not present");
      continue;
    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;
}

关于系统调用的参数其实通过前面的实验我们知道是通过 copyin 和 copyout 这两个函数获取的，而 copyin 和 copyout 都调用的是 walkaddr 来查找虚拟地址对应的物理地址，所以我们只在这里分配本应在 sbrk 系统调用时分配的内存即可。

 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
30
31
32
33
34


uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  uint64 pa;
  struct proc *p = myproc();

  if(va>= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  if(pte == 0 || (*pte & PTE_V) == 0) { // 映射不存在
    if(va>= p->sz || va < p->trapframe->sp) { //判断是否越界
        return 0;
    } else {
      uint64 a = PGROUNDDOWN(va);
      char* mem = kalloc(); // 分配物理内存
      if(mem == 0){
        return 0;
      } else {
        memset(mem, 0, PGSIZE); 
        if(mappages(p->pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){ // 完成映射
          kfree(mem);
          return 0;
        }
        pte = walk(pagetable, va, 0);
      }
    }
  }
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  return pa;
}

这个实验其实给我们展示了使用虚拟地址的一个优点，就是可以对内存按需分配，使得内存分配的效率更高。

Contents

Lazy allocation