目录

Linkers

本文为摘录(或转载),侵删,原文为: https://www.airs.com/blog/archives/38

1 Linkers part 1

1.1 链接器做什么?

很简单:链接器将目标文件转换为可执行文件和共享库。让我们看看这意味着什么。使用链接器的情况是,软件开发过程包括用某种语言编写程序代码:例如,C或 C++或 Fortran(但通常不包括 Java,因为 Java 通常以不同的方式工作,使用加载器而不是链接器)。编译器将这种人类可读的程序代码转换为另一种人类可读的文本形式,称为汇编代码。汇编代码是机器语言的可读形式,计算机可以直接执行。汇编器用于将此汇编代码转换为目标文件。为了完整起见,我要提到某些编译器在内部包括一个汇编器,并直接生成目标文件。无论哪种方式,这就是事情变得有趣的地方。

在古老的日子里,当恐龙漫游数据中心时,许多程序是自给自足的。在那些日子里,通常没有编译器——人们直接用汇编代码编写——而汇编器实际上生成了可执行文件,机器可以直接执行。随着 Fortran 和 Cobol 等语言的出现,人们开始以子例程库的方式思考,这意味着必须有某种方法在两个不同的时间运行汇编器,并将输出组合成一个可执行文件。这要求汇编器生成不同类型的输出,这种输出被称为目标文件(我不知道这个名字来自哪里)。同时需要一个新程序将不同的目标文件组合成一个单一的可执行文件。这个新程序被称为链接器(这个名字的来源应该很明显)。

链接器今天仍然执行相同的任务。在接下来的几十年里,添加了一个新特性:共享库。

2 Linkers part 2

2.1 Basic Linker Data Types

链接器操作于少量基本数据类型:符号 (symbols)、重定位 (relocations)和内容 (contents)。这些在输入的目标文件中定义。以下是这些的概述。

2.1.1 符号 symbol

一个符号基本上是一个名称和一个值。许多符号代表源代码中的静态对象——即在程序运行期间存在于单一位置的对象。例如,在从 C 代码生成的目标文件中,将为每个函数以及每个全局和静态变量生成一个符号。此类符号的值仅仅是对其内容的偏移量。这种类型的符号称为定义符号。重要的是不要将表示变量 my_global_var 的符号的值与 my_global_var 本身的值混淆。符号的值大致是该变量的地址:在 C 中从表达式 &my_global_var 获得的值。

符号还用于表示对在不同目标文件中定义的名称的引用。这样的引用被称为未定义符号。还有其他一些使用较少的符号类型,我将在后面描述。

在链接过程中,链接器将为每个定义符号分配一个地址,并通过查找具有相同名称的定义符号来解析每个未定义符号。

2.1.2 重定位

重定位是对内容执行的计算。大多数重定位引用一个符号和内容内的一个偏移量。许多重定位还会提供一个额外的操作数,称为附加数。一个简单且常用的重定位是“将内容中的此位置设置为此符号的值加上此附加数。”重定位所做的计算类型本质上依赖于链接器所生成代码的处理器架构。例如,RISC 处理器需要两个或更多指令来形成内存地址,因此每个指令将有单独的重定位;例如,“将内容中的此位置设置为此符号值的低 16 位。”

在链接过程中,链接器将按照指示执行所有重定位计算。目标文件中的重定位可能引用未定义符号。如果链接器无法解析该符号,它通常会发出错误(但并不总是:对于某些符号类型或某些重定位类型,错误可能不合适)。

2.1.3 内容

内容是程序执行期间内存应如何显示的内容。内容具有大小、一个字节数组和类型。它们包含由编译器和汇编器生成的机器代码(称为文本)。它们包含已初始化变量的值(数据)。它们包含如字符串常量和开关表等静态无名数据(只读数据或 rdata)。它们包含未初始化的变量,这种情况下字节数组通常会被省略,并假设仅包含零(bss)。编译器和汇编器努力生成完全正确的内容,但链接器实际上对此并不关心,只将其视为原始数据。链接器从每个文件中读取内容,将其按照类型连接在一起,应用重定位,并将结果写入可执行文件。

2.2 基本链接器操作

此时,我们已经足够了解每个链接器使用的基本步骤。

– 读取输入目标文件。确定内容的长度和类型。读取符号。– 构建一个包含所有符号的符号表,将未定义符号链接到它们的定义。– 决定所有内容在输出可执行文件中的位置,这意味着决定它们在程序运行时应该放在哪里。– 读取内容数据和重定位。将重定位应用于内容。将结果写入输出文件。– 可选地写出完整的符号表及符号的最终值。

3 part 3

3.1 地址空间

地址空间简单来说就是内存的一个视图,在这个视图中,每个字节都有一个地址。链接器处理三种不同类型的地址空间。

  1. 每个输入对象文件是一个小的地址空间:其内容都有地址,符号和重定位通过地址引用这些内容。

  2. 输出程序在运行时将被放置在内存的某个位置。这就是输出地址空间,我通常称之为使用虚拟内存地址。

  3. 输出程序将在内存的某个位置被加载。这就是加载内存地址。
    在典型的 Unix 系统中,虚拟内存地址和加载内存地址是相同的。在嵌入式系统中,它们通常不同;例如,初始化的数据(全局或静态变量的初始内容)可能会被加载到 ROM 中的加载内存地址,然后复制到虚拟内存地址的 RAM 中。

共享库通常可以在不同进程中以不同的虚拟内存地址运行。共享库在创建时有一个基地址;这通常仅仅是零。当动态链接器将共享库复制到进程的虚拟内存空间时,必须应用重定位以调整共享库使其在虚拟内存地址上运行。共享库系统最小化必须应用的重定位数量,因为它们在启动程序时需要时间。

3.2 对象文件格式

正如我上面所说,汇编器将人类可读的汇编语言转换为对象文件。对象文件是以一种为链接器设计的格式编写的二进制数据文件。链接器生成一个可执行文件。这个可执行文件是以一种为操作系统或加载程序设计的格式编写的二进制数据文件(即使在动态链接时也是如此,通常操作系统在调用动态链接器以开始运行程序之前会加载可执行文件)。对象文件格式并没有逻辑要求与可执行文件格式相似。然而,在实践中,它们通常非常相似。

大多数对象文件格式定义了段。段通常保存内存内容,或者可以用于保存其他类型的数据。段通常有一个名称、一个类型、一个大小、一个地址和一个关联的数据数组。

对象文件格式可以分为两种一般类型:记录导向和段导向。

  1. 记录导向的对象
    记录导向的对象文件格式定义了一系列大小各异的记录。每个记录以某种特殊代码开始,后面可能跟着数据。读取对象文件需要从头开始读取并处理每个记录。记录用于描述符号和段。重定位可能与段相关联,或者可能由其他记录指定。IEEE-695 和 Mach-O 是当前使用的记录导向对象文件格式。
  1. 段导向的对象文件
    在段导向的对象文件格式中,文件头描述了具有指定数量段的段表。符号可以出现在由文件头描述的对象文件的单独部分,或者可以出现在特殊段中。重定位可以附加到段上,或者可以出现在单独的段中。对象文件可以通过读取段表,然后直接读取特定段来进行读取。ELF、COFF、PE 和 a.out 是段导向对象文件格式。

每种对象文件格式都需要能够表示调试信息。调试信息由编译器生成,并由调试器读取。通常,链接器可以将其视为任何其他类型的数据。然而,在实践中,程序的调试信息可能比实际程序本身要大。链接器可以使用各种技术来减少调试信息的量,从而减少可执行文件的大小。这可以加快链接速度,但需要链接器理解调试信息。

a.out 对象文件格式使用符号表中的特殊字符串存储调试信息,这些字符串被称为 stabs。这些特殊字符串就是特殊类型的符号名称。这种技术也被某些 ECOFF 变体和旧版本的 Mach-O 使用。

COFF 对象文件格式使用符号表中的特殊字段存储调试信息。这种类型信息是有限的,对于 C++来说完全不够用。解决这些限制的常见技术是在 COFF 段中嵌入 stabs 字符串。

ELF 对象文件格式在具有特殊名称的段中存储调试信息。调试信息可以是 stabs 字符串或 DWARF 调试格式。

4 Shared Libraries

我们已经讨论了一些目标文件和可执行文件,那么共享库是什么样的呢?我将重点讲述 SVR4(以及 GNU/Linux 等)中使用的 ELF 共享库,因为它们是最灵活的共享库实现,也是我最熟悉的。

Windows 共享库,称为 DLL,在灵活性方面较低,因为您必须根据代码是否将进入共享库以不同的方式进行编译。您还必须在源代码中表达符号可见性。这并不是本质上的坏事,实际上 ELF 随着时间的推移吸收了一些这些思路,但 ELF 格式在链接时做出更多的决策,因此更强大。

当程序链接器创建共享库时,它尚不知道该共享库将在哪个虚拟地址上运行。实际上,在不同的进程中,同一个共享库将在不同的地址上运行,这取决于动态链接器所做的决策。这意味着共享库代码必须是位置无关的(positionindependent)。更准确地说,在动态链接器加载完成后,它必须是位置无关的。只要有足够的重定位信息,动态链接器总是能够将任何代码片段转换为在任何虚拟地址上运行。然而,进行重定位计算必须在每次程序启动时进行,这意味着程序的启动速度会变慢。因此,任何共享库系统都寻求生成位置独立的代码,这要求在运行时应用的重定位数量尽可能最小,同时仍能接近位置相关代码的运行效率。

一个额外的复杂性是,ELF 共享库的设计大致相当于普通的档案。这意味着默认情况下,主可执行文件可能会覆盖共享库中的符号,导致共享库中的引用会调用可执行文件中的定义,即使共享库也定义了相同的符号。例如,一个可执行文件可能定义了自己版本的 malloc。C 库也定义了 malloc,并且 C 库中包含调用 malloc 的代码。如果可执行文件自己定义了 malloc,它将覆盖 C 库中的函数。当 C 库中的某个其他函数调用 malloc 时,它将调用可执行文件中的定义,而不是 C 库中的定义。

因此,对于任何特定的 ELF 实现,存在不同的要求在不同的方向上拉扯。正确的实现选择将取决于处理器的特性。尽管如此,大多数,但不是全部,处理器做出的决策相当相似。这里我将描述常见的情况。使用常见情况的处理器实例是 i386;做出一些不同决策的处理器实例是 PowerPC。

在一般情况下,代码可能会以两种不同的模式编译。

  • 默认情况下,代码是位置依赖的。
    将位置依赖的代码放入共享库会导致程序链接器生成大量的重定位信息,并使动态链接器在运行时进行大量处理。

  • 代码也可以以位置无关模式编译,通常使用 -fpic 选项。
    位置无关代码在调用非静态函数或引用全局或静态变量时稍微慢一些。然而,它需要的重定位信息要少得多,因此动态链接器将更快地启动程序。

位置无关代码将通过过程链接表(PLT)调用非静态函数。这个 PLT 在.o 文件中并不存在。在.o 文件中,使用 PLT 由一种特殊的重定位来指示。当程序链接器处理这样的重定位时,它会在 PLT 中创建一个条目。它将调整指令,使其成为对 PLT 条目的 PC 相对调用。PC 相对调用本质上是位置无关的,因此不需要重定位条目。程序链接器将为 PLT 条目创建一个重定位,指示动态链接器哪个符号与该条目相关联。这个过程将共享库中每个函数调用的动态重定位数量从每个函数调用一个减少到每个被调用函数一个。

进一步地,PLT(程序链接表)入口通常由动态链接器懒惰地重定位。在大多数 ELF 系统上,这种懒惰行为可以通过在运行程序时设置 LD_BIND_NOW 环境变量来覆盖。然而,默认情况下,动态链接器实际上不会对 PLT 应用重定位,直到某些代码真正调用了相关函数。这也加快了启动时间,因为许多程序的调用不会触发每一个可能的函数。考虑到共享 C 库时尤其如此,因为它的函数调用远比任何典型的程序要多得多。

为了使这一切正常工作,程序链接器将 PLT 入口初始化为加载一个索引到某个寄存器中或将其压入栈中,然后跳转到公共代码。公共代码回调到动态链接器,动态链接器使用该索引查找适当的 PLT 重定位,并利用该重定位找到被调用的函数。动态链接器随后使用函数的地址初始化 PLT 条目,然后跳转到该函数的代码。下次调用该函数时,PLT 条目将直接跳转到该函数。

在给出一个例子之前,我将谈谈位置无关代码中的另一个主要数据结构,即全局偏移表(Global Offset Table,简称 GOT)。它用于全局和静态变量。对于每个来自位置无关代码的全局变量引用,编译器将生成一个从 GOT 中加载以获取变量地址的操作,随后再执行第二个加载以获取变量的实际值。GOT 的地址通常存储在一个寄存器中,以便高效访问。与 PLT 一样,GOT 并不在.o 文件中存在,而是由程序链接器创建。程序链接器将创建动态重定位,动态链接器将在运行时使用这些重定位来初始化 GOT。与 PLT 不同,动态链接器在程序启动时总会完全初始化 GOT。

例如,在 i386 上,GOT 的地址存储在寄存器%ebx 中。这个寄存器在每个位置无关代码函数的入口处进行初始化。初始化序列因编译器而异,但通常看起来像这样:

1
2
call __i686.get_pc_thunk.bx
add $offset,%ebx

函数 __i686.get_pc_thunk.bx 的内容如下:

1
2
mov (%esp),%ebx
ret

这一指令序列使用位置无关序列获取它运行的地址。然后使用一个偏移量获取 GOT 的地址。请注意,这要求 GOT 始终与代码保持固定的偏移,无论共享库被加载到哪里。也就是说,动态链接器必须将共享库作为一个固定单元加载;它不能将不同部分加载到不同地址。

现在,通过从 %ebx 的固定偏移量加载地址,来读取或写入全局和静态变量。程序链接器将为 GOT 中的每个条目创建动态重定位,告知动态链接器如何初始化该条目。这些重定位的类型为 GLOB_DAT。

对于函数调用,程序链接器将设置一个 PLT 条目,形如下述所示:

1
2
3
jmp *offset(%ebx)
pushl #index
jmp first_plt_entry

程序链接器将为 PLT 中的每个条目在 GOT 中分配一个条目。它将为 GOT 条目创建类型为 JMP_SLOT 的动态重定位。它将初始化 GOT 条目为共享库的基地址加上上面代码序列中第二个指令的地址。当动态链接器对 JMP_SLOT 重定位执行初始懒惰绑定时,它仅需在 GOT 条目中添加共享库加载地址与共享库基地址之间的差异。其效果是,第一次 jmp 指令将跳转到第二个指令,该指令将压入索引条目并跳转到第一个 PLT 条目。第一个 PLT 条目是特殊的,形如下述所示:

1
2
pushl 4(%ebx)
jmp *8(%ebx)

这引用了 GOT 中的第二和第三条目。动态链接器将初始化它们,使其具有适合于回调到动态链接器本身的相应值。动态链接器将使用第一个代码序列中压入的索引来查找 JMP_SLOT 重定位。当动态链接器确定要调用的函数时,它将把函数的地址存储到第一个代码序列所引用的 GOT 条目中。因此,下次调用该函数时,jmp 指令将直接跳转到正确的代码。

这只是快速浏览了许多细节,但我希望这能传达主要思想。这意味着,对于 i386 上的位置无关代码,每次对全局函数的调用在第一次调用后需要多一个额外的指令。每次对全局或静态变量的引用也需要多一个额外的指令。几乎每个函数在开始时使用四个额外的指令来初始化%ebx(不引用任何全局变量的叶子函数不需要初始化%ebx)。所有这些对程序缓存都有一定的负面影响。这是为了让动态链接器快速启动程序而付出的运行时性能代价。

在其他处理器上,细节自然有所不同。然而,整体风格是相似的:位置无关代码在共享库中启动更快,但运行稍微慢一些。

5 Part 5

5.1 Shared Libraries Redux

当程序链接器将依赖于位置的代码放入共享库时,它必须将对象文件中的更多重定位信息复制到共享库中。这些重定位信息将在运行时由动态链接器计算为动态重定位。有些重定位信息不必被复制;例如,指向共享库中局部符号的相对程序计数器重定位可以由程序链接器完全解析,而不需要动态重定位。然而,请注意,指向全局符号的相对程序计数器重定位确实需要动态重定位;否则,主可执行文件将无法覆盖该符号。有些重定位信息必须存在于共享库中,但不需要是对象文件中重定位信息的实际副本;例如,一个计算共享库中局部符号绝对地址的重定位通常可以用 RELATIVE 重定位替代,该重定位仅指示动态链接器添加共享库加载地址与其基址之间的差值。使用 RELATIVE 重定位的优势在于动态链接器可以在运行时快速计算,因为它不需要确定符号的值。

对于位置无关代码,程序链接器的工作更加复杂。编译器和汇编器会协同生成位置无关代码的特殊重定位。虽然各个处理器的细节有所不同,但通常会有一个 PLT 重定位和一个 GOT 重定位。这些重定位会指导程序链接器为 PLT 或 GOT 添加一个条目,同时执行一些计算。例如,在 i386 上,位置无关代码中的函数调用会生成一个 R_386_PLT32 重定位。该重定位将像往常一样引用一个符号。它会指导程序链接器为该符号添加一个 PLT 条目,如果尚不存在的话。重定位的计算随后是对 PLT 条目的 PC 相对引用。(重定位名称中的 32 指的是引用的大小,即 32 位)。昨天我描述了在 i386 上每个 PLT 条目也都有一个对应的 GOT 条目,因此 R_386_PLT32 重定位实际上指导程序链接器同时创建一个 PLT 条目和一个 GOT 条目。

当程序链接器在 PLT 或 GOT 中创建一个条目时,它还必须生成一个动态重定位以告知动态链接器有关该条目的信息。通常这将是一个 JMP_SLOT 或 GLOB_DAT 重定位。

这就意味着程序链接器必须跟踪每个符号的 PLT 条目和 GOT 条目。当然,最初不会有这样的条目。当链接器看到 PLT 或 GOT 重定位时,它必须检查重定位所引用的符号是否已经有 PLT 或 GOT 条目,如果没有则创建一个。注意,单个符号可能同时具有 PLT 条目和 GOT 条目;这会发生在位置无关代码中,该代码既调用函数又取其地址。

动态链接器在 PLT 和 GOT 表中的工作是简单地在运行时计算 JMP_SLOT 和 GLOB_DAT 重定位。这里的主要复杂性是我昨天描述的 PLT 条目的惰性求值。

C 语言允许取函数地址,这引入了一个有趣的复杂性。在 C 中,您可以取函数的地址,并且可以将这个地址与另一个函数地址进行比较。问题在于,如果您在共享库中取一个函数的地址,得到的自然结果将是 PLT 条目的地址。毕竟,调用函数的跳转就是跳转到这个地址。然而,每个共享库都有其自己的 PLT,因此特定函数的地址在每个共享库中都会有所不同。这意味着在不同共享库中生成的函数指针的比较可能不同,而它们应该相同。这不是一个纯假设的问题;当我做一个错误端口时,在我修复错误之前,我看到在 Tcl 共享库中比较函数指针时失败了。

在大多数处理器上,解决此错误的办法是对具有 PLT 条目但未定义的符号进行特殊标记。通常符号将被标记为未定义,但带有非零值——该值将设置为 PLT 条目的地址。当动态链接器在搜索用于重定位的符号值时,如果它发现这样的特殊标记符号,它将使用非零值。这将确保所有非函数调用的符号引用都将使用相同的值。为了使这项工作正常,编译器和汇编器必须确保任何不涉及调用的函数引用都不会携带标准 PLT 重定位。这种对函数地址的特殊处理需要在程序链接器和动态链接器中实现。

5.2 ELF Symbols

好了,关于共享库的内容够多了。让我们更详细地讨论 ELF 符号。我不打算详细列出确切的数据结构——您可以查阅 ELF ABI。我要讨论的是不同的字段及其含义。许多不同类型的 ELF 符号也被其他目标文件格式使用,但我不会涵盖这一点。

ELF 符号表中的一个条目有八个部分信息:名称,值,大小,节,绑定,类型,可见性,以及未定义的附加信息(目前有六个位未定义,尽管可能会添加更多)。在共享对象中定义的 ELF 符号也可能有一个关联的版本名称。

对于普通定义的符号,节是在文件中的某个节(具体而言,符号表条目保存了指向节表的索引)。对于目标文件,值是相对于节的起始位置。对于可执行文件,值是绝对地址。对于共享库,值是相对于基地址。

对于未定义引用符号,节索引是特殊值 SHN_UNDEF,其值为 0。节索引 SHN_ABS(0xfff1)表示符号的值是一个绝对值,而不是相对于任何节。

节索引 SHN_COMMON(0xfff2)表示公共符号。公共符号是为处理 Fortran 公共块而发明的,它们通常也用于 C 语言中的未初始化全局变量。公共符号具有不寻常的语义。公共符号的值为零,但将大小字段设置为所需的大小。如果一个目标文件有一个公共符号,而另一个文件有一个定义,该公共符号将被视为未定义引用。如果公共符号没有定义,程序链接器会假装看到一个初始化为零的适当大小的定义。两个目标文件可能有不同大小的公共符号,在这种情况下,程序链接器将使用最大的大小。在共享库之间实现公共符号的语义是一个棘手的问题,最近通过引入公共符号的类型和特殊节索引有所缓解(见下面关于符号类型的讨论)。

除了公共符号外,ELF 符号的大小是变量或函数的大小。这主要用于调试目的。

ELF 符号的绑定可以是全局的、本地的或弱的。全局符号是全局可见的。本地符号只有在本地可见(例如,一个静态函数)。弱符号有两种类型。弱未定义引用类似于普通未定义引用,除了如果重定位引用了一个没有定义符号的弱未定义引用符号,则它不是错误。相反,重定位的计算就像该符号的值为零一样。

弱定义符号允许与同名的非弱定义符号链接,而不引起多重定义错误。历史上,程序链接器处理弱定义符号有两种方式。在 SVR4 上,如果程序链接器看到一个弱定义符号后跟同名的非弱定义符号,它将发出多重定义错误。然而,非弱定义符号后跟弱定义符号不会导致错误。在 Solaris 上,一个弱定义符号后跟一个非弱定义符号会导致所有引用附加到非弱定义符号,而没有错误。行为上的差异是由于 ELF ABI 中的模糊性,不同的人有不同的解读。GNU 链接器遵循 Solaris 的行为。

ELF 符号的类型如下所示:

  • STT_NOTYPE: no particular type.

  • STT_OBJECT: a data object, such as a variable.

  • STT_FUNC: a function

  • STT_SECTION: a local symbol associated with a section. This type of symbol is used to reduce the number of local symbols required, by changing all relocations against local symbols in a specific section to use the STT_SECTION symbol instead.

  • STT_FILE: a special symbol whose name is the name of the source file which produced the object file.

  • STT_COMMON: a common symbol. This is the same as setting the section index to SHN_COMMON, except in a shared object. The program linker will normally have allocated space for the common symbol in the shared object, so it will have a real section index. The STT_COMMON type tells the dynamic linker that although the symbol has a regular definition, it is a common symbol.

  • STT_TLS: a symbol in the Thread Local Storage area. I will describe this in more detail some other day.

ELF 符号的可见性是为提供更好的控制符号在共享库之外的可访问性而发明的。基本思想是符号在共享库内可能是全局的,但在共享库外是本地的。

  • STV_DEFAULT: the usual visibility rules apply: global symbols are visible everywhere.
  • STV_INTERNAL: the symbol is not accessible outside the current executable or shared library.
  • STV_HIDDEN: the symbol is not visible outside the current executable or shared library, but it may be accessed indirectly, probably because some code took its address.
  • STV_PROTECTED: the symbol is visible outside the current executable or shared object, but it may not be overridden. That is, if a protected symbol in a shared library is referenced by other code in the shared library, that other code will always reference the symbol in the shared library, even if the executable defines a symbol with the same name.

6 Linkers part 6

6.1 重定位 (Relocations)

重定位是在内容上执行的计算,重定位还可以指示链接器采取其他操作,比如创建 PLT 或 GOT 条目。让我们仔细看看这个计算。

一般来说,重定位有一个类型、一个符号、一个偏移量和一个增量。从链接器的角度来看,内容仅仅是一系列未解释的字节。重定位会根据需要更改这些字节,以生成正确的最终可执行文件。例如,考虑 C 代码 g = 0; 其中 g 是一个全局变量。在 i386 上,编译器会将其转换为汇编语言指令,这很可能是 movl $0, g=(对于位置相关代码-位置无关代码将从 GOT 加载 g 的地址)。现在,C 代码中的 =g 是一个全局变量,我们或多或少都知道这意味着什么。而汇编代码中的 g 并不是那个变量,它是一个符号,表示该变量的地址。

汇编器不知道全局变量 g 的地址,换句话说就是汇编器不知道符号 g 的值。链接器将负责选择那个地址。因此,汇编器必须告诉链接器它在这条指令中需要使用 g 的地址。汇编器实现这一点的方法是创建一个重定位(relocation)。我们不为每条指令使用单独的重定位类型;相反,每个处理器将具有一组适合其机器架构的自然重定位类型。每种重定位类型表示一个特定的计算。

在 i386 的情况下,汇编器将生成这些字节:

1
c7 05 00 00 00 00 00 00 00 00
  • c7 05 是指令( movl , 将常量移动到地址)。
  • 前四个 00 字节是 32 位常量 0
  • 后四个 00 字节是地址。

汇编器通过生成(在这种情况下)一个 R_386_32 重定位告诉链接器将符号 g 的值放入那四个字节。对于这个重定位,符号将是 g ,偏移量将是指令的最后四个字节,类型将是 R_386_32 ,增量将是 0=(在 i386 的情况下,增量存储在内容中,而不是在重定位本身中,但这是一个细节)。类型 =R_386_32 表示一个特定的计算,即:将符号的值与增量的 32 位和放入偏移量中。由于对于 i386 增量存储在内容中,这也可以表示为:将符号的值加到偏移位置的 32 位字段中。当链接器执行这个计算时,指令中的地址将是全局变量 g 的地址。无论细节如何,重要的一点是重定位通过应用根据类型选择的特定计算来调整内容。

一个使用加数的简单案例示例是:

1
2
char a[10]; // 一个全局数组。
char* p = &a[1]; // 在一个函数中。

对 p 的赋值最终需要对符号 a 进行重定位。在这里,加数将是 1,以便生成的指令引用 a + 1 而不是 a + 0

为了指出重定位是如何依赖于处理器的,我们来考虑在 RISC 处理器上执行 g = 0; 的情况:PowerPC(在 32 位模式下)。在这种情况下,需要多个汇编语言指令:

1
2
3
li 1,0 // 将寄存器 1 设置为 0
lis 9,g@ha // 将 g 的高调整部分加载到寄存器 9 中
stw 1,g@l(9) // 将寄存器 1 的值存储到寄存器 9 中地址加上 g 的低调整部分的地址
  • lis 指令将一个值加载到寄存器 9 的高 16 位中,将低 16 位设置为零。
  • stw 指令将一个带符号的 16 位值添加到寄存器 9,以形成一个地址,然后将寄存器 1 的值存储到该地址。
  • 操作数的 @ha 部分指示汇编器生成一个 R_PPC_ADDR16_HA 重定位。
  • @l 生成一个 R_PPC_ADDR16_LO 重定位。

这些重定位的目标是计算符号 g 的值并将其用作存储地址。

这些信息足够确定这些重定位所执行的计算。

  • R_PPC_ADDR16_HA 重定位计算为 (SYMBOL >> 16) + ((SYMBOL & 0x8000) ? 1 : 0)
  • R_PPC_ADDR16_LO 计算为 SYMBOL & 0xffff

R_PPC_ADDR16_HA 的额外计算是因为 stw 指令添加的是带符号的 16 位值,这意味着如果低 16 位出现负数,我们必须相应地调整高 16 位。重定位的偏移量使得 16 位结果值被存储到机器指令的适当部分。

我在这里讨论的具体重定位示例是针对 ELF 格式的,但同样类型的重定位在任何对象文件格式中都会出现。

我展示的示例是出现在对象文件中的重定位。如第 4 部分所述,这些类型的重定位也可能出现在共享库中,如果它们被程序链接器复制到那里。在 ELF 中,还有一些特定的重定位类型只出现在共享库或可执行文件中,而从未出现在对象文件中。这些是先前讨论的 JMP_SLOT、GLOB_DAT 和 RELATIVE 重定位。另一种只出现在可执行文件中的重定位类型是 COPY 重定位,我将在后面讨论。

6.2 Position Dependent Shared Libraries

我意识到在第 4 部分中,我忘记提到 ELF 共享库使用 PLT 和 GOT 表的一个重要原因。共享库的概念是允许将相同的共享库映射到不同的进程中。只有当共享库代码在每个进程中看起来都一样时,这种做法才能达到最大的效率。如果看起来不一样,那么每个进程将需要自己的私有副本,这样就会失去在物理内存和共享上的节省。

如第 4 部分所讨论,当动态链接器加载一个包含位置依赖代码的共享库时,它必须应用一组动态重定位。这些重定位将改变共享库中的代码,从而使其不再可共享。

PLT 和 GOT 的优点在于它们将重定位移到其他地方,即 PLT 和 GOT 表本身。这些表可以放入共享库的读写部分。这个共享库的这一部分将远小于代码。使用共享库的每个进程中的 PLT 和 GOT 表会有所不同,但代码将是相同的。

7 Linkers part 7: classic small optimization: Thread Local Storage

我假设你知道什么是线程。通常情况下,拥有一个全局变量在每个线程中可以取不同的值是非常有用的(如果你不明白这有什么用,听我说就行)。也就是说,这个变量对程序是全局的,但具体的值是线程局部的。如果线程 A 将线程局部变量设置为 1,而线程 B 随后将其设置为 2,那么在线程 A 中运行的代码将继续看到变量的值为 1,而在线程 B 中运行的代码看到的值为 2。在 Posix 线程中,这种类型的变量可以通过 pthread_key_create 创建,通过 pthread_getspecificpthread_setspecific 访问。

这些函数的工作效果还不错,但每次访问都要进行一次函数调用是很麻烦也很不方便。如果你可以只是声明一个普通的全局变量并将其标记为线程局部,那将更有用。这就是线程局部存储(Thread Local Storage, TLS)的概念,我相信这是在 Sun 发明的。在支持 TLS 的系统上,任何全局(或静态)变量都可以用 __thread 注解。这样,变量就是线程局部的。

显然,这需要编译器的支持。它还需要程序链接器和动态链接器的支持。为了获得最大效率——如果不追求最大效率,那为什么要这样做呢?——还需要一些内核支持。在 ELF 系统上,线程局部存储(TLS)的设计完全支持共享库,包括多个共享库和可执行文件本身使用相同的名称来引用单个 TLS 变量。TLS 变量可以初始化。程序可以获取 TLS 变量的地址,并在线程之间传递指针,因此 TLS 变量的地址是一个动态值,必须是全局唯一的。

这个是怎么实现的?第一步:为 TLS 变量定义不同的存储模型。

这些存储模型按灵活性递减的顺序定义。为了提高效率和简化,支持 TLS 的编译器允许开发者指定使用的适当 TLS 模型(在 gcc 中,可以使用-ftls-model 选项来实现,尽管全局动态和局部动态模型还需要使用-fpic)。因此,当编译将被放入可执行文件且永远不会在共享库中的代码时,开发者可以选择将 TLS 存储模型设置为初始可执行文件。

当然,在实践中,开发者往往不知道代码将如何使用。开发者也可能对 TLS 模型的复杂性不够了解。另一方面,程序链接器知道它是在创建一个可执行文件还是一个共享库,并且知道 TLS 变量是否在本地定义。因此,程序链接器负责在可能的情况下自动优化对 TLS 变量的引用。这些引用以重定位的形式出现,链接器通过以不同的方式更改代码来优化引用。

程序链接器还负责将所有 TLS 变量汇总到一个单独的 TLS 段中(稍后我会更多地谈论段,暂时可以将它们视为一个节)。动态链接器必须将可执行文件和所有包含的共享库的 TLS 段进行分组,解决动态 TLS 重定位,并在使用 dlopen 时动态构建 TLS 段。内核必须确保对 TLS 段的访问是高效的。

以上都是相当一般性的内容。我们做一个例子,再次以 i386 ELF 为例。i386 ELF TLS 有三种不同的实现;我将着眼于 gnu 实现。考虑这段简单代码:

1
2
__thread int i;
int foo() { return i; }

在全局动态模式下,这会生成类似于以下的 i386 汇编代码:

1
2
3
leal i@TLSGD(,%ebx,1), %eax
call ___tls_get_addr@PLT
movl (%eax), %eax

回想一下第 4 部分, %ebx 保存了 GOT 表的地址。第一条指令将对变量 i 具有 R_386_TLS_GD 重定位;重定位将应用于 leal 指令的偏移量。当程序链接器看到这个重定位时,它将为 TLS 变量 i 在 GOT 表中创建两个连续的条目。第一个条目会获得一个 R_386_TLS_DTPMOD32 动态重定位,第二个条目会获得一个 R_386_TLS_DTPOFF32 动态重定位。动态链接器将把 DTPMOD32 GOT 条目设置为保存定义该变量的对象的模块 ID。模块 ID 是在动态链接器表中标识可执行文件或特定共享库的索引。动态链接器将把 DTPOFF32 GOT 条目设置为该模块在 TLS 段中的偏移量。 _tls_get_addr 函数将使用这些值来计算地址(该函数还处理 TLS 变量的延迟分配,这是动态链接器特有的进一步优化)。注意, __tls_get_addr 实际上是由动态链接器本身实现的;因此,全局动态 TLS 变量在静态链接的可执行文件中不被支持(也没有必要)。

在这个时候,你可能在想 pthread_getspecific 有什么效率问题。TLS 的真正优势在于当你看到程序链接器可以做什么时。上面显示的 leal; call 序列是经典的:编译器总是会生成相同的序列来访问全局动态模式下的 TLS 变量。程序链接器利用了这一事实。如果程序链接器看到上面的代码将进入到一个可执行文件中,它知道访问不必被视为全局动态;可以将其视为初始可执行文件。程序链接器实际上会将代码重写为如下:

1
2
movl %gs:0, %eax
subl $i@GOTTPOFF(%ebx), %eax

在这里我们看到,TLS 系统利用 %gs 段寄存器(在操作系统的配合下),指向可执行文件的 TLS 段。对于每个支持 TLS 的处理器,都会做一些类似的效率优化。由于程序链接器在构建可执行文件,它构建 TLS 段,并知道 i 在该段中的偏移量。 GOTTPOFF 并不是一个真正的重定位;它是在程序链接器中创建并解析的。它当然是从 GOT 表到 TLS 段中 i 的地址的偏移量。原始序列中的 movl (%eax), %eax 仍然保留,用于实际加载变量的值。

实际上,如果 i 没有在可执行文件中定义,那就是会发生的情况。在我展示的例子中,i在可执行文件中定义,因此程序链接器可以真正从全局动态访问一直到局部可执行访问。这看起来如下:

1
2
movl %gs:0,%eax
subl $i@TPOFF,%eax

这里 i@TPOFF 仅仅是 i 在 TLS 段中的已知偏移量。我不会深入探讨为什么使用 subl 而不是 addl ;只需说这又是动态链接器中的一个效率优化。

如果你关注到这些,你会看到,当一个可执行文件访问在该可执行文件中定义的 TLS 变量时,通常需要两个指令来计算地址,通常后面还有另一个指令来实际加载或存储值。这比调用 pthread_getspecific 高效得多。可以承认,当共享库访问 TLS 变量时,结果与 pthread_getspecific 并没有什么太大区别,但也不应该更差。而且使用__thread 的代码更容易编写和阅读。

这是一场真正的疾风之旅。i386 上有三种独立但相关的 TLS 实现(称为 sun、gnu 和 gnu2),定义了 23 种不同的重定位类型。我当然不会尝试描述所有细节;无论如何我也不知道所有细节。所有这些都旨在为给定存储模型提供高效访问 TLS 变量。

TLS 是否值得在程序链接器和动态链接器中增加额外的复杂性?由于这些工具被每个程序使用,并且由于 C 标准全局变量 errno 尤其可以使用 TLS 实现,因此答案很可能是肯定的。

8 Linkers part 8: ELF Segments

我之前说过可执行文件格式通常与目标文件格式相同。对于 ELF 来说,这是正确的,但有一个翻转。

  • 在 ELF 中,目标文件由段组成:文件中的所有数据通过段表访问。可执行文件和共享库通常包含一个段表,程序如 nm 会使用它。
  • 但是,操作系统和动态链接器不使用段表。相反,它们使用段表,提供了文件的另一种视图。

9 Linkers part 9

9.1 Symbol Versions

共享库提供了一个 API。因为可执行文件是使用一组特定的头文件构建的,并且链接了特定实例的共享库,它还提供了一个 ABI。能够独立于可执行文件更新共享库是非常 desirable。这允许修复共享库中的错误,并且允许共享库和可执行文件分开分发。有时更新共享库需要更改 API,有时更改 API 又需要更改 ABI。当共享库的 ABI 发生变化时,便无法在不更新可执行文件的情况下更新共享库。这是一个不幸的情况。

例如,考虑系统 C 库和 stat 函数。当文件系统升级以支持 64 位文件偏移时,必须更改 stat 结构中某些字段的类型。这是 stat 的 ABI 的变化。新版本的系统库应该提供返回 64 位值的 stat。但是旧的现有可执行文件却期望调用返回 32 位值的 stat。这可以通过在系统头文件中使用复杂的宏来解决。但还有更好的方法。

更好的方法是符号版本(symbol version),这是一种由 Sun 公司引入并由 GNU 工具扩展的机制。每个共享库可以定义一组(多个)符号版本,并为每个定义的符号分配特定的版本。版本和符号分配是通过在创建共享库时传递给程序链接器的脚本完成的。

当一个可执行文件或共享库 A 链接到另一个共享库 B 时,A 引用了在 B 中定义的具有特定版本的符号 S,A 中的未定义动态符号引用 S 被赋予 B 中符号 S 的版本。当动态链接器看到 A 引用的是 S 的特定版本时,它会将其链接到 B 中的该特定版本。如果 B 后来引入了 S 的新版本,只要 B 继续提供旧版本的 S,这将不会影响 A。

例如,当 stat 发生变化时,C库将提供两个版本的 stat,一个是旧版本(例如,LIBC_1.0),另一个是新版本(LIBC_2.0)。新版本的 stat 将被标记为默认版本——程序链接器将使用它来满足对象文件中对 stat 的引用。链接到旧版本的可执行文件将需要 LIBC_1.0 版本的 stat,因此将继续正常工作。请注意,甚至可以在单个程序中使用两个版本的 stat,通过不同的共享库进行访问。

如您所见,版本实际上是符号名称的一部分。最大的不同在于,共享库可以定义一个特定的版本,用于满足没有版本的引用。

版本也可以在目标文件中使用(这是对原始 Sun 实现的 GNU 扩展)。这对于在不需要版本脚本的情况下指定版本非常有用。当符号名称包含@字符时,@之前的字符串是符号的名称,@之后的字符串是版本。如果有两个连续的@字符,那么这就是默认版本。

9.2 Relaxation

一般来说,程序链接器不会改变内容,除了应用重定位。然而,程序链接器在链接时可以执行一些优化。其中之一就是松弛。

放松本质上是处理器特定的。它包括优化代码序列,当最终地址已知时,这些序列可以变得更小或更有效率。最常见的放松类型是对调用指令的处理。像 m68k 这样的处理器支持不同的 PC 相对调用指令:一种具有 16 位偏移量,另一种具有 32 位偏移量。当调用一个在 16 位偏移范围内的函数时,使用较短的指令更有效率。在链接时缩小这些指令的优化被称为放松。

放松是基于重定位条目应用的。链接器查找可能被放松的重定位,并检查它们是否在范围内。如果在范围内,链接器将应用放松,可能会缩小内容的大小。放松通常只能在链接器识别出被重定位的指令时进行。应用放松可能会使其他重定位也在范围内,因此放松通常在循环中进行,直到没有更多的机会为止。

当链接器在内容中间放松一个重定位时,它可能需要调整任何跨过放松点的相对程序计数器(PC)引用。因此,汇编器需要为所有的 PC 相对引用生成重定位条目。在不进行放松时,这些重定位可能并不是必需的,因为在单个内容内的 PC 相对引用在内容最终位置的任何地方都是有效的。然而在放松时,链接器需要查看所有适用于该内容的其他重定位,并在适当的地方调整 PC 相对引用。这个调整将只是重新计算 PC 相对偏移量。

当然,也可以应用不会改变内容大小的放松。例如,在 MIPS 架构中,位置无关调用序列通常是将函数的地址加载到$25 寄存器中,然后通过该寄存器进行间接调用。当调用的目标在分支和调用指令的 18 位范围内时,通常使用分支和调用会更加高效,因为这样处理器在开始调用之前不必等待$25 的加载完成。这个放松改变了指令序列而不改变大小。

10 Linkers part 10: Parallel Linking

链接过程在一定程度上可以并行化。这可以帮助隐藏 I/O 延迟,并更好地利用现代多核系统。我对 gold 的意图是利用这些想法加速链接过程。

可以并行化的第一个领域是读取所有输入文件的符号和重定位项。符号必须按顺序处理;否则,对于链接器来说,将很难正确解析多个定义。尤其是,在处理某个归档文件之前,必须完全处理掉所有在归档之前使用的符号,否则链接器无法知道在链接中应该包含归档的哪些成员(我想我还没有谈到归档文件)。然而,尽管有这些顺序要求,实际的 I/O 并行执行仍然是有益的。

在所有符号和重定位项读取完成后,链接器必须完成所有输入内容的布局。这其中大部分无法并行完成,因为设置某种类型内容的位置需要知道所有前置类型内容的大小。在进行布局时,链接器可以确定所有需要写入输出文件的数据的最终位置。

布局完成后,读取内容、应用重定位并将内容写入输出文件的过程可以完全并行化。每个输入文件可以单独处理。

由于在布局阶段已知输出文件的最终大小,因此可以对输出文件使用 mmap。当不进行放松时,可以将输入内容直接读取到输出文件中的指定位置,并在该位置进行重定位。这减少了所需的系统调用数量,并理想地允许操作系统为输出文件执行最佳的磁盘 I/O。

11 Linkers part 11: Archives

归档是传统的 Unix 包格式。它们是由 ar 程序创建的,通常以.a 扩展名命名。归档文件通过-l 选项传递给 Unix 链接器。

尽管 ar 程序能够从任何类型的文件创建归档,但通常用于将目标文件放入归档。当以这种方式使用时,它为归档创建符号表。符号表列出了归档中任何目标文件定义的所有符号,并指示每个符号由哪个目标文件定义。最初,符号表是由 ranlib 程序创建的,但如今它总是默认由 ar 创建(尽管如此,许多 Makefile 仍然不必要地运行 ranlib)。

当链接器看到一个归档时,它会查看归档的符号表。对于每个符号,链接器检查是否见过对该符号的未定义引用而没有看到定义。如果是这种情况,它会从归档中提取目标文件并将其包含在链接中。换句话说,链接器提取所有定义了被引用但尚未定义的符号的目标文件。

此操作重复进行,直到归档中不能再定义更多符号。这允许归档中的目标文件引用同一归档中其他目标文件定义的符号,而无需担心它们出现的顺序。

请注意,链接器根据命令行中归档在其他目标文件和归档相对于位置的顺序进行考虑。如果一个目标文件在命令行中出现在归档之后,那么该归档将不会用于定义目标文件引用的符号。

一般来说,如果归档提供了公共符号的定义,链接器将不会包含这些归档。你会记得,如果链接器看到一个公共符号,然后看到一个与之同名的已定义符号,它将把公共符号视为未定义引用。只有当有其他理由将已定义符号包含在链接中时,这种情况才会发生;已定义符号不会从归档中被提取。

在旧的基于 a.out 的 SunOS 系统中,归档中的公共符号有一个有趣的变化。如果链接器看到一个公共符号,然后看到归档中的公共符号,它不会包含来自归档的目标文件,但如果归档中的大小大于当前大小,它会将公共符号的大小更改为归档中的大小。C库在实现 stdin 变量时依赖于这种行为。

12 Linkers part 12: Symbol Resolution, 符号解析

我发现符号解析是链接器中更棘手的方面之一。符号解析是链接器在第二次及后续看到特定符号时所做的事情。我在之前的一些文章中已经提到过这个主题, 但让我们更深入地看一下。

某些符号是特定目标文件的局部符号。出于符号解析的目的,我们可以忽略这些符号,因为根据定义,链接器永远不会看到它们超过一次。在 ELF 中,这些符号的绑定为 STB_LOCAL

一般来说,符号是通过名称来解析的:每个具有相同名称的符号都是同一个实体。我们已经看到了一些对这一普遍规则的例外。

  • 一个符号可以具有版本:两个名称相同但版本不同的符号是不同的符号。
  • 一个符号可以具有非默认可见性:在一个共享库中具有隐藏可见性的符号与在另一个共享库中具有相同名称的符号不是同一个符号。

影响符号解析的特征包括:

– 符号名称– 符号版本– 符号是否为默认版本– 符号是定义、引用还是通用符号– 符号可见性– 符号是弱符号还是强符号(即非弱符号)– 符号是否在包含在输出中的常规目标文件中定义,或在共享库中– 符号是否为线程局部– 符号是指向函数还是变量

符号解析的目标是确定符号的最终值。在所有符号解析完成后,我们应该知道定义该符号的具体目标文件或共享库,并且我们应该知道该符号的类型、大小等。有可能在所有符号表读取完毕后,一些符号仍然未定义;一般来说,只有在某些重定位引用该符号时,这才会导致错误。

此时我想提出一个简单的符号解析算法,但我不认为我可以做到。不过,我会尽量覆盖所有重点。让我们假设我们有两个同名的符号。我们将第一个看到的符号称为 A,而新的符号称为 B。(在下面的算法中,我将忽略符号的可见性;我希望可见性的影响应该是显而易见的。)

  1. 如果 A 有一个版本:
    • 如果 B 有一个与 A 不同的版本,它们实际上是不同的符号。
    • 如果 B 有与 A 相同的版本,它们是相同的符号;继续。
    • 如果 B 没有版本,而 A 是该符号的默认版本,它们是相同的符号;继续。
    • 否则,B 可能是不同的符号。但请注意,如果 A 和 B 都是未定义的引用,那么 A 可能指的是该符号的默认版本,但我们尚不知道。在这种情况下,如果 B 没有版本,A 和 B 确实是相同的符号。直到我们看到实际的定义之前,我们无法确定。
  1. 如果 A 没有版本:

    • 如果 B 没有版本,它们是相同的符号;继续进行。
    • 如果 B 有版本,并且是默认版本,它们是相同的符号;继续进行。
    • 否则,B 可能是不同的符号,如上所述。
  2. 如果 A 是线程局部而 B 不是,或者反之,则我们有一个错误。

  3. 如果 A 是未定义引用:

    • 如果 B 是未定义引用,那么我们可以完成解析,并在某种程度上忽略 B。
    • 如果 B 是定义或公共符号,那么我们可以将 A 解析为 B。
  4. 如果 A 是目标文件中的强定义:

    • 如果 B 是未定义引用,那么我们将 B 解析为 A。
    • 如果 B 是目标文件中的强定义,那么我们有一个多重定义错误。
    • 如果 B 是目标文件中的弱定义,那么 A 将覆盖 B。实际上,B 被忽略。
    • 如果 B 是公共符号,那么我们将 B 视为未定义引用。
    • 如果 B 是共享库中的定义,那么 A 将覆盖 B。动态链接器将更改共享库中所有对 B 的引用,以指向 A。
  5. 如果 A 是目标文件中的弱定义,我们的处理方式与强定义情况相同,有一个例外:如果 B 是目标文件中的强定义。在原始的 SVR4 链接器中,该情况被视为多重定义错误。在 Solaris 和 GNU 链接器中,该情况通过让 B 覆盖 A 来处理。

  6. 如果 A 是目标文件中的公共符号:

    • 如果 B 是公共符号,我们将 A 的大小设置为 A 和 B 的大小中的最大值,然后将 B 视为未定义引用。
    • 如果 B 是共享库中的函数类型定义,那么 A 将覆盖 B(这个特殊情况是为了正确处理一些 Unix 系统库)。
    • 否则,我们将 A 视为未定义引用。
  7. 如果 A 是共享库中的定义,那么如果 B 是常规对象中的定义(强或弱),它将覆盖 A。否则,我们将 A 视为定义在目标文件中。

  8. 如果 A 是共享库中的公共符号,我们有一个有趣的情况。共享库中的符号必须有地址,因此它们不能像目标文件中的符号那样是公共的。但 ELF 确实允许共享库中的符号具有 STT_COMMON 类型(这是一个相对较新的添加)。对于符号解析的目的,如果 A 是共享库中的公共符号,我们仍然将其视为定义,除非 B 也是公共符号。在后者情况下,B 覆盖 A,B 的大小设置为 A 和 B 的大小中的最大值。

13 Linkers part 13: Symbol Versions Redux

13.1 向后兼容性

正如我之前所讨论的,符号版本是一个 ELF 扩展,旨在解决一个特定的问题:使得可以在不更改现有可执行文件的情况下升级共享库。也就是说,它们为共享库提供了向后兼容性。有许多相关的问题是符号版本无法解决的。它们并不提供共享库的向前兼容性:如果你升级了可执行文件,可能也需要升级共享库(如果有一个功能可以使你的可执行文件基于旧版本的共享库构建,那将是很好的,但在实践中很难实现)。它们只在共享库接口上工作:它们不帮助系统调用的 ABI 变更,而这些变更发生在内核接口上。它们也不帮助解决共享库的不兼容版本共享的问题,特别是在复杂应用程序是由几个具有不兼容依赖的现有共享库构建时可能会发生这种情况。

尽管有这些局限性,共享库的向后兼容性仍然是一个重要问题。使用符号版本来确保向后兼容性需要一种细致而严格的方法。你必须首先对每个符号应用版本。如果共享库中的某个符号没有版本,则不可能以向后兼容的方式进行更改。接下来,你必须密切关注每个符号的 ABI。如果由于任何原因符号的 ABI 发生变化,必须提供一个实现旧 ABI 的副本。这个副本应该标记为原始版本。新的符号必须给一个新版本。

符号的 ABI 变化可能有多种方式。对函数的参数类型或返回类型的任何更改都是 ABI 变化。变量类型的任何变化都是 ABI 变化。如果参数或返回类型是结构或类,则任何字段类型的变化都是 ABI 变化,即如果结构中的某个字段指向另一个结构,而该结构发生变化,则 ABI 也发生了变化。如果一个函数被定义为返回一个枚举的实例,并且该枚举添加了一个新值,这也是 ABI 变化。换句话说,即便是微小的更改也可能是 ABI 变化。你需要问的问题是:已经编译的现有代码是否可以在没有更改的情况下继续使用新符号?如果答案是否定的,那么你就有了 ABI 变化,必须定义一个新的符号版本。

在编写实现旧 ABI 的符号时,你必须非常小心,不能仅仅复制现有代码。你必须确保它真的实现了旧的 ABI。

在使用 C++ 时会面临一些特殊挑战。向一个类添加一个新的虚方法可能会导致任何使用该类的函数的 ABI 变化。在这种情况下提供向后兼容的类版本非常棘手,因为没有自然的方法来指定旧版本的虚拟表或 RTTI 信息的名称和版本。

当然,你绝不能删除任何符号。

准确处理所有细节,并验证它们的正确性,需要极大的关注细节。不幸的是,我不知道任何工具可以帮助人们编写正确的版本脚本或验证它们。尽管如此,如果正确实现,结果是好的:现有的可执行文件将继续运行。

13.2 静态链接与动态链接

当然,还有另一种确保现有可执行文件继续运行的方法:静态链接,不使用任何共享库。这将使它们的 ABI 问题仅限于内核接口,通常比库接口显著更小。

静态链接有性能上的权衡。静态链接的程序无法享受与其他同时运行程序共享库的好处。另一方面,静态链接的程序在库中执行时不必支付位置独立代码的性能代价。

升级共享库只能通过动态链接来完成。这种升级可以提供错误修复和更好的性能。此外,动态链接器可以选择适合特定平台的共享库版本,这也有助于性能。

静态链接允许对程序进行更可靠的测试。你只需要担心内核的变化,而不是共享库的变化。

一些人认为动态链接总是更优。我认为双方都有好处,哪个选择最好取决于具体情况。

我已经提到了一些特定于链接器的优化:放松和垃圾回收不需要的段。还有另一类在链接时发生的优化,但实际上与编译器有关。这些优化的通用名称是链接时优化(link time optimization) 或整体程序优化 (whole program optimization)。

一般的想法是,编译器优化过程在链接时运行。在链接时运行的优势在于编译器能够看到整个程序。这允许编译器执行在源文件单独编译时无法完成的优化。最明显的这种优化是跨源文件内联函数。另一个是优化简单函数的调用序列,例如,在寄存器中传递更多参数,或者知道该函数不会破坏所有寄存器;这只能在编译器能够看到函数的所有调用者时进行。经验表明,这些和其他优化可以带来显著的性能提升。

一般来说,这些优化是通过让编译器将其中间表示的版本写入目标文件或某个并行文件中来实现的。中间表示将是源文件的解析版本,并且可能已经应用了一些局部优化。有时目标文件仅包含编译器中间表示,有时它还包含常规的目标代码。在前一种情况下,需要进行链接时间优化,而在后一种情况下,它是可选的。

我知道两种典型的链接时间优化实现方式。

  • 第一种方法是让编译器提供一个预链接器。预链接器检查目标文件,寻找存储的中间表示。当它找到一些时,它会运行链接时间优化过程。
  • 第二种方法是链接器本身在找到中间表示时回调到编译器。这通常是通过某种插件 API 实现的。

虽然这些优化发生在链接时,但它们并不是链接器的组成部分,至少不是按照我定义的那样。当编译器读取存储的中间表示时,无论如何最终都会生成一个目标文件。链接器本身将按照惯例处理该目标文件。这些优化应被视为编译器的一部分。

14.1 Initialization Code

C++ 允许全局变量拥有构造函数和析构函数。全局构造函数必须在主函数开始之前执行,而全局析构函数必须在调用 exit 之后执行。实现这一点需要编译器和链接器的协作。

a.out 目标文件格式如今很少使用,但 GNU a.out 链接器有一个有趣的扩展。在 a.out 中,符号有一个字节的类型字段。这编码了一些调试信息,以及符号被定义的段。a.out 目标文件格式仅支持三个段——文本、数据和 bss。定义了四种符号类型的集合:文本集合、数据集合、bss 集合和绝对集合。允许多次定义集合类型的符号。GNU 链接器不会报多重定义错误,而是会构建一个包含所有符号值的表。该表以一个字(holding the number of entries)开始,并以一个零字结束。在输出文件中,集合符号将被定义为表的起始地址。

对于每个 C++全局构造函数,编译器将生成一个名为__CTOR_LIST__的符号,类型为文本集合。在目标文件中,符号的值将是全局构造函数。链接器将把所有__CTOR_LIST__函数收集到一个表中。编译器提供的启动代码将遍历__CTOR_LIST__ 表并调用每个函数。全局析构函数的处理方式类似,名称为_DTOR_LIST_

无论如何,a.out 就说到这里。在 ELF 中,全局构造函数的处理方式相似,但不使用特殊的符号类型。我将描述 gcc 的做法。定义全局构造函数的目标文件将包括一个.ctors 段。编译器将安排在链接的开始和结束时链接特殊目标文件。链接开始时的目标文件将为.ctors 段定义一个符号;该符号将位于段的起始位置。链接结束时的目标文件将为.ctors 段的结束定义一个符号。编译器的启动代码将在这两个符号之间遍历,调用构造函数。全局析构函数在.dtors 段中以类似方式工作。

ELF 共享库的工作方式类似。当动态链接器加载一个共享库时,如果有 DT_INIT 标签,它将调用该函数。根据惯例,ELF 程序链接器将把其设置为名为_init 的函数(如果存在的话)。同样,DT_FINI 标签在卸载共享库时被调用,程序链接器将其设置为名为_fini 的函数。

正如我之前提到的,还有三个标签:DT_INIT_ARRAY、DT_PREINIT_ARRAY 和 DT_FINI_ARRAY,它们根据 SHT_INIT_ARRAY、 SHT_PREINIT_ARRAY 和 SHT_FINI_ARRAY 段类型进行设置。这是 ELF 中一种更新的方法,不需要依赖特殊的符号名称。

15 Linkers part 15 COMDAT sections

在 C++中,有几个构造体并不明确定义在一个地方。示例包括在头文件中定义的内联函数、虚拟表和类型信息对象。在最终链接的程序中,这些构造体必须只有一个实例(实际上我们可能可以使用多个虚拟表的副本,但其他的必须是独一无二的,因为可以获取它们的地址)。不幸的是,并不一定会有一个单一的目标文件来生成这些构造体。这些类型的构造体有时被描述为具有模糊的链接性。

链接器通过使用 COMDAT 节来实现这些功能(可能还有其他方法,但这是我知道的唯一方法)。COMDAT 节是一种特殊类型的节。每个 COMDAT 节都有一个特殊字符串。当链接器看到多个具有相同特殊字符串的 COMDAT 节时,它只会保留其中一个。

例如,当 C++编译器在头文件中看到定义的内联函数 f1,但编译器无法在所有使用中内联该函数(可能是因为某个地方获取了该函数的地址),编译器会将 f1 发出到与字符串 f1 关联的 COMDAT 节中。当链接器看到 COMDAT 节 f1 时,它会丢弃所有后续的 f1 COMDAT 节。

这显然引发了两个完全不同的内联函数 f1 的可能性,它们定义在不同的头文件中。这将是一个无效的 C++程序,违反了单一定义规则(通常缩写为 ODR)。不幸的是,如果没有任何源文件同时包含这两个头文件,编译器将无法诊断错误。而且,不幸的是,链接器会简单地丢弃重复的 COMDAT 节,而也不会注意到错误。这是一个需要改进的领域(至少在 GNU 工具中;我不知道其他工具是否正确诊断这个错误)。

Microsoft PE 目标文件格式提供了 COMDAT 节。这些节可以被标记,以便在内容不相同的情况下导致重复的 COMDAT 节产生错误。这并不像看起来那样有帮助,因为不同的编译器选项可能导致有效的重复具有不同的内容。与 COMDAT 节关联的字符串存储在符号表中。

在我了解 Microsoft PE 格式之前,我在 GNU ELF 链接器中引入了一种不同类型的 COMDAT 节,遵循 Jason Merrill 的建议。任何名称以“.gnu.linkonce.”开头的节都是 COMDAT 节。相关的字符串就是节的名称。因此,内联函数 f1 将被放置在节“.gnu.linkonce.f1”中。这个简单的实现工作得不错,但有一个缺陷是某些函数需要在多个节中找数据;例如,指令可能在一个节中,而相关的静态数据可能在另一个节中。由于内联函数的不同实例可能以不同的方式编译,链接器无法可靠和一致地丢弃重复的数据(我不知道 Microsoft 链接器如何处理这个问题)。

最近版本的 ELF 引入了节组。这些实现了 ELF 中 COMDAT 的官方认可版本,并避免了“.gnu.linkonce”节的问题。我在早先的博客文章中简要描述了这些功能。一种特殊类型为 SHT_GROUP 的节包含组内节索引的列表。该组作为一个整体被保留或丢弃。与该组关联的字符串在符号表中找到。将字符串放入符号表中使得检索变得比较麻烦,但由于该字符串通常是一个符号的名称,意味着该字符串只需要在目标文件中存储一次;这对于 C++来说是一个小优化,因为符号名称可能非常长。

16 Linkers part 16: C++ Template Instantiation

16.1 C++ Template Instantiation

尽管与连接器本身关系不太大,但在链接时仍然有更多 C++的乐趣。C++程序可以声明模板,并用特定的类型实例化它们。理想情况下,这些特定的实例化在程序中应该只出现一次,而不是每个实例化模板的源文件中各出现一次。有几种方法可以使其正常工作。

对于支持 COMDAT 和模糊链接的目标文件格式,最简单和最可靠的机制是编译器生成源文件所需的所有模板实例化,并将它们放入目标文件中。他们应该标记为 COMDAT,以便链接器可以丢弃除一个副本外的所有副本。这确保了所有模板实例化将在链接时可用,并且可执行文件只有一个副本。这是 gcc 在支持的系统中默认执行的操作。显而易见的缺点是编译所有重复模板实例化所需的时间以及它们在目标文件中占用的空间。这有时被称为 Borland 模型,因为这是 Borland 的 C++编译器所做的。

另一种方法是在编译时不生成任何模板实例化。相反,当链接时,如果我们需要的模板实例化未找到,则调用编译器进行构建。这可以通过运行链接器并查找错误消息或使用链接器插件处理未定义符号错误来完成。这个方法的困难在于找到要编译的源代码以及找到传递给编译器的正确选项。通常,源代码会在编译时放入某种存储库文件中,以便在链接时可用。获得正确编译步骤的复杂性是这个方法不是默认的原因。然而,当它有效时,它可以比重复实例化方法更快。这有时被称为 Cfront 模型。

gcc 还支持显式模板实例化,可以用来精确控制模板的实例化位置。若您能完全控制源代码库,并能在某个中央位置实例化所有所需的模板,此方法将有效。这个方法用于 gcc 的 C++库 libstdc++。

C++定义了一个关键字 export,旨在允许以某种方式导出模板定义,使其可以被编译器读取。gcc 不支持这个关键字。如果它能工作,那么在使用 Cfront 模型时,它可能是一种稍微更可靠的使用存储库的方法。

16.2 Exception Frames

C++和其他语言支持异常。

当一个函数抛出异常而另一个函数捕获异常时,程序需要重置堆栈指针和寄存器,以返回到捕获异常的点。在重置堆栈指针时,程序需要识别在被丢弃的堆栈部分中的所有局部变量,并运行它们的析构函数(如果有的话)。这个过程被称为展开堆栈。

展开堆栈所需的信息通常存储在程序中的表格里。使用支持库代码来读取这些表格并执行必要的操作。我在这里不打算详细描述这些表格。然而,有一种适用于它们的链接器优化。

支持库需要在运行时能够找到异常表,当异常发生时。一种异常可以在一个共享库中抛出并在另一个共享库中捕获,因此找到所有所需的异常表可能不是一件简单的事情。可以采用的一种方法是在程序启动时或共享库加载时注册异常表。注册可以在适当的时间使用全局构造函数机制完成。

然而,这种方法对异常施加了运行时成本,这会导致程序启动时间更长。因此,这并不是理想的选择。链接器可以通过构建可以用来查找异常表的表格来优化这一点。GNU 链接器构建的表格经过排序,以便运行时库能够快速查找。这些表格被放入 PT_GNU_EH_FRAME 段。支持库随后需要一种查找这种类型段的方法。这是通过 GNU 动态链接器提供的 dl_iterate_phdr API 来完成的。

请注意,如果编译器认为链接器会生成 PT_GNU_EH_FRAME 段,那么它将不会生成注册异常表的启动代码。因此,链接器必须确保创建这个段。

由于 GNU 链接器需要查看异常表以生成 PT_GNU_EH_FRAME 段,它还会通过丢弃重复的异常表信息来进行优化。

我知道这一节的细节相对较少。我希望整体思路是清晰的。

17 Linkers part 17: Warning Symbols

GNU 链接器支持对 ELF 的一种奇怪扩展,用于在链接时发出符号引用的警告。这最初是为 a.out 实现的,使用了一种特殊的符号类型。对于 ELF,我使用一种特殊的节名称实现了它。

如果你创建一个名为 .gnu.warning.SYMBOL 的节,那么当链接器看到对 SYMBOL 的未定义引用时,它将发出警告。警告是通过在目标文件中看到具有正确名称的未定义符号来触发的。与未定义符号的警告不同,它并不是通过看到重定位条目来触发的。警告的文本简单地是 .gnu.warning.SYMBOL 节的内容。

GNU C 库利用这个特性来警告对像 gets 这样的符号的引用,标准要求这些符号,但通常被认为是不安全的。这是通过在定义 gets 的同一个目标文件中创建一个名为 .gnu.warning.gets 的节来实现的。

GNU 链接器还支持另一种类型的警告,触发条件是名为 .gnu.warning(没有符号名称)的节。如果链接中包含具有该名称节的目标文件,链接器将发出警告。同样,警告的文本简单地是 .gnu.warning 节的内容。我不知道是否有人实际使用这个特性。

18 Linkers part 18: Incremental Linking

程序员经常只会修改单个源文件并重新编译和链接应用程序。标准链接器需要读取所有输入对象和库,以便根据更改重新生成可执行文件。对于一个大型应用程序,这是一项繁重的工作。如果只有一个输入对象文件发生了变化,那么所需的工作量就多于实际需要做的工作。一个解决方案是使用增量链接器。增量链接器对现有的可执行文件或共享库进行增量更改,而不是从头开始重建它们。

我实际上从未编写或处理过增量链接器,但总体思路还是相当简单的。当链接器写入输出文件时,它必须附加额外的信息。

  • 链接器必须创建对象文件与输出文件区域的映射,以便增量链接时知道在替换对象文件时需要移除哪些内容。

  • 链接器必须保留所有输入对象的重定位信息,这些信息引用了其他对象中定义的符号,以便在符号发生变化时可以重新处理它们。链接器应根据符号存储重定位信息,以便快速找到相关的重定位。

  • 链接器应在文本段和数据段中留出额外的空间,以允许对象文件在有限范围内增长,而不需要重写整个可执行文件。它必须保留这些额外空间的位置图,因为在增量链接过程中,这些空间可能会随着时间的推移而移动。

  • 链接器应在输出文件中保留对象文件时间戳的列表,以便能够快速确定哪些对象发生了变化。

通过这些信息,链接器可以识别出自上次输出文件链接以来发生变化的目标文件,并在现有输出文件中替换它们。当目标文件发生变化时,链接器可以识别所有引用目标文件中定义的符号的重定位,并重新处理它们。

当目标文件过大而无法适应文本或数据段中的可用空间时,链接器可以选择在不同的地址创建额外的文本或数据段。这需要小心处理,以确保新代码不会与堆发生冲突,具体取决于本地 malloc 实现的工作方式。或者,增量链接器可以回退到进行完整链接,并再次分配更多空间。

增量链接可以极大地加快编辑/编译/调试周期。不幸的是,绝大多数常见链接器并没有实现这一功能。虽然增量链接并不等同于最终链接,特别是某些链接器优化在增量处理时实施起来非常困难。增量链接实际上只适合在开发周期中使用,这也是链接器速度最重要的时期。

19 Linkers part 19

19.1 __start and __stop Symbols

关于另一个 GNU 链接器扩展的简要说明。

如果链接器在输出文件中看到一个可以成为 C 变量名的部分(该名称仅包含字母数字字符或下划线), 链接器将自动定义标记该部分开始和结束的符号。请注意,大多数部分名称并不适用这一点,因为根据约定,大多数部分名称以句点开头。但部分的名称可以是任何字符串;它不需要以句点开头。当部分名称为 NAME 时,GNU 链接器将分别将符号 __start_NAME__stop_NAME 定义为该部分开始和结束的地址。

这在收集几个不同目标文件中的一些信息时很方便,然后在代码中引用它。 例如,GNU C 库使用此方法来保持一个可能被调用以释放内存的函数列表。 __start__stop 符号用于遍历该列表。

在 C 代码中,这些符号应声明为类似 extern char __start_NAME[] 的形式。 对于外部数组,符号的值和变量的值是相同的。

19.2 Byte Swapping

我正在开发的新链接器,gold,是用 C++编写的。其一个吸引人的特点是使用模板特化来实现高效的字节交换。任何可以用于交叉编译器的链接器在写出数据时都需要能够进行字节交换,以便在小端系统上运行时为大端系统生成代码,反之亦然。GNU 链接器总是按字节一次性将数据存储到内存中,而这对于本地链接器来说是不必要的。几年前的测量数据显示,这大约占用了链接器 CPU 时间的 5%。由于本地链接器是最常见的情况,因此值得避免这种损失。

在 C++中,可以使用模板和模板特化来实现这一点。其思路是编写一个输出数据的模板。然后提供两个模板特化,一个用于相同字节序的链接器,一个用于相反字节序的链接器。然后在编译时选择使用哪个。代码示例如下;为简单起见,我仅展示 16 位的情况。

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// Endian simply indicates whether the host is big endian or not.

struct Endian
{
public:
    // Used for template specializations.
    static const bool host_big_endian = __BYTE_ORDER == __BIG_ENDIAN;
};

// Valtype_base is a template based on size (8, 16, 32, 64) which
// defines the type Valtype as the unsigned integer of the specified
// size.

template
struct Valtype_base;

template<>
struct Valtype_base<16>
{
    typedef uint16_t Valtype;
};

// Convert_endian is a template based on size and on whether the host
// and target have the same endianness. It defines the type Valtype
// as Valtype_base does, and also defines a function convert_host
// which takes an argument of type Valtype and returns the same value,
// but swapped if the host and target have different endianness.

template
struct Convert_endian;

template
struct Convert_endian
{
    typedef typename Valtype_base::Valtype Valtype;

    static inline Valtype
    convert_host(Valtype v)
    { return v; }
};

template<>
struct Convert_endian<16, false>
{
    typedef Valtype_base<16>::Valtype Valtype;

    static inline Valtype
    convert_host(Valtype v)
    { return bswap_16(v); }
};

// Convert is a template based on size and on whether the target is
// big endian. It defines Valtype and convert_host like
// Convert_endian. That is, it is just like Convert_endian except in
// the meaning of the second template parameter.

template
struct Convert
{
    typedef typename Valtype_base::Valtype Valtype;

    static inline Valtype
    convert_host(Valtype v)
    {
        return Convert_endian
        ::convert_host(v);
    }
};

// Swap is a template based on size and on whether the target is big
// endian. It defines the type Valtype and the functions readval and
// writeval. The functions read and write values of the appropriate
// size out of buffers, swapping them if necessary.

template
struct Swap
{
    typedef typename Valtype_base::Valtype Valtype;

    static inline Valtype
    readval(const Valtype* wv)
    { return Convert::convert_host(*wv); }

    static inline void
    writeval(Valtype* wv, Valtype v)
    { *wv = Convert::convert_host(v); }
};

现在,例如,链接器使用 Swap<16,true>::readval 读取一个 16 位大端值。这是可行的,因为链接器总是知道需要交换多少数据,并且它总是知道它是在读取大端还是小端数据。

20 Linkers part 20

我将以关于我正在开发的新链接器 gold 的简短更新结束这个系列。当前(2007 年 9 月 25 日)它可以创建可执行文件。它无法创建共享库或可重定位对象。它对链接脚本的支持非常有限——足以在 GNU/Linux 系统上读取/usr/lib/libc.so。到目前为止,它没有任何有趣的新特性。它仅支持 x86。至今为止,重点完全放在速度上。它是为了多线程而编写的,但线程支持尚未接入。

举个例子,当链接一个 900M 的 C++可执行文件时,GNU 链接器(在基于 Ubuntu 的系统上的版本 2.16.91 20060118)花费了 700 秒用户时间、24 秒系统时间和 16 分钟墙钟时间。而 gold 只花费了 7 秒用户时间、3秒系统时间和 30 秒墙钟时间。因此,虽然我不能保证在添加所有功能后它依然保持这样的速度,但目前它的表现相当不错。

我是 gold 的主要开发人员,但我不是唯一一个在参与此项目的人。还有一些其他人也在进行改进。

我们的目标是将 gold 作为一个免费程序发布,理想情况下是作为 GNU binutils 的一部分。不过,我希望在这样做之前它能更加接近功能完整。它至少需要支持-shared 和-r。我怀疑 gold 会支持 GNU 链接器的所有功能。我怀疑它会支持完整的 GNU 链接脚本语言,尽管我确实计划支持足够的内容以链接 Linux 内核。

gold 的未来计划,在它实际工作后,包括增量链接和更大规模的速度提升。