xv6 labs 2021 report

为啥会在这个节点做 xv6 lab 呢…其实最早是去年12月看 perfbook 的时候,感觉没有简单的 OS 实现的知识的话,很多东西啃的不太顺,比如 spinlock 为什么要关中断、中断的 perf 采样之类的。1月做了 lab1-2,中间基本搁置了,然后趁着居家办公这三周把所有的内容做完了。果然还是得找个不那么忙的工作才能好好学些东西…

言归正传,清明节啥都没做,基本除了录一个关于动画的 podcast、看一本厕纸基本就把这个后三个 lab 清掉了。

一些流水账

耗时:每个 lab 平均耗时大概 3-4 小时,然后看代码和 book 大概要花掉每节 1/2 的时间。加上效率低的时候,我大概 60-80 小时做完了所有的内容(没有计时,只凭回忆和每个 lab 的耗时 * (1.5 - 2.0) 算的)。有些需要看的论文暂时还没看。感觉全看完大概 100h?不知道是不是我写的太慢还是怎么回事,和我打 Baldr Sky 的时间差不多了…

每个 lab (除了 mmap )代码量不多,通常在 150loc 左右。不过你要跟着 hint 去想怎么写。这些 lab 基本上是「让你熟悉 xv6 代码」,而不是让你造一些相对复杂的数据结构(即使是 lock lab,让你造 scalable 的并发结构,其实结构上也很简单)。偏向策略而非实现

推荐可以对照着下面的材料看:

  1. 陈海波 现代操作系统
  2. rCore-Tutorial

我个人对 xv6 book 的一些笔记放在了 GitHub 上:https://github.com/mapleFU/xv6-riscv

debug 主要靠 lab4 的 backtrace。之后我把 backtrace 抽成了一个 commit, 查问题的时候 cherry-pick 上来就行了。虽说我也会用 gdb 来 debug,不过实际帮助不是很大,可能是因为代码都比较简单吧,不如 backtrace 然后查原因。

Lab1

写一些 xv6 的用户态接口。和 POSIX 接口不完全一样。

lab1 实现的时候有个坑,就是 fork 之后一定要正常 exit。这里查的时候出现了关闭的时候无法正常关闭的 bug,导致失败。

这一节介绍了 6.s081 的 user-space 接口. 包括:

  1. 进程相关的 fork/exit/wait/exec
  2. IO 相关的 open/read/write,用户要理解两张表的概念:进程有个 fd 的表,fork 之后 fd 不变;dup 只有有一个指向不同 fd,但是同一个文件的表。跟 Dup 无关,文件资源本身有一个引用表,叫做打开文件表,共享偏移量,来做引用计数。然后有个 v-node 表,记录文件信息和 ref-cnt
  3. pipes, 比如 stdin stdout
  4. cd 不是 system call,而是一个目录切换

Lab2

Lab2 内容是给 xv6 添加一些 syscall,属于没卵意思的那种。
Process 本身记录单个进程,有个 proc.h 记录结构体的内容,然后 update 这个或者读这个内容还要走 spinlock,然后:

1
void syscall(void)

这里会从寄存器找到对应的 syscall number。外部函数调用的时候也会设置这个值(user/usys.pl 会生成 .S 汇编)。

Lab3

Lab3 内容和 PageTable 结合,关键点在于 Walk 函数和页表的标记:

  1. Part1 是添加一个类似 vdso 的 Page, 这个 Page 需要在 proc.c 里面申请,然后挂在 struct proc 上,由 freeproc 释放。同时,这里 PAGE 也需要注意挂在高位。然后剩下的内容包括低位,这里会申请内存给 sz ,包括进程的元信息,GuardPage 和剩下的栈
  2. Part2 没啥好说的,就是使用 vmprint, 来 visit 页表
  3. Part3 主要在硬件 + 软件上,设置 PTE_A 来处理问题

Lab4

