changeset 6589:3320bcbd2eaa

7123493: (proxy) Proxy.getProxyClass doesn't scale under high load Reviewed-by: mchung
author robm
date Mon, 23 Sep 2013 16:48:03 +0100
parents b39302d414e4
children 64054ee415d5
files src/share/classes/java/lang/reflect/Proxy.java src/share/classes/java/lang/reflect/WeakCache.java
diffstat 2 files changed, 606 insertions(+), 203 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/lang/reflect/Proxy.java	Mon Sep 23 17:58:31 2013 +0400
+++ b/src/share/classes/java/lang/reflect/Proxy.java	Mon Sep 23 16:48:03 2013 +0100
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1999, 2010, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1999, 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
@@ -25,19 +25,15 @@
 
 package java.lang.reflect;
 
-import java.lang.ref.Reference;
 import java.lang.ref.WeakReference;
+import java.lang.reflect.WeakCache.BiFunction;
 import java.security.AccessController;
 import java.security.Permission;
 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 sun.misc.ProxyGenerator;
 import sun.reflect.CallerSensitive;
 import sun.reflect.Reflection;
@@ -230,27 +226,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.
@@ -464,131 +448,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);
+    }
 
-        /* collect interface names to use as key for proxy class cache */
-        String[] interfaceNames = new String[interfaces.length];
+    /*
+     * a key used for proxy class with 0 implemented interfaces
+     */
+    private static final Object key0 = new Object();
 
-        // for detecting duplicates
-        Set<Class<?>> interfaceSet = new HashSet<>();
+    /*
+     * Key1 and Key2 are optimized for the common use of dynamic proxies
+     * that implement 1 or 2 interfaces.
+     */
 
-        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 1 implemented interface
+     */
+    private static final class Key1 extends WeakReference<Class<?>> {
+        private final int hash;
+
+        Key1(Class<?> intf) {
+            super(intf);
+            this.hash = intf.hashCode();
+        }
+
+        @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();
+        }
+    }
+
+    /*
+     * 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");
+        }
+
+        @Override
+        public int hashCode() {
+            return hash;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            return this == obj ||
+                   obj != null &&
+                   obj.getClass() == KeyX.class &&
+                   equals(refs, ((KeyX) obj).refs);
+        }
+
+        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;
+                }
+            }
+            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) {
+                }
+                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());
+                }
             }
 
-            /*
-             * 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);
-
-        /*
-         * 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.
-             */
-        }
-
-        /*
-         * 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();
-                }
-                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;
-                }
-            } while (true);
-        }
-
-        try {
             String proxyPkg = null;     // package to define proxy class in
 
             /*
@@ -596,10 +639,10 @@
              * 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)) {
-                    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) {
@@ -616,60 +659,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);
+            try {
+                return defineClass0(loader, proxyName,
+                                    proxyClassFile, 0, proxyClassFile.length);
+            } catch (ClassFormatError e) {
                 /*
-                 * Choose a name for the proxy class to generate.
+                 * 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).
                  */
-                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.
-                 */
-                byte[] proxyClassFile = ProxyGenerator.generateProxyClass(
-                    proxyName, interfaces);
-                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;
     }
 
     /**
@@ -773,11 +787,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/src/share/classes/java/lang/reflect/WeakCache.java	Mon Sep 23 16:48:03 2013 +0100
@@ -0,0 +1,393 @@
+/*
+ * 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;
+
+/**
+ * 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> {
+
+    interface BiFunction<T, U, R> {
+
+        /**
+         * Applies this function to the given arguments.
+         *
+         * @param t the first function argument
+         * @param u the second function argument
+         * @return the function result
+         */
+        R apply(T t, U u);
+    }
+
+    interface Supplier<T> {
+        T get();
+    }
+
+    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);
+                }
+            }
+        }
+    }
+}