google-perftoolsを別のCPUに移植してみた
google-perftoolsというx86,x86_64,ppcなUNIX向けのプロファイラの(cpu-profiler部分)を、armなLinuxに対応させてみました。何かの役に立つかもしれないので、patchおよびpatch作成作業のメモを載せます。arm-v5tアーキテクチャ(ARM9系)向けの移植です。
Linux/ARM向けのソフトウェアのパフォーマンスを解析したいなぁと思うことがあったのですが、OProfileはカーネル入れ替えがめんどくさい、gprofはプロファイル専用のバイナリを作成するのがめんどくさい、プロプラな奴は興味ないということで移植しました。移植の方がめんどくさいだろという話もありますが。perftools自体の説明はこちらが便利です。あーそういえばAndroidもARMでしたっけ?
パッチ
http://binary.nahi.to/google-perftools-0.93_armv5t_1.patch
パッチの適用方法とmake方法は次のとおりです。
host% tar xvzf google-perftools-0.93.tar.gz
host% cd google-perftools-0.93/
host% chmod +w aclocal.m4 (tarballのpermissionがおかしい模様)
host% patch -p1 < google-perftools-0.93_armv5t_1.patch
host% CC=armv5tel-redhat-linux-gnueabi-gcc CXX=armv5tel-redhat-linux-gnueabi-g++ ./configure \
--host=arm-linux --enable-frame-pointer --prefix=/path/to/nfs_root/
host% sudo make install以上でインストールが完了します。ARMマシン(以下target)上で、.soをPRELOADして解析対象を実行すると、prof.outという解析結果ファイルが生成されます。
target# export CPUPROFILE=/root/prof.out target# export CPUPROFILE_FREQUENCY=100 (秒間最大何回プロファイルタイマをfireさせるか. デフォルト100, 最大4000) target# LD_PRELOAD=/lib/libprofiler.so.0 /path/to/program PROFILE: interrupts/evictions/bytes = 512/0/156
解析対象の /path/to/program は、-O0 または -O2 -fno-omit-frame-pointer でコンパイルされていることが必要です。stripされていてもOKです。
解析結果のprof.outファイルの内容を可視化するにはpprofコマンドを使います。pprofコマンドをARMマシン上で動かそうとすると、そちらにperl, file, binutils, graphvizくらいはインストールされていないとダメですが、これらを頑張ってARMマシンに入れなくても、次を満たしていればx86上でプロファイル結果を見られます。
これは便利。
host% pprof --tools=/usr/bin/armv5tel-redhat-linux-gnueabi- \
--lib_prefix=/usr/armv5tel-redhat-linux-gnueabi/sys-root/ \
/path/to/nfs_root/path/to/program /path/to/nfs_root/root/prof.out
Welcome to pprof! For help, type 'help'.
(pprof) top
Total: 512 samples
251 49.0% 49.0% 251 49.0% c
152 29.7% 78.7% 152 29.7% b
96 18.8% 97.5% 96 18.8% a
13 2.5% 100.0% 13 2.5% wordexp
0 0.0% 100.0% 2 0.4% _dl_signal_error
0 0.0% 100.0% 510 99.6% __evoke_link_warning_getwd
0 0.0% 100.0% 499 97.5% main
(pprof)pprofにかける際のprogramは、strip前のものにしてください。pprof結果が怪しいときは、./configure で --enable-old-sighandler してみてください。うまく動かなかったりしたら教えてください。私は主にqemuとFedora6-armで動作確認してます。
移植方法
同ソフトウェアはアーキテクチャ依存部分が分離されているので、移植作業は楽で、
- ARMv5t用のアトミック演算関数を2種類書く
- スタックトレース関数を書く
- シグナルを受信したときのPCの値を得る関数を書く
の3stepで大体終わりです。順に。
1. アトミック演算関数を2種類書く (src/base/atomicops-internals-armv5t.h)
最低限、compare-and-swap(CAS)と、storeだけ書けばOKです。これは、ユーザ空間で完結したスレッドの排他制御に使われます。CASは、GCC4組込みのAtomic Builtins(__sync_ほげ() という関数群)が使えるアーキテクチャであれば、何も考えずにそれをwrapして終わりなのですが、ARM用は存在しない（コンパイルはできるけどリンクでundefined reference) ようなので、自分で書くことになります。ARMv5tでは、CAS実装に直接的に使える命令がありません。cmpxchg8b命令はv7アーキテクチャ(Cortex)から、ldrex/strex命令(=ll/sc)もv6アーキテクチャ(ARM11とか)からしか使えないそうで。v5の場合は...どうしよ。割り込みを禁止できないユーザモードのプロセスでCASするのは面倒ですね。
とりあえずswp/swpb命令というのは使えるので、それを使ってatomicに最大限近そうなCASを書くのが、速度と安全性のバランスが良いのかな。glibcが内部で(?)使っているatomic.hというファイル (glibc-ports-2.7/sysdeps/arm/bits/atomic.h) に実装例がありますねぇ。この実装は、2つあるswpの間のcmp命令実行の前後でコンテキストスイッチが起きるとまずいことになりますが*1、まープロファイラだし(?)、これでよしとします。
typedef int32_t AtomicWord;
inline AtomicWord Acquire_CompareAndSwap(volatile AtomicWord* ptr,
AtomicWord old_value,
AtomicWord new_value) {
AtomicWord result;
//#if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
// result = __sync_val_compare_and_swap(ptr, old_value, new_value);
//#else
AtomicWord tmp;
__asm__ __volatile__ ("0: \n\t"
"ldr %1,[%2] \n\t"
"cmp %1,%4 \n\t"
"movne %0,%1 \n\t"
"bne 1f \n\t"
"swp %0,%3,[%2] \n\t"
"cmp %1,%0 \n\t"
"swpne %1,%0,[%2] \n\t"
"bne 0b \n\t"
"1:"
: "=&r"(result), "=&r"(tmp)
: "r"(ptr), "r"(new_value), "r"(old_value)
: "cc", "memory");
//#endif
return result;
}次、release-storeですが、storeはCで書き、store直前にGCCの最適化を阻むバリアだけ置いとけばOKかと。例によってメモリ同期命令はv6tアーキ以降にしかない(筈)です。
inline void Release_Store(volatile AtomicWord* ptr, AtomicWord value) {
#if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 1)
__sync_synchronize();
#else
__asm__ __volatile__("" : : : "memory");
#endif
*ptr = value;
}NPTL専用でよければ、glibc-ports-2.7/sysdeps/unix/sysv/linux/arm/nptl/bits/atomic.h のほうを参考にする手もあるのかな。v5/v6両用のコードにできる模様。
なおARMの命令は、「RealViewコード生成ツールv2.0」の「アセンブラガイド」をダウンロードすれば全て載ってます。無料です。Web版もあったかも。
2. スタックトレース関数を書く (src/stacktrace_armv5t-inl.h)
次に、スタックのバックトレースを行なう関数 GetStackTrace() を書きます。バックトレースというのは、(gdb) bt すると表示されるあれのことです。この関数も1.同様、シグナルハンドラから呼ばれるので、シグナルセーフにつくるのがベターです。google-perftools-0.93/INSTALL 等にも、デッドロックの危険があるからGetStackTrace()でmallocは呼ばない方が良いのだと注記されていました。バックトレースを行なう関数というと、glibcにそのままの名前の関数 backtrace() というのがあり、#include
フレームポインタが省略されていないと仮定すると、arm-gccでコンパイルしたコードの、関数の入口部分は次のようになってます。
% armv5tel-redhat-linux-gnueabi-objdump -d example
...
0000853c <main>:
853c: e1a0c00d mov ip, sp
8540: e92dd800 push {fp, ip, lr, pc}objdumpのバージョンによっては stmdb sp!, {fp, ip, lr, pc} と表示される場合もありますが、単に表記が違うだけでマシン語のバイト列は同じです。2行目のpushが実行された後のスタックのレイアウトは、こんな感じです。なので、bt関数は
#define OFFSET_FP_TO_SAVED_FP (-3)
#define OFFSET_FP_TO_LR 2
static void **NextStackFrame(void **old_sp) {
void **new_sp = (void **) *old_sp;
// initial value of fp regigster (at _start()) is 0x0.
if ((uintptr_t)new_sp == 0) return NULL;
new_sp += OFFSET_FP_TO_SAVED_FP;
// Check that the transition from frame pointer old_sp to frame
// pointer new_sp isn't clearly bogus
if (new_sp <= old_sp) return NULL;
if ((uintptr_t)new_sp - (uintptr_t)old_sp > 100000) return NULL;
return new_sp;
}
int GetStackTrace(void **result, int max_depth, int skip_count) {
void **sp;
int n = 0;
uintptr_t fp = 0;
__asm__ __volatile__ ("mov %0, fp" : "=r"(fp));
sp = (void **)fp;
if ((uintptr_t)sp == 0x0) return 0;
sp += OFFSET_FP_TO_SAVED_FP;
while (sp && n < max_depth) {
if ((uintptr_t)sp > 0xc0000000) {
break;
}
if (skip_count > 0) {
skip_count--;
} else {
result[n] = *(sp + OFFSET_FP_TO_LR);
++n;
}
sp = NextStackFrame(sp);
}
return n;
}でよろしいのではないかと。説明端折りすぎ。x86版を多少書き換えただけです。インラインアセンブラ部分など。
3. シグナルを受信したときのPCの値を得る関数を書く (src/get_pc.h)
最後に、シグナルを食らったとき、どの命令を実行していたか(program counterの値)を戻す関数GetPCを書きます。シグナルハンドラをsigaction()で登録する際、SA_SIGINFOというフラグを指定しておくと、シグナルハンドラの第三引数としてucontext_t*という型の構造体を得ることができますので、この構造体の中に保存されているPC値を戻してやればOKです。handlerのシグネチャ等の詳細はman sigaction。
inline void* GetPC(const ucontext_t& signal_ucontext) {
return (void*)signal_ucontext.uc_mcontext.arm_pc;
}これだけ。ucontext_tの内容は、sys/ucontext.h (glibc-ports-2.7/sysdeps/unix/sysv/linux/arm/sys/ucontext.h) とか、asm/sigcontext.h (linux-2.6.2x/include/asm-arm/sigcontext.h) を参照すればわかります。
ただ、カーネルが古いと(?)、SA_SIGINFOのucontext_t経由ではPCの値が取れないようです。手元の2.6.10カーネルではダメでした。catchsegvコマンドのソースコードである glibc-2.7/debug/segfault.c を参考に、SA_SIGINFOを指定しないでsigaction()し、glibc-ports-2.7/sysdeps/unix/sysv/linux/arm/sigcontextinfo.h のSIGCONTEXTマクロやGET_PC()マクロを使う方法なら、きちんとPCを取ることができました。詳しい事情をだれか教えて的。とりあえず、configureオプションで、こちらの実装も選択できるようにしておきました。詳細はパッチ見てください。
以上です。以下はおまけ。
perftoolsのしくみと、i386向けGetPC実装について
arm版GetPC関数の実装は上に書いたとおりの簡素なものですが、実はx86版のGetPCの実装はもうすこし凝っています。その概要をメモとして残しておきます。google-perftoolsは、測定対象のプログラムにLD_PRELOAD等で割り込んで、main関数の前でsetitimer(ITIMER_PROF)システムコールを呼び、測定対象プロセスに一定周期でSIGPROFシグナルが飛んでくるようにします。SIGPROFのハンドラもperftoolsが用意していて、その中でさきほどのGetStackTrace()を使ったbacktrace処理が行なわれます。main()がfoo()を呼び、foo()がbar()を呼び、bao()の中でSIGPROFを食らったとすると、backtraceは当然、
prof_handler() <-- シグナルハンドラ bar() foo() main()
となるわけですが、bar()関数のプロローグ処理の前や、エピローグ処理の後にシグナルを食らうと、foo関数用のスタックフレームが構築前あるいは解体後であるため、バックトレースが
prof_handler() <-- シグナルハンドラ foo() main()
となってしまいます。
perftoolsは、バックトレースの先頭の2関数を無視し、残りのトレースとGetPC()で取得したPCが指している関数をつないでコールグラフを作成するので、後者の場合だと、mainが直接barを呼ぶ、おかしなコールグラフが作成されてしまいます。これを避けるために、x86版のGetPCでは、フレーム構築前・解体後にGetPCされたときは、bar内のアドレスでは無く、foo内のアドレスを戻すように細工が行なわれます。arm版ではこの処理は行なっていません。TODOということで。
GetStackTrace()とフレームポインタ省略について
GetStackTrace()は、スタックに保存されたfp(フレームポインタ)を辿っているだけですので、もし解析対象のプログラムや、google-perftools自身が -fomit-frame-pointer (フレームポインタ省略) でコンパイルされていると、うまく動きません。ARM用のGCCは、x86とは違って -O2 で最適化すると自動で -fomit-frame-pointer してしまうので、注意が必要です。明示的に -O2 -fno-omit-frame-pointer で両者をコンパイルしてやらないとだめです。google-perftoolsでは、./configure --enable-frame-pointer でそのようなコンパイルが行なわれることにしているようでしたので、arm portもそれに従いました。
詳しくありませんがおそらく、-fomit-frame-pointerされたバイナリであっても、ELFの.eh_frameセクションの情報(DWARFv3 CFI?)を見ればバックトレースできるのだと思います。実際armなgdbは-O2 binaryでも平気でbt可能ですし。perftoolsでは、他のarchでもそこまで頑張っていないので、arm版でもfpを辿るだけの素朴な実装にしました。perftoolsはlibunwindによるスタック巻戻しにも対応しているので、もしlibunwindがarmに対応しているなら、そっちを使う手もあるかもですね。あーだめか。http://www.nongnu.org/libunwind/download.html によると A complete open-source implementation of the libunwind API currently exists for IA-64 Linux and is under development for Linux on x86, x86-64, and PPC64.だわ、ダメですね。
- (参考) fryskというツールの作者さんによる.eh_frame周辺の解説。RedHatの人かしら。
arm用の、プリインストールなDSO (/lib/libc.so とか) は、大抵-O2でコンパイルされているとおもいますので、そういうDSO内でSIGPROFが配送された場合にはコールグラフが少しおかしなものになります。これも制限事項ということで。
CASの件
1,のCASですが、思わずglibcを全面的に参考にしてコード書いてしまったのでperftoolsのライセンス的にどうなのよという話も。もっと無難な方法、ふがふが.hを#includeしてほげほげ関数使えばOKだよ的な方法があれば教えてください。ちょっと調べた限りでは、
- linux kernelのasm-arm/atomic.h は、ユーザプログラムからは使えない
- pre-v6向けコードでは、非SMP前提でlocal_irq_save()して割り込みを無効にしている為
- Qtにそれらしい関数群がある (/usr/include/Qt/qatomic_arm.h） けど、TASだけでCASはなさげだし、Qtに依存するのもなんだかなー
- libstdc++のatomicity.h (/usr/lib/gcc/armv5tel-redhat-linux-gnueabi/4.1.2/include/c++/bits/atomicity.h) にもCASはない
- __gnu_cxx::__exchange_and_add()ならあるけど、逆アセンブルした限りではCで書かれたnon-atomic stubをコンパイルしたコードのようで、glibcのnear-atomic CASのほうがだいぶマシ。
- glibcのソースコードにはarm用のatomic.h (or 古めのglibcだと atomicity.h) が含まれていて、near-atomicなわけだけど、私の使っているtoolchainのinclude directory以下にはどちらもインストールされていない
- atomic_ops projectもARMは対応してない
という感じでうまい策がありません。何か根本的な勘違いがある気もしますが...。
v5のswpb命令でバイナリセマフォは問題なく実装でき、かつperftoolsではAcquire_CompareAndSwap()とRelease_Store()はスレッドの排他にしか使われないので、いっそのことAcquire_CompareAndSwap()をswpbなセマフォのP操作に、Release_Store()を同V操作に読みかえてしまおうか。。。汚いけど。
その他
patchの動作確認は、qemu-system-arm上でFedora Core 6 for ARMを動作させて行ないました。カーネルは http://fedora-arm.wantstofly.org/qemu/zImage-versatile-2.6.22 、rootfsは http://fedora-arm.wantstofly.org/rootfs/fc6-arm-root-with-gcc.tar.bz2 、クロスコンパイラ類は http://fedora-arm.wantstofly.org/cross/latest/i386/*.rpm を使い、How To: Running Fedora-ARM under QEMU に従って起動させたものです。Fedora-ARMは、yumも使えてなかなか快適です。ArmadilloとかAndroid上でも動くんじゃないかと思います。LinuxThreadsを使っている場合には、signal回りで若干の追加コードがいるかなぁ。あとでそういうARMボードの上で動かして試すこと＞私。
*1:少し考える or SPIN等で検査すれば例を提示できそうですが眠いので略。ちなみにv6以降ではswp/swpbは非推奨命令。後述の qatomic_arm.hみたいに、グローバルなロックをひとつだけ抱えて、どこでコンテキストスイッチしても問題の起きないv5用CASを実装する手もあるのかと思いますが、バイナリセマフォを実現するためのCASの中で別の方法(swpb)で実装したバイナリセマフォをP/Vするのは激しくイマイチな感じなのでやめときます。おかしなこと書いていたらすみません。関係ないけど、NetBSDではrestartable atomic sequenceという仕組みでuser/kernelが協調することで低機能なCPUでもCAS等を実装可能にしているんですね。atomic sequence中にコンテキストスイッチすると、カーネルがそれを検出してatomic seqを最初から実行しなおさせると。コンテキストスイッチしなければランタイムコスト0。http://db.usenix.org/publications/library/proceedings/usenix03/tech/freenix03/full_papers/mcgarry/mcgarry_html/index.html このアイディアは素敵だなぁ。
PIE randomization
前の記事にコメントをいただいて、PIE randomizationのことを思い出したので、ちょい実験。PIEな実行ファイルは、どのアドレスにロードしても動くので、どこにロードするかはカーネルのfs/binfmt_elf.cあたりが適当に決めることが可能なわけですが、私の使ってるカーネルさんはPIEを毎回異なるランダムなアドレスにロードする(PIE randomization, aka ASLR)のか、それともどこか固定なアドレスにロードするのかを確かめたということです。
というのも、私は主にFedoraを使っているのですが、2.6.18-1.2798.fc6 では効いていたPIEのrandomizationが 2.6.22.4-45.fc6 とか 2.6.22.9-61.fc6 (今日現在の最新版) では効かなくなっておりまして。カーネルのメインラインのほうでも2006年末から似たようなコードのcommitとrevertを2-3回繰り返しているもので*1、結局どうなったんかなーと思い。昨日Fedoraの8を入れたので状況確認と。確認作業は簡単です。
#include <stdio.h> int main() { here: printf("%p\n", &&here); // mainのアドレスでもいいけど return 0; }
をFedora8の2.6.23.1-49.fc8で実行するだけ。
% gcc -fPIE -pie pie.c % ./a.out 0xb7fca539 % ./a.out 0xb7f23539 % ./a.out 0xb7f45539 % ./a.out 0xb7f06539
お、またrandomizeが効くようになってる。src.rpmを見ると、linux-2.6-execshield.patch にそういうコードが入っているようですね。binfmt_elf.cへの数行パッチ。以上、思い出したので実験＆メモでした。いま翻訳している本*2 の事前調査も兼ねつつ。あ、もうひとつ、protection mechanismといえば、glibc-2.7で -D_FORTIFY_SOURCE=2がCだけでなくC++にも対応したので、Binary Hacksの記述が少し古くなりました。
50行straceもどき
すこし前に、straceコマンドもどきを50行くらいで書いてみたことがあるので、それを貼ってみまーす。いきなりコード。あ、C99です。
// strace_modoki.c: Linux/x86専用です。x86_64カーネルでは-m32でコンパイルしても動きません。 #include <stdio.h> #include <unistd.h> #include <sys/ptrace.h> #include <sys/types.h> #include <sys/wait.h> #include <asm/user.h> #include <asm/ptrace.h> int main() { int i; static const char* syscallstr[1000] = {0}; for(i = 0; i < 1000; ++i) syscallstr[i] = "???"; syscallstr[0] = "restart_syscall"; syscallstr[1] = "exit"; syscallstr[2] = "fork"; /* 略 */ syscallstr[321] = "signalfd"; syscallstr[322] = "timerfd"; syscallstr[323] = "eventfd"; if (!fork()) { // child ptrace(PTRACE_TRACEME, 0, 0, 0); execve("/bin/echo", (char *const []){ "/bin/echo", "123", NULL }, (char *const []){ NULL }); _exit(-1); } else { int st, in_syscall = 1; // うまく動かなかったら1を0にしてみてください :-) if (in_syscall) printf("enter execve() "); wait(&st); // wait for exec while (ptrace(PTRACE_SYSCALL, p, 0, 0) == 0) { // cont until syscall enter/leave wait(&st); // wait for syscall enter/leave if(WIFEXITED(st)) { puts("= ?"); break; } long orig_eax = ptrace(PTRACE_PEEKUSER, p, 4 * ORIG_EAX, 0); struct user_regs_struct regs; ptrace(PTRACE_GETREGS, p, 0, ®s); if (in_syscall == 0) { in_syscall = 1; printf("enter %s(0x%lx) ", (orig_eax >= 0 && orig_eax < 1000) ? syscallstr[orig_eax] : "???", regs.ebx); } else { in_syscall = 0; printf("= %ld\n", regs.eax); } fflush(stdout); } } return 0; }
冒頭の syscallstr[nnn] = "xxx"; の部分は、/usr/include/asm/unistd.h をもとに、適当に変形して生成してください。余談ですがこのファイルをたまにのぞくと新規に追加されたシステムコールがわかって楽しいです。signalfdとか。エラーチェック他全部省略の手抜きコードです。うまく動かなかったらゴメンナサイ。
これを実行すると、まずfork()して子プロセスで /bin/echo 123 を実行し、親プロセスがその子の様子をptraceで観察します。出力はこんな感じになります。
% gcc -Wall -W strace_modoki.c % ./a.out enter execve() = 0 enter brk(0x0) = 164818944 enter access(0x4bee8f) = -2 enter open(0x4bf077) = 3 enter fstat64(0x3) = 0 enter mmap2(0x0) = -1208172544 enter close(0x3) = 0 enter open(0xb7fd7a08) = 3 enter read(0x3) = 512 enter fstat64(0x3) = 0 enter mmap2(0x0) = -1208176640 enter mmap2(0x4c5000) = 5001216 enter mmap2(0x5ff000) = 6287360 enter mmap2(0x602000) = 6299648 enter close(0x3) = 0 enter mmap2(0x0) = -1208180736 enter set_thread_area(0xbfac95c4) = 0 enter mprotect(0x5ff000) = 0 enter mprotect(0x4c1000) = 0 enter munmap(0xb7fcc000) = 0 enter brk(0x0) = 164818944 enter brk(0x9d50000) = 164954112 enter fstat64(0x1) = 0 enter mmap2(0x0) = -1208119296 enter write(0x1) 123 = 4 enter close(0x1) = 0 enter munmap(0xb7fd9000) = 0 enter exit_group(0x0) = ? %
全くpretty printされていませんが、一応straceっぽい出力が得られています。ptraceの詳細については、man 2 ptraceや、2002年のこの記事あたりが参考になると思います。
構造体のサイズ違いで悩んだのでリンク時に検出
先日、次のようなC++のクラスが原因で少々悩みました。
struct A { #ifdef V2 int bar_; /* バージョン2以降でしか使わないメンバ変数(らしい) */ #endif int foo_; /* 以下略 */ };
このAを使っている.cppの一部は、g++ -DV2でコンパイルされており、残りは-DV2なしでコンパイルされていたのです。sizeof(A)が異なるオブジェクト同士がリンクされてしまい、まずいことになっていました。たとえば、次のようなa.hと、
// a.h struct A { #ifdef V2 int bar_; #endif int foo_; A(); int getFoo() const { return foo_; } void setFoo(int foo); };
a.cpp, main.cpp を用意して、
// a.cpp #include "a.h" A::A() : #ifdef V2 bar_(0), #endif foo_(0) {} void A::setFoo(int foo) { foo_ = foo; }
// main.cpp #include "a.h" #include <cstdio> int main() { A a; a.setFoo(123); std::printf("foo=%d\n", a.getFoo()); }
一方の.cppにしか -DV2 をあたえないでコンパイルを行うと、
% g++ -DV2 -c a.cpp <-- sizeof(A) == 8 % g++ -c main.cpp <-- sizeof(A) == 4 % g++ a.o main.o % ./a.out foo=0 <--- 123ではなく0が出力される
main()の2行目でセットした値123がどこかに消えてしまう結果となります。この場合ですと、setFoo()ではきちんとA::foo_に値をセットしているものの、getFoo()では、誤って A::bar_ から値を読む結果になってしまっています。なお、操作する相手が整数でなくポインタだったりすると、不可解なクラッシュが起きたりすると思います。まぁ、（これも）よくある事態な気がしますが、構造体Aを書いたのが自分ではなく、また今回は馴染の無いビルドシステムを相手にしていたこともあり、原因がここだと判明するまでに少し時間がかかってしまったのでした。
(追記) あ、今たまたま眺めたGCCのWiki (http://gcc.gnu.org/wiki/Visibility) にも、... if you forget your preprocessor defines in just one object file ... なんて記述があるなぁ。やはりハマるのは私だけではないのだなー。
というわけで、また同じ事で悩むのが嫌なので、「ひとつのクラス/構造体Aについて、sizeof(A)の値が異なる.o同士がリンクされたこと」を自動的に検出できないか考えました。手を入れるのはクラス/構造体の定義された.hと.cppだけという条件で。
構造体のサイズ違いの自動検出 (ランタイム)
まず、ランタイムに検出する方法を考えました。これはごく簡単に実現できそうです。
// a.hへ追記 __attribute__((constructor)) static void size_checker() { extern std::size_t sizeof_A; assert(sizeof_A == sizeof(A)); }
// a.cppに追記 std::size_t sizeof_A = sizeof(A); // 正しい(基準となる)サイズを覚える
これで、もしsizeof(A)の値が異なる.o同士がリンクされていると、実行時にmain()の前でチェックが行われ、問題があればassertで止まります。止まった場所をgdbのbacktraceやtracefなどで :-) 調べれば、原因箇所がわかるはずです。
例:
% g++ -DV2 -ggdb3 -c a.cpp % g++ -ggdb3 main.cpp a.o <-- -DV2をわざと付け忘れてみる % ./a.out <-- 実行時にmain()より前にassertで止まる a.out: a.h:22: void size_checker(): Assertion `sizeof_A == sizeof(A)' failed. % tracef -ClT ./a.out <-- どこで止まったか調べる (main.cppのコンパイル方法がまずいとわかる) [pid 1613] +++ process 1613 attached (ppid 1612) +++ [pid 1613] === symbols loaded: './a.out' === [pid 1613] ==> _start() at 0x00000000004004f0 [pid 1613] ==> __libc_csu_init() at 0x00000000004006f0 [pid 1613] ==> _init() at 0x0000000000400480 [pid 1613] ==> call_gmon_start() at 0x000000000040051c [pid 1613] <== call_gmon_start() [rax = 0x0] [pid 1613] ==> frame_dummy() at 0x00000000004005a0 [pid 1613] <== frame_dummy() [rax = 0x0] [pid 1613] ==> __do_global_ctors_aux() at 0x0000000000400780 [pid 1613] ==> global constructors keyed to _ZN1AC2Ev() at 0x00000000004006cc [/tmp/a.cpp:13] [pid 1613] ==> size_checker()() at 0x00000000004006a0 [/tmp/a.h:20] [pid 1613] <== size_checker()() [rax = 0x8] [pid 1613] <== global constructors keyed to _ZN1AC2Ev() [rax = 0x8] [pid 1613] ==> global constructors keyed to main() at 0x0000000000400634 [/tmp/main.cpp:11] <-- main.cppで不一致発生 [pid 1613] ==> size_checker()() at 0x0000000000400608 [/tmp/a.h:20] a.out: a.h:22: void size_checker(): Assertion `sizeof_A == sizeof(A)' failed. [pid 1613] --- SIGABRT received (#6 Aborted) --- [pid 1613] +++ process 1613 (ppid 1612) KILLED by SIGABRT (#6 Aborted) +++ tracef: done
調べたい対象がAだけでなく複数あるなら、templateを使ってライブラリ化しておくとよいとおもいます。グローバルなオブジェクトのコンストラクタでチェックを行います。こちらは__attribute__を使っていないので、MSVCなど、g++以外のコンパイラでも動くと思います。
// size_check_r.h #include <cassert> namespace hoge { template <typename T> struct SizeChecker { SizeChecker() { assert(size_ == sizeof(T)); } static std::size_t size_; }; } #define CHECK_SIZE(T) namespace { hoge::SizeCheckerR<T> sizeof_ ## T ## _checker_; } #define DEF_PROPER_SIZE(T) template<> std::size_t hoge::SizeChecker<T>::size_ = sizeof(T)
これを用意して、
// a.h #include <size_check_r.h> // 中略 CHECK_SIZE(A);
および
// a.cpp // 中略 DEF_PROPER_SIZE(A);
と。
構造体のサイズ違いの自動検出 (リンク時)
どうせなら、実行時ではなくリンク時に検査できたらよりgoodです。やってみます。まず、a.hをリンクすると勝手に、「sizeof(A)の値をシグネチャ(シンボル名)に含むような関数」を呼ぶようにします。
// a.hに追記 (boost/mpl/int.hpp をインクルードしてください) __attribute__((constructor)) static void size_checker() { extern void size_checker_helper_(boost::mpl::int_<sizeof(A)>); size_checker_helper_(boost::mpl::int_<sizeof(A)>()); }
関数名にsizeof(A)の値(4とか8とか)を含むようにするのは難しいので、整数値を型に写像する boost::mpl::int_<> を用いて、関数の引数に含めるようにしています。boost::mpl::int_<> は、Lokiでいう Int2Type です。
そして、a.cppでのみ、(a.cppでの)sizeof(A)の値をシグネチャに含む関数を定義します。
// a.cppにのみ追記 void size_checker_helper_(boost::mpl::int_<sizeof(A)>) {}
こうしておくと、
% g++ -DV2 -c a.cpp ; g++ main.cpp a.o /tmp/ccQTotL4.o: In function `size_checker()': main.cpp:(.text+0x7a): undefined reference to `size_checker_helper_(mpl_::int_<4>)' collect2: ld returned 1 exit status
みたいな感じで、「(a.cppでのsizeof(A)は8だったのに) main.cppでは4だったぞ！」とリンクタイムにsizeof(A)の不一致を叱ってもらえます。ちょっとエラーメッセージがわかりにくいですが。。
前と同じようにライブラリ化してみます。
// size_check_l.h #include <boost/mpl/int.hpp> #include <boost/mpl/identity.hpp> namespace hoge { template <typename T> struct SizeChecker { SizeChecker() { extern void size_checker_helper_(typename boost::mpl::identity<T>, typename boost::mpl::int_<sizeof(T)>); size_checker_helper_(boost::mpl::identity<T>(), boost::mpl::int_<sizeof(T)>()); } }; } #define CHECK_SIZE(T) namespace { hoge::SizeChecker<T> sizeof_ ## T ## _checker_; } #define DEF_PROPER_SIZE(T) void size_checker_helper_(boost::mpl::identity<T>, boost::mpl::int_<sizeof(T)>) {}
boost::mpl::identity
構造体のサイズ違いの自動検出 (リンク時 その2)
上の方法だと、検出はリンク時に行えますが、実行時にmain関数の前で余計なコードが走ってしまう*1のが気になります。そこを改良。
// size_check_l2.h (最終版) #include <boost/mpl/int.hpp> #include <boost/mpl/identity.hpp> #define CHECK_SIZE(T) \ extern void size_checker_helper_(boost::mpl::identity<T>, boost::mpl::int_<sizeof(T)>); \ namespace { \ void (* sizeof_ ## T ## _checker )(boost::mpl::identity<T>, boost::mpl::int_<sizeof(T)>) \ __attribute__((used)) \ = size_checker_helper_; \ } #define DEF_PROPER_SIZE(T) \ void size_checker_helper_(boost::mpl::identity<T>, boost::mpl::int_<sizeof(T)>) {}
size_checker_helper_関数を呼ぶのをやめて、その関数へのポインタを持つだけにしました。これで、ランタイムコストは0で、ポインタn個と、チェック関数1つ分のバイナリサイズの肥大だけで済みます。ポインタを無名名前空間から出し、単にstaticな変数としてもよいです。
__attribute__((used)) は、ポインタがコンパイラに要らない子扱いされないようにする対策です（コンパイル時に消えてなくなると、リンク時のチェックが効かなくなります...）。MSVCではどうしたらいいのかなぁ。
% nm -C --format=posix a.out | grep check size_checker_helper_(boost::mpl::identity<A>, mpl_::int_<8>) T 00000000004005f0 0000000000000002 (anonymous namespace)::sizeof_A_checker d 0000000000600a70 0000000000000008 (anonymous namespace)::sizeof_A_checker d 0000000000600a78 0000000000000008 % objdump -Cd a.out | lv ... 00000000004005f0 <size_checker_helper_(boost::mpl::identity<A>, mpl_::int_<8>)>: 4005f0: f3 c3 repz retq ...
私の環境(x86_64なLinux)では、チェック関数は2バイトでした。これは余談ですが、nmを --format=posix あるいは -fp オプション付きで使うと、各シンボルのサイズを出せて便利だと最近認識し、実行ファイルの中から、自動で巨大なグローバル変数をみつけたり、自動で巨大な関数を見つけたりするのに使ってます。ちょっとしたセルフチェックとして。
ポインタn個と関数を特別にでっちあげたセクションに配置するように__attribute__((section))しておき、あとでそこをstrip -Rしてしまう手もあるかもしれません。
// size_check_l3.h #include <boost/mpl/int.hpp> #include <boost/mpl/identity.hpp> #define CHECK_SIZE(T) \ extern void size_checker_helper_(boost::mpl::identity<T>, boost::mpl::int_<sizeof(T)>); \ namespace { \ void (* sizeof_ ## T ## _checker )(boost::mpl::identity<T>, boost::mpl::int_<sizeof(T)>) \ __attribute__((section(".size_checker"), used)) \ = size_checker_helper_; \ } #define DEF_PROPER_SIZE(T) \ __attribute__((section(".size_checker_text"))) \ void size_checker_helper_(boost::mpl::identity<T>, boost::mpl::int_<sizeof(T)>) {}
% strip -R .size_checker_text -R .size_checker a.out
ちょっと面倒かな。
boostを使わない
boostを使わない/使えない場合は、
namespace boost { namespace mpl { template<int N> struct int_ {} template<typename T> struct identity {}; }}
などと自分でどこかに書いておいて、こちらを使えばOKです。
まとめ
またどーでもいいことで長文になってしまった。。まとめます。
// size_check.h #include <boost/mpl/int.hpp> #include <boost/mpl/identity.hpp> #define CHECK_SIZE(T) \ extern void size_checker_helper_(boost::mpl::identity<T>, boost::mpl::int_<sizeof(T)>); \ namespace { \ void (* sizeof_ ## T ## _checker )(boost::mpl::identity<T>, boost::mpl::int_<sizeof(T)>) \ __attribute__((section(".size_checker"), used)) \ = size_checker_helper_; \ } #define DEF_PROPER_SIZE(T) \ __attribute__((section(".size_checker_text"))) \ void size_checker_helper_(boost::mpl::identity<T>, boost::mpl::int_<sizeof(T)>) {}
という10行くらいのコードを書きました。
// test.h #include "size_check.h" struct A { #ifdef V2 char bar_; /* バージョン2以降でしか使わないメンバ変数(らしい) */ #endif int foo_; }; CHECK_SIZE(A); // 追記
// test.cpp #include "test.h" DEF_PROPER_SIZE(A); // 追記
もし、#ifdefでサイズの変わる構造体や、packされる可能性のある構造体を作成したり見かけたりしたら、今回書いたマクロを使って、そこに CHECK_SIZE(), DEF_PROPER_SIZE() と書いておくと、次のように、間違ったMakefile、不可解なビルドシステム...に起因するよくわからない不具合をサクっと検出することができ、貴重な時間を無駄にしなくて済むかもしれません。。
例:
// main.cpp #include "test.h" int main() {}
% g++ -DV2 -O2 -c test.cpp ; g++ -O2 -c main.cpp ; g++ test.o main.o main.o:(.data+0x0): undefined reference to `size_checker_helper_(boost::mpl::identity<A>, mpl_::int_<4>)' collect2: ld returned 1 exit status % g++ -O2 -c test.cpp ; g++ -DV2 -O2 -c main.cpp ; g++ test.o main.o main.o:(.data+0x0): undefined reference to `size_checker_helper_(boost::mpl::identity<A>, mpl_::int_<8>)' collect2: ld returned 1 exit status
-DV2の有無が一致していないと怒られる。
% g++ -DV2 -O2 -c test.cpp ; g++ -DV2 -O2 -c main.cpp ; g++ test.o main.o % g++ -O2 -c test.cpp ; g++ -O2 -c main.cpp ; g++ test.o main.o
一致していると怒られない。
% g++ -DV2 -O2 -fPIC -shared -o test.so test.cpp % g++ -O2 main.cpp test.so /tmp/ccaJzoMv.o:(.size_check+0x0): undefined reference to `size_checker_helper_(boost::mpl::identity<A>, mpl_::int_<4>)' collect2: ld returned 1 exit status % g++ -DV2 -O2 main.cpp test.so %
構造体がDSO (DLL) の中に格納されている場合でも、問題なくサイズ不整合が検出可能。
% g++ -fpack-struct -DV2 -O2 -c test.cpp ; g++ -DV2 -O2 -c main.cpp ; g++ test.o main.o main.o:(.data+0x0): undefined reference to `size_checker_helper_(boost::mpl::identity<A>, mpl_::int_<8>)' collect2: ld returned 1 exit status % g++ -DV2 -O2 -c test.cpp ; g++ -fpack-struct -DV2 -O2 -c main.cpp ; g++ test.o main.o main.o:(.data+0x0): undefined reference to `size_checker_helper_(boost::mpl::identity<A>, mpl_::int_<5>)' collect2: ld returned 1 exit status % g++ -fpack-struct -DV2 -O2 -c test.cpp ; g++ -fpack-struct -DV2 -O2 -c main.cpp ; g++ test.o main.o %
構造体のpack指定(-fpack-struct や #pragma pack(push,N))の不整合も検出可能。以上、「いまさらMPLを覚えたのでなんでもそれで叩いてみる」シリーズ第2弾(?)でした。
RFC
なにかもっとよさげな方法があれば教えてください。stripに頼らずともバイナリ肥大/ランタイムコストが0な奴とか、もっとずっとシンプルな方法とか、boostにそういうのあるよ、とか。
クラスの作成者が何もせずともsizeofの整合性を確認できたりしないかな。うーん、全ての*.oから、デバッグ情報として書かれているクラスのサイズをダンプしておいて比較..とかかなぁ。いまやってるDWARF3の勉強用の題材としてはよさげだけど、コンパイル以外の作業をしないと発見できないというのはヘボいな。
*1:tracefで確認できます <- しつこい
ついカッとなって実行バイナリにパッチ
とある都合で、ソフトウェア開発の際にソースコードの提供されていないツールを使うことになりました。x86なLinux上で動く、ちょっとしたtoolchainです。が、そのツールの処理速度が遅く、入力サイズに対して、結果が出てくるまでの時間がどうもO(N^2)かそれよりひどい。遅くてイライラするので、昨晩ついカッとなってパッチを当てました。そのメモです。また、ありがちな事態(?)な気もするので、みなさんどうしてるのかなー的なお伺いも兼ねて。
ボトルネックの特定
そのツール(以下A)の実行バイナリはstripされておらず.symtabが残っていました。のでまず、どこが遅いのかgoogle-perftoolsをLD_PRELOADしてそのソフトウェアを実行し、実行プロファイルを取りました。すると、嬉しいことにある一つの関数(以下F)で全体の90%以上の時間を消費していることがわかりました。関数Fは、Aの実行バイナリの中に含まれており、DSO(DLL)内の関数では無いので、LD_PRELOAD一発で高速版に置き換えたりはできないのですが、まぁどうにかできそうな範疇の予感です。
# yum install graphviz gv
# yum localinstall google-perftools-0.93-1.i386.rpm
% CPUPROFILE=/tmp/profile.out LD_PRELOAD=/usr/lib/libprofiler.so.0 ./A
PROFILE: interrupts/evictions/bytes = 22379/6911/720720
% pprof ./A /tmp/profile.out
Welcome to pprof! For help, type 'help'.
(pprof) top
Total: 22379 samples
22364 99.9% 99.9% 22364 99.9% F
13 0.1% 100.0% 22378 100.0% msort_with_tmp
1 0.0% 100.0% 1 0.0% memcpy
1 0.0% 100.0% 22379 100.0% main
0 0.0% 100.0% 22379 100.0% _start
0 0.0% 100.0% 22364 99.9% G
0 0.0% 100.0% 22378 100.0% qsort
0 0.0% 100.0% 22379 100.0% __libc_start_main
(pprof) gv <-- ざっくりとしたコールグラフを確認次に、どこからその遅い関数Fが呼ばれているのか、callgrindを使って正確に調べました。callgrind上でのソフトウェアの動作はかなり遅くなりますので、ただでさえ遅いこのソフトのプロファイルを取るのには何時間もかかりました。もちろん、Aを objdump -d で逆アセンブルしてFの呼び出し箇所を静的に調べる*1こともできますが、callgrindを使用すると、呼び出し箇所だけでなく、それぞれの箇所を何回通ったかもわかり、より便利です。
# yum install valgrind kdesdk % valgrind --tool=callgrind ./A ==18353== Callgrind, a call-graph generating cache profiler. ==18353== Copyright (C) 2002-2007, and GNU GPL'd, by Josef Weidendorfer et al. ==18353== Using LibVEX rev 1732, a library for dynamic binary translation. ==18353== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP. ==18353== Using valgrind-3.2.3, a dynamic binary instrumentation framework. ==18353== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al. ==18353== For more details, rerun with: -v ==18353== ==18353== For interactive control, run 'callgrind_control -h'. ==18353== ==18353== Events : Ir ==18353== Collected : 128019689295 ==18353== ==18353== I refs: 128,019,689,295 % kcachegrind ./callgrind.out.18353 & <-- 詳細なコールグラフを確認
callgrindの結果をkcachegrindでvisualizeしたものと、Aの重要な部分を逆アセンブルしたリストを眺めた*2ところ、要するにこのソフトウェアは、細かい部分を捨象すると次のようなつくりになっており、遅いのだという結論を得ることができました。
/* tooooslow.c */ #include <stdlib.h> typedef struct { int data; } S; #define N 50000 /* 入力サイズ */ S* input = 0; /* 入力データ */ int F(const S* s1, const S* s2) { /* この子が遅い */ int i, dmy = 0; for (i = 0; i < N; ++i) { /* 実際は、input, s1->data, s2->data を用いた O(N) の計算 */ ++dmy; } return (s1->data) - (s2->data); } int G(const void* s1, const void* s2) { return F((const S*)s1, (const S*)s2); } int main() { int i; input = calloc(N, sizeof(S)); for(i = 0; i < N; ++i) input[i].data = (N - i) % 128; /* 適当に初期化 */ qsort(input, N, sizeof(S), G); exit(0); }
objdump -dしたところ、Gは、mainのqsort以外では使われていません。また、Fの内部でinputに変更が加わることはなく、そのためFは、少なくともmainのqsortから呼ばれる場合については、(s1->data, s2->data)の組が同じなら戻り値も同じ、算数で言うところの関数、GCCでいうところの__attribute__((pure))な関数です。このFをどうにかします。
パッチ方法の検討
Fの処理オーダーを改善すれば、このツールAが高速化すると見込めるわけですが、Fのアルゴリズムを、ソースコードなしでO(N)からO(1)に改善するのは、ちょっと一晩では難しいと思ったので、Fを次のようにラップすることで妥協することにしました。
int F_wrap(const S* s1, const S* s2) { key = 連結(s1->data, s2->data); if (hash.ある?(key)) { return 覚えてた奴; } ret = もとのF(s1, s2); hash.おぼえる(key, ret); return ret; }
また、
という俺ルールにしました。私はこれらの技術が達人のみなさんと比べてそんなに流暢に使えるわけでもなく、手を出すと一晩では仕上らない予感がしたからです。なお、これらを使った格好いい方法はBinary Hacksに載ってるような気もします。
で、このルールの元、次の方法でパッチすることにしました。
- LD_PRELOADでF_wrapをAのプロセス空間に滑り込ませる
- Gの書き換えは、__attribute__((constructor)) な関数もPRELOADしておくことで実行時にmainの前で行う。
これに必要な情報は、Aをobjdump -dすれば収集できます。
% objdump -d tooooslow | lv ... 080483e4 <F>: 80483e4: 55 push %ebp 80483e5: 89 e5 mov %esp,%ebp 80483e7: 83 ec 10 sub $0x10,%esp ... 0804841d <G>: 804841d: 55 push %ebp 804841e: 89 e5 mov %esp,%ebp 8048420: 83 ec 08 sub $0x8,%esp 8048423: 8b 45 0c mov 0xc(%ebp),%eax 8048426: 8b 55 08 mov 0x8(%ebp),%edx 8048429: 89 44 24 04 mov %eax,0x4(%esp) 804842d: 89 14 24 mov %edx,(%esp) 8048430: e8 af ff ff ff call 80483e4 <F> <-- 書き換える場所 ...
パッチ
こんな感じになりました。なお、高速化(hash)部分は省略し、F_wrap()からF()を呼び、F()の戻り値をprintfするだけのコードにしてあります。
// bin_patch.cpp #ifndef _GNU_SOURCE #define _GNU_SOURCE #endif #include <cstdio> #include <cstdlib> #include <cassert> #include <stdint.h> #include <sys/mman.h> #include <dlfcn.h> #define F 0x80483e4U #define CALL_F 0x8048430U #define PAGESIZE 4096 using namespace std; typedef struct { int data; } S; extern "C" int F_wrap(const S* p, const S* q) { int (*f)(const S*, const S*) = (int (*)(const S*, const S*))F; int ret = f(p, q); printf("F(%p [%d], %p [%d]) = %d\n", p, p->data, q, q->data, ret); return ret; } __attribute__((constructor)) static void do_patch() { int ret; if (getenv("DONT_PATCH_A")) return; // Aのテキスト部分を書き換え可能にする if ((CALL_F & ~(PAGESIZE-1)) != ((CALL_F + 4) & ~(PAGESIZE-1))) { // ページをまたいでパッチするので *2 ret = mprotect((void*)(CALL_F & ~(PAGESIZE-1)), PAGESIZE * 2, PROT_READ | PROT_WRITE | PROT_EXEC); } else { ret = mprotect((void*)(CALL_F & ~(PAGESIZE-1)), PAGESIZE, PROT_READ | PROT_WRITE | PROT_EXEC); } if (ret != 0) { perror("mprotect"); return; } // Aのコードを実際に書き換える unsigned int* p = (unsigned int*)(CALL_F + 1); // 1足しているのは 'e8' をスキップするため if (*p != (F - (CALL_F + 5))) { // mprotectがEACCESS/EFAULTを戻さないことを確認してから読む方が確実なのでそうしている fprintf(stderr, "パッチ対象のバイナリじゃないよー\n"); return; } *p = ((uintptr_t)F_wrap) - (CALL_F + 5); // アドレスの書き換え (PC相対のアドレスを書く) __asm__ __volatile__("push %%ebx ; cpuid ; pop %%ebx" :: "a"(0) : "memory", "%ecx", "%edx"); }
使いかたは、DSOとしてコンパイル・リンクし、LD_PRELOADするだけです。
% g++ -Wall -O2 -fPIC -shared -o bin_patch.so bin_patch.cpp -ldl % LD_PRELOAD=./bin_patch.so ./tooooslow F(0xb7ec300c [79], 0xb7ec3010 [78]) = 1 F(0xb7ec3008 [80], 0xb7ec300c [78]) = 2 F(0xb7ec3008 [80], 0xb7ec3010 [79]) = 1 ...
誤って、あるいは事情があって 'tooooslow' 以外にPRELOADしてしまっても、よほど運が悪くなければ何もしません。
% LD_PRELOAD=./bin_patch.so /bin/echo hoge パッチ対象のバイナリじゃないよー hoge
以上でございます。
なお、Aをvalgrind上で実行している場合、mprotectがENOMEMで戻ってしまい、実行時パッチに失敗することがありました。理由はいまのところ不明。callgrindやcachegrindでパッチ後のプロファイルを取りたいなどの場合は、xxdやbvi、hte、あるいはemacsの M-x hexl-find-file などの適当なバイナリエディタで事前に実行ファイルAに静的にパッチしておくとよいと思われます*3。
余談
実は最初、Gの call F を call F_wrap@DSO に簡単に書き換えることはできないのではないかとおもい、次のような方法にしていました。動的リンカに自身(F_wrap)のアドレスを教えてもらえばいいやと思っていたわけです。
- Gの call F を、call F_wrap に書き換えたいのだけど、F_wrapのアドレスが事前にわからないので、とりあえず call exit@plt に書き換えておく。exit@pltのアドレスは、nm --synthetic ./A などですぐわかる。
- F_wrapをexitにaliasしておく。あるいは、単にF_wrapではなくexitという名前でラップ関数をつくり、gcc -fno-builtin-exit でコンパイルしておく。すると、exit@plt は、このラップ関数をlibcのexitだと思って呼ぶようになる。
- F_wrapの冒頭で、自分がFとして呼ばれたのか、exitとして呼ばれたのかを判定する。バックトレースすれば確実にわかるが、めんどくさいので引数のs1をintにキャストして、-256から+255の範囲だったらexit呼び出しだろうということにする(これはひどい)。
という方法です*4。最近PLTを違う用途に活用しすぎです。
// bin_patch_PLT.cpp ... #define EXIT_PLT 0x80482f8U __attribute__((constructor)) static void do_patch() { (さっきと同じコード) *p = EXIT_PLT - (CALL_F + 5); // exit@pltに飛ばす } extern "C" int F_wrap(const S* p, const S* q) { if (((int)p >= 256) || ((int)p < -256)) { // case 1. pはアドレスっぽい。Fを呼ぶ (さっきと同じコード) } // case 2. pはexit statusっぽい。libcのexitを呼ぶ void (*real_exit)(int) = (void (*)(int))dlsym(RTLD_NEXT, "exit"); real_exit((int)p); return 0; // not reached } void exit(int) __attribute__((alias("F_wrap")));
で、この方法はかなり汚いhackなので、自分でも何をしているのか忘れそうだなーと思いこの日記を書き始めました。でも書いている途中で、直接 F_wrap に飛ばせるじゃんということがわかり、なんだか何が難しいやらよくわからない(当社比)ぼんやりしたエントリになったのでした。でも、トラブル解決の記録ものとして晒しておきます。もしいつか誰かの何かのお役に立つことでもあれば幸いでございます。
成果
とりあえず、待ち時間に昼寝ができそうなほど長かったリンク時間が1/6に短縮されました。わーい。あと、これを手がけたおかげで、今日以降はPLTを経由してない関数呼び出しも好きなようにフックできるぞーっと。関数のアドレスがわかるならだけど。
TODO: hogetrace絡みでshinhさんに個人的に教えてもらったあれこれをもう一回読む。なんか全然違うこの話題に応用できそうでタイムリー。
まとめ
ベンダに直してもらえYO!
*1:今回のケースでは、ライセンス上の問題はありませんでした
*2:今回のkcachegrindの使いかた: "self"でソートしてもっとも時間のかかっている関数(F)をクリックし、"Call Graph"で右クリックしてGraphのCaller DepthをUnlimitedにして、どういう経路でFが呼ばれているか眺めればOK
*3:が、F_wrap()がどこにロードされるか事前には必ずしも決められないか....。次の「余談」のところを見てください
*4:そういえばPRELOADするDSOのPT_LOADのp_vaddrって、100%でなくてもいいですが、効きますっけ? ローダ読め? はい
関数テンプレートの特殊化について
関数テンプレートの特殊化いろいろ
なんか日記を書くのを忘れていました。よくない。というわけで、最近おぼえたtipsを書きます。クラステンプレート内のテンプレートの特殊化（もどき）についての自分なりのまとめ。
まず、
namespace A { template<int V> static void YYY() { std::printf("default %d\n", V); } } int main() { YYY<0>(); YYY<128>(); }
のような関数テンプレートがあるとき、これを特殊化*1した関数は
namespace A { template<int V> static void YYY() { std::printf("default %d\n", V); } template<> static void YYY<128>() { std::printf("for 128\n"); } template<> static void YYY<256>() { std::printf("for 256\n"); } }
のように書けます。同様に、メンバ関数テンプレート
struct B { template<int V> static void YYY() { std::printf("default %d\n", V); } };
があった場合、この特殊化は、Bの中、クラススコープには規格上書いてはいけないことになっており、g++も実際にそういうコードを受け付けない*2ので、
template<> inline void B::YYY<128>() { std::printf("for 128\n"); } template<> inline void B::YYY<256>() { std::printf("for 256\n"); }
のように名前空間スコープに書けばOKです。クラス外に出すとインライン化されにくくなるので、inlineをつけておきました。では、外側のクラスがクラステンプレートだった場合はどうかというと、
template <typename T> struct C { template<int V> static void YYY() { std::printf("default %d\n", V); } };
次のように、外側のCを明示的に特殊化した上で内側のYYY()を特殊化するような関数を名前空間スコープに書くことはできるけど、
// C<int> に対する YYY<128>() template<> template<> inline void C<int>::YYY<128>() { std::printf("for 128\n"); }
Cを特殊化しないでYYY()を特殊化するのはg++に "error: enclosing class templates are not explicitly specialized" だと言われてしまいコンパイルできません。C++の規格にも上のコードとそっくりの例まで挙げてダメだと書かれてます*3。
// error: enclosing class templates are not explicitly specialized template<typename T> template<> inline void C<T>::YYY<128>() { std::printf("for 128\n"); }
そういうときどうするかというと、あまり詳しくないですがたぶん、古典ことMC++D, Modern C++ Designの2章に書いてある通り、
- boost::type
; - boost::mpl::bool_<B>
- boost::mpl::int_
- boost::mpl::integral_c
あたりのお好きなもの（LokiでいうType2Type
template <typename T> class C { void YYY_(boost::mpl::int_<128>) { /* specialized */ } void YYY_(...) { /* default */ } public: template<int V> static void YYY() { YYY_(boost::mpl::int_<V>()); } };
こうすると、YYY<0>(); と YYY<128>(); で別々の関数、それぞれ YYY_(...) と YYY_(boost::mpl::int_<128>) が呼ばれることになるので、特殊化が実現できたようなものです。これをここでは特殊化もどきと呼びます。
あるいは、次のように、クラススコープ、特に特殊化されていないクラステンプレートのスコープでも、クラステンプレートの部分特殊化なら可能であることを利用して、D
template <typename T> class D { template <int V, typename Dmy = void> struct D_ { static void XXX() { std::printf("default %d\n", V); } }; template <int V> // partial specialization struct D_<V, typename boost::enable_if_c<V == 128>::type> { static void XXX() { std::printf("for %d\n", V); } }; template <int V> // partial specialization struct D_<V, typename boost::enable_if_c<V == 256>::type> { static void XXX() { std::printf("for %d\n", V); } }; public: template<int V> static void XXX() { D_<V>::XXX(); } };
BoostのMLのこのメールでは、こちらの方法が推奨されていました。次の通り、D_ の部分特殊化版を誰でも後から追加できますからね。
// namespace scope に V==0の場合の特殊化を後から追加 template <typename T> template <int V> struct D<T>::D_<V, typename boost::enable_if_c<V == 0>::type> { static void XXX() { std::printf("for %d\n", V); } };
のように。boost::enable_ifは、これまた数行で書けるだいたいこんな感じのクラステンプレートです。というわけで、「クラステンプレートC内のメンバ関数テンプレートを、Cを特殊化しないで特殊化(もどき)する」には、「クラステンプレートに委譲しとけば？」でファイナルアンサーのように思うのですが、練習（何の？）ため、他の関数に処理を委譲せずに特殊化もどきを実現できないかを考えてみます。
関数テンプレートの enable_ifオーバーロードによる特殊化もどき - 2分岐バージョン
もし、特殊化する関数が1つだけ、Pのときの関数と!Pのときの関数だけ用意すればことたりるなら、boost::enable_ifと関数のオーバーロードを使って、委譲なしで綺麗に特殊化もどきを実現できます。
template<bool B> static void bar(typename boost::enable_if_c<B>::type* = 0) { std::printf("for true\n"); } template<bool B> static void bar(typename boost::disable_if_c<B>::type* = 0) { std::printf("for false\n"); }
としたり、
template<int V> static void boo(typename boost::enable_if_c<V == 0>::type* = 0) { std::printf("for 0\n"); } template<int V> static void boo(typename boost::enable_if_c<V != 0>::type* = 0) { std::printf("default\n"); }
としたり、です。
(おまけ)関数テンプレートの enable_ifオーバーロードによる特殊化もどき - 3+分岐バージョン
ですが、合計3つ以上の関数を用意したい場合にはenable_ifはちょっと面倒です。
template<int V> static void boo(typename boost::enable_if_c<V == 0>::type* = 0) { std::printf("for 0\n"); } template<int V> static void boo(typename boost::enable_if_c<V == 1>::type* = 0) { std::printf("for 1\n"); } static void boo(typename boost::enable_if_c<V == 2>::type* = 0) { std::printf("for 2\n"); } static void boo(typename boost::enable_if_c<!(V == 0) && !(V == 1) && !(V == 2)>::type* = 0) { std::printf("default\n"); }
のようにdefaultな関数の引数がえらいことになります。boo(...) などでdefault関数を書ければいいんですけどね。コンパイラに曖昧だと言われてしまってどうにも。どうにかなるでしょうか。
上の例は、特殊化(もどき)の条件(V==ほげ)が2回づつ登場してしまっているのが気に入りません。ですので、今回は、MPLを使って、頑張って特殊化もどきの条件を各1回だけ書けばいいようにしてみました。はじめてのMPLと。
#include <cstdio> #include <boost/utility/enable_if.hpp> #include <boost/type_traits/is_same.hpp> #include <boost/mpl/int.hpp> #include <boost/mpl/bool.hpp> #include <boost/mpl/lambda.hpp> #include <boost/mpl/list.hpp> #include <boost/mpl/at.hpp> #include <boost/mpl/or.hpp> #include <boost/mpl/fold.hpp> template <typename T> struct X { struct detail { typedef boost::mpl::list< boost::mpl::lambda< boost::is_same< boost::mpl::_1, boost::mpl::int_<128> // V==128で特殊化したい > >::type, boost::mpl::lambda< boost::is_same< boost::mpl::_1, boost::mpl::int_<256> // V==256で特殊化したい > >::type > value_list; // boost::mpl::fold<> にあとで渡す template<int V> struct compar_meta_fn { template<typename Sum, typename Seq> struct apply { typedef boost::mpl::or_< Sum, /* true_ or false_ */ typename Seq::type::template apply<boost::mpl::int_<V> >::type > type; }; }; }; // ::template apply<... という奇妙な文法については、書籍 "C++ Templates - the complete guide" の9章に丁寧な解説があります template<int V> static void XXX(typename boost::enable_if< typename boost::mpl::at_c<typename detail::value_list, 0>::type::template apply<boost::mpl::int_<V> >::type >::type* = 0) { std::printf("for %d\n", V); // 128 } template<int V> static void XXX(typename boost::enable_if< typename boost::mpl::at_c<typename detail::value_list, 1>::type::template apply<boost::mpl::int_<V> >::type >::type* = 0) { std::printf("for %d\n", V); // 256 } template<int V> static void XXX(typename boost::disable_if< typename boost::mpl::fold< typename detail::value_list, boost::mpl::false_, typename boost::mpl::lambda<typename detail::template compar_meta_fn<V> >::type >::type >::type* = 0) { std::printf("default %d\n", V); } }; int main() { X<int>::XXX<0>(); X<long>::XXX<128>(); X<float>::XXX<256>(); X<double>::XXX<512>(); }
以上です。実行結果:
% ./a.out default 0 for 128 for 256 default 512
整数値でなく型で特殊化もどきをしたい場合は、boost::mpl::int_
template <typename T> struct Z { LIST_BEGIN() LIST_ELEM(128), LIST_ELEM(256) LIST_END(lst); template<int V> static void XXX(ENABLE_NTH(lst,0)) { std::printf("for %d\n", V); // 128 } template<int V> static void XXX(ENABLE_NTH(lst,1)) { std::printf("for %d\n", V); // 256 } template<int V> static void XXX(OTHERWISE(lst)) { std::printf("default %d\n", V); } };
くらいに縮めればなんとか使え...ないですかね。とりあえず、異なるVごとに別の XXX
結論
MPLを今更ながら使ってみたら面白かった。なお、MPLを使ってみるにあたっては、稲葉一浩さんのBoost本(第二版)に大変お世話になりました。
hogetrace - 関数コールトレーサ
でかいソフトウェアの、大量のソースコードを短時間で読む必要が生じたので、その補助ツールとしてptrace(2)ベースのLinux用関数トレーサを自作しました。こういうツール上でまずソフトウェアを実行してみて、どのファイルのどの関数がどういう順で呼ばれるか把握おけば、いきなりソースコードの山と格闘を始めるより楽かなーと思いまして。せっかく作ったので公開します。
http://binary.nahi.to/hogetrace/
straceはシステムコールだけ、ltraceは共有ライブラリ(DSO)の関数呼び出しだけ*1をトレースしますが、このツールは、実行バイナリ中の自作関数の呼び出しもトレースします。例えば再帰で1から10まで足し算するソースコードを用意して
% cat recursion.c #include <stdio.h> int sum(int n) { return n == 0 ? 0 : n + sum(n - 1); } int main() { int s = sum(10); printf("sum(10) = %d\n", s); return s; }
最適化なしで普通にコンパイルしてトレーサにかけてみるとこんな感じの出力になります。-g をつけると、ファイル名/行番号を出せるので、そうしてあります。
% gcc -g -o recursion recursion.c % hogetrace --plt -lATv ./recursion [pid 17700] +++ process 17700 attached (ppid 17699) +++ [pid 17700] === symbols loaded: './recursion' === [pid 17700] ==> _start() at 0x08048300 [pid 17700] ==> __libc_start_main@plt() at 0x080482cc [pid 17700] ==> __libc_csu_init() at 0x08048460 [pid 17700] ==> _init() at 0x08048294 [pid 17700] ==> call_gmon_start() at 0x08048324 [pid 17700] <== call_gmon_start() [eax = 0x0] [pid 17700] ==> frame_dummy() at 0x080483b0 [pid 17700] <== frame_dummy() [eax = 0x0] [pid 17700] ==> __do_global_ctors_aux() at 0x080484d0 [pid 17700] <== __do_global_ctors_aux() [eax = 0xffffffff] [pid 17700] <== _init() [eax = 0xffffffff] [pid 17700] <== __libc_csu_init() [eax = 0x8049534] [pid 17700] ==> main() at 0x08048404 [/home/sato/ht-trunk/sample/recursion.c:9] [pid 17700] ==> sum(int n <10>) at 0x080483d4 [/home/sato/ht-trunk/sample/recursion.c:4] [pid 17700] ==> sum(int n <9>) at 0x080483d4 [/home/sato/ht-trunk/sample/recursion.c:4] [pid 17700] ==> sum(int n <8>) at 0x080483d4 [/home/sato/ht-trunk/sample/recursion.c:4] [pid 17700] ==> sum(int n <7>) at 0x080483d4 [/home/sato/ht-trunk/sample/recursion.c:4] [pid 17700] ==> sum(int n <6>) at 0x080483d4 [/home/sato/ht-trunk/sample/recursion.c:4] [pid 17700] ==> sum(int n <5>) at 0x080483d4 [/home/sato/ht-trunk/sample/recursion.c:4] [pid 17700] ==> sum(int n <4>) at 0x080483d4 [/home/sato/ht-trunk/sample/recursion.c:4] [pid 17700] ==> sum(int n <3>) at 0x080483d4 [/home/sato/ht-trunk/sample/recursion.c:4] [pid 17700] ==> sum(int n <2>) at 0x080483d4 [/home/sato/ht-trunk/sample/recursion.c:4] [pid 17700] ==> sum(int n <1>) at 0x080483d4 [/home/sato/ht-trunk/sample/recursion.c:4] [pid 17700] ==> sum(int n <0>) at 0x080483d4 [/home/sato/ht-trunk/sample/recursion.c:4] [pid 17700] <== sum() [eax = 0x0] [pid 17700] <== sum() [eax = 0x1] [pid 17700] <== sum() [eax = 0x3] [pid 17700] <== sum() [eax = 0x6] [pid 17700] <== sum() [eax = 0xa] [pid 17700] <== sum() [eax = 0xf] [pid 17700] <== sum() [eax = 0x15] [pid 17700] <== sum() [eax = 0x1c] [pid 17700] <== sum() [eax = 0x24] [pid 17700] <== sum() [eax = 0x2d] [pid 17700] <== sum() [eax = 0x37] [pid 17700] ==> printf@plt() at 0x080482ec sum(10) = 55 [pid 17700] <== printf@plt() [eax = 0xd] [pid 17700] <== main() [eax = 0x37] [pid 17700] ==> _fini() at 0x080484f8 [pid 17700] ==> __do_global_dtors_aux() at 0x08048350 [pid 17700] <== __do_global_dtors_aux() [eax = 0x0] [pid 17700] <== _fini() [eax = 0x0] [pid 17700] +++ process 17700 detached (ppid 17699) +++ hogetrace: done
結果の55が計算され、表示されるまでの関数の呼び出し状況がわかると思います。
当初は、KLabのftraceなど、gcc -finstrument-functions系のトレーサを使わせてもらおうと思っていたのですが、（私の解析したいソフトウェアの場合）ソフトウェアの再コンパイルやMakefileの書き換えに大変手間がかかることがわかったので、「stripされていなければ再コンパイル不要」なツールを自作してみたという感じです*2。連休もあることだし、勉強がてら。仕組みはstrace/ltrace/gdb と同じくptrace(2)ベースで、fork/exec/clone対応、DSOの関数呼び出しのトレースも対応、です。なお関数の引数表示のところは、ftraceのソースコードをそのまま流用させていただきました。ありがとうございます。
以下仕組みのメモ + 遊んでいておもしろかったところ (あとでちゃんと書く):
- libbfdを使って解析対象のプログラムの.symtabを読んで、全関数の先頭アドレスを得ている。ついでに.plt上の合成(synthetic)シンボル(printf@pltとか)も得ている
- libopcodesで、さっき得た各関数の先頭アドレスから、バイナリを逆アセンブル、ret命令を探すことで関数からのリターンアドレスを静的に解析 /特定している。スタック見て動的にやる方法もありますが、今回は静的にやった。ltraceとは違う方法にしてみたかったというのもあるし、マルチスレッド環境で動的にセットしたBPを別スレッドが踏むとめんどくさいというのもあったり。
- ret/retq命令探しの際、_start() はretじゃなくてhltだとか、末尾再帰関数で-O2だとretがないとか、throwで抜けてるとやっぱりretがないとか、構造体を値で戻すような関数だと0xC3ではなく0xC2だったりとか、__attribute__((noreturn))されてるとretしないとか、そういう関数を呼ぶ側も callではなくjmpにしちゃうとか、探すときに細かい注意点がある。
- ひとつの関数内に複数のretが存在することが（もちろん？）ある。switch-case使ったときとか。
- .debug_info 見て、関数の定義されているファイル名、行番号の情報を取得している。同じく.debug_info 見て、関数の引数の情報を取得している。
- 解析対象をforkしてptrace(TRACEME);してsetenv(LD_BIND_NOW=1);してexec。setenvしておかないと、 PLT経由の関数呼びの初回(_dl_runtime_resolve時)がすぐにreturnするように表示されてしまう。子プロセスの起動時間を延ばしてしまう悪いhackかも。
- 解析対象がメモリにロードされたら、関数の先頭アドレス、RET命令アドレスにブレークポイント設定。ptrace(POKE)でそのアドレスに0xCCを書くだけ
- 解析対象が0xCCを踏むと、tracefにシグナルで通知がくる。ので、適当に情報を表示。0xCCで止まった解析対象の再開方法は、gdbとかと同じ(説明になっていない)。EIPを戻して元の命令書き戻してシングルステップして云々。詳しくは書籍「デバッガの理論と実装 (ASCII SOFTWARE SCIENCE Language)」あたりを。
- PLT経由のジャンプのフックは、まずPLT先頭の jmp *0x80... のとこに0xCCを仕掛け、その次の命令 push 0x.. にも0xCCを仕掛けておく。jmp*を踏んで解析対象が止まったら、解析対象のスタック上のリターンアドレスをPEEKして、tracef側に記憶する。そのリターンアドレスをpush 0x..のアドレスにすりかえる(POKE)。push 0xにリターンしてくるとまた0xCCを踏んで止まるので、tracef側に記憶しておいた本物のリターンアドレスを、今度はEIPに書き込んで continue。以上。これはひどい。
- この方法だと、DSO内で例外がthrowされて、それが解析対象のバイナリまで到達すると、abortする。ごめんなさいごめんなさいごめんなさい。まぁ滅多にそんなことしないよね。
- 最低限の対策として、__cxa_throw@plt の先頭でブレークした時は、このリターンアドレスのtweakを行わないようにしておいた。これで、exe内でthrowして、exe内でcatchする場合は問題なくなった。dso内でthrowして、exe内でcatchするプログラムをtraceする場合は、--pltか-Tのどちらかをはずしてもらわないとダメだ...。やはりltrace風の(よくあるデバッガの)、スタック見てリターンアドレスに地雷置くやりかたのほうがよかったか。
- GOT/PLT回りは、arch毎にコードがいる。x86_64はx86とほとんど同じだけど、jmp* がPC相対なのでやっぱり#ifdefすることになった。
- 例外のthrowで表示(コールツリーのインデント具合)が乱れないよう、各プロセス/スレッドの関数呼び出し状況を、tracef側の std::stack
にも記憶しておく。 - ptraceはぐぐってもあまり文献がなくて、結局頼りになるのはstraceとltraceのソースコードだけだった。straceは多OS対応で魔窟なので、ltraceを中心に見た。でもltraceはスレッドというかcloneというか PTRACE_O_TRACECLONE というかに対応していない。結局そこは試行錯誤。あと、ltraceの .dynほげセクションの処理部分は面白かったのだけど、今回は使わない...
- straceをstraceしたり、ltraceをstraceしたりするといろいろなことがわかった。
- プロセスのptraceを終了する(detach)と、そのプロセスが即死する現象に悩んだ。単に、プロセスの0xCCを元に戻さないままデタッチしていたからシグナルで死んでいるだけだった。ありがとうございました。forkすると0xCCなまま.textがコピーされることも忘れずに。当然ですが。
- ptrace(GETREGS)に渡す構造体の初期化を省いたら、それが原因でvalgrindが死ぬほどの量の警告を出してくれた。ptraceの引数の初期化省略が原因だと気づくのにすこし時間がかかった。
- ptrace(2)は、以前straceもどきを作ってみてそれでおわりにしていたけど、いろいろ試してみたら想像以上におもしろかった。早いとこ遊んでおけばよかった。
デバッガもどきを作るのは初めてだったので、とてーも楽しかったです。ソースコードやrpmはリンク先にあります。
