Reordering of plain vars/volatiles and benign data races

[Dmitriy V'jukov]

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

> 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.

Btw, Doug,

I have an additional question and it will also provide a context for
the original question regarding visibility/coherence.

I've had a discussion on Russian forum (all in Russian, so links will
not make any sense) regarding possible reorderings of plain
vars/volatiles.
Here is it's essence:
him: Plain store can not sink below volatile store, but may hoist
above volatile store (referring to your "Cookbook for Compiler
Writers").
me: No, you must not write programs with data races, and for data race
free programs JMM guarantees sequential consistency, i.e. not
reorderings ever!
him: But there is a well-known data races in standard String class
regarding hash calculation.
me: Well, language standard does not operate in terms of 'good' and
'bad', it only defines semantics. So if you are 200% sure what you are
doing, and standard guarantees behaviour that you need for your racy
program, then, well, correct behaviour is guaranteed, what else to
add?
me: But then, if we are considering racy programs, you may observe
basically any reordering, not just "plain store may hoist above
volatile store". You even may "observe" (if you will reason from
"thread interleaving" point of view) that plain store sinked below
volatile store.

May you comment on this? Why you say "Don't write programs with
races"? What caveats here (besides extreme complexity)? In the end
"racy string hash calculation" is recognized as legal, right?

After some thinking I added:
If you use plain vars for synchronization, it's unclear for me
regarding coherence/visibility guarantees. Let's assume that ordering
is not required in particular situation. If you will use volatiles for
synchronization, updates will eventually propagate between threads.
But if you use plain vars then, I guess, there are no guarantees that
updates will propagate between threads. So if you "raise a signal" or
"enqueue an item into a queue", other threads may not ever see that.
This significantly reduces usefulness of plain vars for
synchronization.

After that I've thought: and what about Fences API? It provides only
ordering guarantees and uses plain vars, so probably there are no
guarantees of coherence/visibility for Fences API too (and I guess
AtomicXXX.lazySet(), because it's a kind of 'not volatile'). And this
makes them basically useless for synchronization (one may get
deadlocks, or changes may just effectively 'disappear').

Please, make my mind clear on this. I am not throlling.
I am more familiar with C++ memory model, and in C++ following program:

int main()
{
  std::atomic<bool> flag (false);
  std::thread th ([&]()
  {
        flag = true;
  });
  while (flag == false) {}
  th.join();
}

also allowed to deadlock IF one considers only ordering rules
(synchronizaes-with, happens-before relations). But the cornerstone is
the following rule:
"Implementations should make atomic stores visible to atomic loads
within a reasonable amount of time"
If we will take this rule into account, then we may conclude: store to
flag will be visible to load in a reasonable amount of time (note, no
ordering/happens-before involved here), after that reasonable amount
of time main thread will stop spinning, join worker thread, and exit.
QED.

So I am looking for similar rule for Java volatiles.
And then want to make my mind clear regarding Fences API (in what way
coherency guaranteed for Fences API, since rules for volatiles do not
applicable to it).

Thank you.

--
Dmitry Vyukov
_______________________________________________
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:

> 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.

Btw, Doug,

I have an additional question and it will also provide a context for
the original question regarding visibility/coherence.

I've had a discussion on Russian forum (all in Russian, so links will
not make any sense) regarding possible reorderings of plain
vars/volatiles.
Here is it's essence:
him: Plain store can not sink below volatile store, but may hoist
above volatile store (referring to your "Cookbook for Compiler
Writers").
me: No, you must not write programs with data races, and for data race
free programs JMM guarantees sequential consistency, i.e. not
reorderings ever!
him: But there is a well-known data races in standard String class
regarding hash calculation.
me: Well, language standard does not operate in terms of 'good' and
'bad', it only defines semantics. So if you are 200% sure what you are
doing, and standard guarantees behaviour that you need for your racy
program, then, well, correct behaviour is guaranteed, what else to
add?
me: But then, if we are considering racy programs, you may observe
basically any reordering, not just "plain store may hoist above
volatile store". You even may "observe" (if you will reason from
"thread interleaving" point of view) that plain store sinked below
volatile store.

May you comment on this? Why you say "Don't write programs with
races"? What caveats here (besides extreme complexity)? In the end
"racy string hash calculation" is recognized as legal, right?

After some thinking I added:
If you use plain vars for synchronization, it's unclear for me
regarding coherence/visibility guarantees. Let's assume that ordering
is not required in particular situation. If you will use volatiles for
synchronization, updates will eventually propagate between threads.
But if you use plain vars then, I guess, there are no guarantees that
updates will propagate between threads. So if you "raise a signal" or
"enqueue an item into a queue", other threads may not ever see that.
This significantly reduces usefulness of plain vars for
synchronization.

After that I've thought: and what about Fences API? It provides only
ordering guarantees and uses plain vars, so probably there are no
guarantees of coherence/visibility for Fences API too (and I guess
AtomicXXX.lazySet(), because it's a kind of 'not volatile'). And this
makes them basically useless for synchronization (one may get
deadlocks, or changes may just effectively 'disappear').

Please, make my mind clear on this. I am not throlling.
I am more familiar with C++ memory model, and in C++ following program:

int main()
{
 std::atomic<bool> flag (false);
 std::thread th ([&]()
 {
       flag = true;
 });
 while (flag == false) {}
 th.join();
}

also allowed to deadlock IF one considers only ordering rules
(synchronizaes-with, happens-before relations). But the cornerstone is
the following rule:
"Implementations should make atomic stores visible to atomic loads
within a reasonable amount of time"
If we will take this rule into account, then we may conclude: store to
flag will be visible to load in a reasonable amount of time (note, no
ordering/happens-before involved here), after that reasonable amount
of time main thread will stop spinning, join worker thread, and exit.
QED.

So I am looking for similar rule for Java volatiles.
And then want to make my mind clear regarding Fences API (in what way
coherency guaranteed for Fences API, since rules for volatiles do not
applicable to it).

Thank you.

--
Dmitry Vyukov

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

[Boehm, Hans]

 

> -----Original Message-----
> From: concurrency-interest-bounces@...
> [mailto:concurrency-interest-bounces@...] On Behalf
> Of Dmitriy V'jukov
> Sent: Tuesday, October 13, 2009 3:56 AM
> To: Doug Lea
> Cc: concurrency-interest@...; dholmes@...;
> JavaMemoryModel@...
> Subject: [concurrency-interest] Reordering of plain
> vars/volatiles and benign data races
>
> On Sun, Oct 11, 2009 at 3:21 PM, Doug Lea <dl@...> wrote:
> > 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.
>
>
> Btw, Doug,
>
> I have an additional question and it will also provide a
> context for the original question regarding visibility/coherence.
>
> I've had a discussion on Russian forum (all in Russian, so
> links will not make any sense) regarding possible reorderings
> of plain vars/volatiles.
> Here is it's essence:
> him: Plain store can not sink below volatile store, but may
> hoist above volatile store (referring to your "Cookbook for
> Compiler Writers").
> me: No, you must not write programs with data races, and for
> data race free programs JMM guarantees sequential
> consistency, i.e. not reorderings ever!
> him: But there is a well-known data races in standard String
> class regarding hash calculation.
> me: Well, language standard does not operate in terms of
> 'good' and 'bad', it only defines semantics. So if you are
> 200% sure what you are doing, and standard guarantees
> behaviour that you need for your racy program, then, well,
> correct behaviour is guaranteed, what else to add?
> me: But then, if we are considering racy programs, you may
> observe basically any reordering, not just "plain store may
> hoist above volatile store". You even may "observe" (if you
> will reason from "thread interleaving" point of view) that
> plain store sinked below volatile store.
>
> May you comment on this? Why you say "Don't write programs
> with races"? What caveats here (besides extreme complexity)?
> In the end "racy string hash calculation" is recognized as
> legal, right?
>
> After some thinking I added:
> If you use plain vars for synchronization, it's unclear for
> me regarding coherence/visibility guarantees. Let's assume
> that ordering is not required in particular situation. If you
> will use volatiles for synchronization, updates will
> eventually propagate between threads.
> But if you use plain vars then, I guess, there are no
> guarantees that updates will propagate between threads. So if
> you "raise a signal" or "enqueue an item into a queue", other
> threads may not ever see that.
> This significantly reduces usefulness of plain vars for
> synchronization.
>
> After that I've thought: and what about Fences API? It
> provides only ordering guarantees and uses plain vars, so
> probably there are no guarantees of coherence/visibility for
> Fences API too (and I guess AtomicXXX.lazySet(), because it's
> a kind of 'not volatile'). And this makes them basically
> useless for synchronization (one may get deadlocks, or
> changes may just effectively 'disappear').
>
> Please, make my mind clear on this. I am not throlling.
> I am more familiar with C++ memory model, and in C++
> following program:
>
> int main()
> {
>   std::atomic<bool> flag (false);
>   std::thread th ([&]()
>   {
> flag = true;
>   });
>   while (flag == false) {}
>   th.join();
> }
>
> also allowed to deadlock IF one considers only ordering rules
> (synchronizaes-with, happens-before relations). But the
> cornerstone is the following rule:
> "Implementations should make atomic stores visible to atomic
> loads within a reasonable amount of time"
> If we will take this rule into account, then we may conclude:
> store to flag will be visible to load in a reasonable amount
> of time (note, no ordering/happens-before involved here),
> after that reasonable amount of time main thread will stop
> spinning, join worker thread, and exit.
> QED.
>
> So I am looking for similar rule for Java volatiles.
> And then want to make my mind clear regarding Fences API (in
> what way coherency guaranteed for Fences API, since rules for
> volatiles do not applicable to it).
>
> Thank you.
>
> --
> Dmitry Vyukov

I'm not Doug, but ...

The Java memory model, unlike C++, does allow some races on ordinary variables.  It has to, since malicious sandboxed code may introduce races.  The problems with this are currently:

- Extreme complexity, both in writing the code, and in understanding the spec.

- People have recently discovered that the spec has some technical problems.  (See Sevcik and Aspinall, ECOOP 2008.)  It unexpectedly forbids some common optimizations.  (I.e. after you understand the complex spec, don't trust it 100% :-).  Fortunately, you are unlikely to encounter the problems.)  It is well understood that this is not good.  But there seem to be no painless and complete solutions.  Some of us are working on rather drastic ones.

The JMM guarantees sequential consistency for data-race-free programs.  This does not prohibt ordinary accesses from getting hoisted above volatile stores, for example.  A race-free program can't tell the difference.  This fact is important to get good performance.

If you do program with data races in Java the more complex rules you will have to deal with continue to allow hoisting above volatile stores.  The results no longer look anything like sequential consistency.

(Java ordinary variables behave a bit like memory_order_relaxed atomics in C++, only with even weaker properties, e.g. accesses to a single location may appear to be reordered, and long and double accesses are not indivisble.)

Hans

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