FreeBSDのread-mostlyロックのソースコードを読んでみた

# はじめに

FreeBSDには、read-mostlyロック([rmlock(9)](https://www.freebsd.org/cgi/man.cgi?query=rmlock&apropos=0&sektion=9&manpath=FreeBSD+11.0-RELEASE&arch=default&format=html))という、reader/writerロック([rwlock(9)](https://www.freebsd.org/cgi/man.cgi?query=rwlock&apropos=0&sektion=9&manpath=FreeBSD+11.0-RELEASE&arch=default&format=html))に似たロックプリミティブがある。ロック利用者のほとんどがreaderの場合、rwlockに比べてreaderのスケーラビリティが高い。

本エントリでは、そのrmlockの実装をざっと読んでみる。対象のソースコードはFreeBSD 11相当である。

# rmlockの特徴

- rwlockとほぼ同じセマンティクスで使える
    - rwlockと異なりロック・アンロックAPIに`tracker`と呼ばれるローカル変数を追加で渡すように修正が必要
    - rwlockをrmlockに置き換えるのは比較的容易[^semantics]
- rwlockに比べて、reader数（≒CPU数）に対してスケーラブル
    - readerのfast pathではアトミック命令を使っていない[^atomic]
- writerが重い
    - readerがいなくなるのを待ち合わせる処理が重い
    - writerが待っている間は、新規readerも待たされるので、引きずられてreaderも長く待たされる可能性がある
- rmlockを持ったままblock/sleepしても良い[^sleepable]

[^semantics]: 置き換えるのが難しい場合もある。例えば、ロックを取った状態で関数を抜けるようなとき(オブジェクトを検索する関数だと、見つかったオブジェクトに対するロックを取った状態でオブジェクトを返す)、関数の呼び出し側で`tracker`を用意して関数引数に渡す必要がある。

[^atomic]: なぜアトミック命令を使っていないとスケールするかは、[Is Parallel Programming Hard, And, If So, What Can You Do About It?](https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html)を読むとわかります。

[^sleepable]: sleepしたい時はRM_SLEEPABLEフラグをつけてロックを初期化する。そうするとrmlock内部で使うロックが[mutex(9)](https://www.freebsd.org/cgi/man.cgi?query=mutex&apropos=0&sektion=9&manpath=FreeBSD+11.0-RELEASE&arch=default&format=html)から[sx(9)](https://www.freebsd.org/cgi/man.cgi?query=sx&apropos=0&sektion=9&manpath=FreeBSD+11.0-RELEASE&arch=default&format=html)に変わる。

# readerの動作
`rm_rlock`、`rm_runlock`のコードを読む。双方とも、writerがいなければ軽い処理(fast path)のみで終了し、writerがいるとさらに重い処理(slow path)を実行することになる。
## rm_rlock
### Fast path

`rm_rlock`がreaderロック取得APIであるが、内部実装では、[`_rm_rlock`](http://fxr.watson.org/fxr/source/kern/kern_rmlock.c?v=FREEBSD11#L427)がメインの関数である。短いので全部載せる。

```c
  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がロックを取得しているか、もしくは取得しようとしているかどうかを判断している[^slowpath]。

[^slowpath]: 厳密にはwriterが`rm_wlock`を呼んだ後の初回の`rm_rlock`でも条件式が偽になる。

条件式にある`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`](http://fxr.watson.org/fxr/source/kern/kern_rmlock.c?v=FREEBSD11#L346)である。

前半は例外的な処理が多いので省略する。1点だけ書くと、`rm_tracker_remove`でCPU毎のリストから一旦`tracker`を外している。これは、まだ正式にreaderになっていないためである[^list]。リストへはslow pathの最後に繋ぎ直す。

[^list]: readerになってからリストに繋げば良いようにも思えるが、競合状態を回避するために、先にリストに繋がなければならない。

以下に後半の必要なコードのみ掲載する。

```c
  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`を外し、以下の条件式を満たすならばすぐに関数から抜ける。

```c
  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のコードである。これも短いため、すべて掲載する。

```c
  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`である。意外と短いため、すべて載せる。

```c
  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`](http://fxr.watson.org/fxr/source/kern/kern_rmlock.c?v=FREEBSD11#L255)もコードが短いの全部載せる。

```c
  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`に繋がっている。

続きのコードを再掲する。

```c
  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)](https://www.freebsd.org/cgi/man.cgi?query=sx&apropos=0&sektion=9&manpath=FreeBSD+11.0-RELEASE&arch=default&format=html))を読みたい。このロックプリミティブもrwlockと似たロックらしい。