1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 #ifndef mozilla_DeadlockDetector_h
7 #define mozilla_DeadlockDetector_h
9 #include "mozilla/Attributes.h"
15 #include "nsClassHashtable.h"
23 * The following is an approximate description of how the deadlock detector
26 * The deadlock detector ensures that all blocking resources are
27 * acquired according to a partial order P. One type of blocking
28 * resource is a lock. If a lock l1 is acquired (locked) before l2,
29 * then we say that |l1 <_P l2|. The detector flags an error if two
30 * locks l1 and l2 have an inconsistent ordering in P; that is, if
31 * both |l1 <_P l2| and |l2 <_P l1|. This is a potential error
32 * because a thread acquiring l1,l2 according to the first order might
33 * race with a thread acquiring them according to the second order.
34 * If this happens under the right conditions, then the acquisitions
37 * This deadlock detector doesn't know at compile-time what P is. So,
38 * it tries to discover the order at run time. More precisely, it
39 * finds <i>some</i> order P, then tries to find chains of resource
40 * acquisitions that violate P. An example acquisition sequence, and
41 * the orders they impose, is
42 * l1.lock() // current chain: [ l1 ]
45 * l2.lock() // current chain: [ l1, l2 ]
46 * // order: { l1 <_P l2 }
48 * l3.lock() // current chain: [ l1, l2, l3 ]
49 * // order: { l1 <_P l2, l2 <_P l3, l1 <_P l3 }
50 * // (note: <_P is transitive, so also |l1 <_P l3|)
52 * l2.unlock() // current chain: [ l1, l3 ]
53 * // order: { l1 <_P l2, l2 <_P l3, l1 <_P l3 }
54 * // (note: it's OK, but weird, that l2 was unlocked out
55 * // of order. we still have l1 <_P l3).
57 * l2.lock() // current chain: [ l1, l3, l2 ]
58 * // order: { l1 <_P l2, l2 <_P l3, l1 <_P l3,
60 * BEEP BEEP! Here the detector will flag a potential error, since
61 * l2 and l3 were used inconsistently (and potentially in ways that
65 class DeadlockDetector
68 typedef nsTArray
<const T
*> ResourceAcquisitionArray
;
72 typedef nsTArray
<OrderingEntry
*> HashEntryArray
;
73 typedef typename
HashEntryArray::index_type index_type
;
74 typedef typename
HashEntryArray::size_type size_type
;
75 static const index_type NoIndex
= HashEntryArray::NoIndex
;
78 * Value type for the ordering table. Contains the other
79 * resources on which an ordering constraint |key < other|
80 * exists. The catch is that we also store the calling context at
81 * which the other resource was acquired; this improves the
82 * quality of error messages when potential deadlock is detected.
86 explicit OrderingEntry(const T
* aResource
)
87 : mOrderedLT() // FIXME bug 456272: set to empirical dep size?
89 , mResource(aResource
)
97 SizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const
99 size_t n
= aMallocSizeOf(this);
100 n
+= mOrderedLT
.SizeOfExcludingThis(aMallocSizeOf
);
101 n
+= mExternalRefs
.SizeOfExcludingThis(aMallocSizeOf
);
105 HashEntryArray mOrderedLT
; // this <_o Other
106 HashEntryArray mExternalRefs
; // hash entries that reference this
110 // Throwaway RAII lock to make the following code safer.
113 explicit PRAutoLock(PRLock
* aLock
) : mLock(aLock
) { PR_Lock(mLock
); }
114 ~PRAutoLock() { PR_Unlock(mLock
); }
119 static const uint32_t kDefaultNumBuckets
;
123 * Create a new deadlock detector.
125 * @param aNumResourcesGuess Guess at approximate number of resources
126 * that will be checked.
128 explicit DeadlockDetector(uint32_t aNumResourcesGuess
= kDefaultNumBuckets
)
129 : mOrdering(aNumResourcesGuess
)
131 mLock
= PR_NewLock();
133 NS_RUNTIMEABORT("couldn't allocate deadlock detector lock");
144 PR_DestroyLock(mLock
);
148 SizeOfEntryExcludingThis(const T
* aKey
, const nsAutoPtr
<OrderingEntry
>& aEntry
,
149 MallocSizeOf aMallocSizeOf
, void* aUserArg
)
151 // NB: Key is accounted for in the entry.
152 size_t n
= aEntry
->SizeOfIncludingThis(aMallocSizeOf
);
157 SizeOfIncludingThis(MallocSizeOf aMallocSizeOf
) const
159 size_t n
= aMallocSizeOf(this);
163 n
+= mOrdering
.SizeOfExcludingThis(SizeOfEntryExcludingThis
, aMallocSizeOf
);
171 * Make the deadlock detector aware of |aResource|.
173 * WARNING: The deadlock detector owns |aResource|.
177 * @param aResource Resource to make deadlock detector aware of.
179 void Add(const T
* aResource
)
182 mOrdering
.Put(aResource
, new OrderingEntry(aResource
));
185 void Remove(const T
* aResource
)
189 OrderingEntry
* entry
= mOrdering
.Get(aResource
);
191 // Iterate the external refs and remove the entry from them.
192 HashEntryArray
& refs
= entry
->mExternalRefs
;
193 for (index_type i
= 0; i
< refs
.Length(); i
++) {
194 refs
[i
]->mOrderedLT
.RemoveElementSorted(entry
);
197 // Iterate orders and remove this entry from their refs.
198 HashEntryArray
& orders
= entry
->mOrderedLT
;
199 for (index_type i
= 0; i
< orders
.Length(); i
++) {
200 orders
[i
]->mExternalRefs
.RemoveElementSorted(entry
);
203 // Now the entry can be safely removed.
204 mOrdering
.Remove(aResource
);
208 * CheckAcquisition This method is called after acquiring |aLast|,
209 * but before trying to acquire |aProposed|.
210 * It determines whether actually trying to acquire |aProposed|
211 * will create problems. It is OK if |aLast| is nullptr; this is
212 * interpreted as |aProposed| being the thread's first acquisition
213 * of its current chain.
215 * Iff acquiring |aProposed| may lead to deadlock for some thread
216 * interleaving (including the current one!), the cyclical
217 * dependency from which this was deduced is returned. Otherwise,
220 * If a potential deadlock is detected and a resource cycle is
221 * returned, it is the *caller's* responsibility to free it.
225 * @param aLast Last resource acquired by calling thread (or 0).
226 * @param aProposed Resource calling thread proposes to acquire.
228 ResourceAcquisitionArray
* CheckAcquisition(const T
* aLast
,
232 // don't check if |0 < aProposed|; just vamoose
236 NS_ASSERTION(aProposed
, "null resource");
239 OrderingEntry
* proposed
= mOrdering
.Get(aProposed
);
240 NS_ASSERTION(proposed
, "missing ordering entry");
242 OrderingEntry
* current
= mOrdering
.Get(aLast
);
243 NS_ASSERTION(current
, "missing ordering entry");
245 // this is the crux of the deadlock detector algorithm
247 if (current
== proposed
) {
248 // reflexive deadlock. fastpath b/c InTransitiveClosure is
249 // not applicable here.
250 ResourceAcquisitionArray
* cycle
= new ResourceAcquisitionArray();
252 NS_RUNTIMEABORT("can't allocate dep. cycle array");
254 cycle
->AppendElement(current
->mResource
);
255 cycle
->AppendElement(aProposed
);
258 if (InTransitiveClosure(current
, proposed
)) {
259 // we've already established |aLast < aProposed|. all is well.
262 if (InTransitiveClosure(proposed
, current
)) {
263 // the order |aProposed < aLast| has been deduced, perhaps
264 // transitively. we're attempting to violate that
265 // constraint by acquiring resources in the order
266 // |aLast < aProposed|, and thus we may deadlock under the
268 ResourceAcquisitionArray
* cycle
= GetDeductionChain(proposed
, current
);
269 // show how acquiring |aProposed| would complete the cycle
270 cycle
->AppendElement(aProposed
);
273 // |aLast|, |aProposed| are unordered according to our
274 // poset. this is fine, but we now need to add this
275 // ordering constraint.
276 current
->mOrderedLT
.InsertElementSorted(proposed
);
277 proposed
->mExternalRefs
.InsertElementSorted(current
);
282 * Return true iff |aTarget| is in the transitive closure of |aStart|
283 * over the ordering relation `<_this'.
285 * @precondition |aStart != aTarget|
287 bool InTransitiveClosure(const OrderingEntry
* aStart
,
288 const OrderingEntry
* aTarget
) const
290 // NB: Using a static comparator rather than default constructing one shows
291 // a 9% improvement in scalability tests on some systems.
292 static nsDefaultComparator
<const OrderingEntry
*, const OrderingEntry
*> comp
;
293 if (aStart
->mOrderedLT
.BinaryIndexOf(aTarget
, comp
) != NoIndex
) {
298 size_type len
= aStart
->mOrderedLT
.Length();
299 for (auto it
= aStart
->mOrderedLT
.Elements(); i
< len
; ++i
, ++it
) {
300 if (InTransitiveClosure(*it
, aTarget
)) {
308 * Return an array of all resource acquisitions
309 * aStart <_this r1 <_this r2 <_ ... <_ aTarget
310 * from which |aStart <_this aTarget| was deduced, including
311 * |aStart| and |aTarget|.
313 * Nb: there may be multiple deductions of |aStart <_this
314 * aTarget|. This function returns the first ordering found by
315 * depth-first search.
317 * Nb: |InTransitiveClosure| could be replaced by this function.
318 * However, this one is more expensive because we record the DFS
319 * search stack on the heap whereas the other doesn't.
321 * @precondition |aStart != aTarget|
323 ResourceAcquisitionArray
* GetDeductionChain(const OrderingEntry
* aStart
,
324 const OrderingEntry
* aTarget
)
326 ResourceAcquisitionArray
* chain
= new ResourceAcquisitionArray();
328 NS_RUNTIMEABORT("can't allocate dep. cycle array");
330 chain
->AppendElement(aStart
->mResource
);
332 NS_ASSERTION(GetDeductionChain_Helper(aStart
, aTarget
, chain
),
333 "GetDeductionChain called when there's no deadlock");
337 // precondition: |aStart != aTarget|
338 // invariant: |aStart| is the last element in |aChain|
339 bool GetDeductionChain_Helper(const OrderingEntry
* aStart
,
340 const OrderingEntry
* aTarget
,
341 ResourceAcquisitionArray
* aChain
)
343 if (aStart
->mOrderedLT
.BinaryIndexOf(aTarget
) != NoIndex
) {
344 aChain
->AppendElement(aTarget
->mResource
);
349 size_type len
= aStart
->mOrderedLT
.Length();
350 for (auto it
= aStart
->mOrderedLT
.Elements(); i
< len
; ++i
, ++it
) {
351 aChain
->AppendElement((*it
)->mResource
);
352 if (GetDeductionChain_Helper(*it
, aTarget
, aChain
)) {
355 aChain
->RemoveElementAt(aChain
->Length() - 1);
361 * The partial order on resource acquisitions used by the deadlock
364 nsClassHashtable
<nsPtrHashKey
<const T
>, OrderingEntry
> mOrdering
;
368 * Protects contentious methods.
369 * Nb: can't use mozilla::Mutex since we are used as its deadlock
375 DeadlockDetector(const DeadlockDetector
& aDD
) MOZ_DELETE
;
376 DeadlockDetector
& operator=(const DeadlockDetector
& aDD
) MOZ_DELETE
;
381 // FIXME bug 456272: tune based on average workload
382 const uint32_t DeadlockDetector
<T
>::kDefaultNumBuckets
= 32;
385 } // namespace mozilla
387 #endif // ifndef mozilla_DeadlockDetector_h