MIT 6.828 - 4. Lab 04: Xv6 lazy page allocation

Tags: MIT 6.828

实验总结

  1. 本次实验用时约八个小时。
  2. 收获是对线性地址的理解更深入了。

遇到的困难包括:

  1. 懒。
  2. xv6-riscv 默认开了 kpti(内核和用户态页表分离) ,故需要在各种系统调用头部手动模拟 traverse 页表的过程,以及模拟处理缺页异常。(我现在觉得这不是一个很好的设计)

测试结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
$ make grade
running lazytests:
(3.7s)
lazy: pte printout: OK
lazy: map: OK
lazy: unmap: OK
usertests:
(95.8s)
usertests: pgbug: OK
usertests: sbrkbugs: OK
usertests: argptest: OK
usertests: sbrkmuch: OK
usertests: sbrkfail: OK
usertests: sbrkarg: OK
usertests: stacktest: OK
usertests: all tests: OK
Score: 100/100

0. 实验准备

实验指导链接

上来直接:

1
2
$ cd xv6-riscv-fall19
$ git checkout lazy

实验分为四个子任务(实际更多个):

  1. 设计一个输出页表的调试程序 vmprint(pagetable_t)
  2. 实现不立即分配内存的 sbrk 调用。
  3. 冒烟。
  4. 各种修复。

1. vmprint

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
void printwalk(pagetable_t pagetable, int depth)
{
// there are 2^9 = 512 PTEs in a page table.
for (int i = 0; i < 512; i++)
{
pte_t pte = pagetable[i];

if (pte & PTE_V)
{
for (int j = 0; j < depth; j++)
printf(" ..");
// printf("%d: pte %p pa %p %s%s%s\n", i, pte, PTE2PA(pte), (pte) & PTE_R ? "r" : "-", (pte) & PTE_W ? "w" : "-", (pte) & PTE_X ? "x" : "-");
printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
}

if ((pte & PTE_V) && (pte & (PTE_R | PTE_W | PTE_X)) == 0)
{
// this PTE points to a lower-level page table.
uint64 child = PTE2PA(pte);
printwalk((pagetable_t)child, depth + 1);
}
}
}

void vmprint(pagetable_t t)
{
printf("page table %p\n", t);
printwalk(t, 1);
}

2. 实现 lazy sbrk

非常好改,但通过 sbrk 输入负数来归还线性空间时,需要及时 demalloc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
if(n < 0)
uvmdealloc(myproc()->pagetable, addr, myproc()->sz);

return addr;
}

3 & 4. 冒烟 & 修复

首先需要正确处理缺页异常,完成必要的检查(访问非法的线性地址 和 栈溢出):

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
//
// handle an interrupt, exception, or system call from user space.
// called from trampoline.S
//
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->tf->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->tf->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) {
// ------------------------------------- here -------------------------------------
// 13: Page load fault, 15: Page store fault
// printf("usertrap(): page fault, scause %p pid=%d\n", r_scause(), p->pid);
// printf(" sepc=%p vaddr=%p\n", r_sepc(), r_stval());

struct proc *p = myproc();
pagetable_t pagetable = p->pagetable;
uint64 fault_vaddr = (uint64) r_stval();
uint64 vpage_base = PGROUNDDOWN(fault_vaddr);

if(fault_vaddr >= p->sz) {
// printf("usertrap(): page fault: invalid memory access to vaddr %p\n", fault_vaddr);
p->killed = 1;
goto end;
}

if(fault_vaddr < p->ustack) {
// printf("usertrap(): page fault: segfault on vaddr %p below stack %p\n", fault_vaddr, p->ustack);
p->killed = 1;
goto end;
}

char *mem = kalloc();
if(mem == 0) {
// printf("usertrap(): page fault: no more physical page available, killing process due to a OOM\n");
p->killed = 1;
goto end;
}

memset(mem, 0, PGSIZE);

if(mappages(pagetable, vpage_base, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
// printf("usertrap(): page fault: cannot map a page");
kfree(mem);
p->killed = 1;
goto end;
}
} 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;
}

end:
if(p->killed)
exit(-1);

// give up the CPU if this is a timer interrupt.
if(which_dev == 2)
yield();

usertrapret();
}

注意到为了能够正确找到栈空间顶部的位置,我给 proc 数据结构加了一个新的 entry 叫做 ustack
对应需要修改 fork 和 exec 的代码,因为在这里有新 proc 结构的生成,故需要维护这个属性。

模拟页表和缺页的检查代码实现如下:

注意到需要特判 pid = 1 的情况,是因为 xv6 的 initcode 中引用了大于用户线性空间最大值 proc->sz(这个属性由 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
35
36
int uvmchkaddr(pagetable_t pagetable, uint64 addr, uint64 size) {
struct proc* p = myproc();
char *mem;
pte_t *pte;
uint64 a, end;

if(p->pid > 1) {
if(addr >= p->sz) {
printf("uvmchkaddr(): page fault: invalid memory access to vaddr %p\n", addr);
return -1;
}

if(addr < p->ustack && addr >= p->ustack - PGSIZE) {
printf("uvmchkaddr(): page fault: segfault on vaddr %p on stack guard\n", addr);
return -1;
}
}

a = PGROUNDDOWN(addr);
end = PGROUNDUP(a + size);
for(; a < end; a += PGSIZE) {
if((pte = walk(pagetable, a, 1)) != 0 && (*pte & PTE_V))
continue;

mem = kalloc();
if(mem == 0)
return -1;
memset(mem, 0, PGSIZE);
if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
kfree(mem);
return -1;
}
}

return 0;
}


知识共享许可协议 2000 - 2099 MonKey's Blog | 自豪地采用 Hexo + Pandoc + KaTeX + Highlight.js