com.google.guava/guava/30.0-jre : com/google/common/util/concurrent/CycleDetectingLockFactory.java

CycleDetectingLockFactory
https://github.com/google/guava/guava: Guava is a suite of core and expanded libraries that include utility classes, google's collections, io classes, and much much more.
Apache License, Version 2.0
Kevin Bourrillion (Google)
/*
 * Copyright (C) 2011 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.util.concurrent;

import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.MoreObjects;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.collect.MapMaker;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.j2objc.annotations.Weak;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.EnumMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.checkerframework.checker.nullness.qual.Nullable;

The CycleDetectingLockFactory creates ReentrantLock instances and ReentrantReadWriteLock instances that detect potential deadlock by checking for cycles in lock acquisition order. Potential deadlocks detected when calling the lock(), lockInterruptibly(), or tryLock() methods will result in the execution of the Policy specified when creating the factory. The currently available policies are: 

  DISABLED
  
WARN
  
THROW

The locks created by a factory instance will detect lock acquisition cycles with locks created by other CycleDetectingLockFactory instances (except those with Policy.DISABLED). A lock's behavior when a cycle is detected, however, is defined by the Policy of the factory that created it. This allows detection of cycles across components while delegating control over lock behavior to individual components. 
Applications are encouraged to use a CycleDetectingLockFactory to create any locks for which external/unmanaged code is executed while the lock is held. (See caveats under Performance).
Cycle Detection
Deadlocks can arise when locks are acquired in an order that forms a cycle. In a simple
example involving two locks and two threads, deadlock occurs when one thread acquires Lock A, and
then Lock B, while another thread acquires Lock B, and then Lock A:
Thread1: acquire(LockA) --X acquire(LockB)
Thread2: acquire(LockB) --X acquire(LockA)

Neither thread will progress because each is waiting for the other. In more complex
applications, cycles can arise from interactions among more than 2 locks:
Thread1: acquire(LockA) --X acquire(LockB)
Thread2: acquire(LockB) --X acquire(LockC)
...
ThreadN: acquire(LockN) --X acquire(LockA)

The implementation detects cycles by constructing a directed graph in which each lock
represents a node and each edge represents an acquisition ordering between two locks.

  Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired locks when the
      Thread acquires its first hold (and releases its last remaining hold).
  
Before the lock is acquired, the lock is checked against the current set of acquired
      locks---to each of the acquired locks, an edge from the soon-to-be-acquired lock is either
      verified or created.
  
If a new edge needs to be created, the outgoing edges of the acquired locks are traversed
      to check for a cycle that reaches the lock to be acquired. If no cycle is detected, a new
      "safe" edge is created.
  
If a cycle is detected, an "unsafe" (cyclic) edge is created to represent a potential
      deadlock situation, and the appropriate Policy is executed.

Note that detection of potential deadlock does not necessarily indicate that deadlock will
happen, as it is possible that higher level application logic prevents the cyclic lock
acquisition from occurring. One example of a false positive is:
LockA -> LockB -> LockC
LockA -> LockC -> LockB

ReadWriteLocks
While ReadWriteLock instances have different properties and can form cycles without potential deadlock, this class treats ReadWriteLock instances as equivalent to traditional exclusive locks. Although this increases the false positives that the locks detect (i.e. cycles that will not actually result in deadlock), it simplifies the algorithm and implementation considerably. The assumption is that a user of this factory wishes to eliminate any cyclic acquisition ordering. 
Explicit Lock Acquisition Ordering
The WithExplicitOrdering class can be used to enforce an application-specific ordering in addition to performing general cycle detection. 
Garbage Collection
In order to allow proper garbage collection of unused locks, the edges of the lock graph are
weak references.
Performance
The extra bookkeeping done by cycle detecting locks comes at some cost to performance.
Benchmarks (as of December 2011) show that:

  for an unnested lock() and unlock(), a cycle detecting lock takes 38ns as opposed to the 24ns taken by a plain lock. 
for nested locking, the cost increases with the depth of the nesting:
      
        2 levels: average of 64ns per lock()/unlock()
        
3 levels: average of 77ns per lock()/unlock()
        
4 levels: average of 99ns per lock()/unlock()
        
5 levels: average of 103ns per lock()/unlock()
        
10 levels: average of 184ns per lock()/unlock()
        
20 levels: average of 393ns per lock()/unlock()
      

As such, the CycleDetectingLockFactory may not be suitable for performance-critical
applications which involve tightly-looped or deeply-nested locking algorithms.
Author: Darick Tong
Since: 13.0/**
 * The {@code CycleDetectingLockFactory} creates {@link ReentrantLock} instances and {@link
 * ReentrantReadWriteLock} instances that detect potential deadlock by checking for cycles in lock
 * acquisition order.
 *
 * <p>Potential deadlocks detected when calling the {@code lock()}, {@code lockInterruptibly()}, or
 * {@code tryLock()} methods will result in the execution of the {@link Policy} specified when
 * creating the factory. The currently available policies are:
 *
 * <ul>
 *   <li>DISABLED
 *   <li>WARN
 *   <li>THROW
 * </ul>
 *
 * <p>The locks created by a factory instance will detect lock acquisition cycles with locks created
 * by other {@code CycleDetectingLockFactory} instances (except those with {@code Policy.DISABLED}).
 * A lock's behavior when a cycle is detected, however, is defined by the {@code Policy} of the
 * factory that created it. This allows detection of cycles across components while delegating
 * control over lock behavior to individual components.
 *
 * <p>Applications are encouraged to use a {@code CycleDetectingLockFactory} to create any locks for
 * which external/unmanaged code is executed while the lock is held. (See caveats under
 * <strong>Performance</strong>).
 *
 * <p><strong>Cycle Detection</strong>
 *
 * <p>Deadlocks can arise when locks are acquired in an order that forms a cycle. In a simple
 * example involving two locks and two threads, deadlock occurs when one thread acquires Lock A, and
 * then Lock B, while another thread acquires Lock B, and then Lock A:
 *
 * <pre>
 * Thread1: acquire(LockA) --X acquire(LockB)
 * Thread2: acquire(LockB) --X acquire(LockA)
 * </pre>
 *
 * <p>Neither thread will progress because each is waiting for the other. In more complex
 * applications, cycles can arise from interactions among more than 2 locks:
 *
 * <pre>
 * Thread1: acquire(LockA) --X acquire(LockB)
 * Thread2: acquire(LockB) --X acquire(LockC)
 * ...
 * ThreadN: acquire(LockN) --X acquire(LockA)
 * </pre>
 *
 * <p>The implementation detects cycles by constructing a directed graph in which each lock
 * represents a node and each edge represents an acquisition ordering between two locks.
 *
 * <ul>
 *   <li>Each lock adds (and removes) itself to/from a ThreadLocal Set of acquired locks when the
 *       Thread acquires its first hold (and releases its last remaining hold).
 *   <li>Before the lock is acquired, the lock is checked against the current set of acquired
 *       locks---to each of the acquired locks, an edge from the soon-to-be-acquired lock is either
 *       verified or created.
 *   <li>If a new edge needs to be created, the outgoing edges of the acquired locks are traversed
 *       to check for a cycle that reaches the lock to be acquired. If no cycle is detected, a new
 *       "safe" edge is created.
 *   <li>If a cycle is detected, an "unsafe" (cyclic) edge is created to represent a potential
 *       deadlock situation, and the appropriate Policy is executed.
 * </ul>
 *
 * <p>Note that detection of potential deadlock does not necessarily indicate that deadlock will
 * happen, as it is possible that higher level application logic prevents the cyclic lock
 * acquisition from occurring. One example of a false positive is:
 *
 * <pre>
 * LockA -&gt; LockB -&gt; LockC
 * LockA -&gt; LockC -&gt; LockB
 * </pre>
 *
 * <p><strong>ReadWriteLocks</strong>
 *
 * <p>While {@code ReadWriteLock} instances have different properties and can form cycles without
 * potential deadlock, this class treats {@code ReadWriteLock} instances as equivalent to
 * traditional exclusive locks. Although this increases the false positives that the locks detect
 * (i.e. cycles that will not actually result in deadlock), it simplifies the algorithm and
 * implementation considerably. The assumption is that a user of this factory wishes to eliminate
 * any cyclic acquisition ordering.
 *
 * <p><strong>Explicit Lock Acquisition Ordering</strong>
 *
 * <p>The {@link CycleDetectingLockFactory.WithExplicitOrdering} class can be used to enforce an
 * application-specific ordering in addition to performing general cycle detection.
 *
 * <p><strong>Garbage Collection</strong>
 *
 * <p>In order to allow proper garbage collection of unused locks, the edges of the lock graph are
 * weak references.
 *
 * <p><strong>Performance</strong>
 *
 * <p>The extra bookkeeping done by cycle detecting locks comes at some cost to performance.
 * Benchmarks (as of December 2011) show that:
 *
 * <ul>
 *   <li>for an unnested {@code lock()} and {@code unlock()}, a cycle detecting lock takes 38ns as
 *       opposed to the 24ns taken by a plain lock.
 *   <li>for nested locking, the cost increases with the depth of the nesting:
 *       <ul>
 *         <li>2 levels: average of 64ns per lock()/unlock()
 *         <li>3 levels: average of 77ns per lock()/unlock()
 *         <li>4 levels: average of 99ns per lock()/unlock()
 *         <li>5 levels: average of 103ns per lock()/unlock()
 *         <li>10 levels: average of 184ns per lock()/unlock()
 *         <li>20 levels: average of 393ns per lock()/unlock()
 *       </ul>
 * </ul>
 *
 * <p>As such, the CycleDetectingLockFactory may not be suitable for performance-critical
 * applications which involve tightly-looped or deeply-nested locking algorithms.
 *
 * @author Darick Tong
 * @since 13.0
 */
