RCU（Read-Copy-Update）の原理

RCUが解く問題──読み取りが多すぎる

多くのカーネルデータ構造は、読み取りが圧倒的に多く、更新がまれ です。ルーティングテーブル、デバイスのリスト、各種設定。これらは1秒に何百万回も読まれる一方、書き換えは数秒〜数分に一度しか起きません。

ここで素朴にリーダーライターロックを使うと、読み取りのたびにロックのカウンタへアトミック操作 が走ります。アトミック操作はキャッシュラインを各コアで奪い合うため、コア数が増えるほど遅くなる。読むだけなのに、読み手同士がスケールしないのです。

RCU（Read-Copy-Update） は、この前提を逆手に取ります。読み取り側からロックもアトミック操作も書き込みも完全に取り除き、コストのしわ寄せをすべて「まれな更新側」へ寄せる。これがRCUの基本思想です。

読み取り側：ただのポインタ参照に同期を載せる

RCUの読み取りは、クリティカルセクションを区切るだけ です。Linuxでは rcu_read_lock() と rcu_read_unlock() で囲みますが、これらは名前に反して ロックを取りません。プリエンプション無効化などの軽い印を付けるだけで、多くの構成では実質ノーオペレーションに近いコストです。

rcu_read_lock();
p = rcu_dereference(gp);   /* 共有ポインタを安全に読む */
if (p)
    do_something(p->field);
rcu_read_unlock();

ここで本質的に効いているのは rcu_dereference() です。これは ポインタ経由のデータ依存を守るためのフェンス相当 で、「ポインタ p を読んでから p->field を読む」順序が、CPUの並べ替えで崩れないことを保証します。詳しい背景は メモリオーダリングとメモリバリア を参照してください。

publish-subscribe：新版を「安全に公開する」

更新側が新しいデータを作って差し替えるとき、危ないのは 初期化がまだ他コアに見えていないのに、ポインタだけ先に見えてしまう ことです。new->field への書き込みより、gp = new のポインタ書き込みが先に他コアへ届くと、読み手が未初期化のフィールドを掴みます。

これを防ぐのが publish-subscribe パターン です。公開側は rcu_assign_pointer()、購読側は前述の rcu_dereference() を使い、「中身を全部書き終えてからポインタを差し替える」順序 をペアで保証します。

/* 更新側（publish） */
new = kmalloc(sizeof(*new), GFP_KERNEL);
new->a = 1;
new->b = 2;
rcu_assign_pointer(gp, new);   /* ここまでの初期化が先に見える */

rcu_assign_pointer() は内部的にリリース相当のバリアを発行し、rcu_dereference() 側のデータ依存と対になって、初期化 → 公開 → 参照 → フィールド読み の順序を成立させます。読み手は古い版か新しい版か、どちらか 完全な版 だけを見るのであって、中途半端な版を見ることはありません。

grace period とクォースセント状態──いつ旧版を捨てられるか

新版を公開した後、旧版を読んでいる読み手 がまだ残っています。彼らがいる間に旧版を解放するとダングリングポインタになる。では「もう誰も旧版を見ていない」とどう判定するのか。ここがRCUの心臓部です。

RCUは個々のポインタを追跡しません。代わりに grace period（猶予期間） という時間区間で考えます。grace periodとは、公開時点で進行中だった読み取りクリティカルセクションが、すべて完了するまで の期間です。

その判定材料が クォースセント状態（quiescent state、静止状態） です。あるCPUがクォースセント状態にあるとは、そのCPUが今この瞬間、いかなるRCU読み取りクリティカルセクションの中にもいない と保証できることを指します。古典的（非プリエンプト）RCUでは、次のような瞬間がクォースセント状態の目印になります。

• コンテキストスイッチ が起きた（読み取り区間はスイッチをまたがない）
• ユーザー空間で実行している
• アイドルループに入っている

更新側はこの grace period の完了を待ってから、旧版を解放します。待ち方には2通りあります。

/* 更新側の典型形：差し替え → 待つ → 解放 */
old = gp;
rcu_assign_pointer(gp, new);
synchronize_rcu();   /* 旧版を読む全読み手が抜けるまで待つ */
kfree(old);          /* ここで安全に解放できる */

リーダーライターロックとの本質的な違い

同じ「読み多・書き少」を狙う両者ですが、設計思想は正反対です。

最大の違いは、RCUでは 更新が読み手をブロックしない ことです。リーダーライターロックは書き手と読み手が排他しますが、RCUは新旧2版を共存させるため、更新の真っ最中でも読み手はノンストップ で走り続けます。読み手から見ればロックの存在自体が消えるのです。関連する排他制御全般の整理は 排他制御とデッドロック を参照してください。

なぜLinuxカーネルで大量採用されたのか

Linuxカーネルには現在、数千か所のRCU利用箇所があります。理由は、カーネルの典型パターンとRCUの得意分野が一致する からです。

• 読み取り経路がとにかく多い：パケット転送のたびのルーティング表参照、open のたびのファイルディスクリプタ表、ネットワーク名前空間やモジュールリストの走査など、ホットパスのほとんどが読み取り主体。
• メニーコアでスケールさせたい：コア数が数十〜数百になると、読み取りごとのアトミック操作がそのままボトルネックになる。RCUの読み手は競合ゼロなので、コアを足すほど性能が伸びる。
• 既存のロックを置き換えやすい：リスト走査やハッシュ表参照を rcu_read_lock() で囲み、更新を publish-subscribe と call_rcu() に変えるだけで、APIの形を大きく変えずに移行できる。

読み取り（ホットパス）          更新（まれ）
  rcu_read_lock()                新版を作成・初期化
  p = rcu_dereference(gp)        rcu_assign_pointer(gp, new)
  ... use p ...                  synchronize_rcu() / call_rcu()
  rcu_read_unlock()              旧版を解放
   └ 競合なし・ほぼ無料           └ grace period を待つぶん高い

まとめ