CSAPP笔记02程序的机器级表示（上）

0x00 本章概述

​ 计算机直接执行机器代码，用字节序列编码低级操作，包括处理数据、管理内存、读写储存设备上的数据和网络通信。编译器基于编程语言的规则、目标机器的指令集和操作系统的管理，经过预处理、编译、汇编和链接四个步骤生成可执行的机器代码。gcc c语言编译器以汇编代码的形式产生输出，汇编语言是机器语言的文本形式。

​ 能够阅读和理解汇编代码是一项很重要的技能，阅读和理解编译器产生的汇编代码，能够①理解编译器的优化能力，并分析代码中隐藏的低效率。②了解到高级语言中的抽象层的具体实现。③了解底层漏洞是如何出现的，以及如何防护。

​ 源代码和对应的汇编代码之间的关系通常不容易建立，通过汇编代码推测出源代码是一种逆向工程（reverse engineering）。

​ 不同于高级语言，机器代码和具体的硬件平台直接相关，而中间的汇编语言，则又和负责编译的编译器有关。

​ 本章的机器代码基于x86-64，汇编语言版本是gcc默认的AT&T（业界另一种主流是Intel的版本），本章主要介绍x86-64中那些符合现代操作系统的特性，对于历史遗留的兼容特性，不做介绍。

​ 8086是第一代单芯片，16位微处理器之一，8087是浮点协处理器。

​ 80286提出了引入了保护模式。

​ 80386增加了平坦寻址模式（flat adressing model），并且将体系扩展到32位。

​ Pentium（奔腾系列）加入了条件传送，并引入了SSE指令，用来一次处理128位向量（主要用于浮点数，废除了x87协处理器） 增加了超线程（hyperthreading），该技术能够在同一个处理器上同时处理两个程序（不是分时占用）

​ Core（酷睿系列）加入了AVX指令，即SSE的扩展，一次能处理512位向量。

​ IA32是指Intel Architechure 32-bit，也包括现在的64位扩展，但是我们一般成为x86-64，也称作x86系列代指所有。

0x01 程序编码

gcc -Og p1.c p2.c -o p.out 

​ 上述命令能够生成符合原始c代码的机器代码，-Og即关闭优化。

​ gcc的工作流程：①gcc首先预处理c代码，将#include命令指定的文件插入进来，并替换所有用#define声明的宏。②编译器编译两个源文件，产生两个汇编文件，p1.s p2.s。③汇编器会将汇编代码转化成二进制目标文件代码p1.o和p2.o。目标代码是机器代码的一种形式，包含所有指令的二进制形式，但是还没有填入全局地址（在被运行时填入）。④链接器将两个目标代码文件与实现库函数（例如printf）的代码合并（.o文件），并最终产生可执行代码文件p.out

​ 机器级代码（汇编语言）：

​ 对于汇编或者机器语言，指令集架构（Instruction Set Architecture,ISA)定义了处理器的状态、指令的格式、以及每条指令对状态的影响，ISA将程序的行为描述成好像每条指令都是按顺序执行的，一条一条的，但实际上时并发执行许多指令的，但是最终运行结果和ISA指定的顺序执行的结果一致

​ 程序使用的是虚拟内存，将内存模型看作一个非常大的字节数组，但实际上，储存器系统的实现时多个硬件储存器和操作系统配合起来实现的。

​ 汇编/机器代码和原始的c的代码差别很大，因为c是对机器汇编的进一步抽象，隐藏了许多细节：

​ ①程序计数器 （Program Counter，PC），在x86-64(x86的64位扩展)上用%rip表示（%是AT&T的写法，Intel的汇编不用），给出下一条指令在内存（虚拟内存）中的地址。

​ ②通用寄存器16个，储存64位的数据，可以储存地址（对应c语言的指针）或者整数数据。

​ ③条件码寄存器（状态字寄存器/标志寄存器），保存着最近执行的指令的信息。

​ ④一组向量寄存器，用来保存一个或者多个整数或者浮点数。（SSE AVX）

​ 程序内存包括：程序的可执行机器码，操作系统的一些信息（调用历程？），用来管理过程调用和返回的运行时栈，以及用户分配的内存块（如malloc从堆中分配）。

​ 在x86-64中虚拟地址是64位的字长（8字节 ）来表示的，目前的操作系统中，高16位设置0，也就是低48位有效，实际能够访问的是0-64TB，操作系统负责管理虚拟地址空间，cpu根据操作系统的设置将虚拟地址翻译成物理地址。

