MITで使われてた(る)教育用のOS、xv6を動かせるx86のエミュレーターを作りました。バイナリトランスレーションではなくCPU命令やMMU、デバイス等を手動で実装しました。

レポジトリ: https://github.com/ykskb/dax86

以下READMEからの抜粋です。

なぜ作ったか:

  • CPUの上でOSがどう実装されて動くのか知りたかった。

何を作ったか:

  • memfsのxv6がブートから走ります。
  • パイプライン化やアウトオブオーダー等は使わず、実装されてるCPU命令は一つ一つ順に実行されます。
  • 理解の為にパフォーマンスよりもロジックやデバイスを分かりやすく表現することの方が重視されてます。CPU命令やハードウェアの実装には説明コメントも書かれています。

この記事ではこのプロジェクトで自分がどうCPUについて調べつつエミュレーターを実装していったか、また詰まった所などを書いてます。

このプロジェクトで学んだキーポイントを他の記事にしています。

始まり

このプロジェクトはこの本、自作エミュレータで学ぶx86アーキテクチャを読んで始まりました。かわいい女の子が表紙で戸惑うかどうかはさておき、逐次実行型のエミュレーターを作るには最適のスターターブックです。基本的なmovやadd命令、さらにはクリティカルなpushやcall命令がeflagsやModR/Mの説明と共にどう実装すればいいか詳細に書かれています。dax86でのCPUの構造体やCPU命令の宣言構成等はこの本のコードを拡張したものになってます。

本を読み終え、エミュレーターの形ができ、テスト用の実行バイナリがいくつか走るようになりました。しかしこの時点ではOSが走るには足りない実装が多数ありました。セグメントレジスターやコントロールレジスター、デバイスも無い状態ですし、32ビットの実行バイナリが前提だったので、スイッチを入れた時点ではリアルモード下で命令が16ビットで解釈される実際のx86マシンの動作も無い状況でした。さらにはCISCであるx86にはシングルバイト命令が約250個とダブルバイト命令が更に250個ほどあり、実装すべきCPU命令が山のように感じられました。

ブート

xv6を走らせるという目標に決めたので、基本的なシングルバイト命令の実装しつつx86アーキテクチャとxv6の内部を理解する為に様々なドキュメントやウェブサイトを読みました。x86についてはA20ラインやセグメンテーション、GDT(グローバルデスクリプター)やページングについて学び、xv6に於いてはブート部分のコードを読み、先述のメモリ管理構造に加えキーボードやディスクなどのデバイスが必要なことが分かりました。

この時点ではブート部分辺りの理解や実装だったので、部分的にテスト用のアセンブリやCを書き、目標とする振る舞いを実装するといったTDD的なアプローチが出来ました。(tests/execが該当ディレクトリです。)ただこの目標とする振る舞いの設定というのが簡単ではなく、自分の理解で設定するしか方法が無いので、本当にあってるのか不安な所が多々あり、実際に間違った理解でテストの目標を設定していた為に何回か後になって難解なバグとなって帰ってくるのを経験しました。具体的な例としては、GDTのベースアドレスの構成方法が間違っていて、テストケースである0x00000000(プロテクトモードに跳ぶ際によく使われる値)は構成できてて通っていたのですが、ゼロではない値をTSS(タスクステートセグメント)の為に構成する際にセットされた値が取得できずメモリーのエラーになってしまっていて、間違いを修正する為にかなりデバッグに労力と時間を費やすケースがありました。

ブート部分では主に2箇所で苦労しました。カーネルのコードをディスクからメモリーにロードする部分とページサイズ拡張されたページディレクトリを使ったカーネルへのジャンプ命令です。後者ではIdenticalな(ゼロがゼロに対応してる)マッピングと仮想アドレスのマッピングの二つがなぜ必要なのか理解するのも苦労しました。これらについては別の記事で詳細に書きましたが、OSイメージの作成からカーネルへジャンプするまでを完全に理解するのは自分にとっては中々大変でした。

OSの初期化

ブートの実装が何とか終わり、xv6のメイン関数に到達しました。このメイン関数はデバイスやCPUチップ、メモリーページ等の初期化を行い、最終的にはユーザーモードでOSのプロセススケジューラーを走らせます。ここで最初に詰まったのはマルチプロセッサーの為の構造でした。マルチプロセッサー機構ではデバイス割り込みが事前に設定されたルートに従って特定のCPUに送られる必要があり、BIOSが作成するMP設定テーブルやIOAPI、LAPICといったCPUのチップを実装する必要がありました。インターネットで情報を探すのですが、実際に仮想デバイスやチップとして実装する際に使えるようなデータ遷移の情報は中々ありません。行き着くのは海外の大学のコンピュータサイエンスコース用のウェブサイトかインテルの公式ドキュメントでした。やはりこういう問題は開発者の日常的なものではなく、Stackoverflow等で欲しい情報が得られるのは稀でした。その他書籍を読んだりして何とか理解に辿り着き、最終的には非同期スレッドをタイマーやキーボード用に走らせ、ロックを使ってメインのCPUスレッドのメモリに割り込みデータを書き込むようにしました。

メイン関数の後半では更なる労力と時間が必要とされました。先述したTSS(タスクステートセグメント)のバグや割り込み処理ルーチン等、命令実行のコンテクスト周りの実装でかなり詰まったのを覚えています。この時点では多数の初期化関数が走っていて部分的なテストケースを書くTDD的なアプローチはもう出来ませんでした。その為かなり力技なデバッグをする必要がありました。どこでバグが発生しているのかを見つける為、命令のログを実装したり、特定の命令ポインタ(EIP)をキャッチしてメモリ範囲を出力したりもしました。もはやコードが自分の管理下にあるという感覚は皆無でした。objdumpから逆アセンブルされた命令をエミュレーターから出力されたログとメモリ範囲と比較して追うのは辛かったですが貴重で楽しく感じました。

最初のシェルコマンド

最後のチャレンジは少し面白いものでした。カーネルのメイン関数はユーザーモードでプロセススケジューラーを始め、シェルを走らせるのが最後の仕事ですが、シェル開始のメッセージが表示されたのを確認したので、キーボードの入力をサポートする必要がありました。当然xv6は実際のマシンやqemuで走るのを想定されているので、キーボードのスキャンコードを適切に処理する機構を備えています。あまりホスト側のキーボードの設定をいじりたくなかったので、エミュレーターでは単純にgetcharで取得したASCIIコードをスキャンコードに戻すマッピングを作りこの機能を実装しました。その後lsを入力し、ファイルがリストされるのを確認しました。今の所小文字のマッピングしか作っていないし、かなり遅いリストでしたがここまで結構な時間をかけたのもあり、恐らく自分の経験では最高なlsコマンドでした。

dax86-xv6

あとがき

この記事を書いてる時点でlsやmkdir、echoコマンド等が正常に走るのは確認したのですが、まだ完全に安定してはいないようです。恐らくユーザーモードでのページマッピングか割り込みのコンテクストスイッチがうまくいってないようで、時々xv6の"remap"のエラーになってしまうのが確認されましたし、ユーザーモードで特定の命令ポインタになるとセグメンテーションフォルトになってしまうのも確認されました。これらのことからまだ実装を調査して直す必要がありそうですし、まだxv6の理解出来ていないところもあるので、それらに努力してまたキーポイント等を記事でシェアできればと思います。ここまで読んで頂きありがとうございました。