[Bug nptl/13165] pthread_cond_wait() can consume a signal that was sent before it started waiting

["triegel at redhat dot com" <sourceware-bugzilla@sourceware.org>]

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

--- Comment #22 from Torvald Riegel <triegel at redhat dot com> 2012-09-20 11:22:45 UTC ---
(In reply to comment #19)
> (In reply to comment #16)
> Sorry for the long reply. Please, bare with me, because this issue is very
> subtle and I don't know how to explain it more succinctly.

No worries.  If it would be straight-forward, we wouldn't be talking about it
here :)

> 
> First of all, let me clarify that this is a test that exposes the race, and not
> the usage scenario that I claim should be supported. The usage scenario is
> described in the bug description. Well, actually, I do claim that the scenario
> in the test should be supported too, but the scenario in the description makes
> more sense.

I think your test is good and helps to point out the issue (including,
actually, why it's not a bug).  In your comment #1, I agree on assumption 1),
but not on assumption 2). The latter (2) is not required by the standard.

> > I'm not aware of any requirement that pthread_cond_signal should block until a
> > waiter has actually woken up. (Your test case relies on it to not block, so
> > that it can send out multiple signals while holding the mutex, right?)  I'm
> > also not aware of any ordering requirement wrt. waiters (i.e., fairness).  If
> > you combine both, you will see that the behavior you observe is a valid
> > execution.
> 
> I'm not making any assumptions about the state of the waiters when
> pthread_cond_signal returns.

You do assume that only those will be associated with this particular signal
call.  We can argue that whether this is part of the state of waiters or not,
but I hope you'll agree that it's at least a property that the waiters are part
of.

> All I'm assuming is that, no matter if the
> signaling thread releases and reacquires the mutex after each sent signal or
> sends all signals without releasing the mutex, at least as many waiters as the
> number of signals will wake (eventually).

This assumption is correct, but you assume more:  That only the threads before
cond_signal returns will be considered as blocked.

So, if you have waiters W and signal S, and an execution of (W1->W2->S->W3),
then the standard requires that W1 and W2 need to be considered as blocked
threads by S.  It does not require that W3 is _not_ considered as a blocked
thread.

Informally, S is required to be ordered after W1 and W2, but it is unspecified
whether it is ordered before W3. S does not block; it is like starting an
asynchronous operation that will eventually deliver a signal.  S can return
earlier, and the earlier return can happen before W3, but that doesn't mean
anything for the delivery of the signal.

> But even if this assumption is wrong (and it's not), if you set
> releaseMutexBetweenSignals to true, the test will release the mutex after each
> sent signal. In this case the test doesn't send multiple signals while holding
> the mutex, and the problem still occurs.
> 
> As for fairness, this is not about fairness. It is also not about ordering
> between the waiters. It's about ordering between waiters and signalers.

The ordering between waiters and signalers is the first point, which I
illustrated with "signalers don't block for waiters".  After that, we have the
problem of which of the blocked threads the signal chooses to wake up, so this
becomes an ordering problem (i.e., a selection problem if applied
continuously). On an abstract level, this is a typical fairness problem.

As I pointed out, it's the combination of both these issues.

> I'm getting tired of people jumping to fairness at the first mention of
> ordering.

If you're tired, get some sleep before suggesting that the participants of this
discussion don't understand ordering.

> You could say that I'm requesting fairness if I wanted the first
> single signal to wake the waiter that blocked first. But all I'm requesting is
> for the signal to wake at least one of the waiters that started waiting before
> the signal was sent. I don't care which one of them.

That's the first wrong assumption ("before the signal" [call returned]).  If
you don't make that incorrect assumption, then it becomes a fairness issue
among classes of waiters, where the classes are defined by whether they
happened before a certain signal call.

> This is guaranteed by the standard (from the documentation of pthread_cond_wait
> and pthread_cond_signal on the opengroup site):
> 
> "The pthread_cond_signal() function shall unblock at least one of the threads
> that are blocked on the specified condition variable cond (if any threads are
> blocked on cond)."
>
> And I think the next quote makes it very clear what threads are considered to
> be blocked on the condvar at the time of the call to pthread_cond_signal():

It says that a thread must be considered blocked if the cond_wait call happened
before the signal call.  It does NOT say that ONLY those threads need to be
considered blocked.

> "That is, if another thread is able to acquire the mutex after the
> about-to-block thread has released it, then a subsequent call to
> pthread_cond_broadcast() or pthread_cond_signal() in that thread shall behave
> as if it were issued after the about-to-block thread has blocked."
> 
> In effect this means that each call to pthread_cond_signal() defines a point in
> time and all waiters (or calls to pthread_cond_wait() if you prefer) are either
> before this call, or after it. And only the ones that are before it are allowed
> to consume the signal sent by this call.

No it does not.  It only talks about what happens before (=> meaning it
implies):

waiter happens-before signaler => waiter is considered blocked

It does not say (<=> meaning being equivalent to):

waiter happens-before signaler <=> waiter is considered blocked

(In fact, if you spin the second (<=>) further, you could only expect / build
an ordering based on the mutex, but not for other kinds of enforced
happens-before order. That's not what we'd want.)

> On the other hand, the standard doesn't guarantee that there won't be spurious
> wakeups. However, glibc tries to prevent them. But the logic for this
> prevention is flawed and causes the race that this bug is about.

The term "race" here is misleading.  If there's a race, in it's how you use the
cond var and expect it to behave.  The logic would be flawed if it allowed
incorrect behavior, which it doesn't.

> So the net result is that glibc chose to provide a feature that is not
> required, but dropped a much more important feature which is actually required.
> Hence, this bug is not a fairness feature request, it is a correctness defect
> report.

No.  You assume a guarantee that isn't required by the standard.

The comment that you are asking for a fairness feature is an attempt at an
explanation for you that should point out the difference to what the standard
guarantees.  This was meant to help in this discussion.  If we want to further
discuss this, I believe this needs to focus around whether the standard
requires that certain threads must not be considered blocked.

-- 
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.