链接 | W41ter’s Bistro

链接是把各种代码、数据收集起来组合成单一文件的过程，这个文件可以被加载到内存中执行。在实际开发中，会将项目分散成小的、更容易管理的模块，然后独立的修改和编译这些模块。链接则是将各个模块组合成可执行文件的过程。

链接通常由链接器完成，不过现代编译器或编译环境已经处理了链接过程，需要手动使用链接器完成的场景已经很少了。大多数现代编译系统提供了编译驱动程序，它可以依次使用预处理、编译、汇编、链接器来完成编译到链接的过程，不需要用户干预。

比如由a.c和b.c两个文件，在编译驱动程序的帮助下，可以使用简单命令完成：

gcc -o program a.c b.c

上述命令等价于下面这些命令：

cpp a.c a.i
cpp b.c b.i
cc1 a.i -o a.S
cc1 b.i -o b.S
as -o a.o a.S
as -o b.o b.S
ld -o program a.o b.o

上述过程依次调用预处理、编译、汇编和链接器，最终生成了可执行文件。

像ld程序这样的静态链接器以一组可重定位的目标文件和参数作为输入，生成完全链接的可执行目标文件。可重定位目标文件由一系列的节(section)组成。

可重定位目标文件

目标文件有三种

可重定位目标文件
可执行目标文件
共享目标文件

这里只关心可重定位目标文件，它包含了二进制代码和数据，不过其中的信息并不完善，需要和其他文件一起才能组成一个可执行目标文件或者共享目标文件。

所谓可重定位，是指包含的二进制代码中有引用到其他模块的，由于不知道其他模块中二进制代码布局，所以留了空等待回填。使用例子更方便理解可重定位目标文件。假设有下面的代码：

#include <stdio.h>

int a, a1=1;

int main(void) {
  static int b = 1;
  static int c;

  printf("hello world", a, b);

  return 0;
}

将之命名为hello.c，然后使用命令生成重定位目标文件：

gcc -c hello.o hello.c

此时hello.o便是可重定位目标文件，使用objdump -h hello.o可以看看可重定位目标文件的节(section)：

/mnt/d/tmp$ objdump -h hello.o

hello.o:     file format elf64-x86-64

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  0 .text         00000028  0000000000000000  0000000000000000  00000040  2**0
                  CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE
  1 .data         00000008  0000000000000000  0000000000000000  00000068  2**2
                  CONTENTS, ALLOC, LOAD, DATA
  2 .bss          00000004  0000000000000000  0000000000000000  00000070  2**2
                  ALLOC
  3 .rodata       0000000c  0000000000000000  0000000000000000  00000070  2**0
                  CONTENTS, ALLOC, LOAD, READONLY, DATA
  4 .comment      00000035  0000000000000000  0000000000000000  0000007c  2**0
                  CONTENTS, READONLY
  5 .note.GNU-stack 00000000  0000000000000000  0000000000000000  000000b1  2**0
                  CONTENTS, READONLY
  6 .eh_frame     00000038  0000000000000000  0000000000000000  000000b8  2**3
                  CONTENTS, ALLOC, LOAD, RELOC, READONLY, DATA

Idx 是编号，Name 是节点名称，Size 是节大小，VMA 是在虚拟内存中的起点，LMA 是节的装载地址（除了ROM之外，通常与 VMA 相同），File off 是在文件中的具体偏移，Algn 是对齐地址。各节第二行描述了节的属性。CONTENTS 表示节在文件中占用了内存空间，ALLOC 则表示需要分配内存，RELOC 表示需要重定位。

.text 包含了已编译程序的二进制代码，.data是已经初始化的全局C变量或静态局部变量，.bss是未初始化的全局变量或静态局部变量，rodata包含只读数据。其他的数据暂时可以不用关心。

观察符号表来说明符号所在section：

/mnt/d/tmp$ objdump -t hello.o

hello.o:     file format elf64-x86-64

SYMBOL TABLE:
0000000000000000 l    df *ABS*  0000000000000000 hello.c
0000000000000000 l    d  .text  0000000000000000 .text
0000000000000000 l    d  .data  0000000000000000 .data
0000000000000000 l    d  .bss   0000000000000000 .bss
0000000000000000 l    d  .rodata        0000000000000000 .rodata
0000000000000004 l     O .data  0000000000000004 b.2288
0000000000000000 l     O .bss   0000000000000004 c.2289
0000000000000000 l    d  .note.GNU-stack        0000000000000000 .note.GNU-stack
0000000000000000 l    d  .eh_frame      0000000000000000 .eh_frame
0000000000000000 l    d  .comment       0000000000000000 .comment
0000000000000004       O *COM*  0000000000000004 a
0000000000000000 g     O .data  0000000000000004 a1
0000000000000000 g     F .text  0000000000000028 main
0000000000000000         *UND*  0000000000000000 printf

各列分别是解内偏移，标记位，所在节，对齐方式和符号名。ABS 表示这是一个不和任何节相关的绝对符号，UND则这个符号不在本文件中定义，COM 表示还未分配位置的未初始化数据目标。

a和c没有初始化，放到了.bss节中，b和a1则是放到了.data节中，而mian表示的函数放到了.text节中，printf则是未定义的符号，需要进行重定位。使用objdump -r可以显示可重定位目标文件的重定位项：

/mnt/d/tmp$ objdump -r hello.o

hello.o:     file format elf64-x86-64

RELOCATION RECORDS FOR [.text]:
OFFSET           TYPE              VALUE
0000000000000006 R_X86_64_PC32     .data
000000000000000c R_X86_64_PC32     a-0x0000000000000004
0000000000000013 R_X86_64_32       .rodata
000000000000001d R_X86_64_PC32     printf-0x0000000000000004


RELOCATION RECORDS FOR [.eh_frame]:
OFFSET           TYPE              VALUE
0000000000000020 R_X86_64_PC32     .text

分别表示 .text 和 .eh_frame 节的重定位表。重定位表是在程序中留下的空位所在地方，可以修改代码简单验证一下。

#include <stdio.h>

int a;

int main(void) {
  static int b = 1;

  printf("hello world", a, b);
  printf("hello world", a, b);
  printf("hello world", a, b);
  return 0;
}

这里将printf使用多次，然后看看重定位表：

/mnt/d/tmp$ objdump -r hello.o

hello.o:     file format elf64-x86-64

RELOCATION RECORDS FOR [.text]:
OFFSET           TYPE              VALUE
0000000000000006 R_X86_64_PC32     .data
000000000000000c R_X86_64_PC32     a-0x0000000000000004
0000000000000013 R_X86_64_32       .rodata
000000000000001d R_X86_64_PC32     printf-0x0000000000000004
0000000000000023 R_X86_64_PC32     .data
0000000000000029 R_X86_64_PC32     a-0x0000000000000004
0000000000000030 R_X86_64_32       .rodata
000000000000003a R_X86_64_PC32     printf-0x0000000000000004
0000000000000040 R_X86_64_PC32     .data
0000000000000046 R_X86_64_PC32     a-0x0000000000000004
000000000000004d R_X86_64_32       .rodata
0000000000000057 R_X86_64_PC32     printf-0x0000000000000004


RELOCATION RECORDS FOR [.eh_frame]:
OFFSET           TYPE              VALUE
0000000000000020 R_X86_64_PC32     .text

这样的结果刚好印证了前面的说法。

链接器将可重定位目标文件组合成为可执行或共享目标文件时，必须完成两个任务：

符号解析符号解析是将符号的定义和每次使用联系起来
重定位重定位则是将引用符号时留空填上对应的符号地址

符号解析

链接器解析符号引用的办法是将每个引用与它输入的可重定位目标文件的符号表中一个确定的符号联系起来。如果符号的定义和引用都在同一文件内，解析起来非常方便。如果不是当前模块中定义的符号，则会在其他文件中查找，如果所有文件中都没有，那么会报错。比如对于下面的文件：

void bar(int,int);
int main() {
    bar(0,0);
    return 0;
}

编译器能够正常执行，并生成可重定位目标文件，但是链接器会报错误:

/tmp/cc672f5D.o: In function `main':
test.c:(.text+0x5): undefined reference to `bar'
collect2: error: ld returned 1 exit status

NOTICE: 注意C++中符号的命名不同于C语言（存在重载），所以在C++中可能看到的符号名类似于_Z3barii

当然，如果多个文件中存在多重定义的全局符号，则会按照一定的规则来选出一个符号作为目标符号，具体信息可以查阅相关资料。

重定位

你可能已经注意到在重定位表中存在这两种不同类型的重定义R_X86_64_PC32和R_X86_64_32。

前一种表示使用32位PC相对地址引用，比如pc+4之类的值，所以此处应该回填目标符号和当前符号的相对地址。

后一种表示使用32位绝对地址引用，说明此处可以直接填上符号的绝对地址，比如jmp bar。

链接器在所有的符号查找完成的同时记录下其真正的地址。链接器重定位算法大概如下：

foreach section s {
  foreach relocation entry r {
    refptr = s + r.offset;
    if (r.type == XXXX_PC32) {
      refaddr = ADDR(s) + r.offset;
      *refptr = ADDR(r.symbol) + *refptr - refaddr;
    }
    if (r.type == XXXX_32) {
      *refptr = ADDR(r.symbol) + *refptr;
    }
  }
}

其中的ADDR()表示了指定符号的真正地址。对于相对地址，首先用节的真实地址（这就是为甚么符号表中竟然含有节名）和符号在节中的偏移计算出需要回填的位置在内存中的真实地址。然后通过所引用符号的内存地址计算出其偏移。可能不能理解的是为何算法中加上了*refptr，我们可以看看重定位表项:a-0x0000000000000004，后面的值实际上就是*refptr的值。这样做可以在不同指令大小和编码方式不同的机器上，使用相同的链接器，即链接器可以透明的重定位引用，而不需要知道具体机器相关的细节。对于绝对地址，已经不需要再过解释。

静态链接库

有时会用到一些第三方提供的库文件，但是只用到其中一两个函数，而整个文件非常大，感觉非常不合算。比如标准库函数，如果我们只需要一个printf却把整个标准库包含进去，得不偿失。此时静态库的概念被提出来，将所有相关的目标模块打包成为一个单独的文件，然后链接器链接的时候，只拷贝被程序引用到的目标模块或函数。

共享库与位置无关代码

比如使用标准库，每个程序都拷贝一份标准库代码，如果 PC 中运行着非常多的程序时，那么标准库拷贝也会被复制多份，因此提出了共享库的概念。使用共享库，将原有的拷贝代码到程序中的方式改为 PC 中只运行一份代码库，所有程序中均调用该共享库的实例。共享库是一个目标模块，在运行时随机加载到储存器的任意地址，并和一个在储存器中的程序链接起来。这个过程成为动态链接，是由一个叫动态链接器的程序来执行的。共享库在 Unix 系统中通常使用后缀 so，在 Windows 系统中称为 DLL。

动态库是随机加载到存储器中，而用户程序怎么知道何时何地呢？此时使用叫做位置无关的代码(Position-Independent Code, PIC)来解决。举例来说明为何位置无关代码能解决这个问题，首先假设有 find_func_address 函数用于在共享库中查找目标函数地址：

void *find_func_address(const char *name);

然后在具体的程序中使用共享库并使用内部函数：

/* 假设共享库中有函数 bar，其签名如下 */
typedef void (*Bar)();

/* load library */
Bar bar = (Bar)find_func_address("bar");  

bar(); /* call */

/* release library */

只需要 find_func_address 能找到函数在共享库中的地址，然后在需要的地方查找即可。不过程序员肯定受不了每次使用均调用一次 find_func_address ，并且程序中存在上千甚至更多次引用时，重复加载的效率也非常低。因此可以将代码改写一下：

typedef void (*Bar)();
void bar() {
  static Bar bar_ = (Bar) find_func_address("bar");
  return bar_();
}

...

bar(); /* call */

这里的代码解决了上面的两个问题：1、程序中引用共享库中的 bar 函数只需要使用 void bar() 函数即可；2、利用局部静态变量的初始化特性保证只初始化一次。

注意，上述代码并不是线程安全的，参考：多线程中局部静态变量初始化的陷阱

当然，这部分工作已经由编译器完成，我们不需要操心。在编译器实现中，使用了 GOT (global offset table) 和 PLT (procedure linkage table) 完成，而这个过程称为延迟绑定(lazy binding)。所谓延迟绑定，就是将过程地址的绑定推迟到第一次调用该过程（函数）时。每个函数均有对应的 GOT 表项和 PLT 表项，如果将之和上面的代码对应，那么 GOT 表项相当于 void bar()，而 PLT 表项相当于 static Bar bar_ = (Bar) find_func_address("bar");。在使用延迟绑定技术时，用户调用了共享库函数，此时 IP 跳转到该函数的 GOT 表项所在位置；对于首次调用，GOT 表项填着 PLT 表项地址，所以 IP 继续跳转到 PLT 表项所在位置，而 PLT 负责完成查找函数地址，并将地址保存到 GOT 表项，然后跳转到 GOT 表项从新执行；对于非首次访问，直接跳转到 GOT 所在地址，完成调用过程。

references

[1] 深入理解计算机系统 [2] Objdump 使用