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后面会成为系统架构的核心。但是这次成功的经历,给了我很大的信心。
![image-20220827203515524](https://raw.githubusercontent.com/DavidZyy/PicBed/master/img/image-20220827203515524.png)
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的铺垫,我后面不可能继续做页回收,所以从这个角度讲也是有意义的。
![image-20220827203232833](https://raw.githubusercontent.com/DavidZyy/PicBed/master/img/image-20220827203232833.png)
页回收——内存大统一
7月下旬,决赛第一阶段结束还有十几天吧。我终于可以腾出手来做页回收了。
从一方面讲,其实这个时候我可能更应该去帮yzz做测试用例,听他说动态链接和多线程做的等一些部分做的还是挺吃力的,好在他最后都做出了。
另一方面,由于前面我们的交流过少,我不清楚他的进度,在这上面的积累不够,也帮不上什么忙。相反继续做后面可能用到的页回收帮助更大些。
第一次先是花了一个星期阅读understanding the linux kernel,看源码,但是由于不同的页的回收方式不同,特殊的页的回收需要引入反向映射和交换(swap)技术。我当时概念还不清晰,一个星期之后,代码差不多写好了,该debug运行了。感觉实在不想看了,就放到一遍,复习了两天数学。
两天之后感觉时间比较紧迫,就又整理了一下代码,剔除掉枝叶,理出了一条主干,顺着这条主干走就舒服多了。
到了八月,第一阶段的比赛结束,我们依旧取得了满分的成绩。然而我在这一阶段并没有直接的贡献。
几天后,可以回收页缓存的页回收功能也基本完成了。
进入决赛第二阶段。这一阶段我们的交流频繁了不少,几乎每天都通过腾讯会议互相交流进展,yzz搭建好基础设施后,互相分配了任务。我们依次支持了busybox,lua,lmbench的测试用例。他又去支持了qjs等拓展应用。
这十几天的工作强度还是挺高的,经常出现bug,我们就不断循环在加入新功能,测试,修bug中。记得有一个bug是硬件bug,即k210进入执行程序时莫名卡住不动,我们从下午找到晚上,后来发现是和状态寄存器的某个位的设置有关。
这一期间,为了支持样例,更多的系统调用和新的功能被加入进内核,颇有一种融汇贯通的感觉。
值得一提的还有lmbench的最后一个用例跑不出结果,我先找了一天原因,没找到;后来yzz发现是内核用户态切换时没有保存浮点寄存器的问题;也正是这个样例的最后两个部分因为内存不足,迫切需要内存系统的升级。
于是反向映射和swap被引入到内核中。这两个部分的加入,使得几乎所有物理页的分配和回收被统一起来。
然而遗憾的是,由于最后阶段时间不足,还有bug未修掉,还是未能成功跑完它。
![image-20220827202816372](https://raw.githubusercontent.com/DavidZyy/PicBed/master/img/image-20220827202816372.png)
![image-20220827203005578](https://raw.githubusercontent.com/DavidZyy/PicBed/master/img/image-20220827203005578.png)
后记
比赛截止前的最后一天我们基本上在制作和修改ppt。第二天答辩的时间也幸运的被安排在下午。数月的辛劳,最终化为了15分钟的ppt演讲和5分钟的问答。
当一切尘埃落定,从中脱出身来,回忆起这几个月经历,有种深深的不真实感。
一路下来,特别要感谢我的队友,没有他的带领和陪伴,我不可能走的这么远。
这次收获的不仅仅是知识和能力,我还深深认识到了自己的不足。前面几次的实践的过程,明明可以做的更好,但却因为没有好好规划而留下遗憾,实在可惜。
谨以此文作为总结。
附录
项目地址: