深入理解计算机之链接

链接基本概念

链接就是将各种代码和数据片段收集并整合成一个单一的文件的过程。这个过程可以在编译时完成，也可以在文件加载到内存时由加载器完成，甚至也可以在程序运行时完成。
以下面的两段代码为例：

/* /link/main.c */
int sum(int *a, int n);
int array[2] = {1, 2};
int main()
{
    int val = sum(array, 2);
    return val;
}

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

这是一个简单求数组元素之和的程序，但代码被分在两个源文件中，当执行gcc -Og -o prog main.c sum.c时，gcc提供的编译器驱动程序会依次调用预处理器、编译器、汇编器、链接器，并最终形成一个可执行文件prog。当我们在Shell里输入./prog时，Shell会调用操作系统中一个叫加载器的函数，将prog加载到内存中。
可以看出，源文件要变成一个可执行文件，要经历4个过程，其中，每个源文件都会独自经过前3个过程，而最后一步链接器则是将每个源文件生成的.o文件以及一些必要的系统目标文件组合起来，形成一个可执行文件prog。

链接过程.PNG

静态链接

关于静态链接，这里就截取csapp里的几段话，其总结的很好：

静态链接.PNG

目标文件

目标文件分为三种：

目标文件.PNG

编译器和汇编器生成可重定位目标文件和共享目标文件，链接器生成可执行目标文件。
不同操作系统上，目标文件有不同的格式，Windows使用PE(Portable Executable)格式，MacOS-X使用Mach-O格式，Linux和Unix则使用ELF(Executable and Linkable Format)格式。

可重定位目标文件

ELF文件.PNG

ELF头以一个16字节的序列开始，这个序列描述了生成该文件的系统的字大小和字节顺序。ELF头剩余部分包含了帮助链接器语法分析和解析目标文件的信息，包括ELF头的大小、目标文件的类型（可重定位、可执行或者共享的）、机器类型（如x86-64）、节头部表的文件偏移，以及节头部表中条目的大小和数量。不同节的位置和大小是由节头部表描述的，其中每个节在节头部表中都有一个固定大小的条目。

• .text
  已编译程序的机器代码
• .rodata
  只读数据
• .data
  已初始化的全局和静态C变量。
• .bss
  未初始化的全局和静态C变量，以及初始化为0的全局、静态C变量。
• .symtab
  程序里定义和引用的函数和全局变量的信息。
• .rel.text
  代码的重定位条目
• .rel.data
  初始化了的数据重定位条目
• .strtab
  主要存储.systab和.debug里符号的名称。

符号和符号表

每一个可重定位目标模块m都有一个符号表（.symtab），它包含m定义和引用的符号信息。有3种不同的符号：

• 由模块m定义并能被其它模块引用的全局符号（全局链接器符号），对应于非静态的C函数和全局变量。
• 只能被模块m定义和引用的局部符号，对应于带static属性的C函数和全局变量。
• 由其它模块定义并被模块m引用的全局符号，这些符号称为外部符号，对应于在其它模块中定义的非静态C函数和全局变量。

需要着重注意的一点是，.symtab中不包含非静态的过程变量，这些变量是由运行时的栈来管理的，链接器对它们不感兴趣。而对于带有static修饰的过程变量，可以看下面的截图：

无static修饰的过程变量.PNG
符号表是由汇编器构造而成的，使用由编译器输出到.s文件里的符号。符号表的内容主要是一个由条目组成的数组，每个条目的结构如下： 符号表条目.PNG

• name字段是.strtab中的字节偏移
• value字段是符号的地址；对于可重定位模块，value表示的是在对应节里的字节偏移（可用于符号解析）；对于可执行目标文件，value表示的是绝对的运行地址（可用于重定位）。
• type字段一般用于区别数据或函数。
• size字段表示的是目标的大小。
• binding字段表示符号是本地的还是全局的。
• section字段是在节头部表中的索引，每个符号都被分配到目标文件中的某个节。

可重定位目标文件有3个伪节（仅可重定位目标文件有），它们在节头部表中没有对应的条目：ABS用来记录那些不应该被重定位的符号；UNDEF用来记录那些本模块引用，但在别的模块定义的符号；COMMON用来记录那些还未重定位的未初始化的数据符号，同时，对于COMMON符号，value表示的是它的对齐要求，size表示它的最小大小。

COMMON节与.bss的差别比较细微： COMMON和.bss.PNG

符号解析

链接器通过将每个引用与其输入可重定位目标文件的符号表中的符号定义精确地关联来解析符号引用。对于定义和引用都在同一个模块的本地符号，解析十分简单，因为每一个模块的本地符号，编译器只允许有一个定义。
但对于全局符号的解析就比较麻烦，因为多个可重定位目标文件可能会定义相同名字的全局符号。在编译时，编译器向汇编器输出的每个全局符号，或者是强或者是弱，而汇编器把这个信息隐含地编码在可重定位目标文件的符号表里。函数和已初始化的全局变量是强符号，未初始化的全局变量是弱符号。
而Linux链接器则使用下面的规则来处理多重定义的符号：

