Fences API and visibility/coherency

[Dmitriy V'jukov]

Hi,

I am new to this group and to the Java concurrency in general, so
probably I am just missing something obvious. Anyway I will appreciate
if someone will make following moment clear to me.

As far as I understand, Java does not provide any visibility/coherency
guarantees for accesses to plain (non-volatile) variables. I.e.
following code may run forever (right?):

public class StopThread {
  private static boolean stopRequested;
  public static void main(String[] args) throws InterruptedException {
    Thread backgroundThread = new Thread(new Runnable() {
      public void run() {
        int i = 0;
        while (!stopRequested)
          i++;
      }
    });
    backgroundThread.start();
    TimeUnit.SECONDS.sleep(1);
    stopRequested = true;
  }
}

I guess that for volatile variables there are visibility/coherency
guarantees, i.e. volatile stores performed in one thread must
eventually become visible to volatile loads performed in another
thread. (I do not see this in JLS and can not figure this from JVM
Spec Chapter 8, however I am sure that at least there is such
intention. Can somebody point to where such guarantees explicitly
stated for volatiles?)

So the question is: what about visibility/coherency guarantees
regarding Fences API? As far as I see Fences API deals solely with
ordering, but not with visibility. So if I use plain variables +
Fences API, then I get NO visibility/coherency. I.e. for the following
code:

class C {
    Object data;  // need volatile access but not volatile
    // ...
 }

 class App {
   Object getData(C c) {
      return Fences.orderReads(c).data;
   }

   void setData(C c) {
      Object newValue = ...;
      c.data = Fences.orderWrites(newValue);
      Fences.orderAccesses(c);
   }
   // ...
}

there is no guarantee that getData() will eventually see object stored
by setData(). And this renders the whole thing basically useless to
me.
What I am missing?
Thank you.

--
Dmitry Vyukov
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Doug Lea]

Dmitriy V'jukov wrote:

> As far as I understand, Java does not provide any visibility/coherency
> guarantees for accesses to plain (non-volatile) variables. I.e.
> following code may run forever (right?):

Yes. More generally, programs that include non-volatile,
non-final, non-fenced (see below) variables accessed
by multiple threads without locking have poorly defined
behavior. Modulo a few details surrounding thread
creation/termination, etc this is the definition of a
"race condition" for Java. Don't write programs with races.

>
> public class StopThread {
>   private static boolean stopRequested;
>   public static void main(String[] args) throws InterruptedException {
>     Thread backgroundThread = new Thread(new Runnable() {
>       public void run() {
>         int i = 0;
>         while (!stopRequested)
>           i++;
>       }
>     });
>     backgroundThread.start();
>     TimeUnit.SECONDS.sleep(1);
>     stopRequested = true;
>   }
> }
>
> I guess that for volatile variables there are visibility/coherency
> guarantees, i.e. volatile stores performed in one thread must
> eventually become visible to volatile loads performed in another
> thread. (I do not see this in JLS and can not figure this from JVM
> Spec Chapter 8, however I am sure that at least there is such
> intention. Can somebody point to where such guarantees explicitly
> stated for volatiles?)
>

Hiding inside the ordering rules: If a given write must
happen-before a given read, then the results of that write must
be available to the read.

> So the question is: what about visibility/coherency guarantees
> regarding Fences API? As far as I see Fences API deals solely with
> ordering, but not with visibility. So if I use plain variables +
> Fences API, then I get NO visibility/coherency. I.e. for the following
> code:
>

Fences operate at a lower level -- basically programming
directly to the happens-before rules.
A lot of people (including me) don't like this aspect of
Fences. Variables accessed using low-level fences
don't need to be specially marked, which makes correct
use even harder to verify than it might otherwise be.

> class C {
>     Object data;  // need volatile access but not volatile
>     // ...
>  }
>
>  class App {
>    Object getData(C c) {
>       return Fences.orderReads(c).data;
>    }
>
>    void setData(C c) {
>       Object newValue = ...;
>       c.data = Fences.orderWrites(newValue);
>       Fences.orderAccesses(c);
>    }
>    // ...
> }
>
> there is no guarantee that getData() will eventually see object stored
> by setData(). And this renders the whole thing basically useless to
> me.
> What I am missing?

Any thread calling setData must eventually actually write "data",
thus making it  available to some subsequent call to getData
by another thread.

-Doug

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Dmitriy V'jukov]

On Sun, Oct 11, 2009 at 3:21 PM, Doug Lea <dl@...> wrote:

Hi Doug,

> Dmitriy V'jukov wrote:
>
>>
>> public class StopThread {
>>  private static boolean stopRequested;
>>  public static void main(String[] args) throws InterruptedException {
>>    Thread backgroundThread = new Thread(new Runnable() {
>>      public void run() {
>>        int i = 0;
>>        while (!stopRequested)
>>          i++;
>>      }
>>    });
>>    backgroundThread.start();
>>    TimeUnit.SECONDS.sleep(1);
>>    stopRequested = true;
>>  }
>> }
>>
>> I guess that for volatile variables there are visibility/coherency
>> guarantees, i.e. volatile stores performed in one thread must
>> eventually become visible to volatile loads performed in another
>> thread. (I do not see this in JLS and can not figure this from JVM
>> Spec Chapter 8, however I am sure that at least there is such
>> intention. Can somebody point to where such guarantees explicitly
>> stated for volatiles?)
>>
> Hiding inside the ordering rules: If a given write must
> happen-before a given read, then the results of that write must
> be available to the read.

This is another thing, I mean visibility/coherency, not ordering. The
rule you described relates to both volatile and plain variables. BUT
it works IFF there is another volatile write that was already seen by
a thread and already established "happens-before edge" between
threads. My question is about that "top-level" volatile write, its
visibility is NOT guaranteed by any happens-before relations.

For example:

volatile int X = 0;

//thread 1:
X = 1;

// thread 2:
while (X == 0) {} // spin wait

Is there any guarantees regarding when thread 2 will see thread 1
write? You can't refer to ordering/happens-before here, because there
is NO happens-before edges between thread 1 and thread 2 yet.
Happens-before is what we are trying to establish with this write, but
do not have any yet.

>> So the question is: what about visibility/coherency guarantees
>> regarding Fences API? As far as I see Fences API deals solely with
>> ordering, but not with visibility. So if I use plain variables +
>> Fences API, then I get NO visibility/coherency. I.e. for the following
>> code:
>>
>
> Fences operate at a lower level -- basically programming
> directly to the happens-before rules.
> A lot of people (including me) don't like this aspect of
> Fences. Variables accessed using low-level fences
> don't need to be specially marked, which makes correct
> use even harder to verify than it might otherwise be.

Happens-before is about ordering, but what I am interested in is
visibility/coherence. What guarantees regarding visibility/coherence?

>> class C {
>>    Object data;  // need volatile access but not volatile
>>    // ...
>>  }
>>
>>  class App {
>>   Object getData(C c) {
>>      return Fences.orderReads(c).data;
>>   }
>>
>>   void setData(C c) {
>>      Object newValue = ...;
>>      c.data = Fences.orderWrites(newValue);
>>      Fences.orderAccesses(c);
>>   }
>>   // ...
>> }
>>
>> there is no guarantee that getData() will eventually see object stored
>> by setData(). And this renders the whole thing basically useless to
>> me.
>> What I am missing?
>
> Any thread calling setData must eventually actually write "data",
> thus making it  available to some subsequent call to getData
> by another thread.

