本文是MIT课程6.S081操作系统学习笔记的一部分：

相关的代码都放在了GitHub下了：RayZhang13/MIT-6.S081-2021

课程相关的资源、视频和教材见Lab util: Unix utilities开头。

在xv6操作系统中，虚拟内存提供了一种间接性，使得内核可以通过标记PTE无效或者只读来完成对内存访问的拦截，并产生缺页中断，最终通过修改PTE来实现映射物理地址的修改。

这次的Lab中，我们将实现一个写时复制（Copy-on-Write）版本的fork机制，来增进对xv6中虚拟内存和COW的了解。

准备

对应课程

本次的作业是Lab Cow，我们将修改xv6内核相关代码，最终实现COW下的fork功能。

这次我们需要看掉Lecture 8，也就是B站课程的P7。主要跟着网课过了下懒分配、按需补零、写时复制、按需调页和内存映射文件的相关知识，虚拟内存这块着实是玩出花来了…

另外P6，也就是Lecture 7，是6.S081 2020课程中相关Lab习题讲解课… 貌似和我们的2021习题不对应，可以去看看，但是估计也是看了个寂寞…

教材方面不用读新一章了，还是第四章Traps and system calls的内容，COW这块都在最后。

系统环境

使用Arch Linux虚拟机作为实验环境…

环境依赖配置，编译使用make qemu等，如遇到问题，见第一次的Lab util: Unix utilities

使用准备

参考本次的实验说明书：Lab cow: Copy-on-write fork

从仓库clone下来课程文件：

1
git clone git://g.csail.mit.edu/xv6-labs-2021

切换到本次作业的cow分支即可：

1
2
cd xv6-labs-2021
git checkout cow

在作业完成后可以使用make grade对所有结果进行评分。

题目

COW简介

在xv6操作系统下的fork系统调用实现的主要功能为：将所有的父进程用户空间内存拷贝到子进程用户空间。如果父进程当前占用的内存空间很大，那么拷贝的过程将产生很大的开销，并花费相当一段时间。更糟糕的是，这部分开销很有可能是浪费的，例如fork()操作后在子进程中紧跟着执行exec()，那么子进程将丢弃刚才拷贝的所有内存，可能根本没有使用其中的大部分。另一方面，如果父进程和子进程都使用了同一个页面，并且有进程修改了页面，那么此时内存的拷贝就是需要的，毕竟父进程和子进程的内存空间在逻辑上应当是独立的互不影响的。

因此我们引入了COW机制，即写时复制。在fork中，我们的目的是尽可能地延后创建出的子进程，其物理内存的分配和复制时机，直到最后必须需要内存复制。

下图COW示例取自CS:APP 图9.30：

首先进程1和进程2，共享了一个object，在fork示例中，我们可以认为是父进程的用户空间。虚拟内存分别在两个进程的用户空间中做了映射，指向同一块物理内存地址，也就是我们的object在物理内存具体位置。接下来，当进程2尝试对内存的某个页进行修改时，会触发缺页中断page fault，随后COW将物理内存中对应的部分复制到其他位置，并重新映射进程2中这个内存页的物理地址，好让进程1和进程2之间内存空间互不影响，等到复制完成，我们再在新开辟复制的位置进行写操作，从而达到了进程1和进程2相互隔离的目的。

现在让我们回到fork的实现上去，在COW的fork实现中，我们首先要为子进程创建一个页表，并将其用户内存的PTE指向父进程的物理地址，也就是上图中的(a)。需要注意到的是，我们一开始需要将父进程和子进程中的PTE全部设置为只读，以方便在任何一方尝试修改共享内存页时触发缺页中断page fault。随后，内核的缺页中断处理函数判断情形（例如当前页用于COW），则为当前被中断的进程开辟一个新的内存页，并将原来的内存页数据拷贝到新内存页下，并修改PTE指向新的内存页，且标记为可写，也就是上图的(b)。至此，当缺页中断处理函数返回时，当前的用户进程就可以正常的对内存页进行写操作。

但是，由于COW机制的加入，当我们在fork中尝试释放内存页的时候会更加的棘手。由于一个物理内存页可能被多个进程的页表所引用，因此释放时必须要小心。我们需要使用一个引用数ref count，来记录当前内存页被引用的次数，只有ref count归零的时候才能代表当前内存页可以被释放。

实现COW下的fork

要求和提示

在本部分中，我们的任务是在xv6操作系统中实现一个写时复制的fork。完成的代码需要通过cowtest和usertests测试。cowtest中的相关测试样例详见user/cowtest.c。

例如，如果我们对xv6操作系统一开始什么都没做修改，就直接执行cowtest，我们会得到如下结果：

1
2
3
$ cowtest
simple: fork() failed
$

这是因为在simple测试样例中，它分配了超过一半的可用物理内存空间，随后调用fork。在没有实现COW的xv6下，操作系统会采取eager策略，立即为子进程创建对应用户空间并着手复制，这会直接导致物理内存空间的耗尽。

为了实现COW我们要在以下几处完成修改：

  • 修改kernel/vm.c下的uvmcopy()函数，我们需要共享父进程和子进程的用户空间，而非重新分配新的内存。此外，我们还需要将子进程和父进程的PTE置为只读，以触发缺页中断page fault。
  • 修改kernel/trap.c下的usertrap()函数，使得内核可以正确的判断出发生了缺页中断page fault。一旦内核识别出在一个COW内存页上发生了缺页中断，就需要使用kalloc()开辟新的内存页，并将原内存页的数据拷贝到新的内存页上，并设置新的映射关系，将PTE下的可读PTE_W置位。
  • 我们需要确保当该物理页面最后的PTE引用ref count清零了才可将其进行释放。当kernel/kalloc.c下的kalloc()分配该内存页时我们就将其ref count设置为1，每当有fork操作使得子进程共享该内存页时我们就将ref count加一，同理每当一个进程将对应映射关系从其页表中删除时，我们就要将ref count减一。只有当ref count清零的时候我们才可以将当前内存页使用kernel/kalloc.c下的kfree()放置在空闲列表中。我们可以把这些计数的ref count放在一个固定大小的整数数组中，例如我们可以使用页面的物理地址除以4096来索引数组，然后给数组一个等同于kalloc.c中kinit()放置在空闲列表中页面的最高物理地址的元素数。
  • 不要忘记修改kernel/vm.c下的copyout()，来适应COW的内存页，因为可能有用户空间下的内存页暂未被分配，原先的copyout也会触发page fault。

相关提示：

  • 我们很有可能需要标记当前的PTE为COW内存页映射，因此我们可以使用RSW（reserved for software）标识位来实现：

  • 一些有用的宏和定义可以方便处理PTE的相关标识位，这些代码在kernel/riscv.h的最后可以找到。

  • 如果COW下的缺页中断产生了，但是也没有足够的物理内存空间，那么进程应当被杀死。

设置refcount引用计数

为了标记物理内存中各个内存页的被引用情况，我们需要使用引用计数法。那么怎样设计存储计数的数据结构呢，正如上文中提示所说的，我们将物理内存RAM所在的地址按照页面划分成(PHYSTOP - KERNBASE) / PGSIZE个页面：

因此我们的数据结构在kernel/kalloc.c下设计为：

1
2
3
4
struct {
  struct spinlock lock;
  int refcount_arr[(PHYSTOP - KERNBASE) / PGSIZE];
} refcount;

初始化的时候也记得初始化一下锁：

1
2
3
4
5
6
7
void
kinit()
{
  initlock(&refcount.lock, "refcount");
  initlock(&kmem.lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}

另外我们顺带实现两个修改ref count的函数，其中一个用于直接设置数值，例如在kalloc时就需要将ref count直接设置为1；另外一个用于为当前的内存页ref count追加数值，例如在fork中将当前的内存页映射给新的进程时就需要加一，而在取消映射的时候就需要减一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int refcount_add(uint64 va, int add) { 
  int index = (va - KERNBASE) / PGSIZE;
  acquire(&refcount.lock);
  int res = refcount.refcount_arr[index];
  res += add;
  refcount.refcount_arr[index] = res;
  release(&refcount.lock);
  return res;
}

void refcount_set(uint64 va, int ref) { 
  int index = (va - KERNBASE) / PGSIZE; 
  acquire(&refcount.lock);
  refcount.refcount_arr[index] = ref;
  release(&refcount.lock);
}

另外也不要忘记把这两个函数在kernel/defs.h下注册一下：

1
2
int             refcount_add(uint64, int);
void            refcount_set(uint64, int);

修改kalloc和kfree

在kernel/kalloc.c下，根据上面提到的做法，我们需要在kalloc中添加功能，将对应的内存页引用数设置为1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
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

  if (r) 
    refcount_set((uint64)r, 1);
    
  return (void*)r;
}

而在何时进行引用数的自减时，还是建议将相关的操作交给kfree，而不是kernel/vm.c下的uvmummap。虽然我们说在页表中取消映射关系的时候进行减一，事实上我们需要将相关的决策交给kfree，一方面也是为了和kalloc相对应，一方面也不是只有uvmunmap的情形下需要对引用数进行减操作。所以代码如下：

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
// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");
  
  if (refcount_add((uint64)pa, -1) > 0) {
    return;
  }

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

注意到在kernel/kalloc.c下的freerange函数中，在对所有物理内存页面进行初始化的过程中调用了kfree，这可能会导致所有的内存页引用数转为-1，一个临时性的解决办法就是提前将页面的ref count设置为1，这样减一后刚好是0，满足了我们的需求：

1
2
3
4
5
6
7
8
9
10
void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE){
    refcount_set((uint64)p, 1);
    kfree(p);
  }
}

修改uvmcopy函数

根据刚才的提示，我们要修改kernel/vm.c下的uvmvopy函数。之所以要修改这个函数，是因为fork()调用这个函数来实现对用户态页表和用户空间数据的复制。

但是现在COW下，我们需要共享父进程和子进程的用户空间，而非重新分配新的内存。此外，我们还需要将子进程和父进程的PTE置为只读，以触发缺页中断page fault，另外将PTE标记上COW标志符，表示这是一个写时复制的COW内存页。

首先我们需要定义COW的标识位，这块需要我们在kernel/riscv.h的最后添加一行：

1
2
3
4
5
6
#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) // 1 -> set as 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
31
32
// Given a parent process's page table, copy
// its memory into a child's page table.
// Copies both the page table and the
// physical memory.
// returns 0 on success, -1 on failure.
// frees any allocated pages on failure.
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;

  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);
    if (*pte & PTE_W) { // if the page is writable
        *pte ^= PTE_W; // disable write flag
        *pte |= PTE_COW; //setup COW flag
    }
    // map pagetable to same physical addr in the new processs
    if(mappages(new, i, PGSIZE, (uint64)pa, PTE_FLAGS(*pte)) != 0){
      uvmunmap(new, 0, i / PGSIZE, 1);
      return -1;
    }
    // increace ref for page share
    refcount_add(pa, 1);
  }
  return 0;
}

实现COW页面缺页中断处理函数copycow

这样改下来程序一时半会儿是跑不起来了，因为当我们尝试想COW页面写入的时候会触发缺页中断，这里我们先把缺页中断的处理函数实现一下。根据刚才的提示，我们需要使用kalloc()开辟新的内存页，并将原内存页的数据拷贝到新的内存页上，并设置新的映射关系，将PTE下的可读PTE_W置位，并将COW标识位清零。

我们在kernel/vm.c下实现copycow函数：

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 cow page,
// Return 0 on success, -1 on failure, -2 on invalid va
int copycow(pagetable_t pagetable, uint64 va) { 
  if (va >= MAXVA) {
    printf("va cannot be greater than MAXVA: %p\n", va);
    return -2;
  }
  uint64 mem;
  va = PGROUNDDOWN(va);
  pte_t *pte = walk(pagetable, va, 0);
  uint64 pa = PTE2PA(*pte);
  uint flags = PTE_FLAGS(*pte);
  if (!(*pte & PTE_COW)){ // check if page is COW page
    printf("Not a COW page. Invalid va: %p\n", va);
    return -2;
  }
  if (!(mem = (uint64)kalloc())){ // kalloc new page
    printf("Failed to allocate physical page.\n");
    return -1;
  }
  memmove((void *)mem, (void *)pa, PGSIZE); //copy to new page
  flags ^= PTE_COW | PTE_W; // setup write flag, disable COW flag
  uvmunmap(pagetable, va, 1, 1); // cancel original pagetable map which caused page fault
  if (mappages(pagetable, va, PGSIZE, mem, flags) != 0) { // remap va to new page
    kfree((void*)mem);
    return -1;
  }
  return 0;
}

另外记得顺带在kernel/defs.h中声明一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// vm.c
void            kvminit(void);
void            kvminithart(void);
void            kvmmap(pagetable_t, uint64, uint64, uint64, int);
int             mappages(pagetable_t, uint64, uint64, uint64, int);
pagetable_t     uvmcreate(void);
void            uvminit(pagetable_t, uchar *, uint);
uint64          uvmalloc(pagetable_t, uint64, uint64);
uint64          uvmdealloc(pagetable_t, uint64, uint64);
int             uvmcopy(pagetable_t, pagetable_t, uint64);
void            uvmfree(pagetable_t, uint64);
void            uvmunmap(pagetable_t, uint64, uint64, int);
void            uvmclear(pagetable_t, uint64);
uint64          walkaddr(pagetable_t, uint64);
int             copyout(pagetable_t, uint64, char *, uint64);
int             copyin(pagetable_t, char *, uint64, uint64);
int             copyinstr(pagetable_t, char *, uint64, uint64);
int             copycow(pagetable_t, uint64);

修改trap处理函数

在设置好了copycow函数之后，我们需要将这段代码插入到kernel/trap.c下的usertrap函数中，这里我们将处理来自用户空间的中断、异常和系统调用。因此，我们需要在这里添加对缺页中断的判断分支，我们通过查询RISC-V的手册RISC-V privileged instructions，看到如下表，表示了不同类型的trap发生时scause寄存器的数值：

我们知道在COW的内存页下，读取内存页是不会导致缺页中断的，因为PTE_R标识位是正常置位的。而尝试对COW内存页写入时却会导致缺页中断，因为PTE_W是清零的，这种情形下对应的scause是15。因此，我们需要在usertrap中加入一个判断分支if (r_scause() == 15)来对这种情形进行判断：

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
//
// handle an interrupt, exception, or system call from user space.
// called from trampoline.S
//
void
usertrap(void)
{
  int which_dev = 0;

  if((r_sstatus() & SSTATUS_SPP) != 0)
    panic("usertrap: not from user mode");

  // send interrupts and exceptions to kerneltrap(),
  // since we're now in the kernel.
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();
  
  // save user program counter.
  p->trapframe->epc = r_sepc();
  
  if(r_scause() == 8){
    // system call

    if(p->killed)
      exit(-1);

    // sepc points to the ecall instruction,
    // but we want to return to the next instruction.
    p->trapframe->epc += 4;

    // an interrupt will change sstatus &c registers,
    // so don't enable until done with those registers.
    intr_on();

    syscall();
  } else if((which_dev = devintr()) != 0){
    // ok
  } else if (r_scause() == 15) {
    uint64 va = r_stval();
    if(copycow(p->pagetable, va) < 0) {
      p->killed = 1;
    }
  } else {
    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;
  }

  if(p->killed)
    exit(-1);

  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2)
    yield();

  usertrapret();
}

修改copyout函数

这点也在刚才的提示中贴心的点出来了，由于我们的COW页面是只读状态，那么在kernel/vm.c下的copyout函数需要进行修改。因为这个函数负责的是将一些数据从内核态复制到用户态，按照原先xv6的设置，copyout是不可能预见到内存空间中的内存页只读的。

修改的办法也说不上很难，在我们通过walk页表取得PTE后先不着急转化成物理地址，而是先看一下这个PTE的COW标识位，如果有标识位那直接使用刚才的copycow函数，一通操作，复制到新页面修改，映射到新的物理地址映射，再继续接下来的操作：

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
// Copy from kernel to user.
// Copy len bytes from src to virtual address dstva in a given page table.
// Return 0 on success, -1 on error.
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    if(dstva >= MAXVA){
      printf("dstva cannot be greater than MAXVA: %p\n", dstva);
      return -1;
    }
    va0 = PGROUNDDOWN(dstva);
    pte_t *pte = walk(pagetable, va0, 0);
    if(!pte) {
      printf("Failed to get pa from pgtbl. va: %p\n", va0);
      return -1;
    }
    if(*pte & PTE_COW){
      if(copycow(pagetable, va0) < 0){
        return -1;
      }
    }
    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;
}

测试

主目录下执行make clean; make qemu，然后尝试运行一下简单的cowtest，看起来没啥问题：

总结

接下来我们来到主目录上使用make grade进行评分，有几点注意一下：

  • 你需要在主目录下创建time.txt表示完成任务的时间。

  • 测试过程中usertests耗时略长，电脑机能不行的小伙伴可以适当将测试的超时延长一点点，请把主目录下 grade-lab-cow 文件里面的 timeout 参数改大点，不然可能你的测试项目还没跑完他就跳出给你标个大大的 FAIL…

接下来，我们主目录下make grade一下，看下结果：

看着不错，完事～