diff options
Diffstat (limited to 'guava/src/com/google/common/util/concurrent/CycleDetectingLockFactory.java')
| -rw-r--r-- | guava/src/com/google/common/util/concurrent/CycleDetectingLockFactory.java | 1034 |
1 files changed, 1034 insertions, 0 deletions
diff --git a/guava/src/com/google/common/util/concurrent/CycleDetectingLockFactory.java b/guava/src/com/google/common/util/concurrent/CycleDetectingLockFactory.java new file mode 100644 index 0000000..53d19d0 --- /dev/null +++ b/guava/src/com/google/common/util/concurrent/CycleDetectingLockFactory.java @@ -0,0 +1,1034 @@ +/* + * Copyright (C) 2011 The Guava Authors + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.google.common.util.concurrent; + +import com.google.common.annotations.Beta; +import com.google.common.annotations.VisibleForTesting; +import com.google.common.base.Function; +import com.google.common.base.Preconditions; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Lists; +import com.google.common.collect.MapMaker; +import com.google.common.collect.Maps; +import com.google.common.collect.Sets; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.EnumMap; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.concurrent.TimeUnit; +import java.util.concurrent.locks.ReentrantLock; +import java.util.concurrent.locks.ReentrantReadWriteLock; +import java.util.logging.Level; +import java.util.logging.Logger; + +import javax.annotation.Nullable; +import javax.annotation.concurrent.ThreadSafe; + +/** + * The {@code CycleDetectingLockFactory} creates {@link ReentrantLock}s and + * {@link ReentrantReadWriteLock}s that detect potential deadlock by checking + * for cycles in lock acquisition order. + * <p> + * Potential deadlocks detected when calling the {@code lock()}, + * {@code lockInterruptibly()}, or {@code tryLock()} methods will result in the + * execution of the {@link Policy} specified when creating the factory. The + * currently available policies are: + * <ul> + * <li>DISABLED + * <li>WARN + * <li>THROW + * </ul> + * The locks created by a factory instance will detect lock acquisition cycles + * with locks created by other {@code CycleDetectingLockFactory} instances + * (except those with {@code Policy.DISABLED}). A lock's behavior when a cycle + * is detected, however, is defined by the {@code Policy} of the factory that + * created it. This allows detection of cycles across components while + * delegating control over lock behavior to individual components. + * <p> + * Applications are encouraged to use a {@code CycleDetectingLockFactory} to + * create any locks for which external/unmanaged code is executed while the lock + * is held. (See caveats under <strong>Performance</strong>). + * <p> + * <strong>Cycle Detection</strong> + * <p> + * Deadlocks can arise when locks are acquired in an order that forms a cycle. + * In a simple example involving two locks and two threads, deadlock occurs + * when one thread acquires Lock A, and then Lock B, while another thread + * acquires Lock B, and then Lock A: + * <pre> + * Thread1: acquire(LockA) --X acquire(LockB) + * Thread2: acquire(LockB) --X acquire(LockA) + * </pre> + * Neither thread will progress because each is waiting for the other. In more + * complex applications, cycles can arise from interactions among more than 2 + * locks: + * <pre> + * Thread1: acquire(LockA) --X acquire(LockB) + * Thread2: acquire(LockB) --X acquire(LockC) + * ... + * ThreadN: acquire(LockN) --X acquire(LockA) + * </pre> + * The implementation detects cycles by constructing a directed graph in which + * each lock represents a node and each edge represents an acquisition ordering + * between two locks. + * <ul> + * <li>Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired + * locks when the Thread acquires its first hold (and releases its last + * remaining hold). + * <li>Before the lock is acquired, the lock is checked against the current set + * of acquired locks---to each of the acquired locks, an edge from the + * soon-to-be-acquired lock is either verified or created. + * <li>If a new edge needs to be created, the outgoing edges of the acquired + * locks are traversed to check for a cycle that reaches the lock to be + * acquired. If no cycle is detected, a new "safe" edge is created. + * <li>If a cycle is detected, an "unsafe" (cyclic) edge is created to represent + * a potential deadlock situation, and the appropriate Policy is executed. + * </ul> + * Note that detection of potential deadlock does not necessarily indicate that + * deadlock will happen, as it is possible that higher level application logic + * prevents the cyclic lock acquisition from occurring. One example of a false + * positive is: + * <pre> + * LockA -> LockB -> LockC + * LockA -> LockC -> LockB + * </pre> + * + * <strong>ReadWriteLocks</strong> + * <p> + * While {@code ReadWriteLock}s have different properties and can form cycles + * without potential deadlock, this class treats {@code ReadWriteLock}s as + * equivalent to traditional exclusive locks. Although this increases the false + * positives that the locks detect (i.e. cycles that will not actually result in + * deadlock), it simplifies the algorithm and implementation considerably. The + * assumption is that a user of this factory wishes to eliminate any cyclic + * acquisition ordering. + * <p> + * <strong>Explicit Lock Acquisition Ordering</strong> + * <p> + * The {@link CycleDetectingLockFactory.WithExplicitOrdering} class can be used + * to enforce an application-specific ordering in addition to performing general + * cycle detection. + * <p> + * <strong>Garbage Collection</strong> + * <p> + * In order to allow proper garbage collection of unused locks, the edges of + * the lock graph are weak references. + * <p> + * <strong>Performance</strong> + * <p> + * The extra bookkeeping done by cycle detecting locks comes at some cost to + * performance. Benchmarks (as of December 2011) show that: + * + * <ul> + * <li>for an unnested {@code lock()} and {@code unlock()}, a cycle detecting + * lock takes 38ns as opposed to the 24ns taken by a plain lock. + * <li>for nested locking, the cost increases with the depth of the nesting: + * <ul> + * <li> 2 levels: average of 64ns per lock()/unlock() + * <li> 3 levels: average of 77ns per lock()/unlock() + * <li> 4 levels: average of 99ns per lock()/unlock() + * <li> 5 levels: average of 103ns per lock()/unlock() + * <li>10 levels: average of 184ns per lock()/unlock() + * <li>20 levels: average of 393ns per lock()/unlock() + * </ul> + * </ul> + * + * As such, the CycleDetectingLockFactory may not be suitable for + * performance-critical applications which involve tightly-looped or + * deeply-nested locking algorithms. + * + * @author Darick Tong + * @since 13.0 + */ +@Beta +@ThreadSafe +public class CycleDetectingLockFactory { + + /** + * Encapsulates the action to be taken when a potential deadlock is + * encountered. Clients can use one of the predefined {@link Policies} or + * specify a custom implementation. Implementations must be thread-safe. + * + * @since 13.0 + */ + @Beta + @ThreadSafe + public interface Policy { + + /** + * Called when a potential deadlock is encountered. Implementations can + * throw the given {@code exception} and/or execute other desired logic. + * <p> + * Note that the method will be called even upon an invocation of + * {@code tryLock()}. Although {@code tryLock()} technically recovers from + * deadlock by eventually timing out, this behavior is chosen based on the + * assumption that it is the application's wish to prohibit any cyclical + * lock acquisitions. + */ + void handlePotentialDeadlock(PotentialDeadlockException exception); + } + + /** + * Pre-defined {@link Policy} implementations. + * + * @since 13.0 + */ + @Beta + public enum Policies implements Policy { + /** + * When potential deadlock is detected, this policy results in the throwing + * of the {@code PotentialDeadlockException} indicating the potential + * deadlock, which includes stack traces illustrating the cycle in lock + * acquisition order. + */ + THROW { + @Override + public void handlePotentialDeadlock(PotentialDeadlockException e) { + throw e; + } + }, + + /** + * When potential deadlock is detected, this policy results in the logging + * of a {@link Level#SEVERE} message indicating the potential deadlock, + * which includes stack traces illustrating the cycle in lock acquisition + * order. + */ + WARN { + @Override + public void handlePotentialDeadlock(PotentialDeadlockException e) { + logger.log(Level.SEVERE, "Detected potential deadlock", e); + } + }, + + /** + * Disables cycle detection. This option causes the factory to return + * unmodified lock implementations provided by the JDK, and is provided to + * allow applications to easily parameterize when cycle detection is + * enabled. + * <p> + * Note that locks created by a factory with this policy will <em>not</em> + * participate the cycle detection performed by locks created by other + * factories. + */ + DISABLED { + @Override + public void handlePotentialDeadlock(PotentialDeadlockException e) { + } + }; + } + + /** + * Creates a new factory with the specified policy. + */ + public static CycleDetectingLockFactory newInstance(Policy policy) { + return new CycleDetectingLockFactory(policy); + } + + /** + * Equivalent to {@code newReentrantLock(lockName, false)}. + */ + public ReentrantLock newReentrantLock(String lockName) { + return newReentrantLock(lockName, false); + } + + /** + * Creates a {@link ReentrantLock} with the given fairness policy. The + * {@code lockName} is used in the warning or exception output to help + * identify the locks involved in the detected deadlock. + */ + public ReentrantLock newReentrantLock(String lockName, boolean fair) { + return policy == Policies.DISABLED ? new ReentrantLock(fair) + : new CycleDetectingReentrantLock( + new LockGraphNode(lockName), fair); + } + + /** + * Equivalent to {@code newReentrantReadWriteLock(lockName, false)}. + */ + public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName) { + return newReentrantReadWriteLock(lockName, false); + } + + /** + * Creates a {@link ReentrantReadWriteLock} with the given fairness policy. + * The {@code lockName} is used in the warning or exception output to help + * identify the locks involved in the detected deadlock. + */ + public ReentrantReadWriteLock newReentrantReadWriteLock( + String lockName, boolean fair) { + return policy == Policies.DISABLED ? new ReentrantReadWriteLock(fair) + : new CycleDetectingReentrantReadWriteLock( + new LockGraphNode(lockName), fair); + } + + // A static mapping from an Enum type to its set of LockGraphNodes. + private static final Map<Class<? extends Enum>, + Map<? extends Enum, LockGraphNode>> lockGraphNodesPerType = + new MapMaker().weakKeys().makeComputingMap( + new OrderedLockGraphNodesCreator()); + + /** + * Creates a {@code CycleDetectingLockFactory.WithExplicitOrdering<E>}. + */ + public static <E extends Enum<E>> WithExplicitOrdering<E> + newInstanceWithExplicitOrdering(Class<E> enumClass, Policy policy) { + // OrderedLockGraphNodesCreator maps each enumClass to a Map with the + // corresponding enum key type. + @SuppressWarnings("unchecked") + Map<E, LockGraphNode> lockGraphNodes = + (Map<E, LockGraphNode>) lockGraphNodesPerType.get(enumClass); + return new WithExplicitOrdering<E>(policy, lockGraphNodes); + } + + /** + * A {@code CycleDetectingLockFactory.WithExplicitOrdering} provides the + * additional enforcement of an application-specified ordering of lock + * acquisitions. The application defines the allowed ordering with an + * {@code Enum} whose values each correspond to a lock type. The order in + * which the values are declared dictates the allowed order of lock + * acquisition. In other words, locks corresponding to smaller values of + * {@link Enum#ordinal()} should only be acquired before locks with larger + * ordinals. Example: + * + * <pre> {@code + * enum MyLockOrder { + * FIRST, SECOND, THIRD; + * } + * + * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory = + * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(Policies.THROW); + * + * Lock lock1 = factory.newReentrantLock(MyLockOrder.FIRST); + * Lock lock2 = factory.newReentrantLock(MyLockOrder.SECOND); + * Lock lock3 = factory.newReentrantLock(MyLockOrder.THIRD); + * + * lock1.lock(); + * lock3.lock(); + * lock2.lock(); // will throw an IllegalStateException + * }</pre> + * + * As with all locks created by instances of {@code CycleDetectingLockFactory} + * explicitly ordered locks participate in general cycle detection with all + * other cycle detecting locks, and a lock's behavior when detecting a cyclic + * lock acquisition is defined by the {@code Policy} of the factory that + * created it. + * <p> + * Note, however, that although multiple locks can be created for a given Enum + * value, whether it be through separate factory instances or through multiple + * calls to the same factory, attempting to acquire multiple locks with the + * same Enum value (within the same thread) will result in an + * IllegalStateException regardless of the factory's policy. For example: + * + * <pre> {@code + * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory1 = + * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...); + * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory2 = + * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...); + * + * Lock lockA = factory1.newReentrantLock(MyLockOrder.FIRST); + * Lock lockB = factory1.newReentrantLock(MyLockOrder.FIRST); + * Lock lockC = factory2.newReentrantLock(MyLockOrder.FIRST); + * + * lockA.lock(); + * + * lockB.lock(); // will throw an IllegalStateException + * lockC.lock(); // will throw an IllegalStateException + * + * lockA.lock(); // reentrant acquisition is okay + * }</pre> + * + * It is the responsibility of the application to ensure that multiple lock + * instances with the same rank are never acquired in the same thread. + * + * @param <E> The Enum type representing the explicit lock ordering. + * @since 13.0 + */ + @Beta + public static final class WithExplicitOrdering<E extends Enum<E>> + extends CycleDetectingLockFactory { + + private final Map<E, LockGraphNode> lockGraphNodes; + + @VisibleForTesting + WithExplicitOrdering( + Policy policy, Map<E, LockGraphNode> lockGraphNodes) { + super(policy); + this.lockGraphNodes = lockGraphNodes; + } + + /** + * Equivalent to {@code newReentrantLock(rank, false)}. + */ + public ReentrantLock newReentrantLock(E rank) { + return newReentrantLock(rank, false); + } + + /** + * Creates a {@link ReentrantLock} with the given fairness policy and rank. + * The values returned by {@link Enum#getDeclaringClass()} and + * {@link Enum#name()} are used to describe the lock in warning or + * exception output. + * + * @throws IllegalStateException If the factory has already created a + * {@code Lock} with the specified rank. + */ + public ReentrantLock newReentrantLock(E rank, boolean fair) { + return policy == Policies.DISABLED ? new ReentrantLock(fair) + : new CycleDetectingReentrantLock(lockGraphNodes.get(rank), fair); + } + + /** + * Equivalent to {@code newReentrantReadWriteLock(rank, false)}. + */ + public ReentrantReadWriteLock newReentrantReadWriteLock(E rank) { + return newReentrantReadWriteLock(rank, false); + } + + /** + * Creates a {@link ReentrantReadWriteLock} with the given fairness policy + * and rank. The values returned by {@link Enum#getDeclaringClass()} and + * {@link Enum#name()} are used to describe the lock in warning or exception + * output. + * + * @throws IllegalStateException If the factory has already created a + * {@code Lock} with the specified rank. + */ + public ReentrantReadWriteLock newReentrantReadWriteLock( + E rank, boolean fair) { + return policy == Policies.DISABLED ? new ReentrantReadWriteLock(fair) + : new CycleDetectingReentrantReadWriteLock( + lockGraphNodes.get(rank), fair); + } + } + + /** + * For a given Enum type, creates an immutable map from each of the Enum's + * values to a corresponding LockGraphNode, with the + * {@code allowedPriorLocks} and {@code disallowedPriorLocks} prepopulated + * with nodes according to the natural ordering of the associated Enum values. + */ + @VisibleForTesting + static class OrderedLockGraphNodesCreator + implements Function<Class<? extends Enum>, + Map<? extends Enum, LockGraphNode>> { + + @Override + @SuppressWarnings("unchecked") // There's no way to properly express with + // wildcards the recursive Enum type required by createNodesFor(), and the + // Map/Function types must use wildcards since they accept any Enum class. + public Map<? extends Enum, LockGraphNode> apply( + Class<? extends Enum> clazz) { + return createNodesFor(clazz); + } + + <E extends Enum<E>> Map<E, LockGraphNode> createNodesFor(Class<E> clazz) { + EnumMap<E, LockGraphNode> map = Maps.newEnumMap(clazz); + E[] keys = clazz.getEnumConstants(); + final int numKeys = keys.length; + ArrayList<LockGraphNode> nodes = + Lists.newArrayListWithCapacity(numKeys); + // Create a LockGraphNode for each enum value. + for (E key : keys) { + LockGraphNode node = new LockGraphNode(getLockName(key)); + nodes.add(node); + map.put(key, node); + } + // Pre-populate all allowedPriorLocks with nodes of smaller ordinal. + for (int i = 1; i < numKeys; i++) { + nodes.get(i).checkAcquiredLocks(Policies.THROW, nodes.subList(0, i)); + } + // Pre-populate all disallowedPriorLocks with nodes of larger ordinal. + for (int i = 0; i < numKeys - 1; i++) { + nodes.get(i).checkAcquiredLocks( + Policies.DISABLED, nodes.subList(i + 1, numKeys)); + } + return Collections.unmodifiableMap(map); + } + + /** + * For the given Enum value {@code rank}, returns the value's + * {@code "EnumClass.name"}, which is used in exception and warning + * output. + */ + private String getLockName(Enum<?> rank) { + return rank.getDeclaringClass().getSimpleName() + "." + rank.name(); + } + } + + //////// Implementation ///////// + + private static final Logger logger = Logger.getLogger( + CycleDetectingLockFactory.class.getName()); + + final Policy policy; + + private CycleDetectingLockFactory(Policy policy) { + this.policy = policy; + } + + /** + * Tracks the currently acquired locks for each Thread, kept up to date by + * calls to {@link #aboutToAcquire(CycleDetectingLock)} and + * {@link #lockStateChanged(CycleDetectingLock)}. + */ + // This is logically a Set, but an ArrayList is used to minimize the amount + // of allocation done on lock()/unlock(). + private static final ThreadLocal<ArrayList<LockGraphNode>> + acquiredLocks = new ThreadLocal<ArrayList<LockGraphNode>>() { + @Override + protected ArrayList<LockGraphNode> initialValue() { + return Lists.<LockGraphNode>newArrayListWithCapacity(3); + } + }; + + /** + * A Throwable used to record a stack trace that illustrates an example of + * a specific lock acquisition ordering. The top of the stack trace is + * truncated such that it starts with the acquisition of the lock in + * question, e.g. + * + * <pre> + * com...ExampleStackTrace: LockB -> LockC + * at com...CycleDetectingReentrantLock.lock(CycleDetectingLockFactory.java:443) + * at ... + * at ... + * at com...MyClass.someMethodThatAcquiresLockB(MyClass.java:123) + * </pre> + */ + private static class ExampleStackTrace extends IllegalStateException { + + static final StackTraceElement[] EMPTY_STACK_TRACE = + new StackTraceElement[0]; + + static Set<String> EXCLUDED_CLASS_NAMES = ImmutableSet.of( + CycleDetectingLockFactory.class.getName(), + ExampleStackTrace.class.getName(), + LockGraphNode.class.getName()); + + ExampleStackTrace(LockGraphNode node1, LockGraphNode node2) { + super(node1.getLockName() + " -> " + node2.getLockName()); + StackTraceElement[] origStackTrace = getStackTrace(); + for (int i = 0, n = origStackTrace.length; i < n; i++) { + if (WithExplicitOrdering.class.getName().equals( + origStackTrace[i].getClassName())) { + // For pre-populated disallowedPriorLocks edges, omit the stack trace. + setStackTrace(EMPTY_STACK_TRACE); + break; + } + if (!EXCLUDED_CLASS_NAMES.contains(origStackTrace[i].getClassName())) { + setStackTrace(Arrays.copyOfRange(origStackTrace, i, n)); + break; + } + } + } + } + + /** + * Represents a detected cycle in lock acquisition ordering. The exception + * includes a causal chain of {@code ExampleStackTrace}s to illustrate the + * cycle, e.g. + * + * <pre> + * com....PotentialDeadlockException: Potential Deadlock from LockC -> ReadWriteA + * at ... + * at ... + * Caused by: com...ExampleStackTrace: LockB -> LockC + * at ... + * at ... + * Caused by: com...ExampleStackTrace: ReadWriteA -> LockB + * at ... + * at ... + * </pre> + * + * Instances are logged for the {@code Policies.WARN}, and thrown for + * {@code Policies.THROW}. + * + * @since 13.0 + */ + @Beta + public static final class PotentialDeadlockException + extends ExampleStackTrace { + + private final ExampleStackTrace conflictingStackTrace; + + private PotentialDeadlockException( + LockGraphNode node1, + LockGraphNode node2, + ExampleStackTrace conflictingStackTrace) { + super(node1, node2); + this.conflictingStackTrace = conflictingStackTrace; + initCause(conflictingStackTrace); + } + + public ExampleStackTrace getConflictingStackTrace() { + return conflictingStackTrace; + } + + /** + * Appends the chain of messages from the {@code conflictingStackTrace} to + * the original {@code message}. + */ + @Override + public String getMessage() { + StringBuilder message = new StringBuilder(super.getMessage()); + for (Throwable t = conflictingStackTrace; t != null; t = t.getCause()) { + message.append(", ").append(t.getMessage()); + } + return message.toString(); + } + } + + /** + * Internal Lock implementations implement the {@code CycleDetectingLock} + * interface, allowing the detection logic to treat all locks in the same + * manner. + */ + private interface CycleDetectingLock { + + /** @return the {@link LockGraphNode} associated with this lock. */ + LockGraphNode getLockGraphNode(); + + /** @return {@code true} if the current thread has acquired this lock. */ + boolean isAcquiredByCurrentThread(); + } + + /** + * A {@code LockGraphNode} associated with each lock instance keeps track of + * the directed edges in the lock acquisition graph. + */ + private static class LockGraphNode { + + /** + * The map tracking the locks that are known to be acquired before this + * lock, each associated with an example stack trace. Locks are weakly keyed + * to allow proper garbage collection when they are no longer referenced. + */ + final Map<LockGraphNode, ExampleStackTrace> allowedPriorLocks = + new MapMaker().weakKeys().makeMap(); + + /** + * The map tracking lock nodes that can cause a lock acquisition cycle if + * acquired before this node. + */ + final Map<LockGraphNode, PotentialDeadlockException> + disallowedPriorLocks = new MapMaker().weakKeys().makeMap(); + + final String lockName; + + LockGraphNode(String lockName) { + this.lockName = Preconditions.checkNotNull(lockName); + } + + String getLockName() { + return lockName; + } + + void checkAcquiredLocks( + Policy policy, List<LockGraphNode> acquiredLocks) { + for (int i = 0, size = acquiredLocks.size(); i < size; i++) { + checkAcquiredLock(policy, acquiredLocks.get(i)); + } + } + + /** + * Checks the acquisition-ordering between {@code this}, which is about to + * be acquired, and the specified {@code acquiredLock}. + * <p> + * When this method returns, the {@code acquiredLock} should be in either + * the {@code preAcquireLocks} map, for the case in which it is safe to + * acquire {@code this} after the {@code acquiredLock}, or in the + * {@code disallowedPriorLocks} map, in which case it is not safe. + */ + void checkAcquiredLock(Policy policy, LockGraphNode acquiredLock) { + // checkAcquiredLock() should never be invoked by a lock that has already + // been acquired. For unordered locks, aboutToAcquire() ensures this by + // checking isAcquiredByCurrentThread(). For ordered locks, however, this + // can happen because multiple locks may share the same LockGraphNode. In + // this situation, throw an IllegalStateException as defined by contract + // described in the documentation of WithExplicitOrdering. + Preconditions.checkState( + this != acquiredLock, + "Attempted to acquire multiple locks with the same rank " + + acquiredLock.getLockName()); + + if (allowedPriorLocks.containsKey(acquiredLock)) { + // The acquisition ordering from "acquiredLock" to "this" has already + // been verified as safe. In a properly written application, this is + // the common case. + return; + } + PotentialDeadlockException previousDeadlockException = + disallowedPriorLocks.get(acquiredLock); + if (previousDeadlockException != null) { + // Previously determined to be an unsafe lock acquisition. + // Create a new PotentialDeadlockException with the same causal chain + // (the example cycle) as that of the cached exception. + PotentialDeadlockException exception = new PotentialDeadlockException( + acquiredLock, this, + previousDeadlockException.getConflictingStackTrace()); + policy.handlePotentialDeadlock(exception); + return; + } + // Otherwise, it's the first time seeing this lock relationship. Look for + // a path from the acquiredLock to this. + Set<LockGraphNode> seen = Sets.newIdentityHashSet(); + ExampleStackTrace path = acquiredLock.findPathTo(this, seen); + + if (path == null) { + // this can be safely acquired after the acquiredLock. + // + // Note that there is a race condition here which can result in missing + // a cyclic edge: it's possible for two threads to simultaneous find + // "safe" edges which together form a cycle. Preventing this race + // condition efficiently without _introducing_ deadlock is probably + // tricky. For now, just accept the race condition---missing a warning + // now and then is still better than having no deadlock detection. + allowedPriorLocks.put( + acquiredLock, new ExampleStackTrace(acquiredLock, this)); + } else { + // Unsafe acquisition order detected. Create and cache a + // PotentialDeadlockException. + PotentialDeadlockException exception = + new PotentialDeadlockException(acquiredLock, this, path); + disallowedPriorLocks.put(acquiredLock, exception); + policy.handlePotentialDeadlock(exception); + } + } + + /** + * Performs a depth-first traversal of the graph edges defined by each + * node's {@code allowedPriorLocks} to find a path between {@code this} and + * the specified {@code lock}. + * + * @return If a path was found, a chained {@link ExampleStackTrace} + * illustrating the path to the {@code lock}, or {@code null} if no path + * was found. + */ + @Nullable + private ExampleStackTrace findPathTo( + LockGraphNode node, Set<LockGraphNode> seen) { + if (!seen.add(this)) { + return null; // Already traversed this node. + } + ExampleStackTrace found = allowedPriorLocks.get(node); + if (found != null) { + return found; // Found a path ending at the node! + } + // Recurse the edges. + for (Map.Entry<LockGraphNode, ExampleStackTrace> entry : + allowedPriorLocks.entrySet()) { + LockGraphNode preAcquiredLock = entry.getKey(); + found = preAcquiredLock.findPathTo(node, seen); + if (found != null) { + // One of this node's allowedPriorLocks found a path. Prepend an + // ExampleStackTrace(preAcquiredLock, this) to the returned chain of + // ExampleStackTraces. + ExampleStackTrace path = + new ExampleStackTrace(preAcquiredLock, this); + path.setStackTrace(entry.getValue().getStackTrace()); + path.initCause(found); + return path; + } + } + return null; + } + } + + /** + * CycleDetectingLock implementations must call this method before attempting + * to acquire the lock. + */ + private void aboutToAcquire(CycleDetectingLock lock) { + if (!lock.isAcquiredByCurrentThread()) { + ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get(); + LockGraphNode node = lock.getLockGraphNode(); + node.checkAcquiredLocks(policy, acquiredLockList); + acquiredLockList.add(node); + } + } + + /** + * CycleDetectingLock implementations must call this method in a + * {@code finally} clause after any attempt to change the lock state, + * including both lock and unlock attempts. Failure to do so can result in + * corrupting the acquireLocks set. + */ + private void lockStateChanged(CycleDetectingLock lock) { + if (!lock.isAcquiredByCurrentThread()) { + ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get(); + LockGraphNode node = lock.getLockGraphNode(); + // Iterate in reverse because locks are usually locked/unlocked in a + // LIFO order. + for (int i = acquiredLockList.size() - 1; i >=0; i--) { + if (acquiredLockList.get(i) == node) { + acquiredLockList.remove(i); + break; + } + } + } + } + + final class CycleDetectingReentrantLock + extends ReentrantLock implements CycleDetectingLock { + + private final LockGraphNode lockGraphNode; + + private CycleDetectingReentrantLock( + LockGraphNode lockGraphNode, boolean fair) { + super(fair); + this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode); + } + + ///// CycleDetectingLock methods. ///// + + @Override + public LockGraphNode getLockGraphNode() { + return lockGraphNode; + } + + @Override + public boolean isAcquiredByCurrentThread() { + return isHeldByCurrentThread(); + } + + ///// Overridden ReentrantLock methods. ///// + + @Override + public void lock() { + aboutToAcquire(this); + try { + super.lock(); + } finally { + lockStateChanged(this); + } + } + + @Override + public void lockInterruptibly() throws InterruptedException { + aboutToAcquire(this); + try { + super.lockInterruptibly(); + } finally { + lockStateChanged(this); + } + } + + @Override + public boolean tryLock() { + aboutToAcquire(this); + try { + return super.tryLock(); + } finally { + lockStateChanged(this); + } + } + + @Override + public boolean tryLock(long timeout, TimeUnit unit) + throws InterruptedException { + aboutToAcquire(this); + try { + return super.tryLock(timeout, unit); + } finally { + lockStateChanged(this); + } + } + + @Override + public void unlock() { + try { + super.unlock(); + } finally { + lockStateChanged(this); + } + } + } + + final class CycleDetectingReentrantReadWriteLock + extends ReentrantReadWriteLock implements CycleDetectingLock { + + // These ReadLock/WriteLock implementations shadow those in the + // ReentrantReadWriteLock superclass. They are simply wrappers around the + // internal Sync object, so this is safe since the shadowed locks are never + // exposed or used. + private final CycleDetectingReentrantReadLock readLock; + private final CycleDetectingReentrantWriteLock writeLock; + + private final LockGraphNode lockGraphNode; + + private CycleDetectingReentrantReadWriteLock( + LockGraphNode lockGraphNode, boolean fair) { + super(fair); + this.readLock = new CycleDetectingReentrantReadLock(this); + this.writeLock = new CycleDetectingReentrantWriteLock(this); + this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode); + } + + ///// Overridden ReentrantReadWriteLock methods. ///// + + @Override + public ReadLock readLock() { + return readLock; + } + + @Override + public WriteLock writeLock() { + return writeLock; + } + + ///// CycleDetectingLock methods. ///// + + @Override + public LockGraphNode getLockGraphNode() { + return lockGraphNode; + } + + @Override + public boolean isAcquiredByCurrentThread() { + return isWriteLockedByCurrentThread() || getReadHoldCount() > 0; + } + } + + private class CycleDetectingReentrantReadLock + extends ReentrantReadWriteLock.ReadLock { + + final CycleDetectingReentrantReadWriteLock readWriteLock; + + CycleDetectingReentrantReadLock( + CycleDetectingReentrantReadWriteLock readWriteLock) { + super(readWriteLock); + this.readWriteLock = readWriteLock; + } + + @Override + public void lock() { + aboutToAcquire(readWriteLock); + try { + super.lock(); + } finally { + lockStateChanged(readWriteLock); + } + } + + @Override + public void lockInterruptibly() throws InterruptedException { + aboutToAcquire(readWriteLock); + try { + super.lockInterruptibly(); + } finally { + lockStateChanged(readWriteLock); + } + } + + @Override + public boolean tryLock() { + aboutToAcquire(readWriteLock); + try { + return super.tryLock(); + } finally { + lockStateChanged(readWriteLock); + } + } + + @Override + public boolean tryLock(long timeout, TimeUnit unit) + throws InterruptedException { + aboutToAcquire(readWriteLock); + try { + return super.tryLock(timeout, unit); + } finally { + lockStateChanged(readWriteLock); + } + } + + @Override + public void unlock() { + try { + super.unlock(); + } finally { + lockStateChanged(readWriteLock); + } + } + } + + private class CycleDetectingReentrantWriteLock + extends ReentrantReadWriteLock.WriteLock { + + final CycleDetectingReentrantReadWriteLock readWriteLock; + + CycleDetectingReentrantWriteLock( + CycleDetectingReentrantReadWriteLock readWriteLock) { + super(readWriteLock); + this.readWriteLock = readWriteLock; + } + + @Override + public void lock() { + aboutToAcquire(readWriteLock); + try { + super.lock(); + } finally { + lockStateChanged(readWriteLock); + } + } + + @Override + public void lockInterruptibly() throws InterruptedException { + aboutToAcquire(readWriteLock); + try { + super.lockInterruptibly(); + } finally { + lockStateChanged(readWriteLock); + } + } + + @Override + public boolean tryLock() { + aboutToAcquire(readWriteLock); + try { + return super.tryLock(); + } finally { + lockStateChanged(readWriteLock); + } + } + + @Override + public boolean tryLock(long timeout, TimeUnit unit) + throws InterruptedException { + aboutToAcquire(readWriteLock); + try { + return super.tryLock(timeout, unit); + } finally { + lockStateChanged(readWriteLock); + } + } + + @Override + public void unlock() { + try { + super.unlock(); + } finally { + lockStateChanged(readWriteLock); + } + } + } +} |