1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/glue/DeadlockDetector.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,562 @@
1.4 +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: sw=4 ts=4 et :
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +#ifndef mozilla_DeadlockDetector_h
1.10 +#define mozilla_DeadlockDetector_h
1.11 +
1.12 +#include "mozilla/Attributes.h"
1.13 +
1.14 +#include <stdlib.h>
1.15 +
1.16 +#include "plhash.h"
1.17 +#include "prlock.h"
1.18 +
1.19 +#include "nsTArray.h"
1.20 +
1.21 +#ifdef NS_TRACE_MALLOC
1.22 +# include "nsTraceMalloc.h"
1.23 +#endif // ifdef NS_TRACE_MALLOC
1.24 +
1.25 +namespace mozilla {
1.26 +
1.27 +
1.28 +// FIXME bug 456272: split this off into a convenience API on top of
1.29 +// nsStackWalk?
1.30 +class NS_COM_GLUE CallStack
1.31 +{
1.32 +private:
1.33 +#ifdef NS_TRACE_MALLOC
1.34 + typedef nsTMStackTraceID callstack_id;
1.35 + // needs to be a macro to avoid disturbing the backtrace
1.36 +# define NS_GET_BACKTRACE() NS_TraceMallocGetStackTrace()
1.37 +# define NS_DEADLOCK_DETECTOR_CONSTEXPR
1.38 +#else
1.39 + typedef void* callstack_id;
1.40 +# define NS_GET_BACKTRACE() 0
1.41 +# define NS_DEADLOCK_DETECTOR_CONSTEXPR MOZ_CONSTEXPR
1.42 +#endif // ifdef NS_TRACE_MALLOC
1.43 +
1.44 + callstack_id mCallStack;
1.45 +
1.46 +public:
1.47 + /**
1.48 + * CallStack
1.49 + * *ALWAYS* *ALWAYS* *ALWAYS* call this with no arguments. This
1.50 + * constructor takes an argument *ONLY* so that |GET_BACKTRACE()|
1.51 + * can be evaluated in the stack frame of the caller, rather than
1.52 + * that of the constructor.
1.53 + *
1.54 + * *BEWARE*: this means that calling this constructor with no
1.55 + * arguments is not the same as a "default, do-nothing"
1.56 + * constructor: it *will* construct a backtrace. This can cause
1.57 + * unexpected performance issues.
1.58 + */
1.59 + NS_DEADLOCK_DETECTOR_CONSTEXPR
1.60 + CallStack(const callstack_id aCallStack = NS_GET_BACKTRACE()) :
1.61 + mCallStack(aCallStack)
1.62 + {
1.63 + }
1.64 + NS_DEADLOCK_DETECTOR_CONSTEXPR
1.65 + CallStack(const CallStack& aFrom) :
1.66 + mCallStack(aFrom.mCallStack)
1.67 + {
1.68 + }
1.69 + CallStack& operator=(const CallStack& aFrom)
1.70 + {
1.71 + mCallStack = aFrom.mCallStack;
1.72 + return *this;
1.73 + }
1.74 + bool operator==(const CallStack& aOther) const
1.75 + {
1.76 + return mCallStack == aOther.mCallStack;
1.77 + }
1.78 + bool operator!=(const CallStack& aOther) const
1.79 + {
1.80 + return mCallStack != aOther.mCallStack;
1.81 + }
1.82 +
1.83 + // FIXME bug 456272: if this is split off,
1.84 + // NS_TraceMallocPrintStackTrace should be modified to print into
1.85 + // an nsACString
1.86 + void Print(FILE* f) const
1.87 + {
1.88 +#ifdef NS_TRACE_MALLOC
1.89 + if (this != &kNone && mCallStack) {
1.90 + NS_TraceMallocPrintStackTrace(f, mCallStack);
1.91 + return;
1.92 + }
1.93 +#endif
1.94 + fputs(" [stack trace unavailable]\n", f);
1.95 + }
1.96 +
1.97 + /** The "null" callstack. */
1.98 + static const CallStack kNone;
1.99 +};
1.100 +
1.101 +
1.102 +/**
1.103 + * DeadlockDetector
1.104 + *
1.105 + * The following is an approximate description of how the deadlock detector
1.106 + * works.
1.107 + *
1.108 + * The deadlock detector ensures that all blocking resources are
1.109 + * acquired according to a partial order P. One type of blocking
1.110 + * resource is a lock. If a lock l1 is acquired (locked) before l2,
1.111 + * then we say that |l1 <_P l2|. The detector flags an error if two
1.112 + * locks l1 and l2 have an inconsistent ordering in P; that is, if
1.113 + * both |l1 <_P l2| and |l2 <_P l1|. This is a potential error
1.114 + * because a thread acquiring l1,l2 according to the first order might
1.115 + * race with a thread acquiring them according to the second order.
1.116 + * If this happens under the right conditions, then the acquisitions
1.117 + * will deadlock.
1.118 + *
1.119 + * This deadlock detector doesn't know at compile-time what P is. So,
1.120 + * it tries to discover the order at run time. More precisely, it
1.121 + * finds <i>some</i> order P, then tries to find chains of resource
1.122 + * acquisitions that violate P. An example acquisition sequence, and
1.123 + * the orders they impose, is
1.124 + * l1.lock() // current chain: [ l1 ]
1.125 + * // order: { }
1.126 + *
1.127 + * l2.lock() // current chain: [ l1, l2 ]
1.128 + * // order: { l1 <_P l2 }
1.129 + *
1.130 + * l3.lock() // current chain: [ l1, l2, l3 ]
1.131 + * // order: { l1 <_P l2, l2 <_P l3, l1 <_P l3 }
1.132 + * // (note: <_P is transitive, so also |l1 <_P l3|)
1.133 + *
1.134 + * l2.unlock() // current chain: [ l1, l3 ]
1.135 + * // order: { l1 <_P l2, l2 <_P l3, l1 <_P l3 }
1.136 + * // (note: it's OK, but weird, that l2 was unlocked out
1.137 + * // of order. we still have l1 <_P l3).
1.138 + *
1.139 + * l2.lock() // current chain: [ l1, l3, l2 ]
1.140 + * // order: { l1 <_P l2, l2 <_P l3, l1 <_P l3,
1.141 + * l3 <_P l2 (!!!) }
1.142 + * BEEP BEEP! Here the detector will flag a potential error, since
1.143 + * l2 and l3 were used inconsistently (and potentially in ways that
1.144 + * would deadlock).
1.145 + */
1.146 +template <typename T>
1.147 +class DeadlockDetector
1.148 +{
1.149 +public:
1.150 + /**
1.151 + * ResourceAcquisition
1.152 + * Consists simply of a resource and the calling context from
1.153 + * which it was acquired. We pack this information together so
1.154 + * that it can be returned back to the caller when a potential
1.155 + * deadlock has been found.
1.156 + */
1.157 + struct ResourceAcquisition
1.158 + {
1.159 + const T* mResource;
1.160 + CallStack mCallContext;
1.161 +
1.162 + ResourceAcquisition(
1.163 + const T* aResource,
1.164 + const CallStack aCallContext=CallStack::kNone) :
1.165 + mResource(aResource),
1.166 + mCallContext(aCallContext)
1.167 + {
1.168 + }
1.169 + ResourceAcquisition(const ResourceAcquisition& aFrom) :
1.170 + mResource(aFrom.mResource),
1.171 + mCallContext(aFrom.mCallContext)
1.172 + {
1.173 + }
1.174 + ResourceAcquisition& operator=(const ResourceAcquisition& aFrom)
1.175 + {
1.176 + mResource = aFrom.mResource;
1.177 + mCallContext = aFrom.mCallContext;
1.178 + return *this;
1.179 + }
1.180 + };
1.181 + typedef nsTArray<ResourceAcquisition> ResourceAcquisitionArray;
1.182 +
1.183 +private:
1.184 + typedef nsTArray<PLHashEntry*> HashEntryArray;
1.185 + typedef typename HashEntryArray::index_type index_type;
1.186 + typedef typename HashEntryArray::size_type size_type;
1.187 + enum {
1.188 + NoIndex = HashEntryArray::NoIndex
1.189 + };
1.190 +
1.191 + /**
1.192 + * Value type for the ordering table. Contains the other
1.193 + * resources on which an ordering constraint |key < other|
1.194 + * exists. The catch is that we also store the calling context at
1.195 + * which the other resource was acquired; this improves the
1.196 + * quality of error messages when potential deadlock is detected.
1.197 + */
1.198 + struct OrderingEntry
1.199 + {
1.200 + OrderingEntry() :
1.201 + mFirstSeen(CallStack::kNone),
1.202 + mOrderedLT() // FIXME bug 456272: set to empirical
1.203 + { // dep size?
1.204 + }
1.205 + ~OrderingEntry()
1.206 + {
1.207 + }
1.208 +
1.209 + CallStack mFirstSeen; // first site from which the resource appeared
1.210 + HashEntryArray mOrderedLT; // this <_o Other
1.211 + };
1.212 +
1.213 + static void* TableAlloc(void* /*pool*/, size_t size)
1.214 + {
1.215 + return operator new(size);
1.216 + }
1.217 + static void TableFree(void* /*pool*/, void* item)
1.218 + {
1.219 + operator delete(item);
1.220 + }
1.221 + static PLHashEntry* EntryAlloc(void* /*pool*/, const void* key)
1.222 + {
1.223 + return new PLHashEntry;
1.224 + }
1.225 + static void EntryFree(void* /*pool*/, PLHashEntry* entry, unsigned flag)
1.226 + {
1.227 + delete static_cast<T*>(const_cast<void*>(entry->key));
1.228 + delete static_cast<OrderingEntry*>(entry->value);
1.229 + entry->value = 0;
1.230 + if (HT_FREE_ENTRY == flag)
1.231 + delete entry;
1.232 + }
1.233 + static PLHashNumber HashKey(const void* aKey)
1.234 + {
1.235 + return NS_PTR_TO_INT32(aKey) >> 2;
1.236 + }
1.237 + static const PLHashAllocOps kAllocOps;
1.238 +
1.239 + // Hash table "interface" the rest of the code should use
1.240 +
1.241 + PLHashEntry** GetEntry(const T* aKey)
1.242 + {
1.243 + return PL_HashTableRawLookup(mOrdering, HashKey(aKey), aKey);
1.244 + }
1.245 +
1.246 + void PutEntry(T* aKey)
1.247 + {
1.248 + PL_HashTableAdd(mOrdering, aKey, new OrderingEntry());
1.249 + }
1.250 +
1.251 + // XXX need these helper methods because OrderingEntry doesn't have
1.252 + // XXX access to underlying PLHashEntry
1.253 +
1.254 + /**
1.255 + * Add the order |aFirst <_o aSecond|.
1.256 + *
1.257 + * WARNING: this does not check whether it's sane to add this
1.258 + * order. In the "best" bad case, when this order already exists,
1.259 + * adding it anyway may unnecessarily result in O(n^2) space. In
1.260 + * the "worst" bad case, adding it anyway will cause
1.261 + * |InTransitiveClosure()| to diverge.
1.262 + */
1.263 + void AddOrder(PLHashEntry* aLT, PLHashEntry* aGT)
1.264 + {
1.265 + static_cast<OrderingEntry*>(aLT->value)->mOrderedLT
1.266 + .InsertElementSorted(aGT);
1.267 + }
1.268 +
1.269 + /**
1.270 + * Return true iff the order |aFirst < aSecond| has been
1.271 + * *explicitly* added.
1.272 + *
1.273 + * Does not consider transitivity.
1.274 + */
1.275 + bool IsOrdered(const PLHashEntry* aFirst, const PLHashEntry* aSecond)
1.276 + const
1.277 + {
1.278 + return NoIndex !=
1.279 + static_cast<const OrderingEntry*>(aFirst->value)->mOrderedLT
1.280 + .BinaryIndexOf(aSecond);
1.281 + }
1.282 +
1.283 + /**
1.284 + * Return a pointer to the array of all elements "that" for
1.285 + * which the order |this < that| has been explicitly added.
1.286 + *
1.287 + * NOTE: this does *not* consider transitive orderings.
1.288 + */
1.289 + PLHashEntry* const* GetOrders(const PLHashEntry* aEntry) const
1.290 + {
1.291 + return static_cast<const OrderingEntry*>(aEntry->value)->mOrderedLT
1.292 + .Elements();
1.293 + }
1.294 +
1.295 + /**
1.296 + * Return the number of elements "that" for which the order
1.297 + * |this < that| has been explicitly added.
1.298 + *
1.299 + * NOTE: this does *not* consider transitive orderings.
1.300 + */
1.301 + size_type NumOrders(const PLHashEntry* aEntry) const
1.302 + {
1.303 + return static_cast<const OrderingEntry*>(aEntry->value)->mOrderedLT
1.304 + .Length();
1.305 + }
1.306 +
1.307 + /** Make a ResourceAcquisition out of |aEntry|. */
1.308 + ResourceAcquisition MakeResourceAcquisition(const PLHashEntry* aEntry)
1.309 + const
1.310 + {
1.311 + return ResourceAcquisition(
1.312 + static_cast<const T*>(aEntry->key),
1.313 + static_cast<const OrderingEntry*>(aEntry->value)->mFirstSeen);
1.314 + }
1.315 +
1.316 + // Throwaway RAII lock to make the following code safer.
1.317 + struct PRAutoLock
1.318 + {
1.319 + PRAutoLock(PRLock* aLock) : mLock(aLock) { PR_Lock(mLock); }
1.320 + ~PRAutoLock() { PR_Unlock(mLock); }
1.321 + PRLock* mLock;
1.322 + };
1.323 +
1.324 +public:
1.325 + static const uint32_t kDefaultNumBuckets;
1.326 +
1.327 + /**
1.328 + * DeadlockDetector
1.329 + * Create a new deadlock detector.
1.330 + *
1.331 + * @param aNumResourcesGuess Guess at approximate number of resources
1.332 + * that will be checked.
1.333 + */
1.334 + DeadlockDetector(uint32_t aNumResourcesGuess = kDefaultNumBuckets)
1.335 + {
1.336 + mOrdering = PL_NewHashTable(aNumResourcesGuess,
1.337 + HashKey,
1.338 + PL_CompareValues, PL_CompareValues,
1.339 + &kAllocOps, 0);
1.340 + if (!mOrdering)
1.341 + NS_RUNTIMEABORT("couldn't initialize resource ordering table");
1.342 +
1.343 + mLock = PR_NewLock();
1.344 + if (!mLock)
1.345 + NS_RUNTIMEABORT("couldn't allocate deadlock detector lock");
1.346 + }
1.347 +
1.348 + /**
1.349 + * ~DeadlockDetector
1.350 + *
1.351 + * *NOT* thread safe.
1.352 + */
1.353 + ~DeadlockDetector()
1.354 + {
1.355 + PL_HashTableDestroy(mOrdering);
1.356 + PR_DestroyLock(mLock);
1.357 + }
1.358 +
1.359 + /**
1.360 + * Add
1.361 + * Make the deadlock detector aware of |aResource|.
1.362 + *
1.363 + * WARNING: The deadlock detector owns |aResource|.
1.364 + *
1.365 + * Thread safe.
1.366 + *
1.367 + * @param aResource Resource to make deadlock detector aware of.
1.368 + */
1.369 + void Add(T* aResource)
1.370 + {
1.371 + PRAutoLock _(mLock);
1.372 + PutEntry(aResource);
1.373 + }
1.374 +
1.375 + // Nb: implementing a Remove() method makes the detector "more
1.376 + // unsound." By removing a resource from the orderings, deadlocks
1.377 + // may be missed that would otherwise have been found. However,
1.378 + // removing resources possibly reduces the # of false positives,
1.379 + // and additionally saves space. So it's a trade off; we have
1.380 + // chosen to err on the side of caution and not implement Remove().
1.381 +
1.382 + /**
1.383 + * CheckAcquisition This method is called after acquiring |aLast|,
1.384 + * but before trying to acquire |aProposed| from |aCallContext|.
1.385 + * It determines whether actually trying to acquire |aProposed|
1.386 + * will create problems. It is OK if |aLast| is nullptr; this is
1.387 + * interpreted as |aProposed| being the thread's first acquisition
1.388 + * of its current chain.
1.389 + *
1.390 + * Iff acquiring |aProposed| may lead to deadlock for some thread
1.391 + * interleaving (including the current one!), the cyclical
1.392 + * dependency from which this was deduced is returned. Otherwise,
1.393 + * 0 is returned.
1.394 + *
1.395 + * If a potential deadlock is detected and a resource cycle is
1.396 + * returned, it is the *caller's* responsibility to free it.
1.397 + *
1.398 + * Thread safe.
1.399 + *
1.400 + * @param aLast Last resource acquired by calling thread (or 0).
1.401 + * @param aProposed Resource calling thread proposes to acquire.
1.402 + * @param aCallContext Calling context whence acquisiton request came.
1.403 + */
1.404 + ResourceAcquisitionArray* CheckAcquisition(const T* aLast,
1.405 + const T* aProposed,
1.406 + const CallStack& aCallContext)
1.407 + {
1.408 + NS_ASSERTION(aProposed, "null resource");
1.409 + PRAutoLock _(mLock);
1.410 +
1.411 + PLHashEntry* second = *GetEntry(aProposed);
1.412 + OrderingEntry* e = static_cast<OrderingEntry*>(second->value);
1.413 + if (CallStack::kNone == e->mFirstSeen)
1.414 + e->mFirstSeen = aCallContext;
1.415 +
1.416 + if (!aLast)
1.417 + // don't check if |0 < proposed|; just vamoose
1.418 + return 0;
1.419 +
1.420 + PLHashEntry* first = *GetEntry(aLast);
1.421 +
1.422 + // this is the crux of the deadlock detector algorithm
1.423 +
1.424 + if (first == second) {
1.425 + // reflexive deadlock. fastpath b/c InTransitiveClosure is
1.426 + // not applicable here.
1.427 + ResourceAcquisitionArray* cycle = new ResourceAcquisitionArray();
1.428 + if (!cycle)
1.429 + NS_RUNTIMEABORT("can't allocate dep. cycle array");
1.430 + cycle->AppendElement(MakeResourceAcquisition(first));
1.431 + cycle->AppendElement(ResourceAcquisition(aProposed,
1.432 + aCallContext));
1.433 + return cycle;
1.434 + }
1.435 + if (InTransitiveClosure(first, second)) {
1.436 + // we've already established |last < proposed|. all is well.
1.437 + return 0;
1.438 + }
1.439 + if (InTransitiveClosure(second, first)) {
1.440 + // the order |proposed < last| has been deduced, perhaps
1.441 + // transitively. we're attempting to violate that
1.442 + // constraint by acquiring resources in the order
1.443 + // |last < proposed|, and thus we may deadlock under the
1.444 + // right conditions.
1.445 + ResourceAcquisitionArray* cycle = GetDeductionChain(second, first);
1.446 + // show how acquiring |proposed| would complete the cycle
1.447 + cycle->AppendElement(ResourceAcquisition(aProposed,
1.448 + aCallContext));
1.449 + return cycle;
1.450 + }
1.451 + // |last|, |proposed| are unordered according to our
1.452 + // poset. this is fine, but we now need to add this
1.453 + // ordering constraint.
1.454 + AddOrder(first, second);
1.455 + return 0;
1.456 + }
1.457 +
1.458 + /**
1.459 + * Return true iff |aTarget| is in the transitive closure of |aStart|
1.460 + * over the ordering relation `<_this'.
1.461 + *
1.462 + * @precondition |aStart != aTarget|
1.463 + */
1.464 + bool InTransitiveClosure(const PLHashEntry* aStart,
1.465 + const PLHashEntry* aTarget) const
1.466 + {
1.467 + if (IsOrdered(aStart, aTarget))
1.468 + return true;
1.469 +
1.470 + index_type i = 0;
1.471 + size_type len = NumOrders(aStart);
1.472 + for (const PLHashEntry* const* it = GetOrders(aStart);
1.473 + i < len; ++i, ++it)
1.474 + if (InTransitiveClosure(*it, aTarget))
1.475 + return true;
1.476 + return false;
1.477 + }
1.478 +
1.479 + /**
1.480 + * Return an array of all resource acquisitions
1.481 + * aStart <_this r1 <_this r2 <_ ... <_ aTarget
1.482 + * from which |aStart <_this aTarget| was deduced, including
1.483 + * |aStart| and |aTarget|.
1.484 + *
1.485 + * Nb: there may be multiple deductions of |aStart <_this
1.486 + * aTarget|. This function returns the first ordering found by
1.487 + * depth-first search.
1.488 + *
1.489 + * Nb: |InTransitiveClosure| could be replaced by this function.
1.490 + * However, this one is more expensive because we record the DFS
1.491 + * search stack on the heap whereas the other doesn't.
1.492 + *
1.493 + * @precondition |aStart != aTarget|
1.494 + */
1.495 + ResourceAcquisitionArray* GetDeductionChain(
1.496 + const PLHashEntry* aStart,
1.497 + const PLHashEntry* aTarget)
1.498 + {
1.499 + ResourceAcquisitionArray* chain = new ResourceAcquisitionArray();
1.500 + if (!chain)
1.501 + NS_RUNTIMEABORT("can't allocate dep. cycle array");
1.502 + chain->AppendElement(MakeResourceAcquisition(aStart));
1.503 +
1.504 + NS_ASSERTION(GetDeductionChain_Helper(aStart, aTarget, chain),
1.505 + "GetDeductionChain called when there's no deadlock");
1.506 + return chain;
1.507 + }
1.508 +
1.509 + // precondition: |aStart != aTarget|
1.510 + // invariant: |aStart| is the last element in |aChain|
1.511 + bool GetDeductionChain_Helper(const PLHashEntry* aStart,
1.512 + const PLHashEntry* aTarget,
1.513 + ResourceAcquisitionArray* aChain)
1.514 + {
1.515 + if (IsOrdered(aStart, aTarget)) {
1.516 + aChain->AppendElement(MakeResourceAcquisition(aTarget));
1.517 + return true;
1.518 + }
1.519 +
1.520 + index_type i = 0;
1.521 + size_type len = NumOrders(aStart);
1.522 + for (const PLHashEntry* const* it = GetOrders(aStart);
1.523 + i < len; ++i, ++it) {
1.524 + aChain->AppendElement(MakeResourceAcquisition(*it));
1.525 + if (GetDeductionChain_Helper(*it, aTarget, aChain))
1.526 + return true;
1.527 + aChain->RemoveElementAt(aChain->Length() - 1);
1.528 + }
1.529 + return false;
1.530 + }
1.531 +
1.532 + /**
1.533 + * The partial order on resource acquisitions used by the deadlock
1.534 + * detector.
1.535 + */
1.536 + PLHashTable* mOrdering; // T* -> PLHashEntry<OrderingEntry>
1.537 +
1.538 + /**
1.539 + * Protects contentious methods.
1.540 + * Nb: can't use mozilla::Mutex since we are used as its deadlock
1.541 + * detector.
1.542 + */
1.543 + PRLock* mLock;
1.544 +
1.545 +private:
1.546 + DeadlockDetector(const DeadlockDetector& aDD) MOZ_DELETE;
1.547 + DeadlockDetector& operator=(const DeadlockDetector& aDD) MOZ_DELETE;
1.548 +};
1.549 +
1.550 +
1.551 +template<typename T>
1.552 +const PLHashAllocOps DeadlockDetector<T>::kAllocOps = {
1.553 + DeadlockDetector<T>::TableAlloc, DeadlockDetector<T>::TableFree,
1.554 + DeadlockDetector<T>::EntryAlloc, DeadlockDetector<T>::EntryFree
1.555 +};
1.556 +
1.557 +
1.558 +template<typename T>
1.559 +// FIXME bug 456272: tune based on average workload
1.560 +const uint32_t DeadlockDetector<T>::kDefaultNumBuckets = 64;
1.561 +
1.562 +
1.563 +} // namespace mozilla
1.564 +
1.565 +#endif // ifndef mozilla_DeadlockDetector_h
