View Javadoc
1   /*
2    * Copyright (C) 2010 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5    * in compliance with the License. You may obtain a copy of the License at
6    *
7    * http://www.apache.org/licenses/LICENSE-2.0
8    *
9    * Unless required by applicable law or agreed to in writing, software distributed under the License
10   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11   * or implied. See the License for the specific language governing permissions and limitations under
12   * the License.
13   */
14  
15  package com.google.common.util.concurrent;
16  
17  import static com.google.common.base.Preconditions.checkNotNull;
18  
19  import com.google.common.annotations.Beta;
20  import com.google.common.annotations.GwtIncompatible;
21  import com.google.common.base.Throwables;
22  import com.google.j2objc.annotations.Weak;
23  import java.util.concurrent.TimeUnit;
24  import java.util.concurrent.locks.Condition;
25  import java.util.concurrent.locks.ReentrantLock;
26  import java.util.function.BooleanSupplier;
27  import javax.annotation.concurrent.GuardedBy;
28  
29  /**
30   * A synchronization abstraction supporting waiting on arbitrary boolean conditions.
31   *
32   * <p>This class is intended as a replacement for {@link ReentrantLock}. Code using {@code Monitor}
33   * is less error-prone and more readable than code using {@code ReentrantLock}, without significant
34   * performance loss. {@code Monitor} even has the potential for performance gain by optimizing the
35   * evaluation and signaling of conditions. Signaling is entirely <a
36   * href="http://en.wikipedia.org/wiki/Monitor_(synchronization)#Implicit_signaling">implicit</a>.
37   * By eliminating explicit signaling, this class can guarantee that only one thread is awakened when
38   * a condition becomes true (no "signaling storms" due to use of {@link
39   * java.util.concurrent.locks.Condition#signalAll Condition.signalAll}) and that no signals are lost
40   * (no "hangs" due to incorrect use of {@link java.util.concurrent.locks.Condition#signal
41   * Condition.signal}).
42   *
43   * <p>A thread is said to <i>occupy</i> a monitor if it has <i>entered</i> the monitor but not yet
44   * <i>left</i>. Only one thread may occupy a given monitor at any moment. A monitor is also
45   * reentrant, so a thread may enter a monitor any number of times, and then must leave the same
46   * number of times. The <i>enter</i> and <i>leave</i> operations have the same synchronization
47   * semantics as the built-in Java language synchronization primitives.
48   *
49   * <p>A call to any of the <i>enter</i> methods with <b>void</b> return type should always be
50   * followed immediately by a <i>try/finally</i> block to ensure that the current thread leaves the
51   * monitor cleanly: <pre>   {@code
52   *
53   *   monitor.enter();
54   *   try {
55   *     // do things while occupying the monitor
56   *   } finally {
57   *     monitor.leave();
58   *   }}</pre>
59   *
60   * <p>A call to any of the <i>enter</i> methods with <b>boolean</b> return type should always appear
61   * as the condition of an <i>if</i> statement containing a <i>try/finally</i> block to ensure that
62   * the current thread leaves the monitor cleanly: <pre>   {@code
63   *
64   *   if (monitor.tryEnter()) {
65   *     try {
66   *       // do things while occupying the monitor
67   *     } finally {
68   *       monitor.leave();
69   *     }
70   *   } else {
71   *     // do other things since the monitor was not available
72   *   }}</pre>
73   *
74   * <h2>Comparison with {@code synchronized} and {@code ReentrantLock}</h2>
75   *
76   * <p>The following examples show a simple threadsafe holder expressed using {@code synchronized},
77   * {@link ReentrantLock}, and {@code Monitor}.
78   *
79   * <h3>{@code synchronized}</h3>
80   *
81   * <p>This version is the fewest lines of code, largely because the synchronization mechanism used
82   * is built into the language and runtime. But the programmer has to remember to avoid a couple of
83   * common bugs: The {@code wait()} must be inside a {@code while} instead of an {@code if}, and
84   * {@code notifyAll()} must be used instead of {@code notify()} because there are two different
85   * logical conditions being awaited. <pre>   {@code
86   *
87   *   public class SafeBox<V> {
88   *     private V value;
89   *
90   *     public synchronized V get() throws InterruptedException {
91   *       while (value == null) {
92   *         wait();
93   *       }
94   *       V result = value;
95   *       value = null;
96   *       notifyAll();
97   *       return result;
98   *     }
99   *
100  *     public synchronized void set(V newValue) throws InterruptedException {
101  *       while (value != null) {
102  *         wait();
103  *       }
104  *       value = newValue;
105  *       notifyAll();
106  *     }
107  *   }}</pre>
108  *
109  * <h3>{@code ReentrantLock}</h3>
110  *
111  * <p>This version is much more verbose than the {@code synchronized} version, and still suffers
112  * from the need for the programmer to remember to use {@code while} instead of {@code if}.
113  * However, one advantage is that we can introduce two separate {@code Condition} objects, which
114  * allows us to use {@code signal()} instead of {@code signalAll()}, which may be a performance
115  * benefit. <pre>   {@code
116  *
117  *   public class SafeBox<V> {
118  *     private final ReentrantLock lock = new ReentrantLock();
119  *     private final Condition valuePresent = lock.newCondition();
120  *     private final Condition valueAbsent = lock.newCondition();
121  *     private V value;
122  *
123  *     public V get() throws InterruptedException {
124  *       lock.lock();
125  *       try {
126  *         while (value == null) {
127  *           valuePresent.await();
128  *         }
129  *         V result = value;
130  *         value = null;
131  *         valueAbsent.signal();
132  *         return result;
133  *       } finally {
134  *         lock.unlock();
135  *       }
136  *     }
137  *
138  *     public void set(V newValue) throws InterruptedException {
139  *       lock.lock();
140  *       try {
141  *         while (value != null) {
142  *           valueAbsent.await();
143  *         }
144  *         value = newValue;
145  *         valuePresent.signal();
146  *       } finally {
147  *         lock.unlock();
148  *       }
149  *     }
150  *   }}</pre>
151  *
152  * <h3>{@code Monitor}</h3>
153  *
154  * <p>This version adds some verbosity around the {@code Guard} objects, but removes that same
155  * verbosity, and more, from the {@code get} and {@code set} methods. {@code Monitor} implements the
156  * same efficient signaling as we had to hand-code in the {@code ReentrantLock} version above.
157  * Finally, the programmer no longer has to hand-code the wait loop, and therefore doesn't have to
158  * remember to use {@code while} instead of {@code if}. <pre>   {@code
159  *
160  *   public class SafeBox<V> {
161  *     private final Monitor monitor = new Monitor();
162  *     private final Monitor.Guard valuePresent = new Monitor.Guard(monitor) {
163  *       public boolean isSatisfied() {
164  *         return value != null;
165  *       }
166  *     };
167  *     private final Monitor.Guard valueAbsent = new Monitor.Guard(monitor) {
168  *       public boolean isSatisfied() {
169  *         return value == null;
170  *       }
171  *     };
172  *     private V value;
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  *   }}</pre>
194  *
195  * @author Justin T. Sampson
196  * @author Martin Buchholz
197  * @since 10.0
198  */
199 @Beta
200 @GwtIncompatible
201 @SuppressWarnings("GuardedBy") // TODO(b/35466881): Fix or suppress.
202 public 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   @Beta
303   public abstract static class Guard {
304 
305     @Weak final Monitor monitor;
306     final Condition condition;
307 
308     @GuardedBy("monitor.lock")
309     int waiterCount = 0;
310 
311     /** The next active guard */
312     @GuardedBy("monitor.lock")
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   /**
329    * Whether this monitor is fair.
330    */
331   private final boolean fair;
332 
333   /**
334    * The lock underlying this monitor.
335    */
336   private final ReentrantLock lock;
337 
338   /**
339    * The guards associated with this monitor that currently have waiters ({@code waiterCount > 0}).
340    * A linked list threaded through the Guard.next field.
341    */
342   @GuardedBy("lock")
343   private Guard activeGuards = null;
344 
345   /**
346    * Creates a monitor with a non-fair (but fast) ordering policy. Equivalent to {@code
347    * Monitor(false)}.
348    */
349   public Monitor() {
350     this(false);
351   }
352 
353   /**
354    * Creates a monitor with the given ordering policy.
355    *
356    * @param fair whether this monitor should use a fair ordering policy rather than a non-fair (but
357    *     fast) one
358    */
359   public Monitor(boolean fair) {
360     this.fair = fair;
361     this.lock = new ReentrantLock(fair);
362   }
363 
364   /**
365    * Creates a new {@link Guard} for {@code this} monitor.
366    *
367    * @Param isSatisfied The guards boolean condition.  See {@link Guard#isSatisfied}.
368    */
369   public Guard newGuard(final BooleanSupplier isSatisfied) {
370     checkNotNull(isSatisfied, "isSatisfied");
371     return new Guard(this) {
372       @Override
373       public boolean isSatisfied() {
374         return isSatisfied.getAsBoolean();
375       }
376     };
377   }
378 
379   /**
380    * Enters this monitor. Blocks indefinitely.
381    */
382   public void enter() {
383     lock.lock();
384   }
385 
386   /**
387    * Enters this monitor. Blocks indefinitely, but may be interrupted.
388    *
389    * @throws InterruptedException if interrupted while waiting
390    */
391   public void enterInterruptibly() throws InterruptedException {
392     lock.lockInterruptibly();
393   }
394 
395   /**
396    * Enters this monitor. Blocks at most the given time.
397    *
398    * @return whether the monitor was entered
399    */
400   public boolean enter(long time, TimeUnit unit) {
401     final long timeoutNanos = toSafeNanos(time, unit);
402     final ReentrantLock lock = this.lock;
403     if (!fair && lock.tryLock()) {
404       return true;
405     }
406     boolean interrupted = Thread.interrupted();
407     try {
408       final long startTime = System.nanoTime();
409       for (long remainingNanos = timeoutNanos; ; ) {
410         try {
411           return lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS);
412         } catch (InterruptedException interrupt) {
413           interrupted = true;
414           remainingNanos = remainingNanos(startTime, timeoutNanos);
415         }
416       }
417     } finally {
418       if (interrupted) {
419         Thread.currentThread().interrupt();
420       }
421     }
422   }
423 
424   /**
425    * Enters this monitor. Blocks at most the given time, and may be interrupted.
426    *
427    * @return whether the monitor was entered
428    * @throws InterruptedException if interrupted while waiting
429    */
430   public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException {
431     return lock.tryLock(time, unit);
432   }
433 
434   /**
435    * Enters this monitor if it is possible to do so immediately. Does not block.
436    *
437    * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
438    *
439    * @return whether the monitor was entered
440    */
441   public boolean tryEnter() {
442     return lock.tryLock();
443   }
444 
445   /**
446    * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted.
447    *
448    * @throws InterruptedException if interrupted while waiting
449    */
450   public void enterWhen(Guard guard) throws InterruptedException {
451     if (guard.monitor != this) {
452       throw new IllegalMonitorStateException();
453     }
454     final ReentrantLock lock = this.lock;
455     boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
456     lock.lockInterruptibly();
457 
458     boolean satisfied = false;
459     try {
460       if (!guard.isSatisfied()) {
461         await(guard, signalBeforeWaiting);
462       }
463       satisfied = true;
464     } finally {
465       if (!satisfied) {
466         leave();
467       }
468     }
469   }
470 
471   /**
472    * Enters this monitor when the guard is satisfied. Blocks indefinitely.
473    */
474   public void enterWhenUninterruptibly(Guard guard) {
475     if (guard.monitor != this) {
476       throw new IllegalMonitorStateException();
477     }
478     final ReentrantLock lock = this.lock;
479     boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
480     lock.lock();
481 
482     boolean satisfied = false;
483     try {
484       if (!guard.isSatisfied()) {
485         awaitUninterruptibly(guard, signalBeforeWaiting);
486       }
487       satisfied = true;
488     } finally {
489       if (!satisfied) {
490         leave();
491       }
492     }
493   }
494 
495   /**
496    * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
497    * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be
498    * interrupted.
499    *
500    * @return whether the monitor was entered, which guarantees that the guard is now satisfied
501    * @throws InterruptedException if interrupted while waiting
502    */
503   public boolean enterWhen(Guard guard, long time, TimeUnit unit) throws InterruptedException {
504     final long timeoutNanos = toSafeNanos(time, unit);
505     if (guard.monitor != this) {
506       throw new IllegalMonitorStateException();
507     }
508     final ReentrantLock lock = this.lock;
509     boolean reentrant = lock.isHeldByCurrentThread();
510     long startTime = 0L;
511 
512     locked:
513     {
514       if (!fair) {
515         // Check interrupt status to get behavior consistent with fair case.
516         if (Thread.interrupted()) {
517           throw new InterruptedException();
518         }
519         if (lock.tryLock()) {
520           break locked;
521         }
522       }
523       startTime = initNanoTime(timeoutNanos);
524       if (!lock.tryLock(time, unit)) {
525         return false;
526       }
527     }
528 
529     boolean satisfied = false;
530     boolean threw = true;
531     try {
532       satisfied =
533           guard.isSatisfied()
534               || awaitNanos(
535                   guard,
536                   (startTime == 0L) ? timeoutNanos : remainingNanos(startTime, timeoutNanos),
537                   reentrant);
538       threw = false;
539       return satisfied;
540     } finally {
541       if (!satisfied) {
542         try {
543           // Don't need to signal if timed out, but do if interrupted
544           if (threw && !reentrant) {
545             signalNextWaiter();
546           }
547         } finally {
548           lock.unlock();
549         }
550       }
551     }
552   }
553 
554   /**
555    * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
556    * the time to acquire the lock and the time to wait for the guard to be satisfied.
557    *
558    * @return whether the monitor was entered, which guarantees that the guard is now satisfied
559    */
560   public boolean enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit) {
561     final long timeoutNanos = toSafeNanos(time, unit);
562     if (guard.monitor != this) {
563       throw new IllegalMonitorStateException();
564     }
565     final ReentrantLock lock = this.lock;
566     long startTime = 0L;
567     boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
568     boolean interrupted = Thread.interrupted();
569     try {
570       if (fair || !lock.tryLock()) {
571         startTime = initNanoTime(timeoutNanos);
572         for (long remainingNanos = timeoutNanos; ; ) {
573           try {
574             if (lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) {
575               break;
576             } else {
577               return false;
578             }
579           } catch (InterruptedException interrupt) {
580             interrupted = true;
581             remainingNanos = remainingNanos(startTime, timeoutNanos);
582           }
583         }
584       }
585 
586       boolean satisfied = false;
587       try {
588         while (true) {
589           try {
590             if (guard.isSatisfied()) {
591               satisfied = true;
592             } else {
593               final long remainingNanos;
594               if (startTime == 0L) {
595                 startTime = initNanoTime(timeoutNanos);
596                 remainingNanos = timeoutNanos;
597               } else {
598                 remainingNanos = remainingNanos(startTime, timeoutNanos);
599               }
600               satisfied = awaitNanos(guard, remainingNanos, signalBeforeWaiting);
601             }
602             return satisfied;
603           } catch (InterruptedException interrupt) {
604             interrupted = true;
605             signalBeforeWaiting = false;
606           }
607         }
608       } finally {
609         if (!satisfied) {
610           lock.unlock(); // No need to signal if timed out
611         }
612       }
613     } finally {
614       if (interrupted) {
615         Thread.currentThread().interrupt();
616       }
617     }
618   }
619 
620   /**
621    * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
622    * not wait for the guard to be satisfied.
623    *
624    * @return whether the monitor was entered, which guarantees that the guard is now satisfied
625    */
626   public boolean enterIf(Guard guard) {
627     if (guard.monitor != this) {
628       throw new IllegalMonitorStateException();
629     }
630     final ReentrantLock lock = this.lock;
631     lock.lock();
632 
633     boolean satisfied = false;
634     try {
635       return satisfied = guard.isSatisfied();
636     } finally {
637       if (!satisfied) {
638         lock.unlock();
639       }
640     }
641   }
642 
643   /**
644    * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
645    * not wait for the guard to be satisfied, and may be interrupted.
646    *
647    * @return whether the monitor was entered, which guarantees that the guard is now satisfied
648    * @throws InterruptedException if interrupted while waiting
649    */
650   public boolean enterIfInterruptibly(Guard guard) throws InterruptedException {
651     if (guard.monitor != this) {
652       throw new IllegalMonitorStateException();
653     }
654     final ReentrantLock lock = this.lock;
655     lock.lockInterruptibly();
656 
657     boolean satisfied = false;
658     try {
659       return satisfied = guard.isSatisfied();
660     } finally {
661       if (!satisfied) {
662         lock.unlock();
663       }
664     }
665   }
666 
667   /**
668    * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
669    * lock, but does not wait for the guard to be satisfied.
670    *
671    * @return whether the monitor was entered, which guarantees that the guard is now satisfied
672    */
673   public boolean enterIf(Guard guard, long time, TimeUnit unit) {
674     if (guard.monitor != this) {
675       throw new IllegalMonitorStateException();
676     }
677     if (!enter(time, unit)) {
678       return false;
679     }
680 
681     boolean satisfied = false;
682     try {
683       return satisfied = guard.isSatisfied();
684     } finally {
685       if (!satisfied) {
686         lock.unlock();
687       }
688     }
689   }
690 
691   /**
692    * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
693    * lock, but does not wait for the guard to be satisfied, and may be interrupted.
694    *
695    * @return whether the monitor was entered, which guarantees that the guard is now satisfied
696    */
697   public boolean enterIfInterruptibly(Guard guard, long time, TimeUnit unit)
698       throws InterruptedException {
699     if (guard.monitor != this) {
700       throw new IllegalMonitorStateException();
701     }
702     final ReentrantLock lock = this.lock;
703     if (!lock.tryLock(time, unit)) {
704       return false;
705     }
706 
707     boolean satisfied = false;
708     try {
709       return satisfied = guard.isSatisfied();
710     } finally {
711       if (!satisfied) {
712         lock.unlock();
713       }
714     }
715   }
716 
717   /**
718    * Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not
719    * block acquiring the lock and does not wait for the guard to be satisfied.
720    *
721    * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
722    *
723    * @return whether the monitor was entered, which guarantees that the guard is now satisfied
724    */
725   public boolean tryEnterIf(Guard guard) {
726     if (guard.monitor != this) {
727       throw new IllegalMonitorStateException();
728     }
729     final ReentrantLock lock = this.lock;
730     if (!lock.tryLock()) {
731       return false;
732     }
733 
734     boolean satisfied = false;
735     try {
736       return satisfied = guard.isSatisfied();
737     } finally {
738       if (!satisfied) {
739         lock.unlock();
740       }
741     }
742   }
743 
744   /**
745    * Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be called
746    * only by a thread currently occupying this monitor.
747    *
748    * @throws InterruptedException if interrupted while waiting
749    */
750   public void waitFor(Guard guard) throws InterruptedException {
751     if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
752       throw new IllegalMonitorStateException();
753     }
754     if (!guard.isSatisfied()) {
755       await(guard, true);
756     }
757   }
758 
759   /**
760    * Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread
761    * currently occupying this monitor.
762    */
763   public void waitForUninterruptibly(Guard guard) {
764     if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
765       throw new IllegalMonitorStateException();
766     }
767     if (!guard.isSatisfied()) {
768       awaitUninterruptibly(guard, true);
769     }
770   }
771 
772   /**
773    * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted. May
774    * be called only by a thread currently occupying this monitor.
775    *
776    * @return whether the guard is now satisfied
777    * @throws InterruptedException if interrupted while waiting
778    */
779   public boolean waitFor(Guard guard, long time, TimeUnit unit) throws InterruptedException {
780     final long timeoutNanos = toSafeNanos(time, unit);
781     if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
782       throw new IllegalMonitorStateException();
783     }
784     if (guard.isSatisfied()) {
785       return true;
786     }
787     if (Thread.interrupted()) {
788       throw new InterruptedException();
789     }
790     return awaitNanos(guard, timeoutNanos, true);
791   }
792 
793   /**
794    * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a
795    * thread currently occupying this monitor.
796    *
797    * @return whether the guard is now satisfied
798    */
799   public boolean waitForUninterruptibly(Guard guard, long time, TimeUnit unit) {
800     final long timeoutNanos = toSafeNanos(time, unit);
801     if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
802       throw new IllegalMonitorStateException();
803     }
804     if (guard.isSatisfied()) {
805       return true;
806     }
807     boolean signalBeforeWaiting = true;
808     final long startTime = initNanoTime(timeoutNanos);
809     boolean interrupted = Thread.interrupted();
810     try {
811       for (long remainingNanos = timeoutNanos; ; ) {
812         try {
813           return awaitNanos(guard, remainingNanos, signalBeforeWaiting);
814         } catch (InterruptedException interrupt) {
815           interrupted = true;
816           if (guard.isSatisfied()) {
817             return true;
818           }
819           signalBeforeWaiting = false;
820           remainingNanos = remainingNanos(startTime, timeoutNanos);
821         }
822       }
823     } finally {
824       if (interrupted) {
825         Thread.currentThread().interrupt();
826       }
827     }
828   }
829 
830   /**
831    * Leaves this monitor. May be called only by a thread currently occupying this monitor.
832    */
833   public void leave() {
834     final ReentrantLock lock = this.lock;
835     try {
836       // No need to signal if we will still be holding the lock when we return
837       if (lock.getHoldCount() == 1) {
838         signalNextWaiter();
839       }
840     } finally {
841       lock.unlock(); // Will throw IllegalMonitorStateException if not held
842     }
843   }
844 
845   /**
846    * Returns whether this monitor is using a fair ordering policy.
847    */
848   public boolean isFair() {
849     return fair;
850   }
851 
852   /**
853    * Returns whether this monitor is occupied by any thread. This method is designed for use in
854    * monitoring of the system state, not for synchronization control.
855    */
856   public boolean isOccupied() {
857     return lock.isLocked();
858   }
859 
860   /**
861    * Returns whether the current thread is occupying this monitor (has entered more times than it
862    * has left).
863    */
864   public boolean isOccupiedByCurrentThread() {
865     return lock.isHeldByCurrentThread();
866   }
867 
868   /**
869    * Returns the number of times the current thread has entered this monitor in excess of the number
870    * of times it has left. Returns 0 if the current thread is not occupying this monitor.
871    */
872   public int getOccupiedDepth() {
873     return lock.getHoldCount();
874   }
875 
876   /**
877    * Returns an estimate of the number of threads waiting to enter this monitor. The value is only
878    * an estimate because the number of threads may change dynamically while this method traverses
879    * internal data structures. This method is designed for use in monitoring of the system state,
880    * not for synchronization control.
881    */
882   public int getQueueLength() {
883     return lock.getQueueLength();
884   }
885 
886   /**
887    * Returns whether any threads are waiting to enter this monitor. Note that because cancellations
888    * may occur at any time, a {@code true} return does not guarantee that any other thread will ever
889    * enter this monitor. This method is designed primarily for use in monitoring of the system
890    * state.
891    */
892   public boolean hasQueuedThreads() {
893     return lock.hasQueuedThreads();
894   }
895 
896   /**
897    * Queries whether the given thread is waiting to enter this monitor. Note that because
898    * cancellations may occur at any time, a {@code true} return does not guarantee that this thread
899    * will ever enter this monitor. This method is designed primarily for use in monitoring of the
900    * system state.
901    */
902   public boolean hasQueuedThread(Thread thread) {
903     return lock.hasQueuedThread(thread);
904   }
905 
906   /**
907    * Queries whether any threads are waiting for the given guard to become satisfied. Note that
908    * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee
909    * that the guard becoming satisfied in the future will awaken any threads. This method is
910    * designed primarily for use in monitoring of the system state.
911    */
912   public boolean hasWaiters(Guard guard) {
913     return getWaitQueueLength(guard) > 0;
914   }
915 
916   /**
917    * Returns an estimate of the number of threads waiting for the given guard to become satisfied.
918    * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an
919    * upper bound on the actual number of waiters. This method is designed for use in monitoring of
920    * the system state, not for synchronization control.
921    */
922   public int getWaitQueueLength(Guard guard) {
923     if (guard.monitor != this) {
924       throw new IllegalMonitorStateException();
925     }
926     lock.lock();
927     try {
928       return guard.waiterCount;
929     } finally {
930       lock.unlock();
931     }
932   }
933 
934   /**
935    * Returns unit.toNanos(time), additionally ensuring the returned value is not at risk of
936    * overflowing or underflowing, by bounding the value between 0 and (Long.MAX_VALUE / 4) * 3.
937    * Actually waiting for more than 219 years is not supported!
938    */
939   private static long toSafeNanos(long time, TimeUnit unit) {
940     long timeoutNanos = unit.toNanos(time);
941     return (timeoutNanos <= 0L)
942         ? 0L
943         : (timeoutNanos > (Long.MAX_VALUE / 4) * 3) ? (Long.MAX_VALUE / 4) * 3 : timeoutNanos;
944   }
945 
946   /**
947    * Returns System.nanoTime() unless the timeout has already elapsed. Returns 0L if and only if the
948    * timeout has already elapsed.
949    */
950   private static long initNanoTime(long timeoutNanos) {
951     if (timeoutNanos <= 0L) {
952       return 0L;
953     } else {
954       long startTime = System.nanoTime();
955       return (startTime == 0L) ? 1L : startTime;
956     }
957   }
958 
959   /**
960    * Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed.
961    * Caller must have previously sanitized timeoutNanos using toSafeNanos.
962    */
963   private static long remainingNanos(long startTime, long timeoutNanos) {
964     // assert timeoutNanos == 0L || startTime != 0L;
965 
966     // TODO : NOT CORRECT, BUT TESTS PASS ANYWAYS!
967     // if (true) return timeoutNanos;
968     // ONLY 2 TESTS FAIL IF WE DO:
969     // if (true) return 0;
970 
971     return (timeoutNanos <= 0L) ? 0L : timeoutNanos - (System.nanoTime() - startTime);
972   }
973 
974   /**
975    * Signals some other thread waiting on a satisfied guard, if one exists.
976    *
977    * We manage calls to this method carefully, to signal only when necessary, but never losing a
978    * signal, which is the classic problem of this kind of concurrency construct. We must signal if
979    * the current thread is about to relinquish the lock and may have changed the state protected by
980    * the monitor, thereby causing some guard to be satisfied.
981    *
982    * In addition, any thread that has been signalled when its guard was satisfied acquires the
983    * responsibility of signalling the next thread when it again relinquishes the lock. Unlike a
984    * normal Condition, there is no guarantee that an interrupted thread has not been signalled,
985    * since the concurrency control must manage multiple Conditions. So this method must generally be
986    * called when waits are interrupted.
987    *
988    * On the other hand, if a signalled thread wakes up to discover that its guard is still not
989    * satisfied, it does *not* need to call this method before returning to wait. This can only
990    * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the
991    * current thread can and returning the guard to the unsatisfied state. In the latter case the
992    * other thread (last thread modifying the state protected by the monitor) takes over the
993    * responsibility of signalling the next waiter.
994    *
995    * This method must not be called from within a beginWaitingFor/endWaitingFor block, or else the
996    * current thread's guard might be mistakenly signalled, leading to a lost signal.
997    */
998   @GuardedBy("lock")
999   private void signalNextWaiter() {
1000     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1001       if (isSatisfied(guard)) {
1002         guard.condition.signal();
1003         break;
1004       }
1005     }
1006   }
1007 
1008   /**
1009    * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered,
1010    * because caller has previously checked that guardToSkip.isSatisfied() returned false. An
1011    * optimization for the case that guardToSkip.isSatisfied() may be expensive.
1012    *
1013    * We decided against using this method, since in practice, isSatisfied() is likely to be very
1014    * cheap (typically one field read). Resurrect this method if you find that not to be true.
1015    */
1016 //   @GuardedBy("lock")
1017 //   private void signalNextWaiterSkipping(Guard guardToSkip) {
1018 //     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1019 //       if (guard != guardToSkip && isSatisfied(guard)) {
1020 //         guard.condition.signal();
1021 //         break;
1022 //       }
1023 //     }
1024 //   }
1025 
1026   /**
1027    * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the (hopefully
1028    * unlikely) event that isSatisfied() throws.
1029    */
1030   @GuardedBy("lock")
1031   private boolean isSatisfied(Guard guard) {
1032     try {
1033       return guard.isSatisfied();
1034     } catch (Throwable throwable) {
1035       signalAllWaiters();
1036       throw Throwables.propagate(throwable);
1037     }
1038   }
1039 
1040   /**
1041    * Signals all threads waiting on guards.
1042    */
1043   @GuardedBy("lock")
1044   private void signalAllWaiters() {
1045     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1046       guard.condition.signalAll();
1047     }
1048   }
1049 
1050   /**
1051    * Records that the current thread is about to wait on the specified guard.
1052    */
1053   @GuardedBy("lock")
1054   private void beginWaitingFor(Guard guard) {
1055     int waiters = guard.waiterCount++;
1056     if (waiters == 0) {
1057       // push guard onto activeGuards
1058       guard.next = activeGuards;
1059       activeGuards = guard;
1060     }
1061   }
1062 
1063   /**
1064    * Records that the current thread is no longer waiting on the specified guard.
1065    */
1066   @GuardedBy("lock")
1067   private void endWaitingFor(Guard guard) {
1068     int waiters = --guard.waiterCount;
1069     if (waiters == 0) {
1070       // unlink guard from activeGuards
1071       for (Guard p = activeGuards, pred = null; ; pred = p, p = p.next) {
1072         if (p == guard) {
1073           if (pred == null) {
1074             activeGuards = p.next;
1075           } else {
1076             pred.next = p.next;
1077           }
1078           p.next = null; // help GC
1079           break;
1080         }
1081       }
1082     }
1083   }
1084 
1085   /*
1086    * Methods that loop waiting on a guard's condition until the guard is satisfied, while recording
1087    * this fact so that other threads know to check our guard and signal us. It's caller's
1088    * responsibility to ensure that the guard is *not* currently satisfied.
1089    */
1090 
1091   @GuardedBy("lock")
1092   private void await(Guard guard, boolean signalBeforeWaiting) throws InterruptedException {
1093     if (signalBeforeWaiting) {
1094       signalNextWaiter();
1095     }
1096     beginWaitingFor(guard);
1097     try {
1098       do {
1099         guard.condition.await();
1100       } while (!guard.isSatisfied());
1101     } finally {
1102       endWaitingFor(guard);
1103     }
1104   }
1105 
1106   @GuardedBy("lock")
1107   private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) {
1108     if (signalBeforeWaiting) {
1109       signalNextWaiter();
1110     }
1111     beginWaitingFor(guard);
1112     try {
1113       do {
1114         guard.condition.awaitUninterruptibly();
1115       } while (!guard.isSatisfied());
1116     } finally {
1117       endWaitingFor(guard);
1118     }
1119   }
1120 
1121   /**
1122    * Caller should check before calling that guard is not satisfied.
1123    */
1124   @GuardedBy("lock")
1125   private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting)
1126       throws InterruptedException {
1127     boolean firstTime = true;
1128     try {
1129       do {
1130         if (nanos <= 0L) {
1131           return false;
1132         }
1133         if (firstTime) {
1134           if (signalBeforeWaiting) {
1135             signalNextWaiter();
1136           }
1137           beginWaitingFor(guard);
1138           firstTime = false;
1139         }
1140         nanos = guard.condition.awaitNanos(nanos);
1141       } while (!guard.isSatisfied());
1142       return true;
1143     } finally {
1144       if (!firstTime) {
1145         endWaitingFor(guard);
1146       }
1147     }
1148   }
1149 }