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存在的问题的链接，可以参考一下。
在这里插入图片描述
根据上面的分析，我们可以将这个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中用一位标记一下：
在这里插入图片描述
查看参考手册，我们可以看到8-9位是保留位，因此我们可以把第八位用于保存COW：
在这里插入图片描述
并在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);
}

完善alloc与free：

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评分即可，这里说一下我遇到过的错：

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/63580.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【云原生】Docker-compose中所有模块学习

【云原生】Docker-compose中所有模块学习

compose模块 模板文件是使用 Compose 的核心&#xff0c;涉及到的指令关键字也比较多。但大家不用担心&#xff0c;这里面大部分指令跟 docker run 相关参数的含义都是类似的。 默认的模板文件名称为 docker-compose.yml&#xff0c;格式为 YAML 格式。 version: "3&quo…
阅读更多...
【从零学习python 】02. 开发工具介绍

【从零学习python 】02. 开发工具介绍

文章目录 编写Python代码一、常见的代码编辑工具二、运行Python程序三、Pycharm的下载和安装PyCharm的主要功能区域进阶案例 编写Python代码 根据我们之前介绍的知识&#xff0c;我们知道&#xff0c;所谓代码其实就是将一段普通文本按照一定的规范编写&#xff0c;然后交给电…
阅读更多...
人工智能的缺陷

人工智能的缺陷

首先从应用层面理解什么是人工智能&#xff0c;目前人工智能主流应用面包括&#xff1a;自然语言处理领域&#xff0c;代表为chatgpt&#xff0c;我们能用其进行日常交流&#xff0c;问题答疑&#xff0c;论文书写等。计算机视觉领域&#xff0c;代表为人脸识别&#xff0c;现在…
阅读更多...
百度UEditor编辑器如何关闭抓取远程图片功能

百度UEditor编辑器如何关闭抓取远程图片功能

百度UEditor编辑器如何关闭抓取远程图片功能 这个坑娘的功能&#xff0c;开始时居然不知道如何触发&#xff0c;以为有个按钮&#xff0c;点击一下触发&#xff0c;翻阅了文档&#xff0c;没有发现&#xff0c;然后再网络上看到原来是复制粘贴非白名单内的图片到编辑框时触发&a…
阅读更多...
centos7 yum源安装出错及更新问题

centos7 yum源安装出错及更新问题

如下 首先&#xff0c;在搜索jdk时报错如下&#xff1a; 解决办法 1、进入 yum的repo目录 cd /etc/yum.repos.d/2、修改所有的CentOS文件内容 sed -i s/mirrorlist/#mirrorlist/g /etc/yum.repos.d/CentOS-*sed -i s|#baseurlhttp://mirror.centos.org|baseurlhttp://vau…
阅读更多...
Rust 编程小技巧摘选(7)

Rust 编程小技巧摘选(7)

Rust 编程小技巧(7) 1. 结构体 Display trait 结构体的两种形式&#xff0c;对应的成员取法不同&#xff1b; 前者用 self.成员变量名 self.x, self.y&#xff1b;后者用 self.成员索引号 self.0, self.1, self.2, ...... use std::fmt::Display; use std::fmt::Result; us…
阅读更多...
如何从 Android 设备恢复已删除的文件？

如何从 Android 设备恢复已删除的文件？

从 Android 设备恢复已删除的文件很简单&#xff0c;但您需要了解内部恢复和SD 卡恢复之间的区别。 目前销售的大多数 Android 设备都配备了 SD 卡插槽&#xff08;通常为 microSD&#xff09;&#xff0c;可以轻松添加额外的存储空间。该存储空间可用于存储照片、视频、文档&a…
阅读更多...
配置Hive远程服务详细步骤

配置Hive远程服务详细步骤

HiveServer2支持多客户端的并发和认证&#xff0c;为开放API客户端如JDBC、ODBC提供了更好的支持。 &#xff08;1&#xff09;修改hive-site.xml&#xff0c;在文件中添加以下内容&#xff1a; <property><name>hive.metastore.event.db.notification.api.auth&l…
阅读更多...
ArcGIS Pro简介下载安装地址

ArcGIS Pro简介下载安装地址

ArcGIS Pro简介 ArcGIS Pro是一款功能强大的地理信息系统&#xff08;GIS&#xff09;软件&#xff0c;由Esri开发。它为用户提供了一种直观、灵活且高效的方式来处理、分析和可视化地理数据。ArcGIS Pro具有现代化的用户界面和工作流程&#xff0c;使用户能够更好地利用地理信…
阅读更多...
【Linux】节点之间配置免密登录

【Linux】节点之间配置免密登录

文章目录 1、实现2、原理3、SSH的理解 1、实现 先写实现&#xff0c;解决问题后有兴趣的自己看后面的原理。 以实现节点A&#xff08;主&#xff09;免密登录到节点B&#xff08;从&#xff09;为例&#xff1a;&#xff08;注意例子里节点B被登录&#xff09; 步骤一&#xf…
阅读更多...
L2CS-Net: 3D gaze estimation

