6.S081 lab6 cow

2021-02-27 约 1551 字预计阅读 4 分钟

Copy-on-Write Fork for xv6

这次 lab 只有一关，那就是为xv6实现copy on write。

xv6中的fork()系统调用将父进程的用户内存全部复制到子进程中。如果父进程内存占用很大，复制可能需要很长的时间。更糟糕的是，通常来说，这个复制在很大程度上是浪费的；例如，在子进程中，fork()之后的exec()调用会导致子进程丢弃复制的内存，可能大部分内存都没有来得及使用。另一方面，如果父子双方都使用一个page，并且其中一方或双方需要写这个page，那么确实需要复制。

根据官网给的提示：

使用引用计数，对每个物理页面维护一个reference count，记录物理页面被 map 的次数。

kernel/kalloc.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


struct {
  struct spinlock lock;
  struct run *freelist;
  int rc[PHYSTOP / PGSIZE];
} kmem;

void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) {
    kmem.rc[(uint64)p / PGSIZE] = 1;
    kfree(p);
  }
}

void
increase_rc(uint64 pa) {
  acquire(&kmem.lock);
  kmem.rc[pa / PGSIZE]++;
  release(&kmem.lock);
}

利用 RISC-V PTE 中的RSW (reserved for software)位来标记cow页，修改uvmcopy(),在复制内存时，仅将父进程的物理页面 map 到子进程页表中，并清除双方PTE中的PTE_W标志。

在kernel/riscv.h中加入：

1

#define PTE_COW (1L << 8)

在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


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);
    flags = PTE_FLAGS(*pte);
    // only for writable page
    if (flags & PTE_W) {
      flags = (flags | PTE_COW) & (~PTE_W);
      *pte = PA2PTE(pa) | flags;
    }
    increase_rc(pa);
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
      goto err;
    }
  }
  return 0;

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

注意mappages失败时，删掉原有的kfree(mem)，因为我们没有申请新的内存。

发生page falut时，在usertrap()中捕获，对cow page分配真正的物理内存。

kernel/kalloc.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


int
cow_alloc(pagetable_t pagetable, uint64 va) {
  uint64 pa;
  uint64 mem;
  pte_t *pte;
  if (va >= MAXVA)
    return -1;
  va = PGROUNDDOWN(va);
  pte = walk(pagetable, va, 0);
  if (pte == 0) {
    return -1;
  }
  // not a valid cow page
  if (!(*pte & PTE_V)) {
    return -2;
  }
  pa = PTE2PA(*pte);

  // only one rf, make it writable
  acquire(&kmem.lock);
  if (kmem.rc[pa / PGSIZE] == 1) {
    *pte &= ~PTE_COW;
    *pte |= PTE_W;
    release(&kmem.lock);
    return 0;
  }
  release(&kmem.lock);
  if ((mem = (uint64)kalloc()) == 0){
    return -3;
  }
  memmove((void *)mem, (void *)pa, PGSIZE);
  *pte = ((PA2PTE(mem) | PTE_FLAGS(*pte) | PTE_W) & (~PTE_COW));
  // decrease rc
  kfree((void *)pa);
  return 0;
}

在我的实现中，当cow page发生page fault，且reference count为 1 时，不再重新分配页面进行复制，而是直接将该页面消去PTE_COW并加上PTE_W，减少内存分配和复制操作。

在kernel/trap.c：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


else if(r_scause() == 13 || r_scause() == 15) {
  va = r_stval();
  if (va < PGROUNDDOWN(p->trapframe->sp) &&
      va >= PGROUNDDOWN(p->trapframe->sp) - PGSIZE) {
    // guard page
    p->killed = 1;
  } else {
    int ret;
    if((ret = cow_alloc(p->pagetable, va)) < 0 ) {
      p->killed = 1;
    }
  }
}

当使用kalloc()进行内存分配时，需要将对应page的reference count设置为 1，使用kfree()释放内存时，只能将reference count为 0 的页面放回空闲列表。

kernel/kalloc.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


void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r) {
    kmem.freelist = r->next;
    kmem.rc[(uint64)r / PGSIZE] = 1;
  }
  release(&kmem.lock);

  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}

void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  acquire(&kmem.lock);
  kmem.rc[(uint64)pa / PGSIZE]--;
  if(kmem.rc[(uint64)pa / PGSIZE] <= 0) {
    memset(pa, 1, PGSIZE);
    r = (struct run*)pa;
    r->next = kmem.freelist;
    kmem.freelist = r;
  }
  release(&kmem.lock);
}

注意：kfree()中，对于kmem.rc[(uint64)pa / PGSIZE]的修改和读取必须是一个原子操作，否则内存可能被重复释放，例如对于某个物理page，同时 map 到 A、B 的页表中，之后：

A : ref - 1
B : ref - 1
A : ref == 0 => free
B : ref == 0 => free

最后，我们需要修改copyout()，同lazy allocation一样，当因为系统调用切换到内核页表时，硬件无法再为写cow page产生page fault，所以我们需要手动处理：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    cow_alloc(pagetable, va0);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    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;
}

至此便完成了 lab6 copy on write。

目录

6.S081 lab6 cow

Copy-on-Write Fork for xv6