Can a volatile read be reordered before a lazySet?

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

Can a volatile read be reordered before a lazySet?

Dávid Karnok
Hello,

Given two atomic values held by an AtomicLong and an AtomicReference, is it possible the following two lines may be reordered?

theLong.lazySet(theLong.get() + 1);
Object o = theRef.get();

On X86, the memory model states that reads may be reordered with older writes to different locations, so the algorithm fragment above might be broken. For context, this code is part of a single-producer structure wich protects the use of theRef value with an ingress/egress counter pair.

I wonder if the same reordering might happen in a classical atomic ping-pong example:

ping.lazySet(1);
while (pong.get() == 0);

while (ping.get() == 0);
pong.lazySet(1);

i.e., in both threads, the while loops end up before the lazySet and thus deadlocking.

Best regards,
David Karnok


--
Best regards,
David Karnok


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Thomas Kountis
David,

AFAIK all the atomic* members that Java provides, pretty much provide the same guarantees 
as the volatile keyword does - which doesn't allow re-orderings on the compiler side, neither during execution.
If you look behind the covers, the fields that those two wrappers work on, are marked volatile as well. Also, lazy-set
is using the Unsafe.putOrdered...() which relies on a store-store barrier and will prevent any instruction re-ordering (as the name suggests).

So, to answer your question, I believe you are safe as far as it concerns re-orderings on your example. 

t.

On Tue, Dec 23, 2014 at 10:50 PM, Dávid Karnok <[hidden email]> wrote:
Hello,

Given two atomic values held by an AtomicLong and an AtomicReference, is it possible the following two lines may be reordered?

theLong.lazySet(theLong.get() + 1);
Object o = theRef.get();

On X86, the memory model states that reads may be reordered with older writes to different locations, so the algorithm fragment above might be broken. For context, this code is part of a single-producer structure wich protects the use of theRef value with an ingress/egress counter pair.

I wonder if the same reordering might happen in a classical atomic ping-pong example:

ping.lazySet(1);
while (pong.get() == 0);

while (ping.get() == 0);
pong.lazySet(1);

i.e., in both threads, the while loops end up before the lazySet and thus deadlocking.

Best regards,
David Karnok


--
Best regards,
David Karnok


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Vitaly Davidovich

lazySet only orders stores whereas David's code has loads and stores.  As I mentioned earlier, the ping pong example will work but the instructions may reorder.

Sent from my phone

On Dec 23, 2014 9:40 PM, "Thomas Kountis" <[hidden email]> wrote:
David,

AFAIK all the atomic* members that Java provides, pretty much provide the same guarantees 
as the volatile keyword does - which doesn't allow re-orderings on the compiler side, neither during execution.
If you look behind the covers, the fields that those two wrappers work on, are marked volatile as well. Also, lazy-set
is using the Unsafe.putOrdered...() which relies on a store-store barrier and will prevent any instruction re-ordering (as the name suggests).

So, to answer your question, I believe you are safe as far as it concerns re-orderings on your example. 

t.

On Tue, Dec 23, 2014 at 10:50 PM, Dávid Karnok <[hidden email]> wrote:
Hello,

Given two atomic values held by an AtomicLong and an AtomicReference, is it possible the following two lines may be reordered?

theLong.lazySet(theLong.get() + 1);
Object o = theRef.get();

On X86, the memory model states that reads may be reordered with older writes to different locations, so the algorithm fragment above might be broken. For context, this code is part of a single-producer structure wich protects the use of theRef value with an ingress/egress counter pair.

I wonder if the same reordering might happen in a classical atomic ping-pong example:

ping.lazySet(1);
while (pong.get() == 0);

while (ping.get() == 0);
pong.lazySet(1);

i.e., in both threads, the while loops end up before the lazySet and thus deadlocking.

Best regards,
David Karnok


--
Best regards,
David Karnok


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Nitsan Wakart
Saturday morning first cup of coffee 2 cents. T&C apply.
1. In this case:
  theLong.lazySet(1L);
  Object o = theRef.get();
