Lab5: xv6 lazy page allocation

Lab5: xv6 lazy page allocation

这个实验相对其他实验来说还是较为简单的，再加上老师上课直接演示了一半，所以这里直接放操作了

操作系统可以使用页表硬件的技巧之一是延迟分配用户空间堆内存（lazy allocation of user-space heap memory）。Xv6应用程序使用sbrk()系统调用向内核请求堆内存。在我们给出的内核中，sbrk()分配物理内存并将其映射到进程的虚拟地址空间。内核为一个大请求分配和映射内存可能需要很长时间。例如，考虑由262144个4096字节的页组成的千兆字节；即使单独一个页面的分配开销很低，但合起来如此大的分配数量将不可忽视。此外，有些程序申请分配的内存比实际使用的要多（例如，实现稀疏数组），或者为了以后的不时之需而分配内存。为了让sbrk()在这些情况下更快地完成，复杂的内核会延迟分配用户内存。也就是说，sbrk()不分配物理内存，只是记住分配了哪些用户地址，并在用户页表中将这些地址标记为无效。当进程第一次尝试使用延迟分配中给定的页面时，CPU生成一个页面错误（page fault），内核通过分配物理内存、置零并添加映射来处理该错误。您将在这个实验室中向xv6添加这个延迟分配特性。

Eliminate allocation from sbrk() (easy)

你的首项任务是删除sbrk(n)系统调用中的页面分配代码（位于***sysproc.c***中的函数sys_sbrk()）。sbrk(n)系统调用将进程的内存大小增加n个字节，然后返回新分配区域的开始部分（即旧的大小）。新的sbrk(n)应该只将进程的大小（myproc()->sz）增加n，然后返回旧的大小。它不应该分配内存——因此您应该删除对growproc()的调用（但是您仍然需要增加进程的大小！）。

试着猜猜这个修改的结果是什么：将会破坏什么？

进行此修改，启动xv6，并在shell中键入echo hi。你应该看到这样的输出：

init: starting sh
$ echo hi
usertrap(): unexpected scause 0x000000000000000f pid=3sepc=0x0000000000001258 stval=0x0000000000004008
va=0x0000000000004000 pte=0x0000000000000000
panic: uvmunmap: not mapped

“usertrap(): …”这条消息来自***trap.c***中的用户陷阱处理程序；它捕获了一个不知道如何处理的异常。请确保您了解发生此页面错误的原因。“stval=0x0..04008”表示导致页面错误的虚拟地址是0x4008。

过于简单，lec8上课演示过

uint64
sys_sbrk(void)
{int addr;int n;if(argint(0, &n) < 0)return -1;addr = myproc()->sz;myproc()->sz += n;//if(growproc(n) < 0)//  return -1;return addr;
}

Lazy allocation (moderate)

YOUR JOB

修改trap.c中的代码以响应来自用户空间的页面错误，方法是新分配一个物理页面并映射到发生错误的地址，然后返回到用户空间，让进程继续执行。您应该在生成“usertrap(): …”消息的printf调用之前添加代码。你可以修改任何其他xv6内核代码，以使echo hi正常工作。

提示：

• 你可以在usertrap()中查看r_scause()的返回值是否为13或15来判断该错误是否为页面错误
• stval寄存器中保存了造成页面错误的虚拟地址，你可以通过r_stval()读取
• 参考***vm.c***中的uvmalloc()中的代码，那是一个sbrk()通过growproc()调用的函数。你将需要对kalloc()和mappages()进行调用
• 使用PGROUNDDOWN(va)将出错的虚拟地址向下舍入到页面边界
• 当前uvmunmap()会导致系统panic崩溃；请修改程序保证正常运行
• 如果内核崩溃，请在***kernel/kernel.asm***中查看sepc
• 使用pgtbl lab的vmprint函数打印页表的内容
• 如果您看到错误“incomplete type proc”，请include“spinlock.h”然后是“proc.h”。

如果一切正常，你的lazy allocation应该使echo hi正常运行。您应该至少有一个页面错误（因为延迟分配），也许有两个。

修改usertrap

else if (r_scause() == 13 || r_scause() == 15) {
     // 参考课程的例子,注意判断是否合法(例子没有)uint64 va = r_stval();uint64 ka = (uint64)kalloc();if (ka == 0) {
    p->killed = 1;}else if(isValid(p, va) == 0) {
    kfree((void*)ka);p->killed = 1;}else {
    memset((void*)ka, 0, PGSIZE);va = PGROUNDDOWN(va);if (mappages(p->pagetable, va, PGSIZE, ka, PTE_U | PTE_R | PTE_W) != 0) {
    kfree((void*)ka);p->killed = 1;}}} // 判断va地址是否合法，如果va大于sz或者当虚拟地址比进程的用户栈还小，则不合法。
int isValid(struct proc *p, uint64 va) {
    uint64 stackbase = PGROUNDDOWN(p->trapframe->sp);if (va >= p->sz || (va < stackbase)) return 0;return 1;
}

修改uvmunmap()

for(a = va; a < va + npages*PGSIZE; a += PGSIZE){ // 某页为分配不报错，跳过if((pte = walk(pagetable, a, 0)) == 0)//panic("uvmunmap: walk");continue;if((*pte & PTE_V) == 0)//panic("uvmunmap: not mapped");continue;if(PTE_FLAGS(*pte) == PTE_V)panic("uvmunmap: not a leaf");if(do_free){uint64 pa = PTE2PA(*pte);kfree((void*)pa);}*pte = 0;}

Lazytests and Usertests (moderate)

我们为您提供了lazytests，这是一个xv6用户程序，它测试一些可能会给您的惰性内存分配器带来压力的特定情况。修改内核代码，使所有lazytests和usertests都通过。

• 处理sbrk()参数为负的情况。
• 如果某个进程在高于sbrk()分配的任何虚拟内存地址上出现页错误，则终止该进程。
• 在fork()中正确处理父到子内存拷贝。
• 处理这种情形：进程从sbrk()向系统调用（如read或write）传递有效地址，但尚未分配该地址的内存。
• 正确处理内存不足：如果在页面错误处理程序中执行kalloc()失败，则终止当前进程。
• 处理用户栈下面的无效页面上发生的错误。

如果内核通过lazytests和usertests，那么您的解决方案是可以接受的：

$ lazytests
lazytests starting
running test lazy alloc
test lazy alloc: OK
running test lazy unmap...
usertrap(): ...
test lazy unmap: OK
running test out of memory
usertrap(): ...
test out of memory: OK
ALL TESTS PASSED
$ usertests
...
ALL TESTS PASSED
$

处理sbrk()为负数，减少相应的内存，就是dealloc相应的内存n，注意n不能大于p->sz

uint64
sys_sbrk(void)
{
    int addr;int n;if(argint(0, &n) < 0)return -1;struct proc* p = myproc();addr = p->sz;if (n < 0){
    if (p->sz + n < 0) return -1;else uvmdealloc(p->pagetable, p->sz, p->sz + n);}p->sz += n;//if(growproc(n) < 0)// return -1;return addr;
}

修改fork()，正确处理父到子内存拷贝

在fork时会调用uvmcopy复制一份父进程的内存，在lazy allocation中可能0->sz中有部分没有真正分配，在uvmcopy中就会导致panic。累次uvmunmap，修改uvmcopy使得在页面不存在时跳过这一页。

for(i = 0; i < sz; i += PGSIZE){if((pte = walk(old, i, 0)) == 0)//panic("uvmcopy: pte should exist");continue;if((*pte & PTE_V) == 0)//panic("uvmcopy: page not present");continue;pa = PTE2PA(*pte);flags = PTE_FLAGS(*pte);if((mem = kalloc()) == 0)goto err;memmove(mem, (char*)pa, PGSIZE);if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){kfree(mem);goto err;}}return 0;

处理第4种情况，即系统调用（比如write）传入的虚拟地址对应的内存并没有被分配。
首先搞清楚函数执行流程，在调用write后系统trap到内核态，执行copyin来把用户程序va处的内容复制到内核空间，此时若va处并未分配内存，walkaddr会返回0导致系统调用失败。因此我们要做的就是在walkaddr中分配内存。

在walkadress里修改即可

#include "spinlock.h" // 引用头文件proc.h  的时候还要引用 spinlock.h
#include "proc.h"uint64
walkaddr(pagetable_t pagetable, uint64 va)
{pte_t *pte;uint64 pa;struct proc *p = myproc();if(va >= MAXVA)return 0;pte = walk(pagetable, va, 0);if(pte == 0 || (*pte & PTE_V) == 0) {uint64 ka = (uint64)kalloc();if (ka == 0) {return 0;}else if (isValid(p, va) == 0) {kfree((void*)ka);              //注意这里也要kfree，不然会导致内存泄漏return 0;}else {memset((void*)ka, 0, PGSIZE);if (mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, ka, PTE_U | PTE_R | PTE_W) != 0) {kfree((void*)ka);return 0;}return ka;}}if((*pte & PTE_U) == 0)return 0;pa = PTE2PA(*pte);return pa;
}

lazytests starting
running test lazy alloc
test lazy alloc: OK
running test lazy unmap
test lazy unmap: OK
running test out of memory
test out of memory: OK
ALL TESTS PASSED
...
test sbrkarg: OK
test validatetest: OK
test stacktest: OK
test opentest: OK
test writetest: OK
test writebig: OK
test createtest: OK
test openiput: OK
test exitiput: OK
test iput: OK
test mem: OK
test pipe1: OK
test preempt: kill... wait... OK
test exitwait: OK
test rmdot: OK
test fourteen: OK
test bigfile: OK
test dirfile: OK
test iref: OK
test forktest: OK
test bigdir: OK
ALL TESTS PASSED

完成！