Jserv's blog: 親手打造 Dynamic Library Loader

From Jserv's blog: 親手打造 Dynamic Library Loader

這幾個月又繼續設計 / 實做新的 Kernel (與相關的系統程式)，貫徹「每年練習寫一個作業系統」的小目標，其中對 dynamic linker 的支援，是重要的特徵，本文則探討如何在 GNU/Linux 實做出 Dynamic Linker / Dynamic Library Loader (即 ld.so 與 libdl.so) 的功能，並以 ELF 執行檔格式作為探討對象，如此的概念可應用於 RTOS 與廣泛的嵌入式系統。

許多程式設計師都知道 dynamic linker，也知曉像是 LD_PRELOAD 的機制，但鮮少人真正瞭解其背後的內部工作原理，因為難題不僅是 linker 與 loader 的行為，而是在執行時期 (Runtime)，要有種機制得以確保 dynamic linked 的程序中的函式 / 符號位址，已正確地指向了動態函式庫 (以下簡稱 "DLL" 或 DSO [Dynamic Shared object，UNIX 術語]，本文不特別強調其分野) 裡頭的對應位址，基於如此考量，系統至少該具備以下的特徵：

• PIC (Position Independent Code) : 簡單來說，DLL/DSO 本質上要能夠被載入到記憶體的任何有效的位址，也就是字面上 "Position Independent" 的意涵。而早期 UNIX 的 a.out 執行檔格式其實不是不能作 dynamic linker/loader，是被約束於 Position Dependent，也就是一定要被載入到特定的記憶體位址，才能運作，很沒有彈性，USL (UNIX SYSTEM Laboratories) 後來發展的 ELF 格式 (Executable and Linking Format) 就破除如此的限制。編譯器支援 PIC 的特徵 (gcc 的編譯選項是 "-fpic" / "-fPIC" )，會使輸出的 object code 與記憶體位址無關，並減少對絕對位址的使用。
• 在執行時期才去處理符號 (變數與函式等)：透過 ELF 裡頭的 symtab (symbol table) 與 relocation 機制去達成，也就是說，載入 DLL 的那一刻，其實無法執行程式本體，需要在解析 symtab 與對所有的位址都 relocation 後，才會真正去執行，而配合前述的 PIC，可大幅降低執行時期的開銷。當然，沒有 PIC，還是能做出 DLL/DSO，不過 relocation 的開銷就會相當可觀。
• GOT (Global Offset Table) 的引入：要達到可用的 PIC，需要一份全域的 GOT，讓編譯器輸出的機械碼中，保留一個暫存器 (register) 去參照 GOT 這個排列好指向 symbol 位址的表格，如此一來，DLL/DSO 載入後，只需要一次的 relocation 即可得到全域的位址 (以 UNIX Process 的觀點)

實際上 PIC 與 GOT 的搭配，還有一些學問要探討，不過本文的方向則在「親手打造」，暫且先行忽略。接下來的篇幅，將在 i386 (IA32) 的 GNU/Linux 平台上，實做出 libdl.so 的關鍵功能，不依賴原本的 ld.so，理論上應該能快速移植到非 GNU/Linux 的系統。就 API 的角度來說，我們要實做出以下函式：

• dlopen()
• dlsym()
• dlclose()

驗證我們親手打造的 Dynamic Library Loader 的方式：

• 透過 dlopen() 將一個 ELF object code 載入並映射到記憶體，注意：為了簡化設計的難度，我們的實做將忽略 PIC/GOT
• 透過 dlsym() 將稍早載入的 object code 中提取特定 symbol 的進入點 (UNIX Process 的函式位址)，當然，這是做了 relocation 之後的位址
• 傳遞必要的參數給指向前述位址的 function pointer，嘗試去執行，驗證其功能是否符合預期
• 將 symbol 進入點作記憶體 dump，觀察其機械碼的排列方式
• 以 dlclose() 將必要的資源釋放