There's technically nothing to stop reordering between the store and load. The problem is that moving the store past the load has potential implications to other sequences of stores to theLong/theObject which might race with the above. This is described in Shipilev's excellent JMM notes here: Java Memory Model Pragmatics (transcript)
 
IIUC this means stores and volatile loads are conservatively not reordered.
2. The case you quote has a further volatile read, we can break it down as:
  long l = theLong.get() + 1; // LOADLOAD
  theLong.lazySet(l); //STORESTORE
  Object o = theRef.get(); // LOADLOAD
In this case the STORE has to happen after the first load. The first load also must happen before the second load. The store can be reordered to happen after the second load though (at least in theory, but it won't due to 1).
3. The ping pong case is different, because the while loops are of indefinite length, potentially infinite. Delaying the store indefinitely would seem to break sequential consistency and so the while loop acts as an effective store barrier. If you replace the while loop with a for(int i=0;i<K;i++) loop the reordering becomes notionally feasible again.
  


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Thomas Kountis
That cup of coffee must have been really good ;)
Thanks for the detailed explanation Nitsan, especially for that last piece with the while-loop!


On Sat, Dec 27, 2014 at 8:09 AM, Nitsan Wakart <[hidden email]> wrote:
Saturday morning first cup of coffee 2 cents. T&C apply.
1. In this case:
  theLong.lazySet(1L);
  Object o = theRef.get();
There's technically nothing to stop reordering between the store and load. The problem is that moving the store past the load has potential implications to other sequences of stores to theLong/theObject which might race with the above. This is described in Shipilev's excellent JMM notes here: Java Memory Model Pragmatics (transcript)
 
 
image
 
 
 
 
 
Java Memory Model Pragmatics (transcript)
Happens-Before While providing a good basis to reason about programs, SO is not enough to construct a practical weak model. Here is why. Let us analyze a simple cas...
Preview by Yahoo
 
 
IIUC this means stores and volatile loads are conservatively not reordered.
2. The case you quote has a further volatile read, we can break it down as:
  long l = theLong.get() + 1; // LOADLOAD
  theLong.lazySet(l); //STORESTORE
  Object o = theRef.get(); // LOADLOAD
