深入理解计算机系统-程序的机器级表示

程序的机器级表示

在本章，会学习观察汇编代码和机器代码。说到汇编语言就不得不提编译器和汇编器。**编译器是基于编程语言规则、目标机器的指令集和操作系统遵循的惯例，经过一系列阶段如图：

gcc编译器以汇编代码的形式产生输出，然后gcc调用汇编器和链接器生成二进制机器文件和可执行文件。对于Linux机，可以使用 gcc -Og -S xxx.c来进行学习。因为参数-Og表明不进行优化，这可以让汇编代码尽可能地保持和C源码一样的顺序，位置，排列等。

编译器的作用：

编译器的存在使得高级语言能够被翻译成汇编语言，最终生成机器代码，供操作系统认识并执行
编译器提供了类型检查能够帮助我们发现许多的程序错误，保证按照一致的方式来引用和处理数据。

为什么要学习汇编：

能够阅读和理解汇编是一项很重要的技能。当我们以适当的命令调用编译器时，编译器就会产生一个以汇编代码形式表示的输出文件，通过去阅读这些汇编代码，我们能够理解编译器的优化能力，并分析代码中隐含的低效率。
了解不同线程时如何共享程序数据或保持数据私有的，以及准确指导如何阿紫哪里访问共享数据，这些在并发编程非常重要，这些信息在机器代码级是可见的，

1 程序编码

1.1 机器级代码

对于机器编程来说，有两种很重要的抽象。一种是对于程序执行的抽象(使用指令集架构定义程序执行的具体情况)，一种是对于内存的抽象，使得整个虚拟地址空间在OS的加持下成为一个超大的可用数组。

x86-64的机器代码和原始的C代码相差颇大，比如：

程序计数器(PC)在x86-64机中代表下一条指令的位置。
整数寄存器文件包含了16个命名的位置(就是寄存器可见的意思)，分别存储64位的值。寄存器可以用来存储地址(就像C语言的指针)，或者保存程序状态，再或者某些寄存器用于保存临时数据，列如过程调用的参数和局部变量，以及函数返回值。
条件码寄存器，用来实现控制和数据流中的条件变化，比如if和while语句。
一组向量寄存器可以用来存放一个或多个整数或浮点数值。

1.2 汇编文件的格式注解

先看一个C文件，假如其定义如下：

long mult2(long,long);
void multstore(long x,long y,long* dest){
	long t=mult2(x,y);
	*dest=t;
}

通过gcc命令:

1 2	gcc -Og -c mstore.c //-Og告诉编译器使用符合原始C代码整体结构的机器代码的优化等级

得到.s汇编文件,完整内容如下：

	.file	"010-mstore.c"
	.text
	.globl multstore
	.type	multstore,@function
multstore:
	pushq	%rbx
	movq	%rdx,%rbx
	call	mult2
	movq	%rax,(%rbx)
	popq	%rbx
	ret
	.size	multstore, .-multstore
	.ident	"GCC:(Ubuntu 4.8.1-2ubuntu1-12.04) 4.8.1"
	.section		.note.GNU-stack,"",@progbits

其中，以.开头的行为汇编器和链接器工作的伪指令。它描述了C语言种插入汇编的方法，对于一些应用程序来说，必须使用汇编代码来访问机器的低级特性：

一种方法是用汇编代码编写整个函数，在链接阶段把它们和C程序链接起来
另一种方法是利用GCC的支持，直接在C程序中嵌入汇编代码

2 数据格式和寄存器

2.1 数据格式

由于计算机发展是从16位到32位再到64位的，所以Intel使用字(word)表示16位数据类型，用双字(double word)表示32位数据类型，四字(quad word)表示64位数据类型。一般而言，指令后面都会跟着一个后缀，表明操作数的大小。浮点数和整数使用的是完全不同的指令和寄存器。

2.2 寄存器初识

一个标准的x86-64CPU包含一组16个用来存储64位数据的通用寄存器。他们用来存储整数数据和指针. 指令可以对这16个寄存器的低位字节存放的大小不同的有效数据进行操作。这些寄存器可以向前兼容，就是64位可以存储32位，16位和8位的数据，但是32位无法存储64位的数据，如果是大寄存器存小数据，那么只能存在低位中，高位有相对应的填充措施。