Lab4 其实不太难,但是我莫名其妙被卡了很久,因为几个我自己都没想明白的很弱智的问题。

  • Part1 是 calling convention 相关的问题,涉及下面几个内容 https://blog.mwish.me/2020/09/19/Integer-Endian/https://blog.mwish.me/2020/06/07/RISC-V-%E5%85%A5%E9%97%A8-Part2/ . 回答相关的问题就行了,不过我没编译过 .asm 文件,这个非常有意思
  • Part2 是一个 backtrace 的实验,这个地方有几个坑:栈目前的顶在 sp, 顶是地址最低的地方,底在 fpfp 其实不是必须的。然后有一个 ra, 是返回的指令的地址,实际上这里打印的是这个地址。这两地方我一开始都没搞清楚
  • Part3 是内核态调用户态代码,细节不太多,不过很有意思,内核要设置对应的 sepc 到别的位置,然后让它在旧的栈上执行新的代码,因为没有参数,所以没有问题。然后要恢复32个用户寄存器。为什么是 32 个呢?因为代码可能做任何事情。

Part2 对 debug 非常重要。

Lab5

Lab5 也不太难,不过查问题过程还是比较有意思的。这个 lab 需要设置成 cow 的,为此需要:

  1. 我把 vm 模块添加了 uint8 的 ref_cnt 的 map, 由一个 spinlock 保护,kalloc 会递增它,kref 添加对应的 refcntkfree 只在 ref_cnt 为 0 的时候使用
  2. 在 sv39 上,借助了 RSW (软件需要的位)来使用。因为在 COW 的时候,只有 PTE_X 的页面,我才会标记成 RSW + 取消 PTE_W。我有个地方做的不太好,Cow 如果是写两遍都会标记成这样。估计 ref_cnt = 1 的时候我可以不拷贝,直接改写。
  3. 有一些代码需要添加额外的检查,这个我查了好一会儿的 Bug,比如一些 vm 越界访问,不应该再走 walk。因为用户已经在访问错误的地址了
  4. 不是类型安全的带来了很多问题,我觉得不应该犯,感觉类型还是很重要的

Lab6

Lab6 要你在用户态(甚至是本机上,而不是 xv6 上)写一些并发容器。Barrier 有一点点小小难。这个 Lab 应该是最简单的 lab 了,熟悉 POSIX 线程、信号那套基本2小时内搞定

Lab7

不难,但是非常鬼畜。要你模仿一个网卡设备,处理 DMA。给了一本手册看网卡怎么处理的,然后你要在上面做内存映射文件。

这个我觉得指引不是很好,基本上在对着手册和 xv6 的 macro 照着做,而且老实说我被卡了很久…最后一看代码没改多少。

Lab8

Lab8 基本上是 scalable data structure。和 perfbook 的知识可以对上,这里有两部分:

  1. Scalable Allocator
  2. Scalable Hashtable + LRU

Lab 一个要求是数据必须是「准」的,就是不太允许出现还有资源的时候,还返回分配失败。所以很多东西需要 Steal。不过我个人喜欢从一个中心化节点保存数据,然后一些节点来这 Batch Steal,这样处理我感觉相对简单一些,锁协议也相对简单些。

Part2 相对有点小麻烦,需要你详细的做一下行为的对齐。

Lab9

比较简单,对着做就行…这里内容是:

  1. 添加一个 symlink 的接口并实现
  2. 让 FS 支持两级的索引

我觉得可以多看看 xv6 book 的 fs 一节,看看从 Log 到上层用户层 struct file 是怎么组织的,看完了写这两个 Part 基本和切菜一样。

Lab10

不难,不过算是工程量比较多的 Lab 了,基本上是 Lab3 + Lab5 结合。需要完成整个 mmap 的链路。不过有的地方比较简单,比如 mmap 没要求和 cow 结合到一起。

收获

  1. 线程调度了解了一些基本的机制,虽然不了解具体实现,但是,能完整阅读 boost::Context 等代码
  2. Syscall、中断和锁系统能够联系在一起了,也对硬件的 PMO 等接口有了初步理解,对信号的操作了解了不少
  3. fs 对 log 层有了一些初步了解

接下来不准备看这些附带的 paper 了,准备先看完 perfbook,感觉没什么障碍了,之后会再去看看 Linux 相关的书,了解一些具体的细节。

附上自己的一个二次元 podcast: https://www.xiaoyuzhoufm.com/episode/624b2ae7abceb019a955249b