乐趣区

关于ios:深入-iOS-静态链接器一-ld64

作者:字节跳动终端技术——李翔

前言

动态链接(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 的命名据说是来自 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/… 凋谢了 ld64 的源码,但更新不那么及时,始终落后于正式版(如 2021.8 为止开源最新是 609 版本,Xcode 12.5.1 是 650.9)。zld 等基于 ld64 的我的项目都是 fork 自开源版的 ld64。

二、概念铺垫

在介绍 ld64 的执行流程之前,须要先理解几个概念。

输出 — .o.a.dylib

ld64 次要解决 Mach kernel) 上的 Mach-O 输出,包含:

  • Object File (.o)

    • 由 compiler 生成,蕴含元数据(header、LoadCommand 等)、segments & sections(代码、数据 等)、symbol table & relocation entries。
    • object file 之间可能相互依赖(如 A 援用了 B 定义的函数),static linker 做的事件实质上就是把这些信息关联起来输入成一个总的无效的 Mach-O。

  • 动态库 (.a)

    • 能够视为 .o 的汇合,让工程代码能模块化地被组织和复用。
    • 其头部还存储了 symbol name -> .o offset 的映射表,便于 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 等信息。通过解析 .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 中。

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 的偏移和大小

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

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 的加载机制见后文)

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。

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/aidansteel…。

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)

| 类型 | 实现 | 阐明 |
| ———– | ———– | ———– |
| 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:

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

其中节点信息(atom)由 main.oFoo.o 的 symbol table 提供,边信息(fixup)由 main.o 的 relocation entries 提供。

如果波及 ObjC,援用关系会更简单一些,后文「-ObjC 的由来」一节会具体开展。

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.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);

上文提到 input files 次要分为 .o.a.dylib 三类,ld64 在解析不同类型的文件时,会调用该文件对应的 parser 来解决(如 .omach_o::relocatable::parse),并返回对应的 ld::File 子类(如 .old::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 -> .o offset,仅蕴含每个 .o 的 global symbols),不须要把外部所有的 .o 挨个解析一遍。Resolver 在 resolve undefined symbol 时会来查找 .a 的 symbol table 并按需懒加载对应的 .o

archive::Parser<A>::parse

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

解析 .dylib / .tbd

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/…)来 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 表 NameToSlotContentToSlotReferencesToSlot
  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 -> .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

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
  • 编译生成的 .oLC_LINKER_OPTION 中带有 -framework AppKit

又或者:

  • 某个源文件申明了 #import <zlib.h>
  • /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 信息)

要留神的是,开启 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/…),但这种做法为了不劣化也会带来肯定保护老本,因而也须要衡量。

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/…
  • https://opensource.apple.com/…
  • https://github.com/aidansteel…

对于字节终端技术团队

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

就是当初!客户端/前端/服务端/端智能算法/测试开发 面向寰球范畴招聘! 一起来用技术扭转世界 ,感兴趣请分割 chenxuwei.cxw@bytedance.com,邮件主题 简历 - 姓名 - 求职意向 - 冀望城市 - 电话

退出移动版