[Bug libstdc++/50862] New: deadlock in std::condition_variable_any

[Bug libstdc++/50862] New: deadlock in std::condition_variable_any

[bartosz.szurgot at pwr dot wroc.pl]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

             Bug #: 50862
           Summary: deadlock in std::condition_variable_any
    Classification: Unclassified
           Product: gcc
           Version: 4.6.1
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: bartosz.szurgot@pwr.wroc.pl


Created attachment 25610
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25610
proof of concept for deadlock

there is a dead lock when using wait() method of std::condition_variable_any
(condition_variable:199) from more than one thread. it happens when method
locks two mutexes (local and user-provided), when condition is met, in a
different order than when entering.

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[bartosz.szurgot at pwr dot wroc.pl]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #1 from basz <bartosz.szurgot at pwr dot wroc.pl> 2011-10-25 10:28:09 UTC ---
Created attachment 25611
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25611
patch fixing the problem

unlocking local mutex, before locking back user's lock solves the problem.

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2011-10-25
         AssignedTo|unassigned at gcc dot       |redi at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-10-25 11:27:33 UTC ---
on it

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.6.3

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-10-25 13:00:19 UTC ---
The patch isn't sufficient because of this requirement in the standard:
"If the function exits via an exception, lock.lock() shall be called prior to
exiting the function scope."

