リード・コピー・アップデート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
リード・コピー・アップデート(read-copy-update、RCUと略記)とは、複数のCPUを持つコンピュータにおけるオペレーティングシステムのカーネル技術のひとつであり、性能向上を目的としている。 RCUはデータ構造が複数のスレッドに共有されているときに使われ、特にそのデータがよく参照(リード)されて滅多に更新(アップデート)されない場合に有効である。 あるスレッドがそのデータ構造を読みたい場合、そのデータ構造を指すポインタを使用し、特にロックを使ったりチェックしたりといった操作は必要とされない。 これによりデータ構造は共有されていないデータ構造と全く同じに扱うことができる。 しかし、RCUは更新が頻繁に発生する状況を想定した設計ではないので、更新は時間がかかる。
RCU は、Linuxカーネルのバージョン 2.6 など、いくつかのオペレーティングシステムで使用可能である。 この技術は米国のソフトウェア特許 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の基本的な考え方は、更新を「削除」と「再設定」のフェーズに分割することである。 削除フェーズではデータ構造内のデータへの参照を削除する(それらの参照を別のバージョンのデータ構造への参照に切り替える)。 そうすることで参照しようとするものと並行して動作させる。 削除フェーズが並行して参照者と共存できるのは、最近のCPUの設計によって参照者が(変更中の元のデータ構造ではなく)別バージョンのデータ構造を参照することを保証できるためである。 再設定フェーズでは、削除フェーズで「削除」されたデータ構造を再設定する。 再設定中のデータ構造を参照されると動作が保証できないので、再設定フェーズは必ず参照者が再設定対象のデータ構造のアドレスを保持していないことを確認してから行わなければならない。
更新を削除と再設定のフェーズに分割するには、更新者は削除フェーズを速やかに行い、削除フェーズに入ったときに動作していた全ての参照者が停止するまで再設定フェーズを遅らせる。このために新たな参照者はブロックさせるか、コールバック関数を設定して待たせる。 これにより、削除フェーズに入ったときにすでに参照に入っていたものだけが問題となる。というのは削除フェーズが開始してから参照をしようとしたものは削除されたデータにはアクセスできず、再設定フェーズにも影響しないからである。
典型的なRCUにおける更新は以下のような流れとなる。
- データ構造へのポインタを削除して、その後の参照者がそれを参照できないようにする。
- 全ての参照者がRCUの参照側クリティカルセクションを抜けるのを待つ。
- この時点で更新したいデータ構造への参照を持つスレッドはいなくなるので、安全に再設定(たとえば、Linuxカーネルでは kfree() を使って解放する)できる。
上記の ステップ(2) が RCUの遅延破壊の鍵となるアイデアである。 全ての参照者を待つことにより、参照者側は非常に高速な同期の恩恵にあずかり、全く同期する必要がない場合もある。 対照的に、一般的なロックを使った方法では、参照者は重い同期手法を使ってデータ構造を削除しようとするスレッドが同時に動作することを防がなければならない。 これは、ロックを使った場合データをその場で更新するので参照者を排除しなければならないからである。 対照的にRCUベースの更新は、最近のCPUではひとつのポインタをアトミックに変更できることを利用して、リンク構造からアトミックにデータを挿入したり削除したりして参照者の動作を妨げないようにする。 並行動作するRCUの参照者は古いバージョンのデータを参照でき、アトミック操作やメモリバリアやキャッシュミス(これらは今日のSMPコンピュータシステムではロックの衝突がなくても性能を低下させる)を排除できる。
前述の3段階の処理では、更新は削除と再設定をする必要があるが、再設定を別のスレッドがやってくれるならその方が便利なことが多々ある。Linuxカーネルでは、ディレクトリエントリキャッシュ(dcache)の動作がそのようになっている。 同じスレッドが両方(削除(1)と再設定(3))を行う場合でも、それらを分けて考える方がわかりやすい。 たとえば、RCUの参照と更新は全く通信する必要がないが、RCUは負荷の少ない暗黙の通信を前述の3段階のステップ(2)で行っている。
では、更新者は何も同期機構を使わずにどうやって参照者が処理を終えたことを知るのだろうか？ それは後述する。
[編集] RCUの基本API
LinuxカーネルのRCUの基本API(Application Programming Interface)は非常に小さい。
- rcu_read_lock()
- rcu_read_unlock()
- synchronize_rcu() / call_rcu()
- rcu_assign_pointer()
- rcu_dereference()
Linuxカーネルは他にもRCU関連APIを持っている。
[編集] rcu_read_lock()
参照者が使用し、更新者に対して参照者が参照側クリティカルセクションに入ったことを通知する。 RCUで保護されたデータ構造がRCUの参照側クリティカルセクションにおいて参照されている間は再設定されずに残ることを保証される。 他の手法では、参照カウントをRCUと共に使用して長期間の参照に対応したりする。
[編集] rcu_read_unlock()
参照者が使用し、参照者が参照側クリティカルセクションから出たことを更新者に通知する。 RCUの参照側クリティカルセクションはネスト可能であり、オーバーラップ可能である。
[編集] synchronize_rcu() / call_rcu()
更新が終わって再設定が始まったことを示す。 既存の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()
この場合、CPU 0の参照側クリティカルセクションの完了だけを待ち、CPU 2が後からクリティカルセクションに入っても、そちらは待たない。
もちろん、synchronize_rcu() は、既存のRCU参照側クリティカルセクションが完了したら即座に呼び出したところに戻る必要はない。 たとえば、スケジューリングによって遅らせることもありうる。 また、多くのRCUの実装例ではバッチの処理効率を上げるために使われており、その場合 synchronize_rcu() はずっと遅らせられる。
synchronize_rcu() は参照が終わったことを判断しなければならず、それをどう実装するかがRCUの鍵である。 RCUは参照の多い状況で効果があり、その意味で synchronize_rcu() の負荷は小さくなければならない。
call_rcu() API は、コールバック型の synchronize_rcu() であり、後で詳述する。 ブロックする代わりに関数と引数を登録し、動作中のRCU参照側クリティカルセクションが完了したときにそれがコールされるようにする。このコールバックはブロックできない状況の場合に便利である。
[編集] rcu_assign_pointer()
更新者が使用し、更新者から参照者に安全に変化を伝え、RCUに保護されたポインタを更新する。 この関数は、CPUアーキテクチャ上必要なメモリバリア命令を実行し、新たな値を返す。 もっと重要な点として、この関数はどのポインタがRCUによって保護されているかを保証する。
[編集] rcu_dereference()
参照者が使用し、RCUに保護されたポインタを得る。 rcu_deference() は実際のポインタを参照するわけではなく、その後の参照を保護するのである。 また、CPUアーキテクチャ上必要なメモリバリア命令も実行する。 現状ではAlphaだけがメモリバリア命令を必要とし、他のCPUでは何もしない。
rcu_dereference() の返す値はRCU参照側クリティカルセクション内でのみ有効である。 たとえば以下のようなコードは不正である。
rcu_read_lock();
p = rcu_dereference(head.next);
rcu_read_unlock();
x = p->address;
rcu_read_lock();
y = p->data;
rcu_read_unlock();
参照をひとつのRCU参照側クリティカルセクションから別のクリティカルセクションに持ち越すことはできない。 同様にクリティカルセクション外で参照を行うこともできない。
rcu_assign_pointer()と同様、rcu_dereference() もRCUで保護されたポインタを保証するものである。
[編集] RCU API間の関係
以下の図は各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_kernel(), call_rcu() が呼び出された順番を記憶し、(1) synchronize_kernel() がそれらの呼び出し側への戻りを設定するか、(2) call_rcu() のコールバックが呼び出される順番を決定する。 効果的な実装としては、各APIのオーバヘッドを減らして、背後でバッチ的に処理するほうがよい。
[編集] RCUの単純な実装
RCUのおもちゃ的な実装を考えるとRCUを理解しやすいだろう。 ここではそのような簡単な実装を説明する。 この実装は non-preemptive な環境でのみ動作することに注意。
void rcu_read_lock(void) { }
void rcu_read_unlock(void) { }
void synchronize_rcu(void)
{
int cpu;
for_each_cpu(cpu)
run_on(cpu);
}
#define rcu_assign_pointer(p, v) ({ \
smp_wmb(); \
(p) = (v); \
})
#define rcu_dereference(p) ({ \
typeof(p) _________p1 = p; \
smp_read_barrier_depends(); \
(_________p1); \
})
rcu_read_lock() と rcu_read_unlock() は全く何もしない。 non-preemptive な古いカーネルではこのように参照側のオーバヘッドは全く無い(少なくとも Alpha CPU 以外では)。 したがって、rcu_read_lock() がデッドロック状態になることもない。 synchronize_rcu()は単純に全てのCPUで自身が動作するようにスケジュールする。 run_on() は sched_setaffinity() のような形で実装できるだろう。 もちろん、もう少し高級な実装をするなら、CPUを無理やり全て奪うのではない方法をとるだろう。
さて、これでどう動作するだろうか？
RCU参照側クリティカルセクションにあるスレッドをブロックすることはできない。 したがって、各CPUがコンテキストスイッチをするということは、RCU参照側クリティカルセクションを抜け出したことを意味する。 全てのCPUでコンテキストスイッチが実行されたら、既存のクリティカルセクションは全て抜けたことが保証される。
そこで、データを削除して synchronize_rcu() を呼び出す。 synchronize_rcu() から戻ってきたら RCU参照側クリティカルセクションが動作していないことが保証され、安全に再設定できるのである。
[編集] リーダー・ライターロックとの比較
RCUはいろいろな使い方があるが、一般的な使い方はリーダー・ライターロックに比較される。 以下のふたつのコードはリーダー・ライターロック(左側)とRCU(右側)を同じ処理で使ったものである。
1 struct el { 1 struct el {
2 struct list_head list; 2 struct list_head list;
3 long key; 3 long key;
4 spinlock_t mutex; 4 spinlock_t mutex;
5 int data; 5 int data;
6 /* 他のデータフィールド */ 6 /* 他のデータフィールド */
7 }; 7 };
8 rwlock_t listmutex; 8 spinlock_t listmutex;
9 struct el head; 9 struct el head;
1 int search(long key, int *result) 1 int search(long key, int *result)
2 { 2 {
3 struct list_head *lp; 3 struct list_head *lp;
4 struct el *p; 4 struct el *p;
5 5
6 read_lock(); 6 rcu_read_lock();
7 list_for_each_entry(p, head, lp) { 7 list_for_each_entry_rcu(p, head, lp) {
8 if (p->key == key) { 8 if (p->key == key) {
9 *result = p->data; 9 *result = p->data;
10 read_unlock(); 10 rcu_read_unlock();
11 return 1; 11 return 1;
12 } 12 }
13 } 13 }
14 read_unlock(); 14 rcu_read_unlock();
15 return 0; 15 return 0;
16 } 16 }
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->list); 8 list_del(&p->list);
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() を使用すればよい(訳注：コールバック関数の引数に p(の値) を指定して、kfree(p) を実行する)。
[編集] リード・コピー・アップデートと呼ばれる理由
この名称はRCUがリンクリストをその場で更新するのに使われていたことに由来する。 この場合、以下のような処理の流れとなる。
- 新しい構造体を作成する。
- データを古い構造体からコピーし、古いデータ構造へのポインタをセーブする。
- 新しいデータ構造に更新(変更)を加える。
- グローバルなポインタが新しいデータ構造の方を指すよう変更する。
- カーネルが古いデータ構造の参照者がいないと判断するまでスリープする(Linuxなら synchronize_rcu() を使用する)。
更新を行ったスレッドがカーネルによって起こされたら、安全に古いデータ構造を解放できる。
そのため、参照(read)スレッドは、更新(update)スレッドがコピー(copy)している間も並行して動作できる。 以上から、「リード・コピー・アップデート(read-copy update)」と呼ばれたのである。
