失敗ロック例いくつか

なにかあまりスレッドとか得意でない人のコードを見ていて、いくつかダメな予感がするパターンがあるよね、ってことで適当に集めてみました。どれもこれも小さな例にすると、こんなミスしねーよ、って感じなんですけど、複雑なコードの中にあると結構ミスるもんかな、と。私自身マルチスレッドはたいへん苦手で、実際私がやらかしたケースもいくつか。

ひとつめ: ロック順序逆転

// そこらじゅうで確保されてるグローバルなロック
pthread_mutex_t g_mu = PTHREAD_MUTEX_INITIALIZER;

// このクラスを使うところは全域 g_mu でロックされてるとします
class C {
public:
  C() {
    pthread_mutex_init(&mu_, NULL);
  }
  void doSlowOperation() {
    pthread_mutex_lock(&mu_);
    // この処理は重いから先にロックを解放しておこう!
    pthread_mutex_unlock(&g_mu);
    // Slow operation.
    pthread_mutex_lock(&g_mu);
    pthread_mutex_unlock(&mu_);
  }
private:
  pthread_mutex_t mu_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock1.cc

このコードは thread A が出口付近で g_mu を取ろうとする時に、他のスレッドが入口付近で mu_ を確保しにいくと、デッドロックします。

教訓としては、複数ロックがネストする時はとりあえずデッドロックを心配すると良い気がします。ネストする場合は、二つのロックを取る順序は必ず同じ順序で取るようにするべき。ロック1とロック2がある時に、ロック1,2両方取られている時間と、ロック1だけが取られている時間と、ロック2だけが取られている時間があると、まぁだいたいやばいです。

まぁ、この場合は本当に g_mu を外さにゃいかんのかをまず考えた方がいい気がします。あちこちで確保されてるロックが一つだけ、って状態は性能に問題が出るまでは割と安心な状態です。

ふたつめ: 同じ変数に別のロックを使う

// そこらじゅうで確保されてるグローバルなロック
pthread_mutex_t g_mu = PTHREAD_MUTEX_INITIALIZER;

// このクラスを使うところは全域 g_mu でロックされてるとします
public:
  C() {
    pthread_mutex_init(&mu_, NULL);
  }
  void doSlowOperation() {
    // この処理は重いから先にロックを解放しておこう
    // ひとつめではデッドロックしてしまったから先に外しておく
    pthread_mutex_unlock(&g_mu);
    pthread_mutex_lock(&mu_);
    for (int i = 0; i < 5; i++)
      vals_.push_back(i);
    pthread_mutex_unlock(&mu_);
    pthread_mutex_lock(&g_mu);
  }
  void doFastOperation() {
    // g_mu が取られてるから大丈夫!
    vals_.push_back(42);
  }
private:
  pthread_mutex_t mu_;
  std::vector<int> vals_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock2.cc

doSlowOperation を見る限り、 vals_ は mu_ で守られてるべきっぽいですが、 doFastOperation では g_mu に頼ってます。普通に race condition があるので、この場合普通にクラッシュしました。

教訓としては、なにかロックしてるから大丈夫、ではなくて、適切なロックを使ってるかどうかを常に意識すると良いです。どのロックに守られてるか、ってのは C++ の所有権並に重要なことだと思うんで、 mutex をメンバに持たせる時は、その mutex がどの変数をガードするかどうかをコメントするようにするとやや良い気がします。

みっつめ: ロック順序逆転してない?

class C {
public:
  explicit C(int val) : val_(val) {
    pthread_mutex_init(&mu_, NULL);
  }
  int add(C* c) {
    // 必ず mu_ => c->mu_ の順序でロックするよ!
    pthread_mutex_lock(&mu_);
    pthread_mutex_lock(&c->mu_);
    int r = val_ + c->val_;
    pthread_mutex_unlock(&c->mu_);
    pthread_mutex_unlock(&mu_);
    return r;
  }
private:
  pthread_mutex_t mu_;
  int val_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock3.cc

C::add はぱっと見首尾一貫した順序を守ってるように見えるんですが、 this と引数 c が逆転すればひとつめの例と同じで、ロック順序が逆転しているのでデッドロックします。

具体的には、 c1->add(c2) と c2->add(c1) があったとして、前者が c1 のロックを取る→後者が c2 のロックを取る、という順序で起きると次のロックはどちらも取れません。

これはこのクラスの使い方によっては、問題無い場合もあります。必ず一定の法則に従って add のレシーバと引数を選んでいれば大丈夫で、たぶん、

assert(c1 != c2);
c1 < c2 ? c1->add(c2) : c2->add(c1);

とかしていれば大丈夫…な気がします。自信がないですが。

がまぁ素直になんとかした方がいいと思います。パフォーマンスに問題が無ければ mu_ を static にしてしまうのがラクチンです。

よっつめ: 狭義のレースは無いのだけど

class C {
public:
  explicit C() {
    pthread_mutex_init(&mu_, NULL);
  }
  void setVals(std::vector<int> vals) {
    pthread_mutex_lock(&mu_);
    vals_ = vals;
    pthread_mutex_unlock(&mu_);
    // Update the cache.
    setSum(calcSum());
  }
  int getSum() {
    pthread_mutex_lock(&mu_);
    int sum = sum_;
    pthread_mutex_unlock(&mu_);
    return sum;
  }
  void setSum(int sum) {
    pthread_mutex_lock(&mu_);
    sum_ = sum;
    pthread_mutex_unlock(&mu_);
  }
  void check() {
    pthread_mutex_lock(&mu_);
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    assert(sum == sum_);
    pthread_mutex_unlock(&mu_);
  }
private:
  int calcSum() {
    pthread_mutex_lock(&mu_);
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    pthread_mutex_unlock(&mu_);
    return sum;
  }
  pthread_mutex_t mu_;
  std::vector<int> vals_;
  int sum_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock4.cc

vector を持っていて、その合計値がよく欲しくなるので、合計値をキャッシュとして持っておく、というような想定で書かれたコードです。ロックが一つしか無くて、 vals_ も sum_ も mu_ にしっかりガードされてるので安心…ではないです。

たしかに vals_ や sum_ に同時アクセスするケースは無いのですが、 sum_ が vals_ の合計でない値になってしまう場合があります。というのは setVals が calcSum や setSum でいちいちロックを外してしまっているので、例えば、 calcSum が 30 という結果を返す→ setVals が別スレッドで呼ばれて sum_ が 50 にアップデートされる→元のスレッドに戻って sum_ に 30 を代入する、のような。

この手のレースはなんと呼ぶのか知らないのですが、一つの変数へのアクセスはちゃんとガードされてるので、 thread sanitizer なんかの race detector にかからず、 annotation をしっかり書いても見つけてくれないはずです。 QuickCheck なんかがこういうのを探してくれる、って話だったような。

この手の、メンバ変数 A が○○なら B は必ずこれを満たさなければならない…みたいな条件があるクラスはマルチスレッドでなくてもあまり嬉しくないですね。パフォーマンスに問題なければそもそもキャッシュしたくないわけですが、まぁこの例ではパフォーマンスに問題があったから calcSum を private に移してキャッシュすることにしたんだなぁ、という流れが透けて見える感じです。 check みたいな関数を用意してやたら呼びまくるのは安心感があっていい方法ではあると思います。

ちなみに修正例:

class C {
public:
  explicit C() : sum_(0) {
    pthread_mutex_init(&mu_, NULL);
  }
  void setVals(std::vector<int> vals) {
    pthread_mutex_lock(&mu_);
    vals_ = vals;
    // Update the cache.
    sum_ = calcSumLocked();
    pthread_mutex_unlock(&mu_);
  }
  int getSum() {
    pthread_mutex_lock(&mu_);
    int sum = sum_;
    pthread_mutex_unlock(&mu_);
    return sum;
  }
  void check() {
    pthread_mutex_lock(&mu_);
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    assert(sum == sum_);
    pthread_mutex_unlock(&mu_);
  }
private:
  int calcSumLocked() {
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    return sum;
  }
  pthread_mutex_t mu_;
  std::vector<int> vals_;
  int sum_;
};

こういう hogehogeLocked みたいなのは、こういうクラスだとよく必要になる気がします。

いつつめ: rwlock

最後ふたつは mutex よりは使用頻度が低いもので。

class C {
public:
  C() : val_(3) {
    pthread_rwlockattr_t attr;
    pthread_rwlockattr_init(&attr);
    pthread_rwlockattr_setkind_np(
        &attr, PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
    pthread_rwlock_init(&mu_, &attr);
    pthread_rwlockattr_destroy(&attr);
  }
  int calcSomething() {
    pthread_rwlock_rdlock(&mu_);
    // getVal の中で同じロックを取るけど、 reader lock だから大丈夫!
    int r = 42 + getVal();
    pthread_rwlock_unlock(&mu_);
    return r;
  }
  int getVal() {
    pthread_rwlock_rdlock(&mu_);
    int r = val_;
    pthread_rwlock_unlock(&mu_);
    return r;
  }
  void setVal(int val) {
    pthread_rwlock_wrlock(&mu_);
    val_ = val;
    pthread_rwlock_unlock(&mu_);
  }
private:
  pthread_rwlock_t mu_;
  int val_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock5.cc

以前書いた話 です。 calcSomething の中でヘルパ関数 getVal を呼んでいるのは、 glibc のデフォルトの pthread_rwlock_t なら大丈夫なんですが、この場合 writer starvation を回避する rwlockattr をつけてるのでデッドロックしてしまいます。また、 pthread の実装によってはデフォルトのでデッドロックするそうです。

writer starvation とは、 reader がたくさんいて、一つのロックに常に複数の reader lock を reader が取ってしまっていて、全然 writer がロックを取れない状況を言うそうです。これを回避するために、 writer が待ってる時は新規 reader を受け付けない、という処置がされているロックがあって、まぁこれつけないとパフォーマンス上使いものにならんケースが多いようです。

ただ、このタイプの rwlock を使うと、 thread 1 が calcSomething の reader lock を取る→ thread 2 が setVal の writer lock を待ちはじめる→ thread 1 が getVal の reader lock を取ろうとするが、 writer が待ってるので取れない、という形のデッドロックになります。

教訓としては必要がなければ rwlock をそもそも使わない、ってのがあるかと思います。あとまぁ普通に reader lock だろうと nest させてると良くないなっていう。普通のロックに変えれませんし。

あと

condition variable のダメケースを作ろうかと思ったんですけど、あんま短くていい感じのが作れなかったので省略。一般に lock の外で cond_signal すると cond_wait で拾えないケースがある…ってやつが短く書けない。順序によっては普通に大丈夫なんですよね…

あと別解

存在を忘れかけてたんですけど、 Haskell, Falcon, Lua を消して Scheme, Clojure, Common Lisp を足そうとしたバージョンがあったんですが、 ideone の Scheme が Gauche じゃなくて Guile だったので萎えたバージョン:

http://shinh.skr.jp/obf/polyadd2.txt

こっちの方向性で assembly を加えて 13 にする予定だったんですけど、挫折しました。

polyglot addition

https://codeiq.jp/ace/cielavenir/q816

を見ておお面白い問題だーと思って、がんばったのはいいんですが、提出忘れてたぽいんで、勝手に上げておいておきます。

Ruby / Bash / Python / Perl6 / Perl / Haskell / Brainfuck / Whitespace / Groovy / Falcon / JavaScript (spidermonkey) / Lua の 12 言語で加算するプログラムです。

http://shinh.skr.jp/obf/polyadd.txt

まー polyglot ってのは前回の文字重複禁止に比べれば簡単なではあるんですよね。

あと今回はわかりやすい(?) 解説サイトを作りました! 左右か hl で操作してください。

http://shinh.skr.jp/obf/polyadd.html

hello, world * 6

https://codeiq.jp/ace/nabetani_takenori/q766

を見て、おおこれは面白い問題だーと思ってチャレンジしました。とはいえ 3 言語で重複無しとか、文字種制限経験者には楽勝なんで、 6 言語になりました。第一感では 5 言語くらいはいけるだろーと思って、後で Forth が追加できたんで 6 になったっていう。

Groovy 953B 文字種6 "$-o{}

"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"{"}"}"}"}"}"}"}"}"}"}"}${--"${--"${--"${--"${--"${--"${--"${--"${--"{"}"}"}"}"}"}"}"}"}${--"${--"${--"${--"${--"${--"o"}"}"}"}"}"}${--"o"}${--"${--"${--"${--"${--"${--"${--"{"}"}"}"}"}"}"}""${--"${--"${--"${--"${--"${--"${--"o"}"}"}"}"}"}"}${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"o"}"}"}"}"}"}"}"}"}"}${--"${--"${--"o"}"}"}${--"${--"${--"o"}"}"}o${--"-"}${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"-"}"}"}"}"}"}"}"}"}"}"}"}"}${--"${--"${--"${--"{"}"}"}"}o${--"${--"${--"${--"${--"${--"${--"${--"${--"{"}"}"}"}"}"}"}"}"}${--"${--"${--"o"}"}"}${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"o"}"}"}"}"}"}"}"}"}"}"}${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"${--"-"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"}"

