ついカッとなって実行バイナリにパッチ
とある都合で、ソフトウェア開発の際にソースコードの提供されていないツールを使うことになりました。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%でなくてもいいですが、効きますっけ? ローダ読め? はい