In this case the STORE has to happen after the first load. The first load also must happen before the second load. The store can be reordered to happen after the second load though (at least in theory, but it won't due to 1).
3. The ping pong case is different, because the while loops are of indefinite length, potentially infinite. Delaying the store indefinitely would seem to break sequential consistency and so the while loop acts as an effective store barrier. If you replace the while loop with a for(int i=0;i<K;i++) loop the reordering becomes notionally feasible again.
  




--
Thomas Kountis
PGP: 0x069D29A3

Q: "Whats the object-oriented way to become wealthy?"
A:  Inheritance


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Vitaly Davidovich
In reply to this post by Nitsan Wakart
Nitsan,

In #1, what do you mean exactly by "IIUC this means stores and volatile loads are conservatively not reordered"? Are you talking about JIT code motion only? Specifically, I'm pretty sure theLong.lazySet(1); Object o = theRef.get() sequence compiles to machine code with no cpu fences on x86; it's a mov immediate into theLong and a mov of theRef into register; the cpu can reorder these (without a StoreLoad in-between).

On Sat, Dec 27, 2014 at 3:09 AM, Nitsan Wakart <[hidden email]> wrote:
Saturday morning first cup of coffee 2 cents. T&C apply.
1. In this case:
  theLong.lazySet(1L);
  Object o = theRef.get();
There's technically nothing to stop reordering between the store and load. The problem is that moving the store past the load has potential implications to other sequences of stores to theLong/theObject which might race with the above. This is described in Shipilev's excellent JMM notes here: Java Memory Model Pragmatics (transcript)
 
 
image
 
 
 
 
 
Java Memory Model Pragmatics (transcript)
Happens-Before While providing a good basis to reason about programs, SO is not enough to construct a practical weak model. Here is why. Let us analyze a simple cas...
Preview by Yahoo
 
 
IIUC this means stores and volatile loads are conservatively not reordered.
2. The case you quote has a further volatile read, we can break it down as:
  long l = theLong.get() + 1; // LOADLOAD
  theLong.lazySet(l); //STORESTORE
  Object o = theRef.get(); // LOADLOAD
In this case the STORE has to happen after the first load. The first load also must happen before the second load. The store can be reordered to happen after the second load though (at least in theory, but it won't due to 1).
3. The ping pong case is different, because the while loops are of indefinite length, potentially infinite. Delaying the store indefinitely would seem to break sequential consistency and so the while loop acts as an effective store barrier. If you replace the while loop with a for(int i=0;i<K;i++) loop the reordering becomes notionally feasible again.
  


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Gil Tene
In reply to this post by Thomas Kountis
It is valid (e.g. per the JMM cookbook) for a JVM to implement a volatile read such that it prevents reordering with subsequent stores, but not with prior ones. Given this valid (and common) implementation, both cases asked about below can have a reordering happen between the lazySet and a subsequent (in program order) volatile get. Target machine (x86 or not) has nothing to do with it, as the compiler can (and will) do this reordering before any target machine code gets generated.

The only ordering that lazySet is actually known/required to provide will prevent the store operation from being reordered with any stores that came before it. There is nothing to prevent it from being pushed forward past other non-dependent stores, loads, or volatile loads. [The thing that stops it being pushed forward past a non-dependent volatile store is the volatile store's relationship with stores that precede it].

So:

theLong.lazySet(theLong.get() + 1);
Object o = theRef.get();

can be legitimately re-ordered by the compiler to:

x = theLong.get() + 1
Object o = theRef.get();
theLong.lazySet(x);

And the ping pong case:

ping.lazySet(1);
while (pong.get() == 0);

while (ping.get() == 0);
pong.lazySet(1);

can be legitimately reordered by the compiler to:

T1:
while (pong.get() == 0);
ping.lazySet(1);

T2:
while (ping.get() == 0);
pong.lazySet(1);
 
and can certainly result in a well deserved deadlock.

— Gil.
 

On Dec 23, 2014, at 6:17 PM, Thomas Kountis <[hidden email]> wrote:

David,

AFAIK all the atomic* members that Java provides, pretty much provide the same guarantees 
as the volatile keyword does - which doesn't allow re-orderings on the compiler side, neither during execution.
If you look behind the covers, the fields that those two wrappers work on, are marked volatile as well. Also, lazy-set
is using the Unsafe.putOrdered...() which relies on a store-store barrier and will prevent any instruction re-ordering (as the name suggests).

So, to answer your question, I believe you are safe as far as it concerns re-orderings on your example. 

t.

On Tue, Dec 23, 2014 at 10:50 PM, Dávid Karnok <[hidden email]> wrote:
Hello,

Given two atomic values held by an AtomicLong and an AtomicReference, is it possible the following two lines may be reordered?

theLong.lazySet(theLong.get() + 1);
Object o = theRef.get();

On X86, the memory model states that reads may be reordered with older writes to different locations, so the algorithm fragment above might be broken. For context, this code is part of a single-producer structure wich protects the use of theRef value with an ingress/egress counter pair.

I wonder if the same reordering might happen in a classical atomic ping-pong example:

ping.lazySet(1);
while (pong.get() == 0);

while (ping.get() == 0);
pong.lazySet(1);

i.e., in both threads, the while loops end up before the lazySet and thus deadlocking.

Best regards,
David Karnok


--
Best regards,
David Karnok


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest





_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Andrew Haley
On 28/12/14 00:53, Gil Tene wrote:

> The only ordering that lazySet is actually known/required to provide
> will prevent the store operation from being reordered with any
> stores that came before it. There is nothing to prevent it from
> being pushed forward past other non-dependent stores, loads, or
> volatile loads. [The thing that stops it being pushed forward past a
> non-dependent volatile store is the volatile store's relationship
> with stores that precede it].

But, as Doug said:

"There are three basic strengths of write: Relaxed (normal),
releasing, and SC volatile. I got talked into naming the second
releasing version 'lazySet' which is confusing enough, but compounded
by the almost equally odd internal unsafe name 'ordered'.

"These should be less confusing in JDK9 when we provide more uniform
enhanced-volatile support."

Andrew.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Nitsan Wakart
In reply to this post by Vitaly Davidovich
Re-read the Shipilev "JMM Pragmatics" reference again last night, and discussed with Gil. I think that cup of coffee was nowhere near enough :-). In particular:
"If IUC this means stores and volatile loads are conservatively not reordered" is FALSE because the premise "IUC" is false. I did not understand correctly which leads me to amend my comment:
1. There's technically nothing to stop reordering between the store and load.
>  theLong.lazySet(1L);
>  Object o = theRef.get();
2. There's technically nothing to stop reordering between the store and load.
>  long l = theLong.get() + 1; // LOADLOAD
>  theLong.lazySet(l); //STORESTORE
>  Object o = theRef.get(); // LOADLOAD
3. I still think the while loop presents a different case to normal flow. So for now I still hold that the lazySet cannot be moved after the while loop.

My sincere apologies for the confusion.
Happy holidays to all.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

oleksandr otenko
Not sure why you say (3). Since lazySet is not part of JMM, I am only assuming it is pretty much like an ordered store on x86.

In the presence of write buffers the loop may spin indefinitely, yet the lazy-stored write won't become visible to the pong thread - there'd be nothing to cause the buffers of the ping thread to flush. So ping effectively will appear to perform all the loads of the indefinite loop ahead of the store.

In reality the only event that would cause the write buffers to flush, is the thread preemption.


Alex


On 31/12/2014 07:20, Nitsan Wakart wrote:
Re-read the Shipilev "JMM Pragmatics" reference again last night, and discussed with Gil. I think that cup of coffee was nowhere near enough :-). In particular:
"If IUC this means stores and volatile loads are conservatively not reordered" is FALSE because the premise "IUC" is false. I did not understand correctly which leads me to amend my comment:
1. There's technically nothing to stop reordering between the store and load.
>  theLong.lazySet(1L);
>  Object o = theRef.get();
2. There's technically nothing to stop reordering between the store and load.
>  long l = theLong.get() + 1; // LOADLOAD
>  theLong.lazySet(l); //STORESTORE
>  Object o = theRef.get(); // LOADLOAD
3. I still think the while loop presents a different case to normal flow. So for now I still hold that the lazySet cannot be moved after the while loop.

My sincere apologies for the confusion.
Happy holidays to all.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Vitaly Davidovich

Write buffers don't *need* to be drained, they drain automatically anyway.  At least that's the case for intel.  So the issue here is more like what Gil said - compiler can reorder the code causing a deadlock.

Sent from my phone

On Dec 31, 2014 9:45 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Not sure why you say (3). Since lazySet is not part of JMM, I am only assuming it is pretty much like an ordered store on x86.

In the presence of write buffers the loop may spin indefinitely, yet the lazy-stored write won't become visible to the pong thread - there'd be nothing to cause the buffers of the ping thread to flush. So ping effectively will appear to perform all the loads of the indefinite loop ahead of the store.

In reality the only event that would cause the write buffers to flush, is the thread preemption.


Alex


On 31/12/2014 07:20, Nitsan Wakart wrote:
Re-read the Shipilev "JMM Pragmatics" reference again last night, and discussed with Gil. I think that cup of coffee was nowhere near enough :-). In particular:
"If IUC this means stores and volatile loads are conservatively not reordered" is FALSE because the premise "IUC" is false. I did not understand correctly which leads me to amend my comment:
1. There's technically nothing to stop reordering between the store and load.
>  theLong.lazySet(1L);
>  Object o = theRef.get();
2. There's technically nothing to stop reordering between the store and load.
>  long l = theLong.get() + 1; // LOADLOAD
>  theLong.lazySet(l); //STORESTORE
>  Object o = theRef.get(); // LOADLOAD
3. I still think the while loop presents a different case to normal flow. So for now I still hold that the lazySet cannot be moved after the while loop.

My sincere apologies for the confusion.
Happy holidays to all.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

oleksandr otenko
Yes, but do they drain if no one writes anything?

Alex

On 31/12/2014 15:18, Vitaly Davidovich wrote:

Write buffers don't *need* to be drained, they drain automatically anyway.  At least that's the case for intel.  So the issue here is more like what Gil said - compiler can reorder the code causing a deadlock.

Sent from my phone

On Dec 31, 2014 9:45 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Not sure why you say (3). Since lazySet is not part of JMM, I am only assuming it is pretty much like an ordered store on x86.

In the presence of write buffers the loop may spin indefinitely, yet the lazy-stored write won't become visible to the pong thread - there'd be nothing to cause the buffers of the ping thread to flush. So ping effectively will appear to perform all the loads of the indefinite loop ahead of the store.

In reality the only event that would cause the write buffers to flush, is the thread preemption.


Alex


On 31/12/2014 07:20, Nitsan Wakart wrote:
Re-read the Shipilev "JMM Pragmatics" reference again last night, and discussed with Gil. I think that cup of coffee was nowhere near enough :-). In particular:
"If IUC this means stores and volatile loads are conservatively not reordered" is FALSE because the premise "IUC" is false. I did not understand correctly which leads me to amend my comment:
1. There's technically nothing to stop reordering between the store and load.
>  theLong.lazySet(1L);
>  Object o = theRef.get();
2. There's technically nothing to stop reordering between the store and load.
>  long l = theLong.get() + 1; // LOADLOAD
>  theLong.lazySet(l); //STORESTORE
>  Object o = theRef.get(); // LOADLOAD
3. I still think the while loop presents a different case to normal flow. So for now I still hold that the lazySet cannot be moved after the while loop.

