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