MIT 6.S081 Fall 2020 Lab 6

Copy-on-Write Fork for xv6

Wings 收录于类别操作系统和系列 Learning MIT 6.S081

2022-12-26 2022-12-26 约 1853 字预计阅读 4 分钟次阅读条评论

系列 - Learning MIT 6.S081

学!

Implement copy-on write

就一个实验.

uvmcopy

首先 fork 的直接 copy 不能用, 因为我们要 cow.

父子的页面映射要一样, 这里可以考虑直接 copy. 不过 PTE 需要修改, 要取消 W 位使其不可写, 并且加入一个标志位, 表示这个页面是 COW 的, 写的时候触发 page fault 去看如果有这个位, 则进行 COW.

在 riscv.h 中加一个 PTE 位的宏定义, 方便我们写代码.

1

#define PTE_C (1L << 8) // 1 -> cow page

然后修改 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


// Given a parent process's page table, copy
// its mapping into a child's page table.
// Implement COW, Clear PTE_W and set COW bit
// in the PTEs of both child and parent.
// returns 0 on success, -1 on failure.
int
uvmcopy(pagetable_t old, pagetable_t new, int 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");
    *pte &= ~PTE_W;
    *pte |= PTE_C;
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    if (mappages(new, i, PGSIZE, pa, flags) != 0)
      goto err;
  }
  return 0;

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

注意这里映射的是旧的物理地址 pa, 并且出错后 uvmunmap 不用最终 free, 第四个参数为 0.

page referee counts

由于一个物理页面可能被多个虚拟地址映射, 而进程会释放物理页面. 不能出现子进程结束, 释放页面, 然后把还被父进程引用着的页面给释放了. 所以需要记录每个物理页面的引用数, kfree 时只有一个引用才真正 free.

查看 riscv.h 或者 xv6 手册, 可以发现可用的内存是 128M, 从 KERNBASE 到 PHYSTOP, 总共 32768 个页, 用一个数组记录就行. 这里选择用 8 位无符号整数. 为方便定义了一些宏:

1
2
3
4


// shift a physical address to the ref count index
#define PA2IDX(pa) ((uint64)pa >> 12)
// shift a pte to the ref count index
#define PTE2IDX(pte) (pte >> 10)

然后在 kalloc 和 kfree 中处理引用的问题. 注意数组的初始化. 相关代码 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
37
38
39
40
41
42
43
44
45
46
47


...

uint8 refcnts[(PHYSTOP - KERNBASE) / PGSIZE];

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

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

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

  // decrease refcnt, if is 0, do free.
  if (--refcnts[PA2IDX(pa)] == 0) {
    // Fill with junk to catch dangling refs.
    memset(pa, 1, PGSIZE);

    r = (struct run*)pa;

    acquire(&kmem.lock);
    r->next = kmem.freelist;
    kmem.freelist = r;
    release(&kmem.lock);
  }
}

void *
kalloc(void)
{
  ...
  if(r) {
    refcnts[PA2IDX(r)]++;
    memset((char*)r, 5, PGSIZE); // fill with junk
  }
  ...
}

接着把 copy 时的引用处理一下:

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


extern uint8 refcnts[];

int
uvmcopy(pagetable_t old, pagetable_t new, int sz)
{
  ...
  for (i = 0; i < sz; i += PGSIZE) {
    ...
    refcnts[PTE2IDX(*pte)]++;
  }
  ...
}

handler page fault

page falut 和上一个 lab 一样, 也分两个部分, 一个在是用户态写时造成的, 另一个是内核态写时造成的.

先写一个函数 uvmcow:

 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


// Copy on write. If more than one process
// referees the pa, allocate one page and
// map to pte. Copy one page start from
// pa_start. Otherwise it's the last one.
// Just allow to write.
int
uvmcow(pte_t *pte, uint64 pa_start)
{
  if (refcnts[PTE2IDX(*pte)] > 1) {
    // there are more than one mapping.
    // alloc a new page
    uint flags = PTE_FLAGS(*pte);
    void *pa_new = kalloc();
    if(pa_new == 0)
      return -1;
    else {
      memmove(pa_new, (char *)pa_start, PGSIZE);
      refcnts[PTE2IDX(*pte)]--;
      flags &= ~PTE_C;
      flags |= PTE_W;
      *pte = PA2PTE(pa_new) | flags;
    }
  } else {
    // there is only one mapping, allow to write
    *pte &= ~PTE_C;
    *pte |= PTE_W;
  }
  return 0;
}