JavaScript(spidermonkey) 971B 文字種11 !'()+;=[\]_

_=!'';__=_+_+_;___=(''+''['']);([][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]][(''+[][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]])[__]+(_+[][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]])[+_+[+'']]+___[+_]+(''+!_)[__]+(''+_)[+'']+(''+_)[+_]+___[+'']+(''+[][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]])[__]+(''+_)[+'']+(_+[][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]])[+_+[+'']]+(''+_)[+_]]((''+_)[__]+('!'+[][(''+!_)[+'']+___[__+_+_]+(''+!_)[_+_]+(''+_)[+'']+(''+_)[__]+(''+_)[+_]])[__+[+'']]+([]+!_)[+_]+([]+!_)[_+_]+'(\'\\'+(+_)+(__+__)+(+'')+(''+_)[+_]+___[__+_+_]+___[+_]+(''+_)[+'']+'(\\\'\\'+(+_)+(__+_+_)+(+'')+(''+_)[__]+(''+!_)[_+_]+(''+!_)[_+_]+'\\'+(+_)+(__+_+_)+(__+__+_)+'\\'+(__+_+_)+(__+_)+'\\'+(__+_)+(+'')+'\\'+(+_)+(__+__)+(__+__+_)+'\\'+(+_)+(__+_+_)+(__+__+_)+(''+_)[+_]+(''+!_)[_+_]+___[_+_]+'\\\')\')'))()

