(2021) 19 [代碼講解] 從零實現動態加載

南京大學操作系統課蔣炎巖老師網絡課程筆記。

視頻：https://www.bilibili.com/video/BV1N741177F5?p=15
講義：http://jyywiki.cn/OS/2021/slides/C9.slides#/

背景

回顧：

ELF可執行文件

只要能完成手冊上要求的內容，就可以自己實現一個execve

本次課內容與目標

靜態鏈接與加載

• hello程序的鏈接與加載

動態鏈接與加載

• 理解動態加載的動機
• 自己實現動態加載
• “lazy” 的延遲符號綁定
• ELF文件的動態鏈接與加載

不同的ELF文件的格式

同為Linux中的可執行二進制文件ELF，也有不同的具體的格式。

我們拿一個hello程序舉例：

#include <stdio>int main(){printf("Hello\n");
}

我們用不同的編譯選項來編譯它，注意gcc默認是動態鏈接：

gcc hello.c -o dynamic_hello
gcc -static hello.c -o static_hello

兩個文件dynamic_hello和static_hello都可以正常運行輸出正常的結果，并且它們也都是ELF可執行文件。但是當我們用file命令來查看它們時，會發現有些許不同。

file dynamic_hello
file static_hello

輸出分別為：

dynamic_hello: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=83a317b39ca06b8945b090871745ff8287463528, not stripped

static_hello: ELF 64-bit LSB executable, x86-64, version 1 (GNU/Linux), statically linked, for GNU/Linux 3.2.0, BuildID[sha1]=d9ac8fd547a3c93a5cafa2d47c2416b4a147180f, not stripped

注意上面紅字標出的地方指明了這兩個ELF文件之間的不同，它們一個是動態鏈接加載的，一個是靜態鏈接加載的。

靜態鏈接與加載

編譯、鏈接的需求

為了節省空間和時間，不將所有的代碼都寫在同一個文件中是一個很基本的需求。

為此，我們的C語言需要實現這樣的需求：允許引用其他文件（C標準成為編譯單元，Compilation Unit）里定義的符號。C語言中不禁止你隨便聲明符號的類型，但是類型不匹配是Undefined Behavior。

假如我們有三個c文件，分別是a.c，b.c，main.c：

// a.c
int foo(int a, int b){return a + b;
}

// b.c
int x = 100, y = 200;

// main.c
extern int x, y;
int foo(int a, int b);
int main(){printf("%d + %d = %d\n", x, y, foo(x, y));
}

我們在main.c中聲明了外部變量x,y和函數foo，C語言并不禁止我們這么做，并且在聲明時，C也不會做什么類型檢查。當然，在編譯main.c的時候，我們看不到這些外部變量和函數的定義，也不知道它們在哪里。

我們編譯鏈接這些代碼，Makfile如下：

CFLAGS := -Osa.out: a.o b.o main.ogcc -static -Wl,--verbose a.o b.o main.oa.o: a.cgcc $(CFLAGS) -c a.cb.o: b.cgcc $(CFLAGS) -c b.cmain.o: main.cgcc $(CFLAGS) -c main.cclean:rm -f *.o a.out

結果生成的可執行文件可以正常地輸出我們想要的內容。

make
./a.out
# 輸出：
# 100 + 200 = 300

我們知道foo這個符號是一個函數名，在代碼區。但這時，如果我們將main.c中的foo聲明為一個整型，并且直接打印出這個整型，然后嘗試對其加一。即我們將main.c改寫為下面這樣，會發生什么事呢？

// main.c (changed)
#include <stdio.h>
extern int x, y;
// int foo(int a, int b);
extern int foo;
int main(){printf("%x\n", foo);foo += 1;// printf("%d + %d = %d\n", x, y, foo(x, y));
}

輸出：

c337048d
Segmentation fault (core dumped)

我們發現，其實是能夠打印出四個字節（整型為4個字節），但這四個字節是什么東西呢？

C語言中的類型：C語言中的其實是可以理解為沒有類型的，在C語言的眼中只有內存和指針，也就是內存地址，而所謂的C語言中的類型，其實就是對這個地址的一個解讀。比如有符號整型，就按照補碼解讀接下來的4個字節地址；又比如浮點型，就是按照IEEE754的浮點數規定來解讀接下來的4字節地址。

那我們這里將符號foo定義為了整型，那編譯器也會按照整型4個自己來解讀它，而這個地址指針指向的其實還是函數foo的地址。那這四個字節應該就是函數foo在代碼段的前四個字節。我們不妨用objdump反匯編來驗證我們的想法：

objdump -d a.out

輸出（節選）：

我們看到，foo函數在代碼段的前四個字節的地址確是就是我們上面打印輸出的c3 37 04 8d（注意字節序為小端法）。

那我們接下來試圖對foo進行加一操作相當于是對代碼段的寫操作，而我們知道內存中的代碼段是 可讀可執行不可寫 的，這就對應了上面輸出的Segmentation fault (core dumped)。

總結一下，通過這個例子，我們應當理解：

1. 編譯鏈接的需求：允許引用其他文件（C標準成為編譯單元，Compilation Unit）里定義的符號。C語言中不禁止你隨便聲明符號的類型，但是類型不匹配是Undefined Behavior。
2. C語言中類型的概念：C語言中的其實是可以理解為沒有類型的，在C語言的眼中只有內存和指針，也就是內存地址，而所謂的C語言中的類型，其實就是對這個地址的一個解讀。

程序的編譯 - 可重定向文件

我們先用file命令來查看main.c編譯生成的main.o文件的屬性：

file main.o

輸出：

main.o: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), not stripped

我們看到這里的main.o文件是可重定向( relocatable) 的ELF文件，這里的重定向指的就是我們鏈接過程中對外部符號的引用。也就是說，編譯過的main.o文件對于其中聲明的外部符號如foo，x,y，是不知道的。

既然外部的符號是在鏈接時才會被main程序知道，那在編譯main程序，生成可重定向文件時這些外部的符號是怎么處理的呢？我們同樣通過objdump工具來查看編譯出的main.o文件（未修改的原版本）：

objdump -d main.o

輸出：

main在編譯的時候，引用的外部符號就只能 ”留空(0)“ 了。

我們看到，在編譯但還未鏈接的main.o文件中，對于引用的外界符號的部分是用留空的方式用0暫時填充的。即上圖中紅框框出來的位置。注意圖中的最后一列是筆者添加的注釋，指明了本行中留空的地方對應那個外部符號。

另外注意這里的%rip相對尋址的偏移量都是0，一會兒我們會講到，在靜態鏈接完成之后，它們的偏移量會被填上正確的數值。

我們已經知道在編譯時生成的文件中外部符號的部分使用0暫時留空的，這些外部符號是待鏈接時再填充的。那么，我們在鏈接時究竟需要填充哪些位置呢？我們可以使用readelf工具來查看ELF文件的重定位信息：

readelf -r main.o

這個圖中上方是readelf的結果，下面是objdump的結果，筆者在這里已經將前兩個外部符號的偏移量的對應關系用紅色箭頭指了出來，其他的以此類推。這種對應也可以證明我們上面的分析是正確的的。

應當講，可重定向ELF文件（如main.o）已經告訴了我們足夠多的信息，指示我們應該將相應的外部符號填充到哪個位置。

另外，注意%rip寄存器指向了當前指令的末尾，也就是下一條指令的開頭，所以上圖中最后的偏移量要減4（如 y - 4）。

程序的靜態鏈接

簡單講，程序的靜態鏈接是會把所需要的文件鏈接起來生成可執行的二進制文件，將相應的外部符號，填入正確的位置（就像我們上面查看的那樣）。

我們可以通過使用gcc的 -Wl,--verbose將--verbose傳遞給鏈接器ld，從而直接觀察到整個靜態鏈接的過程，包括：

