プリエンプションはメモリの並べ替えのためのガベージコレクションである (2019)
Preemption is GC for memory reordering (2019) (pvk.ca)
要約
本稿では、プリエンプション(プリエンプティブマルチタスク)を、既にコストを支払っているガベージコレクションのように、メモリの並べ替え(リオーダリング)を保証するための有用なリソースとして捉え直すことを提案しています。割り込み処理の性質を利用することで、明示的なメモリバリアなしに、ユーザー空間でのロックフリープログラミングにおける順序保証を実現できる可能性を示唆しています。このアプローチは、特にx86アーキテクチャにおいて、プリエンプションによる遅延を積極的に活用するものです。
全文翻訳
プリエンプションはメモリ再順序付けのためのGCである
以前、プリエンプションがカーネルよりもユーザスペースでのロックフリープログラミングを難しくする理由について述べました。今では、プリエンプションはガベージコレクションのように、すでに支払っているコストなので、それを利用すべきだと考えています。割り込み処理(実際には割り込みハンドラからの復帰)はx86では完全にシリアライズされており、他のプラットフォームでも同様でしょう。ユーザスペースの命令は、割り込みの前に完全に実行されるか、ユーザスペースへの復帰後にいつか最初から(再)実行されます。これは、明示的なバリアなしでメモリアクセス間の順序を保証するために悪用できるものです。
この割り込みの悪用は、Bounded TSOと相補的です。Bounded TSOは、同時にインフライト状態にあるストア命令のハードウェア制限を測定し(命令が順序通りにリタイアするという知識と組み合わせる)、オーバーヘッドなしで、通常はわずかなレイテンシでライブネスを保証します。しかし、最悪実行時間情報がないと、命令数を実時間に対応付けるのは困難です。割り込みを追跡することで、以前の書き込みが確実にリタイアした、より保守的な遅延の後ではありますが、いつ十分な実時間が経過したかを判断できます。
この考えに至ったのは、2つのロックフリー同期プリミティブ(イベントカウントと、ハザードポインタやエポック再利用で使用される非対称フラグフリップ)に取り組んだ後です。これらは、遅いパスが速いパスからの生命の兆候を待つという点で似ていますが、「スタックした」速いパスの処理方法が異なります。ここでは、Linux/x86[-64]で開発したイベントカウントとフラグフリップの実装について説明します。どちらも順序付けのために割り込みに依存しています。これにより、プリエンプションがユーザスペースでのロックフリーコードのための、事前に支払われたバリアの有用な源泉であると確信していただけるでしょう。
この記事は、ロックフリープログラミング、特に安全なメモリ再利用技術に既に精通しており、形式的なメモリモデルでの推論経験がある読者を対象としています。さらに参照したい場合は、ACM QueueのSamyによる概要が良いリソースです。既にConcurrency Kitのイベントカウントと、私のbarrierdプロジェクトにおける割り込みベースの逆バリアのコードはコミット済みです。
イベントカウントとx86-TSOおよびfutexes
イベントカウントは、基本的にバージョンカウンタであり、スレッドが現在のバージョンが任意の以前のバージョンと異なるまで待機できるようにします。単純な「待機」実装は、バージョンカウンタをスピンさせることができます。しかし、イベントカウントの価値は、ロックフリーコードをOSレベルのブロッキングと統合できることです。待機者はイベントカウントの現在のバージョンv0を取得し、目的の処理を行い、CPUサイクルを消費して待機する代わりに、イベントカウントのバージョンがv0と異なるまでスリープして新しいデータを待ちます。イベントカウントは、しばしば再発明され、多くの名前(例: blockpoints)で呼ばれる一般的な同期プリミティブです。重要なのは、書き込み側がバージョンカウンタを更新でき、待機側がバージョンを読み取り、任意のコードを実行し、バージョンカウンタが以前のバージョンと同じ間効率的に待機できることです。
明示的なバージョンカウンタは、以下の擬似コードのような、誤用された条件変数の「ウェイクアップ漏れ」問題を解決します。
bad condition waiter:
while True:
atomically read data
if need to wait:
WaitOnConditionVariable(cv)
else:
break
正しく機能するためには、条件変数は、待機条件がまだ満たされているかを確認してから条件変数で待機する前に、データと条件変数の両方を保護するミューテックスを待機者が取得することを要求します。
good condition waiter:
while True:
with(mutex):
read data
if need to wait:
WaitOnConditionVariable(cv, mutex)
else:
break
待機者は、書き込み者がデータに変更を加えるのを防ぐ必要があります。さもないと、待機条件を確認してから待機を開始する間に、データ変更(および関連する条件変数ウェイクアップ)が発生する可能性があります。その場合、待機者はウェイクアップを逃し、既に発生した何かを永遠に待ち続ける可能性があります。
good condition waker:
with(mutex):
update data
SignalConditionVariable(cv)
以下の6つの図は、シグナラ(書き込み者)がデータに変更を加え、待機者をウェイクアップするのと、待機者がデータを観察して待機キューに入る間の可能なインターリーブを示しています。最も左側の2つの図は何もインターリーブしていません。これらは正しいロックによって許可される唯一のシナリオです。残りの4つは待機者とシグナラを実際にインターリーブし、3つは偶然正しい(幸運)ですが、1つのケース、WSSWでは待機者がウェイクアップを逃しています。
待機者が書き込み者の進捗を妨げることができる場合、ロックフリープロトコルとは言えません。イベントカウントは、待機者がウェイクアップされたかどうか(イベントカウントのバージョンカウンタが変更された)を検出できるようにし、これにより、待機者がまだ観測していないデータ変更に対するウェイクアップを逃す可能性のあるウィンドウを修正します。重要なのは、待機者がウェイクアップを防止するのではなく、ウェイクアップ漏れを検出することです。したがって、イベントカウントはロックフリー(さらにはウェイトフリー)を維持します。
例えば、ロックフリーリングバッファでイベントカウントを使用できます。コンシューマが書き込みポインタをスピンする代わりに、書き込みポインタをイベントカウントにエンコードし、コンシューマは新しいメッセージを待つためにCPUサイクルを消費することなく、効率的にそれにブロックできます。
イベントカウントの実装で難しいのは、スリーパーをウェイクアップさせることではなく、ウェイクアップすべきスリーパーがいる場合にのみ行うことです。一部のユースケースでは、指数バックオフで十分なため、積極的なウェイクアップを行う必要はありません。バージョン更新がリクエスト/レスポンス通信パターンでのレスポンスの到着を示す場合、指数バックオフ(例: 1.1xのバックオフ係数)は、バックオフ中のブラインドスリープによって引き起こされるレスポンスレイテンシの増加を、例えば10%に制限できます。
残念ながら、これは常に適用できるわけではありません。一般的に、シグナルが以前のリクエストに対するレスポンスに対応すると仮定することはできず、通常は進捗が速すぎて待機者がさらに作業を取得する前に短時間しかスピンしないケースをサポートする必要があります。後者の期待は、バージョンカウンタをインクリメントするたびに無条件にシステムコールを実行してスリーパーをウェイクアップすることはできないことを意味します。これは遅すぎます。この問題は新しくなく、アダプティブスピンロックにデプロイされているものと同様の解決策があります。
アダプティブロックの解決策パターンは、OSプリミティブ(例: futexes)との緊密な統合に依存しています。待機者がスピンするマシンワードである制御ワードは、通常のデータ(この場合はバージョンカウンタ)と、OSシステムコールでウェイクアップされるべきスリーパーがいることを示す新しいフラグをエンコードします。制御ワードへのすべての書き込みはアトミックな読み取り-変更-書き込み命令を使用し、スリープする前に、待機者は「スリーパーが存在する」フラグが設定されていることを確認し、次に、スリーパーフラグが設定された状態で、制御ワードが期待通りのままである場合にのみスリープするシステムコールを発行します。
OpenBSDのLinux futexes用互換シムは、futex呼び出しの実装としては非常にシンプルです。futexのウェイクアップと待機のためのOSコードは、ユーザスペースがミューテックスと条件変数(waitqueues)で行うことと同一です。待機者は、futexワードまたはそれより粗いスーパーセットに対するウェーカーをロックアウトし、futexワードの値が期待通りであることを確認し、futexの待機キューに入ります。ウェーカーは書き込みのためにfutexワードを取得し、待機キューをウェイクアップします。違いは、これらすべてがカーネル内で発生することです。カーネルは、任意のミューテックス/条件変数ペアとは異なり、保護されたデータは常に単一のマシン整数であり、待機条件は等価テストであるため、ユーザスペースとは異なります。このセットアップはカーネルで完全に実装するには十分シンプルですが、有用であるには十分一般的です。
OS支援の条件付きブロッキングは、イベントカウントに適合させるのに十分簡単です。制御ワードはイベントカウントのバージョンカウンタであり、1ビットは「スリーパーが存在する」フラグ(スリーパーフラグ)のために予約されています。
バージョンカウンタのインクリメントは通常の非同期インクリメントを使用できます。スリーパーフラグがインクリメントの前に設定されていたかどうかを判断できれば十分です。スリーパーフラグが設定されていた場合、それをクリアし(アトミックビットリセットで)、制御ワードでブロックされているOSスレッドをウェイクアップします。
increment event count:
old <- fetch_and_add(event_count.counter, 2) # flag is in the low bit
if (old & 1):
atomic_and(event_count.counter, -2)
signal waiters on event_count.counter
待機者はバージョンカウンタが変わるのをしばらくスピンできます。ある時点で、待機者はCPU時間を無駄にするのをやめるべき時だと判断します。待機者は次に、比較交換(CAS)でスリーパーフラグを設定します。CASは、カウンタの値が変更されたか、またはフラグが既に設定されているためにのみ失敗する可能性があります。前者(失敗)の場合、待機をやめる時が来ました。後者(失敗)の場合、またはCASが成功した場合、フラグは設定されます。待機者は次に、制御ワードがまだスリーパーフラグを設定しており、期待される(古い)バージョンカウンタと同じ値である場合にのみブロックするシステムコールを発行できます。
wait until event count differs from prev:
repeat k times:
if (event_count.counter / 2) != prev: # flag is in low bit.
return
compare_and_swap(event_count.counter, prev * 2, prev * 2 + 1)
if cas_failed and cas_old_value != (prev * 2 + 1):
return
repeat k times:
if (event_count.counter / 2) != prev:
return
sleep_if(event_center.center == prev * 2 + 1)
このスキームは機能し、まともなパフォーマンスを提供します。実際、FacebookのFollyには十分です。同時書き込み者(インクリメントするスレッド)がいる場合、これ以上改善できるとは思えません。
しかし、リングバッファの例に戻ると、多くの場合、1つの書き込み者しかいません。単一プロデューサリングバッファにアイテムをエンキューするには、アトミック操作は不要で、releaseストアのみが必要です(https://github.com/concurrencykit/ck/blob/master/include/ck_ring.h#L110)。書き込みポインタのインクリメントは、データ書き込み後にのみ可視であればよく、TSOメモリモデル(x86を含む)では常にそうなります。単一プロデューサリングバッファの書き込みポインタを、インクリメントごとにアトミック操作が発生するイベントカウントに置き換えるのは、簡単な判断ではありません。インクリメンタが1つだけの場合、もっと良い方法はないでしょうか?
x86(または非アトミック読み取り-変更-書き込み命令とTSOを持つ他のアーキテクチャはゼロですが)では可能です…しかし、いくつかの奇妙な点を受け入れる必要があります。
本当に高速である必要がある操作はイベントカウンタのインクリメントです。特にスリーパーフラグが設定されていない場合。一方、スリーパーフラグの設定は、実行中のスレッドが新しいデータを待っている場合にのみ発生するため、より遅く、アトミック命令を使用しても構いません。
最初の(高速パスの)インクリメントを、非アトミックな読み取り-変更-書き込み命令(inc memまたはxadd mem, reg)で行うことを提案します。スリーパーフラグが符号ビットにある場合、それを検出できます(ラップアラウンドでの偽陽性を除いて)。それ以外の場合は、xadd(fetch-and-add)を使用し、フェッチされた値のフラグビットを見る必要があります。
この種の問題では、通常の順序付けベースの議論は役に立ちません。代わりに、x86-TSOメモリモデルに直接移行する必要があります。すべてのアトミック(LOCKプレフィックス付き)命令は、実行コアのストアバッファをフラッシュし、メモリの排他ロックを取得し、そのロックを保持したまま読み取り-変更-書き込み操作を実行します。したがって、スリーパーフラグの操作は、メモリで既に可視になっている更新や、ストアバッファから送信中の更新を失うことはありません。RMWインクリメントも、最新のバージョン更新(グローバルメモリまたは唯一のインクリメンタのストアバッファにある)を常に確認するため、バージョン更新を失うこともありません。最後に、スケジューリングとスレッド移行は、インクリメンタスレッドが自身の書き込みを常に確認することを保証する必要があるため、バージョン更新を失うことはありません。
increment event count without atomics in the common case:
old <- non_atomic_fetch_and_add(event_count.counter, 2)
if (old & 1):
atomic_and(event_count.counter, -2)
signal waiters on event_count.counter
静かに上書きされる可能性のある唯一のものはスリーパーフラグです。待機者は、インクリメントがメモリから値をロードした直後、またはインクリメントがローカルストアバッファからフラグが設定されていない値を読み取っている間に、そのフラグをメモリに設定する可能性があります。問題は、待機者がインクリメントを観測するか、またはフラグの反転が次のインクリメントによって観測されることを知るまで、どれくらいの時間スピンする必要があるかということです。その質問はメモリモデルでは答えられず、最悪実行時間バウンドは現代のx86ではジョークです。
IRET、つまり割り込みハンドラからの復帰に使用される命令がフルバリアであることを思い出して、答えを見つけました。1 また、割り込みは、プリエンプションタイマーだけでも、頻繁かつ定期的な間隔で発生することを知っています(標準的なLinux/x86oidでは4〜10msごと)。
ストア可視性のバウンドに関係なく、待機者はスリーパーフラグを反転させ、しばらく制御ワードをスピンし、その後短時間(例: 最初は1〜2ミリ秒、次に10ミリ秒など)スリープを開始できます。スピン時間はほとんどの場合十分ですが、非常にまれに短すぎる可能性があります。
ある時点で、スリーパーフラグのサイレントな上書きやカウンタのアクティビティが観測されなかったため、フラグは必ず観測され、永遠にスリープしても安全だと確信したいです。ここでも、x86がこの種の厳密なバウンドを提供しているとは思いません。しかし、1秒というのは妥当に思えます。コアがそれだけ長く停止したとしても、割り込みはすべてのコアで毎秒数回発生し、割り込みハンドラからの復帰はフルバリアとして機能します。1秒に少なくとも1回発生する割り込みを越えて、ストアバッファに書き込みが残ることはありません。イベントカウントで1秒間アクティビティが観測されなかった場合、スリーパーフラグは次のインクリメントから観測可能になると仮定するのは安全です。
この仮定は、割り込みが定期的な間隔で発生する場合にのみ安全です。一部のレイテンシに敏感なシステムは、特定のユーザスペーススレッドにコアを割り当て、それらのコアからすべての割り込み処理とプリエンプションを移動させます。Linuxをティックレスモードで実行し、単一の実行可能プロセスを持つ正しく分離されたコアは、十分な頻度で割り込みを処理しない可能性があります。しかし、この種の構成は偶然には起こりません。そのようなシステムでの半秒の停止でさえ、システムエラーとして扱われ、ウォッチドッグをトリガーする可能性があると予想します。割り込みから無料でバリアを得ることができない場合、代わりに実用的なパフォーマンス要件に依存して実行時間のハードバウンドを強制できます。
いずれにせよ、待機者はスリーパーフラグを設定しますが、非常に保守的に見て1秒後までそれが観測されることを期待できません。その時間が経過するまで、待機者は制御ワードをスピンし、その後短く、しかし増加する時間だけブロックします。最後に、制御ワード(イベントカウントバージョンとスリーパーフラグ)が1秒間変更されていない場合、インクリメンタはインフライトの書き込みがなく、スリーパーフラグを観測すると仮定します。制御ワードで永遠にブロックするのは安全です。
wait until event count differs from prev:
repeat k times:
if (event_count.counter / 2) != prev:
return
compare_and_swap(event_count.counter, 2 * prev, 2 * prev + 1)
if cas_failed and cas_old_value != 2 * prev + 1:
return
repeat k times:
if event_count.counter != 2 * prev + 1:
return
repeat for 1 second:
sleep_if_until(event_center.center == 2 * prev + 1,
$exponential_backoff)
if event_count.counter != 2 * prev + 1:
return
sleep_if(event_center.center == prev * 2 + 1)
これは私がconcurrency kitのSPMCおよびMPMCイベントカウントのプルリクエストに実装したソリューションです。MP(マルチプロデューサ)実装は通常の適応ロジックであり、Follyの戦略と一致します。待機者がいない場合のアンコンテンストなインクリメントには約30サイクルかかり、スリーパーのウェイクアップは私のE5-46xx(Linux 4.16)でさらに700サイクル追加されます。単一プロデューサ実装は遅いパスでは同一ですが、待機者がいない場合のインクリメントは1インクリメントあたり約8サイクルしかかからず、アトミック命令を避けるためパイプラインをフラッシュしません(つまり、アウトオブオーダー実行エンジンはスループットを最大化できます)。待機者がいない場合のインクリメントの追加オーバーヘッドは、通常のリングバッファポインタ更新と比較して、単一の予測可能な条件分岐または融合されたtestと分岐、および通常の加算/ストアの代わりにRMWのロードで3〜4サイクルです。これはゼロオーバーヘッドに近く、コーダーがOS支援ブロッキングをロックフリーアルゴリズムで、誰もブロックする必要がない場合のペナルティについて苦悩することなく提供することを容易にします。
Linuxにおける割り込みによる非対称フラグフリップ
ハザードポインタとエポック再利用。これら2つの異なるメモリ再利用技術の根本的な複雑さは、ほぼ同一の同期要件から生じます。まれに、遅いコードパス(非常に遅くても許容される)がメモリに書き込みを行い、別の、はるかにホットなコードパスが遅いパスの最後の書き込みを確実に観測することを知る必要があります。
ハザードポインタの場合、遅いコードパスは、オブジェクトの最後の永続参照をメモリで上書きした後、ポインティを破棄しても安全になるまで待機します。ホットパスはリーダーです。
1. read pointer value *(T **)x.
2. write pointer value to hazard pointer table
3. check that pointer value *(T **)x has not changed
同様に、エポック再利用では、読み取り側セクションは現在のエポック値を取得し、そのエポックで読み取っていることをマークし、次にエポックが古くなっていないことを確認します。
1. $epoch <- current epoch
2. publish self as entering a read-side section under $epoch
3. check that $epoch is still current, otherwise retry
順序整合(SC)メモリモデルでは、2つのシーケンスは通常の(アトミックな)ロードとストアで有効です。遅いパスは常に書き込みを行い、次に他のすべてのスレッドの単一書き込みデータをスキャンして、遅いパスのストアより前にステップ2を実行したことを証明するものが(つまり、古いポインタまたはエポック値を公開することによって)あるかどうかを確認できます。
以下の図は、すべての可能なインターリーブを示しています。すべてのケースで、スレッドが遅いパスの新しい書き込みを観測しなかったという証拠がなくなった後、すべてのスレッドが書き込みを観測すると正しく仮定できます。図では、ステップ1の最初の読み取りをインターリーブしないことで簡略化しました。その役割は、ステップ3で再読み取りされる値の推測を提供することなので、少なくとも正しさに関しては、その初期読み取りはランダムな値を生成しても構いません。遅いパスの2番目の「スキャン」ステップも抽象的に保ちました。実際には、これはホットパスを実行するスレッドのエポックまたはハザードポインタテーブルの非スナップショット読み取りです。遅いパスは、エポックまたはポインタがスキャンに存在しなくなると、それらが復活しないと仮定できます。
誰もハードウェアでSCを実装していません。X86とSPARCは最も強力な実用メモリモデルであるTotal Store Orderingを提供していますが、それでも特別な注釈なしでは上記の読み取り側クリティカルセクションを正しく実行するには不十分です。TSOの下では、読み取り(例: ステップ3)は書き込み(例: ステップ2)の前に実行されることが許可されます。X86-TSOは、ストアが遅延する可能性のあるバッファとしてこれをモデル化しており、以下のシナリオは、ステップ2と3が遅延ストアによって分離されている場合に、SCからの違いを示しています(遅いパスは常に順序整合を回復するように計装できます。遅いパスであるためです)。TSOインターリーブは、ホットパスのステップ2と3が遅いパスのステップによって分離されている場合にのみSCのものと異なります。ステップが隣接している場合、遅いパスのステップに対するそれらの順序は、TSOの遅延ストアの影響を受けません。TSOは非常に強力なので、遅いパスがホットパスの途中で実行される1つのケース、FSSFのみを修正する必要があります。これはTSOによって許可されるストアとロードの順序の逆転を伴います。
単純な実装では、2番目と3番目のステップの間にストア-ロードバリアを挿入するか、バリアとしても機能するアトミック読み取り-変更-書き込み命令を実装することで、この穴を塞ぎます。どちらの変更も安全でSCセマンティクスを回復しますが、無視できないオーバーヘッド(バリアはアウトオブオーダー実行エンジンに、さらに作業を受け入れる前にフラッシュを強制します)が発生します。これは必要とされるのは少数派の場合だけです。
ここでのパターンはイベントカウントに似ており、遅いパスが速いパスに、後者が異なることを行うべきだとシグナルを送ります。しかし、イベントカウントの遅いパスは、速いパスが進歩しない場合に永遠に待機したいのに対し、ハザードポインタとエポック再利用は、そのケースを検出し、スリープ中のスレッド(SMRクリティカルセクションの途中にいないスレッド)を無視する必要があります。
この種の問題では、オーバーヘッドの大部分を遅い(コールド)パスに移動させたいと考えています。Linux 4.3では、まさにこのユースケースのためにmembarrierシステムコールが追加されました。遅いパスは、membarrierシステムコールを発行する前に書き込み(複数可)を実行できます。システムコールが戻ると、まだ可視になっていない(まだリタイアしていない)速いパスの書き込みと、プログラム順序でのそれ以降のすべての命令は、遅いパスの書き込みが可視な状態から開始されます。次の図に示すように、このグローバルバリアは、速いパスに特別なバリアを追加することなく、TSOの下で可能な唯一の異常な実行を排除できます。
membarrierの問題は、遅いバージョンとスケーラブルでないバージョンの2種類があることです。最初の、遅延のないバージョンは、カーネルRCUのコールバックが実行されるのを待ちます。これは私のマシンでは25〜50ミリ秒かかります。遅い理由は、RCUグレースピリオドが経過する条件がグローバルバリアよりも要求が高く、複数のそのようなバリアを必要とする場合があるためです。例えば、同じスキームを使用してエポック再利用を10段階ネストした場合、最も外側の再利用者は最も内側のものより1024倍遅くなります。この遅延に対応して、membarrierの潜在的なユーザーは、IPIをトリガーするために戻り、例えばダミーページをmprotectすることによって行われました。mprotectはバリアとして機能することが保証されておらず、AArch64ではそうしないため、Linux 4.16ではmembarrierに「高速化」モードが追加されました。その高速化モードでは、各membarrierシステムコールは他のすべてのコアにIPIを送信します…数百コアのマシンを見ると、コアあたり(n - 1)のIPIが、すべての(n)コアで毎秒数回、悪い考えに聞こえ始めます。
イベントカウントのために行った観察に戻りましょう。任意の割り込みは私たちにとってバリアとして機能します。なぜなら、割り込み後にリタイアする命令は、割り込み前に行われた書き込みを観測しなければならないからです。ハザードポインタの遅いパスがポインタを上書きした後、またはエポックの遅いパスが現在のエポックを進めた後、現在の時刻を見て、すべてのコアで後で割り込みが処理されるまで待つことができます。遅いパスは、すべてのコアで新しい割り込みが処理されたことを確実に判断できる情報(/procから)を読み取ることができます。遅いパスは、ポインタを上書きした後、またはエポックを更新した後、すべての速いパスの状態をスキャンして、それらがまだ上書きされたポインタまたは以前のエポックを使用している証拠がないか確認できます。割り込み前にその事実を公開しなかった任意の速いパスは、最終的に割り込み後に2番目と3番目のステップを実行し、最後のステップはその遅いパスの更新に気づくでしょう。
/procには、新しい割り込みがすべてのコアで処理されたことを確実に判断できる情報がたくさんあります。しかし、それは細かすぎます(/proc/stat)か、生成が非常に遅いです(/proc/schedstat)。さらに重要なのは、ftraceを使っても、興味深いことが起こったときに簡単にウェイクアップを要求できず、ファイルをポーリングしなければならないことです(さらに、本番環境化するのが奇妙に難しいカーネルインターフェースは言うまでもありません)。
必要なのは、各コアについて、最後に割り込みを処理した最後の時間(確実に)を読み取る方法です。理想的には、すべてのコアで最も古い「最後の割り込み」タイムスタンプの変更時にOSが待機者をウェイクアップするようにブロックすることもできます。x86では、それだけでハザードポインタとエポック再利用に必要な非対称バリアを取得するのに十分です。IRETだけがシリアライズされており、割り込みハンドラのエントリではありません。コアの「最後の割り込み」タイムスタンプへの更新が可視になると、更新前の任意の書き込み、したがって割り込み前の任意の書き込みもグローバルに可視になります。更新とは異なるコアからタイムスタンプ更新を観測する場合(この場合TSOが救ってくれます)、またはシリアライズするIRETでハンドラが戻った後のみです。
これらすべてのロジックを短いeBPFプログラムにバンドルできます。2プログラムは、スレッドローカル配列(それぞれ1つのCLOCK_MONOTONICタイムスタンプ)のマップ、パフォーマンスイベントキュー(CPUあたり1つ)のマップ、および1つの「ウォーターマーク」タイムスタンプの配列を持ちます。プログラムが実行されるたびに、現在の時刻を取得します。その時刻は、割り込みタイムスタンプのスレッドローカル配列に入ります。その配列に新しい値を格納する前に、プログラムはまず以前の割り込み時刻を読み取ります。その時刻がウォーターマーク以下の場合、パフォーマンスイベントキューにエンキューしてユーザスペースをウェイクアップする必要があります。エンキューは、パフォーマンスイベントがスレッドローカル配列よりもオーバーヘッドが大きいこと、および不要なウェイクアップを最小限に抑えたいことから条件付きです。高い信号対雑音比により、ユーザスペースはパフォーマンスイベントキューの読み取り側を各イベントでウェイクアップするように設定でき、これにより更新レイテンシを最小限に抑えることができます。
次に、単一のグローバルデーモンが必要です。このデーモンは、割り込みによってトリガーされる任意のソフトウェアトレースポイントセットにeBPFプログラムをアタッチし、パフォーマンスイベントキューをepollにフックし、epollが新しいパフォーマンスイベントを検出するたびに割り込みタイムスタンプのマップを再読み取りします。残りのコードはこれを処理します。トレースポイントの設定、eBPFプログラムのアタッチ、パフォーマンスイベントキューのウェイクアップの説得、およびそれらすべてをepollにフックすることです。私の完全にロードされた24コアE5-46xx(Linux 4.18、セキュリティパッチ適用済み)で、デーモンは約4ミリ秒ごとにウェイクアップされるたびに、コアの1〜2%(4.16ではさらに少ない)を使用します。パフォーマンスイベントキューは、JITコンパイルされていないeBPFプログラム自体が各コアの0.1〜0.2%を使用すると示しています。
興味深いことに、eBPFはeBPFプログラムで同時アクセスに安全なマップを提供しますが、ユーザスペースからシステムコールインターフェース経由でアクセスする場合、同じマップには保証がありません。しかし、実装は手作業で作成されたlong-by-longコピーループを使用しており、x86-64ではデータはすべてlongに収まります。カーネルのコンパイルフラグ(例: -ffree-standing)が、GCCがmemcpyまたはmemmoveを認識しないのに十分であり、それゆえx86-64でアトミックストアとロードが得られることを願っています。eBPFドキュメントの品質を考えると、この実装の偶然が実際にはAPIの一部であると賭けています。すべてのBPFマップは単一書き込み(カーネル内のCPUごと、またはユーザスペースでの単一スレッド)であるため、これは機能するはずです。
barrierdデーモンが実行されると、任意のプログラムがそのデータファイルをmmapして、各コアがユーザスペースを割り込んだ最後の時間(システムコールをさらに発行したり、IPIを発生させたりすることなく)を知ることができます。また、デーモンが割り込みを待つスレッドを、最も古い割り込みタイムスタンプが更新されたらすぐにウェイクアップさせるために、通常の同期を使用することもできます。アプリケーションは、現在の時刻を取得するためにclock_gettimeを呼び出す必要さえありません。デーモンは、mmapされたデータファイルで更新する仮想時間でも機能します。
barrierdデータファイルには、各コアのタイムスタンプ(CLOCK_MONOTONICと仮想時間の両方)を含むCPUごとの構造体の配列も含まれています。CPUのサブセット(例: コア2〜6)でのみ実行されることがわかっているクライアントは、配列のエントリ2〜6のみを見て、独自の「最後の割り込み」タイムスタンプを計算できます。デーモンは、CPUごとの値が変更されるたびに、それらにフューテックス待機者をウェイクアップします。コンビニエンスインターフェースは悲観的であり、クライアントコードが構成されているすべてのコアで実行される可能性があると仮定します。しかし、誰でも同じファイルをmmapして、よりタイトなロジックを実装できます。
ここでも、ティックレスカーネルには問題があります。デフォルト構成では、完全にアイドルなコアはタイマー割り込みを処理しない可能性があります。barrierdデーモンは、コアが遅れていることを検出し、/proc/statの変更をスキャンし始めます。このフォールバックパスは遅く、より粗い粒度ですが、アイドルコアでは常に機能します。より一般的には、デーモンは専用コアを持つシステムで実行されている可能性があります。RTスレッドを再アフィニティさせることで割り込みを発生させることを考えましたが、それは逆効果のようです。代わりに、barrierdのユーザーが専用コアを特別に扱うのが正しいアプローチだと思います。専用スレッドは割り込みを受けることができません(受けるべきではありません)。そのため、シリアライズ命令でウォッチドッグカウンタを定期的にインクリメントできます。待機者は専用スレッドのカウンタの変更をすぐに観測し、プリエンプティブに共有されるコアで待機するためにbarrierdを使用する可能性があります。おそらく専用スレッドはbarrierdにフックして、時々チェックインできるべきです。それはbarrierdのユーザー間の分離を破りますが、専用コアのスレッドは既に特権的な位置にいます。
ロードされていない4ウェイE5-46xxでLinux 4.16を実行している際のバリアレイテンシを、各メソッドで20000回の観測サンプルサイズで(300msの1つの外れ値を除外する必要がありました)迅速に比較しました。同期メソッドmprotect(ダミーページのパーミッションを削除して復元することでIPIを送信するためにmprotectを悪用する)または高速化されたmembarrier経由の明示的なIPIは、他の(遅延のないmembarrierとカーネルRCU、または割り込みをカウントするbarrierd)よりもはるかに高速です。IPIベースのメソッドにズームインでき、高速化されたmembarrier(IPI)が通常mprotectよりわずかに高速であることがわかります。高速化されたmembarrier経由のIPIは、mprotectの0.046ミリ秒に対して、最悪ケースで0.041ミリ秒に達します。
IPIベースのバリアのパフォーマンスは、システムロードにほぼ依存しないはずです。しかし、低優先度でCPU集約型のコードを低優先度で実行しているすべてのCPUで、同じ4ウェイシステムで、高速化されたmembarrierの遅延増加((68.4-73.0)%の時間、二項検定によると(p < 10\sp{-12})3)を観測しました。この2番目の実験では、各メソッドで100万回の観測サンプルがあり、高速化されたmembarrier経由のIPIの最悪ケースは0.076ミリ秒(ロードされていないシステムでは0.041ミリ秒)でした。一方、mprotectはより安定した0.047ミリ秒でした。
次に非IPIメソッドです。これらは同期IPIをトリガーするメソッドよりも遅いですが、オーバーヘッドが低く、スケーラビリティが高く、実用的なレイテンシを提供することが期待されます。
ロードされていないシステムでは、barrierdを駆動する割り込みは頻度が低く、時には完全に存在しないため、遅延のないmembarrierはより高速な応答時間を達成します。barrierdのフォールバックロジックでさえ観測できます。これは10ミリ秒の不活動後にアイドルCPUの証拠をスキャンするために/proc/statをスキャンします。これは20ミリ秒のスパイクです。vtimeの値は、直接CLOCK_MONOTONICを読み取るのではなく、barrierdの仮想時間に依存する場合に予想される追加の遅延を示しています。全体として、barrierd(53.7ミリ秒)とmembarrier(39.9ミリ秒)の最悪ケースレイテンシはそれほど違いませんが、軽量なマシンでのbarrierdのパフォーマンスを向上させるために、membarrierに基づいた別のフォールバックメカニズムを追加する必要があります。
同じ4ウェイ、24コアのシステムがロード下にある場合、割り込みはより頻繁かつ確実に発生するため、barrierdが輝きますが、ベンチマークプロセスのプリエンプションのため、すべてがより長いテールを持ちます。このロードされたシステムで、遅延のないmembarrier、barrierd、および仮想時間を使用したbarrierdのそれぞれについて100万回の観測のうち、100ミリ秒を超える54個の値(membarrierで18個、barrierdで29個、仮想時間で7個)を削除しました。残りは以下の通りです。barrierdはmembarrierよりも一貫してはるかに高速であり、幾何平均速度は23.8倍です。実際、barrierdは99.99%の時間で遅延のないmembarrierよりも早く完了し(二項検定によると(p<10\sp{-12}))、さらに98.3〜98.5%の時間で10倍高速であると期待できます((p<10\sp{-12}))。ギャップは非常に大きいため、機会的な仮想時間アプローチでさえmembarrier(幾何平均5.6倍)よりも高速ですが、今回はわずか3つの9(99.91〜99.96%の時間でmembarrierと同じくらい高速、(p<10\sp{-12}))です。
barrierdを使用すると、遅延のないmembarrier(カーネルRCUにピギーバックするため実質的に無料であり、これも sunk costです)よりもオーバーヘッドが大きいですが、レイテンシは1/10(25〜50ミリ秒ではなく0〜4ミリ秒)になります。さらに、割り込み追跡はCPUごとであり、スレッドごとではないため、グローバルな単一スレッドデーモン内でのみ発生する必要があります。残りのユーザスペースは、追加のシステムオーバーヘッドを発生させることなく必要な情報を取得できます。さらに重要なのは、スレッドプールワーカーがフューテックスでスリープする前に逆バリアを待っている場合など、スレッドがブロックする必要がないことです。ワーカーがmembarrierで25msまたは50msブロックすると、ワークユニットがワーカーキューにその時間座ってから処理される可能性のあるヒカップが発生します。barrierd(または前述のイベントカウント)を使用すると、ワーカーはワークユニットが表示されるのをスピンして待機し、フューテックスでスリープするのに十分な時間が経過するまで待機できます。
割り込み時間の情報はトレースポイントハックなしで利用可能になるべきだと信じていますが、membarrierのようなシステムコールがbarrierdのような共有デーモンよりも本当に優れているかはわかりません。際立った欠点は、barrierdが一部のCPUがアイドル状態のときに遅くなることです。これは、membarrierフォールバックを含めるか、電力消費を犠牲にして、アイドルコアでもカーネルティックを強制することで修正できます。
プリエンプションは資産となり得る
ユーザスペースでロックフリーコードを書くとき、私たちは常にプリエンプションを念頭に置いています。実際、ユーザスペースでロックフリーコードを使用する主な理由は、敵対的なスケジューリングの可能性にもかかわらず、一貫したレイテンシを確保することです。私たちは、割り込みやスケジューリングにもかかわらずアルゴリズムが機能するように多大な労力を費やしているため、割り込みがどのように役立つかを見落としている可能性があります。明らかに、コードをプリエンプションセーフにするにはコストがかかりますが、プリエンプションはオプションではありません。マネージド言語のガベージコレクションと同様に、プリエンプションはオフにできない機能です。GCとは異なり、ロックフリーコードでプリエンプションを利用する方法は明らかではありませんが、この記事は不可能ではないことを示しています。
プリエンプションを使用して、daemon like barrierdで、非対称バリアをほぼ無料で取得できます。プリエンプション駆動型バリアとBounded TSOのような技術との間には二重性があります。前者は比較的遅いですが、ハードバウンドを提供し、後者は通常、無視できるレイテンシでライブネスを保証しますが、時間バウンドはありません。
プリエンプションを使用して、単一書き込み者イベントカウントを高速化し(通常の非アトミックカウンタと同等)、membarrierの非対称バリアよりも低レイテンシの代替手段を提供しました。同様に、SPeCKは、同期的なシュートダウンに依存する代わりに、定期的なTLBリロードを強制することによって、レイテンシをわずかに犠牲にしてスケーラビリティを確保するために時間バウンドを使用します。割り込み(タイマーまたはその他)で他に何ができるでしょうか?
初期ドラフトに関する議論について、Samy、Gabe、Hanesに感謝します。最終版を改善してくれたRuchirに感謝します。
P.S. 非アトミックRMWなしのイベントカウント?
単一プロデューサイベントカウントの特殊化は、x86以外では見つけにくい非アトミック読み取り-変更-書き込み命令に依存しています。エポックとハザードポインタ再利用におけるフラグフリップパターンは、それが唯一の選択肢ではないことを示していると思います。
バージョンカウンタ用とスリーパーフラグ用の2つの制御ワードが必要です。バージョンカウンタはインクリメンタによってのみ、通常の非アトミック命令で書き込まれます。一方、フラグワードは複数のプロデューサによって、常にアトミック命令で書き込まれます。
課題は、futexのようなOSブロッキングプリミティブは、スリープを単一ワードに条件付けすることしか許可しないことです。16ビットshortのペアを32ビットintにパックしようとすることができますが、ラップアラウンドを回避する余地はあまりありません。そうでなければ、スリーパーフラグはバージョンカウンタをインクリメントする直前にのみクリアされることを保証できます。これにより、スリーパーはバージョンカウンタのみに条件付けできます…しかし、最後のクリアとインクリメントの間でスリーパーフラグが反転した場合、ウェイクアップをトリガーする必要があります。
インクリメント側では、ロジックは次のようになります。
must_wake = false
if sleepers flag is set:
must_wake = true
clear sleepers flag
increment version
if must_wake or sleepers flag is set:
wake up waiters
そして、待機者側では、次を見つけます。
if version has changed
return
set sleepers flag
sleep if version has not changed
分離された「スリーパーフラグ」ワードは、x86単一プロデューサバージョンの単一フラグビットと比較して、スペース使用量を倍増させます。Composite OSは、blockpointsでその2ワードソリューションを使用しており、利点はシンプルさとデータレイアウトの追加の柔軟性です。TSO以外のメモリモデルで、このスキームを単一プロデューサケースでより効率的に実装できるかどうかはわかりません。この2ワードソリューションがx86 TSO以外にのみ役立つ場合、それは基本的にSPARCであり、そのプラットフォームがメンテナンスの負担に値するかどうかはわかりません。
しかし、見てみましょう。おそらくAArch64またはPOWERで上記を機能させることができるかもしれません。
- 公式ドキュメントに裏付けられていない、より直感的な説明を好みます。x86-TSOのストアバッファは実際にはシリコンには存在しません。それは、アウトオブオーダー実行エンジンでリタイアを待っている命令を表します。正確な割り込みは、割り込みハンドラへのエントリさえもOOEエンジンの状態をフラッシュすることを意味し、それゆえ概念的なストアバッファをフラッシュするフルバリアとして機能します。↩
- 生のeBPFを使用したのは、Cフロントエンドが、ロード時にELFファイルを解析して、セットアップすべきeBPFマップとそれらの
fd番号をバックパッチする場所を知る必要がある、ばかげた量のランタイムコードに依存しているためです。また、eBPFプログラムの規模(最大4096命令、通常はそれよりはるかに少ない)では、Cフロントエンドの利点はほとんどないとわかります。clangを使用して開始点を作成しましたが、コンパイラがプログラムの意味論のどの部分が不可欠であるかを知らずに最適化できないほど、30命令をタイトにするのはそれほど難しくありません。bpfシステムコールは、プログラムをロードする際に追加情報を含む文字列バッファをポップレートすることもできます。これは、何かが間違ってアセンブルされたことを知るのに役立ちます。または、検証者がプログラムを拒否する理由を理解するのに役立ちます。↩ - これらの極端な信頼区間は、統計的なSLOをテストするための私の古いコードで計算しました。↩