CSAPP 程序的机器级表示

《深入理解计算机系统》第3章笔记

高级语言通过编译变成汇编语言,汇编代码则与特定的机器密切相关。汇编代码中包含了管理存储器(memory)和执行计算的低级指令的一些细节(写高级程序的人员一般不需要考虑的)。编译器基于编程语言的原则、目标机器的指令集和操作系统遵循的规则,经过一系列的阶段产生机器代码。

程序编码

正如之前所说的,从源代码到机器可执行代码会经过以下几个过程:预处理-> 编译器-> 汇编器 -> 链接器

机器级代码

对于机器级代码来说,有两种抽象非常重要。第一种是机器级程序的格式和行为,定义为指令集体系结构(Instruction set architecture, ISA),它定义了处理器状态、指令的格式,以及每条指令对状态的影响。第二种抽象是,机器级程序使用的存储器地址是虚拟地址,提供的存储器模型看上去是一个非常大的字节数组。

汇编代码和原始的C代码相差比较大,一些通常对C语言程序员隐蔽的处理器状态是可见的:

  • 程序计数器(PC,用 %eip 表示)指示将要执行的下一条指令在存储器中的地址。
  • 整数寄存器文件包含 8 个命名的位置,分别存储 32 位的值。这些寄存器可以存储地址(对应于 C 语言的指针)或证书数据。有的寄存器被用来记录某些重要的程序状态,而其他的寄存器则用来保存临时数据。
  • 条件码(codition code)寄存器保存着最近执行的算术或逻辑指令的状态信息。它们用来实现控制或数据流中的条件变化。
  • 一组浮点寄存器存放浮点数据。

C语言中的聚焦数据类型,例如数组和结构,在汇编中是用连续的字节表示的。汇编代码不区分有符号或无符号整数,不区分各种类型的指针,甚至不区分指针和整数。

程序存储器(program memory)包含:程序的可执行机器代码,操作系统需要的一些信息,用来管理过程调用和返回的运行时栈,以及用户分配的存储器块。同时OS负责管理虚拟地址空间,将虚拟地址转换为物理地址。

一条指令只执行一个非常基本的操作。例如,将存放在寄存器中的两个数字相加,在存储器和寄存器之间传送数据,或是条件分支转移到新的指令地址。编译器必须产生这些指令的序列,从而实现(像算术表达式求值、循环或过程调用和返回这样的)程序结构。

关于格式的注解

所有以 . 开头的行都是指导汇编器和链接器的命令(对程序的解释),我们通常可以忽略这些行。

数据格式

enter description here

访问信息

一个IA32的CPU中有8个32位的寄存器用来存储整数数据和指针,在过程(procedures)处理中,对前三个寄存器(%eax, %ecx, %edx)的保存和恢复惯例不同于接下来的三个寄存器(%ebx, %edi, %esi)。最后两个寄存器(%ebp, %esp)保存着指向程序栈中重要位置的指针。只有根据栈管理的标准惯例才能修改这两个寄存器中的值。

操作数指示符

大多数指令有一个或多个操作数(operand),指示出执行一个操作中要引用的源数据值,以及放置结果的目标位置。操作数可能被分为三种类型:

  • 立即数(immediate),也就是常数值
  • 寄存器(register),表示某个寄存器的内容
  • 存储器(memory)引用,它会根据计算出来的地址访问某个存储器位置

enter description here

数据传送指令

enter description here

算术和逻辑操作

给出的每个指令类都有对字节、字和双字数据进行操作的指令。这些操作被分为四组:加载有效地址、一元操作、二元操作和移位。

加载有效地址

加载有效地址(load effective address)指令 leal 实际上是 movl 指令的变形。它的指令形式是从存储器读数据到寄存器,但实际上它根本就没有引用存储器。它的第一个操作数看上去是一个存储器引用,但该指令并不是从指定的位置读入数据,而是将有效地址写入到目的操作数。

enter description here

一元和二元操作

一元操作:一个操作数既是源又是目的

二元操作:第二个操作数既是源又是目的

移位操作

先给出移位的量,然后是待移位的值

控制

条件码

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

enter description here

enter description here

访问条件码

两种最常见的访问条件码的方法不是直接读取,常用的使用方法有三种:

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

enter description here

跳转指令和他们的编码

跳转指令会导致执行切换到程序中的一个全新的位置

enter description here

翻译条件分支

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

enter description here

循环

汇编中没有相应的循环指令,将条件测试和跳转组合起来可以实现循环的效果

enter description here

switch语句

通过一种称为跳转表(jump table)的数据结构使得实现更加高效,相比使用一组很长的if-else语句,使用跳转表的优点是执行开关语句的时间和开关情况(switch cases)的数量无关。

一般在开关情况数量比较多,并且值的范围跨度比较小的时候使用跳转表

过程

一个过程调用包括将数据和控制从代码的一部分传递到另一部分。另外,它还必须在进入时为过程的局部变量分配空间,并在退出时释放这些空间。大多数机器,包括 IA32,只提供转移控制到过程和从过程转移出控制这种简单的指令。数据传递、局部变量的分配和释放通过操纵程序栈来实现。

栈帧结构

IA32 程序用程序栈来支持过程调用。机器用栈来传递过程参数、存储返回信息、保存寄存器用于以后回复,以及本地存储。为单个过程分配的那部分栈称为栈帧(stack frame)。

enter description here

转移控制

enter description here

寄存器使用惯例

程序寄存器组是唯一能够被所有过程共享的资源。虽然在给定时刻只能有一个过程是活动的,但是我们必须保证当一个过程调用另一个过程时,被调用者不会覆盖某个调用者稍后会使用的寄存器的值。

根据惯例,寄存器 %eax、%edx、%ecx 被划分为调用者保存寄存器(caller save)。当过程 P 调用 Q 时,Q 可以覆盖这些寄存器,而不会破坏任何 P 所需要的数据。另一方面, 寄存器 %ebx、%esi、%edi 被划分为被调用者保存寄存器(callee save)。

数组的分配和访问

C 语言一个不同寻常的特点是可以产生指向数组中元素的指针,并对这些指针进行运算。在机器代码中,这些指针会被翻译成地址计算。

优化编译器非常善于简化数组索引所使用的地址计算。不过这使得 C 代码和它机器代码的翻译之间的对应关系有些难以理解。

指针运算

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

数组与循环

在循环代码中,对数组的引用通常有非常规则的模式,优化编译器会使用这些模式

嵌套数组

int A[5][3];

等价于下面的声明

typedef int row3_t[3];
row3_t A[5];

固定大小的数组

动态分配的数组

异类的数据结构

结构(structure)

将可能不同类型的对象聚合到一个对象中。结构的各个组成部分用名字来引用。类似于数组的实现,结构的所有组成部分都存放在存储器中一段连续的区域内,而指向结构的指针就是结构第一个字节的地址。编译器维护关于每个结构类型的信息,指示每个字段(field)的字节偏移。它以这些偏移作为存储器引用指令中的位移,从而产生对结构元素的引用。

联合(union)

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

对齐(alignment)

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

综合:理解指针

指针是 C 语言的一个重要特征。它们以一种统一方式,对不同数据结构中的元素产生引用。这里介绍一些指针和它们映射到机器代码的关键原则:

  • 每个指针都对应一个类型。这个类型表明指针指向哪一类对象。
  • 每个指针都有一个值。这个值是某个指定类型对象的地址。特殊的 NULL(0) 值表示该指针没有指向任何地方
  • 指针用 & 运算符创建。这个运算符可以应用到任何 lvalue 类的 C 表达式上。
  • 操作符用于指针的间接引用。其结果是一个值,它的类型与该指针的类型相关。间接引用是通过存储器引用来实现的,要么是存储到一个指定的地址,要么是从指定的地址读取。
  • 数组与指针紧密联系。一个数组的名字可以像一个指针变量一样引用(但是不能修改)。数组引用与指针运算和间接引用有一样的效果。数组引用和指针运算都需要用对象大小对偏移量进行伸缩。
  • 将指针从一种类型强制转换成另一种类型,只改变它的类型,而不改变它的值。强制类型转换的一个效果是改变指针运算的伸缩。来看一个例子,如果 p 是一个 char* 类型的指针,那么表达式(int)p+7 计算为 p+28, 而(int)(p+7)计算为 p+7。
  • 指针也可以指向函数。这提供了一个很强大的存储和向代码传递引用的功能,这些引用可以被程序的某个其他部分调用。

存储器的越界引用和缓冲区溢出

C 对于数组引用不进行任何边界检查,而局部变量和状态信息,都存放在栈中。这两种情况结合到一起就可能导致严重的程序错误,对越界的数组元素的写操作会破坏存储在栈中的状态信息。当程序使用这个被破坏的状态,试图重新加载寄存器或执行 ret 指令时,就会出现很严重的错误。

缓冲区溢出的一个更加致命的使用就是让程序执行它本来不愿意执行的函数。这是一种最常见的通过计算机网络攻击系统安全的方法。通常,输入和程序一个字符串,这个字符串包含一些可执行代码的字节编码,称为攻击代码(exploit code),另外还有一些字节会用一个指向攻击代码的指针覆盖返回地址。那么执行 ret 指令的效果就是跳转到攻击代码。

一种攻击形式,攻击代码会使用系统调用启动一个外壳程序,给攻击者提供一组操作系统函数。另一种攻击形式是,攻击代码会执行一些未授权的任务,修复对栈的破坏,然后第二次执行 ret 指令,(表面上)正常返回给调用者。

小结

机器级程序和它们的汇编代码表示,与 C 程序的差别很大。在汇编语言程序中,各种数据类型之间的差别很小。程序是以指令序列来表示的,每条指令都完成一个单独的操作。部分程序状态,如寄存器和运行时栈,对程序员来说是直接可见的。

C 语言中缺乏边界检查,使得许多程序容易出现缓冲区溢出。虽然最近的运行时系统提供了安全保护,而且编译器帮助使得程序更加安全,但是这已经使许多系统容易收到入侵者的恶意攻击。