MIT 6.S081 2020 Lab6 Copy-on-Write Fork for xv6 个人全流程

---

零、写在前面

可以阅读下 《xv6 book》 的第五章中断和设备驱动。

问题

在 xv6 中，fork() 系统调用会将父进程的整个用户空间内存复制到子进程中。**如果父进程占用的内存较大，复制过程会非常耗时。更糟糕的是，这种复制往往是浪费的。**例如，在子进程中调用 fork() 后紧接着执行 exec()，会导致子进程丢弃复制来的内存，很可能其中大部分根本没有被使用。另一方面，如果父子进程都使用了某个页面，并且有一个或两个要写这个页面，那就确实需要进行复制。

解决方案

**写时复制（COW）**的 fork() 目标是推迟为子进程分配和复制物理内存页面，直到它们真的被需要（如果有的话）。

COW 的 fork() 仅为子进程创建一个页表，其中用户内存的页表项（PTE）指向父进程的物理页面。COW 的 fork() 会将父子进程中所有用户页面的页表项标记为不可写（即清除可写标志）。当任一进程尝试写这些 COW 页面时，CPU 会触发一个缺页异常（page fault）。内核的缺页异常处理程序会识别出这是 COW 的情况，为发生异常的进程分配一个新的物理页面，复制原页面的内容，然后修改该进程的页表项指向新页面，并将其标记为可写。异常处理程序返回后，用户进程就可以写这个新复制的页面了。

COW 的 fork() 也让用户内存的物理页面释放变得更复杂。因为一个物理页面可能会被多个进程的页表引用，只有当最后一个引用消失时，该页面才能被释放。

我们发现 COW 和 Lazy alloc 的思想其实是类似的。

记得切换到 cow 分支

---

一、Implement copy-on write

1.1 说明

你的任务是：在 xv6 内核中实现写时复制的 fork()。当你的内核能够成功执行 cowtest 和 usertests 这两个程序时，说明你完成了任务。

官网推荐的实现步骤：

1. 修改 uvmcopy()，不要为子进程分配新页面，而是将父进程的物理页面映射到子进程中。清除父子两者对应页表项中的 PTE_W（可写标志）。

2. 修改 usertrap() 以识别缺页异常。如果在 COW 页面上发生缺页异常，则使用 kalloc() 分配一个新页面，将原页面内容复制过去，并在当前进程的页表中安装新页面，并设置 PTE_W。

3. 确保物理页面只在最后一个引用消失时才释放。你可以为每个物理页面维护一个“引用计数”，记录有多少个用户页表引用了该页面。

   • 当 kalloc() 分配页面时，将引用计数设为 1。
   • 当 fork() 让子进程共享页面时，将引用计数加 1。
   • 每当进程从页表中移除页面时，引用计数减 1。
   • 只有当引用计数为 0 时，kfree() 才能将页面放回空闲列表。
   • 可以用一个定长的整数数组来存储这些引用计数。你需要设计如何为页面选择索引以及数组大小。例如，你可以用页面物理地址除以 4096 作为索引，数组元素个数可以设为 kalloc.c 中 kinit() 放入空闲列表的最高物理地址除以 4096。

4. 修改 copyout()，当遇到 COW 页面时，采用和处理缺页异常一样的方案进行处理。

官网的一些提示：

• 懒惰分配实验应该让你对实现 COW 所需的 xv6 代码已有一定了解。但请不要在本实验中基于你之前懒惰分配实验的实现，而是从一个全新的 xv6 拷贝开始。
• 你可以使用 RISC-V 页表项中的 RSW（软件保留位）来记录每个 PTE 是否为 COW 映射。
• usertests 测试了一些 cowtest 没有覆盖的情况，所以一定要确保两个测试都能通过。
• 有用的页表标志宏和定义可以在 kernel/riscv.h 文件末尾找到。
• 如果在处理 COW 缺页异常时没有可用内存，应该终止对应进程。

1.2 实现

官网给出的步骤其实已经让我们有一个较为清晰的思路了，下面直接实现就行了。

实现逻辑分为两部分：

• 延迟复制与释放
• 写时复制

1.2.1 延迟复制与释放

• 首先在 kalloc.c 中添加一个结构体保存每个页面的引用计数
• 为了保证并发安全，我们额外添加一个自旋锁
• 为了方便，提供一个 宏 用于计算引用计数数组索引，这也是官网给出的 页面物理地址除以 4096 作为索引 的方法

// get cnt Array index
#define PA2IDX(p) (((uint64)(p)) / PGSIZE)struct {struct spinlock lock; // spinlock to ensure concurrency safetyint refCnt[PHYSTOP / PGSIZE]; // page ref cnt array
} pageRef;

在 kinit 中新增一行 pageRef 自旋锁的初始化

