---
tags: CSAPP, 作業系統
---

# CSAPP: Chapter 7

:::info
僅記錄最粗淺的概念，詳細的例子請直接參考原書籍或者課程投影片:
* [Linking](http://www.cs.cmu.edu/afs/cs/academic/class/15213-m19/www/lectures/13-linking.pdf)
:::

## Overview

linker 是編譯系統中重要的存在。它使得程式可以模組化，允許把一個執行擋拆分成多個檔案，讓程式碼架構更清晰而易於維護，也可以更方便的與某個函式庫做結合。此外，編譯的時間上也可以受益於 linker，只需要編譯修改的程式檔並重新連結，而不需要將整個執行檔的相關程式碼都重新編譯。

下面的的簡單範例中有兩個 `.c` 檔，讓我們來看看 linker 在將 `.c` 檔轉換成一個可執行檔的過程中所扮演的腳色。

int sum(int *a, int n);

int array[2] = {1, 2};

int main() 
{
    int val = sum(array, 2);
    return val;
}

> `main.c`

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

> `sum.c`

我們可以用下面的命令來調用 [gcc](https://en.wikipedia.org/wiki/GNU_Compiler_Collection)，得到一個可執行的檔案 `prog`:

$ gcc -o prog main.c sum.c

事實上，gcc 是一個 compiler driver，雖然看起來是一行指令，但在背後的調用包含 preprocessor、compiler、assembler、linker 一系列工具的處理(你可以加上 `-v` 選項來看看詳細的步驟)。實際上整個過程中為:

1. gcc 首先啟動 [preprocessor](https://en.wikipedia.org/wiki/Preprocessor)，得到 `main.i`

cpp (some arguments) main.c /tmp/main.i 

2. 接著，gcc 運行 c [compiler](https://en.wikipedia.org/wiki/Compiler)(cc1)，將 `main.i` 轉換成一個 assembly code

cc1 /tmp/main.i (some arguments) -o /tmp/main.s

3. 啟動 [assembler](https://en.wikipedia.org/wiki/Assembly_language)(as)，將 `main.s` 轉換成一個 relocatable object file

as (some arguments) -o /tmp/main.o /tmp/main.s

4. `sum.o` 也透過 1~3 的流程產生，最後調用 [linker](https://en.wikipedia.org/wiki/Linker_(computing))(ld)，將 `main.o` 和 `sum.o` 連接起來，產生一個 executable object file `prog`

ld -o prog (system object files and args) /tmp/main.o /tmp/sum.o

更細節的說明 linker 的運作的話:

Step 1: Symbol resolution: object file 裡儲存對某個 symbol 的定義及引用，每個 symbol 可能對應於一個 function、global 或者 static variable。在此階段，linker 將每個引用和其定義連接起來。

Step 2: Relocation: 首先將不同 object file 中的 code 和 data section，在產生的執行檔中要合併成單一個 section，如此一來，每個指令和 data section 中的內容就有唯一的位址了。接著修改每個 symbol 的引用使得指向正確的執行期位址。

可以看到 linker 在整個過程中扮演的腳色。在將每個 `*.c` 檔產生出對應的 `＊.o` 後，最後使用像是 ld 這樣的 linker，以這些產生的 object files 作為輸入，生成出一個可以載入和運行的 executable。

## Object files

object files 可以大致區分為三種類型:
* Relocatable object file(`*.o`): 包含 code 和 data，可以與其他的 relocatable 通過 linker 結合起來
* Executable object file(`a.out`): 包含 code 和 data，可以直接載入記憶體中執行
* shared object file(`*.so`): 一種特殊的 relocatable object，可以動態的在載入或執行期去連接
* 在 windows 作業系統中則是 `*.dll` 檔

object files 是透過特定的格式來組織的，每個作業系統的 object files 也不盡相同，這裡我們將以 Linux 上的 [ELF](https://en.wikipedia.org/wiki/Executable_and_Linkable_Format) 格式作為主要的討論對象。



上圖中展示了一個基本的 ELF layout。在最開始的內容是 ELF header，ELF header 包含其生成的機器類型(x86-64)、byte ordering、object file 類型(relocatable / executable / shared) ，section 的大小和數量等等資訊(詳見維基百科)。其後則有不同的 section，典型的 relocatable object file 通常會包含:
* .text: 被編譯後的程式 binary
* .rodata: 只可讀的 data
* .data: 已初始化(不為 0) 的 global 或者 static variable
* .bss: 未初始化或者初始為 0 的 global 或者 static variable
* bss 段的變數不佔用空間，與 data 段分開因此得以提升記憶體的空間效率
* .symtab: symbol table，存放在程式中被定義且引用的函數或者 global 信息
* .rel.text: 當這個 `*.o` 與其他 `＊.o` link 在一起時，需要被修改的 .text 段，一般來說和調用外部函式或者 global 的 instruction 相關
* .rel.data: 類似於 .rel.text，需要被修改的 .data 段
* .debug: 當透過 `-g` 選項編譯產生的 debug 用 symbol table

## Linker with duplicate symbols

如果多個 module 定義同名的 symbol 會發生甚麼事呢? 在 Linux 的編譯系統，symbol 會區分成 strong 和 weak。函式和已初始化的 global 歸類為 strong，為初始化的 global 則歸類為 weak，linker 中需要滿足的規則為:

1. 不允許同名的 strong symbol
2. 如果有一個 strong 以及多個 weak，選擇 strong 的定義
3. 如果有多個 weak，任一選擇其中一個

需注意規則的應用，及可能導致的程式行為(詳見原投影片)。

## Static library
static library 在 Linux 中以名為 archive 的格式儲存，檔案名稱後綴 `.a` 來標示。

static library 提供一種機制，可以將所有相關的 module 打包成單一檔案，當成是 linker 的輸入。則當建構一個可執行檔時，library 中只會有被應用程式所引用的相關 module 被複製出來。假設不使用 static library，將整個函式庫打包成 `.o` 檔作為其他應用程式使用 library 的輸入的話，每個使用 library 的可執行檔都會持有一個副本，導致對儲存空間的浪費; 反之，如果把 library function 都拆成獨立的 `.o`，需要輸入給 linker 的參數又太過複雜且容易出錯。

linker 如何使用 static library 來解析符號引用是需要多加小心的地方。在符號解析階段，linker 維護一個 relocatable object file 的集合 $E$，一個未解析的符號集合 $U$，以及一個已定義的符號集合 $D$，初始時 $E$、$U$、$D$ 皆為空。然後 linker 會從輸入的左至右順序來掃描 relocatable object file 或 archive:

* linker 按輸入順序處理每個文件。對於每個輸入文件，linker 判斷是一個 object file 還是 archive:
* 如果是 object file 就加入到 $E$，並根據檔案的定義和引用修改 $U$ 和 $D$
* 如果檔案是 archive，linker 嘗試匹配 $U$ 中未解析的 symbol $m$ 以及 archive 中的每個 object file 成員是否存在定義，如果是，將其加入到 $E$，並且修改 $U$ 和 $D$ 來反映這個改變，否則捨去該 object file
* 當 linker 完成對所有輸入文件的掃描後，$U$ 若為非空則 linker 會輸出錯誤並且中止。否則它將會合併 $E$ 中的所有 object file 並產生可執行檔

在這個過程下，linker 的 object file 參數之輸入順序就會影響到連結的成功與否。假設我們有一個 `main.c` 使用到一個定義在 `libx.a` 的 object file，下面的命令會產生編譯失敗:

$ gcc -static ./libx.a main.c

因為在處理 `libx.a`，$U$ 中為空，所有 `libx.a` 的 object file 成員都被捨棄。因此一般而言，archive 參數都會被放在命令的結尾，避免此錯誤。此外，如果 archive 間互相引用，就需要正確的排序它們，假設 `foo.c` 調用 `libx.a`，而 `libx.a` 調用 `liby.a` 的函數，且 `liby.a` 也調用 `libx.a` 的函數，命令就要寫成:

$ gcc foo.c libx.a liby.a libx.a

## Shared library

static library 雖然解決了某些問體，但也仍存在一些明顯的缺點。其一，函式庫可能會被更新，如果程式撰寫者想要使用更新的函式庫，需要重新對其做 linking。另外，像是 printf / scanf 這種可能會被頻繁使用的 library function，在 static library 的作法下會複製到每個程式的 text section 中，這導致一定程度的記憶體空間耗費。

[shared library](https://en.wikipedia.org/wiki/Library_(computing)#Shared_libraries) 因應這些問題而生。它可以被載入到記憶體中，與在執行的程式產生連結。這個過程稱為 dynamic linking，由動態連結器(dynamic linker)來執行。shared library 在 Linux 中的後綴為 `.so`，在 microsoft 中則被稱為 DLL。

以 Linux 系統來說，對於每個 library，系統中只存在一個 `.so` 檔，所有引用該函式庫的可執行檔會共享該代碼和數據。

> 延伸閱讀: [C 語言: 動態連結器](https://hackmd.io/@RinHizakura/S1tNA0RZv)

## Library interpositioning

Linux 的 linker 提供一種稱為 library interpositioning 的技術，允許將對共享函式庫的調用用自己定義的函式做替換。

library interpositioning 可以在編譯、連結、或者執行時期進行。

> 延伸閱讀: [Function Interposition in C with an example of user defined malloc()](https://www.geeksforgeeks.org/function-interposition-in-c-with-an-example-of-user-defined-malloc/)