1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Written by Doug Lea with assistance from members of JCP JSR-166 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Expert Group and released to the public domain, as explained at 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://creativecommons.org/licenses/publicdomain 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage java.util.concurrent.locks; 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.*; 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.concurrent.*; 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.concurrent.atomic.*; 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport sun.misc.Unsafe; 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Provides a framework for implementing blocking locks and related 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * synchronizers (semaphores, events, etc) that rely on 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * first-in-first-out (FIFO) wait queues. This class is designed to 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * be a useful basis for most kinds of synchronizers that rely on a 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * single atomic <tt>int</tt> value to represent state. Subclasses 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * must define the protected methods that change this state, and which 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * define what that state means in terms of this object being acquired 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * or released. Given these, the other methods in this class carry 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * out all queuing and blocking mechanics. Subclasses can maintain 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * other state fields, but only the atomically updated <tt>int</tt> 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * value manipulated using methods {@link #getState}, {@link 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * #setState} and {@link #compareAndSetState} is tracked with respect 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to synchronization. 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>Subclasses should be defined as non-public internal helper 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * classes that are used to implement the synchronization properties 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * of their enclosing class. Class 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <tt>AbstractQueuedSynchronizer</tt> does not implement any 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * synchronization interface. Instead it defines methods such as 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link #acquireInterruptibly} that can be invoked as 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * appropriate by concrete locks and related synchronizers to 358210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * implement their public methods. 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>This class supports either or both a default <em>exclusive</em> 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * mode and a <em>shared</em> mode. When acquired in exclusive mode, 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * attempted acquires by other threads cannot succeed. Shared mode 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * acquires by multiple threads may (but need not) succeed. This class 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * does not "understand" these differences except in the 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * mechanical sense that when a shared mode acquire succeeds, the next 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * waiting thread (if one exists) must also determine whether it can 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * acquire as well. Threads waiting in the different modes share the 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * same FIFO queue. Usually, implementation subclasses support only 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * one of these modes, but both can come into play for example in a 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link ReadWriteLock}. Subclasses that support only exclusive or 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * only shared modes need not define the methods supporting the unused mode. 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>This class defines a nested {@link ConditionObject} class that 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * can be used as a {@link Condition} implementation by subclasses 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * supporting exclusive mode for which method {@link 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * #isHeldExclusively} reports whether synchronization is exclusively 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * held with respect to the current thread, method {@link #release} 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * invoked with the current {@link #getState} value fully releases 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * this object, and {@link #acquire}, given this saved state value, 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * eventually restores this object to its previous acquired state. No 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <tt>AbstractQueuedSynchronizer</tt> method otherwise creates such a 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * condition, so if this constraint cannot be met, do not use it. The 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * behavior of {@link ConditionObject} depends of course on the 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * semantics of its synchronizer implementation. 628210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 638210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>This class provides inspection, instrumentation, and monitoring 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * methods for the internal queue, as well as similar methods for 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * condition objects. These can be exported as desired into classes 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * using an <tt>AbstractQueuedSynchronizer</tt> for their 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * synchronization mechanics. 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>Serialization of this class stores only the underlying atomic 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * integer maintaining state, so deserialized objects have empty 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * thread queues. Typical subclasses requiring serializability will 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * define a <tt>readObject</tt> method that restores this to a known 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * initial state upon deserialization. 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <h3>Usage</h3> 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 778210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>To use this class as the basis of a synchronizer, redefine the 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * following methods, as applicable, by inspecting and/or modifying 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the synchronization state using {@link #getState}, {@link 808210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * #setState} and/or {@link #compareAndSetState}: 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <ul> 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li> {@link #tryAcquire} 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li> {@link #tryRelease} 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li> {@link #tryAcquireShared} 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li> {@link #tryReleaseShared} 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li> {@link #isHeldExclusively} 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project *</ul> 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Each of these methods by default throws {@link 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * UnsupportedOperationException}. Implementations of these methods 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * must be internally thread-safe, and should in general be short and 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * not block. Defining these methods is the <em>only</em> supported 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * means of using this class. All other methods are declared 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <tt>final</tt> because they cannot be independently varied. 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 978210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>Even though this class is based on an internal FIFO queue, it 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * does not automatically enforce FIFO acquisition policies. The core 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * of exclusive synchronization takes the form: 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <pre> 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Acquire: 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * while (!tryAcquire(arg)) { 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <em>enqueue thread if it is not already queued</em>; 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <em>possibly block current thread</em>; 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * } 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Release: 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * if (tryRelease(arg)) 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <em>unblock the first queued thread</em>; 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * </pre> 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (Shared mode is similar but may involve cascading signals.) 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1158210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p><a name="barging">Because checks in acquire are invoked before 1168210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * enqueuing, a newly acquiring thread may <em>barge</em> ahead of 1178210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * others that are blocked and queued. However, you can, if desired, 1188210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * define <tt>tryAcquire</tt> and/or <tt>tryAcquireShared</tt> to 1198210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * disable barging by internally invoking one or more of the inspection 1208210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * methods, thereby providing a <em>fair</em> FIFO acquisition order. 1218210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * In particular, most fair synchronizers can define <tt>tryAcquire</tt> 1228210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * to return <tt>false</tt> if predecessors are queued. Other variations 1238210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * are possible. 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1258210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>Throughput and scalability are generally highest for the 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * default barging (also known as <em>greedy</em>, 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <em>renouncement</em>, and <em>convoy-avoidance</em>) strategy. 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * While this is not guaranteed to be fair or starvation-free, earlier 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * queued threads are allowed to recontend before later queued 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * threads, and each recontention has an unbiased chance to succeed 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * against incoming threads. Also, while acquires do not 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * "spin" in the usual sense, they may perform multiple 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * invocations of <tt>tryAcquire</tt> interspersed with other 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * computations before blocking. This gives most of the benefits of 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * spins when exclusive synchronization is only briefly held, without 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * most of the liabilities when it isn't. If so desired, you can 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * augment this by preceding calls to acquire methods with 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * "fast-path" checks, possibly prechecking {@link #hasContended} 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and/or {@link #hasQueuedThreads} to only do so if the synchronizer 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is likely not to be contended. 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1428210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>This class provides an efficient and scalable basis for 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * synchronization in part by specializing its range of use to 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * synchronizers that can rely on <tt>int</tt> state, acquire, and 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * release parameters, and an internal FIFO wait queue. When this does 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * not suffice, you can build synchronizers from a lower level using 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link java.util.concurrent.atomic atomic} classes, your own custom 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link java.util.Queue} classes, and {@link LockSupport} blocking 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * support. 1508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <h3>Usage Examples</h3> 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>Here is a non-reentrant mutual exclusion lock class that uses 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the value zero to represent the unlocked state, and one to 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * represent the locked state. It also supports conditions and exposes 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * one of the instrumentation methods: 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <pre> 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * class Mutex implements Lock, java.io.Serializable { 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1618210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * // Our internal helper class 1628210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * private static class Sync extends AbstractQueuedSynchronizer { 1638210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * // Report whether in locked state 1648210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * protected boolean isHeldExclusively() { 1658210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * return getState() == 1; 1668210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * // Acquire the lock if state is zero 1698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public boolean tryAcquire(int acquires) { 1708210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * assert acquires == 1; // Otherwise unused 1718210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * return compareAndSetState(0, 1); 1728210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1748210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * // Release the lock by setting state to zero 1758210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * protected boolean tryRelease(int releases) { 1768210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * assert releases == 1; // Otherwise unused 1778210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * if (getState() == 0) throw new IllegalMonitorStateException(); 1788210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * setState(0); 1798210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * return true; 1808210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 1818210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1828210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * // Provide a Condition 1838210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Condition newCondition() { return new ConditionObject(); } 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1858210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * // Deserialize properly 1868210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * private void readObject(ObjectInputStream s) 1878210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * throws IOException, ClassNotFoundException { 1888210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * s.defaultReadObject(); 1898210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * setState(0); // reset to unlocked state 1908210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 1918210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1938210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * // The sync object does all the hard work. We just forward to it. 1948210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * private final Sync sync = new Sync(); 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1968210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public void lock() { sync.acquire(1); } 1978210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public boolean tryLock() { return sync.tryAcquire(1); } 1988210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public void unlock() { sync.release(1); } 1998210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public Condition newCondition() { return sync.newCondition(); } 2008210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public boolean isLocked() { return sync.isHeldExclusively(); } 2018210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public boolean hasQueuedThreads() { return sync.hasQueuedThreads(); } 2028210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public void lockInterruptibly() throws InterruptedException { 2038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * sync.acquireInterruptibly(1); 2048210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 2058210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public boolean tryLock(long timeout, TimeUnit unit) 2068210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * throws InterruptedException { 2078210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * return sync.tryAcquireNanos(1, unit.toNanos(timeout)); 2088210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * } 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * </pre> 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2128210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>Here is a latch class that is like a {@link CountDownLatch} 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * except that it only requires a single <tt>signal</tt> to 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * fire. Because a latch is non-exclusive, it uses the <tt>shared</tt> 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * acquire and release methods. 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <pre> 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * class BooleanLatch { 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2208210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * private static class Sync extends AbstractQueuedSynchronizer { 2218210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * boolean isSignalled() { return getState() != 0; } 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2238210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * protected int tryAcquireShared(int ignore) { 2248210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * return isSignalled()? 1 : -1; 2258210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2278210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * protected boolean tryReleaseShared(int ignore) { 2288210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * setState(1); 2298210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * return true; 2308210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 2318210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2338210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * private final Sync sync = new Sync(); 2348210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public boolean isSignalled() { return sync.isSignalled(); } 2358210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public void signal() { sync.releaseShared(1); } 2368210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * public void await() throws InterruptedException { 2378210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * sync.acquireSharedInterruptibly(1); 2388210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 2398210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * </pre> 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @since 1.5 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @author Doug Lea 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 2458210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilsonpublic abstract class AbstractQueuedSynchronizer 2468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson extends AbstractOwnableSynchronizer 2478210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson implements java.io.Serializable { 2488210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final long serialVersionUID = 7373984972572414691L; 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Creates a new <tt>AbstractQueuedSynchronizer</tt> instance 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * with initial synchronization state of zero. 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected AbstractQueuedSynchronizer() { } 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Wait queue node class. 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2608210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>The wait queue is a variant of a "CLH" (Craig, Landin, and 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Hagersten) lock queue. CLH locks are normally used for 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * spinlocks. We instead use them for blocking synchronizers, but 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * use the same basic tactic of holding some of the control 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * information about a thread in the predecessor of its node. A 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * "status" field in each node keeps track of whether a thread 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * should block. A node is signalled when its predecessor 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * releases. Each node of the queue otherwise serves as a 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * specific-notification-style monitor holding a single waiting 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * thread. The status field does NOT control whether threads are 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * granted locks etc though. A thread may try to acquire if it is 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * first in the queue. But being first does not guarantee success; 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * it only gives the right to contend. So the currently released 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * contender thread may need to rewait. 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>To enqueue into a CLH lock, you atomically splice it in as new 2768210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * tail. To dequeue, you just set the head field. 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <pre> 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * +------+ prev +-----+ +-----+ 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * head | | <---- | | <---- | | tail 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * +------+ +-----+ +-----+ 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * </pre> 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>Insertion into a CLH queue requires only a single atomic 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * operation on "tail", so there is a simple atomic point of 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * demarcation from unqueued to queued. Similarly, dequeing 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * involves only updating the "head". However, it takes a bit 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * more work for nodes to determine who their successors are, 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in part to deal with possible cancellation due to timeouts 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and interrupts. 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>The "prev" links (not used in original CLH locks), are mainly 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * needed to handle cancellation. If a node is cancelled, its 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * successor is (normally) relinked to a non-cancelled 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * predecessor. For explanation of similar mechanics in the case 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * of spin locks, see the papers by Scott and Scherer at 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.cs.rochester.edu/u/scott/synchronization/ 2978210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>We also use "next" links to implement blocking mechanics. 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The thread id for each node is kept in its own node, so a 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * predecessor signals the next node to wake up by traversing 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * next link to determine which thread it is. Determination of 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * successor must avoid races with newly queued nodes to set 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the "next" fields of their predecessors. This is solved 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * when necessary by checking backwards from the atomically 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * updated "tail" when a node's successor appears to be null. 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (Or, said differently, the next-links are an optimization 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * so that we don't usually need a backward scan.) 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>Cancellation introduces some conservatism to the basic 310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * algorithms. Since we must poll for cancellation of other 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * nodes, we can miss noticing whether a cancelled node is 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * ahead or behind us. This is dealt with by always unparking 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * successors upon cancellation, allowing them to stabilize on 3148210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * a new predecessor, unless we can identify an uncancelled 3158210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * predecessor who will carry this responsibility. 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>CLH queues need a dummy header node to get started. But 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * we don't create them on construction, because it would be wasted 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * effort if there is never contention. Instead, the node 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is constructed and head and tail pointers are set upon first 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * contention. 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>Threads waiting on Conditions use the same nodes, but 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * use an additional link. Conditions only need to link nodes 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * in simple (non-concurrent) linked queues because they are 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * only accessed when exclusively held. Upon await, a node is 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * inserted into a condition queue. Upon signal, the node is 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * transferred to the main queue. A special value of status 329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * field is used to mark which queue a node is on. 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Scherer and Michael Scott, along with members of JSR-166 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * expert group, for helpful ideas, discussions, and critiques 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * on the design of this class. 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project static final class Node { 3378210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** Marker to indicate a node is waiting in shared mode */ 3388210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson static final Node SHARED = new Node(); 3398210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** Marker to indicate a node is waiting in exclusive mode */ 3408210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson static final Node EXCLUSIVE = null; 3418210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** waitStatus value to indicate thread has cancelled */ 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project static final int CANCELLED = 1; 3448210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** waitStatus value to indicate successor's thread needs unparking */ 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project static final int SIGNAL = -1; 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** waitStatus value to indicate thread is waiting on condition */ 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project static final int CONDITION = -2; 3488210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 3498210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * waitStatus value to indicate the next acquireShared should 3508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * unconditionally propagate 3518210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 3528210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson static final int PROPAGATE = -3; 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Status field, taking on only the values: 3568210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * SIGNAL: The successor of this node is (or will soon be) 3578210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * blocked (via park), so the current node must 3588210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * unpark its successor when it releases or 359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * cancels. To avoid races, acquire methods must 3608210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * first indicate they need a signal, 3618210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * then retry the atomic acquire, and then, 362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * on failure, block. 3638210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * CANCELLED: This node is cancelled due to timeout or interrupt. 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Nodes never leave this state. In particular, 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a thread with cancelled node never again blocks. 3668210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * CONDITION: This node is currently on a condition queue. 3678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * It will not be used as a sync queue node 3688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * until transferred, at which time the status 3698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * will be set to 0. (Use of this value here has 3708210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * nothing to do with the other uses of the 3718210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * field, but simplifies mechanics.) 3728210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * PROPAGATE: A releaseShared should be propagated to other 3738210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * nodes. This is set (for head node only) in 3748210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * doReleaseShared to ensure propagation 3758210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * continues, even if other operations have 3768210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * since intervened. 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 0: None of the above 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The values are arranged numerically to simplify use. 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Non-negative values mean that a node doesn't need to 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * signal. So, most code doesn't need to check for particular 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * values, just for sign. 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The field is initialized to 0 for normal sync nodes, and 3858210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * CONDITION for condition nodes. It is modified using CAS 3868210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * (or when possible, unconditional volatile writes). 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project volatile int waitStatus; 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Link to predecessor node that current node/thread relies on 392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * for checking waitStatus. Assigned during enqueing, and nulled 393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * out (for sake of GC) only upon dequeuing. Also, upon 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * cancellation of a predecessor, we short-circuit while 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * finding a non-cancelled one, which will always exist 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * because the head node is never cancelled: A node becomes 397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * head only as a result of successful acquire. A 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * cancelled thread never succeeds in acquiring, and a thread only 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * cancels itself, not any other node. 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project volatile Node prev; 402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Link to the successor node that the current node/thread 4058210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * unparks upon release. Assigned during enqueuing, adjusted 4068210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * when bypassing cancelled predecessors, and nulled out (for 4078210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * sake of GC) when dequeued. The enq operation does not 4088210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * assign next field of a predecessor until after attachment, 4098210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * so seeing a null next field does not necessarily mean that 4108210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * node is at end of queue. However, if a next field appears 4118210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * to be null, we can scan prev's from the tail to 4128210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * double-check. The next field of cancelled nodes is set to 4138210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * point to the node itself instead of null, to make life 4148210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * easier for isOnSyncQueue. 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project volatile Node next; 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The thread that enqueued this node. Initialized on 4208210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * construction and nulled out after use. 421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project volatile Thread thread; 423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 4248210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Link to next node waiting on condition, or the special 426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * value SHARED. Because condition queues are accessed only 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * when holding in exclusive mode, we just need a simple 428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * linked queue to hold nodes while they are waiting on 429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * conditions. They are then transferred to the queue to 430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * re-acquire. And because conditions can only be exclusive, 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * we save a field by using special value to indicate shared 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * mode. 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node nextWaiter; 435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns true if node is waiting in shared mode 438f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final boolean isShared() { 440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return nextWaiter == SHARED; 441f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 442f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 443f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 4448210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Returns previous node, or throws NullPointerException if null. 4458210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Use when predecessor cannot be null. The null check could 4468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * be elided, but is present to help the VM. 4478210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the predecessor of this node 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node predecessor() throws NullPointerException { 451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node p = prev; 452f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (p == null) 4538210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson throw new NullPointerException(); 454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project else 455f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return p; 456f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 457f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 458f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node() { // Used to establish initial head or SHARED marker 459f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 460f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 461f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node(Thread thread, Node mode) { // Used by addWaiter 462f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.nextWaiter = mode; 463f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.thread = thread; 464f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 465f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 466f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node(Thread thread, int waitStatus) { // Used by Condition 467f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.waitStatus = waitStatus; 4688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson this.thread = thread; 469f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 4728210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 473f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Head of the wait queue, lazily initialized. Except for 474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * initialization, it is modified only via method setHead. Note: 475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If head exists, its waitStatus is guaranteed not to be 476f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * CANCELLED. 477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private transient volatile Node head; 479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 4808210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Tail of the wait queue, lazily initialized. Modified only via 482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * method enq to add new wait node. 483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 4848210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private transient volatile Node tail; 485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The synchronization state. 488f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 489f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private volatile int state; 490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 491f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 492f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the current value of synchronization state. 493f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This operation has memory semantics of a <tt>volatile</tt> read. 494f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return current state value 495f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 496f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected final int getState() { 497f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return state; 498f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 500f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 501f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sets the value of synchronization state. 502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This operation has memory semantics of a <tt>volatile</tt> write. 503f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param newState the new state value 504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 505f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected final void setState(int newState) { 506f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project state = newState; 507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 508f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 509f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 510f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Atomically sets synchronization state to the given updated 511f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * value if the current state value equals the expected value. 512f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This operation has memory semantics of a <tt>volatile</tt> read 513f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and write. 5148210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 515f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param expect the expected value 516f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param update the new value 5178210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return true if successful. False return indicates that the actual 5188210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * value was not equal to the expected value. 519f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 520f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected final boolean compareAndSetState(int expect, int update) { 521f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // See below for intrinsics setup to support this 522f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return unsafe.compareAndSwapInt(this, stateOffset, expect, update); 523f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 524f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 525f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Queuing utilities 526f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 527f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 5288210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * The number of nanoseconds for which it is faster to spin 5298210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * rather than to use timed park. A rough estimate suffices 5308210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * to improve responsiveness with very short timeouts. 5318210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 5328210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson static final long spinForTimeoutThreshold = 1000L; 5338210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 5348210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 5358210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Inserts node into queue, initializing if necessary. See picture above. 536f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param node the node to insert 537f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return node's predecessor 538f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 539f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private Node enq(final Node node) { 540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 541f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node t = tail; 542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (t == null) { // Must initialize 5438210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (compareAndSetHead(new Node())) 5448210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson tail = head; 5458210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } else { 5468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson node.prev = t; 547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (compareAndSetTail(t, node)) { 5488210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson t.next = node; 5498210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return t; 550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 5568210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Creates and enqueues node for current thread and given mode. 5578210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 558f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared 559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the new node 560f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private Node addWaiter(Node mode) { 562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node node = new Node(Thread.currentThread(), mode); 563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Try the fast path of enq; backup to full enq on failure 564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node pred = tail; 565f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pred != null) { 5668210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson node.prev = pred; 567f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (compareAndSetTail(pred, node)) { 5688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson pred.next = node; 569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return node; 570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project enq(node); 573f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return node; 574f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 576f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 5778210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Sets head of queue to be node, thus dequeuing. Called only by 578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * acquire methods. Also nulls out unused fields for sake of GC 579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and to suppress unnecessary signals and traversals. 5808210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 5818210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param node the node 582f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 583f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void setHead(Node node) { 584f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project head = node; 585f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project node.thread = null; 5868210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson node.prev = null; 587f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 588f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 589f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 5908210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Wakes up node's successor, if one exists. 5918210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param node the node 593f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 594f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void unparkSuccessor(Node node) { 595f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 5968210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * If status is negative (i.e., possibly needing signal) try 5978210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * to clear in anticipation of signalling. It is OK if this 5988210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * fails or if status is changed by waiting thread. 599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 6008210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson int ws = node.waitStatus; 6018210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (ws < 0) 6028210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson compareAndSetWaitStatus(node, ws, 0); 6038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 604f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 605f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Thread to unpark is held in successor, which is normally 606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * just the next node. But if cancelled or apparently null, 607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * traverse backwards from tail to find the actual 608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * non-cancelled successor. 609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node s = node.next; 6118210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (s == null || s.waitStatus > 0) { 6128210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson s = null; 6138210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson for (Node t = tail; t != null && t != node; t = t.prev) 6148210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (t.waitStatus <= 0) 6158210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson s = t; 616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 6178210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (s != null) 6188210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson LockSupport.unpark(s.thread); 619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 6228210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Release action for shared mode -- signal successor and ensure 6238210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * propagation. (Note: For exclusive mode, release just amounts 6248210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * to calling unparkSuccessor of head if it needs signal.) 6258210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 6268210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private void doReleaseShared() { 6278210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /* 6288210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Ensure that a release propagates, even if there are other 6298210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * in-progress acquires/releases. This proceeds in the usual 6308210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * way of trying to unparkSuccessor of head if it needs 6318210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * signal. But if it does not, status is set to PROPAGATE to 6328210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * ensure that upon release, propagation continues. 6338210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Additionally, we must loop in case a new node is added 6348210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * while we are doing this. Also, unlike other uses of 6358210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * unparkSuccessor, we need to know if CAS to reset status 6368210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * fails, if so rechecking. 6378210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 6388210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson for (;;) { 6398210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node h = head; 6408210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (h != null && h != tail) { 6418210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson int ws = h.waitStatus; 6428210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (ws == Node.SIGNAL) { 6438210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0)) 6448210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson continue; // loop to recheck cases 6458210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson unparkSuccessor(h); 6468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 6478210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson else if (ws == 0 && 6488210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson !compareAndSetWaitStatus(h, 0, Node.PROPAGATE)) 6498210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson continue; // loop on failed CAS 6508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 6518210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (h == head) // loop if head changed 6528210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson break; 6538210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 6548210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 6558210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 6568210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 6578210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Sets head of queue, and checks if successor may be waiting 6588210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * in shared mode, if so propagating if either propagate > 0 or 6598210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * PROPAGATE status was set. 6608210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 6618210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param node the node 662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param propagate the return value from a tryAcquireShared 663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void setHeadAndPropagate(Node node, int propagate) { 6658210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node h = head; // Record old head for check below 666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project setHead(node); 6678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /* 6688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Try to signal next queued node if: 6698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Propagation was indicated by caller, 6708210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * or was recorded (as h.waitStatus) by a previous operation 6718210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * (note: this uses sign-check of waitStatus because 6728210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * PROPAGATE status may transition to SIGNAL.) 6738210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * and 6748210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * The next node is waiting in shared mode, 6758210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * or we don't know, because it appears null 6768210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 6778210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * The conservatism in both of these checks may cause 6788210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * unnecessary wake-ups, but only when there are multiple 6798210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * racing acquires/releases, so most need signals now or soon 6808210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * anyway. 6818210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 6828210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (propagate > 0 || h == null || h.waitStatus < 0) { 6838210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node s = node.next; 684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (s == null || s.isShared()) 6858210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson doReleaseShared(); 686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 688f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 689f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Utilities for various versions of acquire 690f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 6928210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Cancels an ongoing attempt to acquire. 6938210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param node the node 695f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void cancelAcquire(Node node) { 6978210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // Ignore if node doesn't exist 6988210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (node == null) 6998210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return; 7008210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 7018210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson node.thread = null; 7028210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 7038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // Skip cancelled predecessors 7048210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node pred = node.prev; 7058210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson while (pred.waitStatus > 0) 7068210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson node.prev = pred = pred.prev; 7078210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 7088210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // predNext is the apparent node to unsplice. CASes below will 7098210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // fail if not, in which case, we lost race vs another cancel 7108210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // or signal, so no further action is necessary. 7118210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node predNext = pred.next; 7128210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 7138210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // Can use unconditional write instead of CAS here. 7148210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // After this atomic step, other Nodes can skip past us. 7158210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // Before, we are free of interference from other threads. 7168210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson node.waitStatus = Node.CANCELLED; 7178210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 7188210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // If we are the tail, remove ourselves. 7198210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (node == tail && compareAndSetTail(node, pred)) { 7208210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson compareAndSetNext(pred, predNext, null); 7218210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } else { 7228210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // If successor needs signal, try to set pred's next-link 7238210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // so it will get one. Otherwise wake it up to propagate. 7248210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson int ws; 7258210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (pred != head && 7268210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson ((ws = pred.waitStatus) == Node.SIGNAL || 7278210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) && 7288210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson pred.thread != null) { 7298210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node next = node.next; 7308210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (next != null && next.waitStatus <= 0) 7318210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson compareAndSetNext(pred, predNext, next); 7328210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } else { 7338210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson unparkSuccessor(node); 7348210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 7358210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 7368210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson node.next = node; // help GC 737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Checks and updates status for a node that failed to acquire. 742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns true if thread should block. This is the main signal 743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * control in all acquire loops. Requires that pred == node.prev 7448210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param pred node's predecessor holding status 7468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param node the node 7478210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if thread should block 748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 749f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { 7508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson int ws = pred.waitStatus; 7518210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (ws == Node.SIGNAL) 752f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 753f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This node has already set status asking a release 7548210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * to signal it, so it can safely park. 755f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 7578210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (ws > 0) { 758f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 7598210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Predecessor was cancelled. Skip over predecessors and 7608210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * indicate retry. 761f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 7628210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson do { 7638210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson node.prev = pred = pred.prev; 7648210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } while (pred.waitStatus > 0); 7658210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson pred.next = node; 7668210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } else { 767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 7688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * waitStatus must be 0 or PROPAGATE. Indicate that we 7698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * need a signal, but don't park yet. Caller will need to 7708210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * retry to make sure it cannot acquire before parking. 771f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 7728210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson compareAndSetWaitStatus(pred, ws, Node.SIGNAL); 7738210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 774f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 775f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 777f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 778f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Convenience method to interrupt current thread. 779f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static void selfInterrupt() { 781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Thread.currentThread().interrupt(); 782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 785f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Convenience method to park and then check if interrupted 7868210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 7878210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if interrupted 788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 7898210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private final boolean parkAndCheckInterrupt() { 790f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LockSupport.park(); 791f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return Thread.interrupted(); 792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 794f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 795f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Various flavors of acquire, varying in exclusive/shared and 796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * control modes. Each is mostly the same, but annoyingly 797f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * different. Only a little bit of factoring is possible due to 798f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * interactions of exception mechanics (including ensuring that we 799f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * cancel if tryAcquire throws exception) and other control, at 8008210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * least not without hurting performance too much. 801f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 802f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 803f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 8048210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Acquires in exclusive uninterruptible mode for thread already in 805f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * queue. Used by condition wait methods as well as acquire. 8068210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 807f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param node the node 808f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param arg the acquire argument 8098210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if interrupted while waiting 810f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 811f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final boolean acquireQueued(final Node node, int arg) { 8128210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson boolean failed = true; 813f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 814f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean interrupted = false; 815f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 816f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node p = node.predecessor(); 817f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (p == head && tryAcquire(arg)) { 818f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project setHead(node); 819f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project p.next = null; // help GC 8208210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson failed = false; 821f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return interrupted; 822f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 8238210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 8248210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson parkAndCheckInterrupt()) 825f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project interrupted = true; 826f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 8278210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } finally { 8288210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (failed) 8298210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson cancelAcquire(node); 830f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 831f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 832f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 8338210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 8348210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Acquires in exclusive interruptible mode. 835f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param arg the acquire argument 836f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 8378210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private void doAcquireInterruptibly(int arg) 838f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throws InterruptedException { 839f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node node = addWaiter(Node.EXCLUSIVE); 8408210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson boolean failed = true; 841f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 842f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 843f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node p = node.predecessor(); 844f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (p == head && tryAcquire(arg)) { 845f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project setHead(node); 846f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project p.next = null; // help GC 8478210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson failed = false; 848f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 849f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 8508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 8518210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson parkAndCheckInterrupt()) 8528210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson throw new InterruptedException(); 853f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 8548210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } finally { 8558210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (failed) 8568210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson cancelAcquire(node); 857f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 858f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 859f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 8608210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 8618210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Acquires in exclusive timed mode. 8628210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 863f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param arg the acquire argument 864f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param nanosTimeout max wait time 8658210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if acquired 866f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 8678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private boolean doAcquireNanos(int arg, long nanosTimeout) 868f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throws InterruptedException { 869f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project long lastTime = System.nanoTime(); 870f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node node = addWaiter(Node.EXCLUSIVE); 8718210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson boolean failed = true; 872f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 873f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 874f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node p = node.predecessor(); 875f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (p == head && tryAcquire(arg)) { 876f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project setHead(node); 877f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project p.next = null; // help GC 8788210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson failed = false; 879f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 880f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 8818210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (nanosTimeout <= 0) 882f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 8838210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 8848210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson nanosTimeout > spinForTimeoutThreshold) 885f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LockSupport.parkNanos(nanosTimeout); 8868210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson long now = System.nanoTime(); 8878210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson nanosTimeout -= now - lastTime; 8888210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson lastTime = now; 8898210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (Thread.interrupted()) 8908210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson throw new InterruptedException(); 891f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 8928210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } finally { 8938210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (failed) 8948210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson cancelAcquire(node); 895f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 896f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 897f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 8988210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 8998210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Acquires in shared uninterruptible mode. 900f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param arg the acquire argument 901f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 902f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void doAcquireShared(int arg) { 903f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node node = addWaiter(Node.SHARED); 9048210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson boolean failed = true; 905f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 906f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean interrupted = false; 907f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 908f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node p = node.predecessor(); 909f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (p == head) { 910f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int r = tryAcquireShared(arg); 911f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (r >= 0) { 912f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project setHeadAndPropagate(node, r); 913f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project p.next = null; // help GC 914f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (interrupted) 915f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project selfInterrupt(); 9168210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson failed = false; 917f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 918f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 919f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 9208210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 9218210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson parkAndCheckInterrupt()) 922f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project interrupted = true; 923f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 9248210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } finally { 9258210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (failed) 9268210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson cancelAcquire(node); 927f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 928f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 929f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 9308210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 9318210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Acquires in shared interruptible mode. 932f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param arg the acquire argument 933f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 9348210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private void doAcquireSharedInterruptibly(int arg) 935f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throws InterruptedException { 936f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node node = addWaiter(Node.SHARED); 9378210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson boolean failed = true; 938f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 939f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 940f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node p = node.predecessor(); 941f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (p == head) { 942f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int r = tryAcquireShared(arg); 943f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (r >= 0) { 944f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project setHeadAndPropagate(node, r); 945f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project p.next = null; // help GC 9468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson failed = false; 947f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 948f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 949f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 9508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 9518210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson parkAndCheckInterrupt()) 9528210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson throw new InterruptedException(); 953f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 9548210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } finally { 9558210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (failed) 9568210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson cancelAcquire(node); 957f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 958f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 959f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 9608210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 9618210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Acquires in shared timed mode. 9628210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 963f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param arg the acquire argument 964f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param nanosTimeout max wait time 9658210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if acquired 966f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 9678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private boolean doAcquireSharedNanos(int arg, long nanosTimeout) 968f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throws InterruptedException { 969f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 970f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project long lastTime = System.nanoTime(); 971f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node node = addWaiter(Node.SHARED); 9728210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson boolean failed = true; 973f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 974f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 975f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final Node p = node.predecessor(); 976f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (p == head) { 977f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int r = tryAcquireShared(arg); 978f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (r >= 0) { 979f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project setHeadAndPropagate(node, r); 980f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project p.next = null; // help GC 9818210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson failed = false; 982f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 983f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 984f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 9858210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (nanosTimeout <= 0) 986f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 9878210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 9888210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson nanosTimeout > spinForTimeoutThreshold) 989f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LockSupport.parkNanos(nanosTimeout); 9908210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson long now = System.nanoTime(); 9918210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson nanosTimeout -= now - lastTime; 9928210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson lastTime = now; 9938210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (Thread.interrupted()) 9948210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson throw new InterruptedException(); 995f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 9968210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } finally { 9978210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (failed) 9988210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson cancelAcquire(node); 999f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1000f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1001f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 10028210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // Main exported methods 1003f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1004f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1005f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Attempts to acquire in exclusive mode. This method should query 1006f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * if the state of the object permits it to be acquired in the 1007f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * exclusive mode, and if so to acquire it. 1008f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1009f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>This method is always invoked by the thread performing 1010f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * acquire. If this method reports failure, the acquire method 1011f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * may queue the thread, if it is not already queued, until it is 1012f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * signalled by a release from some other thread. This can be used 10138210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * to implement method {@link Lock#tryLock()}. 1014f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1015f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>The default 10168210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * implementation throws {@link UnsupportedOperationException}. 1017f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10188210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the acquire argument. This value is always the one 10198210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * passed to an acquire method, or is the value saved on entry 10208210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * to a condition wait. The value is otherwise uninterpreted 10218210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * and can represent anything you like. 10228210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if successful. Upon success, this object has 10238210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * been acquired. 10248210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws IllegalMonitorStateException if acquiring would place this 10258210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * synchronizer in an illegal state. This exception must be 10268210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * thrown in a consistent fashion for synchronization to work 10278210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * correctly. 1028f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws UnsupportedOperationException if exclusive mode is not supported 1029f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1030f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected boolean tryAcquire(int arg) { 1031f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new UnsupportedOperationException(); 1032f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1033f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1034f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1035f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Attempts to set the state to reflect a release in exclusive 10368210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * mode. 10378210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 10388210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>This method is always invoked by the thread performing release. 1039f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1040f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>The default implementation throws 10418210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@link UnsupportedOperationException}. 10428210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 10438210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the release argument. This value is always the one 10448210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * passed to a release method, or the current state value upon 10458210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * entry to a condition wait. The value is otherwise 10468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * uninterpreted and can represent anything you like. 10478210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if this object is now in a fully released 10488210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * state, so that any waiting threads may attempt to acquire; 10498210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * and {@code false} otherwise. 10508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws IllegalMonitorStateException if releasing would place this 10518210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * synchronizer in an illegal state. This exception must be 10528210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * thrown in a consistent fashion for synchronization to work 10538210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * correctly. 1054f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws UnsupportedOperationException if exclusive mode is not supported 1055f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1056f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected boolean tryRelease(int arg) { 1057f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new UnsupportedOperationException(); 1058f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1059f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1060f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1061f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Attempts to acquire in shared mode. This method should query if 1062f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the state of the object permits it to be acquired in the shared 10638210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * mode, and if so to acquire it. 1064f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1065f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>This method is always invoked by the thread performing 1066f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * acquire. If this method reports failure, the acquire method 1067f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * may queue the thread, if it is not already queued, until it is 1068f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * signalled by a release from some other thread. 1069f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1070f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>The default implementation throws {@link 10718210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * UnsupportedOperationException}. 1072f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10738210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the acquire argument. This value is always the one 10748210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * passed to an acquire method, or is the value saved on entry 10758210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * to a condition wait. The value is otherwise uninterpreted 10768210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * and can represent anything you like. 10778210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return a negative value on failure; zero if acquisition in shared 10788210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * mode succeeded but no subsequent shared-mode acquire can 10798210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * succeed; and a positive value if acquisition in shared 10808210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * mode succeeded and subsequent shared-mode acquires might 10818210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * also succeed, in which case a subsequent waiting thread 10828210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * must check availability. (Support for three different 10838210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * return values enables this method to be used in contexts 10848210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * where acquires only sometimes act exclusively.) Upon 10858210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * success, this object has been acquired. 10868210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws IllegalMonitorStateException if acquiring would place this 10878210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * synchronizer in an illegal state. This exception must be 10888210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * thrown in a consistent fashion for synchronization to work 10898210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * correctly. 1090f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws UnsupportedOperationException if shared mode is not supported 1091f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1092f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected int tryAcquireShared(int arg) { 1093f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new UnsupportedOperationException(); 1094f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1095f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1096f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1097f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Attempts to set the state to reflect a release in shared mode. 10988210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1099f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>This method is always invoked by the thread performing release. 11008210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 11018210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>The default implementation throws 11028210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@link UnsupportedOperationException}. 11038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 11048210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the release argument. This value is always the one 11058210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * passed to a release method, or the current state value upon 11068210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * entry to a condition wait. The value is otherwise 11078210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * uninterpreted and can represent anything you like. 11088210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if this release of shared mode may permit a 11098210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * waiting acquire (shared or exclusive) to succeed; and 11108210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@code false} otherwise 11118210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws IllegalMonitorStateException if releasing would place this 11128210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * synchronizer in an illegal state. This exception must be 11138210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * thrown in a consistent fashion for synchronization to work 11148210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * correctly. 1115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws UnsupportedOperationException if shared mode is not supported 1116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected boolean tryReleaseShared(int arg) { 1118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new UnsupportedOperationException(); 1119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 11228210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Returns {@code true} if synchronization is held exclusively with 11238210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * respect to the current (calling) thread. This method is invoked 1124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * upon each call to a non-waiting {@link ConditionObject} method. 1125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * (Waiting methods instead invoke {@link #release}.) 11268210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>The default implementation throws {@link 1128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * UnsupportedOperationException}. This method is invoked 1129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * internally only within {@link ConditionObject} methods, so need 1130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * not be defined if conditions are not used. 1131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 11328210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if synchronization is held exclusively; 11338210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@code false} otherwise 1134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws UnsupportedOperationException if conditions are not supported 1135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected boolean isHeldExclusively() { 1137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new UnsupportedOperationException(); 1138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Acquires in exclusive mode, ignoring interrupts. Implemented 1142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * by invoking at least once {@link #tryAcquire}, 1143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * returning on success. Otherwise the thread is queued, possibly 1144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * repeatedly blocking and unblocking, invoking {@link 1145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * #tryAcquire} until success. This method can be used 11468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * to implement method {@link Lock#lock}. 11478210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 11488210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the acquire argument. This value is conveyed to 11498210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@link #tryAcquire} but is otherwise uninterpreted and 11508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * can represent anything you like. 11518210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 1152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final void acquire(int arg) { 1153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!tryAcquire(arg) && 1154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) 1155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project selfInterrupt(); 1156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Acquires in exclusive mode, aborting if interrupted. 1160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Implemented by first checking interrupt status, then invoking 1161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * at least once {@link #tryAcquire}, returning on 1162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * success. Otherwise the thread is queued, possibly repeatedly 1163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * blocking and unblocking, invoking {@link #tryAcquire} 1164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * until success or the thread is interrupted. This method can be 11658210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * used to implement method {@link Lock#lockInterruptibly}. 11668210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 11678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the acquire argument. This value is conveyed to 11688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@link #tryAcquire} but is otherwise uninterpreted and 11698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * can represent anything you like. 1170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws InterruptedException if the current thread is interrupted 1171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final void acquireInterruptibly(int arg) throws InterruptedException { 1173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (Thread.interrupted()) 1174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new InterruptedException(); 1175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!tryAcquire(arg)) 1176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project doAcquireInterruptibly(arg); 1177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Attempts to acquire in exclusive mode, aborting if interrupted, 1181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and failing if the given timeout elapses. Implemented by first 1182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * checking interrupt status, then invoking at least once {@link 1183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * #tryAcquire}, returning on success. Otherwise, the thread is 1184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * queued, possibly repeatedly blocking and unblocking, invoking 1185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link #tryAcquire} until success or the thread is interrupted 1186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * or the timeout elapses. This method can be used to implement 1187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * method {@link Lock#tryLock(long, TimeUnit)}. 11888210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 11898210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the acquire argument. This value is conveyed to 11908210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@link #tryAcquire} but is otherwise uninterpreted and 11918210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * can represent anything you like. 1192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param nanosTimeout the maximum number of nanoseconds to wait 11938210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if acquired; {@code false} if timed out 1194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws InterruptedException if the current thread is interrupted 1195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 11968210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson public final boolean tryAcquireNanos(int arg, long nanosTimeout) throws InterruptedException { 11978210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (Thread.interrupted()) 11988210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson throw new InterruptedException(); 11998210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return tryAcquire(arg) || 12008210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson doAcquireNanos(arg, nanosTimeout); 12018210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 1202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Releases in exclusive mode. Implemented by unblocking one or 1205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * more threads if {@link #tryRelease} returns true. 12068210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * This method can be used to implement method {@link Lock#unlock}. 12078210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 12088210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the release argument. This value is conveyed to 12098210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@link #tryRelease} but is otherwise uninterpreted and 12108210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * can represent anything you like. 12118210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return the value returned from {@link #tryRelease} 1212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final boolean release(int arg) { 1214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (tryRelease(arg)) { 1215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node h = head; 12168210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (h != null && h.waitStatus != 0) 1217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project unparkSuccessor(h); 1218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 1219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 1221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Acquires in shared mode, ignoring interrupts. Implemented by 1225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * first invoking at least once {@link #tryAcquireShared}, 1226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * returning on success. Otherwise the thread is queued, possibly 1227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * repeatedly blocking and unblocking, invoking {@link 12288210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * #tryAcquireShared} until success. 12298210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 12308210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the acquire argument. This value is conveyed to 12318210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@link #tryAcquireShared} but is otherwise uninterpreted 12328210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * and can represent anything you like. 1233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final void acquireShared(int arg) { 1235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (tryAcquireShared(arg) < 0) 1236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project doAcquireShared(arg); 1237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Acquires in shared mode, aborting if interrupted. Implemented 1241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * by first checking interrupt status, then invoking at least once 1242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link #tryAcquireShared}, returning on success. Otherwise the 1243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * thread is queued, possibly repeatedly blocking and unblocking, 1244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * invoking {@link #tryAcquireShared} until success or the thread 12458210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * is interrupted. 12468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the acquire argument 1247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * This value is conveyed to {@link #tryAcquireShared} but is 1248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * otherwise uninterpreted and can represent anything 1249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you like. 1250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws InterruptedException if the current thread is interrupted 1251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final void acquireSharedInterruptibly(int arg) throws InterruptedException { 1253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (Thread.interrupted()) 1254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new InterruptedException(); 1255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (tryAcquireShared(arg) < 0) 1256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project doAcquireSharedInterruptibly(arg); 12578210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 1258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Attempts to acquire in shared mode, aborting if interrupted, and 1261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * failing if the given timeout elapses. Implemented by first 1262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * checking interrupt status, then invoking at least once {@link 1263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * #tryAcquireShared}, returning on success. Otherwise, the 1264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * thread is queued, possibly repeatedly blocking and unblocking, 1265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * invoking {@link #tryAcquireShared} until success or the thread 1266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is interrupted or the timeout elapses. 12678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 12688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the acquire argument. This value is conveyed to 12698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@link #tryAcquireShared} but is otherwise uninterpreted 12708210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * and can represent anything you like. 1271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param nanosTimeout the maximum number of nanoseconds to wait 12728210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if acquired; {@code false} if timed out 1273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws InterruptedException if the current thread is interrupted 1274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 12758210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout) throws InterruptedException { 12768210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (Thread.interrupted()) 12778210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson throw new InterruptedException(); 12788210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return tryAcquireShared(arg) >= 0 || 12798210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson doAcquireSharedNanos(arg, nanosTimeout); 12808210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 1281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Releases in shared mode. Implemented by unblocking one or more 12848210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * threads if {@link #tryReleaseShared} returns true. 12858210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 12868210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @param arg the release argument. This value is conveyed to 12878210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@link #tryReleaseShared} but is otherwise uninterpreted 12888210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * and can represent anything you like. 12898210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return the value returned from {@link #tryReleaseShared} 1290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final boolean releaseShared(int arg) { 1292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (tryReleaseShared(arg)) { 12938210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson doReleaseShared(); 1294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 1295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 1297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Queue inspection methods 1300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Queries whether any threads are waiting to acquire. Note that 1303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * because cancellations due to interrupts and timeouts may occur 13048210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * at any time, a {@code true} return does not guarantee that any 1305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * other thread will ever acquire. 1306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 13078210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>In this implementation, this operation returns in 1308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * constant time. 1309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 13108210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if there may be other threads waiting to acquire 1311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 13128210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson public final boolean hasQueuedThreads() { 1313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return head != tail; 1314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Queries whether any threads have ever contended to acquire this 1318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * synchronizer; that is if an acquire method has ever blocked. 1319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 13208210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>In this implementation, this operation returns in 1321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * constant time. 1322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 13238210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if there has ever been contention 1324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final boolean hasContended() { 1326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return head != null; 1327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the first (longest-waiting) thread in the queue, or 13318210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@code null} if no threads are currently queued. 1332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 13338210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>In this implementation, this operation normally returns in 1334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * constant time, but may iterate upon contention if other threads are 1335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * concurrently modifying the queue. 1336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the first (longest-waiting) thread in the queue, or 13388210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@code null} if no threads are currently queued 1339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final Thread getFirstQueuedThread() { 1341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // handle only fast path, else relay 13428210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return (head == tail) ? null : fullGetFirstQueuedThread(); 1343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Version of getFirstQueuedThread called when fastpath fails 1347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private Thread fullGetFirstQueuedThread() { 1349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 13508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * The first node is normally head.next. Try to get its 13518210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * thread field, ensuring consistent reads: If thread 13528210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * field is nulled out or s.prev is no longer head, then 13538210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * some other thread(s) concurrently performed setHead in 13548210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * between some of our reads. We try this twice before 13558210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * resorting to traversal. 1356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 13578210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node h, s; 13588210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Thread st; 13598210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (((h = head) != null && (s = h.next) != null && 13608210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson s.prev == head && (st = s.thread) != null) || 13618210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson ((h = head) != null && (s = h.next) != null && 13628210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson s.prev == head && (st = s.thread) != null)) 13638210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return st; 1364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13658210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /* 13668210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Head's next field might not have been set yet, or may have 13678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * been unset after setHead. So we must check to see if tail 13688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * is actually first node. If not, we continue on, safely 13698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * traversing from tail back to head to find first, 13708210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * guaranteeing termination. 13718210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 1372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 13738210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node t = tail; 13748210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Thread firstThread = null; 13758210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson while (t != null && t != head) { 13768210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Thread tt = t.thread; 13778210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (tt != null) 13788210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson firstThread = tt; 13798210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson t = t.prev; 1380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 13818210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return firstThread; 1382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 13858210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Returns true if the given thread is currently queued. 1386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 13878210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>This implementation traverses the queue to determine 1388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * presence of the given thread. 1389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 1390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param thread the thread 13918210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if the given thread is on the queue 13928210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws NullPointerException if the thread is null 1393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final boolean isQueued(Thread thread) { 1395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (thread == null) 1396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException(); 1397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (Node p = tail; p != null; p = p.prev) 1398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (p.thread == thread) 1399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 1400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 1401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 14038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 14048210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Returns {@code true} if the apparent first queued thread, if one 14058210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * exists, is waiting in exclusive mode. If this method returns 14068210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@code true}, and the current thread is attempting to acquire in 14078210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * shared mode (that is, this method is invoked from {@link 14088210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * #tryAcquireShared}) then it is guaranteed that the current thread 14098210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * is not the first queued thread. Used only as a heuristic in 14108210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * ReentrantReadWriteLock. 14118210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 14128210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson final boolean apparentlyFirstQueuedIsExclusive() { 14138210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node h, s; 14148210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return (h = head) != null && 14158210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson (s = h.next) != null && 14168210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson !s.isShared() && 14178210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson s.thread != null; 14188210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 14198210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 14208210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 14218210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Queries whether any threads have been waiting to acquire longer 14228210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * than the current thread. 14238210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 14248210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>An invocation of this method is equivalent to (but may be 14258210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * more efficient than): 14268210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <pre> {@code 14278210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * getFirstQueuedThread() != Thread.currentThread() && 14288210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * hasQueuedThreads()}</pre> 14298210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 14308210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>Note that because cancellations due to interrupts and 14318210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * timeouts may occur at any time, a {@code true} return does not 14328210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * guarantee that some other thread will acquire before the current 14338210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * thread. Likewise, it is possible for another thread to win a 14348210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * race to enqueue after this method has returned {@code false}, 14358210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * due to the queue being empty. 14368210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 14378210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>This method is designed to be used by a fair synchronizer to 14388210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * avoid <a href="AbstractQueuedSynchronizer#barging">barging</a>. 14398210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Such a synchronizer's {@link #tryAcquire} method should return 14408210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@code false}, and its {@link #tryAcquireShared} method should 14418210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * return a negative value, if this method returns {@code true} 14428210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * (unless this is a reentrant acquire). For example, the {@code 14438210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * tryAcquire} method for a fair, reentrant, exclusive mode 14448210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * synchronizer might look like this: 14458210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 14468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <pre> {@code 14478210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * protected boolean tryAcquire(int arg) { 14488210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * if (isHeldExclusively()) { 14498210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * // A reentrant acquire; increment hold count 14508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * return true; 14518210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } else if (hasQueuedPredecessors()) { 14528210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * return false; 14538210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } else { 14548210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * // try to acquire normally 14558210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * } 14568210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * }}</pre> 14578210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 14588210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if there is a queued thread preceding the 14598210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * current thread, and {@code false} if the current thread 14608210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * is at the head of the queue or the queue is empty 14618210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 14628210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson final boolean hasQueuedPredecessors() { 14638210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // The correctness of this depends on head being initialized 14648210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // before tail and on head.next being accurate if the current 14658210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // thread is first in queue. 14668210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node t = tail; // Read fields in reverse initialization order 14678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node h = head; 14688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node s; 14698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return h != t && 14708210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson ((s = h.next) == null || s.thread != Thread.currentThread()); 14718210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 14728210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 14738210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 1474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Instrumentation and monitoring methods 1475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1476f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns an estimate of the number of threads waiting to 1478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * acquire. The value is only an estimate because the number of 1479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * threads may change dynamically while this method traverses 1480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * internal data structures. This method is designed for use in 1481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * monitoring system state, not for synchronization 1482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * control. 1483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 14848210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return the estimated number of threads waiting to acquire 1485f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1486f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final int getQueueLength() { 1487f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int n = 0; 1488f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (Node p = tail; p != null; p = p.prev) { 1489f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (p.thread != null) 1490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ++n; 1491f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1492f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return n; 1493f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1494f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1495f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1496f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns a collection containing threads that may be waiting to 1497f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * acquire. Because the actual set of threads may change 1498f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * dynamically while constructing this result, the returned 1499f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * collection is only a best-effort estimate. The elements of the 1500f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * returned collection are in no particular order. This method is 1501f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * designed to facilitate construction of subclasses that provide 1502f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * more extensive monitoring facilities. 15038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the collection of threads 1505f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1506f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final Collection<Thread> getQueuedThreads() { 1507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<Thread> list = new ArrayList<Thread>(); 1508f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (Node p = tail; p != null; p = p.prev) { 1509f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Thread t = p.thread; 1510f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (t != null) 1511f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project list.add(t); 1512f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1513f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return list; 1514f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1515f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1516f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1517f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns a collection containing threads that may be waiting to 1518f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * acquire in exclusive mode. This has the same properties 1519f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * as {@link #getQueuedThreads} except that it only returns 1520f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * those threads waiting due to an exclusive acquire. 15218210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1522f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the collection of threads 1523f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1524f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final Collection<Thread> getExclusiveQueuedThreads() { 1525f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<Thread> list = new ArrayList<Thread>(); 1526f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (Node p = tail; p != null; p = p.prev) { 1527f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!p.isShared()) { 1528f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Thread t = p.thread; 1529f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (t != null) 1530f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project list.add(t); 1531f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1532f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1533f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return list; 1534f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1535f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1536f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1537f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns a collection containing threads that may be waiting to 1538f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * acquire in shared mode. This has the same properties 1539f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * as {@link #getQueuedThreads} except that it only returns 1540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * those threads waiting due to a shared acquire. 15418210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the collection of threads 1543f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1544f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final Collection<Thread> getSharedQueuedThreads() { 1545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<Thread> list = new ArrayList<Thread>(); 1546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (Node p = tail; p != null; p = p.prev) { 1547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (p.isShared()) { 1548f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Thread t = p.thread; 1549f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (t != null) 1550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project list.add(t); 1551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1552f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return list; 1554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1556f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 15578210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Returns a string identifying this synchronizer, as well as its state. 15588210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * The state, in brackets, includes the String {@code "State ="} 15598210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * followed by the current value of {@link #getState}, and either 15608210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * {@code "nonempty"} or {@code "empty"} depending on whether the 15618210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * queue is empty. 1562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 15638210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return a string identifying this synchronizer, as well as its state 1564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1565f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public String toString() { 1566f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int s = getState(); 15678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson String q = hasQueuedThreads() ? "non" : ""; 15688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return super.toString() + 1569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project "[State = " + s + ", " + q + "empty queue]"; 1570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1573f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Internal support methods for Conditions 1574f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1576f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns true if a node, always one that was initially placed on 1577f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a condition queue, is now waiting to reacquire on sync queue. 1578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param node the node 1579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if is reacquiring 1580f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1581f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final boolean isOnSyncQueue(Node node) { 1582f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (node.waitStatus == Node.CONDITION || node.prev == null) 1583f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 1584f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (node.next != null) // If has successor, it must be on queue 1585f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 1586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1587f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * node.prev can be non-null, but not yet on queue because 1588f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the CAS to place it on queue can fail. So we have to 1589f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * traverse from tail to make sure it actually made it. It 1590f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * will always be near the tail in calls to this method, and 1591f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * unless the CAS failed (which is unlikely), it will be 1592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * there, so we hardly ever traverse much. 1593f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1594f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return findNodeFromTail(node); 15958210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 1596f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1598f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns true if node is on sync queue by searching backwards from tail. 1599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Called only when needed by isOnSyncQueue. 1600f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if present 1601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean findNodeFromTail(Node node) { 16038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node t = tail; 1604f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 1605f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (t == node) 1606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 1607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (t == null) 1608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 1609f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project t = t.prev; 1610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1611f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1612f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1613f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 16148210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Transfers a node from a condition queue onto sync queue. 1615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns true if successful. 1616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param node the node 1617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return true if successfully transferred (else the node was 1618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * cancelled before signal). 1619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final boolean transferForSignal(Node node) { 1621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1622f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If cannot change waitStatus, the node has been cancelled. 1623f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1624f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!compareAndSetWaitStatus(node, Node.CONDITION, 0)) 1625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 1626f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Splice onto queue and try to set waitStatus of predecessor to 1629f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * indicate that thread is (probably) waiting. If cancelled or 1630f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * attempt to set waitStatus fails, wake up to resync (in which 1631f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * case the waitStatus can be transiently and harmlessly wrong). 1632f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1633f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node p = enq(node); 16348210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson int ws = p.waitStatus; 16358210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL)) 1636f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LockSupport.unpark(node.thread); 1637f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 1638f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1640f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Transfers node, if necessary, to sync queue after a cancelled 1642f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * wait. Returns true if thread was cancelled before being 1643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * signalled. 1644f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param node its node 16458210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return true if cancelled before the node was signalled 1646f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1647f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final boolean transferAfterCancelledWait(Node node) { 1648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) { 1649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project enq(node); 1650f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 1651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If we lost out to a signal(), then we can't proceed 1654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * until it finishes its enq(). Cancelling during an 1655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * incomplete transfer is both rare and transient, so just 1656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * spin. 1657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16588210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson while (!isOnSyncQueue(node)) 1659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Thread.yield(); 1660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 1661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 16648210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Invokes release with current state value; returns saved state. 16658210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Cancels node and throws exception on failure. 1666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param node the condition node for this wait 1667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return previous sync state 1668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final int fullyRelease(Node node) { 16708210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson boolean failed = true; 1671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 1672f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int savedState = getState(); 16738210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (release(savedState)) { 16748210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson failed = false; 1675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return savedState; 16768210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } else { 16778210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson throw new IllegalMonitorStateException(); 16788210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 16798210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } finally { 16808210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (failed) 16818210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson node.waitStatus = Node.CANCELLED; 1682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1685f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Instrumentation methods for conditions 1686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 16888210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Queries whether the given ConditionObject 1689f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * uses this synchronizer as its lock. 16908210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param condition the condition 1692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return <tt>true</tt> if owned 16938210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws NullPointerException if the condition is null 1694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1695f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final boolean owns(ConditionObject condition) { 1696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (condition == null) 1697f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException(); 1698f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return condition.isOwnedBy(this); 1699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1700f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1702f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Queries whether any threads are waiting on the given condition 1703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * associated with this synchronizer. Note that because timeouts 1704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and interrupts may occur at any time, a <tt>true</tt> return 1705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * does not guarantee that a future <tt>signal</tt> will awaken 1706f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * any threads. This method is designed primarily for use in 1707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * monitoring of the system state. 17088210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1709f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param condition the condition 17108210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return <tt>true</tt> if there are any waiting threads 17118210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws IllegalMonitorStateException if exclusive synchronization 17128210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * is not held 1713f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws IllegalArgumentException if the given condition is 17148210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * not associated with this synchronizer 17158210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws NullPointerException if the condition is null 17168210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 1717f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final boolean hasWaiters(ConditionObject condition) { 1718f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!owns(condition)) 1719f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("Not owner"); 1720f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return condition.hasWaiters(); 1721f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1723f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1724f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns an estimate of the number of threads waiting on the 1725f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * given condition associated with this synchronizer. Note that 1726f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * because timeouts and interrupts may occur at any time, the 1727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * estimate serves only as an upper bound on the actual number of 1728f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * waiters. This method is designed for use in monitoring of the 1729f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * system state, not for synchronization control. 17308210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param condition the condition 17328210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return the estimated number of waiting threads 17338210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws IllegalMonitorStateException if exclusive synchronization 17348210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * is not held 1735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws IllegalArgumentException if the given condition is 17368210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * not associated with this synchronizer 17378210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws NullPointerException if the condition is null 17388210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 1739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final int getWaitQueueLength(ConditionObject condition) { 1740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!owns(condition)) 1741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("Not owner"); 1742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return condition.getWaitQueueLength(); 1743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1746f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns a collection containing those threads that may be 1747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * waiting on the given condition associated with this 1748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * synchronizer. Because the actual set of threads may change 1749f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * dynamically while constructing this result, the returned 1750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * collection is only a best-effort estimate. The elements of the 17518210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * returned collection are in no particular order. 17528210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1753f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param condition the condition 1754f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the collection of threads 17558210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws IllegalMonitorStateException if exclusive synchronization 17568210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * is not held 1757f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws IllegalArgumentException if the given condition is 17588210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * not associated with this synchronizer 17598210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @throws NullPointerException if the condition is null 1760f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1761f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final Collection<Thread> getWaitingThreads(ConditionObject condition) { 1762f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!owns(condition)) 1763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("Not owner"); 1764f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return condition.getWaitingThreads(); 1765f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1768f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Condition implementation for a {@link 1769f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * AbstractQueuedSynchronizer} serving as the basis of a {@link 1770f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Lock} implementation. 1771f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 17728210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>Method documentation for this class describes mechanics, 1773f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * not behavioral specifications from the point of view of Lock 1774f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and Condition users. Exported versions of this class will in 1775f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * general need to be accompanied by documentation describing 1776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * condition semantics that rely on those of the associated 1777f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <tt>AbstractQueuedSynchronizer</tt>. 17788210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 17798210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <p>This class is Serializable, but all fields are transient, 1780f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * so deserialized conditions have no waiters. 1781f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1782f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public class ConditionObject implements Condition, java.io.Serializable { 1783f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final long serialVersionUID = 1173984872572414699L; 1784f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** First node of condition queue. */ 1785f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private transient Node firstWaiter; 1786f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** Last node of condition queue. */ 1787f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private transient Node lastWaiter; 1788f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1789f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1790f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Creates a new <tt>ConditionObject</tt> instance. 1791f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1792f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public ConditionObject() { } 1793f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1794f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Internal methods 1795f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1796f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 17978210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Adds a new waiter to wait queue. 1798f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return its new wait node 1799f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1800f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private Node addConditionWaiter() { 1801f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node t = lastWaiter; 18028210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson // If lastWaiter is cancelled, clean out. 18038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (t != null && t.waitStatus != Node.CONDITION) { 18048210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson unlinkCancelledWaiters(); 18058210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson t = lastWaiter; 18068210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 18078210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node node = new Node(Thread.currentThread(), Node.CONDITION); 18088210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (t == null) 1809f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project firstWaiter = node; 18108210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson else 1811f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project t.nextWaiter = node; 1812f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project lastWaiter = node; 1813f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return node; 1814f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1815f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1816f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 18178210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Removes and transfers nodes until hit non-cancelled one or 1818f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * null. Split out from signal in part to encourage compilers 1819f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to inline the case of no waiters. 1820f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param first (non-null) the first node on condition queue 1821f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1822f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void doSignal(Node first) { 1823f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project do { 18248210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if ( (firstWaiter = first.nextWaiter) == null) 1825f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project lastWaiter = null; 1826f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project first.nextWaiter = null; 1827f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } while (!transferForSignal(first) && 1828f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (first = firstWaiter) != null); 1829f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1830f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1831f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 18328210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Removes and transfers all nodes. 1833f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param first (non-null) the first node on condition queue 1834f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1835f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void doSignalAll(Node first) { 18368210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson lastWaiter = firstWaiter = null; 1837f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project do { 1838f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node next = first.nextWaiter; 1839f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project first.nextWaiter = null; 1840f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project transferForSignal(first); 1841f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project first = next; 1842f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } while (first != null); 1843f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1844f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 18458210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 18468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Unlinks cancelled waiter nodes from condition queue. 18478210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Called only while holding lock. This is called when 18488210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * cancellation occurred during condition wait, and upon 18498210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * insertion of a new waiter when lastWaiter is seen to have 18508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * been cancelled. This method is needed to avoid garbage 18518210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * retention in the absence of signals. So even though it may 18528210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * require a full traversal, it comes into play only when 18538210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * timeouts or cancellations occur in the absence of 18548210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * signals. It traverses all nodes rather than stopping at a 18558210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * particular target to unlink all pointers to garbage nodes 18568210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * without requiring many re-traversals during cancellation 18578210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * storms. 18588210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 18598210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private void unlinkCancelledWaiters() { 18608210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node t = firstWaiter; 18618210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node trail = null; 18628210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson while (t != null) { 18638210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node next = t.nextWaiter; 18648210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (t.waitStatus != Node.CONDITION) { 18658210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson t.nextWaiter = null; 18668210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (trail == null) 18678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson firstWaiter = next; 18688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson else 18698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson trail.nextWaiter = next; 18708210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (next == null) 18718210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson lastWaiter = trail; 18728210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 18738210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson else 18748210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson trail = t; 18758210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson t = next; 18768210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 18778210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 18788210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 1879f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // public methods 1880f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1881f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1882f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Moves the longest-waiting thread, if one exists, from the 1883f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * wait queue for this condition to the wait queue for the 1884f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * owning lock. 18858210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1886f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 18878210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * returns {@code false} 1888f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1889f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final void signal() { 18908210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (!isHeldExclusively()) 1891f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalMonitorStateException(); 1892f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node first = firstWaiter; 1893f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (first != null) 1894f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project doSignal(first); 1895f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 18968210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 1897f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1898f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Moves all threads from the wait queue for this condition to 1899f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the wait queue for the owning lock. 19008210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1901f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 19028210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * returns {@code false} 1903f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1904f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final void signalAll() { 19058210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (!isHeldExclusively()) 1906f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalMonitorStateException(); 1907f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node first = firstWaiter; 19088210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (first != null) 1909f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project doSignalAll(first); 1910f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1911f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1912f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1913f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Implements uninterruptible condition wait. 1914f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <ol> 19158210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Save lock state returned by {@link #getState}. 19168210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Invoke {@link #release} with 19178210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * saved state as argument, throwing 19188210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * IllegalMonitorStateException if it fails. 19198210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Block until signalled. 1920f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li> Reacquire by invoking specialized version of 1921f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link #acquire} with saved state as argument. 1922f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * </ol> 1923f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1924f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final void awaitUninterruptibly() { 1925f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node node = addConditionWaiter(); 1926f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int savedState = fullyRelease(node); 1927f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean interrupted = false; 1928f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!isOnSyncQueue(node)) { 1929f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LockSupport.park(); 19308210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (Thread.interrupted()) 1931f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project interrupted = true; 1932f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1933f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (acquireQueued(node, savedState) || interrupted) 1934f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project selfInterrupt(); 1935f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1936f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1937f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 1938f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * For interruptible waits, we need to track whether to throw 1939f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * InterruptedException, if interrupted while blocked on 1940f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * condition, versus reinterrupt current thread, if 1941f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * interrupted while blocked waiting to re-acquire. 1942f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1943f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1944f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** Mode meaning to reinterrupt on exit from wait */ 1945f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int REINTERRUPT = 1; 1946f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** Mode meaning to throw InterruptedException on exit from wait */ 1947f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final int THROW_IE = -1; 1948f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1949f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 19508210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Checks for interrupt, returning THROW_IE if interrupted 1951f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * before signalled, REINTERRUPT if after signalled, or 1952f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 0 if not interrupted. 1953f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1954f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int checkInterruptWhileWaiting(Node node) { 19558210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return Thread.interrupted() ? 19568210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) : 1957f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 0; 1958f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1959f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1960f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 19618210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Throws InterruptedException, reinterrupts current thread, or 19628210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * does nothing, depending on mode. 1963f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 19648210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private void reportInterruptAfterWait(int interruptMode) 1965f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throws InterruptedException { 1966f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (interruptMode == THROW_IE) 1967f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new InterruptedException(); 1968f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project else if (interruptMode == REINTERRUPT) 19698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson selfInterrupt(); 1970f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 1971f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 1972f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 1973f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Implements interruptible condition wait. 1974f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <ol> 19758210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> If current thread is interrupted, throw InterruptedException. 19768210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Save lock state returned by {@link #getState}. 19778210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Invoke {@link #release} with 19788210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * saved state as argument, throwing 19798210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * IllegalMonitorStateException if it fails. 19808210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Block until signalled or interrupted. 1981f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li> Reacquire by invoking specialized version of 1982f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link #acquire} with saved state as argument. 19838210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> If interrupted while blocked in step 4, throw InterruptedException. 1984f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * </ol> 19858210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 1986f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws InterruptedException if the current thread is interrupted (and 1987f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * interruption of thread suspension is supported). 1988f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 1989f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final void await() throws InterruptedException { 19908210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (Thread.interrupted()) 1991f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new InterruptedException(); 1992f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node node = addConditionWaiter(); 1993f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int savedState = fullyRelease(node); 1994f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int interruptMode = 0; 1995f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!isOnSyncQueue(node)) { 1996f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LockSupport.park(); 1997f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 1998f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 1999f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2000f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 2001f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project interruptMode = REINTERRUPT; 20028210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (node.nextWaiter != null) // clean up if cancelled 20038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson unlinkCancelledWaiters(); 2004f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (interruptMode != 0) 2005f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reportInterruptAfterWait(interruptMode); 2006f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2007f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2008f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 2009f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Implements timed condition wait. 2010f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <ol> 20118210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> If current thread is interrupted, throw InterruptedException. 20128210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Save lock state returned by {@link #getState}. 20138210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Invoke {@link #release} with 20148210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * saved state as argument, throwing 20158210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * IllegalMonitorStateException if it fails. 20168210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Block until signalled, interrupted, or timed out. 2017f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li> Reacquire by invoking specialized version of 2018f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link #acquire} with saved state as argument. 20198210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> If interrupted while blocked in step 4, throw InterruptedException. 2020f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * </ol> 20218210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 2022f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param nanosTimeout the maximum time to wait, in nanoseconds 2023f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return A value less than or equal to zero if the wait has 2024f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * timed out; otherwise an estimate, that 2025f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is strictly less than the <tt>nanosTimeout</tt> argument, 2026f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * of the time still remaining when this method returned. 2027f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2028f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws InterruptedException if the current thread is interrupted (and 2029f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * interruption of thread suspension is supported). 2030f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 2031f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final long awaitNanos(long nanosTimeout) throws InterruptedException { 20328210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (Thread.interrupted()) 2033f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new InterruptedException(); 2034f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node node = addConditionWaiter(); 2035f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int savedState = fullyRelease(node); 2036f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project long lastTime = System.nanoTime(); 2037f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int interruptMode = 0; 2038f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!isOnSyncQueue(node)) { 2039f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (nanosTimeout <= 0L) { 20408210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson transferAfterCancelledWait(node); 2041f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 2042f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2043f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LockSupport.parkNanos(nanosTimeout); 2044f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 2045f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 20468210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 2047f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project long now = System.nanoTime(); 2048f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nanosTimeout -= now - lastTime; 2049f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project lastTime = now; 2050f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2051f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 2052f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project interruptMode = REINTERRUPT; 20538210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (node.nextWaiter != null) 20548210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson unlinkCancelledWaiters(); 2055f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (interruptMode != 0) 2056f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reportInterruptAfterWait(interruptMode); 2057f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return nanosTimeout - (System.nanoTime() - lastTime); 2058f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2059f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2060f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 2061f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Implements absolute timed condition wait. 2062f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <ol> 20638210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> If current thread is interrupted, throw InterruptedException. 20648210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Save lock state returned by {@link #getState}. 20658210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Invoke {@link #release} with 20668210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * saved state as argument, throwing 20678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * IllegalMonitorStateException if it fails. 20688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Block until signalled, interrupted, or timed out. 2069f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li> Reacquire by invoking specialized version of 2070f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link #acquire} with saved state as argument. 20718210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> If interrupted while blocked in step 4, throw InterruptedException. 20728210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> If timed out while blocked in step 4, return false, else true. 2073f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * </ol> 20748210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 2075f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param deadline the absolute time to wait until 2076f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return <tt>false</tt> if the deadline has 2077f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * elapsed upon return, else <tt>true</tt>. 2078f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 2079f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws InterruptedException if the current thread is interrupted (and 2080f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * interruption of thread suspension is supported). 2081f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 2082f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final boolean awaitUntil(Date deadline) throws InterruptedException { 2083f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (deadline == null) 2084f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException(); 2085f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project long abstime = deadline.getTime(); 20868210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (Thread.interrupted()) 2087f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new InterruptedException(); 2088f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node node = addConditionWaiter(); 2089f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int savedState = fullyRelease(node); 2090f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean timedout = false; 2091f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int interruptMode = 0; 2092f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!isOnSyncQueue(node)) { 2093f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (System.currentTimeMillis() > abstime) { 20948210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson timedout = transferAfterCancelledWait(node); 2095f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 2096f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2097f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LockSupport.parkUntil(abstime); 2098f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 2099f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 2100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 2102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project interruptMode = REINTERRUPT; 21038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (node.nextWaiter != null) 21048210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson unlinkCancelledWaiters(); 2105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (interruptMode != 0) 2106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reportInterruptAfterWait(interruptMode); 2107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return !timedout; 2108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 21098210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 2110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 21118210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Implements timed condition wait. 2112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <ol> 21138210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> If current thread is interrupted, throw InterruptedException. 21148210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Save lock state returned by {@link #getState}. 21158210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Invoke {@link #release} with 21168210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * saved state as argument, throwing 21178210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * IllegalMonitorStateException if it fails. 21188210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> Block until signalled, interrupted, or timed out. 2119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li> Reacquire by invoking specialized version of 2120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * {@link #acquire} with saved state as argument. 21218210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> If interrupted while blocked in step 4, throw InterruptedException. 21228210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * <li> If timed out while blocked in step 4, return false, else true. 2123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * </ol> 21248210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 2125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param time the maximum time to wait 2126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param unit the time unit of the <tt>time</tt> argument. 2127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return <tt>false</tt> if the waiting time detectably elapsed 2128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * before return from the method, else <tt>true</tt>. 2129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws InterruptedException if the current thread is interrupted (and 2130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * interruption of thread suspension is supported). 2131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 2132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public final boolean await(long time, TimeUnit unit) throws InterruptedException { 2133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (unit == null) 2134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException(); 2135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project long nanosTimeout = unit.toNanos(time); 21368210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (Thread.interrupted()) 2137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new InterruptedException(); 2138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Node node = addConditionWaiter(); 2139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int savedState = fullyRelease(node); 2140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project long lastTime = System.nanoTime(); 2141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean timedout = false; 2142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int interruptMode = 0; 2143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project while (!isOnSyncQueue(node)) { 2144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (nanosTimeout <= 0L) { 21458210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson timedout = transferAfterCancelledWait(node); 2146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 2147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 21488210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (nanosTimeout >= spinForTimeoutThreshold) 21498210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson LockSupport.parkNanos(nanosTimeout); 2150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 2151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 2152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project long now = System.nanoTime(); 2153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project nanosTimeout -= now - lastTime; 2154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project lastTime = now; 2155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 2157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project interruptMode = REINTERRUPT; 21588210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (node.nextWaiter != null) 21598210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson unlinkCancelledWaiters(); 2160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (interruptMode != 0) 2161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reportInterruptAfterWait(interruptMode); 2162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return !timedout; 2163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // support for instrumentation 2166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 2168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns true if this condition was created by the given 21698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * synchronization object. 21708210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 21718210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if owned 2172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 2173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project final boolean isOwnedBy(AbstractQueuedSynchronizer sync) { 2174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return sync == AbstractQueuedSynchronizer.this; 2175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 2178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Queries whether any threads are waiting on this condition. 21798210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Implements {@link AbstractQueuedSynchronizer#hasWaiters}. 21808210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 21818210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return {@code true} if there are any waiting threads 2182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 21838210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * returns {@code false} 21848210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 2185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected final boolean hasWaiters() { 21868210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (!isHeldExclusively()) 2187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalMonitorStateException(); 2188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (Node w = firstWaiter; w != null; w = w.nextWaiter) { 2189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (w.waitStatus == Node.CONDITION) 2190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 2191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 2193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 2196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns an estimate of the number of threads waiting on 21978210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * this condition. 21988210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Implements {@link AbstractQueuedSynchronizer#getWaitQueueLength}. 21998210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 22008210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * @return the estimated number of waiting threads 2201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 22028210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * returns {@code false} 22038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 2204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected final int getWaitQueueLength() { 22058210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (!isHeldExclusively()) 2206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalMonitorStateException(); 2207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int n = 0; 2208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (Node w = firstWaiter; w != null; w = w.nextWaiter) { 2209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (w.waitStatus == Node.CONDITION) 2210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ++n; 2211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return n; 2213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 2216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns a collection containing those threads that may be 22178210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * waiting on this Condition. 22188210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * Implements {@link AbstractQueuedSynchronizer#getWaitingThreads}. 22198210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * 2220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return the collection of threads 2221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 22228210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * returns {@code false} 2223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 2224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project protected final Collection<Thread> getWaitingThreads() { 22258210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson if (!isHeldExclusively()) 2226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalMonitorStateException(); 2227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<Thread> list = new ArrayList<Thread>(); 2228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (Node w = firstWaiter; w != null; w = w.nextWaiter) { 2229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (w.waitStatus == Node.CONDITION) { 2230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Thread t = w.thread; 2231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (t != null) 2232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project list.add(t); 2233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return list; 2236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 2240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Setup to support compareAndSet. We need to natively implement 2241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * this here: For the sake of permitting future enhancements, we 2242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * cannot explicitly subclass AtomicInteger, which would be 2243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * efficient and useful otherwise. So, as the lesser of evils, we 2244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * natively implement using hotspot intrinsics API. And while we 2245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are at it, we do the same for other CASable fields (which could 2246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * otherwise be done with atomic field updaters). 2247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 2248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // BEGIN android-changed 2249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final Unsafe unsafe = UnsafeAccess.THE_ONE; 2250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // END android-changed 2251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final long stateOffset; 2252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final long headOffset; 2253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final long tailOffset; 2254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static final long waitStatusOffset; 22558210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private static final long nextOffset; 2256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project static { 2258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 2259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project stateOffset = unsafe.objectFieldOffset 2260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (AbstractQueuedSynchronizer.class.getDeclaredField("state")); 2261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project headOffset = unsafe.objectFieldOffset 2262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (AbstractQueuedSynchronizer.class.getDeclaredField("head")); 2263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project tailOffset = unsafe.objectFieldOffset 2264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (AbstractQueuedSynchronizer.class.getDeclaredField("tail")); 2265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project waitStatusOffset = unsafe.objectFieldOffset 2266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (Node.class.getDeclaredField("waitStatus")); 22678210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson nextOffset = unsafe.objectFieldOffset 22688210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson (Node.class.getDeclaredField("next")); 22698210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 22708210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } catch (Exception ex) { throw new Error(ex); } 2271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 22748210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * CAS head field. Used only by enq. 2275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 2276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final boolean compareAndSetHead(Node update) { 2277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return unsafe.compareAndSwapObject(this, headOffset, null, update); 2278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 22798210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson 2280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 22818210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * CAS tail field. Used only by enq. 2282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 2283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final boolean compareAndSetTail(Node expect, Node update) { 2284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return unsafe.compareAndSwapObject(this, tailOffset, expect, update); 2285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 2288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * CAS waitStatus field of a node. 2289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 22908210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private final static boolean compareAndSetWaitStatus(Node node, 22918210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson int expect, 2292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int update) { 22938210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return unsafe.compareAndSwapInt(node, waitStatusOffset, 2294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project expect, update); 2295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 2296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 22978210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson /** 22988210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson * CAS next field of a node. 22998210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson */ 23008210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson private final static boolean compareAndSetNext(Node node, 23018210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node expect, 23028210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson Node update) { 23038210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson return unsafe.compareAndSwapObject(node, nextOffset, expect, update); 23048210fadf25ece2a0db4cd0428d7f27d7166310b9Jesse Wilson } 2305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 2306