CとRustで一から作るマイクロカーネルOS

マイクロカーネルは浪漫に溢れる非常に作りがいのあるソフトウェアです。この記事は，「マイクロカーネルベースのOSの一から作ってIaaSで動かす」ことを目標に作ったマイクロカーネルベースのOS Resea（りーせあ）の設計と実装について軽くまとめた物です。

マイクロカーネル全般をまとめた資料はこちら （20120 2/29 追記）

ここでReseaがWebサーバのデモをやってます （終了しました 2019 12/23）

ソースコードはGitHubにあります。

マイクロカーネルとは

Linuxのようなモノリシックカーネルでは色んな機能がカーネル空間で動きますが，マイクロカーネルではユーザプロセスたちが互いに通信しながらOSを作り上げます。プロセス・スレッド・仮想メモリ管理，プロセス間通信，タイマーといった必要最低限の機能だけをカーネルが担います。デバイスドライバやファイルシステムといった残りの機能は，独立したユーザプロセスとして動きます。たとえデバイスドライバが暴走しても他のコンポーネントを壊すことはないのです。マイクロカーネルは信頼性が高く，疎結合で美しいシステムを可能するのです。

というようなマイクロカーネルファンの話を聞くと「Linuxは時代遅れだ！マイクロカーネルこそが未来だ！」と心がときめくのですが，現実は真逆です。モノリシックカーネルは開発しやすく性能の良い素晴らしい設計です。信頼性という観点ではマイクロカーネルは確かに秀でているかもしれませんが，銀の弾丸ではありません。複雑で美しい設計より，単純で醜い設計の方が大体上手くいくものです。worse is better です。（参考: TanenbaumとTorvaldsの議論）

とはいえ，モノリシックカーネルにはない魅力がマイクロカーネルにはあります。それは「カーネルは 必要最低限のプリミティブ だけをもつ」という，とても美しい設計思想です。浪漫ですね。

マイクロカーネルの仕組み

プロセスやスレッドはモノリシックカーネルと同じ概念です。プロセス間通信（IPC）もそうですが，マイクロカーネルでは特に重要な要素です。サーバ（マイクロカーネルではデーモンにあたるプログラムを「サーバ」と呼びます）同士通信しあってOSの機能を提供するので，通信部分がシステムの性能に大きく影響します。

LinuxのIPCにはパイプや，共有メモリ，ソケットなど色々ありますが，マイクロカーネル界ではメッセージパッシングが人気です。ざっくり言うと次のようなインターフェイスをカーネルが提供します:

send(destination, message);
receive(source, message);

宛先（destination）には，チャネルまたはポートと呼ばれるソケットのようなものを使うカーネル（間接型IPC）と，スレッドを指定するカーネル（直接型IPC）の2つの流儀があります。後者は使い勝手悪そうですが，ちょっぴりIPC性能が良いそうです。

また，IPCには非同期IPCと同期的IPCの二種類があります。非同期IPCでは，カーネル内のキューにメッセージを溜め込んでいきます。同期的IPCでは，送信・受信スレッド両方が揃うまでブロックします。同期的IPCではカーネルがキューを持たずに済み，同期的に動くおかげでデバッグが楽なのでおすすめです。

Linuxではシステムコールを発行してカーネルに処理をしてもらいますが，マイクロカーネルでは「サーバへのメッセージの送信」と「サーバからのメッセージの受信」という風に実装します。大体何でもメッセージパッシングでやります。デバイスからの割り込みやページフォルトなど本来カーネル内で処理される物も，メッセージとして対応するサーバに送られ，処理されます。

スレッド管理などカーネルが提供する機能については，専用のシステムコールを用意する（Zircon）か，カーネルサーバへのIPCとして実装する（MINIX）かの2種類あります。Reseaは後者です。

色んなマイクロカーネルたち

L4

L4は「性能を考えた設計をすれば，マイクロカーネルは遅くない」ということを証明したカーネルです。異様に速いです。色んな派生があり，研究だけはなく実世界でもしっかり使われています。中でも有名なのは iPhoneのSecure Enclave です。

MINIX

当初は教育目的で作られたマイクロカーネルベースのOSです。 Operating Systems: Design and Implementation という，オペレーティングシステムの解説とソースコードが一体になった電話帳みたいな本のために書かれたそうです。

Intel CPUで最も広く使われるOSになったり， 近年にはNetBSDのユーザランドが一式移植され実用性が増したりと，教育目的を超えた物になっています。

MINIX 3では高信頼性を掲げ，面白い試みが色々と行われています。

Fuchsia（Zircon）

Googleが開発している最近何かと話題のマイクロカーネルベースのOSです。カーネルはZirconという名前です。L4のように極限までシンプルにするのではなく，ある程度コンパクトにするという設計思想のようです。

システムコールも中々綺麗にまとまっています。システムコールに「ファイル」の概念が現れないのはマイクロカーネルらしさがあって面白いですね。個人的にはコードが読みやすく，システムコール体系も結構好みです。今後の発展が楽しみですね。

設計

せっかく一から作るので，Unix互換は目指さず綺麗でシンプルな「マイクロカーネルらしさ」を感じられるOSを作ることにします。具体的には，Unixの「全てはファイル」に倣って「全てはメッセージパッシング」を設計の根幹としました。つまり，ファイルの読み書きからページフォルトの処理まで全てメッセージパッシングで実現します。

メッセージパッシング

Reseaのメッセージパッシングは同期的かつ間接型です。Reseaでは一つのメッセージに3つのデータ（ペイロード）を設定できます：

• インライン（inline）ペイロード: 単純にコピーされるデータ
• チャネル（channel）ペイロード: チャネルの移譲
• ページ (page) ペイロード: 指定された仮想アドレスに対応する物理メモリページ

チャネル・ページペイロードはそれぞれを送信先プロセスに移す move 操作です。共有できません。各物理メモリページはどれか一つだけのプロセスが所持しています。なので，Reseaでは共有メモリを実装できません。意地でもメッセージパッシングします。

システムコール

Reseaはメッセージパッシングしか出来ない美しいシステムコール体系をもっています。

• cid_t open(void);
  • チャネルの作成
• error_t close(cid_t ch);
  • チャネルの削除
• error_t link(cid_t ch1, cid_t ch2);
  • チャネルの接続
• error_t transfer(cid_t src, cid_t dst);
  • src チャネル宛のメッセージを dst へ転送するようにする
• error_t ipc(cid_t ch, int syscall);
  • メッセージの送信と受信
• error_t notify(cid_t ch, notification_t notification);
  • notificationの送信。Unixのシグナルみたいなやつ。ブロックしない。

詳細な設計に興味がある人は， ドキュメントを読んでください。

実装（カーネル）

「Rustで書かれたカーネル」という謳い文句にはとても惹かれるものがあります。当初はカーネルをRustで書いていましたが途中で辞めました。というのも，Rustはマイクロカーネルを書くのには向いていない気がするのです。

• マイクロカーネルはコンテキストスイッチといった unsafe な操作の塊であり，普通にRustで書いても単に複雑になるだけ。
• 抽象化によって処理が隠れてしまう。どういう処理を行うのか明示的にしたい。RAIIをしたくない。メモリ割り当ての失敗もpanicせずエラーとして伝搬したい。
• 抽象化がないと辛いと感じるほど，マイクロカーネルは大きくないし複雑でもない。

ここで強調しておきたいのはRustという言語に問題があるという話ではなく，使い方の問題であるということです。「いつも」の使い方では上手くいかないということです。

というわけで，ユーザランドは全てRustですがカーネルはC言語で書くことにしました。C言語は機能も標準ライブラリも今どきの言語に比べて貧弱ですが，マイクロカーネルのようなベアメタルで動く小さなプログラムを書くには今もなお（多分いつまでも）最適な言語です。

結局，カーネルは5回くらい書き直しました。書き直す過程で色んな知見を得られま したが， 得られた知見はみんなこの論文にまとまってありました。先人はやはり偉大ですね。

実装（ユーザランド）

メモリ管理サーバ，TCP/IP，FAT32ファイルシステム，IDE（ハードディスク）ドライバ，e1000（ネットワークカード）ドライバ，キーボードドライバ，シェルを実装しました。それぞれ独立したユーザプロセスとして動きます。

ユーザランドはRustで実装することで，C言語でよくある厄介なバグに悩まされることがなくなりました。適当に書いてもしっかり動いてくれます。カーネルはよく逆アセンブリを読みながら厄介なバグを直していましたが，Rustで書いたユーザランドは全くその必要がありませんでした。書いている人間は同じなのに言語が違うだけでここまで変わるというのはすごいです。Cに比べフットプリントやビルド時間が増加するデメリットはありますが，その代償を払う価値は十分あると感じました。

さくらのクラウドへデプロイ

ようやく目標の「作ったOSのHTTPサーバをIaaSで動かす」です。今回はさくらのクラウドを使いました。何故かvirtio-netではなくe1000を選べるという非常に魅力的な機能と，課金体系と設定が分かりやすくポンコツTCP/IP実装が暴走してもクラウド破産しにくいという面から選びました。

KVMのはずなのでそのまま動くだろうと楽観視していましたが，現実は厳しいものでした。飛び交うARPパケットでメモリを使い果たしたり（実装が悪い），何も表示せずカーネルパニックを起こしていたりと，手元の環境では再現しないバグに立ち向かう日々を送る羽目になりました。おかげで勘デバッグ能力が上がりました。

それはそうと，さくらのクラウドで一つ不思議な挙動がありました。何故か一つ目のDHCP DISCOVERを返信してもらえないのです。後ほど再送すると返信してもらえます。ぽんこつe1000デバイスドライバが原因なのか起動が速すぎるのが原因なのか分かりませんが，後者だったら面白いですね。

