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 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 jdk.internal.misc.Unsafe U = jdk.internal.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 jdk.internal.misc.Unsafe U = jdk.internal.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 }