| 6 |
|
*/ |
| 7 |
|
|
| 8 |
|
package java.util.concurrent; |
| 9 |
+ |
import java.lang.invoke.MethodHandles; |
| 10 |
+ |
import java.lang.invoke.VarHandle; |
| 11 |
+ |
import java.util.concurrent.locks.LockSupport; |
| 12 |
|
|
| 13 |
|
/** |
| 14 |
|
* A synchronization point at which threads can pair and swap elements |
| 129 |
|
* a value that is enough for common platforms. Additionally, |
| 130 |
|
* extra care elsewhere is taken to avoid other false/unintended |
| 131 |
|
* sharing and to enhance locality, including adding padding (via |
| 132 |
< |
* @Contended) to Nodes, embedding "bound" as an Exchanger field, |
| 130 |
< |
* and reworking some park/unpark mechanics compared to |
| 131 |
< |
* LockSupport versions. |
| 132 |
> |
* @Contended) to Nodes, embedding "bound" as an Exchanger field. |
| 133 |
|
* |
| 134 |
|
* The arena starts out with only one used slot. We expand the |
| 135 |
|
* effective arena size by tracking collisions; i.e., failed CASes |
| 206 |
|
* because most of the logic relies on reads of fields that are |
| 207 |
|
* maintained as local variables so can't be nicely factored -- |
| 208 |
|
* mainly, here, bulky spin->yield->block/cancel code), and |
| 209 |
< |
* heavily dependent on intrinsics (Unsafe) to use inlined |
| 209 |
> |
* heavily dependent on intrinsics (VarHandles) to use inlined |
| 210 |
|
* embedded CAS and related memory access operations (that tend |
| 211 |
|
* not to be as readily inlined by dynamic compilers when they are |
| 212 |
|
* hidden behind other methods that would more nicely name and |
| 328 |
|
*/ |
| 329 |
|
private final Object arenaExchange(Object item, boolean timed, long ns) { |
| 330 |
|
Node[] a = arena; |
| 331 |
+ |
int alen = a.length; |
| 332 |
|
Node p = participant.get(); |
| 333 |
|
for (int i = p.index;;) { // access slot at i |
| 334 |
< |
int b, m, c; long j; // j is raw array offset |
| 335 |
< |
Node q = (Node)U.getObjectVolatile(a, j = (i << ASHIFT) + ABASE); |
| 336 |
< |
if (q != null && U.compareAndSwapObject(a, j, q, null)) { |
| 334 |
> |
int b, m, c; |
| 335 |
> |
int j = (i << ASHIFT) + ((1 << ASHIFT) - 1); |
| 336 |
> |
if (j < 0 || j >= alen) |
| 337 |
> |
j = alen - 1; |
| 338 |
> |
Node q = (Node)AA.get(a, j); |
| 339 |
> |
if (q != null && AA.compareAndSet(a, j, q, null)) { |
| 340 |
|
Object v = q.item; // release |
| 341 |
|
q.match = item; |
| 342 |
|
Thread w = q.parked; |
| 343 |
|
if (w != null) |
| 344 |
< |
U.unpark(w); |
| 344 |
> |
LockSupport.unpark(w); |
| 345 |
|
return v; |
| 346 |
|
} |
| 347 |
|
else if (i <= (m = (b = bound) & MMASK) && q == null) { |
| 348 |
|
p.item = item; // offer |
| 349 |
< |
if (U.compareAndSwapObject(a, j, null, p)) { |
| 349 |
> |
if (AA.compareAndSet(a, j, null, p)) { |
| 350 |
|
long end = (timed && m == 0) ? System.nanoTime() + ns : 0L; |
| 351 |
|
Thread t = Thread.currentThread(); // wait |
| 352 |
|
for (int h = p.hash, spins = SPINS;;) { |
| 353 |
|
Object v = p.match; |
| 354 |
|
if (v != null) { |
| 355 |
< |
U.putObjectRelease(p, MATCH, null); |
| 355 |
> |
MATCH.setRelease(p, null); |
| 356 |
|
p.item = null; // clear for next use |
| 357 |
|
p.hash = h; |
| 358 |
|
return v; |
| 365 |
|
(--spins & ((SPINS >>> 1) - 1)) == 0) |
| 366 |
|
Thread.yield(); // two yields per wait |
| 367 |
|
} |
| 368 |
< |
else if (U.getObjectVolatile(a, j) != p) |
| 368 |
> |
else if (AA.getVolatile(a, j) != p) |
| 369 |
|
spins = SPINS; // releaser hasn't set match yet |
| 370 |
|
else if (!t.isInterrupted() && m == 0 && |
| 371 |
|
(!timed || |
| 372 |
|
(ns = end - System.nanoTime()) > 0L)) { |
| 368 |
– |
U.putObject(t, BLOCKER, this); // emulate LockSupport |
| 373 |
|
p.parked = t; // minimize window |
| 374 |
< |
if (U.getObjectVolatile(a, j) == p) |
| 375 |
< |
U.park(false, ns); |
| 374 |
> |
if (AA.getVolatile(a, j) == p) { |
| 375 |
> |
if (ns == 0L) |
| 376 |
> |
LockSupport.park(this); |
| 377 |
> |
else |
| 378 |
> |
LockSupport.parkNanos(this, ns); |
| 379 |
> |
} |
| 380 |
|
p.parked = null; |
| 373 |
– |
U.putObject(t, BLOCKER, null); |
| 381 |
|
} |
| 382 |
< |
else if (U.getObjectVolatile(a, j) == p && |
| 383 |
< |
U.compareAndSwapObject(a, j, p, null)) { |
| 382 |
> |
else if (AA.getVolatile(a, j) == p && |
| 383 |
> |
AA.compareAndSet(a, j, p, null)) { |
| 384 |
|
if (m != 0) // try to shrink |
| 385 |
< |
U.compareAndSwapInt(this, BOUND, b, b + SEQ - 1); |
| 385 |
> |
BOUND.compareAndSet(this, b, b + SEQ - 1); |
| 386 |
|
p.item = null; |
| 387 |
|
p.hash = h; |
| 388 |
|
i = p.index >>>= 1; // descend |
| 404 |
|
i = (i != m || m == 0) ? m : m - 1; |
| 405 |
|
} |
| 406 |
|
else if ((c = p.collides) < m || m == FULL || |
| 407 |
< |
!U.compareAndSwapInt(this, BOUND, b, b + SEQ + 1)) { |
| 407 |
> |
!BOUND.compareAndSet(this, b, b + SEQ + 1)) { |
| 408 |
|
p.collides = c + 1; |
| 409 |
|
i = (i == 0) ? m : i - 1; // cyclically traverse |
| 410 |
|
} |
| 433 |
|
|
| 434 |
|
for (Node q;;) { |
| 435 |
|
if ((q = slot) != null) { |
| 436 |
< |
if (U.compareAndSwapObject(this, SLOT, q, null)) { |
| 436 |
> |
if (SLOT.compareAndSet(this, q, null)) { |
| 437 |
|
Object v = q.item; |
| 438 |
|
q.match = item; |
| 439 |
|
Thread w = q.parked; |
| 440 |
|
if (w != null) |
| 441 |
< |
U.unpark(w); |
| 441 |
> |
LockSupport.unpark(w); |
| 442 |
|
return v; |
| 443 |
|
} |
| 444 |
|
// create arena on contention, but continue until slot null |
| 445 |
|
if (NCPU > 1 && bound == 0 && |
| 446 |
< |
U.compareAndSwapInt(this, BOUND, 0, SEQ)) |
| 446 |
> |
BOUND.compareAndSet(this, 0, SEQ)) |
| 447 |
|
arena = new Node[(FULL + 2) << ASHIFT]; |
| 448 |
|
} |
| 449 |
|
else if (arena != null) |
| 450 |
|
return null; // caller must reroute to arenaExchange |
| 451 |
|
else { |
| 452 |
|
p.item = item; |
| 453 |
< |
if (U.compareAndSwapObject(this, SLOT, null, p)) |
| 453 |
> |
if (SLOT.compareAndSet(this, null, p)) |
| 454 |
|
break; |
| 455 |
|
p.item = null; |
| 456 |
|
} |
| 473 |
|
spins = SPINS; |
| 474 |
|
else if (!t.isInterrupted() && arena == null && |
| 475 |
|
(!timed || (ns = end - System.nanoTime()) > 0L)) { |
| 469 |
– |
U.putObject(t, BLOCKER, this); |
| 476 |
|
p.parked = t; |
| 477 |
< |
if (slot == p) |
| 478 |
< |
U.park(false, ns); |
| 477 |
> |
if (slot == p) { |
| 478 |
> |
if (ns == 0L) |
| 479 |
> |
LockSupport.park(this); |
| 480 |
> |
else |
| 481 |
> |
LockSupport.parkNanos(this, ns); |
| 482 |
> |
} |
| 483 |
|
p.parked = null; |
| 474 |
– |
U.putObject(t, BLOCKER, null); |
| 484 |
|
} |
| 485 |
< |
else if (U.compareAndSwapObject(this, SLOT, p, null)) { |
| 485 |
> |
else if (SLOT.compareAndSet(this, p, null)) { |
| 486 |
|
v = timed && ns <= 0L && !t.isInterrupted() ? TIMED_OUT : null; |
| 487 |
|
break; |
| 488 |
|
} |
| 489 |
|
} |
| 490 |
< |
U.putObjectRelease(p, MATCH, null); |
| 490 |
> |
MATCH.setRelease(p, null); |
| 491 |
|
p.item = null; |
| 492 |
|
p.hash = h; |
| 493 |
|
return v; |
| 536 |
|
@SuppressWarnings("unchecked") |
| 537 |
|
public V exchange(V x) throws InterruptedException { |
| 538 |
|
Object v; |
| 539 |
+ |
Node[] a; |
| 540 |
|
Object item = (x == null) ? NULL_ITEM : x; // translate null args |
| 541 |
< |
if ((arena != null || |
| 541 |
> |
if (((a = arena) != null || |
| 542 |
|
(v = slotExchange(item, false, 0L)) == null) && |
| 543 |
|
((Thread.interrupted() || // disambiguates null return |
| 544 |
|
(v = arenaExchange(item, false, 0L)) == null))) |
| 604 |
|
return (v == NULL_ITEM) ? null : (V)v; |
| 605 |
|
} |
| 606 |
|
|
| 607 |
< |
// Unsafe mechanics |
| 608 |
< |
private static final jdk.internal.misc.Unsafe U = jdk.internal.misc.Unsafe.getUnsafe(); |
| 609 |
< |
private static final long BOUND; |
| 610 |
< |
private static final long SLOT; |
| 611 |
< |
private static final long MATCH; |
| 602 |
< |
private static final long BLOCKER; |
| 603 |
< |
private static final int ABASE; |
| 607 |
> |
// VarHandle mechanics |
| 608 |
> |
private static final VarHandle BOUND; |
| 609 |
> |
private static final VarHandle SLOT; |
| 610 |
> |
private static final VarHandle MATCH; |
| 611 |
> |
private static final VarHandle AA; |
| 612 |
|
static { |
| 613 |
|
try { |
| 614 |
< |
BOUND = U.objectFieldOffset |
| 615 |
< |
(Exchanger.class.getDeclaredField("bound")); |
| 616 |
< |
SLOT = U.objectFieldOffset |
| 617 |
< |
(Exchanger.class.getDeclaredField("slot")); |
| 618 |
< |
|
| 611 |
< |
MATCH = U.objectFieldOffset |
| 612 |
< |
(Node.class.getDeclaredField("match")); |
| 613 |
< |
|
| 614 |
< |
BLOCKER = U.objectFieldOffset |
| 615 |
< |
(Thread.class.getDeclaredField("parkBlocker")); |
| 616 |
< |
|
| 617 |
< |
int scale = U.arrayIndexScale(Node[].class); |
| 618 |
< |
if ((scale & (scale - 1)) != 0 || scale > (1 << ASHIFT)) |
| 619 |
< |
throw new Error("Unsupported array scale"); |
| 620 |
< |
// ABASE absorbs padding in front of element 0 |
| 621 |
< |
ABASE = U.arrayBaseOffset(Node[].class) + (1 << ASHIFT); |
| 614 |
> |
MethodHandles.Lookup l = MethodHandles.lookup(); |
| 615 |
> |
BOUND = l.findVarHandle(Exchanger.class, "bound", int.class); |
| 616 |
> |
SLOT = l.findVarHandle(Exchanger.class, "slot", Node.class); |
| 617 |
> |
MATCH = l.findVarHandle(Node.class, "match", Object.class); |
| 618 |
> |
AA = MethodHandles.arrayElementVarHandle(Node[].class); |
| 619 |
|
} catch (ReflectiveOperationException e) { |
| 620 |
|
throw new Error(e); |
| 621 |
|
} |