void
kinit()
{initlock(&kmem.lock, "kmem");initlock(&pageRef.lock, "pageRef"); // initialize the lock for pageReffreerange(end, (void*)PHYSTOP);
}

在 kalloc 中 对新增页面的引用计数初始化为1

void *
kalloc(void)
{// ...if(r) {memset((char*)r, 5, PGSIZE); // fill with junkpageRef.refCnt[PA2IDX(r)] = 1;}return (void*)r;
}

然后修改 kfree 的逻辑为只有当引用计数减为0 时才释放

// 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");acquire(&pageRef.lock); // acquire the lock for pageRef// not referred nowif(--pageRef.refCnt[PA2IDX(pa)] <= 0) {memset(pa, 1, PGSIZE);    // fill with junkr = (struct run*)pa;acquire(&kmem.lock);r->next = kmem.freelist;kmem.freelist = r;release(&kmem.lock);    }release(&pageRef.lock);
}

• 我们还要添加新增引用计数的逻辑
• 以及物理页面复制的逻辑，以便后面调用
• 记得在defs.h添加声明WWWWW
  • 

// if clone is needed
void *kTry_pgclone(void *pa) {acquire(&pageRef.lock);// if it only belongs to meif(pageRef.refCnt[PA2IDX(pa)] <= 1) {release(&pageRef.lock);return pa;}// apply for a new pageuint64 newpa = (uint64)kalloc();if(newpa == 0) {release(&pageRef.lock);return 0;}// copy old data to new onememmove((void*)newpa, (void*)pa, PGSIZE);// refCnt of old page decpageRef.refCnt[PA2IDX(pa)]--;release(&pageRef.lock);return (void*)newpa;
}// inc the refCnt
void kparef_inc(void *pa) {acquire(&pageRef.lock);pageRef.refCnt[PA2IDX(pa)]++;release(&pageRef.lock);
}

• 然后就可以修改 vm.c 中的uvmcopy的复制操作 改为该物理页面的引用次数+1
• 以及为子进程新建页表

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);if (*pte & PTE_W) {*pte = (*pte & ~PTE_W) | PTE_COW;}flags = PTE_FLAGS(*pte);// create pte for son processif(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){goto err;}kparef_inc((void*)pa);}return 0;err:uvmunmap(new, 0, i / PGSIZE, 1);return -1;
}

1.2.2 写时复制

即然要延迟写操作，那么在缺页异常的时候我们就需要知道这些页面是否是 写时复制的共享页面，官网也是提醒我们，可以用 PTE 的保留位来标记。

• 我们为COW 的缺页错误编写一个辅助函数
• 复制一个新页面
• 设置为可写，取消 COW标记
• 取消旧页面映射，添加新映射
• 记得在 defs.h 中添加声明
  • 

int cow_Helper(pagetable_t pagetable, uint64 va)
{pte_t *pte;// get pte for vaif((pte = walk(pagetable, va, 0)) == 0)panic("uvmcowcopy: walk");uint64 pa = PTE2PA(*pte);uint64 newpa;// clone pageif((newpa = (uint64)kTry_pgclone((void*)pa)) != 0){// set PTE_W and unset PTE_COWuint64 flags = (PTE_FLAGS(*pte) | PTE_W) & ~PTE_COW;// unmap but do not free uvmunmap(pagetable, PGROUNDDOWN(va), 1, 0);// map to new pgif(mappages(pagetable, va, 1, newpa, flags) == -1) {panic("uvmcowcopy: mappages");}return 0;}return -1;
}

• 然后修改copyout 的逻辑
• 如果发现是 cow 页面，就调用 cow_Helper() 来处理。

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{uint64 n, va0, pa0;pte_t *pte;struct proc *p = myproc();while(len > 0){va0 = PGROUNDDOWN(dstva);// cowif(va0 < p->sz && (pte = walk(pagetable, va0, 0))!=0 && *pte & PTE_V&& *pte & PTE_COW)cow_Helper(pagetable,va0);// ...
}

• 以及usertrap 逻辑的修改
• 针对 我们写时复制的页面错误单独处理

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 callif(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() == 13 || r_scause() == 15){pte_t *pte;uint64 va = r_stval();// is va valid?if (va >= p->sz)exit(-1);pte = walk(p->pagetable, va, 0);// valid and cow ?if (pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_COW) == 0)exit(-1);// copy on write for cow pgif (cow_Helper(p->pagetable, va) == -1) {exit(-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();
}

测试一下：

cowtest:

usertest:

官网还是写的太详细了（bushi

p->killed = 1;
}

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

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

usertrapret();
}

**测试一下：****cowtest:**[外链图片转存中...(img-TxytPoKI-1748706565978)]**usertest:**[外链图片转存中...(img-kelfELYU-1748706565978)]官网还是写的太详细了（bushi