valgrind 論文読んだメモ
時々 valgrind はオーパーツだとかそういう主張をしてたりします。コードとか論文とかチラ見くらいはしてたのですが、まあちゃんと眺めてみたのでメモ。
Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation
http://valgrind.org/docs/valgrind2007.pdf
1. イントロ
1.1 DBA and DBI
Dynamic binary analysis って種類のツールがあるんですよ、と紹介。その手のツールは Dynamic binary instrumentation で実装されてることが多いですよ、と。つまり実行時にコード埋めるって話。 DBI ってのはすげー汎用性あるんですけどイマイチ注目されてなくてよろしくない、と。
1.2 Shadow Value Tools and Heavyweight DBA
メモリとかレジスタをそのまんま使うんじゃなくて、仮想的にメモリ上に用意したとこにマッピングするテクニックがありますよ、という話。このアプローチは遅いけどたいへん汎用性が高い。
2. Shadow Value Requirements
この手のツールは何ができないといかんか、って話。状態、つまりレジスタとメモリ、メモリの read/write と read/write(2) 、初期化時のメモリ確保とメモリ確保系のシステムコール、スタックとヒープの処理、あたりをフックできる必要がある。それと stderr になんか書ける必要がある。
3. How Valgrind Works
まあなんかここがメインだと思います。だから詳細に。
3.1, 3.2, 3.3
Valgrind は core+tool って感じでなりたってます、と。 tool ってのは memcheck とかそういうやつ。現実には両者は static link されて、ヘンな位置を起動位置にするようになってる。これによって解析される側のコード (guest) のアドレスとかぶらんようにしている。
当初は LD_PRELOAD とか使ってみたりもしてみたけど、 static link されたバイナリの処理ができないし、起動時に解析できない時間があるのも気に喰わなかった、とのこと。
次のアプローチはこっちの論文の方 に書いてあって、 static link された valgrind loader みたいなのを用意して、 valgrind core は dynamic link された executable で tool は shared object 、って感じのアプローチだったらしい。 loader はアドレス指定 mmap で guest に使われるアドレスを占有しておくことによってアドレスの衝突を回避する。このアプローチは WINE に非常に近いってかほとんど同じだと思うんだけど、この論文によると somewhat unreliable だそうだ。
初期化のへんのコードは読んでみたことあるんだけど、なかなかいい感じに hacky で良かった。 valgrind ってやつは guest のコードをそのまま動かす必要があるから、 libc 二回初期化しちゃった事件とかを避けるために、 libc とか使わないで書かれてる。で VG_printf とか VG_malloc とかあるんだけど、この手の関数、特にメモリマネージャとかそいうのはある程度準備してから使わないといけないから、ここではまだあの機能は使えませんよーとかそいうコメントがあったりとか、そういう。
3.4 Guest and Host Registers
guest 側のレジスタは、 ThreadState って構造体があって、 code block (たぶん basic block よりちょっとデカい単位) ごとにメモリに書き出すようにしてます、と。遅そうに見えるけど、まあ元々遅いからそんな気にならんかったみたいな。
3.5 D&R vs C&A
guest のコードは一旦翻訳されて、それから再び JIT されて実行されてます、と。このアプローチは遅いんだが汎用性が高い、ってかなんでもできる。
C&A ってのはそのまま実行して、コードの部分部分にアノテートする、ってアプローチ、だと思う…元のコードそのまま使うから、速いけど汎用性は低い。
両者のハイブリッドとかも余裕でできて、 valgrind も昔は FPU と SIMD が歴史的な事情(たぶんラクだったってだけだと思う)で C&A だったけど、今は全部 D&R らしい。
3.6 Valgrind's IR
IR ってのはこんなんですよ、っていう紹介。 x86 で 3 命令なものが、 17 命令にふくらむ。かなりデカくなるけど、後で optimization かかったりもする、と。ちょっと引用:
0x24F275: movl -16180(%ebx,%eax,4),%eax
1: ------ IMark(0x24F275, 7) ------
2: t0 = Add32(Add32(GET:I32(12),# get %ebx and
Shl32(GET:I32(0),0x2:I8)), # %eax, and
0xFFFFC0CC:I32) # compute addr
3: PUT(0) = LDle:I32(t0) # put %eax
0x24F27C: addl %ebx,%eax
4: ------ IMark(0x24F27C, 2) ------
5: PUT(60) = 0x24F27C:I32 # put %eip
6: t3 = GET:I32(0) # get %eax
7: t2 = GET:I32(12) # get %ebx
8: t1 = Add32(t3,t2) # addl
9: PUT(32) = 0x3:I32 # put eflags val1
10: PUT(36) = t3 # put eflags val2
11: PUT(40) = t2 # put eflags val3
12: PUT(44) = 0x0:I32 # put eflags val4
13: PUT(0) = t1 # put %eax
0x24F27E: jmp*l %eax
14: ------ IMark(0x24F27E, 2) ------
15: PUT(60) = 0x24F27E:I32 # put %eip
16: t4 = GET:I32(0) # get %eax
17: goto {Boring} t4印象的なのは eflags の更新ですかね。ああ EIP の更新とかもそりゃしないといけないんだなぁとかも感慨深い。
あと cpuid みたいなヘンな命令は関数呼び出しになるそうな。
3.7 Translating a Single Code Block
最初に code block ってのは何かっていう説明。 jmp のたびに切れる basic block じゃなくて、 50 命令越えるか、条件分岐が来るか、よくわからんとこへの jmp が来るか、3回 jmp が来るか、って条件で切れる、らしい。今ひとつこの基準がどういうふうに決まったかはよくわからない。
で、上のコードがどう変化していくか。
- Phase 1 disassembly: マシンコード => tree IR
上みたいな IR にする。 tree ってのがなんで tree なのかよくわかってないんだけど、 x86 のややこしいメモリ参照の -16180(%ebx,%eax,4) ってやつが構文木になったままだから、かな。
- Phase2 optimization: tree IR => flat IR
さっきの木になってる部分をバラしつつ、最適化をかけるんだと思う。 redundant get and put elimination (to remove unnecessary copying of guest registers to/from the ThreadState), copy and constant propagation, constant folding, dead code removal, common sub-expression elimination, and even simple loop unrolling for intra-block loops をすると書いてある。他のはともかく、条件分岐で cdoe block 切れるって言ってたのに、なんでループアンロールできるんだろう…
上の例で言うと、例えば EIP は何度も上書きされてるから最後の以外の PUT は消せるし、他にも色々と常識的に消せそうなものはちゃんと消えるみたい。
コード注入。ここは core じゃなくて tool が行なう。例えば memcheck はメモリへの書き込みとかにコードを注入しないといけないから、そいうコードを書き込む。注入されたコードは元のコードよりむしろデカい。上のコードの例だと、この phase が終わると 18 命令になるんだけど、 11 命令が注入されたコードらしい。オリジナルが 7 命令まで減ってるのは phase2 のおかげだと思う。
二度目の最適化。定数の畳み込みと dead code elimination をする、らしい。 tool を適当に書いても少しは最適化してくれますよ、と。
- Phase 5 Tree building: flat IR => tree IR
tree IR に戻す。 x86 とかで短いマシン語に戻しやすいから、ですかね。しかしこの処理って簡単じゃない気がするんだけどな…
- Phase 6 instruction selection: tree IR => instruction list
x86 などのマシンコードに。実際のマシンコードと違う点は、まだエンコードされてない点と、レジスタが仮想レジスタなだけ、っぽい。
- Phase 7 register allocation: instruction list => instruction list
レジスタを仮想じゃなくする。レジスタ一個は必ず ThreadState を差してるように予約してあるそうな。あとレジスタからレジスタの無駄な移動もここで消えます、と。
- Phase 8 Assembly: instruction list => machine code
単にエンコードするだけ。
3.8 Storing Translations
valgrind は最初に全部コンパイルするんじゃなくて、実行されるところを順にコンパイルしてくんだけど、既にコンパイルされた部分は LRU な cache に入ってます、と。
3.9 Executing Translations
code block が終わったら、次のコードに飛ぶ。上述の LRU cache よりさらに小さい cache みたいなのがあって、こっちの方はアセンブリで書かれた高速な lookup があって、こっちに無ければ上述の LRU の方を見る遅い C で書かれたコードに行くらしい。
この小さい cache ってのは、コード (coregrind/m_dispatch/dispatch-x86-linux.S) をぱっと満た感じ、 32768 エントリ入る、衝突の解決全くしないハッシュ、って感じかな。これはちょっと面白いアイデアだなぁ。 bloom filter 的というかなんというか。
valgrind は chaining とか呼ばれる、 jmp 無しで命令つないでくようなことはしません、でもあんま気にならないよ、と。 basic block より広い単位になってるのと、 valgrind の dispatcher は速い、ってのがいいんじゃないか、とのこと。
3.10 System Calls
状態を実際のレジスタとかに配置して、実際にシステムコールを呼ぶ、で、状態を書き戻す。
mmap とかは valgrind がガメてるところを要求してたら最初から失敗させるらしい。これはイマイチよくわからない。そのままシステムコール呼んでも失敗してくれる気がするんだけど…
3.11 Client Requests
guest コードは valgrind の core とか tool にメッセージを送れる、詳細はここでは述べない、とのこと。別の論文の方とかコード (VEX/priv/guest-x86/toIR.c) を読んでみるに、
C1C703 roll $3, %edi
C1C70D roll $13, %edi
C1C71D roll $29, %edi
C1C713 roll $19, %ediの 4 命令で 64bit rotate (つまり nop) が出てくると送れる、って感じぽい。
3.12 The Events System
システムコールでメモリ書き変わったりすると大変なので、 IR でこういうのを表現しようとするんじゃなくて、システムコールのラッパの中で、 tool が登録したイベントハンドラを呼ぶ感じになってます、と。イベントの種類としてはメモリの読み書きなど。
他のイベントの種類としてはスタックの上げ下げとかは、 tool 側からの IR いじりでも実現できるけど、よくチェックしたいものなので core の方でイベントとして提供してる。スタックが変わったのとデカいスタックアロケーションの区別をつけるのは大変で、デフォルトでは 2MB 以上の変化があればスタックが変わったとみなしますがこの値は変えれます、と。あと client request でスタックが変わったことをアプリ側から明示的に教えることもできる。
3.13 Function Replacement and Function Wrapping
valgrind は tool から関数の置き換えができる仕組みを提供してて、その中で元の関数を呼べるのでラップもできる。まあ memcheck とかだと malloc とかフックしないとなので、あたりまえ。
3.14 Threads
スレッドはロックを使って全スレッドをシリアライズしている。ブロックしうるシステムコールか、ある程度長く走ったらロックを離して、他のスレッドに処理を渡す。こいう仕組みになってるおかげで、 kernel が次のスレッドを決めてるものの、スレッドスイッチのタイミングは完全にコントロールしている。これのおかげで複数の IR にバラされた命令の途中でスレッドが切り替わって大変なことになったりはしない。
このへんは m_scheduler/scheduler.c だと思う。なんかこのヘン昔読んだ時に次のスレッド決めるのは core がやってた気がしたんだけど、気のせいだったかな…
これは 3 つ目のスレッド管理方法で、 1 つ目は pthread ラッパで、環境依存だし、 glibc が pthread に依存しまくってて色々ダメでした、と。 2 つ目は今の方法に近いけど複雑で kernel thread が必要だったらしい。
ちゃんとマルチスレッドを使ってパフォーマンス向上させる方法は open question
3.15 Signals
シグナルハンドラの中でコントロールを失うのが問題。さらに中で longjmp とかされると valgrind は永久にコントロールを失う。その手の問題をふせぐには signal を登録する関数をフックしないといけません。
3.16 Self-modifying Code
自己書き換えへの対処は大変。 PPC とかだと flush するための命令があるからわかりやすい。
valgrind は自己書き換え検出をする機構があって、コードのチェックサムを見て変わってたらコンパイルしなおす。これは遅いのでデフォルトではスタックに対してだけ。自己書き換えコードのほとんどは、 GCC の関数内関数とかでスタックに作るアレなので、たいていはこれで十分。
一応全域をチェックするようにする手段と、この機能を完全にオフにする手段、あとアプリ側から client request で教える手段も用意してあります。
4 Valgrind's Shadow Value Support
2章で説明した requirements を valgrind が 3 章を使ってどう満たしているか。 3 章の知識があると比較的当たり前。
5 Evaluation
5.1 ツールの書き易さ、 5.2 ツールが適用できるアプリの数、 5.3 ツールの汎用性、 5.4 ツールのパフォーマンス、って感じ。
5.1 は core が汎用性があるように書いてあるから tool は短い行数で書けるよって話。 core は 170280 行の C と 3207 行のアセンブリ、 memcheck は 10509 行の C で cachegrind は 2431 行、 massif が 1763 行で nulgrind は 39 行。たしかに短いねーとかいう。
5.4 は、何もしない nulgrind で 4.3 倍くらい遅くなって、 memcheck で 22.1 倍、ってくらいの数字はだいたい覚えておいていいかな…ってくらい。
