linker (ld) 在做 symbol resolving 的 order 跟過程

嘗試想要從 linker 中偷到一些有用的資訊來判斷 caller 跟 callee 之間的關係. 而 linker 的確夠複雜, 而且非常 undocumented, 因此記錄下來, 不僅分享, 也讓我當之後忘記這複雜的 detail 後不要重新推敲, 可以回頭看這篇文章即可.

1) 首先來說說 linker 在一堆 .so (shared library) 裡面找 undefined symbol 的過程:

若在 link 的過程中, 要在 command line 指定的多個 .so 檔中搜尋一個 undefined symbol, 搜尋的順序是以 breadth-first-search 的方式進行. 這是 ELF format 定義的方式:

(From ELF spec)
When resolving symbolic references, the dynamic linker examines the symbol tables with a breadth-first search.

這個就要舉例來說明了, 否則很難懂.

如果 link 時候的 command line 指定要 link a.so, b.so, c.so, 而 a.so 依靠 a_1.so, a_1.so 又依靠 a_2.so. c.so 依靠 c_1.so. 則以圖形表示如下:

--- a.so --- b.so --- c.so
      |                       |
      +--- a_1.so        +--- c_1.so
                 |
                 +--- a_2.so

這是一個 .so 的 tree, 所以尋找 undefined symbol 就以 breadth-first-search 來進行. 也就是會以下面的順序來尋找: a.so --> b.so --> c.so --> a_1.so --> c_1.so --> a_2.so

是的, 沒看錯, 就是這樣. ld 的確就是這樣在 .so 裡面找 undefined symbol 的.

2) 再來說說 linker 在一堆 .a 檔案 (archive, 也就是 static library) 裡面尋找 undefined symbol 的過程:

ELF 沒有定義這個過程,  或許是因為這個行為在 ELF 出來之前, 就存在各個 computer platform 了. 把一堆 .o 集合成一個 .a (archive) 是非常老舊也非常直覺的想法. 因此 ELF 沒有定義該怎麼辦, 而是各家的 linker 自己定義. 以 GNU linker (也就是 ld) 來說, 根據他的 user manual, 他是這樣說的:

(From ld user manual)

-larchive

--library=archive

Add archive file archive to the list of files to link. This option may be used any number of times. ld will search its path-list for occurrences of libarchive.a for every archive specified. On systems which support shared libraries, ld may also search for libraries with extensions other than .a. Specifically, on ELF and SunOS systems, ld will search a directory for a library with an extension of .so before searching for one with an extension of .a. By convention, a .so extension indicates a shared library. The linker will search an archive only once, at the location where it is specified on the command line. If the archive defines a symbol which was undefined in some object which appeared before the archive on the command line, the linker will include the appropriate file(s) from the archive. However, an undefined symbol in an object appearing later on the command line will not cause the linker to search the archive again. See the -( option for a way to force the linker to search archives multiple times. You may list the same archive multiple times on the command line. This type of archive searching is standard for Unix linkers.

注意上面用紅字標起來的句子, 其他的都可以先看成是輔助說明.

簡單來說, 就是若有 undefined symbol 要在一堆 .a 裡面找, 就是按照 .a 出現在 command line 的順序. 舉例來說, command line 裡面指定 a.a, b.a, c.a, 則有一 undefined symbol 要在這三個 .a 中尋找, 順序就是: a.a --> b.a --> c.a

不過有注意到上面貼出的 ld spec 裡面的最後幾句話嗎? 我重新紅色標出來關注一下:

(From ld user manual)
See the -( option for a way to force the linker to search archives multiple times. 

翻去 –( 那一節看, 可以看到:

(From ld user manual)

-( archives -)

--start-group archives --end-group

The archives should be a list of archive files. They may be either explicit file names, or `-l' options. The specified archives are searched repeatedly until no new undefined references are created. Normally, an archive is searched only once in the order that it is specified on the command line. If a symbol in that archive is needed to resolve an undefined symbol referred to by an object in an archive that appears later on the command line, the linker would not be able to resolve that reference. By grouping the archives, they all be searched repeatedly until all possible references are resolved. Using this option has a significant performance cost. It is best to use it only when there are unavoidable circular references between two or more archives.

所以說, .a 檔之間的 link order 沒有一定的順序, linker 有方法可以讓你循環 link, 也可以維持舊的模式, 也就是一直線 link, 不回頭找.

(附帶一提的是, GNU linkder 是為了古早的 COFF format 而寫的, 用在 ELF 上會非常沒效率, 因此 Google 自己寫了一套 for ELF 的 linker, 後來這套也被整合進 GNU 的 binutils 裡面, 而為了跟 GNU 自己開發的 ld 區別, 這個由 Google 自己開發的 linker 就叫做 gold. 網路上說 gold 的速度比 ld 快 5x 倍. 但也由於 linker 處理 .a 的方式沒有標準, 所以 gold 裡面的少許 rule 跟 ld 不一樣, 按照 Google RD 的說法是他覺得原本的 GNU ld 寫錯了... 但不管 GNU ld 是不是錯的, 目前有些軟體, 的確會因為這個 GNU ld 跟 gold 行為的些許不同而無法 compile, 例如 Linux kernel 目前只能使用 GNU ld 來 link)

3) 那再談談如果是 .so 跟 .a 之間, 該怎麼 link 呢?

這個同樣的, ELF 沒定義, 所以就看回 linker (ld) 的 user manual, 看 ld 怎麼自己定義這塊. 這邊就要看回上面 show 出的那段了, 這邊再 show 一次, 紅色標出重點部分.

(From ld user manual)

-larchive

--library=archive

Add archive file archive to the list of files to link. This option may be used any number of times. ld will search its path-list for occurrences of libarchive.a for every archive specified. On systems which support shared libraries, ld may also search for libraries with extensions other than .a. Specifically, on ELF and SunOS systems, ld will search a directory for a library with an extension of .so before searching for one with an extension of .a. By convention, a .so extension indicates a shared library. 

OK, 這代表甚麼意思呢? 這代表對 ld 來說, 不管是 static library (.a 又稱作 archive), 還是 shared library (.so), ld 都是一樣對待. 也就是說, 如果有一 undefined symbol 要在一堆 .a, .so 裡面定義, 那就是按照 command line 的順序來找. 例如: a.a b.so c.a d.so, 則 search 的順序會是 a.a --> b.so --> c.a --> d.so

等等, 剛剛不是說 .so 的搜尋順序是 breadth-first-search 嗎? 那這邊怎麼又定義了另一個呢? 這是很有趣的一個問題, 不過如果你仔細看看, 將會發現, 這個 a.a --> b.so --> c.a --> d.so 的順序並沒有違反 .so 之間的 breadth-first-search, 還是先找 b.so, 再找 d.so. Bingo~!

Ok, 那 .so 的第二層在整個搜尋的 order 中該怎麼放呢? 在做了一些實驗之後, 可以發現其實非常簡單, 第二層會放到最後面. 怎麼說? 以上面舉過的例子為例:

 --- a.so --- b.so --- c.so

      |                        |

      +--- a_1.so         +--- c_1.so

                  |

                  +--- a_2.so

如果加上幾個 .a

 --- a.so --- x.a --- b.so --- y.a --- c.so

       |                                           |

       +--- a_1.so                            +--- c_1.so

                  |

                  +--- a_2.so

則整個 search 的順序就會是 a.so --> x.a --> b.so --> y.a --> c.so (有看到就是按照 command line 的順序嗎?) --> a_1.so --> c_1.so --> a_2.so (有看到這邊就是按照 breadth-first-search 的順序嗎?)

所以兩個 rule 都沒被違反, 都遵守了. 又 follow ELF 的規定, 也沒改變原始 ld 的行為. Bingo~!

4) 不過事情當然沒有這麼簡單... 這要從 symbol table 說起:

每個 linking 任務, 最後都是要產生單一個 ELF 檔案, 若不是執行檔, 就是 .so (.a 不是 linking 而來的, .a 是透過 ar 組合而來的) 而每個 ELF 檔案裡面, 都有一個, 並且只有一個 symbol table. 這就是 ELF spec 裡面所說的 symbol table section:

(From ELF spec)
.symtab        This section holds a symbol table, as ‘‘Symbol Table’’ in this section describes.

當然還有所謂的 dynamic relocation table, 但那個可以先忽略不看. 基本上一個 ELF 檔, 就包含一個 symbol table, 裡面記錄了這個 ELF 檔 (執行檔或 .so) 定義了那些 symbol, 以及有哪些 symbol 使用到, 但沒定義.

這個在 linking 出一個 ELF 檔的過程中, 或 linking 完成, 執行一個 ELF 檔的過程, 都是一樣的, 都只有一個 symbol table. 只不過 linking 是要製作出這個 symbol table, 把它存在 ELF 檔中, 而執行過程是要取用這個 symbol table.

OK, 所以我們來看 linking 過程中的這個 symbol table 的情況. 製作這個 symbol table 的 rule 如下:

 - 如果 link 到一個 .o

就把這個 .o 所有定義的 symbol 寫到這個 symbol table 中, 並且也把這個 .o 所有使用到, 但找不到定義的 symbol 也寫到 symbol table 中, 然後標示成 undefined.

 - 如果 link 到一個 .a

這是 static library, 顧名思義, 稱作 library 就代表它不會主動提供 symbol 到 symbol table, 而是被動的被問有沒有 linker 想要的 symbol. 因此當 linker 看到一個 .a 時, linker 會去看看目前的 symbol table 有沒有任何 undefined symbol, 有的話, 就會去這個 .a 找看看, 有的話, 就會把這個 symbol table 中的 undefined symbol 改成 defined.

不過當然不會只有標成 define 這麼簡單, 而要真正的把 define 這個 symbol 的 "東西" 弄進來, 這個東西就是在 .a 裡面 define 這個 symbol 的 .o 檔. 還記得 .a 就是一堆 .o 的集合嗎? 因此 .a 裡面是以一個一個 .o 為單位的被 linker include 進最後的 ELF 檔中 (執行檔或 .so). 因此, 當 .a 檔中的某個 .o 因為有某個 symbol table 中的 undefined symbol 的定義而被 linker include 進來的同時, 也會連帶的把這個 .o 檔裡面的其他 defined symbol 也匯入到 symbol table 中. 所以可以把 .a 想成, 他既 『被動的』 提供 symbol, 也 『主動的』 提供 symbol. 是個很有趣的東西.

瞭解到這一點之後, 回想 .a 的 search 過程預設是單向的, 也就不足為奇了. 不過這邊要注意一點的是, 由於 linker 是把整個 .a 裡面的 .o 的所有 symbol 搬進 symbol table, 所以有可能會碰到 multiple definition 的問題. 瞭解了上面的運作原理後, 這個現象也就很容易理解了.

 - 如果 link 到一個 .so

這是 shared library, 同樣的, 顧名思義, 稱作 library 就代表它不會主動提供 symbol 到 symbol table, 而是被動的被問有沒有 linker 想要的 symbol. 因此當 linker 看到一個 .so 時, linker 會去看看目前的 symbol table 有沒有任何 undefined symbol, 有的話, 就會去這個 .so 找看看, 有的話, 就會把這個 symbol table 中的 undefined symbol 改成 defined. 

而接下來就是 .so 跟 .a 不同的地方了. 因為 .so 是 runtime 才會進行真正 link 的動作, 而在 compile time, linker 僅僅只是將 undefined symbol 改成 defined, 並且標註這個 symbol 需要在 runtime 時載入 xxx.so 到 process memory space, 然後就可找到想找的 symbol. 因此 .so 純粹只會提供 symbol 到 symbol table 中, 他不會 "主動" 匯入任何不想要的 symbol 到 symbol table 中. 基本上可以把 .so 提供 symbol 的 '界線' 想成是以 symbol 為單位, 而 .a 提供 symbol 的 '界線'  是以一個一個的 .o 為單位.

不過接下來將會看到一個我從實驗中觀察到的 trick, 我沒看過任何文件有提到這個 trick, 事實上, 討論 linker internal 的網頁資料少之又少, 所以底下所講的是我數次實驗後的解釋, 可以完美解釋目前我所有的實驗現象. 當然, 如果要證明這個 "假說", 使他變成 "定理", 那就是透過 trace binutils/ld 的 code 了. 這個 trick 就是, 雖然理論上, 在 .so 裡面找到 symbol table 中的 undefined symbol, 只會把 undefined 改成 defined, 而不會匯入任何 .so 當中其他的 symbol 到最後產出的 ELF 的 symbol table 中, 但實作上, 為了實作出 ELF 規格中規範的 breadth-first-search 行為, linker 會把 .so 裡面所有 defined, undefined 的 symbol 都一起匯入到 symbol table 中. 所以就這點來說, linker 是以 .o 為 '界線' 來處理 .a, 但卻以整個 .so 為 '界線' 來處理 .so. 因此 linker 在處理 .so 的時候, 先依序處理 command line 指定的 .so, 把這些 .so 裡的 symbol 匯入到 symbol table 後, 再依 breadth-first-search 的方式, 依序處理 level 2 的 .so (匯入 level 2 的 .so 的 symbol 到 symbol table 中), 然後再 level 3, 然後再 level 4, 然後再..., 最後當要產出最後的 ELF 檔時, 再把這些從 .so 匯入進來的 symbol 踢出最後的 symbol table.

所以簡單來說, 當 linker 看到 .so 時, 不管有沒有找到想要的 symbol for undefined symbol, 都會把 .so 擁有的 defined or undefined symbol 匯入到 symbol table 中. 不過跟 .a 不同的是, 如果 .so 裡面有跟 symbol table 同名的 symbol, linker 不會以為他是 multiple definition, 而會保持 symbol table 中原本的 symbol, 而丟掉 .so 檔裡面的 symbol. 這點是跟 .a 的處理是不同的.

以上這三條 rule 分別處理 .o, .a, .so. 熟記這三條 rule, 就可以通行無阻了. 讓我們看一個例子:

Command line 指定的是 main.c a.so b.a:

 - 在 main.c 中呼叫 func_b, 而 func_b 定義在 b.a 中

 - 在 b.a 中呼叫 func_a, 而 func_a 定義在 a.so 中

 - a.so 依靠 c.so

 - b.a 中除呼叫 func_a 之外, 還有呼叫 func_c, 而 func_c 定義在 c.so 中

因此最後的 caller/callee 關係為何呢? 為什麼這樣仍可以前前後後的 link 起來? 原因是完全符合上述三個 rule:

 - linker 先讀入 main.c 的 symbol, main (defined), 以及 func_b (undefined) 到 symbol table 中. linker 每發現 symbol table 內多了一個新的 undefined symbol 時, 就會先在 symbol table 內找看看是否能被 resolve, 但很可惜的, 以這一步驟的 symbol table 的狀態而言, 沒能找到 func_b 的 define, 所以 linker 就維持 func_b 仍是 undefined.

 - linker 再讀入 a.so 的 symbol, func_a (defined) 到 symbol table 中

 - linker 再看到 b.a 後, 發現 b.a 裡面有定義 func_b, 因此把 b.a 中的那個 .o 檔所具有的 symbol 匯入進 symbol table --> 原本的 func_b (undefined) 變成 func_b (defined), 並且還有 func_c (undefined) 也連帶的被匯入進來了. 注意到了嗎? Linker 此時一定又發現了一個新的 undefined symbol, func_c, 被匯入到 symbol table 了, 所以 linker 就嘗試在目前的 symbol table 中找有沒有 func_c 的存在, 但很可惜的, 仍然找不到, 所以 linker 就讓它繼續 undefined.

 - Linker 此時會看到 c.so (還記得 a.so 依靠 c.so 嗎?), 因此不管三七二十一的把 c.so 的 symbol 都匯入進來, 並且嘗試 resolve 已知的 undefined symbol, 也就是 func_c. Bingo~! 找到了, 因此就會將 func_c 從 undefined 改成 defined, 並記錄說 runtime 時, 要將 c.so 匯入到 process 的 memory space 來進行 runtime symbol resolving. 這就是 linker 全部的秘密了...

5) OK, 那如果加上 .o 呢?

這是甚麼情況呢? 以上面舉過的例子來說:

 --- a.so --- x.a --- b.so --- y.a --- c.so

        |                                          |

        +--- a_1.so                           +--- c_1.so

                   |

                   +--- a_2.so

就是加上幾個 .o, 變成:

 --- a.so --- i.o --- x.a --- b.so --- j.o --- y.a --- c.so

        |                                                            |

        +--- a_1.so                                             +--- c_1.so

                   |

                   +--- a_2.so

Rule 就是一樣的三條 rule. 因此順序是:

 1) linker 看到 a.so, 將 a.so 的 symbol 全部匯入

 2) 看到 i.o, 因為是 .o, 所以匯入, 並進行此時 symbol table 內的 undefined symbol 的 resolving

 3) ... (以下就不贅述了...)

6) 在瞭解了 linker 的 linking 過程後, 我們就可以來看看要怎麼讓 linker 自動告訴我們 caller 跟 callee 的關係

GNU ld (or gold) 有一個參數, 可以讓 linker dump 出 caller/callee 關係: 

因此只要像是下面這樣寫即可:

gcc main.c -lc -o a.out -Wl,-cref

然而, 很不幸的, 這個 --cref 只能告訴我們 .o, .a 彼此之間的 caller/callee 關係, 沒辦法告訴我們 .so 之間的關係. 所以假如我們想要瞭解全部的, 包括 .so 之間的 caller/callee 關係, 我們勢必得要做些 trick... dirty work...

7) Trick 就是把 .so 轉成 .a, 讓 -cref 可以順利的 dump 所有 .o, .a 之間的 caller/callee 關係 (沒有 .so 了, 因為全部被轉換成 .a)

OK. 不過因為 .so 的 search order 要符合 breadth-first-search, 且要符合 command line 內的 .o, .a, .so 仍要符合原本的 order. 所以我們得把每一 level 的 .so 分別做成 .a, 然後排列在新的 command line 中. 例如, 下面這個例子:

 --- a.so --- i.o --- x.a --- b.so --- j.o --- y.a --- c.so

        |                                                            |

        +--- a_1.so                                             +--- c_1.so

                    |

                    +--- a_2.so

新的全部都是 .a 的 command line 會是: a.a  i.o  x.a  b.a  j.o  y.a  c.a  a_1.a  c_1.a  a_2.a

如果你上面都瞭解的話, 你就會知道這是合理的. 不過如果你真的全部都懂的話, 你就會知道把 .so 全部改成 .a 是會有遇到 multiple definition 的問題風險在, 因此要加上一個允許 multiple definition 的 linker option:

(From ld user manual)

--allow-multiple-definition

-z muldefs

Normally when a symbol is defined multiple times, the linker will report a fatal error. These options allow multiple definitions and the first definition will be used.

8) 那要怎麼將 .so 轉成 .a 呢?

其實很簡單, 就是把組成 .so 的 .o 檔, 用 ar combine 在一起即可. 如果產生 .so 的 command line 有 .a 的話, 就要把 .a 解開, 組合到新的 .a 中. 如果產生 .so 的 cmd line 有 .so 的話, 就不理這個 .so 了, 因為我們會把這種下一 level 的 .so, 另外產生新的 .a.

這邊順帶一提的, 想要從 .so 檔直接看到直接下一 level 的 .so 可用 readelf –a | grep NEEDED 看:

9) OK, 所以如果要讓 linker dump 出所有 .o, .a, .so 之間的 caller/callee 關係, 整個的演算法如下:

如果你上面全懂的話, 這個演算法對你將會很直覺了.

lib source[];

lib result[];

foreach static_lib_X or dynamic_lib_Y or object_file_Z in command line

{

    Append static_lib_X or dynamic_lib_Y or object_file_Z into source[];

}

Foreach Obj in source[]

{

    Remove Obj from source[];

    if Obj is object file

    {

        Append Obj to result[];

    }

    if Obj is static lib

    {

        Append Obj to result[];

    }

    if Obj is dynamic lib

    {

        Covert this dynamic lib to static lib;

        Append this newly created static lib to result[];

        if (Obj is NOT system lib (ex: libc.so.6, ld-linux.so.2, libm.so.6, ...))

        {

            lib_Q = 『readelf -d Obj | grep NEEDED'; Append all lib_Q to source[];

        }

    }

    Append result[0]~result[n-1] to result[]; --> 這是為了模擬 dynamic lib 的 symbol 會全匯入到 symbol table 中的行為 

/* 因為只要 linker 讀入一個新的 ELF file 來 link, 他就會嘗試用它來 resolve symbol table 中的 undefined symbol, 也會用 symbol table 中的 defined symbol 來嘗試 resolve 該 ELF file 中的 undefined symbol, 為了模擬這個動作, 在不管加入 .o, .a 還是 .so (會轉成 .a) 後, 都需要重複一次之前塞入的 .a 來模擬當時的 symbol table */

}

Dump result[] to a string, then the string will be the new command line;

最後, 以上是我實驗跟閱讀文件的心得, 不代表一定正確. 若有能人異士指證了我的錯誤, 我會非常高興~ 代表我又多學了更多的東西.