ここでデモが動いています （終了しました 2019 12/23）。運が良ければReseaがWebページを返してくれます。

IPC fastpath

マイクロカーネルのメッセージパッシングには「よくあるケース」があります。クライアントプロセスは，リクエストをサーバプロセスに「送信」してレスポンスを「受信」するという送受信（call）操作がメインです。メッセージの内容にページやチャネルはあまり使われず，大抵は普通のデータ（整数型一つとか）だけ入っています。また，宛先チャネルでは大抵スレッドが既に受信状態で待っています。

このようなよくあるケースに特化したIPC実装（IPC fastpath）を加えることで，性能向上を図るというのがマイクロカーネルで見られます。面白そうなのでReseaにも実装してみました。

マイクロベンチマークとして，round-trip IPCを測ってみました。空のメッセージを送って空のメッセージを受け取るまでの処理にかかるCPUサイクル数を測るものです。ただしこれはマイクロカーネル界の Any%みたいなもので，システム全体の性能は全く別の話です。

参考までにseL4のベンチマークでは，筆者の理解が正しければround-trip IPCに 468 + 484 = 952サイクル かかっています。（ただし，彼らの具体的なベンチマーク設定が分からないので一概には言えません）

カーネル	CPUサイクル数	ベンチマーク環境
Resea (IPC fastpathなし)	2246	Intel Core i5-2467M SandyBridge
Resea (IPC fastpathあり)	1683	Intel Core i5-2467M SandyBridge
seL4	952	SkyLake 3.4GHz

Reseaの結果は上の表の通りになりました。fastpathだとまあまあ早くなるみたいですが，seL4の方が速いですね。ただ，どうやらFuchsia（Zircon）には勝っているようなので第2世代マイクロカーネルを名乗れる性能はあるのではないでしょうか。（これも具体的なベンチマーク設定が分からないので参考程度ですが）

IPC fastpathの実装はここにあります。すっきりしているのでお気に入りです。 seL4のIPC fastpathよりシンプルに実装できているのにベンチマークに負けているのは納得いかないですが，たぶんReseaの方はキャッシュメモリを上手く使えていないのでしょう。

デバッグに便利だったもの

Bochs

Bochsはx86_64 CPUエミュレータです。QEMUやVirtualBoxみたいなやつです。かなり遅いので普段はQEMUを使いますが，例外処理やコンテキストスイッチといったカーネルのコアの実装をする時には手放せないエミュレータです。xchg bx, bx という何もしない命令をブレークポイントとして認識してくれるので，デバッグしたい部分にこの命令を置いて，そこからステップ実行しながら処理を追っていく...ということをよくやりました。

Wireshark

WiresharkはTCP/IPのパケットキャプチャを読むやつとして有名ですが，BluetoothやUSBといったものまで扱える汎用プロトコルアナライザーです。Luaプラグインで 何にでも対応が可能です。そこで，Reseaのメッセージパッシング用プラグインを書いて使っていました。当初は頑張ってカーネルログを読んでいましたが，Wiresharkのおかげでましになりました。色分けされているだけでも分かりやすさが段違いですね。

Stack canary と .stack_sizes

カーネル開発の中で一番苦しんだバグが「カーネルスタックを使い切りスタックの先にあるスレッド構造体を部分的に破壊し，全く別のところでありえない動作を引き起こす」というバグでした。「何もしてないのに壊れた」状態でした。スタックは程よく余裕のあるサイズを割り当てたり，使い切ったらページフォルトが起きるようにしたりするものでしょうが，Reseaカーネルでは実装をできるだけシンプルにするためにケチって1ページ分（4KiB）しか割り当てないのです。

カーネルスタックの底にcanary値を書き込んでおいて時折その値が変わっていないか実行時にチェックしたり，間違ってスタックを大量消費しているコードが無いかをビルド時にチェック（.stack_sizes）したりすることでスタックを使い切るバグに気づけるようになりました。

Sanitizers

基本的にカーネルは何でもできるので，おかしい動作をしてもそのまま実行されてしまいます。Cで書くとなおさら色んなバグが隠れてしまいます。

そこで，未定義動作やdouble-freeのようなメモリ関連のバグを実行時に検出してくれるSanitizerというコンパイラの機能を使っていました。特に UBSan は何度も気づきにくいバグを教えてくれました。

まとめ

初めてHTTPサーバがさくらのクラウドで動いた時には筆舌に尽くしがたい感動がありました。作ったOSがインターネットの一員になったのです。

行数は空行やコメント行を含めて，カーネルが約5000行（コア部分は3000行），そしてユーザランドが約4500行になりました。 Unix互換性を提供しないことで，MINIXよりシンプルかつコンパクトで読みやすい物ができたと思っています。

次は「自作マイクロカーネルOS on 自作キーボード」をやってみたいですね。