@Beta
@CanIgnoreReturnValue // TODO(cpovirk): Consider being more strict.
@GwtIncompatible
public class CycleDetectingLockFactory {

  Encapsulates the action to be taken when a potential deadlock is encountered. Clients can use one of the predefined Policies or specify a custom implementation. Implementations must be thread-safe. 
Since: 13.0/**
   * Encapsulates the action to be taken when a potential deadlock is encountered. Clients can use
   * one of the predefined {@link Policies} or specify a custom implementation. Implementations must
   * be thread-safe.
   *
   * @since 13.0
   */
  @Beta
  public interface Policy {

    Called when a potential deadlock is encountered. Implementations can throw the given 
exception and/or execute other desired logic. Note that the method will be called even upon an invocation of tryLock(). Although tryLock() technically recovers from deadlock by eventually timing out, this behavior is chosen based on the assumption that it is the application's wish to prohibit any cyclical lock acquisitions. /**
     * Called when a potential deadlock is encountered. Implementations can throw the given {@code
     * exception} and/or execute other desired logic.
     *
     * <p>Note that the method will be called even upon an invocation of {@code tryLock()}. Although
     * {@code tryLock()} technically recovers from deadlock by eventually timing out, this behavior
     * is chosen based on the assumption that it is the application's wish to prohibit any cyclical
     * lock acquisitions.
     */
    void handlePotentialDeadlock(PotentialDeadlockException exception);
  }

