Rust 自作 OS 日記/Part 9 my new os...

2020 年を振り返ってみると、色々と検討した結果もう Rust を勉強するしかないなー ということになって春ごろから Rust の勉強を開始、そして myos の開発が始まりました。

さて、およそ半年開発を続けてきた「myos」ですが、

「私の OS」ってなんやねーん

という指摘があちこちから飛んでくるかと思ってましたが、そんなことはありませんでした( ˘ω˘ )

第一部、完。

すでに何度か触れているのでお気づきの方もいらっしゃるかと思いますが myos は moe の後継で、 最初のマイルストーンは C で記述された moe の機能を Rust で書き直すことでした。

まだ moe で実現されていた全ての機能を完全に置き換えることはできていませんが、当初のマイルストーンに到達し、 現在はアプリケーションの動作環境を整える段階になったと考えています。

UEFI / ACPI

UEFI は 2010 年代から使われ始めたファームウェア規格で、 ACPI はハードウェアの構成情報や電力制御に関するインターフェース規格です。 どちらも近年の PC では標準的に使われている規格です。 PC 以外の世界ではほとんど使われてませんが。

Rust で UEFI に対応するためには uefi-rs というライブラリを使うのが簡単です。

github.com

本来 UEFI で提供されている機能の一部がうまく扱えなかったりするのですが、今のところ myos の起動に支障はとくにないのでそのまま使っています。

また、同じところが提供している ACPI ライブラリも組み込んで使っていますが、こちらは不足している機能が多く moe の時に対応できていた機能の一部がまだ対応できていないので置き換えを検討しています。

マルチタスキング

myos では、タイマー割り込みによるオーソドックスなプリエンプティブマルチタスキング、 SMP や SMT によるハードウェアマルチスレッディング、 async + await による協調型マルチタスキングなど複数のマルチタスキングをサポートしています。

moe の SMP 対応は後から追加されたので実はオプションでした。 また、はじめて SMP 対応のコードを書いてみたので、コアごとに分離するべき情報がまとまってなかったり、色々中途半端なところがありました。

myos では最初から SMP 対応前提でスケジューラーなどが設計されました。 SMT (HTT) の割り当てはシステムの負荷が一定以上になるまでスケジューリングしないようになっています。 なお、 SMP 起動部分は古き良きリアルモードで起動する moe 時代のコードをほぼ踏襲することになりました。

ウィンドウシステム

moe では一時期ウィンドウシステムを実装していたものの GUI は不確定要素が大きくなるため、一時期悩んでいた不安定要素の原因になっているのではないかということで一旦削除されました。結果として犯人は別のところにいたことがわかりましたが、今更復活するのもめんどくさいのでなかったことにされてしまいました。

myos のウィンドウシステムは moe のコードを参考に開発されたのでアルファブレンドに対応しています。 moe の時代にあったカラーキーモードは myos ではアルファブレンド前提で完全に削除されました。 また、 moe の時代に実現予定だった機能としてウィンドウに影をつけることができるようになりました。

影をつけた代償として全てのウィンドウが半透過扱いになり、現状 SSE に対応していない事もあって描画は遅くなってしまった気がします。

メモリ管理

現状の myos はカーネルの配置以外にページングを使っていません。 厳密にはロングモードではページングを無効化できないので、物理アドレスと仮想アドレスが一致する Identity mapped という状態でページングを利用しています。

メモリ保護の観点では、開発言語として Rust を採用していること、アプリケーションの実行環境として Sandbox を想定していることなどから、ページングで保護する必要性があまりないのが現状です。

ページングの他の使い道としては、メモリ空間をアプリごとに分離して断片化に強くなるメリットがあります。 こちらはいずれ必要になってくるかもしれません。

なお、現状 4GB 以上の物理メモリが存在しても割り当てません。 これに関連して、メモリが 4GB 以上ある機種で 4GB 以上のメモリが割り当てられてうまく起動できない問題が一時期発生していました。

メモリアロケーターは Slab アロケーターを採用していますが、よくメモリが不足するようになってきたのでパラメータ調整中です。

ファイルシステム

起動時に initrd.img というファイルを読み込んで RAM ディスクとしてマウントしています。

ファイルシステム周りは将来非同期 I/O に対応するため仮実装の場所が多いです。

はりぼて OS エミュレーション

はりぼて OS の API の一部をエミュレーションで対応し、はりぼて OS のアプリがある程度動作します。 もともと initrd に対応してた時に、もしかして結構簡単に実装できるのではということで試験的に実装したものです。

はりぼて OS の 32bit アプリケーションを動かすためだけにカーネルに一部特殊なコードを実装しています。 将来は、エミュレーターやバイナリトランスレーションを導入してカーネル内部の特別扱いを辞めたいと考えています。

WebAssembly ランタイム

標準のアプリケーションバイナリ形式として WebAssembly を採用し、現在はインタプリタで実装しています。 やはり時々動作が遅いと感じることがあるので将来は JIT 対応したいです。

もともと moe でやりたかったのがこの WebAssembly 対応でしたが、諸般の事情で思うように実装が進まず、 myos で初めて実装する事ができました。

ここまでの機能が現状およそ２万行のコードで実現されています。 そのうち WebAssembly に関するコードが 1/4 程度あります。

本題

さて、 moe の後継ということは myos も megos ということになります。

megos はもともと独自の仮想機械を搭載していましたが、当時は色々と未成熟であまりうまく受け入れられませんでした。 一方、 WebAssembly は共通の仮想機械で将来性があります。 また、 WebAssembly で動くということは、ランタイムを移植すれば Web ブラウザでも同じアプリが実行できるということになります。

そんなわけで、世の中がもう少し落ち着いたら myos も megos としてリリースしたいと思っています。

myos の益々の発展をお祈りします。

BASIC-DOS

さいきん変な OS が発表されたっぽいです。

basicdos.com

2020 年になって DOS !!!

ぼくはこういうソフトを見つけた時に、普通の人とはちょっと視点で見てしまいます。

このソフト、ぼくの自作エミュレータで動くのかな？

バイナリないナリ

ということで、まずは公式サイトからダウンロードしてみましょう。

残念ながら、バイナリイメージを見つけることができませんでした。

ソースを GITHUB.COM からダウンロードして中身をのぞいてみます。

2020 年なのに開発環境も DOS !!!

そもそも、ブラウザで動かす前提なので通常のディスクイメージは提供してないようです。

幸いにして COM 形式のバイナリは git に含まれているようなので、そこからディスクイメージを錬成します。

とりあえず作った最初のイメージはブートエラーでした。

起動できるまで

IPL のソースを見てみます。

DOS の基本ブートシーケンスは IPL が IO.SYS と MSDOS.SYS を探して読み込もうとします。 PC-DOS の場合は IBMBIO.COM と IBMDOS.COM という名前になる以外は基本的に同じです。 この OS ではそれに加えて CONFIG.SYS も読み込もうとするようです。いくつか CONFIG.SYS のサンプルがあったのでそれも組み込むようにしました。

また、当初 2HD でイメージを作りましたが BPB の内容が 160KB だったので 160KB で作り直しました。 IPL にうまくパッチを当てれば 2HD でも起動できそうですがそちらは試していません。

なんとか起動してコマンドプロンプトまで進みました。

古の開発環境再来

なんとか起動しましたが、キー入力の応答が悪く、カーソルの描画も変な感じでした。

コンソールドライバのソースを調査して原因の予想がついたので自作エミュレータ側を改修する必要がありますが、 なんと開発機をリプレースしたときに開発環境がなくなってしまっていたのでした。

ということで、開発環境を再構築しようとしましたが、必要なツールのひとつが darwin-arm64 なんか知らん！とエラーになってしまいました・・・。

これのためだけに x86 環境整えるのもなんだかめんどくさいなったので、古い Mac 君に頑張ってもらうことにしました。 久々に触った Intel Mac はとても重みを感じます。

修正

カーソルの描画がおかしい問題は、おそらくエミュレータ側の座標計算が間違ってるだろうということですぐに解決しました。

問題はキー入力です。

通常、自作エミュレーターのキー入力は以下のようなフローで動きます。

ブラウザでキーを押す
　↓
ホストOSのキーイベントが発生
　↓
JS のキーイベント発生
　↓
PS/2 ドライバがスキャンコードに変換して FIFO に書き込み、 IRQ 発火
　↓
BIOS が PS/2 ポート(60)から FIFO の値を読み出してキーバッファに書き込む
　↓
キーボード BIOS がキーバッファからキーデータを読み込む

一方、この OS のキーボードドライバを入れるとこうなります。

ブラウザでキーを押す
　↓
ホストOSのキーイベントが発生
　↓
JS のキーイベント発生
　↓
PS/2 ドライバがスキャンコードに変換して FIFO に書き込み、 IRQ 発火
　↓
OS のドライバが PS/2 ポートの FIFO の値を盗み見してホットキーの処理をし、 
BIOS の IRQ ハンドラを呼び出す
　↓
BIOS が PS/2 ポート(60)から FIFO の値を読み出す→この時 FIFO がすでに空
　↓
キーボード BIOS がキーバッファからキーデータを読み込む→空

OS のドライバが先に FIFO の値を読み込んでしまうので、その後 BIOS がキーデータを読み出す時には FIFO が空になってしまいます。

これを対策するために PS/2 のキーデータを FIFO ではなく上書き方式にすると、キー入力自体はできるようになりました。

しかし、IRQ の発火回数とデータの読み取り回数が一致しなくなるので、短期間に連続でデータが来た時のデータを保証することができなくなって取りこぼしや重複する問題が発生します。 この変更によって今まで動いていたソフトにも影響が出てしまう可能性があるので対策を考えています。

突然の UNDEFINED INSTRUCTION

とりあえず起動して操作できるようになったので、いくつか付属のアプリの動きを検証してみます。

＿人人人人人人人人人人人人人人人人＿ ＞　突然の UNDEFINED INSTRUCTION　＜ ￣Y^{YYYYYYYYYYYYYYY}^￣

エミュレーターのバグの可能性もあるので色々調査したところ、普通に直接呼び出していました。

FFBF:04D0 をリニアアドレスにすると 0x1000C0 になり、さらに A20 をマスクすると 0x000C0 になります。 INT 0x30 の割り込みベクタと一致します。

CALL 5 って CP/M 互換システムコールで使われているのですが、なんでこんな変なアドレスなんでしょうか？ よくわかりませんでした。

いかがでしたか

謎 OS を自作エミュレーターに対応させるのは楽しいですが、時には謎挙動に頭を悩ませることもあります。

それと開発環境はちゃんと残しておきましょう。

Rustの基本戦略

さいきん Rust の基本戦略をやっと完全に理解しました。

1. オブジェクトはスタックに割り当てます。（スタックポインタを減算するだけ）
2. 所有権とライフタイムによってオブジェクトの生存期間が関数の生存期間を超えないように制御します。
3. 関数を抜けたらスタックのオブジェクトを破棄します。（スタックポインタを元に戻すだけ）

