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もやってみると分かっ（たような気がし）てくるのでやってみるのが大事ですね．
