关于操作系统:xv6-源码窥探7mmap

28次阅读

共计 7504 个字符,预计需要花费 19 分钟才能阅读完成。

前言

  • 本篇是对于 MIT 6.S081-2020-Lab10(mmap) 的实现;
  • 如果内容上发现有什么问题请不要悭吝您的键盘。

筹备工作

mmap()munmap() 这两个零碎调用自身是类 UNIX 零碎中才有的,这个试验只是仿照着实现它的一部分文件内存映射的性能(玩具)。具体 mmap() 的作用能够看看 [Linux 中的 mmap 映射 [ 一]](https://zhuanlan.zhihu.com/p/…),理解实在 Linux 中的 mmap() 作用能够为实现这次试验作一个不错的局部的参考。

正式动手做试验之前简略梳理一下我仅从这个试验的角度对 mmap() 的了解,想分明再做才是第一位。

mmap() 能够将磁盘中文件的内容拷贝到某个物理内存区域中,并在用户过程空间建设指定虚拟地址区域与这个物理内存区域之间的映射。然而在实现中,mmap() 并不会去关怀文件的内容,理论数据的拷贝动作是通过 Lazy Allocation 实现的,这也是咱们试验五做过的内容。所以 mmap() 大部分的工作将交给 kernel/trap.c 下的 user trap handler(void usertrap(void)) 去解决 page fault、调配新的内存页、拷贝文件内容,而 mmap() 自身只会做很少的相干的初始化的工作。

具体是哪些初始化工作呢?mmap() 的函数签名为 void* mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset)。参考 Lazy Allocation 里 sys_sbrk() 的实现,mmap() 会将在用户过程空间中找到一个足够大的区域,并记录参数信息,以便作为 page fault 解决时的输出。试验领导上提到,这里须要用一个构造体与 process 关联。思考到用户过程可能 mmap() 屡次文件,咱们就用一个大小为 16 的构造体数组来存储每一次 mmap() 的相干信息,这里的实现很像每个过程的关上文件表 (myproc()->ofile)。

(flags & MAP_SHARED) != 0 时,用户对内存中文件数据的任何批改最终都须要通过过程 exit 时调用 munmap() 落盘;而当 (flags & MAP_PRIVATE) != 0 时,这个内存中的文件数据则能够齐全游离于磁盘中的对应文件数据,相互之间是通明的。有个问题就是,同时有不同的过程对同一个文件落盘的时候需不需要思考同步的问题呢?必定是须要的,只有提前拿好 inode 的互斥锁用完再开释就能够了。获取 inode 锁是为了爱护 inode 援用数,并且 inode layer 会为无效屏蔽 buffer cache layer 块落盘的同步操作,咱们不必去关怀 inode layer 以下的问题。

可能须要提个醒,当 (flags & MAP_SHARED) != 0 时,在实在 Linux 的 mmap() 中对内存文件数据的批改是须要对所有映射这块内存的过程可见的。而试验这里是不须要的,就算须要,思考到地址拜访同步的问题临时也想不到从软件的层面去解决,因而试验领导上说:

It’s OK if processes that map the same MAP_SHARED file do not share physical pages.

最初当然就是 fork() 时,父子过程的内容要统一,但别忘了减少 VMA 的 struct file 的援用数。

以上根本步骤能通过 mmaptest 的局部,上面领导书上提到的可优化的空间:

  1. MAP_SHARED 页的落盘最好是先判断 PTE 的 dirty 是否有置位来选择性地操作。【√】
  2. cow_fork() 优化掉原来的 fork()。【×】

试验局部

mmap

struct vma 是外围构造体,每个过程都会有固定数量的 vma,咱们用一个长为 16 的 struct vma 数组组合到 struct proc 中。其中 valid 字段值取 1 时示意这个 vma 是闲暇的;取 0 时示意改 vma 是正被占用的。每个过程都会仅属于本人的 vma 数组,所以并不需要锁来进行访问控制。

/* kernel/proc.h */

struct vma {
  int valid;
  struct file *f;
  uint64 addr;
  uint64 length;
  int prot;
  int flags;
};

#define MAXVMASSZIE  16

// Per-process state
struct proc {
  ...
  struct vma vmas[MAXVMASSZIE];
};

在 mmap 调配 vma 的时候,须要从 myproc()->vmas 里找到一个闲暇块作为此次 mmap 占用。因为调用时用户过程没有给出映射的起始逻辑地址,这须要咱们本人在用户过程地址空间中找个适合的地位把它放进去。

回顾之前用户过程虚拟地址空间布局,咱们只能把文件内容映射到 heap 区域。但如果像 sbrk(int n) 那样从 myproc()->sz 开始调配的话,又引起大量内存外部碎片不说,到时候开释过程时的工作将会十分麻烦,在执行 void uvmfree(pagetable_t pagetable, uint64 sz) 函数时一不小心就会 panic。所以我抉择在 trapframe 的下方开始调配咱们 vma,调配开释工作都会更加简略,不必思考 myproc()->sz 的问题。所以调用调配 mmap() 调配 vma 时,会采纳 first fit 算法(首次适应算法),打算从 TRAPFRAME(MAXVA-2*PAGESIZE) 开始向低地址扫描,找到第一个可用的的地址时就把 vma 调配到这儿。

