枝でできた時計
A Clock Made of Branches (fzakaria.com)
要約
本記事では、決定論的な仮想マシン（VM）であるRewind VMにおける時間の計測方法について解説しています。ホストの壁時計時間ではなく、ゲストの命令ストリームの進捗、特に条件分岐の回数を時間の代理として使用することで、リプレイ時に一貫した時間経過を再現する方法を探求しています。これにより、バグの再現性向上やレースコンディションの正確なエミュレーションを目指します。
全文翻訳
枝でできた時計
リプレイしたいマシンの中で、時間は何であるか？ 🧘
決定論的なVMであるRewindを構築する際、時間の表現方法という考え方にすぐに直面します。ゲスト内部で時間を計測する方法が必要であり、これにより後続のリプレイ時にゲストは同じ時間を見て、同じ決定を下すことができます。時間は究極の変数です。
ホストの壁時計時間を単純に記録することはできません。なぜなら、2つのインターセプトポイント間の時間は、ホストの負荷、CPU周波数、キャッシュ、その他のプロセスなど、ゲスト外部の要因に依存するからです。したがって、同じゲストの作業でも、ホスト上では異なる時間がかかる可能性があります。
dafuq is a deterministic VM?で説明したように、Rewind VM内の時計、exit timeは、ゲストがsyscallなどから抜けるときにのみ進みます。2つの終了処理の間で行われるすべての処理を瞬時とみなします。したがって、2つのシステムコール間で1秒間数学計算だけを行うようなCPUバウンドなプログラムでも、5µsしか経過しないと認識します。🤦🏻♂️
Rewindには、counter timeという2つ目の時計モードもあり、これは処理時間を考慮しようとします。ゲストがリタイアした条件分岐ごとに、時計は1ナノ秒進みます。11これはrrデバッガによって普及したアプローチと同じです。rrの論文ではこれをdeterministic timeと呼んでいます。
補足: Rewindは初めてですか？一度しか発生しない不安定なビルドとdafuq is a deterministic VM?から始めてください。
「フリー」と「分岐」という言葉で私が何を意味するのか、まだ混乱していますか？2つの時計を区別するために、簡単な例を見てみましょう。
カウンター時間は処理時間を考慮しようとしますが、終了時間は終了時にのみ時計を進めます。22 5µsは、現在のハードウェアでのシステムコールとコンテキストスイッチの合理的なコストの私の推測です。1nsは、現在のコアでの条件分岐のおおよそのコストです。
なぜ分岐なのでしょうか？
§リプレイされるマシンにおける時間は何ですか？
ホストの壁時計時間に依存できないことはすでに理解しています。同じプログラムのすべての実行で同じになる測定値が必要であり、それによって経過時間と等価にすることができます。
すべての実行で同じになるものは何でしょうか？
ゲストの命令ストリームです！CPUは決定論的なマシンです。同じ入力、同じレジスタ、同じメモリ、そして同じ命令は、同じ次の状態を生成します。
命令ストリームの進捗を測定することで、時間を測定できます。💡
CPUメーカーは、まさにそのためのハードウェアカウンターを出荷していることが判明しました。それは信頼できるのでしょうか？見てみましょう。🧐
この単純なプログラムを使用してみましょう：10億からカウントダウンします。
int main(void) {
long i = 1000000000;
do {
i--;
} while (i != 0);
return 0;
}
_start:
mov rcx, 1000000000
.loop:
dec rcx
jnz .loop
mov eax, 60 ; exit(0)
xor edi, edi
syscall
アセンブリ相当には、mov、10億のdec+jnzペア、そして終了のための3つの命令が含まれており、合計で2,000,000,004命令になります。
perf statを使用して、CPUで2回実行し、命令数と条件分岐数を数えてみましょう。
$ nasm -felf64 loop.asm && ld -o loop loop.o
$ taskset -c 5 perf stat -e instructions:u,ex_ret_cond:u ./loop
2,000,001,025 instructions:u 1,000,000,000 ex_ret_cond:u
$ taskset -c 5 perf stat -e instructions:u,ex_ret_cond:u ./loop
2,000,001,054 instructions:u 1,000,000,000 ex_ret_cond:u
同じプログラムと入力で条件分岐数は同じですが、命令数は千ほどずれています。なぜでしょうか？
このループはCPUバウンドでレジスタをデクリメントするだけですが、外部からの影響から完全に隔離されているわけではありません。タイマーが鳴り、ネットワークパケットが到着し、他のコアがプロセッサ間割り込み（IPI）を送信します。プログラムはそれらを一切認識できませんが、私たちが調査している命令カウンターは認識できます。
ループを単一のCPUにピン留めし、/proc/interruptsから、各実行中にそのCPUが受け取った割り込みの数を数えました。
破線は割り込みごとに1つ追加されるカウントであり、命令カウンターはその線にほぼ完全に一致しています。33 /proc/interruptsは、ループの実行前後にperfとtasksetが起動・終了する間に着信する割り込みもキャッチするため、フィットが1ではなく0.94になっています。一方、条件分岐カウンターは、割り込みがどれだけ発生してもゼロのままです。
外部からの割り込みだけが命令数を歪めるわけではありません。プログラムはページフォールトを起こすこともあり、これも割り込みです。命令カウンターは、それを処理するためにカーネルが迂回したことを認識しますが、プログラムは認識しません。
ヒント すぐに使える状態では、AMD Zenは条件分岐を過剰にカウントすることもあります。これはSpecLockMapとして知られる投機的最適化によるもので、数千万回に数回発生します。修正するには、PMU MSRに特定のビットを設定する必要があります。Rewindはこれを自動的に行い、rr#2034も同様です。
§それで、何時ですか？
履歴を巻き戻すためには、信頼性が高く決定論的な時間の測定値が必要です。私たちの伝統的な壁時計時間は、外部世界の影響により信頼性が低いですが、命令ストリームの進捗に関する信頼できる測定値、つまり条件分岐カウンターを持っています。
条件分岐カウンターを時間の代理として使用することは、比較的良い近似であることが判明しました。
| 時計 | VM内の時間 | ホスト上の時間 |
|---|---|---|
| Exit time | 2.1 s | 15.7 s |
| Counter time | 11.7 s | 14.2 s |
なぜ「現実的な」時間の表現を持つことが重要なのでしょうか？
多くのプログラムは時計を読み取り、それに基づいて決定を下すため、ゲストの時計は少なくともある程度現実的でなければなりません。Exit timeの下では、コンピューティングは「無料」です。「1秒以内に完了する」といった作業をチェックするテストは常にパスします。追跡しているバグがタイムアウトである場合、exit timeでは決して再現できません。🙃
レースコンディションも非現実的な時計によって歪められます。Exit timeでは、作業のバースト全体が同じ瞬間に発生するため、スレッドが密集し、実際のハードウェアよりもVMでレースがはるかに頻繁に発生する可能性があります。
現実世界に近づけるほど、現実世界でのみ発生するバグを再現できる可能性が高まります。Counter timeは、exit timeよりも現実世界の優れた近似であり、決定論的であるため、Rewindのデフォルト時計です。
時間は幻想だと言う人もいます。私は、それはjnzカウンターだと言います。