CSAPP程序的机器即表示2（6~11节）

Posted on
Words count in article: 9.3k | Reading time ≈ 37

CSAPP程序的机器即表示2

控制

通常，C 语言中的语句和机器代码中的指令都是按照它们在程序中出现的次序，顺序执行的。用jump 指令可以改变一组机器代码指令的执行顺序，jump 指令指定控制应该被传递到程序的某个其他部分，可能是依赖于某个测试的结果。编译器必须产生构建在这种低级机制基础之上的指令序列，来实现C 语言的控制结构。

我们先谈谈实现条件操作的两种方式，然后描述表达循环的switch 语句的方法。

条件码

除了整数寄存器，CPU 还维护着一组单个位(byte) 的条件码(condition code) 寄存器。我们可以检测这些寄存器来执行条件分支指令。

一下是最常用的条件码

CF : 进位标志。最近的操作使高位产生了进位。可用来检查无符号操作的溢出

ZF: 零标志。最近的操作得出的结果为0

SF : 符号标志。最近的操作得到的结果为负数

OF: 溢出标志。最近的操作导致一个补码的溢出—-正\负溢出

比如说，我们用一条 ADD指令完成等价于C表达式 $t=a+b$ 的功能，a、b、t都是整形的。然后根据下面的C表达式来设置条件码

有几类指令能够修改条件码：

  1. 算术指令：既改变操作数，也有肯能改变条件码。
  2. CMP指令：右操作数减左操作数，只可能改变条件码。
  3. TEST指令：两操作数相与，只可能改变条件码。

访问条件码

条件码寄存器不能直接读取，有三种方法：

  • set指令：根据条件码，设置一个字节。

1
2
3
4
5
6
7
int comp(data_t a,data_t b)
a in %rdi,b in %rsi
comp:
 	cmpq 	%rsi, 	%rdi 	//Compare a:b
 	setl 	%al 			//Set low-order byte of %eax to 0 or 1
 	movzbl 	%al, 	%eax 	//Clear rest of %eax (and rest of %rax)
 	ret

第二行是cmp指令，也就是通过%rdi-%rsi 的状态来设置状态码的

第三行是 set 指令，setl %al之后，al寄存器中的值就为比较命令 cmp执行后状态位 $SF\wedge OF$ 的值

第四行是将 %al 赋值给 eax 的低8bits，然后再将eax的高位设置为0

我们就拿sete来举例，即 “set when equal” 指令。

当a = b 时，会得到 $t=0$ ,因此零标志置为就表示相等。

类似的我们来考虑setl,即”set when less” 指令

当没有发生溢出的时候，OF设置为0，那么只有当 $a-b<0$ 的时候，SF会等于1；
如果发生了溢出，那么OF设置为1，那么要让a仍然小于b，就要让a为负、b为正，a-b 会下溢变成正数，于是 SF会等于0

那么只有当 SF^OF ，才能保证将每一种情况都包含在内，才能表达出 a<b 是否为真。

跳转指令

  • jump指令：根据条件码进行跳转，即控制的条件转移。

跳转指令会导致执行切换到程序中一个全新的位置。在汇编代码中，这些跳转的目的地通常用一个标号(label) 指明.比如说:

1
2
3
4
5
	movq $0,%rax 		Set %rax to 0
	jmp .L1 			Goto .L1
	movq (%rax),%rdx 	Null pointer dereference (skipped)
.L1:
	popq %rdx 			Jump target

指令jmp.L1 会导致程序跳过movq 指令，而从popq 指令开始继续执行。在产生目标代码文件时，汇编器会确定所有带标号指令的地址，并将跳转目标（目的指令的地址）编码为跳转指令的一部分。

下面列举了不同的跳转指令：

  • jmp 是无条件跳转，它可以是直接跳转，即跳转目标是作为指令的一部分 编码的。也可以是间接跳转，即跳转目标是从寄存器或者内存位置中读出的
    • 汇编语言中，直接跳转是给出一个标号作为跳转目标的，例如上面所示代码中的标号“.L1”。间接跳转的写法是 ”*“ 后面跟一个操作数指示符
    • 例如 jmp *%rax 用寄存器 %rax 中的值作为跳转目标，而 jmp *(%rax) 是以%rax中的值作为地址，从内存中读取跳转目标。

上表所示的其他跳转指令都是有条件的：它们根据条件码的某种组合，或者跳转，或者继续执行代码序列中下一条指令。这些指令的名字和跳转条件与SET指令的名字和设置条件是相匹配的。

同SET指令一样，一些底层的机器指令有多个名字，条件跳转只能是直接跳转。

  • cmov条件传送指令：根据条件码决定是否进行mov操作（其性能要优于控制的条件转移P141）也就是有条件地传送数据。

注意点： je 是判断 ZF的，如果ZF=1(计算结果为0) 那么就会跳转；反之，jne是判断 ~ZF 的，如果ZF=0(计算结果不为0)，则会跳转

