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; 018 019import com.google.common.annotations.Beta; 020import com.google.common.annotations.GwtIncompatible; 021import com.google.common.annotations.VisibleForTesting; 022import com.google.common.base.MoreObjects; 023import com.google.common.base.Preconditions; 024import com.google.common.collect.ImmutableSet; 025import com.google.common.collect.Lists; 026import com.google.common.collect.MapMaker; 027import com.google.common.collect.Maps; 028import com.google.common.collect.Sets; 029import com.google.errorprone.annotations.CanIgnoreReturnValue; 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 org.checkerframework.checker.nullness.qual.Nullable; 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@Beta 163@CanIgnoreReturnValue // TODO(cpovirk): Consider being more strict. 164@GwtIncompatible 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 @Beta 175 public interface Policy { 176 177 /** 178 * Called when a potential deadlock is encountered. Implementations can throw the given {@code 179 * exception} and/or execute other desired logic. 180 * 181 * <p>Note that the method will be called even upon an invocation of {@code tryLock()}. Although 182 * {@code tryLock()} technically recovers from deadlock by eventually timing out, this behavior 183 * is chosen based on the 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 of the {@code 198 * PotentialDeadlockException} indicating the potential deadlock, which includes stack traces 199 * illustrating the cycle in lock acquisition order. 200 */ 201 THROW { 202 @Override 203 public void handlePotentialDeadlock(PotentialDeadlockException e) { 204 throw e; 205 } 206 }, 207 208 /** 209 * When potential deadlock is detected, this policy results in the logging of a {@link 210 * Level#SEVERE} message indicating the potential deadlock, which includes stack traces 211 * illustrating the cycle in lock acquisition order. 212 */ 213 WARN { 214 @Override 215 public void handlePotentialDeadlock(PotentialDeadlockException e) { 216 logger.log(Level.SEVERE, "Detected potential deadlock", e); 217 } 218 }, 219 220 /** 221 * Disables cycle detection. This option causes the factory to return unmodified lock 222 * implementations provided by the JDK, and is provided to allow applications to easily 223 * parameterize when cycle detection is enabled. 224 * 225 * <p>Note that locks created by a factory with this policy will <em>not</em> participate the 226 * cycle detection performed by locks created by other factories. 227 */ 228 DISABLED { 229 @Override 230 public void handlePotentialDeadlock(PotentialDeadlockException e) {} 231 }; 232 } 233 234 /** Creates a new factory with the specified policy. */ 235 public static CycleDetectingLockFactory newInstance(Policy policy) { 236 return new CycleDetectingLockFactory(policy); 237 } 238 239 /** Equivalent to {@code newReentrantLock(lockName, false)}. */ 240 public ReentrantLock newReentrantLock(String lockName) { 241 return newReentrantLock(lockName, false); 242 } 243 244 /** 245 * Creates a {@link ReentrantLock} with the given fairness policy. The {@code lockName} is used in 246 * the warning or exception output to help identify the locks involved in the detected deadlock. 247 */ 248 public ReentrantLock newReentrantLock(String lockName, boolean fair) { 249 return policy == Policies.DISABLED 250 ? new ReentrantLock(fair) 251 : new CycleDetectingReentrantLock(new LockGraphNode(lockName), fair); 252 } 253 254 /** Equivalent to {@code newReentrantReadWriteLock(lockName, false)}. */ 255 public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName) { 256 return newReentrantReadWriteLock(lockName, false); 257 } 258 259 /** 260 * Creates a {@link ReentrantReadWriteLock} with the given fairness policy. The {@code lockName} 261 * is used in the warning or exception output to help identify the locks involved in the detected 262 * deadlock. 263 */ 264 public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName, boolean fair) { 265 return policy == Policies.DISABLED 266 ? new ReentrantReadWriteLock(fair) 267 : new CycleDetectingReentrantReadWriteLock(new LockGraphNode(lockName), fair); 268 } 269 270 // A static mapping from an Enum type to its set of LockGraphNodes. 271 private static final ConcurrentMap<Class<? extends Enum>, Map<? extends Enum, LockGraphNode>> 272 lockGraphNodesPerType = new MapMaker().weakKeys().makeMap(); 273 274 /** Creates a {@code CycleDetectingLockFactory.WithExplicitOrdering<E>}. */ 275 public static <E extends Enum<E>> WithExplicitOrdering<E> newInstanceWithExplicitOrdering( 276 Class<E> enumClass, Policy policy) { 277 // createNodes maps each enumClass to a Map with the corresponding enum key 278 // type. 279 checkNotNull(enumClass); 280 checkNotNull(policy); 281 @SuppressWarnings("unchecked") 282 Map<E, LockGraphNode> lockGraphNodes = (Map<E, LockGraphNode>) getOrCreateNodes(enumClass); 283 return new WithExplicitOrdering<E>(policy, lockGraphNodes); 284 } 285 286 private static Map<? extends Enum, LockGraphNode> getOrCreateNodes(Class<? extends Enum> clazz) { 287 Map<? extends Enum, LockGraphNode> existing = lockGraphNodesPerType.get(clazz); 288 if (existing != null) { 289 return existing; 290 } 291 Map<? extends Enum, LockGraphNode> created = createNodes(clazz); 292 existing = lockGraphNodesPerType.putIfAbsent(clazz, created); 293 return MoreObjects.firstNonNull(existing, created); 294 } 295 296 /** 297 * For a given Enum type, creates an immutable map from each of the Enum's values to a 298 * corresponding LockGraphNode, with the {@code allowedPriorLocks} and {@code 299 * disallowedPriorLocks} prepopulated with nodes according to the natural ordering of the 300 * associated Enum values. 301 */ 302 @VisibleForTesting 303 static <E extends Enum<E>> Map<E, LockGraphNode> createNodes(Class<E> clazz) { 304 EnumMap<E, LockGraphNode> map = Maps.newEnumMap(clazz); 305 E[] keys = clazz.getEnumConstants(); 306 final int numKeys = keys.length; 307 ArrayList<LockGraphNode> nodes = Lists.newArrayListWithCapacity(numKeys); 308 // Create a LockGraphNode for each enum value. 309 for (E key : keys) { 310 LockGraphNode node = new LockGraphNode(getLockName(key)); 311 nodes.add(node); 312 map.put(key, node); 313 } 314 // Pre-populate all allowedPriorLocks with nodes of smaller ordinal. 315 for (int i = 1; i < numKeys; i++) { 316 nodes.get(i).checkAcquiredLocks(Policies.THROW, nodes.subList(0, i)); 317 } 318 // Pre-populate all disallowedPriorLocks with nodes of larger ordinal. 319 for (int i = 0; i < numKeys - 1; i++) { 320 nodes.get(i).checkAcquiredLocks(Policies.DISABLED, nodes.subList(i + 1, numKeys)); 321 } 322 return Collections.unmodifiableMap(map); 323 } 324 325 /** 326 * For the given Enum value {@code rank}, returns the value's {@code "EnumClass.name"}, which is 327 * used in exception and warning output. 328 */ 329 private static String getLockName(Enum<?> rank) { 330 return rank.getDeclaringClass().getSimpleName() + "." + rank.name(); 331 } 332 333 /** 334 * A {@code CycleDetectingLockFactory.WithExplicitOrdering} provides the additional enforcement of 335 * an application-specified ordering of lock acquisitions. The application defines the allowed 336 * ordering with an {@code Enum} whose values each correspond to a lock type. The order in which 337 * the values are declared dictates the allowed order of lock acquisition. In other words, locks 338 * corresponding to smaller values of {@link Enum#ordinal()} should only be acquired before locks 339 * with larger ordinals. Example: 340 * 341 * <pre>{@code 342 * enum MyLockOrder { 343 * FIRST, SECOND, THIRD; 344 * } 345 * 346 * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory = 347 * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(Policies.THROW); 348 * 349 * Lock lock1 = factory.newReentrantLock(MyLockOrder.FIRST); 350 * Lock lock2 = factory.newReentrantLock(MyLockOrder.SECOND); 351 * Lock lock3 = factory.newReentrantLock(MyLockOrder.THIRD); 352 * 353 * lock1.lock(); 354 * lock3.lock(); 355 * lock2.lock(); // will throw an IllegalStateException 356 * }</pre> 357 * 358 * <p>As with all locks created by instances of {@code CycleDetectingLockFactory} explicitly 359 * ordered locks participate in general cycle detection with all other cycle detecting locks, and 360 * a lock's behavior when detecting a cyclic lock acquisition is defined by the {@code Policy} of 361 * the factory that created it. 362 * 363 * <p>Note, however, that although multiple locks can be created for a given Enum value, whether 364 * it be through separate factory instances or through multiple calls to the same factory, 365 * attempting to acquire multiple locks with the same Enum value (within the same thread) will 366 * result in an IllegalStateException regardless of the factory's policy. For example: 367 * 368 * <pre>{@code 369 * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory1 = 370 * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...); 371 * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory2 = 372 * CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...); 373 * 374 * Lock lockA = factory1.newReentrantLock(MyLockOrder.FIRST); 375 * Lock lockB = factory1.newReentrantLock(MyLockOrder.FIRST); 376 * Lock lockC = factory2.newReentrantLock(MyLockOrder.FIRST); 377 * 378 * lockA.lock(); 379 * 380 * lockB.lock(); // will throw an IllegalStateException 381 * lockC.lock(); // will throw an IllegalStateException 382 * 383 * lockA.lock(); // reentrant acquisition is okay 384 * }</pre> 385 * 386 * <p>It is the responsibility of the application to ensure that multiple lock instances with the 387 * same rank are never acquired in the same thread. 388 * 389 * @param <E> The Enum type representing the explicit lock ordering. 390 * @since 13.0 391 */ 392 @Beta 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 : new CycleDetectingReentrantLock(lockGraphNodes.get(rank), fair); 421 } 422 423 /** Equivalent to {@code newReentrantReadWriteLock(rank, false)}. */ 424 public ReentrantReadWriteLock newReentrantReadWriteLock(E rank) { 425 return newReentrantReadWriteLock(rank, false); 426 } 427 428 /** 429 * Creates a {@link ReentrantReadWriteLock} with the given fairness policy and rank. The values 430 * returned by {@link Enum#getDeclaringClass()} and {@link Enum#name()} are used to describe the 431 * lock in warning or exception output. 432 * 433 * @throws IllegalStateException If the factory has already created a {@code Lock} with the 434 * specified rank. 435 */ 436 public ReentrantReadWriteLock newReentrantReadWriteLock(E rank, boolean fair) { 437 return policy == Policies.DISABLED 438 ? new ReentrantReadWriteLock(fair) 439 : new CycleDetectingReentrantReadWriteLock(lockGraphNodes.get(rank), fair); 440 } 441 } 442 443 //////// Implementation ///////// 444 445 private static final Logger logger = Logger.getLogger(CycleDetectingLockFactory.class.getName()); 446 447 final Policy policy; 448 449 private CycleDetectingLockFactory(Policy policy) { 450 this.policy = checkNotNull(policy); 451 } 452 453 /** 454 * Tracks the currently acquired locks for each Thread, kept up to date by calls to {@link 455 * #aboutToAcquire(CycleDetectingLock)} and {@link #lockStateChanged(CycleDetectingLock)}. 456 */ 457 // This is logically a Set, but an ArrayList is used to minimize the amount 458 // of allocation done on lock()/unlock(). 459 private static final ThreadLocal<ArrayList<LockGraphNode>> acquiredLocks = 460 new ThreadLocal<ArrayList<LockGraphNode>>() { 461 @Override 462 protected ArrayList<LockGraphNode> initialValue() { 463 return Lists.<LockGraphNode>newArrayListWithCapacity(3); 464 } 465 }; 466 467 /** 468 * A Throwable used to record a stack trace that illustrates an example of a specific lock 469 * acquisition ordering. The top of the stack trace is truncated such that it starts with the 470 * acquisition of the lock in question, e.g. 471 * 472 * <pre> 473 * com...ExampleStackTrace: LockB -> LockC 474 * at com...CycleDetectingReentrantLock.lock(CycleDetectingLockFactory.java:443) 475 * at ... 476 * at ... 477 * at com...MyClass.someMethodThatAcquiresLockB(MyClass.java:123) 478 * </pre> 479 */ 480 private static class ExampleStackTrace extends IllegalStateException { 481 482 static final StackTraceElement[] EMPTY_STACK_TRACE = new StackTraceElement[0]; 483 484 static final ImmutableSet<String> EXCLUDED_CLASS_NAMES = 485 ImmutableSet.of( 486 CycleDetectingLockFactory.class.getName(), 487 ExampleStackTrace.class.getName(), 488 LockGraphNode.class.getName()); 489 490 ExampleStackTrace(LockGraphNode node1, LockGraphNode node2) { 491 super(node1.getLockName() + " -> " + node2.getLockName()); 492 StackTraceElement[] origStackTrace = getStackTrace(); 493 for (int i = 0, n = origStackTrace.length; i < n; i++) { 494 if (WithExplicitOrdering.class.getName().equals(origStackTrace[i].getClassName())) { 495 // For pre-populated disallowedPriorLocks edges, omit the stack trace. 496 setStackTrace(EMPTY_STACK_TRACE); 497 break; 498 } 499 if (!EXCLUDED_CLASS_NAMES.contains(origStackTrace[i].getClassName())) { 500 setStackTrace(Arrays.copyOfRange(origStackTrace, i, n)); 501 break; 502 } 503 } 504 } 505 } 506 507 /** 508 * Represents a detected cycle in lock acquisition ordering. The exception includes a causal chain 509 * of {@code ExampleStackTrace} instances to illustrate the cycle, e.g. 510 * 511 * <pre> 512 * com....PotentialDeadlockException: Potential Deadlock from LockC -> ReadWriteA 513 * at ... 514 * at ... 515 * Caused by: com...ExampleStackTrace: LockB -> LockC 516 * at ... 517 * at ... 518 * Caused by: com...ExampleStackTrace: ReadWriteA -> LockB 519 * at ... 520 * at ... 521 * </pre> 522 * 523 * <p>Instances are logged for the {@code Policies.WARN}, and thrown for {@code Policies.THROW}. 524 * 525 * @since 13.0 526 */ 527 @Beta 528 public static final class PotentialDeadlockException extends ExampleStackTrace { 529 530 private final ExampleStackTrace conflictingStackTrace; 531 532 private PotentialDeadlockException( 533 LockGraphNode node1, LockGraphNode node2, ExampleStackTrace conflictingStackTrace) { 534 super(node1, node2); 535 this.conflictingStackTrace = conflictingStackTrace; 536 initCause(conflictingStackTrace); 537 } 538 539 public ExampleStackTrace getConflictingStackTrace() { 540 return conflictingStackTrace; 541 } 542 543 /** 544 * Appends the chain of messages from the {@code conflictingStackTrace} to the original {@code 545 * message}. 546 */ 547 @Override 548 public String getMessage() { 549 StringBuilder message = new StringBuilder(super.getMessage()); 550 for (Throwable t = conflictingStackTrace; t != null; t = t.getCause()) { 551 message.append(", ").append(t.getMessage()); 552 } 553 return message.toString(); 554 } 555 } 556 557 /** 558 * Internal Lock implementations implement the {@code CycleDetectingLock} interface, allowing the 559 * detection logic to treat all locks in the same manner. 560 */ 561 private interface CycleDetectingLock { 562 563 /** @return the {@link LockGraphNode} associated with this lock. */ 564 LockGraphNode getLockGraphNode(); 565 566 /** @return {@code true} if the current thread has acquired this lock. */ 567 boolean isAcquiredByCurrentThread(); 568 } 569 570 /** 571 * A {@code LockGraphNode} associated with each lock instance keeps track of the directed edges in 572 * the lock acquisition graph. 573 */ 574 private static class LockGraphNode { 575 576 /** 577 * The map tracking the locks that are known to be acquired before this lock, each associated 578 * with an example stack trace. Locks are weakly keyed to allow proper garbage collection when 579 * they are no longer referenced. 580 */ 581 final Map<LockGraphNode, ExampleStackTrace> allowedPriorLocks = 582 new MapMaker().weakKeys().makeMap(); 583 584 /** 585 * The map tracking lock nodes that can cause a lock acquisition cycle if acquired before this 586 * node. 587 */ 588 final Map<LockGraphNode, PotentialDeadlockException> disallowedPriorLocks = 589 new MapMaker().weakKeys().makeMap(); 590 591 final String lockName; 592 593 LockGraphNode(String lockName) { 594 this.lockName = Preconditions.checkNotNull(lockName); 595 } 596 597 String getLockName() { 598 return lockName; 599 } 600 601 void checkAcquiredLocks(Policy policy, List<LockGraphNode> acquiredLocks) { 602 for (int i = 0, size = acquiredLocks.size(); i < size; i++) { 603 checkAcquiredLock(policy, acquiredLocks.get(i)); 604 } 605 } 606 607 /** 608 * Checks the acquisition-ordering between {@code this}, which is about to be acquired, and the 609 * specified {@code acquiredLock}. 610 * 611 * <p>When this method returns, the {@code acquiredLock} should be in either the {@code 612 * preAcquireLocks} map, for the case in which it is safe to acquire {@code this} after the 613 * {@code acquiredLock}, or in the {@code disallowedPriorLocks} map, in which case it is not 614 * safe. 615 */ 616 void checkAcquiredLock(Policy policy, LockGraphNode acquiredLock) { 617 // checkAcquiredLock() should never be invoked by a lock that has already 618 // been acquired. For unordered locks, aboutToAcquire() ensures this by 619 // checking isAcquiredByCurrentThread(). For ordered locks, however, this 620 // can happen because multiple locks may share the same LockGraphNode. In 621 // this situation, throw an IllegalStateException as defined by contract 622 // described in the documentation of WithExplicitOrdering. 623 Preconditions.checkState( 624 this != acquiredLock, 625 "Attempted to acquire multiple locks with the same rank %s", 626 acquiredLock.getLockName()); 627 628 if (allowedPriorLocks.containsKey(acquiredLock)) { 629 // The acquisition ordering from "acquiredLock" to "this" has already 630 // been verified as safe. In a properly written application, this is 631 // the common case. 632 return; 633 } 634 PotentialDeadlockException previousDeadlockException = disallowedPriorLocks.get(acquiredLock); 635 if (previousDeadlockException != null) { 636 // Previously determined to be an unsafe lock acquisition. 637 // Create a new PotentialDeadlockException with the same causal chain 638 // (the example cycle) as that of the cached exception. 639 PotentialDeadlockException exception = 640 new PotentialDeadlockException( 641 acquiredLock, this, previousDeadlockException.getConflictingStackTrace()); 642 policy.handlePotentialDeadlock(exception); 643 return; 644 } 645 // Otherwise, it's the first time seeing this lock relationship. Look for 646 // a path from the acquiredLock to this. 647 Set<LockGraphNode> seen = Sets.newIdentityHashSet(); 648 ExampleStackTrace path = acquiredLock.findPathTo(this, seen); 649 650 if (path == null) { 651 // this can be safely acquired after the acquiredLock. 652 // 653 // Note that there is a race condition here which can result in missing 654 // a cyclic edge: it's possible for two threads to simultaneous find 655 // "safe" edges which together form a cycle. Preventing this race 656 // condition efficiently without _introducing_ deadlock is probably 657 // tricky. For now, just accept the race condition---missing a warning 658 // now and then is still better than having no deadlock detection. 659 allowedPriorLocks.put(acquiredLock, new ExampleStackTrace(acquiredLock, this)); 660 } else { 661 // Unsafe acquisition order detected. Create and cache a 662 // PotentialDeadlockException. 663 PotentialDeadlockException exception = 664 new PotentialDeadlockException(acquiredLock, this, path); 665 disallowedPriorLocks.put(acquiredLock, exception); 666 policy.handlePotentialDeadlock(exception); 667 } 668 } 669 670 /** 671 * Performs a depth-first traversal of the graph edges defined by each node's {@code 672 * allowedPriorLocks} to find a path between {@code this} and the specified {@code lock}. 673 * 674 * @return If a path was found, a chained {@link ExampleStackTrace} illustrating the path to the 675 * {@code lock}, or {@code null} if no path was found. 676 */ 677 private @Nullable ExampleStackTrace findPathTo(LockGraphNode node, Set<LockGraphNode> seen) { 678 if (!seen.add(this)) { 679 return null; // Already traversed this node. 680 } 681 ExampleStackTrace found = allowedPriorLocks.get(node); 682 if (found != null) { 683 return found; // Found a path ending at the node! 684 } 685 // Recurse the edges. 686 for (Entry<LockGraphNode, ExampleStackTrace> entry : allowedPriorLocks.entrySet()) { 687 LockGraphNode preAcquiredLock = entry.getKey(); 688 found = preAcquiredLock.findPathTo(node, seen); 689 if (found != null) { 690 // One of this node's allowedPriorLocks found a path. Prepend an 691 // ExampleStackTrace(preAcquiredLock, this) to the returned chain of 692 // ExampleStackTraces. 693 ExampleStackTrace path = new ExampleStackTrace(preAcquiredLock, this); 694 path.setStackTrace(entry.getValue().getStackTrace()); 695 path.initCause(found); 696 return path; 697 } 698 } 699 return null; 700 } 701 } 702 703 /** 704 * CycleDetectingLock implementations must call this method before attempting to acquire the lock. 705 */ 706 private void aboutToAcquire(CycleDetectingLock lock) { 707 if (!lock.isAcquiredByCurrentThread()) { 708 ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get(); 709 LockGraphNode node = lock.getLockGraphNode(); 710 node.checkAcquiredLocks(policy, acquiredLockList); 711 acquiredLockList.add(node); 712 } 713 } 714 715 /** 716 * CycleDetectingLock implementations must call this method in a {@code finally} clause after any 717 * attempt to change the lock state, including both lock and unlock attempts. Failure to do so can 718 * result in corrupting the acquireLocks set. 719 */ 720 private static void lockStateChanged(CycleDetectingLock lock) { 721 if (!lock.isAcquiredByCurrentThread()) { 722 ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get(); 723 LockGraphNode node = lock.getLockGraphNode(); 724 // Iterate in reverse because locks are usually locked/unlocked in a 725 // LIFO order. 726 for (int i = acquiredLockList.size() - 1; i >= 0; i--) { 727 if (acquiredLockList.get(i) == node) { 728 acquiredLockList.remove(i); 729 break; 730 } 731 } 732 } 733 } 734 735 final class CycleDetectingReentrantLock extends ReentrantLock implements CycleDetectingLock { 736 737 private final LockGraphNode lockGraphNode; 738 739 private CycleDetectingReentrantLock(LockGraphNode lockGraphNode, boolean fair) { 740 super(fair); 741 this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode); 742 } 743 744 ///// CycleDetectingLock methods. ///// 745 746 @Override 747 public LockGraphNode getLockGraphNode() { 748 return lockGraphNode; 749 } 750 751 @Override 752 public boolean isAcquiredByCurrentThread() { 753 return isHeldByCurrentThread(); 754 } 755 756 ///// Overridden ReentrantLock methods. ///// 757 758 @Override 759 public void lock() { 760 aboutToAcquire(this); 761 try { 762 super.lock(); 763 } finally { 764 lockStateChanged(this); 765 } 766 } 767 768 @Override 769 public void lockInterruptibly() throws InterruptedException { 770 aboutToAcquire(this); 771 try { 772 super.lockInterruptibly(); 773 } finally { 774 lockStateChanged(this); 775 } 776 } 777 778 @Override 779 public boolean tryLock() { 780 aboutToAcquire(this); 781 try { 782 return super.tryLock(); 783 } finally { 784 lockStateChanged(this); 785 } 786 } 787 788 @Override 789 public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException { 790 aboutToAcquire(this); 791 try { 792 return super.tryLock(timeout, unit); 793 } finally { 794 lockStateChanged(this); 795 } 796 } 797 798 @Override 799 public void unlock() { 800 try { 801 super.unlock(); 802 } finally { 803 lockStateChanged(this); 804 } 805 } 806 } 807 808 final class CycleDetectingReentrantReadWriteLock extends ReentrantReadWriteLock 809 implements CycleDetectingLock { 810 811 // These ReadLock/WriteLock implementations shadow those in the 812 // ReentrantReadWriteLock superclass. They are simply wrappers around the 813 // internal Sync object, so this is safe since the shadowed locks are never 814 // exposed or used. 815 private final CycleDetectingReentrantReadLock readLock; 816 private final CycleDetectingReentrantWriteLock writeLock; 817 818 private final LockGraphNode lockGraphNode; 819 820 private CycleDetectingReentrantReadWriteLock(LockGraphNode lockGraphNode, boolean fair) { 821 super(fair); 822 this.readLock = new CycleDetectingReentrantReadLock(this); 823 this.writeLock = new CycleDetectingReentrantWriteLock(this); 824 this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode); 825 } 826 827 ///// Overridden ReentrantReadWriteLock methods. ///// 828 829 @Override 830 public ReadLock readLock() { 831 return readLock; 832 } 833 834 @Override 835 public WriteLock writeLock() { 836 return writeLock; 837 } 838 839 ///// CycleDetectingLock methods. ///// 840 841 @Override 842 public LockGraphNode getLockGraphNode() { 843 return lockGraphNode; 844 } 845 846 @Override 847 public boolean isAcquiredByCurrentThread() { 848 return isWriteLockedByCurrentThread() || getReadHoldCount() > 0; 849 } 850 } 851 852 private class CycleDetectingReentrantReadLock extends ReentrantReadWriteLock.ReadLock { 853 854 @Weak final CycleDetectingReentrantReadWriteLock readWriteLock; 855 856 CycleDetectingReentrantReadLock(CycleDetectingReentrantReadWriteLock readWriteLock) { 857 super(readWriteLock); 858 this.readWriteLock = readWriteLock; 859 } 860 861 @Override 862 public void lock() { 863 aboutToAcquire(readWriteLock); 864 try { 865 super.lock(); 866 } finally { 867 lockStateChanged(readWriteLock); 868 } 869 } 870 871 @Override 872 public void lockInterruptibly() throws InterruptedException { 873 aboutToAcquire(readWriteLock); 874 try { 875 super.lockInterruptibly(); 876 } finally { 877 lockStateChanged(readWriteLock); 878 } 879 } 880 881 @Override 882 public boolean tryLock() { 883 aboutToAcquire(readWriteLock); 884 try { 885 return super.tryLock(); 886 } finally { 887 lockStateChanged(readWriteLock); 888 } 889 } 890 891 @Override 892 public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException { 893 aboutToAcquire(readWriteLock); 894 try { 895 return super.tryLock(timeout, unit); 896 } finally { 897 lockStateChanged(readWriteLock); 898 } 899 } 900 901 @Override 902 public void unlock() { 903 try { 904 super.unlock(); 905 } finally { 906 lockStateChanged(readWriteLock); 907 } 908 } 909 } 910 911 private class CycleDetectingReentrantWriteLock extends ReentrantReadWriteLock.WriteLock { 912 913 @Weak final CycleDetectingReentrantReadWriteLock readWriteLock; 914 915 CycleDetectingReentrantWriteLock(CycleDetectingReentrantReadWriteLock readWriteLock) { 916 super(readWriteLock); 917 this.readWriteLock = readWriteLock; 918 } 919 920 @Override 921 public void lock() { 922 aboutToAcquire(readWriteLock); 923 try { 924 super.lock(); 925 } finally { 926 lockStateChanged(readWriteLock); 927 } 928 } 929 930 @Override 931 public void lockInterruptibly() throws InterruptedException { 932 aboutToAcquire(readWriteLock); 933 try { 934 super.lockInterruptibly(); 935 } finally { 936 lockStateChanged(readWriteLock); 937 } 938 } 939 940 @Override 941 public boolean tryLock() { 942 aboutToAcquire(readWriteLock); 943 try { 944 return super.tryLock(); 945 } finally { 946 lockStateChanged(readWriteLock); 947 } 948 } 949 950 @Override 951 public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException { 952 aboutToAcquire(readWriteLock); 953 try { 954 return super.tryLock(timeout, unit); 955 } finally { 956 lockStateChanged(readWriteLock); 957 } 958 } 959 960 @Override 961 public void unlock() { 962 try { 963 super.unlock(); 964 } finally { 965 lockStateChanged(readWriteLock); 966 } 967 } 968 } 969}