MIT6.S081 lab5 lazy allocation

lab5是关于懒分配的实验。前言讲得很好，One of the many neat tricks an O/S can play with page table hardware is lazy allocation of user-space heap memory. LA是用户堆空间上的Trick。

Xv6 applications ask the kernel for heap memory using the sbrk() system call. 利用sbrk系统调用来增长或减少堆空间。

LA的原因，程序角度：

• some programs allocate more memory than they actually use
• some programs allocate memory well in advance of use

内核角度：

• It can take a long time for a kernel to allocate and map memory for a large request

因此更好的做法是 That is, sbrk() doesn’t allocate physical memory, but just remembers which user addresses are allocated and marks those addresses as invalid in the user page table. When the process first tries to use any given page of lazily-allocated memory, the CPU generates a page fault, which the kernel handles by allocating physical memory, zeroing it, and mapping it

Eliminate allocation from sbrk()

第一步，取消sbrk的空间分配，只记录堆空间的最大分配地址。

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

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

Lazy allocation

接下来就是处理LA产生的page fault，读取中断错误类型，然后取出出错的虚拟地址，在这个虚拟地址所在的页面上分配一个物理页面。

void usertrap(void){
	...
 else if (r_scause()==13 || r_scause()==15){
      uint64 va  = r_stval();
      struct proc* p = myproc();
      do{
          // 从空闲链表中取出一页
          char *mem;
          if((mem = kalloc())==0) {
              p->killed = 1;
              break;
          }
          // 初始化页为0
          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;
              break;
          }
      }while(0);
  }
  ...
}

给程序分配的无实际意义的虚拟页可能没被使用，需要修改回收的代码。

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;
//      panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0)
        continue;
//      panic("uvmunmap: not mapped");
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }
}

LA下，任何PTE不存在或PTE无效（PTE_V==0）都是被允许的。三级页表walk可能就会出现PTE不存在。

一切顺利的话，echo hi应该就能运行了。

Lazy Tests and Usertest

以上只是很naive的实现。我们还需要考虑：

• 对出错的va进行用户堆空间的校验；
• sbrk的负参数的处理，即缩小用户堆空间；
• fork系统调用，地址空间拷贝的处理；
• read/write系统调用，它们使用了合法的地址，但却没有分配物理内存。

首先查看进程内存地址分配：

说明需要检查栈以上，堆以下。

// 校验是否是用户堆空间,即栈以上，堆顶以下
if(va < PGROUNDUP(p->trapframe->sp) || va >= p->sz){
    p->killed = 1;
    break;
}

然后应对sbrk的负参数：

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

  if(argint(0, &n) < 0)
    return -1;
  addr = p->sz;
  if(n>0 && addr+n>0){ // 防止addr+n溢出
      p->sz = p->sz+n;
  }else if(n<0){
      p->sz = uvmdealloc(p->pagetable, p->sz, p->sz+n);
  }
  return addr;
}

再考虑fork时的拷贝地址空间的行为，主要是调用 vm.c/uvmcopy():301，还是和前述一致，PTE不存在或PTE无效（PTE_V==0）都是被允许的，没有PTE的话直接跳过。

    if((pte = walk(pagetable, a, 0)) == 0)
       continue;
//      panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0)
        continue;
//      panic("uvmunmap: not mapped");

最后考虑read/write系统调用。read的行为就是从某个文件读取指定内容到我们给出的addr中。想象这样一个场景：我们在堆上申请了缓冲区，然后由于LA并没有实际分配，于是read系统调用就会出错，因为它找不到缓冲区对应的物理地址。

那这里为什么不会产生缺页异常呢？因为read系统调用已经走到了内核区域，页表基地址已经切换到了内核页表地址，这个缺页不是由内核页表产生的，而是用户页表产生的，自然不会在硬件层面产生缺页中断。

查看read/write的代码，核心场景在copyout/copyin时对addr寻找pa的过程，即 walkaddr 函数返回异常的处理。原本的代码是出错直接返回-1，现在我们要分配一页给出错的va，和缺页中断处理一摸一样。

uint64 walkaddr(pagetable_t pagetable, uint64 va){
  pte_t *pte;
  uint64 pa;
  struct proc* p = myproc();

  if(va >= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  if(pte == 0 || (*pte & PTE_V) == 0){
      // 校验是否是用户堆空间,即栈以上，堆顶以下
      if(va < PGROUNDUP(p->trapframe->sp) || va >= p->sz){
          return 0;
      }
      // 从空闲链表中取出一页
      char *mem;
      if((mem = kalloc())==0) {
          return 0;
      }
      // 初始化页为0
      memset(mem, 0, PGSIZE);
      // 映射页
      if(mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U)!=0){
          kfree(mem);
          return 0;
      }
  }
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  return pa;
}

总结

懒分配使得用户堆上的空间在真正使用时才会被分配，要注意其他可能使用堆空间的系统调用，它们也会产生缺页错误。

some reference:https://blog.csdn.net/LostUnravel/article/details/121418421