仮想マシンの作り方 (2022)

 (jmeiners.com)
3 ポイント 投稿者 GN⁺ 2024-12-28 | 1件のコメント | WhatsAppで共有
  • コンピュータ内部の動作とプログラミング言語の実行方式を理解するため、LC-3教育用アーキテクチャ上でアセンブリプログラムを実行する約250行のCベースVMを自分で実装する
  • 実装対象は、65,536個の16ビットメモリ位置、10個のレジスタ、16個のopcode、条件フラグ、trap routine、メモリマップドレジスタを備えた小さなコンピュータモデルである
  • 実行ループは、PCが指す命令を読み取ってインクリメントした後、opcodeを解釈してADD、LDI、BR、JMP、TRAPのような命令を実行するfetch-decode-execute構造で動作する
  • プログラムのロードでは、オブジェクトファイルの最初の16ビットoriginを読み取ってメモリに配置し、LC-3のbig-endian形式を、ほとんどの現代的なコンピュータで使われるlittle-endian形式に合わせてバイトスワップする
  • キーボード入力とコンソール出力はtrap routineとKBSR/KBDRメモリマップドレジスタで処理し、Unix/macOSとWindowsでそれぞれ異なるターミナル入力バッファリングコードが必要になる

チュートリアルの目的と前提

  • LC-3仮想マシンを自分で実装し、アセンブリ言語プログラムを実行する過程をたどる
  • 最終コードはCで約250行で、Unix用lc3.cとWindows用lc3-win.cが提供される
  • 必要な前提知識は、基本的なCまたはC++の読解と2進数演算である
  • 全コードはGitHub repoにあり、チュートリアル自体はliterate program形式なので、コードブロックをつなぎ合わせて最終ソースを作る

仮想マシンがすること

  • VMは、CPUと一部のハードウェア構成要素のように動作するプログラムである
    • 算術演算を行う
    • メモリを読み書きする
    • I/Oデバイスと相互作用する
    • 独自の機械語を理解してプログラムを実行する
  • VMの目的に応じて、実際のハードウェアを忠実に再現することもできるし、ソフトウェア開発を容易にするために新しい仮想アーキテクチャを提供することもできる
  • JVMは標準実行プラットフォームを提供するVMの代表例であり、JVMが実装されたデバイスではJava、Kotlin、Clojureのプログラムを修正なしで実行できる
  • 分離実行もVMの重要な用途である
    • ガベージコレクションでは、VMが実行中のプログラムの外側からスタックとメモリ参照を観察できる
    • Ethereum smart contractは、ファイルシステム、ネットワーク、ディスクなどにアクセスできないVMの中で実行される

LC-3アーキテクチャの構成

  • 実装対象は、大学のコンピュータアーキテクチャとアセンブリ教育で使われるLC-3である
  • LC-3メモリは65,536個の位置を持ち、各位置に16ビット値を保存する
    • 全体の記憶容量は128KBである
    • C実装ではuint16_t memory[MEMORY_MAX]配列で表現する
  • レジスタは合計10個である
    • R0〜R7: 汎用レジスタ8個
    • PC: 次に実行する命令のメモリアドレス
    • COND: 直前の計算結果の条件フラグ
  • LC-3命令はすべて16ビットで、左側4ビットがopcodeである
    • opcodeは16個定義される
    • OP_BR、OP_ADD、OP_LD、OP_ST、OP_JSR、OP_AND、OP_LDR、OP_STR、OP_RTI、OP_NOT、OP_LDI、OP_STI、OP_JMP、OP_RES、OP_LEA、OP_TRAPが含まれる
  • 条件フラグは、直前の計算結果の符号を表す
    • FL_POS: 正
    • FL_ZRO: 0
    • FL_NEG: 負

アセンブリと言語機械語

  • LC-3 VMが実際に実行するのは、人が読むアセンブリではなく16ビット機械語命令の配列である
  • アセンブラは、テキストで書かれたLC-3アセンブリを16ビットのバイナリ命令へ変換する
  • Hello Worldの例は次の流れになる
    • .ORIG x3000: プログラムをロードするメモリアドレスを指定
    • LEA R0, HELLO_STR: 文字列アドレスをR0にロード
    • PUTS: R0が指す文字列を出力
    • HALT: プログラムを停止
    • .STRINGZ "Hello World!": 文字列データをプログラム内に保存
  • .ORIG、.STRINGZはCPU命令ではなくアセンブラディレクティブである
  • 条件とループは、BRn LOOPのようなgotoに近い分岐命令で実装される

実行ループの中核手順

  • VMの実行では同じ手順を繰り返す
    • PCレジスタのアドレスから命令を読む
    • PCをインクリメントする
    • 命令の上位4ビットからopcodeを得る
    • opcodeに対応する実装コードを実行する
    • 再び次の命令を読む
  • 基本の開始アドレスは0x3000である
  • 一部の命令はPCを直接変更して実行フローをジャンプさせる
    • 分岐命令とジャンプ命令のおかげで、単にPCを増やす構造でもループや条件実行が可能になる
  • mainループはswitch (op)でopcodeごとの処理コードを呼び出す
    • OP_ADD、OP_AND、OP_NOT、OP_BR、OP_JMP、OP_JSR、OP_LD、OP_LDI、OP_LDR、OP_LEA、OP_ST、OP_STI、OP_STR、OP_TRAPを処理する
    • OP_RES、OP_RTIは未使用のopcodeとしてabort()で処理できる

命令の実装方式

  • ADDは2つの値を足して宛先レジスタに保存し、条件フラグを更新する
  • ADDには2つのモードがある
    • レジスタモード: 2番目のオペランドを別のレジスタから読む
    • 即値モード: 2番目のオペランドを命令下位5ビットのimm5から読む
  • imm5のように16ビットより短い値は、sign extensionを経て16ビット値へ拡張しなければならない
    • 正数は0で埋める
    • 負数は1で埋めて元の値を保持する
  • レジスタに値を書き込む命令は、update_flagsでR_CONDを更新する
    • 値が0ならFL_ZRO
    • 最上位ビットが1ならFL_NEG
    • それ以外はFL_POS
  • LDIは“load indirect”命令である
    • 命令のPCoffset9をsign extensionする
    • 現在のPCに加えてメモリアドレスを得る
    • その位置に保存された値を再びアドレスとして使い、最終データを読む
    • 読み取った値を宛先レジスタに保存し、条件フラグを更新する

主な命令セット

  • 算術とビット演算
    • ADD: 加算
    • AND: ビットAND
    • NOT: ビットNOT
  • 制御フロー
    • BR: 条件フラグと命令の条件ビットを比較してPCを移動する
    • JMP: 指定レジスタの値をPCに設定する
    • RET: 仕様上は別キーワードだがJMPの特殊ケースである
    • JSR、JSRR: 現在のPCをR7に保存し、サブルーチン位置へジャンプする
  • メモリ読み取り
    • LD: PC基準のoffsetアドレスから読む
    • LDI: 間接アドレスをさらに1回たどって読む
    • LDR: base registerとoffsetで計算したアドレスから読む
    • LEA: 有効アドレス自体をレジスタに保存する
  • メモリ書き込み
    • ST: PC基準のoffsetアドレスに保存する
    • STI: 間接アドレスをたどって保存する
    • STR: base registerとoffsetで計算したアドレスに保存する

Trap routineとI/O

  • LC-3は、共通処理とI/Oデバイスへのアクセスのためにtrap routineを提供する
  • trap routineはLC-3のオペレーティングシステム、あるいはAPIのように見なせる
  • trap codeは次のように定義される
    • TRAP_GETC = 0x20: キーボードから1文字入力、ターミナルにはechoしない
    • TRAP_OUT = 0x21: 1文字出力
    • TRAP_PUTS = 0x22: word stringを出力
    • TRAP_IN = 0x23: 文字入力後にターミナルへecho
    • TRAP_PUTSP = 0x24: byte stringを出力
    • TRAP_HALT = 0x25: プログラム停止
  • 公式LC-3シミュレータではtrap routineはアセンブリで書かれているが、このVMではC関数として実装する
  • PUTSはR0に保存されたアドレスから始めて、x0000に出会うまで文字を出力する
    • LC-3文字列はC文字列のように1バイト単位ではなく、1メモリ位置あたり1文字を保存する
    • 各メモリ位置は16ビットなので、Cで出力する際はcharに変換して出力する
  • HALT trapは"HALT"を出力し、実行フラグを0に変更してVMループを終了する

プログラムイメージのロード

  • LC-3アセンブリプログラムを機械語に変換すると、命令とデータの配列を含むファイルが作られる
  • オブジェクトファイルの最初の16ビットは、プログラムをメモリのどこに置くかを示すoriginである
  • ローダはoriginを先に読み、その後のデータをoriginアドレスからメモリへコピーする
  • LC-3プログラムはbig-endian形式である
    • ほとんどの現代的なコンピュータはlittle-endianなので、ロードした各uint16_tにswap16を適用する
    • 古いPPC Macのようなbig-endianコンピュータではスワップしてはいけない
  • read_imageはファイルをバイナリモードで開き、read_image_fileを呼び出してからファイルを閉じる

メモリマップドレジスタ

  • 通常のレジスタテーブルではアクセスしない特殊レジスタは、特定のメモリアドレスにマップされる
  • LC-3で実装すべきメモリマップドレジスタは2つである
    • MR_KBSR = 0xFE00: keyboard status register
    • MR_KBDR = 0xFE02: keyboard data register
  • KBSRはキーが押されたかどうかを示し、KBDRはどのキーが押されたかを保存する
  • GETCは入力が来るまで実行をブロックするが、KBSRとKBDRはデバイス状態をpollingすることで、入力待ちの間もプログラムが応答し続けられるようにする
  • メモリ読み取りは配列を直接読むのではなくmem_readを経由する
    • アドレスがMR_KBSRならcheck_key()でキーボード状態を確認する
    • キーがあればKBSRの最上位ビットを立て、KBDRにgetchar()の値を保存する
    • キーがなければKBSRを0に設定する

プラットフォーム別のターミナル処理

  • キーボード入力とターミナル動作を正しく処理するには、プラットフォームごとの入力バッファリング設定が必要である
  • Linux/macOS/UNIX実装ではtermios、selectなどを使う
    • canonical modeとechoを無効化する
    • selectで入力可能かどうかを確認する
  • Windows実装ではGetStdHandle、GetConsoleMode、SetConsoleMode、_kbhitなどを使う
    • echoとline inputを調整する
    • WaitForSingleObjectと_kbhitでキー入力を確認する
  • プログラム開始時にdisable_input_buffering()を呼び、終了時にrestore_input_buffering()を呼ぶ
  • SIGINTを受け取ったら、ターミナル設定を復元し、改行を出力して終了する

VMの実行とデバッグ

  • VMのビルド例は次の通り
gcc lc3.c -o lc3-vm
  • 実行するには、アセンブル済みLC-3オブジェクトファイルを引数として渡す
lc3-vm path/to/2048.obj
  • 例として提供されるオブジェクトファイルは2048.objとrogue.objである
  • 2048の例はWASDキーで操作する
  • プログラムが正しく動作しない場合、命令実装の誤りである可能性が高い
    • LC-3アセンブリソースを読みながら、デバッガでVM命令を1ステップずつ実行する方法が推奨される
    • 想定した命令へ移動しない箇所があれば、その命令の仕様と実装を再確認する

オプション: C++ジェネリックベースの実装

  • より短いC++実装手法もオプションとして扱われる
  • 複数の命令がsign extension、PC基準offset、間接アドレス計算のような繰り返し処理を共有するため、命令実行を小さな処理段階のパイプラインとして見ることができる
  • C++テンプレートとビットフラグを使い、opcodeごとに必要な処理段階だけをコンパイル時に含める
  • この方式はコード重複を減らし、各処理段階がチップの物理空間を占める実際のハードウェア配線方式により近い
  • アイデアの出典としてBisqwit’s NES emulatorが言及されている

資料と貢献

  • atul-gがシステム全体の動作を要約するreference cardを提供している
  • さまざまな言語による実装はGitHub topic lc3にまとめられている
    • C、C++、Go、Haskell、Java、JavaScript、Kotlin、Lua、OCaml、Python、Ruby、Rust、Swift、TypeScript、Zigなどが含まれる
  • 自分の実装を一覧に表示させたい場合は、GitHub topic lc3を付ければよい
  • Windowsプラットフォーム対応はinkydragonが貢献した
  • プロジェクトには統合テストに関するgood first issueがある

関連記事

1件のコメント

 
GN⁺ 2024-12-28
Hacker News のコメント

  • 10代のころ、コミュニティカレッジのコンピュータサイエンス入門の授業で、簡単なCPU命令セットを設計し、自分で仮想マシンとアセンブラを作ってアセンブリプログラムを書いて実行してみたことがある
    驚くほど簡単で、コンピュータがずっと神秘的ではないものに感じられた
    FPGA向けの実際のCPU設計から、簡単なOSやその上で動くプログラムを書くところまで、こういうやり方でコンピューティングのあらゆる層を学べそうだと思う
    現代のコンピューティングが要求する性能やセキュリティを除いて、「動けばよい」という目標なら、この分野は意外なほど単純だ

    • 面白そうな授業だし、https://www.nand2tetris.org/やCharles Petzoldの本Codeととてもよく似ているように見える
    • 最初の想像上のCPUから、80286のような実際に量産された初期CPUへ移る瞬間に、複雑さが一気に跳ね上がる
      記憶が正しければ、少なくともメモリセグメンテーションとプロテクトモード、MMUが入ってくる
    • CS 101の授業にもそういうシステムがあった
      PDP上でBASICで書かれた簡単なコンピュータ／アセンブラで、課題の一つはループで加算を繰り返して単純な乗算を実装することだった
      友人はその代わりにプログラムを修正して新しいMUL命令を作り、先生はまったく喜ばなかった
    • 単純な構成要素そのものは本当に簡単だが、実際のユーザーがコンピュータ上で見たり触れたりする商用品質の成果物までは何百もの層で隔てられている
      好奇心があって学ぶ意欲のある人なら、こうした基礎層は簡単に身につけられるが、「早く稼いでできるだけ早く就職できるようになりたい」人にはそうではない
    • nand2tetrisのコースはまさにそういうことをやっているようだ

  • おすすめされた本:

    1. SmithとNairのVirtual Machines: Versatile Platforms for Systems and Processes — このテーマを包括的に概観する本のように見える
    2. Iain CraigのVirtual Machines — 言語と仮想マシンを扱う、より実践寄りの本のように見える
    3. Bill BlundenのVirtual Machine Design and Implementation in C/C++ — 実装中心の実践書のように見える
      これらの本を読んだことがある人がコメントを付けてくれれば、みんなの助けになるはずだ
    • このテーマが本一冊で概観できるほど狭いものなのか、よく分からない
      Nintendoエミュレータ、VT-xを使うハイパーバイザ、伝統的なマルチタスクOS、新しいスクリプト言語のインタプリタ、SQLクエリ最適化器、正規表現マッチャ、ゲームサーバーで信頼できないプレイヤーコードを動かすセキュリティ監視機構などは、考慮事項がほとんど重ならないように見えるが、どれも仮想マシンだ
      文字セル端末のエスケープシーケンスを指定するterminfo形式の中にも、スタックベースの仮想マシンがある
      深く見れば、今日的な意味でコンピュータをコンピュータたらしめているものが仮想マシンであり、チューリングの1936年のEntscheidungsproblem論文も、仮想マシン同士が互いを模倣できることに関わっていた

  • Ben EaterのブレッドボードCPUシリーズを見てから、自分でもCPUを設計してエミュレートしてみたいという気持ちしかない
    座ってそれを設計する時間を見つけられたらいいのだが

  • Brookshear MachineやLittle Computerのような教育用アーキテクチャは、実際のアーキテクチャにまったく似ていないので、役に立たないどころか有害だと思う
    そういうものを使う授業を受けた学生が、何の授業も受けていない人よりも、コンピュータをもっと歪めて理解してしまうのを見たことがある
    自分のコンピュータがどう動くのかを少し学びたい大半の人には、OSの授業のほうがよく、ここでも短いチュートリアルを一つだけやる時間があるなら、「Writing my own bootloader」を勧める
    https://dev.to/frosnerd/writing-my-own-boot-loader-3mld
    これは「Write your own VM」チュートリアルが悪いと言っているのではなく、私の経験では、それをやる人の大半には別のテーマのほうが役に立つという意味だ

    • たった今LC-3を触ってみて、今のプロジェクトではLC-3を不適切な対象マシンとして使い、動的再コンパイルを少し学んでみようとしている
      コンピュータアーキテクチャを学ぶうえでLC-3がなぜ悪いのか、もう少し説明してもらえるだろうか
      実際のハードウェアと完全に違い、単純すぎるというのは理解しているが、CPUエミュレータを書くという観点でもよくないのか気になっている
    • Knuthの古いMIXを思い出す
      1960年代なら作られていてもおかしくない10進機だったが、1970年代以降は誰も作らなかった類のものだ
      ああいうシステムは多くの基本を教えられるが、https://en.wikipedia.org/wiki/Hacker%27s_Delightに出てくるテクニックは主に一般的な数表現方式に依存しているので、学びにくい
    • LC-3のどの点が特に気に入らないのか気になる
      詳しくないのでWikipediaを少し見ただけだが、漫画を見て妙なものを想像していたわりには、ぱっと見それほど衝撃的ではなかった
      s/360と、少しのx86、ごく少しのARMまたは他のRISC系アーキテクチャが混ざった感じで、省略された部分や変な部分は多いものの、目標は素早く動く実装まで持っていくことのように見える
      何が理由で、教育用として「役に立たないどころか有害」だと考えるのか知りたい
    • 古い8ビットアーキテクチャの6502やZ80を使うことを勧める
      インドの多くのコンピュータサイエンスの授業では、今でも8086/8088を使っているようだ
    • LC-3はアドレッシングモードがかなり独特だ
      特に、途中のPC相対ワードを通じて二重間接ロードができる
      それなのに減算は否定から作り、否定はNOTとADD ,,#-1から作らなければならない
      限られた命令エンコーディング空間を考えると、NOT d,s = XOR d,s,#-1のほうがより良い使い道だったように思える

  • 厳密に言えば、これは仮想マシンではなくエミュレータである
    説明的な意味ではその用語を当てはめることもでき、ハードウェア仮想化以前の時代にはある程度の曖昧さもあったが、現代において「Virtual Machine」の圧倒的に一般的な用法は、VT-x のようなハードウェア仮想化機能を使う環境を指す

    • その用法が「圧倒的に一般的」だという点には同意できず、完全に正しい区別とも言いがたい
      JVM は広く普及しており、Ethereum VM はEVMと呼ばれ、https://www.linuxfoundation.org/hubfs/LF%20Research/The_Stat... でも BPF と eBPF を繰り返し「virtual machines」と説明しており、https://webassembly.org/ は「WebAssembly（abbreviated Wasm）はスタックベースの仮想マシンのためのバイナリ命令形式です」と書き出している
      「仮想マシン」は今でも仮想の機械を指す最も一般的な呼び方である
      個人的には「fictive machine」「fictious machine」「imaginary computer」「fantastic automaton」のような表現のほうが好みだが、採用されることはなさそうだ
      「仮想マシン」の代わりに常に「エミュレータ」を使えるわけではない
      wasmtime はエミュレータと呼べるかもしれないが、WebAssembly 自体をエミュレータと呼ぶのは正確ではなく、WebAssembly は wasmtime がエミュレートする仮想マシンである
      エミュレータを仮想マシンと呼ぶのも一般的であり、実行中のエミュレータインスタンスもまた別の意味での仮想マシンである
      ハードウェア仮想化環境を「仮想マシン」と呼ぶのも妥当であり、この最後の意味とはある程度重なっている
      現在の環境ではその用法が圧倒的に一般的かもしれないが、他の場面で必ずしもそうとは限らない
    • 丁重に異議を唱えたい
      最も純粋な意味では、仮想マシンとは作り出されたコンピュータにすぎず、何に使われるのかや、どう動作するのかまでは含意しない
      文章では古典的なコンソールエミュレーションを例にしているが、提示された定義からすれば可能な仮想マシンはそれよりはるかに多いことは明らかである
      要点は、仮想マシンは抽象的な概念であり、その種類が非常に多いということだ
      シミュレータ、エミュレータ、ハイパーバイザなどはいずれも仮想マシンであり、まだ名前の付いていない奇妙な形の仮想マシンもある
      無礼に言いたいのではなく、むしろ敬意をもって、学ぼうとしている人たちのためにこの用語を明確にしたい
    • 擁護されているその区別は、実際には存在しないと思う
      「仮想マシン」は、理由を問わず機械語またはバイトコードを実行するあらゆるソフトウェアに一般的に使われる
      仮想化を含むこともあるが、Java の JVM や Ruby の YARV（Yet Another Ruby VM）のような言語ランタイムにもよく使われる
      むしろこの用語をあまり聞かない領域はエミュレーションのほうで、これは現代のエミュレータの多くがシステム全体をエミュレートするよりも、対象ソフトウェアを動的再コンパイルする手法に傾いているためでもある
    • これは JVM、つまり Java Virtual Machine における意味でのVMである
      Java ほどであれば、「圧倒的に一般的な用法」に当たると言えるだろう