深入理解計算機系統(tǒng)——鏈接

之前在筆記里面總結(jié)的踢故，發(fā)一下。

鏈接

本文參考《深入理解計算機系統(tǒng)》

前言

當(dāng)我們點擊Xcode的運行按鈕時廓潜，你會注意到在界面頂端的提示欄上會出現(xiàn)“Building”的字樣阱佛，緊接著會出現(xiàn)“Linking”的字樣，我們知道Building是編譯過程耍缴，那這個Linking（鏈接）是什么過程呢砾肺？本文將對鏈接過程做一個講解，了解鏈接的過程防嗡，可以幫助你理解計算機系統(tǒng)的底層原理变汪，并解答你平時關(guān)于計算機怎樣識別并執(zhí)行程序的一些疑惑。另外蚁趁，本文也是后續(xù)篇章的基礎(chǔ)疫衩，我們會由鏈接的知識延展出Mach-O文件、fishhook原理以及hook objc_msgSend的知識講解荣德。

鏈接的基本概念

鏈接（linking）是將各種代碼和數(shù)據(jù)片段收集并組合成為一個單一文件的過程闷煤，這個文件可被加載（復(fù)制）到內(nèi)存并執(zhí)行。

鏈接可以執(zhí)行與編譯時（complie time）涮瞻，也就是源代碼被翻譯成機器代碼時鲤拿；也可以執(zhí)行于加載時（load time），也就是在程序被加載器（load-er）加載到內(nèi)存并執(zhí)行時署咽；甚至可以執(zhí)行在運行時（run time）近顷，也就是由應(yīng)用程序來執(zhí)行。在早期的計算機系統(tǒng)中宁否，鏈接是手動執(zhí)行的窒升。在現(xiàn)代系統(tǒng)中，鏈接是由叫做連接器（linker）的程序自動執(zhí)行的慕匠。

鏈接的作用

鏈接器使分離編譯成為可能饱须，我們不用將一個大型的應(yīng)用程序組織為一個巨大的源文件，而是可以把它分解為更小台谊、更好管理的模塊蓉媳，可以獨立地修改和編譯這些模塊。當(dāng)我們改變這些模塊中的一個時锅铅，只需簡單地重新編譯它酪呻，并重新鏈接應(yīng)用，而不必重新編譯其它文件盐须。

下面的討論基于這樣的環(huán)境：一個運行Linux的x86-64系統(tǒng)玩荠，使用標(biāo)準(zhǔn)的ELF-64目標(biāo)文件格式。

編譯器驅(qū)動程序

下面的C語言示例程序，由兩個源文件組成阶冈，main.c和sum.c屉凯。main函數(shù)初始化一個整數(shù)數(shù)組，然后調(diào)用sum函數(shù)來對數(shù)組元素求和眼溶。

// sum.c

int sum(int *a, int n) {
    int s = 0;
    for (int i = 0; i < n; i++) {
        s += a[i];
    }
    return s;
}

// main.c

int array[2] = {1, 2};

int main() {
    int val = sum(array, 2);
    return val;
}

大多數(shù)的編譯系統(tǒng)會提供編譯器驅(qū)動程序（compile driver）悠砚，包含語言預(yù)處理器、編譯器堂飞、匯編器和鏈接器灌旧。首先編譯器驅(qū)動程序會對main.c與sum.c文件的源代碼進(jìn)行翻譯，翻譯過程如下：

image

其中绰筛，main.o稱為可重定位目標(biāo)文件枢泰。

之后，編譯系統(tǒng)會運行鏈接器ld铝噩，將main.o和sum.o以及一些必要的系統(tǒng)目標(biāo)文件組合起來衡蚂，創(chuàng)建一個可以執(zhí)行目標(biāo)文件，這個過程是靜態(tài)鏈接骏庸，過程如下：

image

再之后毛甲，操作系統(tǒng)會調(diào)用加載器（loader），將可執(zhí)行文件prog中的代碼和數(shù)據(jù)復(fù)制到內(nèi)存中具被，然后執(zhí)行玻募。

靜態(tài)鏈接

靜態(tài)鏈接器（static linker）以一組可重定位目標(biāo)文件作為輸入，生成一個完全鏈接的一姿、可以加載和運行的可執(zhí)行目標(biāo)文件七咧。輸入的可重定位目標(biāo)文件由各種不同的代碼和數(shù)據(jù)節(jié)（section）組成，每一節(jié)都是一個連續(xù)的字節(jié)序列叮叹。指令在一節(jié)中艾栋，初始化了的全局變量在另一個節(jié)中，而未初始化的變量又在另外一節(jié)中蛉顽。

為了構(gòu)造可執(zhí)行文件蝗砾，鏈接器必須完成兩個重要的任務(wù)：

符號解析（symbol resolution）。目標(biāo)文件定義和引用符號蜂林，一個個符號對應(yīng)一個函數(shù)或一個全局變量或一個靜態(tài)變量（即C語言中以static屬性聲明的變量）遥诉。符號解析的目的是將每個符號引用正好和一個符號定義關(guān)聯(lián)起來。
重定位（relocation）噪叙。編譯器和匯編器生成從地址0開始的代碼和數(shù)據(jù)節(jié)。鏈接器通過把每個符號定義與一個內(nèi)存位置關(guān)聯(lián)起來霉翔，從而重定位這些節(jié)睁蕾，然后修改所有對這些符號的引用，使它們指向這個內(nèi)存位置。

目標(biāo)文件純粹是字節(jié)塊的集合子眶，這些塊中瀑凝，有些包含程序代碼，有些包含數(shù)據(jù)臭杰，而有些則是引導(dǎo)鏈接器和加載器的數(shù)據(jù)結(jié)構(gòu)粤咪。鏈接器將這些塊連接起來，確定被連接塊的運行時位置渴杆，并且修改代碼和數(shù)據(jù)塊中的各種位置寥枝。

目標(biāo)文件

目標(biāo)文件有三種形式：

可重定位目標(biāo)文件。包含二進(jìn)制代碼和數(shù)據(jù)磁奖，其形式可以在編譯時與其他可重定位目標(biāo)文件合并起來囊拜，創(chuàng)建一個可執(zhí)行目標(biāo)文件。
可執(zhí)行目標(biāo)文件比搭。包含二進(jìn)制代碼和數(shù)據(jù)冠跷，其形式可以被直接復(fù)制到內(nèi)存并執(zhí)行。
共享目標(biāo)文件身诺。一種特殊類型的可重定位目標(biāo)文件蜜托，可以在加載或者運行時被動態(tài)的加載進(jìn)內(nèi)存并鏈接。動態(tài)庫就是這種形式的霉赡。

目標(biāo)文件的生成方式：

編譯器和匯編器生成可重定位目標(biāo)文件（包括共享目標(biāo)文件）盗冷。
鏈接器生成可執(zhí)行目標(biāo)文件。

目標(biāo)文件的格式：

在iOS和MacOS-X中同廉，目標(biāo)文件的格式是Mach-O格式仪糖。
X86-64 Linux和Unix系統(tǒng)使用可執(zhí)行可連接格式ELF。

可重定位目標(biāo)文件

image.png

下上展示了一個典型的ELF可重定位目標(biāo)文件的格式迫肖。ELF頭包含很多信息锅劝，包括生成該文件的系統(tǒng)的字節(jié)大小，字節(jié)順序蟆湖，ELF頭的大小故爵，目標(biāo)文件的類型，機器類型等等隅津。節(jié)頭部表描述了不同節(jié)的位置和大小诬垂。

加載ELF頭和節(jié)頭部表的是節(jié):

