Offer stronger guarantees under the Java Memory Model for List & Vector (using releaseFence) #6425

retronym · 2018-03-14T03:14:56Z

Use memory barrier after mutating List and Vector internals. The barrier is
the same one that the JDK adds to the end of a constructor of a class with
final fields.

The general pattern is that we have a just-created "larval" object graph,
which undergoes some mutation (e.g. appending elements to the tail of the
list in the builder). We return that larval object to the caller of, say,
ListBuilder.build or List.map, and they could store it to a plain field
which would let another thread observe it. According the the JMM, the other
thread might not see all the mutations.

The release fence will prevent re-ordering of stores that preceed it
(the tail mutation, for example) it with stores that suceeed it (the
caller of build storing the resulting list to a field).

The runtime support is a bit complicated becausse we need to be cross
compatible with JDK 8 and 9+. We use method handle based reflection
to achieve this. This has zero runtime overhead in the manner used.

I'm putting this PR forward as WIP as part of the discussion in
scala/collection-strawman#50

Fixes scala/bug#7838

retronym · 2018-03-14T04:01:58Z

Even after this change, we still have a gaping hole in ::, as the private[scala] var tl is erased to a JVM public setter:

  public void tl_$eq(scala.collection.immutable.List<B>);

With this, List can be mutated maliciously after construction, even under the presence of a security manager that prevents reflective access, so any security sensitive code really needs to take defensive copies of incoming Lists before input validation and defensive copies of any internal lists before exposing them.

So the argument for a bona-fide immutable List is still very valid.

We might be able to use some tricks to make the variable properly private, and have :: expose a TailMutator to the selected classes that are allowed to access this. The JDK internals, pre-JPMS, uses a similar pattern to manage "friend" access to sensitive operations across packages.

