Re: [boost] [thread] Request review of new synchronisation object, boost::permit<>

Subject: Re: [boost] [thread] Request review of new synchronisation object, boost::permit<>
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2014-05-05 13:09:49

On 5 May 2014 at 15:38, Peter Dimov wrote:

> > but in essence a manual reset Win32 event object state change doesn't make 
> > strong guarantees about what happens to waiters. A permit grant, if 
> > non-consuming, will block until all waiting threads at the point of grant 
> > have been released. I believe the Win32 SetEvent() doesn't
> block.
> 
> This doesn't make sense to me. How do you differentiate between waiting 
> threads being released or non-released? SetEvent doesn't block, but after 
> it's called, the waiting threads are no longer blocked and will resume their 
> execution at scheduler's judgment. What would it mean for SetEvent to block 
> until they are released? What does released mean?

Released = left the wait function.

> As it stands, permits look very much like events to me - not just 
> semantically similar, but equivalent. The manual reset event has grant, 
> revoke, wait; grant unblocks all current and future waiters. The auto reset 
> event has notify_one and wait, and notify_one unblocks one current or future 
> waiter, except that two or more notify_one calls when there are no waiters 
> are equivalent to one. It seems to me that this is exactly how permits work; 
> or if there's a difference, I can't see it.

There are some subtle differences due to permits being user space, 
portable and non-kernel. But generally yes.

Does this mean they are a wise or bad addition to Boost.Thread?

> Incidentally, I think that both your examples of condition variables not 
> working are wrong. The first one is where you say that
> 
> "The problem here is that the notify can cause the permit object to be
> destroyed before the notify has exited -- which if tried with condition
> variables may produce memory corruption."
> 
> Condition variables, in fact, do support this. If a condition variable 
> implementation causes memory corruption in this scenario, then it's buggy.

I see no guarantee of such in either the Boost documentation or 
http://www.cplusplus.com/reference/condition_variable/condition_variab
le/~condition_variable/. You are safe going the other way round i.e. 
destroying a condvar which has wait functions in the process of 
exiting in other threads.

I raised this point because clang's thread sanitiser pukes if you 
destroy a condvar which is notifying in other threads. It could be a 
false positive.

> The second one is where you say
> 
> "And the compiler's optimiser is permitted by the standard to believe that 
> result has not changed between its initialisation and the first test of its 
> value, so ..."
> 
> The compiler optimizer is not permitted by the standard to hold such 
> beliefs. There is a mutex acquisition between result = 0 and result != 0; 
> this is an acquire operation, and acquire operations may synchronize-with 
> release operations in different threads, which synchronize-with edge may 
> cause the load of 'result' to see a different value unless 'result' can be 
> proven to be local to this thread, which it cannot be because of the [&].

This is a difficult one I agree.

The way I came at it is this: examine this reduced code first:

atomic<bool> &lock;
int result=0;
while(!cas_lock(lock));
if(!result)  // can the compiler assume this is always false?

Sure, the CAS lock prevents reordering of reads and writes either 
side of the lock. But does it tell the compiler that it cannot assume 
that a *local* variable's value will not have changed across the CAS 
lock?

I decided this is a valid optimisation, so the compiler can assume 
result will still be zero and can skip checking it.

This now opens the problem of the capturing lambda - does 
constructing a capturing lambda tell the compiler it cannot assume 
that any of the reference captured values will not be modified? So, 
code like this:

atomic<bool> &lock;
int result=0;
[&]{};
while(!cas_lock(lock));
if(!result)  // can the compiler assume this is always false?

If merely constructing a capturing lambda means local variables could 
be modified, that seems to me as equal to "mark all local variables 
as volatile" which seems daft. Just to be sure though as I wasn't 
sure, I asked about this on stackoverflow at 
https://stackoverflow.com/questions/22809921/do-global-reference-captu
ring-lambdas-in-c-inhibit-alias-optimisations and the answer appeared 
to be that indeed that consequence is daft.

Hence the example in the docs. If I am missing something, I am all 
ears, this problem bothers me. Do remember I did say in the docs that 
I am not claiming that any compiler actually does this optimisation, 
I'm merely saying that some future compiler potentially could.

(and yes, the thread creation almost certainly involves a syscall, 
and a syscall always has the compiler assume all memory could have 
changed, so yes it would always reload the boolean. However while 
this is safe with boost::thread, it may not be with a boost::fiber 
for example).

Anyway, I still stick to my guns on that predicate checked values in 
wait conditions really ought to be stored atomic to prevent 
reordering and elision. Atomic storage guarantees.

Niall

-- 
ned Productions Limited Consulting
http://www.nedproductions.biz/ 
http://ie.linkedin.com/in/nialldouglas/