リンカのお仕事

はじめに

突然ですが、こんなC++プログラムをコンパイルしてみましょう.

#include <cstdio>

void func();

int main() {
  func();
}

funcという関数のプロトタイプ宣言があり、それをmain関数内で呼び出していますが、実体が定義されていません。これをコンパイルしようとすると、例えばこんなエラーがでます。

$ g++ test.cpp
/usr/bin/ld: /tmp/ccFEAPJn.o: in function `main':
test.cpp:(.text+0x9): undefined reference to `func()'
collect2: error: ld returned 1 exit status

エラーメッセージは「funcなんて知らないよ」というものですが、エラーを出しているのは/usr/bin/ldというプログラムです。これは、リンカ(linker)と呼ばれるソフトウェアです。

リンカというと、「分割コンパイルされて作られたオブジェクトファイルをくっつけて実行バイナリを作るもの」というイメージがあるかもしれませんが、他にもいろいろな仕事をしています。それをちょっとだけ見てみましょう。以下、Linux(っていうかELF)の話に限定します。GCCとUbuntuを使います。

分割コンパイル

まずは適当に分割コンパイルしてみましょう。まず、main.cppはこんな感じです。

#include <cstdio>

int a = 1;
int b = 2;

int add(int, int);

int main() {
  int c = add(a, b);
  printf("%d\n", c);
}

addという関数を宣言して呼び出しています。その実体をadd.cppに書いてやりましょう。

int add(int x, int y) {
  return x + y;
}

単に二つの引数を足して返すだけの関数ですね。これを分割コンパイルしましょう。g++に-cオプションをつけると、コンパイルのみおこなって、オブジェクトファイルを作ってくれます。

$ g++ -c main.cpp
$ g++ -c add.cpp

これでmain.o、add.oができました。これをリンクします。g++に.oファイルを食わせるとリンクして、実行バイナリを作ってくれます。

$ g++ main.o add.o
$ ./a.out
3

実行バイナリができて実行できました。これが分割コンパイルです。

関数のアドレス

さて、プログラムを実行する際、コードがメモリ上にロードされています。そして「最初の場所」から順番に実行されていきます。関数とは、メモリ上のラベルであり、どこかのアドレスを指しています。関数呼び出しとは、

• 現在実行中のプログラムのアドレスを記憶して
• 呼びたい関数のアドレスへジャンプして
• その関数の処理が終わったら記憶していたアドレスへ戻ってくる

という一連の処理のことです。

それを見るために、関数のアドレスを表示させてみましょう。さっきのmain.cppを以下のように書き換えてみます。

#include <cstdio>

int a = 1;
int b = 2;

int add(int, int);

int main() {
  int c = add(a, b);
  printf("%d\n", c);
  printf("add :%p\n", add);
  printf("main:%p\n", main);
}

先ほど書いたように、関数とはメモリのどこかのアドレスを指すラベルです。そのラベルがどのアドレスを指しているか表示しています。

コンパイル、実行してみましょう。

$ g++ -c main.cpp
$ g++ main.o add.o
$ ./a.out
3
add :0x55e63ead21bd
main:0x55e63ead2149

関数の実行結果3の後に、関数のアドレスが表示されました。Ubuntuではデフォルトでaddress space layout randomization, ASLRというセキュリティが有効になっているため、実行するたびにアドレスが変わりますが、とりあえず下3桁だけ見ておけばよいです。

これを見ると、addのアドレスの下3桁が1bdに、mainのアドレスの下3桁が149になっていますね。この、関数をどのアドレスに配置すべきかは、実行バイナリであるa.outに書いてあります。readelfというコマンドで見てみましょう。

$ readelf -s ./a.out | grep FUNC | c++filt
     2: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND printf@GLIBC_2.2.5 (2)
     3: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@GLIBC_2.2.5 (2)
     6: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __cxa_finalize@GLIBC_2.2.5 (2)
    29: 0000000000001090     0 FUNC    LOCAL  DEFAULT   16 deregister_tm_clones
    30: 00000000000010c0     0 FUNC    LOCAL  DEFAULT   16 register_tm_clones
    31: 0000000000001100     0 FUNC    LOCAL  DEFAULT   16 __do_global_dtors_aux
    34: 0000000000001140     0 FUNC    LOCAL  DEFAULT   16 frame_dummy
    46: 0000000000001000     0 FUNC    LOCAL  DEFAULT   12 _init
    47: 0000000000001250     5 FUNC    GLOBAL DEFAULT   16 __libc_csu_fini
    50: 00000000000011bd    24 FUNC    GLOBAL DEFAULT   16 add(int, int)
    53: 0000000000001258     0 FUNC    GLOBAL HIDDEN    17 _fini
    54: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND printf@@GLIBC_2.2.5
    55: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@@GLIBC_
    60: 00000000000011e0   101 FUNC    GLOBAL DEFAULT   16 __libc_csu_init
    62: 0000000000001060    47 FUNC    GLOBAL DEFAULT   16 _start
    65: 0000000000001149   116 FUNC    GLOBAL DEFAULT   16 main
    68: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __cxa_finalize@@GLIBC_2.2

