链接(link)

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调用操作系统中一个叫做加载器(<font style="color:#DF2A3F;">loader</font>)的函数，它将可执行文件prog中的代码和数据复制到内存，然后将控制转移到这个程序的开头。

3️⃣ 静态链接（static linker）

• 定义（静态链接器）
  • 输入：一组可重定向目标文件和命令行参数。
  • 输出：一个完全链接的、可以加载的和运行的可执行目标文件。
• 😈 两个主要任务
  • 符号解析（symbolresolution）
    • 目标文件定义和引用符号。每个符号对应于一个函数、全局变量或静态变量。
    • 符号解析的目的是将每个符号引用正好和一个符号定义关联起来。
  • 重定位（relocation）
    • 输入的可重定位目标文件由各种不同的代码和数据节组成，每一节都是一个连续的字节序列。
    • 编译器和汇编器生成从地址 0 开始的代码和数据节。
    • 链接器通过将每个符号定义与一个内存位置关联起来，从而重定位这些节，然后修改所有对这些符号的引用，使得它们指向这个内存位置。
    • 链接器使用汇编器产生的重定位条目(relocationentry)的详细指令，不加甄别地执行这样的重定位。
• 理解
  • 基本事实
    • 目标文件是字节块的集合。
    • 这些块中，有些包含程序代码，有些包含程序数据，而其他的则包含引导链接器和加载器的数据结构。链接器将这些块连接起来，确定被连接块的运行时位置，并且修改代码和数据块中的各种位置。

1️⃣ 目标文件

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

2️⃣ 可重定位目标文件

• **ELF**_可重定位目标文件格式
  

• 解析

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

3️⃣ 符号

• 符号定义

  • 符号定义指的是在源代码中创建一个符号，并为它分配一个内存位置或者给它一个值。

  • 通常，符号定义是对某个变量或函数的声明和赋值，表示这个符号存在于程序中。

  • 每个符号在程序中只能有一个定义（避免重复定义）。如果有多个定义，链接器会报错。

    // 定义一个全局变量 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是距定义目标的节的起始位置的偏移。

  • 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️⃣ 符号解析

• 定义

  • 链接器解析符号引用的方法是将符号引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。
  • 对那些和引用定义在相同模块中的局部符号的引用，符号解析是非常简单明了的。
    • 编译器只允许每个模块中每个局部符号有一个定义。
    • 静态局部变量会有本地符号，编译器还要确保它们拥有唯一的名字。
  • 全局符号的引用解析就棘手得多

    • 当编译器遇到一个不是在当前模块中定义的符号（变量或函数名）时，会假设该符号是在其他某个模块中定义的，生成一个链接器符号表条目，并把它交给链接器处理。

    • 如果链接器在它的任何输入模块中都找不到这个被引用符号的定义，就输出一条错误信息并终止。

      void foo(void);
      
      int main()
      {
          foo();
          return 0;
      }

  • 编译器可以运行，但是链接器无法解析对foo的引用。

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

  • 问题

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

  • 解决方法

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

  • 链接器处理规则

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

  • 示例代码 一

    int main()
    {
        return 0;
    }

    int main()
    {
        return 0;
    }

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

  • 下述代码同理（根据规则）

    int x = 15213;
    int main()
    {
        return 0;
    }

    int x = 15213;
    
    void f()
    {}

• 😈 与静态库的链接

  • 静态库

    • 迄今，我们都是假设链接器读取一组可重定位目标文件，并把它们链接起来，形成一个输出的可执行文件。
    • 实际上，所有的编译系统都提供一种机制，将所有相关的目标模块打包成为一个单独的文件，称为静态库（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
        • 静态库的使用

        #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是一个有符号常数，一些类型的重定位要使用它对被修改引用的值做偏移调整。

  • 😈 代码示例

    extern int global_var;  // 引用外部变量
    
    void foo() {
        printf("%d\n", global_var);  // 需要链接器来处理地址
    }

    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函数的返回值，并且在需要的时候把控制返回给内核。