論文紹介：The benefits and costs of writing a POSIX kernel in a high-level language

元論文: https://www.usenix.org/conference/osdi18/presentation/cutler

Go言語でPOSIXインターフェースを備えたカーネルを実装し、その利点と欠点を比較してみた、という論文です。

論文概要

  • タイトル：The benefits and costs of writing a POSIX kernel in a high-level language
  • 著者：Cody Cutler, M. Frans Kaashoek, and Robert T. Morris (MIT CSAIL)
  • 会議：13th USENIX Symposium on Operating Systems Design and Implementation (OSDI ‘18)

去年のUSENIX OSDIで発表された論文です。USENIXはハイレベルな低レイヤー関連の会議が多く、かつ論文をオープンアクセスで提供してくれるのはアカデミアから離れた身としてはうれしい限りです。

背景

著名なOSのカーネルはC言語で書かれている。C言語は直接メモリを操作したり、デバイスのレジスタを操作したりできる。また、ランタイムを介さないためパフォーマンスも高い。一方、安全なコードを書くことが難しく、バッファーオーバーフローやuse-after-freeのようなバグの温床ともなりうる。
Go言語などの高級言語は、型検査やメモリの安全性がC言語よりも強く保証されるものの、多くの場合はランタイムを介しての実行となり、ガベージコレクション（GC)に頼るため、パフォーマンスへの懸念が生じる。
そこで彼らはBiscuitと名付けたPOSIXのサブセットを備えたカーネルをx86_64プロセッサ用に実装し、評価を行った。

この論文はカーネルの実装にC言語が用いられるべきか、高級言語が用いられるか、という主張をするものではなく、あくまで高級言語を用いた実装がどのようなものかという指標を提供するものだと著者らは位置づけている

実装

Go言語とアセンブラのみで書かれていて、C言語は全く用いていない。
Biscuitを動かすにはGo言語を動かすためのランタイムが必要で、通常であればランタイムはカーネルの機能を呼び出す。
今回は呼び出すカーネルがないので、代わりの機能を提供するShimというレイヤーを用意している。
Goのランタイムは標準のものにGCのタイミングを調整するなどの変更を加えたものを使用している。

割り込み対応、マルチプロセス、ファイルシステム、ネットワークスタックなどPOSIXのカーネルなら備えている機能はおおよそされている。

GCとヒープ枯渇問題

Goはmark-and-sweep方式のGCを持っていて、確保していたメモリがある程度使われるとヒープ領域を適宜拡大していくということをしている。
Biscuitではこの通常のヒープ領域拡大を無効化して独自のタイミングでヒープ枯渇問題を回避している。
ヒープ領域が足りなくなったとき、Biscuitは

  1. キャッシュやソフトステイトのような保持する必要のないものを解放する
  2. システムコールが消費するであろうヒープ領域のサイズをあらかじめ確保しておく
  3. キラースレッドにより異常にヒープ領域を消費しているプロセスを殺す
    ということをしている

システムコールの消費するヒープの量を計算するためにMAXLIVEというツールを開発し、静的解析により事前に必要なヒープの量を計算している。
コールグラフからアロケーションの量を計算していくのが基本だが、ループによる繰り返し処理がからんでくるとアノテーションをつけることでヒントを与えたり、例外的な処理をして回避したりしている。

評価

この研究では高級言語をカーネルの実装に用いることでの利点・欠点を具体化するのが目的なので、評価軸もそれに沿ったものになっている。

まずそもそも高級言語の機能がどれくらい用いられているのか、というのを他のGoで書かれたソフトウェアとの比較を行っている。
GoのコンパイラとMoby（Dockerがつくったコンテナを用いたシステムのフレームワーク）と比較して同じくらいだとしている。
GCで管理されるオブジェクトが有用な場面とそうでない場面もある、と具体例も上げている。
有用な例としてはpollのシステムコールでは入力待ちのスレッドを起こすためのヘルパーオブジェクトのを挿入するが、そのヘルパーオブジェクトのフリーのタイミングを気にしなくても競合が起きないことをあげている。
一方、TCPのコネクションオブジェクトはTCPのシャットダウンプロトコルを実行することが必要だが、Goのfinalizerではオブジェクト間の循環ができないためそのままでは難しいので、そのようなオブジェクトに対してはBiscuit自身が参照カウントを管理している。
また、LinuxのCVEを参照し、Use-after-freeやOut-of-boundsなどのGoでは脆弱性になりえないものとそうでないものを分類している。65個の深刻な脆弱性のうち40個はGoなら防げるとしている。
一方、Goのランタイムやパッケージ自体にも14のCVEが報告されて、うち4つはカーネルにとって深刻な脆弱性になりうるとしている。

アプリケーションベンチマークとしては、CMailbench（メールサーバーをモデルとしたforkとexecにより仮想メモリシステムへのストレス試験）、NGINX、Redisを実際に動かし、Linuxとの比較、ヒープサイズと使用メモリ割合に対するパフォーマンスなどの実験を行っている。

関連研究

カーネルの実装に高級言語を用いる例は様々ある。以前ここでも紹介したRust製カーネルのTockも一例として挙げられている。
しかし、これらの研究はC言語との比較というよりも、新しいコンセプトのOSということに重きを置いている。
カーネル用に既存の言語を改変して用いるというものもあるが、この研究ではGoそのものに大きな変更は加えないようにしている。

まとめ

Go言語を用いてBiscuitと名付けたPOSIXカーネルを実装し、C言語を用いた場合との比較を行った。
高級言語のもたらすパフォーマンス低下は15％を下回るとした一方、だからといってGoを使うべきだと結論づけてはいない。
しかし、Go言語でカーネルを実装する際の恩恵やコストを明らかにし、Goのような高級言語を使うべきか否かの判断材料になるであろうとしている