About 記事一覧 日記一覧 このサイトについて Japanese

実行プログラム作成基盤をスクラッチで書いた

     5760 words   12 minutes 

この記事は 言語実装 Advent Calendar 2019 の8日目です.

言語処理系の理論,自作言語の実装については既に他の方が記事を出してくださると思うので,
私は 実行可能なプログラム に変換する部分を主軸に置きながら自作言語のお話をさせていただければと思います.

実装自体はこちらに置いてあります.

  • screenName: Drumato
  • よく使う言語: Rust/Go
  • エディタ: Neovim
  • 年齢: 19
  • 職業: 学生
  • 興味のあること: コンパイラ/アセンブラ/リンカ/OS/全ての低レイヤに関するなにか

技術の勉強を 2018年5月から始めました.
言語処理系に興味を持ったのは2019年の2月からですね.

一般的に(自作言語をサポートする)言語処理系を実装しようと思った時,以下のような方法が考えられます.

  • 自作言語 -> LLVM IR のコンパイラを実装する
    • この場合,吐き出したLLVM IR( *.ll )を clang 等に入力する必要がある
    • lli 等,簡単に実行結果をチェックできるツールも
  • 自作言語 -> assembly のコンパイラを実装する
    • 同様に吐かれたアセンブリコードを別のツールに入力することで初めて実行結果が得られる
    • GNU binutils 等を用いる事が多い
  • インタプリタ を実装する
    • プログラムを生成する必要がないため,外部ツールを用いる必要が無くなる
    • JIT機能を追加して実行速度を早める方法もある
    • 最近の主流はタダのTree-walkedなインタプリタより VM型 かも?
  • etc

特に最近よく見るのは一番上の方法ですね.
LLVM を用いることでかなり高速なプログラムを生成することができるし,
各言語にLLVMバインディングが存在する為,それを用いることで比較的カジュアルに実装できます.

しかし,私は フルスクラッチ( from scratch )病 にかかっています.
なので,

  • LLVMは凄い,実際に使ってもみたい
  • でも 外部ライブラリはできる限り使いたくない
  • LLVM自体も 超巨大なコンパイラ実装ライブラリ ということができる(?)
  • フロントエンド,バックエンド 全て自分で作って こそ勉強になるんじゃないか!

という事で,

完全にフルスクラッチな実行プログラム生成基盤(コンパイラドライバ) の実装にチャレンジすることにしました.
具体的なアーキテクチャ(これは初期,今年の5月頃に考えていたもので現在とは異なります)を以下に示します.

/images/sechack365/figure1.jpg

つまりまとめると,実行可能プログラムを生成したくなった理由は以下の通りになります.

  • コンパイラの勉強を始める -> 外部ライブラリは使いたくない!
  • 低レイヤーが好きだ -> アセンブリ吐くところで終わりたくない!
    • なのでアセンブラ作ってオブジェクトファイル吐いたりリンカ作ったりしました
  • 自作言語が実行可能な機械語に変換できる -> 単純にお気持ちが満たされる!

ここまでで読者の皆さんと意識を共有できたと思うので,
ここから先は実装の流れ,そして今できる事を話していきたいと思います.

時期 やったこと
2019年5月 Golangで実装開始
2019年5月下旬 Goで書いたコード全削除 & Rustで再実装始め
2019年8月18日 再度ソースコード全削除
2019年9月 x64アセンブラ実装に着手
2019年9月10日 GNU ldでリンク可能なオブジェクトファイルの生成
2019年9月下旬 スタティックリンカ実装に着手
2019年9月21日 実行可能バイナリの生成に成功
2019年9月26日 コンパイラバックエンド部全削除
2019年10月15日 コンパイラフロントエンド部全削除

こうしてみると コード削除しすぎだろ という感じがしますね.
コード削除の主な理由は

  • 単純にコードが汚い
  • モジュールの分け方がうまくなかった,やり直したくなった
  • IRを適当なものから3番地コードに変換

等の理由があります.
8/18にソースコードを全削除してから 9/26に(外部ツールを用いない)実行可能バイナリを生成するまで
約一ヶ月間 かかっています.
この間はもう日常生活のうち自由時間を全てこの実装に費やしていましたね.

初めて自作バイナリが実行できた時の様子がこちらになります.

発狂していますが,私のTwitterは大体こんな感じです.
本記事の執筆時点( 2019/11/24 )では,以下のような規模のプログラムになっています.

/images/sechack365/figure2.jpg

全てRustで実装されています.
実はこのプロジェクトを書く過程でRustを勉強したので,
Rust自体の勉強時間はほぼ0 なんですよね.
コンパイルエラーが優しい言語 はこういう勉強方法ができるので好きです.

コンパイラ,アセンブラ,リンカの各コンポーネントに分けて,
それぞれができることを解説していきます.

  • 式
    • 二項演算
      • 加算
      • 減算
      • 乗算
      • 除算
      • 剰余算
      • ==,!=
      • <,<=,>,>=
      • <<,>>
    • 変数式 x
    • 括弧 (1+2)*3
    • アドレス式 &x
    • 負の数 -x
    • 逆参照 *x
    • 関数呼び出し function(arg1,arg2)
    • インデックス ary[10]
    • メンバ式 Struct.member
    • 配列リテラル [10,20,30+40]
    • 構造体リテラル Name{foo:30,bar:50}
  • 文
    • if if (condition) statement
    • if-else if (condition) statement else statement
    • return return expression
    • assign mutable_ident = expression
    • compound-statement { statement * n }
    • 構造体定義 struct Name { foo : i64, bar : i64 }
    • while的なやつ condloop(condition) statement
    • let let ident_name : type_name = expression
      • ミュータブルなやつ let mut ident_name : type_name = expression
    • 引数定義 func add(x:i64, y:i64)
    • ラベル :fin
    • goto文 goto :fin
    • type-alias type type_name = target_type
  • 組み込み型
    • i64 … 符号付き64bit整数
    • Pointer<T> …スタック上に置かれるポインタ
    • Array<T,N> … 固定長 ( N 個 ) の配列,これもスタック上
  • ユーザ定義型 … type-alias したものとか, 構造体とか
  • その他
    • --dump-cfg … 制御フローグラフをDOT言語に変換して吐き出す
    • --dump-tac … 3番地コードを出力
    • --emit-llvm … LLVM IRを吐くパス(鋭意製作中)

実際にデモをいくつか見せます.

まず,これは自作言語で書いた 6重ポインタ (?) です.

func main(){
  let a : i64 = 30
  let b : Pointer<i64> = &a
  let c : Pointer<Pointer<i64>> = &b
  let d : Pointer<Pointer<Pointer<i64>>> = &c
  let e : Pointer<Pointer<Pointer<Pointer<i64>>>> = &d
  let f : Pointer<Pointer<Pointer<Pointer<Pointer<i64>>>>> = &e
  return *****f
}

めちゃくちゃ冗長なんですが, type-alias 実装しているのでまぁ良しとしましょう.

$ depth sample.dep

すると, a.out が吐き出されます.

/images/sechack365/figure3.jpg

こんな感じです.
構造体のサンプルも見てみましょう.
ついでに --dump-cfg も使ってみます.

struct Depth {
  foo: i64
  bar: i64
}

func main() {
  let depth : Depth = Depth{ foo: 30, bar: 60 }
  let mut x : i64 = 0
  if (depth.foo == 30){
    x = depth.foo
  } else {
    x = depth.bar
  }
  return x
}

/images/sechack365/figure4.jpg

吐かれた cfg.dot に対しGraphvizを用いて,画像に変換しています.

/images/sechack365/figure5.jpg

メンバ名がいまのところスタックオフセットになってしまっているんですが,
ちゃんと制御フローグラフは構築出来ています.

次にアセンブラのできる事を紹介するんですが,
言語処理系の勉強をしている人の中にはアセンブラがどんな役割を持つソフトウェアなのかしらない人も多いと思うので,
ここでは簡単に解説しようと思います.

アセンブラとはとてもシンプルに言えば,
アセンブリ言語をオブジェクトファイルに変換するソフトウェア のことです.

一般的には アセンブリ言語を機械語に翻訳するソフトウェア と言われていて,それは至極正しいんですが,
実際に実装してみると アセンブラの本質ってオブジェクトファイルにまとめる部分では と感じる事が多かったです.

コンパイラと同じように字句解析,構文解析をします.
但し,コンパイラの構文解析における AST のような複雑な構造よりはシンプルですけどね.

そして命令列に対応する機械語を生成します.
これによって 通常 .text に書き込む機械語列が得られるというわけです.

次に, リンカが必要とする情報 をバイナリに埋め込む作業に入ります.
これはあくまで私の場合ですが, GNU ld がリンク可能な最小のオブジェクトファイルには

  • シンボルテーブル .symtab ( リンカがmainシンボルを見つける為 )
    • つまりシンボル文字列テーブル .strtab も必要
  • .text (当たり前)
  • .shstrtab (リンカはセクションの判断にきちんとこの名前を用いている)
  • 勿論 セクションヘッダテーブル も必要
    • 各ヘッダに適切な値を設定する必要もある.

が必要でした.
これらの情報を過不足なく,そして正確に設定することで初めてリンク可能なオブジェクトファイルとなります.
逆に言うと, リンカが実行プログラムを作成する上で 最低限必要な情報 ということです.
それぞれの解説をここで加えているととてつもない分量になってしまうので,

こちらで是非電子版を購入してください.私が3章を担当しています( 宣伝を入れるな )
3章ではELFの基礎的な知識について解説しています.

気を取り直して,現在Depthアセンブラができることです.

  • 生成セクション
    • NULLセクション
    • .text
    • .strtab
    • .symtab
    • .rela.text
    • .shstrtab
  • relative offset jump(めちゃくちゃ難しかった)
    • e9 c1 ff ff ff jmp 400031 <main+0x19> みたいなやつ.
    • アドレス変位の部分に現在の機械語からの相対オフセットが指定されている
  • 対応命令
    • movzx
    • ret
    • pop
    • push
    • cqo
    • add
    • sub
    • idiv
    • imul
    • cmp
    • setle
    • syscall
    • setl
    • setg
    • setge
    • sete
    • setne
    • call
    • lea
    • neg
    • mov
    • jmp
    • sal
    • sar
    • jz

コンパイラが吐くアセンブリコードには全て対応しています.
メモリアドレッシング もできるし,システムコールの発行も出来ます.

これもデモ画像を見てみましょう.

/images/sechack365/figure6.jpg

/images/sechack365/figure7.jpg

うまくアセンブル出来ている事がわかります.
ELFの仕様に則ったオブジェクトファイルを生成しているので,
ちゃんとreadelfしてもエラーが起きず解析できます.

/images/sechack365/figure8.jpg

リンカもアセンブラ同様,簡潔に解説します.
アセンブラの出力によって オブジェクトファイル が得られますが,
これは 再配置可能 な状態と言って, 実際にメモリ上のどこにロードされるか という情報を持っていません.
そこで リンカ というソフトウェアが

  • このシンボルはここにおいて
  • この文字列はここにおいて, 読み取り専用にして
  • ファイル上のここからここは プログラム実行に必要ないから要らないフラグをつけて

みたいに,
オブジェクトファイルを全解析 します.

この作業によって初めて 実行可能なプログラム , つまり メモリにロードし,CPUが実行可能なプログラム に変化します.
リンカがやることは沢山あるのですが,これについて説明しておくとこれまた一冊本が出来てしまうので,
実際に出来上がった本を購入していただければと思います.
日本語で解説されている 最も詳しい リンカ実装本です.
非常にニッチかつ内容も簡単ではないですが, システムプログラミングの基礎 と言ってもいいと思います.
まだ読んでない人は絶対に読むべきです.

自作リンカは 約230行 で実装されているので,できる事はめちゃくちゃ少ないです.

  • 静的リンク
    • 動的リンクは出来ません.
  • 単一オブジェクトファイル
    • 複数ファイルには対応していません
  • 再配置
    • 再配置テーブルを見て,アドレス解決されていないシンボルを見つけます
    • 再配置テーブルの情報から,参照されている機械語上のオフセットにアドレスを書き込みます
    • とてもシンプル
  • エントリポイントの指定
    • _start シンボルを見つけ,割り当てたアドレスを elf64_ehdr.e_entry に書き込みます

これぐらいかな,できる事はとてもシンプルです.
しかしこれだけですが, 現状Depth言語で記述した動くプログラムの全て をリンク可能です.
つまり,アセンブラが吐いた全てのオブジェクトファイルは正常にリンクできます.

これは, リンカというソフトウェアの特性 にも絡んできます.
リンカの実装フェーズは,大まかに3つに分かれていると個人的に思っています.

    1. スタティックリンクできるようにする(今のDepthリンカ)
    • 動的リンクにすると結構難しくなる
    1. ライブラリリンクできるようになる(ここにめちゃくちゃ大きな壁がある)
    • ファイル間のシンボル解決,アーカイブフォーマットの解析,セクション位置の調整…
    • 対応しなければならないセクション数も爆発する
    1. LTO( Link Time Optimization ) の実装

逆に言うと,細かな改良が 最低限の機能に限定すれば あまり必要ないということです.
1番が実装できているので,2番が必要になるまでは現在のリンカで対応できます.

上記コンポーネントを全て利用すると,以下のような事ができます.

/images/sechack365/figure9.jpg

普通シェルで ./binary 等とした時,
ユーザプロセスから execve(2) システムコールが呼ばれ,
内部で様々な処理を実行した後カーネル組み込みのELFローダが起動,
プログラムを実行するという流れになっています.

私は ここも自作したい という気持ちから,
更にコンパイラドライバ内にELFローダも実装しました.
実装全体はこちらに.
下ではロードのメイン処理を載せておきます.

pub fn load(elf_file: ELF) -> i32 {
    let (program, page) = Self::setup_page_with_using_mmap();
    let binary = elf_file.to_vec();
    if let Some(unwrapped_phdrs) = elf_file.phdrs {
        let offset = unwrapped_phdrs[0].p_offset as usize;
        let segment_size = unwrapped_phdrs[0].p_filesz as usize;

        /* get segment from binary */
        let load_segment = binary[offset..offset + segment_size].to_vec();
        let pointer_to_segment = load_segment.as_ptr();

        unsafe {
            program.copy_from_nonoverlapping(pointer_to_segment, segment_size as usize);
            let f: fn() -> i32 = ::std::mem::transmute(page);
            f()
        }
    } else {
        eprintln!("not found program header table");
        0
    }
}
  • 実行可能なメモリ領域を mmap(2)
  • 関数ポインタにキャスト,実行
  • ローダ側でキャッチして,それをプロセスの終了ステータスとする

みたいなことをやっています.
リンカが吐き出す ET_EXEC ファイルのセグメント数が1つだからこそ出来る簡易実装になっています.

実際に動作している様子です.
Linuxカーネル組み込みのローダを使わずに，
(といってもDepthコンパイラドライバのロードには使っているんですが)
add.dep の実行結果を受け取っていることがわかります.

ここからは実装時に困ったことをつらつら書いていきます.

詳しくはこちらスライドを見ていただきたいのですが,
要は ELF独特の仕様に苦しめられた ということです.
自分で色々値を変えてみたりして検証する必要がありました.

坂井さんの本はリンカ実装の上でとても役に立ったんですが,
あれはあくまでも GNU binutils (GNU as)の吐いたオブジェクトファイルをリンクできるプログラムなんですよね.
つまり 自作アセンブラ には対応していないんですよ( 当たり前 ).

ということは,
オブジェクトファイルの生成から間違っているかもしれない という可能性を捨てきれないまま,
リンカを作ったりする必要があるわけですね…
これは辛い,非常に大変だった.

どうやら世の中で コンパイラ･アセンブラ･リンカ を作っている人はかなり少数みたいで,
ドキュメントはほぼありませんでした. というか全く無い.

一番大変だったのは 自作バイナリのデバッグ ですね.
リンカがある程度出来上がったときに実行すると BusError で落ちる事がよくあったんですね.
これ,カーネルが仮想メモリに(アラインメントエラーとかで)うまくマッピング出来なかったりすると起こるんですが
どこを調べても解決方法は載っていないので大変でした.

gdbを使ってもデバッグ情報なんか無いですからね!
後実行してもELFヘッダを機械語列と見てしまっていたり,もう大変でした.

ここでは自作言語の実装の中でもかなりニッチな
自作バイナリの生成 についてお話しました.
ブラックボックスでやりたくないんだ! という方や 低レイヤが好きなんだ! という方は
是非実装に挑戦してみてくださいね.

Updated on 2019-12-08
 compiler, assembler, linker, rust
Back | Home