【MIT6.S081】Lab5 copy-on-write fork

发表于 分类于 标签 , , Disqus： 本文字数： 2.2k 阅读时长 ≈ 8 分钟

为什么我们需要copy on write

通过xv6的实验指导书，我们可以知道：

xv6中的fork()系统调用将父进程的所有用户空间内存复制到子进程中。如果父进程所使用的页数很大，复制可能需要很长时间，而这样的复制操作经常是没有用的：fork()之后通常是子进程中的exec()，这会丢弃复制的内存而不是使用它们。

那么，我们是不是可以在子进程刚创建时将其页表的映射到父进程的物理页，而在其需要对内存进行写操作时再重新分配内存呢？没错，这就是通过copy on write（写时复制）技术来进行优化。

该实验的代码实现见：仓库commit

大致思路

首先说一下大致思路：

在使用fork系统调用创建子进程时，我们不用去额外拷贝父进程的内存，而是将子进程的虚拟内存映射到和父进程相同的物理内存，并且此时应该将父子进程对这块内存的访问权限设置为只读，并且添加一个用于识别COW（copy on write）的标志：

当子进程需要对内存进行写操作时，RISC-V会检测到这一块物理地址的权限为只写，触发Page Fault，这时我们可以为子进程重新分配一块内存空间（取消之前的映射，分配内存后重新映射至新内存），并将父子进程的对应物理页的识别标志位进行修改，去除cow标志PTE_COW，添加写权限标志PTE_W：

具体实现

COW标志位

首先我们需要为PTE添加一个用于识别COW的标志位，上图展示了PTE的后10位也就是其flags的情况，可以看到第8、9位是保留没有被使用的，那么我们可以用第8位来作为COW的标志位：

1
2
3
// riscv.h

#define PTE_COW (1L << 8)

修改uvmcopy

在xv6的fork系统调用中，子进程拷贝父进程的物理页使用了uvmcopy()函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int
fork(void)
{
  int i, pid;
  struct proc *np;
  struct proc *p = myproc();

  // Allocate process.
  if((np = allocproc()) == 0){
    return -1;
  }

  // Copy user memory from parent to child.
  if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
    freeproc(np);
    release(&np->lock);
    return -1;
  }
  ...
}

那么我们需要修改uvmcopy中的代码，将原先的拷贝内存的操作去掉，并将PTE的只读标志位去除、添加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
30
31
32
33
34
35
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);

	// 这里移除了拷贝的代码，并设置了父进程相应的标志位
    if (flags & PTE_W) {
      *pte = (*pte & ~PTE_W) | PTE_COW;
      flags = (flags & ~PTE_W) | PTE_COW;
    }

	// 将子进程的虚拟页映射至父进程的物理页，同时设置了子进程相应的标志位
    if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
      goto err;
    }

	// 这里是对物理页的引用计数进行+1，后文会说明
    kref_inc((void*)pa);
  }
  return 0;

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

引用计数

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.

当我们采取了cow后，只有当所有虚拟页都没有引用某一物理页时这个物理页才能被释放，那么我们可以使用一个数组来对每一个物理页进行引用计数，当fork导致子进程共享物理页时，对应的物理页的引用计数+1，当有进程不再使用物理页时，对应的物理页的引用计数-1，回收物理页的kfree()函数只有当物理页的引用计数为0时才会将其放回空闲列表。

1
2
3
4
5
6
// kalloc.c

struct {
  struct spinlock lock; // 保证操作的原子性
  int ref_count[(PGROUNDUP(PHYSTOP)) / PGSIZE]; // KERNBASE～PHYSTOP是物理内存的大小，因为xv6的内核地址采用了直接映射，为了方便，这里直接使用PHYSTOP。PHYSTOP / PGSIZE则表示有多少个物理页
} kref;

内核在使用kinit()进行初始化时，需要初始化kref的锁，并设置引用计数数组的值：

1
2
3
4
5
6
7
8
9
10
11
void
kinit()
{
  initlock(&kmem.lock, "kmem");
  initlock(&kmem.lock, "kref");
  // 这里初始化时置为1是为了接下来的freerange在调用kfree时不会触发panic
  for (int i = 0; i < PGROUNDUP(PHYSTOP) / PGSIZE; i++) {
    kref.ref_count[i] = 1;
  }
  freerange(end, (void*)PHYSTOP);
}

在kfree()中对物理页的引用计数来判断是否应该释放物理内存：

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
void
kfree(void *pa)
{
  struct run *r;

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

  // 如果在还未对ref count操作前其值已经小于等于0，说明已有问题
  if (kref.ref_count[(uint64)pa / PGSIZE] <= 0) {
    panic("kref");
  }

  // 每次free一个page时，先将这个page的引用计数-1
  kref_dec(pa);
  // ref count - 1，如果结果还大于0，说明这个物理页还被其他进程引用，暂时不需要释放
  if (kref.ref_count[(uint64)pa / PGSIZE] > 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);
}

每分配一个物理页时，该物理页的引用计数初始为1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
    // 这里赋值为1一定要在设置垃圾数值之后，否则会造成污染
    acquire(&kref.lock);
    kref.ref_count[(uint64)r / PGSIZE] = 1;
    release(&kref.lock);
  }
  return (void*)r;
}

将引用计数的操作封装一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// kalloc.c

// 为pa所在的page的引用+1
void kref_inc(void* pa) {
  acquire(&kref.lock);
  ++kref.ref_count[(uint64)pa / PGSIZE];
  release(&kref.lock);
}

// 为pa所在的page的引用-1
void kref_dec(void* pa) {
  acquire(&kref.lock);
  --kref.ref_count[(uint64)pa / PGSIZE];
  release(&kref.lock);
}

page fault时分配新内存

当需要分配新内存时，要检测虚拟页的cow标志位是否有效。在分配了内存后，拷贝原来的物理页中的数据到新的物理页，并将虚拟页的标志位中的cow去除、添加写标志，最后取消虚拟页与原来物理页的映射关系，同时在解除时对引用计数-1，然后将虚拟页映射至新的物理页：

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
// 当出现page fault时，进行cow操作
int cow_alloc(pagetable_t pagetable, uint64 va) {
  if (va >= MAXVA) {
    return -1;
  }

  if ((va % PGSIZE) != 0) {
    return -1;
  }

  pte_t *pte = walk(pagetable, va, 0);
  if (pte == 0)
    return -1;

  uint64 pa = PTE2PA(*pte);
  if (pa == 0)
    return -1;

  // 当page的cow标志位有效时才会重新分配内存
  if ((*pte & PTE_COW) && (*pte & PTE_V)) {
    char* mem = kalloc();
    if (mem == 0) {
      return -1;
    }
    uint64 flags = PTE_FLAGS(*pte);
    flags = (flags & ~PTE_COW) | PTE_W; // 去除COW标记，加上写权限标记
    memmove(mem, (char *)pa, PGSIZE);
    uvmunmap(pagetable, PGROUNDDOWN(va), 1, 1); // 解除之前的映射，并设置do_free为1，这样在kfree中可来将引用计数-1
    if (mappages(pagetable, va, PGSIZE, (uint64)mem, flags) < 0) {
      panic("cow_alloc");
    }
  }
  return 0;
}

实验指导书提醒我们在copyout()中也要执行cow操作，但这里为何要这么做呢？

这是因为需要内核将数据通过copyout拷贝到用户态时，如果需要拷贝的目标位置是用户进程与其父进程共享的，那么这时应该会有page fault产生，但是copyout中是通过walk遍历页表来获取地址的，不会触发page fault，因此需要我们手动执行cow。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;
  pte_t *pte;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    if(va0 >= MAXVA)
      return -1;
    
    if (cow_alloc(pagetable, va0) < 0) {
      return -1;
    }
    ...
  }
}

usertrap中触发page fault

在之前fork操作时我们去除了物理页的write操作，那么在之后需要对该物理页进行写操作时，risc-v就会触发page fault了。

查看risc-v的手册可以发现：

我们需要使用excepton code 13和15（读写），当发生page fault时，这个code会保存在scause寄存器中，那么我们只需要在usertrap中对scause进行相应的处理即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void
usertrap(void)
{
  ...
  } else if (r_scause() == 13 || r_scause() == 15) {
    // 这里的stval寄存器，我的理解是保存了触发page fault时的虚拟地址
    uint64 fault_va = r_stval();
    // 判断地址是否不合法
    if (fault_va >= MAXVA ||
        (fault_va < p->trapframe->sp &&
         fault_va >= (p->trapframe->sp - PGSIZE)) ||
        fault_va <= 0) {
      p->killed = 1;
    }
    // 尝试进行cow操作
    if (cow_alloc(p->pagetable, PGROUNDDOWN(fault_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());
    setkilled(p);
  }
}

值得注意的是，在进行cow操作之前，一定要对地址的范围进行合法性判断，因为usertests中会有非常多的测试函数，其中有一部分会检测地址合法性，不合法的地址应该直接让进程死亡。