MIT6828-HW4-xv6 lazy page allocation

懒分配是物理内存管理的一种策略，其基本思想是直到进程真正使用内存时，才进行内存的分配。本文将对xv6中懒分配的实现进行总结。

xv6的应用通过sbrk()系统调用来获取堆上分配的内存，有些进程申请了内存，但是一直没用，如果给他们分配了内存，就会导致有一部分内存一直被站着不用（占着茅坑不拉*），所以机智的内核就想出了一个策略，直到内存真正被使用，才进行分配。

第一部分：删除`sbrk`中分配内存的部分

首先我们要修改sbrk系统调用，即sysproc.c下的sys_sbrk()函数，删除其中的内存分配部分。sbrk的功能如下：首先，它将进程的内存大小增长n字节，然后返回新分配的空间的起始地址（即进程原来的内存大小）。改进后的sbrk只增加进程的大小，不分配内存。改进后的sbrk如下：

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

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
#if 0
    if(growproc(n) < 0)    //分配内存
    return -1;
#endif
  myproc()->sz += n;       // 修改进程size大小
  return addr;             // 返回起始地址
}

修改后会发生什么现象呢？进程如果试图获取堆内存，那么其大小会增加，但是并没有真的给它分配内存，如果试图去写入新内存，会触发page fault

1 2	$ echo hi pid 3 sh: trap 14 err 6 on cpu 0 eip 0x111c addr 0x4004--kill proc

运行操作系统，输入上面的命令，弹出提示，这个提示来自trap.c中的trap handler，表示捕获到了页错误（trap 14 T_PGFLT），0x4004表示造成PGFLT的虚拟地址为4004

第二部分：Lazy allocation

目标

修改trap.c，当用户空间发生缺页错误后，分配一块新内存，然后让用户进程继续执行，暂时不需要考虑临界情况。这里给了若干个提示，分别如下：

查看打印语句中的参数，看看如何找到触发页错误的虚拟地址：使用rcr2()函数
从allocuvm()函数中找到分配空间的方法
使用PGROUNDDOWN(va)这个宏函数，从引发页错误的地址va找到一个页边界
分配内存后记得使用return返回，要不然会错误执行杀死进程的指令
使用mappages完成地址的映射，在trap.c中调用mappages之前添加如下声明：
int mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
通过tf->trapno==T_PGFLT检查是否为页面错误

实现

找到触发页错误的虚拟地址

首先我们看看trap是如何找到虚拟地址的，在trap.c中的trap()函数内，如果触发了缺页中断，会打印错误信息，打印语句为：

1 2	cprintf("pid %d %s: trap %d err %d on cpu %d" "eip 0x%x addr 0x%x--kill proc\n", myproc()->pid, myproc()->name, tf->trapno, tf->err, cpuid(), tf->eip, rcr2());

从上面的语句中可以看到，出发页错误的虚拟地址是通过rcr2函数找到的。实际上是cr2控制寄存器

从allocuvm()函数找到分配空间的方法

allocuvm()在vm.c中，sbrk通过growproc()这个函数调用了allocuvm()，函数定义如下：

// Allocate page tables and physical memory to grow process from oldsz to
// newsz, which need not be page aligned.  Returns new size or 0 on error.
// 将进程内存空间进行扩展，从oldsz扩展至newsz
int
allocuvm(pde_t *pgdir, uint oldsz, uint newsz){
  char *mem;
  uint a;

  if(newsz >= KERNBASE)
    return 0;
  if(newsz < oldsz)
    return oldsz;

  a = PGROUNDUP(oldsz);   //这里直接将对应大小作为了虚拟地址，很巧妙
  for(; a < newsz; a += PGSIZE){  //没有对齐，因此实际分配的内存是比需要的内存小的
    mem = kalloc();
    if(mem == 0){
      cprintf("allocuvm out of memory\n");
      deallocuvm(pgdir, newsz, oldsz);
      return 0;
    }
    memset(mem, 0, PGSIZE);
    if(mappages(pgdir, (char*)a, PGSIZE, V2P(mem), PTE_W|PTE_U) < 0){
      cprintf("allocuvm out of memory (2)\n");
      deallocuvm(pgdir, newsz, oldsz);
      kfree(mem);
      return 0;
    }
  }
  return newsz;
}

通过`tf->trapno==T_PGFLT`检查是否为页面错误

通过上述语句判断是否为页面错误，然后将内存分配语句写在上面的判断框中：

1
2
3

if(tf->trapno==T_PGFLT){
    // Allocate mem
}

其他问题

为了实现分配过程，我们还需要解决如下问题：

需要分配多少空间？根据提示，我们需要分配一页，一页如果不够用了，就触发中断再分配一页（这样不会导致效率低下吗？）
从哪里开始分配？
分配到哪里

完整实现

根据上面的分析，我们可以得到改进后的部分如下，改进的部分就放在下面这条语句之前：

1 2	cprintf("pid %d %s: trap %d err %d on cpu %d" "eip 0x%x addr 0x%x--kill proc\n", myproc()->pid, myproc()->name, tf->trapno, tf->err, cpuid(), tf->eip, rcr2());

需要注意的是完成内存分配后，要及时break，否则会导致这句错误提示又显示出来。

if(tf->trapno==T_PGFLT){
    // Allocate mem
    uint va = PGROUNDDOWN(rcr2());
    char *mem;
    mem = kalloc();
    if(mem == 0){
        cprintf("trap:allocate new memory failed!\n");
    }
    
    memset(mem, 0, PGSIZE);
    if(mappages(myproc()->pgdir, (char*)va, PGSIZE, V2P(mem), PTE_W | PTE_U) < 0){
        cprintf("trap:allocate new memory failed!(1)\n");
        kfree(mem);
    }else{
        break;
    }
}

关于懒分配，可以参考内核关于缺页异常的处理。至此，我们实现了一个非常简陋的懒分配器，对进程进行内存分配。

挑战任务

这个lazy allocation机制实际上是不完善的，还需要解决如下问题：

分配内存如果是负数怎么办？
如果太大了怎么办？
确保fork和exit在没有被分配内存的情况下也能正确工作（写时复制）
如果堆覆盖栈该怎么办？
如果内核要使用sbrk()分配的空内存该怎么办？

第一部分：删除sbrk中分配内存的部分