memologue RSSフィード

書いている人

日記というよりは備忘録、ソフトウェア技術者の不定期メモ。あるいはバッドノウハウ集。プライベートで調査した細々した諸々のスナップショット。嘘が散りばめられています。ISO/IEC 14882(C++)とPOSIX, GCC, glibc, ELFの話ばかりで、WindowsやMacの話はありません。特に記載がなければLinux/x86とILP32が前提です。時間の経過と共に古い記事は埋もれてしまいます。検索エンジンから飛んできた場合は、ページ内検索をご利用いただくかgoogleキャッシュを閲覧してみてください。技術的な記事を書きためる場所として使っています。言及してもらえると喜びます。主要な記事の一覧を書いておきます:

にんきコンテンツ: [GCC] mainを一度も呼ばないばかりか蹂躙する / Binary2.0 Conference 2006 発表資料 / C++ で SICP / ついカッとなって実行バイナリにパッチ / hogetrace - 関数コールトレーサ

昔のPOSIX関係の記事: シグナルの送受に依存しない設計にしよう / シグナルハンドラで行ってよい処理を知ろう / マルチスレッドのプログラムでのforkはやめよう / スレッドの「非同期キャンセル」を行わない設計にしよう / スレッドの「遅延キャンセル」も出来る限り避けて通ろう / マルチスレッドプログラミングの「常識」を守ろう / C++でsynchronized methodを書くのは難しい / シグナルハンドラからのforkするのは安全か? / g++ の -fthreadsafe-statics ってオプション知ってます? / 非同期シグナルとanti-pattern / localtimeやstrtokは本当にスレッドセーフにできないのか / UNIXの規格について / マルチスレッドと共有変数 - volatile?なにそれ。 / type punning と strict aliasing / アセンブラで遊ぶ時に便利なgdb設定 / 最近の記事は一覧から

2007-12-02

[][] 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上でプロファイル結果を見られます。

  • 次のファイルがx86からアクセス可能
    • prof.out
    • 解析対象のprogram
    • programが依存しているDSO群
  • crossのbinutilsが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で動作確認してます。

移植方法


同ソフトウェアはアーキテクチャ依存部分が分離されているので、移植作業は楽で、

  1. ARMv5t用のアトミック演算関数を2種類書く
  2. スタックトレース関数を書く
  3. シグナルを受信したときの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 <execinfo.h> するだけですぐ使えたりするんですが、この関数は内部でmallocを呼ぶことがあるのでできれば避けろと書かれてます。arm portでもそれに従い自作することにしました。ま、そんなに難しいわけではありません。


フレームポインタが省略されていないと仮定すると、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.だわ、ダメですね。

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 このアイディアは素敵だなぁ。

2007-11-15

[] 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の記述が少し古くなりました。

*1:Fedoraのpatchはこれとは別系統っぽいですが、メインラインにあわせてパッチを有効にしたり無効にしたりしているように見えた

*2:The Shellcoder's Handbook: Discovering and Exploiting Security Holes (2nd edition) という本の、(攻撃云々はわからんので) 14章 Protection Mechanisms およびLinux/ELF関連のとこだけ。

2007-11-05

[] ついカッとなって実行バイナリにパッチ

とある都合で、ソフトウェア開発の際にソースコードの提供されていないツールを使うことになりました。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;
}

また、

  • (インライン)アセンブラは1行まで。おやつは300円まで。
  • できる限りgccに頼る。自分でリロケーションしない。
  • バイナリエディタもできれば使わない

という俺ルールにしました。私はこれらの技術が達人のみなさんと比べてそんなに流暢に使えるわけでもなく、手を出すと一晩では仕上らない予感がしたからです。なお、これらを使った格好いい方法は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!

[][] 構造体のサイズ違いで悩んだのでリンク時に検出

先日、次のような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<T>は、Tをそれ固有の軽い型に写像するクラステンプレートです (LokiのType2Type<T>に相当)。CHECK_SIZEマクロ、DEF_PROPER_SIZEマクロの使いかたは前と同じです。

構造体のサイズ違いの自動検出 (リンク時 その2)


上の方法だと、検出はリンク時に行えますが、実行時にmain関数の前で余計なコードが走ってしまう*5のが気になります。そこを改良。

