参考自：This is an http://www.xuebuyuan.com/1730287.html
一、程序编译链接的整体流程
通常我们使用gcc来生成可执行程序，命令为：gcc hello.c，默认生成可执行文件a.out
其实编译（包括链接）的命令：gcc hello.c 可分解为如下4个大的步骤：
预处理(Preprocessing)
编译(Compilation)
汇编(Assembly)
链接(Linking)
gcc compilation
1. 预处理(Preproceessing)
预处理的过程主要处理包括以下过程：
将所有的#define删除，并且展开所有的宏定义
处理所有的条件预编译指令，比如#if #ifdef #elif #else #endif等
处理#include 预编译指令，将被包含的文件插入到该预编译指令的位置。
删除所有注释 “//”和”/* */”.
添加行号和文件标识，以便编译时产生调试用的行号及编译错误警告行号。
保留所有的#pragma编译器指令，因为编译器需要使用它们
通常使用以下命令来进行预处理：
gcc -E hello.c -o hello.i
参数-E表示只进行预处理 或者也可以使用以下指令完成预处理过程
cpp hello.c > hello.i / cpp – The C Preprocessor /
直接cat hello.i 你就可以看到预处理后的代码
2. 编译(Compilation)
编译过程就是把预处理完的文件进行一系列的词法分析，语法分析，语义分析及优化后生成相应的汇编代码。
$gcc –S hello.i –o hello.s
或者
$ /usr/lib/gcc/i486-linux-gnu/4.4/cc1 hello.c
注：现在版本的GCC把预处理和编译两个步骤合成一个步骤，用cc1工具来完成。gcc其实是后台程序的一些包装，根据不同参数去调用其他的实际处理程序，比如：预编译编译程序cc1、汇编器as、连接器ld
3. 汇编(Assembly)
汇编器是将汇编代码转变成机器可以执行的命令，每一个汇编语句几乎都对应一条机器指令。汇编相对于编译过程比较简单，根据汇编指令和机器指令的对照表一一翻译即可。
$ gcc –c hello.c –o hello.o
或者
$ as hello.s –o hello.co
由于hello.o的内容为机器码，不能以普通文本形式的查看（vi 打开看到的是乱码）。
4. 链接(Linking)
通过调用链接器ld来链接程序运行需要的一大堆目标文件，以及所依赖的其它库文件，最后生成可执行文件。
ld -static crt1.o crti.o crtbeginT.o hello.o -start-group -lgcc -lgcc_eh -lc-end-group crtend.o crtn.o (省略了文件的路径名)。
helloworld的大体编译和链接过程就是这样了，那么编译器和链接器到底做了什么呢？
编译过程可分为6步：扫描（词法分析）、语法分析、语义分析、源代码优化、代码生成、目标代码优化。
词法分析：扫描器（Scanner）将源代的字符序列分割成一系列的记号（Token）。lex工具可实现词法扫描。
语法分析：语法分析器将记号（Token）产生语法树（Syntax Tree）。yacc工具可实现语法分析(yacc: Yet Another Compiler Compiler)。
语义分析：静态语义（在编译器可以确定的语义）、动态语义（只能在运行期才能确定的语义）。
源代码优化：源代码优化器(Source Code Optimizer)，将整个语法书转化为中间代码（Intermediate Code）（中间代码是与目标机器和运行环境无关的）。中间代码使得编译器被分为前端和后端。编译器前端负责产生机器无关的中间代码；编译器后端将中间代码转化为目标机器代码。
目标代码生成：代码生成器(Code Generator).
目标代码优化：目标代码优化器(Target Code Optimizer)。
链接的主要内容是把各个模块之间相互引用的部分处理好，使得各个模块之间能够正确地衔接。
链接的主要过程包括：地址和空间分配（Address and Storage Allocation），符号决议（Symbol Resolution），重定位（Relocation）等。
链接分为静态链接和动态链接。
静态链接是指在编译阶段直接把静态库加入到可执行文件中去，这样可执行文件会比较大。
而动态链接则是指链接阶段仅仅只加入一些描述信息，而程序执行时再从系统中把相应动态库加载到内存中去。
静态链接的大致过程如下图所示：
static linking
二、目标文件的样子（以linux下的elf文件格式为例）
夹在ELF头和节头部表之间的都是节。一个典型的ELF可重定位目标文件包含下面几个节：
.text：已编译程序的机器代码。
.rodata：只读数据，比如printf语句中的格式串和开关（switch）语句的跳转表。
.data：已初始化的全局C变量。局部C变量在运行时被保存在栈中，既不出现在.data中，也不出现在.bss节中。
.bss：未初始化的全局C变量。在目标文件中这个节不占据实际的空间，它仅仅是一个占位符。目标文件格式区分初始化和未初始化变量是为了空间效率在：在目标文件中，未初始化变量不需要占据任何实际的磁盘空间。
.symtab：一个符号表（symbol table），它存放在程序中被定义和引用的函数和全局变量（包括引用到的外部变量和函数，不含有局部变量）的信息。一些程序员错误地认为必须通过-g选项来编译一个程序，得到符号表信息。实际上，每个可重定位目标文件在.symtab中都有一张符号表。然而，和编译器中的符号表不同，.symtab符号表不包含局部变量的表目。
.rel.text：当链接噐把这个目标文件和其他文件结合时，.text节中的许多位置都需要修改。一般而言，任何调用外部函数或者引用全局变量（包括本目标文件内的全局变量，因为在链接时要多个目标文件的相同段合并，这样数据的地址就会改变，所以要重定位）的指令都需要修改。另一方面调用本地函数的指令则不需要修改。注意，可执行目标文件中并不需要重定位信息，因此通常省略，除非使用者显式地指示链接器包含这些信息。
.rel.data：被模块定义或引用的任何全局变量的信息。一般而言，任何已初始化全局变量的初始值是全局变量或者外部定义函数的地址都需要被修改。
.debug：一个调试符号表，其有些表目是程序中定义的局部变量和类型定义，有些表目是程序中定义和引用的全局变量，有些是原始的C源文件。只有以-g选项调用编译驱动程序时，才会得到这张表。
.line：原始C源程序中的行号和.text节中机器指令之间的映射。只有以-g选项调用编译驱动程序时，才会得到这张表。
.strtab：一个字符串表，其内容包括.symtab和.debug节中的符号表，以及节头部中的节名字。字符串表就是以null结尾的字符串序列。
旁注：为什么未初始化的数据称为.bss?
用术语.bss来表示未初始化的数据是很普遍的。它起始于IBM 704汇编语言（大约在1957年）中”块存储开始（Block Storage Start）“指令的首字母缩写，并沿用至今。一个记住区分.data和.bss节的简单方法是把“bss”看成是“更好地节省空间（Better Save Space）！“的缩写。
三、静态链接
虚拟存储器是建立在主存–辅存物理结构基础上，有附加的硬件装置及操作系统存储管理软件组成的一种存储体系。
顾名思义，虚拟存储器是虚拟的存储器，它其实是不存在的，而仅仅是由一些硬件和软件管理的一种“系统”。他提供了三个重要的能力：
1，它将主存看成一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据（这里存在“交换空间”以及“页面调度”等概念），通过这种方式，高效地利用主存；2，它为每个进程提供了统一的地址空间（以虚拟地址编址），从而简化了存储器管理；3，操作系统会为每个进程提供独立的地址空间，从而保护了每个进程的地址空间不被其他进程破坏。
虚拟存储器与虚拟地址空间是两个不同的概念：虚拟存储器是假想的存储器，而虚拟存储空间是假想的内存。它们之间的关系应该与主存储器与内存空间之间的关系类似。
链接部分：
链接就是将不同部分的代码和数据收集和组合成一个单一文件的过程，也就是把不同目标文件合并成最终可执行文件的过程。当然，务必知道：这个过程不涉及内存。
链接可以分为三种情形：
1，编译时链接，也就是我们常说的静态链接；
2，装载时链接；
3，运行时链接。装载时链接和运行时链接合称为动态链接。在此，我们的链接部分将主要讲述静态链接，而装载时链接我们放在装载部分讲，运行时链接忽略。
1、什么是静态链接？
静态链接就是将多个目标文件组合在一起形成一个可执行文件，如将a.o 和 b.o 链接在一起形成 可执行文件ab。
2、静态链接的过程包括哪几个部分？
静态链接包括两个大部分：一是空间和地址的分配；二是符号解析和重定位
####（1）空间和地址的分配
编译器在将a.o 和 b.o 是如何合并在一起的？？
第二种方法就是 相似段合并：顾名思义 就是把不同目标文件的相同名字的段合并成一个段，如下图：
图1
这是编译器实际进行合并目标文件的策略。
/*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”两个目标文件
§gcc -c a.c b.c
从代码中可以看到三个符号：share，swap和main。
静态链接的整个过程分为两步:
第一步：空间和地址分配。扫描所有的输入目标文件，获得他们的各个段的长度、属性和位置，并且将输入目标文件中的符号表中所有的符号定义和符号引用收集起来，统一放到一个全局符号表。这样，连接器将能够获得所有输入目标文件的段长度，并且将它们合并，计算出输出文件中各个段合并后的长度与位置，并建立映射关系。
这里可能会有一个问题：建立了什么样的映射关系。如上面的图1，你可能就会有所了解。映射关系就是指可执行文件与进程虚拟地址空间之间的映射。那么，这里程序还没有执行，更不会出现进程，哪里来的进程地址空间呢？此时虚拟存储器便发挥了很大的作用：虽然此时没有进程，但是每个进程的虚拟地址空间的格式都是一致的。所以，为可执行文件的每个段甚至每个符号符号分配地址也就不会有什么错了。注意：在链接之前，目标文件中的所有段的虚拟地址都是0，因为虚拟空间还没有被分配，默认都为0.等到链接之后，可执行文件中的各个段已经都被分配到了相应的虚拟地址
第二步：符号解析与重定位
首先，符号解析。解析符号就是将每个符号引用与它输入的可重定位目标文件中的符号表中的一个确定的符号定义联系起来。
若找不到，则出现编译时错误。
其次是重定位；
不同的处理器指令对于地址的格式和方式都不一样。我们这里采用的是32位的x86处理器，介绍两种寻址方式。
X86基本重定位类型
宏定义 值 重定位修正方法
R_386_32 1 绝对寻址修正S + A
R_386_PC32 2 相对寻址修正S + A - P
注：
A：保存在被修正位置的值，对于32位cpu的话，采用
R_386_PC32寻址的话
它应该为0xFFFFFFFC即-4，它是代表地址的四个字节；而采用
R_386_32寻址，它应该为0.
P：被修正的位置。考虑以下程序
…
1023: 11 11 11
1026:e8
fc
ff ff ff
102b: 11 11 11
…
上述蓝色fc标记处即是被修正的位置，即0x1027.
S：符号的实际地址。也就是第一步中空间和地址分配时得到的符号虚拟地址。
举例来说吧！链接成的可执行文件中，假设main函数的虚拟地址为0x1000，swap函数的虚拟地址为0x2000；shared变量的虚拟地址为0x3000;
绝对地址修正：对shared变量的地址修正。
l
S：shared的实际地址为0x3000；
l
A：被修正位置的值，即0.
所以最后这个重定位修正地址为：0x3000，不变！
相对寻址修正：对符号“swap”进行修正。
l
S：符号swap的实际地址，即0x2000；
l
A：被修正位置的值，即0xFFFFFFFC（-4）；
l
P：被修正位置，及0x1027
最后的重定位修正地址为：S + A -P = 0x2000 +（-4）- 0x1027 = 0xFD5.即修正后的程序为：
…
1023: 11 11 11
1026:e8
d5 0f 00 00
102b: 11 11 11
…
发现熟悉的规则了吗？下一条指令（PC）的地址为0x102b，加上这个修正值正好等于0x2000，
0x102b + 0xFD5 = 0x2000，刚好是swap函数的地址。
以上内容没有涉及到c标准库，仅仅是自己实现的两个c语言程序之间的链接状况，也就是“程序里面的printf怎么处理”没有说明。这里，我们就要提及“静态库”的概念。其实一个静态库可以简单地看成一组目标文件的集合，即很多目标文件经过压缩打包后形成的一个文件。与静态库链接的过程是这样的：ld链接器自动查找全局符号表，找到那些为决议的符号，然后查出它们所在的目标文件，将这些目标文件从静态库中“解压”出来，最终将它们链接在一起成为一个可执行文件。也就是说只有少数几个库和目标文件被链接入了最终的可执行文件，而非所有的库一股脑地被链接进了可执行文件。
四、装载：
以Linux内核装载ELF为例简述一下装载过程。当我们在Linux系统的bash下输入一个命令执行某个ELF程序时，在用户层面，bash进程会调用fork()系统调用创建一个新的进程，然后新的进程调用execve()来执行指定的ELF文件，原先的bash进程继续返回等待刚才启动时新进程结束，然后继续等待用户输入命令。这里需注意，随着一个新进程的出现，操作系统会为它创建一个独立的虚拟地址空间。
【创建虚拟地址空间】我们知道一个虚拟空间由一组映射函数将虚拟空间的各个页映射到相应的物理空间，那么创建一个虚拟空间实际上并不是创建空间而是创建映射函数所需要的数据结构。举例来说，在x86的Linux下创建虚拟地址空间实际上只是分配一个页目录（页表）就可以了，甚至不设置页映射关系，这些映射关系等到后面程序发生“缺页”时在进行设置。
在进入execve()系统调用之后，Linux内核就开始进行真正的装载工作。在内核中，execve()系统调用相应的入口是sys_execve(),作用：参数的检查复制；调用do_execve(),流程：查找被执行的文件，读取文件的前128个字节以判断文件的格式是elf还是其它；调用search_binary_handle(),流程：通过判断文件头部的魔数确定文件的格式，并且调用相应的装载处理程序。ELF可执行文件的装载处理过程叫load_elf_binary(),它的主要步骤如下：
1，检查ELF可执行文件格式的有效性，比如魔数、程序头表中段的数量。
2，寻找动态链接的“.interp”段，找到动态链接器的路径，以便于后面动态链接时会用上。
3，读取可执行文件的程序头，并且创建虚拟空间与可执行文件的映射关系。
【读取可执行文件的程序头（存储了哪些部分被映射），并且创建虚拟空间与可执行文件的映射关系】创建虚拟空间时的页映射关系函数是虚拟空间到物理内存的映射关系，而这一步所做的事虚拟空间与可执行文件的映射关系。我们知道，当程序发生缺页是，操作系统会为物理内存分配一个物理页，然后将该缺页从磁盘中读取到内存，在设置缺页的虚拟页与物理页之间的映射关系，这样程序才可以得以正常运行。但是明显的一点是，当操作系统捕获到缺页错误时，他应当知道程序当前需要的页在可执行文件中的哪一个位置。而这就是虚拟存储与可执行文件之间的映射关系。实际上，这种映射关系仅仅是保存在操作系统内部的一个数据结构。当发生缺页错误是，CPU将控制权交给操作系统，操作系统利用专门的缺页处理例程来查询这个数据结构（映射关系），然后找到所需页所在的虚拟内存区域，以及在可执行文件的偏移，然后把该页加载进物理内存，同时将该虚拟页与物理页之间建立映射关系，最后把控制权还给进程，进程从刚才缺页位置重新开始执行。
4，初始化ELF进程环境。
5，将系统调用的返回地址修改成ELF可执行文件的入口点，这个入口点取决于程序的链接方式，对于静态链接的ELF可执行文件，它就是ELF文件的文件头中e_entry所指的地址；对于动态链接的ELF可执行文件，程序入口点就是动态链接器。
【将CPU指令寄存器设置成可执行文件的入口，启动运行】对动态链接来讲，此时就启动了动态链接器。
当load_elf_binary()执行完毕，返回至do_execve()在返回至sys_execve()时，系统调用的返回地址已经被改写成了被装载的ELF程序的入口地址了。所以，当sys_execve()系统调用从内核态返回到用户态时，EIP寄存器直接跳转到ELF程序的入口地址。此时，ELF可执行文件装载完成。接下来就是动态链接器对程序进行动态链接了。
进程的虚拟空间：
五、动态链接
动态链接ELF文件的生成过程
主要原因有两个：第一，考虑内存和磁盘空间。静态链接极大地浪费内存空间。因为在静态链接的情况下，假设有两个程序共享一个模块，那么在静态链接后输出的两个可执行文件中各有一个共享模块的副本。如果同时运行这两个可执行文件，那么这个共享模块将在磁盘和内存中都有两个副本，对磁盘和内存造成极大地浪费；第二，程序的更新。一旦程序中的一个模块被修改，那么整个程序都要重新链接、发布给用户。如果这个程序相当的大，那么后果就会更加严重！
对于一个共享对象（linux下共享的模块），要实现被其他程序之间的共享，就要使其代码和数据分开，每个程序都会有该模块的数据部分的副本，代码部分是共享的。
共享模块被映射的虚拟地址空间就在上面进程虚拟空间中的 （Memery Mapping部分）
共享模块被映射的模样是
动态链接做了什么？
务必知道，动态链接是相对于共享对象而言的。动态链接器将程序所需要的所有共享库装载到进程的地址空间，并且将程序汇总所有为决议的符号绑定到相应的动态链接库（共享库）中，并进行重定位工作。
对于共享模块来说，要实现共享，那么其代码对数据的访问必须是地址无关（就是代码中的地址是固定的，当然这是用的相对地址喽）的，如何做到地址无关，编译器是这么干的，每一个共享模块，都会在其代码段有一个GOT(global offset table)段，如上图所示，Got是一个指针数组，用来存储外部变量的地址，而代码相对于Got的距离是固定的，当对外部模块变量数据和函数进行访问时，就去访问变量在GOT中的位置。
共享模块对于数据的访问方式：
本模块的全局变量和函数------相对地址
外模块的全局变量和函数-------GOT段
动态链接重定位时修改GOT中的值就实现了对变量的正确访问。
动态链接的ELF文件启动过程
动态链接基本分为三步：先是启动动态链接器本身，然后装载所有需要的共享对象，最后重定位和初始化。
1，动态链接器自举
就我们所知道的，对普通的共享对象文件来说，它的重定位工作是由动态链接器来完成；它也可以依赖于其他共享对象，其中被依赖的共享对象由动态链接器负责链接和装载。那么，对于动态链接器本身呢，它也是一个共享对象，它的重定位工作由谁完成？它是否可以依赖于其他的共享对象文件？
动态链接器有其自身的特殊性：首先，动态链接器本身不可以依赖其他任何共享对象（人为控制）；其次动态链接器本身所需要的全局和静态变量的重定位工作由它自身完成（自举代码）。
我们知道，在Linux下，动态链接器ld.so实际上也是一个共享对象，操作系统同样通过映射的方式将它加载到进程的地址空间中。操作系统在加载完动态链接器之后，就将控制权交给动态链接器。动态链接器入口地址即是自举代码的入口。动态链接器启动后，它的自举代码即开始执行。自举代码首先会找到它自己的GOT(全局偏移表，记录每个段的偏移位置）。而GOT的第一个入口保存的就是“.dynamic”段的偏移地址，由此找到动态链接器本身的“.dynamic”段。通过“.dynamic”段中的信息，自举代码便可以获得动态链接器本身的重定位表和符号表等，从而得到动态链接器本身的重定位入口，然后将它们重定位。完成自举后，就可以自由地调用各种函数和全局变量。
2，装载共享对象
完成自举后，动态链接器将可执行文件和链接器本身的符号表都合并到一个符号表当中，称之为“全局符号表”。然后链接器开始寻找可执行文件所依赖的共享对象：从“.dynamic”段中找到DT_NEEDED类型，它所指出的就是可执行文件所依赖的共享对象。由此，动态链接器可以列出可执行文件所依赖的所有共享对象，并将这些共享对象的名字放入到一个装载集合中。然后链接器开始从集合中取出一个所需要的共享对象的名字，找到相应的文件后打开该文件，读取相应的ELF文件头和“.dynamic”，然后将它相应的代码段和数据段映射到进程空间中。如果这个ELF共享对象还依赖于其他共享对象，那么将依赖的共享对象的名字放到装载集合中。如此循环，直到所有依赖的共享对象都被装载完成为止。
当一个新的共享对象被装载进来的时候，它的符号表会被合并到全局符号表中。所以当所有的共享对象都被装载进来的时候，全局符号表里面将包含动态链接器所需要的所有符号。
3，重定位和初始化
当上述两步完成以后，动态链接器开始重新遍历可执行文件和每个共享对象的重定位表，将表中每个需要重定位的位置进行修正，原理同前。
重定位完成以后，如果某个共享对象有“.init”段，那么动态链接器会执行“.init”段中的代码，用以实现共享对象特有的初始化过程。
此时，所有的共享对象都已经装载并链接完成了，动态链接器的任务也到此结束。同时装载链接部分也将告一段落！接下来便是程序的执行了。。。
