1月版　無視できないフラグメンテーション問題への解答は？

小崎資広
2010/2/10

ユーザー空間でRCU？ membarrier()システムコールとは

　Mathieu Desnoyersによって、「introduce sys_membarrier(): process-wide memory barrier」と題されたパッチが投稿されました。

　sys_membarrier()は、その名のとおり、メモリバリア（注3）を発行するシステムコールです。「メモリバリアぐらいユーザー空間から勝手に発行すればいいじゃないか。システムコールにする必要性がまったくないよ」と思うかもしれませんが、これにはちゃんと理由があります。

　ちょっと長くなりますが、まずは背景をば。

　MathieuはLTTngの作者として有名で、最近は、LTTng（関連記事）への高速なユーザー空間トレーシング機能の追加に力を入れています（確か、博士論文のネタとして活動していると昔聞いた気がします）。

　彼のユーザー空間トレーサーは、「トレースログは一定量、ユーザー空間でバッファリングする。そこで生じる排他の問題は、ユーザー空間で動作するRCUを使ってロックレスに処理を実行することで解決する」というアイデアにより、トレース処理のオーバーヘッドを最小限にするもののようです。SystemTapのユーザー空間トレーシングが、DTRACE_PROBE()マクロ（注4）をコールするたびにシステムコールを呼び出しているのとは対照的です（注5）。

　そしてそのための仕組みとして、「librcu」という、ユーザー空間で動作するRCUをライブラリ化して公開しています（注6）。

　さて、librcuの話を始める前に、ロックレスとRCU（注7）について若干復習したいと思います。実のところ、現代的なCPUでは、ポインタの代入はアトミック（不可分）で行えるため、書き込みをロックレスにするのはそんなに難しくありません。ある構造体をコピーして変更した後、参照しているポインタをアトミックに書き換えればよいからです。

　より難しいのは古い方のデータをいつ捨てるかの判断です。なぜなら、ロックレスである以上、読み手がまだ古いデータにアクセスしている可能性を捨て切れないからです。カーネルのRCUはこの問題に対して、

1. 読み手はRCUクリティカルセクションでは絶対にコンテキストスイッチしてはいけないという制約を設ける
2. スケジューラにフックを入れ、全CPUが1回以上コンテキストスイッチしたら古いデータの参照区間は抜けたはずであると見なし、解放ルーチンをコールバックで呼び出す

というトリックにより、この問題に対応しています。

注3：http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%A2%E3%83%AA%E3%83%90%E3%83%AA%E3%82%A2。x86ではmfence、sfence、lfenceがメモリバリア命令です。特権命令ではないのでユーザー空間から自由に発行できます。 注4：DTRACE_というprefixが付いているのは偶然ではありません。SystemTapのユーザー空間トレースのポリシーは、DTRACEのUSDT（User- Level Statically Defined Tracing）用のアノテーションがそのまま動くようにすることです。PostgreSQLなどいくつかの著名なオープンソースミドルウェアはすでにDTrace対応を開始しており、これはリーズナブルな選択といってよいと思います、理論上は（いまのSystemTapの実装は遅過ぎていかがなものかと思いますが）。 注5：余談ですが、SystemTapのUSDTの実装はとてもトリッキーです。アプリケーションからは、システムコールをわざと間違った引数で呼び出します。一方カーネル内では、事前に仕込んでおいたカーネルモジュールにより、システムコールのエラーチェックコードにブレークポイントを埋め込み、コードを乗っ取ります。そして、その乗っ取った先でSystemTapスクリプトのprobeハンドラを動かし、スクリプトから好みの情報を抜き放題……という、頭のネジが2〜3本外れた（褒め言葉）設計になっています。これは褒め言葉です。大事なことなので2回いいました。 注6：http://lttng.org/content/userspace-rcu-library。なお、Paul E. McKenney（RCUサブシステムのメンテナ）によるユーザーランドRCUの解説が以下からダウンロードできるようです。http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf 注7：http://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%BC%E3%83%89%E3%83%BB%E3%82%B3%E3%83%94%E3%83%BC%E3%83%BB%E3%82%A2%E3%83%83%E3%83%97%E3%83%87%E3%83%BC%E3%83%88

■「相手に」無理やりメモリバリアを発行させるトリック

　ユーザー空間RCUを作るに当たって問題となるのは、（1）の制約を実装する方法がないことです（注8）。そのため、rcu_read_lock()内でスレッドローカル変数をインクリメントしておいて（注9）、synchronize_rcu()内で、全スレッドに対して、その変数の変更をポーリング監視することによりクリティカルセクションを抜けたかどうかをチェックします。synchronize_rcu()の性能がどれだけ下がってもよいから、rcu_read_lock()／rcu_read_unlock()を高速化しようという執念が読み取れる設計です。

　ところが、ここで1つ問題があります。アトミック命令を使わず、ストアした変数をロードした場合の結果は、メモリバリアを用いない限り正しい結果が保証されません。普通であればここで、rcu_read_lock()とsynchronize_rcu()の両方にメモリバリアを入れるところですが、上記の方針のようにsynchronize_rcu()がどれだけ遅くなってもいいからrcu_read_lock()を速くしたい場合、これは最適解ではありません。

　もう1つの案は、synchronize_rcu()から全スレッドにSIGUSRシグナルを送信、シグナルハンドラからメモリバリアを発行することで、実際に値をロードする直前に相手に強制的にメモリバリアを発行させるという方法です（注10）。ところがこの方法は、シグナル特有のさまざまなレース（競合）の問題に加え、SIGUSRがすでに使われていた場合の対応など副作用が大きくなります。また、CPU上を走行していないスレッドにもシグナルを飛ばすことになるので、スレッド数が多い場合は遅過ぎます。

　しかし、よくよく考えてみると、「全スレッドからメモリバリアを発行する」ことはまったく必須ではないことが分かります。メモリのinconsistencyが発生する可能性があるのは、

1. rcu_read_lock()を通ったスレッド
   かつ
2. rcu_read_lock()以降まだコンテキストスイッチがされてない場合

に限ります。コンテキストスイッチは暗にメモリバリアを張るからです。ここで（1）と（2）ともに判定する方法がないため、代わりに全スレッドにブロードキャストしているわけです。

　（1）はrcu_read_lock()にオーバーヘッドを加えない限り判定不能ですが、（2）はシステムコール化することで改善が可能です。現在CPUを走行中ではないスレッドは、コンテキストスイッチを1回以上行ったに決まっているからです。このアイデアに基づいて、

（I）システムコール発行元スレッドと同一プロセスに所属するスレッドが走行中のCPU集合を取得
（II）それらのCPUに、IPI（Inter-Processor Interrupt：プロセッサ間割り込み）で割り込みを送る
（III）IPI割り込みハンドラでsmp_mb()を呼ぶことにより、「相手に」メモリバリアを発行させる

という動作を実装したのが、sys_membarrier()の正体です。

　白眉は、「相手に」無理やりメモリバリアを発行させるという発想に加え、（I）の関係あるCPUのみにIPIを送るという発想です。

　実は、TLB shootdown（注11）などでも、invalidateは自プロセスに関係あるCPUに限りたいという要求があります。このため、そのプロセスが走行中のCPU集合は、struct mm_structのcpu_vm_maskメンバに保存されていることがスケジューラにより保証されています。よってこの操作はとても低コストです。実装を高速化するため、この変数をロックを取らずに参照することによってレースが発生し得ますが、レースが発生してコンテキストスイッチにより値が変わってしまったときは、コンテキストスイッチ内部で暗にメモリバリアが張られるので、矛盾は発生しません。

　レビューアからは「なんというオレ専用API」「ほかの用途への応用がまったく思い付かない」などと次々の賛辞の声が寄せられ、ちょっとした祭りになっています。Paul E. McKenney（RCUサブシステムのメンテナ）はこのパッチが大のお気に入りで、マージしたいという意向を表明していますので、意外とすぐにマージされるかもしれません。個人的にはガベージコレクション（GC）の改善に応用できないかなどと妄想しています。

注8：ここでは「全スレッドを最高優先度のリアルタイムスレッドにすれば実現可能」という案は考えないことにします。そもそもリアルタイムスレッドを前提にできるなら、RCUなんて複雑な仕組みは必要ありません。 注9：共有変数をインクリメントするためにロックを取るとか、アトミック命令を使うなどという方法はRCUの価値を台無しにしてしまうので、read_rcu_lock()でアクセスしていいメモリはスタックとスレッドローカル変数だけです。余談でした。 注10：なお、librcuはここで説明した2案＋sys_membarrier()方式のすべてを実装しており、リンクするライブラリによって動作を切り替えることができるようになっています。 注11：簡単にいうと、munmapした場合には、TLB（Translation Look-aside Buffer、ページテーブル参照用のキャッシュ）のキャッシュをクリアしないといけません。しかしCPUは、自身のTLBをクリアする命令しか持っていないため、IPIで割り込みを送り、相手にTLBクリアを呼ばせるというテクニックです

2/2

Index Linux Kernel Watch　1月版 　無視できないフラグメンテーション問題への解答は？

Page 1 　Melの悲願なるか？ Memory Compactionチャレンジ   コラム　LKML名言集：It's not "Linus C" Page 2 　ユーザー空間でRCU？ membarrier()システムコールとは

連載 Linux Kernel Watch

---

Linux Squareフォーラム Linuxカーネル関連記事

	連載：Linux Kernel Watch（連載中） Linuxカーネル開発の現場ではさまざまな提案や議論が交わされています。その中からいくつかのトピックをピックアップしてお伝えします
	連載：Linuxファイルシステム技術解説 ファイルシステムにはそれぞれ特性がある。本連載では、基礎技術から各ファイルシステムの特徴、パフォーマンスを検証する
	特集：全貌を現したLinuxカーネル2.6［第1章］ エンタープライズ向けに刷新されたカーネル・コア ついに全貌が明らかになったカーネル2.6。6月に正式リリースされる予定の次期安定版カーネルの改良点や新機能を詳しく解説する
	特集：/procによるLinuxチューニング［前編］ /procで理解するOSの状態 Linuxの状態確認や挙動の変更で重要なのが/procファイルシステムである。/procの概念や/procを利用したOSの状態確認方法を解説する
	特集：仮想OS「User Mode Linux」活用法 Linux上で仮想的なLinuxを動かすUMLの仕組みからインストール／管理方法やIPv6などに対応させるカーネル構築までを徹底解説
	Linuxのカーネルメンテナは柔軟なシステム カーネルメンテナが語るコミュニティとIA-64 Linux IA-64 LinuxのカーネルメンテナであるBjorn Helgaas氏。同氏にLinuxカーネルの開発体制などについて伺った
	more

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）