编译、目标文件与静态链接
从源代码到可执行文件
几乎所有程序员在入门时都编写过如下的Hello Word程序
#include <stdio.h>
int main(){
printf("Hello World!\n");
return 0;
}
然后使用如下命令
gcc hello.c -o hello
我们就得到了可以执行的hello程序，执行它将在终端屏幕上输出一行"Hello World"。
事实上，上述命令执行包含了4个步骤，分别是预处理（Preprocessing），编译（Compiling），汇编（Assembly）与链接（Linking）。
预处理
预处理过程主要处理源代码中以#开头的预处理指令，通常包括以下部分：
- 将所有的#define语句移除，并将对应宏定义展开
- 处理#ifdef 等条件编译指令
- 将#include引入的文件插入到对应的位置，替代原来的#include指令
- 移除注释，添加调试信息如行号等。
- 对于所有的#pragma编译器指令，则会保留。
使用gcc -E hello.c -i hello.i可以将上述hello.c的预处理结果输出到hello.i文件中。预处理后的文件变成了732行，原来的#include已经被替换为stdio.h的内容（会比实际上的stdio.h少一些，因为注释被去除掉了）。以#开头的部分是行号和文件标识。
# 1 "hello.c"
# 1 "<built-in>"
# 1 "<command-line>"
...
# 3 "hello.c"
int main(){
printf("Hello World!\n");
return 0;
}
预处理完成之后的文件中不再包含宏定义（都被展开了），include的文件也被递归地插入到了对应的位置。
编译
使用gcc -S hello.i -o hello.s可以单独执行编译的过程。
编译分为如下几个步骤：
词法分析
通过类似于有限状态机（FSM）的算法，将输入的文本分割成一系列的token，并分类保存以供后续使用。词法分析得到的记号一般可以分为如下几类：关键字、标识符、字面量（数字/字符串）、特殊符号等。
通过lex程序，我们可以将读入一个定义好的词法规则，并生成词法分析的C语言程序。
语法分析
语法分析是通过”上下文无关文法“来生成一个语法树。上下文无关的含义是形如A->α这样的规则，其中的A总是可以用α来替换而无需考虑A出现的上下文。通过yacc程序可以根据规则来产生语法解析器（Parser）。
一个语法树的例子，它表示的是array[index] = (index + 4) * (2+6)这样一条语句：
语义分析
语法分析后得到的语法树是不包含类型的，它无法判断一个语句是否有意义。例如对于一个整型变量a取下标操作就是没有意义的，但是语法上a[index]是合法的。
语义包含静态语义和动态语义，编译器所能分析的是静态语义。语义分析会为所有的表达式进行类型标注，并为有需要的地方添加隐式类型转换。
中间代码生成与优化
到中间代码生成的部分通常都被称为编译器的前端。中间代码生成会生成一些平台无关的中间代码，并对其进行平台无关的代码优化。
一种典型的中间代码是三地址码，即所有的语句都被表示为 y = a op b的形式。
例如array[index] = (index + 4) * (2+6)就可以生成如下的三地址码：
t2 = index + 4
t2 = t2 * 8
arr[index] = t2
// 这个例子的三地址码已经优化过了，可以看到这一表现形式与汇编代码很相似
目标代码生成与优化
编译器后端例如LLVM可以将中间代码转换为具体机器上的目标代码。不同平台的字长，寄存器情况，支持的指令都不相同，所以这一过程与目标机器平台强相关。
经过编译阶段后，我们将得到目标程序的汇编代码描述：
.file "hello.c"
.text
.section .rodata
.LC0:
.string "Hello World!"
.text
.globl main
.type main, @function
main:
.LFB0:
.cfi_startproc
endbr64
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
... ...
汇编
使用gcc -c hello.s -o hello.o可以执行汇编的步骤。汇编会将汇编代码转换成汇编指令，并生成ELF格式的目标文件。汇编过程不需要进行优化，只需要一一对应地将汇编代码翻译成机器指令即可。
汇编过程得到的ELF文件的文件类型将会是REL（Relocatable file），它无法直接执行。
链接
深入了解链接步骤必须要先了解ELF文件格式。但大致上可以将链接（静态链接）分为如下几个过程：
- 地址和空间分配
- 符号决议（强符号、弱符号）
- 重定位，修正指令中所用到的外部符号的地址。
此外，动态链接基本上可以认为是将链接的过程推迟到运行时进行，可以节省空间但是加载运行速度会比较慢。
目标文件格式
目标文件与目标文件格式
编译器编译后，进行链接前的文件称为目标文件。如linux平台下gcc产生的xx.o文件，或者Winddows平台下msvc产生的xx.obj文件都属于目标文件。尽管linux目标文件格式ELF（Executable Linkable Format）和Windows目标文件格式PE（Portable Executable）格式不同，但它们都起源于早期Unix系统中所使用的COFF格式。
在Linux下，目标文件（可重定位文件）都是ELF格式，但ELF格式并不只有目标文件。链接器完成链接后的可执行文件也是ELF格式。此外，共享目标文件（Shared Object File）如xxx.so和核心转储文件（core dump）都使用ELF文件格式。
ELF文件头
在linux系统下，使用man elf命令可以查看详细的文档，如果要在程序中使用，可以引入elf.h头文件。
linux manual对于ELF的描述如下：
An executable file using the ELF file format consists of an ELF header, followed by a program header table or a section header table, or both. The ELF header is always at offset zero of the file. The program header table and the section header table's offset in the file are defined in the ELF header. The two tables describe the rest of the particularities of the file.
即ELF文件总是由一个elf文件头开始，紧跟着一个program header表或者section header表，或者两者都有。这两个表描述了整个elf文件的其它属性。
typedef struct {
unsigned char e_ident[EI_NIDENT];
uint16_t e_type;
uint16_t e_machine;
uint32_t e_version;
ElfN_Addr e_entry;
ElfN_Off e_phoff;
ElfN_Off e_shoff;
uint32_t e_flags;
uint16_t e_ehsize;
uint16_t e_phentsize;
uint16_t e_phnum;
uint16_t e_shentsize;
uint16_t e_shnum;
uint16_t e_shstrndx;
} ElfN_Ehdr;
其中有几个值得关注的属性：
-
e_entry
如果当前elf是个可执行文件，那么它表示程序入口地址。
-
esh_off、e_shnum、e_shentsize
这三个值分别表示section header在文件中的偏移，section header数量和每个section header的大小。
通过这三个值，就可以读取到一个section header的数组。而section header中保存了每个段相关的信息，包括段名，段在文件中的偏移量和大小等。下面是section header的格式：
typedef struct { uint32_t sh_name; //段名，所有字符串被保存在shstrtab段中，这里保存的是段名字符串在shstr段的偏移量。 uint32_t sh_type; uint64_t sh_flags; Elf64_Addr sh_addr; Elf64_Off sh_offset; uint64_t sh_size; uint32_t sh_link; uint32_t sh_info; uint64_t sh_addralign; uint64_t sh_entsize; } Elf64_Shdr; -
ph_off、e_phentsize、e_phnum
这三个值用来表示Program header的位置和属性。Program Header 表仅对于可执行文件或者共享库文件（xxx.so）有意义。
它包含了关于段如何加载到内存中的相关信息。要将一个可执行文件加载到内存并开始运行，只需要读取所有的program header并加载对应段到内存，就可以从e_entry指定的入口位置执行该程序了。
program header的结构如下所示：
typedef struct { uint32_t p_type; // 如果是PT_LOAD，表示该段可加载到内存，具体由下面对vaddr等属性描述。 uint32_t p_flags; Elf64_Off p_offset; // 在文件中的偏移量 Elf64_Addr p_vaddr; // 虚拟地址 Elf64_Addr p_paddr; // 物理地址，在BSD系的系统中通常为0。 uint64_t p_filesz; // 在文件中的大小 uint64_t p_memsz; // 在内存中的大小 uint64_t p_align; } Elf64_Phdr;
以一个hello可执行文件为例，使用readelf -h hello可以得到如下信息。
user@UBUNTU:~$ readelf hello -h
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
Program Header和Section Header分别对应于ELF文件的两种View：
- program header所描述的execution view（用于加载运行）
- section headers所描述的linking view（用于链接）。
ELF文件中的段
示例：
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
[ 0] NULL 0000000000000000 00000000
0000000000000000 0000000000000000 0 0 0
[ 1] .text PROGBITS 0000000000000000 00000040
000000000000001b 0000000000000000 AX 0 0 1
[ 2] .rela.text RELA 0000000000000000 00000258
0000000000000030 0000000000000018 I 11 1 8
[ 3] .data PROGBITS 0000000000000000 0000005b
0000000000000000 0000000000000000 WA 0 0 1
[ 4] .bss NOBITS 0000000000000000 0000005b
0000000000000000 0000000000000000 WA 0 0 1
[ 5] .rodata PROGBITS 0000000000000000 0000005b
000000000000000d 0000000000000000 A 0 0 1
[ 6] .comment PROGBITS 0000000000000000 00000068
000000000000002a 0000000000000001 MS 0 0 1
[ 7] .note.GNU-stack PROGBITS 0000000000000000 00000092
0000000000000000 0000000000000000 0 0 1
[ 8] .note.gnu.propert NOTE 0000000000000000 00000098
0000000000000020 0000000000000000 A 0 0 8
[ 9] .eh_frame PROGBITS 0000000000000000 000000b8
0000000000000038 0000000000000000 A 0 0 8
[10] .rela.eh_frame RELA 0000000000000000 00000288
0000000000000018 0000000000000018 I 11 9 8
[11] .symtab SYMTAB 0000000000000000 000000f0
0000000000000138 0000000000000018 12 10 8
[12] .strtab STRTAB 0000000000000000 00000228
0000000000000029 0000000000000000 0 0 1
[13] .shstrtab STRTAB 0000000000000000 000002a0
0000000000000074 0000000000000000 0 0 1
通过读取ELF文件的section header可以得到文件中包含哪些section。其中包含程序代码和数据的有：
-
.text 段
保存代码。
-
.data 段 / .rodata段
有非零初值的全局变量和static local变量。
-
.bss段
未初始化的全局变量/static local变量。
其它一些段和用途：
-
.comment
编译器版本信息
-
.debug
调试信息
-
.symtab
符号表
-
.rel.text
.text段的重定位表，用于链接期间对.text段的符号进行重定位
-
.strtab
ELF中用到的字符串表，例如符号名字符串会保存在这里。
系统保留的段通常会用.作为开头，用户也可以自定义一些段（例如可以将一段mp3音频数据保存到某个自定义段中）。
符号表与符号
ELF中一个重要的section是symtab。它是一个由Sym结构体组成的数组。
typedef struct {
uint32_t st_name; // 符号名字符串在strtab中的offset。
unsigned char st_info; // 低4位表示符号类型：数据/函数，高28位表示局部/全局/弱引用等。
unsigned char st_other;
uint16_t st_shndx; // 段索引
Elf64_Addr st_value; // 表示符号在段中的偏移
uint64_t st_size; // 符号所代表对象的大小
} Elf64_Sym;
符号表中包含了所有的符号信息。使用readelf -s hello 可以查看符号表：
Symbol table '.symtab' contains 65 entries:
Num: Value Size Type Bind Vis Ndx Name
...
58: 0000000000004018 0 NOTYPE GLOBAL DEFAULT 26 _end
59: 0000000000001060 47 FUNC GLOBAL DEFAULT 16 _start
60: 0000000000004010 0 NOTYPE GLOBAL DEFAULT 26 __bss_start
61: 0000000000001149 27 FUNC GLOBAL DEFAULT 16 main
如上所示，main符号表示的是一个全局函数，位于第16个section，在段中的偏移为0x1149，size为27。
C++与符号修饰
我们知道C++中有一个用于兼容C语言的关键字extern
extern "C"{
some code;
}
这是因为C++编译出来的代码，其elf文件中的符号名称与我们定义的符号名称是不一样的。C++支持命名空间与函数的重载，这意味着一个函数不能仅通过其名字来确定，还需要命名空间信息和参数类型信息，因此C++编译过程中会进行符号修饰。而C语言不支持重载，通常在二进制文件中的符号名称与源文件中定义的符号是一致的。
void C::func(int);
如上这样一个函数，在经过C++的符号修饰后，其对应的符号名字为"_ZN1C4funcEi"，即以_Z 开头，然后N...E中间的是各级名称，最后是参数列表。这些名字会以一个数字开头，表示名字的长度，后面的就是对应长度的字符串。
强符号与弱符号，强引用与弱引用
默认情况下，在一个源文件中声明的全局符号，如果有定义就是强符号，如果没有定义就是弱符号。
int strong_symbol = 42;
double weak_symbol ;
在链接的过程中，如果多个文件中有相同符号，会根据如下规则进行“符号决议”：
-
存在多个强符号
链接器会报错，无法完成链接。
-
存在一个强符号，多个弱符号
最终会选择强符号的定义，如果某个弱符号的类型大小比强符号要大，会给出warning提示。
-
存在多个弱符号
选择这些弱符号中，占用空间大小最大的一个。尽管不会报错，但这样很容易造成bug。
当然，除了默认情况，也可以使手动指定一个符号为弱符号/强符号。
//使用#pragma
// function declaration
#pragma weak power2
int power2(int x);
//使用__attribute__((weak))
// function declaration
int __attribute__((weak)) power2(int x);
// or
int power2(int x) __attribute__((weak));
// variable declaration;
extern int __attribute__((weak)) global_var;
手动指定弱符号的用处在于，如果需要编写一个库函数，并且希望用户可以方便地覆盖其实现，就可以使用弱符号声明。这样当用户没有指定自定义的实现时，就会调用库提供的实现，而如果用户对该符号进行了定义，就会覆盖掉库中的实现。
强引用与弱引用指的则是另一种情况：
对于一个函数声明，如果将其声明为弱引用，即便其实现不存在，那么在链接过程中也不会报错。
void foo() __attribute__((weak)) ;
int main(){
foo();
}
上述例子不会报undefined_reference错误，而是会出现运行时异常，因为foo指向的函数调用地址是0。
而如果只声明一个void foo();那么在链接时就会报错。
用途是可以判断是否链接到了某些库，例如定义一个pthread_create函数的弱引用，就可以在运行时判断该符号是否为NULL而确定是否链接到了多线程库pthread，从而执行相应的操作。
静态链接
静态链接基本上就是将多个目标文件合并成一个可执行文件，一个简单的例子：
# a.c 文件
extern int shared;
int main(){
int a = 100;
swap(&a, &shared);
}
# b.c 文件
int shared = 1;
void swap(int* a, int * b){
*a ^= *b ^= *a ^= *b;
}
将这两个文件分别编译后可以得到a.o和b.o，经过链接后可以合并为一个可执行文件。
合并目标文件
通过对ELF文件的分析，可以了解到目标文件中是以段的形式保存数据和代码的。如果要将多个目标文件合并，最简单的想法就是将所有的段都保存到输出文件中，当然这种做法会产生大量的段，会造成碎片和空间浪费。
通常的做法是将多个目标文件中相同性质的段合并到一起，例如将所有的.text段合并到输出文件的.text段中。那么这一过程可以分为两个步骤：
空间与地址分配
扫描所有目标文件，得到所有段的长度和位置。将相似的段合并的一起，可以计算出合并段的大小，然后建立原来的段到合并段的映射。
符号解析与重定位
根据原有段到合并段的映射，以及重定位表的信息，对输出文件中的地址进行调整。
一些相关概念：
-
重定位
指令中如果包含了外部符号地址，在链接阶段前将会以0替代。而链接器会在链接阶段修正这一地址。
-
重定位表
链接器通过ELF文件中的重定位表来确定需要进行重定位的对象。
-
符号解析
如果引用了外部符号，那么当前目标文件符号表中会将其标注为Undefined。链接器会在其它输入文件中寻找该符号的定义。
-
指令地址修正
一条指令的寻址可能是绝对寻址，也可能是相对寻址（相对当前指令地址），链接器会根据实际情况进行寻址修正。
common块的概念
COMMON块起源于Fortran程序，早期的Fortran程序不支持动态内存分配，需要程序员指出可能使用的临时空间的大小，这部分空间称为common块，当多个目标文件使用的common块大小不一致时，以最大的为准。
当前的链接器使用类似的方式处理多个弱符号的情况，弱符号会被标记为COMMON类型，而强符号不会。
链接器在选择弱符号时无法处理符号的类型，只能根据大小来判断，即多个弱符号同时存在时，会以占用空间最大的为标准。在最终的输出文件中，会在.bss段为该符号分配存储空间。
链接阶段中C++程序的一些问题
重复代码消除与函数级别链接
有以下几种情况在不同的编译单元（目标文件）中产生重复的代码：
-
模板实例化
模板本身是无法知道自身被实例化的情况的，多个目标文件中可能实例化了相同的模板，这样就会在多个目标文件中产生相同的代码。
-
外部内联函数
extern inline函数会在调用处展开为代码，因此会无法找到该函数的入口。
即可以在代码中调用这些函数，但是想要取地址时就会报undefined reference的链接错误。
-
虚函数表
如果保留所有重复的代码，那么除了占用空间变多、效率变低之外，还有可能出现指向同一个函数的指针不一样的情况，所以必须要消除这些重复代码。
以模板函数为例，一个有效的解决方案是将该模板实例的代码单独存放到一个段里面。那么在不同的目标文件中会生成相同的段，这样只需要识别这些相同的段并在最终输出文件中只保留一份即可。gcc的做法是把这种在最终链接时合并的段称作“Link Once"，并命名为"gnu.linkonce.$name"，这样就可以消除掉重复代码。
函数级别链接则是指的像glibc这样的库，它们会包含大量的函数和变量，但是最终被使用的可能只有一小部分。如果将每一个函数和变量都保存到单独的段里面，就可以将未使用的段在链接阶段丢弃，减小最终输出文件的大小。可以通过gcc的编译选项-ffunction-sections和-fdata-sections来是的每个函数/变量都保存到目标文件中单独的段。
全局变量的构造与析构
实际上main函数并不是一个程序中最早被执行的函数，C++中会在main函数之前执行所有全局对象的构造，并在main函数返回后进行全局对象的析构。
Linux系统下程序的入口通常是glibc提供的_start函数，它会执行相关的初始化操作，然后调用main函数，并在main函数返回后进行一些清理工作。编译器会把全局变量的构造和析构分别放到ELF文件的.init段和.fini段，_start函数负责执行这部分代码。
二进制应用接口（ABI，Application Binary Interface）
如果要让两个不同的目标文件互相兼容，那么至少需要它们的符号修饰规则相同，变量内存布局相同，函数调用方式相同，寄存器使用约定相同，虚函数处理方式相同等等。
不同编译器编译的二进制文件可能不兼容，同一个编译器的不同版本也可能不兼容。尽管从源代码重新编译可以解决兼容性的问题，但是有些情况下不得不使用厂商提供的闭源库。早期*NIX平台下的ABI规范非常混乱，不过就目前来说，基本上分为了微软为首的VC++规范和GNU阵营的GCC规范两种情况。
静态库链接
最经典的helloword程序会输出一行”Hello World!"到终端，那么这一过程是如何完成的呢？
向终端输出文字这一操作最终是通过操作系统的系统调用实现的，例如linux下的write系统调用或windows下的WriteConsole系统调用。而printf函数则是由标准库提供的对系统调用的包装。glibc提供的库文件通常位于/usr/lib/libc.a，使用ar -t libc.a可以看到它是由多个目标文件打包而成的。这些目标文件通常只包含一个函数，目的是减少链接最终文件的大小。
链接过程控制
多数情况下，可以使用默认规则进行链接。但以下一些情况可能需要特殊的链接规则控制：
- 操作系统内核
- Bootloader
- 一些嵌入式程序
- 可以脱离操作系统运行的硬盘分区程序
- ...
使用命令行进行链接控制
以一个“最小的helloword”程序作为例子：
char *str = "Hello World!n";
void print(){
asm("movl $13, %%edx\n\t"
"movl %0, %%ecx \n\t"
"movl $0, %%ebx \n\t"
"movl $4, %%eax \n\t"
"int $0x80 \n\t"
::"r"(str): "edx","ecx","ebx"
);
}
void exit(){
asm("movl $42, %ebx \n\t"
"movl $1, %eax \n\t"
"int $0x80 \n\t"
);
}
void nomain(){
print();
exit();
}
以上代码中的print和exit函数分别使用汇编进行了write（系统调用号4）和exit（系统调用号1）系统调用。
如果要执行上述程序，需要特殊的链接控制：
gcc -c fno-builtin hello.c
ld -static -e nomain -o hello hello.o
通过以上链接过程，会得到4个段：.text代码段、.rodata段（保存了字符串的内容）、.data段保存了str指针、.comment保存了编译器版本等信息。这些数据都没有发生改变，理论上可以合并到一个只读段，这一需求用ld脚本就可以实现。
ld脚本进行链接控制
ENTRY(nomain)
SECTIONS(
. = 0x08048000 + SIZEOF_HEADERS;
tinytext : {*(.text) *(.data) *(.rodata)}
/DISCARD/ : {*(.comment)}
)
上述脚本将nomain设置为程序入口，然后把当前虚拟地址设置为0x08048000 + SIZEOF_HEADERS，再将.text段、.data段和.rodata段合并到tinytext段，丢弃.comment段。
在使用.lds链接脚本时，通常需要在构建命令中指定它的位置，比如：
Copy code
$ gcc -T <script_file>.lds <object_files> -o <executable_file>
上面的命令会使用指定的.lds链接脚本文件进行链接，并将链接结果存储到指定的可执行文件中。
.lds链接脚本文件通常包含以下几个部分：
- 头部：定义链接器的版本信息和全局变量等。
- 段定义：定义内存段的名称、起始地址、长度等信息。
- 节定义：定义内存段中的节，比如数据段、代码段等。
- 规则定义：定义链接器如何处理各个段和节之间的关系。
- 段属性定义：定义各个段的属性，比如可读性、可执行性等。