Class CycleDetectingLockFactory
- java.lang.Object
-
- com.google.common.util.concurrent.CycleDetectingLockFactory
-
- Direct Known Subclasses:
CycleDetectingLockFactory.WithExplicitOrdering
@Beta @GwtIncompatible public class CycleDetectingLockFactory extends java.lang.Object
TheCycleDetectingLockFactory
createsReentrantLock
instances andReentrantReadWriteLock
instances that detect potential deadlock by checking for cycles in lock acquisition order.Potential deadlocks detected when calling the
lock()
,lockInterruptibly()
, ortryLock()
methods will result in the execution of theCycleDetectingLockFactory.Policy
specified when creating the factory. The currently available policies are:- DISABLED
- WARN
- THROW
The locks created by a factory instance will detect lock acquisition cycles with locks created by other
CycleDetectingLockFactory
instances (except those withPolicy.DISABLED
). A lock's behavior when a cycle is detected, however, is defined by thePolicy
of the factory that created it. This allows detection of cycles across components while delegating control over lock behavior to individual components.Applications are encouraged to use a
CycleDetectingLockFactory
to create any locks for which external/unmanaged code is executed while the lock is held. (See caveats under Performance).Cycle Detection
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:
Thread1: acquire(LockA) --X acquire(LockB) Thread2: acquire(LockB) --X acquire(LockA)
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:
Thread1: acquire(LockA) --X acquire(LockB) Thread2: acquire(LockB) --X acquire(LockC) ... ThreadN: acquire(LockN) --X acquire(LockA)
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.
- 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).
- 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.
- 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.
- If a cycle is detected, an "unsafe" (cyclic) edge is created to represent a potential deadlock situation, and the appropriate Policy is executed.
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:
LockA -> LockB -> LockC LockA -> LockC -> LockB
ReadWriteLocks
While
ReadWriteLock
instances have different properties and can form cycles without potential deadlock, this class treatsReadWriteLock
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.Explicit Lock Acquisition Ordering
The
CycleDetectingLockFactory.WithExplicitOrdering
class can be used to enforce an application-specific ordering in addition to performing general cycle detection.Garbage Collection
In order to allow proper garbage collection of unused locks, the edges of the lock graph are weak references.
Performance
The extra bookkeeping done by cycle detecting locks comes at some cost to performance. Benchmarks (as of December 2011) show that:
- for an unnested
lock()
andunlock()
, a cycle detecting lock takes 38ns as opposed to the 24ns taken by a plain lock. - for nested locking, the cost increases with the depth of the nesting:
- 2 levels: average of 64ns per lock()/unlock()
- 3 levels: average of 77ns per lock()/unlock()
- 4 levels: average of 99ns per lock()/unlock()
- 5 levels: average of 103ns per lock()/unlock()
- 10 levels: average of 184ns per lock()/unlock()
- 20 levels: average of 393ns per lock()/unlock()
As such, the CycleDetectingLockFactory may not be suitable for performance-critical applications which involve tightly-looped or deeply-nested locking algorithms.
- Since:
- 13.0
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static interface
CycleDetectingLockFactory.CycleDetectingLock
Internal Lock implementations implement theCycleDetectingLock
interface, allowing the detection logic to treat all locks in the same manner.(package private) class
CycleDetectingLockFactory.CycleDetectingReentrantLock
private class
CycleDetectingLockFactory.CycleDetectingReentrantReadLock
(package private) class
CycleDetectingLockFactory.CycleDetectingReentrantReadWriteLock
private class
CycleDetectingLockFactory.CycleDetectingReentrantWriteLock
private static class
CycleDetectingLockFactory.ExampleStackTrace
A Throwable used to record a stack trace that illustrates an example of a specific lock acquisition ordering.private static class
CycleDetectingLockFactory.LockGraphNode
ALockGraphNode
associated with each lock instance keeps track of the directed edges in the lock acquisition graph.static class
CycleDetectingLockFactory.Policies
Pre-definedCycleDetectingLockFactory.Policy
implementations.static interface
CycleDetectingLockFactory.Policy
Encapsulates the action to be taken when a potential deadlock is encountered.static class
CycleDetectingLockFactory.PotentialDeadlockException
Represents a detected cycle in lock acquisition ordering.static class
CycleDetectingLockFactory.WithExplicitOrdering<E extends java.lang.Enum<E>>
ACycleDetectingLockFactory.WithExplicitOrdering
provides the additional enforcement of an application-specified ordering of lock acquisitions.
-
Field Summary
Fields Modifier and Type Field Description private static java.lang.ThreadLocal<java.util.ArrayList<CycleDetectingLockFactory.LockGraphNode>>
acquiredLocks
Tracks the currently acquired locks for each Thread, kept up to date by calls toaboutToAcquire(CycleDetectingLock)
andlockStateChanged(CycleDetectingLock)
.private static java.util.concurrent.ConcurrentMap<java.lang.Class<? extends java.lang.Enum>,java.util.Map<? extends java.lang.Enum,CycleDetectingLockFactory.LockGraphNode>>
lockGraphNodesPerType
private static java.util.logging.Logger
logger
(package private) CycleDetectingLockFactory.Policy
policy
-
Constructor Summary
Constructors Modifier Constructor Description private
CycleDetectingLockFactory(CycleDetectingLockFactory.Policy policy)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
aboutToAcquire(CycleDetectingLockFactory.CycleDetectingLock lock)
CycleDetectingLock implementations must call this method before attempting to acquire the lock.(package private) static <E extends java.lang.Enum<E>>
java.util.Map<E,CycleDetectingLockFactory.LockGraphNode>createNodes(java.lang.Class<E> clazz)
For a given Enum type, creates an immutable map from each of the Enum's values to a corresponding LockGraphNode, with theallowedPriorLocks
anddisallowedPriorLocks
prepopulated with nodes according to the natural ordering of the associated Enum values.private static java.lang.String
getLockName(java.lang.Enum<?> rank)
For the given Enum valuerank
, returns the value's"EnumClass.name"
, which is used in exception and warning output.private static java.util.Map<? extends java.lang.Enum,CycleDetectingLockFactory.LockGraphNode>
getOrCreateNodes(java.lang.Class<? extends java.lang.Enum> clazz)
private static void
lockStateChanged(CycleDetectingLockFactory.CycleDetectingLock lock)
CycleDetectingLock implementations must call this method in afinally
clause after any attempt to change the lock state, including both lock and unlock attempts.static CycleDetectingLockFactory
newInstance(CycleDetectingLockFactory.Policy policy)
Creates a new factory with the specified policy.static <E extends java.lang.Enum<E>>
CycleDetectingLockFactory.WithExplicitOrdering<E>newInstanceWithExplicitOrdering(java.lang.Class<E> enumClass, CycleDetectingLockFactory.Policy policy)
Creates aCycleDetectingLockFactory.WithExplicitOrdering<E>
.java.util.concurrent.locks.ReentrantLock
newReentrantLock(java.lang.String lockName)
Equivalent tonewReentrantLock(lockName, false)
.java.util.concurrent.locks.ReentrantLock
newReentrantLock(java.lang.String lockName, boolean fair)
Creates aReentrantLock
with the given fairness policy.java.util.concurrent.locks.ReentrantReadWriteLock
newReentrantReadWriteLock(java.lang.String lockName)
Equivalent tonewReentrantReadWriteLock(lockName, false)
.java.util.concurrent.locks.ReentrantReadWriteLock
newReentrantReadWriteLock(java.lang.String lockName, boolean fair)
Creates aReentrantReadWriteLock
with the given fairness policy.
-
-
-
Field Detail
-
lockGraphNodesPerType
private static final java.util.concurrent.ConcurrentMap<java.lang.Class<? extends java.lang.Enum>,java.util.Map<? extends java.lang.Enum,CycleDetectingLockFactory.LockGraphNode>> lockGraphNodesPerType
-
logger
private static final java.util.logging.Logger logger
-
policy
final CycleDetectingLockFactory.Policy policy
-
acquiredLocks
private static final java.lang.ThreadLocal<java.util.ArrayList<CycleDetectingLockFactory.LockGraphNode>> acquiredLocks
Tracks the currently acquired locks for each Thread, kept up to date by calls toaboutToAcquire(CycleDetectingLock)
andlockStateChanged(CycleDetectingLock)
.
-
-
Constructor Detail
-
CycleDetectingLockFactory
private CycleDetectingLockFactory(CycleDetectingLockFactory.Policy policy)
-
-
Method Detail
-
newInstance
public static CycleDetectingLockFactory newInstance(CycleDetectingLockFactory.Policy policy)
Creates a new factory with the specified policy.
-
newReentrantLock
public java.util.concurrent.locks.ReentrantLock newReentrantLock(java.lang.String lockName)
Equivalent tonewReentrantLock(lockName, false)
.
-
newReentrantLock
public java.util.concurrent.locks.ReentrantLock newReentrantLock(java.lang.String lockName, boolean fair)
Creates aReentrantLock
with the given fairness policy. ThelockName
is used in the warning or exception output to help identify the locks involved in the detected deadlock.
-
newReentrantReadWriteLock
public java.util.concurrent.locks.ReentrantReadWriteLock newReentrantReadWriteLock(java.lang.String lockName)
Equivalent tonewReentrantReadWriteLock(lockName, false)
.
-
newReentrantReadWriteLock
public java.util.concurrent.locks.ReentrantReadWriteLock newReentrantReadWriteLock(java.lang.String lockName, boolean fair)
Creates aReentrantReadWriteLock
with the given fairness policy. ThelockName
is used in the warning or exception output to help identify the locks involved in the detected deadlock.
-
newInstanceWithExplicitOrdering
public static <E extends java.lang.Enum<E>> CycleDetectingLockFactory.WithExplicitOrdering<E> newInstanceWithExplicitOrdering(java.lang.Class<E> enumClass, CycleDetectingLockFactory.Policy policy)
Creates aCycleDetectingLockFactory.WithExplicitOrdering<E>
.
-
getOrCreateNodes
private static java.util.Map<? extends java.lang.Enum,CycleDetectingLockFactory.LockGraphNode> getOrCreateNodes(java.lang.Class<? extends java.lang.Enum> clazz)
-
createNodes
static <E extends java.lang.Enum<E>> java.util.Map<E,CycleDetectingLockFactory.LockGraphNode> createNodes(java.lang.Class<E> clazz)
For a given Enum type, creates an immutable map from each of the Enum's values to a corresponding LockGraphNode, with theallowedPriorLocks
anddisallowedPriorLocks
prepopulated with nodes according to the natural ordering of the associated Enum values.
-
getLockName
private static java.lang.String getLockName(java.lang.Enum<?> rank)
For the given Enum valuerank
, returns the value's"EnumClass.name"
, which is used in exception and warning output.
-
aboutToAcquire
private void aboutToAcquire(CycleDetectingLockFactory.CycleDetectingLock lock)
CycleDetectingLock implementations must call this method before attempting to acquire the lock.
-
lockStateChanged
private static void lockStateChanged(CycleDetectingLockFactory.CycleDetectingLock lock)
CycleDetectingLock implementations must call this method in afinally
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.
-
-