原文鏈接

通過前面對ELF文件結構的詳細介紹，我們對ELF目標文件從整體輪廓到局部細節(jié)都有了一定的了解跃赚。那么接下來笆搓，當我們有多個目標文件時，如何將它們鏈接起來形成一個可執(zhí)行文件呢纬傲？一切都要從鏈接說起满败。

鏈接概述

模塊化設計是軟件開發(fā)中最常用的設計思想。鏈接（Linking） 本質上就是把各個模塊之間相互引用的部分處理好叹括，使得各個模塊之間能夠正確銜接算墨。比如：

我們在模塊main.c中使用另一個模塊func.c中的foo()函數(shù)。我們在main.c模塊中每一處調用foo時都必須確切知道foo函數(shù)的地址汁雷。但由于每個模塊都是單獨編譯的米同。編譯器在編譯main.c的時候并不知道foo函數(shù)的地址。所以編譯器會暫時把這些調用foo的指令的目標地址擱置摔竿，等待最后鏈接時由鏈接器將這些指令的目標地址修正面粮。這就是靜態(tài)鏈接最基本的過程和作用。

如下圖所示為最基本的靜態(tài)鏈接過程示意圖继低。每個模塊的源代碼文件（如.c）文件經(jīng)過編譯器編譯成目標文件（Object File熬苍，一般擴展名為.o或.obj）。目標文件和 庫（Library） 一起鏈接形成最終的可執(zhí)行文件袁翁。

其中柴底，最常見的庫就是運行時庫（Runtime Library），它是支持程序運行的基本函數(shù)的集合粱胜。庫本質上是一組目標文件的包柄驻，由一些最常用的代碼編譯成目標文件后打包而成。

image

鏈接過程主要包含了三個步驟：

1. 地址與空間分配（Address and Storage Allocation）
2. 符號解析（Symbol Resolution）
3. 重定位（Relocation）

下面焙压，我們以兩個源代碼文件a.c和b.c為例展開分析鸿脓。

// a.c
extern int shared;

int main() {
    int a = 100;
    swap(&a, &shared);
}

// b.c
int shared = 1;

void swap(int *a, int *b) {
    *a ^= *b ^= *a ^= *b;
}

其中抑钟，b.c中定義了兩個全局符號：變量shared、函數(shù)swap野哭；a.c中定義了一個全局符號：main在塔。a.c引用了b.c中的swap和shared。接下來我們要將兩個目標文件鏈接在一起并最終形成一個執(zhí)行程文件ab拨黔。

使用gcc -c命令我們可以分別編譯得到a.o和b.o兩個目標文件蛔溃。

地址與空間分配

在介紹ELF文件結構關于段與節(jié)的區(qū)別時，我們就提到過可執(zhí)行文件中的段是由目標文件中的節(jié)合并而來的篱蝇。那么贺待，我們的第一個問題是：對于多個輸入目標文件，鏈接器如何將它們的各個節(jié)合并到輸出文件呢零截？或者說麸塞，輸出文件中的空間如何分配給輸入文件。

按序疊加

一個最簡單的方案就是將輸入的文件按序疊加瞻润，如下圖所示。

image

雖然這種方法非常簡單甜刻，但是它存在一個問題：在有很多輸入文件的情況下绍撞，輸出文件會有很多零散的節(jié)。這種做法非常浪費空間得院，因為每個節(jié)都需要有一定的地址和空間對齊要求傻铣。x86硬件的對齊要求是4KB。如果一個節(jié)的大小只有1個字節(jié)祥绞，它也要在內存在重用4KB非洲。這樣會造成大量內部碎片。所以不是一個好的方案蜕径。

合并相似節(jié)

一個更加實際的方法便是合并相同性質的節(jié)两踏，比如：將所有輸入文件的 .text節(jié)合并到輸出文件的 text段（注意，此時出現(xiàn)了段和節(jié)兩個概念）兜喻，如下圖所示梦染。

image

其中.bss節(jié)在目標文件和可執(zhí)行文件中不占用文件的空間，但是它在裝載時占用地址空間朴皆。事實上帕识，這里的空間和地址有兩層含義:

1. 在輸出的可執(zhí)行文件中的空間
2. 在裝載后的虛擬地址中的空間

對于有實際數(shù)據(jù)的節(jié)，如.text和.data遂铡，它們在文件中和虛擬地址中都要分配空間肮疗，因為它們在這兩者中都存在；對于.bss來扒接，分配空間的意義只局限于虛擬地址空間伪货，因為它在文件中并沒有內容们衙。我們在這里談到的空間分配只關注于虛擬地址空間的分配，因為這關系到鏈接器后面的關于地址計算的步驟超歌，而可執(zhí)行文件本身的空間分配與鏈接的關系并不大砍艾。

現(xiàn)在的鏈接器空間分配的策略基本上都采用“合并相似節(jié)”的方法，使用這種方法的鏈接器一般采用一種叫 兩步鏈接（Two-pass Linking） 的方法巍举。即整個鏈接過程分為兩步：

• 第一步 地址與空間分配
  掃描所有的輸入目標文件脆荷，獲得它們的各個節(jié)的長度、屬性懊悯、位置蜓谋，并將輸入目標文件中的符號表中所有的符號定義和符號引用收集起來，統(tǒng)一放到一個全局的符號表炭分。這一步桃焕，鏈接器能夠獲得所有輸入目標文件的節(jié)的長度，并將它們合并捧毛，計算出輸出文件中各個節(jié)合并后的長度與位置观堂，并建立映射關系。
• 第二步 符號解析與重定位
  使用前一步中收集到的所有信息呀忧，讀取輸入文件中節(jié)的輸數(shù)據(jù)师痕、重定位信息，并且進行符號解析與重定位而账、調整代碼胰坟、調整代碼中的地址等。事實上泞辐，第二步是鏈接過程的核心笔横，尤其是重定位。

image

在地址與空間分配步驟完成之后咐吼，相似權限的節(jié)會被合并成段吹缔，并生成了ELF文件結構一文中沒有介紹的 程序頭表（Program Header Table） 結構。如下右圖可執(zhí)行文件結構所示锯茄，主要生成兩個段：代碼段（ text段）涛菠、數(shù)據(jù)段（ data段 ）。

image

我們使用ld或gcc將a.o和b.o鏈接起來撇吞，然后使用objdump工具來查看鏈接前后的地址分配情況俗冻。

$ objdump -h a.o

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  0 .text         0000004f  0000000000000000  0000000000000000  00000040  2**0
                  CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE
  1 .data         00000000  0000000000000000  0000000000000000  0000008f  2**0
                  CONTENTS, ALLOC, LOAD, DATA
  2 .bss          00000000  0000000000000000  0000000000000000  0000008f  2**0
                  ALLOC
  ...

$ objdump -h b.o

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  0 .text         0000004b  0000000000000000  0000000000000000  00000040  2**0
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  1 .data         00000004  0000000000000000  0000000000000000  0000008c  2**2
                  CONTENTS, ALLOC, LOAD, DATA
  2 .bss          00000000  0000000000000000  0000000000000000  00000090  2**0
                  ALLOC
  ...

$ objdump -h ab

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  ...
  13 .text         00000202  0000000000400450  0000000000400450  00000450  2**4
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  ...
  24 .data         00000014  0000000000601028  0000000000601028  00001028  2**3
                  CONTENTS, ALLOC, LOAD, DATA
  25 .bss          00000004  000000000060103c  000000000060103c  0000103c  2**0
                  ALLOC
  ...

可以發(fā)現(xiàn)，鏈接前目標文件中所有節(jié)的 VMA（Virtual Memory Address） 都是0牍颈，因為虛擬空間還沒有分配迄薄。鏈接后，可執(zhí)行文件ab中各個節(jié)被分配到了相應的虛擬地址煮岁，如.text節(jié)被分配到了地址0x0000000000400450讥蔽。

那么涣易，為什么鏈接器要將可執(zhí)行文件ab的.text節(jié)分配到0x0000000000400450？而不是從虛擬空間的0地址開始分配呢冶伞？這涉及到操作系統(tǒng)的進程虛擬地址空間的分配規(guī)則新症。在Linux x86-64系統(tǒng)中，代碼段總是從0x0000000000400000開始的响禽，另外.text節(jié)之前還有ELF Header徒爹、Program Header Table、.init等占用了一定的空間芋类，所以就被分配到了0x0000000000400450隆嗅。

符號解析

在兩步鏈接中，這一步和重定位被合并成了一步侯繁，這是因為重定位的過程是伴隨著符號解析的胖喳。這里我們分開介紹。

鏈接器解析符號引用的方法是將每個引用與它輸入的可重定位目標文件的符號表中的一個確定的符號定義關聯(lián)起來贮竟。對那些和引用定義在相同模塊的局部符號的引用丽焊，符號解析是非常簡單的。編譯器只允許每個模塊中每個局部符號有一個定義咕别。靜態(tài)局部變量也會有本地鏈接器符號技健，編譯器還要確保它們擁有唯一的名字。

然而顷级，對于全局符號的解析要復雜得多凫乖。當編譯器遇到一個不是在當前模塊中定義的符號（變量或函數(shù)名）時确垫，會假設該符號是在其他某個模塊中定義的弓颈，生成一個鏈接器符號表條目，并把它交給鏈接器處理删掀。如果鏈接器在它的任何輸入模塊中都找不到這個被引用符號的定義翔冀，就輸出一條錯誤信息并終止。

另一方面披泪，對全局符號的解析纤子，經(jīng)常會面臨多個目標文件可能會定義相同名字的全局符號。這種情況下款票，鏈接器必須要么標志一個錯誤控硼，要么以某種方法選出一個定義并拋棄其他定義。

多重定義的全局符號解析

鏈接器的輸入是一組可重定位目標模塊艾少。每個模塊定義一組符號卡乾，有些是局部符號（只對定義該符號的模塊可見），有些是全局符號（對其他模塊也可見）缚够。如果多個模塊定義同名的全局符號幔妨，該如何進行取舍鹦赎？

Linux編譯系統(tǒng)采用如下的方法解決多重定義的全局符號解析：

在編譯時，編譯器想?yún)R編器輸出每個全局符號误堡，或者是強（strong）或者是弱（weak）古话，而匯編器把這個信息隱含地編碼在可重定位目標文件的符號表中。

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

• 規(guī)則1：不允許有多個同名的強符號陪踩。
• 規(guī)則2：如果有一個強符號和多個弱符號同名，則選擇強符號沾谜。
• 規(guī)則3：如果有多個弱符號同名膊毁，則從這些弱符號中任意選擇一個。

另一方面基跑，由于允許一個符號定義在多個文件中婚温，所以可能會導致一個問題：如果一個弱符號定義在多個目標文件中，而它們的類型不同媳否，怎么辦栅螟？這種情況主要有三種：

• 情況1：兩個或兩個以上的強符號類型不一致。
• 情況2：有一個強符號篱竭，其他都是弱符號力图，出現(xiàn)類型不一致。
• 情況3：兩個或兩個以上弱符號類型不一致掺逼。

其中吃媒，情況1由于多個強符號定義本身就是非法的，所以鏈接器就會報錯吕喘。對于后兩種情況赘那，編譯器和鏈接器采用一種叫 COMMON塊（Common Block
） 的機制來處理。其過程如下：

首先氯质，編譯器將未初始化的全局變量定義為弱符號處理募舟。對于情況3，最終鏈接時選擇最大的類型闻察。對于情況2拱礁，最終輸出結果中的符號所占空間與強符號相同，如果鏈接過程中有弱符號大于強符號辕漂，鏈接器會發(fā)出警告呢灶。

重定位

事實上，重定位過程也伴隨著符號的解析過程钉嘹。鏈接的前兩步完成之后鸯乃，鏈接器就已經(jīng)確定所有符號的虛擬地址了，那么鏈接器就可以根據(jù)符號的地址對每個需要重定位的指令進行地址修正隧期。

那么鏈接器如何知道哪些指令是要被調整的呢飒责？事實上赘娄，我們前面提到的ELF文件中的 重定位表（Relocation Table） 專門用來保存這些與重定位相關的信息。

對于可重定位的ELF文件來說宏蛉，它必須包含重定位表遣臼，用來描述如何修改相應的節(jié)的內容。對于每個要被重定位的ELF節(jié)都有一個對應的重定位表拾并。如果.text節(jié)需要被重定位揍堰，則會有一個相對應叫.rel.text的節(jié)保存了代碼節(jié)的重定位表；如果.data節(jié)需要被重定位嗅义，則會有一個相對應的.rel.tdata的節(jié)保存了數(shù)據(jù)節(jié)的重定位表屏歹。

我們可以使用objdump工具來查看目標文件中的重定位表：

$ objdump -r a.o

a.o:     file format elf64-x86-64

RELOCATION RECORDS FOR [.text]:
OFFSET           TYPE              VALUE
0000000000000023 R_X86_64_32       share
0000000000000030 R_X86_64_PC32     swap-0x0000000000000004
0000000000000049 R_X86_64_PC32     __stack_chk_fail-0x0000000000000004


RELOCATION RECORDS FOR [.eh_frame]:
OFFSET           TYPE              VALUE
0000000000000020 R_X86_64_PC32     .text

我們可以看到每個要被重定位的地方是一個 重定位入口（Relocation Entry）。利用數(shù)據(jù)結構成員包含的信息之碗，即可完成重定位蝙眶。

靜態(tài)鏈接

事實上，靜態(tài)鏈接的過程就是上文所描述的過程褪那。在Linux中幽纷，靜態(tài)鏈接器（static linker）ld以一組可重定位目標文件和命令行參數(shù)作為輸入，生成一個完全鏈接的博敬、可以加載和運行的可執(zhí)行目標文件作為輸出友浸。輸入的可重定位目標文件由各種不同的節(jié)組成，每一節(jié)都是一個連續(xù)的字節(jié)序列偏窝。

動態(tài)鏈接

靜態(tài)鏈接使得進行模塊化開發(fā)收恢，大大提供了程序的開發(fā)效率。隨著祭往，程序規(guī)模的擴大伦意，靜態(tài)鏈接的諸多缺點也逐漸暴露出來，如：浪費內存和磁盤空間链沼、模塊更新困難等默赂。在靜態(tài)鏈接中沛鸵，C語言靜態(tài)庫是很典型的浪費空間的例子括勺。關于模塊更新，靜態(tài)鏈接的程序有任何更新曲掰，都必須重新編譯鏈接疾捍，用戶則需要重新下載安裝該程序。

解決空間浪費和更新困難最簡單的方法便是將程序的模塊相互分割開來栏妖，形成獨立文件乱豆。簡而言之，就是不對那些組成程序的目標文件進行鏈接吊趾，而是等到程序要運行時才進行鏈接宛裕。

動態(tài)鏈接的基本實現(xiàn)

動態(tài)鏈接涉及運行時的鏈接以及多個文件的裝載瑟啃，必需要有操作系統(tǒng)的支持。因為動態(tài)鏈接的情況下揩尸，進程的虛擬地址空間的分布會比靜態(tài)鏈接情況下更為復雜蛹屿，還有一些存儲管理、內存共享岩榆、進程線程等機制在動態(tài)鏈接下也會有一些微妙的變化错负。

目前，主流操作系統(tǒng)都支持動態(tài)鏈接勇边。在Linux中犹撒，ELF動態(tài)鏈接文件被稱為 動態(tài)共享對象（DSO，Dynamic Shared Objects）粒褒，一般以.so為后綴识颊；在Windows中，動態(tài)鏈接文件被稱為 動態(tài)鏈接庫（Dynamic Linking Library）奕坟，一般以.dll為后綴谊囚。

在Linux中，常用的C語言庫的運行庫glibc执赡，其動態(tài)鏈接形式的版本保留在 /lib目錄下镰踏，文件名為 libc.so。整個系統(tǒng)只保留一份C語言動態(tài)鏈接文件libc.so沙合，所有的C語言編寫的奠伪、動態(tài)鏈接的程序都可以在運行時使用它。當程序被裝載時首懈，系統(tǒng)的動態(tài)鏈接器會將程序所需要的所有動態(tài)鏈接庫裝載到進程的地址空間绊率，并將程序中所有未解析的符號綁定到相應的動態(tài)鏈接庫中，并進行重定位究履。

動態(tài)鏈接程序運行時地址空間分布

對于靜態(tài)鏈接的可執(zhí)行文件來說滤否，整個進程只有一個文件要被映射，即可執(zhí)行文件最仑。而對于動態(tài)鏈接藐俺，除了可執(zhí)行文件，還有它所依賴的共享目標文件泥彤。

關于共享目標文件在內存中的地址分配欲芹，主要有兩種解決方案，分別是：

• 靜態(tài)共享庫（Static Shared Library）（地址固定）
• 動態(tài)共享庫（Dynamic Shared Libary）（地址不固定）

靜態(tài)共享庫

靜態(tài)共享庫的做法是將程序的各個模塊統(tǒng)一交給操作系統(tǒng)進行管理吟吝，操作系統(tǒng)在某個特定的地址劃分出一些地址塊菱父，為那些已知的模塊預留足夠的空間。因為這個地址對于不同的應用程序來說，都是固定的浙宜，所以稱之為靜態(tài)官辽。

但是靜態(tài)共享庫的目標地址會導致地址沖突、升級等問題粟瞬。

動態(tài)共享庫

采用動態(tài)共享庫的方式野崇，也稱為裝載時重定位（Load Time Relocation）。其基本思路是：在鏈接時亩钟，對所有絕對地址的引用都不作重定位乓梨，而把這一步推遲到裝載時再完成。一旦模塊裝載地址確定清酥，即目標地址確定扶镀，那么系統(tǒng)就對程序中所有的絕對地址引用進行重定位。

但是這種方式也存在一些問題焰轻。比如臭觉，動態(tài)鏈接模塊被裝載映射至虛擬空間后，指令部分是在多個進程間共享的辱志，由于裝載時重定位的方法需要修改指令蝠筑，所以沒有辦法做到同一份指令被多個進程共享，因為指令被重定位后對于每個進程來說都是不同的揩懒。

然后什乙，動態(tài)鏈接庫中的代碼是共享的，但是其中的可修改數(shù)據(jù)部分對于不同進程來說是由多個副本的已球〕剂停基于此，一種名為地址無關代碼的技術被提出以克服這個問題智亮。

地址無關代碼

計算機科學領域的任何問題都可以通過增加一個間接的中間層來解決忆某。

地址無關代碼（PIC，Position-independent Code） 技術完美闡釋了上面這句名言阔蛉，其基本原理是：把指令中那些需要被修改的部分分離出來弃舒，跟數(shù)據(jù)部分放在一起，這樣指令部分就可以保持不變状原，而數(shù)據(jù)部分可以在每個進程中擁有一個副本聋呢。

共享對象模塊中的地址引用按照是否為跨模塊分為兩類：模塊內部引用、模塊外部引用遭笋。按照不用的引用方式又可分為：指令引用坝冕、數(shù)據(jù)引用徒探。以如下代碼為例瓦呼，可得出如下四種類型：

