2012年12月15日土曜日

Boost.Context on Cygwin

1.51.0 において Boost.Context がリリース入りしました。Boost.Context はコンテキスト切り替えのためのライブラリです。コンテキストの最も一般的な訳語は「文脈」ですが、この場合は実行中のアドレス、CPU のレジスタなど、実行時の状態情報とでもいうべきものです。(プリエンプティブ)マルチタスクは OS がこのコンテキスト情報を切り替えることで成立していますが、これを自前で切り替えられるようにするのが Boost.Context です。あるいは、setjmp/longjmp だと setjmp した時点に戻ることしかできませんが、longjmp した時に同時に setjmp が実行されその場所にまた戻ることが出来ると言っても良いかもしれません(スタックの取り扱いが違いますが)。 これが出来て何が嬉しいかというと、C# の yield みたいなことが実現できるわけですが、それはともかく。CPU のレジスタとか書いていることでお分かりかもしれませんが、Boost.Context は C/C++ の範囲では実現できません。ということでアセンブリ言語で実装されています。Windows だと MASM が要求されるのが面倒だったので gas に移植(というほどのこともないですが)し、Cygwin でビルドできるところまで到達したのですが、example の jump.cpp をコンパイル、動作させてみると、コンテキストを切り替えた先の文字列出力で詰まってしまいました。

//          Copyright Oliver Kowalke 2009.
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)

#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>

#include <boost/assert.hpp>
#include <boost/context/all.hpp>

namespace ctx = boost::context;

ctx::fcontext_t fcm;
ctx::fcontext_t * fc1 = 0;
ctx::fcontext_t * fc2 = 0;

void f1( intptr_t)
{
        std::cout << "f1: entered" << std::endl;
        std::cout << "f1: call jump_fcontext( fc1, fc2, 0)" << std::endl;
        ctx::jump_fcontext( fc1, fc2, 0);
        std::cout << "f1: return" << std::endl;
        ctx::jump_fcontext( fc1, & fcm, 0);
}

void f2( intptr_t)
{
        std::cout << "f2: entered" << std::endl;
        std::cout << "f2: call jump_fcontext( fc2, fc1, 0)" << std::endl;
        ctx::jump_fcontext( fc2, fc1, 0);
        BOOST_ASSERT( false && ! "f2: never returns");
}

int main( int argc, char * argv[])
{
        ctx::guarded_stack_allocator alloc;

        void * base1 = alloc.allocate(ctx::guarded_stack_allocator::default_stacksize());
        BOOST_ASSERT( base1);
        fc1 = ctx::make_fcontext( base1, ctx::guarded_stack_allocator::default_stacksize(), f1);
        BOOST_ASSERT( fc1);
        BOOST_ASSERT( base1 == fc1->fc_stack.sp);
        BOOST_ASSERT( ctx::guarded_stack_allocator::default_stacksize() == fc1->fc_stack.size);

        void * base2 = alloc.allocate(ctx::guarded_stack_allocator::default_stacksize());
        BOOST_ASSERT( base2);
        fc2 = ctx::make_fcontext( base2, ctx::guarded_stack_allocator::default_stacksize(), f2);
        BOOST_ASSERT( fc2);
        BOOST_ASSERT( base2 == fc2->fc_stack.sp);
        BOOST_ASSERT( ctx::guarded_stack_allocator::default_stacksize() == fc2->fc_stack.size);

        std::cout << "main: call start_fcontext( & fcm, fc1, 0)" << std::endl;
        ctx::jump_fcontext( & fcm, fc1, 0);

        std::cout << "main: done" << std::endl;

        return EXIT_SUCCESS;
}

このコードは本来、

main: call start_fcontext( & fcm, fc1, 0)
f1: entered
f1: call jump_fcontext( fc1, fc2, 0)
f2: entered
f2: call jump_fcontext( fc2, fc1, 0)
f1: return
main: done

と出力されて終了するのですが、main: call start ... の行だけ出力されて詰まってしまう状態です。実際にハイライトされている 22 行目で詰まっていたわけですがこれは Cygwin 内部の仕組みのせいでした。

規格に定義されているわけではありませんが、一般的に、ローカル変数(自動変数)、関数の引数などはスタックと呼ばれる領域に格納されています。関数の呼び出しがネストするごとにスタックは伸びていきます。setjmp/longjmp ならば戻るだけ、なので伸びた先のことは忘れてしまえばいいわけですが、コンテキスト切り替えによってまた戻ってくるためにはスタックの状態が保存されていなければなりません。ということで Boost.Context ではスタック領域自体を別に用意した領域に切り替えます。この時、OS 側で管理している情報である NT TIB(Thread Information Block) のスタック情報(top と bottom)も切り替えています。一方、Cygwin ではスタックの底に cygtls というスレッド固有の情報を格納しており、NT TIB を経由して参照しています。このため、Boost.Context によるコンテキスト切り替えの結果、NT TIB が指すスタックの底に cygtls が存在しないことになり(恐らく排他制御に失敗して)詰まってしまっていたわけです。

実際、f1(), f2() 内の出力をコメントアウトすると、正しく切り替え出来 main: done も出力されます(NT TIB が元のスタックの底を指すため)。コンテキスト切り替え先で Cygwin のシステムコールがまともに使えないのはペナルティが大きすぎるので、NT TIB のスタック情報を切り替えをしない版を作ってみたところ正しく動作しているようです(Boost.Context gas on Windows パッチ)。

スタック領域のチェックをするだとかいったデバッグ系ツールと組み合わせられないでしょうが他は大丈夫だと思っているのですがどうでしょうか。

2012年12月8日土曜日

【C++ Advent Calendar 2012】 8日目 「C++ Compiler Farm の紹介」&「キャストの復習」

このエントリは C++ Advent Calendar 2012 8 日目の記事です。

C++ Advent Calendar 2012 というからには普通 C++ のネタを提供するものですが、一応、C++ 関連ではあるのですが言語仕様でもなければライブラリでもないネタです。それだけではなんなので一応小ネタとして「キャストの復習」という内容も書いてみます。

C++ Compiler Farm の紹介

既に一度 Twitter 上で流したネタではあるのですが、「C++ Compiler Farm」 というサイトを作ってみました。

C++ は言語仕様が複雑であり、かつ、標準実装や唯一の実装のようなものが存在しないこともあり処理系によって挙動がまちまちである、というのは C++er は身に染みて良く知っていることだと思います。それでは皆さんの周辺ではコンパイラは何種類くらい利用可能でしょうか?無償利用可能なコンパイラに限っても世の中に結構な数があるわけですがそんなにたくさん常用できる状態にはない、という人も結構いるのではないでしょうか? C++ Compiler Farm はオンラインで複数の C++ コンパイラによるコンパイル結果、実行ファイルの実行結果を確認できるサービスです。

以前 Twitter 上で流した時点ではコンパイル、実行結果の確認はできる、という状態でしたが、結果を後から参照することができませんでした。今回機能強化を果たし、http://ccf.myhome.cx:5000/result/1 のようなリンクで実行結果を後から参照することができるようになりました。これでコンパイラによって挙動が違う、などと言った時に他の人に結果を見せやすくなるんじゃないかな、と期待しています。

コンパイラ無選択状態でも実行可能だったり、全ての結果が保存されたり、編集できなかったりまだまだ低機能ですが利用者がちょっとでも居そうであればちょこちょこやっていこうかと思っています。なお関連ソースコードは https://github.com/yak1ex/ccf で公開しています。

C++ Advent Calendar で紹介しておきながらあるまじきことですが、ほとんど Perl で実装されています。なので概要だけ構成を説明しておくと以下の図のような構成になっています。

