bpftraceでテトリス

みなさんこんにちは．突然ですがbpftraceってご存知でしょうか? 名前から明らかなようにbpfを利用したトレーシングツールです．bpftraceの設計は以前から存在するDTraceやSystemTapに影響を受けています．それらのツールに馴染みのある人にとってはむしろ，bpftraceはDTraceやSystemTapのBPF版と言った方が（非常に雑ですが）分かりやすいかもしれません．

一般にBPFを利用してトレーシンングを実施する場合は，1) BPFプログラム本体 と 2) トレーシング結果を表示するためのユーザランドのプログラム を書く必要がありますが，bpftraceでは独自のスクリプト言語により，それらを特に意識せずにトレーシング処理が記述できます．例えば，プロセス別にシステムコール発行数を集計したい場合は以下のようにしてできます．便利ですね．

% bpftrace -e 'tracepoint:raw_syscalls:sys_enter { @[comm] = count(); }'
Attaching 1 probe...
^C

@[systemd-journal]: 5
@[sudo]: 7
@[vim]: 12
@[dockerd]: 23
@[bpftrace]: 25
@[sshd]: 26
@[tmux: server]: 29
@[containerd]: 113

内部的にはbpftraceはスクリプトの構文解析をしてLLVM IRを出力し，それをBPFプログラムにコンパイルしてカーネルにロードします．また同時にbpftraceプログラム自体がランタイムとなりトレーシング結果を表示します．

ところで

SystemTapではテトリスをはじめとしたゲームが動くらしいです．そうなるとbpftraceで同じことができるか気になりませんか? 気になりますよね?

ということで

tetris.stpをbpftraceに移植してみました．

実は元のtetris.stpを動かしたことがないのでオリジナルの動作は分かりませんが，それっぽく動いてるのできっとOKでしょう¹．

FAQ

Q. どうなってるの?

perfのcpu clockのsoftware eventにBPFプログラムアタッチすることで，一定間隔でBPFプログラムを呼び出すことができます．このBPFプログラム内でBPF mapに保存してある盤面の状態を更新し，画面を再描画します．画面の再描画は実際にはBPFプログラム側からperf_event_output()でメッセージを出力し，そのメッセージを受け取ったユーザランドのbpftraceプログラムがANSI エスケープシーケンスを利用して描画します．

Q. キー入力ってどうしてるの?

元の実装ではkbd_envet()関数をフックしてキー入力を取得していますが，この関数は物理キーボードにしか反応しないようでssh環境では使えなかったので，代わりにpty_write()をkprobeでフックしてキー入力を捕捉しています．これがベストな方法かは分かりません．

Q. 自分の環境だと動いてくれません

動作にはLinux 5.3以上が必要です．そうでない場合，BPFプログラムの命令数上限に引っかかりBPFプログラムがロードできません．もともとBPFプログラムは一定時間の実行終了を保証するために1プログラムあたり4096命令という制限がありましたが，Linux 5.3から特権ユーザは最大100万命令のプログラムをロードできるようになりました²．またbccはgithubにあるmaster branch，bpftraceはこのブランチgithubのmaster branchを利用して下さい．一部最新機能を利用しています³．

Q. Linux 5.2以前の環境でどうしても動かしたい

Linux 5.2以前で動作させるにはBPFプログラムのサイズを小さくする必要があります．

今回作成したプログラムはSystemTap版のものをほぼそのまま移植⁴したものですが，BPFプログラムの観点から見るといろいろと非効率です．何より，盤面のマスの状態を一つ一つBPF mapに保存していますが，これはアクセスの度にbpf_map_lookup_elem()が必要な処理であり，大変非効率です．BPFマップには任意のデータ構造が格納できるので，本来であれば盤面を一つのBPFマップのエントリに全体を保存しておいて，一括でロード・ストアすれば良いです．ただし，現状bpftraceはint以外のvalueをmapにストアすることができません．また，BPFプログラムのループ処理を全てunrollしているのも命令増加数の一因です．これはループを含むBPFプログラムはverifierで弾かれるためです．Bounded Loopを使えば一定制約下でループができますが，これもLinux 5.3で導入された機能です（また現時点でbpftraceはbounded loopをサポートしていません）．