なんかごちゃごちゃ出てきましたが、とりあえずmainの場所は1149に、add(int, int)の場所は11bdと指定されており、確かに下3桁がそれぞれ149、1bdになっています。c++filtはC++の関数名のデマングリングをするコマンドですが、ここでは詳細には触れません。

アセンブリも見てみましょう。objdump -Sで逆アセンブルしてみます。

$ objdump -S ./a.out
(snip)
0000000000001149 <main>:
(snip)
    1165:       e8 53 00 00 00          callq  11bd <add(int, int)>
(snip)
    11bc:       c3                      retq
(snip)
00000000000011bd <add(int, int)>:
(snip)

mainとaddのアドレスがそれぞれ1149、11bdであること、また、main関数からaddを呼び出す時、callq 11bdと、addの指すアドレスが指定されていることがわかります。これを見ると、関数とはメモリ上のアドレスを指すラベルであり、関数呼び出しとはラベルの指すアドレスへのジャンプであることが実感できるかと思います。

シンボルの解決

さて、先ほどはmain.o、add.oの順番でリンクしました。順番を逆にしてみましょう。

$ g++ add.o main.o
$ ./a.out
add :0x560fd7d1c149
main:0x560fd7d1c161

addとmainのメモリの位置が入れ替わり、addの方が先になりました。readelfで見てみましょう。

$ readelf -s ./a.out | grep FUNC | c++filt
(snip)
    50: 0000000000001149    24 FUNC    GLOBAL DEFAULT   16 add(int, int)
(snip)
    65: 0000000000001161   116 FUNC    GLOBAL DEFAULT   16 main
(snip)

addのアドレスが1149に、mainのアドレスが1161になっています。つまり、関数のアドレスはリンクする順番に依存します。したがって、関数のアドレスはリンク時に決まることがわかります。

逆に言えば、リンクするまでは関数のアドレスは決まっていません。readelfでオブジェクトファイルを見てみましょうか。

$ readelf -s main.o  | c++filt
(snip)
    12: 0000000000000000   116 FUNC    GLOBAL DEFAULT    1 main
(snip)
    14: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND add(int, int)
    15: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND printf

mainは関数(FUNC)であることが書いてありますが、アドレスは決まっておらず、さらにaddやprintfはUND、つまり未定義(undefined)となっています。add.oも見てみましょう。

$ readelf -s add.o  | c++filt
(snip)
     9: 0000000000000000    24 FUNC    GLOBAL DEFAULT    1 add(int, int)
(snip)

addは関数(FUNC)であることが書いてありますが、やはりアドレスはまだ決まっていません。この状態でmain.oのアセンブリを見てみましょう。

$ objdump -S main.o | c++filt
0000000000000000 <main>:
(snip)
  1c:   e8 00 00 00 00          callq  21 <main+0x21>
  21:   89 45 fc                mov    %eax,-0x4(%rbp)

addを呼び出しているところには、仮のアドレス(callqの次の命令のアドレス)が入っています。

関数や変数はメモリ上のアドレスのどこかを指すラベルですが、こういうラベルを「シンボル」と言います。リンカは、プログラムのサイズを計算して、シンボルと実際のアドレスを紐づけます。この、ラベルへの参照を解決するのがリンカの仕事です。

スタートアップルーチン

readelfでa.outにある関数のシンボルをもう一度見てみましょう。

$ readelf -s a.out  | grep FUNC |c++filt
     2: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND printf@GLIBC_2.2.5 (2)
     3: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@GLIBC_2.2.5 (2)
     6: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __cxa_finalize@GLIBC_2.2.5 (2)
    29: 0000000000001090     0 FUNC    LOCAL  DEFAULT   16 deregister_tm_clones
    30: 00000000000010c0     0 FUNC    LOCAL  DEFAULT   16 register_tm_clones
    31: 0000000000001100     0 FUNC    LOCAL  DEFAULT   16 __do_global_dtors_aux
    34: 0000000000001140     0 FUNC    LOCAL  DEFAULT   16 frame_dummy
    46: 0000000000001000     0 FUNC    LOCAL  DEFAULT   12 _init
    47: 0000000000001250     5 FUNC    GLOBAL DEFAULT   16 __libc_csu_fini
    50: 0000000000001149    24 FUNC    GLOBAL DEFAULT   16 add(int, int)
    53: 0000000000001258     0 FUNC    GLOBAL HIDDEN    17 _fini
    54: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND printf@@GLIBC_2.2.5
    55: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@@GLIBC_
    60: 00000000000011e0   101 FUNC    GLOBAL DEFAULT   16 __libc_csu_init
    62: 0000000000001060    47 FUNC    GLOBAL DEFAULT   16 _start
    65: 0000000000001161   116 FUNC    GLOBAL DEFAULT   16 main
    68: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __cxa_finalize@@GLIBC_2.2

もともとのプログラムにはmainとaddしか定義がなく、それ以外の関数呼び出しはprintfだけだったのに、他にもいろいろ増えていることがわかりますね。こいつらをリンクするのもリンカの仕事です。このうち、_startだけ見てみましょう。

_startとは、スタートアップルーチンと呼ばれるもので、main関数を呼び出すのが主な仕事です。gdbで見てみましょう。

$ gdb ./a.out

まずは_startにブレークポイントを置きます。

(gdb) b _start
Breakpoint 1 at 0x1060

0x1060にブレークポイントが置かれました。さっきreadelfで見た_startのアドレスと同じですね。

    62: 0000000000001060    47 FUNC    GLOBAL DEFAULT   16 _start

実行すると、_startのところで止まります。

(gdb) r
Breakpoint 1, 0x0000555555555060 in _start ()

アセンブリを見てみましょう。

(gdb) disas
Dump of assembler code for function _start:
=> 0x0000555555555060 <+0>:     endbr64
   0x0000555555555064 <+4>:     xor    %ebp,%ebp
   0x0000555555555066 <+6>:     mov    %rdx,%r9
   0x0000555555555069 <+9>:     pop    %rsi
   0x000055555555506a <+10>:    mov    %rsp,%rdx
   0x000055555555506d <+13>:    and    $0xfffffffffffffff0,%rsp
   0x0000555555555071 <+17>:    push   %rax
   0x0000555555555072 <+18>:    push   %rsp
   0x0000555555555073 <+19>:    lea    0x1d6(%rip),%r8        # 0x555555555250 <__libc_csu_fini>
   0x000055555555507a <+26>:    lea    0x15f(%rip),%rcx        # 0x5555555551e0 <__libc_csu_init>
   0x0000555555555081 <+33>:    lea    0xd9(%rip),%rdi        # 0x555555555161 <main>
   0x0000555555555088 <+40>:    callq  *0x2f52(%rip)        # 0x555555557fe0
   0x000055555555508e <+46>:    hlt
End of assembler dump.

main関数が呼ばれていないことがわかります。実は、スタートアップルーチンは__libc_start_mainを呼んでおり、main関数はその関数から呼ばれます。そのためにスタートアップルーチンにmain関数場所を教えているのがここです。

   0x0000555555555081 <+33>:    lea    0xd9(%rip),%rdi        # 0x555555555161 <main>

プログラムを実行する際、この_startが最初に実行されます。したがって、こいつがリンクされていないと実行バイナリが作れません。オブジェクトファイルをg++ではなく、ldでリンクしてみましょう。

$ ld main.o add.o
ld: warning: cannot find entry symbol _start; defaulting to 0000000000401000
ld: main.o: in function `main':
main.cpp:(.text+0x36): undefined reference to `printf'
ld: main.cpp:(.text+0x51): undefined reference to `printf'
ld: main.cpp:(.text+0x69): undefined reference to `printf'

最初に実行される場所(entry symbol)であるところの_startが無いよと言われたり、printfが見つからないよと言われたりしています。実はこいつらの場所をリンカに教えているのがg++です。g++はコンパイラではなくコンパイラドライバと呼ばれるもので、裏でプリプロセッサを呼んだり、コンパイラを呼んだり、リンカを呼んだりいろいろやってくれるものです。glibcの場所などをldちゃんと教えることで、正しくリンクされ、実行バイナリができます。

まとめ

リンカのお仕事を見てみました。リンカは分割コンパイルされたオブジェクトファイルをくっつけるのも仕事ですが、その際にシンボル名を解決し、実際のアドレスと紐づけています。また、スタートアップルーチンやprintfといった関数を含むライブラリをくっつけたりするのもリンカの仕事ですが、それらのライブラリの場所をリンカに教えるのはコンパイルドライバであるg++です。

リンカはいろいろ奥が深いですが、その詳細を説明するのは私の能力を超えます。気になる人は参考文献を参照してください。

参考文献

• 実践的低レイヤプログラミングのリンカの章 リンカが何をしているか詳しく書いてあるのでざっと読んでおくと「へぇ」と思うことがいっぱいある
• github.com/rui314/mold Rui Ueyamaさんによるリンカの実装。高速な動作をするためにいろいろ工夫されており、ソースを読んでも理解は難しいが、とりあえず「リンカの中身」を見てみるのに良いかもしれない。