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.Beta;
021import com.google.common.annotations.GwtIncompatible;
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 org.checkerframework.checker.nullness.qual.Nullable;
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@Beta
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  @Beta
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    @Nullable
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  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 21.0
371   */
372  public Guard newGuard(final BooleanSupplier isSatisfied) {
373    checkNotNull(isSatisfied, "isSatisfied");
374    return new Guard(this) {
375      @Override
376      public boolean isSatisfied() {
377        return isSatisfied.getAsBoolean();
378      }
379    };
380  }
381
382  /** Enters this monitor. Blocks indefinitely. */
383  public void enter() {
384    lock.lock();
385  }
386
387  /**
388   * Enters this monitor. Blocks at most the given time.
389   *
390   * @return whether the monitor was entered
391   * @since 28.0
392   */
393  public boolean enter(Duration time) {
394    return enter(toNanosSaturated(time), TimeUnit.NANOSECONDS);
395  }
396
397  /**
398   * Enters this monitor. Blocks at most the given time.
399   *
400   * @return whether the monitor was entered
401   */
402  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
403  public boolean enter(long time, TimeUnit unit) {
404    final long timeoutNanos = toSafeNanos(time, unit);
405    final ReentrantLock lock = this.lock;
406    if (!fair && lock.tryLock()) {
407      return true;
408    }
409    boolean interrupted = Thread.interrupted();
410    try {
411      final long startTime = System.nanoTime();
412      for (long remainingNanos = timeoutNanos; ; ) {
413        try {
414          return lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS);
415        } catch (InterruptedException interrupt) {
416          interrupted = true;
417          remainingNanos = remainingNanos(startTime, timeoutNanos);
418        }
419      }
420    } finally {
421      if (interrupted) {
422        Thread.currentThread().interrupt();
423      }
424    }
425  }
426
427  /**
428   * Enters this monitor. Blocks indefinitely, but may be interrupted.
429   *
430   * @throws InterruptedException if interrupted while waiting
431   */
432  public void enterInterruptibly() throws InterruptedException {
433    lock.lockInterruptibly();
434  }
435
436  /**
437   * Enters this monitor. Blocks at most the given time, and may be interrupted.
438   *
439   * @return whether the monitor was entered
440   * @throws InterruptedException if interrupted while waiting
441   * @since 28.0
442   */
443  public boolean enterInterruptibly(Duration time) throws InterruptedException {
444    return enterInterruptibly(toNanosSaturated(time), TimeUnit.NANOSECONDS);
445  }
446
447  /**
448   * Enters this monitor. Blocks at most the given time, and may be interrupted.
449   *
450   * @return whether the monitor was entered
451   * @throws InterruptedException if interrupted while waiting
452   */
453  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
454  public boolean enterInterruptibly(long time, TimeUnit unit) throws InterruptedException {
455    return lock.tryLock(time, unit);
456  }
457
458  /**
459   * Enters this monitor if it is possible to do so immediately. Does not block.
460   *
461   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
462   *
463   * @return whether the monitor was entered
464   */
465  public boolean tryEnter() {
466    return lock.tryLock();
467  }
468
469  /**
470   * Enters this monitor when the guard is satisfied. Blocks indefinitely, but may be interrupted.
471   *
472   * @throws InterruptedException if interrupted while waiting
473   */
474  public void enterWhen(Guard guard) throws InterruptedException {
475    if (guard.monitor != this) {
476      throw new IllegalMonitorStateException();
477    }
478    final ReentrantLock lock = this.lock;
479    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
480    lock.lockInterruptibly();
481
482    boolean satisfied = false;
483    try {
484      if (!guard.isSatisfied()) {
485        await(guard, signalBeforeWaiting);
486      }
487      satisfied = true;
488    } finally {
489      if (!satisfied) {
490        leave();
491      }
492    }
493  }
494
495  /**
496   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
497   * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be
498   * interrupted.
499   *
500   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
501   * @throws InterruptedException if interrupted while waiting
502   * @since 28.0
503   */
504  public boolean enterWhen(Guard guard, Duration time) throws InterruptedException {
505    return enterWhen(guard, toNanosSaturated(time), TimeUnit.NANOSECONDS);
506  }
507
508  /**
509   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
510   * the time to acquire the lock and the time to wait for the guard to be satisfied, and may be
511   * interrupted.
512   *
513   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
514   * @throws InterruptedException if interrupted while waiting
515   */
516  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
517  public boolean enterWhen(Guard guard, long time, TimeUnit unit) throws InterruptedException {
518    final long timeoutNanos = toSafeNanos(time, unit);
519    if (guard.monitor != this) {
520      throw new IllegalMonitorStateException();
521    }
522    final ReentrantLock lock = this.lock;
523    boolean reentrant = lock.isHeldByCurrentThread();
524    long startTime = 0L;
525
526    locked:
527    {
528      if (!fair) {
529        // Check interrupt status to get behavior consistent with fair case.
530        if (Thread.interrupted()) {
531          throw new InterruptedException();
532        }
533        if (lock.tryLock()) {
534          break locked;
535        }
536      }
537      startTime = initNanoTime(timeoutNanos);
538      if (!lock.tryLock(time, unit)) {
539        return false;
540      }
541    }
542
543    boolean satisfied = false;
544    boolean threw = true;
545    try {
546      satisfied =
547          guard.isSatisfied()
548              || awaitNanos(
549                  guard,
550                  (startTime == 0L) ? timeoutNanos : remainingNanos(startTime, timeoutNanos),
551                  reentrant);
552      threw = false;
553      return satisfied;
554    } finally {
555      if (!satisfied) {
556        try {
557          // Don't need to signal if timed out, but do if interrupted
558          if (threw && !reentrant) {
559            signalNextWaiter();
560          }
561        } finally {
562          lock.unlock();
563        }
564      }
565    }
566  }
567
568  /** Enters this monitor when the guard is satisfied. Blocks indefinitely. */
569  public void enterWhenUninterruptibly(Guard guard) {
570    if (guard.monitor != this) {
571      throw new IllegalMonitorStateException();
572    }
573    final ReentrantLock lock = this.lock;
574    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
575    lock.lock();
576
577    boolean satisfied = false;
578    try {
579      if (!guard.isSatisfied()) {
580        awaitUninterruptibly(guard, signalBeforeWaiting);
581      }
582      satisfied = true;
583    } finally {
584      if (!satisfied) {
585        leave();
586      }
587    }
588  }
589
590  /**
591   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
592   * the time to acquire the lock and the time to wait for the guard to be satisfied.
593   *
594   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
595   * @since 28.0
596   */
597  public boolean enterWhenUninterruptibly(Guard guard, Duration time) {
598    return enterWhenUninterruptibly(guard, toNanosSaturated(time), TimeUnit.NANOSECONDS);
599  }
600
601  /**
602   * Enters this monitor when the guard is satisfied. Blocks at most the given time, including both
603   * the time to acquire the lock and the time to wait for the guard to be satisfied.
604   *
605   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
606   */
607  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
608  public boolean enterWhenUninterruptibly(Guard guard, long time, TimeUnit unit) {
609    final long timeoutNanos = toSafeNanos(time, unit);
610    if (guard.monitor != this) {
611      throw new IllegalMonitorStateException();
612    }
613    final ReentrantLock lock = this.lock;
614    long startTime = 0L;
615    boolean signalBeforeWaiting = lock.isHeldByCurrentThread();
616    boolean interrupted = Thread.interrupted();
617    try {
618      if (fair || !lock.tryLock()) {
619        startTime = initNanoTime(timeoutNanos);
620        for (long remainingNanos = timeoutNanos; ; ) {
621          try {
622            if (lock.tryLock(remainingNanos, TimeUnit.NANOSECONDS)) {
623              break;
624            } else {
625              return false;
626            }
627          } catch (InterruptedException interrupt) {
628            interrupted = true;
629            remainingNanos = remainingNanos(startTime, timeoutNanos);
630          }
631        }
632      }
633
634      boolean satisfied = false;
635      try {
636        while (true) {
637          try {
638            if (guard.isSatisfied()) {
639              satisfied = true;
640            } else {
641              final long remainingNanos;
642              if (startTime == 0L) {
643                startTime = initNanoTime(timeoutNanos);
644                remainingNanos = timeoutNanos;
645              } else {
646                remainingNanos = remainingNanos(startTime, timeoutNanos);
647              }
648              satisfied = awaitNanos(guard, remainingNanos, signalBeforeWaiting);
649            }
650            return satisfied;
651          } catch (InterruptedException interrupt) {
652            interrupted = true;
653            signalBeforeWaiting = false;
654          }
655        }
656      } finally {
657        if (!satisfied) {
658          lock.unlock(); // No need to signal if timed out
659        }
660      }
661    } finally {
662      if (interrupted) {
663        Thread.currentThread().interrupt();
664      }
665    }
666  }
667
668  /**
669   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
670   * not wait for the guard to be satisfied.
671   *
672   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
673   */
674  public boolean enterIf(Guard guard) {
675    if (guard.monitor != this) {
676      throw new IllegalMonitorStateException();
677    }
678    final ReentrantLock lock = this.lock;
679    lock.lock();
680
681    boolean satisfied = false;
682    try {
683      return satisfied = guard.isSatisfied();
684    } finally {
685      if (!satisfied) {
686        lock.unlock();
687      }
688    }
689  }
690
691  /**
692   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
693   * lock, but does not wait for the guard to be satisfied.
694   *
695   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
696   * @since 28.0
697   */
698  public boolean enterIf(Guard guard, Duration time) {
699    return enterIf(guard, toNanosSaturated(time), TimeUnit.NANOSECONDS);
700  }
701
702  /**
703   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
704   * lock, but does not wait for the guard to be satisfied.
705   *
706   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
707   */
708  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
709  public boolean enterIf(Guard guard, long time, TimeUnit unit) {
710    if (guard.monitor != this) {
711      throw new IllegalMonitorStateException();
712    }
713    if (!enter(time, unit)) {
714      return false;
715    }
716
717    boolean satisfied = false;
718    try {
719      return satisfied = guard.isSatisfied();
720    } finally {
721      if (!satisfied) {
722        lock.unlock();
723      }
724    }
725  }
726
727  /**
728   * Enters this monitor if the guard is satisfied. Blocks indefinitely acquiring the lock, but does
729   * not wait for the guard to be satisfied, and may be interrupted.
730   *
731   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
732   * @throws InterruptedException if interrupted while waiting
733   */
734  public boolean enterIfInterruptibly(Guard guard) throws InterruptedException {
735    if (guard.monitor != this) {
736      throw new IllegalMonitorStateException();
737    }
738    final ReentrantLock lock = this.lock;
739    lock.lockInterruptibly();
740
741    boolean satisfied = false;
742    try {
743      return satisfied = guard.isSatisfied();
744    } finally {
745      if (!satisfied) {
746        lock.unlock();
747      }
748    }
749  }
750
751  /**
752   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
753   * lock, but does not wait for the guard to be satisfied, and may be interrupted.
754   *
755   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
756   * @since 28.0
757   */
758  public boolean enterIfInterruptibly(Guard guard, Duration time) throws InterruptedException {
759    return enterIfInterruptibly(guard, toNanosSaturated(time), TimeUnit.NANOSECONDS);
760  }
761
762  /**
763   * Enters this monitor if the guard is satisfied. Blocks at most the given time acquiring the
764   * lock, but does not wait for the guard to be satisfied, and may be interrupted.
765   *
766   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
767   */
768  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
769  public boolean enterIfInterruptibly(Guard guard, long time, TimeUnit unit)
770      throws InterruptedException {
771    if (guard.monitor != this) {
772      throw new IllegalMonitorStateException();
773    }
774    final ReentrantLock lock = this.lock;
775    if (!lock.tryLock(time, unit)) {
776      return false;
777    }
778
779    boolean satisfied = false;
780    try {
781      return satisfied = guard.isSatisfied();
782    } finally {
783      if (!satisfied) {
784        lock.unlock();
785      }
786    }
787  }
788
789  /**
790   * Enters this monitor if it is possible to do so immediately and the guard is satisfied. Does not
791   * block acquiring the lock and does not wait for the guard to be satisfied.
792   *
793   * <p><b>Note:</b> This method disregards the fairness setting of this monitor.
794   *
795   * @return whether the monitor was entered, which guarantees that the guard is now satisfied
796   */
797  public boolean tryEnterIf(Guard guard) {
798    if (guard.monitor != this) {
799      throw new IllegalMonitorStateException();
800    }
801    final ReentrantLock lock = this.lock;
802    if (!lock.tryLock()) {
803      return false;
804    }
805
806    boolean satisfied = false;
807    try {
808      return satisfied = guard.isSatisfied();
809    } finally {
810      if (!satisfied) {
811        lock.unlock();
812      }
813    }
814  }
815
816  /**
817   * Waits for the guard to be satisfied. Waits indefinitely, but may be interrupted. May be called
818   * only by a thread currently occupying this monitor.
819   *
820   * @throws InterruptedException if interrupted while waiting
821   */
822  public void waitFor(Guard guard) throws InterruptedException {
823    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
824      throw new IllegalMonitorStateException();
825    }
826    if (!guard.isSatisfied()) {
827      await(guard, true);
828    }
829  }
830
831  /**
832   * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted. May
833   * be called only by a thread currently occupying this monitor.
834   *
835   * @return whether the guard is now satisfied
836   * @throws InterruptedException if interrupted while waiting
837   * @since 28.0
838   */
839  public boolean waitFor(Guard guard, Duration time) throws InterruptedException {
840    return waitFor(guard, toNanosSaturated(time), TimeUnit.NANOSECONDS);
841  }
842
843  /**
844   * Waits for the guard to be satisfied. Waits at most the given time, and may be interrupted. May
845   * be called only by a thread currently occupying this monitor.
846   *
847   * @return whether the guard is now satisfied
848   * @throws InterruptedException if interrupted while waiting
849   */
850  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
851  public boolean waitFor(Guard guard, long time, TimeUnit unit) throws InterruptedException {
852    final long timeoutNanos = toSafeNanos(time, unit);
853    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
854      throw new IllegalMonitorStateException();
855    }
856    if (guard.isSatisfied()) {
857      return true;
858    }
859    if (Thread.interrupted()) {
860      throw new InterruptedException();
861    }
862    return awaitNanos(guard, timeoutNanos, true);
863  }
864
865  /**
866   * Waits for the guard to be satisfied. Waits indefinitely. May be called only by a thread
867   * currently occupying this monitor.
868   */
869  public void waitForUninterruptibly(Guard guard) {
870    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
871      throw new IllegalMonitorStateException();
872    }
873    if (!guard.isSatisfied()) {
874      awaitUninterruptibly(guard, true);
875    }
876  }
877
878  /**
879   * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a
880   * thread currently occupying this monitor.
881   *
882   * @return whether the guard is now satisfied
883   * @since 28.0
884   */
885  public boolean waitForUninterruptibly(Guard guard, Duration time) {
886    return waitForUninterruptibly(guard, toNanosSaturated(time), TimeUnit.NANOSECONDS);
887  }
888
889  /**
890   * Waits for the guard to be satisfied. Waits at most the given time. May be called only by a
891   * thread currently occupying this monitor.
892   *
893   * @return whether the guard is now satisfied
894   */
895  @SuppressWarnings("GoodTime") // should accept a java.time.Duration
896  public boolean waitForUninterruptibly(Guard guard, long time, TimeUnit unit) {
897    final long timeoutNanos = toSafeNanos(time, unit);
898    if (!((guard.monitor == this) & lock.isHeldByCurrentThread())) {
899      throw new IllegalMonitorStateException();
900    }
901    if (guard.isSatisfied()) {
902      return true;
903    }
904    boolean signalBeforeWaiting = true;
905    final long startTime = initNanoTime(timeoutNanos);
906    boolean interrupted = Thread.interrupted();
907    try {
908      for (long remainingNanos = timeoutNanos; ; ) {
909        try {
910          return awaitNanos(guard, remainingNanos, signalBeforeWaiting);
911        } catch (InterruptedException interrupt) {
912          interrupted = true;
913          if (guard.isSatisfied()) {
914            return true;
915          }
916          signalBeforeWaiting = false;
917          remainingNanos = remainingNanos(startTime, timeoutNanos);
918        }
919      }
920    } finally {
921      if (interrupted) {
922        Thread.currentThread().interrupt();
923      }
924    }
925  }
926
927  /** Leaves this monitor. May be called only by a thread currently occupying this monitor. */
928  public void leave() {
929    final ReentrantLock lock = this.lock;
930    try {
931      // No need to signal if we will still be holding the lock when we return
932      if (lock.getHoldCount() == 1) {
933        signalNextWaiter();
934      }
935    } finally {
936      lock.unlock(); // Will throw IllegalMonitorStateException if not held
937    }
938  }
939
940  /** Returns whether this monitor is using a fair ordering policy. */
941  public boolean isFair() {
942    return fair;
943  }
944
945  /**
946   * Returns whether this monitor is occupied by any thread. This method is designed for use in
947   * monitoring of the system state, not for synchronization control.
948   */
949  public boolean isOccupied() {
950    return lock.isLocked();
951  }
952
953  /**
954   * Returns whether the current thread is occupying this monitor (has entered more times than it
955   * has left).
956   */
957  public boolean isOccupiedByCurrentThread() {
958    return lock.isHeldByCurrentThread();
959  }
960
961  /**
962   * Returns the number of times the current thread has entered this monitor in excess of the number
963   * of times it has left. Returns 0 if the current thread is not occupying this monitor.
964   */
965  public int getOccupiedDepth() {
966    return lock.getHoldCount();
967  }
968
969  /**
970   * Returns an estimate of the number of threads waiting to enter this monitor. The value is only
971   * an estimate because the number of threads may change dynamically while this method traverses
972   * internal data structures. This method is designed for use in monitoring of the system state,
973   * not for synchronization control.
974   */
975  public int getQueueLength() {
976    return lock.getQueueLength();
977  }
978
979  /**
980   * Returns whether any threads are waiting to enter this monitor. Note that because cancellations
981   * may occur at any time, a {@code true} return does not guarantee that any other thread will ever
982   * enter this monitor. This method is designed primarily for use in monitoring of the system
983   * state.
984   */
985  public boolean hasQueuedThreads() {
986    return lock.hasQueuedThreads();
987  }
988
989  /**
990   * Queries whether the given thread is waiting to enter this monitor. Note that because
991   * cancellations may occur at any time, a {@code true} return does not guarantee that this thread
992   * will ever enter this monitor. This method is designed primarily for use in monitoring of the
993   * system state.
994   */
995  public boolean hasQueuedThread(Thread thread) {
996    return lock.hasQueuedThread(thread);
997  }
998
999  /**
1000   * Queries whether any threads are waiting for the given guard to become satisfied. Note that
1001   * because timeouts and interrupts may occur at any time, a {@code true} return does not guarantee
1002   * that the guard becoming satisfied in the future will awaken any threads. This method is
1003   * designed primarily for use in monitoring of the system state.
1004   */
1005  public boolean hasWaiters(Guard guard) {
1006    return getWaitQueueLength(guard) > 0;
1007  }
1008
1009  /**
1010   * Returns an estimate of the number of threads waiting for the given guard to become satisfied.
1011   * Note that because timeouts and interrupts may occur at any time, the estimate serves only as an
1012   * upper bound on the actual number of waiters. This method is designed for use in monitoring of
1013   * the system state, not for synchronization control.
1014   */
1015  public int getWaitQueueLength(Guard guard) {
1016    if (guard.monitor != this) {
1017      throw new IllegalMonitorStateException();
1018    }
1019    lock.lock();
1020    try {
1021      return guard.waiterCount;
1022    } finally {
1023      lock.unlock();
1024    }
1025  }
1026
1027  /**
1028   * Returns unit.toNanos(time), additionally ensuring the returned value is not at risk of
1029   * overflowing or underflowing, by bounding the value between 0 and (Long.MAX_VALUE / 4) * 3.
1030   * Actually waiting for more than 219 years is not supported!
1031   */
1032  private static long toSafeNanos(long time, TimeUnit unit) {
1033    long timeoutNanos = unit.toNanos(time);
1034    return Longs.constrainToRange(timeoutNanos, 0L, (Long.MAX_VALUE / 4) * 3);
1035  }
1036
1037  /**
1038   * Returns System.nanoTime() unless the timeout has already elapsed. Returns 0L if and only if the
1039   * timeout has already elapsed.
1040   */
1041  private static long initNanoTime(long timeoutNanos) {
1042    if (timeoutNanos <= 0L) {
1043      return 0L;
1044    } else {
1045      long startTime = System.nanoTime();
1046      return (startTime == 0L) ? 1L : startTime;
1047    }
1048  }
1049
1050  /**
1051   * Returns the remaining nanos until the given timeout, or 0L if the timeout has already elapsed.
1052   * Caller must have previously sanitized timeoutNanos using toSafeNanos.
1053   */
1054  private static long remainingNanos(long startTime, long timeoutNanos) {
1055    // assert timeoutNanos == 0L || startTime != 0L;
1056
1057    // TODO : NOT CORRECT, BUT TESTS PASS ANYWAYS!
1058    // if (true) return timeoutNanos;
1059    // ONLY 2 TESTS FAIL IF WE DO:
1060    // if (true) return 0;
1061
1062    return (timeoutNanos <= 0L) ? 0L : timeoutNanos - (System.nanoTime() - startTime);
1063  }
1064
1065  /**
1066   * Signals some other thread waiting on a satisfied guard, if one exists.
1067   *
1068   * <p>We manage calls to this method carefully, to signal only when necessary, but never losing a
1069   * signal, which is the classic problem of this kind of concurrency construct. We must signal if
1070   * the current thread is about to relinquish the lock and may have changed the state protected by
1071   * the monitor, thereby causing some guard to be satisfied.
1072   *
1073   * <p>In addition, any thread that has been signalled when its guard was satisfied acquires the
1074   * responsibility of signalling the next thread when it again relinquishes the lock. Unlike a
1075   * normal Condition, there is no guarantee that an interrupted thread has not been signalled,
1076   * since the concurrency control must manage multiple Conditions. So this method must generally be
1077   * called when waits are interrupted.
1078   *
1079   * <p>On the other hand, if a signalled thread wakes up to discover that its guard is still not
1080   * satisfied, it does *not* need to call this method before returning to wait. This can only
1081   * happen due to spurious wakeup (ignorable) or another thread acquiring the lock before the
1082   * current thread can and returning the guard to the unsatisfied state. In the latter case the
1083   * other thread (last thread modifying the state protected by the monitor) takes over the
1084   * responsibility of signalling the next waiter.
1085   *
1086   * <p>This method must not be called from within a beginWaitingFor/endWaitingFor block, or else
1087   * the current thread's guard might be mistakenly signalled, leading to a lost signal.
1088   */
1089  @GuardedBy("lock")
1090  private void signalNextWaiter() {
1091    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1092      if (isSatisfied(guard)) {
1093        guard.condition.signal();
1094        break;
1095      }
1096    }
1097  }
1098
1099  /**
1100   * Exactly like signalNextWaiter, but caller guarantees that guardToSkip need not be considered,
1101   * because caller has previously checked that guardToSkip.isSatisfied() returned false. An
1102   * optimization for the case that guardToSkip.isSatisfied() may be expensive.
1103   *
1104   * <p>We decided against using this method, since in practice, isSatisfied() is likely to be very
1105   * cheap (typically one field read). Resurrect this method if you find that not to be true.
1106   */
1107  //   @GuardedBy("lock")
1108  //   private void signalNextWaiterSkipping(Guard guardToSkip) {
1109  //     for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1110  //       if (guard != guardToSkip && isSatisfied(guard)) {
1111  //         guard.condition.signal();
1112  //         break;
1113  //       }
1114  //     }
1115  //   }
1116
1117  /**
1118   * Exactly like guard.isSatisfied(), but in addition signals all waiting threads in the (hopefully
1119   * unlikely) event that isSatisfied() throws.
1120   */
1121  @GuardedBy("lock")
1122  private boolean isSatisfied(Guard guard) {
1123    try {
1124      return guard.isSatisfied();
1125    } catch (Throwable throwable) {
1126      signalAllWaiters();
1127      throw throwable;
1128    }
1129  }
1130
1131  /** Signals all threads waiting on guards. */
1132  @GuardedBy("lock")
1133  private void signalAllWaiters() {
1134    for (Guard guard = activeGuards; guard != null; guard = guard.next) {
1135      guard.condition.signalAll();
1136    }
1137  }
1138
1139  /** Records that the current thread is about to wait on the specified guard. */
1140  @GuardedBy("lock")
1141  private void beginWaitingFor(Guard guard) {
1142    int waiters = guard.waiterCount++;
1143    if (waiters == 0) {
1144      // push guard onto activeGuards
1145      guard.next = activeGuards;
1146      activeGuards = guard;
1147    }
1148  }
1149
1150  /** Records that the current thread is no longer waiting on the specified guard. */
1151  @GuardedBy("lock")
1152  private void endWaitingFor(Guard guard) {
1153    int waiters = --guard.waiterCount;
1154    if (waiters == 0) {
1155      // unlink guard from activeGuards
1156      for (Guard p = activeGuards, pred = null; ; pred = p, p = p.next) {
1157        if (p == guard) {
1158          if (pred == null) {
1159            activeGuards = p.next;
1160          } else {
1161            pred.next = p.next;
1162          }
1163          p.next = null; // help GC
1164          break;
1165        }
1166      }
1167    }
1168  }
1169
1170  /*
1171   * Methods that loop waiting on a guard's condition until the guard is satisfied, while recording
1172   * this fact so that other threads know to check our guard and signal us. It's caller's
1173   * responsibility to ensure that the guard is *not* currently satisfied.
1174   */
1175
1176  @GuardedBy("lock")
1177  private void await(Guard guard, boolean signalBeforeWaiting) throws InterruptedException {
1178    if (signalBeforeWaiting) {
1179      signalNextWaiter();
1180    }
1181    beginWaitingFor(guard);
1182    try {
1183      do {
1184        guard.condition.await();
1185      } while (!guard.isSatisfied());
1186    } finally {
1187      endWaitingFor(guard);
1188    }
1189  }
1190
1191  @GuardedBy("lock")
1192  private void awaitUninterruptibly(Guard guard, boolean signalBeforeWaiting) {
1193    if (signalBeforeWaiting) {
1194      signalNextWaiter();
1195    }
1196    beginWaitingFor(guard);
1197    try {
1198      do {
1199        guard.condition.awaitUninterruptibly();
1200      } while (!guard.isSatisfied());
1201    } finally {
1202      endWaitingFor(guard);
1203    }
1204  }
1205
1206  /** Caller should check before calling that guard is not satisfied. */
1207  @GuardedBy("lock")
1208  private boolean awaitNanos(Guard guard, long nanos, boolean signalBeforeWaiting)
1209      throws InterruptedException {
1210    boolean firstTime = true;
1211    try {
1212      do {
1213        if (nanos <= 0L) {
1214          return false;
1215        }
1216        if (firstTime) {
1217          if (signalBeforeWaiting) {
1218            signalNextWaiter();
1219          }
1220          beginWaitingFor(guard);
1221          firstTime = false;
1222        }
1223        nanos = guard.condition.awaitNanos(nanos);
1224      } while (!guard.isSatisfied());
1225      return true;
1226    } finally {
1227      if (!firstTime) {
1228        endWaitingFor(guard);
1229      }
1230    }
1231  }
1232}