request for advice: safepoints in the JSR 292 spec

[John Rose]

On Dec 13, 2010, at 12:19 AM, Rémi Forax wrote:
> On 12/12/2010 05:02 PM, Rich Hickey wrote:
>> Rémi's synchronized block only coordinates the activities of updaters. 
>> Other threads may, and in some cases may have to, see some of the 
>> setTarget results prior to the sync call, which could be a mess. The 
>> point of syncTargets is to make the setting and the visibility atomic, 
>> which synchronized cannot do.

Yes, syncTargets would be very powerful.  But it would also be hard to
require of all JVMs.  Speaking only for HotSpot, we don't do everything
with safepoints, because they are expensive.  We use racy updates
whenever we can get away with it.  The cost of a racy update is the
co-existence of two states, unpredictably visible to various threads.
I think that's a normal complexity cost for doing good language
implementations.

I think mapping a global atomic update to the JMM would require
more "magic edges" in the happens-before graph.  The proposal
I posted, while weaker, has a correspondingly simpler impact on
the JMM. This is another way of observing that JVMs are likely to
have an easier time of adding the proposed functionality.

So a globally atomic update is harder to implement and harder
to specify.  It is also overkill for a common use case, which is
delayed optimization of call sites.  See below...

> Rich,
> I don't think you can provide an optimized method handle when syncing but
> more probably a default generic method that will later installs a fast path.

Thanks, Remi, for explaining this.  I'm going to pile on here.

(I have one comment on your code; see below.)

I think of the pattern Remi sketches as a 2-phase commit.

Phase 0 and phase 2 are long-term phases.  Phase 1 is brief but not atomic.

Phase 0 is the reign of the old target T0, before any MCS.setTarget.

Phase 1 starts when metadata locks are grabbed.
Under the locks, MCS.setTarget installs a default generic method T1.
(This is analogous to the JVM trick of setting a call site to the "unlinked" state.)

T1 is not racy.  It is careful to grab a reader lock on metadata.
It is likely to install an optimized method T2, via a simple setTarget.
This may happen after an invocation count, or after user-level profiling.
(Therefore, it does not make sense to try to guess at T2 during phase 1.)

The MCS.sync operation is performed during phase 1, after all
relevant setTargets are done.  It has the effect of excluding threads
from observing target T0.  (I.e., it "flushes" T0 from the system.)

Phase 2 starts when metadata locks are released.  During phase 2,
individual threads eventually execute T1.  T1 lazily decides to install T2.
(Or several equivalent versions of T2.)

Threads which observe T1 (because of caching or inlining) will perform
sync actions which will force them to observe more recent call site targets.

During phase 0, T2 cannot be observed.  During phase2, T0 cannot be observed.
The intermediate target T1 can be observed during any phase.

Compare that with Rich's proposed atomic syncTargets operation,
which would exclude phase 1 and target T1, for better and worse.

Another way of comparing syncTargets with setTarget+sync is
simply to syncTargets excludes target T1 from phase 0, whereas
the weaker proposal does not exclude T1.

This weakness can also be described in terms of two reader
threads, a Fast Reader and a Slow Reader.  The Fast Reader
sees the result of the writer's setTarget of T1 in the same
nanosecond.  The Slow Reader sees only T0 until it is
forced to pick up T1 by the sync operation.

-- John

> So if the result of setTarget is visible before the sync call, it will 
> execute
> a default generic method which will also enter in a synchronized block.
> This will effectively coordinate things between readers and writers.
> 
> invariant broken (writer):
> synchronized(masterLock) {
>   // mutate meta data
>   // update all callsites
>   foreach(impacted callsites) {
>     callsite.setTarget(callsite.defaultGenericPath);
>   }
>   sync(impacted callsites);
> }
> 
> default generic method (reader):
> synchonized(masterLock) {
>   // check arguments
>   // use meta data to create a fast path
> }

(This next line should also be synchronized.  -- JRR)

> setTarget(guard + fastpath);
> 
> 
> This pattern intends to mimick the way the VM do lazy deoptimization
> i.e mark the callsite as deoptimized and later when the callsite is used
> re-create a fast path.