对于高位的数据填充，一般有两个策略：一是生成1字节和2字节的指令保持其他高位不变；生成4字节(2字)的指令会把高位填充为0。

几个重要的寄存器：

rax:用来存储返回值
rsp:栈指针，用来指向运行时栈的结束位置,即当前运行栈的栈顶

3 访问信息

3.1 操作数指示符

大多数指令都有一个或多个操作数，指出执行一个操作中要使用的源数据和目的地位置。源数据可以是立即数(常量)，寄存器，或从内存地址里读出；操作结果可以存放到寄存器或内存里。完整的表示方法如下：在这张表里，只有前两个得到的是直接的值，其余都要翻译成内存地址来进行寻址操作然后取值。

对于指令，习惯把它们划分成不同的类，每一类的指令作用相同，只是操作的数据大小不同。 #### 3.2 数据传送指令先来看看数据传送指令，它有点像C语言的赋值运算。MOV类指令有四条指令，他们的主要区别是操作的数据大小不同： x86-64对于MOV指令加了一个限制，就是不能直接把一个值从内存的某个位置复制到另一个位置，而必须使用寄存器作为中介。MOV指令的后缀表明了操作数据的大小，也就是寄存器的大小，不管这个寄存器是源数据还是目的地址，都必须符合指令指定的大小。MOV指令只会更新目的操作数指定的寄存器字节或内存位置(就是只更新指定的低位字节)，高位字节有其他的设置，但是有一个例外，就是movl指令，当它把寄存器作为目的地址时，会把高32位设为0。

常规的movq指令只能以表示32位补码的数字的立即数作为源数据利用符号扩展放到64位寄存器里去；movabsq能以任意64位立即数值作为源数据，并且只能以寄存器作为目的地址。
有两类指令，适用于把较小(位长)的源数据复制到较大(位长)的目的地时使用:
- MOVZ使用0扩展位长；
- MOVS使用符号扩展位长，就是复制源数据的最高有效位。

它们的后两个字符表示位长，第一个指定了源数据的大小，第二个指定了目的的大小。

3.3 压入和弹出数据

这两个数据传送操作可以把数据压入栈中，以及从中弹出数据。在x86-64的机器中，程序栈存放在内存中的某个区域。栈向下增长，因此栈顶元素时所有栈元素里地址最小的。所以为了方便理解，栈是倒过来画的，也是向下增长的。涉及到栈的操作： pushq指令的功能是把数据压入栈中，而popq是弹出指令。不过它们都涉及两个操作，pushq是首先在栈底指针%rsp里存着新的值得地址，然后设置内存中的这个位置得值为准备压入得数据。所以它的操作数是数据源，而popq则是首先把栈顶的值复制到操作数里，然后指针回退，也就是+8(栈顶指针+8意味着减小8字节的空间，因为它是向下增长，+的话就代表往上回去了)。这操作的都是8字节下，64位。

因为栈和程序代码以及其他形式的程序数据都是放在同一内存中，所以程序可以用标准的内存寻址方法访问栈内的任意位置。

4 算术和逻辑运算

下图给出了x86-64的一些整数和逻辑操作。大多数操作都分为了不同大小操作数的变种（只有lead没有其他大小的变种），比如add指令有addb、addw、addl和addq四种变种，分别表示对不同大小的操作数操作，它们一样可向下兼容，但不能向上兼容。除了第一个leaq操作之外，其他的都会改变条件码

4.1 加载有效地址

加载有效地址指令leaq实际上是movq指令的变形。它形式上是将内存数据读到寄存器，但实际上它根本没有引用内存，它并不是从指定位置读出数据，而是将有效地址写入到目的操作数。这就是C语言当中的&s取地址操作符，也是产生指针的重要语句。

比如leaq (%rdi,%rsi,4), %rax的操作结果是R[rax] = R[rsi]*4+R[rdi]。而不是R[rax] = M[R[rsi]*4+R[rdi]]。 #### 4.2 一元和二元操作在上面的算术指令表中，第二组只有1个操作数就是一元操作，其他为二元操作。

