request for advice: safepoints in the JSR 292 spec

[John Rose]

Hi everyone.  On behalf of the JSR 292 EG, I'd like to ask for advice from language implementors on a deep point in our specification.

For many months, the JSR 292 EG has been thinking about safepoints as an informal paradigm for thread-safe invalidation of dynamic call sites.  Specifically, we need to define a mechanism to force a global update through a mutable call site, and we want a mechanism that is narrowly targeted.  The narrow targeting is especially important for those of us who write JITs for machines with unusual memory architectures.

Our current concrete challenge is to define an operation called MutableCallSite.sync which, when executed by a writer thread on a given mutable call site, forces all reader threads everywhere to discard previously cached reads from that call site.

How hard could that be?  Well, there's a thing called the Java Memory Model.  The JMM, which seems to require a long time to master, is here:

  http://www.cs.umd.edu/%7Epugh/java/memoryModel/

In order to express the desired mechanism in the terms of the JMM, I am proposing the device of a single-definition anonymous volatile variable, a sort of "nonce term".  This will be written by the sync operation and read by a future getTarget operation in each thread that touches the affected call site.  (The reason this whole thing is difficult is that the word "future" in the previous sentence cannot be easily defined in the JMM, which avoids total orders.)

My goal in this is to capture the essential points of the "safepoint trick", expressing them in the JMM.  The "safepoint trick" is too good to keep for the JVM internals; we want to share it with language implementors.  (I owe recent thanks to Rich Hickey for strongly urging this request on me at JavaOne.)

Here are the details.  Suppose a thread ("Writer thread #10") wants to publish its most recent version of a call site's target; it executes a sync operation on that call site.  The actions take by the JVM appear as if it created sync4242, a volatile variable that exists nowhere else in the execution, and wrote that variable.

The happens-before diagram looks like this (including the activities of a nearby reader thread):

Reader thread #56:

  R(t99 = mcs.target) -> (activity of t99 as a method handle)

Writer Thread #10:

  W(mcs.target = t100)* -> volatile W(sync4242 = garbage) -> volatile R(sync4242)*

Reader thread #56:

  R(t99 = mcs.target) -> (more activity of t99 as a method handle)

  volatile W(sync4242)* -> volatile R(ignore = sync4242) -> R(mcs.target)

Starred items appear as constraints in a thread's sequence of actions, but are not executed by that thread.

The essential idea is that the MSC.sync operation is converted into a synchronization event (W(sync4242)).  This event is global and totally ordered (per the JMM).  Any reader thread that wishes to participate in the global synchronization order will eventually have to witness this event, and therefore the updates made by the writer thread.  This will be true because the complete happens-before order is constrained by synchronization events.

(The write W(mcs.target = t100) is starred because it doesn't strictly have to happen in the writer thread.  It is enough that the writer thread could make a non-racy observation of t100, at the time it wishes to sync the call site containing t100.)

The structure above is designed to prevent reader threads (except perhaps those that run away into infinite loops and diverge) from clinging to stale target values.  Here's an example of what should be impossible:

Illegal reader thread #57:

  volatile W(sync4242)* -> (synchronization event  #5656) -> R(t99 = mcs.target)

Here, the reader thread executes something like a lock or volatile reference (#5656) and then expects to re-use the c ached value t99.  This should be impossible because the extra happens-before edges involving sync4242 imply this edge in the HB transitive closure:

  W(mcs.target = t100) -> ... -> R(t99 = mcs.target)

Assuming the writes of t99 and t100 are relatively ordered (not racy), this should be impossible, according to JMM 7.3 rule 5, labeled "happens-before consistency".  This rule states that W(r) -> r precludes visibility of an intervening write W(r: v = x1) -> W(v = x2) -> r: x1 = v.  Put backwards, if two writes precede a read in the happens-bofore order, and the two writes are mutually ordered, the second one wins.

Note that either or both of the method handles t99 or t100 can be inlined and optimized into native code.  Getting a reader thread to start using t100 may require recompilation of native code, and getting it to stop using t99 may require "deoptimization".  (By deoptimization I mean the usual thing, a clean non-backtracking abort out of optimized code into a new version of the code.)

Here's the draft language for MutableCallSite#sync:

  http://cr.openjdk.java.net/~jrose/pres/indy-javadoc-mlvm-1209/java/dyn/MutableCallSite.html

So the question of the day is:  Will this really work?  In order to work, the specification has to (a) make logical sense in the terms of the JMM, (b) be reasonably implementable by JVMs, and (c) be useful to programmers.  Indeed, that's a tall order, but I think the above language meets all three requirements.  The JSR 292 EG would deeply appreciate anyone pointing out flaws in this reasoning.

Best wishes,

-- John

P.S.  If this pattern works, we are likely to apply variations of in two other places in the 292 spec, ClassValue and Switcher.  See the draft javadoc for details.  Cliff Click has pointed out that a generalized optimization on volatile variables would have about the same effect.  Perhaps this is what JVMs will be doing routinely in five years, but the 292 API needs this pattern in only a few set places, and so the EG is content to roll it out in a limited way right now.

P.P.S. This is probably the biggest issue which is preventing us from finalizing JSR 292.  Please see the items marked "PROVISIONAL" in the draft javadoc if you are curious about what's left to clean up.  The bleeding edge draft of 292 is always at http://cr.openjdk.java.net/~jrose/pres/indy-javadoc-mlvm .