Summary

ClassValue::remove currently either cannot prevent installation of a stale value (before JDK-8351045) or stalls in an infinite loop if it is called from computeValue (after JDK-8351045); update it so that for a given argument clazz, a call to remove(clazz):

1. Happens-before any subsequent computeValue(clazz) to prevent stale values;
2. The old behavior where computeValue(clazz)'s remove(clazz) calls are no-op is retained only for same-thread invocations.

Problem

The ClassValue::remove API removes a preexisting association identified by the given ClassValue, Class pair. Naturally, it is useful to force a recomputation if an input to the computation of an associated value has updated. Yet, as described in the removed specification below, the remove operation allows a stale value to be installed.

A fix JDK-8351045 attempted to prevent stale values. However, it ignored the historical requirement that a call to remove from computeValue should return no-op (JDK-7153157).

Solution

For a call to remove from computeValue, it is now no-op only if the remove is called from a thread that is calling computeValue.

This allowance of reentrancy comes from the fact that there can sometimes be limited reentrancy that executes successfully on a single thread - for example, a ClassValue.get call may initialize a class, whose class initializer re-enters ClassValue.get; the class initializer will finish the call successfully instead of stalling or entering an infinite loop.

Given such random reentrancy from side effects such as class initialization, blocking remove from computeValue or any of its nested calls seem unrealistic and too risky.

Specification

New specification for remove:

For a particular association, a {@code remove} call happens-before (JLS
{@jls 17.4.5}) any subsequent {@code get}, including any contingent {@code
computeValue} invocation that computed the associated value.  Naturally,
any {@code computeValue} that began before the {@code remove} call must
have its result discarded, because the removal must happen-before the
computation of the associated value.  The {@code get} call that invoked
the stale {@code computeValue} may retry to re-establish this
happens-before relationship.
<p>
If this is invoked through {@code computeValue}, which can happen due to
side effects like class initialization, this will be no-op to the caller
thread.

Removed specification:

In order to explain the interaction between {@code get} and {@code remove} calls,
we must model the state transitions of a class value to take into account
the alternation between uninitialized and initialized states.
To do this, number these states sequentially from zero, and note that
uninitialized (or removed) states are numbered with even numbers,
while initialized (or re-initialized) states have odd numbers.
<p>
When a thread {@code T} removes a class value in state {@code 2N},
nothing happens, since the class value is already uninitialized.
Otherwise, the state is advanced atomically to {@code 2N+1}.
<p>
When a thread {@code T} queries a class value in state {@code 2N},
the thread first attempts to initialize the class value to state {@code 2N+1}
by invoking {@code computeValue} and installing the resulting value.
<p>
When {@code T} attempts to install the newly computed value,
if the state is still at {@code 2N}, the class value will be initialized
with the computed value, advancing it to state {@code 2N+1}.
<p>
Otherwise, whether the new state is even or odd,
{@code T} will discard the newly computed value
and retry the {@code get} operation.
<p>
Discarding and retrying is an important proviso,
since otherwise {@code T} could potentially install
a disastrously stale value.  For example:



{@code T} calls {@code CV.get(C)} and sees state {@code 2N}
{@code T} quickly computes a time-dependent value {@code V0} and gets ready to install it
{@code T} is hit by an unlucky paging or scheduling event, and goes to sleep for a long time
...meanwhile, {@code T2} also calls {@code CV.get(C)} and sees state {@code 2N}
{@code T2} quickly computes a similar time-dependent value {@code V1} and installs it on {@code CV.get(C)}
{@code T2} (or a third thread) then calls {@code CV.remove(C)}, undoing {@code T2}'s work
 the previous actions of {@code T2} are repeated several times
 also, the relevant computed values change over time: {@code V1}, {@code V2}, ...
...meanwhile, {@code T} wakes up and attempts to install {@code V0}; this must fail



We can assume in the above scenario that {@code CV.computeValue} uses locks to properly
observe the time-dependent states as it computes {@code V1}, etc.
This does not remove the threat of a stale value, since there is a window of time
between the return of {@code computeValue} in {@code T} and the installation
of the new value.  No user synchronization is possible during this time.