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 static com.google.common.base.Objects.firstNonNull;
020import static com.google.common.base.Preconditions.checkNotNull;
021
022import com.google.common.annotations.Beta;
023import com.google.common.annotations.VisibleForTesting;
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;
030
031import java.util.ArrayList;
032import java.util.Arrays;
033import java.util.Collections;
034import java.util.EnumMap;
035import java.util.List;
036import java.util.Map;
037import java.util.Set;
038import java.util.concurrent.ConcurrentMap;
039import java.util.concurrent.TimeUnit;
040import java.util.concurrent.locks.ReentrantLock;
041import java.util.concurrent.locks.ReentrantReadWriteLock;
042import java.util.logging.Level;
043import java.util.logging.Logger;
044
045import javax.annotation.Nullable;
046import javax.annotation.concurrent.ThreadSafe;
047
048/**
049 * The {@code CycleDetectingLockFactory} creates {@link ReentrantLock} instances and
050 * {@link ReentrantReadWriteLock} instances that detect potential deadlock by checking
051 * for cycles in lock acquisition order.
052 * <p>
053 * Potential deadlocks detected when calling the {@code lock()},
054 * {@code lockInterruptibly()}, or {@code tryLock()} methods will result in the
055 * execution of the {@link Policy} specified when creating the factory. The
056 * currently available policies are:
057 * <ul>
058 * <li>DISABLED
059 * <li>WARN
060 * <li>THROW
061 * </ul>
062 * <p>The locks created by a factory instance will detect lock acquisition cycles
063 * with locks created by other {@code CycleDetectingLockFactory} instances
064 * (except those with {@code Policy.DISABLED}). A lock's behavior when a cycle
065 * is detected, however, is defined by the {@code Policy} of the factory that
066 * created it. This allows detection of cycles across components while
067 * delegating control over lock behavior to individual components.
068 * <p>
069 * Applications are encouraged to use a {@code CycleDetectingLockFactory} to
070 * create any locks for which external/unmanaged code is executed while the lock
071 * is held. (See caveats under <strong>Performance</strong>).
072 * <p>
073 * <strong>Cycle Detection</strong>
074 * <p>
075 * Deadlocks can arise when locks are acquired in an order that forms a cycle.
076 * In a simple example involving two locks and two threads, deadlock occurs
077 * when one thread acquires Lock A, and then Lock B, while another thread
078 * acquires Lock B, and then Lock A:
079 * <pre>
080 * Thread1: acquire(LockA) --X acquire(LockB)
081 * Thread2: acquire(LockB) --X acquire(LockA)
082 * </pre>
083 * <p>Neither thread will progress because each is waiting for the other. In more
084 * complex applications, cycles can arise from interactions among more than 2
085 * locks:
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 * <p>The implementation detects cycles by constructing a directed graph in which
093 * each lock represents a node and each edge represents an acquisition ordering
094 * between two locks.
095 * <ul>
096 * <li>Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired
097 *   locks when the Thread acquires its first hold (and releases its last
098 *   remaining hold).
099 * <li>Before the lock is acquired, the lock is checked against the current set
100 *   of acquired locks---to each of the acquired locks, an edge from the
101 *   soon-to-be-acquired lock is either verified or created.
102 * <li>If a new edge needs to be created, the outgoing edges of the acquired
103 *   locks are traversed to check for a cycle that reaches the lock to be
104 *   acquired. If no cycle is detected, a new "safe" edge is created.
105 * <li>If a cycle is detected, an "unsafe" (cyclic) edge is created to represent
106 *   a potential deadlock situation, and the appropriate Policy is executed.
107 * </ul>
108 * <p>Note that detection of potential deadlock does not necessarily indicate that
109 * deadlock will happen, as it is possible that higher level application logic
110 * prevents the cyclic lock acquisition from occurring. One example of a false
111 * positive is:
112 * <pre>
113 * LockA -&gt; LockB -&gt; LockC
114 * LockA -&gt; LockC -&gt; LockB
115 * </pre>
116 *
117 * <strong>ReadWriteLocks</strong>
118 * <p>
119 * While {@code ReadWriteLock} instances have different properties and can form cycles
120 * without potential deadlock, this class treats {@code ReadWriteLock} instances as
121 * equivalent to traditional exclusive locks. Although this increases the false
122 * positives that the locks detect (i.e. cycles that will not actually result in
123 * deadlock), it simplifies the algorithm and implementation considerably. The
124 * assumption is that a user of this factory wishes to eliminate any cyclic
125 * acquisition ordering.
126 * <p>
127 * <strong>Explicit Lock Acquisition Ordering</strong>
128 * <p>
129 * The {@link CycleDetectingLockFactory.WithExplicitOrdering} class can be used
130 * to enforce an application-specific ordering in addition to performing general
131 * cycle detection.
132 * <p>
133 * <strong>Garbage Collection</strong>
134 * <p>
135 * In order to allow proper garbage collection of unused locks, the edges of
136 * the lock graph are weak references.
137 * <p>
138 * <strong>Performance</strong>
139 * <p>
140 * The extra bookkeeping done by cycle detecting locks comes at some cost to
141 * performance. Benchmarks (as of December 2011) show that:
142 *
143 * <ul>
144 * <li>for an unnested {@code lock()} and {@code unlock()}, a cycle detecting
145 *   lock takes 38ns as opposed to the 24ns taken by a plain lock.
146 * <li>for nested locking, the cost increases with the depth of the nesting:
147 *   <ul>
148 *   <li> 2 levels: average of 64ns per lock()/unlock()
149 *   <li> 3 levels: average of 77ns per lock()/unlock()
150 *   <li> 4 levels: average of 99ns per lock()/unlock()
151 *   <li> 5 levels: average of 103ns per lock()/unlock()
152 *   <li>10 levels: average of 184ns per lock()/unlock()
153 *   <li>20 levels: average of 393ns per lock()/unlock()
154 *   </ul>
155 * </ul>
156 *
157 * <p>As such, the CycleDetectingLockFactory may not be suitable for
158 * performance-critical applications which involve tightly-looped or
159 * deeply-nested locking algorithms.
160 *
161 * @author Darick Tong
162 * @since 13.0
163 */
164@Beta
165@ThreadSafe
166public class CycleDetectingLockFactory {
167
168  /**
169   * Encapsulates the action to be taken when a potential deadlock is
170   * encountered. Clients can use one of the predefined {@link Policies} or
171   * specify a custom implementation. Implementations must be thread-safe.
172   *
173   * @since 13.0
174   */
175  @Beta
176  @ThreadSafe
177  public interface Policy {
178
179    /**
180     * Called when a potential deadlock is encountered. Implementations can
181     * throw the given {@code exception} and/or execute other desired logic.
182     * <p>
183     * Note that the method will be called even upon an invocation of
184     * {@code tryLock()}. Although {@code tryLock()} technically recovers from
185     * deadlock by eventually timing out, this behavior is chosen based on the
186     * assumption that it is the application's wish to prohibit any cyclical
187     * lock acquisitions.
188     */
189    void handlePotentialDeadlock(PotentialDeadlockException exception);
190  }
191
192  /**
193   * Pre-defined {@link Policy} implementations.
194   *
195   * @since 13.0
196   */
197  @Beta
198  public enum Policies implements Policy {
199    /**
200     * When potential deadlock is detected, this policy results in the throwing
201     * of the {@code PotentialDeadlockException} indicating the potential
202     * deadlock, which includes stack traces illustrating the cycle in lock
203     * acquisition order.
204     */
205    THROW {
206      @Override
207      public void handlePotentialDeadlock(PotentialDeadlockException e) {
208        throw e;
209      }
210    },
211
212    /**
213     * When potential deadlock is detected, this policy results in the logging
214     * of a {@link Level#SEVERE} message indicating the potential deadlock,
215     * which includes stack traces illustrating the cycle in lock acquisition
216     * order.
217     */
218    WARN {
219      @Override
220      public void handlePotentialDeadlock(PotentialDeadlockException e) {
221        logger.log(Level.SEVERE, "Detected potential deadlock", e);
222      }
223    },
224
225    /**
226     * Disables cycle detection. This option causes the factory to return
227     * unmodified lock implementations provided by the JDK, and is provided to
228     * allow applications to easily parameterize when cycle detection is
229     * enabled.
230     * <p>
231     * Note that locks created by a factory with this policy will <em>not</em>
232     * participate the cycle detection performed by locks created by other
233     * factories.
234     */
235    DISABLED {
236      @Override
237      public void handlePotentialDeadlock(PotentialDeadlockException e) {
238      }
239    };
240  }
241
242  /**
243   * Creates a new factory with the specified policy.
244   */
245  public static CycleDetectingLockFactory newInstance(Policy policy) {
246    return new CycleDetectingLockFactory(policy);
247  }
248
249  /**
250   * Equivalent to {@code newReentrantLock(lockName, false)}.
251   */
252  public ReentrantLock newReentrantLock(String lockName) {
253    return newReentrantLock(lockName, false);
254  }
255
256  /**
257   * Creates a {@link ReentrantLock} with the given fairness policy. The
258   * {@code lockName} is used in the warning or exception output to help
259   * identify the locks involved in the detected deadlock.
260   */
261  public ReentrantLock newReentrantLock(String lockName, boolean fair) {
262    return policy == Policies.DISABLED ? new ReentrantLock(fair)
263        : new CycleDetectingReentrantLock(
264            new LockGraphNode(lockName), fair);
265  }
266
267  /**
268   * Equivalent to {@code newReentrantReadWriteLock(lockName, false)}.
269   */
270  public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName) {
271    return newReentrantReadWriteLock(lockName, false);
272  }
273
274  /**
275   * Creates a {@link ReentrantReadWriteLock} with the given fairness policy.
276   * The {@code lockName} is used in the warning or exception output to help
277   * identify the locks involved in the detected deadlock.
278   */
279  public ReentrantReadWriteLock newReentrantReadWriteLock(
280      String lockName, boolean fair) {
281    return policy == Policies.DISABLED ? new ReentrantReadWriteLock(fair)
282        : new CycleDetectingReentrantReadWriteLock(
283            new LockGraphNode(lockName), fair);
284  }
285
286  // A static mapping from an Enum type to its set of LockGraphNodes.
287  private static final ConcurrentMap<Class<? extends Enum>,
288      Map<? extends Enum, LockGraphNode>> lockGraphNodesPerType =
289          new MapMaker().weakKeys().makeMap();
290
291  /**
292   * Creates a {@code CycleDetectingLockFactory.WithExplicitOrdering<E>}.
293   */
294  public static <E extends Enum<E>> WithExplicitOrdering<E>
295      newInstanceWithExplicitOrdering(Class<E> enumClass, Policy policy) {
296    // createNodes maps each enumClass to a Map with the corresponding enum key
297    // type.
298    checkNotNull(enumClass);
299    checkNotNull(policy);
300    @SuppressWarnings("unchecked")
301    Map<E, LockGraphNode> lockGraphNodes =
302        (Map<E, LockGraphNode>) getOrCreateNodes(enumClass);
303    return new WithExplicitOrdering<E>(policy, lockGraphNodes);
304  }
305
306  private static Map<? extends Enum, LockGraphNode> getOrCreateNodes(
307      Class<? extends Enum> clazz) {
308    Map<? extends Enum, LockGraphNode> existing =
309        lockGraphNodesPerType.get(clazz);
310    if (existing != null) {
311      return existing;
312    }
313    Map<? extends Enum, LockGraphNode> created = createNodes(clazz);
314    existing = lockGraphNodesPerType.putIfAbsent(clazz, created);
315    return firstNonNull(existing, created);
316  }
317
318  /**
319   * For a given Enum type, creates an immutable map from each of the Enum's
320   * values to a corresponding LockGraphNode, with the
321   * {@code allowedPriorLocks} and {@code disallowedPriorLocks} prepopulated
322   * with nodes according to the natural ordering of the associated Enum values.
323   */
324  @VisibleForTesting
325  static <E extends Enum<E>> Map<E, LockGraphNode> createNodes(Class<E> clazz) {
326    EnumMap<E, LockGraphNode> map = Maps.newEnumMap(clazz);
327    E[] keys = clazz.getEnumConstants();
328    final int numKeys = keys.length;
329    ArrayList<LockGraphNode> nodes =
330        Lists.newArrayListWithCapacity(numKeys);
331    // Create a LockGraphNode for each enum value.
332    for (E key : keys) {
333      LockGraphNode node = new LockGraphNode(getLockName(key));
334      nodes.add(node);
335      map.put(key, node);
336    }
337    // Pre-populate all allowedPriorLocks with nodes of smaller ordinal.
338    for (int i = 1; i < numKeys; i++) {
339      nodes.get(i).checkAcquiredLocks(Policies.THROW, nodes.subList(0, i));
340    }
341    // Pre-populate all disallowedPriorLocks with nodes of larger ordinal.
342    for (int i = 0; i < numKeys - 1; i++) {
343      nodes.get(i).checkAcquiredLocks(
344          Policies.DISABLED, nodes.subList(i + 1, numKeys));
345    }
346    return Collections.unmodifiableMap(map);
347  }
348
349  /**
350   * For the given Enum value {@code rank}, returns the value's
351   * {@code "EnumClass.name"}, which is used in exception and warning
352   * output.
353   */
354  private static String getLockName(Enum<?> rank) {
355    return rank.getDeclaringClass().getSimpleName() + "." + rank.name();
356  }
357
358  /**
359   * <p>A {@code CycleDetectingLockFactory.WithExplicitOrdering} provides the
360   * additional enforcement of an application-specified ordering of lock
361   * acquisitions. The application defines the allowed ordering with an
362   * {@code Enum} whose values each correspond to a lock type. The order in
363   * which the values are declared dictates the allowed order of lock
364   * acquisition. In other words, locks corresponding to smaller values of
365   * {@link Enum#ordinal()} should only be acquired before locks with larger
366   * ordinals. Example:
367   *
368   * <pre>   {@code
369   * enum MyLockOrder {
370   *   FIRST, SECOND, THIRD;
371   * }
372   *
373   * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory =
374   *   CycleDetectingLockFactory.newInstanceWithExplicitOrdering(Policies.THROW);
375   *
376   * Lock lock1 = factory.newReentrantLock(MyLockOrder.FIRST);
377   * Lock lock2 = factory.newReentrantLock(MyLockOrder.SECOND);
378   * Lock lock3 = factory.newReentrantLock(MyLockOrder.THIRD);
379   *
380   * lock1.lock();
381   * lock3.lock();
382   * lock2.lock();  // will throw an IllegalStateException}</pre>
383   *
384   * <p>As with all locks created by instances of {@code CycleDetectingLockFactory}
385   * explicitly ordered locks participate in general cycle detection with all
386   * other cycle detecting locks, and a lock's behavior when detecting a cyclic
387   * lock acquisition is defined by the {@code Policy} of the factory that
388   * created it.
389   *
390   * <p>Note, however, that although multiple locks can be created for a given Enum
391   * value, whether it be through separate factory instances or through multiple
392   * calls to the same factory, attempting to acquire multiple locks with the
393   * same Enum value (within the same thread) will result in an
394   * IllegalStateException regardless of the factory's policy. For example:
395   *
396   * <pre>   {@code
397   * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory1 =
398   *   CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
399   * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory2 =
400   *   CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
401   *
402   * Lock lockA = factory1.newReentrantLock(MyLockOrder.FIRST);
403   * Lock lockB = factory1.newReentrantLock(MyLockOrder.FIRST);
404   * Lock lockC = factory2.newReentrantLock(MyLockOrder.FIRST);
405   *
406   * lockA.lock();
407   *
408   * lockB.lock();  // will throw an IllegalStateException
409   * lockC.lock();  // will throw an IllegalStateException
410   *
411   * lockA.lock();  // reentrant acquisition is okay}</pre>
412   *
413   * <p>It is the responsibility of the application to ensure that multiple lock
414   * instances with the same rank are never acquired in the same thread.
415   *
416   * @param <E> The Enum type representing the explicit lock ordering.
417   * @since 13.0
418   */
419  @Beta
420  public static final class WithExplicitOrdering<E extends Enum<E>>
421      extends CycleDetectingLockFactory {
422
423    private final Map<E, LockGraphNode> lockGraphNodes;
424
425    @VisibleForTesting
426    WithExplicitOrdering(
427        Policy policy, Map<E, LockGraphNode> lockGraphNodes) {
428      super(policy);
429      this.lockGraphNodes = lockGraphNodes;
430    }
431
432    /**
433     * Equivalent to {@code newReentrantLock(rank, false)}.
434     */
435    public ReentrantLock newReentrantLock(E rank) {
436      return newReentrantLock(rank, false);
437    }
438
439    /**
440     * Creates a {@link ReentrantLock} with the given fairness policy and rank.
441     * The values returned by {@link Enum#getDeclaringClass()} and
442     * {@link Enum#name()} are used to describe the lock in warning or
443     * exception output.
444     *
445     * @throws IllegalStateException If the factory has already created a
446     *    {@code Lock} with the specified rank.
447     */
448    public ReentrantLock newReentrantLock(E rank, boolean fair) {
449      return policy == Policies.DISABLED ? new ReentrantLock(fair)
450          : new CycleDetectingReentrantLock(lockGraphNodes.get(rank), fair);
451    }
452
453    /**
454     * Equivalent to {@code newReentrantReadWriteLock(rank, false)}.
455     */
456    public ReentrantReadWriteLock newReentrantReadWriteLock(E rank) {
457      return newReentrantReadWriteLock(rank, false);
458    }
459
460    /**
461     * Creates a {@link ReentrantReadWriteLock} with the given fairness policy
462     * and rank. The values returned by {@link Enum#getDeclaringClass()} and
463     * {@link Enum#name()} are used to describe the lock in warning or exception
464     * output.
465     *
466     * @throws IllegalStateException If the factory has already created a
467     *    {@code Lock} with the specified rank.
468     */
469    public ReentrantReadWriteLock newReentrantReadWriteLock(
470        E rank, boolean fair) {
471      return policy == Policies.DISABLED ? new ReentrantReadWriteLock(fair)
472          : new CycleDetectingReentrantReadWriteLock(
473              lockGraphNodes.get(rank), fair);
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 = checkNotNull(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} instances 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   * <p>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}