• ldscript里面各個section是按照何種順序 “粘貼”
• ctors / dtors (constructors / destructores) 的實現，（ 我們用過__attribute__((contructor)) ）
• 只讀數據和讀寫數據之間的padding，. = DATA_SEGMENT_ALIGN …

我們可以通過objdump來查看靜態鏈接完成以后生成的可執行文件a.out的內容：

objdump -d a.out

注意，這個a.out的objdump結果圖要與我們之前看到的main.o的objdump輸出對比著來看。

我們可以看到，之前填0留空的地方都被填充上了正確的數值，%rip相對尋址的偏移量以被填上了正確的數值，而且objdump也能夠正確地解析出我們的外部符號名（最后一列）的框。

靜態ELF加載器：加載 a.out 執行

靜態ELF文件的加載：將磁盤上靜態鏈接的可執行文件按照ELF program header，正確地搬運到內存中執行。

操作系統在execve時完成：

• 操作系統在內核態調用mmap
  • 進程還未準備好時，由內核直接執行 ”系統調用“
  • 映射好 a.out 的代碼、數據、堆區、堆棧、vvar、vdso、vsyscall
• 更簡單的實現：直接讀入進程的地址空間

加載完成之后，靜態鏈接的程序就開始從ELF entry開始執行，之后就變成我們熟悉的狀態機，唯一的行為就是取指執行。

我們通過readelf來查看a.out文件的信息：

readelf -h a.out

輸出：

我們這里看到，程序的入口地址是：Entry point address: 0x400a80。我們接著用gdb來調試：

上圖是筆者在gdb中調試的一些內容：

1. 我們用starti來使得程序在第一條指令就停下，可以看到，程序確實是從0x400180開始的，與我們上面查到的入口地址一致。
2. 而我們用cat /proc/[PID]/maps 來查看這個程序中內存的內容，看到我們之前提到的代碼、數據、堆區、堆棧、vvar、vdso、vsyscall都已經被映射進了內存中。

調試的結果符合我們對靜態程序加載時操作系統的行為的預期。

總結：靜態鏈接與加載

1. 由于我們不想將所有的代碼都寫到同一個文件中，所以我們需要分文件編寫并編譯，然后鏈接。
2. 對于靜態鏈接而言。編譯某個文件時會將外部符號先留空為0，然后在靜態鏈接時，將所有的留空的地方正確地進行填充。
3. 在靜態加載時，操作系統會調用mmap將我們運行這個程序所需要的代碼、數據、堆區、堆棧、vvar、vdso、vsyscall等信息都映射進內存，然后從ELF entry的入口地址開始執行。

動態鏈接與加載

為什么需要動態鏈接/加載？

libc.so中有300K 條指令，2 MiB 大小，每個程序如果都靜態鏈接，浪費的空間很大，最好是整個系統里只有一個 libc 的副本，而每個用到 libc 的程序在運行時都可以用到 libc 中的代碼。

• 文件系統里只有一個副本 (libc.so)
• 內存里只有一個副本

問題：真的整個操作系統里只有一個 libc 的副本嗎？

• 方法 1: 看 Linux Kernel 的 trace
• 方法 2: 調試 Linux Kernel, 查看內存映射 (QEMU monitor)
• 方法 3: 簡單做個實驗

實驗驗證

我們通過創建一個動態鏈接庫 libhuge.so， 然后創建1000個進程去調用這個庫中的foo函數，該函數是128M 個 nop。如果程序不是動態鏈接的話，1000 * 128MB的內存占用足以撐爆大多數個人電腦的內存。而如果程序確實是動態鏈接的，即內存中只有一份代碼，那么只會有很小的內存占用。我們是這樣做的：

首先我們有huge.S：

.global foo
foo:# 128MiB of nop.fill 1024 * 1024 * 128, 1, 0x90ret

這就是我們剛才說的一個動態鏈接庫的源代碼。我們一會兒會把他編譯成 libhuge.so供我們的huge.c調用，我們的huge.c是這樣的：

#include <unistd.h>
#include <stdio.h>
int main(){foo(); // huge code, dynamic linkedprintf("pid = %d\n", getpid());while (1) sleep(1);
}

它會調用foo函數，并在結束后打印自己的PID，然后睡眠。Makefile如下：

LIB := /tmp/libhuge.soall: $(LIB) a.out$(LIB): huge.Sgcc -fPIC -shared huge.S -o $@a.out: huge.c $(LIB)gcc -o $@ huge.c -L/tmp -lhugeclean:rm -f *.so *.out $(LIB)

正如我們剛才所介紹的，我們會先將huge.S編譯成動態鏈接庫libhuge.so放在/tmp下，然后我們的huge.c回去動態鏈接這個庫，并完成自己的代碼。這還不夠，我們要創建1000個進程來執行上述行為。這樣才能驗證我們的動態鏈接是不是在內存中真的只有一份代碼，我們用下面的腳本來完成：

#!/bin/bash# for i in {1...1000}
for i in `seq 1 100`
doLD_LIBRARY_PATH=/tmp ./a.out &
donewait
# ps | grep "a.out" | grep -Po "^(\d)*" | xargs kill -9  用于清空生成的進程

實驗證明，我們的操作系統能夠很好地運行這1000個進程，并且內存只多占用了 400MB。也就是說，庫中的foo函數確實是動態鏈接的，內存中只有一份foo的副本。

這在操作系統內核不難實現：所有以只讀方式映射同一個文件的部分（如代碼部分）時，都指向同一個副本，這個過程中會創建引用計數。

實現動態鏈接與加載

我們要實現動態鏈接，需要具體做到哪些事情呢？我們希望有一個庫函數，其中包含一些代碼，所有的進程鏈接這一段代碼，這段代碼在內存中只有一份拷貝。

實現動態加載（1）

需求1：加載純粹的代碼

編譯成位置無關代碼（Position Independent Code, PIC）即可，即引用代碼（跳轉）全部使用PC相對尋址。x86已經是這樣了。直接把代碼mmap進地址空間就行了。

# foo.S
.global fool
foo:movl $1, %eaxret

比如上面這段代碼，它很簡單，就是返回1。

loader.c

實現動態加載（2）

需求2：動態鏈接庫只有純粹的代碼沒有數據可不行，我們要能加載代碼，并且代碼有附帶的數據。

這也好辦，將代碼和數據放在一起，然后都使用PC相對尋址就好了。

對于x86不支持rip相對尋址，我們可以通過 call __i686. get_pc_thunk.bx 來得到下條指令的地址。

我們有這樣一段代碼：

# bar.S
x:      # 數據不能共享 （MAP_PRIVATE 方式映射）.int 0.global bar
bar:addl $1, x(%rip)movl x(%rip), %eaxret

這相當于這樣一段C代碼：

int bar(){static int x = 0;return ++x;
}

即在靜態區定義一個變量x，然后每次調用bar函數時都會將x加一并返回。這也是一段位置無關代碼，也可以直接mmap到內存中去執行。

實現動態加載（3）

需求3：比較難的是，一個文件或者一個動態鏈接庫想要訪問另外一個動態鏈接庫導出的符號。因為我們想要知道的符號（比如bar）也是動態加載的，也就是說，符號的地址是運行（加載）的時候才能確定的。而我們在編譯（比如編譯baz時）的時候無法知道動態加載的符號bar的地址。即允許訪問其他動態鏈接庫導出的符號（代碼 / 數據）。

解決方法是我們用一張表，編譯時編譯成：call *table[bar]。bar.o會先被映射到進程的地址空間中，然后，我們要將baz.o映射到地址空間時，我們會給baz所保有的這張表中bar所對應的表項填上正確的數值，即此時已知的bar的地址。即我們為每個動態加載的符號（代碼 / 數據）創建一張變，在運行時每次用到這些動態符號時，才解析符號的地址。

.global ..bar 
..bat: bar:.quad 0.global baz
baz:movq baz(%rip), %rdicall *%rdiret

