summaryrefslogtreecommitdiffstats
path: root/xpcom/threads/DeadlockDetector.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--xpcom/threads/DeadlockDetector.h359
1 files changed, 359 insertions, 0 deletions
diff --git a/xpcom/threads/DeadlockDetector.h b/xpcom/threads/DeadlockDetector.h
new file mode 100644
index 0000000000..5c40941328
--- /dev/null
+++ b/xpcom/threads/DeadlockDetector.h
@@ -0,0 +1,359 @@
+/* -*- 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
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+#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)
+ : mOrderedLT() // FIXME bug 456272: set to empirical dep size?
+ ,
+ 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>
+// FIXME bug 456272: tune based on average workload
+const uint32_t DeadlockDetector<T>::kDefaultNumBuckets = 32;
+
+} // namespace mozilla
+
+#endif // ifndef mozilla_DeadlockDetector_h
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-14 10:09:24 +0000