​ 一条机器指令只执行一个非常基本的操作，如两个寄存器中的数字运算，储存器和寄存器之间传送数据（不支持直接储存器到储存器，DMA或许可以？），或者条件分支转移到新的指令地址。编译器负责从c语言转换到机器指令序列，从而是实现程序的结构（类似于表达式求值，循环或者过程调用和返回）。

​ 使用：

gcc -Og -S test.c

​ 可以将c语言文件预处理并编译成汇编文件，不继续汇编成机器指令。

​ 要查看机器代码对应的汇编指令，可以用反汇编器（disassembler），比如gdb调试或者objdump。也就是我们先用

gcc -Og test.c -o test.out

​ 将c代码生成可执行文件test.out，然后用:

objdump -d test.out

​ 指令就可以查看机器码对应的汇编指令。

​ 反汇编和机器代码的特性：

​ ①x86-64的指令从1-15字节不等，越常用指令所需字节越少

​ ②指令的设计方式是，从某个给定的位置开始，可以将字节唯一的解码成机器指令（对应二进制构造数的叶节点，参考huffman tree）

​ ③反汇编器只基于机器码中的字节序列来确定汇编代码。

​ ④反汇编器对汇编指令的命名和gcc生成的汇编代码略有不同，但是功能是一样的，比如反汇编生成的过程返回指令是retq（参考上图），而gcc生成的是ret。

​ 要生成实际可执行的diamond，需要对一组目标代码文件运行链接器，而这一组目标代码中必须有一个main函数：

gcc -Og main.c func.c -o 1.out

​ 文件1.out的大小远远大于这个文件生成的机器代码，因为还链接了用来启动和终止程序的机器代码，以及和操作系统交互的代码（例如pritf的代码）。

​ 汇编代码的格式：

​

​ 所有”.”开头的行都是指导汇编器和链接器工作的伪指令，阅读时通常可以忽略。

​ 本书中使用的时ATT(根据美国的通讯公司AT&T命名)，这是GCC和OBJDUMP等一些工具的默认格式，但是Microsoft以及Intel等使用的汇编代码是Intel格式的，这两种格式在许多方面有所不同：

​ ①Intel代码省略了指令大小的后缀，取而代之的是 double word ptr等，而ATT是movq movl。

​ ②Intel代码省略了寄存器前面的“%”，用的是rbx而不是ATT的”%rbx”。

​ ③ATT源操作数在左，目的操作数在右，而Intel的相反：

movq %rbx,%rax   ;ATT写法 rbx->rax
mov rbx,rax 	 ;Intel写法 rax->rbx

​ c语言允许内联汇编语言，或者用gcc命令和汇编代码合并起来。

0x02 数据格式

​ 由于x86系列处理器最开始是16位，因此Intel用字(word)来表示16位的数据类型，因此，城32位数为双字(double words)，64位为四字(quad words)

​ 以上是c语言中的基本数据类型在64为机器中对应的大小。大多数gcc生成的汇编代码指令都有一个字符后缀，用来表明操作数的大小（objdump里没这个后缀，Intel格式也没有）。例如mov指令就有movb（传送字节）movw（传送字）movl（传送双字） movq（传送四字）。

0x03 访问信息

​ x86-64cpu包括16个储存64为值的通用目的寄存器，用来储存整数或者地址（指针）。

​ 可以看到每个寄存器都有多个名字，不同名字对应这x86历史的不同时期cpu的位数，例如16位时期称为%ax（也可用%al,来访问8位）,32位时期则是%eax，64位是%rax。

​ 指令可以对这16个寄存器的不同位置进行访问，例如movq就是访问全部64位 movb访问低16位（不影响其余高48位）等等，但是就是movl比较特殊，或者说对低32位访问比较特殊，会自动清除高32位（历史遗留原因）。

​

​ 寻址方式：

​ 大多数指令有一个或者多个操作数，指示出要使用的数据的值的方法称为寻址方式，有三大类：

​ ①立即数immediate：ATT写法是$后面跟一个数字，不同指令的允许的立即数范围是不同的，比如movb （0-255）

​ ②寄存器register：表示某个寄存器里的内容，根据名称不同使用不同的寄存器里的不同部分（低8字节/低16字节/低32字节/全部64字节）

​ ③内存引用，根据计算出来的地址（通常称为有效地址/偏移地址,因为段地址存在），访问内存的某个位置。内存引用有4个部分 基址寄存器 变址寄存器 比例系数 立即数偏移，组合城的具体的寻址方式如下：

