- 壊れた Rust の並行カウンターを例に、通常のスレッド負荷テストが見逃す問題を、再現可能で最小化可能な実行順序の制御によって明らかにする
- テスト用の
AtomicU32 ラッパーが pause() を挿入し、managed thread がアトミック操作の前後で停止したあと、テストが選んだ順序で再開される
- 単純なテストでは、
100 個のスレッドがそれぞれ 100 回インクリメントし、期待値 10000 の代わりに 9598 のような失敗を起こせるが、タイミング依存のため再現・デバッグ・縮小が難しい
arbtest ベースのプロパティテストは、同じ seed で同じインターリービングを再現し、失敗例を 0: increment, 1: increment, 0: unpause, 1: unpause まで最小化する- 同じ構造を
exhaustigen で拡張すると、最大 5 回のインクリメントまで全インターリービングを列挙でき、fetch_add で修正した後は 81133 個のインターリービングが通過する
アトミックではない並行カウンター
- 例では Rust の
AtomicU32 を使っているが、increment() が load の後に store(value + 1) を行うため、インクリメント操作そのものはアトミックではない
Counter 構造は単純
value: AtomicU32increment() は SeqCst で値を読み、読み取った値に 1 を足して再び保存するget() は現在の値を SeqCst で読む
- 2つのスレッドが同じ値を読んだ後、同じインクリメント結果を保存できるため、更新が失われる
通常のスレッドテストでは不十分な理由
- 最も単純な検証は、複数のスレッドが同じカウンターを繰り返しインクリメントし、最後の値を確認する方法
thread_count = 100increment_count = 100- 期待値は
10000
- 実行例では
left: 9598, right: 10000 で失敗する
- この方法はスケジューリングのタイミングに大きく依存する
- 同じ失敗を決定的に再現するのが難しい
- デバッグしにくい
- スレッド数やインクリメント回数を減らすと運よく通ってしまうことがあり、失敗例を最小化しにくい
プロパティベーステストでインターリービングを扱う
- プロパティベーステスト（PBT）は状態機械テストと相性がよい
- 任意入力を生成しやすい
- 並行実行の結果が逐次実行モデルと同じであるべき、という性質を置ける
- 失敗入力を最小化したいという要件にも合う
- 難点は、実際の OS スレッドを望む時点で一段階ずつ進めるのが難しいことにある
- 解決策は、各反復で任意のスレッドを選び、一段階進める構造
- あるスレッドの
load と store の間に別のスレッドを挟み込める必要がある
- そのために、スレッドを直接制御する managed thread API を構成する
テスト用 AtomicU32 と pause の挿入
- テストビルドでは
std::sync::atomic::AtomicU32 の代わりに独自の managed_thread::AtomicU32 を使う
#[cfg(test)] use managed_thread::AtomicU32#[cfg(not(test))] use std::sync::atomic::AtomicU32
- ラッパー
AtomicU32 は load() と store() の前後で pause() を呼ぶ
load: pause() → 実際の load → pause()store: pause() → 実際の store → pause()
- この挿入点により、テストはアトミック操作の周辺でスレッドを停止・再開し、実行順序を制御できる
managed thread API の形
- テストは
std::thread::scope の中で2つの managed thread を作成する
- scoped thread を使うため、スタック上のローカルデータを借用できる
spawn(scope, &counter) のようにカウンター参照を状態として渡す
- managed thread は最初から特定の
main 関数を実行するのではなく、制御スレッドが submit() で送ったクロージャを実行する
t.submit(|c| c.increment())- スレッドは自身の状態
T に対してクロージャを実行する
- テストループはエントロピーが残っている間、各スレッドに対してランダムに行動する
- スレッドが停止していれば
unpause()
- 停止していなければ
submit() で increment() を実行する
- 逐次モデル
counter_model も同じ回数だけインクリメントする
- 最後にすべてのスレッドを
join() し、counter_model と実際の counter.get() を比較する
pause と unpause の実装
pause() はテスト対象の Counter API を変えないために、thread_local! で現在の managed thread のコンテキストを探す
- コンテキストは
Arc<SharedContext> として共有される
SharedContext は Mutex<State> と Condvar を持つ
- 状態は
Ready, Running, Paused に分かれる
Ready: 次のクロージャを待っている状態Running: managed thread が実行中の状態Paused: pause() 地点で停止した状態
- managed thread が
pause() に到達すると、状態を Running から Paused に変え、condition variable で制御スレッドに通知する
unpause() は状態を Paused から Running に変え、managed thread を起こした後、再び Running でなくなるまで待つ
- 制御スレッドと managed thread が同時に実行され続ける状況を防ぐ
- どの時点でもどちらか一方だけが実行されるようにして、非決定性を減らす
失敗の再現と最小化
arbtest の実行は、壊れたカウンターで失敗を見つける
- 失敗例はモデル値
4、実際の値 3
- 失敗 seed は
0x4fd7ddff00000020
- 同じ seed を指定すると同じインターリービングを再び得られるため、失敗の再現が容易になる
.minimize() を使うと、失敗例がより短い実行に縮小される
- 最終的な最小例の seed は
0x9c2a13a600000001
- 最小 trace は4段階
0: increment1: increment0: unpause1: unpause
- この最小例では期待値が
2 なのに実際の値が 1 となり、load/store ベースのインクリメントの欠陥が明らかになる
全インターリービング列挙への拡張
- 同じ構造を、ランダムなインターリービングの代わりに列挙ベースへ変えられる
exhaustigen を使い、最大 5 回のインクリメントまで全インターリービングを探索するテストを書く
- テストはダミーの反復を避け、常にスレッドを
unpause するか increment を投入するように構成される
- 壊れた実装は同じバグを見つける
Counter::increment() を fetch_add(1, SeqCst) に直すとテストが通る
AtomicU32 ラッパーにも fetch_add() 前後の pause() を追加する- 実行結果は
all 81133 interleavings are fine!
- 実行時間は
real 8.65s、CPU は 8.16s、RSS は 63.91mb
弱いメモリモデルとモデル検査への拡張
- 現在の玩具的な実装の
AtomicU32 は、実際の atomic に委譲している
- 拡張アイデアは、各 atomic ごとに書き込まれた値の集合を保持し、読み取り時に弱いメモリモデルと整合する任意の値を返す方式
- インターリービング探索も、ランダムより賢くできる
shrinking なしで最小化が可能な理由
- 使用した
arbtest は慣れ親しんだ PRNG インターフェースのように見えるが、有限 PRNGを使う
- ランダム値を要求し続けると、ある時点で
Err(OutOfEntropy) を返す
- そのためテストコードに
? と while !rng.is_empty() が登場する
- テストがエントロピーを使い切ると短く終了するため、利用可能なエントロピーを減らせばテスト実行も短くなる
- 内部実装は概念的には
&mut &[u8] に近い
- ランダムな数値を要求するたびにバイトスライスが縮む
- 初期スライスが短いほど、より単純なテストになる
- この方式により、別途 shrinking ロジックを直接実装しなくても、失敗例を短くできる
- サンプルソースコードは properly-concurrent にある
1件のコメント
Hacker Newsのコメント
Rustでは似たアプローチで Temper というライブラリを作っている: https://github.com/reitzensteinm/temper/tree/main
ただし、Rustのメモリモデル全体が生み出す奇妙な含意をモデル化するには、さらに踏み込む必要があり、各スレッドがどの書き込みを認識したかを追跡する台帳が必要になる。アトミックなメモリ順序、読み取り/書き込みフェンスなどに応じて、書き込みXを認識したなら書き込みYも必ず認識しなければならない、といった保証が生じうる
C++/Rustメモリモデルのテストケースを最も多く集めている部類だと思っており、書籍、C++標準、Stack Overflow、ブログなどで見つかるものをほぼすべて集めた。たとえばMara Bosの Rust Atomics and Locks 用ファイルはここにある: https://github.com/reitzensteinm/temper/blob/main/memlog/tes...
記事で言及されている Loom は似ているが、はるかに完成度の高いライブラリで、ミューテックスやキューのようなより高水準のコンポーネントを徹底的にテストできる: https://github.com/tokio-rs/loom ただしメモリモデル自体はTemperほど緻密にはモデル化しておらず、テストケースをLoomに移植しようとは考えていた
Will WilsonのFoundationDBテストに関する発表から着想を得ており、彼は今Antithesisで、任意のDockerコンテナにこの種のテストを実行するハイパーバイザベースのソリューションを作っている: https://www.youtube.com/watch?v=4fFDFbi3toc, https://antithesis.com/
今後10年でこの分野ははるかに大きくなると強く信じている。WebAssembly は任意のソフトウェアをコンパイルできるほど十分に完全でありながら、Antithesisのようなものを作ることが、すでにデータベースをリリースしたことのある精鋭チームによる5年がかりのプロジェクトにならない程度には単純でもある、という絶妙な地点にある
Rustで 共有メモリのアトミックスナップショット を実装し、自動テストにもできる限り真剣に取り組んだ: https://github.com/kaymanb/todc/tree/main/todc-mem
最初は記事に出てきたLoomを使っていたが、後に shuttle に切り替えた: https://github.com/tokio-rs/loom, https://github.com/awslabs/shuttle
shuttleはLoomのような全探索の代わりにランダム化されたアプローチを使うが、スケジューラはバグ発見に対する確率的保証を依然として提供する。使ってみるとshuttleのほうが速く、より複雑なテストシナリオにも拡張できた
記事の方式と同様に、特定のスケジュールがテスト失敗を引き起こした場合は乱数シードを保存できる。失敗したテストを素早く再現できる能力は非常に重要で、以前に見つけて修正したバグに対して明示的なテストケースを書けるようになる: https://github.com/kaymanb/todc/blob/0e2874a70ec8beed8fae773...
Kotlin/Javaでは、JetBrainsの Lincheck がこうした作業に適したライブラリだ: https://github.com/JetBrains/lincheck
特に宣言的である点と、線形化可能性の結果を出力する方法が気に入っている
C++にもLoomのようなライブラリがあるのか気になる。テストしたい ロックフリーデータ構造 がある
かなり古いツールだが扱いやすい。並行性分野の専門家であるDmitry Vyukovが作った
https://github.com/facebook/folly/blob/main/folly/test/Deter...
きちんと理解できていれば、このアプローチには弱い進行保証に関して限界がある
本体の計算はそれほど些細ではないものの、実際のハードウェアと実際のスケジューラでは、特定の CPU 上で中断される可能性がきわめて低い
cmpxchgループを考えられる。CPU 数がnのとき、最悪の場合の進行確率は1/nだが、このテスト方式では1/t^pになる。ここでtはタスク数で CPU 数よりはるかに多い場合があり、pはそのループ本体内の一時停止回数で、容易に 3 以上になりうる。これだけで、実際には動作するアルゴリズムを壊れているように見せるには十分だ逆に、弱い進行をバグとして捉えて強い進行を要求したい場合でも、この方式が有用なツールを提供しているようには見えない
それでも、多くの並行性の問題には明らかに有用だ
1/t^pは正しくないように思えて、単に1/tと見るべきだと思う。結局、t時間が経てばどれか 1 つのタスクは必ず進んでいるはずで、タスクがt個あるなら、自分が進んだタスクである確率は1/tだ重要な混同は、中断されたからといって必ずしも CAS で負けることを意味するわけではない、という点にあるようだ
「率直に言うと、ここには多少の事前知識がある。インラインアセンブリでひどく呪われたことをしない限り、実際のスレッド生成を避けることはできそうにない。何かが
pause()関数を呼び出し、こちらが後で指示するまで止まっていてほしいなら、その処理はテストのスタックとは別のスタックを持つスレッド内で起きなければならない」という部分について、何らかの非同期ランタイムを使えないのか気になる原子演算を計測して協調的マルチタスクを実現しているように見える。コーヒーをもっと飲む必要があるのかもしれないが、スレッドなしでやるほうが単純に見える
このアプローチの欠点の 1 つは、テスト対象コード自体をテストコード向けに修正しなければならない点だ
2 つのスレッドを立ち上げて
ptraceでシングルステップ実行し、命令実行を「ランダムに」差し挟んでも同じことができそうに思える。rr の chaos モードのようなやり方だただし、命令によっては原子的でない可能性があるので、エミュレーションなしで可能だとしても、「原子的マイクロコード」単位でシングルステップ実行する方法が必要になりそうだ
Loom を使うには条件付きコンパイルが必要なようで、ライブラリ 1 つをテストするなら問題ないが、かなり侵襲的だ
#[cfg(loom)]pub(crate) use loom::sync::atomic::AtomicUsize;#[cfg(not(loom))]pub(crate) use std::sync::atomic::AtomicUsize;独自スケジューラをもっとうまく使える言語があるのか気になる
本当に徹底するなら、
ptraceでテストを実行し、スレッドをシングルステップで進めて命令レベルで異なるインターリービングを作れそうだ。実際にそういうやり方を見たことがあるのか気になるここでのようにコードを計測できない場合、ブラックボックステストの代替手段はあるだろうか?
n個の命令を実行するとすると、シグナルを差し挟む前に 0 個からn個までの命令を実行するn回の実行だけが必要で、その後はシグナルハンドラが最後まで実行され、次に基本スレッドも最後まで実行される。全体時間はO(n^2)だしかし、それぞれ
n個の命令を実行するスレッドがt個あり、すべての境界で互いを中断できるなら、現実的なnの値では手が届かない。興味深い動作をする演算だけを選び出してシミュレーションする形で減らす必要がありそうだかなり良さそうなので、一度使ってみたい。ただし、あらゆる種類のエラーを捕まえられるわけではない。
pause()呼び出しのたびにスレッド間で同期が発生して、一部のデータ競合の問題が隠れてしまわないだろうか? Rust では問題にならないかもしれない