跳转至

Chapter 3 程序的机器级表示

一. 引入

（计算机具体的执行过程）

[1] step1: 计算机执行机器编码，用字节序列编码低级的操作(处理数据/管理内存...) [2] step2: 生成机器代码，随后编译器以汇编代码的形式产生输出 [3] step3: 调用汇编器和链接器，根据汇编代码生成可执行的机器代码

（需要学习的地方）

[1] 观察机器代码，以及人类可读的表示形式——汇编代码 [2] 高级语言（比如C语言）编写的程序可以在很多不同的机器上编译与执行 [3] 汇编代码与特定机器密切相关 [4] 要求是：能够阅读和理解编译器产生的代码 [5] 源代码和对应的汇编代码是一种逆向工程(reverse engineering)

二. 本章重点内容

3.1 历史观点

摩尔定律：

晶体管数量每几个月就会翻一倍，在X86微处理器的历史上，这种增长已经存在了几十年

3.2 程序编码

(1) 基础控制指令
Text Only
1
gcc -Og -o p p1.c p2.c

[1] -Og 告诉编译器使用合适的C代码优化等级 (一般是 -O1 或 -O2 )

[2] 执行过程：gcc命令调用一系列程序，将==源代码==转换成可执行代码

【step1】 1. C预处理器扩展源代码，插入所有用#include命令指定的文件 2. C预处理器同时扩展所有用#define声明指定的宏 【step2】 编译器产生两个源文件的==汇编代码==，名字分别为p1.s // p2.s 【step3】 汇编器会将汇编代码转换成二进制==目标代码==的文件p1.o // p2.o [目标代码是机器代码的一种形式，它包含所有指令的二进制形式，但是还差全局值的地址] 【step4】 链接器将两个目标代码文件与实现库函数的代码合并，并产生可执行代码文件p [由-o p 指令指定]

[3] 图示:

  1. 查看源代码对应的汇编代码：

    Text Only
    1
    g++ -Og -S hello.cpp
    ![[截屏2023-10-08 16.34.01.png]] ![[截屏2023-10-08 16.35.03.png]] 这里： g++运行编译器，产生一个汇编文件hello.s 但是不做进一步处理（通常情况下会继续调用汇编器产生目标代码文件）

  2. 编译与汇编该代码：

    Text Only
    1
    g++ -Og -c hello.cpp
    ![[Pasted image 20231008164028.png]] ![[Pasted image 20231008164117.png]] 这里： 会产生目标代码文件hello.o 它是二进制的，无法直接查看

注意： 机器执行的程序只是一个字节序列，它是对一系列编指令的编码，形如：

C++
1
53 48 89 d3 e8 00 00 00 48 89 03 5b c3
机器本身对产生这些指令的源代码几乎一无所知

  1. 反汇编根据机器代码产生类似于汇编代码的形式： aim ：想要查看机器代码文件的内容 approach：使用反汇编器(disassembler) thm：根据机器代码产生一种类似于汇编代码的形式，以便于人类阅读

Text Only
1
objdump -d hello.o
![[Pasted image 20231008164744.png]] 这里： （1）反汇编器只是基于机器代码文件中的字节序列来确定机器代码的，它不需要访问该程序的源代码或汇编代码 （2）反汇编器使用的指令命名原则 和 g++生成汇编代码的指令 有些许差别 有时候后缀q的存在没有影响，比如：callq 与 call // retq 与 ret

  1. 生成可执行代码： 需要对一组目标代码文件运行链接器，而这一组文件中必须包含main函数
    Text Only
    1
    objdump -d prog // 生成可执行代码： prog（程序名）
    ![[Pasted image 20231008165449.png]] 这里： 链接器的任务之一就是为函数调用找到匹配函数的可执行代码的位置
（2）关于格式的注解 && 阅读时的注意点：

[1] 所有以 ' . ' 开头的行都是指导汇编器与链接器工作的伪指令，常可忽略 ![[Pasted image 20231008170141.png]]

[2]写旁批注释的格式： ![[Pasted image 20231008170248.png]]

(3) 数据格式：

1）字 (word) ： word：16位数据类型 double words: 双字，32位(bit)数 == 4bite(字节) quad words: 四字，64位(bit)数 == 8bite(字节)

2）常见类型： ![[Pasted image 20231008170659.png]] 其中需要注意一点： 在X86-64框架下，C指针char*的大小为：64 bit = 8 bite

（4）访问信息：

  1. 寄存器抽象结构图： ![[Pasted image 20231008180127.png]]

  2. 两条规则：[后面会用到，这些就是约定俗成的规章制度]

    对于生成小于8字节(64位)结果的指令： [1] 生成1 / 2字节数字的指令会保持剩下的字节不变 [2] 生成4字节数字的指令会将高位4个字节设置为0

  3. 操作数指示符： def ( 操作数 ) ：

    大多数指令会有一个或者多个操作数(operand) => 指示出执行一个操作中要使用的源数据值 和 放置结果的目的位置

category (操作数格式) ： [说明] 源数据值可以以常数形式给出，或是从寄存器或内存中读出，结果可以放置在寄存器或内存中 [类别1] 立即数(immediate) ：

(1)表示常数值 (2)表示方法为：’$‘ + C标准的常数值，形如：$-577 and $0x1F

[类别2] 寄存器(register) :

（1）使用符号 \(r_a\) 表示任意寄存器 a
（2）使用引用符号R [ \(r_a\) ] 表示它的值

机理：将寄存器集合看成一个数组R，用寄存器标识符作为索引

[类别3] 内存引用(memory)：

（1）会根据计算出来的地址(通常称为：有效地址)访问某个内存位置 （2）表示法：\(M_b\)[Addr] 表示对存储在内存中从地址为Addr开始的b个字节值的引用，常亦可省略下标b

机理：将内存视作一个很大的字节数组

![[Pasted image 20231008182421.png]]

  1. 数据传送指令： (1) 最常使用的指令：将data从一个位置复制到另一个位置

(2) 常用的指令是：MOV类 ![[Pasted image 20231008182658.png]]

格式：

Text Only
1
2
mov? a , b     // 第一个是源操作数，第二个是目的操作数
               // 语法含义：将 a 复制进 b

实例： ![[Pasted image 20231008183150.png]]

(3) 操作中对于“复制”的要求：【🌟】 [1] 源操作数是一个立即数，存储在寄存器或内存中 [2] 目的操作数指定一个位置，要么是一个寄存器，要么是一个内存地址 [3] 两个操作数不能都指向内存位置

=> 随之而来一个重要的问题： Ques: 如何将一个值从 一个内存位置 复制到 另一个内存位置？ Ans：

使用两条指令， 第一条指令：将源值加载到寄存器中 第二条指令：将该寄存器值写入目的位置

(4) 位置匹配的规则：【不重要，了解即可】 [1] 大多数情况下，MOV指令只会更新目的操作数指定的那些寄存器字节或内存位置 [2] 唯一的例外就是movl指令以寄存器作为目的地时，它会将该寄存器的高位4字节设置成0 「这就是之前提到的两条规则之一，记得review」 [3] movabsq 指令能够以任意64位立即数值作为源操作数，并且只能以寄存器为目的

  1. 数据传送实例： ![[Pasted image 20231008184201.png]] (1) process & analysis：

    [1] 函数exchange由三条指令实现：两个数据传送(movq)，加上一条返回函数被调用点的指令(ret) [2] 程序开始执行：过程参数xp和y分别存储在寄存器 %rdi 和 %rsi 中 [3] 指令2从内存中读出x，将它存放在寄存器%rax中，直接实现了x = *xp [4] 随后，用寄存器 %rax 从这个函数返回一个值，因而返回值就是x [5] 指令3将y写入到寄存器%rdi中的xp指向的内存位置，直接实现了*xp = y [6] rank2: 从内存中读值到寄存器中 [7] rank3: 从寄存器写到内存

(2) attention：

[1]间接引用指针就是将指针放在一个寄存器中，然后在内存引用中使用这个寄存器

需要注意： [1.1] 对于指针的复制引用，需要采用' (某寄存器) '的格式，比如：(%rdi) [1.2] 对于局部变量的复制，直接是'某寄存器' 即可，比如：%rax

[2]像x这样的局部变量通常是保存在寄存器中，而不是内存中

[3] 访问寄存器比访问内存快的多

  1. 内存中的栈结构 (1) 栈可以实现为一个数组，总是从数组的一端插入和删除元素，这一端被称为“栈顶”

(2) 程序栈 总是放在内存中的某个区域

(3) 栈的基本操作: ![[Pasted image 20231008190229.png]]

(4) 栈的结构示意图： ![[Pasted image 20231008191223.png]]

  1. 结构说明： 栈是倒着绘制的 （1）栈向下(低地址)增长，栈顶元素的地址是在所有元素地址中最低的 （2）压栈(入栈)：减小栈指针(%rsp的值)，并将数据存放在对应内存中[%rsp往上跑] （3）出栈：从内存中读取数据，并增加栈指针的值[%rsp向下跑]

  2. 出入栈本质及对应汇编代码： 入栈： [ pushq %rax 展开即为下列 ]

    Text Only
    1
2
3
    subq $8 , %rsp     # 栈指针向下走8个字节（注意是指针减法），实现“扩展容量”
movq %rbp , (%rsp)  # 将寄存器%rbp中的值复制到%rsp寄存器中
#从而实现：新值进入栈指针对应的寄存器中，实现“入栈”

出栈： [ popq %rax 展开即为下列 ]

Text Only
1
2
movq (%rsp), %rax  # 将栈指针对应寄存器内的值复制到返回值寄存器中，实现“ 返回出‘被踢者’ ”功能
addq $8 , %rsp     # 栈指针向上走8个字节，实现“扫地出门”

(5) 实例解释说明： ![[Pasted image 20231008192724.png]] 当%rsp为0x108（指针指向），%rax为0x123（包裹内到值）时：

(1) 执行 pushq %rax : 首先%rsp会减去8，得到0x100的位置；然后将值0x123放入内存地址0x100处

(2) 执行完pushq %rax后，如果立即执行popq %rax: 先从内存中读出值0x123，再写到寄存器%rax中（用于返回） 然后寄存器%rsp的值将会增加回到0x108

解释： （1）为什么上文要写这句话：“执行完pushq %rax后，如果立即执行”

因为在进栈之后，出栈之前，必然会有很多其他的操作，因此在pushq与popq之间实际上还有很多内容

（2）值0x123仍然保持在内存位置为0x100处，直至被覆盖(例如有另一个操作改写此处值...) [需要理解的是栈是一个抽象结构，而内存是实际结构，所谓“被栈退了”并不意味着它就“消失”了，它仍在原位置，只是此时它并不在我们的视野范围内（即：“栈内”）]

（5）算术与逻辑操作：
  1. 引入：

（1）常见整数算术操作： ![[Pasted image 20231008214525.png]]

（2）加载有效地址(leaq)：

加载有效地址(leaq)：常用来执行简单的算术操作

  1. 加载有效地址的用途： [指令为：leaq] 1）指令leaq实际上是movq指令的变形:

    指令形式是：从内存读取数据到寄存器，但实际上它根本没有引用内存；它不是从指定位置读入数据，而是将有效地址写入目的操作数

2）可以简洁地描述普通的算术操作: ![[Pasted image 20231008215230.png]]

（point）目的操作数必须是一个寄存器

  1. 一元和二元操作：

def(一元操作)：只有一个操作数，既是源也是目的；这个操作数可以是一个寄存器，也可以是一个内存位置

比如：incq(%rsq)会使栈顶 + 1 (8字节元素)，类比C中的++与--

def(二元操作)：第二个操作数既是源也是目的

可以类比C中的x-=y

实例： subq %rax , %rdx 使得寄存器%rdx的值减去%rax中的值 更好的翻译是：从%rdx中减去%rax

要点说明： [1]第一个操作数可以是立即数、寄存器、内存位置 [2]第二个操作数可以是寄存器、内存位置 [point] 当第二个操作数是内存地址时，处理器必须从内存中读出值，执行操作，再把结果写回内存

  1. 移位操作： 形式：

    先给出移位量，然后第二项给出的是具体要移位的数；目的操作数可以是一个寄存器或是一个内存位置

左移：

SAL与SHL，效果一样，都是将右边填充0

右移：

SAR：算术移位(填上符号位). 记作 \(>>_A\) SHR：逻辑移位(填上0). 记作 \(>>_L\)

（6）控制：
1）引入：

目前为止，我们只考虑了直线代码的行为与逻辑，即：指令一条接一条顺序执行 如果想实现更加便利的功能，比如条件跳转... 用jump指令可以改变一组code的执行顺序，jump指令指定控制应该传递到程序的某个其他部分，也可能是依赖于某个测试的结果

2）条件码(condition code)：

  1. def(条件码寄存器)：描述了最新的算术 or 逻辑操作的属性

  2. 常见的条件码： [1]直接判定的条件码： ![[Pasted image 20231009131552.png]] 例如： ![[Pasted image 20231009131704.png]]

[2]操作判定的条件码： 1) CMP a , b ：利用(b-a)设置条件

2) TEST a , b : 利用(a&b)设置条件

![[Pasted image 20231009131938.png]]

  1. 访问条件码

    具体意义不需要了解；只需要掌握它的用处

用处： 对于指令setX \(D_s\)：将 \(D_s\) 对应的条件作为判定条件，以便于后续“根据判断条件是否成立”进行操作

实例：

Text Only
1
2
3
4
5
6
7
8
9
# int comp(data_t a , data_t b)
# a in %rdi , b in %rsi
# code:

comp: 
    cmpq   %rsi , %rdi  # 比较a:b
    setl   %al          # 设置通过条件 a < b
    movzbl %al , %eax   # 当结果 %eax 满足 %al(上述通过条件) 时
    ret                 # 返回

常见的set访问条件码： ![[Pasted image 20231009133003.png]]

  1. 跳转指令： 1）意义：

    导致执行切换到一个全新的位置

2）目的：

通常用一个label指明

3）形式:

Text Only
1
2
3
4
5
    jX Label    # 若满足了jX对应的判定条件，则code直接跳转到label所指的地方，执行后续；反之按顺序向下进行
    ...

  Label:        # Label所在处
    ...

4）jX对应的判断条件： ![[Pasted image 20231009133513.png]] ps: 常见英文缩写对应含义 e: equal ==

g: greater > ge: greater OR equal >=

l: less le: less OR equal <=

s: negative number s ns not negative number s

3）控制结构：
1. 重点：

汇编代码==的构造逻辑 跟 C语言中的==goto语句 相同

2. 实现：

方法1: 条件控制来实现条件分支 ![[Pasted image 20231009134542.png]] ![[Pasted image 20231009134600.png]]

方法2: 条件传送来实现条件分支

为什么要使用条件传送？ ans: 传统的条件控制见方法1，效率较低 方法2使用 数据 的条件转移：计算一个条件操作的两种结果，然后再根据条件是否满足从中选取一个

![[Pasted image 20231009140038.png]] ![[Pasted image 20231009140057.png]]

本例说明： 它既计算了y-x，也计算了x-y，分别命名为rval与eval，然后它再测试x是否>=y；如果是，就在函数返回rval前，将eval复制到rval中

3. 常见条件传送指令：

形式：

Text Only
1
2
3
4
cmovX S , R 

每条指令都有两个操作数，源操作数S(寄存器或内存地址) 以及 目的寄存器R
源值在内存或源寄存器中读取，但是只有在指定的条件满足时，才会被复制到目的寄存器中
指令集合： ![[Pasted image 20231009141051.png]]

4. 三目运算符逻辑解释：

![[Pasted image 20231009141528.png]]

注意：

无论测试结果如何，抽象代码都会自动地对then-expr和else-expr进行求值 如果这两个表达式中任何一个产生错误条件or副作用，将导致非法行为

例如：

C++
1
2
3
4
5
long hbx(long *xp)
{
    return (xp ? *xp : 0);
}
//代码非法，因为会即使测试结果为false(xp是一个空指针)时，依然会执行*xp操作(对空指针解引用)，导致错误

5. 具体的循环分支：

1）do-while template： ![[Pasted image 20231009142420.png]]

2）while template： ![[Pasted image 20231009142648.png]]

3）for review：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
for(init_expr;test_expr;update_expr)
{
    body_statement
}

<=>

init_expr;
while(test_expr)
{
    body_statement
    update_expr;
}

template： for转换成while ![[Pasted image 20231009143424.png]] while转换成goto ![[Pasted image 20231009143444.png]] 汇编 ![[Pasted image 20231009143550.png]]

4）switch 重点：

(1)switch语句根据一个整数索引值进行多重分支(multiway branching) (2)领会跳转表(jump table)的妙用

![[Pasted image 20231009144804.png]] ![[Pasted image 20231009144903.png]]

（7）过程：

具体实现细节不要求完全掌握，浏览大意即可

1) 调用栈数据结构进行内存管理

2) 常见指令：

Text Only
1
2
call Label   # 过程调用
ret          # 从过程调用中返回

3) 栈上的存储内容： ![[Pasted image 20231009152143.png]]

4) 典型的过程调用例： ![[Pasted image 20231009152937.png]]

  1. 递归的实现[汇编代码表示] C语言：
    C++
    1
2
3
4
5
6
7
    long rfact(long n) // 实现阶乘函数
{
    long result;
    if(n<=1) result =1;
    else result = n * rfact(n-1);
    return result;
}

汇编：

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# long rfact
# n in %rdi

rfact:
    pushq %rbx         # 存储寄存器%rbx
    movq %rdi,%rbx     # 将%rdi内的值n复制到%rbx中
    movl $1,%eax       # %eax是存储答案(本轮)的寄存器，先赋值为1
    cmpq $1,%rdi       # 将%rdi中的值n与进行比对
    jle .L35           # 如果n<=1(符号根据jle的含义)，则跳转至.L35部分展开后续；反之向下进行即可

    leaq -1(%rdi),%rdi # 将%rdi中的值减1，并覆盖%rdi（这里就体现出为什么上面要 movq %rdi,%rbx ）
    call rfact         # 调用递归函数(结果保存在寄存器%rax中)
    imulq %rbx,%rax    # 将%rax中的值与%rbx中的值相乘，得到最终结果（本轮返回值是%rax、%eax[本质上这两者没有区                                                                 别]）

.L35:
    popq %rbx
    ret

（8）数组分配与访问：

[1] 基本原则： 1. 声明形式：

T A[N];

  1. 实际含义：

    [1]起始位置是\(X_A\) [2]在内存中分配了一个长度为L*N字节的连续区域，这里L是数据类型T的大小(单位为字节) [3]引入了一个标识符A，可以用A来表示指向数组开头的指针，这个指针就是\(X_A\) [4]整数索引追踪元素，数组元素i会被存放在\(X_A\) + L* i 的地方

  2. 实例： ![[Pasted image 20231009204609.png]]

[2] 指针运算： 1. 如果p是一个指向类型为T的指针，p的值为\(X_p\) ，那么表达式 p+i 的值为\(X_p\) + L* i 2. 单操作数操作符'&'和‘*’可以产生指针以及间接引用一个指针

[3] 嵌套数组的构造与访问方式： 图解： ![[Pasted image 20231009204937.png]]

原则： 1. 要访问多维数组的元素，编译器会以数组起点作为基地址，偏移量为索引 2. 访问顺序是“行优先”，先按照行的顺序遍历完前面所有，然后再进行本行的列遍历

计算地址的公式： 对于数组：T D[R][C] 它的数组元素D[i][j]的内存地址为：

&D[i][j] = \(X_D\) + L*( C* i + j )

proof:

易见，它的地址应该是 \(X_D\) + i * C * L + j * L 基地址 从0到i-1行共有i个rank 到当前行后进行列遍历

[4] 定长数组：...

[5] 变长数组：...

（9）异质的数据结构：

看看例子即可，这块没什么讲究

【1】常见的两种类型：

类别一：struct（结构体） ![[Pasted image 20231009210512.png]]

![[Pasted image 20231009210641.png]]

类别二：union （联合体） ![[Pasted image 20231009210711.png]]

特点： 1）union U3* 的指针p , p->c , p-> i[0] , p->v 引用的都是数据结构的起始位置 2）一个union的总大小等于它最大字段的大小

【2】数据对齐原则：

thm(对齐原则)：

任何k字节的基本对象的地址必须是k的倍数

意义：

简化了形成处理器和内存系统之间接口的硬件设计

常规写法 与对齐原则 的异同： ![[Pasted image 20231009211458.png]]

（10）杂项：【了解即可，内容很深刻，可以看书上的详细解释说明】

1）使用gdb调试器，常见指令如下： ![[Pasted image 20231009211704.png]]

2）对抗缓冲区溢出攻击的三大策略：

[1] 栈随机化思想 [2] Canary检测（预警机制） [3] 限制可执行代码区域

3）支持变长栈帧：

方式：设置可以变动的—— 帧指针：%rbp (base pointer)

图解： ![[Pasted image 20231009212105.png]]

（11）浮点代码：

实际上这一部分没什么新的，只是一些符号和表示换了一种写法，本质没变！

表示方法；

1）汇编代码用寄存器%xmm0~%xmm15来引用它们 2）每个XMM寄存器都是对应的YMM寄存器的低128位 (16 bites)

传递操作：

类比整型中的 MOV类 ![[Pasted image 20231009212706.png]]

浮点数之间的类型转换(精度调节)：

![[Pasted image 20231009212825.png]]

![[Pasted image 20231009212841.png]]

基础运算操作：

类比整型中的add / sub / imul ... ![[Pasted image 20231009213132.png]]

位级操作：

类比整型中的SHL/SAL【左移】；SHR/SAR【右移】 ![[Pasted image 20231009213505.png]]

比较操作：

类比整型中的 CMP类 ![[Pasted image 20231009213743.png]]

条件码设置：

类比整型中的set类 ![[Pasted image 20231009213708.png]]

过程中的符点代码：

在浮点数的运算/调用中，XMM寄存器用来向函数传递8个符点参数，以及从函数返回浮点值

规则： - （参数寄存器）XMM寄存器%xmm0~%xmm7最多传递8个参数 - （返回值容器寄存器）函数使用%xmm0来返回浮点值 - （覆盖与改写）所有XMM寄存器都是调用者保存的，被调用者不用保存就可以直接改写这些寄存器中的任意一个