My sincere apologies for the confusion.
Happy holidays to all.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Vitaly Davidovich

Your previous reply talked about performing a lazy write and then possibly having it stall indefinitely (or until preemption, as you say) because nobody forces the buffer to drain.  I'm saying if the write actually occurs, it'll drain on its own.

Sent from my phone

On Dec 31, 2014 11:31 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Yes, but do they drain if no one writes anything?

Alex

On 31/12/2014 15:18, Vitaly Davidovich wrote:

Write buffers don't *need* to be drained, they drain automatically anyway.  At least that's the case for intel.  So the issue here is more like what Gil said - compiler can reorder the code causing a deadlock.

Sent from my phone

On Dec 31, 2014 9:45 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Not sure why you say (3). Since lazySet is not part of JMM, I am only assuming it is pretty much like an ordered store on x86.

In the presence of write buffers the loop may spin indefinitely, yet the lazy-stored write won't become visible to the pong thread - there'd be nothing to cause the buffers of the ping thread to flush. So ping effectively will appear to perform all the loads of the indefinite loop ahead of the store.

In reality the only event that would cause the write buffers to flush, is the thread preemption.


Alex


On 31/12/2014 07:20, Nitsan Wakart wrote:
Re-read the Shipilev "JMM Pragmatics" reference again last night, and discussed with Gil. I think that cup of coffee was nowhere near enough :-). In particular:
"If IUC this means stores and volatile loads are conservatively not reordered" is FALSE because the premise "IUC" is false. I did not understand correctly which leads me to amend my comment:
1. There's technically nothing to stop reordering between the store and load.
>  theLong.lazySet(1L);
>  Object o = theRef.get();
2. There's technically nothing to stop reordering between the store and load.
>  long l = theLong.get() + 1; // LOADLOAD
>  theLong.lazySet(l); //STORESTORE
>  Object o = theRef.get(); // LOADLOAD
3. I still think the while loop presents a different case to normal flow. So for now I still hold that the lazySet cannot be moved after the while loop.

My sincere apologies for the confusion.
Happy holidays to all.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

oleksandr otenko
yes, I got you, and my clumsy question really should have read "upon what condition will they drain on their own"

Like, N tics? Coherence traffic ceased? Hyperthreaded sibling does something?

Alex

On 31/12/2014 16:36, Vitaly Davidovich wrote:

Your previous reply talked about performing a lazy write and then possibly having it stall indefinitely (or until preemption, as you say) because nobody forces the buffer to drain.  I'm saying if the write actually occurs, it'll drain on its own.

Sent from my phone

On Dec 31, 2014 11:31 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Yes, but do they drain if no one writes anything?

Alex

On 31/12/2014 15:18, Vitaly Davidovich wrote:

Write buffers don't *need* to be drained, they drain automatically anyway.  At least that's the case for intel.  So the issue here is more like what Gil said - compiler can reorder the code causing a deadlock.

Sent from my phone

On Dec 31, 2014 9:45 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Not sure why you say (3). Since lazySet is not part of JMM, I am only assuming it is pretty much like an ordered store on x86.

In the presence of write buffers the loop may spin indefinitely, yet the lazy-stored write won't become visible to the pong thread - there'd be nothing to cause the buffers of the ping thread to flush. So ping effectively will appear to perform all the loads of the indefinite loop ahead of the store.

In reality the only event that would cause the write buffers to flush, is the thread preemption.


Alex


On 31/12/2014 07:20, Nitsan Wakart wrote:
Re-read the Shipilev "JMM Pragmatics" reference again last night, and discussed with Gil. I think that cup of coffee was nowhere near enough :-). In particular:
"If IUC this means stores and volatile loads are conservatively not reordered" is FALSE because the premise "IUC" is false. I did not understand correctly which leads me to amend my comment:
1. There's technically nothing to stop reordering between the store and load.
>  theLong.lazySet(1L);
>  Object o = theRef.get();
2. There's technically nothing to stop reordering between the store and load.
>  long l = theLong.get() + 1; // LOADLOAD
>  theLong.lazySet(l); //STORESTORE
>  Object o = theRef.get(); // LOADLOAD
3. I still think the while loop presents a different case to normal flow. So for now I still hold that the lazySet cannot be moved after the while loop.

My sincere apologies for the confusion.
Happy holidays to all.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Vitaly Davidovich

I don't know the exact mechanics of draining, but I suspect it happens when the cacheline is fetched and/or RFO completes on it.  The way I understand it is core wants to write but either doesn't have the cacheline or needs to obtain ownership of it; while that request is outstanding, the write is put into the store buffer.  Once the line is available, the write is applied to it from the buffer.

I'd welcome someone with more details to correct/enhance my understanding.

Sent from my phone

On Dec 31, 2014 11:50 AM, "Oleksandr Otenko" <[hidden email]> wrote:
yes, I got you, and my clumsy question really should have read "upon what condition will they drain on their own"

Like, N tics? Coherence traffic ceased? Hyperthreaded sibling does something?

Alex

On 31/12/2014 16:36, Vitaly Davidovich wrote:

Your previous reply talked about performing a lazy write and then possibly having it stall indefinitely (or until preemption, as you say) because nobody forces the buffer to drain.  I'm saying if the write actually occurs, it'll drain on its own.

Sent from my phone

On Dec 31, 2014 11:31 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Yes, but do they drain if no one writes anything?

Alex

On 31/12/2014 15:18, Vitaly Davidovich wrote:

Write buffers don't *need* to be drained, they drain automatically anyway.  At least that's the case for intel.  So the issue here is more like what Gil said - compiler can reorder the code causing a deadlock.

Sent from my phone

On Dec 31, 2014 9:45 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Not sure why you say (3). Since lazySet is not part of JMM, I am only assuming it is pretty much like an ordered store on x86.

In the presence of write buffers the loop may spin indefinitely, yet the lazy-stored write won't become visible to the pong thread - there'd be nothing to cause the buffers of the ping thread to flush. So ping effectively will appear to perform all the loads of the indefinite loop ahead of the store.

