Class ExplainDeadLockUtil

java.lang.Object
org.eclipse.persistence.internal.helper.ExplainDeadLockUtil

public class ExplainDeadLockUtil extends Object
The purpose of this class is to try explain the nature of a dead lock
  • Field Details

  • Method Details

    • explainPossibleDeadLockStartRecursion

      public List<DeadLockComponent> explainPossibleDeadLockStartRecursion(ConcurrencyManagerState concurrencyManagerState)
      Given the concurrency manager state try to explain why we are facing a dead lock.
      Parameters:
      concurrencyManagerState - A clone we have assembled based on the concurrency manager and write lock manager state
      Returns:
      A string that tries
    • createListExplainingDeadLock

      protected List<DeadLockComponent> createListExplainingDeadLock(DeadLockComponent deadLockExplanation)
      When the last (repeating thread) of a dead lock is discovered and we start the unwinding of the recursion, the first DTO we create is flagged with DeadLockComponent.isFirstRepeatingThreadThatExplainsDeadLock() but it lacks all additional metadata. so we want enrich the missing metadata into this dto.
      Parameters:
      deadLockExplanation - The outcome of the explain dead lock algorithm. The last DTO on this data structure is lacking metadata and we want to get rid of it.
      Returns:
      return the dead lock explanation as a simple list that is easy to iterate over without going into infinite loops and where we get rid of the primal repeating thread of our recursion which is lacking metadata about the nature of the dead lock on the thread.
    • recursiveExplainPossibleDeadLockStep01

      protected DeadLockComponent recursiveExplainPossibleDeadLockStep01(ConcurrencyManagerState concurrencyManagerStateDto, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain)
      The algorithm expands the current thread in depth. If the current thread is already part of the threadPartOfCurrentDeadLockExpansion then we have found our dead lock. If we return null, we are empty handed ... we cannot explain the dad lock.
      Parameters:
      recursionMaxDepth - how deep do we want our brute force algorithm to go. Probably 6 threads is good enough to discover most dead locks. Max depth should be set to number of threads we believe can logically form a dead lock + 1.
      currentRecursionDepth - how deep we are in the recursion
      currentCandidateThreadPartOfTheDeadLock - the current thread we want to expand
      threadPartOfCurrentDeadLockExpansion - a small optimization. If in the past we xplored expanding Thread A and now we are via a different routing trying to find a dead lock via thread A again we can immediately ignore expanding the thread.
      Returns:
      NULL, if we reach a dead end without a dead lock. If a non result is returned means that the current thread is part of a dead lock identified..
    • recursiveExplainPossibleDeadLockStep02

      protected DeadLockComponent recursiveExplainPossibleDeadLockStep02(ConcurrencyManagerState concurrencyManagerStateDto, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain)
      Precondition the logic of recursiveExplainPossibleDeadLockStep01(ConcurrencyManagerState, int, int, Thread, List, Set) has been invoked and determined that we need to go deeper and expand the current thread.
      Parameters:
      recursionMaxDepth - the max depth the recursion is allowed to reach before deciding it is pointless to go any further. Max depth should be set to number of threads we believe can logically form a dead lock + 1.
      currentRecursionDepth - how deep we are in the recursion
      currentCandidateThreadPartOfTheDeadLock - the current thread we want to expand
      threadPartOfCurrentDeadLockExpansion - a small optimization. If in the past we xplored expanding Thread A and now we are via a different routing trying to find a dead lock via thread A again we can immediately ignore expanding the thread.
      Returns:
      NULL, if we reach a dead end without a dead lock. If a non result is returned means that the current thread is part of a dead lock identified..
    • currentThreadIsKnownToBeWaitingForAnyResource

      protected boolean currentThreadIsKnownToBeWaitingForAnyResource(ConcurrencyManagerState concurrencyManagerStateDto, Thread currentCandidateThreadPartOfTheDeadLock)
      This a helper sanity check. Whenever we expand a threa we expect the thread must be starved fro some resource.
      Parameters:
      concurrencyManagerStateDto - the dto that holds the state of the cocurrency manager for our dead lock detection algorithm
      currentCandidateThreadPartOfTheDeadLock - the thread we are trying to evaluate
      Returns:
      TRUE if we are aware of one or more resources that the current thread strives to acquire but cannot get false if we are clueless as to any desire for the thread.
    • recursiveExplainPossibleDeadLockStep03ExpandBasedOnCacheKeyWantedForWriting

      protected DeadLockComponent recursiveExplainPossibleDeadLockStep03ExpandBasedOnCacheKeyWantedForWriting(ConcurrencyManagerState concurrencyManagerStateDto, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain, ConcurrencyManager cacheKeyCurrentThreadWantsForWritingButCannotGet)
      We are looking at thread that we know has registered itself as wanting to acquire a write lock and not managing to make progress getting the write lock. We need to have a look at the DeadLockComponent to try to find out who is owning the lock at the current point in time. We will onsider th posisble writers, readers and in case of desperation the active thread on the cache key.
      Parameters:
      concurrencyManagerStateDto - state of concurrency manager
      recursionMaxDepth - how deep the recursion can go
      currentRecursionDepth - the current depeth
      currentCandidateThreadPartOfTheDeadLock - the current thread we are expanding and that may be involved in explaning a dead lock
      threadPartOfCurrentDeadLockExpansion - the predecessor threads that are part of a dead lock expansion we are searching
      threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain - these are threads we already expanded at depth 1 and we know they took us nowhere. We just assume expanding these a second time is a waste of time.
      cacheKeyCurrentThreadWantsForWritingButCannotGet - this is the cache key we have identified as making a our candidate thread stuck and we want to explore who is owning this cache key
      Returns:
      NULL if we get nowhere trying to find the dead lock otherwise a DTO explaining this thread and the successor threads that make the dead lock
    • recursiveExplainPossibleDeadLockStep03Scenario01CurrentWriterVsOtherWritersWriter

      protected DeadLockComponent recursiveExplainPossibleDeadLockStep03Scenario01CurrentWriterVsOtherWritersWriter(ConcurrencyManagerState concurrencyManagerStateDto, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain, ConcurrencyManager cacheKeyCurrentThreadWantsForWritingButCannotGet)
      Expand the possibility of the current thread wanting to acquire for writing what some other already has acquired for writing.
    • recursiveExplainPossibleDeadLockStep05Scenario01CurrentReaderVsOtherWriters

      protected DeadLockComponent recursiveExplainPossibleDeadLockStep05Scenario01CurrentReaderVsOtherWriters(ConcurrencyManagerState concurrencyManagerStateDto, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain, ConcurrencyManager cacheKeyCurrentThreadWantsForWritingButCannotGet)
      Expand the possibility of the current thread wanting to acquire for writing what some other already has acquired for writing.
    • recursiveExpansionCurrentThreadBeingBlockedByActiveWriters

      protected DeadLockComponent recursiveExpansionCurrentThreadBeingBlockedByActiveWriters(ConcurrencyManagerState concurrencyManagerState, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain, ConcurrencyManager cacheKeyThreadWantsToAcquireButCannotGet, boolean currentThreadWantsToAcquireForWriting)
      Try to expand the current thread from the perspective that it wants a cache key that may be own for writing by a competitor thread.
      Parameters:
      concurrencyManagerState - state of the concurrency manager
      recursionMaxDepth - max allowed depth for recursion.
      currentRecursionDepth - the current recursion depth
      currentCandidateThreadPartOfTheDeadLock - the current thread we are expanding in dpeth
      threadPartOfCurrentDeadLockExpansion - the current thread of sets comrpising our dead lock expansion.
      threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain - threads we have expanded in the past and gave no fruits
      cacheKeyThreadWantsToAcquireButCannotGet - the cache key we know our current candidate wants and is not getting.
      currentThreadWantsToAcquireForWriting - a flag that tells us if our current candidate thread is strugling to acquire a lock with the purpose of writing or just for reading.
      Returns:
      NULL if no dead lock is found. a value if a deadlock is found
    • recursiveExplainPossibleDeadLockStep03Scenario02CurrentWriterVsOtherReader

      protected DeadLockComponent recursiveExplainPossibleDeadLockStep03Scenario02CurrentWriterVsOtherReader(ConcurrencyManagerState concurrencyManagerState, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain, ConcurrencyManager cacheKeyCurrentThreadWantsForWritingButCannotGet)
      Expand the recursion exploring the possibility that the reason the current thread cannot acquire the cache key is because there are readers on the cache key.
      Returns:
      NULL if dead lock not discovered. Otherwise dead lock component justifying the deadlock.
    • recursiveExplainPossibleDeadLockStep03Scenario03CurrentWriterVsCacheKeyActiveThread

      protected DeadLockComponent recursiveExplainPossibleDeadLockStep03Scenario03CurrentWriterVsCacheKeyActiveThread(ConcurrencyManagerState concurrencyManagerStateDto, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain, ConcurrencyManager cacheKeyCurrentThreadWantsForWritingButCannotGet)
      In scenario 3 is when we start considering the possbility our data for detecting the dead lock is not ok or the cache is corrupted. We consider quite simply the thread that is flagged as the active thread on the cache key since this is the thread owning the cache key. However if we call for this scenario it means we did not find in our DTO any reader or writer owning the thread. So if indeed the cache key our thread is trying to acquire has an active thread and we do not know what this thread is currently doing - since the thread should either be in our basket of writers or in our basket of readers, we are stuck.
      Returns:
      NULL if looking at the active thread of the wanted cache key does not bare any fruits, otherwise the dead lock component object are returned.
    • recursiveExplainPossibleDeadLockStep05Scenario02CurrentReaderVsCacheKeyActiveThread

      protected DeadLockComponent recursiveExplainPossibleDeadLockStep05Scenario02CurrentReaderVsCacheKeyActiveThread(ConcurrencyManagerState concurrencyManagerStateDto, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain, ConcurrencyManager cacheKeyCurrentThreadWantsForWritingButCannotGet)
      Same as recursiveExplainPossibleDeadLockStep03Scenario03CurrentWriterVsCacheKeyActiveThread(ConcurrencyManagerState, int, int, Thread, List, Set, ConcurrencyManager) but in this case our candidate thread is trying to get the cache key with the purpose of READING and not for writing.
    • recursiveExpansionCurrentThreadBeingBlockedByActiveThreadOnCacheKey

      protected DeadLockComponent recursiveExpansionCurrentThreadBeingBlockedByActiveThreadOnCacheKey(ConcurrencyManagerState concurrencyManagerState, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain, ConcurrencyManager cacheKeyThreadWantsToAcquireButCannotGet, boolean currentThreadWantsToAcquireForWriting)
      Try to expand the current thread from the perspective that it wants a cache key that may be own for writing by a competitor thread.
      Parameters:
      concurrencyManagerState - state of the concurrency manager
      recursionMaxDepth - max allowed depth for recursion.
      currentRecursionDepth - the current recursion depth
      currentCandidateThreadPartOfTheDeadLock - the current thread we are expanding in dpeth
      threadPartOfCurrentDeadLockExpansion - the current thread of sets comrpising our dead lock expansion.
      threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain - threads we have expanded in the past and gave no fruits
      cacheKeyThreadWantsToAcquireButCannotGet - the cache key we know our current candidate wants and is not getting.
      currentThreadWantsToAcquireForWriting - a flag that tells us if our current candidate thread is strugling to acquire a lock with the purpose of writing or just for reading.
      Returns:
      NULL if no dead lock is found. a value if a deadlock is found
    • recursiveExplainPossibleDeadLockStep04ExpandBasedOnThreadStuckOnReleaseDeferredLocks

      protected DeadLockComponent recursiveExplainPossibleDeadLockStep04ExpandBasedOnThreadStuckOnReleaseDeferredLocks(ConcurrencyManagerState concurrencyManagerStateDto, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain)
      When a thead cannot move forward due to having deferred cache keys, it means that the thread could not go as deep as it wanted during object building and hda to defer making some parts of the object. The thread is stuck because the parts of the object it could not build are apparently not finished either.
      Returns:
      NULL if we are able to explain a dead lock via expanding this the current candidate thread Otherwiser a DTO component that explains the the dad lock
    • recursiveExplainPossibleDeadLockStep05ExpandBasedOnCacheKeyWantedForReading

      protected DeadLockComponent recursiveExplainPossibleDeadLockStep05ExpandBasedOnCacheKeyWantedForReading(ConcurrencyManagerState concurrencyManagerStateDto, int recursionMaxDepth, int currentRecursionDepth, Thread currentCandidateThreadPartOfTheDeadLock, List<Thread> threadPartOfCurrentDeadLockExpansion, Set<Thread> threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain, ConcurrencyManager cacheKeyCurrentThreadWantsForReadingButCannotGet)
      In this case have a thread that wants to acquire for reading a cache key but it does not manage to acquire it because the cache key is being owned by somebody else. So we need to see what the writer of this cache key is doing.
    • isBuildObjectOnThreadComplete

      public static IsBuildObjectCompleteOutcome isBuildObjectOnThreadComplete(ConcurrencyManagerState concurrencyManagerStateDto, Thread thread, Map<Thread,Thread> recursiveSet)
      This method is nothing more than copy paste code from the algorithm ConcurrencyManager.isBuildObjectOnThreadComplete(Thread, Map, List, boolean) We re-write this code to instead of returning true/false return an actual DTO object that can allow our dead lock explanation algorithm to identify the next thread to expand to explain the dead lock.
      Parameters:
      concurrencyManagerStateDto - our representation of a cloned ste of the concurrency manager and write lock manager
      thread - the current thread to explore which might have deferred locks. At level 1 of the recursion the thread is certain to have deferred locks.
      recursiveSet - this is an hash map holding the threads in the current recusion algorithm that have been expanded already to avoid expanding more than once the same thread and going into an infinite dead lock.
    • deadLockFoundCreateConcurrencyManagerStateWriterThreadCouldNotAcquireWriteLock

      protected DeadLockComponent deadLockFoundCreateConcurrencyManagerStateWriterThreadCouldNotAcquireWriteLock(DeadLockComponent nextThreadPartOfDeadLock, Thread threadNotAbleToAccessResource, ConcurrencyManager cacheKeyThreadWantsToAcquireButCannotGet)
      Create a dead lock dto component.
      Parameters:
      nextThreadPartOfDeadLock - the dto component of a dead lock that comes from a depper recursion expansion
      threadNotAbleToAccessResource - the thread at the current depth that is part of the dead lock
      cacheKeyThreadWantsToAcquireButCannotGet - the cache key that the thread wanted to acquire for writing
      Returns:
      the DTO representing a component part of a dead lock
    • deadLockFoundCreateConcurrencyManagerStateReaderThreadCouldNotAcquireWriteLock

      protected DeadLockComponent deadLockFoundCreateConcurrencyManagerStateReaderThreadCouldNotAcquireWriteLock(DeadLockComponent nextThreadPartOfDeadLock, Thread threadNotAbleToAccessResource, ConcurrencyManager cacheKeyThreadWantsToAcquireButCannotGet)
      Dto component participating in a dead lock.
      Parameters:
      nextThreadPartOfDeadLock - the thread that was participating in the dead lock as we went deeper in the recursion.
      threadNotAbleToAccessResource - the thread at the current depth that is part of the dead lock
      cacheKeyThreadWantsToAcquireButCannotGet - the cache key that the thread wanted to acquire for writing
      Returns:
      the DTO representing a component part of a dead lock
    • deadLockFoundCreateConcurrencyManagerStateDeferredThreadCouldNotAcquireWriteLock

      protected DeadLockComponent deadLockFoundCreateConcurrencyManagerStateDeferredThreadCouldNotAcquireWriteLock(DeadLockComponent nextThreadPartOfDeadLock, Thread threadNotAbleToAccessResource, ConcurrencyManager cacheKeyBlockingIsBuildObjectComplete)
      Create a deadlock component for a thread known to be stuck trying to release deferred locks.
      Parameters:
      nextThreadPartOfDeadLock - the thread that was participating in the dead lock as we went deeper in the recursion.
      threadNotAbleToAccessResource - the thread at the current depth that is part of the dead lock
      cacheKeyBlockingIsBuildObjectComplete - this is a cache key that is not necessarily desired by the blocked thread, but which is recrusively blocking the thread stuck in isBuildObjectcomplete logic. This is a bit complicated to explain, but essentially when a thread cannot acquire write lock it sometimes can defer on the lock. Later to finish object building the thread will be waiting to make sure that locks it deferred are considered to be all finished. When deferred lock is not finished it could be cause much deeper some other secondary object could not be built due to some cache key not accessible.. Therefore the cacheKeyBlockingIsBuildObjectComplete might be quite deep and far away from the cache key our thread had to defer... It is an element blocking our thread from finishing.
      Returns:
      the DTO representing a component part of a dead lock