diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
commit | 26a029d407be480d791972afb5975cf62c9360a6 (patch) | |
tree | f435a8308119effd964b339f76abb83a57c29483 /xpcom/threads/DeadlockDetector.h | |
parent | Initial commit. (diff) | |
download | firefox-26a029d407be480d791972afb5975cf62c9360a6.tar.xz firefox-26a029d407be480d791972afb5975cf62c9360a6.zip |
Adding upstream version 124.0.1.upstream/124.0.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'xpcom/threads/DeadlockDetector.h')
-rw-r--r-- | xpcom/threads/DeadlockDetector.h | 359 |
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 |