可執行檔載入與動態連結 (Executable Loading & Dynamic Linking)

Overview Table

7.8 可執行目的檔 (Executable Object Files) (p.731)

Linker 把多個 relocatable object file 合併成單一二進位可執行檔,內含載入並執行程式所需的全部資訊。格式與 relocatable object file 類似,但:

• ELF header 除描述整體格式外,還包含 entry point(程式執行的第一條指令位址)。
• .text、.rodata、.data 已被 relocated 到最終的 run-time 記憶體位址。
• .init section 定義小函式 _init,由程式初始化程式碼呼叫。
• 因為已完全連結(relocated),不需要 .rel sections。

       0 +---------------------------+
         |        ELF header         | \
         |   Segment header table    |  |  Read-only memory segment
         |          .init            |  |  (code segment)  r-x
         |          .text            |  |
         |         .rodata           | /
         +---------------------------+
         |          .data            | \  Read/write memory segment
         |          .bss             | /  (data segment)   rw-
         +---------------------------+
         |         .symtab           | \
         |          .debug           |  |  符號表與除錯資訊
         |          .line            |  |  「不會」載入記憶體
         |         .strtab           | /
         +---------------------------+
         |   Section header table    |    描述各 section
         +---------------------------+

Program Header Table(Segment Header Table)(p.732)

ELF 可執行檔設計成容易載入:檔案中連續的區塊 (chunks) 映射到連續的記憶體區段 (segments),此映射由 program header table 描述。以範例程式 prog 為例(objdump 輸出):

• memsz > filesz 的差額(此例 8 bytes)= .bss:執行時初始化為 0,不佔檔案空間。
• 對齊條件:對任一 segment s,linker 必須選擇起始位址 vaddr 使得

其中 off 是該 segment 第一個 section 在檔案中的偏移、align 是 program header 指定的對齊($2^{21}=\mathtt{\text{0x200000}}$)。驗證:0x600df8 mod 0x200000 = 0xdf8 = 0xdf8 mod 0x200000。

• 此對齊是一種最佳化:因虛擬記憶體以大的 2 的冪次連續區塊組織,可讓 segment 有效率地傳輸到記憶體(詳見 09-Virtual-Memory/04-Memory-Mapping)。

7.9 載入可執行目的檔 (Loading) (p.733)

在 shell 輸入 ./prog,因非內建命令,shell 呼叫 loader(記憶體常駐的 OS 程式碼;任何程式可經 execve 呼叫它)。Loader 把可執行檔的 code 與 data 從磁碟複製到記憶體,然後跳到 entry point 開始執行——此過程稱為 loading。

Linux x86-64 Run-time Memory Image (p.734)

 2^48 +------------------------------+
      |        Kernel memory         |  <- user code 不可見
2^48-1+------------------------------+
      |          User stack          |  (run time 建立, 向下成長)
      |             |                |  <- %rsp (stack pointer)
      |             v                |
      +------------------------------+
      |  Memory-mapped region for    |
      |      shared libraries        |
      +------------------------------+
      |             ^                |
      |             |                |  <- brk
      |        Run-time heap         |  (malloc 建立, 向上成長)
      +------------------------------+
      |  Read/write segment          | \
      |  (.data, .bss)               |  |  從可執行檔
      +------------------------------+  |  載入
      |  Read-only code segment      |  |
      |  (.init, .text, .rodata)     | /
0x400000 -----------------------------+
      |          (未使用)             |
    0 +------------------------------+

• Code segment 起始於 0x400000,其後接 data segment、run-time heap(malloc 向上成長)、shared modules 保留區;user stack 從最大合法使用者位址($2^{48}-1$)向下成長;$2^{48}$ 以上保留給 kernel。

啟動流程

./prog → shell → execve → loader
   → 依 program header table 複製 chunks 到 code/data segments
   → 跳至 entry point = _start (定義於系統目的檔 crt1.o, 所有 C 程式相同)
   → _start 呼叫 __libc_start_main (定義於 libc.so)
   → 初始化執行環境 → 呼叫使用者的 main → 處理回傳值 → 必要時交還 kernel

7.10 共享函式庫與動態連結 (Dynamic Linking with Shared Libraries) (p.734)

Static library 的缺點:(1) 函式庫更新後,程式設計師必須知悉並顯式重新連結;(2) 幾乎每個 C 程式都用 printf/scanf 等標準 I/O,其程式碼在每個執行中行程的 text segment 都有一份複本,在數百行程的系統上嚴重浪費記憶體。

Shared library(共享函式庫) 是一種 object module,可在 run time 或 load time 載入到任意記憶體位址並與記憶體中的程式連結——此過程稱為 dynamic linking(動態連結),由 dynamic linker 執行。Linux 上以 .so 為後綴(又稱 shared objects);Microsoft 系統稱為 DLL。

「共享」的兩層意義:

建置與連結流程 (p.735-736)

linux> gcc -shared -fpic -o libvector.so addvec.c multvec.c   # 建 shared library
linux> gcc -o prog2l main2.c ./libvector.so                   # 部分連結

• -fpic:令 compiler 產生 position-independent code(見 7.12);shared library 必須用此選項編譯。
• -shared:令 linker 產生 shared object file。

  main2.c  vector.h
      |
  Translators (cpp, cc1, as)          libc.so, libvector.so
      |                                       |
   main2.o                            relocation 與 symbol table 資訊
      \___________ Linker (ld) _______________/
                       |
   prog2l  <-- "部分連結" (partially linked) 的可執行檔
                       |
              Loader (execve)                 libc.so, libvector.so
                       |                              |
                       |                        code 與 data
   完全連結的記憶體映像 <-- Dynamic linker (ld-linux.so)

• 建立 prog2l 時,libvector.so 的 code/data sections 完全沒有被複製進可執行檔;linker 只複製部分 relocation 與 symbol table 資訊,使其引用可在 load time 解析。
• Loader 載入 prog2l 後,發現其中的 .interp section(內含 dynamic linker 的路徑名,如 ld-linux.so),於是不直接把控制權交給應用程式,而是先載入並執行 dynamic linker。
• Dynamic linker 完成三項 relocation 後才把控制權交給應用程式,之後共享函式庫的位置固定不再改變:
  1. 把 libc.so 的 text 與 data 重定位到某個 memory segment
  2. 把 libvector.so 的 text 與 data 重定位到另一個 memory segment
  3. 重定位 prog2l 中對 libc.so、libvector.so 所定義符號的引用

7.11 應用程式在執行期載入共享函式庫 (p.737)

除了 load time,應用程式也可以在執行中請求 dynamic linker 載入並連結任意 shared library,無須在編譯期對這些函式庫連結。實際應用:

• 軟體發布:Windows 開發者常以新版 shared library 發布更新,使用者下載替換後,下次執行即自動連結載入新版。
• 高效能 Web 伺服器:早期以 fork + execve 執行 CGI 程式產生動態內容;現代作法是把每個產生動態內容的函式包成 shared library,請求到達時動態載入並直接呼叫——函式快取在伺服器位址空間中,後續請求只需一次函式呼叫的成本,且可不停機更新或新增函式。

