# MIT6.s081-2020 Lab5 Lazy page allocation

lab 5 文档 (opens new window)

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

# 准备

git fetch
git checkout lazy
make clean
1
2
3

# Eliminate allocation from sbrk()

引言

本实验你的任务是从 sbrk(n) 系统调用实现中删除页面分配，这是 sysproc.c 中的函数 sys_sbrk()。sbrk(n) 系统调用将进程的内存大小增加 n 字节，然后返回新分配区域的开始（即旧大小）。您的新 sbrk(n) 应该只是将进程的大小 (myproc()->sz) 增加 n 并返回旧大小。它不应该分配内存——所以你应该删除对 growproc() 的调用（但你仍然需要增加进程的大小！）。

实现

本节的核心在于修改 sys_sbrk() 使得其只增加/减少进程地址空间大小，而不真正地分配页面。

kernel/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;
  p->sz += n;
  return addr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

结果

启动 xv6，然后键入echo hi到shell中，可获得如下内容：

init: starting sh
$ echo hi
usertrap(): unexpected scause 0x000000000000000f pid=3
            sepc=0x0000000000001258 stval=0x0000000000004008
va=0x0000000000004000 pte=0x0000000000000000
panic: uvmunmap: not mapped
1
2
3
4
5
6

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

# Lazy allocation + Lazytests and Usertests

引言

修改trap.c中的代码，通过将新分配的物理内存页面映射到故障地址，然后返回用户空间让进程继续执行，来响应来自用户空间的页面故障。您应该在之前添加您的代码printf产生“usertrap(): ...”消息的调用。

修改您需要的任何其他 xv6 内核代码以获得echo hi去工作。

实现

这里建议两个一起做了，免得回头还要修改

本实验中，你的目标是修改trap.c和其他地方的代码，使得在你的代码能够在缺页时分配一块新的内存并建立映射。根据所给的提示，按照HINT一步步做下去即可。

HINT1：通过查看 usertrap() 中的 r_scause() 是 13 还是 15 来检查错误是否是页面错误。r_stval()返回 RISC-Vstval寄存器，其中包含导致页面错误的虚拟地址。

HINT2：从 vm.c 中的 uvmalloc() 参考代码，这是 sbrk() 调用的（通过 growproc()）。您需要调用 kalloc() 和 mappages()。使用 PGROUNDDOWN(va) 将错误的虚拟地址向下舍入到页面边界。正确处理内存不足：如果 kalloc() 在页面错误处理程序中失败，则终止当前进程。处理用户堆栈下方无效页面上的错误。

kernel/trap.c

void
usertrap(void)
{
//...
else if((which_dev = devintr()) != 0){
    // ok
  }else if(r_scause() == 13 || r_scause() == 15) {
    uint64 va = r_stval();
    uint64 pa = (uint64)kalloc();
    if (pa == 0) {
      p->killed = 1;
    } else if (va >= p->sz || va <= PGROUNDDOWN(p->trapframe->sp)) {
      kfree((void*)pa);
      p->killed = 1;
    } else {
      va = PGROUNDDOWN(va);
      memset((void*)pa, 0, PGSIZE);
      if (mappages(p->pagetable, va, PGSIZE, pa, PTE_W| PTE_X | PTE_U | PTE_R) != 0) {
        kfree((void*)pa);
        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;
  }
//...
}
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

HINT3：uvmunmap() 会painc；如果某些页面未映射，请修改uvmunmap()以不painc。

kernel/vm.c

void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
//...
    if((pte = walk(pagetable, a, 0)) == 0)
      continue;
      //panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0)
      //panic("uvmunmap: not mapped");
      continue;
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
//...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

HINT4：处理负值的 sbrk() 参数，即用户空间地址减少的情况，如果一个进程在高于任何使用 sbrk() 分配的虚拟内存地址上发生页面错误，则终止该进程。

kernel/sysproc.c

#include "spinlock.h"
#include "proc.h"
uint64
sys_sbrk(void)
{
  int addr;
  int n;
  if(argint(0, &n) < 0)
    return -1;
  struct proc *p = myproc();
  addr = p->sz;
  uint64 newaddr = addr + n;
  if(newaddr >= MAXVA || newaddr <= 0)
    return addr;
  //if(growproc(n) < 0)
    //return -1;
  if(n < 0) {
    if(p->sz + n < 0) return -1;
    else uvmdealloc(p->pagetable, p->sz, p->sz + n);
  }
  p->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
25
26

HINT5：正确处理 fork() 中的父子内存副本。

在 fork() 中我们可以看到使用 uvmcopy() 这个函数来复制父进程的页表，而在复制父进程页表的过程中自然会发现未映射的情况从而报错，我们同uvmunmap() 中修改即可

int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
//...
    if((pte = walk(old, i, 0)) == 0)
      //panic("uvmcopy: pte should exist");
      continue;
    if((*pte & PTE_V) == 0)
      //panic("uvmcopy: page not present");
      continue;
//...
}
1
2
3
4
5
6
7
8
9
10
11
12

HINT6：处理进程将有效地址从 sbrk() 传递给系统调用（例如read或write），但尚未分配该地址的内存的情况。

根据sys_read和sys_write的调用链可以发现：

sys_read()->readi()->either_copyout()->copyout()->walkaddr()
1

因此，我们可以参考usertrap的内容编写：

kernel/vm.c

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)
  //  return 0;
  //if((*pte & PTE_V) == 0)
  //  return 0;
  if (pte == 0 || (*pte & PTE_V) == 0) {
    //pa = lazyalloc(va);
    struct proc *p = myproc();
    if(va >= p->sz || va < PGROUNDUP(p->trapframe->sp)) return 0;
    pa = (uint64)kalloc();
    if (pa == 0) return 0;
    if (mappages(p->pagetable, va, PGSIZE, pa, PTE_W|PTE_R|PTE_U|PTE_X) != 0) {
      kfree((void*)pa);
      return 0;
    }
    return pa;
  }
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  return pa;
}
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

结果

启动 xv6，然后输入lazytests到shell中，可获得如下内容：

image-lab5-1.png

在shell中运行usertests代码，可以得到如下内容：

image-lab5-2.png

# 总结

该部分实验的内容不算难，并且在教学视频中已经明确指出。