同时我们也应该了解到，sub 和 add 这类指令也会影响符号位，所以说会出现这样的汇编代码：

这段代码我们这么理解： 首先让rdx寄存器中的数字减去1，判断是否为0，若为0则将ZF置为1，若不为0则将ZF置为0。然后用jne进行条件跳转。最后的逻辑就是

if rdx-1 != 0 则跳转，等于0则返回。 

1
2
subq	$1, %rdx
jne		.L10

跳转指令的编码

在汇编代码中，跳转目标用符号标号书写。汇编器，以及后来的链接器，会产生跳转目标的适当编码。跳转指令有几种不同的编码，但是最常用都是PC-relative。也就是说它们会将目标指令的地址与紧跟在跳转指令后面那条指令的地址之间的差作为编码 这些地址偏移量可以编码为1、2 或4 个字节。

第二种编码方法是给出“绝对”地址，用4 个字节直接指定目标。汇编器和链接器会选择适当的跳转目的编码。

下面是一个PC-relative的例子，它包含两个跳转：第二行的jmp指令前向跳转到更高的地址，而第7行的jg指令后向跳转到较低的地址。

1
2
3
4
5
6
7
8
 	movq 	%rdi, %rax
 	jmp 	.L2
.L3:
 	sarq 	%rax
.L2:
 	testq 	%rax, %rax
 	jg 		.L3
 	rep; 	ret

仍然是同一个函数，汇编器产生的 “.o” 格式的反汇编版本如下所示：

1
2
3
4
5
6
0: 48 89 f8 	mov 	%rdi,%rax
3: eb 03 		jmp 	8<loop+0x8>
5: 48 d1 f8 	sar 	%rax
8: 48 85 c0 	test 	%rax,%rax
b: 7f f8 		jg 		5<loop+0x5>
d: f3 c3 		repz 	retq

我们看到反汇编版本生成的汇编语言没有label，jmp + label的直接跳转也变成了 jmp+地址 的间接跳转。那么我们刚才说了，产生跳转目标的编码是由目标指令的地址与紧跟在跳转指令后面那条指令的地址之间的差得出的。我们现在就可以来验证这个是否正确。

我们观察到第2行中跳转指令的跳转目标指明为0x8,观察指令的字节编码，会看到第一条跳转指令的目标编码(在第二个字节当中)为0x03 ，然后将其加上紧跟在跳转指令后面那条指令的地址0x5 就得到了跳转目标地址0x8 也就是第4行指令的地址。

同样的，第二个跳转指令的目标编码是0xf8(十进制的-8) .将这个数加上紧跟在跳转指令后面那条指令的地址 0xd 即得到0x5 ，即第三行指令的地址。

这说明在执行，当执行PC 相对寻址时，程序计数器的值是跳转指令后面的那条指令的地址，而不是跳转指令本身的地址。

A: 02+4003fc = 4003fe

B: 因为 0xf4 是-12的补码所以这里是 400431-12 = 400425

C: 根据反汇编器产生的注释，跳转目标是绝对地址 0x400547.那么根据字节编码，一定在距离pop 0x2 的地址处。减去这个值就得到地址 0x400545. 注意，ja指令的编码需要2个字节，它一定位于地址0x400543处。

D: jmpq 是 e9, XXXXXX = 0xffffff73(负数)+0x4005ed =0x400560

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

其实在代码中，我们更多的是要使用控制结构(循环，if-else, switch 等)现在我们要思考怎么用刚学的条件位、comp、jump指令来实现这些控制结构。那么我们一般写的控制结构是没有goto的，因为goto会让程序变得很乱，可读性会变差。但是我们的汇编代码在实现这些控制结构的时候，用了非常类似于goto的代码。只不过goto利用jump来实现。

我们可以先来写一个C语言代码，然后写一个goto风格的C语言代码，最后将其汇编代码贴出。比较一下它们之间的相似于不同。这个函数是让我们求两个整数之间差的绝对值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(a) Original C code								(b) Equivalent goto version
long lt_cnt = 0;								long gotodiff_se(long x, long y)
long ge_cnt = 0;								{		
long absdiff_se(long x, long y)						long result;
{													if (x >= y)
	long result;										goto x_ge_y;	
	if (x < y) {									lt_cnt++;
		lt_cnt++;									result = y - x;
		result = y - x;								return result;
	}											  x_ge_y:
	else {											ge_cnt++;
		ge_cnt++;									result = x - y;
		result = x - y;								return result;
	}											}
	return result;	
}

我们看到 b)是goto风格的C语言代码，这类代码在一段语句块之前有一个标签(label) ，只要goto 后面加一个标签名字，那么整个程序就会跳转到那个标签去运行。

