リード・コピー・アップデート

リード・コピー・アップデート（read-copy-update、RCUと略記）とは、オペレーティングシステムにおいて一種の排他制御^{[note 1]}を実装する同期機構であり、リーダー・ライターロック（英語版）の代替手段として使われることがある。参照において待ち状態が生じず、極めてオーバーヘッドが低い。しかしRCUにおけるデータ更新は、既存の参照者のために古い版のデータ構造を保持しつつ行うため、時間と空間（メモリ）をより多く必要とする。古い版のデータ構造は、既存の参照者が全てアクセスを完了した後で回収される。

概要

RCUでは「参照側クリティカルセクション」という概念があり、通常 rcu_read_lock() と rcu_read_unlock() で挟まれた部分がそれにあたる。参照側クリティカルセクション内にない文は「不活性状態」と呼ばれ、RCUで保護されたデータ構造への参照を保持することは許されない。データを共有するスレッド間で、少なくとも1つが不活性状態にある期間を「猶予期間」と呼ぶ。定義上、任意のRCU参照側クリティカルセクションが猶予期間の始まりに存在する場合、その猶予期間の終了までにクリティカルセクションが完了しなければならず、それがRCUの提供する根本的保証の前提となっている。この保証が参照側オーバーヘッドを極めて小さくすることがわかっており、実際サーバクラスのLinuxカーネルでの参照側オーバーヘッドはゼロである^[1]。

RCUの基本的な考え方は、更新を「削除」と「再利用」のフェーズに分割することである。削除フェーズではデータ構造内のデータへの参照を削除する（それらの参照を別のバージョンのデータ構造への参照に切り替える）。そうすることで参照側クリティカルセクションと並行して更新可能にする。削除フェーズが参照者と並行して動作できるのは、最近のCPUの設計によって参照者が新旧いずれかの版のデータ構造だけを参照することを保証できるためである（参照側クリティカルセクション内で参照するデータ構造の版が入れ替わることがない）。猶予期間が過ぎると、旧版のデータ構造を参照している参照者がいないと断定でき、旧版のデータを構成するアイテムを再利用フェーズで解放（再利用）しても安全である^[2]。

更新を削除と再利用のフェーズに分割することで、更新者は削除フェーズを速やかに行い、削除フェーズに入ったときに動作していた全ての参照者が停止するまで、言い換えれば猶予期間が過ぎるまで再利用フェーズを遅らせる^{[note 2]}。

典型的なRCUにおける更新は以下のような流れとなる^[3]。

RCUで保護されたデータ構造にアクセスする参照者は全てRCU参照側クリティカルセクション内で参照することを保証する。
データ構造へのポインタを削除して、その後の参照者がそれを参照できないようにする。
猶予期間が過ぎるのを待つ。それにより（前のフェーズで削除されたデータ構造へのポインタを持っている可能性のある）全ての参照者がRCU参照側クリティカルセクションを抜けるのを待つ。
この時点で更新したいデータ構造への参照を持つスレッドはいなくなるので、安全に再利用（たとえば、解放）できる^{[note 3]}。

このような手順において、更新者が削除と再利用のステップを実行するが、再利用については全く別のスレッドに任せた方が便利なことが多い。参照カウントを持たせることで、参照者が削除を行うこともできるので、更新ステップ（上記の (2)）と再利用ステップ（上記の (4)）が同じスレッドで行われるとしても、それらを分けて考えた方がわかりやすい。

利用

2008年初めごろの段階で、Linuxカーネル内では、ネットワーク・プロトコルスタック^[4]やメモリ管理システム^[5]など約2,000箇所で RCU API を利用している^[6]。 2006年以降、研究者らはRCUや類似の技法をいくつかの問題に適用してきた。例えば、動的解析に使用するメタデータの管理^[7]、クラスター型オブジェクトのライフタイム管理^[8]、K42研究OSでのオブジェクト管理^[9]^[10]、ソフトウェアトランザクショナルメモリ実装の最適化^[11]^[12]などである。DragonFly BSD はRCUによく似た技法を採用しており、Linuxの SRCU 実装に極めて近い。

長所と短所

RCUでは、全参照者が参照を終えるのを待つことができ、それによって非常に軽量な同期が可能で、場合よっては同期しないで参照することができる。対照的に一般のロックを使った方式では、参照者はオーバーヘッドの大きな同期機構を使って更新者が使用中のデータ構造を削除するのを防がなければならない。これはロックを使った更新者がその場でデータを更新するためであり、従って参照する者がいないことを保証する必要がある。一方RCUでは現代的CPUでは1つのポインタの書き換えがアトミックになされるという点を利用し、参照者をわずらわせずにデータ構造のリンクをアトミックに挿入・削除・置換する。RCUの参照者は旧版のデータを同時並行的に参照し続けることができ、不可分操作やメモリバリアやキャッシュミス(これらは今日のSMPコンピュータシステムではロックの衝突がなくても性能を低下させる)を排除できる^[13]^[14]。RCUの参照側の軽量さは単に性能向上、スケーラビリティ、リアルタイム応答性に寄与するだけではない。例えば、デッドロックやライブロック状態を防ぐことにも繋がる^{[note 4]}。

