编译、汇编、链接、执行：from code to process

编译的四步

我们一般说的编译实际上是包含了四个步骤的，即预编译、编译、汇编和链接。比如如果用 gcc 而不加任何其他参数，那么从 a.c 到生成 a.out 的过程中实际上就一次性完成了这四步。

预编译

预编译的过程很简单，就是处理所有的预处理指令，包括宏定义、条件编译指令和 #inlcude 这些。 比如如果我们有这样一个简单的程序：

#include <stdio.h>

int main() {
    printf("Hello, World!\n");
    return 0;
}

那么预编译阶段就会直接展开 #include 语句，把 stdio 这个头文件全部插入到当前文件里面。

这个过程是完全隐式的，不会生成任何的可见文件。如果要看可以用 gcc -E 来仅进行预编译，并把结果打到 stdout 里。

编译

编译当然是这四部里面最重要也最复杂的一步，其中包含了非常多的子步骤，即词法分析、语法分析、语义分析、中间代码生成、代码优化等。

词法分析

在词法分析 (Lexical Analysis) 的过程中，词法分析器 (Lexer) 会将 source code 转换成一系列的 tokens。这时候会移除其中的空格、换行、注释等元素，仅留下有意义的符号，比如关键字、变量名等。

比如代码 int main() { return 0; } 会被分解成 int , main , ( , ) , { , return , 0 , } , ; 这几个 token。

语法分析

然后进入语法分析 (Syntax Analysis) 的阶段，我们一般也称这一步叫 parse。语法分析器 (Parser) 会接收 Lexer 的结果，并根据语言的语法规则构造一个抽象语法树 (AST)。

比如对于上面这段简单的代码，生成的 AST 可能是长这样的：

	Program
	   |
	Function
       /        \
      /         Body
     /        /      \
"int main"  Call    Return
	      |       |
	   "printf"  "0"
	      |
	"Hello, World!\n"

语义分析

然后会对 AST 进行语义分析 (Semantic Analysis)，一般包括类型检查、作用域规则、函数定义与调用、赋值等。

比如对于我们的这个 AST，它可能首先会检查 main 函数的返回类型是否符合 C 语言标准，然后可能会检查 printf 这个函数调用的参数类型是否正确，同时也会检查 printf 是在 main 的作用域之内。另外，虽然这个例子中没有赋值的操作，但是最后 return 了一个 integer 0，编译器也会检查这个类型和函数返回类型是否匹配。

这一步结束后会得到一个增强过的 AST，可能会多带上一些类型信息、绑定信息等。比如 return 0 中的 0 会被标注是 int 类型，而 printf 会被会被绑定到其在 stdio.h 中的声明。 同时，如果这一步里面有什么问题，当然也会得到 warning 和 eror 。

中间代码生成和代码优化

之后 AST 会被转换成一种中间表示 (Intermediate Representation, IR)，IR 一般是被设计成与具体的程序语言、机器无关的，这样可以让编译器支持多种语言。同时 IR 一般也是易于进行分析和优化的，便于编译器去实现各种优化技术，比如代码消除、循环优化等。

一个最简单的代码优化的例子就是对于循环的优化，比如有这样一段代码：

int i;
int n = 10;
int a = 5;
int b = 6;
int array[10];

for (i = 0; i < n; i++) {
    array[i] = a * b + i;
}

在这个循环中， a * b 的结果在每一次循环中都是一样的，与 i 的值无关，所以就可以把这个结果提取出来。相当于优化成这样：

int i;
int n = 10;
int a = 5;
int b = 6;
int array[10];
int temp = a * b;

for (i = 0; i < n; i++) {
    array[i] = temp + i;
}

当然因为代码优化是对 IR 来做的，所以实际上没有这样可读的代码生成，只是 IR 的逻辑相当于这样。

目标代码生成

随后 IR 就会被转换成汇编代码。以开头的那个简单的 C 语言片段为例，生成的汇编代码可能类似这样：

.section	.rodata
.LC0:
	.string	"Hello, World!\n"
	.text
	.globl	main
	.type	main, @function
main:
	pushq	%rbp
	movq	%rsp, %rbp
	leaq	.LC0(%rip), %rdi
	call	puts
	movl	$0, %eax
	popq	%rbp
	ret

在这一步中涉及到了寄存器如何分配、指令如何调度和代码布局，这些都比较影响程序的执行效率。

因为寄存器的访问速度是远快于内存的，所以如果能尽可能将频繁访问的变量放在寄存器里面，就能大大提高整体的访问速度。而合理排布指令的执行顺序可以减少处理器的等待时间，主要是避免对数据的依赖造成的阻塞。

代码布局决定了程序的各个部分如何在内存中分布，因为现代 CPU 的分支预测机制倾向于预测接下来的执行路径将会继续顺序执行，而不是跳转，所以将概率更高的分支放在顺序执行里面运行效率会更高。所以对于分支理想的话会形成这样子的汇编代码，即 near_branch 顺序执行， far_branch 通过跳转来执行：

cmp eax, 1
je near_branch
jmp far_branch
near_branch:
    ; high frequency
    jmp continue_execution
far_branch:
    ; low frequency
    continue_execution:

至此就完成了编译的环节，得到了汇编代码，一般会存在一个 .s 或者 .asm 文件里面。

汇编

汇编这一步是相对比较简单的，这个词的字面意思就是很机械地去一一对应，也就是查表然后固定将一条汇编代码转换成二进制。

比如一条简单的汇编代码，将数字 1 移动到 AX 寄存器里面

MOV AX, 1

在 x86 和 small endian 下就应该永远对应这样的二进制形式

B8 01 00

其中 B8 是操作码，表示 MOV AX, immediate ，而 01 00 是 1 的 16 位表示。

完成汇编之后就会生成 object file，一般是 .obj 或者 .o 。

ELF 文件

不像之前的 C 源代码、汇编代码文件，到这里 object file 就已经是 binary 了，也就是说不再是 plain text 了，所以就需要了解一下 object file 的格式，看一下它到底包含了什么东西。

在 Unix 上，包括 object file 在内的所有 binary 的格式都是 ELF (Executable and Linkable Format)，ELF 除了 object file 之外还有 shared object file (.so) 和真正的可执行文件，比如 /bin/bash 。

ELF 文件的一开始是一个 ELF Header，包含了关于这个 ELF 的各种 metadata。比如一上来的是 magicn umber，指示了这个文件是一个 ELF (45 4c 46 就是 ELF 三个字母的 ASCII， 7f 是从历史原因从 PDP-11 流传下来的开头)，然后还有 ELF 的 version, ABI 的 version 等等信息。比如上面那个简单程序的 ELF header 信息：

$ readelf -h hello
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              DYN (Shared object file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x1060
  Start of program headers:          64 (bytes into file)
  Start of section headers:          14712 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         13
  Size of section headers:           64 (bytes)
  Number of section headers:         31
  Section header string table index: 30

ELF 的主体实际上是很多个 section，所以其实可以把 ELF 就简单理解成是对 binary 的通用容器，具体要有什么样的信息，可以在不同的 section 里面去自己定义。所以 ELF 中还有一个部分是对于这些 sections 的目录，这就是 Section Header Table。

最重要和常见的 section 有这几个：

• text，程序的执行代码
• data，已经初始化的全局变量和静态变量
• bss，未初始化的全局变量和静态变量
• rodata，只读数据，比如字符串常量和其他常量
• symtab，符号表，即程序中的函数、变量等符号信息

这几个 section 都是在经过了汇编之后就存在的，但是静态链接时部分可能还会进行一些修改。

如果 ELF 是一个可执行文件的话还会有一个 Program Header Table，供了将程序或者系统的不同部分加载到内存中所需的信息。

所以总体上 ELF 的结构是这样的：

ELF Header
Program Header Table (Optional)
.text	(Section)
.rodata	(Section)
…	(Section)
.data	(Section)
Section Header Table

静态链接

完成汇编的过程之后就已经有了一系列的 ELF 格式的 object file，这时候还需要静态链接把多个 object file 中符号的定义统一起来，因为比如非常常见的可能就是一个 function 是在另一个文件中被定义的。

为了完成这样的统一，链接器 (linker) 需要先解析出所有的符号（变量名、函数名等各种标识符），从而在全局的层面掌握这些符号的定义和应用情况，然后就可以将对函数的调用指向对函数的定义。

为了最终正确的地址指向，linker 实际上需要为这些所有的 ELF 里面的内容去分配一个统一的地址空间。因为各个 ELF 自己是单独为自己的 section 来编地址的，所以大部分统一后的地址都是和原先不一致的，如果链接前的 ELF 中有一些对于变量或函数地址的直接引用（比如通过指针），那么 linker 也就需要去修正这些引用，让它们指向修改后的地址。实际上原先的 ELF 中就是会带一个 relocation table 的，linker 可以直接根据这个 relocation table 来进行修正。

在分配这个地址时也会发生对于 section 的合并。因为静态链接的结果生成的 bianry 的容器仍然是 ELF，因此实际上格式和之前是类似的。比如 text section 不会有好几个，仍然只会留有一个，因此不同的 object file 的 text section 在静态链接只后的 ELF 中就会被合并到一个 text section 里面去。

装载

装载的过程就是 loader 把 ELF 的内容移动到内存里。

在装载的过程中，loader 会以一个不一样的视角去看待 ELF 文件，不再是看成一个个的 sections，而是一个个的 segments，一般前者被称为 linking view，后者被成为 execution view。在 execution view 下，关注的主要是内容所需要的权限的区别，因此 load 完会形成这样的几个主要的 segment: .text, .data 和 .bss 。 .text 一般会和 .rodata 放在一起形成一个只读的内存区域，这样可以有效防止程序在运行过程中代码被修改。而 .data 和 .bss 这部分当然就需要是可读写的，但是不同的是 .bss 在 load 的时候就会全部置零，用来存储未初始化的全局变量。

除了把 ELF 的内容装载到内存，在程序初始化的时候 OS 还会为其分配 Stack 和 Heap 两段地址空间。Stack 就是用来存储函数参数、返回地址、局部变量这些信息，也就是说每当发生函数调用，其 metadata 就会由这个 Stack 来保存。从应用开发者的角度来说，Stack 是不应该被直接访问或者管理的。

真正应用开发者会进行手动管理的部分是 Heap，比如每次用 malloc 分配出来的内存就是在 Heap 里面。原理上来说内存分配应该完全是 kernel 做的事情，所以每次进行内存分配都是需要调用 syscall (比如 mmap 和 brk) 的，所以为了更高效可能是运行库 (libc) 会去「批发」一块大的内存，然后再「零售」给真正需要使用的地方。