[编译链接装载]之静态链接

原 作者 杜肖孟 | 发表于 | 分类于 2015级

链接器之所以存在或者产生，基本上是由于程序开发的模块化。这里讲的模块，主要是编译概念上的模块，通常他们按照功能划分，比如一个.c或者.cpp文件就是一个编译单元，就是一个模块，编译后就产生一个.o目标文件。为了最终生成一个可执行文件、静态库或者动态库，就需要把各个编译单元按照特定的约定组合到一起。这里特定的约定指的就是“目标文件格式”，它定义了目标文件、库文件和可执行文件的格式，这里组合这一过程就叫做链接。

链接主要有以下几个任务：空间与地址分配，符号解析，重定位，昨天晚上回宿舍躺床上后，一直在想这几个过程，哪个先进行，哪个后进行，试图从目标文件开始理清链接进行的顺序，知直到生成可执行文件。但是我失败了，索性不管了，我大概清楚这几个过程都做了什么工作就好，如果纠结的失眠了第二天就起不来了=_=。用到的样例代码 在文末。

空间与地址分配

主流操作系统中，可执行文件都是基于虚拟地址空间的，即每个可执行文件都有相同且独立的地址空间，并且文件中各个段（代码段，数据段，以及进程空间中的堆栈段）都有相似的布局。在 Linux 下，ELF 可执行文件默认从地址 0x08048000 开始。而普通目标文件却使用从零开始的地址空间，这样一来，模块M中的符号m就可能和模块N中的符号n拥有“相同”的地址。

链接器链接各个模块时，扫描所有的模块，获得它们的各个section 的长度、属性和位置，将具有相同性质的 section 合并，并将合并后的段写入可执行文件中，这个过程叫做存储空间的分配。同时计算出可执行文件中各个段合并后的长度和位置，整理目标文件中所有的符号定义和符号引用，统一放到一个全局符号表中，链接器由此决定一个符号在哪里被定义，在哪里被引用。

符号地址的确定

空间分配完之后，目标文件中的各个 section 在链接后的虚拟地址就已经确定了。接下来开始计算各个符号的虚拟地址。

各个符号在 section 内的相对位置是固定的（就是相当于段内偏移量的概念），所以这时候其实这些符号的地址已经是确定的了，链接器必须给每个符号加上一个偏移量，使它们能够调整到正确的虚拟地址。比如假设 ”a.o“ 中的 ”main“ 函数相对于 “a.o” 中的 “.text” 的偏移是 X，但是经过链接合并之后，”a.o” 的 “.text” 位于虚拟地址 0x08048094，那么 “main” 的地址应该是 0x08048094+X。

通过相同的计算方法得知所有符号的地址后，链接器更新全局符号表。

符号解析

符号解析就是将每个引用与输入的目标文件中的符号表中的一个确定的符号联系起来。对于引用和定义在模块内部的符号，符号解析非常简单明了，直接就找到了。编译器只允许每个文件中每个全局符号只有一个定义。

通常的观念是，之所以要链接是因为我们目标文件中用到的符号被定义在其他目标文件中，我们要将它们解析出来。比如直接链接 “a.o”，链接器就会发现 shared 和 swap 两个符号没有被定义。

这里写图片描述

这也是我们经常碰到的问题之一，比如缺少某个库，或者符号的声明与定义不一样。我们直接引用了某个变量或者函数，但是符号解析的时候没找到对应的定义。

编译只是针对单个文件，当编译器遇到一个不是在当前文件中定义的符号时，它会假设该符号是在其他文件中定义的，生成一个链接器符号表条目，并把它交给链接器处理。所以编译的时候不会报错，但是链接的时候，链接器搜索所有的输入目标文件的符号表后，当发现无法解析对此符号的引用时，就会报错。

多重定义

还有一个棘手的问题是，多个目标文件可能会定义相同的符号。请跳转到后面：强符号与弱符号。

链接器如何使用静态库来解析引用

假设输入了若干目标文件和库文件给链接器去生成可执行文件，链接器从左到右按照它们在命令行上出现的顺序来扫描，在扫描的过程中，链接器维护了3个集合：E 表示需要合并到可执行文件中目标文件集合；U 表示未解析的符号集合，即被引用到但未定义；D 表示在先前的输入文件中已经定义过的符号。初始状态时，E,U,D 三个集合都是空。

对于在命令行中输入的每一个文件 f：

  • 如果 f 是目标文件，添加 f 到集合 E 中，同时用 f 中的符号定义和引用更新 U 和 D 集合；然后处理下一个输入文件。
  • 如果 f 是库文件，链接器尝试用 f 中定义的符号去匹配 U 集合中的未解析符号。如果库文件中的模块 m 定义了符号，该符号解析了 U 中的符号引用，那么把 m 添加到 E 中，同时更新 U 和 D。对库文件中所有的目标模块，迭代这个过程，直到 U 和 D 集合不再发生变化。迭代完成后，如果库文件中的模块没有被包含在 E 集合中，直接丢弃。

处理完 f 后，处理下一个输入文件。如果所有的命令行输入文件都扫描完，U 集合非空，链接器打印错误并退出。否则链接器合并所有的 E 集合中的文件，生成可执行文件。

由于该算法是顺序扫描输入的文件，所以输入的顺序非常重要。如果定义在库文件中，对库文件中的符号引用在目标文件中，但库文件输入的顺序在目标文件前面，这时候就会出现引用链接失败，引用未解析。如执行”gcc -static ./libxxx.o main.c”。

这里写图片描述

一般的规则是把库文件放在命令行的最后。如果库文件之间相互独立，不存在彼此之间的引用关系，那么库文件之间的顺序无所谓。但如果库文件之间不相互独立，存在引用关系，必须要保证引用符号的库文件在前面（左边），定义符号的库文件在后面（右边）。

重定位

3.1 重定位

当源代码 “a.c” 在被编译成目标文件时，编译器并不知道 “shared” 和 “swap” 的地址，因为它们定义在其他目标文件中，所以编译器就暂时用假地址代替着，把真正的地址计算工作，留给了链接器。

链接器在完成地址和空间分配之后就已经确定所有符号的虚拟地址了，符号解析之后符号的引用和定义联系起来了，每个引用就能找到相应的地址，那么对这些符号的引用也必须被相应的调整。链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。

所以我们在看可执行文件的反汇编代码时，看到的都是真正的虚拟地址了。

3.2 重定位表

链接器是怎么知道哪些指令是要被调整的呢？ 这些指令的哪些部分要被调整（修正）？如何调整？ 所以有一个重定位表这个结构专门用来保存与重定位相关的信息，它在 ELF 文件中往往是一个或多个 section。

我们已经知道，每个要被重定位的 section 都有一个对应的重定位表，比如“.data”有要被重定位的地方，就会有一个相对应叫“.rel.data”的 section 保存了 “.data”的重定位表。可以用objdump -r 来查看目标文件的重定位表。

这里写图片描述

每一个要被重定位的地方叫一个重定位入口（Relocation Entry），重定位入口的偏移（Offset）表示该入口在要被重定位的 section 中的位置，“RELOCATION RECORDS FOR [.text]” 表示这个重定位表是 .text 的重定位表，所以偏移表示 .text 节中需要被调整的位置。

重定位表是一个 Elf32_Rel 结构的数组，每个数组元素对应一个重定位入口，结构定义如下：

这里写图片描述

这里写图片描述

根据类型的不同，有不同的指令修正方式。

这里写图片描述

3.3 指令修正方式

不同的处理器指令对于地址的格式和方式都不一样。，比如对于32 位Intel x86处理器来说，转移跳转指令（jmp 指令）、子程序调用指令（mov 指令）和数据传送指令（mov 指令）寻址方式千差万别。我们只关心其中两种最基本的重定位类型：32 位PC相对地址引用（R_386_PC32）和 32 位绝对地址引用（R_386_32）。

我们就以 a.o 为例来解释这两种修正方式，将 a.o 与 b.o 链接成最终的可执行文件 ab，看一下链接器将如何修改 a.o 里面的这两个重定位入口？

绝对寻址修正

先看 a.o 中 .text 节的第一个重定位入口，即偏移为 0x1c 的这条 push 指令，它的类型为 R_386_32，即绝对地址修正，它修正后的结果应该是 S+A，它对应的符号是 shared。

我们先来看下 可执行文件 ab 中 shared 的虚拟地址。

这里写图片描述

再来看下原来保存在被修正位置的值，偏移为 0x1c 的那个指令处原来的值。

这里写图片描述

  • S 是符号 shared 的实际地址，即 0x0804a004。
  • A 是被修正位置的值，即 0x00000000。

所以最后这个重定位入口修正后地址为：0x0804a004 + 0x00000000 = 0x0804a004。（小端模式）

这里写图片描述

相对寻址修正

再来看 a.o 中 .text 节的第二个重定位入口，即偏移为 0x25 的这条 call 指令，它的类型为 R_386_PC32，即相对地址修正，它修正后的结果应该是 S+A-P，它对应的符号是 swap。

我们先来看下 可执行文件 ab 中 swap 的虚拟地址。

这里写图片描述

再来看下原来需要被修正位置的值，偏移为 0x25 的那个指令处原来的值。或者看目标文件 a.o 中 swap 的值。

这里写图片描述

  • S 是符号 shared 的实际地址，即 0x080480cd。
  • A 是被修正位置的值，即 0xFFFFFFFC(-4)。
  • P 是被修正的位置，即 0x080480b9

所以最后这个重定位入口修正后地址为：0x080480cd + （-4）- 0x080480b9 = 0x00000010。

这里写图片描述

这条相对位移调用指令调用的地址是该指令下一条指令的起始地址加上偏移量，即 0x080480bd + 0x00000010 = 0x 080480cd，刚好是 swap 函数的地址。

COMMON 块

4.1 强符号与弱符号

我们在编程的时候还经常碰到一种情况叫符号重复定义。如下：

这里写图片描述

多个目标文件含有相同名字全局符号的定义，那么链接这些目标文件的时候会出现上面的错误。

对 C/C++ 语言来说，编译器默认函数和初始化的全局变量为强符号，未定义的全局变量为弱符号。强符号和弱符号都是针对定义来说的，不是针对符号的引用。那么当遇到多个符号的情况，是如何处理的？

针对强弱符号的概念，链接器会按下面的规则处理与选择被多次定义的全局符号：

  • 规则1：不允许强符号被多次定义。如果有多个强符号被定义，则链接器报符号重复定义错误。
  • 规则2：如果有一个强符号，多个弱符号，则选择强符号。
  • 规则3：如果出现多个相同类型弱符号，那么任意选一个。

我们看几个例子：

  • 两个强符号 main（规则一）
/* foo1.c */
int main()
{
            return 0;
}
/* bar1.c */
int main()
{
            return 0;
}

这里写图片描述

  • x 一强一弱（规则二）
/* foo2.c */
#include<stdio.h>

void f();

int x = 15213;

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

/* bar2.c */
#include<stdio.h>

int x;
void f()
{
    x = 15212;
}

这里写图片描述

  • x 有两个弱定义（规则三）
/* foo4.c */
#include<stdio.h>

void f();

int x;

int main()
{
    x = 15213;
    f();
    printf("x = %d\n", x);

    return 0;
}
/* bar4.c */
int x;

void f()
{
    x = 15212;
}

这里写图片描述

4.2 COMMON 块

正如上面提到的，由于弱符号机制允许同一个符号的定义存在于多个文件中，所以可能会出现一个问题：如果一个弱符号定义在多个目标文件中，而它们的类型又不相同，那怎么办？到底实际被用到的是哪个？

多个符号定义类型不一致的几种情况如下：

  • 两个或两个以上强符号类型不一致；
  • 有一个强符号，其他都是弱符号，出现类型不一致；
  • 两个或两个以上弱符号类型不一致。

现在的编译器和链接器都支持一种叫 COMMON 块的机制，这种机制最早来源于 Fortran，细节不多说了，自己去了解。主要想表达的是，当不同的目标文件需要的 COMMON 块空间大小不一致时，以最大的那块为准。

现代的链接器在处理弱符号的时候，采用的就是与 COMMON 块一样的机制。我们的样例 SimpleSection.c 中，符号 global_uninit_var 就是一个弱符号，我们看一下它的相关信息：

这里写图片描述

它的类型是 SHN_COMMON ，size 为 4。假设我们在另外一个文件中也定义了 global_uninit_var 变量。且未初始化，它的类型为 double，占 8 个字节，情况会怎样？ 事实上按照COMMON 类型的链接规则，最终链接后输出文件中， global_uninit_var 的大小以输入文件中最大的那个为准，即 global_uninit_var 所占的空间为 8 字节。我们可以验证一下，在另一个文件定义 double global_uninit_var;，然后编译和本来的样例进行链接：然后 readelf -s 查看一下输出文件的符号表，找到 global_uninit_var 的相关信息，如下：

这里写图片描述

我们可以再看一个例子：

/* foo5.c */
#include<stdio.h>

void f();

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;
}

这里写图片描述

bar5.c 中 赋值语句 x=-0.0 将用负零的双精度浮点表示覆盖存储器中 x 和 y 的位置。还可以注意到，如果链接过程中有弱符号大小大于强符号，那么 ld 链接器会报警告。

强弱符号的存在，可能会造成一些不易察觉的错误，尤其是涉及到大量模块的系统程序中，这种错误很难发现，尤其是对于不懂链接器是如何工作的程序员，所以编程的时候要小心，下面这篇文章还有一些例子，大家可以看下。C语言全局变量那些事儿

直接导致需要 COMMON 机制的原因是编译器和链接器允许不同类型的弱符号存在，但本质原因还是链接器不支持符号类型，它只知道一个符号的名字，没法判断各个符号的类型是否一致。

再来回顾一下，说 .bss 的时候提到，未初始化的全局变量，没有像未初始化的局部静态变量一样，直接放到 .bss 中，什么原因呢？

这里写图片描述

通过上面对链接器处理多个弱符号的过程，我们可以知道，编译成目标文件时，如果包含了弱符号，那么该弱符号最终所占的空间大小在此时是未知的，因为有可能其他编译单元中该符号所占的空间与本编译单元该符号占的空间大小不一致。在链接过程中就可以确定弱符号的大小了，它可以在最终输出文件的 BSS 段为其分配空间。所以，未初始化全局变量最终是被放在 BSS 段的。

参考资料：

  • 《程序员的自我修养》第四章静态链接
  • 《深入理解计算机系统》第一章链接
  • 编译和链接那点事
/* a.c */
extern int shared;
int global = 10;
int main()
{

    int a = 100;
    swap( &a, &shared );
}
/* b.c */
int shared = 1;
void swap( int* a, int* b )
{
    *a ^= *b ^= *a ^= *b;
}