RCUの実装詳細（grace period検出とコールバック）

なぜ実装が難しいのか──「全CPUの静止」を数百コアで検出する

RCUの原理は「公開後に全CPUがクォースセント状態（QS、読み取り区間の外にいると保証できる瞬間）を一度ずつ通過すれば、grace period（GP、猶予期間）が完了する」というものです。原理そのものは RCUの原理 で扱いました。本記事はその一段下、「数百コアで、誰がいつ静止したかをどう集約し、いつGPを終わらせ、貯まったコールバックをどう処理するか」 という実装の核心を追います。

素朴に実装するなら、GPごとに「未報告CPUのビットマスク」を1つ用意し、各CPUが静止するたびに自分のビットを下ろし、全ビットが0になったらGP完了とすればよさそうです。しかしこれは メニーコアで即座に破綻 します。1つのマスクを保護する1つのロックを、数百コアが静止のたびに奪い合うため、そのキャッシュラインがコア間を行き来し続ける（バウンシング）。RCUは読み取りを限界まで軽くするのが目的なのに、GP検出の側で別のスケーラビリティ問題を作ってしまうのです。

rcu_nodeツリー──ロック競合を部分木に閉じ込める

Tree RCUの中心的アイデアは、CPU群を木構造に分割し、ロックの取り合いを各部分木の内側に閉じ込める ことです。1枚のフラットなビットマスクの代わりに、rcu_node 構造体を多分木（典型的な扇出は64、CONFIG_RCU_FANOUT）に組みます。

                 [ root rcu_node ]          ← 全体のGP状態を集約
                /        |        \
        [ rcu_node ] [ rcu_node ] [ rcu_node ]   ← 中間ノード（大規模時）
         /   |   \
   CPU0  CPU1 ... CPU63                       ← 葉ノード1つが最大64CPUを束ねる
   （各CPUは rcu_data を1つ持つ）

各 rcu_node は、自分の子（下位ノードまたはCPU）のうち まだ当該GPで静止していないもの をビットマスク qsmask で持ちます。CPUが静止すると、まず自分が属する 葉ノードのロックだけ を取って自分のビットを下ろす。これで全ビットが0になったら、初めて1つ上の親へ「この部分木は全員静止した」と報告し、親のビットを下ろしにいきます。

データ構造の役割分担は次のとおりです。

QSの検出──いつ「このCPUは静止した」と言えるか

葉ノードのビットを下ろす前提として、そのCPUが本当にQSを通過したか を判定する必要があります。非プリエンプトRCUでは コンテキストスイッチ・ユーザ空間実行・アイドルがQSの目印でした。Tree RCUはこれを能動的に回収する仕組みを持ちます。

• スケジューラティック（rcu_check_callbacks 相当）：周期タイマ割り込みのたびに、そのCPUがユーザ空間にいたか、あるいはアイドルだったかを調べ、QSなら記録する。
• コンテキストスイッチ：プロセススケジューリング が走るたびにQSとして報告される。
• プリエンプタブルRCU（CONFIG_PREEMPT_RCU）：読み取り区間内でのプリエンプションを許すため、QSの定義が変わる。rcu_read_lock() がカウンタを上げ、区間内でプリエンプトされたタスクは葉ノードの blkd_tasks リストに繋がれ、そのタスクが rcu_read_unlock() を実行するまでQSにならない。区間内で寝てよくなった代償として、ブロック中タスクの追跡が要るわけです。

grace period状態機械──rcu_gp_kthreadが回す

GPの開始・監視・終了は、システムに1つだけある専用カーネルスレッド rcu_gp_kthread が状態機械として駆動します。CPUごとに勝手にGPを進めるのではなく、1点に制御を集約することで、GP番号の整合とツリー初期化を一貫させています。GPは大きく3フェーズで進みます。