在筆者的實做，這個特製的 Dynamic Library Loader 稱為 "ndl"，自然前述的三個重要函式就被命名為 ndlopen(), ndlsym(), ndlclose()，以利辨識。先來看看測試的程式 (test-ndl.c)：

#include  #include "ndl.h"  /* dump machine code of loaded DSO */ static void dump(char *p);  int main() {     void *handle;      /* add */     handle = ndlopen("add.o");     int (*fp_add) (int, int) = ndlsym(handle, "add");      printf("add (%p):\n", fp_add);     dump((char*) fp_add);      printf("[add] 1 + 1 = %d\n", fp_add(1, 1));     ndlclose(handle);      printf("\n");      /* hello */     handle = ndlopen("hello.o");     void (*fp_hello) (char *) = ndlsym(handle, "hello");     char *msg = ndlsym(handle, "dyn_str");      printf("hello (%p):\n", fp_hello);     dump((char *) fp_hello);      fp_hello("Hello World");     fp_hello(msg);     ndlclose(handle);      return 0; }  static void dump(char *p) {     int c = 0;     while (*p != (char) 0xc3) { /* 'c3' = asm("ret") */         printf("%02x ", (*p++) & 0xff);         if (++c % 16 == 0)             printf("\n");     }     printf("c3\n"); } 

上述程式包含兩輪的測試，一個是載入 'add.o'，另一個是 'hello.o'，前者是簡單的算術操作，而後者涉及函式呼叫。對應的 DLL/DSO 程式碼列表：

jserv@venux:/tmp/ndl$ cat add.c  int add(int x, int y) {  return x + y; } jserv@venux:/tmp/ndl$ cat hello.c #include   char dyn_str[] = "__DSO__";  void hello(char *s) {  printf("[hello] %s\n", s); }

以下是參考的編譯與執行輸出：

jserv@venux:/tmp/ndl$ make gcc -c hello.c -Os -Wall -fomit-frame-pointer -I./external gcc -c add.c -Os -Wall -fomit-frame-pointer -I./external gcc -o test_ndl test_ndl.c ndl.c dummy.c \   /usr/lib/libbfd.a /usr/lib/libiberty.a -static \   -Os -Wall -fomit-frame-pointer -I./external -Wl,-O1 jserv@venux:/tmp/ndl$ ./test_ndl   :: handle = 0x8e026a8 add (0x8e02854): 8b 44 24 08 03 44 24 04 c3 [add] 1 + 1 = 2   :: reloc_name = __printf_chk  :: handle = 0x8e02770 hello (0x8e029bc): 83 ec 10 ff 74 24 14 68 dc 29 e0 08 6a 01 e8 51  a1 2f ff 83 c4 1c c3 [hello] Hello World [hello] __DSO__ 

那麼上述的實驗中，有哪些該注意的細節呢？在深入探討筆者提出的 ndl 前，可以留意到：

• 首先，'test_ndl' 這個程式本身是 statically linked，連結到 libbfd 與 libiberty 這兩個專門處理 ELF 的函式庫 (在 Debian/Ubuntu 裡頭，由套件 binutils-dev 所提供)，並無連結到 libdl，而是採用我們親手打造的函式
• 一般 statically linked 的程式無法使用 dlopen()，但我們的程式沒有如此限制，仍可在動態時期載入 DSO 並處理 symbol 與 relocation
• 迴避 PIC/GOT 的細節，編譯參數沒有 -fpic 或 -fPIC
• 'add.o' 與 'hello.o' 的差別在於，'hello.c' 有呼叫到 printf() 的動作，這致使執行時期仍需要多作一個 relocation，此動作需要在實際呼叫被載入的 hello() 前準備好，否則無法運作

讓我們觀察看看 'add.o' 與 'hello.o' 在 ELF 檔案中的資訊，可透過 binutils 的 readelf 工具程式分析：

jserv@venux:/tmp/ndl$ readelf -r add.o  There are no relocations in this file. jserv@venux:/tmp/ndl$ readelf -r hello.o  Relocation section '.rel.text' at offset 0x368 contains 2 entries:  Offset     Info    Type            Sym.Value  Sym. Name 00000008  00000501 R_386_32          00000000   .rodata.str1.1 0000000f  00000902 R_386_PC32        00000000   __printf_chk 

由此可見，'hello.o' 所呼叫的 printf() 函式主體其實位於 statically-linked 的 'test-ndl' 執行檔中，而 printf() 的符號在編譯時期被替換為 '__printf_chk'。readelf 工具程式告訴我們，'hello.o' 在 Relocation section '.rel.text' 有兩個符號，對照於 'hello.c'：

• '.rodata.str1.1' 即 "[hello] %s\n" (傳遞給 printf() 的參數)，型態為 R_386_32 (absolute 32-bit)
• '__printf_chk' 即 printf()，其型態為 R_386_PC32 (PC relative 32 bit signed)

而在 'add.o' 中，自然是沒有額外的 relocations 操作。倘若我們再比對 ndl 所載入的 'hello.o' 與 ELF 的 .text section，就可獲得驗證，使用 objdump 工具：

jserv@venux:/tmp/ndl$ objdump -xd hello.o   hello.o:     file format elf32-i386 hello.o architecture: i386, flags 0x00000011: HAS_RELOC, HAS_SYMS start address 0x00000000 ... Disassembly of section .text:  00000000 :    0: 83 ec 10              sub    $0x10,%esp    3: ff 74 24 14           pushl  0x14(%esp)    7: 68 00 00 00 00        push   $0x0    8: R_386_32 .rodata.str1.1    c: 6a 01                 push   $0x1    e: e8 fc ff ff ff        call   f     f: R_386_PC32 __printf_chk   13: 83 c4 1c              add    $0x1c,%esp   16: c3                    ret 

對照於 test_ndl 的輸出：

hello (0x8e029bc): 83 ec 10 ff 74 24 14 68 dc 29 e0 08 6a 01 e8 51 a1 2f ff 83 c4 1c c3 

就再清楚不過了，'hello' symbol 的反組譯自 '83' 'ec' 10' (sub $0x10,%esp) 開始到 c3 (ret) 為止，都被載入到記憶體，並做了必要的 relocation。以下是簡要探討 ndlopen(), ndlsym(), ndlclose() 的實做，詳情可參閱原始程式碼 [ndl.tar.bz2]。

在原始程式 ndl.c 中，我們引入 libelf 所提供的 bfd.h 檔頭 (BFD, the Binary File Descriptor library)，並宣告兩個結構體，供後續使用：

typedef struct {     const char *name;     void *fp; } ndl_sym_t;  typedef struct {     htab_t syms;     char *map;     size_t length; } ndl_t; 

在 API 的實做則是：

void *ndlsym(void *h, const char *symbol) {     ndl_t *handle = (ndl_t *) h;     ndl_sym_t **sym;     void *addr;     sym = (ndl_sym_t **) htab_find_slot(handle->syms, symbol, NO_INSERT);     if (! sym)         return NULL;     addr = (*sym)->fp;     mprotect((void *)((((int) addr + 4095) & ~4095) - 4096),              4096, PROT_READ | PROT_WRITE | PROT_EXEC);     return addr; }  void ndlclose(void *h) {     ndl_t *handle = (ndl_t *) h;     free(handle->map); }

ndlsym() 與 ndlclose() 的實做就相當顯然了，只要 dlopen() 能將 ELF 必要的欄位與資訊填入前述的資料結構，那麼就是作必要的查表動作即可，需要留意的是 mprotect() 的呼叫，因為我們要將對照後的記憶體位址區段標示為「可讀、可寫、可執行」(x86 的特性)。dlopen() 的實做稍微複雜一點，不過重點是實做 load_relocs() 函式，其接受指向 ndl_t 結構的 handle，以及指向已開啟 ELF object code 的 bfd 結構的 abfd 兩個參數。程式碼列表如下：

static int load_relocs(ndl_t *handle, bfd *abfd) {     int size, i;     asection *sect = bfd_get_section_by_name(abfd, ".text");     arelent **loc;      size = bfd_get_reloc_upper_bound(abfd, sect);     if (size < 0) {         bfd_perror("bfd_get_reloc_upper_bound");         return 1;     }      loc = (arelent **) malloc(size);      size = bfd_canonicalize_reloc(abfd, sect, loc, g_syms);     if (size < 0) {         bfd_perror("bfd_canonicalize_reloc");         return 1;     }      for (i = 0; i < size; i++) {         arelent* rel = loc[i];         void **p = (void **) (handle->map + sect->filepos + rel->address);         const char *name;         if (!rel->sym_ptr_ptr || !*(rel->sym_ptr_ptr))             continue;         name = (*(rel->sym_ptr_ptr))->name;         if (!name || !name[0])             continue;          /* section */         if (name[0] == '.') {             asection* s = bfd_get_section_by_name(abfd, name);             *p = handle->map + (int)*p + s->filepos + rel->addend;         }         /* function */         else {             *p = lookup_func_table(name, p);             printf("\t:: reloc_name = %s\n", name);         }     }     free(loc);      return 0; } 

回顧筆者提到 Relocation section '.rel.text' 有兩個符號：'.rodata.str1.1' 與 '__printf_chk'，前者以 '.' (句點) 開頭者，為 section，否則為 function，再回顧 objdump 的輸出：

jserv@venux:/tmp/ndl$ objdump -xd hello.o ... SYMBOL TABLE: 00000000 l    df *ABS* 00000000 hello.c 00000000 l    d  .text 00000000 .text 00000000 l    d  .data 00000000 .data 00000000 l    d  .bss 00000000 .bss 00000000 l    d  .rodata.str1.1 00000000 .rodata.str1.1 00000000 l    d  .note.GNU-stack 00000000 .note.GNU-stack 00000000 l    d  .comment 00000000 .comment 00000000 g     F .text 00000017 hello 00000000         *UND* 00000000 __printf_chk 00000000 g     O .data 00000008 dyn_str ... 

而作為一個 dynamic library loader，ndl 的工作就是基於這兩項，做出正確的查詢動作，以 BFD 提供的函式，將正確的位址找出。有趣的是，既然 printf() 在編譯時期被轉換為 '__printf_chk' 這個 symbol，而 'hello.o' 本身卻只有 undefined symbol (即上列 objdump 輸出的 '*UND*')，其實做在哪呢？就在 test_ndl.c 中，在編譯為 statically-linked 程式時，gcc 默默的將一份 '__printf_chk' 實做碼 (來自 GNU glibc) 連結到 test_ndl 這個應用程式。我們的 load_relocs() 中，針對函式的查詢則用輕便的方式：窮舉法，以下是原始程式碼：

static inline void *lookup_func_table(const char *func_name, void **ptr) {     if (0 == strcmp(func_name, "printf"))         *ptr = (void *)((unsigned int) &printf -                         (unsigned int) ptr - 4);     else if (0 == strcmp(func_name, "puts"))         *ptr = (void *)((unsigned int) &puts -                         (unsigned int) ptr - 4);     else if (0 == strcmp(func_name, "__printf_chk"))         *ptr = (void *)((unsigned int) &__printf_chk -                         (unsigned int) ptr - 4);     else {         /* FIXME: handle uncaught function entries */     }     return *ptr; } 

當然，筆者這麼作，實在是相當偷懶，但對一個 self-contained 的環境來說，應已足夠，需要留意的是 frame pointer 的操作，所以適度要調整進入點的位置："ptr - 4"。正如前述所及，完整的 dynamic linker/loader 需要考慮相當多細節，但本文用最簡便的方式，提供可行且易於分析的途徑，未來筆者會再探討涉及作業系統與函式庫的議題。
由 jserv 發表於 November 13, 2009 10:14 AM