リンカーを自作した

2022-03-13
#compiler #binary

自作Cコンパイラではすべて自分で実装してみるというつもりでCコンパイラ、プリプロセッサ、アセンブラを作ってきたが、ついに欠けている最後の要素だったリンカーを作った。

今まではアセンブラですべてのアセンブリコードを受け取って、マシンコード生成とラベルのアドレスを解決して直接ELF形式の実行ファイルを出力していた。 それでほとんど問題はないんだけど、リンカーが使えるとオブジェクトファイルを生成しておくことで分割コンパイルできるようになりコンパイル時間が短縮できたり、 他のコンパイラの出力結果も使用できるようになるという利点がある。

またリンカーがなくてすべてのコードを一緒にアセンブルしていることにより、ソースファイル中の static 変数や関数でも実際には漏れてしまっているため、プログラム全体で衝突しない名前を使う必要があるという欠点があった。

アセンブラからは実行ファイルだけじゃなくオブジェクトファイルの出力もできるようにはしていたので、リンカーを用意できれば一通り揃うことになる。

リンカーの仕事

リンカーは複数のオブジェクトファイルを受け取ってアドレスを計算して実行ファイルを出力するのが主な仕事となる。 各オブジェクトファイルにはシンボルや再配置情報などが含まれているので、それらを組み合わせて処理することになる。

オブジェクトファイルの構造

ELF64フォーマットのオブジェクトファイルの大雑把に解説：

  • データがセクションに別れていて、それぞれ実行するマシンコードやデータなどが格納されれている
  • シンボルは「このセクションのこのオフセット位置」というのを示していて、外部から参照する場合にどこかわかるようになっている
  • 再配置テーブルは「セクション内のこの部分は、シンボルこれこれからこのように計算する」という情報が入っている

もう少し詳しい説明は「ELFのオブジェクトファイル形式を生成する」を見るといいかもしれない。

リンクの処理

実際のリンクの処理の流れは、

  1. すべてのオブジェクトファイルを読み込む
  2. セクションに含まれるデータの種類によって分類する
  3. 各セクションのアドレスを計算する（それによりシンボルのアドレスも決定される）
  4. 再配置情報でデータを書き換える
  5. 実行ファイル出力

となる。

以降に重要なデータの構造と扱い方を示す。

セクション

セクションの構造体は以下の通り：

typedef struct {
  Elf64_Word    sh_name;                /* Section name (string tbl index) */
  Elf64_Word    sh_type;                /* Section type */
  Elf64_Xword   sh_flags;               /* Section flags */
  Elf64_Addr    sh_addr;                /* Section virtual addr at execution */
  Elf64_Off     sh_offset;              /* Section file offset */
  Elf64_Xword   sh_size;                /* Section size in bytes */
  Elf64_Word    sh_link;                /* Link to another section */
  Elf64_Word    sh_info;                /* Additional section information */
  Elf64_Xword   sh_addralign;           /* Section alignment */
  Elf64_Xword   sh_entsize;             /* Entry size if section holds table */
} Elf64_Shdr;
  • sh_type がセクションタイプ
    • SHT_PROGBITS (=1) がマシンコードやデータを表す
      • sh_flags のビットで役割を判別：
      • SHF_EXECINSTR (=1<<2) で実行可能（マシンコード）
      • SHF_WRITE (=1<<0) で書き込み可
    • SHT_NOBITS (=8) だと初期値のない変数（.bss）領域

シンボル

typedef struct {
  Elf64_Word      st_name;
  unsigned char   st_info;
  unsigned char   st_other;
  Elf64_Half      st_shndx;
  Elf64_Addr      st_value;
  Elf64_Xword     st_size;
} Elf64_Sym;
  • st_info: 下位4ビットが type、上位4ビットが bind となっている
    • bind が STB_LOCAL (=0) で同じオブジェクトファイル内の別セクション、 STB_GLOBAL (=1) で別オブジェクトファイルのシンボル参照

再配置情報

typedef struct {
  Elf64_Addr      r_offset;
  Elf64_Xword     r_info;
  Elf64_Sxword    r_addend;
} Elf64_Rela;
  • r_offset: セクション内のオフセット位置
  • r_addend: 計算結果への加算値
  • r_info: 下位32ビットがタイプ、上位32ビットがシンボル
    • 再配置タイプ（主要なもののみ）：
      • R_X86_64_64 (=1): 絶対アドレス（64ビット）
      • R_X86_64_PC32 (=2): PC からの相対（32ビット）
      • R_X86_64_PLT32 (=4): PC からの相対（32ビット）

再配置情報は対応するセクションごとに出力されるので、相対アドレスを計算するための PC は、再配置のセクションの先頭アドレス + r_offset となり、実際の値は シンボルのアドレス - PC + r_addend となる （STB_LOCAL （＝同オブジェクトファイル別セクション）の場合は セクションの先頭アドレス - PC + r_addend）。

再配置情報は Elf64_Rela 以外にも Elf64_Rel という addend がないものあるようだが自作のアセンブラからは出力されないのでひとまず保留。 再配置タイプも他にいろいろあるが、必要なものだけ実装。

ELFの実行形式

実行形式は以前から出力していたので特に新しいことはないが、「ELF64でQuine」あたりを見るとちょっとわかるかもしれない。

締め

ソースは ld.c 、 今のところソースファイル一つで済むくらいの規模なので、案外単純だった。

静的リンクしかサポートしてないしライブラリファイル.aを扱ってないので今後の課題。

参考

  • mold での並列処理の説明
  • リンカーみたく古くから作られて使われているソフトに今になって革新を起こせるなんてすごいですね

関連リンク

関連記事

新着記事