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