1 /*

     2  * Copyright (c) 2010, 2011, 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.dyn;

    27 

    28 import java.util.WeakHashMap;

    29 import java.util.concurrent.atomic.AtomicInteger;

    30 import java.util.concurrent.atomic.AtomicReference;

    31 import java.lang.reflect.UndeclaredThrowableException;

    32 

    33 /**

    34  * Lazily associate a computed value with (potentially) every type.

    35  * For example, if a dynamic language needs to construct a message dispatch

    36  * table for each class encountered at a message send call site,

    37  * it can use a {@code ClassValue} to cache information needed to

    38  * perform the message send quickly, for each class encountered.

    39  * @author John Rose, JSR 292 EG

    40  */

    41 public abstract class ClassValue<T> {

    42     /**

    43      * Compute the given class's derived value for this {@code ClassValue}.

    44      * <p>

    45      * This method will be invoked within the first thread that accesses

    46      * the value with the {@link #get get} method.

    47      * <p>

    48      * Normally, this method is invoked at most once per class,

    49      * but it may be invoked again if there has been a call to

    50      * {@link #remove remove}.

    51      * <p>

    52      * If this method throws an exception, the corresponding call to {@code get}

    53      * will terminate abnormally with that exception, and no class value will be recorded.

    54      *

    55      * @param type the type whose class value must be computed

    56      * @return the newly computed value associated with this {@code ClassValue}, for the given class or interface

    57      * @see #get

    58      * @see #remove

    59      */

    60     protected abstract T computeValue(Class<?> type);

    61 

    62     /**

    63      * Returns the value for the given class.

    64      * If no value has yet been computed, it is obtained by

    65      * an invocation of the {@link #computeValue computeValue} method.

    66      * <p>

    67      * The actual installation of the value on the class

    68      * is performed atomically.

    69      * At that point, if several racing threads have

    70      * computed values, one is chosen, and returned to

    71      * all the racing threads.

    72      * <p>

    73      * The {@code type} parameter is typically a class, but it may be any type,

    74      * such as an interface, a primitive type (like {@code int.class}), or {@code void.class}.

    75      * <p>

    76      * In the absence of {@code remove} calls, a class value has a simple

    77      * state diagram:  uninitialized and initialized.

    78      * When {@code remove} calls are made,

    79      * the rules for value observation are more complex.

    80      * See the documentation for {@link #remove remove} for more information.

    81      *

    82      * @param type the type whose class value must be computed or retrieved

    83      * @return the current value associated with this {@code ClassValue}, for the given class or interface

    84      * @throws NullPointerException if the argument is null

    85      * @see #remove

    86      * @see #computeValue

    87      */

    88     public T get(Class<?> type) {

    89         ClassValueMap map = getMap(type);

    90         if (map != null) {

    91             Object x = map.get(this);

    92             if (x != null) {

    93                 return (T) map.unmaskNull(x);

    94             }

    95         }

    96         return setComputedValue(type);

    97     }

    98 

    99     /**

   100      * Removes the associated value for the given class.

   101      * If this value is subsequently {@linkplain #get read} for the same class,

   102      * its value will be reinitialized by invoking its {@link #computeValue computeValue} method.

   103      * This may result in an additional invocation of the

   104      * {@code computeValue computeValue} method for the given class.

   105      * <p>

   106      * In order to explain the interaction between {@code get} and {@code remove} calls,

   107      * we must model the state transitions of a class value to take into account

   108      * the alternation between uninitialized and initialized states.

   109      * To do this, number these states sequentially from zero, and note that

   110      * uninitialized (or removed) states are numbered with even numbers,

   111      * while initialized (or re-initialized) states have odd numbers.

   112      * <p>

   113      * When a thread {@code T} removes a class value in state {@code 2N},

   114      * nothing happens, since the class value is already uninitialized.

   115      * Otherwise, the state is advanced atomically to {@code 2N+1}.

   116      * <p>

   117      * When a thread {@code T} queries a class value in state {@code 2N},

   118      * the thread first attempts to initialize the class value to state {@code 2N+1}

   119      * by invoking {@code computeValue} and installing the resulting value.

   120      * <p>

   121      * When {@code T} attempts to install the newly computed value,

   122      * if the state is still at {@code 2N}, the class value will be initialized

   123      * with the computed value, advancing it to state {@code 2N+1}.

   124      * <p>

   125      * Otherwise, whether the new state is even or odd,

   126      * {@code T} will discard the newly computed value

   127      * and retry the {@code get} operation.

   128      * <p>

   129      * Discarding and retrying is an important proviso,

   130      * since otherwise {@code T} could potentially install

   131      * a disastrously stale value.  For example:

   132      * <ul>

   133      * <li>{@code T} calls {@code CV.get(C)} and sees state {@code 2N}

   134      * <li>{@code T} quickly computes a time-dependent value {@code V0} and gets ready to install it

   135      * <li>{@code T} is hit by an unlucky paging or scheduling event, and goes to sleep for a long time

   136      * <li>...meanwhile, {@code T2} also calls {@code CV.get(C)} and sees state {@code 2N}

   137      * <li>{@code T2} quickly computes a similar time-dependent value {@code V1} and installs it on {@code CV.get(C)}

   138      * <li>{@code T2} (or a third thread) then calls {@code CV.remove(C)}, undoing {@code T2}'s work

   139      * <li> the previous actions of {@code T2} are repeated several times

   140      * <li> also, the relevant computed values change over time: {@code V1}, {@code V2}, ...

   141      * <li>...meanwhile, {@code T} wakes up and attempts to install {@code V0}; <em>this must fail</em>

   142      * </ul>

   143      * We can assume in the above scenario that {@code CV.computeValue} uses locks to properly

   144      * observe the time-dependent states as it computes {@code V1}, etc.

   145      * This does not remove the threat of a stale value, since there is a window of time

   146      * between the return of {@code computeValue} in {@code T} and the installation

   147      * of the the new value.  No user synchronization is possible during this time.

   148      *

   149      * @param type the type whose class value must be removed

   150      * @throws NullPointerException if the argument is null

   151      */

   152     public void remove(Class<?> type) {

   153         ClassValueMap map = getMap(type);

   154         if (map != null) {

   155             synchronized (map) {

   156                 map.remove(this);

   157             }

   158         }

   159     }

   160 

   161     /// Implementation...

   162 

   163     // The hash code for this type is based on the identity of the object,

   164     // and is well-dispersed for power-of-two tables.

   165     /** @deprecated This override, which is implementation-specific, will be removed for PFD. */

   166     public final int hashCode() { return hashCode; }

   167     private final int hashCode = HASH_CODES.getAndAdd(0x61c88647);

   168     private static final AtomicInteger HASH_CODES = new AtomicInteger();

   169 

   170     private static final AtomicInteger STORE_BARRIER = new AtomicInteger();

   171 

   172     /** Slow path for {@link #get}. */

   173     private T setComputedValue(Class<?> type) {

   174         ClassValueMap map = getMap(type);

   175         if (map == null) {

   176             map = initializeMap(type);

   177         }

   178         T value = computeValue(type);

   179         STORE_BARRIER.lazySet(0);

   180         // All stores pending from computeValue are completed.

   181         synchronized (map) {

   182             // Warm up the table with a null entry.

   183             map.preInitializeEntry(this);

   184         }

   185         STORE_BARRIER.lazySet(0);

   186         // All stores pending from table expansion are completed.

   187         synchronized (map) {

   188             value = (T) map.initializeEntry(this, value);

   189             // One might fear a possible race condition here

   190             // if the code for map.put has flushed the write

   191             // to map.table[*] before the writes to the Map.Entry

   192             // are done.  This is not possible, since we have

   193             // warmed up the table with an empty entry.

   194         }

   195         return value;

   196     }

   197 

   198     // Replace this map by a per-class slot.

   199     private static final WeakHashMap<Class<?>, ClassValueMap> ROOT

   200         = new WeakHashMap<Class<?>, ClassValueMap>();

   201 

   202     private static ClassValueMap getMap(Class<?> type) {

   203         return ROOT.get(type);

   204     }

   205 

   206     private static ClassValueMap initializeMap(Class<?> type) {

   207         synchronized (ClassValue.class) {

   208             ClassValueMap map = ROOT.get(type);

   209             if (map == null)

   210                 ROOT.put(type, map = new ClassValueMap());

   211             return map;

   212         }

   213     }

   214 

   215     static class ClassValueMap extends WeakHashMap<ClassValue, Object> {

   216         /** Make sure this table contains an Entry for the given key, even if it is empty. */

   217         void preInitializeEntry(ClassValue key) {

   218             if (!this.containsKey(key))

   219                 this.put(key, null);

   220         }

   221         /** Make sure this table contains a non-empty Entry for the given key. */

   222         Object initializeEntry(ClassValue key, Object value) {

   223             Object prior = this.get(key);

   224             if (prior != null) {

   225                 return unmaskNull(prior);

   226             }

   227             this.put(key, maskNull(value));

   228             return value;

   229         }

   230 

   231         Object maskNull(Object x) {

   232             return x == null ? this : x;

   233         }

   234         Object unmaskNull(Object x) {

   235             return x == this ? null : x;

   236         }

   237     }

   238 }