多重定义符号选择规则.PNG
这种特性有时候会造成一些奇怪的错误，比如下列代码：

/* foo5.c */
#include <stdio.h>
void f(void);
int x = 15213;
int y = 15212;

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

/* bar5.c */
double x;

void f()
{
     x = -0.0;
}

根据规则2，链接器会选择foo5.c里的x，但在bar5.c里的函数f将x作为double型进行了赋值。因此函数f会将foo5.c里定义的x和y都覆盖掉（4+4=8）。在多人协作的情况下，这种错误不容易发现。

COMMON和.bass区别的原因.PNG
附：
重载.PNG

与静态库链接

链接demo.PNG 调用链接库.PNG

静态库：相关的函数编译成单独的可重定位目标文件，然后存入到一个静态库文件中，这个静态库文件其实就是一个archive包，里面有若干个可重定位目标文件。在链接时，链接器只会取出静态库里被引用的目标模块。

与静态库链接.PNG

创建静态库：

linux>gcc -c addvec.c multvec.c
linux>ar rcs libvector.a addvec.o multvec.o
linux>gcc -c main2.c
linux>gcc -static -o prog2c main2.o ./libvector.a

链接器解析过程

在符号解析阶段，链接器是从左往右逐个扫描可重定位目标文件和静态库文件，这些文件的顺序是由出现在编译器驱动程序的命令行参数的顺序决定的。
在这次扫描中，链接器会维护一个可重定位目标文件的集合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中的目标文件，构成可执行文件。

需要注意的是，命令行上库和目标文件的顺序非常重要，如果定义一个符号的库出现在引用这个符号的目标文件的前面，那么引用就不能被解析，链接会失败。关于库的一般准则是将它们放在命令行的结尾。

重定位

一旦链接器完成了符号解析，就把代码中的每个符号引用和符号定义（即输入目标模块中符号表里的条目）关联起来。现在就可以开始重定位步骤了，由两步组成：

1. 链接器将所有相同类型的节合并为同一类型的聚合节。然后链接器将运行时内存地址赋给新的聚合节，以及每个符号。当这一步完成时，程序中的每条指令和全局变量都有唯一的运行时内存地址了。
2. 链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。在这一步，链接器依赖于由汇编器生成的重定位条目，再节合已确定运行位置的节和符号，就可以修改代码里对符号的引用。

当汇编器生成一个目标模块时，它并不知道数据和代码最终将放在内存中的什么位置，它也不知道这个模块引用的任何外部定义的函数或者全局变量的位置。所以，无论何时汇编器遇到对最终位置未知的目标引用，它就会生成一个重定位条目，告诉链接器如何修改这个引用。代码的重定位条目放在.rel.text中，已初始化数据的重定位条目放在.rel.data中。 重定位条目.PNG
在还没有进行重定位前，每个可重定位目标文件里对符号的引用都用0作为占位符表示： 未重定位的目标文件.PNG
重定位后： 重定位后目标文件的.txt节.PNG
可以看出，重定位后，代码里符号引用处的字节被改变了。在加载的时候，加载器会把这些节中的字节直接复制到内存，不再进行任何修改地执行这些指令。

可执行目标文件

可执行目标文件.PNG
可执行文件连续的片于内存连续段之间的映射关系由段头部表描述： 可执行文件的头部表.PNG

从上图可以看出，内存将被可执行目标文件的内容初始化为两个内存段。第1行和第2行告诉我们第一个内存段（代码段）具有读/执行权限，开始于内存地址0x400000处，总内存大小为0x69c字节，并且被初始化为可执行目标文件的头0x69c字节，其中包括ELF头、段头部表、.init、.text和.rodata节。

第3行和第4行告诉我们第二个段（数据段）具有读/写权限，开始于内存地址0x600df8处，总内存大小为0x230字节，并且被从目标文件偏移0xdf8处开始的.data节中的0x228个字节初始化。该段剩余的8个字节对应于运行时将被初始化为0的.bss数据。 对齐要求.PNG

加载可执行目标文件

要运行可执行目标文件prog，直接在Linux shell的命令行中跳转到对应目录然后输入./prog即可。shell会
调用一个称为加载器的操作系统代码来运行程序，另外一提的是，任何Linux程序都可以通过调用execve函数来调用加载器。加载器将可执行目标文件里的代码和数据从磁盘加载到内存，然后跳转到程序的第一条指令或入口点来运行该程序。这个将程序复制到内存并运行的过程称为加载。
每个Linux程序都有一个运行时内存映像，如下图所示：

Linux程序运行时内存映像.PNG Linux程序运行时内存.PNG
加载器在运行时，它创建类似上图的内存映像。在段头部表的引导下，加载器将可执行文件的片复制到代码段和数据段，接下来，加载器跳转到程序的入口点，也就是_start函数的地址。这个函数是在系统目标文件ctrl.o中定义的，对所有的C程序都是一样的。_start函数调用系统启动函数__libc_start_main，该函数定义在libc.so中。它初始化执行环境，调用用户层的main函数，处理main函数的返回值，并且在需要的时候把控制返回给内核。 加载器工作概述.PNG
加载器.PNG

动态链接共享库

静态链接库的两个缺点：

• 当静态库更新后，我们总需要重新进行链接形成新的可执行目标文件。

• 大多数程序都会使用到相同的库函数，在运行时，这些库函数的代码都会复制到每个进行的代码段中去，这对内存是一种浪费。
  

  共享库： 共享库.PNG
  共享库的两种共享： 共享库的共享方式.PNG
  动态链接过程： 动态链接过程.PNG
  创建动态链接库命令.PNG

当加载器加载和运行部分链接的可执行文件prog21时，它注意到prog21包含一个.interp节，这个节包含动态链接器的路径名，动态链接器本身就是一个共享目标（如在Linux系统上的ld-linux.so）。加载器不会像它通常所做的那样将控制传递给应用，而是加载和运行这个动态链接器。然后，动态链接器通过执行下面的重定位完成链接任务：

• 重定位libc.so的文本和数据到某对应内存段。
• 重定位libvector.so的文本和数据到另外的对应内存段。
• 重定位prog21中所有由libc.so和libvector.so定义的符号和引用。

最后，动态链接器将控制传递给应用程序。从这个时刻开始，共享库的位置就固定了，并且在程序执行的过程中都不会改变。

从应用程序中加载和链接共享库

前面讨论的是应用程序在加载后执行前时，动态链接器加载和链接动态库的情景。然后，应用程序还可以在它运行时要求动态链接器加载和链接某个动态库。
Linux系统提供了一个简单的接口，允许应用程序在运行时加载和链接共享库：

#include <dlfcn.h>
void *dlopen(const char *filename, int flag);//返回：若成功则为指向句柄的指针，若出错则为NULL。
void *dlsym(void *handle, char *symbol);//返回：若成功则为指向符号的指针，若出错则为NULL。
int dlclose(void *handle);//返回：若成功则为0，若出错则为-1。
const char *dlerror(void);//返回：如果前面对dlopen、dlsym或dlclose的调用失败，则为错误消息，如果前面的调用成功，则为NULL。

dlopen函数加载和链接共享库filename。filename里面的外部符号则通过在它前面以RTLD_GLOBAL标志打开的共享库来解析。如果可执行文件是带-rdynamic标志编译的，那么它的全局符号也是可以被后面的共享模块用于符号解析的。flag参数必须要么包括RTLD_NOW,该标志告诉链接器立即解析共享库里对外部符号的引用，要么包括RTLD_LAZY标志，该标志指示链接器推迟符号解析直到执行来自库中的代码。
dlsym函数的输入是一个指向前面已经打开了的共享库句柄和一个symbol名字，如果该符号存在，就返回符号的地址，否则返回NULL。
如果没有其它模块还在使用这个共享库，dlclose函数就卸载该共享库。
dlerror函数返回一个字符串，它描述的是调用dlopen、dlsym、或者dlclose函数时发生的最近错误，如果没有错误，则返回NULL。

linux>gcc -rdynamic -o prog2r dll.c -ldl
------------------------------------code/link/dll.c
#include <stdio.h>
#include <stdlib.h>
#include <dlfcn.h>
int x[2] = {1, 2};
int y[2] = {3, 4};
int z[2];
int main()
{
     void *handle;
     void (*addvec)(int *, int *, int *, int);
     char *error;
     handle = dlopen("./libvector.so", RTLD_LAZY);
     if (!handle)  {
         fprintf(stderr, "%s\n", dlerror());
         exit(1);
     }
     addvec = dlsym(handle, "addvec");
     if ((error = dlerror()) != NULL)  {
         fprintf(stderr, "%s\n", error);
         exit(1);
     }
     addvec(x, y, z, 2);
     printf("z = [%d %d]\n", z[0], z[1]);
     if (dlclose(handle) < 0)  {
         fprintf(stderr, "%s\n", dlerror());
         exit(1);
     }
     return 0;
}

JAVA本地调用.PNG

位置无关代码

位置无关代码.PNG
PIC数据引用： PIC数据调用.jpg
PIC函数调用：
PIC函数引用.PNG 在进行第一次PIC函数调用时动态链接器才会进行重定位解析，具体流程见上图。

库打桩机制

库打桩.PNG

目标文件工具

目标文件工具.PNG