作者：位元組跳動終端技術——李翔
靜态連結（static linking）是程式建構中的一個重要環節，它負責分析 compiler 等子產品輸出的 <code>.o</code>、<code>.a</code>、<code>.dylib</code> 、經過對 symbol 的解析、重定向、聚合，組裝出 executable 供運作時 loader 和 dynamic linker 來執行，有着承上啟下的作用。
對于 iOS 工程而言，目前負責靜态連結的主要是 ld64。蘋果對 ld64 加持了一些功能，以适配 iOS 項目的建構，比如：
現在在 Xcode 中即使不主動管理依賴的系統動态庫（如 UIKit），你的工程也可以正常連結成功
提供“強制加載靜态庫中 ObjC class 和 category” 的開關（預設開啟），讓 ObjC 的資訊在輸出中完整不丢失
大量特性的實作也在靜态連結這一步完成，如：
基于二進制重排的啟動速度優化，利用 ld64 的<code>-order_file</code> 讓 linker 按照指定順序生成 Mach-O
用 <code>-exported_symbols_list</code> 優化建構産物中 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 的命名據說是來自 <code>LoaDer</code> 、<code>Link eDitor</code>。
ld64：ld64 是蘋果為 Darwin 系統重新設計的 ld。和 ld 的最大差別在于，ld64 是 atom-based 而不是 section-based（關于 atom 的介紹後面會展開）。在 macOS 上執行 <code>ld</code> （<code>/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ld</code>）預設就是 ld64。系統和 Xcode 自帶的版本可以通過 <code>ld -version_details</code> 查詢，如 650.9。蘋果在這裡 https://opensource.apple.com/tarballs/ld64/ 開放了 ld64 的源碼，但更新不那麼及時，始終落後于正式版（如 2021.8 為止開源最新是 609 版本，Xcode 12.5.1 是 650.9） 。zld 等基于 ld64 的項目都是 fork 自開源版的 ld64。
在介紹 ld64 的執行流程之前，需要先了解幾個概念。
ld64 主要處理 Mach kernel 上的 Mach-O 輸入，包括：
Object File (<code>.o</code>)
由 compiler 生成，包含中繼資料（header、LoadCommand 等）、segments & sections（代碼、資料 等）、symbol table & relocation entries。
object file 之間可能互相依賴（如 A 引用了 B 定義的函數），static linker 做的事情本質上就是把這些資訊關聯起來輸出成一個總的有效的 Mach-O 。
靜态庫 (<code>.a</code>)
可以視為 <code>.o</code> 的集合，讓工程代碼能子產品化地被組織和複用。
其頭部還存儲了 symbol name -> <code>.o</code> offset 的映射表，便于 link 時快速查詢某個 symbol 的歸屬。
一個靜态庫可能包含多個架構（universal / fat Mach-O），static linker 在處理時會按需選擇目标架構。可以通過 <code>lipo</code> 等工具檢視其架構資訊。
動态庫 (<code>.dylib</code>、<code>.tbd</code>)
不同于靜态庫，動态庫由 dyld 在運作時經過 rebase、binding 等過程後加載。static linker 在 link 時僅在處理 undefined symbol 時會嘗試從輸入的動态庫清單中查詢每個動态庫 export 的 symbol。
iOS 工程中使用的大部分是系統動态庫（UIKit 等），工程也可以以 framework 等形式提供自己的動态庫（需要指定對 rpath 以讓自定義動态庫能被 dyld 正常加載）
<code>.tbd</code> (text-based dylib stub) 是蘋果在 Xcode 7 後引入的一種描述 dylib 的檔案格式，包含支援的架構、導出哪些 symbol 等資訊。通過解析 <code>.tbd</code> ld64 可以快速地知道該 dylib 提供了哪些 symbol 可被用于連結 & 有哪些其他動态庫依賴，而不用去解析整個解析一遍 dylib。目前大多數系統的 dylib 都采用這種方式。
如 Foundation：
對 static linker 來說，symbol 是 Mach-O 提供的、link 時需要參考的一個個基本元素。
Mach-O 有一塊專門的區域用于存儲所有的 symbol，即 symbol table。
global function、global variable、class 等都會作為一條條 entry 被放入 symbol table 中。
Symbol 包含以下屬性：
名稱：具體生成規則由 compiler 決定。如 C variable <code>_someGlolbalVar</code> 、C function <code>_someGlobalFunction</code>、 ObjC class <code>__OBJC_CLASS_$_SomeClass</code>、 ObjC method <code>-[SomeClass foo]</code> 等。不同的 compiler 有不同的 name mangling 政策。
是“定義”還是“引用”：對應函數、變量的“定義”和“引用”。
visibility：如果是“定義”，還有 visibility 的概念來控制對其他檔案的可見性（具體說明見後文「visibility」）、
strong / weak：如果是“定義”，還有 strong / weak 的概念來控制多個“定義” 存在時的合并政策（具體說明見後文「strong / weak definition」。
Mach-O symbol table entry 具體的資料結構可以參考文檔或源碼
Mach-O 中将 symbol 分為三組：
global / defined external symbol ：外部可用的 symbol 定義
local symbol：該檔案定義和引用的 symbol，僅該檔案可用（比如被 <code>static</code> 标記）
undefined external symbol：依賴外部的 symbol 引用
屬性
說明
舉例
global / defined external symbol
由該檔案定義，對外部可見
<code>int i = 1;</code>
local symbol
由該檔案定義，對外部不可見
<code>static int i = 1;</code>
undefined external symbol
引用了外部的定義
<code>extern int i;</code>
可以通過檢視該 Mach-O LoadCommand 中的 <code>LC_DYSYMTAB</code> 來擷取三組 symbol 的偏移和大小
visibility 決定了 symbol definition 在 link 時對其他檔案是否可見。上面說的 local symbol 對外不可見，global symbol 對外可見。
global symbol 裡又分為兩類：normal & private external。如果是 private external（對應 Mach-O 中 <code>N_PEXT</code> 字段） ，static linker 會在輸出中把該 symbol 轉為 local symbol。可以了解為該 symbol definition 隻在這一次 link 過程中對外可見，後續 link 的産物如果要被二次 link，就對外不可見了（展現了 private 的性質）
一個 symbol 是否是 「private external」可以在源碼和編譯期用 <code>__attribute__((visibility("xxx")))</code> 來辨別，可選值為 <code>default</code>（normal）、<code>hidden</code>（private external）
不指定 <code>__attribute__((visibility("xxx")))</code> 的，預設為 <code>default</code>
<code>-fvisibility</code> 可以修改預設 visibility (gcc、clang 都支援)
指定 <code>__attribute__((visibility("xxx")))</code> 的，visibility 為 <code>xxx</code>
舉例：
不指定 <code>-fvisibility</code>：
<code>-fvisibility=hidden</code>：
symbol definition 中還有 strong / weak 之分：當 static linker 發現多個 name 相同的 symbol definition 時，會根據 strong/weak 類型執行以下合并政策：
有多個 strong => 非法輸入，abort
有且僅有一個 strong => 取該 strong
有多個 weak，沒有 strong => 取第一個 weak
symbol definition 預設情況基本都是 strong，可以在源碼中通過 <code>__attribute__((weak))</code> 、<code>#pragma weak</code> 标記 weak 屬性，看一個例子：
生成的 <code>main.o</code> 中該函數對應的 symbol table entry 被标記為了 <code>N_WEAK_DEF</code>，static linker 據此來區分 strong / weak：
執行後輸出：
要注意的是，分析最終輸出使用了哪個 symbol definition 需要結合實際情況。比如某個 strong symbol 封裝在靜态庫中，始終沒有被 static linker 加載，而同名的 weak symbol 已經被加載了，上述（2）的政策就應當變成（3）了。（關于靜态庫中 symbol 的加載機制見後文）
symbol definition 還可能是 tentative definition（或者叫 common definition）。這個其實也很常見，比如：
這樣一個未初始化的全局變量就是一個 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 為「未初始化的全局變量定義」。結合更多的例子來了解：
tentative definition 在 Mach-O 中屬于 <code>__DATA,__common</code> 這個 section。
compiler 無法在編譯期确定所有 symbol 的位址（如對外部函數的調用），是以會在 Mach-O 對應的位置“留白”、并生成一條對應的 Relocation Entry。static linker 在連結期通過 Relocation Entry 知曉每個 section 中哪些位置需要被 relocate、如何 relocate。
Load Command 中的 <code>LC_SEGMENT_64</code> 描述了各個 section 對應的 Relocation Entries 的數量、偏移量：
Mach-O 中用 <code>relocation_info</code> 表示一條 Relocation Entry：
<code>r_address</code> ：從該 section 頭開始偏移多少位置的内容需要 relocate
<code>r_extern</code> & <code>r_symbolnum</code>
<code>r_extern</code> 為 1 表示從 symbol table 的第 <code>r_symbolnum</code> 個 symbol 讀取資訊
<code>r_extern</code> 為 0 表示從第 <code>r_symbolnum</code> 個 section 讀取資訊
<code>r_type</code> ：relocation 的類型，如 <code>X86_64_RELOC_BRANCH</code> 表示 relocate 的是 <code>CALL/JMP</code> 指令的内容
字段明細可參考文檔 https://github.com/aidansteele/osx-abi-macho-file-format-reference#relocation_info。
ld64 是一種 atom-based linker，atom 是其執行處理的基本單元。atom 可以用來表示 symbol，也可以用來表示其他的資訊，如 <code>SectionBoundaryAtom</code>。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 的 <code>N_TYPE</code> 字段得來
regular：大多數 atom 是這種類型
absolute：對應 <code>N_ABS</code>，ld64 不會修改它的值
tentative：<code>N_UNDF</code>，對應上面 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 的類型，總共有幾十種，如 <code>kindStoreX86PCRel32</code>
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，比如調用 <code>printf</code>
indirect
記錄指向 atom indirect table 中某個 index 的指針
非 input file 提供，隻能由 linker 在 link 階段生成，可用于 atom 合并後的 case
看一個簡單的例子：
上面的代碼中 <code>main.m</code> 調用了 <code>Foo.h</code> 定義的全局變量 <code>someGlobalVar</code> 和函數 <code>someGlobalFunction</code>，compiler 生成的 <code>main.o</code> 和 <code>Foo.o</code> 存在以下 symbol：
link 時 ld64 會将其轉換成如下的 atom graph：
其中節點資訊（atom）由 <code>main.o</code> 和 <code>Foo.o</code> 的 symbol table 提供，邊資訊（fixup）由 <code>main.o</code> 的 relocation entries 提供。
如果涉及 ObjC，引用關系會更複雜一些，後文「<code>-ObjC</code> 的由來」一節會詳細展開。
ld64 内部維護了一個 <code>SymbolTable</code> 對象，裡面包含了所有處理過的 symbol，并提供了各種快速查詢的接口。
往 <code>SymbolTable</code> 裡增加 atom 時會觸發合并操作，主要分為兩種
by-name：name 相同的 atom 可以合并為一個，如前面提到的 Strong / Weak & Tentative Definition
by-content：content 相同的 atom 可以合并為一個，如 string constant
<code>SymbolTable</code> 核心的資料結構是 <code>_indirectBindingTable</code>，這東西其實就是個存儲 atom 的數組，每個 atom 都會按解析順序被 append 到這個數組上（如果不被合并的話）。
同時 <code>SymbolTable</code> 還維護了多個 mapping，輔助用于外部根據 name、content、references 查詢某個 atom 的各類需求。
ld64 在 Resolve 階段執行合并、處理 undefined 等操作都是基于該 <code>SymbolTable</code> 來完成。
iOS 工程中一般不會主動觸發 ld64，可以在 Xcode build log 中找到 linking 對應的 clang 指令，複制到 terminal 加上 <code>-v</code> 來輸出 clang 調用的 ld 指令。
ld64 指令的參數形式為：
一個簡單工程的 ld64 參數大緻如下：
其中
<code>-o</code> 指定 output 的路徑
input files 的輸入有幾種方式
直接作為指令行的參數傳入
通過 <code>-filelist</code> 以檔案的形式傳入，該檔案以換行符分隔每一個 input file
通過搜尋路徑
<code>-lxxx</code>，告訴 ld64 去 lib 搜尋路徑找 <code>libxxx.a</code> 或者 <code>libxxx.dylib</code>
lib 搜尋路徑預設是 <code>/usr/lib</code> 和 <code>/usr/local/lib</code>
可以通過 <code>-Lpath/to/your/lib</code> 來增加額外的 lib 搜尋路徑
<code>-framework xxx</code>，告訴 ld64 去 framework 搜尋路徑找 <code>xxx.framework/xxx</code>
framework 搜尋路徑預設是 <code>/Library/Frameworks</code> 和 <code>/System/Library/Frameworks</code>
可以通過 <code>-Fpath/to/your/framework</code> 來增加額外的 framework 搜尋路徑
如果指定了 <code>-syslibroot /path/to/search</code>，會給 lib 和 framework 搜尋路徑都加上 <code>/path/to/search</code> 的字首（如 iOS 模拟器一般會拼上形如 <code>/Applications/Xcode.app/Contents/Developer/Platforms/iPhoneSimulator.platform/Developer/SDKs/iPhoneSimulator14.5.sdk</code> 的路徑）
其他 options
從頂層視角來看，ld64 接收一組 input files 和 options，輸出 executable（注：ld64 也支援 dylib 等其他類型的輸出，下面主要以 executable 為例）
執行邏輯可以分為以下 5 個大階段：
Command line processing
Parsing input files
Resolving
Passes/Optimizations
Generate output file
第一步是解析指令行參數。比較直覺，就是把指令行參數字元串模型化成記憶體中的 <code>Options</code> 對象，便于後續邏輯的讀取。
這一步主要做兩件事：
把指令行裡所有的 input，轉換成 input file paths。上文提到在指令行中為 ld64 指定 input files 的輸入有幾種方式（<code>-filelist</code>、各種搜尋路徑等等的邏輯）都會在這一步轉換解析成實際 input files 的絕對路徑
把其他指令行參數（如 <code>-dead_strip</code>）存到 <code>Options</code> 對應的字段中
具體實作可參考 <code>Options.cpp</code> 中 <code>Options</code> 的構造函數：
第二步是解析 input files。周遊第一步解析出來的 input file paths，從 file system 讀取檔案内容進一步分析轉換成
atom、fixup、sections 等資訊，供 Resolver 後續使用。
上文提到 input files 主要分為 <code>.o</code>、<code>.a</code>、<code>.dylib</code> 三類，ld64 在解析不同類型的檔案時，會調用該檔案對應的 parser 來處理（如 <code>.o</code> 是 <code>mach_o::relocatable::parse</code>），并傳回對應的 <code>ld::File</code> 子類（如 <code>.o</code> 是 <code>ld::relocatable::File</code>），有點工廠模式的味道。
<code>.o</code> 是 ld64 擷取 section 和 atom 資訊的直接來源，是以需要深度地掃描。
<code>mach_o::relocatable::parse</code>
讀取 Header 和 Load Command
<code>LC_SEGMENT_64</code> 提供各個 section 的資訊（位置、大小、relocation 位置、relocation 條目數等）
<code>LC_SYMTAB</code> 提供 symbol table 資訊（位置、大小、條目數）
<code>LC_DYSYMTAB</code> 提供 symbol table 分類統計
local symbol 個數（該檔案定義的 symbol，外部不可見）
global / defined external symbol 個數（該檔案定義的 symbol 且外部可見）
undefined external symbol 個數（外部定義的 symbol）
<code>LC_LINKER_OPTION</code>
Mach-O 中用來辨別 linker option 的 Load Command，linker 會讀取這些 options 作為補充
比如 auto-linking 等特性，就依賴這個 Load Command 來實作（注入類似 <code>-framework UIKit</code> 的參數）
其他資訊如 <code>LC_BUILD_VERSION</code>
對 section 和 symbol 按位址排序：因為 Mach-O 自帶的順序可能是亂的
<code>makeSections</code>：根據 <code>LC_SEGMENT_64</code> 建立 Section 數組，存入 <code>_sectionsArray</code>
處理 <code>__compact_unwind</code> 和 <code>__eh_frame</code>
建立 <code>_atomsArray</code>：周遊 <code>_sectionsArray</code>，把每個 section 的 atom 加入 <code>_atomsArray</code>
<code>makeFixups</code>：建立 fixup
周遊 <code>_sectionsArray</code>，讀取該 section 的 relocation entries
轉換成 <code>FixupInAtom</code>
存入 <code>_allFixups</code> (<code>vector&lt;FixupInAtom&gt;</code>)
解析 <code>.o</code> 的邏輯參考 <code>ld::relocatable::File* Parser&lt;A&gt;::parse</code>。
處理 <code>.a</code> 時一開始隻處理 <code>.a</code> 的 symbol table （<code>.a</code> 的 symbol table 存儲的是 symbol name -> <code>.o</code> offset，僅包含每個 <code>.o</code> 的 global symbols），不需要把内部所有的 <code>.o</code> 挨個解析一遍。Resolver 在 resolve undefined symbol 時會來查找 <code>.a</code> 的 symbol table 并按需懶加載對應的 <code>.o</code>。
<code>archive::Parser&lt;A&gt;::parse</code>
讀取 header 校驗該檔案是否是 <code>.a</code>
讀取 <code>.a</code> symbol table header，擷取 symbol table 條目數
把 symbol table 的映射存到 <code>_hashTable</code> 中
<code>mach_o::dylib::parse</code>
讀取 Header 和 Load Command（和 <code>.o</code> 類似）
<code>LC_SEGMENT_64</code> 、<code>LC_SYMTAB</code> 、<code>LC_DYSYMTAB</code> 等和 <code>.o</code> 類似
<code>LC_DYLD_INFO</code>、 <code>LC_DYLD_INFO_ONLY</code> 提供 dynamic loader info
rebase info
binding info
weak binding info
lazy binding info
export info
其他資訊如 <code>LC_RPATH</code>、<code>LC_VERSION_MIN_IPHONEOS</code>
根據 <code>LC_DYLD_INFO</code>、 <code>LC_DYLD_INFO_ONLY</code>、 <code>LC_DYLD_EXPORTS_TRIE</code> 提供的 symbol 資訊，存入 <code>_atoms</code>
後續外部來查詢該 dylib 是否 export 某個符号時本質上都是查詢 <code>_atoms</code> 。
如果處理的是 <code>.tbd</code>，關鍵是要擷取兩個資訊：
提供哪些 export symbol （如 Foundation 的 <code>_NSLog</code>）
該動态庫還依賴哪些其他動态庫（如 Foundation 依賴 CoreFoundation & libobjc）
ld64 會借助 TAPI（https://opensource.apple.com/source/tapi/tapi-1.30/Readme.md）來 parse <code>.tbd</code> 檔案，parse 完（其實就是調 yaml 解析庫解析了一遍）可以調接口（<code>tapi::LinkerInterfaceFile</code>）直接得到結構化的資訊。
ld64 支援 fat 多架構的 Mach-O 解析。
在 <code>InputFiles::makeFile</code> 中可以看到取出目标架構的邏輯：
值得一提的是，考慮到不同 input files 的解析過程是互相獨立的，ld64 使用 pthread 實作了一個 worker pool 來并發處理 input files（worker 數和 CPU 邏輯核數相同）
pthread 邏輯參考 <code>InputFiles::InputFiles</code> 的構造函數
第三步是調用 <code>Resolver</code> 把 input files 提供的所有 atoms 彙總關聯成 atom graph 并處理，是「連結」的核心子產品。
實作上這裡的邏輯也非常多，挑選核心流程來了解。
這一步負責從解析好的 input files 中提取所有初始的 atom 并加入全局的 <code>SymbolTable</code> 中。
判斷 input file 在 InputFiles::InputFiles 階段是否已經 parse 完
已 parse 完，進行下一步
沒 parse 完，嘗試啟動一個 pthread worker 處理 inputFile（執行邏輯和第一步「解析 Input」裡一樣），并 <code>pthread_cond_wait</code> 等待
parse 階段 ld64 已經從 object file 的 symbol table 和 relocation entries 中抽象出了 <code>_atoms</code>，這一步挨個處理即可。
<code>Resolver::doAtom</code> 處理單個 atom 的邏輯 ：
<code>SymbolTable::add</code>（僅 global symbol & undefined external symbol，local symbol 不處理）
如果 name 沒出現過，append 到 <code>_indirectBindingTable</code> （定義見「概念鋪墊 — Symbol Table」
如果 name 出現過，考慮 strong / weak 等 symbol definition 沖突解決政策
同步更新幾張輔助 mapping 表 <code>NameToSlot</code>、<code>ContentToSlot</code>、<code>ReferencesToSlot</code>
周遊該 atom 的 fixup，嘗試把 by-name / by-content 的 reference 轉成 by-slot（直接指向對應 <code>_indirectBindingTable</code> 中對應的 atom）
buildAtomList 階段理論上完全不需要處理靜态庫，因為隻有在後面 resolve undefined symbol 時才有可能查詢靜态庫裡包含的 symbol。但在以下兩種情況下，這一步需要對靜态庫内的 <code>.o</code> 展開處理：
如果該 <code>.a</code> 受 <code>-all_load</code> 或 <code>-force_load</code> 影響，強制 load 所有 <code>.o</code>
如果 ld64 開啟了 <code>-ObjC</code>，強制 load 所有包含 ObjC class 和 category 的 <code>.o</code>（symbol name 包含 <code>_OBJC_CLASS_</code> 、<code>.objc_c</code>）
load 過程和前面提到的 object file 的 parse & 加載 atoms 一樣。
靜态庫 File 對象内部還會維護一個 MemberToStateMap，來記錄 <code>.o</code> 的 load 狀态
buildAtomList 階段不 add 動态庫的 atoms，但會做一些額外的處理和校驗，包括 bitcode bundle（<code>__LLVM, __bundle</code>）、 Swift framework 依賴檢查、Swift 版本檢查等。
此時 <code>SymbolTable</code> 中已經收集了 input files 中的大部分 atom，下一步需要把其中歸屬不明的 symbol 引用關聯到對應的 symbol 定義上去。
周遊 <code>SymbolTable</code> 中 undefined symbol （被 reference 的但是沒有對應 atom 實體的 symbol definition）
對每一個 undefined symbol ，嘗試去靜态庫 & 動态庫裡找
靜态庫：前面提到靜态庫維護了一個 symbol name -> <code>.o</code> offset 的 mapping，是以要判斷某個 symbol definition 是否屬于該靜态庫隻需要去這個 mapping 裡查即可。如果查找到了，則解析對應的 <code>.o</code>、并把該 <code>.o</code> 的 atoms 加入 <code>SymbolTable</code> 中（<code>.o</code> 的加載邏輯參考前文 Parsing input files 和 buildAtomList）
動态庫：如果比對到了某個動态庫的 exported symbol，ld64 會為該 undefined atom 建立一個 proxy atom 表示對動态庫中的引用。
如果靜态庫 & 動态庫裡都沒找到，判斷是否是 <code>section$</code>、<code>segment$</code> 等 boundary atoms，并手動建立對應的 symbol definition
處理 tentative symbol
如果 <code>-undefined</code> 不是 error（指令行參數控制發現 undefined symbol 時不報錯）、或者命中了 <code>-U</code>（參數控制某些 undefined symbol 不報錯），那麼 ld64 會手動建立一個 <code>UndefinedProxyAtom</code> 作為其 symbol definition
由于搜尋靜态庫和動态庫的過程中有可能引入新的 undefined symbol，是以一次周遊結束後需要判斷該條件并按需重新周遊。
接下來執行開啟了 <code>-dead_strip</code> 後的邏輯。此時所有的 atom 和它們之間的引用關系已經記錄在了 <code>SymbolTable</code> 中，可以把所有的 atom 抽象成 atom graph 來移除沒有被引用到的無用 atom。
初始化 root atoms
entry point atom（如 <code>_main</code>）
所有被 <code>-u</code>（強制加載某個 symbol，即使在靜态庫中）、<code>-exported_symbols_list</code>、<code>-exported_symbol</code>(在 output 中作為 global symbol 輸出） 命中的 atoms
dyld 相關的幾個 stub atom
所有被标記為 dont-dead-strip 的 atom（該 atom 對應的 section 在 <code>.o</code> 中被标記為了 <code>S_ATTR_NO_DEAD_STRIP</code>）
從 root atoms 開始通過 fixup 周遊 atom graph，把它們能周遊到的 atoms 都标記為 live
移除 dead atom
周遊一遍 atoms，移除所有被合并的 atom。
（Symbol 的合并參考「概念鋪墊 — Symbol」）
周遊一遍 atoms，把它們按照所屬的 section 歸類存放。
至此，我們已經擁有了寫 output 所需要的完整的、有關聯的資訊了（sections & 對應的 atoms）。在輸出之前，還需要執行多輪的「Pass」。一個 Pass 對應實作某一特定特性的代碼邏輯，如
<code>ld::passes::objc</code>
<code>ld::passes::stubs</code>
<code>ld::passes::dylibs</code>
<code>ld::passes::dedup::doPass</code>
...
pass 依次執行，個别 pass 之間也會強制要求執行的先後順序以保證輸出的正确性。
每個工程可以結合實際需求調整要執行的 pass。
最後一步是輸出 output files。ld64 的輸出包括主 output 檔案和其他輔助輸出如 link map、dependency info 等。
在正式輸出前，ld64 還執行了一些其他操作，包括：
<code>synthesizeDebugNotes</code>
<code>buildSymbolTable</code>
<code>generateLinkEditInfo</code>
<code>buildChainedFixupInfo</code>
其中 <code>buildSymbolTable</code> 負責建構 output file 中的 symbol table。「概念鋪墊 — Symbol」中提到每個 symbol 在 link 階段有自己的 visibility，用來控制 link 時對其他檔案的可見性。同理，在 link 結束後輸出的 Mach-O 中這些 symbol 現在隸屬于一個新的檔案，此時它們的 visibility 要被 ld64 依據各種處理政策來重新調整：
前文提到的被标記為 private extern 的 symbol，這一步被轉換為 local symbol
ld64 也提供了多種參數來控制這一行為，如 <code>-reexport-lx</code>、<code>-reexport_library</code>、<code>-reexport_framework</code>（指定 lib 的 global symbol 在 output 中繼續為 global）、<code>-hidden-lx</code>（指定 lib 中的 symbol 在 output 中轉為 hidden）
上述操作都忙完後，ld64 就會拿着 <code>FinalSection</code> 數組愉快地去寫 output file 了，大緻邏輯如下：
開辟一塊記憶體，維護一個目前寫入位置的 offset 指針
周遊 <code>FinalSection</code> 數組
周遊 atoms
如果是動态庫建立的 proxy atom，跳過（不占用輸出檔案的空間）
把 atom content 寫入目前 offset
周遊 fixups（<code>applyFixUps</code>），根據 fixup 的類型修正 atom content 對應位置的内容
auto linking 是一種不用主動聲明 <code>-l</code>、 <code>-framework</code> 等 lib 依賴也能讓 linker 正常工作的機制。
比如：
某個源檔案聲明依賴了 <code>#import &lt;AppKit/AppKit.h&gt;</code>
link 時不指定 <code>-framework AppKit</code>
編譯生成的 <code>.o</code> 的 <code>LC_LINKER_OPTION</code> 中帶有 <code>-framework AppKit</code>
又或者：
某個源檔案聲明了 <code>#import &lt;zlib.h&gt;</code>
<code>/usr/include/module.modulemap</code> 内容
link 時不指定 <code>-lz</code>
編譯生成的 <code>.o</code> 的 <code>LC_LINKER_OPTION</code> 中帶有 <code>-lz</code>
實作原理：compiler 編譯 <code>.o</code> 時，解析 import，把依賴的 framework 寫入最後 Mach-O 裡的 <code>LC_LINKER_OPTION</code> （存儲了對應的 <code>-framework XXX</code> 資訊）
要注意的是，開啟 Clang module 時（<code>-fmodules</code>）自動開啟 auto linking 。可以用 <code>-fno-autolink</code> 主動關閉。
前面提到開啟了 <code>-ObjC</code> 後，ld64 會在解析符号 search lib 時強制加載每個靜态庫内包含 ObjC class 和 category 的 <code>.o</code>。這麼做的原因是什麼呢？
經試驗可發現：
ObjC 的 class 定義對應 symbol 的 visibility 為 <code>global</code>（自己定義、link 時外部檔案可見）
ObjC 的 class 調用對應 symbol 的 visibility 為 <code>undefined external</code>（外部定義、需要 link 時 fixup）
ObjC 的 method 定義對應 symbol 的 visibility 為 <code>local</code>（對外部不可見）
ObjC 的 method 調用不會生成 symbol
假設現在有兩個類 <code>ClassA</code> & <code>ClassB</code> ：
編譯後，<code>ClassA.o</code>：
global symbol：...
local symbol：...
undefined external symbol：<code>_OBJC_CLASS_$_ClassB</code>
<code>ClassB.o</code>：
global symbol： <code>_OBJC_CLASS_$_ClassB</code>
local symbol：<code>-[ClassB methodB]</code>
undefined external：...
雖然 ClassA 調用了 ClassB 的方法，但 Class A 生成的 object file 的 symbol table 中隻有 <code>_OBJC_CLASS_$_ClassB</code> 這個對 ClassB 類本身的 reference，根本沒有 <code>-[ClassB methodB]</code>。這樣的話，按照 ld64 正常的解析邏輯，既不會因為 <code>ClassA</code> 中對 <code>methodB</code> 的調用去尋找 <code>ClassB.m</code> 的定義（壓根沒有生成 <code>undefined external</code>）、即使想找，<code>ClassB</code> 也沒有暴露這個 method 的 symbol （local symbol 對外部檔案不可見）。
既然如此，ObjC 的 method 定義為什麼不會被 ld64 認為是 dead code 而 strip 掉呢？
其實是因為 ObjC 的 class 定義會間接引用到它的 method 定義。比如上面 <code>ClassB</code> 的例子中，atom 之間的依賴關系如下：
<code>_OBJC_CLASS_$_ClassB</code> -> <code>__OBJC_CLASS_RO_$_ClassB</code> ->
<code>__OBJC_$_INSTANCE_METHODS_ClassB</code> -> <code>-[ClassB methodB]</code>
隻要這個 class 定義被引用了，那麼它的所有 method 定義也會被一起認為是 live code 而保留下來。
再看看引入 Category 後的情況：
假設 B 定義了 <code>ClassB</code> 和 <code>methodB</code>
C 是 B 的 category，定義了 <code>ClassB</code> 的 <code>methodBFromCategory</code>
A 引用了 <code>ClassB</code> 和 <code>methodB</code> 、<code>methodBFromCategory</code>
這種情況下：
因為 A 引用了 B 的 ClassB，是以 B 要被 ld64 加載。
雖然 A 引用了 C 的 <code>methodBFromCategory</code>，但 A 沒有解析 <code>methodBFromCategory</code> 這個符号的需求（沒生成），是以 ld64 不需要加載 C。
為了讓程式能正确執行，C 的 <code>methodBFromCategory</code> 定義必須被 ld64 link 進來。這裡需要分兩種情況：
如果 C 在主工程中，ld64 需要直接解析 C 生成的 object file，并生成如下 atom 依賴：
<code>objc-cat-list</code> -> <code>__OBJC_$_CATEGORY_ClassB_$_SomeCategory</code>
-> <code>__OBJC_$_CATEGORY_INSTANCE_METHODS_ClassB_$_SomeCategory</code> ->
<code>-[ClassB(SomeCategory) methodBFromCategory]</code>
其中 <code>objc-cat-list</code> 表示所有 ObjC 的 categories，在 dead code strip 初始階段被标記為 live，是以 <code>methodBFromCategory</code> 會被 link 進 executable 而不被裁剪。
如果 C 被封裝在一個靜态庫裡，link 時 ld64 沒有動機去加載 C，<code>methodBFromCategory</code> 沒有被 link 進 executable，導緻最終運作時 <code>ClassB</code> 沒有加載該 category、執行時錯誤。
是以才有了 <code>-ObjC</code> 這個開關，保證靜态庫中單獨定義的 ObjC category 被 link 進最終的 output 中。
現在的 Xcode 中一般預設都開啟了 <code>-ObjC</code>，但這種為了相容 category 而暴力加載靜态庫中所有 ObjC class 和 category 的實作并不是最完美的方案，因為可能是以在 link 階段加載了許多本不需要加載的 ObjC class。理論上我們可以通過人為在 category 定義和引用之間建立引用關系來讓 ld64 在不開啟 <code>-ObjC</code> 的情況下也能加載 category，比如 IGListKit 就曾嘗試手動注入一些 weak 的 dummy 變量（PR https://github.com/Instagram/IGListKit/pull/957） ，但這種做法為了不劣化也會帶來一定維護成本，是以也需要權衡。
ld64 中對 <code>-ObjC</code> 的處理可參考 <code>src/ld/parsers/archive_file.cpp</code>：
ld64 也提供了豐富的參數供開發者查詢其執行過程，可以在 mac 上通過 <code>man ld</code> 檢視 Options for introspecting the linker 一欄
列印 ld64 各大步驟的耗時分布。
列印 ld64 加載的每一個 <code>.o</code> <code>.a</code> <code>.dylib</code>。
列印 <code>.a</code> 中 <code>.o</code> 被加載的原因（即什麼 symbol 被需要）。
列印開啟 <code>-dead_strip</code> 後，某個 symbol 的 reference chain（即不被 strip 的原因）
比如 <code>-why_live _OBJC_CLASS_$_TTNewUserHelper</code>：
輸出 linkmap 到指定路徑，包含所有 symbols 和對應位址的 map 。
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等各終端都有深入研究。
就是現在！用戶端／前端／服務端／端智能算法／測試開發 面向全球範圍招聘！一起來用技術改變世界，感興趣請聯系 [email protected]，郵件主題 履歷-姓名-求職意向-期望城市-電話。
火山引擎應用開發套件MARS是位元組跳動終端技術團隊過去九年在抖音、今日頭條、西瓜視訊、飛書、懂車帝等 App 的研發實踐成果，面向移動研發、前端開發、QA、 運維、産品經理、項目經理以及營運角色，提供一站式整體研發解決方案，助力企業研發模式更新，降低企業研發綜合成本。