public Class ExplainDeadLockUtil

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 org.eclipse.persistence.internal.helper.type.DeadLockComponent#isFirstRepeatingThreadThatExplainsDeadLock() but it lacks all additional metadata. so we want enrich the missing metadata into this dto.

Parameters

deadLockExplanation:DeadLockComponent

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:List<DeadLockComponent>

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.

This a helper sanity check. Whenever we expand a threa we expect the thread must be starved fro some resource.

Parameters

concurrencyManagerStateDto:ConcurrencyManagerState

the dto that holds the state of the cocurrency manager for our dead lock detection algorithm

currentCandidateThreadPartOfTheDeadLock:Thread

the thread we are trying to evaluate

Returns:boolean

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.

Create a deadlock component for a thread known to be stuck trying to release deferred locks.

Parameters

nextThreadPartOfDeadLock:DeadLockComponent

the thread that was participating in the dead lock as we went deeper in the recursion.

threadNotAbleToAccessResource:Thread

the thread at the current depth that is part of the dead lock

cacheKeyBlockingIsBuildObjectComplete:ConcurrencyManager

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:DeadLockComponent

the DTO representing a component part of a dead lock

Dto component participating in a dead lock.

Parameters

nextThreadPartOfDeadLock:DeadLockComponent

the thread that was participating in the dead lock as we went deeper in the recursion.

threadNotAbleToAccessResource:Thread

the thread at the current depth that is part of the dead lock

cacheKeyThreadWantsToAcquireButCannotGet:ConcurrencyManager

the cache key that the thread wanted to acquire for writing

Returns:DeadLockComponent

the DTO representing a component part of a dead lock

Create a dead lock dto component.

Parameters

nextThreadPartOfDeadLock:DeadLockComponent

the dto component of a dead lock that comes from a depper recursion expansion

threadNotAbleToAccessResource:Thread

the thread at the current depth that is part of the dead lock

cacheKeyThreadWantsToAcquireButCannotGet:ConcurrencyManager

the cache key that the thread wanted to acquire for writing

Returns:DeadLockComponent

the DTO representing a component part of a dead lock

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:ConcurrencyManagerState

state of the concurrency manager

recursionMaxDepth:int

max allowed depth for recursion.

currentRecursionDepth:int

the current recursion depth

currentCandidateThreadPartOfTheDeadLock:Thread

the current thread we are expanding in dpeth

threadPartOfCurrentDeadLockExpansion:List<Thread>

the current thread of sets comrpising our dead lock expansion.

threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain:Set<Thread>

threads we have expanded in the past and gave no fruits

cacheKeyThreadWantsToAcquireButCannotGet:ConcurrencyManager

the cache key we know our current candidate wants and is not getting.

currentThreadWantsToAcquireForWriting:boolean

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:DeadLockComponent

NULL if no dead lock is found. a value if a deadlock is found

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:ConcurrencyManagerState

state of the concurrency manager

recursionMaxDepth:int

max allowed depth for recursion.

currentRecursionDepth:int

the current recursion depth

currentCandidateThreadPartOfTheDeadLock:Thread

the current thread we are expanding in dpeth

threadPartOfCurrentDeadLockExpansion:List<Thread>

the current thread of sets comrpising our dead lock expansion.

threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain:Set<Thread>

threads we have expanded in the past and gave no fruits

cacheKeyThreadWantsToAcquireButCannotGet:ConcurrencyManager

the cache key we know our current candidate wants and is not getting.

currentThreadWantsToAcquireForWriting:boolean

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:DeadLockComponent

NULL if no dead lock is found. a value if a deadlock is found

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:int

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:int

how deep we are in the recursion

currentCandidateThreadPartOfTheDeadLock:Thread

the current thread we want to expand

threadPartOfCurrentDeadLockExpansion:List<Thread>

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:DeadLockComponent

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..

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:int

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:int

how deep we are in the recursion

currentCandidateThreadPartOfTheDeadLock:Thread

the current thread we want to expand

threadPartOfCurrentDeadLockExpansion:List<Thread>

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:DeadLockComponent

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..

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:ConcurrencyManagerState

state of concurrency manager

recursionMaxDepth:int

how deep the recursion can go

currentRecursionDepth:int

the current depeth

currentCandidateThreadPartOfTheDeadLock:Thread

the current thread we are expanding and that may be involved in explaning a dead lock

threadPartOfCurrentDeadLockExpansion:List<Thread>

the predecessor threads that are part of a dead lock expansion we are searching

threadsAlreadyExpandedInThePastThatWeDoNotWantToExpandAgain:Set<Thread>

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:ConcurrencyManager

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:DeadLockComponent

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

Expand the possibility of the current thread wanting to acquire for writing what some other already has acquired for writing.

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:DeadLockComponent

NULL if dead lock not discovered. Otherwise dead lock component justifying the deadlock.

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:DeadLockComponent

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.

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:DeadLockComponent

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

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.

Expand the possibility of the current thread wanting to acquire for writing what some other already has acquired for writing.

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.