２の所有権やライフタイムはコンパイル時にチェックされるので実行時は１と３のスタックポインタ操作だけになり、この仕組みだけを使ったオブジェクトは安全で高速に割り当てと解放が可能です。これが Rust の最も基本となるオブジェクト割り当て方針です。

この仕組みでオブジェクトの割り当てが不可能な状況が２つ存在します。オブジェクトのサイズがコンパイル時にわからないケースと、オブジェクトの生存期間が関数の生存期間を超える（かもしれない）ケースです。

オブジェクトのサイズがわからないとスタックポインタの操作が難しくなるのでスタックに確保できず、 Box や Vec などの専用のラッパークラスを経由してヒープに割り当てる必要があります。 *1

関数の生存期間を超えるライフタイムのオブジェクトは、ライフタイムを調整して静的またはヒープに割り当てるケースと、関数の戻り値にライフタイムを指定して調整するケースがあります。

静的に割り当てたオブジェクトは初期化メソッドが const fn であるなどの制約がありますが、プログラムの実行中は常に生存している最も寿命が長いオブジェクトになります。また静的オブジェクトの参照を表す特殊なライフタイムが 'static になります。

ヒープに割り当てる場合は一番制約が少ないですが、先述のように専用のラッパークラスを利用し、さらにアロケーターによる複雑なアルゴリズムでメモリの割り当てと解放を行うので最も遅くなるオブジェクトでもあります。 ヒープに割り当てたオブジェクトは所有権とライフタイムによって寿命管理され、誰からも参照されなくなったとコンパイラが判断した時に開放されますが、コンパイラの判断が難しいケースではさらに Rc や Arc などでラッピングして実行時に所有権を管理します。 *2

最後の関数の戻り値にライフタイムを指定するケースはオブジェクトがどうやって割り当てられているのかよくわからないのでもう少し調査が必要です。予想としては、呼び出す側の関数のスタックに場所だけ割りてておいて呼び出される側に渡してるんでしょうか？

以上のように、所有権とライフタイムをコンパイラが管理することで安全性を担保しつつ、可能な限りオブジェクトをスタックに割り当てることで高速に実行できるのが Rust の特徴ということがわかります。

そして、なぜコンパイル時に配列のサイズが確定できないとコンパイラが猛烈に怒り出すのかもこれでわかるかと思います。

Rust なんもわからん。

*1: Vec のようにサイズが無限に拡大するオブジェクトは無理でも、サイズが初期パラメータで半固定になる配列なら可能な気もしますが・・・

*2:他の言語はたいていヒープに確保するオブジェクトの利用がメインで、所有権に相当する概念はデフォルトで実行時に管理します

ロゼッタと林檎と

最近 myos の開発していて気になったことがあります。

myos のスケジューラーをほとんどいじってないのに今まで見たことない不審な動きをするようになったんですよ

そういえば、開発用の Mac を Intel から Apple に買い替えました。

そして、現状 Apple Mac の brew で qemu 入れようとすると Intel 版 (Rosetta) しか使えません。

どうやら Rosetta 版の qemu は同期関係がうまく動いてないようです。強いメモリとか弱いメモリとか電磁メモリとか云々・・・

というわけで、 Apple ネイティブの qemu が必要になりました。

でも、ソースからビルドするのはめんどいな〜

そこのあなた！なんと、便利なアプリがあります。

github.com

本来は iOS で qemu 使うための GUI フロントエンドアプリのようですが、このアプリはパッチ済みのネイティブ版 qemu を同梱しています。

GUI の設定だけだと myos を動かすには色々足りないものがあったのでカスタマイズが必要ですが、これでだいぶ安定して qemu が使えるようになりました。

Rust 自作 OS 日記/Part 8 🔔

飲食店のテーブルには謎のボタンがついていることがあります。 お店の中のものを勝手に触ると怒られますが、謎のボタンを押すと店員さんがやってきていろいろなサービスを受けることができます。 これって何かに似てませんか？

前回は WebAssembly のランタイムを実装しました。

WebAssembly 単体では計算とメモリアクセスくらいしかできません。 *1 APIを通してOSに依頼することでいろいろなサービスを受けることができます。

ということで、今回はAPIを実装します。

２種類のAPI

API を実装するにあたり、２種類の方式が思いつきます。

名前ベース方式

モジュール名と関数名を直接指定してインポートした関数を呼び出します。 WASI がこの方式を採用しています。

呼び出すコードはシンプルになりますが、機能ごとにインポートするためインポート項目が多くなります。

また、システムコールは通常 WASM 同士を直接リンクするわけではないので、２つの違う世界の関数を結びつけるためにパラメータの変換などを呼び出される全ての関数に実装する必要があってコストがかかります。

WASM を直接リンクできるリンカーがある場合、この方式ではサードパーティーによる拡張が比較的容易になります。

番号ベース（システムコール）方式

入口となる関数（システムコール）のみをインポートし、番号で機能を指定します。 確か Emscripten が Linux? API をエミュレーションするためにこの方式を採用していた気がします。

インターフェースとして実装する関数が少なくなるメリットがありますが、どの番号がどの機能になるか管理する必要があってサードパーティーによる拡張が難しく、一度公開された機能番号は後から変更が難しく将来廃れたAPIが歯抜けになりやすい問題もあります。

また、この方式は多くの OS においてユーザーモードからカーネルを呼び出すインターフェースに実際に使われています。 System Call や SVC (Supervisor Call) と呼ばれます。

今回はこちらを採用します。

