[Ruby 1.9 - Bug #4696][Assigned] thread.c#lock func() が spurious wakeup unsafe

Issue #4696 has been reported by Motohiro KOSAKI.


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

Author: Motohiro KOSAKI
Status: Assigned
Priority: Low
Assignee: Motohiro KOSAKI
Category: core
Target version: 1.9.3
ruby -v: ruby 1.9.3dev (2011-05-13 trunk 31548) [x86_64-linux]

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


static int
lock_func(rb_thread_t *th, mutex_t *mutex, int timeout_ms)
{
for (;:wink: {
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. native_cond_wait() が spurious wakeupで起床したばあい、誰もnative_cond_signal()を
    呼んでいないにもかかわらず cond_notified がデクリメントされてしまう。
    結果、以後デッドロックチェックが誤動作する

  2. pthread_cond_timedwait()で寝ているスレッドが、pthread_cond_signal()にて起床させられ、
    かつ、コンテキススイッチやらなにやらしている間にタイムアウト時間も過ぎてしまった場合
    戻り値が0になるか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で滞留スレッドが0じゃなければ、過度期状態ということでしょう。

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

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

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

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

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

Issue #4696 has been updated by Motohiro KOSAKI.

File 0001-new-deadlock-check.patch added

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

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

Author: Motohiro KOSAKI
Status: Assigned
Priority: Low
Assignee: Motohiro KOSAKI
Category: core
Target version: 1.9.3
ruby -v: ruby 1.9.3dev (2011-05-13 trunk 31548) [x86_64-linux]

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


static int
lock_func(rb_thread_t *th, mutex_t *mutex, int timeout_ms)
{
for (;:wink: {
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. native_cond_wait() が spurious wakeupで起床したばあい、誰もnative_cond_signal()を
    呼んでいないにもかかわらず cond_notified がデクリメントされてしまう。
    結果、以後デッドロックチェックが誤動作する

  2. pthread_cond_timedwait()で寝ているスレッドが、pthread_cond_signal()にて起床させられ、
    かつ、コンテキススイッチやらなにやらしている間にタイムアウト時間も過ぎてしまった場合
    戻り値が0になるか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で滞留スレッドが0じゃなければ、過度期状態ということでしょう。

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

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

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

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

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

2011$BG/(B5$B7n(B15$BF|(B17:31 Yusuke ENDOH [email protected]:

$B1sF#$G$9!#(B
$B$J$<$+L>;X$7$5$l$F$$$k$N$G(B ($B$$$d!"1sF#$,:n$C$?%P%0$@$+$i$@$1$I(B)

$B$$$d$“!”$3$N$X$s$NIaDL$N?M$,IaDL$K:n$k$H@dBP%P%0$C$F$k<BAu$,=PMh>e$,$kf+;EMM$N2t$J(B
$B$“$?$j$,!”(Bpthread$B$OG>$_$=$K?eCn$,J($$$?%5%k$K$h$C$F@_7W$5$l$?$HYhYi$5$l$kM31o$J$s$G$7$g$&!#(B
$B$o$?$7$b=i8+$G5$$E$$$?$o$1$G$O$J$/$F!"2?%v7n$b2x$7$$Fw$$$r46$8$D$D8@8l2=$G$-$J$$$b$d$b$d$r(B
$BJz$($F$$$?$N$G!#(B

$B$5$i$KE>$8$F$3$3$+$i!“(BRuby$B$N(BConditionVariable
$B$ODc%l%Y%k$9$.$FIaDL$N(BRuby$B%W%m%0%i%^$K$O(B
$B@dBP@5$7$/;H$($J$$$+$i!”$b$C$H9b%l%Y%k$J%/%i%9$rI8=`E:IU$7$h$&$:!#$C$FOC$K$D$J$,$k$s$@$H;W$$$^$9!#(B
$B$*K_5Y$_$0$i$$$K0lEY9M$($k;~4V$,$H$l$?$i$$$$$J!#$^$D$b$H$5$s$+$i$O(B
python$B$N(B processing$B%i%$%V%i%j(B
$B$$$$$h$$$$$h$C$F8@$o$l$F$$$F$9$4$/5$$K$J$C$F$k$7!#(B

$B1sF#$G$9!#(B
$B$J$<$+L>;X$7$5$l$F$$$k$N$G(B ($B$$$d!"1sF#$,:n$C$?%P%0$@$+$i$@$1$I(B)

2011$BG/(B5$B7n(B15$BF|(B16:22 Motohiro KOSAKI
[email protected]:

$B0J2<$N#2$D$NLdBjE@$,$"$j$^$9!#(B

$BN>J}$H$b!"$$C$7$c$k$H$$j$@$H;W$$$^$9!#(B

$B%Q%C%A$r:n$C$F$_$?$H$3$m!"E:IU$N$h$&$K$+$J$j>.$5$$=$@5$GBP1~$G$-$k$3$H$,J,$+$C$?$N$G(B

$B<h$j9~$_2DG=$H;W$$$^$9$,!"#1!]#2=54V$^$C$F$5$5$@$5$s$d$^$a$5$s$,H?BP$9$k$J$iN.;:$K$5$;$h$&$H(B

$B;W$$$^$9!#(B

$B$3$N%Q%C%A$KLdBj$,$J$$$+$I$&$+$O<+?.$,$J$$$G$9$,!“8=>u$KLdBj$,$”$k$3$H$K$O(B
$B<+?.$,$“$k(B ($BeLdBj$K$J$k$+$H$$$&$H!”$[$(B osx
$B$G$7$+LdBj$K$J$i$J$$$h$&(B
$B$G$9$,(B) $B$N$G!“1sF#$O$H$j$”$($:;?@.$G$9!#(B

1.9.3
$B%j%j!<%9$K8~$1$F!“$b$7$3$N%Q%C%A$K4X78$”$j$=$&$JLdBj$,5/$-$?>l9g$O!“(B
$B$H$j$”$($:(B revert $B$9$k$H$$$&$3$H$G!#(B

$B$“$H!”(Btransition_for_lock $B$K(B volatile

$B$rIU$1$k$N$b$*4j$$$7$^$9(B