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 | 1038 |
1 files changed, 0 insertions, 1038 deletions
diff --git a/guava/src/com/google/common/util/concurrent/CycleDetectingLockFactory.java b/guava/src/com/google/common/util/concurrent/CycleDetectingLockFactory.java deleted file mode 100644 index 528fc8e..0000000 --- a/guava/src/com/google/common/util/concurrent/CycleDetectingLockFactory.java +++ /dev/null @@ -1,1038 +0,0 @@ -/* - * 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 static com.google.common.base.Preconditions.checkNotNull; - -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} instances and - * {@link ReentrantReadWriteLock} instances 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} instances have different properties and can form cycles - * without potential deadlock, this class treats {@code ReadWriteLock} instances 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. - checkNotNull(enumClass); - checkNotNull(policy); - @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 = checkNotNull(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} instances 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); - } - } - } -} |