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 的并发结构,其实结构上也很简单)。偏向策略而非实现
推荐可以对照着下面的材料看:
- 陈海波 现代操作系统
- 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 接口. 包括:
- 进程相关的 fork/exit/wait/exec
- IO 相关的 open/read/write,用户要理解两张表的概念:进程有个 fd 的表,fork 之后 fd 不变;dup 只有有一个指向不同 fd,但是同一个文件的表。跟 Dup 无关,文件资源本身有一个引用表,叫做打开文件表,共享偏移量,来做引用计数。然后有个 v-node 表,记录文件信息和 ref-cnt
- pipes, 比如 stdin stdout
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 函数和页表的标记:
- Part1 是添加一个类似 vdso 的 Page, 这个 Page 需要在
proc.c
里面申请,然后挂在struct proc
上,由freeproc
释放。同时,这里 PAGE 也需要注意挂在高位。然后剩下的内容包括低位,这里会申请内存给sz
,包括进程的元信息,GuardPage 和剩下的栈 - Part2 没啥好说的,就是使用
vmprint
, 来 visit 页表 - 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 的,为此需要:
- 我把 vm 模块添加了
uint8
的 ref_cnt 的 map, 由一个 spinlock 保护,kalloc
会递增它,kref
添加对应的refcnt
,kfree
只在 ref_cnt 为 0 的时候使用 - 在 sv39 上,借助了 RSW (软件需要的位)来使用。因为在 COW 的时候,只有
PTE_X
的页面,我才会标记成 RSW + 取消 PTE_W。我有个地方做的不太好,Cow 如果是写两遍都会标记成这样。估计ref_cnt = 1
的时候我可以不拷贝,直接改写。 - 有一些代码需要添加额外的检查,这个我查了好一会儿的 Bug,比如一些 vm 越界访问,不应该再走 walk。因为用户已经在访问错误的地址了
- 不是类型安全的带来了很多问题,我觉得不应该犯,感觉类型还是很重要的
Lab6
Lab6 要你在用户态(甚至是本机上,而不是 xv6 上)写一些并发容器。Barrier
有一点点小小难。这个 Lab 应该是最简单的 lab 了,熟悉 POSIX 线程、信号那套基本2小时内搞定
Lab7
不难,但是非常鬼畜。要你模仿一个网卡设备,处理 DMA。给了一本手册看网卡怎么处理的,然后你要在上面做内存映射文件。
这个我觉得指引不是很好,基本上在对着手册和 xv6 的 macro 照着做,而且老实说我被卡了很久…最后一看代码没改多少。
Lab8
Lab8 基本上是 scalable data structure。和 perfbook 的知识可以对上,这里有两部分:
- Scalable Allocator
- Scalable Hashtable + LRU
Lab 一个要求是数据必须是「准」的,就是不太允许出现还有资源的时候,还返回分配失败。所以很多东西需要 Steal。不过我个人喜欢从一个中心化节点保存数据,然后一些节点来这 Batch Steal,这样处理我感觉相对简单一些,锁协议也相对简单些。
Part2 相对有点小麻烦,需要你详细的做一下行为的对齐。
Lab9
比较简单,对着做就行…这里内容是:
- 添加一个 symlink 的接口并实现
- 让 FS 支持两级的索引
我觉得可以多看看 xv6 book 的 fs 一节,看看从 Log 到上层用户层 struct file
是怎么组织的,看完了写这两个 Part 基本和切菜一样。
Lab10
不难,不过算是工程量比较多的 Lab 了,基本上是 Lab3 + Lab5 结合。需要完成整个 mmap
的链路。不过有的地方比较简单,比如 mmap
没要求和 cow 结合到一起。
收获
- 线程调度了解了一些基本的机制,虽然不了解具体实现,但是,能完整阅读
boost::Context
等代码 - Syscall、中断和锁系统能够联系在一起了,也对硬件的 PMO 等接口有了初步理解,对信号的操作了解了不少
- fs 对 log 层有了一些初步了解
接下来不准备看这些附带的 paper 了,准备先看完 perfbook,感觉没什么障碍了,之后会再去看看 Linux 相关的书,了解一些具体的细节。
附上自己的一个二次元 podcast: https://www.xiaoyuzhoufm.com/episode/624b2ae7abceb019a955249b