650 作业回顾

这学期650做了几个作业，让我再次体会行将毕业还需用C语言来实现许多成熟功能时的心累——多么痛的领悟！

总体来说，这些作业的代码质量实在一般，都有虎头蛇尾之嫌。虽然最后分数不低，但仍自觉写得十分垃圾。
因此在此简单回顾一下这些作业中值得反思与改进的地方，为以后再写C提供一些参考。

HW1 & HW2 - my_malloc

上来头一个作业就来了个下马威。自己有大半年没有写过C程序，很多常用的变量类型和语法都有点忘了，有时也会和C++的写法搞混。加之作业的步骤写得很简略，不像551那样手把手教你如何编程，第一个星期着实有点难过。好在写了几个简单的测试程序，借助cpp.sh也找回些感觉。作业内容是设计一个程序来代替malloc/free的功能。按照我最开始的想法，直接把所有分配的块都记录下来接到一个链表上，在为每一个块设定一个是否可用的标志即可。但这个程序写出来以后用作业的测试用例一测，运行时间将近十分钟……等得花儿都谢了还以为自己写了死循环，做完饭发现跑出了结果。主要是因为全由一个链表管理时，每次分配都需要遍历链表长度数量级的节点，从而在不断malloc后消耗越来越长的时间。

改进

改进的思路有两种，一种是只记录空闲块，即每次free后才将块计入链表，并在下次分配时从空闲链表移除该节点。另一种是保留两个链表，一个记录所有分配块，另一个记录空闲块。最后，为了省事，我还是采用了后者，毕竟完整链表的代码已经写好，想着偷懒便在那基础上改。这一改反而给自己造成了更多的麻烦……

只记录空闲块有一个问题，即不知道一块内存是否由本程序分配。解决方案也很简单，可以在每块分配的内存的元数据中添加一些标识符，来确保是我们的malloc分配的内存。

另一种思路曾经考虑过用二叉树来记录空闲块，这样在使用best fit策略查找特定大小的内存时时间复杂度较低。但由于自己基本功有些差，而且这种策略在合并相邻内存难以实现，因此没有继续深究。因为sbrk函数实际上是线性地在heap上申请空间分配给data segment区，比较适合采用一个线性的数据结构来对应其位置与顺序。

合并策略

当相邻的空闲块出现在空闲链表中时，我的策略是先从当前块向前遍历到第一个连续空闲块后再向后合并所有连续空闲块。这样的设计实际上效率与直接向后合并没有太大差距，但实现起来更容易出错——毕竟，判断指针是否合法、什么条件对应如何合并需要考虑清楚。也就是这里的过于追求合并的高效，造成第二次作业改进为多线程时的无法bug free……

第二次作业

第二次作业是在第一次作业基础上将malloc分别有锁和无锁地改写为多线程程序。有锁简单，只要把之前程序中所有涉及sbrk申请内存，以及改写两个链表的部分都加上锁就可以了。这种改法在测试中完全相当于重复执行单线程程序，时间也几乎就是单线程固定的倍数，没有什么特别的。

无锁的方案利用了Thread Local Storage (TLS)变量的特性，即每个线程分别分配不同的内存，实现同名变量在线程间内存相互隔离。这时我又犯难了：究竟是推倒重来，完全用单一空闲链表的思路实现呢，还是在当前双链表的基础上改进呢？最后还是懒惰占了上风，也让我付出了不小代价：直到due前两小时还在debug，最终也没有bug free。

多线程的主要问题就在于如何合并相邻空闲块。由于sbrk分配的内存地址仍旧是线性增长的，但存到空闲块链表的相邻块地址则不一定是连续的，这时候就需要很多与边界有关的判断。交作业时候心一狠直接把合并函数注释掉了，基本不影响时间，只是增加了fragmentation的指标，没扣几分，还算幸运……

HW3 - socket_game

这次作业是第一次编写Linux socket相关的程序。在这之前，进程间通信、TCP协议的程序我是从来没有接触过，这次作业也是写得最辛苦的一次。从零开始读文档，借助老师给的例程理解SOCKET/BIND/LISTEN/ACCEPT/CONNECT/CLOSE/SEND/RECV分别是做什么的，哪个之后应该接哪个。在建立各个player之间以及与master的双向通信的图状结构时还比较顺利，等发起数据时候就乱套了。先是没有理解好select函数的作用，直到快due才明白它自己就可以同时监测多个socket/file descriptor。然后是没搞清楚socket关闭后会发生什么，于是对最后清理时出现的种种bug百思不得其解。

依旧在提交时也没能bug free，只在某些情况下能够输出正确的结果，另一些情况下对于结束条件的判断存在bug。尤其是对于这种多进程程序，没有类似于单进程valgrind调试时方便简洁的工具，只能使用最野蛮最原始的打印与断言调试法，一行一行测试哪里搞错了。相信我，这个过程比我描述得更痛苦，连续花了好几个晚上在3409 debug，每天都信心满满认为明天就能交作业，结果第二天又备受打击地继续陷入debug的困境。这也是我第一次因为程序功能没有实现完全，而非segfault或内存泄露而没有把程序写完善。