（待機）── コールバックが現れる ──▶ [GP-INIT]
   [GP-INIT]  グローバルgp_seqを進め、ツリー全rcu_nodeのqsmaskを
              「全CPU未報告」に初期化（新しいGPの開始を宣言）
        │
        ▼
   [QS-WAIT]  各CPUがQSを報告 → 葉のビットdown → 全部0なら親へ伝播
              rcu_gp_kthreadは周期的にforce_quiescent_state()で
              停滞CPUへIPIを送り、報告を促す
        │  rootのqsmaskが空になった＝全CPUが静止を通過
        ▼
   [GP-CLEANUP]  gp_seqを「完了」へ進め、各CPUのrcu_dataに
                 「このGPは完了した」と記録。待っていたコールバックを
                 「実行可能」へ移し、softirq/rcuocを起こす
        │
        ▼
（待機に戻る。保留コールバックが残っていれば次のGPを即開始）

ここで効くのが gp_seq（GPシーケンス番号） です。GP番号を単調増加のカウンタで持ち、下位ビットで「GP進行中か完了済みか」の位相を表します。各CPUの rcu_data は「自分が待っているGP番号」を覚えており、グローバルな gp_seq がそれを追い越したかを比較するだけで「自分の待ちGPは完了したか」を ロックなしで判定 できます。個々のコールバックにGP番号の刻印（スタンプ）を付け、番号比較で完了を見るこの方式が、コールバック処理全体の土台です。

call_rcuとコールバック処理──貯めて、待って、一括で流す

更新側が call_rcu(head, func) を呼ぶと、func は その場では実行されません。GP完了後に非同期で呼ぶのがこのAPIの役目で、割り込みハンドラ のように待てない文脈から安全に解放を予約できます。処理の流れはこうです。

1. 登録：call_rcu はコールバックを 呼び出したCPUの rcu_data のリスト へ繋ぐ。グローバルなロックを取らずper-CPUで完結するため、登録は極めて軽い。
2. GPとの紐付け：そのコールバックには「現在進行中（または次の）GP番号」が割り当てられる。rcu_segcblist（セグメント化コールバックリスト）が、コールバックを「DONE（実行可能）／WAIT（このGPを待つ）／NEXT（次のGPを待つ）」のセグメントに区分けして管理する。
3. GP完了の波及：rcu_gp_kthread がGPを終えると、各CPUのリストで「そのGPを待っていた」セグメントが DONEへ昇格 する。
4. 実行：DONEになったコールバックを、RCU_SOFTIRQ（ソフト割り込み文脈）で、あるいは設定により専用スレッド rcuoc（callback-offload kthread） が、一括して呼び出す。

/* 更新側：call_rcu は即座に戻り、解放はGP後に肩代わりされる */
void replace(struct foo *new) {
    struct foo *old = rcu_dereference_protected(gp, lockdep_is_held(&lock));
    rcu_assign_pointer(gp, new);   /* 新版を公開 */
    call_rcu(&old->rcu, free_foo); /* old は GP 完了後に free_foo で解放 */
    /* ここで戻る。ブロックしない */
}

RCUの派生──SRCUとTasks RCU

基本のTree RCUには「読み取り区間内で寝てはいけない」「QSはスケジューラ事象で取る」という制約があります。用途に合わせてQSの定義そのものを差し替えたのが派生RCUです。

SRCU はGPを ドメイン（srcu_struct）ごとに分離 するのが核心です。srcu_read_lock() はper-CPUカウンタを上げ、unlock で下げる。GP検出は「世代を切り替え、旧世代のカウンタ合計が読み手の入った数と一致した（＝旧世代の読み手が全員抜けた）」ことで行います。区間内で寝てもよい代わりに、読み手は軽量ながら 実際にper-CPUカウンタを操作する（純粋なTree RCUの読み手は何も書かない）点が対価です。ドメインを分けることで、ある経路の長い読み手が無関係な経路のGPを巻き込んで遅らせる事態を避けられます。

Tasks RCU は、call_rcu では追えない対象——具体的には ftraceがコード書き換えで挿入する「トランポリン」 の安全な回収のために生まれました。トランポリンは rcu_read_lock() で囲めない素のコード片なので、QSを「各タスクが一度でも自発的にスケジューラを通過したか」と再定義し、現在トランポリン上を走っているタスクがいなくなった ことを保証します。

まとめ──分割集約・状態機械・バッチングの三段構え