Bug #4696: thread.c#lock_func() が spurious wakeup unsafe

• Status: Closed
• Assignee: kosaki (Motohiro KOSAKI)
• Target version: 1.9.3
• ruby -v: -

[kosaki (Motohiro KOSAKI)]

レビューをしていて、気づいたので起票します。
現在の lock_func (ie Mutex.lockの実体)は以下のような構造になっています
（本質的ではない部分をカットしてあります）

---

static int
lock_func(rb_thread_t *th, mutex_t *mutex, int timeout_ms)
{
for (;;) {
if (!mutex->th) {
mutex->th = th;
break;
}

    mutex->cond_waiting++;
    if (timeout_ms) {
        ret = native_cond_timedwait(&mutex->cond, &mutex->lock, &timeout);
        if (ret == ETIMEDOUT) {
            interrupted = 2;
            mutex->cond_waiting--;
            break;
        }
    }
    else {
        native_cond_wait(&mutex->cond, &mutex->lock);
    }
    mutex->cond_notified--;

    if (RUBY_VM_INTERRUPTED(th)) {
        interrupted = 1;
        break;
    }
}
return interrupted;

}

---

以下の２つの問題点があります。

1. native_cond_wait() が spurious wakeupで起床したばあい、誰もnative_cond_signal()を
   呼んでいないにもかかわらず cond_notified がデクリメントされてしまう。
   結果、以後デッドロックチェックが誤動作する

2. pthread_cond_timedwait()で寝ているスレッドが、pthread_cond_signal()にて起床させられ、
   かつ、コンテキススイッチやらなにやらしている間にタイムアウト時間も過ぎてしまった場合
   戻り値が０になるかETIMEOUTになるかはプラットフォーム依存。この場合にETIMEOUTを返す
   プラットフォーム上で、復帰値のETIMEOUTを信用するとやはり mutex->cond_waiting がずれてしまう。
   対策としては、さきにcond waitが暗に持っているpredicate（この場合は mutex->th と
   RUBY_VM_INTERRUPTED のチェックを最初におこない、それが終わってからETIMEOUTチェックを
   することで、プラットフォームの影響を避けられます。

(1)は deadlock checkマージ時からの障害なんですが、YARVマージ時点ですでに
mutex->cond_waiting がずれる問題はあって、それを顕在化させる方法がなかったという理解
(2)はpthread_cond_timedwitを使うようにした r31373 からの障害

結局最大の問題はspurious wakeupがある以上、native_cond_signal()を呼ぶ回数とwakeupの回数は
一致する保証はないのだから、カウンタをcond_signal時に+1してwakeupしたときに-1する設計は
無理があるということです。

で、さらによくよく考えてみるとdeadlockの設計はもっと簡単に出来ることが分かりました。
lock_func内でunlock待ちで滞留しているスレッドの数は簡単にカウントできるのだから、
mutex->thがNULLで滞留スレッドが０じゃなければ、過度期状態ということでしょう。

パッチを作ってみたところ、添付のようにかなり小さい修正で対応できることが分かったので
取り込み可能と思いますが、１－２週間まってささださんやまめさんが反対するなら流産にさせようと
思います。

なお、軽く各プラットフォームの状況を聞いたり調べた感じだと以下のような状況

・Linux
pthread_cond_wait()がglibc内でspurious wakeup対応があるので、アプリケーションからは
spurious wakeupは見えない。linux thread だとシグナル受けるとEINTRで復帰してしまうバグが
あるが、それは thread_pthread.c#native_cond_wait() で塞いである(r31482)ので影響を与えない。
pthread_cond_timedwait()の復帰値はバージョンによって異なり、初期のglibcは０を返したが
最近のはわざわざシステムコールから復帰したあとに、clock_gettime()で時間をチェックして
時間超過していた場合は復帰値をETIMEOUTに差し替える処理が追加されており問題が起こる
（余計なことを・・・）

・NetBSD
上記状況で、pthread_cond_timedwait()がETIMEOUTを返す仕様であると、聞いたことがあります。

・Mac
なんと、スレッドがシグナルと受けると cond_wait()が0を復帰値にして返ってくると言う
トンデモ仕様だそうです。

[kosaki (Motohiro KOSAKI)]

• File 0001-new-deadlock-check.patch 0001-new-deadlock-check.patch added

