001/*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.util.concurrent;
016
017import static com.google.common.base.Preconditions.checkNotNull;
018
019import com.google.common.annotations.Beta;
020import com.google.common.annotations.GwtIncompatible;
021import com.google.common.annotations.VisibleForTesting;
022import com.google.common.base.MoreObjects;
023import com.google.common.base.Preconditions;
024import com.google.common.collect.ImmutableSet;
025import com.google.common.collect.Lists;
026import com.google.common.collect.MapMaker;
027import com.google.common.collect.Maps;
028import com.google.common.collect.Sets;
029import com.google.errorprone.annotations.CanIgnoreReturnValue;
030import com.google.j2objc.annotations.Weak;
031import java.util.ArrayList;
032import java.util.Arrays;
033import java.util.Collections;
034import java.util.EnumMap;
035import java.util.List;
036import java.util.Map;
037import java.util.Set;
038import java.util.concurrent.ConcurrentMap;
039import java.util.concurrent.TimeUnit;
040import java.util.concurrent.locks.ReentrantLock;
041import java.util.concurrent.locks.ReentrantReadWriteLock;
042import java.util.logging.Level;
043import java.util.logging.Logger;
044import javax.annotation.Nullable;
045import javax.annotation.concurrent.ThreadSafe;
046
047/**
048 * The {@code CycleDetectingLockFactory} creates {@link ReentrantLock} instances and
049 * {@link ReentrantReadWriteLock} instances that detect potential deadlock by checking for cycles in
050 * lock acquisition order.
051 *
052 * <p>Potential deadlocks detected when calling the {@code lock()}, {@code lockInterruptibly()}, or
053 * {@code tryLock()} methods will result in the execution of the {@link Policy} specified when
054 * creating the factory. The currently available policies are:
055 * <ul>
056 * <li>DISABLED
057 * <li>WARN
058 * <li>THROW
059 * </ul>
060 *
061 * <p>The locks created by a factory instance will detect lock acquisition cycles with locks created
062 * by other {@code CycleDetectingLockFactory} instances (except those with {@code Policy.DISABLED}).
063 * A lock's behavior when a cycle is detected, however, is defined by the {@code Policy} of the
064 * factory that created it. This allows detection of cycles across components while delegating
065 * control over lock behavior to individual components.
066 *
067 * <p>Applications are encouraged to use a {@code CycleDetectingLockFactory} to create any locks for
068 * which external/unmanaged code is executed while the lock is held. (See caveats under
069 * <strong>Performance</strong>).
070 *
071 * <p><strong>Cycle Detection</strong>
072 *
073 * <p>Deadlocks can arise when locks are acquired in an order that forms a cycle. In a simple
074 * example involving two locks and two threads, deadlock occurs when one thread acquires Lock A, and
075 * then Lock B, while another thread acquires Lock B, and then Lock A:
076 *
077 * <pre>
078 * Thread1: acquire(LockA) --X acquire(LockB)
079 * Thread2: acquire(LockB) --X acquire(LockA)
080 * </pre>
081 *
082 * <p>Neither thread will progress because each is waiting for the other. In more complex
083 * applications, cycles can arise from interactions among more than 2 locks:
084 *
085 * <pre>
086 * Thread1: acquire(LockA) --X acquire(LockB)
087 * Thread2: acquire(LockB) --X acquire(LockC)
088 * ...
089 * ThreadN: acquire(LockN) --X acquire(LockA)
090 * </pre>
091 *
092 * <p>The implementation detects cycles by constructing a directed graph in which each lock
093 * represents a node and each edge represents an acquisition ordering between two locks.
094 * <ul>
095 * <li>Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired locks when the
096 *     Thread acquires its first hold (and releases its last remaining hold).
097 * <li>Before the lock is acquired, the lock is checked against the current set of acquired
098 *     locks---to each of the acquired locks, an edge from the soon-to-be-acquired lock is either
099 *     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
164public 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}