eBPFって何だろう

eBPFには前々から興味があったので、ちょっと調べてみた。資料はいろいろある。日本語だと（会員登録が必要なので最後まで読めないが）「Berkeley Packet Filter入門」が詳しい。英語でよければ「BPF: Linux kernel code execution engine」とか。

eBPF以前

オリジナルのBPF (Berkeley Packet Filter)が登場したのは90年代初頭で、tcpdumpに組み込まれているので知らずにお世話になっている人も多いかと。論文（「The BSD Packet Filter: A New Architecture for User-level Packet Capture」[USENIX93]）が出版されたのが1993年で、著者の一人はEDTモデルでも言及したVan Jacobson先生。

tcpdumpやwiresharkのようなツールはユーザ空間で動作するけど、すべてのパケットをカーネル空間からコピーするとオーバヘッドが大きいので大変。ということで不要なパケットはカーネル空間でフィルタリングして、欲しいパケット、例えば「ホストfooから来たICMPパケットのみ」をユーザ空間に持ってきたくなる。しかし、あらかじめフィルタリングのルールをカーネルに埋め込んでおくのは、組合せのパターンが多すぎて不可能。そこで簡単なパケットフィルタリング用の簡単な仮想マシンをカーネル空間で動かそうというのが、基本的なアイデアである。ちなみにちょっと脱線すると、仮想マシンにはシステム仮想マシンとプロセス仮想マシンがあって、KVMは前者、BPFやJavaVMは後者に分類される。

ただし、カーネル内仮想マシンとしてパケットフィルタを最初に実装したのがBPFというわけではなく、Jeffrey MogulやRichard Rashidが80年代にCSPFを4.3BSD UNIX上に実装している（「The Packet Filter: An Efficient Mechanism for User-level Network Code」[SOSP87]）。CSPFはスタックマシンだったが、BPFはレジスタマシンにすることで、当時増えてきたRISCマシンで高速に動作するように再設計された。その後も新しいパケットフィルタはいろいろ実装されているが、ここでは割愛する。

なお、Linuxではバージョン2.2の頃からLSF (Linux Socket Filter)という仕組みでほぼBPFと同等なことを実現している。BFP言語自体は互換性があるが、実装がまったく異なっている。BSDでは/dev/bpfというキャラクタデバイスを使っていたが、これに対して、LSFではソケットオプションを使って、フィルタを制御する。

また、パケットフィルタというと、Netfilterという仕組みがある。これはプロトコルスタックの各所（入力、転送、出力等）に設けられたフックポイントに設定した処理を実行するものである。iptables（バージョン3.13からnftablesがサポートされたが、バージョン2.2のipchainsのように置き換わっていくのかな。）を使うことでNetfilterの挙動を制御できる。レイヤでいうとNetfilterはまさにプロトコルスタック内の仕組みだが、BPFはプロトコルスタックとネットワークドライバの境界に位置する仕組みになる。nftables周りもそのうち調べてみよう。

BPF仮想マシン

BPF仮想マシンは前述したようなレジスタマシンで、レジスタにはアキュムレータとインデックスレジスタ（共に32ビット幅）があり、さらに16個の32ビットスクラッチメモリストアを持つ。eBPFは仮想マシンの仕様も拡張されているが、ここでは割愛する。

tcpdumpを使えば、フィルタリングルールがどのようにBPF命令に変換されるかわかる。

$ sudo tcpdump -d -i en0 'ip and tcp'
(000) ldh      [12]
(001) jeq      #0x800           jt 2	jf 5
(002) ldb      [23]
(003) jeq      #0x6             jt 4	jf 5
(004) ret      #262144
(005) ret      #0

ldh命令でパケットの12バイト目からハーフワード（16ビット）ロードする。ここはちょうどEtherTypeフィールドなので、IP（v4）パケットであれば、0x800が格納されている。BPFの条件分岐命令には条件が成立した場合のラベルと、不成立した場合のラベルを指定する。なお、一般的な命令セットアーキテクチャの分岐命令だと、不成立した場合はfall throughされるので、ちょっと特徴的。また、ループできない制限もある。IPパケットの場合はさらにパケットの23バイト目をロードして、TCPかチェックする。最終的に'ip and tcp'が成立した場合は、004行目で262144 (0x40000)を返して終了。不成立の場合は005行目で0を返して終了になる。パケットフィルタとして使う場合は、戻り値は許可するバイト数となる。したがって0はドロップを、十分大きな値はパスを意味する。

eBPFの登場

近年、BPFはパケットフィルタリング以外にも、トレーシング・モニタリングやシステムコールフィルタリング（seccomp）など応用が広がってきた。このようにカーネル内仮想マシンの需要は結構あるもので、BPFの限界も見えてきたので、拡張しましたというのがeBPF (Extended BPF)になる。なお比較のため、元々あったBPF実装はcBPF (Classic BPF)と呼ばれている。

commit bd4cf0ed331a275e9bf5a49e6d0fd55dffc551b8
Author: Alexei Starovoitov <ast@kernel.org>
Date:   Fri Mar 28 18:58:25 2014 +0100

   net: filter: rework/optimize internal BPF interpreter's instruction set

   This patch replaces/reworks the kernel-internal BPF interpreter with
   an optimized BPF instruction set format that is modelled closer to
   mimic native instruction sets and is designed to be JITed with one to
   one mapping. Thus, the new interpreter is noticeably faster than the
   current implementation of sk_run_filter(); mainly for two reasons:

これがeBPFのオリジナルパッチだろうか。この頃はInternal BPFと呼ばれていてcBPFのバックエンドとしてのみ使われていた。JITコンパイルとの相性が悪いからネイティブの命令セットに近づけたとある。マイクロベンチマークでの評価では、x86-64マシンで1.5〜4倍の性能向上した。

commit daedfb22451dd02b35c0549566cbb7cc06bdd53b
Author: Alexei Starovoitov <ast@kernel.org>
Date:   Thu Sep 4 22:17:18 2014 -0700

   net: filter: split filter.h and expose eBPF to user space

そして約半年後にユーザ空間から直接利用できるようになった。

主要なソースコードはこんなところか。
・kernel/bpf　BPFコア部分
・net/core/filter.c　cBPFコア部分
・tools/bpf　BPF関連のツール群
・samples/bpf　BPF関連のサンプルコード

ということで、本日はeBPFの導入まで。