  Pre-defined Policy implementations. 
Since: 13.0/**
   * Pre-defined {@link Policy} implementations.
   *
   * @since 13.0
   */
  @Beta
  public enum Policies implements Policy {
    When potential deadlock is detected, this policy results in the throwing of the 
PotentialDeadlockException indicating the potential deadlock, which includes stack traces illustrating the cycle in lock acquisition order. /**
     * When potential deadlock is detected, this policy results in the throwing of the {@code
     * PotentialDeadlockException} indicating the potential deadlock, which includes stack traces
     * illustrating the cycle in lock acquisition order.
     */
    THROW {
      @Override
      public void handlePotentialDeadlock(PotentialDeadlockException e) {
        throw e;
      }
    },

    When potential deadlock is detected, this policy results in the logging of a Level.SEVERE message indicating the potential deadlock, which includes stack traces illustrating the cycle in lock acquisition order. /**
     * When potential deadlock is detected, this policy results in the logging of a {@link
     * Level#SEVERE} message indicating the potential deadlock, which includes stack traces
     * illustrating the cycle in lock acquisition order.
     */
    WARN {
      @Override
      public void handlePotentialDeadlock(PotentialDeadlockException e) {
        logger.log(Level.SEVERE, "Detected potential deadlock", e);
      }
    },

    Disables cycle detection. This option causes the factory to return unmodified lock
implementations provided by the JDK, and is provided to allow applications to easily
parameterize when cycle detection is enabled.
Note that locks created by a factory with this policy will not participate the
cycle detection performed by locks created by other factories.
/**
     * Disables cycle detection. This option causes the factory to return unmodified lock
     * implementations provided by the JDK, and is provided to allow applications to easily
     * parameterize when cycle detection is enabled.
     *
     * <p>Note that locks created by a factory with this policy will <em>not</em> participate the
     * cycle detection performed by locks created by other factories.
     */
    DISABLED {
      @Override
      public void handlePotentialDeadlock(PotentialDeadlockException e) {}
    };
  }

  Creates a new factory with the specified policy. /** Creates a new factory with the specified policy. */
  public static CycleDetectingLockFactory newInstance(Policy policy) {
    return new CycleDetectingLockFactory(policy);
  }

  Equivalent to newReentrantLock(lockName, false). /** Equivalent to {@code newReentrantLock(lockName, false)}. */
  public ReentrantLock newReentrantLock(String lockName) {
    return newReentrantLock(lockName, false);
  }

  Creates a ReentrantLock with the given fairness policy. The lockName is used in the warning or exception output to help identify the locks involved in the detected deadlock. /**
   * Creates a {@link ReentrantLock} with the given fairness policy. The {@code lockName} is used in
   * the warning or exception output to help identify the locks involved in the detected deadlock.
   */
  public ReentrantLock newReentrantLock(String lockName, boolean fair) {
    return policy == Policies.DISABLED
        ? new ReentrantLock(fair)
        : new CycleDetectingReentrantLock(new LockGraphNode(lockName), fair);
  }

  Equivalent to newReentrantReadWriteLock(lockName, false). /** Equivalent to {@code newReentrantReadWriteLock(lockName, false)}. */
  public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName) {
    return newReentrantReadWriteLock(lockName, false);
  }

  Creates a ReentrantReadWriteLock with the given fairness policy. The lockName is used in the warning or exception output to help identify the locks involved in the detected deadlock. /**
   * Creates a {@link ReentrantReadWriteLock} with the given fairness policy. The {@code lockName}
   * is used in the warning or exception output to help identify the locks involved in the detected
   * deadlock.
   */
  public ReentrantReadWriteLock newReentrantReadWriteLock(String lockName, boolean fair) {
    return policy == Policies.DISABLED
        ? new ReentrantReadWriteLock(fair)
        : new CycleDetectingReentrantReadWriteLock(new LockGraphNode(lockName), fair);
  }

  // A static mapping from an Enum type to its set of LockGraphNodes.
  private static final ConcurrentMap<Class<? extends Enum>, Map<? extends Enum, LockGraphNode>>
      lockGraphNodesPerType = new MapMaker().weakKeys().makeMap();

  Creates a CycleDetectingLockFactory.WithExplicitOrdering<E>. /** Creates a {@code CycleDetectingLockFactory.WithExplicitOrdering<E>}. */
  public static <E extends Enum<E>> WithExplicitOrdering<E> newInstanceWithExplicitOrdering(
      Class<E> enumClass, Policy policy) {
    // createNodes maps each enumClass to a Map with the corresponding enum key
    // type.
    checkNotNull(enumClass);
    checkNotNull(policy);
    @SuppressWarnings("unchecked")
    Map<E, LockGraphNode> lockGraphNodes = (Map<E, LockGraphNode>) getOrCreateNodes(enumClass);
    return new WithExplicitOrdering<E>(policy, lockGraphNodes);
  }

  private static Map<? extends Enum, LockGraphNode> getOrCreateNodes(Class<? extends Enum> clazz) {
    Map<? extends Enum, LockGraphNode> existing = lockGraphNodesPerType.get(clazz);
    if (existing != null) {
      return existing;
    }
    Map<? extends Enum, LockGraphNode> created = createNodes(clazz);
    existing = lockGraphNodesPerType.putIfAbsent(clazz, created);
    return MoreObjects.firstNonNull(existing, created);
  }

  For a given Enum type, creates an immutable map from each of the Enum's values to a corresponding LockGraphNode, with the allowedPriorLocks and 
