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可以正常完成。

  1. 如果缩小内存，sbrk的n小于0。走原始的growproc(n)。

  2. 如果缺页地址大于进程的sz，设为killed。

  3. 缺页分配内存时如果失败，设为killed。

  4. 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)