L2CS-Net: 3D gaze estimation

L2CS-Net: Fine-Grained Gaze Estimation in Unconstrained Environments论文解析 摘要1. 简介2. Related Work3. METHOD3.1 Proposed loss function3.2 L2CS-Net 结构3.3 数据集3.4 评价指标 4. 实验4.1 实验结果 论文地址&#xff1a;L2CS-Net: Fine-Grained Gaze Estimation…
阅读更多...
Mysql主从复制-主库/从库

Mysql主从复制-主库/从库

介绍 mysql的主从复制是一个异步的复制过程&#xff0c;底层是基于Mysql数据库自带的二进制日志功能&#xff0c;就是一台或多台数据库&#xff08;slave,从库&#xff09;从另一台MYSQL数据库&#xff08;master,主库&#xff09;进行日志的复制然后再解析并应用到自己&#…
阅读更多...
IO进程线程第五天（8.2）进程函数＋XMind（守护进程（幽灵进程），输出一个时钟，终端输入quit时退出时钟）

IO进程线程第五天（8.2）进程函数＋XMind（守护进程（幽灵进程），输出一个时钟，终端输入quit时退出时钟）

1.守护进程&#xff08;幽灵进程&#xff09; #include<stdio.h> #include<head.h> int main(int argc, const char *argv[]) {pid_t cpid fork();if(0cpid){ //创建新的会话pid_t sidsetsid();printf("sid%d\n",sid);//修改运行目录为不可卸载的文件…
阅读更多...
K8S系列文章之 自动化运维利器 Ansible

K8S系列文章之 自动化运维利器 Ansible

Ansible-安装 第一步&#xff1a;安装我们的epel扩展源 yum -y install epel-release 我这里会报/var/run/yum.pid 已被锁定&#xff0c;如果没有直接进行下一步 [rootmaster home]# yum -y install epel-release 已加载插件&#xff1a;fastestmirror, langpacks /var/run/…
阅读更多...
计算机网络—TCP和UDP、输入url之后显示主页过程、TCP三次握手和四次挥手

计算机网络—TCP和UDP、输入url之后显示主页过程、TCP三次握手和四次挥手

TCP基本认识 TCP是面向连接的、可靠的&#xff0c;基于字节流的传输层通信协议。 图片来源小林coding 序号&#xff1a;传输方向上字节流的字节编号。初始时序号会被设置一个随机的初始值&#xff08;ISN&#xff09;&#xff0c;之后每次发送数据时&#xff0c;序号值 ISN…
阅读更多...
【网络】DNS、ICMP、NAT

【网络】DNS、ICMP、NAT

目录 一、DNS(Domain Name System) 1、DNS背景 2、域名简介 二、ICMP协议 1、ICMP功能 2、ICMP的报文格式 3、ping命令 4、traceroute命令 三、NAT技术 1、NAT技术背景 2、NAT IP转换过程 3、NAPT 4、NAT技术的缺陷 5、NAT和代理服务器 一、DNS(Domain Name Syste…
阅读更多...
QtWebApp开发https服务器，完成客户端与服务器基于ssl的双向认证，纯代码操作

QtWebApp开发https服务器，完成客户端与服务器基于ssl的双向认证，纯代码操作

引言&#xff1a;所谓http协议&#xff0c;本质上也是基于TCP/IP上服务器与客户端请求和应答的标准&#xff0c;web开发中常用的http server有apache和nginx。Qt程序作为http client可以使用QNetworkAccessManager很方便的进行http相关的操作。Qt本身并没有http server相关的库…
阅读更多...
【零基础学Rust | 基础系列 | 数据结构】元组，数组，向量，字符串，结构体

【零基础学Rust | 基础系列 | 数据结构】元组，数组，向量，字符串，结构体

文章标题 简介&#xff1a;一&#xff0c;元组&#xff1a;1&#xff0c;定义元组&#xff1a;2&#xff0c;访问元组元素&#xff1a;3&#xff0c;元组解构&#xff1a;4&#xff0c;元组在函数中的应用&#xff1a; 二&#xff0c;数组&#xff1a;1&#xff0c;数组的声明和…
阅读更多...
GG修改器安装与Root环境的安装

GG修改器安装与Root环境的安装

关于GG修改器大家应该都有一定的了解吧&#xff0c;就是类似于电脑端CE的一个软件。 GG修改器在百度云盘里请自行下载&#xff01; 百度网盘链接&#xff1a;https://pan.baidu.com/s/1p3KJRg9oq4s0XzRuEIBH4Q 提取码&#xff1a;vuwj 那我要开始了&#xff01; 本来不想讲GG…
阅读更多...
【状态估计】一维粒子滤波研究（Matlab代码实现）

【状态估计】一维粒子滤波研究（Matlab代码实现）

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…
阅读更多...
最新文章

Copyright @ 2022~2023