MIT 6s081 lab 5: xv6 lazy page allocation

发布时间:2024年01月15日

Page faults

Basic

通过page fault可以实现一系列的虚拟内存功能:

  • lazy allocation
  • copy-on-write fork
  • demand paging
  • memory mapped files

虚拟内存的两个主要的优点:

1、隔离性:每个应用程序拥有自己的地址空间,因此不可能修改其他应用程序的内存数据,同时用户空间和内核空间也具备隔离性

2、抽象,处理器和指令可以使用虚拟地址,内核会定义从虚拟地址到物理地址的映射关系

page fault可以使得地址映射关系变得动态,内核可以更新page table,内核将会有巨大的灵活性

内核使用三个重要信息来响应page fault:

  • 出错的虚拟内存地址(存放在STVAL寄存器中)
  • 出错的原因(存放在SCAUSE寄存器中)
  • 引起page fault时的程序计数器值,代表page fault发生的位置(存放在SEPC寄存器)

page fault同样使用trap机制来进入内核空间。

Lazy page allocation

sbrk是XV6提供的系统调用,它使得用户应用程序能扩大自己的heap。当一个应用程序启动的时候,sbrk指向的是heap的最底端,同时也是stack的最顶端。这个位置通过代表进程的数据结构中的sz字段表示.

在这里插入图片描述

当sbrk实际发生或者被调用的时候,内核会分配一些物理内存,并将这些内存映射到用户应用程序的地址空间,然后将内存内容初始化为0,再返回sbrk系统调用。这样,应用程序可以通过多次sbrk系统调用来增加它所需要的内存。类似的,应用程序还可以通过给sbrk传入负数作为参数,来减少或者压缩它的地址空间。

在XV6中,sbrk的实现默认是eager allocation。这表示了,一旦调用了sbrk,内核会立即分配应用程序所需要的物理内存。但是实际上,对于应用程序来说很难预测自己需要多少内存,所以通常来说,应用程序倾向于申请多于自己所需要的内存。

利用lazy allocation,核心思想非常简单,sbrk系统调基本上不做任何事情,唯一需要做的事情就是提升p->sz,将p->sz增加n,其中n是需要新分配的内存page数量。但是内核在这个时间点并不会分配任何物理内存。之后在某个时间点,应用程序使用到了新申请的那部分内存,这时会触发page fault,这时再分配需要的物理内存,然后再去执行

lab5:xv6 lazy page allocation

作业地址:Lab: xv6 lazy page allocation (mit.edu)

Eliminate allocation from sbrk() (easy)

根据提示,修改sys_sbrk函数,删去growproc(n)的调用,但要修改myproc()->sz

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 += n;
  return addr;
}

Lazy allocation (moderate)

根据指导书提示,修改usertrap函数,参考uvmalloc()函数,添加对page fault的处理,注意要使用PGROUNDDOWN(va)来对齐,建立完整的一页

void
usertrap(void)
{
  int which_dev = 0;

  if((r_sstatus() & SSTATUS_SPP) != 0)
    panic("usertrap: not from user mode");

  // send interrupts and exceptions to kerneltrap(),
  // since we're now in the kernel.
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();
  
  // save user program counter.
  p->trapframe->epc = r_sepc();
  
  if(r_scause() == 8){
    // system call

    if(p->killed)
      exit(-1);

    // sepc points to the ecall instruction,
    // but we want to return to the next instruction.
    p->trapframe->epc += 4;

    // an interrupt will change sstatus &c registers,
    // so don't enable until done with those registers.
    intr_on();

    syscall();
  } else if((which_dev = devintr()) != 0){
    // ok
  }  // lab5 add begin
  else if(r_scause() == 13 || r_scause() == 15) // page fault 
  {
      uint64 va = r_stval(); // get the virtual address that caused the page fault.
      // printf("page fault %p\n", va);
      if(va <= p->sz) {
        char * pa = kalloc(); // alloc physial memory ,分配一页物理内存
        if(pa == 0){ // 申请失败
          p->killed = 1; // 杀死进程
        }
        else{
          memset(pa, 0, PGSIZE); //清空物理内存
          if(mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)pa, PTE_W|PTE_R|PTE_U) != 0){ //建立从va下取整开始一页的映射
            kfree(pa); // 分配失败,释放物理内存
            p->killed = 1;
          }
        }
      }
  }
  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;
  }

  if(p->killed)
    exit(-1);

  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2)
    yield();

  usertrapret();
}

Lazytests and Usertests (moderate)

1、首先要处理sbrk传入的参数为负数的情况

uint64
sys_sbrk(void)
{
  int addr;
  int n;
 
  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  if(n < 0){ //如果删除内存,就直接删除,但有可能之前就没有分配
     if(growproc(n) < 0) // 修改uvmunmap函数,walk不到也不管,没有建立映射也不管
      return -1;
  }
  else{
    myproc()->sz += n;
  }
  return addr;
}

同时要修改uvmunmap函数,删除的部分内存**有可能之前就没有分配对应的页表,也可能分配了页表,但没有插入页表项,**所以需要把panic("uvmunmap: walk")panic("uvmunmap: not mapped")注释掉,改成continue

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

2、当page-faults发生的虚拟地址比之前sbrk申请的内存地址还要高,说明出现了错误,需要杀死进程,同时需要处理虚拟地址空间小于最开始栈顶指针的位置的情况,这种情况也需要杀死进程。

修改usertrap()函数:

else if(r_scause() == 13 || r_scause() == 15) // page fault 
  {
      uint64 va = r_stval(); // get the virtual address that caused the page fault.
      // printf("page fault %p\n", va);
      if(va <= p->sz && va >= p->trapframe->sp) {
        char * pa = kalloc(); // alloc physial memory ,分配一页物理内存
        if(pa == 0){ // 申请失败
          p->killed = 1; // 杀死进程
        }
        else{
          memset(pa, 0, PGSIZE); //清空物理内存
          if(mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)pa, PTE_W|PTE_R|PTE_U) != 0){ //建立从va下取整开始一页的映射
            kfree(pa); // 分配失败,释放物理内存
            p->killed = 1;
          }
        }
      }
      else p->killed = 1; // 此时出现异常的va高于p->sz,说明有问题,直接kill process
  }

3、需要处理fork时,对用户进程的页表的处理,修改uvmcopy函数(和修改uvmunmap函数类似),**有可能有的虚拟地址并没有建立页表,也有可能有的地址建立了页表,但没有添加页表项。**因此将panic("uvmcopy: pte should exist")panic("uvmcopy: page not present")改为continue

int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  char *mem;

  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0)
      // panic("uvmcopy: pte should exist");
      continue;
    if((*pte & PTE_V) == 0)
      // panic("uvmcopy: page not present");
      continue;
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    if((mem = kalloc()) == 0)
      goto err;
    memmove(mem, (char*)pa, PGSIZE);
    if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
      kfree(mem);
      goto err;
    }
  }
  return 0;

 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}

4、需要处理read、write、pipe的系统调用,传入的虚拟地址可能是有效的(高于一开始的栈顶指针,低于sbrk分配的内存地址),但并没有分配对应的物理内存,此时需要及时地进行分配。

修改sys_read

uint64
sys_read(void)
{
  struct file *f;
  int n;
  uint64 p;

  if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argaddr(1, &p) < 0)
    return -1;

  // 判断一下addr虚拟地址对应的物理地址空间是否被申请,如果没有被申请,则申请。
  if(p <= myproc()->sz && p >= myproc()->trapframe->sp && walkaddr(myproc()->pagetable, p) == 0) {
      printf("debug: %p %d\n", p, n);
      // 如果这个虚拟地址p没有映射,那就建立映射
      char * pa = kalloc(); // alloc physial memory ,分配一页物理内存
      if(pa == 0){ // 申请失败
        myproc()->killed = 1;
        return -1;
      }
      else{
        memset(pa, 0, PGSIZE); //清空物理内存
        if(mappages(myproc()->pagetable, PGROUNDDOWN(p), PGSIZE, (uint64)pa, PTE_W|PTE_R|PTE_U) != 0){ //建立从va下取整开始一页的映射
          kfree(pa); // 分配失败,释放物理内存
          myproc()->killed = 1;
          return -1;
        }
      }
  }

  return fileread(f, p, n);
}

修改sys_write

uint64
sys_write(void)
{
  struct file *f;
  int n;
  uint64 p;
 
  if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argaddr(1, &p) < 0)
    return -1;

  if(p <= myproc()->sz && p >= myproc()->trapframe->sp && walkaddr(myproc()->pagetable, p) == 0) {
      // printf("debug: %p %d\n", p, n);
      // 如果这个虚拟地址p没有映射,那就建立映射
      char * pa = kalloc(); // alloc physial memory ,分配一页物理内存
      if(pa == 0){ // 申请失败
        myproc()->killed = 1;
        return -1;
      }
      else{
        memset(pa, 0, PGSIZE); //清空物理内存
        if(mappages(myproc()->pagetable, PGROUNDDOWN(p), PGSIZE, (uint64)pa, PTE_W|PTE_R|PTE_U) != 0){ //建立从va下取整开始一页的映射
          kfree(pa); // 分配失败,释放物理内存
          myproc()->killed = 1;
          return -1;
        }
      }
  }

  return filewrite(f, p, n);
}

修改sys_pipe

uint64
sys_pipe(void)
{
  uint64 fdarray; // user pointer to array of two integers
  struct file *rf, *wf;
  int fd0, fd1;
  struct proc *p = myproc();

  if(argaddr(0, &fdarray) < 0)
    return -1;

  // 这里同理,要加判断
  if(fdarray <= myproc()->sz && fdarray >= myproc()->trapframe->sp && walkaddr(myproc()->pagetable, fdarray) == 0) {
      // printf("debug: %p %d\n", p, n);
      // 如果这个虚拟地址p没有映射,那就建立映射
      char * pa = kalloc(); // alloc physial memory ,分配一页物理内存
      if(pa == 0){ // 申请失败
        myproc()->killed = 1;
        return -1;
      }
      else{
        memset(pa, 0, PGSIZE); //清空物理内存
        if(mappages(myproc()->pagetable, PGROUNDDOWN(fdarray), PGSIZE, (uint64)pa, PTE_W|PTE_R|PTE_U) != 0){ //建立从va下取整开始一页的映射
          kfree(pa); // 分配失败,释放物理内存
          myproc()->killed = 1;
          return -1;
        }
      }
  }
...
}

测试:

== Test running lazytests == 
$ make qemu-gdb
(4.5s) 
== Test   lazy: map == 
  lazy: map: OK 
== Test   lazy: unmap == 
  lazy: unmap: OK 
== Test usertests == 
$ make qemu-gdb
(78.4s) 
== Test   usertests: pgbug == 
  usertests: pgbug: OK 
...
...
== Test   usertests: forktest == 
  usertests: forktest: OK 
== Test time == 
time: OK 
Score: 119/119
文章来源:https://blog.csdn.net/weixin_45988024/article/details/135604739
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。