一元操作指令只有一个操作数，这个操作数既是源又是目的。所以它们就像C语言的自增，自减操作一样。
对于二元操作，一般都是第二个操作数减去/加上/除以/乘以/异或/或/且第一个操作数。注意，如果第二个操作数是内存地址，那么必须先从内存中读出值，再把结果写回内存。

4.3 移位操作

移位指令很特别，因为它们只允许以特定的寄存器作为操作数。一般来说，选择长度为8的寄存器就可以了，因为移位数值一定是无符号数，所以8位最长可以移动255位，可是255位长的计算机还没出现，所以一定够用了。

在对位长为\(w\)位的数据进行移位操作时，移位量是寄存器的低\(m\)位决定的(也就是只有低\(m\)位的值会被当做移位量，哪怕存放移位量的寄存器是8位，也可能只读取低3位的值，此时最多移动7位)，其中\(m=log2(w)m=log_2(w)m=log2(w)\)，高位会被忽略。

SAL和SHL执行逻辑移位，高位补0；SAR执行算术右移，补最高位，SHR执行逻辑右移，补0.移位操作的目的操作数可以是寄存器，也可以是内存地址。

5 控制

机器代码提供两种基本的低级机制来实现有条件的行为：测试数据值，然后根据结果来改变控制流或数据流。

5.1 条件码

除了整数寄存器，CPU还维护一组单个位的条件码寄存器，它们描述了最近的算术或逻辑操作的属性。

CF:进位标志。最近的操作使得最高位产生了进位。可以用来检测无符号数的溢出。
ZF:零标志。表明最近的操作得出的结果为0。
SF:符号标志。最近的操作得到的结果是负数。
OF:溢出标志。最近的操作导致了一个补码的溢出——正溢出或负溢出。

刚刚说的那些一元二元操作（除了leaq)以及移位操作，会改变条件码和寄存器的值。也有一些只改变条件码而不改变任何其他寄存器的操作：如下所示的CMP家族和TEST家族，它们仅仅根据两个操作数之差来设置条件码。除了只设置条件码而不进行目的寄存器的更新外，CMP和SUB指令是一样的。TEST指令的行为和AND指令一样，除了它们不会更改目的寄存器的值外。

5.2 访问条件码

条件码通常不会直接读取，常用的使用方法有3种：

一是可以根据条件码的某种组合将一个字节设置为0或1，
二是可以跳转到程序的其他某个部分，
三是可以有条件地传送数据。

对于第一种情况，常用来实现SET指令，SET成员之间的区别就在于它们考虑的条件码组合是什么，这些指令的后缀指明了这一点，它们在此不作为寄存器长度要求来使用。一般而言，SET指令存在于那些可以更改条件码的指令的后面，这样就可以读取到最新的值了，当然也可以不这么做。至于每个指令把目的操作数到底设置成了什么,可以通过条件码计算，也可以通过a-b(如果前面是CMP b,a)或a+b(如果前面是TEST b,a指令)的计算结果来判断。

表格中的第三组只作用于有符号数操作，第四组只作用于无符号数操作。至于究竟用哪个，编译器会在编译期根据源码进行判断选择。条件跳转只能是直接跳转。

5.3 跳转指令

对于需要指定执行位置时，可以使用跳转指令。跳转的目的地通常使用一个标号指明。这些指令的命名格式和跳转条件和SET指令是一致的。 - 对于jmp指令来说，它是无条件跳转，它既可以是直接跳转，也可以是间接跳转，此时跳转目标从寄存器或内存位置中读出。

5.4 跳转指令编码

对于如何确定跳转的位置，有多种方法，但是最常用的是PC相对法。这种方法会把目标指令的地址和紧跟在跳转指令后面的指令的地址的差值作为值编码在跳转指令后面。在执行PC相对寻址时，程序计数器的值是跳转指令后面的那条指令的地址。使用PC相对法进行编码，好处就是指令很简洁，而且目标代码可以不做修改就移植到别的机器上。

5.5 条件控制实现条件分支

