はじめに（注意）

ちょうど一年ぐらい前にLinuxのBPFについて記事を書いていました．最初の記事は古典的なBPFについて，二番目の記事はseccompについてです． eBPFに関する文章も書いていて，てっきり公開していたと思っていたのですが今下書きのまま保存され一年以上放置されていたことに気づきました.. BPFの開発は非常に活発で，ここに書いてる情報が古い可能性もあるのですが，せっかくなので公開しておきます．

この記事はLinux 4.7時点での情報に基づきます．プログラムはLinux 4.7（Ubuntu Xeniel）で動作確認しています．

extended BPF (eBPF)

前々回と前回のエントリでLinuxにおいてBPFのプログラムを利用してパケットフィルタリングやseccompを利用する例を見ました．BPFを利用する利点は，大きく以下の2つです．

ユーザがフィルタプログラムを自由に設定できる
コードはカーネル内安全に実行される (実行前に静的に安全性をチェック）

そんなBPFですが，これを拡張し，カーネル内の様々なイベントに対してユーザが定義した処理を実行できるようにすれば，様々なトレースに使えるのではないかという議論が2011年ごろから*1起こりました．そして，その機能実現のためにBPFのレジスタマシンを拡張したextended BPF (eBPF)が考案されました．昔からあるBPFをclassic BPF (cBPF)，extended BPFをeBPFあるいはinternal BPFとして区別します*2．

eBPFは以下のような特徴/機能があります．

10個のレジスタ (cBPFは2つ)
- R0 : 戻り値格納用
- R1-R5 : 引数
- R6-R9 : BPFプログラムが利用
- R10: スタックへアクセスするためのフレームポインタ (read only)
レジスタ幅は64bit (cBPFは32bit)
ジャンプが jt/jf ではなく jt/fall through に
負の方向のジャンプを許可
他のbpfプログラムへのジャンプを許可 (ただし無限ループできないように遷移回数は制限されている)
bpf_call命令によるカーネル内の関数の呼び出し
eBPF mapによるデータのやりとり

eBPF map

eBPFの中でも特にeBPF mapはダイナミックトレースを実現するのに欠かせない機能です． eBPF mapはbpfで利用可能なデータ構造で，eBPFプログラム間やユーザスペース/カーネルスペースのプログラム間でのデータのやりとりに利用します．例えばeBPFマップを利用することで任意の型のkey/valueの連想配列を作成することができます． eBPF mapはまず最初にユーザプロセスが作成します．BPFプログラムはそのmapにプログラム中からアクセスすることができます．

eBPFプログラムの例

eBPF mapを作成したり，あるいはeBPFのプログラムをイベントにアタッチするにはLinux 3.18から追加されたbpf(2)システムコールを利用します． bpf(2)のマニュアルに情報がありますが，とりあえず現在(2016/8/1)においては情報がやや古いです.. カーネルのソースのsamples/bpf以下にeBPFのプログラムの例があるので，それと合わせてドキュメントを見た方がいいと思います．

ここでは，サンプルの中でお手頃なsock_exasmple.cを見てみましょう．このプログラムはeBPFを利用して，受信したTCPパケット，IPパケット，ARPパケットの種類をカウントするものです．

/* eBPF example program:
 * - creates arraymap in kernel with key 4 bytes and value 8 bytes
 *
 * - loads eBPF program:
 *   r0 = skb->data[ETH_HLEN + offsetof(struct iphdr, protocol)];
 *   *(u32*)(fp - 4) = r0;
 *   // assuming packet is IPv4, lookup ip->proto in a map
 *   value = bpf_map_lookup_elem(map_fd, fp - 4);
 *   if (value)
 *        (*(u64*)value) += 1;
 *
 * - attaches this program to eth0 raw socket
 *
 * - every second user space reads map[tcp], map[udp], map[icmp] to see
 *   how many packets of given protocol were seen on eth0
 */
#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <linux/bpf.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <linux/if_ether.h>
#include <linux/ip.h>
#include <stddef.h>
#include "libbpf.h"

static int test_sock(void)
{
    int sock = -1, map_fd, prog_fd, i, key;
    long long value = 0, tcp_cnt, udp_cnt, icmp_cnt;

    map_fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(key), sizeof(value),
                256, 0);
    if (map_fd < 0) {
        printf("failed to create map '%s'\n", strerror(errno));
        goto cleanup;
    }

    struct bpf_insn prog[] = {
        BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
        BPF_LD_ABS(BPF_B, ETH_HLEN + offsetof(struct iphdr, protocol) /* R0 = ip->proto */),
        BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4), /* *(u32 *)(fp - 4) = r0 */
        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), /* r2 = fp - 4 */
        BPF_LD_MAP_FD(BPF_REG_1, map_fd),
        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
        BPF_MOV64_IMM(BPF_REG_1, 1), /* r1 = 1 */
        BPF_RAW_INSN(BPF_STX | BPF_XADD | BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* xadd r0 += r1 */
        BPF_MOV64_IMM(BPF_REG_0, 0), /* r0 = 0 */
        BPF_EXIT_INSN(),
    };

    prog_fd = bpf_prog_load(BPF_PROG_TYPE_SOCKET_FILTER, prog, sizeof(prog),
                "GPL", 0);
    if (prog_fd < 0) {
        printf("failed to load prog '%s'\n", strerror(errno));
        goto cleanup;
    }

    sock = open_raw_sock("lo");

    if (setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, &prog_fd,
               sizeof(prog_fd)) < 0) {
        printf("setsockopt %s\n", strerror(errno));
        goto cleanup;
    }

    for (i = 0; i < 10; i++) {
        key = IPPROTO_TCP;
        assert(bpf_lookup_elem(map_fd, &key, &tcp_cnt) == 0);

        key = IPPROTO_UDP;
        assert(bpf_lookup_elem(map_fd, &key, &udp_cnt) == 0);

        key = IPPROTO_ICMP;
        assert(bpf_lookup_elem(map_fd, &key, &icmp_cnt) == 0);

        printf("TCP %lld UDP %lld ICMP %lld packets\n",
               tcp_cnt, udp_cnt, icmp_cnt);
        sleep(1);
    }

cleanup:
    /* maps, programs, raw sockets will auto cleanup on process exit */
    return 0;
}

int main(void)
{
    FILE *f;

    f = popen("ping -c5 localhost", "r");
    (void)f;

    return test_sock();
}

プログラムの主要点について見ていきいます．

eBPFのmapの作成

    map_fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(key), sizeof(value),
                256, 0);

bpf_create_map()によって大きさが256のeBPF mapを作成します．map_fdがこのeBPF mapのdescriptorです．

eBPFプログラムの作成

/*
 * - loads eBPF program:
 *   r0 = skb->data[ETH_HLEN + offsetof(struct iphdr, protocol)];
 *   *(u32*)(fp - 4) = r0;
 *   // assuming packet is IPv4, lookup ip->proto in a map
 *   value = bpf_map_lookup_elem(map_fd, fp - 4);
 *   if (value)
 *        (*(u64*)value) += 1;
 */

    struct bpf_insn prog[] = {
        BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
        BPF_LD_ABS(BPF_B, ETH_HLEN + offsetof(struct iphdr, protocol) /* R0 = ip->proto */),
        BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4), /* *(u32 *)(fp - 4) = r0 */
        BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
        BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), /* r2 = fp - 4 */
        BPF_LD_MAP_FD(BPF_REG_1, map_fd),
        BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
        BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
        BPF_MOV64_IMM(BPF_REG_1, 1), /* r1 = 1 */
        BPF_RAW_INSN(BPF_STX | BPF_XADD | BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* xadd r0 += r1 */
        BPF_MOV64_IMM(BPF_REG_0, 0), /* r0 = 0 */
        BPF_EXIT_INSN(),
    };

cBPFと同様に，define済みのマクロを利用してeBPFのプログラムを作成することができます． <linux/bpf.h>にeBPFの命令や，eBPFプログラムから呼び出すことのできる関数が宣言されています． eBPFについても詳しくはカーネルのドキュメントに書いてあります．

このプログラムが何をしているかというのは，コメントに書いてある通りですが，ポイントとしては

R1-R5のレジスタが引数として使われる
R10はフレームポインタ
最初R1にはパケットデータを保持するsk_buffのポインタが格納されている
BPF_LD_ABS (正確にはBPF_ABS | <size> | BPF_LD）は特別な命令で，sk_buffからデータを読み出す．このときR6レジスタにsk_buffのポインタを格納する．（注: パケットデータはsk_buff構造体の中のポインタからアクセスするため，単純なeBPFの命令ではアクセスできない．そのため特別扱いしている)
BPF_CALLでBPF_FUNC_map_lookup_elem（この関数はカーネル内にあらかじめ存在）を呼び出している
BPF_FUNC_map_lookup_elemの第一引数はeBPF mapのfd，第二引数はキーのアドレス．ここではスタック上にキーを格納し，それを渡している．戻り値はキーに対応するマップが見つかったらそのアドレス

eBPFフィルタプログラムの利用

BPFでパケットフィルタリングする場合は，setsockopt(2)を使ってソケットのfdに対してcBPFのプログラムをアタッチすることができました．このとき実はcBPFのプログラムは内部でeBPFのプログラムに変換され実行されます．

それでは，eBPFプログラムそのものをソケットにアタッチすることはできるのでしょうか? 答えはもちろんイエスです．アタッチする手順は以下の通りです．

bpfシステムコール（Linux 3.18から追加）を使って，まずカーネル空間にeBPFのプログラムを追加
setsockoptの第二引数にSO_ATTACH_BPFを指定してeBPFのプログラムをアタッチする

上のプログラムではbpfシステムコールの代わりに，そのラッパー関数であるbpf_prog_loadを利用しています．

    prog_fd = bpf_prog_load(BPF_PROG_TYPE_SOCKET_FILTER, prog, sizeof(prog),
                "GPL", 0);
    if (prog_fd < 0) {
        printf("failed to load prog '%s'\n", strerror(errno));
        goto cleanup;
    }

    sock = open_raw_sock("lo");

    if (setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, &prog_fd,
               sizeof(prog_fd)) < 0) {
        printf("setsockopt %s\n", strerror(errno));
        goto cleanup;
    }

eBPFプログラムはカーネル内で実行されるため，カーネルモジュールと同様にライセンスを明示する必要があります． bpf_prog_loadの第四引数でライセンスとして"GPL"を指定しています．GPL compatibleなライセンスにしておかないとカーネル内の他のGPLの関数が呼べなくなります．

`setsockopt`の挙動

BPFに関するsetsockoptの挙動を整理しておくと，

cBPFプログラムのロードは，SO_ATTACH_FILTER
- このとき，sk_attach_filterが呼ばれる
  - さらに，sk_attach_filterから，__get_filter() > bpf_prepare_filter() > bpf_migrate_filter() > bpf_convert_filter() と関数が呼ばれcBPFはeBPFに変換される
eBPFプログラムのロードは，SO_ATTAH_BPF
- このとき，sk_attach_bpfが呼ばれる

JIT

Linux 3.16からeBPFに対してもJITが使えるようになりました．ちなみに，BPFをJIT化しようとする議論は2011年ごろからありました（A JIT for packet filters）．

/proc/sys/net/core/bpf_jit_enable を1にするとjitが有効になります．また，2にするとdebugモードとなり，jitの結果がdemsgで確認できます．デフォルトは無効化（0）されています．

ソース

eBPFの主なソースはkernel/bpfにあります．また，tools/net以下にBPFのアセンブラ/ディスアセンブラがあります． eBPFのインタプリタに興味がある方は，eBPFのユーザランド実装であるubpfを見た方が分かりやすいかもしれません．

まとめ

今回はeBPFの基礎について簡単に説明しました． eBPFによるトレースの方法や，実際にeBPFプログラムを作成する方法（もちろん，#defineを使わないで作成する方法があります）などは機会があれば別に書こうと思います．

*1:もっと前からあったかもしれない

*2:最近ではLinuxでBPFといった場合eBPFの方を指すようになってきているようです

睡分不足

LinuxのBPF : (3) eBPFの基礎

はじめに（注意）

extended BPF (eBPF)

eBPF map

eBPFプログラムの例

eBPFのmapの作成

eBPFプログラムの作成

eBPFフィルタプログラムの利用

`setsockopt`の挙動

JIT

ソース

まとめ

はじめに（注意）

extended BPF (eBPF)

eBPF map

eBPFプログラムの例

eBPFのmapの作成

eBPFプログラムの作成

eBPFフィルタプログラムの利用

setsockoptの挙動

JIT

ソース

まとめ

`setsockopt`の挙動