写在前面

这是在CMU第一学期秋季上的一门神课,恶补了自己在计算机系统方面的缺陷。之所以这门课课号开头为2是推荐本科二年级来上这门课;而这门课相对应的给研究生开设的网课课号是15-513,开头为5,也就是研究生第一年应该上的基础课。

说它是基础课是因为这是一门计算机各大方面的基础大杂烩,但是烩的特别有条理性。书中从二的补码讲起,延伸到浮点数,之后到机器语言和汇编语言,堆栈格式和函数调用conventions,然后有了这些基础之后开始讲计算机体系结构和如何优化C语言程序,缓存,编译链接,虚拟内存、内存管理算法,洋洋洒洒一路讲到Unix IO,文件和网络收尾。,有一些C语言基础和Linux使用经验的人应该都可以看得懂在讲什么。其实很希望自己在本科的时候能够上一门类似的课,然而并没有。

这篇博主要描述下课程内容和收获。

课程内容

先说下这门课的评分机制:这门课评估一共分为两大部分:期中期末考试和lab,其中考试当然就是考课上教的内容,每年的题有一些题型重复很多,比如说堆栈格式,浮点数,缓存的工作原理,TLB的工作原理等等。然后每年还有一些新出的题型,不尽相同。

我觉得最有意思的是第二部分,也就是lab。lab分为七个部分,每部分相对应的也是课上所讲的特定内容。

I. Data lab

Data lab的要求简单概括,是给你一堆Puzzle,让你去用指定的操作符实现。操作符的话基本只包括C语言的位运算符。举个例子:

/* implement bitXor(x, y) using only & and ~ */

利用与运算符和非运算符去实现位运算异或。

/* implement isLessOrEqual(x,y) using ! ~ & ^ | + << >> */

利用合法操作符实现两个以二的补码表示的int类型变量的大小比较

这个lab放出来时候正在学数据的表示方式,如int二的补码,无符号数和二的补码的同一性,IEEE浮点数表示方式等等。

觉得这个lab很像脑筋急转弯。和别人聊这门课的时候我都问过,你觉得最难的lab是哪个;大部分中国人都是说malloc lab最难(第六个lab),然后我问的多数美国人都认为data lab最难而malloc lab还是很好写的。这表明了什么我不太清楚,但是我们的脑子好像确实比较适合做脑筋急转弯。今年排行榜第一名是中国学生。

II. Bomb lab

Bomb lab是我觉得很有意思的一个lab,有趣程度仅次于下一个attack lab。这个要求是说,教授给每个学生分发了一个二进制程序(炸弹),没有源码。运行这个炸弹的话会输出一行字,让你输入一串字符串才能够通过这一个phase,也就是defuse了炸弹的一部分。如果输入错误,那么炸弹会爆炸。炸弹爆炸是有后果的:每一次爆炸会直接从这个lab的成绩里减掉0.5分,所以不能用穷举法去破解,更不用说在规定时间内用穷举法在来解出这个lab的可能性很小。炸弹一共有6个phase加一个secret phase,每一层都要比上一层困难一些。

而defuse的关键就在于利用gdb或者objdump将程序反汇编之后观察其源代码,看他要求输入的字符串是什么字符串,然后其他的就是看肉眼反编译能力和想象力了。

前三个phase其实还算比较简单,其中第一个phase是明文。后面的就需要自己去推导他要的字符串是什么。最后一个phase和链表相关,所以把课上学的内容应用到lab当中也是很重要的。

最最关键的是在炸弹爆炸的那个函数加一个断点,这样就永远不会爆炸了。😃

III. Attack lab

这个lab趣味性是所有lab里最高的,和我在本科的时候自己根据兴趣去玩的东西一样。此lab就是在搞缓冲区溢出,各种形式的缓冲区溢出,从vanilla到最新的Return Oriented Programming,一层比一层好玩儿。想当年在做计算机网络实验课程助教的时候还强行给学弟学妹们展示了一下如何进行溢出攻击,但是鉴于时间窗很短可能想要展示的东西也没完全展示出来。

这个lab放出来的时候在讲堆栈和函数的调用,由于这学期第一次用第三版书作为新教材开课,讲x86-64位系统堆栈的时候和32位系统很是不同;最大的区别之一就是ebp(64位的rbp)寄存器已经不太用来当作栈帧寄存器了。但是其实栈溢出的原理都是一样的,只要有缓冲区漏洞那么就可以溢出,各种溢出。