// 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の勉強用の題材としてはよさげだけど、コンパイル以外の作業をしないと発見できないというのはヘボいな。

[][] 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, &regs);
      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年のこの記事あたりが参考になると思います。

*1:今回のケースでは、ライセンス上の問題はありませんでした

*2:今回のkcachegrindの使いかた: "self"でソートしてもっとも時間のかかっている関数(F)をクリックし、"Call Graph"で右クリックしてGraphのCaller DepthをUnlimitedにして、どういう経路でFが呼ばれているか眺めればOK

*3:が、F_wrap()がどこにロードされるか事前には必ずしも決められないか....。次の「余談」のところを見てください

*4:そういえばPRELOADするDSOのPT_LOADのp_vaddrって、100%でなくてもいいですが、効きますっけ? ローダ読め? はい

*5:tracefで確認できます <- しつこい

2007-10-08

[] 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<addr_t> にも記憶しておく。
  • 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はリンク先にあります。

[]関数テンプレートの特殊化について

関数テンプレートの特殊化いろいろ


なんか日記を書くのを忘れていました。よくない。というわけで、最近おぼえたtipsを書きます。クラステンプレート内のテンプレートの特殊化(もどき)についての自分なりのまとめ。


まず、

namespace A {
  template<int V>
  static void YYY() {
    std::printf("default %d\n", V);
  }
}
int main() {
  YYY<0>();
  YYY<128>();
}

のような関数テンプレートがあるとき、これを特殊化*3した関数は

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++も実際にそういうコードを受け付けない*4ので、

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++の規格にも上のコードとそっくりの例まで挙げてダメだと書かれてます*5

// 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<T>;
  • boost::mpl::bool_<B>
  • boost::mpl::int_<V>
  • boost::mpl::integral_c<EnumT,EnumV>

あたりのお好きなもの(LokiでいうType2Type<T>, Int2Type<V>)を使って、型とか個々の整数値、列挙値をそれ固有の軽い型のオブジェクトに変換して(説明になっていない)、オーバーロードで適切な関数を呼ぶようにすると思います。上の4つのMPL系クラステンプレートはそれぞれ3行ぐらいですので、自作するのも簡単です。

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<T>::XXX<V>()からD<T>::D_<V>::XXX()に処理を委譲してしまう手もあると思います。

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_<V>ではなくboost::type<T>を使えばOKです。is_same<>も別のに変えた方がいいかもしれないけど。で、ちょっとこのままでは長すぎるので、適当にマクロで(BOOST.PPは見なかったことにします)

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<V>(OTHERWISE) 関数が生成されてしまうのは問題か。

結論


MPLを今更ながら使ってみたら面白かった。なお、MPLを使ってみるにあたっては、稲葉一浩さんのBoost本(第二版)に大変お世話になりました。

*1:-x というオプションが一応ありますが略

*2:すでに類似ツールあるかなぁとか、gdbでできるんじゃないかなぁとか思いつつも。なにかありますかねぇ

*3:関数テンプレートの部分的な特殊化はできないから、以下関数に付いて単に特殊化と言ったら明示的特殊化です

*4:VC++はなぜか書けるみたいだけど

*5:これまたVC++では通るみたいですが...。なんてプログラマに優しいんだ

2007-02-04

[][] C/C++の定数の型の話, C90/C99の差分のびみょーな話

Cのソースコードに m = 195; とか n = 0xffffffff; とか書いたときの定数(右辺)の型って、なんであるかご存じでしょうか? また、C90(1990年版のISO C言語規格)とC99(1999年版のそれ)ではその型が微妙に異なったりすることがあるんですが、ご存じでしょうか? さらには、お使いのマシンがILP32であるかLP64であるかLLP64であるかによっても、微妙に型が違ってきたりするんですが、それについてはどうでしょうか? えーもちろん、普段は「Uがついてなかったらint, Uがついてたらunsigned intジャネーノ?」くらいの理解でも殆ど不自由しないわけですが、詳細な理解がないとハマるケースも稀にあります。


私はというと、上に書いたような事は、C90/99の差違を除いてはだいたい理解しているつもりだったのですが、C90/99の差異について無頓着だったがために、先日ちょっとした不意打ちをくらいました。事例(クイズ?)として紹介してみます。

クイズ


