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 
  38 import java.lang.reflect.Field;
  39 import java.lang.reflect.Modifier;
  40 import java.security.AccessController;
  41 import java.security.PrivilegedActionException;
  42 import java.security.PrivilegedExceptionAction;
  43 import java.util.function.BinaryOperator;
  44 import java.util.function.UnaryOperator;
  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 sun.misc.Unsafe U = sun.misc.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 = U.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 U.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 U.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             U.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             U.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)U.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)U.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 }