1 /*
2 * Copyright (C) 2011 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 java.util.Objects.requireNonNull;
19
20 import com.google.common.annotations.Beta;
21 import com.google.common.annotations.GwtIncompatible;
22 import com.google.common.annotations.VisibleForTesting;
23 import com.google.common.base.MoreObjects;
24 import com.google.common.base.Preconditions;
25 import com.google.common.collect.ImmutableSet;
26 import com.google.common.collect.Lists;
27 import com.google.common.collect.MapMaker;
28 import com.google.common.collect.Maps;
29 import com.google.common.collect.Sets;
30 import com.google.errorprone.annotations.CanIgnoreReturnValue;
31 import com.google.j2objc.annotations.Weak;
32 import java.util.ArrayList;
33 import java.util.Arrays;
34 import java.util.Collections;
35 import java.util.EnumMap;
36 import java.util.List;
37 import java.util.Map;
38 import java.util.Map.Entry;
39 import java.util.Set;
40 import java.util.concurrent.ConcurrentMap;
41 import java.util.concurrent.TimeUnit;
42 import java.util.concurrent.locks.ReentrantLock;
43 import java.util.concurrent.locks.ReentrantReadWriteLock;
44 import java.util.logging.Level;
45 import java.util.logging.Logger;
46 import javax.annotation.CheckForNull;
47
48 /**
49 * The {@code CycleDetectingLockFactory} creates {@link ReentrantLock} instances and {@link
50 * ReentrantReadWriteLock} instances that detect potential deadlock by checking for cycles in lock
51 * acquisition order.
52 *
53 * <p>Potential deadlocks detected when calling the {@code lock()}, {@code lockInterruptibly()}, or
54 * {@code tryLock()} methods will result in the execution of the {@link Policy} specified when
55 * creating the factory. The currently available policies are:
56 *
57 * <ul>
58 * <li>DISABLED
59 * <li>WARN
60 * <li>THROW
61 * </ul>
62 *
63 * <p>The locks created by a factory instance will detect lock acquisition cycles with locks created
64 * by other {@code CycleDetectingLockFactory} instances (except those with {@code Policy.DISABLED}).
65 * A lock's behavior when a cycle is detected, however, is defined by the {@code Policy} of the
66 * factory that created it. This allows detection of cycles across components while delegating
67 * control over lock behavior to individual components.
68 *
69 * <p>Applications are encouraged to use a {@code CycleDetectingLockFactory} to create any locks for
70 * which external/unmanaged code is executed while the lock is held. (See caveats under
71 * <strong>Performance</strong>).
72 *
73 * <p><strong>Cycle Detection</strong>
74 *
75 * <p>Deadlocks can arise when locks are acquired in an order that forms a cycle. In a simple
76 * example involving two locks and two threads, deadlock occurs when one thread acquires Lock A, and
77 * then Lock B, while another thread acquires Lock B, and then Lock A:
78 *
79 * <pre>
80 * Thread1: acquire(LockA) --X acquire(LockB)
81 * Thread2: acquire(LockB) --X acquire(LockA)
82 * </pre>
83 *
84 * <p>Neither thread will progress because each is waiting for the other. In more complex
85 * applications, cycles can arise from interactions among more than 2 locks:
86 *
87 * <pre>
88 * Thread1: acquire(LockA) --X acquire(LockB)
89 * Thread2: acquire(LockB) --X acquire(LockC)
90 * ...
91 * ThreadN: acquire(LockN) --X acquire(LockA)
92 * </pre>
93 *
94 * <p>The implementation detects cycles by constructing a directed graph in which each lock
95 * represents a node and each edge represents an acquisition ordering between two locks.
96 *
97 * <ul>
98 * <li>Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired locks when the
99 * Thread acquires its first hold (and releases its last remaining hold).
100 * <li>Before the lock is acquired, the lock is checked against the current set of acquired
101 * locks---to each of the acquired locks, an edge from the soon-to-be-acquired lock is either
102 * verified or created.
103 * <li>If a new edge needs to be created, the outgoing edges of the acquired locks are traversed
104 * to check for a cycle that reaches the lock to be acquired. If no cycle is detected, a new
105 * "safe" edge is created.
106 * <li>If a cycle is detected, an "unsafe" (cyclic) edge is created to represent a potential
107 * deadlock situation, and the appropriate Policy is executed.
108 * </ul>
109 *
110 * <p>Note that detection of potential deadlock does not necessarily indicate that deadlock will
111 * happen, as it is possible that higher level application logic prevents the cyclic lock
112 * acquisition from occurring. One example of a false positive is:
113 *
114 * <pre>
115 * LockA -> LockB -> LockC
116 * LockA -> LockC -> LockB
117 * </pre>
118 *
119 * <p><strong>ReadWriteLocks</strong>
120 *
121 * <p>While {@code ReadWriteLock} instances have different properties and can form cycles without
122 * potential deadlock, this class treats {@code ReadWriteLock} instances as equivalent to
123 * traditional exclusive locks. Although this increases the false positives that the locks detect
124 * (i.e. cycles that will not actually result in deadlock), it simplifies the algorithm and
125 * implementation considerably. The assumption is that a user of this factory wishes to eliminate
126 * any cyclic acquisition ordering.
127 *
128 * <p><strong>Explicit Lock Acquisition Ordering</strong>
129 *
130 * <p>The {@link CycleDetectingLockFactory.WithExplicitOrdering} class can be used to enforce an
131 * application-specific ordering in addition to performing general cycle detection.
132 *
133 * <p><strong>Garbage Collection</strong>
134 *
135 * <p>In order to allow proper garbage collection of unused locks, the edges of the lock graph are
136 * weak references.
137 *
138 * <p><strong>Performance</strong>
139 *
140 * <p>The extra bookkeeping done by cycle detecting locks comes at some cost to performance.
141 * Benchmarks (as of December 2011) show that:
142 *
143 * <ul>
144 * <li>for an unnested {@code lock()} and {@code unlock()}, a cycle detecting lock takes 38ns as
145 * opposed to the 24ns taken by a plain lock.
146 * <li>for nested locking, the cost increases with the depth of the nesting:
147 * <ul>
148 * <li>2 levels: average of 64ns per lock()/unlock()
149 * <li>3 levels: average of 77ns per lock()/unlock()
150 * <li>4 levels: average of 99ns per lock()/unlock()
151 * <li>5 levels: average of 103ns per lock()/unlock()
152 * <li>10 levels: average of 184ns per lock()/unlock()
153 * <li>20 levels: average of 393ns per lock()/unlock()
154 * </ul>
155 * </ul>
156 *
157 * <p>As such, the CycleDetectingLockFactory may not be suitable for performance-critical
158 * applications which involve tightly-looped or deeply-nested locking algorithms.
159 *
160 * @author Darick Tong
161 * @since 13.0
162 */
163 @Beta
164 @CanIgnoreReturnValue // TODO(cpovirk): Consider being more strict.
165 @GwtIncompatible
166 @ElementTypesAreNonnullByDefault
167 public class CycleDetectingLockFactory {
168
169 /**
170 * Encapsulates the action to be taken when a potential deadlock is encountered. Clients can use
171 * one of the predefined {@link Policies} or specify a custom implementation. Implementations must
172 * be thread-safe.
173 *
174 * @since 13.0
175 */
176 @Beta
177 public interface Policy {
178
179 /**
180 * Called when a potential deadlock is encountered. Implementations can throw the given {@code
181 * exception} and/or execute other desired logic.
182 *
183 * <p>Note that the method will be called even upon an invocation of {@code tryLock()}. Although
184 * {@code tryLock()} technically recovers from deadlock by eventually timing out, this behavior
185 * is chosen based on the assumption that it is the application's wish to prohibit any cyclical
186 * lock acquisitions.
187 */
188 void handlePotentialDeadlock(PotentialDeadlockException exception);
189 }
190
191 /**
192 * Pre-defined {@link Policy} implementations.
193 *
194 * @since 13.0
195 */
196 @Beta
197 public enum Policies implements Policy {
198 /**
199 * When potential deadlock is detected, this policy results in the throwing of the {@code
200 * PotentialDeadlockException} indicating the potential deadlock, which includes stack traces
201 * illustrating the cycle in lock acquisition order.
202 */
203 THROW {
204 @Override
205 public void handlePotentialDeadlock(PotentialDeadlockException e) {
206 throw e;
207 }
208 },
209
210 /**
211 * When potential deadlock is detected, this policy results in the logging of a {@link
212 * Level#SEVERE} message indicating the potential deadlock, which includes stack traces
213 * illustrating the cycle in lock acquisition order.
214 */
215 WARN {
216 @Override
217 public void handlePotentialDeadlock(PotentialDeadlockException e) {
218 logger.log(Level.SEVERE, "Detected potential deadlock", e);
219 }
220 },
221
222 /**
223 * Disables cycle detection. This option causes the factory to return unmodified lock
224 * implementations provided by the JDK, and is provided to allow applications to easily
225 * parameterize when cycle detection is enabled.
226 *
227 * <p>Note that locks created by a factory with this policy will <em>not</em> participate the
228 * cycle detection performed by locks created by other factories.
229 */
230 DISABLED {
231 @Override
232 public void handlePotentialDeadlock(PotentialDeadlockException e) {}
233 };
234 }
235
236 /** Creates a new factory with the specified policy. */
237 public static CycleDetectingLockFactory newInstance(Policy policy) {
238 return new CycleDetectingLockFactory(policy);
239 }
240
241 /** Equivalent to {@code newReentrantLock(lockName, false)}. */
242 public ReentrantLock newReentrantLock(String lockName) {
243 return newReentrantLock(lockName, false);
244 }
245
246 /**
247 * Creates a {@link ReentrantLock} with the given fairness policy. The {@code lockName} is used in
248 * the warning or exception output to help identify the locks involved in the detected deadlock.
249 */
250 public ReentrantLock newReentrantLock(String lockName, boolean fair) {
251 return policy == Policies.DISABLED
252 ? new ReentrantLock(fair)
253 : new CycleDetectingReentrantLock(new LockGraphNode(lockName), fair);
254 }
255
256 /** Equivalent to {@code newReentrantReadWriteLock(lockName, false)}. */
257 public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName) {
258 return newReentrantReadWriteLock(lockName, false);
259 }
260
261 /**
262 * Creates a {@link ReentrantReadWriteLock} with the given fairness policy. The {@code lockName}
263 * is used in the warning or exception output to help identify the locks involved in the detected
264 * deadlock.
265 */
266 public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName, boolean fair) {
267 return policy == Policies.DISABLED
268 ? new ReentrantReadWriteLock(fair)
269 : new CycleDetectingReentrantReadWriteLock(new LockGraphNode(lockName), fair);
270 }
271
272 // A static mapping from an Enum type to its set of LockGraphNodes.
273 private static final ConcurrentMap<
274 Class<? extends Enum<?>>, Map<? extends Enum<?>, LockGraphNode>>
275 lockGraphNodesPerType = new MapMaker().weakKeys().makeMap();
276
277 /** Creates a {@code CycleDetectingLockFactory.WithExplicitOrdering<E>}. */
278 public static <E extends Enum<E>> WithExplicitOrdering<E> newInstanceWithExplicitOrdering(
279 Class<E> enumClass, Policy policy) {
280 // createNodes maps each enumClass to a Map with the corresponding enum key
281 // type.
282 checkNotNull(enumClass);
283 checkNotNull(policy);
284 @SuppressWarnings("unchecked")
285 Map<E, LockGraphNode> lockGraphNodes = (Map<E, LockGraphNode>) getOrCreateNodes(enumClass);
286 return new WithExplicitOrdering<E>(policy, lockGraphNodes);
287 }
288
289 @SuppressWarnings("unchecked")
290 private static <E extends Enum<E>> Map<? extends E, LockGraphNode> getOrCreateNodes(
291 Class<E> clazz) {
292 Map<E, LockGraphNode> existing = (Map<E, LockGraphNode>) lockGraphNodesPerType.get(clazz);
293 if (existing != null) {
294 return existing;
295 }
296 Map<E, LockGraphNode> created = createNodes(clazz);
297 existing = (Map<E, LockGraphNode>) lockGraphNodesPerType.putIfAbsent(clazz, created);
298 return MoreObjects.firstNonNull(existing, created);
299 }
300
301 /**
302 * For a given Enum type, creates an immutable map from each of the Enum's values to a
303 * corresponding LockGraphNode, with the {@code allowedPriorLocks} and {@code
304 * disallowedPriorLocks} prepopulated with nodes according to the natural ordering of the
305 * associated Enum values.
306 */
307 @VisibleForTesting
308 static <E extends Enum<E>> Map<E, LockGraphNode> createNodes(Class<E> clazz) {
309 EnumMap<E, LockGraphNode> map = Maps.newEnumMap(clazz);
310 E[] keys = clazz.getEnumConstants();
311 final int numKeys = keys.length;
312 ArrayList<LockGraphNode> nodes = Lists.newArrayListWithCapacity(numKeys);
313 // Create a LockGraphNode for each enum value.
314 for (E key : keys) {
315 LockGraphNode node = new LockGraphNode(getLockName(key));
316 nodes.add(node);
317 map.put(key, node);
318 }
319 // Pre-populate all allowedPriorLocks with nodes of smaller ordinal.
320 for (int i = 1; i < numKeys; i++) {
321 nodes.get(i).checkAcquiredLocks(Policies.THROW, nodes.subList(0, i));
322 }
323 // Pre-populate all disallowedPriorLocks with nodes of larger ordinal.
324 for (int i = 0; i < numKeys - 1; i++) {
325 nodes.get(i).checkAcquiredLocks(Policies.DISABLED, nodes.subList(i + 1, numKeys));
326 }
327 return Collections.unmodifiableMap(map);
328 }
329
330 /**
331 * For the given Enum value {@code rank}, returns the value's {@code "EnumClass.name"}, which is
332 * used in exception and warning output.
333 */
334 private static String getLockName(Enum<?> rank) {
335 return rank.getDeclaringClass().getSimpleName() + "." + rank.name();
336 }
337
338 /**
339 * A {@code CycleDetectingLockFactory.WithExplicitOrdering} provides the additional enforcement of
340 * an application-specified ordering of lock acquisitions. The application defines the allowed
341 * ordering with an {@code Enum} whose values each correspond to a lock type. The order in which
342 * the values are declared dictates the allowed order of lock acquisition. In other words, locks
343 * corresponding to smaller values of {@link Enum#ordinal()} should only be acquired before locks
344 * with larger ordinals. Example:
345 *
346 * <pre>{@code
347 * enum MyLockOrder {
348 * FIRST, SECOND, THIRD;
349 * }
350 *
351 * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory =
352 * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(Policies.THROW);
353 *
354 * Lock lock1 = factory.newReentrantLock(MyLockOrder.FIRST);
355 * Lock lock2 = factory.newReentrantLock(MyLockOrder.SECOND);
356 * Lock lock3 = factory.newReentrantLock(MyLockOrder.THIRD);
357 *
358 * lock1.lock();
359 * lock3.lock();
360 * lock2.lock(); // will throw an IllegalStateException
361 * }</pre>
362 *
363 * <p>As with all locks created by instances of {@code CycleDetectingLockFactory} explicitly
364 * ordered locks participate in general cycle detection with all other cycle detecting locks, and
365 * a lock's behavior when detecting a cyclic lock acquisition is defined by the {@code Policy} of
366 * the factory that created it.
367 *
368 * <p>Note, however, that although multiple locks can be created for a given Enum value, whether
369 * it be through separate factory instances or through multiple calls to the same factory,
370 * attempting to acquire multiple locks with the same Enum value (within the same thread) will
371 * result in an IllegalStateException regardless of the factory's policy. For example:
372 *
373 * <pre>{@code
374 * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory1 =
375 * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
376 * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory2 =
377 * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
378 *
379 * Lock lockA = factory1.newReentrantLock(MyLockOrder.FIRST);
380 * Lock lockB = factory1.newReentrantLock(MyLockOrder.FIRST);
381 * Lock lockC = factory2.newReentrantLock(MyLockOrder.FIRST);
382 *
383 * lockA.lock();
384 *
385 * lockB.lock(); // will throw an IllegalStateException
386 * lockC.lock(); // will throw an IllegalStateException
387 *
388 * lockA.lock(); // reentrant acquisition is okay
389 * }</pre>
390 *
391 * <p>It is the responsibility of the application to ensure that multiple lock instances with the
392 * same rank are never acquired in the same thread.
393 *
394 * @param <E> The Enum type representing the explicit lock ordering.
395 * @since 13.0
396 */
397 @Beta
398 public static final class WithExplicitOrdering<E extends Enum<E>>
399 extends CycleDetectingLockFactory {
400
401 private final Map<E, LockGraphNode> lockGraphNodes;
402
403 @VisibleForTesting
404 WithExplicitOrdering(Policy policy, Map<E, LockGraphNode> lockGraphNodes) {
405 super(policy);
406 this.lockGraphNodes = lockGraphNodes;
407 }
408
409 /** Equivalent to {@code newReentrantLock(rank, false)}. */
410 public ReentrantLock newReentrantLock(E rank) {
411 return newReentrantLock(rank, false);
412 }
413
414 /**
415 * Creates a {@link ReentrantLock} with the given fairness policy and rank. The values returned
416 * by {@link Enum#getDeclaringClass()} and {@link Enum#name()} are used to describe the lock in
417 * warning or exception output.
418 *
419 * @throws IllegalStateException If the factory has already created a {@code Lock} with the
420 * specified rank.
421 */
422 public ReentrantLock newReentrantLock(E rank, boolean fair) {
423 return policy == Policies.DISABLED
424 ? new ReentrantLock(fair)
425 // requireNonNull is safe because createNodes inserts an entry for every E.
426 // (If the caller passes `null` for the `rank` parameter, this will throw, but that's OK.)
427 : new CycleDetectingReentrantLock(requireNonNull(lockGraphNodes.get(rank)), fair);
428 }
429
430 /** Equivalent to {@code newReentrantReadWriteLock(rank, false)}. */
431 public ReentrantReadWriteLock newReentrantReadWriteLock(E rank) {
432 return newReentrantReadWriteLock(rank, false);
433 }
434
435 /**
436 * Creates a {@link ReentrantReadWriteLock} with the given fairness policy and rank. The values
437 * returned by {@link Enum#getDeclaringClass()} and {@link Enum#name()} are used to describe the
438 * lock in warning or exception output.
439 *
440 * @throws IllegalStateException If the factory has already created a {@code Lock} with the
441 * specified rank.
442 */
443 public ReentrantReadWriteLock newReentrantReadWriteLock(E rank, boolean fair) {
444 return policy == Policies.DISABLED
445 ? new ReentrantReadWriteLock(fair)
446 // requireNonNull is safe because createNodes inserts an entry for every E.
447 // (If the caller passes `null` for the `rank` parameter, this will throw, but that's OK.)
448 : new CycleDetectingReentrantReadWriteLock(
449 requireNonNull(lockGraphNodes.get(rank)), fair);
450 }
451 }
452
453 //////// Implementation /////////
454
455 private static final Logger logger = Logger.getLogger(CycleDetectingLockFactory.class.getName());
456
457 final Policy policy;
458
459 private CycleDetectingLockFactory(Policy policy) {
460 this.policy = checkNotNull(policy);
461 }
462
463 /**
464 * Tracks the currently acquired locks for each Thread, kept up to date by calls to {@link
465 * #aboutToAcquire(CycleDetectingLock)} and {@link #lockStateChanged(CycleDetectingLock)}.
466 */
467 // This is logically a Set, but an ArrayList is used to minimize the amount
468 // of allocation done on lock()/unlock().
469 private static final ThreadLocal<ArrayList<LockGraphNode>> acquiredLocks =
470 new ThreadLocal<ArrayList<LockGraphNode>>() {
471 @Override
472 protected ArrayList<LockGraphNode> initialValue() {
473 return Lists.<LockGraphNode>newArrayListWithCapacity(3);
474 }
475 };
476
477 /**
478 * A Throwable used to record a stack trace that illustrates an example of a specific lock
479 * acquisition ordering. The top of the stack trace is truncated such that it starts with the
480 * acquisition of the lock in question, e.g.
481 *
482 * <pre>
483 * com...ExampleStackTrace: LockB -> LockC
484 * at com...CycleDetectingReentrantLock.lock(CycleDetectingLockFactory.java:443)
485 * at ...
486 * at ...
487 * at com...MyClass.someMethodThatAcquiresLockB(MyClass.java:123)
488 * </pre>
489 */
490 private static class ExampleStackTrace extends IllegalStateException {
491
492 static final StackTraceElement[] EMPTY_STACK_TRACE = new StackTraceElement[0];
493
494 static final ImmutableSet<String> EXCLUDED_CLASS_NAMES =
495 ImmutableSet.of(
496 CycleDetectingLockFactory.class.getName(),
497 ExampleStackTrace.class.getName(),
498 LockGraphNode.class.getName());
499
500 ExampleStackTrace(LockGraphNode node1, LockGraphNode node2) {
501 super(node1.getLockName() + " -> " + node2.getLockName());
502 StackTraceElement[] origStackTrace = getStackTrace();
503 for (int i = 0, n = origStackTrace.length; i < n; i++) {
504 if (WithExplicitOrdering.class.getName().equals(origStackTrace[i].getClassName())) {
505 // For pre-populated disallowedPriorLocks edges, omit the stack trace.
506 setStackTrace(EMPTY_STACK_TRACE);
507 break;
508 }
509 if (!EXCLUDED_CLASS_NAMES.contains(origStackTrace[i].getClassName())) {
510 setStackTrace(Arrays.copyOfRange(origStackTrace, i, n));
511 break;
512 }
513 }
514 }
515 }
516
517 /**
518 * Represents a detected cycle in lock acquisition ordering. The exception includes a causal chain
519 * of {@code ExampleStackTrace} instances to illustrate the cycle, e.g.
520 *
521 * <pre>
522 * com....PotentialDeadlockException: Potential Deadlock from LockC -> ReadWriteA
523 * at ...
524 * at ...
525 * Caused by: com...ExampleStackTrace: LockB -> LockC
526 * at ...
527 * at ...
528 * Caused by: com...ExampleStackTrace: ReadWriteA -> LockB
529 * at ...
530 * at ...
531 * </pre>
532 *
533 * <p>Instances are logged for the {@code Policies.WARN}, and thrown for {@code Policies.THROW}.
534 *
535 * @since 13.0
536 */
537 @Beta
538 public static final class PotentialDeadlockException extends ExampleStackTrace {
539
540 private final ExampleStackTrace conflictingStackTrace;
541
542 private PotentialDeadlockException(
543 LockGraphNode node1, LockGraphNode node2, ExampleStackTrace conflictingStackTrace) {
544 super(node1, node2);
545 this.conflictingStackTrace = conflictingStackTrace;
546 initCause(conflictingStackTrace);
547 }
548
549 public ExampleStackTrace getConflictingStackTrace() {
550 return conflictingStackTrace;
551 }
552
553 /**
554 * Appends the chain of messages from the {@code conflictingStackTrace} to the original {@code
555 * message}.
556 */
557 @Override
558 public String getMessage() {
559 // requireNonNull is safe because ExampleStackTrace sets a non-null message.
560 StringBuilder message = new StringBuilder(requireNonNull(super.getMessage()));
561 for (Throwable t = conflictingStackTrace; t != null; t = t.getCause()) {
562 message.append(", ").append(t.getMessage());
563 }
564 return message.toString();
565 }
566 }
567
568 /**
569 * Internal Lock implementations implement the {@code CycleDetectingLock} interface, allowing the
570 * detection logic to treat all locks in the same manner.
571 */
572 private interface CycleDetectingLock {
573
574 /** @return the {@link LockGraphNode} associated with this lock. */
575 LockGraphNode getLockGraphNode();
576
577 /** @return {@code true} if the current thread has acquired this lock. */
578 boolean isAcquiredByCurrentThread();
579 }
580
581 /**
582 * A {@code LockGraphNode} associated with each lock instance keeps track of the directed edges in
583 * the lock acquisition graph.
584 */
585 private static class LockGraphNode {
586
587 /**
588 * The map tracking the locks that are known to be acquired before this lock, each associated
589 * with an example stack trace. Locks are weakly keyed to allow proper garbage collection when
590 * they are no longer referenced.
591 */
592 final Map<LockGraphNode, ExampleStackTrace> allowedPriorLocks =
593 new MapMaker().weakKeys().makeMap();
594
595 /**
596 * The map tracking lock nodes that can cause a lock acquisition cycle if acquired before this
597 * node.
598 */
599 final Map<LockGraphNode, PotentialDeadlockException> disallowedPriorLocks =
600 new MapMaker().weakKeys().makeMap();
601
602 final String lockName;
603
604 LockGraphNode(String lockName) {
605 this.lockName = Preconditions.checkNotNull(lockName);
606 }
607
608 String getLockName() {
609 return lockName;
610 }
611
612 void checkAcquiredLocks(Policy policy, List<LockGraphNode> acquiredLocks) {
613 for (LockGraphNode acquiredLock : acquiredLocks) {
614 checkAcquiredLock(policy, acquiredLock);
615 }
616 }
617
618 /**
619 * Checks the acquisition-ordering between {@code this}, which is about to be acquired, and the
620 * specified {@code acquiredLock}.
621 *
622 * <p>When this method returns, the {@code acquiredLock} should be in either the {@code
623 * preAcquireLocks} map, for the case in which it is safe to acquire {@code this} after the
624 * {@code acquiredLock}, or in the {@code disallowedPriorLocks} map, in which case it is not
625 * safe.
626 */
627 void checkAcquiredLock(Policy policy, LockGraphNode acquiredLock) {
628 // checkAcquiredLock() should never be invoked by a lock that has already
629 // been acquired. For unordered locks, aboutToAcquire() ensures this by
630 // checking isAcquiredByCurrentThread(). For ordered locks, however, this
631 // can happen because multiple locks may share the same LockGraphNode. In
632 // this situation, throw an IllegalStateException as defined by contract
633 // described in the documentation of WithExplicitOrdering.
634 Preconditions.checkState(
635 this != acquiredLock,
636 "Attempted to acquire multiple locks with the same rank %s",
637 acquiredLock.getLockName());
638
639 if (allowedPriorLocks.containsKey(acquiredLock)) {
640 // The acquisition ordering from "acquiredLock" to "this" has already
641 // been verified as safe. In a properly written application, this is
642 // the common case.
643 return;
644 }
645 PotentialDeadlockException previousDeadlockException = disallowedPriorLocks.get(acquiredLock);
646 if (previousDeadlockException != null) {
647 // Previously determined to be an unsafe lock acquisition.
648 // Create a new PotentialDeadlockException with the same causal chain
649 // (the example cycle) as that of the cached exception.
650 PotentialDeadlockException exception =
651 new PotentialDeadlockException(
652 acquiredLock, this, previousDeadlockException.getConflictingStackTrace());
653 policy.handlePotentialDeadlock(exception);
654 return;
655 }
656 // Otherwise, it's the first time seeing this lock relationship. Look for
657 // a path from the acquiredLock to this.
658 Set<LockGraphNode> seen = Sets.newIdentityHashSet();
659 ExampleStackTrace path = acquiredLock.findPathTo(this, seen);
660
661 if (path == null) {
662 // this can be safely acquired after the acquiredLock.
663 //
664 // Note that there is a race condition here which can result in missing
665 // a cyclic edge: it's possible for two threads to simultaneous find
666 // "safe" edges which together form a cycle. Preventing this race
667 // condition efficiently without _introducing_ deadlock is probably
668 // tricky. For now, just accept the race condition---missing a warning
669 // now and then is still better than having no deadlock detection.
670 allowedPriorLocks.put(acquiredLock, new ExampleStackTrace(acquiredLock, this));
671 } else {
672 // Unsafe acquisition order detected. Create and cache a
673 // PotentialDeadlockException.
674 PotentialDeadlockException exception =
675 new PotentialDeadlockException(acquiredLock, this, path);
676 disallowedPriorLocks.put(acquiredLock, exception);
677 policy.handlePotentialDeadlock(exception);
678 }
679 }
680
681 /**
682 * Performs a depth-first traversal of the graph edges defined by each node's {@code
683 * allowedPriorLocks} to find a path between {@code this} and the specified {@code lock}.
684 *
685 * @return If a path was found, a chained {@link ExampleStackTrace} illustrating the path to the
686 * {@code lock}, or {@code null} if no path was found.
687 */
688 @CheckForNull
689 private ExampleStackTrace findPathTo(LockGraphNode node, Set<LockGraphNode> seen) {
690 if (!seen.add(this)) {
691 return null; // Already traversed this node.
692 }
693 ExampleStackTrace found = allowedPriorLocks.get(node);
694 if (found != null) {
695 return found; // Found a path ending at the node!
696 }
697 // Recurse the edges.
698 for (Entry<LockGraphNode, ExampleStackTrace> entry : allowedPriorLocks.entrySet()) {
699 LockGraphNode preAcquiredLock = entry.getKey();
700 found = preAcquiredLock.findPathTo(node, seen);
701 if (found != null) {
702 // One of this node's allowedPriorLocks found a path. Prepend an
703 // ExampleStackTrace(preAcquiredLock, this) to the returned chain of
704 // ExampleStackTraces.
705 ExampleStackTrace path = new ExampleStackTrace(preAcquiredLock, this);
706 path.setStackTrace(entry.getValue().getStackTrace());
707 path.initCause(found);
708 return path;
709 }
710 }
711 return null;
712 }
713 }
714
715 /**
716 * CycleDetectingLock implementations must call this method before attempting to acquire the lock.
717 */
718 private void aboutToAcquire(CycleDetectingLock lock) {
719 if (!lock.isAcquiredByCurrentThread()) {
720 ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
721 LockGraphNode node = lock.getLockGraphNode();
722 node.checkAcquiredLocks(policy, acquiredLockList);
723 acquiredLockList.add(node);
724 }
725 }
726
727 /**
728 * CycleDetectingLock implementations must call this method in a {@code finally} clause after any
729 * attempt to change the lock state, including both lock and unlock attempts. Failure to do so can
730 * result in corrupting the acquireLocks set.
731 */
732 private static void lockStateChanged(CycleDetectingLock lock) {
733 if (!lock.isAcquiredByCurrentThread()) {
734 ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
735 LockGraphNode node = lock.getLockGraphNode();
736 // Iterate in reverse because locks are usually locked/unlocked in a
737 // LIFO order.
738 for (int i = acquiredLockList.size() - 1; i >= 0; i--) {
739 if (acquiredLockList.get(i) == node) {
740 acquiredLockList.remove(i);
741 break;
742 }
743 }
744 }
745 }
746
747 final class CycleDetectingReentrantLock extends ReentrantLock implements CycleDetectingLock {
748
749 private final LockGraphNode lockGraphNode;
750
751 private CycleDetectingReentrantLock(LockGraphNode lockGraphNode, boolean fair) {
752 super(fair);
753 this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
754 }
755
756 ///// CycleDetectingLock methods. /////
757
758 @Override
759 public LockGraphNode getLockGraphNode() {
760 return lockGraphNode;
761 }
762
763 @Override
764 public boolean isAcquiredByCurrentThread() {
765 return isHeldByCurrentThread();
766 }
767
768 ///// Overridden ReentrantLock methods. /////
769
770 @Override
771 public void lock() {
772 aboutToAcquire(this);
773 try {
774 super.lock();
775 } finally {
776 lockStateChanged(this);
777 }
778 }
779
780 @Override
781 public void lockInterruptibly() throws InterruptedException {
782 aboutToAcquire(this);
783 try {
784 super.lockInterruptibly();
785 } finally {
786 lockStateChanged(this);
787 }
788 }
789
790 @Override
791 public boolean tryLock() {
792 aboutToAcquire(this);
793 try {
794 return super.tryLock();
795 } finally {
796 lockStateChanged(this);
797 }
798 }
799
800 @Override
801 public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
802 aboutToAcquire(this);
803 try {
804 return super.tryLock(timeout, unit);
805 } finally {
806 lockStateChanged(this);
807 }
808 }
809
810 @Override
811 public void unlock() {
812 try {
813 super.unlock();
814 } finally {
815 lockStateChanged(this);
816 }
817 }
818 }
819
820 final class CycleDetectingReentrantReadWriteLock extends ReentrantReadWriteLock
821 implements CycleDetectingLock {
822
823 // These ReadLock/WriteLock implementations shadow those in the
824 // ReentrantReadWriteLock superclass. They are simply wrappers around the
825 // internal Sync object, so this is safe since the shadowed locks are never
826 // exposed or used.
827 private final CycleDetectingReentrantReadLock readLock;
828 private final CycleDetectingReentrantWriteLock writeLock;
829
830 private final LockGraphNode lockGraphNode;
831
832 private CycleDetectingReentrantReadWriteLock(LockGraphNode lockGraphNode, boolean fair) {
833 super(fair);
834 this.readLock = new CycleDetectingReentrantReadLock(this);
835 this.writeLock = new CycleDetectingReentrantWriteLock(this);
836 this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
837 }
838
839 ///// Overridden ReentrantReadWriteLock methods. /////
840
841 @Override
842 public ReadLock readLock() {
843 return readLock;
844 }
845
846 @Override
847 public WriteLock writeLock() {
848 return writeLock;
849 }
850
851 ///// CycleDetectingLock methods. /////
852
853 @Override
854 public LockGraphNode getLockGraphNode() {
855 return lockGraphNode;
856 }
857
858 @Override
859 public boolean isAcquiredByCurrentThread() {
860 return isWriteLockedByCurrentThread() || getReadHoldCount() > 0;
861 }
862 }
863
864 private class CycleDetectingReentrantReadLock extends ReentrantReadWriteLock.ReadLock {
865
866 @Weak final CycleDetectingReentrantReadWriteLock readWriteLock;
867
868 CycleDetectingReentrantReadLock(CycleDetectingReentrantReadWriteLock readWriteLock) {
869 super(readWriteLock);
870 this.readWriteLock = readWriteLock;
871 }
872
873 @Override
874 public void lock() {
875 aboutToAcquire(readWriteLock);
876 try {
877 super.lock();
878 } finally {
879 lockStateChanged(readWriteLock);
880 }
881 }
882
883 @Override
884 public void lockInterruptibly() throws InterruptedException {
885 aboutToAcquire(readWriteLock);
886 try {
887 super.lockInterruptibly();
888 } finally {
889 lockStateChanged(readWriteLock);
890 }
891 }
892
893 @Override
894 public boolean tryLock() {
895 aboutToAcquire(readWriteLock);
896 try {
897 return super.tryLock();
898 } finally {
899 lockStateChanged(readWriteLock);
900 }
901 }
902
903 @Override
904 public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
905 aboutToAcquire(readWriteLock);
906 try {
907 return super.tryLock(timeout, unit);
908 } finally {
909 lockStateChanged(readWriteLock);
910 }
911 }
912
913 @Override
914 public void unlock() {
915 try {
916 super.unlock();
917 } finally {
918 lockStateChanged(readWriteLock);
919 }
920 }
921 }
922
923 private class CycleDetectingReentrantWriteLock extends ReentrantReadWriteLock.WriteLock {
924
925 @Weak final CycleDetectingReentrantReadWriteLock readWriteLock;
926
927 CycleDetectingReentrantWriteLock(CycleDetectingReentrantReadWriteLock readWriteLock) {
928 super(readWriteLock);
929 this.readWriteLock = readWriteLock;
930 }
931
932 @Override
933 public void lock() {
934 aboutToAcquire(readWriteLock);
935 try {
936 super.lock();
937 } finally {
938 lockStateChanged(readWriteLock);
939 }
940 }
941
942 @Override
943 public void lockInterruptibly() throws InterruptedException {
944 aboutToAcquire(readWriteLock);
945 try {
946 super.lockInterruptibly();
947 } finally {
948 lockStateChanged(readWriteLock);
949 }
950 }
951
952 @Override
953 public boolean tryLock() {
954 aboutToAcquire(readWriteLock);
955 try {
956 return super.tryLock();
957 } finally {
958 lockStateChanged(readWriteLock);
959 }
960 }
961
962 @Override
963 public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
964 aboutToAcquire(readWriteLock);
965 try {
966 return super.tryLock(timeout, unit);
967 } finally {
968 lockStateChanged(readWriteLock);
969 }
970 }
971
972 @Override
973 public void unlock() {
974 try {
975 super.unlock();
976 } finally {
977 lockStateChanged(readWriteLock);
978 }
979 }
980 }
981 }