Re: [RFC] [BZ 14417] Document condvar synchronization

[Jakub Jelinek <jakub at redhat dot com>]

On Fri, Sep 21, 2012 at 02:34:46PM +0200, Torvald Riegel wrote:
> +   In turn, this allows the implementation to not have to distinguish between
> +   real and spurious wake-ups for FW, nor to have to maintain classes of
> +   waiting threads based on which S1 the respective W1s happened before.  If
> +   a signal is available (which can be determined based on the three shared
> +   counters), the first waiting thread able to wake-up (spuriously or
> +   otherwise) and acquire __lock will simply consume the signal.
> +   Example execution (A, and B are waiting threads, A:W1 happens-before S1
> +   happens-before A:W2): A:W1, A:FW, S1, B:W1, B:FW, B:FW returns (spurious),
> +   B:W3, A:FW returns (real), A:W2.  B:FW can return spuriously due to a
> +   third waiting thread executing W1 between B:W1 and B:FW, for example.

How?  B:W3 shouldn't happen, as B's seq will be __wakeup_seq after S1                                                                              
incremented it, and there are no further S1 events, so seq == __wakeup_seq                                                                         
and thus it should loop (i.e. B:W2, not B:W3).                                                                                                     
                                                                                                                                                   
Perhaps A, B, C, D waiting threads, E signalling threads holding mutex when                                                                        
calling S1, A:W1 -> B:W1 -> E:S1 -> C:W1 -> D:W1 -> E:S1 ?                                                                                         
A:W1, A:FW, B:W1, B:FW, E:S1, futex wake signals say A, C:W1, C:FW, D:W1,
D:FW,                                                                    
E:S1, futex wake signals say C, D:FW returns (spurious, e.g. it didn't sleep                                                                       
in the kernel yet and futex returned because __futex changed), D:W3 (D's seq                                                                       
is 1, __wakeup_seq 2), C:FW returns (real), C:W3 (C's seq is 1, __wakeup_seq                                                                       
2, __woken_seq at the start 1), A:FW returns (real), A:W2 (A's seq is 0,                                                                           
__wakeup_seq 2, but __woken_seq is 2 at this point).                                                                                               
So that would be what the BZ is about, one later pthread_cond_signal                                                                               
awakening more than one "new" thread if there were enough                                                                                          
pthread_cond_signal calls that should have awaken "old" threads.                                                                                   

If Austin group says that the glibc behavior is not kosher, we can always
drop all traces of __woken_seq and live with spurious wakeups, but I hope
we don't need to do that.

	Jakub