XV6 Lab：Copy On Write

Introduction

本文旨在记录作者完成课程任务的过程，可供参考。

本实验需要完成的内容大致如下

The goal of copy-on-write (COW) fork() is to defer allocating and copying physical memory pages for the child until the copies are actually needed, if ever.

Here's a reasonable plan of attack.

1. Modify uvmcopy() to map the parent's physical pages into the child, instead of allocating new pages. Clear PTE_W in the PTEs of both child and parent.
2. Modify usertrap() to recognize page faults. When a page-fault occurs on a COW page, allocate a new page with kalloc(), copy the old page to the new page, and install the new page in the PTE with PTE_W set.
3. Ensure that each physical page is freed when the last PTE reference to it goes away -- but not before. A good way to do this is to keep, for each physical page, a "reference count" of the number of user page tables that refer to that page. Set a page's reference count to one when kalloc() allocates it. Increment a page's reference count when fork causes a child to share the page, and decrement a page's count each time any process drops the page from its page table. kfree() should only place a page back on the free list if its reference count is zero. It's OK to to keep these counts in a fixed-size array of integers. You'll have to work out a scheme for how to index the array and how to choose its size. For example, you could index the array with the page's physical address divided by 4096, and give the array a number of elements equal to highest physical address of any page placed on the free list by kinit() in kalloc.c.
4. Modify copyout() to use the same scheme as page faults when it encounters a COW page.

实验仓库链接如下

xv6-2020

指导书链接如下

xv6-CopyOnWrite

仓库内有多个 lab 分支，本文所提的 lab 对应的分支切换方法如下

git checkout cow

问题：该 xv6 版本较旧，在较新版本的 qemu 上会遇到无法启动的问题，需要在 start.c 中添加下面的代码

  // configure Physical Memory Protection to give supervisor mode
  // access to all of physical memory.
  w_pmpaddr0(0x3fffffffffffffull);
  w_pmpcfg0(0xf);

同样的，较新版本的 gcc 也会遇到一些问题

修改计划

在原本的 xv6 中，fork 的过程大致如下

1. 调用 allocproc 新分配一个进程，带有空白用户页表
2. 调用 uvmcopy 复制父进程的页表到子进程
   1. 这个函数会按照 VA 从低到高，根据父进程页表找到对应的 PTE 和 PA
   2. 给子进程分配新的页，复制父进程的PA的内容到这里，并且 PTE 的 Flags 也一并取出
   3. 调用 mappages 更新子进程页表
3. 处理文件引用相关的事情

exec 的过程如下

1. 打开新的 ELF 文件
2. 创建新的空白页表 (proc_pagetable)
3. 把 ELF 的内容加载进内存 (uvmalloc)
4. 创建用户栈并把 argv 放进用户栈中
5. 释放旧的页表（proc_freepagetable）

可以看到这个过程中花了大力气复制的页表直接被抛弃了，所以我们需要做的就是修改用户页表时实现 COW ，只有需要修改时再发生复制和写入操作。

xv6 mit 官方指导书给出的修改路线如下

1. 修改 uvmcopy()
   • PTE_W = 0
   • PTE_COW = 1
   • 物理地址的 Reference Count ++
2. 修改 usertrap()
   • 识别出 COW
   • 调用 kalloc() 并复制新页，新物理地址的 PTE_W=1, PTE_COW=0
   • 原物理地址 Reference Count– ，如果变成了 1 ，同样设置 PTE_W=1, PTE_COW=0
3. Reference Count 处理
   • 用一个数组为 freelist 中每个物理页都设置引用计数
   • kinit() 将引用计数都初始化为 0
   • kfree() 减少引用计数，如果引用计数减少到为 0 了，放回 freelist 中
   • kalloc() 引用计数设置为 1
4. 修改 copyout()
   • 给定用户页表、目标虚拟地址、内核地址以及拷贝长度，该函数会将数据拷贝到目标地址中
   • 这同样需要使用 COW 机制

