Make cycle collector's purple buffer consist of entries that the objects in the purple buffer can point to, and remove the notion of scan delay (which was previously set to 0). (Bug 490695) r+sr=peterv r=bsmedberg
authorL. David Baron <dbaron@dbaron.org>
Wed, 06 May 2009 13:46:04 -0700
changeset 28049 f152b230cd4876421ae16f3330d35ea8d7c00f05
parent 28048 8f7b73d88f6bbedec99c6c8ef48b243ab922d05c
child 28050 b5414a0acb156295c74732c73c33a27e9a0650fc
push id6860
push userdbaron@mozilla.com
push dateWed, 06 May 2009 20:46:33 +0000
treeherdermozilla-central@f152b230cd48 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbsmedberg
bugs490695
milestone1.9.2a1pre
Make cycle collector's purple buffer consist of entries that the objects in the purple buffer can point to, and remove the notion of scan delay (which was previously set to 0). (Bug 490695) r+sr=peterv r=bsmedberg
xpcom/base/nsCycleCollector.cpp
xpcom/build/nsXPCOM.h
xpcom/build/nsXPCOMPrivate.h
xpcom/glue/nsISupportsImpl.h
xpcom/glue/standalone/nsXPCOMGlue.cpp
xpcom/stub/nsXPComStub.cpp
--- a/xpcom/base/nsCycleCollector.cpp
+++ b/xpcom/base/nsCycleCollector.cpp
@@ -170,48 +170,32 @@ struct nsCycleCollectorParams
     PRBool mHookMalloc;
     PRBool mDrawGraphs;
     PRBool mFaultIsFatal;
     PRBool mLogPointers;
 
     PRUint32 mShutdownCollections;
 #endif
     
-    PRUint32 mScanDelay;
-    
     nsCycleCollectorParams() :
 #ifdef DEBUG_CC
         mDoNothing     (PR_GetEnv("XPCOM_CC_DO_NOTHING") != NULL),
         mReportStats   (PR_GetEnv("XPCOM_CC_REPORT_STATS") != NULL),
         mHookMalloc    (PR_GetEnv("XPCOM_CC_HOOK_MALLOC") != NULL),
         mDrawGraphs    (PR_GetEnv("XPCOM_CC_DRAW_GRAPHS") != NULL),
         mFaultIsFatal  (PR_GetEnv("XPCOM_CC_FAULT_IS_FATAL") != NULL),
         mLogPointers   (PR_GetEnv("XPCOM_CC_LOG_POINTERS") != NULL),
 
-        mShutdownCollections(DEFAULT_SHUTDOWN_COLLECTIONS),
+        mShutdownCollections(DEFAULT_SHUTDOWN_COLLECTIONS)
 #else
-        mDoNothing     (PR_FALSE),
+        mDoNothing     (PR_FALSE)
 #endif
-
-        // The default number of collections to "age" candidate
-        // pointers in the purple buffer before we decide that any
-        // garbage cycle they're in has stabilized and we want to
-        // consider scanning it.
-        //
-        // Making this number smaller causes:
-        //   - More time to be spent in the collector (bad)
-        //   - Less delay between forming garbage and collecting it (good)
-
-        mScanDelay(0)
     {
 #ifdef DEBUG_CC
-        char *s = PR_GetEnv("XPCOM_CC_SCAN_DELAY");
-        if (s)
-            PR_sscanf(s, "%d", &mScanDelay);
-        s = PR_GetEnv("XPCOM_CC_SHUTDOWN_COLLECTIONS");
+        char *s = PR_GetEnv("XPCOM_CC_SHUTDOWN_COLLECTIONS");
         if (s)
             PR_sscanf(s, "%d", &mShutdownCollections);
 #endif
     }
 };
 
 #ifdef DEBUG_CC
 // Various operations involving the collector are recorded in a
@@ -229,21 +213,18 @@ struct nsCycleCollectorStats
     PRUint32 mFreedBytes;
 
     PRUint32 mSetColorGrey;
     PRUint32 mSetColorBlack;
     PRUint32 mSetColorWhite;
 
     PRUint32 mFailedUnlink;
     PRUint32 mCollectedNode;
-    PRUint32 mBumpGeneration;
-    PRUint32 mZeroGeneration;
 
     PRUint32 mSuspectNode;
-    PRUint32 mSpills;    
     PRUint32 mForgetNode;
     PRUint32 mFreedWhilePurple;
   
     PRUint32 mCollection;
 
     nsCycleCollectorStats()
     {
         memset(this, 0, sizeof(nsCycleCollectorStats));
@@ -263,21 +244,18 @@ struct nsCycleCollectorStats
         DUMP(mFreedBytes);
     
         DUMP(mSetColorGrey);
         DUMP(mSetColorBlack);
         DUMP(mSetColorWhite);
     
         DUMP(mFailedUnlink);
         DUMP(mCollectedNode);
-        DUMP(mBumpGeneration);
-        DUMP(mZeroGeneration);
     
         DUMP(mSuspectNode);
-        DUMP(mSpills);
         DUMP(mForgetNode);
         DUMP(mFreedWhilePurple);
     
         DUMP(mCollection);
 #undef DUMP
     }
 };
 #endif
@@ -655,226 +633,258 @@ struct GCGraph
     }
     ~GCGraph() { 
     }
 };
 
 // XXX Would be nice to have an nsHashSet<KeyType> API that has
 // Add/Remove/Has rather than PutEntry/RemoveEntry/GetEntry.
 typedef nsTHashtable<nsVoidPtrHashKey> PointerSet;
