The benefits and costs of writing a POSIX kernel in a high-level language

Citation

@inproceedings {222627,
author = {Cody Cutler and M. Frans Kaashoek and Robert T. Morris},
title = {The benefits and costs of writing a {POSIX} kernel in a high-level language},
booktitle = {13th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 18)},
year = {2018},
isbn = {978-1-939133-08-3},
address = {Carlsbad, CA},
pages = {89--105},
url = {https://www.usenix.org/conference/osdi18/presentation/cutler},
publisher = {{USENIX} Association},
month = oct,
}

どんなもの？

高級言語（Go）で POSIX カーネルを作る試み

「Biscuit」

目的のポイント

• Linux のような C で書かれたカーネルと同じような構成のカーネルを Go で書くことで、ガーベジコレクションに代表される Go の持つ高級な要素が、カーネル開発に有効なのか、パフォーマンスに与える影響はどのくらいなのかを評価する。
• ガーベジコレクションを持つ高級言語が実用的ならば、 Linux でよく報告されるバッファーオーバーフローや use-after-free といった脆弱性を防ぐことができる。

作成したカーネルの構成

• モノリシックな POSIX カーネル
  • つまり、最低限のシステムコールを実装している（Linux と完全互換ではない）。
• AHCI ディスクドライバー、 Ethernet NIC ドライバーを Go で実装
  • ディスク上のファイルへのアクセスと、ネットワークを使った実験ができる。
• できるだけ言語やランタイムに手を加えない
  • という目標だが、さすがにすべては無理なので、ランタイムの一部に変更を加え、ランタイムが依存するさらに低レイヤーな部分のために Shim 層を用意した。
  • C は一切使用せず、 Go とアセンブリのみ。

先行研究との比較

• 高級言語によるカーネル開発は、新しいアイディアを試すプロジェクトが多かった → 本論文でやりたいことは、よくある C で書かれたカーネルの構成を、高級言語で書き直してみること
• 同じく Go で書かれた似たような目的のプロジェクト Gopher OS があるが、まだ未成熟

この技術の重要なポイント

ヒープ枯渇を防ぐ試み

メモリが枯渇した状況でシステムコールが呼ばれたとき、そのシステムコールを実行するための十分なメモリが確保できないことがある。 Linux では、アロケーションに失敗し、さらにリトライできないような状況のときには、行った変更をすべて元に戻して、エラーコードを返す実装をしている。これはコードを複雑にし、実際元に戻す処理にバグが生まれやすい。

Biscuit では、システムコールに必要なヒープの容量を事前に予測し、不足しているときは、処理を実行する前に GC や Killer を走らせる。このようにすることで、変更を元に戻す処理が不要になり、また、一部のシステムコールを除いて、呼び出し側にアロケーション失敗としてエラーを返すこともない。

必要なヒープの容量を求めるために、 MAXLIVE という静的解析ツールを作成した。必要なヒープの容量とは、同じ時刻に生存しているオブジェクトが消費するメモリ量の保守的（最悪を想定する）な値である。 Go の中間表現を使って、ヒープアロケーションが発生する箇所を探し、そのオブジェクトがエスケープするかによって、同時刻に生存するかを判断する。スライス、マップについては、値を追加することで、内部で大きなオブジェクトを確保し直す処理が走る場合があることから、予測が困難なため、開発者がアノテーションを手書きした。複雑なループに対しても同様。

goroutine によるカーネルスレッド

カーネル内での並行処理は goroutine 任せで、かつユーザースペースのスレッドに対応する goroutine も作られる。割り込みについては、割り込み時に goroutine 切り替えのフラグを立てておき、 Go コンパイラが生成するプリエンプションコードが実行されたときに、実際にカーネルスレッドの切り替えが行われる。

ユーザースレッドの切り替えはどうやっているんだろう？

評価からわかること

• カーネル開発において、 Go の高級な機能は結構使える。（Figure 5）
• Linux の 2017 年における任意のコードが実行できる脆弱性 65 件のうち、40 件は Go を用いることで防げたバグと考えられる。
• Linux の 90% くらいの性能は出る。（Figure 9）
  • ただし nginx 相手に GC 遅延 582ms をたたき出すワーストケースもあった。

課題

• ヒープの断片化に対して対応できていない
  • オブジェクトのサイズごとに残りのヒープ容量を管理するようにしなければいけない
• ヒープの動的拡張をしたい
• goroutine のスケジューリングを既存の Go ランタイムに任せていてスケジューリングに自由度がないので、ランタイムを修正したい
• 必要なヒープ容量を先に計算しておく作戦は、 C で書かれたカーネルにも適用できるのではないか？