このようなコードを考えます。妙なコードですが、問題の起こる最小の例を抜き出したということでご勘弁ください。これは、C90とC99で異なる振る舞いをするコードになっています。4294967295は、2進数で書くと1111 1111 1111 1111 1111 1111 1111 1111です(1が32個並ぶ)です。

#include <stdio.h>

void foo(int nume) {
  unsigned long long x = nume / 4294967295;
  printf("%llu\n", x);
}

int main() {
  foo(-1);
  return 0;
}

これを、次の4つの環境でコンパイル・リンクして実行すると、

  • (1) ILP32, C90準拠コンパイラ (gccなど)
  • (2) ILP32, C99準拠コンパイラ (gcc4 -std=c99 など)
  • (3) LP64, C90準拠コンパイラ (gccなど)
  • (4) LP64, C99準拠コンパイラ (gcc4 -std=c99 など)

それぞれ、どのような出力が得られるでしょうか?


えー、4294967295 の型が(1)-(4)でそれぞれ何になるかがポイントです。それによって除算がどう行われるかが、除算の結果の型も含めて決まります。変数xへの代入部分は、この例では答えに影響しません。というか、影響しないようにxの型を選んであります。

答え


(1)-(4)の出力は順に

  • (1) 1
  • (2) 0
  • (3) 0
  • (4) 0

となります。次の通り:

% gcc -v
gcc version 4.1.1 20070105 (Red Hat 4.1.1-51)
% uname -m
x86_64

% gcc -m32          div.c && ./a.out
1
% gcc -m32 -std=c99 div.c && ./a.out
0
% gcc -m64          div.c && ./a.out 
0
% gcc -m64 -std=c99 div.c && ./a.out
0

順を追って解説します。まず、「定数の型がどのように決まるか」から押さえましょう。

定数の型はどのように決まるのか (C90編)


C90における定数の型は、ISO C90 規格書*1の6.1.3.2に載ってます。

整数定数の型は、次の並びのうちでその値を表現できる最初の型とする。

  • 接尾語無しの10進数: int, long int, unsigned long int
  • 接尾語無しの8進数又は16進数: int, unsigned int, long int, unsigned long int
  • 文字u又はUが接尾語として付く場合: unsigned int, unsigned long int
  • 文字l又はLが接尾語として付く場合: long int, unsigned long int
  • 文字u又はU及び文字l又はLが接尾語として付く場合: unsigned long int

たとえば、ILP32環境で定数「1」や「214783647」*2はintですが、「2147483648」*3はintでもlong intでも表現できないのでunsigned long intになります。型が、符号有無も含めて異なります。また、同じ数(!?)でも10進定数にするか16進定数にするかで型が異なることがあります。LP64環境で「2147483648」は long int ですが、「0x80000000」は unsigned int になってしまいます。やはり型が、符号有無も含めて異なります。ぅゎ。

定数の型はどのように決まるのか (C99編)


C99における定数の型は、ISO C99 規格書の6.4.4.1に載ってます。C99の場合は表になっているんですが、私の方でC90にフォーマットを合わせたものを記します。ひとまず「接尾語無しの10進数」のlong intの次が、C90ではunsigned long intだったのに対しC99ではlong long intになっています。これが今回のポイントです。

整数定数の型は、次の並びのうちでその値を表現できる最初の型とする。

  • 接尾語無しの10進数: int, long int, long long int
  • 接尾語無しの8進数又は16進数: int, unsigned int, long int, unsigned long int, long long int, unsigned long long int
  • 文字u又はUが接尾語として付く場合: unsigned int, unsigned long int, unsigned long long int
  • 文字l又はLが接尾語として付く場合の10進数: long int, long long int
  • 文字l又はLが接尾語として付く場合の8進数又は16進数: long int, unsigned long int, long long int, unsigned long long int
  • 文字u又はU及び文字l又はLが接尾語として付く場合: unsigned long int, unsigned long long int
  • 文字ll又はLLが接尾語として付く場合の10進数: long long int
  • 文字ll又はLLが接尾語として付く場合の8進数又は16進数: long long int, unsigned long long int
  • 文字u又はU及び文字ll又はLLが接尾語として付く場合: unsigned long long int

ILP32+C99では定数「1」や「214783647」はintですが、「2147483648」は long long int になります。またC90同様、同じ数(?)でも10進定数にするか16進定数にするかで型が異なることがあります。ILP32+C99で「2147483648」は long long int ですが、「0x80000000」は unsigned int です。やはり型が、符号有無も含めて異なります。

解説


これを踏まえ、(1)-(4)で4294967295の型がどうなるかを起点として除算の動きを見ます。


(1)では、4294967295の型はunsigned long int になります。ですから、除算は

 -1 [int] / 4294967295 [unsigned long int]
   ==(usual arithmetic conversion)==> 
 -1 [unsigned long int] / 4294967295 [unsigned long int]
   ==>
 4294967295 [unsigned long int] / 4294967295 [unsigned long int]
   ==>
 1

のように行われ(適当な記法でスミマセン)、結果は1になります。0にはなりません!。結果の型は unsigned long int です。


(2)では、4294967295の型はlong long intになります。ですから、除算は

 -1 [int] / 4294967295 [long long int]
   ==(usual arithmetic conversion)==> 
 -1 [long long int] / 4294967295 [long long int]
   ==>
 0

のように行われ、結果は0になります。結果の型は long long int です。64bitの符号「付き」の型に揃えられてから演算されるので、(1)のように -1 が 4294967295UL に読み替えられないのがポイントでしょう。


(3)と(4)はlong型が64bitである関係で、同じ演算になります。C90/99で違いは出ません。4294967295の型はlong intになります。除算は

 -1 [int] / 4294967295 [long int]
   ==(usual arithmetic conversion)==> 
 -1 [long int] / 4294967295 [long int]
   ==>
 0

のように行われ、結果は0になります。結果の型は long int です。-1が-1のまま演算される点は、(2)と同じですね。

(余談) usual arithmetic conversion


usual arithmetic conversion (通常の算術型変換) については、Cの規格を参照してください。このpdfにも少し載ってます。long long型(64bit型)のことを忘れてもいいなら、いやあまりよくないとおもいますが、K&Rの第二版にも一応載ってます。

GCCの警告


実はGCCは、C90とC99で型が異なるような定数を使用すると、C90モードでコンパイルした際に次のような警告を出してくれます。この警告が出たら、無視せずに原因をよく考える方がよさそうです。

warning: this decimal constant is unsigned only in ISO C90

しかしながら、データモデルによって型が変化するケース、10進で書くか8/16進で書くかによって型が変化するケースについては、プログラマが気を付けるしかなさそうです。

まとめ


C言語のソースコード中に記載した定数は、結構意外な型として扱われていることがあり、その詳細を知らないと(たまに)問題が起こる。特に、

  • 10進定数を8/16進定数に書き直すと(あるいはその逆)、型が変化してしまうことがあるので注意
    • 同じことですが、ある数を10進定数として書くか、8/16進定数で書くかによって型が異なってしまうことがあるので注意
  • C90準拠のコンパイラとC99準拠のコンパイラで、定数の型が異なってしまうことがあるので注意
  • ILP32環境でコンパイルするかLP64環境でコンパイルするかで、定数の型が異なってしまうことがあるので注意

この3点に注意が必要です。また、

  • 上に書いたGCCの警告を無視しない
  • 定数を、符号無しだと思ってソースコード中に書いているのなら、必ず接尾語Uを書く (LとLLについても同様)

というのもよい習慣だと思います。

C++について


C++言語(ISO/IEC 14882:2003)は、2003年版の規格では、C言語互換部分についてはC90を参照してますので、gccをC90モードで使ったときと同じ結果になります。

% cp div.c div.cpp

% g++ -m32 div.cpp && ./a.out       
div.cpp:4: 警告: this decimal constant is unsigned only in ISO C90
1
% g++ -m64 div.cpp && ./a.out
0

*1:C90のJIS版は、旧規格になりますのでWebから発注はできません。http://www.webstore.jsa.or.jp/webstore/Com/html/jp/ShoppingInfo.htm のFAX注文書で JIS X3010:1993 と X3010:1996(Amd1) を発注することになります。合計で3.5万円程です。詳しくはJSAに問い合わせを

*2:2進で 0111 1111 1111 1111 1111 1111 1111 1111 です

*3:2進で 1000 0000 0000 0000 0000 0000 0000 0000 です