Re: My current understanding of cond var access restrictions

[Rich Felker <dalias@libc.org>]

On Thu, Aug 14, 2014 at 01:20:25AM +0200, Jens Gustedt wrote:
> Hi,
> 
> Am Mittwoch, den 13.08.2014, 17:23 -0400 schrieb Rich Felker:
> > Since this has all gotten really confusing, I've written up a summary
> > of my current understanding of access- and destruction-related issues
> > with cond vars. Jens, I'd appreciate it if you could comment on
> > whether the below text seems to match your understanding.
> 
> I think so.
> 
> But have in mind that all what you say, strongly relies on
> implementing each of the control structures as one monolithic
> object. As soon as you split conditions into two parts (one the user
> space interface, one an internal synchronization structure that is
> allocated separately) part of the trouble disappears.

The basic idea of your design is reference-counting the object.
There's no need for dynamic allocation to make this work. Simply
incrementing/decrementing a reference counter in the main object, and
waiting for it to reach zero in the destroy function, achieves the
same thing -- but it requires either spinlocks or a FUTEX_WAKE_OP for
the final decrement-to-zero if there is a destroyer waiting.

Of course this doesn't work for the unmapping issue with
process-shared objects, but allocation doesn't work there either.

> I know that you don't like that "split" approach for the disadvantages
> that dynamic allocation has. But I think that the standard(s) clearly
> have such an implementation in mind when they speak of init functions
> allocating the necessary resources for a control structure.

C, yes. POSIX, yes, but only for non-process-shared objects unless by
allocation you mean to include kernelspace allocation of
synchronization objects via a kernel API specifically designed for
this (which Linux lacks).

> > 1. When can a cv be destroyed?
> > [...]
> 
> I think this can be summarized in that the thread that does the
> destruction must be able to establish a happens-before relation
> between all pthread_cond_[timed]wait operations and the final wake
> operation. In current POSIX this relation can only be established by
> mutexes or similar synchronization mechanisms. Once C11 will be
> integrated to POSIX, atomic operations will be added to that.

Yes.

> > 4. When can signal and broadcast safely use the mutex?
> > 
> > Not at all, unless it can block waiters from exiting the wait. Any
> > waiter could spontaneously exit the wait as a result of cancellation,
> > timeout, or a cv signal from another thread, and by the above, it may
> > be entitled to destroy the mutex.
> 
> Are you suggesting that all waiters when coming back should first
> regain an internal lock on the cv?

I'm not sure. To some extent, rather, it's making me doubt that
requeue is practical, but I'm still hopeful.

> > 5. When can [timed]wait safely access the cv?
> > 
> > Only before unlocking the mutex, unless the implementation
> > synchronizes with possible signaling threads, or with destruction (and
> > possibly unmapping). Otherwise, per the above, it's possible that a
> > signaling thread destroys the cv.
> 
> so again this suggests an internal lock on the cv that would be used
> to synchronize between waiters and wakers?

Yes, I think so.

> > Since it seems impossible to implement a cv without accessing the cv
> > object after the mutex unlock (even in the minimal implementation,
> 
> This supposing that the mutex unlock operation and the wait operation
> are done with two different system calls.

Yes. Linux has no futex operation which both writes and waits except
possibly priority-inheritance locking, which is definitely not an
appropriate primitive here.

> > it's necessary to have at least one read access for the futex wait), I
> > think this means an internal synchronization mechanism is necessary.
> 
> If by internal synchronization you mean that the transition from the
> unlock to the wait only has to appear to be atomic (the ``as-if''
> rule), yes.

I just meant that it seems necessary to do something to preserve the
right to access the cv object by excluding other operations which
could lead to it being destroyed. Possibly this is just a simplified
version of what I have now (blocking destroy), but I don't see how
that can solve the unmapping problem for process-shared cv's (if it
needs to be supported). Perhaps a better solution would be to have
signal/broadcast wait for any waiters that weren't woken/requeued
(since woken/requeued ones are potentially past the point of needing
to access the cv object) to reach the point just before relocking the
mutex. This sounds similar to what you were proposing.

I'll elaborate more in a second follow-up email.

Rich