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

[Marek Polacek <polacek at redhat dot com>]

On Fri, Sep 21, 2012 at 02:34:46PM +0200, Torvald Riegel wrote:
> +/* Overview of condvar synchronization (just considering wait/signal):
> +
> +   As shared state, we have three counters and a futex that waiting threads
> +   use to wait until waken.  __total_seq counts the number of waiting threads
> +   that have started waiting at some point in time, including those that have
> +   been already wakened.  __wakeup_seq counts the number of times that a
> +   signaling thread wakened waiting threads (if any existed previously and
> +   incremented __total_seq so that it was larger than __wakeup_seq).
> +   __woken_seq counts the number of waiters that have actually woken up due

Maybe "that have been actually..."?

> +   Those CSs all use __lock and thus execute mutually exclusive.  Waiting
> +   threads block using a futex_wait (FW) call on __futex.  Thus we can get
> +   the following execution sequence:
> +     W1, FW, (W2, FW)*, W3
> +   FW is not atomic wrt. W1-W3 or S1 (but FW is atomic wrt. S1's futex_wake
> +   call).  However, FW will only  block if __futex has the same value as

				   ^^ redundant space

> +   observed in the preceding W1 or W2 CS; therefore, we only block if a W1,FW
> +   or W2,FW pair was not interrupted by another W1 or S1.  This is important
> +   to avoid blocking based on false/stale information.  For example, if S1
> +   would not  increment __futex, then we would get a lost wake-up in

	       ^^ likewise

> +   W1, S1, FW, block forever.  Instead, if FW does not block due to __futex
> +   being changed concurrently, then it will either retry (W2) or finish (W3).
> +   We retry waiting whenever no signal has happened yet after we started
> +   waiting (val == seq) or when other waiting threads have consumed the
> +   signals (val == woken_seq).
> +
> +   POSIX requires that if a waiting thread A's W1 happens before S1, A will
> +   be considered as being "blocked" on the condvar by S1.  However, it does
> +   not require that only those threads whose W1 happens before S1 are
> +   considered to be blocked by S1; if S1 happens before W1 of thread B, B can
> +   still be considered as blocked.  S1 will then waken one of the threads

Maybe s/waken/wake/.

> +   being blocked.  Informally, executing S1 behaves like an asynchronous
> +   signal: It will be consumed eventually at some time during or after S1,
> +   and by one of the threads blocked on the condvar at that time (without any
> +   fairness guarantees).  Bug #13165 discusses this in more detail.
> +
> +   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.
> +
> +   FIXME: When __futex overflows, this can create an ABA issue for FW,
> +   potentially leading to a lost wake-up.  However, this only happens if the
> +   thread is suspended between W1/W2 and FW and during this time, other
> +   threads make UINT_MAX calls pthread_cond_wait or pthread_cond_signal.
> +   Then, this thread will not wake-up until the next spurious or real wake-up
> +   on __futex.  Alternatively,  32 pthread_cond_broadcast calls and one call

32?

Thank a lot for doing this.

	Marek