[PATCH][BZ #14417] Unlock mutex before going back to waiting for PI mutexes

[Siddhesh Poyarekar]

Hi,

Red Hat bz #552960[1] reported a deadlock in multiple threads doing a
pthread_cond_wait and the main thread doing a pthread_cond_signal, with
the synchronizing mutex having the PTHREAD_PRIO_INHERIT flag set.  This
was subsequently fixed with commit c5a0802a because the problem was
then thought to stem from the fact that the futex syscall returned an
EAGAIN.  The said commit put in code to retry the wait if the return
code from the futex syscall in the PI case was EAGAIN.

The fix however resulted in the problem mentioned in sourceware bz
#14417, where pulseaudio would hang in a pthread_cond_wait.  Analysis
of the bug showed that the pthread_cond* logic actually *depends* on
the EAGAIN, in the sense that it uses it as an indication of of a
wakeup that was almost lost to compensate for a race between a waiter
waiting and a signaller incrementing the futex.  Details of how this
happens (and why a waiter waking another waiter in this manner is OK)
are in Torvald's documentation patch[2] for pthread_cond_wait.

Further study of the original problem showed that the deadlock occurs
because of the way x86 and x86_64 do the futex_wait in the priority
inherited case.  The x86 and x86_64 implementations use the
FUTEX_WAIT_REQUEUE_PI operation which, on successful return, has the
mutex lock taken.  As a result of this, there could be two waiters, one
woken by the EAGAIN (W1) and another by the futex_wake (W2) from the
signal, that race to get out of the wait loop.  If the W1 succeeds in
getting out first, it would leave W1 to go back to do a futex wait.
The problem however, is that W1 does not release the mutex that the
kernel locked for it on successful return and the result of this is the
deadlock that we see.  A further problem (specific to x86_64) is that
W1 goes out thinking that it has the mutex, which is also incorrect.

The attached patch fixes these two problems.  For both x86 and x86_64,
if FUTEX_WAIT_REQUEUE_PI returns success but the thread has to go back
to wait, it unlocks the mutex before going back.  Further, if the
thread is woken by an EAGAIN, it acts as if it came out of the normal
FUTEX_WAIT, and hence attempts to lock the mutex before returning.  The
latter fix is only for x86.

Testing:
=======

I have tested this fix on x86_64 by building glibc for 64 as well as
32-bit.  There is also a test case in this fix, which passes
successfully with this patch.  I have also made sure that the test case
fails without this patch.

Further, bz #14477 is also caused due to the same reason (lock held by
the sleeping waiter), but is a different problem.  I will work on a fix
for that too, but I'd like to get this one in first since the approach
for both fixes will be similar.

Regards,
Siddhesh

nptl/ChangeLog:

	* Makefile (tests): New test case tst-cond24.
	(LDFLAGS-tst-cond24): Link tst-cond24 against librt.
	* sysdeps/unix/sysv/linux/i386/i486/pthread_cond_timedwait.S
	(__pthread_cond_timedwait): Unlock mutex before going back to
	wait in PI case.
	* sysdeps/unix/sysv/linux/i386/i486/pthread_cond_wait.S
	(__pthread_cond_wait): Likewise.  Revert handling of EAGAIN
	return from futex_wait.
	* sysdeps/unix/sysv/linux/x86_64/pthread_cond_timedwait.S
	(__pthread_cond_timedwait): Unlock mutex before going back to
	wait in PI case.  Set requeue_pi flag only if wait returned 0.
	* sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S
	(__pthread_cond_wait): Likewise.  Revert handling of EAGAIN
	return from futex_wait.
	* tst-cond24.c: New test case.

[1]: https://bugzilla.redhat.com/show_bug.cgi?id=552960
[2]: http://sourceware.org/ml/libc-alpha/2012-09/msg00555.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: condvar-deadlock.patch
Type: text/x-patch
Size: 18348 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20120921/1da235bd/attachment.bin>