[9] RFR(S): 8005873: JRuby test_respond_to.rb asserts with: MT-unsafe modification of inline cache

[John Rose]

On May 15, 2014, at 2:04 AM, Vladimir Ivanov <vladimir.x.ivanov at oracle.com> wrote:

> Cache is written only once, so it has only 2 states (null and non-null value) during it's lifecycle.
> 
> The only stale value cachedLambdaForm() can see is null, but then the caller tries to initialize the cache and after acquiring the lock in setCachedLambdaForm() sees actual value.
> 
> So, the worst thing can happen if readers aren't synchronized is creation of unnecessary LF (which go dead right away) in rare cases.


Lazy evaluation is a pattern that we use (or try to use) in a lot of places.  It's important to understand it and get it right.

With JDK-8005873, the root cause is that lazy evaluation is producing multiple right answers, and an assert is throwing a panic.  The correct fix is to use a CAS or lock (or equivalent) to make sure that, even if several threads race to produce a right answer, only one right answer gets published and used.

I coded this completely free of locks, in 'setCachedLambdaForm', because I thought that multiple right answers would be harmless.  That's arguably still correct, but if it makes assertions fire, we should clean up the edge case, rather than detune the assert.

Uniquification can be done with a lock or a CAS.  CAS is preferable, but hard to code.  AtomicReferenceArray provides easy access to CAS, but you pay a cost for simple 'get', since that is volatile.  That's not desirable; in fact the @Stable property is more appropriate.  On balance I would prefer a simple lock, such as this:

+    synchronized
     public LambdaForm setCachedLambdaForm(int which, LambdaForm form) {
-        // Should we perform some sort of CAS, to avoid racy duplication?
+        // Simulate a CAS, to avoid racy duplication of results.
+        LambdaForm prev = lambdaForms[which];
+        if (prev != null)  return prev;
         return lambdaForms[which] = form;
     }
 
Once lazy results are guaranteed unique the rest of the algorithm is fine, I think.  See below.

— John

P.S.  More discussion of lazy evaluation and races, assuming published values are unique.

If the state variable behind a lazy evaluation is a pointer to safely-published data, then a racy read will pick up either the initial state (null) or the desired data.

A slow path for null detection needs to reliably pick up the true value of the variable, to avoid starvation and multiple initialization.  Doing the slow-path read and write inside of a lock satisfies the requirements of the JMM for correct race-free code.

Outside of the lock, it is important that anything observed by the racy read eventually lead to a correct answer, even if the racy read gives an out-of-date answer.

If the lock's critical section is trivial (no object construction or side effects) then a CAS is usually faster, but it is hard to code correctly.  The new JMM will fix this we hope and make it possible to perform safe and sane CAS operations.  Meanwhile, the atomic reference array would work, but it is (IMO) overly expensive since it performs

The bottom line is that we don't need any volatile references on the fast path.

One hazard is that the JMM does not guarantee safe publication in either of the following two cases:

Caveat #1. Data is accessed along a path that does not use a final field.
Caveat #2. Data is accessed along a path that has been modified since construction.

Caveat #1 is usually (by itself) not a problem, if the access path goes through an object with at least one final field.  (That's because existing implementations use a broad fence at the end of a constructor if an object contains any non-static finals.)  And the new JMM may further downgrade or remove Caveat #1.

Caveat #2 includes the case of a non-final field in a "mostly final" object.  The field LambdaForm.vmentry is such a field.  Any non-final fields accessed through a vmentry patched into a published LambdaForm are racy, unless some sort of fence has been issued before the vmentry object is patched into the lambda form.

Caveat #2 It also includes the case where the path goes through an array element which was changed since the root object was constructed.  This happens in various tabular structures where an array that starts out full of nulls ends up containing lazily evaluated entries.  The entries should each be safely published.

Caveat #2 does *not* apply to stable array substructures like LamdaForm.names, if (as is the case with 'names') the arrays are assigned before the enclosing object is fully constructed, and the array references themselves are final.