はじめに

つい先日、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
- リーダー側のクリティカルセクションの開始時に呼ぶ
- 通常時は何もしない¹
- もし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カーネルが横取りをサポートしていないためだと思われる。 ↩

OpenBSDカーネルの新しい同期機構SMRのコードを読んだときのメモ