符號解析與重定位 (Symbol Resolution & Relocation)

Overview Table

7.6 符號解析 (Symbol Resolution) (p.715)

Linker 的第一大任務:把每個模組中的符號參照,關聯到所有輸入 relocatable object file 符號表中的恰好一個定義。

• 區域符號 (local symbols):解析簡單——compiler 保證每個模組內每個 local symbol 只有一個定義,且 static 區域變數會被賦予唯一名稱。
• 全域符號 (global symbols):compiler 遇到當前模組未定義的符號(變數或函式名)時,假設它定義在其他模組,產生一個 linker symbol table entry 交給 linker 處理。
• 若 linker 在所有輸入模組中都找不到定義,印出(常常很難懂的)錯誤並終止:

linux> gcc -Wall -Og -o linkerror linkerror.c
/tmp/ccSz5uti.o: In function 'main':
/tmp/ccSz5uti.o(.text+0x7): undefined reference to 'foo'

• 更棘手的情況:多個模組定義同名全域符號——linker 必須報錯,或選一個定義並丟棄其餘。Linux 的作法由 compiler、assembler、linker 三者合作完成。

7.6.1 Linker 如何解析重複符號名 (p.716)

編譯時 compiler 將每個全域符號以 strong 或 weak 匯出給 assembler,assembler 把此資訊隱含編碼進 relocatable object file 的符號表:

Linux linker 處理重複符號名的三條規則:

書中五組範例對照 (p.716-719):

foo5/bar5 型別不一致的記憶體覆寫示意 (p.719,x86-64 上 double 8 bytes、int 4 bytes):

位址          foo5.c 視角           bar5.c 的 x = -0.0 寫入範圍
0x601020    int x = 15213;    <──┐
0x601024    int y = 15212;    <──┤  double x 佔 8 bytes,
                                  └  一次覆寫 x 與 y!
執行結果:x = 0x0  y = 0x80000000   (−0.0 的 IEEE 754 位元樣式)

COMMON vs .bss 慣例的真正原因 (p.719):compiler 翻譯某模組遇到 weak 全域符號 x 時,不知道其他模組是否也定義 x、也無法預測 linker 會選哪一個實例,因此把決定權推遲給 linker,將其放入 COMMON。反之:

(接續 07-Linking/01-Static-Linking-and-Object-Files 中「看似任意」的 COMMON/.bss 分配慣例。)

7.6.2 與靜態函式庫連結 (Linking with Static Libraries) (p.720)

靜態函式庫 (static library):把相關 object module 打包成單一檔案供 linker 輸入;linker 建構可執行檔時只複製程式實際參照到的 member object module——縮小磁碟與記憶體中的執行檔,程式員又只需在命令列寫少數幾個檔名。

• Linux 上以 archive 格式儲存(副檔名 .a):多個 relocatable object file 串接,加上描述各 member 大小與位置的 header。
• 標準庫例子 (p.721):libc.a(標準 I/O、字串、整數數學:atoi、printf、scanf、strcpy、rand…約 5 MB)、libm.a(浮點數學:sin、cos、sqrt…約 2 MB)。C compiler driver 一律自動把 libc.a 傳給 linker,不必手動列出。
• 為何需要函式庫?其他方案皆有缺陷 (p.721):

建立與使用函式庫(以 addvec.o/multvec.o 組成的 libvector.a 為例,p.722):

linux> gcc -c addvec.c multvec.c
linux> ar rcs libvector.a addvec.o multvec.o        # 用 ar 工具建 archive
linux> gcc -c main2.c
linux> gcc -static -o prog2c main2.o ./libvector.a  # 或等價地:
linux> gcc -static -o prog2c main2.o -L. -lvector

• -static:要求 linker 產出完全連結 (fully linked) 的可執行檔——載入記憶體即可執行,載入期不需任何進一步連結。
• -lvector 是 libvector.a 的縮寫;-L. 告訴 linker 在當前目錄尋找函式庫。
• 例中 main2.o 參照 addvec → linker 複製 addvec.o 進執行檔;程式未參照 multvec.o 的任何符號 → 不複製;另從 libc.a 複製 printf.o 及若干 C run-time 系統模組 (p.723-724)。

 來源檔       main2.c   vector.h
                  │
           Translators (cpp, cc1, as)
                  │
 Relocatable   main2.o     libvector.a       libc.a       ← 靜態函式庫
 object files     │         └ addvec.o        └ printf.o 及其相依模組
                  └─────────────┬──────────────────┘
                           Linker (ld)
                                │
                             prog2c    ← 完全連結的可執行 object file

7.6.3 Linker 如何用靜態函式庫解析參照 (p.724)

符號解析階段,linker 由左至右依命令列順序掃描 relocatable object file 與 archive(driver 會先把 .c 譯成 .o),過程維護三個集合(初始皆空):

• E:將被合併形成執行檔的 relocatable object file 集合
• U:未解析符號集合(已被參照、尚未定義)
• D:先前輸入檔中已定義的符號集合

對每個命令列輸入檔 f(由左至右):
        ┌─ f 是 object file ──→ f 加入 E;依 f 的符號定義/參照更新 U、D
 f ──→──┤
        └─ f 是 archive ─────→ 拿 U 中的未解析符號比對 archive 各 member:
                                  member m 定義了能解析 U 中參照的符號
                                    → m 加入 E,依 m 更新 U、D
                                  反覆迭代 members 直到 U、D 不再變化 (fixed point)
                                  未進 E 的 member 直接丟棄,續處理下一輸入檔
 掃描結束:
   U 非空 → 印出錯誤並終止
   U 為空 → 合併並重定位 E 中的 object files,產出可執行檔

linux> gcc -static ./libvector.a main2.c
/tmp/cc9XH6Rp.o: In function 'main':
/tmp/cc9XH6Rp.o(.text+0x18): undefined reference to 'addvec'

排序通則 (p.725):

• 函式庫放在命令列尾端。
• 各函式庫的 member 彼此獨立(不互相參照)→ 尾端函式庫任意順序皆可。
• 函式庫不獨立 → 必須排序使得:對每個被 archive member 外部參照的符號 s,命令列上至少有一個 s 的定義跟在該參照之後。例:foo.c 呼叫 libx.a 與 libz.a 中的函式,兩者又呼叫 liby.a → gcc foo.c libx.a libz.a liby.a。
• 循環相依可重複列出函式庫:foo.c → libx.a → liby.a → libx.a 時用 gcc foo.c libx.a liby.a libx.a;或直接把 libx.a、liby.a 合併成單一 archive。

7.7 重定位 (Relocation) (p.725)

符號解析完成後,程式碼中每個符號參照都已對應到恰好一個符號定義(某輸入模組符號表中的一個 entry),linker 也已知各輸入模組 code/data section 的確切大小。重定位分兩步:

1. 重定位 section 與符號定義 (Relocating sections and symbol definitions):把所有同型別 section 合併為單一聚合 section(如各模組的 .data 合併成輸出檔唯一的 .data),再為新聚合 section、各輸入模組定義的 section 與符號指派 run-time 記憶體位址。完成後,程式中每條指令與每個全域變數都有唯一的 run-time 位址。
2. 重定位 section 內的符號參照 (Relocating symbol references within sections):修改 code/data section 內文中的每個符號參照,使其指向正確 run-time 位址——依賴 relocatable object module 中的 relocation entry 資料結構。

7.7.1 重定位項目 (Relocation Entries) (p.726)

Assembler 產生 object module 時,既不知道 code/data 最終存放的記憶體位置,也不知道被參照的外部函式/全域變數的位置。因此每遇到最終位置未知的參照,就產生一筆 relocation entry,告訴 linker 合併進執行檔時如何修改該參照。

• Code 的 relocation entry 放在 .rel.text;data 的放在 .rel.data。
• ELF 重定位項目格式(Elf64_Rela,Figure 7.9):

typedef struct {
    long offset;    /* 待重定位參照的 section offset */
    long type:32,   /* 重定位型別 */
         symbol:32; /* 符號表索引 */
    long addend;    /* 重定位運算式的常數部分(有號) */
} Elf64_Rela;

ELF 定義 32 種重定位型別(多數很冷僻),本書只關注最基本的兩種:

7.7.2 重定位符號參照 (Relocating Symbol References) (p.727)

重定位演算法(Figure 7.10;假設每個 section s 是 byte 陣列、每筆 entry r 是 Elf64_Rela,且 linker 已為每個 section 選好 ADDR(s)、每個符號選好 ADDR(r.symbol)):

foreach section s {
    foreach relocation entry r {
        refptr = s + r.offset;    /* 指向待重定位參照的指標 */

        /* 重定位 PC 相對參照 */
        if (r.type == R_X86_64_PC32) {
            refaddr = ADDR(s) + r.offset;   /* 參照的 run-time 位址 */
            *refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr);
        }
        /* 重定位絕對參照 */
        if (r.type == R_X86_64_32)
            *refptr = (unsigned) (ADDR(r.symbol) + r.addend);
    }
}

範例程式 main.o 的反組譯(objdump -dx main.o,Figure 7.11)顯示 main 參照兩個全域符號 array 與 sum,assembler 各產生一筆 relocation entry:

0:  48 83 ec 08      sub   $0x8,%rsp
4:  be 02 00 00 00   mov   $0x2,%esi
9:  bf 00 00 00 00   mov   $0x0,%edi          ← %edi = &array(32-bit 佔位)
        a: R_X86_64_32   array                ← 絕對重定位項目
e:  e8 00 00 00 00   callq 13 <main+0x13>     ← call sum(32-bit 佔位)
        f: R_X86_64_PC32 sum-0x4              ← PC 相對重定位項目
13: 48 83 c4 08      add   $0x8,%rsp
17: c3               retq

(注意:relocation entry 與指令實際存放於 object file 的不同 section,objdump 只是為方便而並列顯示。)

重定位 PC 相對參照 (p.728-729):call sum 起於 section offset 0xe,由 1-byte opcode 0xe8 加上 32 位元 PC 相對參照的佔位組成。

• Relocation entry:r.offset = 0xf、r.symbol = sum、r.type = R_X86_64_PC32、r.addend = -4
• 假設 linker 已決定 ADDR(s) = ADDR(.text) = 0x4004d0、ADDR(r.symbol) = ADDR(sum) = 0x4004e8

refaddr = ADDR(s) + r.offset = 0x4004d0 + 0xf = 0x4004df
*refptr = ADDR(r.symbol) + r.addend - refaddr
        = 0x4004e8 + (-4) - 0x4004df = 0x5
重定位後: 4004de:  e8 05 00 00 00   callq 4004e8 <sum>

執行期驗證:call 位於 0x4004de,CPU 執行它時 PC = 0x4004e3(緊接在 call 之後那條指令的位址)。call 的執行兩步:

1. 將 PC 推入 stack
2. PC ← PC + 0x5 = 0x4004e3 + 0x5 = 0x4004e8   ← 正好是 sum 的第一條指令

重定位絕對參照 (p.729-730):mov 指令把 array 的位址(32 位元立即值)複製進 %edi,起於 offset 0x9,由 opcode 0xbf 加 32 位元絕對參照佔位組成。

• Relocation entry:r.offset = 0xa、r.symbol = array、r.type = R_X86_64_32、r.addend = 0
• 假設 ADDR(r.symbol) = ADDR(array) = 0x601018

*refptr = ADDR(r.symbol) + r.addend = 0x601018 + 0 = 0x601018
重定位後: 4004d9:  bf 18 10 60 00   mov $0x601018,%edi

重定位完成後(Figure 7.12),執行檔的 .text 與 .data 中所有參照都已指向正確 run-time 位址;載入時 loader 可直接把這些 section 的 bytes 複製進記憶體並執行,不需任何進一步修改 (p.730)。

兩種重定位公式對照

Exam/Test Patterns

Related Notes

• 07-Linking/01-Static-Linking-and-Object-Files
• 07-Linking/03-Executable-Loading-and-Dynamic-Linking
• 07-Linking/04-Library-Interpositioning-and-Tools
• 03-Machine-Level-Programs/03-Control-Flow
• 01-Computer-Systems-Tour/01-Information-and-Program-Translation
• 02-Information-Representation/04-Floating-Point