计算机系统基础复习提纲 - 第二部分
- Machine-Level Programming I: Basics
- Machine-Level Programming II: Control
- Machine-Level Programming III: Procedures
- Machine-Level Programming IV: Data
- Machine-Level Programming V: Advanced Topics
Machine-Level Programming I: Basics
-Og
选项告诉编译器使用会生成符合原始 C
代码整体结构的机器代码的优化等级。
由指令集体系结构或指令集架构 (ISA) 来定义机器级程序的格式和行为,它定义了处理器状态、指令的格式,以及每条指令对状态的影响。大多数 ISA,包括 x86-64,将程序的行为描述成好像每条指令都是按顺序执行的,一条指令结束后,下一条再开始。
机器级程序使用的内存地址是虚拟地址,提供的内存模型看上去是一个非常大的字节数组。
汇编代码表示非常接近于机器代码,与机器代码的二进制格式相比,汇编代码的主要特点是用文本格式表示。
- 程序计数器(通常称为“PC”,在 x86-64
中用
%rip
表示)给出将要执行的下一条指令在内存中的地址。 - 整数寄存器文件包含 16 个命名的位置,分别存储 64 位的值。这些寄存器可以存储地址(对应于 C 语言的指针)或整数数据。有的寄存器被用来记录某些重要的程序状态,而其他的寄存器用来保存临时数据,例如过程的参数和局部变量,以及函数的返回值。
- 条件码寄存器保存着最近执行的算术或逻辑指令的状态信息。它们用来实现控制或数据流中的条件变化。
- 一组向量寄存器可以存放一个或多个整数或浮点数值。
gcc-S
选项生成汇编文件,-c
生成目标文件。
当这些指令以寄存器作为目标时,对于生成小于 8 字节结果的指令,寄存器中剩下的字节会怎么样,对此有两条规则:生成 1 字节和 2 字节数字的指令会保持剩下的字节不变;生成 4 字节数字的指令会把高位 4 个字节置为 0。
源操作数可以是立即数/寄存器/内存,目的操作数可以是寄存器/内存。传送指令的两个操作数不能都指向内存位置。
常规的movq
指令只能以表示为 32
位补码数字的立即数作为源操作数,然后把这个值符号扩展得到 64
位的值,放到目的位置。movabsq
指令能够以任意 64
位立即数值作为源操作数,并且只能以寄存器作为目的。
逻辑上应该被命名为movzlq
的指令可以用movl
实现。
cltq
指令没有操作数,它总是以寄存器%eax
作为源,%rax
作为符号扩展结果的目的。
汇编指令纠错:
- 寄存器和指令后缀不匹配/两个寄存器大小不一样
- 两个参数都是内存地址
- 用非 64 位的寄存器作内存地址
- 寄存器不存在
- 立即数作为目的
一个值从一个内存位置移到另一个内存位置,如果涉及到类型转换:
- 从小类型转移到大类型,先进行类型转换(注意类型有无符号)移到寄存器,再移到目的地址。
- 从大类型转移到小类型,先按原来的大小移到寄存器,再截取寄存器的低位移到目的地址。
栈顶元素是所有栈中元素地址中最低的。地址向栈底依次增大。
加载有效地址指令leaq
实际上是movq
指令的变形。它的指令形式是从内存读数据到寄存器,但实际上它根本就没有引用内存。它的第一个操作数看上去是一个内存引用,但该指令并不是从指定的位置读入数据,而是将有效地址写入到目的操作数。leaq
的目的操作数必须是一个寄存器。
一元操作的操作数可以是寄存器/内存。二元操作的源操作数可以是立即数/寄存器/内存,目的操作数可以是寄存器/内存。
移位操作的\(k\)可以是一个立即数,或者放在单字节寄存器%cl
中。x86-64
中,移位操作对\(w\)位长的数据值进行操作,移位量是由%cl
寄存器的低\(m\)位决定的,这里\(2^m=w\)。高位会被忽略。
xorq %rdx,%rdx
把寄存器清零。
上图中
idivq
和divq
的第二行为 R[%rax
]\(\leftarrow\)R[%rdx
]: R[%rax
]\(\div\)S。
clto
改为cqto
。
x86-64 指令集还提供了两条不同的“单操作数”乘法指令,以计算两个 64
位值的全 128 位乘积一一一个是无符号数乘法
(mulq
),而另一个是补码乘法
(imulq
)。这两条指令都要求一个参数必须在寄存器%rax
,而另一个作为指令的源操作数给出。然后乘积存放在寄存器%rdx
(高
64 位)和%rax
(低 64 位)中。
有符号除法指令idivl
将寄存器%rdx
(高 64
位)和%rax
(低 64 位)中的 128
位数作为被除数,而除数作为指令的操作数给出。指令将商存储在寄存器%rax
中,将余数存储在寄存器%rdx
中。
对于大多数 64 位除法应用来说,除数也常常是一个 64
位的值。这个值应该存放在%rax
中,%rdx
的位应该设置为全
0(无符号运算)或者%rax
的符号位(有符号运算)。后面这个操作可以用指令clto
来完成。这条指令不需要操作数一一它隐含读出%rax
的符号位,并将它复制到%rdx
的所有位。
练习题:3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10
Machine-Level Programming II: Control
条件码:
CF
:进位标志。最近的操作使最高位产生了进位。可用来检查无符号操作的溢出ZF
:零标志。最近的操作得出的结果为 0。SF
:符号标志。最近的操作得到的结果为负数。OF
:溢出标志。最近的操作导致一个补码溢出一一正溢出或负溢出。
在算CF
的时候,当做无符号数的计算;在算OF
的时候,当做有符号数的计算。
发生最高位的进位或借位时,CF
都为
1。
leaq
不改变条件码。
TEST
的典型用法:两个操作数是一样的,用来检查是整数、负数还是零;其中一个操作数是掩码,用来指示哪些位应该被测试。
一条SET
指令的目的操作数是低位单字节寄存器元素之ー,或是一个字节的内存位置,指令会将这个字节设置成
0 或者 1。为了得到一个 32 位或 64 位结果,我们必须对高位清零。
b
——char
unsigned char
w
——short
unsigned short
l
——int
unsigned int
q
——long
unsigned long
void *
(无符号)
jmp
指令是无条件跳转。它可以是直接跳转,即跳转目标是作为指令的一部分编码的;也可以是间接跳转,即跳转目标是从寄存器或内存位置中读出的。
条件跳转只能是直接跳转。
跳转指令有几种不同的编码,但是最常用都是 PC 相对的。也就是,它们会将目标指令的地址与紧跟在跳转指令后面那条指令的地址之间的差作为编码。这些地址偏移量可以编码为 1、2 或 4 个字节。第二种编码方法是给出“绝对”地址,用 4 个字节直接指定目标。
if-else
:
跳转指令的条件取反是if
的条件。
源是寄存器/内存,目的只能是寄存器。不支持单字节传送。
对于所有的操作数长度,都使用同一个的指令名字。
基于条件控制转移:
基于条件传送:
条件传送指令的条件取反是if
的条件。
条件传送不可用的情况:
- 计算花费很大
- 可能出现不安全的访问
- 有副作用
do-while
:
while
:
jump to middle/跳转到中间(先跳转到最后执行一遍判断):
guarded-do(首先判断初始条件,如果不成立就跳过循环,之后变成do-while
):
(通常会优化初始测试)
for:
switch
:
跳转表是一个数组,表项\(i\)是一个代码段的地址,这个代码段实现当开关索引值等于\(i\)是程序应该采取的动作。程序代码用开关索引值来执行一个跳转表内的数组引用,确定跳转指令的目标。当开关情况数量比较多,并且值的范围跨度比较小时,就会使用跳转表。
首先把\(n\)的取值范围移到从\(0\)开始,补码表示的负数会被映射成大整数,之后用\(index\)是否大于 (above) 上界来判断是否在范围之外。对于重复的情况,使用同一个标号;对于缺失的情况,使用默认情况的标号。
使用jmp
指令的间接跳转,每个地址 8 个字节。
switch
的汇编中要注意的点:
- 默认的情况
- 偏移
- 重复的情况
- fall through 的情况
- 缺失的情况
练习题:3.13 3.14 3.15 3.18 3.20 3.21 3.23 3.26 3.28 3.31
Machine-Level Programming III: Procedures
栈帧:
call Q
指令会把地址 A 压入栈中,并将 PC 设置为 Q
的起始地址。压入的地址 A
被称为返回地址,是紧跟在call
指令后面的那条指令的地址。对应的指令ret
会从栈中弹出地址
A,并把 PC 设置为 A。
同跳转一样,调用可以直接的,也可以是间接的。在汇编代码中,直接调用的目标是一个标号,而间接调用的目标是、*后面跟一个操作数指示符。
如果有超出 6 个参数,要把参数\(1\sim 6\)复制到对应的寄存器,把参数\(7\sim n\)放到栈上,而参数 7 位于栈顶。通过栈传递参数时,所有的数据大小都向 8 的倍数对齐。
有些时候,局部数据必须存放在内存中,常见的情况包括:
- 寄存器不足够存放所有的本地数据。
- 对一个局部变量使用地址运算符'&',因此必须能够为它产生一个地址。
- 某些局部变量是数组或结构,因此必须能够通过数组或结构引用被访问到
一般来说,过程通过减小栈指针在栈上分配空间。分配的结果作为栈帧的一部分,标号为“局部变量”。
根据惯例,寄存器%rbx
、%rbp
和%r12~%r15
被划分为被调用者保存寄存器。当过程
P 调用过程 Q 时,Q 必须保存这些寄存器的值,保证它们的值在 Q 返回到 P
时与 Q 被调用时是一样的。过程 Q
保存一个寄存器的值不变,要么就是根本不去改变它,要么就是把原始值压入栈中,改变寄存器的值,然后在返回前从栈中弹出旧值。压入寄存器的值会在栈帧中创建标号为“保存的寄存器”的一部分。
所有其他的寄存器,除了栈指针%rsp
,都分类为调用者保存寄存器。这就意味着任何函数都能修改它们。
练习题:3.32 3.33
Machine-Level Programming IV: Data
计算同一个数据结构中的两个指针之差,结果的数据类型为long
,值等于两个地址之差除以该数据类型的大小。
一般用MOV
取值,LEA
取地址。
声明T D[R][C]
,数组元素D[i][j]
的内存地址为\(x_D+L(C\cdot i+j)\)。
嵌套数组的另一种形式:一个一维指针数组,数组中的每个元素是指向一维数组的指针。此时寻址是\(M[8\cdot i]+L\cdot j\)。
对于定长数组B[N][N]
,遍历第\(k\)列,会生成一个指针Bptr
指向B[0][k]
,以及另一个指针Bend
指向B[N][k]
;遍历时每次给Bptr
加上\(N\)(汇编代码中其实是\(LN\)),直到Bptr==Bend
结束。
对于多维变长数组,寻址时用乘法指令(而不是leq
指令)计算\(C\cdot
i\),遍历列的优化和定长数组相似,只不过判断结束时使用j==n
。
结构体访问字段即是加上一定的偏移量,在内存中的顺序和声明时的顺序一致。任何\(K\)字节的基本对象的地址必须是\(K\)的倍数。
结构体整体也要向\(K\)对齐,\(K\)是结构体中基本对象中最大的\(K\)。
重新排列结构体元素节省空间:贪心,大的放在前面。
练习题:3.36 3.37 3.38 3.41 3.42 3.44 3.45
Machine-Level Programming V: Advanced Topics
缓冲区溢出:超出为数组分配的内存空间。存在于gets
、strcpy
、strcat
、scanf
、fscanf
、sscanf
等字符串库函数中。
栈缓冲区溢出攻击:gets
函数写入的字符串覆盖了上一个函数的返回地址。
代码注入攻击:在栈缓冲区写入攻击代码,并且覆盖上一个函数的返回地址为攻击代码的地址。
对抗缓冲区溢出攻击
- 使用限制字符串长度的函数,使用
fgets
、strncpy
、%ns
等; - 栈随机化的思想使得栈的位置在程序每次运行时都有变化。因此,即使许多机器都运行同样的代码,它们的栈地址都是不同的。实现的方式是:程序开始时,在栈上分配一段\(0\sim n\)字节之间的随机大小的空间,程序不使用这段空间,但是它会导致程序每次执行时后续的栈位置发生了变化。地址空间布局随机化,简称 ASLR,每次运行时程序的不同部分,包括程序代码、库代码、栈、全局变量和堆数据,都会被加载到内存的不同区域;
- 限制哪些内存区域能够存放可执行代码。增加“可执行”权限,标记栈为不可执行。
- 在发生了越界写的时候,在造成任何有害结果之前,尝试检测到它。栈保护者机制的思想是在栈帧中任何局部缓冲区与栈状态之间存储一个特殊的金丝雀值,也称为哨兵值。金丝雀值是在程序每次运行时随机产生的,因此,攻击者没有简单的办法能够知道它是什么。在恢复寄存器状态和从函数返回之前,程序检査这个金丝雀值是否被该函数的某个操作或者该函数调用的某个函数的某个操作改变了。如果是的,那么程序异常中止。
面向返回编程(ROP)攻击:利用一系列
Gadget(以0xc3
结束)执行一系列指令。
对于联合的引用都是数据结构的起始位置,一个联合的总的大小等于它最大字段的大小。一种应用情况是,我们事先知道对一个数据结构中的两个不同字段的使用是互斥的,那么将这两个字段声明为联合的一部分,而不是结构的部分,会减小分配空间的总量。联合还可以用来访问不同数据类型的位模式。当用联合来将各种不同大小的数据类型结合到一起时,字节顺序问题就变得很重要了。
变长栈帧:有些函数,需要的局部存储是变长的。例如,当函数调用alloca
时就会发生这种情况。alloca
是一个标准库函数,可以在栈上分配任意字节数量的存储。当代码声明一个局部变长数组时,也会发生这种情况。
为了管理变长栈帧,x86-64
代码使用寄存器%rbp
作为帧指针(或基指针),代码必须把%rbp
之前的值保存到栈中,因为它是一个被调用者保存寄存器。然后在函数的整个执行过程中,都使得%rbp
指向那个时刻栈的位置,然后用固定长度的局部变量相对于%rbp
的偏移量来引用它们。在函数的结尾,leave
指令将帧指针恢复到它之前的值。这条指令不需要参数,等价于执行movq %rbp, %rsp
和popq %rbp
,这个指令具有释放整个栈帧的效果。
练习题:3.46
计算机系统基础复习提纲 - 第二部分