Re: atomicity for value types

[forax]

- Mail original -
> De: "John Rose" 
> À: "Remi Forax" 
> Cc: "valhalla-spec-experts" 
> Envoyé: Mercredi 15 Janvier 2020 02:18:07
> Objet: Re: atomicity for value types

> On Jan 14, 2020, at 4:52 PM, Remi Forax  wrote:
>> 
>> In the context of Java, we are already using the term 'atomic', in
>> AtomicInteger, AtomicLong, etc,
> 
> Even more fundamentally, the term “atomic” is in the JLS, JVMS, and JMM
> with the same meaning being proposed here, and *not* subsumed by nor identical
> with “volatile”.
> 
> JMVS 4:
> 
>> Untyped instructions that manipulate the operand stack must treat values of 
>> type
>> long and double as atomic (indivisible).
> 
> JLS 17.7. Non-Atomic Treatment of double and long:
> 
>> Writes and reads of volatile long and double values are always atomic… 
>> Writes to
>> and reads of references are always atomic…
> 
> And JMM has more of the same.
> 
>> and in that case the semantics is volatile + atomic operations (at least 
>> CAS),
>> so i think using atomic or any keyword derived from it will not help to our
>> users to understand the semantics for an inline class.
> 
> So volatile is associated with atomic, but it is not identical.
> You came up with an interesting example of that association,
> the AtomicLong API, but it’s just an association.  Nobody will be
> confused.

I'm confused :)

> 
>> As Doug said, for a VarHandle, the semantics we want is called opaque, so
>> "opaque" is ok for me.
> 
> Opaque has meaning only in the JMM (not for the general public)
> and in that document the term atomic is also more correct.
> 
>> Otherwise, the idea is that you can not cut the loads/stores, so 
>> "indivisible"
>> is also ok.
> 
> The JVMS uses “indivisible” (see above) to amplify the term “atomic”,
> but the primary term is “atomic”.
>

Do you agree that the semantics we want for an inline type that is non 
teareable and the semantics we want for a value with locked operations (locked 
like in LADD) are different ?
I've chosen "indivisible" because is the latin equivalent of atomic (which 
comes from the greak leanguage), but that's not the point, the point is that we 
need two terms given that there are two semantics.

Actually the JDK (package java.util.concurrent.atomic) and the JVMS/JLS 
disagree on what atomic means, this should be fixed too. But it's a collateral 
problem. 

Furthermore, at some point in the future, we will want to propose an inline 
generics that provides locked operations on any values, the natural name for 
this inline class is "Atomic", an Atomic being the unmutable, zero cost 
equivalent of an AtomicLong. This will muddy the water even more.

> — John

Rémi

Re: atomicity for value types

[Martin Buchholz]

I've always felt that it's better to have concurrency properties declared
as part of the type, guided by C++ atomic<>, and VarHandle was a step away
from that (towards concurrency "assembly language").  It's more difficult
in Java where there are no zero-cost user abstractions (yet!).

I'm worried about a hardware dependent performance cliff when the size of
an object grows beyond some word size and locks need to be used.

Java still needs that revised memory model, but it's very difficult to get
right.

Re: atomicity for value types

[Doug Lea]

On 1/14/20 3:43 PM, John Rose wrote:
> On Jan 14, 2020, at 9:11 AM, Doug Lea  > wrote:

>> In which case "__AlwaysOpaque" would be a more accurate term.
> 
> Very interesting!  I guess this is the most relevant definition of opaque:
>   http://gee.cs.oswego.edu/dl/html/j9mm.html#opaquesec
> 
> Doug, in honor of one of your pet expressions, I would have
> preferred to spell this keyword “not-too-tearable”, but
> that’s truly an opaque phrase.


OK; I was concerned that your proposed definition was too strong, but
weaker is fine, because optionally stronger modes can then be accessed
via VarHandles. The term used in JDK9+ memory specs is "bitwise-atomic",
which is one part of Opaque mode (also holding for plain mode <=32bit
and refs). But it is possible and desirable to separate it for sake of
Record types. Perhaps a better term is "integral" (better than
non-tearable). But if we want hyphen-friendly modifiers, just
"bitwise-atomic" works (or __bitwiseAtomic as standin until adopted). As in:

bitwise-atomic inline class Long256 { long v1, v2, v3 ,v4; … }

(Aside: should "bitwise-atomic long" also be a valid type?)

-Doug

Re: atomicity for value types

[John Rose]

On Jan 14, 2020, at 4:52 PM, Remi Forax  wrote:
> 
> In the context of Java, we are already using the term 'atomic', in 
> AtomicInteger, AtomicLong, etc,

Even more fundamentally, the term “atomic” is in the JLS, JVMS, and JMM
with the same meaning being proposed here, and *not* subsumed by nor identical
with “volatile”.

JMVS 4:

> Untyped instructions that manipulate the operand stack must treat values of 
> type long and double as atomic (indivisible).

JLS 17.7. Non-Atomic Treatment of double and long:

> Writes and reads of volatile long and double values are always atomic… Writes 
> to and reads of references are always atomic…

And JMM has more of the same.

> and in that case the semantics is volatile + atomic operations (at least 
> CAS), so i think using atomic or any keyword derived from it will not help to 
> our users to understand the semantics for an inline class.

So volatile is associated with atomic, but it is not identical.
You came up with an interesting example of that association,
the AtomicLong API, but it’s just an association.  Nobody will be
confused.

> As Doug said, for a VarHandle, the semantics we want is called opaque, so 
> "opaque" is ok for me. 

Opaque has meaning only in the JMM (not for the general public)
and in that document the term atomic is also more correct.

> Otherwise, the idea is that you can not cut the loads/stores, so 
> "indivisible" is also ok.

The JVMS uses “indivisible” (see above) to amplify the term “atomic”,
but the primary term is “atomic”.

— John

Re: atomicity for value types

[Remi Forax]

In the context of Java, we are already using the term 'atomic', in 
AtomicInteger, AtomicLong, etc, 
and in that case the semantics is volatile + atomic operations (at least CAS), 
so i think using atomic or any keyword derived from it will not help to our 
users to understand the semantics for an inline class. 

As Doug said, for a VarHandle, the semantics we want is called opaque, so 
"opaque" is ok for me. 

Otherwise, the idea is that you can not cut the loads/stores, so "indivisible" 
is also ok. 

Rémi 

> De: "John Rose" 
> À: "valhalla-spec-experts" 
> Envoyé: Mercredi 15 Janvier 2020 01:40:34
> Objet: Re: atomicity for value types

> On Dec 18, 2019, at 5:46 PM, John Rose < [ mailto:john.r.r...@oracle.com |
> john.r.r...@oracle.com ] > wrote:

>> - Define a contextual keyword “alwaysatomic" (working title 
>> “__AlwaysAtomic”).

> I just referred more carefully to the draft JEP on keyword
> management [ https://openjdk.java.net/jeps/8223002 |
> https://openjdk.java.net/jeps/8223002 ] and
> realize that it guides us toward a so-called “hyphenated
> contextual keyword” in preference to a “unitary contextual
> keyword”. That is, “always-atomic” is more in keeping with
> that document than “alwaysatomic”.

> I do think this looks more jarring than the unitary keyword:

> always-atomic inline class Cursor { … }

> But, that’s only because it’s an early hyphenated keyword,
> which nobody is eye-trained on yet. If we believe that
> hyphenated keywords are the wave of the future, as I do,
> then we should embrace it, rather than the old-school
> unitary token “alwaysatomic”.

> In the prototype I’m using a temporary (unitary contextual) keyword-ato
> __AlwaysAtomic, plus a temporary annotation @__alwaysatomic__.

> In the JVMs the draft of the corresponding modifier bit looks like this:

> ACC_ALWAYSATOMIC 0x0040 Instances of this inline type are never torn.

Re: atomicity for value types

[John Rose]

On Dec 18, 2019, at 5:46 PM, John Rose  wrote:
> 
> - Define a contextual keyword “alwaysatomic" (working title “__AlwaysAtomic”).

I just referred more carefully to the draft JEP on keyword
management https://openjdk.java.net/jeps/8223002 and
realize that it guides us toward a so-called “hyphenated
contextual keyword” in preference to a “unitary contextual
keyword”.  That is, “always-atomic” is more in keeping with
that document than “alwaysatomic”.

I do think this looks more jarring than the unitary keyword:

always-atomic inline class Cursor { … }

But, that’s only because it’s an early hyphenated keyword,
which nobody is eye-trained on yet.  If we believe that
hyphenated keywords are the wave of the future, as I do,
then we should embrace it, rather than the old-school
unitary token “alwaysatomic”.

In the prototype I’m using a temporary (unitary contextual) keyword
__AlwaysAtomic, plus a temporary annotation @__alwaysatomic__.


In the JVMs the draft of the corresponding modifier bit looks like this:

ACC_ALWAYSATOMIC0x0040  Instances of this inline type are never torn.

Re: atomicity for value types

[John Rose]

On Jan 14, 2020, at 9:11 AM, Doug Lea  wrote:
> 
> On 1/13/20 4:44 PM, Tobi Ajila wrote:
>> Hi John
>> 
>> Given that inline types can be flattened there is a possibility that
>> data races will occur in places where users were not expecting it
>> before. So your `__AlwaysAtomic` modifier is a necessary tool as the
>> existing spec will only enforce atomicity for 32bit primitives and
>> references. I just want to confirm if the intention of the
>> __AlwaysAtomic bit on an inline class is only to ensure atomic reads and
>> writes of inline types and that there are no happens-before ordering
>> expectations as there are with the existing volatile modifier on fields.
>> 
> 
> In which case "__AlwaysOpaque" would be a more accurate term.


Very interesting!  I guess this is the most relevant definition of opaque:
  http://gee.cs.oswego.edu/dl/html/j9mm.html#opaquesec

Doug, in honor of one of your pet expressions, I would have
preferred to spell this keyword “not-too-tearable”, but
that’s truly an opaque phrase.

OK, so the above document defines a nice linear scale of four
memory access modes, ordered from weak to strong: Plain,
Opaque, Release/Acquire, and Volatile.  “Any guaranteed
property of a weaker mode, plus more, holds for a stronger
mode.”

For a JIT writer, this means stronger modes will require
additional ordering constraints, in IR and/or as hardware
fence instructions, and perhaps also stronger memory
access instructions.  In the worst case (which we may
see with inline types) library calls may be required
to perform some accesses — plus the space overhead of
control variables for things like seq-locks or mutexes.

The effect of the Plain mode on atomicity is described here:
> Additionally, while Java Plain accesses to int, char, short, float, byte, and 
> reference types are primitively bitwise atomic, for the others, long, double, 
> as well as compound Value Types planned for future JDK releases, it is 
> possible for a racy read to return a value with some bits from a write by one 
> thread, and other bits from another, with unusable results.

Then, Opaque mode tightens up the behavior of Plain mode by
adding Bitwise Atomicity (what I want here), plus three more
guarantees: Per-variable antecedence acyclicity, Coherence,
and Progress.

The document then suggests that these three more guarantees
won’t inconvenience the JIT writer:
> Opaque mode does not directly impose any ordering constraints with respect to 
> other variables beyond Plain mode.

But I think there will might be inconveniences.  Our current prototype
doesn’t mess with STM or HTM, but just buffers every new value
(under always-atomic or volatile) into a freshly allocated heap node,
issues a Release fence, and publishes the node reference into the
relevant 64-bit variable.  The node reference itself is stored in Plain
(Relaxed) mode, not Opaque or Release mode, and subsequent loads
are also relaxed (no IR or HW fences).

What we are doing with this buffering trick is meeting the requirements
of atomicity by using the previously-specified mechanisms for safe
publication (of regular identity classes with final instance variables).
In order to use this trick correctly we need to ensure that the specified
behavior of the always-atomic store does not make additional requirements.

When I look at the HotSpot code, I find that, if I were to classify
loads and stores of always-atomic as always-Opaque, I would find
myself adding more IR constraints than if I simply use the trick of
buffering for safe publication.  Maybe HotSpot is doing some overkill
on Opaque mode (see notes below for evidence of that) but I can’t
help thinking that at least the requirement of Progress (for Opaque)
will require the loop optimizer to take special care with always-Opaque
variables that it would not have to take with merely always-atomic ones.

This is a round-about way of say, “really Opaque? Why not just atomic?”
If I take always-Opaque as the definition I can use a clearly defined
category in upcoming JMM revisions (good!) but OTOH I get knock
on requirements (slow-downs) from that same category (bad!).

It’s  not right to say, “but always-atomic values will *always* be
*slow* as well, so quit complaining about lost optimizations”.
That’s because the JVM will often pack small always-atomic values
into single memory units (64- or 128-bit, whatever the hardware
supports with native atomicity).  In such cases, Plain order has
a real performance benefit relative to Opaque order, yes?

So, in the end, I’d like to call it always-atomic, and leave Opaque
mode as an additional opt-in for these types.

— John

P.S. More background, FTR:

Our intention with always-atomic types is to guarantee a modest
extension of type safety, that combinations of field values which
appear from memory reads will never be different from combinations
that have been created by constructor code (or else they are the default
combination).  This appeal to constructors extends type 

Re: atomicity for value types

[Doug Lea]

On 1/13/20 4:44 PM, Tobi Ajila wrote:
> Hi John
> 
> Given that inline types can be flattened there is a possibility that
> data races will occur in places where users were not expecting it
> before. So your `__AlwaysAtomic` modifier is a necessary tool as the
> existing spec will only enforce atomicity for 32bit primitives and
> references. I just want to confirm if the intention of the
> __AlwaysAtomic bit on an inline class is only to ensure atomic reads and
> writes of inline types and that there are no happens-before ordering
> expectations as there are with the existing volatile modifier on fields.
> 

In which case "__AlwaysOpaque" would be a more accurate term.

-Doug


> For example:
> 
> ```
> __AlwaysAtomic inline class Long256 { long v1, v2, v3 ,v4; … }
> 
> class Example {
> Long256 bigLong;
> int x;
> int y;
> 
> void method() {
> Long256 newLong = new Long256(1, 2, 3, 4);
> 
> x = 1;
> 
> 
> //compiler is still free to re-order write to bigLong with respect
> //to writes to x and y, but the write to bigLong must be done atomically
> bigLong = newLong;
> 
> y = 2;
> }
> }
> ```
> 
> Does this match your expectations?
> 
> The reason I ask is because of the "Protection is “as if” each field
> were volatile" wording in your previous note. Does this only speak to
> the atomicity properties of the volatile modifier? Or do you intend
> further constraints?
> 
> Regards,
> --Tobi
> 
> 
> "valhalla-spec-experts" 
> wrote on 2019/12/18 08:46:42 PM:
> 
>> From: John Rose 
>> To: valhalla-spec-experts 
>> Date: 2019/12/18 08:47 PM
>> Subject: [EXTERNAL] atomicity for value types
>> Sent by: "valhalla-spec-experts" > boun...@openjdk.java.net>
>>
>> In a nutshell, here’s a proposal for value type atomicity:
>>
>> - Define a contextual keyword “alwaysatomic" (working title
> “__AlwaysAtomic”).
>> - It can only occur with “inline” in class declaration.
>> - All instances of the given inline class are protected against races.
>> - Protection is “as if” each field were volatile, “and the same” for
>> array elements.
>> - In the class file the ACC_VOLATILE bit is used (0x0040) to record
>> the keyword.
>> - This bit does not necessarily disable flattening; if the JVM can
>> get away with flattening it should.
>> - The JVM can get away with flattening such values on stack, in
>> registers, and perhaps in final heap variables.
>> - The JVM can get away with flattening such values if they are
>> “naturally atomic”, meaning they can be wholly loaded or stored in
>> one (atomic) hardware instruction.
>>
>> More details to follow.  Here’s a backgrounder I wrote a while ago:
>>
>> INVALID URI REMOVED
>>
> u=http-3A__cr.openjdk.java.net_-7Ejrose_oblog_value-2Dtearing.html=DwIFaQ=jf_iaSHvJObTbx-
>>
> siA1ZOg=erClOruSa3K4FS7XawcTd7k9ZbtVLiryTZ1WIpneMMg=9WXy2DpynXX2sj1FbCiuW127ablyOD_EN13-
>> aS4ug04=dhRZz0Da6RYg45c_b-x6gFBP0sqXC1VtTWP--BDHMS4=
>>
>> — John
>>
>>
> 

Re: atomicity for value types

[Tobi Ajila]

> The only special atomicity properties of volatile I’m
> appealing to are those which apply to long and double.

Thanks for confirming that.

> In effect, if an inline object contains a pointer,
> storing it should include a previous store-store ordering
> constraint, or some other implementation of the JMM
> “freeze” operation at the end of the inline’s constructor.

Given the LW2 spec allows withfield to be used anywhere in the nest, an
inline-type containing a reference could be constructed outside of the
 factory. Should the JMM “freeze” semantics additionally apply to the
withfield bytecode?

--Tobi

> From: John Rose 
> To: Tobi Ajila 
> Cc: valhalla-spec-experts 
> Date: 2020/01/13 05:03 PM
> Subject: [EXTERNAL] Re: atomicity for value types
>
> On Jan 13, 2020, at 1:44 PM, Tobi Ajila  wrote:
> >
> > Hi John
> >
> > Given that inline types can be flattened there is a possibility
> that data races will occur in places where users were not expecting
> it before. So your `__AlwaysAtomic` modifier is a necessary tool as
> the existing spec will only enforce atomicity for 32bit primitives
> and references. I just want to confirm if the intention of the
> __AlwaysAtomic bit on an inline class is only to ensure atomic reads
> and writes of inline types and that there are no happens-before
> ordering expectations as there are with the existing volatile
> modifier on fields.
>
> Confirmed; thanks for taking the time to raise the question clearly.
>
> It really isn’t “always volatile”; that would be a different and much
less
> useful feature.
>
> > For example:
> >
> > ```
> > __AlwaysAtomic inline class Long256 { long v1, v2, v3 ,v4; … }
> >
> > class Example {
> > Long256 bigLong;
> > int x;
> > int y;
> >
> > void method() {
> > Long256 newLong = new Long256(1, 2, 3, 4);
> >
> > x = 1;
> >
> > //compiler is still free to re-order write to bigLong with respect
> > //to writes to x and y, but the write to bigLong must be done
atomically
> > bigLong = newLong;
> >
> > y = 2;
> > }
> > }
> > ```
> >
> > Does this match your expectations?
>
> Yes, it does.
>
> > The reason I ask is because of the "Protection is “as if” each
> field were volatile" wording in your previous note. Does this only
> speak to the atomicity properties of the volatile modifier? Or do
> you intend further constraints?
>
> No further constraints beyond simple atomicity of the individual
> load or store.  In particular no new ordering constraints with other
> loads or stores.
>
> The only special atomicity properties of volatile I’m appealing to
> are those which apply to long and double.  Those are the properties
> I am seeking to extend to value types, both those marked “volatile”
> at the use site of the type, and those marked “alwaysatomic” at the
> declaration site of the type.
>
> But now that you ask… there are *old* ordering constraints which
> are relevant.
>
> I expect, because an inline type’s fields are always final, that
> storing an inline value containing a pointer to a new object will
> safely publish that new object.  This rule in the JMM may need
> to be clarified.  In effect, if an inline object contains a pointer,
> storing it should include a previous store-store ordering
> constraint, or some other implementation of the JMM
> “freeze” operation at the end of the inline’s constructor.
>
> Make sense?
>
> — John
>
> P.S.  After writing unit tests for “alwaysatomic” I found tearing
> race conditions in HotSpot which were wrong for all inline types,
> and not just “alwaysatomic”.  In particular, if the JVM ever secretly
> buffers a value onto the heap, it should issue a store-store barrier
> before publishing the secret reference.  This may happen, for example,
> when an inline value is stored in an Object variable.  I’m mentioning
> this in case you have a similar issue in J9.  We had enough complicated
> paths in the HotSpot prototype that in some cases the store-store
> barrier was not being emitted, causing wrong execution.
>
> See also this thread about surprise tearing, and why it’s wrong:
>
> https://urldefense.proofpoint.com/v2/url?
>
u=http-3A__mail.openjdk.java.net_pipermail_valhalla-2Ddev_2020-2DJanuary_006706.html=DwIFaQ=jf_iaSHvJObTbx-

>
siA1ZOg=erClOruSa3K4FS7XawcTd7k9ZbtVLiryTZ1WIpneMMg=uSBdbgpyj81Z9PT43WizJufMTVJq-

> YMA3jDRYV1Fpr0=X9LNJxyH8Z8b1-Kfti4O4yQB-cmMxA3PwXIPvhoP55o=

Re: atomicity for value types

[Tobi Ajila]

Hi John

Given that inline types can be flattened there is a possibility that data
races will occur in places where users were not expecting it before. So
your `__AlwaysAtomic` modifier is a necessary tool as the existing spec
will only enforce atomicity for 32bit primitives and references. I just
want to confirm if the intention of the __AlwaysAtomic bit on an inline
class is only to ensure atomic reads and writes of inline types and that
there are no happens-before ordering expectations as there are with the
existing volatile modifier on fields.

For example:

```
__AlwaysAtomic inline class Long256 { long v1, v2, v3 ,v4;  … }

class Example {
Long256 bigLong;
int x;
int y;

void method() {
Long256 newLong = new Long256(1, 2, 3, 4);

x = 1;

//compiler is still free to re-order write to bigLong with
respect
//to writes to x and y, but the write to bigLong must be done
atomically
bigLong = newLong;

y = 2;
}
}
```

Does this match your expectations?

