6.828 Homework xv6 lazy page allocation

date: 2019-02-20
tags: OS 6.828

Part One: Eliminate allocation from sbrk()

首先是要在sbrk中去掉分配内存的部分。sbrk函数原来的版本是：

int
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  if(growproc(n) < 0)
    return -1;
  return addr;
}

可想而知，分配内存的主要方式来源于growproc（在proc.c），growpoc就是会给当前进程的page table加n的内存，并把proc->sz加n。注意，阅读allocuvm函数可以得知，在分配的时候不会对n或者之后的sz+n，round到page size的整数倍。所以按照题目要求，我们不分配内存，只增加sz，那么就是：

int
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  myproc()->sz += n;
  return addr;
}

之后，如果启动xv6，就会得到需要的结果：

init: starting sh
$ echo hi
pid 3 sh: trap 14 err 6 on cpu 0 eip 0x112c addr 0x4004--kill proc
$

这里输出的是位于trap.c中的page fault，对应的是在trap.c中跳入trap函数。

Part Two: Lazy allocation

按照题目要求，在trap中加入

  case T_PGFLT:
  {
    // code from allocuvm
    uint newsz = myproc()->sz;
    uint a = PGROUNDDOWN(rcr2());
    if(a < newsz){
      char *mem = kalloc();
      if(mem == 0) {
        cprintf("out of memory\n");
        exit();
        break;
      }
      memset(mem, 0, PGSIZE);
      mappages(myproc()->pgdir, (char*)a, PGSIZE, V2P(mem), PTE_W|PTE_U);
    }
    break;
  }

中间的代码都是由allocuvm学来的，注意因为是lazy allocation所以只需要分配一个pagesize就可以了，同时a要PGROUNDDOWN，而不是PGROUNDUP。应该是因为在allocuvm里面，传入的量是myproc()->sz，是4096的倍数，而通过rcr2得到的是第一个没有被分配的地址。可以共下面的这个我加了两行cprintf的输出中看出来。

$ echo hi
addr: 16384
rcr2(): 16388
hi

所以，如果在trap中仍然用PGROUNDUP就会跳过去一个page了。但是为什么如果写错了触发的错误是mappages中的panic(remap)我就不明白了。

然后为了能访问mappages，在trap.c的最上面声明了

extern int mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm);

同时把其定义处的static去掉。

然后为了实现Optional Challenges，把sbrk改为：

int
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  if(n < 0) {  // when n < 0, there is no lazy allocation
    // 注意，growproc在释放没有被分配的内存的时候会直接跳过去，不会报错
    if(growproc(n) < 0)
      return -1;
  } else {
    if(myproc()->sz + n >= KERNBASE)
      return -1;
    myproc()->sz += n;
  }
  return addr;
}

从而实现了负数和大数的限制。没有写测试...所以不能确定对。

这里顺便记录一下xv6是如何调用trap的。之前在讲system call的时候，说过是因为调用了int指令。而page fault这样的中断呢？

x86有一个特殊的table称为interrupt descriptot table(IDT)，其为一个function handler的数组。这个数组里面调用的函数都在vector.S中定义了。（注意vector.S是由vector.pl这个perl文件生成的。）每个function handler都调用了alltrap从而调用trap。在调用之前，会把trapframe推进栈中，对于page fault这样需要特殊寄存器的中断，会多推进去一些需要的东西。

zhuzilin's Blog

about

6.828 Homework xv6 lazy page allocation

Part One: Eliminate allocation from sbrk()

Part Two: Lazy allocation