AWS EC2 上で Windows / Linux サーバ Micro instance 各1台。それぞれでコンパイルサーバが実行されており、Web サーバは Linux 側。ブラウザ上の Javascript と協調しながら処理する感じです。サーバ側では非同期処理フレームワーク AnyEvent を使っていますので、C++er としては Boost.Asio とかで書けると格好いいところなんですが。サンドボックス部分だけ、Google Chrome のオープンソース実装である Chromium の C/C++ コードを一部修正して使用しています。これで system("rm -rf /"); とか入力されても問題ないようになっています(http://ccf.myhome.cx:5000/result/7)。……そのはず、です。Windows 側はメッセージなしで黙って無視される形ですね。実行時間、使用メモリについても制限をかけています。相変わらず Amazon Web Services 無料範囲内での運用で、使用資源を絞った状態ですが以前よりはちょっと緩めました。この辺は調整だと思っていますので使用実績が増えれば考えるための材料も増えるかと思っています。

「C++ Compiler Farm」を紹介させて頂きました。皆様の C++ life に少しでも役立てば幸いです。

キャストの復習

ということで小ネタ「キャストの復習」です。最初に言っておきますが、規格上どうか、という話であって、実装上は概ね変わらないとかそういう割と役に立たない話になります。また、アラインメントについて省略したり正確な表現でなかったりします。

さて、C++ キャストは以下の 4 種類あります。

  • const_cast
  • dynamic_cast
  • reinterpret_cast
  • static_cast

このうち const_cast は const 外し、dynamic_cast は安全なキャストであるかどうかを判定できる、という点で位置づけは割と明快です(dynamic_cast の使いどころはどこか、というのはそれはそれで議論になりそうですが)。ということでたまに使い分けで議論になる reinterpret_cast と static_cast について、特にポインタの場合について掘り下げてみようと思います。

が、その前に C-style キャストについても確認しておきましょう。C++ においては C-style キャスト (type)value は以下の C++ キャストとして解釈可能なもののうち先にあるものと解釈されます(14882:2011 5.4p4)。

  • const_cast 1回
  • static_cast 1回
  • static_cast 1回 + const_cast 1回
  • reinterpret_cast 1回
  • reinterpret_cast 1回 + const_cast 1回

つまり文脈によってどのように解釈されるかが変わります。

C 言語において割と暗黙のうちに仮定されているんじゃないかという前提として、ポインタのキャストでは指す位置は変わらない(値は変わらず解釈が変わる)、というものがある気がします(注:C 言語においてもchar* への変換以外規格上その保証はありません(9899:1999, 9899:2011 6.3.2.3p7)。ついでに strict aliasing rule 的に char* 系以外の別の型へのポインタ経由でアクセスすると未定義動作です(9899:1999, 9899:2011 6.5p7)。一方で、C++ においてはポインタのキャストでその値(指している場所)が変わる場合が有り得ます。

以下のような継承がされているクラス群がある場合、

struct A { int n; };
struct B { int n; };
struct C : A, B { int n; };

C 型のオブジェクト内に A 型、B 型のオブジェクトが含まれる形となり、かつ先頭位置を C 型と共有可能なのは A 型か B 型かいずれか一つしかないことになります。規格上定義されていませんが典型的にはメモリレイアウトは以下の図のようになります。

図のようにA型、B型の順に並んでいるとして、C* を B* に static_cast すると C の中にある B の先頭を指すことになり、つまり、指す位置が変わります。逆に B* を C* に static_cast しても指す位置が変わります。この場合、もともと C 型のオブジェクト中の B 型オブジェクトを指していない場合などは不正な位置を指すことになります。つまりこのキャストはいつでも安全とは言えないのですが、static_cast はstandard conversion として規定されている型変換の逆方向のキャストもできると規定されている(14882:2003 5.2.9p6, 14882:2011 5.2.9p7)ため一律コンパイル可能です(もちろん不正な位置を指す場合には未定義動作ですが)。つまり「static_cast ならば安全なキャストだ」というわけではありません。

では static_cast の立ち位置とはなんでしょう?上の段落で単なる「キャストする」ではなく「static_cast する」と明示したことに気付かれたでしょうか?C++03 以前では、reinterpret_cast でのポインタのキャストについてはヌルポインタがヌルポインタのままであること(14882:2003 5.2.10p8)、T1* → T2* → T1* で元に戻ること(14882:2003 5.2.10p7)以外は未規定(unspecified)であり可搬性のあるコードを書くならば reinterpret_cast は使うな、が基本でした。つまり、上のような B* → C* あるいは C* → B* についても(続けてやれば元に戻ること以外) reinterpret_cast の結果について言えることはありませんでした。つまり(未定義動作の場合もあるけど)結果が規定されている static_cast と規定されていない reinterpret_cast という位置づけだった訳です。

C++03 以前において例えば char* を unsigned char* にキャストする(規格上)可搬性のある方法は、void* を経由して static_cast する方法でした。

char *pc;
// unsigned char* upc = static_cast<unsigned char*>(pc); // COMPILE ERROR
unsigned char* upc = static_cast<unsigned char*>(static_cast<void*>(pc));

void* への変換は指す位置が変わらないという規定があります(14882:2003 4.10p2)。一方、void* へ変換して元の型に戻すと同じ場所を指すという規定もあるため(14882:2003 5.2.9p10)、void* からのキャストも指す位置は変わらないことになります。一方、以下のコードもコンパイルは通りますが、

char *pc;
unsigned char* upc_bad1 = (unsigned char*)pc;
unsigned char* upc_bad2 = reinterpret_cast<unsigned char*>(pc);

この C-style キャストは(static_cast ではキャストできない変換なので)前述の通り reinterpret_cast として解釈されます。これも前述の通り reinterpret_cast では結果が保証されないためこのコードは可搬性がありません(pc と upc_bad* で同じ位置を指している保証がない)。

というのが、C++03 以前の話。C++11 では reinterpret_cast の規定が変わりました(14882:2011 5.2.10p7)。

An object pointer can be explicitly converted to an object pointer of a different type. When a prvalue v of type “pointer to T1” is converted to the type “pointer to cv T2”, the result is static_cast<cv T2*>(static_cast<cv void*>(v)) if both T1 and T2 are standard-layout types (3.9) and the alignment requirements of T2 are no stricter than those of T1, or if either type is void. Converting a prvalue of type “pointer to T1” to the type “pointer to T2” (where T1 and T2 are object types and where the alignment requirements of T2 are no stricter than those of T1) and back to its original type yields the original pointer value. The result of any other such pointer conversion is unspecified.

太字下線部分が大体追加された規定で、standard-layout type へのポインタ間の場合、void* を経由する static_cast 2回と等価、つまり↑で可搬性がある方法としていたものになります。standard layout type は規格の範囲で(パディング等はあるけど)メモリレイアウトが決まる型のことです。char, unsigned char については standard-layout type なので、C-style キャストの場合も含めて↑で可搬性がないとしていたコードが可搬性があることになりました。世の人々も指す位置が変わらないと思って reinterpret_cast を使ってるし実装も他に選択肢がなくまず間違いなくそうなってるし、という理由で規定が変更されています(DR658)。もともとコードの見た目でキャストの位置づけが分かるように、という意図で C++ キャストが分けられていたはずなのですが、まぁ現実には勝てない、というところなのでしょうか。

さて、これを B*, C* の例に適用すると、クラスについては、メンバ・基本クラスに非 standard-layout class がないこと、メンバに参照なし、仮想関数・仮想基本クラスなし、継承階層中非静的メンバをもつクラスは自分自身を含めて高々一つ、が standard layout class となるため、B は standard-layout type ですが、C は standard-layout type ではありません。結果、reinterpret_cast についてはやっぱり何も言えない、ということになります。実際には C++03, C++11 いずれの実装であっても指す位置が変わらない、というのが普通の実装でしょう(指す位置を変える積極的な理由がない)。ということを示そうとしたのが http://ccf.myhome.cx:5000/result/12 です。いずれの処理系においても static_cast では指す位置が変わる場合があり、reinterpret_cast では指す位置が変わっていません。なおこのコードでは reinterpret_cast によるポインタと整数との変換をしています。これ自体も(整数のサイズが十分であれば)一周回れば元に戻る、以外はどのような変換が実施されるかは処理系依存です(14882:2003, 14882:2011 5.2.10p5)(そしてアドレスをそのまま整数値とする実装が多いでしょうし、このコードは少なくとも変換が単射であることを期待したコードですので厳密には可搬性はありません)。個人的にはこのポインタと整数の相互変換が C++03 以前で reinterpret_cast を使うべき唯一のケースだと思っています。

さて、「キャストの復習」と題して、static_cast、reinterpret_cast によるポインタの変換について、C++11 での変更を含めてお送りしました。今後 C++ コミュニティにおいて reinterpret_cast の位置づけがどのようになるのか(一部の異なるポインタ型の変換について正当な手段とされるのか、あくまでも処理系依存や未規定なキャストについてのみ使うべきとされるのか)、興味深いところではあります。

まとめ

C++ Advent Calendar 2012 8日目として、「C++ Compiler Farm の紹介」と「キャストの復習」をお送りしました。C++ Advent Calendar 2012 明日の担当は @Flast_ROさんです。お楽しみに→【にゃははー】

2012年9月30日日曜日

YAPC::Asia Tokyo 2012 参加メモ

ブログ書くまでが YAPC::Asia らしいので。/.-j にしようか迷ったけど一応こちらで。

1日目、2日目で参加。1日目は新幹線が 80 分くらい遅れたため残念ながら Larry 氏のセッションは聞けず、その後から参加。YAPC 参加者は Web 界隈の人が多いんじゃないかと思っているが、そういう意味ではそもそも日常業務的に Perl どころがプログラミングも(基本)しないという点で特異な参加者な気もする(1日目は年休取得して参加)。ということで Web サービス寄りよりかは Perl 本体寄りのセッション選択、のはず。以降、各セッションの雑多なメモとか感想とか。

一日目

Acmeism, Pegex and CoffeeScript on CPAN

40 分の枠に収まらなかった感じ。もうちょいちゃんと聞きたかった。

リアルタイム通知システムの舞台裏

C++ Compiler Farm みたいなものを作っていて通知ではなくバックエンドのコンパイルサーバについてだがこの辺の管理(どのサーバに投げたか)とかどうしようというのと通ずるものがある気がした。メッセージキュー(RabitMQ)で解決したみたいだが、CCF では S3 がその位置に来そう。

Perl初心者が作ったサーバ運用ツール

英語での発表。運用ツールそのものについて自分に知見がないけど、テストがある、というのが重要なところか。ただこれ、テスト可能なように設定を綺麗に分離してやるというか、role と blueprint との関係が重要な気がする。

GitHubを使った開発とデプロイ

丁度 Perl モジュールの fork とかし始めたところだったのでそういう話なのかなと(勝手に)期待していたけどそうではなく普通にプロジェクトの中心リポジトリとして Github を使う感じだった。

Distributed Job System. Clutch

中央サーバを必要とせずクライアント側で振り分ける分散ジョブシステム、だろうか。多分構成次第? 多対多になるなら間に中央管理サーバを置いた方が楽になる気がするし、振り分け先が動的に変化するケースだと難しくなったりするんじゃないだろうか。

DBD::SQLite: Recipes, Issues, and Plans

正直一番実用的だったかもしれない。解析の仕方から考えなきゃならないデータに対してとりあえず DB に突っ込んで SQL で色々料理してみるというのはかなり強力なスキームだと思っているが、その上で SQLite は強い味方である。で、DB へのデータ投入とか SQL が苦手な処理をする時に一旦外でやろうとする場合などで DBD::SQLite はお世話になりまくりである。bulk insert は自分も prepare/分割commit/各種pragma on でやってたのでお墨付きをもらった感が。複数レコード insert は今度試してみたい。その他、DBD::SQLite ユーザーは一度軽く資料を眺めておくといいんじゃないかと思う。

Profiling memory usage of Perl applications

TreeMap によるメモリ使用量の視覚化デモが格好良かった。使われていたのは JavaScript InfoVis Toolkit だろうか。Interactive な視覚化をやるのに Javascript を使うというのは環境も(あまり)選ばないし便利な気がする。

平均レスポンスタイム50msをPerlで捌く中規模サービスの実装/運用

実際の内容についてはどうこう言えることはないのだが、前振りのアドテック業界について、が非常に分かりやすい導入だったと思う。

Perlアプリケーションのベンチマークとプロファイリング

↑のセッションでもそうだがとにかく計測すること、視覚化することがまず重要か。CCF なんかはとりあえず立ち上げてるだけなので試せるといいなぁ。

LT

相変わらずネタ満載。

二日目

「新しい」を生み出すためのWebアプリ開発とその周辺

今回のベストトーク賞受賞セッション。企画の部分は、Web アプリに限らず何か作ろうと思ってる万人に得るものがあるのではないかと。実装については枯れたものを使えば十分というあたり? 11月末~12月発売予定という「Webサービスのつくり方」は期待大。

Padre - The Perl IDE for Normal People

Emacs ユーザーと Vim ユーザーが聴取者の大半というのが印象的。自分も Emacs も Vim もプログラミングに使わないけど IDE も(ほとんど)使わないという点で Normal People からは外れてるわけだけど。Perl ユーザーが拡張とかしやすいのは Perl で書かれた IDE というのはそうかもしれないけど Perl のコアユーザー層が IDE 使ってないわけで。Eclipse なんかは企業からの後押しが大きかったわけだし、一般ユーザー層への拡大の需要というかそういうのがないと難しいかもしれない。

Perl 今昔物語

日記をさらってみたところ自分は 2008 が初参加の模様。この手のイベント自体が初参加だった。2010 は 2 日目だけ参加、2011 はキャンセル(海外出張)。参加してない部分のタイムテーブルを見ると聞いときゃ良かったというのが結構ある。今後はもう少し参加に貪欲になってもいいかもしれない。内容としてはPerl で書く必然性が薄れてきた、みたいなことを言われていたのが印象的だった。他のセッションの内容にもその辺が出てきているような気がする。

Perl と SQL のいろいろ

DBI/DBD についての分かりやすいチュートリアル。周辺モジュールの簡単な紹介もあって参考になった。質問タイムでプレースホルダの強制ができないんで O/R マッパー使ってるみたいなコメントがあって、プレースホルダの使用くらいプログラマとして最低限度の常識じゃないのかと思ったけど現実はそうもいかないんだろうなぁというのが悲しいところ。

シリコンバレーと世界のPerlエンジニア

川崎さんがアクティブ過ぎて眩しい。「10年後に食える仕事 食えない仕事」から引用されてた「グローカル」「ジャパンプレミアム」「無国籍ジャングル」「重力の世界」っていうのは興味深い。元々の本だとプログラマは「重力の世界」みたいだけど日本の適当な開発要求とのブリッジングという位置では立ち位置はありそう。それはそれでしんどそうだけど。

Perlで始める!初めての機械学習の学習

メモ見たら PRML 同人誌とだけ書いてあったw。とりあえず手に入れたいと思う。perl-kinect は面白そうなので公開されないかなぁ。

Perl入学式をやってみた!

期待していなかったのだが(ごめんなさい)、熱い思いを感じられるいいセッションだったと思う。「ハードルを下げることを重視する」「継続して参加できる環境を作る」というのは他のイベント主催の人も参考にできるかもしれないが、このレベルまで頑張るのは相当大変なことだと思う。あと、Perl 入学式参加者の Perl のわかりにくかったところとして、リファレンス(-> が省略できる場合がある)、コンテキストの概念、ファイルハンドルの , の省略、辺りが挙がってたのはそうだよなぁ、と思わざるを得ない。慣れてくると大丈夫だし逆に楽に書ける要因になったりもするんだけど、場合に応じてうまい具合に挙動が変わる、は、むしろ初めての人にはわかりにくい、と。

Performance Profiling with Devel::NYTProf

他のセッションでも言われていたけど、まず計測しろ、と。あと、目標達成したらそれ以上余計な事しない。局所的な変更から積み上げる。

LT

相変わらずネタ満載。

How Perl Changed My Life & Closing

総括感想も含めて。なんだろう、所詮 Perl はプログラミング言語の一つな訳だけど、TMTOWTDI に代表されるその精神というかそういうのがコミュニティにも有ってそれだけ懐が深いというか、Closing で牧さんが the most welcoming conference みたいなこと書いてたけどそういうのが有るんじゃないかな、と。忘れていたけど自分としては初参加のイベントが YAPC::Asia 2008 だった訳で、そこから色々参加(だけは)するようになったのを考えるとそれなりに大きな転機だったのかもしれないとも思う。そういう意味で Perl ってのは自分の中で結構大きい割合を占めているかもしれない。実際「Perl は生活、C++ は趣味」という感じで技術ネタは C++ が多いけど実際書いてたり日常使ってるものは Perl の方が多かったりするし。今現時点で Perl を選ぶ理由ってのはそんなにないのかもしれないけど、でも自分は Perl が好きなんだなぁ、と思う。で、スピーカーの人にはせっかくの YAPC なので別に Perl べったりの内容にする必要はないと思うんだけどもう少し Perl 寄りの発表をして欲しいなぁという気持ちもあったり。まぁとにかく来年も参加したいと思う。

2012年9月8日土曜日

小ネタ: Perl の警告: Deep recursion on subroutine ...

Perl では再帰呼び出しのネストが深いと警告してくれる機能がある。定石的に use strict; use warnings; していれば有効になっている。

use warnings;
sub dfs {
    if($_[0] < 101) { dfs($_[0]+1); }
}
dfs(0);
Deep recursion on subroutine "main::dfs" at ... line 3.

perldiag には "unless you're writing strange benchmark programs, in which case it indicates something else." などと書いてあったりするのだが、閾値が 100 であるためちょっと大きめのグラフに対して再帰で DFS かけたりしたら余裕で突破したりするのである。警告を抑制したい場合、Perl の警告はカテゴリ分けされているため再帰に関する警告だけオフにしてやればいい。

use warnings;
no warnings 'recursion';
sub dfs {
    if($_[0] < 101) { dfs($_[0]+1); }
}
dfs(0);

が、これだと全体で警告がオフになってしまう。Perl の警告制御は lexical scope である。これは限定した部分で警告をオン・オフできるということだが、

use warnings;
sub dfs {
    if($_[0] < 101) {
        no warnings 'recursion';
        dfs($_[0]+1);
    } # End of the effect of no warnings
}
dfs(0);

もう一つ、dynamic scope ではない、ということも意味している。つまり、以下では警告は抑制されない。

use warnings;
sub dfs {
    if($_[0] < 101) {
        dfs($_[0]+1);
    }
}
no warnings 'recursion';
dfs(0);

実際に deep recursion が発生するのは dfs(0); の実行中じゃないかと思ってしまうのだが、字面上(lexical)は 4 行目の dfs 呼び出しで発生するからだ。

2012年9月4日火曜日

Variadic Template にまつわる Workaround

C++11 は確かに便利、なのだが現状はまだ実装が十分と言えず回避手段(workaround)を取らざるを得ない場合がある。の割には余りそういう説明を見ない、ということでせっかく書いたのでメモってみる。まぁ Boost のソースコードの中にたくさん埋まっているのだろうし、ひょっとしたら C++er は息をするように workaround が書ける人種なのかもしれないが、そこはそれ。

sorry, unimplemented: use of ‘type_pack_expansion’ in template

#include <utility>
struct B { int operator()(int n) const { return n; } };

template<typename C>
struct A {

#if __GNUC__ == 4 && (__GNUC_MINOR__ <= 5 || __GNUC_MINOR__ == 6 && __GNUC_PATCHLEVEL__ == 0)

  template<typename ... Args>
  struct deduce {
      typedef decltype(C()(std::declval<Args&&>()...)) type;
  };
  template<typename ... Args>
  typename deduce<Args...>::type operator()(Args && ... args) const
  { return C()(std::forward<Args>(args)...); }

#else

  template<typename ... Args>
// sorry, unimplemented: use of ‘type_pack_expansion’ in template
// http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48292
  auto operator()(Args && ... args) const -> decltype(C()(std::forward<Args>(args)...))
  { return C()(std::forward<Args>(args)...); }

#endif
};

このエラーメッセージが出るのは恐らくこの場合には限らないと思うのだが、type pack (Args ... みたいな展開)を tailing return type 中で使った場合。GCC bugzilla にも書いてある通り、別のクラスに切り出すことで回避できる。@iorate さんの記事([C++][Boost] C++ で一般化された on を書く)にも workaround の方法を含め書かれている。後は、GCC 4.6.1 から直っている、という情報くらいだろうか。

sorry, unimplemented: cannot expand ‘Args ...’ into a fixed-length argument list

#include <boost/fusion/include/vector.hpp>

#include <boost/fusion/adapted/mpl.hpp>
#include <boost/fusion/include/as_vector.hpp>
#include "variadic_bridge.hpp"

template<typename ... Args>
struct C {

#if __GNUC__ == 4 && __GNUC_MINOR__ <= 6

  typename boost::fusion::result_of::as_vector<
    typename yak::util::variadic_to_vector<Args...>::type
  >::type v;

#else

// sorry, unimplemented: cannot expand ‘Args ...’ into a fixed-length argument list
// http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39653
  boost::fusion::vector<Args...> v;

#endif
};

こっちはエラーメッセージを日本語対象でググっても合っているものは tweet 1件しかヒットしない。……みんな困ってそうなものなのだが。variadic な template parameter を非 variadic な template に渡せない、というものだ。自作ヘルパ variadic_bridge.hpp を使って variadic な template parameter を MPL vector に変換して、さらに boost::fusion::vector に変換している。まぁ MPL vector まで持って来られれば後はどうとでもなるとは思うが、一応、固定長引数として Metafunction Class に渡す variadic_to_fixed も用意はしてある。こっちは GCC 4.7.0 から修正。

まとめ?

そもそも VC は 2012 でも variadic template 対応してねーよ、という時点で PP するしかないという話なのが悲しいところ。

しかし、CSS はブラウザバグとその対処、みたいなものが結構見つかるのだが C++ についてはそういうまとめみたいなものはないのだろうか。

2012年9月2日日曜日

(今更) C++ で拡張メソッド

Transactional Memory について予告をしておきながら別ネタ。何で実装しようと思ったのかそのきっかけを忘れてしまっているが、今更 C++ で拡張メソッドである。func(a, x) のようにメンバ関数外のものが a.func(x) で呼べるというやつである。まぁ、「今更」というくらいであって既にやってる方は色々いるわけだが。@cpp_akira (faith_and_brave) さん (2008年)じくよろさん(でいいのだろうか?)(2009年)@gim_kondo さん(2011年)などが作られているわけである。

もちろん C++ 自体には拡張メソッドは存在しないのでそれっぽいものを実現する仕組みを自前で作ることになるのだが、基本的に C++ で拡張メソッド風なものを実装しようとした場合、拡張するメソッド(関数)以外に大体 3 つの構成要素が必要だと思われる。

  1. 対象のオブジェクト、あるいは、引数を保持するオブジェクト(以下ラッパと表記)
  2. 上記ラッパを作成、値を紐付けする仕組み(以下ラッパ束縛と表記)
  3. 紐付けされなかった方と結びつけて実際の呼び出しを行う仕組み(以下ラッパ呼び出しと表記)

これで先の方の実装について整理するとこんな感じだろうか。じくよろさんの実装は最終的にフリー関数へ転送しているが「func(a, x) を」という形式に拘らなければ関数オブジェクト内でそのまま拡張メソッドの内容を実装してしまえばいいのでそのように実装した場合として記述している。

実装ラッパラッパ束縛ラッパ呼び出し
@cpp_akira さん拡張メソッドの内容を表す関数オブジェクト内に引数も保持コンストラクタoperator| のオーバーロード(任意の1引数関数オブジェクトを受ける)
じくよろさん拡張メソッドの内容を表す関数オブジェクト内に引数も保持コンストラクタoperator, のオーバーロード(関数オブジェクト限定)
@gim_kondo さん拡張メソッドの内容を表す関数オブジェクト内に対象オブジェクトへの this ポインタを保持対象オブジェクトへのメンバテンプレート埋め込みとマクロ置換によるコンストラクタ呼び出し関数オブジェクトの呼び出し

@gim_kondo さんの実装は . (ドット演算子)で呼び出せるようになっているが拡張メソッド呼び出し側でのマクロ置換発生は代償としてちょっと evil だと思われる。この判断をした時点で基本的に演算子オーバーロードで実装ということになるのだが、今回選んだ演算子は ->* である。ほとんどの C++er は使ったことがないだろうと思われる、というかひょっとしたら存在を知ってる人すら少ないかもしれない。通常の使い方は以下のような形である。

struct A { void func(void) {} };

int main(void)
{
 void (A::*mp)(void) = &A::func;
 A a, *pa = &a;
 (pa->*mp)();
 return 0;
}

つまりメンバないしメンバ関数へのポインタを参照するためのものである。とりあえず括弧の付け方に注意。知らないとまず間違えると思う。とりあえずこれがなくて困るとは普通ならない(そもそも普通の使い方ならポインタに対して使う)し、メンバアクセスのための演算子なので拡張メソッドとしては意味は近いはず、ということから選定。

で、拡張メソッド的なものが作れるというのは分かっている上でなぜまた(特に需要もないのに)別に作るのか。↑で書いたとおり、C++ で拡張メソッドを作ろうとすると本来の拡張メソッドだけでなく他の仕組みも必要になるわけでそれが面倒い。できるだけ拡張メソッド本体以外の余計な部分は勝手に作成させたい。で作ってみたのがこんな感じ。内部実装は https://github.com/yak1ex/cpp_stuff/blob/master/extender.hpp にある。

#include <iostream>
#include "extender.hpp"

namespace test { struct A { int n; }; }

namespace ext {

DEFINE_EXTENDER1(test::A, func1, {
 typedef test::A& result_type; // MUST follow result_of protocol

 result_type operator()(test::A& a, int &n) const {
  std::cout << "int&" << std::endl;
  return a;
 }
 result_type operator()(test::A& a, const int &n) const {
  std::cout << "const int&" << std::endl;
  return a;
 }
});

DEFINE_EXTENDER2(test::A, func2, {
 typedef test::A& result_type; // MUST follow result_of protocol

 result_type operator()(test::A& a, int &n) const {
  std::cout << "int&" << std::endl;
  return a;
 }
 result_type operator()(test::A& a, const int &n) const {
  std::cout << "const int&" << std::endl;
  return a;
 }
});

}

int main(void) {
 using ext::func1;
 using ext::func2;

 test::A a = { 0 }; int n = 0;

 ((a->*func1)(1)->*func1)(n); // Cascading but unintuitive

// NOTE: different from ordinary operator semantics/precedence
 a->*func2(1)->*func2(n);

 return 0;
}

実行結果

const int&
int&
const int&
int&

g++ 4.[5678] それぞれで -std=c++0x 有無両方で動作を確認している(いくつか workaround も入っている)。通常の演算子の優先順位の意味論に従ったのが EXTENDER1 の方、使いやすさを優先したのが EXTENDER2。まぁ普通は EXTENDER2 の方だと思う。使う側としてはほぼ書きたい拡張メソッドの内容部分のみだけで実現できている、と言っていいと思う。マクロにしてあるが↓なので直書きでもそんなに変わらない。なお、上記の例では 1 引数同士で const の違いだけでオーバーロードしているが、任意の型で引数の数が違っている場合でもそのまま operator() を書けばオーバーロード可能である。

#define DEFINE_EXTENDER1(target, name, ...) \
struct BOOST_PP_CAT(name, _functor) : public yak::util::extender1<BOOST_PP_CAT(name, _functor), target> \
__VA_ARGS__ name
#define DEFINE_EXTENDER2(target, name, ...) \
struct BOOST_PP_CAT(name, _functor) : public yak::util::extender2<BOOST_PP_CAT(name, _functor), target> \
{ \
 struct _ __VA_ARGS__; \
} name

内部実装について簡単に説明すると、CRTP + Barton Nackman trick を使ってラッパと演算子を定義している形。上表と同じ形で書くと次のようになる。

実装ラッパラッパ束縛ラッパ呼び出し
EXTENDER1拡張メソッドの内容を表す関数オブジェクト内に対象オブジェクトも保持operator->* のオーバーロードで関数オブジェクトを返す関数オブジェクトの呼び出し
EXTENDER2引数を保持するオブジェクトを関数オブジェクトと別に用意operator() のオーバーロードでラッパを返すoperator->* のオーバーロード(ラッパ限定)

2012年8月4日土曜日

LL Decade 「君ならどう書く Online」 で書いたコード

本日(8/4)開催された、LL Decade では「君ならどう書く Online」という企画がありました(問題の内容はリンク先参照)。14:00 までという短い時間と告知がそれほど強いものではなかったこともあってか参加者は 14 名(+締め切り以降10名)(間違ってるかも)だったそうですが、おかげで商品をゲットすることが出来ました。問題発表前は C++ Template Meta Programming で書いて「コンパイルの必要もない Lightweight です(キリッ」とかやろうかと思ったのですが、文字列の validation ということで断念しました。で、順当に Perl で書いた訳ですがせっかくこういう場で書くんだから多少のひねりが欲しいところです。という訳で書いたのが以下のコード。文字列処理ということで正規表現さんにお出まし願ったわけですが、普段使わない機能を使ってみました。

#!/usr/bin/perl

# regexp 内でそれなりに頑張る

use utf8;
use strict;
use warnings;

local $/; # slurp
my $t = <STDIN>;
$t =~ s/^(
   (?<ipv4>(?&ipv4_))|
   (?<ipv6>(?&ipv6_))|
   (?<mac>(?&mac_))|
   (?<any>.*)
  )$
  |(?<spc>\s+)
  (?(DEFINE)
   (?<ipv4_1>1[0-9]{2}|2([0-4][0-9]|5[0-5])|[1-9]?[0-9])
   (?<ipv4_>(?:(?&ipv4_1)\.){3}(?&ipv4_1))
   (?<ipv6_1>[1-9a-fA-F][0-9a-fA-F]{0,3}|0)
   (?<ipv6_>(?:(?&ipv6_1):){7}(?&ipv6_1))
   (?<mac_1>[0-9a-fA-F]{2})
   (?<mac_>(?:(?&mac_1):){5}(?&mac_1)|(?:(?&mac_1)-){5}(?&mac_1)) # 格好悪い。backreference でいける?
  )/@{{
   ipv4 => '01',
   ipv6 => '10',
   mac => '00',
   any => '11',
   spc => '',
  }}{keys %+}/mxge;

print pack('B*', $t);

9,10 行目は Perl5 だと悲しい slurp。以降の(一応一つの)正規表現で 0 と 1 の文字列に変換してから pack() で普通の文字列に復元という流れになっています。18行目からの (?(DEFINE) で始まっている部分は正規表現パターンに対して名前を付けている部分です。(?<name>pattern) で pattern に対して name という名前を付け、(?&name) で呼び出している訳です。hoge_1 になっているのがアドレス構成要素 1 要素分、hoge_ になっているのがアドレス全体に対するパターンです。これを (?<name>pattern) で hoge として名前付きキャプチャしています(12行目から)。名前付きキャプチャの結果はハッシュ %+ に設定されるので、keys を使って有効なキャプチャ名(hoge)を取得し、ハッシュで値を置き換えています(25行目)。keys をリストコンテキストで評価したいので(ハッシュリテラルに対する)ハッシュスライスを使っています。わざわざハッシュリテラルを使っているのはその方がなんか格好良さそうだからです。spc 関連は改行削除用のものです。正規表現のオプションとしては、複数行に ^$ をマッチさせるための m、空白等を入れるための x、全体を置き換えるための g、eval するための e を指定しています。こうして変換した後は pack を使って変換して出力するだけです。

perlre とか見ながら即席で書いたにしてはなかなか面白みのあるコードに仕上がったんじゃないかと思います。IP アドレス等にマッチする正規表現そのものがあんまりいけてない感じなのがちょっと残念なところですが。もっと格好良い書き方がある気がします。

ちなみにもらった商品は、iOS プログラミング第2版(ISBN978-4-86401-049-8) なのですが、Mac 持ってないんですよね。iPad も会社支給(貸与)された今、MBP とかを買うべきと言うお告げだったりするのでしょうか。

2012年8月1日水曜日

A bit inside of Transactional Language Constructs for C++ - part.2 Intel TM ABI

前回 Part.1 では、Transactional Language Constructs for C++ (以下 TM 提案)について Atomic transaction の記述「他のスレッドが transaction の中間結果を観測しない」が、どのようなからくりになっているかを説明しました。Part.2 では、TM 提案と対とも言える文書、Intel TM ABI specification を元にコンパイラがどのように C++ TM を実現しようとするかについて覗いてみたいと思います。

TM 提案を実装しているコンパイラはいくつかありますが Intel によるプロトタイプ実装 Intel C++ STM Compiler, Prototype Edition というものがあります。Intel TM ABI とはこの実装で使用されている ABI です。元々 TM 提案は何が実現されるか(what)についてだけ規定しておりどのように実装するか(how)については規定していません。これはソフトウェア、ハードウェア、ハイブリッドといった区分を含め様々な TM 実装を利用できるようにするためです。コンパイラの実装としてもこの方針に則っており、Tntel TM ABI に則ったライブラリ(libitm)を差し替えることで実装を切り替えられるようになっています。GCC 4.7 以降も TM 提案を試験的に実装していますが、同様に Intel TM ABI に則ったライブラリ(正確には特に例外周りで変更があるみたいですが)への呼び出しに変換されて実現されます。

さて、では TM 提案 に則ったコードをコンパイラがどのように libitm への呼び出しに変換するのかを見てみましょう。以下は TM ABI の例を一部改変しています。

int s;
[[transaction_safe]] int f(int);
void foo(void)
{
  int i;
  for (i=0;i<10;i++)
  {
    __transaction_atomic {
      s += f(i);
      if (s > 1000) __transaction_cancel;
    }
  }
}

このコードは(例外関係を無視し効率を考えないとして)例えば次のようなコードに変換されます。

int s;
int f(int);
static _ITM_srcLocation start_outer_loc = {…};
static _ITM_srcLocation commit_outer_loc = {…};
static _ITM_srcLocation abort_loc = {…};
void foo(void)
{
  _ITM_transaction * td = _ITM_getTransaction();
  for (i=0;i<10;i++) {
    int doWhat = _ITM_beginTransaction (td,pr_instrumentedCode | &start_outer_loc);
    if (doWhat & a_restoreLiveVariables) {
      /* TM 化していない有効なローカル変数を復元する */
    }
    if (doWhat & a_abortTransaction) goto txn1_abort_label;
    if ((doWhat & a_saveLiveVariables)) {
      /* TM 化しない有効なローカル変数を保存する */
    }
    int sval = (int)_ITM_RU4 (td, (uint32 *)&s);
    sval += f_@TXN(i); // TM 化された関数 f の呼び出し
    _ITM_WaRU4 (td, (uint32 *)&s, (unit32_t)sval);
    if (sval > 1000)
      _ITM_abortTransaction(td,userAbort,&abort_loc);
    _ITM_commitTransaction(td,commit_outer_loc);
    txn1_abort_label:
  }
  return;
}

以下では _ITM_ を省略して記述します。srcLocation 関連はデバッグ情報みたいなもので無視して構いません。"instrumented" という表現は TM 対応化された、くらいの意味に取ればいいと思われます。では、簡単に流れに沿って説明してみましょう。

  • まず最初に getTransaction() で transaction descriptor を取得しています。以下の libitm 関数呼び出しで共通して渡されている情報です。内部に libitm で必要な情報が格納されているわけですが、結局は実質スレッドに紐付け可能なわけで libitm 側で管理すればいいんじゃね?という話はあります。この辺りも簡単に ABI spec 3.8 節に触れられており、また、実際 GCC の場合は td が存在しないコードになります。特に本筋に大きな影響はないので spec の記載通りで書いています。
  • beginTransaction() によって transaction を開始します。これは内部的に setjmp() と同じような処理を含んでおり、commit に失敗した場合や abort された場合に(longjmpと同様の処理が行われ)再びこの関数から戻ってきます。戻り値は次にどのような処理を行うべきか、です。前述の通り abort した場合などもこの関数から戻ってくるためどのような処理をするか戻り値から判別しなければなりません。下表で再実行となっているのは commit に失敗した場合の transaction 再実行です。取り消し不可能云々は本稿では説明しません。さしあたって無視してもらっても大筋は成立します。
    transaction 開始時
    状況戻り値
    直列で取り消し不可能な transaction (serial irrevocable transaction)を開始
    a_runUninstrumentedCode
    transaction 開始a_saveLiveVariables | a_runInstrumentedCode
    transaction 再実行a_restoreLiveVariables | a_runInstrumentedCode
    直列で取り消し不可能な transaction として transaction 再実行(モード変更)a_restoreLiveVariables | a_runUninstrumentedCode
    取り消し不可能な transaction として transaction を開始a_runInstrumentedCode
    transaction 終了時
    状況戻り値
    transaction が aborta_restoreLiveVariables | a_abortTransaction
  • a_restoreLiveVariables と a_saveLiveVariables はローカル変数に対するものです。libitm に渡して TM 化する場合オーバーヘッドがかかるため TM 化する変数アクセスは当然出来るだけ絞りたいわけです。transaction 中であればローカル変数は自分のスレッドからしか有効にアクセスできません。ということでローカル変数について保存・復帰によって対処しようというものがこれらのフラグとそれに対応する処理となります。
  • abort された場合は、a_abortTransaction が返ってくるので(a_restoreLiveVariables によってローカル変数の復帰済み)、以降の transaction 関連コードをスキップします。
  • RU4() だとか WaRU4() が実際に TM 化するためのメモリアクセスの置き換えです。最初の R or W が読み書きの区別、最後が型です(この場合は U4)。途中の aR 等は読み込みの後(after Read)等の意味を持ち、状況に応じて不要な処理を省くといったことを実現するために分けられています。
  • f_@TXN は関数 f() の TM 化バージョンという表記です。実際にはコンパイラによって変わってくるでしょう。transaction 中であるかを判別する inTransaction() という関数もあるのでそれを使って関数内で切り替えることも可能だと思いますが、恐らくはゼロオーバーヘッドを考慮して 2 バージョン用意する形を想定して書かれているのだと思います。
  • abortTransaction() はそのまま transaction の abort で前述のように beginTransaction() の場所に戻ります。
  • commitTransaction() もそのまま transaction の commit です。commit に失敗した場合、前述のように beginTransaction() に戻って transaction が再実行されます。

さて、どうでしょうか? まだ libitm の中まで見ていませんが、begin, abort, commit があって変数アクセスが置き換えられているということから(単一グローバルロックでなくとも)、Transactional Memory が実現できそうかなという感じがするんじゃないでしょうか? part.3 では libitm 実装の一つである RSTM を参考にして TM がどのように実現されているかを簡単に見てみたいと思います。

2012年7月31日火曜日

A bit inside of Transactional Language Constructs for C++ - part.1 Atomic transaction

Boost.勉強会 #10 にて @yohhoy さんが Transactional Language Constructs for C++ (C++ における Transactional Memory 拡張)について発表 されました。丁度自分も提案文書を読んでいるところであり Transactional Memory (以下 TM)というか並列プログラミング全般について知識がないので勉強会駆動の発表ネタになるかなと思っていたところだったので非常にタイムリーでした。発表内容としては現在提案されている TM 拡張の syntax と semantics についての説明で、実装については対象外だったわけですが(もともと提案文書には実装については含まれていない)、その発表の中で

  • (Atomic Transaction で、他の transaction だけでなく)他のスレッドに途中状態を見せないってどう実現するのか分からない

というコメントがありました(多分)。その時は、ピンと来なかったのですが色々調べたりするうちにその感覚が分かってきました。その心は

  • ゼロオーバーヘッドか?(TM 有効にしても実際に TM を使用しなければオーバーヘッドはないか?)

という質問にも通じます。私は TM 拡張は基本的に transaction 内部のコードだけ変更すればいいと考えていたので実行時にはほぼゼロオーバーヘッドだと思っていたのですが、(transaction 外の)他のスレッドにも途中状態を見せないということは transaction 外のコードに対しても何かガードなりを設ける必要があるのではないか?という懸念があった訳です。

が、なんというか「確かに嘘は書いてないんだけどさぁ」という解釈が可能であることに気付きましたので、本稿ではそのことについて書いてみます。

さて、提案文書では Atomic transaction について以下のように書かれています。

In a data-race-free program, an atomic transaction appears to execute atomically; that is, the compound statement appears to execute as a single indivisible operation whose operations do not interleave with the operations of other threads.
データ競合がないプログラムでは、atomic transaction はアトミックに実行される。(atomic transaction として指定された)複文は他のスレッドの操作とインターリーブされない単一の分割不可能な操作として実行される。

さて、ここでどうしても後半に意識がいってしまうわけですが、この文章で最も重要なのは最初の部分 "In a data-race-free program" です(appear であることも多分重要)。

data-race-free とは何かについては TM 提案の最初の方にも簡単に触れられています。C++11 では 1 スレッド内の実行順序について "sequenced before" という関係で順序が定められているものがあります。またスレッド間の実行順序について "synchronized with" という関係で順序が定められているものがあります。これらをもとに "happens before" という関係が定められています(厳密にはもうちょっと複雑)。

  • A is sequenced before B → A happens before B
  • A synchronizes with B → A happens before B
  • A happens before B ∧ B happens before C → A happens before C

そして、あるメモリ領域に対する書き込み操作と、別の読み込み操作あるいは書き込み操作が同じメモリ領域に対して行われている時、これらを conflict と称します。以上を元に data race (データ競合) は、次のように規定されています。

The execution of a program contains a data race if it contains two conflicting 2 operations in different threads, at least one of which is not an atomic operation, and neither happens before the other.
異なるスレッドの 2 つの操作が conflict しており、"happens before" の関係になく、かつ、少なくとも一方は atomic ではない場合、data race が発生している。

要するに、「同一メモリ領域に対する書き込みと、読み込みないし書き込み」(=conflict)について順番が定められていないケースを data-race と呼んでいる訳です。

さて、transaction 間については、ある transaction の終了と別の transaction の開始には "synchronized with" の関係があるとされ、実行がインターリーブしません。従って、transaction 間では data-race は発生しません。では、transaction と transaction 外ではどうなるでしょうか?

atomic transaction はロックや atomic など他の同期機構を含むことができません。このため、transaction 内のコードと transaction 外のコードについて "synchronized with" 関係が発生しません。この状況下で data-race-free、つまり順序不定な conflict が存在しないためには、

  1. 同一スレッド内で sequenced before 関係にあるか、
  2. そもそも conflict が存在しないか、
  3. 別の transaction 内に存在しているか、

のいずれかである必要があります。結果として別スレッドの transaction 外のコードは transaction の途中状態を見ることがありません。この場合、2 しか有り得ず、そもそも transaction が変更するメモリ領域に対するアクセス、conflict が存在しない訳ですから。

つまり、atomic transaction において他のスレッドが transaction の途中状態を見ないというのは atomic transaction によって保証されているというよりは、その前提、data-race-free なプログラムである、というところに依るところが大きいと言えます。data-race-free であることはプログラマが保証してやらねばなりません。一番簡単なのは conflict があるところを transaction で囲むことでしょう。この場合、atomic transaction である必要はありません(transaction 間であれば relaxed transaction でも順序が規定されるので)。

本記事では A bit inside of Transactional Language Constructs for C++ part.1 として TM 提案 での atomic transaction の記述の解釈について書いてみました。心づもりとしては part.2 では TM 提案の対とも言える文書、Intel TM ABI を元にコンパイラがどのように C++ TM を実現しようとするかについての概要、part.3 では Intel TM ABI を実装しているライブラリ RSTM の実装を簡単に覗いてみたいと思っています。

2012年7月15日日曜日

小ネタ: BOOST_CHECK_CLOSE と BOOST_CHECK_CLOSE_FRACTION

Boost.Test は Boost にあるユニットテストフレームワークである。ユニットテストの項目記述用に色々とマクロが定義されているのだが、その中に浮動小数点数比較用のものがある。なぜ浮動小数点数用が別にあるかというと誤差の問題が存在するからで許容範囲を与えるようになっている。

BOOST_CHECK_CLOSE         ( 1.00001e-10, 1.00000e-10, 0.00001 ); // FAIL
BOOST_CHECK_CLOSE_FRACTION( 1.00001e-10, 1.00000e-10, 0.00001 ); // OK

ではこの _FRACTION の有無の違いは何かということでドキュメントを見ると、見ると……。違いが分からなかったという貴方は正しい。なぜならドキュメントが間違っているからだ。間違っていることは #3964 で指摘されており trunk では修正されているのだが release ブランチにマージされていないようだ。ということで、チケットを切ってみた。状況にもよるがチケット切ると割とすぐに対応してもらえたりするので、見つけた問題点はばんばんチケット切ると良いと思う(もちろん重複確認ぐらいはした上で)。

話を戻すと、BOOST_CHECK_CLOSE はパーセンテージ指定、BOOST_CHECK_CLOSE_FRACTION は比率指定、つまり

BOOST_CHECK_CLOSE         ( 1.00001e-10, 1.00000e-10, 0.001 );   // OK
BOOST_CHECK_CLOSE_FRACTION( 1.00001e-10, 1.00000e-10, 0.00001 ); // OK

が同じ挙動になるということである。

ちなみにパーセンテージ、比率ということからも分かる通り、許容範囲は相対指定である。マクロを使う限りにおいては引数それぞれからの相対で両方を満たしていなければならない(これに関するドキュメントもリリースでは古いので trunk から)。

|u − v| / |u| ≤ ε ∧ |u − v| / |v| ≤ ε

つまり以下はいずれも FAIL する。

BOOST_CHECK_CLOSE         ( 0.99999e-10, 1.00000e-10, 0.001 );   // FAIL
BOOST_CHECK_CLOSE_FRACTION( 0.99999e-10, 1.00000e-10, 0.00001 ); // FAIL

片方からだけでも構わないという場合は第 4 引数を FPC_WEAK として直接 check_is_close を使えば良い。

2012年7月2日月曜日

emplace と aggregate

C++11 で rvalue reference による perfect forwarding が実現されたため、STL コンテナに emplace 系の関数が追加されている。insert() や push_back() は value_type 型の値自体を与える必要があるが、emplace 系には生成に必要な引数(コンストラクタの引数等)を渡してやれば良い。

 std::vector<std::pair<int, int>> v1;
 std::pair<int, int> p{ 0, 0 };
 v1.push_back(p);
 v1.push_back({ 0, 0 });
 v1.emplace_back(0, 0);

これで無駄な temporary 作成が無くなり万々歳、なのだが。非常によく似た以下の例は実はコンパイルできない。

 struct point { int x, y; };
 std::vector<point> v2;
 point pt{ 0, 0 };
 v2.push_back(pt);
 v2.push_back({ 0, 0 }); // (g++ 4.5 compilation error
                        // by ambiguous between const value_type & and value_type &&)
 v2.emplace_back(0, 0);  // g++ 4.5-4.8 compilation error
                        // new initializer expression list treated as compound expression

g++ 4.5 特有のエラーについては置いとくとして、下側なんでやねんというのは StackOverflow の質問 ならびに引用されている DR を見てもらえれば良いのだが、問題は emplace 系で呼び出される std::allocator_traits::construct(m, p, args) が最終的に ::new((void *)p) U(std::forward(args)...) となり、list-initialization ではなく direct-initialization になってしまう、という点にある。単純に list-initialization にする、というのは例えば下記のようなコードの挙動を変えてしまうということで、

 std::vector<std::vector<int>> v;
 v.emplace_back(3, 4); // v[0] == {4, 4, 4}, not {3, 4} as in list-initialization

is_constructible<U, Args...> が true かどうか(direct-initialization が有効かどうか)によって、direct-initialization か list-initialization かを呼び分ける方向での修正が提案されている。

こんな単純そうな例ですら落とし穴があるとは、ほんと C++11 難しい。

2012年3月16日金曜日

左シフト演算子と未定義動作

指定したビット数だけ下(LSB)からビットが立ったビットマスクを得るために

(1U << bits) - 1

という式を愛用していたのだがはまってしまった。bits == std::numeric_limits::digits つまり全て 1 のマスクにしたい場合、この式は未定義動作をもたらす。14882:2003 5.8/1 には(右シフトも含めて一般に)こうある。

The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

そして実際に少なくとも x86 上ではまず期待通り(全て 1)にはならない。x86 アセンブリの左シフト命令はシフト数は 5 ビット分だけ有効である。つまり 32 == 100000(2) は 0 ビットシフトと同じになり結果として上の式は 1 - 1 == 0 となってしまう。

左シフトには他にも未定義動作となる場合があるのだがこの記述にも変遷がある。

14882:1998 と 14882:2003 では以下の通りである。つまり undefined behavior という記述がない。E1 が signed な場合はどうなるのが正しいんだよ、という感じである。恐らく未定義動作を意図していない記述だろう。

The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to the power E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise. [Note: the constants ULONG_MAX and UINT_MAX are defined in the header <climits>). ]

一方、14882:2011 (多分。自分の参照文書は n3291 なので違う場合もあり得る)では DR854 によりこうなっている。

The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to the power E2 × 2E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise. [Note: the constants ULONG_MAX and UINT_MAX are defined in the header <climits>). ] one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1×2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

int, long int よりも大きな型も想定した記述となっていること、E1 が signed な場合にも記述が明確となり、負の場合には未定義動作となっている。

そして、既に DR1457 が出ており以下のように修正される予定である。

if E1 has a signed type and non-negative value, and E1 × 2E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

これは、1 << std::numeric_limits::digits のように最大の負数を得るためにビット数-1(=符号ビット分少ないビット数)だけシフト、つまり符号ビットを 1 にするコードを合法にするためである。ただし、これは signed の範囲で表現できない unsigned の値から signed への変換について処理系定義の動作を含む。……しかしだったら signed 全体について全て unsigned にして処理した後 singed に戻すとか規定してしまえばいいじゃないかとも思う。

なお、右シフトについては実質的に記述は変わっておらず(文による表現が式による表現になっただけ)、E1 が負数の場合は処理系定義となっている(以下は n3291 より)。

The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

2012年3月14日水曜日

図解 MPL Metafunctions

Boost ライブラリの中でも Boost.MPL は割と食わず嫌いというかなんとなく敬遠している人も多いライブラリのような気がする。MPL = Meta Programming Library ということで「メタプログラミング?黒魔術?」みたいな受け取り方をされているんじゃないかというか、実際には

という言にふさわしい、コンパイルタイムメタプログラミングを Sequence、Iterator、Algorithm といったランタイム(実行時:コンパイルタイムの対義語として)の語彙で取り扱えるようにする一般人のためのライブラリである。typename ::type 乱舞になりがちなところと、代入や状態の変更ができず関数型言語的に記述する必要があるところだけ気をつければ難しくない。のだがちょっと自分の中で整理しきれていなかったのが Metafunction 関係である。前回 MPL 用再帰的 equal を書く中で大分整理できたのでまとめてみる。

MPL の Metafunction 関係について包含図を書いてみると以下のようになる。

MPL Metafunctions

Metafunction がランタイム世界での通常の関数にあたる。適用が ::type しないといけないところがちょっと面倒なところだ。Metafunction 以外の Lambda Expression は高階関数にあたるところであり Metafunction Class と Placeholder Expression からなる。Metafunction Class は関数オブジェクト(Functor)にあたると思えばよい。operator() の代わりにメンバテンプレート apply があると考えても良いだろう。さて、ランタイムにおける世界でも毎回毎回関数オブジェクトを書くのは面倒ということで Boost.Lambda や C++11 でのラムダ式がある。これの MPL 版にあたるのが Placeholder Expression だ。良く分からない英語が書いてあるが、placeholder(boost::mpl::_1 等)自身や、テンプレートパラメータのどこかに placeholder ないし Placeholder Expression を含むテンプレートクラスの特殊化(specialization)である。

_1
plus<_, int_<2> >
if_< less<_1, int_<7> >, plus<_1,_2>, _1 >

最後が bind expression である。これは単に bind の特殊化だ。bind はメンバテンプレート apply を持つため必ず Metafunction Class となるが、必ずしも Placeholder Expression とはならない。placeholder なしで bind することも可能だからだ。そのため Placeholder Expression から一部はみ出している。

bind< times<>, int_<2>, int_<2> >

さて、なんとなく Metafunction 族については分かっただろうか。自分もここまでは大体分かっていたのだがそれに作用するもの、具体的に主要なものをあげると apply, lambda, apply_wrap, protect, quote 辺りについて整理ができていなかったので以下に並べてみる。以下の図で青色が引数に取る対象、桃色がある場合はその部分が実際に変換される対象である。

MPL apply

apply は Lambda Expression を引数に取り、その Lambda Expression を適用する(呼び出す)。実際には lambda を適用した後で apply_wrap を呼び出す。では、その lambda と apply_wrap がどうなっているかというと、

MPL lambda

lambda は任意の型を引数に取るが、その内 Placeholder Expression を Metafunction Class に変換する。他はそのままである。

MPL apply_wrap

そして、apply_wrap は Metafunction Class の呼び出しである。実際には ::apply<...> と同等だ。なので、apply は lambda により全て Metafunction Class に変換した後、apply_wrap で呼び出すことになる。

MPL protect

protect は Metafunction Class を受け取るが bind expression しか変換しない。リファレンスマニュアルの例だが以下のように bind 時の placeholder の置き換えを抑止する。protect なしだと入れ子の bind 中の _1, _2 まで置き換えられているが、protect をかけると置き換えされない。

struct f
{
    template< typename T1, typename T2 > struct apply
    {
        typedef T2 type;
    };
};

typedef bind< quote3<if_>,_1,_2,bind<f,_1,_2> > b1;
typedef bind< quote3<if_>,_1,_2,protect< bind<f,_1,_2> > > b2;

typedef apply_wrap2< b1,false_,char >::type r1;
typedef apply_wrap2< b2,false_,char >::type r2;

BOOST_MPL_ASSERT(( is_same<r1,char> ));
BOOST_MPL_ASSERT(( is_same<r2,protect< bind<f,_1,_2> > > ));

MPL quote

最後に上の protect の例でも使われていた quote である。これは Metafunction を Metafunction Class に変換する。引数の数を指定する必要があり、その際デフォルトパラメータの部分も数えなければならないし、変換された Metafunction Class には全引数を渡してやらなくてはならない。bind 等と併用するくらいなら Placeholder Expression + lambda の方が楽かもしれない。

まとめ

どうだろうか。少しでも理解の助けになっただろうか?現実的には以下のルールに従っていれば大体問題ないと思われる。

  • 高階関数を受け取る場合は Lambda Expression を受け取ることにする
    • 適用(呼び出し)する場合は apply を使う
    • 高階関数として「そのまま」渡したい場合は lambda をかける(protect をかけた状態になる。実際 lambda は Lambda Expression に対しては protect<bind<...> > になる)
  • 高階関数として Metafunction を渡したい場合は quote をかける

2012年3月12日月曜日

Boost.MPL 用再帰的 equal

Boost.MPL の Sequence はその特性上 is_same を使いにくい。例えば

BOOST_MPL_ASSERT((
 boost::is_same<
  boost::mpl::push_front<
   list<>,
   int_<1>
  >::type,
  list<int_<1> >
 >));

は通らない。push_front した結果は list ではなくなっているからだ。このため Boost.MPL には equal というアルゴリズムが用意されている。

BOOST_MPL_ASSERT((
 boost::mpl::equal<
  boost::mpl::push_front<
   list<>,
   int_<1>
  >::type,
  list<int_<1> >
 >));

equal は Sequence の種類を気にせずその「要素」が一致しているかを判別するためこれは通る。通るのだが、equal は最上位の Sequence だけしか考慮してくれないため多次元の Sequence だとうまくいかない。equal の第 3 引数は要素を比較する際の Predicate であるため次元に合わせて equal を渡してやればいいのだが割と面倒である。

// bind base
BOOST_MPL_ASSERT((
 boost::mpl::equal<
  vector<vector<int_<1> > >,
  list<list<int_<1> > >,
  boost::mpl::bind<
   boost::mpl::quote3<boost::mpl::equal>,
   boost::mpl::_1,
   boost::mpl::_2,
   boost::mpl::protect<
    boost::mpl::bind<
     boost::mpl::quote2<boost::is_same>,
     boost::mpl::_1,
     boost::mpl::_2
    >
   >
  >
 >));
// lambda base
BOOST_MPL_ASSERT((
 boost::mpl::equal<
  vector<vector<int_<1> > >,
  list<list<int_<1> > >,
  boost::mpl::lambda<
   boost::mpl::equal<
    boost::mpl::_1,
    boost::mpl::_2,
    boost::mpl::lambda<
     boost::is_same<
      boost::mpl::_1,
      boost::mpl::_2
     >
    >::type
   >
  >::type
 >));

やってることは同じである。というか bind base の方は実質 lambda を展開した結果になっている。二次元でこれだとそれ以上だと絶望しそうだ。ということで再帰的な equal を書いてみた。

template<typename Arg1, typename Arg2, typename Pred = boost::is_same<boost::mpl::_1, boost::mpl::_2> >
struct equal_deep
{
 typedef typename boost::mpl::eval_if<
  boost::mpl::and_<boost::mpl::is_sequence<Arg1>, boost::mpl::is_sequence<Arg2> >,
  boost::mpl::equal<Arg1, Arg2, equal_deep<boost::mpl::_1, boost::mpl::_2, typename boost::mpl::lambda<Pred>::type> >,
  boost::mpl::eval_if<
   boost::mpl::or_<boost::mpl::is_sequence<Arg1>, boost::mpl::is_sequence<Arg2> >,
   boost::mpl::false_,
   boost::mpl::apply<Pred, Arg1, Arg2>
  >
 >::type type;
};
BOOST_MPL_ASSERT((
 equal_deep<
  vector<vector<int_<1> > >,
  list<list<int_<1> > >,
 >));

やっていることはそれほど難しくない。引数が両方 Sequence である時には equal に対して自分自身(equal_deep)を渡して再帰し、両方が Sequence でない時には渡された Predicate を呼び出す。自分が MPL Metafunction 関係をちゃんと把握していなかったので lambda かけるところと apply で迷ったぐらいである。7 行目の eval_if は if_ だと is_same の場合は大丈夫だが Sequence に対して呼び出せない Predicate (equal_to 等) を渡した場合にコンパイルエラーになるため eval_if でなければならない。また、nullary Metafunction を受け付ける部分は typename ::type を付けずに不要なインスタンス化を避けている。

これを書く際にせっかくなので一度 MPL Metafunction 系について整理してみたのだが以下次号。

2012年2月18日土曜日

Susie プラグインと GPL

axpdf--.spi という似非(まともにレンダリングせず画像データだけ抽出する) PDF プラグインを作成、公開しているのですが、公開ページにも書いている通りライセンス的に問題のない PDF Susie プラグインを作成したい、というのが目的の一つでもありました。私は一個人プログラマであって法的なところで確実なことは言えないわけですがちょっと書いてみます。

PDF は仕様が公開されているためオープンソースのレンダラも存在しています。最も有名なのは Ghostscript でしょうか。MuPDF なんてのもあるようですね。しかし、これらのコードを内部で使って Susie プラグインを作成、公開する、という方法には問題があります。これらのコードは GPL でライセンスされているためプラグイン自体も GPL で公開することになります。GPL での派生著作物がどの範囲にあたるのか、は議論の余地があり最終的には法廷で決着が付けられるべきところですが、とりあえず FSF の主張ないし期待するところを正とします。すると動的リンクされるプラグインが GPL でライセンスされている場合、本体側のプログラムも GPL でライセンスされていなければなりません(cf. GPL FAQ Can I apply the GPL when writing a plug-in for a non-free program? フリーではないプログラム向けのプラグインにGPLを適用することはできますか?)。Susie プラグインに対応したソフトで GPL でライセンスされているソフトというのはそう多くないはずです(自分は知りません)。つまり多くの場合でライセンス的に問題のない状態で使用できないことになってしまいます。FAQ のこの項では「フリーではないメインプログラムとのリンクを許可する例外条項」(cf. GPL FAQ What legal issues come up if I use GPL-incompatible libraries with GPL software? フリーではないライブラリを利用するフリーソフトウェアを書いているのですが、GPLを適用した場合どのような法的問題が発生するでしょうか?)の記述があるのですが、この例外条項を付与できるのは著作権者のみです。つまり使用しようとしている「GPL でライセンスされたライブラリ」の著作権者全てに許諾を得る必要があります。これはちょっと望み薄でしょう。

さて、ここまでは以前からそう思っていたことで、ここからはちょっと考えが整理できたかな、と思っていることです。やはり駄目そうです。コメントを参照ください。(2003/01/19) GPL な Susie プラグインを真っ当に使ってもらうためには例外条項がいるとして、では例外条項なしの GPL でライセンスされた Susie プラグインが、GPL でライセンスされていないビューワのもとで使用された場合、その責は誰が負うべきでしょうか。行為としてはビューワの使用者のものなのですが、一方で GPL はソフトウェアの使用に制限を課さないライセンスだという記述もあり、でも GPL の意図上使用者が自由に使えて良いわけはないし、かといって GPL なビューワとの使用なら問題ないんだから GPL な Susie プラグインを公開できないというのも変な話です。これについては GPL による制限が課されているのは使用の前の「動的リンク」であると考えることで GPL 違反をしているのは使用者である、と納得することができました。つまり例外条項なしの GPL でライセンスされた Susie プラグインを公開すること自体は問題なく、GPL でライセンスされていないビューワのもとで使用しないようにするのは使用者の責任であることになります。配布しないなら GPL に違反しないです。(2003/01/19) ただし、プラグイン作者は GPL でライセンスされていることを明示した上で(これは GPL で要求されています)、個人的には GPL でライセンスされていないビューワのもとで動作させてはならないとも明示的に警告するべきではないかとも思います、道義的に。より個人的には、例外条項を付けるか、付けられないならそもそも公開するべきではないとも思いますが。

2012年1月15日日曜日

Windows 上での Boost.Interprocess の named_mutex の挙動

自分が改造して公開している ax7z_s.spi のα版では(必要もないのですが) Boost.Interprocess をほんの一部だけ使用しています。その中でちょっと想定外の挙動があったのでメモしてみます。使用しているのは named_mutex です。Windows 上だと Mutex に対するラッパになっている……と思っていたのですが実はそうなっていません(少なくとも 1.48 までは)。共有メモリを使ってエミュレーションされています。では、それがどのような違いを生むのか簡単に見てみましょう。まずは Win32 API 版。

Locker by Win32 API

#include <windows.h>
#include <iostream>

int main(void)
{
 HANDLE hMutex = CreateMutex(0, TRUE, "cx.myhome.yak.test"); // Initial owner
 char c; std::cin >> std::noskipws >> c;
 CloseHandle(hMutex);
 return 0;
}

Waiter by Win32 API

#include <windows.h>
#include <iostream>

int main(void)
{
 HANDLE hMutex = CreateMutex(0, FALSE, "cx.myhome.yak.test");
 char c; std::cin >> std::noskipws >> c;
 DWORD dwResult = WaitForSingleObject(hMutex, INFINITE);
 std::cout << dwResult << std::endl;
 ReleaseMutex(hMutex);
 CloseHandle(hMutex);
 return 0;
}

Locker 起動→Waiter 起動→Locker に ENTER 入力→Waiter で ENTER 入力、した場合の挙動は次の図のようになります。

Locker が Mutex を獲得したまま終了しますが、この時点で Wait している Waiter 側には WAIT_ABANDONED(256) が返ってきます。Mutex を獲得していたプロセスが死んだことを通知するための値ですが、WAIT_OBJECT_0(0) が返ってきたかのように無視すればそのまま動作します。一方、Locker 起動→Locker に ENTER 入力→Waiter 起動→Waiter で ENTER 入力、した場合の挙動は次の図のようになります。

こちらでも Locker が Mutex を獲得したまま終了しますが、この時点で Mutex に対するハンドルがないので Mutex オブジェクトが消滅します(多分)。結果、Locker を起動した際には何事もなく WAIT_OBJECT_0(0) が返ってきます。

いずれにしろ、Locker 側が Mutex を獲得したまま終了しても、Waiter 側は問題なく実行できる、というところがポイントです。

それでは Boost Interprocess を使った場合はどうなるでしょうか?

Locker by Boost.Interprocess

#include <boost/interprocess/sync/named_mutex.hpp>
#include <iostream>

int main()
{
 using namespace boost::interprocess;
 named_mutex mutex(open_or_create, "cx.myhome.yak.test");
 mutex.lock();
 char c; std::cin >> std::noskipws >> c;
 return 0;
}

Waiter by Boost.Interprocess

#include <boost/interprocess/sync/named_mutex.hpp>
#include <iostream>

int main()
{
 using namespace boost::interprocess;
 named_mutex mutex(open_or_create, "cx.myhome.yak.test");
 char c; std::cin >> std::noskipws >> c;
 mutex.lock();
 mutex.unlock();
 return 0;
}

Locker 起動→Waiter 起動→Locker に ENTER 入力→Waiter で ENTER 入力、した場合の挙動は次の図のようになります。

Locker が Mutex を獲得したまま終了しますが、Win32 API の場合と異なり獲得された状態のまま残ってしまいます。そのため、Locker はデッドロックします。ちゃんと解放するように組めばいい、と思われるかもしれませんが、強制終了させた場合なんかもデッドロックしてしまうため結構厳しいです。Locker 起動→Locker に ENTER 入力→Waiter 起動→Waiter で ENTER 入力、した場合の挙動も次のようになります。

こちらの場合でも Mutex は獲得された状態のまま残ってしまい、Locker がデッドロックします。

どうしてこうなるか、というのは named_mutex の実装に由来します。上では共有メモリを使っていると書きましたが正確にはファイルマッピングを使っています。名前との対応関係を容易にするためでしょう実際にファイルと結びつけられたものです。c:\ProgramData あるいは c:\Documents and Settings\All Users\Application Data フォルダ以下に boost_interprocess というフォルダが作成され、さらにその下に 20120102003353.109999 のような名前のフォルダが起動時刻を元に作成されます。この下に指定された名前(上の例の場合なら cx.myhome.yak.test)のファイルができます。これが Mutex の実体です。特に9~12バイト目の部分が Mutex の状態を表しており、1 なら獲得状態、0なら非獲得状態です。このファイルが獲得状態のまま残り続けるためずっとデッドロックすることになります。もちろんこのファイルを削除してから起動してやればロックからは脱出できます。また、再起動後に Waiter 等を実行すると起動時刻を元に作成するフォルダが再作成され古いフォルダは削除されるのでロック状態からは脱出できるようになっています。つまり Boost.Interprocess のデータは破棄しない限り再起動するまでの間有効ということです。

さて、最後にもう一つ。Boost.Interprocess の named_mutex の例の項では remover というものがあります。大抵の C++er は「デストラクタで始末すればいいのになんで別に始末するためのものを用意する必要があるんだろう?」と思われるのではないでしょうか。理由は恐らく「共有されている named_mutex の実体」を削除するタイミングは named_mutex 各オブジェクトからは分からないためだと思われます。デストラクタで行っている理由は例外送出時の対応と、順序(named_mutex オブジェクト破棄後に remove)のため……だと思ったのですが、実は順序は named_mutex 破棄後に remove でなくとも動作します。

#include <boost/interprocess/sync/named_mutex.hpp>
#include <iostream>

int main()
{
 using namespace boost::interprocess;
 named_mutex mutex(open_or_create, "cx.myhome.yak.test");
 mutex.lock();
 char c; std::cin >> std::noskipws >> c;
 named_mutex::remove("cx.myhome.yak.test");
 std::cin >> std::noskipws >> c;
 return 0;
}

上のコードを実行し、boost_interprocess フォルダの中を覗いてみると cx.myhome.yak.test という名前のファイルが出来ておりラスト 4 byte は 1 になっているはずです。 1 回 ENTER を打った後だと named_mutex オブジェクトが存在する状態で remove していることなりますが、cx.myhome.yak.test はなくなり、60FEE8D7B3C8CC018964BC3FCED2CC01 みたいな謎のファイル名に変わっているはずです。これは削除準備状態でこのファイル自体を開くことはできません。元ファイルを参照しているハンドルが閉じられた場合(この場合 named_mutex が破棄された場合)削除されます。ちなみにこの削除準備状態で Waiter を実行して ENTER を打つと cx.myhome.yak.test は存在しないためデッドロックせず問題なく終了します。この後、再度 ENTER を打つと named_mutex が破棄され削除準備状態だったファイルが削除されます。逆に言えば remove は問答無用で実体を削除してしまうため使うタイミングは良く考えるべきだと言えると思います。

さて、長々書いてきましたが、どうやらこれ、POSIX の場合に使用される POSIX semaphore の挙動と一致しているようです。そしてプロセスが死ぬようなケースでは POSIX semaphore を使わず OS が勝手に解放してくれるファイルロック等を使え、ということのようです。参考 URL: