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 }