Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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