Bug 456272: deadlock detector improvements
authorChris Jones <jones.chris.g@gmail.com>
Mon, 04 May 2009 21:57:15 -0700
changeset 27982 b78e21f29c5128608cb5f133661267160aa373e1
parent 27981 bf9632b84142f763282c46e6f8bbbb13ace21a6e
child 27983 1a8155f3f573cac9d20dc3a405c27ce28f75e3af
push id6823
push usercjones@mozilla.com
push dateTue, 05 May 2009 04:58:54 +0000
treeherdermozilla-central@b78e21f29c51 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
bugs456272
milestone1.9.2a1pre
Bug 456272: deadlock detector improvements
xpcom/glue/BlockingResourceBase.cpp
xpcom/glue/BlockingResourceBase.h
xpcom/glue/CondVar.h
xpcom/glue/DeadlockDetector.cpp
xpcom/glue/DeadlockDetector.h
xpcom/glue/Makefile.in
xpcom/glue/Monitor.h
xpcom/glue/Mutex.h
xpcom/glue/nsTArray.h
xpcom/glue/objs.mk
xpcom/tests/Makefile.in
xpcom/tests/TestDeadlockDetector.cpp
xpcom/tests/TestDeadlockDetectorScalability.cpp
xpcom/tests/TestSynchronization.cpp
--- a/xpcom/glue/BlockingResourceBase.cpp
+++ b/xpcom/glue/BlockingResourceBase.cpp
@@ -16,551 +16,370 @@
  * The Original Code is mozilla.org code.
  *
  * The Initial Developer of the Original Code is
  * Netscape Communications Corporation.
  * Portions created by the Initial Developer are Copyright (C) 1998
  * the Initial Developer. All Rights Reserved.
  *
  * Contributor(s):
+ *   Chris Jones <jones.chris.g@gmail.com>
  *
  * Alternatively, the contents of this file may be used under the terms of
  * either of the GNU General Public License Version 2 or later (the "GPL"),
  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  * in which case the provisions of the GPL or the LGPL are applicable instead
  * of those above. If you wish to allow use of your version of this file only
  * under the terms of either the GPL or the LGPL, and not to allow others to
  * use your version of this file under the terms of the MPL, indicate your
  * decision by deleting the provisions above and replace them with the notice
  * and other provisions required by the GPL or the LGPL. If you do not delete
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
-#ifdef DEBUG
+#include "mozilla/BlockingResourceBase.h"
 
-#include "plhash.h"
-#include "prprf.h"
-#include "prlock.h"
-#include "prthread.h"
-#include "nsDebug.h"
-#include "nsVoidArray.h"
+#ifdef DEBUG
+#include "nsAutoPtr.h"
 
-#include "mozilla/BlockingResourceBase.h"
 #include "mozilla/CondVar.h"
 #include "mozilla/Monitor.h"
 #include "mozilla/Mutex.h"
-
-#ifdef NS_TRACE_MALLOC
-# include <stdio.h>
-# include "nsTraceMalloc.h"
-#endif
+#endif // ifdef DEBUG
 
