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 @Contended) to reduce cache contention. Padding is 59 * overkill for most Atomics because they are usually irregularly 60 * scattered in memory and thus don't interfere much with each 61 * other. But Atomic objects residing in arrays will tend to be 62 * placed adjacent to each other, and so will most often share 63 * cache lines (with a huge negative performance impact) without 64 * 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 // Android-removed: @Contended, this hint is not used by the Android runtime. 123 // @jdk.internal.vm.annotation.Contended 124 static final class Cell { 125 volatile long value; Cell(long x)126 Cell(long x) { value = x; } cas(long cmp, long val)127 final boolean cas(long cmp, long val) { 128 return U.compareAndSwapLong(this, VALUE, cmp, val); 129 } reset()130 final void reset() { 131 U.putLongVolatile(this, VALUE, 0L); 132 } reset(long identity)133 final void reset(long identity) { 134 U.putLongVolatile(this, VALUE, identity); 135 } 136 137 // Unsafe mechanics 138 private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 139 private static final long VALUE; 140 static { 141 try { 142 VALUE = U.objectFieldOffset 143 (Cell.class.getDeclaredField("value")); 144 } catch (ReflectiveOperationException e) { 145 throw new Error(e); 146 } 147 } 148 } 149 150 /** Number of CPUS, to place bound on table size */ 151 static final int NCPU = Runtime.getRuntime().availableProcessors(); 152 153 /** 154 * Table of cells. When non-null, size is a power of 2. 155 */ 156 transient volatile Cell[] cells; 157 158 /** 159 * Base value, used mainly when there is no contention, but also as 160 * a fallback during table initialization races. Updated via CAS. 161 */ 162 transient volatile long base; 163 164 /** 165 * Spinlock (locked via CAS) used when resizing and/or creating Cells. 166 */ 167 transient volatile int cellsBusy; 168 169 /** 170 * Package-private default constructor. 171 */ Striped64()172 Striped64() { 173 } 174 175 /** 176 * CASes the base field. 177 */ casBase(long cmp, long val)178 final boolean casBase(long cmp, long val) { 179 return U.compareAndSwapLong(this, BASE, cmp, val); 180 } 181 182 /** 183 * CASes the cellsBusy field from 0 to 1 to acquire lock. 184 */ casCellsBusy()185 final boolean casCellsBusy() { 186 return U.compareAndSwapInt(this, CELLSBUSY, 0, 1); 187 } 188 189 /** 190 * Returns the probe value for the current thread. 191 * Duplicated from ThreadLocalRandom because of packaging restrictions. 192 */ getProbe()193 static final int getProbe() { 194 return U.getInt(Thread.currentThread(), PROBE); 195 } 196 197 /** 198 * Pseudo-randomly advances and records the given probe value for the 199 * given thread. 200 * Duplicated from ThreadLocalRandom because of packaging restrictions. 201 */ advanceProbe(int probe)202 static final int advanceProbe(int probe) { 203 probe ^= probe << 13; // xorshift 204 probe ^= probe >>> 17; 205 probe ^= probe << 5; 206 U.putInt(Thread.currentThread(), PROBE, probe); 207 return probe; 208 } 209 210 /** 211 * Handles cases of updates involving initialization, resizing, 212 * creating new Cells, and/or contention. See above for 213 * explanation. This method suffers the usual non-modularity 214 * problems of optimistic retry code, relying on rechecked sets of 215 * reads. 216 * 217 * @param x the value 218 * @param fn the update function, or null for add (this convention 219 * avoids the need for an extra field or function in LongAdder). 220 * @param wasUncontended false if CAS failed before call 221 */ longAccumulate(long x, LongBinaryOperator fn, boolean wasUncontended)222 final void longAccumulate(long x, LongBinaryOperator fn, 223 boolean wasUncontended) { 224 int h; 225 if ((h = getProbe()) == 0) { 226 ThreadLocalRandom.current(); // force initialization 227 h = getProbe(); 228 wasUncontended = true; 229 } 230 boolean collide = false; // True if last slot nonempty 231 done: for (;;) { 232 Cell[] as; Cell a; int n; long v; 233 if ((as = cells) != null && (n = as.length) > 0) { 234 if ((a = as[(n - 1) & h]) == null) { 235 if (cellsBusy == 0) { // Try to attach new Cell 236 Cell r = new Cell(x); // Optimistically create 237 if (cellsBusy == 0 && casCellsBusy()) { 238 try { // Recheck under lock 239 Cell[] rs; int m, j; 240 if ((rs = cells) != null && 241 (m = rs.length) > 0 && 242 rs[j = (m - 1) & h] == null) { 243 rs[j] = r; 244 break done; 245 } 246 } finally { 247 cellsBusy = 0; 248 } 249 continue; // Slot is now non-empty 250 } 251 } 252 collide = false; 253 } 254 else if (!wasUncontended) // CAS already known to fail 255 wasUncontended = true; // Continue after rehash 256 else if (a.cas(v = a.value, 257 (fn == null) ? v + x : fn.applyAsLong(v, x))) 258 break; 259 else if (n >= NCPU || cells != as) 260 collide = false; // At max size or stale 261 else if (!collide) 262 collide = true; 263 else if (cellsBusy == 0 && casCellsBusy()) { 264 try { 265 if (cells == as) // Expand table unless stale 266 cells = Arrays.copyOf(as, n << 1); 267 } finally { 268 cellsBusy = 0; 269 } 270 collide = false; 271 continue; // Retry with expanded table 272 } 273 h = advanceProbe(h); 274 } 275 else if (cellsBusy == 0 && cells == as && casCellsBusy()) { 276 try { // Initialize table 277 if (cells == as) { 278 Cell[] rs = new Cell[2]; 279 rs[h & 1] = new Cell(x); 280 cells = rs; 281 break done; 282 } 283 } finally { 284 cellsBusy = 0; 285 } 286 } 287 // Fall back on using base 288 else if (casBase(v = base, 289 (fn == null) ? v + x : fn.applyAsLong(v, x))) 290 break done; 291 } 292 } 293 apply(DoubleBinaryOperator fn, long v, double x)294 private static long apply(DoubleBinaryOperator fn, long v, double x) { 295 double d = Double.longBitsToDouble(v); 296 d = (fn == null) ? d + x : fn.applyAsDouble(d, x); 297 return Double.doubleToRawLongBits(d); 298 } 299 300 /** 301 * Same as longAccumulate, but injecting long/double conversions 302 * in too many places to sensibly merge with long version, given 303 * the low-overhead requirements of this class. So must instead be 304 * maintained by copy/paste/adapt. 305 */ doubleAccumulate(double x, DoubleBinaryOperator fn, boolean wasUncontended)306 final void doubleAccumulate(double x, DoubleBinaryOperator fn, 307 boolean wasUncontended) { 308 int h; 309 if ((h = getProbe()) == 0) { 310 ThreadLocalRandom.current(); // force initialization 311 h = getProbe(); 312 wasUncontended = true; 313 } 314 boolean collide = false; // True if last slot nonempty 315 done: for (;;) { 316 Cell[] as; Cell a; int n; long v; 317 if ((as = cells) != null && (n = as.length) > 0) { 318 if ((a = as[(n - 1) & h]) == null) { 319 if (cellsBusy == 0) { // Try to attach new Cell 320 Cell r = new Cell(Double.doubleToRawLongBits(x)); 321 if (cellsBusy == 0 && casCellsBusy()) { 322 try { // Recheck under lock 323 Cell[] rs; int m, j; 324 if ((rs = cells) != null && 325 (m = rs.length) > 0 && 326 rs[j = (m - 1) & h] == null) { 327 rs[j] = r; 328 break done; 329 } 330 } finally { 331 cellsBusy = 0; 332 } 333 continue; // Slot is now non-empty 334 } 335 } 336 collide = false; 337 } 338 else if (!wasUncontended) // CAS already known to fail 339 wasUncontended = true; // Continue after rehash 340 else if (a.cas(v = a.value, apply(fn, v, x))) 341 break; 342 else if (n >= NCPU || cells != as) 343 collide = false; // At max size or stale 344 else if (!collide) 345 collide = true; 346 else if (cellsBusy == 0 && casCellsBusy()) { 347 try { 348 if (cells == as) // Expand table unless stale 349 cells = Arrays.copyOf(as, n << 1); 350 } finally { 351 cellsBusy = 0; 352 } 353 collide = false; 354 continue; // Retry with expanded table 355 } 356 h = advanceProbe(h); 357 } 358 else if (cellsBusy == 0 && cells == as && casCellsBusy()) { 359 try { // Initialize table 360 if (cells == as) { 361 Cell[] rs = new Cell[2]; 362 rs[h & 1] = new Cell(Double.doubleToRawLongBits(x)); 363 cells = rs; 364 break done; 365 } 366 } finally { 367 cellsBusy = 0; 368 } 369 } 370 // Fall back on using base 371 else if (casBase(v = base, apply(fn, v, x))) 372 break done; 373 } 374 } 375 376 // Unsafe mechanics 377 private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 378 private static final long BASE; 379 private static final long CELLSBUSY; 380 private static final long PROBE; 381 static { 382 try { 383 BASE = U.objectFieldOffset 384 (Striped64.class.getDeclaredField("base")); 385 CELLSBUSY = U.objectFieldOffset 386 (Striped64.class.getDeclaredField("cellsBusy")); 387 388 PROBE = U.objectFieldOffset 389 (Thread.class.getDeclaredField("threadLocalRandomProbe")); 390 } catch (ReflectiveOperationException e) { 391 throw new Error(e); 392 } 393 } 394 395 } 396