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