こんにちは、世界

ではハローワールドを実装してみます。

WebAssembly に対応している言語は増えてきているので他の言語でアプリケーションを実装することもできますが、当面は Rust でサンプルを開発することにします。

Rust の wasm ターゲットは wasm32-unknown-unknown となります。まずはコンパイラの準備をします。

% rustup target add wasm32-unknown-unknown 

準備ができたらアプリフォルダを作ってゴリゴリ実装していきます。 ハローワールドくらいなら直接 API を呼び出してもいいですが、システムコール部分は myoslib というライブラリにまとめて他のアプリも開発できるようにしたいので以下のようなフォルダ構成にしました。

.
├── Cargo.toml
├── hello
│   ├── Cargo.toml
│   └── src
│       └── main.rs
└── myoslib
    ├── Cargo.toml
    └── src
        └── lib.rs

この構成にしてルート側の Cargo.toml の [workspace] のところにメンバーを追加することで一発でビルドできるようになります。

また、 hello/Cargo.toml は以下のように myoslib を読み込めるようにします。

[package]
authors = ["省略"]
edition = "2018"
name = "hello"
version = "0.1.0"

[dependencies]
myoslib = {path = "../myoslib"}

hello/src/main.rs に以下のようなコードを書きます。

#![no_main]
#![no_std]

use core::fmt::Write;
use myoslib::*;

#[no_mangle]
fn _start() {
    println!("Hello, world!");
}

変なおまじないがたくさんありますが、割と普通？な Rust のソースです。

これをビルドします。

% cargo build --target wasm32-unknown-unknown --release

ビルドが成功したら target/wasm32-unknown-unknown/release/hello.wasm が出来上がるのでこれを動かしてみます。

動きました。 *2

マクロの裏側

前述のハローワールドは println! マクロを使うために結構いろんなライブラリ関数が組み込まれているようで、バイナリサイズが数十KBになります。バイナリの中をよくみるとリリースビルドしてもデバッグ情報が含まれていたので wasm-strip してみると数KBまで縮まりました。

そもそも println! マクロを使うのをやめると数百バイトまで小さくなります。 println! マクロは便利ですが小規模なアプリであまり乱用してはいけないと思いました。

ということで、 println! マクロを使わないハローワールドは以下のようなコードになります。

#![no_main]
#![no_std]

use myoslib::*;

#[no_mangle]
fn _start() {
    os_print("Hello, world!\n");
}

この os_print は myoslib の中で以下のように定義されています。

pub fn os_print(s: &str) {
    unsafe {
        syscall2(1, s.as_ptr() as usize, s.len());
    }
}

ここで呼び出している syscall2 が本当の API でシステムコールに相当します。 システムコールは Rust のソースの外の世界という扱いになるので呼び出すところは unsafe が必要になります。 なお、システムコールを実際に処理する関数は１つですが、 WebAssembly では引数の型によって別の関数が必要になるので引数の型に合わせて syscall0 〜 syscall6 というエイリアスを提供しています。

なお、この辺はまだ実験段階なので将来細かいところが変わる可能性があります。

1MB の壁

出来あがった wasm の内容をツールで確認してみると (memory 17) という項目があります。 これはメモリをおよそ 1MB 確保するという意味になります。 メモリをほとんど使ってないはずなのに、これはなんでしょうか？

Rust は Vec や Box などで明示的にラッピングしない限り基本的にスタックにオブジェクトを確保しようとします。 スタックはヒープよりも高速に割り当て・開放ができてアロケーターも不要になるためです。 wasm 自体も実行するためにスタックを必要としますが、こちらは通常のプログラムからは不可視です。 そこで、memory の一部を Rust が仮想的にスタックとして使える領域として使います。ここの初期値が 1MB となっています。 なお、 global 変数の 0 番目が仮想スタックポインタとして使われることが多いようです。

ほとんどメモリを使わない小さなアプリでも 1MB 固定で確保されてしまうのはなんとかしたいです。

Cargo.tomlのあるルートフォルダの下に .cargo/config というファイルを作り、

[target.wasm32-unknown-unknown]
rustflags = [
  "-C", "link-args=-z stack-size=32768",
]

のような記述をすることで、この領域を小さくすることができます。数字を増やせば逆に大きくすることもできます。 スタック領域が小さすぎるとアプリが正常に動作しませんし、大きすぎると実行時に大量のメモリを無駄に消費してしまうので調整が難しいところです。

なお、 WebAssembly ではメモリサイズを 64KB 単位のページで扱っているので、スタックサイズを最小の16バイトを指定しても実行時には最低 64KB 確保されます。 極端に小さくしすぎても無駄になるので筆者は間をとってとりあえず32KBにしておきました。

おまけ: AssemblyScript の場合

AssemblyScript の場合、デフォルトではメモリ管理用のランタイムが付いてくるのでハローワールドが 15KB ほどになってしまいますが、ランタイムが必要ない場合はオプションで取り除くことでソースをそのまま WebAssembly に変換したような無駄の少ないバイナリを得ることができます。 AssemblyScript は WebAssembly 専用の言語なので、他の言語よりも WebAssembly 本来の機能に近い演算子やキーワードを記述できるのが強みな感じがします。

一方、文字列型が UTF-16 になってしまう点や、オブジェクトを API に引き渡す部分が AssemblyScript 専用のインターフェースが必要になってしまうので、今回本採用は見送りになりました。いずれ対応するかもしれません。

次のステップ

ハローワールドは動くようになりましたが、それ以上のアプリを作るにはAPIが圧倒的に足りていません。 しばらくは API を充実させていくのが主な作業になりそうです。