Ok, this is what I mean. You say that "thread must eventually actually
write", can you point to where it's described in the standard? For
example, for plain stores/loads there is no such guarantee, i.e.
thread perfectly allowed to not do actual writes of non-volatiles
variables (until it's required by ordering), or not do reads from main
memory of plain variables (until it's required by ordering). So it's
unclear to me what guarantees for volatiles and fences and
AtomicXXX.lazySet().


--
Dmitry Vyukov

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Doug Lea]

Dmitriy V'jukov wrote:

>>> class C {
>>>    Object data;  // need volatile access but not volatile
>>>    // ...
>>>  }
>>>
>>>  class App {
>>>   Object getData(C c) {
>>>      return Fences.orderReads(c).data;
>>>   }
>>>
>>>   void setData(C c) {
>>>      Object newValue = ...;
>>>      c.data = Fences.orderWrites(newValue);
>>>      Fences.orderAccesses(c);
>>>   }
>>>   // ...
>>> }
>>>
> Ok, this is what I mean. You say that "thread must eventually actually
> write", can you point to where it's described in the standard? For
> example, for plain stores/loads there is no such guarantee, i.e.
> thread perfectly allowed to not do actual writes of non-volatiles
> variables (until it's required by ordering), or not do reads from main
> memory of plain variables (until it's required by ordering). So it's
> unclear to me what guarantees for volatiles and fences and
> AtomicXXX.lazySet().
>

I agree that the answer is not obvious in the spec. But
you can reason as follows:
1. From JLS sec 17.4.4, the final action of a thread happens-before
(and synchronizes-with) that of any thread joining or waiting for it.
2. Because of the orderAccesses call above, the data write must
happen before the final action of the thread, say t, writing it,
and, inductively, before all other subsequent ordered accesses.
3. So, if t ever terminates and is joined, or performs
any other synchronization, the write will
occur and the read (in some other thread) must see it.

The only cases I know where this reasoning does not apply are for
"daemon" threads that are never joined and never synchronize
in any other way.
In which case they might as well have never run.

-Doug




_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Dmitriy V'jukov]

On Sun, Oct 11, 2009 at 6:42 AM, Doug Lea <dl@...> wrote:

> Dmitriy V'jukov wrote:
>>>>
>>>> class C {
>>>>   Object data;  // need volatile access but not volatile
>>>>   // ...
>>>>  }
>>>>
>>>>  class App {
>>>>  Object getData(C c) {
>>>>     return Fences.orderReads(c).data;
>>>>  }
>>>>
>>>>  void setData(C c) {
>>>>     Object newValue = ...;
>>>>     c.data = Fences.orderWrites(newValue);
>>>>     Fences.orderAccesses(c);
>>>>  }
>>>>  // ...
>>>> }
>>>>
>> Ok, this is what I mean. You say that "thread must eventually actually
>> write", can you point to where it's described in the standard? For
>> example, for plain stores/loads there is no such guarantee, i.e.
>> thread perfectly allowed to not do actual writes of non-volatiles
>> variables (until it's required by ordering), or not do reads from main
>> memory of plain variables (until it's required by ordering). So it's
>> unclear to me what guarantees for volatiles and fences and
>> AtomicXXX.lazySet().
>>
>
> I agree that the answer is not obvious in the spec. But
> you can reason as follows:
> 1. From JLS sec 17.4.4, the final action of a thread happens-before
> (and synchronizes-with) that of any thread joining or waiting for it.
> 2. Because of the orderAccesses call above, the data write must
> happen before the final action of the thread, say t, writing it,
> and, inductively, before all other subsequent ordered accesses.
> 3. So, if t ever terminates and is joined, or performs
> any other synchronization, the write will
> occur and the read (in some other thread) must see it.
>
> The only cases I know where this reasoning does not apply are for
> "daemon" threads that are never joined and never synchronize
> in any other way.
> In which case they might as well have never run.

Sorry, I am still missing something. You explain visibility in a
recursive way, i.e. this is visible if that is visible, and the
problem that I can not have 'that', just 'this'. What I expect to see
is some *inherent* visibility of volatiles (Fences.orderWrites(),
AtomicXXX.lazySet()), i.e. they have to be eventually visible just
because they have to eventually visible. Otherwise IMHO
synchronization primitive is dead broken. If I correctly understand
you, you are saying that if I write a producer-consumer queue it's
formal correctness depends on in what thread push() will be called
(elements can lost if enqueued from daemon thread). Wicked!

Here is more concrete example to consider:

public class StopThread {
  private static volatile int stopRequested;
  public static void main(String[] args) throws InterruptedException {
    Thread backgroundThread = new Thread(new Runnable() {
      public void run() {
        int i = 0;
        while (stopRequested == 0)
          i++;
      }
    });
    backgroundThread.start();
    TimeUnit.SECONDS.sleep(1);
    stopRequested = 1;
    backgroundThread.join();
  }
}

I guess that every sane programmer will expect the program to
terminate. And you state that the program may not terminate, because
volatile write is guaranteed to reach main memory only straight before
join, but join will not happen until main thread see volatile write.
So if both actions (join, volatile write) does not happen together no
rule is violated.

Another example:

class X
{
        Object data;
        void signal(Object o)
        {
                // basically store-release (w/o trailing #StoreLoad)
                data = Fences.orderWrites(o);
        }
       
        Object wait()
        {
                // basically load-acquire
                while (Fences.orderReads(data)) {}
                return Fences.orderReads(c);
        }
};

class App
{
        X x1;
        X x2;
       
        void thread1()
        {
                //...
                x1.signal(new Object ());
                //...
                x2.wait();
                //...
        }

        void thread2()
        {
                //...
                x2.signal(new Object ());
                //...
                x1.wait();
                //...
        }
}

If there are guarantees only regarding ordering, then this example
allowed to deadlock, because store-release is allowed to sink below
load-acquire. I.e. compiler may generate following code:

        void thread1()
        {
                //...
                x2.wait();
                x1.signal(new Object ());
                //...
        }

        void thread2()
        {
                //...
                x1.wait();
                x2.signal(new Object ());
                //...
        }

which is clearly deadlocks.
And if there are guarantees regarding visibility/coherence (i.e.
Fences.orderWrites()/volatile writes/AtomicXXX.lazySet() MUST become
visible to other threads in reasonable (finite) amount of time) then
compiler is disallowed to generate above deadlocking code, because
then it will violate coherence guarantee.

How Java can live w/o such guarantees? Please help me! I am totally lost.

--
Dmitry Vyukov

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Doug Lea]

Dmitriy V'jukov wrote:
> Sorry, I am still missing something. You explain visibility in a recursive
> way, i.e. this is visible if that is visible, and the problem that I can not
> have 'that', just 'this'. What I expect to see is some *inherent* visibility
> of volatiles

A view more in keeping with the JLS is that a write is visible to a
read if the write happens-before/synchronizes-with the read.

Because Java (like most languages/platforms) has no strict
progress guarantees, the write could be stalled indefinitely,
but it will eventually happen before other actions that this
write in turn must happen-before.

Sorry that my further comment seems to have been confusing:

>> The only cases I know where this reasoning does not apply are for "daemon"
>> threads that are never joined and never synchronize in any other way. In
>> which case they might as well have never run.

This was just a side observation of an (uninteresting) possible gap
in the JLS wording -- it seems to officially allow the existence
of daemon threads without any distinguished end-event.
But it is not at all a practical issue. Among other reasons,
because the mere act of terminating involves a bunch of
synchronization.

-Doug



_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[David Holmes-6]

I think there are some tangled lines of communication here ...

Dmitriy V'jukov writes:

> Here is more concrete example to consider:
>
> public class StopThread {
>   private static volatile int stopRequested;
>   public static void main(String[] args) throws InterruptedException {
>     Thread backgroundThread = new Thread(new Runnable() {
>       public void run() {
>         int i = 0;
>         while (stopRequested == 0)
>           i++;
>       }
>     });
>     backgroundThread.start();
>     TimeUnit.SECONDS.sleep(1);
>     stopRequested = 1;
>     backgroundThread.join();
>   }
> }
>
> I guess that every sane programmer will expect the program to
> terminate.

And it will terminate. The volatile write to stopRequested in main() will be seen by the new thread as soon as it happens because of the happens-before ordering established by volatile reads and writes. Because the volatile read of stopRequested exists, the volatile write to it _must_ be made visible before a subsequent read of that variable.

Other synchronization actions - like use of synchronized, and Thread.join() - can establish additional happens-before orderings that cover regular and volatile variables.

Happens-before is not just about ordering but also visibility. The happens-before relation is established by the program code not by runtime dynamics.**

One way happens-before used to be described was like this (consult Java Memory Model website/archives to search this out). In general, every write to a variable is placed into a set of writes for that variable, and a read is permitted to read any value in that set. So for example:

  int x = 0;

   // thread 1     // thread 2

   x = 1;
   x = 2;
                    int y = x;

y could have the value 0, 1 or 2, even if the read of x happened long after the write of 2 into x. By establishing happens-before relationships you remove values from the set of writes so that a subsequent read is constrained in what it returns ie:

  volatile int x = 0;

  //  thread 1    // thread 2
                  int y = x; // (a)  
  x = 1;
                  y = x;  // (b)
  x = 2;
                  y = x; // (c)

each read of x in thread 2 is now guaranteed to see specific values:
(a) y == 0
(b) y == 1
(c) y == 2

As I understand the Fences API, while they are expressed in a way that appears to be order-centric, their semantics are defined in terms of happens-before and so also determines visibility.

I hope this is of some assistance. The Java memory model is a very complex area and definitely not intuitive (for most people anyway - myself included).

** If a compiler/run-time system did an analysis that proved that there was no read of a given volatile variable then it could elide the write to the variable (keeping it in a thread-local register). But in the absence of such analysis the code that a JIT/runtime generates/executes for volatile writes, assumes that there will exist a volatile read somewhere and generates appropriate code: a store to main memory plus whatever memory-synchronization operations might be required for that platform.

Cheers,
David Holmes


_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Dmitriy V'jukov]

On Sun, Oct 11, 2009 at 3:18 PM, David Holmes <davidcholmes@...> wrote:

>
> I think there are some tangled lines of communication here ...
>
> Dmitriy V'jukov writes:
>> Here is more concrete example to consider:
>>
>> public class StopThread {
>>   private static volatile int stopRequested;
>>   public static void main(String[] args) throws InterruptedException {
>>     Thread backgroundThread = new Thread(new Runnable() {
>>       public void run() {
>>         int i = 0;
>>         while (stopRequested == 0)
>>           i++;
>>       }
>>     });
>>     backgroundThread.start();
>>     TimeUnit.SECONDS.sleep(1);
>>     stopRequested = 1;
>>     backgroundThread.join();
>>   }
>> }
>>
>> I guess that every sane programmer will expect the program to
>> terminate.
>
> And it will terminate. The volatile write to stopRequested in main() will be seen by the new thread as soon as it happens because of the happens-before ordering established by volatile reads and writes.

There is no happens-before relations yet. So you can't say that
something it this code happens because of the 'happens-before'. They
are established only when volatile read *by some other reason* returns
value stored by volatile write.


> Because the volatile read of stopRequested exists, the volatile write to it _must_ be made visible before a subsequent read of that variable.

David, as far as I understand, you misunderstand the specifications.
'subsequent' is defined in the specification not by means of wall
clock time. It's defined by synchronization order. Not vise versa. And
there are only weak consistency requirements for synchronization
order.
So, even if load happens after 1 hour by wall clock after write, it
may not be 'subsequent'. And it the case in my example - all (infinite
number of) loads of stopRequested perfectly maybe be NOT subsequent to
store to stopRequested. That's what I am talking about.


> Other synchronization actions - like use of synchronized, and Thread.join() - can establish additional happens-before orderings that cover regular and volatile variables.

I hope that I misunderstand you. Do you actually mean that volatiles
are useless for synchronization (i.e. may not propagate changes) if
not accompanied by periodic use of synchronized or thread joins?


> Happens-before is not just about ordering but also visibility. The happens-before relation is established by the program code not by runtime dynamics.**

As far as I understand happens-before, it's solely about ordering.
Yes, it provides visibility BUT only for dependent state (not
"top-level" accesses). I.e. if you have only 1 volatile store in a
program, there is no happens-before edges yet, so they can guarantee
NOTHING for that store.

> One way happens-before used to be described was like this (consult Java Memory Model website/archives to search this out). In general, every write to a variable is placed into a set of writes for that variable, and a read is permitted to read any value in that set. So for example:
>
>  int x = 0;
>
>   // thread 1     // thread 2
>
>   x = 1;
>   x = 2;
>                    int y = x;
>
> y could have the value 0, 1 or 2, even if the read of x happened long after the write of 2 into x. By establishing happens-before relationships you remove values from the set of writes so that a subsequent read is constrained in what it returns ie:
>
>  volatile int x = 0;
>
>  //  thread 1    // thread 2
>                  int y = x; // (a)
>  x = 1;
>                  y = x;  // (b)
>  x = 2;
>                  y = x; // (c)
>
> each read of x in thread 2 is now guaranteed to see specific values:
> (a) y == 0
> (b) y == 1
> (c) y == 2

Hummm... I'm not sure from what you draw any guarantees for this code.
From mutual disposition of code for 2 threads? And what if I reformat
it in the following way:

volatile int x = 0;
//  thread 1    // thread 2
                 int y = x; // (a)
                 y = x;  // (b)
                 y = x; // (c)
x = 1;
x = 2;

All guarantees disappear now?
David, it's 'subsequent' that is defined by 'happens-before', not vise versa.


>
> As I understand the Fences API, while they are expressed in a way that appears to be order-centric, their semantics are defined in terms of happens-before and so also determines visibility.

Ordering and visibility is completely different things.
Roughly speaking, ordering deals with propagation *of dependent
state*. While visibility deals with first-class propagation of
changes.
For example for producer-consumer queue, ordering is charged with the
following thing: consumer will see correct user data associated with
the queue element. While visibility is charged with: consumer will see
queue element.

If synchronization primitive does not provide any visibility
guarantees it's basically useless, because allows a lot of code to not
take any effect (at least for a long-long time, basically infinity),
and makes some code deadlocking.


> I hope this is of some assistance. The Java memory model is a very complex area and definitely not intuitive (for most people anyway - myself included).
>
> ** If a compiler/run-time system did an analysis that proved that there was no read of a given volatile variable then it could elide the write to the variable (keeping it in a thread-local register). But in the absence of such analysis the code that a JIT/runtime generates/executes for volatile writes, assumes that there will exist a volatile read somewhere and generates appropriate code: a store to main memory plus whatever memory-synchronization operations might be required for that platform.

This is closer. Where is this guarantee in the specification? The
guarantee along the lines of: for volatile store compiler has to
generate write to main memory, and that write must not deviate too
much from program order (i.e. for example, write can't sink below a
loop with large number of iterations). And the same for loads. This
will be something like a guarantee of coherency. But will still not
cover Fences (they work with plain variables, not volatiles).

--
Dmitry Vyukov

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[David Holmes-6]

Dmitriy,

The definition of "happens-before" from the JLS:

17.4.5 Happens-before Order
Two actions can be ordered by a happens-before relationship. If one action happens-
before another, then the first is visible to and ordered before the second.

---

As you can see _visibility_ is very much a part of it.

And happens-before is a relationship established by actions defined in the program source code. If an action A happens-before an action B, and at runtime B occurs subsequent to A, then because there is a happens-before relationship between them, we can deduce certain things from that. For example consider this class:

class VolatileValue {
  static volatile int x = 1;

  static int getX() { return x; }

  static void setX() { x = 42; }
}

The memory model rules tell us that:

"A write to a volatile variable (§8.3.1.4) v synchronizes-with all subsequent
reads of v by any thread (where subsequent is defined according to the synchronization
order)."

Or in simpler, informal, terms: a write to a volatile variable happens-before a subsequent read of that variable.

So suppose thread 1 calls VolatileValue.getX() and thread 2 calls VolatileValue.setX(). We don't know a-priori what order those calls will be made in but we do know the results of getX() for either ordering:
- 1 if the getX() occurs first; and
- 42 if the setX() occurs first

---

I suggest you take further discussion of Java Memory Model fundamentals to the JMM mailing list. My way of expressing things may not be precise enough to aid your understanding, so I'll leave it to one of the formalists there to express things more precisely.

https://mailman.cs.umd.edu/mailman/listinfo/javamemorymodel-discussion

Good luck.

David Holmes

> -----Original Message-----
> From: concurrency-interest-bounces@...
> [mailto:concurrency-interest-bounces@...]On Behalf Of Dmitriy
> V'jukov
> Sent: Monday, 12 October 2009 6:18 PM
> To: dholmes@...
> Cc: Doug Lea; concurrency-interest@...
> Subject: Re: [concurrency-interest] Fences API and visibility/coherency
>
>
> On Sun, Oct 11, 2009 at 3:18 PM, David Holmes
> <davidcholmes@...> wrote:
> >
> > I think there are some tangled lines of communication here ...
> >
> > Dmitriy V'jukov writes:
> >> Here is more concrete example to consider:
> >>
> >> public class StopThread {
> >>   private static volatile int stopRequested;
> >>   public static void main(String[] args) throws InterruptedException {
> >>     Thread backgroundThread = new Thread(new Runnable() {
> >>       public void run() {
> >>         int i = 0;
> >>         while (stopRequested == 0)
> >>           i++;
> >>       }
> >>     });
> >>     backgroundThread.start();
> >>     TimeUnit.SECONDS.sleep(1);
> >>     stopRequested = 1;
> >>     backgroundThread.join();
> >>   }
> >> }
> >>
> >> I guess that every sane programmer will expect the program to
> >> terminate.
> >
> > And it will terminate. The volatile write to stopRequested in
> main() will be seen by the new thread as soon as it happens
> because of the happens-before ordering established by volatile
> reads and writes.
>
> There is no happens-before relations yet. So you can't say that
> something it this code happens because of the 'happens-before'. They
> are established only when volatile read *by some other reason* returns
> value stored by volatile write.
>
>
> > Because the volatile read of stopRequested exists, the volatile
> write to it _must_ be made visible before a subsequent read of
> that variable.
>
> David, as far as I understand, you misunderstand the specifications.
> 'subsequent' is defined in the specification not by means of wall
> clock time. It's defined by synchronization order. Not vise versa. And
> there are only weak consistency requirements for synchronization
> order.
> So, even if load happens after 1 hour by wall clock after write, it
> may not be 'subsequent'. And it the case in my example - all (infinite
> number of) loads of stopRequested perfectly maybe be NOT subsequent to
> store to stopRequested. That's what I am talking about.
>
>
> > Other synchronization actions - like use of synchronized, and
> Thread.join() - can establish additional happens-before orderings
> that cover regular and volatile variables.
>
> I hope that I misunderstand you. Do you actually mean that volatiles
> are useless for synchronization (i.e. may not propagate changes) if
> not accompanied by periodic use of synchronized or thread joins?
>
>
> > Happens-before is not just about ordering but also visibility.
> The happens-before relation is established by the program code
> not by runtime dynamics.**
>
> As far as I understand happens-before, it's solely about ordering.
> Yes, it provides visibility BUT only for dependent state (not
> "top-level" accesses). I.e. if you have only 1 volatile store in a
> program, there is no happens-before edges yet, so they can guarantee
> NOTHING for that store.
>
>
> > One way happens-before used to be described was like this
> (consult Java Memory Model website/archives to search this out).
> In general, every write to a variable is placed into a set of
> writes for that variable, and a read is permitted to read any
> value in that set. So for example:
> >
> >  int x = 0;
> >
> >   // thread 1     // thread 2
> >
> >   x = 1;
> >   x = 2;
> >                    int y = x;
> >
> > y could have the value 0, 1 or 2, even if the read of x
> happened long after the write of 2 into x. By establishing
> happens-before relationships you remove values from the set of
> writes so that a subsequent read is constrained in what it returns ie:
> >
> >  volatile int x = 0;
> >
> >  //  thread 1    // thread 2
> >                  int y = x; // (a)
> >  x = 1;
> >                  y = x;  // (b)
> >  x = 2;
> >                  y = x; // (c)
> >
> > each read of x in thread 2 is now guaranteed to see specific values:
> > (a) y == 0
> > (b) y == 1
> > (c) y == 2
>
> Hummm... I'm not sure from what you draw any guarantees for this code.
> From mutual disposition of code for 2 threads? And what if I reformat
> it in the following way:
>
> volatile int x = 0;
> //  thread 1    // thread 2
>                  int y = x; // (a)
>                  y = x;  // (b)
>                  y = x; // (c)
> x = 1;
> x = 2;
>
> All guarantees disappear now?
> David, it's 'subsequent' that is defined by 'happens-before', not
> vise versa.
>
>
> >
> > As I understand the Fences API, while they are expressed in a
> way that appears to be order-centric, their semantics are defined
> in terms of happens-before and so also determines visibility.
>
> Ordering and visibility is completely different things.
> Roughly speaking, ordering deals with propagation *of dependent
> state*. While visibility deals with first-class propagation of
> changes.
> For example for producer-consumer queue, ordering is charged with the
> following thing: consumer will see correct user data associated with
> the queue element. While visibility is charged with: consumer will see
> queue element.
>
> If synchronization primitive does not provide any visibility
> guarantees it's basically useless, because allows a lot of code to not
> take any effect (at least for a long-long time, basically infinity),
> and makes some code deadlocking.
>
>
> > I hope this is of some assistance. The Java memory model is a
> very complex area and definitely not intuitive (for most people
> anyway - myself included).
> >
> > ** If a compiler/run-time system did an analysis that proved
> that there was no read of a given volatile variable then it could
> elide the write to the variable (keeping it in a thread-local
> register). But in the absence of such analysis the code that a
> JIT/runtime generates/executes for volatile writes, assumes that
> there will exist a volatile read somewhere and generates
> appropriate code: a store to main memory plus whatever
> memory-synchronization operations might be required for that platform.
>
> This is closer. Where is this guarantee in the specification? The
> guarantee along the lines of: for volatile store compiler has to
> generate write to main memory, and that write must not deviate too
> much from program order (i.e. for example, write can't sink below a
> loop with large number of iterations). And the same for loads. This
> will be something like a guarantee of coherency. But will still not
> cover Fences (they work with plain variables, not volatiles).
>
> --
> Dmitry Vyukov
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest@...
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Dmitriy V'jukov]

On Sun, Oct 11, 2009 at 1:47 PM, Doug Lea <dl@...> wrote:

> Dmitriy V'jukov wrote:
>>
>> Sorry, I am still missing something. You explain visibility in a recursive
>> way, i.e. this is visible if that is visible, and the problem that I can
>> not
>> have 'that', just 'this'. What I expect to see is some *inherent*
>> visibility
>> of volatiles
>
> A view more in keeping with the JLS is that a write is visible to a
> read if the write happens-before/synchronizes-with the read.

Arrrgggghhhh!
Please, see my reply to David. I understand that it's much more likely
that it's me who miss something than you and David. But happens-before
may only guarantee visibility of *dependent* state, and there are
always 'top-level' changes that are not covered by any happens-before
edges, they have to propagate on their own w/o any assistance.
It's called 'cache-coherency', or 'coherent system', i.e. changes once
done automatically propagate throughout the system on it's own. And
what I draw from what you and David say, JVM is an abstraction of not
cache coherent machine, i.e. changes do not have to propagate by
itself. And it's totally wicked for me, while programming distributed
cache-coherent machines is hard, programming distributed non
cache-coherent machines is brain-damaging. I thought that Java is
about simplicity in it's memory model...


> Because Java (like most languages/platforms) has no strict
> progress guarantees, the write could be stalled indefinitely,
> but it will eventually happen before other actions that this
> write in turn must happen-before.

I understand that such an abstract specification can't provide exact
timings, and that's not required.
I don't know regarding most languages. But C++ standard just says that:
"Implementations should make atomic stores visible to atomic loads
within a reasonable amount of time."
And it's enough for programs to not deadlock, and to be sure that
atomic stores will not sink below infinite loop.
The same applies to CLI/C#. You may see following discussion with Joe
Duffy (lead of Microsoft Parallel Team):
http://www.bluebytesoftware.com/blog/CommentView,guid,72aaa68e-4cbd-41db-a7ce-ddc64411eafa.aspx
(see comments section)
Basically, Joe said that the program may deadlock.
I said that if the program deadlocks, then the language does not
provide coherency guarantees and is not useful for concurrent
programming. The language must provide coherency guarantees.
Joe said that he consulted with compiler team and they conclude that
the aspect is underspecified and it's serious hole in the language,
and it's actually may lead to deadlocks in 'good' programs that every
sane programmer will expect to not deadlock. As far as I understand
they are going to patch specification and compiler.

Now as for practical aspect.
I believe that the things is not as you said, and every sane language
implementation provides inherent coherency guarantees for volatiles.
I.e. they becomes visible to other threads in reasonable amount of
time on their own. But it's not the case for plain variables. And the
concern is with Fences API because it uses plain variables. So it's
not clear as to whether 'good' program based on Fences allowed to
deadlock or not. For example:

class SingleProducerSingleConsumerQueue; // based on plain vars and Fences API

SingleProducerSingleConsumerQueue queue1;
SingleProducerSingleConsumerQueue queue2;

// thread 1:
queue1.push(new Object());
while (queue2.pop() == null) {}

// thread 2:
queue2.push(new Object());
while (queue1.pop() == null) {}

If methods will be inlined, push to queue may sink below pop, and the
program will deadlock. I do not see anything in the specification that
prevents that.

--
Dmitry Vyukov
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Dmitriy V'jukov]

On Mon, Oct 12, 2009 at 1:37 PM, David Holmes <davidcholmes@...> wrote:

>
> Dmitriy,
>
> The definition of "happens-before" from the JLS:
>
> 17.4.5 Happens-before Order
> Two actions can be ordered by a happens-before relationship. If one action happens-
> before another, then the first is visible to and ordered before the second.
>
> ---
>
> As you can see _visibility_ is very much a part of it.
>
> And happens-before is a relationship established by actions defined in the program source code. If an action A happens-before an action B, and at runtime B occurs subsequent to A, then because there is a happens-before relationship between them, we can deduce certain things from that. For example consider this class:
>
> class VolatileValue {
>  static volatile int x = 1;
>
>  static int getX() { return x; }
>
>  static void setX() { x = 42; }
> }
>
> The memory model rules tell us that:
>
> "A write to a volatile variable (§8.3.1.4) v synchronizes-with all subsequent
> reads of v by any thread (where subsequent is defined according to the synchronization
> order)."
>
> Or in simpler, informal, terms: a write to a volatile variable happens-before a subsequent read of that variable.
>
> So suppose thread 1 calls VolatileValue.getX() and thread 2 calls VolatileValue.setX(). We don't know a-priori what order those calls will be made in but we do know the results of getX() for either ordering:
> - 1 if the getX() occurs first; and
> - 42 if the setX() occurs first

My question basically boils down to: if thread 1 periodically calls
VolatileValue.getX(), and we know by wall clock that thread 2 executed
VolatileValue.setX(), let's say, an hour ago, is there any guarantees
that thread 1 will eventually see 42?
Then, if we will replace volatile by plain var + Fences, what about
guarantees then?
Happens-before has nothing to do with this. Because it's
happens-before that will be determined by the synchronizes-with
relation, and not vise versa. Coherence is a kind of primary thing
here, and ordering is secondary, sort of.


> ---
>
> I suggest you take further discussion of Java Memory Model fundamentals to the JMM mailing list. My way of expressing things may not be precise enough to aid your understanding, so I'll leave it to one of the formalists there to express things more precisely.
>
> https://mailman.cs.umd.edu/mailman/listinfo/javamemorymodel-discussion

Thank you. I will ask my question there. I was just not aware of that
mailing, and seen here some discussions of Fences API.


--
Dmitry Vyukov

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[David Holmes-6]

Taking one last stab at clearing this up ...

Dmitriy V'jukov writes:
> My question basically boils down to: if thread 1 periodically calls
> VolatileValue.getX(), and we know by wall clock that thread 2 executed
> VolatileValue.setX(), let's say, an hour ago, is there any guarantees
> that thread 1 will eventually see 42?

Of course. The first getX() that occurs after setX() will return 42.

> Then, if we will replace volatile by plain var + Fences, what about
> guarantees then?

Assuming the correct Fence method is used - I believe so. The Fences API defines additional happens-before relationships and that will ensure visibility and ordering.

(How this happens is another matter - one of the contention points with the Fences API is that it isn't always obvious which actions need to be handled specially because of a use of the Fences API elsewhere. And I'm not an expert on the Fences API - personally I think its not a good idea.)

> Happens-before has nothing to do with this. Because it's
> happens-before that will be determined by the synchronizes-with
> relation, and not vise versa. Coherence is a kind of primary thing
> here, and ordering is secondary, sort of.

I do not understand why you keep saying things like this - obviously there is some fundamental disconnect here (and I'm not sure what you are meaning by coherence in this context).

The happens-before ordering is defined by JLS 17.4.5. If there is a happens-before relationship between a write of a variable and a subsequent read of that variable, then the read must return the value written. A happens-before relationship can come about in a number of ways including:
a) the variable concerned is volatile
b) the write and read occur within synchronized regions of code that lock the same monitor

and now,

c) the Fences API has been correctly used to introduce a happens-before relationship.

The implementation is responsible for ensuring the memory model is obeyed. So for example, a simple implementation could always write a volatile variable to memory and add whatever platform specific memory synchronization instruction is needed. A hypothetical, sophisticated/complex implementation might only write variables into thread-local locations initially and upon a read of the variable deduce if a happens-before ordering exists that requires that the variable's value be retrieved from one of those thread-local locations.

> Thank you. I will ask my question there. I was just not aware of that
> mailing, and seen here some discussions of Fences API.

Sure. Discussing Fences API on either list is fine - but if there are issues to reconcile concerning the JMM fundamentals it's probably best to do that on the JMM list first.

Cheers,
David


_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Dmitriy V'jukov]

On Tue, Oct 13, 2009 at 8:44 AM, David Holmes <davidcholmes@...> wrote:

>
> Taking one last stab at clearing this up ...
>
> Dmitriy V'jukov writes:
>> My question basically boils down to: if thread 1 periodically calls
>> VolatileValue.getX(), and we know by wall clock that thread 2 executed
>> VolatileValue.setX(), let's say, an hour ago, is there any guarantees
>> that thread 1 will eventually see 42?
>
> Of course. The first getX() that occurs after setX() will return 42.

Definitely. I agree with you. But the problem that "getX() that occurs
after setX()" may never occur. It's not wall-clock time, right?
"After" is defined by "synchronization-order", and
synchronization-order does not care about wall-clock time. So where
are any guarantees that "getX() that occurs after setX()" will ever
occur?


>> Then, if we will replace volatile by plain var + Fences, what about
>> guarantees then?
>
> Assuming the correct Fence method is used - I believe so. The Fences API defines additional happens-before relationships and that will ensure visibility and ordering.

Happens-before is not about visibility in any way, shape or form. It
basically guarantees that if/when you've seen X, then you will see
everything that happened before X. It's just ordering. It does not
guarantee that you will see X itself, and when you will see X.
And what I am talking about is that you may not see X. Ever. So the
guarantee that "if you will see X, then..." totally does not matter,
because it's not guaranteed that you will see X itself.



>
> (How this happens is another matter - one of the contention points with the Fences API is that it isn't always obvious which actions need to be handled specially because of a use of the Fences API elsewhere. And I'm not an expert on the Fences API - personally I think its not a good idea.)
>
>> Happens-before has nothing to do with this. Because it's
>> happens-before that will be determined by the synchronizes-with
>> relation, and not vise versa. Coherence is a kind of primary thing
>> here, and ordering is secondary, sort of.
>
> I do not understand why you keep saying things like this - obviously there is some fundamental disconnect here (and I'm not sure what you are meaning by coherence in this context).

Propagation of changes. Like in "cache coherent system".
If we have variable, and one thread writes to it, the changes have to
propagate to other threads.


> The happens-before ordering is defined by JLS 17.4.5. If there is a happens-before relationship between a write of a variable and a subsequent read of that variable, then the read must return the value written.

There is no happens-before relation between volatile write and
volatile read in my examples.
If you disagree, please prove opposite - you need to prove that read
occurs after write, after as defined by synchronization order, so you
need to prove that so(read, write).
If the things as you said, the proof must exist, right?

My proof is as follows:
There is no happens-before relation between volatile store and
volatile load. So the load always allowed to return initial value of
the variable.

> A happens-before relationship can come about in a number of ways including:
> a) the variable concerned is volatile
> b) the write and read occur within synchronized regions of code that lock the same monitor
>
> and now,
>
> c) the Fences API has been correctly used to introduce a happens-before relationship.
>
> The implementation is responsible for ensuring the memory model is obeyed. So for example, a simple implementation could always write a volatile variable to memory and add whatever platform specific memory synchronization instruction is needed. A hypothetical, sophisticated/complex implementation might only write variables into thread-local locations initially and upon a read of the variable deduce if a happens-before ordering exists that requires that the variable's value be retrieved from one of those thread-local locations.
>
>> Thank you. I will ask my question there. I was just not aware of that
>> mailing, and seen here some discussions of Fences API.
>
> Sure. Discussing Fences API on either list is fine - but if there are issues to reconcile concerning the JMM fundamentals it's probably best to do that on the JMM list first.

