1a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson/* 229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is free software; you can redistribute it and/or modify it 529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * under the terms of the GNU General Public License version 2 only, as 629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * published by the Free Software Foundation. Oracle designates this 729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * particular file as subject to the "Classpath" exception as provided 829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * by Oracle in the LICENSE file that accompanied this code. 929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is distributed in the hope that it will be useful, but WITHOUT 1129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * version 2 for more details (a copy is included in the LICENSE file that 1429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * accompanied this code). 1529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * You should have received a copy of the GNU General Public License version 1729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2 along with this work; if not, write to the Free Software Foundation, 1829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * or visit www.oracle.com if you need additional information or have any 2229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * questions. 2329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer */ 2429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer 2529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer/* 2629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This file is available under and governed by the GNU General Public 2729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * License version 2 only, as published by the Free Software Foundation. 2829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * However, the following notice accompanied the original version of this 2929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * file: 3029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 31a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Written by Doug Lea with assistance from members of JCP JSR-166 32a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Expert Group and released to the public domain, as explained at 33a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 34a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 35a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 36a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonpackage java.util.concurrent; 37a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 38a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.concurrent.atomic.AtomicReference; 39a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonimport java.util.concurrent.locks.LockSupport; 40a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 41a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson/** 42a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * A reusable synchronization barrier, similar in functionality to 43a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link java.util.concurrent.CyclicBarrier CyclicBarrier} and 44a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link java.util.concurrent.CountDownLatch CountDownLatch} 45a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * but supporting more flexible usage. 46a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 4791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * <p><b>Registration.</b> Unlike the case for other barriers, the 48a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * number of parties <em>registered</em> to synchronize on a phaser 49a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * may vary over time. Tasks may be registered at any time (using 50a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * methods {@link #register}, {@link #bulkRegister}, or forms of 51a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * constructors establishing initial numbers of parties), and 52a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * optionally deregistered upon any arrival (using {@link 53a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * #arriveAndDeregister}). As is the case with most basic 54a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * synchronization constructs, registration and deregistration affect 55a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * only internal counts; they do not establish any further internal 56a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * bookkeeping, so tasks cannot query whether they are registered. 57a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * (However, you can introduce such bookkeeping by subclassing this 58a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * class.) 59a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 6091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * <p><b>Synchronization.</b> Like a {@code CyclicBarrier}, a {@code 61a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Phaser} may be repeatedly awaited. Method {@link 62a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * #arriveAndAwaitAdvance} has effect analogous to {@link 63a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * java.util.concurrent.CyclicBarrier#await CyclicBarrier.await}. Each 64a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * generation of a phaser has an associated phase number. The phase 65a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * number starts at zero, and advances when all parties arrive at the 66a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser, wrapping around to zero after reaching {@code 67a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Integer.MAX_VALUE}. The use of phase numbers enables independent 68a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * control of actions upon arrival at a phaser and upon awaiting 69a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * others, via two kinds of methods that may be invoked by any 70a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * registered party: 71a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 72a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <ul> 73a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 74b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li><b>Arrival.</b> Methods {@link #arrive} and 75a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link #arriveAndDeregister} record arrival. These methods 76a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * do not block, but return an associated <em>arrival phase 77a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * number</em>; that is, the phase number of the phaser to which 78a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the arrival applied. When the final party for a given phase 79a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * arrives, an optional action is performed and the phase 80a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * advances. These actions are performed by the party 81a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * triggering a phase advance, and are arranged by overriding 82a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * method {@link #onAdvance(int, int)}, which also controls 83a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * termination. Overriding this method is similar to, but more 84a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * flexible than, providing a barrier action to a {@code 85a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * CyclicBarrier}. 86a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 87b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li><b>Waiting.</b> Method {@link #awaitAdvance} requires an 88a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * argument indicating an arrival phase number, and returns when 89a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the phaser advances to (or is already at) a different phase. 90a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Unlike similar constructions using {@code CyclicBarrier}, 91a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * method {@code awaitAdvance} continues to wait even if the 92a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * waiting thread is interrupted. Interruptible and timeout 93a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * versions are also available, but exceptions encountered while 94a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * tasks wait interruptibly or with timeout do not change the 95a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * state of the phaser. If necessary, you can perform any 96a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * associated recovery within handlers of those exceptions, 97a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * often after invoking {@code forceTermination}. Phasers may 98b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * also be used by tasks executing in a {@link ForkJoinPool}. 99b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Progress is ensured if the pool's parallelismLevel can 100b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * accommodate the maximum number of simultaneously blocked 101b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * parties. 102a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 103a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * </ul> 104a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 10591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * <p><b>Termination.</b> A phaser may enter a <em>termination</em> 106a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * state, that may be checked using method {@link #isTerminated}. Upon 107a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * termination, all synchronization methods immediately return without 108a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * waiting for advance, as indicated by a negative return value. 109a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Similarly, attempts to register upon termination have no effect. 110a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Termination is triggered when an invocation of {@code onAdvance} 111a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * returns {@code true}. The default implementation returns {@code 112a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * true} if a deregistration has caused the number of registered 113a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * parties to become zero. As illustrated below, when phasers control 114a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * actions with a fixed number of iterations, it is often convenient 115a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to override this method to cause termination when the current phase 116a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * number reaches a threshold. Method {@link #forceTermination} is 117a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * also available to abruptly release waiting threads and allow them 118a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to terminate. 119a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 12091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * <p><b>Tiering.</b> Phasers may be <em>tiered</em> (i.e., 121a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * constructed in tree structures) to reduce contention. Phasers with 122a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * large numbers of parties that would otherwise experience heavy 123a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * synchronization contention costs may instead be set up so that 124a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * groups of sub-phasers share a common parent. This may greatly 125a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * increase throughput even though it incurs greater per-operation 126a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * overhead. 127a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 128a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>In a tree of tiered phasers, registration and deregistration of 129a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * child phasers with their parent are managed automatically. 130a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Whenever the number of registered parties of a child phaser becomes 131a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * non-zero (as established in the {@link #Phaser(Phaser,int)} 132a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * constructor, {@link #register}, or {@link #bulkRegister}), the 133a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * child phaser is registered with its parent. Whenever the number of 134a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * registered parties becomes zero as the result of an invocation of 135a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link #arriveAndDeregister}, the child phaser is deregistered 136a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * from its parent. 137a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 138a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p><b>Monitoring.</b> While synchronization methods may be invoked 139a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * only by registered parties, the current state of a phaser may be 140a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * monitored by any caller. At any given moment there are {@link 141a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * #getRegisteredParties} parties in total, of which {@link 142a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * #getArrivedParties} have arrived at the current phase ({@link 143a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * #getPhase}). When the remaining ({@link #getUnarrivedParties}) 144a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * parties arrive, the phase advances. The values returned by these 145a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * methods may reflect transient states and so are not in general 146a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * useful for synchronization control. Method {@link #toString} 147a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * returns snapshots of these state queries in a form convenient for 148a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * informal monitoring. 149a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 150a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p><b>Sample usages:</b> 151a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 152a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>A {@code Phaser} may be used instead of a {@code CountDownLatch} 153a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to control a one-shot action serving a variable number of parties. 154a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The typical idiom is for the method setting this up to first 155a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * register, then start the actions, then deregister, as in: 156a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 157b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 158a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * void runTasks(List<Runnable> tasks) { 159a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * final Phaser phaser = new Phaser(1); // "1" to register self 160a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * // create and start threads 161a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * for (final Runnable task : tasks) { 162a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser.register(); 163a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * new Thread() { 164a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * public void run() { 165a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser.arriveAndAwaitAdvance(); // await all creation 166a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * task.run(); 167a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 168a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }.start(); 169a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 170a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 171a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * // allow threads to start and deregister self 172a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser.arriveAndDeregister(); 173a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }}</pre> 174a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 175a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>One way to cause a set of threads to repeatedly perform actions 176a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * for a given number of iterations is to override {@code onAdvance}: 177a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 178b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 179a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * void startTasks(List<Runnable> tasks, final int iterations) { 180a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * final Phaser phaser = new Phaser() { 181a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * protected boolean onAdvance(int phase, int registeredParties) { 182a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * return phase >= iterations || registeredParties == 0; 183a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 184a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }; 185a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser.register(); 186a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * for (final Runnable task : tasks) { 187a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser.register(); 188a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * new Thread() { 189a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * public void run() { 190a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * do { 191a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * task.run(); 192a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser.arriveAndAwaitAdvance(); 193a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } while (!phaser.isTerminated()); 194a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 195a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }.start(); 196a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 197a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser.arriveAndDeregister(); // deregister self, don't wait 198a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }}</pre> 199a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 200a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * If the main task must later await termination, it 201a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * may re-register and then execute a similar loop: 202b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 203a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * // ... 204a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser.register(); 205a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * while (!phaser.isTerminated()) 206a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser.arriveAndAwaitAdvance();}</pre> 207a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 208a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>Related constructions may be used to await particular phase numbers 209a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * in contexts where you are sure that the phase will never wrap around 210a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code Integer.MAX_VALUE}. For example: 211a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 212b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 213a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * void awaitPhase(Phaser phaser, int phase) { 214a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * int p = phaser.register(); // assumes caller not already registered 215a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * while (p < phase) { 216a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if (phaser.isTerminated()) 217a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * // ... deal with unexpected termination 218a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * else 219a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * p = phaser.arriveAndAwaitAdvance(); 220a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 221a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser.arriveAndDeregister(); 222a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }}</pre> 223a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 224a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 225a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>To create a set of {@code n} tasks using a tree of phasers, you 226a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * could use code of the following form, assuming a Task class with a 227a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * constructor accepting a {@code Phaser} that it registers with upon 228a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * construction. After invocation of {@code build(new Task[n], 0, n, 229a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * new Phaser())}, these tasks could then be started, for example by 230a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * submitting to a pool: 231a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 232b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 233a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * void build(Task[] tasks, int lo, int hi, Phaser ph) { 234a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if (hi - lo > TASKS_PER_PHASER) { 235a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * for (int i = lo; i < hi; i += TASKS_PER_PHASER) { 236a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * int j = Math.min(i + TASKS_PER_PHASER, hi); 237a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * build(tasks, i, j, new Phaser(ph)); 238a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 239a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } else { 240a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * for (int i = lo; i < hi; ++i) 241a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * tasks[i] = new Task(ph); 242a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * // assumes new Task(ph) performs ph.register() 243a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * } 244a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }}</pre> 245a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 246a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The best value of {@code TASKS_PER_PHASER} depends mainly on 247a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * expected synchronization rates. A value as low as four may 248a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * be appropriate for extremely small per-phase task bodies (thus 249a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * high rates), or up to hundreds for extremely large ones. 250a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 251a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p><b>Implementation notes</b>: This implementation restricts the 252a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * maximum number of parties to 65535. Attempts to register additional 253a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * parties result in {@code IllegalStateException}. However, you can and 254a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * should create tiered phasers to accommodate arbitrarily large sets 255a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of participants. 256a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 257a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @since 1.7 258a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @author Doug Lea 259a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 260a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilsonpublic class Phaser { 261a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /* 262a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * This class implements an extension of X10 "clocks". Thanks to 263a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Vijay Saraswat for the idea, and to Vivek Sarkar for 264a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * enhancements to extend functionality. 265a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 266a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 267a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 268a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Primary state representation, holding four bit-fields: 269a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 270a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * unarrived -- the number of parties yet to hit barrier (bits 0-15) 271a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * parties -- the number of parties to wait (bits 16-31) 272a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phase -- the generation of the barrier (bits 32-62) 273a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * terminated -- set if barrier is terminated (bit 63 / sign) 274a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 275a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Except that a phaser with no registered parties is 276a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * distinguished by the otherwise illegal state of having zero 277a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * parties and one unarrived parties (encoded as EMPTY below). 278a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 279a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * To efficiently maintain atomicity, these values are packed into 280a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * a single (atomic) long. Good performance relies on keeping 281a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * state decoding and encoding simple, and keeping race windows 282a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * short. 283a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 284a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * All state updates are performed via CAS except initial 285a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * registration of a sub-phaser (i.e., one with a non-null 286a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * parent). In this (relatively rare) case, we use built-in 287a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * synchronization to lock while first registering with its 288a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * parent. 289a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 290a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The phase of a subphaser is allowed to lag that of its 291a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * ancestors until it is actually accessed -- see method 292a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * reconcileState. 293a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 294a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private volatile long state; 295a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 296a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int MAX_PARTIES = 0xffff; 297a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int MAX_PHASE = Integer.MAX_VALUE; 298a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int PARTIES_SHIFT = 16; 299a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int PHASE_SHIFT = 32; 300a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int UNARRIVED_MASK = 0xffff; // to mask ints 301a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long PARTIES_MASK = 0xffff0000L; // to mask longs 302a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long COUNTS_MASK = 0xffffffffL; 303a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final long TERMINATION_BIT = 1L << 63; 304a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 305a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // some special values 306a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int ONE_ARRIVAL = 1; 307a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int ONE_PARTY = 1 << PARTIES_SHIFT; 308a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int ONE_DEREGISTER = ONE_ARRIVAL|ONE_PARTY; 309a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int EMPTY = 1; 310a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 311a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // The following unpacking methods are usually manually inlined 312a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 313a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static int unarrivedOf(long s) { 314a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int counts = (int)s; 315a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (counts == EMPTY) ? 0 : (counts & UNARRIVED_MASK); 316a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 317a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 318a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static int partiesOf(long s) { 319a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (int)s >>> PARTIES_SHIFT; 320a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 321a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 322a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static int phaseOf(long s) { 323a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (int)(s >>> PHASE_SHIFT); 324a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 325a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 326a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static int arrivedOf(long s) { 327a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int counts = (int)s; 328a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (counts == EMPTY) ? 0 : 329a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (counts >>> PARTIES_SHIFT) - (counts & UNARRIVED_MASK); 330a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 331a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 332a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 333b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * The parent of this phaser, or null if none. 334a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 335a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private final Phaser parent; 336a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 337a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 338a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The root of phaser tree. Equals this if not in a tree. 339a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 340a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private final Phaser root; 341a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 342a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 343a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Heads of Treiber stacks for waiting threads. To eliminate 344a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * contention when releasing some threads while adding others, we 345a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * use two of them, alternating across even and odd phases. 346a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Subphasers share queues with root to speed up releases. 347a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 348a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private final AtomicReference<QNode> evenQ; 349a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private final AtomicReference<QNode> oddQ; 350a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 351a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private AtomicReference<QNode> queueFor(int phase) { 352a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return ((phase & 1) == 0) ? evenQ : oddQ; 353a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 354a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 355a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 356a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns message string for bounds exceptions on arrival. 357a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 358a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private String badArrive(long s) { 359a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return "Attempted arrival of unregistered party for " + 360a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson stateToString(s); 361a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 362a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 363a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 364a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns message string for bounds exceptions on registration. 365a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 366a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private String badRegister(long s) { 367a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return "Attempt to register more than " + 368a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson MAX_PARTIES + " parties for " + stateToString(s); 369a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 370a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 371a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 372a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Main implementation for methods arrive and arriveAndDeregister. 373a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Manually tuned to speed up and minimize race windows for the 374a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * common case of just decrementing unarrived field. 375a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 376a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param adjust value to subtract from state; 377a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * ONE_ARRIVAL for arrive, 378a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * ONE_DEREGISTER for arriveAndDeregister 379a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 380a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int doArrive(int adjust) { 381a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Phaser root = this.root; 382a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (;;) { 383a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long s = (root == this) ? state : reconcileState(); 384a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int phase = (int)(s >>> PHASE_SHIFT); 385a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (phase < 0) 386a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return phase; 387a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int counts = (int)s; 388a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int unarrived = (counts == EMPTY) ? 0 : (counts & UNARRIVED_MASK); 389a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (unarrived <= 0) 390a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new IllegalStateException(badArrive(s)); 391b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, s-=adjust)) { 392a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (unarrived == 1) { 393a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long n = s & PARTIES_MASK; // base of next state 394a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int nextUnarrived = (int)n >>> PARTIES_SHIFT; 395a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (root == this) { 396a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (onAdvance(phase, nextUnarrived)) 397a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson n |= TERMINATION_BIT; 398a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (nextUnarrived == 0) 399a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson n |= EMPTY; 400a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 401a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson n |= nextUnarrived; 402a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int nextPhase = (phase + 1) & MAX_PHASE; 403a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson n |= (long)nextPhase << PHASE_SHIFT; 404b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.compareAndSwapLong(this, STATE, s, n); 405a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson releaseWaiters(phase); 406a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 407a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (nextUnarrived == 0) { // propagate deregistration 408a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson phase = parent.doArrive(ONE_DEREGISTER); 409b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.compareAndSwapLong(this, STATE, s, s | EMPTY); 410a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 411a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 412a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson phase = parent.doArrive(ONE_ARRIVAL); 413a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 414a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return phase; 415a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 416a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 417a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 418a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 419a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 420b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Implementation of register, bulkRegister. 421a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 422a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param registrations number to add to both parties and 423a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * unarrived fields. Must be greater than zero. 424a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 425a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int doRegister(int registrations) { 426a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // adjustment to state 427a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long adjust = ((long)registrations << PARTIES_SHIFT) | registrations; 428a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Phaser parent = this.parent; 429a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int phase; 430a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (;;) { 431a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long s = (parent == null) ? state : reconcileState(); 432a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int counts = (int)s; 433a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int parties = counts >>> PARTIES_SHIFT; 434a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int unarrived = counts & UNARRIVED_MASK; 435a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (registrations > MAX_PARTIES - parties) 436a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new IllegalStateException(badRegister(s)); 437a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson phase = (int)(s >>> PHASE_SHIFT); 438a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (phase < 0) 439a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 440a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (counts != EMPTY) { // not 1st registration 441a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (parent == null || reconcileState() == s) { 442a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (unarrived == 0) // wait out advance 443a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson root.internalAwaitAdvance(phase, null); 444b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (U.compareAndSwapLong(this, STATE, s, s + adjust)) 445a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 446a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 447a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 448a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (parent == null) { // 1st root registration 449a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long next = ((long)phase << PHASE_SHIFT) | adjust; 450b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, next)) 451a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 452a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 453a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else { 454a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson synchronized (this) { // 1st sub registration 455a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (state == s) { // recheck under lock 456a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson phase = parent.doRegister(1); 457a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (phase < 0) 458a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 459a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // finish registration whenever parent registration 460a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // succeeded, even when racing with termination, 461a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // since these are part of the same "transaction". 462b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak while (!U.compareAndSwapLong 463b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (this, STATE, s, 464a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson ((long)phase << PHASE_SHIFT) | adjust)) { 465a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s = state; 466a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson phase = (int)(root.state >>> PHASE_SHIFT); 467a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert (int)s == EMPTY; 468a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 469a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 470a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 471a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 472a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 473a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 474a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return phase; 475a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 476a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 477a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 478a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Resolves lagged phase propagation from root if necessary. 479a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Reconciliation normally occurs when root has advanced but 480a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * subphasers have not yet done so, in which case they must finish 481a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * their own advance by setting unarrived to parties (or if 482a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * parties is zero, resetting to unregistered EMPTY state). 483a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 484a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return reconciled state 485a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 486a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private long reconcileState() { 487a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Phaser root = this.root; 488a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long s = state; 489a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (root != this) { 490a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int phase, p; 491a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // CAS to root phase with current parties, tripping unarrived 492a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while ((phase = (int)(root.state >>> PHASE_SHIFT)) != 493a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (int)(s >>> PHASE_SHIFT) && 494b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak !U.compareAndSwapLong 495b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (this, STATE, s, 496a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s = (((long)phase << PHASE_SHIFT) | 497a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson ((phase < 0) ? (s & COUNTS_MASK) : 498a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (((p = (int)s >>> PARTIES_SHIFT) == 0) ? EMPTY : 499a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson ((s & PARTIES_MASK) | p)))))) 500a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson s = state; 501a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 502a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return s; 503a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 504a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 505a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 506a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Creates a new phaser with no initially registered parties, no 507a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * parent, and initial phase number 0. Any thread using this 508a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser will need to first register for it. 509a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 510a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public Phaser() { 511a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this(null, 0); 512a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 513a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 514a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 515a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Creates a new phaser with the given number of registered 516a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * unarrived parties, no parent, and initial phase number 0. 517a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 518a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param parties the number of parties required to advance to the 519a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * next phase 520a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws IllegalArgumentException if parties less than zero 521a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * or greater than the maximum number of parties supported 522a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 523a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public Phaser(int parties) { 524a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this(null, parties); 525a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 526a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 527a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 528a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Equivalent to {@link #Phaser(Phaser, int) Phaser(parent, 0)}. 529a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 530a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param parent the parent phaser 531a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 532a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public Phaser(Phaser parent) { 533a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this(parent, 0); 534a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 535a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 536a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 537a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Creates a new phaser with the given parent and number of 538a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * registered unarrived parties. When the given parent is non-null 539a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * and the given number of parties is greater than zero, this 540a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * child phaser is registered with its parent. 541a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 542a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param parent the parent phaser 543a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param parties the number of parties required to advance to the 544a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * next phase 545a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws IllegalArgumentException if parties less than zero 546a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * or greater than the maximum number of parties supported 547a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 548a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public Phaser(Phaser parent, int parties) { 549a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (parties >>> PARTIES_SHIFT != 0) 550a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new IllegalArgumentException("Illegal number of parties"); 551a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int phase = 0; 552a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.parent = parent; 553a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (parent != null) { 554a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Phaser root = parent.root; 555a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.root = root; 556a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.evenQ = root.evenQ; 557a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.oddQ = root.oddQ; 558a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (parties != 0) 559a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson phase = parent.doRegister(1); 560a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 561a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else { 562a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.root = this; 563a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.evenQ = new AtomicReference<QNode>(); 564a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.oddQ = new AtomicReference<QNode>(); 565a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 566a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.state = (parties == 0) ? (long)EMPTY : 567a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson ((long)phase << PHASE_SHIFT) | 568a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson ((long)parties << PARTIES_SHIFT) | 569a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson ((long)parties); 570a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 571a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 572a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 573a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Adds a new unarrived party to this phaser. If an ongoing 574a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * invocation of {@link #onAdvance} is in progress, this method 575a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * may await its completion before returning. If this phaser has 576a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * a parent, and this phaser previously had no registered parties, 577a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this child phaser is also registered with its parent. If 578a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this phaser is terminated, the attempt to register has 579a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * no effect, and a negative value is returned. 580a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 581a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the arrival phase number to which this registration 582a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * applied. If this value is negative, then this phaser has 583a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * terminated, in which case registration has no effect. 584a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws IllegalStateException if attempting to register more 585a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * than the maximum supported number of parties 586a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 587a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int register() { 588a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return doRegister(1); 589a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 590a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 591a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 592a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Adds the given number of new unarrived parties to this phaser. 593a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * If an ongoing invocation of {@link #onAdvance} is in progress, 594a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this method may await its completion before returning. If this 595a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * phaser has a parent, and the given number of parties is greater 596a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * than zero, and this phaser previously had no registered 597a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * parties, this child phaser is also registered with its parent. 598a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * If this phaser is terminated, the attempt to register has no 599a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * effect, and a negative value is returned. 600a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 601a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param parties the number of additional parties required to 602a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * advance to the next phase 603a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the arrival phase number to which this registration 604a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * applied. If this value is negative, then this phaser has 605a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * terminated, in which case registration has no effect. 606a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws IllegalStateException if attempting to register more 607a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * than the maximum supported number of parties 608a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws IllegalArgumentException if {@code parties < 0} 609a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 610a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int bulkRegister(int parties) { 611a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (parties < 0) 612a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new IllegalArgumentException(); 613a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (parties == 0) 614a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return getPhase(); 615a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return doRegister(parties); 616a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 617a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 618a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 619a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Arrives at this phaser, without waiting for others to arrive. 620a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 621a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>It is a usage error for an unregistered party to invoke this 622a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * method. However, this error may result in an {@code 623a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * IllegalStateException} only upon some subsequent operation on 624a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this phaser, if ever. 625a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 626a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the arrival phase number, or a negative value if terminated 627a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws IllegalStateException if not terminated and the number 628a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of unarrived parties would become negative 629a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 630a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int arrive() { 631a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return doArrive(ONE_ARRIVAL); 632a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 633a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 634a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 635a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Arrives at this phaser and deregisters from it without waiting 636a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * for others to arrive. Deregistration reduces the number of 637a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * parties required to advance in future phases. If this phaser 638a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * has a parent, and deregistration causes this phaser to have 639a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * zero parties, this phaser is also deregistered from its parent. 640a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 641a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>It is a usage error for an unregistered party to invoke this 642a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * method. However, this error may result in an {@code 643a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * IllegalStateException} only upon some subsequent operation on 644a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this phaser, if ever. 645a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 646a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the arrival phase number, or a negative value if terminated 647a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws IllegalStateException if not terminated and the number 648a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of registered or unarrived parties would become negative 649a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 650a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int arriveAndDeregister() { 651a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return doArrive(ONE_DEREGISTER); 652a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 653a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 654a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 655a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Arrives at this phaser and awaits others. Equivalent in effect 656a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to {@code awaitAdvance(arrive())}. If you need to await with 657a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * interruption or timeout, you can arrange this with an analogous 658a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * construction using one of the other forms of the {@code 659a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * awaitAdvance} method. If instead you need to deregister upon 660a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * arrival, use {@code awaitAdvance(arriveAndDeregister())}. 661a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 662a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>It is a usage error for an unregistered party to invoke this 663a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * method. However, this error may result in an {@code 664a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * IllegalStateException} only upon some subsequent operation on 665a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this phaser, if ever. 666a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 667a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the arrival phase number, or the (negative) 668a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@linkplain #getPhase() current phase} if terminated 669a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws IllegalStateException if not terminated and the number 670a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of unarrived parties would become negative 671a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 672a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int arriveAndAwaitAdvance() { 673a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Specialization of doArrive+awaitAdvance eliminating some reads/paths 674a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Phaser root = this.root; 675a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (;;) { 676a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long s = (root == this) ? state : reconcileState(); 677a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int phase = (int)(s >>> PHASE_SHIFT); 678a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (phase < 0) 679a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return phase; 680a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int counts = (int)s; 681a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int unarrived = (counts == EMPTY) ? 0 : (counts & UNARRIVED_MASK); 682a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (unarrived <= 0) 683a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new IllegalStateException(badArrive(s)); 684b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, s -= ONE_ARRIVAL)) { 685a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (unarrived > 1) 686a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return root.internalAwaitAdvance(phase, null); 687a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (root != this) 688a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return parent.arriveAndAwaitAdvance(); 689a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long n = s & PARTIES_MASK; // base of next state 690a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int nextUnarrived = (int)n >>> PARTIES_SHIFT; 691a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (onAdvance(phase, nextUnarrived)) 692a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson n |= TERMINATION_BIT; 693a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (nextUnarrived == 0) 694a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson n |= EMPTY; 695a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else 696a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson n |= nextUnarrived; 697a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int nextPhase = (phase + 1) & MAX_PHASE; 698a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson n |= (long)nextPhase << PHASE_SHIFT; 699b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (!U.compareAndSwapLong(this, STATE, s, n)) 700a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (int)(state >>> PHASE_SHIFT); // terminated 701a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson releaseWaiters(phase); 702a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return nextPhase; 703a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 704a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 705a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 706a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 707a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 708a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Awaits the phase of this phaser to advance from the given phase 709a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * value, returning immediately if the current phase is not equal 710a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * to the given phase value or this phaser is terminated. 711a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 712a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param phase an arrival phase number, or negative value if 713a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * terminated; this argument is normally the value returned by a 714a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * previous call to {@code arrive} or {@code arriveAndDeregister}. 715a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the next arrival phase number, or the argument if it is 716a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * negative, or the (negative) {@linkplain #getPhase() current phase} 717a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if terminated 718a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 719a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int awaitAdvance(int phase) { 720a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Phaser root = this.root; 721a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long s = (root == this) ? state : reconcileState(); 722a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int p = (int)(s >>> PHASE_SHIFT); 723a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (phase < 0) 724a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return phase; 725a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p == phase) 726a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return root.internalAwaitAdvance(phase, null); 727a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return p; 728a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 729a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 730a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 731a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Awaits the phase of this phaser to advance from the given phase 732a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * value, throwing {@code InterruptedException} if interrupted 733a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * while waiting, or returning immediately if the current phase is 734a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * not equal to the given phase value or this phaser is 735a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * terminated. 736a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 737a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param phase an arrival phase number, or negative value if 738a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * terminated; this argument is normally the value returned by a 739a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * previous call to {@code arrive} or {@code arriveAndDeregister}. 740a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the next arrival phase number, or the argument if it is 741a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * negative, or the (negative) {@linkplain #getPhase() current phase} 742a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if terminated 743a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws InterruptedException if thread interrupted while waiting 744a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 745a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int awaitAdvanceInterruptibly(int phase) 746a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throws InterruptedException { 747a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Phaser root = this.root; 748a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long s = (root == this) ? state : reconcileState(); 749a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int p = (int)(s >>> PHASE_SHIFT); 750a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (phase < 0) 751a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return phase; 752a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p == phase) { 753a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson QNode node = new QNode(this, phase, true, false, 0L); 754a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = root.internalAwaitAdvance(phase, node); 755a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (node.wasInterrupted) 756a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new InterruptedException(); 757a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 758a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return p; 759a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 760a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 761a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 762a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Awaits the phase of this phaser to advance from the given phase 763a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * value or the given timeout to elapse, throwing {@code 764a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * InterruptedException} if interrupted while waiting, or 765a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * returning immediately if the current phase is not equal to the 766a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * given phase value or this phaser is terminated. 767a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 768a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param phase an arrival phase number, or negative value if 769a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * terminated; this argument is normally the value returned by a 770a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * previous call to {@code arrive} or {@code arriveAndDeregister}. 771a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param timeout how long to wait before giving up, in units of 772a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code unit} 773a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param unit a {@code TimeUnit} determining how to interpret the 774a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code timeout} parameter 775a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the next arrival phase number, or the argument if it is 776a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * negative, or the (negative) {@linkplain #getPhase() current phase} 777a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if terminated 778a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws InterruptedException if thread interrupted while waiting 779a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @throws TimeoutException if timed out while waiting 780a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 781a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int awaitAdvanceInterruptibly(int phase, 782a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long timeout, TimeUnit unit) 783a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throws InterruptedException, TimeoutException { 784a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long nanos = unit.toNanos(timeout); 785a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Phaser root = this.root; 786a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long s = (root == this) ? state : reconcileState(); 787a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int p = (int)(s >>> PHASE_SHIFT); 788a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (phase < 0) 789a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return phase; 790a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p == phase) { 791a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson QNode node = new QNode(this, phase, true, true, nanos); 792a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson p = root.internalAwaitAdvance(phase, node); 793a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (node.wasInterrupted) 794a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new InterruptedException(); 795a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (p == phase) 796a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new TimeoutException(); 797a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 798a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return p; 799a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 800a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 801a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 802a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Forces this phaser to enter termination state. Counts of 803a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * registered parties are unaffected. If this phaser is a member 804a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * of a tiered set of phasers, then all of the phasers in the set 805a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * are terminated. If this phaser is already terminated, this 806a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * method has no effect. This method may be useful for 807a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * coordinating recovery after one or more tasks encounter 808a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * unexpected exceptions. 809a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 810a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public void forceTermination() { 811a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Only need to change root state 812a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Phaser root = this.root; 813a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long s; 814a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while ((s = root.state) >= 0) { 815b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (U.compareAndSwapLong(root, STATE, s, s | TERMINATION_BIT)) { 816a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // signal all threads 817a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson releaseWaiters(0); // Waiters on evenQ 818a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson releaseWaiters(1); // Waiters on oddQ 819a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return; 820a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 821a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 822a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 823a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 824a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 825a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns the current phase number. The maximum phase number is 826a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code Integer.MAX_VALUE}, after which it restarts at 827a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * zero. Upon termination, the phase number is negative, 828a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * in which case the prevailing phase prior to termination 829a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * may be obtained via {@code getPhase() + Integer.MIN_VALUE}. 830a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 831a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the phase number, or a negative value if terminated 832a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 833a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public final int getPhase() { 834a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (int)(root.state >>> PHASE_SHIFT); 835a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 836a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 837a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 838a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns the number of parties registered at this phaser. 839a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 840a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the number of parties 841a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 842a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int getRegisteredParties() { 843a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return partiesOf(state); 844a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 845a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 846a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 847a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns the number of registered parties that have arrived at 848a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the current phase of this phaser. If this phaser has terminated, 849a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * the returned value is meaningless and arbitrary. 850a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 851a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the number of arrived parties 852a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 853a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int getArrivedParties() { 854a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return arrivedOf(reconcileState()); 855a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 856a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 857a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 858a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns the number of registered parties that have not yet 859a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * arrived at the current phase of this phaser. If this phaser has 860a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * terminated, the returned value is meaningless and arbitrary. 861a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 862a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the number of unarrived parties 863a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 864a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public int getUnarrivedParties() { 865a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return unarrivedOf(reconcileState()); 866a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 867a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 868a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 869a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns the parent of this phaser, or {@code null} if none. 870a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 871a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the parent of this phaser, or {@code null} if none 872a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 873a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public Phaser getParent() { 874a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return parent; 875a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 876a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 877a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 878a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns the root ancestor of this phaser, which is the same as 879a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this phaser if it has no parent. 880a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 881a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return the root ancestor of this phaser 882a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 883a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public Phaser getRoot() { 884a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return root; 885a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 886a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 887a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 888a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns {@code true} if this phaser has been terminated. 889a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 890a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return {@code true} if this phaser has been terminated 891a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 892a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean isTerminated() { 893a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return root.state < 0L; 894a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 895a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 896a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 897a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Overridable method to perform an action upon impending phase 898a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * advance, and to control termination. This method is invoked 899a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * upon arrival of the party advancing this phaser (when all other 900a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * waiting parties are dormant). If this method returns {@code 901a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * true}, this phaser will be set to a final termination state 902a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * upon advance, and subsequent calls to {@link #isTerminated} 903a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * will return true. Any (unchecked) Exception or Error thrown by 904a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * an invocation of this method is propagated to the party 905a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * attempting to advance this phaser, in which case no advance 906a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * occurs. 907a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 908a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>The arguments to this method provide the state of the phaser 909a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * prevailing for the current transition. The effects of invoking 910a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * arrival, registration, and waiting methods on this phaser from 911a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * within {@code onAdvance} are unspecified and should not be 912a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * relied on. 913a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 914a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>If this phaser is a member of a tiered set of phasers, then 915a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code onAdvance} is invoked only for its root phaser on each 916a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * advance. 917a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 918a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <p>To support the most common use cases, the default 919a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * implementation of this method returns {@code true} when the 920a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * number of registered parties has become zero as the result of a 921a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * party invoking {@code arriveAndDeregister}. You can disable 922a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * this behavior, thus enabling continuation upon future 923a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * registrations, by overriding this method to always return 924a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@code false}: 925a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 926a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <pre> {@code 927a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Phaser phaser = new Phaser() { 928a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * protected boolean onAdvance(int phase, int parties) { return false; } 929a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }}</pre> 930a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 931a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param phase the current phase number on entry to this method, 932a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * before this phaser is advanced 933a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param registeredParties the current number of registered parties 934a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return {@code true} if this phaser should terminate 935a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 936a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson protected boolean onAdvance(int phase, int registeredParties) { 937a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return registeredParties == 0; 938a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 939a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 940a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 941a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Returns a string identifying this phaser, as well as its 942a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * state. The state, in brackets, includes the String {@code 943a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * "phase = "} followed by the phase number, {@code "parties = "} 944a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * followed by the number of registered parties, and {@code 945a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * "arrived = "} followed by the number of arrived parties. 946a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 947a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return a string identifying this phaser, as well as its state 948a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 949a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public String toString() { 950a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return stateToString(reconcileState()); 951a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 952a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 953a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 954b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Implementation of toString and string-based error messages. 955a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 956a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private String stateToString(long s) { 957a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return super.toString() + 958a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson "[phase = " + phaseOf(s) + 959a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson " parties = " + partiesOf(s) + 960a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson " arrived = " + arrivedOf(s) + "]"; 961a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 962a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 963a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Waiting mechanics 964a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 965a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 966a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Removes and signals threads from queue for phase. 967a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 968a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void releaseWaiters(int phase) { 969a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson QNode q; // first element of queue 970a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Thread t; // its thread 971a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson AtomicReference<QNode> head = (phase & 1) == 0 ? evenQ : oddQ; 972a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while ((q = head.get()) != null && 973a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson q.phase != (int)(root.state >>> PHASE_SHIFT)) { 974a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (head.compareAndSet(q, q.next) && 975a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (t = q.thread) != null) { 976a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson q.thread = null; 977a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson LockSupport.unpark(t); 978a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 979a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 980a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 981a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 982a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 983a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Variant of releaseWaiters that additionally tries to remove any 984a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * nodes no longer waiting for advance due to timeout or 985a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * interrupt. Currently, nodes are removed only if they are at 986a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * head of queue, which suffices to reduce memory footprint in 987a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * most usages. 988a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 989a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return current phase on exit 990a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 991a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int abortWait(int phase) { 992a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson AtomicReference<QNode> head = (phase & 1) == 0 ? evenQ : oddQ; 993a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (;;) { 994a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Thread t; 995a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson QNode q = head.get(); 996a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int p = (int)(root.state >>> PHASE_SHIFT); 997a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (q == null || ((t = q.thread) != null && q.phase == p)) 998a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return p; 999a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (head.compareAndSet(q, q.next) && t != null) { 1000a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson q.thread = null; 1001a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson LockSupport.unpark(t); 1002a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1003a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1004a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1005a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1006a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** The number of CPUs, for spin control */ 1007a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final int NCPU = Runtime.getRuntime().availableProcessors(); 1008a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1009a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1010a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * The number of times to spin before blocking while waiting for 1011a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * advance, per arrival while waiting. On multiprocessors, fully 1012a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * blocking and waking up a large number of threads all at once is 1013a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * usually a very slow process, so we use rechargeable spins to 1014a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * avoid it when threads regularly arrive: When a thread in 1015a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * internalAwaitAdvance notices another arrival before blocking, 1016a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * and there appear to be enough CPUs available, it spins 1017a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * SPINS_PER_ARRIVAL more times before blocking. The value trades 1018a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * off good-citizenship vs big unnecessary slowdowns. 1019a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1020a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static final int SPINS_PER_ARRIVAL = (NCPU < 2) ? 1 : 1 << 8; 1021a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1022a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1023a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Possibly blocks and waits for phase to advance unless aborted. 1024a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Call only on root phaser. 1025a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 1026a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param phase current phase 1027a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @param node if non-null, the wait node to track interrupt and timeout; 1028a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * if null, denotes noninterruptible wait 1029a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * @return current phase 1030a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1031a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private int internalAwaitAdvance(int phase, QNode node) { 1032a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // assert root == this; 1033a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson releaseWaiters(phase-1); // ensure old queue clean 1034a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean queued = false; // true when node is enqueued 1035a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int lastUnarrived = 0; // to increase spins upon change 1036a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int spins = SPINS_PER_ARRIVAL; 1037a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long s; 1038a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int p; 1039a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while ((p = (int)((s = state) >>> PHASE_SHIFT)) == phase) { 1040a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (node == null) { // spinning in noninterruptible mode 1041a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int unarrived = (int)s & UNARRIVED_MASK; 1042a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (unarrived != lastUnarrived && 1043a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (lastUnarrived = unarrived) < NCPU) 1044a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson spins += SPINS_PER_ARRIVAL; 1045a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean interrupted = Thread.interrupted(); 1046a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (interrupted || --spins < 0) { // need node to record intr 1047a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson node = new QNode(this, phase, false, false, 0L); 1048a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson node.wasInterrupted = interrupted; 1049a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1050a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1051a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (node.isReleasable()) // done or aborted 1052a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson break; 1053a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else if (!queued) { // push onto queue 1054a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson AtomicReference<QNode> head = (phase & 1) == 0 ? evenQ : oddQ; 1055a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson QNode q = node.next = head.get(); 1056a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if ((q == null || q.phase == phase) && 1057a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson (int)(state >>> PHASE_SHIFT) == phase) // avoid stale enq 1058a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson queued = head.compareAndSet(q, node); 1059a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1060a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson else { 1061a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson try { 1062a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson ForkJoinPool.managedBlock(node); 1063b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (InterruptedException cantHappen) { 1064a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson node.wasInterrupted = true; 1065a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1066a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1067a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1068a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1069a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (node != null) { 1070a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (node.thread != null) 1071a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson node.thread = null; // avoid need for unpark() 1072a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (node.wasInterrupted && !node.interruptible) 1073a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Thread.currentThread().interrupt(); 1074a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (p == phase && (p = (int)(state >>> PHASE_SHIFT)) == phase) 1075a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return abortWait(phase); // possibly clean up on abort 1076a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1077a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson releaseWaiters(phase); 1078a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return p; 1079a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1080a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1081a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson /** 1082b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Wait nodes for Treiber stack representing wait queue. 1083a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson */ 1084a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static final class QNode implements ForkJoinPool.ManagedBlocker { 1085a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Phaser phaser; 1086a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final int phase; 1087a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final boolean interruptible; 1088a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final boolean timed; 1089a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean wasInterrupted; 1090a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson long nanos; 109191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle final long deadline; 1092a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson volatile Thread thread; // nulled to cancel wait 1093a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson QNode next; 1094a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1095a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson QNode(Phaser phaser, int phase, boolean interruptible, 1096a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson boolean timed, long nanos) { 1097a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.phaser = phaser; 1098a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.phase = phase; 1099a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.interruptible = interruptible; 1100a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.nanos = nanos; 1101a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson this.timed = timed; 110291770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle this.deadline = timed ? System.nanoTime() + nanos : 0L; 1103a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson thread = Thread.currentThread(); 1104a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1105a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1106a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean isReleasable() { 1107a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (thread == null) 1108a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1109a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (phaser.getPhase() != phase) { 1110a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson thread = null; 1111a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1112a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1113a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (Thread.interrupted()) 1114a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson wasInterrupted = true; 1115a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (wasInterrupted && interruptible) { 1116a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson thread = null; 1117a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 1118a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1119b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (timed && 1120b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (nanos <= 0L || (nanos = deadline - System.nanoTime()) <= 0L)) { 1121b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak thread = null; 1122b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return true; 1123a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1124a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 1125a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1126a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1127a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson public boolean block() { 1128b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak while (!isReleasable()) { 1129b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (timed) 1130b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak LockSupport.parkNanos(this, nanos); 1131b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else 1132b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak LockSupport.park(this); 1133b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1134b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return true; 1135a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1136a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1137a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1138a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Unsafe mechanics 1139a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 1140b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 1141b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long STATE; 1142a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static { 1143a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson try { 1144b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak STATE = U.objectFieldOffset 1145b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Phaser.class.getDeclaredField("state")); 1146b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (ReflectiveOperationException e) { 1147a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new Error(e); 1148a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1149edf43d27e240d82106f39ae91404963c23987234Narayan Kamath 1150edf43d27e240d82106f39ae91404963c23987234Narayan Kamath // Reduce the risk of rare disastrous classloading in first call to 1151edf43d27e240d82106f39ae91404963c23987234Narayan Kamath // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773 1152edf43d27e240d82106f39ae91404963c23987234Narayan Kamath Class<?> ensureLoaded = LockSupport.class; 1153a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson } 1154a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson} 1155