コンパイラが作ったバイナリをつなぎ合わせるプログラム　「lld」の作者が語る、リンカの仕組み

LLVMのリンカ「lld」オリジナルの作者

植山類氏：植山類です。今僕が作っているmoldというリンカについて発表します。

今回の発表の概要です。リンカが何かを知っている人はそんなにたくさんいないと思うので、まず説明します。次に、「mold」のポイントは速いことなのですが、速いと何がうれしいのかを説明します。そのあと、どれくらい速いのかを説明した上で、どう実現されているのか、概要を紹介します。詳細になると何時間あっても終わらないので、かなりハイレベルな話をします。

自己紹介のスライドを入れていませんが、僕はリンカを何度か作ったことがあって、LLVMのlldのオリジナルの作者も僕です。lldは一般的にAndroidやChrome OS、Chromeをビルドする時やFirefoxで使われています。ほかに任天堂のゲームコンソールやPlayStationでも使われているので、みなさんの家庭にも、lldで僕がオリジナルで作ったリンカで作られたバイナリがあると思います。それは5年くらい前の話で、2020年頃からはmoldを作っています。

リンカとは何か

リンカとはコンパイラが作ったバイナリをつなぎ合わせるプログラムです。いろいろな機能があって、マニュアルページも長くて、ドキュメントが悪いことが多いため、訳がわからないパターンが多く、難しいプログラムです。ただ、リンカそのものの概念は簡単です。

（スライドを指して）リンカが実際どの辺りで使われているか。moldの場合、makeしてみるとたくさんのコマンドが動きます。ここだと最初のclang++、これはg++と同じでコンパイラですが、コンパイラが.ccファイルを読んで、.oファイルを出力するようなものがたくさん動いて、普通は最後にその.oファイルをまとめてもう一度コンパイラに渡して最後の出力を作っていると思います。最後の太字部分が、リンカが動いているところです。Unixではコンパイラ（clangやgcc）はフロントエンドになっていて、実際にリンカのコマンドはこういうフロントエンド経由で起動されます。

例えばCコンパイラも本当はcc1というコマンドなんですが、cc1を直接起動することはなく、clangやgccのようなコマンドで起動することになっています。拡張子を見れば何をやるべきかがわかるのと、.oファイル与えられていたらプログラミング言語ではなくオブジェクトファイルなので、リンカを起動する必要があるので、リンカを起動します。

つまり、どんなプログラムをコンパイルしてもリンカが常に起動します。たとえシングルファイルのプログラムをコンパイルするとしても、内部的には1つのファイルを1つの.oに変換し、改めてld、リンカコマンドをコンパイラドライバが裏で立ち上げて、リンクを実行することになっています。

なぜリンカが必要なのか。根本的な話になりますが、実はリンカがなくてもコンピューターシステムとしては成立します。ただ、リンカなしのシステムを考えると、コンパイラが直接実行ファイルを全部出力しないといけなくなるんです。そうすると、コンパイラに全部のソースコードを一気に渡す必要があるので、それはちょっと非現実的です。プログラムのサイズが何万行や何十万行、ものによっては何億行のものも存在しますが、それを一発でコンパイルするのは実質無理です。

（スライドを指して）例えば、libcの関数があります。これらはCで書かれた関数です。libcが特別なのは単にデフォルトでついてくるライブラリというだけで、中身自体はCで書かれています。これらを毎回コンパイルするのも無駄なので、プログラムの断片をマシンコードにコンパイルしてつなぎ合わせることをナチュラルにやりたくて、コンピューターが発明されたかなり初期の段階からリンカはあり、使われています。

リンカは何をやるのか

リンカが何をやるのかを理解するためには、コンピューターのプログラムがどう動くかをある程度理解する必要があります。コンピュータープログラムは最終的にはメモリに読み込まれて、その部分をCPUが実行することによって実行が進みます。実行ファイルのイメージはけっこう簡単で、連続した領域がファイルに入っていて、それがそのまま連続してメモリにロードされるようになっています。メモリのどこにロードされるのかはファイルヘッダに書いてあるので、そのままロードする。指定された場所にジャンプして実行が始まるようになっています。

実行ファイルをメモリにロードするのはローダーの役目ですが、その実行ファイルを作るのはリンカの役目です。ではリンカは何をやるのかというと、似たようなことをやります。ただし、メモリにロードするわけではなく、ファイルからファイルにデータを移します。オブジェクトファイルにもコードとデータが分かれて入っているので、まとめて1つの領域にして実行ファイルを構成します。

（スライドを指して）この図はリンカが何をやるかを示しています。ただし、単につなげるだけではなく、ある程度データを編集する必要があります。それについて説明します。

例えば、左側のプログラムはCのコードですが、これをアセンブルすると右側のアセンブリになります。左側のソースコードの中でprintfは関数の宣言だけが書いてあって、定義が入っていないので、Cコンパイラはprintfという関数の存在と、その型はわかりますが、printfという関数が実際に何かはわかりません。ましてやprintfが実行時にどこにあるかはぜんぜんわかりません。

（スライドを指して）今のアセンブリを実際のマシンコードにすると、こうなります。objdumpというコマンドを使うとオブジェクトファイルの中身を逆アセンブリして出力できるのですが、ここでポイントになるのがオフセット14からのところです。これはコール命令で、ここでprintfを呼んでいますが、オフセットになっている00 00 00 00という部分が本来アドレスで入るべきなんです。

本当はコール命令の位置からprintfの位置までのオフセットがここに入っていないといけないのですが、Cコンパイラがこのコードを出力する時にはプログラムの全体像を知っているわけではないので、オフセットが埋められず、とりあえずゼロが埋まっています。その代わり、15のところにR_X86_64_PLT32と書いてありますが、これが別の領域に入っているメタ情報で、この15byte目をprintfのアドレスで修正してくれというデータが入っているので、これを見てそのプログラムをまずつなぎ合わせます。

そうすると、プログラムのそれぞれの関数がどこの位置にいくかがわかります。リロケーション情報（Fixup情報）を自分で修正できるので、それをバイナリパッチをします。メモリにロードすると実行可能なプログラムになるのでリロケーションを適用します。

ここまでがリンカの基本機能です。オブジェクトファイルを1つにまとめてリロケーションを適用すれば実行可能になるわけです。

メジャー機能その1　静的ライブラリ

それ以外の細かい機能は、広い意味においてはすべておまけです。ただ、おまけの機能といっても実際にリンカを作る際に知らないと始まらないので、少し説明します。

メジャーな機能が主に2つあります。1つ目は静的ライブラリ、アーカイブファイルと呼んでいるものです。これはzipファイルのように、ただの無圧縮のアーカイブファイルですが、オブジェクトファイルがたくさん入っています。

（スライドを指して）例えば、このarコマンド（ar t /usr/lib/〇〇というコマンド）を実際に叩いてみると、これはlibcの関数が全部入っているアーカイブファイルということがわかります。libcの関数がそれぞれ小分けされて、オブジェクトファイルとしてコンパイルされてまとめて入っています。小分けしないで大きな1つのオブジェクトファイルをドカンと置いて、「これがlibcです。これをリンクしてください」とやると、全部リンクされてしまうのでスペースの無駄です。

普通はlibcを使っていてもごく一部の関数しか使わないので、できるだけ小分けして必要なオブジェクトファイルだけを抜き出して、自動的にリンクされるような動作になっています。すごく原始的なシステムでは、libcの関数は、自分が使っているものと自分がコンパイルしたオブジェクトをリンカに同時に渡すとプログラムが出力されます。

ただ、自分が使っているlibcの関数を全部把握するのは非常に面倒ですし、libcの関数自体がlibcの別の関数を使っている（例えばprintfはvsprintfを使っている）という依存関係があるので、それを手でメンテするのは面倒くさい。なので、静的アーカイブライブラリについては自動的にファイルを抜いてくるという機能が実装されています。

なので、未定義シンボルがあると、自分が渡したオブジェクトファイルの中で解決できないもので、なおかつアーカイブファイルから抜き出して解決できるものがあれば、そのオブジェクトファイルを抜き出して使うことになります。それにより細かい管理をせず、全部リンクするのを避けることができます。この機能は50年くらい前の最初のUnixから存在していて、Unixで初めて発明されたものでもないと思うので、それよりさらに前からあります。

静的ライブラリのメリットは、仕組みが単純でわかりやすいこと。しかし、プログラムの断片がいろいろな実行ファイルに含まれるので面倒くさく、プログラムのコピーがそのまま埋め込まれるので、例えば、セキュリティをアップデートしたくなったらリンクし直さないといけないという面倒くささがあります。

メジャー機能その2　共有ライブラリ

もう1つのメジャーな機能として共有ライブラリがあります。ライブラリの一種ですが、ポイントは実行ファイルとは別に1つのファイルに分かれていて、別にメモリにロードされることです。実行ファイルがロードされるのと同時に、それが依存している共有ライブラリがまたメモリにロードされます。

メリットとしては、重複したコードをそれぞれ実行ファイルに埋め込まなくていい。しかも、物理的にたくさんのプロセスが動いていて、それが同じライブラリを使っている時は、メモリ上では物理的に同じになっています。マップされるアドレスが違うことはあっても物理的なページは共有できるので、メモリも多少節約できます。

デメリットとしては、複雑で、昔のWindowsのDLL地獄のように、シェアードライブラリ（共有ライブラリ）を更新するとプログラムの動作が変わって壊れることも起こり得ます。このようにそれぞれデメリットとメリットがあります。

共有ライブラリがどうリンクに関係してくるか。動的リロケーションが行われるので、リンカは動的リロケーションのための情報を作らないといけません。つまり、さっきのオブジェクトファイルをつなぎ合わせるのと同じ問題が、次はメモリ上で発生します。実行ファイルをロードして、共有ファイルをロードして、その間に関数の呼び出しがあればアドレスを修正しないと呼び出しできません。デフォルトではゼロが埋まったままなので、ローダーに対するリロケーションをリンカが出力して、動的にアドレスを解決する必要があります。

ただ、これも若干トリッキーで、ダイナミックリロケーションを行うべき場所はすごくたくさんあります。

例えばprintfは、libcを共有ライブラリとして使っていたらそのアドレスを全部直さないといけないことになります。そうするとあらゆるところを修正することになって、2つ問題が発生します。1つは、単純に修正するところが多いのでプログラムのロードが遅くなる。もう1つは、libcの共有ライブラリがロードされる位置がプロセスによって違う可能性があるので、基本的にリロケーションは別々のアドレスに対して行われることになります。そうすると、それぞれのプロセスのインスタンスごとにリロケーションした結果になるので、物理メモリを共有できずメモリが若干もったいないことになります。

リンカが行うこと

なので、リンカはもう少し凝ったことをやります。間接参照を導入することによって問題を解決しようとします。実際にはPLTやGOTといわれるテーブルを作って、リロケーションを行う場所を集約します。例えばprintfを呼びたければ一度printfに対応するPLTに飛んで、そこから実際のアドレスに飛びます。実行ファイルや共有ライブラリをモジュールといいますが、1つのモジュールの中の相対的な位置はメモリ上では常に固定なので、スライドすることはあっても相対的な位置は変わりません。CALL命令は相対的な位置を取るので、必ずPLTに飛ぶとしておけばどこにロードしてもPLTに飛びます。

PLTだけを変えるようにしておけばリロケーションが一発で済み、先ほどの問題が解決できる。PLTやGOTは必要に応じてリンカが作るので、これはスタティックリンカがやらなければいけない仕事です。

実際に何をやらなければいけないか。共有ライブラリを読んで、共有ライブラリで何が定義されているのかを知る。それから共有ライブラリを呼び出しているリロケーションや参照するリロケーションがあれば、そのためにPLTやGOTのエントリを作ってそこに飛ばす。PLTやGOTをどうダイナミックローダが修正してほしいかという情報も出力します。

ここまでの話をまとめると、リンカはオブジェクトファイルや与えられたファイルを全部読みます。それぞれ何が定義されていて何を必要としているかという情報を解決します。そのあとリロケーション情報を読んで、必要ならPLTやGOTを作ります。PLTやGOTのサイズが決まるとメモリ上でのレイアウトが完全に決められて、ファイル上でのレイアウトも決められるので、ファイルからファイルにデータをコピーできるようになり、リロケーションを適用すると実行ファイルが完成します。ここまでが、リンカが何をやるかという情報でした。

（次回へつづく）