#include <DeadlockDetector.h>

Collaboration diagram for mozilla::DeadlockDetector< T >:

Classes
struct	OrderingEntry
	Value type for the ordering table.
struct	PRAutoLock
struct	ResourceAcquisition
	ResourceAcquisition Consists simply of a resource and the calling context from which it was acquired. More...
Public Types
typedef nsTArray < ResourceAcquisition >	ResourceAcquisitionArray
Public Member Functions
	DeadlockDetector (PRUint32 aNumResourcesGuess=kDefaultNumBuckets)
	DeadlockDetector Create a new deadlock detector.
	~DeadlockDetector ()
	~DeadlockDetector
void	Add (T *aResource)
	Add Make the deadlock detector aware of \|aResource\|.
ResourceAcquisitionArray *	CheckAcquisition (const T aLast, const T aProposed, const CallStack &aCallContext)
	CheckAcquisition This method is called after acquiring \|aLast\|, but before trying to acquire \|aProposed\| from \|aCallContext\|.
bool	InTransitiveClosure (const PLHashEntry aStart, const PLHashEntry aTarget) const
	Return true iff \|aTarget\| is in the transitive closure of \|aStart\| over the ordering relation `<_this'.
ResourceAcquisitionArray *	GetDeductionChain (const PLHashEntry aStart, const PLHashEntry aTarget)
	Return an array of all resource acquisitions aStart <_this r1 <_this r2 <_ ...
bool	GetDeductionChain_Helper (const PLHashEntry aStart, const PLHashEntry aTarget, ResourceAcquisitionArray *aChain)
	DeadlockDetector (const DeadlockDetector &aDD)
DeadlockDetector &	operator= (const DeadlockDetector &aDD)
Public Attributes
PLHashTable *	mOrdering
	The partial order on resource acquisitions used by the deadlock detector.
PRLock *	mLock
	Protects contentious methods.
Static Public Attributes
static const PRUint32	kDefaultNumBuckets = 64

Detailed Description

template<typename T>
class mozilla::DeadlockDetector< T >

DeadlockDetector.

The following is an approximate description of how the deadlock detector works.

The deadlock detector ensures that all blocking resources are acquired according to a partial order P. One type of blocking resource is a lock. If a lock l1 is acquired (locked) before l2, then we say that |l1 <_P l2|. The detector flags an error if two locks l1 and l2 have an inconsistent ordering in P; that is, if both |l1 <_P l2| and |l2 <_P l1|. This is a potential error because a thread acquiring l1,l2 according to the first order might race with a thread acquiring them according to the second order. If this happens under the right conditions, then the acquisitions will deadlock.

This deadlock detector doesn't know at compile-time what P is. So, it tries to discover the order at run time. More precisely, it finds some order P, then tries to find chains of resource acquisitions that violate P. An example acquisition sequence, and the orders they impose, is l1.lock() // current chain: [ l1 ] // order: { }

l2.lock() // current chain: [ l1, l2 ] // order: { l1 <_P l2 }

l3.lock() // current chain: [ l1, l2, l3 ] // order: { l1 <_P l2, l2 <_P l3, l1 <_P l3 } // (note: <_P is transitive, so also |l1 <_P l3|)

l2.unlock() // current chain: [ l1, l3 ] // order: { l1 <_P l2, l2 <_P l3, l1 <_P l3 } // (note: it's OK, but weird, that l2 was unlocked out // of order. we still have l1 <_P l3).

l2.lock() // current chain: [ l1, l3, l2 ] // order: { l1 <_P l2, l2 <_P l3, l1 <_P l3, l3 <_P l2 (!!!) } BEEP BEEP! Here the detector will flag a potential error, since l2 and l3 were used inconsistently (and potentially in ways that would deadlock).

Member Typedef Documentation

template<typename T >

typedef nsTArray<ResourceAcquisition> mozilla::DeadlockDetector< T >::ResourceAcquisitionArray

Constructor & Destructor Documentation

template<typename T >

mozilla::DeadlockDetector< T >::DeadlockDetector ( PRUint32 aNumResourcesGuess = kDefaultNumBuckets ) [inline]

DeadlockDetector Create a new deadlock detector.

Parameters:

aNumResourcesGuess

Guess at approximate number of resources that will be checked.

template<typename T >

mozilla::DeadlockDetector< T >::~DeadlockDetector ( ) [inline]

~DeadlockDetector

*NOT* thread safe.

template<typename T >

mozilla::DeadlockDetector< T >::DeadlockDetector ( const DeadlockDetector< T > & aDD )

Member Function Documentation

template<typename T >

void mozilla::DeadlockDetector< T >::Add ( T * aResource ) [inline]

Add Make the deadlock detector aware of |aResource|.

WARNING: The deadlock detector owns |aResource|.

Thread safe.

Parameters:

aResource

Resource to make deadlock detector aware of.

template<typename T >

ResourceAcquisitionArray* mozilla::DeadlockDetector< T >::CheckAcquisition	(	const T *	aLast,
		const T *	aProposed,
		const CallStack &	aCallContext
	)			`[inline]`

Iff acquiring |aProposed| may lead to deadlock for some thread interleaving (including the current one!), the cyclical dependency from which this was deduced is returned. Otherwise, 0 is returned.

If a potential deadlock is detected and a resource cycle is returned, it is the *caller's* responsibility to free it.

Thread safe.

Parameters:

	aLast	Last resource acquired by calling thread (or 0).
	aProposed	Resource calling thread proposes to acquire.
	aCallContext	Calling context whence acquisiton request came.

template<typename T >

ResourceAcquisitionArray* mozilla::DeadlockDetector< T >::GetDeductionChain	(	const PLHashEntry *	aStart,
		const PLHashEntry *	aTarget
	)			`[inline]`

Return an array of all resource acquisitions aStart <_this r1 <_this r2 <_ ...

Nb: there may be multiple deductions of |aStart <_this aTarget|. This function returns the first ordering found by depth-first search.

Nb: |InTransitiveClosure| could be replaced by this function. However, this one is more expensive because we record the DFS search stack on the heap whereas the other doesn't.

|aStart != aTarget|

template<typename T >

bool mozilla::DeadlockDetector< T >::GetDeductionChain_Helper	(	const PLHashEntry *	aStart,
		const PLHashEntry *	aTarget,
		ResourceAcquisitionArray *	aChain
	)			`[inline]`