my experience of learning os
2022年全国大学生计算机系统能力大赛，操作系统设计赛结束了，我们队的作品tatakos，非常幸运的获得了内核赛道的一等奖。
得知这个消息的一刻，并没有想象中的激动，感觉也是在情理之中，水到渠成。
这大半年学习os和参加比赛的经历还是很宝贵的，值得记录一下。
MIT6.s081——起航
去年下半年上完os的课之后，感觉自己的理解还不够深刻，所以打算再上门网课补一下。于是寒假里开始研究MIT的6.s081课程配套的xv6，当时看的还是旧版32位x86架构的，只是对着文档阅读代码。记得当时我被x86的架构搞得晕头转向，什么“全局描述符”，“局部描述符”（假如我没有记错的话），总感觉无法理解。我甚至还通过翻译去硬啃了几章IA-32的手册，即使是这样，感觉还是没有领悟到真谛。
想着参加一下这个比赛，抱着玩玩的心态，并没有想着拿什么奖(主要还是清楚自己的水平，比较有自知之明)，我的队友yzz也有意向，于是二人一拍即合，组成一队，这个时候我还不知道自己抱上了大腿。
开学到学校后，索性换了最新版本的riscv-xv6，并且搭配2020年的实验和视频。就这样，一边看视频，一边啃手册，一边做实验。实验做的并不轻松，现在看来可能很简单的问题，但在当时就是不可逾越的鸿沟，折腾了很久也没有把程序调过，很多实验我没有做出就暂时先跳过了。什么cow啊，lazy啊，锁啊，虽然原理很简单，但是代码就是写不对，加上也不太会调试，bug改不出来。不过我由于没什么课程，时间很充足，每天就是调调程序，倒也不是很痛苦。每周去参加一下社团例会，也偶尔能调剂一下。总而言之日子过得还算惬意。
这中间和yzz的几次交谈，我逐渐意识到了队友的实力强大，我们决定就使用xv6作为基础，在这上面改，因为从零开始工作量太大了，而且去年也有不少队伍是基于xv6的，可以用作参考。从这个方面来说，xv6真可谓是这个比赛的万物起源之一了。三月底的时候，他改写了xv6的目录结构，开始移植到k210板卡上。我还是继续做xv6的实验，到了4月中旬把mmap实验做掉之后，才开始加入进来。
6.s081其实做的不是很好，因为好几个实验都没能做出来。我还打印了它课程上讲的几篇论文，打算好好的研读，都因为时间问题搁置了。但是它建立了我对os的基本印象，没有它我后面不可能走的这么远。
虚拟文件系统——入坑linux
我加入之后，当务之急是完成文件系统。比赛所使用的文件系统是fat32。我们当时还不知道是自己实现还是移植现成的。刚好初赛的测试用例中有一个mount挂载的，需要用到vfs虚拟文件系统。就想着从虚拟文件系统开始搞起吧。当时我对于这些概念还是比较混乱的，做的过程也是知识拓荒的过程。(事后回顾过来，其实这个时候的决策有些问题，应该先去做具体的文件系统fat32，先把测试样例通过了，虚拟文件系统可以后期再做，只是锦上添花)。于是开始搞吧，研究vfs的四大部件（file、dentry、inode、super_block），网上也找了不少博客，还有去年获奖的队伍xv6-k210可供参考，但是研究了几天，总感觉是浮于表面，想写代码，却不得其门而入。
这段时间yzz向我推荐了一本书professional linux kernel architecture，看其中的vfs章节，我自己也找了understanding the linux kernel，两书并行参考，后来我感觉后书看上去更舒服一些，就主要参考后书了。这两本书都是基于linux2.6内核写的，虽然已经是二十年的版本，但是一些基本原理是不会变的。于是开始对着书本，一边阅读源码，一边把搬运源码。
现在想来，那真是一段不堪回首的往事。由于内核的代码太过庞大，很多功能我们实际上是用不到的，但是我又很贪心，也想加入到我们的内核中，比如符号链接（symbolic link）；还有很多技巧性很强但是非常优雅的编码方式，比如通过把函数名作为参数，对下层的具体文件系统和RAMFS实现统一的抽象。而且内核代码各个模块的关联性还是很强的，比如vfs模块还和设备管理，文件缓存等有所关联，我在对整体没有建立起一个全面的概念的情况下，就像是盲人摸象。就这样从4月下旬从5月上旬，包括五一，我一直在理解代码，复制代码，改写代码中循环；心态差点崩溃。
这期间yzz做了包括buddy和slob内存分配模块，调试板卡，移植sd卡驱动等诸多工作，其中硬件的水很深，据他说也遇到了不少困难；我也帮不上什么忙，硬件是我的短板，我也想抽空学一下，但是脱不开身。
就这样到了五一之后，我开始有了一些头绪，之前复制的代码慢慢有了线索，简化了不少冗余的东西。虽说还是很困难，但是不至于一头雾水，做出来没问题，只是不知道还要多久，代码写好后调bug的时间更是不可控。
这时我们开了一个短会，因为差不多还有一个月初赛就要结束了，而我们的fat32还是不能支持。比起这个刚需项，vfs的优先级被降低了，经过讨论，甚至可以不用vfs。（其实最好还是做一下，后面因为没有vfs，我们很多对于ramfs的处理都不够优雅。）我们于是决定先去支持fat32.
我花了不少时间从linux上抄的代码只能暂时放放了。接下来我们两头并行，他去写fat32，我则移植现成的Fatfs作为备选项。
那段时间还是非常繁忙的，经历了社团换届，创新实践结课等诸多事宜。对于这次移植，我还闹了个笑话，由于没有搞清楚各个接口的作用就匆忙上手，我还以为Fatfs没有提供从某个偏移处开始读文件的接口，还自己去实现了一遍。现在回头看，真是愚蠢的可笑。我还就移植结果写了一篇文章。
差不多一周后，他告诉我已经可以稳定支持了。那么我就没必要继续进行这个备选方案了。
这段“抄”linux的经历虽然痛苦，还是值得的。从这里我第一次读懂了linux内核代码的一点皮毛；见识了内核开发者们是怎么编码的；也是通过vfs的学习对大型软件系统有了模块化的概念。
page cache页缓存——架构的核心
完成fat32之后，初赛的测试用例也被yzz做的差不多了，其实很多系统调用由于判题程序只检查返回值，不用真正的实现。
到目前为止，我还没有对我们的os做出实质性的贡献。刚好还有两个系统调用mmap和munmap，我由于之前在xv6的实验中做过，就由我来做了。其实这两个系统调用后面可以纳入一个更加通用的体系中，这个体系囊括了我们整个进程地址空间，只是当时我并不知道。还因为对齐的问题以及一些其他的影响做了好久。
五月下旬，yzz优化了sd卡的读写，在测试读写速度发现非常慢，读写512kb的数据需要20多秒。
经过研究发现是因为原来xv6的读写只采用了块缓存，即每次读写一个扇区（512b），特别实在qemu上面，后面会越来越慢。他还做了一个分析器，来分析函数的调用次数和时间，从而找到性能瓶颈。如果能采用多块读写也许会更快。
当时我在understanding the linux kernel上看到了页缓存（page cache），想要引入os中取代块缓存，似乎可以解决这个问题。就这样我开始做页缓存，并且优化磁盘的读写。其实我们原来的系统过初赛已经没问题了，做这些只是为了继续优化性能。
linux的页缓存的数据结构是基数树(radix tree)，我对着linux的源码边写边改。这里我还埋了一颗雷，这颗雷后面导致了bug。根本原因是基数树的高度为0时的处理，这里我做的稍显武断，就把雷给埋下了。
这个时间段我们讨论了很多关于读写的问题，什么轮询，中断，同步异步IO，是否有必要专门用一个内核线程进行读写。虽然这些东西后面都没有用到。
就这样到六月。那几天比较无聊，找了几部小说，写代码之余看看。记得还是端午假期，我一个人在实验室，外面下着大雨，实在没有心情干活了，就端着手机看《倚天屠龙记》，沉浸金庸笔下的武侠世界中。
端午之后，由于初赛过了，第一阶段的决赛试题还没有发布，算是比较轻松。我意识到自己还要考研，差不多应该准备复习了。于是捧起书，每天抽出一半的时间来复习，一半的时间写代码。进度就降下来了。
就这样，六月过半，page cache以及磁盘读写优化算是完成了，但是还有bug，我怎么也调不出来。因为bug的代码发生在buddy和slob中，还以为是yzz的内存分配模块出了问题。最中在yzz的帮助下找到了两个特别弱智的bug，一个是把变量名当作结构体名，放到sizeof中去分配内存，一个是循环时把i，j搞混了。这对我而言也是一个深刻的教训。写好代码后一定要复查。
在做的过程中，我还发现了内存和磁盘分配给同一个文件时尽量连续和有顺序性，可以增大传输的效率。
修复bug后，又测试了一下，扇区正向分配的读写速度已经可以达到1m/1s。虽然页缓存模块还比较简陋，就像一辆破车，但好歹可以跑了。
当时我们还不知道，page cache后面会成为系统架构的核心。但是这次成功的经历，给了我很大的信心。
vma——深入虚拟内存
6月下旬，yzz回家了，我还在学校里，打算继续在系统中加入页回收的功能。
翻着understanding the linux kernel，发现页回收需要用到反向映射（reverse mapping），而这本书的内核版本是2.6.11，这个版本的内核使用的是object-based reverse mapping（面向对象的反向映射），需要使用到虚拟内存区域（vma）。
当时找了一些反向映射的文章，这篇文章给我留下了深刻的映像。
在详细的了解了vma之后，发现其有更加广泛的用途，比如在处理页错误和内存保护。
于是打算先实现一下vma。还是对着linux的源码，边看边改。到了7月上旬，支持红黑树查询，合并和分裂的vma模块完成了。这中间，因为mprotect对于vma区域权限的更改非常复杂，我还犹豫了很久要不要支持，最终选择了放弃。有了vma，我还重写了mmap部分和处理页错误的部分。大致完成后，和他视频交流了一次。后来我在学校呆着也没意思，就也回了家。
七月中旬回家后，我几乎都在合并完善和debug，但是我的工作没有用得上。因为yzz在做决赛第一阶段的过程中也做了一个vma模块。
事实证明，不在学校，交流不便，对我们还是产生了不少的影响的。整个七月份我们的交流很少。初赛第一阶段几乎都是他一个人在做，由于交流不便，我跟不上他的进度，也没有帮什么忙。这个地方也是遗憾，时候反思下来确实不好。等我把vma debug完成，和前面的页缓存整合起来已经是7月下旬了。
虚拟内存区域（vma）模块，对我个人而言是比较满意的，我感觉自己做的还不错；但对我们整个项目而言就不是那么成功，因为代码没被引入到内核中。虽然后面我也想过对内核中的vma模块再进行优化，但是因为时间问题而放弃了。
虽然如此，如果没有做vma的铺垫，我后面不可能继续做页回收，所以从这个角度讲也是有意义的。
页回收——内存大统一
7月下旬，决赛第一阶段结束还有十几天吧。我终于可以腾出手来做页回收了。
从一方面讲，其实这个时候我可能更应该去帮yzz做测试用例，听他说动态链接和多线程做的等一些部分做的还是挺吃力的，好在他最后都做出了。
另一方面，由于前面我们的交流过少，我不清楚他的进度，在这上面的积累不够，也帮不上什么忙。相反继续做后面可能用到的页回收帮助更大些。
第一次先是花了一个星期阅读understanding the linux kernel，看源码，但是由于不同的页的回收方式不同，特殊的页的回收需要引入反向映射和交换（swap）技术。我当时概念还不清晰，一个星期之后，代码差不多写好了，该debug运行了。感觉实在不想看了，就放到一遍，复习了两天数学。
两天之后感觉时间比较紧迫，就又整理了一下代码，剔除掉枝叶，理出了一条主干，顺着这条主干走就舒服多了。
到了八月，第一阶段的比赛结束，我们依旧取得了满分的成绩。然而我在这一阶段并没有直接的贡献。
几天后，可以回收页缓存的页回收功能也基本完成了。
进入决赛第二阶段。这一阶段我们的交流频繁了不少，几乎每天都通过腾讯会议互相交流进展，yzz搭建好基础设施后，互相分配了任务。我们依次支持了busybox，lua，lmbench的测试用例。他又去支持了qjs等拓展应用。
这十几天的工作强度还是挺高的，经常出现bug，我们就不断循环在加入新功能，测试，修bug中。记得有一个bug是硬件bug，即k210进入执行程序时莫名卡住不动，我们从下午找到晚上，后来发现是和状态寄存器的某个位的设置有关。
这一期间，为了支持样例，更多的系统调用和新的功能被加入进内核，颇有一种融汇贯通的感觉。
值得一提的还有lmbench的最后一个用例跑不出结果，我先找了一天原因，没找到；后来yzz发现是内核用户态切换时没有保存浮点寄存器的问题；也正是这个样例的最后两个部分因为内存不足，迫切需要内存系统的升级。
于是反向映射和swap被引入到内核中。这两个部分的加入，使得几乎所有物理页的分配和回收被统一起来。
然而遗憾的是，由于最后阶段时间不足，还有bug未修掉，还是未能成功跑完它。
后记
比赛截止前的最后一天我们基本上在制作和修改ppt。第二天答辩的时间也幸运的被安排在下午。数月的辛劳，最终化为了15分钟的ppt演讲和5分钟的问答。
当一切尘埃落定，从中脱出身来，回忆起这几个月经历，有种深深的不真实感。
一路下来，特别要感谢我的队友，没有他的带领和陪伴，我不可能走的这么远。
这次收获的不仅仅是知识和能力，我还深深认识到了自己的不足。前面几次的实践的过程，明明可以做的更好，但却因为没有好好规划而留下遗憾，实在可惜。
谨以此文作为总结。
附录
项目地址：