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