那么我们再来看看这个程序产生的汇编代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(c) Generated assembly code
//long absdiff_se(long x, long y)
//x in %rdi, y in %rsi
absdiff_se:
cmpq %rsi, %rdi 						Compare x:y
jge .L2 								If >= goto x_ge_y
addq $1, lt_cnt(%rip) 					lt_cnt++
movq %rsi, %rax
subq %rdi, %rax 						result = y - x
ret 									Return//Return的缺省值就是%rax 
.L2: x_ge_y:
addq $1, ge_cnt(%rip) 					ge_cnt++
movq %rdi, %rax
subq %rsi, %rax 						result = x - y
ret 									Return

我们看到汇编语言和goto风格的C语言是非常相似的。其实这就是 if- else 控制流在汇编语言中的实现原理。在汇编中我们会使用 jx(jump+条件) 条件跳转命令来模拟goto, 这里的 jge就是当大于等于的时候跳转 ，

对于一个 if-else 语句，在C语言里的模板是这样的：

1
2
3
4
if(test-expr)
	then-statement
else
	else-statement

这里的test-expr 是一个整数表达式，他的取值为0或者为非0。这两个分支语句中 (then-statement 或者else-statement) 只会执行一个。

在汇编语言里，通常转换成下面这个模板，我们用C语法来描述：

1
2
3
4
5
6
7
8
t = test-expr;
if(!t)
	goto false;
then-statement
goto done;
false:
	else statement
done:

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

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

现在我们再来看看 General Conditional Expression 也就是条件表达式在汇编语言中的呈现情况

比如下面这句条件表达式：

1
val = x > y ? x-y:y-x;

这句和上面的if-else 的表达效果是一样的，可以被总结为这种模式：

1
val = Tese? Then_Expr : Else_Expr;

那么这句话用goto风格的C语言是这样表现的：

1
2
3
4
5
6
7
8
	ntest = !Test;
	if(ntest) goto ELse;
	val = Then_Expr;
	goto Done;
Else:
	val = ELse_Expr;
Done:
	...

还有一种方法，而是将 Then_Expr 和 Else_Expr 表达式都算出来，然后再做一个判断

1
2
3
4
5
result = Then_Expr;
eval = Else_Expr;
nt = !Test;
if(nt) result = eval;
return result;

在这样一个没有goto版本的控制流中，每一步都是顺着往下执行的。

这和刚才的goto版本是不一样的，因为goto语句会降低程序的性能。 我们可以这样来解释：
CPU在执行一条语句的时候，事实上已经将后面好几条将要被执行的语句放到cache里面了，然而这时候如果出现了goto语句，cpu就要到内存里面去找goto后面的语句，而cache中的语句这时候就没有用了。而到内存中去找语句的速度是远远慢于直接从cache里面取出语句的，所以多用goto会导致程序的效率低下。所以我们这样写，是为了减少goto语句的发生。

下面来看看goto风格和不用goto的代码之间的差别

1
2
3
4
5
6
7
8
t = test-expr;							result = Then_Expr;
if(!t)									eval = Else_Expr;
	goto false;							nt = !Test;
then-statement							if(nt) result = eval;
goto done;								return result;
false:		
	else statement
done:

我们看到如果是 if-else 风格的代码，他只会在then_Expr 和 Else_Expr 中计算一个代码块，但是右边的条件表达式语句则是对then_Expr和Else_Expr 都进行了一个计算。

其实，条件表达式就是用条件传送来实现条件分支的一个例子。我们可以来看看它的汇编代码

1
2
3
4
5
6
7
8
9
10
11
(c) Generated assembly code
long absdiff(long x, long y)
x in %rdi, y in %rsi
absdiff:
	movq %rsi, %rax
	subq %rdi, %rax		rval = y-x
	movq %rdi, %rdx
	subq %rsi, %rdx 	eval = x-y
	cmpq %rsi, %rdi 	Compare x:y
	cmovge %rdx, %rax 	If >=, rval = eval
	ret 				Return tval

我们来解释一下这段汇编代码，首先它计算了 y-x和x-y 并分别存储到 rval和eval之中，然后它对x、y进行了一个比较。关键在于汇编代码的第七行 cmovge 指令 实现了 cmovdiff的条件复制。只有当第六行的 cmpq指令表明一个值大于等于另一个值(cmovge最后的ge已经表明) ,才会把数据源寄存器传送到目的。

下图列举了 x86-64上一些可用的传送指令。每条指令都有两个操作数：源寄存器或者内存地址S , 目的寄存器R ,和SET、Jump指令一样，cmov指令的结果取决于条件码的值。源值可以从内存或者源寄存器中读取，但是只有在指定的条件满足时，指令把原值S复制到目的R。

源和目的 的值可以是16、32、64 位场。不支持单字节的条件传送。无条件指令的操作数的长度显式地编码在指令名中，汇编器可以从目标寄存器的名字推断出条件传送指令的操作数长度。

但是条件表达式也存在很多弊端，这里列出几个例子：

第一个就是Else_Expr和Then_Expr 计算起来都非常复杂，导致整行语句要运行非常长的时间

第二个就是如果一个表达式计算起来是非法的话，整个代码就会报错。

