x86におけるメモリアクセス権のルール
定期的に忘れる気がするのでメモ．SDM Volume 3A 4.1.3, 4.6参照.
用語
- 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
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の結果は無視される
- PKRU[2i] (0 <= i <= 15) : access-disable
- protection keyはsupervisor mode addressに関しては無視される
*1:PML4E,PDPTE,PDE,PTEいずれかでU/S bitが0という意味
Ownership is theft? TockのTakeCellについて
tockというrust製の組み込み向けOSがあります． このtockの作成者らが2015年にOwnership is Theft: Experiences Building an Embedded OS in Rust (PLOS 2015)という論文を発表しました．そこでは著者がtockを開発する上で嵌ったownershipに関する問題と，それを解決するための言語の修正アプローチが述べられています．ただその後rustの開発者とのやりとりもあり，言語に修正を加えることなく当初実装したかったことが実装できたようです．The Case for Writing a Kernel in Rust (APSys'17)にそのことが簡単に書かれています．
Ownershipと問題
ご存知の通りrustにはメモリ安全を保証するためにownershipという仕組みがあり，たとえシングルスレッドでも同一データに対するmutableなreferenceを複数持つことができません．といってもmutableなreferenceが複数欲し場合は往々にしてあります．論文では以下のような構成の乱数生成器呼び出しを例に挙げています．
SysCallDispatcher <--> SimpleRNG <---> RNG
pub struct SimpleRNG { pub busy: bool, } impl SimpleRNG { pub fn command(&mut self) { self.busy = true; //... } pub fn deliver(&mut self, rand: u32) { self.busy = false; //... } } pub struct SysCallDispatcher<'a> { pub srng: &'a mut SimpleRNG, } pub struct RNG<'a> { pub srng: &'a mut SimpleRNG, } impl<'a> SysCallDispatcher<'a> { pub fn dispatch(&mut self) { self.srng.command(); } } impl<'a> RNG<'a> { pub fn done(&mut self, num: u32) { self.srng.deliver(num); } }
ここでは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なバッファ領域を共有するようです．
cBPFプログラムをLLVM IRに変換する
最近Linuxでいろいろと大活躍のBPF (Berkeley Packet Filter)には主に2種類あって，一番最初に提唱されlibpcapなどで利用されるcBPF (classic BPF)と，主にLinux内で現在利用されている，cBPFをベースに拡張したeBPF (extended BPF)があります． cBPFのプログラムはlibpcapを使ってtcpdumpなどで使われるフィルタ式からコンパイルすることが可能です．一方eBPFはllvmのバックエンドでサポートされているためclangを使ってC言語からコンパイルすることが可能です．
Linuxはカーネル内にcBPFプログラムをeBPFプログラムに変換する機構を持っていて，cBPFプログラムを使う場合は内部的にeBPFに変換されて実行されています． これによりlibpcapでコンパイルしたcBPFプログラムはLinux内で使うことができますが，最近ちょっとしたプロジェクトでubpfというeBPFのユーザランド実装を使った環境でlibpcapを使ってコンパイルしたcBPFプログラムを動かしたいということがありました． そこで簡単にcBPFのプログラムをeBPFに直接変換するものを作ってみましたが，ふとcBPFプログラムをLLVM IRに変換すれば，LLVMの方で最適化もしてくれるしコンパイルも楽になるのではと思い，やってみることにしました．
ちなみに，実質的に機械語からLLVM IRの変換となるわけで，なんじゃそりゃという感じかもしれませんが機械語からLLVM IRに変換するアイディアは自体は特に新しいものでもなんでもなくて，主に最適化や（セキュリティ用途の）プログラムの静的解析などを目的としていろいろとおこなわれています．代表的なプロジェクトとしては dagger, mcsema, fcd, libbeauty, fracture, BAP*1などがあります．
TL;DR
ドキュメント
結局試行錯誤しながらやってくしかないんですが，特に参考したものを挙げておきます．
- LLVM Language Reference Manual
- LLVM IRのリファレンス．頭から読んでもしょうがないので適宜必要に応じて参照する形になると思います．
- LLVM-C: C interface to LLVM
- LLVM公式のチュートリアル
- How to get started with the LLVM C API
- A Toy Front-End for LLVM, written in Rust: Getting started
- きつねさんでもわかるLLVM ~コンパイラを自作するためのガイドブック
- https://bitbucket.org/tari/merthc
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名を指定するだけでよくなる
- Basic Blockのラベル名は
- レジスタ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)
なんとなくそれっぽいのが出来ているような気がします（画像が勝手に圧縮されてしまう..）．
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もやってみると分かっ（たような気がし）てくるのでやってみるのが大事ですね．
LinuxのBPF : (5) eBPFによるLinux Kernel Tracing
eBPFによるカーネルトレース
一番最初に書いた通り，eBPFはLinuxのトレーサとして利用できます．
カーネルがeBPFプログラムを実行する場合，BPFインタプリタにctxが渡されます（jit化されている場合も同様です）．
https://github.com/torvalds/linux/blob/v4.12/kernel/bpf/core.c#L766
/* Named registers */ ... #define ARG1 regs[BPF_REG_ARG1] // これは BPF_REG_R1 ... static unsigned int __bpf_prog_run(void *ctx, const struct bpf_insn *insn) { ... ARG1 = (u64) (unsigned long) ctx; ... // インタプリタによる処理の実行
このctxはeBPFプログラムをどこにアタッチするかで異なります．
BPFでパケットフィルタリングをする際は，パケットの受信or送信のタイミングでctxとしてskbuffのポインタが渡されてeBPFプログラムが実行されていました．
この構造を応用して，カーネル内の様々なイベントに対して，ユーザが作成したeBPFプログラムを適当なctxの下で実行することでトレースを実現します．
eBPF Program Type
eBPFプログラムの種類は，eBPF Program Typeで区別されます．このProgram TypeはbpfシステムコールでeBPFプログラムをロードする際に指定します．
Linux 4.12時点では以下のようなProgram Typeが存在します．
https://github.com/torvalds/linux/blob/v4.12/include/trace/events/bpf.h#L12
#define __PROG_TYPE_MAP(FN) \ FN(SOCKET_FILTER) \ FN(KPROBE) \ FN(SCHED_CLS) \ FN(SCHED_ACT) \ FN(TRACEPOINT) \ FN(XDP) \ FN(PERF_EVENT) \ FN(CGROUP_SKB) \ FN(CGROUP_SOCK) \ FN(LWT_IN) \ FN(LWT_OUT) \ FN(LWT_XMIT)
今までSOCKET_FILTERとしてのeBPFをずっと見てきた訳ですが，実際にはこれだけの種類があります．
どの用途としてeBPFプログラムを作成するかによって，eBPFプログラムの引数や，eBPFプログラムの戻り値の意味，eBPFプログラムから呼ぶことが可能なカーネル内の関数，さらにはeBPFプログラム作成のために使えるライブラリの種類も変わってきます．
特にカーネルトレース機能としてのeBPFを考える場合，kprobe, tracepoint, perf_event あたりが重要になります． kprobeやperfは元々eBPF以前からカーネルに存在したトレーシング機能ですが，それらの様々なフックポイントに対してeBPFプログラムがアタッチできるようになっています．
ちなみに，カーネルのどのバージョンでBPFのどの機能がサポートされているかというのは，以下のbccの資料がまとまっています． https://github.com/iovisor/bcc/blob/master/docs/kernel-versions.md
bccのトレースツール群
前回簡単に説明したbccには様々なトレーシングツールがデフォルトで含まれています．
これらのツールで何がトレースできるのかというのは，以下のbccの図にまとまっています．
公式のチュートリアルに一部のみですが機能の説明があります． おそらく，今後もツール群は増えていくものと思われます．
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プログラムが出力されるのかを追いかけると深みにはまります．
LinuxのBPF : (4) ClangによるeBPFプログラムの作成と，BPF Compiler Collection (BCC)
Clangを利用したeBPFプログラムの作成
前回はeBPFプログラムをstruct bpf_insnの配列として直接書きましたが，あまりにも面倒です．
cBPFの場合はtcpdump (libpcap)を使うことができました．
llvm3.7よりeBPFのバックエンドが追加されました．したがって，clangを利用してC言語のプログラムをeBPFプログラムにコンパイルすることが可能です．
eBPFへのコンパイル
例えば，以下のようなCプログラムを考えます．
int f(int x){ return x+1; }
-target bpfを指定することでeBPFのプログラムにコンパイルすることが可能です．
llvm IRの出力
clang -c -S -emit-llvm a.c
; ModuleID = 'a.c' source_filename = "a.c" target datalayout = "e-m:e-p:64:64-i64:64-n32:64-S128" target triple = "bpf" ; Function Attrs: noinline nounwind define i32 @f(i32) #0 { %2 = alloca i32, align 4 store i32 %0, i32* %2, align 4 %3 = load i32, i32* %2, align 4 %4 = add nsw i32 %3, 1 ret i32 %4 } attributes #0 = { noinline nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" } !llvm.ident = !{!0} !0 = !{!"clang version 4.0.1 (tags/RELEASE_401/final)"}
eBPFアセンブリの出力
clang -c -S -target bpf a.c
.text .globl f .p2align 3 f: # @f # BB#0: *(u32 *)(r10 - 4) = r1 r2 = r1 r1 += 1 r0 = r1 *(u64 *)(r10 - 16) = r2 exit
eBPFプログラムの出力
clang -c -target bpf a.c
この場合，ELFバイナリが出力されます．
% objdump -x a.o a.o: file format elf64-little a.o architecture: UNKNOWN!, flags 0x00000010: HAS_SYMS start address 0x0000000000000000 Sections: Idx Name Size VMA LMA File off Algn 0 .text 00000030 0000000000000000 0000000000000000 00000040 2**3 CONTENTS, ALLOC, LOAD, READONLY, CODE SYMBOL TABLE: 0000000000000000 g .text 0000000000000000 f % readelf -x .text a.o Hex dump of section '.text': 0x00000000 631afcff 00000000 bf120000 00000000 c............... 0x00000010 07010000 01000000 bf100000 00000000 ................ 0x00000020 7b2af0ff 00000000 95000000 00000000 {*..............
ELFバイナリからeBPFプログラムだけを抽出したい場合は，以下のようにします．
objcopy -I elf64-little -O binary a.o a.bin
% ./ubpf-disassembler a.bin a.s % cat a.s stxw [r10-4], r1 mov r2, r1 add r1, 0x1 mov r0, r1 stxdw [r10-16], r2 exit
このようにしてeBPFのプログラムが作成できますが，実際にカーネル内で動作できるプログラムを作成するにはいくつか注意が必要になります．
カーネルで動作するeBPFプログラムの例
カーネルのsamples/bpf以下にC言語で書かれたeBPFの例がいくつかあります．IPの上位プロトコロル別に外向きのパケットバイト数をカウントするCのプログラムが，sockex1_kern.c及びsockex1_user.cです．
https://github.com/torvalds/linux/blob/v4.12/samples/bpf/sockex1_kern.c (eBPFプログラム)
#include <uapi/linux/bpf.h> #include <uapi/linux/if_ether.h> #include <uapi/linux/if_packet.h> #include <uapi/linux/ip.h> #include "bpf_helpers.h" struct bpf_map_def SEC("maps") my_map = { .type = BPF_MAP_TYPE_ARRAY, .key_size = sizeof(u32), .value_size = sizeof(long), .max_entries = 256, }; SEC("socket1") int bpf_prog1(struct __sk_buff *skb) { int index = load_byte(skb, ETH_HLEN + offsetof(struct iphdr, protocol)); long *value; if (skb->pkt_type != PACKET_OUTGOING) return 0; value = bpf_map_lookup_elem(&my_map, &index); if (value) __sync_fetch_and_add(value, skb->len); return 0; }
https://github.com/torvalds/linux/blob/v4.12/samples/bpf/sockex1_user.c
#include <stdio.h> #include <assert.h> #include <linux/bpf.h> #include "libbpf.h" #include "bpf_load.h" #include "sock_example.h" #include <unistd.h> #include <arpa/inet.h> int main(int ac, char **argv) { char filename[256]; FILE *f; int i, sock; snprintf(filename, sizeof(filename), "%s_kern.o", argv[0]); if (load_bpf_file(filename)) { printf("%s", bpf_log_buf); return 1; } sock = open_raw_sock("lo"); assert(setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, prog_fd, sizeof(prog_fd[0])) == 0); f = popen("ping -c5 localhost", "r"); (void) f; for (i = 0; i < 5; i++) { long long tcp_cnt, udp_cnt, icmp_cnt; int key; key = IPPROTO_TCP; assert(bpf_map_lookup_elem(map_fd[0], &key, &tcp_cnt) == 0); key = IPPROTO_UDP; assert(bpf_map_lookup_elem(map_fd[0], &key, &udp_cnt) == 0); key = IPPROTO_ICMP; assert(bpf_map_lookup_elem(map_fd[0], &key, &icmp_cnt) == 0); printf("TCP %lld UDP %lld ICMP %lld bytes\n", tcp_cnt, udp_cnt, icmp_cnt); sleep(1); } return 0; }
このプログラムはカーネルソースのルートでmake headers_installとしたのち，samples/bpfでmakeすればコンパイルできると思います(要clang/llc)．
load_bpf_file()はelfからeBPFプログラムを呼びだす関数です．
コードを見ればやっていることはなんとなく分かると思いますが，何故このプログラムがちゃんと動作するかは少々複雑です．
前回示したeBPFのプログラムは以下のようになっていました．
BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
BPF_LD_ABS(BPF_B, ETH_HLEN + offsetof(struct iphdr, protocol) /* R0 = ip->proto */),
BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4), /* *(u32 *)(fp - 4) = r0 */
BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), /* r2 = fp - 4 */
BPF_LD_MAP_FD(BPF_REG_1, map_fd),
BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
BPF_MOV64_IMM(BPF_REG_1, 1), /* r1 = 1 */
BPF_RAW_INSN(BPF_STX | BPF_XADD | BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* xadd r0 += r1 */
BPF_MOV64_IMM(BPF_REG_0, 0), /* r0 = 0 */
BPF_EXIT_INSN(),
特に重要なポイントとしては，
BPF_LD_ABSはskbuffからデータを読み出す特別な命令で，R6レジスタにskbuffのポインタを格納する必要があるBPF_FUNC_map_lookup_elemを呼び出す前に，R1レジスタにeBPF mapのdescriptorを格納する
の2点です．
skbuffからのロード
まず，skbuffからのデータのロードに関して，Cでは以下のようになっています．
int index = load_byte(skb, ETH_HLEN + offsetof(struct iphdr, protocol));
ここで，load_byte()はbpf_helpers.hで定義されています．
/* llvm builtin functions that eBPF C program may use to * emit BPF_LD_ABS and BPF_LD_IND instructions */ struct sk_buff; unsigned long long load_byte(void *skb, unsigned long long off) asm("llvm.bpf.load.byte");
つまり，この関数はllvm IRのintrinsicな命令を出力します．
実際にllcでeBPFプログラムを出力する際に，R6レジスタにskbuffを追加する命令が追加されます．
https://github.com/llvm-mirror/llvm/blob/release_50/lib/Target/BPF/BPFISelDAGToDAG.cpp#L179
case ISD::INTRINSIC_W_CHAIN: { unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue(); switch (IntNo) { case Intrinsic::bpf_load_byte: case Intrinsic::bpf_load_half: case Intrinsic::bpf_load_word: { SDLoc DL(Node); SDValue Chain = Node->getOperand(0); SDValue N1 = Node->getOperand(1); SDValue Skb = Node->getOperand(2); SDValue N3 = Node->getOperand(3); SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64); Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue()); Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3); break; } }
bpf_load_byte は 最終的にBPF_ABS | <size> | BPF_LD の命令になります．
https://github.com/llvm-mirror/llvm/blob/release_50/lib/Target/BPF/BPFInstrInfo.td#L544
let Defs = [R0, R1, R2, R3, R4, R5], Uses = [R6], hasSideEffects = 1, hasExtraDefRegAllocReq = 1, hasExtraSrcRegAllocReq = 1, mayLoad = 1 in { class LOAD_ABS<bits<2> SizeOp, string OpcodeStr, Intrinsic OpNode> : InstBPF<(outs), (ins GPR:$skb, i64imm:$imm), "r0 = *("#OpcodeStr#" *)skb[$imm]", [(set R0, (OpNode GPR:$skb, i64immSExt32:$imm))]> { bits<3> mode; bits<2> size; bits<32> imm; let Inst{63-61} = mode; let Inst{60-59} = size; let Inst{31-0} = imm; let mode = 1; // BPF_ABS let size = SizeOp; let BPFClass = 0; // BPF_LD } ... def LD_ABS_B : LOAD_ABS<2, "u8", int_bpf_load_byte>; def LD_ABS_H : LOAD_ABS<1, "u16", int_bpf_load_half>; def LD_ABS_W : LOAD_ABS<0, "u32", int_bpf_load_word>;
eBPF mapの処理
次に，eBPF mapの部分に関してですが，ロードされる前のeBPFプログラムは以下のようなオブジェクトファイルになっています．
% objdump -x sockex1_kern.o sockex1_kern.o: file format elf64-little sockex1_kern.o architecture: UNKNOWN!, flags 0x00000011: HAS_RELOC, HAS_SYMS start address 0x0000000000000000 Sections: Idx Name Size VMA LMA File off Algn 0 .text 00000000 0000000000000000 0000000000000000 00000040 2**2 CONTENTS, ALLOC, LOAD, READONLY, CODE 1 socket1 00000078 0000000000000000 0000000000000000 00000040 2**3 CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE 2 maps 00000018 0000000000000000 0000000000000000 000000b8 2**2 CONTENTS, ALLOC, LOAD, DATA 3 license 00000004 0000000000000000 0000000000000000 000000d0 2**0 CONTENTS, ALLOC, LOAD, DATA SYMBOL TABLE: 0000000000000068 l socket1 0000000000000000 LBB0_3 0000000000000000 g license 0000000000000000 _license 0000000000000000 g socket1 0000000000000000 bpf_prog1 0000000000000000 g maps 0000000000000000 my_map RELOCATION RECORDS FOR [socket1]: OFFSET TYPE VALUE 0000000000000038 UNKNOWN my_map
注目すべきは最後のrelocationに関するところで，my_mapの値はrelocatableなシンボルとなっています．
load_bpf_file()では，bpfプログラムを読み込む際に以下のことをおこなっています．
- mapsセクションからeBPF mapの情報を読み取り，eBPF mapを作成
- ELFのrelocation recordsをチェックし，必要に応じて処理をおこなう
- 最終的にeBPFプログラムをカーネルにロードする
ちなみに，BPF_FUNC_map_lookup_elemの番号はlinux/bpf.hで定義されています．
BPF Compiler Collection (BCC)
上記の例で分かるように，clangでeBPFプログラムがコンパイルできるものの，実際には何かライブラリがなければカーネル内で動作するeBPFプログラムを作成し動作させることは面倒です．また，eBPFにプログラムがコンパイルできたとしても，それがカーネル内で正しく動くかどうかは別問題です．eBPFプログラムをロードする際のverifierで弾かれる可能性も十分あります． カーネルソースのsamples/bpf以下にいくつかヘルパー関数が存在するものの，自分が作成するプログラムで使用するには少々面倒です．
BPF Compiler Collection (BCC)は，簡単にeBPFによるLinux kernel tracingを実現するためのライブラリ/ツール群です．bccは以下のような機能等があります．
- eBPFプログラムを書くために便利なライブラリの提供
- python bindings
- eBPFによる様々なトレーシングツールの提供
bccは巨大なプロジェクトですが，ここでは今までやってきたパケットの統計量の取得に関してみていきたいと思います．
インストール
本題に入る前に，インストール方法について軽くふれておくと，bccのインストール方法はここに書いてありますが，Ubuntuであれば，
sudo apt-get install binutils bcc bcc-tools libbcc-examples python-bcc
で入ると思います．あるいは，自分でコンパイルする場合は
% git clone https://github.com/iovisor/bcc
% cd bcc
% mkdir build
% cd build
% cmake ..
% make
% make install
でできると思います．最新機能を試したい場合は自分でカーネル含めてコンパイルした方がいいと思います．
bccによるプログラムの例
bccを利用してIPの上位プロトコル別に外向きパケットのバイト数をカウントするプログラムは以下のように書けます．
#include <bcc/proto.h> BPF_ARRAY(my_map, long, 256); int bpf_prog(struct __sk_buff *skb) { u8* cursor = 0; struct ethernet_t *ethhdr = cursor_advance(cursor, sizeof(*ethhdr)); if(!(ethhdr->type == 0x0800)){ // not ipv4 return -1; } struct ip_t *iphdr = cursor_advance(cursor, sizeof(*iphdr)); u32 index = iphdr->nextp; if (skb->pkt_type != PACKET_OUTGOING) return -1; long *value = my_map.lookup(&index); if (value) lock_xadd(value, skb->len); return -1; }
import time from bcc import BPF def main(): b = BPF(src_file="./sockex1.c", debug=0) f = b.load_func("bpf_prog", BPF.SOCKET_FILTER) BPF.attach_raw_socket(f, "lo") my_map = b.get_table("my_map") ICMP = 1 TCP = 6 UDP = 17 for i in range(5): print("TCP {} UDP {} ICMP {} bytes".format(my_map[TCP], my_map[UDP], my_map[ICMP])) time.sleep(1) if __name__ == "__main__": main()
BPF(src_file="...")でbpfプログラムのロード & コンパイルBPF.attach_raw_socket()でraw socketにBPFプログラムをアタッチget_table()でmapにアクセス
しています．
bccで読み込んでいるCプログラムは元のものと似ていますが，以下の特徴があります．
- bpf/proto.hを利用
BPF_ARRAYマクロを利用してeBPF mapを定義cursor_advance()関数を利用してskbuffにアクセス
また，eBPFのプログラムでフィルタリングをする場合，戻り値はuserspaceに返すバイトの長さ（の最大）を指定します．普通はパケットをドロップしたい場合は0, そうでない場合は-1にします．といっても今回の例ではユーザプログラム側では特にパケットを受信してないのであまり深い意味は持たないです．（__sk_receive_skb()の中のsk_filter_trim_capからbpfのプログラムが呼ばれ，その戻り値に応じてskbuffの長さが変更 or dropされます）．
BPF.attach_raw_socket(f, "lo")の後にf.sockでeBPFプログラムがアタッチされたsocketのdescriptorが取得できます．
cursor_advance()
cursor_advance()の定義は以下のようになっています．
#define cursor_advance(_cursor, _len) \ ({ void *_tmp = _cursor; _cursor += _len; _tmp; })
ということで，上のcursor_advance()のコードは以下のようになります．
u8* cursor = 0; struct ethernet_t *ethhdr = ({void *_tmp = cursor; cursor += sizeof(*ethhdr); _tmp;});
これをそのまま解釈すると，最初の状態ではethhdrには0が代入されて，cursorはsizeof(*ethhdr)の分だけ加算されることになります．
さて，それではどうしてこれでskbuff内のパケットデータにアクセスできるのかというと，まずethernet_tは以下のように宣言されています．
#define BPF_PACKET_HEADER __attribute__((packed)) __attribute__((deprecated("packet"))) struct ethernet_t { unsigned long long dst:48; unsigned long long src:48; unsigned int type:16; } BPF_PACKET_HEADER;
ethernet_tには"packet"というattributeがつけられています．bccがプログラムをコンパイルする際に，このattirbuteがついている変数へのassignの場合，bpf_dext_pkt()を出力します．
StatusTuple CodegenLLVM::visit_packet_expr_node(PacketExprNode *n) {
auto p = proto_scopes_->top_struct()->lookup(n->id_->name_, true);
VariableDeclStmtNode *offset_decl, *skb_decl;
Value *offset_mem, *skb_mem;
TRY2(lookup_var(n, "skb", scopes_->current_var(), &skb_decl, &skb_mem));
TRY2(lookup_var(n, "$" + n->id_->name_, scopes_->current_var(), &offset_decl, &offset_mem));
if (p) {
auto f = p->field(n->id_->sub_name_);
if (f) {
size_t bit_offset = f->bit_offset_;
size_t bit_width = f->bit_width_;
if(n->bitop_){
...
} else {
emit("bpf_dext_pkt(pkt, %s + %zu, %zu, %zu)", n->id_->c_str(), bit_offset >> 3, bit_offset & 0x7, bit_width);
Function *load_fn = mod_->getFunction("bpf_dext_pkt");
if (!load_fn) return mkstatus_(n, "unable to find function bpf_dext_pkt");
LoadInst *skb_ptr = B.CreateLoad(skb_mem);
Value *skb_ptr8 = B.CreateBitCast(skb_ptr, B.getInt8PtrTy());
LoadInst *offset_ptr = B.CreateLoad(offset_mem);
Value *skb_hdr_offset = B.CreateAdd(offset_ptr, B.getInt64(bit_offset >> 3));
expr_ = B.CreateCall(load_fn, vector<Value *>({skb_ptr8, skb_hdr_offset,
B.getInt64(bit_offset & 0x7), B.getInt64(bit_width)}));
// this generates extra trunc insns whereas the bpf.load fns already
// trunc the values internally in the bpf interpeter
//expr_ = B.CreateTrunc(pop_expr(), B.getIntNTy(bit_width));
}
} else {
emit("pkt->start + pkt->offset + %s", n->id_->c_str());
return mkstatus_(n, "unsupported");
}
}
return StatusTuple(0);
}
bpf_dext_pkt()は以下のようになっています．
https://github.com/iovisor/bcc/blob/master/src/cc/export/helpers.h#L404
u64 bpf_dext_pkt(void *pkt, u64 off, u64 bofs, u64 bsz) { if (bofs == 0 && bsz == 8) { return load_byte(pkt, off); } else if (bofs + bsz <= 8) { return load_byte(pkt, off) >> (8 - (bofs + bsz)) & MASK(bsz); } else if (bofs == 0 && bsz == 16) { return load_half(pkt, off); } else if (bofs + bsz <= 16) { return load_half(pkt, off) >> (16 - (bofs + bsz)) & MASK(bsz); } else if (bofs == 0 && bsz == 32) { return load_word(pkt, off); } else if (bofs + bsz <= 32) { return load_word(pkt, off) >> (32 - (bofs + bsz)) & MASK(bsz); } else if (bofs == 0 && bsz == 64) { return load_dword(pkt, off); } else if (bofs + bsz <= 64) { return load_dword(pkt, off) >> (64 - (bofs + bsz)) & MASK(bsz); } return 0; }
load_byte()から最終的にllvm.bpf.load.byteが出力されます．
https://github.com/iovisor/bcc/blob/master/src/cc/export/helpers.h#L287
struct sk_buff; unsigned long long load_byte(void *skb, unsigned long long off) asm("llvm.bpf.load.byte");
…というのが自分の理解ですが，自分のllvmの知識は圧倒的に不足しているので違ったらごめんなさい．
BPF_ARRAY
BPF_ARRAY()マクロは最終的に以下のように展開されます．
https://github.com/iovisor/bcc/blob/master/src/cc/export/helpers.h#L287
// Changes to the macro require changes in BFrontendAction classes #define BPF_F_TABLE(_table_type, _key_type, _leaf_type, _name, _max_entries, _flags) \ struct _name##_table_t { \ _key_type key; \ _leaf_type leaf; \ _leaf_type * (*lookup) (_key_type *); \ _leaf_type * (*lookup_or_init) (_key_type *, _leaf_type *); \ int (*update) (_key_type *, _leaf_type *); \ int (*insert) (_key_type *, _leaf_type *); \ int (*delete) (_key_type *); \ void (*call) (void *, int index); \ void (*increment) (_key_type); \ int (*get_stackid) (void *, u64); \ u32 max_entries; \ int flags; \ }; \ __attribute__((section("maps/" _table_type))) \ struct _name##_table_t _name = { .flags = (_flags), .max_entries = (_max_entries) }
あまり真面目にコードを追ってないですが，どうやらbccがプログラムをパースする際に，mapの定義があったらそのmapを作成しているようです． https://github.com/iovisor/bcc/blob/fc673a9e0cf31e935f53cb69a76fc0668c8ffecc/src/cc/frontends/b/codegen_llvm.cc#L1103
StatusTuple CodegenLLVM::visit_table_decl_stmt_node(TableDeclStmtNode *n) {
...
int map_fd = bpf_create_map(map_type, key->bit_width_ / 8, leaf->bit_width_ / 8, n->size_, 0);
...
}
lookup()は最終的にbpf_map_lookup_elem()が呼ばれます．
StatusTuple CodegenLLVM::emit_table_lookup(MethodCallExprNode *n) {
TableDeclStmtNode* table = scopes_->top_table()->lookup(n->id_->name_);
IdentExprNode* arg0 = static_cast<IdentExprNode*>(n->args_.at(0).get());
IdentExprNode* arg1;
StructVariableDeclStmtNode* arg1_type;
auto table_fd_it = table_fds_.find(table);
if (table_fd_it == table_fds_.end())
return mkstatus_(n, "unable to find table %s in table_fds_", n->id_->c_str());
Function *pseudo_fn = mod_->getFunction("llvm.bpf.pseudo");
if (!pseudo_fn) return mkstatus_(n, "pseudo fd loader doesn't exist");
Function *lookup_fn = mod_->getFunction("bpf_map_lookup_elem_");
if (!lookup_fn) return mkstatus_(n, "bpf_map_lookup_elem_ undefined");
CallInst *pseudo_call = B.CreateCall(pseudo_fn, vector<Value *>({B.getInt64(BPF_PSEUDO_MAP_FD),
B.getInt64(table_fd_it->second)}));
Value *pseudo_map_fd = pseudo_call;
TRY2(arg0->accept(this));
Value *key_ptr = B.CreateBitCast(pop_expr(), B.getInt8PtrTy());
expr_ = B.CreateCall(lookup_fn, vector<Value *>({pseudo_map_fd, key_ptr}));
...
}
最初の例ではbpf_map_lookup_elem()の引数のdescriptorはプログラムをコンパイル後に書き換えていましたが，bccの場合は最初にmapを作ってそのdescriptorをそのままllvmのIRに埋め込んでいるのだと思います．多分．
このように，bccはeBPFプログラムが書きやすいようなmodified Cを提供しています．
もう少し具体的なパケットフィルタリングに関する応用例はbccの examples/networking 以下にあります．（例えばhttp_filterなど)
まとめ
clangによるeBPFプログラムの作成方法と，bccを利用したeBPFプログラムの作成方法の基礎について書きました．
次回は今まで説明してこなかったeBPFを利用したkernel tracingについて書こうと思います．
LinuxのBPF : (3) eBPFの基礎
はじめに（注意）
ちょうど一年ぐらい前にLinuxのBPFについて記事を書いていました． 最初の記事は古典的なBPFについて，二番目の記事はseccompについてです． eBPFに関する文章も書いていて，てっきり公開していたと思っていたのですが今下書きのまま保存され一年以上放置されていたことに気づきました.. BPFの開発は非常に活発で，ここに書いてる情報が古い可能性もあるのですが，せっかくなので公開しておきます．
この記事はLinux 4.7時点での情報に基づきます．プログラムはLinux 4.7（Ubuntu Xeniel）で動作確認しています．
extended BPF (eBPF)
前々回と前回のエントリでLinuxにおいてBPFのプログラムを利用してパケットフィルタリングやseccompを利用する例を見ました．BPFを利用する利点は，大きく以下の2つです．
- ユーザがフィルタプログラムを自由に設定できる
- コードはカーネル内安全に実行される (実行前に静的に安全性をチェック）
そんなBPFですが，これを拡張し，カーネル内の様々なイベントに対してユーザが定義した処理を実行できるようにすれば，様々なトレースに使えるのではないかという議論が2011年ごろから*1起こりました． そして，その機能実現のためにBPFのレジスタマシンを拡張したextended BPF (eBPF)が考案されました． 昔からあるBPFをclassic BPF (cBPF)，extended BPFをeBPFあるいはinternal BPFとして区別します*2．
eBPFは以下のような特徴/機能があります．
- 10個のレジスタ (cBPFは2つ)
- R0 : 戻り値格納用
- R1-R5 : 引数
- R6-R9 : BPFプログラムが利用
- R10: スタックへアクセスするためのフレームポインタ (read only)
- レジスタ幅は64bit (cBPFは32bit)
- ジャンプが jt/jf ではなく jt/fall through に
- 負の方向のジャンプを許可
- 他のbpfプログラムへのジャンプを許可 (ただし無限ループできないように遷移回数は制限されている)
bpf_call命令によるカーネル内の関数の呼び出し- eBPF mapによるデータのやりとり
eBPF map
eBPFの中でも特にeBPF mapはダイナミックトレースを実現するのに欠かせない機能です． eBPF mapはbpfで利用可能なデータ構造で，eBPFプログラム間やユーザスペース/カーネルスペースのプログラム間でのデータのやりとりに利用します． 例えばeBPFマップを利用することで任意の型のkey/valueの連想配列を作成することができます． eBPF mapはまず最初にユーザプロセスが作成します．BPFプログラムはそのmapにプログラム中からアクセスすることができます．
eBPFプログラムの例
eBPF mapを作成したり，あるいはeBPFのプログラムをイベントにアタッチするにはLinux 3.18から追加されたbpf(2)システムコールを利用します．
bpf(2)のマニュアルに情報がありますが，とりあえず現在(2016/8/1)においては情報がやや古いです..
カーネルのソースのsamples/bpf以下にeBPFのプログラムの例があるので，それと
合わせてドキュメントを見た方がいいと思います．
ここでは，サンプルの中でお手頃なsock_exasmple.cを見てみましょう．
このプログラムはeBPFを利用して，受信したTCPパケット，IPパケット，ARPパケットの種類をカウントするものです．
/* eBPF example program: * - creates arraymap in kernel with key 4 bytes and value 8 bytes * * - loads eBPF program: * r0 = skb->data[ETH_HLEN + offsetof(struct iphdr, protocol)]; * *(u32*)(fp - 4) = r0; * // assuming packet is IPv4, lookup ip->proto in a map * value = bpf_map_lookup_elem(map_fd, fp - 4); * if (value) * (*(u64*)value) += 1; * * - attaches this program to eth0 raw socket * * - every second user space reads map[tcp], map[udp], map[icmp] to see * how many packets of given protocol were seen on eth0 */ #include <stdio.h> #include <unistd.h> #include <assert.h> #include <linux/bpf.h> #include <string.h> #include <stdlib.h> #include <errno.h> #include <sys/socket.h> #include <arpa/inet.h> #include <linux/if_ether.h> #include <linux/ip.h> #include <stddef.h> #include "libbpf.h" static int test_sock(void) { int sock = -1, map_fd, prog_fd, i, key; long long value = 0, tcp_cnt, udp_cnt, icmp_cnt; map_fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(key), sizeof(value), 256, 0); if (map_fd < 0) { printf("failed to create map '%s'\n", strerror(errno)); goto cleanup; } struct bpf_insn prog[] = { BPF_MOV64_REG(BPF_REG_6, BPF_REG_1), BPF_LD_ABS(BPF_B, ETH_HLEN + offsetof(struct iphdr, protocol) /* R0 = ip->proto */), BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4), /* *(u32 *)(fp - 4) = r0 */ BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), /* r2 = fp - 4 */ BPF_LD_MAP_FD(BPF_REG_1, map_fd), BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2), BPF_MOV64_IMM(BPF_REG_1, 1), /* r1 = 1 */ BPF_RAW_INSN(BPF_STX | BPF_XADD | BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* xadd r0 += r1 */ BPF_MOV64_IMM(BPF_REG_0, 0), /* r0 = 0 */ BPF_EXIT_INSN(), }; prog_fd = bpf_prog_load(BPF_PROG_TYPE_SOCKET_FILTER, prog, sizeof(prog), "GPL", 0); if (prog_fd < 0) { printf("failed to load prog '%s'\n", strerror(errno)); goto cleanup; } sock = open_raw_sock("lo"); if (setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, &prog_fd, sizeof(prog_fd)) < 0) { printf("setsockopt %s\n", strerror(errno)); goto cleanup; } for (i = 0; i < 10; i++) { key = IPPROTO_TCP; assert(bpf_lookup_elem(map_fd, &key, &tcp_cnt) == 0); key = IPPROTO_UDP; assert(bpf_lookup_elem(map_fd, &key, &udp_cnt) == 0); key = IPPROTO_ICMP; assert(bpf_lookup_elem(map_fd, &key, &icmp_cnt) == 0); printf("TCP %lld UDP %lld ICMP %lld packets\n", tcp_cnt, udp_cnt, icmp_cnt); sleep(1); } cleanup: /* maps, programs, raw sockets will auto cleanup on process exit */ return 0; } int main(void) { FILE *f; f = popen("ping -c5 localhost", "r"); (void)f; return test_sock(); }
プログラムの主要点について見ていきいます．
eBPFのmapの作成
map_fd = bpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(key), sizeof(value), 256, 0);
bpf_create_map()によって大きさが256のeBPF mapを作成します．map_fdがこのeBPF mapのdescriptorです．
eBPFプログラムの作成
/* * - loads eBPF program: * r0 = skb->data[ETH_HLEN + offsetof(struct iphdr, protocol)]; * *(u32*)(fp - 4) = r0; * // assuming packet is IPv4, lookup ip->proto in a map * value = bpf_map_lookup_elem(map_fd, fp - 4); * if (value) * (*(u64*)value) += 1; */ struct bpf_insn prog[] = { BPF_MOV64_REG(BPF_REG_6, BPF_REG_1), BPF_LD_ABS(BPF_B, ETH_HLEN + offsetof(struct iphdr, protocol) /* R0 = ip->proto */), BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_0, -4), /* *(u32 *)(fp - 4) = r0 */ BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), /* r2 = fp - 4 */ BPF_LD_MAP_FD(BPF_REG_1, map_fd), BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2), BPF_MOV64_IMM(BPF_REG_1, 1), /* r1 = 1 */ BPF_RAW_INSN(BPF_STX | BPF_XADD | BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* xadd r0 += r1 */ BPF_MOV64_IMM(BPF_REG_0, 0), /* r0 = 0 */ BPF_EXIT_INSN(), };
cBPFと同様に，define済みのマクロを利用してeBPFのプログラムを作成することができます．
<linux/bpf.h>にeBPFの命令や，eBPFプログラムから呼び出すことのできる関数が宣言されています．
eBPFについても詳しくはカーネルのドキュメントに書いてあります．
このプログラムが何をしているかというのは，コメントに書いてある通りですが，ポイントとしては
- R1-R5のレジスタが引数として使われる
- R10はフレームポインタ
- 最初R1にはパケットデータを保持する
sk_buffのポインタが格納されている BPF_LD_ABS(正確にはBPF_ABS | <size> | BPF_LD）は特別な命令で，sk_buffからデータを読み出す．このときR6レジスタにsk_buffのポインタを格納する．（注: パケットデータはsk_buff構造体の中のポインタからアクセスするため，単純なeBPFの命令ではアクセスできない．そのため特別扱いしている)BPF_CALLでBPF_FUNC_map_lookup_elem（この関数はカーネル内にあらかじめ存在）を呼び出しているBPF_FUNC_map_lookup_elemの第一引数はeBPF mapのfd，第二引数はキーのアドレス．ここではスタック上にキーを格納し，それを渡している．戻り値はキーに対応するマップが見つかったらそのアドレス
eBPFフィルタプログラムの利用
BPFでパケットフィルタリングする場合は，setsockopt(2)を使ってソケットのfdに対してcBPFのプログラムをアタッチすることができました．
このとき実はcBPFのプログラムは内部でeBPFのプログラムに変換され実行されます．
それでは，eBPFプログラムそのものをソケットにアタッチすることはできるのでしょうか? 答えはもちろんイエスです． アタッチする手順は以下の通りです．
bpfシステムコール（Linux 3.18から追加）を使って，まずカーネル空間にeBPFのプログラムを追加setsockoptの第二引数にSO_ATTACH_BPFを指定してeBPFのプログラムをアタッチする
上のプログラムではbpfシステムコールの代わりに，そのラッパー関数であるbpf_prog_loadを利用しています．
prog_fd = bpf_prog_load(BPF_PROG_TYPE_SOCKET_FILTER, prog, sizeof(prog), "GPL", 0); if (prog_fd < 0) { printf("failed to load prog '%s'\n", strerror(errno)); goto cleanup; } sock = open_raw_sock("lo"); if (setsockopt(sock, SOL_SOCKET, SO_ATTACH_BPF, &prog_fd, sizeof(prog_fd)) < 0) { printf("setsockopt %s\n", strerror(errno)); goto cleanup; }
eBPFプログラムはカーネル内で実行されるため，カーネルモジュールと同様にライセンスを明示する必要があります．
bpf_prog_loadの第四引数でライセンスとして"GPL"を指定しています．GPL compatibleなライセンスにしておかないとカーネル内の他のGPLの関数が呼べなくなります．
setsockoptの挙動
BPFに関するsetsockoptの挙動を整理しておくと，
- cBPFプログラムのロードは，
SO_ATTACH_FILTER- このとき，
sk_attach_filterが呼ばれる- さらに，
sk_attach_filterから，__get_filter()>bpf_prepare_filter()>bpf_migrate_filter()>bpf_convert_filter()と関数が呼ばれcBPFはeBPFに変換される
- さらに，
- このとき，
- eBPFプログラムのロードは，
SO_ATTAH_BPF- このとき，
sk_attach_bpfが呼ばれる
- このとき，
JIT
Linux 3.16からeBPFに対してもJITが使えるようになりました． ちなみに，BPFをJIT化しようとする議論は2011年ごろからありました（A JIT for packet filters）．
/proc/sys/net/core/bpf_jit_enable を1にするとjitが有効になります．また，2にするとdebugモードとなり，jitの結果がdemsgで確認できます．
デフォルトは無効化（0）されています．
ソース
eBPFの主なソースはkernel/bpfにあります．また，tools/net以下にBPFのアセンブラ/ディスアセンブラがあります． eBPFのインタプリタに興味がある方は，eBPFのユーザランド実装であるubpfを見た方が分かりやすいかもしれません．
まとめ
今回はeBPFの基礎について簡単に説明しました．
eBPFによるトレースの方法や，実際にeBPFプログラムを作成する方法（もちろん，#defineを使わないで作成する方法があります）などは機会があれば別に書こうと思います．
nomによるnumpyデータのパース
nom
nomはrust製のパーサコンビネーターライブラリです．
個人的にはno_stdでの動作をサポートしてる点が嬉しいです．
今回勉強のためにnomでnumpyのファイル（のヘッダ）をパースしてみます．
numpyのフォーマット
今回は以下のようにして作成したデータをパースしてみます．
$ python -c "import numpy as np; a = np.arange(9).reshape(3,3); np.save('a.npy', a)"; $ hexdump -C a.npy 00000000 93 4e 55 4d 50 59 01 00 46 00 7b 27 64 65 73 63 |.NUMPY..F.{'desc| 00000010 72 27 3a 20 27 3c 69 38 27 2c 20 27 66 6f 72 74 |r': '<i8', 'fort| 00000020 72 61 6e 5f 6f 72 64 65 72 27 3a 20 46 61 6c 73 |ran_order': Fals| 00000030 65 2c 20 27 73 68 61 70 65 27 3a 20 28 33 2c 20 |e, 'shape': (3, | 00000040 33 29 2c 20 7d 20 20 20 20 20 20 20 20 20 20 0a |3), } .| 00000050 00 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 |................| 00000060 02 00 00 00 00 00 00 00 03 00 00 00 00 00 00 00 |................| 00000070 04 00 00 00 00 00 00 00 05 00 00 00 00 00 00 00 |................| 00000080 06 00 00 00 00 00 00 00 07 00 00 00 00 00 00 00 |................| 00000090 08 00 00 00 00 00 00 00 |........| 00000098
フォーマットの公式ドキュメント: https://docs.scipy.org/doc/numpy-dev/neps/npy-format.html
以下のようなフォーマットになっているようです．
- 先頭は
\x93NUMPY - 次の1byteがメジャーバージョン
- 次の1byteがマイナーバージョン
- メジャーバージョン1の場合，次の2byteがヘッダ長（この後に続くpythonのdictを表す文字列の長さ（パディング含む））
- メジャーバージョン2の場合，次の4byteがヘッダ長
- 次に文字列でpythonのdictの形式で
descr,fortran_order,shapeが格納されているdescr: numpyのdtype．通常は'<u8'とか'<f8'などの文字列だが，structured arrayの場合は型情報のリストになる．fortran_order:TrueかFalseshape: タプルでarrayの形を表す
- その後，アラインメントを揃えるために適当なスペースがあり，最後に改行(
\x0a) - その後が実際のデータ．データの格納形式は
descrで指定されたdtypeに基づく
完成品1
とりあえず，1. dictの部分はdescr, fortran_order, shapeの順に格納されていると仮定 *1 2. dtypeの部分はstrucured arrayは考えないで，endianとワードサイズのみだけ取り出す として作ってみました．
#[derive(Debug, PartialEq)] pub struct NpyHeader { major_version: u8, minor_version: u8, header_len: u32, little_endian: bool, fortran_order: bool, word_size: u32, shape: Vec<u8>, } named!(pub parse_header<NpyHeader>, do_parse!( tag!(b"\x93NUMPY") >> major_version: le_u8 >> minor_version: le_u8 >> header_len: alt!( cond_reduce!(major_version == 1, map!(le_u16, |x| x as u32)) | cond_reduce!(major_version == 2, le_u32)) >> tag!("{'descr': '") >> little_endian: map!(alt!(tag!("<") | tag!(">")), |x| x == b"<") >> le_u8 >> // skip byte word_size: map_res!(map_res!(digit, std::str::from_utf8), std::str::FromStr::from_str) >> tag!("', 'fortran_order': ") >> fortran_order: map!(alt!(tag!("True") | tag!("False")), |s| s == b"True") >> tag!(", 'shape': ") >> shape: delimited!(char!('('), separated_list!(ws!(char!(',')), map_res!( map_res!(digit, std::str::from_utf8), std::str::FromStr::from_str)), char!(')')) >> tag!(", }") >> take_while!(call!(|c| c == b' ')) >> tag!("\n") >> ( NpyHeader{ major_version, minor_version, header_len, little_endian, fortran_order, word_size, shape, } ) ) );
実行結果
#[cfg(test)] mod test { use super::*; use std::fs::File; use std::io::Read; #[test] fn parse_nom() { let mut buf = vec![]; File::open("./a.npy") .expect("failed to open file") .read_to_end(&mut buf) .unwrap(); let r = parse_header(&buf); println!("{:?}", r); assert_eq!( r.to_result().ok().unwrap(), NpyHeader { major_version: 1, minor_version: 0, header_len: 70, little_endian: true, fortran_order: false, word_size: 8, shape: vec![3, 3], } ); } }
$ cargo test -- --nocapture
...
running 1 test
Done([0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0], NpyHeader { major_version: 1, minor_version: 0, header_len: 70, little_endian: true, fortran_order: false, word_size: 8, shape: [3, 3] })
test test::parse_nom ... ok
ポイント
named!()マクロで関数を定義する．今回の場合fn parse_header(input: &[u8]) -> nom::IResult<&[u8], NpyHeader>みたいな関数が定義されることになる．nom::IResult<I,O>の型パラメータは，Iがまだパースしていない残りの部分の型，Oがパースした結果の型- 正しくパースされると，
Done(I,O)が返る．エラーだったらError(Err)かIncomplete(Needed)
do_parse!()マクロを使うと，IResultを返す関数を>>で繋げることができる- 具体的には，
do_parse!(I->IResult<I,A> >> I->IResult<I,B> >> ... I->IResult<I,X> , ( O ) ) => I -> IResult<I, O>の形になる - 最後に
()で囲んだものが最終的な戻り値 - 基本的にnomがいろいろな関数とマクロを提供しているので，それを
do_parse!()の中で組み合わせていくことになる do_parse!()の中でxxx: yyyとするとパース処理した結果が後からxxxで参照できる
- 具体的には，
tag!()で指定したバイト列の読み取りle_u8はlittle endianで1byte読み取る関数*2．同様の関数にle_u16とかle_u32などalt!()は複数のパーサを受け取り，先頭から試していって最初に成功した結果を返すalt!(tag!("True") | tag!("False")の部分は最初がtag!("True")（短い方の文字列)でなければならない．これは"False"が先の場合，"False"にマッチするか確認するために5文字読み込むので，次に"True"にマッチするか確認する際は文字長が足らないため必ず失敗する．詳細はドキュメント参照
- パース処理で得られた部分の型を変換したい場合は，
map!()あるいはmap_res!()を使う- スライスを文字列へ変換:
map_res!(xxxx, std::str::from_utf8) - 文字列を数値へ変換:
map_res!(xxxx, std::str::FromStr::from_str)
- スライスを文字列へ変換:
if処理をしたいときはcond!(),if-else処理をしたい時はalt!()とcond_reduce!()を組み合わせるdelimited!(opening, X, closing)でXを取り出すws!()は各トークン間のスペースを自動で取り除くseparated_list!()でセパレータで区切られた値をVecで取得できる．ちなみに，もし末尾にセパレータがある場合そのセパレータは残る (例えば1,2,3,みたいな場合)
完成品2
もう少し真面目にdictをパースしてみたのがこちら．といっても手抜きでdictのvalueとしてboolかstringか数値のタプルかの3つしか考えてないですが．上の例はあえて全部一つのdo_parse!()にまとめましたが実際には分割した方が，可読性もテストしやすさも向上します．本当ならdictをパースしたあと，さらに個別の各要素をチェックしていく必要がありますが，飽きてきたのでこの辺で.. ちなみにもしdict部分に変なデータがあってもそのままパースされることになります．
named!(to_u8<u8>, map_res!( map_res!(digit, std::str::from_utf8), std::str::FromStr::from_str) ); #[derive(Debug, PartialEq)] pub enum DictValue<'a> { Str(&'a str), Bool(bool), Tuple(Vec<u8>), } named!(tuple_value<DictValue>, map!( delimited!( char!('('), separated_list!(ws!(char!(',')), to_u8), pair!(opt!(ws!(char!(','))), char!(')'))), DictValue::Tuple) ); named!(bool_value<DictValue>, map!(alt!(tag!("True") | tag!("False")), |s| DictValue::Bool(s == b"True")) ); named!(quoted_string<&str>, map_res!( delimited!( char!('\''), is_not!("'"), char!('\'')), std::str::from_utf8) ); named!(string_value<DictValue<'a>>, map!( map_res!( delimited!( char!('\''), is_not!("'"), char!('\'')), std::str::from_utf8), DictValue::Str) ); named!(key_value<(&str, DictValue)>, do_parse!( key: quoted_string >> ws!(char!(':')) >> value: alt!(string_value | bool_value | tuple_value) >> (key, value) ) ); named!(pub parse_dict<HashMap<&str,DictValue>>, delimited!( pair!(char!('{'), opt!(multispace)), map!(many0!(terminated!(key_value, opt!(ws!(char!(','))))), |vec: Vec<_>| vec.into_iter().collect()), pair!(opt!(multispace), char!('}'))) ); #[derive(Debug, PartialEq)] pub struct NpyHeader2<'a> { major_version: u8, minor_version: u8, header_len: u32, dict: HashMap<&'a str, DictValue<'a>>, } named!(pub parse_header2<NpyHeader2>, do_parse!( tag!(b"\x93NUMPY") >> major_version: le_u8 >> minor_version: le_u8 >> header_len: alt!( cond_reduce!(major_version == 1, map!(le_u16, |x| x as u32)) | cond_reduce!(major_version == 2, le_u32)) >> dict: parse_dict >> take_while!(call!(|c| c == b' ')) >> tag!("\n") >> ( NpyHeader2{ major_version, minor_version, header_len, dict, } ) ) );
実行結果
#[test] fn parse_nom2() { let mut buf = vec![]; File::open("./a.npy") .expect("failed to open file") .read_to_end(&mut buf) .unwrap(); let r = parse_header2(&buf); let mut dict = HashMap::new(); dict.insert("descr", DictValue::Str("<i8")); dict.insert("fortran_order", DictValue::Bool(false)); dict.insert("shape", DictValue::Tuple(vec![3,3])); println!("{:?}", r); assert_eq!( r.to_result().ok().unwrap(), NpyHeader2 { major_version: 1, minor_version: 0, header_len: 70, dict: dict, } ); }
$ cargo test -- --nocapture
...
Done([0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0], NpyHeader2 { major_version: 1, minor_version: 0, header_len: 70, dict: {"descr": Str("<i8"), "fortran_order": Bool(false), "shape": Tuple([3, 3])} })
ポイント
alt!()を使う場合，各パーサの戻り値は同じでなければならない．今回はenumを使って対処している
余談
後から気づきましたが，nomを使ってnumpyのstructured arraysをパースしてるnpy-rsというのがあるのでnumpyデータをちゃんとパースしたい人は参考になるかもしれません．dictのパースはValueのenumを作ってパースしてけば綺麗に書ける訳ですね．確かに．
感想
マクロはあまり好きではないので最初とっつきにくい印象がありましたが，書いていくうちにまぁこんなもんかもしれないと思いました．同じ処理をするにもいろいろな書き方ができるので，ライブラリが提供しているマクロ/関数をうまく活用することが簡潔なコードを書く鍵になります．幸いnomで書かれたパーサはいろいろあるのでそれが参考になります．書いていて少し気になったのが，synstasticでの文法チェックが少々遅いこと．体感として明らかにnomでマクロを定義する前と後で遅くなりました．今回の簡単な例でも1s近く遅くなった気がします．これはnom（というかマクロ）の問題なのか，それ以外の問題なのかはわかりませんが..
