链接（linking）

链接是将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可被加载到内存并执行。
链接执行时期：

• 编译时
• 加载时
• 运行时

编译过程：
gcc -Og -o prog main.c sum.c

• C预处理器(cpp)，将C源程序mina.c翻译成一个ACSII码的中间文件。
  cpp main.c /tmp/main.i
• C编译器(ccl)，将main.i翻译成一个ASCII汇编语言文件main.s
  ccl /tmp/main.i -o /tmp/main.s
• 汇编器，将main.s翻译成一个可重定位目标文件 main.o
  as -o /tmp/main.o /tmp/main.s
• 链接器，将main.o和sum.o以及一些必要的系统目标文件组合起来，创建一个可执行文件prog:
  ld -o prog /tmp/main.o /tmp/sum.o

调用程序：
./prog
shell调用操作系统中一个叫加载器（loader）的函数，它将可执行文件aprog中的代码和数据复制到内存，然后将控制转移到程序的开头。

静态链接

上面的ld命令就是一个静态链接器，将一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的、可以加载和运行的可执行目标文件作为输出。

目标文件

1. 可重定位目标文件。包含二进制代码和数据，其形式可以在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件。
2. 可执行目标文件。包含二进制代码和数据，其形式可以被直接复制到内存并执行。
3. 共享目标文件。一种特殊类型的可重定位目标文件，可以在加载或运行时被动态加载进内存并链接。
   1和3都由编译器和汇编器生成，2则由链接器生成。

可重定位目标文件

ELF： 一种目标文件格式，用于现代x86-64 Linux和Unix系统使用的可执行可链接格式（Executable and Linkable Format,ELF）

image.png

• .text：已编译程序的机器代码。
• .rodata：只读数据
• .data：已初始化的全局和静态C变量。
• .bss：未初始化的全局和静态C变量，以及所有初始化为0的全局或静态变量。这是一个占位符，不分配实际空间，运行时才在内存中分配这些变量，初始值为0。

• .symtab：符号表，存放在程序中定义和引用的函数和全局变量信息。

  
  image.png

符号和符号表

符号表 .symtab
符号：

1. 由模块m定义并能被其他模块引用的全局符号。（不带static属性的C函数和全局变量）
2. 由其他模块定义并被模块m引用的全局符号，这些符号称为外部符号。
3. 只被模块m定义和引用的局部符号（带有static属性的C函数和全局变量），这些符号在模块m中任何位置都可见，但是不能被其他模块引用。
   本地链接符号和本地程序变量是不同的。局部变量是不会出现在符号表中的，因为这些都是在运行时在栈中被管理，链接器对此类符号不感兴趣。

符号解析

链接器解析符号引用的方法是将每个引用与它输入的可重定向目标文件的符号表中的一个确定的符号定义关联起来。对那些引用定义在系统模块中的局部符号的引用，符号解析非常简单，因为编译器只允许每个模块中每个局部符号有一个定义。
全局符号则不同，编译器遇到不在当前模块中定义的符号时，会生成一个链接器符号表条目，并交由链接器处理。如果链接器在输入的模块中找不到这个被引用的符号定义，就会输出错误信息并终止。全局符号还可能有相同的名字，所以解析起来也会增加困难。

解析多重定义的全局符号

image.png

与静态库链接

编译系统提供了一种机制，将所有相关目标模块打包成为一个单独得文件，称为静态库（static library），它可以用作链接器的输入。当链接器构造一个输出的可执行文件时，它只复制静态库里被应用程序引用的目标模块。即将许多.o文件打包成一个.a文件，然后将.a文件作为链接器的输入，并从.a文件里面复制被引用的.o模块。
以标准C函数为例（printf, atoi,scanf），如果编译器内置这些函数，那么如果要更新函数，必须要更新编译器。如果将所有函数的.o文件打包成一个.o文件，这样会使得可执行文件占用磁盘与内存空间较大。如果将函数的.o文件单独分开，这样在编译时要输入的.o文件又会太多。
为了解决上面那些问题，就提出了静态库的概念。将所有的.o打包成一个.a文件，链接器只复制用到的目标模块。这样既方便了程序员，也节省了磁盘与内存空间。

image.png

链接器如何使用静态库来解析引用

维护三个集合，可重定位目标文件集合E，未解析的符号U，已定义的符号集合D。

• 对命令行上每个输入文件f，链接器判断f是目标文件还是存档文件（.a），如果是目标文件，那么把f添加到E中，修改U和D来反映f中的符号定义和引用，并继续下一个文件。
• 如果f是存档文件，那么尝试匹配U中未解析的符号，如果存档文件某个成员m定义了一个符号来解析U中的一个引用，那么将m当做目标文件对待。一直重复这个过程，当U，D不再发生变化时，丢弃次存档文件的其他成员。继续处理下一个文件。
• 如果命令行上输入文件扫描完成后，U是非空的，那么就报错（因为有未解析的符号）。否则，合并E中的目标文件，构建出可执行文件。
  所以，目标文件一般放在参数开头，库文件放在参数结尾。如果库文件在开头，那么可能由于U一开始是空的，很多目标文件要用的引用都会被丢弃。导致链接失败。

重定位

完成了链接之后，链接器就知道它的输入目标模块中的代码节和数据节的确切大小。就可以开始重定位的步骤了，在这个步骤中，合并输入模块，并为每个符号分配运行时地址。重定位分为两步：

• 重定位节和符号定义。将所有相同类型的节合并为一个节。如将所有输入模块的.data节合并为一个节，作为可执行文件的.data节。此时程序中的每条指令和全局变量都有唯一的运行时内存地址了。
• 重定位节中的符号引用。链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。