Perl 80B 文字種14 #:@ACFHMW^emqs

s##qq@RRRRR:RRRRQWRRQRRRq:@^qq@qqemq^mqSSSAHmSqSe:^@^qq@SQ^QWFWFmmm::HmQmSAF@#ee

Ruby 123B 文字種12 %0678<inprt (空白も)

print %%%<<770%666<<707%606<<708%600<<708%600<<777%666<<660%77<<700%668<<786%667<<777%666<<780%666<<708%600<<700%600<<70%60

Bash 773B 文字種15 \t&/12>Pacdklwz|

dc	czzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPzzzzzzzzPzPzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzPczzzzzzzzzzzP	2>&1	|	dc	2>&1	|	awk	/ll/

Forth 208B 文字種11 \n3459DEIMOT

439
335
MOD
EMIT
434
333
MOD
EMIT
443
335
MOD
EMIT
443
335
MOD
EMIT
444
333
MOD
EMIT
44
EMIT
333
43
MOD
EMIT
453
334
MOD
EMIT
444
333
MOD
EMIT
449
335
MOD
EMIT
443
335
MOD
EMIT
433
333
MOD
EMIT
43
33
MOD
EMIT

まとめ

提出物はここに置いておきました。 readme とかも入ってます。

http://shinh.skr.jp/obf/hello6.zip

