1️⃣ 概念

定义
- 链接（linking）是将各种代码和数据片段收集并组合成一个单一文件的过程，这个文件可被加载(复制)到内存并执行。
执行期
- 链接可以执行于编译时(compiletime)，也就是在源代码被翻译成机器代码时。
- 链接可以执行于加载时(loadtime)，也就是在程序被加载器(loader)加载到内存并执行时
- 链接可以执行于运行时(runtime)，也就是由应用程序来执行。
执行对象
- 现代计算机，链接是由叫做链接器（linker）的程序自动执行的。

2️⃣ 编译器驱动程序

作用
- 大多数编译系统提供编译器驱动程序(compilerdriver)，它代表用户在需要时调用语言预处理器、编译器、汇编器和链接器。
- Linux 环境下，我们可以在 shell 中输入如下命令，调用 GCC 驱动程序
  - gcc -o prog main.c sum.c
  - main.c 和 sum.c 分别为两个不同的源文件。

示例程序

int sum(int *a, int n);

int array[2] = {1, 2};

int main()
{
    int val = sum(array, 2);
    return val;
}

int sum(int *a, int n)
{
    int i, s = 0;
    
    for (i = 0; i < n; i++) {
        s += a[i];
    }
    return s;
}

😈 驱动程序是如何将示例程序从 ASCII码 源文件翻译成可执行目标文件的？
- 步骤
  - 驱动程序首先运行 C 预处理器(cpp)，它将 C 的源程序 main.c 翻译成一个 ASCII 码的中间文件 main.i。
  - 接着，驱动程序运行 C 编译器( cc1 )，它将 main.i 翻译成一个 ASCII 汇编语言文件 main.s
  - 然后，驱动程序运行汇编器( as )，它将 main.s 翻译成一个可重定位目标文件 main.o。
  - 最后，驱动程序运行链接器程序( ld )，将 main.o 和 sum.o 以及一些必要的系统目标文件组合起来，创建一个可执行目标文件 prog。
- 流程图
- 执行
  - 要运行可执行文件 prog，我们在 Linux shell 的命令行上输入它的名字
    - linux> ./prog
  - shell 调用操作系统中一个叫做加载器的函数，它将可执行文件 prog 中的代码和数据复制到内存，然后将控制转移到这个程序的开头。

3️⃣ 静态链接（static linker）

定义（静态链接器）
- 输入：一组可重定向目标文件和命令行参数。
- 输出：一个完全链接的、可以加载的和运行的可执行目标文件。
😈 两个主要任务
- 符号解析（symbolresolution）
  - 可重定向目标文件定义和引用符号。每个符号对应于一个函数、全局变量或静态变量。
  - 符号解析的目的是将每个符号引用正好和一个符号定义关联起来。
- 重定位（relocation）
  - 输入的 可重定位目标文件 (.o) 可以看成由多个 section（节）拼起来的：比如代码节 .text、数据节 .data 等。每个节在文件里都是一段连续存放的字节块。
  - 在生成 .o 时，编译器/汇编器只确定节内偏移（从 0 开始计数），并不会确定最终装载地址；因此对外部符号的地址通常先留占位，等链接阶段再填。
  - 链接器 先为每个符号（函数/全局变量等）分配最终地址，然后根据重定位信息，把代码和数据中所有引用该符号的位置改写为正确的地址（或相对偏移），从而让这些引用在最终程序里指向正确的位置。
  - 链接器 使用汇编器产生的重定位条目的详细指令，不加甄别地执行这样的重定位。
理解
- 基本事实
  - 一个可重定位目标文件是字节块的集合。
  - 这些块中，有些包含程序代码，有些包含程序数据，而其他的则包含引导链接器和加载器的数据结构。链接器将这些块连接起来，确定被连接块的运行时位置，并且修改代码和数据块中的各种位置。

1️⃣ 目标文件

形式
- 可重定位目标文件：
  - 包含二进制代码和数据，其形式可以在链接时与其他可重定位目标文件合并起来，创建一个可执行目标文件。
- 可执行目标文件：
  - 包含二进制代码和数据，其形式可以被直接复制到内存并执行。
- 共享目标文件：
  - 一种特殊的可重定位目标文件，可以在加载或者运行时被动态地加载进内存并链接。
理解
- 编译器和汇编器生成可重定位目标文件；链接器生成可执行目标文件。
- 从技术上来说
  - 目标模块（object mudule）就是一个字节序列。
  - 目标文件（object file）就是一个以文件形式存放在硬盘的目标模块。

2️⃣ 可重定位目标文件

ELF可重定位目标文件格式
解析
- .text：已编译程序的机器代码。
- .rodata：只读数据。
- .data：已初始化的全局和静态 C 变量。
- .bss：未初始化的全局和静态 C 变量，以及初始化为 0 的全局或静态变量。
- .symtab：符号表，它存放在程序中定义和引用的函数和全局变量的信息。
- .rel.text：代码段 .text 的重定位表，它列出 .text 中哪些位置包含“待填的地址/位移”。。
  - 当链接器把这个目标文件和其他文件组合时，需要修改这些位置。
  - 一般而言，任何调用外部函数或者引用全局变量的指令都需要修改。
  - 另一方面，调用本地函数的指令则不需要修改。
- .rel.data：是数据段 .data 的重定位表，它记录 .data 中哪些位置存放了“需要在链接后才能确定的地址值”。
  - 包含被模块引用或定义的所有全局变量的重定位信息。
  - 任何已初始化的全局变量，如果它的初始值是一个全局变量地址或者外部定义函数的地址，都需要被修改。
- .debug：调试符号表，其条目是程序中定义的局部变量和类型定义。
  - 保存源代码到机器码的映射关系，以及局部变量/类型/作用域等信息，供 gdb/lldb 在调试时显示变量、行号和堆栈使用；程序运行本身不依赖它。
- .line：原始 C 源程序中的行号和 .text 节中机器指令之间的映射。
- .strtab：字符串表，其内容保存 .symtab 和 .debug 节中的符号表以及节头部中的节名字。
- ELF 头
  - 以 16 字节的序列开始，描述了生成该文件的系统的字的大小和字节顺序。
  - ELF 头剩下的部分包含帮助链接器语法分析和解释目标文件的信息。
  - 其中包括
    - ELF 头的大小
    - 目标文件的类型（如可重定位、可执行或者共享的）
    - 机器类型（如x86-64）
    - 节头部表（section header table）的文件偏移
    - 节头部表中条目的大小和数量——不同节的位置和大小是由节头部表描述的，其中目标文件中每个节都有一个固定大小的条目(entry)。
- 节头部表
  - 节头部表是 ELF 文件中的一个数组，每个条目描述文件中的一个节。每个节头条目都是一个固定大小的结构，描述该节的类型、位置、大小等信息。

3️⃣ 符号

符号定义
- 符号定义 指的是在源代码创建一个符号，并为它分配一个内存位置或者给它一个值。
- 通常，符号定义是对某个变量或函数的声明和赋值，表示这个符号存在于程序中。
- 每个符号在程序中只能有一个定义（避免重复定义）。如果有多个定义，链接器会报错。
  1
  2
  3
  4
  5
  6
  7
  // 定义一个全局变量 x
  int x = 10;
  // 定义一个函数 foo
  void foo()
  {
  printf("hello world");
  }

符号引用

符号引用 指的是在程序中使用某个符号，但是在当前源文件中没有进行定义。

符号引用 指的是对其他模块或者外部符号的访问，链接器会根据符号引用找到该符号的定义。

// 声明一个外部符号 x
extern int x; 
// 引用全局变量 x
void bar() {
    printf("%d\n", x); 
}
// 声明一个外部函数 foo
extern void foo();  
void bar() {
    foo();  // 引用函数 foo
}

符号的种类

由模块 m 定义并能被其他模块引用的全局符号。
- 全局符号 对应于非静态的C函数和全局变量。
由其他模块定义并被模块 m 引用的全局符号。
- 外部符号 对应于在其他模块中定义的非静态C函数和全局变量。
只被模块 m 定义和引用的本地符号。
- 它们对应于带 static 属性的 C 函数和全局变量。这些符号在模块 m 中任何位置都可见，但是不能被其他模块引用。

#include <stdio.h>

// 1. 模块 m 定义并能被其他模块引用的全局符号（Global Symbol）
int global_var = 100; // 定义了一个全局变量 global_var

void foo() { // 定义了一个全局函数 foo
     printf("Function foo() called\n");
}

// 2. 只被模块 m 定义和引用的局部符号（Local Symbol with static)
static int local_var = 200; // 定义了一个局部符号 local_var，只能在 file1.c 中访问

static void bar() { // 定义了一个局部函数 bar，只能在 file1.c 中访问
    printf("Function bar() called\n");
}

#include <stdio.h>

// 3. 由其他模块定义并被模块 m 引用的全局符号（External Symbol）
extern int global_var;  // 引用了在 file1.c 中定义的全局符号 global_var
extern void foo();      // 引用了在 file1.c 中定义的全局函数 foo

 void test() {
    printf("global_var = %d\n", global_var); // 使用 global_var
    foo(); // 使用 foo
}

4️⃣ 符号表

符号表定义

每个可重定位目标模块 m 都有一个符号表，它包含 m 定义和引用的符号的信息。

理解
- .symtab 中的符号表不包含对应于本地非静态程序变量的任何符号。这些符号在运行时在栈中被管理，链接器对此类符号不感兴趣。
- 定义为带有 static 属性的本地过程变量是不在栈中管理的。相反，编译器在 .data 或 .bss 中为每个定义分配空间，并在符号表中创建一个有唯一名字的本地链接器符号。
- 在这种情况中，编译器向汇编器输出两个不同名字的局部链接器符号。比如，它可以用 x.1 表示函数 f 中的定义，而用 x.2 表示函数 g 中的定义。

符号表的结构

符号表是一个包含符号的一维数组，.symtab 节中就包含着 ELF 符号表。

符号的定义

name 是字符串表中的字节偏移，指向符号的以 null 结尾的字符串名字。
value 是符号的地址。对于可重定位的模块来说，value 只表示符号在其所在节（section）内的相对位置——也就是相对于该节起始地址的偏移量。
size 是目标的大小（以字节为单位）。
type 通常要么是数据，要么是函数。符号表还可以包含各个节的条目，以及对应原始源文件的路径名的条目。所以这些目标的类型也有所不同。
binding 字段表示符号是本地的还是全局的。
section 字段表示每个符号都被分配到目标文件的某个节，该字段也是一个到节头部表的索引。
- 有三个特殊的伪节（pseudosection），它们在节头部表中是没有条目的：
  - ABS 代表不该被重定位的符号
  - UNDEF 代表未定义的符号，也就是在本目标模块中引用，但是却在其他地方定义的符号
  - COMMON 表示符号是未初始化的数据，链接器会在链接时为其分配内存。
- 注意
  - 只有可重定位目标文件中才有这些伪节，可执行目标文件中是没有的。
例子
- 解析
  - 全局符号 main 定义的条目，它是一个位于 .text 节中偏移量为 0 的 24 字节函数。
  - 全局符号 array 的定义，它是一个位于 .data 节中偏移量为 0 处的 8 字节目标。
  - 最后一个条目来自对外部符号 sum 的引用。
  - READELF 用整数索引来标识每个节。Ndx=1 表示 .text 节，而 Ndx=3 表示 .data 节。

5️⃣ 符号解析

定义

链接器 解析符号引用的方法是将符号引用和输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。

解析方式

对和引用定义在相同模块中的局部符号的引用，符号解析是非常简单明了的。
- 编译器只允许每个模块中每个局部符号有一个定义。
- 静态局部变量会有本地符号，编译器还要确保它们拥有唯一的名字。
全局符号的引用解析就棘手得多
- 当编译器遇到一个不是在当前模块中定义的符号（变量或函数名）时，会假设该符号是在其他某个模块中定义的，生成一个链接器符号表条目，并把它交给链接器处理。
- 如果链接器在它的任何输入模块中都找不到这个被引用符号的定义，就输出一条错误信息并终止。
  1
  2
  3
  4
  5
  6
  void foo(void);
  
  int main() {
  foo();
  return 0;
  }
  编译器可以运行，但是链接器无法解析对 foo 的引用。

链接器如何解析多重定义的全局符号 😈

问题

链接器的输入是一组可重定位目标模块。每个模块定义一组符号，有些是局部的，有些是全局的。
如果多个模块定义同名的全局符号，会发生什么呢？

解决方法

在编译时，编译器向汇编器输出每个全局符号，或者是强（strong）或者是弱（weak）
而汇编器把这个信息隐含地编码在可重定位目标文件的符号表里。
函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。

链接器处理规则

规则1：不允许有多个同名的强符号。
规则2：如果有一个强符号和多个弱符号同名，那么选择强符号。
规则3：如果有多个弱符号同名，那么从这些弱符号中任意选择一个。

示例代码

规则一

int main() {
    return 0;
}

1
2
3

int main() {
    return 0;
}

这种情况下，链接器将生成一条错误信息，因为强符号 main 被定义了多次（规则1）

规则二

如果在一个模块里 x 未被初始化，那么链接器将安静地选择在另一个模块中定义的强符号(规则2)：

#include <stdio.h>

void f(void);

int x = 15213;
int main() {
    f();
    printf("x = %d\n", x);
    return 0;
}

int x;

void f() {
    x = 15212;
}

在运行时，函数 f 将 x 的值由 15213 改为 15212，链接器不会表明它检测到多个 x 的定义。

规则三

如果 x 有两个弱定义，会发生同样的事情

/* foo4.c */
#include <stdio.h>
void f(void);

int x;

int main() {
    x = 15213;
    f();
    printf("x = %d\n", x);
    return 0;
}

/* bar4.c */
int x;

void f() {
    x = 15212;
}

与静态库的链接😈

静态库

迄今，我们都是假设链接器读取一组可重定位目标文件，并把它们链接起来，形成一个输出的可执行文件。
实际上，所有的编译系统都提供一种机制，将所有相关的目标模块打包成为一个单独的文件，称为静态库（static library），它可以用做链接器的输入。
当链接器构造一个输出的可执行文件时，它只复制静态库里面被应用程序引用的目标模块。

存储位置

在Linux系统中，静态库以一种称为存档（archive）的特殊文件格式存放在磁盘中。
存档文件是一组连接起来的可重定位目标文件的集合，有一个头部用来描述每个成员目标文件的大小和位置。存档文件名由后缀 .a 标识。

创建静态库

代码示例

int addcnt = 0;

void addvec(int *x, int *y, int *z, int n) {
    int i;
            
    addcnt++;
            
    for (i = 0; i < n; i++)
        z[i] = x[i] + y[i];
}

int multcnt = 0;

void multvec(int *x, int *y,int *z, int n) {
    int i;
            
    multcnt++;
            
    for (i = 0; i < n; i++)
        z[i] = x[i] * Y[i];
}

命令行
- linux> gcc -c addvec.c multvec.c
- linux> ar rcs libvector.a addvec.o multvec.o
静态库的使用
1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include "vector.h"

int x[2] = {1, 2};
int y[2]= {3, 4};
int z[2];

int main() {
addvec(x, y, Z, 2);
printf("z = [%d %d]\n", z[0], z[1]);
return 0;
}
- 为了创建这个程序的可执行文件，我们要编译和链接输入文件 main.o 和 libvector.a
- 命令行
  - linux> gcc -c main2.c
  - linux> gcc -static -o prog2c main2.o ./libvector.a
- 或者
  - linux> gcc -c main2.c
  - linux> gcc -static -o prog2c main2.o -L. -lvector
- 流程图
- 解析
  - 当链接器运行时，它判定 main2.o 引用了 addvec.o 定义的 addvec 符号，所以复制 addvec.o 到可执行文件。
  - 因为程序不引用任何由 multvec.o 定义的符号，所以链接器就不会复制这个模块到可执行文件。
  - 链接器还会复制 libc.a 中的 printf.o 模块，以及许多 C 运行时系统中的其他模块。

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

定义
- 在符号解析阶段，链接器从左到右按照它们在编译器驱动程序命令行上出现的顺序来扫描可重定位目标文件和存档文件。
再扫描的过程中，链接器维护三个集合且初始时 E、U、D全为空：
- 可重定位目标文件集合 E
- 未解析的符号集合 U
- 已经定义的符号集合 D
👿 扫描流程
- 对于命令行上的每个输入文件 f，链接器会判断 f 是一个目标文件还是一个存档文件。
- 如果 f 是一个目标文件，那么链接器把 f 添加到 E，修改 U 和 D 来反映 f 中的符号定义和引用，并继续下一个输入文件。
- 如果 f 是一个存档文件，那么链接器尝试匹配 U 中未解析的符号和由存档文件成员定义的符号。
  - 如果某个存档文件成员 m，定义了一个符号来解析 U 中的一个引用，那么就将 m 加到 E 中，并且链接器修改 U 和 D 来反映 m 中的符号定义和引用。
  - 对存档文件中所有的成员目标文件都依次进行这个过程，直到 U 和 D 都不再发生变化。
  - 此时，任何不包含在 E 中的成员目标文件都被丢弃，而链接器将继续处理下一个输入文件。
- 如果当链接器完成对命令行上输入文件的扫描后，U 是非空的，那么链接器就会输出一个错误并终止。否则，它会合并和重定位 E 中的目标文件，构建输出的可执行文件。
命令行上的库和目标文件的顺序
- 问题
  - 在命令行中，如果定义一个符号的库出现在引用这个符号的目标文件之前，那么引用就不能被解析，链接会失败。
- 示例
  - linux> gcc -static ./libvector.a main2.c
- 解析
  - 在处理 libvector.a 时，U 是空的，所以没有 libvector.a 中的成员目标文件会添加到 E 中。因此，对 addvec 的引用是绝不会被解析的，所以链接器会产生一条错误信息并终止。

6️⃣ 重定位

前提

一旦链接器完成了符号解析，它会确保代码中每个符号引用与它正好唯一的符号定义关联起来。
这意味着对于每个符号引用（如对全局变量或函数的调用），链接器会在目标模块中查找符号表，找到唯一的符号定义并将它们绑定起来。
例如，如果 file1.o 中引用了 x，链接器会从 file2.o 中的符号表中找到 x 的定义，完成符号解析，并将引用解析到正确的地址。

定义

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

步骤 😈

重定位 “节” 和 “符号定义”
- 这一步中，链接器将所有相同类型的节合并为同一类型的新的聚合节。
- 例如
  - 来自所有输入模块的 .data 节被全部合并成一个节，这个节成为输出的可执行目标文件的 .data 节。
- 然后，链接器将运行时内存地址赋给新的聚合节，赋给输入模块定义的每个节，以及赋给输入模块定义的每个符号。
- 每个节的地址保存在节头部表中，符号的地址保存在符号表中。
- 当这一步完成时，程序中的每条指令和全局变量都有唯一的运行时内存地址了。
重定位 ”节“中的 ”符号引用“
- 这一步中，链接器修改 ”代码节“和 ”数据节“ 中对每个符号的引用，使得它们指向正确的运行时地址。
- 执行这一步，链接器依赖于可重定位目标模块中称为重定位条目的数据结构。

重定位条目

前提
- 当汇编器生成一个目标模块时，它并不知道数据和代码最终将放在内存中的什么位置。它也不知道这个模块引用的任何外部定义的函数或者全局变量的位置。
- 所以，汇编器遇到对最终位置未知的目标引用，它就会生成一个重定位条目，告诉链接器在将目标文件合并成可执行文件时如何修改这个引用。
- **.rel.text**：包含与代码段（.text 节）相关的重定位条目。这些条目描述了代码中对外部符号的引用位置（例如函数调用或跳转）。
- **.rel.data**：包含与数据段（.data 节）相关的重定位条目。这些条目描述了数据中对外部符号的引用位置（例如全局变量引用）。
ELF重定位条目格式
- offset：是需要被修改的符号引用的节偏移。
- symbol：标识被修改符号引用应该指向的符号。
- type：告知链接器如何修改新的引用。
- addend：是一个有符号常数，一些类型的重定位要使用它对被修改引用的值做偏移调整。
😈 代码示例
1
2
3
4
5
extern int global_var; // 引用外部变量

void foo() {
printf("%d\n", global_var); // 需要链接器来处理地址
}
1
int global_var = 42; // 定义外部变量
- 汇编过程
  - 汇编器将 file1.o 中的 global_var 引用视为一个符号引用。它并不知道 global_var 在内存中的地址，因为这个地址在编译时是未定义的，因此汇编器为 global_var 生成一个重定位条目，告诉链接器该符号在代码中的位置（即 foo() 函数中引用 global_var 的位置）。
  - 汇编器也会为 file2.o 生成目标文件，其中包含对 global_var 的定义，但汇编器不会生成重定位条目，因为它已经知道 global_var 的地址（这是由 file2.o 中的定义提供的）。
- 链接过程
  - 链接器将 file1.o 和 file2.o 合并成一个最终的可执行文件。
  - 在合并过程中，链接器检查 file1.o 中的重定位条目（在 .rel.text 节中），并将 global_var 的地址更新为在 file2.o 中定义的实际地址。
  - 假设 file2.o 中定义的 global_var 的地址是 0x1000，链接器会将 file1.o 中 global_var 的引用地址更新为 0x1000。

7️⃣ 可执行目标文件

ELF 可执行目标文件格式
- 格式解析
  - ELF 头描述文件的总体格式。它还包括程序的入口点(entrypoint)，也就是当程序运行时要执行的第一条指令的地址。
  - .text、.rodata 和 .data 节与可重定位目标文件中的节是相似的，除了这些节已经被重定位到它们最终的运行时内存地址以外。
  - .init 节定义了一个小函数，叫做 _init，程序的初始化代码会调用它。
  - 因为可执行文件是完全链接的（已被重定位），所以它不再需要 .rel 节。
- 理解
  - ELF 可执行文件被设计得很容易加载到内存，可执行文件的连续的片被映射到连续的内存段。
  - 程序头部表(programheader table)描述了这种映射关系。
  - 示例
    - 解析
      - 从程序头部表，我们会看到根据可执行目标文件的内容初始化两个内存段。
      - 第1、2行表明第一个段（代码段）有读/执行访问权限，开始于内存地址 0x400000 处，总共的内存大小是 0x69c 字节，并且被初始化为可执行目标文件的头 0x69c个字节，其中包括 ELF 头、程序头部表以及 .init、.text 和 .rodata 节。
      - 第3、4行表明第二个段（数据段）有读/写访问权限，开始于内存地址0x600df8处，总的内存大小为 0x230 字节，并用从目标文件中偏移 0xdf8 处开始的 .data 节中的 0x228 个字节初始化。该段中剩下的8个字节对应于运行时将被初始化为 0 的 .bss数据。
  - 注意
    - 对于任何段s，链接器必须选择一个起始地址vaddr，使得：
      vaddr mod align = off mod align
      这里，off是目标文件中段的第一个节的偏移，align是程序头部指定的对齐。
    - 在上图中的data segment
      - vaddr mod align = 0x600df8 mod 0x200000 = 0xdf8
      - off mod align = 0xdf8 mod 0x200000 = 0xdf8

8️⃣ 加载可执行目标文件

前提
- 要运行可执行目标文件prog，我们可以在Linux shell的命令行中输入它的名字：
  linux> ./prog
解析
- 因为 prog 不是一个内置的shell命令，所以 shell 会认为 prog 是一个可执行目标文件，通过调用某个驻留在存储器中称为加载器（loader）的操作系统代码来运行它。
- 任何 Linux 程序都可以通过调用 execve 函数来调用加载器。
- 加载器将可执行目标文件中的代码和数据从磁盘复制到内存中，然后通过跳转到程序的第一条指令或入口点来运行该程序。这个将程序复制到内存并运行的过程叫做加载。
虚拟内存
- 当加载器运行时，它创建类似于上图所示的虚拟内存。
- 在程序头部表的引导下，加载器将可执行文件的片（chunk）复制到代码段和数据段。
- 接下来，加载器跳转到程序的入口点，也就是 _start 函数的地址。该函数位于系统目标文件 ctrl.o 中。对所有的C 程序都是一样的。_start 函数调用系统启动函数 __libc_start_main，该函数定义在 libc.so 中。它初始化执行环境，调用用户层的 main 函数，处理 main 函数的返回值，并且在需要的时候把控制返回给内核。