Class Deadlock

java.lang.Object
org.apache.derby.impl.services.locks.Deadlock
class Deadlock extends Object

Code to support deadlock detection.

This class implements deadlock detection by searching for cycles in the wait graph. If a cycle is found, it means that (at least) two transactions are blocked by each other, and one of them must be aborted to allow the other one to continue.

The wait graph is obtained by asking the LockSet instance to provide a map representing all wait relations, see getWaiters(LockTable). The map consists of two distinct sets of (key, value) pairs:

  1. (space, lock) pairs, where space is the compatibility space of a waiting transaction and lock is the ActiveLock instance on which the transaction is waiting
  2. (lock, prevLock) pairs, where lock is an ActiveLock and prevLock is the ActiveLock or LockControl for the first waiter in the queue behind lock

The search is performed as a depth-first search starting from the lock request of a waiter that has been awoken for deadlock detection (either because derby.locks.deadlockTimeout has expired or because some other waiter had picked it as a victim in order to break a deadlock). From this lock request, the wait graph is traversed by checking which transactions have already been granted a lock on the object, and who they are waiting for.

The state of the search is maintained by pushing compatibility spaces (representing waiting transactions) and granted locks onto a stack. When a dead end is found (that is, a transaction that holds locks without waiting for any other transaction), the stack is popped and the search continues down a different path. This continues until a cycle is found or the stack is empty. Detection of cycles happens when pushing a new compatibility space onto the stack. If the same space already exists on the stack, it means the graph has a cycle and we have a deadlock.

When a deadlock is found, one of the waiters in the deadlock cycle is awoken and it will terminate itself, unless it finds that the deadlock has been broken in the meantime, for example because one of the involved waiters has timed out.

  • Constructor Details

    • Deadlock

      private Deadlock()

  • Method Details

    • look

      static Object[] look(AbstractPool factory, LockTable set, LockControl control, ActiveLock startingLock, byte deadlockWake)

      Look for a deadlock.

      Walk through the graph of all locks and search for cycles among the waiting lock requests which would indicate a deadlock. A simple deadlock cycle is where the granted locks of waiting compatibility space A is blocking compatibility space B and space B holds locks causing space A to wait.

      MT - if the LockTable is a LockSet object, the callers must be synchronized on the LockSet object in order to satisfy the synchronization requirements of LockSet.addWaiters(). If it is a ConcurrentLockSet object, the callers must not hold any of the ReentrantLocks guarding the entries in the lock table, and the callers must make sure that only a single thread calls look() at a time.

      Parameters:
      factory - The locking system factory
      set - The complete lock table. A lock table is a hash table keyed by a Lockable and with a LockControl as the data element.
      control - A LockControl contains a reference to the item being locked and doubly linked lists for the granted locks and the waiting locks. The passed in value is the lock that the caller was waiting on when woken up to do the deadlock check.
      startingLock - represents the specific waiting lock request that the caller has been waiting on, before just being woken up to do this search.
      deadlockWake - Either Constants.WAITING_LOCK_IN_WAIT, or Constants.WAITING_LOCK_DEADLOCK.
      Returns:
      The identifier to be used to open the conglomerate later.
      Throws:
      StandardException - Standard exception policy.

    • rollback

      private static void rollback(Stack chain)
      Backtrack in the depth-first search through the wait graph. Expect the top of the stack to hold the compatibility space we've just investigated. Pop the stack until the most recently examined granted lock has been removed.
      Parameters:
      chain - the stack representing the state of the search

    • getWaiters

      private static Hashtable getWaiters(LockTable set)
      Get all the waiters in a LockTable. The waiters are returned as pairs (space, lock) mapping waiting compatibility spaces to the lock request in which they are blocked, and (lock, prevLock) linking a lock request with the lock request that's behind it in the queue of waiters.
      Parameters:
      set - the lock table
      Returns:
      all waiters in the lock table
      See Also:

    • handle

      private static Object[] handle(AbstractPool factory, Stack chain, int start, Dictionary waiters, byte deadlockWake)
      Handle a deadlock when it has been detected. Find out if the waiter that started looking for the deadlock is involved in it. If it isn't, pick a victim among the waiters that are involved.
      Returns:
      null if the waiter that started looking for the deadlock isn't involved in the deadlock (in which case another victim will have been picked and awoken), or an array describing the deadlock otherwise

    • buildException

      static StandardException buildException(AbstractPool factory, Object[] data)
      Build an exception that describes a deadlock.
      Parameters:
      factory - the lock factory requesting the exception
      data - an array with information about who's involved in a deadlock (as returned by handle(AbstractPool, Stack, int, Dictionary, byte))
      Returns:
      a deadlock exception

    • addInfo

      private static void addInfo(StringBuffer sb, String desc, Object data)

    • getContext

      static Context getContext(String contextID)
      Privileged lookup of a Context. Must be package protected so that user code can't call this entry point.