My kingdom for larval object support in the VM. (See 41m https://www.youtube.com/watch?v=VPF8DLnDgE4)

NthPortal · 2018-03-15T01:19:43Z

Is it possible to reduce the visibility of tl to ~~[collection]~~ [immutable] at most, if not to [this]? Then, it could perhaps have its privacy protected by the JVM.

retronym · 2018-03-15T04:47:28Z

@NthPortal I gave that some thought, but there are a few problems that I see.

First, Scala's private[collection] erases to JVM public because of the way that Scala lets you access such a member from within collection.subpackage. So we'd need a way to make things really JVM package private. There's a ticket somewhere suggesting an annotation for that purpose. I guess the other way is to write a Java class with the field's and setter and have :: extend that, but that's a bit icky.

Second, we don't seal the scala.collection package, so it's possible for anyone to load an extra class in that package.

Pre-JDK9, the Java standard library had VM support to seal "java.**".

⚡ (cat /tmp/Access.java; java_use 1.8; javac -d /tmp/out /tmp/Access.java; java -cp /tmp/out java.lang.invoke.Access )
package java.lang.invoke;

public class Access {
    static void foo(LambdaForm l) {}
    public static void main(String[] args) {
        foo(null);
    }
}

Error: A JNI error has occurred, please check your installation and try again
Exception in thread "main" java.lang.SecurityException: Prohibited package name: java.lang.invoke
	at java.lang.ClassLoader.preDefineClass(ClassLoader.java:662)
	at java.lang.ClassLoader.defineClass(ClassLoader.java:761)
	at java.security.SecureClassLoader.defineClass(SecureClassLoader

User libraries can get a similar effect with Sealed packages in JARs. We haven't used that so far, no doubt there would be compatibility problems if and when we start doing this. I suppose we'll have to face up to those problems anyway, once we ship scala-library.jar as a JPMS module, as that new module system has outlawed split packages.

We need to develop a better threat model to find a path forward. Scala has to make a bunch of stuff JV M public, so maybe it isn't worth building a strong defense around :: when other avenues are open.

NthPortal · 2018-03-15T05:40:52Z

I think a fence is certainly a valuable start, regardless.

retronym · 2018-03-16T03:41:33Z

I've added a commit to show what I propose for scala/scala-dev#408 (conforming the the stricter bytecode verifier in classfile format 53)

adriaanm · 2018-04-30T13:47:34Z

I'm tentatively pushing this to M5.

retronym · 2018-05-04T04:55:08Z

I've published an updated instrumented.jar which should make partest --specialized happy again.

lrytz · 2018-05-28T12:20:39Z

Would be good to move this forward for M5. What needs to be done?

Testing (jcstress)?
Ask @viktorklang for review
Rebase, upload another new instrumented.jar

viktorklang · 2018-05-28T14:43:56Z

src/library/scala/collection/immutable/List.scala

@@ -477,6 +482,7 @@ sealed abstract class List[+A]
 @SerialVersionUID(4L)
 case class :: [+A](override val head: A, private[scala] var next: List[A @uncheckedVariance]) // sound because `next` is used only locally


Is this comment really true given the reachability of the var in the generated bytecode.

You're right, this doesn't state the assumption that people won't mutate this from Java with tl_$eq. But that's a general problem we have (e.g. trait vals are mutable from Java, too)

viktorklang · 2018-05-28T15:04:27Z

src/library/scala/collection/immutable/List.scala

@@ -148,6 +149,7 @@ sealed abstract class List[+A]
      t = nx
      rest = rest.tail
    }
+    ScalaRunTime.releaseFence()


For maintainability, I'd suggest each invocation of releaseFence needs a comment explaining what it intends to publish, so that others in the future can reason about it.

Something like "Publish assignments to List.{head,next}"?

Yes, exactly. So if someone is in here, they know what the current intent is. 👍

viktorklang · 2018-05-28T15:05:44Z

src/library/scala/collection/immutable/Vector.scala

@@ -218,6 +219,7 @@ final class Vector[+A] private[immutable] (private[collection] val startIndex: I
    s.dirty = dirty
    s.gotoPosWritable(focus, idx, focus ^ idx)  // if dirty commit changes; go to new pos and prepare for writing
    s.display0(idx & 31) = elem.asInstanceOf[AnyRef]
+    ScalaRunTime.releaseFence()


If any of these are removed or inappropriately moved, is there a corresponding bench which aims to stochastically prove that correct results are obtained?

Agreed, we should create a jcstress suite to test drive/defend each of these changes. I'll add that before we merge this unless someone else volunteers to help out.

@retronym Awesome, thanks Jason!

viktorklang · 2018-05-28T15:05:56Z

src/library/scala/runtime/VM.java

+import java.lang.invoke.MethodType;
+import java.lang.reflect.Field;
+
+public class VM {


sure thing.

Speaking of modifiers, I would have preferred to make this package private, and to have indirected call through ScalaRuntime.releaseFence. But we don't have a way to force VM inlining of ScalaRuntime.releaseFence, so I wanted to keep it inlinable by the Scala inliner.

@retronym Ok. Perhaps document it as an internal API?

Maybe it would be better, at least initially, to leave inlining of releaseFence up to the JDK (my kingdom for @ForceInline!), and make VM package protected.

viktorklang · 2018-05-28T15:07:26Z

src/library/scala/runtime/VM.java

+
+
+    static {
+        RELEASE_FENCE = mkHandle();


Is there a requirement as to what thread must invoke the initialization of this to ensure correct access to internals?

This code is protected by the static init lock on this class, so whichever thread gets here first can safely initialize. RELEASE_FENCE = ... will be safely published. Do you see this differently?

No, that part is fine. But since it will be initialized by the first calling thread, and that thread needs to have correct permissions for thisinitialization, does it make sense to try to "force" the initialization from a specific place which we know to be early?

"Permissions" as in a SecurityManager sense? I hadn't thought of that. Do you have a recommendation based on your Akka experience?

@retronym I don't have any "current" recommendations since I haven't been keeping up with how the module system will impact this situation. Perhaps worth asking on the concurrency-interest ML?

If we're running on 9, lookup.findStatic(Class.forName("java.lang.invoke.VarHandle"), "releaseFence", MethodType.methodType(Void.TYPE)); will work, so we don't need to worry about the module system preventing the fallback case from working.

I guess we could initialize VM from Predef, but which Thread is going to initialize Predef? If we do find a problem in the wild, the user will have a workaround of initializing this in their application entry point, and we can revisit.

retronym · 2018-05-29T05:25:41Z

I've taken a shot at writing a failing jcstress test, but so far failed to reproduce the issue.

My attempt is included here, you can try it with:

sbt dist/mkPack && (cd test/jcstress; java_use 10; sbt clean jcstress:run)

I've tried to create a test to show the issue with a ListLike class: https://github.com/retronym/scala/blob/5aa8c1420cbfe7f102f1cf541445511ce932dea8/test/jcstress/src/test/scala/scala/collection/immutable/ListLikeStressTest.scala

I'd expect that to fail occasionally when jcstress asks the JVM to reorders instructions (-XX:+UnlockDiagnosticVMOptions, -XX:+StressLCM, -XX:+StressGCM), sometimes we should see the assignment of this.list = list before the assignments of all of the internals of that list. But I can't get that to fail (and hence motivate the addition of the release fence)

/cc @ktoso

ktoso · 2018-05-29T05:41:46Z

test/instrumented/library/scala/runtime/ScalaRunTime.scala

+  /**
+    * Forwards to `VarHandle.releaseFence` or `sun.misc.Unsafe.storeFence` on JDK9+ or JDK8 respectively.
+    */
+  @inline def releaseFence(): Unit = VM.RELEASE_FENCE.invoke()


nice 👍 😍

Indeed! 👍

viktorklang · 2018-05-29T08:22:12Z

src/library/scala/collection/immutable/List.scala

@@ -470,6 +475,7 @@ sealed abstract class List[+A]

 case class :: [+A](override val head: A, private[scala] var next: List[A @uncheckedVariance]) // sound because `next` is used only locally


Is :: meant to be extendable?

It could be final. List is sealed, but that doesn't prevent non-Scala subclasses.

It doesn't prevent Scala subclasses either!

$ scala Welcome to Scala 2.13.0-M4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_40). Type in expressions for evaluation. Or try :help. scala> class Oops extends ::(5, Nil) defined class Oops

I still forget about that!

final all the things!

retronym · 2018-08-10T08:14:02Z

@lrytz @adriaanm I've split the trait setter to a separate PR. I'll do another pass to address @viktorklang's comments on Monday. I wasn't able to make jcstress demonstrate the bug, unfortunately.

SethTisue · 2018-08-10T15:18:46Z

@retronym maybe rebasing will restore Scabot to its senses

SethTisue · 2018-08-15T18:32:00Z

I took the liberty of rebasing and force-pushing

retronym · 2018-08-16T04:43:31Z

src/library/scala/collection/mutable/ListBuffer.scala

@@ -61,6 +62,7 @@ class ListBuffer[A]
  // Avoids copying where possible.
  override def toList: List[A] = {
    aliased = nonEmpty
+    ScalaRunTime.releaseFence()
    first


Echoing @adriaanm's comments from #7028 that belong over in this PR.

Why no fence for the other methods that mutate? I see they're private, but they are called from public methods, I assume?

My rationale is that this is the where the reference to the List is given out. Only after this point could client code share it with another thread. My assumption is that users are only using the ListBuilder itself on a single thread, and its only the resulting List that needs to be safely publishible.

I'm happy to add the fence after each mutation of tail, at least initially, to make things easier to reason about.

retronym · 2018-08-16T04:51:59Z

src/library/scala/collection/immutable/Vector.scala

@@ -219,6 +220,7 @@ final class Vector[+A] private[immutable] (private[collection] val startIndex: I
    s.dirty = dirty
    s.gotoPosWritable(focus, idx, focus ^ idx)  // if dirty commit changes; go to new pos and prepare for writing
    s.display0(idx & 31) = elem.asInstanceOf[AnyRef]
+    ScalaRunTime.releaseFence()


Echoing @adriaanm's comments from #7028 that belong over in this PR.

is this to publish the mutation of dirty?

Yes, that's the intent.

Should we also do this in the constructor?

Good catch, I hadn't considered that. I think we get away without one because it starts with the default value. I'll add a comment to that effect. Also happy to add the fence if that seems to subtle.

On second thoughts, I'll add the fence. We need the memory barrier to safely publish the assignments to the other val fields in Vector, and the presence of a single non-final field means the implicit fence at the end of the constructor is not guaranteed (although it is added in practice for classes with >= 1 final fields)

retronym · 2018-08-16T05:39:36Z

I added a commit that moves releaseFence to runtime.Statics. I'd like to start out by trying to rely on the JDK inliner to inline that method.

If we agree that this is the right approach, I'll need to update the other PR to target this new method.

lrytz · 2018-08-16T10:20:04Z

src/library/scala/runtime/Statics.java

+
+      private static Object findUnsafe(Class<?> unsafeClass) throws IllegalAccessException {
+          Object found = null;
+          for (Field field : unsafeClass.getDeclaredFields()) {


I don't have experience with Unsafe, so I googled a bit. https://dzone.com/articles/understanding-sunmiscunsafe suggest that you could create a new Unsafe instance instead of getting the singleton, as the latter doesn't work on Android. Not sure if that's still relevant.

Apart from that, the use of setAccessible(true) in List requires basically reflection to be allowed when running any Scala program. Was that the case before? Could security managers be configured in a fine-grained way to allow reflection only for this particular access?

Unless things changed without me noticing Android is not really Java8+ so Scala nowadays does not work on it in any case, so most likely this should not be a consideration here. Though one may want to check if I'm up to date about that.

Good point re: setAccessible. A similar issue was reported with our use of that in structural types: scala/bug#2318 (comment)

In that case, we catch the SecurityException and fall back to doing nothing.

We could do something similar here, I guess, but it would be good to alert the user somehow that the memory barriers aren't supported in that configuration. For instance, we could throw an exception that says "restart with -Dscala.barrier.noop=true to accept this limitation". Not nice :(

This would only affect users on Java 8, of course. On 9+ we just use the public VarHandle API.

Not very nice, but I think that's our only option. Silently skipping the fence is certainly not a good idea.

Looks like the proposal discussed here wasn't implemented in this PR. Should a ticket on http://github.com/scala/scala-dev/ be created to track this?

SethTisue · 2018-08-18T02:26:32Z

@retronym can I go and ahead merge this? it looks like there isn't anything here that we can't tweak further before RC1?

retronym · 2018-08-18T04:11:11Z

@SethTisue The last commit introduces a semantic merge conflict with #7028. I'll drop it from the PR and resubmit it separately along with some better error handling for platforms where setAccessible and/or Unsafe aren't available. That followup could come after M5 IMO.

retronym · 2018-08-18T04:14:29Z

Hmmm, on second thought I think its better to fix the semantic merge conflict right away, rather than risk bootstrapping issues with modules or the by letting the sands of scala.runtime._ shift needlessly.

Fixed by scala#6425

scala-jenkins added this to the 2.13.0-M4 milestone Mar 14, 2018

retronym mentioned this pull request Mar 14, 2018

Make List.tail a final (val) scala/collection-strawman#50

Closed

retronym added the WIP label Mar 14, 2018

retronym force-pushed the topic/unsafe-undead branch from a2682a4 to e0f4254 Compare March 16, 2018 03:38

retronym mentioned this pull request Mar 16, 2018

Trait encoding vs the persnickety JVM 9 verifier: final fields only updatable from within <init> scala/scala-dev#408

Closed

lrytz mentioned this pull request Apr 23, 2018

Offer stronger guarantees under the Java Memory model for List, Vector scala/bug#7838

Closed

adriaanm modified the milestones: 2.13.0-M4, 2.13.0-M5 Apr 30, 2018

retronym force-pushed the topic/unsafe-undead branch 4 times, most recently from 956121d to a24d33a Compare May 4, 2018 04:54

retronym force-pushed the topic/unsafe-undead branch from a24d33a to 7ea53e7 Compare May 4, 2018 06:01

viktorklang reviewed May 28, 2018

View reviewed changes

retronym mentioned this pull request May 29, 2018

java.lang.IllegalStateException during execution sbt/sbt-jcstress#12

Open

retronym force-pushed the topic/unsafe-undead branch 3 times, most recently from b395c5c to 5aa8c14 Compare May 29, 2018 05:24

ktoso reviewed May 29, 2018

View reviewed changes

viktorklang reviewed May 29, 2018

View reviewed changes

retronym mentioned this pull request Aug 9, 2018

Mixin fields with trait setters shouldn't be JVM final #7028

Merged

retronym added 2 commits August 15, 2018 11:30

Make Vector safe to share across threads without synchronization

51d6e60

Make List safe to share across threads without synchronization

6541df7

SethTisue force-pushed the topic/unsafe-undead branch from c40c26b to 6541df7 Compare August 15, 2018 18:31

SethTisue self-assigned this Aug 15, 2018

retronym commented Aug 16, 2018

View reviewed changes

retronym added 2 commits August 16, 2018 15:11

More fences and commentary

b6d74ff

Combine VM with Statics, and rely on JIT inlining of releaseFence

2c6d90c

retronym closed this Aug 16, 2018

retronym reopened this Aug 16, 2018

lrytz reviewed Aug 16, 2018

View reviewed changes

Merge remote-tracking branch 'origin/2.13.x' into topic/unsafe-undead

054a9ac

SethTisue merged commit caeddb7 into scala:2.13.x Aug 18, 2018

SethTisue changed the title ~~Use a releaseFence after mutation of List, Vector~~ Use releaseFence to offer stronger guarantees under the Java Memory model for List & Vector Aug 22, 2018

SethTisue changed the title ~~Use releaseFence to offer stronger guarantees under the Java Memory model for List & Vector~~ Offer stronger guarantees under the Java Memory model for List & Vector (using releaseFence) Aug 22, 2018

SethTisue changed the title ~~Offer stronger guarantees under the Java Memory model for List & Vector (using releaseFence)~~ Offer stronger guarantees under the Java Memory Model for List & Vector (using releaseFence) Aug 22, 2018

jackkoenig added a commit to jackkoenig/scala that referenced this pull request Feb 27, 2019

Remove usesMutableState from ScalaDocs

1fd2b59

Fixed by scala#6425

jackkoenig mentioned this pull request Feb 27, 2019

Remove usesMutableState from ScalaDocs #7802

Merged

lrytz mentioned this pull request Nov 28, 2019

With -release 8 in JDK 11 some classes are not found scala/bug#11814

Closed

SethTisue mentioned this pull request Apr 9, 2020

Uncertain Cause of IllegalArgumentException NetLogo/NetLogo#1830

Closed

This was referenced Apr 20, 2023

Race condition may cause newly-created List to mutate. scala/bug#9462

Closed

Do not mutate List in Types.scala scala/bug#8061

Closed

		@@ -477,6 +482,7 @@ sealed abstract class List[+A]
		@SerialVersionUID(4L)
		case class :: [+A](override val head: A, private[scala] var next: List[A @uncheckedVariance]) // sound because `next` is used only locally

		@@ -470,6 +475,7 @@ sealed abstract class List[+A]

		case class :: [+A](override val head: A, private[scala] var next: List[A @uncheckedVariance]) // sound because `next` is used only locally

Offer stronger guarantees under the Java Memory Model for List & Vector (using releaseFence) #6425

Offer stronger guarantees under the Java Memory Model for List & Vector (using releaseFence) #6425

Uh oh!

Conversation

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment