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