前言

静态链接（static linking）是程序构建中的一个重要环节，它负责分析 compiler 等模块输出的.o、.a、.dylib、经过对 symbol 的解析、重定向、聚合，组装出 executable 供运行时 loader 和 dynamic linker 来执行，有着承上启下的作用。

对于 iOS 工程而言，目前负责静态链接的主要是 ld64。苹果对 ld64 加持了一些功能，以适配 iOS 项目的构建，比如：

• 现在在 Xcode 中即使不主动管理依赖的系统动态库（如 UIKit），你的工程也可以正常链接成功
• 提供“强制加载静态库中 ObjC class 和 category” 的开关（默认开启），让 ObjC 的信息在输出中完整不丢失

大量特性的实现也在静态链接这一步完成，如：

• 基于二进制重排的启动速度优化，利用 ld64 的-order_file让 linker 按照指定顺序生成 Mach-O
• 用-exported_symbols_list优化构建产物中 export info 占用的空间，减少包大小

借助组件二进制化、自定义构建系统等优化手段，当前大型工程中增量构建的效率已经显著提升，但静态链接作为每次必须执行的环节依然“贡献”了大部分耗时。了解 ld64 的工作原理能辅助我们加深对构建过程的理解、寻找提升链接速度的方法、以及探索更多品质和体验优化的可能性。

目录

• 历史背景
• 概念铺垫
• ld64 命令参数
• ld64 执行流程
• ld64 on iOS
• 其他

一、历史背景

• GNU ld：GNU ld，或者说 GNU linker，是 GNU 项目对 Unix ld 命令的实现。它是 GNU binary utils 的一部分，有两个版本：传统的基于BFD& 只支持 ELF 的 gold。（gold 由 Google 团队研发，2008 年被纳入 GNU binary utils。目前随着 Google 重心放到 llvm 的 lld 上，gold 几乎不怎么维护了）。ld 的命名据说是来自LoaDer 、Link eDitor。
• ld64：ld64 是苹果为 Darwin 系统重新设计的 ld。和 ld 的最大区别在于，ld64 是 atom-based 而不是 section-based（关于 atom 的介绍后面会展开）。在 macOS 上执行 ld（/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ld）默认就是 ld64。系统和 Xcode 自带的版本可以通过 ld -version_details查询，如 650.9。苹果在这里 https://opensource.apple.com/tarballs/ld64/ 开放了 ld64 的源码，但更新不那么及时，始终落后于正式版（如 2021.8 为止开源最新是 609 版本，Xcode 12.5.1 是 650.9） 。zld 等基于 ld64 的项目都是 fork 自开源版的 ld64。

二、概念铺垫

在介绍 ld64 的执行流程之前，需要先了解几个概念。

2.1 输入 — .o、.a、.dylib

• Object File (.o)
• 由 compiler 生成，包含元数据（header、LoadCommand 等）、segments & sections（代码、数据 等）、symbol table & relocation entries。
• object file 之间可能相互依赖（如 A 引用了 B 定义的函数），static linker 做的事情本质上就是把这些信息关联起来输出成一个总的有效的 Mach-O 。

• 静态库 (.a)
• 可以视为.o的集合，让工程代码能模块化地被组织和复用。
• 其头部还存储了 symbol name -> .ooffset 的映射表，便于 link 时快速查询某个 symbol 的归属。
• 一个静态库可能包含多个架构（universal / fat Mach-O），static linker 在处理时会按需选择目标架构。可以通过 lipo等工具查看其架构信息。

• 动态库 (.dylib、.tbd)
• 不同于静态库，动态库由 dyld 在运行时经过 rebase、binding 等过程后加载。static linker 在 link 时仅在处理 undefined symbol 时会尝试从输入的动态库列表中查询每个动态库 export 的 symbol。
• iOS 工程中使用的大部分是系统动态库（UIKit 等），工程也可以以 framework 等形式提供自己的动态库（需要指定对 rpath 以让自定义动态库能被 dyld 正常加载）
• .tbd (text-based dylib stub) 是苹果在 Xcode 7 后引入的一种描述 dylib 的文件格式，包含支持的架构、导出哪些 symbol 等信息。通过解析 .tbdld64 可以快速地知道该 dylib 提供了哪些 symbol 可被用于链接 & 有哪些其他动态库依赖，而不用去解析整个解析一遍 dylib。目前大多数系统的 dylib 都采用这种方式。
• 如 Foundation：

--- !tapi-tbd
tbd-version:     4
targets:         [ i386-ios-simulator, x86_64-ios-simulator, arm64-ios-simulator ]
uuids:
  - target:          i386-ios-simulator
    value:           A4A5325F-E813-3493-BAC8-76379097756A
  - target:          x86_64-ios-simulator
    value:           C2A18288-4AA2-3189-A1C6-5963E370DE4C
  - target:          arm64-ios-simulator
    value:           81DE1BE5-83FA-310A-9FB3-CF39C14CA977
install-name:    '/System/Library/Frameworks/Foundation.framework/Foundation'
current-version: 1775.118.101
compatibility-version: 300
reexported-libraries:
  - targets:         [ i386-ios-simulator, x86_64-ios-simulator, arm64-ios-simulator ]
    libraries:       [ '/System/Library/Frameworks/CoreFoundation.framework/CoreFoundation', 
                       '/usr/lib/libobjc.A.dylib' ]
exports:
  - targets:         [ arm64-ios-simulator, x86_64-ios-simulator, i386-ios-simulator ]
    symbols:         [ '$ld$hide$os10.0$_OBJC_CLASS_$_NSURLSessionStreamTask', '$ld$hide$os10.0$_OBJC_CLASS_$_NSURLSessionTaskMetrics', 
                        ....
                       _NSLog, _NSLogPageSize, _NSLogv, _NSMachErrorDomain, _NSMallocZone, 
                       ....]

2.2 Symbol & Symbol Table

对 static linker 来说，symbol 是 Mach-O 提供的、link 时需要参考的一个个基本元素。

Mach-O 有一块专门的区域用于存储所有的 symbol，即 symbol table。

global function、global variable、class 等都会作为一条条 entry 被放入 symbol table 中。

Symbol 包含以下属性：

• 名称：具体生成规则由 compiler 决定。如 C variable_someGlolbalVar、C function _someGlobalFunction、 ObjC class __OBJC_CLASS_$_SomeClass、 ObjC method -[SomeClass foo]等。不同的 compiler 有不同的 name mangling 策略。
• 是“定义”还是“引用”：对应函数、变量的“定义”和“引用”。
• visibility：如果是“定义”，还有 visibility 的概念来控制对其他文件的可见性（具体说明见后文「visibility」）、
• strong / weak：如果是“定义”，还有 strong / weak 的概念来控制多个“定义” 存在时的合并策略（具体说明见后文「strong / weak definition」。

Mach-O symbol table entry 具体的数据结构可以参考文档（https://github.com/aidansteele/osx-abi-macho-file-format-reference#nlist_64）或源码（https://opensource.apple.com/source/xnu/xnu-4570.71.2/EXTERNAL_HEADERS/mach-o/nlist.h.auto.html）

2.3 Visibility

Mach-O 中将 symbol 分为三组：

• global / defined external symbol ：外部可用的 symbol 定义
• local symbol：该文件定义和引用的 symbol，仅该文件可用（比如被static标记）
• undefined external symbol：依赖外部的 symbol 引用

可以通过查看该 Mach-O LoadCommand 中的LC_DYSYMTAB来获取三组 symbol 的偏移和大小

visibility 决定了 symbol definition 在 link 时对其他文件是否可见。上面说的 local symbol 对外不可见，global symbol 对外可见。

global symbol 里又分为两类：normal & private external。如果是 private external（对应 Mach-O 中 N_PEXT字段） ，static linker 会在输出中把该 symbol 转为 local symbol。可以理解为该 symbol definition 只在这一次 link 过程中对外可见，后续 link 的产物如果要被二次 link，就对外不可见了（体现了 private 的性质）

一个 symbol 是否是 「private external」可以在源码和编译期用__attribute__((visibility("xxx")))来标识，可选值为default（normal）、hidden（private external）

• 不指定__attribute__((visibility("xxx")))的，默认为default
• -fvisibility可以修改默认 visibility (gcc、clang 都支持)
• 指定__attribute__((visibility("xxx")))的，visibility 为 xxx

举例：

// test.c

__attribute__((visibility("default"))) int i1Default = 101;
__attribute__((visibility("hidden"))) int i1Hidden = 102;
int i1Normal = 103;

不指定 -fvisibility：

-fvisibility=hidden：

2.4 Strong / Weak definition

symbol definition 中还有 strong / weak 之分：当 static linker 发现多个 name 相同的 symbol definition 时，会根据 strong/weak 类型执行以下合并策略：

1. 有多个 strong => 非法输入，abort
2. 有且仅有一个 strong => 取该 strong
3. 有多个 weak，没有 strong => 取第一个 weak

symbol definition 默认情况基本都是 strong，可以在源码中通过__attribute__((weak))、#pragma weak标记 weak 属性，看一个例子：

// main.c

void __attribute__((weak)) foo() {
  printf("weak foo called");
}

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

// strong_foo.c
void foo() {
  printf("strong foo called");
}

生成的main.o中该函数对应的 symbol table entry 被标记为了N_WEAK_DEF，static linker 据此来区分 strong / weak：

执行后输出：

strong foo called

要注意的是，分析最终输出使用了哪个 symbol definition 需要结合实际情况。比如某个 strong symbol 封装在静态库中，始终没有被 static linker 加载，而同名的 weak symbol 已经被加载了，上述（2）的策略就应当变成（3）了。（关于静态库中 symbol 的加载机制见后文）

2.5 Tentative definitions / Commons

symbol definition 还可能是 tentative definition（或者叫 common definition）。这个其实也很常见，比如：

int i;

这样一个未初始化的全局变量就是一个 tentative definition。

更官方一点的定义是：

A declaration of an identifier for an object that has file scope without an initializer, and without a storage-class specifier or with the storage-class specifier static

说的比较绕不要被带进去了，可以先简单理解 tentative definition 为「未初始化的全局变量定义」。结合更多的例子来理解：

int i1 = 1; // regular definition，global symbol
static int i2 = 2; // regular definition，local symbol
extern int i3 = 3; // regular definition，global symbol
int i4; // tentative definition, global symbol
static int i5; // tentative definition, local symbol

int i1; // valid tentative definition, refers to 第 1 行
int i2; // invalid tentative definition，visibility 和第 2 行的 static 冲突
int i3; // valid tentative definition, refers to 第 3 行
int i4; // valid tentative definition, refers to 第 4 行
int i5; // invalid tentative definition，visibility 和第 5 行的 static 冲突

tentative definition 在 Mach-O 中属于 __DATA,__common这个 section。

2.6 Relocation (Entries)

compiler 无法在编译期确定所有 symbol 的地址（如对外部函数的调用），因此会在 Mach-O 对应的位置“留空”、并生成一条对应的 Relocation Entry。static linker 在链接期通过 Relocation Entry 知晓每个 section 中哪些位置需要被 relocate、如何 relocate。

Load Command 中的 LC_SEGMENT_64描述了各个 section 对应的 Relocation Entries 的数量、偏移量：

Mach-O 中用relocation_info 表示一条 Relocation Entry：

• r_address：从该 section 头开始偏移多少位置的内容需要 relocate
• r_extern &r_symbolnum
• r_extern为 1 表示从 symbol table 的第 r_symbolnum个 symbol 读取信息
• r_extern 为 0 表示从第 r_symbolnum个 section 读取信息
• r_type：relocation 的类型，如X86_64_RELOC_BRANCH表示 relocate 的是CALL/JMP指令的内容

字段明细可参考文档 https://github.com/aidansteele/osx-abi-macho-file-format-reference#relocation_info。

2.7 ld64 — Atom & Fixup

ld64 是一种 atom-based linker，atom 是其执行处理的基本单元。atom 可以用来表示 symbol，也可以用来表示其他的信息，如 SectionBoundaryAtom。ld64 在解析时会把 input files 抽象成各种 atoms，交由 Resolver 统一处理。

相比 section-based linker ，atom-based linker 把处理对象视为一个 atom graph，更细的粒度方便了各种图算法的应用，也能更直接地实现各种特性。

Atom 有以下属性：

• name，对应上面 Symbol 的 name
• content
• 函数的 content 是其实现的代码指令
• 全局变量的 content 是其初始值
• scope，对应上面 Symbol 的 visibility
• definition kind，有四种，通过 Mach-O Symbol Table Entry 的N_TYPE字段得来
• regular：大多数 atom 是这种类型
• absolute：对应N_ABS，ld64 不会修改它的值
• tentative：N_UNDF，对应上面 Symbol 的 tentative definition
• proxy：ld64 解析阶段如果发现某个 symbol 由动态库提供，会创建一个 proxy atom 占位

一个 atom 旗下可能有一组 fixup，fixup 顾名思义是用于表示在 link 时如何校正 atom content 的一种数据结构。object file 的 Relocation Entries 提供了初始的 fixup 信息，ld64 在执行过程中也可能为 atom 生成额外的 fixup。

fixup 描述了 atom 之间的依赖关系，是 atom graph 中的「边」，dead code stripping 就需要这些依赖关系来判断哪些 atom 不被需要、可以移除。

一个 fixup 包含以下属性：

• kind：fixup 的类型，总共有几十种，如kindStoreX86PCRel32
• offset：对应 Relocation 的 offset
• addend：对应 Relocation 的 addend
• target atom：指向的 atom
• binding type：binding 策略（by-name、by-content、direct、indirect）

看一个简单的例子：

// Foo.h
extern const int someGlobalVar;

int someGlobalFunction(void);


// Foo.m
const int someGlobalVar = 100;

int someGlobalFunction() {
  return 123;
}


// main.m
#import "Foo.h"

int main(int argc, char * argv[]) {
  int i = someGlobalVar;
  someGlobalFunction();
}

上面的代码中 main.m调用了Foo.h定义的全局变量someGlobalVar和函数 someGlobalFunction，compiler 生成的main.o和 Foo.o 以下 symbol：

link 时 ld64 会将其转换成如下的 atom graph：

其中节点信息（atom）由main.o 和 Foo.o的 symbol table 提供，边信息（fixup）由main.o 的 relocation entries 提供。

如果涉及 ObjC，引用关系会更复杂一些，后文「-ObjC的由来」一节会详细展开。

2.8 ld64 — Symbol Table

ld64 内部维护了一个 SymbolTable对象，里面包含了所有处理过的 symbol，并提供了各种快速查询的接口。

往SymbolTable里增加 atom 时会触发合并操作，主要分为两种

1. by-name：name 相同的 atom 可以合并为一个，如前面提到的 Strong / Weak & Tentative Definition
2. by-content：content 相同的 atom 可以合并为一个，如 string constant

SymbolTable核心的数据结构是_indirectBindingTable，这东西其实就是个存储 atom 的数组，每个 atom 都会按解析顺序被 append 到这个数组上（如果不被合并的话）。

同时SymbolTable还维护了多个 mapping，辅助用于外部根据 name、content、references 查询某个 atom 的各类需求。

class SymbolTable : public ld::IndirectBindingTable
{
private:

// core vector 
std::vector<const ld::Atom*>&        _indirectBindingTable;

// for by-name query
NameToSlot                           _byNameTable;

// for by-content query
ContentToSlot                        _literal4Table;
ContentToSlot                        _literal8Table;
ContentToSlot                        _literal16Table;
UTF16StringToSlot                    _utf16Table;
CStringToSlot                        _cstringTable;

// fo by-reference query
ReferencesToSlot                     _nonLazyPointerTable;
ReferencesToSlot                     _threadPointerTable;
ReferencesToSlot                     _cfStringTable;
ReferencesToSlot                     _objc2ClassRefTable;
ReferencesToSlot                     _pointerToCStringTable;
}

ld64 在 Resolve 阶段执行合并、处理 undefined 等操作都是基于该SymbolTable来完成。

三、ld64 命令参数

iOS 工程中一般不会主动触发 ld64，可以在 Xcode build log 中找到 linking 对应的 clang 命令，复制到 terminal 加上 -v来输出 clang 调用的 ld 命令。

ld64 命令的参数形式为：

ld files...  [options] [-o outputfile]

一个简单工程的 ld64 参数大致如下：

ld -filelist xxx -framework Foundation -lobjc -o yyy 

其中

• -o指定 output 的路径
• input files 的输入有几种方式

• 直接作为命令行的参数传入

• 通过-filelist以文件的形式传入，该文件以换行符分隔每一个 input file
• 通过搜索路径
• -lxxx，告诉 ld64 去 lib 搜索路径找libxxx.a 或者libxxx.dylib
• lib 搜索路径默认是/usr/lib和/usr/local/lib
• 可以通过-Lpath/to/your/lib 来增加额外的 lib 搜索路径
• -framework xxx，告诉 ld64 去 framework 搜索路径找xxx.framework/xxx
• framework 搜索路径默认是/Library/Frameworks和/System/Library/Frameworks
• 可以通过 -Fpath/to/your/framework来增加额外的 framework 搜索路径
• 如果指定了-syslibroot /path/to/search，会给 lib 和 framework 搜索路径都加上/path/to/search 的前缀（如 iOS 模拟器一般会拼上形如/Applications/Xcode.app/Contents/Developer/Platforms/iPhoneSimulator.platform/Developer/SDKs/iPhoneSimulator14.5.sdk的路径）
  
  
• 其他 options

四、ld64 执行流程

从顶层视角来看，ld64 接收一组 input files 和 options，输出 executable（注：ld64 也支持 dylib 等其他类型的输出，下面主要以 executable 为例）

执行逻辑可以分为以下 5 个大阶段：

1. Command line processing
2. Parsing input files
3. Resolving
4. Passes/Optimizations
5. Generate output file

Command Line Processing

第一步是解析命令行参数。比较直观，就是把命令行参数字符串模型化成内存中的 Options 对象，便于后续逻辑的读取。

这一步主要做两件事：

1. 把命令行里所有的 input，转换成 input file paths。上文提到在命令行中为 ld64 指定 input files 的输入有几种方式（-filelist、各种搜索路径等等的逻辑）都会在这一步转换解析成实际 input files 的绝对路径

2. 把其他命令行参数（如-dead_strip）存到Options 对应的字段中

具体实现可参考 Options.cpp中 Options 的构造函数：

// create object to track command line arguments
Options options(argc, argv);

Parsing input files

第二步是解析 input files。遍历第一步解析出来的 input file paths，从 file system 读取文件内容进一步分析转换成

atom、fixup、sections 等信息，供 Resolver 后续使用。

ld::tool::InputFiles inputFiles(options);

上文提到 input files 主要分为 .o、.a、.dylib三类，ld64 在解析不同类型的文件时，会调用该文件对应的 parser 来处理（如 .o是mach_o::relocatable::parse），并返回对应的ld::File 子类（如.o是ld::relocatable::File），有点工厂模式的味道。

解析 .o

.o 是 ld64 获取 section 和 atom 信息的直接来源，因此需要深度地扫描。

mach_o::relocatable::parse

1.读取 Header 和 Load Command

• LC_SEGMENT_64提供各个 section 的信息（位置、大小、relocation 位置、relocation 条目数等）

• LC_SYMTAB提供 symbol table 信息（位置、大小、条目数）

• LC_DYSYMTAB 提供 symbol table 分类统计

• local symbol 个数（该文件定义的 symbol，外部不可见）
• global / defined external symbol 个数（该文件定义的 symbol 且外部可见）
• undefined external symbol 个数（外部定义的 symbol）
  LC_LINKER_OPTION
• Mach-O 中用来标识 linker option 的 Load Command，linker 会读取这些 options 作为补充
• 比如 auto-linking 等特性，就依赖这个 Load Command 来实现（注入类似-framework UIKit的参数）
• 其他信息如LC_BUILD_VERSION 

2.对 section 和 symbol 按地址排序：因为 Mach-O 自带的顺序可能是乱的

3. makeSections：根据 LC_SEGMENT_64创建 Section 数组，存入_sectionsArray

4.处理__compact_unwind和__eh_frame

5.创建_atomsArray：遍历_sectionsArray，把每个 section 的 atom 加入_atomsArray

6.makeFixups：创建 fixup

• 遍历_sectionsArray，读取该 section 的 relocation entries
• 转换成 FixupInAtom
• 存入_allFixups (vector<FixupInAtom>)

解析.o的逻辑参考ld::relocatable::File* Parser<A>::parse。

解析 .a

处理.a时一开始只处理 .a的 symbol table （.a的 symbol table 存储的是 symbol name -> .ooffset，仅包含每个.o的 global symbols），不需要把内部所有的.o挨个解析一遍。Resolver 在 resolve undefined symbol 时会来查找 .a的 symbol table 并按需懒加载对应的.o。

archive::Parser<A>::parse

1. 读取 header 校验该文件是否是 .a
2. 读取.asymbol table header，获取 symbol table 条目数
3. 把 symbol table 的映射存到 _hashTable中

解析 .dylib / .tbd

mach_o::dylib::parse

1. 读取 Header 和 Load Command（和.o 类似）

• LC_SEGMENT_64 、LC_SYMTAB 、LC_DYSYMTAB 等和.o类似

• LC_DYLD_INFO、 LC_DYLD_INFO_ONLY提供 dynamic loader info

• rebase info
• binding info
• weak binding info
• lazy binding info
•  export info

• 其他信息如 LC_RPATH、LC_VERSION_MIN_IPHONEOS

2.根据LC_DYLD_INFO、 LC_DYLD_INFO_ONLY、 LC_DYLD_EXPORTS_TRIE 提供的信息，存入 _atoms

后续外部来查询该 dylib 是否 export 某个符号时本质上都是查询_atoms 。

如果处理的是 .tbd，关键是要获取两个信息：

1. 提供哪些 export symbol （如 Foundation 的_NSLog）
2. 该动态库还依赖哪些其他动态库（如 Foundation 依赖 CoreFoundation & libobjc）

ld64 会借助 TAPI（https://opensource.apple.com/source/tapi/tapi-1.30/Readme.md）来 parse .tbd文件，parse 完（其实就是调 yaml 解析库解析了一遍）可以调接口（tapi::LinkerInterfaceFile）直接得到结构化的信息。

Fat 文件

ld64 支持 fat 多架构的 Mach-O 解析。

在InputFiles::makeFile中可以看到取出目标架构的逻辑：

pthread 多线程处理

• 值得一提的是，考虑到不同 input files 的解析过程是互相独立的，ld64 使用 pthread 实现了一个 worker pool 来并发处理 input files（worker 数和 CPU 逻辑核数相同）
• pthread 逻辑参考 InputFiles::InputFiles的构造函数

Resolving

第三步是调用 Resolver 把 input files 提供的所有 atoms 汇总关联成 atom graph 并处理，是「链接」的核心模块。

实现上这里的逻辑也非常多，挑选核心流程来理解。

1. buildAtomList

这一步负责从解析好的 input files 中提取所有初始的 atom 并加入全局的SymbolTable中。

遍历 inputFiles 并 parse

• 判断 input file 在 InputFiles::InputFiles 阶段是否已经 parse 完
• 已 parse 完，进行下一步
• 没 parse 完，尝试启动一个 pthread worker 处理 inputFile（执行逻辑和第一步「解析 Input」里一样），并 pthread_cond_wait等待

加载 .o 的 atoms

parse 阶段 ld64 已经从 object file 的 symbol table 和 relocation entries 中抽象出了_atoms，这一步挨个处理即可。

Resolver::doAtom处理单个 atom 的逻辑 ：

1. SymbolTable::add（仅 global symbol & undefined external symbol，local symbol 不处理）

• 如果 name 没出现过，append 到_indirectBindingTable （定义见「概念铺垫 — Symbol Table」
• 如果 name 出现过，考虑 strong / weak 等 symbol definition 冲突解决策略
• 同步更新几张辅助 mapping 表 NameToSlot、ContentToSlot、ReferencesToSlot

2. 遍历该 atom 的 fixup，尝试把 by-name / by-content 的 reference 转成 by-slot（直接指向对应_indirectBindingTable中对应的 atom）

加载 .a 的 atoms

buildAtomList 阶段理论上完全不需要处理静态库，因为只有在后面 resolve undefined symbol 时才有可能查询静态库里包含的 symbol。但在以下两种情况下，这一步需要对静态库内的 .o展开处理：

1. 如果该.a受-all_load 或-force_load影响，强制 load 所有 .o
2. 如果 ld64 开启了-ObjC，强制 load 所有包含 ObjC class 和 category 的 .o（symbol name 包含 _OBJC_CLASS_、.objc_c）

load 过程和前面提到的 object file 的 parse & 加载 atoms 一样。

静态库 File 对象内部还会维护一个 MemberToStateMap，来记录.o的 load 状态

加载 .dylib 的 atoms

buildAtomList 阶段不 add 动态库的 atoms，但会做一些额外的处理和校验，包括 bitcode bundle（__LLVM, __bundle）、 Swift framework 依赖检查、Swift 版本检查等。

2. resolveUndefines

此时 SymbolTable中已经收集了 input files 中的大部分 atom，下一步需要把其中归属不明的 symbol 引用关联到对应的 symbol 定义上去。

1. 遍历 SymbolTable中 undefined symbol （被 reference 的但是没有对应 atom 实体的 symbol definition）

2. 对每一个 undefined symbol ，尝试去静态库 & 动态库里找

• 静态库：前面提到静态库维护了一个 symbol name ->.ooffset 的 mapping，因此要判断某个 symbol definition 是否属于该静态库只需要去这个 mapping 里查即可。如果查找到了，则解析对应的.o、并把该 .o的 atoms 加入 SymbolTable 中（.o的加载逻辑参考前文 Parsing input files 和 buildAtomList）
• 动态库：如果匹配到了某个动态库的 exported symbol，ld64 会为该 undefined atom 创建一个 proxy atom 表示对动态库中的引用。

3. 如果静态库 & 动态库里都没找到，判断是否是 section$、segment$等 boundary atoms，并手动创建对应的 symbol definition

4. 处理 tentative symbol

5. 如果-undefined不是 error（命令行参数控制发现 undefined symbol 时不报错）、或者命中了 -U（参数控制某些 undefined symbol 不报错），那么 ld64 会手动创建一个 UndefinedProxyAtom作为其 symbol definition

由于搜索静态库和动态库的过程中有可能引入新的 undefined symbol，因此一次遍历结束后需要判断该条件并按需重新遍历。

3. deadStripOptimize

接下来执行开启了-dead_strip后的逻辑。此时所有的 atom 和它们之间的引用关系已经记录在了 SymbolTable中，可以把所有的 atom 抽象成 atom graph 来移除没有被引用到的无用 atom。

1. 初始化 root atoms
1.entry point atom（如_main）
2.所有被-u（强制加载某个 symbol，即使在静态库中）、-exported_symbols_list、-exported_symbol(在 output 中作为 global symbol 输出） 命中的 atoms
3.dyld 相关的几个 stub atom
4.所有被标记为 dont-dead-strip 的 atom（该 atom 对应的 section 在 .o中被标记为了S_ATTR_NO_DEAD_STRIP）
2. 从 root atoms 开始通过 fixup 遍历 atom graph，把它们能遍历到的 atoms 都标记为 live
3. 移除 dead atom

4. removeCoalescedAwayAtoms

遍历一遍 atoms，移除所有被合并的 atom。

（Symbol 的合并参考「概念铺垫 — Symbol」）

5. fillInInternalState

遍历一遍 atoms，把它们按照所属的 section 归类存放。

Passes/Optimizations

至此，我们已经拥有了写 output 所需要的完整的、有关联的信息了（sections & 对应的 atoms）。在输出之前，还需要执行多轮的「Pass」。一个 Pass 对应实现某一特定特性的代码逻辑，如

• ld::passes::objc
• ld::passes::stubs
• ld::passes::dylibs
• ld::passes::dedup::doPass
• ...

pass 依次执行，个别 pass 之间也会强制要求执行的先后顺序以保证输出的正确性。

每个工程可以结合实际需求调整要执行的 pass。

Generate Output files

最后一步是输出 output files。ld64 的输出包括主 output 文件和其他辅助输出如 link map、dependency info 等。

在正式输出前，ld64 还执行了一些其他操作，包括：

• ...
• synthesizeDebugNotes
• buildSymbolTable
• generateLinkEditInfo
• buildChainedFixupInfo
• ...

其中buildSymbolTable负责构建 output file 中的 symbol table。「概念铺垫 — Symbol」中提到每个 symbol 在 link 阶段有自己的 visibility，用来控制 link 时对其他文件的可见性。同理，在 link 结束后输出的 Mach-O 中这些 symbol 现在隶属于一个新的文件，此时它们的 visibility 要被 ld64 依据各种处理策略来重新调整：

1. 前文提到的被标记为 private extern 的 symbol，这一步被转换为 local symbol
2. ld64 也提供了多种参数来控制这一行为，如 -reexport-lx、-reexport_library、-reexport_framework（指定 lib 的 global symbol 在 output 中继续为 global）、-hidden-lx（指定 lib 中的 symbol 在 output 中转为 hidden）

上述操作都忙完后，ld64 就会拿着 FinalSection数组愉快地去写 output file 了，大致逻辑如下：

• 开辟一块内存，维护一个当前写入位置的 offset 指针
• 遍历 FinalSection数组

• 遍历 atoms

• 如果是动态库创建的 proxy atom，跳过（不占用输出文件的空间）

• 把 atom content 写入当前 offset

• 遍历 fixups（applyFixUps），根据 fixup 的类型修正 atom content 对应位置的内容

五、ld64 on iOS

Auto Linking

auto linking 是一种不用主动声明 -l、 -framework等 lib 依赖也能让 linker 正常工作的机制。

比如：

• 某个源文件声明依赖了#import <AppKit/AppKit.h>
• link 时不指定-framework AppKit
• 编译生成的 .o的 LC_LINKER_OPTION 中带有 -framework AppKit

又或者：

• 某个源文件声明了#import <zlib.h>
• /usr/include/module.modulemap内容

module zlib [system] [extern_c] {
 header "zlib.h"
 export *
 link "z"
}

• link 时不指定-lz
• 编译生成的 .o的LC_LINKER_OPTION中带有 -lz

实现原理：compiler 编译 .o时，解析 import，把依赖的 framework 写入最后 Mach-O 里的 LC_LINKER_OPTION（存储了对应的-framework XXX信息）

要注意的是，开启 Clang module 时（-fmodules）自动开启 auto linking 。可以用-fno-autolink主动关闭。

-ObjC 的由来

前面提到开启了 -ObjC 后，ld64 会在解析符号 search lib 时强制加载每个静态库内包含 ObjC class 和 category 的 .o。这么做的原因是什么呢？

经试验可发现：

• ObjC 的 class 定义对应 symbol 的 visibility 为global（自己定义、link 时外部文件可见）
• ObjC 的 class 调用对应 symbol 的 visibility 为undefined external（外部定义、需要 link 时 fixup）
• ObjC 的 method 定义对应 symbol 的 visibility 为local（对外部不可见）
• ObjC 的 method 调用不会生成 symbol

假设现在有两个类 ClassA & ClassB：

// ClassA.m


#import "ClassB.h"

@implementation ClassA

- (void)methodA
{
  [[ClassB new] methodB];
}

@end



// ClassB.m

@implementation ClassB

- (void)methodB
{
   
}

@end

编译后，ClassA.o：

• global symbol：...
• local symbol：...
• undefined external symbol：_OBJC_CLASS_$_ClassB

ClassB.o：

• global symbol：_OBJC_CLASS_$_ClassB
• local symbol：-[ClassB methodB]
• undefined external：...

虽然 ClassA 调用了 ClassB 的方法，但 Class A 生成的 object file 的 symbol table 中只有_OBJC_CLASS_$_ClassB这个对 ClassB 类本身的 reference，根本没有-[ClassB methodB]。这样的话，按照 ld64 正常的解析逻辑，既不会因为 ClassA中对methodB的调用去寻找ClassB.m的定义（压根没有生成 undefined external）、即使想找，ClassB也没有暴露这个 method 的 symbol （local symbol 对外部文件不可见）。

既然如此，ObjC 的 method 定义为什么不会被 ld64 认为是 dead code 而 strip 掉呢？

其实是因为 ObjC 的 class 定义会间接引用到它的 method 定义。比如上面 ClassB的例子中，atom 之间的依赖关系如下：

_OBJC_CLASS_$_ClassB -> __OBJC_CLASS_RO_$_ClassB->

__OBJC_$_INSTANCE_METHODS_ClassB->-[ClassB methodB]

只要这个 class 定义被引用了，那么它的所有 method 定义也会被一起认为是 live code 而保留下来。

再看看引入 Category 后的情况：

• 假设 B 定义了ClassB和 methodB
• C 是 B 的 category，定义了ClassB的methodBFromCategory
• A 引用了ClassB 和 methodB、methodBFromCategory

这种情况下：

• 因为 A 引用了 B 的 ClassB，所以 B 要被 ld64 加载。
• 虽然 A 引用了 C 的methodBFromCategory，但 A 没有解析methodBFromCategory这个符号的需求（没生成），因此 ld64 不需要加载 C。

为了让程序能正确执行，C 的methodBFromCategory定义必须被 ld64 link 进来。这里需要分两种情况：

1. 如果 C 在主工程中，ld64 需要直接解析 C 生成的 object file，并生成如下 atom 依赖：

objc-cat-list-> __OBJC_$_CATEGORY_ClassB_$_SomeCategory

-> __OBJC_$_CATEGORY_INSTANCE_METHODS_ClassB_$_SomeCategory ->

-[ClassB(SomeCategory) methodBFromCategory]

其中 objc-cat-list表示所有 ObjC 的 categories，在 dead code strip 初始阶段被标记为 live，因此methodBFromCategory会被 link 进 executable 而不被裁剪。

2. 如果 C 被封装在一个静态库里，link 时 ld64 没有动机去加载 C，methodBFromCategory没有被 link 进 executable，导致最终运行时 ClassB没有加载该 category、执行时错误。

所以才有了 -ObjC 这个开关，保证静态库中单独定义的 ObjC category 被 link 进最终的 output 中。

现在的 Xcode 中一般默认都开启了 -ObjC，但这种为了兼容 category 而暴力加载静态库中所有 ObjC class 和 category 的实现并不是最完美的方案，因为可能因此在 link 阶段加载了许多本不需要加载的 ObjC class。理论上我们可以通过人为在 category 定义和引用之间建立引用关系来让 ld64 在不开启 -ObjC的情况下也能加载 category，比如 IGListKit 就曾尝试手动注入一些 weak 的 dummy 变量（PR https://github.com/Instagram/IGListKit/pull/957） ，但这种做法为了不劣化也会带来一定维护成本，因此也需要权衡。

ld64 中对-ObjC的处理可参考src/ld/parsers/archive_file.cpp：

bool File<A>::forEachAtom(ld::File::AtomHandler& handler) const
{
    bool didSome = false;
    if ( _forceLoadAll || _forceLoadThis ) {
        // call handler on all .o files in this archive
        ...
    }
    else if ( _forceLoadObjC ) {
        // call handler on all .o files in this archive containing objc classes
        for (const auto& entry : _hashTable) {
            if ( (strncmp(entry.first, ".objc_c", 7) == 0) || (strncmp(entry.first, "_OBJC_CLASS_$_", 14) == 0) ) {
                const Entry* member = (Entry*)&_archiveFileContent[entry.second];
                MemberState& state = this->makeObjectFileForMember(member);
                char memberName[256];
                member->getName(memberName, sizeof(memberName));
                didSome |= loadMember(state, handler, "-ObjC forced load of %s(%s)\n", this->path(), memberName);
            }
        }
        // ObjC2 has no symbols in .o files with categories but not classes, look deeper for those
        const Entry* const start = (Entry*)&_archiveFileContent[8];
        const Entry* const end = (Entry*)&_archiveFileContent[_archiveFilelength];
        ...
    }
    ...    
}

六、其他

调试向的命令行参数

ld64 也提供了丰富的参数供开发者查询其执行过程，可以在 mac 上通过 man ld查看 Options for introspecting the linker 一栏

-print_statistics

打印 ld64 各大步骤的耗时分布。

      ld total time: 2.26 seconds
   option parsing time:  6.9 milliseconds (  0.3%)
 object file processing:  0.1 milliseconds (  0.0%)
     resolve symbols: 2.24 seconds
     build atom list:  0.0 milliseconds (  0.0%)
         passess:  6.2 milliseconds (  0.2%)
      write output:  10.4 milliseconds (  0.4%)

-t

打印 ld64 加载的每一个 .o .a .dylib。

-why_load xxx

打印.a 中 .o被加载的原因（即什么 symbol 被需要）。

-ObjC forced load of bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTHomeTab/libCommon.a(ArticleTabBarStyleNewsListScreenshotsProvider_IMP.o)
-ObjC forced load of bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTHomeTab/libCommon.a(TTExploreMainViewController.o)
-ObjC forced load of bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTHomeTab/libCommon.a(TTFeedCollectionViewController.o)
-ObjC forced load of bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTHomeTab/libCommon.a(TTFeedCollectionFollowListCell.o)
....
_dec_8i40_31bits forced load of external/TTAudio/Vendor/libopencore-amrnb.a(d8_31pf.o)
_decode_2i40_11bits forced load of external/TTAudio/Vendor/libopencore-amrnb.a(d2_11pf.o)
_decode_2i40_9bits forced load of external/TTAudio/Vendor/libopencore-amrnb.a(d2_9pf.o)

-why_live xxx

打印开启 -dead_strip后，某个 symbol 的 reference chain（即不被 strip 的原因）

比如 -why_live _OBJC_CLASS_$_TTNewUserHelper：

_OBJC_CLASS_$_TTNewUserHelper from external/TTVersionHelper/ios-arch-iphone/libTTVersionHelper_TTVersionHelper_awesome_ios.a(TTNewUserHelper.o)
 objc-class-ref from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTPrivacyAlertManager/libNews.a(TTPrivacyAlertManager.swift.o)
  +[TTDetailLogManager createLogItemWithGroupID:] from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTDetail/libCommon.a(TTDetailLogManager.o)
   __OBJC_$_CLASS_METHODS_TTDetailLogManager from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTDetail/libCommon.a(TTDetailLogManager.o)
    __OBJC_METACLASS_RO_$_TTDetailLogManager from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTDetail/libCommon.a(TTDetailLogManager.o)
     _OBJC_METACLASS_$_TTDetailLogManager from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTDetail/libCommon.a(TTDetailLogManager.o)
      _OBJC_CLASS_$_TTDetailLogManager from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTDetail/libCommon.a(TTDetailLogManager.o)
       objc-class-ref from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/LMCoreKitTTAdapter/libNews.a(LMDetailTechnicalLoggerImpl.o)
        ___73-[TTDetailFetchContentManager fetchDetailForArticle:priority:completion:]_block_invoke from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTDetail/libCommon.a(TTDetailFetchContentManager.o)
         -[TTDetailFetchContentManager fetchDetailForArticle:priority:completion:] from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTDetail/libCommon.a(TTDetailFetchContentManager.o)
          __OBJC_$_INSTANCE_METHODS_TTDetailFetchContentManager from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTDetail/libCommon.a(TTDetailFetchContentManager.o)
           __OBJC_CLASS_RO_$_TTDetailFetchContentManager from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTDetail/libCommon.a(TTDetailFetchContentManager.o)
            _OBJC_CLASS_$_TTDetailFetchContentManager from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTDetail/libCommon.a(TTDetailFetchContentManager.o)
             objc-class-ref from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/BDAudioBizTTAdaptor/libNews.a(TTAudioFetchableImp.o)
              objc-class-ref from bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/BDAudioBizTTAdaptor/libNews.a(TTAudioFetchableImp.o)

-map (linkmap)

输出 linkmap 到指定路径，包含所有 symbols 和对应地址的 map 。

# Path: /Users/bytedance/NewsInHouse_bin
# Arch: x86_64

# Object files:
...
[3203] bazel-out/ios-x86_64-min10.0-applebin_ios-ios_x86_64-dbg-ST-7bf874b56ea0/bin/Module/TTHomeTab/libCommon.a(TTFeedActivityView.o)
...

# Sections:
# Address        Size            Segment        Section
0x100004000        0x0D28B292        __TEXT        __text
0x10D28F292        0x00011586        __TEXT        __stubs
...
0x10D70B5E8        0x00346BE0        __DATA        __cfstring
0x10DA521C8        0x00032170        __DATA        __objc_classlist
...

# Symbols:
# Address        Size            File  Name
0x100004590        0x00000020        [  8] -[NSNull(Addition) boolValue]
...
0x1117EE0C6        0x00000027        [4282] literal string: -[TTFeedGeneralListView skipTopHeight]
...
0x1104B4430        0x00000028        [22685] _OBJC_METACLASS_$_MQPWebService
0x1104B4458        0x00000028        [22685] _OBJC_CLASS_$_APayH5WapViewToolbar
...
0x1114A9CD4        0x0000005C        [ 10] GCC_except_table0
0x1114A9D30        0x00000028        [ 14] GCC_except_table12
...
<<dead>>         0x00000008        [3269] _kCoverAcatarMargin
<<dead>>         0x00000008        [3269] _kCoverTitleMargin
...

LTO — Link Time Optimization

LTO 是一种链接期全模块级别代码优化的技术。开启 LTO 后 ld64 会借助 libLTO 来实现相关功能。关于 ld64 处理 LTO 的机制后续会单独另写一篇文章介绍。

结语

本文从源码角度分析了 ld64 的主体工作原理，实际应用中工程可结合自身需求对 ld64 进行定制来修复特定问题或者实现特定功能。本文也是系列的第一章内容，后续会带来更多静态链接器的介绍，包括 zld，lld，mold 等，敬请期待。

参考资料

• https://opensource.apple.com/source/ld64/
• https://opensource.apple.com/source/ld64/ld64-136/doc/design/linker.html
• https://github.com/aidansteele/osx-abi-Mach-O-file-format-reference

关于字节终端技术团队

字节跳动终端技术团队(Client Infrastructure)是大前端基础技术的全球化研发团队（分别在北京、上海、杭州、深圳、广州、新加坡和美国山景城设有研发团队），负责整个字节跳动的大前端基础设施建设，提升公司全产品线的性能、稳定性和工程效率；支持的产品包括但不限于抖音、今日头条、西瓜视频、飞书、瓜瓜龙等，在移动端、Web、Desktop等各终端都有深入研究。

就是现在！客户端／前端／服务端／端智能算法／测试开发 面向全球范围招聘！一起来用技术改变世界，感兴趣请联系 chenxuwei.cxw@bytedance.com，邮件主题 简历-姓名-求职意向-期望城市-电话。

记得点击关注公众号，别错过下次干货内容推送哦！