1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.  Oracle designates this
   7  * particular file as subject to the "Classpath" exception as provided
   8  * by Oracle in the LICENSE file that accompanied this code.
   9  *
  10  * This code is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * version 2 for more details (a copy is included in the LICENSE file that
  14  * accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License version
  17  * 2 along with this work; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  19  *
  20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  21  * or visit www.oracle.com if you need additional information or have any
  22  * questions.
  23  */
  24 
  25 /*
  26  * This file is available under and governed by the GNU General Public
  27  * License version 2 only, as published by the Free Software Foundation.
  28  * However, the following notice accompanied the original version of this
  29  * file:
  30  *
  31  * Written by Doug Lea with assistance from members of JCP JSR-166
  32  * Expert Group and released to the public domain, as explained at
  33  * http://creativecommons.org/publicdomain/zero/1.0/
  34  */
  35 
  36 package java.util.concurrent.locks;
  37 
  38 import java.util.concurrent.TimeUnit;
  39 
  40 import jdk.internal.misc.Strands;
  41 import jdk.internal.misc.Unsafe;
  42 
  43 /**
  44  * Basic thread blocking primitives for creating locks and other
  45  * synchronization classes.
  46  *
  47  * <p>This class associates, with each thread that uses it, a permit
  48  * (in the sense of the {@link java.util.concurrent.Semaphore
  49  * Semaphore} class). A call to {@code park} will return immediately
  50  * if the permit is available, consuming it in the process; otherwise
  51  * it <em>may</em> block.  A call to {@code unpark} makes the permit
  52  * available, if it was not already available. (Unlike with Semaphores
  53  * though, permits do not accumulate. There is at most one.)
  54  * Reliable usage requires the use of volatile (or atomic) variables
  55  * to control when to park or unpark.  Orderings of calls to these
  56  * methods are maintained with respect to volatile variable accesses,
  57  * but not necessarily non-volatile variable accesses.
  58  *
  59  * <p>Methods {@code park} and {@code unpark} provide efficient
  60  * means of blocking and unblocking threads that do not encounter the
  61  * problems that cause the deprecated methods {@code Thread.suspend}
  62  * and {@code Thread.resume} to be unusable for such purposes: Races
  63  * between one thread invoking {@code park} and another thread trying
  64  * to {@code unpark} it will preserve liveness, due to the
  65  * permit. Additionally, {@code park} will return if the caller's
  66  * thread was interrupted, and timeout versions are supported. The
  67  * {@code park} method may also return at any other time, for "no
  68  * reason", so in general must be invoked within a loop that rechecks
  69  * conditions upon return. In this sense {@code park} serves as an
  70  * optimization of a "busy wait" that does not waste as much time
  71  * spinning, but must be paired with an {@code unpark} to be
  72  * effective.
  73  *
  74  * <p>The three forms of {@code park} each also support a
  75  * {@code blocker} object parameter. This object is recorded while
  76  * the thread is blocked to permit monitoring and diagnostic tools to
  77  * identify the reasons that threads are blocked. (Such tools may
  78  * access blockers using method {@link #getBlocker(Thread)}.)
  79  * The use of these forms rather than the original forms without this
  80  * parameter is strongly encouraged. The normal argument to supply as
  81  * a {@code blocker} within a lock implementation is {@code this}.
  82  *
  83  * <p>These methods are designed to be used as tools for creating
  84  * higher-level synchronization utilities, and are not in themselves
  85  * useful for most concurrency control applications.  The {@code park}
  86  * method is designed for use only in constructions of the form:
  87  *
  88  * <pre> {@code
  89  * while (!canProceed()) {
  90  *   // ensure request to unpark is visible to other threads
  91  *   ...
  92  *   LockSupport.park(this);
  93  * }}</pre>
  94  *
  95  * where no actions by the thread publishing a request to unpark,
  96  * prior to the call to {@code park}, entail locking or blocking.
  97  * Because only one permit is associated with each thread, any
  98  * intermediary uses of {@code park}, including implicitly via class
  99  * loading, could lead to an unresponsive thread (a "lost unpark").
 100  *
 101  * <p><b>Sample Usage.</b> Here is a sketch of a first-in-first-out
 102  * non-reentrant lock class:
 103  * <pre> {@code
 104  * class FIFOMutex {
 105  *   private final AtomicBoolean locked = new AtomicBoolean(false);
 106  *   private final Queue<Thread> waiters
 107  *     = new ConcurrentLinkedQueue<>();
 108  *
 109  *   public void lock() {
 110  *     boolean wasInterrupted = false;
 111  *     // publish current thread for unparkers
 112  *     waiters.add(Thread.currentThread());
 113  *
 114  *     // Block while not first in queue or cannot acquire lock
 115  *     while (waiters.peek() != Thread.currentThread() ||
 116  *            !locked.compareAndSet(false, true)) {
 117  *       LockSupport.park(this);
 118  *       // ignore interrupts while waiting
 119  *       if (Thread.interrupted())
 120  *         wasInterrupted = true;
 121  *     }
 122  *
 123  *     waiters.remove();
 124  *     // ensure correct interrupt status on return
 125  *     if (wasInterrupted)
 126  *       Thread.currentThread().interrupt();
 127  *   }
 128  *
 129  *   public void unlock() {
 130  *     locked.set(false);
 131  *     LockSupport.unpark(waiters.peek());
 132  *   }
 133  *
 134  *   static {
 135  *     // Reduce the risk of "lost unpark" due to classloading
 136  *     Class<?> ensureLoaded = LockSupport.class;
 137  *   }
 138  * }}</pre>
 139  *
 140  * @since 1.5
 141  */
 142 public class LockSupport {
 143     private LockSupport() {} // Cannot be instantiated.
 144 
 145     private static void setBlocker(Thread t, Object arg) {
 146         // Even though volatile, hotspot doesn't need a write barrier here.
 147         U.putReference(t, THREAD_PARKBLOCKER, arg);
 148     }
 149 
 150     private static void setBlocker(Fiber<?> f, Object arg) {
 151         // Even though volatile, hotspot doesn't need a write barrier here.
 152         U.putReference(f, FIBER_PARKBLOCKER, arg);
 153     }
 154 
 155     /**
 156      * Makes available the permit for the given thread, if it
 157      * was not already available.  If the thread was blocked on
 158      * {@code park} then it will unblock.  Otherwise, its next call
 159      * to {@code park} is guaranteed not to block. This operation
 160      * is not guaranteed to have any effect at all if the given
 161      * thread has not been started.
 162      *
 163      * @param thread the thread to unpark, or {@code null}, in which case
 164      *        this operation has no effect
 165      */
 166     public static void unpark(Thread thread) {
 167         if (thread != null) {
 168             Fiber<?> fiber = Strands.getFiber(thread);
 169             if (fiber != null) {
 170                 Strands.unparkFiber(fiber); // can throw RejectedExecutionException
 171             } else {
 172                 U.unpark(thread);
 173             }
 174         }
 175     }
 176 
 177     /**
 178      * Makes available the permit for the given strand, if it
 179      * was not already available.  If the strand was blocked on
 180      * {@code park} then it will unblock.  Otherwise, its next call
 181      * to {@code park} is guaranteed not to block. This operation
 182      * is not guaranteed to have any effect at all if the given
 183      * strand is a Thread that has not been started.
 184      *
 185      * @param strand the strand to unpark, or {@code null}, in which case
 186      *        this operation has no effect
 187      * @throws IllegalArgumentException if strand is not a {@code Thread},
 188      *         {@code Fiber} or {@code null}
 189      */
 190     public static void unpark(Object strand) {
 191         if (strand != null) {
 192             if (strand instanceof Thread) {
 193                 unpark((Thread) strand);
 194             } else if (strand instanceof Fiber) {
 195                 Strands.unparkFiber((Fiber<?>) strand);  // can throw RejectedExecutionException
 196             } else {
 197                 throw new IllegalArgumentException();
 198             }
 199         }
 200     }
 201 
 202     /**
 203      * Disables the current thread for thread scheduling purposes unless the
 204      * permit is available.
 205      *
 206      * <p>If the permit is available then it is consumed and the call returns
 207      * immediately; otherwise
 208      * the current thread becomes disabled for thread scheduling
 209      * purposes and lies dormant until one of three things happens:
 210      *
 211      * <ul>
 212      * <li>Some other thread invokes {@link #unpark unpark} with the
 213      * current thread as the target; or
 214      *
 215      * <li>Some other thread {@linkplain Thread#interrupt interrupts}
 216      * the current thread; or
 217      *
 218      * <li>The call spuriously (that is, for no reason) returns.
 219      * </ul>
 220      *
 221      * <p>This method does <em>not</em> report which of these caused the
 222      * method to return. Callers should re-check the conditions which caused
 223      * the thread to park in the first place. Callers may also determine,
 224      * for example, the interrupt status of the thread upon return.
 225      *
 226      * @param blocker the synchronization object responsible for this
 227      *        thread parking
 228      * @since 1.6
 229      */
 230     public static void park(Object blocker) {
 231         Object strand = Strands.currentStrand();
 232         if (strand instanceof Fiber) {
 233             Fiber<?> fiber = (Fiber<?>) strand;
 234             setBlocker(fiber, blocker);
 235             Strands.parkFiber();
 236             setBlocker(fiber, null);
 237         } else {
 238             Thread thread = (Thread) strand;
 239             setBlocker(thread, blocker);
 240             U.park(false, 0L);
 241             setBlocker(thread, null);
 242         }
 243     }
 244 
 245     /**
 246      * Disables the current thread for thread scheduling purposes, for up to
 247      * the specified waiting time, unless the permit is available.
 248      *
 249      * <p>If the specified waiting time is zero or negative, the
 250      * method does nothing. Otherwise, if the permit is available then
 251      * it is consumed and the call returns immediately; otherwise the
 252      * current thread becomes disabled for thread scheduling purposes
 253      * and lies dormant until one of four things happens:
 254      *
 255      * <ul>
 256      * <li>Some other thread invokes {@link #unpark unpark} with the
 257      * current thread as the target; or
 258      *
 259      * <li>Some other thread {@linkplain Thread#interrupt interrupts}
 260      * the current thread; or
 261      *
 262      * <li>The specified waiting time elapses; or
 263      *
 264      * <li>The call spuriously (that is, for no reason) returns.
 265      * </ul>
 266      *
 267      * <p>This method does <em>not</em> report which of these caused the
 268      * method to return. Callers should re-check the conditions which caused
 269      * the thread to park in the first place. Callers may also determine,
 270      * for example, the interrupt status of the thread, or the elapsed time
 271      * upon return.
 272      *
 273      * @param blocker the synchronization object responsible for this
 274      *        thread parking
 275      * @param nanos the maximum number of nanoseconds to wait
 276      * @since 1.6
 277      */
 278     public static void parkNanos(Object blocker, long nanos) {
 279         if (nanos > 0) {
 280             Object strand = Strands.currentStrand();
 281             if (strand instanceof Fiber) {
 282                 Fiber<?> fiber = (Fiber<?>) strand;
 283                 setBlocker(fiber, blocker);
 284                 Strands.parkFiber(nanos);
 285                 setBlocker(fiber, null);
 286             } else {
 287                 Thread thread = (Thread) strand;
 288                 setBlocker(thread, blocker);
 289                 U.park(false, nanos);
 290                 setBlocker(thread, null);
 291             }
 292         }
 293     }
 294 
 295     /**
 296      * Disables the current thread for thread scheduling purposes, until
 297      * the specified deadline, unless the permit is available.
 298      *
 299      * <p>If the permit is available then it is consumed and the call
 300      * returns immediately; otherwise the current thread becomes disabled
 301      * for thread scheduling purposes and lies dormant until one of four
 302      * things happens:
 303      *
 304      * <ul>
 305      * <li>Some other thread invokes {@link #unpark unpark} with the
 306      * current thread as the target; or
 307      *
 308      * <li>Some other thread {@linkplain Thread#interrupt interrupts} the
 309      * current thread; or
 310      *
 311      * <li>The specified deadline passes; or
 312      *
 313      * <li>The call spuriously (that is, for no reason) returns.
 314      * </ul>
 315      *
 316      * <p>This method does <em>not</em> report which of these caused the
 317      * method to return. Callers should re-check the conditions which caused
 318      * the thread to park in the first place. Callers may also determine,
 319      * for example, the interrupt status of the thread, or the current time
 320      * upon return.
 321      *
 322      * @param blocker the synchronization object responsible for this
 323      *        thread parking
 324      * @param deadline the absolute time, in milliseconds from the Epoch,
 325      *        to wait until
 326      * @since 1.6
 327      */
 328     public static void parkUntil(Object blocker, long deadline) {
 329         Object strand = Strands.currentStrand();
 330         if (strand instanceof Fiber) {
 331             Fiber<?> fiber = (Fiber<?>) strand;
 332             setBlocker(fiber, blocker);
 333             long millis = deadline - System.currentTimeMillis();
 334             long nanos = TimeUnit.NANOSECONDS.convert(millis, TimeUnit.MILLISECONDS);
 335             Strands.parkFiber(nanos);
 336             setBlocker(fiber, null);
 337         } else {
 338             Thread thread = (Thread) strand;
 339             setBlocker(thread, blocker);
 340             U.park(true, deadline);
 341             setBlocker(thread, null);
 342         }
 343     }
 344 
 345     /**
 346      * Returns the blocker object supplied to the most recent
 347      * invocation of a park method that has not yet unblocked, or null
 348      * if not blocked.  The value returned is just a momentary
 349      * snapshot -- the thread may have since unblocked or blocked on a
 350      * different blocker object.
 351      *
 352      * @param t the thread
 353      * @return the blocker
 354      * @throws NullPointerException if argument is null
 355      * @since 1.6
 356      */
 357     public static Object getBlocker(Thread t) {
 358         if (t == null)
 359             throw new NullPointerException();
 360         return U.getReferenceVolatile(t, THREAD_PARKBLOCKER);
 361     }
 362 
 363     /**
 364      * Disables the current thread for thread scheduling purposes unless the
 365      * permit is available.
 366      *
 367      * <p>If the permit is available then it is consumed and the call
 368      * returns immediately; otherwise the current thread becomes disabled
 369      * for thread scheduling purposes and lies dormant until one of three
 370      * things happens:
 371      *
 372      * <ul>
 373      *
 374      * <li>Some other thread invokes {@link #unpark unpark} with the
 375      * current thread as the target; or
 376      *
 377      * <li>Some other thread {@linkplain Thread#interrupt interrupts}
 378      * the current thread; or
 379      *
 380      * <li>The call spuriously (that is, for no reason) returns.
 381      * </ul>
 382      *
 383      * <p>This method does <em>not</em> report which of these caused the
 384      * method to return. Callers should re-check the conditions which caused
 385      * the thread to park in the first place. Callers may also determine,
 386      * for example, the interrupt status of the thread upon return.
 387      */
 388     public static void park() {
 389         Object strand = Strands.currentStrand();
 390         if (strand instanceof Fiber) {
 391             Strands.parkFiber();
 392         } else {
 393             U.park(false, 0L);
 394         }
 395     }
 396 
 397     /**
 398      * Disables the current thread for thread scheduling purposes, for up to
 399      * the specified waiting time, unless the permit is available.
 400      *
 401      * <p>If the specified waiting time is zero or negative, the
 402      * method does nothing. Otherwise, if the permit is available then
 403      * it is consumed and the call returns immediately; otherwise the
 404      * current thread becomes disabled for thread scheduling purposes
 405      * and lies dormant until one of four things happens:
 406      *
 407      * <ul>
 408      * <li>Some other thread invokes {@link #unpark unpark} with the
 409      * current thread as the target; or
 410      *
 411      * <li>Some other thread {@linkplain Thread#interrupt interrupts}
 412      * the current thread; or
 413      *
 414      * <li>The specified waiting time elapses; or
 415      *
 416      * <li>The call spuriously (that is, for no reason) returns.
 417      * </ul>
 418      *
 419      * <p>This method does <em>not</em> report which of these caused the
 420      * method to return. Callers should re-check the conditions which caused
 421      * the thread to park in the first place. Callers may also determine,
 422      * for example, the interrupt status of the thread, or the elapsed time
 423      * upon return.
 424      *
 425      * @param nanos the maximum number of nanoseconds to wait
 426      */
 427     public static void parkNanos(long nanos) {
 428         if (nanos > 0) {
 429             Object strand = Strands.currentStrand();
 430             if (strand instanceof Fiber) {
 431                 Strands.parkFiber(nanos);
 432             } else {
 433                 U.park(false, nanos);
 434             }
 435         }
 436     }
 437 
 438     /**
 439      * Disables the current thread for thread scheduling purposes, until
 440      * the specified deadline, unless the permit is available.
 441      *
 442      * <p>If the permit is available then it is consumed and the call
 443      * returns immediately; otherwise the current thread becomes disabled
 444      * for thread scheduling purposes and lies dormant until one of four
 445      * things happens:
 446      *
 447      * <ul>
 448      * <li>Some other thread invokes {@link #unpark unpark} with the
 449      * current thread as the target; or
 450      *
 451      * <li>Some other thread {@linkplain Thread#interrupt interrupts}
 452      * the current thread; or
 453      *
 454      * <li>The specified deadline passes; or
 455      *
 456      * <li>The call spuriously (that is, for no reason) returns.
 457      * </ul>
 458      *
 459      * <p>This method does <em>not</em> report which of these caused the
 460      * method to return. Callers should re-check the conditions which caused
 461      * the thread to park in the first place. Callers may also determine,
 462      * for example, the interrupt status of the thread, or the current time
 463      * upon return.
 464      *
 465      * @param deadline the absolute time, in milliseconds from the Epoch,
 466      *        to wait until
 467      */
 468     public static void parkUntil(long deadline) {
 469         Object strand = Strands.currentStrand();
 470         if (strand instanceof Fiber) {
 471             long millis = deadline - System.currentTimeMillis();
 472             long nanos = TimeUnit.NANOSECONDS.convert(millis, TimeUnit.MILLISECONDS);
 473             Strands.parkFiber(nanos);
 474         } else {
 475             U.park(true, deadline);
 476         }
 477     }
 478 
 479     /**
 480      * Returns the pseudo-randomly initialized or updated secondary seed.
 481      * Copied from ThreadLocalRandom due to package access restrictions.
 482      */
 483     static final int nextSecondarySeed() {
 484         int r;
 485         Thread t = Thread.currentThread();
 486         if ((r = U.getInt(t, SECONDARY)) != 0) {
 487             r ^= r << 13;   // xorshift
 488             r ^= r >>> 17;
 489             r ^= r << 5;
 490         }
 491         else if ((r = java.util.concurrent.ThreadLocalRandom.current().nextInt()) == 0)
 492             r = 1; // avoid zero
 493         U.putInt(t, SECONDARY, r);
 494         return r;
 495     }
 496 
 497     /**
 498      * Returns the thread id for the given thread.  We must access
 499      * this directly rather than via method Thread.getId() because
 500      * getId() has been known to be overridden in ways that do not
 501      * preserve unique mappings.
 502      */
 503     static final long getThreadId(Thread thread) {
 504         return U.getLong(thread, TID);
 505     }
 506 
 507     // Hotspot implementation via intrinsics API
 508     private static final Unsafe U = Unsafe.getUnsafe();
 509     private static final long THREAD_PARKBLOCKER = U.objectFieldOffset
 510             (Thread.class, "parkBlocker");
 511     private static final long FIBER_PARKBLOCKER = U.objectFieldOffset
 512             (Fiber.class, "parkBlocker");
 513     private static final long SECONDARY = U.objectFieldOffset
 514             (Thread.class, "threadLocalRandomSecondarySeed");
 515     private static final long TID = U.objectFieldOffset
 516             (Thread.class, "tid");
 517 
 518 }