MIT 6.828 - 5. Lab 05: Copy-on-Write Fork for xv6

Tags: MIT 6.828

实验总结

  1. 本次实验用时约 11 个小时。
  2. 收获是对 Copy-on-Write 机制的理解更深入了。

遇到的困难包括: 1. 懒。 2. 中间把代码写挂了两次,经过 soha 提示,恍然大悟,原因是相同的:在子进程退出内存回收时把共享的 physical page 给回收了,经过修改已经解决。

测试结果:

1
2
3
4
5
6
7
8
9
10
11
running cowtest: 
$ make qemu-gdb
(6.4s)
simple: OK
three: OK
file: OK
usertests:
$ make qemu-gdb
OK (87.4s)
time: OK
Score: 100/100

0. 实验准备

实验指导链接

上来直接:

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

可以将实验分为几个子任务:

  1. 给内存页面管理系统 kalloc.c 加上引用计数机制。(这里应该加一些 assert ,就可以有效避免上述 困难2 不会调的问题,我没加,故调不出来)
  2. 修改 uvmcopy() 使其创建 cow 页面而不是立即复制。cow 页面的特点:可读不可写,有一个 PTE_COW 标记。(这个标记复用的 rv 定义的 pte 中第一个 custom 标志位)
  3. 修改 usertrap() 使其处理 store page fault 硬件异常(查 rv 手册知,是 15 号),此时创建新页面,更新页表。
  4. 确认引用为 0 时,物理页面会被回收。
  5. 对系统调用进行检查,在他们写入 cow 页面前创建新页面。

0. 引用计数

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
struct {
struct spinlock lock;
struct run *freelist;
uint *ref_count;
} kmem;

void
kinit()
{
initlock(&kmem.lock, "kmem");
kmem.ref_count = (uint*)end;
uint64 rc_pages = ((((PHYSTOP - (uint64)end) >> 12) + 1) * sizeof(uint) >> 12) + 1;
uint64 rc_offset = (uint64)rc_pages << 12;
freerange(end + rc_offset, (void*)PHYSTOP);
}

// ...

void
kref(void* pa) {
uint64 idx = ((uint64)pa - (uint64)end) >> 12;

acquire(&kmem.lock);
kmem.ref_count[idx]++;
release(&kmem.lock);
}

void
kderef(void* pa) {
uint64 idx = ((uint64)pa - (uint64)end) >> 12;
char shall_free = 0;

acquire(&kmem.lock);
kmem.ref_count[idx]--;
if(kmem.ref_count[idx] == 0)
shall_free = 1;
release(&kmem.lock);

if(shall_free)
kfree(pa);
}

1. 实现基于 cow 的 uvmcopy

非常好改,其中 PTE_COW = (1L << 8),详见 rv 手册。

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
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
pte_t *pte;
uint64 pa, i;
uint flags, newflags;

for(i = 0; i < sz; i += PGSIZE){
if((pte = walk(old, i, 0)) == 0)
panic("uvmcopy: pte should exist");
if((*pte & PTE_V) == 0)
panic("uvmcopy: page not present");
pa = PTE2PA(*pte);
flags = PTE_FLAGS(*pte);
kref((void*)pa);
newflags = flags | PTE_COW;
newflags &= (~PTE_W);
if(mappages(new, i, PGSIZE, (uint64)pa, newflags) == 0) {
uvmunmap(old, i, PGSIZE, 0);
if(mappages(old, i, PGSIZE, pa, newflags) != 0) {
panic("Bad mapping");
}
} else {
kderef((void*)pa);
goto err;
}
}
return 0;

err:
uvmunmap(new, 0, i, 1);
return -1;
}

2. 处理页面异常

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
if(r_scause() == 15) {
// 15: load page fault
uint64 fault_addr = r_stval();
uint64 vpage_head = PGROUNDDOWN(fault_addr);

pte_t *pte;
if((pte = walk(p->pagetable, vpage_head, 0)) == 0) {
printf("usertrap(): page not found\n");
p->killed = 1;
goto end;
}

if((*pte | PTE_V) && (*pte | PTE_U) && (*pte | PTE_COW)) {
char *mem = kalloc();
if(mem == 0) {
printf("usertrap(): no more physical page found, exit due to OOM\n");
p->killed = 1;
goto end;
}

char *pa = (char *)PTE2PA(*pte);
memmove(mem, pa, PGSIZE);
uint flags = PTE_FLAGS(*pte);
uint newflags = flags & (~PTE_COW);
newflags |= PTE_W;

uvmunmap(p->pagetable, vpage_head, PGSIZE, 0);
kderef((void*)pa);
if(mappages(p->pagetable, vpage_head, PGSIZE, (uint64)mem, newflags) != 0) {
panic("usertrap(): cannot map page\n");
}
}
}

4 & 5. 各种检查

模拟页表和缺页的检查代码实现如下。把它插到 sys_read sys_write sys_pipe 这三个系统调用中,即可通过 usertests

注意到需要特判 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
37
38
39
40
41
42
43
int uvmchkaddr(struct proc *p, uint64 addr, uint64 size, int write) {
pagetable_t pagetable = p->pagetable;
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;
}
}

a = PGROUNDDOWN(addr);
end = PGROUNDUP(a + size);
for(; a < end; a += PGSIZE) {
if((pte = walk(pagetable, a, 1)) == 0)
panic("uvmchkaddr(): bad pte");

if(write && (*pte & PTE_COW)) {
uint64 pa0 = PTE2PA(*pte);
char *mem = kalloc();
if(mem == 0) {
printf("uvmchkaddr(): no more physical page found, exit due to OOM\n");
return -1;
}
memmove(mem, (void *)pa0, PGSIZE);
uint flags = PTE_FLAGS(*pte);
uint newflags = flags & (~PTE_COW);
newflags |= PTE_W;

uvmunmap(pagetable, a, PGSIZE, 0);
kderef((void *)pa0);
if(mappages(pagetable, a, PGSIZE, (uint64)mem, newflags) != 0) {
panic("uvmchkaddr(): cannot map page\n");
}
} else {
if(!((*pte & PTE_U) && (*pte & PTE_V)))
return -1;
}
}

return 0;
}


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