OpenBSDカーネルの同期機構SRPについて調べた

# はじめに

先日、[SMR](https://qiita.com/ozaki-r/items/fed4cbc4990b88a82f6a)というLinux RCUに似た同期機構がOpenBSDにコミットされました。今回は、以前からOpenBSDに存在するSRPという同期機構について調べました。

# SRPとは

SRPはShared Reference Pointersの略です。SRPを使って作成したオブジェクトにロックなしで安全にアクセスしたり、オブジェクト参照中は解放されないことを保証したりする機能を提供します。2015年にリリースされたOpenBSD 5.8で登場した(SMRほどではないですが)比較的新しい同期機能です。

[コミットログ](https://github.com/openbsd/src/commit/52776b7dd171c092a35f86a9ed8bd1c22cac9fb8)には`internally srp is a twisted version of hazard pointers, which are a relative of RCU.`と書かれています。適当に訳すと、「内部的にはSRPはRCUの親戚にといえるハザードポインタのひねくれた実装である。」ぐらいでしょうか。

ハザードポインタについての詳しい説明は[Wikipedia](https://en.wikipedia.org/wiki/Hazard_pointer)や[kumagiさんのブログ記事](http://kumagi.hatenablog.com/entry/2013/01/08/232549)を読んでください(丸投げ)。RCUと同じく、ハザードポインタはロック等の同期を取らずオブジェクトを参照しているスレッドがいなくなったことを保障する機能を提供してくれます。RCUやSMRは、スレッドが切り替わったといった間接的な情報でオブジェクトを参照するスレッドがいなくなったことを保障しますが、ハザードポインタはもっと直接的にオブジェクトの参照そのものを管理することで同じことを保障します。

ハザードポインタは、スレッドローカルなリストを用意し、オブジェクトを参照している間は、そのオブジェクトを指すポインタをリスト内に保持します。オブジェクトを解放したいときは、すべてのリストにあるすべてのポインタを確認し、当該オブジェクトを指すポインタがないことを確認してからオブジェクトを解放します。スレッドローカルなリストは当該スレッドからのみ更新されるため、ロックを含むアトミック命令を用いた処理は不要です[^membar]。

[^membar]: ただしオブジェクト解放時に別スレッドから参照されるため、メモリバリアが必要なります。

SRPではスレッドローカルではなくCPU毎の配列にハザードポインタを持っています。配列は固定長でサイズは16[^16]です。オブジェクトの解放時には、CPU毎の配列をすべて調べて、オブジェクトへのハザードポインタが存在しないことを保障します。

[^16]: 参照はすぐに外され同時にたくさん参照を持つことはないので固定長になっているのだと思います。

# 使用例を見ながらSRPのコードを読む

SRPの使用例として、一番簡単なSRPの使い方をしているBPFを紹介します。BPFは指定したフィルタにマッチしたパケットをコピーしてユーザランドのプログラムに渡す機能です[^bpf]。フィルタはBPF仮想マシンで実行できるプログラムとして記述でき、BPFフィルタを使うときはプログラムをカーネルに渡します。

[^bpf]: rawソケットようにパケットの送信もできます。

bpf_d構造体はBPFを表すデータ構造です。そのメンバ変数である`bd_rfilter`にSRPが用いられています。

```c:BPFを表すデータ構造
/*
 * Descriptor associated with each open bpf file.
 */  
struct bpf_d {
        // 省略
        struct srp      bd_rfilter;     /* read filter code */
        // 省略
};
```

`struct srp`は`void *`のみを持つデータ構造で、ほぼ単なるポインタだと思って良いです。`bd_rfilter`はBPFプログラムへのポインタです。ロックを用いずBPFプログラムを削除したり更新したりするためにSRPが用いられています。

```c:BPFプログラムの参照
int
_bpf_mtap(caddr_t arg, const struct mbuf *m, u_int direction,
    void (*cpfn)(const void *, void *, size_t))
{
        // 省略

        struct srp_ref bsr;
        struct bpf_program *bf;
        struct bpf_insn *fcode = NULL;

        bf = srp_enter(&bsr, &d->bd_rfilter);
        if (bf != NULL) 
                fcode = bf->bf_insns; 
        slen = bpf_mfilter(fcode, m, pktlen);
        srp_leave(&bsr);

        // 省略         
}
```

`_bpf_mtap`関数はインタフェースがパケットを受信したときに呼ばれるコールバック関数です。ここでフィルタ(BPFプログラム)を実行し、フィルタにマッチした場合はパケットをユーザランドのプロセスに渡します。
見たとおりですが`srp_enter`でフィルタの参照を取り、`srp_leave`で参照を外します。`srp_ref`構造体は、`srp_enter`で参照に用いるハザードポインタへのポインタを入れておき、`srp_leave`でO(1)でハザードポインタにアクセスするためのものです。

以下で2つの関数のコードを実際に見てみましょう。

```c:srp_enter
void *
srp_enter(struct srp_ref *sr, struct srp *srp)
{
        struct cpu_info *ci = curcpu();
        struct srp_hazard *hzrd;
        u_int i;

        for (i = 0; i < nitems(ci->ci_srp_hazards); i++) {
                hzrd = &ci->ci_srp_hazards[i];
                if (hzrd->sh_p == NULL) {
                        sr->hz = hzrd;
                        return (srp_v(hzrd, srp));
                }
        }

        panic("%s: not enough srp hazard records", __func__);

        /* NOTREACHED */
        return (NULL);
}
```
```c:srp_leave
void
srp_leave(struct srp_ref *sr)
{
        sr->hz->sh_p = NULL;
}
```
`srp_enter`の処理内容は

- CPUコア毎のデータ構造である`cpu_info`にあるハザードポインタの配列から空いているスロットを探す
- `srp_ref`構造体にハザードポインタを入れる(`sr->hz = hzrd`)
- `srp_v`(後述)でハザードポインタから対象オブジェクト(`srp`構造体)への参照をつくる

`srp_leave`関数は`srp_ref`構造体を経由してハザードポインタをクリアします。`srp_ref`構造体の役割はこれだけです。

次に`srp_v`の中身を見てみます。

```c:srp_v
static inline void *
srp_v(struct srp_hazard *hzrd, struct srp *srp)
{
        void *v;

        hzrd->sh_p = srp;

        /*
         * ensure we update this cpu's hazard pointer to a value that's still
         * current after the store finishes, otherwise the gc task may already
         * be destroying it     
         */
        do {
                v = srp->ref;
                hzrd->sh_v = v;
                membar_consumer();
        } while (__predict_false(v != srp->ref));

        return (v);
}
```

何も気にせず`hzrd->sh_p = srp`していて、一見`srp_enter`でのNULLチェックとの間に競合状態があるように見えますが、おそらく以下の理由で問題ないのだと思います。

- もし割り込みが起きて割り込みハンドラが同じ`hzrd`を使ったとしても、割り込みハンドラは必ず最後まで実行し終わってから戻ってくるので、`hzrd`は返却されている(NULLになっている)
- OpenBSDはカーネルコンテキストでのプリエンプションをサポートしておらず、途中で他のコンテキスト(カーネルスレッド等)に切り替わらないので、NULLチェックと代入は事実上アトミックに実行される[^racy]

[^racy]: プリエンプションをサポートするカーネルではプリエンプションを一時的に切る等の対応が必要になると思います。

whileループは`srp_v`を抜けるときは確実に`hzrd->sh_v == srp->ref`になっていることを保証するための処理です。(メモリバリアについてはこの記事では詳しい解説をしません。)

次はフィルタオブジェクトの変更や解放について見ていきましょう。フィルタオブジェクトの置き換えは`bpf_setf`で行われます。

```c:BPFフィルタの設定
int
bpf_setf(struct bpf_d *d, struct bpf_program *fp, int wf)
{
        // 省略

        KERNEL_ASSERT_LOCKED();
        filter = wf ? &d->bd_wfilter : &d->bd_rfilter;

        // 省略

        if (fp->bf_insns == 0) {
                if (fp->bf_len != 0)
                        return (EINVAL);
                // 設定されたフィルタを削除する
                srp_update_locked(&bpf_insn_gc, filter, NULL);

        // 省略

        bf = malloc(sizeof(*bf), M_DEVBUF, M_WAITOK);
        bf->bf_len = flen;
        bf->bf_insns = fcode;

        // 新しいフィルタを設定する
        srp_update_locked(&bpf_insn_gc, filter, bf);

        // 省略
}
```

`srp_update_locked`関数でフィルタオブジェクトの置き換え、つまり`bd_rfilter`の参照先の変更が行われます。

第1引数の`bpf_insn_gc`は、オブジェクト開放時に呼ばれるデストラクタだと思ってください。(実際、最終的に`free`関数が呼ばれます。)

`srp_update_locked`関数の定義はこんな感じです。

```c:srp_udpate_locked
void
srp_update_locked(struct srp_gc *srp_gc, struct srp *srp, void *v)
{
        if (v != NULL)
                refcnt_take(&srp_gc->srp_gc_refcnt);

        v = srp_swap_locked(srp, v);

        if (v != NULL)
                srp_v_gc_start(srp_gc, srp, v);
}
```

`srp_swap_locked`は`srp->ref`に`v`は設定し、古い`srp->ref`を返すだけです。

次は`srp_v_gc_start`です。

```c:srp_v_gc_start
void
srp_v_gc_start(struct srp_gc *srp_gc, struct srp *srp, void *v)
{
        struct srp_gc_ctx *ctx;

        if (!srp_v_referenced(srp, v)) {
                /* we win */
                srp_v_dtor(srp_gc, v);
                return;
        }

        /* in use, try later */

        ctx = pool_get(&srp_gc_ctx_pool, PR_WAITOK);
        ctx->srp_gc = srp_gc;
        ctx->hzrd.sh_p = srp;
        ctx->hzrd.sh_v = v;

        timeout_set(&ctx->tick, srp_v_gc, ctx);
        timeout_add(&ctx->tick, 1);
}
```

大雑把に説明すると、オブジェクトを参照してるスレッドがいなければすぐに`srp_v_dtor`を呼ぶ。そうでなければ、1チックつまりタイマ割り込みの間隔1回分の時間だけ待って、同じことを繰り返します。

そして最後に`srp_v_referenced`です。

```c:srp_v_referenced
int
srp_v_referenced(struct srp *srp, void *v)
{       
        struct cpu_info *ci;
        CPU_INFO_ITERATOR cii;
        u_int i;
        struct srp_hazard *hzrd;

        CPU_INFO_FOREACH(cii, ci) {
                for (i = 0; i < nitems(ci->ci_srp_hazards); i++) {
                        hzrd = &ci->ci_srp_hazards[i];

                        if (hzrd->sh_p != srp)
                                continue;
                        membar_consumer();
                        if (hzrd->sh_v != v)
                                continue;

                        return (1);
                }
        }

        return (0);
}
```

`srp_v_referenced`はSRPのキモとなる参照している人を探す処理です。前述した通り、全CPUのハザードポインタを走査し、対象となるオブジェクトを指すハザードポインタがあるかどうか調べているのがわかります。CPU数が増えると全部のハザードポインタをチェックするコストが無視できなくなりそうですね。

# おわりに

OpenBSDカーネルの比較的新しい同期機構であるSRPについて解説してみました。Linux RCUと似た機能を提供していますが、ハザードポインタという異なる手法で機能を実現している点が興味深いです。

この記事ではメモリバリアの説明をしなかったですが、いずれちゃんと理解して説明できたら良いなと思います。