This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] New condvar implementation that provides stronger ordering guarantees.
- From: Torvald Riegel <triegel at redhat dot com>
- To: Rich Felker <dalias at libc dot org>
- Cc: GLIBC Devel <libc-alpha at sourceware dot org>, Marcus Shawcroft <marcus dot shawcroft at gmail dot com>, "Joseph S. Myers" <joseph at codesourcery dot com>, Richard Henderson <rth at redhat dot com>, "Carlos O'Donell" <codonell at redhat dot com>, Mike Frysinger <vapier at gentoo dot org>, David Holsgrove <david dot holsgrove at xilinx dot com>, Chung-Lin Tang <chunglin_tang at mentor dot com>, Adhemerval Zanella <azanella at linux dot vnet dot ibm dot com>, Andreas Krebbel <krebbel at linux dot ibm dot com>, Kaz Kojima <kkojima at rr dot iij4u dot or dot jp>, Chris Metcalf <cmetcalf at tilera dot com>, David Miller <davem at davemloft dot net>, Darren Hart <dvhart at infradead dot org>
- Date: Sun, 22 Feb 2015 15:07:50 +0100
- Subject: Re: [PATCH] New condvar implementation that provides stronger ordering guarantees.
- Authentication-results: sourceware.org; auth=none
- References: <1424456307 dot 20941 dot 122 dot camel at triegel dot csb> <20150220192023 dot GX23507 at brightrain dot aerifal dot cx>
On Fri, 2015-02-20 at 14:20 -0500, Rich Felker wrote:
> On Fri, Feb 20, 2015 at 07:18:27PM +0100, Torvald Riegel wrote:
> > There's another issue specific to condvars: ABA issues on the underlying
> > futexes. Unlike mutexes that have just three states, or semaphores that
> > have no tokens or a limited number of them, the state of a condvar is
> > the *order* of the waiters. With a semaphore, we can grab whenever
> > there is a token, and block in the futex_wait when there is none. With
> > condvars, a waiter must not block if there had been more
> > signals/broadcasts than waiters before it (ie, ordering matters).
>
> I don't quite follow your claim that the order is part of the state.
> My interpretation is that the state is merely the _set_ of waiters at
> the instant of signal/broadcast.
What I mean is that because a futex_wait can execute long after the
respective waiter started to block logically, the state needs to
"remember" which waiters started to block in the past, so that when new
waiters arrive and block more recently, it isn't lost that the old
waiters should get woken up.
I agree that the requirements regarding which waiters should be woken
are about a *set* of eligible waiters (ie, those waiters that blocked
before the resp. signal/broadcast). One could model the state as the
state of waiters that are still blocked, and remove from this set on
signal/broadcast. However, to avoid ABA in this scheme, this would mean
that waiters have to reserve a "slot" in this set for the time they
start to block until they have stopped blocking. That would mean
additional synchronization, and perhaps some waiters blocking others
(eg, due to having just 32b for the futex word).
What I was trying to highlight wrt the differences to mutexes was really
that the order of waiters and signal/broadcast matters, and that it's
not sufficient to model it as whether a signal is available to wake
*some* waiter or not. Instead, we need to select a representation of
the order of waiters and signals, so that we don't loose information
necessary to fulfill the who's-eligible-for-wake-up requirements.
Abstractly, the requirements regarding wake-up on futexes are weaker
than on condvars. So we need to do additional stuff to make it work for
condvars based on futexes. It's different with mutexes, which have the
same weaker requirements regarding which thread is allowed to grab the
lock (unless one would want to build a lock that hands out ownership in
FIFO order to threads...).
> But perhaps thinking of order as
> state makes sense if you're looking at this from the standpoint of a
> weakly ordered memory model where such an "instant" does not make
> sense without either forced serialization or order-as-data. Is this
> what you mean?
>
> > This algorithm satisfies the equivalent of the strong mutex destruction
> > guarantee. However, unlike mutexes, because of spurious wake-ups being
> > allowed a correct program has to effectively ensure that destruction
> > happens after signals/broadcast calls return. Thus, the destruction
> > requirement in POSIX is not as restrictive as with semaphores, but we
> > still need to take care.
>
> If the mutex is held when changing the state on which the predicate
> depends and signaling, it's possible for a woken waiter to determine
> whether a subsequent signal is possible simply from observing the
> predicate.
It the predicate change and the signal are in the same critical section,
I agree that the waiter can safely determine that it can do destruction
subsequently. In this case, the program implicitly ensures that signal
happens-before destruction (due to how the mutex is used).
> So I think there are some situations where destruction
> after pthread_cond_wait returns makes sense, but I don't think they're
> a problem.
Agreed. The new condvar takes care of this.
> If the signal is made while the mutex is not held, there is absolutely
> no way for the woken thread to determine whether the call to signal
> has already been made or not, so I agree that it's invalid to destroy
> in this case.
Agreed.