Rustで書いたJVM

 (andreabergia.com)
3 ポイント 投稿者 GN⁺ 2023-07-22 | 1件のコメント | WhatsAppで共有
  • Rustを学ぶためのサイドプロジェクト rjvm は学習用のトイJVMだが、実際の .class と jar を読み込み、Javaバイトコードを実行する範囲まで実装している
  • サポートしていない機能は、スレッド、リフレクション、アノテーション、I/O、JITコンパイラ、文字列インターンだが、制御フロー、オブジェクト生成、メソッド呼び出し、例外、ガベージコレクションは含まれる
  • サンプルではOpenJDK 7の実際の rt.jar を使い、java.lang.StackTraceElement のようなクラスが実際のJDKからロードされる
  • コードは reader、vm、vm_cli の3つのRustクレートに分かれており、.class のパースからコールスタック、ネイティブメソッド、値とオブジェクトのモデリングまで扱う
  • 最後のマイルストーンは stop-the-world semispace copying collector で、目標達成後にプロジェクトは停止され、既知のバグを修正する計画もない

学習用Rust JVM rjvm

  • rjvm はRustを学ぶために作られたトイJava Virtual Machine
  • コードは GitHub で公開されている
  • 本格的なJVM実装というより学習目的の実装であり、次の機能はサポートしていない
    • スレッド
    • リフレクション
    • アノテーション
    • I/O
    • JITコンパイラ
    • 文字列インターン
  • ジェネリクスは当初未サポート一覧に入っていたが、実際には動作する

どこまで実装されたか

  • rjvm は単なるパーサにとどまらず、複数のJVM動作を直接実装している
    • if、for のような制御フロー
    • プリミティブ型とオブジェクト生成
    • 仮想メソッドと静的メソッドの呼び出し
    • 例外処理
    • ガベージコレクション
    • jar ファイルからのクラス解決
  • テストコードには Throwable、Exception、StackTraceElement を使う例が含まれる
  • 実際のI/Oがないため、System.out.println の代わりに tempPrint というネイティブメソッドを使用する
  • サンプルでは OpenJDK 7 の実際の rt.jar を使い、java.lang.StackTraceElement も実際のJDKから取得する

3つのRustクレート

  • プロジェクトは標準的なRustプロジェクトで、3つのクレートで構成される
    • reader: .class ファイルを読み、その内容をモデリングする型を含む
    • vm: コードを実行できる仮想マシンをライブラリ形式で提供する
    • vm_cli: java 実行ファイルに似たシンプルなコマンドラインランチャーを含む
  • reader クレートは別リポジトリに分離し、crates.io で公開する案が検討されている

.class ファイルのパース

  • Javaコードは javac でコンパイルされて .class ファイルになり、通常は zip 形式の .jar ファイルとして配布される
  • Javaコードを実行するには、まずコンパイラが生成したバイトコードを含む .class ファイルをロードする必要がある
  • クラスファイルには、実行と型解決に必要な情報が一緒に入っている
    • クラス名やソースファイル名などのメタデータ
    • スーパークラス名
    • 実装しているインターフェース
    • フィールドとフィールド型、アノテーション
    • メソッドディスクリプタ、throws 節、アノテーション、ジェネリクス情報
    • バイトコード、例外ハンドラテーブル、行番号テーブル
  • reader クレートはクラスファイルをパースし、クラスとその内容をモデリングする Rust struct を返す

メソッド実行とコールスタック

  • vm クレートの主要APIは Vm::invoke で、メソッド実行に使われる
  • 実行中の各メソッドは CallStack の中に1つの CallFrame を持つ
  • main 実行時、コールスタックは最初は空で、実行のために新しいフレームが作られる
  • 関数呼び出しごとに新しいフレームがコールスタックに追加され、メソッド実行が終わるとそのフレームは削除される
  • ほとんどのメソッドはJavaバイトコードで実装されるが、rjvm はネイティブメソッドもサポートする
    • ネイティブメソッドはJavaバイトコードではなく、JVM自体が直接実装するメソッド
    • System::currentTimeMillis、System::arraycopy、Throwable::fillInStackTrace などがある
    • rjvm では Rust関数 として実装される
  • JVMはスタックベースの仮想マシンであるため、バイトコード命令は主に値スタック上で動作する
  • 各コールフレームには、値スタックと、インデックスで識別されるローカル変数の集合が関連付けられる

値とオブジェクトのモデリング

  • Value は、ローカル変数、スタック要素、オブジェクトフィールドに格納できる値をモデリングする
  • Value はRustの enum として実装され、次の状態を含む
    • Uninitialized
    • Int(i32)
    • Long(i64)
    • Float(f32)
    • Double(f64)
    • Object(AbstractObject<'a>)
    • Null
  • Rustの enum のような直和型は、1つの値が複数の型のいずれかになり得ることを表現するのに適している
  • オブジェクト格納は当初、クラス参照とフィールド値を持つ Vec<Value> ベースの単純な Object 構造体から始まった
  • ガベージコレクタ実装後は、ポインタとキャストを多用する、より低レベルな実装に変わった
  • 現在の AbstractObject は実際のオブジェクトや配列をモデリングし、いくつかのヘッダワードとフィールド値を含むバイト配列ポインタである

バイトコード命令の実行

  • メソッド実行は、バイトコード命令を1つずつ処理する過程
  • JVM命令は200個を超え、バイトコードでは1バイトでエンコードされる
  • 多くの命令には引数が続き、一部の命令は可変長である
  • rjvm は Instruction 型でJavaバイトコード命令をモデリングする
  • メソッド実行時には、値スタックとローカル変数配列を維持し、次に実行する命令アドレスであるプログラムカウンタを0に初期化する
  • 通常、命令実行後にプログラムカウンタは次の命令へ移動するが、ジャンプ命令は別の位置へ移動させることができる
  • ジャンプ命令は if、for、while のようなフロー制御文の実装に使われる
  • 別のメソッドを呼び出す命令は別系統として存在する
    • どのメソッドを呼び出すかを決める方法には、仮想ルックアップや静的ルックアップなどがある
    • 対象メソッドを解決した後、新しいフレームをコールスタックに追加して実行を開始する
    • 戻り値が void でなければ、戻り値がスタックにpushされ、実行が再開される

例外処理

  • 例外は通常の制御フローを破り、メソッドから早期に返り、コールスタックに沿って伝播する可能性があるため、実装が複雑になる
  • 各 catch ブロックは、メソッドの例外テーブルの1項目に対応する
  • 例外テーブル項目には、ハンドラを見つけるために必要な情報が含まれる
    • 適用されるプログラムカウンタ範囲
    • catch ブロックの最初の命令アドレス
    • そのブロックが捕捉する例外クラス名
  • CallFrame::execute_instruction はRustの Result を使って命令実行結果を表現する
  • 命令実行結果は4つの状態に分かれる
    • 成功し、現在のメソッド実行を継続する
    • 成功し、return 命令であるため現在のメソッドが戻り値とともに終了する
    • 内部VMエラーにより実行に失敗する
    • Java例外が投げられて実行に失敗する
  • メソッド実行ループは命令をパースし、プログラムカウンタを次のアドレスへ移動した後に命令を実行する
  • 例外が発生すると、現在の命令位置に合う例外ハンドラを探す
    • ハンドラがなければ例外を呼び出し元へ伝播する
    • ハンドラがあれば例外オブジェクトをスタックに再度pushし、catch ハンドラ位置から実行を続ける
  • Rustの Result とパターンマッチングは、この動作をコード構造として表現するのに適している

ガベージコレクション

  • rjvm の最後の主要マイルストーンはガベージコレクタの実装
  • 選択したアルゴリズムは stop-the-world semispace copying collector
  • スレッドがないため、stop-the-world方式は自然に成立する
  • 実装は Cheney's algorithm のより単純な変種で、コードは gc.rs にある
  • この方式は利用可能なメモリを2つのsemispaceに分ける
    • 1つはアクティブ領域としてオブジェクト割り当てに使われる
    • もう1つは未使用領域として残る
    • アクティブ領域がいっぱいになると、生きているオブジェクトをもう一方のsemispaceへコピーする
    • すべてのオブジェクト参照を新しいコピーを指すように更新する
    • 2つのsemispaceの役割を入れ替える
  • この手順は blue-green deployment に似た方式としてたとえられる
  • アルゴリズムの長所と短所ははっきりしている
    • 最大メモリの半分を使えないため、メモリの無駄が大きい
    • ポインタを増加させる方式なので割り当てが非常に高速
    • オブジェクトをコピーして圧縮するため、メモリ断片化を扱う必要がない
    • オブジェクト圧縮はキャッシュライン活用の改善により性能を高める可能性がある
  • 実際のJava VMは、一般にG1やparallel GCのような、より洗練された世代別ガベージコレクタを使用する

プロジェクトの終了地点

  • rjvm を作る中でRustと仮想マシン実装について多くを学び、特に実際に動作するガベージコレクタの実装に満足している
  • ガベージコレクタは完成度が高いわけではないが、実際に動作する
  • 当初の目標を達成したため、プロジェクトはここで停止される
  • 既知のバグはあるが、それを直す計画はない
  • RustはJVM実装に使って楽しかった言語であり、今後の記事で rjvm の実装とJVMの動作方式をより詳しく扱う予定

関連記事

1件のコメント

 
GN⁺ 2023-07-22
Hacker Newsのコメント

  • ガベージコレクション実装の難しい部分は、すべての参照が適切にルートとして捕捉されていることを確認する点で、特に移動型コレクタではなおさらです。
    do_garbage_collection メソッドは unsafe としてマークされていますが[1]、呼び出し側が安全に呼ぶには何を保証すべきかの説明がありません。
    ヒープへのすべての参照がルートとして捕捉されることをどう保証しているのか気になりますし、これは些細な問題ではありません[2][3][4]。
    また、リポジトリをクローンして cargo test を実行してみたところ、すべてのテストが should be able to add entries to the classpath: InvalidEntry(".../vm/rt.jar") エラーで失敗しました: vm/tests/integration/real_code_tests.rs:15:10
    [1] https://github.com/andreabergia/rjvm/blob/be9c54066c64a82879...
    [2] https://manishearth.github.io/blog/2021/04/05/a-tour-of-safe...
    [3] https://without.boats/blog/shifgrethor-iii/
    [4] https://coredumped.dev/2022/04/11/implementing-a-safe-garbag...

    • この VM はネイティブのコールスタックの代わりに独自の仮想コールスタックを維持しているので、かなり直感的です。
      そのため、そのスタックを走査して引数やローカル変数を見つけ、ルートとして利用できます。
      この方式には性能コストがありますが、ガベージコレクションのトレースははるかに単純になり、コルーチンや continuation のような並行性・制御フローのプリミティブ機能も実装しやすくなります。
    • ガベージコレクタは基本的に厳密な帳簿管理のようなものなので比較的簡単ですが、並行ガベージコレクションを始めた瞬間に地獄のように難しくなります。

  • 良いプロジェクトですし、おめでとうございます。
    ただ、「サポートしていないもの: ジェネリクス」という部分は少し奇妙に感じます。
    JVM でジェネリクスをサポートするとは、どういう意味なのでしょうか。
    バイトコードレベルでは型消去のため全部 Object、つまり参照型だと単純に考えてよいのではありませんか？ それともクラス定義パーサの話でしょうか？ だとしても、基本構文以外にクラスファイルが有効かどうかを検査するロジックはないように見えます。

    • ジェネリクスについては reddit でも同じ話が出ていて、その通りです。
      実際にやるべきことは、クラス、メソッド、フィールドのジェネリクス情報を含む Signature 属性 を読む程度です (https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-4.ht...)。
      実際、今試してみたところ、下のコードも動きました :-)
      public class Generic { public static void main(String[] args) { List strings = new ArrayList(10); strings.add("hey"); strings.add("hackernews"); for (String s : strings) { tempPrint(s); } } private static native void tempPrint(String value); }
    • おそらく checkcast 命令のことかもしれません: https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.ht...
      たとえば final Main value = list.get(0); のようなコードを書くと生成されます。
      http://henrikeichenhardt.blogspot.com/2013/05/how-are-java-g...
    • おおむねその通りです。ジェネリクスはまれにリフレクションへ影響しますが、リフレクションもサポートされていませんし、全体としてはコンパイル時に最も近いクラスまたはインターフェースへ置き換えられます。
      一方で文字列インターンがないのは非常に奇妙です。実装も些細な部類ですし、これがないと JVM と呼ぶのは難しいでしょう。
      文字列が参照ベースで等しくなることは重要で、JLS の一部です。
      スレッドがない点も、この試み全体をおもちゃのプロジェクトレベルにしています。

  • 本当にすごい。1992年にJavaの作業に加わったときは名前が Oak で、私がいたグループはJavaでOS全体を書く方向を見ていた
    「機械語」、つまりネイティブメソッドとして必要最小限の部分だけを残せば、組み込みOSの攻撃対象領域を減らせるという発想だった
    もともとJavaはTVや家電のような環境で動かすことを目標にしていて、当時ネイティブメソッドはRustではなくCで実装していた
    Rustで作られたJVMは、この全体の流れにかなり強力な メモリ安全性 を加えてくれる

    • 個人的には、Androidがある程度それを達成したと思う
      OSロジックの多くをJavaやKotlinで書いている一方で、ネイティブコードのシステムサービスも多く混在しており、よく知られた、あるいは悪名高いBinder IPCで相互接続している
    • このアイデアは確かに何度か試みられている [0, 1]
      [0] - https://en.wikipedia.org/wiki/Singularity_(operating_system)
      [1] - https://en.wikipedia.org/wiki/Midori_(operating_system)
    • しばらくの間、一般ユーザー向けではなかったが JavaOS もあったはず: https://en.wikipedia.org/wiki/JavaOS
    • 兄弟コメントで挙がっているもの以外にも、SavageJE、microEJ、PTCとAonixのベアメタルJavaランタイム、SunSPOTのSquawkVMのようなものがある

  • Goで書かれた JVM 17 実装として https://jacobin.org/ も見る価値がある

    • JVM上で動作するScalaで実装されたJVMである https://github.com/lihaoyi/Metascala もある
    • プログラミングプロジェクト名としてはかなり興味深い
      Jacobinsは1790年代のフランス革命期の革命的政治クラブであり、https://jacobin.com にある雑誌の名前でもある

  • このシグネチャの ライフタイムパラメータ が原因で限界に突き当たったのか気になる
    fn execute_instruction(&mut self, vm: &mut Vm<'a>, call_stack: &mut CallStack<'a>, instruction: Instruction) -> Result, MethodCallFailed<'a>>
    Result の Err バリアントにライフタイムを追加し、そのライフタイムが不変である場合、ここでは vm と call_stack がそうであるように、通常は ? 演算子や早期リターンを使えなくなる[1]
    そうなるとエラー処理がより冗長で読みにくくなるが、実際にもそういう経験だったのか気になる
    [1] https://users.rust-lang.org/t/nll-and-early-return-not-allow...

  • 素晴らしい学習プロジェクトで、作者が楽しんでやっているのも良い
    VMをゼロから実装するのは本当に楽しく、以前そうした作業をしながら多くを学んだ
    ガベージコレクションを組み込んでみたいなら MMTk を見てみるのもよい (https://www.mmtk.io/)
    複数のVMに差し込めるよう設計された高品質な収集アルゴリズムがあり、Rustで書かれている

    • ちなみにMMTkは x86専用 だ
      お遊びプロジェクトに使おうとしたが、Macだったので諦めた

  • とてもよくできている
    VMを作るのはいつでも楽しく、Rustの型システムと組み合わせると興味深い学習体験だっただろう
    仕事を探しているなら、Twitter、Mastodon、あるいは会社のメールに連絡してもよい。ここのユーザーIDを見れば見つけられるはずだ

  • こういう素晴らしいプロジェクトを見ると圧倒される気持ちになる。
    どうやってRustを始めて、基礎をどの程度身につければこんなことに挑戦できるのか、原作者が説明してくれたらうれしい

    • まったく同じ気持ち。
      あまり脱線したくはないけれど、個人的に最近はこういう感情とかなり格闘している。
      プロのソフトウェア開発者としてほぼ10年働いてきたし、今の肩書きや実際に製品を出せる能力を見ても、自分が有能で偽物の開発者ではないことは分かっている。
      それなのに最近は開発者ブログを見ると、自分は十分に分かっていなくて「本物の」開発者ではないかのように圧倒される。
      頭の中に理想的な開発者像を作り上げて、その想像上の基準と自分を比べてしまうことで、こういう感情が生まれるのだと思う。
      深い知識を持ち、明快かつ簡潔に表現する人たちを尊敬する一方で、なぜ自分はああではないのかと考えてしまう。
      仕事が終わって家族の面倒を見たあとでは、何かをさらにやるだけのエネルギーがほとんど残っていないし、プログラミングがすべてではないことも分かっているけれど、もっと学んで成長したい気持ちはある。
      健全でも合理的でもないと分かってはいるけれど、最近はなかなか振り払えない感情だ
    • 正直、HNを開くたびに半分くらいは インポスター症候群 を感じる。
      以前にVMの経験が少しあって、数年前にはブログに短い記事シリーズを書いたこともある。
      前職では、顧客のかなり風変わりな問題を解決するためにJVMバイトコードを少しいじったこともあった。
      それから数年前に素晴らしい https://craftinginterpreters.com/ を読み、そこでアイデアを得た。
      でもこのプロジェクトは間違いなく大規模で複雑だった。
      かなり時間がかかったし、私の多くのサイドプロジェクトと同じように何度か放置もしたけれど、最終的に完成できてうれしい :-)
    • Rustの専門家でも原作者でもないけれど、別の技術である ソケット を例に話すことはできる。
      最近ソケットを深く掘り下げたのだが、2週間前まではマニュアルページやドキュメント、ブログ記事などをざっと読んで得た高レベルの理解しかなかった。
      ネットワーキングの基礎を理解したくて、できるだけたくさん読むことにしたところ、1週間後にはPythonとCでソケットコードを書けるくらいまで学べた。
      Pythonはかなり分かっているので、深く掘り下げたあとで sockets ライブラリを見ると、よりよく理解できた。
      技術Aを言語Xでもっとうまく扱いたいなら、技術Aについてできるだけ多く読んだり見たりして、言語Yで何かを作ってみることを勧める。
      そのあとで言語Xに戻れば、技術Aの周辺概念はすでにかなり身についている状態になっている
    • 小さく分割すればいい。
      単純な言語VMには、メモリ内でのオブジェクト表現、バイトコードインタプリタ、簡単なガベージコレクタ、ローダーがあるはずだ。
      バイトコードインタプリタは、スタック、そのスタック上で関数を表現する方法、各バイトコードを解釈してプログラムカウンタを進めるループとして捉えられる
    • 余暇にどれくらいコーディングするかが重要。平均すると週に何時間かということ。
      0時間なら、もちろん責めるような話ではないし、ほかに集中すべきことが多いのも分かるが、何年も平均して週10〜20時間サイドプロジェクトをやってきた人が印象的な成果物を出すのは不思議ではない

  • 似たようなプロジェクトを厚かましく宣伝すると: https://github.com/tenaf0/rust-jvm3

  • 386(486) ATクローン向けに無料のOSを作っている。単なる趣味で、gnuのように大規模でプロフェッショナルなものではない :-)

    • Rustでデモカーネルを書く no-stdチュートリアル がある: https://os.phil-opp.com
      osdev.org、sandpile.org、RBIL、freevgaも参考になる。
      最大の悩みの種はハードウェアサポートだ。
      信頼できるポートI/Oや文書化されていないハードウェアトリックのようなレシピが載っている、良いビンテージの紙の本もたくさんある。
      Intel® 64 and IA-32 Architectures Software Developer’s Manual Combined Volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4
      Microsoft MS-DOS Programmer's Reference, real-mode BIOS呼び出しも含む
      PC Interrupts
      Undocumented PC
      PC Intern
      Programmer's Guide To The EGA, VGA, And Super VGA Cards
      Graphics Programming Black Book Special Edition
      さらに、単一カーネル、マイクロカーネル、ハイブリッドの時代以降におけるOS開発の進展も試してみる価値がある。
      seL4のような capabilityベース の構造には、capabilityと優れたIPCを含め、性能とセキュリティの面で本質的な利点がいくつもある。
      POSIX互換レイヤも重要だ。スレッドやプロセスの概念がない組み込みOSでもPOSIXを実装できる。
      ハイパーバイザはIntel VT-[xd]があればずっと簡単に追加できるし、なければエミュレーションにフォールバックすればいい。変換型エミュレーションは性能が非常に高い。
      割り込みハンドラを一般化して高速化し、競合状態を避け、ロックフリーパターンを使いこなせるようになる必要がある。
      x87やMMXを含め、サポートしていない命令を再書き換えしたりトラップしたりすることも必要だ。
      純粋なマイクロカーネルが失敗した理由は、複数のリソースをトランザクション的に順序付けて管理する複雑さが増大したからだ。
      マイクロカーネルアーキテクチャには理論上、セキュリティ面と運用面で大きな利点があるが、純粋な形では広く定着しなかった