disallowedPriorLocks prepopulated with nodes according to the natural ordering of the associated Enum values. /**
   * For a given Enum type, creates an immutable map from each of the Enum's values to a
   * corresponding LockGraphNode, with the {@code allowedPriorLocks} and {@code
   * disallowedPriorLocks} prepopulated with nodes according to the natural ordering of the
   * associated Enum values.
   */
  @VisibleForTesting
  static <E extends Enum<E>> Map<E, LockGraphNode> createNodes(Class<E> clazz) {
    EnumMap<E, LockGraphNode> map = Maps.newEnumMap(clazz);
    E[] keys = clazz.getEnumConstants();
    final int numKeys = keys.length;
    ArrayList<LockGraphNode> nodes = Lists.newArrayListWithCapacity(numKeys);
    // Create a LockGraphNode for each enum value.
    for (E key : keys) {
      LockGraphNode node = new LockGraphNode(getLockName(key));
      nodes.add(node);
      map.put(key, node);
    }
    // Pre-populate all allowedPriorLocks with nodes of smaller ordinal.
    for (int i = 1; i < numKeys; i++) {
      nodes.get(i).checkAcquiredLocks(Policies.THROW, nodes.subList(0, i));
    }
    // Pre-populate all disallowedPriorLocks with nodes of larger ordinal.
    for (int i = 0; i < numKeys - 1; i++) {
      nodes.get(i).checkAcquiredLocks(Policies.DISABLED, nodes.subList(i + 1, numKeys));
    }
    return Collections.unmodifiableMap(map);
  }

  For the given Enum value rank, returns the value's "EnumClass.name", which is used in exception and warning output. /**
   * For the given Enum value {@code rank}, returns the value's {@code "EnumClass.name"}, which is
   * used in exception and warning output.
   */
  private static String getLockName(Enum<?> rank) {
    return rank.getDeclaringClass().getSimpleName() + "." + rank.name();
  }

  A CycleDetectingLockFactory.WithExplicitOrdering provides the additional enforcement of an application-specified ordering of lock acquisitions. The application defines the allowed ordering with an Enum whose values each correspond to a lock type. The order in which the values are declared dictates the allowed order of lock acquisition. In other words, locks corresponding to smaller values of Enum.ordinal() should only be acquired before locks with larger ordinals. Example: 
enum MyLockOrder {
  FIRST, SECOND, THIRD;
 }
CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory =
  CycleDetectingLockFactory.newInstanceWithExplicitOrdering(Policies.THROW);
Lock lock1 = factory.newReentrantLock(MyLockOrder.FIRST);
Lock lock2 = factory.newReentrantLock(MyLockOrder.SECOND);
Lock lock3 = factory.newReentrantLock(MyLockOrder.THIRD);
lock1.lock();
lock3.lock();
lock2.lock();  // will throw an IllegalStateException

As with all locks created by instances of CycleDetectingLockFactory explicitly ordered locks participate in general cycle detection with all other cycle detecting locks, and a lock's behavior when detecting a cyclic lock acquisition is defined by the Policy of the factory that created it. 
Note, however, that although multiple locks can be created for a given Enum value, whether
it be through separate factory instances or through multiple calls to the same factory,
attempting to acquire multiple locks with the same Enum value (within the same thread) will
result in an IllegalStateException regardless of the factory's policy. For example:

CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory1 =
  CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory2 =
  CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
Lock lockA = factory1.newReentrantLock(MyLockOrder.FIRST);
Lock lockB = factory1.newReentrantLock(MyLockOrder.FIRST);
Lock lockC = factory2.newReentrantLock(MyLockOrder.FIRST);
lockA.lock();
lockB.lock();  // will throw an IllegalStateException
lockC.lock();  // will throw an IllegalStateException
lockA.lock();  // reentrant acquisition is okay

