Dynamic Linking Relocation

Posted on Edited on

Load process 在 dynamic linking 的差別是 load 完執行檔後 OS 會先看 ELF 的 .interp section 知道要 load 哪個 dynamic linker，OS load dynamic linker 並將控制權先交給它，在 linux 下是 /lib/x86_64-linux-gnu/ld-2.19.so（很明顯也是個 shared library）。

dynamic linker 做的事情分成三步：

  1. 啟動
  2. load 所有需要的 shared library
  3. relocation & initialization

dynamic linker 本身也是個 shared library，但它有一些限制，例如不能有依賴的 shared library、不能使用 global 變數、不能 call function 等等。在啟動階段，dynamic linker 會先找到自己的 GOT，而 GOT 第一個 entry 存的是 .dynamic section 的 offset。.dynamic section 保存了 dynamic linker 需要的資訊，例如依賴哪些 shared library，dynamic symbol table、dynamic relocation table 的位置等等。readelf -d 可以查看 .dynamic section。

透過 .dynamic 裡的資訊，linker 可以知道自己的 relocation table 以及 symbol table，能對自己進行 relocation。linker 做完針對自己的 relocation 後，才能開始使用 global 變數、call function 等等。

啟動完成後，dynamic linker 將自己的 symbol 以及 executable file 的 symbol 合併到 global symbol table。接著開始從 executable file 的 .dynamic 得知依賴哪些 shared library，一一打開 shared library 並將之 load 到 memory 中、建立 mapping，並且將 shared library 的 symbol 合併到 global symbol table，再搜尋 shared library 的 dependency。如此 traverse 整棵 shared library dependency tree 之後，即 load 完所需的 shared library。通常會以 BFS traverse dependency tree。

symbol 的部份，ELF 以 dynamic symbol table 保存模組間 import 及 export symbol 的關係，位於 .dynsym，作用以及記錄的資訊跟 .symtab 差不多，但只記錄給其他模組使用的 symbol 以及使用其他模組的 symbol。

traverse dependency tree 的順序跟 symbol 的優先度有關──當兩個 shared library 有相同的 symbol 時要使用誰的？在 Linux 中會優先使用先 load 的 symbol。也就是說，shared library 的 load 順序會影響 symbol 的優先度，而 link 時指定的 library 順序會影響 load 的順序。

接著，linker 開始 traverse executable file 以及 shared library 的 relocation table，使用 global symbol table 來修正 GOT 及 PLT 內的 address。dynamic linking 中的 relocation table .rela.dyn 用來修正 .got 及 data section，.rela.plt 則修正 .got.plt section 內的 address。relocation 完成後，如果 shared library 擁有 .init section，dynamic linker 會執行它以進行對 shared library 的初始化。

最後，dynamic linker 將控制權交給程式的入口開始執行。

Relocation example

雖然簡單來說 dynamic linker 會在 load shared library 時進行 relocation，但如Dynamic Linking PIC所說的，實際上 ELF 是以 lazy binding 來 bind symbol。用個簡單例子看看怎麼做的：

foo.h
1
2
3
4
#ifndef __FOO_H
#define __FOO_H
int foo(int x, int y);
#endif
foo.c
1
2
3
4
int foo(int x, int y)
{
    return (x + y);
}
bar.h
1
2
3
4
#ifndef __BAR_H
#define __BAR_H
void bar(int a, int b, int n);
#endif
bar.c
1
2
3
4
5
6
#include "foo.h"
void bar(int a, int b, int n)
{
    foo(a, b);
    foo(b, n);
}
main.c
1
2
3
4
5
6
7
#include "bar.h"

int main()
{
    bar(2, 3, 10);
    return 0;
}
1
2
3
$ gcc -g -shared -fPIC foo.c -o libfoo.so
$ gcc -g -shared -fPIC bar.c -o libbar.so
$ gcc -g main.c ./libfoo.so ./libbar.so -o main

最後編 executable file 時指定的 library 順序會影響 load library 的順序。

在 main()、bar() 跟 foo() 設中斷點，停在 main() 之後觀察 foo 的 relocation 資訊：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
$ gdb ./main
Reading symbols from ./main...done.
(gdb) b main
Breakpoint 1 at 0x40067a: file main.c, line 5.
(gdb) b bar
Breakpoint 2 at 0x400550
(gdb) b foo
Function "foo" not defined.
Make breakpoint pending on future shared library load? (y or [n]) y
Breakpoint 3 (foo) pending.
(gdb) r
Starting program: /home/cjw/source/dynamic-link/relocate/main

Breakpoint 1, main () at main.c:5
5           bar(2, 3, 10);

