Bug #4696

thread.c#lock_func() が spurious wakeup unsafe

Added by Motohiro KOSAKI almost 3 years ago. Updated almost 3 years ago.

[ruby-dev:43554]
Status:Closed
Priority:Normal
Assignee:Motohiro KOSAKI
Category:core
Target version:1.9.3
ruby -v:- Backport:

Description

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


static int
lockfunc(rbthreadt *th, mutext *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;

}


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

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

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

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

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

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

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

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

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

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

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

0001-new-deadlock-check.patch Magnifier (3.99 KB) Motohiro KOSAKI, 05/15/2011 04:23 PM


Subtasks

Bug #4723: check_deadlock_i での transition_for_lockの扱いが thread unsafeClosedMotohiro KOSAKI

Associated revisions

Revision 31436
Added by Tomoyuki Chikanaga almost 3 years ago

  • eval.c (framefuncid): method return different name from methods defined by Module#define_method with a same block. fixes #4606
    • eval (methodentryof_iseq): new helper function. search control frame stack for a method entry which has given iseq.
    • test/ruby/test_method.rb: add tests for #4696

Revision 32021
Added by Motohiro KOSAKI almost 3 years ago

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

Revision 32059
Added by Motohiro KOSAKI almost 3 years ago

  • threadwin32.c (nativecondsignal): remove unnecessary rbbug(). It's addional fix for r32021. [Bug #4696]

History

#1 Updated by Motohiro KOSAKI almost 3 years ago

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

#2 Updated by Yusuke Endoh almost 3 years ago

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

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

2011年5月15日16:22 Motohiro KOSAKI kosaki.motohiro@gmail.com:

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

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

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

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

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

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

--
Yusuke Endoh mame@tsg.ne.jp

#3 Updated by Yusuke Endoh almost 3 years ago

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

2011年5月15日16:22 Motohiro KOSAKI kosaki.motohiro@gmail.com:

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

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

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

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

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

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

--
Yusuke Endoh mame@tsg.ne.jp

#4 Updated by Motohiro KOSAKI almost 3 years ago

2011年5月15日17:31 Yusuke ENDOH mame@tsg.ne.jp:

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

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

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

#5 Updated by Motohiro KOSAKI almost 3 years ago

2011年5月15日17:31 Yusuke ENDOH mame@tsg.ne.jp:

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

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

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

#6 Updated by Motohiro KOSAKI almost 3 years ago

  • 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]

Also available in: Atom PDF