はじめに
つい先日、OpenBSDに SMR という名前のカーネル同期機構がコミットされたのでソースコードを読んでみました。コミットログにも書いてありますが、Linux (Classic) RCUと機能的にはほぼ同じだと思います。(実装はおそらくあまり似ていないはず。)
SMRの概要
- SMRはSafe Memory Reclamationの略
- Linux Classic RCUとほぼ同機能
- リーダー側のクリティカルセクションAPIとライター(解放)側の待ち合わせ用APIが提供される
- クリティカルセクション内ではスリープ不可
- 対象要素が安全に解放されるまで待つAPIと遅延解放してくれるAPIがある
- SMR用リスト操作APIが提供される
- リーダー側APIもライター(解放)側APIも割り込みハンドラから使える
- タイミング的にOpenBSD 6.5で初登場
- 使っているコードはまだ存在しない(2019/03/03現在)
- マニュアルも存在しない
- 似た機能であるOpenBSD SRPとの棲み分けは不明
SMRのコードを読む
グローバル変数など
- smr_thread
- 安全だと思われる状態まで待ち合わせたのち、グローバルなリスト(
smr_deferred)に繋げられた解放対象要素のコールバック関数を呼ぶ - 待ち合わせは
smr_grace_wait関数で実装されている(後述)
- 安全だと思われる状態まで待ち合わせたのち、グローバルなリスト(
-
smr_deferred- 解放対象要素が繋げられたリスト
- 参照中の要素ではない
-
smr_dispatch(後述)でCPUローカルのリストからこのリストに移される -
smr_threadで要素が取り出される
- 解放対象要素が繋げられたリスト
-
smr_ndeferred-
smr_deferredの要素数 -
smr_threadを起こすためのオブジェクト(条件変数のようなもの)としても使われる
-
-
smr_expedite-
smr_threadでsmr_grace_waitを呼ぶ前に遅延を挟むかどうかのフラグ - 遅延は100ms
- どういうときに遅延を入れるか/入れないかは不明
-
API
-
smr_read_enter- リーダー側のクリティカルセクションの開始時に呼ぶ
- 通常時は何もしない1
- もしidleプロセスが割り込まれて、その割り込みハンドラで
smr_read_enterが呼ばれた場合は、フラグを立てておく- SMRはidleプロセスが実行している ＝ 通常のプロセス(スレッド)が実行していない ＝ クリティカルセクションを抜けている、という判断をしているため、このケースは例外的な扱いをしなければならない
- フラグはスケジューラのCPUローカルな変数であるspc_insmrに設定される
-
smr_read_leave- リーダー側のクリティカルセクションの終了時に呼ぶ
- 何もしない
-
smr_call,smr_barrier,smr_flush- ライター(解放)側で要素を解放したいときに使うAPI
-
smr_callはコールバックを指定して遅延解放させるAPI -
smr_barrierとsmr_flushは解放可能な状態になるまで待ち合わせるAPI -
smr_barrierとsmr_flushは内部的には、解放対象要素を追加してsmr_callを呼び、そのコールバックが呼ばれるまで待ち合わせる、という動作をする -
smr_flushのみsmr_expediteのフラグを立てる
-
smr_callはCPUローカルのリストに解放対象要素をつなぐ- 繋がれた要素は
smr_dispatch(後述)でグローバルなリストにつなぎ直される - 例外的にidleプロセス実行中に割り込んだ割り込みハンドラから呼ばれたときは即座にグローバルなリストに移動させられる
- 繋がれた要素は
重要な関数
-
smr_dispatch- CPUローカルなリストに繋がれている解放対象要素をグローバルなリストにつなぎ替える
-
smr_dispatchはmi_switchかsched_idleから呼ばれる- つまりクリティカルセクションを実行するスレッドはすでにいなくなっているとき
- このときspc_insmrのフラグがクリアされる
- また
smr_dispatchはsmr_threadを起こす- 遅延しない場合は即座に起こし、遅延する場合は100ms後に起こす
-
smr_grace_wait-
smr_threadで呼ばれる - すべてのCPUを走査して、idleでないプロセスが実行中かもしくはspc_insmrのフラグがまだ立っている場合、そのCPUへ自分自身を移動させる
- 移動先のCPUで自分がディスパッチされる ＝ クリティカルセクションを実行中のスレッドはすでにいなくなっているはず
-
- 備考
- 基本的には
smr_dispatchされた段階で安全に解放できるような気がするのだがsmr_grace_waitが必要になるケースがどういう時なのかは不明
- 基本的には
おわりに
というわけで一通り読んでみました。なぜsmr_grace_waitが必要になるのか等、不明な点はありますが、動作の概要はわかったような気がします。
コードが修正されたりマニュアルが追加されたら、記事を更新するかもです。
-
実行中のスレッドのCPUが横取りされるケースを考慮していないのは、OpenBSDカーネルが横取りをサポートしていないためだと思われる。 ↩