Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   What in C++11 prohibits mutex operations from being reordered? (http://www.velocityreviews.com/forums/t959296-what-in-c-11-prohibits-mutex-operations-from-being-reordered.html)

Michael Podolsky 04-02-2013 12:16 PM

What in C++11 prohibits mutex operations from being reordered?
 
Hi Everyone,

My question is about the memory model in the context of C++11
standard.

1. The standard does not demand mutex operations to be all totally
ordered (memory_order_seq_cst), nor demand them to have
memory_order_acq_rel semantics for lock() operation. From various
parts of the standard it may be inferred that lock() operation should
have memory_order_acquire semantics and unlock() operation -
memory_order_release semantics.

2. I then should ask the question: which part of the standard prevents
lock() and unlock() operations on DIFFERENT mutexes to be reorered,
i.e. what prevents the following sequence:

m1.lock();
m1.unlock();
m2.lock();
m2.unlock();

to be compiled into:

m1.lock();
m2.lock();
m1.unlock();
m2.unlock();

which obviously must not be allowed because of potential deadlocks.

3. If the answer to the previous question is some special knowledge of
compiler of mutex objects, I should then ask the same question for a
hypothetical hand-made synchronization object, like a spin-lock,
implemented via atomic operations with memory_order_acquire for
lock() and memory_order_release on unlock(). The same question should
be asked here - does the standard prohibit (and by which exactly
paragraph if you may make the reference) reordering of unlock() and a
following lock() operations for such a hand-made object which may
internally use

atomic<int>::store(0, memory_order_release) for unlock
and then
atomic<int>::exchange(1, memory_order_acquire) for lock?

Note again that these operation are running on DIFFERENT memory
locations, i.e. the question is now reformulated like: what prohibits
the following reordering

from

while( atomic1.exchange(1, memory_order_acquire) ){;}
// critical section protected by atomic1
atomic1.store(0, memory_order_release);

while( atomic2.exchange(1, memory_order_acquire) ){;}
// critical section protected by atomic2
atomic2.store(0, memory_order_release);

to

while( atomic1.exchange(1, memory_order_acquire) ){;}
while( atomic2.exchange(1, memory_order_acquire) ){;}

atomic1.store(0, memory_order_release);
atomic2.store(0, memory_order_release);

Regards,
Michael

Öö Tiib 04-02-2013 02:10 PM

Re: What in C++11 prohibits mutex operations from being reordered?
 
On Tuesday, 2 April 2013 15:16:25 UTC+3, Michael Podolsky wrote:
> My question is about the memory model in the context of C++11
> standard.
>
> 1. The standard does not demand mutex operations to be all totally
> ordered (memory_order_seq_cst), nor demand them to have
> memory_order_acq_rel semantics for lock() operation. From various
> parts of the standard it may be inferred that lock() operation should
> have memory_order_acquire semantics and unlock() operation -
> memory_order_release semantics.


So it is not 'memory_order_relaxed' that may result with data reaching
other thread in strange order.

> 2. I then should ask the question: which part of the standard prevents
> lock() and unlock() operations on DIFFERENT mutexes to be reorered,
> i.e. what prevents the following sequence:
>
> m1.lock();
> m1.unlock();
> m2.lock();
> m2.unlock();
>
> to be compiled into:
>
> m1.lock();
> m2.lock();
> m1.unlock();
> m2.unlock();


How compiler is allowed to compile it like that? The locks and unlocks
have side effects and there is § 1.9/14:
"Every value computation and side effect associated with a full-expression
is sequenced before every value computation and side effect associated with
the next full-expression to be evaluated."

Perhaps the compilers have gone too far with optimizations somewhere?

Michael Podolsky 04-03-2013 02:30 AM

Re: What in C++11 prohibits mutex operations from being reordered?
 
On Apr 2, 10:10*am, Öö Tiib <oot...@hot.ee> wrote:
> On Tuesday, 2 April 2013 15:16:25 UTC+3, Michael Podolsky *wrote:
> > 2. I then should ask the question: which part of the standard prevents
> > lock() and unlock() operations on DIFFERENT mutexes to be reorered,
> > i.e. what prevents the following sequence:

>
> > m1.lock();
> > m1.unlock();
> > m2.lock();
> > m2.unlock();

>
> > to be compiled into:

>
> > m1.lock();
> > m2.lock();
> > m1.unlock();
> > m2.unlock();

>
> How compiler is allowed to compile it like that?


I hope it is not, just wanted to understand what exact part of
standard prevents it from doing so.


> The locks and unlocks
> have side effects and there is § 1.9/14:
> *"Every value computation and side effect associated with a full-expression
> is sequenced before every value computation and side effect associated with
> the next full-expression to be evaluated."


Even a simple assignment has a side effect. §1.9/12 "modifying an
object". So if you are right, the following two assignment to integer
variables cannot be reordered.

i1=5; // has side effect, so
i2=7; // can't be reordered???

We are not allowed by standard to look at the reordering of such
assignments, but we can look at relaxed atomics:

a1.store(5, memory_order_relaxed);
a2.store(7, memory_order_relaxed); // can't be reordered by
// compiler???



It can not be direct relation between "sequenced before" relation and
assembly output, otherwise we would not be allowed to reorder the
previous two relaxed atomic operations on the level of compiler. And
we are allowed.

Regards,
Michael

Öö Tiib 04-03-2013 11:17 AM

Re: What in C++11 prohibits mutex operations from being reordered?
 
On Wednesday, 3 April 2013 05:30:45 UTC+3, Michael Podolsky wrote:
> On Apr 2, 10:10 am, Öö Tiib <oot...@hot.ee> wrote:
> > On Tuesday, 2 April 2013 15:16:25 UTC+3, Michael Podolsky wrote:
> > > 2. I then should ask the question: which part of the standard prevents
> > > lock() and unlock() operations on DIFFERENT mutexes to be reorered,
> > > i.e. what prevents the following sequence:

> >
> > > m1.lock();
> > > m1.unlock();
> > > m2.lock();
> > > m2.unlock();

> >
> > > to be compiled into:

> >
> > > m1.lock();
> > > m2.lock();
> > > m1.unlock();
> > > m2.unlock();

> >
> > How compiler is allowed to compile it like that?

>
> I hope it is not, just wanted to understand what exact part of
> standard prevents it from doing so.


Mutex operations make things visible to other threads and so possibly observable behavior.

> > The locks and unlocks
> > have side effects and there is § 1.9/14:
> > "Every value computation and side effect associated with a full-expression
> > is sequenced before every value computation and side effect associated with
> > the next full-expression to be evaluated."


I forgot to say here that "sequenced before" is only making the abstract
machines expected behavior in one thread clear. If compiler can prove
that it is not observable then it can reorder.

> Even a simple assignment has a side effect. §1.9/12 "modifying an
> object". So if you are right, the following two assignment to integer
> variables cannot be reordered.
>
> i1=5; // has side effect, so
> i2=7; // can't be reordered???


It can be reordered if the i1 and i2 are not volatile. Volatile means
strictly abstract machine (§ 1.9/8) not observable behavior of
abstract machine (§1.9/1 and /5).

> We are not allowed by standard to look at the reordering of such
> assignments, but we can look at relaxed atomics:
>
> a1.store(5, memory_order_relaxed);
> a2.store(7, memory_order_relaxed); // can't be reordered by
> // compiler???


Can be. Those are relaxed! Relaxed means "no data races" and that's
it, no "fences" (hardware memory ordering instructions) required here.
Without fences ... the operations may be done concurrently or reordered
by modern processors and so it does not even matter what assembler
compiler did make of it. Several places in standard explain it.

> It can not be direct relation between "sequenced before" relation and
> assembly output, otherwise we would not be allowed to reorder the
> previous two relaxed atomic operations on the level of compiler. And
> we are allowed.


You originally asked about mutexes, and not about "relaxed" atomic
operations. For example § 1.10/5 elaborates the difference.



Michael Podolsky 04-03-2013 12:23 PM

Re: What in C++11 prohibits mutex operations from being reordered?
 
On Apr 3, 7:17*am, Öö Tiib <oot...@hot.ee> wrote:
> On Wednesday, 3 April 2013 05:30:45 UTC+3, Michael Podolsky *wrote:


> > It can not be direct relation between "sequenced before" relation and
> > assembly output, otherwise we would not be allowed to reorder the
> > previous two relaxed atomic operations on the level of compiler. And
> > we are allowed.

>
> You originally asked about mutexes, and not about "relaxed" atomic
> operations. For example § 1.10/5 elaborates the difference.


I thought you claimed that "sequenced before" is what solely prohibits
compiler from reordering its output instructions in my example with
mutexes, so I brought an example with integers (non-volatile, of
course) and then an example with relaxed atomics to show that
"sequenced before" is not directly equivalent to the order of
instructions produced by compiler, the compiler may still reorder
instructions, even if the later "sequenced before" former.

> For example § 1.10/5 elaborates the difference.


It is not clear for me still what in this paragraph prevents mutex
operations from being reordered in my example. Besides take into
account that in my original example (start of the thread) I have an
implementation of spin-locks with atomic variables and ask the same
question - what prevents these atomic operations from being reordered
by compiler.

Personally, I now have a feeling that it is ONLY a 'for' operator
which makes compiler to decide it cannot reorder (at least for my
custom-made spinlock) -- but I am not sure at all that I am correct,
and still, even for this idea, I can't refer to any specific paragraph
of the C++11 standard.

Regards, Michael

Michael Podolsky 04-03-2013 12:26 PM

Re: What in C++11 prohibits mutex operations from being reordered?
 
"Personally, I now have a feeling that it is ONLY a 'for' operator "

I meant 'while' operator

Alexander Terekhov 04-03-2013 04:53 PM

Re: What in C++11 prohibits mutex operations from being reordered?
 

Michael Podolsky wrote:
>
> Hi Everyone,
>
> My question is about the memory model in the context of C++11
> standard.
>
> 1. The standard does not demand mutex operations to be all totally
> ordered (memory_order_seq_cst), nor demand them to have
> memory_order_acq_rel semantics for lock() operation. From various
> parts of the standard it may be inferred that lock() operation should
> have memory_order_acquire semantics and unlock() operation -
> memory_order_release semantics.
>
> 2. I then should ask the question: which part of the standard prevents
> lock() and unlock() operations on DIFFERENT mutexes to be reorered,
> i.e. what prevents the following sequence:
>
> m1.lock();
> m1.unlock();
> m2.lock();
> m2.unlock();
>
> to be compiled into:
>
> m1.lock();
> m2.lock();
> m1.unlock();
> m2.unlock();
>
> which obviously must not be allowed because of potential deadlocks.


Injecting deadlocks is a no-no but I hope the intent is that the
following

T1:

m1.lock();
.... start T2 ...
m1.unlock();
m2.lock();

T2:

if (m2.trylock() == failure) assert(m1.trylock() == success);

may still abort (in effect allowing deadlock-free reordering above).

regards,
alexander.

?? Tiib 04-03-2013 04:59 PM

Re: What in C++11 prohibits mutex operations from being reordered?
 
On Wednesday, 3 April 2013 15:23:18 UTC+3, Michael Podolsky wrote:
> On Apr 3, 7:17?am, ?? Tiib <oot...@hot.ee> wrote:
> > On Wednesday, 3 April 2013 05:30:45 UTC+3, Michael Podolsky ?wrote:

>
> > > It can not be direct relation between "sequenced before" relation and
> > > assembly output, otherwise we would not be allowed to reorder the
> > > previous two relaxed atomic operations on the level of compiler. And
> > > we are allowed.

> >
> > You originally asked about mutexes, and not about "relaxed" atomic
> > operations. For example ? 1.10/5 elaborates the difference.

>
> I thought you claimed that "sequenced before" is what solely prohibits
> compiler from reordering its output instructions in my example with
> mutexes, so I brought an example with integers (non-volatile, of
> course) and then an example with relaxed atomics to show that
> "sequenced before" is not directly equivalent to the order of
> instructions produced by compiler, the compiler may still reorder
> instructions, even if the later "sequenced before" former.


Yeah, sorry for being unclear. I do not get what exact part of
puzzle it is then that you miss? "sequenced before" it was not
maybe "synchronizes with" or "happens before"? Mutex access can
not be reordered.

> > For example ? 1.10/5 elaborates the difference.

>
> It is not clear for me still what in this paragraph prevents mutex
> operations from being reordered in my example.


Yes, ?1.10/5 only tells that atomic operations, mutexes and fences
as synchronization operations and that relaxed atomic operations *are*
*not* synchronization operations.

Maybe you should first find out how synchronization operations work?
It is tricky logic sprinkled all over the standard ... I think most
of the ?1.10, ?29.3 and ?29.8 are relevant. I try to collect *short*
and *simple* and *logical* explanation ... : If A is sequenced before
B on the same thread, and B synchronizes with C on another thread,
and C is sequenced before D on that second thread, then A happens before
D, and A and D can access the same data even if they are non-atomic
operations. So ... even ordinary 'int' access like 'i = 42' can not be
ordered to other side of m2.lock() nothing to talk of m1.unlock() or
some other synchronization operation like that.

> Besides take into
> account that in my original example (start of the thread) I have an
> implementation of spin-locks with atomic variables and ask the same
> question - what prevents these atomic operations from being reordered
> by compiler.


I did not understand what your example does, sorry. Let me try to write
example that achieves some synchronization ...

// bool that tells that thread 1 is done with data. It is
// atomic just because standard does not guarantee that accesses to
// bool are atomic.
std::atomic<bool> ready(false);
// the ordinary data
int data=0;

void thread_1()
{
// these lines can't be reordered in any way
data=42;
std::atomic_thread_fence(std::memory_order_release );
ready.store(true,std::memory_order_relaxed);
}

void thread_2()
{
if(ready.load(std::memory_order_relaxed))
{
// these lines can't be reordered
std::atomic_thread_fence(std::memory_order_acquire );
std::cout<<"data="<<data<<std::endl;
}
}

The effect is that thread 2 does not touch data if thread 1
is not ready with it. So access to non-atomic "data" is safe, synchronized
and no data race is possible.

Alexander Terekhov 04-03-2013 05:10 PM

Re: What in C++11 prohibits mutex operations from being reordered?
 

?? Tiib wrote:
[...]
> Yeah, sorry for being unclear. I do not get what exact part of
> puzzle it is then that you miss? "sequenced before" it was not
> maybe "synchronizes with" or "happens before"? Mutex access can
> not be reordered.


I always thought that e.g.

a.unlock() "sequenced before" b.lock()

can be reordered in deadlock-free manner as seen by another thread using
trylock().

That's the cornerstone of efficient locking as far as memory model is
concerned.

regards,
alexander.

?? Tiib 04-03-2013 07:30 PM

Re: What in C++11 prohibits mutex operations from being reordered?
 
On Wednesday, 3 April 2013 20:10:02 UTC+3, Alexander Terekhov wrote:
> ?? Tiib wrote:
>
> [...]
> > Yeah, sorry for being unclear. I do not get what exact part of
> > puzzle it is then that you miss? "sequenced before" it was not
> > maybe "synchronizes with" or "happens before"? Mutex access can
> > not be reordered.

>
> I always thought that e.g.
>
> a.unlock() "sequenced before" b.lock()
>
> can be reordered in deadlock-free manner as seen by another thread using
> trylock().


Did you mean try_lock() failing? That function is explicitly and specially
allowed to fail by standard (see ?30.4.1.2/16) even when the lock is not
held by any other thread.

> That's the cornerstone of efficient locking as far as memory model is
> concerned.


It is just for to have cheap 'try_lock()' implementation. Makes sense.
It is good to have both cheap and sometimes failing tools in mix with
expensive and reliable tools.



All times are GMT. The time now is 01:29 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.