Fault Detection in Multi-Threaded C++ Server Applications

http://valgrind.org/docs/muehlenfeld2006.pdf

を読みました。 helgrind をちょっとよくしたよ、って人が書いた論文、だと思います。

先に結論書いておくと、わりとがっかりな感じでした。 race detector がどう動いてるかわかったのは収穫ですが、もうちょい効率の良い方法はあっただろうという気がする…

1. intro

ハードウェアは進歩しているとかなんとか CPU は数増やすしかないとかなんとか

静的にモデルチェックするのはすぐに組み合わせが指数爆発する。あと C++ に関してはまともな使いやすいパーサが無い。

ランタイムにやるのはスケールする。 Eraser っていうアルゴリズムが知られていて、 false positive すごい多くてめんどくさい。

Eraser の説明はこことか? http://www.cs.washington.edu/homes/tom/pubs/eraser.pdf

false positive に強くするには、静的解析をして自動で annotation をつけてからランタイムでやればいい。

この論文では Eraser より二つの点で進化している。 1つ目はハードウェアの挙動をよりよくシミュレートするようになったこと。 2つ目は C++ 特有のなんかに対処したので、 false positive が減ったこと。 65% から 81% くらいの false positive が消せたそうな。

2 fault detection

2.1 definitions

deadlock と race があります。 race は 1 つのデータを複数スレッドでいじることです。この定義はやや狭義なもので、高レベルな race は含めてないです。高レベルな race ってのは一個一個の data はきちんとロックされてるけど、複数の data がアプリレベルで inconsistent な状態になること。

あとロックは時間かかるのでそれも問題になることがあります。

2.2 Dynamic Methods

だいたいの動的な方法は lock-set algorithm Eraser か Lamport's happen-before relation に基づいている、らしい。

lock-set algorithm を使ったものとしては DJIT ってのが helgrind 以前にあって、それは実行環境に依存してて、最初の一個の明らかな race だけ detect できたらしい。 lock-set algorithm のいいところは実行パス中の race が全部検出できること。でも山ほど false positive が出ちゃうと。 DJIT は明らかなものしか報告しないので、 race を適当に見逃しちゃう。 Multi-Race ってのはそれをややよくしたものらしい。

lock-set と happens-before を Java の synchronization に対してあわせてみた人がいるけど、彼らの仮定は全ての SMP 環境で正しいとは言えない。

まあ実行時にやるやりかたは実行を遅くするのが残念。適当にログ残しておいて後で必要なとこだけ解析するやり方もあるけど、データを大量に残さないといけない。とはいえよくスケールする。実行されてないパスはチェックできないけど、まぁ実際使われている。そんなツールの一つが helgrind ですよ、と。

2.3 Runtime Analysis with Helgrind

2.3.1 The tools

Helgrind の紹介。 Eraser algorithm に Visual Threads という改善によって false positive を減らしたもの。

Valgrind の紹介。 well known な false positive には suppression を書けますよ、とか。

2.3.2 Basic Algorithm (Eraser)

基本的なアルゴリズムは、全 lock を set として全ての共有されてるメモリに関して作っておいて、実際にアクセスされた時に保持されている lock 群との and を取っていって、最後に空集合になってたら warning を出す、とかいう。これだとアホほど false positive が出ます。

特にうっとうしいのは最初に初期化して後は read してるだけだから lock いらない場合。というわけで一つのスレッドが触ってるうちは lock-set を初期化しないでおいて、他のスレッドが触ってはじめて lock-set を初期化して、後は普通に書き込みのたびに lock-set に and を取っていくみたいな。

read-write lock (たぶん pthread_rwlock のことだろう) に対する拡張は helgrind には実装されてない。アルゴリズムは read の時は r/w 両方の lock に対して set の and を取っていって、 write の時は writer lock の方だけに set の and を取っていって、空集合になったらアウト、って感じでいいらしい。

Thread Segments

他の false positive としては、最初に main thread がデータを初期化して、起動した thread がそのデータをいじくって、で main thread は join してその thread を待って完成したデータをいじる、みたいなケース。なるほど。

で、これを防ぐアルゴリズムの説明が…むずかしい。要は最初のスレッドじゃないスレッドが2回目のアクセスをした場合、その2つ目のスレッドが最初のスレッドに作られた場合は、 lock-set を初期化せずに2つ目のスレッドに所有権的なものを移動するとか言ってるのだと思う。たぶん join したら権利委譲が起きる、とかも無いとダメだと思うんだけど、どうも説明されてないというか、ちゃんと読めてないか。図2はまったく意味わからん。

3.1 Improvements

まずバグフィックスをしました。 intel の lock prefix は rwlock みたいなもんで mutex ぽい実装されてた helgrind はおかしい。

2個目はデストラクタ内でのメモリ操作で、デストラクタ内で race ってのはありえんにも関わらず false alarm が出てしまう、って話だと思う。どうも vtable がどうこう言っててよくわからない。 vtable への参照を親クラスのデストラクタでいじるとかなんとか書いてあると思うんだけど、はてそんなことするもんだっけか…という。

でまあこの論文の作者のツールはそういうデストラクタ内でのメモリ参照に自動で valgrind のアノテートをつけるらしい。これはちょうかんたんだったと書いてある。まあそうだろう。

3.2 Debugging Process

先の話もあって、プログラムのコンパイル時に自動で annotate をつけないといけなくて、あと、 helgrind が終わってからどれが false positive かなーと調べました、と。

Setup and Environment

SIP のプロキシサーバに対して実験したと。 request-per-thread なモデルなので、 thread segments のとこでやった改善がよく効くとかなんとか。

annotate には、 ELSA っていう C++ パーサがあるらしくて、それを使ったそうな。 http://scottmcpeak.com/elkhound/sources/elsa/

ELSA は preprocess されたコードじゃないと処理できないから、 g++ で preprocess => annotate => g++ って感じになって、ちょっとコンパイル遅くなるとかなんとか。

helgrind のせいで遅くなるから、タイムアウトの処理とかはちょっと変えないといけなかった。

4 RESULTS

はい lock prefix のバグとデストラクタへの annotation でずいぶん false positive が減りました。めでたしめでたし。

libstdc++ のコンテナの allocator は、デフォルトでは使い終わったメモリを使いまわすので、データに連続性が無いのにあるように見えちゃって false positive が出るケースがありました。 libstdc++ はそのへんのポリシーを環境変数でいじれるのでラッキーでした、とのこと。 GLIBCXX_FORCE_NEW ってヤツですかね。

4.1 True Positives

あんまり面白くない race の例が並んでますね…

4.2 False Positives

4.2.1 Destructor of Derived Classes

コピペですよ…他の章と全く同じパラグラフが2つある。そしてこの2パラグラフは意味がよくわからん vtable がどうこうってやつ…

4.2.2 Hardware Bus Lock

intel の lock prefix の話。それが治ったのはもう聞いたからもう書かなくていいです!

4.2.3 Transition of Ownership

thread segments のとこに出てきた、 thread 作ると作られた thread の方に所有がうつるみたいな処置だと、 thread pool みたいに最初に thread たくさん作っておいて、でも権限の委譲はしょっちゅう起きるようなケースに対処できませーん、って話。 thread segments のとこ読んでて当然の疑問として思ったことなので、ああやっぱダメなのね…という。

4.3 False Negatives

楽しそうなタイトルの章です。でも語られるのは一般論だけで実例はナシ!

例えば、一つのスレッドだけが触ってるうちは lock-set を初期化しない、ってヤツだけど、アレをやると、本当は lock が必要なのにしてない A と lock してる B が、 A=>B って順でアクセスした場合に warning を出せなくなっちゃいます。オリジナルの Eraser は A=>B の順でアクセスが起きた場合も detect できるんですけどね、という。

いや、それはそうなんだが、 RESULTS のとこで語るべき話題じゃないだろう…と思ったら、最後のとこに、実際実験してる間にこのケース見つけたよ、とか書いてあった。