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