在现代的计算机技术中，linking 其实非常重要，伴随该技术，产生了符号表、静态库、动态库等技术。在借助 Clang/汇编/Mach-O 进行C基本内存分析一文中，介绍了一个项目在生成二进制之前，大致可以概括为 3 个步骤，编译、汇编、链接。这一节对链接进行全面的分析。
为什么需要链接器
主要有两个目的，第一，代码可以模块化，即将多个源文件打包在一个集合中，这些文件都是功能可以归属为一个大的分类，比如数学计算类。第二，提高效率和资源利用率，如果修改了库中的源文件，只要对外的链接符号保持不变，那么引用它的项目就无需重新编译和链接；另外最终的可执行文件中，只会从引用库中拷贝走真正需要的功能函数，不会将整个库都拷贝进可执行文件。
链接器做了些什么
大致可分为两点，第一符号解析，编译、汇编后生成的每个目标文件中，都会包含符号信息，链接器需要解析它们，分清楚哪些是外部符号，哪些是内部符号。第二重定位，链接器会把多个目标文件，按照不同section划分，合并为一个单一文件，合并后必然导致，原来单个文件中符号的相对偏移位置发生变化，链接器需要修正它们。
什么是 ELF 文件
ELF 全称是可执行可链接的文件格式(Executable and Linkable Format)，通常叫做 ELF 二进制文件。ELF是一个标准，用来规范二进制格式的目标文件。在 Unix 或者 Linux 平台下，对该文件格式的具体实现，可分为三类。
1、可重定位目标文件(Relocatable) .o
就是常说的目标文件，例如 main.c 编译、汇编后的产物命名为 main.o。这种文件不是可执行的文件，但是也遵循了 ELF 格式包含了代码段数据段，符号表等，这些目标文件可以和其他可重定位的目标文件一起打包成最终的可执行文件。
2、可执行文件(Executable) a.out
包含了完整的代码段数据段等其他二进制信息的可执行文件。由于最早版本的 Linux 可执行文件被命名为 a.out，所以延续至今。
3、共享目标文件(Shared) .so
即各种库文件(.a .framework)，这些文件同样支持符号重定位，与其他文件进行链接，可以静态链接(static)，可以在装载时链接(loaded)，也可以在运行时链接(dynamic)。动态链接库，在 Windows 下叫做 DLLs。
ELF 的文件基本格式
其中的大部分段，在借助 Clang/汇编/Mach-O 进行C基本内存分析中已经详细介绍过，这里重点关注符号表和重定位的段。
1、.symtab section符号表，主要是当前文件内部的函数和全局静态变量的符号信息。
2、rel.text section代码段可重定位信息，这个段指明了在代码段中，需要修改的指令的地址，修改可能在合并为可执行文件时发生，也可以是运行时。
3、rel.data section数据段可重定位信息，这个段指明了在数据段中，需要修改的指令的地址，修改主要在合并为可执行文件时发生。
4、.debug sectiondebugging 的符号信息，符号信息可以通过下列三种命令行方式生成。
$ clang -c -g main.c -o main
生成，此时符号信息和目标文件在一起。
$ clang -g1 main.c -o main
单独生成 .dYSM 文件。
$ gcc -g main.c
单独生成 .dSYM 文件。
$ clang -g1 -Wl, -U,<symbol name> -o main
生成符号表时忽略某些符号
查看符号信息
dwarfdump main.dSYM
链接符号类别
1、全局符号
主要指全局函数和全局变量(non-static)类型，这些符号在文件或者模块内部定义，可以被外部引用。
2、本地符号
static 类型的函数和全局变量，这些符号只在当前文件或者模块内使用，外部不可见。另外局部的auto变量不是链接符号，局部变量会在运行时被栈、帧寄存器管理，链接器无需理会。
3、外部符号
当前文件或模块中没有定义，需要引用外部模块的符号，这些符号都用 0 填充，等待链接器进一步处理。
强符号和弱符号
链接符号也有 strong 和 weak 之分，用来让链接器进行决议。函数符号和已经初始化的全局变量都属于强符号，未初始化的变量属于弱符号。
int foo = 5; // strong
void p1() { // strong
}
int foo; // weak，会被保存在 .bss section 中(oc环境下会被保存在 __DATA,__common 中)，并用 0 填充。
强弱符号的链接规则：
1：不能同时存在多个相同的强符号，如果存在，用链接报错提示。
2：同时存在系统的强弱符号，优先选择强符号进行链接(在 Clang 环境下不允许，也会报错)。
3：多个相同的弱符号共存，链接器任意选择其一(在 Clang 环境下不允许，也会报错)。
所以，写代码时，应该遵循一些基本规则。
1：外部不用，就定义为 static 。
2：变量在定义时就进行初始化。
3：使用 extern 来明确外部引用。
符号重定位的过程
例如项目中有 main.c 和 sum.c 两个文件，其中 main.c 使用 sum.c 中的sum函数。。
// main.c file
int as = 12;
int main() {
int ls = 10;
int s = sum(as, ls);
return s;
}
// sum.c file
int sum(int a, int b) {
return a + b;
}
先生成目标文件。
$ clang -c main.c sum.c // 编译产生 main.o 和 sum.o 文件
$ clang main.o sum.o // 链接生成 a.out 文件
由于只有main.c中引用了 sum 函数，以及全局变量 as；所以使用 objdump 查看main.o和最终的可执行文件a.out。
$ objdump -d main.o
0000000000000000 <ltmp0>:
0: ff 83 00 d1 sub sp, sp, #32
.....
18: 08 00 00 90 adrp x8, 0x0 <ltmp0+0x18> // as 全局变量写入寄存器指令
.....
24: 00 00 00 94 bl 0x24 <ltmp0+0x24> // 跳转 sum 函数指令
.....
$ objdump -d a.out
0000000100003f54 <_main>:
100003f54: ff 83 00 d1 sub sp, sp, #32
......
100003f6c: 08 00 00 b0 adrp x8, 0x100004000 <_main+0x1c> // as 全局变量写入寄存器指令
......
100003f78: 06 00 00 94 bl 0x100003f90 <_sum> // 跳转 sum 函数指令
......
0000000100003f90 <_sum>:
100003f90: ff 43 00 d1 sub sp, sp, #16
......
先分析sum函数的符号链接过程：
对于全局变量 int as = 12，链接过程就相对简单一些，使用nm -nm a.out查看符号的虚拟地址(vm)：
$ nm -nm a.out
0000000100000000 (__TEXT,__text) [referenced dynamically] external __mh_execute_header
0000000100003f54 (__TEXT,__text) external _main // sum 函数入口地址
0000000100003f90 (__TEXT,__text) external _sum // sum 函数入口地址
0000000100004000 (__DATA,__data) external _as // 全局变量 as 的地址
as的地址为0x100004000，被写入了__TEXT,__text中的汇编指令的对应位置，该位置原来用0x0占位。
静态库
静态库也叫 archiver，unix 和 linux 下，可以使用ar命令进行打包。
ar rs mymath.a sum.o subtract.o
另外 Xcode 也有打包功能，如果文件很多，可以用 Xcode 进行打包。打包后，可以用nm命令进行查看符号信息。
$ nm -nm mymath.a
mymath.a(sum.o):
0000000000000000 (__TEXT,__text) external _sum
0000000000000000 (__TEXT,__text) non-external ltmp0
0000000000000020 (__LD,__compact_unwind) non-external ltmp1
mymath.a(subtract.o):
0000000000000000 (__TEXT,__text) external _substract
0000000000000000 (__TEXT,__text) non-external ltmp0
0000000000000020 (__TEXT,__text) external _foo
0000000000000028 (__LD,__compact_unwind) non-external ltmp1
或者使用ar命令：
$ ar -t mymath.a
__.SYMDEF SORTED
sum.o
subtract.o
静态库链接算法
静态库是在打包阶段进行链接的，链接器算法规则：
1: 扫描当前参与链接的所有文件，创建三个集合
E 集合: 存放所有需要符号重定位的目标文件(relocatable object file)
U 集合: 存放所有未决议符号
D 集合: 存放之前扫描过所有文件已经定义的符号
2：如果文件 f 是目标文件，将 f 加入 E 中。同时更新 U D 集合。如果是 f 是 .a 静态库，则用 .a 的所有的外部符号与集合 U 中未决议的符号匹配，匹配上，就将这些符号从 U 中删除，同时加入 D 中，同时用这些外部符号更新所有需要用这些符号重定位的目标文件。
3: 最终如果集合 U 为空集，则链接成功，如果非空，就报链接错误。通过最终的结合 D 可以整理出符号表，通过结合 E 可以整理出可执行文件。
动态库 Shared Libraries
为什么叫动态库? 因为这些库不是在打包的时候进行链接。动态库即可以在装载二进制文件的时候链接(load-time)，也可以在运行时进行链接(run-time)。如果是启动时链接，则由启动程序 Loader 进行，Unix 和 Linux 下的函数入口execve()，macOS 中该函数定义在unistd.h文件中。运行时，可以通过dlopen()函数链接，macOS中该函数定义在dlfcn.h文件中。
使用 dlopen 进行动态链接
先生成动态库gcc -shared -o libmymath.so sum.o subtract.o，然后依次加载，读取，关闭。
int as = 12;
int main() {
void *handle;
int (*sum_func)(int, int);
char *err;
// 用懒加载的方式加载动态库
handle = dlopen("./libmymath.so", RTLD_LAZY);
if (!handle) {
return 0;
}
// 获取 sum 函数指针
sum_func = dlsym(handle, "sum");
if ((err = dlerror()) != NULL) {
return 0;
}
// 执行函数
int s = sum_func(as, 10);
printf("s: %d \n", s);
// 关闭动态库句柄
dlclose(handle);
return 0;
}
现在的操作系统大多支持的是运行时动态链接，所以通常程序启动的时候，都会伴随着启动一个动态链接器，在 macOS 和 iOS 平台的链接器是dyld，并且代码开源的。
链接器除了用来链接程序，我们还可以借助其特性实现对库函数的hook。比如hook系统的malloc函数，由于不同的Xcode版本对Clang命令的支持有所区别，这里简单说一下hook原理。
void * __real_malloc(size_t __size);
void * wrap_malloc(size_t __size) {
void *p = __real_malloc(__size);
printf("print wrap_malloc, then invoke real malloc function \n");
return p;
}
__real_malloc只做声明，目的是和真正的malloc函数的实现进行绑定。同时利用链接器把原来的malloc符号绑定在wrap_malloc实现上。另外，如果 hook 了malloc，同时也要 hook free函数。
PIC (Position-Independent Code) 与动态库
PIC 表示地址无关代码，事实上就是PC 相对寻址，链接时，通过-fpic参数，就会让编译器和链接器自动实现 PIC 功能。事实上现在的链接器，默认都会进行 PIC 链接，例如前文中分析的sum函数的链接解析。
链接器生成的main.o中，包含了需要重定位的信息：
$ xcrun objdump -r main.o
RELOCATION RECORDS FOR [__text]:
OFFSET TYPE VALUE
0000000000000024 ARM64_RELOC_BRANCH26 _sum
000000000000001c ARM64_RELOC_PAGEOFF12 _as
0000000000000018 ARM64_RELOC_PAGE21 _as
0000000000000024 ... _sum表示当前main.o偏移0x24的地址需要进行重定位。
...
20: e1 0b 40 b9 ldr w1, [sp, #8]
24: 00 00 00 94 bl 0x24 <ltmp0+0x24> // 重定位到 _sum 符号上
...
这里链接器使用 PIC 的方式生成 a.out。
$ xcrun objdump -d a.out
100003f78: 06 00 00 94 bl 0x100003f90 <_sum> // PC 相对寻址 relocation sum 函数
100003f7c: e0 07 00 b9 str w0, [sp, #4]
100003f80: e0 07 40 b9 ldr w0, [sp, #4]
100003f84: fd 7b 41 a9 ldp x29, x30, [sp, #16]
100003f88: ff 83 00 91 add sp, sp, #32
100003f8c: c0 03 5f d6 ret
0000000100003f90 <_sum>: // sum 函数的 vm 地址
100003f90: ff 43 00 d1 sub sp, sp, #16
即 PC 相对寻址：0x100003f78 + 0x18 = 0x100003f90，这里前文已经详细分析过。在 Linux 系统下，relocation 信息会单独的保存在__DATA_CONST,__GOT 中。在 macOS 下，则直接保存在 relocation 信息中。
lazy binding
前边因为sum函数被一起打包在a.out中，所以可以进行 PC 相对寻址。那如果是调用外部的动态库，PIC 机制又会如何处理呢？
int main() {
int ls = 10;
printf("ls: %d \n", ls);
int s = sum(as, ls);
return s;
}
我们在代码中添加一行printf输出，因为printf属于stdio动态库，这次我们重新编译，链接。
$ clang -c main.c -o main.o
$ clang main.o sum.o
然后查看a.out的动态库绑定的相关信息.
$ xcrun dyldinfo -bind a.out
segment section address type weak addend dylib symbol
__DATA_CONST __got 0x100004000 pointer 0 libSystem _printf
这次看到了__DATA_CONST __got段，保存了_printf的信息，属于libSystem动态库，vm 地址为0x100004000，这个地址并不是_printf符号的真正地址，因为_printf在动态库libSystem中，这里只是一个占位，可以借助 MachOView 来查看一下
内容和上边dyldinfo命令查看的结果是一致的。从程序启动的流程看，启动过程会加载各个动态库的映像，动态库libSystem中会包含_printf符号信息，但此时依然不会解析，因为启动时加载的动态库会非常多，如果都进行解析，会让程序启动非常耗时。真正解析这个符号会推迟到第一调用 printf 函数时，此时只需要单独解析 printf 函数，对性能影响不大。我们继续查看a.out的汇编代码，详细分析一下这个过程。
$ xcrun objdump -d a.out
100003f50: 12 00 00 94 bl 0x100003f98 <_printf+0x100003f98> // bl 跳转 printf 函数
......
Disassembly of section __TEXT,__stubs:
0000000100003f98 <__stubs>: // 开始解析 printf 函数
100003f98: 10 00 00 b0 adrp x16, 0x100004000 <__stubs+0x4> // 0x100004000 属于 __DATA_CONST __got 中 printf 的占位。
100003f9c: 10 02 40 f9 ldr x16, [x16]
100003fa0: 00 02 1f d6 br x16
adrp也是PC相对偏移寻址，只不过是偏移一整页，然后定位到该页的基地址。具体来说
100003f98: 10 00 00 b0 adrp x16, 0x100004000
表示: 将当前PC地址100003f98偏移一整页(page: 4kB = 0x1000)，即 0x100003f98 + 0x1000 = 0x100004f98，然后将低12位(f98)清零(为了得到下一页内存的基地址)，得到0x100004000，这个地址属于__DATA_CONST __gotsection，printf 的占位。程序运行时，首次调用该地址，会发现这是个lazy binding 符号，内核会去libSystem动态库中找到这个符号，并写入到0x100004000地址中。下一步ldr x16, [x16]会把0x100004000地址中，真正的 printf 函数的地址装入，然后进行 br 分支跳转，调用 printf 函数。下次如果还要调用 printf 函数，就不需要再去libSystem中查询，因为0x100004000这个地址中已经记录了printf的真实虚拟地址。
所以总的来看，PIC 可以等价的看做是实现 PC 相对寻址，给各个符号留好坑位，如果是本地的符号会直接链接时绑定，对于调用了外部动态库的函数符号，设定为延迟绑定，延迟到运行时第一次调用该函数。