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.util.Arrays;
  39 import java.util.concurrent.ThreadLocalRandom;
  40 import java.util.function.DoubleBinaryOperator;
  41 import java.util.function.LongBinaryOperator;
  42 
  43 /**
  44  * A package-local class holding common representation and mechanics
  45  * for classes supporting dynamic striping on 64bit values. The class
  46  * extends Number so that concrete subclasses must publicly do so.
  47  */
  48 @SuppressWarnings("serial")
  49 abstract class Striped64 extends Number {
  50     /*
  51      * This class maintains a lazily-initialized table of atomically
  52      * updated variables, plus an extra "base" field. The table size
  53      * is a power of two. Indexing uses masked per-thread hash codes.
  54      * Nearly all declarations in this class are package-private,
  55      * accessed directly by subclasses.
  56      *
  57      * Table entries are of class Cell; a variant of AtomicLong padded
  58      * (via @sun.misc.Contended) to reduce cache contention. Padding
  59      * is overkill for most Atomics because they are usually
  60      * irregularly scattered in memory and thus don't interfere much
  61      * with each other. But Atomic objects residing in arrays will
  62      * tend to be placed adjacent to each other, and so will most
  63      * often share cache lines (with a huge negative performance
  64      * impact) without this precaution.
  65      *
  66      * In part because Cells are relatively large, we avoid creating
  67      * them until they are needed.  When there is no contention, all
  68      * updates are made to the base field.  Upon first contention (a
  69      * failed CAS on base update), the table is initialized to size 2.
  70      * The table size is doubled upon further contention until
  71      * reaching the nearest power of two greater than or equal to the
  72      * number of CPUS. Table slots remain empty (null) until they are
  73      * needed.
  74      *
  75      * A single spinlock ("cellsBusy") is used for initializing and
  76      * resizing the table, as well as populating slots with new Cells.
  77      * There is no need for a blocking lock; when the lock is not
  78      * available, threads try other slots (or the base).  During these
  79      * retries, there is increased contention and reduced locality,
  80      * which is still better than alternatives.
  81      *
  82      * The Thread probe fields maintained via ThreadLocalRandom serve
  83      * as per-thread hash codes. We let them remain uninitialized as
  84      * zero (if they come in this way) until they contend at slot
  85      * 0. They are then initialized to values that typically do not
  86      * often conflict with others.  Contention and/or table collisions
  87      * are indicated by failed CASes when performing an update
  88      * operation. Upon a collision, if the table size is less than
  89      * the capacity, it is doubled in size unless some other thread
  90      * holds the lock. If a hashed slot is empty, and lock is
  91      * available, a new Cell is created. Otherwise, if the slot
  92      * exists, a CAS is tried.  Retries proceed by "double hashing",
  93      * using a secondary hash (Marsaglia XorShift) to try to find a
  94      * free slot.
  95      *
  96      * The table size is capped because, when there are more threads
  97      * than CPUs, supposing that each thread were bound to a CPU,
  98      * there would exist a perfect hash function mapping threads to
  99      * slots that eliminates collisions. When we reach capacity, we
 100      * search for this mapping by randomly varying the hash codes of
 101      * colliding threads.  Because search is random, and collisions
 102      * only become known via CAS failures, convergence can be slow,
 103      * and because threads are typically not bound to CPUS forever,
 104      * may not occur at all. However, despite these limitations,
 105      * observed contention rates are typically low in these cases.
 106      *
 107      * It is possible for a Cell to become unused when threads that
 108      * once hashed to it terminate, as well as in the case where
 109      * doubling the table causes no thread to hash to it under
 110      * expanded mask.  We do not try to detect or remove such cells,
 111      * under the assumption that for long-running instances, observed
 112      * contention levels will recur, so the cells will eventually be
 113      * needed again; and for short-lived ones, it does not matter.
 114      */
 115 
 116     /**
 117      * Padded variant of AtomicLong supporting only raw accesses plus CAS.
 118      *
 119      * JVM intrinsics note: It would be possible to use a release-only
 120      * form of CAS here, if it were provided.
 121      */
 122     @sun.misc.Contended static final class Cell {
 123         volatile long value;
 124         Cell(long x) { value = x; }
 125         final boolean cas(long cmp, long val) {
 126             return U.compareAndSwapLong(this, VALUE, cmp, val);
 127         }
 128         final void reset() {
 129             U.putLongVolatile(this, VALUE, 0L);
 130         }
 131         final void reset(long identity) {
 132             U.putLongVolatile(this, VALUE, identity);
 133         }
 134 
 135         // Unsafe mechanics
 136         private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
 137         private static final long VALUE;
 138         static {
 139             try {
 140                 VALUE = U.objectFieldOffset
 141                     (Cell.class.getDeclaredField("value"));
 142             } catch (ReflectiveOperationException e) {
 143                 throw new Error(e);
 144             }
 145         }
 146     }
 147 
 148     /** Number of CPUS, to place bound on table size */
 149     static final int NCPU = Runtime.getRuntime().availableProcessors();
 150 
 151     /**
 152      * Table of cells. When non-null, size is a power of 2.
 153      */
 154     transient volatile Cell[] cells;
 155 
 156     /**
 157      * Base value, used mainly when there is no contention, but also as
 158      * a fallback during table initialization races. Updated via CAS.
 159      */
 160     transient volatile long base;
 161 
 162     /**
 163      * Spinlock (locked via CAS) used when resizing and/or creating Cells.
 164      */
 165     transient volatile int cellsBusy;
 166 
 167     /**
 168      * Package-private default constructor.
 169      */
 170     Striped64() {
 171     }
 172 
 173     /**
 174      * CASes the base field.
 175      */
 176     final boolean casBase(long cmp, long val) {
 177         return U.compareAndSwapLong(this, BASE, cmp, val);
 178     }
 179 
 180     /**
 181      * CASes the cellsBusy field from 0 to 1 to acquire lock.
 182      */
 183     final boolean casCellsBusy() {
 184         return U.compareAndSwapInt(this, CELLSBUSY, 0, 1);
 185     }
 186 
 187     /**
 188      * Returns the probe value for the current thread.
 189      * Duplicated from ThreadLocalRandom because of packaging restrictions.
 190      */
 191     static final int getProbe() {
 192         return U.getInt(Thread.currentThread(), PROBE);
 193     }
 194 
 195     /**
 196      * Pseudo-randomly advances and records the given probe value for the
 197      * given thread.
 198      * Duplicated from ThreadLocalRandom because of packaging restrictions.
 199      */
 200     static final int advanceProbe(int probe) {
 201         probe ^= probe << 13;   // xorshift
 202         probe ^= probe >>> 17;
 203         probe ^= probe << 5;
 204         U.putInt(Thread.currentThread(), PROBE, probe);
 205         return probe;
 206     }
 207 
 208     /**
 209      * Handles cases of updates involving initialization, resizing,
 210      * creating new Cells, and/or contention. See above for
 211      * explanation. This method suffers the usual non-modularity
 212      * problems of optimistic retry code, relying on rechecked sets of
 213      * reads.
 214      *
 215      * @param x the value
 216      * @param fn the update function, or null for add (this convention
 217      * avoids the need for an extra field or function in LongAdder).
 218      * @param wasUncontended false if CAS failed before call
 219      */
 220     final void longAccumulate(long x, LongBinaryOperator fn,
 221                               boolean wasUncontended) {
 222         int h;
 223         if ((h = getProbe()) == 0) {
 224             ThreadLocalRandom.current(); // force initialization
 225             h = getProbe();
 226             wasUncontended = true;
 227         }
 228         boolean collide = false;                // True if last slot nonempty
 229         done: for (;;) {
 230             Cell[] as; Cell a; int n; long v;
 231             if ((as = cells) != null && (n = as.length) > 0) {
 232                 if ((a = as[(n - 1) & h]) == null) {
 233                     if (cellsBusy == 0) {       // Try to attach new Cell
 234                         Cell r = new Cell(x);   // Optimistically create
 235                         if (cellsBusy == 0 && casCellsBusy()) {
 236                             try {               // Recheck under lock
 237                                 Cell[] rs; int m, j;
 238                                 if ((rs = cells) != null &&
 239                                     (m = rs.length) > 0 &&
 240                                     rs[j = (m - 1) & h] == null) {
 241                                     rs[j] = r;
 242                                     break done;
 243                                 }
 244                             } finally {
 245                                 cellsBusy = 0;
 246                             }
 247                             continue;           // Slot is now non-empty
 248                         }
 249                     }
 250                     collide = false;
 251                 }
 252                 else if (!wasUncontended)       // CAS already known to fail
 253                     wasUncontended = true;      // Continue after rehash
 254                 else if (a.cas(v = a.value,
 255                                (fn == null) ? v + x : fn.applyAsLong(v, x)))
 256                     break;
 257                 else if (n >= NCPU || cells != as)
 258                     collide = false;            // At max size or stale
 259                 else if (!collide)
 260                     collide = true;
 261                 else if (cellsBusy == 0 && casCellsBusy()) {
 262                     try {
 263                         if (cells == as)        // Expand table unless stale
 264                             cells = Arrays.copyOf(as, n << 1);
 265                     } finally {
 266                         cellsBusy = 0;
 267                     }
 268                     collide = false;
 269                     continue;                   // Retry with expanded table
 270                 }
 271                 h = advanceProbe(h);
 272             }
 273             else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
 274                 try {                           // Initialize table
 275                     if (cells == as) {
 276                         Cell[] rs = new Cell[2];
 277                         rs[h & 1] = new Cell(x);
 278                         cells = rs;
 279                         break done;
 280                     }
 281                 } finally {
 282                     cellsBusy = 0;
 283                 }
 284             }
 285             // Fall back on using base
 286             else if (casBase(v = base,
 287                              (fn == null) ? v + x : fn.applyAsLong(v, x)))
 288                 break done;
 289         }
 290     }
 291 
 292     private static long apply(DoubleBinaryOperator fn, long v, double x) {
 293         double d = Double.longBitsToDouble(v);
 294         d = (fn == null) ? d + x : fn.applyAsDouble(d, x);
 295         return Double.doubleToRawLongBits(d);
 296     }
 297 
 298     /**
 299      * Same as longAccumulate, but injecting long/double conversions
 300      * in too many places to sensibly merge with long version, given
 301      * the low-overhead requirements of this class. So must instead be
 302      * maintained by copy/paste/adapt.
 303      */
 304     final void doubleAccumulate(double x, DoubleBinaryOperator fn,
 305                                 boolean wasUncontended) {
 306         int h;
 307         if ((h = getProbe()) == 0) {
 308             ThreadLocalRandom.current(); // force initialization
 309             h = getProbe();
 310             wasUncontended = true;
 311         }
 312         boolean collide = false;                // True if last slot nonempty
 313         done: for (;;) {
 314             Cell[] as; Cell a; int n; long v;
 315             if ((as = cells) != null && (n = as.length) > 0) {
 316                 if ((a = as[(n - 1) & h]) == null) {
 317                     if (cellsBusy == 0) {       // Try to attach new Cell
 318                         Cell r = new Cell(Double.doubleToRawLongBits(x));
 319                         if (cellsBusy == 0 && casCellsBusy()) {
 320                             try {               // Recheck under lock
 321                                 Cell[] rs; int m, j;
 322                                 if ((rs = cells) != null &&
 323                                     (m = rs.length) > 0 &&
 324                                     rs[j = (m - 1) & h] == null) {
 325                                     rs[j] = r;
 326                                     break done;
 327                                 }
 328                             } finally {
 329                                 cellsBusy = 0;
 330                             }
 331                             continue;           // Slot is now non-empty
 332                         }
 333                     }
 334                     collide = false;
 335                 }
 336                 else if (!wasUncontended)       // CAS already known to fail
 337                     wasUncontended = true;      // Continue after rehash
 338                 else if (a.cas(v = a.value, apply(fn, v, x)))
 339                     break;
 340                 else if (n >= NCPU || cells != as)
 341                     collide = false;            // At max size or stale
 342                 else if (!collide)
 343                     collide = true;
 344                 else if (cellsBusy == 0 && casCellsBusy()) {
 345                     try {
 346                         if (cells == as)        // Expand table unless stale
 347                             cells = Arrays.copyOf(as, n << 1);
 348                     } finally {
 349                         cellsBusy = 0;
 350                     }
 351                     collide = false;
 352                     continue;                   // Retry with expanded table
 353                 }
 354                 h = advanceProbe(h);
 355             }
 356             else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
 357                 try {                           // Initialize table
 358                     if (cells == as) {
 359                         Cell[] rs = new Cell[2];
 360                         rs[h & 1] = new Cell(Double.doubleToRawLongBits(x));
 361                         cells = rs;
 362                         break done;
 363                     }
 364                 } finally {
 365                     cellsBusy = 0;
 366                 }
 367             }
 368             // Fall back on using base
 369             else if (casBase(v = base, apply(fn, v, x)))
 370                 break done;
 371         }
 372     }
 373 
 374     // Unsafe mechanics
 375     private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
 376     private static final long BASE;
 377     private static final long CELLSBUSY;
 378     private static final long PROBE;
 379     static {
 380         try {
 381             BASE = U.objectFieldOffset
 382                 (Striped64.class.getDeclaredField("base"));
 383             CELLSBUSY = U.objectFieldOffset
 384                 (Striped64.class.getDeclaredField("cellsBusy"));
 385 
 386             PROBE = U.objectFieldOffset
 387                 (Thread.class.getDeclaredField("threadLocalRandomProbe"));
 388         } catch (ReflectiveOperationException e) {
 389             throw new Error(e);
 390         }
 391     }
 392 
 393 }