1 /*
   2  * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 package jdk.internal.util.concurrent;
  25 
  26 import jdk.internal.loader.BootLoader;
  27 import jdk.internal.misc.JavaLangAccess;
  28 import jdk.internal.misc.SharedSecrets;
  29 
  30 import java.lang.reflect.UndeclaredThrowableException;
  31 import java.util.Iterator;
  32 import java.util.Objects;
  33 import java.util.concurrent.ConcurrentHashMap;
  34 import java.util.function.BiFunction;
  35 import java.util.function.Supplier;
  36 
  37 /**
  38  * AbstractClassLoaderValue is a superclass of root-{@link ClassLoaderValue}
  39  * and {@link Sub sub}-ClassLoaderValue.
  40  *
  41  * @param <CLV> the type of concrete ClassLoaderValue (this type)
  42  * @param <V>   the type of values associated with ClassLoaderValue
  43  */
  44 public abstract class AbstractClassLoaderValue<CLV extends AbstractClassLoaderValue<CLV, V>, V> {
  45 
  46     /**
  47      * Sole constructor.
  48      */
  49     AbstractClassLoaderValue() {}
  50 
  51     /**
  52      * Returns the key component of this ClassLoaderValue. The key component of
  53      * the root-{@link ClassLoaderValue} is the ClassLoaderValue itself,
  54      * while the key component of a {@link #sub(Object) sub}-ClassLoaderValue
  55      * is what was given to construct it.
  56      *
  57      * @return the key component of this ClassLoaderValue.
  58      */
  59     public abstract Object key();
  60 
  61     /**
  62      * Constructs new sub-ClassLoaderValue of this ClassLoaderValue with given
  63      * key component.
  64      *
  65      * @param key the key component of the sub-ClassLoaderValue.
  66      * @param <K> the type of the key component.
  67      * @return a sub-ClassLoaderValue of this ClassLoaderValue for given key
  68      */
  69     public <K> Sub<K> sub(K key) {
  70         return new Sub<>(key);
  71     }
  72 
  73     /**
  74      * Returns {@code true} if this ClassLoaderValue is equal to given {@code clv}
  75      * or if this ClassLoaderValue was derived from given {@code clv} by a chain
  76      * of {@link #sub(Object)} invocations.
  77      *
  78      * @param clv the ClassLoaderValue to test this against
  79      * @return if this ClassLoaderValue is equal to given {@code clv} or
  80      * its descendant
  81      */
  82     public abstract boolean isEqualOrDescendantOf(AbstractClassLoaderValue<?, V> clv);
  83 
  84     /**
  85      * Returns the value associated with this ClassLoaderValue and given ClassLoader
  86      * or {@code null} if there is none.
  87      *
  88      * @param cl the ClassLoader for the associated value
  89      * @return the value associated with this ClassLoaderValue and given ClassLoader
  90      * or {@code null} if there is none.
  91      */
  92     public V get(ClassLoader cl) {
  93         Object val = AbstractClassLoaderValue.<CLV>map(cl).get(this);
  94         try {
  95             return extractValue(val);
  96         } catch (Memoizer.RecursiveInvocationException e) {
  97             // propagate recursive get() for the same key that is just
  98             // being calculated in computeIfAbsent()
  99             throw e;
 100         } catch (Throwable t) {
 101             // don't propagate exceptions thrown from Memoizer - pretend
 102             // that there was no entry
 103             // (computeIfAbsent invocation will try to remove it anyway)
 104             return null;
 105         }
 106     }
 107 
 108     /**
 109      * Associates given value {@code v} with this ClassLoaderValue and given
 110      * ClassLoader and returns {@code null} if there was no previously associated
 111      * value or does nothing and returns previously associated value if there
 112      * was one.
 113      *
 114      * @param cl the ClassLoader for the associated value
 115      * @param v  the value to associate
 116      * @return previously associated value or null if there was none
 117      */
 118     public V putIfAbsent(ClassLoader cl, V v) {
 119         ConcurrentHashMap<CLV, Object> map = map(cl);
 120         @SuppressWarnings("unchecked")
 121         CLV clv = (CLV) this;
 122         while (true) {
 123             try {
 124                 Object val = map.putIfAbsent(clv, v);
 125                 return extractValue(val);
 126             } catch (Memoizer.RecursiveInvocationException e) {
 127                 // propagate RecursiveInvocationException for the same key that
 128                 // is just being calculated in computeIfAbsent
 129                 throw e;
 130             } catch (Throwable t) {
 131                 // don't propagate exceptions thrown from foreign Memoizer -
 132                 // pretend that there was no entry and retry
 133                 // (foreign computeIfAbsent invocation will try to remove it anyway)
 134             }
 135             // TODO:
 136             // Thread.onSpinLoop(); // when available
 137         }
 138     }
 139 
 140     /**
 141      * Removes the value associated with this ClassLoaderValue and given
 142      * ClassLoader if the associated value is equal to given value {@code v} and
 143      * returns {@code true} or does nothing and returns {@code false} if there is
 144      * no currently associated value or it is not equal to given value {@code v}.
 145      *
 146      * @param cl the ClassLoader for the associated value
 147      * @param v  the value to compare with currently associated value
 148      * @return {@code true} if the association was removed or {@code false} if not
 149      */
 150     public boolean remove(ClassLoader cl, Object v) {
 151         return AbstractClassLoaderValue.<CLV>map(cl).remove(this, v);
 152     }
 153 
 154     /**
 155      * Replaces the value associated with this ClassLoaderValue and given
 156      * ClassLoader with {@code newV} if the associated value is equal to given
 157      * value {@code oldV} and returns {@code true} or does nothing and returns
 158      * {@code false} if there is no currently associated value or it is not equal
 159      * to given value {@code oldV}.
 160      *
 161      * @param cl the ClassLoader for the associated value
 162      * @param oldV  the value to compare with currently associated value
 163      * @param newV  the value to associate if current value is equal to oldV
 164      * @return {@code true} if the association was replaced or {@code false} if not
 165      */
 166     public boolean replace(ClassLoader cl, V oldV, V newV) {
 167         @SuppressWarnings("unchecked")
 168         CLV clv = (CLV) this;
 169         return AbstractClassLoaderValue.<CLV>map(cl).replace(clv, oldV, newV);
 170     }
 171 
 172     /**
 173      * Returns the value associated with this ClassLoaderValue and given
 174      * ClassLoader if there is one or computes the value by invoking given
 175      * {@code mappingFunction}, associates it and returns it.
 176      * <p>
 177      * Computation and association of the computed value is performed atomically
 178      * by the 1st thread that requests a particular association while holding a
 179      * lock associated with this ClassLoaderValue and given ClassLoader.
 180      * Nested calls from the {@code mappingFunction} to {@link #get},
 181      * {@link #putIfAbsent} or {@link #computeIfAbsent} for the same association
 182      * are not allowed and throw {@link IllegalStateException}. Nested call to
 183      * {@link #remove} for the same association is allowed but will always return
 184      * {@code false} regardless of passed-in comparison value. Nested calls for
 185      * other association(s) are allowed, but care should be taken to avoid
 186      * deadlocks. When two threads perform nested computations of the overlapping
 187      * set of associations they should always request them in the same order.
 188      *
 189      * @param cl              the ClassLoader for the associated value
 190      * @param mappingFunction the function to compute the value
 191      * @return the value associated with this ClassLoaderValue and given
 192      * ClassLoader.
 193      * @throws IllegalStateException if a direct or indirect invocation from
 194      *                               within given {@code mappingFunction} that
 195      *                               computes the value of a particular association
 196      *                               to {@link #get}, {@link #putIfAbsent} or
 197      *                               {@link #computeIfAbsent}
 198      *                               for the same association is attempted.
 199      */
 200     public V computeIfAbsent(ClassLoader cl,
 201                              BiFunction<
 202                                  ? super ClassLoader,
 203                                  ? super CLV,
 204                                  ? extends V
 205                                  > mappingFunction) throws IllegalStateException {
 206         ConcurrentHashMap<CLV, Object> map = map(cl);
 207         @SuppressWarnings("unchecked")
 208         CLV clv = (CLV) this;
 209         Memoizer<CLV, V> mv = null;
 210         while (true) {
 211             Object val = (mv == null) ? map.get(clv) : map.putIfAbsent(clv, mv);
 212             if (val == null) {
 213                 if (mv == null) {
 214                     // create Memoizer lazily when 1st needed and restart loop
 215                     mv = new Memoizer<>(cl, clv, mappingFunction);
 216                     continue;
 217                 }
 218                 // mv != null, therefore sv == null was a result of successful
 219                 // putIfAbsent
 220                 try {
 221                     // trigger Memoizer to compute the value
 222                     V v = mv.get();
 223                     // attempt to replace our Memoizer with the value
 224                     map.replace(clv, mv, v);
 225                     // return computed value
 226                     return v;
 227                 } catch (Throwable t) {
 228                     // our Memoizer has thrown, attempt to remove it
 229                     map.remove(clv, mv);
 230                     // propagate exception because it's from our Memoizer
 231                     throw t;
 232                 }
 233             } else {
 234                 try {
 235                     return extractValue(val);
 236                 } catch (Memoizer.RecursiveInvocationException e) {
 237                     // propagate recursive attempts to calculate the same
 238                     // value as being calculated at the moment
 239                     throw e;
 240                 } catch (Throwable t) {
 241                     // don't propagate exceptions thrown from foreign Memoizer -
 242                     // pretend that there was no entry and retry
 243                     // (foreign computeIfAbsent invocation will try to remove it anyway)
 244                 }
 245             }
 246             // TODO:
 247             // Thread.onSpinLoop(); // when available
 248         }
 249     }
 250 
 251     /**
 252      * Removes all values associated with given ClassLoader {@code cl} and
 253      * {@link #isEqualOrDescendantOf(AbstractClassLoaderValue) this or descendants}
 254      * of this ClassLoaderValue.
 255      * This is not an atomic operation. Other threads may see some associations
 256      * be already removed and others still present while this method is executing.
 257      * <p>
 258      * The sole intention of this method is to cleanup after a unit test that
 259      * tests ClassLoaderValue directly. It is not intended for use in
 260      * actual algorithms.
 261      *
 262      * @param cl the associated ClassLoader of the values to be removed
 263      */
 264     public void removeAll(ClassLoader cl) {
 265         ConcurrentHashMap<CLV, Object> map = map(cl);
 266         for (Iterator<CLV> i = map.keySet().iterator(); i.hasNext(); ) {
 267             if (i.next().isEqualOrDescendantOf(this)) {
 268                 i.remove();
 269             }
 270         }
 271     }
 272 
 273     private static final JavaLangAccess JLA = SharedSecrets.getJavaLangAccess();
 274 
 275     /**
 276      * @return a ConcurrentHashMap for given ClassLoader
 277      */
 278     @SuppressWarnings("unchecked")
 279     private static <CLV extends AbstractClassLoaderValue<CLV, ?>>
 280     ConcurrentHashMap<CLV, Object> map(ClassLoader cl) {
 281         return (ConcurrentHashMap<CLV, Object>)
 282             (cl == null ? BootLoader.getClassLoaderValueMap()
 283                         : JLA.createOrGetClassLoaderValueMap(cl));
 284     }
 285 
 286     /**
 287      * @return value extracted from the {@link Memoizer} if given
 288      * {@code memoizerOrValue} parameter is a {@code Memoizer} or
 289      * just return given parameter.
 290      */
 291     @SuppressWarnings("unchecked")
 292     private V extractValue(Object memoizerOrValue) {
 293         if (memoizerOrValue instanceof Memoizer) {
 294             return ((Memoizer<?, V>) memoizerOrValue).get();
 295         } else {
 296             return (V) memoizerOrValue;
 297         }
 298     }
 299 
 300     /**
 301      * A memoized supplier that invokes given {@code mappingFunction} just once
 302      * and remembers the result or thrown exception for subsequent calls.
 303      * If given mappingFunction returns null, it is converted to NullPointerException,
 304      * thrown from the Memoizer's {@link #get()} method and remembered.
 305      * If the Memoizer is invoked recursively from the given {@code mappingFunction},
 306      * {@link RecursiveInvocationException} is thrown, but it is not remembered.
 307      * The in-flight call to the {@link #get()} can still complete successfully if
 308      * such exception is handled by the mappingFunction.
 309      */
 310     private static final class Memoizer<CLV extends AbstractClassLoaderValue<CLV, V>, V>
 311         implements Supplier<V> {
 312 
 313         private final ClassLoader cl;
 314         private final CLV clv;
 315         private final BiFunction<? super ClassLoader, ? super CLV, ? extends V>
 316             mappingFunction;
 317 
 318         private volatile V v;
 319         private volatile Throwable t;
 320         private boolean inCall;
 321 
 322         Memoizer(ClassLoader cl,
 323                  CLV clv,
 324                  BiFunction<? super ClassLoader, ? super CLV, ? extends V>
 325                      mappingFunction
 326         ) {
 327             this.cl = cl;
 328             this.clv = clv;
 329             this.mappingFunction = mappingFunction;
 330         }
 331 
 332         @Override
 333         public V get() throws RecursiveInvocationException {
 334             V v = this.v;
 335             if (v != null) return v;
 336             Throwable t = this.t;
 337             if (t == null) {
 338                 synchronized (this) {
 339                     if ((v = this.v) == null && (t = this.t) == null) {
 340                         if (inCall) {
 341                             throw new RecursiveInvocationException();
 342                         }
 343                         inCall = true;
 344                         try {
 345                             this.v = v = Objects.requireNonNull(
 346                                 mappingFunction.apply(cl, clv));
 347                         } catch (Throwable x) {
 348                             this.t = t = x;
 349                         } finally {
 350                             inCall = false;
 351                         }
 352                     }
 353                 }
 354             }
 355             if (v != null) return v;
 356             if (t instanceof Error) {
 357                 throw (Error) t;
 358             } else if (t instanceof RuntimeException) {
 359                 throw (RuntimeException) t;
 360             } else {
 361                 throw new UndeclaredThrowableException(t);
 362             }
 363         }
 364 
 365         static class RecursiveInvocationException extends IllegalStateException {
 366             private static final long serialVersionUID = 1L;
 367 
 368             RecursiveInvocationException() {
 369                 super("Recursive call");
 370             }
 371         }
 372     }
 373 
 374     /**
 375      * sub-ClassLoaderValue is an inner class of {@link AbstractClassLoaderValue}
 376      * and also a subclass of it. It can therefore be instantiated as an inner
 377      * class of either an instance of root-{@link ClassLoaderValue} or another
 378      * instance of itself. This enables composing type-safe compound keys of
 379      * arbitrary length:
 380      * <pre>{@code
 381      * ClassLoaderValue<V> clv = new ClassLoaderValue<>();
 382      * ClassLoaderValue<V>.Sub<K1>.Sub<K2>.Sub<K3> clv_k123 =
 383      *     clv.sub(k1).sub(k2).sub(k3);
 384      * }</pre>
 385      * From which individual components are accessible in a type-safe way:
 386      * <pre>{@code
 387      * K1 k1 = clv_k123.parent().parent().key();
 388      * K2 k2 = clv_k123.parent().key();
 389      * K3 k3 = clv_k123.key();
 390      * }</pre>
 391      * This allows specifying non-capturing lambdas for the mapping function of
 392      * {@link #computeIfAbsent(ClassLoader, BiFunction)} operation that can
 393      * access individual key components from passed-in
 394      * sub-[sub-...]ClassLoaderValue instance in a type-safe way.
 395      *
 396      * @param <K> the type of {@link #key()} component contained in the
 397      *            sub-ClassLoaderValue.
 398      */
 399     public final class Sub<K> extends AbstractClassLoaderValue<Sub<K>, V> {
 400 
 401         private final K key;
 402 
 403         Sub(K key) {
 404             this.key = key;
 405         }
 406 
 407         /**
 408          * @return the parent ClassLoaderValue this sub-ClassLoaderValue
 409          * has been {@link #sub(Object) derived} from.
 410          */
 411         public AbstractClassLoaderValue<CLV, V> parent() {
 412             return AbstractClassLoaderValue.this;
 413         }
 414 
 415         /**
 416          * @return the key component of this sub-ClassLoaderValue.
 417          */
 418         @Override
 419         public K key() {
 420             return key;
 421         }
 422 
 423         /**
 424          * sub-ClassLoaderValue is a descendant of given {@code clv} if it is
 425          * either equal to it or if its {@link #parent() parent} is a
 426          * descendant of given {@code clv}.
 427          */
 428         @Override
 429         public boolean isEqualOrDescendantOf(AbstractClassLoaderValue<?, V> clv) {
 430             return equals(Objects.requireNonNull(clv)) ||
 431                    parent().isEqualOrDescendantOf(clv);
 432         }
 433 
 434         @Override
 435         public boolean equals(Object o) {
 436             if (this == o) return true;
 437             if (!(o instanceof Sub)) return false;
 438             @SuppressWarnings("unchecked")
 439             Sub<?> that = (Sub<?>) o;
 440             return this.parent().equals(that.parent()) &&
 441                    Objects.equals(this.key, that.key);
 442         }
 443 
 444         @Override
 445         public int hashCode() {
 446             return 31 * parent().hashCode() +
 447                    Objects.hashCode(key);
 448         }
 449     }
 450 }