命令数上限を回避する技としてはbpf tail callを利用してBPFプログラムをチェインする方法もありますが，こちらもbpftraceは現状対応していません．BPFプログラムを分割して一つのイベントに複数のBPFプログラムをアタッチするという必殺技もありますが，イベントがドロップするとBPFプログラムが呼ばれないので，一貫した動作を保証することが困難になります．

ということで，Linux 5.2以前でまともに動くテトリスを作成するのはなかなか難しいと思いますが，我こそはと思う方はぜひチャレンジしてみてはいかがでしょうか．

結論

bpftraceでも頑張ればテトリスは動きます．

---

冗談はさておき，bpftraceは現在v1.0に向けて活発に開発中です．テトリスは動かないかもしれませんが，4.xのカーネルで利用できます．主要機能は完成していて十分実用的に使用できます⁵が，まだ細かい部に問題があることがあります．興味のある方はぜひ試してみて，もし問題があればissueの方に報告すると良いと思います．こちらに各ディストリビューションごとにインストール方法がまとまっています．使い方は公式のチュートリアルが参考になります．

また，ちょうど今月にbpftraceの一部開発もしているBrendan Gregg先生のBPF本が出ますね．電子書籍版が既に出ているのでざっと読みましたが，ツールとしてはbpftraceを中心に据えている一方で，（タイトルからは分かりませんが）少量ながらしっかりと既存のトレーシングツールの説明もあり，あくまで実用的なパフォーマンスの問題改善にフォーカスした本なのが良いと思いました．ちなみにトレーシング以外のBPFの話，例えばXDPなどの話はほぼない⁶のでそれらは違う文献を当たることになります⁷．

1. 最初実行に少し時間がかかっているのは，BPFプログラムのコンパイルおよびロード時間です． ↩

2. 命令数上限が4096から100万に引き上げられたというとちょっと極端に聞こえますが，実情はそう単純ではありません．実際にBPFプログラムが実行可能かどうかは，BPFの命令数上限の他に，verifierによる検証が一定数以内で終わるかという条件もあります．例えばBPFプログラムはtail callによって他のBPFプログラムに遷移することができますが，この場合はverifeirはその遷移を含めてBPF命令をチェックします．したがって，verifierによって検査される命令数は単一のBPFプログラムの命令数よりも多くなります．このverifierが検査する命令数上限(BPF_COMPLEXITY_LIMIT_INSNS)はverifierの速度向上とともに引き上げられており，Linux 5.3ではそれが100万になりました．また，それに伴い，プログラムロード時のプログラムサイズ制限も特権ユーザに関してはBPF_COMPLEXITY_LIMIT_INSNSに引き上げられました（当該コミット）． ↩

3. bpftraceにパッチ当ててるのはずるくない? っていうのは多分すぐ本体にマージされるので許してください... (2019-12-6追記: マージされました) 将来的にはbcc v0.12.0, bpftrace v0.9.4 以上で対応できると思います（共にまだ未リリース）． ↩

4. ライン消去のアルゴリズムだけループが書けないBPFプログラムでは書きにくかったので少し変更しています． ↩

5. FacebookやNetflixでは既にプロダクション環境で使われているみたいです (cf. https://www.slideshare.net/brendangregg/um2019-bpf-a-new-type-of-software ; この資料だとBPFプログラムが使われている，としか書いてないのでbpftraceではなくてbccのツールかもしれませんが) ↩

6. ネットワークのパフォーマンス解析の話は丸々一章あります． ↩

7. 付録にあるBPF Cの説明やBPF命令セットの話は役に立つと思います． ↩