|
|
Java example source code file (CycleDetectingLockFactory.java)
This example Java source code file (CycleDetectingLockFactory.java) is included in the alvinalexander.com
"Java Source Code
Warehouse" project. The intent of this project is to help you "Learn
Java by Example" TM.
Learn more about this Java project at its project page.
The CycleDetectingLockFactory.java Java example source code
/*
* 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.GwtIncompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.MoreObjects;
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 com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.j2objc.annotations.Weak;
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.ConcurrentMap;
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>
*
* <p>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).
*
* <p>Cycle Detection
*
* <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>
*
* <p>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>
*
* <p>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>
*
* <p>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>
*
* <p>ReadWriteLocks
*
* <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>Explicit Lock Acquisition Ordering
*
* <p>The {@link CycleDetectingLockFactory.WithExplicitOrdering} class can be used to enforce an
* application-specific ordering in addition to performing general cycle detection.
*
* <p>Garbage Collection
*
* <p>In order to allow proper garbage collection of unused locks, the edges of the lock graph are
* weak references.
*
* <p>Performance
*
* <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>
*
* <p>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
@CanIgnoreReturnValue // TODO(cpovirk): Consider being more strict.
@ThreadSafe
@GwtIncompatible
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 not 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 ConcurrentMap<Class>
lockGraphNodesPerType = new MapMaker().weakKeys().makeMap();
/**
* Creates a {@code CycleDetectingLockFactory.WithExplicitOrdering<E>}.
*/
public static <E extends Enum WithExplicitOrdering newInstanceWithExplicitOrdering(
Class<E> enumClass, Policy policy) {
// createNodes maps each enumClass to a Map with the corresponding enum key
// type.
checkNotNull(enumClass);
checkNotNull(policy);
@SuppressWarnings("unchecked")
Map<E, LockGraphNode> lockGraphNodes = (Map) getOrCreateNodes(enumClass);
return new WithExplicitOrdering<E>(policy, lockGraphNodes);
}
private static Map<? extends Enum, LockGraphNode> getOrCreateNodes(Class clazz) {
Map<? extends Enum, LockGraphNode> existing = lockGraphNodesPerType.get(clazz);
if (existing != null) {
return existing;
}
Map<? extends Enum, LockGraphNode> created = createNodes(clazz);
existing = lockGraphNodesPerType.putIfAbsent(clazz, created);
return MoreObjects.firstNonNull(existing, created);
}
/**
* 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 <E extends Enum Map createNodes(Class 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 static String getLockName(Enum<?> rank) {
return rank.getDeclaringClass().getSimpleName() + "." + rank.name();
}
/**
* <p>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>
*
* <p>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>
*
* <p>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
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);
}
}
//////// 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 acquiredLocks =
new ThreadLocal<ArrayList() {
@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 final 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>
*
* <p>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 %s",
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 static 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 {
@Weak 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 {
@Weak 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);
}
}
}
}
Other Java examples (source code examples)
Here is a short list of links related to this Java CycleDetectingLockFactory.java source code file:
|
The search page
Other Java source code examples at this package level
Click here to learn more about this project