-static PRUintn      ResourceAcqnChainFrontTPI = (PRUintn)-1;
-static PLHashTable* OrderTable = 0;
-static PRLock*      OrderTableLock = 0;
-static PRLock*      ResourceMutex = 0;
+namespace mozilla {
+//
+// BlockingResourceBase implementation
+//
 
-// Needs to be kept in sync with BlockingResourceType. */
-static char const *const kResourceTypeNames[] = {
+// static members
+const char* const BlockingResourceBase::kResourceTypeName[] =
+{
+    // needs to be kept in sync with BlockingResourceType
     "Mutex", "Monitor", "CondVar"
 };
 
-struct nsNamedVector : public nsVoidArray {
-    const char* mName;
-
-#ifdef NS_TRACE_MALLOC
-    // Callsites for the inner locks/monitors stored in our base nsVoidArray.
-    // This array parallels our base nsVoidArray.
-    nsVoidArray mInnerSites;
-#endif
+#ifdef DEBUG
 
-    nsNamedVector(const char* name = 0, PRUint32 initialSize = 0)
-        : nsVoidArray(initialSize),
-          mName(name)
-    {
-    }
-};
-
-static void *
-_hash_alloc_table(void *pool, PRSize size)
-{
-    return operator new(size);
-}
+PRCallOnceType BlockingResourceBase::sCallOnce;
+PRUintn BlockingResourceBase::sResourceAcqnChainFrontTPI = (PRUintn)-1;
+BlockingResourceBase::DDT BlockingResourceBase::sDeadlockDetector;
 
-static void 
-_hash_free_table(void *pool, void *item)
-{
-    operator delete(item);
-}
-
-static PLHashEntry *
-_hash_alloc_entry(void *pool, const void *key)
-{
-    return new PLHashEntry;
-}
-
-/*
- * Because monitors and locks may be associated with an mozilla::BlockingResourceBase,
- * without having had their associated nsNamedVector created explicitly in
- * nsAutoMonitor::NewMonitor/DeleteMonitor, we need to provide a freeEntry
- * PLHashTable hook, to avoid leaking nsNamedVectors which are replaced by
- * nsAutoMonitor::NewMonitor.
- *
- * There is still a problem with the OrderTable containing orphaned
- * nsNamedVector entries, for manually created locks wrapped by nsAutoLocks.
- * (there should be no manually created monitors wrapped by nsAutoMonitors:
- * you should use nsAutoMonitor::NewMonitor and nsAutoMonitor::DestroyMonitor
- * instead of PR_NewMonitor and PR_DestroyMonitor).  These lock vectors don't
- * strictly leak, as they are killed on shutdown, but there are unnecessary
- * named vectors in the hash table that outlive their associated locks.
- *
- * XXX so we should have nsLock, nsMonitor, etc. and strongly type their
- * XXX nsAutoXXX counterparts to take only the non-auto types as inputs
- */
-static void 
-_hash_free_entry(void *pool, PLHashEntry *entry, PRUintn flag)
+bool
+BlockingResourceBase::DeadlockDetectorEntry::Print(
+    const DDT::ResourceAcquisition& aFirstSeen,
+    nsACString& out,
+    bool aPrintFirstSeenCx) const
 {
-    nsNamedVector* vec = (nsNamedVector*) entry->value;
-    if (vec) {
-        entry->value = 0;
-        delete vec;
-    }
-    if (flag == HT_FREE_ENTRY)
-        delete entry;
-}
-
-static const PLHashAllocOps _hash_alloc_ops = {
-    _hash_alloc_table, _hash_free_table,
-    _hash_alloc_entry, _hash_free_entry
-};
-
-static PRIntn
-_purge_one(PLHashEntry* he, PRIntn cnt, void* arg)
-{
-    nsNamedVector* vec = (nsNamedVector*) he->value;
-
-    if (he->key == arg)
-        return HT_ENUMERATE_REMOVE;
-    vec->RemoveElement(arg);
-    return HT_ENUMERATE_NEXT;
-}
+    CallStack lastAcquisition = mAcquisitionContext; // RACY, but benign
+    bool maybeCurrentlyAcquired = (CallStack::kNone != lastAcquisition);
+    CallStack printAcquisition =
+        (aPrintFirstSeenCx || !maybeCurrentlyAcquired) ?
+            aFirstSeen.mCallContext : lastAcquisition;
 
-static void
-OnResourceRecycle(void* aResource)
-{
-    NS_PRECONDITION(OrderTable, "should be inited!");
-
-    PR_Lock(OrderTableLock);
-    PL_HashTableEnumerateEntries(OrderTable, _purge_one, aResource);
-    PR_Unlock(OrderTableLock);
-}
+    fprintf(stderr, "--- %s : %s",
+            kResourceTypeName[mType], mName);
+    out += BlockingResourceBase::kResourceTypeName[mType];
+    out += " : ";
+    out += mName;
 
-static PLHashNumber
-_hash_pointer(const void* key)
-{
-    return PLHashNumber(NS_PTR_TO_INT32(key)) >> 2;
-}
-
-// TODO just included for function below
-#include "prcmon.h"
-
-// Must be single-threaded here, early in primordial thread.
-static void InitAutoLockStatics()
-{
-    (void) PR_NewThreadPrivateIndex(&ResourceAcqnChainFrontTPI, 0);
-    OrderTable = PL_NewHashTable(64, _hash_pointer,
-                                 PL_CompareValues, PL_CompareValues,
-                                 &_hash_alloc_ops, 0);
-    if (OrderTable && !(OrderTableLock = PR_NewLock())) {
-        PL_HashTableDestroy(OrderTable);
-        OrderTable = 0;
+    if (maybeCurrentlyAcquired) {
+        fputs(" (currently acquired)", stderr);
+        out += " (currently acquired)\n";
     }
 
-    if (OrderTable && !(ResourceMutex = PR_NewLock())) {
-        PL_HashTableDestroy(OrderTable);
-        OrderTable = 0;
-    }
+    fputs(" calling context\n", stderr);
+    printAcquisition.Print(stderr);
 
-    // TODO unnecessary after API changes
-    PR_CSetOnMonitorRecycle(OnResourceRecycle);
+    return maybeCurrentlyAcquired;
 }
 
-/* TODO re-enable this after API change.  with backwards compatibility
- enabled, it conflicts with the impl in nsAutoLock.cpp.  Not freeing
- this stuff will "leak" memory that is cleanup up when the process
- exits. */
-#if 0
-void _FreeAutoLockStatics()
-{
-    PLHashTable* table = OrderTable;
-    if (!table) return;
 
-    // Called at shutdown, so we don't need to lock.
-    // TODO unnecessary after API changes
-    PR_CSetOnMonitorRecycle(0);
-    PR_DestroyLock(OrderTableLock);
-    OrderTableLock = 0;
-    PL_HashTableDestroy(table);
-    OrderTable = 0;
-}
-#endif
-
-
-static nsNamedVector* GetVector(PLHashTable* table, const void* key)
+BlockingResourceBase::BlockingResourceBase(
+    const char* aName,
+    BlockingResourceBase::BlockingResourceType aType)
 {
-    PLHashNumber hash = _hash_pointer(key);
-    PLHashEntry** hep = PL_HashTableRawLookup(table, hash, key);
-    PLHashEntry* he = *hep;
-    if (he)
-        return (nsNamedVector*) he->value;
-    nsNamedVector* vec = new nsNamedVector();
-    if (vec)
-        PL_HashTableRawAdd(table, hep, hash, key, vec);
-    return vec;
-}
-
-static void OnResourceCreated(const void* key, const char* name )
-{
-    NS_PRECONDITION(key && OrderTable, "should be inited!");
+    // PR_CallOnce guaranatees that InitStatics is called in a
+    // thread-safe way
+    if (PR_SUCCESS != PR_CallOnce(&sCallOnce, InitStatics))
+        NS_RUNTIMEABORT("can't initialize blocking resource static members");
 
-    nsNamedVector* value = new nsNamedVector(name);
-    if (value) {
-        PR_Lock(OrderTableLock);
-        PL_HashTableAdd(OrderTable, key, value);
-        PR_Unlock(OrderTableLock);
-    }
-}
+    mDDEntry = new BlockingResourceBase::DeadlockDetectorEntry(aName, aType);
+    if (!mDDEntry)
+        NS_RUNTIMEABORT("can't allocated deadlock detector entry");
 
-// We maintain an acyclic graph in OrderTable, so recursion can't diverge.
-static PRBool Reachable(PLHashTable* table, const void* goal, const void* start)
-{
-    PR_ASSERT(goal);
-    PR_ASSERT(start);
-    nsNamedVector* vec = GetVector(table, start);
-    for (PRUint32 i = 0, n = vec->Count(); i < n; i++) {
-        void* aResource = vec->ElementAt(i);
-        if (aResource == goal || Reachable(table, goal, aResource))
-            return PR_TRUE;
-    }
-    return PR_FALSE;
+    mChainPrev = 0;
+    sDeadlockDetector.Add(mDDEntry);
 }
 
-static PRBool WellOrdered(const void* aResource1, const void* aResource2,
-                          const void *aCallsite2, PRUint32* aIndex2p,
-                          nsNamedVector** aVec1p, nsNamedVector** aVec2p)
+
+BlockingResourceBase::~BlockingResourceBase()
 {
-    NS_ASSERTION(OrderTable && OrderTableLock, "supposed to be initialized!");
-
-    PRBool rv = PR_TRUE;
-    PLHashTable* table = OrderTable;
-
-    PR_Lock(OrderTableLock);
-
-    // Check whether we've already asserted (addr1 < addr2).
-    nsNamedVector* vec1 = GetVector(table, aResource1);
-    if (vec1) {
-        PRUint32 i, n;
-
-        for (i = 0, n = vec1->Count(); i < n; i++)
-            if (vec1->ElementAt(i) == aResource2)
-                break;
-
-        if (i == n) {
-            // Now check for (addr2 < addr1) and return false if so.
-            nsNamedVector* vec2 = GetVector(table, aResource2);
-            if (vec2) {
-                for (i = 0, n = vec2->Count(); i < n; i++) {
-                    void* aResourcei = vec2->ElementAt(i);
-                    PR_ASSERT(aResourcei);
-                    if (aResourcei == aResource1 
-                        || Reachable(table, aResource1, aResourcei)) {
-                        *aIndex2p = i;
-                        *aVec1p = vec1;
-                        *aVec2p = vec2;
-                        rv = PR_FALSE;
-                        break;
-                    }
-                }
-
-                if (rv) {
-                    // Insert (addr1 < addr2) into the order table.
-                    // XXX fix plvector/nsVector to use const void*
-                    vec1->AppendElement((void*) aResource2);
-#ifdef NS_TRACE_MALLOC
-                    vec1->mInnerSites.AppendElement((void*) aCallsite2);
-#endif
-                }
-            }
-        }
-    }
-
-    // all control flow must pass through this point
-//unlock:
-    PR_Unlock(OrderTableLock);
-    return rv;
+    // we don't check for really obviously bad things like freeing
+    // Mutexes while they're still locked.  it is assumed that the
+    // base class, or its underlying primitive, will check for such
+    // stupid mistakes.
+    mChainPrev = 0;             // racy only for stupidly buggy client code
+    mDDEntry = 0;               // owned by deadlock detector
 }
 
-//
-// BlockingResourceBase implementation
-//
-// Note that in static/member functions, user code abiding by the 
-// BlockingResourceBase API's contract gives us the following guarantees:
-//
-//  - mResource is not NULL
-//  - mResource points to a valid underlying resource
-//  - mResource is NOT shared with any other mozilla::BlockingResourceBase
-//
-// If user code violates the API contract, the behavior of the following
-// functions is undefined.  So no error checking is strictly necessary.
-//
-// That said, assertions of the the above facts are sprinkled throughout the
-// following code, to check for errors in user code.
-//
-namespace mozilla {
-
 
 void
-BlockingResourceBase::Init(void* aResource, 
-                           const char* aName, 
-                           BlockingResourceBase::BlockingResourceType aType)
-{
-    if (NS_UNLIKELY(ResourceAcqnChainFrontTPI == PRUintn(-1)))
-        InitAutoLockStatics();
-
-    NS_PRECONDITION(aResource, "null resource");
-
-    OnResourceCreated(aResource, aName);
-    mResource = aResource;
-    mChainPrev = 0;
-    mType = aType;
-}
-
-BlockingResourceBase::~BlockingResourceBase()
+BlockingResourceBase::CheckAcquire(const CallStack& aCallContext)
 {
-    NS_PRECONDITION(mResource, "bad subclass impl, or double free");
-
-    // we don't expect to find this resouce in the acquisition chain.
-    // it should have been Release()'n as many times as it has been 
-    // Acquire()ed, before this destructor was called.
-    // additionally, WE are the only ones who can create underlying 
-    // resources, so there should be one underlying instance per 
-    // BlockingResourceBase.  thus we don't need to do any cleanup unless 
-    // client code has done something seriously and obviously wrong.
-    // that, plus the potential performance impact of full cleanup, mean
-    // that it has been removed for now.
-
-    OnResourceRecycle(mResource);
-    mResource = 0;
-    mChainPrev = 0;
-}
-
-void BlockingResourceBase::Acquire()
-{
-    NS_PRECONDITION(mResource, "bad base class impl or double free");
-    PR_ASSERT_CURRENT_THREAD_OWNS_LOCK(ResourceMutex);
-
-    if (mType == eCondVar) {
-        NS_NOTYETIMPLEMENTED("TODO: figure out how to Acquire() condvars");
+    if (eCondVar == mDDEntry->mType) {
+        NS_NOTYETIMPLEMENTED(
+            "FIXME bug 456272: annots. to allow CheckAcquire()ing condvars");
         return;
     }
 
-    BlockingResourceBase* chainFront = 
-        (BlockingResourceBase*) 
-            PR_GetThreadPrivate(ResourceAcqnChainFrontTPI);
-
-    if (eMonitor == mType) {
-        // reentering a monitor: the old implementation ensured that this
-        // was only done immediately after a previous entry.  little
-        // tricky here since we can't rely on the monitor already having
-        // been entered, as AutoMonitor used to let us do (sort of)
+    BlockingResourceBase* chainFront = ResourceChainFront();
+    nsAutoPtr<DDT::ResourceAcquisitionArray> cycle(
+        sDeadlockDetector.CheckAcquisition(
+            chainFront ? chainFront->mDDEntry : 0, mDDEntry,
+            aCallContext));
+    if (!cycle)
+        return;
 
-        if (this == chainFront) {
-            // acceptable reentry, and nothing to update.
-            return;
-        } 
-        else if (chainFront) {
-            BlockingResourceBase* br = chainFront->mChainPrev;
-            while (br) {
-                if (br == this) {
-                    NS_ASSERTION(br != this, 
-                                 "reentered monitor after acquiring "
-                                 "other resources");
-                    // have to ignore this allocation and return.  even if
-                    // we cleaned up the old acquisition of the monitor and
-                    // put the new one at the front of the chain, we'd
-                    // almost certainly set off the deadlock detector.
-                    // this error is interesting enough.
-                    return;
-                }
-                br = br->mChainPrev;
-            }
-        }
+    fputs("###!!! ERROR: Potential deadlock detected:\n", stderr);
+    nsCAutoString out("Potential deadlock detected:\n");
+    bool maybeImminent = PrintCycle(cycle, out);
+
+    if (maybeImminent) {
+        fputs("\n###!!! Deadlock may happen NOW!\n\n", stderr);
+        out.Append("\n###!!! Deadlock may happen NOW!\n\n");
+    } else {
+        fputs("\nDeadlock may happen for some other execution\n\n",
+              stderr);
+        out.Append("\nDeadlock may happen for some other execution\n\n");
     }
 
-    const void* callContext =
-#ifdef NS_TRACE_MALLOC
-        (const void*)NS_TraceMallocGetStackTrace();
-#else
-        nsnull
-#endif
-        ;
-
-    if (eMutex == mType
-        && chainFront == this
-        && !(chainFront->mChainPrev)) {
-        // corner case: acquire only a single lock, then try to reacquire 
-        // the lock.  there's no entry in the order table for the first
-        // acquisition, so we might not detect this (immediate and real!) 
-        // deadlock.
-        //
-        // XXX need to remove this corner case, and get a stack trace for 
-        // first acquisition, and get the lock's name
-        char buf[128];
-        PR_snprintf(buf, sizeof buf,
-                    "Imminent deadlock between Mutex@%p and itself!",
-                    chainFront->mResource);
-
-#ifdef NS_TRACE_MALLOC
-        fputs("\nDeadlock will occur here:\n", stderr);
-        NS_TraceMallocPrintStackTrace(
-            stderr, (nsTMStackTraceIDStruct*)callContext);
-        putc('\n', stderr);
-#endif
-
-        NS_ERROR(buf);
-
-        return;                 // what else to do? we're screwed
-    }
-
-    nsNamedVector* vec1;
-    nsNamedVector* vec2;
-    PRUint32 i2;
-
-    if (!chainFront 
-        || WellOrdered(chainFront->mResource, mResource, 
-                       callContext, 
-                       &i2, 
-                       &vec1, &vec2)) {
-        mChainPrev = chainFront;
-        PR_SetThreadPrivate(ResourceAcqnChainFrontTPI, this);
-    }
-    else {
-        char buf[128];
-        PR_snprintf(buf, sizeof buf,
-                    "Potential deadlock between %s%s@%p and %s%s@%p",
-                    vec1->mName ? vec1->mName : "",
-                    kResourceTypeNames[chainFront->mType],
-                    chainFront->mResource,
-                    vec2->mName ? vec2->mName : "",
-                    kResourceTypeNames[mType],
-                    mResource);
-
-#ifdef NS_TRACE_MALLOC
-        fprintf(stderr, "\n*** %s\n\nStack of current acquisition:\n", buf);
-        NS_TraceMallocPrintStackTrace(
-            stderr, NS_TraceMallocGetStackTrace());
-
-        fputs("\nStack of conflicting acquisition:\n", stderr);
-        NS_TraceMallocPrintStackTrace(
-            stderr, (nsTMStackTraceIDStruct *)vec2->mInnerSites.ElementAt(i2));
-        putc('\n', stderr);
-#endif
-
-        NS_ERROR(buf);
-
-        // because we know the latest acquisition set off the deadlock,
-        // detector, it's debatable whether we should append it to the 
-        // acquisition chain; it might just trigger later errors that 
-        // have already been reported here.  I choose not too add it.
-    }
+    // XXX can customize behavior on whether we /think/ deadlock is
+    // XXX about to happen.  for example:
+    // XXX   if (maybeImminent)
+    //           NS_RUNTIMEABORT(out.get());
+    NS_ERROR(out.get());
 }
 
-void BlockingResourceBase::Release()
+
+void
+BlockingResourceBase::Acquire(const CallStack& aCallContext)
 {
-    NS_PRECONDITION(mResource, "bad base class impl or double free");
-    PR_ASSERT_CURRENT_THREAD_OWNS_LOCK(ResourceMutex);
-
-    if (mType == eCondVar) {
-        NS_NOTYETIMPLEMENTED("TODO: figure out how to Release() condvars");
+    if (eCondVar == mDDEntry->mType) {
+        NS_NOTYETIMPLEMENTED(
+            "FIXME bug 456272: annots. to allow Acquire()ing condvars");
         return;
     }
+    NS_ASSERTION(mDDEntry->mAcquisitionContext == CallStack::kNone,
+                 "reacquiring already acquired resource");
 
-    BlockingResourceBase* chainFront = 
-        (BlockingResourceBase*) 
-            PR_GetThreadPrivate(ResourceAcqnChainFrontTPI);
-    NS_ASSERTION(chainFront, 
+    ResourceChainAppend(ResourceChainFront());
+    mDDEntry->mAcquisitionContext = aCallContext;
+}
+
+
+void
+BlockingResourceBase::Release()
+{
+    if (eCondVar == mDDEntry->mType) {
+        NS_NOTYETIMPLEMENTED(
+            "FIXME bug 456272: annots. to allow Release()ing condvars");
+        return;
+    }
+      
+    BlockingResourceBase* chainFront = ResourceChainFront();
+    NS_ASSERTION(chainFront
+                 && CallStack::kNone != mDDEntry->mAcquisitionContext,
                  "Release()ing something that hasn't been Acquire()ed");
 
-    if (NS_LIKELY(chainFront == this)) {
-        PR_SetThreadPrivate(ResourceAcqnChainFrontTPI, mChainPrev);
+    if (chainFront == this) {
+        ResourceChainRemove();
     }
     else {
         // not an error, but makes code hard to reason about.
-        NS_WARNING("you're releasing a resource in non-LIFO order; why?");
-
+        NS_WARNING("Resource acquired at calling context\n");
+        mDDEntry->mAcquisitionContext.Print(stderr);
+        NS_WARNING("\nis being released in non-LIFO order; why?");
+        
+        // remove this resource from wherever it lives in the chain
         // we walk backwards in order of acquisition:
         //  (1)  ...node<-prev<-curr...
         //              /     /
         //  (2)  ...prev<-curr...
         BlockingResourceBase* curr = chainFront;
         BlockingResourceBase* prev = nsnull;
         while (curr && (prev = curr->mChainPrev) && (prev != this))
             curr = prev;
         if (prev == this)
             curr->mChainPrev = prev->mChainPrev;
     }
+
+    mDDEntry->mAcquisitionContext = CallStack::kNone;
 }
 
+
+bool
+BlockingResourceBase::PrintCycle(const DDT::ResourceAcquisitionArray* aCycle,
+                                 nsACString& out)
+{
+    NS_ASSERTION(aCycle->Length() > 1, "need > 1 element for cycle!");
+
+    bool maybeImminent = true;
+
+    fputs("=== Cyclical dependency starts at\n", stderr);
+    out += "Cyclical dependency starts at\n";
+
+    const DDT::ResourceAcquisition res = aCycle->ElementAt(0);
+    maybeImminent &= res.mResource->Print(res, out);
+
+    DDT::ResourceAcquisitionArray::index_type i;
+    DDT::ResourceAcquisitionArray::size_type len = aCycle->Length();
+    const DDT::ResourceAcquisition* it = 1 + aCycle->Elements();
+    for (i = 1; i < len - 1; ++i, ++it) {
+        fputs("\n--- Next dependency:\n", stderr);
+        out += "Next dependency:\n";
+
+        maybeImminent &= it->mResource->Print(*it, out);
+    }
+
+    fputs("\n=== Cycle completed at\n", stderr);
+    out += "Cycle completed at\n";
+    it->mResource->Print(*it, out, true);
+
+    return maybeImminent;
+}
+
+
 //
 // Debug implementation of Mutex
 void
 Mutex::Lock()
 {
-    PR_Lock(ResourceMutex);
-    Acquire();
-    PR_Unlock(ResourceMutex);
+    CallStack callContext = CallStack();
 
+    CheckAcquire(callContext);
     PR_Lock(mLock);
+    Acquire(callContext);       // protected by mLock
 }
 
 void
 Mutex::Unlock()
 {
+    Release();                  // protected by mLock
     PRStatus status = PR_Unlock(mLock);
-    NS_ASSERTION(PR_SUCCESS == status, "problem Unlock()ing");
+    NS_ASSERTION(PR_SUCCESS == status, "bad Mutex::Unlock()");
+}
 
-    PR_Lock(ResourceMutex);
-    Release();
-    PR_Unlock(ResourceMutex);
-}
 
 //
 // Debug implementation of Monitor
-void 
-Monitor::Enter() 
+void
+Monitor::Enter()
 {
-    PR_Lock(ResourceMutex);
-    ++mEntryCount;
-    Acquire();
-    PR_Unlock(ResourceMutex);
+    BlockingResourceBase* chainFront = ResourceChainFront();
+
+    // the code below implements monitor reentrancy semantics
+
+    if (this == chainFront) {
+        // immediately re-entered the monitor: acceptable
+        PR_EnterMonitor(mMonitor);
+        ++mEntryCount;
+        return;
+    }
 
+    CallStack callContext = CallStack();
+    
+    // this is sort of a hack around not recording the thread that
+    // owns this monitor
+    if (chainFront) {
+        for (BlockingResourceBase* br = ResourceChainPrev(chainFront);
+             br;
+             br = ResourceChainPrev(br)) {
+            if (br == this) {
+                NS_WARNING(
+                    "Re-entering Monitor after acquiring other resources.\n"
+                    "At calling context\n");
+                GetAcquisitionContext().Print(stderr);
+
+                // show the caller why this is potentially bad
+                CheckAcquire(callContext);
+
+                PR_EnterMonitor(mMonitor);
+                ++mEntryCount;
+                return;
+            }
+        }
+    }
+
+    CheckAcquire(callContext);
     PR_EnterMonitor(mMonitor);
+    NS_ASSERTION(0 == mEntryCount, "Monitor isn't free!");
+    Acquire(callContext);       // protected by mMonitor
+    mEntryCount = 1;
 }
 
 void
 Monitor::Exit()
 {
+    if (0 == --mEntryCount)
+        Release();              // protected by mMonitor
     PRStatus status = PR_ExitMonitor(mMonitor);
-    NS_ASSERTION(PR_SUCCESS == status, "bad ExitMonitor()");
+    NS_ASSERTION(PR_SUCCESS == status, "bad Monitor::Exit()");
+}
+
+nsresult
+Monitor::Wait(PRIntervalTime interval)
+{
+    AssertCurrentThreadIn();
 
-    PR_Lock(ResourceMutex);
-    if (--mEntryCount == 0)
-        Release();
-    PR_Unlock(ResourceMutex);
+    // save monitor state and reset it to empty
+    PRInt32 savedEntryCount = mEntryCount;
+    CallStack savedAcquisitionContext = GetAcquisitionContext();
+    BlockingResourceBase* savedChainPrev = mChainPrev;
+    mEntryCount = 0;
+    SetAcquisitionContext(CallStack::kNone);
+    mChainPrev = 0;
+
+    // give up the monitor until we're back from Wait()
+    nsresult rv =
+        PR_Wait(mMonitor, interval) == PR_SUCCESS ?
+            NS_OK : NS_ERROR_FAILURE;
+    
+    // restore saved state
+    mEntryCount = savedEntryCount;
+    SetAcquisitionContext(savedAcquisitionContext);
+    mChainPrev = savedChainPrev;
+
+    return rv;
 }
 
 
-} // namespace mozilla
+//
+// Debug implementation of CondVar
+nsresult
+CondVar::Wait(PRIntervalTime interval)
+{
+    AssertCurrentThreadOwnsMutex();
+
+    // save mutex state and reset to empty
+    CallStack savedAcquisitionContext = mLock->GetAcquisitionContext();
+    BlockingResourceBase* savedChainPrev = mLock->mChainPrev;
+    mLock->SetAcquisitionContext(CallStack::kNone);
+    mLock->mChainPrev = 0;
+
+    // give up mutex until we're back from Wait()
+    nsresult rv =
+        PR_WaitCondVar(mCvar, interval) == PR_SUCCESS ?
+            NS_OK : NS_ERROR_FAILURE;
+
+    // restore saved state
+    mLock->SetAcquisitionContext(savedAcquisitionContext);
+    mLock->mChainPrev = savedChainPrev;
+
+    return rv;
+}
+
+#endif // ifdef DEBUG
 
 
-#endif // ifdef DEBUG
+} // namespace mozilla
--- a/xpcom/glue/BlockingResourceBase.h
+++ b/xpcom/glue/BlockingResourceBase.h
@@ -16,16 +16,17 @@
  * The Original Code is mozilla.org code.
  *
  * The Initial Developer of the Original Code is
  * Netscape Communications Corporation.
  * Portions created by the Initial Developer are Copyright (C) 1998
  * the Initial Developer. All Rights Reserved.
  *
  * Contributor(s):
+ *   Chris Jones <jones.chris.g@gmail.com>
  *
  * Alternatively, the contents of this file may be used under the terms of
  * either of the GNU General Public License Version 2 or later (the "GPL"),
  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  * in which case the provisions of the GPL or the LGPL are applicable instead
  * of those above. If you wish to allow use of your version of this file only
  * under the terms of either the GPL or the LGPL, and not to allow others to
  * use your version of this file under the terms of the MPL, indicate your
@@ -35,151 +36,325 @@
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 
 #ifndef mozilla_BlockingResourceBase_h
 #define mozilla_BlockingResourceBase_h
 
-#include "nscore.h"
+#include "prlock.h"
 #include "prlog.h"
+
+#include "nscore.h"
+#include "nsDebug.h"
 #include "nsError.h"
-#include "nsDebug.h"
+
+#ifdef DEBUG
+#include "prinit.h"
+#include "prthread.h"
+
+#include "nsStringGlue.h"
+
+#include "mozilla/DeadlockDetector.h"
+#endif
 
 //
 // This header is not meant to be included by client code.
 //
 
 namespace mozilla {
 
 
 /**
+ * BlockingResourceBase
  * Base class of resources that might block clients trying to acquire them.  
- * Aids in debugging, deadlock detection, etc.
+ * Does debugging and deadlock detection in DEBUG builds.
  **/
 class NS_COM_GLUE BlockingResourceBase
 {
-protected:
-    BlockingResourceBase() {
-    }
+public:
     // Needs to be kept in sync with kResourceTypeNames.
     enum BlockingResourceType { eMutex, eMonitor, eCondVar };
 
+    /**
+     * kResourceTypeName
+     * Human-readable version of BlockingResourceType enum.
+     */
+    static const char* const kResourceTypeName[];
+
+
 #ifdef DEBUG
+
+private:
+    // forward declaration for the following typedef
+    struct DeadlockDetectorEntry;
+
+    // ``DDT'' = ``Deadlock Detector Type''
+    typedef DeadlockDetector<DeadlockDetectorEntry> DDT;
+
+    /**
+     * DeadlockDetectorEntry
+     * We free BlockingResources, but we never free entries in the
+     * deadlock detector.  This struct outlives its BlockingResource
+     * and preserves all the state needed to print subsequent
+     * error messages.
+     *
+     * These objects are owned by the deadlock detector.
+     */
+    struct DeadlockDetectorEntry
+    {
+        DeadlockDetectorEntry(const char* aName,
+                              BlockingResourceType aType) :
+            mName(aName),
+            mType(aType),
+            mAcquisitionContext(CallStack::kNone)
+        {
+        }
+        
+        /**
+         * Print
+         * Write a description of this blocking resource to |out|.  If
+         * the resource appears to be currently acquired, the current
+         * acquisition context is printed and true is returned.
+         * Otherwise, we print the context from |aFirstSeen|, the
+         * first acquisition from which the code calling |Print()|
+         * became interested in us, and return false.  |Print()| can
+         * be forced to print the context from |aFirstSeen| regardless
+         * by passing |aPrintFirstSeenCx=true|.
+         *
+         * *NOT* thread safe.  Reads |mAcquisitionContext| without
+         * synchronization, but this will not cause correctness
+         * problems.
+         *
+         * FIXME bug 456272: hack alert: because we can't write call
+         * contexts into strings, all info is written to stderr, but
+         * only some info is written into |out|
+         */
+        bool Print(const DDT::ResourceAcquisition& aFirstSeen,
+                   nsACString& out,
+                   bool aPrintFirstSeenCx=false) const;
+
+        /**
+         * mName
+         * A descriptive name for this resource.  Used in error
+         * messages etc.
+         */
+        const char* mName;
+        /**
+         * mType
+         * The more specific type of this resource.  Used to implement
+         * special semantics (e.g., reentrancy of monitors).
+         **/
+        BlockingResourceType mType;
+        /**
+         * mAcquisitionContext
+         * The calling context from which this resource was acquired, or
+         * |CallStack::kNone| if it is currently free (or freed).
+         */
+        CallStack mAcquisitionContext;
+    };
+
+protected:
+    /**
+     * BlockingResourceBase
+     * Initialize this blocking resource.  Also hooks the resource into
+     * instrumentation code.
+     *
+     * Thread safe.
+     *
+     * @param aName A meaningful, unique name that can be used in
+     *              error messages, et al.
+     * @param aType The specific type of |this|, if any.
+     **/
+    BlockingResourceBase(const char* aName, BlockingResourceType aType);
+
     ~BlockingResourceBase();
 
     /**
-     * Initialize this blocking resource.  Also hooks the resource into
-     * instrumentation code.
-     * @param aResource Unique handle for the underlying blocking resource.
-     * @param aName A meaningful, unique name that can be used in
-     *              error messages, et al.
-     * @param aType The specific type of |aResource|, if any.
+     * CheckAcquire
+     *
+     * Thread safe.
+     *
+     * @param aCallContext the client's calling context from which the
+     *        original acquisition request was made.
      **/
-    void Init(void* aResource, 
-              const char* aName,
-              BlockingResourceType aType);
+    void CheckAcquire(const CallStack& aCallContext);
 
-    /*
-     * The following variables and methods are used by the deadlock detector.
-     * To understand how they're used, it's best to give a quick overview
-     * of how the deadlock detector works.
+    /**
+     * Acquire
      *
-     * 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 simultaneous
-     * run with a thread acquiring them according to the second order.
-     * If this happens under the right conditions, then the
-     * acquisitions will deadlock.
+     * *NOT* thread safe.  Requires ownership of underlying resource.
      *
-     * 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 the following:
-     *   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$)
+     * @param aCallContext the client's calling context from which the
+     *        original acquisition request was made.
+     **/
+    void Acquire(const CallStack& aCallContext); //NS_NEEDS_RESOURCE(this)
+
+    /**
+     * Release
+     * Remove this resource from the current thread's acquisition chain.
+     * The resource does not have to be at the front of the chain, although
+     * it is confusing to release resources in a different order than they
+     * are acquired.  This generates a warning.
      *
-     *   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).
+     * *NOT* thread safe.  Requires ownership of underlying resource.
+     **/
+    void Release();             //NS_NEEDS_RESOURCE(this)
+
+    /**
+     * PrintCycle
+     * Append to |out| detailed information about the circular
+     * dependency in |cycle|.  Returns true if it *appears* that this
+     * cycle may represent an imminent deadlock, but this is merely a
+     * heuristic; the value returned may be a false positive or false
+     * negative.
      *
-     *   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 deadlocking-
-     * inducingly).
+     * *NOT* thread safe.  Calls |Print()|.
      *
-     * In reality, this is somewhat more complicated because each thread
-     * has its own acquisition chain.  In addition, the example above 
-     * elides several important details from the detector implementation.
+     * FIXME bug 456272 hack alert: because we can't write call
+     * contexts into strings, all info is written to stderr, but only
+     * some info is written into |out|
      */
+    static bool PrintCycle(const DDT::ResourceAcquisitionArray* cycle,
+                           nsACString& out);
 
     /**
-     * mResource
-     * Some handle to a resource that may block acquisition.  Used to 
-     * identify the resource in acquisition chains.
-     **/
-    void* mResource;
+     * ResourceChainFront
+     *
+     * Thread safe.
+     *
+     * @return the front of the resource acquisition chain, i.e., the last
+     *         resource acquired.
+     */
+    static BlockingResourceBase* ResourceChainFront()
+    {
+        return (BlockingResourceBase*)
+            PR_GetThreadPrivate(sResourceAcqnChainFrontTPI);
+    }
+
+    /**
+     * ResourceChainPrev
+     *
+     * *NOT* thread safe.  Requires ownership of underlying resource.
+     */
+    static BlockingResourceBase*
+    ResourceChainPrev(const BlockingResourceBase* aResource)
+    {
+        return aResource->mChainPrev;
+    } //NS_NEEDS_RESOURCE(this)
 
     /**
-     * mType
-     * The more specific type of this resource.  Used to implement special
-     * semantics (e.g., reentrancy of monitors.)
-     **/
-    BlockingResourceType mType;
+     * ResourceChainAppend
+     * Set |this| to the front of the resource acquisition chain, and link
+     * |this| to |aPrev|.
+     *
+     * *NOT* thread safe.  Requires ownership of underlying resource.
+     */
+    void ResourceChainAppend(BlockingResourceBase* aPrev)
+    {
+        mChainPrev = aPrev;
+        PR_SetThreadPrivate(sResourceAcqnChainFrontTPI, this);
+    } //NS_NEEDS_RESOURCE(this)
+
+    /**
+     * ResourceChainRemove
+     * Remove |this| from the front of the resource acquisition chain.
+     *
+     * *NOT* thread safe.  Requires ownership of underlying resource.
+     */
+    void ResourceChainRemove()
+    {
+        NS_ASSERTION(this == ResourceChainFront(), "not at chain front");
+        PR_SetThreadPrivate(sResourceAcqnChainFrontTPI, mChainPrev);
+    } //NS_NEEDS_RESOURCE(this)
+
+    /**
+     * GetAcquisitionContext
+     * Return the calling context from which this resource was acquired,
+     * or CallStack::kNone if it's currently free.
+     *
+     * *NOT* thread safe.  Requires ownership of underlying resource.
+     */
+    CallStack
+    GetAcquisitionContext()
+    {
+        return mDDEntry->mAcquisitionContext;
+    }
+
+    /**
+     * SetAcquisitionContext
+     * Set the calling context from which this resource was acquired.
+     *
+     * *NOT* thread safe.  Requires ownership of underlying resource.
+     */
+    void
+    SetAcquisitionContext(CallStack aAcquisitionContext)
+    {
+        mDDEntry->mAcquisitionContext = aAcquisitionContext;
+    }
 
     /**
      * mChainPrev
      * A series of resource acquisitions creates a chain of orders.  This
      * chain is implemented as a linked list; |mChainPrev| points to the
-     * resource most recently Show()'n before this one.
+     * resource most recently Acquire()'d before this one.
      **/
     BlockingResourceBase* mChainPrev;
 
+private:
     /**
-     * Acquire
-     * Add this resource to the front of the current thread's acquisition 
-     * chain.  Should be called by, e.g., Mutex::Lock().
-     **/
-    void Acquire();
-    
+     * mDDEntry
+     * The key for this BlockingResourceBase in the deadlock detector.
+     */
+    DeadlockDetectorEntry* mDDEntry;
+
+    /**
+     * sCallOnce
+     * Ensures static members are initialized only once, and in a
+     * thread-safe way.
+     */
+    static PRCallOnceType sCallOnce;
+
     /**
-     * Release
-     * Remove this resource from the current thread's acquisition chain.
-     * The resource does not have to be at the front of the chain, although
-     * it is confusing to release resources in a different order than they
-     * are acquired.
-     **/
-    void Release();
+     * sResourceAcqnChainFrontTPI
+     * Thread-private index to the front of each thread's resource
+     * acquisition chain.
+     */
+    static PRUintn sResourceAcqnChainFrontTPI;
+
+    /**
+     * sDeadlockDetector
+     * Does as named.
+     */
+    static DDT sDeadlockDetector;
 
-#else
-    ~BlockingResourceBase() {
+    /**
+     * InitStatics
+     *
+     * *NOT* thread safe.
+     *
+     * Inititialize static members of BlockingResourceBase that can't
+     * be statically initialized.
+     */
+    static PRStatus InitStatics() {
+        PR_NewThreadPrivateIndex(&sResourceAcqnChainFrontTPI, 0);
+        return PR_SUCCESS;
     }
 
-    void Init(void* aResource, 
-              const char* aName,
-              BlockingResourceType aType) { }
+
+#else  // non-DEBUG implementation
 
-    void            Acquire() { }
-    void            Release() { }
+    BlockingResourceBase(const char* aName, BlockingResourceType aType)
+    {
+    }
+
+    ~BlockingResourceBase()
+    {
+    }
 
 #endif
 };
 
 
 } // namespace mozilla
 
 
--- a/xpcom/glue/CondVar.h
+++ b/xpcom/glue/CondVar.h
@@ -55,93 +55,108 @@ namespace mozilla {
 class NS_COM_GLUE CondVar : BlockingResourceBase
 {
 public:
     /**
      * CondVar
      *
      * The CALLER owns |lock|.
      *
-     * @param lock An Mutex to associate with this condition variable.
-     * @param name A name which can reference this monitor
+     * @param aLock An Mutex to associate with this condition variable.
+     * @param aName A name which can reference this monitor
      * @returns If failure, nsnull.
      *          If success, a valid Monitor* which must be destroyed
      *          by Monitor::DestroyMonitor()
      **/
-    CondVar(Mutex& aLock, const char* name)
-        : mLock(&aLock) {
+    CondVar(Mutex& aLock, const char* aName) :
+        BlockingResourceBase(aName, eCondVar),
+        mLock(&aLock)
+    {
         // |lock| must necessarily already be known to the deadlock detector
         mCvar = PR_NewCondVar(mLock->mLock);
         if (!mCvar)
             NS_RUNTIMEABORT("Can't allocate mozilla::CondVar");
-        Init(mCvar, name, eCondVar);
     }
 
     /**
      * ~CondVar
      * Clean up after this CondVar, but NOT its associated Mutex.
      **/
-    ~CondVar() {
+    ~CondVar()
+    {
         NS_ASSERTION(mCvar && mLock,
                      "improperly constructed CondVar or double free");
         PR_DestroyCondVar(mCvar);
         mCvar = 0;
         mLock = 0;
     }
 
+#ifndef DEBUG
     /** 
      * Wait
      * @see prcvar.h 
      **/      
-    nsresult Wait(PRIntervalTime interval = PR_INTERVAL_NO_TIMEOUT) {
+    nsresult Wait(PRIntervalTime interval = PR_INTERVAL_NO_TIMEOUT)
+    {
         // NSPR checks for lock ownership
         return PR_WaitCondVar(mCvar, interval) == PR_SUCCESS
             ? NS_OK : NS_ERROR_FAILURE;
     }
+#else
+    nsresult Wait(PRIntervalTime interval = PR_INTERVAL_NO_TIMEOUT);
+#endif // ifndef DEBUG
 
     /** 
      * Notify
      * @see prcvar.h 
      **/      
-    nsresult Notify() {
+    nsresult Notify()
+    {
         // NSPR checks for lock ownership
         return PR_NotifyCondVar(mCvar) == PR_SUCCESS
             ? NS_OK : NS_ERROR_FAILURE;
     }
 
     /** 
      * NotifyAll
      * @see prcvar.h 
      **/      
-    nsresult NotifyAll() {
+    nsresult NotifyAll()
+    {
         // NSPR checks for lock ownership
         return PR_NotifyAllCondVar(mCvar) == PR_SUCCESS
             ? NS_OK : NS_ERROR_FAILURE;
     }
 
 #ifdef DEBUG
     /**
      * AssertCurrentThreadOwnsMutex
      * @see Mutex::AssertCurrentThreadOwns
      **/
-    void AssertCurrentThreadOwnsMutex () {
+    void AssertCurrentThreadOwnsMutex()
+    {
         mLock->AssertCurrentThreadOwns();
     }
 
     /**
      * AssertNotCurrentThreadOwnsMutex
      * @see Mutex::AssertNotCurrentThreadOwns
      **/
-    void AssertNotCurrentThreadOwnsMutex () {
+    void AssertNotCurrentThreadOwnsMutex()
+    {
         mLock->AssertNotCurrentThreadOwns();
     }
 
 #else
-    void AssertCurrentThreadOwnsMutex () { }
-    void AssertNotCurrentThreadOwnsMutex () { }
+    void AssertCurrentThreadOwnsMutex()
+    {
+    }
+    void AssertNotCurrentThreadOwnsMutex()
+    {
+    }
 
 #endif  // ifdef DEBUG
 
 private:
     CondVar();
     CondVar(CondVar&);
     CondVar& operator=(CondVar&);
 
new file mode 100644
--- /dev/null
+++ b/xpcom/glue/DeadlockDetector.cpp
@@ -0,0 +1,44 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: sw=4 ts=4 et :
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is mozilla.org code.
+ *
+ * The Initial Developer of the Original Code is
+ * Netscape Communications Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 1998
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Chris Jones <jones.chris.g@gmail.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#include "DeadlockDetector.h"
+
+namespace mozilla {
+const CallStack CallStack::kNone((CallStack::callstack_id) -1);
+}
new file mode 100644
--- /dev/null
+++ b/xpcom/glue/DeadlockDetector.h
@@ -0,0 +1,577 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: sw=4 ts=4 et :
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is mozilla.org code.
+ *
+ * The Initial Developer of the Original Code is
+ * Netscape Communications Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 1998
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Chris Jones <jones.chris.g@gmail.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+#ifndef mozilla_DeadlockDetector_h
+#define mozilla_DeadlockDetector_h
+
+#include <stdlib.h>
+
+#include "plhash.h"
+#include "prlock.h"
+
+#include "nsTArray.h"
+
+#ifdef NS_TRACE_MALLOC
+#  include "tracemalloc/nsTraceMalloc.h"
+#endif  // ifdef NS_TRACE_MALLOC
+
+namespace mozilla {
+
+
+// FIXME bug 456272: split this off into a convenience API on top of
+// nsStackWalk?
+class NS_COM_GLUE CallStack
+{
+private:
+#ifdef NS_TRACE_MALLOC
+    typedef nsTMStackTraceID callstack_id;
+    // needs to be a macro to avoid disturbing the backtrace
+#   define NS_GET_BACKTRACE() NS_TraceMallocGetStackTrace()
+#else
+    typedef void* callstack_id;
+#   define NS_GET_BACKTRACE() 0
+#endif  // ifdef NS_TRACE_MALLOC
+
+    callstack_id mCallStack;
+
+public:
+    /**
+     * CallStack
+     * *ALWAYS* *ALWAYS* *ALWAYS* call this with no arguments.  This
+     * constructor takes an argument *ONLY* so that |GET_BACKTRACE()|
+     * can be evaluated in the stack frame of the caller, rather than
+     * that of the constructor.
+     *
+     * *BEWARE*: this means that calling this constructor with no
+     * arguments is not the same as a "default, do-nothing"
+     * constructor: it *will* construct a backtrace.  This can cause
+     * unexpected performance issues.
+     */
+    CallStack(const callstack_id aCallStack = NS_GET_BACKTRACE()) :
+        mCallStack(aCallStack)
+    {
+    }
+    CallStack(const CallStack& aFrom) :
+        mCallStack(aFrom.mCallStack)
+    {
+    }
+    CallStack& operator=(const CallStack& aFrom)
+    {
+        mCallStack = aFrom.mCallStack;
+        return *this;
+    }
+    bool operator==(const CallStack& aOther) const
+    {
+        return mCallStack == aOther.mCallStack;
+    }
+    bool operator!=(const CallStack& aOther) const
+    {
+        return mCallStack != aOther.mCallStack;
+    }
+
+    // FIXME bug 456272: if this is split off,
+    // NS_TraceMallocPrintStackTrace should be modified to print into
+    // an nsACString
+    void Print(FILE* f) const
+    {
+#ifdef NS_TRACE_MALLOC
+        if (this != &kNone && mCallStack) {
+            NS_TraceMallocPrintStackTrace(f, mCallStack);
+            return;
+        }
+#endif
+        fputs("  [stack trace unavailable]\n", f);
+    }
+
+    /** The "null" callstack. */
+    static const CallStack kNone;
+};
+
+
+/**
+ * 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:
+    /**
+     * ResourceAcquisition
+     * Consists simply of a resource and the calling context from
+     * which it was acquired.  We pack this information together so
+     * that it can be returned back to the caller when a potential
+     * deadlock has been found.
+     */
+    struct ResourceAcquisition
+    {
+        const T* mResource;
+        CallStack mCallContext;
+
+        ResourceAcquisition(
+            const T* aResource,
+            const CallStack aCallContext=CallStack::kNone) :
+            mResource(aResource),
+            mCallContext(aCallContext)
+        {
+        }
+        ResourceAcquisition(const ResourceAcquisition& aFrom) :
+            mResource(aFrom.mResource),
+            mCallContext(aFrom.mCallContext)
+        {
+        }
+        ResourceAcquisition& operator=(const ResourceAcquisition& aFrom)
+        {
+            mResource = aFrom.mResource;
+            mCallContext = aFrom.mCallContext;
+            return *this;
+        }
+    };
+    typedef nsTArray<ResourceAcquisition> ResourceAcquisitionArray;
+
+private:
+    typedef nsTArray<PLHashEntry*> HashEntryArray;
+    typedef typename HashEntryArray::index_type index_type;
+    typedef typename HashEntryArray::size_type size_type;
+    enum {
+        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
+    {
+        OrderingEntry() :
+            mFirstSeen(CallStack::kNone),
+            mOrderedLT()        // FIXME bug 456272: set to empirical
+        {                       // dep size?
+        }
+        ~OrderingEntry()
+        {
+        }
+
+        CallStack mFirstSeen; // first site from which the resource appeared
+        HashEntryArray mOrderedLT; // this <_o Other
+    };
+
+    static void* TableAlloc(void* /*pool*/, PRSize size)
+    {
+        return operator new(size);
+    }
+    static void TableFree(void* /*pool*/, void* item)
+    {
+        operator delete(item);
+    }
+    static PLHashEntry* EntryAlloc(void* /*pool*/, const void* key)
+    {
+        return new PLHashEntry;
+    }
+    static void EntryFree(void* /*pool*/, PLHashEntry* entry, PRUintn flag)
+    {
+        delete static_cast<T*>(const_cast<void*>(entry->key));
+        delete static_cast<OrderingEntry*>(entry->value);
+        entry->value = 0;
+        if (HT_FREE_ENTRY == flag)
+            delete entry;
+    }
+    static PLHashNumber HashKey(const void* aKey)
+    {
+        return NS_PTR_TO_INT32(aKey) >> 2;
+    }
+    static const PLHashAllocOps kAllocOps;
+
+    // Hash table "interface" the rest of the code should use
+
+    PLHashEntry** GetEntry(const T* aKey)
+    {
+        return PL_HashTableRawLookup(mOrdering, HashKey(aKey), aKey);
+    }
+
+    void PutEntry(T* aKey)
+    {
+        PL_HashTableAdd(mOrdering, aKey, new OrderingEntry());
+    }
+
+    // XXX need these helper methods because OrderingEntry doesn't have
+    // XXX access to underlying PLHashEntry
+
+    /**
+     * Add the order |aFirst <_o aSecond|.
+     *
+     * WARNING: this does not check whether it's sane to add this
+     * order.  In the "best" bad case, when this order already exists,
+     * adding it anyway may unnecessarily result in O(n^2) space.  In
+     * the "worst" bad case, adding it anyway will cause
+     * |InTransitiveClosure()| to diverge.
+     */
+    void AddOrder(PLHashEntry* aLT, PLHashEntry* aGT)
+    {
+        static_cast<OrderingEntry*>(aLT->value)->mOrderedLT
+            .InsertElementSorted(aGT);
+    }
+
+    /**
+     * Return true iff the order |aFirst < aSecond| has been
+     * *explicitly* added.
+     *
+     * Does not consider transitivity.
+     */
+    bool IsOrdered(const PLHashEntry* aFirst, const PLHashEntry* aSecond)
+        const
+    {
+        return NoIndex !=
+            static_cast<const OrderingEntry*>(aFirst->value)->mOrderedLT
+                .BinaryIndexOf(aSecond);
+    }
+
+    /**
+     * Return a pointer to the array of all elements "that" for
+     * which the order |this < that| has been explicitly added.
+     *
+     * NOTE: this does *not* consider transitive orderings.
+     */
+    PLHashEntry* const* GetOrders(const PLHashEntry* aEntry) const
+    {
+        return static_cast<const OrderingEntry*>(aEntry->value)->mOrderedLT
+            .Elements();
+    }
+
+    /**
+     * Return the number of elements "that" for which the order
+     * |this < that| has been explicitly added.
+     *
+     * NOTE: this does *not* consider transitive orderings.
+     */
+    size_type NumOrders(const PLHashEntry* aEntry) const
+    {
+        return static_cast<const OrderingEntry*>(aEntry->value)->mOrderedLT
+            .Length();
+    }
+
+    /** Make a ResourceAcquisition out of |aEntry|. */
+    ResourceAcquisition MakeResourceAcquisition(const PLHashEntry* aEntry)
+        const
+    {
+        return ResourceAcquisition(
+            static_cast<const T*>(aEntry->key),
+            static_cast<const OrderingEntry*>(aEntry->value)->mFirstSeen);
+    }
+
+    // Throwaway RAII lock to make the following code safer.
+    struct PRAutoLock
+    {
+        PRAutoLock(PRLock* aLock) : mLock(aLock) { PR_Lock(mLock); }
+        ~PRAutoLock() { PR_Unlock(mLock); }
+        PRLock* mLock;
+    };
+
+public:
+    static const PRUint32 kDefaultNumBuckets;
+
+    /**
+     * DeadlockDetector
+     * Create a new deadlock detector.
+     *
+     * @param aNumResourcesGuess Guess at approximate number of resources
+     *        that will be checked.
+     */
+    DeadlockDetector(PRUint32 aNumResourcesGuess = kDefaultNumBuckets)
+    {
+        mOrdering = PL_NewHashTable(aNumResourcesGuess,
+                                    HashKey,
+                                    PL_CompareValues, PL_CompareValues,
+                                    &kAllocOps, 0);
+        if (!mOrdering)
+            NS_RUNTIMEABORT("couldn't initialize resource ordering table");
+
+        mLock = PR_NewLock();
+        if (!mLock)
+            NS_RUNTIMEABORT("couldn't allocate deadlock detector lock");
+    }
+
+    /**
+     * 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(T* aResource)
+    {
+        PRAutoLock _(mLock);
+        PutEntry(aResource);
+    }
+
+    // Nb: implementing a Remove() method makes the detector "more
+    // unsound."  By removing a resource from the orderings, deadlocks
+    // may be missed that would otherwise have been found.  However,
+    // removing resources possibly reduces the # of false positives,
+    // and additionally saves space.  So it's a trade off; we have
+    // chosen to err on the side of caution and not implement Remove().
+
+    /**
+     * CheckAcquisition This method is called after acquiring |aLast|,
+     * but before trying to acquire |aProposed| from |aCallContext|.
+     * It determines whether actually trying to acquire |aProposed|
+     * will create problems.  It is OK if |aLast| is NULL; 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.
+     * @param aCallContext Calling context whence acquisiton request came.
+     */
+    ResourceAcquisitionArray* CheckAcquisition(const T* aLast,
+                                               const T* aProposed,
+                                               const CallStack& aCallContext)
+    {
+        NS_ASSERTION(aProposed, "null resource");
+        PRAutoLock _(mLock);
+
+        PLHashEntry* second = *GetEntry(aProposed);
+        OrderingEntry* e = static_cast<OrderingEntry*>(second->value);
+        if (CallStack::kNone == e->mFirstSeen)
+            e->mFirstSeen = aCallContext;
+
+        if (!aLast)
+            // don't check if |0 < proposed|; just vamoose
+            return 0;
+
+        PLHashEntry* first = *GetEntry(aLast);
+
+        // this is the crux of the deadlock detector algorithm
+
+        if (first == second) {
+            // reflexive deadlock.  fastpath b/c InTransitiveClosure is
+            // not applicable here.
+            ResourceAcquisitionArray* cycle = new ResourceAcquisitionArray();
+            if (!cycle)
+                NS_RUNTIMEABORT("can't allocate dep. cycle array");
+            cycle->AppendElement(MakeResourceAcquisition(first));
+            cycle->AppendElement(ResourceAcquisition(aProposed,
+                                                     aCallContext));
+            return cycle;
+        }
+        if (InTransitiveClosure(first, second)) {
+            // we've already established |last < proposed|.  all is well.
+            return 0;
+        }
+        if (InTransitiveClosure(second, first)) {
+            // the order |proposed < last| has been deduced, perhaps
+            // transitively.  we're attempting to violate that
+            // constraint by acquiring resources in the order
+            // |last < proposed|, and thus we may deadlock under the
+            // right conditions.
+            ResourceAcquisitionArray* cycle = GetDeductionChain(second, first);
+            // show how acquiring |proposed| would complete the cycle
+            cycle->AppendElement(ResourceAcquisition(aProposed,
+                                                     aCallContext));
+            return cycle;
+        }
+        // |last|, |proposed| are unordered according to our
+        // poset.  this is fine, but we now need to add this
+        // ordering constraint.
+        AddOrder(first, second);
+        return 0;
+    }
+
+    /**
+     * Return true iff |aTarget| is in the transitive closure of |aStart|
+     * over the ordering relation `<_this'.
+     *
+     * @precondition |aStart != aTarget|
+     */
+    bool InTransitiveClosure(const PLHashEntry* aStart,
+                             const PLHashEntry* aTarget) const
+    {
+        if (IsOrdered(aStart, aTarget))
+            return true;
+
+        index_type i = 0;
+        size_type len = NumOrders(aStart);
+        for (const PLHashEntry* const* it = GetOrders(aStart);
+             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 PLHashEntry* aStart,
+        const PLHashEntry* aTarget)
+    {
+        ResourceAcquisitionArray* chain = new ResourceAcquisitionArray();
+        if (!chain)
+            NS_RUNTIMEABORT("can't allocate dep. cycle array");
+        chain->AppendElement(MakeResourceAcquisition(aStart));
+
+        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 PLHashEntry* aStart,
+                                  const PLHashEntry* aTarget,
+                                  ResourceAcquisitionArray* aChain)
+    {
+        if (IsOrdered(aStart, aTarget)) {
+            aChain->AppendElement(MakeResourceAcquisition(aTarget));
+            return true;
+        }
+
+        index_type i = 0;
+        size_type len = NumOrders(aStart);
+        for (const PLHashEntry* const* it = GetOrders(aStart);
+             i < len; ++i, ++it) {
+            aChain->AppendElement(MakeResourceAcquisition(*it));
+            if (GetDeductionChain_Helper(*it, aTarget, aChain))
+                return true;
+            aChain->RemoveElementAt(aChain->Length() - 1);
+        }
+        return false;
+    }
+
+    /**
+     * The partial order on resource acquisitions used by the deadlock
+     * detector.
+     */
+    PLHashTable* mOrdering;     // T* -> PLHashEntry<OrderingEntry>
+
+    /**
+     * Protects contentious methods.
+     * Nb: can't use mozilla::Mutex since we are used as its deadlock
+     * detector.
+     */
+    PRLock* mLock;
+
+    DeadlockDetector(const DeadlockDetector& aDD);
+    DeadlockDetector& operator=(const DeadlockDetector& aDD);
+};
+
+
+template<typename T>
+const PLHashAllocOps DeadlockDetector<T>::kAllocOps = {
+    DeadlockDetector<T>::TableAlloc, DeadlockDetector<T>::TableFree,
+    DeadlockDetector<T>::EntryAlloc, DeadlockDetector<T>::EntryFree
+};
+
+
+template<typename T>
+// FIXME bug 456272: tune based on average workload
+const PRUint32 DeadlockDetector<T>::kDefaultNumBuckets = 64;
+
+
+} // namespace mozilla
+
+#endif // ifndef mozilla_DeadlockDetector_h
--- a/xpcom/glue/Makefile.in
+++ b/xpcom/glue/Makefile.in
@@ -128,17 +128,17 @@ EXPORTS = \
 		$(NULL)
 
 SDK_LIBRARY     =                        \
 		$(LIB_PREFIX)xpcomglue_s.$(LIB_SUFFIX) \
 		$(NULL)
 
 
 ## TODO temp hack until build system handles this
-export:: BlockingResourceBase.h CondVar.h Monitor.h Mutex.h
+export:: BlockingResourceBase.h CondVar.h DeadlockDetector.h Monitor.h Mutex.h
 	$(INSTALL) $^ $(DIST)/include/mozilla
 
 
 # we don't want the shared lib, but we want to force the creation of a static lib.
 FORCE_STATIC_LIB = 1
 
 # Force use of PIC
 FORCE_USE_PIC	= 1
--- a/xpcom/glue/Monitor.h
+++ b/xpcom/glue/Monitor.h
@@ -62,113 +62,125 @@ namespace mozilla {
  * When possible, use MonitorAutoEnter to hold this monitor within a
  * scope, instead of calling Enter/Exit directly.
  **/
 class NS_COM_GLUE Monitor : BlockingResourceBase
 {
 public:
     /**
      * Monitor
-     * @param name A name which can reference this monitor
+     * @param aName A name which can reference this monitor
      * @returns If failure, nsnull
      *          If success, a valid Monitor*, which must be destroyed
      *          by Monitor::DestroyMonitor()
      **/
-    Monitor(const char* name)
+    Monitor(const char* aName) :
+        BlockingResourceBase(aName, eMonitor)
 #ifdef DEBUG
-        : mEntryCount(0)
+        , mEntryCount(0)
 #endif
     {
         mMonitor = PR_NewMonitor();
         if (!mMonitor)
             NS_RUNTIMEABORT("Can't allocate mozilla::Monitor");
-        Init(mMonitor, name, eMonitor);
     }
 
     /**
      * ~Monitor
      **/
-    ~Monitor() {
+    ~Monitor()
+    {
         NS_ASSERTION(mMonitor,
                      "improperly constructed Monitor or double free");
         PR_DestroyMonitor(mMonitor);
         mMonitor = 0;
     }
 
 #ifndef DEBUG
     /** 
      * Enter
      * @see prmon.h 
      **/
-    void Enter() {
-        // NSPR does consistency checks for us
+    void Enter()
+    {
         PR_EnterMonitor(mMonitor);
     }
 
     /** 
      * Exit
      * @see prmon.h 
      **/
-    void Exit() {
+    void Exit()
+    {
         PR_ExitMonitor(mMonitor);
     }
 
+    /**
+     * Wait
+     * @see prmon.h
+     **/      
+    nsresult Wait(PRIntervalTime interval = PR_INTERVAL_NO_TIMEOUT)
+    {
+        return PR_Wait(mMonitor, interval) == PR_SUCCESS ?
+            NS_OK : NS_ERROR_FAILURE;
+    }
+
 #else
     void Enter();
     void Exit();
+    nsresult Wait(PRIntervalTime interval = PR_INTERVAL_NO_TIMEOUT);
 
 #endif  // ifndef DEBUG
 
     /** 
-     * Wait
-     * @see prmon.h 
-     **/      
-    nsresult Wait(PRIntervalTime interval = PR_INTERVAL_NO_TIMEOUT) {
-        return PR_Wait(mMonitor, interval) == PR_SUCCESS
-            ? NS_OK : NS_ERROR_FAILURE;
-    }
-
-    /** 
      * Notify
      * @see prmon.h 
      **/      
-    nsresult Notify() {
+    nsresult Notify()
+    {
         return PR_Notify(mMonitor) == PR_SUCCESS
             ? NS_OK : NS_ERROR_FAILURE;
     }
 
     /** 
      * NotifyAll
      * @see prmon.h 
      **/      
-    nsresult NotifyAll() {
+    nsresult NotifyAll()
+    {
         return PR_NotifyAll(mMonitor) == PR_SUCCESS
             ? NS_OK : NS_ERROR_FAILURE;
     }
 
 #ifdef DEBUG
     /**
      * AssertCurrentThreadIn
      * @see prmon.h
      **/
-    void AssertCurrentThreadIn () {
+    void AssertCurrentThreadIn()
+    {
         PR_ASSERT_CURRENT_THREAD_IN_MONITOR(mMonitor);
     }
 
     /**
      * AssertNotCurrentThreadIn
      * @see prmon.h
      **/
-    void AssertNotCurrentThreadIn () {
-        // TODO
+    void AssertNotCurrentThreadIn()
+    {
+        // FIXME bug 476536
     }
 
 #else
-    void AssertCurrentThreadIn () { }
-    void AssertNotCurrentThreadIn () { }
+    void AssertCurrentThreadIn()
+    {
+    }
+    void AssertNotCurrentThreadIn()
+    {
+    }
 
 #endif  // ifdef DEBUG
 
 private:
     Monitor();
     Monitor(const Monitor&);
     Monitor& operator =(const Monitor&);
 
@@ -192,35 +204,40 @@ public:
     /**
      * Constructor
      * The constructor aquires the given lock.  The destructor
      * releases the lock.
      * 
      * @param aMonitor A valid mozilla::Monitor* returned by 
      *                 mozilla::Monitor::NewMonitor. 
      **/
-    MonitorAutoEnter(mozilla::Monitor &aMonitor)
-        : mMonitor(&aMonitor) {
+    MonitorAutoEnter(mozilla::Monitor &aMonitor) :
+        mMonitor(&aMonitor)
+    {
         NS_ASSERTION(mMonitor, "null monitor");
         mMonitor->Enter();
     }
     
-    ~MonitorAutoEnter(void) {
+    ~MonitorAutoEnter(void)
+    {
         mMonitor->Exit();
     }
  
-    nsresult Wait(PRIntervalTime interval = PR_INTERVAL_NO_TIMEOUT) {
+    nsresult Wait(PRIntervalTime interval = PR_INTERVAL_NO_TIMEOUT)
+    {
        return mMonitor->Wait(interval);
     }
 
-    nsresult Notify() {
+    nsresult Notify()
+    {
         return mMonitor->Notify();
     }
 
-    nsresult NotifyAll() {
+    nsresult NotifyAll()
+    {
         return mMonitor->Notify();
     }
 
 private:
     MonitorAutoEnter();
     MonitorAutoEnter(const MonitorAutoEnter&);
     MonitorAutoEnter& operator =(const MonitorAutoEnter&);
     static void* operator new(size_t) CPP_THROW_NEW;
--- a/xpcom/glue/Mutex.h
+++ b/xpcom/glue/Mutex.h
@@ -68,73 +68,83 @@ class NS_COM_GLUE Mutex : BlockingResour
 public:
     /**
      * Mutex
      * @param name A name which can reference this lock
      * @returns If failure, nsnull
      *          If success, a valid Mutex* which must be destroyed
      *          by Mutex::DestroyMutex()
      **/
-    Mutex(const char* name) {
+    Mutex(const char* name) :
+        BlockingResourceBase(name, eMutex)
+    {
         mLock = PR_NewLock();
         if (!mLock)
             NS_RUNTIMEABORT("Can't allocate mozilla::Mutex");
-        Init(mLock, name, eMutex);
     }
 
     /**
      * ~Mutex
      **/
-    ~Mutex() {
+    ~Mutex()
+    {
         NS_ASSERTION(mLock,
                      "improperly constructed Lock or double free");
         // NSPR does consistency checks for us
         PR_DestroyLock(mLock);
         mLock = 0;
     }
 
 #ifndef DEBUG
     /**
      * Lock
      * @see prlock.h
      **/
-    void Lock() {
+    void Lock()
+    {
         PR_Lock(mLock);
     }
 
     /**
      * Unlock
      * @see prlock.h
      **/
-    void Unlock() {
+    void Unlock()
+    {
         PR_Unlock(mLock);
     }
 
     /**
      * AssertCurrentThreadOwns
      * @see prlock.h
      **/
-    void AssertCurrentThreadOwns () { }
+    void AssertCurrentThreadOwns ()
+    {
+    }
 
     /**
      * AssertNotCurrentThreadOwns
      * @see prlock.h
      **/
-    void AssertNotCurrentThreadOwns () { }
+    void AssertNotCurrentThreadOwns ()
+    {
+    }
 
 #else
     void Lock();
     void Unlock();
 
-    void AssertCurrentThreadOwns () {
+    void AssertCurrentThreadOwns ()
+    {
         PR_ASSERT_CURRENT_THREAD_OWNS_LOCK(mLock);
     }
 
-    void AssertNotCurrentThreadOwns () {
-        // TODO
+    void AssertNotCurrentThreadOwns ()
+    {
+        // FIXME bug 476536
     }
 
 #endif  // ifndef DEBUG
 
 private:
     Mutex();
     Mutex(const Mutex&);
     Mutex& operator=(const Mutex&);
@@ -158,18 +168,19 @@ public:
     /**
      * Constructor
      * The constructor aquires the given lock.  The destructor
      * releases the lock.
      * 
      * @param aLock A valid mozilla::Mutex* returned by 
      *              mozilla::Mutex::NewMutex. 
      **/
-    MutexAutoLock(mozilla::Mutex& aLock)
-        : mLock(&aLock) {
+    MutexAutoLock(mozilla::Mutex& aLock) :
+        mLock(&aLock)
+    {
         NS_ASSERTION(mLock, "null mutex");
         mLock->Lock();
     }
     
     ~MutexAutoLock(void) {
         mLock->Unlock();
     }
  
@@ -189,18 +200,19 @@ private:
  * Releases the Mutex when it enters scope, and re-acquires it when it leaves 
  * scope.
  *
  * MUCH PREFERRED to bare calls to Mutex.Unlock and Lock.
  */ 
 class NS_COM_GLUE NS_STACK_CLASS MutexAutoUnlock 
 {
 public:
-    MutexAutoUnlock(mozilla::Mutex& aLock) 
-        : mLock(&aLock) {
+    MutexAutoUnlock(mozilla::Mutex& aLock) :
+        mLock(&aLock)
+    {
         NS_ASSERTION(mLock, "null lock");
         mLock->Unlock();
     }
 
     ~MutexAutoUnlock() 
     {
         mLock->Lock();
     }
--- a/xpcom/glue/nsTArray.h
+++ b/xpcom/glue/nsTArray.h
@@ -536,16 +536,80 @@ class nsTArray : public nsTArray_base {
       if (!EnsureCapacity(Length() + 1, sizeof(elem_type)))
          return nsnull;
       ShiftData(index, 0, 1, sizeof(elem_type));
       elem_type *elem = Elements() + index;
       elem_traits::Construct(elem);
       return elem;
     }
 
+    // This method searches for the least index of the greatest
+    // element less than or equal to |item|.  If |item| is inserted at
+    // this index, the array will remain sorted.  True is returned iff
+    // this index is also equal to |item|.  In this case, the returned
+    // index may point to the start of multiple copies of |item|.
+    // @param item   The item to search for.
+    // @param comp   The Comparator used.
+    // @outparam idx The index of greatest element <= to |item|
+    // @return       True iff |item == array[*idx]|.
+    // @precondition The array is sorted
+    template<class Item, class Comparator>
+    PRBool
+    GreatestIndexLtEq(const Item& item,
+                      const Comparator& comp,
+                      index_type* idx NS_OUTPARAM) const {
+      // Nb: we could replace all the uses of "BinaryIndexOf" with this
+      // function, but BinaryIndexOf will be oh-so-slightly faster so
+      // it's not strictly desired to do.
+
+      // invariant: low <= [idx] < high
+      index_type low = 0, high = Length();
+      while (high > low) {
+        index_type mid = (high + low) >> 1;
+        if (comp.Equals(ElementAt(mid), item)) {
+          // we might have the array [..., 2, 4, 4, 4, 4, 4, 5, ...]
+          // and be searching for "4". it's arbitrary where mid ends
+          // up here, so we back it up to the first instance to maintain
+          // the "least index ..." we promised above.
+          do {
+            --mid;
+          } while (NoIndex != mid && comp.Equals(ElementAt(mid), item));
+          *idx = ++mid;
+          return PR_TRUE;
+        }
+        if (comp.LessThan(ElementAt(mid), item))
+          // invariant: low <= idx < high
+          low = mid + 1;
+        else
+          // invariant: low <= idx < high
+          high = mid;
+      }
+      // low <= idx < high, so insert at high ("shifting" high up by
+      // 1) to maintain invariant.
+      // (or insert at low, since low==high; just a matter of taste here.)
+      *idx = high;
+      return PR_FALSE;
+    }
+
+    // Inserts |item| at such an index to guarantee that if the array
+    // was previously sorted, it will remain sorted after this
+    // insertion.
+    template<class Item, class Comparator>
+    elem_type *InsertElementSorted(const Item& item, const Comparator& comp) {
+      index_type index;
+      GreatestIndexLtEq(item, comp, &index);
+      return InsertElementAt(index, item);
+    }
+
+    // A variation on the InsertElementSorted metod defined above.
+    template<class Item>
+    elem_type *InsertElementSorted(const Item& item) {
+      return InsertElementSorted(item, nsDefaultComparator<elem_type, Item>());
+    }
+
     // This method appends elements to the end of this array.
     // @param array     The elements to append to this array.
     // @param arrayLen  The number of elements to append to this array.
     // @return          A pointer to the new elements in the array, or null if
     //                  the operation failed due to insufficient memory.
     template<class Item>
     elem_type *AppendElements(const Item* array, size_type arrayLen) {
       if (!EnsureCapacity(Length() + arrayLen, sizeof(elem_type)))
@@ -627,16 +691,37 @@ class nsTArray : public nsTArray_base {
 
     // A variation on the RemoveElement method defined above that assumes
     // that 'operator==' is defined for elem_type.
     template<class Item>
     PRBool RemoveElement(const Item& item) {
       return RemoveElement(item, nsDefaultComparator<elem_type, Item>());
     }
 
+    // This helper function combines GreatestIndexLtEq with
+    // RemoveElementAt to "search and destroy" the first element that
+    // is equal to the given element.
+    // @param item  The item to search for.
+    // @param comp  The Comparator used to determine element equality.
+    // @return PR_TRUE if the element was found
+    template<class Item, class Comparator>
+    PRBool RemoveElementSorted(const Item& item, const Comparator& comp) {
+      index_type index;
+      PRBool found = GreatestIndexLtEq(item, comp, &index);
+      if (found)
+        RemoveElementAt(index);
+      return found;
+    }
+
+    // A variation on the RemoveElementSorted method defined above.
+    template<class Item>
+    PRBool RemoveElementSorted(const Item& item) {
+      return RemoveElementSorted(item, nsDefaultComparator<elem_type, Item>());
+    }
+
     // This method causes the elements contained in this array and the given
     // array to be swapped.
     // NOTE: This method isn't heavily optimized if either array is an
     // nsAutoTArray.
     PRBool SwapElements(self_type& other) {
       return SwapArrayElements(other, sizeof(elem_type));
     }
 
--- a/xpcom/glue/objs.mk
+++ b/xpcom/glue/objs.mk
@@ -72,15 +72,16 @@ XPCOM_GLUE_SRC_CPPSRCS = $(addprefix $(t
 # nsGenericFactory is not really all that helpful in the standalone glue,
 # and it has a bad dependency on the NSPR AtomicIncrement function, so we
 # only build it for the dependent XPCOM glue and builtin to xpcom-core.
 
 # TODO nsAutoLock.cpp should die soon
 
 XPCOM_GLUENS_SRC_LCPPSRCS =      \
   BlockingResourceBase.cpp       \
+  DeadlockDetector.cpp           \
   nsAutoLock.cpp                 \
   nsGenericFactory.cpp           \
   nsProxyRelease.cpp             \
   nsTextFormatter.cpp            \
   $(NULL)
 
 XPCOM_GLUENS_SRC_CPPSRCS = $(addprefix $(topsrcdir)/xpcom/glue/,$(XPCOM_GLUENS_SRC_LCPPSRCS))
--- a/xpcom/tests/Makefile.in
+++ b/xpcom/tests/Makefile.in
@@ -98,32 +98,45 @@ CPP_UNIT_TESTS = \
                  TestTextFormatter.cpp \
                  $(NULL)
 
 ifndef MOZ_ENABLE_LIBXUL
 CPP_UNIT_TESTS += \
                   TestArray.cpp \
                   TestAutoLock.cpp \
                   TestCRT.cpp \
+                  TestDeque.cpp \
                   TestEncoding.cpp \
                   TestExpirationTracker.cpp \
                   TestPipes.cpp \
                   TestProxies.cpp \
-                  TestThreads.cpp \
-                  TestThreadPool.cpp \
-                  TestXPIDLString.cpp \
-                  TestDeque.cpp \
+                  TestStorageStream.cpp \
                   TestStrings.cpp \
-                  TestStorageStream.cpp \
                   TestSynchronization.cpp \
                   TestTArray.cpp \
+                  TestThreadPool.cpp \
+                  TestThreads.cpp \
                   TestTimeStamp.cpp \
+                  TestXPIDLString.cpp \
                   $(NULL)
 endif
 
+ifdef MOZ_DEBUG
+# FIXME bug 456272: testing assertion failures is fragile,
+# and TestDeadlockDetector doesn't like Windows
+ifneq ($(OS_ARCH), WINNT)
+ifneq ($(OS_ARCH), WINCE)
+CPP_UNIT_TESTS += \
+                  TestDeadlockDetector.cpp \
+                  TestDeadlockDetectorScalability.cpp \
+                  $(NULL)
+endif
+endif
+endif
+
 ifndef MOZILLA_INTERNAL_API
 CPP_UNIT_TESTS += \
                   TestStringAPI.cpp \
                   $(NULL)
 endif
 
 include $(topsrcdir)/config/config.mk
 
new file mode 100644
--- /dev/null
+++ b/xpcom/tests/TestDeadlockDetector.cpp
@@ -0,0 +1,589 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: sw=4 ts=4 et :
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is mozilla.org code.
+ *
+ * The Initial Developer of the Original Code is
+ * Netscape Communications Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 1998
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Chris Jones <jones.chris.g@gmail.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#include "prenv.h"
+#include "prerror.h"
+#include "prio.h"
+#include "prproces.h"
+
+#include "TestHarness.h"
+
+#include "mozilla/CondVar.h"
+#include "mozilla/Monitor.h"
+#include "mozilla/Mutex.h"
+
+using namespace mozilla;
+
+static PRThread*
+spawn(void (*run)(void*), void* arg)
+{
+    return PR_CreateThread(PR_SYSTEM_THREAD,
+                           run,
+                           arg,
+                           PR_PRIORITY_NORMAL,
+                           PR_GLOBAL_THREAD,
+                           PR_JOINABLE_THREAD,
+                           0);
+}
+
+#define PASS()                                  \
+    do {                                        \
+        passed(__FUNCTION__);                   \
+        return NS_OK;                           \
+    } while (0);
+
+
+#define FAIL(why)                               \
+    do {                                        \
+        fail(why);                              \
+        return NS_ERROR_FAILURE;                \
+    } while (0);
+
+#define ALEN(arr) (sizeof(arr) / sizeof(arr[0]))
+
+//-----------------------------------------------------------------------------
+
+static const char* sPathToThisBinary;
+static const char* sAssertBehaviorEnv = "XPCOM_DEBUG_BREAK=abort";
+
+class Subprocess
+{
+public:
+    // not available until process finishes
+    PRInt32 mExitCode;
+    nsCString mStdout;
+    nsCString mStderr;
+
+    Subprocess(const char* aTestName) {
+        // set up stdio redirection
+        PRFileDesc* readStdin;  PRFileDesc* writeStdin;
+        PRFileDesc* readStdout; PRFileDesc* writeStdout;
+        PRFileDesc* readStderr; PRFileDesc* writeStderr;
+        PRProcessAttr* pattr = PR_NewProcessAttr();
+
+        NS_ASSERTION(pattr, "couldn't allocate process attrs");
+
+        NS_ASSERTION(PR_SUCCESS == PR_CreatePipe(&readStdin, &writeStdin),
+                     "couldn't create child stdin pipe");
+        NS_ASSERTION(PR_SUCCESS == PR_SetFDInheritable(readStdin, PR_TRUE),
+                     "couldn't set child stdin inheritable");
+        PR_ProcessAttrSetStdioRedirect(pattr, PR_StandardInput, readStdin);
+
+        NS_ASSERTION(PR_SUCCESS == PR_CreatePipe(&readStdout, &writeStdout),
+                     "couldn't create child stdout pipe");
+        NS_ASSERTION(PR_SUCCESS == PR_SetFDInheritable(writeStdout, PR_TRUE),
+                     "couldn't set child stdout inheritable");
+        PR_ProcessAttrSetStdioRedirect(pattr, PR_StandardOutput, writeStdout);
+
+        NS_ASSERTION(PR_SUCCESS == PR_CreatePipe(&readStderr, &writeStderr),
+                     "couldn't create child stderr pipe");
+        NS_ASSERTION(PR_SUCCESS == PR_SetFDInheritable(writeStderr, PR_TRUE),
+                     "couldn't set child stderr inheritable");
+        PR_ProcessAttrSetStdioRedirect(pattr, PR_StandardError, writeStderr);
+
+        // set up argv with test name to run
+        char* const newArgv[3] = {
+            strdup(sPathToThisBinary),
+            strdup(aTestName),
+            0
+        };
+
+        // make sure the child will abort if an assertion fails
+        NS_ASSERTION(PR_SUCCESS == PR_SetEnv(sAssertBehaviorEnv),
+                     "couldn't set XPCOM_DEBUG_BREAK env var");
+
+        PRProcess* proc;
+        NS_ASSERTION(proc = PR_CreateProcess(sPathToThisBinary,
+                                             newArgv,
+                                             0, // inherit environment
+                                             pattr),
+                     "couldn't create process");
+        PR_Close(readStdin);
+        PR_Close(writeStdout);
+        PR_Close(writeStderr);
+
+        mProc = proc;
+        mStdinfd = writeStdin;
+        mStdoutfd = readStdout;
+        mStderrfd = readStderr;
+
+        free(newArgv[0]);
+        free(newArgv[1]);
+        PR_DestroyProcessAttr(pattr);
+    }
+
+    void RunToCompletion(PRUint32 aWaitMs)
+    {
+        PR_Close(mStdinfd);
+
+        PRPollDesc pollfds[2];
+        PRInt32 nfds;
+        PRBool stdoutOpen = PR_TRUE, stderrOpen = PR_TRUE;
+        char buf[4096];
+        PRInt32 len;
+
+        PRIntervalTime now = PR_IntervalNow();
+        PRIntervalTime deadline = now + PR_MillisecondsToInterval(aWaitMs);
+
+        while ((stdoutOpen || stderrOpen) && now < deadline) {
+            nfds = 0;
+            if (stdoutOpen) {
+                pollfds[nfds].fd = mStdoutfd;
+                pollfds[nfds].in_flags = PR_POLL_READ;
+                pollfds[nfds].out_flags = 0;
+                ++nfds;
+            }
+            if (stderrOpen) {
+                pollfds[nfds].fd = mStderrfd;
+                pollfds[nfds].in_flags = PR_POLL_READ;
+                pollfds[nfds].out_flags = 0;
+                ++nfds;
+            }
+
+            PRInt32 rv = PR_Poll(pollfds, nfds, deadline - now);
+            NS_ASSERTION(0 <= rv, PR_ErrorToName(PR_GetError()));
+
+            if (0 == rv) {      // timeout
+                Finish(PR_FALSE); // abnormal
+                return;
+            }
+
+            for (PRInt32 i = 0; i < nfds; ++i) {
+                if (!pollfds[i].out_flags)
+                    continue;
+
+                PRBool isStdout = mStdoutfd == pollfds[i].fd;
+                
+                if (PR_POLL_READ & pollfds[i].out_flags) {
+                    len = PR_Read(pollfds[i].fd, buf, sizeof(buf) - 1);
+                    NS_ASSERTION(0 <= len, PR_ErrorToName(PR_GetError()));
+                }
+                else if (PR_POLL_HUP & pollfds[i].out_flags) {
+                    len = 0;
+                }
+                else {
+                    NS_ERROR(PR_ErrorToName(PR_GetError()));
+                }
+
+                if (0 < len) {
+                    buf[len] = '\0';
+                    if (isStdout)
+                        mStdout += buf;
+                    else
+                        mStderr += buf;
+                }
+                else {
+                    if (isStdout) {
+                        stdoutOpen = PR_FALSE;
+                        PR_Close(mStdoutfd);
+                    }
+                    else {
+                        stderrOpen = PR_FALSE;
+                        PR_Close(mStderrfd);
+                    }
+                }
+            }
+
+            now = PR_IntervalNow();
+        }
+
+        Finish(!stdoutOpen && !stderrOpen && now <= deadline);
+    }
+
+private:
+    void Finish(PRBool normalExit) {
+        if (!normalExit) {
+            PR_KillProcess(mProc);
+            PR_Close(mStdoutfd);
+            PR_Close(mStderrfd);
+            mExitCode = -1;
+            PRInt32 dummy;
+            PR_WaitProcess(mProc, &dummy);
+        }
+        else {
+            PR_WaitProcess(mProc, &mExitCode); // this had better not block ...
+        }
+    }
+
+    PRProcess* mProc;
+    PRFileDesc* mStdinfd;         // writeable
+    PRFileDesc* mStdoutfd;        // readable
+    PRFileDesc* mStderrfd;        // readable
+};
+
+//-----------------------------------------------------------------------------
+// Harness for checking detector errors
+bool
+CheckForDeadlock(const char* test, const char* const* findTokens)
+{
+    Subprocess proc(test);
+    proc.RunToCompletion(1000);
+
+    if (0 == proc.mExitCode)
+        return false;
+
+    PRInt32 idx = 0;
+    for (const char* const* tp = findTokens; *tp; ++tp) {
+        const char* const token = *tp;
+        idx = proc.mStderr.Find(token, PR_FALSE, idx);
+        if (kNotFound == idx) {
+            printf("(missed token '%s' in output)\n", token);
+            puts("----------------------------------\n");
+            puts(proc.mStderr.get());
+            puts("----------------------------------\n");
+            return false;
+        }
+        idx += strlen(token);
+    }
+
+    return true;
+}
+
+//-----------------------------------------------------------------------------
+// Single-threaded sanity tests
+
+// Stupidest possible deadlock.
+nsresult
+Sanity_Child()
+{
+    mozilla::Mutex m1("dd.sanity.m1");
+    m1.Lock();
+    m1.Lock();
+    return 0;                  // not reached
+}
+
+nsresult
+Sanity()
+{
+    const char* const tokens[] = {
+        "###!!! ERROR: Potential deadlock detected",
+        "=== Cyclical dependency starts at\n--- Mutex : dd.sanity.m1",
+        "=== Cycle completed at\n--- Mutex : dd.sanity.m1",
+        "###!!! Deadlock may happen NOW!", // better catch these easy cases...
+        "###!!! ASSERTION: Potential deadlock detected",
+        0
+    };
+    if (CheckForDeadlock("Sanity", tokens)) {
+        PASS();
+    } else {
+        FAIL("deadlock not detected");
+    }
+}
+
+// Slightly less stupid deadlock.
+nsresult
+Sanity2_Child()
+{
+    mozilla::Mutex m1("dd.sanity2.m1");
+    mozilla::Mutex m2("dd.sanity2.m2");
+    m1.Lock();
+    m2.Lock();
+    m1.Lock();
+    return 0;                  // not reached
+}
+
+nsresult
+Sanity2()
+{
+    const char* const tokens[] = {
+        "###!!! ERROR: Potential deadlock detected",
+        "=== Cyclical dependency starts at\n--- Mutex : dd.sanity2.m1",
+        "--- Next dependency:\n--- Mutex : dd.sanity2.m2",
+        "=== Cycle completed at\n--- Mutex : dd.sanity2.m1",
+        "###!!! Deadlock may happen NOW!", // better catch these easy cases...
+        "###!!! ASSERTION: Potential deadlock detected",
+        0
+    };
+    if (CheckForDeadlock("Sanity2", tokens)) {
+        PASS();
+    } else {
+        FAIL("deadlock not detected");
+    }
+}
+
+
+nsresult
+Sanity3_Child()
+{
+    mozilla::Mutex m1("dd.sanity3.m1");
+    mozilla::Mutex m2("dd.sanity3.m2");
+    mozilla::Mutex m3("dd.sanity3.m3");
+    mozilla::Mutex m4("dd.sanity3.m4");
+
+    m1.Lock();
+    m2.Lock();
+    m3.Lock();
+    m4.Lock();
+    m4.Unlock();
+    m3.Unlock();
+    m2.Unlock();
+    m1.Unlock();
+
+    m4.Lock();
+    m1.Lock();
+    return 0;
+}
+
+nsresult
+Sanity3()
+{
+    const char* const tokens[] = {
+        "###!!! ERROR: Potential deadlock detected",
+        "=== Cyclical dependency starts at\n--- Mutex : dd.sanity3.m1",
+        "--- Next dependency:\n--- Mutex : dd.sanity3.m2",
+        "--- Next dependency:\n--- Mutex : dd.sanity3.m3",
+        "--- Next dependency:\n--- Mutex : dd.sanity3.m4",
+        "=== Cycle completed at\n--- Mutex : dd.sanity3.m1",
+        "###!!! ASSERTION: Potential deadlock detected",
+        0
+    };
+    if (CheckForDeadlock("Sanity3", tokens)) {
+        PASS();
+    } else {
+        FAIL("deadlock not detected");
+    }
+}
+
+
+nsresult
+Sanity4_Child()
+{
+    mozilla::Monitor m1("dd.sanity4.m1");
+    mozilla::Mutex m2("dd.sanity4.m2");
+    m1.Enter();
+    m2.Lock();
+    m1.Enter();
+    return 0;
+}
+
+nsresult
+Sanity4()
+{
+    const char* const tokens[] = {
+        "Re-entering Monitor after acquiring other resources",
+        "###!!! ERROR: Potential deadlock detected",
+        "=== Cyclical dependency starts at\n--- Monitor : dd.sanity4.m1",
+        "--- Next dependency:\n--- Mutex : dd.sanity4.m2",
+        "=== Cycle completed at\n--- Monitor : dd.sanity4.m1",
+        "###!!! ASSERTION: Potential deadlock detected",
+        0
+    };
+    if (CheckForDeadlock("Sanity4", tokens)) {
+        PASS();
+    } else {
+        FAIL("deadlock not detected");
+    }
+}
+
+//-----------------------------------------------------------------------------
+// Multithreaded tests
+
+mozilla::Mutex* ttM1;
+mozilla::Mutex* ttM2;
+
+static void
+TwoThreads_thread(void* arg)
+{
+    PRInt32 m1First = NS_PTR_TO_INT32(arg);
+    if (m1First) {
+        ttM1->Lock();
+        ttM2->Lock();
+        ttM2->Unlock();
+        ttM1->Unlock();
+    }
+    else {
+        ttM2->Lock();
+        ttM1->Lock();
+        ttM1->Unlock();
+        ttM2->Unlock();
+    }
+}
+
+nsresult
+TwoThreads_Child()
+{
+    ttM1 = new mozilla::Mutex("dd.twothreads.m1");
+    ttM2 = new mozilla::Mutex("dd.twothreads.m2");
+    if (!ttM1 || !ttM2)
+        NS_RUNTIMEABORT("couldn't allocate mutexes");
+
+    PRThread* t1 = spawn(TwoThreads_thread, (void*) 0);
+    PR_JoinThread(t1);
+
+    PRThread* t2 = spawn(TwoThreads_thread, (void*) 1);
+    PR_JoinThread(t2);
+
+    return 0;
+}
+
+nsresult
+TwoThreads()
+{
+    const char* const tokens[] = {
+        "###!!! ERROR: Potential deadlock detected",
+        "=== Cyclical dependency starts at\n--- Mutex : dd.twothreads.m2",
+        "--- Next dependency:\n--- Mutex : dd.twothreads.m1",
+        "=== Cycle completed at\n--- Mutex : dd.twothreads.m2",
+        "###!!! ASSERTION: Potential deadlock detected",
+        0
+    };
+
+    if (CheckForDeadlock("TwoThreads", tokens)) {
+        PASS();
+    } else {
+        FAIL("deadlock not detected");
+    }
+}
+
+
+mozilla::Mutex* cndMs[4];
+const PRUint32 K = 100000;
+
+static void
+ContentionNoDeadlock_thread(void* arg)
+{
+    PRInt32 starti = NS_PTR_TO_INT32(arg);
+
+    for (PRUint32 k = 0; k < K; ++k) {
+        for (PRInt32 i = starti; i < ALEN(cndMs); ++i)
+            cndMs[i]->Lock();
+        // comment out the next two lines for deadlocking fun!
+        for (PRInt32 i = ALEN(cndMs) - 1; i >= starti; --i)
+            cndMs[i]->Unlock();
+
+        starti = (starti + 1) % 3;
+    }
+}
+
+nsresult
+ContentionNoDeadlock_Child()
+{
+    PRThread* threads[3];
+
+    for (PRUint32 i = 0; i < ALEN(cndMs); ++i)
+        cndMs[i] = new mozilla::Mutex("dd.cnd.ms");
+
+    for (PRInt32 i = 0; i < ALEN(threads); ++i)
+        threads[i] = spawn(ContentionNoDeadlock_thread, NS_INT32_TO_PTR(i));
+
+    for (PRUint32 i = 0; i < ALEN(threads); ++i)
+        PR_JoinThread(threads[i]);
+
+    for (PRUint32 i = 0; i < ALEN(cndMs); ++i)
+        delete cndMs[i];
+
+    return 0;
+}
+
+nsresult
+ContentionNoDeadlock()
+{
+    Subprocess proc(__FUNCTION__);
+    proc.RunToCompletion(10000);
+    if (0 != proc.mExitCode) {
+        printf("(expected 0 == return code, got %d)\n", proc.mExitCode);
+        puts("(output)\n----------------------------------\n");
+        puts(proc.mStdout.get());
+        puts("----------------------------------\n");
+        puts("(error output)\n----------------------------------\n");
+        puts(proc.mStderr.get());
+        puts("----------------------------------\n");
+
+        FAIL("deadlock");
+    }
+    PASS();
+}
+
+
+
+//-----------------------------------------------------------------------------
+
+int
+main(int argc, char** argv)
+{
+    if (1 < argc) {
+        // XXX can we run w/o scoped XPCOM?
+        const char* test = argv[1];
+        ScopedXPCOM xpcom(test);
+        if (xpcom.failed())
+            return 1;
+
+        // running in a spawned process.  call the specificed child function.
+        if (!strcmp("Sanity", test))
+            return Sanity_Child();
+        if (!strcmp("Sanity2", test))
+            return Sanity2_Child();
+        if (!strcmp("Sanity3", test))
+            return Sanity3_Child();
+        if (!strcmp("Sanity4", test))
+            return Sanity4_Child();
+
+        if (!strcmp("TwoThreads", test))
+            return TwoThreads_Child();
+        if (!strcmp("ContentionNoDeadlock", test))
+            return ContentionNoDeadlock_Child();
+
+        FAIL("unknown child test");
+    }
+
+    ScopedXPCOM xpcom("Deadlock detector correctness");
+    if (xpcom.failed())
+        return 1;
+
+    // in the first invocation of this process.  we will be the "driver".
+    int rv = 0;
+
+    sPathToThisBinary = argv[0];
+
+    if (NS_FAILED(Sanity()))
+        rv = 1;
+    if (NS_FAILED(Sanity2()))
+        rv = 1;
+    if (NS_FAILED(Sanity3()))
+        rv = 1;
+    if (NS_FAILED(Sanity4()))
+        rv = 1;
+
+    if (NS_FAILED(TwoThreads()))
+        rv = 1;
+    if (NS_FAILED(ContentionNoDeadlock()))
+        rv = 1;
+
+    return rv;
+}
new file mode 100644
--- /dev/null
+++ b/xpcom/tests/TestDeadlockDetectorScalability.cpp
@@ -0,0 +1,202 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: sw=4 ts=4 et :
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is mozilla.org code.
+ *
+ * The Initial Developer of the Original Code is
+ * Netscape Communications Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 1998
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Chris Jones <jones.chris.g@gmail.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#include "TestHarness.h"
+
+//#define OLD_API
+
+#define PASS()                                  \
+    do {                                        \
+        passed(__FUNCTION__);                   \
+        return NS_OK;                           \
+    } while (0);
+
+
+#define FAIL(why)                               \
+    do {                                        \
+        fail(why);                              \
+        return NS_ERROR_FAILURE;                \
+    } while (0);
+
+#ifdef OLD_API
+#  include "nsAutoLock.h"
+   typedef PRLock* lock_t;
+#  define NEWLOCK(n) nsAutoLock::NewLock(n)
+#  define DELETELOCK(v) nsAutoLock::DestroyLock(v)
+#  define AUTOLOCK(v, l) nsAutoLock v(l)
+#else
+#  include "mozilla/Mutex.h"
+   typedef mozilla::Mutex* lock_t;
+#  define NEWLOCK(n) new mozilla::Mutex(n)
+#  define DELETELOCK(v) delete (v)
+#  define AUTOLOCK(v, l) mozilla::MutexAutoLock v(*l)
+#endif
+
+//-----------------------------------------------------------------------------
+
+static void
+AllocLockRecurseUnlockFree(int i)
+{
+    if (0 == i)
+        return;
+
+    lock_t lock = NEWLOCK("deadlockDetector.scalability.t1");
+    {
+        AUTOLOCK(_, lock);
+        AllocLockRecurseUnlockFree(i - 1);
+    }
+    DELETELOCK(lock);
+}
+
+// This test creates a resource dependency chain N elements long, then
+// frees all the resources in the chain.
+static nsresult
+LengthNDepChain(int N)
+{
+    AllocLockRecurseUnlockFree(N);
+    PASS();
+}
+
+//-----------------------------------------------------------------------------
+
+// This test creates a single lock that is ordered < N resources, then
+// repeatedly exercises this order k times.
+static nsresult
+OneLockNDeps(const int N, const int K)
+{
+    lock_t lock = NEWLOCK("deadlockDetector.scalability.t2.master");
+    lock_t* locks = new lock_t[N];
+    if (!locks)
+        NS_RUNTIMEABORT("couldn't allocate lock array");
+
+    for (int i = 0; i < N; ++i)
+        locks[i] =
+            NEWLOCK("deadlockDetector.scalability.t2.dep");
+
+    // establish orders
+    {AUTOLOCK(m, lock);
+        for (int i = 0; i < N; ++i)
+            AUTOLOCK(s, locks[i]);
+    }
+
+    // exercise order check
+    {AUTOLOCK(m, lock);
+        for (int i = 0; i < K; ++i)
+            for (int j = 0; j < N; ++j)
+                AUTOLOCK(s, locks[i]);
+    }
+
+    for (int i = 0; i < N; ++i)
+        DELETELOCK(locks[i]);
+    delete[] locks;
+
+    PASS();
+}
+
+
+//-----------------------------------------------------------------------------
+
+// This test creates N resources and adds the theoretical maximum number
+// of dependencies, O(N^2).  It then repeats that sequence of
+// acquisitions k times.  Finally, all resources are freed.
+//
+// It's very difficult to perform well on this test.  It's put forth as a
+// challenge problem.
+
+static nsresult
+MaxDepsNsq(const int N, const int K)
+{
+    lock_t* locks = new lock_t[N];
+    if (!locks)
+        NS_RUNTIMEABORT("couldn't allocate lock array");
+
+    for (int i = 0; i < N; ++i)
+        locks[i] = NEWLOCK("deadlockDetector.scalability.t3");
+
+    for (int i = 0; i < N; ++i) {
+        AUTOLOCK(al1, locks[i]);
+        for (int j = i+1; j < N; ++j)
+            AUTOLOCK(al2, locks[j]);
+    }
+
+    for (int i = 0; i < K; ++i) {
+        for (int j = 0; j < N; ++j) {
+            AUTOLOCK(al1, locks[j]);
+            for (int k = j+1; k < N; ++k)
+                AUTOLOCK(al2, locks[k]);
+        }
+    }
+
+    for (int i = 0; i < N; ++i)
+        DELETELOCK(locks[i]);
+    delete[] locks;
+
+    PASS();
+}
+
+//-----------------------------------------------------------------------------
+
+int
+main(int argc, char** argv)
+{
+    ScopedXPCOM xpcom("Deadlock detector scalability");
+    if (xpcom.failed())
+        return 1;
+
+    int rv = 0;
+
+    // Uncomment these tests to run them.  Not expected to be common.
+
+#if 0
+    if (NS_FAILED(LengthNDepChain(1 << 14))) // 16K
+        rv = 1;
+#endif
+
+#if 0
+    if (NS_FAILED(OneLockNDeps(1 << 14, 100))) // 16k
+        rv = 1;
+#endif
+
+#if 0
+    if (NS_FAILED(MaxDepsNsq(1 << 10, 10))) // 1k
+        rv = 1;
+#endif
+
+    return rv;
+}
--- a/xpcom/tests/TestSynchronization.cpp
+++ b/xpcom/tests/TestSynchronization.cpp
@@ -1,8 +1,47 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: sw=4 ts=4 et :
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is mozilla.org code.
+ *
+ * The Initial Developer of the Original Code is
+ * Netscape Communications Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 1998
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Chris Jones <jones.chris.g@gmail.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
 #include "TestHarness.h"
 
 #include "mozilla/CondVar.h"
 #include "mozilla/Monitor.h"
 #include "mozilla/Mutex.h"
 #include "nsAutoLock.h"
 
 using namespace mozilla;