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, 顶是地址最低的地方，底在 fp，fp 其实不是必须的。然后有一个 ra, 是返回的指令的地址，实际上这里打印的是这个地址。这两地方我一开始都没搞清楚
  • Part3 是内核态调用户态代码，细节不太多，不过很有意思，内核要设置对应的 sepc 到别的位置，然后让它在旧的栈上执行新的代码，因为没有参数，所以没有问题。然后要恢复32个用户寄存器。为什么是 32 个呢？因为代码可能做任何事情。

Part2 对 debug 非常重要。

Lab5

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

  1. 我把 vm 模块添加了 uint8 的 ref_cnt 的 map, 由一个 spinlock 保护，kalloc 会递增它，kref 添加对应的 refcnt，kfree 只在 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