RCUには当然ながら短所もある。例えば、RCUは参照が多く更新が少ない状況に最適な技法であり、更新が頻繁に行われる状況には適していない。また、RCUは参照者と更新者が同時並行的に動作できることで参照側の同期機構を軽量化しているが、参照と更新の並行性がなじまないアルゴリズムも存在する。

RCUは10年以上に渡って使われているが、その応用範囲は正確には把握されておらず、今も研究対象となっている。

特許

この技術は米国のソフトウェア特許 5,442,758（1995年 8月15日、権利者はシークエント・コンピュータ）でカバーされている（他に 5,608,893、5,727,528、6,219,690、6,886,162）。すでに権利失効している特許 4,809,168 も非常に近い技術をカバーしていた。RCU はSCOとIBMの間の訴訟問題でも言及されている。

RCUインタフェースの例

RCUはいくつかのOSで利用可能であり、Linuxカーネルには2002年10月に追加された。liburcu などのユーザーレベルの実装も利用可能である^[15]。

Linuxカーネル 2.6 でのRCU実装はよく知られており、以下ではそれを元に RCU API について解説する。中核となるAPIは極めて小さい^[16]。

rcu_read_lock(): RCUで保護されたデータへの参照を開始することを示す。それによってクリティカルセクション期間中に対象データが再利用されないようにする。
rcu_read_unlock(): 参照者が使用し、参照者が参照側クリティカルセクションから出たことを更新者に通知する。RCUの参照側クリティカルセクションはネスト可能であり、オーバーラップ可能である。
synchronize_rcu(): 全CPU上の既存のRCU参照側クリティカルセクションが全て完了するまでブロックされる。synchronize_rcu は後続のRCU参照側クリティカルセクションを待つ必要はない。たとえば、以下のようなイベントの流れを考えてみよう。

	         CPU 0                  CPU 1                 CPU 2
	     ----------------- ------------------------- ---------------
	 1.  rcu_read_lock()
	 2.                    enters synchronize_rcu()
	 3.                                               rcu_read_lock()
	 4.  rcu_read_unlock()
	 5.                     exits synchronize_rcu()
	 6.                                              rcu_read_unlock()

synchronize_rcu は参照者が参照を完了したことを判定するAPIであり、RCU実装の要である。RCUは特に参照が多く更新が滅多にない場合に有効であり、synchronize_rcu のオーバーヘッドは極めて小さくなければならない。

ブロックする代わりに synchronize_rcu でコールバック関数と引数を登録し、動作中のRCU参照側クリティカルセクションが完了したときにそれがコールされるようにする実装もある。Linuxカーネルでは、このコールバック型のAPIを call_rcu と呼ぶ。

rcu_assign_pointer(): 更新者が使用し、更新者から参照者に安全に変化を伝え、RCUに保護されたポインタを更新する。この関数は、CPUアーキテクチャ上必要なメモリバリア命令を実行し、新たな値を返す。もっと重要な点として、この関数はどのポインタがRCUによって保護されているかを保証する。
rcu_dereference_pointer(): RCUに保護されたポインタをフェッチするために参照者が使用し、そのポインタが指している値を安全に得る。また、CPUアーキテクチャ上必要なメモリバリア命令も実行する。rcu_dereference_pointer が返す値はRCU参照側クリティカルセクション内でのみ有効である。rcu_assign_pointer との関連で rcu_dereference_pointer の重要な機能は、どのポインタがRCUで保護されているかを示すことである。

以下の図は各APIが参照者、更新者、再利用者の間でどう関係しているかを示している。

            rcu_assign_pointer()
                                    +--------+
            +---------------------->| 参照者 |---------+
            |                       +--------+         |
            |                           |              |
            |                           |              | 保護:
            |                           |              | rcu_read_lock()
            |                           |              | rcu_read_unlock()
            |        rcu_dereference()  |              |
       +---------+                      |              |
       | 更新者  |<---------------------+              |
       +---------+                                     V
            |                                    +-----------+
            +----------------------------------->| 再利用者  |
                                                 +-----------+
              遅延:
              synchronize_rcu() & call_rcu()

RCUの内部機構は rcu_read_lock, rcu_read_unlock, synchronize_rcu, call_rcu が呼び出された順番を記憶し、(1) synchronize_rcu がそれらの呼び出し側への戻りを設定するか、(2) call_rcu のコールバックが呼び出される順番を決定する。効果的な実装としては、各APIのオーバヘッドを減らして、背後でバッチ的に処理するほうがよい。

RCUの単純な実装

RCUのおもちゃ的な実装を考えるとRCUを理解しやすいだろう。ここではそのような簡単な実装を説明する。この実装はプリエンプション不可な環境でのみ動作することに注意^[17]。

	void rcu_read_lock(void) { }

	void rcu_read_unlock(void) { }

	void call_rcu(void (*callback) (void *), void *arg)
	{
		// add callback/arg pair to a list
	}

	void synchronize_rcu(void)
	{
		int cpu, ncpus = 0;

		for_each_cpu(cpu)
                        schedule_current_task_to(cpu);

                for each entry in the call_rcu list
                        entry->callback (entry->arg);
	}

rcu_assign_pointer と rcu_dereference_pointer を無視しても大勢に影響はないが、いずれにしろ、以下のようになる。

	#define rcu_assign_pointer(p, v)	({ \
							smp_wmb(); \
							(p) = (v); \
						})

	#define rcu_dereference_pointer(p)      ({ \
					        	typeof(p) _value = (p); \
					        	smp_rmb(); /* not needed on all architectures */ \
					        	(_value); \
					        })

rcu_read_lock と rcu_read_unlock は全く何もしない。プリエンプション不可な古いカーネルでは、このように参照側のオーバヘッドは全く無い（メモリバリアが必要となるのは DEC Alpha だけである^[18]）。したがって rcu_read_lock がデッドロック状態になることもなく、リアルタイムプロセスがスケジューリングのデッドラインに陥ることもなく、優先順位の逆転が発生することもなく、ロックの衝突が激しく発生することもない。

synchronize_rcu の実装は、synchronize_cpu を呼び出した者を各CPUに移動させ、全CPUでコンテキストスイッチ可能となるまでブロックさせる。プリエンプション不可なのでRCU参照側クリティカルセクション内でプリエンプションは発生せず、あるCPUで（他のプロセスをスケジュールする）コンテキストスイッチが起きたときにはそれ以前のRCU参照側クリティカルセクションは完了しているはずである。全CPUでコンテキストスイッチが起きたら、既存のRCU参照側クリティカルセクションが全て完了していることを保証できる。

リーダー・ライターロックとの比較

RCUはいろいろな使い方があるが、一般的な使い方はリーダー・ライターロックに近い。以下のふたつのコードはリーダー・ライターロック(左側)とRCU(右側)を同じ処理で使ったものである^[19]。

 1 struct el {                           1 struct el {
 2   struct list_head lp;                2   struct list_head lp;
 3   long key;                           3   long key;
 4   spinlock_t mutex;                   4   spinlock_t mutex;
 5   int data;                           5   int data;
 6   /* Other data fields */             6   /* Other data fields */
 7 };                                    7 };
 8 DEFINE_RWLOCK(listmutex);             8 DEFINE_SPINLOCK(listmutex);
 9 LIST_HEAD(head);                      9 LIST_HEAD(head);

 1 int search(long key, int *result)     1 int search(long key, int *result)
 2 {                                     2 {
 3   struct el *p;                       3   struct el *p;
 4                                       4
 5   read_lock(&listmutex);              5   rcu_read_lock();
 6   list_for_each_entry(p, &head, lp) { 6   list_for_each_entry_rcu(p, &head, lp) {
 7     if (p->key == key) {              7     if (p->key == key) {
 8       *result = p->data;              8       *result = p->data;
 9       read_unlock(&listmutex);        9       rcu_read_unlock();
10       return 1;                      10       return 1;
11     }                                11     }
12   }                                  12   }
13   read_unlock(&listmutex);           13   rcu_read_unlock();
14   return 0;                          14   return 0;
15 }                                    15 }

 1 int delete(long key)                  1 int delete(long key)
 2 {                                     2 {
 3   struct el *p;                       3   struct el *p;
 4                                       4
 5   write_lock(&listmutex);             5   spin_lock(&listmutex);
 6   list_for_each_entry(p, &head, lp) { 6   list_for_each_entry(p, &head, lp) {
 7     if (p->key == key) {              7     if (p->key == key) {
 8       list_del(&p->lp);               8       list_del_rcu(&p->lp);
 9       write_unlock(&listmutex);       9       spin_unlock(&listmutex);
                                        10       synchronize_rcu();
10       kfree(p);                      11       kfree(p);
11       return 1;                      12       return 1;
12     }                                13     }
13   }                                  14   }
14   write_unlock(&listmutex);          15   spin_unlock(&listmutex);
15   return 0;                          16   return 0;
16 }                                    17 }

両者の違いは非常に小さい。参照側のロックは rcu_read_lock() と rcu_read_unlock() になり、更新側のロックはリーダー・ライターロックから単純なスピンロックに変更され、kfree()を実行するまえに synchronize_rcu() が呼び出される。

しかし、この場合参照側と更新側が同時に動作する可能性が出てくる。多くの場合はこれは問題とはならないが、使われ方を十分注意する必要がある。たとえば、複数の独立したリストをアトミックに更新しなければならない場合、これをRCUに置き換えるには注意が必要である。

synchronize_rcu() があるということはRCUでは delete() がブロックされる可能性があることを示す。それが問題となる場合は代わりに call_rcu() を call_rcu (kfree, p) のように使用すればよい。これは参照カウントと組合わせる場合に特に便利である。