深入 iOS 静态链接器— ld64

生也有涯,知也无涯。这篇文章主要讲述深入 iOS 静态链接器— ld64相关的知识,希望能为你提供帮助。

深入 iOS 静态链接器— ld64

文章图片

作者:字节跳动终端技术——李翔
前言静态链接(static linking)是程序构建中的一个重要环节,它负责分析 compiler 等模块输出的 .o.a.dylib 、经过对 symbol 的解析、重定向、聚合,组装出 executable 供运行时 loader 和 dynamic linker 来执行,有着承上启下的作用。
深入 iOS 静态链接器— ld64

文章图片

对于 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 的命名据说是来自 LoaDerLink 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 的执行流程之前,需要先了解几个概念。
输入 — .o.a.dylibld64 主要处理 Mach kernel 上的 Mach-O 输入,包括:
  • Object File (.o)
    • 由 compiler 生成,包含元数据(header、LoadCommand 等)、segments & sections(代码、数据 等)、symbol table & relocation entries。
    • object file 之间可能相互依赖(如 A 引用了 B 定义的函数),static linker 做的事情本质上就是把这些信息关联起来输出成一个总的有效的 Mach-O 。
深入 iOS 静态链接器— ld64

文章图片

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

文章图片

  • 动态库 (.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 等信息。通过解析 .tbd ld64 可以快速地知道该 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, ....]

Symbol & Symbol Table对 static linker 来说,symbol 是 Mach-O 提供的、link 时需要参考的一个个基本元素。
Mach-O 有一块专门的区域用于存储所有的 symbol,即 symbol table。
global function、global variable、class 等都会作为一条条 entry 被放入 symbol table 中。
深入 iOS 静态链接器— ld64

文章图片

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 具体的数据结构可以参考文档或源码
Visibility
Mach-O 中将 symbol 分为三组:
  • global / defined external symbol :外部可用的 symbol 定义
  • local symbol:该文件定义和引用的 symbol,仅该文件可用(比如被 static 标记)
  • undefined external symbol:依赖外部的 symbol 引用
属性 说明 举例
global / defined external symbol 由该文件定义,对外部可见 int i = 1;
local symbol 由该文件定义,对外部不可见 static int i = 1;
undefined external symbol 引用了外部的定义 extern int i;
可以通过查看该 Mach-O LoadCommand 中的 LC_DYSYMTAB 来获取三组 symbol 的偏移和大小
深入 iOS 静态链接器— ld64

文章图片

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
深入 iOS 静态链接器— ld64

文章图片

-fvisibility=hidden
深入 iOS 静态链接器— ld64

文章图片

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.cvoid __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:
深入 iOS 静态链接器— ld64

文章图片

执行后输出:
strong foo called

要注意的是,分析最终输出使用了哪个 symbol definition 需要结合实际情况。比如某个 strong symbol 封装在静态库中,始终没有被 static linker 加载,而同名的 weak symbol 已经被加载了,上述(2)的策略就应当变成(3)了。(关于静态库中 symbol 的加载机制见后文)
Tentative definitions / Commons
symbol definition 还可能是 tentative definition(或者叫 common definition)。这个其实也很常见,比如:
int i;

这样一个未初始化的全局变量就是一个 tentative definition。
更官方一点的定义是:
说的比较绕不要被带进去了,可以先简单理解 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 symbolint 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。
Relocation (Entries)compiler 无法在编译期确定所有 symbol 的地址(如对外部函数的调用),因此会在 Mach-O 对应的位置“留空”、并生成一条对应的 Relocation Entry。static linker 在链接期通过 Relocation Entry 知晓每个 section 中哪些位置需要被 relocate、如何 relocate。
Load Command 中的 LC_SEGMENT_64 描述了各个 section 对应的 Relocation Entries 的数量、偏移量:
深入 iOS 静态链接器— ld64

文章图片

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。
ld64 — Atom & Fixupld64 是一种 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)
类型 实现 说明
direct 记录指向目标 Atom 的 pointer 一般由同一个 object file 里对一些匿名、不可变的 target atom 的引用生成,如在同一个 object file 里调用 static function
by-name 记录指向目标 Atom name(c-string) 的指针 引用 global symbol,比如调用 printf
indirect 记录指向 atom indirect table 中某个 index 的指针 非 input file 提供,只能由 linker 在 link 阶段生成,可用于 atom 合并后的 case
看一个简单的例子:
// 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.oFoo.o 存在以下 symbol:
深入 iOS 静态链接器— ld64

文章图片

link 时 ld64 会将其转换成如下的 atom graph:
深入 iOS 静态链接器— ld64

文章图片

其中节点信息(atom)由 main.oFoo.o 的 symbol table 提供,边信息(fixup)由 main.o 的 relocation entries 提供。
如果涉及 ObjC,引用关系会更复杂一些,后文「-ObjC 的由来」一节会详细展开。
ld64 — Symbol Tableld64 内部维护了一个 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 为例)
深入 iOS 静态链接器— ld64

文章图片

执行逻辑可以分为以下 5 个大阶段:
  1. Command line processing
  2. Parsing input files
  3. Resolving
  4. Passes/Optimizations
  5. Generate output file
深入 iOS 静态链接器— ld64

文章图片

Command Line Processing第一步是解析命令行参数。比较直观,就是把命令行参数字符串模型化成内存中的 Options 对象,便于后续逻辑的读取。
这一步主要做两件事:
  1. 把命令行里所有的 input,转换成 input file paths。上文提到在命令行中为 ld64 指定 input files 的输入有几种方式(-filelist、各种搜索路径等等的逻辑)都会在这一步转换解析成实际 input files 的绝对路径
  2. 把其他命令行参数(如 -dead_strip)存到 Options 对应的字段中
深入 iOS 静态链接器— ld64

文章图片

具体实现可参考 Options.cppOptions 的构造函数:
// 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);

深入 iOS 静态链接器— ld64

文章图片

上文提到 input files 主要分为 .o.a.dylib 三类,ld64 在解析不同类型的文件时,会调用该文件对应的 parser 来处理(如 .omach_o::relocatable::parse),并返回对应的 ld::File 子类(如 .old::relocatable::File),有点工厂模式的味道。
解析 .o
.o 是 ld64 获取 section 和 atom 信息的直接来源,因此需要深度地扫描。
深入 iOS 静态链接器— ld64

文章图片

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& lt; FixupInAtom& gt; )
解析 .o 的逻辑参考 ld::relocatable::File* Parser& lt; A& gt; ::parse
解析 .a
处理 .a 时一开始只处理 .a 的 symbol table (.a 的 symbol table 存储的是 symbol name -> .o offset,仅包含每个 .o 的 global symbols),不需要把内部所有的 .o 挨个解析一遍。Resolver 在 resolve undefined symbol 时会来查找 .a 的 symbol table 并按需懒加载对应的 .o
深入 iOS 静态链接器— ld64

文章图片

archive::Parser& lt; A& gt; ::parse
  1. 读取 header 校验该文件是否是 .a
  2. 读取 .a symbol table header,获取 symbol table 条目数
  3. 把 symbol table 的映射存到 _hashTable
解析 .dylib / .tbd
深入 iOS 静态链接器— ld64

文章图片

mach_o::dylib::parse
  1. 读取 Header 和 Load Command(和 .o 类似)
    • LC_SEGMENT_64LC_SYMTABLC_DYSYMTAB 等和 .o 类似
    • LC_DYLD_INFOLC_DYLD_INFO_ONLY 提供 dynamic loader info
      • rebase info
      • binding info
      • weak binding info
      • lazy binding info
      • export info
    • 其他信息如 LC_RPATHLC_VERSION_MIN_IPHONEOS
  2. 根据 LC_DYLD_INFOLC_DYLD_INFO_ONLYLC_DYLD_EXPORTS_TRIE 提供的 symbol 信息,存入 _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)直接得到结构化的信息。
深入 iOS 静态链接器— ld64

文章图片

Fat 文件
ld64 支持 fat 多架构的 Mach-O 解析。
InputFiles::makeFile 中可以看到取出目标架构的逻辑:
深入 iOS 静态链接器— ld64

文章图片

pthread 多线程处理
  • 值得一提的是,考虑到不同 input files 的解析过程是互相独立的,ld64 使用 pthread 实现了一个 worker pool 来并发处理 input files(worker 数和 CPU 逻辑核数相同)
  • pthread 逻辑参考 InputFiles::InputFiles 的构造函数
Resolving第三步是调用 Resolver 把 input files 提供的所有 atoms 汇总关联成 atom graph 并处理,是「链接」的核心模块。
深入 iOS 静态链接器— ld64

文章图片

深入 iOS 静态链接器— ld64

文章图片

实现上这里的逻辑也非常多,挑选核心流程来理解。
1. buildAtomList
这一步负责从解析好的 input files 中提取所有初始的 atom 并加入全局的 SymbolTable 中。
遍历 inputFiles 并 parse
  • 判断 input file 在 InputFiles::InputFiles 阶段是否已经 parse 完
    • 已 parse 完,进行下一步
    • 没 parse 完,尝试启动一个 pthread worker 处理 inputFile(执行逻辑和第一步「解析 Input」里一样),并 pthread_cond_wait 等待
加载 .o 的 atomsparse 阶段 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 表 NameToSlotContentToSlotReferencesToSlot
  2. 遍历该 atom 的 fixup,尝试把 by-name / by-content 的 reference 转成 by-slot(直接指向对应 _indirectBindingTable 中对应的 atom)
加载 .a 的 atomsbuildAtomList 阶段理论上完全不需要处理静态库,因为只有在后面 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 的 atomsbuildAtomList 阶段不 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 -> .o offset 的 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
  • ...
深入 iOS 静态链接器— ld64

文章图片

pass 依次执行,个别 pass 之间也会强制要求执行的先后顺序以保证输出的正确性。
每个工程可以结合实际需求调整要执行的 pass。
Generate Output files最后一步是输出 output files。ld64 的输出包括主 output 文件和其他辅助输出如 link map、dependency info 等。
深入 iOS 静态链接器— ld64

文章图片

在正式输出前,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 Linkingauto linking 是一种不用主动声明 -l-framework 等 lib 依赖也能让 linker 正常工作的机制。
比如:
  • 某个源文件声明依赖了 #import & lt; AppKit/AppKit.h& gt;
  • link 时不指定 -framework AppKit
  • 编译生成的 .oLC_LINKER_OPTION 中带有 -framework AppKit
又或者:
  • 某个源文件声明了 #import & lt; zlib.h& gt;
  • /usr/include/module.modulemap 内容
module zlib [system] [extern_c] { header "zlib.h" export * link "z" }

  • link 时不指定 -lz
  • 编译生成的 .oLC_LINKER_OPTION 中带有 -lz
实现原理:compiler 编译 .o 时,解析 import,把依赖的 framework 写入最后 Mach-O 里的 LC_LINKER_OPTION (存储了对应的 -framework XXX 信息)
深入 iOS 静态链接器— ld64

文章图片

要注意的是,开启 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 定义了 ClassBmethodB
  • C 是 B 的 category,定义了 ClassBmethodBFromCategory
  • A 引用了 ClassBmethodBmethodBFromCategory
这种情况下:
  • 因为 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 而不被裁剪。
  1. 如果 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: # AddressSizeSegmentSection 0x1000040000x0D28B292__TEXT__text 0x10D28F2920x00011586__TEXT__stubs ... 0x10D70B5E80x00346BE0__DATA__cfstring 0x10DA521C80x00032170__DATA__objc_classlist ...# Symbols: # AddressSizeFileName 0x1000045900x00000020[8] -[NSNull(Addition) boolValue] ... 0x1117EE0C60x00000027[4282] literal string: -[TTFeedGeneralListView skipTopHeight] ... 0x1104B44300x00000028[22685] _OBJC_METACLASS_$_MQPWebService 0x1104B44580x00000028[22685] _OBJC_CLASS_$_APayH5WapViewToolbar ... 0x1114A9CD40x0000005C[ 10] GCC_except_table0 0x1114A9D300x00000028[ 14] GCC_except_table12 ... < < dead> > 0x00000008[3269] _kCoverAcatarMargin < < dead> > 0x00000008[3269] _kCoverTitleMargin ...

LTO — Link Time OptimizationLTO 是一种链接期全模块级别代码优化的技术。开启 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等各终端都有深入研究。
【深入 iOS 静态链接器— ld64】就是现在!客户端/前端/服务端/端智能算法/测试开发 面向全球范围招聘!一起来用技术改变世界,感兴趣请联系 chenxuwei.cxw@bytedance.com,邮件主题 简历-姓名-求职意向-期望城市-电话。

    推荐阅读