cow pages

感觉cow lab是我做的最纠结的lab了，代码量其实非常少，但是就是非常见简单的20~`30行代码，就出了许多莫名奇妙的bug。copy on write page实现原理非常简单，父进程在创建子进程时，子进程只需要将父进程的所有的虚拟地址拷贝`一份即可,此时子进程与父进程共享同样的物理页，子进程和父进程可以同时读取同样的物理页面；当子进程或者父进程需要将数据写回物理页时，则申请一块新的物理页，并将虚拟地址重新映射到新的物理页上。这样实现的好处有两点：

• 可以节省内存，此时子进程与父进程可以有多个进行共享只读的物理页面，从而减少物理内存的使用。
• 可以加快子进程的创建效率，此时子进程不需要再重新申请物理页面，从而可以加快子进程的创建速度。
  在这个lab实现的时候真心遇到各种坑，熬了不少夜，很多莫名奇妙的bug总是出现，可以记录下出现的各种bug。
• 出现page fault，且scause = 2，表示出现了错误的指令。
• 出现page fault,且scause = 12,表示出现了加载页面失败的错误。
• 程序在单核模式下运行正确，但在多核模式下就各种奇怪的问题。
• 程序莫名奇妙出现陷入死循环，卡住不动。
  
  git repo

Implement copy-on write

Your task is to implement copy-on-write fork in the xv6 kernel. You are done if your modified kernel executes both the cowtest and usertests programs successfully.

代码实现的话，总共分为四个部门:

• uvmcopy时，此时我们需要将子进程的页表项中的所有虚拟地址全部映射到父进程的物理页面里面。
• copyout时，此时因为在系统内部调用文件读写时，此时则是通过copy out和copy in来实现的，此时我们则需要判断当前的页面是否为cow page，如果为cow page则需要重新申请物理内存页面，然后重新写入数据。h’t’y’y’y’y’y’y’y’y’y’y’y’y’y’y’y’y’y
• usertrap：在发生写入没有写权限的页面时，就会处罚page fault的trap，此时我们需要申请新的物理页面然后映射到虚拟地址上，然后再次重新执行该指令。
• kalloc: 在进行kalloc和kfree时，我们增加对物理页面内存的引用计数，如果一个物理页面被映射到多个虚拟地址上，则每增加一次映射，则将计数进行增加，每次进行free操作时，我们则将引用进行进行较少，当引用计数为0时，此时我们可以释放该物理页面，并进行回收。

1. usertrap: 添加对trap的处理

   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 call if(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){ uint64 va = r_stval(); if (va >= MAXVA || (va <= PGROUNDDOWN(p->trapframe->sp) && va >= PGROUNDDOWN(p->trapframe->sp) - PGSIZE)) { p->killed = 1; } // 检测pte的flag if (uvmcowalloc(p->pagetable, va) != 0) p->killed = 1; } else{ p->killed = 1; } if(p->killed) exit(-1); // give up the CPU if this is a timer interrupt. if(which_dev == 2) yield(); usertrapret(); }

2. vm：

• 子进程复制时，对物理内存页进行标记

  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); // clear PTE_W and mark the page as cow page. if(flags & PTE_W){ flags = (flags | PTE_COW) & (~PTE_W); *pte = PA2PTE(pa) | flags; } krefinc((void*)pa); if(mappages(new, i, PGSIZE, pa, flags) != 0){ goto err; } } return 0; err: uvmunmap(new, 0, i / PGSIZE, 1); return -1; }

• 检测是否为cow page,如果是cow page则申请新的物理页，加进来。

  int uvmcowalloc(pagetable_t pagetable, uint64 va) { uint64 pa; pte_t *pte; uint flags; if (va >= MAXVA) return -1; va = PGROUNDDOWN(va); pte = walk(pagetable, va, 0); if (pte == 0) return -1; pa = PTE2PA(*pte); if (pa == 0) return -1; flags = PTE_FLAGS(*pte); if (flags & PTE_COW){ flags = (flags & ~PTE_COW) | PTE_W; char *ka = kalloc(); if (ka == 0) return -1; memmove(ka, (char*)pa, PGSIZE); kfree((void*)pa); *pte = PA2PTE((uint64)ka) | flags; return 0; } return 0; }

• copyout:

  int copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len) { uint64 n, va0, pa0; while(len > 0){ va0 = PGROUNDDOWN(dstva); if (uvmcowalloc(pagetable, va0) != 0) return -1; pa0 = 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; }

• kalloc函数处理：

  uint32 krefcount(void *pa){ uint32 ret = 0; acquire(&kmem.lock); ret = kmem.refcount[PA2IDX(pa)]; release(&kmem.lock); return ret; } void krefinc(void *pa){ acquire(&kmem.lock); kmem.refcount[PA2IDX(pa)]++; release(&kmem.lock); } void krefdec(void *pa){ acquire(&kmem.lock); kmem.refcount[PA2IDX(pa)]--; release(&kmem.lock); }

思考总结

• 当我们遇到fork时我们如何处理？
• • 我们依次拷贝父进程的所有虚拟地址空间，同时将子进程的虚拟地址全部隐射到父进程的物理页面，并同时将父进程和子进程的页面全部标记为cow page。假设父进程的页面已经全部都为cow page,则此时我们只需要设置子进程的页面标志即可。
• 当父进程或子进程写cow page时，我们如何处理？
• • 父进程或子进程写cow page时，我们直接申请一个新的物理页，并将虚拟地址映射到新的物理页上即可。
• 引用计数的数组长度？
• • 引用数组，如果直接选择的话，实际上我们可以选择长度为$\frac{PHYSTOP}{4096}$。但是实际上没有必要，实际上我们可以看到大于$kernelbase$以上的高地址位都被内核给占用了，不会分配给用户进程，实际上这些物理页面被分配后，永远不会再被别的进程占用和分配。因此实际上我们的长度可以设定为$\frac{PHYSTOP-KERNELBASE}{4096}$.
• 为什么我们需要处理copy out?
• cow page写入时如何处理？
• • cow page写入时会发生trap，因为此时该物理页并没有写入的标志，此时我们则需要捕获trap，然后进行处理。
• 当cow page被子进程复制时，如何处理?
• • 我们直接进行将地址进行映射。
• 当前cow page的引用计数？
• • 当cow page的reference大于1时，则我们可以知道该页面可能被多个进程映射，则此时我们按照正常的cow page处理即可。
• • 当cow page的reference等于1时，则我们可以知道该页面只被一个进程映射，则此时我们可以还是按照正常的进程申请物理页面然后映射；其实我们还有另一种办法，直接恢复该页面的标记，将该物理页面标记为正常的页面，可读可写即可。
• • 我们进行kfree时，会对引用计数减一操作，引用计数如果大于1时，则我们此时不做任何操作。当reference等于0时，则我们可以知道该页面未被任何一个进程引用，则可以对其进行释放。

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://mikemeng.org/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