程序的机器级表示

机器级代码

  • 计算机系统使用了多种不同形式的抽象，利用更简单的抽象模型来隐藏实现的细节。对于机器级编程来说，其中两种抽象尤为重要。
    • 第一种是由指令集体系结构或指令集架构(Instruction Set Architecture,ISA)来定义机器级程序的格式和行为，它定义了处理器状态、指令的格式，以及每条指令对状态的影响。
    • 第二种抽象是，机器级程序使用的内存地址是虚拟地址，提供的内存模型看上去是一个非常大的字节数组。存储器系统的实际实现是将多个硬件存储器和操作系统软件组合起来。
  • C语言编译过程中，将把用C语言提供的相对比较抽象的执行模型表示的程序转化成处理器执行的非常基本的指令。
  • 汇编代码表示非常接近于机器代码。与机器代码的二进制格式相比，汇编代码的主要特点是它用可读性更好的文本格式表示。
    • x86-64的机器代码和原始的C代码差别非常大。一些通常对C语言程序员隐藏的处理器状态都是可见的。
      • 程序计数器(通常称为"PC"，在x86-64中用%rip表示)给出将要执行的下一条指令在内存中的地址。
      • 整数寄存器文件包含16个命名的位置，分别存储64位的值。这些寄存器可以存储地址（对应于C语言的指针）或整数数据。有的寄存器被用来记录某些重要的程序状态，而其他的寄存器用来保存临时数据，例如过程的参数和局部变量，以及函数的返回值。
      • 条件码寄存器来保存着最近执行的算术或逻辑指令的状态信息。它们用来实现控制或数据流中的条件变化，比如说用来实现if和which语句。
      • 一组向量寄存器可以存放一个或多个整数或浮点数值。
  • 虽然C语言提供了一种模型，可以在内存中声明和分配各种数据类型的对象，但是机器代码知识简单地将内存看成一个很大的、按字节寻址地数组。C语言中的聚合数据类型，例如数组和结构，在机器代码中用一组连续的字节来表示。

x86指令特点

  • x86-64的指令长度从1到15个字节不等。常用的指令以及操作数较少的指令所需的字节数少，而那些不太常用或操作数较多的指令所需字节数较多
  • 设计指令格式的方式是，从某个给定位置开始，可以将字节唯一地解码成机器指令。
  • 反汇编器只是基于机器代码文件中地字节序列来确定汇编代码。它不需要访问该程序地源代码或汇编代码
  • 反汇编器使用的指令命名规则与GCC生成的汇编代码使用的有些细微的差别。

数据格式

  • 字(word)表示16位数据类型。因此，称32位数为"双字(double words)"，称64位数为"四字(quand words)"。

    • C声明Intel数据类型汇编代码后缀大小（字节）
      char字节b1
      short字w2
      int双字l4
      long四字q8
      char*四字q8
      float单精度s4
      double双精度l8

访问信息

  • 一个x86-64的中央处理单元(CPU)包含一组16个存储64位值的通用目的寄存器。
    • 最初的8060中有8个16位的寄存器，%ax到%sp。扩展到x86-64后，原来的8个寄存器扩展成64位，标号从%rax到'%rsp'。除此之外，还新增了8个新的寄存器，标号是按照新的命名规则制定的：从%r8到%r15

操作数指示符

  • 大多数指令有一个或多个操作数(operand)，指示出执行一个操作中要使用的源数据值，以及放置结果的目的位置。各种不同的操作数的可能性被分为三种类型。

    • 第一种类型是立即数（immediate）：用来表示常数值。立即数的书写方式是'$'后面跟一个用标准C表示法表示的整数。

    • 第二种类型是寄存器(register)：它表示某个寄存器的内容。用符号$r_a$来表示任意寄存器$a$，用引号$R[r_a]$来表示它的值，这是将寄存器集合看成一个数组R，用寄存器标识符作为索引。

    • 第三类操作数是内存引用，他会根据计算出来的地址(通常称为有效地址)访问某个内存位置。用符号$M_b[Addr]$表示对存储在内存中从地址$Addr$开始的b个字节值的引用。为了方便，通常省去下标b。

      • 类型格式操作数值名称
        立即数$$Imm$$Imm$立即数寻址
        寄存器$r_a$$R[r_a]$寄存器寻址
        存储器$Imm$$M[Imm]$绝对寻址
        存储器$r_a$$M[R[r_a]]$间接寻址
        存储器$Imm(r_b)$$M[Imm+R[r_b]]$(基址+偏移量)寻址
        存储器$(r_b,r_i)$$M[R[r_b]+R[r_i]]$变址寻址
        存储器$Imm(r_b,r_i)$$M[Imm+R[r_b]+R[r_i]]$变址寻址
        存储器$(,r_b,r_i)$$M[R[r_i]*s]$比例变址寻址
        存储器$Imm(,r_i,s)$$M[Imm+R[r_i]*s]$比例变址寻址
        存储器$(r_b,r_i,s)$$M[R[r_b]+R[r_i]*s]$比例变址寻址
        存储器$Imm(r_b,r_i,s)$$M[Imm+R[r_b]+R[r_i]*s]$比列变址寻址

数据传输指令

  • 将数据从一个位置复制到另一个位置的指令。

  • MOV类。这些指令把数据从源位置复制到目的位置，不做任何变化。

    • 指令效果描述
      MOV S,DD <- S传送
      movb传送字节
      movw传送字
      movl传送双字
      movq传送四字
      moabsq I,RR <- I传送绝对的四字

  • MOVZ类中的指令把目的中剩余的字节填充为0，而MOVS类中的指令通过符号扩展来填充，把源操作的最高位进行复制

    • 指令效果描述
      MOVZ S,RR <- 零扩展(S)以零扩展进行传送
      movzbw将做了零扩展的字节传送到字
      movzbl将做了零扩展的字节传送到双字
      movzwl将做了零扩展的字传送到双字
      movzbq将做了零扩展的字节传送到四字
      movzwq将做了零扩展的字传送到四字
      • 零扩展数据传送指令。这些指令以寄存器或内存地址作为源，以寄存器作为目的
    • 指令效果描述
      MOVS S,RR <- 符号扩展(S)传送符号扩展的字节
      movsbw将做了符号扩展的字节传送到字
      movsbl将做了符号扩展的字节传送到双字
      movswl将做了符号扩展的字传送到双字
      movsbq将做了符号扩展的字节传送到四字
      movswq将做了符号扩展的字传送到四字
      movslq将做了符号扩展的双字传送到四字
      cltq%rax <- 符号扩展(%eax)把%eax符号扩展到%rax

压入和弹出栈数据

  • 两个数据传送操作可以将数据压入程序栈中，以及从程序栈中弹出数据。栈指针%rsp保存着栈顶元素的地址。

    • 指令效果描述
      pushq S$R[%rsp]<-R[%rsp]-8$;
      $M[R[%rsp]]<-S$      		将四字压入栈
      popq D$D<-M[R[%rsp]]$
      $R[%rsp]<-R[%rsp]+8$      		将四字弹出栈
      • 将一个四字值压入栈中，首先要将栈指针减8，然后将值写到新的栈顶地址。
      • 弹出一个四字的操作包括从栈顶位置读出数据，然后将栈指针加8.

算术和逻辑操作

  • 指令效果描述
    leaq S,D$D <-&S$加载有效地址
    INC D$D<-D+1$加1
    DEC D$D<-D-1$减1
    NEG D$D<-D$取负
    NOT D$D<--D$取补
    ADD S,D$D<-D+S$加
    SUB S,D$D<-D-S$减
    IMUL S,D$D<-D*S$乘
    XOR S,D$D<-D \textasciicircum S$异或
    OR S,D$D<DS$
    AND S,D$D<D&S$与
    SAL k,D$D<D<<k$左移
    SHL k,D$D<D<<k$左移(等同于SAL)
    SAR k,D$D>_Ak$算术右移
    SHR k,D$D>_Lk$逻辑右移

加载有效地址

  • 将有效地址写入到目的操作数

