novus log

之所以會有這篇文章，源於前天發生的一件笨事。我正在為手邊新專案撰寫 CMakeLists，結果在編譯某個 DLL 的時候出現錯誤，主要的訊息是一堆 "Undefined reference to..."。

我對這類的玩意還算蠻有經驗的，快速確定了該連結的東西都有寫到，剩下比較有可能的大概就是連結順序的問題。但這實在不太可能發生，我一向非常留意這些細節。

可是我再三確認 CMakeLists 當中撰寫的順序，卻找不出所以然。不由得讓我有點驚恐，莫非我對 ld 的知識一直有誤？又或者 CMake 會亂調連結順序？

於是我花了大半天的時間用 nm 檢查有關的目的檔內符號名稱是否正確、在 CMakeLists 中亂印 message，最後終於找到禍首。原因是我有一個 CMake function 有名字的引數多了一項，這十之八九是複製貼上造成的，導致於某些情況下 ARGN 會少一項，其他的就不用多說了。簡而言之就是兩個字：手殘，和連結順序完全無關。

這個結果還蠻讓人失望的，我以為像這種特殊事件有機會增加某些特殊知識，又或者可以糾正自己未發現的錯誤認知，畢竟耽誤了大半天的時間總該有點收穫吧。不過至少確認了我對連結順序的理解大致上正確，而且補充了 DLL 連結方面的知識，也不算毫無所得。更重要的教訓或許是，先入為主的假設往往會帶人遠離現實。

言歸正傳，我對連結器的知識是在很長一段時間裡，從許多不同管道零散吸收而來，想藉這個機會做個整理和網友分享。以下的資訊只適用於各平台上相容於 GNU Binutils 的工具，其他牌的 toolchain 未必採用相同規則。另外，以下討論的是建置時期的連結，不牽涉到執行期查找動態程式庫的行為。

為了方便起見，本文統一透過 g++ frontend 呼叫連結器，而不直接呼叫 ld。

基礎知識

GNU ld 最基本的連結單位是 object 檔，即單一個編譯單元所對應的編譯結果，通常副檔名是 .o。在 object 檔所維護的資訊當中，連結器主要關注的是：

• 輸出符號: 這是定義在 object 檔內，且可提供給外界使用的符號。
• 未定義符號: 這是被 object 檔使用、需要從外部提供的符號。

連結器的工作就是找出每一個 object 檔的未定義符號到底被哪一個 object 檔提供，最後組合成目的檔（target）。

對 ld 來說，要的話就是把整個 object 檔連結進來，不然就是整個 object 都不需要。即使一個 object 檔當中只有少許的符號被使用，object 的其他內容照樣會被連結入最終的目標檔。

這就是為什麼一些 hello world 等級的程式會出人意料肥大的原因，我看過不少不明究理的人拿這點抱怨「編譯器」很爛，生成一堆垃圾程式碼云云，每次看到這種話我都很想幫「編譯器」叫屈，其實只要連結到一些專攻小體積的標準程式庫，目的檔馬上就小了。

對於標準程式庫作者來說，若希望使用者只連結確實用到的程式，最簡單的作法就是把編譯單元拆得細一點，最好一個檔案只放一個函數、變數，這個原則在現實中的 C 程式庫很常見。這種做法對於比較容易切割的基礎程式庫還算合理，若是複雜度比較高的高階程式庫也想比照辦理，可能隨便一個 C++ class 就要分成二三十個檔案來寫。This is not Sparta, this is MADNESS！

單純的 object 檔連結

當輸入是單純的 object 時，有一個很簡單的演算法可以完成工作。首先，ld 必須維護兩組資料：

• 到目前為止已經知道定義在何處的符號清單，以下簡稱「已知清單」。
• 到目前為止需要使用，但還不知道定義在何處的符號清單，以下簡稱「未知清單」。

每當 ld 讀入一個 object 檔時：

• 首先將該 object 所有的輸出符號加入已知清單，如果該 object 的輸出符號和已知清單中的符號衝突，連結器會吐出多重定義（multiple definition）錯誤。
• 若未知清單內的符號可在 object 的輸出符號當中找到，則將這些項目從未知清單中移除。
• 運用已知清單解析 object 的未定義符號，最後將無法解析者加入未知清單。

重複以上步驟，直到命令列中的 object 檔都被處理完。當完成後若未知清單沒有被清空，ld 會吐出未定義參考（undefined reference）錯誤。

在輸入只包含單純的 object 檔時，上面的演算法不受讀入 object 檔的順序影響。不過處理靜態程式庫當中的 object 時，情況變得有點不一樣。

連結靜態程式庫

靜態程式庫其實只是將一堆 object 檔打包在一起而已，連結器會逐一掃描靜態程式庫中的各個 object，決定是否要將這個 object 加入連結。

• 首先，ld 會看這個 object 的輸出符號是否有助於減少未知清單中的項目，若一個 object 無法提供未知清單中的符號，就會被 ld 略過，而且沒有其他因素的話 ，ld 將不會回過頭再次處理同一個 object。
• 如果 object 輸出的符號可以解決未知清單中的某些項目，那麼 ld 就會將 object 加入連結，和前述加入 object 的流程一樣。
• 當靜態程式庫中的某個 object 被加入連結，而且這個 object 引入新的未定義符號，那麼 ld 會重頭掃描同一個靜態程式庫，試圖找出、並連結這些未定義符號所在的 object 。如果這個步驟加入的 object 又引入新的未定義符號，同樣的流程會一直重複，直到沒有新的未定義符號為止。

在這個規則之下，同一個靜態程式庫內的 object 並不受連結順序影響，但只要連結跨越靜態程式庫邊界，順序就會是個問題。舉個簡單的例子，假如我們有三段 C++ 原始碼如下：

bar.cpp :

void bar()
{
    puts("bar()");
}

foo.cpp :

void bar();

void foo()
{
    puts("foo()");
    bar();
}

main.cpp :

void foo();

int main()
{
    puts("main()");
    foo();
}

如果只使用 object 檔連結，如前面所述，順序不會造成任何問題。

g++ -c main.cpp foo.cpp bar.cpp

# Linking order won't matter
g++ -o app.exe main.o foo.o bar.o
g++ -o app.exe foo.o bar.o main.o
g++ -o app.exe bar.o main.o foo.o

但是如果把其中某些原始檔包成靜態程式庫，連結順序就會是個問題。

# ok
g++ -o app.exe main.o libfoo.a libbar.a     

# [Fail 1] undefined reference to `foo()'
g++ -o app.exe libfoo.a libbar.a main.o    

# [Fail 2] undefined reference to `bar()'
g++ -o app.exe main.o libbar.a libfoo.a

以 Fail 1 為例：連結器首先看到 libfoo.a，此時未知清單沒有任何需要解析的符號，因此 libfoo.a 當中的 object 都會略過，同樣的事情也發生在 libbar.a 身上。到了 main.o 時，雖然所需要的 foo() 在之前出現過，但相關的 object 已經被忽略，所以發生 undefined reference。

再來看 Fail 2：首先，main.o 引入 foo() 到未知清單中。當連結器看到 libbar.a 時，未知清單只需要 foo()，這是 libbar.a 的 object 所無法提供的，於是會被略過。libfoo.a 可以提供 foo() 的需求，因此這個 object 會被加入連結，但這個 object 所需的 bar() 卻再也無法獲得滿足。

以上會得出很多人應該都知道的經驗法則：

如果一個程式庫 A 需要依賴程式庫 B，在連結命令中 A 應該要放在 B 之前。

一個比較有趣的情況是循環依賴，也就是靜態程式庫 A 依賴靜態程式庫 B，同時 B 也依賴 A 的情形。如果我們將前例中的 bar.cpp 改成:

bar.cpp :

void foo();

void bar()
{
    puts("bar()");
    foo();
}

以下面順序可以連結成功:

g++ -o app.exe main.o libfoo.a libbar.a 

但是以下面順序則會失敗:

g++ -o app.exe main.o libbar.a libfoo.a

連結 SO 檔

就我的理解，ld 似乎是將 SO 當成單獨的連結單位處理，類似處理單一 object，不過我對這點不是那麼肯定。無論如何，當多個 SO 檔連結時，順序並不會影響結果。

連結 DLL 檔

MinGW 所提供的 ld 可以透過兩種方式連結 DLL。傳統 Windows 程式設計的做法是幫每一個 DLL 生成對應的靜態程式庫，這個靜態程式庫只是媒介，讓連結器能夠解析符號而已。 由於使用的是靜態連結的規則，因此會受到輸入順序影響。

另一方面，用 GNU toolchain 生成的 DLL 有一些特別的設計，可以不透過中介的靜態程式庫直接連結。 這種連結方式和 SO 一樣不受連結順序影響。

不過 DLL 和 SO 還是有一個顯著的區別，生成 DLL 的過程必須把所有未定義符號解決，不像生成 SO 可以存而不論。

改變預設行為的參數

如果 ld 預設行為真的沒辦法把事情擺平，有一些參數可以讓使用者做進一步的指定。

-start-group 和 -end-group

前面說過，若靜態程式庫中的 object 有無法解析的未定義符號，ld 會掃描同一個靜態程式庫的 object，試圖解決這些未定義符號。

透過 -start-group 和 -end-group 指定多個靜態程式庫為同一群組，可令 ld 重新掃描的範圍擴大到同群組內的所有 object。這是 ld 的參數，所以透過 gcc 或 g++ frontend 呼叫別忘了加 -Wl。

g++ -o app.exe main.o -Wl,-start-group libbar.a libfoo.a -Wl,-end-group

由於重新掃描的範圍變大，而且上面的演算法複雜度為 object 數量的平方，可想而知在一些比較極端的情況下會使連結速度明顯變慢。

--whole-archive 和 --no-whole-archive

另外 ld 的 --whole-archive 可以強制將緊接其後的程式庫全部都連結進來，不管個別 object 使否實際被使用到。遇到 --no-whole-archive 之後的程式庫又會以「正常」方式連結。

g++ -o app.exe main.o -Wl,--whole-archive libbar.a -Wl,--no-whole-archive libfoo.a 

由於這個方式不分青紅皂白把所有 object 都連結進來，不管 object 是否確實被使用，所以目的檔很可能會變得很肥大。

結語

其實對一般人來說，這篇文章大部份的內容沒那麼重要，真正的重點只有這個常識：「如果一個程式庫 A 需要依賴程式庫 B，在連結命令中 A 應該要放在 B 之前」。不過在一些比較奇怪的程式庫相依關係下，多了解一點還是有助於故障排除。

雖然 ld 提供了一些進階的選項，但不容易透過 CMake 這類的高階工具使用。