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設定 / 最近の記事は一覧から

2006-05-28

[][] Java の ConTest っぽいものを、glibcの新機能(LD_AUDIT)を使って Linux + C/C++ で実現してみる

たまには何か書きます。C/C++のマルチスレッドなプログラムのユニットテストでバグを効率的に見つけるためのライブラリ?の作成について。

IBM dWのConTest


はてなブックマークを眺めていたら、「ConTestを使用したマルチスレッド・ユニットのテスト - 並列テストが困難な理由とConTestの活用」というIBM developerWorksの記事が話題になっていました。


「(Javaの) 並列プログラム上での単体テストの問題点を解決する補助的なテスト手法」だそうで、例としてあがっているのは次のようなケースです。

  • 名前を印刷するのに3つのスレッドを用意する
  • それぞれ、「姓」「スペース」「名」を印刷する
  • 3つのスレッドは同期を取っていない。つまりバグがある
  • しかし、単体テストを行っても、ほぼ毎回、「姓」「スペース」「名」という正しい順序で(スレッドが実行)されてしまい、バグを検出できない

ConTestはこういう場面で使えるツールなんだそうです。ConTest上で(?)プログラムを実行すると、「姓」「スペース」「名」の順でスレッドが実行されないケースを通常より増やすことができるそうです。仕組みは次の通り:

ConTestの基本的な原理はきわめて単純です。計測段階でクラス・ファイルを変換し、ConTestのランタイム機能への呼び出しを選択された場所に挿入します。ConTestが実行されると、こうした場所でコンテキスト・スイッチがときどき発生します。この選択された場所とは、同期ブロックの出入口や共有変数へのアクセスなど、スレッド間の相対順序が実行結果に影響を与える可能性のある場所のことです。yield() やsleep() などのメソッドを呼び出すことにより、コンテキスト・スイッチが実行されます。こうした処理はランダムに実行されるため、実行のたびに異なったインターリービングが発生することになります。典型的なバグを明らかにする際には、ヒューリスティックスが使用されます。

おもしろそうです。

Linuxに移植する


これを、脊髄反射的に Linux + C/C++ な環境で実現してみます。


ちょっと調べてみてわかったんですが、glibc-2.4 で入ったLD_AUDITという便利な機能を使うと、わずか30行程度、5分くらいのコーディングで、ConTestもどきが実現できてしまいます。テスト対象のプログラムの再コンパイルは不要です。ただし、「共有変数へのアクセスかどうか」を調べて yield() するのはちょっと大変で、5分では書けない感じがするので、今回は

  • 適当なタイミングでテスト対象プログラムの実行に割り込んで
  • 適当な確率で yield() する*1

だけにしました。こんなテキトーな方針でも、それなりに効果がありました。


まず、dW上のJavaで書かれたサンプルプログラム、NakedNamePrinter を C++ に機械的に移植します。

#include <string>
#include <boost/thread.hpp>
namespace {
  std::string firstName;
  std::string surName;

  class NakedNamePrinter {
    class FirstNamePrinter {
    public: void operator()() {
        std::printf("%s", firstName.c_str());
      }
    };
    class SpacePrinter {
    public: void operator()() {
        std::printf(" ");
      }
    };
    class SurnamePrinter {
    public: void operator()() {
        std::printf("%s", surName.c_str());
      }
    };
  public:
    NakedNamePrinter(const std::string& firstName_, const std::string& surName_) {
      firstName = firstName_;
      surName = surName_;
      boost::thread_group t;
      t.create_thread(*(new FirstNamePrinter)); // leakは無視で
      t.create_thread(*(new SpacePrinter));
      t.create_thread(*(new SurnamePrinter));
      t.join_all();
    }
  };
}

int main() {
  NakedNamePrinter printer("Washington", "Irving");
  std::printf("\n");
  std::fflush(stdout);
}

次に、ConTestモドキをCで実装します。同じくまずはコードを示します:

