MIT6.S081 Lab-5: Lazy Allocation

Posted on
居然没有hard难度的任务，我哭死

从上课视频来看，估计当年上这门课的同学们被Page Table Lab\text{Page Table Lab}整破防了，于是教授在这里想方设法地降难度给提示来补偿大家在Page Table Lab\text{Page Table Lab}受的罪。

本次实验要实现Lazy Allocation\text{Lazy Allocation}。应用程序通常不会事先知道自己要用多少内存，因此往往会有很多内存预先申请了但是没有使用，造成了很大的浪费。如果实现Lazy-Allocation\text{Lazy-Allocation}，就可以提高内存的利用率。具体而言，我们给应用程序分配虚拟地址，但是不急着分配对应的物理空间，而是直到进程需要访问物理空间的时候才分配就像老师宣布要ddl了你才开始赶作业一样。

1. 修改sbrk\text{1. 修改sbrk}

第一步是修改sbrk或者说就是修改growproc，很简单，直接修改进程大小字段即可，不分配物理页，等到访问（不存在的）物理页发生Page Fault\text{Page Fault}了再分配。所以这一步做完以后用shell\text{shell}执行命令必然会出错。

1
2
3
4
5
6
int
growproc(int n)
{
  myproc()->sz += n;
  return 0;
}

2. Lazy Allocation\text{2. Lazy Allocation}

其实到这里为止，教授都在课堂上写过代码。。。在usertrap中判断中断原因（检查scause寄存器的值）是否为Page Fault\text{Page Fault}，然后从stval寄存器中取出发生Page Fault\text{Page Fault}的虚拟地址，再照抄参考借鉴uvmalloc中的代码片段就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
if(r_scause() == 13 || r_scause() == 15)
{
  uint64 va = r_stval();
  printf("usertrap(): scause %p: page fault. pid=%d\n", r_scause(), p->pid);
  printf("            sepc=%p stval=%p. Doing lazy allocation.\n", r_sepc(), r_stval());
  uint64* mem = (uint64*)kalloc();
  if(mem == 0) p->killed = 1;
  memset(mem, 0, PGSIZE);
  uint64 a = PGROUNDDOWN(va);
  if(mappages(p->pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_R|PTE_U) != 0)
  {
    kfree(mem);
    p->killed = 1;
  }
  if(p->killed)
    printf("Oops, lazy allocation failed. Killed process.\n");
  else printf("Lazy allocation done: %p -> %p\n", a, (uint64)mem);
}
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;
}

不过在uvmunmap中，如果我们遇到了一个没分配物理地址的虚拟地址（一般来说就是分配了但是还没等到用就被释放了），uvmunmap会panic\text{panic}，把相关的判断去掉即可。此外，如果设置了释放物理页的选项，那么用kfree释放一个未分配物理页的虚拟页也会panic\text{panic}，因此在kfree之前先检查物理页是否存在，如果它不存在（还没分配）那就不用释放了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)
      panic("uvmunmap: walk");
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      if(*pte & PTE_V) kfree((void*)pa);
    }
    *pte = 0;
  }
}

3. 各种奇葩的特殊情况\text{3. 各种奇葩的特殊情况}

虽然这个难度标的是moderate\text{moderate}，但是我花的时间差不多相当于一个hard\text{hard}太菜了，感觉大概是moderate\text{moderate}里比较麻烦的那种顶尖力B肯定比不过普通力A嘛。不过它当然比不上Page Table Lab\text{Page Table Lab}那两个魔鬼hard\text{hard}任务。

尽管如此，还是有一些坑点。提示里面已经给出了一些要完善的地方，比如判断虚拟地址的范围不能爆栈，比如注意缩小用户进程内存空间的情况（个人认为应该及时uvmdemalloc，不这么做的话你不能指望后面会在这里发生Page Fault\text{Page Fault}让你释放物理页）。。。这些都还是比较简单的，很多做个判断差不多就行。下面列出几个比较坑的地方。

首先是不建议在usertrap里给错误信息输出提示语句，因为usertests\text{usertests}里有几个邪门测试是要疯狂分配内存直到穷尽地址空间为止，教授就是希望你能判断出这些情况不合法然后不处理或者杀掉进程。但是这些邪门的测试把这种事情干了很多很多很多遍，所以输出了一大堆错误提示信息让我误以为出问题了，然后对空debug\text{debug}搞半天。。。实际上就是正常的。

然后是sbrkbug测试的一个坑点，这个测试会调用sbrk把用户进程内存空间缩小为0。。。然后肯定会触发Page Fault\text{Page Fault}，但是这个Page Fault\text{Page Fault}的错误代码既不是1313也不是1515而是1212，在usertrap里要注意这种情况，不然会一直处理这个Page Fault\text{Page Fault}。

最后是sbrkarg测试，这个测试可以检查你是否做对了copyin。copyin接受用户空间的指针的时候会用walkaddr去寻找对应的物理地址，如果没找到的话会直接判错并返回。但是现在我们采用了Lazy Allocation\text{Lazy Allocation}策略，有可能访问到合法但是未分配的物理地址，这时我们当然不能草率地返回一个错误码。因此在walkaddr里面也要进行Lazy Allocation\text{Lazy Allocation}，如果我们访问不到物理地址，可以试试看是不是需要Lazy Allocation\text{Lazy Allocation}，如果Lazy Allocation\text{Lazy Allocation}成功了就再访问一次（我知道可以优化一小下，懒得改了），这次我们就得到合法的物理地址了。

代码大致长这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  uint64 pa;

  if(va >= MAXVA)
    return 0;
  pte = walk(pagetable, va, 0);
  if(!pte || ((*pte) & PTE_V) == 0)
  {
    if(!lazy_alloc(va)) return 0;
    pte = walk(pagetable, va, 0);
  }
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  return pa;
}

其中lazy_alloc是我把第二个任务写在usertrap里的代码提取出来的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int lazy_alloc(uint64 va)
{
  struct proc *p = myproc();
  if(va >= MAXVA) return 0;
  if(va >= p->sz || va < p->trapframe->sp) 
    return 0;
  uint64* mem = (uint64*)kalloc();
  if(mem == 0) 
  {
    //printf("kalloc failed!\n");
    return 0;
  }
  memset(mem, 0, PGSIZE);
  uint64 a = PGROUNDDOWN(va);
  if(mappages(p->pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_R|PTE_U) != 0)
  {
    printf("map %p to %p, failed\n", a, (uint64)mem);
    kfree(mem);
    return 0;
  }
  return 1;
}

好像就没啥了诶。。。一些细节的改动可以看看我的github\text{github}，虽然它们有些感觉不是必须的。。。