之所以會有這篇文章,源於前天發生的一件笨事。我正在為手邊新專案撰寫 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 這類的高階工具使用。

arrow
arrow
    全站熱搜

    novus 發表在 痞客邦 留言(2) 人氣()