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