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