以下は、２０１６年４月時点の Linux カーネル文書、Documentation/RCU/Design/Requirements/Requirements.html の kanda.motohiro@gmail.com による全訳です。原文と同じ、GPL v2 で公開します。google site に置く都合で、原文のHTMLタグなどは忠実に再現していません。RCU については、同じ作者の、perfbook の９章が詳しいです。
RCUの要件をめぐる旅
Copyright IBM Corporation, 2015
Author: Paul E. McKenney
この文書の最初の版は、 LWN 記事 ここ, ここ, そして ここ に載りました。
前書き
リードコピーアップデート(RCU)は、リーダーライターロックの代わりにしばしば使われる同期機構です。RCUは、更新者がリーダーをブロックしないという点で特別です。これは、RCUのリード側プリミティブが極めて速くスケーラブルであり得ることを意味します。さらに、更新者はリーダーと同時実行して、有意義な前方進行ができます。しかし、RCUリーダーと更新者の間のこのような同時実行は、いったい、RCUリーダーは正確に何をしているのだろうかという疑問を起こすでしょう。それはさらに、RCUの要件は正確に何であるかという疑問を起こします。
なのでこの文書は、RCUの要件をまとめます。そしてこれは、形式的でない、RCUの高レベル仕様と考えることができます。RCUの仕様はその性質上、主に経験的であることを理解するのは重要です。実は私は、これら要件の多くを厳しい方法で学びました。この状況はかなりの驚きかもしれません。しかし、この学習プロセスはとても楽しかっただけでなく、技術を興味深い新しい方法で適用しようと望む多くの人々と作業をするのは素晴らしい特権でもありました。
さて、それは置いといて、以下が現在知られているRCUの要件のカテゴリーです。
１ 基本的要件
２ 基本的に、要件でないもの
３ 並列性の人生の真実
４ 実装の質に関する要件
５ Linuxカーネルがもたらす複雑さ
６ ソフトウェアエンジニアリング要件
７ その他のRCUフレーバー
８ 将来あり得る変化
この後にまとめがあります。さらにその後に、必要不可欠のクイッククイズの答えがあります。
基本的要件
RCUの基本的要件は、厳格な数学的要件に最も近いです。それは:
１ グレースピリオド保証
２ パブリッシュサブスクライブ保証
３ メモリバリア保証
４ RCUプリミティブは無条件に実行することが保証されます
５ リードからライトのアップグレードは保証されます
グレースピリオド保証
RCUのグレースピリオド保証は、計画的だったという点で特別です。Jack Slingwine と私が１９９０年代初めに、RCU(当時は “rclock” と呼ばれました)の作業を始めた時から、私たちはこの保証を確かに心に持っていました。とは言え、過去２０年のRCUの経験は、この保証について、ずっと詳しい理解をもたらしました。
RCUのグレースピリオド保証は、更新者が全ての既存のRCUリード側クリティカルセクションの完了を待つのを可能とします。RCUリード側クリティカルセクションは、マーカー rcu_read_lock() で始まり、マーカー rcu_read_unlock() で終わります。これらのマーカーはネストしても良く、RCUはネストしたセットを、一つの大きなRCUリード側クリティカルセクションとして扱います。 rcu_read_lock() と rcu_read_unlock() の本番品質の実装は極めて軽量で、CONFIG_PREEMPT=n を使って本番用にビルドされたLinuxカーネルでは、実際に、正確にゼロオーバーヘッドを持ちます。
この保証は、リーダーにとって極めて低いオーバーヘッドでオーダリングを強制できます。例えば:
1 int x, y;
2
3 void thread0(void)
4 {
5 rcu_read_lock();
6 r1 = READ_ONCE(x);
7 r2 = READ_ONCE(y);
8 rcu_read_unlock();
9 }
10
11 void thread1(void)
12 {
13 WRITE_ONCE(x, 1);
14 synchronize_rcu();
15 WRITE_ONCE(y, 1);
16 }
１４行目の synchronize_rcu() は、全ての既存のリーダーを待つので、x から値ゼロをロードした thread0() の全てのインスタンスは、thread1() が y にストアする前に完了しなければいけません。このため、そのインスタンスはy からも値ゼロをロードしなくてはいけません。同様に、y から値１をロードした thread0() の全てのインスタンスは、synchronize_rcu() が開始した後に開始したはずです。このため、x からも値１をロードしなくてはいけません。なので、このような結果は起きることがあり得ません。
(r1 == 0 && r2 == 1)
クイッククイズ１：
待ってください！あなたは、更新者はリーダーと同時実行して有意義な前方進行ができると言いました。しかし、既存のリーダーは synchronize_rcu() をブロックします！！！あなたは私をだますつもりですか？？？
このシナリオは、 DYNIX/ptx でのRCUの最初の用途の一つに似ています。それは、分散ロックマネージャがノード障害からの回復を行うのに適した状態に遷移するのを管理しました。大まかにこんなものです。
1 #define STATE_NORMAL 0
2 #define STATE_WANT_RECOVERY 1
3 #define STATE_RECOVERING 2
4 #define STATE_WANT_NORMAL 3
5
6 int state = STATE_NORMAL;
7
8 void do_something_dlm(void)
9 {
10 int state_snap;
11
12 rcu_read_lock();
13 state_snap = READ_ONCE(state);
14 if (state_snap == STATE_NORMAL)
15 do_something();
16 else
17 do_something_carefully();
18 rcu_read_unlock();
19 }
20
21 void start_recovery(void)
22 {
23 WRITE_ONCE(state, STATE_WANT_RECOVERY);
24 synchronize_rcu();
25 WRITE_ONCE(state, STATE_RECOVERING);
26 recovery();
27 WRITE_ONCE(state, STATE_WANT_NORMAL);
28 synchronize_rcu();
29 WRITE_ONCE(state, STATE_NORMAL);
30 }
do_something_dlm() の、RCUリード側クリティカルセクションは start_recovery() の synchronize_rcu() と協調して、do_something() が、recovery() と決して同時に走らないことを保証します。しかも、do_something() へのオーバーヘッドは小さいかあるいは全くありません。
クイッククイズ２：
なぜ、２８行目の synchronize_rcu() は必要ですか？
デッドロックのような致命的な問題を避けるために、RCUリード側クリティカルセクションは synchronize_rcu() への呼び出しを含んではいけません。同様に、RCUリード側クリティカルセクションは、直接的にも間接的にも、synchronize_rcu() の呼び出しの完了を待つものを含んではいけません。
RCUのグレースピリオド保証はそれ自身、単独でも便利で、多くのユースケースがあります。しかし、RCUを使って、連結データ構造へのリード側アクセスを調停することができたら良いでしょう。このためには、グレースピリオド保証は不十分です。それは、以下の add_gp_buggy() 関数でわかります。後でリーダーのコードは見ますが、今のところはリーダーはロックなしに gp ポインタをピックアップして、ロードした値がNULL でないなら、->a と ->b フィールドをロックなしにアクセスすると考えましょう。
1 bool add_gp_buggy(int a, int b)
2 {
3 p = kmalloc(sizeof(*p), GFP_KERNEL);
4 if (!p)
5 return -ENOMEM;
6 spin_lock(&gp_lock);
7 if (rcu_access_pointer(gp)) {
8 spin_unlock(&gp_lock);
9 return false;
10 }
11 p->a = a;
12 p->b = a;
13 gp = p; /* ORDERING BUG */
14 spin_unlock(&gp_lock);
15 return true;
16 }
問題は、コンパイラと弱いオーダリングのCPUの両方は、自分の権限でこのコードを以下のようにリオーダーすることができることです。
1 bool add_gp_buggy_optimized(int a, int b)
2 {
3 p = kmalloc(sizeof(*p), GFP_KERNEL);
4 if (!p)
5 return -ENOMEM;
6 spin_lock(&gp_lock);
7 if (rcu_access_pointer(gp)) {
8 spin_unlock(&gp_lock);
9 return false;
10 }
11 gp = p; /* ORDERING BUG */
12 p->a = a;
13 p->b = a;
14 spin_unlock(&gp_lock);
15 return true;
16 }
もしRCUリーダーが dd_gp_buggy_optimized が１１行目を実行したすぐ後に gp をフェッチしたら、それは、->a と ->b フィールドにゴミを見るでしょう。そしてこれは、コンパイラとハードウェア最適化が面倒を起こす多くの方法の一つでしかありません。なので、明らかに、コンパイラとCPUがこのようなリオーダリングをするのを防ぐ何らかの方法が必要です。それは私たちを、次の節で議論するパブリッシュサブスクライブ保証に連れて行きます。
パブリッシュサブスクライブ保証
RCUのパブリッシュサブスクライブ保証は、RCUリーダーをじゃませずに、データを連結データ構造に挿入するのを可能とします。更新者は新しいデータを挿入するために rcu_assign_pointer() を使い、リーダーは新しいか古いかにかかわらず、データをアクセスするために rcu_dereference() を使います。以下は、挿入の例を示します。
1 bool add_gp(int a, int b)
2 {
3 p = kmalloc(sizeof(*p), GFP_KERNEL);
4 if (!p)
5 return -ENOMEM;
6 spin_lock(&gp_lock);
7 if (rcu_access_pointer(gp)) {
8 spin_unlock(&gp_lock);
9 return false;
10 }
11 p->a = a;
12 p->b = a;
13 rcu_assign_pointer(gp, p);
14 spin_unlock(&gp_lock);
15 return true;
16 }
１３行目の rcu_assign_pointer() は、概念的には、単純な代入文に等しいです。しかしそれは、その代入が、１１と１２行目の二つの代入の後に起きることを保証します。それは、C11 の memory_order_release ストア操作に似ています。それはまた、多くの「興味深い」コンパイラ最適化を防ぎます。その例には、代入の直前に gp を作業領域として使うことが含まれます。
クイッククイズ３：
でも、rcu_assign_pointer() は、p->a と p->b の二つの代入がリオーダーされるのを防ぐためには何もしません。それも問題を起こすのではありませんか？
リーダーはRCUで守られたデータへの自分のアクセスを制御するために特別に何かをする必要はないと思われるかもしれません。以下の、do_something_gp_buggy() が示すように。
1 bool do_something_gp_buggy(void)
2 {
3 rcu_read_lock();
4 p = gp; /* OPTIMIZATIONS GALORE!!! */
5 if (p) {
6 do_something(p->a, p->b);
7 rcu_read_unlock();
8 return true;
9 }
10 rcu_read_unlock();
11 return false;
12 }
でもこの誘惑は断ち切らなければいけません。コンパイラ(DEC Alpha CPU はもちろん)がこのコードを失敗させる方法は驚くほどたくさんあるからです。一つだけ例をあげるなら、以下の場合、コンパイラはレジスタが無い時は、p に独立したコピーを維持する代わりに、 gp から再フェッチする選択をするかもしれません。
1 bool do_something_gp_buggy_optimized(void)
2 {
3 rcu_read_lock();
4 if (gp) { /* OPTIMIZATIONS GALORE!!! */
5 do_something(gp->a, gp->b);
6 rcu_read_unlock();
7 return true;
8 }
9 rcu_read_unlock();
10 return false;
11 }
もしこの関数が、現在の構造体を新しいものと入れ替える連続する更新と同時に走ったら、gp->a と gp->b のフェッチは二つの異なる構造体から来ることが十分あり得ます。それはひどい混乱をもたらすでしょう。これ(そしてその他たくさん)を防ぐために、do_something_gp() は gp からフェッチするのに rcu_dereference() を使います。
1 bool do_something_gp(void)
2 {
3 rcu_read_lock();
4 p = rcu_dereference(gp);
5 if (p) {
6 do_something(p->a, p->b);
7 rcu_read_unlock();
8 return true;
9 }
10 rcu_read_unlock();
11 return false;
12 }
rcu_dereference() は、Linux カーネルでは、volatile キャストと、(DEC Alpha のために)メモリバリアを使います。C11 memory_order_consumeの高品質な実装がいつか現れたなら、rcu_dereference() は memory_order_consume ロードとして実装可能でしょう。実際に使われる実装には無関係に、rcu_dereference() がフェッチしたポインタは、その rcu_dereference() を含む最も外側のRCUリード側クリティカルセクションの外では使うことはできません。なお、対応するデータ要素の保護が、RCUから何か他の同期機構、最も一般的にはロックや参照カウンティングに引き渡された場合はそれは可能です。
短く言えば、更新者は rcu_assign_pointer() を使い、リーダーは rcu_dereference() を使います。そしてこれら二つのRCU API 要素は、協調して、リーダーが新しく追加されたデータ要素の一貫したビューを持つことを保証します。
もちろん、RCUで守られたデータ構造から要素を削除する必要もあります。例えば、以下のプロセスを使います。
１ データ要素をそれを取り囲む構造体から削除します。
２ 全ての既存のRCUリード側クリティカルセクションが完了するのを待ちます（既存のリーダーだけが、新しく削除されたデータ要素への参照を持っている可能性があるからです）。
３ この時点で、新しく削除されたデータ要素への参照を持つのは、更新者だけです。なので、それは安全にそのデータ要素を回収できます。例えば、それを kfree() に渡すことで。
remove_gp_synchronous() は、このプロセスを実装します。
1 bool remove_gp_synchronous(void)
2 {
3 struct foo *p;
4
5 spin_lock(&gp_lock);
6 p = rcu_access_pointer(gp);
7 if (!p) {
8 spin_unlock(&gp_lock);
9 return false;
10 }
11 rcu_assign_pointer(gp, NULL);
12 spin_unlock(&gp_lock);
13 synchronize_rcu();
14 kfree(p);
15 return true;
16 }
この関数は直裁的です。１３行目でグレースピリオドを待ち、１４行目で古いデータ要素を解放します。この待ちによって、p が参照するデータ要素が解放される前に、リーダーが do_something_gp() の７行目に達することが保証されます。６行目の rcu_access_pointer() は、rcu_dereference() に似ていますが、以下が違います。
１ rcu_access_pointer() が返す値はデレファレンスできません。もしあなたが、ポインタ自身だけでなく、ポイントされる値もアクセスしたいならば、rcu_access_pointer() の代わりに rcu_dereference() を使って下さい。
２ rcu_access_pointer() 呼び出しは、守られる必要はありません。それに対して、rcu_dereference() はRCU リード側クリティカルセクションの中にあるか、あるいは、ポインタが変わることができないコード断片の中になくてはいけません。例えば、対応する更新側のロックで守られたコードの中など。
クイッククイズ４：
rcu_dereference() あるいは rcu_access_pointer() がない場合、コンパイラはどのような破壊的最適化をする可能性がありますか？
短く言えば、RCU のパブリッシュサブスクライブ保証は、rcu_assign_pointer() と rcu_dereference() の組み合わせで提供されます。この保証は、データ要素が、RCUで守られた連結データ構造に、RCUリーダーをじゃますることなく安全に追加されるのを可能とします。この保証は、グレースピリオド保証と組み合わせて使って、データ要素が、RCUで守られた連結データ構造から、同様に、RCUリーダーをじゃますることなく安全に削除されるのを可能とします。
この保証は部分的にしか予想されませんでした。DYNIX/ptx は、パブリケーションには明示的なメモリバリアを使いましたが、サブスクリプションには rcu_dereference() 相当のものは何もありませんでした。まして、後に rcu_dereference() に含まれる smp_read_barrier_depends() のようなものはありませんでした。これらの操作の必要性は、１９９０年代終わりの DEC Alpha アーキテクトとの会議で、極めて突然に判明しました。その頃 DEC はまだ独立した会社でした。Alpha アーキテクトが、何らかの種類のバリアが絶対に必要だと私に納得させるのに、ゆうに一時間かかりました。そして私が、彼らの文書がこの点を明確にしていないことを彼らに納得させるのにゆうに二時間かかりました。より最近の C と C++ の標準化委員会の文書は、コンパイラの側からのトリックと罠について、十分な教育を与えます。短く言えば、１９９０年代初頭のコンパイラはそれほどトリッキーではありませんでした。しかし、２０１５年では、 rcu_dereference() を忘れるなんて決して思わないこと！
メモリバリア保証
前の節の単純な連結データ構造のシナリオは、一つ以上のCPUを持つシステムにおいて、RCUの厳重なメモリオーダリング保証が必要であることを明確に示します。
１ synchronize_rcu() が始まるよりも前に始まったRCUリード側クリティカルセクションを持つそれぞれのCPUは、そのRCUリード側クリティカルセクションが終わってから、その synchronize_rcu() が戻るまでの間に、完全なメモリバリアを実行することが保証されます。この保証がないと、既存のRCUリード側クリティカルセクションは remove_gp_synchronous() の１４行目の kfree() の後も、今削除された struct foo への参照を持っているかもしれません。
２ synchronize_rcu() が戻った後で終わるRCUリード側クリティカルセクションを持つそれぞれのCPUは、その synchronize_rcu() が始まってから、そのRCUリード側クリティカルセクションが始まるまでの間に、完全なメモリバリアを実行することが保証されます。この保証がないと、remove_gp_synchronous() の１４行目の kfree() の後に走る、後のRCUリード側クリティカルセクションは、後に do_something_gp() を実行し、それは新しく削除された struct foo を見るかもしれません。
３ もし、synchronize_rcu() を呼んだタスクが、あるCPUにとどまるならば、そのCPUは synchronize_rcu() の実行中のどこかで、完全なメモリバリアを実行することが保証されます。この保証は、remove_gp_synchronous() の１４行目の kfree() が、本当に、１１行目の削除の後に走ることを保証します。
４ もし、synchronize_rcu() を呼んだタスクが、それを呼んでいる間、CPUのグループ内を移動するならば、そのグループに含まれるそれぞれのCPUは synchronize_rcu() の実行中のどこかで、完全なメモリバリアを実行することが保証されます。この保証も、remove_gp_synchronous() の１４行目の kfree() が、本当に、１１行目の削除の後に走ることを保証します。それに加えて、synchronize_rcu() を実行しているスレッドがその間、移動する場合も保証します、
クイッククイズ５：
複数のCPUは、いつでも、何のオーダリングの制限もなしに、RCUリード側クリティカルセクションを始めることができます。それなのに、RCUはどうやって、あるRCUリード側クリティカルセクションがある synchronize_rcu() のインスタンスより前に始まったことがわかるのでしょうか？
クイッククイズ６：
最初と二つ目の保証は、信じられないほど厳格なオーダリングを必要とします。これらメモリバリアは全部、本当に必要ですか？
これらのメモリバリア保証は、グレースピリオドが全ての既存のリーダーを待つという、基本的RCU保証に代わるものではないことに注意下さい。それとは逆に、この節で述べたメモリバリアは、前記の基本的保証を強制するようなやり方で動作しなくてはいけません。もちろん、異なる実装はこの要件を異なる方法で強制します。しかし、強制は必要です。
RCUプリミティブは無条件に実行することが保証されます
一般の場合のRCUプリミティブは無条件です。それらは呼ばれて、自分の仕事をして、戻ります。エラーの可能性はなく、リトライは不要です。これは、RCU設計哲学の鍵です。
しかし、この哲学は、強情ではなく、実用的です。もし誰かが、特別の条件付きRCUプリミティブの優れた正当性に気がついたならば、それは実装され追加されることがあるでしょう。結局、この保証は予期されたものではなく、リバースエンジニアリングされたものです。このRCUプリミティブの無条件性は、最初は、実装の偶然でした。そして、条件付きプリミティブを持つ同期プリミティブについての後の経験の結果私は、この偶然を保証へと格上げすることになりました。なので、RCU世界に、条件付きプリミティブを追加することの正当性は、詳細で説得力のあるユースケースに基づく必要があります。
リードからライトのアップグレードは保証されます
RCUが関係する限り、RCUリード側クリティカルセクション内で更新を実行するのは常に可能です。例えば、あるRCUリード側クリティカルセクションはあるデータ要素を探しているとします。そして、その要素を更新するために、更新側のスピンロックを取ろうとするかもしれません。これは全て、そのRCUリード側クリティカルセクションにいるまま行われます。もちろん、synchronize_rcu() を呼ぶ前に、そのRCUリード側クリティカルセクションを抜ける必要があります。しかし、それが不便ならば、この文書の後で述べる、call_rcu() と kfree_rcu() API メンバを使えばよいです。
クイッククイズ７：
でも、ライトへのアップグレード操作は、どうやって他のリーダーを排除するのですか？
この保証は、リード側と更新側のコードで検索コードを共有することを許します。それは予期されたもので、最も初期の DYNIX/ptx RCU 文書にあります。
基本的に、要件でないもの
RCUは極めて軽量のリーダーを提供します。そしてそのリード側保証は、とても便利ですが、対応して、軽量です。なので、RCUが実際以上のことを保証しているだろうと推測するのはとても容易です。もちろん、RCUが保証しないことの一覧は無限に長いでしょう。しかし、以下の節は、いくつかの保証されないものであり、今までに混乱をまねいたものをリストします。特に記述がない限り、これらの保証されないものは、予期されたものです。
１ リーダーは最低限のオーダリングしか要求しません
２ リーダーは更新者を排除しません
３ 更新者は古いリーダーだけを待ちます
４ グレースピリオドはリード側クリティカルセクションを分断しません
５ リード側クリティカルセクションは、グレースピリオドを分断しません
６ プリエンプションを禁止しても、グレースピリオドはブロックしません
リーダーは最低限のオーダリングしか要求しません
rcu_read_lock() と rcu_read_unlock() のような、リード側マーカーは、絶対的に、何のオーダリング保証も提供しません。それらが synchronize_rcu() などのグレースピリオドAPIとの相互作用によるものを除きます。これを見るために、以下のスレッドの対を考えましょう。
1 void thread0(void)
2 {
3 rcu_read_lock();
4 WRITE_ONCE(x, 1);
5 rcu_read_unlock();
6 rcu_read_lock();
7 WRITE_ONCE(y, 1);
8 rcu_read_unlock();
9 }
10
11 void thread1(void)
12 {
13 rcu_read_lock();
14 r1 = READ_ONCE(y);
15 rcu_read_unlock();
16 rcu_read_lock();
17 r2 = READ_ONCE(x);
18 rcu_read_unlock();
19 }
thread0() と thread1() が同時に実行した後、
(r1 == 1 && r2 == 0)
となるのは極めてありえます。（つまり、y が、x よりも先に代入されたように見えます）それはもし、rcu_read_lock() と rcu_read_unlock() がオーダリングの性質に関して効果があるならば不可能のはずです。しかしそういうことはないので、CPUは自分の権限のもとで、大いにリオーダリングをします。これは仕様です。大きなオーダリング制約は全て、これら高速パスAPIを遅くします。
クイッククイズ８：
コンパイラもこのコードをリオーダーするのではないですか？
リーダーは更新者を排除しません
rcu_read_lock() も rcu_read_unlock() も、更新者を排除しません。それが行うのは、グレースピリオドが終わるのを妨げるだけです。以下の例はそれを示します。
1 void thread0(void)
2 {
3 rcu_read_lock();
4 r1 = READ_ONCE(y);
5 if (r1) {
6 do_something_with_nonzero_x();
7 r2 = READ_ONCE(x);
8 WARN_ON(!r2); /* BUG!!! */
9 }
10 rcu_read_unlock();
11 }
12
13 void thread1(void)
14 {
15 spin_lock(&my_lock);
16 WRITE_ONCE(x, 1);
17 WRITE_ONCE(y, 1);
18 spin_unlock(&my_lock);
19 }
もし、thread0() 関数の rcu_read_lock() が、 thread1() の更新を排除するならば、WARN_ON() は決して発火できません。しかし事実は、rcu_read_lock() は、以降のグレースピリオドを除いては、まるで何も排除はしません。thread1() はグレースピリオドがないので、WARN_ON() は発火できますし、実際にします。
更新者は古いリーダーだけを待ちます
synchronize_rcu() が完了した後は、実行しているリーダーはいないと思うのはありがちです。この誘惑は避けなければいけません。なぜならば、synchronize_rcu() が開始した後すぐに、新しいリーダーは開始することができ、synchronize_rcu() はいかなる意味でも、これら新しいリーダーを待つ義務はないからです。
クイッククイズ９：
synchronize_rcu() が本当に、全てのリーダーが完了するまで待つとしましょう。更新者は、これを信頼できますか？
グレースピリオドはリード側クリティカルセクションを分断しません
もしもあるRCUリード側クリティカルセクションの何らかの部分があるグレースピリオドの前にあり、別のRCUリード側クリティカルセクションの何らかの部分がその同じグレースピリオドの後にあるとしたら、最初のRCUリード側クリティカルセクションの全ては、二つ目の全ての前にあると考えるのはありがちです。しかしこれは全く誤りです。単一のグレースピリオドがRCUリード側クリティカルセクションのセットを分断することはありません。この状況の例を以下に示します。x, y, z は全て最初、ゼロです。
1 void thread0(void)
2 {
3 rcu_read_lock();
4 WRITE_ONCE(a, 1);
5 WRITE_ONCE(b, 1);
6 rcu_read_unlock();
7 }
8
9 void thread1(void)
10 {
11 r1 = READ_ONCE(a);
12 synchronize_rcu();
13 WRITE_ONCE(c, 1);
14 }
15
16 void thread2(void)
17 {
18 rcu_read_lock();
19 r2 = READ_ONCE(b);
20 r3 = READ_ONCE(c);
21 rcu_read_unlock();
22 }
こういう結果は全く可能だとわかります。
(r1 == 1 && r2 == 0 && r3 == 1)
以下の図は、これがどのように起きることができるかを示します。まるで囲まれた QS は、RCUがそれぞれのスレッドで quiescent state、 静止状態を記録した点を示します。それはつまり、RCUが、現在のグレースピリオドの前に開始したスレッドがRCUリード側クリティカルセクションの真ん中にいることはありえないとわかった点です。
もしこのようにRCUリード側クリティカルセクションを分断する必要があるならば、二つのグレースピリオドを使う必要があります。最初のグレースピリオドは二つ目のグレースピリオドが始まる前に終わることがわかっています。
1 void thread0(void)
2 {
3 rcu_read_lock();
4 WRITE_ONCE(a, 1);
5 WRITE_ONCE(b, 1);
6 rcu_read_unlock();
7 }
8
9 void thread1(void)
10 {
11 r1 = READ_ONCE(a);
12 synchronize_rcu();
13 WRITE_ONCE(c, 1);
14 }
15
16 void thread2(void)
17 {
18 r2 = READ_ONCE(c);
19 synchronize_rcu();
20 WRITE_ONCE(d, 1);
21 }
22
23 void thread3(void)
24 {
25 rcu_read_lock();
26 r3 = READ_ONCE(b);
27 r4 = READ_ONCE(d);
28 rcu_read_unlock();
29 }
ここで、もし、(r1 == 1) ならば、 thread0() の b へのライトは、 thread1() のグレースピリオドの終わりより前に起きなくてはいけません。さらに、もし、(r4 == 1) ならば、 thread3() の b からのリードは、thread2() のグレースピリオドの後に起きなくてはいけません。さらにもし、(r2 == 1) ならば、thread1() のグレースピリオドの終わりは、thread2() のグレースピリオドの開始より前でなくてはいけません。これはつまり、二つのRCUリード側クリティカルセクションはオーバーラップできないことを意味し、(r3 == 1) を保証します。この結果、
(r1 == 1 && r2 == 1 && r3 == 0 && r4 == 1)
は起きることはできません。
この要件でないものは、予期されてもいませんでした。しかし、RCUのメモリオーダリングとの相互作用を研究している時に明らかになりました。
リード側クリティカルセクションは、グレースピリオドを分断しません
もし、RCUリード側クリティカルセクションが二つのグレースピリオドの間に起きたならば、これらのグレースピリオドはオーバーラップすることはできないだろうと考えるのは同様にありがちです。しかし、この誘惑は、いかなる良い所へもつながっていません。以下で示す通りです。全ての変数は最初、ゼロです。
1 void thread0(void)
2 {
3 rcu_read_lock();
4 WRITE_ONCE(a, 1);
5 WRITE_ONCE(b, 1);
6 rcu_read_unlock();
7 }
8
9 void thread1(void)
10 {
11 r1 = READ_ONCE(a);
12 synchronize_rcu();
13 WRITE_ONCE(c, 1);
14 }
15
16 void thread2(void)
17 {
18 rcu_read_lock();
19 WRITE_ONCE(d, 1);
20 r2 = READ_ONCE(c);
21 rcu_read_unlock();
22 }
23
24 void thread3(void)
25 {
26 r3 = READ_ONCE(d);
27 synchronize_rcu();
28 WRITE_ONCE(e, 1);
29 }
30
31 void thread4(void)
32 {
33 rcu_read_lock();
34 r4 = READ_ONCE(b);
35 r5 = READ_ONCE(e);
36 rcu_read_unlock();
37 }
この場合、以下の結果は、完全に可能です。以下に示す通りです。
(r1 == 1 && r2 == 1 && r3 == 1 && r4 == 0 && r5 == 1)
繰り返しますが、RCUリード側クリティカルセクションはあるグレースピリオドのほとんど全部とオーバーラップすることができます。そのグレースピリオド全体とオーバーラップしない限りにおいて。その結果、RCUリード側クリティカルセクションは、二つのRCUグレースピリオドを分断することはありません。
クイッククイズ１０：
あるチェーンの最初にあるRCUリード側クリティカルセクションと最後のを分断するためには、それぞれがRCUリード側クリティカルセクションで区切られたグレースピリオドのシーケンスがいくつあれば十分でしょう？
プリエンプションを禁止しても、グレースピリオドはブロックしません
任意のあるCPUにおいてプリエンプションを禁止すると、以降のグレースピリオドをブロックすることになることがかつてはありました。しかし、これは実装の偶然であり、それは要件ではありません。そして現在のLinuxカーネル実装においては、あるCPUにおいてプリエンプションを禁止しても、Oleg Nesterov が 示したように、実際、グレースピリオドはブロックされません。
もしあなたが、プリエンプト禁止領域でグレースピリオドをブロックする必要があるならば、例えば以下に示すように、rcu_read_lock() と rcu_read_unlock() を加える必要があります。
1 preempt_disable();
2 rcu_read_lock();
3 do_something();
4 rcu_read_unlock();
5 preempt_enable();
6
7 /* Spinlocks implicitly disable preemption. */
8 spin_lock(&mylock);
9 rcu_read_lock();
10 do_something();
11 rcu_read_unlock();
12 spin_unlock(&mylock);
理論的には、あなたは、最初にRCUリード側クリティカルセクションに入ることができますが、上に示すように、そのRCUリード側クリティカルセクション全体をプリエンプト禁止領域に含まれるようにするほうがより効率的です。もちろん、プリエンプト禁止領域の外に伸びるRCUリード側クリティカルセクションは正しく動作します。しかし、そのようなクリティカルセクションはプリエンプトされるかもしれず、それは、rcu_read_unlock() が余計な仕事をすることを強制します。そして、いいえ、これは、あなたのRCUリード側クリティカルセクションの全てをプリエンプト禁止領域に閉じ込めるようにおすすめしているのではありません。そんなことをすれば、リアルタイム応答が悪化しますから。
この要件でないものは、プリエンプト可能RCUとともに現れました。もしあなたが、プリエンプト不可能コード領域を待つグレースピリオドが必要ならば、RCU-sched を使って下さい。
並列性の人生の真実
以下の並列性の人生の真実は、いかなる意味でも、RCUに特有ではありません。しかし、RCU実装はこれに従う必要があります。なので、繰り返す価値があります。
１ いかなるCPUあるいはタスクも、いつでも遅延することがあります。そして、プリエンプションや割り込みを無効にすることでこの遅延を避けようとする全ての試みは、完全にむだです。これはプリエンプト可能ユーザレベル環境と仮想化環境(そこでは、あるゲストOSのVCPUは下にあるハイパーバイザによっていつでもプリエンプトされます)で最も明らかです。しかし、ECCエラー、NMI、そして他のハードウェアイベントのために、ベアメタル環境でも起きることがあります。約２０秒以上の遅延は警告が出ることがありますが、RCU実装は、極めて長い遅延に耐えられるアルゴリズムを使うことを義務付けられています。ここで、「極めて長い」とは、６４ビットカウンタを加算するときに、ラップアラウンドするほど長くはないということです。
２ コンパイラもCPUもメモリアクセスをリオーダーできます。それが問題となる時は、RCUはオーダリングを守るためにコンパイラディレクティブとメモリバリア命令を使わなくてはいけません。
３ どんなキャッシュラインにおいても、メモリ位置への競合するライトは高価なキャッシュミスになります。同時実行するライトの数が大きくなり、同時実行するライトがより頻繁になるにつれて、よりドラマチックな遅延が起きます。なのでRCUは、大きな性能とスケーラビリティ問題を避けるために、十分な局所性を持つアルゴリズムを使う義務があります。
４ おおまかに言って、なんらかの排他ロックの保護のもとでは、たった一つのCPU分の処理しか実行することはできません。なのでRCUは、スケーラブルなロック設計を使わなくてはいけません。
５ カウンタは有限です。特に、３２ビットシステムでは。なのでRCUのカウンタの使用は、カウンタのラップに耐えなくてはいけません。あるいは、カウンタのラップが、単一のシステムが実行するだろう時間よりもずっと長くかかるように設計されなくてはいけません。後者の例として、RCUの dyntick-idle ネストカウンタは割り込みのネストレベルのために５４ビットを許します。（このカウンタは、３２ビットシステムでも６４ビットです）このカウンタをオーバーフローさせるためには、あるCPUで、そのCPUが全くアイドルにならないまま、 2^54 半割り込みが必要です。
訳注
割り込みハンドラに入って、出ないのを、half-interrupt、半割り込みと呼びます。以降の、割り込みとNMI の節を参照。
もし、１マイクロ秒ごとに半割り込みが起きたら、このカウンタがオーバーフローするには５７０年の実行時間がかかるでしょう。それは今のところ、受け入れられる長さの時間だと信じられます。
６ Linuxシステムでは何千ものCPUがあり、単一のLinuxカーネルを単一の共用メモリ環境で走らせることがあります。なのでRCUは、高エンドスケーラビリティに大いに注意しなくてはいけません。
並列性の人生の真実のこの最後のものは、RCUがそれ以前の人生の真実に特に注意しなくてはいけないことを意味します。Linuxが、何千ものCPUを持つシステムにまでスケールするかという考えは、１９９０年代には少しばかりの懐疑に会ったでしょうが、これらの要件は、１９９０年代初めにおいても、驚くべきものではありませんでした。
実装の質に関する要件
以下の節は、実装の質の要件の一覧を示します。これらの要件を無視するRCU実装を使うことはできるでしょうが、それは限界を持つでしょうから、工業的強度の本番での使用には不適切でしょう。以下が、実装の質の要件の一覧です。
１ 特殊化
２ 性能とスケーラビリティ
３ 構成可能性
４ 特殊ケース
以下の節で、これらのクラスを扱います。
特殊化
RCUは、今も、これまでもずっと、以下の図で示すように、主にリードがほとんどの状況のためのものでした。これは、RCUのリード側プリミティブは、しばしばその更新側プリミティブの犠牲のもとで最適化されていることを意味します。
この、リードがほとんどの状況に集中することは、RCUが他の同期プリミティブと相互運用しなくてはいけないことを意味します。例えば、以前に議論した、add_gp() と remove_gp_synchronous() の例は、リーダーを守るためにRCUを使い、更新者を調整するためにロックを使いました。しかし、要求ははるかに大きくなり、いろいろな同期プリミティブがRCUリード側クリティカルセクション内で合法であることを求めました。それには、スピンロック、シーケンスロック、アトミック操作、参照カウンタ、そしてメモリバリアが含まれます。
クイッククイズ１１：
スリープするロックはどうですか？
多くのアルゴリズムはデータの一貫したビューを必要としないことは、しばしば驚きです。しかし、多くはそのモードで機能することができます。ネットワークルーティングが顕著な例です。インターネットルーティングアルゴリズムは、更新を伝搬するのにかなりな時間がかかります。なので更新があるシステムに届いた時には、そのシステムはかなりの時間の間、ネットワークトラフィックを誤った方向に送っていることがあります。いくつかのスレッドがあと何ミリ秒の間か、トラフィックを誤った方向に送り続けるのは、明らかに問題ではありません。最悪の場合、TCPの再送が最後にはデータを、それが行く必要のあるところに届けるでしょう。一般的に、計算機の外側の宇宙の状態を追跡する時に、あるレベルの矛盾は許容されなくてはいけません。他に何もなくても、光速の遅延に由来するものがあります。
さらに、外部状態についての不確定性は多くの場合で避けられません。例えば、二人の獣医が、ある猫が生きているかを決めるのに、心臓の鼓動を使うとします。しかし、最後の鼓動からどれだけ待てば、その猫が本当に死んでいると決められるでしょう？４００ミリ秒以下待つのはばかげています。そうすると、リラックスした猫は、一分に１００回以上、死んだり生きたりを繰り返すように見えることを意味します。さらに、人類と同様、猫の心臓は、しばらくの時間、止まることがあります。なので、正確な待ち時間は、主観的な判定となります。二人の獣医のうち、一人は猫の死を宣言するのに３０秒待つかもしれず、もう片方は、まるまる一分待つことを主張するかもしれません。すると、二人の獣医は、最後の鼓動の後の最後の３０秒の間、猫の状態について意見が一致しません。これは、以下に楽しく描かれるとおりです。
とても興味深いことに、この同じ状況がハードウェアにもあてはまります。危機が訪れた時、ある外部のサーバが落ちたかどうか、どうやったらわかるでしょう。定期的にそれにメッセージを送って、決められた時間内に応答を受けなければ、それが落ちたと宣言できます。ポリシーの決定は、通常は短期間の矛盾に耐えることができます。ポリシーはしばらく前に決められ、たった今、初めて効力を持ちました。なので、数ミリ秒の遅延は通常は重要ではありません。
しかし、アルゴリズムによっては、絶対に一貫したデータを見なくてはいけないものがあります。例えば、ユーザレベルのSystemV セマフォ IDから対応するカーネル内データ構造への変換は、RCUで守られます。しかし、削除したばかりのセマフォを更新することは、絶対に許されません。Linuxカーネルでは、この一貫性の要求は、RCUリード側クリティカルセクションからそのカーネル内のデータ構造にあるスピンロックを取ることによって満足されます。そしてこれは、前記図の緑の箱で示されます。多くの他のテクニックを使うこともできます。そしてそれらは実際にLinuxカーネルで使われています。
短く言えば、RCUは一貫性を維持するようには要求されていません。そして、一貫性が必要な時には、RCUと一緒に他の機構を使うことができます。RCUは特殊化されているために、自分の仕事を極めてうまく行うことができます。そしてそれは他の同期機構と相互運用することができるために、与えられた仕事において使うべき同期ツールの正しい混合が可能です。
性能とスケーラビリティ
エネルギー効率は、今日の性能の致命的な要素です。なので、Linux カーネルRCU実装はアイドルCPUを不必要に起こすのを避けなくてはいけません。この要件は予期されていたと主張することはできません。実は私はこれを、電話での会話で学びました。そこで私は、電池で給電されるシステムにおけるエネルギー効率の重要性と、LinuxカーネルRCU実装のある一つのエネルギー効率上の欠点について、「率直で開かれた」フィードバックをもらいました。私の経験によると、電池で給電される組み込みコミュニティは、全ての必要のない起床を、きわめて敵対的な行動と考えるようです。それはとても激しいので、Linuxカーネルメーリングリストの投稿くらいでは、彼らの怒りを発散するには不十分です。
メモリ消費はほとんどの状況でそれほど重要ではありません。メモリサイズが大きくなり、メモリ価格が下がってきた今ではますますそうです。しかし、私が、Matt Mackall の bloatwatch の仕事で学んだように、メモリフットプリントはプリエンプト不可能 (CONFIG_PREEMPT=n) カーネルを使う単一CPUシステムでは致命的に重要です。このために、tiny RCU が生まれました。Josh Triplett はそれ以来、彼の Linux kernel tinification プロジェクトで、小さいメモリの旗を引き継いできました。その結果、SRCU は、それを必要としないカーネルではオプションになりました。
残りの性能要件は、ほとんど、驚くほどのことはないものです。例えば、RCUのリード側特殊化のために、rcu_dereference() は無視できるほどのオーバーヘッド(例えば、小さなコンパイラ最適化をいくつか抑止するだけ)を持つべきです。同様に、プリエンプト不可能環境では、rcu_read_lock() と rcu_read_unlock() は正確にゼロオーバーヘッドを持つべきです。
プリエンプト可能環境では、RCUリード側クリティカルセクションがプリエンプトされなかった場合(最高優先度のリアルタイムプロセスの場合のように)、rcu_read_lock() と rcu_read_unlock() は最低限のオーバーヘッドを持つべきです。特に、それらは、アトミックリードモディファイライト操作、メモリバリア命令、プリエンプション禁止、割り込み禁止、あるいは後ろへの分岐を持つべきではありません。しかし、RCUリード側クリティカルセクションがプリエンプトされた場合、rcu_read_unlock() はスピンロックを取って割り込みを禁止するかもしれません。これが、RCUリード側クリティカルセクションを、プリエンプト禁止領域内にネストする方が、その逆よりも良い理由です。なお、そのクリティカルセクションが過度にリアルタイム遅延を悪化させない程度に短い場合に限ります。
synchronize_rcu() グレースピリオド待ちプリミティブはスループットのために最適化されています。このためそれは、最も長いRCUリード側クリティカルセクションの長さに加えて、数ミリ秒の遅延を起こすことがあります。一方、synchronize_rcu() を複数、同時実行して呼び出すと、元になる単一のグレースピリオド待ち操作によってそれらが満足するように、バッチ最適化を使う必要があります。例えば、Linuxカーネルにおいて、単一のグレースピリオド待ち操作が、 1,000 以上の 個別の synchronize_rcu() 呼び出しを満足するのは珍しいことではありません。このようにして、呼び出しごとのオーバーヘッドをほとんどゼロに緩和することができます。しかし、グレースピリオド最適化は、リアルタイムスケジューリングと割り込み遅延の測定できるほどの悪化を避けるためにも必要です。
複数ミリ秒の synchronize_rcu() の遅延が受け入れがたい場合もあります。そういう場合、代わりに synchronize_rcu_expedited() を使うことができます。それは、小さなシステムでは、グレースピリオド遅延を数十マイクロ秒にまで小さくします。少なくてもそのRCUリード側クリティカルセクションが短いならば。今のところ、巨大システムでのsynchronize_rcu_expedited() の遅延要件に特別なことはありませんが、RCU仕様が経験的であることからして、それはきっと変わるでしょう。しかし最も明らかなのは、スケーラビリティ要件です。４０９６CPUからの synchronize_rcu_expedited() 呼び出しの嵐は、少なくても何らかの前方進行をするべきです。synchronize_rcu_expedited() はより小さい遅延を可能としますがその代わりにそれはアイドルでないオンラインCPUにある程度のリアルタイム遅延を課すことが許されています。とは言え、この悪化を、願わくばスケジューリングクロック割り込みの遅延程度まで減らすためにさらに対策をしなければいけなくなるだろうというのはありがちです。
synchronize_rcu_expedited() の小さくされたグレースピリオド遅延でさえ受け入れがたい場合もいくつかあります。そのような場合、以下のように非同期の call_rcu() を、synchronize_rcu() の代わりに使うことができます。
1 struct foo {
2 int a;
3 int b;
4 struct rcu_head rh;
5 };
6
7 static void remove_gp_cb(struct rcu_head *rhp)
8 {
9 struct foo *p = container_of(rhp, struct foo, rh);
10
11 kfree(p);
12 }
13
14 bool remove_gp_asynchronous(void)
15 {
16 struct foo *p;
17
18 spin_lock(&gp_lock);
19 p = rcu_dereference(gp);
20 if (!p) {
21 spin_unlock(&gp_lock);
22 return false;
23 }
24 rcu_assign_pointer(gp, NULL);
25 call_rcu(&p->rh, remove_gp_cb);
26 spin_unlock(&gp_lock);
27 return true;
28 }
struct foo の定義が最終的に必要です。１から５行目にあります。関数 remove_gp_cb() は２５行目で call_rcu() に渡され、以降のグレースピリオドが終わった後に呼び出されます。これはremove_gp_synchronous() と同じ効果を持ちますが、更新者はグレースピリオドが過ぎるのを待つことを強制されません。call_rcu() は、synchronize_rcu() も synchronize_rcu_expedited() の使用も違法であるいくつかの状況で使うことができます。それには、プリエンプト禁止コード、local_bh_disable() コード、割り込み禁止コード、そして割り込みハンドラの中を含みます。しかし、call_rcu() であっても、NMI ハンドラの中では違法です。Linuxカーネルでは、コールバック関数(今の場合 remove_gp_cb())は、softirq (ソフトウェア割り込み)環境で呼ばれます。それは、本当の softirq ハンドラ内であるか、local_bh_disable() の保護のもとにあります。Linuxカーネル内でもユーザ空間でも、あまりに長くかかるRCUコールバック関数を書くのは悪い習慣です。長く走る操作は、別のスレッドか、（Linuxカーネルならば）ワークキューに追放されるべきです。
クイッククイズ１２：
なぜ、１９行目は、rcu_access_pointer() を使うのですか？結局、２５行目の call_rcu() はその構造体内にストアします。それは、同時実行する挿入と悪く相互作用します。これは、rcu_dereference() が必要であることを意味しませんか？
しかし、その remove_gp_cb() がしている全てのことは、そのデータ要素に対して、kfree() を呼ぶことです。これは慣用句であり、kfree_rcu() によりサポートされます。その結果、以下に示すように、「fire and forget, 発火させて忘れる」操作ができます。
1 struct foo {
2 int a; 3 int b; 4 struct rcu_head rh; 5 }; 6 7 bool remove_gp_faf(void) 8 { 9 struct foo *p; 10 11 spin_lock(&gp_lock); 12 p = rcu_dereference(gp); 13 if (!p) { 14 spin_unlock(&gp_lock); 15 return false; 16 } 17 rcu_assign_pointer(gp, NULL); 18 kfree_rcu(p, rh); 19 spin_unlock(&gp_lock); 20 return true; 21 }
remove_gp_faf() は単純に kfree_rcu() を呼んで進むことに注意下さい。その後のグレースピリオドと kfree() にはそれ以上何も注意を払う必要はありません。call_rcu() と同じ環境から kfree_rcu() を呼ぶことは許されます。興味深いことに、DYNIX/ptx は、 call_rcu() と kfree_rcu() の同等品を持っていましたが、 synchronize_rcu() はありませんでした。これは、DYNIX/ptx では、RCUはそれほど頻繁に使われてはいなかったという事実のためです。なので、synchronize_rcu() のようなものが必要なとてもわずかな場所では、単純にそれをオープンコードしました。
クイッククイズ１３：
あなたは前に、call_rcu() と kfree_rcu() は更新者がリーダーにブロックされるのを避けることができると主張しました。しかし、コールバック呼び出しとメモリの解放は（それぞれ）なおも、グレースピリオドが過ぎるのを待たないといけないというのに、それが正しいとはどういうことですか？
でも、もし、更新者がグレースピリオドが終わった後に実行されるコードの完了を待たなくてはならず、ただし、その間に行うことのできる他の作業があるときには、どうしましょう？ポーリングスタイルの、get_state_synchronize_rcu() と cond_synchronize_rcu() 関数はこの目的のために使うことができます。以下のとおり。
1 bool remove_gp_poll(void)
2 {
3 struct foo *p;
4 unsigned long s;
5
6 spin_lock(&gp_lock);
7 p = rcu_access_pointer(gp);
8 if (!p) {
9 spin_unlock(&gp_lock);
10 return false;
11 }
12 rcu_assign_pointer(gp, NULL);
13 spin_unlock(&gp_lock);
14 s = get_state_synchronize_rcu();
15 do_something_while_waiting();
16 cond_synchronize_rcu(s);
17 kfree(p);
18 return true;
19 }
１４行目で、get_state_synchronize_rcu() は、RCUから「クッキー」をもらいます。そして１５行目は他の作業を実行し、そして最後に、１６行目はその間にグレースピリオドが過ぎていたら直ちに戻ります。そうでないときは、必要に応じて待ちます。get_state_synchronize_rcu と cond_synchronize_rcu() が必要となったのはごく最近です。なので、それらが時の試練に耐えるかは、しばらくしないとわからないでしょう。
RCUはこのように、更新者が遅延、柔軟性、そしてCPUオーバーヘッドの間のトレードオフを見つけられるように、幅広いツールを提供します。
構成可能性
composability 構成可能性は、近年多くの注目を集めています。それは多分、部分的には、マルチコアハードウェアと、シングルスレッドでの使用のためにシングルスレッド環境で設計されたオブジェクト指向技術の衝突のためでしょう。そして、理論的には、RCUリード側クリティカルセクションは部品となることができます。そして実際、任意に深くネストできます。現実的には、構成可能部品の全ての現実世界での実装と同じように、限界はあります。
CONFIG_PREEMPT=n のLinuxカーネルのように、rcu_read_lock() と rcu_read_unlock() が何もコードを生成しないRCU実装では、それは任意の深さにネストできます。結局、オーバーヘッドはありません。ただし、 それら rcu_read_lock() と rcu_read_unlock()インスタンスの全てがコンパイラに見えたなら、コンパイラは最後には、メモリ、大容量記憶域、ユーザの辛抱、のいずれか最初になくなったもののためにコンパイルに失敗するでしょう。それぞれ自身の翻訳単位にある相互に再帰的な関数の場合のようにネストがコンパイラからは見えないならば、スタックオーバーフローになるでしょう。ネストが、ループの形式を取れば、制御変数がオーバーフローするか、(Linuxカーネル内では)RCU CPUストール警告が出るでしょう。とは言え、このRCU実装のクラスは、存在する中で最も構成可能な部品の一つです。
明示的にネストの深さを追跡するRCU実装は、そのネストの深さのカウンタにより制限されます。例えば、Linuxカーネルのプリエンプト可能なRCUはネストを INT_MAX に制限します。これはほとんど全ての現実的な目的にとって十分のはずです。とは言え、連続するRCUリード側クリティカルセクションの対であって、その間にグレースピリオドを待つ操作があるものは、他のRCUリード側クリティカルセクションの中には囲まれることができません。これは、RCUリード側クリティカルセクションの中ではグレースピリオドを待つのは違法だからです。そうするならば、デッドロックになるか、あるいは、RCUが暗黙的に外側のRCUリード側クリティカルセクションを分割する結果になります。そのどちらも、長寿命で成功したカーネルにはつながらないでしょう。
構成可能性を制限するのは、RCUだけではないことを注意するのは重要です。例えば、多くのトランザクショナルメモリ実装は、二つのトランザクションが取り消し不可能操作（例えば、ネットワーク受信処理）によって隔てられる構成を許しません。別の例としては、ロックを元とするクリティカルセクションは驚くほど自由に構成可能ですが、デッドロックを避けることができるのが前提です。
要するに、RCUリード側クリティカルセクションは高度に構成可能ですが、状況によっては注意が必要です。それは、他の全ての構成可能同期機構と同じことです。
特殊ケース
あるRCUワークロードは、RCUリード側クリティカルセクションの終わることがなく強い流れを持つかもしれません。たぶん、あまりにそれが強いために、少なくても一つの飛行中のRCUリード側クリティカルセクションが存在しないような時間間隔は決してありえないとします。RCUはこの状況がグレースピリオドをブロックするのを許すことはできません。全てのRCUリード側クリティカルセクションが有限である限り、グレースピリオドも有限でなくてはいけません。
とは言え、プリエンプト可能RCU実装では、潜在的には、RCUリード側クリティカルセクションが長時間にわたってプリエンプトされる結果になることがあります。それは、長く続くRCUリード側クリティカルセクションを作る効果があります。この状況は、重い負荷のシステムでだけ起きえます。しかし、リアルタイム優先度を使うシステムはもちろん、より、それが起きやすいです。なので、この場合を扱う助けとなるように、RCU優先度ブーストが提供されます。とは言え、RCU優先度ブーストの正確な要件は、より多くの経験が蓄積されるにつれて、進化することがあり得ます。
とても高い更新率を持つワークロードもあるでしょう。そのようなワークロードは、その代わり、RCU以外の何かを使うべきだと主張することもできるでしょうが、RCUがそのようなワークロードを優雅に扱わなくてはいけないという事実は残ります。この要件は、グレースピリオドのバッチングを動機づけるもう一つの要素です。しかし、それはまた、call_rcu() コードパスでキューされた多数のRCUコールバックをチェックする動機にもなっています。最後に、高い更新率はRCUリード側クリティカルセクションを遅延させるべきではありません。ただし、synchronize_rcu_expedited() が try_stop_cpus() を使うために、その関数を使う時にはある程度のリード側遅延は起きることがあります。（将来は、synchronize_rcu_expedited() はより軽量のプロセッサ間割り込み（IPI)を使うように変換されるでしょう。しかし、これでもなお、リーダーを妨害するでしょう。ずっと少しだとしても。）
これら３つの特殊ケース全ては１９９０年代初めには理解されていました。しかし、２０００年代初めの、close(open(path)) のきついループからなる単純なユーザレベルのテストが、突然、高更新率の特殊ケースについてずっと深い要求を提供しました。このテストは、高更新率に対処するためにいくらかのRCUコードをなおすことも動機付けました。例えば、もしあるCPUが、自分に、10,000 以上のRCUコールバックがキューされていることを発見したら、それは、よりアグレッシブにグレースピリオドを開始し、よりアグレッシブにグレースピリオドの完了を強制することによる回避手段を取るようにRCUにさせます。この回避手段は、グレースピリオドがより早く完了するようにします。しかしそれは、RCUのバッチ最適化を制限するコストを払います。それは、そのグレースピリオドが起こすCPUオーバーヘッドを増します。
ソフトウェアエンジニアリング要件
マーフィーの法則と「人は誤りをおかすもの」により、事故や使い方の誤りに対する防御は必要です。
１ rcu_read_lock() が必要なところ全てで、それを使うのを忘れるのはあまりにも簡単です。なので、CONFIG_PROVE_RCU=y をつけてビルドされたカーネルは、rcu_dereference() がRCUリード側クリティカルセクションの外側で使われたら警告します。更新側のコードは rcu_dereference_protected() を使うことができます。それは、何が保護を提供しているかを示す lockdep 式 を引数に取ります。もしも指定された保護が無い時には、lockdep 警告が表示されます。
リーダーと更新者の間で共用されるコードは、rcu_dereference_check() を使うことができます。これも lockdep 式を引数に取り、rcu_read_lock() も、指定された保護も無い時に lockdep 警告を表示します。また、必要な保護が容易に表せない(できれば稀な)場合には、rcu_dereference_raw() を使うことができます。最後に、rcu_read_lock_held() は、その関数がRCUリード側クリティカルセクション内で呼ばれた事を確認するために提供されます。私は、Thomas Gleixner がいくつかのRCUの使用を調べた少し後に、この要件のセットに気付かされました。
２ ある関数は、始まった時に、全てのRCU APIを使う前に、RCUに関する前提条件を確認したいかもしれません。rcu_lockdep_assert() はこの仕事をします。lockdep が有効なカーネルではその式をアサートし、そうでないときは何もしません。
３ rcu_assign_pointer() と rcu_dereference()を使うのを忘れて、たぶん、(誤って)単純な代入をすることも、容易です。この類の誤りを捉えるために、ある RCU で守られるポインタを __rcu でタグ付けすることができます。その後、sparse を CONFIG_SPARSE_RCU_POINTER=y をつけて走らせると、そのポインタへの単純な代入アクセスに文句を言います。Arnd Bergmann は私にこの要件を教えてくれ、必要な パッチシリーズ を提供してくれました。
４ CONFIG_DEBUG_OBJECTS_RCU_HEAD=y をつけてビルドされたカーネルは、もしあるデータ要素が続けて二回、途中にグレースピリオドをはさまずに call_rcu() に渡されると警告します。（この誤りは、二重解放に似ています。）ダイナミックに確保される、対応する rcu_head 構造体は、自動的に追跡されます。しかし、スタック上に確保される rcu_head 構造体は、init_rcu_head_on_stack() で初期化し、destroy_rcu_head_on_stack() でクリーンアップする必要があります。同様に、静的に確保される、スタックでない rcu_head 構造体は、init_rcu_head() で初期化し、destroy_rcu_head() でクリーンアップする必要があります。Mathieu Desnoyers は私にこの要件を教えてくれ、必要な パッチ を提供してくれました。
５ RCUリード側クリティカルセクションでの無限ループは、最後には、RCU CPU ストール警告を起こします。なお、「最後には」の長さは、RCU_CPU_STALL_TIMEOUT Kconfig オプションで制御されます。あるいは、rcupdate.rcu_cpu_stall_timeout ブート/sysfs パラメタで制御されます。しかし、RCUはこの特定のRCUリード側クリティカルセクションを待っているグレースピリオドが無い限り、この警告を生成する義務はありません。
極端なワークロードによっては、意図的にRCUグレースピリオドを遅らせることがあるでしょう。そういうワークロードを走らせているシステムは、rcupdate.rcu_cpu_stall_suppress 付きでブートすれば、警告を抑止できます。このカーネルパラメタは、sysfs 経由でも設定できます。さらに、RCU CPUストール警告は、sysrq ダンプとパニックの間は、非生産的です。なのでRCUは、rcu_sysrq_start() と rcu_sysrq_end() API メンバを提供し、長い sysrq ダンプの前と後で呼ぶことができます。またRCUは、rcu_panic() ノーティファイアも提供し、それは、パニックの始めに自動的に呼ばれ、それ以上のRCU CPUストール警告を抑止します。
この要件は、１９９０年台初期に知られるようになりました。まさに、最初に CPUストールをデバッグしなくてはいけなくなった時です。とは言え、DYNIX/ptx の初期実装は、Linux のそれと比べると、とても一般的でした。
６ RCU リード側クリティカルセクションから漏れ出るポインタを検出できればとても素晴らしいでしょうが、今のところそれをする良い方法はありません。漏れ出るポインタと、RCUから例えば参照カウンティングのような他の同期機構に手渡されるポインタを区別する必要があることが、一つの難問です。
７ CONFIG_RCU_TRACE=y 付きでビルドされたカーネルでは、RCU関連の情報は、debugfs とイベントトレースを経由して提供されます。
８ rcu_assign_pointer() と rcu_dereference() をオープンコードで使って、典型的な連結データ構造を作成するのは、驚くほど誤りやすいです。なので、RCUで守られる 連結リスト と、最近は、RCUで守られる ハッシュテーブル が利用可能です。Linuxカーネルと、ユーザ空間RCUライブラリには、他の多くの特別用途のためのRCUで守られるデータ構造が利用可能です。
９ 連結構造体には、コンパイル時に作成され、それでも __rcu チェックが必要な物があります。RCU_POINTER_INITIALIZER() マクロはこのためのものです。
１０ 後に、単一の外部ポインタを使ってパブリッシュされる連結構造体を作成する時には、rcu_assign_pointer() を使う必要はありません。RCU_INIT_POINTER() はこの仕事のために提供されます。また、実行時にポインタに NULL を設定することもします。
これは厳格な一覧ではありません。RCUの診断能力は、実際の世界のRCUの使用で見つかった使い方のバグの数とタイプによって導かれ続けるでしょう。
Linuxカーネルがもたらす複雑さ
Linux カーネルは全ての種類のソフトウエアにとって興味深い環境を提供します。それにはRCUも含まれます。関係ある興味深い点のいくつかは以下です。
１ 構成
２ ファームウェアインタフェース
３ 初期ブート
４ 割り込みとマスク不可能割り込み（NMI)
５ ローダブルモジュール
６ ホットプラグCPU
７ スケジューラとRCU
８ トレースとRCU
９ エネルギー効率
１０ メモリ効率
１１ 性能、スケーラビリティ、応答時間そして信頼性
この一覧はたぶん不完全です。しかし、Linuxカーネルがもたらす複雑さの最も主なものの感触を確かに与えます。以下の節のそれぞれは上記話題の一つをカバーします。
構成
RCUのゴールは、自動構成です。ほとんど誰も、RCUの Kconfig オプションについて悩まなくてもよいようにです。そしてほぼ全てのユーザにとってRCUは実際に「箱から出してすぐ」うまく動きます。
しかし、カーネルブートパラメタと Kconfig オプションによって扱われる特殊化されたユースケースがあります。不幸にも、Kconfig システムは、新しい Kconfig オプションについて明示的にユーザに問い合わせます。このため、それらのほとんど全ては CONFIG_RCU_EXPERT Kconfig オプションの後ろに隠されなくてはいけません。
これは全部、とても自明です。しかし、Linus Torvalds が最近私に、この要件を思い出させなければいけなかったというのは事実です。
ファームウェアインタフェース
多くの場合、カーネルはファームウェアからシステムの情報を得ます。時には変換の途中で失われるものがあります。あるいは、変換は正確でも、元のメッセージが誤りです。
例えば、あるシステムのファームウェアは、CPU数を多めに報告します。時には巨大なファクターで。もしRCUが素直にファームウェアを信じたら、普通はそうなのですが、CPUごとのkthreadをたくさん作りすぎるでしょう。この結果システムはそれでも正しく動作しますが、余分のkthreadは不必要にメモリを消費して、ps 一覧に現れた時には混乱を起こすかもしれません。
なのでRCUはあるCPUが実際に存在すると信じる事を自分に許す前に、そのCPUが実際にオンラインになってくるのを待たないといけません。このようにして起きる「幽霊CPU」(それは決してオンラインになりません)は、いくつかの面倒 を起こします。
初期ブート
Linuxカーネルのブートシーケンスは興味深いプロセスです。そして、RCUは初期に、rcu_init() がまだ呼ばれていない時にさえ使われます。実際は、RCUのいくつかのプリミティブは最初のタスクの task_structが使用可能となり、ブートCPUのCPUごと変数がセットアップされたらもう、使うことができます。リード側プリミティブ(rcu_read_lock(), rcu_read_unlock(), rcu_dereference(), そして rcu_access_pointer()) は、とても初期でも、正常に動作します。rcu_assign_pointer() もです。
call_rcu() は、ブートの間、いつでも呼ぶことができますが、コールバックは、スケジューラが完全に上がって走り出すまで呼ばれる保証はありません。コールバックがこのように遅延するのは、RCUは自分が完全に初期化されるまでコールバックを呼ばないという事実のためであり、その完全な初期化はスケジューラが自分自身を初期化して、RCUが自分の kthread を生成して走らせることができるようになる点までは起きないからです。理論的には、もっと早くコールバックを呼ぶことは可能でしょう。しかし、これは万能薬ではありません。なぜならば、そのようなコールバックが呼ぶことのできる操作は厳しく制限されているでしょうから。
たぶん驚かれるでしょうか、synchronize_rcu(), synchronize_rcu_bh() (以下で議論します)、そして synchronize_sched() は全て、ブートのとても初期の間に通常に動作します。その理由は、一つしかCPUがなく、プリエンプションも禁止されているからです。これは、synchronize_rcu() （もしくは、友達）呼び出し自身が、静止状態であり、そのため、グレースピリオドであることを意味します。このため、初期ブートの実装は no-op でかまいません。
synchronize_rcu_bh() と synchronize_sched() の両方は残りのブート期間も、通常に動作し続けることができます。それは、それらのRCUリード側クリティカルセクションに渡って、プリエンプションが禁止されているという事実のおかげです。また、まだ、一つしかCPUがないという事実のおかげでもあります。しかし、一旦、スケジューラが初期化を始めたら、プリエンプションは有効になります。まだ、一つしかCPUはありません。しかし、プリエンプションが有効になったという事実は、CONFIG_PREEMPT=y カーネルでは synchronize_rcu() の no-op 実装はもはやうまくいかないことを意味します。なので、スケジューラが初期化を始めたらすぐに、初期ブートの高速パスは無効にされます。これは、synchronize_rcu() は、コールバックをポストする自分のランタイムモードに切り替わることを意味します。その結果、全ての synchronize_rcu() 呼び出しは、対応するコールバックが呼ばれるまでブロックします。不幸にも、コールバックは、RCUのランタイムのグレースピリオド機構が上がって走りだすまで呼ばれることはできません。それは、RCUの kthread を生成することが許されるのに十分なほど、スケジューラが自分の初期化を終わるまでは起きることができません。このため、スケジューラ初期化の間に synchronize_rcu() を呼ぶとデッドロックになることがあります。
クイッククイズ１４：
では、CONFIG_PREEMPT=n カーネルでスケジューラ初期化の間、synchronize_rcu() はどうなるのですか？
私はこのブート時の要件を、繰り返し起こるシステムハングの結果として学びました。
割り込みとNMI
Linuxカーネルには割り込みがあります。そして、RCUリード側クリティカルセクションは、割り込みハンドラ内と割り込み禁止のコード領域内で合法です。call_rcu() の呼び出しも同じく合法です。
Linuxカーネルアーキテクチャによっては、アイドルでないプロセスコンテキストから割り込みハンドラに入って、決してそこから抜けることなく、その代わりにひそかにプロセスコンテキストに戻る遷移をすることができるものがあります。このトリックは、カーネル内からシステムコールを呼ぶのに使われることがあります。このような「半割り込み」は、RCUがどのように割り込みネストレベルを数えるかについてとても注意しなくてはいけないことを意味します。私はこの要件を、RCUの dyntick-idle コードを書き直している間に、厳しい方法で学びました。
Linuxカーネルにはマスク不可能割り込み(NMI)があります。そして、RCUリード側クリティカルセクションは、NMI ハンドラ内で合法です。ありがたいことに、call_rcu() を含むRCU更新側プリミティブはNMIハンドラ内では禁止されています。
名前とは異なり、Linuxカーネルアーキテクチャによっては、ネストしたNMIがあります。RCUはそれを正しく扱わないといけません。Andy Lutomirski はこの要件で私を 驚かせました。彼はまた、この要件を満足する アルゴリズム で親切にも私を驚かせてくれました。
ローダブルモジュール
Linuxカーネルには、ローダブルモジュールがあります。そしてこのモジュールは、アンロードすることもできます。あるモジュールがアンロードされた後に、その関数の一つを呼ぼうとする全ての試みはセグメントフォールトになります。なので、モジュールアンロード関数は、ローダブルモジュールの関数の全ての遅延呼び出しをキャンセルしなくてはいけません。例えば、完了していない全ての mod_timer() は del_timer_sync() もしくは同様のものによって扱われなくてはいけません。
不幸にも、RCUコールバックをキャンセルする方法はありません。あなたが一度、call_rcu() を呼んだら、そのコールバック関数は、システムが先に停止しないかぎり、いつかは呼び出されます。モジュールアンロード要求に応じてシステムをクラッシュするのは、通常は社会的に無責任と考えられるために、飛行中のRCUコールバックを扱う何か他の方法が必要です。
このためRCUは、rcu_barrier() を提供します。それは、全ての飛行中のRCUコールバックが呼ばれるまで待ちます。もしモジュールが call_rcu() を使ったら、その終了関数はこのため、未来の全ての call_rcu() 呼び出しを止めて、そして rcu_barrier() を呼ぶべきです。理論的には、元となるモジュールアンロードのコードが無条件に rcu_barrier() を呼ぶこともできますが、現実的には、それは受け入れがたい遅延を起こすでしょう。
Nikita Danilov はこの要件を、類似のファイルシステムアンマウントの状況のために指摘しました。そして、Dipankar Sarma は、rcu_barrier() をRCUに取り入れました。モジュールアンロードのための rcu_barrier() の必要性は、その後に明らかになりました。
ホットプラグCPU
Linux カーネルはCPUホットプラグをサポートします。それは、CPUが来ては去ることがあるのを意味します。もちろん、オフラインCPUから何らかのRCU API メンバを使うのは違法です。この要件は、DYNIX/ptx の最初の日からありました。しかし、一方、LinuxカーネルのCPUホットプラグ実装は、「興味深い」です。
LinuxカーネルのCPUホットプラグ実装は、ノーティファイアを持ち、それはいろいろなカーネルサブシステム（RCUを含みます）が、そのCPUホットプラグ操作に適切に応答することを可能とするために使われます。CPUホットプラグノーティファイアから、ほとんどのRCUを操作を呼ぶことができます。それには、synchronize_rcu() のような通常の同期グレースピリオド操作さえも含まれます。しかし、synchronize_rcu_expedited() のような急ぎのグレースピリオド操作はサポートされません。それは、現在の実装はCPUホットプラグ操作をブロックするために、デッドロックになるという事実のためです。
さらに、rcu_barrier() のような、全てのコールバックを待つ操作もサポートされません。それは、CPUホットプラグ操作のフェーズには、去るCPUのコールバックがそのCPUホットプラグ操作が終わるまでは呼ばれない時があるからです。それもデッドロックになります。
スケジューラとRCU
RCUはスケジューラに依存します。そして、スケジューラは自分のデータ構造のいくつかを守るためにRCUを使います。これは、以下の場合を除いて、スケジューラは最も外側のRCUリード側クリティカルセクションの真ん中では、runqueue ロックと優先度継承ロックを取ることを禁じられていることを意味します。(1)スケジューラが同じリード側クリティカルセクションを抜ける前にそれを放す場合。あるいは、(2)そのリード側クリティカルセクション全体に渡って、割り込みが禁止されている場合。同じ禁止が、この禁止が適用される何らかのロックを持っている時に取られる全てのロックにも（再帰的に！）適用されます。この規則に従う結果、プリエンプト可能RCUは、runqueue ロックもしくは優先度継承ロックを持っている時には、rcu_read_unlock_special() を呼んではいけません。こうしてデッドロックを防ぎます。
v4.4 の前は、スケジューラロックを取ったRCUリード側クリティカルセクションに渡ってプリエンプションを禁止することだけが必要でした。v4.4 で、急ぎのグレースピリオドは、IPI を使うようになりました。そして、このIPIはrcu_read_unlock()が低速パスを取るように強制することがあり得ます。なので、この急ぎのグレースピリオドの変更は、プリエンプションに加えて、割り込みも禁止することを必要としました。
RCUの側では、プリエンプション可能RCUのrcu_read_unlock()実装は、同様のデッドロックを避けるように注意深く書かれなくてはいけません。特に、rcu_read_unlock() は割り込みに耐えなくてはいけません。割り込みハンドラはrcu_read_lock() と rcu_read_unlock()の両方を呼ぶからです。この可能性のため、rcu_read_unlock() は負のネストレベルを使って、割り込みハンドラがRCUを使うことによる破壊的な再帰を避ける必要があります。
この、スケジューラとRCUの相互の要件の対は全くの驚きとして現れました。
前に述べたように、RCUはkthreadを使います。そして、このkthreadが過剰なCPU時間の蓄積をするのを避けることが必要です。この要件は驚きではありません。しかし、CONFIG_NO_HZ_FULL=y 付きでビルドされたときに、コンテキストスイッチが頻繁なワークロードを走らせた時に、RCUがそれに違反したのは実際、驚きでした。RCUはこの要件を満たすように、かなり進化してきました。コンテキストスイッチが頻繁で、CONFIG_NO_HZ_FULL=y のワークロードであっても。しかし、さらに改善する余地はあります。
トレースとRCU
RCUコードでトレースを使うのは可能です。しかし、トレース自身はRCUを使います。このため、トレースで使うために、rcu_dereference_raw_notrace() が提供されます。それは、それがない場合に起きる破壊的再帰を防ぎます。このAPIは、あるアーキテクチャの仮想化でも使われます。そこでは、RCUリーダーが、トレースが使えない環境で実行します。トレースの人々は、要件を見つけ、かつ、必要な修正を提供しました。なので、この驚きの要件は比較的苦痛のないものでした。
エネルギー効率
アイドルCPUに割り込むのは、社会的に受け入れがたいと思われています。特に、電池で給電される組み込みシステムの人にとっては。このため、RCUはどのCPUがアイドルであるかを検出することで、エネルギーを節約します。それには、アイドル状態から割りこまれたCPUを追跡することも含みます。これは、エネルギー効率要件の大きな部分です。このため私はこれを、怒りの電話で学びました。
RCUはアイドルCPUに割り込むのを避けますから、アイドルCPUでRCUリード側クリティカルセクションを実行するのは違法です。（CONFIG_PROVE_RCU=y 付きでビルドされたカーネルは、あなたがこれをしようとすると警告します。）RCU_NONIDLE() マクロと、_rcuidle イベントトレースが、この制限を回避するために提供されます。さらに、rcu_is_watching() を使って、現在このCPUでRCUリード側クリティカルセクションを走らせるのが合法かを判定することができます。私はアイドルループのコードを検証している時に、一方で診断の必要性を、もう一方で、RCU_NONIDLE() の必要性を学びました。Steven Rostedt は、 _rcuidle イベントトレースを提供しました。それは、アイドルループでとてもたくさん使われています。
ユーザ空間で走っている、nohz_full CPU を割り込むのも、同様に社会的に受け入れがたいです。なのでRCUは、nohz_full ユーザ空間実行を追跡しなくてはいけません。そして、CONFIG_NO_HZ_FULL_SYSIDLE=y カーネルでは、RCUは一方ではアイドルCPUを、もう一方では、アイドルであるかもしくはユーザ空間で実行中であるCPUを別々に追跡しなくてはいけません。いずれの場合も、RCUは時間の２点で状態をサンプルすることができなくてはいけません。そして、どれか他のCPUが何らかの時間を、アイドル、そして／あるいは、ユーザ空間での実行に費やしたかどうかを決定することができなくてはいけません。
これらのエネルギー効率要件を理解し、満足するのはとても難しいことがわかってきました。例えば、RCUのエネルギー効率コードは、５回以上、真っ白な紙からの書き直しを経ました。その最後のが、とうとう、本物のハードウェアで走る本物のエネルギー節約 を示すことができました。前に述べたように、私はこれらの要件の多くを怒りの電話で学びました。私をLinuxカーネルメーリングリストでフレームするくらいでは、明らかに、彼らのRCUのエネルギー効率バグに対する怒りを完全に発散させるには不十分だったのです！
メモリ効率
小さいメモリの、リアルタイムでないシステムは単純に、Tiny RCU を使えばいいとしても、コードサイズは、メモリ効率の一つの側面でしかありません。もう一つの側面は、call_rcu() と kfree_rcu() で使われる rcu_head 構造体の大きさです。この構造体は、ポインタの対以外には何も含みませんが、それは実際、多くのRCUで守られるデータ構造内に現れます。それには、サイズが致命的なものを含まれます。page 構造体は良い例です。それは、その構造体内の多くの union キーワードの存在でわかります。
グレースピリオドが過ぎるのを待っている rcu_head 構造体を追跡するために、RCUが、手作業で作られた単一連結リストを使っている理由の一つは、メモリ効率の必要性です。同じ理由で、rcu_head は、それをポストした call_rcu() あるいは kfree_rcu() のファイルと行番号を追跡するフィールドなどのデバッグ情報を含みません。この情報が、デバッグ専用カーネルビルドでいつかは現れることがあるかもしれませんが、今のところは、->func がしばしば必要なデバッグ情報を提供します。
しかし、場合によっては、メモリ効率の必要性は、よりずっと極端な手段につながることがあります。page 構造体に戻ると、rcu_head フィールドは対応するページの生涯のいろいろな点で使われるとても多くの他の構造体と記憶域を共用しています。ある競合条件を正しく解決するために、Linuxカーネルのメモリ管理サブシステムは、グレースピリオド処理の全てのフェーズで、特定のビットがゼロであり続けることを必要とします。そして、そのビットはたまたま、rcu_head 構造体の ->next フィールドの最低位ビットにマップします。RCUは、そのコールバックをポストするために、call_rcu() が使われる限り、それを保証します。それに対して、kfree_rcu() や、エネルギー効率のためにいつか作られるかもしれない、call_rcu() の未来の「遅延した」何らかの変種では保証はされません。
性能、スケーラビリティ、応答時間そして信頼性
以前の議論を続けますが、RCUはLinuxカーネルのネットワーキング、セキュリティ、仮想化、そしてスケジューリングコードパスの性能クリティカルな部分の、ホットなコードパスで大いに使われています。なのでRCUは、特にそのリード側プリミティブでは、効率的な実装を使わなくてはいけません。そのためにも、プリエンプト可能RCUのrcu_read_lock() 実装がインラインにできたら良いでしょう。しかし、それをするには、task_struct についての #include 問題を解決する必要があります。
Linux カーネルは４０９６CPUまでのハードウェア構成をサポートします。それは、RCUが極めてスケーラブルでなくてはいけないことを意味します。グローバルロックを頻繁に取ったり、グローバル変数への頻繁なアトミック操作をするアルゴリズムは単純にRCU実装では許されません。なのでRCUは、rcu_node 構造体を元にする combining tree をたくさん使います。RCUは、全てのCPUが連続してRCUのランタイムプリミティブのあらゆる組み合わせを呼び出すことに耐える必要があります。しかも、操作ごとのオーバーヘッドは最小です。実際、多くの場合、負荷を増すことは、操作ごとのオーバーヘッドを減らさなくてはいけません。synchronize_rcu(), call_rcu(), synchronize_rcu_expedited(), そして rcu_barrier() のバッチ最適化のために。一般的な規則として、RCUはLinuxカーネルの残りの部分がそれに投げつけると決めたものは何でも、喜んで受け入れなくてはいけません。
Linuxカーネルはリアルタイムワークロードのために使われます。特に、-rt パッチセットと組み合わせた時には。リアルタイム遅延応答の要件はあまりに厳しいので、伝統的な、RCUリード側クリティカルセクション全体でプリエンプションを禁止するアプローチは不適切です。なので、CONFIG_PREEMPT=y を付けてビルドされたカーネルは、RCUリード側クリティカルセクションがプリエンプト可能なRCU実装を使います。この要件は、ユーザが、以前のリアルタイムパッチが彼らの要求を満たさないことをはっきりさせた後で、その存在が知られるようになりました。それには、-rt パッチセットのごく初期のバージョンで発生するあるRCUの問題も関係しました。
さらに、RCUは１００マイクロ秒以下のリアルタイム遅延予算でなんとかやりくりしなくてはいけません。実際、-rt パッチセットを使う、より小さいシステムでは、Linuxカーネルは２０マイクロ秒以下のリアルタイム遅延をカーネル全体で提供します。それにはRCUも含まれます。なので、RCUのスケーラビリティと遅延は、このたぐいの構成で十分でなくてはいけません。私が驚いたことに、１００マイクロ秒以下のリアルタイム遅延予算は、最も巨大なシステムにもあてはまりました。それは、４０９６までのCPUを持つシステムも含みます。このリアルタイム要件は、グレースピリオド kthread の動機となりました。それはまた、いくつかの競合条件の扱いを単純にしました。
最後に、RCUが同期プリミティブであるという位置は、どんなRCUの失敗も、極めてデバッグが難しいことがある任意のメモリ破壊につながることを意味します。これは、RCUが極めて高信頼でなくてはいけないことを意味します。それは現実的には、RCUが攻撃的なストレステストスイートを持たなくてはいけないことも意味します。このストレステストを rcutorture と呼びます。
rcutorture の必要性は驚きではありませんが、現在の、Linuxカーネルのはかりしれない人気は、興味深く、そしてたぶん、今までにない検証への挑戦を課しています。これを見るために、今日では、１０億以上のLinuxカーネルの実行インスタンスがあることを考えてください。Android スマートフォン、Linux が使われているテレビジョン、そしてサーバーがありますから。この数は、祝福された Internet of Things の到来とともに、鋭利に増加することが予期されます。
RCUが、平均で１００万年の実行時間に一回現れる競合条件を含むとします。このバグは、インストールベース全体では、ほぼ一日に三回起きるでしょう。RCUは単純に、ハードウェア故障率の背後に隠れることもできるでしょう。誰も、自分のスマートフォンが何百万年も、もつとは実際、期待しないでしょうから。しかし、この考えに過度に安らぎを見出す人は、以下の事実を考えるべきです。つまり、ほとんどの法律では、それにはLinuxカーネルも含まれるかもしれない、ある機構の、安全が致命的ないくつかのタイプの資格証明のためには、複数年にわたる成功したテストで十分であるという事実を。実際、Linuxカーネルは既に、安全が致命的なアプリケーションのために本番で使われているという噂があります。あなたがどう思うかは知りませんが、私は、もしRCUのバグが誰かを殺したらとてもいやな気分になるでしょう。それが、最近私が検証と証明に焦点を置いていることを説明するかもしれません。
その他のRCUフレーバー
RCUに関して最も驚くべきことの一つは、今では少なくても５以上のフレーバー、あるいはAPIファミリーがあることです。さらに、これまで唯一の焦点であった主となるフレーバーには二つの異なる実装、プリエンプト不可能と可能な、があります。他の4つのフレーバーを以下に一覧とします。それぞれの要件は、個別の節で説明します。
１ ボトムハーフフレーバー
２ Sched フレーバー
３ スリープ可能RCU
４ Tasks RCU
ボトムハーフフレーバー
RCUのソフトウエア割り込み禁止(“bottom-half” とも呼びます。なので、略称は “_bh” です)、あるいは、RCU-bh は、Dipankar Sarma によって、Robert Olsson が研究したネットワークベースのサービス拒否攻撃に耐えられるRCUのフレーバーを提供するために開発されました。その攻撃は、そのシステムにあまりにたくさんのネットワーク負荷をかけるために、CPUのいくつかが決してソフトウエア割り込み実行を抜けられず、それらのCPUは全くコンテキストスイッチができなくなります。すると、当時のRCU実装では、グレースピリオドが終わることができません。その結果は、メモリ不足状態とシステムハングです。
解決策は、RCU-bh の作成でした。それは、そのリード側クリティカルセクションの間、local_bh_disable() をします。そしてそれは、コンテキストスイッチ、アイドル、ユーザーモード、そしてオフラインに加えて、あるタイプのソフトウエア割り込み処理から他のへの遷移も、静止状態として使います。これは、RCU-bh のグレースピリオドは、CPUのどれかが無限にソフトウエア割り込みを実行しても完了できることを意味します。このようにして、RCU-bh を元とするアルゴリズムがネットワークベースのサービス拒否攻撃に耐えることが可能となります。
rcu_read_lock_bh() と rcu_read_unlock_bh() はソフトウエア割り込みハンドラを禁止し、再度許可しますから、RCU-bh リード側クリティカルセクションの間にソフトウエア割り込みを始める全ての試みは遅延されます。この場合、rcu_read_unlock_bh() がソフトウエア割り込み処理を呼ぶでしょう。それはかなり時間がかかるかもしれません。もちろん、このソフトウエア割り込みオーバーヘッドは、rcu_read_unlock_bh() ではなく、RCU-bh リード側クリティカルセクションの後にあるコードに関連付けられるべきだと主張することができます。しかし事実は、ほとんどのプロファイリングツールはそこまでの細粒度の区別をするように期待できないということです。例えば、重いネットワーク負荷の間に、3ミリ秒の長さのRCU-bhリード側クリティカルセクションが実行したと思いましょう。その3ミリ秒の間に少なくても一つのソフトウエア割り込みハンドラを呼ぶ試みがあったというのはとてもありそうです。しかしそのような呼び出し全ては rcu_read_unlock_bh() の時まで遅延されます。これはもちろん、最初に見たときには、rcu_read_unlock_bh() がとても遅く動いているように 見えることがあります。
RCU-bh API には、 rcu_read_lock_bh(), rcu_read_unlock_bh(), rcu_dereference_bh(), rcu_dereference_bh_check(),
synchronize_rcu_bh(), synchronize_rcu_bh_expedited(), call_rcu_bh(), rcu_barrier_bh(), そして rcu_read_lock_bh_held() があります。
Sched フレーバー
プリエンプト可能RCUの前には、RCUグレースピリオドを待つことは、既存の割り込みとNMIハンドラを待つ副作用もありました。しかし、プリエンプト可能RCU実装には、この性質を持たないものがあります。そこでは、RCUリード側クリティカルセクションの外の全てのコードの地点は静止状態であることができます。なので、RCU-sched が作られました。それは、RCU-sched グレースピリオドが既存の割り込みとNMIハンドラを待つ点で「古典的」RCUにならいます。
CONFIG_PREEMPT=n 付きでビルドされたカーネルでは、RCU と RCU-sched API は同じ実装を持ちます。一方、CONFIG_PREEMPT=y でビルドされたカーネルはそれぞれ別の実装を提供します。
CONFIG_PREEMPT=y カーネルでは、rcu_read_lock_sched() とrcu_read_unlock_sched() は皆、プリエンプションを禁止、再許可することによく注意下さい。これは、RCU-sched リード側クリティカルセクションの間にプリエンプションの試みがあったら、rcu_read_unlock_sched() は、全ての遅延とオーバーヘッドを持ってスケジューラに入ることを意味します。rcu_read_unlock_bh() と同じように、これは、rcu_read_unlock_sched() がとても遅く動いたように見えることがあります。しかし、最も優先度の高いタスクはプリエンプトされません。なので、そのタスクは、低オーバーヘッドの rcu_read_unlock_sched() 呼び出しを楽しむでしょう。
RCU-sched API には、 rcu_read_lock_sched(), rcu_read_unlock_sched(), rcu_read_lock_sched_notrace(), rcu_read_unlock_sched_notrace(), rcu_dereference_sched(), rcu_dereference_sched_check(), synchronize_sched(), synchronize_rcu_sched_expedited(), call_rcu_sched(), rcu_barrier_sched(), そして rcu_read_lock_sched_held() があります。しかし、プリエンプションを禁止するものは全て、RCU-sched リード側クリティカルセクションを区切ります。それには、preempt_disable() and preempt_enable(), local_irq_save() そして local_irq_restore() などがあります。
スリープ可能RCU
１０年以上に渡って、誰かが、「私はRCUリード側クリティカルセクションの中でブロックする必要があります」というのを聞いたら、その誰かはRCUを理解していないことの確かなしるしでした。結局、もしあなたが、常にRCUリード側クリティカルセクションの中でブロックしているならば、あなたは多分、より高いオーバーヘッドの同期機構を使う余裕があるはずです。しかし、これは、Linux のノーティファイアの出現とともに変わりました。そのRCUリード側クリティカルセクションはほとんど決してスリープしませんが、時にはそうする必要があります。これは、スリープ可能RCU もしくは SRCU の導入につながりました。
SRCU は、異なるドメインが定義できます。そしてそのドメインのそれぞれは srcu_struct 構造体のインスタンスで定義されます。この構造体へのポインタを、それぞれのSRCU関数に渡さなくてはいけません。例えば、synchronize_srcu(&ss)。ここで、ss がその srcu_struct です。このドメインの鍵となる利点は、あるドメインの遅いSRCUリーダーはどれか他のドメインのSRCUグレースピリオドを遅らせないことです。とは言え、これらドメインの一つの結果は、リード側コードは srcu_read_lock() から srcu_read_unlock() に「クッキー」を渡さなくてはいけないことです。例えば、以下のとおり。
1 int idx;
2
3 idx = srcu_read_lock(&ss);
4 do_something();
5 srcu_read_unlock(&ss, idx);
前に述べたように、SRCU リード側クリティカルセクション内でブロックするのは合法です。しかし、大きな力は大きな責任を伴います。もしあなたが、あるドメインのSRCU リード側クリティカルセクションの一つの内で永遠にブロックしたら、そのドメインのグレースピリオドも永遠にブロックするでしょう。もちろん、永遠にブロックする一つの良い方法は、デッドロックです。それは、もしあるドメインのSRCU リード側クリティカルセクション内の任意の操作が、直接的あるいは間接的に、そのドメインのグレースピリオドが過ぎるのを待ってブロックすると起きることがあります。例えば、これは自己デッドロックになります。
1 int idx;
2
3 idx = srcu_read_lock(&ss);
4 do_something();
5 synchronize_srcu(&ss);
6 srcu_read_unlock(&ss, idx);
しかし、もし５行目で、ドメイン ss の synchronize_srcu() の間保持される mutex を取ったなら、それでもデッドロックは可能です。さらに、もし５行目で、どれか他のドメイン ss1 の synchronize_srcu() の間保持される mutex を取り、そしてドメイン ss1 のSRCU リード側クリティカルセクションが、ドメイン ss の synchronize_srcu() の間保持されるもう一つの mutex を取ったなら、またもやデッドロックは可能です。そのようなデッドロックサイクルは、任意の多数の異なるSRCUドメインに拡張することがあります。繰り返しますが、大きな力は大きな責任を伴います。
他のRCUフレーバーと異なり、SRCU リード側クリティカルセクションはアイドル、そしてオフラインCPUでさえ走ることができます。この能力は、srcu_read_lock() と srcu_read_unlock() がメモリバリアを含むことを要求します。それは、SRCUリーダーはRCUリーダーよりも少し遅く走ることを意味します。それはまた、smp_mb__after_srcu_read_unlock() API を動機付けます。それは、srcu_read_unlock() と組み合わせて、完全なメモリバリアを保証します。
SRCU API には、 srcu_read_lock(), srcu_read_unlock(), srcu_dereference(), srcu_dereference_check(),synchronize_srcu(), synchronize_srcu_expedited(), call_srcu(), srcu_barrier(), そして、 srcu_read_lock_held() があります。また、srcu_struct を定義し、初期化するための DEFINE_SRCU(), DEFINE_STATIC_SRCU(), そして init_srcu_struct() API があります。
Tasks RCU
トレーシングのある形式では、異なる型のプローブをインストールするために必要なバイナリの書き換えを処理するために、「トランポリン」を使います。古いトランポリンを解放できたら良いでしょう。それは、RCUの何らかの形式のすべきことのように聞こえます。しかし、コードの任意のところにトレースをインストールできることが必要なので、rcu_read_lock() と rcu_read_unlock() のようなリード側マーカーを使うことはできません。さらに、これらのマーカーをトランポリン自身に持つのはうまくいきません。なぜならば、rcu_read_unlock() の後には必ず命令があるだろうからです。synchronize_rcu() が、実行が rcu_read_unlock() に到達したことを保証したとしても、実行が完全にトランポリンを離れたことは保証できません。
解決策は、Tasks RCU の形式であり、自発的なコンテキストスイッチで区切られる暗黙のリード側クリティカルセクションを持つことです。つまり、schedule(), cond_resched_rcu_qs(), そして synchronize_rcu_tasks() の呼び出しです。それに加えて、ユーザ空間での実行からとそれへの遷移も tasks-RCU のリード側クリティカルセクションを区切ります。
tasks-RCU API はとてもコンパクトです。call_rcu_tasks(), synchronize_rcu_tasks(), とrcu_barrier_tasks() だけからなります。
将来あり得る変化
RCUが更新側のスケーラビリティを達成するために使う一つのトリックは、CPU数が多くなるにつれて、グレースピリオド遅延を増すことです。もしこれが深刻な問題となったら、グレースピリオド状態マシンを作り直して、さらに遅延を増やす必要が無いようにする必要があるでしょう。
急ぎのグレースピリオドはCPUを走査します。なのでその遅延とオーバーヘッドはCPU数が多くなるにつれて増します。もしこれが巨大システムで深刻な問題となったら、このスケーラビリティ問題を避けるために何らかの再設計が必要でしょう。
RCUはいくつかの場所でCPUホットプラグを禁止します。多分、最も有名なのは、急ぎのグレースピリオドと rcu_barrier() 操作において。もしもCPUホットプラグノーティファイアで急ぎのグレースピリオドを使う強い理由があるなら、CPUホットプラグを禁止するのをやめる必要があります。これはかなりの複雑さをもたらすでしょう。なので、とても良い理由があるべきでしょう。
グレースピリオド遅延を一方とし、他のCPUへの割り込みを一方とするトレードオフは、再検討する必要があるかもしれません。希望はもちろん、急ぎのグレースピリオド操作の間、ゼログレースピリオド遅延とゼロプロセッサ間割り込みの発生です。この理想は実現不可能でしょうが、もう少しの改善ができるというのはあり得ます。
RCUのマルチプロセッサ実装は、combining tree を使ってCPUをグループにして、ロック競合を減らしてキャッシュ局所性を増します。しかしこの combining tree は、そのメモリをNUMAノード間に広げることもなく、CPUグループをソケットやコアのようなハードウェア機能に合わせることもありません。そのような拡散と整列は現在では不必要と信じられています。なぜならば、ホットパスであるリード側プリミティブは combining tree をアクセスすることはありませんし、一般の場合の call_rcu() もそうしないからです。もしあなたが、あなたのアーキテクチャがそのような拡散と整列が必要だと信じるならば、あなたのアーキテクチャは rcutree.rcu_fanout_leaf ブートパラメタからも利益を受けるはずです。それは、ソケット内のCPU数、NUMAノード数、あるいは何にでも設定することができます。CPU数が大きすぎるなら、CPU数の約数を使いましょう。もしCPU数が巨大な素数なら、ええと、それは確かに、「興味深い」アーキテクチャの選択ですね。より柔軟なしかけを考えることもできるでしょう。ただし、rcutree.rcu_fanout_leaf ではだめなことがわかったならば。そして、それがだめなことが注意深く実行され、現実的なシステムレベルのワークロードによって示された場合に限り。
RCUがCPU番号をマップし直す必要があるしかけは、必要性が極めて明らかに示されることと、代替策を完全に調査することを必要とするだろうことに注意下さい。
RCUのフレーバーは困るほどたくさんあります。この数は時とともに増え続けてきました。将来いつか、そのいくつかを一緒にするとができるでしょう。
RCUのいろいろな kthread はかなり最近加わったものです。極端な負荷をもっと優雅に扱うために調整が必要だろうというのはとてもあり得ます。また、RCUの kthread とソフトウェア割り込みハンドラによるCPU使用率を、このCPU使用率を引き起こしたコードに関連付ける必要があるようになるかもしれません。例えば、RCUコールバックオーバーヘッドはその元となった call_rcu() インスタンスに課金できるかもしれません。ただし、多分、本番カーネルでは無いならば。
まとめ
この文書は、二十年以上にわたるRCUの要件を紹介しました。要件は変わり続けることから、これはこの主題に関する最後の言葉ではないでしょう。しかし、それは少なくても現在明らかな要件の重要なサブセットを知る役には立つでしょう。
謝辞
この記事を、人間が読めるようにしてくれた、Steven Rostedt, Lai Jiangshan, Ingo Molnar, Oleg Nesterov, Borislav Petkov, Peter Zijlstra, Boqun Feng, そして Andy Lutomirski の助けに感謝します。この作業への Michelle Rankin の助けに感謝します。他の貢献者への感謝は Linux カーネルの git アーカイブにあります。マンガは、copyright (c) 2013 by Melissa Broussard で、Creative Commons Attribution-Share Alike 3.0 United States ライセンスのもとで提供されます。
クイッククイズの答え
１
まず、もし更新者がリーダーにブロックされるのを望まないならば、call_rcu() あるいは kfree_rcu() を使うことができます。これについてはあとで説明します。次に、synchronize_rcu() を使っても、他の更新側のコードは実際にリーダーと同時実行して走れます。既存のリーダーも、そうでないものも。
２
追加のグレースピリオドがないと、メモリのリオーダリングの結果、do_something_dlm() が、recovery() の最後のビットと同時実行して、do_something() を実行することになります。
３
いいえ。起きません。リーダーは、gp の代入までは、これら二つのフィールドのいずれも見ることはできません。その時には、両方のフィールドが完全に初期化されています。なので、p->a と p->b の代入をリオーダーしても、何の問題も起きるはずはありません。
４
do_something_gp() が rcu_dereference() を使わなかったら何が起きるかから始めましょう。それは以前にこの同じポインタからフェッチした値を再使用するかもしれません。それはまた、gp からポインタを、一度に1バイトずつフェッチするかもしれません。それは、load tearing になり、二つの別々のポインタ値のバイトごとのまぜこぜになります。それは value-speculation 最適化を使うことさえするかもしれません。そこで推測を誤り、しかし、値をチェックするところに来るまでの間に、更新者がそのポインタを誤った推測に等しくなるように変更するかもしれません。その途中で、初期化前のごみを返した全てのデレファレンスはお気の毒！
remove_gp_synchronous() に関しては、gp への全ての更新が gp_lock を持っている間に行われるため、前記最適化は無害です。しかし、CONFIG_SPARSE_RCU_POINTER=y をつけると、あなたが gp に __rcu をつけて定義し、rcu_access_pointer() も rcu_dereference() も使わないでそれをアクセスしたら、sparse は文句を言います。
５
もしRCUが、ある synchronize_rcu() インスタンスの前に、あるRCUリード側クリティカルセクションが始まったのかどうかわからないときは、それは、そのRCUリード側クリティカルセクションが先に始まったと仮定しなくてはいけません。言葉を代えて言えば、synchronize_rcu() のあるインスタンスは、それが、あるRCUリード側クリティカルセクションよりも先に始まったことを証明できるときに限って、待たないでよいです。
６
はい。それらは本当に必要です。なぜ最初の保証が必要かを見るために、以下のイベントのシーケンスを考えましょう。
CPU 1: rcu_read_lock()
CPU 1: q = rcu_dereference(gp); /* Very likely to return p. */
CPU 0: list_del_rcu(p);
CPU 0: synchronize_rcu() starts.
CPU 1: do_something_with(q->a); /* No smp_mb(), so might happen after kfree(). */
CPU 1: rcu_read_unlock()
CPU 0: synchronize_rcu() returns.
CPU 0: kfree(p);
なので、RCUリード側クリティカルセクションとグレースピリオドの終わりの間には、絶対に完全なメモリバリアがなくてはいけません。
二つ目の規則が必要なことを示すイベントのシーケンスはほぼ同じです。
CPU 0: list_del_rcu(p);
CPU 0: synchronize_rcu() starts.
CPU 1: rcu_read_lock()
CPU 1: q = rcu_dereference(gp); /* Might return p if no memory barrier. */
CPU 0: synchronize_rcu() returns.
CPU 0: kfree(p);
CPU 1: do_something_with(q->a); /* Boom!!! */
CPU 1: rcu_read_unlock()
そして同様に、グレースピリオドの始めとRCUリード側クリティカルセクションの始めの間にメモリバリアが無いため、CPU1はフリーリストをアクセスすることになるかもしれません。
“as if”（で、あるかのような）規則はもちろん適用されます。なので、適切なメモリバリアがあるかのように動作する実装は全て、正しい実装です。とは言え、で、あるかのような規則に従ったと信じるようにご自分をごまかすよりも、実際に規則に従う方が、ずっと簡単ですよ！
７
そうしません。通常のRCU更新と同じで、それはRCUリーダーを排除しません。
８
いいえ。READ_ONCE() と WRITE_ONCE() にある volatile キャストは、この特別な場合には、コンパイラがリオーダーするのを防ぎます。
９
いいえ。synchronize_rcu() が、全てのリーダーが完了するのを待ったとしても、synchronize_rcu() が完了した後すぐに、新しいリーダーが開始するかもしれません。なので、synchronize_rcu() の後のコードは、いかなる場合もリーダーがいないことに依存することはできません。
１０
理論的には、無限大です。現実的には、実装の詳細とタイミングの問題の両方に敏感な未知の数です。なので、現実においても、RCUの使用者は、現実的な解答でなく理論的解答に従わなくてはいけません。
１１
それは、LinuxカーネルのRCUリード側クリティカルセクションでは禁止されます。なぜならば、RCUリード側クリティカルセクション内に静止状態(今の場合、自発的コンテキストスイッチ)を置くのは違法だからです。しかし、ユーザ空間のRCUリード側クリティカルセクションと、それに、Linuxカーネルのスリープ可能RCU(SRCU) リード側クリティカルセクションではスリープするロックを使ってもよいです。さらに、-rt パッチセットはスピンロックをスリープするロックに変えますから、対応するクリティカルセクションはプリエンプト可能です。これは、このスリープするようにされたスピンロック(ただし、他のスリープするロックはだめ！)は、-rt Linux カーネルのリード側クリティカルセクションで取ることができることも意味します。
なお、通常のRCUリード側クリティカルセクションが条件付きでスリープするロック(mutex_trylock() のように)を取ることは合法であることに注意下さい。ただし、そのスリープするロックを条件付きで取ろうとして無限にループしてはだめです。鍵となる点は、mutex_trylock() のようなものは、mutex を取って戻るか、あるいは mutex がすぐに取れないときはエラーを返すかのどちらかであることです。いずれにしても、mutex_trylock() はスリープせずにすぐに戻ります。
１２
たぶん、１８行目で取られる ->gp_lock は、全ての変更を排除します。それには、rcu_dereference() が対策して守ろうとする挿入も全て含まれます。なので、全ての挿入は２５行目で ->gp_lock が放されるまで待たされます。これは、その結果、rcu_access_pointer() で十分であることを意味します。
１３
そのようにものごとを定義することはできます。しかしその類いの定義によれば、ガーベッジコレクションのある言語では、更新は次回にガーベッジコレクタが走る時まで完了できないということになるのを心に留めて下さい。それは全く合理的とは言えません。鍵となる点は、ほとんどの場合、call_rcu() あるいは kfree_rcu() を使う更新者は call_rcu() あるいは kfree_rcu() を呼んだら直ちに次の更新に進むことができ、以降のグレースピリオドを待つ必要はないということです。
１４
CONFIG_PREEMPT=n カーネルでは、synchronize_rcu() は直接、synchronize_sched() にマップします。なので、synchronize_rcu() は、CONFIG_PREEMPT=n カーネルでは、ブートの間ずっと、正常に動きます。しかし、あなたのコードは CONFIG_PREEMPT=y カーネルでも動かなくてはいけません。なので、スケジューラの初期化の間に synchronize_rcu() を呼ぶのを避けるのは、やはり必要です。
以上