鏈接器和裝入器的基本工作原理

一個程序要想在內存中運行，除了編譯之外還要經過鏈接和裝入這兩個步驟。從程序員的角度來看，引入這兩個步驟帶來的好處就是可以直接在程序中使用printf和errno這種有意義的函數名和變量名，而不用明確指明printf和errno在標準C庫中的地址。當然，為了將程序員從早期直接使用地址編程的夢魘中解救出來，編譯器和匯編器在這當中做出了革命性的貢獻。編譯器和匯編器的出現使得程序員可以在程序中使用更具意義的符號來為函數和變量命名，這樣使得程序在正確性和可讀性等方面都得到了極大的提高。但是隨著C語言這種支持分別編譯的程序設計語言的流行，一個完整的程序往往被分割為若干個獨立的部分并行開發，而各個模塊間通過函數接口或全局變量進行通訊。這就帶來了一個問題，編譯器只能在一個模塊內部完成符號名到地址的轉換工作，不同模塊間的符號解析由誰來做呢？比如前面所舉的例子，調用printf的用戶程序和實現了printf的標準C庫顯然就是兩個不同的模塊。實際上，這個工作是由鏈接器來完成的。

為了解決不同模塊間的鏈接問題，鏈接器主要有兩個工作要做――符號解析和重定位：

符號解析：當一個模塊使用了在該模塊中沒有定義過的函數或全局變量時，編譯器生成的符號表會標記出所有這樣的函數或全局變量，而鏈接器的責任就是要到別的模塊中去查找它們的定義，如果沒有找到合適的定義或者找到的合適的定義不唯一，符號解析都無法正常完成。

重定位：編譯器在編譯生成目標文件時，通常都使用從零開始的相對地址。然而，在鏈接過程中，鏈接器將從一個指定的地址開始，根據輸入的目標文件的順序以段為單位將它們一個接一個的拼裝起來。除了目標文件的拼裝之外，在重定位的過程中還完成了兩個任務：一是生成最終的符號表；二是對代碼段中的某些位置進行修改，所有需要修改的位置都由編譯器生成的重定位表指出。

舉個簡單的例子，上面的概念對讀者來說就一目了然了。假如我們有一個程序由兩部分構成，m.c中的main函數調用f.c中實現的函數sum：

/* m.c */

int i = 1;

int j = 2;

extern int sum();

void main()

{

int s;

s = sum(i, j);

/* f.c */

int sum(int i, int j)

{

return i + j;

}

在Linux用gcc分別將兩段源程序編譯成目標文件：

$ gcc -c m.c

$ gcc -c f.c

我們通過objdump來看看在編譯過程中生成的符號表和重定位表：

$ objdump -x m.o

……

SYMBOL TABLE:

……

00000000 gO .data 00000004 i

00000004 gO .data 00000004 j

00000000 gF .text 00000021 main

00000000 *UND* 00000000 sum

RELOCATION RECORDS FOR [.text]:

OFFSET TYPE VALUE

00000007 R_386_32 j

0000000d R_386_32 i

00000013 R_386_PC32 sum

首先，我們注意到符號表里面的sum被標記為UND(undefined)，也就是在m.o中沒有定義，所以將來要通過ld(Linux下的鏈接器)的符號解析功能到別的模塊中去查找是否存在函數sum的定義。另外，在重定位表中有三條記錄，指出了在重定位過程中代碼段中三處需要修改的位置，分別位于7、d和13。下面以一種更加直觀的方式來看一下這三個位置：

$ objdump -dx m.o

Disassembly of section .text:

00000000 :

0: 55push %ebp

1: 89 e5mov %esp,%ebp

3: 83 ec 04sub $0x4,%esp

6: a1 00 00 00 00mov 0x0,%eax

7: R_386_32 j

b: 50push %eax

c: a1 00 00 00 00mov 0x0,%eax

d: R_386_32 i

11: 50push %eax

12: e8 fc ff ff ffcall 13

13: R_386_PC32 sum

17: 83 c4 08add $0x8,%esp

1a: 89 c0mov %eax,%eax

1c: 89 45 fcmov %eax,0xfffffffc(%ebp)

1f: c9leave

20: c3ret

以sum為例，對函數sum的調用是通過call指令實現的，使用IP相對尋址方式。可以看到，在目標文件m.o中，call指令位于從零開始的相對地址12的位置，這里存放的e8是call的操作碼，而從13開始的4個字節存放著sum相對call的下一條指令add的偏移。顯然，在鏈接之前這個偏移量是不知道的，所以將來要來修改13這里的代碼。那現在這里為什么存放著0xfffffffc(注意Intel的CPU使用little endian的編址方式)呢？這大概是出于安全的考慮，因為0xfffffffc正是－4的補碼表示(讀者可以在gdb中使用p /x -4查看)，而call指令本身占用了5個字節，因此無論如何call指令中的偏移量不可能是－4。我們再看看重定位之后call指令中的這個偏移量被修改成了什么：

$ gcc m.o f.o

$ objdump -dj .text a.out | less

Disassembly of section .text:

……

080482c4 :

……

80482d6: e8 0d 00 00 00call 80482e8

80482db: 83 c4 08add $0x8,%esp

……

080482e8 :

……

可以看到經過重定位之后，call指令中的偏移量修改成0x0000000d了，簡單的計算告訴我們：0x080482e8－0x80482db=0xd。這樣，經過重定位之后最終的可執行程序就生成了。

可執行程序生成后，下一步就是將其裝入內存運行。Linux下的編譯器(C語言)是cc1，匯編器是as，鏈接器是ld，但是并沒有一個實際的程序對應裝入器這個概念。實際上，將可執行程序裝入內存運行的功能是由execve(2)這一系統調用實現的。簡單來講，程序的裝入主要包含以下幾個步驟：

讀入可執行文件的頭部信息以確定其文件格式及地址空間的大小；

以段的形式劃分地址空間；

將可執行程序讀入地址空間中的各個段，建立虛實地址間的映射關系；

將bbs段清零；

創建堆棧段；

建立程序參數、環境變量等程序運行過程中所需的信息；

啟動運行。

鏈接和裝入技術的發展史

一個程序要想裝入內存運行必然要先經過編譯、鏈接和裝入這三個階段，雖然是這樣一個大家聽起來耳熟能詳的概念，在操作系統發展的過程中卻已經經歷了多次重大變革。簡單來講，可以將其劃分為以下三個階段：

1． 靜態鏈接、靜態裝入

這種方法最早被采用，其特點是簡單，不需要操作系統提供任何額外的支持。像C這樣的編程語言從很早開始就已經支持分別編譯了，程序的不同模塊可以并行開發，然后獨立編譯為相應的目標文件。在得到了所有的目標文件后，靜態鏈接、靜態裝入的做法是將所有目標文件鏈接成一個可執行映象，隨后在創建進程時將該可執行映象一次全部裝入內存。舉個簡單的例子，假設我們開發了兩個程序Prog1和Prog2，Prog1由main1.c、utilities.c以及errhdl1.c三部分組成，分別對應程序的主框架、一些公用的輔助函數(其作用相當于庫)以及錯誤處理部分，這三部分代碼編譯后分別得到各自對應的目標文件main1.o、utilities.o以及errhdl1.o。同樣，Prog2由main2.c、utilities.c以及errhdl2.c三部分組成，三部分代碼編譯后分別得到各自對應的目標文件main2.o、utilities.o以及errhdl2.o。值得注意的是，這里Prog1和Prog2使用了相同的公用輔助函數utilities.o。當我們采用靜態鏈接、靜態裝入的方法，同時運行這兩個程序時內存和硬盤的使用情況如圖1所示：

可以看到，首先就硬盤的使用來講，雖然兩個程序共享使用了utilities，但這并沒有在硬盤保存的可執行程序映象上體現出來。相反，utilities.o被鏈接進了每一個用到它的程序的可執行映象。內存的使用也是如此，操作系統在創建進程時將程序的可執行映象一次全部裝入內存，之后進程才能開始運行。如前所述，采用這種方法使得操作系統的實現變得非常簡單，但其缺點也是顯而易見的。首先，既然兩個程序使用的是相同的utilities.o，那么我們只要在硬盤上保存utilities.o的一份拷貝應該就足夠了；另外，假如程序在運行過程中沒有出現任何錯誤，那么錯誤處理部分的代碼就不應該被裝入內存。因此靜態鏈接、靜態裝入的方法不但浪費了硬盤空間，同時也浪費了內存空間。由于早期系統的內存資源十分寶貴，所以后者對早期的系統來講更加致命。

2． 靜態鏈接、動態裝入

既然采用靜態鏈接、靜態裝入的方法弊大于利，我們來看看人們是如何解決這一問題的。由于內存緊張的問題在早期的系統中顯得更加突出，因此人們首先想到的是要解決內存使用效率不高這一問題，于是便提出了動態裝入的思想。其想法是非常簡單的，即一個函數只有當它被調用時，其所在的模塊才會被裝入內存。所有的模塊都以一種可重定位的裝入格式存放在磁盤上。首先，主程序被裝入內存并開始運行。當一個模塊需要調用另一個模塊中的函數時，首先要檢查含有被調用函數的模塊是否已裝入內存。如果該模塊尚未被裝入內存，那么將由負責重定位的鏈接裝入器將該模塊裝入內存，同時更新此程序的地址表以反應這一變化。之后，控制便轉移到了新裝入的模塊中被調用的函數那里。

動態裝入的優點在于永遠不會裝入一個使用不到的模塊。如果程序中存在著大量像出錯處理函數這種用于處理小概率事件的代碼，使用這種方法無疑是卓有成效的。在這種情況下，即使整個程序可能很大，但是實際用到(因此被裝入到內存中)的部分實際上可能非常小。

仍然以上面提到的兩個程序Prog1和Prog2為例，假如Prog1運行過程中出現了錯誤而Prog2在運行過程中沒有出現任何錯誤。當我們采用靜態鏈接、動態裝入的方法，同時運行這兩個程序時內存和硬盤的使用情況如圖2所示：

圖 2采用靜態鏈接、動態裝入方法，同時運行Prog1和Prog2時內存和硬盤的使用情況

可以看到，當程序中存在著大量像錯誤處理這樣使用概率很小的模塊時，采用靜態鏈接、動態裝入的方法在內存的使用效率上就體現出了相當大的優勢。到此為止，人們已經向理想的目標邁進了一部，但是問題還沒有完全解決――內存的使用效率提高了，硬盤呢？

3． 動態鏈接、動態裝入

采用靜態鏈接、動態裝入的方法后看似只剩下硬盤空間使用效率不高的問題了，實際上內存使用效率不高的問題仍然沒有完全解決。圖2中，既然兩個程序用到的是相同的utilities.o，那么理想的情況是系統中只保存一份utilities.o的拷貝，無論是在內存中還是在硬盤上，于是人們想到了動態鏈接。

在使用動態鏈接時，需要在程序映象中每個調用庫函數的地方打一個樁(stub)。stub是一小段代碼，用于定位已裝入內存的相應的庫；如果所需的庫還不在內存中，stub將指出如何將該函數所在的庫裝入內存。

當執行到這樣一個stub時，首先檢查所需的函數是否已位于內存中。如果所需函數尚不在內存中，則首先需要將其裝入。不論怎樣，stub最終將被調用函數的地址替換掉。這樣，在下次運行同一個代碼段時，同樣的庫函數就能直接得以運行，從而省掉了動態鏈接的額外開銷。由此，用到同一個庫的所有進程在運行時使用的都是這個庫的同一份拷貝。

下面我們就來看看上面提到的兩個程序Prog1和Prog2在采用動態鏈接、動態裝入的方法，同時運行這兩個程序時內存和硬盤的使用情況(見圖3)。仍然假設Prog1運行過程中出現了錯誤而Prog2在運行過程中沒有出現任何錯誤。

圖 3采用動態鏈接、動態裝入方法，同時運行Prog1和Prog2時內存和硬盤的使用情況

圖中，無論是硬盤還是內存中都只存在一份utilities.o的拷貝。內存中，兩個進程通過將地址映射到相同的utilities.o實現對其的共享。動態鏈接的這一特性對于庫的升級(比如錯誤的修正)是至關重要的。當一個庫升級到一個新版本時，所有用到這個庫的程序將自動使用新的版本。如果不使用動態鏈接技術，那么所有這些程序都需要被重新鏈接才能得以訪問新版的庫。為了避免程序意外使用到一些不兼容的新版的庫，通常在程序和庫中都包含各自的版本信息。內存中可能會同時存在著一個庫的幾個版本，但是每個程序可以通過版本信息來決定它到底應該使用哪一個。如果對庫只做了微小的改動，庫的版本號將保持不變；如果改動較大，則相應遞增版本號。因此，如果新版庫中含有與早期不兼容的改動，只有那些使用新版庫進行編譯的程序才會受到影響，而在新版庫安裝之前進行過鏈接的程序將繼續使用以前的庫。這樣的系統被稱作共享庫系統。

Linux下動態鏈接的實現

如今我們在Linux下編程用到的庫(像libc、QT等等)大多都同時提供了動態鏈接庫和靜態鏈接庫兩個版本的庫，而gcc在編譯鏈接時如果不加-static選項則默認使用系統中的動態鏈接庫。對于動態鏈接庫的原理大多數的書本上只是進行了泛泛的介紹，在此筆者將通過在實際系統中反匯編出的代碼向讀者展示這一技術在Linux下的實現。

下面是個最簡單的C程序hello.c：

#include

int main()

{

printf("Hello, world\n");

return 0;

}

在Linux下我們可以使用gcc將其編譯成可執行文件a.out：

$ gcc hello.c

程序里用到了printf，它位于標準C庫中，如果在用gcc編譯時不加-static的話，默認是使用libc.so，也就是動態鏈接的標準C庫。在gdb中可以看到編譯后printf對應如下代碼 ：

$ gdb -q a.out

(gdb) disassemble printf

Dump of assembler code for function printf:

0x8048310 : jmp *0x80495a4

0x8048316 : push $0x18

0x804831b : jmp 0x80482d0 <_init>

這也就是通常在書本上以及前面提到的打樁(stub)過程，顯然這并不是真正的printf函數。這段stub代碼的作用在于到libc.so中去查找真正的printf。

(gdb) x /w 0x80495a4

0x80495a4 <_global_offset_table_>: 0x08048316

可以看到0x80495a4處存放的0x08048316正是pushl $0x18這條指令的地址，所以第一條jmp指令沒有起到任何作用，其作用就像空操作指令nop一樣。當然這是在我們第一次調用printf時，其真正的作用是在今后再次調用printf時體現出來的。第二條jmp指令的目的地址是plt，也就是procedure linkage table，其內容可以通過objdump命令查看，我們感興趣的就是下面這兩條對程序的控制流有影響的指令：

$ objdump -dx a.out

……

080482d0 >.plt>:

80482d0: ff 35 90 95 04 08 pushl 0x8049590

80482d6: ff 25 94 95 04 08 jmp *0x8049594

……

第一條push指令將got(global offset table)中與printf相關的表項地址壓入堆棧，之后jmp到內存單元0x8049594中所存放的地址0x4000a960處。這里需要注意的一點是，在查看got之前必須先將程序a.out啟動運行，否則通過gdb中的x命令在0x8049594處看到的結果是不正確的。

(gdb) b main

Breakpoint 1 at 0x8048406

(gdb) r

Starting program: a.out

Breakpoint 1, 0x08048406 in main ()

(gdb) x /w 0x8049594

0x8049594 <_global_offset_table_>: 0x4000a960

(gdb) disassemble 0x4000a960

Dump of assembler code for function _dl_runtime_resolve:

0x4000a960 <_dl_runtime_resolve>: pushl %eax

0x4000a961 <_dl_runtime_resolve>: pushl %ecx

0x4000a962 <_dl_runtime_resolve>: pushl %edx

0x4000a963 <_dl_runtime_resolve>: movl 0x10(%esp,1),%edx

0x4000a967 <_dl_runtime_resolve>: movl 0xc(%esp,1),%eax

0x4000a96b <_dl_runtime_resolve>: call 0x4000a740

0x4000a970 <_dl_runtime_resolve>: popl %edx

0x4000a971 <_dl_runtime_resolve>: popl %ecx

0x4000a972 <_dl_runtime_resolve>: xchgl %eax,(%esp,1)

0x4000a975 <_dl_runtime_resolve>: ret $0x8

0x4000a978 <_dl_runtime_resolve>: nop

0x4000a979 <_dl_runtime_resolve>: leal 0x0(%esi,1),%esi

End of assembler dump.

前面三條push指令執行之后堆棧里面的內容如下：

下面將0x18存入edx，0x8049590存入eax，有了這兩個參數，fixup就可以找到printf在libc.so中的地址。當fixup返回時，該地址已經保存在了eax中。xchg指令執行完之后堆棧中的內容如下：

最妙的要數接下來的ret指令的用法，這里ret實際上被當成了call來使用。ret $0x8之后控制便轉移到了真正的printf函數那里，并且清掉了堆棧上的0x18和0x8049584這兩個已經沒用的參數，這時堆棧便成了下面的樣子：

而這正是我們所期望的結果。應該說這里ret的用法與Linux內核啟動后通過iret指令實現由內核態切換到用戶態的做法有著異曲同工之妙。很多人都聽說過中斷指令int可以實現用戶態到內核態這種優先級由低到高的切換，在接受完系統服務后iret指令負責將優先級重新降至用戶態的優先級。然而系統啟動時首先是處于內核態高優先級的，Intel i386并沒有單獨提供一條特殊的指令用于在系統啟動完成后降低優先級以運行用戶程序。其實這個問題很簡單，只要反用iret就可以了，就像這里將ret當作call使用一樣。另外，fixup函數執行完還有一個副作用，就是在got中與printf相關的表項(也就是地址為0x80495a4的內存單元)中填上查找到的printf函數在動態鏈接庫中的地址。這樣當我們再次調用printf函數時，其地址就可以直接從got中得到，從而省去了通過fixup查找的過程。也就是說got在這里起到了cache的作用。

一點感想

其實有很多東西只要勤于思考，還是能夠自己悟出一些道理的。國外有一些高手就是通過能夠大家都能見到的的一點點資料，自己摸索出來很多不為人知的秘密。像寫《Undocument Dos》和《Undocment Windows》的作者，他就為我們樹立了這樣的榜樣！

學習計算機很關鍵的一點在于一定要富于探索精神，要讓自己做到知其然并知其所以然。侯先生在《STL源碼剖析》一書開篇題記中寫到"源碼之前，了無秘密"，當然這是在我們手中掌握著源碼的情況下，如若不然，不要忘記Linux還為我們提供了大量的像gdb、objdump這樣的實用工具。有了這些得力的助手，即使沒有源碼，我們一樣可以做到"了無秘密"。