教育用のシンプルなOSであるxv6が動くRISC-Vエミュレータを作成しました。エミュレータのソースコードは全てd0iasm/rvemuのリポジトリで公開しています。本記事では、OSを動かすまでに実装したエミュレータの機能について、大きな変更をしたコミットのソースコードをたどることによって振り返ります。

注意：あとから実装のミスに気付いて直すことを繰り返しているため、各時点のソースコードが必ずしも正しい実装とは限りません。

2019年10月22日 (143c7d5: src/lib.rs)

リポジトリを作成して初めてのコミット。勉強のためにRustで開発したい、そして、エミュレータをブラウザで動かすためにWebAssemblyにコンパイルしたいと考えていたため、Rust and WebAssemblyのチュートリアルにあるテンプレートを使用して環境を整えた。src/lib.rs内でimportしているwasm-bindgenがRustとJavaScriptをブリッジしてくれるライブラリである。

エミュレータとしての機能はまだ何もない。

2019年10月30日 (2274ebf: src/cpu/instruction.rs)

2つのレジスタを足し算するaddと、レジスタと12ビットの即値を足し算するaddi命令を実装した。

RISC-Vは仕様が全てオープンであり、riscv.org/specificationsから仕様書のPDFをダウンロードできる。まずはこの中のVolume I: Unprivileged ISAを読んで、CPUの命令を一つずつ実装していくことにした。

コンピュータにおけるCPUの役割は、主にフェッチ、デコード、実行の3ステップによって、0と1のバイナリで構成されるプログラムを順に実行することである。

  1. フェッチ (Fetch): プログラムが保存されているメモリから次に実行すべき命令を取り出す。
  2. デコード (Decode): 命令列をCPUにとって意味のある形式に分割する。命令をどのように解釈するかはriscv.org/specificationsのVolume I: Unprivileged ISAに定義されている。
  3. 実行 (Execute): デコードによって指定された操作を実行する。ハードウェアならば足し算引き算などの算術演算はALU (Arithmetic logic unit) と連携して操作を行うが、エミュレータでは細かいコンポーネントを気にしないで実装することにした。

2019年11月11日 (2d59abc: src/cpu.rs)

32ビットアーキテクチャ用の基本整数演算命令のRV32Iを実装した。

RISC-VのISAは全てのプラットフォームが実装すべき基本整数演算命令に対して、用途に合わせて他の命令群を拡張することができる。32ビットアーキテクチャ用の基本整数演算をRV32I、64ビットアーキテクチャ用の基本整数演算をRV64Iと呼ぶ。

Volume I: Unprivileged ISAでは、よく使用される拡張命令群をまとめてRV32G/RV64G (general-purpose ISA) と呼ぶ。これは基本整数演算命令と、以下の6種類の拡張命令群を含む。エミュレータはRV64Gの命令を実装することを試みる。

  • RV32I/RV64I: 整数演算、ビット演算、シフト演算、メモリへのロードとストア、分岐命令など最も基本的な命令
  • RV32M/RV64M: 掛け算、割り算の命令
  • RV32A/RV64A: アトミック命令
  • RV32F/RV64F: 単精度浮動小数点数 (Float) の命令
  • RV32D/RV64D: 浮動小数点数 (Double) の命令
  • Zicsr: コントロールレジスタを操作するのための命令
  • Zifencei: フェンス命令 (メモリの書き込み順序を保証するための命令)

RV32Iでは40の命令を定義しており、今回はfence、ecall、ebreakを除く37命令を実装した。fence命令は複数のハードウェアスレッドが存在するときに、スレッド間でメモリの内容の一貫性を保つための命令である。ハードウェアスレッドとは、複数のスレッドの実行をハードウェアで提供することである。複数のハードウェアスレッドが存在するとは、つまり、次に実行すべき命令の位置を保存しているプログラムカウンタを複数持つことである。ハードウェアスレッドの数が多いほど同時に実行できるプログラムが増えるため高速化に繋がる。

エミュレータは1つのハードウェアスレッドしか実装していないので、今のところはfence命令は不必要であると判断した。また、ecallとebreakはVolume II: Privileged Architectureで定義されている特権モードを実装するときに必要になるが、この時点ではまだ実装していない。

2019年11月18日 (caea7c6: src/cpu.rs)

レジスタを64ビットに拡張し、64ビットアーキテクチャ用の基本整数演算命令であるRV64Iを実装した。RV64IはRV32Iの命令に対し12の命令を新たに追加したものである。基本的な操作はRV32Iと同じだが、有効なビット幅が異なる。例えば、RV32Iのadd命令は32ビット幅のレジスタ2つの足し算だが、RV64Iのadd命令は64ビット幅のレジスタ2つの足し算である。32ビット幅の足し算をするために、RV64Iではaddwという命令が追加されている。

2019年11月19日 (44c0584: src/cpu.rs)

掛け算、割り算の命令を定義するRV64Mを実装した。

掛け算では結果が64ビットに収まらない大きい数になった場合 (これは arithmetic overflow と呼ばれる)、下位の64ビットだけをレジスタに保存し、上位のビットは無視する。また、割り算では0による割り算の結果として全てのビットを立てる。このように、RISC-Vでは算術演算による例外を発生しないことにしている。なぜなら、例外処理をするためにはVolume II: Privileged Architectureで定義されている例外に関する機構を実装する必要があり、ハードウェアを小さくすることの弊害になり得るからだ。

2019年12月30日 (67558bd: src/cpu.rs)

32ビット幅の単精度浮動小数点数 (float) を定義するRV64Fを実装した。浮動小数点数はIEEEによって標準化されているIEEE 754-2008に準拠している。

RISC-VのCPUは整数のレジスタを32個持っているのだが、浮動小数点数を拡張する場合には追加で32個の浮動小数点数のレジスタを持つことになる。更にfcsrという状態を保持するステータスレジスタも持つ。fcsrは丸め処理をどのように行うかと、演算による例外発生が起きたかのフラグを保持する。例えば、0除算が起こった場合はfcsrの3ビット目 (DZフラグ) がセットされる。

丸め処理は以下のように5種類の方法が定義されているが、今のところちゃんと実装していない。(以下はwikipedia IEEE 754より引用)

  • 最近接丸め（偶数）: 最も近くの表現できる値へ丸める。表現可能な2つの値の中間の値であったら、一番低い仮数ビット（桁）が0になるほうを採用する。これは二進での標準動作かつ十進でも推奨となっている
  • 最近接丸め（0から遠いほうへ）: 最も近くの表現できる値へ丸める。表現可能な2つの値の中間の値であったら、正の値ならより大きいほう、負の値ならより小さいほうの値を採用する
  • 0方向への丸め: 0に近い側へ丸める。切り捨て (truncation) とも呼ばれる
  • +∞への丸め: 正の無限大に近い側へ丸める。切り上げ (rounding up, ceiling) とも呼ばれる
  • −∞への丸め: 負の無限大に近い側へ丸める。切り下げ (rounding down, floor) とも呼ばれる

2020年1月2日 (83ef66c: src/cpu.rs)

64ビット幅の倍精度浮動小数点数 (double) を定義するRV64Dを実装した。浮動小数点数はIEEEによって標準化されているIEEE 754-2008に準拠している。

基本的には単精度浮動小数点数 (RV64F) と同じである。今回も丸め処理はちゃんと実装していない。（いつかやる…）

2020年1月5日 (533ea69: src/cpu.rs)

アトミック命令を定義するRV64Aを実装した。

アトミック命令とは複数のハードウェアスレッド間でメモリの一貫性を保つための命令である。有名なものとして、x86ではcompare-and-swap (CAS)と呼ばれるアトミック命令が定義されている。compare-and-swap命令ではあるメモリ位置の内容と指定された値を比較し、等しければそのメモリ位置に別の指定された値を格納する。つまり、とあるメモリ位置の内容が変更されていないことを保証することができる。しかし、値が変更されていないことだけを確認するため、他のスレッドが元々の値Aを異なる値Bに変更したあと、また元の値Aに書き直すと値がAのままに見えるため、「変更がなかった」とcompare-and-swap命令を行うスレッドが誤認してしまうことがある。この問題をABA問題という。

RISC-VではABA問題を避けるために、compare-and-swapの代わりにload-reserved (LR) 命令とstore-conditional (SC) 命令を採用した。load-reserved命令では指定されたアドレスから値を読み、レジスタに値を保存する。その際にアドレスを予約する。store-conditional命令では、予約されたアドレスに何か変更があった場合、アドレスへの書き込みが失敗する。アドレスの値をチェックするcompare-and-swapとは異なり、load-reserved/store-conditionalではアドレス自体を監視するためABA問題を回避できる。

他にもアトミックに加算をする命令などが存在する。しかし、エミュレータではまだ1CPU (1スレッド) の実装なのでアトミック性は実装していない。（どのように実装すれば良いのかもまだよくわかっていない。）

2020年2月14日 (a751a6b: src/cpu.rs)

RISC-VはCPUの状態を保存するステータスレジスタ (CSR) を最大で4096個持つことができる。ステータスレジスタを読み書きするRV64Zicsrを実装した。

ステータスレジスタはRISC-Vの仕様書のVolume II: Privileged Architectureに定義されている。

2020年2月18日 (ba64dfa: src/exception.rs)

例外処理の一部を実装した。

RISC-Vでは例外、割り込み、トラップの用語を以下のように定義している。これらの用語はアーキテクチャや教科書によって異なる使われ方をしていることがあるが、本記事ではRISC-Vの定義に従う。

  • 例外 (Exception): プログラム実行中にCPU内部で発生する同期イベント。例えば、サポートされていない命令を実行しようとすると、例外が発生する
  • 割り込み (Interrupt): CPU外部で発生する非同期イベント。例えば、ユーザのキーボード入力などは割り込みとしてCPUに通知される
  • トラップ (Trap): 例外や割り込みが発生したさいに実行がトラップハンドラに移ること。トラップハンドラにはトラップが発生したときに実行するコードが格納されており、OSが用意する

例外の種類は現時点で14種類あり、例外が発生したときにmcauseステータスレジスタに例外の種類を示す値を保存する。

2020年2月22日 (6b6f7f9: src/cpu.rs)

特権レベルを遷移するmretとsret命令を実装した。

RISC-Vにおける特権レベルには現時点でマシンモード (M-mode)、ユーザモード (U-mode)、スーパーバイザーモード (S-mode) の3種類存在する。全てのプラットフォームは必ず最も原始的なマシンモードをサポートしなければならず、この時点までのエミュレータはマシンモードを前提として動いていた。

マシンモードのみを実装したハードウェアは、仮想アドレスなどの機能を持たずCPUはプログラムの命令を順に実行していくだけのシンプルものである。組み込みなどの分野で複雑な機能は必要ないが、ハードウェアを小さくしたい場合などには重宝される。対して、OSなどの複雑なシステムを動かしたい場合は、3種類のモードを全て実装する必要がある。

今回実装したmret命令はマシンモードから他の特権レベルに遷移するための命令である。遷移先の特権レベルはmstatusステータスレジスタのmppフィールドの値によって決定する。mppフィールドの値が0ならユーザモード、1ならスーパーバイザーモード、3ならマシンモードに遷移する。sret命令は同様にスーパーバイザーモードから他の特権レベルに遷移するための命令である。

2020年3月4日 (859d9fa: src/exception.rs)

例外をあげることによって特権レベルを遷移するecallを実装した。

ecall命令は、現在の特権レベルがマシンモードならenvironment-call-from-M-mode、スーパーバイザーモードならenvironment-call-from-S-mode、ユーザモードならenvironment-call-from-U-modeの例外を発生させる。そしてこれらの例外をトラップするときに、より権限の高いモードに遷移する。基本的にはecallが発生するとマシンモードに遷移するが、medelegとmidelegのステータスレジスタの値によってスーパーバイザーモードに権限を移譲することができる。

ecallとmret/sretは補完関係にある。以下に特権レベル遷移の簡略化した概要図を載せる。 privilege levels transition

2020年3月9日 (7cc38ab: src/devices/uart.rs)

CPUが外部とシリアル通信するための周辺機器であるUART (universal asynchronous receiver-transmitter) を実装した。

RISC-Vは周辺機器とメモリマップドI/Oの手法によってやり取りする。メモリマップドI/Oとは、周辺機器のレジスタが存在する特定のアドレスに読み書きすることによってデータをやり取りする手法である。CPUからはメモリアクセスと同じように扱うことができる。特定のアドレスの位置はRISC-Vのの仕様には載っておらず、（おそらく）マザーボードを設計した人が決める。今回はQEMUのvirtマシンと同じように実装した。

QEMUの実装を見ると、UARTは0x10000000の位置から0x100の大きさだけマップされていることがわかる。また、今回動かそうとしているxv6のUARTの実装を見ると、”16550a UART”を採用しており、このUARTの仕様はウェブからアクセスすることができる。

仕様では5種類のレジスタが存在しているが、全ての機能は実装せずxv6で使われている機能だけを実装した。

2020年3月13日 (ea77341: src/cpu.rs)

仮想メモリ機構によるアドレス変換を実装した。メモリにアクセスする前に、translate関数でアドレスを変換することにした。

今まではCPUがアドレスを指定すると、そのアドレスに手を加えることなくメモリやメモリマップドされた周辺機器とやり取りした。実際にメモリや周辺機器が存在するアドレスを物理アドレスと言う。仮想メモリ機構が有効化されると、CPUが扱うアドレスは仮想アドレスと呼ばれ、アドレスを物理アドレスに変換する必要がある。仮想メモリ機構はsatpステータスレジスタのmodeフィールドの値によって有効化される。アドレスの変換はハードウェアではMMU (memory management unit) が担当することが多いが、エミュレータではCPU内部に実装した。

RISC-Vではアドレス変換の方法をSv32、Sv39、Sv48の3種類定義している。今回はSv39のみを実装した。Sv39では仮想メモリのアドレス幅が39ビットあるため、最大で512GiB (=2**39)のメモリを使用できる。

アドレスの変換はハードウェアのページテーブルウォークによって行われる。ページテーブルとは仮想アドレスと物理アドレスを対応づけるために使われるデータ構造で、いわゆる固定長要素の配列である。RISC-VのSv39ではページテーブルが3段存在し、このテーブルの要素を辿っていくことで物理アドレスに変換する。

2020年3月16日 (d690e52: src/devices/plic.rs)

周辺機器からの割り込みを制御するPLIC (platform-level interrupt controller) を実装した。

PLICもUARTと同じくメモリマップドデバイスの一つである。QEMUの実装を見ると、PLICは0xc000000の位置から0x4000000の大きさだけマップされていることがわかる。

PLICの主な機能は、どの周辺機器がどのハードウェアスレッドに対して割り込んだかを伝えることである。xv6の割り込みの実装を見てみると、plic_claimの関数によって、どの周辺機器が割り込みを行ったかを示す値をPLICから得ている。xv6のplicの実装の実装を見ると、plic_claim関数ではPLIC_SCLAIMの位置にメモリマップドされた値を読んでいるだけだとわかる。よって、この時点ではまだ実装していないが、割り込みが発生したときにこのアドレスの位置の周辺機器を識別する値を書き込めばよい。

2020年3月18日 (1e7964f: src/interrupt.rs)

割り込みを実装した。

今まで実装したUARTやPLICの周辺機器は、メモリマップドされたアドレスに存在する値を読み書きできるだけで、まだ割り込みをすることができていなかった。

src/interrupt.rsで割り込みが発生ときにPLICのsclaimレジスタに周辺機器を識別する値を書き込んでいる。これにより、OS側の割り込みハンドラがこの値を読むことでどの周辺機器が割り込みを発生させたのか識別できる。

2020年3月18日 (e535d27: src/devices/clint.rs)

タイマー割り込みを行うためのCLINT (core-local interruptor) を実装した。

CLINTもUARTやPLICと同じくメモリマップドデバイスの一つである。QEMUの実装を見ると、CLINTは0x2000000の位置から0x10000の大きさだけマップされていることがわかる。

タイマーを初期化しているxv6の実装を見ると、インターバルタイムの1000000とMTIMEを足した値をCLINT_MTIMECMPの位置に書き込んでいるのがわかる。CPUが何サイクル実行したかをカウントするMTIMEレジスタの値がCPUこの値より大きくなったときに、タイマー割り込みが発生する。

2020年3月20日 (c225992: src/devices/virtio.rs)

ディスクやネットワークのインターフェースであるvirtioを実装した。ネットワークの方は実装しておらず、ディスクの読み書き部分である。

VirtioもUART、PLIC、CLINTと同じくメモリマップドデバイスの一つである。QEMUの実装を見ると、virtioは0x10001000の位置から0x1000の大きさだけマップされていることがわかる。

virtioの仕様書は読まずに、xv6のvirtioのドライバの実装内のディスクを読み書きする関数であるvirtio_disk_rwに対応するようにエミュレータを実装した。Virtioの実装時にはtakahirox/riscv-rustの実装も参考にさせていただいた。

これでxv6が動く。ここまでで実装した機能は、以下の通りである。しかし、浮動小数点数の丸めやアトミック命令の原子性はまだ実装できていないがxv6が動いているので、CPUの命令はここまで実装する必要が無かったのではないかと思う。

  • RV64G命令
  • 特権レベル
  • 関連するステータスレジスタ
  • 仮想メモリ機構
  • UART
  • CLINT
  • PLIC
  • Virtio

次の目標はLinuxを動かすことだが、まだわからないことだらけなので徐々に学んでいきたい。