• 類型1：模塊內部的函數(shù)調用。
• 類型2：模塊內部的數(shù)據(jù)訪問，如模塊中定義的全局變量央串、靜態(tài)變量磨澡。
• 類型3：模塊外部的函數(shù)調用。
• 類型4：模塊外部的數(shù)據(jù)訪問质和，如其他模塊中定義的全局變量稳摄。

static int a;
extern int b;
extern void ext();

void bar() {
    a = 1;      // 類型2：模塊內部數(shù)據(jù)訪問
    b = 2;      // 類型4：模塊外部數(shù)據(jù)訪問
}

void foo() {
    bar();      // 類型1：模塊內部函數(shù)調用
    ext();      // 類型4：模塊外部函數(shù)調用
}

類型1 模塊內部函數(shù)調用

由于被調用的函數(shù)與調用者都處于同一模塊，它們之間的相對位置是固定的饲宿。對于現(xiàn)代的系統(tǒng)來說厦酬，模塊內部的調用都可以是相對地址調用，或者是基于寄存器的相對調用瘫想，所以對于這種指令是不需要重定位的仗阅。

類型2 模塊內部數(shù)據(jù)訪問

一個模塊前面一般是若干個頁的代碼，后面緊跟著若干個頁的數(shù)據(jù)国夜，這些頁之間的相對位置是固定的减噪，即任何一條指令與它需要訪問的模塊內部數(shù)據(jù)之間的相對位置是固定的，所以只需要相對于當前指令加上固定的偏移量就可以訪問模塊內部數(shù)據(jù)了车吹。

類型3 模塊間數(shù)據(jù)訪問

模塊間的數(shù)據(jù)訪問比模塊內部稍微麻煩一些筹裕，因為模塊間的數(shù)據(jù)訪問目標地址要等到裝載時才決定。此時窄驹，動態(tài)鏈接需要使用代碼無關地址技術朝卒，其基本思想是把地址相關的部分放到數(shù)據(jù)段。ELF的實現(xiàn)方法是：在數(shù)據(jù)段中建立一個指向這些變量的指針數(shù)組乐埠，也稱為全局偏移表（Global Offset Table扎运，GOT），當代碼需要引用該全局變量時饮戳，可以通過GOT中相對應的項間接引用豪治。過程示意圖如下所示：

image

當指令中需要訪問變量b時，程序會先找到GOT扯罐，然后根據(jù)GOT中變量所對應的項找到變量的目標地址负拟。每個變量都對應一個4字節(jié)的地址，鏈接器在裝載模塊時會查找每個變量所在的地址歹河，然后填充GOT中的各個項掩浙，以確保每個指針所指向的地址正確。由于GOT本身是放在數(shù)據(jù)段的秸歧，所以它可以在模塊裝載時被修改厨姚，并且每個進程都可以有獨立的副本，相互不受影響键菱。

類型4 模塊間函數(shù)調用

對于模塊間函數(shù)調用谬墙，同樣可以采用類型3的方法來解決。與上面的類型有所不同的是，GOT中響應的項保存的是目標函數(shù)的地址拭抬，當模塊需要調用目標函數(shù)時部默，可以通過GOT中的項進行間接跳轉。

總結

通過上文的描述，我們基本理清了鏈接的過程以及靜態(tài)鏈接和動態(tài)鏈接的區(qū)別。事實上南蹂，鏈接的具體實現(xiàn)細節(jié)是非常復雜，本文只是對其進行了概述份蝴，更多細節(jié)以及優(yōu)化實現(xiàn)還是需要我們自己進一步去探索。

參考

1. Executable and Linkable Format (ELF)
2. 《Linux 二進制分析》
3. 《程序員的自我修養(yǎng)——鏈接氓轰、裝載與庫》
4. 《深入理解計算機系統(tǒng)》
5. Executable and Linkable Format

（完）