Post

CS:APP读书笔记-3-程序的机器级表示

Posted Updated
By Iolop 29 min read

第三章：程序的机器级表示

面对现在的可执行文件，我们千头万绪不知道该怎么去理解它。在Windows上，我们知道双击去运行它；Linux上，我们可以在命令行中通过./file的形式去执行。这一章，我们将会走进程序的机器级表示，来理解代码时如何被转变成CPU可以理解的模式的，我们又是如何来表示我们在源代码中的各种数据，而CPU又是如何访问它们。除此外，我们还将学习到我们常用的流程控制又是如何实现。以上这些内容采用C语言进行描述以及通过gcc编译出的各类中间文件进行解释，其他的类型比如虚拟机、JIT、解释器类型语言不在此列。

CPU的演化

要理解可执行文件是怎么运行的，我们有必要先回头去看看CPU的演化过程。再最早时期，也许你曾看到书上提到一种打孔程序机1。这种形式后来被汇编代码所取代，因为汇编代码更容易被人们记忆。再后来，随着CPU的发展，我们拥有了更强的性能和更广阔的可用空间，随之演变的是更抽象的语言——我们现在常用的高级语言。简单的来看，我们把这三种演化的关系：机器码——汇编代码——高级语言，可以映射到如今的源代码到可执行代码的翻译之路上：编译——汇编——链接。

以前常说的x86，其实是Intel的32位处理器，可惜Intel没把握住64这个风口，让AMD先一步迈了出去，先有了amd64(注意和arm64不是同一个东西)，然后Intel跟进，出现了x86-64(强行更名)。

程序编码

通过如下命令，我们可以编译源代码，得到可执行代码。

1

gcc -Og -o hello hello.c

gcc是我们之前说的一整套工具，这是Linux上的默认编译器。通过上述命令，gcc会自动地帮助你执行一系列地命令来完成预处理、编译、汇编、链接过程。

  1. 预处理：完成对源文件的拓展，插入头文件。
  2. 编译：通过编译器，转化位汇编代码，产生.s文件。
  3. 汇编：将汇编代码转化成二进制目标代码，产生.o文件。
  4. 链接：将上述文件和库进行链接，包括重定位等一系列操作，生成可执行文件。

除了gcc，或许你还听说过clangd。

机器级代码

我们之前提到过，计算机系统内很重要的一个东西就是抽象，在机器级编程这一级别，我们拥有两个很重要的抽象。第一个是 指令集体系/架构(Instruction Set Architecture, ISA) ，程序的行为在ISA的抽象下，表现的像是顺序执行每一条指令。实际上硬件的设计非常复杂，很多时候它可以并发执行许多指令，但是可以保证效果和顺序指令保持一致。第二种抽象就是程序使用的内存地址是 虚拟地址 。系统提供的内存模型在这种抽象下像是一个巨大的数组。在下x86-64的情况下，我们需要知道以下几种在机器级代码中的小东西，这些东西通常被C语言的高级抽象隐藏，让我们免于直接面对他们的难处。除非你需要使用内联汇编。

  • 程序计数器(Program Counter)：表示即将执行的下一条指令，通常在amd64中使用 rip 寄存器来指代。
  • 通用寄存器(register)：用来存储64位的值，在x86-64架构中，常见的是RAX、RDX、RDI、RSI……这些寄存器用来存储状态、保存临时数据、变量等值。
  • 条件寄存器：用来存储最近一次的运算中的状态信息，用来实现控制流中的条件变化。
  • 一组向量寄存器：可以保存一个或者多个整数/浮点值。

不同的架构下，这些寄存器的名字不同。比如ARM64中，通用寄存器采用x0-x30的命名方式，程序计数器名字就是pc，而非rip。同样的，mips32、mips64这些架构更是不同。在后续的分析中，我们只会使用x86-64(amd64)架构。如果有兴趣，可以查阅这些架构的官方手册，观察和x86-64的不同。或者采用交叉编译的方式，编译出这些平台可用的ELF，在IDA中查看。

我们之前提到过，系统把内存视为一片连续的巨大字节数组。同样的，我们虽然在C里面拥有各种结构体，但是在内存里它们只是连续的数据而已，不会有任何区别。有无符号，指针类型这些都不在汇编代码的考虑范围内。那么在内存里，我们究竟有什么？它们包含着运行程序所必须的库函数、堆栈数据、程序本身的代码。在高位上，一般是留给内核所用，程序能用的往往是低位。目前来说，虽然我们拥有64位的寻址空间，但是一般只用48位即可满足需求。在这一大片空间内，操作系统负责管理虚拟的地址空间，将虚拟地址翻译到物理地址。

汇编代码示例

现在，我们对以下代码，使用 gcc -Og -S bitset_func.c，就会得到一个汇编代码。它的形式和源码有很大的不同，不过我们可以简单一窥其中的对应。

1
2
3
4
5
6

#include <stdio.h>

void set_bit(int *v, int index) {
  int mask = 1 << index;
  *v &= mask;
}

1
2
3
4
5
6

set_bit:
	movl	$1, %eax
	movl	%esi, %ecx
	sall	%cl, %eax
	andl	%eax, (%rdi)
	ret

同时，如果我们使用 gcc -Og -c bitset_func.c，就会得到二进制格式的文件，这时内容已经基本无法肉眼辨别，这其中有一段序列正是我们在上面看到的汇编代码经过汇编后的形式，为了能得到映射，我们需要使用objdump -d bitset_func.o来观察这个二进制文件。

1
2
3
4
5
6
7
8
9

Disassembly of section .text:

0000000000000000 <set_bit>:
   0:   f3 0f 1e fa             endbr64 
   4:   b8 01 00 00 00          mov    $0x1,%eax
   9:   89 f1                   mov    %esi,%ecx
   b:   d3 e0                   shl    %cl,%eax
   d:   21 07                   and    %eax,(%rdi)
   f:   c3                      ret

所以说，在二进制程序中，CPU知道的只是一串字节序列，它读取字节序列并且翻译到唯一映射的操作上，关于这种机器码和汇编代码的映射关系，可以查询各架构的ISA，比如x86-64的架构书就在这里2。也许你注意到了一点，这些指令的长度或长或短，这就是复杂指令集的一种特征——不固定长度的指令。

这时候，我们需要另一个包含了 main 函数的 bitset_main.c 文件。我们使用gcc -Og -c bitset_main.c命令仍然单独编译，但是不链接。然后使用objdump -d bitset_main.o观察

1
2
3
4
5
6
7

#include <stdio.h>
void set_bit(int *v, int index);
int main() {
  int value = 92;
  set_bit(&value, 6);
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Disassembly of section .text:
0000000000000000 <main>:
   0:   f3 0f 1e fa             endbr64 
   4:   48 83 ec 18             sub    $0x18,%rsp
   8:   64 48 8b 04 25 28 00    mov    %fs:0x28,%rax
   f:   00 00 
  11:   48 89 44 24 08          mov    %rax,0x8(%rsp)
  16:   31 c0                   xor    %eax,%eax
  18:   c7 44 24 04 5c 00 00    movl   $0x5c,0x4(%rsp)
  1f:   00 
  20:   48 8d 7c 24 04          lea    0x4(%rsp),%rdi
  25:   be 06 00 00 00          mov    $0x6,%esi
  2a:   e8 00 00 00 00          call   2f <main+0x2f>
  2f:   48 8b 44 24 08          mov    0x8(%rsp),%rax
  34:   64 48 2b 04 25 28 00    sub    %fs:0x28,%rax
  3b:   00 00 
  3d:   75 0a                   jne    49 <main+0x49>
  3f:   b8 00 00 00 00          mov    $0x0,%eax
  44:   48 83 c4 18             add    $0x18,%rsp
  48:   c3                      ret

注意，对比能看到，在进行set_bit调用的时候，位置是留空的。因为call指令的映射是0x58。

我们再次使用gcc -Og -o bitset bitset_func.c bitset_main.c。这一次，完成可执行文件的编译、汇编、链接。同样的，使用objdump -d bitset来观察编译结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

0000000000001149 <main>:
    1149:       f3 0f 1e fa             endbr64 
    114d:       48 83 ec 18             sub    $0x18,%rsp
    1151:       64 48 8b 04 25 28 00    mov    %fs:0x28,%rax
    1158:       00 00 
    115a:       48 89 44 24 08          mov    %rax,0x8(%rsp)
    115f:       31 c0                   xor    %eax,%eax
    1161:       c7 44 24 04 5c 00 00    movl   $0x5c,0x4(%rsp)
    1168:       00 
    1169:       48 8d 7c 24 04          lea    0x4(%rsp),%rdi
    116e:       be 06 00 00 00          mov    $0x6,%esi
    1173:       e8 1f 00 00 00          call   1197 <set_bit>
    1178:       48 8b 44 24 08          mov    0x8(%rsp),%rax
    117d:       64 48 2b 04 25 28 00    sub    %fs:0x28,%rax
    1184:       00 00 
    1186:       75 0a                   jne    1192 <main+0x49>
    1188:       b8 00 00 00 00          mov    $0x0,%eax
    118d:       48 83 c4 18             add    $0x18,%rsp
    1191:       c3                      ret    
    1192:       e8 b9 fe ff ff          call   1050 <__stack_chk_fail@plt>

0000000000001197 <set_bit>:
    1197:       f3 0f 1e fa             endbr64 
    119b:       b8 01 00 00 00          mov    $0x1,%eax
    11a0:       89 f1                   mov    %esi,%ecx
    11a2:       d3 e0                   shl    %cl,%eax
    11a4:       21 07                   and    %eax,(%rdi)
    11a6:       c3                      ret

此时，经过了链接的步骤，我们能发现，这里的bit_set已经被正确的填入了地址。这再次印证了我们之前提到的步骤：编译、汇编、链接。

在上述中展示的反汇编代码中，我们看到的格式或许和你知道的不太一样。这是因为Linux默认采用AT&T格式的汇编，这和Windows采用Intel格式不太一样，但是区别不大。有兴趣的朋友自行搜索这两者的差异即可。

数据格式

在上面的汇编代码 bitset_func.s中，也许你能看到一些操作指令后面跟着的符号，比如 l，q 这类。它们其实是表示了操作的数据大小。但是在下面经过 objdump 反汇编出来的结果中，这些表示数据大小的符号没有出现。一般来说，在Intel处理器上，我们有如下的大小对应关系。由于历史原因，2字节的被称为word，随之而来的是4字节被称为double words或者long words，8字节称为quad words。

如果你使用gdb，这可能有点疑惑。因为gdb的x命令对数据的对应关系是

  • b - byte
  • h - halfword (16-bit value)
  • w - word (32-bit value)
  • g - giant word (64-bit value)
C语言类型Intel数据类型后缀表示大小
char字节b1
short字w2
int双字l4
long四字q8
char *四字q8
float单精度s4
double双精度l8

访问数据

在x86-64体系内，我们常接触的寄存器不多通用寄存器16个3。关于这些寄存器的用法，在ABI中有相关规定，amd64上我们记住参数寄存器(rdi/rsi/rdx/rcx/r8/r9)和返回寄存器(rax)。对于寄存器，一些基本的知识就不再赘述了，比如操作的数据大小、操作方向、数据传送指令、压栈弹栈、数值计算等4。这里我们只说最关键的一部分，寻址。在AT&T语法中，寻址可以表示为下面几种形式。

寻址听起来可能不太容易理解，可以理解成我们该如何根据某种数据格式，去哪里寻找对应的数据。

同时，你可能对为什么Go语言能够多值返回，C却只能有一个返回值有疑惑。它们明明都可以在Linux平台运行，遵守同一套ABI。恭喜你，入门啦！虽然它们遵守同一个ABI，可是它们的实现却有区别。在gcc编译中，c采用了寄存器+栈传参和寄存器rax返回，但是Go采用栈帧传参，返回值也是在栈上面。栈可是不受限制的，这也不奇怪为什么Go能多值返回了。如果你有兴趣用IDA去查看一个编译好的Go，在调用函数的时候你会发现，它的压栈操作总会多那么一点。并且返回之后，总会从栈取值。

格式操作的数据寻址方式
$$ 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,s)$$M[Imm+R[r_b]+R[r_i]\cdot s]$比例变址寻址

上面的寻址方式很多，其实存在共性，看最后一个比例变址寻址基本都能明白。M代表内存空间，R代表寄存器。如果你对指针这一概念比较熟悉，那么就能很快的理解这些寻址方式的应用。

流程控制

在C里面，我们有流程控制的语句，比如 if-else,while,continue-break-goto，它们又是怎么实现的呢？CPU除了上面说到的整数寄存器之外，还有一组 条件寄存器(Condition code reg) ，它们保存着最近一次指令执行后的条件变化。

  • CF(carrary flag)：进位标志，最高位产生了进位。
  • ZF(zero flag)：零表示，操作得到了0。
  • SF(sign flag)：符号标志，操作得到了负数。
  • OF(overflow flag)：溢出标志，操作导致一个补码溢出。

当我们在进行数学运算或者条件判断时，这些标志位就能辅助我们。例如一次运算 t=a+b

  • CF被置位：无符号溢出。
  • ZF被置位：t=0。
  • SF被置位：t<0。
  • OF被置位：有符号加法溢出。

同理，我们的流程控制中的条件可以被等价的转化为一次运算，然后来判断这些条件码，即可得到所需。在这里，我们需要注意一个问题，如何比较无符号数和有符号数？假如我们进行一次 CMP 指令，该怎么判断我们到底进行了哪一种数据的比较。所以这里有一套需要记一下的指令助记符，那就是条件跳转。实际上下面的大于小于都还可以接一个 e ，形成 jge 这种格式，等价于大于等于。

条件跳转条件
$jz/jnz$为0/不为0时跳转
$jg/jnle$ $(great/not\ less\ equal)$有符号大于
$jl/jnge (less/not great equal)$有符号小于
$ja/jnbe (above/not\ below\ equal)$无符号大于
$jb/jnae(below/not\ above\ equal)$无符号小于

除开上述的条件跳转，我们还有条件传送指令 cmovge 现在我们能简单的分辨这个指令了 compare and move when great & equal 。简单来说，现在通过这条指令，我们可以完成一次 cmp+mov ，而不必用两条指令完成。

为什么需要这个指令？这其实和代码执行的过程有关，在CPU内部，一条指令的执行涉及到取指令，取数据，运算，回写数据等步骤，这些步骤可以拆分成流水线一样，这样的话我们就可以在上一个指令执行的同时，预取下一个指令和它所需。一次条件跳转可能浪费很多个时钟周期，因为预取的数据不可用，流水线要重填充。所以尽量保证预测命中，这种优化思路，我们能够在DPDK中大量看见。

那么条件传送是完美无缺吗？也不见得。由于条件传送可以看成是对两个结果求值，再判断是否更新值。那么以下两种情况，条件传送就不适用：

  • 两个结果之一存在非法使用
  • 结果的运算周期超越条件跳转

流程控制的实现

在汇编代码中，我们常见的流程控制 if-else，for，while 都可以被实现成一个简单的 cmp-jmp。但是有一个不会，那就是 switch。在编译的过程中，switch 如果分支少，是可能被优化成 if 来实现的，当跳转条目多且密集的时候，它会被实现成一个跳转表(jump table)，根据索引来直接跳转。

这是一个较少跳转时的汇编实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
  int a = atoi(argv[1]);
  switch (a) {
  case 100:
    printf("this is %d\n", a);
  case 105:
    printf("this is %d\n", a);
  case 101:
    printf("this is %d\n", a);
  default:
    printf("this is %d\n", a);
  }
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

movq	8(%rsi), %rdi
movl	$10, %edx
movl	$0, %esi
call	strtol@PLT
movl	%eax, %ebx
cmpl	$101, %eax
je	.L2
cmpl	$105, %eax
je	.L3
cmpl	$100, %eax
jne	.L4
movl	%eax, %edx
leaq	.LC0(%rip), %rsi
movl	$1, %edi
movl	$0, %eax
call	__printf_chk@PLT

这是一个跳转条目多且密集时的实现。请注意汇编实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
  int a = atoi(argv[1]);
  switch (a) {
  case 100:
    printf("this is %d\n", a);
  case 105:
    printf("this is %d\n", a);
  case 101:
    printf("this is %d\n", a);
  case 102:
    printf("this is %d\n", a);
  case 106:
    printf("this is %d\n", a);
  default:
    printf("this is %d\n", a);
  }
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

	movq	8(%rsi), %rdi
	movl	$10, %edx
	movl	$0, %esi
	call	strtol@PLT
	movl	%eax, %ebx
	subl	$100, %eax
	cmpl	$6, %eax
	ja	.L2
	movl	%eax, %eax
	leaq	.L4(%rip), %rdx
	movslq	(%rdx,%rax,4), %rax
	addq	%rdx, %rax
	notrack jmp	*%rax
.L4:
	.long	.L8-.L4
	.long	.L7-.L4
	.long	.L6-.L4
	.long	.L2-.L4
	.long	.L2-.L4
	.long	.L5-.L4
	.long	.L3-.L4
	.text

那么跳转条目多又稀疏呢？又恢复成了cmp-jmp。

1
2
3
4
5
6
7
8
9
10
11
12

movq	8(%rsi), %rdi
movl	$10, %edx
movl	$0, %esi
call	strtol@PLT
movl	%eax, %ebx
cmpl	$1022, %eax
je	.L2
jle	.L10
cmpl	$1066, %eax
je	.L7
cmpl	$10021, %eax
jne	.L6

所以编译器的优化过程很多时候可能超过我们的想象，请注意，这些优化有些时候反而是副作用。

过程

过程我们可以理解成一种封装，具体的实现被隐藏在一个接口之下。通过指定具体的参数和返回结果来完成一个功能，这个功能的具体实现可以不被透露。在不同的语言环境下，它可以叫 函数（function），也可以被称为 方法（method） 亦或是 子例程（subroutine），名字如何都无伤大雅，我们只需要记住，这是一种抽象。下层的服务提供者对上提供服务时，不需要上级了解过多的具体细节。在这里，我们要讨论的是C语言中的函数机制。

为了实现机器级别的过程，我们需要确定以下的三个细节（假设P调用Q）：

  • 传递控制。要进入Q时，程序计数器PC必须设置为Q的第一条指令地址，返回时要能够设置为P的调用处下一条指令地址。
  • 传递数据。P要能对Q传递参数，而Q要能返回一个结果。
  • 分配、释放内存。在开始时，Q可能需要分配临时变量的空间，随后返回时释放它们。

为了满足上述的规定，C里面采用了一种特殊的结构来满足——运行时栈帧。

栈结构

栈是一个很经典的结构，它可以视为一个FILO(First in Last out)结构，每一次的栈操作一般来说都是采用了经典的 push/pop 操作。巧妙地是，由于栈平衡地需要，往往push/pop都是呈现对称性，它们一般都会成对出现。x86-64结构下，在P调用Q时，前六个参数一般通过寄存器传递，其他的参数往往需要通过栈的帮助。在调用Q的最后一步，我们一般会看到 call 这个指令，这个指令其实执行了两个操作，把返回地址压栈和跳转目标地址。一般来说，我们以返回地址为界，上面的叫做P的栈帧，下方的是Q的栈帧。到此为止，我们就看到了栈这个结构是如何帮助我们在进行层层嵌套的调用时，如何保持向上追溯和返回的能力。栈里面如果往上看，你就能看到直到当前执行函数的调用路径。这也是我们在进行调试时的一个重要能力。

参考链接

  1. 打孔卡 https://zh.wikipedia.org/wiki/%E6%89%93%E5%AD%94%E5%8D%A1 ↩

  2. 参考手册 https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html ↩

  3. 通用寄存器 https://math.hws.edu/eck/cs220/f22/registers.html ↩

  4. 指令集 https://zhuanlan.zhihu.com/p/411300340 ↩

CS:APP
读书笔记
This post is licensed under CC BY 4.0 by the author.