8145539: (coll) AbstractMap.keySet and .values should not be volatile

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

8145539: (coll) AbstractMap.keySet and .values should not be volatile

Volker.Borchert
Sorry if this is inappropiate here...

I'm just browsing 1.8.0_92 release notes and the following question arose.

http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/ce72c7641f38 states

+     * <p>It is also imperative that implementations read the field only once,
+     * as in:
+     *
+     * <pre> {@code
+     * public Set<K> keySet() {
+     *   Set<K> ks = keySet;  // single racy read
+     *   if (ks == null) {
+     *     ks = new KeySet();
+     *     keySet = ks;
+     *   }
+     *   return ks;
+     * }
+     *}</pre>

and changed

--- a/src/java.base/share/classes/java/util/TreeMap.java Thu Dec 17 20:42:01 2015 +0300
+++ b/src/java.base/share/classes/java/util/TreeMap.java Thu Dec 17 21:14:58 2015 +0300
@@ -852,7 +852,11 @@
      */
     public Collection<V> values() {
         Collection<V> vs = values;
-        return (vs != null) ? vs : (values = new Values());
+        if (vs == null) {
+            vs = new Values();
+            values = vs;
+        }
+        return vs;
     }
 
     /**

but

    public NavigableSet<K> navigableKeySet() {
        KeySet<K> nks = navigableKeySet;
        return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
    }

remained unchanged, with navigableKeySet also non-volatile, so I'd think
the comment above would apply. (Similar for entrySet() and descendingMap().)

What am I missing?

        vb

////////////////////////////////////////////////////////////////////

ATIS systems GmbH
Sitz: Bad Homburg
Registergericht: Bad Homburg HRB 1514
Geschaeftsfuehrer: Stefan Diepolder, Daniel Sieh
 
________________________________________________________________________________________________

This message is confidential. It may also be privileged or otherwise protected by work product immunity or other legal rules. If you have received this message by mistake please let us know by reply and then delete it from your system; you should not copy it or disclose its contents to anyone. All messages sent to and from ATIS systems GmbH may be monitored to ensure compliance with internal policies and to protect our business. E-Mails are not secure and cannot be guaranteed to be error free as they can be intercepted, amended, lost or destroyed. Anyone who communicates with us by e-mail is taken to accept these risks.




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

Re: 8145539: (coll) AbstractMap.keySet and .values should not be volatile

Aleksey Shipilev-2
On 04/20/2016 03:01 PM, [hidden email] wrote:
> I'm just browsing 1.8.0_92 release notes and the following question arose.
>
> http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/ce72c7641f38 states

...

> but
>
>     public NavigableSet<K> navigableKeySet() {
>         KeySet<K> nks = navigableKeySet;
>         return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
>     }
>
> remained unchanged, with navigableKeySet also non-volatile, so I'd think
> the comment above would apply. (Similar for entrySet() and descendingMap().)
>
> What am I missing?
The block in navigableKeySet() is semantically the same as suggested in
the Javadoc: it reads the non-volatile $navigableKeySet exactly once.
The patch changed keySet() and values() that were doing two racy reads.

Thanks,
-Aleksey


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

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: 8145539: (coll) AbstractMap.keySet and .values should not be volatile

Volker.Borchert
In reply to this post by Volker.Borchert
> The block in navigableKeySet() is semantically the same as suggested in
> the Javadoc: it reads the non-volatile $navigableKeySet exactly once.

Sorry, I can't see the difference between

        KeySet<K> nks = navigableKeySet;
        return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));

and

        NavigableMap<K, V> km = descendingMap;
        return (km != null) ? km : (descendingMap = new DescendingSubMap<>(this, ...));

and

        EntrySet es = entrySet;
        return (es != null) ? es : (entrySet = new EntrySet());

and

        Collection<V> vs = values;
        return (vs != null) ? vs : (values = new Values());

but only the last one was changed. Am I just routine-blinded?

> The patch changed keySet() and values() that were doing two racy reads.

TreeMap.keySet() delegates to navigableKeySet() so the patch to AbstractMap
won't affect it.

Regards

        vb

////////////////////////////////////////////////////////////////////

ATIS systems GmbH
Sitz: Bad Homburg
Registergericht: Bad Homburg HRB 1514
Geschaeftsfuehrer: Stefan Diepolder, Daniel Sieh
 
________________________________________________________________________________________________

This message is confidential. It may also be privileged or otherwise protected by work product immunity or other legal rules. If you have received this message by mistake please let us know by reply and then delete it from your system; you should not copy it or disclose its contents to anyone. All messages sent to and from ATIS systems GmbH may be monitored to ensure compliance with internal policies and to protect our business. E-Mails are not secure and cannot be guaranteed to be error free as they can be intercepted, amended, lost or destroyed. Anyone who communicates with us by e-mail is taken to accept these risks.




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

Re: 8145539: (coll) AbstractMap.keySet and .values should not be volatile

Aleksey Shipilev-2
On 04/20/2016 04:50 PM, [hidden email] wrote:
>> The block in navigableKeySet() is semantically the same as suggested in
>> the Javadoc: it reads the non-volatile $navigableKeySet exactly once.

...

> but only the last one was changed. Am I just routine-blinded?
>
>> The patch changed keySet() and values() that were doing two racy reads.
>
> TreeMap.keySet() delegates to navigableKeySet() so the patch to AbstractMap
> won't affect it.

Sorry, I should have meant AbstractMap.keySet() and values(). Those were
broken under non-volatile keySet/values fields.

Others were merely a style/readability rewrites to match the suggested
use: avoiding inline assignments makes reasoning about load/stores
easier. We are quite probably missing those style tuneups in other
places, but this does not affect correctness.

-Aleksey


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

signature.asc (853 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: 8145539: (coll) AbstractMap.keySet and .values should not be volatile

Volker.Borchert
In reply to this post by Volker.Borchert
> Sorry, I should have meant AbstractMap.keySet() and values(). Those were
> broken under non-volatile keySet/values fields.
>
> Others were merely a style/readability rewrites to match the suggested
> use: avoiding inline assignments makes reasoning about load/stores
> easier. We are quite probably missing those style tuneups in other
> places, but this does not affect correctness.

(browse 1.8.0_77 source)

I see. Thank you.

        vb

////////////////////////////////////////////////////////////////////

ATIS systems GmbH
Sitz: Bad Homburg
Registergericht: Bad Homburg HRB 1514
Geschaeftsfuehrer: Stefan Diepolder, Daniel Sieh
 
________________________________________________________________________________________________

This message is confidential. It may also be privileged or otherwise protected by work product immunity or other legal rules. If you have received this message by mistake please let us know by reply and then delete it from your system; you should not copy it or disclose its contents to anyone. All messages sent to and from ATIS systems GmbH may be monitored to ensure compliance with internal policies and to protect our business. E-Mails are not secure and cannot be guaranteed to be error free as they can be intercepted, amended, lost or destroyed. Anyone who communicates with us by e-mail is taken to accept these risks.




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

Re: 8145539: (coll) AbstractMap.keySet and .values should not be volatile

thurstonn
In reply to this post by Aleksey Shipilev-2
Just curious,

has anyone actually observed a real JVM returning null in the original, racy code?
I realize the JMM allows it, but I'd be surprised that a JVM would reorder reads of the *same* memory location

Reply | Threaded
Open this post in threaded view
|

Re: 8145539: (coll) AbstractMap.keySet and .values should not be volatile

Vitaly Davidovich
The problem is compilers can do weird things on the assumption of data race free code.  If you haven't seen https://software.intel.com/en-us/blogs/2013/01/06/benign-data-races-what-could-possibly-go-wrong, I recommend reading it.  It's in the context of C/C++/Go but the general point stands.

In this case, compiler can arrange a read of the field into a register/stack slot - assume it reads null.  Later it re-tests the field (memory), sees non null, but returns the register/stack slot value.  It's weird, but legal.  Whether it happens I don't know, but you likely don't want to find out :).

On Monday, April 25, 2016, thurstonn <[hidden email]> wrote:
Just curious,

has anyone actually observed a real JVM returning null in the original, racy
code?
I realize the JMM allows it, but I'd be surprised that a JVM would reorder
reads of the *same* memory location





--
View this message in context: http://jsr166-concurrency.10961.n7.nabble.com/8145539-coll-AbstractMap-keySet-and-values-should-not-be-volatile-tp13382p13403.html
Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
_______________________________________________
Concurrency-interest mailing list
<a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;Concurrency-interest@cs.oswego.edu&#39;)">Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


--
Sent from my phone

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

Re: 8145539: (coll) AbstractMap.keySet and .values should not be volatile

thurstonn
Yes, I understand the compiler transformation that could cause the problem, and that it's allowed by the JMM, but I find it hard to believe that there's an actual JIT out there in the wild that would actually do so.
The "normal", logical optimization would be to eliminate the redundant read, which actually "solves" the data race.

It's one thing for the compiler (or more likely the CPU) to reorder reads of *different memory locations*, but to reorder reads of *the same memory location*?  That seems far-fetched.

Anyway, I'll take a look at the link.


*I should note that the problem wouldn't have manifested itself in AbstractMap since #keyset and #values were originally declared volatile; I was asking about the general idiom

Vitaly Davidovich wrote
The problem is compilers can do weird things on the assumption of data race
free code.  If you haven't seen
https://software.intel.com/en-us/blogs/2013/01/06/benign-data-races-what-could-possibly-go-wrong,
I recommend reading it.  It's in the context of C/C++/Go but the general
point stands.

In this case, compiler can arrange a read of the field into a
register/stack slot - assume it reads null.  Later it re-tests the field
(memory), sees non null, but returns the register/stack slot value.  It's
weird, but legal.  Whether it happens I don't know, but you likely don't
want to find out :).

On Monday, April 25, 2016, thurstonn <[hidden email]> wrote:

> Just curious,
>
> has anyone actually observed a real JVM returning null in the original,
> racy
> code?
> I realize the JMM allows it, but I'd be surprised that a JVM would reorder
> reads of the *same* memory location
>
>
>
>
>
> --
> View this message in context:
> http://jsr166-concurrency.10961.n7.nabble.com/8145539-coll-AbstractMap-keySet-and-values-should-not-be-volatile-tp13382p13403.html
> Sent from the JSR166 Concurrency mailing list archive at Nabble.com.
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email] <javascript:;>
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>


--
Sent from my phone

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

Re: 8145539: (coll) AbstractMap.keySet and .values should not be volatile

Justin Sampson
In reply to this post by Vitaly Davidovich
Vitaly Davidovich wrote:

> The problem is compilers can do weird things on the assumption of
> data race free code. If you haven't seen
> https://software.intel.com/en-us/blogs/2013/01/06/benign-data-races-what-could-possibly-go-wrong
> I recommend reading it. It's in the context of C/C++/Go but the
> general point stands.

Interesting -- that article actually seems to describe cases of
thin-air reads due to the compiler reusing memory locations, which
is impossible in Java even for racy code, right?

Thanks,
Justin

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

Re: 8145539: (coll) AbstractMap.keySet and .values should not be volatile

Vitaly Davidovich
Yes, I believe JVMs are not allowed to introduce phantom reads or writes.  In other words, reading a plain field into a local (and only using the local) in java means it will not be re-read, whereas no such guarantee exists in C/C++.  Relatedly, that blog shows a case where gcc and clang read and write, back-to-back(!), a field to memory -- that is also not allowed in conforming JVMs, AFAIK.

On Tue, Apr 26, 2016 at 3:12 PM, Justin Sampson <[hidden email]> wrote:
Vitaly Davidovich wrote:

> The problem is compilers can do weird things on the assumption of
> data race free code. If you haven't seen
> https://software.intel.com/en-us/blogs/2013/01/06/benign-data-races-what-could-possibly-go-wrong
> I recommend reading it. It's in the context of C/C++/Go but the
> general point stands.

Interesting -- that article actually seems to describe cases of
thin-air reads due to the compiler reusing memory locations, which
is impossible in Java even for racy code, right?

Thanks,
Justin


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