ICS Lab 最终总结

Posted on Views: Symbols count in article: 5.7k Reading time ≈ 5 mins.

ICS 全部的 Lab 在今日结束了，于是给这一个学期的工作写个总结。不得不说，这堆东西耗费了本学期里最多的精力。在期末季由于阳了影响复习，ICS 以 PF 告终（于是最后一个 Lab 也摆了）。算是个十分无奈的结局，不过考虑到选这门课的目的只是学些东西，倒足以自我安慰。

1. Data Lab

Data Lab 是一系列位运算Puzzle和整数/浮点数运算Trick。第一个Lab实属“技巧性太强”，有的不参考别人的解法几乎没法做。大概记忆是痛苦的寻思和抄答案，以及写的过程是在各个咖啡馆里，其他记不清了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Correctness Results	Perf Results
Points	Rating	Errors	Points	Ops	Puzzle
1	1	0	2	4	bitAnd
1	1	0	2	4	bitConditional
2	2	0	2	15	byteSwap
3	3	0	2	6	logicalShift
4	4	0	2	9	cleanConsecutive1
4	4	0	2	24	countTrailingZero
2	2	0	2	8	divpwr2
2	2	0	2	9	oneMoreThan
3	3	0	2	14	satMul3
3	3	0	2	8	subOK
3	3	0	2	15	isLessOrEqual
4	4	0	2	11	trueThreeFourths
4	4	0	2	13	float_twice
4	4	0	2	20	float_i2f
4	4	0	2	18	float_f2i
4	4	0	2	11	float_pwr2

Score = 80/80 [48/48 Corr + 32/32 Perf] (189 total operators)

2. Bomb Lab

Bomb Lab 是“拆二进制炸弹”。反汇编得到汇编代码，然后通过分析它在干什么，或者用 gdb 在运行时跟踪它在干什么（也以此避免爆炸扣分），来找到每一个phase的答案：比如某处的字符串、跳转表、按某种要求的顺序排序的数等。当时还对程序运行时的内存结构一无所知，于是寻找这些信息是个神奇的过程。而通过每一个 phase 都很令人激动！

后面的 phase 变得很复杂，读代码十分困难（实属废了大劲），但是在运行时查看栈指针附近的内存却能很快地猜出它在干的事，这让我突然意识到 Lab 是一个“实验”。

还有些奇奇怪怪的背景设定和“mua ha ha ha”，可惜不如去年的答案中有“关注嘉然顿顿解馋”和“顶晚人和我会一直陪着你”，今年似乎只有原。

1
2
3
4
BOOM!!!
The bomb has blown up.
Your instructor has been notified.
# didn't happen #

3. Attack Lab

这个更是神奇，要进行缓冲区溢出攻击。分为没啥防备的 Code injection 攻击，以及在有栈随机化、运行权限的控制下搞的 Return-oriented 攻击。要通过溢出覆盖掉原来的返回地址，跳到我们的代码运行，Code injection 就是可以直接把代码塞进栈里，而 Return-oriented 是利用一些别处的代码片段（Gadget）进行“断章取义”然后借助 ret 指令（C3）跳来跳去。

还是在玩汇编、玩机器指令，玩得比较花。像最后一个 phase 甚至加了栈保护者（canary），但还是要通过一个内存操作的漏洞，悄悄地改变它复制的范围，然后通过巧妙测算改变 canary 下面的东西。

写这个 Lab 的时候大概是光棒录制集中的时期。参与食南京大牌档和拍片，然后又匆匆跑回来接着整，对此印象很深刻。

1
2
3
4
5
Cookie: 0xff114514
Type string:Touch3!: You called touch3("0xff114514")
Valid solution for level 3 with target starget
PASS: Sent exploit string to server to be validated.
NICE JOB!

4. Arch Lab

这个比较怪。先是写些 y86 汇编，然后给一个 SEQ 处理器添加两条指令（写 HCL），这些都好办。之后是给一个流水线（PIPE）处理器下的数组复制算法优化。方法大概是循环展开、消除加载-使用冲突等等，结果按性能给分。那段时间有点过于忙，处理器那一章是匆忙看完的。后来这个 Lab 的解法看起来很丑，而且没追求满分——满分还要去魔改处理器（是针对程序改处理器，听起来就很离谱！）

搞完这个以后就告别了汇编。

1
2
3
4
5
6
7
8
9
10
11
Autodriver: Job exited with status 0
tar -m -xf handin.tar
tar -m -xf autograde.tar
mv ./*-sum.ys ./grade/parta/handin/student-sum.ys
mv ./*-rsum.ys ./grade/parta/handin/student-rsum.ys
mv ./*-bubble.ys ./grade/parta/handin/student-bubble.ys
mv ./*seq-full.hcl ./grade/partb/handin/seq-full.hcl
mv ./*-ncopy.ys ./grade/partc/handin/student-ncopy.ys
mv ./*-pipe-full.hcl ./grade/partc/handin/student-pipe-full.hcl
cd grade; ./driver.pl
PARTA_SCORES=30 PARTB_SCORES=40 PARTC_PERFORMANCE=7.86 PARTC_SCORES=52.8

5. Cache Lab

它跨越了期中季。“擦车” Lab 是写起来比较有成就感的一个。且这是第一回需要处理命令行参数，建立一个比较完整的命令行应用——一个高速缓存模拟器。自己设计一些操作来模拟 Cache 的行为：查找、替换（LRU策略）等等，摸清 Cache 在做的几件事就可以开写（当然，启动还是依赖了网上的版本），不过 Bug 还是在不易留意之处出现。写它的时候我在外面的自习室，因为一个 Bug 搞到1点都没注意。

后半部分是做一个矩阵转置算法的性能优化，这部分除了简单的循环展开、按 Cache 的大小分块之外，我自己很难想出别的什么，于是又参考了神奇算法。卡着边界得到满点。 令人感叹，这是封校前最后的 Lab。

1
2
3
4
5
6
7
Cache Lab summary:
                        Points   Max pts      Misses
Csim correctness          27.0        27
Trans perf 32x32           8.0         8         284
Trans perf 64x64           8.0         8        1176
Trans perf 60x68          10.0        10        1599
          Total points    53.0        53

6. Shell Lab

时间变得有点紧，我决定使用 Grace Day！这阵子也比较混乱，学异常处理这一章时我感觉我就需要一个异常处理程序，进入内核态处理完再回来。目的是写一个具有任务调度功能的 Tiny Shell，要能处理 SIGINT(ctrl+c) 一类的信号，很难上手，好在框架比较完整。需要实现的只有具体的运行以及几个信号处理。虽然 writeup 上说应当别急着使用测试程序，但跟据舍友给出的经验，测试用的 trace 是循序渐进的，实现某个功能就能通过某些 trace，于是就按这个顺序来。

感谢某人的 reference。在经历了比以前痛苦但不如之后痛苦的 debug 后，分数的提升很迅速，最后在autolab上是满点（虽然在我这里有时是124/128，因为 race 存在，可能之后会查出来扣掉）。

1
2
3
4
5
6
7
......
Running 4 iters of trace31.txt
1. Running trace31.txt...
2. Running trace31.txt...
3. Running trace31.txt...
4. Running trace31.txt...
Score: 128/128

7. Malloc Lab

最大最恶的 Lab！写一个动态内存分配器，重点是堆上内存空间的管理，基本全看性能给分：包括空间利用率和吞吐量（即处理速度）。书上给出了隐式空闲链表的完整实现，简单提及显式链表和分离链表。但想要得分必须实现显式链表，满分则需要改成分离链表。这是一个逐步改进过程，而最大的问题在于 bug 无处不在。也因此，要求我们先写一个检查堆各项指标良好的函数（但这个也可能包含bug）。

我的第一阶段就是和 bug 最斗争，先是极其恶劣的 Segmentation Fault，来自毫无容错的指针运算（比较草的是，我的sigsegv几乎全出在了checkheap函数里）；然后是链表的行为完全不符合设想，又是一通狂改，狂暴 printf 输出。当我终于调好了显式链表，拿到了80+，这天我离开了学校。

又实现了几个优化，舍友在这些优化的情况下达到了88。然而我提交以后竟只有71，是吞吐量比本机低上许多。当时我正在病发编程，我一句一句地寻找性能瓶颈，不论怎么调都对这个B性能没有改进。我麻了，在跟它较劲的第二天，它的 ddl 和后面的 Proxy Lab一起改为了1.6。于是放弃搞它。

在期末考试过后，再次拾起，又经历了一阵子相同的无用优化。那时我已经认定了和舍友的版本相比，我在一个 trace 上表现极差。我分析它，却整不出个所以然来。直到决定投向玄学调参，我通过把chunksize 改成1.5甚至2倍，竟一路把分数从71调到83；接下来修改寻找空闲块的find_fit策略，由 first-fit 改成 前几个-fit，提高至87；再修改时写错了一个地方，结果竟达到 95。试图修改，可是改不得——实际上我以为写错了而毫无作用的，其实是对不同长度的链表做了不同的事。

于是收工。离ddl不远了。

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
Using default tracefiles in ./traces/
Measuring performance with a cycle counter.
Processor clock rate ~= 2000.0 MHz
......................
Results for mm malloc:
  valid  util   ops    secs     Kops  trace
   yes    77%  100000  0.006566 15231 ./traces/alaska.rep
 * yes    99%    4805  0.000481  9991 ./traces/amptjp.rep
 * yes    81%    4162  0.000204 20406 ./traces/bash.rep
 * yes    77%   57716  0.001955 29529 ./traces/boat.rep
 * yes    73%    6000  0.000957  6267 ./traces/binary2-bal.rep
 * yes    99%    5032  0.000436 11536 ./traces/cccp.rep
 * yes    99%    5848  0.000475 12320 ./traces/cccp-bal.rep
 * yes    76%   11991  0.000532 22535 ./traces/chrome.rep
 * yes    98%   20000  0.000618 32358 ./traces/coalesce-big.rep
   yes    50%   14400  0.000372 38722 ./traces/coalescing-bal.rep
   yes   100%      15  0.000003  4912 ./traces/corners.rep
 * yes    99%    5683  0.000649  8758 ./traces/cp-decl.rep
 u yes    71%      --        --    -- ./traces/exhaust.rep
 * yes   100%    5380  0.000668  8049 ./traces/expr-bal.rep
   yes   100%      15  0.000003  4912 ./traces/corners.rep
 * yes    85%   99544  0.003558 27981 ./traces/firefox-reddit2.rep
 * yes    95%   55092  0.002596 21224 ./traces/freeciv.rep
   yes    81%    1494  0.000067 22268 ./traces/perl.rep
   yes    17%      10  0.000003  3899 ./traces/malloc.rep
   yes    14%      17  0.000003  6189 ./traces/malloc-free.rep
 * yes    99%    5683  0.000874  6504 ./traces/cp-decl.rep
   yes    31%   14401  0.117897   122 ./traces/realloc.rep
14 13     89%  286936  0.014002 20492

Perf index = 56 (util) & 39 (thru) = 95/100

8. Proxy Lab

PF之后摆了（Malloc 主要是不甘心）。我本来打算留2天给这个Lab，但5号也摸了，于是只留了一天。这个 Lab 要实现一个代理服务器，再加入多线程和 Cache，还有些针对 Real Page 的鲁棒性等（不太相干的内容）。我实现了基本功能，加上几句就有了线程化。之后因为没时间写 Cache 了，Lab就此结束，拿了63/90 。由于代码与书上给出的都比较近似，还算好写，但听说针对 Real Page 的边际成本很大。

1
2
3
4
5
6
Basic: 40 / 40
Concurrency: 15 / 15
Cache: 0 / 15
Real Pages: 8 / 20

totalScore = 63 / 90

后记

在大概 shell lab 进行时，class machine 经历了一次更新，更新到 ubuntu 22。而我在用的 wsl 还是 ubuntu 20。在 make 时，发现 GLIBC 的版本不匹配，于是尝试更新。当我正完成安装时，才在网上看到 GLIBC 不可轻易升级的文章——因为它可能导致 Linux 的内核紊乱。GLIBC 是最底层的C语言库，而内核基于C，所有功能都与它有关。当安装到最后报出两条错误，我意识到惨案发生。在那之后，我无论输入什么指令，得到的响应就只有那两条错误了。于是这个 linux machine 被我玩坏了。不过对它没多少留恋，继而重装了 ubuntu 22。

一些不得不尝的经历啊。