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