BPF for lightweight tunnel infrastructureについて調べてみた

# はじめに

このエントリは[Linux Advent Calendar 2016](http://qiita.com/advent-calendar/2016/linux)の5日目の記事として書かれました。

[bpf: BPF for lightweight tunnel infrastructure](https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/commit/?id=3a0af8fd61f90920f6fa04e4f1e9a6a73c1b4fd2)という機能が最近net-nextにマージされました(つまり特に問題なければ4.10でマージされる予定)。トンネルにどうBPFが使われているのか興味があったので調べてみました。

関係するコミットは以下の3つです。

- [bpf: BPF for lightweight tunnel infrastructure](https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/commit/?id=3a0af8fd61f90920f6fa04e4f1e9a6a73c1b4fd2)
- [bpf: Add tests and samples for LWT\-BPF](https://git.kernel.org/cgit/linux/kernel/git/davem/net-next.git/commit/?id=f74599f7c5309b21151233b98139e9b723fd1110)
- [Lightweight & flow based encapsulation](http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=e69724f32e62502a6e686eae36b7aadfeea60dca)

#背景知識
まずBPFとlightweight tunnel infrastructure (lwtunnel)について調べました。

## BPFについて
BPFについては [LinuxのBPF : \(1\) パケットフィルタ \- 睡分不足](http://mmi.hatenablog.com/entry/2016/08/01/031233) が分かりやすいので、詳しくはそちらを参照してください。

伝統的な*BSDのBPFは、カーネル内でパケットを高速にフィルタリングしてユーザに渡す(tcpdumpが分かりやすい例だと思います)のが基本的な機能です[^bpf_tx]。

[^bpf_tx]: 実はパケット(L2フレーム)を送信する機能も存在しますが、ここではあまり重要ではないです。

Linuxに実装されているのは、伝統的なBPFを拡張したeBPFです。拡張箇所については[EBPF and Linux Networking](http://www.slideshare.net/PLUMgrid/ebpf-and-linux-networking)の21ページ目のスライドが詳しいです。大きな違いの一つはパケットに対するstore機能が追加されていること、つまりパケットを書き換えることが可能であることだと思います。BPF for lightweight tunnel infrastructureでもこの機能が使われています。

## Lightweight tunnel infrastructureについて
Lightweight tunnel infrastructure(lwtunnel)は、各種トンネル(カプセル化)技術の共通フレームワークです。つまり、X over YのYの方を共通化するものです[^Xover]。[Lightweight & flow based encapsulation](http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=e69724f32e62502a6e686eae36b7aadfeea60dca)というコミットでマージされました。

[^Xover]: XにIPv4/IPv6以外を使えるかはよくわかってないです。

net-nextでは以下のカプセル化機能がlwtunnelベースになっています[^lwtunnel_support]。

[^lwtunnel_support]: GREやVXLANもそのうちlwtunnelベースになるようです。

- MPLS
- Identifier Locator Addressing (ILA)
- IPv6 Segment routing (SEG6)
- BPF

ここにBPFが現れました。どうやらカプセル化自体をBPFにやらせるというもののようです。

#サンプルプログラムを動かしてみる

いきなりソースコードを読んでもよくわからないので、とりあえずは`linux/samples/bpf`以下にある、`test_lwt_bpf.sh`というサンプルプログラム(というよりテスト)を動かしてみます。

##準備
###カーネル
net-nextレポジトリ[^net-next]の最新版のカーネルをインストールします。

[^net-next]: git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next.git

カーネルコンフィグは以下のコンフィグが有効になっていれば大丈夫だと思います。

```
CONFIG_BPF=y
CONFIG_BPF_SYSCALL=y
CONFIG_LWTUNNEL=y
CONFIG_LWTUNNEL_BPF=y
```

###iproute2

サンプルを動かすには`ip route`の`encap bpf`というオプションが必要です。これはまだiproute2本家のレポジトリには入っておらず、Thomas Grafさんのiproute2レポジトリの[bpf-lwtブランチ](https://github.com/tgraf/iproute2/tree/bpf-lwt)を使う必要があります。

###その他のパッケージ
サンプルを動かすために以下のパッケージを追加でインストールしました。(Fedora 24の場合です。)

- dnf install clang
- dnf install llvm
- dnf install glibc-devel.i686
- dnf install https://copr-be.cloud.fedoraproject.org/results/caoli5288/netperf/fedora-24-x86_64/00438225-netperf/

###サンプルプログラムのビルド
Linuxソースコードのトップディレクトリで以下を実行します。カーネルヘッダのインストールはBPFプログラムのビルドに必要でした。

```
make headers_install
make samples/bpf/  # 最後の'/'は必要です
```

##サンプルプログラムの実行
サンプルプログラムは実行中にBPFプログラムをビルドするのですが、それに必要なヘッダファイルのパスがずれていたので以下のパッチを当てる必要がありました。(これが正しい対応かどうかはわかりません。)

```diff
diff --git a/samples/bpf/test_lwt_bpf.sh b/samples/bpf/test_lwt_bpf.sh
index a695ae2..7f75bfb 100644
--- a/samples/bpf/test_lwt_bpf.sh
+++ b/samples/bpf/test_lwt_bpf.sh
@@ -371,28 +371,28 @@ DST_MAC=$(lookup_mac $VETH1 $NS1)
 SRC_MAC=$(lookup_mac $VETH0)
 DST_IFINDEX=$(cat /sys/class/net/$VETH0/ifindex)
 
-CLANG_OPTS="-O2 -target bpf -I ../include/"
+CLANG_OPTS="-O2 -target bpf -I ../../usr/include/"
 CLANG_OPTS+=" -DSRC_MAC=$SRC_MAC -DDST_MAC=$DST_MAC -DDST_IFINDEX=$DST_IFINDEX"
 clang $CLANG_OPTS -c test_lwt_bpf.c -o test_lwt_bpf.o
```

##実行結果
今回は`test_push_ll_and_redirect`と`test_no_l2_and_redirect`というテストだけを実行したいので、その他のテストはコメントアウトしました[^fail]。

[^fail]: 実際のところ、途中で他のテストが止まってしまったので、仕方なくコメントアウトして実行しました。

実行すると以下のような出力が得られます。

```shell-session
$ sudo sh test_lwt_bpf.sh
+ setup_one_veth lwt_ns1 tst_lwt1a tst_lwt1b 192.168.254.1 192.168.254.2 192.168.254.3
+ ip netns add lwt_ns1
+ ip link add tst_lwt1a type veth peer name tst_lwt1b
+ ip link set dev tst_lwt1a up
+ ip addr add 192.168.254.1/24 dev tst_lwt1a
+ ip link set tst_lwt1b netns lwt_ns1
+ ip netns exec lwt_ns1 ip link set dev tst_lwt1b up
+ ip netns exec lwt_ns1 ip addr add 192.168.254.2/24 dev tst_lwt1b
+ '[' 192.168.254.3 ']'
+ ip netns exec lwt_ns1 ip addr add 192.168.254.3/32 dev tst_lwt1b
+ setup_one_veth lwt_ns2 tst_lwt2a tst_lwt2b 192.168.111.1 192.168.111.2
+ ip netns add lwt_ns2
+ ip link add tst_lwt2a type veth peer name tst_lwt2b
+ ip link set dev tst_lwt2a up
+ ip addr add 192.168.111.1/24 dev tst_lwt2a
+ ip link set tst_lwt2b netns lwt_ns2
+ ip netns exec lwt_ns2 ip link set dev tst_lwt2b up
+ ip netns exec lwt_ns2 ip addr add 192.168.111.2/24 dev tst_lwt2b
+ '[' '' ']'
+ ip netns exec lwt_ns1 netserver
Starting netserver with host 'IN(6)ADDR_ANY' port '12865' and family AF_UNSPEC
+ echo 1
++ lookup_mac tst_lwt1b lwt_ns1
++ set +x
+ DST_MAC=0x8fd429f47b96
++ lookup_mac tst_lwt1a
++ set +x
+ SRC_MAC=0xa170b08dfcd2
++ cat /sys/class/net/tst_lwt1a/ifindex
+ DST_IFINDEX=64
+ CLANG_OPTS='-O2 -target bpf -I ../../usr/include/'
+ CLANG_OPTS+=' -DSRC_MAC=0xa170b08dfcd2 -DDST_MAC=0x8fd429f47b96 -DDST_IFINDEX=64'
+ clang -O2 -target bpf -I ../../usr/include/ -DSRC_MAC=0xa170b08dfcd2 -DDST_MAC=0x8fd429f47b96 -DDST_IFINDEX=64 -c test_lwt_bpf.c -
o test_lwt_bpf.o
+ test_push_ll_and_redirect
+ test_start 'test_push_ll_and_redirect on lwt xmit'
+ set +x
----------------------------------------------------------------                                                           [12/1931]
Starting test: test_push_ll_and_redirect on lwt xmit
----------------------------------------------------------------
+ install_test xmit push_ll_and_redirect
+ cleanup_routes
+ ip route del 192.168.254.2/32 dev tst_lwt1a
+ true
+ ip route del table local local 192.168.99.1/32 dev lo
+ true
+ cp /dev/null /sys/kernel/debug/tracing/trace
+ OPTS='encap bpf headroom 14 xmit obj test_lwt_bpf.o section push_ll_and_redirect '
+ '[' xmit == in ']'
+ ip route add 192.168.254.2/32 encap bpf headroom 14 xmit obj test_lwt_bpf.o section push_ll_and_redirect dev tst_lwt1a
+ ping -c 3 192.168.254.2
PING 192.168.254.2 (192.168.254.2) 56(84) bytes of data.
64 bytes from 192.168.254.2: icmp_seq=1 ttl=64 time=0.123 ms
64 bytes from 192.168.254.2: icmp_seq=2 ttl=64 time=0.101 ms
64 bytes from 192.168.254.2: icmp_seq=3 ttl=64 time=0.070 ms

--- 192.168.254.2 ping statistics ---
3 packets transmitted, 3 received, 0% packet loss, time 2051ms
rtt min/avg/max/mdev = 0.070/0.098/0.123/0.021 ms
++ get_trace
++ set +x
+ match_trace '            ping-12817 [000] ....  2906.088681: : redirected to 64
            ping-12817 [000] ....  2907.114058: : redirected to 64
            ping-12817 [000] ....  2908.139829: : redirected to 64' '
redirected to 64
redirected to 64
redirected to 64'
+ set +x
+ return 0
+ remove_prog xmit
+ '[' xmit == in ']'
+ ip route del 192.168.254.2/32 dev tst_lwt1a
+ cleanup
+ set +ex
+ echo 0
+ exit 0
----------------------------------------------------------------                                                           [12/1817]
Starting test: test_no_l2_and_redirect on lwt xmit
----------------------------------------------------------------
+ install_test xmit fill_garbage_and_redirect
+ cleanup_routes
+ ip route del 192.168.254.2/32 dev tst_lwt1a
+ true
+ ip route del table local local 192.168.99.1/32 dev lo
+ true
+ cp /dev/null /sys/kernel/debug/tracing/trace
+ OPTS='encap bpf headroom 14 xmit obj test_lwt_bpf.o section fill_garbage_and_redirect '
+ '[' xmit == in ']'
+ ip route add 192.168.254.2/32 encap bpf headroom 14 xmit obj test_lwt_bpf.o section fill_garbage_and_redirect dev tst_lwt1a
+ ping -c 3 192.168.254.2
PING 192.168.254.2 (192.168.254.2) 56(84) bytes of data.
ping: sendmsg: Numerical result out of range
ping: sendmsg: Numerical result out of range
ping: sendmsg: Numerical result out of range

--- 192.168.254.2 ping statistics ---
3 packets transmitted, 0 received, 100% packet loss, time 2031ms

++ get_trace
++ set +x
+ match_trace '            ping-14391 [000] ....  6044.873789: : redirected to 104
            ping-14391 [000] ....  6045.879477: : redirected to 104
            ping-14391 [000] ....  6046.905686: : redirected to 104' '
+ set +x
+ return 0
+ remove_prog xmit
+ '[' xmit == in ']'
+ ip route del 192.168.254.2/32 dev tst_lwt1a
+ cleanup
+ set +ex
+ echo 0
+ exit 0
```

いろいろ出力していますが、やっていることは以下の通りです。

- vethペアを作って、ピアのvethをnetnsに入れて、両方のvethにIPを振る
- ピアのvethのIPを宛先とする経路を設定する
    - その際に`encap bpf headroom 14 xmit obj test_lwt_bpf.o section push_ll_and_redirect`をオプションに指定する
    - これにより、カプセル化する際にBPFプログラムを呼び出す
    - BPFプログラムではL3ヘッダの外側にL2ヘッダを付ける(もしくはゴミを付ける)
- ping <ピアのIP>が成功する/失敗することを確認する

つまり、このサンプルプログラムでは、カプセル化してるといってもL3パケットにL2(Ethernet)ヘッダを付けているだけです。

なおL2ヘッダに必要な情報(送信元/先MACアドレス)はBPFプログラムをビルドする際に渡しています(`clang`の行を参照)。またBPFでパケットを転送するために必要なインタフェース番号もこのときに渡しています。

`test_push_ll_and_redirect`では正しいL2ヘッダを付けているのでpingが成功し、`test_no_l2_and_redirect`ではゴミを付けているのでpingが失敗しています。

#ソースコードを読んでみる

##サンプルプログラムを読む

上記サンプルプログラムで利用されるBPFプログラムを読んでみます。当該コードは以下の通りです。

```c:samples/bpf/test_lwt_bpf.c
static inline int __do_push_ll_and_redirect(struct __sk_buff *skb)
{
        uint64_t smac = SRC_MAC, dmac = DST_MAC;
        int ret, ifindex = DST_IFINDEX;
        struct ethhdr ehdr;

        ret = bpf_skb_change_head(skb, 14, 0);
        if (ret < 0) {
                printk("skb_change_head() failed: %d\n", ret);
        }

        ehdr.h_proto = __constant_htons(ETH_P_IP);
        memcpy(&ehdr.h_source, &smac, 6);
        memcpy(&ehdr.h_dest, &dmac, 6);

        ret = bpf_skb_store_bytes(skb, 0, &ehdr, sizeof(ehdr), 0);
        if (ret < 0) {
                printk("skb_store_bytes() failed: %d\n", ret);
                return BPF_DROP;
        }

        return bpf_redirect(ifindex, 0);
}

SEC("push_ll_and_redirect")
int do_push_ll_and_redirect(struct __sk_buff *skb)
{
        int ret, ifindex = DST_IFINDEX;
        
        ret = __do_push_ll_and_redirect(skb);
        if (ret >= 0)
                printk("redirected to %d\n", ifindex);
        
        return ret;
}
```

カプセル化処理で最初に呼ばれるのは、`ip route`コマンドで指定された`push_ll_and_redirect`のアノテーションがある、`do_push_ll_and_redirect`です。実処理はそこから呼ばれる`__do_push_ll_and_redirect`にあります。

```c
        ret = bpf_skb_change_head(skb, 14, 0);
```

skbのヘッダの位置をL2ヘッダ分ずらしています。

```c
        ehdr.h_proto = __constant_htons(ETH_P_IP);
        memcpy(&ehdr.h_source, &smac, 6);
        memcpy(&ehdr.h_dest, &dmac, 6);
```

L2ヘッダを用意しています。前述の通り必要な情報はビルド時に与えられています。(`SRC_MAC`と`DST_MAC`)。

```c
        ret = bpf_skb_store_bytes(skb, 0, &ehdr, sizeof(ehdr), 0);
```

用意したL2ヘッダをskbにコピーしています。

```
        return bpf_redirect(ifindex, 0);
```

最後に`bpf_redirect`を呼んでいます。引数にはビルド時に指定されたインタフェースを渡しています。

これだけ見てもわかりませんでしたが、どうやら`bpf_redirect`で指定したインタフェースからパケットを送出しているようです。次はカーネルのその辺りを部分を読んでいきます。

##カーネルのソースコードを読む

とりあえずいろいろ前提を飛ばして、前述のサンプルプログラムでBPFプログラムが呼ばれていそうな箇所を見ていきます。コミットを見た感じ`net/core/lwt_bpf.c`の`bpf_xmit`がそれっぽいので見てみます[^bpf_xmit]。

[^bpf_xmit]: 最初`bpf_output`だと勘違いして、かなり回り道をしました...

```c:net/core/lwt_bpf.c
static int bpf_xmit(struct sk_buff *skb)
{
        struct dst_entry *dst = skb_dst(skb);
        struct bpf_lwt *bpf;

        bpf = bpf_lwt_lwtunnel(dst->lwtstate);
        if (bpf->xmit.prog) {
                int ret;

                ret = run_lwt_bpf(skb, &bpf->xmit, dst, CAN_REDIRECT);
                switch (ret) {
                case BPF_OK:
                        /* If the header was expanded, headroom might be too
                         * small for L2 header to come, expand as needed.
                         */
                        ret = xmit_check_hhlen(skb);
                        if (unlikely(ret))
                                return ret;

                        return LWTUNNEL_XMIT_CONTINUE;
                case BPF_REDIRECT:
                        return LWTUNNEL_XMIT_DONE;
                default:
                        return ret;
                }
        }

        return LWTUNNEL_XMIT_CONTINUE;
}
```

おそらく`run_lwt_bpf`でBPFを実行してるのだと思います。

```
static int run_lwt_bpf(struct sk_buff *skb, struct bpf_lwt_prog *lwt,
                       struct dst_entry *dst, bool can_redirect)
{
        int ret;

        /* Preempt disable is needed to protect per-cpu redirect_info between
         * BPF prog and skb_do_redirect(). The call_rcu in bpf_prog_put() and
         * access to maps strictly require a rcu_read_lock() for protection,
         * mixing with BH RCU lock doesn't work.
         */
        preempt_disable();
        rcu_read_lock();
        bpf_compute_data_end(skb);
        ret = bpf_prog_run_save_cb(lwt->prog, skb);
        rcu_read_unlock();

        switch (ret) {
        case BPF_OK:
                break;

        case BPF_REDIRECT:
                if (unlikely(!can_redirect)) {
                        pr_warn_once("Illegal redirect return code in prog %s\n",
                                     lwt->name ? : "<unknown>");
                        ret = BPF_OK;
                } else {
                        ret = skb_do_redirect(skb);
                        if (ret == 0)
                                ret = BPF_REDIRECT;
                }
                break;

        case BPF_DROP:
                kfree_skb(skb);
                ret = -EPERM;
                break;

        default:
                pr_warn_once("bpf-lwt: Illegal return value %u, expect packet loss\n", ret);
                kfree_skb(skb);
                ret = -EINVAL;
                break;
        }

        preempt_enable();

        return ret;
}
```

`bpf_prog_run_save_cb`がBPFプログラムを実行していそうです。

普通なら`ret`が`BPF_OK` (== 0)が返ってきて、`return ret`するのだと思いますが、今回はBPFプログラムが最後に`bpf_redirect`を呼んでいるので`BPF_OK`ではなく、`BPF_REDIRECT`を返してるかもしれません。ちょっと確認してみると、`net/core/filter.c`にありました。

```c:net/core/filter.c
BPF_CALL_2(bpf_redirect, u32, ifindex, u64, flags)
{
        struct redirect_info *ri = this_cpu_ptr(&redirect_info);

        if (unlikely(flags & ~(BPF_F_INGRESS)))
                return TC_ACT_SHOT;

        ri->ifindex = ifindex;
        ri->flags = flags;

        return TC_ACT_REDIRECT;
}
```

返してるものが`TC_ACT_REDIRECT`ですが、どうもこれは`BPF_REDIRECT`と読み替えても良さそうです。

```c:include/uapi/linux/bpf.h
/* Generic BPF return codes which all BPF program types may support.
 * The values are binary compatible with their TC_ACT_* counter-part to
 * provide backwards compatibility with existing SCHED_CLS and SCHED_ACT
 * programs.
 *      
 * XDP is handled seprately, see XDP_*.
 */     
enum bpf_ret_code {
        BPF_OK = 0,
        /* 1 reserved */
        BPF_DROP = 2, 
        /* 3-6 reserved */
        BPF_REDIRECT = 7,
        /* >127 are reserved for prog type specific return codes */
};
```

というわけで、どうやら`skb_do_redirect`が呼ばれそうです。ここから`__bpf_redirect`、`__bpf_redirect_common`、`__bpf_tx_skb`ときて最後に`dev_queue_xmit`が呼ばれていました。これはデバイス(今回はveth)のデータ送信関数に繋がります(みなさんご存知`ndo_start_xmit`)。

呼び出し元の`bpf_xmit`では`BPF_REDIRECT`のときは`return LWTUNNEL_XMIT_DONE`して処理を終了しています。パケットはすでに送信済みなので動作としては正しそうです。

`bpf_xmit`を呼んでるのは`lwtunnel_xmit`だと思いますが、`lwtunnel_xmit`はどこで呼ばれているのでしょうか？探してみると`ip_finish_output2`にありました。これは今回のようにIPパケットをカプセル化してるのであれば、呼び出し位置としては妥当です。

```c:net/ipv4/ip_output.c
        if (lwtunnel_xmit_redirect(dst->lwtstate)) {
                int res = lwtunnel_xmit(skb);

                if (res < 0 || res == LWTUNNEL_XMIT_DONE)
                        return res;
        }
```

`LWTUNNEL_XMIT_DONE`が返ってきた場合は、それ以上を処理を行なわずreturnしています。正しそうです。

#おわりに

BPF for lightweight tunnel infrastructureに調べてみました。

この機能を使うとカプセル化そのものをBPFでプログラムすることできます。カーネルモジュールでも同じようなことはできると思いますが、それよりは簡単にカプセル化機能を追加できると思います。

BPFは色々な使われ方をしていて面白いです。今後もさらに増えていくと思うので楽しみですね。