001/*
002 * Copyright (C) 2010 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.util.concurrent;
016
017import static com.google.common.base.Preconditions.checkNotNull;
018
019import com.google.common.annotations.Beta;
020import com.google.common.annotations.GwtIncompatible;
021import com.google.errorprone.annotations.concurrent.GuardedBy;
022import com.google.j2objc.annotations.Weak;
023import java.util.concurrent.TimeUnit;
024import java.util.concurrent.locks.Condition;
025import java.util.concurrent.locks.ReentrantLock;
026import java.util.function.BooleanSupplier;
027import org.checkerframework.checker.nullness.qual.Nullable;
028
029/**
030 * A synchronization abstraction supporting waiting on arbitrary boolean conditions.
031 *
032 * <p>This class is intended as a replacement for {@link ReentrantLock}. Code using {@code Monitor}
033 * is less error-prone and more readable than code using {@code ReentrantLock}, without significant
034 * performance loss. {@code Monitor} even has the potential for performance gain by optimizing the
035 * evaluation and signaling of conditions. Signaling is entirely <a
036 * href="http://en.wikipedia.org/wiki/Monitor_(synchronization)#Implicit_signaling">implicit</a>. By
037 * eliminating explicit signaling, this class can guarantee that only one thread is awakened when a
038 * condition becomes true (no "signaling storms" due to use of {@link
039 * java.util.concurrent.locks.Condition#signalAll Condition.signalAll}) and that no signals are lost
040 * (no "hangs" due to incorrect use of {@link java.util.concurrent.locks.Condition#signal
041 * Condition.signal}).
042 *
043 * <p>A thread is said to <i>occupy</i> a monitor if it has <i>entered</i> the monitor but not yet
044 * <i>left</i>. Only one thread may occupy a given monitor at any moment. A monitor is also
045 * reentrant, so a thread may enter a monitor any number of times, and then must leave the same
046 * number of times. The <i>enter</i> and <i>leave</i> operations have the same synchronization
047 * semantics as the built-in Java language synchronization primitives.
048 *
049 * <p>A call to any of the <i>enter</i> methods with <b>void</b> return type should always be
050 * followed immediately by a <i>try/finally</i> block to ensure that the current thread leaves the
051 * monitor cleanly:
052 *
053 * <pre>{@code
054 * monitor.enter();
055 * try {
056 *   // do things while occupying the monitor
057 * } finally {
058 *   monitor.leave();
059 * }
060 * }</pre>
061 *
062 * <p>A call to any of the <i>enter</i> methods with <b>boolean</b> return type should always appear
063 * as the condition of an <i>if</i> statement containing a <i>try/finally</i> block to ensure that
064 * the current thread leaves the monitor cleanly:
065 *
066 * <pre>{@code
067 * if (monitor.tryEnter()) {
068 *   try {
069 *     // do things while occupying the monitor
070 *   } finally {
071 *     monitor.leave();
072 *   }
073 * } else {
074 *   // do other things since the monitor was not available
075 * }
076 * }</pre>
077 *
078 * <h2>Comparison with {@code synchronized} and {@code ReentrantLock}</h2>
079 *
080 * <p>The following examples show a simple threadsafe holder expressed using {@code synchronized},
081 * {@link ReentrantLock}, and {@code Monitor}.
082 *
083 * <h3>{@code synchronized}</h3>
084 *
085 * <p>This version is the fewest lines of code, largely because the synchronization mechanism used
086 * is built into the language and runtime. But the programmer has to remember to avoid a couple of
087 * common bugs: The {@code wait()} must be inside a {@code while} instead of an {@code if}, and
088 * {@code notifyAll()} must be used instead of {@code notify()} because there are two different
089 * logical conditions being awaited.
090 *
091 * <pre>{@code
092 * public class SafeBox<V> {
093 *   private V value;
094 *
095 *   public synchronized V get() throws InterruptedException {
096 *     while (value == null) {
097 *       wait();
098 *     }
099 *     V result = value;
100 *     value = null;
101 *     notifyAll();
102 *     return result;
103 *   }
104 *
105 *   public synchronized void set(V newValue) throws InterruptedException {
106 *     while (value != null) {
107 *       wait();
108 *     }
109 *     value = newValue;
110 *     notifyAll();
111 *   }
112 * }
113 * }</pre>
114 *
115 * <h3>{@code ReentrantLock}</h3>
116 *
117 * <p>This version is much more verbose than the {@code synchronized} version, and still suffers
118 * from the need for the programmer to remember to use {@code while} instead of {@code if}. However,
119 * one advantage is that we can introduce two separate {@code Condition} objects, which allows us to
120 * use {@code signal()} instead of {@code signalAll()}, which may be a performance benefit.
121 *
122 * <pre>{@code
123 * public class SafeBox<V> {
124 *   private V value;
125 *   private final ReentrantLock lock = new ReentrantLock();
126 *   private final Condition valuePresent = lock.newCondition();
127 *   private final Condition valueAbsent = lock.newCondition();
128 *
129 *   public V get() throws InterruptedException {
130 *     lock.lock();
131 *     try {
132 *       while (value == null) {
133 *         valuePresent.await();
134 *       }
135 *       V result = value;
136 *       value = null;
137 *       valueAbsent.signal();
138 *       return result;
139 *     } finally {
140 *       lock.unlock();
141 *     }
142 *   }
143 *
144 *   public void set(V newValue) throws InterruptedException {
145 *     lock.lock();
146 *     try {
147 *       while (value != null) {
148 *         valueAbsent.await();
149 *       }
150 *       value = newValue;
151 *       valuePresent.signal();
152 *     } finally {
153 *       lock.unlock();
154 *     }
155 *   }
156 * }
157 * }</pre>
158 *
159 * <h3>{@code Monitor}</h3>
160 *
161 * <p>This version adds some verbosity around the {@code Guard} objects, but removes that same
162 * verbosity, and more, from the {@code get} and {@code set} methods. {@code Monitor} implements the
163 * same efficient signaling as we had to hand-code in the {@code ReentrantLock} version above.
164 * Finally, the programmer no longer has to hand-code the wait loop, and therefore doesn't have to
165 * remember to use {@code while} instead of {@code if}.
166 *
167 * <pre>{@code
168 * public class SafeBox<V> {
169 *   private V value;
170 *   private final Monitor monitor = new Monitor();
171 *   private final Monitor.Guard valuePresent = monitor.newGuard(() -> value != null);
172 *   private final Monitor.Guard valueAbsent = monitor.newGuard(() -> value == null);
173 *
174 *   public V get() throws InterruptedException {
175 *     monitor.enterWhen(valuePresent);
176 *     try {
177 *       V result = value;
178 *       value = null;
179 *       return result;
180 *     } finally {
181 *       monitor.leave();
182 *     }
183 *   }
184 *
185 *   public void set(V newValue) throws InterruptedException {
186 *     monitor.enterWhen(valueAbsent);
187 *     try {
188 *       value = newValue;
189 *     } finally {
190 *       monitor.leave();
191 *     }
192 *   }
193 * }
194 * }</pre>
195 *
196 * @author Justin T. Sampson
197 * @author Martin Buchholz
198 * @since 10.0
199 */
200@Beta
201@GwtIncompatible
202@SuppressWarnings("GuardedBy") // TODO(b/35466881): Fix or suppress.
203public final class Monitor {
204  // TODO(user): Use raw LockSupport or AbstractQueuedSynchronizer instead of ReentrantLock.
205  // TODO(user): "Port" jsr166 tests for ReentrantLock.
206  //
207  // TODO(user): Change API to make it impossible to use a Guard with the "wrong" monitor,
208  //    by making the monitor implicit, and to eliminate other sources of IMSE.
209  //    Imagine:
210  //    guard.lock();
211  //    try { /* monitor locked and guard satisfied here */ }
212  //    finally { guard.unlock(); }
213  // Here are Justin's design notes about this:
214  //
215  // This idea has come up from time to time, and I think one of my
216  // earlier versions of Monitor even did something like this. I ended
217  // up strongly favoring the current interface.
218  //
219  // I probably can't remember all the reasons (it's possible you
220  // could find them in the code review archives), but here are a few:
221  //
222  // 1. What about leaving/unlocking? Are you going to do
223  //    guard.enter() paired with monitor.leave()? That might get
224  //    confusing. It's nice for the finally block to look as close as
225  //    possible to the thing right before the try. You could have
226  //    guard.leave(), but that's a little odd as well because the
227  //    guard doesn't have anything to do with leaving. You can't
228  //    really enforce that the guard you're leaving is the same one
229  //    you entered with, and it doesn't actually matter.
230  //
231  // 2. Since you can enter the monitor without a guard at all, some
232  //    places you'll have monitor.enter()/monitor.leave() and other
233  //    places you'll have guard.enter()/guard.leave() even though
234  //    it's the same lock being acquired underneath. Always using
235  //    monitor.enterXXX()/monitor.leave() will make it really clear
236  //    which lock is held at any point in the code.
237  //
238  // 3. I think "enterWhen(notEmpty)" reads better than "notEmpty.enter()".
239  //
240  // TODO(user): Implement ReentrantLock features:
241  //    - toString() method
242  //    - getOwner() method
243  //    - getQueuedThreads() method
244  //    - getWaitingThreads(Guard) method
245  //    - implement Serializable
246  //    - redo the API to be as close to identical to ReentrantLock as possible,
247  //      since, after all, this class is also a reentrant mutual exclusion lock!?
248
249  /*
250   * One of the key challenges of this class is to prevent lost signals, while trying hard to
251   * minimize unnecessary signals. One simple and correct algorithm is to signal some other waiter
252   * with a satisfied guard (if one exists) whenever any thread occupying the monitor exits the
253   * monitor, either by unlocking all of its held locks, or by starting to wait for a guard. This
254   * includes exceptional exits, so all control paths involving signalling must be protected by a
255   * finally block.
256   *
257   * Further optimizations of this algorithm become increasingly subtle. A wait that terminates
258   * without the guard being satisfied (due to timeout, but not interrupt) can then immediately exit
259   * the monitor without signalling. If it timed out without being signalled, it does not need to
260   * "pass on" the signal to another thread. If it *was* signalled, then its guard must have been
261   * satisfied at the time of signal, and has since been modified by some other thread to be
262   * non-satisfied before reacquiring the lock, and that other thread takes over the responsibility
263   * of signaling the next waiter.
264   *
265   * Unlike the underlying Condition, if we are not careful, an interrupt *can* cause a signal to be
266   * lost, because the signal may be sent to a condition whose sole waiter has just been
267   * interrupted.
268   *
269   * Imagine a monitor with multiple guards. A thread enters the monitor, satisfies all the guards,
270   * and leaves, calling signalNextWaiter. With traditional locks and conditions, all the conditions
271   * need to be signalled because it is not known which if any of them have waiters (and hasWaiters
272   * can't be used reliably because of a check-then-act race). With our Monitor guards, we only
273   * signal the first active guard that is satisfied. But the corresponding thread may have already
274   * been interrupted and is waiting to reacquire the lock while still registered in activeGuards,
275   * in which case the signal is a no-op, and the bigger-picture signal is lost unless interrupted
276   * threads take special action by participating in the signal-passing game.
277   */
278
279  /*
280   * Timeout handling is intricate, especially given our ambitious goals:
281   * - Avoid underflow and overflow of timeout values when specified timeouts are close to
282   *   Long.MIN_VALUE or Long.MAX_VALUE.
283   * - Favor responding to interrupts over timeouts.
284   * - System.nanoTime() is expensive enough that we want to call it the minimum required number of
285   *   times, typically once before invoking a blocking method. This often requires keeping track of
286   *   the first time in a method that nanoTime() has been invoked, for which the special value 0L
287   *   is reserved to mean "uninitialized". If timeout is non-positive, then nanoTime need never be
288   *   called.
289   * - Keep behavior of fair and non-fair instances consistent.
290   */
291
292  /**
293   * A boolean condition for which a thread may wait. A {@code Guard} is associated with a single
294   * {@code Monitor}. The monitor may check the guard at arbitrary times from any thread occupying
295   * the monitor, so code should not be written to rely on how often a guard might or might not be
296   * checked.
297   *
298   * <p>If a {@code Guard} is passed into any method of a {@code Monitor} other than the one it is
299   * associated with, an {@link IllegalMonitorStateException} is thrown.
300   *
301   * @since 10.0
302   */
303  @Beta
304  public abstract static class Guard {
305
306    @Weak final Monitor monitor;
307    final Condition condition;
308
309    @GuardedBy("monitor.lock")
310    int waiterCount = 0;
311
312    /** The next active guard */
313    @GuardedBy("monitor.lock")
314    @Nullable
315    Guard next;
316
317    protected Guard(Monitor monitor) {
318      this.monitor = checkNotNull(monitor, "monitor");
319      this.condition = monitor.lock.newCondition();
320    }
321
322    /**
323     * Evaluates this guard's boolean condition. This method is always called with the associated
324     * monitor already occupied. Implementations of this method must depend only on state protected
325     * by the associated monitor, and must not modify that state.
326     */
327    public abstract boolean isSatisfied();
328  }
329
330  /** Whether this monitor is fair. */
331  private final boolean fair;
332
333  /** The lock underlying this monitor. */
334  private final ReentrantLock lock;
335
336  /**
337   * The guards associated with this monitor that currently have waiters ({@code waiterCount > 0}).
338   * A linked list threaded through the Guard.next field.
339   */
340  @GuardedBy("lock")
341  private Guard activeGuards = null;
342
343  /**
344   * Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to {@code
345   * Monitor(false)}.
346   */
347  public Monitor() {
348    this(false);
349  }
350
351  /**
352   * Creates a monitor with the given ordering policy.
353   *
354   * @param fair whether this monitor should use a fair ordering policy rather than a non-fair (but
355   *     fast) one
356   */
357  public Monitor(boolean fair) {
358    this.fair = fair;
359    this.lock = new ReentrantLock(fair);
360  }
361
362  /**
363   * Creates a new {@linkplain Guard guard} for this monitor.
364   *
365   * @param isSatisfied the new guard's boolean condition (see {@link Guard#isSatisfied
366   *     isSatisfied()})
367   * @since 21.0
368   */
369  public Guard newGuard(final BooleanSupplier isSatisfied) {
370    checkNotNull(isSatisfied, "isSatisfied");
371    return new Guard(this) {
372      @Override
373      public boolean isSatisfied() {
374        return isSatisfied.getAsBoolean();
375      }
376    };
377  }
378
379  /** Enters this monitor. Blocks indefinitely. */
380  public void enter() {
381    lock.lock();
382  }
383
384  /**
385   * Enters this monitor. Blocks at most the given time.
386   *
387   * @return whether the monitor was entered
388   */
389  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
390  public boolean enter(long time, TimeUnit unit) {
391    final long timeoutNanos = toSafeNanos(time, unit);
392    final ReentrantLock lock = this.lock;
393    if (!fair && lock.tryLock()) {
394      return true;
395    }
396    boolean interrupted = Thread.interrupted();
397    try {
398      final long startTime = System.nanoTime();
399      for (long remainingNanos = timeoutNanos; ; ) {
400        try {
401          return lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS);
402        } catch (InterruptedException interrupt) {
403          interrupted = true;
404          remainingNanos = remainingNanos(startTime, timeoutNanos);
405        }
406      }
407    } finally {
408      if (interrupted) {
409        Thread.currentThread().interrupt();
410      }
411    }
412  }
413
414  /**
415   * Enters this monitor. Blocks indefinitely, but may be interrupted.
416   *
417   * @throws InterruptedException if interrupted while waiting
418   */
419  public void enterInterruptibly() throws InterruptedException {
420    lock.lockInterruptibly();
421  }
422
423  /**
424   * Enters this monitor. Blocks at most the given time, and may be interrupted.
425   *
426   * @return whether the monitor was entered
427   * @throws InterruptedException if interrupted while waiting
428   */
429  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
430  public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException {
431    return lock.tryLock(time, unit);
432  }
433
434  /**
435   * Enters this monitor if it is possible to do so immediately. Does not block.
436   *
437   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
438   *
439   * @return whether the monitor was entered
440   */
441  public boolean tryEnter() {
442    return lock.tryLock();
443  }
444
445  /**
446   * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted.
447   *
448   * @throws InterruptedException if interrupted while waiting
449   */
450  public void enterWhen(Guard guard) throws InterruptedException {
451    if (guard.monitor != this) {
452      throw new IllegalMonitorStateException();
453    }
454    final ReentrantLock lock = this.lock;
455    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
456    lock.lockInterruptibly();
457
458    boolean satisfied = false;
459    try {
460      if (!guard.isSatisfied()) {
461        await(guard, signalBeforeWaiting);
462      }
463      satisfied = true;
464    } finally {
465      if (!satisfied) {
466        leave();
467      }
468    }
469  }
470
471  /**
472   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
473   * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be
474   * interrupted.
475   *
476   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
477   * @throws InterruptedException if interrupted while waiting
478   */
479  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
480  public boolean enterWhen(Guard guard, long time, TimeUnit unit) throws InterruptedException {
481    final long timeoutNanos = toSafeNanos(time, unit);
482    if (guard.monitor != this) {
483      throw new IllegalMonitorStateException();
484    }
485    final ReentrantLock lock = this.lock;
486    boolean reentrant = lock.isHeldByCurrentThread();
487    long startTime = 0L;
488
489    locked:
490    {
491      if (!fair) {
492        // Check interrupt status to get behavior consistent with fair case.
493        if (Thread.interrupted()) {
494          throw new InterruptedException();
495        }
496        if (lock.tryLock()) {
497          break locked;
498        }
499      }
500      startTime = initNanoTime(timeoutNanos);
501      if (!lock.tryLock(time, unit)) {
502        return false;
503      }
504    }
505
506    boolean satisfied = false;
507    boolean threw = true;
508    try {
509      satisfied =
510          guard.isSatisfied()
511              || awaitNanos(
512                  guard,
513                  (startTime == 0L) ? timeoutNanos : remainingNanos(startTime, timeoutNanos),
514                  reentrant);
515      threw = false;
516      return satisfied;
517    } finally {
518      if (!satisfied) {
519        try {
520          // Don't need to signal if timed out, but do if interrupted
521          if (threw && !reentrant) {
522            signalNextWaiter();
523          }
524        } finally {
525          lock.unlock();
526        }
527      }
528    }
529  }
530
531  /** Enters this monitor when the guard is satisfied. Blocks indefinitely. */
532  public void enterWhenUninterruptibly(Guard guard) {
533    if (guard.monitor != this) {
534      throw new IllegalMonitorStateException();
535    }
536    final ReentrantLock lock = this.lock;
537    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
538    lock.lock();
539
540    boolean satisfied = false;
541    try {
542      if (!guard.isSatisfied()) {
543        awaitUninterruptibly(guard, signalBeforeWaiting);
544      }
545      satisfied = true;
546    } finally {
547      if (!satisfied) {
548        leave();
549      }
550    }
551  }
552
553  /**
554   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
555   * the time to acquire the lock and the time to wait for the guard to be satisfied.
556   *
557   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
558   */
559  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
560  public boolean enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit) {
561    final long timeoutNanos = toSafeNanos(time, unit);
562    if (guard.monitor != this) {
563      throw new IllegalMonitorStateException();
564    }
565    final ReentrantLock lock = this.lock;
566    long startTime = 0L;
567    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
568    boolean interrupted = Thread.interrupted();
569    try {
570      if (fair || !lock.tryLock()) {
571        startTime = initNanoTime(timeoutNanos);
572        for (long remainingNanos = timeoutNanos; ; ) {
573          try {
574            if (lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) {
575              break;
576            } else {
577              return false;
578            }
579          } catch (InterruptedException interrupt) {
580            interrupted = true;
581            remainingNanos = remainingNanos(startTime, timeoutNanos);
582          }
583        }
584      }
585
586      boolean satisfied = false;
587      try {
588        while (true) {
589          try {
590            if (guard.isSatisfied()) {
591              satisfied = true;
592            } else {
593              final long remainingNanos;
594              if (startTime == 0L) {
595                startTime = initNanoTime(timeoutNanos);
596                remainingNanos = timeoutNanos;
597              } else {
598                remainingNanos = remainingNanos(startTime, timeoutNanos);
599              }
600              satisfied = awaitNanos(guard, remainingNanos, signalBeforeWaiting);
601            }
602            return satisfied;
603          } catch (InterruptedException interrupt) {
604            interrupted = true;
605            signalBeforeWaiting = false;
606          }
607        }
608      } finally {
609        if (!satisfied) {
610          lock.unlock(); // No need to signal if timed out
611        }
612      }
613    } finally {
614      if (interrupted) {
615        Thread.currentThread().interrupt();
616      }
617    }
618  }
619
620  /**
621   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
622   * not wait for the guard to be satisfied.
623   *
624   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
625   */
626  public boolean enterIf(Guard guard) {
627    if (guard.monitor != this) {
628      throw new IllegalMonitorStateException();
629    }
630    final ReentrantLock lock = this.lock;
631    lock.lock();
632
633    boolean satisfied = false;
634    try {
635      return satisfied = guard.isSatisfied();
636    } finally {
637      if (!satisfied) {
638        lock.unlock();
639      }
640    }
641  }
642
643  /**
644   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
645   * lock, but does not wait for the guard to be satisfied.
646   *
647   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
648   */
649  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
650  public boolean enterIf(Guard guard, long time, TimeUnit unit) {
651    if (guard.monitor != this) {
652      throw new IllegalMonitorStateException();
653    }
654    if (!enter(time, unit)) {
655      return false;
656    }
657
658    boolean satisfied = false;
659    try {
660      return satisfied = guard.isSatisfied();
661    } finally {
662      if (!satisfied) {
663        lock.unlock();
664      }
665    }
666  }
667
668  /**
669   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
670   * not wait for the guard to be satisfied, and may be interrupted.
671   *
672   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
673   * @throws InterruptedException if interrupted while waiting
674   */
675  public boolean enterIfInterruptibly(Guard guard) throws InterruptedException {
676    if (guard.monitor != this) {
677      throw new IllegalMonitorStateException();
678    }
679    final ReentrantLock lock = this.lock;
680    lock.lockInterruptibly();
681
682    boolean satisfied = false;
683    try {
684      return satisfied = guard.isSatisfied();
685    } finally {
686      if (!satisfied) {
687        lock.unlock();
688      }
689    }
690  }
691
692  /**
693   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
694   * lock, but does not wait for the guard to be satisfied, and may be interrupted.
695   *
696   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
697   */
698  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
699  public boolean enterIfInterruptibly(Guard guard, long time, TimeUnit unit)
700      throws InterruptedException {
701    if (guard.monitor != this) {
702      throw new IllegalMonitorStateException();
703    }
704    final ReentrantLock lock = this.lock;
705    if (!lock.tryLock(time, unit)) {
706      return false;
707    }
708
709    boolean satisfied = false;
710    try {
711      return satisfied = guard.isSatisfied();
712    } finally {
713      if (!satisfied) {
714        lock.unlock();
715      }
716    }
717  }
718
719  /**
720   * Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not
721   * block acquiring the lock and does not wait for the guard to be satisfied.
722   *
723   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
724   *
725   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
726   */
727  public boolean tryEnterIf(Guard guard) {
728    if (guard.monitor != this) {
729      throw new IllegalMonitorStateException();
730    }
731    final ReentrantLock lock = this.lock;
732    if (!lock.tryLock()) {
733      return false;
734    }
735
736    boolean satisfied = false;
737    try {
738      return satisfied = guard.isSatisfied();
739    } finally {
740      if (!satisfied) {
741        lock.unlock();
742      }
743    }
744  }
745
746  /**
747   * Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be called
748   * only by a thread currently occupying this monitor.
749   *
750   * @throws InterruptedException if interrupted while waiting
751   */
752  public void waitFor(Guard guard) throws InterruptedException {
753    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
754      throw new IllegalMonitorStateException();
755    }
756    if (!guard.isSatisfied()) {
757      await(guard, true);
758    }
759  }
760
761  /**
762   * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted. May
763   * be called only by a thread currently occupying this monitor.
764   *
765   * @return whether the guard is now satisfied
766   * @throws InterruptedException if interrupted while waiting
767   */
768  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
769  public boolean waitFor(Guard guard, long time, TimeUnit unit) throws InterruptedException {
770    final long timeoutNanos = toSafeNanos(time, unit);
771    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
772      throw new IllegalMonitorStateException();
773    }
774    if (guard.isSatisfied()) {
775      return true;
776    }
777    if (Thread.interrupted()) {
778      throw new InterruptedException();
779    }
780    return awaitNanos(guard, timeoutNanos, true);
781  }
782
783  /**
784   * Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread
785   * currently occupying this monitor.
786   */
787  public void waitForUninterruptibly(Guard guard) {
788    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
789      throw new IllegalMonitorStateException();
790    }
791    if (!guard.isSatisfied()) {
792      awaitUninterruptibly(guard, true);
793    }
794  }
795
796  /**
797   * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a
798   * thread currently occupying this monitor.
799   *
800   * @return whether the guard is now satisfied
801   */
802  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
803  public boolean waitForUninterruptibly(Guard guard, long time, TimeUnit unit) {
804    final long timeoutNanos = toSafeNanos(time, unit);
805    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
806      throw new IllegalMonitorStateException();
807    }
808    if (guard.isSatisfied()) {
809      return true;
810    }
811    boolean signalBeforeWaiting = true;
812    final long startTime = initNanoTime(timeoutNanos);
813    boolean interrupted = Thread.interrupted();
814    try {
815      for (long remainingNanos = timeoutNanos; ; ) {
816        try {
817          return awaitNanos(guard, remainingNanos, signalBeforeWaiting);
818        } catch (InterruptedException interrupt) {
819          interrupted = true;
820          if (guard.isSatisfied()) {
821            return true;
822          }
823          signalBeforeWaiting = false;
824          remainingNanos = remainingNanos(startTime, timeoutNanos);
825        }
826      }
827    } finally {
828      if (interrupted) {
829        Thread.currentThread().interrupt();
830      }
831    }
832  }
833
834  /** Leaves this monitor. May be called only by a thread currently occupying this monitor. */
835  public void leave() {
836    final ReentrantLock lock = this.lock;
837    try {
838      // No need to signal if we will still be holding the lock when we return
839      if (lock.getHoldCount() == 1) {
840        signalNextWaiter();
841      }
842    } finally {
843      lock.unlock(); // Will throw IllegalMonitorStateException if not held
844    }
845  }
846
847  /** Returns whether this monitor is using a fair ordering policy. */
848  public boolean isFair() {
849    return fair;
850  }
851
852  /**
853   * Returns whether this monitor is occupied by any thread. This method is designed for use in
854   * monitoring of the system state, not for synchronization control.
855   */
856  public boolean isOccupied() {
857    return lock.isLocked();
858  }
859
860  /**
861   * Returns whether the current thread is occupying this monitor (has entered more times than it
862   * has left).
863   */
864  public boolean isOccupiedByCurrentThread() {
865    return lock.isHeldByCurrentThread();
866  }
867
868  /**
869   * Returns the number of times the current thread has entered this monitor in excess of the number
870   * of times it has left. Returns 0 if the current thread is not occupying this monitor.
871   */
872  public int getOccupiedDepth() {
873    return lock.getHoldCount();
874  }
875
876  /**
877   * Returns an estimate of the number of threads waiting to enter this monitor. The value is only
878   * an estimate because the number of threads may change dynamically while this method traverses
879   * internal data structures. This method is designed for use in monitoring of the system state,
880   * not for synchronization control.
881   */
882  public int getQueueLength() {
883    return lock.getQueueLength();
884  }
885
886  /**
887   * Returns whether any threads are waiting to enter this monitor. Note that because cancellations
888   * may occur at any time, a {@code true} return does not guarantee that any other thread will ever
889   * enter this monitor. This method is designed primarily for use in monitoring of the system
890   * state.
891   */
892  public boolean hasQueuedThreads() {
893    return lock.hasQueuedThreads();
894  }
895
896  /**
897   * Queries whether the given thread is waiting to enter this monitor. Note that because
898   * cancellations may occur at any time, a {@code true} return does not guarantee that this thread
899   * will ever enter this monitor. This method is designed primarily for use in monitoring of the
900   * system state.
901   */
902  public boolean hasQueuedThread(Thread thread) {
903    return lock.hasQueuedThread(thread);
904  }
905
906  /**
907   * Queries whether any threads are waiting for the given guard to become satisfied. Note that
908   * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee
909   * that the guard becoming satisfied in the future will awaken any threads. This method is
910   * designed primarily for use in monitoring of the system state.
911   */
912  public boolean hasWaiters(Guard guard) {
913    return getWaitQueueLength(guard) > 0;
914  }
915
916  /**
917   * Returns an estimate of the number of threads waiting for the given guard to become satisfied.
918   * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an
919   * upper bound on the actual number of waiters. This method is designed for use in monitoring of
920   * the system state, not for synchronization control.
921   */
922  public int getWaitQueueLength(Guard guard) {
923    if (guard.monitor != this) {
924      throw new IllegalMonitorStateException();
925    }
926    lock.lock();
927    try {
928      return guard.waiterCount;
929    } finally {
930      lock.unlock();
931    }
932  }
933
934  /**
935   * Returns unit.toNanos(time), additionally ensuring the returned value is not at risk of
936   * overflowing or underflowing, by bounding the value between 0 and (Long.MAX_VALUE / 4) * 3.
937   * Actually waiting for more than 219 years is not supported!
938   */
939  private static long toSafeNanos(long time, TimeUnit unit) {
940    long timeoutNanos = unit.toNanos(time);
941    return (timeoutNanos <= 0L)
942        ? 0L
943        : (timeoutNanos > (Long.MAX_VALUE / 4) * 3) ? (Long.MAX_VALUE / 4) * 3 : timeoutNanos;
944  }
945
946  /**
947   * Returns System.nanoTime() unless the timeout has already elapsed. Returns 0L if and only if the
948   * timeout has already elapsed.
949   */
950  private static long initNanoTime(long timeoutNanos) {
951    if (timeoutNanos <= 0L) {
952      return 0L;
953    } else {
954      long startTime = System.nanoTime();
955      return (startTime == 0L) ? 1L : startTime;
956    }
957  }
958
959  /**
960   * Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed.
961   * Caller must have previously sanitized timeoutNanos using toSafeNanos.
962   */
963  private static long remainingNanos(long startTime, long timeoutNanos) {
964    // assert timeoutNanos == 0L || startTime != 0L;
965
966    // TODO : NOT CORRECT, BUT TESTS PASS ANYWAYS!
967    // if (true) return timeoutNanos;
968    // ONLY 2 TESTS FAIL IF WE DO:
969    // if (true) return 0;
970
971    return (timeoutNanos <= 0L) ? 0L : timeoutNanos - (System.nanoTime() - startTime);
972  }
973
974  /**
975   * Signals some other thread waiting on a satisfied guard, if one exists.
976   *
977   * <p>We manage calls to this method carefully, to signal only when necessary, but never losing a
978   * signal, which is the classic problem of this kind of concurrency construct. We must signal if
979   * the current thread is about to relinquish the lock and may have changed the state protected by
980   * the monitor, thereby causing some guard to be satisfied.
981   *
982   * <p>In addition, any thread that has been signalled when its guard was satisfied acquires the
983   * responsibility of signalling the next thread when it again relinquishes the lock. Unlike a
984   * normal Condition, there is no guarantee that an interrupted thread has not been signalled,
985   * since the concurrency control must manage multiple Conditions. So this method must generally be
986   * called when waits are interrupted.
987   *
988   * <p>On the other hand, if a signalled thread wakes up to discover that its guard is still not
989   * satisfied, it does *not* need to call this method before returning to wait. This can only
990   * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the
991   * current thread can and returning the guard to the unsatisfied state. In the latter case the
992   * other thread (last thread modifying the state protected by the monitor) takes over the
993   * responsibility of signalling the next waiter.
994   *
995   * <p>This method must not be called from within a beginWaitingFor/endWaitingFor block, or else
996   * the current thread's guard might be mistakenly signalled, leading to a lost signal.
997   */
998  @GuardedBy("lock")
999  private void signalNextWaiter() {
1000    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1001      if (isSatisfied(guard)) {
1002        guard.condition.signal();
1003        break;
1004      }
1005    }
1006  }
1007
1008  /**
1009   * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered,
1010   * because caller has previously checked that guardToSkip.isSatisfied() returned false. An
1011   * optimization for the case that guardToSkip.isSatisfied() may be expensive.
1012   *
1013   * <p>We decided against using this method, since in practice, isSatisfied() is likely to be very
1014   * cheap (typically one field read). Resurrect this method if you find that not to be true.
1015   */
1016  //   @GuardedBy("lock")
1017  //   private void signalNextWaiterSkipping(Guard guardToSkip) {
1018  //     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1019  //       if (guard != guardToSkip && isSatisfied(guard)) {
1020  //         guard.condition.signal();
1021  //         break;
1022  //       }
1023  //     }
1024  //   }
1025
1026  /**
1027   * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the (hopefully
1028   * unlikely) event that isSatisfied() throws.
1029   */
1030  @GuardedBy("lock")
1031  private boolean isSatisfied(Guard guard) {
1032    try {
1033      return guard.isSatisfied();
1034    } catch (Throwable throwable) {
1035      signalAllWaiters();
1036      throw throwable;
1037    }
1038  }
1039
1040  /** Signals all threads waiting on guards. */
1041  @GuardedBy("lock")
1042  private void signalAllWaiters() {
1043    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1044      guard.condition.signalAll();
1045    }
1046  }
1047
1048  /** Records that the current thread is about to wait on the specified guard. */
1049  @GuardedBy("lock")
1050  private void beginWaitingFor(Guard guard) {
1051    int waiters = guard.waiterCount++;
1052    if (waiters == 0) {
1053      // push guard onto activeGuards
1054      guard.next = activeGuards;
1055      activeGuards = guard;
1056    }
1057  }
1058
1059  /** Records that the current thread is no longer waiting on the specified guard. */
1060  @GuardedBy("lock")
1061  private void endWaitingFor(Guard guard) {
1062    int waiters = --guard.waiterCount;
1063    if (waiters == 0) {
1064      // unlink guard from activeGuards
1065      for (Guard p = activeGuards, pred = null; ; pred = p, p = p.next) {
1066        if (p == guard) {
1067          if (pred == null) {
1068            activeGuards = p.next;
1069          } else {
1070            pred.next = p.next;
1071          }
1072          p.next = null; // help GC
1073          break;
1074        }
1075      }
1076    }
1077  }
1078
1079  /*
1080   * Methods that loop waiting on a guard's condition until the guard is satisfied, while recording
1081   * this fact so that other threads know to check our guard and signal us. It's caller's
1082   * responsibility to ensure that the guard is *not* currently satisfied.
1083   */
1084
1085  @GuardedBy("lock")
1086  private void await(Guard guard, boolean signalBeforeWaiting) throws InterruptedException {
1087    if (signalBeforeWaiting) {
1088      signalNextWaiter();
1089    }
1090    beginWaitingFor(guard);
1091    try {
1092      do {
1093        guard.condition.await();
1094      } while (!guard.isSatisfied());
1095    } finally {
1096      endWaitingFor(guard);
1097    }
1098  }
1099
1100  @GuardedBy("lock")
1101  private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) {
1102    if (signalBeforeWaiting) {
1103      signalNextWaiter();
1104    }
1105    beginWaitingFor(guard);
1106    try {
1107      do {
1108        guard.condition.awaitUninterruptibly();
1109      } while (!guard.isSatisfied());
1110    } finally {
1111      endWaitingFor(guard);
1112    }
1113  }
1114
1115  /** Caller should check before calling that guard is not satisfied. */
1116  @GuardedBy("lock")
1117  private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting)
1118      throws InterruptedException {
1119    boolean firstTime = true;
1120    try {
1121      do {
1122        if (nanos <= 0L) {
1123          return false;
1124        }
1125        if (firstTime) {
1126          if (signalBeforeWaiting) {
1127            signalNextWaiter();
1128          }
1129          beginWaitingFor(guard);
1130          firstTime = false;
1131        }
1132        nanos = guard.condition.awaitNanos(nanos);
1133      } while (!guard.isSatisfied());
1134      return true;
1135    } finally {
1136      if (!firstTime) {
1137        endWaitingFor(guard);
1138      }
1139    }
1140  }
1141}