借り初めのひみつきち

仮ブログです。移転先募集中

Rust 自作 OS 日記/Part 8 🔔

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

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

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

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

2種類のAPI

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

名前ベース方式

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

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

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

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

番号ベース(システムコール)方式

入口となる関数(システムコール)のみをインポートし、番号で機能を指定します。 確か EmscriptenLinux? 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 が出来上がるのでこれを動かしてみます。

f:id:neriring16:20201212215507p:plain

動きました。 *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 が必要になります。 なお、システムコールを実際に処理する関数は1つですが、 WebAssembly では引数の型によって別の関数が必要になるので引数の型に合わせて syscall0syscall6 というエイリアスを提供しています。

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

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型式から外れて変なファイル名になります。

妄想

モチベーション

wasm のサブセットを base64 に最適化したい

内容

単純なオクテットストリーム → base64 変換をするとサイズが約 4/3 になるが、以下のような変換で直接 base64 ストリームに変換することで効率低下を抑えることができる

i32 は wasm においては単なる整数としてのみでなくポインタや条件比較にも使用される最も基本的な型であり、高度な計算を必要としないプログラムであれば i32 命令のみで記述可能である

WebAssembly MVP 命令のうち型に関係ない基本命令と i32 命令を合わせるとおよそ60個 → リマップすれば 6bit で表現可能

LEB128 はそのままでは効率が悪いので 6bit で効率の良いエンコーディングを新たに考える

import/export の名前は半角英数に限定する

いけそうだな?

結論

zlib 圧縮してから base64 でよくね?

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

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

前回の続き

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

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

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

次世代のバイナリ形式

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

f:id:neriring16:20201127115209p:plain

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

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

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

WebAssembly の読み方

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

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

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

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

wasm ファイルの構造は固定の識別子(Magic)とバージョン番号のあとに12種類のセクションが並んでいます。 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 単位を1ページとするので (memory 1) と指定すると 64KB のメモリーを割り当てる意味になり、小規模なアプリは大体この指定になります。ちょっと大雑把ですね。

  • 6: global セクション

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

  • 7: export セクション

外部にエクスポートする項目を定義します。 functablememoryglobal にそれぞれ名前をつけて外部に公開することができます。 実際に 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 のソースをアセンブルしてみます。 内容は2つの引数を足し算した結果を返すだけのよくあるサンプルです。

