001 /*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.util.concurrent;
018
019 import com.google.common.annotations.Beta;
020 import com.google.common.annotations.VisibleForTesting;
021 import com.google.common.base.Function;
022 import com.google.common.base.Preconditions;
023 import com.google.common.collect.ImmutableSet;
024 import com.google.common.collect.Lists;
025 import com.google.common.collect.MapMaker;
026 import com.google.common.collect.Maps;
027 import com.google.common.collect.Sets;
028
029 import java.util.ArrayList;
030 import java.util.Arrays;
031 import java.util.Collections;
032 import java.util.EnumMap;
033 import java.util.List;
034 import java.util.Map;
035 import java.util.Set;
036 import java.util.concurrent.TimeUnit;
037 import java.util.concurrent.locks.ReentrantLock;
038 import java.util.concurrent.locks.ReentrantReadWriteLock;
039 import java.util.logging.Level;
040 import java.util.logging.Logger;
041
042 import javax.annotation.Nullable;
043 import javax.annotation.concurrent.ThreadSafe;
044
045 /**
046 * The {@code CycleDetectingLockFactory} creates {@link ReentrantLock}s and
047 * {@link ReentrantReadWriteLock}s that detect potential deadlock by checking
048 * for cycles in lock acquisition order.
049 * <p>
050 * Potential deadlocks detected when calling the {@code lock()},
051 * {@code lockInterruptibly()}, or {@code tryLock()} methods will result in the
052 * execution of the {@link Policy} specified when creating the factory. The
053 * currently available policies are:
054 * <ul>
055 * <li>DISABLED
056 * <li>WARN
057 * <li>THROW
058 * </ul>
059 * The locks created by a factory instance will detect lock acquisition cycles
060 * with locks created by other {@code CycleDetectingLockFactory} instances
061 * (except those with {@code Policy.DISABLED}). A lock's behavior when a cycle
062 * is detected, however, is defined by the {@code Policy} of the factory that
063 * created it. This allows detection of cycles across components while
064 * delegating control over lock behavior to individual components.
065 * <p>
066 * Applications are encouraged to use a {@code CycleDetectingLockFactory} to
067 * create any locks for which external/unmanaged code is executed while the lock
068 * is held. (See caveats under <strong>Performance</strong>).
069 * <p>
070 * <strong>Cycle Detection</strong>
071 * <p>
072 * Deadlocks can arise when locks are acquired in an order that forms a cycle.
073 * In a simple example involving two locks and two threads, deadlock occurs
074 * when one thread acquires Lock A, and then Lock B, while another thread
075 * acquires Lock B, and then Lock A:
076 * <pre>
077 * Thread1: acquire(LockA) --X acquire(LockB)
078 * Thread2: acquire(LockB) --X acquire(LockA)
079 * </pre>
080 * Neither thread will progress because each is waiting for the other. In more
081 * complex applications, cycles can arise from interactions among more than 2
082 * locks:
083 * <pre>
084 * Thread1: acquire(LockA) --X acquire(LockB)
085 * Thread2: acquire(LockB) --X acquire(LockC)
086 * ...
087 * ThreadN: acquire(LockN) --X acquire(LockA)
088 * </pre>
089 * The implementation detects cycles by constructing a directed graph in which
090 * each lock represents a node and each edge represents an acquisition ordering
091 * between two locks.
092 * <ul>
093 * <li>Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired
094 * locks when the Thread acquires its first hold (and releases its last
095 * remaining hold).
096 * <li>Before the lock is acquired, the lock is checked against the current set
097 * of acquired locks---to each of the acquired locks, an edge from the
098 * soon-to-be-acquired lock is either verified or created.
099 * <li>If a new edge needs to be created, the outgoing edges of the acquired
100 * locks are traversed to check for a cycle that reaches the lock to be
101 * acquired. If no cycle is detected, a new "safe" edge is created.
102 * <li>If a cycle is detected, an "unsafe" (cyclic) edge is created to represent
103 * a potential deadlock situation, and the appropriate Policy is executed.
104 * </ul>
105 * Note that detection of potential deadlock does not necessarily indicate that
106 * deadlock will happen, as it is possible that higher level application logic
107 * prevents the cyclic lock acquisition from occurring. One example of a false
108 * positive is:
109 * <pre>
110 * LockA -> LockB -> LockC
111 * LockA -> LockC -> LockB
112 * </pre>
113 *
114 * <strong>ReadWriteLocks</strong>
115 * <p>
116 * While {@code ReadWriteLock}s have different properties and can form cycles
117 * without potential deadlock, this class treats {@code ReadWriteLock}s as
118 * equivalent to traditional exclusive locks. Although this increases the false
119 * positives that the locks detect (i.e. cycles that will not actually result in
120 * deadlock), it simplifies the algorithm and implementation considerably. The
121 * assumption is that a user of this factory wishes to eliminate any cyclic
122 * acquisition ordering.
123 * <p>
124 * <strong>Explicit Lock Acquisition Ordering</strong>
125 * <p>
126 * The {@link CycleDetectingLockFactory.WithExplicitOrdering} class can be used
127 * to enforce an application-specific ordering in addition to performing general
128 * cycle detection.
129 * <p>
130 * <strong>Garbage Collection</strong>
131 * <p>
132 * In order to allow proper garbage collection of unused locks, the edges of
133 * the lock graph are weak references.
134 * <p>
135 * <strong>Performance</strong>
136 * <p>
137 * The extra bookkeeping done by cycle detecting locks comes at some cost to
138 * performance. Benchmarks (as of December 2011) show that:
139 *
140 * <ul>
141 * <li>for an unnested {@code lock()} and {@code unlock()}, a cycle detecting
142 * lock takes 38ns as opposed to the 24ns taken by a plain lock.
143 * <li>for nested locking, the cost increases with the depth of the nesting:
144 * <ul>
145 * <li> 2 levels: average of 64ns per lock()/unlock()
146 * <li> 3 levels: average of 77ns per lock()/unlock()
147 * <li> 4 levels: average of 99ns per lock()/unlock()
148 * <li> 5 levels: average of 103ns per lock()/unlock()
149 * <li>10 levels: average of 184ns per lock()/unlock()
150 * <li>20 levels: average of 393ns per lock()/unlock()
151 * </ul>
152 * </ul>
153 *
154 * As such, the CycleDetectingLockFactory may not be suitable for
155 * performance-critical applications which involve tightly-looped or
156 * deeply-nested locking algorithms.
157 *
158 * @author Darick Tong
159 * @since 13.0
160 */
161 @Beta
162 @ThreadSafe
163 public class CycleDetectingLockFactory {
164
165 /**
166 * Encapsulates the action to be taken when a potential deadlock is
167 * encountered. Clients can use one of the predefined {@link Policies} or
168 * specify a custom implementation. Implementations must be thread-safe.
169 *
170 * @since 13.0
171 */
172 @Beta
173 @ThreadSafe
174 public interface Policy {
175
176 /**
177 * Called when a potential deadlock is encountered. Implementations can
178 * throw the given {@code exception} and/or execute other desired logic.
179 * <p>
180 * Note that the method will be called even upon an invocation of
181 * {@code tryLock()}. Although {@code tryLock()} technically recovers from
182 * deadlock by eventually timing out, this behavior is chosen based on the
183 * assumption that it is the application's wish to prohibit any cyclical
184 * lock acquisitions.
185 */
186 void handlePotentialDeadlock(PotentialDeadlockException exception);
187 }
188
189 /**
190 * Pre-defined {@link Policy} implementations.
191 *
192 * @since 13.0
193 */
194 @Beta
195 public enum Policies implements Policy {
196 /**
197 * When potential deadlock is detected, this policy results in the throwing
198 * of the {@code PotentialDeadlockException} indicating the potential
199 * deadlock, which includes stack traces illustrating the cycle in lock
200 * acquisition order.
201 */
202 THROW {
203 @Override
204 public void handlePotentialDeadlock(PotentialDeadlockException e) {
205 throw e;
206 }
207 },
208
209 /**
210 * When potential deadlock is detected, this policy results in the logging
211 * of a {@link Level#SEVERE} message indicating the potential deadlock,
212 * which includes stack traces illustrating the cycle in lock acquisition
213 * order.
214 */
215 WARN {
216 @Override
217 public void handlePotentialDeadlock(PotentialDeadlockException e) {
218 logger.log(Level.SEVERE, "Detected potential deadlock", e);
219 }
220 },
221
222 /**
223 * Disables cycle detection. This option causes the factory to return
224 * unmodified lock implementations provided by the JDK, and is provided to
225 * allow applications to easily parameterize when cycle detection is
226 * enabled.
227 * <p>
228 * Note that locks created by a factory with this policy will <em>not</em>
229 * participate the cycle detection performed by locks created by other
230 * factories.
231 */
232 DISABLED {
233 @Override
234 public void handlePotentialDeadlock(PotentialDeadlockException e) {
235 }
236 };
237 }
238
239 /**
240 * Creates a new factory with the specified policy.
241 */
242 public static CycleDetectingLockFactory newInstance(Policy policy) {
243 return new CycleDetectingLockFactory(policy);
244 }
245
246 /**
247 * Equivalent to {@code newReentrantLock(lockName, false)}.
248 */
249 public ReentrantLock newReentrantLock(String lockName) {
250 return newReentrantLock(lockName, false);
251 }
252
253 /**
254 * Creates a {@link ReentrantLock} with the given fairness policy. The
255 * {@code lockName} is used in the warning or exception output to help
256 * identify the locks involved in the detected deadlock.
257 */
258 public ReentrantLock newReentrantLock(String lockName, boolean fair) {
259 return policy == Policies.DISABLED ? new ReentrantLock(fair)
260 : new CycleDetectingReentrantLock(
261 new LockGraphNode(lockName), fair);
262 }
263
264 /**
265 * Equivalent to {@code newReentrantReadWriteLock(lockName, false)}.
266 */
267 public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName) {
268 return newReentrantReadWriteLock(lockName, false);
269 }
270
271 /**
272 * Creates a {@link ReentrantReadWriteLock} with the given fairness policy.
273 * The {@code lockName} is used in the warning or exception output to help
274 * identify the locks involved in the detected deadlock.
275 */
276 public ReentrantReadWriteLock newReentrantReadWriteLock(
277 String lockName, boolean fair) {
278 return policy == Policies.DISABLED ? new ReentrantReadWriteLock(fair)
279 : new CycleDetectingReentrantReadWriteLock(
280 new LockGraphNode(lockName), fair);
281 }
282
283 // A static mapping from an Enum type to its set of LockGraphNodes.
284 private static final Map<Class<? extends Enum>,
285 Map<? extends Enum, LockGraphNode>> lockGraphNodesPerType =
286 new MapMaker().weakKeys().makeComputingMap(
287 new OrderedLockGraphNodesCreator());
288
289 /**
290 * Creates a {@code CycleDetectingLockFactory.WithExplicitOrdering<E>}.
291 */
292 public static <E extends Enum<E>> WithExplicitOrdering<E>
293 newInstanceWithExplicitOrdering(Class<E> enumClass, Policy policy) {
294 // OrderedLockGraphNodesCreator maps each enumClass to a Map with the
295 // corresponding enum key type.
296 @SuppressWarnings("unchecked")
297 Map<E, LockGraphNode> lockGraphNodes =
298 (Map<E, LockGraphNode>) lockGraphNodesPerType.get(enumClass);
299 return new WithExplicitOrdering<E>(policy, lockGraphNodes);
300 }
301
302 /**
303 * A {@code CycleDetectingLockFactory.WithExplicitOrdering} provides the
304 * additional enforcement of an application-specified ordering of lock
305 * acquisitions. The application defines the allowed ordering with an
306 * {@code Enum} whose values each correspond to a lock type. The order in
307 * which the values are declared dictates the allowed order of lock
308 * acquisition. In other words, locks corresponding to smaller values of
309 * {@link Enum#ordinal()} should only be acquired before locks with larger
310 * ordinals. Example:
311 *
312 * <pre> {@code
313 * enum MyLockOrder {
314 * FIRST, SECOND, THIRD;
315 * }
316 *
317 * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory =
318 * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(Policies.THROW);
319 *
320 * Lock lock1 = factory.newReentrantLock(MyLockOrder.FIRST);
321 * Lock lock2 = factory.newReentrantLock(MyLockOrder.SECOND);
322 * Lock lock3 = factory.newReentrantLock(MyLockOrder.THIRD);
323 *
324 * lock1.lock();
325 * lock3.lock();
326 * lock2.lock(); // will throw an IllegalStateException
327 * }</pre>
328 *
329 * As with all locks created by instances of {@code CycleDetectingLockFactory}
330 * explicitly ordered locks participate in general cycle detection with all
331 * other cycle detecting locks, and a lock's behavior when detecting a cyclic
332 * lock acquisition is defined by the {@code Policy} of the factory that
333 * created it.
334 * <p>
335 * Note, however, that although multiple locks can be created for a given Enum
336 * value, whether it be through separate factory instances or through multiple
337 * calls to the same factory, attempting to acquire multiple locks with the
338 * same Enum value (within the same thread) will result in an
339 * IllegalStateException regardless of the factory's policy. For example:
340 *
341 * <pre> {@code
342 * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory1 =
343 * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
344 * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory2 =
345 * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
346 *
347 * Lock lockA = factory1.newReentrantLock(MyLockOrder.FIRST);
348 * Lock lockB = factory1.newReentrantLock(MyLockOrder.FIRST);
349 * Lock lockC = factory2.newReentrantLock(MyLockOrder.FIRST);
350 *
351 * lockA.lock();
352 *
353 * lockB.lock(); // will throw an IllegalStateException
354 * lockC.lock(); // will throw an IllegalStateException
355 *
356 * lockA.lock(); // reentrant acquisition is okay
357 * }</pre>
358 *
359 * It is the responsibility of the application to ensure that multiple lock
360 * instances with the same rank are never acquired in the same thread.
361 *
362 * @param <E> The Enum type representing the explicit lock ordering.
363 * @since 13.0
364 */
365 @Beta
366 public static final class WithExplicitOrdering<E extends Enum<E>>
367 extends CycleDetectingLockFactory {
368
369 private final Map<E, LockGraphNode> lockGraphNodes;
370
371 @VisibleForTesting
372 WithExplicitOrdering(
373 Policy policy, Map<E, LockGraphNode> lockGraphNodes) {
374 super(policy);
375 this.lockGraphNodes = lockGraphNodes;
376 }
377
378 /**
379 * Equivalent to {@code newReentrantLock(rank, false)}.
380 */
381 public ReentrantLock newReentrantLock(E rank) {
382 return newReentrantLock(rank, false);
383 }
384
385 /**
386 * Creates a {@link ReentrantLock} with the given fairness policy and rank.
387 * The values returned by {@link Enum#getDeclaringClass()} and
388 * {@link Enum#name()} are used to describe the lock in warning or
389 * exception output.
390 *
391 * @throws IllegalStateException If the factory has already created a
392 * {@code Lock} with the specified rank.
393 */
394 public ReentrantLock newReentrantLock(E rank, boolean fair) {
395 return policy == Policies.DISABLED ? new ReentrantLock(fair)
396 : new CycleDetectingReentrantLock(lockGraphNodes.get(rank), fair);
397 }
398
399 /**
400 * Equivalent to {@code newReentrantReadWriteLock(rank, false)}.
401 */
402 public ReentrantReadWriteLock newReentrantReadWriteLock(E rank) {
403 return newReentrantReadWriteLock(rank, false);
404 }
405
406 /**
407 * Creates a {@link ReentrantReadWriteLock} with the given fairness policy
408 * and rank. The values returned by {@link Enum#getDeclaringClass()} and
409 * {@link Enum#name()} are used to describe the lock in warning or exception
410 * output.
411 *
412 * @throws IllegalStateException If the factory has already created a
413 * {@code Lock} with the specified rank.
414 */
415 public ReentrantReadWriteLock newReentrantReadWriteLock(
416 E rank, boolean fair) {
417 return policy == Policies.DISABLED ? new ReentrantReadWriteLock(fair)
418 : new CycleDetectingReentrantReadWriteLock(
419 lockGraphNodes.get(rank), fair);
420 }
421 }
422
423 /**
424 * For a given Enum type, creates an immutable map from each of the Enum's
425 * values to a corresponding LockGraphNode, with the
426 * {@code allowedPriorLocks} and {@code disallowedPriorLocks} prepopulated
427 * with nodes according to the natural ordering of the associated Enum values.
428 */
429 @VisibleForTesting
430 static class OrderedLockGraphNodesCreator
431 implements Function<Class<? extends Enum>,
432 Map<? extends Enum, LockGraphNode>> {
433
434 @Override
435 @SuppressWarnings("unchecked") // There's no way to properly express with
436 // wildcards the recursive Enum type required by createNodesFor(), and the
437 // Map/Function types must use wildcards since they accept any Enum class.
438 public Map<? extends Enum, LockGraphNode> apply(
439 Class<? extends Enum> clazz) {
440 return createNodesFor(clazz);
441 }
442
443 <E extends Enum<E>> Map<E, LockGraphNode> createNodesFor(Class<E> clazz) {
444 EnumMap<E, LockGraphNode> map = Maps.newEnumMap(clazz);
445 E[] keys = clazz.getEnumConstants();
446 final int numKeys = keys.length;
447 ArrayList<LockGraphNode> nodes =
448 Lists.newArrayListWithCapacity(numKeys);
449 // Create a LockGraphNode for each enum value.
450 for (E key : keys) {
451 LockGraphNode node = new LockGraphNode(getLockName(key));
452 nodes.add(node);
453 map.put(key, node);
454 }
455 // Pre-populate all allowedPriorLocks with nodes of smaller ordinal.
456 for (int i = 1; i < numKeys; i++) {
457 nodes.get(i).checkAcquiredLocks(Policies.THROW, nodes.subList(0, i));
458 }
459 // Pre-populate all disallowedPriorLocks with nodes of larger ordinal.
460 for (int i = 0; i < numKeys - 1; i++) {
461 nodes.get(i).checkAcquiredLocks(
462 Policies.DISABLED, nodes.subList(i + 1, numKeys));
463 }
464 return Collections.unmodifiableMap(map);
465 }
466
467 /**
468 * For the given Enum value {@code rank}, returns the value's
469 * {@code "EnumClass.name"}, which is used in exception and warning
470 * output.
471 */
472 private String getLockName(Enum<?> rank) {
473 return rank.getDeclaringClass().getSimpleName() + "." + rank.name();
474 }
475 }
476
477 //////// Implementation /////////
478
479 private static final Logger logger = Logger.getLogger(
480 CycleDetectingLockFactory.class.getName());
481
482 final Policy policy;
483
484 private CycleDetectingLockFactory(Policy policy) {
485 this.policy = policy;
486 }
487
488 /**
489 * Tracks the currently acquired locks for each Thread, kept up to date by
490 * calls to {@link #aboutToAcquire(CycleDetectingLock)} and
491 * {@link #lockStateChanged(CycleDetectingLock)}.
492 */
493 // This is logically a Set, but an ArrayList is used to minimize the amount
494 // of allocation done on lock()/unlock().
495 private static final ThreadLocal<ArrayList<LockGraphNode>>
496 acquiredLocks = new ThreadLocal<ArrayList<LockGraphNode>>() {
497 @Override
498 protected ArrayList<LockGraphNode> initialValue() {
499 return Lists.<LockGraphNode>newArrayListWithCapacity(3);
500 }
501 };
502
503 /**
504 * A Throwable used to record a stack trace that illustrates an example of
505 * a specific lock acquisition ordering. The top of the stack trace is
506 * truncated such that it starts with the acquisition of the lock in
507 * question, e.g.
508 *
509 * <pre>
510 * com...ExampleStackTrace: LockB -> LockC
511 * at com...CycleDetectingReentrantLock.lock(CycleDetectingLockFactory.java:443)
512 * at ...
513 * at ...
514 * at com...MyClass.someMethodThatAcquiresLockB(MyClass.java:123)
515 * </pre>
516 */
517 private static class ExampleStackTrace extends IllegalStateException {
518
519 static final StackTraceElement[] EMPTY_STACK_TRACE =
520 new StackTraceElement[0];
521
522 static Set<String> EXCLUDED_CLASS_NAMES = ImmutableSet.of(
523 CycleDetectingLockFactory.class.getName(),
524 ExampleStackTrace.class.getName(),
525 LockGraphNode.class.getName());
526
527 ExampleStackTrace(LockGraphNode node1, LockGraphNode node2) {
528 super(node1.getLockName() + " -> " + node2.getLockName());
529 StackTraceElement[] origStackTrace = getStackTrace();
530 for (int i = 0, n = origStackTrace.length; i < n; i++) {
531 if (WithExplicitOrdering.class.getName().equals(
532 origStackTrace[i].getClassName())) {
533 // For pre-populated disallowedPriorLocks edges, omit the stack trace.
534 setStackTrace(EMPTY_STACK_TRACE);
535 break;
536 }
537 if (!EXCLUDED_CLASS_NAMES.contains(origStackTrace[i].getClassName())) {
538 setStackTrace(Arrays.copyOfRange(origStackTrace, i, n));
539 break;
540 }
541 }
542 }
543 }
544
545 /**
546 * Represents a detected cycle in lock acquisition ordering. The exception
547 * includes a causal chain of {@code ExampleStackTrace}s to illustrate the
548 * cycle, e.g.
549 *
550 * <pre>
551 * com....PotentialDeadlockException: Potential Deadlock from LockC -> ReadWriteA
552 * at ...
553 * at ...
554 * Caused by: com...ExampleStackTrace: LockB -> LockC
555 * at ...
556 * at ...
557 * Caused by: com...ExampleStackTrace: ReadWriteA -> LockB
558 * at ...
559 * at ...
560 * </pre>
561 *
562 * Instances are logged for the {@code Policies.WARN}, and thrown for
563 * {@code Policies.THROW}.
564 *
565 * @since 13.0
566 */
567 @Beta
568 public static final class PotentialDeadlockException
569 extends ExampleStackTrace {
570
571 private final ExampleStackTrace conflictingStackTrace;
572
573 private PotentialDeadlockException(
574 LockGraphNode node1,
575 LockGraphNode node2,
576 ExampleStackTrace conflictingStackTrace) {
577 super(node1, node2);
578 this.conflictingStackTrace = conflictingStackTrace;
579 initCause(conflictingStackTrace);
580 }
581
582 public ExampleStackTrace getConflictingStackTrace() {
583 return conflictingStackTrace;
584 }
585
586 /**
587 * Appends the chain of messages from the {@code conflictingStackTrace} to
588 * the original {@code message}.
589 */
590 @Override
591 public String getMessage() {
592 StringBuilder message = new StringBuilder(super.getMessage());
593 for (Throwable t = conflictingStackTrace; t != null; t = t.getCause()) {
594 message.append(", ").append(t.getMessage());
595 }
596 return message.toString();
597 }
598 }
599
600 /**
601 * Internal Lock implementations implement the {@code CycleDetectingLock}
602 * interface, allowing the detection logic to treat all locks in the same
603 * manner.
604 */
605 private interface CycleDetectingLock {
606
607 /** @return the {@link LockGraphNode} associated with this lock. */
608 LockGraphNode getLockGraphNode();
609
610 /** @return {@code true} if the current thread has acquired this lock. */
611 boolean isAcquiredByCurrentThread();
612 }
613
614 /**
615 * A {@code LockGraphNode} associated with each lock instance keeps track of
616 * the directed edges in the lock acquisition graph.
617 */
618 private static class LockGraphNode {
619
620 /**
621 * The map tracking the locks that are known to be acquired before this
622 * lock, each associated with an example stack trace. Locks are weakly keyed
623 * to allow proper garbage collection when they are no longer referenced.
624 */
625 final Map<LockGraphNode, ExampleStackTrace> allowedPriorLocks =
626 new MapMaker().weakKeys().makeMap();
627
628 /**
629 * The map tracking lock nodes that can cause a lock acquisition cycle if
630 * acquired before this node.
631 */
632 final Map<LockGraphNode, PotentialDeadlockException>
633 disallowedPriorLocks = new MapMaker().weakKeys().makeMap();
634
635 final String lockName;
636
637 LockGraphNode(String lockName) {
638 this.lockName = Preconditions.checkNotNull(lockName);
639 }
640
641 String getLockName() {
642 return lockName;
643 }
644
645 void checkAcquiredLocks(
646 Policy policy, List<LockGraphNode> acquiredLocks) {
647 for (int i = 0, size = acquiredLocks.size(); i < size; i++) {
648 checkAcquiredLock(policy, acquiredLocks.get(i));
649 }
650 }
651
652 /**
653 * Checks the acquisition-ordering between {@code this}, which is about to
654 * be acquired, and the specified {@code acquiredLock}.
655 * <p>
656 * When this method returns, the {@code acquiredLock} should be in either
657 * the {@code preAcquireLocks} map, for the case in which it is safe to
658 * acquire {@code this} after the {@code acquiredLock}, or in the
659 * {@code disallowedPriorLocks} map, in which case it is not safe.
660 */
661 void checkAcquiredLock(Policy policy, LockGraphNode acquiredLock) {
662 // checkAcquiredLock() should never be invoked by a lock that has already
663 // been acquired. For unordered locks, aboutToAcquire() ensures this by
664 // checking isAcquiredByCurrentThread(). For ordered locks, however, this
665 // can happen because multiple locks may share the same LockGraphNode. In
666 // this situation, throw an IllegalStateException as defined by contract
667 // described in the documentation of WithExplicitOrdering.
668 Preconditions.checkState(
669 this != acquiredLock,
670 "Attempted to acquire multiple locks with the same rank " +
671 acquiredLock.getLockName());
672
673 if (allowedPriorLocks.containsKey(acquiredLock)) {
674 // The acquisition ordering from "acquiredLock" to "this" has already
675 // been verified as safe. In a properly written application, this is
676 // the common case.
677 return;
678 }
679 PotentialDeadlockException previousDeadlockException =
680 disallowedPriorLocks.get(acquiredLock);
681 if (previousDeadlockException != null) {
682 // Previously determined to be an unsafe lock acquisition.
683 // Create a new PotentialDeadlockException with the same causal chain
684 // (the example cycle) as that of the cached exception.
685 PotentialDeadlockException exception = new PotentialDeadlockException(
686 acquiredLock, this,
687 previousDeadlockException.getConflictingStackTrace());
688 policy.handlePotentialDeadlock(exception);
689 return;
690 }
691 // Otherwise, it's the first time seeing this lock relationship. Look for
692 // a path from the acquiredLock to this.
693 Set<LockGraphNode> seen = Sets.newIdentityHashSet();
694 ExampleStackTrace path = acquiredLock.findPathTo(this, seen);
695
696 if (path == null) {
697 // this can be safely acquired after the acquiredLock.
698 //
699 // Note that there is a race condition here which can result in missing
700 // a cyclic edge: it's possible for two threads to simultaneous find
701 // "safe" edges which together form a cycle. Preventing this race
702 // condition efficiently without _introducing_ deadlock is probably
703 // tricky. For now, just accept the race condition---missing a warning
704 // now and then is still better than having no deadlock detection.
705 allowedPriorLocks.put(
706 acquiredLock, new ExampleStackTrace(acquiredLock, this));
707 } else {
708 // Unsafe acquisition order detected. Create and cache a
709 // PotentialDeadlockException.
710 PotentialDeadlockException exception =
711 new PotentialDeadlockException(acquiredLock, this, path);
712 disallowedPriorLocks.put(acquiredLock, exception);
713 policy.handlePotentialDeadlock(exception);
714 }
715 }
716
717 /**
718 * Performs a depth-first traversal of the graph edges defined by each
719 * node's {@code allowedPriorLocks} to find a path between {@code this} and
720 * the specified {@code lock}.
721 *
722 * @return If a path was found, a chained {@link ExampleStackTrace}
723 * illustrating the path to the {@code lock}, or {@code null} if no path
724 * was found.
725 */
726 @Nullable
727 private ExampleStackTrace findPathTo(
728 LockGraphNode node, Set<LockGraphNode> seen) {
729 if (!seen.add(this)) {
730 return null; // Already traversed this node.
731 }
732 ExampleStackTrace found = allowedPriorLocks.get(node);
733 if (found != null) {
734 return found; // Found a path ending at the node!
735 }
736 // Recurse the edges.
737 for (Map.Entry<LockGraphNode, ExampleStackTrace> entry :
738 allowedPriorLocks.entrySet()) {
739 LockGraphNode preAcquiredLock = entry.getKey();
740 found = preAcquiredLock.findPathTo(node, seen);
741 if (found != null) {
742 // One of this node's allowedPriorLocks found a path. Prepend an
743 // ExampleStackTrace(preAcquiredLock, this) to the returned chain of
744 // ExampleStackTraces.
745 ExampleStackTrace path =
746 new ExampleStackTrace(preAcquiredLock, this);
747 path.setStackTrace(entry.getValue().getStackTrace());
748 path.initCause(found);
749 return path;
750 }
751 }
752 return null;
753 }
754 }
755
756 /**
757 * CycleDetectingLock implementations must call this method before attempting
758 * to acquire the lock.
759 */
760 private void aboutToAcquire(CycleDetectingLock lock) {
761 if (!lock.isAcquiredByCurrentThread()) {
762 ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
763 LockGraphNode node = lock.getLockGraphNode();
764 node.checkAcquiredLocks(policy, acquiredLockList);
765 acquiredLockList.add(node);
766 }
767 }
768
769 /**
770 * CycleDetectingLock implementations must call this method in a
771 * {@code finally} clause after any attempt to change the lock state,
772 * including both lock and unlock attempts. Failure to do so can result in
773 * corrupting the acquireLocks set.
774 */
775 private void lockStateChanged(CycleDetectingLock lock) {
776 if (!lock.isAcquiredByCurrentThread()) {
777 ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
778 LockGraphNode node = lock.getLockGraphNode();
779 // Iterate in reverse because locks are usually locked/unlocked in a
780 // LIFO order.
781 for (int i = acquiredLockList.size() - 1; i >=0; i--) {
782 if (acquiredLockList.get(i) == node) {
783 acquiredLockList.remove(i);
784 break;
785 }
786 }
787 }
788 }
789
790 final class CycleDetectingReentrantLock
791 extends ReentrantLock implements CycleDetectingLock {
792
793 private final LockGraphNode lockGraphNode;
794
795 private CycleDetectingReentrantLock(
796 LockGraphNode lockGraphNode, boolean fair) {
797 super(fair);
798 this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
799 }
800
801 ///// CycleDetectingLock methods. /////
802
803 @Override
804 public LockGraphNode getLockGraphNode() {
805 return lockGraphNode;
806 }
807
808 @Override
809 public boolean isAcquiredByCurrentThread() {
810 return isHeldByCurrentThread();
811 }
812
813 ///// Overridden ReentrantLock methods. /////
814
815 @Override
816 public void lock() {
817 aboutToAcquire(this);
818 try {
819 super.lock();
820 } finally {
821 lockStateChanged(this);
822 }
823 }
824
825 @Override
826 public void lockInterruptibly() throws InterruptedException {
827 aboutToAcquire(this);
828 try {
829 super.lockInterruptibly();
830 } finally {
831 lockStateChanged(this);
832 }
833 }
834
835 @Override
836 public boolean tryLock() {
837 aboutToAcquire(this);
838 try {
839 return super.tryLock();
840 } finally {
841 lockStateChanged(this);
842 }
843 }
844
845 @Override
846 public boolean tryLock(long timeout, TimeUnit unit)
847 throws InterruptedException {
848 aboutToAcquire(this);
849 try {
850 return super.tryLock(timeout, unit);
851 } finally {
852 lockStateChanged(this);
853 }
854 }
855
856 @Override
857 public void unlock() {
858 try {
859 super.unlock();
860 } finally {
861 lockStateChanged(this);
862 }
863 }
864 }
865
866 final class CycleDetectingReentrantReadWriteLock
867 extends ReentrantReadWriteLock implements CycleDetectingLock {
868
869 // These ReadLock/WriteLock implementations shadow those in the
870 // ReentrantReadWriteLock superclass. They are simply wrappers around the
871 // internal Sync object, so this is safe since the shadowed locks are never
872 // exposed or used.
873 private final CycleDetectingReentrantReadLock readLock;
874 private final CycleDetectingReentrantWriteLock writeLock;
875
876 private final LockGraphNode lockGraphNode;
877
878 private CycleDetectingReentrantReadWriteLock(
879 LockGraphNode lockGraphNode, boolean fair) {
880 super(fair);
881 this.readLock = new CycleDetectingReentrantReadLock(this);
882 this.writeLock = new CycleDetectingReentrantWriteLock(this);
883 this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
884 }
885
886 ///// Overridden ReentrantReadWriteLock methods. /////
887
888 @Override
889 public ReadLock readLock() {
890 return readLock;
891 }
892
893 @Override
894 public WriteLock writeLock() {
895 return writeLock;
896 }
897
898 ///// CycleDetectingLock methods. /////
899
900 @Override
901 public LockGraphNode getLockGraphNode() {
902 return lockGraphNode;
903 }
904
905 @Override
906 public boolean isAcquiredByCurrentThread() {
907 return isWriteLockedByCurrentThread() || getReadHoldCount() > 0;
908 }
909 }
910
911 private class CycleDetectingReentrantReadLock
912 extends ReentrantReadWriteLock.ReadLock {
913
914 final CycleDetectingReentrantReadWriteLock readWriteLock;
915
916 CycleDetectingReentrantReadLock(
917 CycleDetectingReentrantReadWriteLock readWriteLock) {
918 super(readWriteLock);
919 this.readWriteLock = readWriteLock;
920 }
921
922 @Override
923 public void lock() {
924 aboutToAcquire(readWriteLock);
925 try {
926 super.lock();
927 } finally {
928 lockStateChanged(readWriteLock);
929 }
930 }
931
932 @Override
933 public void lockInterruptibly() throws InterruptedException {
934 aboutToAcquire(readWriteLock);
935 try {
936 super.lockInterruptibly();
937 } finally {
938 lockStateChanged(readWriteLock);
939 }
940 }
941
942 @Override
943 public boolean tryLock() {
944 aboutToAcquire(readWriteLock);
945 try {
946 return super.tryLock();
947 } finally {
948 lockStateChanged(readWriteLock);
949 }
950 }
951
952 @Override
953 public boolean tryLock(long timeout, TimeUnit unit)
954 throws InterruptedException {
955 aboutToAcquire(readWriteLock);
956 try {
957 return super.tryLock(timeout, unit);
958 } finally {
959 lockStateChanged(readWriteLock);
960 }
961 }
962
963 @Override
964 public void unlock() {
965 try {
966 super.unlock();
967 } finally {
968 lockStateChanged(readWriteLock);
969 }
970 }
971 }
972
973 private class CycleDetectingReentrantWriteLock
974 extends ReentrantReadWriteLock.WriteLock {
975
976 final CycleDetectingReentrantReadWriteLock readWriteLock;
977
978 CycleDetectingReentrantWriteLock(
979 CycleDetectingReentrantReadWriteLock readWriteLock) {
980 super(readWriteLock);
981 this.readWriteLock = readWriteLock;
982 }
983
984 @Override
985 public void lock() {
986 aboutToAcquire(readWriteLock);
987 try {
988 super.lock();
989 } finally {
990 lockStateChanged(readWriteLock);
991 }
992 }
993
994 @Override
995 public void lockInterruptibly() throws InterruptedException {
996 aboutToAcquire(readWriteLock);
997 try {
998 super.lockInterruptibly();
999 } finally {
1000 lockStateChanged(readWriteLock);
1001 }
1002 }
1003
1004 @Override
1005 public boolean tryLock() {
1006 aboutToAcquire(readWriteLock);
1007 try {
1008 return super.tryLock();
1009 } finally {
1010 lockStateChanged(readWriteLock);
1011 }
1012 }
1013
1014 @Override
1015 public boolean tryLock(long timeout, TimeUnit unit)
1016 throws InterruptedException {
1017 aboutToAcquire(readWriteLock);
1018 try {
1019 return super.tryLock(timeout, unit);
1020 } finally {
1021 lockStateChanged(readWriteLock);
1022 }
1023 }
1024
1025 @Override
1026 public void unlock() {
1027 try {
1028 super.unlock();
1029 } finally {
1030 lockStateChanged(readWriteLock);
1031 }
1032 }
1033 }
1034 }