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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.lang;
27
28 import jdk.internal.misc.Unsafe;
29 import jdk.internal.vm.annotation.ForceInline;
30 import jdk.internal.vm.annotation.Stable;
31
32 import java.lang.ref.PhantomReference;
33 import java.lang.ref.ReferenceQueue;
34 import java.lang.ref.WeakReference;
35 import java.util.concurrent.ConcurrentHashMap;
36 import java.util.concurrent.atomic.AtomicBoolean;
37 import java.util.concurrent.atomic.AtomicInteger;
38 import java.util.concurrent.atomic.AtomicReference;
39
40 /**
41 * Lazily associate a computed value with (potentially) every type.
42 * For example, if a dynamic language needs to construct a message dispatch
43 * table for each class encountered at a message send call site,
44 * it can use a {@code ClassValue} to cache information needed to
45 * perform the message send quickly, for each class encountered.
46 * @author John Rose, JSR 292 EG
47 * @since 1.7
48 */
49 public abstract class ClassValue<T> {
50 /**
51 * Sole constructor. (For invocation by subclass constructors, typically
52 * implicit.)
53 */
54 protected ClassValue() {
55 }
56
57 /**
58 * Computes the given class's derived value for this {@code ClassValue}.
59 * <p>
60 * This method will be invoked within the first thread that accesses
61 * the value with the {@link #get get} method.
62 * <p>
63 * Normally, this method is invoked at most once per class,
64 * but it may be invoked again if there has been a call to
65 * {@link #remove remove}.
66 * <p>
67 * If this method throws an exception, the corresponding call to {@code get}
68 * will terminate abnormally with that exception, and no class value will be recorded.
69 *
70 * @param type the type whose class value must be computed
71 * @return the newly computed value associated with this {@code ClassValue}, for the given class or interface
72 * @see #get
73 * @see #remove
74 */
75 protected abstract T computeValue(Class<?> type);
76
77 /**
78 * Returns the value for the given class.
79 * If no value has yet been computed, it is obtained by
80 * an invocation of the {@link #computeValue computeValue} method.
81 * <p>
82 * The actual installation of the value on the class
83 * is performed atomically.
84 * At that point, if several racing threads have
85 * computed values, one is chosen, and returned to
86 * all the racing threads.
87 * <p>
88 * The {@code type} parameter is typically a class, but it may be any type,
89 * such as an interface, a primitive type (like {@code int.class}), or {@code void.class}.
90 * <p>
91 * In the absence of {@code remove} calls, a class value has a simple
92 * state diagram: uninitialized and initialized.
93 * When {@code remove} calls are made,
94 * the rules for value observation are more complex.
95 * See the documentation for {@link #remove remove} for more information.
96 *
97 * @param type the type whose class value must be computed or retrieved
98 * @return the current value associated with this {@code ClassValue}, for the given class or interface
99 * @throws NullPointerException if the argument is null
100 * @see #remove
101 * @see #computeValue
102 */
103 @SuppressWarnings("unchecked")
104 @ForceInline
105 public T get(Class<?> type) {
106 ClassValueMap map = type.classValueMap;
107 Object value;
108 if (map != null) {
109 value = map.get(key);
110 if (value != null && !(value instanceof Removed)) {
111 return (value == NULL_MASK) ? null : (T) value;
112 }
113 } else {
114 value = null;
115 }
116 return getSlow(type, value);
117 }
118 // ...the rest in separate method
119 @SuppressWarnings("unchecked")
120 private T getSlow(Class<?> type, Object oldValue) {
121 ClassValueMap.expungeStaleEntries();
122 ClassValueMap map = getMap(type);
123 while (true) {
124 // assert oldValue == null || oldValue instanceof Removed;
125 T newValue = computeValue(type);
126 if (oldValue == null) {
127 oldValue = map.putIfAbsent(key, (newValue == null) ? NULL_MASK : newValue);
128 if (oldValue == null) {
129 return newValue;
130 } else {
131 // another thread has beaten us
132 if (!(oldValue instanceof Removed)) {
133 return (oldValue == NULL_MASK) ? null : (T) oldValue;
134 }
135 }
136 } else {
137 // assert oldValue instanceof Removed;
138 if (map.replace(key, oldValue, (newValue == null) ? NULL_MASK : newValue)) {
139 // this only succeeds if oldValue is still the same instance of
140 // Removed as observed before computeValue invocation
141 return newValue;
142 } else {
143 // another thread has beaten us
144 oldValue = map.get(key);
145 if (oldValue != null && !(oldValue instanceof Removed)) {
146 return (oldValue == NULL_MASK) ? null : (T) oldValue;
147 }
148 }
149 }
150 // retry compute since we observed another version of Removed
151 // as was current before compute which means that there was
152 // at least one value present in between time which means
153 // that the result of our compute is stale.
154 }
155 }
156
157 /**
158 * Removes the associated value for the given class.
159 * If this value is subsequently {@linkplain #get read} for the same class,
160 * its value will be reinitialized by invoking its {@link #computeValue computeValue} method.
161 * This may result in an additional invocation of the
162 * {@code computeValue} method for the given class.
163 * <p>
164 * In order to explain the interaction between {@code get} and {@code remove} calls,
165 * we must model the state transitions of a class value to take into account
166 * the alternation between uninitialized and initialized states.
167 * To do this, number these states sequentially from zero, and note that
168 * uninitialized (or removed) states are numbered with even numbers,
169 * while initialized (or re-initialized) states have odd numbers.
170 * <p>
171 * When a thread {@code T} removes a class value in state {@code 2N},
172 * nothing happens, since the class value is already uninitialized.
173 * Otherwise, the state is advanced atomically to {@code 2N+1}.
174 * <p>
175 * When a thread {@code T} queries a class value in state {@code 2N},
176 * the thread first attempts to initialize the class value to state {@code 2N+1}
177 * by invoking {@code computeValue} and installing the resulting value.
178 * <p>
179 * When {@code T} attempts to install the newly computed value,
180 * if the state is still at {@code 2N}, the class value will be initialized
181 * with the computed value, advancing it to state {@code 2N+1}.
182 * <p>
183 * Otherwise, whether the new state is even or odd,
184 * {@code T} will discard the newly computed value
185 * and retry the {@code get} operation.
186 * <p>
187 * Discarding and retrying is an important proviso,
188 * since otherwise {@code T} could potentially install
189 * a disastrously stale value. For example:
190 * <ul>
191 * <li>{@code T} calls {@code CV.get(C)} and sees state {@code 2N}
192 * <li>{@code T} quickly computes a time-dependent value {@code V0} and gets ready to install it
193 * <li>{@code T} is hit by an unlucky paging or scheduling event, and goes to sleep for a long time
194 * <li>...meanwhile, {@code T2} also calls {@code CV.get(C)} and sees state {@code 2N}
195 * <li>{@code T2} quickly computes a similar time-dependent value {@code V1} and installs it on {@code CV.get(C)}
196 * <li>{@code T2} (or a third thread) then calls {@code CV.remove(C)}, undoing {@code T2}'s work
197 * <li> the previous actions of {@code T2} are repeated several times
198 * <li> also, the relevant computed values change over time: {@code V1}, {@code V2}, ...
199 * <li>...meanwhile, {@code T} wakes up and attempts to install {@code V0}; <em>this must fail</em>
200 * </ul>
201 * We can assume in the above scenario that {@code CV.computeValue} uses locks to properly
202 * observe the time-dependent states as it computes {@code V1}, etc.
203 * This does not remove the threat of a stale value, since there is a window of time
204 * between the return of {@code computeValue} in {@code T} and the installation
205 * of the new value. No user synchronization is possible during this time.
206 *
207 * @param type the type whose class value must be removed
208 * @throws NullPointerException if the argument is null
209 */
210 public void remove(Class<?> type) {
211 ClassValueMap.expungeStaleEntries();
212 ClassValueMap map = type.classValueMap;
213 if (map != null) {
214 Object value, removed = null;
215 do {
216 value = map.get(key);
217 if (value == null || value instanceof Removed) {
218 // non-existence is treated as Removed(V0)
219 // invoking remove() when state is Removed(VN) does not
220 // change it to Removed(VN+1)
221 break;
222 }
223 if (removed == null) {
224 removed = new Removed();
225 }
226 } while (!map.replace(key, value, removed));
227 }
228 }
229
230 // Possible functionality for JSR 292 MR 1
231 /*public*/ void put(Class<?> type, T value) {
232 ClassValueMap.expungeStaleEntries();
233 ClassValueMap map = getMap(type);
234 map.put(key, (value == null) ? NULL_MASK : value);
235 }
236
237 /// --------
238 /// Implementation...
239 /// --------
240
241 /**
242 * The key used in ClassValueMap for this ClassValue.
243 * Since ClassValue(s) are usually assigned to static final fields, it makes
244 * sense to promote the key to constant too.
245 */
246 @Stable
247 private final Key key = new Key(this);
248
249 /**
250 * Key of a ClassValue and a tracker of the ClassValue at the same time.
251 */
252 private static final class Key extends PhantomReference<ClassValue<?>> {
253
254 /** Value stream for hash. See similar structure in ThreadLocal. */
255 private static final AtomicInteger nextHash = new AtomicInteger();
256
257 /** Good for power-of-two tables. See similar structure in ThreadLocal. */
258 private static final int HASH_INCREMENT = 0x61c88647;
259
260 /** Single global queue for all stale keys to be enqueued */
261 static final ReferenceQueue<ClassValue<?>> queue = new ReferenceQueue<>();
262
263 @Stable
264 private final int hash;
265
266 Key(ClassValue<?> cv) {
267 super(cv, queue);
268 int h = nextHash.getAndAdd(HASH_INCREMENT);
269 // undo the effect of CHM.spread()
270 this.hash = h ^ (h >>> 16);
271 }
272
273 @Override
274 public int hashCode() {
275 return hash;
276 }
277
278 // equals is identity
279 }
280
281 /** A masked null value. */
282 private static final Object NULL_MASK = new Object();
283
284 /** Removed value(s) */
285 private static final class Removed {}
286
287 /** Return the backing map associated with this type, possibly constructing it. */
288 private static ClassValueMap getMap(Class<?> type) {
289 ClassValueMap map = type.classValueMap;
290 return (map != null) ? map : initializeMap(type);
291 }
292
293 private static ClassValueMap initializeMap(Class<?> type) {
294 ClassValueMap map = ClassValueMap.create();
295 return U.compareAndSwapObject(type, CLASS_VALUE_MAP_OFFSET, null, map)
296 ? map
297 : (ClassValueMap) U.getObjectVolatile(type, CLASS_VALUE_MAP_OFFSET);
298 }
299
300 /** A backing map for all ClassValues in a particular Class.
301 */
302 static final class ClassValueMap extends ConcurrentHashMap<Key, Object> {
303 // eh, needed to silent the gods
304 private static final long serialVersionUID = 1L;
305
306 // a node in a linked list of WeakReference(s) to ClassValueMap(s)
307 private static final class WeakNode extends WeakReference<ClassValueMap> {
308 WeakNode next;
309 WeakNode(ClassValueMap map) { super(map); }
310 }
311
312 // the head of the linked list of WeakReference(s) to ClassValueMap(s)
313 private static final AtomicReference<WeakNode> mapsList = new AtomicReference<>();
314
315 // the lock used to guard expunging logic
316 private static final AtomicBoolean expungeInProgress = new AtomicBoolean();
317
318 private ClassValueMap() {
319 super(1);
320 }
321
322 static ClassValueMap create() {
323 ClassValueMap map = new ClassValueMap();
324 WeakNode node = new WeakNode(map);
325 // register the weakly referenced map into the list
326 do {
327 node.next = mapsList.get();
328 } while (!mapsList.compareAndSet(node.next, node));
329 return map;
330 }
331
332 static void expungeStaleEntries() {
333 // make sure only one thread at a time is expunging stale entries;
334 // this is important for correctness so that no stale enqueued key
335 // is missed from being removed from any map that might possibly
336 // hold it.
337 if (!expungeInProgress.get() &&
338 expungeInProgress.compareAndSet(false, true)) try {
339 expungeStaleEntriesImpl();
340 } finally {
341 expungeInProgress.set(false);
342 }
343 }
344
345 private static void expungeStaleEntriesImpl() {
346 // start with an empty private list
347 WeakNode first = null, last = null;
348 // iterate Key(s) of GCed ClassValue(s)
349 Key key;
350 while ((key = (Key) Key.queue.poll()) != null) {
351 // steal any (newly) registered map(s) from the shared 'mapsList'
352 // as they might already be holding the stale 'key' that has just
353 // been removed from the queue. The following guarantees that
354 // no (stale-key, live-map) combination is missed:
355 // - a map is 1st registered into the mapsList and then non-stale
356 // keys are inserted into it
357 // - a non-stale key becomes stale when a ClassValue that it
358 // phantomly references is GCed; the key is then enqueued
359 // - a stale key is 1st removed from the queue and then mapsList
360 // is checked for any (newly) registered map(s)
361 if (mapsList.get() != null) {
362 WeakNode stolen = mapsList.getAndSet(null);
363 // add them to the end of current private list
364 if (last != null) {
365 last.next = stolen;
366 } else {
367 // assert first == null;
368 first = stolen;
369 }
370 }
371 // iterate the accumulated private list of maps
372 last = null;
373 for (WeakNode node = first; node != null; ) {
374 ClassValueMap map = node.get();
375 if (map == null) {
376 // Class and its ClassValueMap have already been GCed
377 // -> remove the node from the list
378 if (last == null) {
379 first = node = node.next;
380 } else {
381 last.next = node = node.next;
382 }
383 } else {
384 // ClassValueMap is still alive
385 // -> attempt to remove the key from it
386 map.remove(key);
387 // navigate to next in list
388 last = node;
389 node = node.next;
390 }
391 }
392 // at this time, 'last' points to the last WeakNode in the private
393 // list (if any) and the following always holds:
394 // assert (first == null) == (last == null);
395 }
396 // re-insert the stolen and expunged list of map(s) back into shared
397 // mapsList
398 if (last != null) {
399 do {
400 last.next = mapsList.get();
401 } while (!mapsList.compareAndSet(last.next, first));
402 }
403 }
404 }
405
406 /** We need to cas */
407 private static final Unsafe U = Unsafe.getUnsafe();
408 private static final long CLASS_VALUE_MAP_OFFSET;
409
410 static {
411 try {
412 CLASS_VALUE_MAP_OFFSET = U.objectFieldOffset(
413 Class.class.getDeclaredField("classValueMap"));
414 } catch (Exception e) {
415 throw new Error(e);
416 }
417 }
418 }