$ cat /proc/`pgrep main`/maps
00400000-00401000 r-xp 00000000 08:24 8259464                            /home/cjw/source/dynamic-link/relocate/main
00600000-00601000 rw-p 00000000 08:24 8259464                            /home/cjw/source/dynamic-link/relocate/main
7ffff762f000-7ffff77d0000 r-xp 00000000 08:22 1572872                    /lib/x86_64-linux-gnu/libc-2.19.so
7ffff77d0000-7ffff79d0000 ---p 001a1000 08:22 1572872                    /lib/x86_64-linux-gnu/libc-2.19.so
7ffff79d0000-7ffff79d4000 r--p 001a1000 08:22 1572872                    /lib/x86_64-linux-gnu/libc-2.19.so
7ffff79d4000-7ffff79d6000 rw-p 001a5000 08:22 1572872                    /lib/x86_64-linux-gnu/libc-2.19.so
7ffff79d6000-7ffff79da000 rw-p 00000000 00:00 0
7ffff79da000-7ffff79db000 r-xp 00000000 08:24 8259463                    /home/cjw/source/dynamic-link/relocate/libbar.so
7ffff79db000-7ffff7bda000 ---p 00001000 08:24 8259463                    /home/cjw/source/dynamic-link/relocate/libbar.so
7ffff7bda000-7ffff7bdb000 rw-p 00000000 08:24 8259463                    /home/cjw/source/dynamic-link/relocate/libbar.so
7ffff7bdb000-7ffff7bdc000 r-xp 00000000 08:24 8259445                    /home/cjw/source/dynamic-link/relocate/libfoo.so
7ffff7bdc000-7ffff7ddb000 ---p 00001000 08:24 8259445                    /home/cjw/source/dynamic-link/relocate/libfoo.so
7ffff7ddb000-7ffff7ddc000 rw-p 00000000 08:24 8259445                    /home/cjw/source/dynamic-link/relocate/libfoo.so
7ffff7ddc000-7ffff7dfc000 r-xp 00000000 08:22 1572869                    /lib/x86_64-linux-gnu/ld-2.19.so
7ffff7fd5000-7ffff7fd8000 rw-p 00000000 00:00 0
7ffff7ff6000-7ffff7ff8000 rw-p 00000000 00:00 0
7ffff7ff8000-7ffff7ffa000 r-xp 00000000 00:00 0                          [vdso]
7ffff7ffa000-7ffff7ffc000 r--p 00000000 00:00 0                          [vvar]
7ffff7ffc000-7ffff7ffd000 r--p 00020000 08:22 1572869                    /lib/x86_64-linux-gnu/ld-2.19.so
7ffff7ffd000-7ffff7ffe000 rw-p 00021000 08:22 1572869                    /lib/x86_64-linux-gnu/ld-2.19.so
7ffff7ffe000-7ffff7fff000 rw-p 00000000 00:00 0
7ffffffdd000-7ffffffff000 rw-p 00000000 00:00 0                          [stack]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

$ readelf -r libbar.so

Relocation section '.rela.dyn' at offset 0x430 contains 8 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
...

Relocation section '.rela.plt' at offset 0x4f0 contains 3 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000200980  000300000007 R_X86_64_JUMP_SLO 0000000000000000 __gmon_start__ + 0
000000200988  000400000007 R_X86_64_JUMP_SLO 0000000000000000 foo + 0
000000200990  000700000007 R_X86_64_JUMP_SLO 0000000000000000 __cxa_finalize + 0

(gdb) x/1xbg 0x7ffff79da000+0x000000200988
0x7ffff7bda988: 0x00007ffff79da586

(gdb) info address foo
Symbol "foo" is a function at address 0x7ffff7bdb660.

libbar.so 裡需要修正 address 的位置是 0x7ffff79da000 + 0x000000200988，因為 library 要到 load 的時候才能知道起始位置，所以必須用 offset 算出要修改的地方，因為還沒用過 foo，這個 address 的內容還不是 foo 的 address。

1
2
3
4
5
$ readelf -S libbar.so
...
  [20] .got.plt          PROGBITS         0000000000200968  00000968
       0000000000000030  0000000000000008  WA       0     0     8
...

從 relocation entry 來看，relocate 的 offset 是 0x000000200988，在 .got.plt 裡。0x7ffff7bda988 這個位置在 load libbar.so 的第三個 segment，屬性是 rw-p，是可以修改的。

繼續跑看第一次 call foo()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
(gdb) c
Continuing.

