どうやってテキストエディタをインストールしているか

河田旺氏(以下、河田):Preferred Networksで働いている河田です。ふだんはコンパイラやランタイムのエンジニアをやっています。今日は「sold: A linker for shared objects」というタイトルで発表します。

突然ですが、みなさんはどうやってテキストエディタをインストールしていますか。OSにプリインストールされたものを使ったり、aptなどで入れたり、中には自分でビルドしている人もいるかと思います。僕は、最新バージョンじゃないと動かないプラグインがあったので、自分でビルドして使っています。

最新のNeovimを自分でビルドして使うためにはどうするか

僕は最新のNeovimを使っているのですが、これを常にビルドするのはけっこう大変です。特に、新しくマシンが増えるたびにビルド環境を整えるのが面倒です。ビルドがない場合は、依存しているライブラリをビルドする必要があります。

そこで、1度ビルドしたものを他のマシンでコピーして使い回したい、という動機がありました。しかし、ビルドしたものは、共有ライブラリ、shared object、Linuxだと.soファイルへの依存があって、コピーできないことがほとんどです。

(スライドを示して)この下の黒いところに、ビルドしたNeovimを他のマシンにコピーするとどうなるかを示しています。この場合、libnsl.so.3というバイナリがなくて、shared objectがないため、実行に失敗するのがわかります。

そこで最初に出てきそうなのが、静的リンクにすればよいのでは? という話です。静的リンクにすると、共有ライブラリへの依存は消えます。

しかし、静的リンクはしばしばサポートされていない問題があります。例えば、Neovimを静的リンクでできるようにするPR(Pull Request)は、ビルドの設定が複雑になりすぎるという理由で、マージされていなかったりします。

そこで、動的にリンクされたバイナリに、あとから共有ライブラリをリンクすればよいのでは? という発想があります。

「sold」リンカとは何か

では、本題に入ります。「sold」はアプリケーションに動的にリンクされたライブラリを、あとから静的にリンクし直すためのリンカです。社内の浜地さんが、2020年1月に作り始めました。

soldは入力として、動的にシュリンクされたバイナリを取って、依存する動的リンクライブラリをリンクしたバイナリとして出力します。(スライドを示して)この黒いコマンド例だと、Neovimを入力に取って、nvim.soldoutというバイナリを出力します。これだと、Neovimはlibnsl.so.3というバイナリからshared objectに依存しているのですが、この出力はlibnsl.so.3がリンクされていて、このnsl.so.3なしで動けます。

もう1つ、簡単で小さな具体例を見せます。ここでlddというコマンドが登場します。lddは、バイナリや、shared objectに依存する動的リンクライブラリを列挙するためのコマンドです。

この例でldd a.outは、最初はfuga.soとhoge.soに依存しています。これをsoldでa.outをリンクすると、a.out.soldoutというバイナリができます。

これをあらためてlddで確認すると、依存関係がなくなっていて、それらはfugaやlib.hogeで、fuga -i soldだったりlib.hoge.soldなしで動くようになっているのがわかります。

「sold」リンカの仕組み

それでは、ここからsoldがどのように動いているかを説明します。soldの説明をする前に、Linuxの実行可能バイナリや動的リンクライブラリのフォーマットについて、少し説明します。

現在のLinuxでは、Executable Linkable Format、ELFというバイナリのフォーマットが主に使われています。ELFファイルは、いくつかのセグメントで構成されます。管理データが入っているセグメントやPT_LOADセグメントなどです。プログラムをコンパイルした時に生成される命令列、atやcall命令などは、PT_LOADセグメントに入っています。

ELFを使っているシステムでは、ELFのシンボルと再配置情報を使って、外部の動的リンクライブラリ中の関数を呼び出します。

(スライドを示して)この例では、Neovimの中でfugaという関数を呼び出します。対応するシンボルと再配置情報を使ってlibnsl.so.3の中のfugaを見つけて呼び出します。

では、ここからはsoldが、どのように動的リンクライブラリを静的リンクにするかを説明します。まず、必要なPT_LOADをコピーします。(スライドを示して)この例だと、Neovimの下のところに1つ、libnsl.so.3からコピーしてきたPT_LOADが増えています。

次に、コピーした関数を呼び出すように再配置情報を書き換えます。この例だと、libnsl.so.3の中のfugaを呼び出していたものを、Neovimの中のfugaを呼び出すように書き換えます。最後に、不要なシンボル情報を消します。

これで外部の動的リンク、ライブラリ中の関数を呼び出していたものが、静的リンクした関数の呼び出しに変わりました。

再配置情報の書き換え(R_X86_64_64の場合)

ここからは、先ほど説明を省略した再配置情報の書き換えをR_X86_64_64の場合に絞って説明します。再配置情報にはいろいろ種類があるのですが、その中の1種類です。

そもそもR_X86_64_64は、指定したアドレスにシンボルのアドレスを埋めるための再配置情報です。この例だと、Neovimの0xdeadbeefにhogeのアドレスを埋めるのが目的です。

(スライドを示しながら)このために必要な再配置情報がこんな感じです。タイプがR_X86_64_64で、シンボル名がhoge、書き換え先のOffsetが0xdeadbeefです。

ダイナミックローダがこの再配置情報を処理すると、この0xdeadbeefのところにabcdabcdが埋まります。実行時は、この右側の状態で実行されます。

soldでこのR_X86_64_64をどのように処理するかを見てみましょう。soldは、シンボルが定義されていたらR_X86_64_RELATIVEに書き換えるという処理をします。

先ほどと同じ例を考えます。最初はR_X86_64_64のままなのですが、soldはこれをR_X86_64_RELATIVEに書き換えます。そして、書き換え先のOffsetは、0xdeadbeefのままで変わらず、addendを0xdeadbeef-0xabcdabcdの再配置情報にします。このaddendは、0xdeadbeefの再配置情報の補正値のようなものです。

セグメント、PT_GNU_RELROとPT_TLSをどのように処理するか

先ほどELFファイルには、管理データやPT_LOAD以外にもセグメントがあると言いました。それらのセグメントの中にも、soldで扱えるようにするためにおもしろい工夫があるもの、必要なものがあるので紹介します。

例えばPT_GNU_RELROは、特定のメモリ空間を保護するためのセグメントです。そしてPT_TLSは、CやC++のthread local変数を扱うためのもので、PT_GNU_EH_FRAMEは例外を扱うためのセグメントです。(スライドを示して)今回は上の2つ、PT_GNU_RELROとPT_TLSをどのように処理するかを、簡潔に説明します。

そもそもPT_GNU_RELEOは、再配置後に特定のメモリ空間を書き込み不可にするセグメントです。PT_GNU_RELROは、addrとsizeを保持していて、これを見たローダはmprotectでaddrからsizeバイトをPROT_EXECに発行します。これはGlobal Offset Tableに対して使われることが多いです。

厄介なのは、1つのELFで有効なのは1つのPT_GNU_RELROである、という性質です。これはローダの実装やld-linux.soの実装を読むと、1つしか見ないことがわかります。

しかしsoldでリンクしたバイナリには、複数のGlobal Offset Tableがあります。さらに厄介なことに、1つのPT_GNU_RELROでは、サイズをすごく大きくして、すべてのGlobal Offset Tableを保護することができません。これはGlobal Offset Tableの間に「書き込み可」が必須のメモリ範囲があるためです。

そこでsoldでは、link-time時にコード生成をして、この問題に対処しています。soldは該当するメモリ範囲を一つひとつmprotectするバイナリを、リンク時に生成します。このバイナリはアーキテクチャごとに違います。

このバイナリを生成して適当なPT_LOADに突っ込んで、そのsent addrをInit_arrayに入れておきます。そうすると起動時に呼ばれます。Init_arrayはshared objectのロード時に呼ばれる関数ポインタ群で、C++のコンストラクタなどが入っています。

(スライドを示して)下に、実際のコード例として、soldで使っているコードを書いておきました。最初のdeadbeefがリンク時に書き換えるアドレスで、次のaabbccがリンク時に書き換えるサイズです。最後に、リンク時に書き換えないのですが、この0x0aはSYS_mprotectのシステムコールの番号です。

特殊な変数Thread Local Storageをどう扱うのか

次に、Thread Local Storageをどう扱うか、またその工夫について話をします。そもそもThread Local Strageというのは、(スライドを示して)CやC++でこのような構文で使える特殊な変数です。

通常、スレッド間ではアドレス空間は共有で、スレッド固有の変数を作れないのですが、Thread Local Strageを使うと作れます。Thread Local Strageは、ローダによってスレッドごとにメモリ割り当てられます。

Thread Local Strageへのアクセスは、モジュールとオフセットという2つの整数を使って行われます。(スライドを示して)この黒いところに示したコード例はlibcから引っ張ってきたものですが、これがTLSにアクセスするために、内部的に呼び出される関数です。

soldでTSL変数を処理する場合は、モジュールとオフセットの両方を書き換える必要があります。これは、2種類の再配置情報の両方を書き換えることを意味します。

この2種類の再配置情報は、R_X86_64_DTPMOD64がモジュール番号で、R_X86_64DTPOFF64がオフセットに対応する再配置情報です。しかし厄介なことに、両方必要なのにモジュール番号にだけ再配置情報が入っているケースがあります。これは、Thread local dynamic modelというThread Local Strageへのアクセス方法です。この場合だとDTPMOD64のほうにしかありません。

しかもより厄介なことに、これにも対処できないと、Thread Local変数へのアクセスの際に不正なアクセスが発生して、アプリがSEGVで落ちます。

解決策とデモ

soldのこの問題への解決策は、オフセットの位置を無理やり推測することです。(スライドを示して)TLSへのアクセスに使われる構造体はこのようになっていて、オフセットの位置はモジュール番号の8byte先で固定されています。

このため、R_X86_64_DTPMOD64のみでオフセットの位置を推測でき、TLSを扱えるように変更できました。では、デモを見せます。

普通のNeovimを起動します。きちんとエディタとして使えることがわかります。これをsoldでリンクすると、nvim.soldoutというバイナリができます。ここではLD_DEBUG=unusedという環境変数を付けて起動します。これはあとで説明します。soldで作成したバイナリも、エディタとして使えることがわかります。

最後に、依存する動的リンクライブラリが実際に減っていることを確認します。元のNeovimは10個のshared objectに依存していました。soldoutしたものは6個ほどに減っています。

セッションのまとめ

では、soldの現状です。soldは依存する動的リンクライブラリをあとからリンクするリンカでした。lsやfind、tree、grepなどでリンク可能で、動作も確認しています。Neovimもリンク可能です。ただ、LD_DEBUG=unusedという環境変数がないとセグメンテーションで落ちることがわかっています。

さらにlibcやlibm、libpthreadがリンクできない問題があります。これらは重要で、かつ歴史があって複雑です。発表を終わります。ありがとうございました。

質疑応答

司会者:ありがとうございます。コメントがすごく大量にきています。しかも有識者らしい人が多くいます。「この手法では、SnapとかFlatpackというアプリケーションをアイソレーションするような、全部統合するものと違って、daemonやユーティリティが要らないのがいい」とのことです。

Snap、Flatpackを置いておいても、StatfireやErmine、プロプラ(プロプライエタリソフトウェア)など類似なものはあるけど、両者とも単純に古いですね。

河田:そうですね。この2つは試していて、ELFにはバージョンの概念がありますが、そのあたりの扱いが甘くて落ちたりします。それから例外なども扱いが甘かった気がします。

司会者:ほかの感想では「実際にやろうと思うと、細かいことがいっぱいあるんですね」や「soldoutは実行時の動的リンク操作をAOTしているとみなすと、コンテナの起動を高速化する文脈で活きてきそう」といただいています。あちらだとI/Oなどの外部世界とつなぐ直前でメモリダンプしていて、これは私には知見がないですが、アイデアも展開されていますよね?

河田:そうですね。ELD実行時の動的リンクについてはそのとおりです。ld-linux.soがやっていることを肩代わりして、そのあとの状態を、新しいExecutableに代わるフォーマットに書き込んでいる、という見方ができます。

司会者:そのほかの感想は、「動的依存ライブラリをまとめるのはおもしろい。grepと言語系では割とありそうだけれども、あとからスタティックリンクできる発想は、以前できないかと調べたものだが、実現していたんだ」などがあります。

河田:そうですね。

司会者:ほかの質問では、「ASLRやvDSOはうまいことやったのか、気になる」とあります。

河田:ASLRに対応するのには悩まされました。(スライドを示して)ここで再配置情報書き換える時に、RELATIVEを使っているのはASLRが関係しています。ASLRなしだとアドレスが固定で決まるので、固定したアドレスを埋め込んでいいはずですが、ASLRがあるため、アドレスは実行時に毎回変わり得るので、リロケーションを埋めて、あとはASLRで変わったアドレスに対して対応・対処する工夫があります。これはオリジナルのhamaji-sanの工夫で、この人は天才、頭がいいですね。

司会者:あとは「プログラム実行中にdlopenでライブラリを読み込んだりする場合は埋め込めないんですか」という質問です。

河田:それは不可能ですね。

司会者:原理上、そうですよね。あとは別の質問で「LDライブラリパスをローカルディレクトリに設定するだけでは駄目なのだろうか」という素朴な疑問です。

河田:そうですね。これは.soファイルをリモートにコピーしたうえで、依存する.soファイルを全部リモートにコピーして、LDライブラリパスをローカルディレクトリに設定すればいいのではないかという話だと思うのですが、これは社内的な事情で不可です。

司会者:なるほど。質問は以上です。時間もちょうどいい感じになったので、こちらで終わります。ありがとうございました。

河田:ありがとうございました。失礼します。