最后一个就是如果对x自身进行操作，那么我们就会得到意想不到的结果。比如上图我们的意图是如果 x>0 那么就x是原来的7倍，反之则是原来基础上加3。 事实上因为这两个表达式都被计算了，因此我们不管怎么样得到的答案都是原来的七倍再加上三。

所以在写条件表达式之前我们要想想是否有弊端，否则我们就老老实实去写If-then-else

循环

C语言中有 do-while, while ,for 三种循环结构。但是在汇编语言中没有相应的指令存在。可以通过条件测试和跳转的组合来实现循环的效果。我们先来看看do-while 循环

do-while 循环

do-while 循环的语句通用模板如下：

1
2
3
do
	body-statement
	while(test=expr);

也就是说每次循环程序都会执行循环体中的语句，然后执行测试表达式。如果测试为真，就回去再执行一次循环。我们可以看到 body-statement 至少会执行一次。

用 goto 风格的C语言可以这样改写：

1
2
3
4
5
loop:
	body-statement
	t = test-expr
	if(t)
		goto loop;

我们具体举一个例子来分析：这个函数的目的是数一数一个二进制字符串中有几个1

1
2
3
4
5
6
7
8
9
10
//C code												Goto Version
long pcount_do(unsigned long x)							long pcount_do(unsigned long x)					
{														{
	long result = 0;										long result = 0;
	do{													  loop:
		result+= x&0x1;										result+= x&0x1;
		x>>=1;		/*x=x>>1*/								x>>=1;
	}while(x);												if(x) goto loop;
	return result;											return result;
}														}

那么用汇编语言是这样来表达的：

1
2
3
4
5
6
7
8
	movl 	$0  ,%eax   		# result = 0
.L2:							# loop:
	movq 	%rdi,%rdx
	andl	$1	,%eax			# t = x&0x1
	addq 	%rdx,%rax			# result +=t
	shrq 	%rdi				# x>>=1
	jne		.L2					# if(x) goto loop
	rep;ret

​

while循环

那么while循环可以在do-while循环上修改一下即可

1
2
3
4
5
6
7
while (Test)			------>							goto test;
	Body											loop:
														Body
													test:
														if(Test)
															goto loop;
													done:

我们只要一上来直接goto test： 即可。这种方法叫做 jump to middle

还是一样的例子我们用while重写：

1
2
3
4
5
6
7
8
9
10
11
12
//C code												Goto Version
long pcount_while(unsigned long x)						long pcount_do(unsigned long x)					
{														{
	long result = 0;										long result = 0;
	while(x){												goto test;
		result+= x&0x1;									  loop: 
		x>>=1;		/*x=x>>1*/								 result += x&0x1;
	}												 		 x>>=1;
	return result;										  test:
    														 if(x) goto loop;
}														 	 return result;	
														}

我们还有第二种翻译方法，称之为 guarded-do, 首先用条件分支，进来就判断，如果初始条件不成立就跳过循环，把代码变换为do-while 循环。当使用较高优化等级编译的时候，例如使用命令行 -O1，GCC就会采用这种策略

可以用下面这种模板来表达这种方法，把通用的while循环格式翻译成 do-while 循环：

1
2
3
4
5
6
7
8
9
10
//C code												go-to Style
t = test-expr;											t = test-expr;
if (!t)                        							if (!t)  
	goto done;												goto done;
do 														loop:
	body-statement											body-statement
	while(test-expr);										t = test-expr;
done														if(t)
    															goto loop;
														done:

思考题：jump to middle 和 guared-do 什么时候是好的，什么时候是不好的？

guarded-do 是直接进行判断。这个之所以更加高效，是因为一开始进入循环时，通常不会不满足循环条件，即一开始不会跳转到后面，所以会直接顺序一直执行循环体。

for循环

for循环是我们很常用的一种循环体，其特点就是结束时间很明确，每一步都很标准。而while则更加自由。

for循环的模板：

1
2
for(init;Test;Update)
	Body

我们需要的就是将 for 循环转换成 while循环

1
2
3
4
5
Init;
while(Test){
	Body
	Update;
}

这里有很多表达式 ，还是拿原来的例子说

初始条件 Init: i=0

测试条件 Test: i<WSIZE

更新跳步 Update: i++

循环主题

1
2
3
4
{
	unsigned bit = (x>>i)&0x1;
	retult += bit;
}

根据上面的模板，我们可以对这段代码进行一个转换：

1
2
3
4
5
6
7
8
9
10
11
12
long pcount_for_while(unsigned long x){
	size_t i;
	long result = 0;
	i=0;
	while(i<WSIZE)
	{
		unsigned bit = (x>>i)&0x1;
		result += bit;
		i++;
	}
	return result;
}

我们还可以将For循环转换成 Do-While 循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
long pcount_for_goto_dw(unsigned long x){
	size_t i;
	long result = 0;
	i=0;								//Init
	/*
	if(!(i<WSIZE))						//可以删除的Test
		goto done;
	*/
  loop:
	while(i<WSIZE)						//Body
	{
		unsigned bit = (x>>i)&0x1;
		result += bit;
	}
	i++;								//Update
	if(!(i<WSIZE))						//Test
		goto done;
  done:	
	return result;						
}

为什么可以删除第一个Test呢，因为这里for循环第一次肯定是满足条件的。

switch 语句

switch 语句常常用在做命令行下的用户界面或者自动客服。当在写多分叉、较复杂的分支结构时，用if-else会导致可读性下降。

switch 不仅提高了C代码的可读性，而且通过使用跳转表(jump table) 这种数据结构让实现更加高效。GCC根据switch的数量和值的稀疏成都来翻译switch语句。当switch情况数量比较多,且值得范围跨度比较小的时候，就会使用跳转表。

下面是一个Jump Table 示意图

我们将每个代码块的地址填到Jump Table里面去。当我们执行switch中的代码块的时候，我们就使用 goto *JTab[x] 命令 *Jtab[x] 就是一段地址，我们会用goto直接跳到这个地址去。

我们来细致得解读一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
long my_switch(long x,long y,long z)
{
	long w=1;
	switch(x){
	case 1:
		w = y*z;
		break;
	case 2:
		w=y/z;
		/*Fall Through*/
	case 3:
		w+=z;
		break;
	case 5:
	case 6:
		w-=z;
		break;
	default:
		w=2;
	}
	return w;
}

这段代码编译出来的Jump table和switch得对应关系是这样的：

  • 当 x==1 的时候：

  • x==2的时候，因为没有break语句，所以执行完case2会继续执行 case3。 这个过程称为 Fall Through

  • x\=\=2 ，x\=\=3 时候的代码块如下：

  • x\=\=5 ,x\=\= 6 和defalut的代码块如下：

Summarizing

C Control

▪ if-then-else
▪ do-while
▪ while, for
▪ switch

Assembler Control

▪ Conditional jump
▪ Conditional move
▪ Indirect jump (via jump tables)
▪ Compiler generates code sequence to implement more complex control

Standard Techniques

▪ Loops converted to do-while or jump-to-middle form
▪ Large switch statements use jump tables
▪ Sparse switch statements may use decision trees (if-elseif-elseif-else)

过程

  • Mechanisms
  • Stack Structure
  • Calling Conventions
    • Passing control
    • Passing data
    • Managing local data
  • Illustration of Recursion

Mechanisms(机制)

要提供对过程的机器级支持，必须要处理许多不同的属性。为了讨论方便，假设过程P 调用过程Q， Q 执行后返回到P。 这些动作包括下面一个或多个机制：

  • 传递控制 ： 在进入过程Q的时候，程序计数器必须被设置为Q 的代码的起始地址，然后在返回时，要把程序计数器设置为p中调用Q后面那条指令的地址。
  • 传递数据： P 必须能够向Q提供一个或者多个参数，Q必须能够向P返回一个值
  • 内存管理：在开始时，Q可能需要为局部变量分配空间，而在返回前，又必须释放这些存储空间。

可以简单地说：过程 = 传递控制 + 传递参数 + 分配和释放内存

接下来，我们一步步地构建起不同的机制，先描述控制，再描述数据传递，最后是内存管理。

运行时栈

首先我们来看看栈结构，右侧长条是地址：

我们看到，栈顶指针指向最底下，因为x86-64的栈向低地址方向增长。

将栈放大来看，并标出地址增长和减小的方向：

我们可以用 pushq和popq指令来将数据存入栈中或者是从栈中取出。

Push

  • 首先将source中的操作数取出

  • 然后将栈顶指针指向的地址减去8, 因为下移8个byte之后，多出来 8*8 = 64 个bit可以用来存储一个64位的地址

  • 最后将这个操作数的地址写入栈顶指针

Pop

  • 首先将 %rsp 栈顶指针中的值读出
  • 然后将栈顶指针加上8
  • 最后将读出的值存入到寄存器当中

所以不管是 Push还是Pop，都是值改变了 $\%rsp$ 的值，并没有改变内存 。

栈帧

下面我们仔细谈论栈帧的概念。

当过程需要的存储空间超出寄存器能够存放的大小时，就会在栈上分配空间。这个部分称为过程的栈帧(Frame)。上图就是运行时栈的通用结构。

  • 当前正在执行的过程的帧总是在栈顶。
  • 当过程P调用过程Q的时候,会把返回地址压入栈中，指明Q返回时，要从p程序的哪个位置继续执行。我们会把这个返回地址当作p的栈帧的一部分，因为他存放的是于P相关的状态。

  • Q 的代码会扩展当前栈的边界，分配它的栈帧所需的空间。在这个空间中，它可以保存寄存器的值，分配局部变量空间，为它调用的过程设置参数。
  • 大多数过程的栈帧都是定长的，在过程的开始就分配好了
  • 通过寄存器，过程P 可以传递最多6 个整数值(也就是指针和整数), 但是如果Q 需要更多的参数，P 可以在调用Q 之前在自己的栈帧里存储好这些参数。

转移控制

P调用Q，Q运行完之后返回P，这个函数转移的底层是用栈实现的：

  • 首先将程序计数器(PC) 设置为 Q 的代码的起始位置。
  • 稍后从Q返回的时候，处理器用指令call Q 调用过程Q来记录好过程P需要继续执行的代码的位置，这个指令会把地址A压入栈中，并将PC设置为Q的起始地址。
  • 压入的地址A被称为返回地址，是紧跟在 call 指令后面的那条指令的地址。对应的指令ret会从栈中弹出地址A,并把pc设置为A

call 指令有一个目标，即指明被调用过程起始的指令地址。 调用可以是直接的也可以是间接的。在汇编代码中，直接调用的目标是一个Label，而间接调用的目标是 *加上一个操作数指示符

现在我们用一个具体的例子来理解：

1
2
3
4
5
6
7
8
9
10
11
Beginning of function multstore
0000000000400540 <multstore>:
400540: 53 					push %rbx
400541: 48 89 d3 			mov %rdx,%rbx
. . .
Return from function multstore
40054d: c3 					retq
. . .
Call to multstore from main
400563: e8 d8 ff ff ff 		callq 400540 <multstore>
400568: 48 8b 54 24 08 		mov 0x8(%rsp),%rdx

从上面这段代码中我们可以看到，在main函数中，地址为 0x400563 的call指令调用函数 multstore. 此时栈中的状态如图所示：

调用完call之后，栈中的状态如图：

也就是说，call的小姑就是将400563的后一句400568给压入栈中，并跳转到函数multistore的第一条指令，地址为 0x400540. 然后函数multstore继续执行，一直到遇上地址 0x40054d处的ret指令。

ret指令从栈中弹出值 0x400568,然后跳转到这个地址，就在call之后一句，然后继续main函数的执行。

再来看看上课居的例子：

1
2
3
4
5
6
7
8
9
10
void multstore(long x, long y, long *dest) 
{
	long t = mult2(x, y); 
	*dest = t;
}
long mult2(long a, long b)
{	
	long s = a * b; 
	return s;
}

将其编译成汇编语言，得到：

1
2
3
4
5
6
7
8
9
10
11
0000000000400540 <multstore>:
400540: push	%rbx 			# Save %rbx 
400541: mov 	%rdx,%rbx 		# Save dest 
400544: callq 	400550 <mult2>	# mult2(x,y) 
400549: mov 	%rax,(%rbx)		# Save at dest
40054c: pop 	%rbx			# Restore %rbx
40054d: retq					# Return
0000000000400550 <mult2>:
400550: 	mov  	  %rdi,%rax   	# a 
400553:		imul 	  %rsi,%rax		# a * b 
400557: 	retq					# Return

首先，运行到0x400544这一段，程序计数器%rip中存储的就是0x400544,他会调用 400550 地址的函数也就是 mult2

call运行完之后，%rip 中的地址变成了 0x400550 ，同时将call的后一句的地址压栈，并修改%rsp 的值

解这运行到了 400557 这行命令，就要return了，return操作是将栈顶取出放入 %rip 并退栈，最后%rip 的值为 0x400549

数据传送

当调用一个过程时，除了要把控制传递给它沐在过程返回时再传递回来之外，过程调用还可能包括把数据作为参数传递。我们大部分过程间的数据传送是通过寄存器实现的。

比如当过程P调用过程Q的时候，P的代码必须收i按将参数复制到合适的寄存器中。类似的，当Q返回到P的时候，P的代码可以访问寄存器 %rax 中的返回值。

x86-64中，可以通过寄存器最多传递6 个整型（例如整数和指针）参数(Argument)。寄存器的使用是有特殊顺序的.寄存器是按照特殊顺序来使用的，而使用的名字是根据参数的大小来确定的

比如：可以通过64 位寄存器适当的部分访问小于64 位的参数。如果第一个参数是32 位的，那么可以用％edi 来访问它。

重点：如果一个函数有大于6个整形的参数，超出六个的部分就要通过栈来传递。假设过程P调用过程Q，有n个参数，且n>6.那么p的代码分配的栈帧就必须要能容纳第七到第n号参数的存储空间。

通过栈传递参数时，所有的数据大小都向8的倍数对齐。参数到位以后，程序就可以执行call指令间控制转移到过程Q了。过程Q可以通过寄存器访问参数，也可以通过栈来访问。

相应的，如果Q也调用了某个有超过6个参数的函数，他也需要在自己的栈帧中为超出6个部分的参数分配空间。也就是分配到下图中 “Argument Build Area” (参数构造区) 的区域

下面是一个具体的例子：

有多个不同类型参数的函数示例。参数1~6 通过寄存器传递，而参数7~8 通过栈传递

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
(a) C code
void proc(	long a1, long *a1p,
		  	int a2, int *a2p,
		  	short a3, short *a3p,
			char a4, char *a4p	)
{
	*a1p += a1;
	*a2p += a2;
	*a3p += a3;
	*a4p += a4;
}
(b) Generated assembly code
    void proc(a1, a1p, a2, a2p, a3, a3p, a4, a4p)
    Arguments passed as follows:
        a1 in %rdi (64 bits)
        a1p in %rsi (64 bits)
        a2 in %edx (32 bits)
        a2p in %rcx (64 bits)
        a3 in %r8w (16 bits)
        a3p in %r9 (64 bits)
        a4 at %rsp+8 ( 8 bits)
        a4p at %rsp+16 (64 bits)
proc:
	movq 16(%rsp), %rax 	Fetch a4p (64 bits)
	addq %rdi, (%rsi)		*a1p += a1 (64 bits)
	addl %edx, (%rcx) 		*a2p += a2 (32 bits)
	addw %r8w, (%r9) 		*a3p += a3 (16 bits)
	movl 8(%rsp), %edx 		Fetch a4 ( 8 bits)
	addb %dl, (%rax) 		*a4p += a4 ( 8 bits)
	ret 				    Return

可以看到，作为过程调用的一部分，返回地址被压入栈中。因而这两个参数位于相对于栈指针距离为8 和16 的位置。在这段代码中，我们可以看到根据操作数的大小，使用了ADD 指令的不同版本：

  • al(long)使用addq
  • a2(int)使用addl
  • a3(short)使用addw
  • a4(char)使用addb
  • 请注意第6行的movl指令从内存读人4 字节，而后面的addb指令只使用其中的低位一字节。

栈上的局部存储

有些时候，局部数据必须存放在内存中，常见的情况包括：

  • 寄存器不足够存放所有的本地数据。
  • 对一个局部变量使用地址运算符 ‘&’，. 因此必须能够为它产生一个地址。
  • 某些局部变量是数组或结构，因此必须能够通过数组或结构引用被访问到。

一般来说，过程通过减小 栈指针在栈上分配空间。分配的结果作为栈帧的一部分，标号为”局部变量”

(a) Code for swap_add and calling function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long swap_add(long *xp, long *yp)
{
	long x = *xp;
	long y = *yp;
	*xp = y;
	*yp = x;
	return x + y;
}
long caller()
{
	long arg1 = 534;
	long arg2 = 1057;
	long sum = swap_add(&arg1, &arg2);
	long diff = arg1 - arg2;
	return sum * diff;
}

我们可以从下面这段汇编语言分析出caller是如何用栈帧来实现这些局部变量的。

  • 代码开始的时候把栈指针减了16，这是在栈上分配了16个字节
  • 将534，1057压栈，可以看到&arg2 = S+8 &arg1 = S.因此可以推断局部变量 arg1和arg2 存放在栈帧中的位置相对于栈顶指针的偏移量为0和8
  • add调用完成后，caller的代码会从栈上取出这两个值(因为进行过了swap操作，两个地址指向的值已经交换了)，并计算它们的差，再乘以 swap_add 在寄存器 %rax 中返回的值
  • 最后，该函数将栈顶指针加上16来释放栈帧。
1
2
3
4
5
6
7
8
9
10
11
12
13
long caller()
caller:
	subq 	$16, %rsp 				Allocate 16 bytes for stack frame
	movq 	$534, (%rsp) 			Store 534 in arg1
	movq 	$1057, 8(%rsp)			Store 1057 in arg2
	leaq 	8(%rsp), %rsi 			Compute &arg2 as second argument
	movq 	%rsp, %rdi 				Compute &arg1 as first argument
	call 	swap_add 				Call swap_add(&arg1, &arg2)
	movq 	(%rsp), %rdx 			Get arg1
	subq 	8(%rsp), %rdx 			Compute diff = arg1 - arg2
	imulq 	%rdx, %rax 				Compute sum * diff
	addq 	$16, %rsp 				Deallocate stack frame
	ret 							Return

下面是一个更复杂的例子。它给出了一个必须在栈上分配局部变量存储空间的函数，同时还要向有8个参数的proc传递值。

