lock-freeアルゴリズムにおけるメモリ回収

これは C++ advent calendar の参加記事です。
もともとは「マルチコア時代のLock-free入門」の補遺として書くつもりだったのが、何だかんだで一年近くほったらかしになってしまっていたので、今回 advent calendar という締切りを課すことでようやく書くことができました。(笑)
前の発表で、lock-freeアルゴリズムを C++ で実装するには「タグ付きポインタ」や「Hazard pointer」を使いましょうと言いましたが、具体的な実装コードについてはあまり触れませんでした。そこで、実際に「タグ付きポインタ」と「Hazard pointer」を使い、代表的なlock-freeアルゴリズムである Lock-Free Queue を実装してみました。
GitHub - yamasa/lockfree: Experimental implementations of lock-free algorithms, using hazard pointers and tagged pointers.
タグ付きポインタ版(queue_tagged.h)のほうはC++03とgcc拡張の範囲で実装していますが、Hazard pointer版(queue_hazard.h)のほうはC++0xの機能をバリバリに使っているので、おそらくgcc4.6でしかコンパイルできないと思います。ちょっと調子にのってしまいました。(笑)

「タグ付きポインタ」と「Hazard pointer」の違い

さて、今回実装したタグ付きポインタ版とHazard pointer版のそれぞれの Lock-Free Queue には、単にC++0x対応の有無だけではない大きな違いがあります。それはキューの要素として扱える型の制限です。
タグ付きポインタ版では、キューの要素は trivially copyable な型でなければなりません。 trivially copyable を簡単に説明すると、memcpy相当の操作だけでコピーできてデストラクタでは何も行なわないような型のことです。詳しくはC++0x仕様書やこちらの記事などを参照してください。
何故 trivially copyable でなければならないかというと、タグ付きポインタ版のほうの dequeue 操作では、valueを読み出そうとしてるNodeが他スレッドによって回収・再利用されたのを「検知」することはできても、回収そのものを「保留させる」ことはできないからです。よって、「data race覚悟でvalueをコピーし、直後のCASで失敗したらやり直す」という手段を取らざるを得ません。そのため、非 trivially copyable なクラスだと、他スレッドが書き換え途中の状態を見てしまい、不正なアドレスにアクセスしてしまったりする事故が起きてしまう可能性があるのです。
一方のHazard pointer版では、 dequeue 操作でのNodeの回収・再利用を「保留させる」ことができます。そのため、同時に複数のスレッドがキューの要素へアクセスすることは無いことが保証できるので、ムーブ代入なども自由に利用することが可能になるのです。
このように、同じようなlock-freeアルゴリズムであっても、メモリ回収に用いる手法の違いによって性質が大きく変わってしまうことがあるのです。