最后一点感想就是C程序员真的很辛苦。不像现代语言有许多方便的特性、易懂的预分析结果、详尽的文档与注释，C程序很多时候都得赤膊上阵自己干。哪怕是C++ 11、甚至Windows下的VC++相比之下都没有那么打击人。我曾以为VC++已经是最难读懂文档实现功能的库与语言了，直到我真正写了一些稍微复杂的C程序。

HW4 - libpqxx

经历了第三次作业的摧残，第四次作业简直是白送。完全没有任何难度，当一次调库侠，按照libpqxx的文档抄抄改改就完成了C++的简单ORM方法的封装。在这次作业中我才知道，SQL injection是多么容易避免的错误，现代的数据库这些细节已经非常完善了。同时，由于作业要求并不要求关于删改部分的操作，也没有多线程等等复杂要求，因此真的让人觉得没学到什么。

为了弥补前两次作业失掉的分数，我选择做了这次的附加题。附加题要求用现有ORM工具实现查表，按照Django的文档走一遍就好了。这也是我第一次真正写一个完整的基于Django的Model-View-Template/Form的后台服务，也第一次发现原来后台起个服务器能这么简单快捷！在这之后，学期中好几个项目我都用了Django作为后台。

HW5 - rootkit

rootkit这次作业代码量比较少，逻辑也很清楚，但我仍旧花了不少时间在debug和改进代码上。总体来说，这次作业的代码质量比之前稍有进步，由于需求很清晰，最初搭建的框架简洁明了，也基本做到了注释简明易读。只是有几个问题耽误了大量的时间。

通过cat /proc/kallsyms | grep memcpy 来查询内核中是否有memcpy这个符号。

具体逻辑跟随着作业简介，通过strace来查看不同命令调用的syscall。

内核debug

由于没有趁手的工具，debug时没法像gdb那样对全局一目了然，也没有图形化IDE的debugger那样直截了当地显示所有变量的便捷，因此我又使用了最低效的办法：注释与打印。

最开始时由于每次insmod注入后，都会发生kernel panic，令我十分烦恼。因此我采用了“增量”测试的方法——先把所有功能代码注释掉，再一个个取消注释，测试具体函数。当我全部注释掉后，才发现原来是对原函数取址时硬编码的地址写反了，造成管理分页权限的函数没有执行成功，才导致了每次都会崩溃。改好了后终于把模块跑了起来。

而后，当我插入getdents函数后又造成内核被Killed，分析后发现应该是死循环造成的，进而看到自己又犯了while循环忘记步进的低级错误。自从决定不在自己的C代码中写for后，无数次被自己坑惨，实乃自作孽不可活。🤦‍

copy_to_user

再往后，程序基本正确，但在open函数中始终无法正确执行copy_to_user这个函数。man page中并没有该函数的文档，谷歌后只在kernel.org上查到了__copy_to_user这个函数的文档。我想当然就以为二者应该是一样的，况且在GitHub上搜该函数对应的代码和文档中的用法基本一致，因此从未想过“官方”文档竟然也会出错！为了解决这个bug，花了整整两个晚上将近6小时时间，尝试了网上提到的所有copy_to_user的用法——包括改为__put_user，拷贝指针地址而非变量本身，改变缓冲区大小等等。可无论怎么改，返回值始终不是0，也就意味着函数不成功。由于我设置了类似断言的错误处理，每次都会把内核搞乱，因此每测试一次就要重启一次虚拟机，搞得我精疲力竭后，还是同学指出或许是返回状态值可能有误，才将我解脱出这篇苦海。

最后发现，原来官方文档也不能全信！一定要自己设计些小的测试用例来熟悉这些非原生的、文档不详的函数，才能避免在上面大费周章。

清理不成功

最后就是从内核移除rootkit注入模块后清理不成功。像极了个捣蛋鬼小朋友，搞乱了之后不知如何恢复原貌。我总觉得把改过的地方都恢复，按理说就能够无痛移除，但实际上会有未知的bug，在我rmmod后发生在内核中，从而扰乱与文件相关的一些服务，包括除了当前活动的session外其他ssh session断开的问题。暂时还没有想出应该如何完美清理rootkit。

总结

作为一门研究生课程，其难度我觉得只能达到本科生大二到大三之间的水平。尽管如此，我还是学到了不少知识，尤其是有关操作系统以及虚拟内存、多线程/多进程相关的之前自己非常薄弱的知识，还算收获不少。也让我有些遗憾：要是当初学了计算机相关的专业就好啦，这些知识相比起大二时令人痛苦的光学、数学物理方法，乃至之后的热统，都是既简单又富有逻辑，可操作性也很强。虽然我并不后悔自己学过些物理，窥见过美好的人类知识的高峰，但也有些遗憾——要是更早认清自己能力不足以挑战那些极其复杂的物理问题，而转而学习这些由工程师建立起的知识体系与框架，或许能掌握更多方法论的知识。孰是孰非，只能交由时间判断了！