dlopen 介面(#include <dlfcn.h>,連結時加 -ldl)

• dlopen 的 flag 必須包含 RTLD_NOW(立即解析外部符號引用)或 RTLD_LAZY(延遲到該函式庫的程式碼被執行時才解析)兩者之一;可再 OR 上 RTLD_GLOBAL。
• filename 中的外部符號,用先前以 RTLD_GLOBAL 開啟的函式庫解析;若可執行檔以 -rdynamic 編譯,則其 global symbols 也可供解析。

/* dll.c 典型流程 (p.739) */
handle = dlopen("./libvector.so", RTLD_LAZY);      /* 載入 */
addvec = dlsym(handle, "addvec");                  /* 取函式指標 */
addvec(x, y, z, 2);                                /* 像普通函式一樣呼叫 */
dlclose(handle);                                   /* 卸載 */
/* 編譯: gcc -rdynamic -o prog2r dll.c -ldl */

7.12 位置無關程式碼 (Position-Independent Code, PIC) (p.740)

動機:讓多個行程共享同一份函式庫程式碼。若改用「事先為每個函式庫指派固定位址區塊」的作法會有嚴重問題:位址空間使用低效(行程沒用到也佔位)、難以管理(區塊不得重疊、函式庫改版可能塞不下、新函式庫要找空間)、長期造成位址空間碎片化,且各系統的指派不同,管理惡夢加倍。

解法:把 shared module 的 code segment 編譯成載入到記憶體任何位置都不需 linker 修改的程式碼——可以不經任何 relocation 就載入的程式碼稱為 PIC。以 gcc -fpic 產生;shared library 必須一律以此選項編譯。(當然,每個行程仍有自己的 read/write data segment 複本。)

• 在 x86-64 上,同一 executable object module 內部的符號引用不需特殊處理即是 PIC:用 PC-relative addressing 編譯、由 static linker 重定位即可。
• 需要特殊技術的是:引用由 shared module 定義的外部程序 (external procedures) 與全域變數。

PIC 資料引用:GOT (Global Offset Table) (p.740-741)

關鍵事實:無論 object module 載到記憶體何處,data segment 與 code segment 的距離恆定——code 中任一指令到 data 中任一變數的距離是 run-time constant,與絕對位址無關。

• Compiler 在 data segment 開頭建立 GOT:被該 module 引用的每個 global data object(程序或全域變數)各佔一個 8-byte entry,並為每個 entry 產生 relocation record。
• Load time 由 dynamic linker 重定位每個 GOT entry,填入該 object 的絕對位址。
• 每個引用 global objects 的 object module 都有自己的 GOT。

Data segment
  GOT[0]: ...
  GOT[3]: &addcnt      <-┐
                          |  GOT[3] 與指令距離 0x2008b9
Code segment              |  = run-time constant
  addvec:                 |
    mov 0x2008b9(%rip),%rax   # %rax = *GOT[3] = &addcnt
    addl $0x1,(%rax)          # addcnt++

PIC 函式呼叫:PLT + Lazy Binding (p.741-743)

呼叫 shared library 定義的函式時,compiler 無法預測其 run-time 位址。若用一般 relocation record 交給 dynamic linker 在載入時修改,會修改到呼叫模組的 code segment,就不是 PIC 了。GNU 系統改用 lazy binding(延遲繫結):把每個程序位址的繫結延遲到第一次呼叫時。

• 動機:典型程式只會呼叫 libc.so 匯出的數百上千個函式中的一小部分;延遲解析可避免載入時做成百上千次不必要的 relocation。
• 成本:第一次呼叫有不小的 run-time 開銷;之後每次呼叫只多一條指令與一次記憶體引用(間接跳轉)。
• 由 GOT + PLT (procedure linkage table) 兩個資料結構互動實作。只要 object module 呼叫任何定義在 shared library 中的函式,它就有自己的 GOT 和 PLT。

• 初始狀態:每個(函式用的)GOT entry 指向對應 PLT entry 的第二條指令。

(a) 第一次呼叫 addvec (lazy binding):

  callq 0x4005c0          # 呼叫 addvec -> 其實呼叫 PLT[2]   ... Step 1
       |
       v
  PLT[2]: 4005c0: jmpq *GOT[4]   # GOT[4] 初值 = 0x4005c6
                    |            #  -> 跳回下一條指令          ... Step 2
                    v
          4005c6: pushq $0x1     # 推入 addvec 的 ID          ... Step 3
          4005cb: jmpq 4005a0    # 跳到 PLT[0]
                    |
                    v
  PLT[0]: 4005a0: pushq *GOT[1]  # 推入 dynamic linker 的引數  ... Step 4
          4005a6: jmpq *GOT[2]   # 跳入 dynamic linker
                    |
                    v
  dynamic linker: 用堆疊上兩個 entry 求出 addvec 的 run-time 位址,
                  以其「覆寫 GOT[4]」,再把控制權交給 addvec

(b) 之後每次呼叫 addvec:

  callq 0x4005c0  ->  PLT[2]: jmpq *GOT[4]  ->  直接跳到 addvec
  (僅多 1 條指令 + 1 次記憶體間接引用)

Exam/Test Patterns

Related Notes

• 07-Linking/01-Static-Linking-and-Object-Files
• 07-Linking/02-Symbol-Resolution-and-Relocation
• 07-Linking/04-Library-Interpositioning-and-Tools
• 08-Exceptional-Control-Flow/04-Process-Control
• 09-Virtual-Memory/04-Memory-Mapping
• 03-Machine-Level-Programs/06-Buffer-Overflow-and-Pointer-Safety