70種の文字を使ったようです。

\t\n !\"\#$%&'()+-/0123456789:;<=>@ADEFHIMOPQRSTW[\\]^_acdeiklmnopqrstwz{|}

言語セットが違えば7言語とか見えるかもしれませんけど、このセットだとなかなかむつかしいなーという印象でした、が、できても不思議ではないとも思います。

何が楽しいって、どの言語をどういうふうに使うか、ってことですね。ていうか 私の場合比較的よくわかってる Perl, Ruby, Bash あたりに負担がかかってくるわけですが…

あと地味にかけられてる 1000B 制限が微妙に厳しくてですね…

robust_quine.pl

Ruby にできて Perl にできないことは無いという格言があります。

http://d.hatena.ne.jp/ku-ma-me/20140219/p1

$$qq.=q';printf"\$\$qq.=q%c%s%c;;##%c;\n\$\$uu.=q%c%s%c;;##%c;\n\n\$\$ii||=%c\$_;;\$\$\$ii.=\$\$qq;;s#^;.{217}\$#\$\$qq#ee;;#;#^^;\n\$\$nn||=%c\$_;;\$\$\$nn.=\$\$uu;;s#;.{217}\$#\$\$uu#ee;#;",39,$&,39,39,39,$&,39,39,92,92;exit';;##';
$$uu.=q';printf"\$\$qq.=q%c%s%c;;##%c;\n\$\$uu.=q%c%s%c;;##%c;\n\n\$\$ii||=%c\$_;;\$\$\$ii.=\$\$qq;;s#^;.{217}\$#\$\$qq#ee;;#;#^^;\n\$\$nn||=%c\$_;;\$\$\$nn.=\$\$uu;;s#;.{217}\$#\$\$uu#ee;#;",39,$&,39,39,39,$&,39,39,92,92;exit';;##';

