前言
虚拟内存提供某种间接援用：内核能够通过将PTE标记为有效或只读来截获内存援用，从而导致页面谬误，也能够通过批改PTE来更改地址含意。计算机系统中有一个说法：任何零碎问题都能通过某种间接援用来解决。本试验探讨了一个示例：copy-on-write(COW)fork
问题
xv6中的fork()syscall复制父过程所有用户空间的内存到子过程中。如果父过程很大，这个拷贝过程就会花很长时间。更蹩脚的是，这个拷贝常常被节约：fork()函数后子过程通常追随一个exec()，这会抛弃复制的内存、通常不应用大部分内存。另一方面，若父子过程其中一个或都写入了这个复制的页面，则这个拷贝过程是须要的。
解决方案
你在实现COW fork()过程中的指标是，推延开拓空间和拷贝物理内存页直到真正须要这些拷贝时。COW fork()仅为子过程创立一个页表，其中用于用户内存的PTE指向父过程物理页。COW fork()将父子过程所有用户PTE都标记为只读。当任一过程尝试写入这些 COW 页之一时，CPU 将强制呈现页谬误。内核页面谬误处理程序检测到这种状况，为谬误过程调配一页物理内存，将原始页面复制到新页面中，并在谬误过程中批改相干 PTE 以援用新页面，这次 PTE 标记为可写。当页面谬误处理程序返回时，用户过程将可能写入其页面正本。
COW fork()使开释实现用户内存的物理页面变得更加辣手。给定的物理页可能由多个过程的页表援用，并且仅当最初一个援用隐没时才应开释。在像 xv6 这样的简略内核中，这种相当简略，但在生产内核中，这可能很难正确。例如，Patching until the COWs come home.
要求
在xv6内核中实现copy-on-write fork。
为帮忙你的实现，咱们曾经提供了一个程序指令cowtest（源码在user/cowtest.c）。cowtest运行各种测试，但如果过没有更改xv6即使第一个测试也会失败。
这个“简略的”测试开拓超过一半的可用物理内存，而后fork()s。个别状况下，fork会因为没有足够的闲暇物理内存给子过程一个残缺的拷贝而失败。
当你实现后，该当通过cowtest usertests -q的所有测试。
正当的attack打算
- 批改
uvmcopy()以将父级的物理页面映射到子级，而不是调配新页面。革除子级和父级的 PTE 中已被置位PTE_W的PTE_W位。 - 批改
usertrap()以辨认页面谬误。当最后可写的 COW 页面上产生写入页面谬误时，应用kalloc()调配一个新页面，将旧页面复制到新页面，并在被置位为PTE_W的 PTE 中装置新页面。最后为只读的页面（未映射PTE_W，如文本段中的页面）应放弃只读并在父过程和子过程之间共享; 尝试编写此类页面的过程应该被kill()。 - 确保每个物理页在最初一个 PTE 援用隐没时被开释--但不是之前。执行此操作的一个好办法是为每个物理页面保留援用该页面的用户页表数量的“援用计数”。将页面的援用计数设置为 1 当
kalloc()调配它时。当 fork 导致子级共享页面时，递增页面的援用计数，并在每次任何过程从其页表中删除页面时递加页面的计数。kfree()应该只在援用计数为零时将页面放回自在列表。能够将这些计数保留在固定大小的整数数组中。您必须制订一个如何索引数组以及如何抉择其大小的计划。例如，你能够用页面的物理地址除以 4096 来索引数组，并为数组提供一个数字，这个数等于kalloc.c中的kinit()搁置在闲暇列表中的任何页面的最高位物理地址。能够随便批改kalloc.c（例如kalloc(), kfree()）来保护援用计数。 - 批改
copyout()以在遇到 COW 页面时应用与页面谬误雷同的计划。
提醒
- 记录每个PTE是否是COW映射会很有用。为此，你能够应用RISC-V PTE的RSW（软件预留）置位。
- 无关页表flags的一些有用的宏和定义位于
kernel/riscv.h开端。 - 若产生一个COW页面谬误且内存不够，则该过程该当被
kill
实现
复制页表但推延复制页表内容：依据提醒，我从
fork()中调用的uvmcopy()动手。uvmcopy()本来的作用是：把父过程页表中每个PTE所指内容都拷贝到新开拓的空间内并在子过程的页表上造成映射。当初须要把开拓空间这一步去掉，间接在子页表造成映射，然而要扭转flags。为了让代码难看点、放弃逻辑清晰，我创立一个新函数cow_uvmcopy()并在uvmcopy()中调用它。新函数根本与老函数保持一致，不过去掉开拓空间、加上扭转flags：int cow_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); // 扭转flags // *pte = (*pte & (~PTE_W)) | PTE_C; // 错的！（后续阐明） if (*pte & PTE_W) { // 把父过程PTE的PTE_W地位0，再加上PTE_C位 *pte = (*pte & (~PTE_W)) | PTE_C; } // 间接将父过程物理地址在子过程页表中建设映射 if(mappages(new, i, PGSIZE, (uint64)pa, PTE_FLAGS(*pte)) != 0) { goto err; } increaseReference(pa); // 援用计数+1（后续阐明） } return 0;err: uvmunmap(new, 0, i / PGSIZE, 1); return -1;}无关flags的设置：首先要把父子过程的
PTE_W给去掉，这样能力在未来触发page fault。而后就是加上对于cow的标记，须要在riscv.h中自定义，能够定义在预留位上（详见Lab3 page tables）#define PTE_C (1L << 8)。未来可通过该bit位判断是本来就不可读的还是cow机制强加的不可读。更改trap以碰到page fault时开拓空间拷贝内容：依据题目给的计划第2点，须要在
usertrap()中辨认须要cow的page fault状况，开拓空间并拷贝，而后扭转只读的权限置位进而使程序可能写入指定内存。usertrap()自身就算一个抉择构造，比方当产生零碎调用时，通过r_scause() == 8进入syscall分支调用syscall()。因而此处只须要增加一个else if分支来解决page fault- 对于辨认须要cow的page fault状况：其实在2020年的课程中，本试验前边还有一个试验[Lab: xv6 lazy page allocation
](https://pdos.csail.mit.edu/6.828/2020/labs/lazy.html)，其中给出了对于辨认page fault的提醒
r_scause() == 13 || r_scause() == 15（也能够只判断15时，13代表读，15代表写）。具体实现。因为
copyout也须要解决此状况，因而把业务逻辑代码放入函数封装if (...) { // 其余状况 ...} else if (r_scause() == 13 || r_scause() == 15) { // page fault状况 // 页面谬误, 调配空间并拷贝 // 在walkaddr函数实现状况判断和调配空间并拷贝的业务 if (cow_walkaddr(p->pagetable, r_stval()) == 0) { goto error; //解决失败或遇到并非cow的page fault} else {error: // 该分支通过打印信息而后kill掉过程来解决未知中断状况， //对于不须要cow的page fault状况可设置标签将其跳转到此处 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_walkaddr()。参考walkaddr()函数（通过给定page table和虚拟地址返回物理地址，失败返回0）。cow_walkaddr()逻辑是：通过给定page table和虚拟地址，若非cow状况则象walkaddr()一样返回物理地址；若是cow状况，则开拓新空间、拷贝内存、接触旧的只读映射、建设新的可写映射。uint64 cow_walkaddr(pagetable_t pagetable, uint64 va) { pte_t *pte; uint64 pa; int flags; if(va >= MAXVA) return 0; pte = walk(pagetable, va, 0); // 虚拟地址对应PTE if (pte == 0) return 0; else if ((*pte & PTE_V) == 0) return 0; else if ((*pte & PTE_U) == 0) return 0; pa = PTE2PA(*pte); flags = PTE_FLAGS(*pte); if (flags & PTE_W) return pa; // 若有PTE_W阐明不是cow else if ((flags & PTE_C) == 0) return 0; // 判断是否带PTE_C void* new_mem = kalloc(); // 新页面空间 if (new_mem == 0) return 0; memmove(new_mem, (const void*)pa, PGSIZE); // 拷贝页面空间 uvmunmap(pagetable, PGROUNDDOWN(va), 1, 1); // 解除map并开释空间 flags = (flags | PTE_W) ^ PTE_C; // 新flags // 建设新map if (mappages(pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)new_mem, flags) != 0) { kfree(new_mem); return 0; } return (uint64)new_mem;}
内存空间援用计数：依据提醒可知基本思路是：对每个物理内存都标记一个数字示意该内存被援用次数，当
kalloc()的时候置1，每次fork和copyout的时候+1；而kfree()的时候先将该数字-1，而后判断只有当该数字为0的时候才真正开释该内存。由此，在新文件
ref_cnt.c中实现援用次数保留、援用次数减少缩小性能。// ref_cnt.c#include "types.h"#include "memlayout.h"#include "riscv.h"#include "defs.h"#include "spinlock.h"static int ref_cnts[PHYSTOP / 4096]; // 依据提醒设置数组大小// 因为波及并发的共享内存问题，因而须要// 能够应用一个锁。// 但实际上每个援用计数之间并没有抵触，因而也能够离开应用锁static struct spinlock locks[PHYSTOP / 4096];void increaseReference(uint64 pa) { uint64 idx = (pa) / 4096; acquire(locks + idx); ++ref_cnts[idx]; release(locks + idx);}int decreaseReference(uint64 pa) { int ret; uint64 idx = (pa) / 4096; acquire(locks + idx); ret = --ref_cnts[idx]; release(locks + idx); if (ret < 0) { // 排除援用计数为正数的状况 panic("reference count: -1"); } return ret;}别忘了在
defs.h中申明函数- 援用计数初始化：
kalloc()须要将援用计数置1。因为没应用的内存援用计数为0，因而这里间接采纳减少的形式初始化。 - 援用计数减少：在刚
fork()后父子过程共享内存时，内存实际上被援用2次。具体该当在fork()复制父页表到子页表（间接与父过程物理地址建设映射）时减少援用计数。即在cow_uvmcopy()中，映射建设胜利后调用increaseReference()。(前边已有标记) 援用计数缩小：依据提醒，在
kfree()中先缩小援用次数、再判断是否须要真的开释——即在kfree()结尾退出系列命令：void kfree(void *pa) { // 将援用计数-1并判断以后援用计数是否为0 // 若大于0则间接返回函数 if (decreaseReference((uint64)pa) > 0) return; ...}其余：实际上xv6在初始化时会先
kfree()一波，这时候所有援用计数都还是0，kfree的时候会产生援用计数为-1的谬误状况，因而可将所有援用计数初始化为1或初始调用kfree()前先将援用计数+1：在kalloc.c的kinit()中初始化内存，调用freerange()来kfree内存，因而在freerange()中的kfree()之前加increaseReference():void freerange(void *pa_start, void *pa_end) { char *p; p = (char*)PGROUNDUP((uint64)pa_start); for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) { increaseReference((uint64)p); kfree(p); }}
在
copyout()中增加同样的解决：int copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len) { uint64 n, va0, pa0; while(len > 0){ va0 = PGROUNDDOWN(dstva); // pa0 = walkaddr(pagetable, va0); // 之前曾经封装好函数，这里只须要把walkaddr换成cow_walkaddr pa0 = cow_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;}
遇到的问题
- panic: reference count = -1（援用计数为-1）
最开始跑的时候连第一个都过不去，就报这个援用计数-1（本人设置的）的panic。想了半天反馈过去：因为我依照提醒程序，先写了cow_uvmcopy()实现页表复制，再写援用计数，以至于再复制页表的时候忘加援用计数递增了。因而在cow_uvmcopy()中加上援用计数递增就解决了。 textwrite failed
这个谬误不是很显著。在过了所有cowtest的同时，还过了大部分usertests。只有到这个textwrite的时候才呈现谬误，对应了调试实践中bug-error-failure过程中兴许会差很多个状态转移。又试了又想了半天，才搞明确bug，其实在提醒2中也有提醒：将本来可写的PTE设为不可写，而后触发谬误；然而对于本来就不可写的，就要统一放弃父子过程共享，不能cow。
我最后写cow_uvmcopy()的时候没有思考这一点，间接用*pte = (*pte & (~PTE_W)) | PTE_C;一刀切地把PTE的PTE_W去掉（因为感觉没有PTE_W的PTE这一步也没影响）而后加上PTE_C位（然而这一步就产生很大影响）。退出cow机制后，在试图写入不可写内存时有两种状况：（1）触发cow机制，须要开拓新内存拷贝...（2）这个内存本来就不可写，这时候是真的page fault。而我一刀切的办法，将本来不可写的内存也加上了PTE_C位，就无奈判断出第（2）种状况了，后果全是第（1）种。因而，通过退出判断本来的PTE是否可写再去扭转置位就能防止这种状况：if (*pte & PTE_W) { // 把父过程PTE的PTE_W地位0，再加上PTE_C位 *pte = (*pte & (~PTE_W)) | PTE_C;}
后果
- 运行后果
- 测试后果
总结
- 通过该试验对COW机制的基本原理有了意识和了解，也感叹计算机前辈们可能思考出并实现该机制的厉害！
- C++智能指针援用计数用法也可间接在内存上应用！
- 对创立过程有了更深刻的了解！