MIT 6.S081 操作系统课程系列5 lazy page allocation

https://pdos.csail.mit.edu/6.828/2020/labs/lazy.html
本次实验需要读xv6手册第4章，主要是4.6缺页异常。看相关kernel代码。
实现lazy分配。

缺页异常

• xv6下，如果异常发生在user空间，kernel会kill异常的进程。
  如果发生在kernel空间，报panic。

• 实用的操作系统通常会有其他操作。很多系统会用缺页异常来实现copy-on-write(COW) fork。
  fork以后子进程会复制一份父进程的内存数据，如果父子能共享这份内存就会更高效，但是直接共享肯定会造成数据混乱。

• copy-on-write fork能通过缺页来实现安全的共享内存。
  当cpu转换虚拟地址到物理地址失败时会产生一个缺页异常。
  riscv有三种缺页异常：

  1. 加载缺页(加载指令无法转换地址)
  2. 存储缺页(存储指令无法转换地址)
  3. 指令缺页(地址无法转换)

• 异常时scause寄存器存了缺页类型，stval存了无法转换的地址。

COW fork

• fork时首先父子进程会共享所有物理内存，但是标记为只读。当父或子发起存储操作，会报缺页异常。
  kernel各复制一份缺页地址的数据(可读可写)到父子进程。
  更新各自页表，回滚到之前导致缺页的指令，再执行一次并继续。

• 这样的COW对fork是实用的，因为子进程通常在fork后马上调用exec，新起地址空间。子进程只会出少数几次缺页，kernel也不用进行整个复制。
  而且COW是透明的，应用程序不用做任何修改。

• 页表和缺页还有其他玩法，比如lazy allocation。

  1. 程序调用sbrk时。kernel扩大地址空间，但不实际分配内存和更新页表。
  2. 当这些地址上出缺页异常时，kernel才实际分配内存并更新页表。
     因为应用程序经常过多地申请内存，所以这样做很实用。

做题

本次实验从sbrk开始做一系列修改，最终实现lazy分配。

1. 如果扩大内存，sbrk的n大于0。去掉growproc，直接更新sz。
2. usertrap(trap.c)里r_scause()为13或15时是缺页异常。r_stval()获取缺页的地址。
3. 缺页时模拟一下growproc的流程，即uvmalloc里，先分配一页内存，再做好映射。
4. uvmunmap里PTE无效时直接continue，不再panic。

到此echo可以正常完成。

5. 如果缩小内存，sbrk的n小于0。走原始的growproc(n)。
6. 如果缺页地址大于进程的sz，设为killed。
7. 缺页分配内存时如果失败，设为killed。
8. fork的uvmcopy里如果PTE无效直接continue，不再panic。

lazytests

测试程序lazytests有三个函数sparse_memory，sparse_memory_unmap，oom。

• sparse_memory
  先分配1G内存，不实际分配，只改sz。
  再挑其中一部分地址写数据。
  再读数据验证是否等于写入的值。

• 执行lazytests会出panic: uvmunmap: walk
  用之前做的backtrace定位为lazytests.c里的run fork并运行sparse_memory后，wait->freeproc->proc_freepagetable->uvmfree->uvmunmap。
  回收子进程页表时walk转换虚拟地址出错，也就是这个虚拟地址没做映射。
  回收页表是按p->sz来的，因为是lazy造成根本没分配内存页没做映射，强行回收就出错了。

• *把这个panic改成continue。可过sparse_memory。**

• sparse_memory_unmap
  出现panic: uvmcopy: page not present
  sparse_memory_unmap先lazy分配1G内存。
  再对部分地址写数据。再对每个写数据的地址i起子进程。子进程sbrk减小1G内存，并对i写数据。
  因为开始分配的1G是假的，所以fork时按sz复制的话，uvmcopy就找不到地址的映射。

• *把panic改为continue即可。**

此时lazytests可过

usertests测试

• sbrkarg写文件失败
  sbrkarg先分配一页内存，open一个文件，再往文件写一页数据。
  跟踪到最后是走了copyin，因为是假的分配，相应的地址没有页表数据，所以copyin的walkaddr返回了0导致整个失败。

• *walkaddr返回0时分配一下内存，做映射，拿到物理地址即可。**

• sbrkarg的pipe测试仍然失败。
  跟踪发现是sys_pipe的copyout失败，跟copyin一样walkaddr失败。

• *跟copyin一样修改即可。**

• 再运行usertests。copyin失败。
  copyin/copyout里不能无脑分配，因为确实会有非法地址的情况，至少得有个简单的保护。

• *可以用p->sz来做限制。**

• 再运行usertests。argptest失败。
  panic: freewalk: leaf
  回收页表时PTE的映射数据没有事先被清除。也就是unmap没做好。

  跟踪代码，fork时uvmcopy复制了17页数据，从0到0x0000000000010000。
  再从sbrk(0) - 1(0x0000000000010fff)读数据，最后readi里用copyout复制数据。
  问题出在copyout里实时分配和映射的边界判断。
  从0x0000000000010fff读超过一页的数据，那么末尾已经超出了进程的sz，这时错误地进行了分配和映射，导致映射了sz以外的地址，那么unmap时就删不掉这个多出来的映射，最后回收页表时就会panic。

• *copyout/copyin里如果va0 >= p->sz就返回-1，不要分配了，这样就不会超出sz。之前用的va0 > p->sz所以出问题。**

• stacktest: panic: remap
  stacktest会读sp指针下面一页地址的数据，这个地址在页表里是没有的，这里不能无脑分配并映射，因为sp以下的地址是不合法的。

• *需要判断一下stack pointer的起始地址(p->trapframe->sp)，小于这个地址的缺页是非法的，设置为killed。**
  这也是课程的最后一个提示。

总结

• lazytests和usertests必须都通过才算完成。
• 需要理解内存分配、页表的原理。
• 理解原理的基础上仔细看代码调代码。
• 看懂测试代码。
• 之前实验做的backtrace非常香 (https://pdos.csail.mit.edu/6.828/2020/labs/traps.html)