1
2
3
4
5
6
7
long call_proc()
{
long x1 = 1; int x2 = 2;
short x3 = 3; char x4 = 4;
proc(x1, &x1, x2, &x2, x3, &x3, x4, &x4);
return (x1+x2)*(x3-x4);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
long call_proc()
call_proc:
//Set up arguments to proc
subq 	$32, %rsp 			Allocate 32-byte stack frame
movq 	$1, 24(%rsp) 		Store 1 in &x1
movl 	$2, 20(%rsp) 		Store 2 in &x2
movw 	$3, 18(%rsp) 		Store 3 in &x3
movb 	$4, 17(%rsp) 		Store 4 in &x4
leaq 	17(%rsp), %rax 		Create &x4
movq 	%rax, 8(%rsp) 		Store &x4 as argument 8
movl 	$4, (%rsp) 			Store 4 as argument 7
leaq 	18(%rsp), %r9 		Pass &x3 as argument 6
movl 	$3, %r8d 			Pass 3 as argument 5
leaq 	20(%rsp), %rcx 		Pass &x2 as argument 4
movl 	$2, %edx 			Pass 2 as argument 3
leaq 	24(%rsp), %rsi 		Pass &x1 as argument 2
movl 	$1, %edi			Pass 1 as argument 1
//Call proc
call 	proc
//Retrieve changes to memory
movslq 	20(%rsp), %rdx 		Get x2 and convert to long
addq 	24(%rsp), %rdx 		Compute x1+x2
movswl 	18(%rsp), %eax 		Get x3 and convert to int
movsbl 	17(%rsp), %ecx 		Get x4 and convert to int
subl 	%ecx, %eax 			Compute x3-x4
cltq 						Convert to long
imulq 	%rdx, %rax 			Compute (x1+x2) * (x3-x4)
addq 	$32, %rsp 			Deallocate stack frame
ret 						Return

可以看到代码中一大部分是为调用proc做准备。其中包括为局部变量和参数建立栈帧，将函数参数加载至寄存器。

寄存器中的局部存储空间

被调用者保存寄存器

寄存器 %rbx 、%rbp 和 %r12~%r15 被划分为被调用者保存寄存器

过程P 调用过程 Q 的时候，Q必须保存这些寄存器的值，保证他们的值在Q返回到P时与Q被调用时是一样的。这时候有两种可能性，要门就是根本不去改变它，要么就是把原始值压入栈中，改变寄存器的值，然后再返回前从栈中弹出旧值。

调用者保存寄存器

除了%rsp和被调用者保存寄存器，剩下的都是调用者保存寄存器。这就意味着任何函数都能修改它们。

可以这样来理解“调用者保存”这个名字：过程P 在某个此类寄存器中有局部数据，然后调用过程Q 因为Q 可以随意修改这个寄存器，所以在调用之前首先保存好这个数据是P(调用者）的责任。

可以看看下面这个例子：

1
2
3
4
5
6
long(long x,long y)
{
	long u = Q(y);
	long v = Q(x);
	return u+v;
}

编译成汇编代码如下

可以看出来:%rbp 保存 x %rbx 保存计算出来的Q(y) 的值。

  • 在函数的开头，把两个寄存器的值保存到栈中(2~3行) 因为这两个寄存器之前可能有值
  • 第一次调用之前，把参数复制到 %rbp
  • 在第二次调用Q之前，把%rax(第一次计算的结果) 放到%rbx中
  • 在函数的结尾，将 %rbp和%rbx 从栈中弹出，恢复这两个被调用者保存寄存器的值，注意他们的弹出顺序和压入顺序相反。

递归过程

每个过程调用在栈中都有它自己的私有空间，因此多个未完成调用的局部变量不会相互影响。此外，栈的原则很自然地就提供了适当的策略，当过程被调用时分配局部存储，当返回时释放存储。

下面给出了递归的阶乘函数的C代码和汇编代码

1
2
3
4
5
6
7
8
9
10
11
12
13
(a) C code								(b) Generated assembly code //n in %rdi
long rfact(long n)						rfact:
{											pushq %rbx 			Save %rbx
    long result;							movq %rdi, %rbx		Store n in callee-saved register
    if (n <= 1)								movl $1, %eax		Set return value = 1
    	result = 1;							cmpq $1, %rdi		Compare n:1
    else									jle .L35 			If <=, goto done
	    result = n * rfact(n-1);			leaq -1(%rdi), %rdi Compute n-1
    return result;							call rfact			Call rfact(n-1)
}											imulq %rbx, %rax 	Multiply result by n
										.L35:
											popq %rbx 			Restore %rbx
											ret 				Return

我们可以看到，汇编代码使用寄存器 %rbx来保存参数n，先把已经有的值保存在栈上(2行)随后在返回前恢复该值(12行)

根据栈的使用特性和寄存器保存规则，可以保证当递归调用 rfact(n-1)返回时(第9行) 会发生：

  • 该次调用的结果会保存在寄存器 %rax 中
  • 参数n的值仍然存在寄存器 %rbx 中

把这两个值相乘就能得到期望的结果

从这个例子我们可以看到，递归调用一个函数本身与调用其他函数是一样的。栈规则提供了一种机制，每次函数调用都有它自己私有的状态信息（保存的返回位置和被调用者保存寄存器的值)存储空间。如果需要，它还可以提供局部变量的存储。栈分配和释放的规则很自然地就与函数调用-返回的顺序匹配。这种实现函数调用和返回的方法甚至对更复杂的情况也适用，包括相互递归调用（例如，过程P 调用Q，Q 再调用P)。

课后练习

1

2

3

4

5

6

7

8

9

10

11

12

13

z

-------------本文结束，感谢您的阅读-------------