1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     3  *

     4  * This code is free software; you can redistribute it and/or modify it

     5  * under the terms of the GNU General Public License version 2 only, as

     6  * published by the Free Software Foundation.  Oracle designates this

     7  * particular file as subject to the "Classpath" exception as provided

     8  * by Oracle in the LICENSE file that accompanied this code.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    21  * or visit www.oracle.com if you need additional information or have any

    22  * questions.

    23  */

    24 

    25 /*

    26  * This file is available under and governed by the GNU General Public

    27  * License version 2 only, as published by the Free Software Foundation.

    28  * However, the following notice accompanied the original version of this

    29  * file:

    30  *

    31  * Written by Doug Lea with assistance from members of JCP JSR-166

    32  * Expert Group and released to the public domain, as explained at

    33  * http://creativecommons.org/publicdomain/zero/1.0/

    34  */

    35 

    36 package java.util.concurrent.atomic;

    37 import java.util.function.UnaryOperator;

    38 import java.util.function.BinaryOperator;

    39 import sun.misc.Unsafe;

    40 import java.lang.reflect.Field;

    41 import java.lang.reflect.Modifier;

    42 import java.security.AccessController;

    43 import java.security.PrivilegedExceptionAction;

    44 import java.security.PrivilegedActionException;

    45 import sun.reflect.CallerSensitive;

    46 import sun.reflect.Reflection;

    47 

    48 /**

    49  * A reflection-based utility that enables atomic updates to

    50  * designated {@code volatile} reference fields of designated

    51  * classes.  This class is designed for use in atomic data structures

    52  * in which several reference fields of the same node are

    53  * independently subject to atomic updates. For example, a tree node

    54  * might be declared as

    55  *

    56  *  <pre> {@code

    57  * class Node {

    58  *   private volatile Node left, right;

    59  *

    60  *   private static final AtomicReferenceFieldUpdater<Node, Node> leftUpdater =

    61  *     AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "left");

    62  *   private static AtomicReferenceFieldUpdater<Node, Node> rightUpdater =

    63  *     AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "right");

    64  *

    65  *   Node getLeft() { return left;  }

    66  *   boolean compareAndSetLeft(Node expect, Node update) {

    67  *     return leftUpdater.compareAndSet(this, expect, update);

    68  *   }

    69  *   // ... and so on

    70  * }}</pre>

    71  *

    72  * <p>Note that the guarantees of the {@code compareAndSet}

    73  * method in this class are weaker than in other atomic classes.

    74  * Because this class cannot ensure that all uses of the field

    75  * are appropriate for purposes of atomic access, it can

    76  * guarantee atomicity only with respect to other invocations of

    77  * {@code compareAndSet} and {@code set} on the same updater.

    78  *

    79  * @since 1.5

    80  * @author Doug Lea

    81  * @param <T> The type of the object holding the updatable field

    82  * @param <V> The type of the field

    83  */

    84 public abstract class AtomicReferenceFieldUpdater<T,V> {

    85 

    86     /**

    87      * Creates and returns an updater for objects with the given field.

    88      * The Class arguments are needed to check that reflective types and

    89      * generic types match.

    90      *

    91      * @param tclass the class of the objects holding the field

    92      * @param vclass the class of the field

    93      * @param fieldName the name of the field to be updated

    94      * @param <U> the type of instances of tclass

    95      * @param <W> the type of instances of vclass

    96      * @return the updater

    97      * @throws ClassCastException if the field is of the wrong type

    98      * @throws IllegalArgumentException if the field is not volatile

    99      * @throws RuntimeException with a nested reflection-based

   100      * exception if the class does not hold field or is the wrong type,

   101      * or the field is inaccessible to the caller according to Java language

   102      * access control

   103      */

   104     @CallerSensitive

   105     public static <U,W> AtomicReferenceFieldUpdater<U,W> newUpdater(Class<U> tclass,

   106                                                                     Class<W> vclass,

   107                                                                     String fieldName) {

   108         return new AtomicReferenceFieldUpdaterImpl<U,W>

   109             (tclass, vclass, fieldName, Reflection.getCallerClass());

   110     }

   111 

   112     /**

   113      * Protected do-nothing constructor for use by subclasses.

   114      */

   115     protected AtomicReferenceFieldUpdater() {

   116     }

   117 

   118     /**

   119      * Atomically sets the field of the given object managed by this updater

   120      * to the given updated value if the current value {@code ==} the

   121      * expected value. This method is guaranteed to be atomic with respect to

   122      * other calls to {@code compareAndSet} and {@code set}, but not

   123      * necessarily with respect to other changes in the field.

   124      *

   125      * @param obj An object whose field to conditionally set

   126      * @param expect the expected value

   127      * @param update the new value

   128      * @return {@code true} if successful

   129      */

   130     public abstract boolean compareAndSet(T obj, V expect, V update);

   131 

   132     /**

   133      * Atomically sets the field of the given object managed by this updater

   134      * to the given updated value if the current value {@code ==} the

   135      * expected value. This method is guaranteed to be atomic with respect to

   136      * other calls to {@code compareAndSet} and {@code set}, but not

   137      * necessarily with respect to other changes in the field.

   138      *

   139      * <p><a href="package-summary.html#weakCompareAndSet">May fail

   140      * spuriously and does not provide ordering guarantees</a>, so is

   141      * only rarely an appropriate alternative to {@code compareAndSet}.

   142      *

   143      * @param obj An object whose field to conditionally set

   144      * @param expect the expected value

   145      * @param update the new value

   146      * @return {@code true} if successful

   147      */

   148     public abstract boolean weakCompareAndSet(T obj, V expect, V update);

   149 

   150     /**

   151      * Sets the field of the given object managed by this updater to the

   152      * given updated value. This operation is guaranteed to act as a volatile

   153      * store with respect to subsequent invocations of {@code compareAndSet}.

   154      *

   155      * @param obj An object whose field to set

   156      * @param newValue the new value

   157      */

   158     public abstract void set(T obj, V newValue);

   159 

   160     /**

   161      * Eventually sets the field of the given object managed by this

   162      * updater to the given updated value.

   163      *

   164      * @param obj An object whose field to set

   165      * @param newValue the new value

   166      * @since 1.6

   167      */

   168     public abstract void lazySet(T obj, V newValue);

   169 

   170     /**

   171      * Gets the current value held in the field of the given object managed

   172      * by this updater.

   173      *

   174      * @param obj An object whose field to get

   175      * @return the current value

   176      */

   177     public abstract V get(T obj);

   178 

   179     /**

   180      * Atomically sets the field of the given object managed by this updater

   181      * to the given value and returns the old value.

   182      *

   183      * @param obj An object whose field to get and set

   184      * @param newValue the new value

   185      * @return the previous value

   186      */

   187     public V getAndSet(T obj, V newValue) {

   188         V prev;

   189         do {

   190             prev = get(obj);

   191         } while (!compareAndSet(obj, prev, newValue));

   192         return prev;

   193     }

   194 

   195     /**

   196      * Atomically updates the field of the given object managed by this updater

   197      * with the results of applying the given function, returning the previous

   198      * value. The function should be side-effect-free, since it may be

   199      * re-applied when attempted updates fail due to contention among threads.

   200      *

   201      * @param obj An object whose field to get and set

   202      * @param updateFunction a side-effect-free function

   203      * @return the previous value

   204      * @since 1.8

   205      */

   206     public final V getAndUpdate(T obj, UnaryOperator<V> updateFunction) {

   207         V prev, next;

   208         do {

   209             prev = get(obj);

   210             next = updateFunction.apply(prev);

   211         } while (!compareAndSet(obj, prev, next));

   212         return prev;

   213     }

   214 

   215     /**

   216      * Atomically updates the field of the given object managed by this updater

   217      * with the results of applying the given function, returning the updated

   218      * value. The function should be side-effect-free, since it may be

   219      * re-applied when attempted updates fail due to contention among threads.

   220      *

   221      * @param obj An object whose field to get and set

   222      * @param updateFunction a side-effect-free function

   223      * @return the updated value

   224      * @since 1.8

   225      */

   226     public final V updateAndGet(T obj, UnaryOperator<V> updateFunction) {

   227         V prev, next;

   228         do {

   229             prev = get(obj);

   230             next = updateFunction.apply(prev);

   231         } while (!compareAndSet(obj, prev, next));

   232         return next;

   233     }

   234 

   235     /**

   236      * Atomically updates the field of the given object managed by this

   237      * updater with the results of applying the given function to the

   238      * current and given values, returning the previous value. The

   239      * function should be side-effect-free, since it may be re-applied

   240      * when attempted updates fail due to contention among threads.  The

   241      * function is applied with the current value as its first argument,

   242      * and the given update as the second argument.

   243      *

   244      * @param obj An object whose field to get and set

   245      * @param x the update value

   246      * @param accumulatorFunction a side-effect-free function of two arguments

   247      * @return the previous value

   248      * @since 1.8

   249      */

   250     public final V getAndAccumulate(T obj, V x,

   251                                     BinaryOperator<V> accumulatorFunction) {

   252         V prev, next;

   253         do {

   254             prev = get(obj);

   255             next = accumulatorFunction.apply(prev, x);

   256         } while (!compareAndSet(obj, prev, next));

   257         return prev;

   258     }

   259 

   260     /**

   261      * Atomically updates the field of the given object managed by this

   262      * updater with the results of applying the given function to the

   263      * current and given values, returning the updated value. The

   264      * function should be side-effect-free, since it may be re-applied

   265      * when attempted updates fail due to contention among threads.  The

   266      * function is applied with the current value as its first argument,

   267      * and the given update as the second argument.

   268      *

   269      * @param obj An object whose field to get and set

   270      * @param x the update value

   271      * @param accumulatorFunction a side-effect-free function of two arguments

   272      * @return the updated value

   273      * @since 1.8

   274      */

   275     public final V accumulateAndGet(T obj, V x,

   276                                     BinaryOperator<V> accumulatorFunction) {

   277         V prev, next;

   278         do {

   279             prev = get(obj);

   280             next = accumulatorFunction.apply(prev, x);

   281         } while (!compareAndSet(obj, prev, next));

   282         return next;

   283     }

   284 

   285     private static final class AtomicReferenceFieldUpdaterImpl<T,V>

   286         extends AtomicReferenceFieldUpdater<T,V> {

   287         private static final Unsafe unsafe = Unsafe.getUnsafe();

   288         private final long offset;

   289         private final Class<T> tclass;

   290         private final Class<V> vclass;

   291         private final Class<?> cclass;

   292 

   293         /*

   294          * Internal type checks within all update methods contain

   295          * internal inlined optimizations checking for the common

   296          * cases where the class is final (in which case a simple

   297          * getClass comparison suffices) or is of type Object (in

   298          * which case no check is needed because all objects are

   299          * instances of Object). The Object case is handled simply by

   300          * setting vclass to null in constructor.  The targetCheck and

   301          * updateCheck methods are invoked when these faster

   302          * screenings fail.

   303          */

   304 

   305         AtomicReferenceFieldUpdaterImpl(final Class<T> tclass,

   306                                         final Class<V> vclass,

   307                                         final String fieldName,

   308                                         final Class<?> caller) {

   309             final Field field;

   310             final Class<?> fieldClass;

   311             final int modifiers;

   312             try {

   313                 field = AccessController.doPrivileged(

   314                     new PrivilegedExceptionAction<Field>() {

   315                         public Field run() throws NoSuchFieldException {

   316                             return tclass.getDeclaredField(fieldName);

   317                         }

   318                     });

   319                 modifiers = field.getModifiers();

   320                 sun.reflect.misc.ReflectUtil.ensureMemberAccess(

   321                     caller, tclass, null, modifiers);

   322                 ClassLoader cl = tclass.getClassLoader();

   323                 ClassLoader ccl = caller.getClassLoader();

   324                 if ((ccl != null) && (ccl != cl) &&

   325                     ((cl == null) || !isAncestor(cl, ccl))) {

   326                   sun.reflect.misc.ReflectUtil.checkPackageAccess(tclass);

   327                 }

   328                 fieldClass = field.getType();

   329             } catch (PrivilegedActionException pae) {

   330                 throw new RuntimeException(pae.getException());

   331             } catch (Exception ex) {

   332                 throw new RuntimeException(ex);

   333             }

   334 

   335             if (vclass != fieldClass)

   336                 throw new ClassCastException();

   337             if (vclass.isPrimitive())

   338                 throw new IllegalArgumentException("Must be reference type");

   339 

   340             if (!Modifier.isVolatile(modifiers))

   341                 throw new IllegalArgumentException("Must be volatile type");

   342 

   343             this.cclass = (Modifier.isProtected(modifiers) &&

   344                            caller != tclass) ? caller : null;

   345             this.tclass = tclass;

   346             if (vclass == Object.class)

   347                 this.vclass = null;

   348             else

   349                 this.vclass = vclass;

   350             offset = unsafe.objectFieldOffset(field);

   351         }

   352 

   353         /**

   354          * Returns true if the second classloader can be found in the first

   355          * classloader's delegation chain.

   356          * Equivalent to the inaccessible: first.isAncestor(second).

   357          */

   358         private static boolean isAncestor(ClassLoader first, ClassLoader second) {

   359             ClassLoader acl = first;

   360             do {

   361                 acl = acl.getParent();

   362                 if (second == acl) {

   363                     return true;

   364                 }

   365             } while (acl != null);

   366             return false;

   367         }

   368 

   369         void targetCheck(T obj) {

   370             if (!tclass.isInstance(obj))

   371                 throw new ClassCastException();

   372             if (cclass != null)

   373                 ensureProtectedAccess(obj);

   374         }

   375 

   376         void updateCheck(T obj, V update) {

   377             if (!tclass.isInstance(obj) ||

   378                 (update != null && vclass != null && !vclass.isInstance(update)))

   379                 throw new ClassCastException();

   380             if (cclass != null)

   381                 ensureProtectedAccess(obj);

   382         }

   383 

   384         public boolean compareAndSet(T obj, V expect, V update) {

   385             if (obj == null || obj.getClass() != tclass || cclass != null ||

   386                 (update != null && vclass != null &&

   387                  vclass != update.getClass()))

   388                 updateCheck(obj, update);

   389             return unsafe.compareAndSwapObject(obj, offset, expect, update);

   390         }

   391 

   392         public boolean weakCompareAndSet(T obj, V expect, V update) {

   393             // same implementation as strong form for now

   394             if (obj == null || obj.getClass() != tclass || cclass != null ||

   395                 (update != null && vclass != null &&

   396                  vclass != update.getClass()))

   397                 updateCheck(obj, update);

   398             return unsafe.compareAndSwapObject(obj, offset, expect, update);

   399         }

   400 

   401         public void set(T obj, V newValue) {

   402             if (obj == null || obj.getClass() != tclass || cclass != null ||

   403                 (newValue != null && vclass != null &&

   404                  vclass != newValue.getClass()))

   405                 updateCheck(obj, newValue);

   406             unsafe.putObjectVolatile(obj, offset, newValue);

   407         }

   408 

   409         public void lazySet(T obj, V newValue) {

   410             if (obj == null || obj.getClass() != tclass || cclass != null ||

   411                 (newValue != null && vclass != null &&

   412                  vclass != newValue.getClass()))

   413                 updateCheck(obj, newValue);

   414             unsafe.putOrderedObject(obj, offset, newValue);

   415         }

   416 

   417         @SuppressWarnings("unchecked")

   418         public V get(T obj) {

   419             if (obj == null || obj.getClass() != tclass || cclass != null)

   420                 targetCheck(obj);

   421             return (V)unsafe.getObjectVolatile(obj, offset);

   422         }

   423 

   424         @SuppressWarnings("unchecked")

   425         public V getAndSet(T obj, V newValue) {

   426             if (obj == null || obj.getClass() != tclass || cclass != null ||

   427                 (newValue != null && vclass != null &&

   428                  vclass != newValue.getClass()))

   429                 updateCheck(obj, newValue);

   430             return (V)unsafe.getAndSetObject(obj, offset, newValue);

   431         }

   432 

   433         private void ensureProtectedAccess(T obj) {

   434             if (cclass.isInstance(obj)) {

   435                 return;

   436             }

   437             throw new RuntimeException(

   438                 new IllegalAccessException("Class " +

   439                     cclass.getName() +

   440                     " can not access a protected member of class " +

   441                     tclass.getName() +

   442                     " using an instance of " +

   443                     obj.getClass().getName()

   444                 )

   445             );

   446         }

   447     }

   448 }