2018-03-04

perf, ftraceのしくみ

Linuxのトレーサーであるperfやftraceのツールの使い方に関する情報は結構ありますが，構造に関してはあまり見つけられなかったため，ここに簡単に調べたことをまとめようかと思います．（ツールの使い方の説明はあんまりしないです．）

この文章はLinux 4.15のソースに基づいています．

全体像
ftrace
perf
perfとeBPF
ftraceとeBPF
その他トレーシングツール
まとめ

全体像

そもそもLinuxのトレーサーとひとえに言ってもperfとかftraceとかkprobeとかuprobeとかいろいろありすぎて一体どうなっているんだという感じなので簡単に関係を図示しています．

f:id:mm_i:20180304224739p:plain

実際はいろいろと複雑に絡み合ってるのでなかなか可視化するのが難しいですが，まぁ一つの見方だと思ってください．

大雑把には以下のように分類できます．

ユーザランドのツール
- perf, perf-tools, bcc, trace-cmd
インタフェース
- perf_event_open(2), bpf(2), ioctl(2), debugfs (tracefs), ...
トレーサー, フレームワーク
- perf, ftrace, eBPF
event, data source
- Performance counter
- tracepoint
- kprobe
- uprobe
- mcount

ftrace

ftraceは主にカーネルのコードのトレースを目的としたフレームワークです． ftraceという名前の通り，function tracingが主機能の一つですが，実際には以下のようなトレーサーが含まれています．

function
- 関数呼び出しの記録
functrion_graph
- 関数の戻りも記録
event tracer
- tracepoint, kprobe, uprobe
latency tracer
- wakeup
  - wakeup時間までのトレース
- irqsoff
  - 割り込み停止時間トレース
- ...
mmio tracer
...

ftraceとのやりとりはユーザスペースからはdebugfsを通じておこないます． debugfsは /sys/kernel/debug/ にマウントされていることが多いと思います．特にdebugfsの中のtracing/ディレクトリ以下がftrace部分です． Linux 4.1から，（主にセキュリティのため）debugfsをマウントしたくない場合でもftraceが利用できるように，tracefsが導入されています．これは従来のdebugfsのtracing部分を分離したものです． debugfsがマウントされている場合，互換性のためにdebug/tracingにtracefsがマウントされるようになっています．

ftraceを利用する場合はまず使用するトレーサーを選択します．トレーサーはトレース結果をリングバッファへ出力します．このバッファへはtracefs経由でアクセスすることが可能です． ftraceにはトレース結果のフィルタリングや，あるイベント時にトレースを開始するなどの機能があります．

トレーサーのコードは主に kernel/trace以下に存在します．

tracefsによるftraceの使い方は以下が参考になります．

ftrace - Function Tracer, https://github.com/torvalds/linux/blob/v4.15/Documentation/trace/ftrace.txt
Steven Rostedt, Debugging the kernel using Ftrace - part 1, https://lwn.net/Articles/365835/, 2009.
Steven Rsotedt, Secrets of the Ftrace function tracer, https://lwn.net/Articles/370423/, 2010.
mhiramat, Ftraceでカーネルの一部の処理を追いかける方法, https://qiita.com/mhiramat/items/42a6af4f3c289ad37095, 2016.
Andrej Yemelianov, Kernel Tracing with Ftrace, https://blog.selectel.com/kernel-tracing-ftrace/, 2017.

以下ではfunction tracing, tracepint, kprobeについて簡単に説明します．

function trace

function tracingはgccのプロファイリング機能を利用します．

gccでは-pgオプションをつけてコンパイルすると，関数呼び出しがmcountという関数の呼び出しに変換されます．

例:

# w/o -pg
% echo "int main(){return 0;}" | gcc -x c -O0 -S -fno-asynchronous-unwind-tables -o- -
        .file   ""
        .text
        .globl  main
        .type   main, @function
main:
        pushq   %rbp
        movq    %rsp, %rbp
        movl    $0, %eax
        popq    %rbp
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 7.2.0-8ubuntu3) 7.2.0"
        .section        .note.GNU-stack,"",@progbits

# w/ -pg
% echo "int main(){return 0;}" | gcc -pg -x c -O0 -S -fno-asynchronous-unwind-tables -o- -
        .file   ""
        .text
        .globl  main
        .type   main, @function
main:
        pushq   %rbp
        movq    %rsp, %rbp
1:      call    *mcount@GOTPCREL(%rip)
        movl    $0, %eax
        popq    %rbp
        ret
        .size   main, .-main
        .ident  "GCC: (Ubuntu 7.2.0-8ubuntu3) 7.2.0"
        .section        .note.GNU-stack,"",@progbits

ユーザランドのプログラムの場合，glibcに含まれるmcountの関数とリンクされます．このmcountの関数はいわゆるトランポリンコードとして動作し，mcountの関数内で記録をとることで関数呼び出しがトレースできます．

ftraceのfunction traceも基本は同じですが，カーネル内の全ての関数呼び出しをmcountを経由してしまうと性能が大幅に低下することは想像に難くありません．そこで，ftraceでは-pg付きでコンパイルしたのち，mcountのcall命令をnopに置き換えるということをします（これはCONFIG_DYNAMIC_FTRACE=yのときですが，普通ftraceを使う場合は有効にするはず）．この処理はカーネルビルド時におこないます．どこにmcountのcall命令が存在したかというのはカーネル内の__start_mcount_locと__end_mcount_locの間に保持しておきます．

% sudo cat /proc/kallsyms | grep mcount
ffffffffbc83d1c0 T __start_mcount_loc
ffffffffbc886f90 T __stop_mcount_loc

この情報を使ってftraceでfunction tracingする際に対象箇所のコードを書き換えてmcountを呼ぶようにします．こうすることで，ftraceを利用していないときのオーバヘッドをほぼ0に抑えています．

