一、什么是copy-on write(写时复制)？

xv6中的fork()系统调用将父进程的所有用户空间内存复制到子进程中*(同样linux 中除pid=1的进程外所有的进程都是fork出来的)*。如果父进程较大，则复制可能需要很长时间。更糟糕的是，这项工作经常造成大量浪费；例如，子进程中的fork()后跟exec()将导致子进程丢弃复制的内存，而其中的大部分可能都从未使用过。另一方面，如果父子进程都使用一个页面，并且其中一个或两个对该页面有写操作，则确实需要复制。

copy-on-write (COW) 的目标是推迟到子进程实际需要物理内存拷贝时再进行分配和复制物理内存页面。

COW只为子进程创建一个页表，用户内存的PTE指向父进程的物理页。COW将父进程和子进程中的所有用户PTE标记为不可写。当任一进程试图写入其中一个COW页时，CPU将强制产生页面错误(page fault)。内核页面错误处理程序检测到这种情况将为出错进程分配一页物理内存，将原始页复制到新页中，并修改出错进程中的相关PTE指向新的页面，将PTE标记为可写。当页面错误处理程序返回时，用户进程将能够写入其页面副本。

COW将使得释放用户内存的物理页面变得更加棘手。给定的物理页可能会被多个进程的页表引用，并且只有在最后一个引用消失时才应该被释放。

我们可以看出来 COW与lazy allocation相似，都是在进程要求分配内存的时候，不实际分配物理地址，等到发生page fault后再进行处理。**page fault是cow与lazy allocation的核心**

二、如何实现copy-on write

1.修改fork()函数

子进程都是由父进程fork而来，想要实现copy-on write，需要我们对fork函数做修改。

原本的fork()函数会将父进程的所有数据都复制到子进程。修改后的fork()函数需要将子进程内存的PTE指向父进程，权限相关的讨论我们之后进行。

修改前的fork函数如下：

修改后的fork函数如下：

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
//fork()函数 从已经存在的进程中创建一个子进程，而原进程称为父进程。fork函数 需要为新子进程生成pid等功能，uvmcopy函数负责将
//父进程的pte所指的值复制给子进程
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  char *mem;

  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((mem = kalloc()) == 0)
      goto err;
    memmove(mem, (char*)pa, PGSIZE);
    if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
      kfree(mem);
      goto err;
    }
  }
  return 0;

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

1.1 子进程如何共享父进程的地址空间？

1.1.1 方法一、复制页表(pagetable)的值

第一种方法，在fork函数新建子进程时，直接将子进程的pagetable值赋值父进程的pagetable值。

这种方法在复制时快速有效，但是存在以下几个问题：

(1).倘若进程2修改物理内存A的数据，为了不影响父进程，父进程对应的物理内存数据不能发生改变。只有进程2从Pagetable开始修改，重新建立level2、level1、level0级页表,B页表指向新的物理内存才可以实现。同时，考虑到内存引用计数机制的需求，该方法无法正确判断一个物理页面的引用计数，因为直接复制了pagetable，没有牵扯到最低级的物理内存。

所以该方法不满足需求。

1.1.2 方法二、仅将最后一级PTE的值指向物理内存

第二种方法，在fork函数新建子进程时，子进程自建完整的页表结构，只将最后一级PTE指向与父进程相同的物理内存。

该方法由于直接涉及到了物理内存，方便加入引用计数机制，同时，当需要向页面写入数据时，只需要修改最低级PTE所指的物理内存即可。

该方法满足需求。

2.权限问题

写时复制将父进程和子进程中的所有用户PTE标记为不可写。当任一进程试图写入其中一个COW页时，CPU将强制产生页面错误。这样做缺少分辨父进程原本有无权限的有限方法，需要我们增加标志位来辅助辨别。

XV6操作系统的权限管理比较简单，没有支持Linux的多用户权限，XV6通过PTE低10位作为Flag标志位来管理权限。

低8位与低9位被保留下来，作为拓展标志位使用。我们可以利用低8位作为COW标志位。

父进程原本拥有对物理内存的写权限，父子进程COW位被设为1.
父进程原本未拥有对物理内存的写权限，父子进程COW位被设为0.

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
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *oldpte;
  pte_t *newpte;
  uint64 pa, i;
  //uint flags;
  //char *mem;

  for(i = 0; i < sz; i += PGSIZE){
    if((oldpte = walk(old, i, 0)) == 0)
      panic("uvmcopy: oldpte should exist");
    if((*oldpte & PTE_V) == 0)
      panic("uvmcopy: oldpage not present");
    pa = PTE2PA(*oldpte);
    //flags=PTE_FLAGS(*oldpte);
    if(*oldpte&PTE_W){
      *oldpte=*oldpte&(~PTE_W);
      *oldpte=*oldpte|PTE_RSW;
      //flags=PTE_FLAGS(*oldpte);
    }

    if((newpte = walk(new, i, 1)) == 0)
      panic("uvmcopy: newpte should exist");
    addpgcnt(PGROUNDDOWN(pa));
    *newpte=*oldpte;
  }
  return 0;
}

3.引用计数

原本的XV6操作系统中，由于fork函数会将父进程的用户空间完全复制到新的物理内存中再映射给子进程。进程在释放物理内存等操作时不需要考虑到其父进程或子进程使用同一物理内存的情况，在增加写时复制机制后，XV6操作系统在处理某进程由于写操作引起的页面错误时必须保证其他进程的正常运行，所以为物理内存增加引用计数是必要的。

需要引用计数辅助决定需要写入数据的进程是否需要额外申请物理内存。

当引用计数大于1时，写入数据的进程需要自己申请一块空闲内存，该内存的数据复制自原本将写入的内存，进程最后一级的PTE指向新分配的物理内存，再进行自己的写入操作。同时旧物理内存的引用数需要减1。

当引用计数等于1时，直接写入数据即可。

引用计数功能的实现

XV6操作系统原本的物理内存分配与回收机制是将将空闲的物理内存地址空间以页(4096个字节)为单位，使用链表结构将页整理起来。进程申请物理内存时，操作系统从链表中取出一个物理内存分配给进程，当进程结束时，操作系统回收页表将其加入空闲链表中。

引用计数功能的实现不需要对原本页表的分配释放机制做出太大的改变：

XV6操作系统参与分配的页表数量是固定的(PHYSTOP/PGSIZE)，使用一个固定大小的数值便可以记录每个页表的引用次数。同时使用自旋锁保证引用计数的互斥性。

1
2
3
4
5
6
struct 
{
  struct spinlock lock;
  int cnt[PHYSTOP/PGSIZE];
} pgcnt;

kalloc原本用于分配空闲页表，修改后额外将cnt(引用计数)设为1值

kfree原本用于释放回收页表，修改后只有当cnt(引用计数)为1时才释放页表，其余情况下只需要将cnt(引用计数)减1即可。

额外增加3个函数，addpgcnt(uint64 pa)将物理内存pa的cnt值加1（该功能用于fork函数子进程共享父进程的物理内存），cntpgcnt(uint64 pa)返回物理内存pa的cnt值。

4.虚拟地址合法范围

在实际的代码编写过程中，我遇到了一个bug：

这一BUG发生的原因经过排查后得到：在Lab5_xv6LazyPageAllocation实验中，为了满足usertest的要求，我在usertrap中加入了对发生错误的虚拟地址合法性检测。

1
2
3
if(p->trapframe->sp>failedva){
      p->killed=1;
}

这段代码将虚拟地址发生在栈指针下的情况视为错误，终止了进程。并且成功通过了测验。

在本实验中我考虑到COW与Lazy Allocation都是利用page fault在中断处理函数usertrap中做文章,并且scause值都相同，皆为13或15，便直接将Lazy Allocation的这段检测代码复制了过来。

实际上：Lazy Allocation是对堆分配做出的优化，并且在之前的实验中并没有涉及对fork函数的修改，通过fork产生的子函数，p->sz值大于等于栈指针是必然的。所以Lazy Allocation假分配虚拟地址报错必然是高于栈指针。

COW对fork函数进行了修改，在0-p->sz的范围内，子进程所有的物理内存都是共享自父进程。所以页面错误(page fault)可能发生在栈指针下，更详细的BUG分析在Lab6 init starting sh bug 原因分析文章中。

实际上虚拟地址的合法范围应该是0~p->sz。