$$ii||=\$_;;$$$ii.=$$qq;;s#^;.{217}$#$$qq#ee;;#;#^^;
$$nn||=\$_;;$$$nn.=$$uu;;s#;.{217}$#$$uu#ee;#;

まぁ Perl はだいぶラクですな…

mingn

MinGW 的な、ミニマルな GCC 開発環境を NaCl 上で動かしたいなってことで冬休みくらいから遊んでた (gcc のポート自体は一昨年からあったが…) ものをちまちま naclports という NaCl に移植したアプリ集みたいなところにコミットして、なんとなく区切りがついたような気がしたのでデモサイトを作ってみました。

http://commondatastorage.googleapis.com/mingn/index.html

できることは gcc で適当なものをコンパイルしたり、 vim で編集したり ruby と python と nethack が動くくらいです。欠点としては redirect と pipe と sub-shell が無いので使いものにならないことです。 ICFPC 2006 の UMIX とかも動くようにコードを置いておきました。

bootstrap の bash と unzip 以外は HTML5 File System に突っ込んだバイナリを起動してるんで、 Chrome OS でオフライン開発する夢に一歩近付いたかなぁと思ってるんですけど、まだ10歩くらいはある道程なのでしんどい。

まあ TODO は死ぬほどたくさんあるんだけど、死ぬほどたくさんありすぎて、かなり巨大なやる気が来ないと解決されないので…

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h