// kontest.c (LGPL)
#define _GNU_SOURCE
#include <pthread.h>
#include <link.h>
#include <fcntl.h>
#include <unistd.h>

static int fd = -1;
unsigned int la_version(unsigned int version) {
  fd = open("/dev/urandom", O_RDONLY);
  return LAV_CURRENT;
}

unsigned int la_objopen(struct link_map * lmp, Lmid_t lmid, uintptr_t * cookie) {
  return LA_FLG_BINDTO | LA_FLG_BINDFROM;
}

// 次のマクロは、glibcソースコードの elf/tst-auditmod1.c より拝借
# define pltenter la_x86_64_gnu_pltenter
# define pltexit la_x86_64_gnu_pltexit
# define La_regs La_x86_64_regs
# define La_retval La_x86_64_retval
# define int_retval lrv_rax
// ここまで

ElfW(Addr)
pltenter (ElfW(Sym) *sym, unsigned int ndx, uintptr_t *refcook,
          uintptr_t *defcook, La_regs *regs, unsigned int *flags,
          const char *symname, long int *framesizep)
{
  unsigned int v;
  // ここのさじ加減は「適当」です。要調整
  if (read(fd, &v, sizeof(unsigned int)) == sizeof(unsigned int) && v % 40 == 0) {
    // nanosleep(&(struct timespec){0, 1}, NULL); // 没
    pthread_yield();
  }
  return sym->st_value;
}

#if 0
// la_symbind64 でyieldするのは間違いでした。コメント欄を見てください (nminoruさんありがとうございました)
uintptr_t la_symbind64 (Elf64_Sym *sym, unsigned int ndx, uintptr_t *refcook,
                        uintptr_t *defcook, unsigned int *flags, const char *symname) {
  unsigned int v;
  if (read(fd, &v, sizeof(unsigned int)) == sizeof(unsigned int) && v % 4 == 0) {
    pthread_yield();
  }
  return sym->st_value;
}
#endif

la_version(), pltenter() などは、LD_AUDITインタフェースの規約であらかじめ決められた関数名です。これらの関数が含まれたkontest.cを次のようにコンパイルして.soにします。

 zsh% gcc -Wall -fPIC -shared -o kontest.so kontest.c -lpthread

で、お馴染みのLD_PRELOADと同様の方法で、LD_AUDIT=kontest.soを指定しつつ、プログラムを実行します。

 zsh% LD_AUDIT=/path/to/kontest.so ./nakednameprinter

すると、規約であらかじめ決められたタイミングで、kontest.soのpltenter()などが呼び出されるようになります。これを利用し、pltenter()の中でyield()するというのが今回のアイディアです。la_symbind64()は pltenter()は、(nakednameprinterがリンクしている共有ライブラリ上の)関数が呼び出される直前に、毎回呼び出されます*2。今回はこの中で、約2-3%の確率で pthread_yield() するようにしてみました(この値は適当に決めました)。私はx86_64環境で作業しているので、その他の環境の方はソースコード中の#defineを、glibcソースコードを参考に適切に書き換えてください。

結果


ConTestもどきの上でのプログラム実行はこんな感じで行います:

# ConTestもどきのコンパイル(.soにします)
[yupo@ath64]~/test% gcc -Wall -fPIC -shared -o kontest.so kontest.c -lpthread

# NakedNamePrinterもどきのコンパイル
[yupo@ath64]~/test% g++ -Wall NakedNamePrinter.cpp -o nakednameprinter -lboost_thread

# ConTestもどきを使わないでNakedNamePrinterを1000回実行し、結果を集計
[yupo@ath64]~/test% ( for ((i=0; i<1000; i++)); do ./nakednameprinter; done ) | sort | uniq -c
   1000 Washington Irving

# ConTestもどきの上でNakedNamePrinterを1000回実行し、結果を集計
[yupo@ath64]~/test% ( for ((i=0; i<1000; i++)); do LD_AUDIT=./kontest.so ./nakednameprinter; done ) | sort | uniq -c
     10  IrvingWashington
     20  WashingtonIrving
      1 IrvingWashington
    954 Washington Irving
     15 WashingtonIrving

