MIT_6.s081_Lab5_lazy page allocation

Eliminate allocation from sbrk()

我们先来看看这个图：

代码段不必多说，唯一要注意的点就是fork()函数调用的时候不会去复制程序段，而是通过映射让父子进程共享。

我们现在要给用户空间分配内存就是说

我们知道，sbrk()分配物理内存并将其映射到进程的虚拟地址空间，内核为大型请求分配和映射内存可能需要很长时间。

本实验你的任务是修改 sys_sbrk()使得其只增加/减少进程地址空间大小，而不真正地分配页面。sbrk是xv6提供的系统调用，它使得用户应用程序能扩大自己的heap。当一个应用程序启动的时候，

在xv6中，sbrk的实现默认是eager allocation，一旦调用了sbrk，内核就会立即分配物理内存给进程。但这样有点浪费，我们可以利用lazy allocation来做，sbrk基本不做任何事，只是改变p->se的大小，将p->sz增加n，其中n是需要新分配的内存page数量。但是内核在这个时间点并不会分配任何物理内存。

我们先来看看原版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)//检测传入的参数
    return -1;
  addr = myproc()->sz;//uint64 sz,Size of process memory (bytes)
  if(growproc(n) < 0)//分配n个bytes
    return -1;
  return addr;
}

我们看看growproc函数，就知道为什么要这么做了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Grow or shrink user memory by n bytes.
// Return 0 on success, -1 on failure.
int
growproc(int n)
{
  uint sz;
  struct proc *p = myproc();

  sz = p->sz;
  if(n > 0){
    if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
      return -1;
    }
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
  }
  p->sz = sz;
  return 0;
}

大家看，在上述函数中，使用uvmalloc函数是会为这个进程的虚拟地址分配实际的物理内存的。

在sys_sbrk()函数中，用来分配页面的是growproc函数，我们直接修改这部分：

1
2
uint new_addr=addr+n;//直接把地址+n，分配虚拟地址
myproc()->sz=newaddr;

然后对new_addr控制在合理的范围之内范围：

1
2
3
if(newaddr>=MAXVA||newaddr<=0){
	return addr;
}

Lazy allocation

本实验中，你的目标是修改trap.c和其他地方的代码，使得在你的代码能够在缺页时分配一块新的内存并建立映射。

page fault可以让地址映射关系变得动态起来，这也是我们实现lazy allocation的关键。当发生page fault的时候，xv6内核会打印出错的虚拟地址，并且会将这个地址保存在STVAL寄存器中，所以，当一个用户应用程序出发了page fault，程序会切换到内核，同时将出错的地址存放在STVAL寄存器中。

对于不同的场景page falut有不同的响应，比如，13表示是因为load引起的page fault；15表示是因为store引起的page fault；12表示是因为指令执行引起的page fault。

缺页处理

我们可以先检查是否为缺页错误。当我们看到了一个page fault，相应的虚拟地址小于当前p->sz，同时大于stack，那么我们就知道这是一个来自于heap的地址，但是内核还没有分配任何物理内存。所以对于这个page fault的响应也理所当然的直接明了：在page fault handler中，通过kalloc函数分配一个内存page；初始化这个page内容为0；将这个内存page映射到user page table中；最后重新执行指令。比方说，如果是load指令，或者store指令要访问属于当前进程但是还未被分配的内存，在我们映射完新申请的物理内存page之后，重新执行指令应该就能通过了。

在usertrap函数中，我们可以为缺页异常添加检测，如果缺页异常，且其原因是我们的lazy alloction的话，我们就可以为其分配物理内存，并在页表建立映射，代码如下：

1
2
3
4
5
6
7
if((r_scause() == 13 || r_scause() == 15) && trap_by_lazyllocation){ // 缺页异常，并且发生异常的地址进行过懒分配
      // 分配物理内存，并在页表创建映射
   } 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;
   }

那么我们如何检测是否是lazy allocation导致的错误呢？我们需要定义一个函数trap_by_lazyallocation，其实现如下：

1
2
3
4
5
6
uint64 va = r_stval();//获取栈指针
if(va<p->sz){
    return 1;
}else{
    return 0;
}

也就是说，当我们的这个要访问的页面小于进程的整个逻辑内存的页面的数量时，说明是缺页的。但是测试之后发现不对，我们再次修改：

1
((pte = walk(p->pagetable, va, 0))==0) || ((*pte & PTE_V)==0)

我们还要va映射不能进入pagetable，这样才能做到检验。那么我们怎样分配呢？

我们可以通过uvmalloc函数来做到分配物理页面，先来看看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
25
uint64
uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  char *mem;
  uint64 a;

  if(newsz < oldsz)
    return oldsz;

  oldsz = PGROUNDUP(oldsz);
  for(a = oldsz; a < newsz; a += PGSIZE){
    mem = kalloc();
    if(mem == 0){
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
    memset(mem, 0, PGSIZE);
    if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
      kfree(mem);
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
  }
  return newsz;
}

我们仿照上述的uvmalloc函数来编写下面的uvm_lazy函数：

1
2
memset(mem, 0, PGSIZE);
mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U)

这样就差不多了。

补充一个segmentation fault的知识：在xv6中使用的是页式存储，因此没有segmentation fault的概念，但是linux是段页式存储，因此有可能会出现segmentation fault的错误，所谓段错误就是指访问的内存超过了系统给这个程序的内存空间。比如说：尝试写一块属于操作系统的内存，或以错误的类型访问内存区域。段错误就是访问了不可访问的内存，这个内存要么是不存在的，要么是访问受限的。

指针越界和SIGSEGV是最常出现的情况，