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