Here is my question on javamemorymodel-discussion list (archives
available only for members):
https://mailman.cs.umd.edu/mailman/private/javamemorymodel-discussion/2009-October/000357.html


--
Dmitry Vyukov

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[David Holmes-6]

I think this is going nowhere, or in circles ...

> > Dmitriy V'jukov writes:
> >> My question basically boils down to: if thread 1 periodically calls
> >> VolatileValue.getX(), and we know by wall clock that thread 2 executed
> >> VolatileValue.setX(), let's say, an hour ago, is there any guarantees
> >> that thread 1 will eventually see 42?
> >
> > Of course. The first getX() that occurs after setX() will return 42.
>
>
> Definitely. I agree with you. But the problem that "getX() that occurs
> after setX()" may never occur. It's not wall-clock time, right?
> "After" is defined by "synchronization-order", and
> synchronization-order does not care about wall-clock time. So where
> are any guarantees that "getX() that occurs after setX()" will ever
> occur?

Are you talking about scheduling now? There may not be a guarantee that the thread calling setX() ever actually gets to do that while the other thread periodically calls getX(). But _if_ it does then the result of the getX() that follows that setX() is guaranteed to return 42.

> Happens-before is not about visibility in any way, shape or form.

Again I refer you to the definition of the happens-before ordering in JLS 17.4.5:

"Two actions can be ordered by a happens-before relationship. If one action happens-
before another, then the first is visible to and ordered before the second."

See the word "visible" in there?

> It
> basically guarantees that if/when you've seen X, then you will see
> everything that happened before X. It's just ordering. It does not
> guarantee that you will see X itself, and when you will see X.
> And what I am talking about is that you may not see X. Ever. So the
> guarantee that "if you will see X, then..." totally does not matter,
> because it's not guaranteed that you will see X itself.

Incorrect. If a happens-before relationship exists then the memory model defines what values a read is required to return.

> Propagation of changes. Like in "cache coherent system".
> If we have variable, and one thread writes to it, the changes have to
> propagate to other threads.

But that isn't what the Java Memory Model is trying to define. The old JMM was expressed in terms of working memory and main memory (ie a cache) but that model was inadequate. The new JMM is not expressed in those terms but more abstractly. To quote the JLS again:

"The memory model determines what values can be read at every point in the
program."
 

> > The happens-before ordering is defined by JLS 17.4.5. If there
> is a happens-before relationship between a write of a variable
> and a subsequent read of that variable, then the read must return
> the value written.
>
> There is no happens-before relation between volatile write and
> volatile read in my examples.
> If you disagree, please prove opposite - you need to prove that read
> occurs after write, after as defined by synchronization order, so you
> need to prove that so(read, write).
> If the things as you said, the proof must exist, right?

Of course there is a happens-before relationship in the example: x is a volatile; getX reads it and setX writes it:

"A write to a volatile variable (§8.3.1.4) v synchronizes-with all subsequent
reads of v by any thread (where subsequent is defined according to the synchronization
order)."

"If an action x synchronizes-with a following action y, then we also have hb(x,
y)."

Hence: there is a happens-before relationship between a write of a volatile and a subsequent read of that volatile.

So when getX is subsequent to setX the happens-before relation requires that the value 42 be returned.

QED.

Note I'm not saying when getX must be subsequent to setX, I'm saying _if it is_ subsequent. That is what the JMM defines.

I don't think there is anything else I say beyond continuing to repeat myself here.

David
-----
 

> My proof is as follows:
> There is no happens-before relation between volatile store and
> volatile load. So the load always allowed to return initial value of
> the variable.
>
>
> > A happens-before relationship can come about in a number of
> ways including:
> > a) the variable concerned is volatile
> > b) the write and read occur within synchronized regions of code
> that lock the same monitor
> >
> > and now,
> >
> > c) the Fences API has been correctly used to introduce a
> happens-before relationship.
> >
> > The implementation is responsible for ensuring the memory model
> is obeyed. So for example, a simple implementation could always
> write a volatile variable to memory and add whatever platform
> specific memory synchronization instruction is needed. A
> hypothetical, sophisticated/complex implementation might only
> write variables into thread-local locations initially and upon a
> read of the variable deduce if a happens-before ordering exists
> that requires that the variable's value be retrieved from one of
> those thread-local locations.
> >
> >> Thank you. I will ask my question there. I was just not aware of that
> >> mailing, and seen here some discussions of Fences API.
> >
> > Sure. Discussing Fences API on either list is fine - but if
> there are issues to reconcile concerning the JMM fundamentals
> it's probably best to do that on the JMM list first.
>
> Here is my question on javamemorymodel-discussion list (archives
> available only for members):
> https://mailman.cs.umd.edu/mailman/private/javamemorymodel-discuss