*1:そもそも通常の OS ではアプリからハードウェアに勝手にアクセスするのは許されていないのでアプリ単体では何もできません。

*2:現在、FATドライバーが長いファイル名に対応していないので8.3型式から外れて変なファイル名になります。

Rust 自作 OS 日記/Part 7 次世代の OS へ。

myos の開発をはじめておよそ半年が経ちました。

前回の続き

前回の日記より実装も進歩してはりぼて OS でできることの８〜９割程度が myos でもできるようになりましたが、まだいくつか課題があります。

そもそも myos ははりぼて OS ベースではないし、はりぼて OS の再実装を目標としていたわけでもありません。 根本的な構造の違いによる非互換性もあります。元のカーネルのポリシーを曲げてまでそれ以上の互換性に拘る必要があるでしょうか？

64bit マルチコア対応のカーネルでスレッド非対応の 32bit アプリしか動かない現状はカーネルの無駄使いです。 いったんこの辺で完了として次のステップへ進む時がきました。

次世代のバイナリ形式

次世代のバイナリ形式といえば WebAssembly です。

WebAssembly は紆余曲折を経て作られた次世代の新しい共通実行形式です。 名前で想像がつくように元々は Web で使うために生まれたバイナリ形式ですが、将来性を見出した人たちによっていろんな分野で使われはじめています。 WebAssembly には未来があります。

WebAssembly は S 式で記述されたアセンブリソーステキスト形式の .wat とバイナリ形式の .wasm があり、ツールを使えば相互に変換可能です。 我々が使うのはもちろんバイナリ形式の方です。

WebAssembly のランタイムはすでに色々な人が作っているので myos に簡単に組み込めるものもあるかもしれません。 が、自作します。

WebAssembly の読み方

wasm ファイルを読み込むには LEB128 というエンコードを理解する必要があります。 これは小さい数値は1バイト、大きな数値はより多くのバイト数を割り当てた可変長のバイト列にしてファイルサイズを節約するためのエンコードです。

LEB128 の場合は名前の通りリトルエンディアンで、1バイトの8ビットのうち下位7ビットを実際のデータ、最上位ビットを後続バイトのフラグに使います。 つまり、 0x00-0x7F までなら１バイト(7bit)のデータ、 0x80-0xFF なら後続のバイトが続き、最上位ビットが０になるまで繰り返します。 各バイトは7ビットずつシフトしていくのでちょっと中途半端なデータになるしエンコードやデコード処理が面倒ですが、一般に数値データの情報量は12bit程度(正確な数値忘れました)と言われており、32bitや64bitの数値を小さいサイズで表現できる事が多いです。

また、 LEB128 の亜種で Signed LEB128 というものもあり、バイト列から実際の値に変換する処理は同じですが、データ結果の最上位ビットが 1 だった場合は空いてる残りの上位ビットを全部 1 にして負の数値として扱います。Signed LEB128 では 0x7F が -1 となります。

wasm ファイルはこの LEB128 エンコードをほとんどの項目で採用しているため、 LEB128 のストリームのような感じになっています。 実際には階層構造となっているのでファイルの先頭から最後まで全ての LEB128 データが直接繋がっているわけではないですが。

wasm ファイルの構造は固定の識別子(Magic)とバージョン番号のあとに１２種類のセクションが並んでいます。 Custom 以外のセクションは並び順が決まっていて順番が守られていないと不正なデータになります。 そのため WAT のソースとは違う順番で並んでいる事があります。 これは先頭の方のセクションで定義したデータを後ろのセクションから参照する必要があるためです。 type セクションなどはソースで定義しなくても func で定義した内容が自動的に追加されます。

各セクションの構造は 1 バイトのセクション識別子と LEB128 エンコードされたセクションのサイズがあり、その後に実際の内容が続きます。 ほとんどのセクションはベクタ構造のため、最初の値は LEB128 エンコードされた項目数となっているセクションが多いです。

WebAssembly ではファイルやセクションの終わりは定義されておらず、ファイル先頭から順番にセクションを読み込んでファイルが終わったらそこで終了になります。データが壊れているときの挙動がちょっと怖いですね。

• 0: custom セクション

WebAssembly の仕様書で定義されていないカスタムメタデータを格納するのに使います。 カスタムセクションはセクションの先頭に識別用の名前があります。

• 1: type セクション

関数のシグネチャ（引数と戻り値の型の組み合わせ）を定義します。 将来他の使い道も想定しているようです。

• 2: import セクション

外部（主に JavaScript）からインポートする項目を定義します。 モジュール名と実際の項目名を指定するため、モジュール名がネームスペースのような役割を果たしています。 なお、ここで定義された関数とバイナリ内部にある関数は連番となるので import 関数の分だけ定義と参照の番号がずれます。

• 3: func セクション

このバイナリに含まれている関数を定義します。 実際にこのセクションにある情報は type のインデックスだけなので n 番目の関数の型が T であるということしかわかりません。 実際の関数の情報はこれより前の type や import セクションの内容に依存し、名前は export セクション、コードは code セクションにそれぞれ分かれています。

• 4: table セクション

table は関数の識別子が入った配列で、このセクションでは table の大きさを決めます。 WebAssembly ではセキュリティのために間接呼び出しの call_indirect 命令で指定できるのは table のインデックスだけとなります。 将来的には複数の table が使えるような拡張を予定しているようですが、現状は 0〜1 個しかありません。

• 5: memory セクション

memory というデータ構造を定義します。このセクションでは memory の大きさを決めます。 将来的には複数の memory が使えるような拡張を予定しているようですが、現状は 1 個しかありません。*1

memory というのは WebAssembly のデータ領域で、 export されていれば JavaScript からは ArrayBuffer とほぼ同じようにアクセスできます。 WebAssembly の memory は 64KB 単位を１ページとするので (memory 1) と指定すると 64KB のメモリーを割り当てる意味になり、小規模なアプリは大体この指定になります。ちょっと大雑把ですね。

• 6: global セクション

グローバル変数を定義できます。あんまり使い道ない気がします。

• 7: export セクション

外部にエクスポートする項目を定義します。 func、table、 memory、global にそれぞれ名前をつけて外部に公開することができます。 実際に JavaScript から WebAssembly を呼び出す場合ここのセクションを使います。

• 8: start セクション

エントリポイントとなる function のインデックスを指定します。 エントリポイントは存在しない事も多いです。

• 9: elem セクション

先述の table の内容をあらかじめ定義するセクションです。 table の x 番目には function の y 番目という感じでデータを定義します。

• 10: code セクション

プログラムコードを定義します。 code セクションはさらに関数ごとに分かれて、それぞれの関数のローカル変数の定義と WebAssembly のバイトコード列があります。 WebAssembly バイトコードはオペコードのバイト値と必要に応じて LEB128 エンコードされたパラメータが繋がっているので、先頭から順番にちゃんとパースしていかないと命令の切れ目がよくわからなくなります。

• 11: data セクション

データ領域の内容を定義します。 このセクションで定義した内容は起動前に memory の特定の領域に書き込まれます。 不思議なことに書き込む memory のオフセットはバイトコードの式で記述し、通常は { i32.const XXXX; end } のようなコード列になります。*2 メリットがよくわからないし複雑なバイトコードを書き込んだらどう解釈されるんでしょうか・・・

これらのセクションを順番に読み込んでメモリ上に構造体を作ればロード処理は完了です。 800行くらいかかりました。

ロードが終わったらバイトコードを実行します。

実例

例としてこのような WAT のソースをアセンブルしてみます。 内容は２つの引数を足し算した結果を返すだけのよくあるサンプルです。

(module
  (func $add (export "add") (param $a i32) (param $b i32) (result i32)
    local.get $a
    local.get $b
    i32.add
  )
)

すると以下のようなバイナリになります。

00 61 73 6D 01 00 00 00 01 07 01 60 02 7F 7F 01
7F 03 02 01 00 07 07 01 03 61 64 64 00 00 0A 09
01 07 00 20 00 20 01 6A 0B

これを分解してみます。

まず先頭の 00 61 73 6D はマジックナンバー、次の 01 00 00 00 はリトルエンディアンで 0x00000001 となり、バージョン 1 を表します。 ここまでの 8 バイトはすべての wasm ファイルで共通の固定値です。

続く 01 07 01 60 02 7F 7F 01 7F は 01 がセクション 1 (type) 07 がサイズ(7) を表します。 次の 01 はこのセクション全体の要素数(1)、 60 は関数タイプを表す固定値、 02 7F 7F は要素数 2 のベクタ [0x7f, 0x7F] で 0x7F は i32 を表しているので引数の型は (i32 i32) となり、次の 01 7F は戻り値の要素数(1) と型(0x7F = i32) を表し、 ここまでを逆アセンブルすると (type $0 (func (param i32) (param i32) (result i32))) となります。 この type セクションは func などから自動生成されるので元のソースには記述されていません。

続く 03 02 01 00 は 03 がセクション 3 (func) 02 がサイズ (2) を表します。 次の 01 はこのセクション全体の要素数(1)、次の 00 が内容 (type 0)を表します。 ここまで逆アセンブルすると (func $0 (type $0) (param i32) (param i32) (result i32)) と等価になりますが、このままではコードブロックが定義されていません。

続く 07 07 01 03 61 64 64 00 00 は 07 がセクション 7 (export)、次の 07 がサイズ (7) を表します。 次の 01 はこのセクション全体の要素数(1)、次の 03 61 64 64 が関数名 (add) 、次の 00 はこの export が関数であることを表し、最後の 00 は関数のインデックス (0) を表します。 これを逆アセンブルすると (export "add" (func $0)) となります。元のソースでは func の中に隠れています。

最後の 0A 09 01 07 00 20 00 20 01 6A 0B は 0A がセクション 10 (code) 09 がサイズ(9) を表します。 次の 01 はこのセクション全体の要素数(1)、次の 07 は関数のサイズ(7)、次の 00 はローカル変数の要素数 (0)、残りの 20 00 20 01 6A 0B はコードで、これをさらに分解すると 20 00が get.local 0 20 01が get.local 1 6A が i32.add 0B が end となります。これを先ほどの func セクションと統合して逆アセンブルすると

 (func $0 (type $0) (param $0 i32) (param $1 i32) (result i32)
  local.get $0
  local.get $1
  i32.add
)

となります。

今までのセクションを統合して最後にルート要素として (module ) で囲むと

(module
 (type $0 (func (param i32) (param i32) (result i32)))
 (func $0 (type $0) (param $0 i32) (param $1 i32) (result i32)
   local.get $0
   local.get $1
   i32.add
 )
 (export "add" (func $0))
)

となり、これが完全な逆アセンブル結果になります。

スタックマシンと逆ポーランド記法

WebAssembly はスタックマシンのバイトコードを採用しています。 スタックマシンはデータをロードする時にスタックに push され、ストアはスタックから pop した値をストアし、演算命令は決まった数だけデータを pop してから結果を push します。 CPU の物理的なレジスタ構成に依存しないコードになるので中間言語としてよく使われる手法です。

また、スタックマシンのバイトコードは逆ポーランド記法の計算式とほぼ対応しています。 1 + 2 というよく知っている式を逆ポーランド記法にすると 1 2 + という式になり、これを WebAssembly のソースコードで記述すると

i32.const 1
i32.const 2
i32.add

となり、逆ポーランド記法の要素とバイトコードが 1:1 で対応しているのがわかるかと思います。

これらの操作を愚直に実装するとものすごい量の push と pop の繰り返しになるためとても遅くなりますが、簡単に実装できるので当面はこのまま実装します。 ロードストア系の命令と演算命令はスタックマシンを理解すれば比較的簡単に実装できます。

WebAssembly にポインタは存在しない

この辺りは JavaScript で WebAssembly を扱ったことがある人ならよく知っているかもしれません。

WebAssembly のデータ型は基本的に数値のみ (i32, i64, f32, f64) でオブジェクト参照もポインタもありません。 数値より複雑なデータ型はどうやって扱えばいいのでしょうか・・・？

ここで memory が登場します。

memory は JavaScript からは ArrayBuffer とほぼ同等のインターフェースを持った WebAssembly.Memory という型のオブジェクトで扱います。 WebAssembly のコードからはこの配列をメモリとみなしてデータの読み書きを行います。 メモリアクセスは i32 の数値を memory の配列のインデックス兼ポインターとして扱います。 ポインタというデータ型があるわけではなくメモリアクセス命令の方で意味を持たせるので低レベルの機械語に近いイメージです。

memory の範囲を超えるメモリアクセスは例外になりますが null ポインタは特に特別扱いされていません。 0 番地にデータを置くことも一応可能ですが、 null ポインタとの区別がつかなくなるので使わない方がいいです。

なお、現行バージョンでは memory は１つしか存在しませんが将来は複数に拡張する予定があるようです。 80286 の再来ですね。

ブロックと制御命令

WebAssembly では自由なアドレスに分岐できる命令が存在しません。

バイトコードは階層構造のブロックになっていて、分岐命令はブロックのネストに対する分岐として動作します。 しかし、ブロックの種類によってブロックを抜ける分岐とブロックの先頭に戻る分岐のどちらの動作になるか固定で指定できないため、ループの構造によっては複数のブロックが複雑に重なり合ったバイトコードになります。 いわゆる switch 文などを使った分岐先が多い関数の場合もものすごい量のブロックがネストしています。

ブロックに関わる命令として block, loop, if, else, end があります。

block 命令は分岐ラベルの付いたただのブロックです。 block に対する分岐は C 言語の break のようにブロックを抜ける動作をします。

loop 命令は繰り返し実行するブロックです。 loop に対する分岐は C 言語の continue のようにブロックの先頭に戻る動作をします。

if 命令は条件分岐のためのブロック、 else 命令は if とセットで使うブロックでペアになる if が実行されなかった時に代わりに実行されます。 if 〜 else ブロックは

比較命令
if
  expr1
  ..
else
  expr2
  ..
end

のような構造になり、通常は比較命令とセットで使います。

end はブロックの終端を表す命令です。ブロック命令のないトップレベルで end 命令があった場合は関数ブロックの終端を意味します。 つまりブロックのネストはバイトコード上では

block
    expr
end

のような構造になります。

なお、 else ブロックが続く if ブロックは else 命令が end 命令を兼ねているので、この場合 if ブロックには end 命令がありません。

ブロックには戻り値の型を指定することができ、ブロックを終了するときはスタックトップの値を戻り値として利用します。 繰り返しループされるブロックに戻り値を指定した場合の動きは仕様書を読んでもよくわかりませんでした。 for ループのような機能を実現するためにループ先頭で使うんでしょうか？

br 命令は分岐命令です。分岐対象は先述のようにブロックとなります。 対象ブロックの種類によって前方分岐か後方分岐か動作が変化します。 現在のネストを基準にしているので br 0 は現在いる最深ブロックを対象に分岐します。 また、分岐元と分岐先のスタックレベルが違う場合は巻き戻し処理が行われます。

br_if は条件分岐命令です。通常は比較命令とセットで比較命令の結果をスタックトップから取り出し、条件が成立した場合のみ分岐を実行します。

br_table 命令は C の switch 文で使います。スタックトップの値を取り出して命令の直後に続いているテーブルから表引きで分岐します。分岐表のためにとても長いバイトコードになります。

このように WebAssembly の制御命令は結構複雑な動作をするものが多いです。

関数呼び出しと引数とローカル変数

関数を呼び出すときは type セクションで定義した型の引数を push するとそれがパラメータとして渡ります。 一般的な C 言語の ABI と異なり、一番最初に push された値が一番左のパラメータ、一番最後に push された値が一番右のパラメータになります。 関数の中では一番左のパラメータは一番若い番号 (0) のローカル変数としてアクセスできます。

関数実行時にパラメータとローカル変数はまとめてひとつの配列のようなものに入れてローカル変数として渡されます。 引数以外のローカル変数は code セクションの関数本体の最初の方に定義されており、関数実行時には 0 で初期化されます。

call 命令は import セクションまたは func セクションで定義された関数の番号を指定して呼び出します。 両者は連番になっており、 import された関数の方が若い番号になります。

call_indirect 命令は table のインデックスを指定して関数を呼び出します。 table の内容は JavaScript からも操作することができますが WebAssembly のバイトコードから table の内容に直接アクセスする方法はありません。

return 命令は関数を終了して呼び出し元に戻るショートカット命令です。 関数のトップレベルにある end 命令でも関数を終了します。

標準 API の問題

WebAssembly には標準の API が存在しません。

WebAssembly 単体では数値演算か、 memory の中のバイト列を変更するくらいしかできません。

JavaScript から呼び出す場合は呼び出す JavaScript に完全に依存した構造となります。

ブラウザ外の実行環境では WASI という規格の標準化が進められている最中ですが、まだ正式版がリリースされておらず、 個人的には WASI はあまりいけてないかなと思っています。

その他の API の選択肢となるとあまり候補がありません。 WebAssembly は import/export を使って拡張が容易ですし、せっかく自作 OS を作っているので独自 API を考えていくのもいいかなと思います。

Minimum Viable Product

WebAssembly には MVP (Minimum Viable Product) と呼ばれる目標があり、現在は主要なブラウザで WebAssembly MVP がサポートされています。

すでにいくつか触れた通り、将来拡張予定の機能が MVP 実装では一部制限されています。 最初から目標を高くしすぎると実装が困難で時間もかかるので、最小限の機能をとりあえずまとめてリリースという感じでしょうか？

しかし、 WebAssembly MVP をフルスクラッチで実装しようと思うと意外と高い目標であることがわかります。

現状の myos ではここまで紹介した機能のすべてを実装することがまだできていません。 また、そもそも現状の myos でサポートできない機能もあるので myos における WemAssembly MVP の実装完了はまだまだ先になりそうです。

*1:理論上は 0 個も可能ですが、メモリを使わないプログラムはほぼあり得ないので

*2:ちなみに elem セクションなどにも同様の仕様があります

Rust 自作 OS 日記/Part 6 過去最大の更新

このシリーズの記事は月１くらいで書こうと思ってて前回からそんなに日付も経ってないのですが、 ここ最近で過去最大にいろいろ変わってしまったので前倒しで書くことにします。

initrd

某はりぼて OS では起動時にフロッピーディスクの内容をメモリに転送して RAM ディスクのように使います。 これ自体は特別珍しい仕様でもなく、 Linux などでも起動に必要なファイルをまとめたイメージを RAM ディスクとして読み込んで臨時ルートファイルシステムとして使う仕組みがあります。

というわけで myos も起動時にカーネルと一緒に initrd.img というファイルを RAM ディスクとして読み込む機能を実装しました。

myos は UEFI から起動するのでファイルを読み込む処理自体はカーネルの読み込みと同じように簡単に実装でき、セクションの再配置等をしなくて済む分カーネルの読み込みよりも簡単です。 ブートローダーの変更点はイメージファイルをメモリに読み込む処理と読み込んだアドレスをカーネルに教える数行程度です。

ファイルシステム

ファイルシステムにおける重要な概念として、ブロックデバイスとキャラクタデバイスがあります。 ブロックデバイスは本来ブロック単位で入出力するデバイスを指していて近年の定義ではバッファリングされるデバイスを指すようですが、実際にはファイルシステムが構築されるストレージを想定した概念です。 キャラクタデバイスは本来は主に文字単位で入出力するデバイスを指していて近年の定義ではバッファリングされないデバイスを指すようで、コンソール端末やシリアルポートなどが典型的なキャラクタデバイスになります。 ブロックとキャラクタどちらにも分類されない（できない）デバイスもあると思いますが、通常ブロックデバイスに含まれないデバイスは一般にキャラクタデバイスに分類されます。変な話ですね。 ブロックデバイスに対してファイルシステムとして見える形でアクセスできるようにする操作をマウントと言います。

initrd をサポートするにあたり、メモリ上の特定の領域をブロックデバイスに見せかけてアクセスするドライバ (いわゆる RAM ディスク) と、簡易的な FAT ファイルシステムのドライバを実装しました。

Rust では常に所有権を意識してオブジェクトを扱う必要がありますが、ファイルシステムは誰が何を所有するかというのが結構難しく、 また myos では非同期 I/O を採用する予定ですがこちらも管理や設計が難しく、現在はその辺が仮実装となっています。

アプリケーションの実行

ファイルが読み込みできるようになったのでアプリの実行もできるようにしてみました。

myos は某はりぼて OS と直接関連はありませんが、 API の数が少なく実装が比較的容易そうだったので実装してみました。 はりぼて OS エミュレーター(Haribote Os Emulator) の頭文字をとって HOE という名前にしました。 現在は 2/3 程度の API が実装され、半分くらいのアプリは動作しているようです。 なお、某はりぼて OS のアプリは大抵圧縮されてますが、現状 myos では圧縮アプリに非対応なので非圧縮版のバイナリを入手する必要があります。

Personality

HOE 対応にあたり、ネイティブタスクのスレッドと HOE 上で動作しているタスクを区別してコンテキスト管理できるようにスレッドに Personality を設定できるようにしました。 API を実行する際はスレッドに紐づけられた Personality から HOE ランタイムのインスタンスを取得し、各種ハンドルの変換やアプリ固有のデータはこのインスタンスを通じて管理します。

まだかなり汚い仮実装のところも多いですが、とりあえずアプリが動くようになって画面が賑やかになりました。

しかし 64bit のカーネルからセグメントをバリバリ使う 32bit アプリを呼び出すためかなり特殊な処理が多くなってしまいました。 いずれ本体の開発が落ち着いたら CPU エミュレーターでも作って対応した方がいいかもしれません（対応するとは言ってない