​

​ 数据传送指令：

​

​ 以上是最简单的数据传送指令mov类，几个指令的区别是传送的数据大小不同，需要注意的是，选用的寄存器要匹配，例如movw %ax,%bx 而不是movw %rax,%rax 因为是16为数据，要使用16位寄存器。x86-64限制，不能源操作数和目的操作数都是内存地址。

​ 以下是将位数较小的源操作数移动到位数较大的目的操作数的扩展移动指令：

​ 可以看到分为两类，0扩展和符号扩展，movz类和movs类（z:zero s:sign） 可以看到没有movzlq,因为movl就自动会将目的寄存器的高32位清零，movl %eax,%ebx即相当于movzlq %eax,%rbx。

​ 还有类似的专用扩展指令，cltq用来将%eax符号扩展成%rax。效果与movslq %eax,%rax效果完全一致。不过指令对应的机器码更短

​ 压入和弹出栈数据

​ pushq %rbp是压数据入栈相当于sub $8,%rsp movq %rbp,(%rsp)

​ popq %rbp则是出栈到%rbp 相当于movq (%rsp),%rbp addq $8,%rsp

​ 因为栈和程序的其他数据都是在同一内存（实际上是同一个段 平坦模型），所以可以用寻址方式直接访问栈中的数据，例如 movq 8(%rsp),%rdx 就是将栈顶的前一个4字复制到rdx里。

​

0x04 算数和逻辑操作

​ 以下是x86-64的整数和逻辑运算，除了leaq之外（因为leaq是对地址的操作，x86-64地址必是四字）都有四种不同数据大小的指令。他们分别是加载有效地址、一元操作，二元操作和位移：

​ SAL中的A即algorithm 算术算法

​

​ leaq指令

​ leaq即加载有效地址，实际是movq指令的变形，并不真的从内存读数据，而是直接将有效地址写入目的操作数。如

leaq 8(%rax),%rdi

​ 即是将8+%rax的值传送到%rdi。同时我们注意到，利用内存里数据的寻址方式，我们可以用leaq进行简单的加法和乘法运算,上面就进行了8+%rax的运算，可以更复杂比如：

long t=x+4*y+12*z; x in %rdi,y in %rsi,z in %rdx
;对应leaq实现：
leaq (%rdi,%rsi,4),%rax
leaq (%rdx,%rdx,2),%rdx
leaq (%rax,%rdx,4),%rax;

​ 一元和二元操作

​ 一元操作即操作数即是源又是目的，可以是寄存器和内存位置，如 incq %rax，即让%rax加1，这对应于c语言里的++ –。

​ 二元操作，左边是源操作数，右边是目的操作数，可以是内存单元或者寄存器，但是不能同时是内存单元。

​

​ 位移操作

​ 位移操作的左边操作数是位移量，右边是要位移的数，可以进行算术和逻辑位移（SAL/R SHL/R)，位移量可以是立即数，如果要是变动的量，位移量必须是%cl。算术位移适用于有符号数（右移不是右边不是添加0，而是添加1）

x<<4	sal $4,%rax
x>>n	sar %cl,%rax

​

​ 指令与符号的关系

​ 大多数指令既可以用于无符号数和有符号数（补码运算），只有类似与右位移和乘法mul和除法div区分有符号数和无符号数，右位移用无符号数用SHR，有符号数用SAR，乘法mul只适用无符号数，imul既使用无符号数又适用有符号数，除法同样。

​

​ 特殊的算术操作

​ 两个64位二进制数的乘法可能需要128位二进制数保存，也可能只要64位就可储存，那么imulq有以下两种格式：

imulq s,d ;d=d*s; 即两个64位二进制数相乘的结果可以用一个64位二进制数保存
imulq s   ; s * %rax,即s和%rax的值相乘，结果低64位在%rax里，高64位在%rdx里

​ 对于除法，128位/64位时，被除数的高64位放在%rdx里，低64位放在%rax里，结果商放在%rax里，余数放在%rdx里，例子如下：

long p=x/y;
long r=x%y;
*qp=p;
*rp=r;
;对应x86-64汇编 x in %rdi,y in %rsi,qp in %rdx,rp in %rcx 
movq %rdx,%r8;因为rdx将要被设置成被除数高64位，因此要备份
movq %rdi,%rax
cqto; change quad to oct 将%rax从四字转换成8字，也就是%rdx清零
idivq %rsi
movq %rax,(%r8)
movq %rdx,(%rcx)