It is the responsibility of the application to ensure that multiple lock instances with the
same rank are never acquired in the same thread.
Type parameters: <E> – The Enum type representing the explicit lock ordering.
Since: 13.0/**
   * A {@code CycleDetectingLockFactory.WithExplicitOrdering} provides the additional enforcement of
   * an application-specified ordering of lock acquisitions. The application defines the allowed
   * ordering with an {@code Enum} whose values each correspond to a lock type. The order in which
   * the values are declared dictates the allowed order of lock acquisition. In other words, locks
   * corresponding to smaller values of {@link Enum#ordinal()} should only be acquired before locks
   * with larger ordinals. Example:
   *
   * <pre>{@code
   * enum MyLockOrder {
   *   FIRST, SECOND, THIRD;
   * }
   *
   * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory =
   *   CycleDetectingLockFactory.newInstanceWithExplicitOrdering(Policies.THROW);
   *
   * Lock lock1 = factory.newReentrantLock(MyLockOrder.FIRST);
   * Lock lock2 = factory.newReentrantLock(MyLockOrder.SECOND);
   * Lock lock3 = factory.newReentrantLock(MyLockOrder.THIRD);
   *
   * lock1.lock();
   * lock3.lock();
   * lock2.lock();  // will throw an IllegalStateException
   * }</pre>
   *
   * <p>As with all locks created by instances of {@code CycleDetectingLockFactory} explicitly
   * ordered locks participate in general cycle detection with all other cycle detecting locks, and
   * a lock's behavior when detecting a cyclic lock acquisition is defined by the {@code Policy} of
   * the factory that created it.
   *
   * <p>Note, however, that although multiple locks can be created for a given Enum value, whether
   * it be through separate factory instances or through multiple calls to the same factory,
   * attempting to acquire multiple locks with the same Enum value (within the same thread) will
   * result in an IllegalStateException regardless of the factory's policy. For example:
   *
   * <pre>{@code
   * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory1 =
   *   CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
   * CycleDetectingLockFactory.WithExplicitOrdering<MyLockOrder> factory2 =
   *   CycleDetectingLockFactory.newInstanceWithExplicitOrdering(...);
   *
   * Lock lockA = factory1.newReentrantLock(MyLockOrder.FIRST);
   * Lock lockB = factory1.newReentrantLock(MyLockOrder.FIRST);
   * Lock lockC = factory2.newReentrantLock(MyLockOrder.FIRST);
   *
   * lockA.lock();
   *
   * lockB.lock();  // will throw an IllegalStateException
   * lockC.lock();  // will throw an IllegalStateException
   *
   * lockA.lock();  // reentrant acquisition is okay
   * }</pre>
   *
   * <p>It is the responsibility of the application to ensure that multiple lock instances with the
   * same rank are never acquired in the same thread.
   *
   * @param <E> The Enum type representing the explicit lock ordering.
   * @since 13.0
   */
  @Beta
  public static final class WithExplicitOrdering<E extends Enum<E>>
      extends CycleDetectingLockFactory {

    private final Map<E, LockGraphNode> lockGraphNodes;

    @VisibleForTesting
    WithExplicitOrdering(Policy policy, Map<E, LockGraphNode> lockGraphNodes) {
      super(policy);
      this.lockGraphNodes = lockGraphNodes;
    }

    Equivalent to newReentrantLock(rank, false). /** Equivalent to {@code newReentrantLock(rank, false)}. */
    public ReentrantLock newReentrantLock(E rank) {
      return newReentrantLock(rank, false);
    }

    Creates a ReentrantLock with the given fairness policy and rank. The values returned by Enum.getDeclaringClass() and Enum.name() are used to describe the lock in warning or exception output. 
Throws: IllegalStateException – If the factory has already created a Lock with the specified rank./**
     * Creates a {@link ReentrantLock} with the given fairness policy and rank. The values returned
     * by {@link Enum#getDeclaringClass()} and {@link Enum#name()} are used to describe the lock in
     * warning or exception output.
     *
     * @throws IllegalStateException If the factory has already created a {@code Lock} with the
     *     specified rank.
     */
    public ReentrantLock newReentrantLock(E rank, boolean fair) {
      return policy == Policies.DISABLED
          ? new ReentrantLock(fair)
          : new CycleDetectingReentrantLock(lockGraphNodes.get(rank), fair);
    }

    Equivalent to newReentrantReadWriteLock(rank, false). /** Equivalent to {@code newReentrantReadWriteLock(rank, false)}. */
    public ReentrantReadWriteLock newReentrantReadWriteLock(E rank) {
      return newReentrantReadWriteLock(rank, false);
    }

    Creates a ReentrantReadWriteLock with the given fairness policy and rank. The values returned by Enum.getDeclaringClass() and Enum.name() are used to describe the lock in warning or exception output. 
Throws: IllegalStateException – If the factory has already created a Lock with the specified rank./**
     * Creates a {@link ReentrantReadWriteLock} with the given fairness policy and rank. The values
     * returned by {@link Enum#getDeclaringClass()} and {@link Enum#name()} are used to describe the
     * lock in warning or exception output.
     *
     * @throws IllegalStateException If the factory has already created a {@code Lock} with the
     *     specified rank.
     */
    public ReentrantReadWriteLock newReentrantReadWriteLock(E rank, boolean fair) {
      return policy == Policies.DISABLED
          ? new ReentrantReadWriteLock(fair)
          : new CycleDetectingReentrantReadWriteLock(lockGraphNodes.get(rank), fair);
    }
  }

  //////// Implementation /////////

  private static final Logger logger = Logger.getLogger(CycleDetectingLockFactory.class.getName());

  final Policy policy;

  private CycleDetectingLockFactory(Policy policy) {
    this.policy = checkNotNull(policy);
  }

  Tracks the currently acquired locks for each Thread, kept up to date by calls to aboutToAcquire(CycleDetectingLock) and lockStateChanged(CycleDetectingLock). /**
   * Tracks the currently acquired locks for each Thread, kept up to date by calls to {@link
   * #aboutToAcquire(CycleDetectingLock)} and {@link #lockStateChanged(CycleDetectingLock)}.
   */
  // This is logically a Set, but an ArrayList is used to minimize the amount
  // of allocation done on lock()/unlock().
  private static final ThreadLocal<ArrayList<LockGraphNode>> acquiredLocks =
      new ThreadLocal<ArrayList<LockGraphNode>>() {
        @Override
        protected ArrayList<LockGraphNode> initialValue() {
          return Lists.<LockGraphNode>newArrayListWithCapacity(3);
        }
      };

  A Throwable used to record a stack trace that illustrates an example of a specific lock
acquisition ordering. The top of the stack trace is truncated such that it starts with the
acquisition of the lock in question, e.g.
com...ExampleStackTrace: LockB -> LockC
  at com...CycleDetectingReentrantLock.lock(CycleDetectingLockFactory.java:443)
  at ...
  at ...
  at com...MyClass.someMethodThatAcquiresLockB(MyClass.java:123)

/**
   * A Throwable used to record a stack trace that illustrates an example of a specific lock
   * acquisition ordering. The top of the stack trace is truncated such that it starts with the
   * acquisition of the lock in question, e.g.
   *
   * <pre>
   * com...ExampleStackTrace: LockB -&gt; LockC
   *   at com...CycleDetectingReentrantLock.lock(CycleDetectingLockFactory.java:443)
   *   at ...
   *   at ...
   *   at com...MyClass.someMethodThatAcquiresLockB(MyClass.java:123)
   * </pre>
   */
  private static class ExampleStackTrace extends IllegalStateException {

    static final StackTraceElement[] EMPTY_STACK_TRACE = new StackTraceElement[0];

    static final ImmutableSet<String> EXCLUDED_CLASS_NAMES =
        ImmutableSet.of(
            CycleDetectingLockFactory.class.getName(),
            ExampleStackTrace.class.getName(),
            LockGraphNode.class.getName());

    ExampleStackTrace(LockGraphNode node1, LockGraphNode node2) {
      super(node1.getLockName() + " -> " + node2.getLockName());
      StackTraceElement[] origStackTrace = getStackTrace();
      for (int i = 0, n = origStackTrace.length; i < n; i++) {
        if (WithExplicitOrdering.class.getName().equals(origStackTrace[i].getClassName())) {
          // For pre-populated disallowedPriorLocks edges, omit the stack trace.
          setStackTrace(EMPTY_STACK_TRACE);
          break;
        }
        if (!EXCLUDED_CLASS_NAMES.contains(origStackTrace[i].getClassName())) {
          setStackTrace(Arrays.copyOfRange(origStackTrace, i, n));
          break;
        }
      }
    }
  }

  Represents a detected cycle in lock acquisition ordering. The exception includes a causal chain of ExampleStackTrace instances to illustrate the cycle, e.g. com....PotentialDeadlockException: Potential Deadlock from LockC -> ReadWriteA
  at ...
  at ...
Caused by: com...ExampleStackTrace: LockB -> LockC
  at ...
  at ...
Caused by: com...ExampleStackTrace: ReadWriteA -> LockB
  at ...
  at ...

