1/*
2 * Written by Doug Lea with assistance from members of JCP JSR-166
3 * Expert Group and released to the public domain, as explained at
4 * http://creativecommons.org/publicdomain/zero/1.0/
5 */
6
7package java.util.concurrent.locks;
8
9/**
10 * Basic thread blocking primitives for creating locks and other
11 * synchronization classes.
12 *
13 * <p>This class associates, with each thread that uses it, a permit
14 * (in the sense of the {@link java.util.concurrent.Semaphore
15 * Semaphore} class). A call to {@code park} will return immediately
16 * if the permit is available, consuming it in the process; otherwise
17 * it <em>may</em> block.  A call to {@code unpark} makes the permit
18 * available, if it was not already available. (Unlike with Semaphores
19 * though, permits do not accumulate. There is at most one.)
20 * Reliable usage requires the use of volatile (or atomic) variables
21 * to control when to park or unpark.  Orderings of calls to these
22 * methods are maintained with respect to volatile variable accesses,
23 * but not necessarily non-volatile variable accesses.
24 *
25 * <p>Methods {@code park} and {@code unpark} provide efficient
26 * means of blocking and unblocking threads that do not encounter the
27 * problems that cause the deprecated methods {@code Thread.suspend}
28 * and {@code Thread.resume} to be unusable for such purposes: Races
29 * between one thread invoking {@code park} and another thread trying
30 * to {@code unpark} it will preserve liveness, due to the
31 * permit. Additionally, {@code park} will return if the caller's
32 * thread was interrupted, and timeout versions are supported. The
33 * {@code park} method may also return at any other time, for "no
34 * reason", so in general must be invoked within a loop that rechecks
35 * conditions upon return. In this sense {@code park} serves as an
36 * optimization of a "busy wait" that does not waste as much time
37 * spinning, but must be paired with an {@code unpark} to be
38 * effective.
39 *
40 * <p>The three forms of {@code park} each also support a
41 * {@code blocker} object parameter. This object is recorded while
42 * the thread is blocked to permit monitoring and diagnostic tools to
43 * identify the reasons that threads are blocked. (Such tools may
44 * access blockers using method {@link #getBlocker(Thread)}.)
45 * The use of these forms rather than the original forms without this
46 * parameter is strongly encouraged. The normal argument to supply as
47 * a {@code blocker} within a lock implementation is {@code this}.
48 *
49 * <p>These methods are designed to be used as tools for creating
50 * higher-level synchronization utilities, and are not in themselves
51 * useful for most concurrency control applications.  The {@code park}
52 * method is designed for use only in constructions of the form:
53 *
54 * <pre> {@code
55 * while (!canProceed()) {
56 *   // ensure request to unpark is visible to other threads
57 *   ...
58 *   LockSupport.park(this);
59 * }}</pre>
60 *
61 * where no actions by the thread publishing a request to unpark,
62 * prior to the call to {@code park}, entail locking or blocking.
63 * Because only one permit is associated with each thread, any
64 * intermediary uses of {@code park}, including implicitly via class
65 * loading, could lead to an unresponsive thread (a "lost unpark").
66 *
67 * <p><b>Sample Usage.</b> Here is a sketch of a first-in-first-out
68 * non-reentrant lock class:
69 * <pre> {@code
70 * class FIFOMutex {
71 *   private final AtomicBoolean locked = new AtomicBoolean(false);
72 *   private final Queue<Thread> waiters
73 *     = new ConcurrentLinkedQueue<>();
74 *
75 *   public void lock() {
76 *     boolean wasInterrupted = false;
77 *     // publish current thread for unparkers
78 *     waiters.add(Thread.currentThread());
79 *
80 *     // Block while not first in queue or cannot acquire lock
81 *     while (waiters.peek() != Thread.currentThread() ||
82 *            !locked.compareAndSet(false, true)) {
83 *       LockSupport.park(this);
84 *       // ignore interrupts while waiting
85 *       if (Thread.interrupted())
86 *         wasInterrupted = true;
87 *     }
88 *
89 *     waiters.remove();
90 *     // ensure correct interrupt status on return
91 *     if (wasInterrupted)
92 *       Thread.currentThread().interrupt();
93 *   }
94 *
95 *   public void unlock() {
96 *     locked.set(false);
97 *     LockSupport.unpark(waiters.peek());
98 *   }
99 *
100 *   static {
101 *     // Reduce the risk of "lost unpark" due to classloading
102 *     Class<?> ensureLoaded = LockSupport.class;
103 *   }
104 * }}</pre>
105 */
106public class LockSupport {
107    private LockSupport() {} // Cannot be instantiated.
108
109    private static void setBlocker(Thread t, Object arg) {
110        // Even though volatile, hotspot doesn't need a write barrier here.
111        U.putObject(t, PARKBLOCKER, arg);
112    }
113
114    /**
115     * Makes available the permit for the given thread, if it
116     * was not already available.  If the thread was blocked on
117     * {@code park} then it will unblock.  Otherwise, its next call
118     * to {@code park} is guaranteed not to block. This operation
119     * is not guaranteed to have any effect at all if the given
120     * thread has not been started.
121     *
122     * @param thread the thread to unpark, or {@code null}, in which case
123     *        this operation has no effect
124     */
125    public static void unpark(Thread thread) {
126        if (thread != null)
127            U.unpark(thread);
128    }
129
130    /**
131     * Disables the current thread for thread scheduling purposes unless the
132     * permit is available.
133     *
134     * <p>If the permit is available then it is consumed and the call returns
135     * immediately; otherwise
136     * the current thread becomes disabled for thread scheduling
137     * purposes and lies dormant until one of three things happens:
138     *
139     * <ul>
140     * <li>Some other thread invokes {@link #unpark unpark} with the
141     * current thread as the target; or
142     *
143     * <li>Some other thread {@linkplain Thread#interrupt interrupts}
144     * the current thread; or
145     *
146     * <li>The call spuriously (that is, for no reason) returns.
147     * </ul>
148     *
149     * <p>This method does <em>not</em> report which of these caused the
150     * method to return. Callers should re-check the conditions which caused
151     * the thread to park in the first place. Callers may also determine,
152     * for example, the interrupt status of the thread upon return.
153     *
154     * @param blocker the synchronization object responsible for this
155     *        thread parking
156     * @since 1.6
157     */
158    public static void park(Object blocker) {
159        Thread t = Thread.currentThread();
160        setBlocker(t, blocker);
161        U.park(false, 0L);
162        setBlocker(t, null);
163    }
164
165    /**
166     * Disables the current thread for thread scheduling purposes, for up to
167     * the specified waiting time, unless the permit is available.
168     *
169     * <p>If the permit is available then it is consumed and the call
170     * returns immediately; otherwise the current thread becomes disabled
171     * for thread scheduling purposes and lies dormant until one of four
172     * things happens:
173     *
174     * <ul>
175     * <li>Some other thread invokes {@link #unpark unpark} with the
176     * current thread as the target; or
177     *
178     * <li>Some other thread {@linkplain Thread#interrupt interrupts}
179     * the current thread; or
180     *
181     * <li>The specified waiting time elapses; or
182     *
183     * <li>The call spuriously (that is, for no reason) returns.
184     * </ul>
185     *
186     * <p>This method does <em>not</em> report which of these caused the
187     * method to return. Callers should re-check the conditions which caused
188     * the thread to park in the first place. Callers may also determine,
189     * for example, the interrupt status of the thread, or the elapsed time
190     * upon return.
191     *
192     * @param blocker the synchronization object responsible for this
193     *        thread parking
194     * @param nanos the maximum number of nanoseconds to wait
195     * @since 1.6
196     */
197    public static void parkNanos(Object blocker, long nanos) {
198        if (nanos > 0) {
199            Thread t = Thread.currentThread();
200            setBlocker(t, blocker);
201            U.park(false, nanos);
202            setBlocker(t, null);
203        }
204    }
205
206    /**
207     * Disables the current thread for thread scheduling purposes, until
208     * the specified deadline, unless the permit is available.
209     *
210     * <p>If the permit is available then it is consumed and the call
211     * returns immediately; otherwise the current thread becomes disabled
212     * for thread scheduling purposes and lies dormant until one of four
213     * things happens:
214     *
215     * <ul>
216     * <li>Some other thread invokes {@link #unpark unpark} with the
217     * current thread as the target; or
218     *
219     * <li>Some other thread {@linkplain Thread#interrupt interrupts} the
220     * current thread; or
221     *
222     * <li>The specified deadline passes; or
223     *
224     * <li>The call spuriously (that is, for no reason) returns.
225     * </ul>
226     *
227     * <p>This method does <em>not</em> report which of these caused the
228     * method to return. Callers should re-check the conditions which caused
229     * the thread to park in the first place. Callers may also determine,
230     * for example, the interrupt status of the thread, or the current time
231     * upon return.
232     *
233     * @param blocker the synchronization object responsible for this
234     *        thread parking
235     * @param deadline the absolute time, in milliseconds from the Epoch,
236     *        to wait until
237     * @since 1.6
238     */
239    public static void parkUntil(Object blocker, long deadline) {
240        Thread t = Thread.currentThread();
241        setBlocker(t, blocker);
242        U.park(true, deadline);
243        setBlocker(t, null);
244    }
245
246    /**
247     * Returns the blocker object supplied to the most recent
248     * invocation of a park method that has not yet unblocked, or null
249     * if not blocked.  The value returned is just a momentary
250     * snapshot -- the thread may have since unblocked or blocked on a
251     * different blocker object.
252     *
253     * @param t the thread
254     * @return the blocker
255     * @throws NullPointerException if argument is null
256     * @since 1.6
257     */
258    public static Object getBlocker(Thread t) {
259        if (t == null)
260            throw new NullPointerException();
261        return U.getObjectVolatile(t, PARKBLOCKER);
262    }
263
264    /**
265     * Disables the current thread for thread scheduling purposes unless the
266     * permit is available.
267     *
268     * <p>If the permit is available then it is consumed and the call
269     * returns immediately; otherwise the current thread becomes disabled
270     * for thread scheduling purposes and lies dormant until one of three
271     * things happens:
272     *
273     * <ul>
274     *
275     * <li>Some other thread invokes {@link #unpark unpark} with the
276     * current thread as the target; or
277     *
278     * <li>Some other thread {@linkplain Thread#interrupt interrupts}
279     * the current thread; or
280     *
281     * <li>The call spuriously (that is, for no reason) returns.
282     * </ul>
283     *
284     * <p>This method does <em>not</em> report which of these caused the
285     * method to return. Callers should re-check the conditions which caused
286     * the thread to park in the first place. Callers may also determine,
287     * for example, the interrupt status of the thread upon return.
288     */
289    public static void park() {
290        U.park(false, 0L);
291    }
292
293    /**
294     * Disables the current thread for thread scheduling purposes, for up to
295     * the specified waiting time, unless the permit is available.
296     *
297     * <p>If the permit is available then it is consumed and the call
298     * returns immediately; otherwise the current thread becomes disabled
299     * for thread scheduling purposes and lies dormant until one of four
300     * things happens:
301     *
302     * <ul>
303     * <li>Some other thread invokes {@link #unpark unpark} with the
304     * current thread as the target; or
305     *
306     * <li>Some other thread {@linkplain Thread#interrupt interrupts}
307     * the current thread; or
308     *
309     * <li>The specified waiting time elapses; or
310     *
311     * <li>The call spuriously (that is, for no reason) returns.
312     * </ul>
313     *
314     * <p>This method does <em>not</em> report which of these caused the
315     * method to return. Callers should re-check the conditions which caused
316     * the thread to park in the first place. Callers may also determine,
317     * for example, the interrupt status of the thread, or the elapsed time
318     * upon return.
319     *
320     * @param nanos the maximum number of nanoseconds to wait
321     */
322    public static void parkNanos(long nanos) {
323        if (nanos > 0)
324            U.park(false, nanos);
325    }
326
327    /**
328     * Disables the current thread for thread scheduling purposes, until
329     * the specified deadline, unless the permit is available.
330     *
331     * <p>If the permit is available then it is consumed and the call
332     * returns immediately; otherwise the current thread becomes disabled
333     * for thread scheduling purposes and lies dormant until one of four
334     * things happens:
335     *
336     * <ul>
337     * <li>Some other thread invokes {@link #unpark unpark} with the
338     * current thread as the target; or
339     *
340     * <li>Some other thread {@linkplain Thread#interrupt interrupts}
341     * the current thread; or
342     *
343     * <li>The specified deadline passes; or
344     *
345     * <li>The call spuriously (that is, for no reason) returns.
346     * </ul>
347     *
348     * <p>This method does <em>not</em> report which of these caused the
349     * method to return. Callers should re-check the conditions which caused
350     * the thread to park in the first place. Callers may also determine,
351     * for example, the interrupt status of the thread, or the current time
352     * upon return.
353     *
354     * @param deadline the absolute time, in milliseconds from the Epoch,
355     *        to wait until
356     */
357    public static void parkUntil(long deadline) {
358        U.park(true, deadline);
359    }
360
361    /**
362     * Returns the pseudo-randomly initialized or updated secondary seed.
363     * Copied from ThreadLocalRandom due to package access restrictions.
364     */
365    static final int nextSecondarySeed() {
366        int r;
367        Thread t = Thread.currentThread();
368        if ((r = U.getInt(t, SECONDARY)) != 0) {
369            r ^= r << 13;   // xorshift
370            r ^= r >>> 17;
371            r ^= r << 5;
372        }
373        else if ((r = java.util.concurrent.ThreadLocalRandom.current().nextInt()) == 0)
374            r = 1; // avoid zero
375        U.putInt(t, SECONDARY, r);
376        return r;
377    }
378
379    // Hotspot implementation via intrinsics API
380    private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
381    private static final long PARKBLOCKER;
382    private static final long SECONDARY;
383    static {
384        try {
385            PARKBLOCKER = U.objectFieldOffset
386                (Thread.class.getDeclaredField("parkBlocker"));
387            SECONDARY = U.objectFieldOffset
388                (Thread.class.getDeclaredField("threadLocalRandomSecondarySeed"));
389        } catch (ReflectiveOperationException e) {
390            throw new Error(e);
391        }
392    }
393
394}
395