0x05 流程控制

​ 前面的代码都是顺序执行，没有实现c语言中的条件、循环和分支流程等。这些都是要实现有条件的执行，实现有条件的执行，机器码提供两种方式：

​ ①测试数据，根据结果改变控制流（条件转移）

​ ②测试数据，根据结果改变数据流（条件传送）

​

​ 条件码

​ cpu中有一个条件码寄存器（condition register，又叫状态字寄存器）。它们描述了最近的算术/逻辑运算的属性，可以通过检测这些寄存器，来执行分支条件。常见的条件码有：

​ CF（cross flag）:进位标志，检查最近操作的结果作为无符号数时的溢出，溢出为1，否则为0。

​ ZF（zero flag）：零标志，检查最近操作的结果是否为0，如果为0，则置1，否则置0。

​ SF（sign flag）：符号标志，检查最近操作的结果作为有符号数时的符号，负数置1，否则置0。

​ OF（overflow flag）：溢出标志，检查最近操作的结果作为有符号数时的溢出（正溢出/负溢出），溢出为1，否则为0。

​ 任何运算指令（不论算术还是逻辑还是位移），都会改变条件码寄存器，其余的指令不改变，但是有特例，leaq不改变 inc类dec类不改变。

​ 除了运算指令会设置外，另外还有两类专门用来设置条件码寄存器的指令：

​ cmp指令类似于sub指令，cmp s,d 计算d-s的值，但是不把结果写回d，但是根据结果改变条件码。

​ test类似于and，同样是不写回结果，但是改变条件码。

​ 访问条件码

​ 条件码通常不会直接读取，使用的三种方式：①利用set类指令设置一个字节为0或者1。②利用条件码有条件地跳转。③利用条件码有条件地传送数据。

​ set类指令：

​ set类指令的名字即代表了满足对应的条件才将字节置1，比如：

cmpq %rax,5;
setge %cl;

​ 即%rax>=5时设置%cl为1，其具体原理是，如果%rax>=5，则cmpq %rax,5会将SF置0（结果大于0）OF置1（没有发生负溢出），因此~(OF^SF)=1。将%cl置1。

​ 同时可以看到，针对大于小于的情况，区分了有符号数和无符号数的判断。

​

​ 跳转指令

​ 跳转指令jmp，跳转指令改变指令执行顺序，跳转的目的通常用一个标号来指明。jmp是无条件跳转，可以是直接跳转，目标地址（或者偏移地址）作为指令的一部分编码；间接跳转，即目标地址在寄存器或者内存单元里，用”*“表示

jmp .l1;直接跳转
jmp *(%rax);间接跳转 用*表示，以rax的值作为跳转地址
jmp *%rax;间接跳转，用*表示以rax的值，从内存中读出跳转地址

​ 区别于jmp还有一类有条件跳转的指令，即满足对应条件才跳转的指令：

​ 跳转指令的编码

​ 理解跳转指令如何编码，对理解编译器如何链接十分重要，跳转指令有几种不同的编码，但是最常见的是 pc相对的（相对地址），也就是会将目标指令的地址与当前pc的地址（当前pc指向下一条指令而不是本条指令）之差作为编码。第二种方式是给出绝对地址（有效地址），给出的方式可以是直接（标号对应的imediate）也可以是间接的（寄存器/内存里）。

0x03	jmp .l1						;eb 03
0x05	sarq 1,%rax;将%rax算术右移1位	 ;48 d1 f8 	
		.l1:
0x08	testq %rax,%rax				 ;48 85 c0

​ 执行到jmp时 pc指向下一条，所以pc是0x05,因此机器指令中的偏移03，会让跳转到0x08，对应的testq语句。

​ 使用相对偏移的跳转的好处是，即使程序被执行时地址改变了，仍然可以正确跳转。

​

​ 条件指令实现条件分支

if(){
    
}else{
    
}
if(){
    goto true
}else{
    
}
goto done
true:

done:

​ 跳转对应于c中的goto，因此，将标准的if-else结果转化成goto实现。对应的汇编代码：

cmpq %rsi,%rsi
jge true
...
...
ret;ret即函数返回
true:
...
...
ret

​ 条件传送实现条件分支

