lazy alloaction

感觉这个lab是最近感觉最容易的lab了，只花了一天就完成了lab，还是感谢网络资源，感谢各位后浪们的付出，将课件翻译成中文版，翻译的质量很好，通过阅读lecture即可很快的熟悉相关的lazy allocation的原理描述，利用trap来实现。我们再来仔细看一下trap的原理：

中断现场->保存现场-> 处理trap ->恢复现场->恢复运行

利用trap我们可以进行相关的指令跳转，来执行我们需要的操作，执行完成之后，我们再恢复指令重新执行。所以我们可以利用trap来进行lazy allocation.按需申请物理内存资源，我们在申请内存时，可以先对只对该虚拟地址va进行标记，如果实际的程序需要进行访问该va时，我们再申请实际的物理内存页进行映射，映射完成后我们再恢复指令运行。
git repo

Eliminate allocation from sbrk

Your first task is to delete page allocation from the sbrk(n) system call implementation, which is the function sys_sbrk() in sysproc.c. The sbrk(n) system call grows the process's memory size by n bytes, and then returns the start of the newly allocated region (i.e., the old size). Your new sbrk(n) should just increment the process's size (myproc()->sz) by n and return the old size. It should not allocate memory -- so you should delete the call to growproc() (but you still need to increase the process's size!).

这个非常容易实现，我们只需要在sys_sbrk函数内部对地址进行标记，标记该进程已经拥有该地址空间即可。
我们可以仔细分析一下内存

我们可以看到代码实现如下：

uint64
sys_sbrk(void)
{
  uint64 addr;
  int n;
  struct proc * p = myproc();

  if(argint(0, &n) < 0)
    return -1;

  addr = p->sz;
  if(n > 0){
  	if(p->sz + n > MAXVA) return -1;
  	p->sz += n;
  }else{
	if(growproc(n) < 0)
		return -1;
  }
  
  return addr;
}

Lazy allocation

Modify the code in trap.c to respond to a page fault from user space by mapping a newly-allocated page of physical memory at the faulting address, and then returning back to user space to let the process continue executing. You should add your code just before the printf call that produced the "usertrap(): ..." message. Modify whatever other xv6 kernel code you need to in order to get echo hi to work.

实现在发生trap时我们时，我们首先判断发生trap时的地址是否合法，如果合法则我们认为该内存是lazy allocation，此时我们就kalloc一页实际的物理内存，然后进行映射，映射完成后，我们将trap恢复时执行的指令地址设置为$sepc$寄存器中的地址，CPU会从再次从发生trap的指令处开始执行。

usertrap(void)
{
  int which_dev = 0;

  if((r_sstatus() & SSTATUS_SPP) != 0)
    panic("usertrap: not from user mode");

  // send interrupts and exceptions to kerneltrap(),
  // since we're now in the kernel.
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();
  
  // save user program counter.
  p->trapframe->epc = r_sepc();
  
  if(r_scause() == 8){
    // system call

    if(p->killed)
      exit(-1);

    // sepc points to the ecall instruction,
    // but we want to return to the next instruction.
    p->trapframe->epc += 4;

    // an interrupt will change sstatus &c registers,
    // so don't enable until done with those registers.
    intr_on();

    syscall();
  } else if((which_dev = devintr()) != 0){
    // ok
  } else {
    uint64 pcode = r_scause();
	uint64 va = r_stval();
	uint64 epc = r_sepc();
	
	// page fault, valid virtual address, 记录trap发生的原因
  	if(pcode == 15 || pcode == 13){
		if(va >= p->sz || va <= p->trapframe->sp || va > MAXVA){
			p->killed = 1;
			goto fail;
		}
		// alloc a page
		char *mem = kalloc();		
	    if(mem == 0){
	        p->killed = 1;
			goto fail;
	    }
		memset(mem,0,PGSIZE);

    // mapper a page for va
		if(mappages(p->pagetable,PGROUNDDOWN(va),PGSIZE,(uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
			kfree(mem);
			p->killed = 1;
			goto fail;
		}

    // restore epc
		p->trapframe->epc = epc;  
	}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;
	}
  }

fail:
  if(p->killed)
    exit(-1);

  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2)
    yield();

  usertrapret();
}

修改uvmunmap时，我们在页表中walk时一旦发现该virtual address无法找到对应的物理页时，则我们此时直接跳过，而不是直接panic。

// Remove npages of mappings starting from va. va must be
// page-aligned. The mappings must exist.
// Optionally free the physical memory.
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  uint64 a;
  pte_t *pte;

  if((va % PGSIZE) != 0)
    panic("uvmunmap: not aligned");

  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    // 未找到该地址
    if((pte = walk(pagetable, a, 0)) == 0){
	     continue;
    }
	
	if((*pte & PTE_V) == 0){
      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

We've supplied you with lazytests, an xv6 user program that tests some specific situations that may stress your lazy memory allocator. Modify your kernel code so that all of both lazytests and usertests pass.
Handle negative sbrk() arguments.
Kill a process if it page-faults on a virtual memory address higher than any allocated with sbrk().
Handle the parent-to-child memory copy in fork() correctly.
Handle the case in which a process passes a valid address from sbrk() to a system call such as read or write, but the memory for that address has not yet been allocated.
Handle out-of-memory correctly: if kalloc() fails in the page fault handler, kill the current process.
Handle faults on the invalid page below the user stack.

我们发现在进行usertests，sbrkarg这个测试结果一直过不了，页没有报usertrap的错误，仔细跟踪了一下代码，发现它是调用了sys_write操作，而sys_write最终调用了copyin的操作，仔细检查一下copyin的函数发现它是直接在页表中读取操作，walkaddr时报错，所以直接返回-1。所以我们需要修改walkaddr函数，我们发现当前的地址没有在页表中找到时，则取申请一页新的物理页，然后将其映射到新的物理地址中。

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){
  	struct proc *p = myproc();
	if(va >= p->sz) return 0;
	
  // malloc a new page
	char *mem = kalloc();
	if(mem == 0) return 0;
  // map a page for the new address
	if(mappages(pagetable,PGROUNDDOWN(va),PGSIZE,(uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
		kfree(mem);
		return 0;
	}	
	return (uint64)mem;
  }
  
  if((*pte & PTE_U) == 0){
    return 0;
  }
  pa = PTE2PA(*pte);
  return pa;
}

我们最后还需要注意的提示：

Handle faults on the invalid page below the user stack.

我们首先看一下系统用户进程的栈空间分布？
我们知道在栈的空件是从高地址往低地址增长的，如果我们发现栈的空间大小一个page，栈的地址空间为1~4096,因为所有的进程都是用户初始化进程的子进程，在子进程复制时，同时会复制父进程的栈空间。我们在进行sbrk操作时，实际扩充的进程的heap.

void
userinit(void)
{
  struct proc *p;

  p = allocproc();
  initproc = p;
  
  // allocate one user page and copy init's instructions
  // and data into it.
  uvminit(p->pagetable, initcode, sizeof(initcode));
  p->sz = PGSIZE;

  // prepare for the very first "return" from kernel to user.
  p->trapframe->epc = 0;      // user program counter
  p->trapframe->sp = PGSIZE;  // user stack pointer

  safestrcpy(p->name, "initcode", sizeof(p->name));
  p->cwd = namei("/");

  p->state = RUNNABLE;

  release(&p->lock);
}

Handle faults on the invalid page below the user stack.

user stack：user stack主要作为用户程序在userspace执行时需要的栈空间，当我们在用户空间执行用户的程序时，这时sp寄存器指向的就是user stack。

kernel stack：kernel stack主要用户进程在系统调用时，切换到内核时执行内核的系统函数时，则这时kernel space执行时需要的栈空间，当系统调用发生时，则会发生trap，此时系统会切换pc到内核的函数调用，则此时我们执行内核函数时所需要的栈即为kernel stack。我们可以看到kstack之间有一个guard page.

  p->trapframe->kernel_sp = p->kstack + PGSIZE; // process's kernel stack
// map kernel stacks beneath the trampoline,
// each surrounded by invalid guard pages.
#define KSTACK(p) (TRAMPOLINE - ((p)+1)* 2*PGSIZE)

stack相邻的地方都有一个guard page，为了防止stack越界，访问guard page时就会报错。我们可以看到在exec函数执行时，代码和数据加装在完成后，会紧接着申请两个物理页，一个作为guard page,一个作为stack。当然方式比较奇怪：

// Allocate two pages at the next page boundary.
// Use the second as the user stack.
sz = PGROUNDUP(sz);
uint64 sz1;
// malloc 2 page
if((sz1 = uvmalloc(pagetable, sz, sz + 2*PGSIZE)) == 0)
  goto bad;
sz = sz1;
// 将第一个page标志位去掉
uvmclear(pagetable, sz-2*PGSIZE);
sp = sz;
stackbase = sp - PGSIZE;

Handle faults on the invalid page below the user stack.我们只需要检测当前的va是否处在guard page中。我们知道guard page的地址范围为：
stackbase = PGROUNDDOWN(p->trapframe->sp) \\
stackbase - PGSIZE \le va \le stackbase

// page fault, valid virtual address
  	if(pcode == 15 || pcode == 13){
		if(va >= (stack-2*PGSIZE) && va < (stack-PGSIZE)){
			p->killed = 1;
			goto fail;
		}
		
		if(va >= p->sz || va > MAXVA){
			p->killed = 1;
			goto fail;
		}
		
		char *mem = kalloc();		
	    if(mem == 0){
	        p->killed = 1;
			goto fail;
	    }
		memset(mem,0,PGSIZE);
		if(mappages(p->pagetable,PGROUNDDOWN(va),PGSIZE,(uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
			kfree(mem);
			p->killed = 1;
			goto fail;
		}
		p->trapframe->epc = epc;  
	}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;
	}

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 公开课学习

← 【MIT6.S081】 lab6 cow pages 【MIT6.S081】 lab4 traps →

扫描二维码，分享此文章

【MIT6.S081】 lab5 lazy alloaction

lazy alloaction

Eliminate allocation from sbrk

Lazy allocation

Lazytests and Usertests