I'll commit a fix this evening.

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[bartosz.szurgot at pwr dot wroc.pl]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #4 from basz <bartosz.szurgot at pwr dot wroc.pl> 2011-10-25 13:51:45 UTC ---
the most recent document on C++0x i have is N3290. according to it it is so for
condition_variable (30.5.1.9 and 30.5.1.10), but description for wait() of
condition_variable_any is a bit more confusing. it says that it must be called
in 30.5.2.10, but 30.5.2.9 say it is undefined, if lock is called or not
("Note: if any of the wait functions exits via an exception, it is unspecified
whether the Lock is held. One can use a Lock type that allows to query that,
such as the unique_lock wrapper.")... :/

i hope this is just a simple mistake in the spec (otherwise it would be a bit
of a pain in the neck). do you have any more recent document to verify this?

perhaps this should be a separate bug report?

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-10-25 14:09:29 UTC ---
(In reply to comment #4)
> condition_variable_any is a bit more confusing. it says that it must be called
> in 30.5.2.10, but 30.5.2.9 say it is undefined, if lock is called or not

No no no, that's not what it says.

It says lock.lock() is called, that is a requirement. It must be called.

But calling lock.lock() could fail, so the note clarifies that it is
*unspecified* (not undefined!) whether the lock is *held*.

So lock.lock() will be called, but it might not succeed.

> ("Note: if any of the wait functions exits via an exception, it is unspecified
> whether the Lock is held. One can use a Lock type that allows to query that,
> such as the unique_lock wrapper.")... :/
> 
> i hope this is just a simple mistake in the spec (otherwise it would be a bit
> of a pain in the neck). do you have any more recent document to verify this?

It's not a mistake. http://lwg.github.com/issues/lwg-defects.html#1497

> perhaps this should be a separate bug report?

No, it's intimately related, I'll fix it all at once. But not until this
evening.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2406.html#gen_cond_var
covers all this, with a working implementation

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[bartosz.szurgot at pwr dot wroc.pl]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #6 from basz <bartosz.szurgot at pwr dot wroc.pl> 2011-10-25 14:45:29 UTC ---
yes - you're right. i got this note all wrong. thanks for the clarifications
and links!

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-10-25 20:56:47 UTC ---
Author: redi
Date: Tue Oct 25 20:56:43 2011
New Revision: 180446

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=180446
Log:
    PR libstdc++/50862
    * include/std/condition_variable (condition_variable_any::wait): Fix
    deadlock and ensure _Lock::lock() is called on exit.
    (condition_variable_any::native_handle): Remove, as per LWG 1500.
    * testsuite/30_threads/condition_variable_any/50862.cc: New.

Added:
    trunk/libstdc++-v3/testsuite/30_threads/condition_variable_any/50862.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/std/condition_variable

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-10-25 22:29:41 UTC ---
fixed on trunk so far, I'll wait until 4.6.2 is released then fix it for 4.6.3
too

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[bartosz.szurgot at pwr dot wroc.pl]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #9 from bartek 'basz' szurgot <bartosz.szurgot at pwr dot wroc.pl> 2011-10-26 06:39:15 UTC ---
implementation is nice. i think there is still one more problem to be fixed,
though. namely the line:
~_Unlock() { _M_lock.lock(); }
since lock() may throw an exception, which should never take place in d-tor.
more over, ~_Unlock() can happen to be called because of an exception thrown
from:
_M_cond.wait(__my_lock2);
which means terminate().

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-10-26 10:29:50 UTC ---
Yes, I suppose it should be:

~_Unlock()
{
  if (uncaught_exception())
    __try { _M_lock.lock(); } __catch(...) { }
  else
    _M_lock.lock();
}

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[bartosz.szurgot at pwr dot wroc.pl]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #11 from bartek 'basz' szurgot <bartosz.szurgot at pwr dot wroc.pl> 2011-10-26 12:41:34 UTC ---
i'm not sure about uncaught_exception(). i remember reading in Herb Sutter's
that it's usage should be avoided, since it has some flaw, that makes it's
return value unsure. but this was written in times of C++03 and i can't
remember what was the reasoning behind it (threading perhaps?), so i do not
know if it still holds for C++11 as well or not. any way there is still a
possibility of exception throwing from d-tor, which would be better to avoid.

for now my proposal to overcome this is something like:

struct _Unlock
{
  explicit _Unlock(_Lock& __lk) : _M_lock(&__lk) { __lk.unlock(); }
  ~_Unlock()
  {
    try
    {
      if(_M_lock)
        _M_lock->lock();
    }
    catch(...){}
  }
  _Lock &release(void)
  {
     _Lock* tmp=_M_Lock;
     _M_Lock=nullptr;
     return *tmp;
  }
private:
  _Lock* _M_lock;
};

unique_lock<mutex> __my_lock(_M_mutex);
_Unlock __unlock(__lock);
unique_lock<mutex> __my_lock2(std::move(__my_lock));
_M_cond.wait(__my_lock2);
__unlock.release().lock(); // if no exception so far - may throw here

general idea is to call lock() in d-tor inside the try-catch block, in case of
any exception, anywhere in the method, and if there was no one risen until the
last line we take responsibility for calling lock() from __unlock and call it
explicitly, so that exception can always be safely thrown from that call.

but perhaps we'd be able to come out with some better/cleaner/shorter solution
for this problem?

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #12 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-10-26 13:02:31 UTC ---
(In reply to comment #11)
> i'm not sure about uncaught_exception(). i remember reading in Herb Sutter's
> that it's usage should be avoided, since it has some flaw, that makes it's
> return value unsure.

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#1368 ?


> but this was written in times of C++03 and i can't
> remember what was the reasoning behind it (threading perhaps?), so i do not
> know if it still holds for C++11 as well or not. any way there is still a
> possibility of exception throwing from d-tor, which would be better to avoid.

Why?  In general, yes. But in this specific case I don't see a problem.
it's a local class, noone can misuse it elsewhere.
The value of uncaught_exception is well defined at the point where I want to
call it.

> but perhaps we'd be able to come out with some better/cleaner/shorter solution
> for this problem?

Comment 10 :)

In practice, _M_cond.wait() is not going to throw (the error conditions for
pthread_cond_wait cannot happen here) so this is irrelevant.

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #13 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-10-26 13:05:52 UTC ---
(In reply to comment #11)
> unique_lock<mutex> __my_lock(_M_mutex);
> _Unlock __unlock(__lock);
> unique_lock<mutex> __my_lock2(std::move(__my_lock));
> _M_cond.wait(__my_lock2);
> __unlock.release().lock(); // if no exception so far - may throw here

This re-locks it while _M_mutex is locked, reintroducing the deadlock

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[bartosz.szurgot at pwr dot wroc.pl]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #14 from bartek 'basz' szurgot <bartosz.szurgot at pwr dot wroc.pl> 2011-10-26 13:42:29 UTC ---
uhum - i missed that one... :/

ok then - looks like http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862#c10 is a
working solution. :)

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[aoliva at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #15 from Alexandre Oliva <aoliva at gcc dot gnu.org> 2011-10-26 13:55:25 UTC ---
Shouldn't the testcase contain:

// { dg-require-sched-yield "" }

?  I'm getting a failure because this_thread::yield is not defined, and
30_threads/this_thread/2.cc contains this directive so as to not fail in the
same way.

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #16 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-10-26 14:06:12 UTC ---
Yes, thanks for spotting it.  Ideally we'd define this_thread::yield() anyway,
but until then the test should use the dg-require

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #17 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-10-26 23:35:30 UTC ---
Author: redi
Date: Wed Oct 26 23:35:26 2011
New Revision: 180549

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=180549
Log:
    PR libstdc++/50862
    * include/std/condition_variable (condition_variable_any::wait): Avoid
    terminating if relocking user mutex throws during stack-unwinding.
    * testsuite/30_threads/condition_variable_any/50862.cc: Add dg-require.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/std/condition_variable
    trunk/libstdc++-v3/testsuite/30_threads/condition_variable_any/50862.cc

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

--- Comment #18 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-12-19 00:34:33 UTC ---
Author: redi
Date: Mon Dec 19 00:34:29 2011
New Revision: 182467

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=182467
Log:
    PR libstdc++/50862
    * include/std/condition_variable (condition_variable_any::wait): Fix
    deadlock and ensure _Lock::lock() is called on exit.
    * testsuite/30_threads/condition_variable_any/50862.cc: New.

Added:
   
branches/gcc-4_6-branch/libstdc++-v3/testsuite/30_threads/condition_variable_any/50862.cc
Modified:
    branches/gcc-4_6-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_6-branch/libstdc++-v3/include/std/condition_variable

[Bug libstdc++/50862] deadlock in std::condition_variable_any

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50862

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #19 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-12-19 00:35:07 UTC ---
fixed for 4.6.3