第三章：程序的机器级表示
3.1 历史观点
3.2 程序编码
3.2.0 编译过程（源文件 ——> 可执行文件的过程）
我们先准备一个简单的C语言源文件。
#include <stdio.h>
int main(){
printf("hello,world\n");
return 0;
}在Unix系统上,从源文件到目标文件的转化是由编译器驱动程序完成的:
linux> gcc -O hello hello.c
在这里, GCC编译器驱动程序读取源程序文件hello.c,并把它翻译成一个可执行目标文件hello
这个翻译过程可分为四个阶段完成
执行这四个阶段的程序(预处理器、编译器、汇编器和链接器)一起构成了编译系统(compilation system)
-
预处理阶段。预处理器(cpp)根据以字符
#开头的命令,修改原始的C程序。比如hello.c中第1行的#include <stdio.h>命令告诉预处理器读取系统头文件stdio.h的内容,并把它直接插人程序文本中。结果就得到了另一个C程序,通常是以.i作为文件扩展名。 -
编译阶段。编译器(ccl)将文本文件
hello.i翻译咸文本文件hello.s,它包含一个汇编语言程序。
该程序包含函数main的定义,如下所示:Dump of assembler code for function main: 0x0000000000001149 <+0>: endbr64 0x000000000000114d <+4>: push %rbp 0x000000000000114e <+5>: mov %rsp,%rbp 0x0000000000001151 <+8>: lea 0xeac(%rip),%rax # 0x2004 0x0000000000001158 <+15>: mov %rax,%rdi 0x000000000000115b <+18>: call 0x1050 <puts@plt> 0x0000000000001160 <+23>: mov $0x0,%eax 0x0000000000001165 <+28>: pop %rbp 0x0000000000001166 <+29>: ret End of assembler dump. -
汇编阶段。接下来,汇编器(as)将
hello.s翻译成机器语言指令,把这些指令打包成一种叫做可重定位目标程序(relocatable object program)的格式,并将结果保存在目标文件hello.o中。
hello.o文件是一个二进制文件,它包含的17个字节是函数main
的指令编码。如果我们在文本编辑器中打开hello.o文件,将看到一堆乱码。 -
链接阶段。请注意,
hello程序调用了printf函数,它是每个C编译器都提供的标准C库中的一个函数。
printf函数存在于一个名为printf.o的单独的预编译好了的目标文件中,而这个文件必须以某种方式合并到我们的hello.o程序中。
链接器(ld)就负责处理这种合并。
结果就得到hello文件,它是一个可执行目标文件(或者简称为可执行文件),可以被加载到内存中,由系统执行。
注意：
在学习时我们可以使用下面这种方法进行编译：
linux> gcc -Og -o hello hello.c因为编译选项-Og告诉编译器使用会生成符合原始C代码整体结构的机器代码的优化等级。使用较高级别优化产生的代码会严重变形,以至于产生的机器代码和初始源代码之间的关系非常难以理解。因此我们会使用-Og优化作为学习工具,然后当我们增加优化级别时,再看会发生什么。
实际中,从得到的程序的性能考虑,较高级别的优化(例如,以选项-O1或-O2指定)被认为是较好的选择。
3.2.1 基本概念
-
Instructure Set Architecture：指令集架构 (包括指令规格，寄存器等)，简称ISA，它是软硬件之间的“合同” -
Mircoarchitecture：指令集架构的具体实现方式 (比如流水线级数，缓存大小等)，它是可变的 -
Machine Code：机器码，也就是机器可以直接执行的二进制指令 -
Assembly Code：汇编码，也就是机器码的文本形式 (主要是给人类阅读) -
程序员的角度 vs 微体系结构 （程序员可见 vs 程序员不可见），在CPU方面，开放给程序员的编程接口只是PC，寄存器，条件码，其他的内部信息比如CPU内部的Cache对程序员来说都是不可见的，内存角度来讲，大部分的ISA支持字节寻址方式 (即Byte寻址，实际上还有Bit寻址，32-bit寻址，64-bit寻址等，只是比较少见而已)，绝大多数的ISA具有确定的大小端模式 (有些ISA可变)。
3.3 数据格式
由于是从16位体系结构扩展成32位的, Intel用术语“字(word)”表示16位数据类型。因此,称32位数为“双字(double words)”,称64位数为“四字(quad words)”。
| C声明 | Intel数据类型 | 汇编代码后缀 | 大小（字节） |
|---|---|---|---|
| char | 字节 | b | 1 |
| short | 字 | w | 2 |
| int | 双字 | l | 4 |
| long | 四字 | q | 8 |
| char* | 四字 | q | 8 |
| float | 单精度 | s | 4 |
| double | 双精度 | l | 8 |
大多数GCC生成的汇编代码指令都有一个字符的后缀,表明操作数的大
小。
例如,数据传送指令有四个变种: movb(传送字节)、 movw(传送字)、 movl(传送双字)和movq(传送四字)
3.4 访问信息
一个x86-64的中央处理单元(CPU)包含一组16个存储64位值的通用目的寄存器。这些寄存器用来存储整数数据和指针。图3-2显示了这16个寄存器。它们的名字都以%r开头,不过后面还跟着一些不同的命名规则的名字,这是由于指令集历史演化造成的。
最初的8086中有8个16位的寄存器,即图中的%ax到%bp。每个寄存器都有特殊的用途,它们的名字就反映了这些不同的用途。
扩展到IA32架构时,这些寄存器也扩展成32位寄存器,标号从%eax到%ebp。
扩展到x86-64后,原来的8个寄存器扩展成64位,标号从%rax到%rbp。除此之外,还增加了8个新的寄存器,它们的标号是按照新的命名规则制定的,从%r8到%r15。
在现在的程序中，这些寄存器除了
%rsp栈指针寄存器，%rip指令指针寄存器等,多数寄存器的用途与其命名不再有着严格的关联
下图是作者授课时的PPT，显示了调用参数时常用的寄存器
3.4.1 操作数指示符
- 立即数：在ATT格式的汇编代码中,立即数的书写方式是
$后面跟一个用标准C表示法表示的整数,比如,$-577或$0x1F。 - 寄存器
- 内存引用
3.4.2 数据传送指令
以MOV类为例：这些指令把数据从源位置复制到目的位置。
| 指令 | 效果 | 描述 |
|---|---|---|
| MOV S , D | S ——> D | 传送 |
| movb | 传送字节 | |
| movw | 传送字 | |
| movl | 传送双字 | |
| movq | 传送四字 | |
| movabsq I , R | I ——> R | 传送绝对的四字 |
注意：
- 源操作数指定的值是一个立即数,存储在寄存器中或者内存中。目的操作数指定一个位置,要么是一个寄存器或者,要么是一个内存地址。
- x86-64加了一条限制,传送指令的两个操作数不能都指向内存位置。将一个值从一个内存位置复制到另一个内存位置需要两条指令一第一条指令将源值加载到寄存器中,第二条将该寄存器值写人目的位置。
- x86_64重要特性：x86_64中的内存引用总是用四字长寄存器给出的，例如
%rax，哪怕操作数只是一个字节、一个字或者一个双字。
3.4.3 数据传送示例
C语言代码
long exchange(long *xp , long y){
long x = *xp;
*xp = y;
return x;
}汇编代码
#long exchange(long *xp, long y)
#xp in %rdi , y in %rsi
1 exchange :
2 movq (%rdi) , %rax #Get x at xp.Set as return value
3 movq %rsi , (%rdi) #Story y at xp
4 ret #Return当过程开始执行时,过程参数xp和y分别存储在寄存器%rdi和%rsi中。然后,指令2从内存中读出x,把它存放到寄存器%rax中,直接实现了C程序中的操作x=*xp。稍后,用寄存器%rax从这个函数返回一个值,因而返回值就是x。指令3将y写入到寄存器%rdi中的xp指向的内存位置,直接实现了操作*xp=y。
3.4.4 压入和弹出栈数据
入栈和出栈指令：
pushq指令的功能是把数据压入到栈上,而popq指令是弹出数据。
这些指令都只有一个操作数————压入的数据源和弹出的数据目的。
将一个四字值压入栈中,首先要将栈指针减8,然后将值写到新的栈顶地址。
因此,指令pushq %rbp的行为等价于下面两条指令
subq $8,%rsp #Decrement stack pointer
movq %rbp,(%rsp) #Store %rbp on stack它们之间的区别是在机器代码中pushq指令编码为1个字节,而上面那两条指令一共需要8个字节。
弹出一个四字的操作包括从栈顶位置读出数据,然后将栈指针加8。
因此,指令popq %rax等价于下面两条指令:
movq (%rsp),%rax #Read %rax from stack
addq $8,%rsp #Increment stack pointer3.5 算术和逻辑操作
下图列出看x86_64的一些整数和逻辑操作。
大多数操作都分成了指令类，这些指令类有各种带不同大小操作数的变种（只有leaq没有其他大小的变种），其基本规则与上述MOV类相同。
加载有效地址(leaq)指令通常用来执行简单的算术操作。其余的指令
是更加标准的一元或二元操作。我们用>>A和>>L来分别表示算术右移和逻辑右移。
注意,这里的操作顺序与ATT格式的汇编代码中的相反
3.5.1 加载有效地址（lea）
加载有效地址（load effective address）指令leaq实际上是movq指令的变形。
它的指令形式是从内存读数据到寄存器，单实际上它根本就没有引用内存。
它的第一个操作数看上去是一个内存引用，但是该指令并不是从指定的位置读入数据，而是将有效地址写入到目的操作数。
这条指令可以为后面的内存引用产生指针。
另外,它还可以简洁地描述普通的算术操作。例如,如果寄存器%rdx的值为x,那么指令leaq 7(%rdx,%rdx,4),%rax将设置寄存器%rax的值为5x+7。
编译器经常发现leaq的一些灵活用法,根本就与有效地址计算无关。
目的操作数必须是一个寄存器。
为了说明leaq在编译出的代码中的使用,看看下面这个C程序:
long scale(long x,long y,long z){
long t = x + 4 * y + 12 * z;
return t;
}编译时，该函数的算术运算以三条leaq指令实现
# long scale(long x,long y,long z)
# x in %rdi,y in %rsi,z in %rdx
scale:
leaq (%rdi,%rsi,4),%rax # x + 4*y
leaq (%rdx,%rdx,2),%rdx # z + 2*z = 3*z
leaq (%rax,%rdx,4),%rax # (x+4*y)+4*(3*z) = x + 4*y + 12*
ret3.5.2 一元和二元操作
3.5.3 移位操作
3.5.4 讨论
3.5.5 特殊的算术操作
3.6 控制
3.6.1 条件码
除了整数寄存器, CPU还维护着一组单个位的条件码(condition code)寄存器,它们描述了最近的算术或逻辑操作的属性。可以检测这些寄存器来执行条件分支指令。最常用的条件码有:
- CF:进位标志。最近的操作使最高位产生了进位。可用来检查无符号操作的溢出。
- ZF:零标志。最近的操作得出的结果为0。
- SF:符号标志。最近的操作得到的结果为负数。
- OF:溢出标志。最近的操作导致一个补码溢出一正溢出或负溢出
leaq指令不改变任何条件码,因为它是用来进行地址计算的。
3.6.2 访问条件码
条件码通常不会直接读取,常用的使用方法有三种:
- 可以根据条件码的某种组合,将一个字节设置为0或者1
- 可以条件跳转到程序的某个其他部分
- 可以有条件地传送数据
对于第一种方法，我们将这一整类指令称为SET指令
一个计算C语言表达式a<b的典型指令序列如下所示,这里a和b都是
long类型
# int comp(data_t a,data_t b)
# a in %rdi,b in %rsi
1 comp:
2 cmpq %rsi,%rdi # Compare a:b
3 setl %al # Set low-order byte of %eax to 0 or 1
4 movzbl %al,%eax #Clear rest of %eax(andd rest of %rax)
5 ret注意cmpq指令的比较顺序(第2行)。虽然参数列出的顺序先是%rsi(b)再是%rdi(a),
实际上比较的是a和b。
还要记得,正如在3.4.2节中讨论过的那样, movzbl指令不仅会
把%eax的高3个字节清零,还会把整个寄存器%rax的高4个字节都清零。
3.6.3 跳转指令
参考下面的伪汇编代码
movq $0,%rax #Set %rax to 0
jmp .L #Goto .L1
movq (%rax),%rdx #Null pointer dereference(skipped)
.L1:
popq %rdx #Jump target指令jmp .L1会导致程序跳过movq指令,而从popq指令开始继续执行。在产生目标代码文件时,汇编器会确定所有带标号指令的地址,并将跳转目标(目的指令的地址)编码为跳转指令的一部分
3.6.4 跳转指令的编码
虽然我们不关心机器代码格式的细节,但是理解跳转指令的目标如何编码,这对第7章研究链接非常重要。此外,它也能帮助理解反汇编器的输出。
在汇编代码中,跳转目标用符号标号书写。汇编器,以及后来的链接器,会产生跳转目标的适当编码。
跳转指令有几种不同的编码,但是最常用都是PC相对的(PC-relative)———— 它们会将目标指令的地址与紧跟在跳转指令后面那条指令的地址之间的差作为编码。这些地址偏移量可以编码为l、 2或4个字节。
第二种编码方法是给出绝对地址,用4个字节直接指定目标。
汇编器和链接器会选择适当的跳转目的编码。
下面是一个PC相对寻址的例子,这个函数的汇编代码由编译文件branch.c产生。它包含两个跳转:第2行的jmp指令前向跳转到更高的地址,而第7行的jg指令后向跳转到较低的地址。
1 movq %rdi,%rax
2 jmp .L2
3 .L3:
4 sarq %rax
5 .L2:
6 testq %rax,%rax
7 jg .L3
8 rep; ret汇编器产生的.o格式的反汇编版本如下:
1 0: 48 89 f8 mov %rdi,%rax
2 3: eb 03 jmp 8 <loop+0x8>
3 5: 48 d1 f8 sar %rax
4 8: 48 85 c0 test %rax,%rax
5 b: 7f f8 jg 5 <loop+0x5>
6 d: f3 c3 repz retq右边反汇编器产生的注释中,第2行中跳转指令的跳转目标指明为0x8,第5行中跳转指令的跳转目标是0x5(反汇编器以十六进制格式给出所有的数字)。不过,观察指令的字节编码,会看到第一条跳转指令的目标编码(在第二个字节中)为0x03,把它加上0x5,也就是下一条指令的地址,就得到跳转目标地址0x8,也就是第4行指令的地址。
3.6.5 用条件控制来实现条件分支
实现条件操作的传统方法是通过使用控制的条件转移。当条件满足时,程序沿着一条
执行路径执行,而当条件不满足时,就走另一条路径。
条件控制的方法与我们习惯的思维相同，先进行判断，选择分支后再执行分支内容。这与“goto代码”的编程风格相似。
汇编代码会利用上述的条件码和跳转指令来进行条件控制
举例：
//原始C语言代码
long lt_cnt = 0;
long ge_cnt = 0;
long absdiff_se(long x, long y) {
long result;
if (x < y) {
lt_cnt++;
result = y - x;
} else {
ge_cnt++;
result = x - y;
}
return result;
}//与之等价的goto版本
long gotodiff_se(long x,long y)
{
long result;
if(x >= y)
goto x_ge_y;
lt_cnt++;
result = y - x;
return result;
x_ge_y:
ge_cnt++;
result = x - y;
return result;
}# 产生的汇编代码
# long absdiff_se(long x ,long y)
# x in %rdi, y in %rsi
absdiff_se:
cmpq %rsi, %rdi # compare x and y
jge .L2 # if x >= y, jump to .L2
addq $1,lt_cnt(%rip) # lt_cnt++
movq %rsi, %rax
subq %rdi, %rax
ret # return
.L2:
addq $1,ge_cnt(%rip) # ge_cnt++
movq %rdi, %rax
subq %rsi, %rax # result = x - y
ret # return3.6.6 用条件传送来实现条件分支
条件控制这种机制简单而通用,但是在现代处理器上,它可能会非常低效。
一种替代的策略是使用数据的条件转移。
这种方法计算一个条件操作的两种结果,然后再根据条件是否满足从中选取一个。
只有在一些受限制的情况中,这种策略才可行,但是如果可行,就可以用一条简单的条件传送指令来实现它,条件传送指令更符合现代处理器的性能特性。
举例：
//原始的C语言代码
long absdiff(long x, long y) {
long result;
if (x < y) {
result = y - x;
} else {
result = x - y;
}
return result;
}//使用条件赋值的实现
long cmovdiff(long x, long y, long z)
{
long rval = y-x;
long eval = x-y;
long ntest = x >= y;
/*Line beloe requires single instruction:*/
if (ntest) rval = eval;
return rval;
}# 产生的汇编代码
# 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 and y
cmovge %rdx, %rax # If >=, rval = eval
ret # Retrun tval为了理解为什么基于条件数据传送的代码会比基于条件控制转移的代码性能要好，我们可以从处理器使用流水线获得高性能这一角度考虑
我们知道当流水线满载时效率最高，那就要求能够事先确定要执行的指令序列
然而，当机器遇到条件跳转(也称为“分支″)时,只有当分支条件求值完成之后,才能决定分支往哪边走。这就可能产生效率下降。
现代处理器解决这个问题的办法之一是：采用非常精密的分支预测逻辑来猜测每条跳转指令是否会执行。只要它的猜测还比较可靠(现代微处理器设计试图达到90%以上的成功率),指令流水线中就会充满着指令。另一方面,错误预测一个跳转,要求处理器丢掉它为该跳转指令后所有指令已做的工作,然后再开始用从正确位置处起始的指令去填充流水线。正如我们会看到的,这样一个错误预测会招致很严重的惩罚,浪费大约15-30个时钟周期,导致程序性能严重下降。
条件传送就是解决这一问题的另一办法，同条件跳转不同,处理器无需预测测试的结果就可以执行条件传送。处理器只是读源值(可能是从内存中),检查条件码,然后要么更新目的寄存器,要么保持不变。
下面补充一些条件传送指令。当传送条件满足时,指令把源值S复制到目的R。
不过！话又说回来......
不是所有的条件表达式都可以用条件传送来编译，使用条件传送也不总是会提高代码的效率。
例如,如果每个分支里执行的的求值需要大量的计算,那么当相对应的条件不满足时,这些工作就白费了。编译器必须考虑浪费的计算和由于分支预测错误所造成的性能处罚之间的相对性能。
说实话,编译器并不具有足够的信息来做出可靠的决定。例如,它们不知道分支会多好地遵循可预测的模式。我们对GCC的实验表明,只有当两个表达式都很容易计算时,例如表达式分别都只是一条加法指令,它才会使用条件传送。根据我们的经验,即使许多分支预测错误的开销会超过更复杂的计算, GCC还是会使用条件控制转移。
所以,总的来说,条件数据传送提供了一种用条件控制转移来实现条件操作的替代策略。它们只能用于非常受限制的情况,但是这些情况还是相当常见的,而且与现代处理器的运行方式更契合。
3.6.7 循环
C语言提供了多种循环结构,即do-While、 While和for。 汇编中没有相应的指令存在,可以用条件测试和跳转组合起来实现循环的效果。GCC和其他汇编器产生的循环代码主要基于两种基本的循环模式。
3.6.7.1 do-while循环
do-while语句通用格式如下：
do
body-statement
while (test-expr);这种通用形式可以被翻译成如下所示的条件和goto语句:
loop:
body-statement
t = test-expr;
if(t)
goto loop;举例：
//C代码
long fact_do(long n) {
long result = 1;
do {
result *= n;
n--;
} while (n > 0);
return result;
}//等价的goto版本
long fact_do_goto(long n)
{
long result = 1;
loop:
result *= n;
n = n - 1;
if (n > 1)
goto loop;
return result;
}# 对应的汇编代码
# long fact_do(long n)
# n in %rdi
fact_do:
movl $1,%eax # Set return value to 1
.L2: # loop:
imulq %rdi,%rax # Computr result *= n
subq $1,%rdi # Decrement n
cmpq $1,%rdi # Compare n with 1
jg .L2 # If n > 1, goto loop
rep; ret # Return result3.6.7.2 while循环
while语句的通用形式如下：
while (test-expr)
body-statementGCC在代码生成中使用两种翻译方法将其翻译为机器代码
第一种翻译方法：jump to middle
它执行一个无条件跳转跳到循环结尾处的测试,以此来执行初始的测试。可以用以下模板来表达这种方法,这个模板把通用的while循环格式翻译到goto代码:
goto test;
loop:
body-statement
test:
t = test-expr;
if(t)
goto loop;举例：
//C代码
long fact_while(long n) {
long result = 1;
while (n > 1) {
result *= n;
n--;
}
return result;
}//等价的goto版本
long fact_while_jm_goto(long n)
{
long result = 1;
goto test;
loop:
result *= n;
n--;
test:
if (n > 1)
goto loop;
return result;
}# 对应的汇编代码
# long fact_while(long n)
# n in %rdi
fact_while:
movl $1, %eax # Set result = 1
jmp .L5 # Goto test
.L6: # Loop
imulq %rdi, %rax # result *= n
subq $1, %rdi # n--
.L5: # Test
cmpq $1, %rdi # Compare n and 1
jg .L6 # If n > 1, goto loop
rep; ret # Return result第二种翻译方法,guarded-do
首先用条件分支,如果初始条件不成立就跳过循环,把代码变换为do-While循环。
把通用的while循环格式翻译成do-while循环:
t = test-expr;
if (!t)
goto done;
do
body-statement
while (test-expr);
done:相应地,还可以把它翻译成goto代码如下:
t = test-expr;
if (!t)
goto done;
loop:
body-statement
t = test-expr;
if (t)
goto loop;
done:举例：
// C代码
long fact_while(long n) {
long result = 1;
while (n > 1) {
result *= n;
n--;
}
return result;
}// 等价的goto版本
long fact_while_gd_goto(long n)
{
long result = 1;
if (n <= 1)
{
goto done;
}
loop:
result *= n;
n--;
if (n > 1)
{
goto loop;
}
done:
return result;
}# 对应的汇编代码
# long fact _while(long n)
# n in %rdi
fact_while:
cmpq $1, %rdi # Compare n with 1
jle .L7 # If n <= 1, goto done
movl $1, %eax # Set result to 1
.L6: # loop:
imulq %rdi, %rax # result *= n
subq $1, %rdi # n--
cmpq $1, %rdi # Compare n with 1
jne .L6 # If n != 1, goto loop
.L7: # done:
movl $1, %eax # Set result to 1
ret # Return3.6.7.3 for循环
for循环的通用形式如下:
for(init-expr;test-expr;update-expr)
body-statementC语言标准说明(有一个例外,一会说),这样一个循环的行为与下面这段使用while循环的代码的行为一样:
init-expr;
while(test-expr){
body-statement
update-expr;
}GCC为for循环产生的代码是while循环的两种翻译之一，这取决于优化的等级
- jump to middle策略产生的goto代码：
init-expr; goto test; loop: body-statement update-expr; test: t = test-expr; if (t) goto loop; - guarded-do策略产生的goto代码：
init-expr; t = test-expr; if(!t) goto done; loop: body-statement update-expr; t = test-expr; if(t) goto loop; done:
具体例子就不再赘述了。来说下特殊情况：
在C语言中执行continue语句会导致程序跳到当前循环迭代的结尾。当处理continue语句时,将for循环翻译成while循环的描述规则需要一些改进。
/* Example of for loop containing a continue statement */
/* Sum even numbers between 0 and 9 */
long sum = 0;
long i;
for(i = 0;i < 10;i++){
if (1 & i)
continue;
sum += i;
}倘若直接使用上述翻译规则会得到下面的代码：
/*Naive translation of for loop into while loop*/
/*WARNING:This is buggy code*/
long sum = 0;
long i = 0;
while(i < 10)
{
if(i & 1)
/*This will cause an infinite loop*/
continue;
sum += i;
i++;
}因为continue语句会阻止索引变量i被修改，所以这段代码是无限循环
通用的解决方法是用goto语句替代continue语句，它会跳过循环体中余下的部分，直接跳到update部分：
/*Correct translation of fot loop into while loop*/
long sum = 0;
long i = 0;
while (i < 10)
{
if (i & 1)
goto update;
sum += i;
update:
i++;
}3.6.8 switch语句
switch语句可以根据一个整数索引值进行多重分支(multiway branching)。在
处理具有多种可能结果的测试时,这种语句特别有用。它们不仅提高了C代码的可读性,
而且通过使用 跳转表(jump table) 这种数据结构使得实现更加高效。
跳转表是一个数组,表项i是一个代码段的地址,这个代码段实现当开关索引值等于士时程序应该采取的动作。程序代码用开关索引值来执行一个跳转表内的数组引用,确定跳转指令的目标。和使用一组很长的if-else语旬相比,使用跳转表的优点是执行开关语句的时间与开关情况的数量无关。GCC根据开关情况的数量和开关情况值的稀疏程度来翻译开关语句。当开关情况数量比较多(例如4个以上),并且值的范围跨度比较小时,就会便用跳转表。
举例：
void switch_eg(long x, long n, long *dest) {
long val = x;
switch(n) {
case 100:
val *= 13;
break;
case 102:
val += 10;
// Fall through
case 103:
val += 11;
break;
case 104:
case 106:
val *= val;
break;
default:
val = 0;
}
*dest = val;
}//翻译到拓展的C语言，表示出了跳转表
void switch_eg_impl(long x, long n, long *dest) {
/*Table of code pointers*/
static void *jt[7] = {
&&loc_A, &&loc_def, &&loc_B, &&loc_C, &&loc_D, &&loc_E, &&loc_F
};
unsigned long index = n - 100;
long val;
/*
原始的C代码有针对值100、 102-104和106的情况,
但是开关变量n可以是任意整数。
编译器首先将n减去100,把取值范围移到0和6之间,创建一个新的程序变量,
在我们的C版本中称为index
*/
if (index > 6) {
goto loc_def;
}
/*Multiway branch*/
goto *jt[index];
loc_A: /*Case 100*/
val = x * 13;
goto done;
loc_B: /*Case 102*/
val = x + 10;
goto done;
loc_C: /*Case 103*/
val = x + 11;
goto done;
loc_D: /*Case 104,106*/
val = x * x;
goto done;
loc_def: /*Default case*/
val = 0;
goto done;
done:
*dest = val;
}# 汇编代码
# void switch_eg(long x, long n, long *dest)
# x in %rdi, n in %rsi, dest in %rdx
switch_eg:
subq $100, %rsi # Compute index = n - 100
cmpq $6, %rsi # Compare index to 6
ja .L8 # If index > 6, goto loc_def
jmp *.L4(,%rsi,8) # Goto *jt[index]
.L3: # loc_A:
leaq (%rdi,%rdi,2),%rax 3*x
leaq (%rdi,%rax,4),%rdi val = 13*x
jmp .L2 # Goto done
.L5: # loc_B:
addq $10, %rdi # x += 10
.L6: # loc_C:
addq $11, %rdi # val = x + 11
jmp .L2 # Goto done
.L7: # loc_D:
imulq %rdi, %rdi # val = x*x
jmp .L2 # Goto done
.L8: # loc_def:
movl $0,%edi # val = 0
.L2: # done:
movq %rdi,(%rdx) # *dest = val
ret # Return3.7 过程
过程是软件中一种很重要的抽象。
它提供了一种封装代码的方式,用一组指定的参数和一个可选的返回值实现了某种功能。然后,可以在程序中不同的地方调用这个函数。设计良好的软件用过程作为抽象机制,隐藏某个行为的具体实现,同时又提供清晰简洁的接口定义,说明要计算的是哪些值,过程会对程序状态产生什么样的影响。不同编程语言中,过程的形式多样:函数(function),方法(method) ,子例程(subroutine) ,处理函数(handler)等等,但是它们有一些共有的特性。
要提供对过程的机器级支持,必须要处理许多不同的属性。
为了讨论方便,假设过程P调用过程Q, Q执行后返回到P。这些动作包括下面一个或多个机制:
- 传递控制：在进入过程Q的时候,程序计数器必须被设置为Q的代码的起始地址,然后在返回时,要把程序计数器设置为P中调用Q后面那条指令的地址。
- 传递数据： P必须能够向Q提供一个或多个参数, Q必须能够向P返回一个值。
- 分配和释放内存：在开始时, Q可能需要为局部变量分配空间,而在返回前,又必须释放这些存储空间。
3.7.1 运行时栈
C语言过程调用机制的一个关键特性(大多数其他语言也是如此)在于使用了栈数据结构提供的后进先出的内存管理原则。在过程P调用过程Q的例子中,可以看到当Q在执行时, P以及所有在向上追溯到P的调用链中的过程,都是暂时被挂起的。当Q运行时,它只需要为局部变量分配新的存储空间,或者设置到另一个过程的调用。另一方面,当Q返回时,任何它所分配的局部存储空间都可以被释放。因此,程序可以用栈来管理它的过程所需要的存储空间,栈和程序寄存器存放着传递控制和数据、分配内存所需要的信息。当P调用Q时,控制和数据信息添加到栈尾。当P返回时,这些信息会释放掉。
当x86-64过程需要的存储空间超出寄存器能够存放的大小时,就会在栈上分配空间。
这个部分称为过程的栈帧(stack fram)。
下图给出了运行时栈的通用结构,包括把它划分为栈帧。当前正在执行的过程的帧总是在栈顶。
当过程P调用过程Q时,会把返回地址压人栈中,指明当Q返回时,要从p程序的哪个位置继续执行。我们把这个返回地址当做P的栈帧的一部分,因为它存放的是与P相关的状态。Q的代码会扩展当前栈的边界,分配它的栈帧所需的空间。在这个空间中,它可以保存寄存器的值,分配局部变量空间,为它调用的过程设置参数。大多数过程的栈帧都是定长的,在过程的开始就分配好了。但是有些过程需要变长的帧。通过寄存器,过程P可以传递最多6个整数值(也就是指针和整数),但是如果Q需要更多的参数, P可以在调用Q之前在自已的栈帧里存储好这些参数。
再借助Deepseek理解一下栈帧吧
3.7.2 转移控制
将控制从函数P转移到函数Q只需要简单地把程序计数器(PC)设置为Q的代码的起始位置。
不过,当稍后从Q返回的时候,处理器必须记录好它需要继续P的执行的代码位置。在x86-64机器中,这个信息是用指令call Q调用过程Q来记录的。该指令会把地址A压人栈中,并将PC设置为Q的起始地址。压人的地址A被称为返回地址,是紧跟在call指令后面的那条指令的地址。对应的指令ret会从栈中弹出地址A,并把PC设置为A。
下表给出的是call和ret指令的一般形式:
| 指令 | 描述 |
|---|---|
| call Lable | 过程调用 |
| call *Operand | 过程调用 |
| ret | 从过程调用中返回 |
call指令有一个目标,即指明被调用过程起始的指令地址。同跳转一样,调用可以
是直接的,也可以是间接的。在汇编代码中,直接调用的目标是一个标号,而间接调用的
目标是*后面跟一个操作数指示符
我们以下面这段代码为例：
#include <stdio.h>
void multstore(long x, long y, long *dest) {
long t = x * y;
*dest = t;
}
int main() {
long d;
multstore(2, 3, &d);
printf("2 * 3 --> %ld\n", d);
return 0;
}节选其反汇编代码：
# 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。此时的状态如下图所示,指明了栈指针%rsp和程序计数器%rip的值o
call的效果是将返回地址0x400568压入栈中,并跳到函数multstore的第一条指令,地址为0x0400540。函数multstore继续执行,直到遇到地址0x40054d处的ret指令。这条指令从栈中弹出值0x400568,然后跳转到这个地址,就在call指令之后,继续main函数的执行。
这里的两个寄存器有着特殊、专一的功能：
%rsp：Stack Pointer Register,指向当前栈顶。%rip：Instruction Pointer Register，指向下一条要执行的指令。
3.7.3 数据传送
当调用一个过程时,除了要把控制传递给它并在过程返回时再传递回来之外,过程调用还可能包括把数据作为参数传递,而从过程返回还有可能包括返回一个值。x86-64中,大部分过程间的数据传送是通过寄存器实现的。
x86-64中,可以通过寄存器最多传递6个整型(例如整数和指针)参数。
寄存器的使用是有特殊顺序的,寄存器使用的名字取决于要传递的数据类型的大小。
如果一个函数有大于6个整型参数,超出6个的部分就要通过栈来传递。
假设过程P调用过程Q,有n个整型参数,且n>6。那么P的代码分配的栈帧必须要能容纳7到n号参数的存储空间。要把参数1~6复制到对应的寄存器,把参数7~n放到栈上,而参数7位于栈顶。
通过栈传递参数时,所有的数据大小都向8的倍数对齐。
以一个8参数的函数为例：
// C代码
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;
}# 汇编代码
# 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前面6个参数通过寄存器传递,后面2个通过栈传递,如下图所示，可以看到,作为过程调用的一部分,返回地址被压入栈中。因而这两个参数位于相对于栈指针距离为8和16的位置。在这段代码中,我们可以看到根据操作数的大小,使用了ADD指令的不同版本: a1(long)使用addq,a2(int)使用addl, a3(short)使用addw,而a4(char)使用addb。请注意第6行的movl指令从内存读人4字节,而后面的addb指令只使用其中的低位一字节。
3.7.4 栈上的局部存储
有些时候局部数据必须存放在内存中，常见情况包括：
- 寄存器不足够存放所有的本地数据。
- 对一个局部变量使用地址运算符
&,因此必须能够为它产生一个地址。 - 某些局部变量是数组或结构,因此必须能够通过数组或结构引用被访问到。
3.7.5 寄存器中的局部存储空间
寄存器组是唯一被所有过程共享的资源。
虽然在给定时刻只有一个过程是活动的,我们仍然必须确保当一个过程(调用者)调用另一个过程(被调用者)时,被调用者不会覆盖调用者稍后会使用的寄存器值。
为此, x86-64采用了一组统一的寄存器使用惯例,所有的过程(包括程序库)都必须遵循。
根据惯例,寄存器%rbx、%rbp和%r12~%r15被划分为被调用者保存寄存器。
当过程P调用过程Q时, Q必须保存这些寄存器的值,保证它们的值在Q返回到P时与Q被调用时是一样的。过程Q保存一个寄存器的值不变,要么就是根本不去改变它,要么就是把原始值压入栈中,改变寄存器的值,然后在返回前从栈中弹出旧值。压入寄存器的值会在栈帧中创建标号为“保存的寄存器”的一部分（参考3.7.1中图片）。有了这条惯例, P的代码就能安全地把值存在被调用者保存寄存器中(当然,要先把之前的值保存到栈上),调用Q,然后继续使用寄存器中的值,不用担心值被破坏。
所有其他的寄存器,除了栈指针%rsp,都分类为调用者保存寄存器。这就意味着任何函数都能修玫它们。可以这样来理解“调用者保存”这个名字:过程P在某个此类寄存器中有局部数据,然后调用过程Q。因为Q可以随意修改这个寄存器,所以在调用之前首先保存好这个数据是P(调用者)的责任。
举例：
//调用函数
long P(long x,long y)
{
long u = Q(y);
long v = Q(x);
return u + v;
}# 汇编代码
# long P(long x,long y)
x in %rdi, y in %rsi
1 P:
2 pushq %rbp # save %rbp
3 pushq %rbx # save %rbx
4 subq $8, %rsp # align stack frame
5 movq %rdi, %rbx # x -> %rbx save x
6 movq %rsi, %rdi # mobv y to first argument
7 call Q # call Q(y)
8 movq %rax,%rbx # save result
9 movq %rbp, %rdi # move x to first argument
10 call Q # call Q(x)
11 addq %rbx, %rax # Q(x) + Q(y)
12 addq $8, %rsp # deallocate last part of stack
13 popq %rbx # restore %rbx
14 popq %rbp # restore %rbp
15 ret # return这个函数需要两次调用Q，在第一次调用中,必须保存x的
值以备后面使用。类似地,在第二次调用中,也必须保存Q(y)的值。
从汇编语句可以看出，GCC生成的代码使用了两个被调用者保存寄存器,%rbp保存x和%rbx保存计算出来的Q(y)的值。
在函数的开头,把这两个寄存器的值保存到栈中(第2-3行)。在第一次调用Q
之前,把参数x复制到%rbp(第5行)。在第二次调用Q之前,把这次调用的结果复制到%rbx(第8行)。在函数的结尾, (第13-14行),把它们从栈中弹出,恢复这两个被调用者保存寄存器的值。注意它们的弹出顺序与压入顺序相反,说明了栈的后进先出规则。
3.7.6 递归过程
前面已经描述的寄存器和栈的惯例使得x86-64过程能够递归地调用它们自身。每个过程调用在栈中都有它自已的私有空间,因此多个未完成调用的局部变量不会相互影响。此外,栈的原则很自然地就提供了适当的策略,当过程被调用时分配局部存储,当返回时释放存储。
递归调用一个函数本身与调用其他函数是一样的。
栈规则提供了一种机制,每次函数调用都有它自已私有的状态信息(保存的返回位置和被调用者保存寄存器的值)存储空间。如果需要,它还可以提供局部变量的存储。栈分配和释放的规则很自然地就与函数调用一返回的顺序匹配。这种实现函数调用和返回的方法甚至对更复杂的情况也适用,包括相互递归调用(例如,过程P调用Q, Q再调用P)。
举例：
long rfact(long n)
{
long result;
if (n <= 1)
{
result = 1;
}
else
{
result = n * rfact(n - 1);
}
return result;
}# 汇编代码
# long rfact(long n)
# n in %rdi
rfact:
pushq %rbx # save %rbx
movq %rdi, %rbx # store n in callee-saved register
movl $1, %eax # set return value to 1
cmpq $1, %rdi # compare n with 1
jle .L35 # if n <= 1, goto done
leaq -1(%rdi), %rdi # n = n - 1
call rfact # recursive call
imulq %rbx, %rax # return value = n * rfact(n-1)
.L35: # done
popq %rbx # restore %rbx
ret # return3.8 数组分配和访问
3.8.1 基本原则
关于C语言中数组的基本定义和引用方式在这里就不赘述了
3.8.2 指针运算
C语言允许对指针进行运算,而计算出来的值会根据该指针引用的数据类型的大小进行伸缩。
单操作数操作符&和*可以产生指针和间接引用指针
3.8.3 嵌套的数组
当我们创建数组的数组时,数组分配和引用的一般原则也是成立的。
3.8.4 定长数组
我们以一个计算矩阵A、B乘积的代码及其优化为例
这段代码包含很多聪明的优化。它去掉了整数索引j,并把所有的数组引用都转换成了指针间接引用,其中包括:
(1)生成一个指针,命名为Aptr,指向A的行i中连续的元素;
(2)生成一个指针,命名为Bptr,指向B的列k中连续的元素;
(3)生成一个指针,命名为Bend,当需要终止该循环时,它会等于Bptr的值。
Aptr的初始值是A的行i的第一个元素的地址,由C表达式&A[i][0]给出o。Bptr的初始值是B的列k的第一个元素的地址,由C表达式&B[0][k]给出。Bend的值是假想中B的列j的第(n+1)个元素的地址,由C表达式&B[N][k]给出。
// 原始C代码
# define N 16
typedef int fix_matrix[N][N];
/*Compute i,k of fixed matrix product*/
int fix_prod_ele(fix_matrix A,fix_matrix B,long i,long k)
{
long j;
int result=0;
for(j=0;j<N;j++)
result+=A[i][j]*B[j][k];
return result;
}// 优化后的C代码(编译器会自动完成这些优化)
# define N 16
typedef int fix_matrix[N][N];
/*Compute i,k of fixed matrix product*/
int fix_prod_ele(fix_matrix A,fix_matrix B,long i,long k)
{
int *Aptr = &A[i][0]; /*Points to elements in row i of A*/
int *Bptr = &B[0][k]; /*Points to elements in column k of B*/
int *Bend = &B[N][k]; /*Marks stopping point for Bptr*/
int result = 0;
do{ /*No need for initial test*/
result += *Aptr * *Bptr;/*Add next product to sum*/
Aptr++; /*Move Aptr to next column*/
Bptr += N; /*Move Bptr to next row */
}while(Bptr != Bend); /*Test for stopping point*/
return result;
}# int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k)
# A in %rdi, B in %rsi, i in %rdx, k in %rcx
fix_prod_ele:
salq $6, %rdx # Compute 64 * i
addq %rdx, %rdi # Compute Aptr = x_A + 64i = &A[i][0]
leaq (%rsi,%rcx,4), %rcx # Compute Bptr = x_B + 4k = &B[0][k]
leaq 1024(%rcx), %rsi # Compute Bend = x_B + 4k + 1024 = &B[N][k]
movl $0, %eax # Set result = 0
.L7: # loop:
movl (%rdi), %edx # Read *Aptr
imull (%rcx), %edx # Multiply by *Bptr
addl %edx, %eax # Add to result
addq $4, %rdi # Increment Aptr ++
addq $64, %rcx # Increment Bptr += N
cmpq %rsi, %rcx # Compare Bptr:Bend
jne .L7 # If !=, goto loop
rep; ret # Return3.8.5 变长数组
在变长数组的C版本中,我们可以将一个数组声明如下:
int A[expr1][expr2]它可以作为一个局部变量,也可以作为一个函数的参数,然后在遇到这个声明的时候,通过对表达式expr和expr求值来确定数组的维度。因此，例如要访问n*n数组的元素i,j，我们可以写一个如下的函数
int var_ele(long n ,int A[n][n],long i,long j){
return A[i][j];
}参数n必须在参数A[n][n]之前,这样函数就可以在遇到这个数组的时候计算出数组的维度。
GCC为这个引用函数产生的代码如下所示：
# int var_ele(long n ,int A[n][n],long i,long j)
# n in %rdi, A in %rsi, i in %rdx, j in %rcx
var_ele:
imulq %rdx, %rdi # Compute n*i
leaq (%rsi,%rdi,4), %rax # Compute x_A + 4(n*i)
movl (%rax,%rcx,4), %eax # Read from M[x_A + 4(n*i) + 4*j]
ret这个地址的计算类似于定长数组的地址计算,不同点在于:
- 由于增加了参数n,寄存器的使用变化了;
- 用了乘法指令来计算
n*i(第2行),而不是用leaq指令来计
算3i.
因此引用变长数组只需要对定长数组做一点儿概括。动态的版本必须用乘法指令对i伸缩n倍,而不能用一系列的移位和加法。在一些处理器中,乘法会招致严重的性能处罚,但是在这种情况中无可避免。
在一个循环中引用变长数组时,编译器常常可以利用访问模式的规律性来优化索引的计算,例如下面这种优化：
/*Compute i,k of variable matrix product*/
int var_prod_ele(long n,int A[n][n],int B[n][n],long i,long k)
{
long j;
int result=0;
for(j=0;j<n;j++)
{
result+=A[i][j]*B[j][k];
}
return result;
}/*编译器自动执行这些优化*/
/*Compute i,k of variable matrix product*/
int var_prod_ele(long n,int A[n][n],int B[n][n],long i,long k)
{
int *Arow=A[i];
int *Bptr=&B[0][k];
int result=0;
long j;
for(j=0;j<n;j++){
result+=Arow[j]*(*Bptr);
Bptr+=n;
}
return result;
}# var_prod_ele的循环的汇编代码:
#Registers: n in %rdi, Arow in %rsi, Bptr in %rcx, 4n in %r9, result in %eax, j in %edx
.L24: # loop:
movl (%rsi,%rdx,4), %r8d # Read Arow[j]
imull (%rcx), %r8d # Multiply by *Bptr
addl %r8d, %eax # Add to result
addq $1, %rdx # j++
addq %r9, %rcx # Bptr += n
cmpq %rdi, %rdx # Compare j:n
jne .L24 # If !=, goto loop我们看到程序既使用了伸缩过的值4n(寄存器%r9)来增加Bptr,也使用了n的值(寄存器%rdi)来检查循环的边界。C代码中并没有体现出需要这两个值,但是由于指针运算的伸缩,才使用了这两个值。
可以看到,如果允许使用优化, GCC能够识别出程序访间多维数组的元素的步长。然后生成的代码会避免直接应用等式会导致的乘法。不论生成基于指针的代码还是基于数组的代码,这些优化都能显著提高程序的性能。
3.9 异质的数据结构
3.9.1 结构
类似于数组的实现,结构的所有组成部分都存放在内存中一段连续的区域内,而指向结构的指针就是结构第一个字节的地址。
编译器利用偏移量对结构中的对象进行引用
一下面这个结构声明为例：
struct rec{
int i;
int j;
int a[2];
int *p;
};这个结构包括4个字段:两个4字节int、一个由两个类型为int的元素组成的数组和一个8字节整型指针,总共是24个字节:
为了访间结构的字段,编译器产生的代码要将结构的地址加上适当的偏移。
例如,假设struct rec*类型的变量r放在寄存器%rdi中。那么下面的代码将元素r->i复制到元素r->j:
# Registers: r in %rdi
movl (%rdi),%eax # Get r->i
movl %eax,4(%rdi) # Store in r->j要产生一个指向结构内部对象的指针,我们只需将结构的地址加上该字段的偏移量。
例如,只用加上偏移量8+4*1=12,就可以得到指针&(r->a[1])。对于在寄存器%rdi中的指针r和在寄存器%rsi中的长整数变量i,我们可以用一条指令产生指针&(r->a [i])的值:
# Registers:r in %rdi ,i in %rsi
leaq 8(%rdi,%rsi,4) , %rax # Set %rax to $r->a[i]详细解析一下上述汇编代码，顺便巩固一下关于lea的用法：
leaq：Load Effective Address (Quadword)，计算有效地址并将其存储到目标寄存器中。%rdi：第一个寄存器，存储基地址。%rsi：第二个寄存器，存储索引值。4：比例因子（scale factor），表示索引值需要乘以 4。8：偏移量（displacement），表示在计算结果的基础上加上 8。%rax：目标寄存器，计算结果将存储到这里。
8(%rdi, %rsi, 4) 的计算公式为：
地址 = 基地址 + 索引值 * 比例因子 + 偏移量
也就是
%rax = %rdi + %rsi * 4 + 8
最后举一个例子,下面的代码实现的是语句:r->p = &r->a[r->i + r->j];
# Regidters: r in %rdi
movl 4(%rdi),%eax # Get r->j
addl (%rdi),%eax # Add r->i
cltq # Extend to 8 bytes
leaq 8(%rdi,%rax,4),%rax # Compute %r->a[r->i+r->j]
movq %rax,16(%rdi) # Store in r->p综上所述,结构的各个字段的选取完全是在编译时处理的。机器代码不包含关于字段声明或字段名字的信息。
3.9.2 联合
联合提供了一种方式,能够规避C语言的类型系统,允许以多种类型来引用一个对象。联合声明的语法与结构的语法一样,只不过语义相差比较大。它们是用不同的字段来引用相同的内存块。
考虑下面的声明：
struct S3
{
char c;
int i[2];
double v;
};
union U3
{
char c;
int i[2];
double v;
};在一台x86_64Linux机器上编译，字段的偏移量、数据类型S3和U3的完整大小如下：
| 类型 | c | i | v | 大小 |
|---|---|---|---|---|
| S3 | 0 | 4 | 16 | 24 |
| U3 | 0 | 0 | 0 | 8 |
一个联合的总大小等于它最大字段的大小
接下来的例子将展示联合的作用
假设我们想实现一个二叉树的数据结构，每个叶子节点都有两个double类型的数据值，而每个内部节点都有指向两个孩子节点的指针，但是没有数据。
如果以结构声明
struct node_s
{
struct node_s *left;
struct node_s *right;
double data[2];
};那么每个节点都需要32个字节，每种类型的节点都要浪费一半的字节。
相反，如果我们用联合声明一个节点
union node_u{
struct {
union node_u *left;
union node_u *right;
}internal;
double data[2];
};那么每个节点就只需要16个字节。如果n是一个指针，指向union node_u*类型的节点，我们用n -> data[0]和n -> data[1]来引用叶子结点的数据，而用n -> internal.left和n -> internal.right来引用内部节点的孩子。
不过如果这样编码，就没有办法来确定一个给定的节点到底是叶子节点还是内部节点。通常的方法是引入一个枚举类型，定义这个联合中可能的不同选择，然后再创建一个结构，包含一个标签字段和这个联合：
typedef enum { N_LEAF, N_INTERNAL } nodetype_t;
struct node_t{
nodetype_t type;
union{
struct{
struct node_t *left;
struct node_t *right;
} internal;
double data[2];
} info;
};这个结构总共需要24个字节:type 是4个字节,info.internal.left 和 info.internal.right 各要8个字节,或者是 info.data 要16个字节。我们后面很快会谈到,在字段type 和联合的元素之间需要4个字节的填充,所以整个结构大小为4+4+16=24。在这种情况中,相对于给代码造成的麻烦,使用联合带来的节省是很小的。对于有较多字段的数据结构,这样的节省会更加吸引人。
联合还可以用来访问不同数据类型的位模式。例如,假设我们使用简单的强制类型转
换将一个 double 类型的值d转换为 unsigned long 类型的值u:
unsigned long u = (unsigned long) d;
值u会是d的整数表示。除了d的值为0.0的情况以外,u的位表示会与d的很不一样。
再看下面这段代码,从一个 double 产生一个 unsigned long 类型的值:
unsigned long double2bits (double d) {
union {
double d;
unsigned long u;
} temp;
temp.d = d;
return temp.u;
};在这段代码中,我们以一种数据类型来存储联合中的参数,又以另一种数据类型来访
问它。结果会是u具有和d一样的位表示,包括符号位字段、指数和尾数,如3.11 节中
描述的那样。u的数值与d的数值没有任何关系,除了等于0.0的情况。
3.9.3 数据对齐
许多计算机系统对基本数据类型的合法地址做出了一些限制,要求某种类型对象的地
址必须是某个值K(通常是2、4或8)的倍数。这种对齐限制简化了形成处理器和内存系统之间接口的硬件设计。
无论数据是否对齐,x86-64 硬件都能正确工作。不过,Intel 还是建议要对齐数据以
提高内存系统的性能。
对齐原则是:任何K 字节的基本对象的地址必须是K的倍数。
可以看到这条原则会得到如下对齐:
| K | 类型 |
|---|---|
| 1 | char |
| 2 | short |
| 4 | int, float |
| 8 | long, char*,double |
对于包含结构的代码,编译器可能需要在字段的分配中插入间隙,以保证每个结构元
素都满足它的对齐要求。而结构本身对它的起始地址也有一些对齐要求。
比如说,考虑下面的结构声明:
struct S1 {
int i;
char c;
int j;
};
蓝色部分就是为了 数据对齐填充的部分
合理安排结构中对象的顺序才不会因为数据对齐导致内存的浪费
3.10 在机器级程序中将控制与数据结合起来
3.10.1 理解指针
指针的关键原则：
- 每个指针都对应一个类型。
- 每个指针都有一个值。这
- 指针用
&运算符创建 *操作符用于间接引用指针。- 数组与指针紧密联系。
- 将指针从一种类型强制转换成另一种类型,只改变它的类型,而不改变它的值。
- 指针也可以指向函数。
关于函数指针，作者给我们这样的提示：
函数指针声明的语法对程序员新手来说特别难以理解。对于以下声明:
int (*f)(int*);要从里(从f开始)往外读。因此,我们看到像(*f)表明的那样,f是一个指针;
而(*f) (int* )表明f是一个指向函数的指针,这个函数以一个 int* 作为参数。
最后,我们看到,它是指向以 int * 为参数并返回 int 的函数的指针。
*f 两边的括号是必需的,否则声明变成
int *f(int*);它会被解读成
(int *) f(int*);也就是说,它会被解释成一个函数原型,声明了一个函数 f,它以一个 int * 作为参数
并返回一个 int *。
3.10.2 应用:使用 GDB 调试器
3.10.3 内存越界引用和缓冲区溢出
C对于数组引用不进行任何边界检查,而且局部变量和状态信息(例如保存的寄存器值和返回地址)都存放在栈中。
一种特别常见的状态破坏称为缓冲区溢出(buffer overflow)。通常,在栈中分配某个字符数组来保存一个字符串,但是字符串的长度超出了为数组分配的空间。下面这个程序示例就说明了这个问题:
/* Implementation of library function gets() */
char *gets(char *s)
{
int c;
char *dest = s;
while ((c = getchar()) != '\n' && c ! = EOF)
*dest++ = c;
if (c == EOF && dest == s)
/* No characters read */
return NULL;
*dest++ = '\0'; /* Terminate string */
return s;
}
/* Read input line and write it back */
void echo()
{
char buf [8]; /* Way too small! */
gets (buf);
puts (buf);
}前面的代码给出了库函数 gets 的一个实现,用来说明这个函数的严重问题。它从标准输入读入一行,在遇到一个回车换行字符或某个错误情况时停止。它将这个字符串复制到参数s指明的位置,并在字符串结尾加上 null 字符。在函数 echo 中,我们使用了 gets,这个函数只是简单地从标准输入中读入一行,再把它回送到标准输出。
gets 的问题是它没有办法确定是否为保存整个字符串分配了足够的空间。在 echo 示例中,我们故意将缓冲区设得非常小——只有8个字节长。任何长度超过7个字符的字符串都会导致写越界。
检查 GCC为echo产生的汇编代码,看看栈是如何组织的:
# void echo()
1 echo:
2 subq $24, %rsp # Allocate 24 bytes on stack
3 movq %rsp, %rdi # Compute buf as %rsp
4 call gets # Call gets
5 movq %rsp, %rdi # Compute buf as %rsp
6 call puts # Call puts
7 addq $24, %rsp # Deallocate stack space
8 ret # Return字符串到23个字符之前都没有严重的后果,但是超过以后,返回指针的值以及更多可能的保存状态会被破坏。如果存储的返回地址的值被破坏了,那么 ret 指令(第8行)会导致程序跳转到一个完全意想不到的位置。
| 输入的字符数量 | 附加的被破坏的状态 |
|---|---|
| 0~7 | 无 |
| 9~23 | 未被使用的栈空间 |
| 24~31 | 返回地址 |
| 32+ | caller 中保存的状态 |
缓冲区溢出的一个更加致命的使用就是让程序执行它本来不愿意执行的函数。这是一种最常见的通过计算机网络攻击系统安全的方法。通常,输入给程序一个字符串,这个字符串包含一些可执行代码的字节编码,称为攻击代码(exploit code),另外,还有一些字节会用一个指向攻击代码的指针覆盖返回地址。那么,执行 ret 指令的效果就是跳转到攻击代码。
在一种攻击形式中,攻击代码会使用系统调用启动一个 shell 程序,给攻击者提供一组操作系统函数。在另一种攻击形式中,攻击代码会执行一些未授权的任务,修复对栈的破坏,然后第二次执行 ret 指令,(表面上)正常返回到调用者。
3.10.4 对抗缓冲区溢出攻击
3.10.4.1 栈随机化
栈随机化的思想使得栈的位置在程序每次运行时都有变化。因此,即使许多机器都运行同样的代码,它们的栈地址都是不同的。实现的方式是:程序开始时,在栈上分配一段0~字节之间的随机大小的空间,例如,使用分配函数 alloca 在栈上分配指定字节数量的空间。程序不使用这段空间,但是它会导致程序每次执行时后续的栈位置发生了变化。分配的范围n必须足够大,才能获得足够多的栈地址变化,但是又要足够小,不至于浪费程序太多的空间。
下面的代码是一种确定“典型的”栈地址的方法:
int main() {
long local;
printf("local at %p\n", &local);
return 0;
}在Linux 系统中,栈随机化已经变成了标准行为。它是更大的一类技术中的一种,这类技术称为地址空间布局随机化(Address-Space Layout Randomization),或者简称 ASLR
3.10.4.2 栈破坏检测
最近的GCC 版本在产生的代码中加入了一种栈保护者(stack protector) 机制,来检测缓冲区越界。其思想是在栈帧中任何局部缓冲区与栈状态之间存储一个特殊的金丝雀(canary)值。这个金丝雀值,也称为哨兵值(guard value),是在程序每次运行时随机产生的,因此,攻击者没有简单的办法能够知道它是什么。
在恢复寄存器状态和从函数返回之前,程序检查这个金丝雀值是否被该函数的某个操作或者该函数调用的某个函数的某个操作改变了。如果是的,那么程序异常中止。
最近的GCC版本会试着确定一个函数是否容易遭受栈溢出攻击,并且自动插入这种溢出检测。实际上,对于前面的栈溢出展示,我们不得不用命令行选项-fno-stack-protector来阻止 GCC产生这种代码。
3.10.4.3 .限制可执行代码区域
最后一招是消除攻击者向系统中插入可执行代码的能力。一种方法是限制哪些内存区域能够存放可执行代码。在典型的程序中,只有保存编译器产生的代码的那部分内存才需要是可执行的。其他部分可以被限制为只允许读和写。
3.10.5 支持变长栈帧
为了管理变长栈帧,x86-64 代码使用寄存器%rbp 作为帧指针(frame pointer)(有时称为基指针(base pointe))。当使用帧指针时码必须把%rbp 之前的值保存到栈中,因为它是一个被调用者保存寄存器。然后在函数的整个执行过程中,都使得%rbp指向那个时刻栈的位置,然后用固定长度的局部变量(例如i)相对于%rbp的偏移量来引用它们。
以变长数组为例：
long vframe(long n, long idx, long *q) {
long i;
long *p[n];
p[0] = &i;
for (i = 1; i < n; i++)
p[i] = q;
return *p[idx];
}# long vframe(long n, long idx, long *b(
# n in %rdi, idx in %rsi, qin %rdx
# Only portions of code shown
1 vframe:
2 pushq %rbp # Save old %rbp
3 movb %rsp, %rbp # Set frame pointer
4 subq $16, %rsp # Allocate space for i (%rsp = s1(
5 leaq 22(,%rdi,8), %rax
6 andq $-16, %rax
7 subq %rax, %rsp # Allocate space for array p (%rsp = s2)
8 leaq 7(%rsp), %rax
6 shrq $3, %rax
10 leaq 0(,%rax,8), %r8 # Set %r8 to &p[0]
11 movq %r8, %rcx # Set %rcx to &p[0] (%rcx = p)
...
# Code for initialization loop
# i in %rax and on stack, n in %rdi, pin %rcx, q in %rdx
12 .L3: # loop:
13 movq %rdx, (%rcx,%rax,8) # Set p[i] to q
14 addq $1, %rax # Increment i
15 movq %rax, -8(%rbp) # Store on stack
16 .L2:
17 movq -8(%rbp), %rax # Retrieve i from stack
18 cmpq %rdi, %rax # Compare i:n
19 jl .L3 # If <, goto loop
...
# Code for function exit
20 leave # Restore %rbp and %rsp
21 ret # Return函数 vframe 的栈帧结构,该函数使用寄存器%rbp作为帧指针
在较早版本的x86 代码中,每个函数调用都使用了帧指针。而现在,只在栈帧长可变的情况下才使用,就像函数 vframe 的情况一样。历史上,大多数编译器在生成IA32 代码时会使用帧指针。最近的GCC 版本放弃了这个惯例。可以看到把使用帧指针的代码和不使用帧指针的代码混在一起是可以的,只要所有的函数都把%rbp 当做被调用者保存寄存器来处理即可。
3.11 浮点代码
《csapp》这本书的讲述基于AVX2。
AVX 浮点体系结构允许数据存储在16个 YMM 寄存器中,它们的名字为%ymm0~%ymm15。每个 YMM 寄存器都是256位(32字节)。当对标量数据操作时,这些寄存器只保存浮点数,而且只使用低32位(对于 float)或64位(对于 double)。汇编代码用寄存器的SSE XMM 寄存器名字%xmm0%xmm15 来引用它们,每个 XMM 寄存器都是对应的YMM 寄存器的低128位(16字节)。
3.11.1 浮点传送和转换操作
下表给出了一组在内存和 XMM 寄存器之间以及从一个XMM 寄存器到另一个不做任何转换的传送浮点数的指令。
引用内存的指令是标量指令,意味着它们只对单个而不是一组封装好的数据值进行操作。数据要么保存在内存中(由表中的M_32 和M_64 指明,表示32、64位内存范围),要么保存在 XMM 寄存器中(在表中用 X 表示)。无论数据对齐与否,这些指令都能正确执行,不过代码优化规则建议 32位内存数据满足4字节对齐,64位数据满足8字节对齐。内存引用的指定方式与整数 MOV 指令的一样,包括偏移量、基址寄存器、变址寄存器和伸缩因子的所有可能的组合。
| 浮点传送指令 | 源 | 目的 | 描述 |
|---|---|---|---|
| vmovss | M_32 | X | 传送单精度数 |
| vmovss | X | M_32 | 传送单精度数 |
| vmovsd | M_64 | X | 传送双精度数 |
| vmovsd | X | M_64 | 传送双精度数 |
| vmovaps | X | X | 传送对齐的封装好的单精度数 |
| vmovapd | X | X | 传送对齐的封装好的双精度数 |
GCC 只用标量传送操作从内存传送数据到XMM 寄存器或从 XMM 寄存器传送数据到内存。对于在两个 XMM 寄存器之间传送数据,GCC 会使用两种指令之一,即用vmovaps 传送单精度数,用vmovapd 传送双精度数。对于这些情况,程序复制整个寄存器还是只复制低位值既不会影响程序功能,也不会影响执行速度,所以使用这些指令还是针对标量数据的指令没有实质上的差别。指令名字中的字母“a'表示“aligned(对齐的)”。当用于读写内存时,如果地址不满足16字节对齐,它们会导致异常。在两个寄存器之间传送数据,绝不会出现错误对齐的状况。
下面是一个不同浮点传送操作的例子,考虑以下C函数
float float_mov(float v1, float *src, float *dst) {
float v2 = *src;
*dst = vl;
return v2;
}与它相关联的x86-64 汇编代码为
# float float_mov(float v1, float *src, float *dst)
# v1 in %xmm0, src in %rdi, dst in %rsi
1 float_mov:
2 vmovaps %xmmO, %xmm1 # Copy v1
3 vmovss (%rdi), %xmm0 # Read v2 from src
4 vmovss %xmm1, (%rsi) # Write v1 to dst
5 ret # Return v2 in %xmm0下表的指令把一个从XMM 寄存器或内存中读出的浮点值进行转换,并将结果写入一个通用寄存器(例如%rax、%ebx等)。把浮点值转换成整数时,指令会执行截断(truncation),把值向0进行舍入。
| 双操作数浮点转换指令 | 源 | 目的 | 描述 |
|---|---|---|---|
| vcvttss2si | X/M_32 | R_32 | 用截断的方法把单精度数转换成整数 |
| vcvttsd2si | X/M_64 | R_32 | 用截断的方法把双精度数转换成整数 |
| vcvttss2siq | X/M_32 | R_64 | 用截断的方法把单精度数转换成四字整数 |
| vcvttsd2siq | X/M_64 | R_64 | 用截断的方法把双精度数转换成四字整数 |
下表指令把整数转换成浮点数。它们使用的是不太常见的三操作数格式,有两个源和一个目的。第一个操作数读自于内存或一个通用目的寄存器。这里可以忽略第二个操作数,因为它的值只会影响结果的高位字节。而我们的目标必须是XMM 寄存器。
| 三操作数浮点转换指令 | 源1 | 源2 | 目的 | 描述 |
|---|---|---|---|---|
| vcvtsi2ss | M_32/R_32 | X | X | 把整数转换成单精度数 |
| vcvtsi2sd | M_32/R_32 | X | X | 把整数转换成双精度数 |
| vcvtsi2ssq | M_64/R_64 | X | X | 把四字整数转换成单精度数 |
| vcvtsi2sdq | M_64/R_64 | X | X | 把四字整数转换成双精度数 |
在最常见的使用场景中,第二个源和目的操作数都是一样的,就像下面这条指令:
vcvtsi2sdq %rax, %xmm1, %xmm1
这条指令从寄存器%rax 读出一个长整数,把它转换成数据类型 double,并把结果存放进XMM 寄存器%xmm1 的低字节中。
3.11.2 过程中的浮点代码
在x86-64中,XMM 寄存器用来向函数传递浮点参数,以及从函数返回浮点值。
有如下规则：
- XMM寄存器
%xmm0~%xmm7最多可以传递8个浮点参数。按照参数列出的顺序使用这些寄存器。可以通过栈传递额外的浮点参数。 - 函数使用寄存器
%xmm0来返回浮点值。 - 所有的XMM 寄存器都是调用者保存的。被调用者可以不用保存就覆盖这些寄存器
中任意一个。
3.11.3 浮点运算操作
下表描述了一组执行算术运算的标量 AVX2 浮点指令。每条指令有一个(S)或两个(S1, S2)源操作数,和一个目的操作数D。第一个源操作数S 可以是一个XMM 寄存器或一个内存位置。第二个源操作数和目的操作数都必须是 XMM 寄存器。每个操作都有一条针对单精度的指令和一条针对双精度的指令。结果存放在目的寄存器中。
| 单精度 | 双精度 | 效果 | 描述 |
|---|---|---|---|
| vaddss | vaddsd | D <- S2 + S1 | 浮点数加 |
| vsubss | vsubsd | D <- S2 - S1 | 浮点数减 |
| vmulss | vmulsd | D <- S2 * S1 | 浮点数乘 |
| vdivss | vdivsd | D <- S2/S1 | 浮点数除 |
| vmaxss | vmaxsd | D <- max(S2, S1) | 浮点数最大值 |
| vminss | vminsd | D <- min(S2, S1) | 浮点数最小值 |
| sqrtss | sqrtsd | D <- √S1 | 浮点数平方根 |
3.11.4 定义和使用浮点常数
和整数运算操作不同,AVX 浮点操作不能以立即数值作为操作数。相反,编译器必须为所有的常量值分配和初始化存储空间。然后代码在把这些值从内存读入。
3.11.5 在浮点代码中使用位级操作
对封装数据的位级操作(这些指令对一个XMM 寄存器中的所有128位进行布尔操作)
| 单精度 | 双精度 | 效果 | 描述 |
|---|---|---|---|
| vxorps | vorpd | D <- S2 ^ S1 | 位级异或(EXCLUSIVE-OR) |
| vandps | andpd | D <- S2 & S1 | 位级与(AND) |
3.11.6 浮点比较操作
AVX2 提供了两条用于比较浮点数值的指令:
| 指令 | 基于 | 描述 |
|---|---|---|
| ucomiss S1, S2 | S2-S1 | 比较单精度值 |
| ucomisd S1, S2 | S2-S1 | 比较双精度值 |
这些指令类似于CMP 指令(参见 3.6节),它们都比较操作数 S 和S(但是顺序可能与预计的相反),并且设置条件码指示它们的相对值。与cmpg 一样,它们遵循以相反顺序列出操作数的ATT 格式惯例。参数 S2 必须在XMM 寄存器中,而S可以在XMM 寄存器中,也可以在内存中。
浮点比较指令会设置三个条件码:零标志位 ZE、进位标志位 CF 和奇偶标志位 PF。
条件码的设置条件如下:
| 顺序S2:S1 | CF | ZF | PF |
|---|---|---|---|
| 无序的 | 1 | 1 | 1 |
| S2 < S1 | 1 | 0 | 0 |
| S2 = S1 | 0 | 1 | 0 |
| S2 > S1 | 0 | 0 | 0 |
3.12 小结
在本章中,我们窥视了C语言提供的抽象层下面的东西,以了解机器级编程。通过让编译器产生机器级程序的汇编代码表示,我们了解了编译器和它的优化能力,以及机器、数据类型和指令集。在第5章,我们会看到,当编写能有效映射到机器上的程序时,了解编译器的特性会有所帮助。我们还更完整地了解了程序如何将数据存储在不同的内存区域中。在第12章会看到许多这样的例子,应用程序员需要知道一个程序变量是在运行时栈中,是在某个动态分配的数据结构中,还是全局程序数据的一部分。理解程序如何映射到机器上,会让理解这些存储类型之间的区别容易一些。
机器级程序和它们的汇编代码表示,与C程序的差别很大。各种数据类型之间的差别很小。程序是以指令序列来表示的,每条指令都完成一个单独的操作。部分程序状态,如寄存器和运行时栈,对程序员来说是直接可见的。本书仅提供了低级操作来支持数据处理和程序控制。编译器必须使用多条指令来产生和操作各种数据结构,以及实现像条件、循环和过程这样的控制结构。我们讲述了C语言和如何编译它的许多不同方面。我们看到C语言中缺乏边界检查,使得许多程序容易出现缓冲区溢出。虽然最近的运行时系统提供了安全保护,而且编译器帮助使得程序更安全,但是这已经使许多系统容易受到恶意入侵者的攻击。
我们只分析了C到x86-64 的映射,但是大多数内容对其他语言和机器组合来说也是类似的。例如,编译 C++ 与编译C就非常相似。实际上,C++ 的早期实现就只是简单地执行了从 C++ 到C的源到源的转换,并对结果运行C编译器,产生目标代码。C++ 的对象用结构来表示,类似于C的 struct。C++的方法是用指向实现方法的代码的指针来表示的。相比而言,Java 的实现方式完全不同。Java 的目标代码是一种特殊的二进制表示,称为Java 字节代码。这种代码可以看成是虚拟机的机器级程序。正如它的名字暗示的那样,这种机器并不是直接用硬件实现的,而是用软件解释器处理字节代码,模拟虚拟机的行为。另外,有一种称为及时编译(just-in-time compilation)的方法,动态地将字节代码序列翻译成机器指令。当代码要执行多次时(例如在循环中),这种方法执行起来更快。用字节代码作为程序的低级表示,优点是相同的代码可以在许多不同的机器上执行,而在本章谈到的机器代码只能在x86-64 机器上运行。
摘自原文3.12