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.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 java.util.logging.Logger;
045import org.checkerframework.checker.nullness.qual.Nullable;
046
047/**
048 * The {@code CycleDetectingLockFactory} creates {@link ReentrantLock} instances and {@link
049 * ReentrantReadWriteLock} instances that detect potential deadlock by checking for cycles in lock
050 * 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 *
056 * <ul>
057 *   <li>DISABLED
058 *   <li>WARN
059 *   <li>THROW
060 * </ul>
061 *
062 * <p>The locks created by a factory instance will detect lock acquisition cycles with locks created
063 * by other {@code CycleDetectingLockFactory} instances (except those with {@code Policy.DISABLED}).
064 * A lock's behavior when a cycle is detected, however, is defined by the {@code Policy} of the
065 * factory that created it. This allows detection of cycles across components while delegating
066 * control over lock behavior to individual components.
067 *
068 * <p>Applications are encouraged to use a {@code CycleDetectingLockFactory} to create any locks for
069 * which external/unmanaged code is executed while the lock is held. (See caveats under
070 * <strong>Performance</strong>).
071 *
072 * <p><strong>Cycle Detection</strong>
073 *
074 * <p>Deadlocks can arise when locks are acquired in an order that forms a cycle. In a simple
075 * example involving two locks and two threads, deadlock occurs when one thread acquires Lock A, and
076 * then Lock B, while another thread acquires Lock B, and then Lock A:
077 *
078 * <pre>
079 * Thread1: acquire(LockA) --X acquire(LockB)
080 * Thread2: acquire(LockB) --X acquire(LockA)
081 * </pre>
082 *
083 * <p>Neither thread will progress because each is waiting for the other. In more complex
084 * applications, cycles can arise from interactions among more than 2 locks:
085 *
086 * <pre>
087 * Thread1: acquire(LockA) --X acquire(LockB)
088 * Thread2: acquire(LockB) --X acquire(LockC)
089 * ...
090 * ThreadN: acquire(LockN) --X acquire(LockA)
091 * </pre>
092 *
093 * <p>The implementation detects cycles by constructing a directed graph in which each lock
094 * represents a node and each edge represents an acquisition ordering between two locks.
095 *
096 * <ul>
097 *   <li>Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired locks when the
098 *       Thread acquires its first hold (and releases its last remaining hold).
099 *   <li>Before the lock is acquired, the lock is checked against the current set of acquired
100 *       locks---to each of the acquired locks, an edge from the soon-to-be-acquired lock is either
101 *       verified or created.
102 *   <li>If a new edge needs to be created, the outgoing edges of the acquired locks are traversed
103 *       to check for a cycle that reaches the lock to be acquired. If no cycle is detected, a new
104 *       "safe" edge is created.
105 *   <li>If a cycle is detected, an "unsafe" (cyclic) edge is created to represent a potential
106 *       deadlock situation, and the appropriate Policy is executed.
107 * </ul>
108 *
109 * <p>Note that detection of potential deadlock does not necessarily indicate that deadlock will
110 * happen, as it is possible that higher level application logic prevents the cyclic lock
111 * acquisition from occurring. One example of a false positive is:
112 *
113 * <pre>
114 * LockA -&gt; LockB -&gt; LockC
115 * LockA -&gt; LockC -&gt; LockB
116 * </pre>
117 *
118 * <p><strong>ReadWriteLocks</strong>
119 *
120 * <p>While {@code ReadWriteLock} instances have different properties and can form cycles without
121 * potential deadlock, this class treats {@code ReadWriteLock} instances as equivalent to
122 * traditional exclusive locks. Although this increases the false positives that the locks detect
123 * (i.e. cycles that will not actually result in deadlock), it simplifies the algorithm and
124 * implementation considerably. The assumption is that a user of this factory wishes to eliminate
125 * any cyclic acquisition ordering.
126 *
127 * <p><strong>Explicit Lock Acquisition Ordering</strong>
128 *
129 * <p>The {@link CycleDetectingLockFactory.WithExplicitOrdering} class can be used to enforce an
130 * application-specific ordering in addition to performing general cycle detection.
131 *
132 * <p><strong>Garbage Collection</strong>
133 *
134 * <p>In order to allow proper garbage collection of unused locks, the edges of the lock graph are
135 * weak references.
136 *
137 * <p><strong>Performance</strong>
138 *
139 * <p>The extra bookkeeping done by cycle detecting locks comes at some cost to performance.
140 * Benchmarks (as of December 2011) show that:
141 *
142 * <ul>
143 *   <li>for an unnested {@code lock()} and {@code unlock()}, a cycle detecting lock takes 38ns as
144 *       opposed to the 24ns taken by a plain lock.
145 *   <li>for nested locking, the cost increases with the depth of the nesting:
146 *       <ul>
147 *         <li>2 levels: average of 64ns per lock()/unlock()
148 *         <li>3 levels: average of 77ns per lock()/unlock()
149 *         <li>4 levels: average of 99ns per lock()/unlock()
150 *         <li>5 levels: average of 103ns per lock()/unlock()
151 *         <li>10 levels: average of 184ns per lock()/unlock()
152 *         <li>20 levels: average of 393ns per lock()/unlock()
153 *       </ul>
154 * </ul>
155 *
156 * <p>As such, the CycleDetectingLockFactory may not be suitable for performance-critical
157 * applications which involve tightly-looped or deeply-nested locking algorithms.
158 *
159 * @author Darick Tong
160 * @since 13.0
161 */
162@Beta
163@CanIgnoreReturnValue // TODO(cpovirk): Consider being more strict.
164@GwtIncompatible
165public class CycleDetectingLockFactory {
166
167  /**
168   * Encapsulates the action to be taken when a potential deadlock is encountered. Clients can use
169   * one of the predefined {@link Policies} or specify a custom implementation. Implementations must
170   * be thread-safe.
171   *
172   * @since 13.0
173   */
174  @Beta
175  public interface Policy {
176
177    /**
178     * Called when a potential deadlock is encountered. Implementations can throw the given {@code
179     * 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 {@code
198     * PotentialDeadlockException} indicating the potential deadlock, which includes stack traces
199     * 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 {@link
210     * 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  /** Creates a new factory with the specified policy. */
235  public static CycleDetectingLockFactory newInstance(Policy policy) {
236    return new CycleDetectingLockFactory(policy);
237  }
238
239  /** Equivalent to {@code newReentrantLock(lockName, false)}. */
240  public ReentrantLock newReentrantLock(String lockName) {
241    return newReentrantLock(lockName, false);
242  }
243
244  /**
245   * Creates a {@link ReentrantLock} with the given fairness policy. The {@code lockName} is used in
246   * the warning or exception output to help identify the locks involved in the detected deadlock.
247   */
248  public ReentrantLock newReentrantLock(String lockName, boolean fair) {
249    return policy == Policies.DISABLED
250        ? new ReentrantLock(fair)
251        : new CycleDetectingReentrantLock(new LockGraphNode(lockName), fair);
252  }
253
254  /** Equivalent to {@code newReentrantReadWriteLock(lockName, false)}. */
255  public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName) {
256    return newReentrantReadWriteLock(lockName, false);
257  }
258
259  /**
260   * Creates a {@link ReentrantReadWriteLock} with the given fairness policy. The {@code lockName}
261   * is used in the warning or exception output to help identify the locks involved in the detected
262   * deadlock.
263   */
264  public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName, boolean fair) {
265    return policy == Policies.DISABLED
266        ? new ReentrantReadWriteLock(fair)
267        : new CycleDetectingReentrantReadWriteLock(new LockGraphNode(lockName), fair);
268  }
269
270  // A static mapping from an Enum type to its set of LockGraphNodes.
271  private static final ConcurrentMap<Class<? extends Enum>, Map<? extends Enum, LockGraphNode>>
272      lockGraphNodesPerType = new MapMaker().weakKeys().makeMap();
273
274  /** Creates a {@code CycleDetectingLockFactory.WithExplicitOrdering<E>}. */
275  public static <E extends Enum<E>> WithExplicitOrdering<E> newInstanceWithExplicitOrdering(
276      Class<E> enumClass, Policy policy) {
277    // createNodes maps each enumClass to a Map with the corresponding enum key
278    // type.
279    checkNotNull(enumClass);
280    checkNotNull(policy);
281    @SuppressWarnings("unchecked")
282    Map<E, LockGraphNode> lockGraphNodes = (Map<E, LockGraphNode>) getOrCreateNodes(enumClass);
283    return new WithExplicitOrdering<E>(policy, lockGraphNodes);
284  }
285
286  private static Map<? extends Enum, LockGraphNode> getOrCreateNodes(Class<? extends Enum> clazz) {
287    Map<? extends Enum, LockGraphNode> existing = lockGraphNodesPerType.get(clazz);
288    if (existing != null) {
289      return existing;
290    }
291    Map<? extends Enum, LockGraphNode> created = createNodes(clazz);
292    existing = 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    final 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  @Beta
393  public static final class WithExplicitOrdering<E extends Enum<E>>
394      extends CycleDetectingLockFactory {
395
396    private final Map<E, LockGraphNode> lockGraphNodes;
397
398    @VisibleForTesting
399    WithExplicitOrdering(Policy policy, Map<E, LockGraphNode> lockGraphNodes) {
400      super(policy);
401      this.lockGraphNodes = lockGraphNodes;
402    }
403
404    /** Equivalent to {@code newReentrantLock(rank, false)}. */
405    public ReentrantLock newReentrantLock(E rank) {
406      return newReentrantLock(rank, false);
407    }
408
409    /**
410     * Creates a {@link ReentrantLock} with the given fairness policy and rank. The values returned
411     * by {@link Enum#getDeclaringClass()} and {@link Enum#name()} are used to describe the lock in
412     * warning or exception output.
413     *
414     * @throws IllegalStateException If the factory has already created a {@code Lock} with the
415     *     specified rank.
416     */
417    public ReentrantLock newReentrantLock(E rank, boolean fair) {
418      return policy == Policies.DISABLED
419          ? new ReentrantLock(fair)
420          : new CycleDetectingReentrantLock(lockGraphNodes.get(rank), fair);
421    }
422
423    /** Equivalent to {@code newReentrantReadWriteLock(rank, false)}. */
424    public ReentrantReadWriteLock newReentrantReadWriteLock(E rank) {
425      return newReentrantReadWriteLock(rank, false);
426    }
427
428    /**
429     * Creates a {@link ReentrantReadWriteLock} with the given fairness policy and rank. The values
430     * returned by {@link Enum#getDeclaringClass()} and {@link Enum#name()} are used to describe the
431     * lock in warning or exception output.
432     *
433     * @throws IllegalStateException If the factory has already created a {@code Lock} with the
434     *     specified rank.
435     */
436    public ReentrantReadWriteLock newReentrantReadWriteLock(E rank, boolean fair) {
437      return policy == Policies.DISABLED
438          ? new ReentrantReadWriteLock(fair)
439          : new CycleDetectingReentrantReadWriteLock(lockGraphNodes.get(rank), fair);
440    }
441  }
442
443  //////// Implementation /////////
444
445  private static final Logger logger = Logger.getLogger(CycleDetectingLockFactory.class.getName());
446
447  final Policy policy;
448
449  private CycleDetectingLockFactory(Policy policy) {
450    this.policy = checkNotNull(policy);
451  }
452
453  /**
454   * Tracks the currently acquired locks for each Thread, kept up to date by calls to {@link
455   * #aboutToAcquire(CycleDetectingLock)} and {@link #lockStateChanged(CycleDetectingLock)}.
456   */
457  // This is logically a Set, but an ArrayList is used to minimize the amount
458  // of allocation done on lock()/unlock().
459  private static final ThreadLocal<ArrayList<LockGraphNode>> acquiredLocks =
460      new ThreadLocal<ArrayList<LockGraphNode>>() {
461        @Override
462        protected ArrayList<LockGraphNode> initialValue() {
463          return Lists.<LockGraphNode>newArrayListWithCapacity(3);
464        }
465      };
466
467  /**
468   * A Throwable used to record a stack trace that illustrates an example of a specific lock
469   * acquisition ordering. The top of the stack trace is truncated such that it starts with the
470   * acquisition of the lock in question, e.g.
471   *
472   * <pre>
473   * com...ExampleStackTrace: LockB -&gt; LockC
474   *   at com...CycleDetectingReentrantLock.lock(CycleDetectingLockFactory.java:443)
475   *   at ...
476   *   at ...
477   *   at com...MyClass.someMethodThatAcquiresLockB(MyClass.java:123)
478   * </pre>
479   */
480  private static class ExampleStackTrace extends IllegalStateException {
481
482    static final StackTraceElement[] EMPTY_STACK_TRACE = new StackTraceElement[0];
483
484    static final ImmutableSet<String> EXCLUDED_CLASS_NAMES =
485        ImmutableSet.of(
486            CycleDetectingLockFactory.class.getName(),
487            ExampleStackTrace.class.getName(),
488            LockGraphNode.class.getName());
489
490    ExampleStackTrace(LockGraphNode node1, LockGraphNode node2) {
491      super(node1.getLockName() + " -> " + node2.getLockName());
492      StackTraceElement[] origStackTrace = getStackTrace();
493      for (int i = 0, n = origStackTrace.length; i < n; i++) {
494        if (WithExplicitOrdering.class.getName().equals(origStackTrace[i].getClassName())) {
495          // For pre-populated disallowedPriorLocks edges, omit the stack trace.
496          setStackTrace(EMPTY_STACK_TRACE);
497          break;
498        }
499        if (!EXCLUDED_CLASS_NAMES.contains(origStackTrace[i].getClassName())) {
500          setStackTrace(Arrays.copyOfRange(origStackTrace, i, n));
501          break;
502        }
503      }
504    }
505  }
506
507  /**
508   * Represents a detected cycle in lock acquisition ordering. The exception includes a causal chain
509   * of {@code ExampleStackTrace} instances to illustrate the cycle, e.g.
510   *
511   * <pre>
512   * com....PotentialDeadlockException: Potential Deadlock from LockC -&gt; ReadWriteA
513   *   at ...
514   *   at ...
515   * Caused by: com...ExampleStackTrace: LockB -&gt; LockC
516   *   at ...
517   *   at ...
518   * Caused by: com...ExampleStackTrace: ReadWriteA -&gt; LockB
519   *   at ...
520   *   at ...
521   * </pre>
522   *
523   * <p>Instances are logged for the {@code Policies.WARN}, and thrown for {@code Policies.THROW}.
524   *
525   * @since 13.0
526   */
527  @Beta
528  public static final class PotentialDeadlockException extends ExampleStackTrace {
529
530    private final ExampleStackTrace conflictingStackTrace;
531
532    private PotentialDeadlockException(
533        LockGraphNode node1, LockGraphNode node2, ExampleStackTrace conflictingStackTrace) {
534      super(node1, node2);
535      this.conflictingStackTrace = conflictingStackTrace;
536      initCause(conflictingStackTrace);
537    }
538
539    public ExampleStackTrace getConflictingStackTrace() {
540      return conflictingStackTrace;
541    }
542
543    /**
544     * Appends the chain of messages from the {@code conflictingStackTrace} to the original {@code
545     * message}.
546     */
547    @Override
548    public String getMessage() {
549      StringBuilder message = new StringBuilder(super.getMessage());
550      for (Throwable t = conflictingStackTrace; t != null; t = t.getCause()) {
551        message.append(", ").append(t.getMessage());
552      }
553      return message.toString();
554    }
555  }
556
557  /**
558   * Internal Lock implementations implement the {@code CycleDetectingLock} interface, allowing the
559   * detection logic to treat all locks in the same manner.
560   */
561  private interface CycleDetectingLock {
562
563    /** @return the {@link LockGraphNode} associated with this lock. */
564    LockGraphNode getLockGraphNode();
565
566    /** @return {@code true} if the current thread has acquired this lock. */
567    boolean isAcquiredByCurrentThread();
568  }
569
570  /**
571   * A {@code LockGraphNode} associated with each lock instance keeps track of the directed edges in
572   * the lock acquisition graph.
573   */
574  private static class LockGraphNode {
575
576    /**
577     * The map tracking the locks that are known to be acquired before this lock, each associated
578     * with an example stack trace. Locks are weakly keyed to allow proper garbage collection when
579     * they are no longer referenced.
580     */
581    final Map<LockGraphNode, ExampleStackTrace> allowedPriorLocks =
582        new MapMaker().weakKeys().makeMap();
583
584    /**
585     * The map tracking lock nodes that can cause a lock acquisition cycle if acquired before this
586     * node.
587     */
588    final Map<LockGraphNode, PotentialDeadlockException> disallowedPriorLocks =
589        new MapMaker().weakKeys().makeMap();
590
591    final String lockName;
592
593    LockGraphNode(String lockName) {
594      this.lockName = Preconditions.checkNotNull(lockName);
595    }
596
597    String getLockName() {
598      return lockName;
599    }
600
601    void checkAcquiredLocks(Policy policy, List<LockGraphNode> acquiredLocks) {
602      for (int i = 0, size = acquiredLocks.size(); i < size; i++) {
603        checkAcquiredLock(policy, acquiredLocks.get(i));
604      }
605    }
606
607    /**
608     * Checks the acquisition-ordering between {@code this}, which is about to be acquired, and the
609     * specified {@code acquiredLock}.
610     *
611     * <p>When this method returns, the {@code acquiredLock} should be in either the {@code
612     * preAcquireLocks} map, for the case in which it is safe to acquire {@code this} after the
613     * {@code acquiredLock}, or in the {@code disallowedPriorLocks} map, in which case it is not
614     * safe.
615     */
616    void checkAcquiredLock(Policy policy, LockGraphNode acquiredLock) {
617      // checkAcquiredLock() should never be invoked by a lock that has already
618      // been acquired. For unordered locks, aboutToAcquire() ensures this by
619      // checking isAcquiredByCurrentThread(). For ordered locks, however, this
620      // can happen because multiple locks may share the same LockGraphNode. In
621      // this situation, throw an IllegalStateException as defined by contract
622      // described in the documentation of WithExplicitOrdering.
623      Preconditions.checkState(
624          this != acquiredLock,
625          "Attempted to acquire multiple locks with the same rank %s",
626          acquiredLock.getLockName());
627
628      if (allowedPriorLocks.containsKey(acquiredLock)) {
629        // The acquisition ordering from "acquiredLock" to "this" has already
630        // been verified as safe. In a properly written application, this is
631        // the common case.
632        return;
633      }
634      PotentialDeadlockException previousDeadlockException = disallowedPriorLocks.get(acquiredLock);
635      if (previousDeadlockException != null) {
636        // Previously determined to be an unsafe lock acquisition.
637        // Create a new PotentialDeadlockException with the same causal chain
638        // (the example cycle) as that of the cached exception.
639        PotentialDeadlockException exception =
640            new PotentialDeadlockException(
641                acquiredLock, this, previousDeadlockException.getConflictingStackTrace());
642        policy.handlePotentialDeadlock(exception);
643        return;
644      }
645      // Otherwise, it's the first time seeing this lock relationship. Look for
646      // a path from the acquiredLock to this.
647      Set<LockGraphNode> seen = Sets.newIdentityHashSet();
648      ExampleStackTrace path = acquiredLock.findPathTo(this, seen);
649
650      if (path == null) {
651        // this can be safely acquired after the acquiredLock.
652        //
653        // Note that there is a race condition here which can result in missing
654        // a cyclic edge: it's possible for two threads to simultaneous find
655        // "safe" edges which together form a cycle. Preventing this race
656        // condition efficiently without _introducing_ deadlock is probably
657        // tricky. For now, just accept the race condition---missing a warning
658        // now and then is still better than having no deadlock detection.
659        allowedPriorLocks.put(acquiredLock, new ExampleStackTrace(acquiredLock, this));
660      } else {
661        // Unsafe acquisition order detected. Create and cache a
662        // PotentialDeadlockException.
663        PotentialDeadlockException exception =
664            new PotentialDeadlockException(acquiredLock, this, path);
665        disallowedPriorLocks.put(acquiredLock, exception);
666        policy.handlePotentialDeadlock(exception);
667      }
668    }
669
670    /**
671     * Performs a depth-first traversal of the graph edges defined by each node's {@code
672     * allowedPriorLocks} to find a path between {@code this} and the specified {@code lock}.
673     *
674     * @return If a path was found, a chained {@link ExampleStackTrace} illustrating the path to the
675     *     {@code lock}, or {@code null} if no path was found.
676     */
677    private @Nullable ExampleStackTrace findPathTo(LockGraphNode node, Set<LockGraphNode> seen) {
678      if (!seen.add(this)) {
679        return null; // Already traversed this node.
680      }
681      ExampleStackTrace found = allowedPriorLocks.get(node);
682      if (found != null) {
683        return found; // Found a path ending at the node!
684      }
685      // Recurse the edges.
686      for (Entry<LockGraphNode, ExampleStackTrace> entry : allowedPriorLocks.entrySet()) {
687        LockGraphNode preAcquiredLock = entry.getKey();
688        found = preAcquiredLock.findPathTo(node, seen);
689        if (found != null) {
690          // One of this node's allowedPriorLocks found a path. Prepend an
691          // ExampleStackTrace(preAcquiredLock, this) to the returned chain of
692          // ExampleStackTraces.
693          ExampleStackTrace path = new ExampleStackTrace(preAcquiredLock, this);
694          path.setStackTrace(entry.getValue().getStackTrace());
695          path.initCause(found);
696          return path;
697        }
698      }
699      return null;
700    }
701  }
702
703  /**
704   * CycleDetectingLock implementations must call this method before attempting to acquire the lock.
705   */
706  private void aboutToAcquire(CycleDetectingLock lock) {
707    if (!lock.isAcquiredByCurrentThread()) {
708      ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
709      LockGraphNode node = lock.getLockGraphNode();
710      node.checkAcquiredLocks(policy, acquiredLockList);
711      acquiredLockList.add(node);
712    }
713  }
714
715  /**
716   * CycleDetectingLock implementations must call this method in a {@code finally} clause after any
717   * attempt to change the lock state, including both lock and unlock attempts. Failure to do so can
718   * result in corrupting the acquireLocks set.
719   */
720  private static void lockStateChanged(CycleDetectingLock lock) {
721    if (!lock.isAcquiredByCurrentThread()) {
722      ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
723      LockGraphNode node = lock.getLockGraphNode();
724      // Iterate in reverse because locks are usually locked/unlocked in a
725      // LIFO order.
726      for (int i = acquiredLockList.size() - 1; i >= 0; i--) {
727        if (acquiredLockList.get(i) == node) {
728          acquiredLockList.remove(i);
729          break;
730        }
731      }
732    }
733  }
734
735  final class CycleDetectingReentrantLock extends ReentrantLock implements CycleDetectingLock {
736
737    private final LockGraphNode lockGraphNode;
738
739    private CycleDetectingReentrantLock(LockGraphNode lockGraphNode, boolean fair) {
740      super(fair);
741      this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
742    }
743
744    ///// CycleDetectingLock methods. /////
745
746    @Override
747    public LockGraphNode getLockGraphNode() {
748      return lockGraphNode;
749    }
750
751    @Override
752    public boolean isAcquiredByCurrentThread() {
753      return isHeldByCurrentThread();
754    }
755
756    ///// Overridden ReentrantLock methods. /////
757
758    @Override
759    public void lock() {
760      aboutToAcquire(this);
761      try {
762        super.lock();
763      } finally {
764        lockStateChanged(this);
765      }
766    }
767
768    @Override
769    public void lockInterruptibly() throws InterruptedException {
770      aboutToAcquire(this);
771      try {
772        super.lockInterruptibly();
773      } finally {
774        lockStateChanged(this);
775      }
776    }
777
778    @Override
779    public boolean tryLock() {
780      aboutToAcquire(this);
781      try {
782        return super.tryLock();
783      } finally {
784        lockStateChanged(this);
785      }
786    }
787
788    @Override
789    public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
790      aboutToAcquire(this);
791      try {
792        return super.tryLock(timeout, unit);
793      } finally {
794        lockStateChanged(this);
795      }
796    }
797
798    @Override
799    public void unlock() {
800      try {
801        super.unlock();
802      } finally {
803        lockStateChanged(this);
804      }
805    }
806  }
807
808  final class CycleDetectingReentrantReadWriteLock extends ReentrantReadWriteLock
809      implements CycleDetectingLock {
810
811    // These ReadLock/WriteLock implementations shadow those in the
812    // ReentrantReadWriteLock superclass. They are simply wrappers around the
813    // internal Sync object, so this is safe since the shadowed locks are never
814    // exposed or used.
815    private final CycleDetectingReentrantReadLock readLock;
816    private final CycleDetectingReentrantWriteLock writeLock;
817
818    private final LockGraphNode lockGraphNode;
819
820    private CycleDetectingReentrantReadWriteLock(LockGraphNode lockGraphNode, boolean fair) {
821      super(fair);
822      this.readLock = new CycleDetectingReentrantReadLock(this);
823      this.writeLock = new CycleDetectingReentrantWriteLock(this);
824      this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
825    }
826
827    ///// Overridden ReentrantReadWriteLock methods. /////
828
829    @Override
830    public ReadLock readLock() {
831      return readLock;
832    }
833
834    @Override
835    public WriteLock writeLock() {
836      return writeLock;
837    }
838
839    ///// CycleDetectingLock methods. /////
840
841    @Override
842    public LockGraphNode getLockGraphNode() {
843      return lockGraphNode;
844    }
845
846    @Override
847    public boolean isAcquiredByCurrentThread() {
848      return isWriteLockedByCurrentThread() || getReadHoldCount() > 0;
849    }
850  }
851
852  private class CycleDetectingReentrantReadLock extends ReentrantReadWriteLock.ReadLock {
853
854    @Weak final CycleDetectingReentrantReadWriteLock readWriteLock;
855
856    CycleDetectingReentrantReadLock(CycleDetectingReentrantReadWriteLock readWriteLock) {
857      super(readWriteLock);
858      this.readWriteLock = readWriteLock;
859    }
860
861    @Override
862    public void lock() {
863      aboutToAcquire(readWriteLock);
864      try {
865        super.lock();
866      } finally {
867        lockStateChanged(readWriteLock);
868      }
869    }
870
871    @Override
872    public void lockInterruptibly() throws InterruptedException {
873      aboutToAcquire(readWriteLock);
874      try {
875        super.lockInterruptibly();
876      } finally {
877        lockStateChanged(readWriteLock);
878      }
879    }
880
881    @Override
882    public boolean tryLock() {
883      aboutToAcquire(readWriteLock);
884      try {
885        return super.tryLock();
886      } finally {
887        lockStateChanged(readWriteLock);
888      }
889    }
890
891    @Override
892    public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
893      aboutToAcquire(readWriteLock);
894      try {
895        return super.tryLock(timeout, unit);
896      } finally {
897        lockStateChanged(readWriteLock);
898      }
899    }
900
901    @Override
902    public void unlock() {
903      try {
904        super.unlock();
905      } finally {
906        lockStateChanged(readWriteLock);
907      }
908    }
909  }
910
911  private class CycleDetectingReentrantWriteLock extends ReentrantReadWriteLock.WriteLock {
912
913    @Weak final CycleDetectingReentrantReadWriteLock readWriteLock;
914
915    CycleDetectingReentrantWriteLock(CycleDetectingReentrantReadWriteLock readWriteLock) {
916      super(readWriteLock);
917      this.readWriteLock = readWriteLock;
918    }
919
920    @Override
921    public void lock() {
922      aboutToAcquire(readWriteLock);
923      try {
924        super.lock();
925      } finally {
926        lockStateChanged(readWriteLock);
927      }
928    }
929
930    @Override
931    public void lockInterruptibly() throws InterruptedException {
932      aboutToAcquire(readWriteLock);
933      try {
934        super.lockInterruptibly();
935      } finally {
936        lockStateChanged(readWriteLock);
937      }
938    }
939
940    @Override
941    public boolean tryLock() {
942      aboutToAcquire(readWriteLock);
943      try {
944        return super.tryLock();
945      } finally {
946        lockStateChanged(readWriteLock);
947      }
948    }
949
950    @Override
951    public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
952      aboutToAcquire(readWriteLock);
953      try {
954        return super.tryLock(timeout, unit);
955      } finally {
956        lockStateChanged(readWriteLock);
957      }
958    }
959
960    @Override
961    public void unlock() {
962      try {
963        super.unlock();
964      } finally {
965        lockStateChanged(readWriteLock);
966      }
967    }
968  }
969}