リンクとロード

リンクは、オブジェクトファイル内のシンボル、セクション、リロケーションを結合して実行可能イメージまたは共有オブジェクトを構成します。ロードは、そのイメージをプロセスのアドレス空間に配置し、実行に必要な動的な準備を完了させます。これらは互いに連携しますが、異なるフェーズです。

本文の具体的な形式と数式は、Linux ELF および x86-64 System V ABI を例に挙げています。他のプラットフォームのオブジェクト形式、呼び出し規約、ダイナミックリンク戦略については、それぞれの仕様を参照してください。

オブジェクトファイルには機械語以外に何があるか

セクションはリンク時の視点での組織単位です。プログラムヘッダはロード時の視点でのセグメントを記述します。実行時には、PT_LOAD などのプログラムヘッダに基づいてマッピングされ、セクション名ごとに個別に mmap されるわけではありません。.bss にはメタデータが存在しますが、それが表す各ゼロバイトをファイルに保存する必要はありません。

シンボル解決とレイアウト：誰を参照するかを先に決める

1つのオブジェクトファイルが helper を定義し、別のオブジェクトファイルが helper を参照しているとします。リンカは、バインディング、可視性、バージョン、リンクルールに基づいて、その参照がどの定義に対応するかを決定し、関連する内容をレイアウトしてリロケーションを適用します。

同名でも必ずしも衝突するわけではありません。ローカルシンボルには独自のスコープがあり、弱シンボルと強シンボルには異なるルールがあり、ダイナミックシンボルは可視性と検索範囲の影響も受けます。逆に、ダイナミックシンボルの解決を「最初にロードされたライブラリが常に優先される」と単純化することもできません。

リロケーション：各タイプには正確な数式がある

S をターゲットシンボルのアドレス、A を addend、P をリロケーションフィールドの位置とする。x86-64 における R_X86_64_PC32 は S+A−P を使用し、R_X86_64_64 は S+A を使用します。異なるタイプでは、フィールドの幅とオーバーフローチェックも規定されています。AMD64 ABI リロケーションテーブル

典型的な call rel32 のエンコーディングでは、CPU が相対的に参照するのは次の命令ですが、ABI の数式ではフィールド位置 P が使用され、一般的な addend −4 が両者の差を既に処理しています。もし数式が S−(P+4)+A と書かれ、かつ A が −4 である場合、4 が重複して減算されてしまいます。

外部関数呼び出しでは R_X86_64_PLT32 が使用される可能性があり、そのターゲットは PLT エントリに関連し、リンカによって直接呼び出しに緩和される場合があります。すべてのコンパイラが外部呼び出しで PC32 を明示的に表示することを要求することはできません。数式を理解した後は、実際のリロケーションタイプを確認すべきです。

4バイト書き込む前に、符号付き範囲を確認する

rel32 オフセットは符号付き32ビット数です。ターゲットが呼び出し点より前にある場合、オフセットは負になり、リトルエンディアンフィールドへの書き込みには2の補数が使用されます。ターゲットが遠すぎる場合、下位32ビットに単純に切り捨てることはできず、そうすると CPU は別のアドレスにジャンプしてしまいます。以下では、すでに直接ターゲットが確定している PC32 の計算のみをモデル化し、シンボル検索や PLT の選択はシミュレートしません。

def pc32(symbol, addend, place):
    displacement = symbol + addend - place
    if not -(1 << 31) <= displacement < (1 << 31):
        raise OverflowError("PC32 relocation out of range")
    return displacement.to_bytes(4, "little", signed=True)


assert pc32(0x2000, -4, 0x1001) == bytes.fromhex("fb 0f 00 00")
backward = pc32(0x1000, -4, 0x2001)
assert 0x2005 + int.from_bytes(backward, "little", signed=True) == 0x1000
for displacement in (-(1 << 31), (1 << 31) - 1):
    assert int.from_bytes(pc32(displacement, 0, 0), "little", signed=True) == displacement
for displacement in (-(1 << 31) - 1, 1 << 31):
    try:
        pc32(displacement, 0, 0)
    except OverflowError:
        pass
    else:
        raise AssertionError("truncated relocation accepted")

S と P を共通に平行移動してもオフセットは変化しないため、モジュール内部のいくつかの PC 相対参照がロードベースアドレスに合わせて再修正を必要としない理由が説明できます。しかし、モジュール外で定義されたシンボル、絶対アドレスフィールド、TLS などはそれぞれ独自のルールを持っています。1つの内部相対呼び出しから「PIC にはリロケーションがない」と一般化することはできません。

P、次の命令、そして −4、誰がすでに距離を補正したのか？

まず4バイトフィールド P をマーキングし、次に次の命令 P+4 をマーキングすると、addend の役割は明確になります。以下では、ターゲットを呼び出し点の前に配置することも、モジュール全体を平行移動することも、意図的に4を重複して減算することもできます。オフセットが範囲外の場合、切り捨てられた4バイトは生成されません。「ファイルに書き込める数字」であっても、CPU が正しいアドレスに到達できるとは限らないからです。

$$d=S+A-P,A=-4,(P+4)+d=S$$

最小限のオブジェクトファイル実験

独立した実験ディレクトリに2つのファイルを作成します。

/* caller.c */
extern int twice(int);
int main(void) { return twice(21) == 42 ? 0 : 1; }

/* twice.c */
int twice(int x) { return x * 2; }

cc -O0 -c caller.c -o caller.o
cc -O0 -c twice.c -o twice.o
readelf -sW caller.o
readelf -rW caller.o
objdump -dr caller.o
cc caller.o twice.o -o demo
./demo

まず未定義の twice シンボルを探し、次にそれに対応するリロケーションを確認し、最後にリンク後のプログラムがどのように実行されるかを観察します。具体的なオフセット、命令、PIE のデフォルト値はツールチェーンによって異なりますが、実験の重点はシンボル参照と修正フィールドを対応させることです。

静的ライブラリ：ルールに従ってオブジェクトメンバを抽出する

.a はオブジェクトファイルのアーカイブです。伝統的な Unix リンカは、アーカイブを処理する際に未解決の参照に基づいてメンバを抽出するため、コマンドラインの順序が重要になる場合があります。参照元を提供する定義を持つ静的ライブラリの前に配置するのが一般的な書き方です。

循環依存は、ライブラリグループ化による再スキャンなどのメカニズムで処理できます。GNU ld や他のリンカは対応するオプションをサポートしていますが、具体的なスキャン戦略は異なります。LLD はアーカイブ内の遅延シンボルを保存し、後続の参照時に抽出します。すべてのリンカを完全に同一の左から右への単一スキャンとして記述することはできません。

リンカの GC は、セクションやリロケーションなどの参照関係に基づいて、ルートから到達可能な内容を保持します。ルートにはエクスポートされたシンボルやリンクスクリプトの KEEP も含まれます。これは単に _start から逆アセンブルして call 命令を追跡するものではありません。関数やデータごとにセクションを分割することで、細粒度の回収が可能になりますが、すべての入力が自然に分割されているわけではありません。

1つのメンバがリンクに含まれても、その中のすべての関数が残るとは限らない

引き続き前述の caller.c を使用し、twice.c を拡張して2つの関数にします。twice は main から呼び出されますが、unused_helper は参照されません。GNU ld.bfd を使用して以下の実験を行い、リンカを固定して、アーカイブスキャン戦略をすべてのツールのルールと誤認しないようにします。

/* twice.c：前のバージョンを置き換え */
int twice(int x) { return x * 2; }
int unused_helper(void) { return 99; }

gcc -O0 -ffunction-sections -fdata-sections -c twice.c -o twice.o
ar rcs libtwice.a twice.o
gcc -fuse-ld=bfd caller.o ./libtwice.a -o with-unused
gcc -fuse-ld=bfd caller.o ./libtwice.a -Wl,--gc-sections -o trimmed
nm with-unused
nm trimmed
./with-unused
./trimmed

最初のリンクでは、caller.o による twice への参照により twice.o 全体が抽出されるため、2つの関数がすべて入力集合に含まれます。2回目のリンクでも同じメンバが抽出されますが、セクション回収により .text.unused_helper が保持グラフに含まれていないことが判明し、削除できます。両方のプログラムは 0 を返しますが、nm において unused_helper は未回収バージョンにのみ表示されるはずです。ここでは O0 を使用し LTO を無効にすることで、フロントエンドのインライン化や削除効果を説明に混入させないようにしています。

もし libtwice.a を caller.o の前に配置した場合、GNU ld.bfd はその時点で twice の未解決参照を持っていないため、メンバを抽出しない可能性があります。その結果、未定義参照のエラーになります。順序を元に戻せば解決します。この順序の問題を解決するために無条件で --whole-archive を使用すると入力範囲が拡大し、さらにそれ自体がすべてのセクションを後続の GC から守ることを保証するものではありません。GNU ld アーカイブおよびセクション回収オプション

1つの .o を抽出したのに、なぜ1つの関数のみ残るのか？

「リンク入力に含まれたこと」と「最終的に生き残ったこと」を異なる集合として描くことで、ライブラリの順序とセクション回収の両方を同時に説明できます。伝統的なアーカイブスキャン時に twice の未解決参照がまだ存在しない場合、メンバを抽出しない可能性があります。強制抽出した後でも、unused がある独立したセクションは GC 中に削除される可能性があります。ここでは GNU ld.bfd の教育用の境界を固定し、結果を LLD などの異なる実装にそのまま適用しないようにしています。

GOT と PLT：間接アクセスと解決のタイミングを分けて考える

GOT はアドレススロットを提供し、PLT は呼び出しスタブを提供します。これらは一部の位置独立コードやダイナミック呼び出しパスの一部です。古典的な遅延関数バインディングでは、最初の呼び出しはターゲットを検索して対応するスロットを更新し、後続の呼び出しはすでに保存されたアドレスを利用します。

即時バインディングは、関連する解決をロードフェーズに前倒しします。例えば、Linux ダイナミックリンカは LD_BIND_NOW を通じて制御できます。しかし、解決が前倒しされたからといって、元の PLT 呼び出し命令が間接オーバーヘッドのない直接呼び出しに自動的に変更されるわけではありません。PLT を使用するかどうか、緩和できるかどうか、GOT を通じて呼び出すかどうかは、コンパイルとリンクの選択に依存します。Linux ld.so

ダイナミックシンボルのインターポージションも、検索スコープ、バインディング、可視性の影響を受けます。これは実装の置換やプリロードに柔軟性をもたらす一方で、インライン化やローカルバインディングの仮定を制限する可能性があります。すべての malloc 呼び出しが必ず同じパスを通ると断言することはできません。

ロードと dlopen

dlopen はプロセス実行中に共有オブジェクトをロードし、dlsym はシンボルを検索し、dlclose はロード参照を減少させます。実際のプラグインインターフェースでは、ABI、所有権、スレッド、アンロード条件を定義し、エラーをチェックする必要があります。関数ポインタやスレッドがまだライブラリコードを実行している間に、無秩序にアンロードすることはできません。dlopen マニュアル

ダイナミックロードによる既存ライブラリの使用と、JIT によるマシンコードの公開は異なります。JIT はメモリ上でオブジェクト、リロケーション、実行可能権限を処理でき、「.o を書き、.so にリンク、dlopen を実行する」というファイルフローを統一して通る必要はありません。JIT コンパイル を参照してください。

LTO：最適化がコンパイルユニット間の情報を見られるようにする

通常の独立したコンパイルでは、最適化器が見ることができる関数本体が制限されます。LTO は IR や関連する中間情報を保持し、リンクフェーズでシンボル解決結果と組み合わせてモジュール間の分析と最適化を実行し、その後マシンコードを生成してリンクを続行します。LTO がなくても、リンカはリロケーション、セクション回収、その他のリンク最適化を実行するため、「単に連結するだけ」と呼ぶことはできません。

Full LTO と ThinLTO の組織方法は異なります。ThinLTO はモジュールのサマリーを組み合わせてグローバル分析と選択的な関数インポートを実行し、その後モジュールバックエンドを並列実行し、キャッシュを使用することもできます。Clang は -flto=thin などの設定でこのモードを明示的に選択します。これは、gold や LLD の呼び出しにおける天然のデフォルトの LTO 方式ではありません。Clang ThinLTO ドキュメント

インライン化の可否はコストモデルや可視性などの制約によって決定され、「ホットパスの呼び出しのみをインポートする」ことに限りません。LTO がすべてのダイナミックプラグインや外部定義を把握しているわけでもなく、所谓的「全プログラム境界」はリンクとシンボルの仮定と組み合わせて考える必要があります。パフォーマンスの向上、メモリ使用量、リンク所要時間は実際のプロジェクトで測定すべきであり、一律の向上率を提供するものではありません。

問題特定のためのクイックリファレンス

参考文献

• AMD64 System V ABI。
• ld.so、dlopen。
• Clang ThinLTO。

Keywords: ELF, シンボル解決, リロケーション, PC32, PLT32, アーカイブ, GOT, PLT, 遅延バインディング, dlopen, LTO, ThinLTO