一元和二元操作

  • 一元操作，只有一个操作数，既是源又是目的。
  • 二源操作，第二个操作数既是源又是目的。

移位操作

  • 最后一组是移位操作，先给出移位量，然后第二项给出的是要移位的数。移位量可以是一个立即数，或者放在单字节寄存器$%cl$中。（这些指令很特别，因为只允许以这个特定的寄存器作为操作数。）

特殊的算术操作

  • 两个64位有符号或无符号整数相乘得到的乘机需要128位来表示。

    • 指令效果描述
      imulq S
      mulq S      		$R[%rdx]:R[%rax]<-SR[%rax]$
      $R[%rdx]:R[%rax]<-S      R[%rax]$      		有符号全乘法
      无符号全乘法
      cqto$R[%rdx]:R[%rax]<-符号扩展(R[%rax])$转换为八字
      idivq S$R[%rax]<-R[%rdx]:R[%rax]~mod~S$
      $R[%rax]<-R[%rdx]:R[%rax]~÷~S$      		有符号除法
      divq S$R[%rdx]<-R[%rdx]:R[%rax]~mod~S$
      $R[%rax]<-R[%rdx]:R[%rax]~÷~S$      		无符号除法
      • 无符号乘法和补码乘法都要求一个参数必须在寄存器$%rax$中，而另一个作为指令的源操作数给出。然后乘积存放在寄存器$%rdx$（高64位）和%rax（低64位）中。
      • 有符号除法指令idivl将寄存器$%rdx$（高64位）和$%rax$（低64位）中的128位数作为被除数，而除数作为指令的操作数给出。

控制

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

条件码

  • CPU维护着一组单个位的条件码(condition code)寄存器，它们描述了最近的算术或逻辑操作的属性。

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

  • 条件码通常不会直接取数，常用的使用方法有三种：

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

  • 对于第一种情况，可以根据条件码的某种组合，将一个字节设置为0或者1.这一整类指令称为SET指令。

    • 指令同义名效果设置条件
      sete Dsetz$D<-ZF$相等/零
      setnesetnz$D<-ZF$不等/非零
      sets D$D<SF$负数
      setns D$D<-SF$非负数
      setg Dsetnle$D< \sim(SF ~\textasciicircum DF)&~\sim ZF$大于(有符号>)
      setge Dsetnl$D<\sim~(SF~\textasciicircum DF)$大于等于(有符号>=)
      setl Dsetnge$D<-SF~\textasciicircum DF$小于(有符号<)
      setle Dsetng$D<-(SF~\textasciicircum DF)ZE$
      seta Dsetnbe$D<\sim CF~& \sim ZF$超过(无符号>)
      setae Dsetnb$D<-\sim CF$超过或相等(无符号>=)
      setb Dsetnae$D<-CF$低于(无符号<)
      setbe Dsetna$D<-CFZF$

CMP和TEST

  • CMP指令根据两个操作数之差来设置条件码

  • TEST指令的行为与AND指令一样，除了它们只设置条件码而不改变目的寄存器的值。

    • 指令基于描述
      $CMP~~S_1,S_2$
      cmpb
      cmpw
      cmpl
      cmpq      		$S_1~~-~~S_2$比较
      比较字节
      比较字
      比较双字
      比较四字
      $TEST~~S_1,S_2$
      testb
      testw
      testl
      testq      		$S_1&S_2$测试
      测试字节
      测试字
      测试双字
      测试四字

跳转指令

  • 正常执行的情况下，指令按照它们出现的顺序一条一条地执行。跳转(jump)指令会导致执行切换到程序中的一个全新的位置。

  • 指令jmp .L1会导致程序跳过movq指令，而从popq指令开始继续执行。

  • jmp指令可以是无条件跳转。它可以是直接跳转，即跳转目标是作为指令的一部分编码地；也可以是间接跳转，即跳转目标是从寄存器内或内存位置中导出地。

    • 指令同义名跳转条件描述
      jmp Label1直接跳转
      jmp *Operand1间接跳转
      je LabeljzZF相等/零
      jne Labeljnz-ZF不相等/非零
      js LabelSF负数
      jns Label-SF非负数
      jg Labeljnle$\sim (SF~\textasciicircum OF)& \sim ZF$大于(有符号>)
      jge Labeljnl$\sim (SF~\textasciicircum OF)$大于或等于(有符号>=)
      jl Labeljnge$SF~\textasciicircum OF$小于(有符号<)
      jle Labeljng$(SF~\textasciicircum OF)ZF$
      ja Labeljnbe$\sim CF~&~\sim~ZF$超过(无符号>)
      jae Labeljnb$-CF$超过或相等(无符号>=)
      jb Labeljnae$CF$低于(无符号<)
      jbe Labeljna$CFZF$

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

  • 将条件表达式和语句从C语言翻译成机器代码，最常用的方式是结合有条件和无条件跳转。

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

  • 是心啊条件操作的传统方法是通过使用控制的条件转移。当条件满足时，程序沿着一条执行路径上执行，而当条件不满足时，就走另一条路径。这种机制简单而通用，但是在现代处理器上，它可能会非常低效。
  • 一种替代的策略是使用数据的条件转移。这种方法计算一个条件操作的两种结果，然后再根据条件是否满足从总选取一个。

条件传送指令

  • 同条件跳转不同，处理器无需预测测试的结果就可以执行条件传送。处理器只是读源值（可能是从内存中），检查条件码，然后要么更新目的寄存器，要么保持不变。

  • 指令同义名传送条件描述
    cmove S,Rcmoovz$ZF$相等/零
    cmovne S,Rcomovnz$\sim ZF$不相等/非零
    cmovs S,R$SF$负数
    cmovns S,R$\sim SF$非负数
    cmovg S,Rcmovnle$\sim~(SF~\textasciicircum OF)&\sim ZF$大于（有符号>)
    cmovge S,Rcmovnl$\sim(SF ~\textasciicircum OF)$大于或等于（有符号>=）
    cmovl S,Rcmovnge$SF~\textasciicircum OF$小于（有符号<）
    cmovle S,Rcmovng$(SF~\textasciicircum OF)ZF$
    cmova S,Rcmovnbe$\sim CF~& \sim ZF$超过（无符号>）
    cmovae S,Rcmovnb$ \sim CF$超过或相等（无符号>=）
    cmovb S,Rcoovnae$CF$低于（无符号<）
    cmovbe S,Rcmovna$CFZF$

循环

  • C语言提供了多种循环结构，即do-while、while和for。汇编中没有相应的指令存在，可以用条件测试和跳转组合起来实现循环的效果。

do-while 循环

  • 循环体至少会执行一次。

while循环

  • 第一种翻译方法，称之为跳转到中间(jump to middle)，它执行一个无条件跳转跳到循环结尾处的测试，以此来执行初始的测试。
  • 第二种翻译方法，称之为guarded-do，首先用条件分支，如果初始条件不成立就跳过循环，把代码变换为do-while循环。
  • for循环类似

switch语句

  • switch（开关）语句可以根据一个整数索引值进行多重分支（multiway branching）。

过程

  • 过程是软件中一种很重要的抽象。一种封装代码的方式，用一组指定的参数和一个可选的返回值实现了某种功能。
  • 要提供对过程的机器级支持，必须要处理许多不同的属性。为了讨论方便，假设过程P调用过程Q,Q执行后返回到P。这些动作包括下面一个或多个机制：
    • 传递控制。在进入过程Q的时候，程序计数器必须被设置车为Q的代码的起始地址，然后在返回时，要把程序计数器设置为P中调用Q后面那条指令的地址。
    • 传递数据。P必须能够向Q提供一个或多个参数，Q必须能够向P返回一个值
    • 分配和释放内存。在开始时，Q可能需要为局部变量分配空间，而在返回前，又必须释放这些存储空间。

