# CS:APP Ch7 Linking # 為什麼要學習 Linking * 理解 linker (連結器) 幫助你建構大型程式 * 大型程式會包含許多 libraries ,了解如何 linking 可以幫助你處理棘手的編譯錯誤。 * 理解 linker 可以避免寫程式上犯下難以抓出的錯誤 * linker 執行 symbol resolution 所做的決定將大大的影響程式執行。 * 理解 linking 幫助你理解 [scope](https://en.wikipedia.org/wiki/Scope_(computer_science)) 的概念 * global 跟 local variable 之間的差別 * static 的作用 * 理解 linking 幫助你理解重要的系統概念 * 理解 linking 讓你更理解如何使用 shared library # Linking ![](https://i.imgur.com/BtgY0c9.png) Source code file 經過 1. cpp ( preprocessor ) 2. cc1 ( gcc compiler ) 3. as ( assembler ) 最終變為 `Relocatable object file` ( `relocatable` 代表此 file 可以再與其他 object file 結合),如同上圖中的 `main.o` 和 `sum.o` 。 Linker 將所需的 object file 結合為 `executable object file` ,如同上圖的 `prog`。 shell 呼叫作業系統中的 loader 將 executable object file 中的程式碼與資料複製到 main memory 中,並將控制權交給程式,讓它開始執行。 ```shell= $ ./prog ``` * preprocessor, compiler, assembler 和 linker 合稱為 compiler driver 。 # Why Linkers ? ### Modularity 共同的 Functions 可以被寫為 library 達到模組化的作用。 ### Efficiency * time : * 每次 Recompile 可以只對修改過的檔案編譯。 * separate compilation: 可以同時編譯多個檔案。 * space : * Common function 可以被放到同個檔案成為 libraries。 # What Do Linkers Do linker 將不同的 relocatable object file 作為輸入,最終產生可以載入且運行的 executable object file 。 ## Symbol resolution 在程式碼中,我們不斷的 define 或 reference symbol ,用以下例子來說明。 ```cpp void rand () { ... } /* 定義 symbol rand */ int main () { int a = 0; /* 定義 symbol a */ int *ptr = &a; /* 定義 symbol ptr, reference symbol a */ int b = rand (); /* 定義 symbol b, reference symbol rand */ } ``` 在 symbol rsolution 階段, linker 需要將每個 symbol reference 連結到正確且唯一的 symbol definition , symbol definition 則從所有的 relocatable object file 中的 symbol table 尋找。 在本篇[後面的章節](https://hackmd.io/00iwNBbDTlKk-foar0fq5g?view#How-linkers-resolve-Duplicate-Symbol-Definitions)有更細的討論。 ## Relocation 在 symbol resolution 章節中, linker 為每個 symbol reference 到一個 symbol definition ,這時 linker 就可以知道每個 module 的 `.text` 和 `.data` 確切大小,即可開始做 relocation 。 ![](https://i.imgur.com/63gI5Nf.png) ### Relocation section and symbol definition 各個 relocatable object file 都有 code 和 data sections ,這個階段會將分散在各個 file 相同類型的 section 合為單一的 section ,如同上圖所示。 Linker 替每個 symbol definition (每個 function 跟全域變數) 分配一個執行時的唯一 address 。 :::info 這邊也呼應到在區別宣告跟定義的時候,會將定義認定為替某個 symbol 分配記憶體空間,當 linker 在執行 linking 的時候,也是找出唯一的一個 strong symbol ,並為它分配一個執行時的唯一 address 。 ::: ### Relocation symbol reference 在 symbol resolution 步驟中,每個 symbol reference 都被連結到某一個 symbol definition ,在這個步驟就將 symbol reference 指到正確的執行時 address 。 經過上述兩個步驟後,最終產生 executable object file ,裏面的 `.text` 和 `.data` section 內的 symbol 都已經被重新定位, loader 可以直接將這些 section 複製到 memory 中即可開始執行程式,不需要再修改任何指令。 :::info reference 這個單字很常在 compile error log 中看到: ``` /tmp/asskutu.o(.txex+0x12): undefined reference to 'foo' ``` 這就是 linker 執行 symbol resolution 過程中,它無法為 `foo` 這個 symbol 找到一個 symbol definition 來 reference 。 ::: # Object file Object file 有以下三種格式,object file 可以理解為 module (.c file) 以 byte sequence 的形式儲存在磁碟中。 1. Relocatable object file (.o file) 2. Executable object file (a.out file) 3. Shared object file (.so file) ## ELF 在 linux 中,使用 Executable and Linkable **Format** 來作為以上三種 object file 的統一**格式**,這邊就不細講各個欄位。 > `.bss` 是用來儲存未初始化或是初始為0的全域或 static 變數,在 object file 中,他們是不佔記憶體空間的,在運行時才會分配記憶體,因此,`.bss` 可以記憶為 "Better Save Space" ,幫助區分 `.bss` 和 `.data` 。 下圖是一個典型的 reloctable object file 的 ELF 格式: ![](https://i.imgur.com/GLdyQm5.png) ![](https://i.imgur.com/d24pM0e.png) ## Executable object file ## 處理 object file 的工具 * ar : 用來建立 static libraries * strings : 顯示在檔案中可以列印的字串 * strip : 從 object file 刪除 debug symbol table 。在將 object file 放到目標環境之前,應該進行清理動作來縮小 object file * nm : 列出 object file 的 symbol * size : 顯示分區的名字和大小 * readelf : 顯示 elf 格式 object file 的資訊。包含 elf header 中的資訊,包含 size 和 nm 功能。 * objdump : 可以顯示 object file 的所有資訊。他最大功能用來 disassemble `.text` section 中的 binary format command 。 * ldd : 列出 object file 執行時所需的 shared libraries 。 # Symbol and Symbol table 在每個 relocatable object file 中都會維護一個 system table ,透過 `$ readelf -s` 可以看到的 `.symtab` section 就是 symbol table , 裏面紀錄著該 module 定義與引用 symbol 的資訊,有以下三種 symbol: * global symbols * module 自己定義的 global variable 或 function ,可以被其他 module reference 。 * external symbols * module 內 reference 別人定義的 symbol 。 * local symbols * 透過 static 宣告的 global variable 或 function ,無法被其他 module reference 。 :::warning Local variable **並不是** Local symbol ,local symbol 指的是以 static 定義的函式與變數,會被放在 ELF 中的 `.bss` 或 `.data` 區塊。 Local variable 是由 compiler 所負責的,執行時放在 stack 中進行管理,因此 Linker 對 local variable 是一無所知的。 ::: # Symbol resolution 執行 Symbol resolution 會面臨到一個問題,我們看以下例子, [func1.c] ```cpp int p = 1; func1 () { } ``` [func2.c] ```cpp int p; func2 () { } ``` `func1` 和 `func2` 都定義了名為 `p` 的 global symbol ,若是有人 reference `p` 這個 symbol 時, Linker 該怎麼去做 Linking ? 換句話說,若是有多個 module 都定義了相同名字的 global symbol , Linker 該怎麼去做 linking 呢? ## How linkers resolve Duplicate Symbol Definitions * 在編譯階段, Compiler 會將每個 symbol 分類為 **strong** 或 **weak** 。 * **Strong** Symbol : 包含 procedures 和被初始化過的全域變數。 * **Weak** Symbol : 未被初始化的全域變數。 * Assembler 會將 symbol 是 strong 還 weak 紀錄在 reloctable object file 的 symbol table 中。 * Linker 就可以藉此特性與 Linker's symbol rule 來解決上述的問題。 ### Linker Symbol's Rule Linker 利用以下列規則來決定如何做 Linking : 1. 同時存在多個同名的 strong symbol 是不允許的。 2. 假設有一個 strong symbol 與多個 weak symbol , Linker 應選擇 strong symbol 。 3. 如果只有多個 weak symbol ,任意選擇其中一個 。 透過以下例子來理解以上的概念: ### example 1 [foo1.c] ```cpp int x = 5566; int main() { return 0; } ``` [foo2.c] ```cpp int x = 666; void f() { } ``` 因為有兩個 strong symbol , Linker 會報出錯誤。 ### example 2 [foo3.c] ```cpp int x = 5566; int main() { f(); printf ("%d", x); return 0; } ``` [foo4.c] ```cpp int x; void f() { x = 64; } ``` 在 [foo4.c] 中的 `x` 是一個 weak symbol ,根據規則2, Linker 會將其 link 到 [foo3.c] 的 `x` ,但這邊會有一個問題,在 main 中你印出的值將變成 64 ,這對於 `main()` 的作者來說,應該不是預期的結果且相當討厭。 ### example 3 [bar1.c] ```cpp int y = 5566; int x = 1; int main () { f(); printf ("x = %d, y = %d", x, y); return 0; } ``` [bar2.c] ```cpp double x; void f() { x = 0.1; } ``` 在 [bar2.c] 的 `x` 是一個 weak symbol , Linker 會將其 link 到 [bar1.c] 的 `x` ,這邊除了存在類似範例 2 的問題,這兩個 symbol 還是**不同 type** , double 在我的機器上是 8 byte 大小,而 integer 是 4 byte 大小,因此在 `main()` 中, 因為 `x` 被轉變為 8 byte 大小, `y` 會因此被覆蓋... 這是一個細微難以察覺的 bug ,尤其是因為他只會觸發 Linker 爆出一條 warning ,且通常要在程式執行很久之後才會表現出來。 如果你懷疑這類問題,用像 `GCC-fno-common` 的 flag 來呼叫 linker ,這個 flag 告訴 linker 遇到多重定義的 global symbol 時,觸發一個錯誤,或者使用 -Werror 把所有 warning 視為 error 。 * 該如何避免這樣的錯誤呢? 儘量避免使用全域變數,如果要使用的話, 1. 如果可以的話使用 `static` 2. 確保全域變數都要初始化 3. 使用 `extern` 來標示你 reference 到外部的全域變數。不過若是在某個 file 忘記使用的話,依然會遇到一樣的問題... 範例3的錯誤若是在大型程式中,是個相當難發現的錯誤,這也是為什麼要了解 linking 是如何運作的。 # Loading Exectuable Object file ![](https://i.imgur.com/CgozrIy.png) # Linking with Libraries ## Static libraries 開發程式中,一定都會引用標準函式庫,裏面包含常見的函式,讓大家免於重新造輪子的痛苦,這樣的標準函式庫如同 reloctable object file 一樣可以作為 Linker 的輸入,同樣參與 symbol resolution 的過程, linker 只複製 static libraries 裡被 application 引用的目標 module 。 以下舉例 ![](https://i.imgur.com/tBSgLvR.png) 編譯所下指令為 ```shell $ gcc -static -o prog2c main2.o -L. -lvector ``` * `-static` 告訴 compiler driver , Linker 應該產生一個可以完全 Linking 的 Executable object file ,可以直接載入到記憶體執行,無需做其他 linking 動作。 * `-L.` 告知 Linker 當前目錄下尋找 library 。 * `-lvector` 則是 libvector.a 的縮寫。 * libc.a 是標準函式庫,不用特別在輸入中指定 對於 linker 來說,他會照著輸入到 compiler driver 的順序來做 Linking ,若是有 symbol reference 找不到對應的 definition,就會暫時紀錄下來,從接下來輸入的 library 和 object file 中繼續做 symbol resolution ,當 Linker 都掃描完所有輸入文件後,所有 symbol reference 應該都找到對應的 definition 並產生出 executable object file ,否則 Linker 將報出錯誤。 ### Linking order Error 上述規則會造成做 Linking 時的困擾,如果我們將輸入到 compiler driver 的順序改變一下,如同以下 ```shell $ gcc -static -o prog2c -L. -lvector main.o ``` 輸入到 Linker 的順序中, `main.o` 是最後一個輸入,若是裏面有使用到定義於 library 中的 symbol ,由於他後面沒有任何文件輸入,在 `main.o` 中的 symbol reference 將連結不到定義,而造成 Linker 報出錯誤... :::info 因此,一般建議將 library 放到 compiler driver 輸入的結尾來避免這種困擾。 ::: ### Static libraries disadvantage Static library 存在以下缺點,也使得後來出現 shared library 來解決這些問題: * 若是 library 需要更新,程式必須跟更新過後的 library 重新做 Linking 。 * 每一個 executable object file 都需要把用到的 static library 複製一份到檔案內;且每個程式運行時都會將自己用到的 static library 複製一份到記憶體中。 * 幾乎每個 C program 都會用到 `printf` , Linker 在執行時,都需要將 `printf` 的 object file 複製到最終的 executable object file 中。 在程式執行時,這些常用函數又會被複製到執行中的 process 的 text 中。 在一個執行數百個程式的系統中,將對記憶體資源造成極大的浪費。 ## 7.11 Shared library shared libray 是一個 object module ,在載入 (load-time linking)或是執行階段 (run-time linking),都可以被載入到任意的位址,由 dynamic linker 負責將 shared library 和一個在記憶體中的程式做到 linking ,這樣的過程稱為 dynamic linking 。 ![](https://i.imgur.com/Xf6uoxL.png) 以上圖來看如何使用 shared library 做到 load-time linking 。 ### 產生 shared library ```shell $ gcc -shared -fpic -o libvector.so addvec.c multvec.c -fpic ``` * `-fpic` 代表請 compiler 生成與位置無關的程式碼 * `-shared` 指示 Linker 建立共享的 object file ### Partially static linking ```shell $ gcc -o prog21 main2.o ./libvector.so ``` * 靜態執行部份的 linking ,建立 executable object file `prog21` 。 什麼是靜態執行 **部份** linking ? > 以上圖例子來說,關鍵在於沒有任何 `libvector.so` 的程式碼或是 data 被複製到 `prog21` 中 (這點就是 static library 消耗過多記憶體的原因)。 相反地, Linker 複製了跟 `libvector.so` 有關 relocation 和 symbol table 等資訊,以便在載入或執行 `prog21` 時候可以去做 relocation 。 ### Fully linked executable in memory * 當 Loader 載入 `prog21` 到記憶體中, Loader 藉由檢查 executable file 中是否包含 `.interp` section 來決定是否已經完全的做完 linking ,如果已經完成所有 linking , loader 會將控制權交給程式開始執行,否則會將 `.interp` 內包含的 dynamic linker 的執行路徑讀出,載入並執行 dynamic linker 。 * dynamic loader 會從 `.dynamic` section 中知道該使用哪些 shared libraries 。 * dynamic loader 執行剩下的未完成的 relocation 。 * dynamic loader 將控制權交給執行程式, shared libraries 的位置將固定下來,在程式執行過程中都不會改變。 > 以上圖例子來說, Loader (在 linux 中會是 execve)會從 `prog21` 中發現 `.interp` section 裏面包含 dynamic linker 的執行路徑(在 linux 中會是 ld-linux.so)並執行, dynamic linker 接著執行以下 relocation 來完成 linking 。 > 1. relocate `libc.so` 的 `.text` 和 `.data` 到某個記憶體位址上。 > 2. relocate `libvector.so` 的 `.text` 和 `.data` 到某個記憶體位址上。 > 3. relocate 在 `prog21` 中的特定 symbol reference ,這些 symbol reference 會連結到 `libc.so` 和 `libvector.so` 中的 symbol defintion 。 > > 當所有 linking 都完成,控制權將交給程式,程式即可開始執行。 # Linking Summary * Linking 是一種結合多個 object file 成為一個 program 的技術。 包含以下兩個步驟: * Symbol resolution * Relocation * Linking 可以發生在不同的階段 * compile time * load time * run time * 了解 Linking 過程可以幫助你遠離討人厭的錯誤,使你成為一個更好的 programmer 。 ###### tags: `CS:APP` 投影片來源:http://www.cs.cmu.edu/afs/cs/academic/class/15213-f19/www/lectures/14-linking.pdf 上課影片:https://youtu.be/wJRpLEP6rHU ### 待看補充資料 1. [Articles in tag "Linkers and Loaders" - Eli Bendersky's website ](https://eli.thegreenplace.net/tag/linkers-and-loaders?fbclid=IwAR1iq3AYvxNURIfv4oh1WazK-YWELQCwr8aPoa4REYl6MZQVKMo_gLER6Jg)