.text：已編譯程序的機器代碼。
.rodata：只讀數(shù)據(jù)伦仍，比如 printf語句中的格式串和開關(guān)語句的跳轉(zhuǎn)表结窘。
.data：已初始化的全局和靜態(tài)C變量。局部C變量在運行時被保存在棧中充蓝，既不出現(xiàn)在隧枫，data節(jié)中喉磁，也不出現(xiàn)在.bss節(jié)中
.bss：未初始化的全局和靜態(tài)C變量，以及所有被初始化為0的全局或靜態(tài)變量官脓。在目標(biāo)文件中這個節(jié)不占據(jù)實際的空間协怒，它僅僅是一個占位符。目標(biāo)文件格式區(qū)分已初始化和未初始化變量是為了空間效率：在目標(biāo)文件中卑笨，未初始化變量不需要占據(jù)任何實際的磁盤空間孕暇。運行時，在內(nèi)存中分配這些變量赤兴，初始值為0妖滔。
.symtab：一個符號表，它存放在程序中定義和引用的函數(shù)和全局變量的信息搀缠。一些程序員錯誤地認(rèn)為必須通過-g選項來編譯一個程序铛楣，才能得到符號表信息。實際上艺普，每個可重定位目標(biāo)文件在. symtab中都有一張符號表（除非程序員特意用 STRIP命令去掉它）簸州。然而，和編譯器中的符號表不同歧譬， symtab符號表不包含局部變量的條目岸浑。
.rel.text：一個.text節(jié)中位置的列表，當(dāng)鏈接器把這個目標(biāo)文件和其他文件組合時瑰步，需要修改這些位置矢洲。一般而言，任何調(diào)用外部函數(shù)或者引用全局變量的指令都需要修改缩焦。另一方面读虏，調(diào)用本地函數(shù)的指令則不需要修改。注意袁滥，可執(zhí)行目標(biāo)文件中并不需要重定位信息盖桥，因此通常省略，除非用戶顯式地指示鏈接器包含這些信息题翻。
.rel.data：被模塊引用或定義的所有全局變量的重定位信息揩徊。一般而言，任何已初始化的全局變量嵌赠，如果它的初始值是一個全局變量地址或者外部定義函數(shù)的地址塑荒，都需要被修改。
.debug：一個調(diào)試符號表姜挺，其條目是程序中定義的局部變量和類型定義齿税，程序中定義和引用的全局變量，以及原始的C源文件初家。只有以-g選項調(diào)用編譯器驅(qū)動程序時偎窘，才會得到這張表乌助。
.line：原始C源程序中的行號和.text節(jié)中機器指令之間的映射溜在。只有以-g選項調(diào)用編譯器驅(qū)動程序時陌知，才會得到這張表。
.strtab：一個字符串表掖肋，其內(nèi)容包括. symtab和仆葡， debug節(jié)中的符號表，以及節(jié)頭部中的節(jié)名字志笼。字符串表就是以nu11結(jié)尾的字符串的序列沿盅。

符號和符號表

每個可重定位目標(biāo)模塊（目標(biāo)文件）m都有一個符號表，它包含m定義和引用的符號的信息纫溃。在鏈接器的上下文中腰涧，有三種不同的符號：

由模塊m定義并能被其它模塊引用的全局符號。這些符號對應(yīng)于非靜態(tài)的C函數(shù)和全局變量紊浩。
由其它模塊定義并被模塊m引用的全局符號窖铡。這些符號稱為外部符號，對應(yīng)于在其它模塊中定義的非靜態(tài)C函數(shù)和全局變量坊谁。
只被模塊m定義和引用的局部符號费彼。它們對應(yīng)于帶static屬性的C函數(shù)和全局變量。這些符號在模塊m中任何位置都可見口芍，但是不能被其它模塊引用箍铲。

.symtab中的符號表不包含非靜態(tài)程序變量的任何符號，這些程序變量符號在棧中被管理鬓椭，鏈接器對此類符號不感興趣颠猴。

如何解析多重定義的全局符號

鏈接器的輸入是一組可重定位目標(biāo)模塊。每個模塊定義一組符號小染，有些是局部的（只對定義該符號的模塊可見）翘瓮，有些是全局的（對其他模塊也可見）。如果多個模塊定義同名的全局符號氧映，會發(fā)生什么呢春畔？下面是 Linux編譯系統(tǒng)采用的方法。

在編譯時岛都，編譯器向匯編器輸出每個全局符號律姨，或者是強（ strong）或者是弱（weak），而匯編器把這個信息隱含地編碼在可重定位目標(biāo)文件的符號表里臼疫。函數(shù)和已初始化的全局變量是強符號择份，未初始化的全局變量是弱符號。

根據(jù)強弱符號的定義烫堤，Linux鏈接器使用下面的規(guī)則來處理多重定義的符號名

規(guī)則1：不允許有多個同名的強符號荣赶。
規(guī)則2：如果有一個強符號和多個弱符號同名凤价，那么選擇強符號。
規(guī)則3：如果有多個弱符號同名拔创，那么從這些弱符號中任意選擇一個利诺。

靜態(tài)庫

迄今為止，我們都是假設(shè)鏈接器讀取一組可重定位目標(biāo)文件剩燥，并把它們鏈接起來慢逾，輸出一個可執(zhí)行目標(biāo)文件。實際上灭红，所有的編譯系統(tǒng)都提供一種機制侣滩，將所有相關(guān)的目標(biāo)模塊打包成一個單獨的文件，稱為靜態(tài)庫变擒。靜態(tài)庫可以用做鏈接器的輸入君珠，當(dāng)鏈接器構(gòu)造一個輸出的可執(zhí)行目標(biāo)文件時，它只復(fù)制靜態(tài)庫里被應(yīng)用程序引用的目標(biāo)模塊娇斑，這就減少了可執(zhí)行文件在磁盤和內(nèi)存中的大小策添。在Linux系統(tǒng)中，靜態(tài)庫由后綴.a標(biāo)識悠菜。

重定位

一旦鏈接器完成了符號解析這一步舰攒，就把代碼中的每個符號引用和正好一個符號定義（即它的一個輸入目標(biāo)模塊中的一個符號表條目）關(guān)聯(lián)起來。此時悔醋，鏈接器就知道它的輸入目標(biāo)模塊中的代碼節(jié)和數(shù)據(jù)節(jié)的確切大小∧η裕現(xiàn)在就可以開始重定位步驟了，在這個步驟中芬骄，將合并輸入模塊猾愿，并為每個符號分配運行時地址。重定位由兩步組成：

重定位節(jié)和符號定義账阻。在這一步中蒂秘，鏈接器將所有相同類型的節(jié)合并為同一類型的新的聚合節(jié)。例如淘太，來自所有輸入模塊的.data節(jié)被全部合并成一個節(jié)姻僧，這個節(jié)成為輸出的可執(zhí)行目標(biāo)文件的.data節(jié)。然后蒲牧，鏈接器將運行時內(nèi)存地址賦給新的聚合節(jié)撇贺，賦給輸人模塊定義的每個節(jié)，以及賦給輸人模塊定義的每個符號冰抢。當(dāng)這一步完成時松嘶，程序中的每條指令和全局變量都有唯一的運行時內(nèi)存地址了。
重定位節(jié)中的符號引用挎扰。在這一步中翠订，鏈接器修改代碼節(jié)和數(shù)據(jù)節(jié)中對每個符號的引用巢音，使得它們指向正確的運行時地址。要執(zhí)行這一步尽超，鏈接器依賴于可重定位目標(biāo)模塊中稱為重定位條目（relocation entry）的數(shù)據(jù)結(jié)構(gòu)官撼。

當(dāng)匯編器生成一個目標(biāo)模塊時，它并不知道數(shù)據(jù)和代碼最終將放在內(nèi)存中的什么位置橙弱，它也并不知道這個模塊引用的任何外部定義的函數(shù)或者全局變量的位置歧寺。所以燥狰，無論何時匯編器遇到對最終位置的目標(biāo)引用棘脐，它就會生成一個重定位條目，告訴鏈接器在將目標(biāo)文件合并成可執(zhí)行目標(biāo)文件時如何修改這個引用龙致。

可執(zhí)行目標(biāo)文件與加載可執(zhí)行目標(biāo)文件

見《深入理解計算機系統(tǒng)》

動態(tài)鏈接共享庫

靜態(tài)庫由一些缺點：靜態(tài)庫需要定期維護和更新蛀缝；每個程序都會使用一些通用的標(biāo)準(zhǔn)函數(shù)，在運行時目代，這些函數(shù)的代碼會被復(fù)制到每個運行進(jìn)程的文本段中屈梁，在一個運行上百個進(jìn)行的典型系統(tǒng)上，這是對內(nèi)存資源的浪費榛了。

共享庫（shared library）是致力于解決靜態(tài)庫缺陷的一個現(xiàn)代創(chuàng)新產(chǎn)物在讶。共享庫是一個目標(biāo)模塊，在運行或加載時霜大，可以加載到任意內(nèi)存地址构哺，并和一個在內(nèi)存中的程序鏈接起來。這個過程稱為動態(tài)鏈接战坤，是由一個叫做動態(tài)鏈接器（dynamic linker）的程序來執(zhí)行的曙强。在Linux系統(tǒng)中，共享庫通常由.so后綴標(biāo)識途茫。

共享庫以兩種不同的方式來共享的碟嘴。首先，在任何給定的文件系統(tǒng)中囊卜，對于一個庫只有一個.so文件娜扇。所有引用該哭的可執(zhí)行目標(biāo)文件共享這個.so文件中的代碼和數(shù)據(jù)，而不是像靜態(tài)庫的內(nèi)容那樣被復(fù)制和嵌入到引用它們的可執(zhí)行文件中栅组。其次雀瓢，在內(nèi)存中，一個共享庫的.text節(jié)的一個副本可以被不同的正在運行的進(jìn)程共享笑窜。