CS:APP Chapter 7 Linking 閱讀筆記

本文旨在記錄 Computer Systems: A Programmer's Perspective (CS:APP) 一書第七章閱讀心得，該書是 CMU 的計算機系統概論的教材 (難度相當於台灣的大學高年級)，該書的簡體中文翻譯名稱為《深入理解計算機系統》。

CS:APP 亦是 Linux Kernel Internals 2024 Spring 課程指定教材，並一同收錄於
Linux Kernel Internals 2024 Spring Collections。

---

7.1 Compiler Drivers

我們知道常說的 compiling 事實上是指 Compiler Driver 的一系列工作，即將 C 轉換成可執行檔的多個過程，包含

1. C compiler 將 C 翻譯為 asm code
2. assembler 將 asm code 翻譯為 binary code
3. linker 解析 reference 到 symbol 包含函式與變數以及安排記憶體位置
4. loader 載入程式到 kernel 當中
5. task 等待分配 CPU 執行

本章名 Linking 表示第三步是本章重點之一，然而，linking 也發生於執行期；前者是 static linking，也就是 linker 介入鏈結各項檔案時，後者則稱 dynamic linking，此時期最重要的工作之一就是指向動態分配的記憶體位置，以及載入 shared object files。

7.2 Static Linking

靜態連結期是編譯系統中的最後一個步驟，主要工作是將所有 text section 和 data section 分配到「好的位置」；首先我們知道，prog 是一連串 binary code，也就是 0000111100100...，而 object files 則是由一連串 symbols、指令和 hex 組成的，故可以想像 linker 就是將 object files 的內容放到正確的位置以結合成執行檔，linker 的兩個主要任務稱為：

1. Symbol resolution
   將 symbol，也就是函式或變數的名稱，和它的「定義」結合；更詳細的說是，應該要形成一個 Symbol Table，給予某一個 symbol，如果是函式，就會查詢到其執行步驟，變數則是占存器或記憶體位置。
2. Relocation
   將相應定義的 binary code 放置到對應的位置而形成執行檔。

此處只要了解 object files 和執行檔的樣貌就能夠知道 static linking 的行為了，畢竟真正困難的工作， compiler 以及 assembler 已經完成，說到底 linker 僅僅是「重新擺放」 object files 罷了。

As you read, keep in mind some basic facts about linkers: Object files are merely collections of blocks of bytes. Some of these blocks contain program code, others contain program data, and others contain data structures that guide the linker and loader.
A linker concatenates blocks together, decides on run-time locations for the concatenated blocks, and modifies various locations within the code and data blocks.

分別更詳細的內容將於後面章節詳述。

7.3 Object Files

Object files 事實上有三種型式

1. Relocatable object file
2. Executable object file
3. Shared object file

assembler 產生的是 relocatable object file，我們可以透過 objdump readelf hexdump 等方式查看其內容，如 objdump -d foo.o

main.o:     file format elf64-x86-64

Disassembly of section .text:

0000000000000000 <foo>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   48 83 ec 10             sub    $0x10,%rsp
   8:   bf 00 00 00 00          mov    $0x0,%edi
   d:   e8 00 00 00 00          callq  12 <foo+0x12>
  12:   90                      nop
  13:   c9                      leave
  14:   c3                      retq

0000000000000016 <main>:
  16:   55                      push   %rbp
  17:   48 89 e5                mov    %rsp,%rbp
  1a:   e8 00 00 00 00          callq  1f <main+0x9>
  1f:   b8 00 00 00 00          mov    $0x0,%eax
  24:   5d                      pop    %rbp
  25:   c3                      retq

而 linker 產生的執行檔 execute file 又可稱 executable object file，也就是一連串 binary code 組成的檔案。

而 shared object file 像是 .so (有時稱 dynamic library file)，會在執行期的 dynamic linking 時被放入執行檔中，好處是比起 static library file .a 可以節省檔案大小，但需要注意執行環境以及執行初期需要花費一些時間。

而發生在 static linking 的 .a 會在 7.6 中說明。

我們大致可以整理以下內容

1. .o 檔是 relocatable object file 由 assembler 產生

2. .so
   是 shared object file，在執行期以 dynamic linking 的方式載入，使用如下

   ​​​​// produce .so
   ​​​​$ gcc -fPIC -c file2.c -o file2.o
   ​​​​$ gcc -shared -o libmylib.so file2.o
   ​​​​// link .so
   ​​​​$ gcc main.c -L. -lmylib -o myprogram
   ​​​​$ LD_LIBRARY_PATH=. ./myprogram
   

3. .a 檔稱作 static library file，在連結期以static linking的方式併入執行檔，使用如下

   ​​​​// produce .a
   ​​​​$ gcc -c file1.c -o file1.o
   ​​​​$ ar rcs libmylib.a file1.o
   ​​​​// link .a
   ​​​​$ gcc main.c -L. -lmylib -o myprogram
   

7.4 Relocatable Object Files

Executable and Linkable Format (ELF) 檔案被廣泛指涉 Linux 系統中具有固定結構的檔案，如 .text .data 等，見下圖

被嚴格定義的原因是，它們用來和作業系統互動，如果是 executable ELF 則可直接被 OS loader 載入到記憶體並執行。

我們可以使用 readelf -h 展示 object files 的 ELF header，如 readelf -h *.o

ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              REL (Relocatable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          0 (bytes into file)
  Start of section headers:          6184 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           64 (bytes)
  Number of section headers:         14
  Section header string table index: 13

使用在上述 object file 的執行檔之輸出為

ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              DYN (Shared object file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x1370
  Start of program headers:          64 (bytes into file)
  Start of section headers:          15456 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         13
  Size of section headers:           64 (bytes)
  Number of section headers:         31
  Section header string table index: 30

7.5 Symbols and Symbol Tables