静态链接时符号的查找流程

静态链接将多个目标文件组合为一个可执行文件。每个目标文件会定义和引用若干符号，链接器需要收集各个目标文件中定义和引用的符号，并建立符号之间的联系。符号分布在多个目标文件中，不同目标文件之间或许还存在交叉引用关系，那么链接器是按照什么策略去查找符号的呢？

背景

目标文件中，存在已定义和未定义的符号。已定义的符号可被其他目标文件引用，未定义的符号则引用其他目标文件中的符号。下面是一个简单的 C 程序，其中定义了多个符号：

static int a = 1;

int bar(int);

int foo() {
    return a;
}

int main(int argc, char *argv[]) {
    bar(foo());
}

将其编译为目标文件后，观察其中的符号：

$ gcc -c main.c 
$ nm main.o
0000000000000000 d a
                 U bar
0000000000000000 T foo
000000000000000c T main

nm 命令可用于查询一个目标文件中的符号信息，其中第二列输出位符号的类型，其含义如下：

• d: Initialized data (bbs), local
• U: Undefined symbol
• T: Text symbol, global

这里 d 指静态符号，只能被目标文件内部访问，而 U 和 T 是全局符号，U 表示未定义符号，T 表示已定义的符号。

静态链接的流程

使用 GCC 来执行链接的命令如下：

$ gcc main.o bar.o -labc -lbaz -lbar

GCC 提供给链接器的是一组目标文件 (main.o, bar.o) 和一些静态库 (libabc.a, libbaz.a libbar.a)。链接器会从左到右逐个处理，并尝试将必要的目标文件包含到可执行文件中。这个过程是围绕目标文件中的符号展开的。

链接器会维护两个列表：

• 已定义符号列表
• 未定义符号列表

链接器从左到右处理目标文件和静态库：

当遇到目标文件时：

• 从全局未定义符号中去除目标文件中已定义符号
• 将目标文件中已定义符号加入全局已定义符号列表中
  • 如果目标文件中已定义符号在全局已定义符号列表中已经存储，则会报重复定义的错误
• 将目标文件中未定义符号加入全局未定义符号列表中
• 将此目标文件加入到最终可执行文件要包含的目标文件列表中

当遇到静态库时：

• 遍历静态库中所有的目标文件，对于每个文件执行如下流程：
  • 如果该目标文件中的已定义符号存在于全局未定义符号列表中，则按前面处理目标文件的流程处理
• 如果上述流程中有任何目标文件被最终可执行文件包含，则再次遍历整个静态库，否则则处理完毕
  • 再次处理的原因：同一个静态库中，后面处理的目标文件可能引用了前面的目标文件

链接完成后，全局未定义符号表应该为空，否则就存在未定义的错误。

以上就是静态链接中符号查找的流程。

模拟静态链接流程

上面的文字描述可能不够直观，这里不妨使用 Python 来模拟一下静态链接的流程：

首先定义目标文件和静态库：

from typing import List, Set

class Object:
    def __init__(self, name,
                 defined_symbols: Set[str],
                 undefined_symbols: Set[str]):
        self.name = name
        self.defined_symbols = defined_symbols
        self.undefined_symbols = undefined_symbols
    
    def __repr__(self) -> str:
        return self.name

class StaticLibrary:
    def __init__(self,  objects: List[Object]):
        self.objects = objects

目标文件中包含已定义和未定义的符号，静态库则包含一组目标文件。

class Linker:
    def __init__(self):
        self.defined_symbols = set()
        self.undefined_symbols = set()
        self.linked_objects = []
    
    def link(self, items: List[Union[Object, StaticLibrary]]):
        for item in items:
            if isinstance(item, Object):
                self.link_object(item)
            else:
                self.link_static_library(item)
        
        if len(linker.undefined_symbols) > 0:
            raise RuntimeError("undefined symbols: " + ", ".join(linker.undefined_symbols))

Linker 中包含已定义和未定义的符号的集合，还有需要被包含到可执行文件中的目标文件。

执行 link 的时候会传入一些目标文件或静态库，链接器会顺序处理每个元素，根据类型不同分别执行对目标文件的链接和静态库的链接。链接完成后，如果存在未定义的符号，则链接会失败。

目标文件的链接流程如下：

def link_object(self, object: Object):
    # 链接目标文件时，首先判断是否有重复的符号，如果有则报错
    deplicated_symbels = self.defined_symbols & object.defined_symbols
    if len(deplicated_symbels) > 0:
        raise RuntimeError("deplicated symbels: " + ", ".join(deplicated_symbels))

    # 将目标文件中已定义和未定义符号加入全局列表
    self.defined_symbols |= object.defined_symbols
    self.undefined_symbols |= object.undefined_symbols
    # 消除全局未定义符号
    self.undefined_symbols -= self.defined_symbols
    
    # 将此目标文件加入已被链接目标文件列表中
    self.linked_objects.append(object)

静态库的链接流程如下：

def link_static_library(self, library: StaticLibrary):
    while True:
        has_object_been_linked = False
        for object in library.objects:
            # 如果当前目标文件能消除全局未定义符号，则链接此目标文件
            if len(object.defined_symbols & self.undefined_symbols) > 0:
                self.link_object(object)
                has_object_been_linked = True
        # 如果没有任何目标文件被链接，则跳出
        if has_object_been_linked:
            break

可以使用如下代码来模拟链接中符号查找过程：

bar = Object("bar.o", {"bar"}, {"foo"})           # 定义符号 bar, 未定义符号 foo
main = Object("main.o", {"foo", "main"}, {"bar"}) # 定义符号 foo、main, 未定义符号 bar

linker = Linker()
linker.link([bar, main])
print(linker.linked_objects)
# [bar.o, main.o]

链接过程未出现问题，最终 bar.o 和 main.o 会用于构造可执行文件。

下面模拟含重复符号的情况，我们在 bar.o 中也定义一个 foo 符号：

bar = Object("bar.o", {"bar", "foo"}, set())           # 定义符号 bar、foo
main = Object("main.o", {"foo", "main"}, {"bar"}) # 定义符号 foo、main, 未定义符号 bar

linker = Linker()
linker.link([bar, main])
print(linker.linked_objects)
# RuntimeError: deplicated symbels: foo

运行后，会报符号重复定义的错误。

下面模拟符号缺失的错误，将 bar.o 中的符号 bar 修改为 bar123：

bar = Object("bar.o", {"bar123"}, set())           # 定义符号 bar123
main = Object("main.o", {"foo", "main"}, {"bar"}) # 定义符号 foo、main, 未定义符号 bar

linker = Linker()
linker.link([bar, main])
print(linker.linked_objects)
# RuntimeError: undefined symbols: bar

运行后，会报符号未定义的错误。

常见问题

下面列举一些和符号查找有关的常见的问题，这能更直观地了解静态库符号的查找流程，有助于巩固前面所描述的原理。

引用到非预期的符号

下面的例子中用到了两个静态库，这两个静态库中都有一个 foo 函数，并且被各静态库中的其他函数调用，关系如下：

上图中，静态库 liba.a 中的 a 函数希望调用 liba.a 中的 foo 函数。同样地，函数 b 调用 libb.a 中的 foo 函数。但是编译链接后，我发现仅仅只有一个 foo 函数被使用，而两个 foo 的功能有差异，这导致程序出错了。

可以使用前面实现的 Python 代码来模拟一下这个过程：

liba = StaticLibrary([
    Object("a::a.o", {"a"}, {"foo"}),
    Object("a::foo.o", {"foo"}, set()),
])

libb = StaticLibrary([
    Object("b::a.o", {"b"}, {"foo"}),
    Object("b::foo.o", {"foo"}, set()),
])

main = Object("main.o", {"main"}, {"a", "b"})

linker = Linker()
linker.link([main, liba, libb])
print(linker.linked_objects)
# [main.o, a::a.o, a::foo.o, b::a.o]

如果理解了上述静态链接流程，那么问题的原因就很容易理解了。最终实际上只有 liba.a 中的 foo.o 被包含到可执行文件中，因为 liba.a::foo.o 中已经定义了符号 foo，后续在处理 libb.a 中的 foo.o 时，会发现 foo.o 中定义的符号其实全部都已经定义了，因此会跳过目标文件 libb.a::foo.o 。在处理 libb.a::b.o 时，符号 foo 会引用到已定义的符号 liba.a::foo.o::foo。

如果在链接时把静态库的顺序调整一下，就会得到另外一种情况：

linker = Linker()
linker.link([main, libb, liba])  # libb 在前
print(linker.linked_objects)
# [main.o, b::a.o, b::foo.o, a::a.o]

但无论如何这都不是预期中的结果。对于上面这种场景，只能修改符号的名称，这样才能避免引用到非预期的符号。

另外在开发中也应该尽早地发现这种符号重复定义的问题，因为这种情况下，尽管链接成功了，但因为链接到了错误的符号，在运行时依然会出问题（除非两个函数完全一样）。

$ gcc main.o -Wl,--whole-archive liba.a -Wl,--no-whole-archive -Wl,--whole-archive libb.a -Wl,--no-whole-archive
gcc main.o -Wl,--whole-archive liba.a -Wl,--no-whole-archive -Wl,--whole-archive libb.a -Wl,--no-whole-archive
******/bin/ld: libb.a(b2.o): in function `foo':
b2.c:(.text+0x0): multiple definition of `foo'; liba.a(a2.o):a2.c:(.text+0x0): first defined here
collect2: error: ld returned 1 exit status
make: *** [makefile:11: main] Error 1

使用链接选项 whole-archive 告诉链接器把静态库中所有的目标文件都包含到可执行文件中（即使不会被使用到），这样就能在开发阶段发现符号重定义的问题。

符号重定义了为什么不报错

前面的例子中，两个 foo.o 中包含了相同的符号，为什么在链接的时候不会报错呢？不是静态链接时不允许有重复定义的符号吗？只有当一个目标文件能够消除全局未定义的符号时，它才会被链接。前面的案例中，其中一个 foo.o 文件会先被链接，而后处理的一个 foo.o 文件因为不再能消除全局未定义符号，因此它会被跳过，而重复符号的检查发生在对目标文件执行链接的时候。

下面的例子中，我们给两个 foo.o 中分别加入 foo1 和 foo2 两个符号，然后在 main.o 使用这些符号，这就能保证两个 foo.o 都能消除全局未定义符号，它们会被链接到可执行文件中，这时就会出现重复定义的错误。

liba = StaticLibrary([
    Object("a::a.o", {"a"}, {"foo"}),
    Object("a::foo.o", {"foo", "foo1"}, set()),
])

libb = StaticLibrary([
    Object("b::a.o", {"b"}, {"foo"}),
    Object("b::foo.o", {"foo", "foo2"}, set()),
])

main = Object("main.o", {"main"}, {"a", "b", "foo1", "foo2"})

linker = Linker()
linker.link([main, liba, libb])
print(linker.linked_objects)
# RuntimeError: deplicated symbels: foo

符号明明定义了，为什么报未定义错误

在命令行上传入的目标文件和静态库的顺序很重要，通常做法是将静态库放置于目标文件之后。如果静态库之间存在依赖关系，则需要小心安排它们的位置。

假如 main.c 调用了 liba.a 和 libb.a 中的函数，而 liba.a 和 libb.a 调用了 libc.a 中的函数，则需要把 libc.a 放置在最后：

$ gcc main.o liba.a libb.a libc.a

有时候静态库之间存在复杂的引用关系，这时候有可能需要在命令行上多次重复同一个静态库。看下面的例子：

liba = StaticLibrary([
    Object("a::a1.o", {"a1"}, set()),
    Object("a::a1.o", {"a2"}, set("b2")),
])

libb = StaticLibrary([
    Object("b::b1.o", {"b1"}, {"a2"}),
    Object("b::b2.o", {"b2"}, {"a1"}),
])

main = Object("main.o", {"main"}, {"a1", "b1"})

如果按照如下命令来链接就会出错：

$ gcc main.o liba.a libb.a

因为链接是从左到右依次执行的，下面是处理流程：

• 处理 main.o，发现当前未定义符号集合为 a1、b1
• 处理 liba.a 时，发现 a1.o 中包含全局未定义符号 a1，因此将 a1.o 包含到可执行文件中
• 处理 libb.a 时，发现 b1.o 中包含全局未定义符号 b1，因此将 b1.o 包含到可执行文件中，同时将 b1 引用的 a2 加入全局未定义符号列表中

处理完毕后，会发现符号 a2 未定义。

linker = Linker()
linker.link([main, liba, libb])
print(linker.linked_objects)
# RuntimeError: undefined symbols: a2

为了能找到符号 a2，需要再次提供 liba.a：

$ gcc main.o liba.a libb.a liba.a

因为 a2 引用了 b2，此时依然会出错：

linker.link([main, liba, libb, liba])
# RuntimeError: undefined symbols: b2

你也许想到了，最终的命令如下：

$ gcc main.o liba.a libb.a liba.a libb.a

当模块之间引用关系比较复杂的时候，通过重复提供静态库来解决有些复杂，此时可以使用链接器的 --start-group archives --end-group 选项来处理：

$ gcc main.o -Wl,--start-group liba.a libb.a -Wl,--end-group

放置在 --start-group 和 --end-group 之间的静态库会被多次查找，直到无新的未定义符号出现，这能够轻松解决静态库符号相互依赖的问题，无需多次重复静态库。

下面是官网文档中的介绍：

-( archives -) or —start-group archives —end-group

The archives should be a list of archive files. They may be either explicit file names, or -l options.

The specified archives are searched repeatedly until no new undefined references are created. Normally, an archive is searched only once in the order that it is specified on the command line. If a symbol in that archive is needed to resolve an undefined symbol referred to by an object in an archive that appears later on the command line, the linker would not be able to resolve that reference. By grouping the archives, they all be searched repeatedly until all possible references are resolved.

Using this option has a significant performance cost. It is best to use it only when there are unavoidable circular references between two or more archives.

总结

本文描述了静态链接中符号的查找流程，这是静态链接的一个核心。链接器处理目标文件和静态库逐渐消除未定义符号，以此来收集最终构成可执行文件的目标文件。如果你清楚了符号查找的流程，常见的静态链接错误都能快速解决。