Java の ConTest っぽいものを、glibcの新機能(LD_AUDIT)を使って Linux + C/C++ で実現してみる
たまには何か書きます。C/C++のマルチスレッドなプログラムのユニットテストでバグを効率的に見つけるためのライブラリ?の作成について。
IBM dWのConTest
はてなブックマークを眺めていたら、「ConTestを使用したマルチスレッド・ユニットのテスト - 並列テストが困難な理由とConTestの活用」というIBM developerWorksの記事が話題になっていました。
「(Javaの) 並列プログラム上での単体テストの問題点を解決する補助的なテスト手法」だそうで、例としてあがっているのは次のようなケースです。
- 名前を印刷するのに３つのスレッドを用意する
- それぞれ、「姓」「スペース」「名」を印刷する
- ３つのスレッドは同期を取っていない。つまりバグがある
- しかし、単体テストを行っても、ほぼ毎回、「姓」「スペース」「名」という正しい順序で（スレッドが実行）されてしまい、バグを検出できない
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;
}
#endifla_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 以外の方法で、似たようなことを実現する方法３つです。
(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さんにコメント欄でご指摘いただいた件を修正しました。ありがとうございました。
