下面就要進入本書的第二部分——在系統上運作程式。書的第一部分，主要是研究單個應用程式，關注的是資料類型、機器指令、程式性能、存儲器系統等話題。在書的第二部分，我們繼續對計算機系統的探索。現代作業系統與硬體合作，（程序的概念、虛拟存儲器）為每個程式提供一種假象，好像這個程式是計算機上唯一運作的程式。實際上在任何時間點，計算機上都有多個程式在運作。

連結（Linking）是将各種代碼和資料收集起來組合成一個單一檔案的過程。連結是由連結器（Linker）完成的。連結器在軟體開發中扮演着一個關鍵的角色，因為它使分離編譯成為可能——我們不用将一個大型程式組織為一個巨大的源檔案，而是把它分解為更小、更好管理的子產品，我們可以獨立修改和編譯這些子產品。當我們修改一個子產品時，隻需重新編譯這個子產品，重新連結即可，不必編譯其他檔案。

特别是在現在的 IDE 都比較發達的情況下，連結通常是默默無聞的。當我們寫好代碼，按下“編譯并運作”的按鍵時，我們通常不會很注意連結的過程。那學習連結的概念有什麼好處呢？

幫助你構造大型程式
避免一些危險的程式設計錯誤
了解語言的作用域規則
了解其他重要系統概念，（加載和運作程式、虛拟存儲器、分頁、存儲器映射、共享庫）

編譯系統

預處理器（cpp）：根據 # 開頭的的指令，修改原始的 C 程式。會将源代碼 hello.c 轉變為 hello.i ，是被修改後的源檔案。
編譯器（cc1）：将文本檔案 hello.i 翻譯成 hello.s ，它就是 C 代碼對應的彙編語言程式。彙程式設計式是很有用的，它以一種标準的文本格式描述低級的機器語言指令，也就為不同進階語言的不同編譯器提供了通用的輸出語言。
彙編器（as）：将 hello.s 翻譯成機器語言指令，并打包成可重定位目标程式（relocatable object program）的形式，儲存在 hello.o 中。 hello.o 是一個二進制檔案，位元組編碼是機器語言指令。如果直接用文本編輯器打開二進制檔案，将會看到亂碼。
連結器（ld）：将對象程式 hello.o 和所需要的靜态庫 lib.a 經過連結器的處理，最終成為一個可執行目标檔案。例如，這個 hellowolrd 程式用到了函數 printf ，這個函數就存在一個名為 printf.o 的單獨編譯好的目标檔案。連結器就負責合并兩個目标檔案，得到一個可執行目标檔案（executable object file），簡稱可執行檔案 hello.exe
加載器（loader，shell 調用）：将可執行檔案加載到記憶體中執行。

假設我們寫了兩個 C 語言代碼，分别是

main.c

和

sum.c

，前者中代碼用到了後者中定義的函數。兩者分别經過編譯過程（cpp、cc1、as）之後，生成可重定位目标檔案

main.o

sum.o

，最後，執行連結操作：

ld -o sum main.o sum.o

就得到可執行檔案

sum

。

連結的基本知識

下面來了解一些關于連結的術語。

靜态連結

Unix 下

ld

程式，叫做靜态連結器，以一組可重定位目标檔案和指令行參數作為輸入，生成一個完全連結，可以加載運作的可執行目标檔案做為輸出。

目标檔案

三種形式：

可重定位目标檔案。包含二進制代碼和資料。可以在連結時與其他可重定位檔案結合起來，建立一個可執行目标檔案
可執行目标檔案，可以被拷貝到存儲器中執行。
共享目标檔案，一類特殊的可重定位目标檔案，可以在加載或運作時動态地加載到存儲器中并連結。

目标檔案純粹是位元組塊的集合，有的塊包含程式代碼，有的儲存資料，或者指導連結器和加載器的資料結構。連結器對目标機器知之甚少，編譯器和彙編器已經完成了大部分工作。

各個系統之間，目标檔案格式不盡相同。下面讨論的是 Unix 可執行和可連結目标檔案格式（Executable and Linkable Format，ELF）。雖然我們的讨論集中在 ELF 上，但是不管是那種格式，基本概念是互通的。

連結器做了什麼？

連結器主要是将有關的目标檔案彼此相連接配接生成可加載、可執行的目标檔案。連結器的核心工作是：

符号解析（symbol resolution）
重定位（relocation）

符号表

來看一下典型的 ELF 可重定位目标檔案的格式。

節	内容
ELF header	描述生成該檔案的系統的字的大小、位元組順序、目标檔案類型、機器類型等，幫助連結器文法分析和解釋目标檔案的資訊
.text	編譯後的機器代碼
.rodata	隻讀資料
.data	已初始化的全局變量
.bss	未初始化的全局變量，在目标檔案不占實際空間，是“better save space”的縮寫
symtab	符号表，存放在程式中定義和引用的函數與全局變量的資訊
.rel.text	.text節的重定位資訊，當連結時，指令的位置就被修改
.rel.data	.data節的重定位資訊，當連結時，變量的位置就被修改
.debug	調試符号表
Section Header Table	節頭部表，存放每個節的偏移和大小

每個可重定位目标子產品 m ，都有一張符号表。符号表實際上是一個結構體數組，每一個元素包含名稱、大小和符号的位置。符号表存放如下三種符号：

在 m 中定義，且能被其他子產品引用全局符号，也就是不帶 static 的全局變量。
在其他子產品中定義，并被 m 引用的全局符号，是其他子產品中的全局變量或者函數。這些符号叫做外部符号（external）
在 m 中定義的帶 static 的全局變量，這些符号對 m 是随處可見的，但不能被其他子產品所引用。

我們知道，局部變量會由棧來管理。局部靜态變量，會存放到

.bss

或者

.data

節中，也不由符号表來管理。

符号解析

連結時，符号解析就是将對每個符号的引用與它輸入的可重定位目标檔案的符号表中的一個确定的符号定義聯系起來。

看下面兩張圖，可以了解符号表的作用，以及連結器對哪種類型的符号感興趣：

符号解析的過程：對定義和引用在相同子產品中的本地符号，符号解析相當簡單。編譯器隻允許每個子產品中每個本地符号隻有一個定義。不過，對全局符号的引用解析就麻煩得多，當編譯器遇到一個不是在本子產品中定義的符号（變量名或函數名）時，它會假設這是在某個其他子產品中定義的，并把後續工作交給連結器處理。如果連結器在所有的子產品都找不到這個被引用的符号的定義，它就會輸出報錯資訊并終止。一般來說，報錯資訊就是：undefined reference to something。

解析多重定義的符号

符号解析時，符号有強弱之分：

強符号：函數和初始化的全局變量。
弱符号：未初始化的全局變量。

根據下面的規則來處理多重定義的符号：

不允許有多個重名強符号。
如果有一個強符号和多個弱符号，選擇強符号
多個弱符号，那麼就從中任意選擇一個。

在上圖的

main.c

中，

time

是弱符号，其餘的符号是強符号。

如果說在兩個不同的檔案中定義了同名的函數，由于函數都是強符号，連結時就會報錯。

下面看一個特殊的例子：

//檔案1
#include<stdio.h>
void f(void);

int x = 15213;
int y = 15212;

int main()
{
    f();
    printf("x = 0x%x y = 0x%x \n", x, y);
    return 0;
}

//檔案2
double x;
void f()
{
    x = -0.0;
}

實驗結果如下，可以看到，變量 y 的值也被改變了。

上述代碼的問題在于，檔案2中定義的變量 x 是弱定義，在調用 f 函數對 x 進行寫入的時候，實際上操作的應該是檔案1中定義的強符号。在檔案2中，x 的類型是 double，占 8 個位元組，指派語句

x = -0.0

會導緻檔案1中定義的強符号 y 的資料也被覆寫。在 linux 下，編譯會發出一條警告，提示我們，兩個同名符号的大小不同。

由上面的例子可以知道，對連結知識的不了解，可能導緻意想不到的錯誤，而且編譯器不會報 error。是以，我們可以得到一些很重要的程式設計經驗：

避免使用全局變量
如果一定要使用全局變量：
- 加上 static ，使其成為靜态變量。
- 定義全局變量時初始化，使其成為強符号。
- 使用 extern 來辨別是從其他子產品引用的全局符号。

重定位

重定位就是當連結器完成了符号解析這一步之後，連結器就知道了輸入子產品的代碼節和資料節的确切大小，可以開始重定位了。看下圖：

重定位說白了就是把不同可重定位對象檔案拼成可執行對象檔案。在這個合并的步驟中，為每個符号配置設定運作時位址。

重定位分兩步：

重定位節和符号定義（合并）。将所有相同的節合并為新的聚合節。然後，連結器确定運作時存儲器位址賦給新的節，再根據偏移量賦給每個符号。此時，程式中的每個指令和全局變量都有唯一的運作時位址了。
重定位節中的符号引用。連結器修改代碼節和資料節中對每個符号的引用，使其指向正确的運作時位址。

下面是一個實驗，源檔案

relocation.c

如下：

int sum(int *a, int n);
int array[2] = {1, 2};
int main()
{
    int val = sum(array, 2);
    return val;
}

源檔案

sum.c

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

使用指令：

gcc -c relocation.c -o relocation.o

，-c 選項的意思是隻編譯不連結，我們可以由此得到可重定位目标檔案。

objdump -r -d relocation.o

反編譯對應的可重定位對象檔案，可以得到如下的彙編代碼：

全局數組

array

需要重定位。call 指令調用函數

sum

，這也是一個需要重定位的符号。我們将目光移到 call 指令這一行。

e8

是

call

的位元組編碼，可以看到，後面的操作數都是零，就是留出位置讓連結器在連結的時候填上對應的實際記憶體位址。同理

bf

mov

的位元組編碼，

array

的首位址也是連結完成後才知道的，是以還沒有确定位址。

call 指令的下一行，有一句

13: R_X86_64_PC32 sum-0x4

，這個東西叫做重定位條目（relocation entry），無論何時彙編器遇到了對最終位置未知的符号引用，就會生成一個重定位條目，也就是存放在

.rel.text

.rel.data

節中的資料。

objdump

為了友善，将彙編代碼和重定位條目放到一起顯示，雖然他們實際存儲不在一起。

PC相對引用重定位

我們現在來看一下連結器如何确定 call 調用的實際位置。重定位條目

13: R_X86_64_PC32 sum-0x4

告訴連結器要修改位于目标檔案偏移量 0x13 （數一下機器編碼的位元組數，可以發現 call 指令剛好是第 0x13 個位元組）的 PC相對引用（PC是指程式計數器），使得它在運作時指向 sum 的偏移量

-0x4

位置。

使用指令

gcc -o relocation relocation.c sum.c
objdump -dx relocation

在可執行檔案的反彙編代碼中找到 main 這一節，main 的位址是

0x4004d6

，sum 的位址是

0x4004f5

。這也就是連結器為節選擇了運作時位址。

ADDR(.text) = 0x4004d6
ADDR(sum) = 0x4004f5

//計算引用的運作時，程式計數器的位址
refaddr = ADDR(.text) + offset = 0x4004d6 + 0x13 = 0x4004e9

//是以 call 的目标位址是 （第二個refptr是 0 ，計算前 call 後的操作數）
*refptr = unsigned(ADDR(sum) - refaddr) -0x4
        = unsigned(0x4004f5 - 0x4004e9) -0x4
        = 0x8

以上就是 PC 相對重定位的過程。連結器将結果填入可執行目标檔案，call 指令有了如下的重定位形式：

4004e8:     e8 08 00 00 00          callq   4004f5 <sum>

絕對引用重定位

對于全局數組

array

的重定位條目：

e：R_X86_64_32 array

，重定位條目告訴連結器，這是一個絕對引用，将要修改位于目标檔案偏移量 0xe 的絕對引用，使其指向符号

array

。絕對引用就相對簡單，隻需要把連結器确定的數組開頭的運作時位址，即

&array[0]

填入相應的地方即可。

共享庫

我們目前為止做的工作都是連結器讀取一組可重定位目标檔案，并把它們連結起來。那在處理一大堆常用的标準函數，例如

printf、scanf、malloc

等，我們要怎麼做呢？

思路1：讓編譯器辨認出對标準函數的調用，生成相應的代碼
- 缺點：對于有大量标準函數的程式設計語言，這種方法會顯著增加編譯器的複雜性。
思路2：将所有的标準函數放到一個單獨的可重定位目标檔案中，程式員将其與他們自己的目标檔案連結生成可執行檔案。
- 缺點：這樣做的話，對于每個可執行檔案，都存在一份所有标準函數的集合，很浪費空間。
思路3：将每個标準函數建立一個獨立的可重定位目标檔案，然後連結的時候顯示地連結标準函數
- 缺點：耗時，容易出錯。

共同的缺點：對于标準函數的任何改變，都需要修改新的編譯器版本或要重新編譯整個可重定位目标檔案，這十分耗時。

解決的方法就是引入庫（library）的概念。

靜态庫

比較老式的做法就是所謂的靜态庫（Static Libraries,

.a

字尾表示 archive files，歸檔檔案）。

靜态庫是一個外部函數與變量的集合體。靜态庫的檔案内容，通常包含一堆程式員自定的變量與函數，在編譯期間，靜态庫沒有把全部内容連結，隻是把需要的代碼連結進去這個可執行檔案與編譯可執行檔案的程式，都是一種程式的靜态建立（static build）。

具體過程就是把不同檔案的 .o 檔案通過 Archiver 打包成為一個 .a 檔案。Archiver 支援增量更新，如果有函數變動，隻需要重新編譯改動的部分。

在 C 語言中最常用的是 C 标準庫與 C 數學庫。C 标準庫一般可以通過 libc.a 來進行引用，大小 4.6 MB，包含 1496 個對象檔案，主要負責輸入輸出、記憶體配置設定、信号處理、字元串處理、操作資料、生成随機數及整型的數學運算。C 數學庫可以通過 libm.a 來引用，大小 2 MB，包含 444 個對象檔案，主要是提供浮點數運算的支援（比如三角函數、幂次等等）

下面看一個具體例子，各個檔案代碼如下：

使用如下指令：

隻編譯不連結，獲得兩個目标檔案：
gcc -c addvec.c multvec.c

将兩個目标檔案打包成一個字尾為 .a 的靜态庫：
ar rcs libvector.a addvec.o multvec.o 

使用靜态庫連結
gcc -c main.c -o main.o
gcc -static -o p main.o ./libvector.a

-static 參數告訴編譯器，連結器應當建構一個完全連結的可執行檔案。

連結器會判斷：

addvec.o

中的符号

addvec

被

main.o

引用，是以拷貝這個子產品到可執行檔案。由于沒有用到

multvec.o

中的符号，是以不會拷貝這個子產品到可執行檔案。此外，由于用到了函數

printf

，連結器還會拷貝

libc.a

中的

printf.o

子產品，以及許多其他運作時需要用到的子產品。下圖很清晰的展現了靜态庫的好處：

動态連結共享庫

靜态庫仍有缺點：需要定期維護和更新。如果程式員想要用一個庫的最新版本，那麼就必須先更新該庫，然後再将更新的庫與他們的程式重新連結。以及，幾乎每個 C 程式都要用到标準 I/O 函數，例如

printf

scanf

之類。按照靜态庫的思路，這些代碼會被拷貝到每個運作的程序的文本段中，在一個運作了幾十個程序的系統上，會造成存儲器資源的極大浪費。

共享庫（shared library）就是緻力解決靜态庫缺陷的現代創新産物。共享庫是一個子產品，可以在運作時加載到任何的存儲器位置，并和一個存儲器中的程式連結起來。這個過程就叫動态連結（dynamic linking），由動态連結器（dynamic linking）來完成。

共享庫也叫共享目标（shared object），在 Unix 系統下常用字尾名 .so 來表示。在 Windows 中大量利用了動态連結庫，就是 DLL（dynamic linking library）。

如果還是以上面的例子，但是以動态連結的方式，工作原理如下圖：

建立一個共享的目标檔案
gcc -shared -fPIC -o libvector.so addvec.c mutlvec.c

建立可執行目标檔案 p2，這個檔案的形式是可以在運作時與 libvector.so 動态連結
gcc -o p2 main.c ./libvector.so

-fPIC 訓示編譯器生成與位置無關的代碼。目的就是允許多個正在運作的程序共享存儲區中相同的庫代碼，節約了存儲器空間。

基本的思路是：建立可執行檔案時，靜态地執行一部分連結，當程式被加載運作時，動态地完成剩餘的連結過程。

可執行目标檔案、加載運作

下圖可以看到一個可執行目标檔案的形式，它是由多個目标檔案合并而來的。我們最開始的 C 源代碼，是一個 ASCII 碼檔案，已經被轉換成一個二進制檔案，包含了加載程式且運作它所需的所有資訊。

運作可執行目标檔案，就是在外殼中輸入它的名字，外殼會調用一個叫做加載器（loader）的作業系統代碼來運作它。加載器将可執行目标檔案的代碼和資料從磁盤拷貝到存儲器中，然後跳轉到程式的入口點，運作該程式。

總結

連結是一種運作程式由多個目标檔案構造得來的技術。連結可以發生在編譯時（靜态連結）、加載時、運作時（動态連結）。了解連結的相關知識點，我們從代碼級進入到系統級，有益于我們了解作業系統是如何完成各種複雜工作的。

參考連結

CMU 2017年春季學期 ICS課程網站
wiki -靜态庫
C編譯器、連結器、加載器詳解

【CSAPP筆記】13. 連結