Instances are logged for the Policies.WARN, and thrown for Policies.THROW. 
Since: 13.0/**
   * Represents a detected cycle in lock acquisition ordering. The exception includes a causal chain
   * of {@code ExampleStackTrace} instances to illustrate the cycle, e.g.
   *
   * <pre>
   * com....PotentialDeadlockException: Potential Deadlock from LockC -&gt; ReadWriteA
   *   at ...
   *   at ...
   * Caused by: com...ExampleStackTrace: LockB -&gt; LockC
   *   at ...
   *   at ...
   * Caused by: com...ExampleStackTrace: ReadWriteA -&gt; LockB
   *   at ...
   *   at ...
   * </pre>
   *
   * <p>Instances are logged for the {@code Policies.WARN}, and thrown for {@code Policies.THROW}.
   *
   * @since 13.0
   */
  @Beta
  public static final class PotentialDeadlockException extends ExampleStackTrace {

    private final ExampleStackTrace conflictingStackTrace;

    private PotentialDeadlockException(
        LockGraphNode node1, LockGraphNode node2, ExampleStackTrace conflictingStackTrace) {
      super(node1, node2);
      this.conflictingStackTrace = conflictingStackTrace;
      initCause(conflictingStackTrace);
    }

    public ExampleStackTrace getConflictingStackTrace() {
      return conflictingStackTrace;
    }

    Appends the chain of messages from the conflictingStackTrace to the original 
message. /**
     * Appends the chain of messages from the {@code conflictingStackTrace} to the original {@code
     * message}.
     */
    @Override
    public String getMessage() {
      StringBuilder message = new StringBuilder(super.getMessage());
      for (Throwable t = conflictingStackTrace; t != null; t = t.getCause()) {
        message.append(", ").append(t.getMessage());
      }
      return message.toString();
    }
  }

  Internal Lock implementations implement the CycleDetectingLock interface, allowing the detection logic to treat all locks in the same manner. /**
   * Internal Lock implementations implement the {@code CycleDetectingLock} interface, allowing the
   * detection logic to treat all locks in the same manner.
   */
  private interface CycleDetectingLock {

    Returns: the LockGraphNode associated with this lock./** @return the {@link LockGraphNode} associated with this lock. */
    LockGraphNode getLockGraphNode();

    Returns: true if the current thread has acquired this lock./** @return {@code true} if the current thread has acquired this lock. */
    boolean isAcquiredByCurrentThread();
  }

  A LockGraphNode associated with each lock instance keeps track of the directed edges in the lock acquisition graph. /**
   * A {@code LockGraphNode} associated with each lock instance keeps track of the directed edges in
   * the lock acquisition graph.
   */
  private static class LockGraphNode {

    The map tracking the locks that are known to be acquired before this lock, each associated
with an example stack trace. Locks are weakly keyed to allow proper garbage collection when
they are no longer referenced.
/**
     * The map tracking the locks that are known to be acquired before this lock, each associated
     * with an example stack trace. Locks are weakly keyed to allow proper garbage collection when
     * they are no longer referenced.
     */
    final Map<LockGraphNode, ExampleStackTrace> allowedPriorLocks =
        new MapMaker().weakKeys().makeMap();

    The map tracking lock nodes that can cause a lock acquisition cycle if acquired before this
node.
/**
     * The map tracking lock nodes that can cause a lock acquisition cycle if acquired before this
     * node.
     */
    final Map<LockGraphNode, PotentialDeadlockException> disallowedPriorLocks =
        new MapMaker().weakKeys().makeMap();

    final String lockName;

    LockGraphNode(String lockName) {
      this.lockName = Preconditions.checkNotNull(lockName);
    }

    String getLockName() {
      return lockName;
    }

    void checkAcquiredLocks(Policy policy, List<LockGraphNode> acquiredLocks) {
      for (int i = 0, size = acquiredLocks.size(); i < size; i++) {
        checkAcquiredLock(policy, acquiredLocks.get(i));
      }
    }

    Checks the acquisition-ordering between this, which is about to be acquired, and the specified acquiredLock. When this method returns, the acquiredLock should be in either the 
preAcquireLocks map, for the case in which it is safe to acquire this after the acquiredLock, or in the disallowedPriorLocks map, in which case it is not safe. /**
     * Checks the acquisition-ordering between {@code this}, which is about to be acquired, and the
     * specified {@code acquiredLock}.
     *
     * <p>When this method returns, the {@code acquiredLock} should be in either the {@code
     * preAcquireLocks} map, for the case in which it is safe to acquire {@code this} after the
     * {@code acquiredLock}, or in the {@code disallowedPriorLocks} map, in which case it is not
     * safe.
     */
    void checkAcquiredLock(Policy policy, LockGraphNode acquiredLock) {
      // checkAcquiredLock() should never be invoked by a lock that has already
      // been acquired. For unordered locks, aboutToAcquire() ensures this by
      // checking isAcquiredByCurrentThread(). For ordered locks, however, this
      // can happen because multiple locks may share the same LockGraphNode. In
      // this situation, throw an IllegalStateException as defined by contract
      // described in the documentation of WithExplicitOrdering.
      Preconditions.checkState(
          this != acquiredLock,
          "Attempted to acquire multiple locks with the same rank %s",
          acquiredLock.getLockName());

      if (allowedPriorLocks.containsKey(acquiredLock)) {
        // The acquisition ordering from "acquiredLock" to "this" has already
        // been verified as safe. In a properly written application, this is
        // the common case.
        return;
      }
      PotentialDeadlockException previousDeadlockException = disallowedPriorLocks.get(acquiredLock);
      if (previousDeadlockException != null) {
        // Previously determined to be an unsafe lock acquisition.
        // Create a new PotentialDeadlockException with the same causal chain
        // (the example cycle) as that of the cached exception.
        PotentialDeadlockException exception =
            new PotentialDeadlockException(
                acquiredLock, this, previousDeadlockException.getConflictingStackTrace());
        policy.handlePotentialDeadlock(exception);
        return;
      }
      // Otherwise, it's the first time seeing this lock relationship. Look for
      // a path from the acquiredLock to this.
      Set<LockGraphNode> seen = Sets.newIdentityHashSet();
      ExampleStackTrace path = acquiredLock.findPathTo(this, seen);

      if (path == null) {
        // this can be safely acquired after the acquiredLock.
        //
        // Note that there is a race condition here which can result in missing
        // a cyclic edge: it's possible for two threads to simultaneous find
        // "safe" edges which together form a cycle. Preventing this race
        // condition efficiently without _introducing_ deadlock is probably
        // tricky. For now, just accept the race condition---missing a warning
        // now and then is still better than having no deadlock detection.
        allowedPriorLocks.put(acquiredLock, new ExampleStackTrace(acquiredLock, this));
      } else {
        // Unsafe acquisition order detected. Create and cache a
        // PotentialDeadlockException.
        PotentialDeadlockException exception =
            new PotentialDeadlockException(acquiredLock, this, path);
        disallowedPriorLocks.put(acquiredLock, exception);
        policy.handlePotentialDeadlock(exception);
      }
    }

    Performs a depth-first traversal of the graph edges defined by each node's 
allowedPriorLocks to find a path between this and the specified lock. 
Returns: If a path was found, a chained ExampleStackTrace illustrating the path to the lock, or null if no path was found./**
     * Performs a depth-first traversal of the graph edges defined by each node's {@code
     * allowedPriorLocks} to find a path between {@code this} and the specified {@code lock}.
     *
     * @return If a path was found, a chained {@link ExampleStackTrace} illustrating the path to the
     *     {@code lock}, or {@code null} if no path was found.
     */
    private @Nullable ExampleStackTrace findPathTo(LockGraphNode node, Set<LockGraphNode> seen) {
      if (!seen.add(this)) {
        return null; // Already traversed this node.
      }
      ExampleStackTrace found = allowedPriorLocks.get(node);
      if (found != null) {
        return found; // Found a path ending at the node!
      }
      // Recurse the edges.
      for (Entry<LockGraphNode, ExampleStackTrace> entry : allowedPriorLocks.entrySet()) {
        LockGraphNode preAcquiredLock = entry.getKey();
        found = preAcquiredLock.findPathTo(node, seen);
        if (found != null) {
          // One of this node's allowedPriorLocks found a path. Prepend an
          // ExampleStackTrace(preAcquiredLock, this) to the returned chain of
          // ExampleStackTraces.
          ExampleStackTrace path = new ExampleStackTrace(preAcquiredLock, this);
          path.setStackTrace(entry.getValue().getStackTrace());
          path.initCause(found);
          return path;
        }
      }
      return null;
    }
  }

  CycleDetectingLock implementations must call this method before attempting to acquire the lock.
/**
   * CycleDetectingLock implementations must call this method before attempting to acquire the lock.
   */
  private void aboutToAcquire(CycleDetectingLock lock) {
    if (!lock.isAcquiredByCurrentThread()) {
      ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
      LockGraphNode node = lock.getLockGraphNode();
      node.checkAcquiredLocks(policy, acquiredLockList);
      acquiredLockList.add(node);
    }
  }

  CycleDetectingLock implementations must call this method in a finally clause after any attempt to change the lock state, including both lock and unlock attempts. Failure to do so can result in corrupting the acquireLocks set. /**
   * CycleDetectingLock implementations must call this method in a {@code finally} clause after any
   * attempt to change the lock state, including both lock and unlock attempts. Failure to do so can
   * result in corrupting the acquireLocks set.
   */
  private static void lockStateChanged(CycleDetectingLock lock) {
    if (!lock.isAcquiredByCurrentThread()) {
      ArrayList<LockGraphNode> acquiredLockList = acquiredLocks.get();
      LockGraphNode node = lock.getLockGraphNode();
      // Iterate in reverse because locks are usually locked/unlocked in a
      // LIFO order.
      for (int i = acquiredLockList.size() - 1; i >= 0; i--) {
        if (acquiredLockList.get(i) == node) {
          acquiredLockList.remove(i);
          break;
        }
      }
    }
  }

  final class CycleDetectingReentrantLock extends ReentrantLock implements CycleDetectingLock {

    private final LockGraphNode lockGraphNode;

    private CycleDetectingReentrantLock(LockGraphNode lockGraphNode, boolean fair) {
      super(fair);
      this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
    }

    ///// CycleDetectingLock methods. /////

    @Override
    public LockGraphNode getLockGraphNode() {
      return lockGraphNode;
    }

    @Override
    public boolean isAcquiredByCurrentThread() {
      return isHeldByCurrentThread();
    }

    ///// Overridden ReentrantLock methods. /////

    @Override
    public void lock() {
      aboutToAcquire(this);
      try {
        super.lock();
      } finally {
        lockStateChanged(this);
      }
    }

    @Override
    public void lockInterruptibly() throws InterruptedException {
      aboutToAcquire(this);
      try {
        super.lockInterruptibly();
      } finally {
        lockStateChanged(this);
      }
    }

    @Override
    public boolean tryLock() {
      aboutToAcquire(this);
      try {
        return super.tryLock();
      } finally {
        lockStateChanged(this);
      }
    }

    @Override
    public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
      aboutToAcquire(this);
      try {
        return super.tryLock(timeout, unit);
      } finally {
        lockStateChanged(this);
      }
    }

    @Override
    public void unlock() {
      try {
        super.unlock();
      } finally {
        lockStateChanged(this);
      }
    }
  }

  final class CycleDetectingReentrantReadWriteLock extends ReentrantReadWriteLock
      implements CycleDetectingLock {

    // These ReadLock/WriteLock implementations shadow those in the
    // ReentrantReadWriteLock superclass. They are simply wrappers around the
    // internal Sync object, so this is safe since the shadowed locks are never
    // exposed or used.
    private final CycleDetectingReentrantReadLock readLock;
    private final CycleDetectingReentrantWriteLock writeLock;

    private final LockGraphNode lockGraphNode;

    private CycleDetectingReentrantReadWriteLock(LockGraphNode lockGraphNode, boolean fair) {
      super(fair);
      this.readLock = new CycleDetectingReentrantReadLock(this);
      this.writeLock = new CycleDetectingReentrantWriteLock(this);
      this.lockGraphNode = Preconditions.checkNotNull(lockGraphNode);
    }

    ///// Overridden ReentrantReadWriteLock methods. /////

    @Override
    public ReadLock readLock() {
      return readLock;
    }

    @Override
    public WriteLock writeLock() {
      return writeLock;
    }

    ///// CycleDetectingLock methods. /////

    @Override
    public LockGraphNode getLockGraphNode() {
      return lockGraphNode;
    }

    @Override
    public boolean isAcquiredByCurrentThread() {
      return isWriteLockedByCurrentThread() || getReadHoldCount() > 0;
    }
  }

  private class CycleDetectingReentrantReadLock extends ReentrantReadWriteLock.ReadLock {

    @Weak final CycleDetectingReentrantReadWriteLock readWriteLock;

    CycleDetectingReentrantReadLock(CycleDetectingReentrantReadWriteLock readWriteLock) {
      super(readWriteLock);
      this.readWriteLock = readWriteLock;
    }

    @Override
    public void lock() {
      aboutToAcquire(readWriteLock);
      try {
        super.lock();
      } finally {
        lockStateChanged(readWriteLock);
      }
    }

    @Override
    public void lockInterruptibly() throws InterruptedException {
      aboutToAcquire(readWriteLock);
      try {
        super.lockInterruptibly();
      } finally {
        lockStateChanged(readWriteLock);
      }
    }

    @Override
    public boolean tryLock() {
      aboutToAcquire(readWriteLock);
      try {
        return super.tryLock();
      } finally {
        lockStateChanged(readWriteLock);
      }
    }

    @Override
    public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
      aboutToAcquire(readWriteLock);
      try {
        return super.tryLock(timeout, unit);
      } finally {
        lockStateChanged(readWriteLock);
      }
    }

    @Override
    public void unlock() {
      try {
        super.unlock();
      } finally {
        lockStateChanged(readWriteLock);
      }
    }
  }

  private class CycleDetectingReentrantWriteLock extends ReentrantReadWriteLock.WriteLock {

    @Weak final CycleDetectingReentrantReadWriteLock readWriteLock;

    CycleDetectingReentrantWriteLock(CycleDetectingReentrantReadWriteLock readWriteLock) {
      super(readWriteLock);
      this.readWriteLock = readWriteLock;
    }

    @Override
    public void lock() {
      aboutToAcquire(readWriteLock);
      try {
        super.lock();
      } finally {
        lockStateChanged(readWriteLock);
      }
    }

    @Override
    public void lockInterruptibly() throws InterruptedException {
      aboutToAcquire(readWriteLock);
      try {
        super.lockInterruptibly();
      } finally {
        lockStateChanged(readWriteLock);
      }
    }

    @Override
    public boolean tryLock() {
      aboutToAcquire(readWriteLock);
      try {
        return super.tryLock();
      } finally {
        lockStateChanged(readWriteLock);
      }
    }

    @Override
    public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException {
      aboutToAcquire(readWriteLock);
      try {
        return super.tryLock(timeout, unit);
      } finally {
        lockStateChanged(readWriteLock);
      }
    }

    @Override
    public void unlock() {
      try {
        super.unlock();
      } finally {
        lockStateChanged(readWriteLock);
      }
    }
  }
}
Type parameters:	<E> – The Enum type representing the explicit lock ordering.
Since:	13.0
/

com.google.guava/ guava/ 30.0-jre/ com/google/common/util/concurrent/CycleDetectingLockFactory.java