用户态在 usertrap 中处理 page fault.

 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


extern uint8 refcnts[];

void
usertrap(void)
{
  ...
  else if(r_scause() == 13 || r_scause() == 15) {
    uint64 va = r_stval();
    // check va is valid
    if (va >= p->sz || (p->trapframe->sp - PGSIZE <= va && va < p->trapframe->sp))
      p->killed = 1;
    else {
      pte_t *pte = walk(p->pagetable, va, 0);
      if (*pte && *pte & PTE_C) {
        // caused by cow
        uint64 pa = walkaddr(p->pagetable, va);
        if (uvmcow(pte, PGROUNDDOWN(pa)) != 0)
          p->killed = 1;
      } else {
        printf("usertrap(): unexpected page fault scause %p pid=%d\n", r_scause(), p->pid);
        printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
        p->killed = 1;
      }
    }
  }
  ...
}

根据提示, 内核态访问用户空间会发生在 copyout 的时候, 于是需要处理 copyout 中可能碰到的 cow:

 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


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

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    pte = walk(pagetable, va0, 0);
    if (*pte & PTE_C) {
      // cow
      if (uvmcow(pte, pa0) != 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;
}

有个比较坑的地方是, walk 中碰到 va 大于最大虚拟地址会 panic, 而 walkaddr 是直接返回 0. usertests 中的 copyout 就有个测试点是 va 超出限制, 所以得先 walkaddr 判断了再 walk 取 pte.

lock

CUPS = 1 时已经可以通过了, 但是多个 CUP 就会寄. 原因在于对 refcnts 操作的时候没加锁.

(之前想的时候想到了要加锁, 后来写着写着就忘记了… 看来还是要想到啥赶紧记下来)

1
2
3
4
5
6
7


// Count for physical page referee
struct krefcnt {
  struct spinlock lock;
  uint8 cnt;
};

struct krefcnt refcnts[(PHYSTOP - KERNBASE) / PGSIZE];

把 refcnts 换成这个结构体 (其实就是对每个数加了个锁)

初始化锁:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) {
    initlock(&refcnts[PA2IDX(p)].lock, "refcnt");
    refcnts[PA2IDX(p)].cnt = 1;
    kfree(p);
  }
}

在所有修改 cnt 的地方都加锁:

 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


void
kfree(void *pa)
{
  ...
  // decrease refcnt, if is 0, do free.
  idx = PA2IDX(pa);
  acquire(&refcnts[idx].lock);
  if (--refcnts[idx].cnt == 0) {
    ...
  }
  release(&refcnts[idx].lock);
}

void *
kalloc(void)
{
  ...
  if(r) {
    idx = PA2IDX(r);
    acquire(&refcnts[idx].lock);
    refcnts[idx].cnt++;
    release(&refcnts[idx].lock);
    memset((char*)r, 5, PGSIZE); // fill with junk
  }
  ...
}

int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  ...
  for(i = 0; i < sz; i += PGSIZE){
    ...
    if (mappages(new, i, PGSIZE, pa, flags) != 0)
      goto err;
    idx = PTE2IDX(*pte);
    acquire(&refcnts[idx].lock);
    refcnts[idx].cnt++;
    release(&refcnts[idx].lock);
  }
  ...
}

// Copy on write. If more than one process
// referees the pa, allocate one page and
// map to pte. Copy one page start from
// pa_start. Otherwise it's the last one.
// Just allow to write.
int
uvmcow(pte_t *pte, uint64 pa_start)
{
  int idx;

  if ((*pte & PTE_C) == 0)
    panic("uvmcow");

  idx = PTE2IDX(*pte);
  acquire(&refcnts[idx].lock);
  if (refcnts[idx].cnt > 1) {
    // there are more than one mapping.
    // alloc a new page
    uint flags = PTE_FLAGS(*pte);
    void *pa_new = kalloc();
    if(pa_new == 0) {
      release(&refcnts[idx].lock);
      return -1;
    }
    else {
      memmove(pa_new, (char *)pa_start, PGSIZE);
      refcnts[idx].cnt--;
      flags &= ~PTE_C;
      flags |= PTE_W;
      *pte = PA2PTE(pa_new) | flags;
    }
  } else {
    // there is only one mapping, allow to write
    *pte &= ~PTE_C;
    *pte |= PTE_W;
  }
  release(&refcnts[idx].lock);
  return 0;
}

Optional challenge exercises

猜到了是把 lazy allocation 结合起来, 不写了, 懒.

目录