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