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