Compulsory exercises

Preparation

  • To start the lab, switch to the cow branch:
1
2
3
git fetch
git checkout cow
make clean
  • OS真不是人写的把😭

Implement copy-on write(hard)

  • 当xv6 fork一个子进程时，需要复制父进程的地址空间，这不仅占用了空间，也消耗了时间，你的任务是采用写时复制，fork()时child使用parent的内存空间，即子进程映射到父进程的物理空间上，当进程要写时，触发Page Fault
  • 实现COW
  • 修改uvmcopy()以在fork()时不分配新page，而映射到父进程
vm.c uvmcopy()
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
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;

  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);

    acquire(&cnt_lock);
    cnt[((uint64)pa) >> 12] += 1;
    release(&cnt_lock);

    *pte = *pte & (~PTE_W);
    *pte = *pte | (PTE_RSW);
    flags = PTE_FLAGS(*pte);

    if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
      goto err;
    }
  }
  return 0;

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

  • 修改usertrap()以处理Page Fault

trap.c usertrap()
1
2
3
4
5
6
else if ((r_scause() == 15)) {
  uint64 va = r_stval();
  if (cow(p->pagetable, va) < 0) {
    p->killed = 1;
  }
}

  • 添加PTE_RSW标志位用于标识是否是cow page

riscv.h
1
#define PTE_RSW (1L << 8)

  • 添加cow处理函数

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
int 
cow(pagetable_t pagetable, uint64 va) {
    if (va >= MAXVA) {
      return -1;
    }
    pte_t* pte = walk(pagetable, va, 0);
    if (pte == 0) {
      return -1;
    }
    if ((*pte & PTE_V) == 0) {
      return -1;
    }
    if ((*pte & PTE_RSW) == 0) {
      return -1;
    }
    if ((*pte & PTE_U) == 0) {
      return -1;
    }
    uint64 pa = PTE2PA(*pte);
    uint64 ka = (uint64) kalloc();
    if (ka == 0) {
      return -1;
    } else {
      memmove((char*)ka, (char*)pa, PGSIZE);
      uint64 flags = PTE_FLAGS(*pte);
      *pte = PA2PTE(ka) | flags | PTE_W;
      *pte &= (~PTE_RSW);
      kfree((void *)pa);

      return 0;
    }
}

  • 修改copyout()

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
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;

    pte_t* pte = walk(pagetable, va0, 0);
    if (pte == 0) {
      return -1;
    }

    if ((*pte & PTE_W) == 0) {
      if (cow(pagetable, va0) < 0) {
        return -1;
      }
    }
    pa0 = PTE2PA(*pte);

    n = PGSIZE - (dstva - va0);
    if(n > len)
      n = len;
    memmove((void *)(pa0 + (dstva - va0)), src, n);

    len -= n;
    src += n;
    dstva = va0 + PGSIZE;
  }
  return 0;
}

  • 添加计数器和锁，并在每次fork是增加计数，在free时只有计数为0时才能真正free

kalloc.c
1
2
struct spinlock cnt_lock;
int cnt[PHYSTOP >> 12];

Optional challenge exercises

  • Modify xv6 to support both lazy page allocation and COW.

  • Measure how much your COW implementation reduces the number of bytes xv6 copies and the number of physical pages it allocates. Find and exploit opportunities to further reduce those numbers.