实现过程

添加 PTE_COW 标志位

首先我们需要添加 PTE_COW 到 RSW 中，查看 riscv rv39 的 PTE 格式如下

 63      54 53      28 27      19 18      10 9   8 7 6 5 4 3 2 1 0
+----------+----------+----------+----------+-----+-+-+-+-+-+-+-+-+
| reserved |  PPN[2]  |  PPN[1]  |  PPN[0]  | RSW |D|A|G|U|X|W|R|V|
+----------+----------+----------+----------+-----+-+-+-+-+-+-+-+-+
     10         26          9          9       2   1 1 1 1 1 1 1 1

这里选择第8位作为 PTE_COW

#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // 1 -> user can access

#define PTE_COW (1L << 8) // 新增RSW

添加 Reference Count

在 kalloc.c 中进行修改

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}

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

从上面的代码可以得知 freelist 的范围——end 到 PHYSTOP-1，这样就可以知道 reference count 的数组至少有多大了。

为了方便找到数组索引，设计如下的索引方式

int ref_cnt[PHYSTOP / PGSIZE];
refer_cnt = refcnt[pa / PGSIZE];

这样一来， pa = PHYSTOP-1 时不会越界，低于 end 的部分也不会被访问，虽然数组会稍微大了一点，但是影响不大。

数组还需要加上锁的保护

struct {
  struct spinlock lock;
  int ref_cnt[PHYSTOP / PGSIZE];
} ref;

为了避免死锁，ref.lock 和 kmem.lock 不要同时拥有，最后代码大致如下

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  initlock(&ref.lock, "ref_cnt");
  freerange(end, (void*)PHYSTOP);
}

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

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

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");
  // check ref_cnt
  acquire(&ref.lock);
  int idx = (uint64)pa / PGSIZE;
  if(ref.ref_cnt[idx] <= 0)
    panic("kfree: refcnt");
  ref.ref_cnt[idx]--;
  if (ref.ref_cnt[idx] >= 1){
    release(&ref.lock);
    return;
  }
  release(&ref.lock);
  // ref_cnt = 0, free page
  // 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)
{
  struct run *r;

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

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

void incref(void *pa){
  acquire(&ref.lock);
  ref.ref_cnt[(uint64)pa/PGSIZE]++;
  release(&ref.lock);
}

同样记得修改 defs.h

修改 uvmcopy()

基础设施已经完成，接下来是其他内核函数

按照前面的说法，我们需要 clear PTE_W, set PTE_COW, 增加引用计数，代码如下

int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  // instead of allocating new pages. Clear PTE_W in the PTEs of both child and parent.
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  pte_t temp_pte;
  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);
    temp_pte = *pte;
    // 不可写区域不需要COW，已经设置 COW 和 PTE_W=0 也不用再设置一遍
    if ((*pte & PTE_W) != 0){
      *pte |= PTE_COW;
      *pte &= ~PTE_W;
    }
    flags = PTE_FLAGS(*pte);
    if(mappages(new, i, PGSIZE, pa, flags) != 0)
      goto err;
    // 增加引用数量
    incref((void *)pa);
  }
  return 0;

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

值得注意的一点是，如果原本就是不可写区域，不需要设置 COW 位

修改 usertrap()

当程序需要修改 COW 页时，会触发异常：

用户进程执行：

*p = value;        // 对 COW page 写

        ↓

PTE:
PTE_V   = 1
PTE_U   = 1
PTE_W   = 0
PTE_COW = 1       // 软件定义

        ↓

硬件发现：
这是 store
但是 PTE_W = 0

        ↓

page fault
        ↓
进入 usertrap()

查询 scause 含义可以得到

对应的 stval 则是 faulting virtual address

所以我们可以得到这样的逻辑

scause == 15 ?
       │
       no ──→ 正常处理
       │
       yes
       ↓