添付に失敗したみたい。再チャレンジ

[mame (Yusuke Endoh)]

• ruby -v changed from ruby 1.9.3dev (2011-05-13 trunk 31548) [x86_64-linux] to -

遠藤です。
なぜか名指しされているので (いや、遠藤が作ったバグだからだけど)

2011年5月15日16:22 Motohiro KOSAKI [e-mail]:

以下の２つの問題点があります。

両方とも、おっしゃるとおりだと思います。

パッチを作ってみたところ、添付のようにかなり小さい修正で対応できることが分かったので
取り込み可能と思いますが、１−２週間まってささださんやまめさんが反対するなら流産にさせようと
思います。

このパッチに問題がないかどうかは自信がないですが、現状に問題があることには
自信がある (実用上問題になるかというと、ほぼ osx でしか問題にならないよう
ですが) ので、遠藤はとりあえず賛成です。

1.9.3 リリースに向けて、もしこのパッチに関係ありそうな問題が起きた場合は、
とりあえず revert するということで。

あと、transition_for_lock に volatile を付けるのもお願いします

--
Yusuke Endoh [e-mail]

[mame (Yusuke Endoh)]

遠藤です。
なぜか名指しされているので (いや、遠藤が作ったバグだからだけど)

2011年5月15日16:22 Motohiro KOSAKI [e-mail]:

以下の２つの問題点があります。

両方とも、おっしゃるとおりだと思います。

パッチを作ってみたところ、添付のようにかなり小さい修正で対応できることが分かったので
取り込み可能と思いますが、１−２週間まってささださんやまめさんが反対するなら流産にさせようと
思います。

このパッチに問題がないかどうかは自信がないですが、現状に問題があることには
自信がある (実用上問題になるかというと、ほぼ osx でしか問題にならないよう
ですが) ので、遠藤はとりあえず賛成です。

1.9.3 リリースに向けて、もしこのパッチに関係ありそうな問題が起きた場合は、
とりあえず revert するということで。

あと、transition_for_lock に volatile を付けるのもお願いします

--
Yusuke Endoh [e-mail]

[kosaki (Motohiro KOSAKI)]

2011年5月15日17:31 Yusuke ENDOH [e-mail]:

遠藤です。
なぜか名指しされているので (いや、遠藤が作ったバグだからだけど)

いやあ、このへんの普通の人が普通に作ると絶対バグってる実装が出来上がる罠仕様の塊な
あたりが、pthreadは脳みそに水虫が沸いたサルによって設計されたと揶揄される由縁なんでしょう。
わたしも初見で気づいたわけではなくて、何ヶ月も怪しい匂いを感じつつ言語化できないもやもやを
抱えていたので。

さらに転じてここから、RubyのConditionVariable は低レベルすぎて普通のRubyプログラマには
絶対正しく使えないから、もっと高レベルなクラスを標準添付しようず。って話につながるんだと思います。
お盆休みぐらいに一度考える時間がとれたらいいな。まつもとさんからは pythonの processingライブラリ
いいよいいよって言われていてすごく気になってるし。

[kosaki (Motohiro KOSAKI)]

2011年5月15日17:31 Yusuke ENDOH [e-mail]:

遠藤です。
なぜか名指しされているので (いや、遠藤が作ったバグだからだけど)

いやあ、このへんの普通の人が普通に作ると絶対バグってる実装が出来上がる罠仕様の塊な
あたりが、pthreadは脳みそに水虫が沸いたサルによって設計されたと揶揄される由縁なんでしょう。
わたしも初見で気づいたわけではなくて、何ヶ月も怪しい匂いを感じつつ言語化できないもやもやを
抱えていたので。

さらに転じてここから、RubyのConditionVariable は低レベルすぎて普通のRubyプログラマには
絶対正しく使えないから、もっと高レベルなクラスを標準添付しようず。って話につながるんだと思います。
お盆休みぐらいに一度考える時間がとれたらいいな。まつもとさんからは pythonの processingライブラリ
いいよいいよって言われていてすごく気になってるし。

[kosaki (Motohiro KOSAKI)]

• Status changed from Assigned to Closed
• % Done changed from 0 to 100

This issue was solved with changeset r32021.
Motohiro, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

---

• thread.c: introduce spurious wakeup safe deadlock check.
  [Bug #4696][ruby-dev:43554]