Breakpoint 2, bar (a=2, b=3, n=10) at bar.c:7
7           foo(a, b);
(gdb) x/10i $pc
=> 0x7ffff79da6b1 <bar+17>:     mov    -0x8(%rbp),%edx
   0x7ffff79da6b4 <bar+20>:     mov    -0x4(%rbp),%eax
   0x7ffff79da6b7 <bar+23>:     mov    %edx,%esi
   0x7ffff79da6b9 <bar+25>:     mov    %eax,%edi
   0x7ffff79da6bb <bar+27>:     callq  0x7ffff79da580 <foo@plt>
   0x7ffff79da6c0 <bar+32>:     mov    -0xc(%rbp),%edx
   0x7ffff79da6c3 <bar+35>:     mov    -0x8(%rbp),%eax
   0x7ffff79da6c6 <bar+38>:     mov    %edx,%esi
   0x7ffff79da6c8 <bar+40>:     mov    %eax,%edi
   0x7ffff79da6ca <bar+42>:     callq  0x7ffff79da580 <foo@plt>
(gdb) b *0x7ffff79da6bb
(gdb) c
(gdb) x/1i $pc
=> 0x7ffff79da6bb <bar+27>:     callq  0x7ffff79da580 <foo@plt>
(gdb) si
0x00007ffff79da580 in foo@plt () from ./libbar.so
(gdb) x/3i $pc
=> 0x7ffff79da580 <foo@plt>:    jmpq   *0x200402(%rip)        # 0x7ffff7bda988
   0x7ffff79da586 <foo@plt+6>:  pushq  $0x1
   0x7ffff79da58b <foo@plt+11>: jmpq   0x7ffff79da560
(gdb) si
0x00007ffff79da586 in foo@plt () from ./libbar.so
2: x/i $pc
=> 0x7ffff79da586 <foo@plt+6>:  pushq  $0x1
(gdb) 
0x00007ffff79da58b in foo@plt () from ./libbar.so
2: x/i $pc
=> 0x7ffff79da58b <foo@plt+11>: jmpq   0x7ffff79da560
(gdb) 
0x00007ffff79da560 in ?? () from ./libbar.so
2: x/i $pc
=> 0x7ffff79da560:      pushq  0x20040a(%rip)        # 0x7ffff7bda970
(gdb) 
0x00007ffff79da566 in ?? () from ./libbar.so
2: x/i $pc
=> 0x7ffff79da566:      jmpq   *0x20040c(%rip)        # 0x7ffff7bda978
(gdb) x/3i $pc
=> 0x7ffff79da566:      jmpq   *0x20040c(%rip)        # 0x7ffff7bda978
   0x7ffff79da56c:      nopl   0x0(%rax)
   0x7ffff79da570 <__gmon_start__@plt>: jmpq   *0x20040a(%rip)        # 0x7ffff7bda980
(gdb) si
_dl_runtime_resolve () at ../sysdeps/x86_64/dl-trampoline.S:34
34      ../sysdeps/x86_64/dl-trampoline.S: No such file or directory.
2: x/i $pc
=> 0x7ffff7df02b0 <_dl_runtime_resolve>:        sub    $0x38,%rsp
(gdb) x/1xbg 0x7ffff7bda978
0x7ffff7bda978: 0x00007ffff7df02b0

0x7ffff79da580 是 foo 在 PLT 裡的位置，call foo() 的時候會跳過去。這個位置位於 load libbar.so 的第一個 segment，屬性 r-xp，可執行，同時也代表 PLT 是被放在可執行的 segment 裡。到 foo@plt 後會再跳到 foo 在 .got.plt 的 entry 所指的 address，也就是前面看到的 0x00007ffff79da586，同時也是 foo@plt 的下一個指令，最後在 0x7ffff79da566: jmpq *0x20040c(%rip) # 0x7ffff7bda978 會跳到 0x7ffff7bda978 記錄的位置 0x00007ffff7df02b0，即 _dl_runtime_resolve 的入口，到這邊當然是要 resolve symbol 啦，至於中間 push 的動作跟給 _dl_runtime_resolve 參數有關。

設中斷點在 call 完 foo() 之後，看看 resolve 完 foo 在 .got.plt 裡對應的 entry 會如何：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
(gdb) b *0x7ffff79da6c0
Breakpoint 5 at 0x7ffff79da6c0: file bar.c, line 8.
(gdb) c
Continuing.

Breakpoint 3, foo (x=2, y=3) at foo.c:3
3           return (x + y);
2: x/i $pc
=> 0x7ffff7bdb66a <foo+10>:     mov    -0x4(%rbp),%edx
1: $pc = (void (*)()) 0x7ffff7bdb66a <foo+10>
(gdb) c
Continuing.

Breakpoint 5, bar (a=2, b=3, n=10) at bar.c:8
8           foo(b, n);
2: x/i $pc
=> 0x7ffff79da6c0 <bar+32>:     mov    -0xc(%rbp),%edx
1: $pc = (void (*)()) 0x7ffff79da6c0 <bar+32>
(gdb) x/7i $pc
=> 0x7ffff79da6c0 <bar+32>:     mov    -0xc(%rbp),%edx
   0x7ffff79da6c3 <bar+35>:     mov    -0x8(%rbp),%eax
   0x7ffff79da6c6 <bar+38>:     mov    %edx,%esi
   0x7ffff79da6c8 <bar+40>:     mov    %eax,%edi
   0x7ffff79da6ca <bar+42>:     callq  0x7ffff79da580 <foo@plt>
   0x7ffff79da6cf <bar+47>:     leaveq 
   0x7ffff79da6d0 <bar+48>:     retq   
(gdb) x/1xbg 0x7ffff79da000+0x000000200988
0x7ffff7bda988: 0x00007ffff7bdb660
(gdb) info address foo
Symbol "foo" is a function at address 0x7ffff7bdb660.

出現 foo 的 address 啦！

再看第二次 call foo() 會怎樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
(gdb) b *0x7ffff79da6ca
Breakpoint 6 at 0x7ffff79da6ca: file bar.c, line 8.
(gdb) c
Continuing.

Breakpoint 6, 0x00007ffff79da6ca in bar (a=2, b=3, n=10) at bar.c:8
8           foo(b, n);
2: x/i $pc
=> 0x7ffff79da6ca <bar+42>:     callq  0x7ffff79da580 <foo@plt>
(gdb) si
0x00007ffff79da580 in foo@plt () from ./libbar.so
2: x/i $pc
=> 0x7ffff79da580 <foo@plt>:    jmpq   *0x200402(%rip)        # 0x7ffff7bda988
1: $pc = (void (*)()) 0x7ffff79da580 <foo@plt>
(gdb) x/5i $pc
=> 0x7ffff79da580 <foo@plt>:    jmpq   *0x200402(%rip)        # 0x7ffff7bda988
   0x7ffff79da586 <foo@plt+6>:  pushq  $0x1
   0x7ffff79da58b <foo@plt+11>: jmpq   0x7ffff79da560
   0x7ffff79da590 <__cxa_finalize@plt>: jmpq   *0x2003fa(%rip)        # 0x7ffff7bda990
   0x7ffff79da596 <__cxa_finalize@plt+6>:       pushq  $0x2
(gdb) si
foo (x=2, y=3) at foo.c:2
2       {
2: x/i $pc
=> 0x7ffff7bdb660 <foo>:        push   %rbp
1: $pc = (void (*)()) 0x7ffff7bdb660 <foo>

一樣跳到 foo@plt，接著會跳到 foo 於 .got.plt 所記錄的 address，現在是 foo() 的 address 了所以就會進 foo() 了！

總結上面的 lazy binding 行為，call function 時會跳到 PLT 裡執行，進到 PLT 的第一個指令是跳到 symbol 於 GOT 裡所指向的位置。第一次 call 時 GOT 記錄的 address 會是 PLT 對應的下一個指令，相當於繼續執行 PLT 的 instruction，接著一路 call 到 resolve symbol 的 function 找 symbol 以及將 address 填進 GOT。之後再 call 到相同 function 一樣會先到 PLT，但第一個指令就會從 GOT 得到正確 address、跳去該 function 執行。

觀察 main 裡的 bar 也會有類似的情況，只是 main 因為是 executable file，relocation entry 的 offset 已經是 load 進 memory 的 address，可以不用像 shared library 那樣要用 load 的 memory 開頭算 offset。

Initialization

除了一般會進入 shared library 的 .init section 進行初始化外，GCC 還提供了 shared library 的 constructor 及 destructor 擴充語法，可以讓 function 在 load shared library 時執行以做更多初始化的動作，宣告語法如下：

1
2
void __attribute__((constructor)) init();
void __attribute__((destructor)) fini();

使用這種 constructor 跟 destructor 必須使用系統預設的 standard runtime library 以及啟動檔案，不可以用 -nostartfiles 以及 -nostdlib 參數。constructor 會在 load shared library 時執行（執行 main 之前），而 destructor 則會在執行 exit() 時執行。如果是 Explicit Runtime Linking，constructor 會在 dlopen() 時執行，destructor 則在 dlclose() 時執行。

Murmur & 省略的細節

上面這樣順順列下來看起來好簡單，但其實我找 GOT 跟 PLT 到底在做什麼找～很～久～一直錯把 GOT 當 PLT，就搞不懂是在幹嘛……

PIC 跟 GOT/PLT 還有不少細節，例如 ELF 怎麼處理 library 內跟跨 library 的 function call？變數的 relocation 怎麼做的？resolve function 怎麼知道要找哪個 symbol？這些先暫時略過，不然我永遠寫不完……Orz