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 }
--- EOF ---