Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
#ifndef mozilla_DeadlockDetector_h
#define mozilla_DeadlockDetector_h
#include "mozilla/Attributes.h"
#include <stdlib.h>
#include "prlock.h"
#include "nsClassHashtable.h"
#include "nsTArray.h"
namespace mozilla {
/**
* 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 <i>some</i> 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).
*/
template <typename T>
class DeadlockDetector {
public:
typedef nsTArray<const T*> ResourceAcquisitionArray;
private:
struct OrderingEntry;
typedef nsTArray<OrderingEntry*> HashEntryArray;
typedef typename HashEntryArray::index_type index_type;
typedef typename HashEntryArray::size_type size_type;
static const index_type NoIndex = HashEntryArray::NoIndex;
/**
* Value type for the ordering table. Contains the other
* resources on which an ordering constraint |key < other|
* exists. The catch is that we also store the calling context at
* which the other resource was acquired; this improves the
* quality of error messages when potential deadlock is detected.
*/
struct OrderingEntry {
explicit OrderingEntry(const T* aResource)
,
mExternalRefs(),
mResource(aResource) {}
~OrderingEntry() {}
size_t SizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const {
size_t n = aMallocSizeOf(this);
n += mOrderedLT.ShallowSizeOfExcludingThis(aMallocSizeOf);
n += mExternalRefs.ShallowSizeOfExcludingThis(aMallocSizeOf);
return n;
}
HashEntryArray mOrderedLT; // this <_o Other
HashEntryArray mExternalRefs; // hash entries that reference this
const T* mResource;
};
// Throwaway RAII lock to make the following code safer.
struct PRAutoLock {
explicit PRAutoLock(PRLock* aLock) : mLock(aLock) { PR_Lock(mLock); }
~PRAutoLock() { PR_Unlock(mLock); }
PRLock* mLock;
};
public:
static const uint32_t kDefaultNumBuckets;
/**
* DeadlockDetector
* Create a new deadlock detector.
*
* @param aNumResourcesGuess Guess at approximate number of resources
* that will be checked.
*/
explicit DeadlockDetector(uint32_t aNumResourcesGuess = kDefaultNumBuckets)
: mOrdering(aNumResourcesGuess) {
mLock = PR_NewLock();
if (!mLock) {
MOZ_CRASH("couldn't allocate deadlock detector lock");
}
}
/**
* ~DeadlockDetector
*
* *NOT* thread safe.
*/
~DeadlockDetector() { PR_DestroyLock(mLock); }
size_t SizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const {
size_t n = aMallocSizeOf(this);
{
PRAutoLock _(mLock);
n += mOrdering.ShallowSizeOfExcludingThis(aMallocSizeOf);
for (const auto& data : mOrdering.Values()) {
// NB: Key is accounted for in the entry.
n += data->SizeOfIncludingThis(aMallocSizeOf);
}
}
return n;
}
/**
* Add
* Make the deadlock detector aware of |aResource|.
*
* WARNING: The deadlock detector owns |aResource|.
*
* Thread safe.
*
* @param aResource Resource to make deadlock detector aware of.
*/
void Add(const T* aResource) {
PRAutoLock _(mLock);
mOrdering.InsertOrUpdate(aResource, MakeUnique<OrderingEntry>(aResource));
}
void Remove(const T* aResource) {
PRAutoLock _(mLock);
OrderingEntry* entry = mOrdering.Get(aResource);
// Iterate the external refs and remove the entry from them.
HashEntryArray& refs = entry->mExternalRefs;
for (index_type i = 0; i < refs.Length(); i++) {
refs[i]->mOrderedLT.RemoveElementSorted(entry);
}
// Iterate orders and remove this entry from their refs.
HashEntryArray& orders = entry->mOrderedLT;
for (index_type i = 0; i < orders.Length(); i++) {
orders[i]->mExternalRefs.RemoveElementSorted(entry);
}
// Now the entry can be safely removed.
mOrdering.Remove(aResource);
}
/**
* CheckAcquisition This method is called after acquiring |aLast|,
* but before trying to acquire |aProposed|.
* It determines whether actually trying to acquire |aProposed|
* will create problems. It is OK if |aLast| is nullptr; 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.
*
* @param aLast Last resource acquired by calling thread (or 0).
* @param aProposed Resource calling thread proposes to acquire.
*/
ResourceAcquisitionArray* CheckAcquisition(const T* aLast,
const T* aProposed) {
if (!aLast) {
// don't check if |0 < aProposed|; just vamoose
return 0;
}
NS_ASSERTION(aProposed, "null resource");
PRAutoLock _(mLock);
OrderingEntry* proposed = mOrdering.Get(aProposed);
NS_ASSERTION(proposed, "missing ordering entry");
OrderingEntry* current = mOrdering.Get(aLast);
NS_ASSERTION(current, "missing ordering entry");
// this is the crux of the deadlock detector algorithm
if (current == proposed) {
// reflexive deadlock. fastpath b/c InTransitiveClosure is
// not applicable here.
ResourceAcquisitionArray* cycle = new ResourceAcquisitionArray();
if (!cycle) {
MOZ_CRASH("can't allocate dep. cycle array");
}
cycle->AppendElement(current->mResource);
cycle->AppendElement(aProposed);
return cycle;
}
if (InTransitiveClosure(current, proposed)) {
// we've already established |aLast < aProposed|. all is well.
return 0;
}
if (InTransitiveClosure(proposed, current)) {
// the order |aProposed < aLast| has been deduced, perhaps
// transitively. we're attempting to violate that
// constraint by acquiring resources in the order
// |aLast < aProposed|, and thus we may deadlock under the
// right conditions.
ResourceAcquisitionArray* cycle = GetDeductionChain(proposed, current);
// show how acquiring |aProposed| would complete the cycle
cycle->AppendElement(aProposed);
return cycle;
}
// |aLast|, |aProposed| are unordered according to our
// poset. this is fine, but we now need to add this
// ordering constraint.
current->mOrderedLT.InsertElementSorted(proposed);
proposed->mExternalRefs.InsertElementSorted(current);
return 0;
}
/**
* Return true iff |aTarget| is in the transitive closure of |aStart|
* over the ordering relation `<_this'.
*
* @precondition |aStart != aTarget|
*/
bool InTransitiveClosure(const OrderingEntry* aStart,
const OrderingEntry* aTarget) const {
// NB: Using a static comparator rather than default constructing one shows
// a 9% improvement in scalability tests on some systems.
static nsDefaultComparator<const OrderingEntry*, const OrderingEntry*> comp;
if (aStart->mOrderedLT.BinaryIndexOf(aTarget, comp) != NoIndex) {
return true;
}
index_type i = 0;
size_type len = aStart->mOrderedLT.Length();
for (auto it = aStart->mOrderedLT.Elements(); i < len; ++i, ++it) {
if (InTransitiveClosure(*it, aTarget)) {
return true;
}
}
return false;
}
/**
* 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.
*
* @precondition |aStart != aTarget|
*/
ResourceAcquisitionArray* GetDeductionChain(const OrderingEntry* aStart,
const OrderingEntry* aTarget) {
ResourceAcquisitionArray* chain = new ResourceAcquisitionArray();
if (!chain) {
MOZ_CRASH("can't allocate dep. cycle array");
}
chain->AppendElement(aStart->mResource);
NS_ASSERTION(GetDeductionChain_Helper(aStart, aTarget, chain),
"GetDeductionChain called when there's no deadlock");
return chain;
}
// precondition: |aStart != aTarget|
// invariant: |aStart| is the last element in |aChain|
bool GetDeductionChain_Helper(const OrderingEntry* aStart,
const OrderingEntry* aTarget,
ResourceAcquisitionArray* aChain) {
if (aStart->mOrderedLT.BinaryIndexOf(aTarget) != NoIndex) {
aChain->AppendElement(aTarget->mResource);
return true;
}
index_type i = 0;
size_type len = aStart->mOrderedLT.Length();
for (auto it = aStart->mOrderedLT.Elements(); i < len; ++i, ++it) {
aChain->AppendElement((*it)->mResource);
if (GetDeductionChain_Helper(*it, aTarget, aChain)) {
return true;
}
aChain->RemoveLastElement();
}
return false;
}
/**
* The partial order on resource acquisitions used by the deadlock
* detector.
*/
nsClassHashtable<nsPtrHashKey<const T>, OrderingEntry> mOrdering;
/**
* Protects contentious methods.
* Nb: can't use mozilla::Mutex since we are used as its deadlock
* detector.
*/
PRLock* mLock;
private:
DeadlockDetector(const DeadlockDetector& aDD) = delete;
DeadlockDetector& operator=(const DeadlockDetector& aDD) = delete;
};
template <typename T>
const uint32_t DeadlockDetector<T>::kDefaultNumBuckets = 32;
} // namespace mozilla
#endif // ifndef mozilla_DeadlockDetector_h