Csapp

CSAPP学习笔记 - 计算机的概览前言 这是CSAPP集体专栏的开篇。 这本书应该不须要我过多介绍了，看这本书集体依赖了视频和书本对照学习，学习的进度很慢也比拟苦楚，不晓得多久能够更一期，做这个系列也算是激励本人加油学习。 集体感想 文科生看到这书头痛到爆炸，很多公式压根看不懂，只能重复看去背了（天知道为什么大学会跑去选个计算机的业余）。 CSAPP介绍 依照集体学习的讲述人说的话就是：这本书讲述的并不深刻，然而能够通知你理解计算机的所有重点内容 概述：理解一个HelloWorld在计算机的底层经验了什么事件一个计算机蕴含了那些根本内容。一个Hello world的C程序在计算机系统的运行程序是怎么的。操作系统和IO设施，操作系统的执行周期。一个Hello world 程序的生命周期首先，咱们从根底动手，看看一个Helloworld 程序在计算机的底层经验了哪些事件？ 预处理：将头文件退出到程序当中造成文件援用，并且生成hello.i 文件编译：把预处理的hello.i文件通过程序代码语言的优化和细节解决，通过编译之后，造成计算机翻译生成编译后文件 hello.s 文件汇编：将编译解决的文件通过机器码指令翻译为机器能辨认的汇编指令，生产 hello.o文件链接：须要将多个文件内容进行合并，比方把hello.o文件和机器汇编printf.o 件合并，生成最终须要的hello 程序 为什么要了解编译系统是如何工作的，咱们用工具调试不香么？ 优化程序性能了解链接这一步骤的异样（全局和局部变量是什么）防止安全漏洞（理解堆栈原理和缓冲器的谬误） 看这本书还能够帮忙咱们理解上面的内容 Switch 为什么有时候要替换为if/else？函数调用开销有多大？for和while那个更快？CPU的逻辑构造： PC(程序计数器)：存储着下一条寄存器指令的地址，大小为一个4字节的存储区域，实际上为一个指针。（32位4个字节，64位为8个字节）（program count） 程序计数器注意事项： 计算机中提供要从存储器中取出的下一个指令地址的寄存器PC每次自增都是固定的字长PC自增是PC+取出指令的长度一个字节占8位，一个字占16位两个指令的地位不肯定相邻 寄存器：通常为用于程序计算的一小块高速缓存，寄存器的容量比拟小。长期存放数据的空间 ALU：负责将寄存器传递的值进行计算操作。 总线：贯通整个计算机系统的外围设施，负责将数据到各个硬件进行固定的字节数据传输。 内存：负责将处理器的内容进行计算或者解决 输入输出设施：输入输出设施示意计算机系统和外部设备的接入操作 一个Hello world 程序在计算机系统的运行程序上面这个图是不便本人了解画的，画的很丑，能够去网上找很多画的难看，画的难看的集体不太能了解（HHH） 下面这个图的运行程序如下： 首先，咱们的程序从硬盘读入，通过硬盘的IO控制器通过DMA的模式间接进入到主内存。（<font color='red'>红线</font>）摘自百科：“DMA，全称为：Direct Memory Access，间接存储器拜访，是所有古代电脑的重要特色，它容许不同速度的硬件安装来沟通，而不须要依赖于 CPU 的大量中断负载。”接着程序通过主内存和IO连接器进入到寄存器中进行计算的操作，这时候有可能会应用ALU，只不过图中没有画进去。寄存器计算实现之后，输入到显示控制器，显示咱们程序的计算结果。（<font color='orange'>橙线</font>） 当然这个图也相当的简略，然而能总体概括一个程序的生命流程。 从下面的步骤能够看到，一个程序的根本步骤就是一个输出到输入的过程，这个过程称为一个环。 操作系统是如何形象IO设施，内存和处理器的?在上面的图例所示当中，咱们来看下咱们通常了解的文件，内存和处理器这三个外围组成部分在操作系统中是如何形象的： 每一个文件就是对于IO设施的形象虚拟内存是对内存和IO设施的形象过程：则是对处理器，虚拟内存和IO设施的形象什么是操作系统？它和应用程序以及硬件的关系？ 操作系统其实就是应用程序和硬件之间的一座桥梁，负责形象硬件层负责的操作逻辑，同时对于应用程序提供爱护。 操作系统将整个硬件划分为 IO设施，虚拟内存和过程这三个十分重要的形象。 操作系统中一个过程的执行周期：当零碎过程运行的时候，shell过程通过零碎调用的模式，构建一个Hello过程。此时shell保留以后过程的上下文，同时进入Hello过程，也产生一份新的hello上下文。将控制权交给Hello过程，此时shell进行期待状态hello过程执行结束，返回后果给shell过程。shell过程回到零碎过程期待下一个命令。 这里有一个思考题：shell的实现机制是如何实现了，如何实现相似shell期待的程序？ Linux：所有皆是文件如何了解？ 上文提到了一个程序其实就是一次输出/输入的过程。 文件是对IO设施的形象，也是过程以及虚拟内存的根底单元和构造组成，所以所有皆文件意味着内存中操作的所有数据都能够看做一个io的输出和输入，输出数据，输入构造，这也意味着文件作为操作系统的根底单元的重要位置。 ...

4.1 Y86-64指令集体系结构通过Y86——一个模仿X86的体系结构学习CPU构造程序员可见状态去掉了%r15，用F代表无寄存器。 Y86-64指令只反对64位。 mov：分成irmovq，rrmovq，mrmovq，rmmovq。不反对第二变址寄存器，和伸缩。即rrmovq (%rdi,%rsi,4) %rdx这样的格局。 算数运算：addq, subq, andq, xorq,这些指令会设置条件码。 残余：跳转，条件传送，call&ret，push&pop，halt指令编码与x86相似。第一个字节前四位指明指令大类，后四位指明具体行为，比方 addq=0x60。第二个字节指明REGIS A，B。 4.2逻辑设计和硬件管制语言HCL逻辑门[逻辑门类型和图形示意] 组合电路和HCL布尔表达式HCL布尔表达式都可能被转化成电路设计。比方位相等bool eq = (a && b) || (!a && !b)就能够用下图示意。而多路复用器电路bool out = (s && a) || (!s && b);（用S管制输入a/b）能够用下图示意。 字节级别将64个小电路做AND运算即可。能够形象成一个大单元。 存储器和时钟作者先提出了两类寄存器的区别。这是在前面才会学到的。硬件寄存器，是用于字传送的，程序员不可见。程序寄存器，程序员可见，就是汇编用到的那些。寄存器在电压回升是载入新值，输入原址（保留的值）。时钟管制着寄存器的加载。 4.3 Y86-64的SEQ实现SEQ硬件实现在程序实现中，一个时钟周期被分为5片（2和5常常在一起说）：1.fetch 2. decode 3.execute 4.memory 5.write back 6.pc update fetch从M[PC]中拿到指令，rA，rB，valC，valP（+8的）。检测简略谬误。 decode从寄存器失去valA，valB。 execute依据icode，决定ALU的性能，输入valE。 memory依据memo_addr,memo_data,从内存中读取/写入数据/产出谬误。他们的值从HCL中来。 write back依据dstE,valE(execute失去的），dstM,valM(memory失去的）更新指标寄存器。 SEQ的实现这个局部把下面的图拆成5个局部，每个局部用小图和HCL的形式形容进去。残缺HCL如下 fetch #SEQbool need_regids =icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ, IIRMOVQ, IRMMOVQ, IMRMOVQ };bool need_valC = icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL };decode&writeback ...

0x00 前言没有看过或者没有看到这里的小伙伴们，看到这个标题一定觉得摸不着头脑。那这里就先来解释一下背景。double poly(double a[], double x, long degree){ long i; double result = a[0]; double xpwr = x; for (i = 1; i <= degree; i++) { result += a[i] * xpwr; xpwr = x * xpwr; } return result;}double polyh(double a[], double x, long degree){ long i; double result = a[degree]; for (i = degree; i >= 0; i–) { result = a[i] + x * result; } return result;}这是 CSAPP 的两道题，每一题是一段代码，这两段代码实现了同一个功能。这两道题有一个共同的问题，比较这两段代码的性能。0x01 答案这里的答案是，poly 的性能比 polyh 的性能要高。poly 的 CPE 是 5，而 polyh 的 CPE 是 8。这就显得很尴尬了，我原以为两个函数的 CPE 都是 8。0x02 我的猜想polyh 的 CPE 是 8 我没有疑问，因为这个循环里的操作是无法并行的，也就是下一次迭代会依赖上一次迭代产生的结果。所以，CPE = 5 + 3，5 是浮点数乘法的延迟下届，3 是浮点数加法的延迟下界。poly 的 CPE 我原本认为也是 8，两个乘法是可以并行的，但是这个加法的是依赖于第一个乘法的值，无法并行，所以 CPE = 5 + 3 = 8。0x03 指令集并行和流水线上面的是我的猜想，所以我认为这里的答案是它们的 CPE 是相同的，性能也是相同的。但是如前面所写，答案并不是这样的。于是，我把之前看的东西都翻出来想了一下，真的不是这样的。现代 CPU 是有一个流水线的概念的。什么是流水线呢，想象一下汽车车间，我们造一辆汽车，是分成了很多道工序的，比如装配发动机、装车门、轮子等等。现代 CPU 也是类似的，我们看到的一条指令，在执行的时候，经历了一长串的流水线，导致了指令真正的执行顺序和我们看到的可能是不一样的，但是由于现代出来的这种机制，可以确保最后的结果是和我们看到的是一样的。0x04 解释poly 函数，在执行的时候，由于有两个浮点数乘法单元，所以 a[i] * xpwr 和 xpwr = x * xpwr 可以并行执行。而 a[i] * xpwr 可以通过流水线的数据转移，让这个加法 result + a[i] * xpwr 可以在下一次迭代的时候执行，因为每次迭代的时候，两个乘法都不会依赖 result 这个结果。这样，加法和乘法可以并行执行。浮点乘法的延迟下界是 5，浮点加法的延迟下界是 3，所以浮点乘法是关键路径，CPE 也自然就是 5 了。再来看看 polyh 函数。这个函数的循环里只有一个浮点乘法运算和一个浮点加法运算。先来看看浮点乘法运算，x * result，很显然，每一次乘法都需要依赖上一次迭代的结果，导致了加法无法和乘法并行执行。于是，CPE 就成了 5 + 3 = 8 了。0x05 最后这个例子，我觉得很有趣，因为它涉及到了一个流水线的细节。同时，也说明了，并不是操作少的代码，效率就高。本文为作者自己读书总结的文章，由于作者的水平限制，难免会有错误，欢迎大家指正，感激不尽。0x06 参考文献《深入理解计算机系统（第 3 版）》第 4、5 章 ...

第一题比较简单，但本菜鸡也做了两个小时(╯‵□′)╯︵┻━┻。。。首先打开事先已经反汇编的 bomb.s 文件，通过 bomb.c 已经知道每一关都是一个函数，它们的命名都是 phase_x，x 代表该关卡的数字，如果某个关卡输入的不正确，就会引爆炸弹 explode_bomb。首先看 main 函数的这几行400e1e: bf 38 23 40 00 mov $0x402338,%edi400e23: e8 e8 fc ff ff callq 400b10 <puts@plt>400e28: bf 78 23 40 00 mov $0x402378,%edi400e2d: e8 de fc ff ff callq 400b10 <puts@plt>400e32: e8 67 06 00 00 callq 40149e <read_line>400e37: 48 89 c7 mov %rax,%rdi400e3a: e8 a1 00 00 00 callq 400ee0 <phase_1>400e3f: e8 80 07 00 00 callq 4015c4 <phase_defused>400e44: bf a8 23 40 00 mov $0x4023a8,%edi打开 gdb，先给这一行打上断点 break *0x400e23，然后 run 起来。这里可以看到调用了 puts 这个函数，寄存器 %edi 存储的是函数的第一个参数，我们把它的结果打印出来 x/s 0x402338、x/s 0x402378，发现得到了运行 bomb 后输出的字符串。说明第一关就是从这里开始的。由于返回值是存在 %rax 中的，这里 mov %rax %rdi，说明输入的内容传参给了 phase_1。在 gdb 里给 phase_1 打断点 break phase_1。0000000000400ee0 <phase_1>: 400ee0: 48 83 ec 08 sub $0x8,%rsp 400ee4: be 00 24 40 00 mov $0x402400,%esi 400ee9: e8 4a 04 00 00 callq 401338 <strings_not_equal> 400eee: 85 c0 test %eax,%eax 400ef0: 74 05 je 400ef7 <phase_1+0x17> 400ef2: e8 43 05 00 00 callq 40143a <explode_bomb> 400ef7: 48 83 c4 08 add $0x8,%rsp 400efb: c3 retq通过这里的代码，就可以分析出来，通过调用 string_not_equal 比较输入的字符串与 0x402400 存储的字符串是否相等，来决定是不是 explode_bomb。通过这个函数名也可以知道一定要输入与 0x402400 相同的字符串就可以通过第一关了。所以在这里打个断点 break *0x400ee9，然后 x/s 0x402400 打印出来这里的字符串，我这里是 Border relations with Canada have never been better.，然后输入这个字符串，第一关就过了~string_not_equal虽然这样就过关了，但是我还是对这里的代码好奇，毕竟是学习嘛，看看这里的代码熟悉熟悉汇编。0000000000401338 <strings_not_equal>: 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 401342: 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 40135a: 75 3f jne 40139b <strings_not_equal+0x63> 40135c: 0f b6 03 movzbl (%rbx),%eax 40135f: 84 c0 test %al,%al 401361: 74 25 je 401388 <strings_not_equal+0x50> 401363: 3a 45 00 cmp 0x0(%rbp),%al 401366: 74 0a je 401372 <strings_not_equal+0x3a> 401368: eb 25 jmp 40138f <strings_not_equal+0x57> 40136a: 3a 45 00 cmp 0x0(%rbp),%al 40136d: 0f 1f 00 nopl (%rax) 401370: 75 24 jne 401396 <strings_not_equal+0x5e> 401372: 48 83 c3 01 add $0x1,%rbx 401376: 48 83 c5 01 add $0x1,%rbp 40137a: 0f b6 03 movzbl (%rbx),%eax 40137d: 84 c0 test %al,%al 40137f: 75 e9 jne 40136a <strings_not_equal+0x32> 401381: ba 00 00 00 00 mov $0x0,%edx 401386: eb 13 jmp 40139b <strings_not_equal+0x63> 401388: ba 00 00 00 00 mov $0x0,%edx 40138d: eb 0c jmp 40139b <strings_not_equal+0x63> 40138f: ba 01 00 00 00 mov $0x1,%edx 401394: eb 05 jmp 40139b <strings_not_equal+0x63> 401396: ba 01 00 00 00 mov $0x1,%edx 40139b: 89 d0 mov %edx,%eax 40139d: 5b pop %rbx 40139e: 5d pop %rbp 40139f: 41 5c pop %r12 4013a1: c3 retq看代码，发现很符合书上讲的，%r12、%rbp、%rbx 都是被调用者保存的寄存器。首先 0x401342 ~ 0x40135a，判断了它们的长度是不是相同，如果长度不相同，那么它们必然不是同一个字符串。mov $0x1,%edx 和 mov %edx,%eax 返回了 1。0x40135c ~ 0x401361 这几行，判断了所输入的字符串的第一个字符是不是 \0。因为走到这条命令，已经判断过长度是相同的了，如果其中的一个字符串的首字符是 \0，那么另外一个必然是一样的（所有的字符串一定都包含一个 \0），所以这里直接就返回 0。0x401361 ~ 0x40137f 是一个循环，它遍历了两个字符串，每一个字符是不是相同的，直到遇到 \0。string_length000000000040131b <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这个函数就比较简单了，其实就是找到 \0 的位置，然后返回其余首地址的差，即长度。这个翻译成 C 语言可以这么写。int string_length(char *s){ char *b = a; while (*b != 0) b = b + 1; return (int) (b - a);}本文是作者在看《深入理解计算机系统》以及完成 bomb lab 时的理解与总结，谨此记录下来已被日后翻阅。同时，也分享给各位希望了解这些知识的同道者们。由于作者水平有限，如有错误之处，望不吝赐教，深表感谢。 ...