バグありプログラムであるNakedNamePrinterを普通に実行すると、1000回中1000回、正しい結果が得られてしまっていますが、ConTestもどき上で実行すると、1000回中954回しか正しい結果が得られていません。逆に言うと、ConTestもどきの上でユニットテストを実行すれば、20回に1回くらいは問題を検出できそうだ ということです。まぁまぁ良い値なのではないでしょうか。

参考資料


LD_AUDITの使いかたは、あまりドキュメント化されていないようですが、探せばいくつかあります。


(1) リンカーとライブラリ, 実行時リンカーの監査インタフェース

まずは、Sun Solarisのマニュアル(pdf, p.165-)。日本語です。


(2) Solarisの /usr/demo/link_audit/src/*.c

上記のpdfから参照されているSolaris向けのサンプルプログラムも参考になります。Solaris 9/10のマシンがあればインストールされているでしょう。多少改変しないとLinuxではコンパイルできませんが、簡易プロファイラを作る例などが入っていました。


(3) glibc-20060306T1239/elf/tst-auditmod1.c

glibc(>=2.4)のソースコード、特に tst-auditmod1.c は参考になります。la_<<アーキテクチャ名>>_plt{enter,exit} 関数の関数名と引数はアーキテクチャ毎に異なりますが、どのように書けば良いのかこのファイルを見ればわかります。elf/*.c を良く読めば、LD_AUDIT をどう実現しているかの仕組みもわかるはずです(わたしはまだあまり読んでいませんが :-)。


(4) 最近のLinuxの /usr/include/link.h

LD_AUDITに指定する.soに含めるべき関数のシグネチャは(3)とこのファイルを見ればわかります。


ほかのやりかた


今日の kontest.so 以外の方法で、似たようなことを実現する方法3つです。


(1) カーネルでほげほげする

Linux Kernel向けの実装(スレッドの切り替えをものすごい頻度で行ってどうたら)があった気がします。でも自分でカーネルをコンパイルして入れ替えるの面倒。。


(2) Valgrindのtoolである Helgrind を使う

用途によっては悪くないかもしれない。でも、Helgrindは最近のValgrindでは一時的に使えなくなってるんで。。

[Valgrind v3.1.1 release note]

Please note that Addrcheck and Helgrind are still not working. Work is underway to reinstate them (or equivalents). We apologise for the inconvenience.


(3) テスト対象を gcc -finstrument-functions で再コンパイルして、__cyg_profile_func_enter() をLD_PRELOADしてpthread_yield()する

テスト対象の再コンパイルめんどくさー。。

まとめ


kontest.so を使うと、マルチスレッドプログラムのバグを効率的に見つけることができる(かもしれません)。

あ...そうだ、本物のConTestのソースコードは大変失礼ながら読んでいません。。。全然違うものだったりしたらゴメンナサイ。


2005-05-29 01:00

nminoruさんにコメント欄でご指摘いただいた件を修正しました。ありがとうございました。

*1:別スレッドに制御を譲るAPIは、Linuxでは pthread_yield() ですね

*2:どの関数から呼ばれたかも、pltenter()の引数 symname を見ればわかるようになっています。ですから、本物のConTestがやっているように、特定の関数だけを狙い撃ちしてyield()することも容易

nminorunminoru 2006/05/28 23:49 あれ la_symbind64() は関数が呼び出される直前に毎回呼び出されますか?
シンボル解決がされた時のみに呼び出されると思っていました。

yupo5656yupo5656 2006/05/28 23:59 あれ、やっちゃったかな。。確認してみます。

yupo5656yupo5656 2006/05/29 01:02 ご指摘の通り、誤解していました。ありがとうございます。とりあえずla_x86_64_gnu_pltenter()を使うように修正してみましたが、如何でしょうか?

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

Connection: close