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