va = r_stval()
       ↓
va = PGROUNDDOWN(va)
       ↓
pte = walk(pagetable, va, 0)
       ↓
PTE_COW ?
       │
       no ──→ kill process
       │
       yes
       ↓
pa = PTE2PA(*pte)
       ↓
refcnt == 1 ?
   │             │
  yes            no
   │              │
   ▼              ▼
PTE_W = 1      kalloc new
PTE_COW = 0       ↓
   │           copy old → new
   │              ↓
   │           PTE → new
   │              ↓
   │           kfree(old)
   │
   └──────────────┘
          ↓
       return

由于读取 refcnt 涉及锁机制，这里暂时不使用这个方案，直接 kalloc(new), kfree(old)

....
  } else if(r_scause() == 15){
    // Store/AMO page fault
    uint64 va = PGROUNDDOWN(r_stval());
    pte_t *pte;

    if((pte = walk(p->pagetable, va, 0)) == 0)
      goto error;
    if((*pte & PTE_V) == 0)
      goto error;
    if((*pte & PTE_COW) == 0)
      goto error;
    
    uint64 pa = PTE2PA(*pte);
    uint flags = PTE_FLAGS(*pte);
    char *new_pa;
    
    // 已经确认是COW页，直接分配并复制
    if((new_pa = kalloc()) == 0){
      p->killed = 1;
    } else {
      // copy
      memmove(new_pa, (char*)pa, PGSIZE);
      // 修改 PTE
      flags |= PTE_W;
      flags &= ~PTE_COW;
      *pte = PA2PTE((uint64)new_pa) | flags;
      
      kfree((void*)pa);
    }
  } else if((which_dev = devintr()) != 0){
    // ok
  } else {
  error:
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
    p->killed = 1;
  }
...

修改 copyout()

原本的 copyout 的流程大致如下

1. 根据 dstva 和 pagetable 找到对应 pa
2. 直接进行数据复制
3. va += PGSIZE 然后循环，直到复制完成

这个过程不会触发 page fault 所以不会走上面的路径，所以我们需要自行处理

walk()
 ↓
检查 PTE
 ↓
如果 COW
    ↓
    分配新页
    copy
    修改 PTE
    kfree(old)
 ↓
再获得新的 PA
 ↓
memmove

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

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    if(va0 >= MAXVA)
      return -1;

    pte_t *pte = walk(pagetable, va0, 0);
    if(pte == 0)
      return -1;
    if((*pte & PTE_V) == 0)
      return -1;
    if((*pte & PTE_U) == 0)
      return -1;
    pa0 = PTE2PA(*pte);

    n = PGSIZE - (dstva - va0);
    if(n > len)
      n = len;
    
    // 不能直接复制！而是要检查 COW
    if ((*pte & PTE_COW)){
      char *new_pa;
      if((new_pa = kalloc()) == 0)
        return -1;
      
      // copy
      memmove(new_pa, (char*)pa0, PGSIZE);
      memmove((void *)(new_pa + (dstva - va0)), src, n);
      // 修改 PTE
      uint flags = PTE_FLAGS(*pte);
      flags |= PTE_W;
      flags &= ~PTE_COW;
      *pte = PA2PTE((uint64)new_pa) | flags;
      kfree((void*)pa0);
    } else if(*pte & PTE_W) {
      memmove((void *)(pa0 + (dstva - va0)), src, n);
    } else {
      return -1;
    }
    len -= n;
    src += n;
    dstva = va0 + PGSIZE;
  }
  return 0;
}

测试

改完之后进行测试

$ cowtest
simple: ok
simple: ok
three: ok
three: ok
three: ok
file: ok
ALL COW TESTS PASSED

$ usertests
usertests starting
test execout: OK
test copyin: OK
test copyout: OK
test copyinstr1: OK
test copyinstr2: OK
test copyinstr3: OK
test rwsbrk: OK
test truncate1: OK
test truncate2: OK
test truncate3: OK
test reparent2: OK
test pgbug: OK
test sbrkbugs: usertrap(): unexpected scause 0x000000000000000c pid=3240
            sepc=0x00000000000055d2 stval=0x00000000000055d2
usertrap(): unexpected scause 0x000000000000000c pid=3241
            sepc=0x00000000000055d2 stval=0x00000000000055d2
OK
test badarg: OK
test reparent: OK
test twochildren: OK
test forkfork: OK
test forkforkfork: OK
test argptest: OK
test createdelete: OK
test linkunlink: OK
test linktest: OK
test unlinkread: OK
test concreate: OK
test subdir: OK
test fourfiles: OK
test sharedfd: OK
test dirtest: OK
test exectest: OK
test bigargtest: OK
test bigwrite: OK
test bsstest: OK
test sbrkbasic: OK
test sbrkmuch: OK
test kernmem: usertrap(): unexpected scause 0x000000000000000d pid=6221
            sepc=0x0000000000002054 stval=0x0000000080000000
usertrap(): unexpected scause 0x000000000000000d pid=6222
            sepc=0x0000000000002054 stval=0x000000008000c350
usertrap(): unexpected scause 0x000000000000000d pid=6223
            sepc=0x0000000000002054 stval=0x00000000800186a0
usertrap(): unexpected scause 0x000000000000000d pid=6224
            sepc=0x0000000000002054 stval=0x00000000800249f0
usertrap(): unexpected scause 0x000000000000000d pid=6225
            sepc=0x0000000000002054 stval=0x0000000080030d40
usertrap(): unexpected scause 0x000000000000000d pid=6226
            sepc=0x0000000000002054 stval=0x000000008003d090
usertrap(): unexpected scause 0x000000000000000d pid=6227
            sepc=0x0000000000002054 stval=0x00000000800493e0
usertrap(): unexpected scause 0x000000000000000d pid=6228
            sepc=0x0000000000002054 stval=0x0000000080055730
usertrap(): unexpected scause 0x000000000000000d pid=6229
            sepc=0x0000000000002054 stval=0x0000000080061a80
usertrap(): unexpected scause 0x000000000000000d pid=6230
            sepc=0x0000000000002054 stval=0x000000008006ddd0
usertrap(): unexpected scause 0x000000000000000d pid=6231
            sepc=0x0000000000002054 stval=0x000000008007a120
usertrap(): unexpected scause 0x000000000000000d pid=6232
            sepc=0x0000000000002054 stval=0x0000000080086470
usertrap(): unexpected scause 0x000000000000000d pid=6233
            sepc=0x0000000000002054 stval=0x00000000800927c0
usertrap(): unexpected scause 0x000000000000000d pid=6234
            sepc=0x0000000000002054 stval=0x000000008009eb10
usertrap(): unexpected scause 0x000000000000000d pid=6235
            sepc=0x0000000000002054 stval=0x00000000800aae60
usertrap(): unexpected scause 0x000000000000000d pid=6236
            sepc=0x0000000000002054 stval=0x00000000800b71b0
usertrap(): unexpected scause 0x000000000000000d pid=6237
            sepc=0x0000000000002054 stval=0x00000000800c3500
usertrap(): unexpected scause 0x000000000000000d pid=6238
            sepc=0x0000000000002054 stval=0x00000000800cf850
usertrap(): unexpected scause 0x000000000000000d pid=6239
            sepc=0x0000000000002054 stval=0x00000000800dbba0
usertrap(): unexpected scause 0x000000000000000d pid=6240
            sepc=0x0000000000002054 stval=0x00000000800e7ef0
usertrap(): unexpected scause 0x000000000000000d pid=6241
            sepc=0x0000000000002054 stval=0x00000000800f4240
usertrap(): unexpected scause 0x000000000000000d pid=6242
            sepc=0x0000000000002054 stval=0x0000000080100590