运行时栈

  • C语言过程调用机制的一个关键特性（大多数其他语言也是如此）在于使用了栈数据结构提供的后进先出的内存管理原则。
    • x86-64的栈向低地址方向增长，而栈指针%rsp指向栈顶元素。可以用pushq和popq指令将数据存入栈中或从栈中取出。
    • 当x86-64过程需要的存储空间超出寄存器能够存放的大小时，就会在栈上分配空间。这个部分称为过程的栈帧(stack frame)。
      • 当过程P调用过程Q时，会把返回地址压入栈中，指明当Q返回时，要从P程序的哪个位置继续执行。

转移控制

  • 将控制从函数P转移到函数Q只需要简单地把程序计数器(PC)设置为Q的代码的起始位置。不过，当稍后从Q返回的时候，处理器必须记录好它需要继续P的执行的代码位置。在x86-64机器中，这个信息是用指令call Q调用过程Q来记录的。该指令会把地址A压入栈中，并将PC设置为Q的起始地址。压入的地址A被称为返回地址，是紧跟在call指令后面的那条指令的地址。对应的指令ret会从栈中弹出地址A，并把PC设置为A。

    • 指令描述
      call Label过程调用
      call *Operand*过程调用
      ret从过程调用中返回

  • call指令有一个目标，即指明被调用过程起始的指令地址。

数据传送

  • 当调用一个过程时，除了要把控制传递给它并在过程返回时再传递回来之外，过程调用还可能包括把数据作为参数传递。而从过程返回还有可能包括返回一个值。
    • 大部分过程间的数据传送是通过寄存器来实现的。
    • 如果一个函数有大于6个整型参数，超出6个的部分就要通过栈来传递。通过栈来传递参数时，所有的数据大小都向8的倍数对齐。参数到位以后，程序就可以执行call指令将控制转移到过程Q了。

栈上的局部存储

  • 局部数据必须存放在内存中，常见的情况包括：
    • 寄存器不足够存放所有的本地数据。
    • 对一个局部变量使用地址运算符'&'，因此必须能偶为它产生一个地址。
    • 某些局部变量是数组或结构，因此必须能够通过数据或结构引用被访问到。在描述数组和结构分配时，我们会讨论这个问题。

寄存器中的局部存储空间

  • 寄存器组是唯一被所有过程共享的资源。虽然在给定时刻只有一个过程是活动的，仍然必须确保当一个过程（调用者）调用另一个过程（被调用者）时，被调用者不会覆盖调用者稍后会使用的寄存器值。为此，x86-64采用了一组统一的寄存器使用惯例，所有的过程（包括程序库）都必须遵守。
    • 根据惯例，寄存器%rbx,%rbp和%r12~%r15被划分为被调用者保存寄存器。当过程P调用过程Q时，Q必须保存这些寄存器的值，保证它们的值在Q返回到P时与Q被调用时是一样的。
    • 所有其他的寄存器，除了栈指针%rsp，都分类为调用者保存寄存器，这就意味着任何函数都能修改它们。

递归过程

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

数据分配和访问

  • C语言中的数组是一种将标量数据聚集成更大数据类型的方式。

基本原则

  • 对于数据类型T和整型常数N，声明如下：$T~A[N]$
    • 起始位置表示为$x_a$。这个声明有两个效果。首先，它在内存中分配一个$L*N$字节的连续区域，这里L是数据类型T的大小(单位为字节)。

指针运算

  • C语言允许对指针进行运算，而计算出来的值会根据该指针引用的数据类型的大小进行伸缩。也就是说，如果P是一个个指向类型为T的数据的指针，P的值为x_p，那么表达式p+i的值为$x_p+L*i$，这里L是数据类型T的大小。

嵌套的数组

  • 对于一个声明如下的数组：$T D[R][C]$：它的数组元素$D[i][j]$的内存地址为：
    • $ &D[i][j]=x_p+L(C*i+j)$。这里，L是数据类型T以字节为单位的大小。

定长数组

  • C语言编译器能够优化定长多维数组上的操作代码

变长数组

  • 允许数组的维度是表达式，在数组被分配的时候才计算出来
  • 在变长数组的C版本中，可以将一个数组声明如下：
    • $int A[exp1][exp2]$
    • 它可以作为一个局部变脸，也可以作为一个函数的参数，然后再遇到这个声明的时候，通过对表达式exp1和exp2求值来确定数组的维度。
    • 当将变长数组作为函数参数时，通常会在函数的栈帧中分配内存以存储该数组的内容。

异质的数据结构

  • 结构(structure)，用关键字struct来声明，将多个对象集合到一个单位中。
  • 联合(union)，用关键字union来声明，允许用几种不同的类型来引用一个对象。

结构

  • C语言的struct声明创建一个数据类型，将可能不同类型的对象聚合到一个对象中。用名字来引用结构的各个组成部分。类似于数组的实现，结构的所有组成部分都存放在内存中一段连续的区域内，而指向结构的指针就是结构第一个字节的地址。

联合

  • 联合提供了一种方式，能够规避C语言的类型系统给，允许以多种类型来引用一个对象。联合声明的语法与结构的语法一样，只不过语义相差比较大。它们是用不同的字段来引用相同的内存块。

数据对齐

  • 许多计算机系统对基本数据类型的合法地址做出了一些限制，要求某种类型对象的地址必须是某个值K(通常是2、4或8)的倍数。这种对齐限制简化了形成处理器和内存系统之间接口的硬件设计。

在机器级程序中将控制与数据结合起来

理解指针

  • 指针是C语言的一个核心特色。它们以一种统一方式，对不同数据结构中的元素产生引用。
    • 每个指针都对应一个类型。
    • 每个指针都有一个值
    • 指针用'&'运算符创建
    • *操作符用于间接引用指针
    • 数组与指针紧密联系
    • 将指针从一种类型强制转换成另一种类型，只改变它的类型，而不改变它的值。
    • 指针也可以指向函数

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

  • C对于数组引用不进行任何边界检查，而且局部变量和状态信息（例如保存的寄存器值和返回地址）都存放在栈中。这两种情况结合到一起就能导致严重的程序错误，对越界的数组元素的写操作会破环存储在栈中的状态信息。
    • 一种特别常见的状态破环称为缓冲区溢出（buffer overflow)。通常，在栈中分配某个字符数组来保存一个字符串，但是字符串的长度超出了为数组分配的空间

对抗缓冲区溢出攻击

  1. 栈随机化
    • 为了在系统中插入攻击代码，攻击者既要插入代码，也要插入指向这段代码的指针，这个指针也是攻击字符串的一部分。
    • 栈随机化的思想使得栈的位置在程序每次允许时都有变化。
  2. 栈破坏检测
    • 计算机的第二道防线是能够检测到何时栈已经被破坏。
    • 最近的GCC版本在产生的代码中加入了一种栈保护者(stack protector)机制，来检测缓冲区越界。其思想是在栈帧中任何局部缓冲区与栈状态之间存储一个特殊的金丝雀(canary)值。这个金丝雀值，也被称为哨兵值(guard value)，是在程序每次允许时随机产生的，因此，攻击者没有简单的办法能够知道它是什么。在恢复寄存器状态和从函数返回之前，程序检查这个金丝雀值是否被该函数的某个操作或者该函数调用的某个函数的某个操作改变了。如果是的，那么程序异常中止。
  3. 限制可执行代码区域
    • 最后一招是消除攻击者向系统中插入可执行代码的能力。一种方法是限制哪些区域能够存放可执行代码。

支持变长栈帧

  • 有些函数，需要的局部存储是变长的。例如，当函数调用alloca时就会发生这种情况。alloca是一个标准库函数，可以在栈上分配任意字节数量的存储。当代码声明一个局部变长数组时，也会发生这种情况。
  • 为了管理变长栈帧，x86-64代码能够使用寄存器%rbp作为栈指针(frame pointer)(有时称为基指针(base pointer)，这也是%rbp中bp两个字母的由来)。当使用战指针时，可以看到代码必须把%rbp之前的值保存到栈中，因为它是一个被调用者保存寄存器。然后在函数的整个执行过程中，都使得%rbp指向哪个时刻栈的位置，然后用固定长度的局部变量(例如i)相对于%rbp的偏移量来引用它们。