ion/2009-October/000357.html


--
Dmitry Vyukov


_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Dmitriy V'jukov]

On Tue, Oct 13, 2009 at 12:09 PM, David Holmes <davidcholmes@...> wrote:
>
> I think this is going nowhere, or in circles ...

Yes :)
So I hope someone deeply involved in JMM will make things clear...

>
>> > Dmitriy V'jukov writes:
>> >> My question basically boils down to: if thread 1 periodically calls
>> >> VolatileValue.getX(), and we know by wall clock that thread 2 executed
>> >> VolatileValue.setX(), let's say, an hour ago, is there any guarantees
>> >> that thread 1 will eventually see 42?
>> >
>> > Of course. The first getX() that occurs after setX() will return 42.
>>
>>
>> Definitely. I agree with you. But the problem that "getX() that occurs
>> after setX()" may never occur. It's not wall-clock time, right?
>> "After" is defined by "synchronization-order", and
>> synchronization-order does not care about wall-clock time. So where
>> are any guarantees that "getX() that occurs after setX()" will ever
>> occur?
>
> Are you talking about scheduling now? There may not be a guarantee that the thread calling setX() ever actually gets to do that while the other thread periodically calls getX(). But _if_ it does then the result of the getX() that follows that setX() is guaranteed to return 42.

No, I do not mean scheduling, I assume fair scheduler that eventually
schedules ready to run threads.


>> Happens-before is not about visibility in any way, shape or form.
>
> Again I refer you to the definition of the happens-before ordering in JLS 17.4.5:
>
> "Two actions can be ordered by a happens-before relationship. If one action happens-
> before another, then the first is visible to and ordered before the second."
>
> See the word "visible" in there?


Yes, perfectly. But I am trying to get farther "words".
This definition itself does not guarantee visibility of changes to
other threads. The key is the word "if". You know it like "If you have
zillion of $$$, then may not work". Even if the statement is true, it
does not mean that every man on a planet may not work, because the
"if" part is usually not satisfied.
You take as unconditional precondition that there is a happens-before
relation, so "if" part is satisfied, so "then" part guarantees
visibility.
I say that there is no happens-before relations yet, so "if" is not
satisfied, so may not even read "then" part.
In order to establish a happens-before relation volatile read must
return value stored by volatile store. Why volatile load will return
value stored by volatile store? There must be some other reason for
that. You may say that that "other reason" is another happens-before
relation. I will say Ok, and how that other happens-before
established? You may say there is another happens-before relation...
Anyway, there must be some 'top-level' happens-before that is
established by completely different reason.
If you have a chicken, you may get an egg. If you have an egg, you may
get a chicken. But if you have neither chicken nor egg, you have to
get one by other means. For example buy one. And that's what I am
talking about - do Java volatiles allow you to buy your first
happens-before relation? After you have one, yes, you may get another,
but it will be only after.

Let's consider your example:

class VolatileValue {
 static volatile int x = 1;

 static int getX() { return x; }

 static void setX() { x = 42; }
}

As you said, thread 2 may get either 1 or 42. Both variants are
viable. The problem is that thread 2 may get 1 infinite number of
times. Since both variants are viable, implementations may choose
first variant always. Why not? No ordering rules broken here.
From practical/implementation point of view, implementation may allow
the store to sink below infinite loop, or the load to never re-read
value from main memory. In both cases thread 2 will get 1 always.
And only if there are some additional requirements regarding
coherence/visibility (like "volatile stores must be visible to
volatile loads in a reasonable amount of time", just because they
"must" and not because of some ordering rules, ordering rules are not
applicable to this code, because no happens-before relations here yet,
the first happens-before relation will appear only when/if thread 2
will return 42).

>
>> It
>> basically guarantees that if/when you've seen X, then you will see
>> everything that happened before X. It's just ordering. It does not
>> guarantee that you will see X itself, and when you will see X.
>> And what I am talking about is that you may not see X. Ever. So the
>> guarantee that "if you will see X, then..." totally does not matter,
>> because it's not guaranteed that you will see X itself.
>
> Incorrect. If a happens-before relationship exists then the memory model defines what values a read is required to return.

Arrrrghhhh. Your statement is correct, but it is not applicable,
because "if' part is not satisfied.
Happens-before causes visibility of values.
Visibility of values causes happens-before.
It's cycle. And we are talking about situation when you have no
happens-before relations nor any visibility of values. You can't
cyclically refer to one or another. You have to buy any of them first.
Something must happen "out of the thin air", so to say. Happens-before
relations can't appear out of the thin air. So it's visibility of some
value that must happen out of the thin air (store in one thread must
just become visible to load in another thread). And after that, yes,
happens-before relation will be established, it will provide
visibility of other values, etc.

>> Propagation of changes. Like in "cache coherent system".
>> If we have variable, and one thread writes to it, the changes have to
>> propagate to other threads.
>
> But that isn't what the Java Memory Model is trying to define. The old JMM was expressed in terms of working memory and main memory (ie a cache) but that model was inadequate. The new JMM is not expressed in those terms but more abstractly. To quote the JLS again:
>
> "The memory model determines what values can be read at every point in the
> program."
>
>> > The happens-before ordering is defined by JLS 17.4.5. If there
>> is a happens-before relationship between a write of a variable
>> and a subsequent read of that variable, then the read must return
>> the value written.

It's not sufficient guarantees for the language to be useful. Because
if you have only such guarantees, programs may deadlock, or updates
disappear (actually deferred indefinitely, but it's the same from
practical point of view).
Once again, you example with 1 and 42. Ordering rules state that both
values are viable. Always.
The same situation is with C++ memory model. It also says that both
values are viable. But there are additional guarantees that changes
must propagate in a reasonable [wall-clock] time. So 1 and 42 are
viable only for reasonable time, and then only 42 is viable. So it's
guaranteed that a thread will see a signal in a reasonable time, and
then a program will terminate. And Java program is allowed to deadlock
here.

>> There is no happens-before relation between volatile write and
>> volatile read in my examples.
>> If you disagree, please prove opposite - you need to prove that read
>> occurs after write, after as defined by synchronization order, so you
>> need to prove that so(read, write).
>> If the things as you said, the proof must exist, right?
>
> Of course there is a happens-before relationship in the example: x is a volatile; getX reads it and setX writes it:
>
> "A write to a volatile variable (§8.3.1.4) v synchronizes-with all subsequent
> reads of v by any thread (where subsequent is defined according to the synchronization
> order)."
>
> "If an action x synchronizes-with a following action y, then we also have hb(x,
> y)."
>
> Hence: there is a happens-before relationship between a write of a volatile and a subsequent read of that volatile.
>
> So when getX is subsequent to setX the happens-before relation requires that the value 42 be returned.
>
> QED.
>
> Note I'm not saying when getX must be subsequent to setX, I'm saying _if it is_ subsequent. That is what the JMM defines.

Exactly. Now we are on the same page. If it is subsequent. But JMM
says "It's Ok, if they (all loads in the loop) will never become
subsequent to the store, and the program will deadlock".
The key here is that "subsequent" is defined not by wall-clock time,
but only by ordering rules (neither of them established yet). And by
ordering rules both 1 and 42 are always viable.

Yes, we all hope that after an hour of wall clock time volatile store
must be visible to volatile load. I.e. load must become 'subsequent'
to store.
But as far as I see there is not such guarantees in the standard. So
everything is basically held up by sanity of compiler writers.
As for volatiles I am sure that they have enough sanity to not allow
volatile store to sink below infinite loop. However my initial concern
was regarding Fences API. Since Fences API uses plain variables and
the aspect is underspecified, it may just happen so that different
parts of the system (compiler, libraries, virtual machine) will
combine is such a way that store will actually sink below infinite
loop or load will never re-read value from main memory. And then
'good' program will actually deadlock in real life.
It's what actually happen with C#/CLI:
http://www.bluebytesoftware.com/blog/CommentView,guid,72aaa68e-4cbd-41db-a7ce-ddc64411eafa.aspx
"I followed up with several compiler folks at Microsoft (VC++ and CLR
JIT), and the general consensus was: (1) we should explicitly prevent
this kind of reordering from happening for volatiles; (2) it is
insufficiently specified that, yes, it could happen in real life; and,
(3) we should explicitly allow this kind of reordering for
non-volatiles."

--
Dmitry Vyukov

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Dmitriy V'jukov]

On Tue, Oct 13, 2009 at 5:31 PM, Adam Morrison <adamx@...> wrote:

>> Definitely. I agree with you. But the problem that "getX() that occurs
>> after setX()" may never occur. It's not wall-clock time, right?
>> "After" is defined by "synchronization-order", and
>> synchronization-order does not care about wall-clock time. So where
>> are any guarantees that "getX() that occurs after setX()" will ever
>> occur?
>
> You are worried about an infinite execution where for every getX(),
> so(getX, setX).  Such an execution is not allowed by JLS 17.4.8.
> There must be a point where setX() is committed, so only a finite
> number of getX() preceed it in the synchronization order.

Hi Adam,

Thank you, at first glance it looks like what I am looking for.
However I have to re-read that piece a dozen of times or so in order
to understand it fully. I would appreciate if more people confirm or
deny as to whether it's what I am looking for or not (I hope that some
people get what I am looking for).

First concerns:
It's yet unclear as to whether the execution is terminating or not
(that's what we are trying to prove/disprove). So as a next committing
actions we may always choose getX. And then there will be no
contradiction, and we will conclude that it's a correct
NON-terminating program.

It's unclear as to whether volatile load must return value stored by
volatile load if the store was committed before load. Values returned
by volatile load are determined by synchronization-order, and not
committing order.

--
Dmitry Vyukov

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Gregg Wonderly-2]

Dmitriy V'jukov wrote:

> On Tue, Oct 13, 2009 at 12:09 PM, David Holmes <davidcholmes@...> wrote:
>>>> Dmitriy V'jukov writes:
>>> Happens-before is not about visibility in any way, shape or form.
>> Again I refer you to the definition of the happens-before ordering in JLS 17.4.5:
>>
>> "Two actions can be ordered by a happens-before relationship. If one action happens-
>> before another, then the first is visible to and ordered before the second."
>>
>> See the word "visible" in there?
>
>
> Yes, perfectly. But I am trying to get farther "words".
> This definition itself does not guarantee visibility of changes to
> other threads. The key is the word "if". You know it like "If you have
> zillion of $$$, then may not work". Even if the statement is true, it
> does not mean that every man on a planet may not work, because the
> "if" part is usually not satisfied.

I think you are just not invoking useful thought here Dmitriy.  Just consider
the example.

class VolatileValue {
  static volatile int x = 1;

  static int getX() { return x; }

  static void setX() { x = 42; }
}

If one thread does

VolatileValue a = new VolatileValue();
System.out.println( a.getX()+"" );
a.setX();
System.out.println( a.getX()+"" );

Would you not assert that the output would be the following?

1
42

Okay, lets look at why the output is 1 followed by 42.  Is it because getX() was
called once before setX()?  No, the call to getX() before call to setX() has no
effect on what setX() does, nor on what any future call of getX().

The setX() call then happens and the value 42 is written to x.  This is a
happens before edge.  The following call of getX() now returns 42.

In this example, if x was not volatile, we'd get the same results.

Now if we instead write code that does the following:

final VolatileValue a = new VolatileValue();

new Thread( "Reader" ) {
        public void run() {
                while( true )
                        System.out.println(a.getX());
        }
}.start();

new Thread( "Writer" ) {
        public void run() {
                a.setX();
        }
}.start();

Then what is the output of this code?  If the "Writer" thread is ever allowed to
run, than the "moment" after setX() is called, the "Reader" thread's following
getX() call will return 42 from that point forward.  This is a "wall clock"
happens before because there is a moment that it happens.  But we don't talk
about the "moment" because the  "moment" didn't make the change in value.  What
made the change in value to x was the write to a volatile value which caused the
JMM to have to "expose" that write to all subsequent reads.

At some point, there would be a "write" that happens before another "read".  It
is that "event" that the JMM speaks of and is what guarantees the "JMM" part
happens.

The scheduling of the OS, processing of exceptions, correctness of logic and all
the other things on the side, are not part of this issue.

IFF setX() ever gets called, then after that "event" (which has a moment in
time, but that time is not the "event"), all subsequent calls to getX() will
return 42.

Gregg Wonderly
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Joe Bowbeer]

Was this question below about inlining and Fences addressed?

I'm assuming the answer is "no: it would not deadlock" -- because the compiler will recognize Fences as akin to volatile, and as with volatile, the compiler will not allow them to cross-paths during optimization.

I am enjoying this discussion.  There's a nebulous (and expanding) region where optimizing compilers and relaxed JVM specifications compete.  If one needs to impose more order on an execution, latches and phasers and even custom thread schedulers are needed.  Though many Java programmers forget this from time to time, underestimate the optimizer, and rely too naively on the good intentions of the JVM.

Joe

On Mon, Oct 12, 2009 at 3:46 AM, Dmitriy V'jukov wrote:

[...] Now as for practical aspect.
I believe that the things is not as you said, and every sane language
implementation provides inherent coherency guarantees for volatiles.
I.e. they becomes visible to other threads in reasonable amount of
time on their own. But it's not the case for plain variables. And the
concern is with Fences API because it uses plain variables. So it's
not clear as to whether 'good' program based on Fences allowed to
deadlock or not. For example:

class SingleProducerSingleConsumerQueue; // based on plain vars and Fences API

SingleProducerSingleConsumerQueue queue1;
SingleProducerSingleConsumerQueue queue2;

// thread 1:
queue1.push(new Object());
while (queue2.pop() == null) {}

// thread 2:
queue2.push(new Object());
while (queue1.pop() == null) {}

If methods will be inlined, push to queue may sink below pop, and the
program will deadlock. I do not see anything in the specification that
prevents that.

--
Dmitry Vyukov

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[Dmitriy V'jukov]

On Tue, Oct 13, 2009 at 8:39 PM, Adam Morrison <adamx@...> wrote:

>> First concerns:
>> It's yet unclear as to whether the execution is terminating or not
>> (that's what we are trying to prove/disprove). So as a next committing
>> actions we may always choose getX. And then there will be no
>> contradiction, and we will conclude that it's a correct
>> NON-terminating program.
>
> That won't work because then the union of all committed actions is not
> equal to all the actions in the execution.
>
> But there does seem to be a hole in the JLS.  It says that the sequence
> of sets of commited actions for an infinite execution "may be infinite".
> So if it's finite, there must exist an infinite set of committed actions, and
> you can commit all the reads plus the write as a maximal element in the
> synchronization order.
>
> However, it looks like the JMM journal paper closes this hole.  One of the
> conditions for a well-formed execution there is that "the synchronization
> order has an order less than or equal to omega.  This means that for each
> synchronization action x, only a finite number of synchronization actions
> occur before x in the synchronization order."
>
> Link:  http://unladen-swallow.googlecode.com/files/journal.pdf

Arrrggghhhhh. Thank you, Adam. This makes sense for me.

"the synchronization order has an order less than or equal to omega"
basically means that every synchronization action must either not
occur at all (situated after 'hang' action in the program order), or
occur in a finite number of steps. This disallows both volatile store
to sink below infinite loop and volatile load to hoist above infinite
loop. Propagation of changes may still take unreasonable but at least
finite amount of time :)
I guess it's a kind of have to be in the specification, but is absent
by some reason. It's sad.

Further proof is trivial:
"A write to a volatile variable v synchronizes-with all subsequent
reads of v by any thread (where subsequent is defined according to the
synchronization order)"

(side thought: JLS explicitly states that it does not require
underlying scheduler to be fair. But the above requirement is a kind
requires fair scheduler... at least for terminating threads. Because
every terminating thread contains final action, that have to occur in
a finite number of steps. So each other action of such thread has to
occur in a finite number of steps too)

As for JLS 17.4.8. As far as I get form "Discussion" section it's all
about prohibiting "out of the thin air" values. As you correctly
noted, there is no requirement for infinite A to be countable. So
volatile write may be committed after infinite number of volatile
loads.

Ok, now we may back to Fences API.
As far as I see, only Fences.orderAccesses() is a synchronization
action. And orderWrites() and orderReads are not.
I guess that the following:
X = Fences.orderWrites(O);
is equivalent to:
release_fence();
X = O;
Note that X is a plain var here.

So for the following code:

class SingleProducerSingleConsumerQueue; // based on plain vars and
Fences.orderWrites/orderReads

SingleProducerSingleConsumerQueue queue1;
SingleProducerSingleConsumerQueue queue2;

// thread 1:
queue1.push(new Object());
while (queue2.pop() == null) {}

// thread 2:
queue2.push(new Object());
while (queue1.pop() == null) {}

It's quite possible that store to X will sink below infinite loop, and
the program will deadlock.
What I am missing now? :)

--
Dmitry Vyukov

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

[David Holmes-6]

Dmitriy,

As far as I am aware "subsequent" has its English-language meaning of
"occurring afterwards". It is not a special term in the JLS. The phrase
"(where subsequent is defined according to the synchronization order)"
simply means that if you examine the synchronization order (which is a total
order) than an action B is subsequent to an action A if B occurs after A in
the synchronization order. There is no trickery or subtlety here.

When a write to a volatile variable X occurs in one thread, the value
written does not have to become globally visible - it can be tucked into a
register as I've described before. But the next read of that variable, that
occurs after the write (ie subsequent to it) _must_ return the value that
was written _because_ there is a happens-before ordering between them.

David Holmes

> -----Original Message-----
> From: Dmitriy V'jukov [mailto:dvyukov@...]
> Sent: Tuesday, 13 October 2009 10:32 PM
> To: dholmes@...
> Cc: Doug Lea; concurrency-interest@...;
> javamemorymodel-discussion@...
> Subject: Re: [concurrency-interest] Fences API and visibility/coherency
>
>
> On Tue, Oct 13, 2009 at 12:09 PM, David Holmes
> <davidcholmes@...> wrote:
> >
> > I think this is going nowhere, or in circles ...
>
> Yes :)
> So I hope someone deeply involved in JMM will make things clear...
>
>
> >
> >> > Dmitriy V'jukov writes:
> >> >> My question basically boils down to: if thread 1 periodically calls
> >> >> VolatileValue.getX(), and we know by wall clock that thread
> 2 executed
> >> >> VolatileValue.setX(), let's say, an hour ago, is there any
> guarantees
> >> >> that thread 1 will eventually see 42?
> >> >
> >> > Of course. The first getX() that occurs after setX() will return 42.
> >>
> >>
> >> Definitely. I agree with you. But the problem that "getX() that occurs
> >> after setX()" may never occur. It's not wall-clock time, right?
> >> "After" is defined by "synchronization-order", and
> >> synchronization-order does not care about wall-clock time. So where
> >> are any guarantees that "getX() that occurs after setX()" will ever
> >> occur?
> >
> > Are you talking about scheduling now? There may not be a
> guarantee that the thread calling setX() ever actually gets to do
> that while the other thread periodically calls getX(). But _if_
> it does then the result of the getX() that follows that setX() is
> guaranteed to return 42.
>
> No, I do not mean scheduling, I assume fair scheduler that eventually
> schedules ready to run threads.
>
>
> >> Happens-before is not about visibility in any way, shape or form.
> >
> > Again I refer you to the definition of the happens-before
> ordering in JLS 17.4.5:
> >
> > "Two actions can be ordered by a happens-before relationship.
> If one action happens-
> > before another, then the first is visible to and ordered before
> the second."
> >
> > See the word "visible" in there?
>
>
> Yes, perfectly. But I am trying to get farther "words".
> This definition itself does not guarantee visibility of changes to
> other threads. The key is the word "if". You know it like "If you have
> zillion of $$$, then may not work". Even if the statement is true, it
> does not mean that every man on a planet may not work, because the
> "if" part is usually not satisfied.
> You take as unconditional precondition that there is a happens-before
> relation, so "if" part is satisfied, so "then" part guarantees
> visibility.
> I say that there is no happens-before relations yet, so "if" is not
> satisfied, so may not even read "then" part.
> In order to establish a happens-before relation volatile read must
> return value stored by volatile store. Why volatile load will return
> value stored by volatile store? There must be some other reason for
> that. You may say that that "other reason" is another happens-before
> relation. I will say Ok, and how that other happens-before
> established? You may say there is another happens-before relation...
> Anyway, there must be some 'top-level' happens-before that is
> established by completely different reason.
> If you have a chicken, you may get an egg. If you have an egg, you may
> get a chicken. But if you have neither chicken nor egg, you have to
> get one by other means. For example buy one. And that's what I am
> talking about - do Java volatiles allow you to buy your first
> happens-before relation? After you have one, yes, you may get another,
> but it will be only after.
>
> Let's consider your example:
>
> class VolatileValue {
>  static volatile int x = 1;
>
>  static int getX() { return x; }
>
>  static void setX() { x = 42; }
> }
>
> As you said, thread 2 may get either 1 or 42. Both variants are
> viable. The problem is that thread 2 may get 1 infinite number of
> times. Since both variants are viable, implementations may choose
> first variant always. Why not? No ordering rules broken here.
> From practical/implementation point of view, implementation may allow
> the store to sink below infinite loop, or the load to never re-read
> value from main memory. In both cases thread 2 will get 1 always.
> And only if there are some additional requirements regarding
> coherence/visibility (like "volatile stores must be visible to
> volatile loads in a reasonable amount of time", just because they
> "must" and not because of some ordering rules, ordering rules are not
> applicable to this code, because no happens-before relations here yet,
> the first happens-before relation will appear only when/if thread 2
> will return 42).
>
>
> >
> >> It
> >> basically guarantees that if/when you've seen X, then you will see
> >> everything that happened before X. It's just ordering. It does not
> >> guarantee that you will see X itself, and when you will see X.
> >> And what I am talking about is that you may not see X. Ever. So the
> >> guarantee that "if you will see X, then..." totally does not matter,
> >> because it's not guaranteed that you will see X itself.
> >
> > Incorrect. If a happens-before relationship exists then the
> memory model defines what values a read is required to return.
>
> Arrrrghhhh. Your statement is correct, but it is not applicable,
> because "if' part is not satisfied.
> Happens-before causes visibility of values.
> Visibility of values causes happens-before.
> It's cycle. And we are talking about situation when you have no
> happens-before relations nor any visibility of values. You can't
> cyclically refer to one or another. You have to buy any of them first.
> Something must happen "out of the thin air", so to say. Happens-before
> relations can't appear out of the thin air. So it's visibility of some
> value that must happen out of the thin air (store in one thread must
> just become visible to load in another thread). And after that, yes,
> happens-before relation will be established, it will provide
> visibility of other values, etc.
>
>
> >> Propagation of changes. Like in "cache coherent system".
> >> If we have variable, and one thread writes to it, the changes have to
> >> propagate to other threads.
> >
> > But that isn't what the Java Memory Model is trying to define.
> The old JMM was expressed in terms of working memory and main
> memory (ie a cache) but that model was inadequate. The new JMM is
> not expressed in those terms but more abstractly. To quote the JLS again:
> >
> > "The memory model determines what values can be read at every
> point in the
> > program."
> >
> >> > The happens-before ordering is defined by JLS 17.4.5. If there
> >> is a happens-before relationship between a write of a variable
> >> and a subsequent read of that variable, then the read must return
> >> the value written.
>
> It's not sufficient guarantees for the language to be useful. Because
> if you have only such guarantees, programs may deadlock, or updates
> disappear (actually deferred indefinitely, but it's the same from
> practical point of view).
> Once again, you example with 1 and 42. Ordering rules state that both
> values are viable. Always.
> The same situation is with C++ memory model. It also says that both
> values are viable. But there are additional guarantees that changes
> must propagate in a reasonable [wall-clock] time. So 1 and 42 are
> viable only for reasonable time, and then only 42 is viable. So it's
> guaranteed that a thread will see a signal in a reasonable time, and
> then a program will terminate. And Java program is allowed to deadlock
> here.
>
>
>
> >> There is no happens-before relation between volatile write and
> >> volatile read in my examples.
> >> If you disagree, please prove opposite - you need to prove that read
> >> occurs after write, after as defined by synchronization order, so you
> >> need to prove that so(read, write).
> >> If the things as you said, the proof must exist, right?
> >
> > Of course there is a happens-before relationship in the
> example: x is a volatile; getX reads it and setX writes it:
> >
> > "A write to a volatile variable (§8.3.1.4) v synchronizes-with
> all subsequent
> > reads of v by any thread (where subsequent is defined according
> to the synchronization
> > order)."
> >
> > "If an action x synchronizes-with a following action y, then we
> also have hb(x,
> > y)."
> >
> > Hence: there is a happens-before relationship between a write
> of a volatile and a subsequent read of that volatile.
> >
> > So when getX is subsequent to setX the happens-before relation
> requires that the value 42 be returned.
> >
> > QED.
> >
> > Note I'm not saying when getX must be subsequent to setX, I'm
> saying _if it is_ subsequent. That is what the JMM defines.
>
>
> Exactly. Now we are on the same page. If it is subsequent. But JMM
> says "It's Ok, if they (all loads in the loop) will never become
> subsequent to the store, and the program will deadlock".
> The key here is that "subsequent" is defined not by wall-clock time,
> but only by ordering rules (neither of them established yet). And by
> ordering rules both 1 and 42 are always viable.
>
> Yes, we all hope that after an hour of wall clock time volatile store
> must be visible to volatile load. I.e. load must become 'subsequent'
> to store.
> But as far as I see there is not such guarantees in the standard. So
> everything is basically held up by sanity of compiler writers.
> As for volatiles I am sure that they have enough sanity to not allow
> volatile store to sink below infinite loop. However my initial concern
> was regarding Fences API. Since Fences API uses plain variables and
> the aspect is underspecified, it may just happen so that different
> parts of the system (compiler, libraries, virtual machine) will
> combine is such a way that store will actually sink below infinite
> loop or load will never re-read value from main memory. And then
> 'good' program will actually deadlock in real life.
> It's what actually happen with C#/CLI:
> http://www.bluebytesoftware.com/blog/CommentView,guid,72aaa68e-4cb

d-41db-a7ce-ddc64411eafa.aspx
"I followed up with several compiler folks at Microsoft (VC++ and CLR
JIT), and the general consensus was: (1) we should explicitly prevent
this kind of reordering from happening for volatiles; (2) it is
insufficiently specified that, yes, it could happen in real life; and,
(3) we should explicitly allow this kind of reordering for
non-volatiles."

--
Dmitry Vyukov


_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest