课程地址:https://pdos.csail.mit.edu/6.S081/2020/schedule.html
Lab 地址:https://pdos.csail.mit.edu/6.S081/2020/labs/lazy.html
我的代码地址:https://github.com/Amroning/MIT6.S081/tree/lazy
xv6手册:https://pdos.csail.mit.edu/6.S081/2020/xv6/book-riscv-rev1.pdf
相关翻译:http://xv6.dgs.zone/labs/requirements/lab5.html
参考博客:https://www.cnblogs.com/weijunji/p/14338483.html
Lab5: xv6 lazy page allocation
上一章的笔记中稍微提到一点的惰性分配,这次实验就来研究一下利⽤缺⻚故障实现内存分配的惰性分配策略,以及惰性分配有哪些优缺点。
用户态程序通过sbrk
系统调用来在堆上分配内存,而sbrk
则会通过kalloc
函数来申请内存页面,之后将页面映射到页表当中。当申请小的空间时,这个过程是没有问题的。但是如果当进程一次申请很大的空间,如数GB的空间,再使用上述策略来一页页地申请映射的话就会非常的慢(1GB/4KB=262,144)。这时候就引入了lazy allocation技术,当调用sbrk
时不进行页面的申请映射,而是仅仅增大堆的大小,当实际访问页面时,就会触发缺页异常,此时再申请一个页面并映射到页表中,再次执行触发缺页异常的代码就可以正常读写内存了。
通过lazy allocation技术,就可以将申请页面的开销平摊到读写内存当中去,在sbrk
中进行大量内存页面申请的开销是不可以接受的,但是将代价平摊到读写操作当中去就可以接受了。
Lab
仅复制部分题目,完整要求请去该帖子顶部链接查看
Eliminate allocation from sbrk() (easy)
你的首项任务是删除
sbrk(n)
系统调用中的页面分配代码(位于sysproc.c中的函数sys_sbrk()
)。sbrk(n)
系统调用将进程的内存大小增加n个字节,然后返回新分配区域的开始部分(即旧的大小)。新的sbrk(n)
应该只将进程的大小(myproc()->sz
)增加n,然后返回旧的大小。它不应该分配内存——因此您应该删除对growproc()
的调用(但是您仍然需要增加进程的大小!)。
实现lazy page allocation
的第一步,只记录分配了多少内存,但是不做实际的分配。
改动系统调用sys_sbrk
,不再调用分配内存的growproc
,仅让进程的sz
加上新增的内存
// kernel/sysproc.c
uint64
sys_sbrk(void)
{
int addr;
int n;
if(argint(0, &n) < 0)
return -1;
addr = myproc()->sz;
/*if(growproc(n) < 0) // 惰性分配
return -1;*/
struct proc* p = myproc();
if (n > 0) //惰性分配,这里仅改变sz字段
p->sz += n;
else if (p->sz + n > 0) //如果是减少内存,还是要马上执行,要检查减去内存后是否大于0
p->sz = uvmdealloc(p->pagetable, p->sz, p->sz + n);
else
return -1;
return addr;
}
这个时候可以启动xv6执行一个简单的命令,可以发现会报错panic: uvmunmap: not mapped
,系统未给进程分配内存:
$ echo hi
usertrap(): unexpected scause 0x000000000000000f pid=3
sepc=0x00000000000012ac stval=0x0000000000004008
panic: uvmunmap: not mapped
Lazytests and Usertests (moderate)
修改trap.c中的代码以响应来自用户空间的页面错误,方法是新分配一个物理页面并映射到发生错误的地址,然后返回到用户空间,让进程继续执行。您应该在生成“
usertrap(): …
”消息的printf
调用之前添加代码。你可以修改任何其他xv6内核代码,以使echo hi
正常工作。
接下来修改usertrap
函数,处理缺页异常。r_scause
可以获取异常原因,其中13表示page load fault
,15表示page write fault
,stval
表示引发缺页异常的虚拟地址,缺页异常就可以由(r_scause() == 13 || r_scause() == 15)
表示。
先判断发生错误的虚拟地址是否位于栈空间之上,进程大小之下(虚拟地址从0开始,进程大小可以表示进程的最高虚拟地址),然后为其分配物理内存并添加映射:
// kernel/trap.c
void
usertrap(void)
{
......
} else if((which_dev = devintr()) != 0){
// ok
}
else if (r_scause() == 13 || r_scause() == 15) { // 惰性分配导致的缺页异常
uint64 fault_va = r_stval(); // 获取引发缺页异常的虚拟地址
char* pa = 0; // 分配的物理地址
// 判断fault_va是否在进程栈空间之中
if (PGROUNDUP(p->trapframe->sp) - 1 < fault_va && fault_va < p->sz && (pa = kalloc()) != 0) {
memset(pa, 0, PGSIZE);
// 物理内存映射
if (mappages(p->pagetable, PGROUNDDOWN(fault_va), PGSIZE, (uint64)pa, PTE_R | PTE_W | PTE_X | PTE_U) != 0) {
printf("lazy alloc: failed to map page\n");
kfree(pa);
p->killed = 1;
}
}
}else {
printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
printf(" sepc=%p stval=%p\n", r_sepc(), r_stval());
p->killed = 1;
}
......
}
惰性分配刚开始并未实际分配内存,遇到解除映射关系时直接跳过这部分内存,不然会导致系统崩溃:
// kernel/vm.c
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
......
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;
}
}
这个时候再启动xv6,执行echo hi
,就可以正常运行了
Lazytests and Usertests (moderate)
我们为您提供了
lazytests
,这是一个xv6用户程序,它测试一些可能会给您的惰性内存分配器带来压力的特定情况。修改内核代码,使所有lazytests
和usertests
都通过。
- 处理
sbrk()
参数为负的情况。- 如果某个进程在高于
sbrk()
分配的任何虚拟内存地址上出现页错误,则终止该进程。- 在
fork()
中正确处理父到子内存拷贝。- 处理这种情形:进程从
sbrk()
向系统调用(如read
或write
)传递有效地址,但尚未分配该地址的内存。- 正确处理内存不足:如果在页面错误处理程序中执行
kalloc()
失败,则终止当前进程。- 处理用户栈下面的无效页面上发生的错误。
sbrk()
参数为负的情况上面已处理
使用分配的虚拟内存时注意检查是否在进程空间中(PGROUNDUP(p->trapframe->sp) - 1 < va && va < p->sz
)
fork
会调用uvmcopy
进行内存拷贝,惰性分配会导致读取到未分配的pte,所以要进行处理:
// kernel/vm.c
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
......
for(i = 0; i < sz; i += PGSIZE){
if ((pte = walk(old, i, 0)) == 0)
// panic("uvmcopy: pte should exist"); 惰性分配导致某些pte未分配,遇到不存在的pte就跳过
continue;
if ((*pte & PTE_V) == 0)
// panic("uvmcopy: page not present"); 同上
continue;
pa = PTE2PA(*pte);
......
}
这里设计两个函数,(1)uvmshouldallocate
:检测一个虚拟地址是不是因为惰性分配还没分配和映射的地址。(2)uvmlazyallocate
:给虚拟地址分配和映射物理内存
其中,uvmshouldallocate
要检测的有:
- 处于
[0, p->sz)
地址范围之中(进程申请的内存范围) - 不是栈的 guard page(见 xv6手册,栈页的低一页故意留成不映射,作为哨兵用于捕捉 stack overflow 错误。惰性分配不应该给这个地址分配物理页和建立映射,而应该直接抛出异常)
(解决 usertests 中的 stacktest 失败的问题) - 页表项不存在
uvmshouldallocate
:
//判断页面是否是之前惰性分配的地址,是的话返回1
int uvmshouldallocate(uint64 va) {
pte_t* pte;
struct proc* p = myproc();
return va < p->sz //确保地址在进程的内存大小范围内
&& PGROUNDDOWN(va) != r_sp() //确保地址不在 guard page 中
&& (((pte = walk(p->pagetable, va, 0)) == 0) || ((*pte & PTE_V) == 0)); //确保页表项确实不存在
}
uvmlazyallocate
:
//给惰性分配的页面分配并映射物理地址
void uvmlazyallocate(uint64 va) {
struct proc* p = myproc();
char* pa = kalloc(); //分配物理地址
if (pa == 0) {
printf("lazy alloc: out of memory\n");
p->killed = 1;
}
else {
memset(pa, 0, PGSIZE);
if (mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)pa, PTE_W | PTE_X | PTE_R | PTE_U) != 0) { //映射物理地址
printf("lazy alloc: failed to map page\n");
kfree(pa);
p->killed = 1;
}
}
}
由于惰性分配的页,在刚分配的时候是没有对应的映射的,所以要把一些原本在遇到无映射地址时会 panic 的函数的行为改为直接忽略这样的地址。
vm.c
中的uvmunmap
:
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
......
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;
......
}
}
vm.c
中的uvmcopy
:
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
......
for(i = 0; i < sz; i += PGSIZE){
if ((pte = walk(old, i, 0)) == 0)
// panic("uvmcopy: pte should exist"); 惰性分配导致某些pte未分配,遇到不存在的pte就跳过
continue;
if ((*pte & PTE_V) == 0)
// panic("uvmcopy: page not present"); 同上
continue;
......
}
vm.c
中的copyin
和 copyout
,如果遇到没分配的虚拟地址就马上分配:
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
uint64 n, va0, pa0;
if (uvmshouldallocate(dstva))
uvmlazyallocate(dstva);
......
}
int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
uint64 n, va0, pa0;
......
}
现在可以执行./grade-lab-lazy lazytests
和./grade-lab-lazy usertests
验证实验是否正确了