Classes | Public Types | Public Member Functions | Public Attributes | Static Public Attributes

mozilla::DeadlockDetector< T > Class Template Reference

DeadlockDetector. More...

#include <DeadlockDetector.h>

Collaboration diagram for mozilla::DeadlockDetector< T >:

List of all members.

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|.
ResourceAcquisitionArrayCheckAcquisition (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'.
ResourceAcquisitionArrayGetDeductionChain (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)
DeadlockDetectoroperator= (const DeadlockDetector &aDD)

Public Attributes

PLHashTablemOrdering
 The partial order on resource acquisitions used by the deadlock detector.
PRLockmLock
 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


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]

CheckAcquisition This method is called after acquiring |aLast|, but before trying to acquire |aProposed| from |aCallContext|.

It determines whether actually trying to acquire |aProposed| will create problems. It is OK if |aLast| is NULL; this is interpreted as |aProposed| being the thread's first acquisition of its current chain.

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

<_ aTarget from which |aStart <_this aTarget| was deduced, including |aStart| and |aTarget|.

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]
template<typename T >
bool mozilla::DeadlockDetector< T >::InTransitiveClosure ( const PLHashEntry aStart,
const PLHashEntry aTarget 
) const [inline]

Return true iff |aTarget| is in the transitive closure of |aStart| over the ordering relation `<_this'.

|aStart != aTarget|

template<typename T >
DeadlockDetector& mozilla::DeadlockDetector< T >::operator= ( const DeadlockDetector< T > &  aDD  ) 

Member Data Documentation

template<typename T >
const PRUint32 mozilla::DeadlockDetector< T >::kDefaultNumBuckets = 64 [static]
template<typename T >
PRLock* mozilla::DeadlockDetector< T >::mLock

Protects contentious methods.

Nb: can't use mozilla::Mutex since we are used as its deadlock detector.

template<typename T >
PLHashTable* mozilla::DeadlockDetector< T >::mOrdering

The partial order on resource acquisitions used by the deadlock detector.


The documentation for this class was generated from the following file: