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