* [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up. @ 2016-12-15 22:27 Torvald Riegel 2016-12-15 22:29 ` Torvald Riegel 0 siblings, 1 reply; 10+ messages in thread From: Torvald Riegel @ 2016-12-15 22:27 UTC (permalink / raw) To: GLIBC Devel; +Cc: vl, Michael Adam, Rich Felker See patch for a description. Tested on x86_64-linux with our tests and the test case from the original bug report: https://bugzilla.redhat.com/show_bug.cgi?id=1401665 OK? I'm sending this minimal patch first to have something that's easy to backport. I'll send further such patches for any other bugs I can find for which a simple backport is possible. I then plan to follow this up with a general clean-up of robust mutexes including proper documentation of the concurrent code. There's another bug that's probably just a glibc problem, one that is a glibc problem but seems to happen to work currently (at least on x86_64), one bug that is just in kernel code, and there's also a general design flaw in the glibc/kernel synchronization algorithm that prevents us from guaranteeing the mutex destruction requirements. I'll work on the latter two subsequently and crosspost to LKML. ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up. 2016-12-15 22:27 [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up Torvald Riegel @ 2016-12-15 22:29 ` Torvald Riegel 2016-12-16 14:11 ` Florian Weimer 2016-12-19 18:20 ` Carlos O'Donell 0 siblings, 2 replies; 10+ messages in thread From: Torvald Riegel @ 2016-12-15 22:29 UTC (permalink / raw) To: GLIBC Devel; +Cc: vl, Michael Adam, Rich Felker [-- Attachment #1: Type: text/plain, Size: 273 bytes --] On Thu, 2016-12-15 at 23:27 +0100, Torvald Riegel wrote: > See patch for a description. > > Tested on x86_64-linux with our tests and the test case from the > original bug report: https://bugzilla.redhat.com/show_bug.cgi?id=1401665 > > OK? Now with an attached patch... [-- Attachment #2: robust-mutex-lwu.patch --] [-- Type: text/x-patch, Size: 4364 bytes --] commit 74be3b28d962a5a6d2eeff51b93d61ddf91e2d49 Author: Torvald Riegel <triegel@redhat.com> Date: Thu Dec 15 16:06:28 2016 +0100 Robust mutexes: Fix lost wake-up. Assume that Thread 1 waits to acquire a robust mutex using futexes to block (and thus sets the FUTEX_WAITERS flag), and is unblocked when this mutex is released. If Thread 2 concurrently acquires the lock and is killed, Thread 1 can recover from the died owner but fail to restore the FUTEX_WAITERS flag. This can lead to a Thread 3 that also blocked using futexes at the same time as Thread 1 to not get woken up because FUTEX_WAITERS is not set anymore. The fix for this is to ensure that we continue to preserve the FUTEX_WAITERS flag whenever we may have set it or shared it with another thread. This is the same requirement as in the algorithm for normal mutexes, only that the robust mutexes need additional handling for died owners and thus preserving the FUTEX_WAITERS flag cannot be done just in the futex slowpath code. [BZ #20973] * nptl/pthread_mutex_lock.c (__pthread_mutex_lock_full): Fix lost wake-up in robust mutexes. * nptl/pthread_mutex_timedlock.c (pthread_mutex_timedlock): Likewise. diff --git a/nptl/pthread_mutex_lock.c b/nptl/pthread_mutex_lock.c index bdfa529..01ac75e 100644 --- a/nptl/pthread_mutex_lock.c +++ b/nptl/pthread_mutex_lock.c @@ -182,6 +182,11 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) &mutex->__data.__list.__next); oldval = mutex->__data.__lock; + /* This is set to FUTEX_WAITERS iff we might have shared the + FUTEX_WAITERS flag with other threads, and therefore need to keep it + set to avoid lost wake-ups. We have the same requirement in the + simple mutex algorithm. */ + unsigned int assume_other_futex_waiters = 0; do { again: @@ -190,9 +195,9 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) /* The previous owner died. Try locking the mutex. */ int newval = id; #ifdef NO_INCR - newval |= FUTEX_WAITERS; + newval |= FUTEX_WAITERS | assume_other_futex_waiters; #else - newval |= (oldval & FUTEX_WAITERS); + newval |= (oldval & FUTEX_WAITERS) | assume_other_futex_waiters; #endif newval @@ -253,7 +258,11 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) } } - oldval = LLL_ROBUST_MUTEX_LOCK (mutex, id); + oldval = LLL_ROBUST_MUTEX_LOCK (mutex, + id | assume_other_futex_waiters); + /* See above. We set FUTEX_WAITERS and might have shared this flag + with other threads; thus, we need to preserve it. */ + assume_other_futex_waiters = FUTEX_WAITERS; if (__builtin_expect (mutex->__data.__owner == PTHREAD_MUTEX_NOTRECOVERABLE, 0)) diff --git a/nptl/pthread_mutex_timedlock.c b/nptl/pthread_mutex_timedlock.c index 07f0901..21e9eea 100644 --- a/nptl/pthread_mutex_timedlock.c +++ b/nptl/pthread_mutex_timedlock.c @@ -142,13 +142,19 @@ pthread_mutex_timedlock (pthread_mutex_t *mutex, &mutex->__data.__list.__next); oldval = mutex->__data.__lock; + /* This is set to FUTEX_WAITERS iff we might have shared the + FUTEX_WAITERS flag with other threads, and therefore need to keep it + set to avoid lost wake-ups. We have the same requirement in the + simple mutex algorithm. */ + unsigned int assume_other_futex_waiters = 0; do { again: if ((oldval & FUTEX_OWNER_DIED) != 0) { /* The previous owner died. Try locking the mutex. */ - int newval = id | (oldval & FUTEX_WAITERS); + int newval = id | (oldval & FUTEX_WAITERS) + | assume_other_futex_waiters; newval = atomic_compare_and_exchange_val_acq (&mutex->__data.__lock, @@ -203,8 +209,12 @@ pthread_mutex_timedlock (pthread_mutex_t *mutex, } } - result = lll_robust_timedlock (mutex->__data.__lock, abstime, id, + result = lll_robust_timedlock (mutex->__data.__lock, abstime, + id | assume_other_futex_waiters, PTHREAD_ROBUST_MUTEX_PSHARED (mutex)); + /* See above. We set FUTEX_WAITERS and might have shared this flag + with other threads; thus, we need to preserve it. */ + assume_other_futex_waiters = FUTEX_WAITERS; if (__builtin_expect (mutex->__data.__owner == PTHREAD_MUTEX_NOTRECOVERABLE, 0)) ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up. 2016-12-15 22:29 ` Torvald Riegel @ 2016-12-16 14:11 ` Florian Weimer 2016-12-16 14:45 ` Volker Lendecke 2016-12-16 22:13 ` Torvald Riegel 2016-12-19 18:20 ` Carlos O'Donell 1 sibling, 2 replies; 10+ messages in thread From: Florian Weimer @ 2016-12-16 14:11 UTC (permalink / raw) To: Torvald Riegel, GLIBC Devel; +Cc: vl, Michael Adam, Rich Felker On 12/15/2016 11:29 PM, Torvald Riegel wrote: > Assume that Thread 1 waits to acquire a robust mutex using futexes to > block (and thus sets the FUTEX_WAITERS flag), and is unblocked when this > mutex is released. If Thread 2 concurrently acquires the lock and is > killed, Thread 1 can recover from the died owner but fail to restore the > FUTEX_WAITERS flag. This can lead to a Thread 3 that also blocked using > futexes at the same time as Thread 1 to not get woken up because > FUTEX_WAITERS is not set anymore. > > The fix for this is to ensure that we continue to preserve the > FUTEX_WAITERS flag whenever we may have set it or shared it with another > thread. This is the same requirement as in the algorithm for normal > mutexes, only that the robust mutexes need additional handling for died > owners and thus preserving the FUTEX_WAITERS flag cannot be done just in > the futex slowpath code. Description and change look good to me in general. > [BZ #20973] > * nptl/pthread_mutex_lock.c (__pthread_mutex_lock_full): Fix lost > wake-up in robust mutexes. > * nptl/pthread_mutex_timedlock.c (pthread_mutex_timedlock): Likewise. > > diff --git a/nptl/pthread_mutex_lock.c b/nptl/pthread_mutex_lock.c > index bdfa529..01ac75e 100644 > --- a/nptl/pthread_mutex_lock.c > +++ b/nptl/pthread_mutex_lock.c > @@ -182,6 +182,11 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) > &mutex->__data.__list.__next); > > oldval = mutex->__data.__lock; > + /* This is set to FUTEX_WAITERS iff we might have shared the âiffâ doesn't seem to be correct here because it's not an exact equivalence, âifâ is sufficient. > + FUTEX_WAITERS flag with other threads, and therefore need to keep it > + set to avoid lost wake-ups. We have the same requirement in the > + simple mutex algorithm. */ > + unsigned int assume_other_futex_waiters = 0; > do > { > again: > @@ -190,9 +195,9 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) > /* The previous owner died. Try locking the mutex. */ > int newval = id; > #ifdef NO_INCR > - newval |= FUTEX_WAITERS; > + newval |= FUTEX_WAITERS | assume_other_futex_waiters; > #else > - newval |= (oldval & FUTEX_WAITERS); > + newval |= (oldval & FUTEX_WAITERS) | assume_other_futex_waiters; > #endif The NO_INCR change is quite confusing. Perhaps drop it and add a comment? VL, what is the copyright status of your test case? Thanks, Florian ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up. 2016-12-16 14:11 ` Florian Weimer @ 2016-12-16 14:45 ` Volker Lendecke [not found] ` <CAJ+X7mT1cU1_2ON2JZM9oYMP_cak734tkf+PZJeo4MZg1i4gmw@mail.gmail.com> 2016-12-16 22:13 ` Torvald Riegel 1 sibling, 1 reply; 10+ messages in thread From: Volker Lendecke @ 2016-12-16 14:45 UTC (permalink / raw) To: Florian Weimer Cc: amitay, Torvald Riegel, GLIBC Devel, Michael Adam, Rich Felker On Fri, Dec 16, 2016 at 03:11:12PM +0100, Florian Weimer wrote: > VL, what is the copyright status of your test case? This is not really mine, it was written by Amitay Isaacs <amitay@gmail.com>. Amitay does a lot of Samba and ctdb coding, so I would expect this to be his (C) under GPLv3+. If you need that as a regression under something more liberal, while I can't speak for him, I would expect this not to be a problem. Amitay? Volker ^ permalink raw reply [flat|nested] 10+ messages in thread
[parent not found: <CAJ+X7mT1cU1_2ON2JZM9oYMP_cak734tkf+PZJeo4MZg1i4gmw@mail.gmail.com>]
* Re: [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up. [not found] ` <CAJ+X7mT1cU1_2ON2JZM9oYMP_cak734tkf+PZJeo4MZg1i4gmw@mail.gmail.com> @ 2016-12-19 17:15 ` Florian Weimer 0 siblings, 0 replies; 10+ messages in thread From: Florian Weimer @ 2016-12-19 17:15 UTC (permalink / raw) To: Amitay Isaacs, Volker Lendecke Cc: Torvald Riegel, GLIBC Devel, Michael Adam, Rich Felker On 12/17/2016 05:52 AM, Amitay Isaacs wrote: > On Sat, Dec 17, 2016 at 1:44 AM, Volker Lendecke <vl@samba.org> wrote: > >> On Fri, Dec 16, 2016 at 03:11:12PM +0100, Florian Weimer wrote: >>> VL, what is the copyright status of your test case? >> >> This is not really mine, it was written by Amitay Isaacs >> <amitay@gmail.com>. Amitay does a lot of Samba and ctdb coding, so I >> would expect this to be his (C) under GPLv3+. If you need that as a >> regression under something more liberal, while I can't speak for him, >> I would expect this not to be a problem. >> >> > Yes, the test has GPLv3+ license and my copyright. > > Copyright (C) Amitay Isaacs 2016 > > Is there any particular reason for asking this? We'd like to include it as a test case in glibc, but that requires a copyright assignment, which is usually not worth the trouble for such a change. Thanks, Florian ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up. 2016-12-16 14:11 ` Florian Weimer 2016-12-16 14:45 ` Volker Lendecke @ 2016-12-16 22:13 ` Torvald Riegel 2016-12-19 19:47 ` Florian Weimer 1 sibling, 1 reply; 10+ messages in thread From: Torvald Riegel @ 2016-12-16 22:13 UTC (permalink / raw) To: Florian Weimer; +Cc: GLIBC Devel, vl, Michael Adam, Rich Felker On Fri, 2016-12-16 at 15:11 +0100, Florian Weimer wrote: > On 12/15/2016 11:29 PM, Torvald Riegel wrote: > > diff --git a/nptl/pthread_mutex_lock.c b/nptl/pthread_mutex_lock.c > > index bdfa529..01ac75e 100644 > > --- a/nptl/pthread_mutex_lock.c > > +++ b/nptl/pthread_mutex_lock.c > > @@ -182,6 +182,11 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) > > &mutex->__data.__list.__next); > > > > oldval = mutex->__data.__lock; > > + /* This is set to FUTEX_WAITERS iff we might have shared the > > âiffâ doesn't seem to be correct here because it's not an exact > equivalence, âifâ is sufficient. No, I think the iff is correct. We do only set it if we may have shared the flag. > > @@ -190,9 +195,9 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) > > /* The previous owner died. Try locking the mutex. */ > > int newval = id; > > #ifdef NO_INCR > > - newval |= FUTEX_WAITERS; > > + newval |= FUTEX_WAITERS | assume_other_futex_waiters; > > #else > > - newval |= (oldval & FUTEX_WAITERS); > > + newval |= (oldval & FUTEX_WAITERS) | assume_other_futex_waiters; > > #endif > > The NO_INCR change is quite confusing. Perhaps drop it and add a comment? Yes. > VL, what is the copyright status of your test case? So, I'll wait a little to see how the test case question resolved, and then commit it with the one change above either with or without a test case. If anyone objects to that, please speak up. ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up. 2016-12-16 22:13 ` Torvald Riegel @ 2016-12-19 19:47 ` Florian Weimer 2016-12-19 20:30 ` Carlos O'Donell 2016-12-20 15:03 ` Torvald Riegel 0 siblings, 2 replies; 10+ messages in thread From: Florian Weimer @ 2016-12-19 19:47 UTC (permalink / raw) To: Torvald Riegel Cc: GNU C Library, vl, Michael Adam, dalias@libc.org >> Rich Felker On 12/16/2016 11:13 PM, Torvald Riegel wrote: > On Fri, 2016-12-16 at 15:11 +0100, Florian Weimer wrote: >> On 12/15/2016 11:29 PM, Torvald Riegel wrote: >>> diff --git a/nptl/pthread_mutex_lock.c b/nptl/pthread_mutex_lock.c >>> index bdfa529..01ac75e 100644 >>> --- a/nptl/pthread_mutex_lock.c >>> +++ b/nptl/pthread_mutex_lock.c >>> @@ -182,6 +182,11 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) >>> &mutex->__data.__list.__next); >>> >>> oldval = mutex->__data.__lock; >>> + /* This is set to FUTEX_WAITERS iff we might have shared the >> >> âiffâ doesn't seem to be correct here because it's not an exact >> equivalence, âifâ is sufficient. > > No, I think the iff is correct. We do only set it if we may have shared > the flag. Then please change it to âThis is set to FUTEX_WAITERS iff we have sharedâ (i.e. drop the âmightâ). Based on the source code, I'm still not sure if this is an exact equivalence. The part which confuses me is the unconditional assignment assume_other_futex_waiters = FUTEX_WAITERS further below. But I think lll_robust_lock returns 0 if we did not share FUTEX_WAITERS, and the code never retries with the assigned assume_other_futex_waiters value, ensuring the equivalence. I think it would be clearer if you switched from a do-while loop to a loop with an exit condition in the middle, right after the call to lll_robust_lock. Putting the FUTEX_WAITERS into the ID passed to lll_robust_lock is a violation of its precondition documented in sysdeps/nptl/lowlevellock.h, so please update the comment. Thanks, Florian ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up. 2016-12-19 19:47 ` Florian Weimer @ 2016-12-19 20:30 ` Carlos O'Donell 2016-12-20 15:03 ` Torvald Riegel 1 sibling, 0 replies; 10+ messages in thread From: Carlos O'Donell @ 2016-12-19 20:30 UTC (permalink / raw) To: Florian Weimer, Torvald Riegel Cc: GNU C Library, vl, Michael Adam, dalias@libc.org >> Rich Felker On 12/19/2016 02:47 PM, Florian Weimer wrote: > On 12/16/2016 11:13 PM, Torvald Riegel wrote: >> On Fri, 2016-12-16 at 15:11 +0100, Florian Weimer wrote: >>> On 12/15/2016 11:29 PM, Torvald Riegel wrote: >>>> diff --git a/nptl/pthread_mutex_lock.c >>>> b/nptl/pthread_mutex_lock.c index bdfa529..01ac75e 100644 --- >>>> a/nptl/pthread_mutex_lock.c +++ b/nptl/pthread_mutex_lock.c @@ >>>> -182,6 +182,11 @@ __pthread_mutex_lock_full (pthread_mutex_t >>>> *mutex) &mutex->__data.__list.__next); >>>> >>>> oldval = mutex->__data.__lock; + /* This is set to >>>> FUTEX_WAITERS iff we might have shared the >>> >>> âiffâ doesn't seem to be correct here because it's not an exact >>> equivalence, âifâ is sufficient. >> >> No, I think the iff is correct. We do only set it if we may have >> shared the flag. > > Then please change it to âThis is set to FUTEX_WAITERS iff we have > sharedâ (i.e. drop the âmightâ). Based on the source code, I'm still > not sure if this is an exact equivalence. OK. I agree I'm also not sure it's an exact equivalence, I'd also probably say "This _will_ be set to..." since technically we share FUTEX_WAITERS in the inner __lll_robust_lock_wait before we come back and set assume_other_futex_waiters. > The part which confuses me is the unconditional assignment > assume_other_futex_waiters = FUTEX_WAITERS further below. It _must_ be assigned unconditionally exactly because of the problem outlined in this issue (and expanded in my review). Because the value of FUTEX_WAITERS is shared, and because of the recovery semantics of the mutex, there is a path through __lll_robust_lock_wait which needs to avoid the loss of FUTEX_WAITERS (and the required wakeup which happens on unlock). Because the unlock and wakeup by T0 clears the FUTEX_WAITERS flag, and you don't know if other threads queued up after you, you must assume the worst and do the wakeup also. I don't see a way to avoid the spurious wakeup. > But I > think lll_robust_lock returns 0 if we did not share FUTEX_WAITERS, > and the code never retries with the assigned > assume_other_futex_waiters value, ensuring the equivalence. I think > it would be clearer if you switched from a do-while loop to a loop > with an exit condition in the middle, right after the call to > lll_robust_lock. Yes, this is a case where assume_other_futex_waiters is zero and we have potentially shared FUTEX_WAITERS via the inner __lll_robust_lock_wait code, so it would appear this example contradicts using "iff". I don't know about restructuring this loop. I'd have to see a concrete example of the cleanup, and I think I'd like to avoid such a cleanup to keep this patch minimal for now. Future cleanup could happen in a lot of ways. > Putting the FUTEX_WAITERS into the ID passed to lll_robust_lock is a > violation of its precondition documented in > sysdeps/nptl/lowlevellock.h, so please update the comment. The precondition is a bit loose about this, but I agree the language could be tightened up. -- Cheers, Carlos. ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up. 2016-12-19 19:47 ` Florian Weimer 2016-12-19 20:30 ` Carlos O'Donell @ 2016-12-20 15:03 ` Torvald Riegel 1 sibling, 0 replies; 10+ messages in thread From: Torvald Riegel @ 2016-12-20 15:03 UTC (permalink / raw) To: Florian Weimer Cc: GNU C Library, vl, Michael Adam, dalias@libc.org >> Rich Felker On Mon, 2016-12-19 at 20:47 +0100, Florian Weimer wrote: > On 12/16/2016 11:13 PM, Torvald Riegel wrote: > > On Fri, 2016-12-16 at 15:11 +0100, Florian Weimer wrote: > >> On 12/15/2016 11:29 PM, Torvald Riegel wrote: > >>> diff --git a/nptl/pthread_mutex_lock.c b/nptl/pthread_mutex_lock.c > >>> index bdfa529..01ac75e 100644 > >>> --- a/nptl/pthread_mutex_lock.c > >>> +++ b/nptl/pthread_mutex_lock.c > >>> @@ -182,6 +182,11 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) > >>> &mutex->__data.__list.__next); > >>> > >>> oldval = mutex->__data.__lock; > >>> + /* This is set to FUTEX_WAITERS iff we might have shared the > >> > >> âiffâ doesn't seem to be correct here because it's not an exact > >> equivalence, âifâ is sufficient. > > > > No, I think the iff is correct. We do only set it if we may have shared > > the flag. > > Then please change it to âThis is set to FUTEX_WAITERS iff we have > sharedâ (i.e. drop the âmightâ). Based on the source code, I'm still > not sure if this is an exact equivalence. I still think the original comment is correct. When we start, we will not have shared, so assume_... starts as false. After we have set F_W, we *might* have shared, so we set assume_... to true. You're right that we might have just succeeded to acquire the lock, and then we might not have shared, but then we're not using assume_... anymore. > The part which confuses me is the unconditional assignment > assume_other_futex_waiters = FUTEX_WAITERS further below. But I think > lll_robust_lock returns 0 if we did not share FUTEX_WAITERS, and the > code never retries with the assigned assume_other_futex_waiters value, > ensuring the equivalence. I think it would be clearer if you switched > from a do-while loop to a loop with an exit condition in the middle, > right after the call to lll_robust_lock. > > Putting the FUTEX_WAITERS into the ID passed to lll_robust_lock is a > violation of its precondition documented in sysdeps/nptl/lowlevellock.h, > so please update the comment. I've already committed the patch after what sounded like approval. As I've said before, I plan to follow this up with a cleanup of the whole robust mutex code. In that cleanup patch we can fine-tune the documentation. ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up. 2016-12-15 22:29 ` Torvald Riegel 2016-12-16 14:11 ` Florian Weimer @ 2016-12-19 18:20 ` Carlos O'Donell 1 sibling, 0 replies; 10+ messages in thread From: Carlos O'Donell @ 2016-12-19 18:20 UTC (permalink / raw) To: Torvald Riegel, GLIBC Devel; +Cc: vl, Michael Adam, Rich Felker On 12/15/2016 05:29 PM, Torvald Riegel wrote: > On Thu, 2016-12-15 at 23:27 +0100, Torvald Riegel wrote: >> See patch for a description. >> >> Tested on x86_64-linux with our tests and the test case from the >> original bug report: https://bugzilla.redhat.com/show_bug.cgi?id=1401665 >> >> OK? This looks good to me. Detailed review below. > Now with an attached patch... > > > robust-mutex-lwu.patch > > > commit 74be3b28d962a5a6d2eeff51b93d61ddf91e2d49 > Author: Torvald Riegel <triegel@redhat.com> > Date: Thu Dec 15 16:06:28 2016 +0100 > > Robust mutexes: Fix lost wake-up. > > Assume that Thread 1 waits to acquire a robust mutex using futexes to > block (and thus sets the FUTEX_WAITERS flag), and is unblocked when this > mutex is released. If Thread 2 concurrently acquires the lock and is > killed, Thread 1 can recover from the died owner but fail to restore the > FUTEX_WAITERS flag. This can lead to a Thread 3 that also blocked using > futexes at the same time as Thread 1 to not get woken up because > FUTEX_WAITERS is not set anymore. Just to reiterate: T0 T1 T2 T3 | | | | LOCK | | | | WAIT | | | s | WAIT UNLOCK s | s WAKE AWAKE | s | | LOCK s | | DIES s | LOCK s | UNLOCK s | NOWAKE * At the point T0 unlocks and wakes T1 we have both T1 and T2 attempting to acquire the same lock which has a value of 0 (no waiters since the shared waiter flag was cleared). If T2 take the lock (no FUTEX_WAITERS set) and dies, the futex value is going to be reset to FUTEX_OWNER_DIED by the kernel (note that the kernel preserves FUTEX_WAITERS, but it was not set in this case because T0 unlocked). In the case of T1, the following loop is executing 27 int 28 __lll_robust_lock_wait (int *futex, int private) 29 { 37 do 38 { 39 /* If the owner died, return the present value of the futex. */ 40 if (__glibc_unlikely (oldval & FUTEX_OWNER_DIED)) 41 return oldval; 42 43 /* Try to put the lock into state 'acquired, possibly with waiters'. */ 44 int newval = oldval | FUTEX_WAITERS; 45 if (oldval != newval 46 && atomic_compare_and_exchange_bool_acq (futex, newval, oldval)) 47 continue; 48 49 /* If *futex == 2, wait until woken. */ 50 lll_futex_wait (futex, newval, private); We have just been woken. T2 acquires the lock, dies, and the lock is cleaned up. Nobody is waiting on the lock. 52 try: 53 ; 54 } 55 while ((oldval = atomic_compare_and_exchange_val_acq (futex, 56 tid | FUTEX_WAITERS, 57 0)) != 0); This fails because the value is not 0 it's FUTEX_OWNER_DIED. We loop up to the top and check FUTEX_OWNER_DIED, which matches, and then we return to the higher-level code which has now lost FUTEX_WAITERS. At this point T3 has lost the wakeup it needs to continue with the lock because T1 has "forgotten" there were waiters. > The fix for this is to ensure that we continue to preserve the > FUTEX_WAITERS flag whenever we may have set it or shared it with another > thread. This is the same requirement as in the algorithm for normal > mutexes, only that the robust mutexes need additional handling for died > owners and thus preserving the FUTEX_WAITERS flag cannot be done just in > the futex slowpath code. Agreed. Just highlighting from above: 39 /* If the owner died, return the present value of the futex. */ 40 if (__glibc_unlikely (oldval & FUTEX_OWNER_DIED)) 41 return oldval; Here we return the shared oldval with FUTEX_WAITERS lost. I struggled with the possibility of a simpler fix that just changed the returned oldval, but you correctly pointed out to me that such a fix breaks the abstraction and algorithms that consider oldval to be the previously read value from memory. Therefore I agree that this needs to be handled at a higher level which also has to handle re-inserting FUTEX_WAITERS as required as is done here. With your patch the only two lock patch we have are now covered and correctly re-add FUTEX_WAITERS if we'd had a slowpath wait that might potentially have lost the FUTEX_WAITERS flag due to a concurrent lock/death sequence. I don't immediately see any other broken paths where FUTEX_WAITERS can be dropped and the wakeup lost. > [BZ #20973] > * nptl/pthread_mutex_lock.c (__pthread_mutex_lock_full): Fix lost > wake-up in robust mutexes. > * nptl/pthread_mutex_timedlock.c (pthread_mutex_timedlock): Likewise. > > diff --git a/nptl/pthread_mutex_lock.c b/nptl/pthread_mutex_lock.c > index bdfa529..01ac75e 100644 > --- a/nptl/pthread_mutex_lock.c > +++ b/nptl/pthread_mutex_lock.c > @@ -182,6 +182,11 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) > &mutex->__data.__list.__next); > > oldval = mutex->__data.__lock; > + /* This is set to FUTEX_WAITERS iff we might have shared the > + FUTEX_WAITERS flag with other threads, and therefore need to keep it > + set to avoid lost wake-ups. We have the same requirement in the > + simple mutex algorithm. */ > + unsigned int assume_other_futex_waiters = 0; OK. > do > { > again: > @@ -190,9 +195,9 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) > /* The previous owner died. Try locking the mutex. */ > int newval = id; > #ifdef NO_INCR > - newval |= FUTEX_WAITERS; > + newval |= FUTEX_WAITERS | assume_other_futex_waiters; > #else > - newval |= (oldval & FUTEX_WAITERS); > + newval |= (oldval & FUTEX_WAITERS) | assume_other_futex_waiters; OK. > #endif > > newval > @@ -253,7 +258,11 @@ __pthread_mutex_lock_full (pthread_mutex_t *mutex) > } > } > > - oldval = LLL_ROBUST_MUTEX_LOCK (mutex, id); > + oldval = LLL_ROBUST_MUTEX_LOCK (mutex, > + id | assume_other_futex_waiters); > + /* See above. We set FUTEX_WAITERS and might have shared this flag > + with other threads; thus, we need to preserve it. */ > + assume_other_futex_waiters = FUTEX_WAITERS; OK. > > if (__builtin_expect (mutex->__data.__owner > == PTHREAD_MUTEX_NOTRECOVERABLE, 0)) > diff --git a/nptl/pthread_mutex_timedlock.c b/nptl/pthread_mutex_timedlock.c > index 07f0901..21e9eea 100644 > --- a/nptl/pthread_mutex_timedlock.c > +++ b/nptl/pthread_mutex_timedlock.c > @@ -142,13 +142,19 @@ pthread_mutex_timedlock (pthread_mutex_t *mutex, > &mutex->__data.__list.__next); > > oldval = mutex->__data.__lock; > + /* This is set to FUTEX_WAITERS iff we might have shared the > + FUTEX_WAITERS flag with other threads, and therefore need to keep it > + set to avoid lost wake-ups. We have the same requirement in the > + simple mutex algorithm. */ > + unsigned int assume_other_futex_waiters = 0; OK. > do > { > again: > if ((oldval & FUTEX_OWNER_DIED) != 0) > { > /* The previous owner died. Try locking the mutex. */ > - int newval = id | (oldval & FUTEX_WAITERS); > + int newval = id | (oldval & FUTEX_WAITERS) > + | assume_other_futex_waiters; OK. > > newval > = atomic_compare_and_exchange_val_acq (&mutex->__data.__lock, > @@ -203,8 +209,12 @@ pthread_mutex_timedlock (pthread_mutex_t *mutex, > } > } > > - result = lll_robust_timedlock (mutex->__data.__lock, abstime, id, > + result = lll_robust_timedlock (mutex->__data.__lock, abstime, > + id | assume_other_futex_waiters, > PTHREAD_ROBUST_MUTEX_PSHARED (mutex)); > + /* See above. We set FUTEX_WAITERS and might have shared this flag > + with other threads; thus, we need to preserve it. */ > + assume_other_futex_waiters = FUTEX_WAITERS; OK. > > if (__builtin_expect (mutex->__data.__owner > == PTHREAD_MUTEX_NOTRECOVERABLE, 0)) -- Cheers, Carlos. ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2016-12-20 15:03 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2016-12-15 22:27 [PATCH][BZ #20973] Robust mutexes: Fix lost wake-up Torvald Riegel 2016-12-15 22:29 ` Torvald Riegel 2016-12-16 14:11 ` Florian Weimer 2016-12-16 14:45 ` Volker Lendecke [not found] ` <CAJ+X7mT1cU1_2ON2JZM9oYMP_cak734tkf+PZJeo4MZg1i4gmw@mail.gmail.com> 2016-12-19 17:15 ` Florian Weimer 2016-12-16 22:13 ` Torvald Riegel 2016-12-19 19:47 ` Florian Weimer 2016-12-19 20:30 ` Carlos O'Donell 2016-12-20 15:03 ` Torvald Riegel 2016-12-19 18:20 ` Carlos O'Donell
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).