AW: New private cond var design

[Jens Gustedt <jens.gustedt@inria.fr>]

Hi,
I definitively like this idea of the list items on the stack.
Some thoughts:

Threads can leave the list prematurely, so we need a doubly linked list.
Threads that are inside the wait function can be organized that they hold the mutex,
this should avoid a lot of race trouble maintaining the list.
Broadcast can be done in O(1) when delegating the wake up to the threads on the list one after another. These have to acquire the mutex anyhow, one at a time.
Jens

:: INRIA Nancy Grand Est :: http://www.loria.fr/~gustedt/   ::
:: AlGorille ::::::::::::::: office Nancy : +33 383593090   ::
:: ICube :::::::::::::: office Strasbourg : +33 368854536   ::
:: ::::::::::::::::::::::::::: gsm France : +33 651400183   ::
:: :::::::::::::::::::: gsm international : +49 15737185122 ::


----- Rich Felker <dalias@libc.org> schrieb:
> The current cv bug reported by Jens occurs when a cv is reused with a
> new mutex before all the former-waiters from the previous mutex have
> woken up and decremented themselves from the waiter count. In this
> case, they can't know whether to decrement the in-cv waiter count or
> the in-mutex waiter count, and thereby end up corrupting these counts.
> 
> Jens' proposed solution tracked "instances" via dynamically allocated,
> reference-counted objects. I finally think I have a solution which
> avoids dynamic allocation: representing the "instance" as a
> doubly-linked-list of automatic objects on the stack of each waiter.
> 
> The cv object itself needs a single pointer to the head of the current
> instance. This pointer is set by the first waiter on an instance.
> Subsequent waiters which arrive when it's already set can check that
> the mutex argument is the same; if not, this is an error. The pointer
> is cleared when the last (formal) waiter is removed by the signal or
> broadcast operation.
> 
> Storing this list eliminates the need to keep a waiter count. The
> length of the linked list itself is the number of waiters which need
> to be moved to the mutex on broadcast. This requires an O(n) walk of
> the list at broadcast time, but that's really a non-issue since the
> kernel is already doing a much more expensive O(n) walk of the futex
> waiter list anyway.
> 
> The list also allows us to eliminate the sequence number wrapping
> issue (sadly, only for private, non-process-shared cv's, since
> process-shared can't use process-local memory like this) in one of two
> ways:
> 
> Option 1: If the list elements store the sequence number their waiter
> is waiting on, the signal/broadcast operations can choose a new
> sequence number distinct from that of all waiters.
> 
> Option 2: Each waiter can wait on a separate futex on its own stack,
> so that sequence numbers are totally unneeded. This eliminates all
> spurious wakes; signal can precisely control exactly which waiter
> wakes (e.g. choosing the oldest), thereby waking only one waiter.
> Broadcast then becomes much more expensive: the broadcasting thread
> has to make one requeue syscall per waiter. But this still might be a
> good design.
> 
> Unless anyone sees problems with this design, I'll probably start
> working on it soon. I think I'll try to commit the private-futex stuff
> first, though, to avoid having to rebase it; fixing the cv issue in
> 1.0.x will not be a direct cherry-pick anyway, so there's no point in
> putting off 1.0.x-incompatible changes pending the fix.
> 
> Rich