(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 7F01 がセクション 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 0003 がセクション 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 0007 がセクション 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 0B0A がセクション 10 (code) 09 がサイズ(9) を表します。 次の 01 はこのセクション全体の要素数(1)、次の 07 は関数のサイズ(7)、次の 00 はローカル変数の要素数 (0)、残りの 20 00 20 01 6A 0B はコードで、これをさらに分解すると 20 00get.local 0 20 01get.local 1 6Ai32.add 0Bend となります。これを先ほどの 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 は1つしか存在しませんが将来は複数に拡張する予定があるようです。 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 過去最大の更新

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

initrd

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

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

f:id:neriring16:20201112095241p:plain

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

ファイルシステム

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

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

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

アプリケーションの実行

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

f:id:neriring16:20201113000947p:plain

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

Personality

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

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

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

Rust 自作 OS 日記/Part 5 マルチタスキング

古代のコンピュータでは1台のコンピュータでひとつのタスクを実行するのが普通でした。*1 現代のコンピュータでは1台のコンピュータで複数のタスクを同時に実行するのが当たり前となり、さらには複数の OS を並列に動かす技術さえあります。

複数のタスクを同時実行するためには、タスクの間を調停する機能が必要となります。

マルチタスキングの種類

ハードウェアでマルチタスキングを実現する機能としてマルチプロセッシング (SMP: Symmetric Multiprocessing) やハードウェアマルチスレッディング (SMT: Simultaneous Multi-Threading /HTTなど) があり、これは既に myos にも実装されています。いずれ詳しく取り上げるかもしれません。 一方、ソフトウェアでマルチタスキングを実現する方法は大きく分けると2種類あってそれぞれプリエンプティブマルチタスキングと協調的マルチタスキングと呼ばれます。

プリエンプティブマルチタスキングはタイマー割り込みなどを使ってごく短時間で実行するタスクを次々切り替える方式です。 現在実行中のタスクの実行権を強制的に取り上げて他のタスクに切り替えることをプリエンプションと言います。 実行中のタスクがどんな状態でも強制的に他のタスクに切り替えできることから応答性は良くなりますが、タスク切り替えのタイミングが把握しづらく、中途半端な状態で切り替わっても問題ないように排他処理などの実装のコストは大きくなります。

もう一方の協調的マルチタスキングはタスク側が明示的に実行権を明け渡した時にタスクを切り替える方式です。 メリットデメリットはプリエンプティブマルチタスキングの正反対で、実装コストが比較的小さくタスク側でタスク切り替えのタイミングを制御できる反面、ひとつのタスクが長時間実行されると他のタスクに切り替えできなくなって応答性が悪くなります。

現代の OS では主にプリエンプティブマルチタスキングを採用していますが、ハードウェアの I/O 待ち合わせ処理や GUI プログラミングにおけるイベントループ処理は一般的に協調的マルチタスキングかそれに近い動作をします。

myos でもこれに倣ってプリエンプティブマルチタスキングを実装していますが、協調的マルチタスキングを採用することで効率よく処理できるタスクも多く存在するため対応したいです。

幸いにして Rust には async / await という協調的マルチタスキングをサポートする言語機能が備わっているため、これを利用して効率的なタスク管理を実装します。

async / await

Rust の協調的マルチタスキングは Future という trait を実装したオブジェクトを使います。 協調動作する関数には async という特別なキーワードを付けて定義すると関数のコンテキスト (変数などの状態) を保存するために内部的な struct を作って dyn Future に変換します。 また、 await キーワードは async 関数の中でのみ利用でき、 await キーワードが現れた前後で関数のコンテキスト用 struct を分離してタスクを中断できるようにしています。

実は Rust が言語としてサポートしているのはここまでで、実際のタスクをどのように管理して実行するかは外部のライブラリに任されています。

いくつかメジャーなライブラリがあるようですが、自作 OS ですし Executor 自体は簡単なサンプルがあるのでそれをもとに実装します。

いざ実装

myos の場合、以下のようなオブジェクトが登場します。

Task

dyn Future に一意の TaskId を付けてラッピングしたもので、個別のタスクに相当します。

Executor

タスクの管理と実行を行う中心部です。 最も単純な Executor は配列に入れた dyn Future に対して順番に poll を呼び出し、 poll の中ではタスクが完了したら Poll::Ready<T> を、タスクが待ち状態に入ったら Poll::Pending を返すのを繰り返します。 myos の Executor は各スレッドにひとつ持つことができます。

TaskWaker

await で待ち状態に入ったタスクに対して再開可能になったことを通知します。

よかったね

ここまで実装してウィンドウメッセージの処理は async / await で処理できるようになり、ひとつのスレッドで複数のウィンドウのメッセージループを処理することができるようになりました。

f:id:neriring16:20201106001952p:plain ↑何が変わったか伝わりづらいスクリーンショット

実はタイマーとスケジューラーの内部処理に問題があってそっちの対応の方が手間がかかってました笑

*1:大規模なコンピュータではタイムシェアリングなどありましたが

Rust 自作 OS 日記/Part 4.1 おまけ

前回の日記でひとつ触れ忘れました。

Rust 自作 OS 日記/Part 4 フォントのはなし - 借り初めのひみつきち

ベクターフォントのラスターフォントにないもうひとつの利点、 それは描画予定のサイズよりあらかじめ大きいバッファに描画してから縮小して実際の画面に描画することでなめらかなフォントを描画できます。

やり方はいろいろ考えられますが、直線のアルゴリズムがブレゼンハムでもこの程度の描画は可能です。

f:id:neriring16:20201016224911p:plain

前回より見やすくなってるのではないでしょうか?

座標を実数で扱ったりサブピクセルレンダリングなどを利用するとさらに高品質に描画できる可能性があります。

Rust 自作 OS 日記/Part 4 フォントのはなし

古きよき太古のコンピューターは ROM にフォントを内蔵していたので文字コードを指定するだけで画面に文字を表示することができました。 現代のコンピューターは広大な画面に自由に図形を描画できるようになった代償として文字を表示するためにフォントが必要になりました。

ラスターフォントとベクターフォント

さて、フォントデータの形式は大きく分けるとラスターフォントとベクターフォントの2種類に大別されます。

ラスターフォントはラスタライズされたピクセルの集合で表現します。 メリットはコンピューターの画面もほぼ同じ仕組みで画像を表示しているので表示するための処理が簡単なところです。 デメリットはあらかじめ設計された固定サイズの表示が基本となり、拡大や縮小は無理やりアルゴリズムで補完してもあまり綺麗な表示はできません。 古いコンピューターや組み込み用途でよく使われます。自作 OS も大半はこの方式のフォントです。

ベクターフォントはペンで書くための座標の軌跡の組み合わせのようなデータ表現です。 メリットは座標の組み合わせのデータなので拡大縮小が容易です。ただし、小さいサイズや極端に大きいサイズはそのままではあまり綺麗に描画できません。 デメリットは画面に表示するためにペンを動かして描画する必要があるため処理が複雑になります。 現代の OS の GUI フォントは基本こちらを利用します。

このようにふたつのフォント形式はほぼ反対の性質を持っているので適材適所で使い分けされます。

コンソール用途ではラスターフォントで十分ですが、 GUI の画面はさまざまなフォントが必要になってくるためラスターフォントでは対応するのが困難になってきます。ベクターフォントが欲しいところです。

Hershey フォント

ベクターフォントといえば TrueType や OpenType が有名ですね。 こちらもそのうち対応したいところですが、仕様が複雑すぎていきなり実装は無理なので良いライブラリを探してくる必要がありそうです。

ところで、実はもっと簡単に対応できるフォントがあります。

Hershey fonts - Wikipedia

このフォントは座標のセットがテキストでエンコードされており、デコードして直線で繋ぐだけで描画できます。 理論上、 32 x 32 くらいのサイズを超えるフォントは実現不可能で曲線も表現できないのでそれほど複雑なフォントは表現できないですが、 それでもベクターフォントなのである程度の拡大縮小は自在です。

私の OS

そんなわけで私の OS にも実装してみました。

f:id:neriring16:20201013202656p:plain

f:id:neriring16:20201013202714p:plain

f:id:neriring16:20201013202725p:plain

このようにさまざまなフォントがさまざまなサイズで描画されて、だいぶそれっぽくなってきました。

見た目だけなら moe に近づいてきたか、もう追い越してる感じがしてきました。

ほんとのところは別のところに手をつけたかったですが、さいきん時間があまり取れなくて日記を書くのが遅れてしまいました(/ _ ; )