はじめに

先日、SMRというLinux RCUに似た同期機構がOpenBSDにコミットされました。今回は、以前からOpenBSDに存在するSRPという同期機構について調べました。

SRPとは

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

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

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

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

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

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

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

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

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が用いられています。

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つの関数のコードを実際に見てみましょう。

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);
}

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の中身を見てみます。

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チェックと代入は事実上アトミックに実行される⁴

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

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

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関数の定義はこんな感じです。

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です。

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です。

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と似た機能を提供していますが、ハザードポインタという異なる手法で機能を実現している点が興味深いです。

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

ただしオブジェクト解放時に別スレッドから参照されるため、メモリバリアが必要なります。 ↩
参照はすぐに外され同時にたくさん参照を持つことはないので固定長になっているのだと思います。 ↩
rawソケットようにパケットの送信もできます。 ↩
プリエンプションをサポートするカーネルではプリエンプションを一時的に切る等の対応が必要になると思います。 ↩