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