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