CSAPP笔记&实验

本章属于第一部分:程序的结构和执行. 包括:

• 基础 Basics

• 控制 Control

• 过程 Procedures

• 数据 Data

程序的机器级表示就是机器代码. 在本章中我们会近距离地观察机器代码, 以及人类可读的表示–汇编代码.
能够阅读并理解汇编代码对了解系统底层是很有帮助的.

我们将 :
1. 游览C语言、汇编代码以及机器代码的关系.
2. 介绍x86-64的细节, 从数据的表示和处理以及控制的实现开始.
3. 了解C中控制结构的实现, 如if、while和switch语句
4. 过程的实现, 过程间数据和控制的传递、局部变量的存储
5. 机器级如何实现数组、结构和联合这样的数据结构
6. 内存越界以及传冲区溢出攻击的问题

Basics

3.1 历史观点

Intel处理器系列也称x86, 经历了一个长期的、不断发展的过程.

本书采用的是x86-64 Linux.

3.2 程序编码

3.2.1 机器级代码

两个重要抽象

指令集架构(Instructrue Set Architecture ISA), 定义了处理器的状态、指令格式以及每条指令对状态的影响.
比如之后学到的mov等指令, 它是软硬件之间的”合同”.

虚拟地址, 即机器级程序同样把内存看作是一个一维的字节数组.

机器级可见状态

x86-64(本书使用)的机器代码和原始C代码差别很大, 一些通常对C程序员透明的处理器状态都是可见的.

• 程序计数器(PC, %rip), 给出将要执行的下一条指令在内存中的地址.
• 整数寄存器文件, 包含16个命名位置, 存储64位值. 可以存储整数数据/地址.
• 条件码寄存器, 保存最近执行的算数或逻辑指令的状态信息. 用来实现控制或条件.
• 向量寄存器, 存放一个或多个整数/浮点数值.

C提供一种模型可以在内存中声明和分配各种数据类型的对象, 但机器代码只是简单的将内存看作一个按
字节寻址的数组, C中所有数据和操作不作区分, 都表示为字节序列.

3.2.2 代码示例

C代码

gcc -Og -o prog main.c mstore.c

gcc, gcc编译器, linux默认编译器
-Og, 告诉编译器生成符合原始C整体结构的机器代码. -O(Optimize)是优化选项
-o prog 生成可执行文件, 文件名prog

C与汇编代码

我们以mstore.c为例观察C与汇编代码的关系.

gcc -Og -S mstore.c

生成mstore.c对应汇编文件mstore.s. -S编译选项告诉编译器GCC产生汇编文件.
我们可以用编辑器打开汇编文件.

pushq %rbx 用来把寄存器rbx内容压栈保存. 为什么首先要保存rbx内容呢?

为此我们先简单了解x86的16个整数寄存器文件.

接着我们来了解两个概念, 调用者保存寄存器/被调用者保存寄存器(Caller-saved/Callee-saved Register)

以上图为例, 函数A调用函数B, 所以A被称为调用者Caller, B称为被调用者Callee. 这里B中修改了
%rbx, 而逻辑上%rbx在调用B前后对A应该保持一致.为此有两个策略

• Caller-saved 在调用者A调用B之前保存rbx内容, 调用后恢复rbx
  

• Callee-saved 被调用着B在执行其动作前保存rbx, 在返回前恢复rbx
  

对于具体使用哪种策略, 不同的寄存器被定义为不同策略.

这里rbx被定义为被调用者保存, 汇编代码首尾语句用来实现该策略, 用程序栈的push/pop实现.

mov指令用来把rdx内容传送到rbx, q用来表示传送数据大小. rdx默认保存函数第三个参数即dest的内容, 之后我们还会对寄存器默认功能有更多讨论.

我们会看到许多指令后缀都指明了操作数的大小, 具体如图

call指令用来函数调用, 并把返回值放入%rax中.

目标代码

gcc -Og -c mstore.c

上述指令生成mstore.c的对应目标文件代码mstore.o, 由于是二进制格式, 无法直接查看.

要查看机器代码内容, 反汇编器(disassembler)程序非常有用. 这些程序根据机器代码生成类似汇编代码
的格式. 在Linux中我们可以使用objdump工具

objdump -d mstore.o

我们可以查看mstore.o的相关信息

通过对比可以发现通过反汇编得到的代码与编译器直接得到的代码有着细微差别.

3.2.3 关于格式的注解

如果你使用上面生成mstore.s的指令会发现出了图中给出的代码还有额外的以.开头的行, 这些是
指导汇编器和连接器的伪指令.
为了清楚说明汇编代码, 本书忽略大多数伪指令, 但包括额外的行号和解释性说明.

3.4 访问信息

寄存器 Integer Register

一个x86-64的CPU包含一组16个存储64位值的通用寄存器, 用来存储整数/指针. 它们的名字
都以%r开头,由于指令集历史演化的原因, 我们还可以使用其中8个寄存器的低32位和低16位.
在一般程序中, 不同寄存器扮演不同角色. 相应编程规范规定了如何使用这些寄存器.

了解这些寄存器在程序中的角色能帮助我们理解汇编代码.

向寄存器复制/生成小于8字节的规则

• 1、2字节保持剩余不变
• 4字节会把高4位置为0

3.4.1 操作数指示符

大多数指令包含两部分–操作码和操作数. 操作码决定CPU操作类型, 大多指令由一个或多个操作数.

操作数

操作数指示出一个执行一个操作要用到的源数据值以及防止结果的位置. 可分为三种类型

• 立即数(immediate), 用来表示常数值. 在AT&T格式中以$开头加上一个标准C表示法表示的整数.

• 寄存器(register), 寄存器内容. 在64位机器中也能用8位、16位以及32位的寄存器作为操作数.

• 内存引用(memory reference) 根据计算出来的地址(有效地址)访问某个内存位置. 我们用$M_b$[$Addr$]
  对内存中从地址$Addr$开始的$b$个字节的引用.

寻址模式

图中是通用寻址形式, 常见于访问数组. 比例因子s必须是1, 2, 4, 8, 对应不同基本数据类型的字节数.

其他寻址模式都是通用形式的特殊情况, 只是忽略了某些部分.

3.4.2 数据传送指令 Move Data

最频繁使用的指令是将数据从一个位置复制到另一个位置的指令. 在我们的讲述中, 把许多不同的指令
划分成指令类. 每一类中的指令执行相同操作, 只不过数据数大小不同.

mov类

最简单的数据传送指令是mov类, 指令把数据从源位置复制到目的位置, 不做任何变化.

mov指令有两个操作数, 源操作数和目的操作数.

mov指令源和目的只有5种可能的组合. 因为立即数不能作为目的操作数. 且x86-64限制mov指令的
两个操作数不能都指向内存位置, 需要用寄存器作为中介.

mov指令中立即数默认只能是32位补码表示, 然后对数值符号位扩展后传送到目的位置.
movabsq指令能够以任意64位立即数作为源操作数, 此时只能以寄存器作为目的数.

mov指令寄存器操作数的大小必须与mov指令最后一个字符指定大小匹配.

在将较小的源值复制到较大的目的时, 需要使用movz类零扩展/movs类符号扩展, 并用最后两个字符
表示源值和目的值的字节大小. 如movzbw, 将做了零扩展的字传送到双字; movslq将做了符号扩展
的双字传送到4字.

这里符号扩展比零扩展多了movsql, 即从双字到四字, 因为这可以用movl实现(x86-64的规定, 任何为
寄存器生成32位值的指令都会把该寄存器高位置为0).

3.4.3 数据传送示例

我们重点来看一下exchange的汇编指令.

根据寄存器使用管理, 函数的参数分别存储在%rdi, %rsi; 返回值存储在%rax.

1. 第一条mov指令从内存取出地址在%rdi的值存入%rax中, 作为最后的返回值.
2. 第二条mov指令将%rsi内容存入内存中, %rsi存储y的值, 内存地址存储在rdi中也就是xp指向的地址.
3. 返回指令

从例子中我们可以看出C中的指针就是地址, 间接引用指针实际上就是从内存中引用指针存储的地址.

3.4.4 压入和弹出栈数据

最后两个数据传送操作可以将数据压入程序栈中.

程序栈

栈是按后进先出原则的数据结构, 程序栈本质上是内存中一段区域, 在第一章中我们提到过程序运行时内存分布.

图中的User Stack即我们说的程序栈.

这里的程序栈要注意两点

• 栈顶指向的是最近加入且在栈中的数据项.
• 栈的增长方向是从高地址向低地址增长, 也就是随着栈的增大, 栈顶地址减小.

push/pop

push/pop本质上就是将数据按栈的规则传送至内存/寄存器中. 图中给出与push/pop等价的两条指令.

结合我们用数组模拟栈的操作应该很好理解.

3.5 算术和逻辑操作

3.5.1 加载有效地址 (load effective address, leaq)

q表示8个字, 由于在64位处理器上地址64位, 所以不存在其他有关大小的变种形式.
指令leaq实际上是movq指令的变形. 指令形式从内存读取数据到寄存器, 但并没有引用内存.

例如上图指令是将有效地址复制到%rax中. 有效地址的计算方式与之间提到的内存地址的计算方式一致.
这里leaq指令并没有从内存地址5x+7处读取数据, 而是将有效地址5x+7这个值写入到目的寄存器rax.

此外leaq指令还用于普通的算数指令.

我们来观察leaq指令是如何实现算数指令的.

注意这里12*z是分两步(3 = 2 + 1) * 4实现的. 我们不直接乘以12是因为s只能取1, 2, 4, 8.

3.5.2 一元和二元操作数

一元操作指令 Unary Operations

这类指令只有一个操作数, 因此它既是源操作数又是目的操作数. 操作数可以是寄存器/内存地址.

类似于C中的++/--.

二元操作指令 Binary Operations

这类指令有两个操作数, 第一个操作数是源操作数, 第二个操作数既是源操作数又是目的操作数, 不能是立即数.

类似与C中的+=/*=等, 当第二个操作数是内存地址时, 处理器必须从内存中读出值, 执行操作, 再把结果
写回内存.

3.5.3 移位操作

两种移位操作

移位操作先给出移位量, 再给出要移位的数. 就像第二章提到的, 移位分为算数/逻辑移位.

移位量

移位量可以是一个立即数, 也可以是放在单字节寄存器%cl中的数. 注意这里只允许特定的寄存器cl.

寄存器cl为单字节, 原则上移位量0~255. 实际上, 对于w位长的数据进行移位操作, 移位量是由
%cl的低m位决定的($2^m = w$), 这也对应第二章对w位字长移位k实际移位值为$k$%$w$.

示例

可以看到对于大多数算数和逻辑指令, 除逻辑/算数右移, 指令没有区分无符号/补码数. 这个特性使得
补码运算成为实现有符号整数运算的一种比较好的方法的原因之一.

下面举一个移位运算的例子.

我们重点看一下z*48对应的汇编指令.

观察到编译器用leaq和左移指令实现z*48. 这么做的原因是乘法指令比较耗时.

3.5.5

一些支持产生两个64位数字的全128位乘积以及整数除法的特殊指令.

对于汇编指令的学习, 更重要的是掌握基本概念, 一些特殊的指令可以随时搜索.

Control

3.6 控制

通常, C中的语句和机器代码的指令都是按照它们在程序中出现的次序, 顺序执行的.
C中有一类之类需要满足条件才能执行, 例如条件语句、循环语句等, 它们需要根据数据测试的结果
来决定操作的顺序.

这一节我们会先涉及实现条件操作的两种方式, 然后描述表达循环语句和$switch$语句的方法.

3.6.1 条件码 condition code

之前我们提到的算数/逻辑指令(除leap)除了计算结果外还会根据运算的结果设置条件码寄存器.

条件码是由CPU来维护的, 长度是单个比特位, 它描述了最近执行操作的属性.

例如ALU执行两条连续算数指令. t1时刻执行指令1, t2时刻执行指令2. t1时刻指令1执行后条件码
寄存器中保存的是指令1的执行结果的属性, t2时刻执行指令2后条件码寄存器内容会被指令2结果
的属性所覆盖.

条件码寄存器

下面介绍几个常用的条件码寄存器.

• CF(Carry), 进位标志, 当最近一条指令最高位产生进位时置1, 可以用来检查无符号数的溢出.

• ZF(Zero), 零标志, 当最近操作的结果等于零时置1.

• SF(Sign), 符号标志, 当最近操作的结果小于0时置1.

• OF(Overflow), 溢出标志, 针对有符号数, 最近操作导致正/负溢出时置1.

条件码寄存器的值是由ALU在执行算数/逻辑运算指令时写入的.

图中的算数/逻辑运算指令都会改变条件码寄存器的内容.
对于不同的指令定义了相应的规则来设置条件码寄存器.

CMP和TEST指令

这两类指令只设置条件码寄存器而不改变任何其他寄存器.

cmp指令根据两个数的差设置条件码. 与sub指令类似.
区别在于cmp指令只会设置条件码寄存器, 不会更新目的寄存器.
sub :

cmp :

test指令和and指令类似, 区别同样是不会改变目的寄存器的内容.

条件码的使用1

首先以判断两个数是否相等的函数为例.

cmp指令根据a-b的结果设置条件码寄存器, 若结果为0, cmp会将零标志ZF设置为1.

接下来的set指令可能会让我们费解了.

3.6.2 访问条件码

set

条件码通常不会直接读取, 一种方法是根据条件码的某种组合, 通过set类指令, 将一个字节设置为0/1.
在上面的例子中, sete根据零标志ZF的值对寄存器al赋值, e是equal的缩写.

最后mov指令对寄存器al进行零扩展, 最后返回判断结果.

条件码使用2

判断是否满足小于.

对比相等情况, 可以发现set类从sete变为setl. 指令setl的含义是如果a小于b, 将寄存器al设为1.
其中后缀l是less的缩写, 而不是表示字节大小long word.

判断a < b的情况相对复杂, 我们需要SF ^ OF的结果(这里类似于datalab中的内容).

• 不溢出, 若a - b < 0, 符号位为1, 溢出位为0; 否则符号位为0, 溢出位为0.
• 溢出, 负溢出(a < 0, b > 0)时 a - b > 0, 符号位为0, 溢出位为1; 正溢出时符号位为1, 溢出位为1.

对于其他判断情况, 可以通过不同条件码的组合实现.

无符号数设置进位标志CF而不是溢出标志OF.

3.6.3 跳转指令

跳转(jmp)指令会导致执行切换到程序中的一个全新位置, 跳转的目的地通常用一个标号(label)指明.

表中除了jmp无条件跳转, 其他跳转指令都是有条件的–根据条件码某种组合, 1时跳转, 否则继续
执行代码序列的下一条指令.

无条件跳转可以是直接跳转, 跳转目标作为指令的一部分编码, .L表示;
也可以是间接跳转, 跳转目标从寄存器或内存位置中读出, '*'加上一个操作数指示符表示. 对于其他
跳转只有直接跳转.

其命名后缀和跳转条件与set类指令匹配.

3.6.5 用条件控制实现条件分支 Condition Control

将条件表达式从C翻译为汇编代码, 最常用的方式是结合有条件和无条件跳转, 有条件跳转和无条件跳转组合
保证只会执行一个分支.

这里以计算两个数差的绝对值的函数为例.

为更好理解汇编代码结构, 可以用C提供的goto语句描述汇编代码程序控制流的C程序.

通过上面的例子, 我们可以把C中if-else的通用形式用条件分支与无条件分支实现.

    if( test-expr )             t = test-expr
        then-statement          if( !t )
    else                ===>        goto false;
        else-statement          then-statement;
    ....                        goto done;
                            false :
                                else-statement
                                done :
                                ....

3.6.6 用条件数据传送来实现条件分支

上面通过使用 控制 的条件转移实现条件操作是传统的方法, 条件满足时程序沿着一条指令路径执行, 否则
就走另一条路径执行(if-else). 这种机制简单通用, 但在现代处理器上可能会非常低效.

一种替代的策略是使用 数据 的条件转移, 这种方法计算一个条件操作的两种结果, 然后根据条件是否满足
从中选取一个. 这种策略只有在一些受限制条件下可行, 但若可行可以用一条简单的 条件传送 指令实现.

这里同样以计算两个参数差的绝对值的函数为例.

可以看到我们既计算了y-x的值又计算了x-y的值, 然后通过测试结果判断是否更新返回值.

观察使用使用 数据 的条件转移对应的汇编代码.

其中cmovege指令实现了 数据 的条件转移. 指令cmov是根据条件码的某种组合来进行有条件
的传送数据. 只有满足对应条件时才会进行数据传送. 例如本例中

只有满足x>=y时才会执行这条指令.

条件传送指令的命名后缀和跳转条件与set/jmp类指令匹配. 目的数必须是寄存器, 汇编器可以
通过目标寄存器的名字推断条件传送指令的操作数长度, 所以这里不用指出字节大小.

为什么条件数据传送传送效率更高

为了理解原因我们需要了解一些关于现代处理器如何运行的知识. 现代处理器通过流水线(pipelining)
来获得高性能. 这需要事先确定要执行的指令序列, 这样才能保持流水线中充满待执行的指令. 当遇到
跳转指令时, 处理器会根据分支预测器来猜测每条跳转指令是否执行. 当发生错误预测时, 会浪费大量
时间, 导致程序性能严重下降. 同条件跳转不同, 处理器无需预测测试结果就可以执行条件数据传送.

条件数据传送不能使用的情况

条件传送指令会对then-expr和else-expr都求值. 而两个表达式可能不可同时求值/表达式会对程序其他
状态产生影响, 就会导致程序错误. 或者两个表达式本身都很耗时, 可能多余的计算耗时相比分支预测
错误造成的性能处罚还要大.

图中分别给出了计算耗时、表达式可能不可同时求值和表达式会对程序状态产生影响的示例.

所以, 条件数据传送提供了一种实现条件策略的替代策略, 只能用于非常受限制的情况.

3.6.7 循环

C语言提供了多种循环结构 : do-while、while和for. 汇编语言中没有相应的指令存在, 可以用条件测试
和跳转组合起来实现循环效果.
下面我们以计算参数二进制形式中1的个数的pcount函数为例介绍三种循环的汇编形式.

do-while

下面分别是C语言do-while与其goto形式.

我们进一步观察函数goto形式与汇编代码.

do-while是由jne指令判断x是否不为0, 若不为0则跳转至标签.L2处, 实现循环操作.

这里我们可以得到do-while的一般形式.

while

while与do-while类似, 区别在于需要先判断条件是否满足, 再执行程序体语句. while一般有两种
实现形式.
第一种形式 : 先无条件跳转至test来执行初始测试, 再由条件判断是跳转至其上面的循环程序体
或向下执行退出循环.

对应的C的goto形式实现

第二种形式 : 通过初始的一个test将while转变为do-while, 即while是在do-while基础上多了第一次的判断.

对应的C的goto形式实现

for

for循环的通用形式如下

把for的不同部分按while形式转化为等价的while语句

for转化为等价while形式实现的pcount函数

for同样可以转化为do-while形式, 这里经过优化后编译器会判断初始条件是否满足, 若满足则可以
直接丢掉初始测试的部分.

3.6.8 switch 语句

switch(开关)语句可以根据一个整数索引值进行多重分支(multiway branching), 运行整数对应的
case代码块, 在处理具有多种可能结构的测试时非常有用. switch通过跳转表(jump table), 一个
代码段地址数组, 对应case代码块程序;索引值用来执行对跳转表内数组的引用,使得这种结构相比
一长串if-else更加高效.

示例

例子中switch语句做了一些乱糟糟的算数运算, 仅作为一个例子使用. 例子有些有意思的特征

• 代码块有多个标号(5,6)

• 代码块落入其他代码块(2->3)

• 缺失的标号(4)

跳转表

跳转表是一个数组结构, 每个表项对应每个代码段的入口地址.

示例汇编代码

程序首先与6比较, 这里巧妙的用到了ja命令, 将数值作为无符号数, 这样做的好处是对于补码<0的数
解释为很大的数. 如果大于6则超出[0,6]的范围, 跳转至default.

这里gcc做了优化, 因为后续case程序块没有用到w的初始值, 所以一开始没有对w赋初始值.

如果在[0,6]范围内, switch的关键指令jmp, 操作数有前缀*, 表明这是一个间接跳转, 对应索引值
x保存在%rdi中, 则跳转地址为 .L4 + x * 8.

跳转表项对应case项顺序, 缺失的数值作为defalut项.

索引值为1时, 执行代码块后直接ret退出, 使用ret退出的原因是switch退出后统一ret.

代码块落入其他代码块(2->3)的goto形式, 这里由于switch没有对w赋初值, 所以形式没那么直观,
对于case 3的情况因为用到了w的值, 所以要把赋值步骤补上, 而对于case 2不需要对w赋值.

观察对应汇编代码我们可以知道, 对于落入后续程序块的情况就是继续向对于程序块执行而不是退出case项.

代码块有多个标号(5,6) : 具有同样标号; 缺失的标号(4) : 进入default程序块.

逆向工程

理解产生的汇编代码与原始代码之间的关系, 关键是找到程序值和寄存器之间的映射关系. 有时编译器
会加入不存在的新值, 有时会将多个程序值映射到一个寄存器以最小化寄存器利用率, 有时编译器会做
一些画蛇添足的蠢事. 我们需要对每个步骤如何更新和测试寄存器找出线索, 解开谜团.