usertrap(): unexpected scause 0x000000000000000d pid=6243
            sepc=0x0000000000002054 stval=0x000000008010c8e0
usertrap(): unexpected scause 0x000000000000000d pid=6244
            sepc=0x0000000000002054 stval=0x0000000080118c30
usertrap(): unexpected scause 0x000000000000000d pid=6245
            sepc=0x0000000000002054 stval=0x0000000080124f80
usertrap(): unexpected scause 0x000000000000000d pid=6246
            sepc=0x0000000000002054 stval=0x00000000801312d0
usertrap(): unexpected scause 0x000000000000000d pid=6247
            sepc=0x0000000000002054 stval=0x000000008013d620
usertrap(): unexpected scause 0x000000000000000d pid=6248
            sepc=0x0000000000002054 stval=0x0000000080149970
usertrap(): unexpected scause 0x000000000000000d pid=6249
            sepc=0x0000000000002054 stval=0x0000000080155cc0
usertrap(): unexpected scause 0x000000000000000d pid=6250
            sepc=0x0000000000002054 stval=0x0000000080162010
usertrap(): unexpected scause 0x000000000000000d pid=6251
            sepc=0x0000000000002054 stval=0x000000008016e360
usertrap(): unexpected scause 0x000000000000000d pid=6252
            sepc=0x0000000000002054 stval=0x000000008017a6b0
usertrap(): unexpected scause 0x000000000000000d pid=6253
            sepc=0x0000000000002054 stval=0x0000000080186a00
usertrap(): unexpected scause 0x000000000000000d pid=6254
            sepc=0x0000000000002054 stval=0x0000000080192d50
usertrap(): unexpected scause 0x000000000000000d pid=6255
            sepc=0x0000000000002054 stval=0x000000008019f0a0
usertrap(): unexpected scause 0x000000000000000d pid=6256
            sepc=0x0000000000002054 stval=0x00000000801ab3f0
usertrap(): unexpected scause 0x000000000000000d pid=6257
            sepc=0x0000000000002054 stval=0x00000000801b7740
usertrap(): unexpected scause 0x000000000000000d pid=6258
            sepc=0x0000000000002054 stval=0x00000000801c3a90
usertrap(): unexpected scause 0x000000000000000d pid=6259
            sepc=0x0000000000002054 stval=0x00000000801cfde0
usertrap(): unexpected scause 0x000000000000000d pid=6260
            sepc=0x0000000000002054 stval=0x00000000801dc130
OK
test sbrkfail: usertrap(): unexpected scause 0x000000000000000d pid=6272
            sepc=0x0000000000004112 stval=0x0000000000012000
OK
test sbrkarg: OK
test validatetest: OK
test stacktest: usertrap(): unexpected scause 0x000000000000000d pid=6276
            sepc=0x00000000000021c4 stval=0x000000000000fba0
OK
test opentest: OK
test writetest: OK
test writebig: OK
test createtest: OK
test openiput: OK
test exitiput: OK
test iput: OK
test mem: OK
test pipe1: OK
test preempt: kill... wait... OK
test exitwait: OK
test rmdot: OK
test fourteen: OK
test bigfile: OK
test dirfile: OK
test iref: OK
test forktest: OK
test bigdir: OK
ALL TESTS PASSED

完成！总共用时大约一个上午。

$ make grade
...
== Test running cowtest == 
$ make qemu-gdb
(12.5s) 
== Test   simple == 
  simple: OK 
== Test   three == 
  three: OK 
== Test   file == 
  file: OK 
== Test usertests == 
$ make qemu-gdb
(211.1s) 
== Test   usertests: copyin == 
  usertests: copyin: OK 
== Test   usertests: copyout == 
  usertests: copyout: OK 
== Test   usertests: all tests == 
  usertests: all tests: OK 
== Test time == 
time: OK 
Score: 110/110