7123493: (proxy) Proxy.getProxyClass doesn't scale under high load
Reviewed-by: mchung
--- a/jdk/src/share/classes/java/lang/reflect/Proxy.java Fri Apr 26 14:16:23 2013 -0700
+++ b/jdk/src/share/classes/java/lang/reflect/Proxy.java Fri Apr 26 16:09:53 2013 -0700
@@ -25,18 +25,14 @@
package java.lang.reflect;
-import java.lang.ref.Reference;
import java.lang.ref.WeakReference;
import java.security.AccessController;
import java.security.PrivilegedAction;
import java.util.Arrays;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.HashSet;
+import java.util.IdentityHashMap;
import java.util.Map;
-import java.util.Set;
-import java.util.List;
-import java.util.WeakHashMap;
+import java.util.concurrent.atomic.AtomicLong;
+import java.util.function.BiFunction;
import sun.misc.ProxyGenerator;
import sun.misc.VM;
import sun.reflect.CallerSensitive;
@@ -232,27 +228,15 @@
private static final long serialVersionUID = -2222568056686623797L;
- /** prefix for all proxy class names */
- private final static String proxyClassNamePrefix = "$Proxy";
-
/** parameter types of a proxy class constructor */
- private final static Class[] constructorParams =
+ private static final Class<?>[] constructorParams =
{ InvocationHandler.class };
- /** maps a class loader to the proxy class cache for that loader */
- private static Map<ClassLoader, Map<List<String>, Object>> loaderToCache
- = new WeakHashMap<>();
-
- /** marks that a particular proxy class is currently being generated */
- private static Object pendingGenerationMarker = new Object();
-
- /** next number to use for generation of unique proxy class names */
- private static long nextUniqueNumber = 0;
- private static Object nextUniqueNumberLock = new Object();
-
- /** set of all generated proxy classes, for isProxyClass implementation */
- private static Map<Class<?>, Void> proxyClasses =
- Collections.synchronizedMap(new WeakHashMap<Class<?>, Void>());
+ /**
+ * a cache of proxy classes
+ */
+ private static final WeakCache<ClassLoader, Class<?>[], Class<?>>
+ proxyClassCache = new WeakCache<>(new KeyFactory(), new ProxyClassFactory());
/**
* the invocation handler for this proxy instance.
@@ -423,131 +407,190 @@
throw new IllegalArgumentException("interface limit exceeded");
}
- Class<?> proxyClass = null;
+ // If the proxy class defined by the given loader implementing
+ // the given interfaces exists, this will simply return the cached copy;
+ // otherwise, it will create the proxy class via the ProxyClassFactory
+ return proxyClassCache.get(loader, interfaces);
+ }
+
+ /*
+ * a key used for proxy class with 0 implemented interfaces
+ */
+ private static final Object key0 = new Object();
+
+ /*
+ * Key1 and Key2 are optimized for the common use of dynamic proxies
+ * that implement 1 or 2 interfaces.
+ */
- /* collect interface names to use as key for proxy class cache */
- String[] interfaceNames = new String[interfaces.length];
+ /*
+ * a key used for proxy class with 1 implemented interface
+ */
+ private static final class Key1 extends WeakReference<Class<?>> {
+ private final int hash;
+
+ Key1(Class<?> intf) {
+ super(intf);
+ this.hash = intf.hashCode();
+ }
- // for detecting duplicates
- Set<Class<?>> interfaceSet = new HashSet<>();
+ @Override
+ public int hashCode() {
+ return hash;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ Class<?> intf;
+ return this == obj ||
+ obj != null &&
+ obj.getClass() == Key1.class &&
+ (intf = get()) != null &&
+ intf == ((Key1) obj).get();
+ }
+ }
- for (int i = 0; i < interfaces.length; i++) {
- /*
- * Verify that the class loader resolves the name of this
- * interface to the same Class object.
- */
- String interfaceName = interfaces[i].getName();
- Class<?> interfaceClass = null;
- try {
- interfaceClass = Class.forName(interfaceName, false, loader);
- } catch (ClassNotFoundException e) {
+ /*
+ * a key used for proxy class with 2 implemented interfaces
+ */
+ private static final class Key2 extends WeakReference<Class<?>> {
+ private final int hash;
+ private final WeakReference<Class<?>> ref2;
+
+ Key2(Class<?> intf1, Class<?> intf2) {
+ super(intf1);
+ hash = 31 * intf1.hashCode() + intf2.hashCode();
+ ref2 = new WeakReference<Class<?>>(intf2);
+ }
+
+ @Override
+ public int hashCode() {
+ return hash;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ Class<?> intf1, intf2;
+ return this == obj ||
+ obj != null &&
+ obj.getClass() == Key2.class &&
+ (intf1 = get()) != null &&
+ intf1 == ((Key2) obj).get() &&
+ (intf2 = ref2.get()) != null &&
+ intf2 == ((Key2) obj).ref2.get();
+ }
+ }
+
+ /*
+ * a key used for proxy class with any number of implemented interfaces
+ * (used here for 3 or more only)
+ */
+ private static final class KeyX {
+ private final int hash;
+ private final WeakReference<Class<?>>[] refs;
+
+ KeyX(Class<?>[] interfaces) {
+ hash = Arrays.hashCode(interfaces);
+ refs = new WeakReference[interfaces.length];
+ for (int i = 0; i < interfaces.length; i++) {
+ refs[i] = new WeakReference<>(interfaces[i]);
}
- if (interfaceClass != interfaces[i]) {
- throw new IllegalArgumentException(
- interfaces[i] + " is not visible from class loader");
- }
-
- /*
- * Verify that the Class object actually represents an
- * interface.
- */
- if (!interfaceClass.isInterface()) {
- throw new IllegalArgumentException(
- interfaceClass.getName() + " is not an interface");
- }
-
- /*
- * Verify that this interface is not a duplicate.
- */
- if (interfaceSet.contains(interfaceClass)) {
- throw new IllegalArgumentException(
- "repeated interface: " + interfaceClass.getName());
- }
- interfaceSet.add(interfaceClass);
-
- interfaceNames[i] = interfaceName;
}
- /*
- * Using string representations of the proxy interfaces as
- * keys in the proxy class cache (instead of their Class
- * objects) is sufficient because we require the proxy
- * interfaces to be resolvable by name through the supplied
- * class loader, and it has the advantage that using a string
- * representation of a class makes for an implicit weak
- * reference to the class.
- */
- List<String> key = Arrays.asList(interfaceNames);
+ @Override
+ public int hashCode() {
+ return hash;
+ }
- /*
- * Find or create the proxy class cache for the class loader.
- */
- Map<List<String>, Object> cache;
- synchronized (loaderToCache) {
- cache = loaderToCache.get(loader);
- if (cache == null) {
- cache = new HashMap<>();
- loaderToCache.put(loader, cache);
- }
- /*
- * This mapping will remain valid for the duration of this
- * method, without further synchronization, because the mapping
- * will only be removed if the class loader becomes unreachable.
- */
+ @Override
+ public boolean equals(Object obj) {
+ return this == obj ||
+ obj != null &&
+ obj.getClass() == KeyX.class &&
+ equals(refs, ((KeyX) obj).refs);
}
- /*
- * Look up the list of interfaces in the proxy class cache using
- * the key. This lookup will result in one of three possible
- * kinds of values:
- * null, if there is currently no proxy class for the list of
- * interfaces in the class loader,
- * the pendingGenerationMarker object, if a proxy class for the
- * list of interfaces is currently being generated,
- * or a weak reference to a Class object, if a proxy class for
- * the list of interfaces has already been generated.
- */
- synchronized (cache) {
- /*
- * Note that we need not worry about reaping the cache for
- * entries with cleared weak references because if a proxy class
- * has been garbage collected, its class loader will have been
- * garbage collected as well, so the entire cache will be reaped
- * from the loaderToCache map.
- */
- do {
- Object value = cache.get(key);
- if (value instanceof Reference) {
- proxyClass = (Class<?>) ((Reference) value).get();
+ private static boolean equals(WeakReference<Class<?>>[] refs1,
+ WeakReference<Class<?>>[] refs2) {
+ if (refs1.length != refs2.length) {
+ return false;
+ }
+ for (int i = 0; i < refs1.length; i++) {
+ Class<?> intf = refs1[i].get();
+ if (intf == null || intf != refs2[i].get()) {
+ return false;
}
- if (proxyClass != null) {
- // proxy class already generated: return it
- return proxyClass;
- } else if (value == pendingGenerationMarker) {
- // proxy class being generated: wait for it
- try {
- cache.wait();
- } catch (InterruptedException e) {
- /*
- * The class generation that we are waiting for should
- * take a small, bounded time, so we can safely ignore
- * thread interrupts here.
- */
- }
- continue;
- } else {
- /*
- * No proxy class for this list of interfaces has been
- * generated or is being generated, so we will go and
- * generate it now. Mark it as pending generation.
- */
- cache.put(key, pendingGenerationMarker);
- break;
+ }
+ return true;
+ }
+ }
+
+ /**
+ * A function that maps an array of interfaces to an optimal key where
+ * Class objects representing interfaces are weakly referenced.
+ */
+ private static final class KeyFactory
+ implements BiFunction<ClassLoader, Class<?>[], Object>
+ {
+ @Override
+ public Object apply(ClassLoader classLoader, Class<?>[] interfaces) {
+ switch (interfaces.length) {
+ case 1: return new Key1(interfaces[0]); // the most frequent
+ case 2: return new Key2(interfaces[0], interfaces[1]);
+ case 0: return key0;
+ default: return new KeyX(interfaces);
+ }
+ }
+ }
+
+ /**
+ * A factory function that generates, defines and returns the proxy class given
+ * the ClassLoader and array of interfaces.
+ */
+ private static final class ProxyClassFactory
+ implements BiFunction<ClassLoader, Class<?>[], Class<?>>
+ {
+ // prefix for all proxy class names
+ private static final String proxyClassNamePrefix = "$Proxy";
+
+ // next number to use for generation of unique proxy class names
+ private static final AtomicLong nextUniqueNumber = new AtomicLong();
+
+ @Override
+ public Class<?> apply(ClassLoader loader, Class<?>[] interfaces) {
+
+ Map<Class<?>, Boolean> interfaceSet = new IdentityHashMap<>(interfaces.length);
+ for (Class<?> intf : interfaces) {
+ /*
+ * Verify that the class loader resolves the name of this
+ * interface to the same Class object.
+ */
+ Class<?> interfaceClass = null;
+ try {
+ interfaceClass = Class.forName(intf.getName(), false, loader);
+ } catch (ClassNotFoundException e) {
}
- } while (true);
- }
+ if (interfaceClass != intf) {
+ throw new IllegalArgumentException(
+ intf + " is not visible from class loader");
+ }
+ /*
+ * Verify that the Class object actually represents an
+ * interface.
+ */
+ if (!interfaceClass.isInterface()) {
+ throw new IllegalArgumentException(
+ interfaceClass.getName() + " is not an interface");
+ }
+ /*
+ * Verify that this interface is not a duplicate.
+ */
+ if (interfaceSet.put(interfaceClass, Boolean.TRUE) != null) {
+ throw new IllegalArgumentException(
+ "repeated interface: " + interfaceClass.getName());
+ }
+ }
- try {
String proxyPkg = null; // package to define proxy class in
int accessFlags = Modifier.PUBLIC | Modifier.FINAL;
@@ -556,11 +599,11 @@
* proxy class will be defined in the same package. Verify that
* all non-public proxy interfaces are in the same package.
*/
- for (int i = 0; i < interfaces.length; i++) {
- int flags = interfaces[i].getModifiers();
+ for (Class<?> intf : interfaces) {
+ int flags = intf.getModifiers();
if (!Modifier.isPublic(flags)) {
accessFlags = Modifier.FINAL;
- String name = interfaces[i].getName();
+ String name = intf.getName();
int n = name.lastIndexOf('.');
String pkg = ((n == -1) ? "" : name.substring(0, n + 1));
if (proxyPkg == null) {
@@ -577,60 +620,31 @@
proxyPkg = ReflectUtil.PROXY_PACKAGE + ".";
}
- {
+ /*
+ * Choose a name for the proxy class to generate.
+ */
+ long num = nextUniqueNumber.getAndIncrement();
+ String proxyName = proxyPkg + proxyClassNamePrefix + num;
+
+ /*
+ * Generate the specified proxy class.
+ */
+ byte[] proxyClassFile = ProxyGenerator.generateProxyClass(
+ proxyName, interfaces, accessFlags);
+ try {
+ return defineClass0(loader, proxyName,
+ proxyClassFile, 0, proxyClassFile.length);
+ } catch (ClassFormatError e) {
/*
- * Choose a name for the proxy class to generate.
- */
- long num;
- synchronized (nextUniqueNumberLock) {
- num = nextUniqueNumber++;
- }
- String proxyName = proxyPkg + proxyClassNamePrefix + num;
- /*
- * Verify that the class loader hasn't already
- * defined a class with the chosen name.
- */
-
- /*
- * Generate the specified proxy class.
+ * A ClassFormatError here means that (barring bugs in the
+ * proxy class generation code) there was some other
+ * invalid aspect of the arguments supplied to the proxy
+ * class creation (such as virtual machine limitations
+ * exceeded).
*/
- byte[] proxyClassFile = ProxyGenerator.generateProxyClass(
- proxyName, interfaces, accessFlags);
- try {
- proxyClass = defineClass0(loader, proxyName,
- proxyClassFile, 0, proxyClassFile.length);
- } catch (ClassFormatError e) {
- /*
- * A ClassFormatError here means that (barring bugs in the
- * proxy class generation code) there was some other
- * invalid aspect of the arguments supplied to the proxy
- * class creation (such as virtual machine limitations
- * exceeded).
- */
- throw new IllegalArgumentException(e.toString());
- }
- }
- // add to set of all generated proxy classes, for isProxyClass
- proxyClasses.put(proxyClass, null);
-
- } finally {
- /*
- * We must clean up the "pending generation" state of the proxy
- * class cache entry somehow. If a proxy class was successfully
- * generated, store it in the cache (with a weak reference);
- * otherwise, remove the reserved entry. In all cases, notify
- * all waiters on reserved entries in this cache.
- */
- synchronized (cache) {
- if (proxyClass != null) {
- cache.put(key, new WeakReference<Class<?>>(proxyClass));
- } else {
- cache.remove(key);
- }
- cache.notifyAll();
+ throw new IllegalArgumentException(e.toString());
}
}
- return proxyClass;
}
/**
@@ -757,21 +771,6 @@
}
}
- private static Object newInstance(Constructor<?> cons, InvocationHandler h) {
- try {
- return cons.newInstance(new Object[] {h} );
- } catch (IllegalAccessException | InstantiationException e) {
- throw new InternalError(e.toString(), e);
- } catch (InvocationTargetException e) {
- Throwable t = e.getCause();
- if (t instanceof RuntimeException) {
- throw (RuntimeException) t;
- } else {
- throw new InternalError(t.toString(), t);
- }
- }
- }
-
/**
* Returns true if and only if the specified class was dynamically
* generated to be a proxy class using the {@code getProxyClass}
@@ -787,11 +786,7 @@
* @throws NullPointerException if {@code cl} is {@code null}
*/
public static boolean isProxyClass(Class<?> cl) {
- if (cl == null) {
- throw new NullPointerException();
- }
-
- return proxyClasses.containsKey(cl);
+ return Proxy.class.isAssignableFrom(cl) && proxyClassCache.containsValue(cl);
}
/**
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/src/share/classes/java/lang/reflect/WeakCache.java Fri Apr 26 16:09:53 2013 -0700
@@ -0,0 +1,379 @@
+/*
+ * Copyright (c) 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
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package java.lang.reflect;
+
+import java.lang.ref.ReferenceQueue;
+import java.lang.ref.WeakReference;
+import java.util.Objects;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentMap;
+import java.util.function.BiFunction;
+import java.util.function.Supplier;
+
+/**
+ * Cache mapping pairs of {@code (key, sub-key) -> value}. Keys and values are
+ * weakly but sub-keys are strongly referenced. Keys are passed directly to
+ * {@link #get} method which also takes a {@code parameter}. Sub-keys are
+ * calculated from keys and parameters using the {@code subKeyFactory} function
+ * passed to the constructor. Values are calculated from keys and parameters
+ * using the {@code valueFactory} function passed to the constructor.
+ * Keys can be {@code null} and are compared by identity while sub-keys returned by
+ * {@code subKeyFactory} or values returned by {@code valueFactory}
+ * can not be null. Sub-keys are compared using their {@link #equals} method.
+ * Entries are expunged from cache lazily on each invocation to {@link #get},
+ * {@link #containsValue} or {@link #size} methods when the WeakReferences to
+ * keys are cleared. Cleared WeakReferences to individual values don't cause
+ * expunging, but such entries are logically treated as non-existent and
+ * trigger re-evaluation of {@code valueFactory} on request for their
+ * key/subKey.
+ *
+ * @author Peter Levart
+ * @param <K> type of keys
+ * @param <P> type of parameters
+ * @param <V> type of values
+ */
+final class WeakCache<K, P, V> {
+
+ private final ReferenceQueue<K> refQueue
+ = new ReferenceQueue<>();
+ // the key type is Object for supporting null key
+ private final ConcurrentMap<Object, ConcurrentMap<Object, Supplier<V>>> map
+ = new ConcurrentHashMap<>();
+ private final ConcurrentMap<Supplier<V>, Boolean> reverseMap
+ = new ConcurrentHashMap<>();
+ private final BiFunction<K, P, ?> subKeyFactory;
+ private final BiFunction<K, P, V> valueFactory;
+
+ /**
+ * Construct an instance of {@code WeakCache}
+ *
+ * @param subKeyFactory a function mapping a pair of
+ * {@code (key, parameter) -> sub-key}
+ * @param valueFactory a function mapping a pair of
+ * {@code (key, parameter) -> value}
+ * @throws NullPointerException if {@code subKeyFactory} or
+ * {@code valueFactory} is null.
+ */
+ public WeakCache(BiFunction<K, P, ?> subKeyFactory,
+ BiFunction<K, P, V> valueFactory) {
+ this.subKeyFactory = Objects.requireNonNull(subKeyFactory);
+ this.valueFactory = Objects.requireNonNull(valueFactory);
+ }
+
+ /**
+ * Look-up the value through the cache. This always evaluates the
+ * {@code subKeyFactory} function and optionally evaluates
+ * {@code valueFactory} function if there is no entry in the cache for given
+ * pair of (key, subKey) or the entry has already been cleared.
+ *
+ * @param key possibly null key
+ * @param parameter parameter used together with key to create sub-key and
+ * value (should not be null)
+ * @return the cached value (never null)
+ * @throws NullPointerException if {@code parameter} passed in or
+ * {@code sub-key} calculated by
+ * {@code subKeyFactory} or {@code value}
+ * calculated by {@code valueFactory} is null.
+ */
+ public V get(K key, P parameter) {
+ Objects.requireNonNull(parameter);
+
+ expungeStaleEntries();
+
+ Object cacheKey = CacheKey.valueOf(key, refQueue);
+
+ // lazily install the 2nd level valuesMap for the particular cacheKey
+ ConcurrentMap<Object, Supplier<V>> valuesMap = map.get(cacheKey);
+ if (valuesMap == null) {
+ ConcurrentMap<Object, Supplier<V>> oldValuesMap
+ = map.putIfAbsent(cacheKey,
+ valuesMap = new ConcurrentHashMap<>());
+ if (oldValuesMap != null) {
+ valuesMap = oldValuesMap;
+ }
+ }
+
+ // create subKey and retrieve the possible Supplier<V> stored by that
+ // subKey from valuesMap
+ Object subKey = Objects.requireNonNull(subKeyFactory.apply(key, parameter));
+ Supplier<V> supplier = valuesMap.get(subKey);
+ Factory factory = null;
+
+ while (true) {
+ if (supplier != null) {
+ // supplier might be a Factory or a CacheValue<V> instance
+ V value = supplier.get();
+ if (value != null) {
+ return value;
+ }
+ }
+ // else no supplier in cache
+ // or a supplier that returned null (could be a cleared CacheValue
+ // or a Factory that wasn't successful in installing the CacheValue)
+
+ // lazily construct a Factory
+ if (factory == null) {
+ factory = new Factory(key, parameter, subKey, valuesMap);
+ }
+
+ if (supplier == null) {
+ supplier = valuesMap.putIfAbsent(subKey, factory);
+ if (supplier == null) {
+ // successfully installed Factory
+ supplier = factory;
+ }
+ // else retry with winning supplier
+ } else {
+ if (valuesMap.replace(subKey, supplier, factory)) {
+ // successfully replaced
+ // cleared CacheEntry / unsuccessful Factory
+ // with our Factory
+ supplier = factory;
+ } else {
+ // retry with current supplier
+ supplier = valuesMap.get(subKey);
+ }
+ }
+ }
+ }
+
+ /**
+ * Checks whether the specified non-null value is already present in this
+ * {@code WeakCache}. The check is made using identity comparison regardless
+ * of whether value's class overrides {@link Object#equals} or not.
+ *
+ * @param value the non-null value to check
+ * @return true if given {@code value} is already cached
+ * @throws NullPointerException if value is null
+ */
+ public boolean containsValue(V value) {
+ Objects.requireNonNull(value);
+
+ expungeStaleEntries();
+ return reverseMap.containsKey(new LookupValue<>(value));
+ }
+
+ /**
+ * Returns the current number of cached entries that
+ * can decrease over time when keys/values are GC-ed.
+ */
+ public int size() {
+ expungeStaleEntries();
+ return reverseMap.size();
+ }
+
+ private void expungeStaleEntries() {
+ CacheKey<K> cacheKey;
+ while ((cacheKey = (CacheKey<K>)refQueue.poll()) != null) {
+ cacheKey.expungeFrom(map, reverseMap);
+ }
+ }
+
+ /**
+ * A factory {@link Supplier} that implements the lazy synchronized
+ * construction of the value and installment of it into the cache.
+ */
+ private final class Factory implements Supplier<V> {
+
+ private final K key;
+ private final P parameter;
+ private final Object subKey;
+ private final ConcurrentMap<Object, Supplier<V>> valuesMap;
+
+ Factory(K key, P parameter, Object subKey,
+ ConcurrentMap<Object, Supplier<V>> valuesMap) {
+ this.key = key;
+ this.parameter = parameter;
+ this.subKey = subKey;
+ this.valuesMap = valuesMap;
+ }
+
+ @Override
+ public synchronized V get() { // serialize access
+ // re-check
+ Supplier<V> supplier = valuesMap.get(subKey);
+ if (supplier != this) {
+ // something changed while we were waiting:
+ // might be that we were replaced by a CacheValue
+ // or were removed because of failure ->
+ // return null to signal WeakCache.get() to retry
+ // the loop
+ return null;
+ }
+ // else still us (supplier == this)
+
+ // create new value
+ V value = null;
+ try {
+ value = Objects.requireNonNull(valueFactory.apply(key, parameter));
+ } finally {
+ if (value == null) { // remove us on failure
+ valuesMap.remove(subKey, this);
+ }
+ }
+ // the only path to reach here is with non-null value
+ assert value != null;
+
+ // wrap value with CacheValue (WeakReference)
+ CacheValue<V> cacheValue = new CacheValue<>(value);
+
+ // try replacing us with CacheValue (this should always succeed)
+ if (valuesMap.replace(subKey, this, cacheValue)) {
+ // put also in reverseMap
+ reverseMap.put(cacheValue, Boolean.TRUE);
+ } else {
+ throw new AssertionError("Should not reach here");
+ }
+
+ // successfully replaced us with new CacheValue -> return the value
+ // wrapped by it
+ return value;
+ }
+ }
+
+ /**
+ * Common type of value suppliers that are holding a referent.
+ * The {@link #equals} and {@link #hashCode} of implementations is defined
+ * to compare the referent by identity.
+ */
+ private interface Value<V> extends Supplier<V> {}
+
+ /**
+ * An optimized {@link Value} used to look-up the value in
+ * {@link WeakCache#containsValue} method so that we are not
+ * constructing the whole {@link CacheValue} just to look-up the referent.
+ */
+ private static final class LookupValue<V> implements Value<V> {
+ private final V value;
+
+ LookupValue(V value) {
+ this.value = value;
+ }
+
+ @Override
+ public V get() {
+ return value;
+ }
+
+ @Override
+ public int hashCode() {
+ return System.identityHashCode(value); // compare by identity
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ return obj == this ||
+ obj instanceof Value &&
+ this.value == ((Value<?>) obj).get(); // compare by identity
+ }
+ }
+
+ /**
+ * A {@link Value} that weakly references the referent.
+ */
+ private static final class CacheValue<V>
+ extends WeakReference<V> implements Value<V>
+ {
+ private final int hash;
+
+ CacheValue(V value) {
+ super(value);
+ this.hash = System.identityHashCode(value); // compare by identity
+ }
+
+ @Override
+ public int hashCode() {
+ return hash;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ V value;
+ return obj == this ||
+ obj instanceof Value &&
+ // cleared CacheValue is only equal to itself
+ (value = get()) != null &&
+ value == ((Value<?>) obj).get(); // compare by identity
+ }
+ }
+
+ /**
+ * CacheKey containing a weakly referenced {@code key}. It registers
+ * itself with the {@code refQueue} so that it can be used to expunge
+ * the entry when the {@link WeakReference} is cleared.
+ */
+ private static final class CacheKey<K> extends WeakReference<K> {
+
+ // a replacement for null keys
+ private static final Object NULL_KEY = new Object();
+
+ static <K> Object valueOf(K key, ReferenceQueue<K> refQueue) {
+ return key == null
+ // null key means we can't weakly reference it,
+ // so we use a NULL_KEY singleton as cache key
+ ? NULL_KEY
+ // non-null key requires wrapping with a WeakReference
+ : new CacheKey<>(key, refQueue);
+ }
+
+ private final int hash;
+
+ private CacheKey(K key, ReferenceQueue<K> refQueue) {
+ super(key, refQueue);
+ this.hash = System.identityHashCode(key); // compare by identity
+ }
+
+ @Override
+ public int hashCode() {
+ return hash;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ K key;
+ return obj == this ||
+ obj != null &&
+ obj.getClass() == this.getClass() &&
+ // cleared CacheKey is only equal to itself
+ (key = this.get()) != null &&
+ // compare key by identity
+ key == ((CacheKey<K>) obj).get();
+ }
+
+ void expungeFrom(ConcurrentMap<?, ? extends ConcurrentMap<?, ?>> map,
+ ConcurrentMap<?, Boolean> reverseMap) {
+ // removing just by key is always safe here because after a CacheKey
+ // is cleared and enqueue-ed it is only equal to itself
+ // (see equals method)...
+ ConcurrentMap<?, ?> valuesMap = map.remove(this);
+ // remove also from reverseMap if needed
+ if (valuesMap != null) {
+ for (Object cacheValue : valuesMap.values()) {
+ reverseMap.remove(cacheValue);
+ }
+ }
+ }
+ }
+}