6.s081/6.1810(Fall 2022)Lab5: Copy-on-Write Fork for xv6

这篇具有很好参考价值的文章主要介绍了6.s081/6.1810(Fall 2022)Lab5: Copy-on-Write Fork for xv6。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

本来往年这里还有个Lazy Allocation的,今年不知道为啥直接给跳过去了。.

其他篇章

环境搭建
Lab1: Utilities
Lab2: System calls
Lab3: Page tables
Lab4: Traps
Lab5: Copy-on-Write Fork for xv6

参考链接

官网链接
xv6手册链接,这个挺重要的,建议做lab之前最好读一读。
xv6手册中文版,这是几位先辈们的辛勤奉献来的呀!再习惯英文文档阅读我还是更喜欢中文一点,开源无敌!
个人代码仓库
官方文档

1. 简单分析

写时拷贝(Copy On Write)技术之前在15445也写过了,这里再简单介绍一下。我们知道,fork的过程有一条就是子进程会拷贝父进程的内存空间,但是这个拷贝是有一定开销的,尤其是在需要拷贝的东西多的时候更明显。但是这就引出了一个问题——我们真的需要去拷贝吗?很显然,从逻辑上来看,只有父进程或子进程对内存空间有修改时,这种拷贝才是有意义的,否则只是徒增开销而已。依此便提出了COW思想——我们将拷贝的时机推迟到某个进程修改内存的时候,这样就可以优化掉很多无必要的开销。

落实到实现策略上,Lab文档为我们描述了一种方案——平时fork我们只需要为父子进程添加一个指向原始页面的指针即可,这个页面将被标记为只读。这样当父进程或子进程尝试写入页面时,就会触发page fault(这应该算异常吧),这个时候再由内核去重新分配内存空间,为进程提供一个可写的页面,处理结束,至此我们就基本实现了这个COW。

不过这么写产生了一个问题,即是内存释放,本来我们页面的释放是随着进程释放同步进行的,但是上面描述的策略中的进程不再持有真实的内存页面,而仅仅是一个引用,为了处理释放,我们可以采用引用计数的方法——我们可以在内存页的元信息(meta data)中单独保存一个值用于计数,当我们的进程释放时,递减引用计数,然后当计数为0时再调用内存的释放。

需要注意的是,这个过程描述起来非常简单,在xv6上的实现也不太困难,但是在实际的大型内核中总会有各种各样的细节问题,Lab提供了一个探讨COW存在的问题的链接,可以参考一下。
6.s081/6.1810(Fall 2022)Lab5: Copy-on-Write Fork for xv6,6.s081,c语言,操作系统
根据上面的分析,我们可以将这个Lab分为三个部分做:

  1. 在fork时造成内存复制的假象
  2. 处理page fault,在写时真实复制内存
  3. 使用引用计数管理内存释放

下面我们就来实现吧!

2. 在fork时实现页面复用而非复制

根据我们之前lab的经验以及lab中的hint,fork中执行页面复制的操作是在vm.c下的uvmcopy完成的:

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");
    if((*pte & PTE_V) == 0)
      panic("uvmcopy: page not present");

    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;
}

可以看到,整体的流程是先分配一个mem,然后将父进程的pa拷贝到mem中去,然后把这个mem映射到子进程上,因此我们可以直接把pa映射过去即可:

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

  for(i = 0; i < sz; i += PGSIZE){
    // 检查页表合法性
    if((pte = walk(old, i, 0)) == 0)
      panic("uvmcopy: pte should exist");
    if((*pte & PTE_V) == 0)
      panic("uvmcopy: page not present");

    *pte &= ~PTE_W; // 取消写权限
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
      goto err;
    }
  }
  return 0;

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

3. 处理page fault

触发page fault就会trap,而trap我们知道是在trap.c下的usertrap完成,而处理fault需要判断fault的类型,这在xv6里面是一个选择结构,通过r_scause()的值来判断,在去年其实有一个Lazy Allocation的Lab的,里面有告诉我们r_scause()值为13或15为页面错误,其中13为读错误,15为写错误,因此此处我们只需要处理值为15时的情况:

  else if (r_scause() == 15) {
    uint64 stval = r_stval();
    if (is_cow_fault(p->pagetable, stval)) {
      if (handle_cow_fault(p->pagetable, stval) < 0) {
        printf("usertrap(): alloc failed!\n"); 
        p->killed = 1;   // 当内存分配完,直接kill
      }
    }
    else {
      goto unexpected;
    }
  }
  else {
unexpected:
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
    setkilled(p);
  }

框架有了,我们怎么来判断一个fault是不是cow导致的呢?我们可以在PTE中用一位标记一下:
6.s081/6.1810(Fall 2022)Lab5: Copy-on-Write Fork for xv6,6.s081,c语言,操作系统
查看参考手册,我们可以看到8-9位是保留位,因此我们可以把第八位用于保存COW:
6.s081/6.1810(Fall 2022)Lab5: Copy-on-Write Fork for xv6,6.s081,c语言,操作系统
并在uvmcopy处置位

    *pte |=  PTE_C; // 设置写时复制标志    

然后我们在vm.c实现上面两个函数:

int 
is_cow_fault(pagetable_t pagetable, uint64 va)
{
  if (va >= MAXVA)
    return 0;
  pte_t* pte = walk(pagetable, PGROUNDDOWN(va), 0);
  return pte && (*pte & (PTE_V | PTE_U | PTE_C));
}

int
handle_cow_fault(pagetable_t pagetable, uint64 va)
{
  va = PGROUNDDOWN(va);
  pte_t* pte = walk(pagetable, va, 0);
  if (!pte) {
    return -1;
  }
  uint64 pa = PTE2PA(*pte);
  uint flags = (PTE_FLAGS(*pte) & ~PTE_C) | PTE_W;  // 取消写时复制标志,设置写权限

  char* mem = kalloc();
  if (!mem) {
    return -1;
  }
  memmove(mem, (char*)pa, PGSIZE);
  uvmunmap(pagetable, va, 1, 1);  // 取消映射

  if (mappages(pagetable, va, PGSIZE, (uint64)mem, flags) != 0) {
    kfree(mem);
    return -1;
  }
  return 0;
}

并在defs.h创建声明

int             is_cow_fault(pagetable_t pagetable, uint64 va);
int             handle_cow_fault(pagetable_t pagetable, uint64 va);

4. 引用计数管理内存释放

首先思考一下我们的引用计数怎么实现,hint提示我们可以利用一个数组,直接映射对应页的引用计数,于是我们在kalloc.c中:

// 引用计数的锁和保存值
struct spinlock cow_ref_lock;
int cow_cnt[(PHYSTOP - KERNBASE) / PGSIZE];
#define PA2IDX(pa) (((uint64)(pa) - KERNBASE) / PGSIZE)

初始化锁:

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  initlock(&cow_ref_lock, "cow_ref_lock");  // 初始化引用计数的锁
  freerange(end, (void*)PHYSTOP);
}

然后定义自增操作与自减操作:

void
inc_ref(void* pa) // 自增引用计数
{
  acquire(&cow_ref_lock);
  cow_cnt[PA2IDX(pa)]++;
  release(&cow_ref_lock);
}

void
dec_ref(void* pa) // 自减引用计数
{
  acquire(&cow_ref_lock);
  cow_cnt[PA2IDX(pa)]--;
  release(&cow_ref_lock);
}

完善allocfree

void
kfree(void *pa)
{
  dec_ref(r);
  if (cow_cnt[PA2IDX(r)] > 0) // 只有引用计数为1时才释放
    return;

  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);

  r = (struct run*)pa;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  release(&kmem.lock);

  if(r)
  {
    cow_cnt[PA2IDX(r)] = 1;      // 将引用计数置1
    memset((char*)r, 5, PGSIZE); // fill with junk
  }
  return (void*)r;
}

然后我们思考一下什么时候引用计数需要增加呢?那应该是fork的时候,因此我们需要暴露出inc_ref(略)然后在uvmcopy中调用它:

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

  for(i = 0; i < sz; i += PGSIZE){
    // 检查页表合法性
    if((pte = walk(old, i, 0)) == 0)
      panic("uvmcopy: pte should exist");
    if((*pte & PTE_V) == 0)
      panic("uvmcopy: page not present");

    if (*pte & PTE_W) // 对于本身可写的页才去取消写权限
    {
      *pte &= ~PTE_W; // 取消写权限
      *pte |= PTE_C; // 设置写时复制标志
    }
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    if(mappages(new, i, PGSIZE, pa, flags) != 0){
      goto err;
    }
    inc_ref((void*)pa);
  }
  return 0;

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

最后还有个问题,就是对于不会触发trap的页操作,这里没有涉及到,根据提示,我们可以找到vm.c下的copyout,这个函数是通过软件访问页表,我们就仿照trap里为它新增一段逻辑:

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    if (is_cow_fault(p->pagetable, stval)) {
      if (handle_cow_fault(p->pagetable, stval) < 0) {
        printf("copyout(): alloc failed!\n");
        return -1;
      }
    }
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (dstva - va0);
    if(n > len)
      n = len;
    memmove((void *)(pa0 + (dstva - va0)), src, n);

    len -= n;
    src += n;
    dstva = va0 + PGSIZE;
  }
  return 0;
}

5. 测试

最后运行make grade评分即可,这里说一下我遇到过的错:文章来源地址https://www.toymoban.com/news/detail-632283.html

  • 终端刚开回车两下就出现 panic: uvmunmap: not aligned :
    原因是va没有对齐,在单独写的那两个函数里对vaa使用va = PGROUNDDOWN(va);即可;
  • Test file测试过不了:
    原因是copyout没有改,改了就行;

到了这里,关于6.s081/6.1810(Fall 2022)Lab5: Copy-on-Write Fork for xv6的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • lab5:深入理解进程切换

    本文主要分析 Linux 5.4.34 版本内核中进程切换的基本操作与基本代码框架。 content_switch 函数位于 Linux 内核源码目录的 kernel/sched/core.c 中,代码如下: content_switch 函数有三个参数:rq、prev、next,其中 rq 指向本次进程切换发生的 进程就绪队列;prev 和 next 分别指向切换前后进程

    2024年02月05日
    浏览(55)
  • mit6.828 - lab5笔记(上)

    unix的文件系统相关知识 unix将可用的磁盘空间划分为两种主要类型的区域: inode区域 和 数据区域 。 unix为每个文件分配一个inode,其中保存文件的 关键元数据 ,如文件的stat属性和指向文件数据块的指针。 数据区域中的空间会被分成大小相同的数据块(就像内存管理中的分

    2024年02月02日
    浏览(34)
  • 操作系统复习 MITS6.1810 lab util 记录

    介绍:主要用来熟悉下环境以及代码结构。 See kernel/sysproc.c for the xv6 kernel code that implements the sleep system call (look for sys_sleep ), user/user.h for the C definition of sleep callable from a user program, and user/usys.S for the assembler code that jumps from user code into the kernel for sleep . 代码: 单个管道一般用于

    2024年02月15日
    浏览(34)
  • 网络攻防技术-Lab5-shellcode编写实验(SEED Labs – Shellcode Development Lab)

    网络攻防技术实验,实验环境、实验说明、实验代码见 Shellcode Development Lab 1) 编译mysh.s得到二进制文件 2) 执行 1)中的二进制文件 ,结果如下图, 我们 看到运行mysh之前的PID与运行mysh之后的PID是不同的,证明我们通过mysh启动了一个新的shell。 3) 获取机器码,以便进一步

    2023年04月13日
    浏览(43)
  • MIT 6.S081 Operating System/Fall 2020 macOS搭建risc-v与xv6开发调试环境

    电脑型号:Apple M2 Pro 2023 操作系统:macOS Ventura 13.4 所以我的电脑是arm64架构的M2芯片 执行安装脚本 /bin/zsh -c \\\"$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)\\\" 镜像选哪个都无所谓,我选择的是阿里巴巴 查看安装是否成功 brew --version 执行brew的安装脚本 这步需要先安装

    2024年02月08日
    浏览(60)
  • MIT 6.S081 Lab Three

    本文为 MIT 6.S081 2020 操作系统 实验三解析。 MIT 6.S081课程前置基础参考: 基于RISC-V搭建操作系统系列 在本实验中,您将探索页表并对其进行修改,以简化将数据从用户空间复制到内核空间的函数。 开始编码之前,请阅读xv6手册的第3章和相关文件: * kernel/memlayout.h* ,它捕获了

    2024年02月09日
    浏览(48)
  • 【MTI 6.S081 Lab】traps

    本实验阅读《深入理解计算机系统》第八章异常控制流并做shell实验将会是很有帮助的 本实验探讨了如何使用陷阱实现系统调用。您将首先使用堆栈进行热身练习,然后实现用户级陷阱处理的示例。 了解一下您在6.1910(6.004)中接触到的RISC-V程序集非常重要。在您的xv6 repo中

    2024年02月15日
    浏览(47)
  • 【MIT 6.S081】Lab7: Multithreading

    本Lab比较简单,就是为xv6添加一个用户级的多线程功能,然后熟悉一下Linux下多线程编程。 笔者用时约2h 这一部分的代码不涉及内核代码,所以也比较简单,根据提示修改 user/uthread.c 中的代码即可。仿照内核中进程转换函数 swtch 的实现即可。首先,添加一个 context 上下文结

    2023年04月09日
    浏览(36)
  • MIT6.S081 - Lab2: system calls

    step1:系统调用声明 user/user.h :系统调用函数(如 int fork(void) ) step2:ecall 进入内核态 user/usys.S (该文件由 user/usys.pl 生成,后续添加函数可以在这里添加):执行如下命令 将系统调用的编号(在 kernel/syscall.h 中定义)写入 a7 寄存器 从 ecall 进入中断处理函数 step3:保存数据并

    2024年04月23日
    浏览(44)
  • MIT 6s081 lab2:system calls

    作业地址:Lab: System calls (mit.edu) Add $U/_trace to UPROGS in Makefile add a prototype for the system call to user/user.h , a stub to user/usys.pl , and a syscall number to kernel/syscall.h . The Makefile invokes the perl script user/usys.pl Add a sys_trace() function in kernel/sysproc.c that implements the new system call by remembering its argument

    2024年01月18日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包