每次 mmap() 时,我都会把 vma 数组里的 vma->valid = 1 的 vma 放到数组的最右端,这样间接拿数组最右端的 vma 就是闲暇的,而后再在残余的 vma 中依据地址由高到底进行排序,排序算法就用就简略的冒泡排序。

/* kernel/sysfile.c */


void
swap_vma(struct vma* vma1, struct vma *vma2)
{if (vma1 == vma2)
    return;
  struct vma temp = *vma1;
  *vma1 = *vma2;
  *vma2 = temp;
}

void
sort_vmas(struct vma* vmas)
{  
  struct vma *l = vmas, *r = vmas+MAXVMASSZIE-1, *bound;

  if (l >= r)
    return;

  while (1) {while (l < vmas+MAXVMASSZIE && !l->valid)
      ++l;
    while (r >= vmas && r->valid)
      --r;
    if (l < r)
      swap_vma(l, r);
    else 
      break;
  }

  if (l == vmas)
    return;

  bound = r;
  struct vma *i, *max;
  
  while (vmas < bound) {
    max = vmas;
    for (i = vmas+1; i <= bound; ++i)
      max = max->addr < i->addr ? i : max;
    swap_vma(max, bound);
    --bound;
  }
}

上一部分也说过,mmap() 不会做很多工作,它只会调配并初始化 vma,并且把文件的援用数自增一而已。另外要留神,如果是以 SHARED 的形式 mmap 文件的,咱们还须要测验 flags 和文件拜访权限的一致性;PRIVATE 就不必了,因为此时内存内容不会写回源文件,你怎么批改内存内容都没关系。

/* kernel/sysfile.c */

uint64
sys_mmap(void)
{

  int prot, flags, fd, length;
  uint64 top = TRAPFRAME;

  if (argint(1, &length) < 0 || argint(2, &prot) < 0 || argint(3, &flags) < 0 || argint(4, &fd) < 0)
    return -1;

  struct proc *p = myproc();
  struct file *f = p->ofile[fd];


  if (flags & MAP_SHARED) {if (f->readable && !f->writable) 
      if (prot ^ PROT_READ) 
        return -1;
    if (!f->readable && f->writable)
      if (prot ^ PROT_WRITE)
        return -1;
  }

  sort_vmas(p->vmas);

  struct vma *vma, *res = p->vmas+MAXVMASSZIE-1;

  if (!res->valid)
    return -1;

  for (vma = p->vmas; vma < p->vmas + MAXVMASSZIE; ++vma) {if (!vma->valid) {if (top <= vma->addr && vma->addr + vma->length <= top - length) {break;} else {top = vma->addr;}
    } else {break;}
  }

  res->addr = top-length;
  res->length = length;
  res->flags = flags;
  res->prot = prot;
  res->valid = 0;
  res->f = filedup(p->ofile[fd]);

  return res->addr;
}

到了 usertrap() 这里对缺页中断的解决就跟 Lazy Allocation 很像了,都是各种异样和边界查看。新增的局部就是从文件读取内容这一块,咱们用了一个辅助函数来封装了这部分的读写逻辑。

/* kernel/trap.c */

void
usertrap(void)
{
  ...
  
  if(r_scause() == 8){...} else if (r_scause() == 13 || r_scause() == 15) {uint64 va = r_stval();
    uint64 sp = PGROUNDUP(p->trapframe->sp);

    if (va >= MAXVA || va < sp) {goto kl;} else {va = PGROUNDDOWN(va);
      pte_t *pte;

      if ((pte = walk(p->pagetable, va, 0)) != 0 && (*pte & PTE_V) != 0)
        goto kl;

      struct vma *vma;
      for (vma = p->vmas; vma < p->vmas + MAXVMASSZIE; ++vma)
        if (!vma->valid)
          if(va >= vma->addr && va+PGSIZE <= vma->addr+vma->length)
            break;
    
      if (vma == &p->vmas[MAXVMASSZIE])
        goto kl;

      char *pa = kalloc();
      if(pa != 0){if(mappages(p->pagetable, va, PGSIZE, (uint64)pa, (vma->prot << 1) | PTE_U) != 0){kfree(pa);
          goto kl;
        }
        rw_vma(vma, 1, (uint64)pa, va-vma->addr, PGSIZE);
      } else {goto kl;}
    }
  } else if((which_dev = devintr()) != 0){// ok} else {
    kl:
    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;
  }
    
  ...
      
}
/* kernel/sysfile.c */

int
rw_vma(struct vma *vma, int r, uint64 addr, uint off, uint n)
{
  struct file *f = vma->f;
  int res = 0;

  if (r) {ilock(f->ip);
    readi(f->ip, 0, addr, off, n);
    iunlock(f->ip);

    int overflow = f->ip->size - off;
    if (overflow <= PGSIZE && overflow > 0) 
      memset((char*)(addr+n-overflow), 0, overflow);
  } else {ilock(f->ip);
    begin_op();
    res = writei(f->ip, 0, addr, off, n);
    end_op();
    iunlock(f->ip);
  }

  return res;
}

这里是我踩的第一个大坑。留神到 mmap_test() 里先是关上名为 “mmap.dur” 的文件,调用 mmap() 将其映射到内存中。之后 _v1() 会读取 mmap() 调配的地址开始的 2 个 PGSIZE 字节的内容,因而总共会触发两次 page-fault 中断。尽管 usertrap() 会为这里调配两个 page,但实际上 “mmap.dur” 的文件大小只有 6144 字节,即 PGSIZE + (PGSZIE/2) 个字节。咱们读第二个页的时候,readi 只会读 PGSIZE/2 个字节就返回了,因而咱们须要在内存中残余 PGSIZE/2 空间里用 0 来进行字节填充,这也是 rw_vma() 的第一个分支外部的所干的事件。否则 _v1() 会在 PGSZIE + (PGSIZE/2) 之后读到一些奇怪的数据,导致连第一个测试都通过不了。

到了 munmap(),因为在过程退出的时候也要开释 vma,因而要把这部分逻辑放到另一个辅助函数中:

/* kernel/sysfile.c */

int
_munmap(uint64 addr, int length, struct vma *vma)
{struct proc *p = myproc();

  if (!vma) {for (vma = p->vmas; vma < p->vmas + MAXVMASSZIE; ++vma)
      if (!vma->valid)
        if (addr >= vma->addr && addr+length <= vma->addr+vma->length)
          break;

    if (vma == p->vmas+MAXVMASSZIE)
      return -1;
  } else {
    addr = vma->addr;
    length = vma->length;
  }

  if (vma->flags & MAP_SHARED)
    _uvmunmap(p->pagetable, addr, PGROUNDUP(length)/PGSIZE, vma);
  else
    _uvmunmap(p->pagetable, addr, PGROUNDUP(length)/PGSIZE, 0);

  vma->addr = vma->addr == addr ? addr+length : vma->addr;
  vma->length -= length;

  if (vma->length == 0) {fileclose(vma->f);
    vma->valid = 1;
  }

  return 0;
}

开释的逻辑很简略,先是搜寻到某个 vma 使得它的范畴可能蕴含住 addraddr + length 的这段区间。但在过程开释的时候咱们就不必这样搜寻了,能够让调用者间接传入想要开释的 vma 进来。而后在开释内存时还要分状况探讨:如果 SHARED 的内容,就须要还须要写回磁盘里;而 PRIVATE 就开释 page 就好了。因为这两个解决逻辑很像,因而它们都由 _uvmunmap() 函数来解决。

/* kernel/sysfile.c */


void
_uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, struct vma* vma)
{
  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;
    if((*pte & PTE_V) == 0)
      continue;
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");

    uint64 pa = PTE2PA(*pte);
    if (vma && *pte & PTE_D)
      rw_vma(vma, 0, PTE2PA(*pte), a-vma->addr, PGSIZE);

    kfree((void*)pa);
    *pte = 0;
  }
}

_munmap() 的逻辑能这么简略都要归功于测试不会在 vma 调配的内存区域之间 punch a hole,即测试每次都只从 vma 区域的一端开始开释,大大减小了算法的复杂度。

最初就是调配和开释过程时的一些初始化和回收逻辑:

/* kernel/pro.c */

static struct proc*
allocproc(void)
{
  struct proc *p;
  ...

found:
  ...

  for (struct vma *vma = p->vmas; vma < p->vmas + MAXVMASSZIE; ++vma) {memset(vma, 0, sizeof(struct vma));
    vma->valid = 1;
  }

  return p;
}

void
exit(int status)
{
  ...
      
  // Close all open files.
  for(int fd = 0; fd < NOFILE; fd++){if(p->ofile[fd]){struct file *f = p->ofile[fd];
      fileclose(f);
      p->ofile[fd] = 0;
    }
  }

  for (struct vma* vma = p->vmas; vma < p->vmas + MAXVMASSZIE; ++vma)
    if (!vma->valid)
      _munmap(0, 0, vma);

  ...
}

如果是跟着提醒一点一点老老实实做比拟好,但我过后看到开释过程时的 vma 的开释解决时,自认为感觉这部分逻辑放在 freeproc(struct proc *p) 里比拟好一些,因为毕竟都是在解决页表相干的逻辑嘛。写完之后发现 forktest 始终 panic: freewalk leaf,死活找不到问题在哪里。起初一个个打印了过程的 pid 时发现执行 exit() 时的过程和执行 freeproc() 的过程不一样。这时才意识到过程退出后的资源回收是父过程的工作,而我过后是通过 myproc() 来获取 struct proc 指针的,导致对父过程的页表进行开释了。这是整个试验做下来个人感觉最大的坑。

最初贴一个 make grade 截图:

后记

这个试验是后面几个试验的内容的综合利用,不须要提前看很多货色,但毕竟是 hard,想要编译几次就通过全副的测试还是比拟难的,我本人应该编译了 100 屡次吧……(汗颜)

下一篇文章应该是 6.S081 2020 最初一个网卡驱动的试验实现,届时操作系统的学习就能够临时告一段了。

正文完
 0