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;
018import static java.util.Objects.requireNonNull;
019
020import com.google.common.annotations.Beta;
021import com.google.common.annotations.GwtIncompatible;
022import com.google.common.annotations.VisibleForTesting;
023import com.google.common.base.MoreObjects;
024import com.google.common.base.Preconditions;
025import com.google.common.collect.ImmutableSet;
026import com.google.common.collect.Lists;
027import com.google.common.collect.MapMaker;
028import com.google.common.collect.Maps;
029import com.google.common.collect.Sets;
030import com.google.errorprone.annotations.CanIgnoreReturnValue;
031import com.google.j2objc.annotations.Weak;
032import java.util.ArrayList;
033import java.util.Arrays;
034import java.util.Collections;
035import java.util.EnumMap;
036import java.util.List;
037import java.util.Map;
038import java.util.Map.Entry;
039import java.util.Set;
040import java.util.concurrent.ConcurrentMap;
041import java.util.concurrent.TimeUnit;
042import java.util.concurrent.locks.ReentrantLock;
043import java.util.concurrent.locks.ReentrantReadWriteLock;
044import java.util.logging.Level;
045import java.util.logging.Logger;
046import javax.annotation.CheckForNull;
047
048/**
049 * The {@code CycleDetectingLockFactory} creates {@link ReentrantLock} instances and {@link
050 * ReentrantReadWriteLock} instances that detect potential deadlock by checking for cycles in lock
051 * acquisition order.
052 *
053 * <p>Potential deadlocks detected when calling the {@code lock()}, {@code lockInterruptibly()}, or
054 * {@code tryLock()} methods will result in the execution of the {@link Policy} specified when
055 * creating the factory. The currently available policies are:
056 *
057 * <ul>
058 *   <li>DISABLED
059 *   <li>WARN
060 *   <li>THROW
061 * </ul>
062 *
063 * <p>The locks created by a factory instance will detect lock acquisition cycles with locks created
064 * by other {@code CycleDetectingLockFactory} instances (except those with {@code Policy.DISABLED}).
065 * A lock's behavior when a cycle is detected, however, is defined by the {@code Policy} of the
066 * factory that created it. This allows detection of cycles across components while delegating
067 * control over lock behavior to individual components.
068 *
069 * <p>Applications are encouraged to use a {@code CycleDetectingLockFactory} to create any locks for
070 * which external/unmanaged code is executed while the lock is held. (See caveats under
071 * <strong>Performance</strong>).
072 *
073 * <p><strong>Cycle Detection</strong>
074 *
075 * <p>Deadlocks can arise when locks are acquired in an order that forms a cycle. In a simple
076 * example involving two locks and two threads, deadlock occurs when one thread acquires Lock A, and
077 * then Lock B, while another thread acquires Lock B, and then Lock A:
078 *
079 * <pre>
080 * Thread1: acquire(LockA) --X acquire(LockB)
081 * Thread2: acquire(LockB) --X acquire(LockA)
082 * </pre>
083 *
084 * <p>Neither thread will progress because each is waiting for the other. In more complex
085 * applications, cycles can arise from interactions among more than 2 locks:
086 *
087 * <pre>
088 * Thread1: acquire(LockA) --X acquire(LockB)
089 * Thread2: acquire(LockB) --X acquire(LockC)
090 * ...
091 * ThreadN: acquire(LockN) --X acquire(LockA)
092 * </pre>
093 *
094 * <p>The implementation detects cycles by constructing a directed graph in which each lock
095 * represents a node and each edge represents an acquisition ordering between two locks.
096 *
097 * <ul>
098 *   <li>Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired locks when the
099 *       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 -&gt; LockB -&gt; LockC
116 * LockA -&gt; LockC -&gt; 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
167public 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 -&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 {@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}