tkokamoの日記

HPCの研究開発なのでそんなことをかきたい

RCU(Read Copy Update)をちゃんと知る(1)-2 実装よりの概要

はじめに

前回(http://tkokamo.hateblo.jp/entry/2017/05/31/213427)は、かなりざっくりとした理解だったのでもう少し実装に近づいた概要です。

(1) 概要(概要)← 前回と今回
(2) Linuxでの実装
(3) rcu-walk(RCUの応用先)

今回までで概要は終わらして、次回からは実際の実装を見ていこうと思っています。

RCUの種類

現在のLinuxには大きく以下のRCUの実装があるようです。(https://lwn.net/Articles/541037/)

参照クリティカルセクション内でブロック不可 ブロック可
SMP非対応 Tiny RCU Tiny Sleepable RCU
SMP対応 Tree RCU (これを理解したい) Tree Sleepable RCU

Sleepable RCU(SRCU)について


クリティカルセクション内で眠れるなんて、すばらしいじゃないか!と思いますが、実際はそんなに使われていません。 (4.13-rc3では、rcu_read_lock:875件、srcu_read_lock:57件)

SRCUの実装はよくわかっていませんが、参照クリティカルセクションでブロックが発生すると参照期間が当然伸びます。そして、これは古いデータが解放されるまでの時間(grace period)が伸びるということを意味します。
grace periodが長くなると、その間に複数世代のデータが作られメモリを圧迫してしまう危険があるので、好ましくありません。
SRCUについてはこれ以上深くはつっこみませんが、興味がある方はhttp://www.rdrop.com/~paulmck/RCU/srcu.2007.01.14a.pdfを見ると良いかと思います。(少し古いです)

Classic RCUとTree RCU


v2.6で当初実装されたRCUはClassic RCUと呼ばれていますが、CPU数が増えると更新側の性能がスケールしない、無駄に電力を使ってしまう、などといった問題がありました。(※CPU数が増えると、といっても数百とかいったレベルらしい)
これらの問題を解決したRCU実装がTree RCUで、現在はTree RCUが用いられています。
参考:http://www.atmarkit.co.jp/flinux/rensai/watch2009/watch04a.html RCUの全面書き直しも! 2.6.29は何が変わった?(1/2) − @IT

Tree RCU(とrcu walk)を理解するのが目的ですが、SMP環境におけるRCUの仕組みを知るには、まずはClassic RCUから見ると良いかと思うので、Classic RCUについて見ていってからTree RCUに手を伸ばそうと思います。(今回ではないです)

RCUのAPIと処理概要

以下に参照側と更新側が用いるRCUのAPIとgrace periodの関係などを表してみました。

f:id:tkokamo:20170812174518p:plain

参照側が呼び出す関数は以下の通りです。

関数 説明
rcu_read_lock() 参照側クリティカルセクションを開始する。実際はただプリエンプションを無効にするだけ
rcu_read_unlock() 参照側クリティカルセクションを終了する。実際はただプリエンプションを有効にするだけ
rcu_dereference() RCUで管理されているデータのポインタを参照する。

更新側が呼び出す関数は以下の通りです。

関数 説明
rcu_assign_pointer() RCUで管理されているデータのポインタを更新する。
call_rcu() 更新前の古いデータへの参照がなくなった時に呼ばれる回収用のコールバック関数を登録する。
synchronize_rcu() grace periodがすぎるまで待ち合わせる。古いLinuxではsynchronize_kernel()

上の図では、CPU0の更新者(update)がcall_rcu()を呼んだ時、参照側クリティカルセクション内にいるCPU2、CPU3の参照者(read)が参照側クリティカルセクションを抜けるまで、古いデータを保持しておく必要があります。
CPU1の2つ目の参照者はcall_rcu()後に参照を始めているため、最新の値を参照しています。そのため、このタスクが参照をやめるまで待つ必要はありません。

実際には、call_rcu()呼び出し後、全てのCPUについてcontext switchが起きたらcall_rcu()で登録されたコールバック関数を呼び出し、古いデータの回収を行うことができます。
最初は「?」となりましたが、以下のように少し整理すると、正しいことがわかります。
参照側クリティカルセクションではプリエンプションが禁止されており、この間にcontext switchが起きることはありません。
逆にいうと、context switchが起きたCPUは参照側クリティカルセクションにいないことが保証されます。
そのため、call_rcu()後、すべてのCPUでcontext switchが起きた時、古いデータの参照は終わっていると判断できるのです。

おわりに

前回と今回でRCUの大雑把な理解はできると思います。
間違いなどありましたら、指摘いただけると助かります。

次回からは、実際にRCUのAPIのコードを以下のような流れで見ていこうと思います。

  • rcu_dereference(), rcu_assign_pointer()
  • Classic RCUの回収処理など
  • Tree RCUの回収処理など