不落辰

知不可乎骤得,托遗响于悲风

0%

操作系统-xv6-lab5-lazy_allocation

发表于 更新于 分类于
本文字数： 6.4k 阅读时长 ≈ 6 分钟

易知x86-64都实现了lazy allocation
例如malloc一块很大的内存，直到对这个内存进行写/读之前，都不会

为xv6实现懒分配lazy allocation

  • lazy allocation
    • 目的 : 为防止sbrk大量内存但实际上并没有使用的情况
    • 实现 : 通过 虚拟内存 和 page fault handler
      • 阶段1. 设定va为合法
        • sbrk系统调用 : 仅仅设定user的这段va是合法的，而不分配内存建立映射。
      • 阶段2. 使用va触发pagefault, 进行响应(handle)
        • pagefault handelr : 为va 分配一块physical page 并 建立映射
        • 阶段2中对于va
          • user使用无效 userva
            • MMU –检测–> trap –> pagefault handler
          • kernel使用无效 userva
            • argaddr 中检测 –> pagefault handelr
        1. pgfault handelr之后 返回到造成pgfault的指令继续执行.

背景

  • 背景：实现lazy allocation之前：也即 eager allocation
  • 通过sbrk(bytes) 向上扩展heap空间

    • 这意味着，当sbrk实际发生或者被调用的时候，内核会分配一些物理内存，并将这些内存映射到用户应用程序的地址空间，然后将内存内容初始化为0，再返回sbrk系统调用。这样，应用程序可以通过多次sbrk系统调用来增加它所需要的内存。类似的，应用程序还可以通过给sbrk传入负数作为参数，来减少或者压缩它的地址空间。我们暂且只关注内存增加
  • 在XV6中，sbrk的实现默认是eager allocation。这表示了，一旦调用了sbrk，内核会立即分配应用程序所需要的物理内存。但是实际上，对于应用程序来说很难预测自己需要多少内存，所以通常来说，应用程序倾向于申请多于自己所需要的内存。这意味着，进程的内存消耗会增加许多，但是有部分内存永远也不会被应用程序所使用到。
    • 你或许会认为这里很蠢，怎么可以这样呢？你可以设想自己写了一个应用程序，读取了一些输入然后通过一个矩阵进行一些运算。你需要为最坏的情况做准备，比如说为最大可能的矩阵分配内存，但是应用程序可能永远也用不上这些内存，通常情况下，应用程序会在一个小得多的矩阵上进行运算。所以，程序员过多的申请内存但是过少的使用内存，这种情况还挺常见的。
  • 原则上来说，这不是一个大问题。但是使用虚拟内存和page fault handler，我们完全可以用某种更聪明的方法来解决这里的问题，这里就是利用lazy allocation。

下面 称 未建立映射的va 为
只设定为合法，但是 在pgtbl中没有相应pte，或者相应的pte并没有指向物理内存

part1 and part2

  • mit教授课上做的就是

lazy alloc 核心思想

  • lazy allocation的核心思想很简单，如下。可分为两个阶段。

    • 阶段1. 设定va为合法
      • 通过sbrk系统调用
        • 设定user的这段va是合法的。通过将p->trapframe->sz增加来达成这一目的。仅仅做了这一件事。根本就没在user pgtbl上登记有关va的任何信息，也没分配physical page。
    • 阶段2. 使用va，触发pagefault 进行响应(handle)
      • 关于如何对page fault响应，大致来说就是
        • 为va 分配一块physical page
        • 将该page与触发page fault的va 在 user pgtbl中建立映射。
        • 重新执行造成 page fault的指令(如load/store)
      • 具体来讲，其阶段二也可分为两部分
        • user使用无效 userva
        • kernel使用无效 userva

  • kernel识别page fault 并进行响应 (（pagefault handler）lazy allocation的所需 )的有效信息

    • 1. 触发page fault的va
      • ($STVAL)
    • 2. 进入trap(引起page fault的)原因类型
      • ($SCAUSE)
      • 比如从user进入usertrap可能有多种原因，而属于pagefault造成的进入kernel的只有三种：instruction page fault(12) , load page fault (13), store page fault(15)
    • 3. 触发page fault的指令
      • ($SEPC) ，保存在trapframe->epc中

code

  • 更改code如下：
  • usertrap中增加handle page fault的分支（通过检测r_scause）
  • growproc:
    • sys_sbrk -> growproc。原先是立刻分配sz大小的物理内存，现在改成只增长heap顶部的上界，也即将va设定为”合法”。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      //  只有sbrk会调用到这里
      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;
              // }
              //  只设定合法但不kalloc 也不建立映射
              sz += n;
          } else if(n < 0){
              sz = uvmdealloc(p->pagetable, sz, sz + n);
          }
          p->sz = sz;
          return 0;
      }
  • isvalidva_proc
    • 检验va是否是应当进行lazy allocation的va（即是否是合法的va）（va应当是heap段的va） 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      uint64 isvalidva_proc(uint64 va)
      {
      //  Handle faults on the invalid page below the user stack.
      //  Kill a process if it page-faults on a virtual memory address higher than any allocated with sbrk().
      struct proc *p = myproc();
      if(va <= p->trapframe->sp || va >= p->sz) return 0;
          //  p->trapframe->sp trap时保留的用户栈顶
      return 1;
      }
  • uvmlazyalloc
    • 对于合法但未分配物理内存和建立映射的虚拟地址va，进行lazyalloc 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      //  对于合法但未分配物理内存和建立映射的虚拟地址va，进行lazyalloc
      void uvmlazyalloc(uint64 va)
      {
          struct proc *p = myproc();
          va = PGROUNDDOWN(va);
          //  为va申请对应的physical mem
          uint64 pa = (uint64) kalloc();
          //  oom
          if(pa == 0){
              p->killed = 1;
          }
          //  申请成功 建立映射
          else{
              memset((void*)pa,0,PGSIZE);
              //  映射
              if(mappages(p->pagetable,va,PGSIZE,pa,PTE_W|PTE_R|PTE_U)!=0){
                  //  映射失败 释放pm
                  kfree((void*)pa);
                  p->killed = 1;
              }
          }
      }
  • uvmunmap
    • 防止释放合法但还没分配物理内存建立映射的va

part3

  • uvmcopy
    • fork时会调用uvmcopy，将parent process的heap段虚拟内存对应的pte拷贝给child的pte，并且还有分配物理内存去映射。显然引入lazy之后就不能这么干了。因为很可能parent的这些虚拟内存还只不过是还未建立映射的地址。自然不应该拷贝。

bug 及 解决

  • 以上这些函数都没花多长时间就改完了。。下面这个改了好长时间：

  • 一直卡在sbrkarg test。

  • 由lazy alloc 核心思想中所述，lazy alloc可分为两个阶段：1. 设定va为合法 和 2. 触发page fault并进行响应。

  • 可具体来说，第二阶段触发page fault并进行响应可分为两种情况 — 根据在user态还是kernel态触发page fault 来分类。具体如下所示

page fault 的触发！

  • 思考问题：user态触发page fault和kernel触发有什么区别？触发后会跳转到哪里？user会进入usertrap，那么kernel会进入kernel trap吗？找到造成缺页的指令是哪条？是哪里检测出了page fault ? 当时这里没搞清晰，改bug改了一上午。见下。

    • 一开始误认为kernel 使用user传入的无效va，也会进入kernel trap（实际上不会）。结果在kernel trap里写了个page fault分支，没有反应。一直卡在sbrkarg。当时debug的时候发现会进入filewrite。改了蛮久才找出来。

  • user态和kernel态使用无效的user va所发生的反应不同，一个触发 fault，一个没有。关键是在二者使用user va的方式不同，一个是MMU硬件查找，一个是walk模拟。

user 态触发 page fault

  • user态使用了一个user 无效的va , 会导致进入usertrap 。原因见下
    • user态发生的page fault （我认为）应当是由硬件MMU检测到的
      • 为什么？因为此时cpu的$satp 是 user的pgtbl。此时是MMU来查找user pgtbl并返回pa的
    • 比如user先p = sbrk(PGSIZE); 然后赋值 *p = 100 ;
    • p是一个还没建立映射的虚拟地址
    • MMU根据va查看user的pgtbl后，发现pte是个空或者无效则会爆出pagefault，设置scause。而后进入trampoline，进入usertrap。
    • 所以我们在usertrap处写一个page fault分支，是用于处理user态造成的page fault的。对于kernel态的，无能为力。

kernel 态触发page fault（实际上并没有page fault）

  • kernel态使用了一个user 无效的va ，并不会进入kerneltrap。原因见下。
  • kernel使用user态无效的虚拟地址 发生在如下情况(简易取一种情况)
    • user将user va 通过syscall传给kernel和kernel对user va的使用流程：举例write
    • user va = sbrk(xxxx);
    • write –user va–> trampoline -> usertrap —> syscall -> sys_write —-取出user va—>filewrite —> either_copyin –> copyin –user va—> walkaddr
      • user va有效 —> 使用user va，读取
      • user va无效（未建立映射的、等待lazyalloc的地址）–> 不读取，放弃copyin,return -1。 而后一层层return -1给sys_write。回到sycall，将-1作为系统调用返回值返回给user。
  • 由此观之，也即，当kernel使用未建立映射的user va时，即userpgtbl中user va对应的pte无效或不存在时，放弃使用（读取/写入）改user va，并return -1(fail)

解决

  • 当kenerl拿到user传入给kernel的user va时，就使得va进行lazyalloc的第二步：分配物理内存并建立映射。

  • argaddr

    • 检验user va是否是heap上的user va，是没建立映射（防止重复建立映射）
    • uvmlazyalloc。为user va进行lazyalloc
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      // Retrieve an argument as a pointer.
      // Doesn't check for legality, since
      // copyin/copyout will do that.
      int
      argaddr(int n, uint64 *ip)
      {
      //  *ip为user传入的user空间的虚拟addr
      *ip = argraw(n);

      //  防止不是heap上懒分配的page
      if(!isvalidva_proc(*ip)) return 0;
      //  防止重复分配physical memory、重复mappage建立映射
      pte_t *pte = walk(myproc()->pagetable,*ip,1);
      //  当当前要使用的user的虚拟地址是一个未建立映射的虚拟地址（等待懒分配的），那么就lazyalloc它
      if((pte == 0 || (*pte & PTE_V) == 0)){
          printf("shc syscall leads to kernel page fault!\n");
          uvmlazyalloc(*ip);
      }
      return 0;
      }

  • 成功pass sbrkarg

  • 之前没改这里之前，一直卡在sbrkarg

    • 由上述解释可知，在没改之前，write会返回-1，故sbrktest会出现write sbrk failed。符合预期。

  • 改完！结束！

补充：write使用va流程图 不看也tm ok

唠叨文字版：user sbrk了一个地址 然后user使用系统调用write 并传入这个地址，比如write(fd, buf, sizeof(buf))（可以看sbrkarg，就是test这个的）。buf即为一个user态没建立映射的虚拟地址，kernel会使用（读取）这个addr。
从trampoline 进入 usertrap 进入syscall分支 进入sys_write ，在这里通过argaddr取出user传入的地址，之后调用filewrite使用了取出的user的va 。filewrite里又调用writei，wirtei调用either_copyin,either_copyin调用copyin（user的va作为srcva传入该函数）。copyin中通过walkaddr软件模拟来使用user的va，如果这个va有效，那么得到pa，然后使用pa进行一个写入。如果va无效，那么walkaddr查找pgtbl 就会没找到有效pte，就会返回0。
copyin发现pa为0，则return -1代表写入失败。顺着刚才描述的栈帧，一层层向上return，最后return -1给filewrite，然后return-1给write，回到sycall。存到trapframe，然后作为系统调用返回值返回给user层。

  • 下面这没啥p用，就是印证下理论
  • 可以看到如果不处理，就会死循环
    • 不断缺页 不断进入usertrap.c这里的 pagefault分支
    • 因为这个pagefault分支并没有对缺页做任何处理 只是直接返回到造成缺页的指令 不断执行这条指令 不断造成缺页。

理论比较

  • 和csapp上的理论上的page fault比较一下（linux也是csapp这么实现的）（图中也并没有画出kenerl如何使用无效va，只有user的pagefault 不过也正常，因为那造成的也不是page fault）
  • 相同之处 在于 当user引用为建立映射的va时，都会在dram中分配一个physical page ，去给userpgtbl建立va到pa的映射。
  • 不同之处在于并没有实现和磁盘的交换操作，只是将dram中的physical page映射给了user va。
  • 缺憾在于这样在dram满了的时候就无法再给user va 分配映射的物理内存了