笔记10 - HW4: xv6 lazy page allocation

发表于 | 分类于

Part One: Eliminate allocation from sbrk()

xv6应用程序通过调用sbrk()系统调用向内核申请heap内存空间，该系统调用将分配物理内存并map到进程的页目录（虚拟地址空间）。鉴于许多程序申请物理空间后并不使用，因此复杂的内核通常会设计为：在应用程序试图使用不存在的页面（访问到的虚拟地址不存在物理页映射）的时候，通过捕获产生页错误信号，然后分配物理内存使得程序可以继续执行，这称为“lazy page allocation”。而在申请heap内存空间的时候，仅仅是增大用户空间的值，即proc->sz。

修改后的代码是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//sysproc.c
int
sys_sbrk(void)
{
  int addr;
  int n;

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

sys_sbrk()是通过growproc()函数来增加物理空间和改变用户空间大小的，注意到一个事实：用户空间的栈顶指针并没有发生改变。init.c通过fork子进程，然后子进程exec执行sh的时候，sh程序的栈顶指针是指向新分配的用户空间顶端的。之后sh程序fork子进程执行命令，子进程保持了该栈顶指针，子进程增加heap内存空间的时候，栈顶指针也没有变化。
这样子的话，在sh中执行echo hi将会出现页错误，具体的发生时机是：
sh.c读取输入命令后，fork子进程执行命令，在解析命令的过程中调用execcmd，execcmd函数调用malloc()函数（见umalloc.c），malloc()函数根据空间使用情况将调用morecore()函数，morecore()函数调用sbrk()函数分配物理空间，进而内核执行sys_sbrk()系统调用。sys_sbrk()只返回分配前用户空间顶部的逻辑地址，因此malloc操作的地址空间其实是位于原用户空间之上。这里我们没有实际分配物理空间，因此后续在morecore()函数中执行hp->s.size = nu;时将发生页错误（还有其他地方也可能产生页错误，只要是访问到的虚拟地址没有映射到物理页），系统会产生T_PGFLT信号，trap.c中将输出相关错误信息，说明内核不知如何处理此类问题。

Part Two: Lazy allocation

我们将在trap.c对缺页信号进行处理，具体思路是：获取发生页错误的虚拟地址，将其向下4K页对齐，然后分配一页的物理空间并映射到进程页目录中。注意到，这并不会产生地址重映射的问题，因为如果重映射，说明发生页错误的虚拟地址向下4K页对齐后的对应的页之前已经被映射进页目录了，而这样的话该地址是不会产生页错误的。代码如下：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//trap.c
void
trap(struct trapframe *tf)
{
                           .
                           .
                           .
  switch(tf->trapno){
                           .
                           .
                           .
//PAGEBREAK: 13
  default:
    if(proc == 0 || (tf->cs&3) == 0){
      // In kernel, it must be our mistake.
      cprintf("unexpected trap %d from cpu %d eip %x (cr2=0x%x)\n",
              tf->trapno, cpunum(), tf->eip, rcr2());
      panic("trap");
    }

    //By jianzzz
    //处理页错误T_PGFLT
    if(tf->trapno == T_PGFLT){
      //rcr2() --> 导致页错误的虚拟地址
      uint va = rcr2();
      uint sz = PGROUNDDOWN(va); 
      cprintf( "T_PGFLT:%x\n",va);
      if((sz = allocuvm(proc->pgdir, sz, sz + PGSIZE)) == 0)
        panic("trap T_PGFLT");  
      break;
    }

    // In user space, assume process misbehaved.
    cprintf("pid %d %s: trap %d err %d on cpu %d "
            "eip 0x%x addr 0x%x--kill proc\n",
            proc->pid, proc->name, tf->trapno, tf->err, cpunum(), tf->eip,
            rcr2());
    proc->killed = 1;
  }
                           .
                           .
                           .
}

xv6的堆分配思想见【The C Programming Language 8.7.实例–存储分配程序】。
由上可知，堆是在用户态实现的，使用链表进行管理。在xv6中，使用malloc并不一定分配物理空间。如果堆管理发现可用空间不够，则调用sbrk()函数申请分配物理空间，此时系统只累加进程空间大小，并返回当前用户空间顶部的逻辑地址。堆管理根据申请的大小调整链表记录，然后尝试对“分配”的空间进行访问，产生页错误，内核对其进行页分配和映射，返回用户态后程序正常运行。之后只要继续在链表记录的大小内使用malloc，若遇到未分配地址则继续产生页错误，否则使用已有的空间；而如果超出了链表记录大小，则再次调用调用sbrk()函数申请分配物理空间并更新链表大小记录。对于不再使用的空间，调用free()并入到空闲链表中，没有实际归还到操作系统。等到程序结束的时候，所有映射到页表的堆空间将被释放。

遗留的问题

申请新的heap空间后，特殊情况下栈顶指针会不会指向到heap空间（比如人为一直pop）？即这里存在一个疑问：栈底是固定的吗？？？

显示 Gitment 评论