リンカーのリンク以外

• リンカーは（おそらく皆さんの想像以上に！）多くのことをしている面白いソフトウェア
• 現状多分世界一速いリンク速度を達成しているリンカーのメンテナの1人として，その一部を紹介します
• お断り
  • Linux向け実行可能ファイルフォーマット（ELF）を出力するリンカーに限った話をします
  • 汎用的なLinux向けリンカーに概ね共通する話をしますがリンカーによって詳細は異なる場合があります

• リンカーはコンパイラが作ったオブジェクトファイル（.o）を束ねて実行可能ファイルや共有ライブラリを作成するビルドの最終層
  • 再配置：コード・データ中のアドレス参照を最終的な配置先に合わせて書き換える
  • シンボル解決：オブジェクトファイル間でシンボルの定義と参照を突き合わせる
• 今回はこれら以外の話をします

• Rustを使うことを止めた開発者の45%がビルド時間の遅さを理由に挙げている（Rust compiler performance survey 2025）
• 涙ぐましい努力によって年々ビルド時間は減少しているがGoやZigなどと比べるとまだ開きがある印象

https://perf.rust-lang.org/dashboard.html より

• Rust製の高速なリンカー（ https://github.com/wild-linker/wild ）
  • 将来的にインクリメンタルリンクをサポートしてRustのビルドパフォーマンスを良くする狙い
  • インクリメンタルリンクをサポートする汎用Linux向けリンカーはない$^1$が，そうでなくても高速
  • 2025/11にgccからサポートされるパッチが入った$^2$
  • Rustコンパイラとの連携が進んでいる
• 現時点ではLinux向け（Mach-O，WebAssemblyサポートが進行中）
• x86_64, AArch64, 64bit RISC-V (rv64gc), LoongArch64をサポート
• 普段使いにも耐えるはず
  • 実際1年ほどデフォルトのリンカーとして使っている
  • Zedエディターの開発チームはローカルでの開発に使ってくれている
  • etc...

1: goldリンカーは（非決定的な）インクリメンタルリンクをサポートしていたがdeprecated
2: gcc 16から-fuse-ld=wildを渡すとgcc内部でwildが呼び出される

• 次ページから（本題ではないので少しだけ）リンク時間に関するベンチ結果をお見せします
  • ビルドパフォーマンスはハードウェア構成，対象ソフトウェア，ファイルシステム等の要因に大きく左右されます
  • より多くの（別の環境や，リンク時間 + メモリ消費量のメトリクス）結果を見たい場合はリポジトリを見てください
  • GNU ldは数十倍のスケールで遅くて縦軸が破壊されるので除外しています

• ここまでの紹介だと，リンカーは「再配置とシンボル解決（+α）をするだけ」に見える
• 確かにそれは主務だが，実際にはさらに多くのことをやっている
  • 様々な事項に気を使いながらリンカーがビルドを壊さないように実装するのは案外難しい（パフォーマンスを重視するならなおさら！）
• 以降それらの一部を紹介
  • 大雑把に"リンク時のバイナリ最適化"（not only LTO）と"ランタイムに対する支援"でカテゴリー分け
  • 基本的には「最終的なビルド成果物の全体像を見通せる立場だからできること」をしている

• リンカーはリンク中に，入力プログラムのコード片を暗黙に書き換えることがある
  • 例えば関数の呼び出し先が近い場合，間接呼び出しを直接ジャンプに置き換える
  • この操作のことをRelaxationと呼ぶ
• どのようなRelaxationが可能かはISA + psABIに基づく
  • 例： RISC-Vで関数呼び出しがauipc + jalr（= 普通のcall）で出力されていても，呼び出し先が近ければjalだけに置き換えられる
  • コードサイズを削減するRelaxationはRISC-V等に多いが，それ以外でもGOT-indirectアクセスを直接アクセスに変換するなどの実行時オーバーヘッド削減を見据えたRelaxationがある

_start:
  0: 00000097    auipc  ra, 0x0
  4: 000080e7    jalr   ra
  8: 05d00893    li     a7, 93
  c: 00000073    ecall

_start:
  4013d0: 00c000ef    jal   nearby_func
  4013d4: 05d00893    li    a7, 93
  4013d8: 00000073    ecall

• Relaxationはコード片が特定のパターンなら最適化できる「ミクロな最適化」
• 一方でマクロな最適化も可能 LTO (Link Time Optimization)
  • コンパイル時の中間表現（IR）をあえてリンカーに渡し，ファイルをまたいだインライン化等の最適化を行う
• リンカーの関与の仕方で大きく2通りある
  • プラグインAPI方式：リンカーがコンパイラのプラグインをdlopen(3)してコールバックを呼ぶ．リンカー自身はIRを解釈しない
  • 組み込み方式：LLVMバックエンドを直接リンカーに組み込んでIRを処理する（lldに存在する機能）
• ただしRustビルドにおいてはリンカーがLTOをすることはあまりない
  • LLVM backendの場合RustコンパイラがLTOの処理をするためリンカーはするべき仕事が残っていない
  • プラグインLTOをするフラグを立てたりCコード等と混ぜてビルドするなどの場合はリンカーが担当することがある
  • このためWildでは最近プラグインLTOに対応するようになった

• 特にC++などでは，テンプレート展開や継承を使うと中身が全く同じ関数がコンパイラによって複数作成されることがある
• リンカーはこれらを検出して統合する場合がある（Identical Code Folding）
  • ICFでは本来別だった関数が同一アドレスに配置されるため，関数ポインターのアドレス等価性が崩れうる（C/C++規格の保証に反する）
  • このためリンカーによっては「どこまでアグレッシブにICFするか」をオプションで選択できる
    （--icf=[all|safe|none]）
    • all：アドレスが参照されている関数も含めて統合する（バイナリは最も小さくなる）
    • safe：アドレスが参照されていない関数のみ統合する（アドレス等価性が問題にならない部分だけfold）
    • none: ICFしない

• コンパイルの過程では本質的に不要なセクションが作成される場合がある
  • オブジェクトファイルは他のオブジェクトファイルがどのシンボル（等）を使うか知らないから
• リンク時にはどのオブジェクトファイルがどのシンボル（等）を使うか把握できるので不要なセクションをそもそも出力しないようにできる（--gc-sections）
  • エントリーポイントや明示的に保持指定されたシンボルをルートとして，Mark & Sweepで参照の到達可能性解析を行う．到達不能なセクションは出力から除外される
  • WildはデフォルトでセクションGCを行う（他のリンカーは大体なぜかデフォルトではない）

• 実行ファイル中には多くの文字列リテラルが出現する
  • 異なるオブジェクトファイルに同一あるいは部分的に重複する文字列が含まれることが少なくない
• リンカーはマージ可能であることを示すフラグ（SHF_MERGE | SHF_STRINGS）が付いたセクションの文字列を重複排除する
  • 例えば"Hello, World!"と"World!"がある場合，後者は前者のsuffixなので後者の参照を前者の途中に向けることで重複排除（tail merging）
  • .rodataや.debug_strなどのセクションで特にサイズが減少する
• 大規模なバイナリでは文字列マージだけでバイナリサイズが数%減ることもある

• 共有ライブラリがロードされるとき，ローダー（ld-linux.so）はシンボル名から定義を検索する
  • この検索が高速だと実行時パフォーマンスが上がって嬉しい
• リンカーは出力ELFファイルにシンボルのハッシュテーブルを格納したセクションを作成する
  • SysV Hash（.hash）：ELFの古典的なハッシュテーブル．チェイン法ベースの素朴な実装
  • GNU Hash（.gnu.hash）：ブルームフィルターを併用した高速なハッシュテーブル．最近は大体こっちが主流
• ハッシュテーブルに格納する内容の決定や実際の構築・埋め込みはすべてリンカーの担当
  • ローダーはリンカーが作ったテーブルを読むだけでOK

• 共有ライブラリのAPIを更新したいが，古いバイナリとの互換性も維持したい場合がある
  • 例：glibcのmemcpyがglibc 2.14でx86_64向けに最適化されコピー方向が変わった結果，重複領域を渡していた（=未定義動作だが偶然動いていた）既存バイナリが壊れた
    → 旧バージョンをmemmove相当にし，新バイナリには最適化版をリンクすることで互換性を維持
• リンカーはバージョンスクリプトに従いシンボルにバージョンタグを付与する
  • 例：memcpy@GLIBC_2.2.5（旧）とmemcpy@@GLIBC_2.14（新・デフォルト）が同じライブラリ内に共存可能
  • @@がデフォルトバージョン，@が旧バージョン
• 新規リンクではデフォルトバージョンが選ばれ，古いバイナリは当時のバージョンタグを保持したまま動作するようにできる
  • バイナリがロードされる際にローダーが適切なバージョンのシンボルを見つけて使う

• プログラムのデバッグやクラッシュ時のバックトレース取得にはStack unwindingが必要
  • Stack unwinding：コールスタックを遡ってどの関数からどの順番で呼ばれたかを復元する処理
• リンカーはコンパイラが出力したunwind情報を集約して，正しい形式でELFに配置する
  • .eh_frame：DWARFベースのunwind情報．CIE/FDEレコードの連結・重複排除をリンカーが行う
    • .eh_frame_hdr：.eh_frameを二分探索するためのインデックステーブル．これもリンカーが生成する
  • SFrame：新しめの軽量フォーマット．DWARFより単純で高速にunwind可能
• これらのフォーマットはディストリビューションやツールチェインによって使われ方がバラバラ
  • リンカーはどの形式が要求されても正しく処理することが求められる

• --wrap=symbolオプションにより，リンカーはシンボル解決時にシンボルを差し替える
  • symbolへの参照を__wrap_symbolに，__real_symbolへの参照を元のsymbolに書き換える
  • 例えば--wrap=mallocとすると，プログラム中のmalloc呼び出しは__wrap_mallocに向き，__wrap_malloc内で__real_mallocを呼ぶと本物のmallocが呼ばれる
• ユースケース
  • プロファイリング：malloc/freeをラップしてメモリアロケーションを計測
  • ログトレース：printf等をラップしてタイムスタンプを付加
  • テスト：特定の関数をモックに差し替え
• ソースコードを変更せずにリンク時に関数の挙動を差し替えられる

• 現代の汎用リンカーは単なる再配置やシンボル解決以上に多くのことをやっている
  • 今回挙げたものは一部
• ビルド成果物の全体像を見通せる立場だからこそできることが多くある
• リンカーの実装に興味があればwild-linker/wildを見てみてください