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