マイクロカーネルとL4について (Yabaitech.tokyo, Writing a (micro)kernel in Rust in 12 days より)
怒田さん*1のこの記事、「CとRustで一から作るマイクロカーネルOS」のおかげで、マイクロカーネルとRustが今ホットです。そこで、技術書典6, 7に出展したYabaitech.tokyoにて連載している、"Writing a (micro)kernel in Rust in 12 days"から、マイクロカーネルとL4についての話を書いた"1日目"の記事の一部冒頭を、いい機会なので再編集してご紹介します。「マイクロカーネルってタネンバウム教授とリーナスの論争のあれだよね?」とか、「L4ってなに?」って方に読んでいただいて、L4ファミリーとマイクロカーネルについて簡単にご紹介できればなと思います。
ちなみに抜粋元の上述の記事は、僕が怒田さんと同じようにRustでマイクロカーネルを書いてみよう、という趣旨の企画です。なので、Yabaitech.tokyoの方もよろしくお願いします!ただし、肝心の連載/実装の方は大して進んでいないので、僕のマイクロカーネル実装が気になったとしても、もう少し首を長くしてお待ちください。Yabaitech.tokyo自体には、粘菌を育てる話、Automata Inference, 新矛盾主義紹介などなど個性的な記事が多いので、ぜひぜひよろしくお願いします。*2
マイクロカーネルとL4
What is Microkernel?
早速だが、 マイクロカーネルとは何だろう?ひと段落で言えばだいたい次のようにな
る。
マイクロカーネル(英 : microkernel)とはオペレーティングシステムの設計思想、及びそのような OS のカーネル部の名称である。
OS が担う各種機能のうち、必要最小限のみをカーネル空間に残し、残りをユーザーレベルに移すことで全体の設計が簡素化でき、結果的にカスタマイズ性が向上し、性能も向上できるという OS の設計手法のことである。
カーネル本体が小規模な機能に限定されるので「マイクロカーネル」と呼ばれるが、必ずしも小さな OS を構成するとは限らない。
以上、Wikipedia 日本語版 からの引用だ。ちなみに、マイクロカーネルの対義語にあたる、普通のカーネルの呼び名はモノリシックカーネルという。Linuxカーネルはこのモノリシックカーネルの典型的な例だ。主なメリットはそのカスタマイズ性の高さと信頼性、堅牢性*3といったところなんだけれど、これだけじゃ何が何だかという感じだろうし、重要な特徴をかいつまんで説明していこう。
極小性
まず、重要なことは、さっきの引用にもあるように、カーネルには必要最小限の機能のみがあるということだ。 カーネル空間では、CPU の特権命令を発行する必要があるような、本当にプリミティブな機能だけが動く。そして、それ以上の機能は、ユーザー空間で動くプロセスが、そのプリミティブな機能をシステムコールとして使いながら実現していく。これらのユーザー空間のプロセスはマイクロカーネルの世界では、「サーバー」と呼ばれる。サーバーは一つであるとは限らず、複数のサーバーがIPCを通じて連携して動作するのがむしろ普通だ。
L4 カーネルを例にとれば、カーネル空間で動く機能はおおまかに次の 5 つだけとなる。
- スレッドプリミティブ
- スケジューリング
- メモリ空間の制御
- IPC
- 割り込み制御
もしかしたら、一見カーネル空間が担う機能としては普通のリストに見えるかもしれな
い。だから、普通の Linux や macOS のカーネル空間には存在しているけれど、このリストでは実は欠けているものをいくつか挙げてみよう。
まず、真っ先に気づきやすいのはデバイスドライバがリストにないことだ。マイクロカーネルアーキテクチャでは、デバイスドライバはユーザー空間で実現される。User space I/Oにあたるものがマイクロカーネルからデバイスドライバに提供され、デバイスドライバはユーザー空間にいながら特定のメモリ空間や IO ポートをたたくことでデバイス管理を実現する。これにより、マイクロカーネルではデバイスドライバがクラッシュしたとして、ほかのユーザー空間プロセスに影響を与えることはないわけだ。ファイルシステムもデバイスドライバと似たような方法でユーザー空間に移されている。
欠けているものその 2 として挙げたいのは、プロセス管理機構。一見すると、あれ、そ
れは (1) で実現されているんじゃ?と思うかもね。でも実はそういうわけじゃない。L4 でいうスレッドとは、レジスタの値とメモリ空間の組を保存したもの、くらいの意味合いしかない。これもそれだけ聞くと普通そんなものなんじゃ?と思ってしまうだろうから、モノリシックカーネルではプロセス管理のためにもっとどんな機能があるか思い出そう。
分かりやすいのはプロセスの起動だろう。execve システムコールは、POSIX OS でプロセスを起動するためのシステムコールだとざっくり言ってしまってもいいと思うが、*4 このシステムコールの第一引数は起動したい実行ファイルのパスだ。 例えば macOS では、 ここに Mach-O フォーマットのファイルへのパスが渡される。 すると、 カーネルは、 あたらしいスレッドプリミティブを作成し、MachOフォーマットをファイルからパースして、しかも用意したスレッドプリミティブのメモリ空間にそれを展開してくれるわけだ。
一方、L4 のシステムコールではそこまでやってくれない。そもそもファイルシステムはカーネルにないし、ファイルシステムを用意してあげたとして、Mach-O をパースするのはユーザー空間の役割だ。L4 のカーネルがやってくれるのは、単に空のメモリ空間と空のレジスタを持ったスケジュール可能なスレッドプリミティブを作ることだけ。それ以外のすべてはユーザー空間に実装されたサーバーの役割だ。 例えばプロセスが開いているファイルハンドルの管理、プロセスの実行ユーザーや実行グループの管理といった機能もすべて同様に L4 カーネルには欠けている。L4 のスレッドプリミティブを呼ぶだけでは、 普段私たちが親しんでいるプロセスらしいことは何も実現できないってわけだ。
このように色々な機能がユーザー空間のサーバーの役割とされて、カーネルは最小の機
能だけを実現することになっているのが、「マイクロカーネル」と呼ばれる理由だろう。これにより、カーネルのサイズはとても小さいものになる。それに、それぞれのサーバーはメモリ空間が分離されているから、一つ一つがクラッシュしても、その影響を最小限に抑えることができ、堅牢性も向上する。
OS パーソナリティ
じゃあ、 そんな最小限なカーネルを使ってしまったら、 いったいどうやって全体とし
て Linux みたいなオペレーティングシステムを実現するのだろう!一言でいえば、 そう
いうマイクロカーネルに足りない部分を全部やるサーバーを一つ作る、 というのが答え
になる。
L4カーネル自体よりも、普通のOSに必要なもろもろの機能を実現するこのサーバーこそ、ユーザーからすればむしろ"OS"と呼びたくなる部分だろう。そしてこのサーバー(群)は、"OS パーソナリティ"と呼ばれることがある。
OS パーソナリティサーバーが、ファイルシステムサーバーやデバイスドライバサーバーを IPC を通して制御し、 POSIX の fork や read, write のような、ユーザーアプリケーションから見えるシステムコールを実装する。そういったサーバー群が協調して、全体として一つのオペレーティングシステムを実現する、 というのがマイクロカーネルベースのオペレーティングシステムの一つの形だ。仮にLinuxの機能を実現したOSパーソナリティがあったとすると、ユーザーアプリケーションがexecveを呼びたければ、L4カーネルのシステムコールをたたくのではなく、このOSパーソナリティに対して、IPCを通じてexecveを要求することになる。
マイクロカーネルの面白いところは、このパーソナリティサーバーを取り換えることで
同じマイクロカーネルでも違うオペレーティングシステムを実現できることだ。L4 の上で Linux パーソナリティを走らせれば、Linux のアプリケーションが動くし、(仮にあるとすればだが)macOS パーソナリティを走らせれば macOS のアプリケーションが動く。 おまけにパーソナリティはユーザー空間のサーバーだから、同時にいくつも並行して走らせることができる。*5マイクロカーネルとパーソナリティの試みは、面白い具体例が色々ある。Fiasco.OC L4 カーネル上で Linux が動く L4 Linux。 これは今も開発が活発に続いている。 何しろ Fiasco.OC は商用 L4 マイクロカーネルだ。 過去の例でいえば、Minixが L4Ka 上で動く Minix/L4、Mach カーネル上で Linux が動く MkLinux、 それに同じく Mach 上で動く OS である GNU Hurd. 他にも色々あるから、探してみるのもいいんじゃないだろうか。このようなOS全体の機能のカスタマイズ性の高さも、マイクロカーネルのメリットの一つだ。
そして、この面白い特徴から、一度あるマイクロカーネルの互換カーネルを作ってしまえば、その上でそのマイクロカーネル用の OS パーソナリティやサーバー群が動くことになる!これが Introduction で説明した自作カーネルを既存のマイクロカーネルの仕様に準拠させるモチベーションの一つだ。*6
L4 Microkernel
さて、これでマイクロカーネルの一般的な概念の紹介はおしまいだ。まぁ大事なのは、 マイクロカーネルは小さな機能だけで構成されていること。 それに、 通常のオペレーティングシステムとしての機能は、マイクロカーネルの上で動く OS パーソナリティで実現されることだ。 この節からは、L4 マイクロカーネルについての話を始めよう。
L4 は、先ほど説明したマイクロカーネルアーキテクチャに基づくマイクロカーネルの
一つだ。L4 と呼ばれるマイクロカーネル実装は複数あるから、きちんと呼ぶなら「L4 マイクロカーネルファミリー」になる。このファミリーというのは、だいたい「Windowsファミリー」と同じくらいの感覚だ。Windows には 95 系と NT 系があるわけだけど、どちらも Windows カーネルと呼ばれるし、それぞれでもバージョン毎にだいぶ違いがある。つまり、 ファミリーとは一つの実装を指しているわけではなく、 共通の系譜を継いだお仲間たちだというわけだね。
そして、L4 マイクロカーネルファミリーの系譜のおおよその起源は、Jochen Liedtke 先生による 1993 年の、ずばり「L4」だ。*7*8 L4 を起源とする L4 ファミリーの系譜の図を Wikipedia から上に引用した。論文"From L3 to seL4 - What Have We Learnt in 20 Years of L4 Microkernels?"*9は、L4 の重要な概念がよくまとまっているうえに、この系譜図上の L4 から seL4 にいたるまでに L4 ファミリーが解決してきた問題や、設計の変遷をまとめたとても良い読み物だ。L4 についてより詳しい資料を読みたくなったら初めにこれを参照してほしい。
他の L4 の重要な情報源といえばずばり公式サイトである http://l4hq.org *10だ。各種 L4 のドキュメントや仕様がまとめられているので、こちらも初めに参照してほしい。
マイクロカーネルとパフォーマンス - L4 の革命
L4 の開発がはじめられたモチベーションは、マイクロカーネルが抱えていた大きな問
題の解決にあった。その問題とは、パフォーマンスの悪さだ。マイクロカーネルは、そ
の設計上 IPC がボトルネックになりやすいということがよく議論にあがる。マイクロカーネルでは、システムコールがサーバー間の複数の IPC で実装され、そして IPC はコンテキストスイッチを伴う。 一方、 モノリシックカーネルのシステムコールは通常 1 回のコンテキストスイッチで済むから、比較するとマイクロカーネルではシステムコールのコストが割高になってしまう。
L4 は、Liedtke がこの問題を緩和するために開発した、画期的なマイクロカーネルだっ
た。先ほど名前だけ少し出た、Machというマイクロカーネルでは、IPC のコストが顕著だった。*11この Mach は L4 の文脈では、「第 1 世代マイクロカーネル」として言及される。もちろん、L4 が第 2 世代だという流れでだけど。
Liedtke は、L4 で極小性をキーコンセプトとしてマイクロカーネルをデザインしなおした。IPC の機構は Mach に比べて極端に単純になり、メッセージサイズも小さくなり CPU のキャッシュになるべくすべてのメッセージが載るように設計した。スケジューリングなども単純化され、さらにはカーネルすべてをアセンブリで書いてしまうというものすごい執念でありうる極小のマイクロカーネルを完成させた。結果はどうなったと思う?なんと IPC は Mach に比べて 20 倍も高速化したのだ! *12ちなみに、 のちに L4 カーネルは C や C++ で書き直されたが、 パフォーマンスは悪化しなかったので安心してほしい。さらに後続の研究では、Linux パーソナリティが L4 上で実装され、 本物の Linux カーネルに比べても数パーセントのオーバーヘッドしか発生しないことが示された。*13もっとも、この実装では、LinuxパーソナリティにFSもデバイスドライバも組み込まれていることで、IPCのコストが抑えられていることには注意してほしい。*14
なにはともあれ、こうして L4 により、マイクロカーネルは実用的なオーバーヘッドで実現できるということが示されたのだ。
マイクロカーネルの逆襲
L4 の登場以降、マイクロカーネルは様々な方向に発展している。MINIX のタネンバウ
ム教授が 2016 年に"Lessons learned from 30 years of Minix"で述べているように、L4 ベースのマイクロカーネルはほとんどあらゆる iPhone のセキュリティチップで動いているし、QNX は色々な組み込み機器で実用化されている。 こいういう機器では、 少々の性能のオーバーヘッドよりも信頼性が重要だからだ。*15 そのタネンバウム先生の MINIX 自身も、実は世界中の Intel x86 CPU で動いていたという事実が最近判明した。*16
マイクロカーネルの発展は実用化方面だけではない。一番クールなプロダクトはやはり
seL4 だろう。*17 seL4 は、マイクロカーネルのコードサイズが小さいことを利用して、その正当性を Isabelle で証明したおそらく世界で唯一のカーネルだ。メモリ安全性といった一般的な性質や、ポートベースのポリシーシステムが決して違反されないことなどを数学的に証明している。*18
しかも seL4 はその仕様設計自体もかなりシンプルで良い感じだ。実際、今回実装する仕様の対象として seL4 はかなり有力な候補だった。しかし、仕様の大きさの問題でこの記事では seL4 を選ばなかった。 また、seL4 の仕様とそれ以前の L4ファミリーの共通点はほとんどないことも注意事項かもしれない。思想上の家族、といったところなのかもね。*19
普段 x86 Linux の世界でだけ生きていると、1992 年、つまり L4 発表の前年のリーナスとタネンバウム先生の論争からマイクロカーネルの時は止まっているかのように思えてしまうものだ。しかし、 マイクロカーネルのパフォーマンスは、モノリシックカーネルに比べれば見劣りこそするかもしれないが、L4 以降大幅に改善した。実用化という面では、QNX, MINIX, L4 の数を足してみれば、もしかすると実は Linux よりも多くの数のマイクロカーネルが世界では動いている可能性すらある。証明済みカーネルというユニークな成果も、マイクロカーネルでなければ不可能だったものだ。あまり大きくは知られていないけれど、マイクロカーネルの世界はどんどん発展していて、いつの間にか逆襲を果たしていたというわけかもしれない。
(おまけ) 自作OSとマイクロカーネルの相性、またL4 X.2. Standardについて
抜粋元のYabaitech.tokyoの記事は、マイクロカーネルの解説本ではなくて、Rustでマイクロカーネルを作ろうという記事でした。自作OSにはマイクロカーネルはピッタリなのでは?という話と、L4には「規格」があって開発しやすいという話を引用して終わりにします。
Rust 言語は、2019 年の今最も注目されているプログラミング言語の一つで、 低レイヤーの分野においては、特にモダンな言語機能を一通りそろっていることによる快適性と、所有権という新しい概念による GC に頼らないメモリ安全性から注目されている。(C 言語でのメモリ関連のデバッグの苦労を思い出せ!) コミュニティ全体で、システムレイヤ ―での応用を考慮しながら開発が進められているのも魅力的なポイントだ。だから、2019 年にカーネルを書く際に Rust でやってみようと思うのは全く奇妙なことではないだろう。*20一方カーネルは、 知っての通り、オペレーティングシステムの中核コンポーネントだ。CPU のもっとも権限の高い空間で動作し、コンピュータのすべてを管理しなければならない。それを 0 から自分で書くというのはとても面白い体験だと思う。プログラマーの「3 大作ってみたいもの」によくあがる、コンパイラ・ CPU・オペレーティングシステムのまさに 3 つ目にもあたることだし。*21 そして今回書くカーネルはただのカーネルではなくマイクロカーネルだ。
今回マイクロカーネルを選んだ大きな理由は二つある。一つは、マイクロカーネルはサイズがとても小さいということ。実用レベルの OS である Redox でも、マイクロカーネル部分のコードは 1 万行未満だ。Linux カーネルのような巨大なモノリシックカーネルを自作してみようというのは途方もない話だが、マイクロカーネルならば短い期間でゼロからでも完成させることができるはずだ。実は去年ついに大学院を卒業して会社員になってしまい、無事に自由時間が今までの 7 分の 2 に減ってしまった。だから短い期間で完成させたいというのは結構切実な願いで、そのために作るカーネルとしてマイクロカーネルを選んだのは自然なことだったわけだ。
そして、もう一つの理由は、L4 マイクロカーネルファミリーという有名なマイクロカーネルの仕様が存在すること。実装するべき完成図がはっきりしているから学びながら開発していくのに都合がいいし、しかも無事仕様をみたせたときには自作したカーネルのうえで、既存のユーザーランドアプリケーションが動作することになる。OS を自作するとき、こんなに嬉しいことはないだろう!小さな労力でこれを達成したら、あとはサーバーなどの自分のユーザーランドをインクリメンタルに開発してゆくことも可能だ。L4 マイクロカーネルは実世界で使われた実績もあってまだ活発に開発・研究がされている。そして今回扱う L4 X.2 Standard のいいところは、何と言ったってシステムコールが 12 個しかないことだ。そう聞いたらなおさら短期間で作れそうな気がしてこないだろうか?仕様があるってことに加えて、 しかもその仕様が小さいわけだ。 色々と説明したけれど、 つまりはマイクロカーネルは自作をするにはピッタリだってこと!
L4 X.2 Standard
さて、 前の節の話でなんとなく分かるように、L4 と一言で言ってみてもまぁ色々な実
装があるわけだ。 じゃあ今回何を作ろうかと考えて決めた結論は、 系譜図のど真ん中あたりに陣取っている Pistachio だ。 Pistachio を選んだ理由は、一言でいって、短期間で自作するのにぴったりだから、だ。系譜図で紹介したように、L4 にはたくさん実装があるのだけれど、そのうちいくつかの実装は、「L4 マイクロカーネルの標準仕様」 に準拠して実装されている。マイクロカーネルの仕様、といわれてもピンとこないかもしれないが、 要は POSIX と似たようなもので、 カーネルが実装しているシステムコール、 そのシステムコールの呼び出し ABI などが定義されている。 割り込みが起きたときにどのようなプロトコルで処理が走るべきか、なんかも定義されているのは少しカーネルらしいところかもしれない。そして、Pistachio は、きちんと定義された最後の仕様といっていい、L4 X.2 Standard というものに準拠している実装なのだ。
L4 X.2 Standard はシステムコールが 12 個しかないというとても小さい仕様になっていて、準拠したマイクロカーネルを実装しやすい。ちなみにこの記事*22が 12 日でカーネルを作る、と言い張っているのはこのAPI が 12 個しかない、 ということを根拠にしている。 X.2 以降のおおよそ似たような L4 ファミリーといえば OKL4 と Fiasco.OC になるのだが、これらはどちらも実用的なマイクロカーネルとなっていて、アカデミアの世界で完結している X.2 に比べ実装されている API がとても多く、互換カーネルを作るのが困難だ。それにそもそもこれらのカーネルは、 もはやきちんと定義された仕様が存在しない。 一方 seL4 は、 実用性も兼ねているにもかかわらずきちんと定義された仕様が存在するのだが、 やはり X.2 に比べるとだいぶ大きな仕様になってしまっている。そんなわけで、最後の実質的な更新は 2010 年頃と少し古いけれど、互換カーネルを自作するのにピッタリの対象としては、X.2、それにPistachio が選ばれたというわけ。
さて、L4 の X.2 Standard について簡単にだけ触れておこう。 そもそも L4 の仕様とい
うときは、だいたい API と ABI の仕様を決めていると思ってくれていい。L4 X.2 では 12個のシステムコール (API) と、それらを呼び出す際の ABI が決められている。そのシステムコールとは、次のものだ。
- KERNELINTERFACE
- EXCHANGEREGISTERS
- THREADCONTROL
- SYSTEMCLOCK
- THREADSWITCH
- SCHEDULE
- IPC
- LIPC
- UNMAP
- SPACECONTROL
- PROCESSORCONTROL
- MEMORYCONTROL
冗談抜きでこれで全部だ。 実にシンプルで小さい仕様だ。ファイルフォーマットが ELF であること、みたいな仕様の範疇を越えることもあるから完全に互換ではないが、 気を付ければ同じユーザーアプリケーションを動かすことは実現できる。 それぞれのシステムコールが何をするものなのかはおおよそ名前から推測できると思う。 これらの詳しい仕様の資料は、http://www.l4ka.org/l4ka/l4-x2-r7.pdf から入手できる。この12個のシステムコールさえ実装すれば、自作のマイクロカーネルも、おおよそ Pistachio と互換のものになるだろう。そしてそうすれば、Pistachio用に書いたユーザーランドが、自作カーネルで動くことになる。そしてそれが、今回のモチベーションだ。*23
*1:ちなみになんですが、怒田さん2016年度の未踏同期の方です。
*2:Boothでこの記事のフル版も含め過去の3冊が買えますよ。
*4:おっと、顔をしかめないでほしい。 fork や exec の話は今は本質じゃないから先に進もう。
*5:まるでハイパーバイザみたいな話だが、実際マイクロカーネルは現代の仮想化機構と共通点が多い。
*6:Yabaitech.tokyo本誌ではこの章の前にIntroductionがあります。
*7:Jochen Liedtke. Improving IPC by kernel design. 14th ACM Symposium on OperatingSystem Principles, pages 175–188, 1993.
*8:L3 という L4 の前身のカーネルもある。そして正確にはそちらが起源なのだが、説明を簡単にするため L4 から始めたい。
*9:Kevin Elphinstone and Gernot Heiser. From L3 to seL4 What Have We Learnt in 20 Years of L4 Microkernels?. SOSP’13, pages 0–0, 1993
*10:2019/12/15日現在、どうやらサイトが落ちているようでうす。ひとまずGoogleのキャッシュなどからご覧ください。
*11:Mach は Minix と並んでもっとも著名なマイクロカーネルの一つだろう。現在の macOS の XNUカーネルの源流でもある。
*13:前出、"From L3 to seL4 What Have We Learnt in 20 Years of L4 Microkernels?"より
*15:Tanenbaum Andrew S. Lessons Learned from 30 Years of MINIX. Commun. ACM, 59, pages 70–78, 2016.
*16:NETWORK WORLD. What is MINIX? The most popular OS in the world, thanks to Intel. https://www.networkworld.com/article/3236064/minix-the-mostpopular-os-in-the-world-thanks-to-intel.html, 2017
*17:Data61/CSIRO. The seL4 Microkernel. https://sel4.systems/, 2016.
*18:Data61/CSIRO. The Proof. http://sel4.systems/Info/FAQ/proof.pml, 2016.
*19:seL4のライセンスはGPL v2なのですが、ユーザーランドのネットワークドライバやファイルシステムはBSDライセンスなのもポイントとsuzaki先生からコメントをいただきました. https://twitter.com/KuniSuzaki/status/1206186021257302017
*20:怒田さんは、カーネル部分を5回くらい書き直した結果、RustよりもCの方がマイクロカーネルには向いていそうだ、と結論付けています。とても興味深い結果ですね。僕の方もやってみて、Rustでマイクロカーネルを書いた感想がいつか書けたらいいなぁと思っています。
*21:ほんとか?
*22:引用元の元の記事
*23:実際は現存してきちんと動くPistachio用のユーザーランドはほぼ皆無なのですが、Pistachioの資産を用いてテストがしやすいという意味ではやはりアリでしょう。