-typedef nsBaseHashtable<nsVoidPtrHashKey, PRUint32, PRUint32>
-    PointerSetWithGeneration;
 
 #ifdef DEBUG_CC
 static void
 WriteGraph(FILE *stream, GCGraph &graph, const void *redPtr);
 #endif
 
 struct nsPurpleBuffer
 {
-
-#define ASSOCIATIVITY 2
-#define INDEX_LOW_BIT 6
-#define N_INDEX_BITS 13
-
-#define N_ENTRIES (1 << N_INDEX_BITS)
-#define N_POINTERS (N_ENTRIES * ASSOCIATIVITY)
-#define TOTAL_BYTES (N_POINTERS * PR_BYTES_PER_WORD)
-#define INDEX_MASK PR_BITMASK(N_INDEX_BITS)
-#define POINTER_INDEX(P) ((((PRUword)P) >> INDEX_LOW_BIT) & (INDEX_MASK))
-
-#if (INDEX_LOW_BIT + N_INDEX_BITS > (8 * PR_BYTES_PER_WORD))
-#error "index bit overflow"
-#endif
-
-    // This class serves as a generational wrapper around a pldhash
-    // table: a subset of generation zero lives in mCache, the
-    // remainder spill into the mBackingStore hashtable. The idea is
-    // to get a higher hit rate and greater locality of reference for
-    // generation zero, in which the vast majority of suspect/forget
-    // calls annihilate one another.
+private:
+    struct Block {
+        Block *mNext;
+        nsPurpleBufferEntry mEntries[128];
+
+        Block() : mNext(nsnull) {}
+    };
+public:
+    // This class wraps a linked list of the elements in the purple
+    // buffer.
 
     nsCycleCollectorParams &mParams;
+    PRUint32 mCount;
+    Block mFirstBlock;
+    nsPurpleBufferEntry *mFreeList;
+
+    // For objects compiled against Gecko 1.9 and 1.9.1.
+    PointerSet mCompatObjects;
 #ifdef DEBUG_CC
+    PointerSet mNormalObjects; // duplicates our blocks
     nsCycleCollectorStats &mStats;
 #endif
-    void* mCache[N_POINTERS];
-    PRUint32 mCurrGen;    
-    PointerSetWithGeneration mBackingStore;
     
 #ifdef DEBUG_CC
     nsPurpleBuffer(nsCycleCollectorParams &params,
                    nsCycleCollectorStats &stats) 
         : mParams(params),
-          mStats(stats),
-          mCurrGen(0)
+          mStats(stats)
     {
-        Init();
+        InitBlocks();
+        mNormalObjects.Init();
+        mCompatObjects.Init();
     }
 #else
     nsPurpleBuffer(nsCycleCollectorParams &params) 
-        : mParams(params),
-          mCurrGen(0)
+        : mParams(params)
     {
-        Init();
+        InitBlocks();
+        mCompatObjects.Init();
     }
 #endif
 
     ~nsPurpleBuffer()
     {
-        memset(mCache, 0, sizeof(mCache));
-        mBackingStore.Clear();
+        FreeBlocks();
     }
 
-    void Init()
+    void InitBlocks()
+    {
+        mCount = 0;
+        mFreeList = nsnull;
+        StartBlock(&mFirstBlock);
+    }
+
+    void StartBlock(Block *aBlock)
     {
-        memset(mCache, 0, sizeof(mCache));
-        mBackingStore.Init();
+        NS_ABORT_IF_FALSE(!mFreeList, "should not have free list");
+
+        // Put all the entries in the block on the free list.
+        nsPurpleBufferEntry *entries = aBlock->mEntries;
+        mFreeList = entries;
+        for (PRUint32 i = 1; i < NS_ARRAY_LENGTH(aBlock->mEntries); ++i) {
+            entries[i - 1].mNextInFreeList =
+                (nsPurpleBufferEntry*)(PRUword(entries + i) | 1);
+        }
+        entries[NS_ARRAY_LENGTH(aBlock->mEntries) - 1].mNextInFreeList =
+            (nsPurpleBufferEntry*)1;
     }
 
-    void BumpGeneration();
-    void SelectAgedPointers(GCGraphBuilder &builder);
+    void FreeBlocks()
+    {
+        Block *b = mFirstBlock.mNext; 
+        while (b) {
+            Block *next = b->mNext;
+            delete b;
+            b = next;
+        }
+        mFirstBlock.mNext = nsnull;
+    }
+
+    void SelectPointers(GCGraphBuilder &builder);
 
 #ifdef DEBUG_CC
     void NoteAll(GCGraphBuilder &builder);
-#endif
-
-    PRBool Exists(void *p)
+
+    PRBool Exists(void *p) const
     {
-        PRUint32 idx = POINTER_INDEX(p);
-        for (PRUint32 i = 0; i < ASSOCIATIVITY; ++i) {
-            if (mCache[idx+i] == p)
-                return PR_TRUE;
-        }
-        PRUint32 gen;
-        return mBackingStore.Get(p, &gen);
+        return mNormalObjects.GetEntry(p) || mCompatObjects.GetEntry(p);
     }
-
-    void Put(void *p)
+#endif
+
+    nsPurpleBufferEntry* NewEntry()
     {
-        PRUint32 idx = POINTER_INDEX(p);
-        for (PRUint32 i = 0; i < ASSOCIATIVITY; ++i) {
-            if (!mCache[idx+i]) {
-                mCache[idx+i] = p;
-                return;
+        if (!mFreeList) {
+            Block *b = new Block;
+            if (!b) {
+                return nsnull;
             }
+            StartBlock(b);
+
+            // Add the new block as the second block in the list.
+            b->mNext = mFirstBlock.mNext;
+            mFirstBlock.mNext = b;
         }
-#ifdef DEBUG_CC
-        mStats.mSpills++;
-#endif
-        SpillOne(p);
+
+        nsPurpleBufferEntry *e = mFreeList;
+        mFreeList = (nsPurpleBufferEntry*)
+            (PRUword(mFreeList->mNextInFreeList) & ~PRUword(1));
+        return e;
     }
 
-    void Remove(void *p)     
+    nsPurpleBufferEntry* Put(nsISupports *p)
     {
-        PRUint32 idx = POINTER_INDEX(p);
-        for (PRUint32 i = 0; i < ASSOCIATIVITY; ++i) {
-            if (mCache[idx+i] == p) {
-                mCache[idx+i] = (void*)0;
-                return;
-            }
+        nsPurpleBufferEntry *e = NewEntry();
+        if (!e) {
+            return nsnull;
         }
-        mBackingStore.Remove(p);
-    }
-
-    void SpillOne(void* &p)
-    {
-        mBackingStore.Put(p, mCurrGen);
-        p = (void*)0;
+
+        ++mCount;
+
+        e->mObject = p;
+
+#ifdef DEBUG_CC
+        mNormalObjects.PutEntry(p);
+#endif
+
+        // Caller is responsible for filling in result's mRefCnt.
+        return e;
     }
 
-    void SpillAll()
+    void Remove(nsPurpleBufferEntry *e)
     {
-        for (PRUint32 i = 0; i < N_POINTERS; ++i) {
-            if (mCache[i]) {
-                SpillOne(mCache[i]);
-            }
-        }
+        NS_ASSERTION(mCount != 0, "must have entries");
+
+#ifdef DEBUG_CC
+        mNormalObjects.RemoveEntry(e->mObject);
+#endif
+
+        e->mNextInFreeList =
+            (nsPurpleBufferEntry*)(PRUword(mFreeList) | PRUword(1));
+        mFreeList = e;
+
+        --mCount;
     }
 
-    PRUint32 Count()
+    PRBool PutCompatObject(nsISupports *p)
+    {
+        ++mCount;
+        return !!mCompatObjects.PutEntry(p);
+    }
+
+    void RemoveCompatObject(nsISupports *p)
     {
-        PRUint32 count = mBackingStore.Count();
-        for (PRUint32 i = 0; i < N_POINTERS; ++i) {
-            if (mCache[i]) {
-                ++count;
-            }
-        }
-        return count;
+        --mCount;
+        mCompatObjects.RemoveEntry(p);
+    }
+
+    PRUint32 Count() const
+    {
+        return mCount;
     }
 };
 
-static PLDHashOperator
-zeroGenerationCallback(const void*  ptr,
-                       PRUint32&    generation,
-                       void*        userArg)
-{
-#ifdef DEBUG_CC
-    nsPurpleBuffer *purp = static_cast<nsPurpleBuffer*>(userArg);
-    purp->mStats.mZeroGeneration++;
-#endif
-    generation = 0;
-    return PL_DHASH_NEXT;
-}
-
-void nsPurpleBuffer::BumpGeneration()
-{
-    SpillAll();
-    if (mCurrGen == 0xffffffff) {
-        mBackingStore.Enumerate(zeroGenerationCallback, this);
-        mCurrGen = 0;
-    } else {
-        ++mCurrGen;
-    }
-#ifdef DEBUG_CC
-    mStats.mBumpGeneration++;
-#endif
-}
-
-static inline PRBool
-SufficientlyAged(PRUint32 generation, nsPurpleBuffer *p)
-{
-    return generation + p->mParams.mScanDelay < p->mCurrGen;
-}
-
 struct CallbackClosure
 {
     CallbackClosure(nsPurpleBuffer *aPurpleBuffer, GCGraphBuilder &aBuilder)
         : mPurpleBuffer(aPurpleBuffer),
           mBuilder(aBuilder)
     {
     }
     nsPurpleBuffer *mPurpleBuffer;
     GCGraphBuilder &mBuilder;
 };
 
 static PRBool
 AddPurpleRoot(GCGraphBuilder &builder, nsISupports *root);
 
 static PLDHashOperator
-ageSelectionCallback(const void*  ptr,
-                     PRUint32&    generation,
-                     void*        userArg)
+selectionCallback(nsVoidPtrHashKey* key, void* userArg)
 {
     CallbackClosure *closure = static_cast<CallbackClosure*>(userArg);
-    if (SufficientlyAged(generation, closure->mPurpleBuffer) &&
-        AddPurpleRoot(closure->mBuilder,
-                      static_cast<nsISupports *>(const_cast<void*>(ptr))))
+    if (AddPurpleRoot(closure->mBuilder,
+                      static_cast<nsISupports *>(
+                        const_cast<void*>(key->GetKey()))))
         return PL_DHASH_REMOVE;
 
     return PL_DHASH_NEXT;
 }
 
 void
-nsPurpleBuffer::SelectAgedPointers(GCGraphBuilder &aBuilder)
+nsPurpleBuffer::SelectPointers(GCGraphBuilder &aBuilder)
 {
-    // Rely on our caller having done a BumpGeneration first, which in
-    // turn calls SpillAll.
-    CallbackClosure closure(this, aBuilder);
-    mBackingStore.Enumerate(ageSelectionCallback, &closure);
+#ifdef DEBUG_CC
+    NS_ABORT_IF_FALSE(mCompatObjects.Count() + mNormalObjects.Count() ==
+                          mCount,
+                      "count out of sync");
+#endif
+
+    if (mCompatObjects.Count()) {
+        mCount -= mCompatObjects.Count();
+        CallbackClosure closure(this, aBuilder);
+        mCompatObjects.EnumerateEntries(selectionCallback, &closure);
+        mCount += mCompatObjects.Count(); // in case of allocation failure
+    }
+
+    // Walk through all the blocks.
+    for (Block *b = &mFirstBlock; b; b = b->mNext) {
+        for (nsPurpleBufferEntry *e = b->mEntries,
+                              *eEnd = e + NS_ARRAY_LENGTH(b->mEntries);
+            e != eEnd; ++e) {
+            if (!(PRUword(e->mObject) & PRUword(1))) {
+                // This is a real entry (rather than something on the
+                // free list).
+                if (AddPurpleRoot(aBuilder, e->mObject)) {
+#ifdef DEBUG_CC
+                    mNormalObjects.RemoveEntry(e->mObject);
+#endif
+                    --mCount;
+                    // Put this entry on the free list in case some
+                    // call to AddPurpleRoot fails and we don't rebuild
+                    // the free list below.
+                    e->mNextInFreeList = (nsPurpleBufferEntry*)
+                        (PRUword(mFreeList) | PRUword(1));
+                    mFreeList = e;
+                }
+            }
+        }
+    }
+
+    NS_WARN_IF_FALSE(mCount == 0, "AddPurpleRoot failed");
+    if (mCount == 0) {
+        FreeBlocks();
+        InitBlocks();
+    }
 }
 
 
 
 ////////////////////////////////////////////////////////////////////////
 // Implement the LanguageRuntime interface for C++/XPCOM 
 ////////////////////////////////////////////////////////////////////////
 
@@ -926,18 +936,23 @@ struct nsCycleCollector
     void MarkRoots(GCGraphBuilder &builder);
     void ScanRoots();
     void RootWhite();
     PRBool CollectWhite(); // returns whether anything was collected
 
     nsCycleCollector();
     ~nsCycleCollector();
 
+    // The first pair of Suspect and Forget functions are only used by
+    // old XPCOM binary components.
     PRBool Suspect(nsISupports *n);
     PRBool Forget(nsISupports *n);
+    nsPurpleBufferEntry* Suspect2(nsISupports *n);
+    PRBool Forget2(nsPurpleBufferEntry *e);
+
     PRUint32 Collect(PRUint32 aTryCollections = 1);
     PRBool BeginCollection();
     PRBool FinishCollection();
     PRUint32 SuspectedCount();
     void Shutdown();
 
     void ClearGraph()
     {
@@ -1501,36 +1516,45 @@ AddPurpleRoot(GCGraphBuilder &builder, n
 
     cp->UnmarkPurple(root);
 
     return PR_TRUE;
 }
 
 #ifdef DEBUG_CC
 static PLDHashOperator
-noteAllCallback(const void* ptr, PRUint32& generation, void* userArg)
+noteAllCallback(nsVoidPtrHashKey* key, void* userArg)
 {
     GCGraphBuilder *builder = static_cast<GCGraphBuilder*>(userArg);
-    builder->NoteXPCOMRoot(static_cast<nsISupports *>(const_cast<void*>(ptr)));
+    builder->NoteXPCOMRoot(
+      static_cast<nsISupports *>(const_cast<void*>(key->GetKey())));
     return PL_DHASH_NEXT;
 }
 
 void
 nsPurpleBuffer::NoteAll(GCGraphBuilder &builder)
 {
-    SpillAll();
-    mBackingStore.Enumerate(noteAllCallback, &builder);
+    mCompatObjects.EnumerateEntries(noteAllCallback, &builder);
+
+    for (Block *b = &mFirstBlock; b; b = b->mNext) {
+        for (nsPurpleBufferEntry *e = b->mEntries,
+                              *eEnd = e + NS_ARRAY_LENGTH(b->mEntries);
+            e != eEnd; ++e) {
+            if (!(PRUword(e->mObject) & PRUword(1))) {
+                builder.NoteXPCOMRoot(e->mObject);
+            }
+        }
+    }
 }
 #endif
 
 void 
 nsCycleCollector::SelectPurple(GCGraphBuilder &builder)
 {
-    mPurpleBuf.BumpGeneration();
-    mPurpleBuf.SelectAgedPointers(builder);
+    mPurpleBuf.SelectPointers(builder);
 }
 
 void
 nsCycleCollector::MarkRoots(GCGraphBuilder &builder)
 {
     mGraph.mRootCount = builder.Count();
 
     // read the PtrInfo out of the graph that we are building
@@ -2163,19 +2187,17 @@ nsCycleCollector::Suspect(nsISupports *n
 
     if (mParams.mLogPointers) {
         if (!mPtrLog)
             mPtrLog = fopen("pointer_log", "w");
         fprintf(mPtrLog, "S %p\n", static_cast<void*>(n));
     }
 #endif
 
-    mPurpleBuf.Put(n);
-
-    return PR_TRUE;
+    return mPurpleBuf.PutCompatObject(n);
 }
 
 
 PRBool
 nsCycleCollector::Forget(nsISupports *n)
 {
     // Re-entering ::Forget during collection used to be a fault, but
     // we are canonicalizing nsISupports pointers using QI, so we will
@@ -2199,17 +2221,88 @@ nsCycleCollector::Forget(nsISupports *n)
 
     if (mParams.mLogPointers) {
         if (!mPtrLog)
             mPtrLog = fopen("pointer_log", "w");
         fprintf(mPtrLog, "F %p\n", static_cast<void*>(n));
     }
 #endif
 
-    mPurpleBuf.Remove(n);
+    mPurpleBuf.RemoveCompatObject(n);
+    return PR_TRUE;
+}
+
+nsPurpleBufferEntry*
+nsCycleCollector::Suspect2(nsISupports *n)
+{
+    // Re-entering ::Suspect during collection used to be a fault, but
+    // we are canonicalizing nsISupports pointers using QI, so we will
+    // see some spurious refcount traffic here. 
+
+    if (mScanInProgress)
+        return nsnull;
+
+    NS_ASSERTION(nsCycleCollector_isScanSafe(n),
+                 "suspected a non-scansafe pointer");
+    NS_ASSERTION(NS_IsMainThread(), "trying to suspect from non-main thread");
+
+    if (mParams.mDoNothing)
+        return nsnull;
+
+#ifdef DEBUG_CC
+    mStats.mSuspectNode++;
+
+    if (nsCycleCollector_shouldSuppress(n))
+        return nsnull;
+
+#ifndef __MINGW32__
+    if (mParams.mHookMalloc)
+        InitMemHook();
+#endif
+
+    if (mParams.mLogPointers) {
+        if (!mPtrLog)
+            mPtrLog = fopen("pointer_log", "w");
+        fprintf(mPtrLog, "S %p\n", static_cast<void*>(n));
+    }
+#endif
+
+    // Caller is responsible for filling in result's mRefCnt.
+    return mPurpleBuf.Put(n);
+}
+
+
+PRBool
+nsCycleCollector::Forget2(nsPurpleBufferEntry *e)
+{
+    // Re-entering ::Forget during collection used to be a fault, but
+    // we are canonicalizing nsISupports pointers using QI, so we will
+    // see some spurious refcount traffic here. 
+
+    if (mScanInProgress)
+        return PR_FALSE;
+
+    NS_ASSERTION(NS_IsMainThread(), "trying to forget from non-main thread");
+    
+#ifdef DEBUG_CC
+    mStats.mForgetNode++;
+
+#ifndef __MINGW32__
+    if (mParams.mHookMalloc)
+        InitMemHook();
+#endif
+
+    if (mParams.mLogPointers) {
+        if (!mPtrLog)
+            mPtrLog = fopen("pointer_log", "w");
+        fprintf(mPtrLog, "F %p\n", static_cast<void*>(e->mObject));
+    }
+#endif
+
+    mPurpleBuf.Remove(e);
     return PR_TRUE;
 }
 
 #ifdef DEBUG_CC
 void 
 nsCycleCollector::Allocated(void *n, size_t sz)
 {
 }
@@ -2223,17 +2316,16 @@ nsCycleCollector::Freed(void *n)
         // Ignore null pointers coming through
         return;
     }
 
     if (mPurpleBuf.Exists(n)) {
         mStats.mForgetNode++;
         mStats.mFreedWhilePurple++;
         Fault("freed while purple", n);
-        mPurpleBuf.Remove(n);
         
         if (mParams.mLogPointers) {
             if (!mPtrLog)
                 mPtrLog = fopen("pointer_log", "w");
             fprintf(mPtrLog, "R %p\n", n);
         }
     }
 }
@@ -2487,21 +2579,19 @@ PRUint32
 nsCycleCollector::SuspectedCount()
 {
     return mPurpleBuf.Count();
 }
 
 void
 nsCycleCollector::Shutdown()
 {
-    // Here we want to run a final collection on everything we've seen
-    // buffered, irrespective of age; then permanently disable
-    // the collector because the program is shutting down.
-
-    mParams.mScanDelay = 0;
+    // Here we want to run a final collection and then permanently
+    // disable the collector because the program is shutting down.
+
     Collect(SHUTDOWN_COLLECTIONS(mParams));
 
 #ifdef DEBUG_CC
     GCGraphBuilder builder(mGraph, mRuntimes);
     mScanInProgress = PR_TRUE;
     SelectPurple(builder);
     mScanInProgress = PR_FALSE;
     if (builder.Count() != 0) {
@@ -2793,17 +2883,19 @@ nsCycleCollector::ExplainLiveExpectedGar
                     }
                 }
 
                 {
                     NodePool::Enumerator queue(mGraph.mNodes);
                     while (!queue.IsDone()) {
                         PtrInfo *pi = queue.GetNext();
                         if (pi->mColor == white) {
-                            if (mPurpleBuf.Exists(pi->mPointer)) {
+                            if (pi->mLangID ==
+                                    nsIProgrammingLanguage::CPLUSPLUS &&
+                                mPurpleBuf.Exists(pi->mPointer)) {
                                 printf(
 "nsCycleCollector: %s %p in component %d\n"
 "  which was reference counted during the root/unlink/unroot phase of the\n"
 "  last collection was not collected due to failure to unlink (see other\n"
 "  warnings) or deficiency in traverse that causes cycles referenced only\n"
 "  from other cycles to require multiple rounds of cycle collection in which\n"
 "  this object was likely the reachable object\n",
                                        pi->mName, pi->mPointer, pi->mSCCIndex);
@@ -2928,23 +3020,36 @@ nsCycleCollector_forgetRuntime(PRUint32 
 PRBool
 NS_CycleCollectorSuspect(nsISupports *n)
 {
     if (sCollector)
         return sCollector->Suspect(n);
     return PR_FALSE;
 }
 
-
 PRBool
 NS_CycleCollectorForget(nsISupports *n)
 {
     return sCollector ? sCollector->Forget(n) : PR_TRUE;
 }
 
+nsPurpleBufferEntry*
+NS_CycleCollectorSuspect2(nsISupports *n)
+{
+    if (sCollector)
+        return sCollector->Suspect2(n);
+    return nsnull;
+}
+
+PRBool
+NS_CycleCollectorForget2(nsPurpleBufferEntry *e)
+{
+    return sCollector ? sCollector->Forget2(e) : PR_TRUE;
+}
+
 
 PRUint32
 nsCycleCollector_collect()
 {
     return sCollector ? sCollector->Collect() : 0;
 }
 
 PRUint32
--- a/xpcom/build/nsXPCOM.h
+++ b/xpcom/build/nsXPCOM.h
@@ -61,41 +61,46 @@
 # define NS_LogAddRef                NS_LogAddRef_P
 # define NS_LogRelease               NS_LogRelease_P
 # define NS_LogCtor                  NS_LogCtor_P
 # define NS_LogDtor                  NS_LogDtor_P
 # define NS_LogCOMPtrAddRef          NS_LogCOMPtrAddRef_P
 # define NS_LogCOMPtrRelease         NS_LogCOMPtrRelease_P
 # define NS_CycleCollectorSuspect    NS_CycleCollectorSuspect_P
 # define NS_CycleCollectorForget     NS_CycleCollectorForget_P
+# define NS_CycleCollectorSuspect2   NS_CycleCollectorSuspect2_P
+# define NS_CycleCollectorForget2    NS_CycleCollectorForget2_P
 #endif
 
 #include "nscore.h"
 #include "nsXPCOMCID.h"
 
 #ifdef __cplusplus
 #define DECL_CLASS(c) class c
+#define DECL_STRUCT(c) struct c
 #else
 #define DECL_CLASS(c) typedef struct c c
+#define DECL_STRUCT(c) typedef struct c c
 #endif
 
 DECL_CLASS(nsAString);
 DECL_CLASS(nsACString);
 
 DECL_CLASS(nsISupports);
 DECL_CLASS(nsIModule);
 DECL_CLASS(nsIComponentManager);
 DECL_CLASS(nsIComponentRegistrar);
 DECL_CLASS(nsIServiceManager);
 DECL_CLASS(nsIFile);
 DECL_CLASS(nsILocalFile);
 DECL_CLASS(nsIDirectoryServiceProvider);
 DECL_CLASS(nsIMemory);
 DECL_CLASS(nsIDebug);
 DECL_CLASS(nsITraceRefcnt);
+DECL_STRUCT(nsPurpleBufferEntry);
 
 /**
  * Every XPCOM component implements this function signature, which is the
  * only entrypoint XPCOM uses to the function.
  *
  * @status FROZEN
  */
 typedef nsresult (*nsGetModuleProc)(nsIComponentManager *aCompMgr,
@@ -454,23 +459,32 @@ NS_LogCOMPtrAddRef(void *aCOMPtr, nsISup
 
 XPCOM_API(void)
 NS_LogCOMPtrRelease(void *aCOMPtr, nsISupports *aObject);
 
 /**
  * The XPCOM cycle collector analyzes and breaks reference cycles between
  * participating XPCOM objects. All objects in the cycle must implement
  * nsCycleCollectionParticipant to break cycles correctly.
+ *
+ * The first two functions below exist only to support binary components
+ * that were compiled for older XPCOM versions.
  */
 XPCOM_API(PRBool)
 NS_CycleCollectorSuspect(nsISupports *n);
 
 XPCOM_API(PRBool)
 NS_CycleCollectorForget(nsISupports *n);
 
+XPCOM_API(nsPurpleBufferEntry*)
+NS_CycleCollectorSuspect2(nsISupports *n);
+
+XPCOM_API(PRBool)
+NS_CycleCollectorForget2(nsPurpleBufferEntry *e);
+
 /**
  * Categories (in the category manager service) used by XPCOM:
  */
 
 /**
  * A category which is read after component registration but before
  * the "xpcom-startup" notifications. Each category entry is treated
  * as the contract ID of a service which implements
--- a/xpcom/build/nsXPCOMPrivate.h
+++ b/xpcom/build/nsXPCOMPrivate.h
@@ -114,16 +114,19 @@ typedef void       (* LogAddRefFunc)(voi
 typedef void       (* LogReleaseFunc)(void*, nsrefcnt, const char*);
 typedef void       (* LogCtorFunc)(void*, const char*, PRUint32);
 typedef void       (* LogCOMPtrFunc)(void*, nsISupports*);
 
 typedef nsresult   (* GetXPTCallStubFunc)(REFNSIID, nsIXPTCProxy*, nsISomeInterface**);
 typedef void       (* DestroyXPTCallStubFunc)(nsISomeInterface*);
 typedef nsresult   (* InvokeByIndexFunc)(nsISupports*, PRUint32, PRUint32, nsXPTCVariant*);
 typedef PRBool     (* CycleCollectorFunc)(nsISupports*);
+typedef nsPurpleBufferEntry*
+                   (* CycleCollectorSuspect2Func)(nsISupports*);
+typedef PRBool     (* CycleCollectorForget2Func)(nsPurpleBufferEntry*);
 
 // PRIVATE AND DEPRECATED
 typedef NS_CALLBACK(XPCOMExitRoutine)(void);
 
 typedef nsresult   (* RegisterXPCOMExitRoutineFunc)(XPCOMExitRoutine exitRoutine, PRUint32 priority);
 typedef nsresult   (* UnregisterXPCOMExitRoutineFunc)(XPCOMExitRoutine exitRoutine);
 
 typedef struct XPCOMFunctions{
@@ -189,16 +192,20 @@ typedef struct XPCOMFunctions{
     InvokeByIndexFunc invokeByIndexFunc;
     CycleCollectorFunc cycleSuspectFunc;
     CycleCollectorFunc cycleForgetFunc;
     StringSetIsVoidFunc stringSetIsVoid;
     StringGetIsVoidFunc stringGetIsVoid;
     CStringSetIsVoidFunc cstringSetIsVoid;
     CStringGetIsVoidFunc cstringGetIsVoid;
 
+    // Added for Mozilla 1.9.2
+    CycleCollectorSuspect2Func cycleSuspect2Func;
+    CycleCollectorForget2Func cycleForget2Func;
+
 } XPCOMFunctions;
 
 typedef nsresult (*GetFrozenFunctionsFunc)(XPCOMFunctions *entryPoints, const char* libraryPath);
 XPCOM_API(nsresult)
 NS_GetFrozenFunctions(XPCOMFunctions *entryPoints, const char* libraryPath);
 
 // think hard before changing this
 #define XPCOM_GLUE_VERSION 1
--- a/xpcom/glue/nsISupportsImpl.h
+++ b/xpcom/glue/nsISupportsImpl.h
@@ -80,120 +80,167 @@ private:
 
 #else // !NS_DEBUG
 
 #define NS_DECL_OWNINGTHREAD            /* nothing */
 #define NS_ASSERT_OWNINGTHREAD(_class)  ((void)0)
 
 #endif // NS_DEBUG
 
-#define NS_PURPLE_BIT ((PRUint32)(1 << 31))
-
-#define NS_PURPLE_MASK (~NS_PURPLE_BIT)
-#define NS_PURPLE_BIT_SET(x) ((x) & (NS_PURPLE_BIT))
-#define NS_CLEAR_PURPLE_BIT(x) ((x) &= (NS_PURPLE_MASK))
-#define NS_VALUE_WITHOUT_PURPLE_BIT(x) ((x) & (NS_PURPLE_MASK))
-
+#define NS_CCAR_REFCNT_BIT 1
+#define NS_CCAR_REFCNT_TO_TAGGED(rc_) \
+  NS_INT32_TO_PTR((rc_ << 1) | NS_CCAR_REFCNT_BIT)
+#define NS_CCAR_PURPLE_ENTRY_TO_TAGGED(pe_) \
+  static_cast<void*>(pe_)
+#define NS_CCAR_TAGGED_TO_REFCNT(tagged_) \
+  nsrefcnt(NS_PTR_TO_INT32(tagged_) >> 1)
+#define NS_CCAR_TAGGED_TO_PURPLE_ENTRY(tagged_) \
+  static_cast<nsPurpleBufferEntry*>(tagged_)
+#define NS_CCAR_TAGGED_STABILIZED_REFCNT NS_CCAR_PURPLE_ENTRY_TO_TAGGED(0)
 
 // Support for ISupports classes which interact with cycle collector.
 
+/**
+ * This struct (once shipped) will be FROZEN with respect to the
+ * NS_CycleCollectorSuspect2 and NS_CycleCollectorForget2 functions.  If
+ * we need to change the struct, we'll need Suspect3 and Forget3 for the
+ * new versions.
+ */
+struct nsPurpleBufferEntry {
+  union {
+    nsISupports *mObject;                 // when low bit unset
+    nsPurpleBufferEntry *mNextInFreeList; // when low bit set
+  };
+  // When an object is in the purple buffer, it replaces its reference
+  // count with a (tagged) pointer to this entry, so we store the
+  // reference count for it.
+  nsrefcnt mRefCnt;
+};
+
 class nsCycleCollectingAutoRefCnt {
 
 public:
   nsCycleCollectingAutoRefCnt()
-    : mValue(0)
+    : mTagged(NS_CCAR_REFCNT_TO_TAGGED(0))
   {}
 
   nsCycleCollectingAutoRefCnt(nsrefcnt aValue)
-    : mValue(aValue)
+    : mTagged(NS_CCAR_REFCNT_TO_TAGGED(aValue))
   {
-    NS_CLEAR_PURPLE_BIT(mValue);
   }
 
   nsrefcnt incr(nsISupports *owner)
   {
-    if (NS_UNLIKELY(mValue == NS_PURPLE_BIT)) {
+    if (NS_UNLIKELY(mTagged == NS_CCAR_TAGGED_STABILIZED_REFCNT)) {
       // The sentinel value "purple bit alone, refcount 0" means
       // that we're stabilized, during finalization. In this
       // state we lie about our actual refcount if anyone asks
       // and say it's 2, which is basically true: the caller who
       // is incrementing has a reference, as does the decr() frame
       // that stabilized-and-is-deleting us.
       return 2;
     }
 
-    nsrefcnt tmp = get();
-    PRBool purple = static_cast<PRBool>(NS_PURPLE_BIT_SET(mValue));
+    nsrefcnt refcount;
+    if (IsPurple()) {
+      nsPurpleBufferEntry *e = NS_CCAR_TAGGED_TO_PURPLE_ENTRY(mTagged);
+      NS_ASSERTION(e->mObject == owner, "wrong entry");
+      refcount = e->mRefCnt;
+      NS_ASSERTION(refcount != 0, "purple ISupports pointer with zero refcnt");
 
-    if (NS_UNLIKELY(purple)) {
-      NS_ASSERTION(tmp != 0, "purple ISupports pointer with zero refcnt");
-      if (!NS_CycleCollectorForget(owner))
-        tmp |= NS_PURPLE_BIT;
+      if (NS_LIKELY(NS_CycleCollectorForget2(e))) {
+        // |e| is now invalid
+        ++refcount;
+        mTagged = NS_CCAR_REFCNT_TO_TAGGED(refcount);
+      } else {
+        ++refcount;
+        e->mRefCnt = refcount;
+      }
+    } else {
+      refcount = NS_CCAR_TAGGED_TO_REFCNT(mTagged);
+      ++refcount;
+      mTagged = NS_CCAR_REFCNT_TO_TAGGED(refcount);
     }
 
-    mValue = tmp + 1;
-    return mValue;
+    return refcount;
   }
 
   void stabilizeForDeletion(nsISupports *owner)
   {
-    mValue = NS_PURPLE_BIT;
+    mTagged = NS_CCAR_TAGGED_STABILIZED_REFCNT;
   }
 
   nsrefcnt decr(nsISupports *owner)
   {
-    if (NS_UNLIKELY(mValue == NS_PURPLE_BIT))
+    if (NS_UNLIKELY(mTagged == NS_CCAR_TAGGED_STABILIZED_REFCNT))
       return 1;
 
-    nsrefcnt tmp = get();
-    NS_ASSERTION(tmp >= 1, "decr() called with zero refcnt");
-
-    PRBool purple = static_cast<PRBool>(NS_PURPLE_BIT_SET(mValue));
-    PRBool shouldBePurple = tmp > 1;
+    nsrefcnt refcount;
+    if (IsPurple()) {
+      nsPurpleBufferEntry *e = NS_CCAR_TAGGED_TO_PURPLE_ENTRY(mTagged);
+      NS_ASSERTION(e->mObject == owner, "wrong entry");
+      refcount = e->mRefCnt;
+      --refcount;
+      
+      if (NS_UNLIKELY(refcount == 0)) {
+        if (NS_UNLIKELY(!NS_CycleCollectorForget2(e))) {
+          NS_NOTREACHED("forget should not fail when reference count hits 0");
+        }
+        mTagged = NS_CCAR_REFCNT_TO_TAGGED(refcount);
+      } else {
+        e->mRefCnt = refcount;
+      }
+    } else {
+      refcount = NS_CCAR_TAGGED_TO_REFCNT(mTagged);
+      --refcount;
 
-    if (NS_UNLIKELY(shouldBePurple && !purple)) {
-      if (!NS_CycleCollectorSuspect(owner))
-        shouldBePurple = PR_FALSE;
-    } else if (NS_UNLIKELY(tmp == 1 && purple)) {
-      if (!NS_CycleCollectorForget(owner)) {
-        NS_NOTREACHED("forget should not fail when reference count hits 0");
+      nsPurpleBufferEntry *e;
+      if (NS_LIKELY(refcount > 0) &&
+          ((e = NS_CycleCollectorSuspect2(owner)))) {
+        e->mRefCnt = refcount;
+        mTagged = NS_CCAR_PURPLE_ENTRY_TO_TAGGED(e);
+      } else {
+        mTagged = NS_CCAR_REFCNT_TO_TAGGED(refcount);
       }
     }
 
-    --tmp;
-
-    if (shouldBePurple)
-      mValue = tmp | NS_PURPLE_BIT;
-    else
-      mValue = tmp;
-
-    return tmp;
+    return refcount;
   }
 
   void unmarkPurple()
   {
-    if (NS_LIKELY(mValue != NS_PURPLE_BIT))
-      NS_CLEAR_PURPLE_BIT(mValue);
+    NS_ASSERTION(IsPurple(), "must be purple");
+    nsrefcnt refcount = NS_CCAR_TAGGED_TO_PURPLE_ENTRY(mTagged)->mRefCnt;
+    mTagged = NS_CCAR_REFCNT_TO_TAGGED(refcount);
+  }
+
+  PRBool IsPurple() const
+  {
+    NS_ASSERTION(mTagged != NS_CCAR_TAGGED_STABILIZED_REFCNT,
+                 "should have checked for stabilization first");
+    return !(NS_PTR_TO_INT32(mTagged) & NS_CCAR_REFCNT_BIT);
   }
 
   nsrefcnt get() const
   {
-    if (NS_UNLIKELY(mValue == NS_PURPLE_BIT))
+    if (NS_UNLIKELY(mTagged == NS_CCAR_TAGGED_STABILIZED_REFCNT))
       return 1;
 
-    return NS_VALUE_WITHOUT_PURPLE_BIT(mValue);
+    return NS_UNLIKELY(IsPurple())
+             ? NS_CCAR_TAGGED_TO_PURPLE_ENTRY(mTagged)->mRefCnt
+             : NS_CCAR_TAGGED_TO_REFCNT(mTagged);
   }
 
   operator nsrefcnt() const
   {
     return get();
   }
 
  private:
-  nsrefcnt mValue;
+  void *mTagged;
 };
 
 class nsAutoRefCnt {
 
  public:
     nsAutoRefCnt() : mValue(0) {}
     nsAutoRefCnt(nsrefcnt aValue) : mValue(aValue) {}
 
--- a/xpcom/glue/standalone/nsXPCOMGlue.cpp
+++ b/xpcom/glue/standalone/nsXPCOMGlue.cpp
@@ -560,8 +560,26 @@ NS_CycleCollectorSuspect(nsISupports* ob
 XPCOM_API(PRBool)
 NS_CycleCollectorForget(nsISupports* obj)
 {
     if (!xpcomFunctions.cycleForgetFunc)
         return PR_FALSE;
 
     return xpcomFunctions.cycleForgetFunc(obj);
 }
+
+XPCOM_API(nsPurpleBufferEntry*)
+NS_CycleCollectorSuspect2(nsISupports* obj)
+{
+    if (!xpcomFunctions.cycleSuspect2Func)
+        return nsnull;
+
+    return xpcomFunctions.cycleSuspect2Func(obj);
+}
+
+XPCOM_API(PRBool)
+NS_CycleCollectorForget2(nsPurpleBufferEntry* e)
+{
+    if (!xpcomFunctions.cycleForget2Func)
+        return PR_FALSE;
+
+    return xpcomFunctions.cycleForget2Func(e);
+}
--- a/xpcom/stub/nsXPComStub.cpp
+++ b/xpcom/stub/nsXPComStub.cpp
@@ -115,17 +115,21 @@ static const XPCOMFunctions kFrozenFunct
     &NS_GetXPTCallStub_P,
     &NS_DestroyXPTCallStub_P,
     &NS_InvokeByIndex_P,
     &NS_CycleCollectorSuspect_P,
     &NS_CycleCollectorForget_P,
     &NS_StringSetIsVoid_P,
     &NS_StringGetIsVoid_P,
     &NS_CStringSetIsVoid_P,
-    &NS_CStringGetIsVoid_P
+    &NS_CStringGetIsVoid_P,
+
+    // these functions were added post 1.9.1
+    &NS_CycleCollectorSuspect2_P,
+    &NS_CycleCollectorForget2_P
 };
 
 EXPORT_XPCOM_API(nsresult)
 NS_GetFrozenFunctions(XPCOMFunctions *functions, const char* /* libraryPath */)
 {
     if (!functions)
         return NS_ERROR_OUT_OF_MEMORY;
 
@@ -548,8 +552,22 @@ NS_CycleCollectorSuspect(nsISupports* ob
 }
 
 #undef NS_CycleCollectorForget
 EXPORT_XPCOM_API(PRBool)
 NS_CycleCollectorForget(nsISupports* obj)
 {
   return NS_CycleCollectorForget_P(obj);
 }
+
+#undef NS_CycleCollectorSuspect2
+EXPORT_XPCOM_API(nsPurpleBufferEntry*)
+NS_CycleCollectorSuspect2(nsISupports* obj)
+{
+  return NS_CycleCollectorSuspect2_P(obj);
+}
+
+#undef NS_CycleCollectorForget2
+EXPORT_XPCOM_API(PRBool)
+NS_CycleCollectorForget2(nsPurpleBufferEntry* e)
+{
+  return NS_CycleCollectorForget2_P(e);
+}