链接器和加载器(Beta2 / 20061107)

链接器和加载器完成几个相关但概念上不同的动作。

• 程序加载:将程序从辅助存储设备(自1968年后这就意味着磁盘)拷贝到主内存中准备运行。在某些情况下，加载仅仅是将数据从磁盘拷入内存;在其他情况下，还包括分配存储空间，设置保护位或通过虚拟内存将虚拟地址映射到磁盘内存页上。
• 重定位:编译器和汇编器通常为每个文件创建程序地址从0开始的目标代码，但是几乎没有计算机会允许从地址 0 加载你的程序。如果一个程序是由多个子程序组成的，那么所有的子程序必须被加载到互不重叠的地址上。重定位就是为程序不同部 分分配加载地址，调整程序中的数据和代码以反映所分配地址的过程。在很多系统中，重定位不止进行一次。对于链接器的一种普遍情景是由多个子程序来构建一个程序，并生成一个链接好的起始地址为 0 的输出程序，各个子程序通过重定位在大程序中确定位置。当这个程序被加载时，系统会选择一个加载地址，而连接好的程 序会作为整体被重定位到加载地址。
• 符号解析:当通过多个子程序来构建一个程序时，子程序间的相互引用是通过符号进行的;主程序可能会调用一个名为 sqrt 的计算平方根例程，并且数学库中定义了 sqrt 例程。链接器通过标明分配给 sqrt 的地址在库中来解析这个符号，并通过修改目标代码使得 call 指令引用该地址。

尽管有相当一部分功能在链接器和加载器之间重叠，定义一个仅完成程序加载的程序为加载器，一个仅完成符号解析的程序为链接器是合理的。他们任何一个都可以进行重定位， 而且曾经也出现过集三种功能为一体的链接加载器。

重定位和符号解析的划分界线是模糊的。由于链接器已经可以解析符号的引用，一种处理代码重定位的方法就是为程序的每一部分分配一个指向基址的符号，然后将重定位地址认为是对该基址符号的引用。

链接器和加载器共有的一个重要特性就是他们都会修改目标代码，他们也许是唯一比调试程序在这方面应用更为广泛的程序。这是一个独特而强大的特性，而且细节非常依赖于机器的规格，如果做错的话就会引发令人困惑的 bug。

每种体系结构都有一些不同的指令格式。我们将只探讨与程序和数据寻址相关的格式细节，因为这些是影响链接器的主要细节。370 在数据引用和跳转中使用相同的指令格式， SPARC 使用不同的指令格式，而 Intel 的有些格式相同，有些格式不同。

每条指令都包含一个操作码，它决定了指令做什么，此外还有一个操作数。操作数可以被编码到指令本身(立即操作数)，或者放置在内存中。内存中每个操作数的地址总要经过一些计算。有时地址包含在指令中(直接寻址)。更经常的是地址存储在某一个寄存器中 (寄存器间接寻址)，或通过将指令中的一个常量加上寄存器中的内容计算得来。如果寄存 器中的值是一个存储区域的地址，而指令中的常量是存储区域中想要访问的数据的偏移量， 这种策略称为基址寻址。如果二者调换过来，并且寄存器中保存的是偏移量，那这种策略就 是索引寻址。基址寻址与索引寻址之间的区别不那么好定义，而且很多体系结构都将他们混 在一起了。例如，370 有一种寻址模式会将两个寄存器和指令中的常量加在一起，并强制的 将一个寄存器称作基址寄存器，另一个为索引寄存器，虽然他们都是相同对待的。

一些体系结构使用固定长度的指令，而另一些使用变长指令。所有的 SPARC 指令都是 4 字节长，并对齐到4字节边界。IBM 370的指令可以是2、4或6个字节长，指令的头一个字 节的头2位确定了指令的长度和格式。Intel x86的指令格式随时都可以是1到14个字节长。 这里的编码方式颇为复杂，部分是由于 x86 最初是为内存受限环境设计的紧凑指令编码，另外也是在 286、386 和后继芯片上的新加指令不得不被硬塞到已存在指令集未使用的位模式中。幸运的是，从链接器作者的角度来看，链接器需要调整的地址和偏移量都是以字节为边界的，所以通常不需要考虑指令编码问题。

在最早的计算机中，内存很小，指令中的地址域足够容纳计算机任何一个内存位置的地址，现在我们称这种策略为直接寻址。在上世纪 60 年代早期，可寻址内存已经变得相当大使得如果指令集中每个指令都包含整个地址将占用太多仍然宝贵的内存。为了解决这个问 题，计算机的架构师们在地址引用指令中部分或彻底的放弃了直接寻址，使用索引和基址寄存器来提供寻址所需的大部分或全部地址位。这可以让指令短一些，但与之而来的代价是编程更复杂了。

在稍老一些的地址空间很小、直接寻址的计算机系统上，由于只有一到两种链接器需 要处理的地址格式，因此代码修改的过程相当简单。对于现代计算机，包括所有的 RISC 架构，都需要进行复杂的多的代码修改。没有一条指令有足够的空间容纳一个直接地址，因此 编译器和链接器不得不才用复杂的寻址技巧来处理任意地址上的数据。某些情况下，使用两到三条指令来组成一个地址都是有可能的，每个指令包含地址的一部分，然后使用位操作将 它们组合为一个完整的地址。在这种情况下，链接器不得不对每个指令都进行恰当的修改， 将地址中的某些位插入到每一个指令中。其它情况下，一个例程或一组例程使用的所有地址 都被放置在一个作为“地址池”的数组中，初始化代码将某一个机器寄存器指向这个数组， 当需要时，代码会将该寄存器作为基址寄存器从地址池中加载所需指针。链接器需要由被程 序使用的所有地址来创建这个数组，并修改各指令使它们可以关联到正确的地址池入口处。 我们将在第 7 章讨论这个话题。

最简单的地址空间是由 PDP-11 版本的 UNIX 提供的。该地址空间为从 0 开始的 64K 字节。 程序的只读代码从位置 0 加载，可读写的数据跟在代码的后面。PDP-11 具有 8K 的页，所以 数据从代码后 8K 对齐的地方开始。栈向下生长，从 64K-1 的地方开始，随着栈和数据的增 长，对应的区域会变大:当它们相遇时程序就没有可用的地址空间了。接着 PDP-11 出现的 V AX 版本的 UNIX，使用了相似的策略。每一个 VAX 的 UNIX 程序的头两个字节都是 0(这是一 个表明不保存任何东西的寄存器保存掩码)。因此，一个全 0 的空指针总是有效的，并且如 果一个 C 程序将空值作为一个字串指针，那么位置 0 的零字节将会当作空字串对待。由于这 个原因，上世纪 80 年代的 UNIX 由于空指针的原因包含有很多难以发现的 bug，经过很多年 后，由于易于发现和修正所有的空指针 bug，移植到其它体系结构上的 UNIX 在位置 0 提供了 零字节。

每个链接器都有某种形式的命令语言来控制链接过程。最起码链接器需要记录所链接的目标代码和库的列表。通常都会有一大长串可能的选项:在哪里放置调试符号，在哪里使用共享或非共享库，使用哪些可能的输出格式等。多数链接器都允许某些方法来指定被链接 代码将要绑定的地址，这在链接一个系统内核或其它没有操作系统控制的程序时就会用到。 在支持多个代码和数据段的链接器中，链接器命令语言可以对链接各个段的顺序、需要特殊处理的段和某些应用程序相关的选项进行指定。

有四种常见技术向链接器传送指令:

• 命令行: 多数系统都会有命令行(或相似功能的其它程序)，通过它可以输入各种

文件名和开关选项。这对于 UNIX 和 Windows 链接器是很常用的方法。对于那些命令行长度有限制的系统，常用的办法是让链接器从文件中读取命令并在命令行上那 样对待他们。

• 与目标文件混在一起: 有些链接器，如IBM主机系统的链接器，从一个单个输入文件中接受替换的目标文件及链接器命令。这种方式来源于卡片输入的年代，那时程 序员需要把目标代码卡片摞起来和手工打制的命令卡片一起送到读卡器中。
• 嵌入在目标文件中: 有一些目标代码格式，特别是微软的，允许将链接器命令嵌入到目标文件中。这就允许编译器将链接一个目标文件时所需要的任何选项通过文件 自身来传递。例如 C 编译器将搜索标准 C 库的命令嵌入到文件中(来传递给链接过 程)。
• 单独的配置语言: 极少有链接器拥有完备的配置语言来控制链接过程。可以处理众 多目标文件类型、机器体系架构和地址空间规定的 GNU 链接器，拥有可以让程序员 指定段链接顺序、合并相近段规则、段地址和大量其它选项的一套复杂的控制语言。 其它链接器一般拥有诸如支持程序员可定义的重叠技术等特性的稍简单一些的配置语言。

由两种方案的优缺点引起的激烈讨论已经持续了很多年了。由于在两台字节序相同的 机器间移植程序要比不同字节序的机器要容易的多，所以实际中对字节序选择的主要考虑来 自于对旧系统的兼容。新近的很多芯片设计可以支持任何一种字节序，这可以在芯片布线时 进行选择，也可以在系统引导时通过编程选择，甚至某些情况下可以针对每个应用程序进行 不同选择。(在这些可切换的芯片上，被加载和存储指令处理的数据的字节序会发生变化， 但是被编码到指令中的常量的字节序是不变的，这是一些可以让链接器作者的工作变得很有 趣的细节)

多字节数据通常会被对齐到一些“天生”的边界上。就是说，4 字节的数据必须对齐到 4 字节的边界上，2 字节要对齐到 2 字节的边界上，并以此类推。另一种想法就是任何 N 字 节数据的地址至少要有log2(N)个低位为0。在某些系统上(Intel X86，DEC VAX，IBM 370/ 390)，引用未对齐数据会付出性能降低的代价，在另外一些系统上(多数 RISC 芯片)，这 会导致程序故障。即使在那些引用未对齐数据不会导致故障的系统上，性能的损失也是非常 大的，以至于值得我们花费精力来尽可能保持地址的对齐。

很多处理器同样要求程序指令的对齐。多数 RISC 芯片要求指令必须对齐在 4 字节的边 界上。

库符号解析是一个迭代的过程，在链接器对目录中的符号完成一遍扫描后，如果在这 边扫描中它又从该库中包括进来了任何文件，那么就还需要在进行一次扫描来解析新包括进 来的文件所需的符号，直到对整个目录彻底扫描后不再需要括入新的文件为止。并不是所有 的链接器都这么做的，很多链接器只是对目录进行一次连续的扫描，并忽略在库中一个文件 对另一个更早扫描的文件的向后依赖。像诸如 tsort 和 lorder 这样的程序可以尽量减少由 于一遍扫描给链接器带来的困难，不过并不推荐程序员通过显式的将相同名称的库在链接器 命令行中列出多次来强制进行多次扫描并解析所有符号。

UNIX 链接器和很多 Windows 链接器在命令行或者控制文件中会使用一种目标文件和库 混合在一起的列表，然后依次处理，这样程序员就可以控制加载目标代码和搜索库的顺序了。 虽然原则上这可以提供相当大的弹性并可以通过将同名私有例程列在库例程之前而在库例程 中插入自己的似有同名例程，在实际中这种排序的搜索还可以提供一些额外的用处。程序员 总是可以先列出所有他们自己的目标文件，然后是任何应用程序特定的库，然后是和数学、 网络等相关的系统库，最后是标准系统库。

当程序员们使用多个库的时候，如果库之间存在循环依赖的时候经常需要将库列出多 次。就是说，如果一个库 A 中的例程依赖一个库 B 中的例程，但是另一个库 B 中的例程又依 赖了库 A 中的另一个例程，那么从 A 扫描到 B 或从 B 扫描到 A 都无法找到所有需要的例程。 当这种循环依赖发生在三个或更多的库之间时情况会更加糟糕。告诉链接器去搜索A B A或 者B A B，甚至有时为A B C D A B C D，这种方法看上去很丑陋，但是确实可以解决这个 问题。由于在库之间几乎不会有重复的符号，如果链接器可以像 IBM 的大型主机系统链接器 或者 AIX 链接器那样，简单的将它们作为一个组一起搜索，那程序员就很舒服了。

该规则的一个主要例外是应用程序有时候会对少许例程定义自己的私有版本，尤其是 对 malloc 和 free，为了进行堆存储管理往往想采用自己的私有版本而不是标准的系统库版 本。在这种情况下，比使用一个链接器标志会注明“不要在库中搜寻这些符号”(效果相同 但)更好的方法是在搜索顺序中将私有的 malloc 放在公共版本之前。

由于几乎所有的现代计算机都具有硬件重定位，可能会有人疑问为什么链接器或加载 器还需要进行软件重定位(当我于 60 年代后期在 PDP-6 上编程时，这个问题就困惑着我， 而从那以后情况就变得更复杂了)。答案部分在于性能的考虑，部分在于绑定时间。

硬件重定位允许操作系统为每个进程从一个固定共知的位置开始分配独立的地址空间， 这就是程序容易加载，并且可以避免在一个地址空间中的程序错误破坏其它地址空间中的程 序。软件链接器或加载器重定位将输入文件合并为一个大文件以加载到硬件重定位提供的地 址空间中，然后就根本不需要任何加载时的地址修改了。

在诸如 286 或 386 那样有几千个段的机器上，实际上有可能做到为每一个例程或全局数 据分配一个段，独立的进行软件重定位。每一个例程或数据可以从各自段的 0 位置开始，所 有的全局引用通过查找系统段表中的段间引用来处理并在程序运行时绑定。不幸的是，x86 段查找非常的慢，而且如果程序对每一个段间模块调用或全局数据引用都要都要进行段查找 的话那速度要比传统程序慢的多。同样重要的时，虽然运行时绑定会对此有一些帮助(这是 我们将在第 10 章涉及的话题)，但大多数程序都没有采用(鉴于当前的硬件性能和容量对 于程序运行都颇为富余)。由于可信的理由，程序文件最好绑定在一起并且在链接时确定地 址，这样它们在调试时静止不变而出货后仍能保持一致性。当一个程序运行的库超出了作者 预期的版本时，库二进制兼容是程序错误的一个长期并且难以发现的来源。(MS Windows应 用程序由于使用了大量的共享库，就倾向于存在这种问题。由于某些库的不同版本会因安装 各种应用程序被加载到同一个计算机上)。即使不考虑 286 风格段的限制，动态连接比起静 态连接而言也要慢的多，而且没有理由为不需要的东西付钱。

仅有一小部分系统还仍然为执行程序在加载时进行重定位，大多数都是为共享库在加 载时进行重定位。诸如 MS-DOS 的系统，很少使用硬件的重定位;另外一些如 MVS 的系统， 具有硬件重定位(却是从一个没有硬件重定位的系统继承来的);还有一些系统，具有硬件 重定位，但是却可以将多个可执行程序和共享库加载到相同的地址空间。所以链接器不能指 望某些特定地址是有效的。

如第七章讨论的，加载时重定位要比链接时重定位简单的多，因为整个程序作为一个 单元进行重定位。例如，如果一个程序被链接为从位置 0 开始，但是实际上被加载到位置 15 000，那么需要所有程序中的空间都要被修正为“加上 15000”。在将程序读入主存后，加载 器根据目标文件中的重定位项，并将重定位项指向的内存位置进行修改。

对于将相同程序加载到普通地址的问题的一个常用的解决方案就是位置无关代码 (position independent code， PIC)。他的思想很简单，就是将数据和普通代码中那些不 会因为被加载的地址改变而变化的代码分离出来。这种方法中代码可以在所有进程间共享， 只有数据页为各进程自己私有。

这是一个令人吃惊的老想法。TSS/360 在 1966 年就使用它了，并且我相信它也不是最 早采用该方法的(TSS 有很多臭名昭著的 bug，但是从我个人经验而言，他的 PIC 特性的确 可以工作)。

在现代体系结构中，生成 PIC 可执行代码并不困难。跳转和分支代码通常是位置相关的， 或者与某一个运行时设置的基址寄存器相关，所以需要对他们进行非运行时的重定位。问题 在于数据的寻址，代码无法获取任何的直接数据地址。由于代码是可重定位的，而数据不是 位置无关的。普通的解决方案是在数据页中建立一个数据地址的表格，并在一个寄存器中保 存这个表的地址，这样代码可以使用相对于寄存器中地址的被索引地址来获取数据。这种方 式的成本在于对每一个数据引用需要进行一次额外的重定位，但是还存在一个问题就是如何 获取保存到寄存器中去的初始地址。

不考虑 x86 指令的复杂编码方式，从链接器的角度看这种体系结构是易于处理的，因为 它只需要处理两种地址，直接地址和与程序计数器相对的地址(我们在这里像大多数 32 位 链接器那样忽略段)。引用数据的指令可以带有 32 位目标地址，链接器可以像其它 32 位地 址那样对其进行重定位，加上目标所在段的段基址。

call 和 jump 指令使用相对寻址，因此指令中的地址是指令当前地址和目标地址的差值。 对于相同段内的 call 和 jmp 指令，由于一个段内的相对地址是永不会改变的因此不需要进 行重定位。对于段间 jump 链接器加上目标段重定位地址并减去指令段的地址。

IBM AIX使用了这种方案的改良版本。AIX程序将多个例程组成模块，模块就是使用单 独的或一组相关的 C/C++源代码文件生成的目标代码。每个模块的数据段保存着一个目录表 (Table Of Content， TOC)，该表是由模块中所有例程和这些例程的小的静态数据的指针组 成的。寄存器 2 通常用来保存当前模块的 TOC 地址，在 TOC 中允许直接访问静态数据，并可 通过 TOC 中保存的指针间接访问代码和数据。由于调用者和被调用者共享相同的 TOC，因此在一个模块内的调用就是一个简单的 call 指令。模块之间的调用必须在调用之前切换 TOC， 调用后再切换回去。

编译器将所有的调用都生成为 call 指令，其后还紧跟一个占位控操作指令 no-op，对 于模块内调用这是正确的。当链接器遇到一个模块间调用时，他会在模块文本段的末尾生成 一个称为global linkage或glink的例程。Glink将调用者的TOC保存在栈中，然后从调用 者的 TOC 中指针中加载被调用者的 TOC 和各种地址，然后跳转到要调用的例程。链接器将每 一个模块间调用都重定向为针对被调用历程的 glink，并将其后的空操作指令修改为从栈中 恢复TOC的加载指令。过程的指针都变为TOC/代码配对(TOC/code pair)的指针，所有通过 指针的 call 都会借助一个使用了该指针指向的 TOC 和代码地址的普通 glink 例程。

这种方案使得模块内调用尽可能的快。模块间调用由于借助了 glink 所以会稍微慢一些， 但是比起我们接下来要看到的其它替代方案来，这种速度的降低是很小的。

链接器将可执行文件中寻址的所有全局变量的指针保存在它创建的全局偏移量表(Glob al Offset Table， GOT)中(每一个共享库拥有自己的GOT，如果主程序和PIC代码一起编 译，它也会有一个 GOT，虽然通常不这么做)。鉴于链接器创建了 GOT，所以对于每个 ELF 可执行程序的数据只有一个地址，而不论在该可执行程序中有多少个例程引用了它。

GOT 寄存器被加载之后，程序数据段中的静态数据与 GOT 直接的距离在链接时被固定了， 所以代码就可以将 GOT 寄存器作为一个基址寄存器来引用局部静态数据。全局数据的地址只 有在程序被加载后才被确定(参看第 10 章)，所以为了引用全局数据，代码必须从 GOT 中加 载数据的指针，然后引用这个指针。这个多余的内存引用使得程序稍微慢了一些，尽管大多 数程序员为了方面的使用动态链接库愿意付出这个代价。对速度要求较高的代码可以使用静 态共享库(参看第 9 章)或者根本不使用共享库。

在 ELF 文件中函数的开始和结束是相当慢的。他们必须保存和恢复 GOT 寄存器，在 x86 中就是 ebx，并且通过 call 和 pop 将程序计数器保存到一个寄存器中也是很慢的。从性能的 观点来看，AIX 使用的 TOC 方法更好，因为每一个过程可以假定它的 TOC 寄存器已经在过程 项中设置了。

最后，PIC 代码要比非 PIC 代码更大、更慢。到底会有多慢很大程度上依赖于体系结构。对于拥有大量寄存器且无法直接寻址的 RISC 系统来说，少一个用作 TOC 或 GOT 指针的寄存器 影响并不明显，并且缺少直接寻址而需要的一些排序时间是不变的。最坏的情况是在 x86 下。 它只有 6 个寄存器，所以用一个寄存器当作 GOT 指针对代码的影响非常大。由于 x86 可以直 接寻址，一个对外部数据的引用在非 PIC 代码下可以是一个简单的 MOV 或 ADD，但在 PIC 代 码下就要变成加载紧跟在 MOV 或 ADD 后面的地址，这既增加了额外的内存引用又占用了宝贵 的寄存器作为临时指针。

特别在 x86 系统上，对于速度要求严格的任务，PIC 代码的性能降低是明显的，以至于 某些系统对于共享库退而采用一种类似 PIC 的方法。

在操作系统运行程序时，它会像通常那样将文件的页映射进来，但注意在可执行程序 中存在一个 INTERPRETER 区段。这里特定的解释器是动态链接器，即 ld.so，它自己也是 ELF 共享库的格式。操作系统并非直接启动程序，而是将动态链接器映射到地址空间的一个合适 的位置，然后从ld.so处开始，并在栈中放入链接器所需要的辅助向量(auxiliary vector) 信息。向量包括:

• AT_PHDR，AT_PHENT，和 AT_PHNUM:程序头部在程序文件中的地址，头部中每个表项的 大小，和表项的个数。头部结构描述了被加载文件中的各个段。如果系统没有将程序映射到 内存中，就会有一个 AT_EXECFD 项作为替换，它包含被打开程序文件的文件描述符。
• AT_ENTRY:程序的起始地址，当动态链接器完成了初始化工作之后，就会跳转到这个 地址去。
• AT_BASE:动态链接器被加载到的地址。

此时，位于 ld.so 起始处的自举代码找到它自己的 GOT，其中的第一项指向了 ld.so 文 件中的 DYNAMIC 段。通过 dynamic 段，链接器在它自己的数据段中找到自己的重定位项表和 重定位指针，然后解析例程需要加载的其它东西的代码引用(Linux ld.so将所有的基础例 程都命名为由字串_dt_起头，并使用专门代码在符号表中搜索以此字串开头的符号并解析它 们)。

链接器然后通过指向程序符号表和链接器自己的符号表的若干指针来初始化一个符号 表链。从概念上讲，程序文件和所有加载到进程中的库会共享一个符号表。但实际中链接器 并不是在运行时创建一个合并后的符号表，而是将个个文件中的符号表组成一个符号表链。 每个文件中都有一个散列表(一系列的散列头部，每个头部引领一个散列队列)以加速符号 查找的速度。链接器可以通过计算符号的散列值，然后访问相应的散列队列进行查找以加速 符号搜索的速度。

链接器在以下位置搜索库:

• 是否 dynamic 段有一个称为 DT_RPATH 的表项，它是由分号分隔开的可以搜索库的目录列表。

它可以通过一个命令行参数或者在程序链接时常规(非动态)链接器的环境变量来添加。它经 常会被诸如数据库类这样需要加载一系列程序并可将库放在单一目录的子系统使用，

• 是否有一个环境符号 LD_LIBRARY_PATH，它可以是由分号分隔开的可供链接器搜索库的目录

列表。这就可以让开发者创建一个新版本的库并将它放置在 LD_LIBRARY_PATH 的路径中，这 样既可以通过已存在的程序来测试新的库，或用来监测程序的行为。(因为安全原因，如果程序设置了 set-uid，那么这一步会被跳过)

• 链接器查看库缓冲文件/etc/ld.so.conf，其中包含了库文件名和路径的列表。如果要查找的 库名称存在于其中，则采用文件中相应的路径。大多数库都通过这种方法被找到(路径末尾的 文件名称并不需要和所搜索的库名称精确匹配，详细请参看下面的库版本章节)。
• 如果所有的都失败了，就查找缺省目录/usr/lib，如果在这个目录中仍没有找到，就打印错 误信息，并退出执行。

一旦找到包含该库的文件，动态链接器会打开该文件，读取 ELF 头部寻找程序头部，它 指向包括 dynamic 段在内的众多段。链接器为库的文本和数据段分配空间，并将它们映射进 来，对于 BSS 分配初始化为 0 的页。从库的 dynamic 段中，它将库的符号表加入到符号表链 中，如果该库还进一步需要其它尚未加载的库，则将那些新库置入将要加载的库链表中。

在该过程结束时，所有的库都被映射进来了，加载器拥有了一个由程序和所有映射进 来的库的符号表联合而成的逻辑上的全局符号表。

由于 GOT 位于代码所引用的可加载 ELF 文件中，因此无论被加载到何处，位于文件中的 相对地址都不会发生变化。代码可以通过相对地址来定位 GOT，将 GOT 的地址加载到一个寄 存器中，然后在需要寻址静态数据的时候从 GOT 中加载相应的指针。如果一个库没有引用任 何的静态数据那么它可以不需 GOT，但实际中所有的库都有 GOT。

为了支持动态链接，每个 ELF 共享库和每个使用了共享库的可执行程序都有一个过程链 接表(Procedure Linkage Table, PLT)。PLT就像GOT对数据引用那样，对函数调用增添 了一层间接途径。PLT 还允许进行“懒惰计算法”，即只有在第一次被调用时，才解析过程 的地址。由于 PLT 表项要比 GOT 多很多(在上面提到的 C 库中会有超过 600 项)，并且大多 数例程在任何给定的程序中都不会被调用，因此“懒惰计算法”既可以提高程序启动的速度， 也可以整体上节省相当可观的时间。

在运行时，几乎所有的 Windows 动态链接器都在操作系统内核中，而 ELF 的动态链接器 则完全作为应用程序的一部分运行，而内核只是将初始文件映射进来。Windows 的策略更快 一些(也有待商榷)，因为它在开始链接前不需要将动态链接器映射进来并重定位。ELF 的 策略则肯定是灵活的多。因为每一个可执行程序都命名了要使用的“解释器”(现在总是名 为 ld.so 的动态链接器)程序，不同的可执行程序可以使用不同的解释器而无须要求操作系 统进行任何变更。在实际中，这就更容易让可执行程序支持多种版本的 UNIX，尤其在 Linux 和 BSD 上，可以通过一个链接到兼容库上的动态链接器来支持非本地的可执行程序。

第三，也是目前最复杂的问题即模板和“extern inline”过程。一个C++模板定义了 一个无穷的过程的家族，每一个家族成员都是由某个类型特定的模板。例如，一个模板可能 定义了一个通用的 hash 表，则就有整数类型的 hash 表家族成员，浮点数类型的 hash 表家族 成员，字符串类型的，或指向各种数据结构的指针的类型的。由于计算机的存储器容量是无 穷的，被编译好的程序需要包含程序中用到的这个家族中实际用到的所有成员，并且不能包 含其它的。如果 C++编译器采用传统方法单独处理每一个源代码文件，他不能确定是否所编 译的源代码文件中用到的模板是否在其它源代码文件中还存在被使用的其它家族成员。如果 编译器采用保守的方法为每一个文件中使用到的每一个家族成员都产生相应的代码，那么最 后将可能对某些家族成员产生了多分代码，这就浪费了空间。如果它不产生那些代码，它就 有漏掉某一个需要的家族成员的可能性存在。

输入文件传递给链接器以产生试验输出和错误信息，然后将输入文件和错误信息，可 能还有更多产生的目标文件一起再传递给链接器以产生最终的目标文件。在 UNIX 系统上，如果 linker 在一次链接任务中不能够解析所有的未定义符号引用，他 可以选择仍然输出一个作为后续链接任务的输入文件的输出文件。在连接过程中链接器使用 普通的库查找规则，使得输出文件包含所需的库，这也是再次作为输入文件所包含的信息。 试验链接解决了上面所有的 C++问题，虽然很慢，但却是有效的方法。

在大多数系统上，链接器是在软件建立过程中唯一会同时检查程序所有部分的程序。 这就意味着他可以做一些别的部件无法进行的全局优化，特别是当程序由多个使用不同语言 和编译器编写的多个模块组成的时候。例如，在一个带有类继承的语言中，一个类的方法可 能会在子类中被覆盖，因此对它的调用通常都是间接的。但是如果没有任何的子类，或者存 在子类但是没有一个覆盖了这个方法，那就可以直接调用这个方法。链接器可以对这种情况 进行特殊优化以避免面向对象语言在继承时的低效率。Princeton 的 Fernandez 曾经写过一 个针对 Modula-3 的优化链接器，可以将 79%的间接方法调用转换为直接调用，同时减少了 10%的执行指令。

一种更激进的方法是对整个程序在链接时进行标准的全局优化。Srivastava 和 Wall 编 写过一个优化链接器，可以将 RISC 体系结构的目标代码反编译为一种中间格式的数据，并 对之实施诸如 inline 这样的高层次优化或诸如将一个更快但限制更多的指令替换为一个稍慢但常用的指令的低层次优化，然后再重新生成目标代码。特别是在 64 位体系结构的 Alpha 体系结构中，对静态或者全局数据，以及任意例程的寻址方法，是将指向地址池中某一项的 地址指针从内存中加载到寄存器里，然后把这个寄存器作为基址寄存器使用(地址持通过一 个全局的指针寄存器来寻址)。他们的 OM 优化链接器会寻找多个连续指令引用一系列地址 足够紧接的全局变量或静态变量的情况(这些全局变量和静态变量的彼此位置接近到足够可 以通过同一个指针即可对他们寻址)，然后重写目标代码以去除多余的从全局地址池中加载 地址的指针。它也寻找那些通过分支跳转指令在 32 位地址范围内的过程调用，并将他们替 换为需加载一个地址的间接调用。它也可以重新排列普通块的位置，使得较小的块排列在一 起，这样以增加同一个指针被引用的次数。通过这些及其它的标准优化技术，OM 在可执行 程序上实现了显著的提高，在一些 SPEC 寄存测试中总指令数减少了 11%。

很多链接器会生成少量的输出目标代码，例如UNIX ELF文件的PLT(译者注: procedure linkage table)中的跳转项。但是一些实验链接器会产生比那更多的代码。

Srivastava 和 Wall 的优化链接器首先将目标文件反编译为一种中间格式的代码。多数 情况下，如果链接器想要中间格式代码的话，他可以很容易的告诉编译器跳过代码生成，而 创建中间格式的目标文件，让链接器去完成代码生成工作。上面这些确实是 Fernandez 优化 器所描述的。链接器可以使用所有的中间格式代码，对其进行大量的优化工作，然后再为输 出文件产生目标代码。

对于商业链接器有很多理由说明为什么它们根据中间格式代码进行代码生成。理由之 一是中间格式代码的语言趋向于和编译器的目标语言相关。设计一种中间格式代码的语言以 处理包括 C 和 C++在内的类 Fortran 语言并不是很难的事情，但是要设计既能处理那些语言 又能处理诸如 Cobol 和 Lisp 这样鲜有共性的语言，那是一件相当难的事情。链接器通常都 是链接从任何编译器和汇编器生成的目标代码，因此使其和特定语言关联起来是会有问题的。

下一步就是确认，进行一系列的静态正确性检查，例如确保每一个虚拟指令都有一个 正确的操作码，每一个分支的目标都是有效的指令，每一个指令都能正确处理所引用数值的 类型。这些检查在程序运行后可以不必再进行因此可以提高程序执行的速度。如果确认时发 现了错误，它会产生一个例外消息。然后准备阶段会为类中所有的静态成员分配存储空间， 然后将它们初始化为标准的缺省值，一般都是 0。大多数 Java 实现会在这时创建一个方法表， 它包含着指向该类及其从父类继承来的所有方法的指针。

Java 链接的最后一步就是解析，相当于其它语言的动态链接过程。每一个类包含一个常量池(constant pool)，其中既有诸如数字和字符串这样的常规常量，也有对其它的类 的引用。所有在编译好的类中的引用，甚至是针对其父类的，都是符号连接，并在这个类被 加载后进行解析(它的父类可能会在它被加载后被修改并重新编译，只要它可通过某种方法保持引用的域和方法仍有定义，那他们就仍是有效的)。Java 规范允许具体实现从确认后 到指令实际使用某个引用前的任何时候对引用进行解析，如调用父类或其它类中定义的函数。 如果不考虑实际解析引用的时间的话，那么一个失败的引用只有在它被使用时才会导致例外 发生，因此程序的行为就好像 Java 使用了 Just-In-Time 的“懒惰”解析策略。这种在解析 时的灵活性允许多种可能的实现方案。这样在将类翻译为本地机器码时就可以立即解析所有 的引用了，包括当一个引用不能解析时所要跳转到的例外处理历程。一个纯解释器会像解释 代码时那样解析这个引用而不是束手无策。

加载和链接的设计所带来的影响是类可以按需加载和解析。Java 的垃圾收集策略像对 其他数据那样应用于类，只要一个类的所有引用都被删除了那么这个类就会被卸载。

Java 的加载和链接模式是我们在这本书里见到的最复杂的。但 Java 尝试去满足一些对 立的目标，可移植的类型安全的代码和合理快速的可执行程序。这里的加载和链接模式支持 增量加载，支持多数类型安全标准的静态确认，允许那些想让程序运行的更快的系统将类翻 译为机器码。