The reason I ask is because of the "Protection is “as if” each field were
volatile" wording in your previous note. Does this only speak to the
atomicity properties of the volatile modifier? Or do you intend further
constraints?

Regards,
--Tobi


"valhalla-spec-experts" 
wrote on 2019/12/18 08:46:42 PM:

> From: John Rose 
> To: valhalla-spec-experts 
> Date: 2019/12/18 08:47 PM
> Subject: [EXTERNAL] atomicity for value types
> Sent by: "valhalla-spec-experts"  boun...@openjdk.java.net>
>
> In a nutshell, here’s a proposal for value type atomicity:
>
> - Define a contextual keyword “alwaysatomic" (working title
“__AlwaysAtomic”).
> - It can only occur with “inline” in class declaration.
> - All instances of the given inline class are protected against races.
> - Protection is “as if” each field were volatile, “and the same” for
> array elements.
> - In the class file the ACC_VOLATILE bit is used (0x0040) to record
> the keyword.
> - This bit does not necessarily disable flattening; if the JVM can
> get away with flattening it should.
> - The JVM can get away with flattening such values on stack, in
> registers, and perhaps in final heap variables.
> - The JVM can get away with flattening such values if they are
> “naturally atomic”, meaning they can be wholly loaded or stored in
> one (atomic) hardware instruction.
>
> More details to follow.  Here’s a backgrounder I wrote a while ago:
>
> https://urldefense.proofpoint.com/v2/url?
>
u=http-3A__cr.openjdk.java.net_-7Ejrose_oblog_value-2Dtearing.html=DwIFaQ=jf_iaSHvJObTbx-

>
siA1ZOg=erClOruSa3K4FS7XawcTd7k9ZbtVLiryTZ1WIpneMMg=9WXy2DpynXX2sj1FbCiuW127ablyOD_EN13-

> aS4ug04=dhRZz0Da6RYg45c_b-x6gFBP0sqXC1VtTWP--BDHMS4=
>
> — John
>
>