csapp读书笔记part1

前言

本部分包含《深入理解计算机系统》第三版第一部分的内容,包含程序的结构和执行的内容。

第二章 信息的表示和处理

计算机中的一切,都是由二进制来进行表示的,理由很简单,因为计算机本质上是一台机器,而对于机器来说,二值信号非常容易被用来进行表示、存储和传输的。

在这一部分我们主要研究无符号编码、补码和浮点数。(我至今想不通当年我们大学为什么要学习反码….)。在这三者之中,我感觉重要性是补码>浮点数>>无符号(因为java里面就没有无符号数2333333)

在计算机中,最容易出现的问题就是溢出问题了,这也导致了很多漏洞的发生。C和C++共用了一套数字的运算和表示机制,而java则是更进一步,完全屏蔽了各种机器上的差异。

2.1 信息的存储

大多数计算机都会将8比特记为一个字节,并且将字节当成最小的单位。

2.1.1 十六进制表示法

这个太简单了,不多叙述。

这里多提一句,shell中自带一个叫bc的进制转化工具(当然其实远远比这个强悍)。

echo "obase=10;ibase=2;数字"|bc,其中的ibase就是原始的进制(i=input),然后obase就是目标的进制。注意!!一定要先写obase,再写ibase,否则会发生后面的数字都是用ibase进行编码的问题。

当然如果只是简单的十进制和十六进制之间的转化,直接用printf也是很方便的。%d=十进制,%x=十六进制。

2.1.2 字大小

我理解的字大小,基本就是一个寄存器的大小。目前主流的字长基本都是64位,即计算机的寻址空间有264位。

由于字大小的不同,导致了在不同机器上(主要还是32位和64位之间)longchar *的大小有了区别。一般在32位机器上longchar *是4位,而在64位机器中是8位。

2.1.3 寻址和字节序

字节序就是我们常说的大端序小端序之间的区别了。我们都知道,字节是计算机寻址的最基本的单位,也是地址的最基本的单位,那么假设我需要读取一个4字节长度的数据,它的起始地址是x,这个很容易得到,那么接下来的四个字节,是按照什么顺序来进行排序的呢?这就引出了字节序这个概念——如果按照最低位放置在低位,那么就是小端序;如果按照最低位放置在高位,那么就是大端序。

理解大端序和小端序应该还是很容易的,那么问题就是,这个对于程序员来说,意义在哪里呢?因为在日常编程中,程序运行在哪一台机器中是确定的,而这台机器无论是大端序还是小端序,似乎对于程序员来说是完全无所谓的。但是在下面的三种情况下,字节序就显得异常重要了:

  • 网络传输。最典型的就是编写socket相关的程序。如果两台机器都是小端序/大端序,那么无伤大雅,如果一台是小端序,另外一台是大端序,那么就会反过来了。
  • 阅读机器级源码的时候。比如利用hexdump查看一个二进制的程序,会发现顺序不一致。
  • 在强制类型转化的时候。强制类型转换是有可能会丢失一部分数据的,而根据顺序的不同,会导致不同的结果。

2.1.4 表示字符串

在C语言里面,字符串都是用\0(也就是null)来结尾的,默认都是用ASCII,而由于字符串本质上仅仅是一个字节数组,所以不存在什么大端序和小端序的问题,因为它的基本单位本来就是不可分的一部分,所以在任何机器上,字符串都具有更强的平台独立性。

2.1.5 表示代码

就算是完全一致的代码,到了不同的机器上面,由于编码、指令集这些的差异,最终的二进制代码往往是不同的。

2.1.6 布尔代数

在C语言中,一共有4种布尔代数的运算,它们分别是~&|^。千万记得,需要和逻辑运算符进行区分。

2.1.7 位运算

事实上,上面所说的布尔代数,完全可以应用到C语言中,也正好对应了这四种符号,C语言这四种符号可以作用于整数上。而且在我的测试中,和java的结果完全一致,也就是java完全支持这四种位运算。

2.1.8 逻辑运算

初学的时候特别容易搞混位运算和逻辑运算,因为运算符确实很相似。C语言中的逻辑运算符包含三个:&&||!。逻辑运算和位运算其实非常好区分:逻辑运算的结果一定是0和1(对应到java里面就是true或者false),而位运算则不是。还有一个重要的区别是,逻辑运算是短路运算,即如果根据第一个表达式就能确定结果,就不会去计算第二个表达式了。

我个人认为造成混淆的原因主要在于,在C语言中,只要不是0就认为是“true”,所以造成了差异。

2.1.9 移位运算

移位有两种:左移和右移。

左移的话是很简单的,因为只需要在右边补充0,然后左边的直接删掉就可以了。由于在补码中,第一位是表示符号的,所以左移完全可能导致符号位的变化。

右移的话,就稍微复杂一点了。就是是在左边补充0呢,还是在左边补充符号位。如果在左边补充0,那么就叫逻辑右移;如果在左边补充的是符号位,那么就叫算术右移。

现在目前几乎所有的编译器/机器组合都是算术右移。而在java中,java保证>>一定是算术右移,因为java还有一个>>>来代表逻辑右移。

还有一个坑:如果要移的位数太多了,超过了原来的数字的位数呢?这里我自己测试的结果是,比如一个int是32位的,那么如果你对它移动48位,那么和移动16位结果是相同的,而且编译器会给出警告。

2.2 整数表示

在这部分中,描述两种编码整数的方式,分别是补码无符号编码。补码是目前计算机中绝对的主流(默认就是补码),因为它可以表达负数,而且用了它加法会变得非常简单,如果你是java程序员,那么更加惬意了,因为java只支持补码(个人不赞成这句话,因为Character.MAX_VALUE转成int的话就是65535,但是也可以解释成java有特殊的机制),不支持无符号编码。无符号编码只能表示0和正数,我个人认为它出现的原因,是有些值肯定是正数(比如进程的pid之类的,那么如果用了补码,就会导致平白无故少了一半的表示范围。

2.2.1 整数数据类型

这里我自己打算介绍一下C语言(64位)和java中的数据差异吧。

在C语言中,char是8位的,也就是取值范围是-128~127,而在java中与之对应的,也表示一字节的则是byte。在java中的char是两字节的,存储的是unicode码,所以可以放入一个常见的中文。

2.2.2 无符号数的编码

无符号编码就特别简单,每个位对应一个2的指数幂,然后求和就可以了。

2.2.3 补码

补码其实也简单,如果最高位是1,那么就认为是负数,并且把最高位的那个弄成负数。

其实除了补码之外,还有原码和反码,但是我个人觉得,首先多两个概念容易混淆,而且这两个概念基本上不用了,所以个人建议直接略过了。

2.2.4 无符号和补码转化

其实转换很简单,只需要记住一点:对应的二进制是完全不变的,变的只是对这个二进制的解释而已。

比如在C语言里声明了一个int i = -1,然后我们知道C语言用的是补码,所以对应的十六进制就是0xFFFFFFFF,如果此时你强制类型转换,转换成了unsigned,那么在底层其实完完全全是一样的,区别只是在你使用的时候。

2.2.5 C语言中的有符号数和无符号数

C语言中的底层用的是补码,除非你手动加上了u标记。而且当执行一个运算的时候,如果其中一个是有符号的,另外一个是无符号的,那么C语言会把有符号强制转化成无符号数。

2.2.6 扩展位表示

如果要把一个大数压缩成小数,那么不可避免的会造成精度的损失。但是如果把小数扩展成大数,就有可能了。

无符号的话,就特别简单,只需要往高位加0就可以了。

有符号的话,其实也简单,只需要往高位加符号位就可以了。

2.2.7 截断数字

假设我们需要把int转成short,那么会丢失掉两个字节的数据,这样可能会导致符号的变化。

2.2.8 建议

首先先来看看,在什么情况下会出现问题:比如你声明了一个unsigned的变量,并且值为0,那么当你对它进行减一操作的时候,它会从0跳到最大的那个数字,就可能会有问题。但是如果是补码的话,就会变成-1。

其实最简单的,就是确保你的类型匹配,换句话说:不要使用无符号数。我个人也觉得,无符号数的害处远远大于它带来的益处,而且目前我们完全不缺空间了,所以放心的时候补码吧。

2.3 整数运算

基本就围绕着无符号数和补码,进行四则运算的操作。

2.3.1 无符号加法

无符号数相加很简单,就是把对应位置上的数字加起来,然后把超出最高位的删除就可以了。

而如果要检测有没有溢出,只需要判断一下和是不是比任何一个小就可以了。

2.3.2 补码加法

补码的加法比较麻烦,可能会两个很大的正数相加,结果溢出;也可能是两个很大的负数相加,发生溢出;当然也可以是正常的两个数相加,然后不发生溢出。

补码的加法对于机器来说很简单,就是我们需要知道,什么时候发生了正溢出,什么时候发生了负溢出。

2.3.3 补码的非

补码的非计算就是,对于一个补码,取反加一就是它的非(加法逆元)。

2.3.4 无符号乘法

emmmm就是二进制乘法,没什么好说的。

2.3.5 补码乘法

也没什么好说的,就是乘完然后截断一下就可以了。

2.3.6 乘以常数

显然如果是2的整数次幂,那么完全等价于左移。根据此,我们也可以推广到一般的常数,因为常数一定可以通过2的整数次幂进行加减来得到,所以可以有效的提高效率。

2.3.7 除以2的幂

注意,因为除法的特殊性,所以我们没有办法将除法从2的幂推广到所有的数字,这部分也是这一张我看的最难的部分了,所以感觉可以先跳过。

2.3.8 整数运算思考

我们可以看到,补码可以表示正数负数,同时和无符号数字一样实现了一样的加减乘除法,可以简单理解就是底层用的就是一个二进制串,然后不论是无符号数还是补码,都是用的一样的方法来操作,只不过最后对结果进行不同的解释罢了。

2.4 浮点数

大学学计算机组成原理的时候的噩梦。因为老师自己都在课上讲错了…

2.4.1 二进制小数

二进制小数还是很好表示的,就是算清楚每一位的权,然后把这些权加起来就可以了。就和十进制无法精确表示三分之一一样,二进制也有无法精确表示的数字,比如十分之一。当然了,由于计算机的空间限制,表示的数字也是有限的。所以我们需要权衡,如果把小数点移动到很左边,那么我们可以表示的小数范围可以更精确,但是整数部分的大小就很有限;反之亦然。

2.4.2 IEEE浮点表示

浮点数有一个叫规格化的东西,就是相当于确定小数点给标在哪里。规范规定了尾数的最高位是1。如果不是1,那么就进行处理,让其一定是1。

IEEE用了 V=(-1)s x M x 2E 来表示一个数字的:

  • s是一个符号位,跟补码一样,1代表负数,0代表正数。对于数字0,有特殊的处理方式。
  • M是一个二进制小数,称之为尾数,它的范围是[1,2),这主要是因为我们默认会加一处理。
  • E明显是一个权值,称为阶码,用来对浮点数进行加权。

所以我们只需要得到SME这三个数字,就可以得到浮点数了。符号位只需要一位就可以表示了,而E则是用的k位数字来进行编码,最后的M用的是n位数字来表示。

在c语言中,float称为单精度浮点数,它的k=8,n=23。而double称为双精度浮点数,它的k=11位,而n=52位。

注意!这张图里面的exp(简写为e)的值和E有关,但是两者并不相等。同样的frac的值和M也有关,但是也不相等。它们之间的关系是E=exp-bias(bias = 2k-1-1),

可以看到单精度的k是8位,所以exp的范围是1~254(注意,这里排除了解码是全1和全0的情况),而对于双精度这个k是11位,所以exp的范围是1~2046。但是实际中,我们并不是直接用这个exp,而是还要再减去一个值(bias),这个值在单精度下是127,在双精度下是1023,所以最后E的范围,在单精度下是-126~127,在双精度下是-1022~1023

最后是尾数,因为不管尾数是什么,我们总能够让尾数以1开头(也就是确认小数点的位置),而且在编码的时候可以不用表示这个1,因为规定了一定以1开头。所以我们这里相当于可以利用这个特性来多骗取一位。

如果阶码全是0,那么就是非规格化形式,非规格化下,图中的exp就都是0了,那按照道理来说E=0-bias,但是实际中却是E=1-bias,而且M也不再是frac+1了,而是就是等于frac的值。为什么这里M不再是以1开头了呢?因为如果以1开头,那么就无法表示0这个数字了。也就是,如果上图中,除了符号位全部是0,那么就代表了数字0。但是新的问题是,那就有两种零了,正零和负零。

如果阶码全是1,并且尾数是全0的时候,可以和符号位配合来表示无穷。而如果阶码全是1,但是尾数不是全0,代表的是NaN(not-a-number)

2.4.3 数字示例

这里使用十进制数字15213.0来进行说明。

  1. 把这个数字转成二进制的,这个相当容易,就是11 1011 0110 1101.0
  2. 接下来,把小数点移动到第一个1后面,并且乘以对应的2的幂次,15213.0 = 1.1101101101101 x 2^13
  3. 按照公式,我们得到了尾数M=1101101101101和阶码E=13,然后把它们俩对应转成frac和exp即可。

2.4.4 舍入

之前提到了,浮点数的这种表达方式,无法精确表达,所以只能近似处理,那么我们就希望能够找到一个浮点数,使它能够最接近我们想要表达的那个数字。

实际中有四种舍入的方法,分别是向上、向下、向零(直接去掉小数部分)和向偶数舍入(四舍六入五留双),其中向偶数舍入是默认的舍入方式。

举几个例子就完全明白了。

首先是十进制的,我需要保留两位小数,那么下面的这些值是如何进行舍入操作的呢?

  • 7.8949999,因为49999<50000,直接舍去即可,变成7.89。
  • 7.8950001,因为50001>50000,所以直接向上进位,变成7.90
  • 7.8950000,这里就需要按照偶数进位了,因为距离最近的是7.90,所以答案是7.90
  • 7.8850000,一样的做法,这里因为7.88是最近的偶数,所以答案是7.88

同样对于二进制也是成立的:

  • 10.00011,一半是100,而011<100,所以直接舍去变成10.00
  • 10.00110,同样110>100,所以544 …..直接进位,答案是10.01
  • 10.11100,这里最近的就是进位,所以是11.00
  • 10.10100,这里最近的是舍去,所以是10.10

2.4.5 浮点运算

该书并没有介绍相应的浮点数的加法乘法的实现原理,因为浮点数不像整数一样,能够对应位置进行加减法,所以浮点数的加法和乘法会比较复杂,不在掌握范围之内。你只需要了解,浮点数进行加法和乘法之后,会使用舍入,同时浮点数的加法是不符合结合律的,这对于程序员和编译器来说,都是很重要的一点,编译器不会对它进行优化。

但是浮点数还是遵循了单调性:如果a大于等于b,那么对于除了NaN的任何数字,都有a+x大于等于b+x,这个单调性反而是无符号数和补码不具有的。同样的乘法也有单调性。

2.4. 6 C语言中的浮点数

之前学习补码和无符号数之间转换的时候,其实只是改变了解释的方式,底层的位是完全没有变动的。但是到了浮点数这里,就会对底层的位模式进行转变了,而且是程序员需要了解的部分:

  • 从int到float,数字不会溢出,但是可能会被舍入
  • int和float转到double的话,是没有问题的。
  • double到float,可能会溢出,也可能会发生舍入。
  • 从float或者double到int的话,值会进行向零舍入,甚至可能会发生溢出。

2.5 小结

这部分主要介绍了两点,首先是如何表示一个整数,分成了补码和无符号数两种,并且对一些常见的操作进行了解释。在整数部分,大部分问题都是由于溢出导致的。同时也理解了浮点数是什么,针对浮点数,只需要了解如何表示它,以及如何使用它就可以了。

第三章 程序的机器级表示

这一部分开始接触汇编代码。由于现代强大的编译器的存在,导致了使用高级语言编写的程序,通过编译器生成的汇编代码,其质量和熟练的汇编语言程序员相比,也是一样的有效的,甚至由于高级语言可以使用不同的编译器来对机器生成不同的汇编代码,反而具有更好的移植能力。

那么我们为什么还需要学习汇编代码呢?因为高级语言有时候会隐藏一些细节,有的时候优化的效率也并不尽如人意,还有的时候是程序员自己为了能够理解底层的安全漏洞等等,总之,汇编语言是非常重要的,也是非常值得学习的。

3.1 处理器历史

这部分在笔记里就不多做赘述,这里只对一些经常用的概念和一些有纪念意义的CPU进行简单介绍:

  • 1978年,8086处理器诞生。
  • 1985年,i386诞生,将16位扩展到了32位。
  • 2004年,Pentium 4E诞生,实现了对IA32的64位扩展的实现,称之为x86-64

IA32是Intel-Architechture-32-bit的缩写,用来指代32位的机器。而Intel-64则是对IA32的64位扩展,当然我们实际中会称它为x86-64。而x86则是一般用来指代这一整个系列。

上面介绍的所有都是Intel的,那还有一家公司——AMD,虽然规则都是Intel来指定的,但是AMD生产的CPU是完全能够兼容这些的。

3.2 程序编码

3.2.1 机器级代码

计算机中有一种很重要的抽象,叫做ISA,Instruction Set Architecture,指令集架构。它定义了机器级程序的格式以及行为,简单来说就是规定了每条指令会发生什么。

下面是一些比较重要的处理器状态:

  • 程序计数器PC:用%rip表示,用来给出下一条将要执行的指令在内存中的地址。
  • 寄存器文件:一堆寄存器,分别存储64位的值,可以是地址、整数数据、局部变量和返回值等。
  • 条件码寄存器:保存最近执行的算术或者逻辑指令。
  • 一组向量寄存器:存放一个或者多个整数、浮点数值。

3.2.2 代码示例

随便编写一段代码,并且使用gcc -S来进行编译(-S指定gcc只使用编译器,而不进行接下来的步骤),会生成汇编文件,可以打开来看看。如果接着生成二进制文件,那么你会发现,其实对应的二进制文件只是对汇编文件的一个编码而已。

当然linux下可以使用objdump -d xx.o来反汇编二进制文件。

关于汇编指令,有一些特性值得了解:

  • 一般越常用的指令越短,符合哈夫曼编码。且一条指令的长度在1-15字节不等。
  • 仔细观察反汇编的结果和gcc给出的结果,你会发现有一些指令最后是q,存在细微的差异,这个q本质上是大小指示符(q=4字=64位),确实可以省略。

3.2.3 关于格式

仔细查看汇编文件,你会发现比较难以阅读,因为里面有很多奇怪的东西。你可以完全省略以.开头的行,因为这些行是用来指导汇编器、链接器工作的。

第二点是,默认的gcc生成的汇编代码、objdump生成的反汇编代码,用的都是AT&T格式的。而Intel和微软则是用的另外一种格式。这两种格式最大的区别就是:它们之间的两个寄存器的位置是相反的,令人疑惑。

3.3 数据格式

Intel用术语“字”(word)表示16位的数据(即short),因此32位称为双字、64位称为四字。

我们可以根据汇编指令后面接的字母来判断这条指令究竟是在操作什么类型的数字。比如movb是在传送字节,movw是在传送字,而movl传送双字、movq传送四字。唯一重复的是,传送双字(int)用的是l,而传送double用的也是l,虽然一样,但是由于一个是整数另外一个是浮点数,用的指令都不同,所以完全不用担心。

3.4 访问信息

一个x86-64的CPU中,包含一组16个能够存储64位的寄存器。这些寄存器用来存储整数和指针。

image-20201003215206023

这十六个寄存器的名字都是以r开头的。最开始有8个16位寄存器,即图中的ax到sp。然后扩展到32位(e代表extention),最后又扩展到64位,并且新增了8个寄存器,按照数字进行保存。

3.4.1 操作数指示符

指令一般都会带着操作数来进行操作。有三种操作数:立即数、寄存器和内存引用。

立即数在ATT格式中,用的是$开头的,然后后面接一个C语言能表示的值。

寄存器表示某个寄存器里面的内容,用ra来表示寄存器,而用R[ra]来表示它的值。

内存引用会根据内存地址去对应的地点取值。

3.4.2 数据传送指令

最简单的数据传送命令,mov,一般以传送的数据量作为后缀,比如要欢送一个字节,就用movb。源操作数必须需要是一个立即数,存储在寄存器或者内存中;而目标操作数必须是一个位置,要么一个寄存器,要么是一个内存地址。并且,mov的两个操作数不能同时是内存地址,这是因为CPU对内存要么读,要么写,不能同时操作。

这里需要注意的是,当使用movl的时候,它会把目标寄存器的高4字节设置成0。

3.4.3 数据传送例子

以下的代码:

1
2
3
4
5
6
long exchange(long *xp, long y)
{
long x = *xp;
*xp = y;
return x;
}

通过反汇编,可以发现它的反汇编代码挺容易的:

1
2
3
4
exchange:
movq (%rdi), %rax
movq %rsi, (%rdi)
ret

这个函数有两个参数,而y是存放在rsi中,xp则是存放在rdi中。这点之后会进行讨论,目前记住就可以了。

可以发现,由于xp是放在rdi中的,所以在实际使用的时候用的是加括号,因为指针就是地址。

3.4.4 入栈和出栈

在x86-64中,栈位于内存的高地址处,并且是从高到低增长的,而栈顶的地址是被存放在rsp寄存器中。

如果入栈的话,首先是先加寄存器,然后在把值放入新的地址中;出栈则是先把数字取出来,然后才把值加上去。

3.5 算术和逻辑操作

主要的算术和逻辑操作有这些:

image-20201004101009210

3.5.1 加载有效地址

leaq指令其实本质上是movq,从内存里加载数据到寄存器里面。但是实际中,我们一般会使用它来进行简单的算术操作,而与有效地址的计算无关。

3.5.2 一元操作和二元操作

一元操作就是只有一个操作数,即操作数又是源、又是目的。二元操作的话,第一个操作数是源操作数,第二个操作数是目的地址。(AT&T和intel是相反的)

3.5.3 移位操作

左移还是一样的,不论是算术还是逻辑,都是往后面加零。而右移需要区分符号右移还是逻辑右移。由于在x86-64中,最长也就64位,所以位移只需要一个字节就能表示了,高位会被忽略,所以其实只需要看%cl即可。

3.5.4 讨论

书中的一些例子。

3.5.5 特殊的算术操作

两个64位int相乘,理论上应该得到128位的数字,而且Intel还是支持128位的。

1
2
3
4
5
6
7
#include <inttypes.h>

typedef unsigned __int128 uint128_t;
void store_uprod(uint128_t *dest, uint64_t x, uint64_t y)
{
*dest = x * (uint128_t)y;
}

进行汇编可以发现,会把两个64位的数字分别放到两个寄存器中,并且对两个64位进行乘法,把结果的高64位放到了rdx中,低64位放到了rax中。

除法也是同理。

3.6 控制

3.6.1 条件码

除了上面介绍的整数寄存器,还有一组单个位的条件码寄存器,通过检测它们可以用来执行条件分支指令,比较常用的有:

  • CF:进位标志。是否有最高位发生了进位。用来判断无符号溢出。
  • ZF:零标志。上一次操作的结果是不是零。
  • SF:符号标志。上一次操作的结果是不是负数。
  • OF:溢出标志。判断有没有导致补码溢出。

之前介绍的几乎所有指令,都会或多或少修改上面的这些条件码,原因这里暂且不表。而还有一些指令是只修改条件码寄存器,不修改其他的寄存器,主要有两条,分别是cmp和test指令。

3.6.2 访问条件码

程序一般不会去读取条件码,而是通过别的指令来操作:

  • 根据条件码的组合来设置字节设置成0或者1。
  • 条件跳转到程序的别的部分
  • 条件传送数据

3.6.3 跳转指令

有一张表格,根据条件码来决定要不要跳转:

image-20201004182235930

3.6.4 跳转指令的编码

跳转指令要跳转到一个位置,那么有两种方式来表达这个位置:1. 绝对地址 2.相对PC地址。绝对地址很好理解,相对地址的计算也比较容易,只要首先获取到这个相对的偏移量,然后加上下一条指令的位置,就是真正要跳转的位置。

举个例子:

1
2
4003fa: 74 02    je  某个地址
4003fc: ff d0 某条指令

那么某个地址怎么算呢?可以通过0x4003fc+02 = 0x4003fe计算得出。

3.6.5 用条件控制来实现条件分支

通过使用cmp+jx相关的组合来完成对if-then-else实现。

3.6.6 用条件传送来实现条件分支

之前的条件控制非常符合人的逻辑,符合某个条件就走其中的一条控制路径,否则就走另外一条。但是对于现代计算机来说,可能效率没有那么高。一种可行的替代方案是,同时计算两种结果,然后根据条件选择其中的一个。这可能有点违反常识,为什么两条路都走反而会更快呢?这个涉及到指令流水线之类的东西(将在之后讨论),暂时不了解。

当然如果这两个表达式不能同时运行,比如两个分支都会对值进行操作,那么显然是不能同时处理的。所以,为了保证正确性,大部分情况下,gcc还是会倾向于使用条件控制来实现。

3.6.7 循环

严格来说,其实C语言一共有三种循环,分别是do-while(基本不用)、for和while循环。

显然do-while是最简单的,因为只需要先进行循环,然后对某个条件进行cmp,并且根据条件来进行跳转就可以了。

接下来是while循环,while循环有两种对应的机器翻译方法,第一种是直接跳转到条件判断,如果判断合格,那么进入到循环;如果不合格就跳出循环。第二种方法首先会使用条件分支,如果条件不成立则跳过。第二种方法相对第一种来说,性能一般会更好。其实对于程序员来说,我个人觉得是没什么区别可言。

最后一种是for循环,其实for循环本质上完全可以被while循环所代替,而且观察底层可以发现,其实用的就是while的两种翻译方法之一,取决你的优化等级。

当然还是有一点需要注意,就是在For循环中使用continue,那么i仍然能够正常进行++操作,但是到了while的话就得注意了。

3.6.8 switch

之前我对switch的理解就是,能够让代码具有更高的可读性,但是没有了解过它是否可以让代码的效率提高。其实是可以的,因为底层用的是跳转表这个数据结构,本质上其实是一个数组,当gcc发现开关数量比较多的情况表,并且值的范围比较小,就会使用跳转表。

这里比较重要的是掌握如何根据汇编的代码反向还原出来源代码。我的做法是首先根据第一段来确定n的范围,然后会给出一个基地址,根据这个Lx,把下面所有的都标记好,然后就可以确定对应的case了,确定了对应的case之后就可以按照逻辑慢慢捋顺了。

3.7 过程

过程其实就是我们俗称的函数或者方法。那么我们需要搞清楚,整个过程中,机器级的支持是什么。假设P调用了Q,并且调用完成之后又回到了P。

要进入到Q里面,就必须首先设置好程序计数器PC的值为Q的代码起始值,返回的时候也需要设置好相应的地址。

同时也需要传递一些参数给Q,同样Q也要能够向P返回一个值。

最后还需要为Q分配空间,并且Q执行完成之后需要能够释放这个空间。

3.7.1 运行时栈

栈位于内存空间的上层,并且是从高地址向低地址增长。只有当寄存器无法存放,才会在栈中分配空间。所以一个函数对应一个栈帧(如果这个函数过于简单,那么其实根本就不会分配栈帧给它)。而由于利用寄存器传递参数会比使用栈(内存)快的多,所以默认传递参数用的是寄存器,通过寄存器传递参数,最多可以传递6个参数。

3.7.2 转移控制

如果要将控制权从P转移到Q,那么只需要把PC设置成Q代码的起始位置就好了。但是如果从Q这里返回的时候,必须要接着从P的位置开始执行,在x86-64中,是通过call指令来完成的,通过调用call Q,会把P的地址压入栈中,并且把PC设置成Q的起始地址,而这个压入的地址就是返回地址,返回地址是接下来应该继续执行的指令的地址。

通过书本的练习可以更好的掌握入栈出栈的寄存器变化,同时需要注意的是,由于有六个参数寄存器的存在,所以栈其实只需要保存返回地址(8字节)即可。

3.7.3 数据传送

当调用函数的时候,除了需要把控制权转移过去外(其实就是跳转到对应的位置),可能还会需要传递参数值,并且返回的时候,可能会有返回值。

x86-64中,可以通过六个寄存器,分别是%rdi%rsi%rdx%rcx%r8%r9来进行参数的传递,当然如果参数只有32位或者更低,可以使用对应寄存器的低位来进行处理。在64位中,参数是从右往左,按照上面的寄存器顺序依次放入,直到放不下,就存入栈中。

1
2
3
4
5
long func(long a1, long a2, long a3, long a4, long a5, long a6, char c, int i, long a7, long a8)
{
long result = a1 + a2 + a3 + a4 + a5 + a6 + c + i + a7;
return result;
}

上面这个函数对应的入参顺序是:

1
2
3
4
5
6
7
8
9
10
pushq	$9  		# a8
pushq $8 # a7
pushq $7 # i
pushq $97 # c
movl $6, %r9d # a6
movl $5, %r8d
movl $4, %ecx
movl $3, %edx
movl $2, %esi
movl $1, %edi

当然实际中肯定会遇到超过六个参数需要传递的情况,那么多余的那些参数就需要通过栈来进行传递了。

3.7.4 栈上的局部存储

有些时候,局部数据必须放到栈中:最简单的例子就是当寄存器无法放下所有的本地数据的时候;或者对局部变量用了取地址符号&;或者是一些局部的数据,比如数组之类的。

3.7.5 寄存器中的局部存储空间

由于寄存器是共享的,所以需要用一定机制来保证数据的正确性,而目前采用的措施就是遵守惯例。惯例规定了,寄存器rbx和rbp,还有r12~r15是被调用的那方来保证值一样的:比如P调用了Q,那么由Q来保证,调用完了这些寄存器的值不会发生变化(可以不去修改这些寄存器,也可以先保存起来,用完之后恢复)。所有其他的寄存器,除了rsp之外,都是调用者P的来保存——Q可以任意修改,因为P会保证这些数据已经被保存起来了。

3.7.6 递归过程

递归本质上就是函数调用,只不过调用者和被调用者都是自己罢了。

3.8 数组分配和访问

C语言中,数组名字其实就是一个指向数组开头的指针,这个指针的值就是地址。

3.8.1 基本原则

在C语言中,指针数组,每个元素的大小都是一个指针的大小,在x86-64中是8字节。而且目前诸如mov指令,其实非常适合数组,因为可以把数组的基地址放到一个寄存器里,然后把索引也放到一个寄存器里,假设一个int的数组,那么就可以通过movl (%rdx,%rcx,4)直接进行访问内存空间了。

3.8.2 指针运算

如果在C语言里面对一个指针p进行了++操作,那么会自动指向下一个元素,C语言默认帮你做了处理,当你p指向的是int,那么p++其实是把p的地址加了4个字节;如果是double,就会自动是8字节。

3.8.3 嵌套的数组

多维数组本质上其实也就是一个一维数组,然后编译器会帮优化成对应的地址而已。

3.8.4 定长数组

如果是定长数组,那么编译器就会进行相应的优化,但是我个人也感觉不太出来优化在哪里。

3.8.5 变长数组

C语言的数组在之前必须用常数进行确定,如果希望实现变长数组,那么必须要使用malloc这种函数来进行映射。同时由于使用了变长参数,所以可能优化效率不如定长数组。

3.9 异质数据结构

C语言中除了上面提到的这些数据结构,还有其他的数据结构,分别是union和struct。

3.9.1 结构

C语言使用struct来创建一个数据类型,将不同的数据结构存放到一个“对象”中,其实可以把struct理解为一个数组,只不过每个元素的数据类型不用相同,而且开辟的空间也是连续的。

3.9.2 联合

union和struct的语法其实是一样的,只不过struct是数组,而union则是使用不同的字段来引用相同的内存区域。

一个联合的总的大小,其实是等于它最大字段的大小。而使用联合的目的就是为了能够节省内存。这就是它诞生的目的,联合中的每一个字段都能够访问相同的内存地址,直接绕开了C语言的类型安全检查机制。

使用union除了能够节省空间以外,还能够对float和int进行位模式的转换。如果你直接使用强制数据类型转化,那么在float和int之间是转的值,而底层的位模式会有天翻地覆的转变;而如果用了union,那么就能够绕开C语言本身的类型转换模式,成功保证了底层位模式不变。

3.9.3 数据对齐

为什么要数据对齐?想象一下如果一个double类型,8字节,那么如果处理器一次性读取8字节,那么就可以一次读取就获取到一个double,但是如果double它米有对齐,那么就需要从内存中读取两次。但是!就算数据没有对齐,那么硬件正常工作是没有问题的,但是Intel建议对齐数据用来提高内存系统的性能。

这里书中有一点非常疑惑,到底什么样的数据类型可以合并,什么样的数据类型是会单独扩展的呢?

3.10 将控制和数据合二为一

这部分深入理解一下指针,然后通过简单的gdb的使用,最后通过简单了解一下缓冲区溢出这个经典的系统漏洞来加深了解。

3.10.1 理解指针

每一个指针,其本质都是一个地址,然后通过前面的标识符来指明它指向的数据类型。

  • 最为特殊的是void *,代表的是指向了一个地址,但是这个地址里面究竟存放的是什么,需要程序员通过强制类型转换来指明目标内存地址所存数据的类型。

  • 指针可以使用&创建,而这个符号只能应用于lvalue表达式(即可以写在等号左边的表达式就叫lvalue)。

  • 数组的名字本质就是一个指针。

  • 对于指针使用强制类型转化,只会修改指针的运算的伸缩性,而不会修改指针所指向的地址。

  • 因为函数本身也在内存之中,所以指针也可以指向函数。

3.10.2 使用GDB

emmm 还是比较推荐使用IDE自带的工具,或者使用一些图形化的来直观的展示。

3.10.3 内存越界和缓冲区溢出

缓冲区溢出的问题,攻击代码可以使系统启动一个shell程序,这样攻击者就可以直接使用shell来进行恶意操作;当然也可以执行一些任务之后,然后正常返回。

3.10.4 对抗缓冲区溢出

缓冲区溢出问题的前提是,栈的地址很容易预测,那么防御手段很简单——让栈空间随机,不能被预测,这样就无法发动攻击了。目前linux中主流的技术用的就是栈随机化,就算是完全相同的程序,程序代码、库代码、栈、堆都会被加载到内存的不同区域。

第二种方法,是给栈压入一个随机值(金丝雀值,是一个只读的值),然后检测一下这个随机值是不是自己生成的随机值,如果不是就说明有问题了。

第三种方法,使用的是让栈中某些内存区域是可执行代码的。

上面这三种方法基本对程序员都是透明的,而且代价都非常小,组合在一起效果也特别好。但是遗憾的是,仍然无法完全抵挡住栈溢出问题。

3.10.5 支持变长栈帧

截至到目前,接触到的机器级代码都有一个特点,那么就是编译器都知道要给栈分配多少空间。但是有的函数,其实需要的长度是不确定的,比如变长数组

3.11 浮点代码

emmm 跳过吧。

3.12 小结

在本章中,主要学习了汇编,并且让人看到了gcc的强大之处。还从根本上了解了参数是如何传递的、同时也了解了C语言中的if-else、while这些底层是如何实现的。

第四章 处理器体系结构

处理器可以算的上人类创造出来的最为复杂的系统之一了。一个处理器支持的指令,再加上指令的字节级编码就成了指令集体系结构(Instruction-Set Architecture,ISA),常见的像Intel处理器家族、IBM家族和ARM处理器家族,用的是不同的ISA。虽然这些厂商之间有他们特有的ISA,但是常见的像x86-64是这些厂商都会提供的。

这一部分开始接触硬件,虽然很多人一辈子可能都不会去设计CPU,但是理解它能够让我们更好的理解计算机。

在这一部分将开始创建一个自己的ISA,称之为Y86-64。

4.1 体系结构

既然我们希望能够构建这么一个硬件出来,那我们需要有一个指令集、编码以及其他的一些东西。

4.1.1 程序员可见状态

程序可能会访问、修改寄存器、PC、条件码和内存。

在x86-64中,常用的寄存器有16个,在y86-64中,省略了r15来进行简化,而且规定了每个寄存器中存放的就是64位的数据。%rsp被用来当做是栈指针,其他寄存器没有指定的用处。有3个只有一位的条件码:ZF、SF和OF,含义和之前的一致。内存方面,直接使用了字节数组来代替。除此之外,还有一个状态是stat,用来表明程序的运行状态。就像下图这样:

image-20201009142236333

4.1.2 Y86-64指令

因为这个指令确定了是操作8字节的数据,所以我们可以根据此来得出自己的指令集。

image-20201009144709864

4.1.3 指令编码

指令编码其实就是根据上面那张表,然后每个寄存器都会对应一个数字,如果是立即数的话就需要先转成8字节的十六进制表示的数字,并且由于是小端序,所以还需要颠倒一下。

我们的这个由于是简单处理,所以会发现不论一个数字是多小,它都会被编码成8字节的,这样造成了空间的浪费。而真正的x86-64中,会根据情况来编码成1、2、4或者8字节。

4.1.4 异常

在上面的设计中,有一个状态码stat,通过它,程序员可以知道当前程序的运行状态。虽然有不同的状态码,但是如果遇到异常,就是简单的停下来就可以了。而实际在x86-64中,会通过调用一个异常处理程序来进行处理。

4.1.5 真正的程序

1
2
3
4
5
6
7
8
9
10
11
long sum(long *start, long count)
{
long sum = 0;
while (count)
{
sum += *start;
start++;
count--;
}
return sum;
}

一段很简单的求和函数,如果通过gcc编译成汇编文件的话,会是下面这个样子:

1
2
3
4
5
6
7
8
9
10
11
sum:
movl $0, %eax # sum = 0
jmp .L2
.L3:
addq (%rdi), %rax # sum += *start,直接从内存取值并且求和放入到寄存器中
addq $8, %rdi # start++
subq $1, %rsi # count--
.L2:
testq %rsi, %rsi # count > 0?
jne .L3
rep ret

但是由于目前没有y86-64对应的编译器,所以无法通过源代码获得相应的汇编代码。

4.1.6 其他一些注意点

pushq 某个寄存器指令会把栈指针减去8,然后把对应寄存器的值压入到内存中。那如果要操作的寄存器本身是rsp呢——即如果汇编命令本身是pushq %rsp,压入内存中应该是%rsp的值,还是%rsp-8呢?

很简单嘛,自己做个试验就知道了。但是问题是,C语言的编译器并不会生成对应的指令,所以我们必须使用手工生成汇编代码来完成这个任务。但是目前还是不会如何在C语言里面执行汇编指令…..

答案是:压入的是原值,而不是%rsp-8

4.2 逻辑设计和硬件控制

这部分开始讲电路了。目前是通过高低电压来表示不同的位的值的。逻辑1用的是1伏特左右的高电压,而逻辑0用的0伏特左右的低电压。

4.2.1 逻辑门

逻辑门就是数字电路基本的计算单元,它们产生的输出等于输入位的值的某个布尔函数。虽然它们应该等价于C语言中的& |~,但是在HCL语言中用的却是逻辑运算符。

4.2.2 组合电路和HCL表达式

就是简单将三种门组合在一起,就能得到很多的结果。这里值得注意的是,C语言中的逻辑操作是短路的,但是HCL中并不是。

书中简单介绍了一个检测位相等的组合电路以及一个单个位的多路复用器。

4.2.3 字级别的组合电路

如果把64个位组合到一起,就形成了对应的能对字进行处理的电路。同样也介绍了一个针对字检测位是否相等的组合电路和一个针对字的多路复用器,这个多路复用器