[Bug libc/14958] New: Concurrent reader deadlock in pthread_rwlock_rdlock()

[Bug libc/14958] New: Concurrent reader deadlock in pthread_rwlock_rdlock()

[daniel.stodden at gmail dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=14958

             Bug #: 14958
           Summary: Concurrent reader deadlock in pthread_rwlock_rdlock()
           Product: glibc
           Version: 2.18
            Status: NEW
          Severity: normal
          Priority: P2
         Component: libc
        AssignedTo: unassigned@sourceware.org
        ReportedBy: daniel.stodden@gmail.com
                CC: drepper.fsp@gmail.com
    Classification: Unclassified


Created attachment 6780
  --> http://sourceware.org/bugzilla/attachment.cgi?id=6780
Example program provoking concurrent reader deadlock.

We believe we found a deadlock scenario in NPTL's rwlock implementation, 
relating to additional scheduling dependencies which NPTL imposes on 
concurrent readers.

It happens when facing sufficient congestion between both 
read- and write-locking candidates queued.

The code attached was tested on eglibc 2.15, but we believe the same
issue remains present in any more recent version of glibc and eglibc
we've seen.

It contains additional comments and a description of an event series
which lead to readers never woken, despite the rwlock being held in
read-locked mode.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[daniel.stodden at gmail dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=14958

--- Comment #1 from Daniel Stodden <daniel.stodden at gmail dot com> 2012-12-13 23:21:36 UTC ---
Here are snippets from a GDB session investigating the blocked program.

(gdb) thread apply all bt

Thread 5 (Thread 0x7ffff5ffc700 (LWP 8428)):
#0  pthread_cond_wait@@GLIBC_2.3.2 () at
../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:162
#1  0x0000000000400a4a in R1 () at rwlock.c:56
#2  0x0000000000400a11 in loop (data=0x400a1b) at rwlock.c:116
#3  0x00007ffff7bc4e9a in start_thread (arg=0x7ffff5ffc700) at
pthread_create.c:308
#4  0x00007ffff78f24bd in clone () at
../sysdeps/unix/sysv/linux/x86_64/clone.S:112
#5  0x0000000000000000 in ?? ()

Thread 4 (Thread 0x7ffff67fd700 (LWP 8427)):
#0  pthread_rwlock_rdlock () at
../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_rdlock.S:85
#1  0x0000000000400a77 in R0 () at rwlock.c:36
#2  0x0000000000400a11 in loop (data=0x400a69) at rwlock.c:116
#3  0x00007ffff7bc4e9a in start_thread (arg=0x7ffff67fd700) at
pthread_create.c:308
#4  0x00007ffff78f24bd in clone () at
../sysdeps/unix/sysv/linux/x86_64/clone.S:112
#5  0x0000000000000000 in ?? ()

Thread 3 (Thread 0x7ffff6ffe700 (LWP 8426)):
#0  pthread_rwlock_wrlock () at
../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_wrlock.S:83
#1  0x0000000000400acc in W1 () at rwlock.c:75
#2  0x0000000000400a11 in loop (data=0x400abe) at rwlock.c:116
#3  0x00007ffff7bc4e9a in start_thread (arg=0x7ffff6ffe700) at
pthread_create.c:308
#4  0x00007ffff78f24bd in clone () at
../sysdeps/unix/sysv/linux/x86_64/clone.S:112
#5  0x0000000000000000 in ?? ()

Thread 2 (Thread 0x7ffff77ff700 (LWP 8425)):
#0  pthread_rwlock_wrlock () at
../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_wrlock.S:83
#1  0x0000000000400aef in W0 () at rwlock.c:67
#2  0x0000000000400a11 in loop (data=0x400ae2) at rwlock.c:116
#3  0x00007ffff7bc4e9a in start_thread (arg=0x7ffff77ff700) at
pthread_create.c:308
#4  0x00007ffff78f24bd in clone () at
../sysdeps/unix/sysv/linux/x86_64/clone.S:112
#5  0x0000000000000000 in ?? ()

Thread 1 (Thread 0x7ffff7fe0700 (LWP 8422)):
#0  0x00007ffff7bc6148 in pthread_join (threadid=140737328961280,
thread_return=0x0) at pthread_join.c:89
#1  0x00000000004008a7 in main (argc=<optimized out>, argv=<optimized out>) at
rwlock.c:143

(gdb) #
(gdb) # Note thread 4 (R0) blocked inside pthread_rwlock_rdlock(),
(gdb) # while rdlock is available, but held by R1 exclusively.
(gdb) #
(gdb) print rwlock
$3 = {__data = {__lock = 0, __nr_readers = 1, __readers_wakeup = 209,
__writer_wakeup = 1186, __nr_readers_queued = 1, __nr_writers_queued = 2,
__writer = 0, __shared = 0, __pad1 = 0, __pad2 = 0, __flags = 0}, __size =
"\000\000\000\000\001\000\000\000\321\000\000\000\242\004\000\000\001\000\000\000\002",
'\000' <repeats 34 times>, __align = 4294967296}

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[daniel.stodden at gmail dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=14958

Daniel Stodden <daniel.stodden at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |daniel.stodden at gmail dot
                   |                            |com

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[bugdal at aerifal dot cx]

http://sourceware.org/bugzilla/show_bug.cgi?id=14958

Rich Felker <bugdal at aerifal dot cx> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugdal at aerifal dot cx

--- Comment #2 from Rich Felker <bugdal at aerifal dot cx> 2012-12-15 05:15:58 UTC ---
Confirmed. I don't see a need for more debugging/trace data. What's going on is
very clear upon reading the original report and test case. I see two potential
fixes:

1. The easy way is to just always use broadcast wakes and let readers and
writers duke it out for who gets the lock next. NPTL's synchronization
primitives are riddled with bugs from trying to be too smart (avoiding spurious
wakes, etc.) and missing important corner cases, and I would not be sad to see
all this ripped out in favor of something that's definitively robust; however,
I recognize I'm probably in the minority here.

2. The way that's harder to get right but that should give better performance
is for the reader that "steals" the lock from waiting writers to detect this
situation and broadcast wake the futex so that all the other waiting readers
also wake up and get a chance to obtain read locks. It seems highly nontrivial
to get all the corner cases right here, especially since waiting writers can be
performing a timedlock operation and could be gone by the time the reader
"steals" the lock from them.

I also confirmed that we don't have a corresponding bug in musl (which uses
approach #1 above).

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[daniel.stodden at gmail dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=14958

--- Comment #3 from Daniel Stodden <daniel.stodden at gmail dot com> 2012-12-16 09:12:29 UTC ---
(In reply to comment #2)
>
> 1. The easy way is to just always use broadcast wakes and let readers and
> writers duke it out for who gets the lock next. NPTL's synchronization
> primitives are riddled with bugs from trying to be too smart (avoiding spurious
> wakes, etc.) and missing important corner cases, and I would not be sad to see
> all this ripped out in favor of something that's definitively robust; however,
> I recognize I'm probably in the minority here.

Yes. This is also the way we're working around the issue until a general fix
becomes available.

The snipped below depends too much on nptl internals to be recommendable
for general use. Posted because it might save the day for those who happen to 
know exactly what they link against.

#include <pthread.h>
#include <limits.h>
#include <unistd.h>
#include <syscall.h>
#include <linux/futex.h>

int
pthread_rwlock_rdlock(pthread_rwlock_t *rwlock)
{
    extern typeof(pthread_rwlock_rdlock) __pthread_rwlock_rdlock;
    int err;

    err = __pthread_rwlock_rdlock(rwlock);
    if (err)
        return err;

    /* NB. Up to least eglibc 2.15, an nptl read lock acquired 
         * doesn't guarantee that all readers expecting to
     * run get woken up. Fixed by rerunning the wakeup call from
     * within. */

    if (rwlock->__data.__nr_readers_queued) {
        /* NB. nasty to resort to atomic ops, but this spares
         * us reimplementing the ll lock while maintaining
         * increment stride. */
        (void)__sync_add_and_fetch(&rwlock->__data.__readers_wakeup, 1);

        /* NB. 'in libc.so or ld.so all futexes are private.' */
        syscall(SYS_futex,
            &rwlock->__data.__readers_wakeup, INT_MAX,
            FUTEX_WAKE | FUTEX_PRIVATE_FLAG,
            NULL, NULL, 0);
    }

    return 0;
}

> 2. The way that's harder to get right but that should give better performance
> is for the reader that "steals" the lock from waiting writers to detect this
> situation and broadcast wake the futex so that all the other waiting readers
> also wake up and get a chance to obtain read locks. It seems highly nontrivial
> to get all the corner cases right here, especially since waiting writers can be
> performing a timedlock operation and could be gone by the time the reader
> "steals" the lock from them.

I agree that detecting writer preemption based on present state is not
possible.

Still, a modified version more carefully negotiating between queued/woken
writers and lock release (to maintain writer starvation avoidance) certainly
could be made. Especially since arbitration through a single mutex makes this
relatively straightforward to implement.

(I must say I was quite suprised how much the current implementation is
avoiding fetch/add or cas operations to achieve this.)

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[bugdal at aerifal dot cx]

http://sourceware.org/bugzilla/show_bug.cgi?id=14958

--- Comment #4 from Rich Felker <bugdal at aerifal dot cx> 2012-12-16 17:33:15 UTC ---
I don't necessarily believe it's impossible; just difficult. For example, the
unlocking thread wanting to wake a writer could set a flag in the rwlock
structure before unlocking indicating that intent. A writer, upon obtaining the
lock, could clear it. A reader, upon obtaining the lock, could inspect the
flag, and if nonzero, broadcast-wake readers and clear the flag. This algorithm
sounds roughly correct, but there may still be holes in it.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[daniel.stodden at gmail dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=14958

--- Comment #5 from Daniel Stodden <daniel.stodden at gmail dot com> 2012-12-17 09:19:31 UTC ---
Rich, I pushed a candidate fix to
https://github.com/dns42/glibc/commit/b7725621b5e2101d4218be0d09bd55a67b4d3512

It explores variant 1 for upstream.

Code presently looks correct to me, but I won't get to test it before later.
I'll post an update accordingly :)

Additional comments for discussion:

 - Note that prerequisites can be checked comparatively precisely.
   Possibly more precisely than you anticipated, taking
   __nr_readers_queued, __nr_writers_queued and __nr_readers
   into account, all at the same time.

 - This works because both queues need to come together, then
   preempted, any other case looks clean to me.

   All queued loops take the ll lock and atomically decrement, then
   succeed. So the whole combination of __nr_*_queued and __nr_readers
   can work as a discriminant.

 - As you mentioned, the timedlock cases indeed deserve special
   attention.

   I think the way they've been written would render the assumptions 
   made by the above patch correct as well.

   But only if rwlock_timedlock calls are really correct.

   Can it be that lll_futex_timed_wait does *not*
   leave an inherent race between timeout and a (too-)late wakeup call?
   In the same way pthread_cond_timedwait must?

   I'm not a futex-expert, but the problem here is that I currently
   don't believe this is even possible. In other words: How does
   present pthread_rwlock_unlock tell that any of __nr_writers_queued
   have been woken up before timing out?

   I almost suspect it can't, doesn't, and -- since timedrwlock makes 
   no attempt to restart the queue on timeout either,
   suffers from a similar race. But this would probably belong into
   another ticket.

   Apologies in advance if I'm mistaken.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug libc/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[neleai at seznam dot cz]

https://sourceware.org/bugzilla/show_bug.cgi?id=14958

Ondrej Bilka <neleai at seznam dot cz> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |WAITING
                 CC|                            |neleai at seznam dot cz

--- Comment #6 from Ondrej Bilka <neleai at seznam dot cz> ---
Daniel, could you send that patch to libc-alpha?

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[jsm28 at gcc dot gnu.org]

https://sourceware.org/bugzilla/show_bug.cgi?id=14958

Joseph Myers <jsm28 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|libc                        |nptl

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14958

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fweimer at redhat dot com

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[triegel at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14958

Torvald Riegel <triegel at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |ASSIGNED
                 CC|                            |triegel at redhat dot com

--- Comment #7 from Torvald Riegel <triegel at redhat dot com> ---
I think it is, strictly speaking, debatable whether the test case (and
underlying assumption about the required behavior) is correct.  If Thread
Execution Scheduling were not supported, the behavior is
implementation-defined:
http://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_rdlock.html

glibc claims it does support it, but the testcase does not explicitly set a
scheduling policy; I would read the POSIX spec as still allowing
implementation-defined behavior in this case.  Nonetheless, given that the
current rwlock implementation ignores the priorities (see bug 13701) and tries
to prefer readers (unless PTHREAD_RWLOCK_WRITER_NONRECURSIVE_INITIALIZER_NP),
it seems better to support this test case.  For a reader-preferring
implementation, it seems intuitive for programmers to expect that if one thread
has acquired a read lock, another thread will acquire a read lock eventually as
well, even in the case of concurrent writer acquisition attempts.

Recursive read-locks are allowed too for the default rwlock type, which would
be similar in that concurrent writers cannot block readers (this is already
treated correctly by the implementation).

Therefore, I think supporting this use case makes sense even if not strictly
required.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[cvs-commit at gcc dot gnu.org]

https://sourceware.org/bugzilla/show_bug.cgi?id=14958

--- Comment #8 from cvs-commit at gcc dot gnu.org <cvs-commit at gcc dot gnu.org> ---
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, master has been updated
       via  b634486d57a14b53f1cfcf739e41ddf826e51977 (commit)
       via  3c9c61febede148b79d8509e16588152d99b3774 (commit)
      from  da7f049cad943629f16cd6e533214955edfd511d (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=b634486d57a14b53f1cfcf739e41ddf826e51977

commit b634486d57a14b53f1cfcf739e41ddf826e51977
Author: Torvald Riegel <triegel@redhat.com>
Date:   Tue Apr 28 23:24:36 2015 +0200

    Fix missing wake-ups in pthread_rwlock_rdlock.

    This adds wake-ups that would be missing if assuming that for a
    non-writer-preferring rwlock, if one thread has acquired a rdlock and
    does not release it, another thread will eventually acquire a rdlock too
    despite concurrent write lock acquisition attempts.  BZ 14958 is about
    supporting this assumption.  Strictly speaking, this isn't a valid
    test case, but nonetheless worth supporting (see comment 7 of BZ 14958).

https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=3c9c61febede148b79d8509e16588152d99b3774

commit 3c9c61febede148b79d8509e16588152d99b3774
Author: Torvald Riegel <triegel@redhat.com>
Date:   Tue Apr 21 20:34:21 2015 +0200

    Fix lost wake-up when pthread_rwlock_timedrwlock times out.

    If we set up a rwlock to prefer writers (and disallow recursive rdlock
    acquisitions), then readers will block for writers that are blocked to
    acquire the lock (otherwise, readers could constantly enter and exit,
    and the writer would never get the lock).  However, the existing
    implementation did not wake such readers when the writer timed out.
    This patch adds the missing wake-up.
    There's no similar case for writers being blocked on readers.

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog                         |   22 +++++
 NEWS                              |   23 +++--
 nptl/Makefile                     |    1 +
 nptl/pthread_rwlock_rdlock.c      |   40 ++++++++-
 nptl/pthread_rwlock_timedrdlock.c |   17 ++++
 nptl/pthread_rwlock_timedwrlock.c |   26 +++++
 nptl/pthread_rwlock_tryrdlock.c   |   18 ++++-
 nptl/pthread_rwlock_unlock.c      |    5 +
 nptl/tst-rwlock15.c               |  116 +++++++++++++++++++++++
 nptl/tst-rwlock16.c               |  183 +++++++++++++++++++++++++++++++++++++
 10 files changed, 437 insertions(+), 14 deletions(-)
 create mode 100644 nptl/tst-rwlock15.c
 create mode 100644 nptl/tst-rwlock16.c

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug nptl/14958] Concurrent reader deadlock in pthread_rwlock_rdlock()

[triegel at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=14958

Torvald Riegel <triegel at redhat dot com> changed:

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

--- Comment #9 from Torvald Riegel <triegel at redhat dot com> ---
Fixed in commit b634486d57a14b53f1cfcf739e41ddf826e51977

-- 
You are receiving this mail because:
You are on the CC list for the bug.