xv6-labs-2020.lab4.lazy page allocation

Posted on Edited on In Views:
惰性分配

lab4: lazy page allocation

1.作业链接

  • https://pdos.csail.mit.edu/6.828/2020/labs/cow.html

2. 实习内容

准备工作

子进程 + 阅读给定文档的 Chapter 03/04

P1: Eliminate allocation from sbrk()

  • 修改系统调用 sbrk()，让其只增加进程的大小 myproc()->sz，返回未增长前的的地址，不分配新的内存空间
  • 直接修改文件 kernel/sysproc.c 中的函数 sys_sbrk() 即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// kernel/sysproc.c:sys_sbrk()
uint64 sys_sbrk(void) {
    // 注意地址要写成 uint64, 原来的代码里面写的是 int
    // 导致最后会有 panic("walk")
    // 截断导致最终 p->sz 变成负数(f开头)
    uint64 addr;
    int n;
    if(argint(0, &n) < 0)
        return -1;
    addr = myproc()->sz;
    // if(growproc(n) < 0)
    //  return -1;
    myproc()->sz = addr + n;
    return addr;
}
  • 这样的修改势必会导致在读取地址的时候导致 page fault，因为没有分配内存，虚拟映射失败
1
echo hi
1
2
3
usertrap(): unexpected scause 0x000000000000000f pid=3
            sepc=0x00000000000012ac stval=0x0000000000004008
panic: uvmunmap: not mapped

P2: Lazy allocation

  • 响应上面的 page fault，从而能够让程序良好运行
  • 需要在 usertrap() 调用 printf() 之前加入一些代码进行 page fault 的判断
  • 可能需要修改一些其它地方的代码

(1) 一些提示

  • 可以通过 r_scause() 为 13 或者 15 来判断当前是否触发的是 pagefault
  • r_stval() 返回导致异常的虚拟地址
  • 仿照 vm.c 中的 uvmalloc() 代码进行分配内存
    • 原来 sbrk() 通过调用 growproc() 间接调用到 uvmalloc()
    • 需要调用 kalloc() 以及 mappages()
  • 使用 PGROUNDDOWN(va) 可以获取到当前虚拟页的最小地址
  • uvmunmap() 会调用 panic()，如果是因为没有映射造成的话，我们应该不让他调用
  • kernel/kernel.asm 中保存着汇编代码，如果发生错误可以查看这部分代码
  • 如果报错 incomplete type proc
    • include "spinlock.h" then "proc.h".

(2) 修改 usertrap()

  • 判断异常是否为 pagefault
  • 如果是则正确分配一页物理页
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
// kernel/trap.c:usertrap()
// ...
else if(scause == 0xf || scause == 0xd) {
    // Page Fault Code Start
    uint64 scause = r_scause();
    // 判断是否为 pagefault
    // 获取虚拟页位置
    uint64 vm_addr = r_stval();
    vm_addr = PGROUNDDOWN(vm_addr);
    pagetable_t pagetable = myproc()->pagetable;
    char *mem;
    // 为虚拟页分配一页物理页
    mem = kalloc();
    // 当分配不到物理页时的处理
    if(mem == 0) {
        p->killed = 1;
    }
    // 刷零
    memset(mem, 0, PGSIZE);
    if(mappages(pagetable, vm_addr, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
        kfree(mem);
        p->killed = 1;
    }
    // Page Fault Code End
}
// ...
  • 同时我们要把由于 pagefault 导致的 panic() 取消
    • 注释掉如下代码
1
2
3
// kernel/vm.c:uvmunmap()
if((*pte & PTE_V) == 0)
    panic("uvmunmap: not mapped");
  • 由于我们现在只是实现了 lazy 的分配，还需要解决这样一个问题，如果申请了一块内存，但是尚未分配映射，此时我们不需要进行 kfree() 操作
  • 整段代码修改如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// kernel/vm.c:uvmunmap()
// ...
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)
    // panic("uvmunmap: not mapped");
    if(PTE_FLAGS(*pte) == PTE_V)
        panic("uvmunmap: not a leaf");
    // 分配了而且映射了的内存才需要释放
    if(do_free && (*pte & PTE_V) != 0){
        uint64 pa = PTE2PA(*pte);
        kfree((void*)pa);
    }
    *pte = 0;
}
// ...
  • 此时运行 echo hi，能够正确的输出 hi

P3: Lazytests and Usertests

  • 处理一些细节问题
  • 实现 sbrk() 中参数为负的情况
  • 如果请求的虚拟地址，比当前进程通过 sbrk() 申请的最高地址要高的话，kill 掉
  • 内核态访问的的内存已申请，但是尚未分配映射
    • You can fix it by add code in walkaddr() in kernel/vm.c:104, as any r/w syscall will invoke walkaddr to get physical address.
  • 能够处理 fork() 中父子进程的内存复制
  • kalloc() 失败的时候，kill 掉当前进程
    • 已经实现
  • 解决栈溢出的问题，栈的大小只有一页，不能访问栈之外的空间

(1) sbrk() 参数为负

  • 直接调用 uvmunmap() 释放即可
  • 简单实现，我们可以直接调用 growproc() 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// kernel/sysproc.c:sys_sbrk()
uint64 sys_sbrk(void) {
    uint64 addr;
    int n;
    if(argint(0, &n) < 0)
        return -1;
    addr = myproc()->sz;
    // if(growproc(n) < 0)
    //  return -1;
    if(n < 0) {
        if(growproc(n) < 0)
            return -1;
    } else {
        myproc()->sz = addr + n;
    }
    return addr;
}

(2) 访问到未申请的空间

  • 判断访问的虚拟地址是否已经申请
1
2
3
4
5
// kernel/trap.c:usertrap()
if(vm_addr >= p->sz) {
    p->killed = 1;
    exit(-1);
}

(3) 栈溢出

  • 因为栈的大小只有一页，我们可以通过 myproc()->trapframe->sp 获取到当前栈所在的页
  • 然后使用 PGROUNDDOWN 以及 PGROUNDUP 获取到边界
1
2
3
4
5
6
7
// kernel/trap.c:usertrap()
// 用户栈溢出
uint64 ustack = p->trapframe->sp;
if(vm_addr < PGROUNDDOWN(ustack)) {
    p->killed = 1;
    exit(-1);
}

(4) fork 问题

  • 调用 fork 的时候，如果父进程存在一些申请了但是尚未分配映射的内存，子进程就不需要 copy 了
  • 在进行 uvmcopy() 的时候进行修改，如果 pte 不存在，则不复制，而不是报错
  • 修改如下
1
2
3
4
5
6
if((pte = walk(old, i, 0)) == 0)
    continue;
// panic("uvmcopy: pte should exist");
if((*pte & PTE_V) == 0)
    continue;
// panic("uvmcopy: page not present");

(5) 内核态的内存操作

  • 如果内核态需要操作一个申请了但是尚未分配映射的空间时，需要进行处理
  • 例如 write() 的内存尚未分配映射
  • 在 walkaddr() 中加入判断
    • 如果出现找不到页的情况，马上分配
    • 具体的分配页的判断和 usertrap() 中的一样，于是我们将其封装为一个函数

(6) 最终的修改情况

  • kernel/defs.h
1
2
// vm.c
uint64          alloc_page(struct proc*, uint64);
  • kernel/vm.c
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 增加一个 lazy allocation 的函数
uint64 alloc_page(struct proc* p, uint64 vm_addr){
    // 访问的虚拟地址没有申请
    // 虚拟地址越界
    if(vm_addr >= p->sz) {
        return 0;
    }
    // 用户栈溢出
    uint64 ustack = p->trapframe->sp;
    if(vm_addr < (uint64)PGROUNDDOWN(ustack)) {
        return 0;
    }
    vm_addr = PGROUNDDOWN(vm_addr);
    pagetable_t pagetable = p->pagetable;
    char *mem;
    // 为虚拟页分配一页物理页
    mem = kalloc();
    // 当分配不到物理页时的处理
    if(mem == 0) {
        return 0;
    }
    // 刷零
    memset(mem, 0, PGSIZE);
    if(mappages(pagetable, vm_addr, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
        kfree(mem);
        return 0;
    }
    return (uint64)mem;
}

// uvmcopy()
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;
    }
    // ...
}

// uvmunmap()
void uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free) {
    // ...
    if((pte = walk(pagetable, a, 0)) == 0) {
        // panic("uvmunmap: walk");
        continue;
    }
    // 分配了而且映射了的内存才需要释放
    if((*pte & PTE_V) == 0) {
        // panic("uvmunmap: not mapped");
        continue;
    }
    // ...
}

// walkaddr()
uint64 walkaddr(pagetable_t pagetable, uint64 va)
    // 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) {
        pa = alloc_page(myproc(), va);
    } else {
        pa = PTE2PA(*pte);
    }
// ...
}
  • kernel/sysproc.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
uint64 sys_sbrk(void) {
    uint64 addr;
    int n;
    struct proc* p;
    if(argint(0, &n) < 0)
        return -1;
    p = myproc();
    addr = p->sz;
    if(n < 0) {
        if(growproc(n) < 0)
            return -1;
    } else {
        p->sz = addr + n;
    }
    return addr;
}
  • kernel/trap.c
1
2
3
4
5
6
7
8
9
10
11
void usertrap(void) {
    // ...
    else if(r_scause() == 15 || r_scause() == 13) {
        int ret = alloc_page(p, r_stval());
        if(ret == 0) {
            p->killed = 1;
            exit(-1);
        }
    }
    // ...
}

3. 实验结果

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
$ make qemu-gdb
(26.0s)
== Test   lazy: map ==
  lazy: map: OK
== Test   lazy: unmap ==
  lazy: unmap: OK
== Test usertests ==
$ make qemu-gdb
Timeout! (300.9s)
== Test   usertests: pgbug ==
  usertests: pgbug: OK
== Test   usertests: sbrkbugs ==
  usertests: sbrkbugs: OK
== Test   usertests: argptest ==
  usertests: argptest: OK
== Test   usertests: sbrkmuch ==
  usertests: sbrkmuch: OK
== Test   usertests: sbrkfail ==
  usertests: sbrkfail: OK
== Test   usertests: sbrkarg ==
  usertests: sbrkarg: OK
== Test   usertests: stacktest ==
  usertests: stacktest: OK
== Test   usertests: execout ==
  usertests: execout: OK
== Test   usertests: copyin ==
  usertests: copyin: OK
== Test   usertests: copyout ==
  usertests: copyout: OK
== Test   usertests: copyinstr1 ==
  usertests: copyinstr1: OK
== Test   usertests: copyinstr2 ==
  usertests: copyinstr2: OK
== Test   usertests: copyinstr3 ==
  usertests: copyinstr3: OK
== Test   usertests: rwsbrk ==
  usertests: rwsbrk: OK
== Test   usertests: truncate1 ==
  usertests: truncate1: OK
== Test   usertests: truncate2 ==
  usertests: truncate2: OK
== Test   usertests: truncate3 ==
  usertests: truncate3: OK
== Test   usertests: reparent2 ==
  usertests: reparent2: OK
== Test   usertests: badarg ==
  usertests: badarg: OK
== Test   usertests: reparent ==
  usertests: reparent: OK
== Test   usertests: twochildren ==
  usertests: twochildren: OK
== Test   usertests: forkfork ==
  usertests: forkfork: OK
== Test   usertests: forkforkfork ==
  usertests: forkforkfork: OK
== Test   usertests: createdelete ==
  usertests: createdelete: OK
== Test   usertests: linkunlink ==
  usertests: linkunlink: OK
== Test   usertests: linktest ==
  usertests: linktest: OK
== Test   usertests: unlinkread ==
  usertests: unlinkread: OK
== Test   usertests: concreate ==
  usertests: concreate: OK
== Test   usertests: subdir ==
  usertests: subdir: OK
== Test   usertests: fourfiles ==
  usertests: fourfiles: OK
== Test   usertests: sharedfd ==
  usertests: sharedfd: OK
== Test   usertests: exectest ==
  usertests: exectest: OK
== Test   usertests: bigargtest ==
  usertests: bigargtest: OK
== Test   usertests: bigwrite ==
  usertests: bigwrite: OK
== Test   usertests: bsstest ==
  usertests: bsstest: OK
== Test   usertests: sbrkbasic ==
  usertests: sbrkbasic: OK
== Test   usertests: kernmem ==
  usertests: kernmem: OK
== Test   usertests: validatetest ==
  usertests: validatetest: OK
== Test   usertests: opentest ==
  usertests: opentest: OK
== Test   usertests: writetest ==
  usertests: writetest: OK
== Test   usertests: writebig ==
  usertests: writebig: OK
== Test   usertests: createtest ==
  usertests: createtest: OK
== Test   usertests: openiput ==
  usertests: openiput: OK
== Test   usertests: exitiput ==
  usertests: exitiput: OK
== Test   usertests: iput ==
  usertests: iput: OK
== Test   usertests: mem ==
  usertests: mem: OK
== Test   usertests: pipe1 ==
  usertests: pipe1: OK
== Test   usertests: preempt ==
  usertests: preempt: OK
== Test   usertests: exitwait ==
  usertests: exitwait: OK
== Test   usertests: rmdot ==
  usertests: rmdot: OK
== Test   usertests: fourteen ==
  usertests: fourteen: OK
== Test   usertests: bigfile ==
  usertests: bigfile: OK
== Test   usertests: dirfile ==
  usertests: dirfile: OK
== Test   usertests: iref ==
  usertests: iref: OK
== Test   usertests: forktest ==
  usertests: forktest: OK
== Test time ==
time: OK
Score: 119/119

4. 遇到的困难以及收获

  • 在 sys_sbrk() 函数中的部分 addr 被声明成了 int，但是实际上应该是 uint64，这个 bug 改了好久，一直都在报错 panic("walk")，看来对原始的代码也不能都相信，还得是自己重新修改下
  • 有些问题的设计还是挺巧妙的，例如在内核态下遇到了 pagefault 的处理，这个在之前都没有仔细思考过
  • 在学习完这一部分的 lab 之后，对整个多级页表的立即更加深入了，对操作系统在底层内存空间实现也有了更好的理解

5. 对课程或 lab 的意见和建议

  • 希望中文版本能把 hint 也翻译过来（当然不是必要的）

6. 参考文献

  • https://pdos.csail.mit.edu/6.828/2020/xv6/book-riscv-rev1.pdf