# MIT6.s081-2020 Lab5 Lazy page allocation
O/S 可以与页表硬件中有趣的应用就是用户空间堆内存的惰性分配。Xv6 应用程序使用 sbrk()
系统调用向内核请求堆内存。在我们为您提供的内核中,sbrk()
分配物理内存并将其映射到进程的虚拟地址空间。内核为大型请求分配和映射内存可能需要很长时间。例如,考虑一个千兆字节由 262,144 个 4096 字节的页面组成;即使每个分配都很便宜,这也是大量的分配。此外,一些程序分配的内存比它们实际使用的多(例如,为了实现稀疏数组),或者在使用之前就分配了内存。为了让 sbrk()
在这些情况下更快地完成,复杂的内核会延迟分配用户内存。也就是说, sbrk()
没有直接分配物理内存,但只记住分配了哪些用户地址,并在用户页表中将这些地址标记为无效。当进程第一次尝试使用任何给定的延迟分配内存页面时,CPU 会生成页面错误,内核通过分配物理内存、归零和映射来处理该页面错误。本实验中将此惰性分配功能添加到 xv6。
# 准备
git fetch
git checkout lazy
make clean
2
3
# Eliminate allocation from sbrk()
引言
本实验你的任务是从 sbrk(n)
系统调用实现中删除页面分配,这是 sysproc.c
中的函数 sys_sbrk()
。sbrk(n)
系统调用将进程的内存大小增加 n 字节,然后返回新分配区域的开始(即旧大小)。您的新 sbrk(n)
应该只是将进程的大小 (myproc()->sz
) 增加 n
并返回旧大小。它不应该分配内存——所以你应该删除对 growproc()
的调用(但你仍然需要增加进程的大小!)。
实现
本节的核心在于修改 sys_sbrk()
使得其只增加/减少进程地址空间大小,而不真正地分配页面。
kernel/sysproc.c
uint64
sys_sbrk(void)
{
int addr;
int n;
if(argint(0, &n) < 0)
return -1;
struct proc *p = myproc();
addr = p->sz;
//if(growproc(n) < 0)
//return -1;
p->sz += n;
return addr;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
结果
启动 xv6,然后键入echo hi
到shell
中,可获得如下内容:
init: starting sh
$ echo hi
usertrap(): unexpected scause 0x000000000000000f pid=3
sepc=0x0000000000001258 stval=0x0000000000004008
va=0x0000000000004000 pte=0x0000000000000000
panic: uvmunmap: not mapped
2
3
4
5
6
“usertrap()
: ...”消息来自 trap.c
中的用户陷阱处理程序;它捕获了一个它不知道如何处理的异常。确保您了解为什么会发生此页面错误。“stval=0x0..04008
”表示导致缺页的虚拟地址为0x4008
。
# Lazy allocation + Lazytests and Usertests
引言
修改trap.c
中的代码,通过将新分配的物理内存页面映射到故障地址,然后返回用户空间让进程继续执行,来响应来自用户空间的页面故障。您应该在之前添加您的代码printf
产生“usertrap()
: ...”消息的调用。
修改您需要的任何其他 xv6 内核代码以获得echo hi
去工作。
实现
这里建议两个一起做了,免得回头还要修改
本实验中,你的目标是修改trap.c
和其他地方的代码,使得在你的代码能够在缺页时分配一块新的内存并建立映射。根据所给的提示,按照HINT一步步做下去即可。
HINT1:通过查看 usertrap()
中的 r_scause()
是 13 还是 15 来检查错误是否是页面错误。r_stval()
返回 RISC-Vstval
寄存器,其中包含导致页面错误的虚拟地址。
HINT2:从 vm.c
中的 uvmalloc()
参考代码,这是 sbrk()
调用的(通过 growproc()
)。您需要调用 kalloc()
和 mappages()
。使用 PGROUNDDOWN(va)
将错误的虚拟地址向下舍入到页面边界。正确处理内存不足:如果 kalloc()
在页面错误处理程序中失败,则终止当前进程。处理用户堆栈下方无效页面上的错误。
kernel/trap.c
void
usertrap(void)
{
//...
else if((which_dev = devintr()) != 0){
// ok
}else if(r_scause() == 13 || r_scause() == 15) {
uint64 va = r_stval();
uint64 pa = (uint64)kalloc();
if (pa == 0) {
p->killed = 1;
} else if (va >= p->sz || va <= PGROUNDDOWN(p->trapframe->sp)) {
kfree((void*)pa);
p->killed = 1;
} else {
va = PGROUNDDOWN(va);
memset((void*)pa, 0, PGSIZE);
if (mappages(p->pagetable, va, PGSIZE, pa, PTE_W| PTE_X | PTE_U | PTE_R) != 0) {
kfree((void*)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;
}
//...
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
HINT3:uvmunmap()
会painc
;如果某些页面未映射,请修改uvmunmap()
以不painc
。
kernel/vm.c
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
//...
if((pte = walk(pagetable, a, 0)) == 0)
continue;
//panic("uvmunmap: walk");
if((*pte & PTE_V) == 0)
//panic("uvmunmap: not mapped");
continue;
if(PTE_FLAGS(*pte) == PTE_V)
panic("uvmunmap: not a leaf");
//...
}
2
3
4
5
6
7
8
9
10
11
12
13
14
HINT4:处理负值的 sbrk()
参数,即用户空间地址减少的情况,如果一个进程在高于任何使用 sbrk()
分配的虚拟内存地址上发生页面错误,则终止该进程。
kernel/sysproc.c
#include "spinlock.h"
#include "proc.h"
uint64
sys_sbrk(void)
{
int addr;
int n;
if(argint(0, &n) < 0)
return -1;
struct proc *p = myproc();
addr = p->sz;
uint64 newaddr = addr + n;
if(newaddr >= MAXVA || newaddr <= 0)
return addr;
//if(growproc(n) < 0)
//return -1;
if(n < 0) {
if(p->sz + n < 0) return -1;
else uvmdealloc(p->pagetable, p->sz, p->sz + n);
}
p->sz += n;
return addr;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
HINT5:正确处理 fork()
中的父子内存副本。
在 fork()
中我们可以看到使用 uvmcopy()
这个函数来复制父进程的页表,而在复制父进程页表的过程中自然会发现未映射的情况从而报错,我们同uvmunmap()
中修改即可
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
//...
if((pte = walk(old, i, 0)) == 0)
//panic("uvmcopy: pte should exist");
continue;
if((*pte & PTE_V) == 0)
//panic("uvmcopy: page not present");
continue;
//...
}
2
3
4
5
6
7
8
9
10
11
12
HINT6:处理进程将有效地址从 sbrk()
传递给系统调用(例如read或write),但尚未分配该地址的内存的情况。
根据sys_read
和sys_write
的调用链可以发现:
sys_read()->readi()->either_copyout()->copyout()->walkaddr()
因此,我们可以参考usertrap
的内容编写:
kernel/vm.c
uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
pte_t *pte;
uint64 pa;
if(va >= MAXVA)
return 0;
pte = walk(pagetable, va, 0);
//if(pte == 0)
// return 0;
//if((*pte & PTE_V) == 0)
// return 0;
if (pte == 0 || (*pte & PTE_V) == 0) {
//pa = lazyalloc(va);
struct proc *p = myproc();
if(va >= p->sz || va < PGROUNDUP(p->trapframe->sp)) return 0;
pa = (uint64)kalloc();
if (pa == 0) return 0;
if (mappages(p->pagetable, va, PGSIZE, pa, PTE_W|PTE_R|PTE_U|PTE_X) != 0) {
kfree((void*)pa);
return 0;
}
return pa;
}
if((*pte & PTE_U) == 0)
return 0;
pa = PTE2PA(*pte);
return pa;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
结果
启动 xv6,然后输入lazytests
到shell
中,可获得如下内容:
在shell
中运行usertests
代码,可以得到如下内容:
# 总结
该部分实验的内容不算难,并且在教学视频中已经明确指出。