In reality the only event that would cause the write buffers to flush, is the thread preemption.


Alex


On 31/12/2014 07:20, Nitsan Wakart wrote:
Re-read the Shipilev "JMM Pragmatics" reference again last night, and discussed with Gil. I think that cup of coffee was nowhere near enough :-). In particular:
"If IUC this means stores and volatile loads are conservatively not reordered" is FALSE because the premise "IUC" is false. I did not understand correctly which leads me to amend my comment:
1. There's technically nothing to stop reordering between the store and load.
>  theLong.lazySet(1L);
>  Object o = theRef.get();
2. There's technically nothing to stop reordering between the store and load.
>  long l = theLong.get() + 1; // LOADLOAD
>  theLong.lazySet(l); //STORESTORE
>  Object o = theRef.get(); // LOADLOAD
3. I still think the while loop presents a different case to normal flow. So for now I still hold that the lazySet cannot be moved after the while loop.

My sincere apologies for the confusion.
Happy holidays to all.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Gil Tene
In reply to this post by oleksandr otenko
It would vary by processor. But in most processors, store buffer contents are usually drained as soon as their associated in-flight L1 cache line arrives so that the store can be merged into it. On processors that implicitly maintain store order, the drain order if usually a FIFO. I.e. stores that have lines ready won't drain before that were ahead of them but don't yet have lines available.

So in general stuff will be in the buffer for a time length that is on the order of an LLC miss (L3 on modern Xeons).


On Dec 31, 2014, at 8:50 AM, Oleksandr Otenko <[hidden email]> wrote:

yes, I got you, and my clumsy question really should have read "upon what condition will they drain on their own"

Like, N tics? Coherence traffic ceased? Hyperthreaded sibling does something?

Alex

On 31/12/2014 16:36, Vitaly Davidovich wrote:

Your previous reply talked about performing a lazy write and then possibly having it stall indefinitely (or until preemption, as you say) because nobody forces the buffer to drain.  I'm saying if the write actually occurs, it'll drain on its own.

Sent from my phone

On Dec 31, 2014 11:31 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Yes, but do they drain if no one writes anything?

Alex

On 31/12/2014 15:18, Vitaly Davidovich wrote:

Write buffers don't *need* to be drained, they drain automatically anyway.  At least that's the case for intel.  So the issue here is more like what Gil said - compiler can reorder the code causing a deadlock.

Sent from my phone

On Dec 31, 2014 9:45 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Not sure why you say (3). Since lazySet is not part of JMM, I am only assuming it is pretty much like an ordered store on x86.

In the presence of write buffers the loop may spin indefinitely, yet the lazy-stored write won't become visible to the pong thread - there'd be nothing to cause the buffers of the ping thread to flush. So ping effectively will appear to perform all the loads of the indefinite loop ahead of the store.

In reality the only event that would cause the write buffers to flush, is the thread preemption.


Alex


On 31/12/2014 07:20, Nitsan Wakart wrote:
Re-read the Shipilev "JMM Pragmatics" reference again last night, and discussed with Gil. I think that cup of coffee was nowhere near enough :-). In particular:
"If IUC this means stores and volatile loads are conservatively not reordered" is FALSE because the premise "IUC" is false. I did not understand correctly which leads me to amend my comment:
1. There's technically nothing to stop reordering between the store and load.
>  theLong.lazySet(1L);
>  Object o = theRef.get();
2. There's technically nothing to stop reordering between the store and load.
>  long l = theLong.get() + 1; // LOADLOAD
>  theLong.lazySet(l); //STORESTORE
>  Object o = theRef.get(); // LOADLOAD
3. I still think the while loop presents a different case to normal flow. So for now I still hold that the lazySet cannot be moved after the while loop.

My sincere apologies for the confusion.
Happy holidays to all.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest





_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Can a volatile read be reordered before a lazySet?

Hans Boehm
In reply to this post by Vitaly Davidovich
In my view, if we have

ping.lazySet(1);
while (pong.get() == 0);

it is certainly possible that some number of the loads become visible before the store.  But I don't believe the intent in either Java or C++, was to allow the compiler to defer the  store until after the loop, causing this to deadlock.

This is largely a question of which progress guarantees are provided:  This transformation makes it look to the programmer as though visibility of the lazySet is delayed indefinitely for no reason.  Both languages are very careful in what they actually promise in this respect because some real implementations do in fact provide very weak guarantees.  At least at the time of the Java memory model, there were non-preemptive threads implementations, in which threads could stall indefinitely for no good reason except the existence of other runnable threads.  As earlier messages point out, hardware architectures also typically don't provide an iron-clad guarantee that store buffers drain in a finite amount of time under all conditions, though in practice they tend do so quite quickly (otherwise e.g. spin-lock releases would not become visible to other threads, which would be bad).

So I think the somewhat unsatisfactory bottom line here is that there is no clear-cut, always-applicable, prohibition against compiler movement of the lazySet/release store (though 17.4.9 imposes some restrictions for Java), but I would consider it very poor quality of implementation to actually do do.  I don't think this would deadlock for any real implementations.

Hans

On Wed, Dec 31, 2014 at 10:32 AM, Vitaly Davidovich <[hidden email]> wrote:

I don't know the exact mechanics of draining, but I suspect it happens when the cacheline is fetched and/or RFO completes on it.  The way I understand it is core wants to write but either doesn't have the cacheline or needs to obtain ownership of it; while that request is outstanding, the write is put into the store buffer.  Once the line is available, the write is applied to it from the buffer.

I'd welcome someone with more details to correct/enhance my understanding.

Sent from my phone

On Dec 31, 2014 11:50 AM, "Oleksandr Otenko" <[hidden email]> wrote:
yes, I got you, and my clumsy question really should have read "upon what condition will they drain on their own"

Like, N tics? Coherence traffic ceased? Hyperthreaded sibling does something?

Alex

On 31/12/2014 16:36, Vitaly Davidovich wrote:

Your previous reply talked about performing a lazy write and then possibly having it stall indefinitely (or until preemption, as you say) because nobody forces the buffer to drain.  I'm saying if the write actually occurs, it'll drain on its own.

Sent from my phone

On Dec 31, 2014 11:31 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Yes, but do they drain if no one writes anything?

Alex

On 31/12/2014 15:18, Vitaly Davidovich wrote:

Write buffers don't *need* to be drained, they drain automatically anyway.  At least that's the case for intel.  So the issue here is more like what Gil said - compiler can reorder the code causing a deadlock.

Sent from my phone

On Dec 31, 2014 9:45 AM, "Oleksandr Otenko" <[hidden email]> wrote:
Not sure why you say (3). Since lazySet is not part of JMM, I am only assuming it is pretty much like an ordered store on x86.

In the presence of write buffers the loop may spin indefinitely, yet the lazy-stored write won't become visible to the pong thread - there'd be nothing to cause the buffers of the ping thread to flush. So ping effectively will appear to perform all the loads of the indefinite loop ahead of the store.

In reality the only event that would cause the write buffers to flush, is the thread preemption.


Alex


On 31/12/2014 07:20, Nitsan Wakart wrote:
Re-read the Shipilev "JMM Pragmatics" reference again last night, and discussed with Gil. I think that cup of coffee was nowhere near enough :-). In particular:
"If IUC this means stores and volatile loads are conservatively not reordered" is FALSE because the premise "IUC" is false. I did not understand correctly which leads me to amend my comment:
1. There's technically nothing to stop reordering between the store and load.
>  theLong.lazySet(1L);
>  Object o = theRef.get();
2. There's technically nothing to stop reordering between the store and load.
>  long l = theLong.get() + 1; // LOADLOAD
>  theLong.lazySet(l); //STORESTORE
>  Object o = theRef.get(); // LOADLOAD
3. I still think the while loop presents a different case to normal flow. So for now I still hold that the lazySet cannot be moved after the while loop.

My sincere apologies for the confusion.
Happy holidays to all.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest