介绍
写在前面
这个实验主要是写内存的懒分配(Lazy page allocation)应该是目前为止最简单的了?!实验说明地址在Lab: xv6 lazy page allocation,我的代码在 github。
断断续续的做也没用多长时间,。需要的知识比较简单,可能会比较考验 debug 的能力,不过参考一下网上的经验,还是很容易解决的。
前置知识
主要的知识就是内存分配为什么需要设置成懒分配(Lazy page allocation)的模式。主要是因为进程在申请内存时,很难精确地知道所需要的内存多大,因此,进程倾向于申请多于所需要的内存。这样会导致一个问题:有些内存可能一直不会使用,申请了很多内存但是使用的很少。懒分配模式就是解决这样一个问题。解决方法是:分配内存时,只增大进程的内存空间字段值,但并不实际进行内存分配;当该内存段需要使用时,会发现找不到内存页,抛出 page fault 中断,这时再进行物理内存的分配,然后重新执行指令。
最主要的一点,需要注意的是,进程的地址空间是连续的,从 0 开始到 MAXVA,如下图所示:
进程创建时,首先为可执行程序分配代码段(text)和数据段(data),然后分配一个无效的页 guard page 用于防止栈溢出。接下来分配进程用户空间栈,xv6 栈的大小是4096,刚好对应一页内存。值得注意的是,栈的生长方向是向下的,sp 是栈指针,初始时指向栈底,即大的地址位置。在栈生长时,栈指针(sp)减小。栈的上面是堆(heap),堆的大小是动态分配的,进程初始化时,堆大小为 0,p->sz 指针指向栈底位置。
实验内容
三个任务的目的都是实现一个功能,递进式实现,有些代码需要在三个任务中不断更改。建议做实验之前看一下这节对应的课程,课程内讲了该怎么更改代码,与实验有很大的关系。
任务一(Eliminate allocation from sbrk())
任务一的目的就是更改 kernel/sysproc.c 中的 sys_sbrk() 函数,把原来只要申请就分配的逻辑改成申请时仅进行标注,即更改进程的 sz 字段。其实只要对 sz 进行增加就能完成这部分的更改,但后面的任务还需要更改这个函数,直接放上最终版:
uint64
sys_sbrk(void)
{
int addr;
int n;
if(argint(0, &n) < 0)
return -1;
struct proc *p = myproc();
addr = p->sz;
//if (addr + n < 0) return -1;
if (addr + n >= MAXVA || addr + n <= 0)
return addr;
p->sz = addr + n;
//if(growproc(n) < 0)
// return -1;
if(n < 0)
uvmdealloc(p->pagetable, addr, p->sz);
return addr;
}这里有三点需要注意的:
- 将 p->sz 增加 n,这也是任务一的要求。
- 如果 n 是负数,则对其对应的内存进行释放(仿照 proc.c 中的 growproc 函数写就行)。
- 判断堆的空间大小。不能超过 MAXVA,也不能释放小于 0 的地址空间。
如果直接运行 echo hi 命令会报错,因为我们还没写分配内存的逻辑,这是下面任务的内容。
任务二(Lazy allocation)
第一步,处理中断,分配内存
仿照上一个实验中的中断处理操作,在 kernel/trap.c 中,找到中断处理的逻辑进行更改。
系统调用的中断码是 8,page fault 的中断码是 13 和 15。因此,这里我们对 r_scause() 中断原因进行判断,如果是 13 或是 15,则说明没有找到地址。错误的虚拟地址被保存在了 STVAL 寄存器中,我们取出该地址进行分配。如果申请物理地址没成功或者虚拟地址超出范围了,那么杀掉进程,代码如下:
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_U | PTE_R) != 0) {
kfree((void*)pa);
p->killed = 1;
}
}
// lazyalloc(va);
} else {
printf(&#34;usertrap(): unexpected scause %p pid=%d\n&#34;, r_scause(), p->pid);
printf(&#34; sepc=%p stval=%p\n&#34;, r_sepc(), r_stval());
p->killed = 1;
}需要注意的几点:
- 如果申请内存成功了,如果虚拟地址不合法,需要再释放掉这块内存;
- va >= p->sz 是指虚拟地址不能超过堆实际分配的大小;
- p->trapframe->sp 是指栈指针的位置,所以 PGROUNDDOWN(p->trapframe->sp) 是指栈顶最大值,是 guard 页的最大地址,用于防止栈溢出;
- 中断判断时,如果出错(虚拟地址不合法或者没有成功映射到物理地址),就杀死进程。
由于在接下来的 write 等函数出现找不到地址时,也需要分配内存。本来打算写一个函数进行代码复用,但实际上不太行,因为只有在这里才需要杀死进程。
第二步,处理 uvmunmap 的报错
uvmunmap 是在释放内存时调用的,由于释放内存时,页表内有些地址并没有实际分配内存,因此没有进行映射。如果在 uvmunmap 中发现了没有映射的地址,直接跳过就行,不需要 panic:
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
uint64 a;
pte_t *pte;
if((va % PGSIZE) != 0)
panic(&#34;uvmunmap: not aligned&#34;);
for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
if((pte = walk(pagetable, a, 0)) == 0)
//panic(&#34;uvmunmap: walk&#34;);
continue;
if((*pte & PTE_V) == 0)
continue;
//panic(&#34;uvmunmap: not mapped&#34;);
if(PTE_FLAGS(*pte) == PTE_V)
panic(&#34;uvmunmap: not a leaf&#34;);
if(do_free){
uint64 pa = PTE2PA(*pte);
kfree((void*)pa);
}
*pte = 0;
}
}这样,任务二就算完成了,注意添加 spinlock.h 和 proc.h 的头部引用 #include。到目前为止,已经可以成功运行 echo hi 命令了。已经算是写完主要的逻辑了。
任务三(Lazytests and Usertests)
任务三是需要通过所有的测试用例,这个任务的代码很少,前面很多已经都写好了。主要是两个函数的异常处理,一个是 uvmcopy,另一个是 walkaddr。
第一步,uvmcopy
fork 函数在创建进程时会调用 uvmcopy 函数。由于没有实际分配内存,因此,在这里,忽略 pte 无效,继续执行代码。
kernel/vm.c
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
pte_t *pte;
uint64 pa, i;
uint flags;
char *mem;
for(i = 0; i < sz; i += PGSIZE){
if((pte = walk(old, i, 0)) == 0)
continue;
//panic(&#34;uvmcopy: pte should exist&#34;);
if((*pte & PTE_V) == 0)
continue;
//panic(&#34;uvmcopy: page not present&#34;);
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;
err:
uvmunmap(new, 0, i / PGSIZE, 1);
return -1;
}第二步,walkaddr
这里,由于 read/write 等系统调用时,由于进程利用系统调用已经到了内核中,页表已经切换为内核页表,无法直接访问虚拟地址。因此,需要通过 walkaddr 将虚拟地址翻译为物理地址。这里如果没找到对应的物理地址,就分配一个:
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;
}需要注意的是,这里的分配代码并不杀死进程。
总结
实验过程可能会出现一些 bug,但实验还是挺简单的。有时候不知道该怎么判断的时候,看一下实验指导书的指导,很有帮助。 我还卡在了 MAXVA 卡了一段时间,。。
参考文献
- 6.s081 Lab5 lazy
- MIT 6.s081 xv6-lab5-lazy
上一篇:机器人专家、MIT博士高炜正式加入梅卡曼德任职研究科学家 ... 下一篇:【2021年3月23日offer速报】麻省理工、哈佛、伯克利、哥大 ... |