重填（相當于在運行時重做靜態鏈接），這樣行嗎？不行，因為這樣違背了我們動態鏈接的初衷：希望整個內存中只有一份代碼的副本，而每次重填會導致每次都在內存中多一份代碼的副本。而上面的解決方案，只有這張表，是需要復制的，這大幅減少了系統中冗余的內存。

總結

總結一下，實現動態鏈接和加載就是兩個關鍵點：

1. PIC位置無關代碼，不管是代碼還是數據，我們全部都要通過PC相對尋址，來使得它們是位置無關代碼。
2. 要引用動態鏈接庫中的符號（編譯時不知道）時，我們創建一張表，在運行（加載）時將其填上正確的地址。

例子

假如我們是十幾種有這樣一個動態鏈接（共享代碼）的需求：

• main需要調用libc中的printf
• printf需要調用libfoo中的foo

我們知道，動態加載的程序最先并不是從main的入口地址開始執行的。而是需要先由加載器libld進行動態加載。libld由操作系統加載，按照相互依賴相反的方向加載：

1. libld加載libfoo，一切順利
2. libld加載libc
   • libc對foo的調用在編譯時，被編譯為call *libc.tab[FOO]
   • libld調用dl_runtime_resolve解析符號，填入libc.tab[FOO]，因為此時libfoo已經被加載到地址空間中了，foo地址是已知的
3. libld完成main的初始化
   • a.out對printf的調用在編譯時，被編譯成call *a.out.tab[PRINTF]
   • libld機械printf的地址，填入call *a.out.tab[PRINTF]，因為此時libc已經被加載到地址空間中了，printf地址是已知的

所有的填表都完成之后，就跳轉到main的入口地址開始執行。

ELF 動態鏈接與加載

上面一種簡化版的動態加載過程，實際的ELF動態加載比這要復雜一點。

GOT (Global Offset Table)

GOT

GOT：shared object用來存儲動態符號的表格。庫函數有，可執行文件也有。

所以用file命令查看a.out和libc.so時都是 ”shared object“ 。也就是說我們生成的可執行文件其實和庫函數是同一種文件格式。它們都需要調用其他的動態鏈接庫中的符號。

GOT中儲存的數據

• GOT[0]：.dynamic節的地址
• GOT[1]：link map，用于遍歷依賴的動態鏈接庫
• GOT[2]：dl_runtime_resolve 的地址，即call *GOT[2] 可以完成符號解析
• GOT[i]：程序所需的動態符號的地址（printf, …）

lazy symbol resolution 延遲符號解析

新需求：能否降低實際沒有調用到的符號的開銷？

程序可能會引用很多符號，但執行時可能大部分符號都沒用到，逐個dl_runtime_resolve的話會造成不必要的開銷。

lazy symbol resolution

想法：加載時設置為NULL，加載時來判斷 / 解析

使用一小段 ”trampoline code“ 跳板代碼

• 如果符號還未解析，就解析
• 跳轉到解析后的符號執行

int print_internal(const char *fmt, ...){if (GOT[PRINRF]){GOT[PRINTF] = call_dl_runtime_reslove("printf");}return GOT[PRINTF]{...};
}

需要編譯器把向printf（動態鏈接庫）的調用翻譯成call printf_internal

壞處：fast path多做一次判斷：call + load + 判斷 + jump，會損失一定的性能。

黑科技：讓printf@GOT指向trampoline的下一條指令。

• 只有兩條指令：call print@plt; jmp *a.out.GOT[PRINTF]
• 對現代處理器非常友好，因為有branch-target-buffer（BTB），幾乎不損失性能。

Takeaways and Wrap-up

我們通過逐步把需求進行分解，從加載的視角理解鏈接：

1. 需要加載一段代碼（foo）：PIC（通過使用PC相對尋址）+ mmap
2. 代碼需要伴隨數據（bar）：數據也使用PC相對尋址 + mmap
3. 需要解析動態符號（baz）：查表（GOT）、優化：PLT，lazy symbol resolve