Line data Source code
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
8 :
9 : #include "mozilla/Attributes.h"
10 :
11 : #include <stdlib.h>
12 :
13 : #include "prlock.h"
14 :
15 : #include "nsClassHashtable.h"
16 : #include "nsTArray.h"
17 :
18 : namespace mozilla {
19 :
20 : /**
21 : * DeadlockDetector
22 : *
23 : * The following is an approximate description of how the deadlock detector
24 : * works.
25 : *
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
35 : * will deadlock.
36 : *
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 ]
43 : * // order: { }
44 : *
45 : * l2.lock() // current chain: [ l1, l2 ]
46 : * // order: { l1 <_P l2 }
47 : *
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|)
51 : *
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).
56 : *
57 : * l2.lock() // current chain: [ l1, l3, l2 ]
58 : * // order: { l1 <_P l2, l2 <_P l3, l1 <_P l3,
59 : * l3 <_P l2 (!!!) }
60 : * BEEP BEEP! Here the detector will flag a potential error, since
61 : * l2 and l3 were used inconsistently (and potentially in ways that
62 : * would deadlock).
63 : */
64 : template<typename T>
65 : class DeadlockDetector
66 : {
67 : public:
68 : typedef nsTArray<const T*> ResourceAcquisitionArray;
69 :
70 : private:
71 : struct OrderingEntry;
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;
76 :
77 : /**
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.
83 : */
84 : struct OrderingEntry
85 : {
86 1934 : explicit OrderingEntry(const T* aResource)
87 : : mOrderedLT() // FIXME bug 456272: set to empirical dep size?
88 : , mExternalRefs()
89 1934 : , mResource(aResource)
90 : {
91 1934 : }
92 500 : ~OrderingEntry()
93 : {
94 500 : }
95 :
96 : size_t
97 0 : SizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const
98 : {
99 0 : size_t n = aMallocSizeOf(this);
100 0 : n += mOrderedLT.ShallowSizeOfExcludingThis(aMallocSizeOf);
101 0 : n += mExternalRefs.ShallowSizeOfExcludingThis(aMallocSizeOf);
102 0 : return n;
103 : }
104 :
105 : HashEntryArray mOrderedLT; // this <_o Other
106 : HashEntryArray mExternalRefs; // hash entries that reference this
107 : const T* mResource;
108 : };
109 :
110 : // Throwaway RAII lock to make the following code safer.
111 : struct PRAutoLock
112 : {
113 13270 : explicit PRAutoLock(PRLock* aLock) : mLock(aLock) { PR_Lock(mLock); }
114 13276 : ~PRAutoLock() { PR_Unlock(mLock); }
115 : PRLock* mLock;
116 : };
117 :
118 : public:
119 : static const uint32_t kDefaultNumBuckets;
120 :
121 : /**
122 : * DeadlockDetector
123 : * Create a new deadlock detector.
124 : *
125 : * @param aNumResourcesGuess Guess at approximate number of resources
126 : * that will be checked.
127 : */
128 3 : explicit DeadlockDetector(uint32_t aNumResourcesGuess = kDefaultNumBuckets)
129 3 : : mOrdering(aNumResourcesGuess)
130 : {
131 3 : mLock = PR_NewLock();
132 3 : if (!mLock) {
133 0 : MOZ_CRASH("couldn't allocate deadlock detector lock");
134 : }
135 3 : }
136 :
137 : /**
138 : * ~DeadlockDetector
139 : *
140 : * *NOT* thread safe.
141 : */
142 0 : ~DeadlockDetector()
143 : {
144 0 : PR_DestroyLock(mLock);
145 0 : }
146 :
147 : size_t
148 0 : SizeOfIncludingThis(MallocSizeOf aMallocSizeOf) const
149 : {
150 0 : size_t n = aMallocSizeOf(this);
151 :
152 : {
153 0 : PRAutoLock _(mLock);
154 0 : n += mOrdering.ShallowSizeOfExcludingThis(aMallocSizeOf);
155 0 : for (auto iter = mOrdering.ConstIter(); !iter.Done(); iter.Next()) {
156 : // NB: Key is accounted for in the entry.
157 0 : n += iter.Data()->SizeOfIncludingThis(aMallocSizeOf);
158 : }
159 : }
160 :
161 0 : return n;
162 : }
163 :
164 : /**
165 : * Add
166 : * Make the deadlock detector aware of |aResource|.
167 : *
168 : * WARNING: The deadlock detector owns |aResource|.
169 : *
170 : * Thread safe.
171 : *
172 : * @param aResource Resource to make deadlock detector aware of.
173 : */
174 1932 : void Add(const T* aResource)
175 : {
176 3866 : PRAutoLock _(mLock);
177 1934 : mOrdering.Put(aResource, new OrderingEntry(aResource));
178 1934 : }
179 :
180 500 : void Remove(const T* aResource)
181 : {
182 1000 : PRAutoLock _(mLock);
183 :
184 500 : OrderingEntry* entry = mOrdering.Get(aResource);
185 :
186 : // Iterate the external refs and remove the entry from them.
187 500 : HashEntryArray& refs = entry->mExternalRefs;
188 593 : for (index_type i = 0; i < refs.Length(); i++) {
189 93 : refs[i]->mOrderedLT.RemoveElementSorted(entry);
190 : }
191 :
192 : // Iterate orders and remove this entry from their refs.
193 500 : HashEntryArray& orders = entry->mOrderedLT;
194 985 : for (index_type i = 0; i < orders.Length(); i++) {
195 485 : orders[i]->mExternalRefs.RemoveElementSorted(entry);
196 : }
197 :
198 : // Now the entry can be safely removed.
199 500 : mOrdering.Remove(aResource);
200 500 : }
201 :
202 : /**
203 : * CheckAcquisition This method is called after acquiring |aLast|,
204 : * but before trying to acquire |aProposed|.
205 : * It determines whether actually trying to acquire |aProposed|
206 : * will create problems. It is OK if |aLast| is nullptr; this is
207 : * interpreted as |aProposed| being the thread's first acquisition
208 : * of its current chain.
209 : *
210 : * Iff acquiring |aProposed| may lead to deadlock for some thread
211 : * interleaving (including the current one!), the cyclical
212 : * dependency from which this was deduced is returned. Otherwise,
213 : * 0 is returned.
214 : *
215 : * If a potential deadlock is detected and a resource cycle is
216 : * returned, it is the *caller's* responsibility to free it.
217 : *
218 : * Thread safe.
219 : *
220 : * @param aLast Last resource acquired by calling thread (or 0).
221 : * @param aProposed Resource calling thread proposes to acquire.
222 : */
223 93722 : ResourceAcquisitionArray* CheckAcquisition(const T* aLast,
224 : const T* aProposed)
225 : {
226 93722 : if (!aLast) {
227 : // don't check if |0 < aProposed|; just vamoose
228 82884 : return 0;
229 : }
230 :
231 10838 : NS_ASSERTION(aProposed, "null resource");
232 21680 : PRAutoLock _(mLock);
233 :
234 10842 : OrderingEntry* proposed = mOrdering.Get(aProposed);
235 10842 : NS_ASSERTION(proposed, "missing ordering entry");
236 :
237 10842 : OrderingEntry* current = mOrdering.Get(aLast);
238 10842 : NS_ASSERTION(current, "missing ordering entry");
239 :
240 : // this is the crux of the deadlock detector algorithm
241 :
242 10842 : if (current == proposed) {
243 : // reflexive deadlock. fastpath b/c InTransitiveClosure is
244 : // not applicable here.
245 0 : ResourceAcquisitionArray* cycle = new ResourceAcquisitionArray();
246 0 : if (!cycle) {
247 0 : MOZ_CRASH("can't allocate dep. cycle array");
248 : }
249 0 : cycle->AppendElement(current->mResource);
250 0 : cycle->AppendElement(aProposed);
251 0 : return cycle;
252 : }
253 10842 : if (InTransitiveClosure(current, proposed)) {
254 : // we've already established |aLast < aProposed|. all is well.
255 9641 : return 0;
256 : }
257 1201 : if (InTransitiveClosure(proposed, current)) {
258 : // the order |aProposed < aLast| has been deduced, perhaps
259 : // transitively. we're attempting to violate that
260 : // constraint by acquiring resources in the order
261 : // |aLast < aProposed|, and thus we may deadlock under the
262 : // right conditions.
263 0 : ResourceAcquisitionArray* cycle = GetDeductionChain(proposed, current);
264 : // show how acquiring |aProposed| would complete the cycle
265 0 : cycle->AppendElement(aProposed);
266 0 : return cycle;
267 : }
268 : // |aLast|, |aProposed| are unordered according to our
269 : // poset. this is fine, but we now need to add this
270 : // ordering constraint.
271 1201 : current->mOrderedLT.InsertElementSorted(proposed);
272 1201 : proposed->mExternalRefs.InsertElementSorted(current);
273 1201 : return 0;
274 : }
275 :
276 : /**
277 : * Return true iff |aTarget| is in the transitive closure of |aStart|
278 : * over the ordering relation `<_this'.
279 : *
280 : * @precondition |aStart != aTarget|
281 : */
282 25343 : bool InTransitiveClosure(const OrderingEntry* aStart,
283 : const OrderingEntry* aTarget) const
284 : {
285 : // NB: Using a static comparator rather than default constructing one shows
286 : // a 9% improvement in scalability tests on some systems.
287 : static nsDefaultComparator<const OrderingEntry*, const OrderingEntry*> comp;
288 25343 : if (aStart->mOrderedLT.BinaryIndexOf(aTarget, comp) != NoIndex) {
289 9641 : return true;
290 : }
291 :
292 15702 : index_type i = 0;
293 15702 : size_type len = aStart->mOrderedLT.Length();
294 28899 : for (auto it = aStart->mOrderedLT.Elements(); i < len; ++i, ++it) {
295 13300 : if (InTransitiveClosure(*it, aTarget)) {
296 103 : return true;
297 : }
298 : }
299 15599 : return false;
300 : }
301 :
302 : /**
303 : * Return an array of all resource acquisitions
304 : * aStart <_this r1 <_this r2 <_ ... <_ aTarget
305 : * from which |aStart <_this aTarget| was deduced, including
306 : * |aStart| and |aTarget|.
307 : *
308 : * Nb: there may be multiple deductions of |aStart <_this
309 : * aTarget|. This function returns the first ordering found by
310 : * depth-first search.
311 : *
312 : * Nb: |InTransitiveClosure| could be replaced by this function.
313 : * However, this one is more expensive because we record the DFS
314 : * search stack on the heap whereas the other doesn't.
315 : *
316 : * @precondition |aStart != aTarget|
317 : */
318 0 : ResourceAcquisitionArray* GetDeductionChain(const OrderingEntry* aStart,
319 : const OrderingEntry* aTarget)
320 : {
321 0 : ResourceAcquisitionArray* chain = new ResourceAcquisitionArray();
322 0 : if (!chain) {
323 0 : MOZ_CRASH("can't allocate dep. cycle array");
324 : }
325 0 : chain->AppendElement(aStart->mResource);
326 :
327 0 : NS_ASSERTION(GetDeductionChain_Helper(aStart, aTarget, chain),
328 : "GetDeductionChain called when there's no deadlock");
329 0 : return chain;
330 : }
331 :
332 : // precondition: |aStart != aTarget|
333 : // invariant: |aStart| is the last element in |aChain|
334 0 : bool GetDeductionChain_Helper(const OrderingEntry* aStart,
335 : const OrderingEntry* aTarget,
336 : ResourceAcquisitionArray* aChain)
337 : {
338 0 : if (aStart->mOrderedLT.BinaryIndexOf(aTarget) != NoIndex) {
339 0 : aChain->AppendElement(aTarget->mResource);
340 0 : return true;
341 : }
342 :
343 0 : index_type i = 0;
344 0 : size_type len = aStart->mOrderedLT.Length();
345 0 : for (auto it = aStart->mOrderedLT.Elements(); i < len; ++i, ++it) {
346 0 : aChain->AppendElement((*it)->mResource);
347 0 : if (GetDeductionChain_Helper(*it, aTarget, aChain)) {
348 0 : return true;
349 : }
350 0 : aChain->RemoveElementAt(aChain->Length() - 1);
351 : }
352 0 : return false;
353 : }
354 :
355 : /**
356 : * The partial order on resource acquisitions used by the deadlock
357 : * detector.
358 : */
359 : nsClassHashtable<nsPtrHashKey<const T>, OrderingEntry> mOrdering;
360 :
361 :
362 : /**
363 : * Protects contentious methods.
364 : * Nb: can't use mozilla::Mutex since we are used as its deadlock
365 : * detector.
366 : */
367 : PRLock* mLock;
368 :
369 : private:
370 : DeadlockDetector(const DeadlockDetector& aDD) = delete;
371 : DeadlockDetector& operator=(const DeadlockDetector& aDD) = delete;
372 : };
373 :
374 :
375 : template<typename T>
376 : // FIXME bug 456272: tune based on average workload
377 : const uint32_t DeadlockDetector<T>::kDefaultNumBuckets = 32;
378 :
379 :
380 : } // namespace mozilla
381 :
382 : #endif // ifndef mozilla_DeadlockDetector_h
|
