< prev index next >
src/java.base/share/classes/java/lang/ClassValue.java
Print this page
*** 1,7 ****
/*
! * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
--- 1,7 ----
/*
! * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
*** 23,38 ****
* questions.
*/
package java.lang;
! import java.util.WeakHashMap;
import java.lang.ref.WeakReference;
import java.util.concurrent.atomic.AtomicInteger;
!
! import static java.lang.ClassValue.ClassValueMap.probeHomeLocation;
! import static java.lang.ClassValue.ClassValueMap.probeBackupLocations;
/**
* Lazily associate a computed value with (potentially) every type.
* For example, if a dynamic language needs to construct a message dispatch
* table for each class encountered at a message send call site,
--- 23,43 ----
* questions.
*/
package java.lang;
! import jdk.internal.misc.Unsafe;
! import jdk.internal.vm.annotation.ForceInline;
! import jdk.internal.vm.annotation.Stable;
!
! import java.lang.ref.PhantomReference;
! import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
+ import java.util.concurrent.ConcurrentHashMap;
+ import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;
! import java.util.concurrent.atomic.AtomicReference;
/**
* Lazily associate a computed value with (potentially) every type.
* For example, if a dynamic language needs to construct a message dispatch
* table for each class encountered at a message send call site,
*** 93,119 ****
* @return the current value associated with this {@code ClassValue}, for the given class or interface
* @throws NullPointerException if the argument is null
* @see #remove
* @see #computeValue
*/
public T get(Class<?> type) {
! // non-racing this.hashCodeForCache : final int
! Entry<?>[] cache;
! Entry<T> e = probeHomeLocation(cache = getCacheCarefully(type), this);
! // racing e : current value <=> stale value from current cache or from stale cache
! // invariant: e is null or an Entry with readable Entry.version and Entry.value
! if (match(e))
! // invariant: No false positive matches. False negatives are OK if rare.
! // The key fact that makes this work: if this.version == e.version,
! // then this thread has a right to observe (final) e.value.
! return e.value();
! // The fast path can fail for any of these reasons:
! // 1. no entry has been computed yet
! // 2. hash code collision (before or after reduction mod cache.length)
! // 3. an entry has been removed (either on this type or another)
! // 4. the GC has somehow managed to delete e.version and clear the reference
! return getFromBackup(cache, type);
}
/**
* Removes the associated value for the given class.
* If this value is subsequently {@linkplain #get read} for the same class,
--- 98,159 ----
* @return the current value associated with this {@code ClassValue}, for the given class or interface
* @throws NullPointerException if the argument is null
* @see #remove
* @see #computeValue
*/
+ @SuppressWarnings("unchecked")
+ @ForceInline
public T get(Class<?> type) {
! ClassValueMap map = type.classValueMap;
! Object value;
! if (map != null) {
! value = map.get(key);
! if (value != null && !(value instanceof Removed)) {
! return (value == NULL_MASK) ? null : (T) value;
! }
! } else {
! value = null;
! }
! return getSlow(type, value);
! }
! // ...the rest in separate method
! @SuppressWarnings("unchecked")
! private T getSlow(Class<?> type, Object oldValue) {
! ClassValueMap.expungeStaleEntries();
! ClassValueMap map = getMap(type);
! while (true) {
! // assert oldValue == null || oldValue instanceof Removed;
! T newValue = computeValue(type);
! if (oldValue == null) {
! oldValue = map.putIfAbsent(key, (newValue == null) ? NULL_MASK : newValue);
! if (oldValue == null) {
! return newValue;
! } else {
! // another thread has beaten us
! if (!(oldValue instanceof Removed)) {
! return (oldValue == NULL_MASK) ? null : (T) oldValue;
! }
! }
! } else {
! // assert oldValue instanceof Removed;
! if (map.replace(key, oldValue, (newValue == null) ? NULL_MASK : newValue)) {
! // this only succeeds if oldValue is still the same instance of
! // Removed as observed before computeValue invocation
! return newValue;
! } else {
! // another thread has beaten us
! oldValue = map.get(key);
! if (oldValue != null && !(oldValue instanceof Removed)) {
! return (oldValue == NULL_MASK) ? null : (T) oldValue;
! }
! }
! }
! // retry compute since we observed another version of Removed
! // as was current before compute which means that there was
! // at least one value present in between time which means
! // that the result of our compute is stale.
! }
}
/**
* Removes the associated value for the given class.
* If this value is subsequently {@linkplain #get read} for the same class,
*** 166,757 ****
*
* @param type the type whose class value must be removed
* @throws NullPointerException if the argument is null
*/
public void remove(Class<?> type) {
! ClassValueMap map = getMap(type);
! map.removeEntry(this);
}
// Possible functionality for JSR 292 MR 1
/*public*/ void put(Class<?> type, T value) {
ClassValueMap map = getMap(type);
! map.changeEntry(this, value);
}
/// --------
/// Implementation...
/// --------
- /** Return the cache, if it exists, else a dummy empty cache. */
- private static Entry<?>[] getCacheCarefully(Class<?> type) {
- // racing type.classValueMap{.cacheArray} : null => new Entry[X] <=> new Entry[Y]
- ClassValueMap map = type.classValueMap;
- if (map == null) return EMPTY_CACHE;
- Entry<?>[] cache = map.getCache();
- return cache;
- // invariant: returned value is safe to dereference and check for an Entry
- }
-
- /** Initial, one-element, empty cache used by all Class instances. Must never be filled. */
- private static final Entry<?>[] EMPTY_CACHE = { null };
-
/**
! * Slow tail of ClassValue.get to retry at nearby locations in the cache,
! * or take a slow lock and check the hash table.
! * Called only if the first probe was empty or a collision.
! * This is a separate method, so compilers can process it independently.
*/
! private T getFromBackup(Entry<?>[] cache, Class<?> type) {
! Entry<T> e = probeBackupLocations(cache, this);
! if (e != null)
! return e.value();
! return getFromHashMap(type);
! }
! // Hack to suppress warnings on the (T) cast, which is a no-op.
! @SuppressWarnings("unchecked")
! Entry<T> castEntry(Entry<?> e) { return (Entry<T>) e; }
!
! /** Called when the fast path of get fails, and cache reprobe also fails.
*/
! private T getFromHashMap(Class<?> type) {
! // The fail-safe recovery is to fall back to the underlying classValueMap.
! ClassValueMap map = getMap(type);
! for (;;) {
! Entry<T> e = map.startEntry(this);
! if (!e.isPromise())
! return e.value();
! try {
! // Try to make a real entry for the promised version.
! e = makeEntry(e.version(), computeValue(type));
! } finally {
! // Whether computeValue throws or returns normally,
! // be sure to remove the empty entry.
! e = map.finishEntry(this, e);
! }
! if (e != null)
! return e.value();
! // else try again, in case a racing thread called remove (so e == null)
! }
! }
!
! /** Check that e is non-null, matches this ClassValue, and is live. */
! boolean match(Entry<?> e) {
! // racing e.version : null (blank) => unique Version token => null (GC-ed version)
! // non-racing this.version : v1 => v2 => ... (updates are read faithfully from volatile)
! return (e != null && e.get() == this.version);
! // invariant: No false positives on version match. Null is OK for false negative.
! // invariant: If version matches, then e.value is readable (final set in Entry.<init>)
! }
!
! /** Internal hash code for accessing Class.classValueMap.cacheArray. */
! final int hashCodeForCache = nextHashCode.getAndAdd(HASH_INCREMENT) & HASH_MASK;
! /** Value stream for hashCodeForCache. See similar structure in ThreadLocal. */
! private static final AtomicInteger nextHashCode = new AtomicInteger();
/** Good for power-of-two tables. See similar structure in ThreadLocal. */
private static final int HASH_INCREMENT = 0x61c88647;
! /** Mask a hash code to be positive but not too large, to prevent wraparound. */
! static final int HASH_MASK = (-1 >>> 2);
! /**
! * Private key for retrieval of this object from ClassValueMap.
! */
! static class Identity {
! }
! /**
! * This ClassValue's identity, expressed as an opaque object.
! * The main object {@code ClassValue.this} is incorrect since
! * subclasses may override {@code ClassValue.equals}, which
! * could confuse keys in the ClassValueMap.
! */
! final Identity identity = new Identity();
! /**
! * Current version for retrieving this class value from the cache.
! * Any number of computeValue calls can be cached in association with one version.
! * But the version changes when a remove (on any type) is executed.
! * A version change invalidates all cache entries for the affected ClassValue,
! * by marking them as stale. Stale cache entries do not force another call
! * to computeValue, but they do require a synchronized visit to a backing map.
! * <p>
! * All user-visible state changes on the ClassValue take place under
! * a lock inside the synchronized methods of ClassValueMap.
! * Readers (of ClassValue.get) are notified of such state changes
! * when this.version is bumped to a new token.
! * This variable must be volatile so that an unsynchronized reader
! * will receive the notification without delay.
! * <p>
! * If version were not volatile, one thread T1 could persistently hold onto
! * a stale value this.value == V1, while another thread T2 advances
! * (under a lock) to this.value == V2. This will typically be harmless,
! * but if T1 and T2 interact causally via some other channel, such that
! * T1's further actions are constrained (in the JMM) to happen after
! * the V2 event, then T1's observation of V1 will be an error.
! * <p>
! * The practical effect of making this.version be volatile is that it cannot
! * be hoisted out of a loop (by an optimizing JIT) or otherwise cached.
! * Some machines may also require a barrier instruction to execute
! * before this.version.
! */
! private volatile Version<T> version = new Version<>(this);
! Version<T> version() { return version; }
! void bumpVersion() { version = new Version<>(this); }
! static class Version<T> {
! private final ClassValue<T> classValue;
! private final Entry<T> promise = new Entry<>(this);
! Version(ClassValue<T> classValue) { this.classValue = classValue; }
! ClassValue<T> classValue() { return classValue; }
! Entry<T> promise() { return promise; }
! boolean isLive() { return classValue.version() == this; }
! }
!
! /** One binding of a value to a class via a ClassValue.
! * States are:<ul>
! * <li> promise if value == Entry.this
! * <li> else dead if version == null
! * <li> else stale if version != classValue.version
! * <li> else live </ul>
! * Promises are never put into the cache; they only live in the
! * backing map while a computeValue call is in flight.
! * Once an entry goes stale, it can be reset at any time
! * into the dead state.
! */
! static class Entry<T> extends WeakReference<Version<T>> {
! final Object value; // usually of type T, but sometimes (Entry)this
! Entry(Version<T> version, T value) {
! super(version);
! this.value = value; // for a regular entry, value is of type T
! }
! private void assertNotPromise() { assert(!isPromise()); }
! /** For creating a promise. */
! Entry(Version<T> version) {
! super(version);
! this.value = this; // for a promise, value is not of type T, but Entry!
! }
! /** Fetch the value. This entry must not be a promise. */
! @SuppressWarnings("unchecked") // if !isPromise, type is T
! T value() { assertNotPromise(); return (T) value; }
! boolean isPromise() { return value == this; }
! Version<T> version() { return get(); }
! ClassValue<T> classValueOrNull() {
! Version<T> v = version();
! return (v == null) ? null : v.classValue();
! }
! boolean isLive() {
! Version<T> v = version();
! if (v == null) return false;
! if (v.isLive()) return true;
! clear();
! return false;
! }
! Entry<T> refreshVersion(Version<T> v2) {
! assertNotPromise();
! @SuppressWarnings("unchecked") // if !isPromise, type is T
! Entry<T> e2 = new Entry<>(v2, (T) value);
! clear();
! // value = null -- caller must drop
! return e2;
! }
! static final Entry<?> DEAD_ENTRY = new Entry<>(null, null);
}
! /** Return the backing map associated with this type. */
! private static ClassValueMap getMap(Class<?> type) {
! // racing type.classValueMap : null (blank) => unique ClassValueMap
! // if a null is observed, a map is created (lazily, synchronously, uniquely)
! // all further access to that map is synchronized
! ClassValueMap map = type.classValueMap;
! if (map != null) return map;
! return initializeMap(type);
}
! private static final Object CRITICAL_SECTION = new Object();
! private static ClassValueMap initializeMap(Class<?> type) {
! ClassValueMap map;
! synchronized (CRITICAL_SECTION) { // private object to avoid deadlocks
! // happens about once per type
! if ((map = type.classValueMap) == null)
! type.classValueMap = map = new ClassValueMap();
! }
! return map;
}
! static <T> Entry<T> makeEntry(Version<T> explicitVersion, T value) {
! // Note that explicitVersion might be different from this.version.
! return new Entry<>(explicitVersion, value);
!
! // As soon as the Entry is put into the cache, the value will be
! // reachable via a data race (as defined by the Java Memory Model).
! // This race is benign, assuming the value object itself can be
! // read safely by multiple threads. This is up to the user.
! //
! // The entry and version fields themselves can be safely read via
! // a race because they are either final or have controlled states.
! // If the pointer from the entry to the version is still null,
! // or if the version goes immediately dead and is nulled out,
! // the reader will take the slow path and retry under a lock.
! }
!
! // The following class could also be top level and non-public:
!
! /** A backing map for all ClassValues.
! * Gives a fully serialized "true state" for each pair (ClassValue cv, Class type).
! * Also manages an unserialized fast-path cache.
! */
! static class ClassValueMap extends WeakHashMap<ClassValue.Identity, Entry<?>> {
! private Entry<?>[] cacheArray;
! private int cacheLoad, cacheLoadLimit;
!
! /** Number of entries initially allocated to each type when first used with any ClassValue.
! * It would be pointless to make this much smaller than the Class and ClassValueMap objects themselves.
! * Must be a power of 2.
! */
! private static final int INITIAL_ENTRIES = 32;
! /** Build a backing map for ClassValues.
! * Also, create an empty cache array and install it on the class.
! */
! ClassValueMap() {
! sizeCache(INITIAL_ENTRIES);
! }
! Entry<?>[] getCache() { return cacheArray; }
!
! /** Initiate a query. Store a promise (placeholder) if there is no value yet. */
! synchronized
! <T> Entry<T> startEntry(ClassValue<T> classValue) {
! @SuppressWarnings("unchecked") // one map has entries for all value types <T>
! Entry<T> e = (Entry<T>) get(classValue.identity);
! Version<T> v = classValue.version();
! if (e == null) {
! e = v.promise();
! // The presence of a promise means that a value is pending for v.
! // Eventually, finishEntry will overwrite the promise.
! put(classValue.identity, e);
! // Note that the promise is never entered into the cache!
! return e;
! } else if (e.isPromise()) {
! // Somebody else has asked the same question.
! // Let the races begin!
! if (e.version() != v) {
! e = v.promise();
! put(classValue.identity, e);
! }
! return e;
! } else {
! // there is already a completed entry here; report it
! if (e.version() != v) {
! // There is a stale but valid entry here; make it fresh again.
! // Once an entry is in the hash table, we don't care what its version is.
! e = e.refreshVersion(v);
! put(classValue.identity, e);
! }
! // Add to the cache, to enable the fast path, next time.
! checkCacheLoad();
! addToCache(classValue, e);
! return e;
! }
}
! /** Finish a query. Overwrite a matching placeholder. Drop stale incoming values. */
! synchronized
! <T> Entry<T> finishEntry(ClassValue<T> classValue, Entry<T> e) {
! @SuppressWarnings("unchecked") // one map has entries for all value types <T>
! Entry<T> e0 = (Entry<T>) get(classValue.identity);
! if (e == e0) {
! // We can get here during exception processing, unwinding from computeValue.
! assert(e.isPromise());
! remove(classValue.identity);
! return null;
! } else if (e0 != null && e0.isPromise() && e0.version() == e.version()) {
! // If e0 matches the intended entry, there has not been a remove call
! // between the previous startEntry and now. So now overwrite e0.
! Version<T> v = classValue.version();
! if (e.version() != v)
! e = e.refreshVersion(v);
! put(classValue.identity, e);
! // Add to the cache, to enable the fast path, next time.
! checkCacheLoad();
! addToCache(classValue, e);
! return e;
! } else {
! // Some sort of mismatch; caller must try again.
! return null;
! }
}
! /** Remove an entry. */
! synchronized
! void removeEntry(ClassValue<?> classValue) {
! Entry<?> e = remove(classValue.identity);
! if (e == null) {
! // Uninitialized, and no pending calls to computeValue. No change.
! } else if (e.isPromise()) {
! // State is uninitialized, with a pending call to finishEntry.
! // Since remove is a no-op in such a state, keep the promise
! // by putting it back into the map.
! put(classValue.identity, e);
! } else {
! // In an initialized state. Bump forward, and de-initialize.
! classValue.bumpVersion();
! // Make all cache elements for this guy go stale.
! removeStaleEntries(classValue);
! }
! }
! /** Change the value for an entry. */
! synchronized
! <T> void changeEntry(ClassValue<T> classValue, T value) {
! @SuppressWarnings("unchecked") // one map has entries for all value types <T>
! Entry<T> e0 = (Entry<T>) get(classValue.identity);
! Version<T> version = classValue.version();
! if (e0 != null) {
! if (e0.version() == version && e0.value() == value)
! // no value change => no version change needed
! return;
! classValue.bumpVersion();
! removeStaleEntries(classValue);
! }
! Entry<T> e = makeEntry(version, value);
! put(classValue.identity, e);
! // Add to the cache, to enable the fast path, next time.
! checkCacheLoad();
! addToCache(classValue, e);
}
! /// --------
! /// Cache management.
! /// --------
!
! // Statics do not need synchronization.
! /** Load the cache entry at the given (hashed) location. */
! static Entry<?> loadFromCache(Entry<?>[] cache, int i) {
! // non-racing cache.length : constant
! // racing cache[i & (mask)] : null <=> Entry
! return cache[i & (cache.length-1)];
! // invariant: returned value is null or well-constructed (ready to match)
! }
!
! /** Look in the cache, at the home location for the given ClassValue. */
! static <T> Entry<T> probeHomeLocation(Entry<?>[] cache, ClassValue<T> classValue) {
! return classValue.castEntry(loadFromCache(cache, classValue.hashCodeForCache));
! }
!
! /** Given that first probe was a collision, retry at nearby locations. */
! static <T> Entry<T> probeBackupLocations(Entry<?>[] cache, ClassValue<T> classValue) {
! if (PROBE_LIMIT <= 0) return null;
! // Probe the cache carefully, in a range of slots.
! int mask = (cache.length-1);
! int home = (classValue.hashCodeForCache & mask);
! Entry<?> e2 = cache[home]; // victim, if we find the real guy
! if (e2 == null) {
! return null; // if nobody is at home, no need to search nearby
! }
! // assume !classValue.match(e2), but do not assert, because of races
! int pos2 = -1;
! for (int i = home + 1; i < home + PROBE_LIMIT; i++) {
! Entry<?> e = cache[i & mask];
! if (e == null) {
! break; // only search within non-null runs
! }
! if (classValue.match(e)) {
! // relocate colliding entry e2 (from cache[home]) to first empty slot
! cache[home] = e;
! if (pos2 >= 0) {
! cache[i & mask] = Entry.DEAD_ENTRY;
! } else {
! pos2 = i;
! }
! cache[pos2 & mask] = ((entryDislocation(cache, pos2, e2) < PROBE_LIMIT)
! ? e2 // put e2 here if it fits
! : Entry.DEAD_ENTRY);
! return classValue.castEntry(e);
! }
! // Remember first empty slot, if any:
! if (!e.isLive() && pos2 < 0) pos2 = i;
! }
! return null;
! }
! /** How far out of place is e? */
! private static int entryDislocation(Entry<?>[] cache, int pos, Entry<?> e) {
! ClassValue<?> cv = e.classValueOrNull();
! if (cv == null) return 0; // entry is not live!
! int mask = (cache.length-1);
! return (pos - cv.hashCodeForCache) & mask;
}
! /// --------
! /// Below this line all functions are private, and assume synchronized access.
! /// --------
!
! private void sizeCache(int length) {
! assert((length & (length-1)) == 0); // must be power of 2
! cacheLoad = 0;
! cacheLoadLimit = (int) ((double) length * CACHE_LOAD_LIMIT / 100);
! cacheArray = new Entry<?>[length];
}
! /** Make sure the cache load stays below its limit, if possible. */
! private void checkCacheLoad() {
! if (cacheLoad >= cacheLoadLimit) {
! reduceCacheLoad();
! }
! }
! private void reduceCacheLoad() {
! removeStaleEntries();
! if (cacheLoad < cacheLoadLimit)
! return; // win
! Entry<?>[] oldCache = getCache();
! if (oldCache.length > HASH_MASK)
! return; // lose
! sizeCache(oldCache.length * 2);
! for (Entry<?> e : oldCache) {
! if (e != null && e.isLive()) {
! addToCache(e);
! }
}
}
! /** Remove stale entries in the given range.
! * Should be executed under a Map lock.
! */
! private void removeStaleEntries(Entry<?>[] cache, int begin, int count) {
! if (PROBE_LIMIT <= 0) return;
! int mask = (cache.length-1);
! int removed = 0;
! for (int i = begin; i < begin + count; i++) {
! Entry<?> e = cache[i & mask];
! if (e == null || e.isLive())
! continue; // skip null and live entries
! Entry<?> replacement = null;
! if (PROBE_LIMIT > 1) {
! // avoid breaking up a non-null run
! replacement = findReplacement(cache, i);
! }
! cache[i & mask] = replacement;
! if (replacement == null) removed += 1;
! }
! cacheLoad = Math.max(0, cacheLoad - removed);
! }
!
! /** Clearing a cache slot risks disconnecting following entries
! * from the head of a non-null run, which would allow them
! * to be found via reprobes. Find an entry after cache[begin]
! * to plug into the hole, or return null if none is needed.
! */
! private Entry<?> findReplacement(Entry<?>[] cache, int home1) {
! Entry<?> replacement = null;
! int haveReplacement = -1, replacementPos = 0;
! int mask = (cache.length-1);
! for (int i2 = home1 + 1; i2 < home1 + PROBE_LIMIT; i2++) {
! Entry<?> e2 = cache[i2 & mask];
! if (e2 == null) break; // End of non-null run.
! if (!e2.isLive()) continue; // Doomed anyway.
! int dis2 = entryDislocation(cache, i2, e2);
! if (dis2 == 0) continue; // e2 already optimally placed
! int home2 = i2 - dis2;
! if (home2 <= home1) {
! // e2 can replace entry at cache[home1]
! if (home2 == home1) {
! // Put e2 exactly where he belongs.
! haveReplacement = 1;
! replacementPos = i2;
! replacement = e2;
! } else if (haveReplacement <= 0) {
! haveReplacement = 0;
! replacementPos = i2;
! replacement = e2;
! }
! // And keep going, so we can favor larger dislocations.
! }
! }
! if (haveReplacement >= 0) {
! if (cache[(replacementPos+1) & mask] != null) {
! // Be conservative, to avoid breaking up a non-null run.
! cache[replacementPos & mask] = (Entry<?>) Entry.DEAD_ENTRY;
} else {
! cache[replacementPos & mask] = null;
! cacheLoad -= 1;
! }
}
- return replacement;
}
!
! /** Remove stale entries in the range near classValue. */
! private void removeStaleEntries(ClassValue<?> classValue) {
! removeStaleEntries(getCache(), classValue.hashCodeForCache, PROBE_LIMIT);
}
!
! /** Remove all stale entries, everywhere. */
! private void removeStaleEntries() {
! Entry<?>[] cache = getCache();
! removeStaleEntries(cache, 0, cache.length + PROBE_LIMIT - 1);
}
-
- /** Add the given entry to the cache, in its home location, unless it is out of date. */
- private <T> void addToCache(Entry<T> e) {
- ClassValue<T> classValue = e.classValueOrNull();
- if (classValue != null)
- addToCache(classValue, e);
}
!
! /** Add the given entry to the cache, in its home location. */
! private <T> void addToCache(ClassValue<T> classValue, Entry<T> e) {
! if (PROBE_LIMIT <= 0) return; // do not fill cache
! // Add e to the cache.
! Entry<?>[] cache = getCache();
! int mask = (cache.length-1);
! int home = classValue.hashCodeForCache & mask;
! Entry<?> e2 = placeInCache(cache, home, e, false);
! if (e2 == null) return; // done
! if (PROBE_LIMIT > 1) {
! // try to move e2 somewhere else in his probe range
! int dis2 = entryDislocation(cache, home, e2);
! int home2 = home - dis2;
! for (int i2 = home2; i2 < home2 + PROBE_LIMIT; i2++) {
! if (placeInCache(cache, i2 & mask, e2, true) == null) {
! return;
}
}
}
- // Note: At this point, e2 is just dropped from the cache.
}
! /** Store the given entry. Update cacheLoad, and return any live victim.
! * 'Gently' means return self rather than dislocating a live victim.
! */
! private Entry<?> placeInCache(Entry<?>[] cache, int pos, Entry<?> e, boolean gently) {
! Entry<?> e2 = overwrittenEntry(cache[pos]);
! if (gently && e2 != null) {
! // do not overwrite a live entry
! return e;
! } else {
! cache[pos] = e;
! return e2;
! }
! }
! /** Note an entry that is about to be overwritten.
! * If it is not live, quietly replace it by null.
! * If it is an actual null, increment cacheLoad,
! * because the caller is going to store something
! * in its place.
! */
! private <T> Entry<T> overwrittenEntry(Entry<T> e2) {
! if (e2 == null) cacheLoad += 1;
! else if (e2.isLive()) return e2;
! return null;
}
-
- /** Percent loading of cache before resize. */
- private static final int CACHE_LOAD_LIMIT = 67; // 0..100
- /** Maximum number of probes to attempt. */
- private static final int PROBE_LIMIT = 6; // 1..
- // N.B. Set PROBE_LIMIT=0 to disable all fast paths.
}
}
--- 206,418 ----
*
* @param type the type whose class value must be removed
* @throws NullPointerException if the argument is null
*/
public void remove(Class<?> type) {
! ClassValueMap.expungeStaleEntries();
! ClassValueMap map = type.classValueMap;
! if (map != null) {
! Object value, removed = null;
! do {
! value = map.get(key);
! if (value == null || value instanceof Removed) {
! // non-existence is treated as Removed(V0)
! // invoking remove() when state is Removed(VN) does not
! // change it to Removed(VN+1)
! break;
! }
! if (removed == null) {
! removed = new Removed();
! }
! } while (!map.replace(key, value, removed));
! }
}
// Possible functionality for JSR 292 MR 1
/*public*/ void put(Class<?> type, T value) {
+ ClassValueMap.expungeStaleEntries();
ClassValueMap map = getMap(type);
! map.put(key, (value == null) ? NULL_MASK : value);
}
/// --------
/// Implementation...
/// --------
/**
! * The key used in ClassValueMap for this ClassValue.
! * Since ClassValue(s) are usually assigned to static final fields, it makes
! * sense to promote the key to constant too.
*/
! @Stable
! private final Key key = new Key(this);
! /**
! * Key of a ClassValue and a tracker of the ClassValue at the same time.
*/
! private static final class Key extends PhantomReference<ClassValue<?>> {
! /** Value stream for hash. See similar structure in ThreadLocal. */
! private static final AtomicInteger nextHash = new AtomicInteger();
/** Good for power-of-two tables. See similar structure in ThreadLocal. */
private static final int HASH_INCREMENT = 0x61c88647;
! /** Single global queue for all stale keys to be enqueued */
! static final ReferenceQueue<ClassValue<?>> queue = new ReferenceQueue<>();
! @Stable
! private final int hash;
! Key(ClassValue<?> cv) {
! super(cv, queue);
! int h = nextHash.getAndAdd(HASH_INCREMENT);
! // undo the effect of CHM.spread()
! this.hash = h ^ (h >>> 16);
}
! @Override
! public int hashCode() {
! return hash;
}
! // equals is identity
}
! /** A masked null value. */
! private static final Object NULL_MASK = new Object();
! /** Removed value(s) */
! private static final class Removed {}
! /** Return the backing map associated with this type, possibly constructing it. */
! private static ClassValueMap getMap(Class<?> type) {
! ClassValueMap map = type.classValueMap;
! return (map != null) ? map : initializeMap(type);
}
! private static ClassValueMap initializeMap(Class<?> type) {
! ClassValueMap map = ClassValueMap.create();
! return U.compareAndSwapObject(type, CLASS_VALUE_MAP_OFFSET, null, map)
! ? map
! : (ClassValueMap) U.getObjectVolatile(type, CLASS_VALUE_MAP_OFFSET);
}
! /** A backing map for all ClassValues in a particular Class.
! */
! static final class ClassValueMap extends ConcurrentHashMap<Key, Object> {
! // eh, needed to silent the gods
! private static final long serialVersionUID = 1L;
! // a node in a linked list of WeakReference(s) to ClassValueMap(s)
! private static final class WeakNode extends WeakReference<ClassValueMap> {
! WeakNode next;
! WeakNode(ClassValueMap map) { super(map); }
}
! // the head of the linked list of WeakReference(s) to ClassValueMap(s)
! private static final AtomicReference<WeakNode> mapsList = new AtomicReference<>();
! // the lock used to guard expunging logic
! private static final AtomicBoolean expungeInProgress = new AtomicBoolean();
! private ClassValueMap() {
! super(1);
}
! static ClassValueMap create() {
! ClassValueMap map = new ClassValueMap();
! WeakNode node = new WeakNode(map);
! // register the weakly referenced map into the list
! do {
! node.next = mapsList.get();
! } while (!mapsList.compareAndSet(node.next, node));
! return map;
}
! static void expungeStaleEntries() {
! // make sure only one thread at a time is expunging stale entries;
! // this is important for correctness so that no stale enqueued key
! // is missed from being removed from any map that might possibly
! // hold it.
! if (!expungeInProgress.get() &&
! expungeInProgress.compareAndSet(false, true)) try {
! expungeStaleEntriesImpl();
! } finally {
! expungeInProgress.set(false);
}
}
! private static void expungeStaleEntriesImpl() {
! // start with an empty private list
! WeakNode first = null, last = null;
! // iterate Key(s) of GCed ClassValue(s)
! Key key;
! while ((key = (Key) Key.queue.poll()) != null) {
! // steal any (newly) registered map(s) from the shared 'mapsList'
! // as they might already be holding the stale 'key' that has just
! // been removed from the queue. The following guarantees that
! // no (stale-key, live-map) combination is missed:
! // - a map is 1st registered into the mapsList and then non-stale
! // keys are inserted into it
! // - a non-stale key becomes stale when a ClassValue that it
! // phantomly references is GCed; the key is then enqueued
! // - a stale key is 1st removed from the queue and then mapsList
! // is checked for any (newly) registered map(s)
! if (mapsList.get() != null) {
! WeakNode stolen = mapsList.getAndSet(null);
! // add them to the end of current private list
! if (last != null) {
! last.next = stolen;
} else {
! // assert first == null;
! first = stolen;
}
}
! // iterate the accumulated private list of maps
! last = null;
! for (WeakNode node = first; node != null; ) {
! ClassValueMap map = node.get();
! if (map == null) {
! // Class and its ClassValueMap have already been GCed
! // -> remove the node from the list
! if (last == null) {
! first = node = node.next;
! } else {
! last.next = node = node.next;
}
! } else {
! // ClassValueMap is still alive
! // -> attempt to remove the key from it
! map.remove(key);
! // navigate to next in list
! last = node;
! node = node.next;
}
}
! // at this time, 'last' points to the last WeakNode in the private
! // list (if any) and the following always holds:
! // assert (first == null) == (last == null);
}
+ // re-insert the stolen and expunged list of map(s) back into shared
+ // mapsList
+ if (last != null) {
+ do {
+ last.next = mapsList.get();
+ } while (!mapsList.compareAndSet(last.next, first));
}
}
}
! /** We need to cas */
! private static final Unsafe U = Unsafe.getUnsafe();
! private static final long CLASS_VALUE_MAP_OFFSET;
! static {
! try {
! CLASS_VALUE_MAP_OFFSET = U.objectFieldOffset(
! Class.class.getDeclaredField("classValueMap"));
! } catch (Exception e) {
! throw new Error(e);
}
}
}
< prev index next >