程序链接过程详解

发表于2022-05-20更新于2023-04-25字数统计4k阅读时长16分阅读次数

前言

链接可以将多个目标文件合并为一个可执行文件，这使得分离编译成为了可能。通常一个项目由多个文件组成，这些文件可以分别编译为目标文件(Windows下为.obj，Unix下一般命名为.o文件)，链接器通过符号识别和重定位等方法解决不同目标文件中的符号引用问题，最终生成可执行文件。链接分为静态链接和动态链接，本文将分别介绍其原理。文中大量图和例子来源于参考文献。

目标文件

目标文件共有三种形式：「可重定位目标文件」、「可执行目标文件」、「共享目标文件」。编译器和汇编器将源程序进行编译和汇编生成二进制可重定位目标文件，链接器将多个可重定位目标文件进行链接生成可执行目标文件，共享目标文件是一种特殊的可重定位目标文件，可以在加载或运行时被动态地进行链接。

为了搞清楚链接过程，首先需要知道可重定位目标文件的结构，这里以Unix系统中的ELF(Executable Linkable Format)格式文件为例。典型的可重定位目标文件结构如下：

实际上，一个源文件编译成为目标文件之后，目标文件中肯定会包含程序指令、全局变量和静态变量(局部变量在运行时栈上分配)。实际上，除了上面说到的内容之外，还有一些额外的内容，这些内容用于指示链接器进行链接。从图中我们可以看出，目标文件将内容分为很多个节(section)，也称为段，各段的含义如下：

  • .text：用于存放程序的机器指令代码。
  • .rodata：用于存放只读数据。通常是一些字符串和const修饰的变量。
  • .data：已初始化的全局和静态(static)变量。
  • .bss：存放未初始化的全局变量和静态变量，以及初始化为0的全局或静态变量。实际上，该段在目标文件中并不占据实际空间，这些变量会被默认初始化为0，所以不将它们放在.data段，在程序执行时在内存中分配这些变量，目的是节省磁盘空间。
  • .symtab：符号表，存放程序中定义和引用的函数和全局变量信息。
  • .rel.text：.text段的重定位表，因为单独编译得到的目标文件有很多函数和变量引用地址是未确定的，这个段就是用于.text段重定位(在静态链接时还会介绍)。
  • .rel.data：.data段的重定位表。
  • .debug：调试符号表，使用-g选项编译时生成，存放用于调试的符号。
  • .line：存放源程序中行号和.text段中指令的映射。
  • .strtab：字符串表，存储各种其他段使用的字符串。

静态链接

考虑最简单的例子：

main.c:

1
2
3
4
5
6
7
extern int shared;
void swap(int*, int*);

int main() {
    int a = 64;
    swap(&a, &shared);
}

swap.c:

1
2
3
4
5
6
7
int shared = 1;

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

将其分别编译得到目标文件，得到main.o和swap.o：

1
gcc -c main.c swap.c

其中main.c文件引用了swap.c文件中的shared变量和swap函数。静态链接主要解决以下两个主要问题：「符号解析」和「重定位」。

符号解析

main.c文件编译得到的main.o目标文件中，显然是有对swap和shared的引用，我们看一下main.o的符号表(也就是.symtab段的内容)：

1
readelf -s main.o
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Symbol table '.symtab' contains 14 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS main.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1 
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    3 
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    4 
     5: 0000000000000000     0 SECTION LOCAL  DEFAULT    6 
     6: 0000000000000000     0 SECTION LOCAL  DEFAULT    7 
     7: 0000000000000000     0 SECTION LOCAL  DEFAULT    8 
     8: 0000000000000000     0 SECTION LOCAL  DEFAULT    5 
     9: 0000000000000000    77 FUNC    GLOBAL DEFAULT    1 main
    10: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND shared
    11: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND _GLOBAL_OFFSET_TABLE_
    12: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND swap
    13: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND __stack_chk_fail

我们可以看到有 shared 和 swap符号，且所属的段都是UND，也就是未定义的符号，说明这两个符号是在外部定义的。当链接时没有另一个含有这些符号的目标文件参与时，将会得到undefined reference错误。

1
ld main.o

结果：

1
2
3
4
ld: main.o: in function `main':
main.c:(.text+0x29): undefined reference to `shared'
ld: main.c:(.text+0x2e): undefined reference to `swap'
ld: main.c:(.text+0x49): undefined reference to `__stack_chk_fail'

重定位

我们先看main.o反汇编的结果：

1
objdump -dx main.o
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Disassembly of section .text:

0000000000000000 <main>:
   0:   f3 0f 1e fa             endbr64 
   4:   53                      push   %rbx
   5:   48 83 ec 10             sub    $0x10,%rsp
   9:   bb 28 00 00 00          mov    $0x28,%ebx
   e:   64 48 8b 03             mov    %fs:(%rbx),%rax
  12:   48 89 44 24 08          mov    %rax,0x8(%rsp)
  17:   31 c0                   xor    %eax,%eax
  19:   c7 44 24 04 40 00 00    movl   $0x40,0x4(%rsp)
  20:   00 
  21:   48 8d 7c 24 04          lea    0x4(%rsp),%rdi
  26:   48 8d 35 00 00 00 00    lea    0x0(%rip),%rsi        # 2d <main+0x2d>
                        29: R_X86_64_PC32       shared-0x4
  2d:   e8 00 00 00 00          callq  32 <main+0x32>
                        2e: R_X86_64_PLT32      swap-0x4
  32:   48 8b 44 24 08          mov    0x8(%rsp),%rax
  37:   64 48 33 03             xor    %fs:(%rbx),%rax
  3b:   75 0b                   jne    48 <main+0x48>
  3d:   b8 00 00 00 00          mov    $0x0,%eax
  42:   48 83 c4 10             add    $0x10,%rsp
  46:   5b                      pop    %rbx
  47:   c3                      retq   
  48:   e8 00 00 00 00          callq  4d <main+0x4d>
                        49: R_X86_64_PLT32      __stack_chk_fail-0x4

首先可以看到，<main>的地址为0，所以并不是最终运行时的函数地址，因为这个目标文件还没有进行符号解析和重定位。

观察 26 和 2d 处的两条指令，第一条是将shared变量的地址放入%rsi寄存器，第二条是调用swap函数，main.o是单独编译的，在编译的时候并不知道shared变量和swap函数的地址，因此实际上这两个地址都是假地址，需要在最终静态链接的时候进行重定位。在main.o中，地址都暂时以0进行代替，即对shared的引用暂时是相对%rip寄存器地址为0的地址，对swap引用的地址偏移量也为0.

重定位主要由以下两个步骤：

  1. 将不同目标文件的同类型的段进行合并，例如将main.o和swap.o的.text段进行合并，这这一步完成之后，程序中每条指令和变量的地址都是确定的。
  2. 链接器对上述合并后的.text段和.data段中的每个符号引用地址进行修改，将之前的占位地址修改成引用符号的真实地址。

编译器生成目标文件时，当遇到引用的外部定义的函数或变量时并不知道其位置，这时候会生成一个「重定位条目」，用于告诉链接器如何修改最终的地址。指令的重定位条目放置在.rel.text段中，数据的重定位条目放在.rel.data段中。

重定位条目内容如下：

1
2
3
4
5
6
typedef struct {
    long offset; /* 待重定向符号的段偏移 */
    long type:32, /* 重定位类型 */
    symbol:32; /* 重定位符号在符号表中的索引 */
    long addend; /* 地址修正时用到的常数 */
} Elf64_Rela;

重定位类型指示了重定位地址的计算方法，从上面的反汇编结果可以看到，shared变量的重定位类型为：R_X86_64_PC32，而swap函数的重定位类型为：R_X86_64_PLT32(这个结果和书上的都不一样，应该是编译器版本的缘故，书上是相对地址引用和绝对地址引用两种类型，我机器上只有相对地址引用的类型)。

现在我们来看怎么得到修正后的地址，实际的shared地址实际上在各段合并之后就是已知的，这个地址在我机器上是：addrtrueaddr_{true} = 0x4010，引用shared的指令的地址也是已知的：addrsymaddr_{sym} = 0x1176，因此修正的地址为两者之差：

addrm=addrtrue−addrsym=0x2e9aaddr_m = addr_{true} - addr_{sym} = 0x2e9a

swap函数也是以类似的方法修正地址，现在看一下链接之后被修正过的地址：

1
2
gcc -o main main.o swap.o
objdump -d main

可以看到，链接之后，shared变量的地址相对偏移量修正为0x2e9a，swap变量的地址相对偏移量修正为1b，也就是跳转到1196的位置。

链接之后得到「可执行目标文件」：main，在shell命令行输入运行命令：

1
./main

当shell识别出这个命令不是内置shell命令时，就会将其当作可执行目标文件，将其加载到内存并执行。我们知道操作系统会给任何一个进程这样的假象：每个进程都完全占据了cpu和内存，其每条指令都是顺序执行且内存是线性的连续空间。

在Linux x86-64系统中，代码段总是从地址0x400000处开始，进程的运行时内存映像如下图所示：

再往上是数据段，然后是堆(heap)，这个空间向上(地址增大的方向)增长，用户可以在堆上分配较大的空间。再往上的区域是为共享模块保存的区域，然后就是用户栈(stack)，这个空间是向下(地址减小的方向)增长的，在地址248−12^{48} - 1往上的空间是未内核保留的。

动态链接

前面我们看到了静态链接将多个可重定位目标文件进行符号解析和重定位，然后合并成一个可执行目标文件，这个文件可以直接加载至内存运行。显然这个过程还存在些缺点，比如可能多个程序会使用到相同的库程序，当然这些程序可以分别将这些库程序静态链接至各自的可执行文件中，这样的话会使得内存中有很多份相同的库指令，这是一种对内存空间的浪费。再者，在静态链接中，倘若某个库更新了版本，必须对整个项目进行重新链接。

共享库(shared library，在Windows也称为动态链接库)是为了解决上述问题而产生的。共享库本质上也是一个目标文件，这个目标文件在运行或加载时，可以放在内存的任意地址，并和内存中的程序进行链接。这个过程称为动态链接，由动态链接器(dynamic linker)完成。

我们可以考虑下如何让多个不同的进程共享一份库代码，即让内存中只存在一份库代码。为了保证符号地址引用的正确性，可以让每个进程保留一块固定的地址空间用于存放共享库，如每个进程都将地址0x500000至0x502000的区域用来放模块A，这样可以让不同进程引用这个地址范围内的变量和函数。这样做确实可以实现代码共享，但是当内存中共享库很多的时候将会很难管理。因此，目前通常采用生成位置无关代码的方式来解决这一问题。

位置无关代码

实际上，共享库实现代码共享的最大问题是地址引用问题，现代系统以一种特别的方式编译共享库模块，使得它可以被加载到内存的任何地址而无需链接器修改，可以加载而无需重定位的代码被称为「位置无关代码(Position-Independent Code PIC)」。

对于一个共享目标文件，显然其内部的代码段和数据段之间的相对地址偏移是固定的，因此对于模块内部的变量和函数引用可以使用相对地址引用，这样不管模块被装载到内存的任何位置引用都是生效的。比较棘手的问题是解决共享模块中对于外部其它模块变量和函数的引用问题，我们并不知道这些外部符号被装载在了内存的什么地址。

为了解决这个问题，编译器在编译共享模块时，在其数据段开始的地方创建了一个「全局偏移表(Global Offset Table,GOT)」。这个表记录了共享模块中所有对于外部符号引用的地址条目：

代码段中对这些变量引用就可以使用相对地址引用至这个GOT表中的条目，在共享模块加载至内存中时，动态链接器会重定位GOT中每个条目，而不需要重定位代码段中的地址。例如上面的addvec函数中需要对addcnt变量进行引用，而这个addcnt变量处于另一个共享模块中，在编译时并不知道它的地址，因此需要通过GOT表进行间接引用，在加载的时候动态链接器是知道内存中addcnt变量的地址的，因此可以修正这个GOT条目。

实际上，为了实现代码的共享，动态链接通过GOT表解决了静态链接中的地址重定位问题，或者说将代码中的地址重定位转变为了共享模块加载进内存时由动态链接器进行GOT条目修正，这样代码段相当于是固定的无需修改的，每个进程之间可以共享，而数据段可以不同的进程拥有一份自己的副本。

延迟绑定(PLT)

当调用共享库中函数时，因为共享库可以加载至内存中的任何位置，因此有了上述的GOT表用于修正地址。但是在程序执行时并不是所有的指向外部模块的函数都会被执行，在加载程序时一次性将所有GOT表条目地址都修正是一种浪费。因此可以采用「延迟绑定(Lazing Binding)」的方法，在函数第一次被调用的时候修正其GOT相关条目，没有执行的函数不进行GOT地址修改。

延迟绑定的基本思想如上，实际实现通过增加一个过程链接表(PLT)来实现：

当第一次调用动态库中的函数时，会跳转到PLT表中相关的条目，上图中调用函数addvec时跳转到PLT[2]，而每个PLT条目和GOT表中的一个条目对应，因此其跳转至GOT[4]处。由于第一次调用函数，GOT表相关条目地址并没有被修正，且其初始值被设置为PLT表条目的下一条指令pushq $0x1，这个指令将addvec符号在.rel.plt表中的下标1压入堆栈中，然后跳转至PLT[0]条目，这个条目是一个特殊条目，其指向动态链接器，动态链接器根据栈中的下标来修正addvec函数在GOT表中的地址。最后再将控制交给addvec，这个函数再次调用时，因为其GOT表中条目地址已被修正，因此不需要再执行上述复杂步骤，而是直接执行。

总结

本文介绍了链接的具体实现过程，先介绍了目标文件的类型和基本内容，然后分别介绍了静态链接和动态链接的具体实现。文中很多示例和图都来源于《深入理解计算机系统3th》和《程序员的自我修养》，在参考文献中也将列出。

参考文献

  1. 《深入理解计算机系统》(CS:APP 3th)
  2. 《程序员的自我修养》