最初の記事は何にしようかなーと思ってたんですけど、Twitter でたまたまいつか読もうと思っていた論文の解説を求めているツイート（これ と これ）を目にしたので論文紹介をしてみようと思います。

情報

この論文は USENIX ATC (Annual Technical Conference) という OS の準トップ国際会議で 2017 年に発表されました。著者は主に Mozilla の方々です。論文は こちら、発表スライドは こちら にあるので興味のある方はご覧ください（アカデミアの方が作るスライドとはちょっと趣が違いますね）。ちなみに論文の extended version が arXiv にあります。

概要

プログラム実行を記録して再生（record-and-replay）できるシステムがあると、例えば再現が難しいバグのデバッグなどの役に立つため嬉しいです（性能オーバーヘッドが小さいとなお良いです）。そういうシステムを実現する手法は色々と提案されているのですが、既存手法はデプロイが容易ではないという大きな問題があります。例えば仮想マシン上での記録（重たい）、カーネル／コンパイラや言語のランタイム／ハードウェアへの変更などが必要だったりします。そこで、デプロイが容易なユーザレベルの record-and-replay システムである RR を開発しました（プロジェクトのウェブページは こちら）。この論文では RR のデザインや性能最適化などについて解説しています。

デザイン

そもそもどういう情報を記録したら実行を「巻き戻して」再生できるのでしょうか？全ての事象を記録しようとすると（事象とは何か、またどうやって実現するか、はさておき）当然ながら容量も性能オーバーヘッドも大変なことになるでしょう。そのため一部の事象を記録して一部は再実行することで再生を実現するのが良さそうです。プログラム実行が全て deterministic（決定的。例えば加算命令は入力が同じなら出力は常に同じなので決定的です）であるならばそもそも難しいことはありません。ただ実際には nondeterministic（非決定的）な要素があるので（例えば RDTSC は実行する度に結果が変わってしまいます）、そういった事象については記録する必要がありそうです。

そこでプログラム実行を適当に区切っていき、区切りの中の全ての非決定的な事象と区切りへの入力を記録します。再生時には、これらの記録を再生した上で残りを再実行します。理屈の上ではこれで記録時と再生時の挙動が一致するはずです。RR ではこの「区切り」をプログラムがユーザ空間とカーネル空間を行き来する時点とします。記録すべき事象と入力は主に非同期イベントのタイミングとシステムコールの結果になります。

論文では以下のデザインについて述べられています。マルチスレッドプログラムにおけるデータ競合、システムコール、非同期イベント（コンテキストスイッチやシグナル）、共有メモリ、非決定的な命令（前述の RDTSC など）、トレースサイズの縮小。次の性能最適化に関連するのでシステムコールだけ簡単に説明します。システムコールによるメモリやレジスタへの変更を記録するため RR はシステムコールをトラップして ptrace システムコールを用いてこれらの変更を記録します（再生時にはシステムコールを実行せず、記録した状態を反映させる）。その他については論文を参照ください。

性能最適化

さて、上記の実装ではシステムコールによる変更の記録が大きな性能オーバーヘッドを引き起こします。記録対象のプログラムがシステムコールを呼ぶたびに 4 回もコンテキストスイッチが生じるためです（システムコール前と後に RR を呼んで戻るため）。そこでシンプルでよく呼ばれるシステムコールに関してはそれをユーザ空間内でトラップして解析するライブラリを噛ませることでコンテキストスイッチを避けてこのオーバーヘッドを削減します。このコンセプト自体はシンプルですが、実装はかなり大変です。

普通に考えたら C のライブラリ関数をラップするライブラリを用意してプリロードすれば良さそうですが、以下の理由から不十分です。プログラムが直接システムコールを呼ぶ。C のライブラリ関数自体にバリエーションがある。対象プログラム自身が他のライブラリをプリロードする必要がある。とのことです。

ということでどうするかというと RR はシステムコールをトラップしたらシステムコールでなく RR のライブラリを呼ぶように対象プログラムを書き換えます（以降はトラップの必要がなくなる）。全てのシステムコールに関して自前のルーチンを用意するのではなく（for simplicity、とのことです）限られたシステムコールに関してのみ書き換えを行ないます。この目的のため seccomp-bpf という BPF のフィルタを用います。その他にもブロックするシステムコールへの対応（デッドロックを避ける必要がある）、システムコールをトラップしている最中に起こるコンテキスイッチへの対応、などなど非常に大変なエンジニアリングが必要なことが窺えます（arXiv 版を参照ください）。この努力の結果性能が使い物になるということです。

性能

ざっくりですが、記録と再生のどちらもオーバーヘッドは 2 倍以下に収まることが多いように見えます。メモリオーバーヘッドに関しては現実的には無視できる程度のようです。

感想

どちらかというと実装力！という論文だとは思いますが実際にすでに大きなインパクトを与えているソフトウェアなので言うことはあまりない気もします。非常に良い仕事だと思います。