1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is free software; you can redistribute it and/or modify it 529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * under the terms of the GNU General Public License version 2 only, as 629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * published by the Free Software Foundation. Oracle designates this 729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * particular file as subject to the "Classpath" exception as provided 829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * by Oracle in the LICENSE file that accompanied this code. 929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is distributed in the hope that it will be useful, but WITHOUT 1129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * version 2 for more details (a copy is included in the LICENSE file that 1429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * accompanied this code). 1529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * You should have received a copy of the GNU General Public License version 1729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2 along with this work; if not, write to the Free Software Foundation, 1829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * or visit www.oracle.com if you need additional information or have any 2229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * questions. 2329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer */ 2429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer 2529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer/* 2629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This file is available under and governed by the GNU General Public 2729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * License version 2 only, as published by the Free Software Foundation. 2829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * However, the following notice accompanied the original version of this 2929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * file: 3029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 31adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Written by Doug Lea with assistance from members of JCP JSR-166 32adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Expert Group and released to the public domain, as explained at 33a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 34adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 35adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util.concurrent.locks; 37aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath 3891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravleimport java.util.ArrayList; 3991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravleimport java.util.Collection; 4091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravleimport java.util.Date; 41b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.concurrent.TimeUnit; 42d7806194431c008c2ae2b546b988c0e819f7b47bJesse Wilson 43adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 44adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Provides a framework for implementing blocking locks and related 45adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * synchronizers (semaphores, events, etc) that rely on 46adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * first-in-first-out (FIFO) wait queues. This class is designed to 47adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * be a useful basis for most kinds of synchronizers that rely on a 4891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * single atomic {@code int} value to represent state. Subclasses 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * must define the protected methods that change this state, and which 50adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * define what that state means in terms of this object being acquired 51adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * or released. Given these, the other methods in this class carry 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * out all queuing and blocking mechanics. Subclasses can maintain 5391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * other state fields, but only the atomically updated {@code int} 54adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * value manipulated using methods {@link #getState}, {@link 55adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * #setState} and {@link #compareAndSetState} is tracked with respect 56adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * to synchronization. 57adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>Subclasses should be defined as non-public internal helper 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * classes that are used to implement the synchronization properties 60adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * of their enclosing class. Class 6191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * {@code AbstractQueuedSynchronizer} does not implement any 62adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * synchronization interface. Instead it defines methods such as 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link #acquireInterruptibly} that can be invoked as 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * appropriate by concrete locks and related synchronizers to 65bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * implement their public methods. 66adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 67adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>This class supports either or both a default <em>exclusive</em> 68adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * mode and a <em>shared</em> mode. When acquired in exclusive mode, 69adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * attempted acquires by other threads cannot succeed. Shared mode 70adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * acquires by multiple threads may (but need not) succeed. This class 71adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * does not "understand" these differences except in the 72adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * mechanical sense that when a shared mode acquire succeeds, the next 73adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * waiting thread (if one exists) must also determine whether it can 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * acquire as well. Threads waiting in the different modes share the 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * same FIFO queue. Usually, implementation subclasses support only 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * one of these modes, but both can come into play for example in a 77adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link ReadWriteLock}. Subclasses that support only exclusive or 78adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * only shared modes need not define the methods supporting the unused mode. 79adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>This class defines a nested {@link ConditionObject} class that 81adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * can be used as a {@link Condition} implementation by subclasses 82adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * supporting exclusive mode for which method {@link 83adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * #isHeldExclusively} reports whether synchronization is exclusively 84adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * held with respect to the current thread, method {@link #release} 85adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * invoked with the current {@link #getState} value fully releases 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * this object, and {@link #acquire}, given this saved state value, 87adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * eventually restores this object to its previous acquired state. No 8891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * {@code AbstractQueuedSynchronizer} method otherwise creates such a 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * condition, so if this constraint cannot be met, do not use it. The 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * behavior of {@link ConditionObject} depends of course on the 91adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * semantics of its synchronizer implementation. 92bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 93bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This class provides inspection, instrumentation, and monitoring 94adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * methods for the internal queue, as well as similar methods for 95adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * condition objects. These can be exported as desired into classes 9691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * using an {@code AbstractQueuedSynchronizer} for their 97adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * synchronization mechanics. 98adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 99bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Serialization of this class stores only the underlying atomic 100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * integer maintaining state, so deserialized objects have empty 101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * thread queues. Typical subclasses requiring serializability will 10291770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * define a {@code readObject} method that restores this to a known 103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * initial state upon deserialization. 104adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <h3>Usage</h3> 106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 107bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>To use this class as the basis of a synchronizer, redefine the 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * following methods, as applicable, by inspecting and/or modifying 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the synchronization state using {@link #getState}, {@link 110bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * #setState} and/or {@link #compareAndSetState}: 111adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 112adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <ul> 113b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>{@link #tryAcquire} 114b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>{@link #tryRelease} 115b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>{@link #tryAcquireShared} 116b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>{@link #tryReleaseShared} 117b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>{@link #isHeldExclusively} 11891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * </ul> 119adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 120adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Each of these methods by default throws {@link 121adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * UnsupportedOperationException}. Implementations of these methods 122adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * must be internally thread-safe, and should in general be short and 123adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * not block. Defining these methods is the <em>only</em> supported 124adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * means of using this class. All other methods are declared 12591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * {@code final} because they cannot be independently varied. 126adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>You may also find the inherited methods from {@link 1286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * AbstractOwnableSynchronizer} useful to keep track of the thread 1296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * owning an exclusive synchronizer. You are encouraged to use them 1306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * -- this enables monitoring and diagnostic tools to assist users in 1316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * determining which threads hold locks. 1326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 133bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Even though this class is based on an internal FIFO queue, it 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * does not automatically enforce FIFO acquisition policies. The core 135adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * of exclusive synchronization takes the form: 136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <pre> 138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Acquire: 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * while (!tryAcquire(arg)) { 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <em>enqueue thread if it is not already queued</em>; 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <em>possibly block current thread</em>; 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * } 143adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Release: 145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if (tryRelease(arg)) 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <em>unblock the first queued thread</em>; 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * </pre> 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * (Shared mode is similar but may involve cascading signals.) 150adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 15191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * <p id="barging">Because checks in acquire are invoked before 152bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * enqueuing, a newly acquiring thread may <em>barge</em> ahead of 15391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * others that are blocked and queued. However, you can, if desired, 15491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * define {@code tryAcquire} and/or {@code tryAcquireShared} to 155bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * disable barging by internally invoking one or more of the inspection 156aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath * methods, thereby providing a <em>fair</em> FIFO acquisition order. 157aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath * In particular, most fair synchronizers can define {@code tryAcquire} 158b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * to return {@code false} if {@link #hasQueuedPredecessors} (a method 159aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath * specifically designed to be used by fair synchronizers) returns 160aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath * {@code true}. Other variations are possible. 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 162bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Throughput and scalability are generally highest for the 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * default barging (also known as <em>greedy</em>, 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <em>renouncement</em>, and <em>convoy-avoidance</em>) strategy. 165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * While this is not guaranteed to be fair or starvation-free, earlier 166adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queued threads are allowed to recontend before later queued 167adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * threads, and each recontention has an unbiased chance to succeed 168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * against incoming threads. Also, while acquires do not 169adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * "spin" in the usual sense, they may perform multiple 17091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * invocations of {@code tryAcquire} interspersed with other 171adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * computations before blocking. This gives most of the benefits of 172adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * spins when exclusive synchronization is only briefly held, without 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * most of the liabilities when it isn't. If so desired, you can 174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * augment this by preceding calls to acquire methods with 175adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * "fast-path" checks, possibly prechecking {@link #hasContended} 176adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and/or {@link #hasQueuedThreads} to only do so if the synchronizer 177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is likely not to be contended. 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 179bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This class provides an efficient and scalable basis for 180adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * synchronization in part by specializing its range of use to 18191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * synchronizers that can rely on {@code int} state, acquire, and 182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * release parameters, and an internal FIFO wait queue. When this does 183adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * not suffice, you can build synchronizers from a lower level using 184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link java.util.concurrent.atomic atomic} classes, your own custom 185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link java.util.Queue} classes, and {@link LockSupport} blocking 186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * support. 187bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 188adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <h3>Usage Examples</h3> 189adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 190adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>Here is a non-reentrant mutual exclusion lock class that uses 191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the value zero to represent the unlocked state, and one to 1926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * represent the locked state. While a non-reentrant lock 1936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * does not strictly require recording of the current owner 1946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * thread, this class does so anyway to make usage easier to monitor. 1956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * It also supports conditions and exposes 196adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * one of the instrumentation methods: 197adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 198b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * class Mutex implements Lock, java.io.Serializable { 200adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 201bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * // Our internal helper class 202bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * private static class Sync extends AbstractQueuedSynchronizer { 20391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * // Reports whether in locked state 204bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * protected boolean isHeldExclusively() { 205bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * return getState() == 1; 206bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 207adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 20891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * // Acquires the lock if state is zero 209bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public boolean tryAcquire(int acquires) { 210bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * assert acquires == 1; // Otherwise unused 2116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * if (compareAndSetState(0, 1)) { 2126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * setExclusiveOwnerThread(Thread.currentThread()); 2136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * return true; 2146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * } 2156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * return false; 216bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 217adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 21891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * // Releases the lock by setting state to zero 219bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * protected boolean tryRelease(int releases) { 220bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * assert releases == 1; // Otherwise unused 221bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * if (getState() == 0) throw new IllegalMonitorStateException(); 2226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * setExclusiveOwnerThread(null); 223bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * setState(0); 224bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * return true; 225bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 226bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 22791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * // Provides a Condition 228bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Condition newCondition() { return new ConditionObject(); } 229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 23091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * // Deserializes properly 231bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * private void readObject(ObjectInputStream s) 232bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * throws IOException, ClassNotFoundException { 233bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * s.defaultReadObject(); 234bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * setState(0); // reset to unlocked state 235bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 236bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 237adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 238bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * // The sync object does all the hard work. We just forward to it. 239bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * private final Sync sync = new Sync(); 240adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 241bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public void lock() { sync.acquire(1); } 242bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public boolean tryLock() { return sync.tryAcquire(1); } 243bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public void unlock() { sync.release(1); } 244bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public Condition newCondition() { return sync.newCondition(); } 245bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public boolean isLocked() { return sync.isHeldExclusively(); } 246bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public boolean hasQueuedThreads() { return sync.hasQueuedThreads(); } 247bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public void lockInterruptibly() throws InterruptedException { 248bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * sync.acquireInterruptibly(1); 249bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 250bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public boolean tryLock(long timeout, TimeUnit unit) 251bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * throws InterruptedException { 252bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * return sync.tryAcquireNanos(1, unit.toNanos(timeout)); 253bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 254a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }}</pre> 255adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 25691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * <p>Here is a latch class that is like a 25791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * {@link java.util.concurrent.CountDownLatch CountDownLatch} 25891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * except that it only requires a single {@code signal} to 25991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * fire. Because a latch is non-exclusive, it uses the {@code shared} 260adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * acquire and release methods. 261adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 262b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 263adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * class BooleanLatch { 264adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 265bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * private static class Sync extends AbstractQueuedSynchronizer { 266bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * boolean isSignalled() { return getState() != 0; } 267adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 268bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * protected int tryAcquireShared(int ignore) { 2698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * return isSignalled() ? 1 : -1; 270bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 271adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 272bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * protected boolean tryReleaseShared(int ignore) { 273bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * setState(1); 274bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * return true; 275bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 276bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 278bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * private final Sync sync = new Sync(); 279bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public boolean isSignalled() { return sync.isSignalled(); } 280bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public void signal() { sync.releaseShared(1); } 281bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public void await() throws InterruptedException { 282bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * sync.acquireSharedInterruptibly(1); 283bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 284a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * }}</pre> 285adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 286adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @since 1.5 287adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @author Doug Lea 288adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 289bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilsonpublic abstract class AbstractQueuedSynchronizer 290bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson extends AbstractOwnableSynchronizer 291bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson implements java.io.Serializable { 292bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 293adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = 7373984972572414691L; 294adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 295adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 29691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Creates a new {@code AbstractQueuedSynchronizer} instance 297adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * with initial synchronization state of zero. 298adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 299adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected AbstractQueuedSynchronizer() { } 300adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 301adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 302adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Wait queue node class. 303adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 304bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>The wait queue is a variant of a "CLH" (Craig, Landin, and 305adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Hagersten) lock queue. CLH locks are normally used for 306adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * spinlocks. We instead use them for blocking synchronizers, but 307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * use the same basic tactic of holding some of the control 308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * information about a thread in the predecessor of its node. A 309adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * "status" field in each node keeps track of whether a thread 310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * should block. A node is signalled when its predecessor 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * releases. Each node of the queue otherwise serves as a 312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * specific-notification-style monitor holding a single waiting 313adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * thread. The status field does NOT control whether threads are 314adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * granted locks etc though. A thread may try to acquire if it is 315adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * first in the queue. But being first does not guarantee success; 316adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * it only gives the right to contend. So the currently released 317adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * contender thread may need to rewait. 318adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 319adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>To enqueue into a CLH lock, you atomically splice it in as new 320bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * tail. To dequeue, you just set the head field. 321adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <pre> 322adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * +------+ prev +-----+ +-----+ 323adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * head | | <---- | | <---- | | tail 324adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * +------+ +-----+ +-----+ 325adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * </pre> 326adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 327adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>Insertion into a CLH queue requires only a single atomic 328adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * operation on "tail", so there is a simple atomic point of 32991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * demarcation from unqueued to queued. Similarly, dequeuing 330adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * involves only updating the "head". However, it takes a bit 331adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * more work for nodes to determine who their successors are, 332adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * in part to deal with possible cancellation due to timeouts 333adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and interrupts. 334adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 335adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>The "prev" links (not used in original CLH locks), are mainly 336adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * needed to handle cancellation. If a node is cancelled, its 337adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * successor is (normally) relinked to a non-cancelled 338adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * predecessor. For explanation of similar mechanics in the case 339adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * of spin locks, see the papers by Scott and Scherer at 340adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * http://www.cs.rochester.edu/u/scott/synchronization/ 341bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 342adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>We also use "next" links to implement blocking mechanics. 343adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The thread id for each node is kept in its own node, so a 344adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * predecessor signals the next node to wake up by traversing 345adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * next link to determine which thread it is. Determination of 346adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * successor must avoid races with newly queued nodes to set 347adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the "next" fields of their predecessors. This is solved 348adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * when necessary by checking backwards from the atomically 349adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * updated "tail" when a node's successor appears to be null. 350adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * (Or, said differently, the next-links are an optimization 351adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * so that we don't usually need a backward scan.) 352adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 353adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>Cancellation introduces some conservatism to the basic 354adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * algorithms. Since we must poll for cancellation of other 355adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * nodes, we can miss noticing whether a cancelled node is 356adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * ahead or behind us. This is dealt with by always unparking 357adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * successors upon cancellation, allowing them to stabilize on 358bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * a new predecessor, unless we can identify an uncancelled 359bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * predecessor who will carry this responsibility. 360adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 361adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>CLH queues need a dummy header node to get started. But 362adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * we don't create them on construction, because it would be wasted 363adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * effort if there is never contention. Instead, the node 364adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is constructed and head and tail pointers are set upon first 365adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * contention. 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 367adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>Threads waiting on Conditions use the same nodes, but 368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * use an additional link. Conditions only need to link nodes 369adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * in simple (non-concurrent) linked queues because they are 370adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * only accessed when exclusively held. Upon await, a node is 371adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * inserted into a condition queue. Upon signal, the node is 372adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * transferred to the main queue. A special value of status 373adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * field is used to mark which queue a node is on. 374adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 375adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill 376adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Scherer and Michael Scott, along with members of JSR-166 377adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * expert group, for helpful ideas, discussions, and critiques 378adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * on the design of this class. 379adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 380adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static final class Node { 381bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** Marker to indicate a node is waiting in shared mode */ 382bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson static final Node SHARED = new Node(); 383bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** Marker to indicate a node is waiting in exclusive mode */ 384bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson static final Node EXCLUSIVE = null; 385bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 386b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** waitStatus value to indicate thread has cancelled. */ 387adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static final int CANCELLED = 1; 388b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** waitStatus value to indicate successor's thread needs unparking. */ 389adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static final int SIGNAL = -1; 390b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** waitStatus value to indicate thread is waiting on condition. */ 391adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static final int CONDITION = -2; 392bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 393bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * waitStatus value to indicate the next acquireShared should 394b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * unconditionally propagate. 395bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 396bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson static final int PROPAGATE = -3; 397adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 399adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Status field, taking on only the values: 400bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * SIGNAL: The successor of this node is (or will soon be) 401bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * blocked (via park), so the current node must 402bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * unpark its successor when it releases or 403adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * cancels. To avoid races, acquire methods must 404bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * first indicate they need a signal, 405bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * then retry the atomic acquire, and then, 406adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * on failure, block. 407bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * CANCELLED: This node is cancelled due to timeout or interrupt. 408adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Nodes never leave this state. In particular, 409adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * a thread with cancelled node never again blocks. 410bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * CONDITION: This node is currently on a condition queue. 411bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * It will not be used as a sync queue node 412bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * until transferred, at which time the status 413bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * will be set to 0. (Use of this value here has 414bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * nothing to do with the other uses of the 415bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * field, but simplifies mechanics.) 416bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * PROPAGATE: A releaseShared should be propagated to other 417bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * nodes. This is set (for head node only) in 418bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * doReleaseShared to ensure propagation 419bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * continues, even if other operations have 420bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * since intervened. 421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 0: None of the above 422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 423adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The values are arranged numerically to simplify use. 424adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Non-negative values mean that a node doesn't need to 425adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * signal. So, most code doesn't need to check for particular 426adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * values, just for sign. 427adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 428adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The field is initialized to 0 for normal sync nodes, and 429bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * CONDITION for condition nodes. It is modified using CAS 430bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (or when possible, unconditional volatile writes). 431adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 432adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project volatile int waitStatus; 433adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 434adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 435adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Link to predecessor node that current node/thread relies on 43691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * for checking waitStatus. Assigned during enqueuing, and nulled 437adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * out (for sake of GC) only upon dequeuing. Also, upon 438adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * cancellation of a predecessor, we short-circuit while 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * finding a non-cancelled one, which will always exist 440adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * because the head node is never cancelled: A node becomes 441adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * head only as a result of successful acquire. A 442adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * cancelled thread never succeeds in acquiring, and a thread only 443adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * cancels itself, not any other node. 444adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 445adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project volatile Node prev; 446adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 447adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 448adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Link to the successor node that the current node/thread 449bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * unparks upon release. Assigned during enqueuing, adjusted 450bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * when bypassing cancelled predecessors, and nulled out (for 451bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * sake of GC) when dequeued. The enq operation does not 452bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * assign next field of a predecessor until after attachment, 453bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * so seeing a null next field does not necessarily mean that 454bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * node is at end of queue. However, if a next field appears 455bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to be null, we can scan prev's from the tail to 456bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * double-check. The next field of cancelled nodes is set to 457bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * point to the node itself instead of null, to make life 458bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * easier for isOnSyncQueue. 459adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 460adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project volatile Node next; 461adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 462adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 463adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The thread that enqueued this node. Initialized on 464bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * construction and nulled out after use. 465adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 466adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project volatile Thread thread; 467adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 468bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 469adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Link to next node waiting on condition, or the special 470adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * value SHARED. Because condition queues are accessed only 471adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * when holding in exclusive mode, we just need a simple 472adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * linked queue to hold nodes while they are waiting on 473adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * conditions. They are then transferred to the queue to 474adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * re-acquire. And because conditions can only be exclusive, 475adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * we save a field by using special value to indicate shared 476adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * mode. 477adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 478adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node nextWaiter; 479adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 480adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 48191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Returns true if node is waiting in shared mode. 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 483adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final boolean isShared() { 484adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return nextWaiter == SHARED; 485adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 486adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 487adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 488bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns previous node, or throws NullPointerException if null. 489bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Use when predecessor cannot be null. The null check could 490bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be elided, but is present to help the VM. 491bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 492adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the predecessor of this node 493adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 494adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node predecessor() throws NullPointerException { 495adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node p = prev; 496adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p == null) 497bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson throw new NullPointerException(); 498adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project else 499adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return p; 500adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 501adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 502b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Establishes initial head or SHARED marker. */ 503b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node() {} 504b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 505b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Constructor used by addWaiter. */ 506b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node(Node nextWaiter) { 507b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak this.nextWaiter = nextWaiter; 508b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putObject(this, THREAD, Thread.currentThread()); 509b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 510b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 511b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Constructor used by addConditionWaiter. */ 512b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node(int waitStatus) { 513b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putInt(this, WAITSTATUS, waitStatus); 514b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putObject(this, THREAD, Thread.currentThread()); 515adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 516adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 517b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** CASes waitStatus field. */ 518b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final boolean compareAndSetWaitStatus(int expect, int update) { 519b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapInt(this, WAITSTATUS, expect, update); 520adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 521adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 522b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** CASes next field. */ 523b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final boolean compareAndSetNext(Node expect, Node update) { 524b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapObject(this, NEXT, expect, update); 525b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 526b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 527b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 528b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long NEXT; 529b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final long PREV; 530b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long THREAD; 531b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long WAITSTATUS; 532b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static { 533b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak try { 534b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak NEXT = U.objectFieldOffset 535b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Node.class.getDeclaredField("next")); 536b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak PREV = U.objectFieldOffset 537b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Node.class.getDeclaredField("prev")); 538b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak THREAD = U.objectFieldOffset 539b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Node.class.getDeclaredField("thread")); 540b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak WAITSTATUS = U.objectFieldOffset 541b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Node.class.getDeclaredField("waitStatus")); 542b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (ReflectiveOperationException e) { 543b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw new Error(e); 544b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 545adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 546adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 547adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 548bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 549adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Head of the wait queue, lazily initialized. Except for 550adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * initialization, it is modified only via method setHead. Note: 551adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * If head exists, its waitStatus is guaranteed not to be 552adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * CANCELLED. 553adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 554adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private transient volatile Node head; 555adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 556bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 557adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Tail of the wait queue, lazily initialized. Modified only via 558adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * method enq to add new wait node. 559adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 560bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson private transient volatile Node tail; 561adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 562adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 563adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The synchronization state. 564adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 565adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private volatile int state; 566adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 567adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 568adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the current value of synchronization state. 56991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * This operation has memory semantics of a {@code volatile} read. 570adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return current state value 571adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 572adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected final int getState() { 573adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return state; 574adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 575adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 576adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 577adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Sets the value of synchronization state. 57891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * This operation has memory semantics of a {@code volatile} write. 579adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newState the new state value 580adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 581adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected final void setState(int newState) { 582adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project state = newState; 583adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 584adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 585adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 586adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Atomically sets synchronization state to the given updated 587adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * value if the current state value equals the expected value. 58891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * This operation has memory semantics of a {@code volatile} read 589adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and write. 590bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 591adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param expect the expected value 592adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param update the new value 593b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @return {@code true} if successful. False return indicates that the actual 594bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * value was not equal to the expected value. 595adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 596adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected final boolean compareAndSetState(int expect, int update) { 597b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapInt(this, STATE, expect, update); 598adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 599adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 600adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Queuing utilities 601adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 602adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 603bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The number of nanoseconds for which it is faster to spin 604bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * rather than to use timed park. A rough estimate suffices 605bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to improve responsiveness with very short timeouts. 606bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 607b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final long SPIN_FOR_TIMEOUT_THRESHOLD = 1000L; 608bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 609bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 610bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts node into queue, initializing if necessary. See picture above. 611adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param node the node to insert 612adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return node's predecessor 613adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 614b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private Node enq(Node node) { 615adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 616b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node oldTail = tail; 617b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (oldTail != null) { 618b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putObject(node, Node.PREV, oldTail); 619b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (compareAndSetTail(oldTail, node)) { 620b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak oldTail.next = node; 621b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return oldTail; 622ed4f365789d43b1961657195df223a19bf4ef20fPrzemyslaw Szczepaniak } 623b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } else { 624b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak initializeSyncQueue(); 625adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 626adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 627adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 628adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 629adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 630bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Creates and enqueues node for current thread and given mode. 631bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 632adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the new node 634adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 635adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node addWaiter(Node mode) { 636b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node node = new Node(mode); 637b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 638b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (;;) { 639b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node oldTail = tail; 640b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (oldTail != null) { 641b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putObject(node, Node.PREV, oldTail); 642b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (compareAndSetTail(oldTail, node)) { 643b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak oldTail.next = node; 644b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return node; 645b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 646b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } else { 647b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak initializeSyncQueue(); 648adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 649adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 650adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 651adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 652adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 653bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Sets head of queue to be node, thus dequeuing. Called only by 654adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * acquire methods. Also nulls out unused fields for sake of GC 655adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and to suppress unnecessary signals and traversals. 656bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 657bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param node the node 658adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 659adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void setHead(Node node) { 660adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project head = node; 661adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project node.thread = null; 662bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson node.prev = null; 663adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 665adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 666bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Wakes up node's successor, if one exists. 667bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 668adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param node the node 669adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 670adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void unparkSuccessor(Node node) { 671adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 672bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * If status is negative (i.e., possibly needing signal) try 673bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to clear in anticipation of signalling. It is OK if this 674bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * fails or if status is changed by waiting thread. 675adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 676bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson int ws = node.waitStatus; 677bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (ws < 0) 678b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak node.compareAndSetWaitStatus(ws, 0); 679bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 680adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 681adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Thread to unpark is held in successor, which is normally 682adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * just the next node. But if cancelled or apparently null, 683adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * traverse backwards from tail to find the actual 684adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * non-cancelled successor. 685adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 686adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node s = node.next; 687bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (s == null || s.waitStatus > 0) { 688bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson s = null; 689b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (Node p = tail; p != node && p != null; p = p.prev) 690b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p.waitStatus <= 0) 691b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak s = p; 692adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 693bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (s != null) 694bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson LockSupport.unpark(s.thread); 695adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 696adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 697adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 69891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Release action for shared mode -- signals successor and ensures 699bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * propagation. (Note: For exclusive mode, release just amounts 700bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to calling unparkSuccessor of head if it needs signal.) 701bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 702bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson private void doReleaseShared() { 703bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /* 704bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Ensure that a release propagates, even if there are other 705bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * in-progress acquires/releases. This proceeds in the usual 706bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * way of trying to unparkSuccessor of head if it needs 707bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * signal. But if it does not, status is set to PROPAGATE to 708bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * ensure that upon release, propagation continues. 709bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Additionally, we must loop in case a new node is added 710bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * while we are doing this. Also, unlike other uses of 711bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * unparkSuccessor, we need to know if CAS to reset status 712bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * fails, if so rechecking. 713bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 714bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson for (;;) { 715bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node h = head; 716bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (h != null && h != tail) { 717bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson int ws = h.waitStatus; 718bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (ws == Node.SIGNAL) { 719b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (!h.compareAndSetWaitStatus(Node.SIGNAL, 0)) 720bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson continue; // loop to recheck cases 721bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson unparkSuccessor(h); 722bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 723bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson else if (ws == 0 && 724b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak !h.compareAndSetWaitStatus(0, Node.PROPAGATE)) 725bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson continue; // loop on failed CAS 726bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 727bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (h == head) // loop if head changed 728bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson break; 729bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 730bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 731bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 732bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 733bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Sets head of queue, and checks if successor may be waiting 734bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * in shared mode, if so propagating if either propagate > 0 or 735bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * PROPAGATE status was set. 736bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 737bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param node the node 738adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param propagate the return value from a tryAcquireShared 739adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 740adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void setHeadAndPropagate(Node node, int propagate) { 741bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node h = head; // Record old head for check below 742adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project setHead(node); 743bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /* 744bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Try to signal next queued node if: 745bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Propagation was indicated by caller, 746b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * or was recorded (as h.waitStatus either before 747b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * or after setHead) by a previous operation 748bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (note: this uses sign-check of waitStatus because 749bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * PROPAGATE status may transition to SIGNAL.) 750bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * and 751bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The next node is waiting in shared mode, 752bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * or we don't know, because it appears null 753bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 754bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The conservatism in both of these checks may cause 755bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * unnecessary wake-ups, but only when there are multiple 756bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * racing acquires/releases, so most need signals now or soon 757bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * anyway. 758bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 759b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (propagate > 0 || h == null || h.waitStatus < 0 || 760b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (h = head) == null || h.waitStatus < 0) { 761bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node s = node.next; 762adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (s == null || s.isShared()) 763bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson doReleaseShared(); 764adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 765adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 766adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 767adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Utilities for various versions of acquire 768adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 769adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 770bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Cancels an ongoing attempt to acquire. 771bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 772adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param node the node 773adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 774adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void cancelAcquire(Node node) { 775bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // Ignore if node doesn't exist 776bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (node == null) 777bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return; 778bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 779bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson node.thread = null; 780bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 781bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // Skip cancelled predecessors 782bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node pred = node.prev; 783bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson while (pred.waitStatus > 0) 784bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson node.prev = pred = pred.prev; 785bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 786bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // predNext is the apparent node to unsplice. CASes below will 787bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // fail if not, in which case, we lost race vs another cancel 788bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // or signal, so no further action is necessary. 789bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node predNext = pred.next; 790bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 791bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // Can use unconditional write instead of CAS here. 792bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // After this atomic step, other Nodes can skip past us. 793bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // Before, we are free of interference from other threads. 794bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson node.waitStatus = Node.CANCELLED; 795bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 796bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // If we are the tail, remove ourselves. 797bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (node == tail && compareAndSetTail(node, pred)) { 798b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak pred.compareAndSetNext(predNext, null); 799bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } else { 800bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // If successor needs signal, try to set pred's next-link 801bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // so it will get one. Otherwise wake it up to propagate. 802bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson int ws; 803bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (pred != head && 804bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson ((ws = pred.waitStatus) == Node.SIGNAL || 805b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (ws <= 0 && pred.compareAndSetWaitStatus(ws, Node.SIGNAL))) && 806bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred.thread != null) { 807bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node next = node.next; 808bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (next != null && next.waitStatus <= 0) 809b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak pred.compareAndSetNext(predNext, next); 810bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } else { 811bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson unparkSuccessor(node); 812bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 813bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 814bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson node.next = node; // help GC 815adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 816adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 817adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 818adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 819adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Checks and updates status for a node that failed to acquire. 820adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns true if thread should block. This is the main signal 82191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * control in all acquire loops. Requires that pred == node.prev. 822bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 823adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param pred node's predecessor holding status 824bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param node the node 825bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if thread should block 826adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 827adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { 828bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson int ws = pred.waitStatus; 829bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (ws == Node.SIGNAL) 830adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 831adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * This node has already set status asking a release 832bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to signal it, so it can safely park. 833adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 834adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 835bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (ws > 0) { 836adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 837bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Predecessor was cancelled. Skip over predecessors and 838bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * indicate retry. 839adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 840bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson do { 841bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson node.prev = pred = pred.prev; 842bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } while (pred.waitStatus > 0); 843bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson pred.next = node; 844bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } else { 845adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 846bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * waitStatus must be 0 or PROPAGATE. Indicate that we 847bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * need a signal, but don't park yet. Caller will need to 848bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * retry to make sure it cannot acquire before parking. 849adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 850b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak pred.compareAndSetWaitStatus(ws, Node.SIGNAL); 851bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 852adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 853adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 854adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 855adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 856adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Convenience method to interrupt current thread. 857adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 858a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static void selfInterrupt() { 859adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Thread.currentThread().interrupt(); 860adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 861adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 862adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 863b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Convenience method to park and then check if interrupted. 864bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 865bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if interrupted 866adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 867bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson private final boolean parkAndCheckInterrupt() { 8686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson LockSupport.park(this); 869adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return Thread.interrupted(); 870adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 871adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 872adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 873adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Various flavors of acquire, varying in exclusive/shared and 874adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * control modes. Each is mostly the same, but annoyingly 875adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * different. Only a little bit of factoring is possible due to 876adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * interactions of exception mechanics (including ensuring that we 877adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * cancel if tryAcquire throws exception) and other control, at 878bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * least not without hurting performance too much. 879adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 880adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 881adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 882bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Acquires in exclusive uninterruptible mode for thread already in 883adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queue. Used by condition wait methods as well as acquire. 884bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 885adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param node the node 886adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param arg the acquire argument 887bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if interrupted while waiting 888adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 889adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final boolean acquireQueued(final Node node, int arg) { 890adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 891adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean interrupted = false; 892adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 893adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node p = node.predecessor(); 894adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p == head && tryAcquire(arg)) { 895adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project setHead(node); 896adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project p.next = null; // help GC 897adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return interrupted; 898adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 899bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 900bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson parkAndCheckInterrupt()) 901adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project interrupted = true; 902adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 903b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (Throwable t) { 904b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cancelAcquire(node); 905b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw t; 906adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 907adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 908adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 909bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 910bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Acquires in exclusive interruptible mode. 911adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param arg the acquire argument 912adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 913bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson private void doAcquireInterruptibly(int arg) 914adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws InterruptedException { 915adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node node = addWaiter(Node.EXCLUSIVE); 916adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 917adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 918adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node p = node.predecessor(); 919adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p == head && tryAcquire(arg)) { 920adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project setHead(node); 921adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project p.next = null; // help GC 922adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return; 923adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 924bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 925bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson parkAndCheckInterrupt()) 926bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson throw new InterruptedException(); 927adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 928b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (Throwable t) { 929b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cancelAcquire(node); 930b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw t; 931adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 932adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 933adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 934bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 935bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Acquires in exclusive timed mode. 936bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 937adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param arg the acquire argument 938adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param nanosTimeout max wait time 939bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if acquired 940adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 941bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson private boolean doAcquireNanos(int arg, long nanosTimeout) 94291770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle throws InterruptedException { 94391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle if (nanosTimeout <= 0L) 94491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle return false; 94591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle final long deadline = System.nanoTime() + nanosTimeout; 946adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node node = addWaiter(Node.EXCLUSIVE); 947adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 948adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 949adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node p = node.predecessor(); 950adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p == head && tryAcquire(arg)) { 951adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project setHead(node); 952adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project p.next = null; // help GC 953adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 954adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 95591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle nanosTimeout = deadline - System.nanoTime(); 956b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (nanosTimeout <= 0L) { 957b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cancelAcquire(node); 958adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 959b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 960bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 961b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD) 9626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson LockSupport.parkNanos(this, nanosTimeout); 963bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (Thread.interrupted()) 964bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson throw new InterruptedException(); 965adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 966b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (Throwable t) { 967b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cancelAcquire(node); 968b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw t; 969adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 970adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 971adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 972bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 973bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Acquires in shared uninterruptible mode. 974adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param arg the acquire argument 975adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 976adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void doAcquireShared(int arg) { 977adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node node = addWaiter(Node.SHARED); 978adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 979adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean interrupted = false; 980adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 981adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node p = node.predecessor(); 982adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p == head) { 983adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int r = tryAcquireShared(arg); 984adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (r >= 0) { 985adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project setHeadAndPropagate(node, r); 986adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project p.next = null; // help GC 987adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (interrupted) 988adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project selfInterrupt(); 989adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return; 990adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 991adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 992bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 993bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson parkAndCheckInterrupt()) 994adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project interrupted = true; 995adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 996b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (Throwable t) { 997b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cancelAcquire(node); 998b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw t; 999adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1000adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1001adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1002bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 1003bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Acquires in shared interruptible mode. 1004adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param arg the acquire argument 1005adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1006bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson private void doAcquireSharedInterruptibly(int arg) 1007adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws InterruptedException { 1008adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node node = addWaiter(Node.SHARED); 1009adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 1010adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 1011adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node p = node.predecessor(); 1012adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p == head) { 1013adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int r = tryAcquireShared(arg); 1014adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (r >= 0) { 1015adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project setHeadAndPropagate(node, r); 1016adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project p.next = null; // help GC 1017adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return; 1018adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1019adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1020bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 1021bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson parkAndCheckInterrupt()) 1022bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson throw new InterruptedException(); 1023adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1024b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (Throwable t) { 1025b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cancelAcquire(node); 1026b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw t; 1027adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1028adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1029adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1030bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 1031bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Acquires in shared timed mode. 1032bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1033adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param arg the acquire argument 1034adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param nanosTimeout max wait time 1035bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if acquired 1036adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1037bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson private boolean doAcquireSharedNanos(int arg, long nanosTimeout) 103891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle throws InterruptedException { 103991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle if (nanosTimeout <= 0L) 104091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle return false; 104191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle final long deadline = System.nanoTime() + nanosTimeout; 1042adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node node = addWaiter(Node.SHARED); 1043adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 1044adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (;;) { 1045adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final Node p = node.predecessor(); 1046adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p == head) { 1047adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int r = tryAcquireShared(arg); 1048adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (r >= 0) { 1049adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project setHeadAndPropagate(node, r); 1050adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project p.next = null; // help GC 1051adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 1052adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1053adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 105491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle nanosTimeout = deadline - System.nanoTime(); 1055b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (nanosTimeout <= 0L) { 1056b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cancelAcquire(node); 1057adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 1058b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 1059bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (shouldParkAfterFailedAcquire(p, node) && 1060b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD) 10616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson LockSupport.parkNanos(this, nanosTimeout); 1062bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (Thread.interrupted()) 1063bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson throw new InterruptedException(); 1064adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1065b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (Throwable t) { 1066b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cancelAcquire(node); 1067b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw t; 1068adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1069adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1070adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1071bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // Main exported methods 1072adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1073adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1074adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Attempts to acquire in exclusive mode. This method should query 1075adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * if the state of the object permits it to be acquired in the 1076adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * exclusive mode, and if so to acquire it. 1077adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1078adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>This method is always invoked by the thread performing 1079adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * acquire. If this method reports failure, the acquire method 1080adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * may queue the thread, if it is not already queued, until it is 1081adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * signalled by a release from some other thread. This can be used 1082bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to implement method {@link Lock#tryLock()}. 1083adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1084adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>The default 1085bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * implementation throws {@link UnsupportedOperationException}. 1086adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1087bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param arg the acquire argument. This value is always the one 1088bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * passed to an acquire method, or is the value saved on entry 1089bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to a condition wait. The value is otherwise uninterpreted 1090bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * and can represent anything you like. 1091bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if successful. Upon success, this object has 1092bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * been acquired. 1093bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalMonitorStateException if acquiring would place this 1094bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * synchronizer in an illegal state. This exception must be 1095bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * thrown in a consistent fashion for synchronization to work 1096bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * correctly. 1097adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws UnsupportedOperationException if exclusive mode is not supported 1098adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1099adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected boolean tryAcquire(int arg) { 1100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new UnsupportedOperationException(); 1101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1104adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Attempts to set the state to reflect a release in exclusive 1105bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * mode. 1106bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1107bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This method is always invoked by the thread performing release. 1108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>The default implementation throws 1110bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@link UnsupportedOperationException}. 1111bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1112bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param arg the release argument. This value is always the one 1113bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * passed to a release method, or the current state value upon 1114bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * entry to a condition wait. The value is otherwise 1115bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * uninterpreted and can represent anything you like. 1116bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if this object is now in a fully released 1117bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * state, so that any waiting threads may attempt to acquire; 1118bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * and {@code false} otherwise. 1119bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalMonitorStateException if releasing would place this 1120bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * synchronizer in an illegal state. This exception must be 1121bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * thrown in a consistent fashion for synchronization to work 1122bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * correctly. 1123adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws UnsupportedOperationException if exclusive mode is not supported 1124adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1125adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected boolean tryRelease(int arg) { 1126adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new UnsupportedOperationException(); 1127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Attempts to acquire in shared mode. This method should query if 1131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the state of the object permits it to be acquired in the shared 1132bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * mode, and if so to acquire it. 1133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>This method is always invoked by the thread performing 1135adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * acquire. If this method reports failure, the acquire method 1136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * may queue the thread, if it is not already queued, until it is 1137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * signalled by a release from some other thread. 1138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>The default implementation throws {@link 1140bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * UnsupportedOperationException}. 1141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1142bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param arg the acquire argument. This value is always the one 1143bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * passed to an acquire method, or is the value saved on entry 1144bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to a condition wait. The value is otherwise uninterpreted 1145bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * and can represent anything you like. 1146bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return a negative value on failure; zero if acquisition in shared 1147bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * mode succeeded but no subsequent shared-mode acquire can 1148bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * succeed; and a positive value if acquisition in shared 1149bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * mode succeeded and subsequent shared-mode acquires might 1150bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * also succeed, in which case a subsequent waiting thread 1151bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * must check availability. (Support for three different 1152bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * return values enables this method to be used in contexts 1153bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * where acquires only sometimes act exclusively.) Upon 1154bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * success, this object has been acquired. 1155bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalMonitorStateException if acquiring would place this 1156bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * synchronizer in an illegal state. This exception must be 1157bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * thrown in a consistent fashion for synchronization to work 1158bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * correctly. 1159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws UnsupportedOperationException if shared mode is not supported 1160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected int tryAcquireShared(int arg) { 1162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new UnsupportedOperationException(); 1163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1166adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Attempts to set the state to reflect a release in shared mode. 1167bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>This method is always invoked by the thread performing release. 1169bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1170bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>The default implementation throws 1171bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@link UnsupportedOperationException}. 1172bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1173bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param arg the release argument. This value is always the one 1174bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * passed to a release method, or the current state value upon 1175bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * entry to a condition wait. The value is otherwise 1176bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * uninterpreted and can represent anything you like. 1177bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if this release of shared mode may permit a 1178bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * waiting acquire (shared or exclusive) to succeed; and 1179bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code false} otherwise 1180bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalMonitorStateException if releasing would place this 1181bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * synchronizer in an illegal state. This exception must be 1182bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * thrown in a consistent fashion for synchronization to work 1183bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * correctly. 1184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws UnsupportedOperationException if shared mode is not supported 1185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected boolean tryReleaseShared(int arg) { 1187adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new UnsupportedOperationException(); 1188adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1189adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1190adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1191bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns {@code true} if synchronization is held exclusively with 1192bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * respect to the current (calling) thread. This method is invoked 1193adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * upon each call to a non-waiting {@link ConditionObject} method. 1194adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * (Waiting methods instead invoke {@link #release}.) 1195bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1196adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <p>The default implementation throws {@link 1197adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * UnsupportedOperationException}. This method is invoked 1198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * internally only within {@link ConditionObject} methods, so need 1199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * not be defined if conditions are not used. 1200adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1201bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if synchronization is held exclusively; 1202bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code false} otherwise 1203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws UnsupportedOperationException if conditions are not supported 1204adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1205adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected boolean isHeldExclusively() { 1206adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new UnsupportedOperationException(); 1207adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1208adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1209adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1210adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Acquires in exclusive mode, ignoring interrupts. Implemented 1211adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * by invoking at least once {@link #tryAcquire}, 1212adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * returning on success. Otherwise the thread is queued, possibly 1213adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * repeatedly blocking and unblocking, invoking {@link 1214adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * #tryAcquire} until success. This method can be used 1215bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * to implement method {@link Lock#lock}. 1216bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1217bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param arg the acquire argument. This value is conveyed to 1218bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@link #tryAcquire} but is otherwise uninterpreted and 1219bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * can represent anything you like. 1220bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 1221adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final void acquire(int arg) { 1222adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (!tryAcquire(arg) && 1223adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) 1224adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project selfInterrupt(); 1225adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1226adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1227adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1228adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Acquires in exclusive mode, aborting if interrupted. 1229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Implemented by first checking interrupt status, then invoking 1230adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * at least once {@link #tryAcquire}, returning on 1231adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * success. Otherwise the thread is queued, possibly repeatedly 1232adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * blocking and unblocking, invoking {@link #tryAcquire} 1233adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * until success or the thread is interrupted. This method can be 1234bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * used to implement method {@link Lock#lockInterruptibly}. 1235bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1236bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param arg the acquire argument. This value is conveyed to 1237bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@link #tryAcquire} but is otherwise uninterpreted and 1238bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * can represent anything you like. 1239adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws InterruptedException if the current thread is interrupted 1240adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 12418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public final void acquireInterruptibly(int arg) 12428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throws InterruptedException { 1243adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (Thread.interrupted()) 1244adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new InterruptedException(); 1245adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (!tryAcquire(arg)) 1246adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project doAcquireInterruptibly(arg); 1247adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1248adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1249adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1250adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Attempts to acquire in exclusive mode, aborting if interrupted, 1251adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and failing if the given timeout elapses. Implemented by first 1252adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * checking interrupt status, then invoking at least once {@link 1253adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * #tryAcquire}, returning on success. Otherwise, the thread is 1254adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * queued, possibly repeatedly blocking and unblocking, invoking 1255adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link #tryAcquire} until success or the thread is interrupted 1256adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * or the timeout elapses. This method can be used to implement 1257adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * method {@link Lock#tryLock(long, TimeUnit)}. 1258bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1259bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param arg the acquire argument. This value is conveyed to 1260bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@link #tryAcquire} but is otherwise uninterpreted and 1261bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * can represent anything you like. 1262adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param nanosTimeout the maximum number of nanoseconds to wait 1263bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if acquired; {@code false} if timed out 1264adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws InterruptedException if the current thread is interrupted 1265adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 12668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public final boolean tryAcquireNanos(int arg, long nanosTimeout) 12678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throws InterruptedException { 1268bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (Thread.interrupted()) 1269bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson throw new InterruptedException(); 1270bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return tryAcquire(arg) || 1271bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson doAcquireNanos(arg, nanosTimeout); 1272bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 1273adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1274adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1275adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Releases in exclusive mode. Implemented by unblocking one or 1276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * more threads if {@link #tryRelease} returns true. 1277bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * This method can be used to implement method {@link Lock#unlock}. 1278bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1279bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param arg the release argument. This value is conveyed to 1280bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@link #tryRelease} but is otherwise uninterpreted and 1281bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * can represent anything you like. 1282bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the value returned from {@link #tryRelease} 1283adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1284adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final boolean release(int arg) { 1285adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (tryRelease(arg)) { 1286adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node h = head; 1287bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (h != null && h.waitStatus != 0) 1288adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project unparkSuccessor(h); 1289adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 1290adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1291adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 1292adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1293adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1294adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1295adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Acquires in shared mode, ignoring interrupts. Implemented by 1296adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * first invoking at least once {@link #tryAcquireShared}, 1297adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * returning on success. Otherwise the thread is queued, possibly 1298adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * repeatedly blocking and unblocking, invoking {@link 1299bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * #tryAcquireShared} until success. 1300bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1301bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param arg the acquire argument. This value is conveyed to 1302bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@link #tryAcquireShared} but is otherwise uninterpreted 1303bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * and can represent anything you like. 1304adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1305adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final void acquireShared(int arg) { 1306adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (tryAcquireShared(arg) < 0) 1307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project doAcquireShared(arg); 1308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1309adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Acquires in shared mode, aborting if interrupted. Implemented 1312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * by first checking interrupt status, then invoking at least once 1313adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@link #tryAcquireShared}, returning on success. Otherwise the 1314adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * thread is queued, possibly repeatedly blocking and unblocking, 1315adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * invoking {@link #tryAcquireShared} until success or the thread 1316bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is interrupted. 131791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * @param arg the acquire argument. 1318adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * This value is conveyed to {@link #tryAcquireShared} but is 1319adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * otherwise uninterpreted and can represent anything 1320adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * you like. 1321adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws InterruptedException if the current thread is interrupted 1322adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 13238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public final void acquireSharedInterruptibly(int arg) 13248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throws InterruptedException { 1325adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (Thread.interrupted()) 1326adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new InterruptedException(); 1327adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (tryAcquireShared(arg) < 0) 1328adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project doAcquireSharedInterruptibly(arg); 1329bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 1330adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1331adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1332adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Attempts to acquire in shared mode, aborting if interrupted, and 1333adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * failing if the given timeout elapses. Implemented by first 1334adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * checking interrupt status, then invoking at least once {@link 1335adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * #tryAcquireShared}, returning on success. Otherwise, the 1336adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * thread is queued, possibly repeatedly blocking and unblocking, 1337adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * invoking {@link #tryAcquireShared} until success or the thread 1338adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * is interrupted or the timeout elapses. 1339bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1340bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param arg the acquire argument. This value is conveyed to 1341bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@link #tryAcquireShared} but is otherwise uninterpreted 1342bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * and can represent anything you like. 1343adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param nanosTimeout the maximum number of nanoseconds to wait 1344bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if acquired; {@code false} if timed out 1345adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws InterruptedException if the current thread is interrupted 1346adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 13478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout) 13488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throws InterruptedException { 1349bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (Thread.interrupted()) 1350bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson throw new InterruptedException(); 1351bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return tryAcquireShared(arg) >= 0 || 1352bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson doAcquireSharedNanos(arg, nanosTimeout); 1353bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 1354adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1355adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1356adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Releases in shared mode. Implemented by unblocking one or more 1357bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * threads if {@link #tryReleaseShared} returns true. 1358bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1359bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param arg the release argument. This value is conveyed to 1360bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@link #tryReleaseShared} but is otherwise uninterpreted 1361bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * and can represent anything you like. 1362bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the value returned from {@link #tryReleaseShared} 1363adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1364adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final boolean releaseShared(int arg) { 1365adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (tryReleaseShared(arg)) { 1366bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson doReleaseShared(); 1367adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 1368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1369adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 1370adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1371adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1372adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Queue inspection methods 1373adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1374adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1375adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Queries whether any threads are waiting to acquire. Note that 1376adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * because cancellations due to interrupts and timeouts may occur 1377bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * at any time, a {@code true} return does not guarantee that any 1378adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * other thread will ever acquire. 1379adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1380bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>In this implementation, this operation returns in 1381adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * constant time. 1382adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1383bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if there may be other threads waiting to acquire 1384adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1385bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public final boolean hasQueuedThreads() { 1386adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return head != tail; 1387adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1388adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1389adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1390adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Queries whether any threads have ever contended to acquire this 1391b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * synchronizer; that is, if an acquire method has ever blocked. 1392adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1393bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>In this implementation, this operation returns in 1394adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * constant time. 1395adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1396bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if there has ever been contention 1397adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final boolean hasContended() { 1399adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return head != null; 1400adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1402adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1403adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the first (longest-waiting) thread in the queue, or 1404bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code null} if no threads are currently queued. 1405adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1406bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>In this implementation, this operation normally returns in 1407adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * constant time, but may iterate upon contention if other threads are 1408adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * concurrently modifying the queue. 1409adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1410adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the first (longest-waiting) thread in the queue, or 1411bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code null} if no threads are currently queued 1412adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1413adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final Thread getFirstQueuedThread() { 1414adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // handle only fast path, else relay 1415bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return (head == tail) ? null : fullGetFirstQueuedThread(); 1416adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1417adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1418adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1419b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Version of getFirstQueuedThread called when fastpath fails. 1420adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Thread fullGetFirstQueuedThread() { 1422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 1423bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The first node is normally head.next. Try to get its 1424bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * thread field, ensuring consistent reads: If thread 1425bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * field is nulled out or s.prev is no longer head, then 1426bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * some other thread(s) concurrently performed setHead in 1427bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * between some of our reads. We try this twice before 1428bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * resorting to traversal. 1429adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1430bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node h, s; 1431bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Thread st; 1432bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (((h = head) != null && (s = h.next) != null && 1433bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson s.prev == head && (st = s.thread) != null) || 1434bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson ((h = head) != null && (s = h.next) != null && 1435bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson s.prev == head && (st = s.thread) != null)) 1436bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return st; 1437adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1438bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /* 1439bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Head's next field might not have been set yet, or may have 1440bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * been unset after setHead. So we must check to see if tail 1441bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is actually first node. If not, we continue on, safely 1442bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * traversing from tail back to head to find first, 1443bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * guaranteeing termination. 1444bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 1445adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1446bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Thread firstThread = null; 1447b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (Node p = tail; p != null && p != head; p = p.prev) { 1448b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Thread t = p.thread; 1449b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (t != null) 1450b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak firstThread = t; 1451adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1452bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return firstThread; 1453adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1454adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1455adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1456bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns true if the given thread is currently queued. 1457adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1458bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This implementation traverses the queue to determine 1459adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * presence of the given thread. 1460adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1461adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param thread the thread 1462bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if the given thread is on the queue 1463bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the thread is null 1464adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1465adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final boolean isQueued(Thread thread) { 1466adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (thread == null) 1467adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NullPointerException(); 1468adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node p = tail; p != null; p = p.prev) 1469adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p.thread == thread) 1470adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 1471adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 1472adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1473adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1474bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 1475bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns {@code true} if the apparent first queued thread, if one 1476bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * exists, is waiting in exclusive mode. If this method returns 1477bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code true}, and the current thread is attempting to acquire in 1478bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * shared mode (that is, this method is invoked from {@link 1479bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * #tryAcquireShared}) then it is guaranteed that the current thread 1480bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not the first queued thread. Used only as a heuristic in 1481bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * ReentrantReadWriteLock. 1482bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 1483bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final boolean apparentlyFirstQueuedIsExclusive() { 1484bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node h, s; 1485bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return (h = head) != null && 1486bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson (s = h.next) != null && 1487bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson !s.isShared() && 1488bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson s.thread != null; 1489bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 1490bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 1491bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 1492bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Queries whether any threads have been waiting to acquire longer 1493bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * than the current thread. 1494bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1495bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>An invocation of this method is equivalent to (but may be 1496bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * more efficient than): 1497b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 1498b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * getFirstQueuedThread() != Thread.currentThread() 1499b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * && hasQueuedThreads()}</pre> 1500bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1501bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Note that because cancellations due to interrupts and 1502bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * timeouts may occur at any time, a {@code true} return does not 1503bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * guarantee that some other thread will acquire before the current 1504bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * thread. Likewise, it is possible for another thread to win a 1505bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * race to enqueue after this method has returned {@code false}, 1506bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * due to the queue being empty. 1507bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1508bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This method is designed to be used by a fair synchronizer to 1509aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath * avoid <a href="AbstractQueuedSynchronizer.html#barging">barging</a>. 1510bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Such a synchronizer's {@link #tryAcquire} method should return 1511bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code false}, and its {@link #tryAcquireShared} method should 1512bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * return a negative value, if this method returns {@code true} 1513bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (unless this is a reentrant acquire). For example, the {@code 1514bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * tryAcquire} method for a fair, reentrant, exclusive mode 1515bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * synchronizer might look like this: 1516bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1517b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <pre> {@code 1518bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * protected boolean tryAcquire(int arg) { 1519bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * if (isHeldExclusively()) { 1520bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * // A reentrant acquire; increment hold count 1521bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * return true; 1522bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } else if (hasQueuedPredecessors()) { 1523bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * return false; 1524bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } else { 1525bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * // try to acquire normally 1526bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 1527bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * }}</pre> 1528bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1529bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if there is a queued thread preceding the 1530bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * current thread, and {@code false} if the current thread 1531bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is at the head of the queue or the queue is empty 15326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @since 1.7 1533bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 15346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public final boolean hasQueuedPredecessors() { 1535bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // The correctness of this depends on head being initialized 1536bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // before tail and on head.next being accurate if the current 1537bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // thread is first in queue. 1538bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node t = tail; // Read fields in reverse initialization order 1539bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node h = head; 1540bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node s; 1541bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return h != t && 1542bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson ((s = h.next) == null || s.thread != Thread.currentThread()); 1543bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 1544bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 1545bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 1546adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Instrumentation and monitoring methods 1547adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1548adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1549adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an estimate of the number of threads waiting to 1550adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * acquire. The value is only an estimate because the number of 1551adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * threads may change dynamically while this method traverses 1552adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * internal data structures. This method is designed for use in 1553b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * monitoring system state, not for synchronization control. 1554adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1555bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the estimated number of threads waiting to acquire 1556adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1557adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final int getQueueLength() { 1558adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int n = 0; 1559adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node p = tail; p != null; p = p.prev) { 1560adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p.thread != null) 1561adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ++n; 1562adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1563adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return n; 1564adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1565adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1566adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1567adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a collection containing threads that may be waiting to 1568adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * acquire. Because the actual set of threads may change 1569adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * dynamically while constructing this result, the returned 1570adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * collection is only a best-effort estimate. The elements of the 1571adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * returned collection are in no particular order. This method is 1572adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * designed to facilitate construction of subclasses that provide 1573adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * more extensive monitoring facilities. 1574bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1575adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the collection of threads 1576adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1577adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final Collection<Thread> getQueuedThreads() { 1578b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak ArrayList<Thread> list = new ArrayList<>(); 1579adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node p = tail; p != null; p = p.prev) { 1580adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Thread t = p.thread; 1581adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (t != null) 1582adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project list.add(t); 1583adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1584adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return list; 1585adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1586adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1587adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1588adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a collection containing threads that may be waiting to 1589adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * acquire in exclusive mode. This has the same properties 1590adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * as {@link #getQueuedThreads} except that it only returns 1591adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * those threads waiting due to an exclusive acquire. 1592bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1593adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the collection of threads 1594adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1595adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final Collection<Thread> getExclusiveQueuedThreads() { 1596b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak ArrayList<Thread> list = new ArrayList<>(); 1597adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node p = tail; p != null; p = p.prev) { 1598adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (!p.isShared()) { 1599adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Thread t = p.thread; 1600adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (t != null) 1601adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project list.add(t); 1602adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1603adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1604adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return list; 1605adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1606adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1607adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1608adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a collection containing threads that may be waiting to 1609adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * acquire in shared mode. This has the same properties 1610adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * as {@link #getQueuedThreads} except that it only returns 1611adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * those threads waiting due to a shared acquire. 1612bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1613adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the collection of threads 1614adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1615adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final Collection<Thread> getSharedQueuedThreads() { 1616b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak ArrayList<Thread> list = new ArrayList<>(); 1617adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node p = tail; p != null; p = p.prev) { 1618adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (p.isShared()) { 1619adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Thread t = p.thread; 1620adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (t != null) 1621adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project list.add(t); 1622adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1623adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1624adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return list; 1625adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1626adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1627adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1628bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns a string identifying this synchronizer, as well as its state. 1629bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The state, in brackets, includes the String {@code "State ="} 1630bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * followed by the current value of {@link #getState}, and either 1631bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code "nonempty"} or {@code "empty"} depending on whether the 1632bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * queue is empty. 1633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1634bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return a string identifying this synchronizer, as well as its state 1635adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1636adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public String toString() { 1637b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return super.toString() 1638b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak + "[State = " + getState() + ", " 1639b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak + (hasQueuedThreads() ? "non" : "") + "empty queue]"; 1640adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1641adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1642adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1643adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Internal support methods for Conditions 1644adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1645adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1646adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns true if a node, always one that was initially placed on 1647adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * a condition queue, is now waiting to reacquire on sync queue. 1648adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param node the node 1649adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return true if is reacquiring 1650adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1651adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final boolean isOnSyncQueue(Node node) { 1652adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (node.waitStatus == Node.CONDITION || node.prev == null) 1653adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 1654adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (node.next != null) // If has successor, it must be on queue 1655adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 1656adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 1657adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * node.prev can be non-null, but not yet on queue because 1658adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the CAS to place it on queue can fail. So we have to 1659adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * traverse from tail to make sure it actually made it. It 1660adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * will always be near the tail in calls to this method, and 1661adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * unless the CAS failed (which is unlikely), it will be 1662adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * there, so we hardly ever traverse much. 1663adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return findNodeFromTail(node); 1665bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 1666adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1667adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1668adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns true if node is on sync queue by searching backwards from tail. 1669adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Called only when needed by isOnSyncQueue. 1670adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return true if present 1671adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1672adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private boolean findNodeFromTail(Node node) { 1673b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // We check for node first, since it's likely to be at or near tail. 1674b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // tail is known to be non-null, so we could re-order to "save" 1675b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // one null check, but we leave it this way to help the VM. 1676b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak for (Node p = tail;;) { 1677b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p == node) 1678adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 1679b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (p == null) 1680adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 1681b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak p = p.prev; 1682adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1683adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1684adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1685adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1686bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Transfers a node from a condition queue onto sync queue. 1687adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns true if successful. 1688adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param node the node 1689adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return true if successfully transferred (else the node was 169091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * cancelled before signal) 1691adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1692adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final boolean transferForSignal(Node node) { 1693adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 1694adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * If cannot change waitStatus, the node has been cancelled. 1695adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1696b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (!node.compareAndSetWaitStatus(Node.CONDITION, 0)) 1697adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 1698adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1699adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 1700adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Splice onto queue and try to set waitStatus of predecessor to 1701adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * indicate that thread is (probably) waiting. If cancelled or 1702adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * attempt to set waitStatus fails, wake up to resync (in which 1703adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * case the waitStatus can be transiently and harmlessly wrong). 1704adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1705adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node p = enq(node); 1706bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson int ws = p.waitStatus; 1707b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (ws > 0 || !p.compareAndSetWaitStatus(ws, Node.SIGNAL)) 1708adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project LockSupport.unpark(node.thread); 1709adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 1710adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1711adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1712adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 171391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Transfers node, if necessary, to sync queue after a cancelled wait. 171491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Returns true if thread was cancelled before being signalled. 171591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * 171691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * @param node the node 1717bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return true if cancelled before the node was signalled 1718adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1719adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final boolean transferAfterCancelledWait(Node node) { 1720b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (node.compareAndSetWaitStatus(Node.CONDITION, 0)) { 1721adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project enq(node); 1722adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 1723adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1724adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 1725adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * If we lost out to a signal(), then we can't proceed 1726adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * until it finishes its enq(). Cancelling during an 1727adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * incomplete transfer is both rare and transient, so just 1728adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * spin. 1729adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1730bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson while (!isOnSyncQueue(node)) 1731adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Thread.yield(); 1732adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 1733adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1734adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1735adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1736bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Invokes release with current state value; returns saved state. 1737bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Cancels node and throws exception on failure. 1738adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param node the condition node for this wait 1739adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return previous sync state 1740adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1741adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final int fullyRelease(Node node) { 1742adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 1743adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int savedState = getState(); 1744b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (release(savedState)) 1745adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return savedState; 1746b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw new IllegalMonitorStateException(); 1747b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (Throwable t) { 1748b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak node.waitStatus = Node.CANCELLED; 1749b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw t; 1750adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1751adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1752adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1753adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Instrumentation methods for conditions 1754adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1755adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1756bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Queries whether the given ConditionObject 1757adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * uses this synchronizer as its lock. 1758bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1759adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param condition the condition 176091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * @return {@code true} if owned 1761bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the condition is null 1762adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1763adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final boolean owns(ConditionObject condition) { 1764adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return condition.isOwnedBy(this); 1765adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1766adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1767adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1768adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Queries whether any threads are waiting on the given condition 1769adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * associated with this synchronizer. Note that because timeouts 177091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * and interrupts may occur at any time, a {@code true} return 177191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * does not guarantee that a future {@code signal} will awaken 1772adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * any threads. This method is designed primarily for use in 1773adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * monitoring of the system state. 1774bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1775adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param condition the condition 177691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * @return {@code true} if there are any waiting threads 1777bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalMonitorStateException if exclusive synchronization 1778bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not held 1779adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalArgumentException if the given condition is 1780bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * not associated with this synchronizer 1781bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the condition is null 1782bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 1783adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final boolean hasWaiters(ConditionObject condition) { 1784adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (!owns(condition)) 1785adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException("Not owner"); 1786adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return condition.hasWaiters(); 1787adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1788adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1789adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1790adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an estimate of the number of threads waiting on the 1791adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * given condition associated with this synchronizer. Note that 1792adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * because timeouts and interrupts may occur at any time, the 1793adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * estimate serves only as an upper bound on the actual number of 1794b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * waiters. This method is designed for use in monitoring system 1795b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * state, not for synchronization control. 1796bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1797adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param condition the condition 1798bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the estimated number of waiting threads 1799bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalMonitorStateException if exclusive synchronization 1800bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not held 1801adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalArgumentException if the given condition is 1802bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * not associated with this synchronizer 1803bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the condition is null 1804bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 1805adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final int getWaitQueueLength(ConditionObject condition) { 1806adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (!owns(condition)) 1807adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException("Not owner"); 1808adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return condition.getWaitQueueLength(); 1809adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1810adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1811adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1812adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a collection containing those threads that may be 1813adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * waiting on the given condition associated with this 1814adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * synchronizer. Because the actual set of threads may change 1815adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * dynamically while constructing this result, the returned 1816adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * collection is only a best-effort estimate. The elements of the 1817bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * returned collection are in no particular order. 1818bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1819adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param condition the condition 1820adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the collection of threads 1821bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalMonitorStateException if exclusive synchronization 1822bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not held 1823adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalArgumentException if the given condition is 1824bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * not associated with this synchronizer 1825bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the condition is null 1826adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1827adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final Collection<Thread> getWaitingThreads(ConditionObject condition) { 1828adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (!owns(condition)) 1829adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException("Not owner"); 1830adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return condition.getWaitingThreads(); 1831adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1832adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1833adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1834adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Condition implementation for a {@link 1835adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * AbstractQueuedSynchronizer} serving as the basis of a {@link 1836adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Lock} implementation. 1837adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 1838bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Method documentation for this class describes mechanics, 1839adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * not behavioral specifications from the point of view of Lock 1840adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and Condition users. Exported versions of this class will in 1841adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * general need to be accompanied by documentation describing 1842adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * condition semantics that rely on those of the associated 184391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * {@code AbstractQueuedSynchronizer}. 1844bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1845bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This class is Serializable, but all fields are transient, 1846adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * so deserialized conditions have no waiters. 1847adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1848adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public class ConditionObject implements Condition, java.io.Serializable { 1849adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = 1173984872572414699L; 1850adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** First node of condition queue. */ 1851adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private transient Node firstWaiter; 1852adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Last node of condition queue. */ 1853adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private transient Node lastWaiter; 1854adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1855adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 185691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Creates a new {@code ConditionObject} instance. 1857adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1858adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public ConditionObject() { } 1859adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1860adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Internal methods 1861adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1862adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1863bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Adds a new waiter to wait queue. 1864adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return its new wait node 1865adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1866adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private Node addConditionWaiter() { 1867adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node t = lastWaiter; 1868bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson // If lastWaiter is cancelled, clean out. 1869bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (t != null && t.waitStatus != Node.CONDITION) { 1870bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson unlinkCancelledWaiters(); 1871bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson t = lastWaiter; 1872bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 1873b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 1874b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node node = new Node(Node.CONDITION); 1875b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 1876bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (t == null) 1877adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project firstWaiter = node; 1878bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson else 1879adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project t.nextWaiter = node; 1880adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastWaiter = node; 1881adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return node; 1882adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1883adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1884adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1885bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Removes and transfers nodes until hit non-cancelled one or 1886adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * null. Split out from signal in part to encourage compilers 1887adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * to inline the case of no waiters. 1888adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param first (non-null) the first node on condition queue 1889adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1890adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void doSignal(Node first) { 1891adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project do { 1892bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if ( (firstWaiter = first.nextWaiter) == null) 1893adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lastWaiter = null; 1894adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project first.nextWaiter = null; 1895adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } while (!transferForSignal(first) && 1896adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project (first = firstWaiter) != null); 1897adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1898adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1899adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1900bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Removes and transfers all nodes. 1901adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param first (non-null) the first node on condition queue 1902adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1903adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void doSignalAll(Node first) { 1904bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lastWaiter = firstWaiter = null; 1905adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project do { 1906adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node next = first.nextWaiter; 1907adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project first.nextWaiter = null; 1908adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project transferForSignal(first); 1909adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project first = next; 1910adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } while (first != null); 1911adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1912adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1913bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 1914bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Unlinks cancelled waiter nodes from condition queue. 1915bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Called only while holding lock. This is called when 1916bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * cancellation occurred during condition wait, and upon 1917bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * insertion of a new waiter when lastWaiter is seen to have 1918bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * been cancelled. This method is needed to avoid garbage 1919bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * retention in the absence of signals. So even though it may 1920bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * require a full traversal, it comes into play only when 1921bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * timeouts or cancellations occur in the absence of 1922bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * signals. It traverses all nodes rather than stopping at a 1923bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * particular target to unlink all pointers to garbage nodes 1924bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * without requiring many re-traversals during cancellation 1925bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * storms. 1926bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 1927bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson private void unlinkCancelledWaiters() { 1928bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node t = firstWaiter; 1929bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node trail = null; 1930bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson while (t != null) { 1931bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Node next = t.nextWaiter; 1932bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (t.waitStatus != Node.CONDITION) { 1933bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson t.nextWaiter = null; 1934bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (trail == null) 1935bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson firstWaiter = next; 1936bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson else 1937bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson trail.nextWaiter = next; 1938bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (next == null) 1939bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lastWaiter = trail; 1940bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 1941bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson else 1942bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson trail = t; 1943bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson t = next; 1944bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 1945bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 1946bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 1947adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // public methods 1948adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1949adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1950adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Moves the longest-waiting thread, if one exists, from the 1951adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * wait queue for this condition to the wait queue for the 1952adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * owning lock. 1953bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1954adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 1955bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * returns {@code false} 1956adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1957adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final void signal() { 1958bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (!isHeldExclusively()) 1959adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalMonitorStateException(); 1960adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node first = firstWaiter; 1961adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (first != null) 1962adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project doSignal(first); 1963adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1964bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 1965adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1966adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Moves all threads from the wait queue for this condition to 1967adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the wait queue for the owning lock. 1968bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 1969adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 1970bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * returns {@code false} 1971adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1972adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final void signalAll() { 1973bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (!isHeldExclusively()) 1974adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalMonitorStateException(); 1975adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node first = firstWaiter; 1976bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (first != null) 1977adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project doSignalAll(first); 1978adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1979adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1980adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1981adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Implements uninterruptible condition wait. 1982adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <ol> 1983b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Save lock state returned by {@link #getState}. 1984b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Invoke {@link #release} with saved state as argument, 1985b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * throwing IllegalMonitorStateException if it fails. 1986b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Block until signalled. 1987b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Reacquire by invoking specialized version of 1988b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * {@link #acquire} with saved state as argument. 1989adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * </ol> 1990adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1991adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final void awaitUninterruptibly() { 1992adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node node = addConditionWaiter(); 1993adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int savedState = fullyRelease(node); 1994adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean interrupted = false; 1995adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (!isOnSyncQueue(node)) { 19966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson LockSupport.park(this); 1997bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (Thread.interrupted()) 1998adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project interrupted = true; 1999adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2000adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (acquireQueued(node, savedState) || interrupted) 2001adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project selfInterrupt(); 2002adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2003adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2004adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 2005adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * For interruptible waits, we need to track whether to throw 2006adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * InterruptedException, if interrupted while blocked on 2007adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * condition, versus reinterrupt current thread, if 2008adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * interrupted while blocked waiting to re-acquire. 2009adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2010adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2011adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Mode meaning to reinterrupt on exit from wait */ 2012adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final int REINTERRUPT = 1; 2013adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Mode meaning to throw InterruptedException on exit from wait */ 2014adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final int THROW_IE = -1; 2015adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2016adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2017bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Checks for interrupt, returning THROW_IE if interrupted 2018adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * before signalled, REINTERRUPT if after signalled, or 2019adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 0 if not interrupted. 2020adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2021adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private int checkInterruptWhileWaiting(Node node) { 2022bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return Thread.interrupted() ? 2023bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) : 2024adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 0; 2025adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2026adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2027adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2028bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Throws InterruptedException, reinterrupts current thread, or 2029bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * does nothing, depending on mode. 2030adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2031bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson private void reportInterruptAfterWait(int interruptMode) 2032adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws InterruptedException { 2033adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (interruptMode == THROW_IE) 2034adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new InterruptedException(); 2035adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project else if (interruptMode == REINTERRUPT) 2036bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson selfInterrupt(); 2037adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2038adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2039adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2040adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Implements interruptible condition wait. 2041adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <ol> 2042b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>If current thread is interrupted, throw InterruptedException. 2043b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Save lock state returned by {@link #getState}. 2044b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Invoke {@link #release} with saved state as argument, 2045b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * throwing IllegalMonitorStateException if it fails. 2046b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Block until signalled or interrupted. 2047b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Reacquire by invoking specialized version of 2048b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * {@link #acquire} with saved state as argument. 2049b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>If interrupted while blocked in step 4, throw InterruptedException. 2050adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * </ol> 2051adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2052adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public final void await() throws InterruptedException { 2053bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (Thread.interrupted()) 2054adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new InterruptedException(); 2055adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node node = addConditionWaiter(); 2056adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int savedState = fullyRelease(node); 2057adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int interruptMode = 0; 2058adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (!isOnSyncQueue(node)) { 20596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson LockSupport.park(this); 2060adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 2061adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 2062adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2063adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 2064adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project interruptMode = REINTERRUPT; 2065bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (node.nextWaiter != null) // clean up if cancelled 2066bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson unlinkCancelledWaiters(); 2067adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (interruptMode != 0) 2068adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project reportInterruptAfterWait(interruptMode); 2069adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2070adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2071adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2072adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Implements timed condition wait. 2073adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <ol> 2074b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>If current thread is interrupted, throw InterruptedException. 2075b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Save lock state returned by {@link #getState}. 2076b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Invoke {@link #release} with saved state as argument, 2077b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * throwing IllegalMonitorStateException if it fails. 2078b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Block until signalled, interrupted, or timed out. 2079b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Reacquire by invoking specialized version of 2080b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * {@link #acquire} with saved state as argument. 2081b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>If interrupted while blocked in step 4, throw InterruptedException. 2082adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * </ol> 2083adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 20848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public final long awaitNanos(long nanosTimeout) 20858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throws InterruptedException { 2086bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (Thread.interrupted()) 2087adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new InterruptedException(); 2088b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // We don't check for nanosTimeout <= 0L here, to allow 2089b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // awaitNanos(0) as a way to "yield the lock". 2090b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final long deadline = System.nanoTime() + nanosTimeout; 2091aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath long initialNanos = nanosTimeout; 2092adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node node = addConditionWaiter(); 2093adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int savedState = fullyRelease(node); 2094adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int interruptMode = 0; 2095adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (!isOnSyncQueue(node)) { 2096adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nanosTimeout <= 0L) { 2097bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson transferAfterCancelledWait(node); 2098adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 2099adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2100b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD) 210191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle LockSupport.parkNanos(this, nanosTimeout); 2102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 2103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 210491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle nanosTimeout = deadline - System.nanoTime(); 2105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 2107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project interruptMode = REINTERRUPT; 2108bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (node.nextWaiter != null) 2109bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson unlinkCancelledWaiters(); 2110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (interruptMode != 0) 2111adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project reportInterruptAfterWait(interruptMode); 2112aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath long remaining = deadline - System.nanoTime(); // avoid overflow 21138fc2ac0fa8eb47ce607f8412e469d4f680b6ef85Neil Fuller return (remaining <= initialNanos) ? remaining : Long.MIN_VALUE; 2114adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2115adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Implements absolute timed condition wait. 2118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <ol> 2119b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>If current thread is interrupted, throw InterruptedException. 2120b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Save lock state returned by {@link #getState}. 2121b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Invoke {@link #release} with saved state as argument, 2122b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * throwing IllegalMonitorStateException if it fails. 2123b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Block until signalled, interrupted, or timed out. 2124b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Reacquire by invoking specialized version of 2125b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * {@link #acquire} with saved state as argument. 2126b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>If interrupted while blocked in step 4, throw InterruptedException. 2127b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>If timed out while blocked in step 4, return false, else true. 2128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * </ol> 2129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 21308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public final boolean awaitUntil(Date deadline) 21318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throws InterruptedException { 2132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long abstime = deadline.getTime(); 2133bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (Thread.interrupted()) 2134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new InterruptedException(); 2135adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node node = addConditionWaiter(); 2136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int savedState = fullyRelease(node); 2137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean timedout = false; 2138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int interruptMode = 0; 2139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (!isOnSyncQueue(node)) { 2140b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (System.currentTimeMillis() >= abstime) { 2141bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson timedout = transferAfterCancelledWait(node); 2142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 2143adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 21446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson LockSupport.parkUntil(this, abstime); 2145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 2146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 2147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 2149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project interruptMode = REINTERRUPT; 2150bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (node.nextWaiter != null) 2151bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson unlinkCancelledWaiters(); 2152adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (interruptMode != 0) 2153adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project reportInterruptAfterWait(interruptMode); 2154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return !timedout; 2155adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2156bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 2157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2158bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Implements timed condition wait. 2159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * <ol> 2160b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>If current thread is interrupted, throw InterruptedException. 2161b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Save lock state returned by {@link #getState}. 2162b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Invoke {@link #release} with saved state as argument, 2163b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * throwing IllegalMonitorStateException if it fails. 2164b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Block until signalled, interrupted, or timed out. 2165b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>Reacquire by invoking specialized version of 2166b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * {@link #acquire} with saved state as argument. 2167b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>If interrupted while blocked in step 4, throw InterruptedException. 2168b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * <li>If timed out while blocked in step 4, return false, else true. 2169adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * </ol> 2170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 21718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson public final boolean await(long time, TimeUnit unit) 21728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throws InterruptedException { 2173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long nanosTimeout = unit.toNanos(time); 2174bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (Thread.interrupted()) 2175adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new InterruptedException(); 2176b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // We don't check for nanosTimeout <= 0L here, to allow 2177b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // await(0, unit) as a way to "yield the lock". 2178b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final long deadline = System.nanoTime() + nanosTimeout; 2179adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Node node = addConditionWaiter(); 2180adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int savedState = fullyRelease(node); 2181adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean timedout = false; 2182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int interruptMode = 0; 2183adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (!isOnSyncQueue(node)) { 2184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (nanosTimeout <= 0L) { 2185bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson timedout = transferAfterCancelledWait(node); 2186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 2187adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2188b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD) 21896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson LockSupport.parkNanos(this, nanosTimeout); 2190adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 2191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project break; 219291770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle nanosTimeout = deadline - System.nanoTime(); 2193adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2194adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 2195adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project interruptMode = REINTERRUPT; 2196bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (node.nextWaiter != null) 2197bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson unlinkCancelledWaiters(); 2198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (interruptMode != 0) 2199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project reportInterruptAfterWait(interruptMode); 2200adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return !timedout; 2201adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2202adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // support for instrumentation 2204adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2205adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2206adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns true if this condition was created by the given 2207bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * synchronization object. 2208bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 2209bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if owned 2210adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2211adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final boolean isOwnedBy(AbstractQueuedSynchronizer sync) { 2212adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return sync == AbstractQueuedSynchronizer.this; 2213adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2214adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2215adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Queries whether any threads are waiting on this condition. 2217b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Implements {@link AbstractQueuedSynchronizer#hasWaiters(ConditionObject)}. 2218bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 2219bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return {@code true} if there are any waiting threads 2220adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 2221bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * returns {@code false} 2222bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 2223adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected final boolean hasWaiters() { 2224bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (!isHeldExclusively()) 2225adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalMonitorStateException(); 2226adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node w = firstWaiter; w != null; w = w.nextWaiter) { 2227adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (w.waitStatus == Node.CONDITION) 2228adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 2229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2230adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 2231adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2232adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2233adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2234adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an estimate of the number of threads waiting on 2235bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this condition. 2236b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Implements {@link AbstractQueuedSynchronizer#getWaitQueueLength(ConditionObject)}. 2237bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 2238bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the estimated number of waiting threads 2239adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 2240bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * returns {@code false} 2241bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 2242adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected final int getWaitQueueLength() { 2243bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (!isHeldExclusively()) 2244adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalMonitorStateException(); 2245adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int n = 0; 2246adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node w = firstWaiter; w != null; w = w.nextWaiter) { 2247adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (w.waitStatus == Node.CONDITION) 2248adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ++n; 2249adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2250adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return n; 2251adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2252adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2253adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2254adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a collection containing those threads that may be 2255bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * waiting on this Condition. 2256b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Implements {@link AbstractQueuedSynchronizer#getWaitingThreads(ConditionObject)}. 2257bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 2258adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the collection of threads 2259adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 2260bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * returns {@code false} 2261adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2262adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected final Collection<Thread> getWaitingThreads() { 2263bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (!isHeldExclusively()) 2264adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalMonitorStateException(); 2265b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak ArrayList<Thread> list = new ArrayList<>(); 2266adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (Node w = firstWaiter; w != null; w = w.nextWaiter) { 2267adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (w.waitStatus == Node.CONDITION) { 2268adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Thread t = w.thread; 2269adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (t != null) 2270adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project list.add(t); 2271adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2272adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2273adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return list; 2274adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2275adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2278adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Setup to support compareAndSet. We need to natively implement 2279adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * this here: For the sake of permitting future enhancements, we 2280adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * cannot explicitly subclass AtomicInteger, which would be 2281adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * efficient and useful otherwise. So, as the lesser of evils, we 2282adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * natively implement using hotspot intrinsics API. And while we 2283adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * are at it, we do the same for other CASable fields (which could 2284adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * otherwise be done with atomic field updaters). 2285adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2286b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 2287b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long STATE; 2288b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long HEAD; 2289b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long TAIL; 2290adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2291adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static { 2292adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 2293b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak STATE = U.objectFieldOffset 2294adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project (AbstractQueuedSynchronizer.class.getDeclaredField("state")); 2295b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak HEAD = U.objectFieldOffset 2296adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project (AbstractQueuedSynchronizer.class.getDeclaredField("head")); 2297b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak TAIL = U.objectFieldOffset 2298adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project (AbstractQueuedSynchronizer.class.getDeclaredField("tail")); 2299b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (ReflectiveOperationException e) { 2300b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw new Error(e); 2301b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 2302aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath 2303aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath // Reduce the risk of rare disastrous classloading in first call to 2304aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773 2305aa2ed9e105504f21641d919b410c692981cfe386Narayan Kamath Class<?> ensureLoaded = LockSupport.class; 2306adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 2308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2309b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Initializes head and tail fields on first contention. 2310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2311b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private final void initializeSyncQueue() { 2312b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Node h; 2313b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (U.compareAndSwapObject(this, HEAD, null, (h = new Node()))) 2314b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak tail = h; 2315adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2316bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 2317adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2318b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * CASes tail field. 2319adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 2320adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private final boolean compareAndSetTail(Node expect, Node update) { 2321b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapObject(this, TAIL, expect, update); 2322bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 2323adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 2324