本章目的： 提供了關于連結各方面的全面讨論，從傳統靜态連結到加載時的共享庫的動态連結，以及到運作時的共享庫的動态連結
連結(linking)是将各種代碼和資料片段收集并組合成一個單一檔案的過程
這個檔案可被加載(複制)到記憶體被并執行
連結可以執行于編譯時，也就是在源代碼被翻譯成機器代碼時
也可以執行于運作時，也就是應用程式執行
在早期，連結是手動執行的，在現代系統中，連結是由叫做連結器(linker)的程式自動執行的
不過，無論是什麼樣的作業系統、ISA或者目标檔案格式、基本連結概念是通用的
細節可能不盡相同，但是概念是相同的
7 連結
7.1 編譯器驅動程式
大多數編譯系統提供 編譯器驅動程式 ， 它代表使用者在需要時調用語言預處理器、編譯器、彙編器和連接配接器
在shell使用指令：
上圖概括了驅動程式在将示例從ASCLL碼源檔案翻譯器成 可執行目标檔案時的行為
如果想看詳細步驟，可以用 –v 選項
它将C的源程式main.c 翻譯成一個ASCLL碼的中間檔案 main.i
Cpp main.c main.i
然後，驅動程式運作C編譯器(ccl)，它将main.i翻譯成一個ASCLL彙編語言檔案main.s
Ccl main.i –Og –o main.s
然後，驅動程式運作彙編器(as)，它将main.s翻譯成一個可重定位目标檔案main.o
As –o main.o main.s
驅動程式經過相同的過程生産sum.o ，最後，它運作連接配接器ld，将main.o和sum.o以及一些必要的系統目标檔案組合起來，建立一個可執行目标檔案 prog
Ld –o prog main.o sum.o
運作prog
./prog
Shell調用作業系統中一個叫做加載器的函數，它将可執行檔案prog的代碼和資料複制到記憶體，然後将控制轉移到這個程式的開頭
上圖展示了 GCC 編譯成不同的中間檔案
7.2 靜态連結
像Linux LD程式這樣的靜态連結器 (static linker) 以一組可重定位目标檔案和指令行參數作為輸入，生成一個完全連結的、可以加載和運作的可執行目标檔案作為輸出
輸入的可重定位目标檔案由各種不同的代碼和資料節(section)組成
每一節都是一個連續的位元組序列，指令在一節中，初始化了的全局變量在另一節中，而未初始化的變量由在另外一節中
為了構造可執行檔案，連結器必須完成兩個主要任務：
7.3 目标檔案
目标檔案有三種形式：
編譯器和彙編器生成可重定位目标檔案(包括共享目标檔案)
連結器生成可執行目标檔案
在技術上來說，一個目标模闆(Object module)就是一個位元組序列，而一個目标檔案(Object file)就是一個以檔案形式存放在磁盤中的目标模闆
目标檔案就是按照特定的目标檔案格式來組織的，各個系統的目标檔案格式都不相同
Windows使用可移植可執行(Protable Executable, PE)格式
現代x86-64 Linux和Unix系統使用可執行可連結格式(Executable and Linkable Format, ELF)
但不管哪種格式，基本概念是相似的
7.4 可重定位目标檔案
ELF頭(ELF header) 以一個16位元組的序列開始，這個序列描述了生産該檔案的系統的字的大小和位元組順序
ELF頭剩下的部分包括幫助連接配接器文法分析和解釋目标檔案的資訊
其中包括ELF頭的大小、目标檔案的類型、機器類型、節頭部表中條目的大小和數量
不同節的位置和大小是由節頭部表描述的，其中目标檔案中每個節都有一個固定大小的條目
包含在EFL頭和節頭部表之間的都是節，一個典型的ELF可重定位目标檔案包含下面幾個節：
7.5 符号和符号表
每個可重定位目标模闆m都有一個符号表，它包含m定義和引用的符号的資訊，在連接配接器的上下文中，有三種不同的符号：
本地連結器符号和本地程式變量不同的， .symtab中的符号表不包含對應于本地非靜态程式變量的任何符号，這些符号在運作時在棧中被管理
定義帶有C static屬性的本地過程變量是不在棧中被管理的，編譯器在.data 或 .bss 中為每個定義配置設定空間，并在符号表中建立一個唯一名字的本地連結符号
符号表是由編譯器構造的，使用編譯器輸出到彙編語言 .s 檔案中的符号， .symtab節中包含ELF符号表，這張符号表包含一個條目的資料
每個符号都被配置設定到目标檔案的某個節，由section字段表示，該字段也是到一個節頭部表的索引
有三個特殊的僞節(pseudosection)，它們在節頭部表中是沒有條目的:
ABS 代表不被重定位的符号
UNDEF 代表未定義的符号，也就是在本目标模闆中引用
COMMON 表示還未被配置設定位置的未初始化的資料目标
對于COMMON符号，value字段給出對齊要求，而size給出最小的大小
注意，隻有可重定位目标檔案才有這些僞節，可執行目标檔案中是沒有的
7.6 符号解析
連結器解析符号引用的方法是将每個引用與它輸入的可重定位目标檔案的符号表中的一個确定的符号定義關聯起來
對于那些和引用定義在相同模闆中的局部符号的引用，符号解析式是非常簡單明了的
編譯器隻允許每個模闆中每個局部符号有一個定義，靜态變量也會有本地連結器符号
編譯器還要確定他們擁有唯一的名字
對于全局變量的引用解析就棘手得多，當編譯器遇到一個不是在目前模闆中定義的符号(變量或函數名)時，會假設該符号是在其他某個子產品中定義的，生成一個連結器符号表條目，并把它交給連結器處理
如果連結器在他任何輸入子產品中找不到這個被引用符号的定義，就輸出一條錯誤資訊
7.6.1 連結器如何解析多重定義的全局符号
連結器的輸入時一組可重定位目标子產品
每個子產品定義一組符号，有些是局部(隻對定義該符号的子產品可見)
有些是全局(對其他子產品也可見)
如果多個子產品定義同名的全局符号，下面是Linux編譯系統采用的方法：
在編譯時，編譯器向彙編器輸出每個全局符号，或者是強(strong)，或者是弱(weak)
而彙編器把這個資訊隐含在可重定位目标檔案的符号表裡
函數和已初始化的全局變量是強符号
未初始化的全局變量是弱符号
假設試圖編譯和連結下面兩個C子產品：
7.6.2 與靜态庫連結
迄今為止，我們都是假設連結器讀取一組可重定位目标檔案，并把它們連結起來，形成一個輸出的可執行檔案
實際上，所有的編譯系統都提供一種機制，将所有相關的目标子產品打包成為一個單獨的檔案，稱為 靜态庫(static library)，它可以用做連結器的輸入
當連結器構造一個輸出的可執行檔案時，它隻複制靜态庫裡被引用程式引用的子產品
在Linux系統中，靜态庫以一種稱為**存檔(archive)**的特殊檔案格式存放在磁盤中
存檔檔案是一組連接配接起來的可重定位目标檔案的集合，有一個頭部用來描述每個成員目标檔案的大小和位置，存檔檔案由字尾 .a 辨別
為了對庫的讨論更加形象，參考下面例程：
要建立這些函數的一個靜态庫，使用ar工具：
為了使用這個庫，我們可以編寫一個應用程式:
//vector.h 是自己建立的一個頭檔案，裡邊包括那兩個函數的聲明
-static 參數告訴編譯器驅動程式，連結器應該建構一個完全連結的可執行目标檔案
它可以加載到記憶體并運作，在加載時無須更進一步的連結
-lvector 參數是 libvector.a 的縮寫， -L. 參數告訴編譯器在目前目錄下查找libvector.a
上圖概括了連結器的行為
當連結器運作時，它判定main2.o引用了addvec.o定義的addvec符号，是以複制addcec.o到可執行檔案，因為程式不引用任何由 multvec.o 定義的符号，是以連結器就不會複制這個子產品到可執行檔案，連結器還會複制liba.a 中的printf.o 子產品，以及許多C運作時系統中的其他子產品
7.6.3 連結器如何使用靜态庫來解析引用
Linux 連結器使用它們解析外部引用的方式
在符号解析階段，連結器從左到右按照它們在編譯器驅動程式指令行上出現的順序來掃描可重定位目标檔案和存檔檔案
(驅動程式自動将指令行中所有的.c檔案翻譯成.o檔案)在這次掃描中，連結器維護一個可重定位目标檔案的集合E(在這個集合中的檔案會被合并起來形成可執行檔案)
一個未解析的符号（即引用了但是尚未定義的符号）集合U，以及一個在前面輸入檔案中已
定義的符号集合D，初始時，E、U、D均為空
7.7 重定位
一旦連結器完成了符号解析這一步，就把代碼中的每個符号引用和正好一個符号定義
(即它的一個輸入目标子產品中的一個符号表條目)關聯起來
此時，連結器就知道它的輸入目标子產品中的代碼節和資料節的确切大小
現在就可以開始重定位步驟了，在這個步驟中，将合并輸入子產品，并為每個符号配置設定運作時位址，步驟：
7.7.1 重定位條目
當彙編器生成一個目标子產品時，它并不知道資料和代碼最終将要放在記憶體的什麼位置
也不知道這個子產品引用的任何外部定義的函數或者全局變量的位置
是以，無論何時彙編器遇到對最終位置未知的目标引用，它就會生産一個重定位條目，告訴連結器在将目标檔案合并成可執行檔案時如何修改這個引用
代碼重定位條目放在 .rel.text中，已初始化資料的重定位條目放在 .rel.text中
上圖展示了ELF重定位條目的格式
Offset 是需要被修改的引用的節偏移
Symbol 辨別被修改引用應該指向的符号
Type 告訴連結器如何修改新的引用
Addend 是一個有符号常數，一些類型的重定位要被使用它對被修改引用的值做偏移調整
這兩種重定位類型支援x86-64小型代碼模型(small code model)，該模型假設可執行目标檔案中的代碼和資料總體大小小于2GB，是以在運作時可以用32位PC相對位址來通路
GCC預設使用小型代碼模型，大于2GB的程式可以用 –mcmodel = medium(中型代碼模型)
和 –mcmodel = large(大型代碼模型)标志來編譯
7.7.2 重定位符号引用
上圖展示了連結器的重定位算法的僞代碼
1，2行在每個節s以及與每個節關聯起來的重定位條目r上疊代執行
假設每個節s是一個位元組數組，每個重定位條目r是一個類型為ELF64_Rela的結構(圖7-9)
還假設當算法運作時，連結器已經為每個節 (ADDR(S)表示) 和每個符号都選擇了運作時位址 (ADDR(r.symbol表示)
3行計算的是需要被重定位的4位元組引用的數組s中的位址
如果這個引用是PC相對尋址，那就5-9行來重定位
如果該引用使用的是絕對尋址，那就通過11-13行來重定位
以本章最開始的執行個體程式看下連結器如何用這個算法重定位程式的引用
用objdump –d –x main.o 産生main.o 的反彙編代碼
Main引用了兩個全局符号: array和sum，為每個引用，彙編器産生一個重定位條目
顯示在引用的後面一行
這些重定位條目告訴連結器對sum的引用要使用32位PC相對位址進行重定位，而對array的引用要使用32位絕對位址進行重定位
1.重定位PC相對引用
上圖第6行中，函數main調用sum函數，sum函數是在子產品sum.o中定義的
CALL指令開始于 節偏移0xe 的地方，包括1位元組的操作碼 0xe8
後面跟着是對目标sum的32位PC相對引用的占位符
相應的重定位條目r由4個字段組成：
r.offset = 0xf
r.symbol = sum
r.type = R_x86-64_PC32
r.addend = -4
這些字段告訴連結器修改開始于偏移量 0xf 處的32位PC相對引用，這樣在運作時它會指向sum例程
假設連結器已經确定
ADDR(s) = ADDR(.text) = 0x4004e8
和
ADDR(r.symbol) = ADDR(sum) = 0x4004e8
使用圖7-10中的算法，連接配接器首先計算出引用的運作時位址(7行)：
Refaddr = ADDR(s) + r.offset = 0x4004d0 + 0xf = 0x4004df
然後更新該引用，使得它在運作時隻想sum程式(8行):
*refptr = (unsigned)(ADDR(r.symbol) + r.addend – refaddr)
= (unsigned)(0x4004e8 + (-4) – 0x4004df)
= (unsigned)(0x5)
在得到的可執行目标檔案中，call指令有如下重定位的形式：
4004de: e8 05 00 00 00 callq 4004e8
2.重定位絕對引用
相對簡單，如圖7-11的第4行，mov指令将array的位址（一個32位立即數值）複制到寄存器%edi中，mov指令開始于節偏移量0x9的位置，包括1位元組操作碼0xbf，後面緊跟着對array的32位絕對位址引用的占位符
這些字段告訴連結器要修改從偏移量0xa開始的絕對引用，這樣在運作時它将會指向array的第一個位元組，假設連結器已經确定
ADDR(r.symbol) = ADDR(array) = 0x601018
7.8 可執行目标檔案
我們的示例C程式，開始時是一組ASCLL文本檔案，現在已經被轉化為一個二進制檔案，且這個二進制檔案包含加載程式到記憶體并運作它所需的所有資訊
上圖概括了一個典型的ELF可執行檔案中的各類資訊
可執行目标檔案格式類似于可重定位目标檔案格式，ELF頭描述檔案的總體格式
它還包括程式的入口點(entry point)，也就是當程式運作時要執行的第一條指令的位址
.text .rodata .data 節與重定位目标檔案中的節是相似的，除了這些節已經被重定位到它們最終的運作記憶體位址以外
.init 節定義了一個小函數，叫做 _init ，程式的初始化代碼會調用它
因為可執行檔案是完全連結的（已被重定位）， 是以它不再需要 .rel 節
ELF可執行檔案被設計得很容易加載到記憶體，可執行檔案的連續的片（chunk）被映射到連續的記憶體段
程式頭部表（program header table）描述了這種映射關系
上圖為可執行檔案prog的程式頭部表，本章開始的示例程式 (OBJDUMP顯示)
從程式頭部，我們會看到根據可執行目标檔案的内容初始化兩個記憶體段，第1，2行
第2行告訴我們第一個段（代碼段）有 讀/執行通路權限，開始于記憶體0x400000處，總共記憶體大小是0x69c位元組，并且被初始化為可執行目标檔案的頭0x69c個位元組，其中包括ELF頭、程式頭部表以及 .init .text .rodata節
7.9 加載可執行目标檔案
要運作可執行目标檔案prog，可以在Linux Shell 的指令行輸入：
./prog
因為prog不是内置Linux指令，是以會被認為是一個可執行檔案
通過調用某個駐留在存儲器中稱為加載器(loader)的作業系統代碼來運作它
任何Linux程式都可以通過調用 Execve 函數來調用加載器
加載器将可執行目标檔案中的代碼和資料從磁盤複制到記憶體中
然後通過跳轉到程式的第一條指令或入口點來運作該程式，将程式複制到記憶體并運作的過程叫做加載
每個Linux程式都有一個運作時記憶體映像，類似上圖
在Linux x86-64系統中，代碼段總是從位址0x400000處開始，後面是資料段
運作時堆在資料段之後，通過調用malloc庫往上增長
堆後面的區域是為共享子產品保留的
使用者棧總是從最大的合法使用者位址開始，向較小記憶體位址增長
棧上的區域，從位址2^48開始，是為核心中代碼和資料保留的，所謂核心就是作業系統駐留在記憶體的部分
當加載器運作時，它建立類似于上圖所示的記憶體映像，在程式頭部表的引導下，加載器将可執行檔案的片(chunk)複制到代碼段和資料段
接下來跳轉到程式的入口點，也就是 _start 函數的位址，這個函數是在系統目标檔案 ctrl.o中定義的，對所有C程式都是一樣的
_start函數調用系統啟動函數 __libc_start_main，由該函數定義在libc.so中
它初始化執行環境，調用使用者層的main函數，處理main函數的傳回值，并且在需要的時候把控制傳回給核心
7.10 動态連結共享庫
靜态庫和所有的軟體都一樣，需要定期維護和更新
如果應用程式員想要使用一個庫的最新版本，必須以某種方式了解到該庫的更新情況
然後顯式地将他們的程式與更新了的庫重新連結
幾乎每個C程式都使用标準I/O函數，比如printf 和 scanf
在運作時，這些函數的代碼會被複制到每個運作程序的文本段中
在一個運作上百個程序的典型系統上，這将是對稀缺的記憶體系統資源極大浪費
共享庫( shared library )是緻力于解決靜态庫缺陷的一個現代創新産物
共享庫是一個目标模闆，在運作或加載時，可以加載到任意的記憶體位址，并和一個在記憶體中的程式連結起來，這個過程稱為動态連結( dynamic linking )，是由一個叫做動态連結器的程式來執行的
共享庫也稱為共享目标( shared object )，在Linux系統中常用 .so 字尾來表示
Windows中，他們稱為DLL(動态連結庫)
共享庫是以兩種不同的方式來“共享”的
首先，在任何給定的檔案系統中，對于一個庫隻有一個 .so 檔案
所有引用該庫的可執行目标檔案共享這個 .so 檔案中的代碼和資料
而不是像靜态庫的内容那樣被複制和嵌入到引用他們的可執行檔案中
其次，在記憶體中，一個共享庫的.text節的一個副本可以被不同的正在運作的程序共享
示例：
-fpic 選項訓示編譯器生成與位置無關的代碼
-shared 選項訓示連結器建立一個共享的目标檔案
一旦建立了這個庫，随後就要将它連結到示例程式中，于上圖shell程式中第二行
這樣就建立了一個可執行目标檔案 prog ，而此檔案形式使得它在運作時可以和libdemo.so連結
基本思路就是當建立可執行檔案時，靜态執行一些連結，然後再程式加載時，動态完成連結過程
此時，沒有任何libdemo.so的代碼和資料節被複制到可執行檔案prog中
反之，連結器複制了一些重定位和符号表資訊，它們使得運作可執行檔案prog時，可以解析對libdemo.so中代碼和資料的引用
當加載器加載和運作可執行檔案prog時，加載部分連結的可執行檔案prog
接着，它注意到prog包含一個 .interp節，這一節包含動态連結器的路徑名
動态連結器本身就是一個共享目标，加載器不會像它通常所做地那樣将控制傳遞給應用
而是加載和運作這個動态連結器，然後動态連結器通過執行下面這些重定位完成連結任務：
7.11 從應用程式中加載和連結共享庫
應用程式還可能在它運作時要求動态連結器加載和連結某個共享庫
而無需在編譯時将那些庫連結到應用中
Linux系統為動态連結器提供了一個簡單的接口，允許應用程式在運作時加載和連結共享庫：
示例：
7.12 位置無關代碼
1.PIC資料引用
編譯器通過運用以下這個有趣的事實來生成對全局變量的PIC引用：
無論我們在記憶體中的何處加載一個目标模闆，資料段與代碼段的距離總是保持不變
是以，資料段中任何指令和資料段中任何變量之間的距離都是一個運作時常量，與代碼段和資料段的絕對記憶體位置是無關的
想要生成對全局變量PIC引用的編譯器利用了這個事實，它在資料段開始的地方建立了一個表，叫做 全局偏移表(Global Offset Tab, GOT)
在GOT中，每個被這個目标子產品引用的全局資料目标都有一個8位元組條目
編譯器還為每個條目生成一個重定位記錄，在加載時動态連結器會重定位GOT中dem
在加載時，動态連結器會重定位GOT中的每個條目，使它包含目标的正确的絕對位址
上圖展示的是 編譯于 7.6.2小節的代碼
這裡的關鍵思想是對GOT[3]的PC相對引用中的偏移量是一個運作時變量
因為addcnt是由libvector.so子產品定義的，編譯器可以利用代碼段和資料段之間不變的距離，産生對addcnt的直接PC相對引用，并增加一個重定位，讓連結器在構造這個共享子產品時解析它
2.PIC函數調用
使用延遲綁定的動機是對于一個像libc.so這樣的共享庫輸出的成百上千函數中
一個典型的引用程式隻會使用其中很少的一部分
把函數位址的解析推遲到它實際被調用的地方，能避免動态連結器在加載時進行成百上千個其實并不需要的重定位，第一次調用過程的開銷很大，之後的每次調用都隻會花費一條指令和一個間接的記憶體引用
延遲綁定是通過兩個資料結構之間簡潔但又有些複雜的互動實作的
GOT和過程連結表(PLT)
如果有一個目标子產品調用定義在共享庫中的任何函數，那麼它就有自己的GOT和PLT
GOT是資料段的一部分，PLT是代碼段的一部分
上圖展示了PLT和GOT如何協作在運作時解析函數的位址
7.13 庫打樁機制
庫打樁，它允許你截獲對共享庫函數的調用，取而代之執行自己的代碼
打樁可以發生在編譯時、連結時、目前程式被加載和執行的運作時
7.13.1 編譯時打樁
上圖展示了如何使用C預處理器在編譯時打樁
使用下面這樣編譯和連結這個程式：
由于使用 -I 參數，是以會進行打樁，他告訴C預處理器在搜尋通常的系統目錄之前，先在目前目錄中查找malloc.h，注意mymalloc.c中的包裝函數是使用标準 malloc.h頭檔案編譯的
運作結果：
7.13.2 連結時打樁
Linux靜态連結器支援用 –wrap f标志進行連結時打樁
這個标志告訴編譯器 把對符号f的引用解析成 __wrap_f
還要把符号 __real_f的引用解析成 f
-Wl, option标志把 option 傳遞給連結器
Option中的每個逗号都要替換為一個空格
–wrap,malloc 就把 –wrap malloc 傳遞給連結器，以類似的方式傳遞
-Wl,–wrap,free
結果：
7.13.3 運作時打樁
運作時打樁，它隻需要能夠通路可執行目标檔案
這個很厲害的機制基于動态連結器的LD_PRELOAD環境變量
7.14 處理目标檔案工具
小結