MIT 6.S081 操作系统课程系列6 Copy-on-Write Fork
https://pdos.csail.mit.edu/6.828/2020/labs/cow.html
https://pdos.csail.mit.edu/6.828/2020/xv6/book-riscv-rev1.pdf
https://pdos.csail.mit.edu/6.828/2020/lec/l-usingvm.pdf
本次实验需要读xv6手册第4章，主要是4.6缺页异常。看相关kernel代码。
实现copy on write fork。
原理
- xv6默认的fork，子进程会copy父进程的所有user空间的内存数据。如果父进程数据很多，非常耗时，而且复制出来的数据很可能基本无用。
比如fork以后子进程马上跑一个exec，会扔掉复制来的数据，那么就白白复制，浪费资源。
如果父子都确实用到了某页内存，那么复制才是必要的。 -
copy-on-write (COW) fork推迟子进程的内存复制，直到实际用到某页数据才进行复制。
子进程创建页表，里边的PTE指向父进程的物理内存，不分配新内存(默认流程会分配新内存并复制父进程的数据)。
把父和子进程的user页表PTE都标记为不可写。
当父或子进程写某页时，会报缺页。
缺页处理里边分配物理内存，复制父进程的数据，父子的相关PTE设置为可写。这样完才成了实际的复制，以后各不相关。 -
这样做会给free带来些麻烦，因为多个fork后，可能有多个进程的PTE指向同一个物理地址。
需要对物理地址做引用计数来解决，到最后没有任何进程跟这个物理地址相关时才真正free。
实现
-
需要通过cowtest和usertests
-
cowtest的simpletest会分配2/3内存再fork，默认fork会copy所有内存，直接会失败。
-
从cow分支全新的代码开始。不要用lazy分支的代码。
-
做一个cow fork版本的uvmcopy。清除PTE_W标志位。不分配物理内存，都映射到父的物理内存。
PTE的8/9位是备用的，可以做一个PTE_COW宏，标志是cow页(未分配内存)还是已分配过内存。 -
usertrap()里的r_scause()
13为load page fault，15为store page fault，就是PTE_W导致。见 https://pdos.csail.mit.edu/6.828/2020/lec/l-usingvm.pdf。 -
缺页时需要在进程树里复制和设置数据，要严格安排好逻辑，考虑各种情况。比如多层fork、缺页和fork交错进行等等。
-
如果当前页是PTE_COW，那么当前进程作为子进程来说，得从父进程复制数据。因为本身是直接映射到了父进程的物理内存地址(pa)，所以可以直接分配内存并复制pa数据(不用在树形结构里往上找了)，把原有映射的pa替换为新的pa，清除PTE_COW标志位。
如果当前页不是PTE_COW，那么一定是分配过内存的。不用再从父进程复制数据。 -
当前进程作为父进程来说，缺页意味着数据将要改变，那么必须把它所有的子进程更新为它目前的数据，
想办法找到所有子进程(比如最简单遍历进程表查父id)，分配内存，复制父进程数据，更新映射，清除PTE_COW。
子进程页仍为不可写，当前进程页设为可写。
只需要更新一层子进程即可，不可写标志位可保证更深层的子进程都会拿到fork时的父进程数据。 -
做一个键值存储。物理地址作为健，记录引用次数。128M内存按页索引一共32768个页，直接用数组可以承受。
- 每次kalloc和cow fork做映射时给物理地址的值+1。
- 每次unmap时如果是PTE_COW，引用次数-1，跳过kfree。
- kfree检查计数，为0时真正执行。
- copyout里要判断flag，按缺页一样处理。
其他问题
-
scause为2的异常
可能是pa的计数没做好，把有用的数据free了。 -
copyout问题
cowtest里的filetest读pipe会失败。
看下pipe的创建流程。
file.c里有ftable全局数组，最多存100个文件数据。申请流程filealloc和进程相似，找一个状态为空白的即可。
sys_pipe的pipealloc先申请两个文件，再kalloc一个pipe变量，把pipe绑定到两个文件上。
用fdalloc申请两个fd，绑定到两个文件上。绑定关系在p->ofile里。
再把两个fd的值用copyout复制到user内存。发现sys_read取fd会失败，argfd里打印一下看到对应的p->ofile确实为0。
因为父进程fork后write一下马上进入下个循环，又会创建pipe，覆盖了原来的fd，子进程sleep(1)后fd已被改写，所以p->ofile确实为0。
但是按fork的原理，父进程再次fork时不应该覆盖原来的fd。
因为copyout里不会像user模式那样产生缺页，所以要手动处理。
dstva对齐后得到va0，取pte，如果PTE_W关闭(注意不是PTE_COW。这个错了会折腾很久)，那么对他执行一样的缺页流程即可。从实际pa复制数据，并复制给他所有有需要的子进程。 -
sbrkfail测试卡死
sbrkfail最后会sbrk分配1000M内存，但不判读失败，直接去取数据。
缺页处理我没判断PTE_V，而是直接判断PTE_COW为0就误认为正常返回。造成在这里死循环。
正常sbrk后PTE_V是打开的，那么加上PTE_V判断即可。 -
stacktest测试
会读sp以下的非法地址。
r_scause()为13是普通缺页，地址可能是非法的，判断一下sp指针，如果缺页地址小于sp直接做成killed。
r_scause()为15是我们清掉PTE_W造成的，地址是正常的，不需要判断。
总结
- 调式了大量进程、内存相关代码。对linux系统有了更深的理解。
