VMWare Fusionメモ

以下はVMWare Fusion 10.1.1 (macOS High Sierra 10.13.3)で動作確認したものです.

設定ファイル(xxx.vmx)はVM停止中に変更する必要があります(そうでないと書き換わることがある).

コマンドラインツール

/Applications/VMware\ Fusion.app/Contents/Library/ 以下にいくつかコマンドラインツールがインストールされている.

  • 起動:vmrun -T fusion start /path/to/vm.vmx
  • 停止:vmrun -T fusion stop /path/to/vm.vmx
  • 再起動:vmrun -T fusion reset /path/to/vm.vmx
  • ディスクのデフラグ: vmware-vdiskmanager -d disk.vmdk
  • ディスクのコンパクション: vmware-vdiskmanager -k disk.vmdk

シリアルポート

設定ファイルに以下を記述

serial0.filename = "/tmp/serial0"
serial0.filetype = "pipe"
serial0.present = "TRUE"

こうするとゲストVMのCOM1の出力がホストのdomain socket/tmp/serial0へ送られるようになる.

socatを利用して標準出力へ出力できる.

socat -d -d unix-connect:/tmp/serial0 stdio

serial0をserial1に変えればCOM2になる(はず).

Nested Virtualization

設定ファイルに以下を記述

vhv.enable = "TRUE"

あるいは,GUIの方から設定>プロセッサとメモリ>詳細オプションから設定

gdb remote debugging

設定ファイルに以下を記述

debugstub.listen.guest64 = "TRUE"
debugstub.port.guest64 = "33333"

こうするとポート33333でgdb serverがlistenするようになる.

VM上でLinuxを実行している場合,以下のようにしてlldbからgdb serverへ接続可能 (vmlinuxは起動しているカーネルイメージ)

% lldb ./vmlinux
(lldb) target create "./vmlinux"
Current executable set to './vmlinux' (x86_64).
(lldb) gdb-remote 33333
Process 1 stopped
* thread #1, stop reason = signal SIGTRAP
    frame #0: 0xffffffff818dee06 vmlinux`native_safe_halt at irqflags.h:55
Target 0: (vmlinux) stopped.
(lldb) b sys_close
Breakpoint 2: where = vmlinux`SyS_close + 6 [inlined] SYSC_close at open.c:1153, address = 0xffffffff81265ee6
(lldb) c
Process 1 resuming
Process 1 stopped
* thread #1, stop reason = breakpoint 2.1
    frame #0: 0xffffffff81265ee6 vmlinux`SyS_close at open.c:1155
Target 0: (vmlinux) stopped.
(lldb) disassemble
vmlinux`SyS_close:
    0xffffffff81265ee0 <+0>:  nopl   (%rax,%rax)
    0xffffffff81265ee5 <+5>:  pushq  %rbp
->  0xffffffff81265ee6 <+6>:  movl   %edi, %esi
    0xffffffff81265ee8 <+8>:  movq   %gs:0x15bc0, %rax
    0xffffffff81265ef1 <+17>: movq   0xac8(%rax), %rax
    0xffffffff81265ef8 <+24>: movq   %rsp, %rbp
    0xffffffff81265efb <+27>: movq   %rax, %rdi
    0xffffffff81265efe <+30>: callq  0xffffffff8128c7f0        ; __close_fd at file.c:621
    0xffffffff81265f03 <+35>: movslq %eax, %rdx
    0xffffffff81265f06 <+38>: movq   $-0x4, %rax
    0xffffffff81265f0d <+45>: leal   0x201(%rdx), %ecx
    0xffffffff81265f13 <+51>: cmpl   $0x1, %ecx
    0xffffffff81265f16 <+54>: jbe    0xffffffff81265f27        ; <+71> at open.c:1153
    0xffffffff81265f18 <+56>: movl   %edx, %ecx
    0xffffffff81265f1a <+58>: andl   $-0x3, %ecx
    0xffffffff81265f1d <+61>: cmpl   $0xfffffdfc, %ecx         ; imm = 0xFFFFFDFC
    0xffffffff81265f23 <+67>: cmovneq %rdx, %rax
    0xffffffff81265f27 <+71>: popq   %rbp
    0xffffffff81265f28 <+72>: retq

ちなみにLinuxカーネルデバッグする際はKASLRはオフにしておいた方がいろいろ楽だと思います (ブートプションにnokaslrをつける)

Vagrant

VagrantVMWare Fusionを利用するには,Vagrant VMWare pluginを購入する必要がある.

Vagrant用Boxの作成

VMWare Fusion用のBoxはあまり作成されていないので,自分で作った方が良いと思います.

基本は適当にVMをセットアップしたのち,VMの保存されているディレクトリへ移動し,

$ vmware-vdiskmanager -d disk.vmdk
$ vmware-vdiskmanager -k disk.vmdk
$ tar zcvf <box_name>.box *.{nvram,vmsd,vmx,vmxf,vmdk} metadata.json
$ vagrant box add <box_name> <box_name>.box --provider vmware_fusion

metadata.jsonの中身は以下の通り

{
  "provider": "vmware_fusion"
}

VMをセットアップする際の注意点

Vagrantfile

簡単な例

Vagrant.configure("2") do |config|
  config.vm.box = "ubuntu"
  config.ssh.guest_port = 22
  if ARGV[0] == "ssh"
    config.ssh.username = "m"
  else
    config.ssh.password = "vagrant"
  end

  config.vm.provider "vmware_fusion" do |v|
    v.vmx["memsize"] = 4096
    v.vmx["numvcpus"] = 2
    v.gui = false
  end
end

vagrant sshしたときはvagrant以外のユーザに接続したいので,ARGV[0]の値に応じて,vagrant sshならuser mで接続,そうでない場合はuser vagrantで接続するように設定している. (user vagrantで接続する際はパスワード認証)

VMWare設定ファイル

VMWareの設定ファイルは .vagrant/machines/default/vmware_fusion/xxxxxxx/以下に存在

VMWare Fusionライブラリでの表示

VagrantでheadlessでVMを起動している場合,VMWare Fusionのライブラリの方にVMの情報が出てこない (https://github.com/hashicorp/vagrant/issues/8466) 少し試行錯誤したところ,どうやら一旦v.gui=trueで起動すればライブラリの方へ追加されるようである.

その他

  • ディスクサイズの変更は面倒なようなので,あらかじめ余裕を持ってディスクを作成しておくのが吉
  • 起動中のVMからboxを作成するvagrant packgeコマンドはVMWareでは使えない

SpectreとeBPF

新年早々巷にいろいろと賑わいをもたらしたSpectreとMeltdownですが,Google Project Zero (GPZ)が公表したSpectreの攻撃コード例の中でeBPFが使用されていました. 安全を謳っているものの昨年もいくつか脆弱性が発見されていたので,「またeBPFか」と思った方もいるかもしれません. といっても今回の件をeBPFの脆弱性と言ってしまうのは可哀想というか,ちょっと違うかなとは思いますが.

若干今さら感ありますがここでは簡単にeBPFがどう攻撃に使われたか簡単に書こうと思います. ちなみに後述するようにすでに対応策のパッチが存在しますので, 現在eBPFでSpectreを利用して攻撃するのは現実的にはかなり難しいのではないかと思います.

Variant1

SpectreのVariant1 (CVE-2017-5753)の基本となる問題は,以下のようなコードがあったとき,

if(index < max_index){
    // 何か処理
}

index >= max_indexであっても投機的実行によりif文の中が実行されてしまうことがあるというものです. もしindex >= max_indexであれば投機的実行された結果は破棄されるので問題ない,と信じられてきましたが,例えば以下のようなコードを考えます.

if(index < max_index){
    value = array[index];
    _ = array2[(value & 1) * 0x100];
}

array2のデータはキャッシュされていないとします.投機実行でif文の中が実行されたとき, array[index]の下位1bitの値に応じて,array2[0]あるいはarray2[0x100]のいずれかにアクセスされ,結果としてアクセスされた領域がキャッシュに乗ります. 従ってこの後array2[0]array2[0x100]のアクセス速度を比較することでarray[index]の下位1bitの値が分かります.

これを応用してあるプロセスのメモリ空間のデータを読み取るのがvariant 1ですが,そもそもこの攻撃を実施するには,

  • 攻撃対象のプロセスの中に上例のようなコードパターンが存在する
  • indexは攻撃者がコントロールできる
  • 適当なarray2に攻撃者がアクセスできる
  • データがキャッシュに乗っているかどうか判断できるだけの精度を持つタイマが利用できる

というようなことが条件になってきます. そんなプログラム果たしてあるのかという話ですが.可能性としては外部のコードを実行するインタプリタjitエンジンが一番あるのかなと思います. 実際GPZではeBPFを利用したカーネル内データの読み出し,論文の方ではV8のデータの読み出しのPoCを示しています.

eBPFを利用した攻撃例

GPZの攻撃例コードはこちらで公開されています.

variant 1の攻撃ではeBPF mapにアクセスする際の境界チェックのコードを利用します. 特に攻撃例で利用されているのはbpf_arrayの読み出し(array_map_lookup_elem())及びbpf_tail_call()です. いずれもstruct bpf_arrayのデータにアクセスする際に,array->map.max_entriesの確認をおこなっています.

array_map_lookup_elem()(variant 1対策前のLinux 4.14のコードです) https://github.com/torvalds/linux/blob/v4.14/kernel/bpf/arraymap.c#L112

static void *array_map_lookup_elem(struct bpf_map *map, void *key)
{
    struct bpf_array *array = container_of(map, struct bpf_array, map);
    u32 index = *(u32 *)key;

    if (unlikely(index >= array->map.max_entries))
        return NULL;

    return array->value + array->elem_size * index;
}

bpf_tail_call() https://github.com/torvalds/linux/blob/v4.13/kernel/bpf/core.c#L1009 (Linux 4.13のコード)

    JMP_TAIL_CALL: {
        struct bpf_map *map = (struct bpf_map *) (unsigned long) BPF_R2;
        struct bpf_array *array = container_of(map, struct bpf_array, map);
        struct bpf_prog *prog;
        u64 index = BPF_R3;

        if (unlikely(index >= array->map.max_entries))
            goto out;
        if (unlikely(tail_call_cnt > MAX_TAIL_CALL_CNT))
            goto out;

        tail_call_cnt++;

        prog = READ_ONCE(array->ptrs[index]);
        if (!prog)
            goto out;

攻撃の流れは以下のようになります.

  1. bpf_map_read()を利用してカーネル内のデータを(投機実行で)読み出し
  2. bpf_tail_call()を利用して読み出したデータの値に基づいて(投機実行で)ユーザスペースの領域にアクセス
  3. ユーザスペース領域のキャッシュヒットを調べてデータを読みだす

攻撃のために2回投機実行を利用しています. なぜ,ユーザスペースの領域にアクセスする際にbpf_map_read()を利用していないかというと,これはおそらくbpf_map_read()のindexが32bitである一方で, bpf_tail_call()のindexが64bitだったから(現在は修正済み)だと思います. 実際のeBPFコードは以下のようになっています.

  struct bpf_insn insns[] = {
    // save context for tail call
    BPF_MOV64_REG(BPF_REG_6, BPF_REG_ARG1),

    // r7 = bitmask
    BPF_LD_MAP_FD(BPF_REG_ARG1, ret.data_map),
    BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_FP),
    BPF_ALU64_IMM(BPF_ADD, BPF_REG_ARG2, -4),
    BPF_ST_MEM(BPF_W, BPF_REG_ARG2, 0, 2),
    BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
    BPF_GOTO_EXIT_IF_R0_NULL,
    BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_0, 0),

    // r9 = bitshift selector
    BPF_LD_MAP_FD(BPF_REG_ARG1, ret.data_map),
    BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_FP),
    BPF_ALU64_IMM(BPF_ADD, BPF_REG_ARG2, -4),
    BPF_ST_MEM(BPF_W, BPF_REG_ARG2, 0, 3),
    BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
    BPF_GOTO_EXIT_IF_R0_NULL,
    BPF_LDX_MEM(BPF_DW, BPF_REG_9, BPF_REG_0, 0),

    // r8 = prog_array_base_offset = *map_lookup_elem(data_map, &1)
    BPF_LD_MAP_FD(BPF_REG_ARG1, ret.data_map),
    BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_FP),
    BPF_ALU64_IMM(BPF_ADD, BPF_REG_ARG2, -4),
    BPF_ST_MEM(BPF_W, BPF_REG_ARG2, 0, 1),
    BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
    BPF_GOTO_EXIT_IF_R0_NULL,
    BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_0, 0),

    // r0 = secret_data_offset = *map_lookup_elem(data_map, &0)
    BPF_LD_MAP_FD(BPF_REG_ARG1, ret.data_map),
    BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_FP),
    BPF_ALU64_IMM(BPF_ADD, BPF_REG_ARG2, -4),
    BPF_ST_MEM(BPF_W, BPF_REG_ARG2, 0, 0),
    BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
    BPF_GOTO_EXIT_IF_R0_NULL,
    BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0),

    // r2 = &secret_data_offset
    BPF_MOV64_REG(BPF_REG_ARG2, BPF_REG_FP),
    BPF_ALU64_IMM(BPF_ADD, BPF_REG_ARG2, -4),
    BPF_STX_MEM(BPF_W, BPF_REG_ARG2, BPF_REG_0, 0),


    BPF_LD_MAP_FD(BPF_REG_ARG1, ret.victim_map),
    BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), /* speculative execution starts in here */
    BPF_GOTO_EXIT_IF_R0_NULL, /* predicted: non-NULL, actual: NULL */
    BPF_LDX_MEM(BPF_DW, BPF_REG_ARG3, BPF_REG_0, 0),

    /*
     * mask and shift secret value so that it maps to one of two cachelines.
     */
    BPF_ALU64_REG(BPF_AND, BPF_REG_ARG3, BPF_REG_7),
    BPF_ALU64_REG(BPF_RSH, BPF_REG_ARG3, BPF_REG_9),
    BPF_ALU64_IMM(BPF_LSH, BPF_REG_ARG3, 7),
    BPF_ALU64_REG(BPF_ADD, BPF_REG_ARG3, BPF_REG_8),

    BPF_LD_MAP_FD(BPF_REG_ARG2, ret.prog_map),
    BPF_MOV64_REG(BPF_REG_ARG1, BPF_REG_6),

    BPF_EMIT_CALL(BPF_FUNC_tail_call),

    BPF_MOV64_IMM(BPF_REG_0, 0),
    BPF_EXIT_INSN()
  };

配列のオフセットを指定するためのindexは事前に作成したdata_mapという別のeBPF mapを利用して指定しています. victim_mapという名のarrayを使ってカーネル内データ読み出し,prog_mapという名のarrayを使ってtail callを経由したユーザランド領域へのアクセスをおこなっています.

ちなみに,わざわざeBPFプログラムを利用しなくてもユーザ空間から直接投機実行でカーネル空間のデータを読み出せばいいのではないかと思った方.それがmeltdownです*1

ユーザ空間へのオフセットの導出

さて,ここまでは比較的単純ですが,実際に攻撃する際にはprog_mapのindexとして,ユーザの特定領域にアクセスするための適当なindexを指定する必要があります. 言い換えると,prog_mapからユーザ領域へのオフセットを求める必要があります. GPZの例ではこのオフセットの導出にもvariant 1を利用しています.

アイディアはシンプルで,prog_mapを使ってtail callを適当なindexで実行し,その後ユーザ領域がキャッシュされていればそこからオフセットが計算できます. といっても,prog_mapはkmallocで確保*2 されますが,kmallocの空間の探索 (kernel logical address = ffff880000000000 - ffffc7ffffffffff = 64TB) を愚直に探索するのは非効率です. そこでどうするのか...というのはGPZのブログに丁寧に書いてあるんですが,ざっくりまとめると

  • 231の空間をユーザスペースに確保
    • 実際には 24(=16個) のページからなる領域を215個作成
    • 各領域は同じ物理メモリをマッピング
      • mmap(MAP_NORESERVE)で231の空間を確保したのち,24ページサイズのファイルを作成,その領域にmmap()で各領域にそのファイルを割り当てる
  • tail callを利用してオフセットを探索.オフセットは231単位で更新する.
  • キャッシュヒットを探すには最初の24ページの領域を調べればok
  • ヒットが見つかると...
    • 48-63: canonical address (ビットの先頭は1と決まっている)
    • 32-47: brute forceのhiger bit
    • 16-31: 不明
    • 12-15: 領域のどのページにヒットしたかから分かる
    • 0-11: 0 (kmallocで4KB単位で取得したから((mapを作成する際のサイズを2049にしている)))
    • 中間の15bitがワカラナイ
  • 中間ビットの求め方
    • 2つのページを用意.探索したいアドレスの半分の仮想アドレスを一つのページ,もう一つを別のページに割り当て
    • これを使ってバイナリサーチ

というようなことをしています,

キャッシュのフラッシュ方法

攻撃を成功させるために重要なことは,境界外のindexに対して投機実行されるようにすることです. このために,攻撃前に境界内のindexを用いて何回か事前に関数を実行しておきます, また,もう一つ重要なこととしてif()分の中で利用される変数(今回の場合はarray->map.max_entries)がキャッシュされていないことが挙げられます. x86ではclflushを利用すればキャッシュフラッシュができますが,当然ながら攻撃者がclflushを使ってarray->map.max_entriesのキャッシュをフラッシュすることは不可能です. そこで,GPZの攻撃例ではfalse sharingを利用したキャッシュフラッシュをおこなっています.

もともとstruct bpf_mapは以下のようになっていました(現在では修正が入っています).

https://github.com/torvalds/linux/blob/v4.14/include/linux/bpf.h#L44

struct bpf_map {
    atomic_t refcnt;
    enum bpf_map_type map_type;
    u32 key_size;
    u32 value_size;
    u32 max_entries;
    u32 map_flags;
    u32 pages;
    u32 id;
    int numa_node;
    struct user_struct *user;
    const struct bpf_map_ops *ops;
    struct work_struct work;
    atomic_t usercnt;
    struct bpf_map *inner_map_meta;
};

この構造ではmax_entriesとeBPF mapの参照カウントであるrefcntが同じキャッシュライン上に存在することになります(キャッシュラインは64byte). refcntはmapを含むeBPFプログラムをロードする際(より正確にはverifierの内部)で更新されます. そこで,攻撃プログラムを実行するCPUコアとは別のコアでprog_mapvictim_mapを利用するeBPFプログラムをロードすると,その結果refcntが更新され,攻撃プログラム側のmax_entriesのキャッシュはfalse sharingによって破棄されることになります.

実際には以下のようなプログラムをロードしてfalse sharingします ((sched_setaffinity()でスレッドを実行するコアを制御できます)).cacheline_bounce_fdsprog_mapvictim_mapのfdが入っています.

struct bpf_insn insns[] = {
  BPF_LD_MAP_FD(BPF_REG_0, cacheline_bounce_fds[0]),
  BPF_LD_MAP_FD(BPF_REG_0, cacheline_bounce_fds[1]),
  BPF_LD_MAP_FD(BPF_REG_0, 0xffffff)
};

このプログラムはverifiationが通らずロードに失敗すると思いますが,キャッシュフラッシュするにはこれで十分です.

対策方法

variant 1に対する(ソフトウェア的な)対策の一つは投機実行がおきないようなプログラムを(フェンス命令などを使って)作成することです. ただし,CPUの投機実行の挙動を正確に把握することは困難です. もう一つのアプローチとしては投機実行されても問題がおきないようにする方法があります.

eBPFでは,eBPF mapにアクセスする際にindexをマスクするような修正が入りました(bpf: prevent out-of-bounds speculation). 例えば,array_map_lookup_elem()は以下のようにindexではなくindex & array->index_mskを使うように変更されています. これにより誤って投機実行されても外部領域にアクセスすることを防いでいます.

https://github.com/torvalds/linux/blob/v4.15/kernel/bpf/arraymap.c#L140

static void *array_map_lookup_elem(struct bpf_map *map, void *key)
{
    struct bpf_array *array = container_of(map, struct bpf_array, map);
    u32 index = *(u32 *)key;

    if (unlikely(index >= array->map.max_entries))
        return NULL;

    return array->value + array->elem_size * (index & array->index_mask);
}

また,eBPFにはrefcntmax_entriesがfalse sharingされないようにする変更も入りました(bpf: avoid false sharing of map refcount with max_entries). これにより,struct bpf_mapは以下のように変更されています.____cacheline_alignedを利用してmax_entriesrefcntが別々のキャッシュラインに乗るようにしています.

https://github.com/torvalds/linux/blob/v4.15/include/linux/bpf.h#L45

struct bpf_map {
    /* 1st cacheline with read-mostly members of which some
     * are also accessed in fast-path (e.g. ops, max_entries).
     */
    const struct bpf_map_ops *ops ____cacheline_aligned;
    struct bpf_map *inner_map_meta;
#ifdef CONFIG_SECURITY
    void *security;
#endif
    enum bpf_map_type map_type;
    u32 key_size;
    u32 value_size;
    u32 max_entries;
    u32 map_flags;
    u32 pages;
    u32 id;
    int numa_node;
    bool unpriv_array;
    /* 7 bytes hole */

    /* 2nd cacheline with misc members to avoid false sharing
     * particularly with refcounting.
     */
    struct user_struct *user ____cacheline_aligned;
    atomic_t refcnt;
    atomic_t usercnt;
    struct work_struct work;
    char name[BPF_OBJ_NAME_LEN];
}

さらに,tail callのindexを32bitになるする修正が(Spectre問題とは関係なく昨年10月に)入っています(bpf: fix bpf_tail_call() x64 JIT). また,jitを有効化した方が攻撃に成功しやすくなるようなので,jitを無効化するというのも一つの緩和策ではあります*4

一般的にはvariant 1の対策は個々のプログラム側でおこなわないといけない点が難しいところです. linuxでは対策を容易にするためにarray_index_nospecというマクロが提案されています. これは以下のように使うことを想定しています.

if (index < size) {
    index = array_index_nospec(index, size);
    val = array[index];
}

このマクロはindexをマスクした値を返しますが,indexがsizeより大きい場合はマスクとして0が利用されるので,結果としてindexは0になります.

SMAPとの関係

最近のintelのCPU (broadwellあたりから?) にはSMAP(Supervisor Mode Access Prevention)と呼ばれる,カーネル空間からユーザ空間のメモリ領域へのアクセスを制限する機能が入っています. GPZでの実験ではSMAPは無効にしたマシンで実験しているようです. SMAPを有効にした際に今回のeBPFの攻撃が成功するのかはよく分かりません. meltdownで権限チェックが回避されてしまう場合があるのを考えると,intelのCPUではSMAPも回避される場合があってもおかしくはないと思います.

Variant2

Spectreのvariant 2(CVE-2017-5715)は,以下のような分岐予測の特性を利用したものです*5

  • CPUの特権レベルによらず同じ分岐予測処理が実行される
  • 分岐予測判断にはソースアドレスの下位の一部しか利用されない
  • 分岐ターゲットアドレスは一部しか保存されていない *6

これにより,例えばゲストOSのユーザ空間のコードがハイパーバイザのコードの分岐予測に影響を与えることが可能になります. 特にGPZのPoCでは主にindirect jumpを利用して, KVMゲストからKVMホストのメモリ領域の読み出しをおこなっています.

メモリ読み出しの基本はvariant 1と同じです.例えば,

jmp *%rax

というような分岐命令があったとき,うまいこと分岐予測を失敗させて,以下のようなコードを投機実行させます.

value = array[index];
x = array2[value+offset];

そうするとvariant 1と同様に(うまくindexとoffsetを指定すれば)データが読み出せることになります.

variant 2で攻撃するには

  • データを読みだすのに使えるコード辺(ガジェット)が存在
  • 適切なoffsetやindexを求めてガジェットに渡す
  • 分岐予測を失敗させガジェットの関数を投機実行させる

といったことが必要になります.

まず,ガジェットに関して.GPZの例ではここでeBPFを利用します. どういうことかというと,indexからデータを読み出してキャッシュに載せるのはeBPFプログラムでおこなうようにして,ガジェットは単にそのeBPFプログラムを実行させるのに利用します. 具体的には,以下のようなガジェット利用して,__bpf_prog_run(const void *ctx, const struct bpf_insn *insn)を投機実行させます.

mov rsi, r9
call QWORD PTR [r8+0xb0]

__bpf_prog_run()はその名の通りeBPFを実行するインタプリタの関数です. System V AMD64のABIでは整数・ポインタ引数はRDI, RSI, RDX, RCX, R8, R9に順に格納されます. 従って,R8に__bpf_prog_runのアドレス (-0xb0),R9にeBPFのプログラムを格納したメモリ領域のアドレスを格納できれば上のガジェットを投機実行した結果,eBPFプログラムが投機実行されることになります.

PoCのコードでは以下のようなeBPFプログラムを利用しています. 読み出した値のビットが1かどうかによってhost_timing_leak_addrhost_timing_leak_addr+0x800をキャッシュに載せています.

struct bpf_insn evil_bytecode_instrs[] = {
  // rax = target_byte_addr
  { .code = BPF_LD | BPF_IMM | BPF_DW, .dst_reg = 0, .imm = target_byte_addr }, { .imm = target_byte_addr>>32 },
  // rdi = timing_leak_array
  { .code = BPF_LD | BPF_IMM | BPF_DW, .dst_reg = 1, .imm = host_timing_leak_addr }, { .imm = host_timing_leak_addr>>32 },
  // rax = *(u8*)rax
  { .code = BPF_LDX | BPF_MEM | BPF_B, .dst_reg = 0, .src_reg = 0, .off = 0 },
  // rax = rax ^ (0x00 or 0xff)
  { .code = BPF_ALU64 | BPF_XOR | BPF_K, .dst_reg = 0, .imm = (invert ? 0xff : 0x00) },
  // rax = rax << ...
  { .code = BPF_ALU64 | BPF_LSH | BPF_K, .dst_reg = 0, .imm = 10 - bit_idx },
  // rax = rax & 0x400
  { .code = BPF_ALU64 | BPF_AND | BPF_K, .dst_reg = 0, .imm = 0x400 },
  // rax = rdi + rax
  { .code = BPF_ALU64 | BPF_ADD | BPF_X, .dst_reg = 0, .src_reg = 1 },
  // rax = *((u8*)rax + 0x800)
  { .code = BPF_LDX | BPF_MEM | BPF_B, .dst_reg = 0, .src_reg = 0, .off = 0x800 },
  // clear rdi (rdi = rdi & 0)
  { .code = BPF_ALU64 | BPF_AND | BPF_K, .dst_reg = 1, .imm = 0 },
  // end
  { .code = BPF_JMP | BPF_EXIT }
};

__bpf_prog_runのアドレスやindexをどうやってガジェットに渡すかというと,GPZの例ではKVMでVMExitした際にR8やR9といったレジスタはゲストのものがそのまま引き継がれて暫く処理が実行されるという点を利用しています. 特にPoCではVMEXIT直後に呼ばれるkvm_x86_ops->handle_external_intr()を攻撃に使用します. このindirect jumpの分岐予測を失敗させてガジェットを投機実行させています((ちなみに,PoCでは攻撃をしやすくするためにVMEXIT直後(このへん)でkvm_x86_ops->handle_external_intrのキャッシュを明示的にclflushでフラッシュさせています.writeupの文章によると効率良くcache evictionさせる方法がいくつか研究であるようです.)).

ハイパーバイザで分岐予測を失敗させるには,ハイパーバイザで分岐を実行するアドレスと,ガジェットのアドレスを求め,ゲストのVM内で同じアドレスを使って分岐を適当に実行させるだけです*7. 実際には分岐予測にはアドレスの一部(せいぜい下位32bit?)しか使用しないので,下位のアドレスだけを使えばユーザ空間で分岐予測のコントロールができます.

さて,それでは問題は一体どうやってガジェットのアドレスや,ホストからゲストの領域へアクセスするためのオフセットを求めるかということになります. まずKVMホストのメモリ領域にはゲストのメモリ領域がマッピングされているはずなので,適当なオフセットを利用してホストからゲストのアドレスにアクセスすることは可能です. またガジェットのアドレスや分岐命令のアドレスなどは,vmlinuxやkvm.koなどがロードされているアドレスが分かればあとは,利用しているバージョンに基づいてオフセットを計算すれば求められます.

PoCのコードではホストの物理アドレスやオフセットなどの情報はゲストに与えて実行していますが, GPZのブログの方にvariant 2を利用してこれらの必要なアドレスをゲストから求める方法が解説されています. 分岐予測履歴をダンプすることでホスト側の分岐アドレス(の下位)を求め,そこから全体のアドレスを求めるようです*8

対応策

eBPF的にはインタプリタのコードがガジェットとして悪用されてしまうのが問題でした. そこで,常にeBPF JITを有効にし,カーネル内にインタプリタのコードを残さないようにするBPF_JIT_ALWAYS_ONというオプションが導入されました(従って,これはvariant 1とは逆の対応になります).

また,KVMの方では,VMEXITした後ゲストのレジスタの一部がそのままで処理が継続されるのが問題ということで,ゲストのレジスタを保存後にクリアする処理が追加されています. (コミットを見ると他にもいくつか修正が入っていることが確認できます)

一般的な対策として,Intelが低い特権レベルの分岐の影響を受けないようにするIBRS (Indirect Branch Restircted Speculation)や直前の分岐の影響を受けないようにするIBPB(Indirect Branch Prediction Barrier)といった, indirect jumpにおける投機実行を制限する機能をマイクロコードアップデートを通じて提供しています. ただしこの1月に提供されたマイクロコードにはバグがあったようで,つい先日windowsでマイクロコードアップデートを無効化するパッチが提供されていますし,この方法の安定利用にはもうしばらく時間がかかりそうです.

ソフトウェア的な解決方法としては, indirect jumpの代わりに一旦アドレスをスタックに積んでからreturnする retpolineという手法が提案されています. returnはindirect jumpとは違う分岐予測が適当されるようで, これにより仮にindirect jumpの分岐予測テーブルが汚染されても,その影響を受けないようにできるようです.

Linuxではブートオプションを通じてどの緩和策を利用するか選択できるようになっています

variant 2もプログラムごとに対応しなければならない点が難しいところです. もうしばらくはspectre対策でいろいろとアップデートがありそうです.

*1:本来であればpage tableのパーミッションがないためアクセスに失敗するはずですが,meltdownではintel CPU特有の権限チェックの前に投機実行してしまうという性質を利用してデータをキャッシュに載せます

*2: map_create() => find_alloc_map() => alloc_map() (fd_array_map_alloc() => array_map_alloc() => bpf_map_area_alloc()

*3:L3がPIPTなのは実験的にも常識的に考えてもそうなんだと思いますが,公式にはキャッシュ構成の情報は公開されていないような気がします. パタヘネに何か書いてあったかもしれない.

*4:おそらくほぼ全てのディストリビューションでBPF JITはデフォルトで無効化されています.

*5:もちろん,分岐予測の実装はCPUアーキテクチャごとに異なり,例えばARMは分岐予測の際に特権レベル等を考慮するのでこの脆弱性の影響を受けないようです

*6:GPZの分析によると,下位32bitもしくはjump元からのオフセットの値

*7:VM内のガジェットのアドレスは特に何もする必要がないので適当にただretする関数でも作成しておきます

*8:一体どうやって分岐予測履歴を求めたのかというと,頑張ってリバースエンジニアリングしたようです.恐るべし..

x86におけるメモリアクセス権のルール

定期的に忘れる気がするのでメモ.SDM Volume 3A 4.1.3, 4.6参照.

f:id:mm_i:20171107215451p:plain

用語

  • supervisor mode access
    • CPL < 3 でのアクセス
  • user mode access
    • CPL == 3 でのアクセス
  • supervisor mode address
    • page entryのU/S bitが一つでも0である領域*1
  • user mode addres
    • supervisor mode address以外の領域
  • implicit supervisor-mode access
    • 命令経由でのシステムのデータ構造(GDTなど)へのアクセス
  • explicit supervisor-mode access
    • implicit supervisor-mode access以外のCPL < 3でのアクセス

CPUの機能

  • SMEP (CR4 bit 20)
    • supervisor modeの場合user mode addressで実行不可
  • SMAP (CR4 bit 21)
    • supervisor modeの場合user mode addressへのwrite不可
  • PKE (CR4 bit 22)
    • Protection Keyを有効化
  • WP bit (CR0 bit 16)
    • 書き込み保護
  • NXE (IA32_EFER SMR bit 11)
    • 実行権限
  • U/S bit (page table)
    • user / supervisor modeの決定
  • R/W bit (page table)
    • 読み書き権限

備考

  • 操作を完了するには,条件1と条件2の2つを満たす必要がある
    • 条件1はsupervisor modeがuser mode addressにアクセスするための条件
    • 条件2は実行条件
  • 条件が複数ある場合はどちらかが満たされば良い
    • supervisor modeでuser modeへwriteする場合,2x2=4通りの条件の組み合わせがある
  • 空欄は無条件を意味する
  • R/W == 1 というのはページテーブルの各段でR/Wが1ということ
  • ぱっとみややこしいが,以下のような規則に基づいていることが分かる
    • user modeからsupervisor mode addressはアクセス不可
    • 書き込み制限 (WP = 1) は R/W=1 で回避可能
    • user領域へのアクセス制限 (SMAP=1) はEFLAGS.AC=1にすることで回避可能
      • このためにACフラグをセット/リセットするSTAC/CLAC命令がある
    • 実行不可能 (NXE=1) はXD=0で回避可能
  • アクセス権限がない場合#PF例外が発生
  • 32bit pagingの場合,NXE bitの機能はない
  • user mode addressへのread/writeは別途Protection Keyの制約がかかる
  • SMEPは2012年ごろ(ivy bridge),SMAPは2014年ごろ (broadwell), Protection Keyは2015年ごろ(skylake)から導入
    • 確認は /proc/cpuinfo で smap, smep, pku

Protection Key

  • CR4.PKE = 1 のとき,paging-structure entryの62:59の4bitをprotection keyとして使う
  • PKRUレジスタにprotection keyでアクセスし,アクセス権があるかを確かめる
    • PKRU[2i] (0 <= i <= 15) : access-disable
      • NOTE: executionはできる
    • PKRU[2i+1] (0 <= i <= 15) : write-disable
      • supervisor modeの場合,WP=0ならprotection keyの結果は無視される
  • protection keyはsupervisor mode addressに関しては無視される

*1:PML4E,PDPTE,PDE,PTEいずれかでU/S bitが0という意味

Ownership is theft? TockのTakeCellについて

tockというrust製の組み込み向けOSがあります. このtockの作成者らが2015年にOwnership is Theft: Experiences Building an Embedded OS in Rust (PLOS 2015)という論文を発表しました.そこでは著者がtockを開発する上で嵌ったownershipに関する問題と,それを解決するための言語の修正アプローチが述べられています.ただその後rustの開発者とのやりとりもあり,言語に修正を加えることなく当初実装したかったことが実装できたようです.The Case for Writing a Kernel in Rust (APSys'17)にそのことが簡単に書かれています.

Ownershipと問題

ご存知の通りrustにはメモリ安全を保証するためにownershipという仕組みがあり,たとえシングルスレッドでも同一データに対するmutableなreferenceを複数持つことができません.といってもmutableなreferenceが複数欲し場合は往々にしてあります.論文では以下のような構成の乱数生成器呼び出しを例に挙げています.

SysCallDispatcher <--> SimpleRNG <---> RNG
pub struct SimpleRNG {
    pub busy: bool,
}

impl SimpleRNG {
    pub fn command(&mut self) {
        self.busy = true;
        //...
    }

    pub fn deliver(&mut self, rand: u32) {
        self.busy = false;
        //...
    }
}

pub struct SysCallDispatcher<'a> {
    pub srng: &'a mut SimpleRNG,
}

pub struct RNG<'a> {
    pub srng: &'a mut SimpleRNG,
}

impl<'a> SysCallDispatcher<'a> {
    pub fn dispatch(&mut self) {
        self.srng.command();
    }
}

impl<'a> RNG<'a> {
    pub fn done(&mut self, num: u32) {
        self.srng.deliver(num);
    }
}

ここではSysCallDispatcherRNGがともにSimpleRNGのreferenceを所有する構成を考えていますが,このコードを実際に使用する場合はborrow checkに引っかかりコンパイルできません.

let mut srng = SimpleRNG { busy: false };
let mut dispathcer = SysCallDispatcher { srng: &mut srng };
// エラー: cannot borrow `srng` as mutable more than once at a time
let mut rng = RNG { srng: &mut srng };

解決策1. Cell

このような場合の解決策の一つはCellを使うことです.

use std::cell::Cell;

pub struct SimpleRNG {
    pub busy: Cell<bool>,
}

impl SimpleRNG {
    pub fn command(&self) {
        self.busy.set(true);
    }

    pub fn deliver(&self, rand: u32) {
        self.busy.set(false);
    }
}

pub struct SysCallDispatcher<'a> {
    pub srng: &'a SimpleRNG,
}

pub struct RNG<'a> {
    pub srng: &'a SimpleRNG,
}

impl<'a> SysCallDispatcher<'a> {
    pub fn dispatch(&self) {
        self.srng.command();
    }
}

impl<'a> RNG<'a> {
    pub fn done(&self, num: u32) {
        self.srng.deliver(num);
    }
}

こうするとコンパイルが通るようになります.

let mut srng = SimpleRNG { busy: false };
let mut dispathcer = SysCallDispatcher { srng: &srng };
let mut rng = RNG { srng: &srng };

ポイントとしては今回SysCallDispatcherRNG&mut Tではなく&T保有している点です.imutableなreferenceなのでborrow checkerにひかかりません.Cellは内部的にunsafeなコードを利用することで値を変更します.get()は値のコピーを返し,set()ではstd::mem::replace()を利用して値を書き換えます.

CellはCopyを実装している型しか使えません.またCellはSyncを実装していないため,Cellをスレッド間で共有するようなコードはコンパイルエラーになります.そのためデータ競合が生じることはありません.

Copyを実装している型しか使えないというのは大きな制約です.プリミティブ型はCellでいいですが,バッファ領域などを共有することができません(&mut TCopyを実装していません).

解決策2. TakeCell

バッファ領域などを共有するために,tockではTakeCellというものを利用しています.TakeCellはCellと似ていますが,以下のデータ構造を利用してreferenceを保持します.

pub struct TakeCell<'a, T: 'a + ?Sized> {
    val: UnsafeCell<Option<&'a mut T>>,
}

take()を利用してTakeCellの値を取得することができます.もし仮にTakeCellの中身が別から取得されている場合はNoneが返ります.

    pub fn take(&self) -> Option<&'a mut T> {
        unsafe {
            let inner = &mut *self.val.get();
            inner.take()
        }
    }

また,クロージャからTakeCellのデータを簡単に利用できるようにmap()というメソッドを提供しています.

    pub fn map<F, R>(&self, closure: F) -> Option<R>
        where F: FnOnce(&mut T) -> R
    {
        let maybe_val = self.take();
        maybe_val.map(|mut val| {
            let res = closure(&mut val);
            self.replace(val);
            res
        })
    }

take()するとTakeCellのデータはNoneになります.そこでデータをTakeCellに戻したい場合はmap()のコードにあるように明示的に戻す必要があります.

TakeCellを使うと例えば以下のようなコードが書けます.

pub struct DMAChannel {
    pub buffer: TakeCell<'static, [u8]>,
}

impl DMAChannel {
    pub fn foo(&mut self) {
        self.buffer.map(|b| {
            //...
        });
    }
}

static mut buffer: [u8; 128] = [0; 128];

fn foo(){
    let mut chan = unsafe {
        DMAChannel {
            buffer: TakeCell::new(&mut buffer),
        }
    };
    chan.foo();
}

staticなborrowを作るためにはunsafeなコードが必要です.

RefCellとtry_borrow_mut

rustを書いたことがある人ならTakeCellなんか利用しなくてもRefCellでいいのでは?と思うと思います. RefCellはget(), set()の代わりにborrow()及びborrow_mut()を提供し,値のreferenceを操作することができます.RefCellはCopyを実装していなくても使用することができます.

RefCell最大の特徴はコンパイル時ではなく実行時にborrow checkをするということです.もし仮に複数のmutableなreferenceを使用とした場合,実行時にpanicします.RefCellを使って安全なコードを書くのはプログラマの責任です.カーネル内でpanicしてしまうのは大変望ましくありません.TakeCellの場合はもしtake()されていたらNoneが返ります (map()の場合は何もしないで終わります). ただし,RefCellにはtry_borrow_mut()というメソッドがあり,もし仮にすでにmutableなrreferenceが取得されていた場合Errが返ります.

TakeCellを利用しなくても,try_borrow_mut()でそれと同等な機能ができるような気がします. それではなぜtockがTakeCellを使っているのかというと... このredditのコメントによると TakeCellができたのはtry_borrow_mut()が導入されるよりも前 *1 というのが最大の理由のようです.

ちなみに,tockにはTakeCellとすごく似ているMapCellというデータ構造もあります.MapCellはreferenceではなく実際の値を保持するようになっており,実際に値を保持しているかはoccupiedと呼ばれるフィールドで保持しています.一方TakeCellは値をreferenceに限定することでOptionのnon-null optimizationを利用してoccupied分のデータ構造を節約しています*2

また,普通だとCellRefCellRcと組み合わせて利用することが多いと思いますが今回カーネル内で動的にメモリを確保することは考えていないのでRcの利用はオプション外です.tockだと基本的にTakeCellでは'staticなバッファ領域を共有するようです.

*1:try_borrow_mutはrust 1.13 (2016-10)からです

*2:refrerenceはnullにならないことが保証されているため,0以外ならreference, 0ならNoneというように判断できます

cBPFプログラムをLLVM IRに変換する

最近Linuxでいろいろと大活躍のBPF (Berkeley Packet Filter)には主に2種類あって,一番最初に提唱されlibpcapなどで利用されるcBPF (classic BPF)と,主にLinux内で現在利用されている,cBPFをベースに拡張したeBPF (extended BPF)があります. cBPFのプログラムはlibpcapを使ってtcpdumpなどで使われるフィルタ式からコンパイルすることが可能です.一方eBPFはllvmのバックエンドでサポートされているためclangを使ってC言語からコンパイルすることが可能です.

Linuxカーネル内にcBPFプログラムをeBPFプログラムに変換する機構を持っていて,cBPFプログラムを使う場合は内部的にeBPFに変換されて実行されています. これによりlibpcapでコンパイルしたcBPFプログラムはLinux内で使うことができますが,最近ちょっとしたプロジェクトでubpfというeBPFのユーザランド実装を使った環境でlibpcapを使ってコンパイルしたcBPFプログラムを動かしたいということがありました. そこで簡単にcBPFのプログラムをeBPFに直接変換するものを作ってみましたが,ふとcBPFプログラムをLLVM IRに変換すれば,LLVMの方で最適化もしてくれるしコンパイルも楽になるのではと思い,やってみることにしました.

ちなみに,実質的に機械語からLLVM IRの変換となるわけで,なんじゃそりゃという感じかもしれませんが機械語からLLVM IRに変換するアイディアは自体は特に新しいものでもなんでもなくて,主に最適化や(セキュリティ用途の)プログラムの静的解析などを目的としていろいろとおこなわれています.代表的なプロジェクトとしては dagger, mcsema, fcd, libbeauty, fracture, BAP*1などがあります.

TL;DR

これ

ドキュメント

結局試行錯誤しながらやってくしかないんですが,特に参考したものを挙げておきます.

LLVM IR生成の基礎

LLVM API

cBPFは単純な機械語なので変換時にそのまま直接LLVM IRをprintで出力するようにして変換しても十分対応可能というか,その方が簡単になるような気もしますがここでは最適化のことなども考えてLLVMAPIを使う方向でいきます.

LLVMAPIにはCのものと,C++のもの2種類存在します.また,LLVM C APIのrust bindingとしてllvm-sys*2があります.今回はこのllvm-sysを使っていこうと思います.まぁどの言語で書いてもだいたい似たような感じになると思います.llvm-sysは基本的にCのAPIをそのままラッパしているだけなので,使う場合はほぼ全てunsafeになります.rustでLLVM APIのsafeなinterfaceを提供しようというプロジェクトはいくつかあって,例えばiron-llvmllvm-rs (llvm-alt)*3がありますが,いずれも最近は更新が止まっているようにみえます.

今回はLLVM5.0を利用しています.

LLVM IR生成のための基本要素

IR生成に関して,主に以下の構成要素があります.

  • Module
  • Function
    • 複数のBuilding Blockから構成される
  • Bulding Block
    • single entry, single exitのセクション
    • control flow graphの一つのノードに相当
    • 複数の命令から構成される
  • Context
    • IR生成の状態を管理するもの
  • IR builder
    • 実際にIRを生成するのに利用

llvm-sysを利用してIRを生成する際はとりあえず以下のような感じになります.

        // context, module, builderの作成
        let context = llvm::core::LLVMContextCreate();
        let module = llvm::core::LLVMModuleCreateWithNameInContext(b"hoge\0".as_ptr() as *const _, context);
        let builder = llvm::core::LLVMCreateBuilderInContext(context);

        /* ここでIRを生成 */

        // IRのダンプ
        llvm::core::LLVMDumpModule(module);

        // cleanup処理
        llvm::core::LLVMDisposeBuilder(builder);
        llvm::core::LLVMDisposeModule(module);
        llvm::core::LLVMContextDispose(context);

関数の作成

関数は主に以下の手順で作成します.

  • LLVMFunctionType()でまず関数の型を作成
  • LLVMAddFunction()でmoduleに関数を追加
  • LLVMAppendBasicBlockInContext()で関数にBasick Blockを追加
  • LLVMPositionBuilderAtEnd()でbuilderが引数で渡したBasick Blockの末尾を指すようにする
  • LLVMBuid**() 命令を使ってBasick Blockの末尾に命令を追加していく

何もしないでただリターンする関数を作る場合は以下のようになります.

        let ty_void = llvm::core::LLVMVoidTypeInContext(context);
        let ty_function = llvm::core::LLVMFunctionType(ty_void, ptr::null_mut(), 0, 0);
        let function =
            llvm::core::LLVMAddFunction(module, b"hoge\0".as_ptr() as *const _, ty_function);

        let bb = llvm::core::LLVMAppendBasicBlockInContext(
            context,
            function,
            b"entry\0".as_ptr() as *const _,
        );
        llvm::core::LLVMPositionBuilderAtEnd(builder, bb);
        llvm::core::LLVMBuildRetVoid(builder);

これにより以下のようなLLVM IRが生成されます.

; ModuleID = 'hoge'
source_filename = "hoge"

define void @hoge() {
entry:
  ret void
}

この場合はBasic Blockは一つしかなく,entryと名前がつけられています.個人的にちょっとわかりにくいのがbuilderで命令を生成する際にはまずLLVMPositionBuilderAtEnd()などの命令を使ってどのBuilding Blockのどこを指すかを指定しておいて,その後その箇所にIRを追加していくという点です.まぁこういうものだと思っておきます.

基本的に命令を出力する関数はLLVMBuild*という名前になっています(C++ APIの場合は Create*になっています). どんな関数が使えるかはLLVM C APIdoxygenのドキュメントを見るか,llvm-sysのcore.rsを参照するといいと思います.

ちなみに,Basic Blockの最後はterminater instruction, つまりbranchとかreturn命令で終了しなければならないという決まりがあります.複数のBasic Blockがあって,あるBasic Blockから次のBasic Blockにそのままfall throughする場合でも明示的なbranch命令が必要になります.

変数の利用

LLVM IRは無限個のレジスタが使えますが,基本的にレジスタへの代入はStatic Single Assignment form (SSA)である必要があります.要するに一度変数を割り当てたら再代入できないということです.LLVMBuild*関数は全てLLVMValueRefを返しますが,このときLLVMBuld*関数の引数で渡した名称でレジスタへの割り当てがおこなわれ,そのレジスタの参照が返ります.ちなみにもし引数で渡した名称が以前に渡したものと同じなら,自動的に連番が振られて名前が衝突しないようになります.

また,allocaというIRの命令でスタック上にメモリを割り当てることも可能です.スタック上のメモリの読み書きはload/store命令で実行することが可能です.

SSAの制約があるため,分岐処理をする場合に分岐内である変数が変更され,分岐後にその変数にアクセスしたい場合はphi命令という特殊な命令を利用します(詳細はSSAWikipediaの記事に書いてあります).ただしload/store命令を利用して明示的にスタック上の変数としてやりとりすればphi命令の使用を回避できます.IR的にはlaod/store命令を使用しない方が効率的なコードとなるはずです.LLVMの最適化の一つにメモリアクセスをなるべくレジスタアクセスに変更する最適化があります.

スタック上に変数を確保して,それを足し算する例は以下のようになります.

        let ty_void = llvm::core::LLVMVoidTypeInContext(context);
        let ty_function = llvm::core::LLVMFunctionType(ty_void, ptr::null_mut(), 0, 0);
        let ty_i64 = llvm::core::LLVMInt64TypeInContext(context);
        let function =
            llvm::core::LLVMAddFunction(module, b"hoge\0".as_ptr() as *const _, ty_function);

        let bb = llvm::core::LLVMAppendBasicBlockInContext(
            context,
            function,
            b"entry\0".as_ptr() as *const _, // label
        );
        llvm::core::LLVMPositionBuilderAtEnd(builder, bb);

        // スタック上に変数を作成
        let a = llvm::core::LLVMBuildAlloca(builder, ty_i64, b"A\0".as_ptr() as *const _);
        let x = llvm::core::LLVMBuildAlloca(builder, ty_i64, b"X\0".as_ptr() as *const _);
        let v = llvm::core::LLVMConstInt(ty_i64, 0, 1);
        llvm::core::LLVMBuildStore(builder, v, a);
        llvm::core::LLVMBuildStore(builder, v, x);
        let lhs = llvm::core::LLVMBuildLoad(builder, a, b"lhs\0".as_ptr() as *const _);
        let rhs = llvm::core::LLVMBuildLoad(builder, x, b"rhs\0".as_ptr() as *const _);

        // add命令
        llvm::core::LLVMBuildAdd(builder, lhs, rhs, b"tmp\0".as_ptr() as *const _);

        llvm::core::LLVMBuildRetVoid(builder);
; ModuleID = 'hoge'
source_filename = "hoge"

define void @hoge() {
entry:
  %A = alloca i64
  %X = alloca i64
  store i64 0, i64* %A
  store i64 0, i64* %X
  %lhs = load i64, i64* %A
  %rhs = load i64, i64* %X
  %tmp = add i64 %lhs, %rhs
  ret void
}

%がついてるものがレジスタの変数名です. ちなみに上のLLVM IRは以下のものと実質的に等価です(メモリアクセスを最適化するとこうなります).

define void @hoge() {
entry:
  %tmp = add i64 0, 0
  ret void
}

LLVM IRの検証

IR Builderを使って不正なLLVM IRを出力することは可能です(Basic Blockがterminater instructionで終了していないとか,命令の引数の型が異なるとか).moduleが正しいLLVM IRを保持しているかどうかはveirfierで検証できます.例えば,以下のようにします(戻り値が1の場合,エラーがあります).

    llvm::analysis::LLVMVerifyModule(
        module,
        llvm::analysis::LLVMVerifierFailureAction::LLVMPrintMessageAction,
        core::ptr::null_mut(),
    )

コード変換の戦略

ここまでIR生成の基礎をみてきました.ここまで来るとなんとなくどうやってIRを生成すべきかが分かってきます. 今回は以下のような単純な戦略でcBPFをLLVM IRに変換しようと思います.

  • cBPFの一命令を一つのBasic Blockに対応させて変換する
    • Basic Blockのラベル名は insn.1 のように連番を振る
    • こうすることでjump命令はただ単に対応するbasic blcok名を指定するだけでよくなる
  • レジスタA,X及びスタック領域のアクセスは全てload/sore命令でアクセスするようにする
    • こうすることでphi命令の使用を回避してIR出力を単純にする

基本的に後でLLVMが最適化してくれることを期待してなるべく楽をする方針でいきます.最適化してくれなかったらその時考えます.

変換処理

実際に作成したプログラムは ここ にあります.以下でいくつか主要点を説明しようと思います. ちなみにあまりテストしていないので問題がある可能性があります.cbpfに関してはここを見てみてください.

プロローグ処理の出力

cBPFのレジスタA,X及び作業用のメモリ領域は最初にalloca命令で確保することにしました. LLVMBuildArrayAlloca()で配列を確保することができます.

    fn emit_prolog(&mut self) {
        unsafe {
            // init A, X, MEM[BPF_INSN]
            let ty_i32 = llvm::core::LLVMInt32TypeInContext(self.context);
            let bb = llvm::core::LLVMAppendBasicBlockInContext(
                self.context,
                self.get_function("main"),
                cstr!("entry"),
            );
            llvm::core::LLVMPositionBuilderAtEnd(self.builder, bb);
            let a = llvm::core::LLVMBuildAlloca(self.builder, ty_i32, cstr!("A"));
            let x = llvm::core::LLVMBuildAlloca(self.builder, ty_i32, cstr!("X"));
            let memsize = llvm::core::LLVMConstInt(ty_i32, cbpf::opcode::BPF_MEMWORDS as _, 0);
            let mem = llvm::core::LLVMBuildArrayAlloca(self.builder, ty_i32, memsize, cstr!("MEM"));
            let v = llvm::core::LLVMConstInt(ty_i32, 0, 1);
            llvm::core::LLVMBuildStore(self.builder, v, a);
            llvm::core::LLVMBuildStore(self.builder, v, x);
            self.values.insert("A".to_owned(), a);
            self.values.insert("X".to_owned(), x);
            self.values.insert("MEM".to_owned(), mem);
        }
    }

外部関数とのリンク

LDWMSHなどの命令はLLVM IRで直接記述することが少々面倒だったので,最初にCで処理を書いてそれをclangでLLVM IRに変換した関数を呼び出すことにしました.このとき一般的には個別にプログラム(関数)を作成し,最後にリンク処理をいれると思いますが,ここでは簡単化のためにmain関数を作成直後に外部関数を読み込んでリンク(モジュールに取り込み)しています.エラー処理などを省いて主要点だけ記述すると以下のようになります.

static UTIL_CODE: &'static str = concat!(include_str!("./ll/util.ll"), "\0");


let buf = llvm::core::LLVMCreateMemoryBufferWithMemoryRange(
    UTIL_CODE.as_ptr() as *const _,
    (UTIL_CODE.len() - 1) as _, // exclude null terminator
    cstr!("util"),
    1,
);
let mut module: LLVMModuleRef = mem::uninitialized();
let mut err_msg: *mut i8 = mem::uninitialized();
let r =
    llvm::ir_reader::LLVMParseIRInContext(self.context, buf, &mut module, &mut err_msg);
// link util
llvm::linker::LLVMLinkModules2(self.module, module);

LLVMCreateMemoryBufferWithMemoryRange()でまずコードをバッファ上に確保して,それをLLVMParseIRInContextでパースします.LLVMLinkModules2()を使うことで読み込んだモジュールを第一引数のモジュールにリンク(マージ)することができます.ちなみにLLVMParseIRInContextで受け取るバッファはnull終端されていないと駄目なようです.

関数の呼び出しはLLVMBuildCall()を使います.

配列へのアセクス

配列へアクセスする場合にはgetelemntptr命令を使います. API的にはLLVMBuildInBoundGEP()などを使います.ストア処理は以下のようになっています.

n @ BPF_ST | n @ BPF_STX => unsafe {
    // mem[k] = a or x
    let idx = k;
    let p = llvm::core::LLVMBuildInBoundsGEP(
        self.builder,
        addr_mem,
        [idx].as_ptr() as *mut _,
        1,
        cstr!(),
    );
    let v = if n == BPF_ST { a } else { x };
    llvm::core::LLVMBuildStore(self.builder, v, p);
},

jmp命令

LLVMBuildCondBrを使います.第2引数がbook値, 第3引数と第4引数で条件が真のときと偽のときのbasic blockを渡すので,これが対応するbasic blockへのジャンプになるように変換します. 分岐の条件は基本的にicmp命令に対応したものがあるのでそれを直接使いますが,JSETだけはないのでANDをとってそれが0以上かどうかを比較しています.

let jt_bb = bbs[insn.jt as usize + idx + 1];
let jf_bb = bbs[insn.jf as usize + idx + 1];

let src = match bpf_src(insn.code) {
    BPF_K => k,
    BPF_X => x,
    _ => panic!("InvalidSrc"),
};

let cond = if bpf_op(insn.code) == BPF_JSET {
    // a & src > 0
    unsafe {
        let a = llvm::core::LLVMBuildAnd(self.builder, a, src, cstr!());
        let zero = llvm::core::LLVMConstInt(ty_i32, 0, 1);
        llvm::core::LLVMBuildICmp(
            self.builder,
            llvm::LLVMIntPredicate::LLVMIntSGT,
            a,
            zero,
            cstr!(),
        )
    }
} else {
    let pred = match bpf_op(insn.code) {
        BPF_JGT => llvm::LLVMIntPredicate::LLVMIntSGT,
        BPF_JGE => llvm::LLVMIntPredicate::LLVMIntSGE,
        BPF_JEQ => llvm::LLVMIntPredicate::LLVMIntEQ,
        _ => panic!("InvalidJmpCondition"),
    };

    unsafe { llvm::core::LLVMBuildICmp(self.builder, pred, a, src, cstr!()) }
};
unsafe {
    llvm::core::LLVMBuildCondBr(self.builder, cond, jt_bb, jf_bb);
}

jitによる実行

LLVMLLVM IRを実行するためのjitを備えています.以下のようにしてLLVM IRをjitで実行することが可能です.

            llvm::execution_engine::LLVMLinkInMCJIT();
            let mut engine: LLVMExecutionEngineRef = mem::uninitialized();
            let mut err_msg: *mut i8 = mem::uninitialized();
            let mut options: LLVMMCJITCompilerOptions = mem::uninitialized();
            let options_size = mem::size_of::<LLVMMCJITCompilerOptions>();
            llvm::execution_engine::LLVMInitializeMCJITCompilerOptions(&mut options, options_size);
            options.OptLevel = 0;
            let result_code = llvm::execution_engine::LLVMCreateMCJITCompilerForModule(
                &mut engine,
                self.module,
                &mut options,
                options_size,
                &mut err_msg,
            );
            if result_code != 0 {
                return Err(
                    std::ffi::CStr::from_ptr(err_msg)
                        .to_string_lossy()
                        .into_owned(),
                );
            }

            type Func = extern "C" fn(*mut u8) -> i32;
            let func_addr = llvm::execution_engine::LLVMGetFunctionAddress(engine, cstr!("main"));
            let func: Func = mem::transmute(func_addr);

            // func(&[1,2,3]) みたいに呼び出せる

最適化

ここまででcBPFプログラムをLLVM IRに変換し,それをjitで実行することができますが今のままではeBPFにコンパイルすることはできません.なぜなら,ldwなどの命令は関数呼び出しに置き換えて処理しましたが,eBPFは通常の関数呼び出しをサポートしてないからです(BPF_CALL命令を使って事前に定義した関数を呼び出すことは可能です).そこで単純にldwなどの関数呼び出しをインライン化して対応します.

実際に最適化する際はLLVMの処理単位であるPassを追加する訳ですが,Passが大量にあってなかなか分かりにくいです.ここでは merthcの最適化のコードを参考にしました.

        unsafe {
            // Per clang and rustc, we want to use both kinds.
            let fpm = llvm::core::LLVMCreateFunctionPassManagerForModule(self.module);
            let mpm = llvm::core::LLVMCreatePassManager();

            // Populate the pass managers with passes
            let pmb = LLVMPassManagerBuilderCreate();
            LLVMPassManagerBuilderSetOptLevel(pmb, 2);
            // Magic threshold from Clang for -O2
            LLVMPassManagerBuilderUseInlinerWithThreshold(pmb, 1024);
            LLVMPassManagerBuilderPopulateModulePassManager(pmb, mpm);
            LLVMPassManagerBuilderPopulateFunctionPassManager(pmb, fpm);
            LLVMPassManagerBuilderDispose(pmb);

            // Iterate over functions, running the FPM over each
            llvm::core::LLVMInitializeFunctionPassManager(fpm);
            let mut func = llvm::core::LLVMGetFirstFunction(self.module);
            while func != ptr::null_mut() {
                llvm::core::LLVMRunFunctionPassManager(fpm, func);
                func = llvm::core::LLVMGetNextFunction(func);
            }
            llvm::core::LLVMFinalizeFunctionPassManager(fpm);

            // Run the MPM over the module
            llvm::core::LLVMRunPassManager(mpm, self.module);

            // Clean up managers
            llvm::core::LLVMDisposePassManager(fpm);
            llvm::core::LLVMDisposePassManager(mpm);
        }
    }

LLVMPassManagerBulderSetOptLevel(pmd, 2)とすることで -O2相当の最適化を実行します.また,インライン化するためにLLVMPassManagerBuilderUseInlineWithThreshold()を読んでいます.LLVMは何らかの閾値でinline化をする訳ですが,とりあえずここでは1024にしました.

LTO

上記の最適化で関数のinline化がされますが,このままではまだldwなどの関数の定義が残っています.そこでLink Time Optimizationでそれらの関数を除去します.このためにLTOを実行する前にldwなどの関数をprivateにしてどこからも参照されないことを保証します.これによりLTOを実行するとそれらの関数が除去されます.

    fn optimize_lto(&self) {
        use llvm::transforms::pass_manager_builder::*;
        unsafe {
            // mark all functions but main (and llvm intrinsics) as private to remove
            for k in self.functions.keys() {
                if k != "main" {
                    llvm::core::LLVMSetLinkage(
                        self.get_function(k),
                        llvm::LLVMLinkage::LLVMPrivateLinkage,
                    );
                }
            }
        }

        unsafe {
            let pm = llvm::core::LLVMCreatePassManager();
            let pmb = LLVMPassManagerBuilderCreate();
            LLVMPassManagerBuilderPopulateLTOPassManager(
                pmb,
                pm,
                1, // Internalize
                1,
            ); // Run inliner
            LLVMPassManagerBuilderDispose(pmb);

            llvm::core::LLVMRunPassManager(pm, self.module);
            llvm::core::LLVMDisposePassManager(pm);
        }
    }

実行例: eBPFへのコンパイル

これでようやくeBPFへコンパイルすることができます. 作成した変換コードをもとにcbpf2irというプログラムを作成しました.libpcapのフィルタ式からcBPFプログラムを生成し,それをLLVM IRへと変換します. 以下のようにして実行できます.

cargo run --bin cbpf2ir -- -o a.ll "tcp port 80 and (((ip[2:2] - ((ip[0]&0xf)<<2)) - ((tcp[12]&0xf0)>>2)) != 0)"

cBPFプログラム:

LD H ABS   {code: 28, jt: 00, jf: 00, k: 0000000C}  ldh [12]
JEQ K      {code: 15, jt: 00, jf: 06, k: 000086DD}  jeq 34525 0 6
LD B ABS   {code: 30, jt: 00, jf: 00, k: 00000014}  ldb [20]
JEQ K      {code: 15, jt: 00, jf: 04, k: 00000006}  jeq 6 0 4
LD H ABS   {code: 28, jt: 00, jf: 00, k: 00000036}  ldh [54]
JEQ K      {code: 15, jt: 0E, jf: 00, k: 00000050}  jeq 80 14 0
LD H ABS   {code: 28, jt: 00, jf: 00, k: 00000038}  ldh [56]
JEQ K      {code: 15, jt: 0C, jf: 00, k: 00000050}  jeq 80 12 0
LD H ABS   {code: 28, jt: 00, jf: 00, k: 0000000C}  ldh [12]
JEQ K      {code: 15, jt: 00, jf: 45, k: 00000800}  jeq 2048 0 69
LD B ABS   {code: 30, jt: 00, jf: 00, k: 00000017}  ldb [23]
JEQ K      {code: 15, jt: 00, jf: 43, k: 00000006}  jeq 6 0 67
LD H ABS   {code: 28, jt: 00, jf: 00, k: 00000014}  ldh [20]
JSET K     {code: 45, jt: 41, jf: 00, k: 00001FFF}  jset 8191 65 0
LDX B MSH  {code: B1, jt: 00, jf: 00, k: 0000000E}  ldxb ([14] & 0xf) << 2
LD H IND   {code: 48, jt: 00, jf: 00, k: 0000000E}  ldh [14+X]
JEQ K      {code: 15, jt: 03, jf: 00, k: 00000050}  jeq 80 3 0
LDX B MSH  {code: B1, jt: 00, jf: 00, k: 0000000E}  ldxb ([14] & 0xf) << 2
LD H IND   {code: 48, jt: 00, jf: 00, k: 00000010}  ldh [16+X]
JEQ K      {code: 15, jt: 00, jf: 3B, k: 00000050}  jeq 80 0 59
LD H ABS   {code: 28, jt: 00, jf: 00, k: 0000000C}  ldh [12]
JEQ K      {code: 15, jt: 00, jf: 39, k: 00000800}  jeq 2048 0 57
LD IMM     {code: 00, jt: 00, jf: 00, k: 00000002}  ldw 2
ST         {code: 02, jt: 00, jf: 00, k: 00000000}  st MEM[0]
LDX MEM    {code: 61, jt: 00, jf: 00, k: 00000000}  ldxw MEM[0]
LD H IND   {code: 48, jt: 00, jf: 00, k: 0000000E}  ldh [14+X]
ST         {code: 02, jt: 00, jf: 00, k: 00000001}  st MEM[1]
LD IMM     {code: 00, jt: 00, jf: 00, k: 00000000}  ldw 0
ST         {code: 02, jt: 00, jf: 00, k: 00000002}  st MEM[2]
LDX MEM    {code: 61, jt: 00, jf: 00, k: 00000002}  ldxw MEM[2]
LD B IND   {code: 50, jt: 00, jf: 00, k: 0000000E}  ldb [14+X]
ST         {code: 02, jt: 00, jf: 00, k: 00000003}  st MEM[3]
LD IMM     {code: 00, jt: 00, jf: 00, k: 0000000F}  ldw 15
ST         {code: 02, jt: 00, jf: 00, k: 00000004}  st MEM[4]
LDX MEM    {code: 61, jt: 00, jf: 00, k: 00000004}  ldxw MEM[4]
LD MEM     {code: 60, jt: 00, jf: 00, k: 00000003}  ldw MEM[3]
AND X      {code: 5C, jt: 00, jf: 00, k: 00000000}  and X
ST         {code: 02, jt: 00, jf: 00, k: 00000004}  st MEM[4]
LD IMM     {code: 00, jt: 00, jf: 00, k: 00000002}  ldw 2
ST         {code: 02, jt: 00, jf: 00, k: 00000005}  st MEM[5]
LDX MEM    {code: 61, jt: 00, jf: 00, k: 00000005}  ldxw MEM[5]
LD MEM     {code: 60, jt: 00, jf: 00, k: 00000004}  ldw MEM[4]
LSH X      {code: 6C, jt: 00, jf: 00, k: 00000000}  lsh X
ST         {code: 02, jt: 00, jf: 00, k: 00000005}  st MEM[5]
LDX MEM    {code: 61, jt: 00, jf: 00, k: 00000005}  ldxw MEM[5]
LD MEM     {code: 60, jt: 00, jf: 00, k: 00000001}  ldw MEM[1]
SUB X      {code: 1C, jt: 00, jf: 00, k: 00000000}  sub X
ST         {code: 02, jt: 00, jf: 00, k: 00000005}  st MEM[5]
LD IMM     {code: 00, jt: 00, jf: 00, k: 0000000C}  ldw 12
ST         {code: 02, jt: 00, jf: 00, k: 00000006}  st MEM[6]
LDX B MSH  {code: B1, jt: 00, jf: 00, k: 0000000E}  ldxb ([14] & 0xf) << 2
LD MEM     {code: 60, jt: 00, jf: 00, k: 00000006}  ldw MEM[6]
ADD X      {code: 0C, jt: 00, jf: 00, k: 00000000}  add X
TAX        {code: 07, jt: 00, jf: 00, k: 00000000}  tax
LD B IND   {code: 50, jt: 00, jf: 00, k: 0000000E}  ldb [14+X]
ST         {code: 02, jt: 00, jf: 00, k: 00000007}  st MEM[7]
LD IMM     {code: 00, jt: 00, jf: 00, k: 000000F0}  ldw 240
ST         {code: 02, jt: 00, jf: 00, k: 00000008}  st MEM[8]
LDX MEM    {code: 61, jt: 00, jf: 00, k: 00000008}  ldxw MEM[8]
LD MEM     {code: 60, jt: 00, jf: 00, k: 00000007}  ldw MEM[7]
AND X      {code: 5C, jt: 00, jf: 00, k: 00000000}  and X
ST         {code: 02, jt: 00, jf: 00, k: 00000008}  st MEM[8]
LD IMM     {code: 00, jt: 00, jf: 00, k: 00000002}  ldw 2
ST         {code: 02, jt: 00, jf: 00, k: 00000009}  st MEM[9]
LDX MEM    {code: 61, jt: 00, jf: 00, k: 00000009}  ldxw MEM[9]
LD MEM     {code: 60, jt: 00, jf: 00, k: 00000008}  ldw MEM[8]
RSH X      {code: 7C, jt: 00, jf: 00, k: 00000000}  rsh X
ST         {code: 02, jt: 00, jf: 00, k: 00000009}  st MEM[9]
LDX MEM    {code: 61, jt: 00, jf: 00, k: 00000009}  ldxw MEM[9]
LD MEM     {code: 60, jt: 00, jf: 00, k: 00000005}  ldw MEM[5]
SUB X      {code: 1C, jt: 00, jf: 00, k: 00000000}  sub X
ST         {code: 02, jt: 00, jf: 00, k: 00000009}  st MEM[9]
LD IMM     {code: 00, jt: 00, jf: 00, k: 00000000}  ldw 0
ST         {code: 02, jt: 00, jf: 00, k: 0000000A}  st MEM[10]
LDX MEM    {code: 61, jt: 00, jf: 00, k: 0000000A}  ldxw MEM[10]
LD MEM     {code: 60, jt: 00, jf: 00, k: 00000009}  ldw MEM[9]
SUB X      {code: 1C, jt: 00, jf: 00, k: 00000000}  sub X
JEQ K      {code: 15, jt: 01, jf: 00, k: 00000000}  jeq 0 1 0
RET K      {code: 06, jt: 00, jf: 00, k: 0000FFFF}  ret 65535
RET K      {code: 06, jt: 00, jf: 00, k: 00000000}  ret 0

LLVM IR (最適化後)

LLVM IR:
; ModuleID = 'cbpf_ir'
source_filename = "cbpf_ir"

; Function Attrs: norecurse nounwind readonly
define i32 @main(i8* nocapture readonly) local_unnamed_addr #0 {
entry:
  %1 = getelementptr inbounds i8, i8* %0, i64 12
  %2 = load i8, i8* %1, align 1
  %3 = zext i8 %2 to i32
  %4 = shl nuw nsw i32 %3, 8
  %5 = getelementptr inbounds i8, i8* %0, i64 13
  %6 = load i8, i8* %5, align 1
  %7 = zext i8 %6 to i32
  %8 = or i32 %4, %7
  %cond = icmp eq i32 %8, 2048
  br i1 %cond, label %insn.10, label %insn.79

insn.10:                                          ; preds = %entry
  %9 = getelementptr inbounds i8, i8* %0, i64 23
  %10 = load i8, i8* %9, align 1
  %11 = icmp eq i8 %10, 6
  br i1 %11, label %insn.12, label %insn.79

insn.12:                                          ; preds = %insn.10
  %12 = getelementptr inbounds i8, i8* %0, i64 20
  %13 = load i8, i8* %12, align 1
  %14 = zext i8 %13 to i32
  %15 = shl nuw nsw i32 %14, 8
  %16 = getelementptr inbounds i8, i8* %0, i64 21
  %17 = load i8, i8* %16, align 1
  %18 = zext i8 %17 to i32
  %.masked = and i32 %15, 7936
  %19 = or i32 %.masked, %18
  %20 = icmp eq i32 %19, 0
  br i1 %20, label %insn.14, label %insn.79

insn.14:                                          ; preds = %insn.12
  %21 = getelementptr inbounds i8, i8* %0, i64 14
  %22 = load i8, i8* %21, align 1
  %23 = zext i8 %22 to i32
  %24 = shl nuw nsw i32 %23, 2
  %25 = and i32 %24, 60
  %26 = add nuw nsw i32 %25, 14
  %27 = zext i32 %26 to i64
  %28 = getelementptr inbounds i8, i8* %0, i64 %27
  %29 = load i8, i8* %28, align 1
  %30 = zext i8 %29 to i32
  %31 = shl nuw nsw i32 %30, 8
  %32 = getelementptr inbounds i8, i8* %28, i64 1
  %33 = load i8, i8* %32, align 1
  %34 = zext i8 %33 to i32
  %35 = or i32 %31, %34
  %36 = icmp eq i32 %35, 80
  br i1 %36, label %insn.22, label %insn.17

insn.17:                                          ; preds = %insn.14
  %37 = add nuw nsw i32 %25, 16
  %38 = zext i32 %37 to i64
  %39 = getelementptr inbounds i8, i8* %0, i64 %38
  %40 = load i8, i8* %39, align 1
  %41 = zext i8 %40 to i32
  %42 = shl nuw nsw i32 %41, 8
  %43 = getelementptr inbounds i8, i8* %39, i64 1
  %44 = load i8, i8* %43, align 1
  %45 = zext i8 %44 to i32
  %46 = or i32 %42, %45
  %47 = icmp eq i32 %46, 80
  br i1 %47, label %insn.22, label %insn.79

insn.22:                                          ; preds = %insn.17, %insn.14
  %48 = getelementptr inbounds i8, i8* %0, i64 16
  %49 = load i8, i8* %48, align 1
  %50 = zext i8 %49 to i32
  %51 = shl nuw nsw i32 %50, 8
  %52 = getelementptr inbounds i8, i8* %0, i64 17
  %53 = load i8, i8* %52, align 1
  %54 = zext i8 %53 to i32
  %55 = or i32 %51, %54
  %56 = sub nsw i32 %55, %25
  %57 = add nuw nsw i32 %25, 26
  %58 = zext i32 %57 to i64
  %59 = getelementptr inbounds i8, i8* %0, i64 %58
  %60 = load i8, i8* %59, align 1
  %61 = and i8 %60, -16
  %62 = zext i8 %61 to i32
  %63 = lshr exact i32 %62, 2
  %64 = icmp eq i32 %56, %63
  br i1 %64, label %insn.79, label %insn.78

insn.78:                                          ; preds = %insn.79, %insn.22
  %merge = phi i32 [ 65535, %insn.22 ], [ 0, %insn.79 ]
  ret i32 %merge

insn.79:                                          ; preds = %entry, %insn.12, %insn.22, %insn.17, %insn.10
  br label %insn.78
}

; Function Attrs: nounwind readnone
define i32 @be(i32) local_unnamed_addr #1 {
  %2 = tail call i32 @llvm.bswap.i32(i32 %0)
  ret i32 %2
}

; Function Attrs: nounwind readnone speculatable
declare i32 @llvm.bswap.i32(i32) #2

attributes #0 = { norecurse nounwind readonly }
attributes #1 = { nounwind readnone }
attributes #2 = { nounwind readnone speculatable }

ちなみに最適化前のコードはこちら. 最適化によってずいぶんすっきりしました.無駄なロードやストアが全て無くなり,phi命令を使うように変換されています. 何故かLTOを通してもどこからも呼ばれていないbe()が残ってしまっていますが...これでもeBPFにはコンパイルできました.

CFGで表すとこうなります (opt a.ll -dot-cfg && dot -Tpng cfg.main.dot -o a.png)

f:id:mm_i:20171009172225p:plain

なんとなくそれっぽいのが出来ているような気がします(画像が勝手に圧縮されてしまう..).

eBPFへのコンパイル

% llc -march=bpf -o a.bpf a.ll
        .text
        .macosx_version_min 10, 12
        .globl  main                    # -- Begin function main
        .p2align        3
main:                                   # @main
# BB#0:                                 # %entry
        r2 = *(u8 *)(r1 + 13)
        r3 = *(u8 *)(r1 + 12)
        r3 <<= 8
        r3 |= r2
        if r3 != 2048 goto LBB0_7
# BB#1:                                 # %insn.10
        r2 = *(u8 *)(r1 + 23)
        if r2 != 6 goto LBB0_7
# BB#2:                                 # %insn.12
        r2 = *(u8 *)(r1 + 21)
        r3 = *(u8 *)(r1 + 20)
        r3 <<= 8
        r3 &= 7936
        r3 |= r2
        if r3 != 0 goto LBB0_7
# BB#3:                                 # %insn.14
        r2 = *(u8 *)(r1 + 14)
        r2 <<= 2
        r2 &= 60
        r3 = r1
        r3 += r2
        r4 = *(u8 *)(r3 + 15)
        r3 = *(u8 *)(r3 + 14)
        r3 <<= 8
        r3 |= r4
        if r3 == 80 goto LBB0_5
# BB#4:                                 # %insn.17
        r3 = r2
        r3 <<= 32
        r3 >>= 32
        r4 = r1
        r4 += r3
        r3 = *(u8 *)(r4 + 17)
        r4 = *(u8 *)(r4 + 16)
        r4 <<= 8
        r4 |= r3
        if r4 != 80 goto LBB0_7
LBB0_5:                                 # %insn.22
        r3 = *(u8 *)(r1 + 16)
        r3 <<= 8
        r4 = *(u8 *)(r1 + 17)
        r3 |= r4
        r3 -= r2
        r2 <<= 32
        r2 >>= 32
        r1 += r2
        r0 = 65535
        r1 = *(u8 *)(r1 + 26)
        r1 &= 240
        r1 >>= 2
        if r3 == r1 goto LBB0_7
LBB0_6:                                 # %insn.78
        exit
LBB0_7:                                 # %insn.79
        r0 = 0
        goto LBB0_6
                                        # -- End function

elfバイナリを出力する場合は以下のようにします.

% llc -filetype=obj -march=bpf -o a.bpf a.ll

elfバイナリからmain関数だけを抽出したい場合はobjcopyが利用できます.

% x86_64-elf-objcopy -O binary a.bpf a.bin
% python2 ~/ubpf/bin/ubpf-disassembler a.bin a.s
% cat a.s
ldxb r2, [r1+13]
ldxb r3, [r1+12]
lsh r3, 0x8
or r3, r2
jne r3, 0x800, +42
ldxb r2, [r1+23]
jne r2, 0x6, +40
ldxb r2, [r1+21]
ldxb r3, [r1+20]
lsh r3, 0x8
and r3, 0x1f00
or r3, r2
jne r3, 0x0, +34
ldxb r2, [r1+14]
lsh r2, 0x2
and r2, 0x3c
mov r3, r1
add r3, r2
ldxb r4, [r3+15]
ldxb r3, [r3+14]
lsh r3, 0x8
or r3, r4
jeq r3, 0x50, +10
mov r3, r2
lsh r3, 0x20
rsh r3, 0x20
mov r4, r1
add r4, r3
ldxb r3, [r4+17]
ldxb r4, [r4+16]
lsh r4, 0x8
or r4, r3
jne r4, 0x50, +14
ldxb r3, [r1+16]
lsh r3, 0x8
ldxb r4, [r1+17]
or r3, r4
sub r3, r2
lsh r2, 0x20
rsh r2, 0x20
add r1, r2
mov r0, 0xffff
ldxb r1, [r1+26]
and r1, 0xf0
rsh r1, 0x2
jeq r3, r1, +1
exit
mov r0, 0x0
ja -3

最後のdisassemblerはubpfのものです.

ということでこんな感じで変換できました.といっても変換したものが本当に正しいのかまだ検証してないですが..

まとめ

cBPFをLLVM IRに変換してみました.最初はとっつきにくい印象のLLVMもやってみると分かっ(たような気がし)てくるのでやってみるのが大事ですね.

*1:これはLLVM IRではなくてRISC likeなBAP Instruction Languageに変換

*2:githubにもリポジトリがありますが,bitbucketの方が最新版です

*3:いずれもllvm-sysがベース

LinuxのBPF : (5) eBPFによるLinux Kernel Tracing

eBPFによるカーネルトレース

一番最初に書いた通り,eBPFはLinuxのトレーサとして利用できます.

カーネルがeBPFプログラムを実行する場合,BPFインタプリタctxが渡されます(jit化されている場合も同様です).

https://github.com/torvalds/linux/blob/v4.12/kernel/bpf/core.c#L766

/* Named registers */
...
#define ARG1   regs[BPF_REG_ARG1]   // これは BPF_REG_R1
...

static unsigned int __bpf_prog_run(void *ctx, const struct bpf_insn *insn)
{
    ...
    ARG1 = (u64) (unsigned long) ctx;
    ...
    // インタプリタによる処理の実行

このctxはeBPFプログラムをどこにアタッチするかで異なります. BPFでパケットフィルタリングをする際は,パケットの受信or送信のタイミングでctxとしてskbuffのポインタが渡されてeBPFプログラムが実行されていました.

この構造を応用して,カーネル内の様々なイベントに対して,ユーザが作成したeBPFプログラムを適当なctxの下で実行することでトレースを実現します.

eBPF Program Type

eBPFプログラムの種類は,eBPF Program Typeで区別されます.このProgram TypeはbpfシステムコールでeBPFプログラムをロードする際に指定します.

Linux 4.12時点では以下のようなProgram Typeが存在します.

https://github.com/torvalds/linux/blob/v4.12/include/trace/events/bpf.h#L12

#define __PROG_TYPE_MAP(FN) \
   FN(SOCKET_FILTER)   \
   FN(KPROBE)      \
   FN(SCHED_CLS)       \
   FN(SCHED_ACT)       \
   FN(TRACEPOINT)      \
   FN(XDP)         \
   FN(PERF_EVENT)      \
   FN(CGROUP_SKB)      \
   FN(CGROUP_SOCK)     \
   FN(LWT_IN)      \
   FN(LWT_OUT)     \
   FN(LWT_XMIT)

今までSOCKET_FILTERとしてのeBPFをずっと見てきた訳ですが,実際にはこれだけの種類があります. どの用途としてeBPFプログラムを作成するかによって,eBPFプログラムの引数や,eBPFプログラムの戻り値の意味,eBPFプログラムから呼ぶことが可能なカーネル内の関数,さらにはeBPFプログラム作成のために使えるライブラリの種類も変わってきます.

特にカーネルトレース機能としてのeBPFを考える場合,kprobe, tracepoint, perf_event あたりが重要になります. kprobeやperfは元々eBPF以前からカーネルに存在したトレーシング機能ですが,それらの様々なフックポイントに対してeBPFプログラムがアタッチできるようになっています.

ちなみに,カーネルのどのバージョンでBPFのどの機能がサポートされているかというのは,以下のbccの資料がまとまっています. https://github.com/iovisor/bcc/blob/master/docs/kernel-versions.md

bccのトレースツール群

前回簡単に説明したbccには様々なトレーシングツールがデフォルトで含まれています

これらのツールで何がトレースできるのかというのは,以下のbccの図にまとまっています.

f:id:mm_i:20170904231602p:plain

公式のチュートリアルに一部のみですが機能の説明があります. おそらく,今後もツール群は増えていくものと思われます.

bccでkprobeを利用したトレースの例

bccでトレースプログラムを書く際は,以下の資料が参考になります.

実際にトレースプログラムを書く際は,bccのツール群の中で自分の目的にもっとも近いものを参考にするのがいいかと思います.

例えば,uprobeを利用してあるPIDのプロセスを監視し,strlen()を呼び出したときの文字列を表示するプログラムは以下のようになります.

https://github.com/iovisor/bcc/blob/master/examples/tracing/strlen_snoop.py

#!/usr/bin/python
#
# strlen_snoop  Trace strlen() library function for a given PID.
#               For Linux, uses BCC, eBPF. Embedded C.
#
# USAGE: strlensnoop PID
#
# Try running this on a separate bash shell.
#
# Written as a basic example of BCC and uprobes.
#
# Copyright 2016 Netflix, Inc.
# Licensed under the Apache License, Version 2.0 (the "License")

from __future__ import print_function
from bcc import BPF
from os import getpid
import sys

if len(sys.argv) < 2:
    print("USAGE: strlensnoop PID")
    exit()
pid = sys.argv[1]

# load BPF program
bpf_text = """
#include <uapi/linux/ptrace.h>
int printarg(struct pt_regs *ctx) {
    if (!PT_REGS_PARM1(ctx))
        return 0;
    u32 pid = bpf_get_current_pid_tgid();
    if (pid != PID)
        return 0;
    char str[80] = {};
    bpf_probe_read(&str, sizeof(str), (void *)PT_REGS_PARM1(ctx));
    bpf_trace_printk("%s\\n", &str);
    return 0;
};
"""
bpf_text = bpf_text.replace('PID', pid)
b = BPF(text=bpf_text)
b.attach_uprobe(name="c", sym="strlen", fn_name="printarg")

# header
print("%-18s %-16s %-6s %s" % ("TIME(s)", "COMM", "PID", "STRLEN"))

# format output
me = getpid()
while 1:
    try:
        (task, pid, cpu, flags, ts, msg) = b.trace_fields()
    except ValueError:
        continue
    if pid == me or msg == "":
        continue
    print("%-18.9f %-16s %-6d %s" % (ts, task, pid, msg))

b.attach_uprobe(name="c", sym="strlen", fn_name="printarg")strlen()が呼ばれたときにprintarg()を実行するようになります.uprobeのctxから関数の引数にアクセスすることができます.printarg()の中でbpf_probe_read()を使ってstrlenの引数の文字列をスタックにコピーし,bpf_trace_printk()を使ってそれを/sys/kernel/debug/tracing/trace_pipe出力します.ユーザランドのプログラム側でtrace_fields()をすることによってそれを読み出して出力しています(ここではconcurrentな利用は考えてないです).簡単ですね.bccで使える関数の詳細はreference guideをみてください.

他にも,kprobeを利用してblock deviceのI/Oのトレースするプログラムは以下のようになっています.

https://github.com/iovisor/bcc/blob/master/examples/tracing/disksnoop.py

b = BPF(text="""
#include <uapi/linux/ptrace.h>
#include <linux/blkdev.h>
BPF_HASH(start, struct request *);
void trace_start(struct pt_regs *ctx, struct request *req) {
  // stash start timestamp by request ptr
  u64 ts = bpf_ktime_get_ns();
  start.update(&req, &ts);
}
void trace_completion(struct pt_regs *ctx, struct request *req) {
  u64 *tsp, delta;
  tsp = start.lookup(&req);
  if (tsp != 0) {
      delta = bpf_ktime_get_ns() - *tsp;
      bpf_trace_printk("%d %x %d\\n", req->__data_len,
          req->cmd_flags, delta / 1000);
      start.delete(&req);
  }
}
""")

b.attach_kprobe(event="blk_start_request", fn_name="trace_start")
b.attach_kprobe(event="blk_mq_start_request", fn_name="trace_start")
b.attach_kprobe(event="blk_account_io_completion", fn_name="trace_completion")

ここではeBPF mapを利用して,block deviceの開始したときに開始時刻を保存,終了時にそれを読み出して出力しています.

他にもいろんなことができるので,いろいろと遊んでみると楽しいと思います.

ちなみにbccでプログラムを書く際は

  • bccはプログラムをeBPFにコンパイルする前に clang/llvm の力によってプログラムを書き換えて正しいeBPFプログラムになるようにしている

という点を知っておくといろいろと納得しやすいと思います.何故bccのプログラムで正しいeBPFプログラムが出力されるのかを追いかけると深みにはまります.

LinuxのBPF : (4) ClangによるeBPFプログラムの作成と,BPF Compiler Collection (BCC)

Clangを利用したeBPFプログラムの作成

前回はeBPFプログラムをstruct bpf_insnの配列として直接書きましたが,あまりにも面倒です. cBPFの場合はtcpdump (libpcap)を使うことができました. llvm3.7よりeBPFのバックエンドが追加されました.したがって,clangを利用してC言語のプログラムをeBPFプログラムにコンパイルすることが可能です.

eBPFへのコンパイル

例えば,以下のようなCプログラムを考えます.

int f(int x){
    return x+1;
}

-target bpfを指定することでeBPFのプログラムにコンパイルすることが可能です.

llvm IRの出力

clang -c -S -emit-llvm a.c
; ModuleID = 'a.c'
source_filename = "a.c"
target datalayout = "e-m:e-p:64:64-i64:64-n32:64-S128"
target triple = "bpf"

; Function Attrs: noinline nounwind
define i32 @f(i32) #0 {
  %2 = alloca i32, align 4
  store i32 %0, i32* %2, align 4
  %3 = load i32, i32* %2, align 4
  %4 = add nsw i32 %3, 1
  ret i32 %4
}

attributes #0 = { noinline nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.ident = !{!0}

!0 = !{!"clang version 4.0.1 (tags/RELEASE_401/final)"}

eBPFアセンブリの出力

clang -c -S -target bpf a.c
 .text
    .globl    f
    .p2align  3
f:                                      # @f
# BB#0:
    *(u32 *)(r10 - 4) = r1
    r2 = r1
    r1 += 1
    r0 = r1
    *(u64 *)(r10 - 16) = r2
    exit

eBPFプログラムの出力

clang -c -target bpf a.c

この場合,ELFバイナリが出力されます.

% objdump -x a.o

a.o:     file format elf64-little
a.o
architecture: UNKNOWN!, flags 0x00000010:
HAS_SYMS
start address 0x0000000000000000

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  0 .text         00000030  0000000000000000  0000000000000000  00000040  2**3
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
SYMBOL TABLE:
0000000000000000 g       .text  0000000000000000 f


% readelf -x .text a.o

Hex dump of section '.text':
  0x00000000 631afcff 00000000 bf120000 00000000 c...............
  0x00000010 07010000 01000000 bf100000 00000000 ................
  0x00000020 7b2af0ff 00000000 95000000 00000000 {*..............

ELFバイナリからeBPFプログラムだけを抽出したい場合は,以下のようにします.

objcopy -I elf64-little -O binary a.o a.bin

また,ubpfにdisassemblerがあります

% ./ubpf-disassembler a.bin a.s
% cat a.s
stxw [r10-4], r1
mov r2, r1
add r1, 0x1
mov r0, r1
stxdw [r10-16], r2
exit

このようにしてeBPFのプログラムが作成できますが,実際にカーネル内で動作できるプログラムを作成するにはいくつか注意が必要になります.

カーネルで動作するeBPFプログラムの例

カーネルsamples/bpf以下にC言語で書かれたeBPFの例がいくつかあります.IPの上位プロトコロル別に外向きのパケットバイト数をカウントするCのプログラムが,sockex1_kern.c及びsockex1_user.cです.

https://github.com/torvalds/linux/blob/v4.12/samples/bpf/sockex1_kern.c (eBPFプログラム)

#include <uapi/linux/bpf.h>
#include <uapi/linux/if_ether.h>
#include <uapi/linux/if_packet.h>
#include <uapi/linux/ip.h>
#include "bpf_helpers.h"

struct bpf_map_def SEC("maps") my_map = {
    .type = BPF_MAP_TYPE_ARRAY,
    .key_size = sizeof(u32),
    .value_size = sizeof(long),
    .max_entries = 256,
};

SEC("socket1")
int bpf_prog1(struct __sk_buff *skb)
{
    int index = load_byte(skb, ETH_HLEN + offsetof(struct iphdr, protocol));
    long *value;

    if (skb->pkt_type != PACKET_OUTGOING)
        return 0;

    value = bpf_map_lookup_elem(&my_map, &index);
    if (value)
        __sync_fetch_and_add(value, skb->len);

    return 0;
}

https://github.com/torvalds/linux/blob/v4.12/samples/bpf/sockex1_user.c

#include <stdio.h>
#include <assert.h>
#include <linux/bpf.h>
#include "libbpf.h"
#include "bpf_load.h"
#include "sock_example.h"
#include <unistd.h>
#include <arpa/inet.h>

int main(int ac, char **argv)
{
    char filename[256];
    FILE *f;
    int i, sock;

    snprintf(filename, sizeof(filename), "%s_kern.o", argv[0]);

    if (load_bpf_file(filename)) {
        printf("%s", bpf_log_buf);
        return 1;
    }

    sock = open_raw_sock("lo");

    assert(setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, prog_fd,
              sizeof(prog_fd[0])) == 0);

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

    for (i = 0; i < 5; i++) {
        long long tcp_cnt, udp_cnt, icmp_cnt;
        int key;

        key = IPPROTO_TCP;
        assert(bpf_map_lookup_elem(map_fd[0], &key, &tcp_cnt) == 0);

        key = IPPROTO_UDP;
        assert(bpf_map_lookup_elem(map_fd[0], &key, &udp_cnt) == 0);

        key = IPPROTO_ICMP;
        assert(bpf_map_lookup_elem(map_fd[0], &key, &icmp_cnt) == 0);

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

    return 0;
}

このプログラムはカーネルソースのルートでmake headers_installとしたのち,samples/bpfmakeすればコンパイルできると思います(要clang/llc). load_bpf_file()はelfからeBPFプログラムを呼びだす関数です.

コードを見ればやっていることはなんとなく分かると思いますが,何故このプログラムがちゃんと動作するかは少々複雑です.

前回示したeBPFのプログラムは以下のようになっていました.

        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(),

特に重要なポイントとしては,

  • BPF_LD_ABSskbuffからデータを読み出す特別な命令で,R6レジスタskbuffのポインタを格納する必要がある
  • BPF_FUNC_map_lookup_elem を呼び出す前に,R1レジスタにeBPF mapのdescriptorを格納する

の2点です.

skbuffからのロード

まず,skbuffからのデータのロードに関して,Cでは以下のようになっています.

 int index = load_byte(skb, ETH_HLEN + offsetof(struct iphdr, protocol));

ここで,load_byte()bpf_helpers.hで定義されています.

/* llvm builtin functions that eBPF C program may use to
 * emit BPF_LD_ABS and BPF_LD_IND instructions
 */
struct sk_buff;
unsigned long long load_byte(void *skb,
                 unsigned long long off) asm("llvm.bpf.load.byte");

つまり,この関数はllvm IRのintrinsicな命令を出力します. 実際にllcでeBPFプログラムを出力する際に,R6レジスタskbuffを追加する命令が追加されます.

https://github.com/llvm-mirror/llvm/blob/release_50/lib/Target/BPF/BPFISelDAGToDAG.cpp#L179

  case ISD::INTRINSIC_W_CHAIN: {
    unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
    switch (IntNo) {
    case Intrinsic::bpf_load_byte:
    case Intrinsic::bpf_load_half:
    case Intrinsic::bpf_load_word: {
      SDLoc DL(Node);
      SDValue Chain = Node->getOperand(0);
      SDValue N1 = Node->getOperand(1);
      SDValue Skb = Node->getOperand(2);
      SDValue N3 = Node->getOperand(3);

      SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64);
      Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue());
      Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3);
      break;
    }
    }

bpf_load_byte は 最終的にBPF_ABS | <size> | BPF_LD の命令になります.

https://github.com/llvm-mirror/llvm/blob/release_50/lib/Target/BPF/BPFInstrInfo.td#L544

let Defs = [R0, R1, R2, R3, R4, R5], Uses = [R6], hasSideEffects = 1,
    hasExtraDefRegAllocReq = 1, hasExtraSrcRegAllocReq = 1, mayLoad = 1 in {
class LOAD_ABS<bits<2> SizeOp, string OpcodeStr, Intrinsic OpNode>
    : InstBPF<(outs), (ins GPR:$skb, i64imm:$imm),
              "r0 = *("#OpcodeStr#" *)skb[$imm]",
              [(set R0, (OpNode GPR:$skb, i64immSExt32:$imm))]> {
  bits<3> mode;
  bits<2> size;
  bits<32> imm;

  let Inst{63-61} = mode;
  let Inst{60-59} = size;
  let Inst{31-0} = imm;

  let mode = 1;     // BPF_ABS
  let size = SizeOp;
  let BPFClass = 0; // BPF_LD
}
...

def LD_ABS_B : LOAD_ABS<2, "u8", int_bpf_load_byte>;
def LD_ABS_H : LOAD_ABS<1, "u16", int_bpf_load_half>;
def LD_ABS_W : LOAD_ABS<0, "u32", int_bpf_load_word>;

eBPF mapの処理

次に,eBPF mapの部分に関してですが,ロードされる前のeBPFプログラムは以下のようなオブジェクトファイルになっています.

% objdump -x sockex1_kern.o

sockex1_kern.o:     file format elf64-little
sockex1_kern.o
architecture: UNKNOWN!, flags 0x00000011:
HAS_RELOC, HAS_SYMS
start address 0x0000000000000000

Sections:
Idx Name          Size      VMA               LMA               File off  Algn
  0 .text         00000000  0000000000000000  0000000000000000  00000040  2**2
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  1 socket1       00000078  0000000000000000  0000000000000000  00000040  2**3
                  CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE
  2 maps          00000018  0000000000000000  0000000000000000  000000b8  2**2
                  CONTENTS, ALLOC, LOAD, DATA
  3 license       00000004  0000000000000000  0000000000000000  000000d0  2**0
                  CONTENTS, ALLOC, LOAD, DATA
SYMBOL TABLE:
0000000000000068 l       socket1        0000000000000000 LBB0_3
0000000000000000 g       license        0000000000000000 _license
0000000000000000 g       socket1        0000000000000000 bpf_prog1
0000000000000000 g       maps   0000000000000000 my_map


RELOCATION RECORDS FOR [socket1]:
OFFSET           TYPE              VALUE
0000000000000038 UNKNOWN           my_map

注目すべきは最後のrelocationに関するところで,my_mapの値はrelocatableなシンボルとなっています. load_bpf_file()では,bpfプログラムを読み込む際に以下のことをおこなっています.

  1. mapsセクションからeBPF mapの情報を読み取り,eBPF mapを作成
  2. ELFのrelocation recordsをチェックし,必要に応じて処理をおこなう
  3. 最終的にeBPFプログラムをカーネルにロードする

ちなみに,BPF_FUNC_map_lookup_elemの番号はlinux/bpf.hで定義されています.

BPF Compiler Collection (BCC)

上記の例で分かるように,clangでeBPFプログラムがコンパイルできるものの,実際には何かライブラリがなければカーネル内で動作するeBPFプログラムを作成し動作させることは面倒です.また,eBPFにプログラムがコンパイルできたとしても,それがカーネル内で正しく動くかどうかは別問題です.eBPFプログラムをロードする際のverifierで弾かれる可能性も十分あります. カーネルソースのsamples/bpf以下にいくつかヘルパー関数が存在するものの,自分が作成するプログラムで使用するには少々面倒です.

BPF Compiler Collection (BCC)は,簡単にeBPFによるLinux kernel tracingを実現するためのライブラリ/ツール群です.bccは以下のような機能等があります.

bccは巨大なプロジェクトですが,ここでは今までやってきたパケットの統計量の取得に関してみていきたいと思います.

インストール

本題に入る前に,インストール方法について軽くふれておくと,bccのインストール方法はここに書いてありますが,Ubuntuであれば,

sudo apt-get install binutils bcc bcc-tools libbcc-examples python-bcc

で入ると思います.あるいは,自分でコンパイルする場合は

% git clone https://github.com/iovisor/bcc
% cd bcc
% mkdir build
% cd build
% cmake ..
% make
% make install

でできると思います.最新機能を試したい場合は自分でカーネル含めてコンパイルした方がいいと思います.

bccによるプログラムの例

bccを利用してIPの上位プロトコル別に外向きパケットのバイト数をカウントするプログラムは以下のように書けます.

#include <bcc/proto.h>

BPF_ARRAY(my_map, long, 256);

int bpf_prog(struct __sk_buff *skb)
{
    u8* cursor = 0;
    struct ethernet_t *ethhdr = cursor_advance(cursor, sizeof(*ethhdr));
    if(!(ethhdr->type == 0x0800)){ // not ipv4
        return -1;
    }
    struct ip_t *iphdr = cursor_advance(cursor, sizeof(*iphdr));
    u32 index = iphdr->nextp;

    if (skb->pkt_type != PACKET_OUTGOING)
        return -1;

    long *value = my_map.lookup(&index);
    if (value)
        lock_xadd(value, skb->len);

    return -1;
}
import time
from bcc import BPF

def main():
    b = BPF(src_file="./sockex1.c", debug=0)
    f = b.load_func("bpf_prog", BPF.SOCKET_FILTER)
    BPF.attach_raw_socket(f, "lo")
    my_map = b.get_table("my_map")

    ICMP = 1
    TCP = 6
    UDP = 17
    for i in range(5):
        print("TCP {} UDP {} ICMP {} bytes".format(my_map[TCP], my_map[UDP],
                                                   my_map[ICMP]))
        time.sleep(1)


if __name__ == "__main__":
    main()

ここではbccpythonバインディングを利用していて,

  • BPF(src_file="...") でbpfプログラムのロード & コンパイル
  • BPF.attach_raw_socket()でraw socketにBPFプログラムをアタッチ
  • get_table()でmapにアクセス

しています.

bccで読み込んでいるCプログラムは元のものと似ていますが,以下の特徴があります.

  • bpf/proto.hを利用
  • BPF_ARRAY マクロを利用してeBPF mapを定義
  • cursor_advance()関数を利用してskbuffにアクセス

また,eBPFのプログラムでフィルタリングをする場合,戻り値はuserspaceに返すバイトの長さ(の最大)を指定します.普通はパケットをドロップしたい場合は0, そうでない場合は-1にします.といっても今回の例ではユーザプログラム側では特にパケットを受信してないのであまり深い意味は持たないです.(__sk_receive_skb()の中のsk_filter_trim_capからbpfのプログラムが呼ばれ,その戻り値に応じてskbuffの長さが変更 or dropされます). BPF.attach_raw_socket(f, "lo")の後にf.sockでeBPFプログラムがアタッチされたsocketのdescriptorが取得できます.

cursor_advance()

cursor_advance()の定義は以下のようになっています.

https://github.com/iovisor/bcc/blob/fc673a9e0cf31e935f53cb69a76fc0668c8ffecc/src/cc/export/helpers.h#L127

#define cursor_advance(_cursor, _len) \
  ({ void *_tmp = _cursor; _cursor += _len; _tmp; })

ということで,上のcursor_advance()のコードは以下のようになります.

u8* cursor = 0;
struct ethernet_t *ethhdr = ({void *_tmp = cursor; cursor += sizeof(*ethhdr); _tmp;});

これをそのまま解釈すると,最初の状態ではethhdrには0が代入されて,cursorsizeof(*ethhdr)の分だけ加算されることになります. さて,それではどうしてこれでskbuff内のパケットデータにアクセスできるのかというと,まずethernet_tは以下のように宣言されています.

https://github.com/iovisor/bcc/blob/fc673a9e0cf31e935f53cb69a76fc0668c8ffecc/src/cc/export/proto.h#L25

#define BPF_PACKET_HEADER __attribute__((packed)) __attribute__((deprecated("packet")))
struct ethernet_t {
  unsigned long long  dst:48;
  unsigned long long  src:48;
  unsigned int        type:16;
} BPF_PACKET_HEADER;

ethernet_tには"packet"というattributeがつけられています.bccがプログラムをコンパイルする際に,このattirbuteがついている変数へのassignの場合,bpf_dext_pkt()を出力します.

https://github.com/iovisor/bcc/blob/fc673a9e0cf31e935f53cb69a76fc0668c8ffecc/src/cc/frontends/b/codegen_llvm.cc#L358

StatusTuple CodegenLLVM::visit_packet_expr_node(PacketExprNode *n) {
  auto p = proto_scopes_->top_struct()->lookup(n->id_->name_, true);
  VariableDeclStmtNode *offset_decl, *skb_decl;
  Value *offset_mem, *skb_mem;
  TRY2(lookup_var(n, "skb", scopes_->current_var(), &skb_decl, &skb_mem));
  TRY2(lookup_var(n, "$" + n->id_->name_, scopes_->current_var(), &offset_decl, &offset_mem));

  if (p) {
    auto f = p->field(n->id_->sub_name_);
    if (f) {
      size_t bit_offset = f->bit_offset_;
      size_t bit_width = f->bit_width_;
      if(n->bitop_){
          ...
      } else {
        emit("bpf_dext_pkt(pkt, %s + %zu, %zu, %zu)", n->id_->c_str(), bit_offset >> 3, bit_offset & 0x7, bit_width);
        Function *load_fn = mod_->getFunction("bpf_dext_pkt");
        if (!load_fn) return mkstatus_(n, "unable to find function bpf_dext_pkt");
        LoadInst *skb_ptr = B.CreateLoad(skb_mem);
        Value *skb_ptr8 = B.CreateBitCast(skb_ptr, B.getInt8PtrTy());
        LoadInst *offset_ptr = B.CreateLoad(offset_mem);
        Value *skb_hdr_offset = B.CreateAdd(offset_ptr, B.getInt64(bit_offset >> 3));
        expr_ = B.CreateCall(load_fn, vector<Value *>({skb_ptr8, skb_hdr_offset,
                                                      B.getInt64(bit_offset & 0x7), B.getInt64(bit_width)}));
        // this generates extra trunc insns whereas the bpf.load fns already
        // trunc the values internally in the bpf interpeter
        //expr_ = B.CreateTrunc(pop_expr(), B.getIntNTy(bit_width));
      }
    } else {
      emit("pkt->start + pkt->offset + %s", n->id_->c_str());
      return mkstatus_(n, "unsupported");
    }
  }
  return StatusTuple(0);
}

bpf_dext_pkt()は以下のようになっています.

https://github.com/iovisor/bcc/blob/master/src/cc/export/helpers.h#L404

u64 bpf_dext_pkt(void *pkt, u64 off, u64 bofs, u64 bsz) {
  if (bofs == 0 && bsz == 8) {
    return load_byte(pkt, off);
  } else if (bofs + bsz <= 8) {
    return load_byte(pkt, off) >> (8 - (bofs + bsz))  &  MASK(bsz);
  } else if (bofs == 0 && bsz == 16) {
    return load_half(pkt, off);
  } else if (bofs + bsz <= 16) {
    return load_half(pkt, off) >> (16 - (bofs + bsz))  &  MASK(bsz);
  } else if (bofs == 0 && bsz == 32) {
    return load_word(pkt, off);
  } else if (bofs + bsz <= 32) {
    return load_word(pkt, off) >> (32 - (bofs + bsz))  &  MASK(bsz);
  } else if (bofs == 0 && bsz == 64) {
    return load_dword(pkt, off);
  } else if (bofs + bsz <= 64) {
    return load_dword(pkt, off) >> (64 - (bofs + bsz))  &  MASK(bsz);
  }
  return 0;
}

load_byte()から最終的にllvm.bpf.load.byteが出力されます. https://github.com/iovisor/bcc/blob/master/src/cc/export/helpers.h#L287

struct sk_buff;
unsigned long long load_byte(void *skb,
  unsigned long long off) asm("llvm.bpf.load.byte");

…というのが自分の理解ですが,自分のllvmの知識は圧倒的に不足しているので違ったらごめんなさい.

BPF_ARRAY

BPF_ARRAY()マクロは最終的に以下のように展開されます. https://github.com/iovisor/bcc/blob/master/src/cc/export/helpers.h#L287

// Changes to the macro require changes in BFrontendAction classes
#define BPF_F_TABLE(_table_type, _key_type, _leaf_type, _name, _max_entries, _flags) \
struct _name##_table_t { \
  _key_type key; \
  _leaf_type leaf; \
  _leaf_type * (*lookup) (_key_type *); \
  _leaf_type * (*lookup_or_init) (_key_type *, _leaf_type *); \
  int (*update) (_key_type *, _leaf_type *); \
  int (*insert) (_key_type *, _leaf_type *); \
  int (*delete) (_key_type *); \
  void (*call) (void *, int index); \
  void (*increment) (_key_type); \
  int (*get_stackid) (void *, u64); \
  u32 max_entries; \
  int flags; \
}; \
__attribute__((section("maps/" _table_type))) \
struct _name##_table_t _name = { .flags = (_flags), .max_entries = (_max_entries) }

あまり真面目にコードを追ってないですが,どうやらbccがプログラムをパースする際に,mapの定義があったらそのmapを作成しているようです. https://github.com/iovisor/bcc/blob/fc673a9e0cf31e935f53cb69a76fc0668c8ffecc/src/cc/frontends/b/codegen_llvm.cc#L1103

StatusTuple CodegenLLVM::visit_table_decl_stmt_node(TableDeclStmtNode *n) {
    ...
    int map_fd = bpf_create_map(map_type, key->bit_width_ / 8, leaf->bit_width_ / 8, n->size_, 0);
    ...
}

lookup()は最終的にbpf_map_lookup_elem()が呼ばれます.

https://github.com/iovisor/bcc/blob/fc673a9e0cf31e935f53cb69a76fc0668c8ffecc/src/cc/frontends/b/codegen_llvm.cc#L567

StatusTuple CodegenLLVM::emit_table_lookup(MethodCallExprNode *n) {
  TableDeclStmtNode* table = scopes_->top_table()->lookup(n->id_->name_);
  IdentExprNode* arg0 = static_cast<IdentExprNode*>(n->args_.at(0).get());
  IdentExprNode* arg1;
  StructVariableDeclStmtNode* arg1_type;

  auto table_fd_it = table_fds_.find(table);
  if (table_fd_it == table_fds_.end())
    return mkstatus_(n, "unable to find table %s in table_fds_", n->id_->c_str());

  Function *pseudo_fn = mod_->getFunction("llvm.bpf.pseudo");
  if (!pseudo_fn) return mkstatus_(n, "pseudo fd loader doesn't exist");
  Function *lookup_fn = mod_->getFunction("bpf_map_lookup_elem_");
  if (!lookup_fn) return mkstatus_(n, "bpf_map_lookup_elem_ undefined");

  CallInst *pseudo_call = B.CreateCall(pseudo_fn, vector<Value *>({B.getInt64(BPF_PSEUDO_MAP_FD),
                                                                  B.getInt64(table_fd_it->second)}));
  Value *pseudo_map_fd = pseudo_call;

  TRY2(arg0->accept(this));
  Value *key_ptr = B.CreateBitCast(pop_expr(), B.getInt8PtrTy());

  expr_ = B.CreateCall(lookup_fn, vector<Value *>({pseudo_map_fd, key_ptr}));

  ...
}

最初の例ではbpf_map_lookup_elem()の引数のdescriptorはプログラムをコンパイル後に書き換えていましたが,bccの場合は最初にmapを作ってそのdescriptorをそのままllvmのIRに埋め込んでいるのだと思います.多分.

このように,bccはeBPFプログラムが書きやすいようなmodified Cを提供しています.

もう少し具体的なパケットフィルタリングに関する応用例はbccの examples/networking 以下にあります.(例えばhttp_filterなど)

まとめ

clangによるeBPFプログラムの作成方法と,bccを利用したeBPFプログラムの作成方法の基礎について書きました.

次回は今まで説明してこなかったeBPFを利用したkernel tracingについて書こうと思います.