但是我更关心的是,这个程序本身提供了一些缓冲区漏洞,但是在这个程序当中还写入了一些机制以防让这些漏洞造成比课程所要求的攻击更大的伤害。在做lab的时候没敢去做要求的攻击以外的事情,在lab之后没有仔细研究过这一点,但是这也确实是我更感兴趣的地方。这是不是相当于类似一个蜜罐系统?在内层程序外面还加了一层壳?目前还不得而知,如果以后有时间的话是要去研究研究的。不过程序本身的权限和用户权限是一样的,也没有以root身份运行,所以对系统能起到的最大影响也仍然是一个普通用户所造成的影响而已。

IV. Cache lab

讲Cache的时候做的一个lab一共分两部分;第一部分是模拟一下LRU的miss rate。第二部分相对有意思一点,要求写miss rate最低的矩阵转置函数,利用分块技术就可以,整个lab的趣味性相对其他几个lab比较低。

第一部分LRU cache simulator 不用实现O(1)的时间,没有这方面的要求,所以相对于Leetcode上的LRU Cache那道题难度上还是有差距。另外在C语言里写一个hash table难度也不小。

第二部分的话就是利用blocking,在纸上各种演算用什么算法,分块大小用多大比较合理,然后最后一个64*64的矩阵的话是要有一些创新性思维的,不能用正常的解题思维去做。这部分给我的最大启示是Sometimes, more is less.

从这个lab开始就要正经用C语言来写程序了,也是期中考试的分界点。

V. Shell lab

又称Tsh lab,要求写一个简易的Shell出来。

Shell的基本要求是能管理前后台程序,能保证多程序并行运行,父进程可以reap僵尸子进程,可以捕获Ctrl-C SIGINT和Ctrl-ZSIGTSTP并且根据当前上下文做出相应操作,可以进行I/O重定向。

这个lab 主要用的就是课程所讲的进程管理和Unix信号管理。进程管理包括用fork创造进程,用execve执行程序还有用wait来等待和回收僵尸子进程,还有关于进程组的一些内容;然后Unix信号管理主要就是signal原理,signal handler和主进程的同步还有signal handler的安装。由于signal handler和主进程是异步的,所以有一些函数最常见的如printf是不能用的。要注意的就是这一点

还有一个就是I/O重定向。在实用的Shell里都会用操作符<>提供I/O重定向的功能,在这个lab当中也是要实现的。主要原理是利用dup或者dup2系统调用把进程打开文件表中项的指针指向另外一个文件。

VI. Malloc lab

Malloc lab是这门课的大头,大头到所有我询问过的人当中绝大部分认为这个lab是所有lab当中最难的一个。甚至在malloc lab recitation刚开始的时候助教就说,也许很多人选这门课就是为了这个lab来的。这个lab也是唯一一个很难拿满分的lab,这学期最后好像只有两个人在排行榜上拿了100,据说上学期(‘15 Summer)是没有人拿100的。

这个lab要求实现自己版本的malloc, calloc, reallocfree。具体的堆空间管理要自己去实现。整个评分机制分为两部分,一是时间效率,二是空间效率。如果你的算法够快而且空间管理也足够完美的话就可以拿满分的。Malloc lab也是这门课里面唯一一个让学生去实现自己的创新思维的lab。

这里是我的malloc-lab repo

VII. Proxy lab

自己用C语言和Linux提供的函数写一个网络代理。第一反应是,居然可以自己写代理了,写完了之后可以留着给自己以后翻着墙用。然而写完之后发现只能支持HTTP,还只能玩儿GET,连POST都不行。正值期末,也没有写自己想实现的功能。

此lab主要需要的知识是网络编程、Unix I/O和线程同步。相对于其他lab来讲,这是比较简单的一个。

这里是我的proxy-lab repo

一些感受

有些人觉得C语言已经不适合这个时代,我觉得这句话半对半错。毕竟当今是大数据的时代,云计算的时代,想要玩儿数据的话用C语言确实是不合适的。但在任何时代做任何事情都是要看工具和工作的对应性的,C对于系统编程的实用性那不是一般的高。C就像一把特别锋利的匕首,想干什么就干什么,想怎么着就怎么着,但是有时候用不好可能会割伤自己。希望下学期OS的时候割伤自己这种事要少点干。

另外就是觉得这些搞系统的人真是有意思,也可能是50年前遗留下来的东西,那就是学习过程中遇到各种有趣的词,非要用一个非常稀有的词去表示一个非常大众的含义,比如说Reap,是说回收僵尸子进程,reap a zombie child,收获僵尸孩子,听起来就好吓人有木有,还有free blocks coalescing,合并就合并么还非用coalesce这么稀有的词。也许也是我的词汇量太小了,但是确实觉得系统编程的用词挺搞笑的。

写在后面

神课不多说。课业量合理,内容充实丰富有趣,收获极大。如果有机会的话非常推荐去上。