参考までに，手元の環境でfunction traceのオンオフでddを実行した際の実行時間は以下のようになりました．

トレースオフ

# current_tracer = nop
% time dd if=/dev/zero of=/dev/null bs=1 count=500k
512000+0 records in
512000+0 records out
512000 bytes (512 kB, 500 KiB) copied, 0.471769 s, 1.1 MB/s
dd if=/dev/zero of=/dev/null bs=1 count=500k  0.13s user 0.34s system 99% cpu 0.473 total

トレースオン

# current_tracder = function_graph
% time dd if=/dev/zero of=/dev/null bs=1 count=500k
512000+0 records in
512000+0 records out
512000 bytes (512 kB, 500 KiB) copied, 5.88682 s, 87.0 kB/s
dd if=/dev/zero of=/dev/null bs=1 count=500k  0.17s user 5.72s system 99% cpu 5.898 total

トレースオン時は実行時間が10倍以上になっています．（ただし，実際にトレースする際は，全ての関数をトレースしても訳がわからなくなるので，フィルタリングを掛けたり一部の処理部分だけトレースを有効化すると思います）．

もう少し具体的な構造の説明は以下が参考になります．

function tracer guts, https://github.com/torvalds/linux/tree/master/Documentation/trace/ftrace-design.txt
Steven Rostedt, Ftrace Kernel Hooks: More than just tracing, https://www.linuxplumbersconf.org/2014/ocw/system/presentations/1773/original/ftrace-kernel-hooks-2014.pdf, 2014.
- mcountの動的書き換え方法

x86でのmcountの実装は arch/x86/kernel/ftrace.c, arch/x86/kernel/ftrace_64.Sにあります．

余談ですが，Linux 4.0から導入されたライブパッチはこのmcountのフックを利用しています． (mcountからパッチされた関数を呼び出す)．

Livepatch, https://github.com/torvalds/linux/blob/master/Documentation/livepatch/livepatch.txt

tracepoint (static event)

tracepointはカーネルのコード内で簡単にprobe functionを定義できるようにするための仕組みです．やっていることを単純化すると，ソース内で以下のようにprobe functinonを呼び出します．

if(event_on){
    callback()
}

実際には一つのトレースポイントに複数の関数を登録することが可能です．（カーネルモジュールからも登録が可能です(例)）．カーネル内の1000以上の箇所でtracepointが定義されています．

tracepointeの定義の詳細はマクロが多用されていて非常に分かりにくいですが，どうも以下のようになっているみたいです．

例: sched_process_exec

https://github.com/torvalds/linux/blob/v4.15/include/trace/events/sched.h#L301

TRACE_EVENT(sched_process_exec,

    TP_PROTO(struct task_struct *p, pid_t old_pid,
         struct linux_binprm *bprm),

    TP_ARGS(p, old_pid, bprm),

    TP_STRUCT__entry(
        __string(   filename,   bprm->filename   )
        __field(    pid_t,      pid     )
        __field(    pid_t,      old_pid     )
    ),

    TP_fast_assign(
        __assign_str(filename, bprm->filename);
        __entry->pid     = p->pid;
        __entry->old_pid = old_pid;
    ),

    TP_printk("filename=%s pid=%d old_pid=%d", __get_str(filename),
          __entry->pid, __entry->old_pid)
);

これらのマクロは include/linux/tracepoint.hで定義されています．各マクロの細かい説明はこちらをみてください．

TRACE_EVENTマクロは最終的にDECLARE_TRACEとして展開されます．

https://github.com/torvalds/linux/blob/v4.15/include/linux/tracepoint.h#L185

#define __DECLARE_TRACE(name, proto, args, cond, data_proto, data_args) \
   extern struct tracepoint __tracepoint_##name;         \
   static inline void trace_##name(proto)               \
   {                               \
       if (static_key_false(&__tracepoint_##name.key))       \
           __DO_TRACE(&__tracepoint_##name,        \
               TP_PROTO(data_proto),           \
               TP_ARGS(data_args),         \
               TP_CONDITION(cond), 0);            \
       if (IS_ENABLED(CONFIG_LOCKDEP) && (cond)) {       \
           rcu_read_lock_sched_notrace();          \
           rcu_dereference_sched(__tracepoint_##name.funcs);\
           rcu_read_unlock_sched_notrace();        \
       }                           \
   }
    ...

この分岐では static-key と呼ばれる仕組みを利用しています． if (static_key_false(&__tracepoint_##name.key))の部分は最初nopとしてコンパイルされます．後からtracepointを有効にするとき，その部分を__DO_TRACE()を実行するようなjmp命令に書き換えます． (ちなみに，最新のドキュメントにはstatic_key_false()はdeprecatedと書いてありますが，普通に利用されてますね..)

__DO_TRACE()の中でコールバック関数を呼び出します．

ここで定義される trace_##name() をフックしたい場所から呼びます． sched_process_execは以下から呼ばれています．

https://github.com/torvalds/linux/blob/v4.15/fs/exec.c#L1683

...
    if (ret >= 0) {
        audit_bprm(bprm);
        trace_sched_process_exec(current, old_pid, bprm);
        ptrace_event(PTRACE_EVENT_EXEC, old_vpid);
        proc_exec_connector(current);
    }
...

で，これだけだとtracepointが定義しただけで，それに対応するコールバック関数は何も登録されていません．

sched_process_execを定義しているsched.hでは，ヘッダの末尾で以下のファイルをincludeしています．

https://github.com/torvalds/linux/blob/v4.15/include/trace/events/sched.h#L576

/* This part must be outside protection */
#include <trace/define_trace.h>

このdefine_trace.hですが，trace/trace_events.hをインクルードしたのち，もう一度sched.hをインクルードします． (TRACE_INCLUDEの部分でincludeされます)

https://github.com/torvalds/linux/blob/v4.15/include/trace/define_trace.h

...
#include <trace/trace_events.h>
#include <trace/perf.h>
...
#define TRACE_HEADER_MULTI_READ

#include TRACE_INCLUDE(TRACE_INCLUDE_FILE)
...

trace_events.hの中で，DECLARE_EVENT_CLASSなどのマクロが再定義されます．従って，shced.hを2回目にインクルードした際はこれらのマクロが適用されます．

https://github.com/torvalds/linux/blob/v4.15/include/trace/trace_events.h#L757

#undef DECLARE_EVENT_CLASS
#define DECLARE_EVENT_CLASS(call, proto, args, tstruct, assign, print) \
_TRACE_PERF_PROTO(call, PARAMS(proto));                    \
static char print_fmt_##call[] = print;                  \
static struct trace_event_class __used __refdata event_class_##call = { \
   .system         = TRACE_SYSTEM_STRING,          \
   .define_fields      = trace_event_define_fields_##call, \
   .fields         = LIST_HEAD_INIT(event_class_##call.fields),\
   .raw_init       = trace_event_raw_init,         \
   .probe          = trace_event_raw_event_##call,     \
   .reg            = trace_event_reg,          \
   _TRACE_PERF_INIT(call)                      \
};

#undef DEFINE_EVENT
#define DEFINE_EVENT(template, call, proto, args)          \
                                   \
static struct trace_event_call __used event_##call = {           \
   .class          = &event_class_##template,      \
   {                               \
       .tp         = &__tracepoint_##call,     \
   },                              \
   .event.funcs        = &trace_event_type_funcs_##template,   \
   .print_fmt      = print_fmt_##template,         \
   .flags          = TRACE_EVENT_FL_TRACEPOINT,        \
};                                 \
static struct trace_event_call __used                    \
__attribute__((section("_ftrace_events"))) *__event_##call = &event_##call

DEFINE_EVENTマクロにより，_ftrace_eventsセクションにstruct trace_event_callのデータが格納されます．

ftraceの初期化時にこの情報を利用してトレースポイントのイベントをリストに追加します．

https://github.com/torvalds/linux/blob/v4.15/kernel/trace/trace_events.c#L3085

static __init int event_trace_enable(void)
...
    for_each_event(iter, __start_ftrace_events, __stop_ftrace_events) {

        call = *iter;
        ret = event_init(call);
        if (!ret)
            list_add(&call->list, &ftrace_events);

eventの有効化はftrace_event_enable_disableでおこないます．

https://github.com/torvalds/linux/blob/v4.15/kernel/trace/trace_events.c#L456

static int __ftrace_event_enable_disable(struct trace_event_file *file,
                     int enable, int soft_disable)
{
...
            ret = call->class->reg(call, TRACE_REG_REGISTER, file);
...

このreg()は，上のDECLARE_EVENT_CLASSで定義したtrace_event_reg()です．

https://github.com/torvalds/linux/blob/v4.15/kernel/trace/trace_events.c#L286

int trace_event_reg(struct trace_event_call *call,
            enum trace_reg type, void *data)
{
    struct trace_event_file *file = data;

    WARN_ON(!(call->flags & TRACE_EVENT_FL_TRACEPOINT));
    switch (type) {
    case TRACE_REG_REGISTER:
        return tracepoint_probe_register(call->tp,
                         call->class->probe,
                         file);
    case TRACE_REG_UNREGISTER:
...

ここのtracepoint_probe_register()により，ftraceのコールバック関数がトレースポイントに登録されます．関数を最初に登録する際はsatatic keyの分岐の部分も書き換えます．

ちなみに，call->class->probeというのはDECLARE_EVENT_CLASSによって定義されたtrace_event_raw_event_##callで，これは以下のようになっています．

https://github.com/torvalds/linux/blob/v4.15/include/trace/trace_events.h#L698

static notrace void                            \
trace_event_raw_event_##call(void *__data, proto)          \
{                                   \
    struct trace_event_file *trace_file = __data;          \
    struct trace_event_data_offsets_##call __maybe_unused __data_offsets;\
    struct trace_event_buffer fbuffer;             \
    struct trace_event_raw_##call *entry;              \
    int __data_size;                       \
                                    \
    if (trace_trigger_soft_disabled(trace_file))          \
        return;                           \
                                    \
    __data_size = trace_event_get_offsets_##call(&__data_offsets, args); \
                                    \
    entry = trace_event_buffer_reserve(&fbuffer, trace_file,    \
                 sizeof(*entry) + __data_size);       \
                                    \
    if (!entry)                           \
        return;                           \
                                    \
    tstruct                             \
                                    \
    { assign; }                         \
                                    \
    trace_event_buffer_commit(&fbuffer);                \
}

trace_event_buffer_commit()によってring bufferへ出力をおこないます．

ftraceではtracepointのeventのオンオフだけでなく，eventに応じたトレースの開始/終了の切り替えなどができるようになっています．

tracepointに関しては以下に資料があります．

Using the Linux Kernel Tracepoints, https://github.com/torvalds/linux/blob/master/Documentation/trace/tracepoints.txt
Event Tracing, https://github.com/torvalds/linux/blob/master/Documentation/trace/events.txt
Steven Rostedt, Using the TRACE_EVENT() macro (Part 1), https://lwn.net/Articles/379903/, 2010.
Steven Rostedt, Using the TRACE_EVENT() macro (Part 2), https://lwn.net/Articles/381064/, 2010.
Steven Rostedt, Using the TRACE_EVENT() macro (Part 3), https://lwn.net/Articles/383362/, 2010.

kprobe (dynamic event)

kprobeはカーネルコード内に動的にフックポイントを追加するための仕組みです．アイディアの基本はフックしたい箇所のコードをブレークポイント命令で書き換えることです．これにより命令単位でカーネル内のほぼ全ての場所のフックが可能になります． (kprobe自身のコードなどはフック不可能です．NOKPROBE_SYMBOLマクロを使うとそのアドレスが_kprobe_blacklistセクションに登録され，そのアドレス範囲に対するkprobeが禁止されます)．

kprobeとtracepointを比較すると，kprobeはtracepointの上位互換のような気もしますが，kprobeはアドレス単位でフックをおこなうためバイナリに依存してしまうのに対し，tracepointの方はバイナリ変更の影響を受けません．（ただし，カーネル開発者側的には一度導入したtracepointを保守する責任が発生するといえます）． tracepiontの方がデータ構造の取得などは楽かと思います．またブレークポイントのフックの方がtracepintのif文によるフックよりかはオーバヘッドが大きいと思います（といっても影響が出るほど大きくはないと思います）．あとはkprobeは動的にコードを書き換えるため，そういう意味ではtracepointの方が安定性があるといえます．とはいってもkprobeも多分本体に導入されてから10年近く経ちますし，特に利用に問題はないかと思います．

kprobeの使い方は，samples/kprobesが参考になります．ブレークポイント箇所の命令を実行する前に呼ばれるpre handlerと，命令実行後に呼ばれるpost handlerを設定してregister_kprobe()を呼びます．

ftraceの観点からみると，tracefsによってkprobeを設定しようとする際，kprobe_events_opsに従ってprobes_write => trace_parse_run_command => trace_run_command の中で createfnのコールバック関数が呼ばれ，結局 create_trace_kprobeが実行されます．ここでregister_trace_kprobe => register_kprobe_event => __register_trace_kprobe の中で register_kprobe()されます．

このときkprobeに登録される関数は，alloc_trace_kprobeの中で tk->rp.kp.pre_handler = kprobe_dispatcher;として kprobe_dispathcerが設定されています． kprobe_dispathcerの中から呼ばれる __kprobe_trace_funcでring bufferへの書き込みをおこなっています．

また，kretprobeという，関数のreturnをフックするための仕組みも提供されています．関数のreturnをフックしたいというよくあるニーズに答えるために導入されたんだと思います．実装的には単純にretをkprobeでフックするのではなく，カーネルのentryをkprobeでフックし，その際にスタック上の戻りアドレスを書き換えてret時にkretprobeのトランポリンコードを呼ぶようにしているようです（かしこい）．

また，uprobeというkprobeのユーザランド版もあります．ちなみに，uprobeはinodeと紐づける形で登録します．

kprobe/uprobeに関しては以下が参考になります．

Sudhanshu Goswami, An introduction to KProbes, https://lwn.net/Articles/132196/, 2005.
Kprobe-based Event Tracing, https://github.com/torvalds/linux/blob/v4.15/Documentation/trace/kprobetrace.txt
kretprobe: Linuxの備忘録とか・・・, http://wiki.bit-hive.com/north/pg/kretprobe, 2012.
Uprobe-tracer: Uprobe-based Event Tracing, https://github.com/torvalds/linux/blob/v4.15/Documentation/trace/uprobetracer.txt

その他のtracer

mmio tracerに関して，簡単に処理を追ってみます．

struct tracerでtracefsでやりとりする際の関数の定義をしているようです．

mmiotraceの例

初期化
- mmio_trace_init() => enable_mmiotrace()
ioremap, iounmap時にtraceする
ioremap_trace_core => __trace_mmiotrace_map() => mmio_trace_mapping()
- call_filter_check_discard でフィルタリング
この後 trace_buffer_unlock_commit() => trace_buffer_unlock_commit_regs() => __buffer_unlock_commit() => ring_buffer_write() でring bufferへ書き込み

trace-cmd

実際にftraceを利用する場合には，ftraceのフロントエンドであるtrace-cmdが利用できます． ftraceのメンテナであるSteven Rostedt氏が直々に開発しています．

man page of trace-cmd, http://man7.org/linux/man-pages/man1/trace-cmd.1.html
Steven Rostedt, Ftrace Profiling, https://events.static.linuxfound.org/sites/events/files/slides/collab-2015-ftrace-profiling.pdf, 2015.

ちなみに，githubのリポジトリの方はかなり古いので注意が必要です．

perf

perfとはLinuxに存在するパフォーマンスモニタリングのための機能です．perf_eventともいいます． perfという名称のユーザスペース用ツールも開発されており，単にperfと言った場合はこのツールを指すことが多いかと思います．ちょっとややこしいので，ここではカーネルの機能の方はperf_eventと書くことにします．

perf（の前進）はもともとPerformance counters for Linux (PCL) という名前だったみたいなので，察するにCPUのperfomance counterへのアクセス手段の提供が当初の目的だったんだと思います．ただし，今ではpermance counter以外のイベントにも対応しています． perf listコマンドによって対応しているイベントの確認ができます．

perf_eventではeventを以下のように分類しています．

PERF_TYPE_HARDWARE
PERF_TYPE_HW_CACHE
PERF_TYPE_RAW
PERF_TYPE_SOFTWARE
PERF_TYPE_TRACEPOINT
PERF_TYPE_BREAKPOINT

hardware, hw_cache, raw がCPUのperfomance counterのイベントに対応します．

perf_event_open(2)システムコールによって，一つのperf eventに対応したfile descriptorが入手できます．このfdに対してread()などをすることでeventのカウンタにアクセスします．

また，perfではイベントのカウンタに2種類あります．一つはcounting counterで，イベントの発生回数を得るために利用します．read()するとカウンタの値が得られます．もう一つがsampling counterで，このカウンタの場合，N回のイベントごとに設定したコールバック関数を呼びます． perf statで得られるのはcounting counterの値，perf recordで得られるのはsamping counterの結果です．

ちなみにこれは余談ですが，perf_event_open(2)のman pageはシステムコールの中でおそらくもっとも長いです．

% git clone https://github.com/mkerrisk/man-pages && cd man-pages/man2
% find ./ -name "*.2" | parallel wc {} | sort -nr | head
3331 13388 88727 ./perf_event_open.2
2796 12584 78237 ./ptrace.2
2281  9245 58337 ./keyctl.2
2102  9984 58088 ./fcntl.2
1938  9262 58178 ./futex.2
1756  7672 45635 ./open.2
1598  6891 43519 ./prctl.2
1368  6316 37622 ./clone.2
1179  5042 32922 ./bpf.2
1100  5122 33092 ./seccomp.2

ユーザスペースツールのperfの使い方は以下が参考になります．

https://github.com/torvalds/linux/tree/master/tools/perf/Documentation
- perf toolのドキュメント (man page)
Brendan Gregg, perf Examples, http://www.brendangregg.com/perf.html
- 神資料
perf wiki, https://perf.wiki.kernel.org/index.php/Main_Page
Paul J. Drongowski, PERF tutorial: Finding execution hot spots, http://sandsoftwaresound.net/perf/perf-tutorial-hot-spots/

PERF_TYPE_HARDWARE, HW_CACHE, RAW

これらのイベントはCPUのperfomance counterのアクセスに利用します． perfomance counterとはCPUについているイベントのモニタリング機能のことです． IntelのCPUの場合SDMの18,19章あたりに書いてあります．どんなイベントが取れるのかはCPUごとに異なりますが，特に一般的なイベントをPERF_EVENT_HARDWARE, PERF_EVENT_HW_CACHEに分類しています． PERF_EVENT_HARDWARE, PERF_EVENT_HW_CACHEには以下のようなものがあります．

% sudo perf list | grep -i hardware
  branch-instructions OR branches                    [Hardware event]
  branch-misses                                      [Hardware event]
  bus-cycles                                         [Hardware event]
  cache-misses                                       [Hardware event]
  cache-references                                   [Hardware event]
  cpu-cycles OR cycles                               [Hardware event]
  instructions                                       [Hardware event]
  ref-cycles                                         [Hardware event]
  L1-dcache-load-misses                              [Hardware cache event]
  L1-dcache-loads                                    [Hardware cache event]
  L1-dcache-stores                                   [Hardware cache event]
  L1-icache-load-misses                              [Hardware cache event]
  LLC-load-misses                                    [Hardware cache event]
  LLC-loads                                          [Hardware cache event]
  LLC-store-misses                                   [Hardware cache event]
  LLC-stores                                         [Hardware cache event]
  branch-load-misses                                 [Hardware cache event]
  branch-loads                                       [Hardware cache event]
  dTLB-load-misses                                   [Hardware cache event]
  dTLB-loads                                         [Hardware cache event]
  dTLB-store-misses                                  [Hardware cache event]
  dTLB-stores                                        [Hardware cache event]
  iTLB-load-misses                                   [Hardware cache event]
  iTLB-loads                                         [Hardware cache event]
  node-load-misses                                   [Hardware cache event]
  node-loads                                         [Hardware cache event]
  node-store-misses                                  [Hardware cache event]
  node-stores                                        [Hardware cache event]

IntelのCPUの話を少しだけすると，intelのcpuではperfomance counterのeventをarchitectural performance eventsとnon-architectural performance events (model-specific performance events)の二つに分けています． architectgural performance counter（クロック数とか)の値はIA32_FIXED_CTR[0-2]レジスタから取得可能です．それ以外のeventは，IA32_PERFEVTSELxレジスタでどのeventを取りたいかを設定します．そのイベントの結果はIA32_PMCxに格納されます．これらのレジスタは全てMSRです．従って，wrmsr/rdmsrでアクセスします．また，CR4.PCE (Performance-Monitoring Counter enable) = 1のとき，rdpmc命令を使ってユーザランドからIA32_PMCxの値を読むことが可能です．rdpmcの方がrdmsrよりも早いらしいです（参考）．

IA32_PMCxのレジスタの数は限られています．CPUによりますが，2個とか4個とか6個とかです．そこでperfではレジスタ数以上のイベントを記録する場合，ラウンドロビンによって適当な時間間隔でレジスタを共有します．従って，最終的に得られる値はあくまで推定値となります．正確な値が必要な場合には取得するイベントを絞る必要があります．このあたりはperf wikiに書いてあります．

perfomance counterにはオーバーフローすると割り込みを発生させる機能があります． sampling counterはこれを利用します．特に，クロック数などのイベントを基準として，適当な間隔で割り込みを発生させ，割り込み発生時のripの記録を取ることでプロファイリングができます．

PERF_EVENT_HARDWARE, PERF_EVENT_HW_CACHE以外のCPU固有のイベントにアクセスするにはPERF_TYPE_RAWを利用して直接イベントの番号を指定します．ちなみに，Linux 4.10付近からプロセッサ毎の固有のPMU eventを名前で参照できるようになっています． perf listしたときにKernel PMU Eventと書かれているものがこれです．この情報はtools/perf/pmu-event/arch/以下のjsonファイルで定義されているようです．

PERF_TYPE_SOFTWARE

perf listしたときにsoftware eventと表示されるやつです．context switchなどがあります．

% sudo perf list | grep -i software
  alignment-faults                                   [Software event]
  bpf-output                                         [Software event]
  context-switches OR cs                             [Software event]
  cpu-clock                                          [Software event]
  cpu-migrations OR migrations                       [Software event]
  dummy                                              [Software event]
  emulation-faults                                   [Software event]
  major-faults                                       [Software event]
  minor-faults                                       [Software event]
  page-faults OR faults                              [Software event]
  task-clock                                         [Software event]

これはどうなっているのかというと，それぞれのイベント箇所で明示的にperf_sw_event()を呼んでいます．

例: arch/x86/mm/fault.c

perf_sw_event() => __perf_sw_event() => ___perf_sw_event => do_pwerf_sw_event => perf_swevent_event

PERF_TYPE_TRACEPOINT

ftraceでも使われていたtracepoint, kprobe, uprobeなどのイベントがPERF_TYPE_TRACEPOINTです． kprobeやuprobeはftraceによって登録されたコールバック関数(kprobe_dispatcher, uprobe_dispatcher)の中からperf_trace_buf_submit()が呼ばれています． tracepointの場合はdefine_trace.hの中で，perf.hが呼ばれ，この中でperf_event用のtracepointのコールバック関数が定義されています．このコールバック関数の登録はftraceのコールバック関数のところでおこなっています．

https://github.com/torvalds/linux/blob/v4.15/kernel/trace/trace_events.c#L305

int trace_event_reg(struct trace_event_call *call,
            enum trace_reg type, void *data)
{
    struct trace_event_file *file = data;

    WARN_ON(!(call->flags & TRACE_EVENT_FL_TRACEPOINT));
    switch (type) {
    case TRACE_REG_REGISTER:
        return tracepoint_probe_register(call->tp,
                         call->class->probe,
                         file);
    case TRACE_REG_UNREGISTER:
        tracepoint_probe_unregister(call->tp,
                        call->class->probe,
                        file);
        return 0;

#ifdef CONFIG_PERF_EVENTS
    case TRACE_REG_PERF_REGISTER:
        return tracepoint_probe_register(call->tp,
                         call->class->perf_probe,
                         call);
        ...

もう少し具体的には，以下のようになっています．

kprobe
- kprobe_dispatcher => kprobe_perf_func => perf_trace_buf_submit
uprobe
- uprobe_dispatcher => uprobe_perf_func => ... => perf_trace_buf_submit
tracepoint
- DECLARE_EVENT_CLASS => perf_trace_run_bpf_submit => perf_tp_event
- 後述するeBPFプログラムの呼び出しと共通化されている．
syscall
- perf_syscall_enter => perf_trace_buf_submit
- perf_syscall_exit => perf_trace_buf_submit

perf_trace_buf_submit() => perf_tp_event => perf_swevent_event

となり処理が継続されます．

PERF_TYPE_BREAKPOINT

これはハードウェアブレークポイントに対応したイベントです．

普通はkprobeやuprobeを使えばいいので使用例がほとんどど見つかりませんが，以下のように利用できます．

% sudo cat /proc/kallsyms| grep sys_brk
ffffffffbb400930 T sys_brk
% sudo perf stat -e mem:0xffffffffbb400930:x ls
bin  perf.data work

 Performance counter stats for 'ls':

                 3      mem:0xffffffffbb400930:x

       0.001000937 seconds time elapsed

具体的なフォーマットはman page参照．

ブレークポイントの設定部分は，ptraceなどからも利用されるようです．

USDT (SDT Event)

perf_eventとは直接は関係ないですが，USDTあるいはSDTと呼ばれるユーザスペースのプログラムでtracepointのようなトレースを実現する方法があります．これはもともとはDtraceで存在していた機能のようで，SystemTapがサポートしています．また，perfも最近対応しています(https://lwn.net/Articles/618956/)．

プログラムのソースコードの適当な箇所にUSDTのprobeを埋め込むと，それ自体はnopとしてコンパイルされます． USDTの情報がELFの.note.stapsdtセクションに格納されるので，後からその情報を利用してuprobeでフックすれば目的の箇所でのフックができます． perf buildid-cacheコマンドで，.note.stapsdtの情報に基づいてイベントが追加できます．

SDTのイベントはperf listでSDT eventとして見えます．

% sudo perf list | grep SDT
  sdt_libc:lll_lock_wait_private                     [SDT event]
  sdt_libc:longjmp                                   [SDT event]
  sdt_libc:longjmp_target                            [SDT event]
  sdt_libc:memory_arena_new                          [SDT event]
  sdt_libc:memory_arena_retry                        [SDT event]
  sdt_libc:memory_arena_reuse                        [SDT event]
  sdt_libc:memory_arena_reuse_free_list              [SDT event]
  sdt_libc:memory_arena_reuse_wait                   [SDT event]
...

perf-tools

perfとftraceを利用したパフォーマンス解析ツールとして，perf-toolsがあります． perfやftrace (tracefs)のラッパーとして動作します．(perf-toolsという名称ですが，ftraceも使っています)．

ただし，今ではbccのツールでperf-toolsでできたことは全てできるんじゃないかと思います．

perf ftrace

若干ややこしいですが，perfコマンドにもftraceのラッパーが含まれており，perf ftraceコマンドで利用できます． perf ftrace recordとして簡単にfunction traceの結果が記録できます．

man page of perf-ftrace

straceとの比較

システムコール呼び出しのトレースをおこなうstraceやライブラリ関数呼び出しのトレースをおこなうltraceといったコマンドがありますが，これらはいずれもptraceを使用しています． straceの場合，システムコール発行/終了時にSIGTRAPを送信します． ltraceの場合はライブラリ関数呼び出しのPLT部分をブレークポイントでフックし，SIGTRAPを送信します．

perfを使ってシステムコールをトレースすることは可能ですが，straceと比べてperfはシグナルを介さずに記録を取ることができるため，高速に動作します．以下に簡単な例を示します．

strace

% time strace -eaccept dd if=/dev/zero of=/dev/null bs=1 count=500k
512000+0 records in
512000+0 records out
512000 bytes (512 kB, 500 KiB) copied, 18.8414 s, 27.2 kB/s
+++ exited with 0 +++
strace -eaccept dd if=/dev/zero of=/dev/null bs=1 count=500k  2.67s user 20.21s system 121% cpu 18.847 total

perf

% time perf record -e 'syscalls:sys_enter_accept' dd if=/dev/zero of=/dev/null bs=1 count=500k
512000+0 records in
512000+0 records out
512000 bytes (512 kB, 500 KiB) copied, 0.490177 s, 1.0 MB/s
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.013 MB perf.data ]
perf record -e 'syscalls:sys_enter_accept' dd if=/dev/zero of=/dev/null   0.20s user 0.40s system 93% cpu 0.635 total

その他

/proc/sys/kernel/perf_event_paranoidの値でperfの実行にCAP_SYS_ADMINが必要かどうか設定できます．

2   allow only user-space measurements (default since Linux 4.6).
1   allow both kernel and user measurements (default before Linux 4.6).
0   allow access to CPU-specific data but not raw tracepoint samples.
-1  no restrictions.

perfとeBPF

Linux Kernel 4.1以降，perfのeventに対してeBPFのプログラムがアタッチできるようになっています．具体的には，以下のカーネルのバージョンで機能が追加されています．

4.1: kprobe (commit)
- BPF_PROG_TYPE_KPROBE
- kprobe_perf_func => trace_call_bpf
4.3: uprobe (commit)
- BPF_PROG_TYPE_KPROBE
  - prog typeはkprobeのものを利用
- uprobe_perf_func => trace_call_bpf
4.7: tracepoint (commit)
- BPF_PROG_TYPE_TRACEPOINT
- DECLARE_EVENT_CLASS => perf_trace_run_bpf_submit => trace_call_bpf
- sysenter, sysexitは他のtracepointと扱いが異なるため，特別な処理が必要 (c.f. bpf: add support for sys_enter_* and sys_exit_* tracepoints
4.9: perf software / hardware event (commit)
- BPF_PROG_TYPE_PERF_EVENT
- __perf_event_overflow => READ_ONCE(event->overflow_handler)(event, data, regs); => bpf_overflow_handler
- sampling counterがオーバーフローした際にbpfプログラムが呼ばれる

BPFプログラムはperf_event_open()で得られたfdに対してioctl(fd, PERF_EVENT_IOC_SET_BPF, prog_fd);を実行してアタッチします． kprobe, uprobeやtracepointはperf側へイベントを渡す際にtrace_call_bpf()を呼ぶようになっています．カウンタオーバフロー時にbpfプログラムが呼ばれる訳ではないです．（そういう意味ではperfのeventにアタッチしているというよりかは，kprobe等に直接アタッチしているといった方が適切かもしれないです）．ブレークポイントイベントに対してはBPFプログラムはアタッチできないようです．

BPFプログラムからは，bpf_trace_printk()を利用してftraceのring bufferへの出力，bpf_perf_event_output()でperfのring bufferへの出力ができます．

sample/bpf/trace_output_kern.c, sample/bpf/trace_output_user.cにBPF側からperfのring bufferに出力するサンプルがあります．概略は以下の通りです．

BPF_MAP_TYPE_PERF_EVENT_ARRAYのbpf arrayを作成 (trace_output_kern.c#6)
ユーザランド側でperf_event_attr.type = PERF_TYPE_SOFTWARE, .config = PERF_COUNT_SW_BPF_OUTPUTとしてperf_event_open (trace_output_user.c#L162)
bpf_map_update_elem()でBPF arrayとperf のfdとの対応付 (trace_output_user.c#L165)
- bpf_map_update_elem() => bpf_fd_array_map_update_elem()
- map_fd_get_ptr()はperf_event_fd_array_get_ptr (perf_event_array_map_opsで定義)
- bpf_event_entry_genでbpf_map_update_elemU()の引数で渡したperf eventのfdに対応するperf_fileを格納
- array->ptrs[index]にその情報が保存される
perf のfdに対してmmap (trace_output_user.c#L41)
BPFプログラム側ではbpf_perf_event_outputを使って出力 (trace_output_kern.c#24)
- bpf_map_update_elem()で格納した情報を読み出し, perf_event_output()を呼ぶ

また，sample/bpf/tracex6_kern.c, sample/bpf/tracex6_user.cにBPF側からperfのカウンタにアクセスする例があります．

実際にこれらの機能を利用する場合はbccを利用するのがいいかと思います．

perfコマンドからも，イベントをBPFのプログラムでフィルタリングできるようになっています (参考)

ftraceとeBPF

Linux 4.15の時点ではftarceのイベントに対してeBPFプログラムはアタッチできません．昨年末にBPF_PROG_TYPE_FTRACEの提案がありましたが(パッチ)，これはBPFをトレースのオンオフの切り替えだけに使うという限定されてたものだったという点や，そもそもパッチ自体にいろいろ問題があったということで採用にはいたってません．今後追加される可能性は十分あるんじゃないかと思います．

その他トレーシングツール

perfやftraceはカーネルと共に開発されていますが，その他独自に開発されているトレーシングツールがいくつかあります．（主にカーネルモジュールの形で利用します）．

特に有名なのがSystemTapで，kprobeやuprobe, tracepointなどに対応し，SystemTap Scriptという形で実質的にC言語でフックした箇所に処理が追加できるのでかなり自由度が高いと思います．もちろんその分安全性には気をつける必要はあります．また，最近bpfのバックエンドも追加されたようです．他にも代表的なツールにLTTngがあります． SystemTapもLTTngも2000年代からずっと開発されているのでいろいろとツールが揃っていると思います． SystemTapのwikiにsystemtap, dtrace, LTTng, perfの比較があります．あんまりSystemTapを使ったことがないのではっきりとは分かりませんが，多分最近になってようやくftrace, perf, eBPFでSystemTapでできたことの多く(+α)ができるようになってる感じなんじゃないかと思います．

また，特に組み込み向けの軽量なトレーシングツールとしてLuaを使ったdynamic tracingができるktapというのがあります(Huaweiが開発)．ただ，これはLinux本体にマージされそうになるも丁度eBPFのマージとぶつかったりして結局マージされず，今では更新は止まっているみたいです．

最近も開発されているトレーシングツールとしてはsysdigというのもあります．これは公式曰く "sysdig as strace + tcpdump + htop + iftop + lsof + wireshark" で，カーネルトレースの用途などには使えませんが，コンテナサポートを全面に押し出しているものなのでそういう用途には便利かもしれないです．

まとめ

perfやftrace周りの処理の概要について簡単に書きました．

結局のところどれを使えばいいんだという話ですが，まぁ自分が好きなのを使えばいいんじゃないでしょうか（ぉ．とりあえず，performance counterの値を知りたいのならperf，カーネルコードのちゃんとしたトレースを取るならftraceですし，あとは今ならbccのツールで手軽に目的のことができるんことが多いんじゃないかなと思います．場合によってはSystemTapやLTTngも見てみるといいと思います．

2018-02-07

VMWare Fusionメモ

vmware mac

以下は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

VagrantでVMWare Fusionを利用するには，Vagrant VMWare pluginを購入する必要がある．

Vagrant用Boxの作成

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

作り方: https://www.vagrantup.com/docs/boxes/base.html

基本は適当に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をセットアップする際の注意点

vagrantユーザをpassword vagrantで作成する
- ubuntuなら，adduser vagrant
vagrantユーザにパスワード無しでsudoできるように設定
- visudoでvagrant ALL=(ALL) NOPASSWD: ALL
- これをしないと，例えば vagrant haltしたときにshutdown -h nowの実行に失敗する
openssh-serverをインストール
vagrant sshで接続するユーザのauthorized_keysにvagrantの公開鍵を追加
- https://github.com/hashicorp/vagrant/blob/master/keys/vagrant.pub
- 初回接続時にvagrantが鍵を自動生成したものに更新する

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では使えない

2018-02-02

SpectreとeBPF

bpf linux sec

新年早々巷にいろいろと賑わいをもたらした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;

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

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

攻撃のために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のブログに丁寧に書いてあるんですが，ざっくりまとめると

2³¹の空間をユーザスペースに確保
- 実際には 2⁴(=16個) のページからなる領域を2¹⁵個作成
- 各領域は同じ物理メモリをマッピング
  - mmap(MAP_NORESERVE)で2³¹の空間を確保したのち，2⁴ページサイズのファイルを作成，その領域にmmap()で各領域にそのファイルを割り当てる
tail callを利用してオフセットを探索．オフセットは2³¹単位で更新する．
キャッシュヒットを探すには最初の2⁴ページの領域を調べればok
- というのものL3は物理アドレスでキャッシュされるため *3
ヒットが見つかると...
- 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_mapやvictim_mapを利用するeBPFプログラムをロードすると，その結果refcntが更新され，攻撃プログラム側のmax_entriesのキャッシュはfalse sharingによって破棄されることになります．

実際には以下のようなプログラムをロードしてfalse sharingします ((sched_setaffinity()でスレッドを実行するコアを制御できます))．cacheline_bounce_fdsにprog_mapやvictim_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にはrefcntとmax_entriesがfalse sharingされないようにする変更も入りました（bpf: avoid false sharing of map refcount with max_entries）．これにより，struct bpf_mapは以下のように変更されています．____cacheline_alignedを利用してmax_entriesとrefcntが別々のキャッシュラインに乗るようにしています．

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_addrかhost_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:一体どうやって分岐予測履歴を求めたのかというと，頑張ってリバースエンジニアリングしたようです．恐るべし..

2017-11-07

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

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という意味

2017-11-04

Ownership is theft? TockのTakeCellについて

rust

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

ここではSysCallDispatcherとRNGがともに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 };

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

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

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

解決策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．

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

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

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

2017-10-09

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

bpf llvm rust

最近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 Language Reference Manual
- LLVM IRのリファレンス．頭から読んでもしょうがないので適宜必要に応じて参照する形になると思います．
LLVM-C: C interface to LLVM
- LLVM C interfaceのdoxygenのドキュメント．特にIR生成に関してはCoreとIRBuilderです
LLVM公式のチュートリアル
- 主にKleidoscopeという独自に定義した言語を対象に，字句解析，構文解析からLLVM IRの生成したりIRをJITで実行したりする方法について書いてあります．LLVM IRの生成に関しては特に，3章と5章のcontrol flowに書いてあります．(C++ APIを利用)
How to get started with the LLVM C API
- LLVM C APIを使ったLLVM IRを出力方法についての概要
A Toy Front-End for LLVM, written in Rust: Getting started
- llvm-sysを使ってrustでLLVM IRを生成する方法についての簡単な解説
きつねさんでもわかるLLVM ~コンパイラを自作するためのガイドブック
- いわゆるきつね本．こちらもLLVMのチュートリアル同様に独自言語の構文解析からIR生成，さらにはパスやバックエンドの作成方法まで広範囲に扱った本ですが，LLVM IRに関しては特に4章と5.7章に書いてあります．2013年の本ですがLLVMの使い方を知るにはいろいろと参考になると思います（LLVMの内部実装を特に解説している本ではないです）．ちなみにこの本ではC++ APIを利用しています．
https://bitbucket.org/tari/merthc
- llvm-sysの作者が作成したMertheseのコンパイラ．llvm-sysの使い方の参考になります．

LLVM IR生成の基礎

LLVM API

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

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

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

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

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

Module
- IR全体のコンテナ．関数(Function)とかグローバル変数とかを保持．
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 APIのdoxygenのドキュメントを見るか，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命令という特殊な命令を利用します（詳細はSSAのWikipediaの記事に書いてあります）．ただし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);
        }
    }

外部関数とのリンク

LDWやMSHなどの命令は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による実行

LLVMはLLVM 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がベース

2017-09-04

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

linux bpf

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プログラムが出力されるのかを追いかけると深みにはまります．