​ 条件转移有一个巨大的缺点，跳转会清空流水线，而分支预测不总是命中的，现代处理器采用多级流水线，以实现各单元并行，提高效率，但是，遇到跳转时，之前读入流水线的指令要清除，需要重新读入，因此效率反而降低了，虽然有分支预测技术，但是并不总是命中的。程序中因该尽量减少跳转

​ 而条件传送则用非跳转实现了条件分支。比如：

if(x<0){
    return -x
}else{
    return x
}//x为long in %rdi
movq %rdi,%rax
movq %rdi,%rbx
negq %rbx
testq %rdi,%rdi
cmovl %rbx,%rax

​ 里面的cmovl即使条件传送指令，是l（less）时传送，也就是SF^OF为1时执行传送。cmov类指令如下：

​ 可以看到条件传送指令是将两个分支结果都先算出来，以其中一个为默认结果，然后根据条件码，有条件的传送另一个分支的结果。

​ 但是，需要注意的是，条件传送预先计算了then-expr和else-expr，因此不总是提高效率，如果这两个表达式计算量非常大，那么因为将两中情况的结果都计算了，反倒降低了效率。

​ 另外，可以看出条件传送使用情况有限，只能对计算结果有两个分支的，对于非计算结果的两个分支无能为力，并且不能在某一结果分支的运算过程中出现错误，例如：

long cread(long *xp){
    return (xp?*xp:0);
}

​ 乍一看，好像可以用条件传送，形成两个结果分支，再根据条件选择其中一个分支但是实际上，由于先运算两个结果，因此如果xp为空指针，那么*xp是非法的！因此不可以使用条件传送。

​

​ 循环

​ 循环其实是条件跳转的一种延申，通过跳转到之前的代码，实现多次执行同一段代码，当条件满足/不满足时继续往下执行，跳出循环。

​ c语言中有三种循环do while循环 while 循环以及for循环，将其转化成goto 实现 依次为：

//---------------do while
do:
//body-expr
if(test-expr)
    goto do
        
//---------------while
//区别于do主要是第一次执行body之前while要test
//而do while不用
  
//方式一        
//jump to middle to test before first do
goto test
do:
//body-expr
test:
if(test-expr)
    goto do
//方式二
//一开始判断一次，如果条件不满足，直接跳过循环。
if(!test-expr)
    goto done
do:
//body-expr
if(test-expr)
    goto do
        
        
//------------------for
//for的区别是 有初始化 有第一次检测和最后更新条件变量
init-expr
goto test
do:
body-expr
update-expr
test:
if(test-expr)
    goto do

​ 根据上述的goto版的c语言代码很容易翻译得到对应的汇编代码，不再赘述。

​

​ switch语句的实现

​ switch语句根据一个整数的索引值，进行多重分支。根据这句话，我们大概就可以猜到switch是如何实现的了，即跳转地址表。switch不仅仅提高了代码的可读性，其跳转地址表的实现也让其在面对多重分支时性能表现远远强于if-else分支（不判断，利用索引拿到跳转地址，只有一次跳转）。

​ 但是如果索引的跨度比较大，且比较分布比较稀疏时，那么跳转地址表的空间利用率就很低，因此编译器会根据具体的case分支情况判断是不是改用if-else的条件跳转。

​ 下面是一个典型的switch的c代码和对应的汇编代码：

void switch_eg(long x,long n,long*dest){
	long val=x;
	switch(n){
	case 100:
		val*=13;
		break;
	case 102:
		val+=10;//no break fall through
	case 103:
		val+=11;
		break;
	case 104:
	case 106:
		val*=val;
		break
	default:
		val=0;
	}
	*dest=val;
}

switch_eg: ;x in %rdi,n in %rsi,dest in %rdx
subq $100,%rsi
cmpq $6,%rsi
ja .l8;如果n大于6则就到default
jmp *.L4(%rsi,8);将.L4+8*%rsi对应的内容作为地址跳转
.L3:
leaq (%rdi,%rdi,2),%rax
leaq (%rdi,%rax,4),%rdi
jmp .L2
.L5:
addq $10,%rdi
;no jmp fall through
.L6:
addq $11,%rdi
jmp .L2
.L7:
imulq %rdi,%rdi
jmp .L2
.L8:
movl $0,%edi;movl会自动清0高32位,和movq $0,%rdi一样的
.L2:
movq %rdi,(%rdx)
ret

​ 对应的跳转表：

​ 执行switch的关键时通过跳转表来访问代码位置，汇编中是jmp *(,%rsi,8),有 * 表示是间接跳转，以内存单元的内容做跳转地址。