将条件表达式和语句if-else从C语言翻译成机器代码，最常用的方式就是结合有条件和无条件跳转。另一种方式使用数据的条件转移实现，这里是介绍控制的条件转移实现。其形式如下

//c代码
if(test-expr)
	then statement;
else
	else-statement;
//接近于汇编的代码
	t=test-expr;
	if(!t)
		goto false;
	then-statement;
	goto done;
false:
	else-statement;
done:

也就是说，汇编器为then-statement和else-statement产生各自的代码块，他会插入条件和无条件分支，以保证能正确执行代码。

5.6 条件传送实现条件分支

对于使用条件控制来实现条件转移，在现代处理器中可能会很低效。而可以通过使用数据的条件分支来实现高效，后者先计算出所有的分支的结果，再在最后进行条件判断，输出分支结果之一。

现代处理器使用了称为流水线的处理结构，使得一个时钟周期内可以处理多条指令的不同阶段操作。但是这种高效率依赖于流水线的满载，如果流水线空荡荡的那反而是降低了性能。于是需要CPU提前把指令填充到流水线，而有些指令没法提前填充，于是CPU使用它的预测算法，把那些未来的指令放到它可能被执行的流水线上。但是！一旦放错了，后果开销更大，此时因为指令的跳转，需要清空流水线，重新载入新的指令。当代CPU可以做到90%准确率，不过有时如果输入偏于随机的话，那么性能就下来了。

使用条件传送高效是因为它不需要预测结果，因为所有的可能结果全部完成运算，仅仅在最后输出时选择一个正确的结果就好，这就把预测取消了。同时因为取消了预测，此时控制流与输入数据无关，流水线一直是满载。就如V=test-expr?then-statement:else-statement;。在C中实现两种条件分支如下：

//用控制实现条件分支
int absdiff(long x,long y)
{
	long result;
	if(x>y)
		result=x-y;
	else
		result=y-x;
	return result;
}
//用条件传送来实现条件分支
int absdiff(long x,long y)
{
	long xby=x-y;
	long xly=y-x;
	long ntest=x>=y;
	if(ntest)
		return xby;
	return xly;
}

循环和switch略

6 过程* 过程是软件中的一种很重要的抽象。它提供了一种封装代码的方式，用一组指定的参数和一个可选的返回值实现了某种功能，然后可以在程序的不同地方调用这个过程。不同的编程语言中，过程描述不同，在C语言中，它们被称为函数，在Java和C++中，它们被称为方法，在进程中，它们可能被称为子进程，在多线程中，可能又叫子线程。虽然很多，但是它们有一些共有的特性。

为了方便，这里就以函数调用为例，函数P调用函数Q,他要包含以下机制：

传递控制：在进入函数Q之前，程序计数器PC必须被设置为Q代码的起始地址，然后在返回后，程序计数器PC设置为P中调用Q后面那条指令地址
传递数据：P必须能够向Q提供一个或多个参数，Q必须能够向P返回一个值
分配和释放内存：在Q中能为局部遍历分配空间，而在返回时释放这些空间

6.1 运行时栈

程序是运行在内存中的，一般来说，内存里包括程序正文，程序运行堆栈。程序正文就是可执行机器代码，程序运行堆栈就是程序运行需要的额外空间，比如内存分配，数组，局部变量等。

C语言的内存管理采用栈的结构，先进后出的顺序。程序可以通过这种方式来管理它所需要的存储空间，当P调用Q时，会把Q添加到栈顶，然后运行结束通过改变rsp栈顶指针来释放。因此，程序可以用栈来管理它的过程所需要的存储空间，栈和寄存器存放在着传递控制和数据。

当x86-64程序需要的空间超过寄存器所能满足的时候，就会在栈上分配空间，这个部分称为过程的栈帧。来看一个一般的程序堆栈结构：

%rsp：寄存器%rsp保存着栈指针，它指向栈顶(图中底部)，而前面提过，内存向下增长，所以把%rsp减少一个值就完成了对于空间的分配，加上一个值就是对空间的回收。
栈帧：每一个函数都有属于自己的栈帧，如图上的Frame for calling function P是调用者P函数的栈帧，Earlier Frames是之前的调用者较早栈帧，还有当前Q函数栈帧。栈帧主要又三个部分组成：save registers、local variables和Argument build area
调用函数P:P函数首先会从右向左去存储被调用函数的参数，因此可存储的参数的寄存器为6个（rdi、rsi、rdx、rcx等，因此当参数的数量大于6时，其他的参数会右向左的被压入当前P的栈帧中，这也是为什么返回地址的上一个地址存储的时Argument 7（位于该栈帧的参数构建区域Argument build area)。之后为了能够在Q返回时知道P程序从哪个位置继续执行，会压入一个返回地址
被调用函数Q：Q的代码会扩展当前栈的边界，分配它的栈帧所需空间。它可以保存寄存器的值，分配局部变量空间，为它调用的过程设置参数。大多数的过程的栈帧都是定长的，在过程开始就分配好了。当Q执行完毕之后，会把返回值寄存在在寄存器%rax中，之后释放当前自己的栈帧，弹出返回地址恢复现场，并弹出压入的参数。
保存寄存器：为了保证被调用者不会覆盖调用者稍后会使用的寄存器，需要设置寄存器值的保存，这就是寄存器保存区域。在惯例中，分为了被调用者保存寄存器和调用者保存寄存器

6.2 转移控制

将控制从函数P转移到函数Q只需简单的将程序计数器PC(%rip)设置为Q的代码起始位置即可，不过为了能够恢复现场，必须保存P的下一个执行指令地址。

对于过程Q的调用汇编上是通过CALL指令实现的。该指令后面跟着Q的地址。此时，过程P把PC设置成Q的地址，然后CALL指令会把将紧跟它的指令的地址压入栈中，这个就是返回地址，当Q调用ret指令进行返回时，会弹出这个返回地址，设置到PC(%rip)上。call的指令格式如下：

call指令有一个目标，即指明被调用过程起始指令地址。既可以是直接的，也可以是间接的。直接调用的目标是一个符号，间接调用的时*后面跟一个操作数指示符。上面的的图片详细展示了mian-->top(100)-->leaf(95)的调用和返回过程。

在调用中call指令完成两个工程，将当前pc的下一个指令地址压入栈中，设置pc的跳转地址。
在返回时，将返回值存入%rax，然后从栈中弹出返回地址设置到pc上，恢复栈顶指针的指向

6.3 数据传送

当过程P调用过程Q时，P的代码必须首先设置参数，如果参数数目小于等于6个，直接设置在寄存器就可以；而Q在返回到P之前，必须首先设置%rax来实现返回值。

在x86-64架构中，寄存器的使用是有顺序的，而且它们的名字取决于参数的大小。

一旦参数到位，就可以调用CALL指令来把控制移交至Q了。

问题1：对于数组参数，是怎么传递的？ 回答：对于数组，很明显8字节的寄存器是无法完全存储的。有数组知识可知，数组是连续的一系列内存，数组名是第一个元素的地址，因此寄存器可以存储数组的首地址，对于后续的元素通过变址寻址方式去访问。 问题2：对于像vector这样的数组，我们在没有按指针/引用的形式传递的时候，它会如何传参呢? 回答：我认为是会发生一份拷贝，将数组拷贝进参数区域传递给被调函数

6.4 栈上的局部存储

有时寄存器可能不能够存储参数，这时就需要使用栈上的空间来完成存储。常见的情况包括：

寄存器不足以存放所有的本地数据
对一个局部变量使用取地址符，就一定需要栈，因为寄存器没有地址这一说。
对于局部变量时数组或结构的情况，因为访问它们需要产生地址引用。

一般来说，过程通过减小栈指针来实现空间的分配，分配的结果作为栈帧的一部分。

6.5 寄存器中局部存储空间

寄存器是唯一被所有过程共享的资源，虽然给定时刻只有一个过程是活动的，单我们仍然必须确保当一个过程（调用者）调用另外一个过程（被调用者）时，被调用者不会覆盖调用者稍后会使用的寄存器。

在惯例中，分为了被调用者保存寄存器和调用者保存寄存器：

被调用者保存寄存器：由被调用者去负责保存调用者的寄存器值。寄存器%rbx、%rbp和%r12~%15都被分为被调用者寄存器。因此P调用Q时，Q必须保存这些寄存器的值，以保证返回P时寄存器的值与Q被调用时一样。
- 一种方法是Q不使用这些寄存器，也就当然不会改变
- 另一种方法是Q将这些寄存器的值压栈，返回时弹出恢复
调用者保存寄存器：由调用者自己去负责保存寄存器的值。除%rsp和上面被调用者保存寄存器，其他的寄存器都分类位调用者保存寄存器。

6.5 递归过程

介于每个过程调用在栈中都有它们自己的私有空间，因此多个未完成调用的局部变量并不会相互影响。这就为递归的实现提供了可能。

递归地调用一个函数与调用其他函数是一样的。栈机制就可以保证每个函数调用都有它自己私有的状态信息存储空间。比如局部变量，返回地址等。

栈分配和释放的规则很自然地就与函数调用-返回的顺序一致。即使对于更加复杂的情况，甚至是相互调用也可以适用。

7 数组分配和访问

在讨论之前，来约束一些规则： \[T A[N];\] 起始位置是\(x_A\)，\(L\)是\(T\)类型的大小。这个声明有两个效果，首先，它在内存分配了一段长度为\(L⋅N\)的连续空间。其次，它引入了标识符A，可以用来当作指向数组开头的指针。这个指针的值就是数组首元素的地址，也就是这里的\(x_A\)。数组元素i(从0开始)的地址是\(x_A+L⋅i\)。

x86-64的数组引用指令可以简化对于数组的访问。假设数组的首地址放在%rdx中，而下标i放在%rcx中。那么指令

1	movl (%rdx,%rcx,4),%eax

会把元素i的值放在%eax中。其中的常数4代表数据大小，如果是int64类型，那么可以改成8。伸缩因子1，1，4，8覆盖了所有基本数据类型的大小。

7.1 指针运算

C语言允许对指针进行运算，运算的结果会根据该指针引用的数据类型的大小进行伸缩。如果p是一个指向类型T的指针，p的值是\(x_p\)，那么表达式\(p+i\)的值就是\(x_p+L⋅i\)，这里\(L\)是数据类型T的大小。

对于指针操作，有取地址符&和解引用符*，在数组里，可以有些骚操作。比如A[i]等价于*(A+i)。

7.2 变长数组

C语言运行数组的维度是表达式，在数组被分配的时候才计算出来：

1	int A[expr][expre2];

这就意味者C语言支持边长数组，即数组的长度在编译的时候才能确定。

8 内存越界引用和缓冲区溢出

数组是保存在栈里的，所以对数组的越界访问可能会破坏栈结构。想一想，如果某时某个数组长度为10而访问其第12个元素，就有可能访问到上一个过程设置的返回地址，再修改就会造成当前调用返回到未知区域。

缓冲区溢出的一个更加致命的使用就是使得程序调用一个它本来不应该调用的函数，这也是一种常见的计算机网络攻击的方法。

8.1 对抗缓冲区溢出攻击

缓冲区溢出攻击是很可怕的，所以应该采取措施来进行防范。

栈随机化：这种方法旨在随机化每次栈的起始位置，来让恶意程序无法推算出栈的位置。不过攻击代码还是可以通过多次执行nop指令(只是单纯的递增程序计数器而不执行行为)来推算栈的位置。
栈破化检测：在缓冲区末尾和其他栈区域之间添加一个特殊的值。程序通过检测这个值与内存中的只读的备份值是否一致，如果不一致证明发生了不被允许的访问。此时程序终止。这个值称为金丝雀值，因为早期金丝雀用于检测矿洞的有毒气体。所以在汇编代码里看到的%fs:40指令就是通过段寻址的方式从内存读入值设置金丝雀值。
最后一种方法是通过限制代码的可执行区域来实现的。这种方法把内存区域划分成可执行区，可读取，可读写区。只有可执行区的代码才是可执行的。这样可以限制程序对于栈的更改触及到可执行代码。