ロンドン大学カレッジとFacebookの研究者らが共同研究により、AndroidのJavaコード用のデッドロック検出ツール(deadlock detector)を新たに開発し、オープンソースの静的解析ツールであるInferの一部として公開した。この新しいアナライザは、CIパイプラインに統合するために特別に設計されたインクリメンタルなアプローチにより、大規模なコードベースを効率的に処理することができる。
研究成果を説明した論文の中で研究者らは、今回のデッドロック解析ツールの中核となるアルゴリズムが指数的(NP)時間で実行されることを示している。
解析の第1ステップは、抽象的な言語を用いて実際のコードをモデリングする作業である。この抽象言語はJavaを単純化したモデルと言えるもので、入れ子、再入ロック、非決定的な反復処理と分岐、非再帰的手続き呼び出しをサポートしている。変数やメモリ割り当てなど、その他の詳細な言語機能はモデリングされない。
アナライザは各メソッドに対して、ロックの取得と解放に関するメソッド動作の概要と、そのメソッドがメインスレッドとバックグラウンドスレッドのどちらで実行されるのかを算出する。
メソッドの概要の中には、メソッドが取得を試みるすべてのロックと、同時に保持するすべてのロックが一覧として含まれる。このデータに基いて、A、Bという2つのロックを行うクリティカルペア(A,B)のリストが生成される。
このデータをすべてのメソッドに対して計算することで、2つの並行動作するメソッド間でデッドロックが発生するかどうか、という質問に答えることが可能になる。
パフォーマンスを最大化するため、アナライザはコードベース全体を一度に解析することは行わず、指定されたバージョンにおいて変更されたメソッドのみを処理した上で、リビジョン内のメソッドのいずれかとデッドロックになる可能性のあるすべてのメソッドを特定する。これは大規模なコードベースを効率よく処理する上で重要なポイントであり、静的、動的、ハイブリッドを問わず、他のデッドロック解析ツールと一線を画している部分である、と研究者らは述べている。
Facebookではこのデッドロックアナライザを、コードレビューに提出されたコミットに対してInferを実行するCIパイプラインの一部として、2年前から運用している。そのFacebookによると、このデッドロックアナライザは、数十万のコミットを処理する中で500件以上のデッドロックを報告し、その内の54パーセントが修正されたということだ。コミットあたりの実行時間は平均213秒である。
修正されなかった報告の一部は偽陽性、すなわち、並列動作の不可能な２メソッド間のデッドロックの報告である。その他のケースとしては、デッドロックの可能性が低いと開発者が判断したものや、別のコミットを通じて修正されたものがある。残念なことに、これらのカテゴリについての正確な数字は提供されていないので、誤検出の頻度がどの程度であったかは不明である。