はじめに
FreeBSDには、read-mostlyロック(rmlock(9))という、reader/writerロック(rwlock(9))に似たロックプリミティブがある。ロック利用者のほとんどがreaderの場合、rwlockに比べてreaderのスケーラビリティが高い。
本エントリでは、そのrmlockの実装をざっと読んでみる。対象のソースコードはFreeBSD 11相当である。
rmlockの特徴
- rwlockとほぼ同じセマンティクスで使える
- rwlockと異なりロック・アンロックAPIに
trackerと呼ばれるローカル変数を追加で渡すように修正が必要 - rwlockをrmlockに置き換えるのは比較的容易1
- rwlockと異なりロック・アンロックAPIに
- rwlockに比べて、reader数（≒CPU数）に対してスケーラブル
- readerのfast pathではアトミック命令を使っていない2
- writerが重い
- readerがいなくなるのを待ち合わせる処理が重い
- writerが待っている間は、新規readerも待たされるので、引きずられてreaderも長く待たされる可能性がある
- rmlockを持ったままblock/sleepしても良い3
readerの動作
rm_rlock、rm_runlockのコードを読む。双方とも、writerがいなければ軽い処理(fast path)のみで終了し、writerがいるとさらに重い処理(slow path)を実行することになる。
rm_rlock
Fast path
rm_rlockがreaderロック取得APIであるが、内部実装では、_rm_rlockがメインの関数である。短いので全部載せる。
426 int
427 _rm_rlock(struct rmlock *rm, struct rm_priotracker *tracker, int trylock)
428 {
429 struct thread *td = curthread;
430 struct pcpu *pc;
431
432 if (SCHEDULER_STOPPED())
433 return (1);
434
435 tracker->rmp_flags = 0;
436 tracker->rmp_thread = td;
437 tracker->rmp_rmlock = rm;
438
439 if (rm->lock_object.lo_flags & LO_SLEEPABLE)
440 THREAD_NO_SLEEPING();
441
442 td->td_critnest++; /* critical_enter(); */
443
444 __compiler_membar();
445
446 pc = cpuid_to_pcpu[td->td_oncpu]; /* pcpu_find(td->td_oncpu); */
447
448 rm_tracker_add(pc, tracker);
449
450 sched_pin();
451
452 __compiler_membar();
453
454 td->td_critnest--;
455
456 /*
457 * Fast path to combine two common conditions into a single
458 * conditional jump.
459 */
460 if (0 == (td->td_owepreempt |
461 CPU_ISSET(pc->pc_cpuid, &rm->rm_writecpus)))
462 return (1);
463
464 /* We do not have a read token and need to acquire one. */
465 return _rm_rlock_hard(rm, tracker, trylock);
466 }
重要な箇所は448行目のrm_tracker_addと460行目の条件式である。
448行目：rm_tracker_addは_rm_rlockの引数で渡されたtrackerをCPU毎のリストに繋いでいる。これにより現在のCPU上にreaderが一人追加される。このリストはCPU毎のデータでかつ当該CPU上でしか操作しないため、ロックは不要である。
460行目：条件式が真になる細かい条件はともかく、ここではslow pathにフォールバックするかどうかを判定しているはずである。つまり、writerがロックを取得しているか、もしくは取得しようとしているかどうかを判断している4。
条件式にあるtd->td_owepreemptはプリエンプションされようとしているときに非0になるスレッド構造体の変数である。rmlockのロジックとはあまり関係がないため、ここでは無視する。
rm->rm_writecpusはCPUビットマップで、初期値はオール1、readerがslow pathを一度でも通れば当該CPUのビットが0になる。rm->rm_writecpusのビットが1に戻るのは、writerがrm_wlockを呼んだときだけなので、read-mostlyなのであればビットは基本的には0になっていると思って良い。(rm_wlockの節でwriterの動作を説明する。)
ぱっと見わからないが、462行目で_rm_rlockを抜けるまでにアトミック命令を一度も使っていない。(sched_pinも使っていない。)
Slow path
rm_rlockのslow pathの本体は_rm_rlock_hardである。
前半は例外的な処理が多いので省略する。1点だけ書くと、rm_tracker_removeでCPU毎のリストから一旦trackerを外している。これは、まだ正式にreaderになっていないためである5。リストへはslow pathの最後に繋ぎ直す。
以下に後半の必要なコードのみ掲載する。
408 mtx_lock(&rm->rm_lock_mtx);
409 }
410
411 critical_enter();
412 pc = pcpu_find(curcpu);
413 CPU_CLR(pc->pc_cpuid, &rm->rm_writecpus);
414 rm_tracker_add(pc, tracker);
415 sched_pin();
416 critical_exit();
417
418 if (rm->lock_object.lo_flags & LO_SLEEPABLE)
419 sx_xunlock(&rm->rm_lock_sx);
420 else
421 mtx_unlock(&rm->rm_lock_mtx);
422
423 return (1);
424 }
408行目：内部ロック(rm_lock_mtx)を取得している。このロックはrm_wlockの処理中に保持されるロックのため、このロックが取れたということはwriter側の必要な処理が終わったということである。あとでrm_wlockのコードを読むので分かるが、rm_wlockはかなり重い処理を行なうため、このロックが取れるまでにはかなり待たされることになる。
その後、_rm_rlockの説明にも出てきたrm_writecpusの自分のCPUのビットをクリアし、rm_tracker_addでtrackerをリストを繋ぐ。これによりreaderが1人増えたことになる。
最後にロックを解放して関数を抜ける。
rm_runlock
Fast path
rm_tracker_removeでリストからtrackerを外し、以下の条件式を満たすならばすぐに関数から抜ける。
519 if (0 == (td->td_owepreempt | tracker->rmp_flags))
520 return;
プリエンプションの方がおいておくと、今度はrmp_flagsというフラグが0の場合に条件を満たす。このフラグはwriterが当該readerの存在を認識しているときに非0になる。ざっくりいうとreaderからwriterにアクションが必要になるときに非0になる。詳しくはrm_wlockで説明する。
もし条件を満たさなければ、slow pathに移行する。
Slow path
_rm_unlock_hardがslow pathのコードである。これも短いため、すべて掲載する。
468 static void
469 _rm_unlock_hard(struct thread *td,struct rm_priotracker *tracker)
470 {
471
472 if (td->td_owepreempt) {
473 td->td_critnest++;
474 critical_exit();
475 }
476
477 if (!tracker->rmp_flags)
478 return;
479
480 mtx_lock_spin(&rm_spinlock);
481 LIST_REMOVE(tracker, rmp_qentry);
482
483 if (tracker->rmp_flags & RMPF_SIGNAL) {
484 struct rmlock *rm;
485 struct turnstile *ts;
486
487 rm = tracker->rmp_rmlock;
488
489 turnstile_chain_lock(&rm->lock_object);
490 mtx_unlock_spin(&rm_spinlock);
491
492 ts = turnstile_lookup(&rm->lock_object);
493
494 turnstile_signal(ts, TS_EXCLUSIVE_QUEUE);
495 turnstile_unpend(ts, TS_EXCLUSIVE_LOCK);
496 turnstile_chain_unlock(&rm->lock_object);
497 } else
498 mtx_unlock_spin(&rm_spinlock);
499 }
481行目：LIST_REMOVEは(わかりにくいが)rm_activeReadersというリストからtrackerを外している。
483-497行目：RMPF_SIGNALというフラグが立っている場合に、writerを起床している(turnstile_signal)。RMPF_SIGNALフラグが立つ条件は、writerが当該readerを待ってsleepしており、起こされるのを待っているときである。(詳しくはrm_wlockの節で説明する。)
rm_activeReadersの排他制御にrm_spinlockというグローバルなロックを使っているため、スケーラビリティを落とす要因になりそうである。
writerの動作
rm_wlock
rm_wlockの本体は_rm_wlockである。意外と短いため、すべて載せる。
525 void
526 _rm_wlock(struct rmlock *rm)
527 {
528 struct rm_priotracker *prio;
529 struct turnstile *ts;
530 cpuset_t readcpus;
531
532 if (SCHEDULER_STOPPED())
533 return;
534
535 if (rm->lock_object.lo_flags & LO_SLEEPABLE)
536 sx_xlock(&rm->rm_lock_sx);
537 else
538 mtx_lock(&rm->rm_lock_mtx);
539
540 if (CPU_CMP(&rm->rm_writecpus, &all_cpus)) {
541 /* Get all read tokens back */
542 readcpus = all_cpus;
543 CPU_NAND(&readcpus, &rm->rm_writecpus);
544 rm->rm_writecpus = all_cpus;
545
546 /*
547 * Assumes rm->rm_writecpus update is visible on other CPUs
548 * before rm_cleanIPI is called.
549 */
550 #ifdef SMP
551 smp_rendezvous_cpus(readcpus,
552 smp_no_rendevous_barrier,
553 rm_cleanIPI,
554 smp_no_rendevous_barrier,
555 rm);
556
557 #else
558 rm_cleanIPI(rm);
559 #endif
560
561 mtx_lock_spin(&rm_spinlock);
562 while ((prio = LIST_FIRST(&rm->rm_activeReaders)) != NULL) {
563 ts = turnstile_trywait(&rm->lock_object);
564 prio->rmp_flags = RMPF_ONQUEUE | RMPF_SIGNAL;
565 mtx_unlock_spin(&rm_spinlock);
566 turnstile_wait(ts, prio->rmp_thread,
567 TS_EXCLUSIVE_QUEUE);
568 mtx_lock_spin(&rm_spinlock);
569 }
570 mtx_unlock_spin(&rm_spinlock);
571 }
572 }
535-538行目：内部のロックを取得している。readerのfast pathはロックを取らないので、read-mostlyな状況ではすぐにロックを取得できるはずである。
540行目：条件式はわかりにくいが、CPU_CMPはビットマップが一致すると0を返すので、rm_writecpusがallcpusと一致しないときにブロックに入る。一致しなくなるのは、_rm_rlock_hardにあった通り、いずれかのCPUで1度でもreaderがslow pathを通ったときである。つまりreaderが少なくとも一人は存在し、そのためのケアをしなければならなときである。もしreaderが一人もいなければ(そんなことはほとんどないだろうが)、すぐに_rm_wlockを抜ける。
ブロック内の処理は短いがかなり重い。
542-544行目：rm_writecpusのうち0になっている部分を1に変えたものをreadcpusに入れ、rm_writecpusをallcpusにリセットしている(≒オール1にする)。
readcpusにはプロセッサ間割り込み(IPI)が必要なCPUのビットマップが入る。read-mostlyロックを特性上、ほとんどの場合はオール1(allcpusと一致する)だと思われる。
551-555行目：対象CPU上でrm_cleanIPI関数を呼び出すIPIを発行している。rm_cleanIPIもコードが短いの全部載せる。
254 static void
255 rm_cleanIPI(void *arg)
256 {
257 struct pcpu *pc;
258 struct rmlock *rm = arg;
259 struct rm_priotracker *tracker;
260 struct rm_queue *queue;
261 pc = pcpu_find(curcpu);
262
263 for (queue = pc->pc_rm_queue.rmq_next; queue != &pc->pc_rm_queue;
264 queue = queue->rmq_next) {
265 tracker = (struct rm_priotracker *)queue;
266 if (tracker->rmp_rmlock == rm && tracker->rmp_flags == 0) {
267 tracker->rmp_flags = RMPF_ONQUEUE;
268 mtx_lock_spin(&rm_spinlock);
269 LIST_INSERT_HEAD(&rm->rm_activeReaders, tracker,
270 rmp_qentry);
271 mtx_unlock_spin(&rm_spinlock);
272 }
273 }
274 }
この関数は、当該CPUにあるすべてのtrackerのrmp_flagsにRMPF_ONQUEUEをセットし、rm_activeReadersキューに繋いでいる。
わざわざIPIを使っている理由は、こうすることで、CPU毎にあるtrackerのリストの操作を(readerが)ロックを取らずに行なうことができる点にある。CPU毎のデータを必ず当該CPUでのみ操作するならば、ロックは不要である。
このアトミック性を実現するためには、IPIされる側つまりreaderは、リスト操作の途中でrm_cleanIPIが呼ばれないようにする必要がある。_rm_rlockにあったtd_critnest++が実はその役割を果たしている。この操作はわかりにくいがプリエンプションを抑制している。そしてrm_cleanIPIは割り込みスレッドで実行されるので、プリエンプションを抑制することでrm_cleanIPIが割り込んでこないことを保障できる。
なおsmp_rendezvous_cpusは同期IPIなので、対象CPUのすべてでrm_cleanIPIが実行された後、関数から戻ってくる。この段階で、すべてのCPU毎のキューにいたtrackerはrm_activeReadersに繋がっている。
続きのコードを再掲する。
561 mtx_lock_spin(&rm_spinlock);
562 while ((prio = LIST_FIRST(&rm->rm_activeReaders)) != NULL) {
563 ts = turnstile_trywait(&rm->lock_object);
564 prio->rmp_flags = RMPF_ONQUEUE | RMPF_SIGNAL;
565 mtx_unlock_spin(&rm_spinlock);
566 turnstile_wait(ts, prio->rmp_thread,
567 TS_EXCLUSIVE_QUEUE);
568 mtx_lock_spin(&rm_spinlock);
569 }
570 mtx_unlock_spin(&rm_spinlock);
571 }
572 }
561-570行目：これらすべてのreaderがrm_runlockを呼んでロックを解放するのを待っている。rm_activeReadersからreaderを一つ取り出し、RMPF_SIGNALフラグをtrackerのrmp_flagsに追加し、当該スレッドからの返事(前述の_rm_unlock_hardのturnstile_signalのこと)を待つ。これをすべてのreaderに対して繰り返す。O(n)の処理なので、アクティブなreader数が多ければそれに比例して処理時間が長くなる。
そして前述の通り、この処理を行っている間は新規readerは_rm_rlock_hardで待たされる。
rm_wunlock
rm_wunlockは内部ロックを解放するだけである。以上。
おわりに
FreeBSDのrmlockのソースコードを読んだ。細かい部分は飛ばして読んだが、ロジックの大筋は理解できたと思う。たしかに理想的な状況(read-mostly)では、readerの処理はかなり軽いしスケーラビリティも高そうである。その代わり、writerが増えるとあっという間に性能が低下しそうでもある。
次はちらっと登場したshared/exclusiveロック(sx(9))を読みたい。このロックプリミティブもrwlockと似たロックらしい。
-
置き換えるのが難しい場合もある。例えば、ロックを取った状態で関数を抜けるようなとき(オブジェクトを検索する関数だと、見つかったオブジェクトに対するロックを取った状態でオブジェクトを返す)、関数の呼び出し側で
trackerを用意して関数引数に渡す必要がある。 ↩ -
なぜアトミック命令を使っていないとスケールするかは、Is Parallel Programming Hard, And, If So, What Can You Do About It?を読むとわかります。 ↩
-
sleepしたい時はRM_SLEEPABLEフラグをつけてロックを初期化する。そうするとrmlock内部で使うロックがmutex(9)からsx(9)に変わる。 ↩
-
厳密にはwriterが
rm_wlockを呼んだ後の初回のrm_rlockでも条件式が偽になる。 ↩ -
readerになってからリストに繋げば良いようにも思えるが、競合状態を回避するために、先にリストに繋がなければならない。 ↩