Quiescent State Based ReclamationとRCUの話とHTMの話

くまぎ @kumagi

ブログ書いた 「userspace RCU(QSBR)の使い方と解説」 http://t.co/mvjPoU6M51 安全にロックフリーするための局所的なガベージコレクタとも言える。

Sadayuki Furuhashi @frsyuki

@kumagi awesome

Sadayuki Furuhashi @frsyuki

@kumagi 全スレッドがrcu_quiescent_stateを定期的に呼ばないと成立しない気がしますが、データの読み出しを行わないスレッドとか、たまに行わなくなるスレッドは、どういうタイミングでrcu_quiescent_stateを呼んでいるんでしょ？

くまぎ @kumagi

@frsyuki ぉ、その欠点に気づいてしまうとはさすがですね。他のUserspaceRCUがみんなRW-Lockの代わりにも使える（しかも位置やシグネチャも一致するのでバイナリのリンク先を変えるだけで良い）一方でQSBRはアルゴリズム中に侵入的に変更を加える必要があります。

くまぎ @kumagi

@frsyuki データの読み出しを行わないスレッドはrcu_thread_offlineを呼び出しておいて、local_clockをINT_MAXにする（もしくは0にして明示的に無視するif文を足す）をすることで、永続的にquiescent_stateに居ることになります。

Sadayuki Furuhashi @frsyuki

@kumagi ほほーなるほど。しかし侵入的に変更が必要と言っても、なかなか難しいですねぇ。まず読み書きに参加するスレッドを決め、参加する以上は定期的にrcu_quiescent_stateを呼ぶ必要がある…という取り決めに従えるケースでないと使えない。

Sadayuki Furuhashi @frsyuki

@kumagi でないと最悪停止時間が長くて厳しい。fork-joinで決まった数のタスクの並列処理するが、多少のデータは共有して読み書きする必要があるようなケースだとうまくいくかも。たまに読み出さない時間が無くなり、定期的に読み出すか、一切読み出さないかのどちらかに絞り込める。

くまぎ @kumagi

@frsyuki ですです。C++ならデストラクタでthread_offlineを呼び出すオブジェクトを一緒に取り回す事でいくらかスマートにはなりますが、厄介なのが複数の物を組み合わせて扱う場合で、自分がAから獲得した値が一緒に使ってるBのQSで消去されてしまうという…。

くまぎ @kumagi

@frsyuki QSBRやEBR(Epoch Based Reclamation)はGrace Periodの長さを犠牲に、Readerのペナルティの最小化を図るアルゴリズムなので幾分仕方ない気はします。

くまぎ @kumagi

@frsyuki ですがもう少しメモリを使っていいなら、リタイヤリストを作っておいて、消去時はその時のold_counterと一緒にそのリストに繋ぐだけ。その長さが一定量を超えたらリストからfreeという手法も使えます。長さじゃなくてbad_allocを契機にする手もあります。

Sadayuki Furuhashi @frsyuki

@kumagi それはなかなか良さそうだけども、アクセスパターンによってはSEGVるので実用的には厳しいのでは。

くまぎ @kumagi

@frsyuki リタイヤリストからの消去ルーチンはロックで守る必要があります。リタイヤリストから消去する場合は、全スレッドのlocal_counterのminを取ってからリストを舐めれば安全で効率的です。

Sadayuki Furuhashi @frsyuki

@kumagi なるほど。

Sadayuki Furuhashi @frsyuki

@kumagi fork-joinの中に閉じた場合にのみ限定するなら、その間いっさいメモリを解放しない…という割り切り戦略の方が使いやすいかもw　速いし。fork-joinが終わったら全部解放する。メモリは、積めば良い。ファイルをmmapして非アクティブ領域はswapさせるとか。

くまぎ @kumagi

@frsyuki 使う前から見積もりが立つなら、一切free無しで、全部終わってからページごとぬっ殺す戦略は実用的だと思います。

くまぎ @kumagi

@frsyuki 最悪停止時間やメモリ消費量を改良したいのであればそもそもHazard PointerやPass the Buckなどのアルゴリズムを使う事で改良できます。このスライドの http://t.co/1aYIsNl4dD 40ページから44ページに詳細があります。

Sadayuki Furuhashi @frsyuki

@kumagi ところでハードウェアトランザクショナルメモリがアツくなってきた昨今ですが、通常時はRead-write lock、使えるのならHTMを使うという戦略で、大抵のreadが多いケースにおいては今後対応できるのでは。

くまぎ @kumagi

@frsyuki HTMの欠点（トランザクション内で扱えるメモリ量にハード的な上限がある）をきちんと把握して使う分には大抵解決すると思います。Elimination、NUMA-aware、線形化可能性を捨てた最適化等には勝てないですが、別に勝たなくても良いという…。

Sadayuki Furuhashi @frsyuki

@kumagi トランザクション内で扱えるメモリ量の上限については、他のアルゴリズムを組み合わせれば何とかなるんじゃないですかね？ なりそうですけど、ならないですかね？

くまぎ @kumagi

@frsyuki なりますよ。いわゆるHybrid TMという奴らですね。正しく理解して使う分には大丈夫ですが、privatizationやらStrong Isolationやらの特性の違いが全部最強側に寄せてくれてるHTMよりややこしかったりするので、誰でも使えるかというと…。

Sadayuki Furuhashi @frsyuki

@kumagi 例えば、大半のメモリ領域はHTMに管理させずに直接扱うが、読み書きを行う際はHTMの管理下にある1バイトを必ず読み書きする…これでスケーラビリティは低下するがメモリ量の上限を取り払える、というシンプルな方法はあり得ない？

くまぎ @kumagi

@frsyuki HTMの実装にも依りますが、Transaction Beginした後で部分的にNon-Transactional Readを行うインタフェースはHaswellには無かったような…？それと、それはRW-Lock以上の旨みはないのでは…？

Sadayuki Furuhashi @frsyuki

@kumagi なるほど