xpcom/base/nsCycleCollector.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /* vim: set cindent tabstop=4 expandtab shiftwidth=4: */
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is mozilla.org code.
  17  *
  18  * The Initial Developer of the Original Code is
  19  * The Mozilla Foundation.
  20  * Portions created by the Initial Developer are Copyright (C) 2006
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *   L. David Baron <dbaron@dbaron.org>, Mozilla Corporation
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either of the GNU General Public License Version 2 or later (the "GPL"),
  28  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 //
  41 // This file implements a garbage-cycle collector based on the paper
  42 //
  43 //   Concurrent Cycle Collection in Reference Counted Systems
  44 //   Bacon & Rajan (2001), ECOOP 2001 / Springer LNCS vol 2072
  45 //
  46 // We are not using the concurrent or acyclic cases of that paper; so
  47 // the green, red and orange colors are not used.
  48 //
  49 // The collector is based on tracking pointers of four colors:
  50 //
  51 // Black nodes are definitely live. If we ever determine a node is
  52 // black, it's ok to forget about, drop from our records.
  53 //
  54 // White nodes are definitely garbage cycles. Once we finish with our
  55 // scanning, we unlink all the white nodes and expect that by
  56 // unlinking them they will self-destruct (since a garbage cycle is
  57 // only keeping itself alive with internal links, by definition).
  58 //
  59 // Grey nodes are being scanned. Nodes that turn grey will turn
  60 // either black if we determine that they're live, or white if we
  61 // determine that they're a garbage cycle. After the main collection
  62 // algorithm there should be no grey nodes.
  63 //
  64 // Purple nodes are *candidates* for being scanned. They are nodes we
  65 // haven't begun scanning yet because they're not old enough, or we're
  66 // still partway through the algorithm.
  67 //
  68 // XPCOM objects participating in garbage-cycle collection are obliged
  69 // to inform us when they ought to turn purple; that is, when their
  70 // refcount transitions from N+1 -> N, for nonzero N. Furthermore we
  71 // require that *after* an XPCOM object has informed us of turning
  72 // purple, they will tell us when they either transition back to being
  73 // black (incremented refcount) or are ultimately deleted.
  74
  75
  76 // Safety:
  77 //
  78 // An XPCOM object is either scan-safe or scan-unsafe, purple-safe or
  79 // purple-unsafe.
  80 //
  81 // An object is scan-safe if:
  82 //
  83 //  - It can be QI'ed to |nsXPCOMCycleCollectionParticipant|, though this
  84 //    operation loses ISupports identity (like nsIClassInfo).
  85 //  - The operation |traverse| on the resulting
  86 //    nsXPCOMCycleCollectionParticipant does not cause *any* refcount
  87 //    adjustment to occur (no AddRef / Release calls).
  88 //
  89 // An object is purple-safe if it satisfies the following properties:
  90 //
  91 //  - The object is scan-safe.
  92 //  - If the object calls |nsCycleCollector::suspect(this)|,
  93 //    it will eventually call |nsCycleCollector::forget(this)|,
  94 //    exactly once per call to |suspect|, before being destroyed.
  95 //
  96 // When we receive a pointer |ptr| via
  97 // |nsCycleCollector::suspect(ptr)|, we assume it is purple-safe. We
  98 // can check the scan-safety, but have no way to ensure the
  99 // purple-safety; objects must obey, or else the entire system falls
 100 // apart. Don't involve an object in this scheme if you can't
 101 // guarantee its purple-safety.
 102 //
 103 // When we have a scannable set of purple nodes ready, we begin
 104 // our walks. During the walks, the nodes we |traverse| should only
 105 // feed us more scan-safe nodes, and should not adjust the refcounts
 106 // of those nodes.
 107 //
 108 // We do not |AddRef| or |Release| any objects during scanning. We
 109 // rely on purple-safety of the roots that call |suspect| and
 110 // |forget| to hold, such that we will forget about a purple pointer
 111 // before it is destroyed.  The pointers that are merely scan-safe,
 112 // we hold only for the duration of scanning, and there should be no
 113 // objects released from the scan-safe set during the scan (there
 114 // should be no threads involved).
 115 //
 116 // We *do* call |AddRef| and |Release| on every white object, on
 117 // either side of the calls to |Unlink|. This keeps the set of white
 118 // objects alive during the unlinking.
 119 //
 120
 121 #if !defined(__MINGW32__) && !defined(WINCE)
 122 #ifdef WIN32
 123 #include <crtdbg.h>
 124 #include <errno.h>
 125 #endif
 126 #endif
 127
 128 #include "nsCycleCollectionParticipant.h"
 129 #include "nsIProgrammingLanguage.h"
 130 #include "nsBaseHashtable.h"
 131 #include "nsHashKeys.h"
 132 #include "nsDeque.h"
 133 #include "nsCycleCollector.h"
 134 #include "nsThreadUtils.h"
 135 #include "prenv.h"
 136 #include "prprf.h"
 137 #include "plstr.h"
 138 #include "prtime.h"
 139 #include "nsPrintfCString.h"
 140 #include "nsTArray.h"
 141 #include "nsIObserverService.h"
 142 #include "nsIConsoleService.h"
 143 #include "nsServiceManagerUtils.h"
 144 #include "nsThreadUtils.h"
 145 #include "nsTPtrArray.h"
 146 #include "nsVoidArray.h" // for nsCStringArray
 147
 148 #include <stdio.h>
 149 #include <string.h>
 150 #ifdef WIN32
 151 #include <io.h>
 152 #include <process.h>
 153 #endif
 154
 155 #define DEFAULT_SHUTDOWN_COLLECTIONS 5
 156 #ifdef DEBUG_CC
 157 #define SHUTDOWN_COLLECTIONS(params) params.mShutdownCollections
 158 #else
 159 #define SHUTDOWN_COLLECTIONS(params) DEFAULT_SHUTDOWN_COLLECTIONS
 160 #endif
 161
 162 // Various parameters of this collector can be tuned using environment
 163 // variables.
 164
 165 struct nsCycleCollectorParams
 166 {
 167     PRBool mDoNothing;
 168 #ifdef DEBUG_CC
 169     PRBool mReportStats;
 170     PRBool mHookMalloc;
 171     PRBool mDrawGraphs;
 172     PRBool mFaultIsFatal;
 173     PRBool mLogPointers;
 174
 175     PRUint32 mShutdownCollections;
 176 #endif
 177
 178     PRUint32 mScanDelay;
 179
 180     nsCycleCollectorParams() :
 181 #ifdef DEBUG_CC
 182         mDoNothing     (PR_GetEnv("XPCOM_CC_DO_NOTHING") != NULL),
 183         mReportStats   (PR_GetEnv("XPCOM_CC_REPORT_STATS") != NULL),
 184         mHookMalloc    (PR_GetEnv("XPCOM_CC_HOOK_MALLOC") != NULL),
 185         mDrawGraphs    (PR_GetEnv("XPCOM_CC_DRAW_GRAPHS") != NULL),
 186         mFaultIsFatal  (PR_GetEnv("XPCOM_CC_FAULT_IS_FATAL") != NULL),
 187         mLogPointers   (PR_GetEnv("XPCOM_CC_LOG_POINTERS") != NULL),
 188
 189         mShutdownCollections(DEFAULT_SHUTDOWN_COLLECTIONS),
 190 #else
 191         mDoNothing     (PR_FALSE),
 192 #endif
 193
 194         // The default number of collections to "age" candidate
 195         // pointers in the purple buffer before we decide that any
 196         // garbage cycle they're in has stabilized and we want to
 197         // consider scanning it.
 198         //
 199         // Making this number smaller causes:
 200         //   - More time to be spent in the collector (bad)
 201         //   - Less delay between forming garbage and collecting it (good)
 202
 203         mScanDelay(0)
 204     {
 205 #ifdef DEBUG_CC
 206         char *s = PR_GetEnv("XPCOM_CC_SCAN_DELAY");
 207         if (s)
 208             PR_sscanf(s, "%d", &mScanDelay);
 209         s = PR_GetEnv("XPCOM_CC_SHUTDOWN_COLLECTIONS");
 210         if (s)
 211             PR_sscanf(s, "%d", &mShutdownCollections);
 212 #endif
 213     }
 214 };
 215
 216 #ifdef DEBUG_CC
 217 // Various operations involving the collector are recorded in a
 218 // statistics table. These are for diagnostics.
 219
 220 struct nsCycleCollectorStats
 221 {
 222     PRUint32 mFailedQI;
 223     PRUint32 mSuccessfulQI;
 224
 225     PRUint32 mVisitedNode;
 226     PRUint32 mWalkedGraph;
 227     PRUint32 mCollectedBytes;
 228     PRUint32 mFreeCalls;
 229     PRUint32 mFreedBytes;
 230
 231     PRUint32 mSetColorGrey;
 232     PRUint32 mSetColorBlack;
 233     PRUint32 mSetColorWhite;
 234
 235     PRUint32 mFailedUnlink;
 236     PRUint32 mCollectedNode;
 237     PRUint32 mBumpGeneration;
 238     PRUint32 mZeroGeneration;
 239
 240     PRUint32 mSuspectNode;
 241     PRUint32 mSpills;
 242     PRUint32 mForgetNode;
 243     PRUint32 mFreedWhilePurple;
 244
 245     PRUint32 mCollection;
 246
 247     nsCycleCollectorStats()
 248     {
 249         memset(this, 0, sizeof(nsCycleCollectorStats));
 250     }
 251
 252     void Dump()
 253     {
 254         fprintf(stderr, "\f\n");
 255 #define DUMP(entry) fprintf(stderr, "%30.30s: %-20.20d\n", #entry, entry)
 256         DUMP(mFailedQI);
 257         DUMP(mSuccessfulQI);
 258
 259         DUMP(mVisitedNode);
 260         DUMP(mWalkedGraph);
 261         DUMP(mCollectedBytes);
 262         DUMP(mFreeCalls);
 263         DUMP(mFreedBytes);
 264
 265         DUMP(mSetColorGrey);
 266         DUMP(mSetColorBlack);
 267         DUMP(mSetColorWhite);
 268
 269         DUMP(mFailedUnlink);
 270         DUMP(mCollectedNode);
 271         DUMP(mBumpGeneration);
 272         DUMP(mZeroGeneration);
 273
 274         DUMP(mSuspectNode);
 275         DUMP(mSpills);
 276         DUMP(mForgetNode);
 277         DUMP(mFreedWhilePurple);
 278
 279         DUMP(mCollection);
 280 #undef DUMP
 281     }
 282 };
 283 #endif
 284
 285 #ifdef DEBUG_CC
 286 static PRBool nsCycleCollector_shouldSuppress(nsISupports *s);
 287 static void InitMemHook(void);
 288 #endif
 289
 290 ////////////////////////////////////////////////////////////////////////
 291 // Base types
 292 ////////////////////////////////////////////////////////////////////////
 293
 294 struct PtrInfo;
 295
 296 class EdgePool
 297 {
 298 public:
 299     // EdgePool allocates arrays of void*, primarily to hold PtrInfo*.
 300     // However, at the end of a block, the last two pointers are a null
 301     // and then a void** pointing to the next block.  This allows
 302     // EdgePool::Iterators to be a single word but still capable of crossing
 303     // block boundaries.
 304
 305     EdgePool()
 306     {
 307         mSentinelAndBlocks[0].block = nsnull;
 308         mSentinelAndBlocks[1].block = nsnull;
 309     }
 310
 311     ~EdgePool()
 312     {
 313         NS_ASSERTION(!mSentinelAndBlocks[0].block &&
 314                      !mSentinelAndBlocks[1].block,
 315                      "Didn't call Clear()?");
 316     }
 317
 318     void Clear()
 319     {
 320         Block *b = Blocks();
 321         while (b) {
 322             Block *next = b->Next();
 323             delete b;
 324             b = next;
 325         }
 326
 327         mSentinelAndBlocks[0].block = nsnull;
 328         mSentinelAndBlocks[1].block = nsnull;
 329     }
 330
 331 private:
 332     struct Block;
 333     union PtrInfoOrBlock {
 334         // Use a union to avoid reinterpret_cast and the ensuing
 335         // potential aliasing bugs.
 336         PtrInfo *ptrInfo;
 337         Block *block;
 338     };
 339     struct Block {
 340         enum { BlockSize = 64 * 1024 };
 341
 342         PtrInfoOrBlock mPointers[BlockSize];
 343         Block() {
 344             mPointers[BlockSize - 2].block = nsnull; // sentinel
 345             mPointers[BlockSize - 1].block = nsnull; // next block pointer
 346         }
 347         Block*& Next()
 348             { return mPointers[BlockSize - 1].block; }
 349         PtrInfoOrBlock* Start()
 350             { return &mPointers[0]; }
 351         PtrInfoOrBlock* End()
 352             { return &mPointers[BlockSize - 2]; }
 353     };
 354
 355     // Store the null sentinel so that we can have valid iterators
 356     // before adding any edges and without adding any blocks.
 357     PtrInfoOrBlock mSentinelAndBlocks[2];
 358
 359     Block*& Blocks() { return mSentinelAndBlocks[1].block; }
 360
 361 public:
 362     class Iterator
 363     {
 364     public:
 365         Iterator() : mPointer(nsnull) {}
 366         Iterator(PtrInfoOrBlock *aPointer) : mPointer(aPointer) {}
 367         Iterator(const Iterator& aOther) : mPointer(aOther.mPointer) {}
 368
 369         Iterator& operator++()
 370         {
 371             if (mPointer->ptrInfo == nsnull) {
 372                 // Null pointer is a sentinel for link to the next block.
 373                 mPointer = (mPointer + 1)->block->mPointers;
 374             }
 375             ++mPointer;
 376             return *this;
 377         }
 378
 379         PtrInfo* operator*() const
 380         {
 381             if (mPointer->ptrInfo == nsnull) {
 382                 // Null pointer is a sentinel for link to the next block.
 383                 return (mPointer + 1)->block->mPointers->ptrInfo;
 384             }
 385             return mPointer->ptrInfo;
 386         }
 387         PRBool operator==(const Iterator& aOther) const
 388             { return mPointer == aOther.mPointer; }
 389         PRBool operator!=(const Iterator& aOther) const
 390             { return mPointer != aOther.mPointer; }
 391
 392     private:
 393         PtrInfoOrBlock *mPointer;
 394     };
 395
 396     class Builder;
 397     friend class Builder;
 398     class Builder {
 399     public:
 400         Builder(EdgePool &aPool)
 401             : mCurrent(&aPool.mSentinelAndBlocks[0]),
 402               mBlockEnd(&aPool.mSentinelAndBlocks[0]),
 403               mNextBlockPtr(&aPool.Blocks())
 404         {
 405         }
 406
 407         Iterator Mark() { return Iterator(mCurrent); }
 408
 409         void Add(PtrInfo* aEdge) {
 410             if (mCurrent == mBlockEnd) {
 411                 Block *b = new Block();
 412                 if (!b) {
 413                     // This means we just won't collect (some) cycles.
 414                     NS_NOTREACHED("out of memory, ignoring edges");
 415                     return;
 416                 }
 417                 *mNextBlockPtr = b;
 418                 mCurrent = b->Start();
 419                 mBlockEnd = b->End();
 420                 mNextBlockPtr = &b->Next();
 421             }
 422             (mCurrent++)->ptrInfo = aEdge;
 423         }
 424     private:
 425         // mBlockEnd points to space for null sentinel
 426         PtrInfoOrBlock *mCurrent, *mBlockEnd;
 427         Block **mNextBlockPtr;
 428     };
 429
 430 };
 431
 432 #ifdef DEBUG_CC
 433
 434 struct ReversedEdge {
 435     PtrInfo *mTarget;
 436     nsCString *mEdgeName;
 437     ReversedEdge *mNext;
 438 };
 439
 440 #endif
 441
 442
 443 enum NodeColor { black, white, grey };
 444
 445 // This structure should be kept as small as possible; we may expect
 446 // a million of them to be allocated and touched repeatedly during
 447 // each cycle collection.
 448
 449 struct PtrInfo
 450 {
 451     void *mPointer;
 452     nsCycleCollectionParticipant *mParticipant;
 453     PRUint32 mColor : 2;
 454     PRUint32 mInternalRefs : 30;
 455     PRUint32 mRefCount;
 456     EdgePool::Iterator mFirstChild; // first
 457     EdgePool::Iterator mLastChild; // one after last
 458
 459 #ifdef DEBUG_CC
 460     size_t mBytes;
 461     char *mName;
 462     PRUint32 mLangID;
 463
 464     // For finding roots in ExplainLiveExpectedGarbage (when there are
 465     // missing calls to suspect or failures to unlink).
 466     PRUint32 mSCCIndex; // strongly connected component
 467
 468     // For finding roots in ExplainLiveExpectedGarbage (when nodes
 469     // expected to be garbage are black).
 470     ReversedEdge* mReversedEdges; // linked list
 471     PtrInfo* mShortestPathToExpectedGarbage;
 472     nsCString* mShortestPathToExpectedGarbageEdgeName;
 473
 474     nsCStringArray mEdgeNames;
 475 #endif
 476
 477     PtrInfo(void *aPointer, nsCycleCollectionParticipant *aParticipant
 478             IF_DEBUG_CC_PARAM(PRUint32 aLangID)
 479             )
 480         : mPointer(aPointer),
 481           mParticipant(aParticipant),
 482           mColor(grey),
 483           mInternalRefs(0),
 484           mRefCount(0),
 485           mFirstChild(),
 486           mLastChild()
 487 #ifdef DEBUG_CC
 488         , mBytes(0),
 489           mName(nsnull),
 490           mLangID(aLangID),
 491           mSCCIndex(0),
 492           mReversedEdges(nsnull),
 493           mShortestPathToExpectedGarbage(nsnull),
 494           mShortestPathToExpectedGarbageEdgeName(nsnull)
 495 #endif
 496     {
 497     }
 498
 499 #ifdef DEBUG_CC
 500     void Destroy() {
 501         PL_strfree(mName);
 502         mEdgeNames.~nsCStringArray();
 503     }
 504 #endif
 505
 506     // Allow NodePool::Block's constructor to compile.
 507     PtrInfo() {
 508         NS_NOTREACHED("should never be called");
 509     }
 510 };
 511
 512 /**
 513  * A structure designed to be used like a linked list of PtrInfo, except
 514  * that allocates the PtrInfo 32K-at-a-time.
 515  */
 516 class NodePool
 517 {
 518 private:
 519     enum { BlockSize = 32 * 1024 }; // could be int template parameter
 520
 521     struct Block {
 522         // We create and destroy Block using NS_Alloc/NS_Free rather
 523         // than new and delete to avoid calling its constructor and
 524         // destructor.
 525         Block() { NS_NOTREACHED("should never be called"); }
 526         ~Block() { NS_NOTREACHED("should never be called"); }
 527
 528         Block* mNext;
 529         PtrInfo mEntries[BlockSize];
 530     };
 531
 532 public:
 533     NodePool()
 534         : mBlocks(nsnull),
 535           mLast(nsnull)
 536     {
 537     }
 538
 539     ~NodePool()
 540     {
 541         NS_ASSERTION(!mBlocks, "Didn't call Clear()?");
 542     }
 543
 544     void Clear()
 545     {
 546 #ifdef DEBUG_CC
 547         {
 548             Enumerator queue(*this);
 549             while (!queue.IsDone()) {
 550                 queue.GetNext()->Destroy();
 551             }
 552         }
 553 #endif
 554         Block *b = mBlocks;
 555         while (b) {
 556             Block *n = b->mNext;
 557             NS_Free(b);
 558             b = n;
 559         }
 560
 561         mBlocks = nsnull;
 562         mLast = nsnull;
 563     }
 564
 565     class Builder;
 566     friend class Builder;
 567     class Builder {
 568     public:
 569         Builder(NodePool& aPool)
 570             : mNextBlock(&aPool.mBlocks),
 571               mNext(aPool.mLast),
 572               mBlockEnd(nsnull)
 573         {
 574             NS_ASSERTION(aPool.mBlocks == nsnull && aPool.mLast == nsnull,
 575                          "pool not empty");
 576         }
 577         PtrInfo *Add(void *aPointer, nsCycleCollectionParticipant *aParticipant
 578                      IF_DEBUG_CC_PARAM(PRUint32 aLangID)
 579                     )
 580         {
 581             if (mNext == mBlockEnd) {
 582                 Block *block;
 583                 if (!(*mNextBlock = block =
 584                         static_cast<Block*>(NS_Alloc(sizeof(Block)))))
 585                     return nsnull;
 586                 mNext = block->mEntries;
 587                 mBlockEnd = block->mEntries + BlockSize;
 588                 block->mNext = nsnull;
 589                 mNextBlock = &block->mNext;
 590             }
 591             return new (mNext++) PtrInfo(aPointer, aParticipant
 592                                          IF_DEBUG_CC_PARAM(aLangID)
 593                                         );
 594         }
 595     private:
 596         Block **mNextBlock;
 597         PtrInfo *&mNext;
 598         PtrInfo *mBlockEnd;
 599     };
 600
 601     class Enumerator;
 602     friend class Enumerator;
 603     class Enumerator {
 604     public:
 605         Enumerator(NodePool& aPool)
 606             : mFirstBlock(aPool.mBlocks),
 607               mCurBlock(nsnull),
 608               mNext(nsnull),
 609               mBlockEnd(nsnull),
 610               mLast(aPool.mLast)
 611         {
 612         }
 613
 614         PRBool IsDone() const
 615         {
 616             return mNext == mLast;
 617         }
 618
 619         PtrInfo* GetNext()
 620         {
 621             NS_ASSERTION(!IsDone(), "calling GetNext when done");
 622             if (mNext == mBlockEnd) {
 623                 Block *nextBlock = mCurBlock ? mCurBlock->mNext : mFirstBlock;
 624                 mNext = nextBlock->mEntries;
 625                 mBlockEnd = mNext + BlockSize;
 626                 mCurBlock = nextBlock;
 627             }
 628             return mNext++;
 629         }
 630     private:
 631         Block *mFirstBlock, *mCurBlock;
 632         // mNext is the next value we want to return, unless mNext == mBlockEnd
 633         // NB: mLast is a reference to allow enumerating while building!
 634         PtrInfo *mNext, *mBlockEnd, *&mLast;
 635     };
 636
 637 private:
 638     Block *mBlocks;
 639     PtrInfo *mLast;
 640 };
 641
 642
 643 class GCGraphBuilder;
 644
 645 struct GCGraph
 646 {
 647     NodePool mNodes;
 648     EdgePool mEdges;
 649     PRUint32 mRootCount;
 650 #ifdef DEBUG_CC
 651     ReversedEdge *mReversedEdges;
 652 #endif
 653
 654     GCGraph() : mRootCount(0) {
 655     }
 656     ~GCGraph() {
 657     }
 658 };
 659
 660 // XXX Would be nice to have an nsHashSet<KeyType> API that has
 661 // Add/Remove/Has rather than PutEntry/RemoveEntry/GetEntry.
 662 typedef nsTHashtable<nsVoidPtrHashKey> PointerSet;
 663 typedef nsBaseHashtable<nsVoidPtrHashKey, PRUint32, PRUint32>
 664     PointerSetWithGeneration;
 665
 666 #ifdef DEBUG_CC
 667 static void
 668 WriteGraph(FILE *stream, GCGraph &graph, const void *redPtr);
 669 #endif
 670
 671 struct nsPurpleBuffer
 672 {
 673
 674 #define ASSOCIATIVITY 2
 675 #define INDEX_LOW_BIT 6
 676 #define N_INDEX_BITS 13
 677
 678 #define N_ENTRIES (1 << N_INDEX_BITS)
 679 #define N_POINTERS (N_ENTRIES * ASSOCIATIVITY)
 680 #define TOTAL_BYTES (N_POINTERS * PR_BYTES_PER_WORD)
 681 #define INDEX_MASK PR_BITMASK(N_INDEX_BITS)
 682 #define POINTER_INDEX(P) ((((PRUword)P) >> INDEX_LOW_BIT) & (INDEX_MASK))
 683
 684 #if (INDEX_LOW_BIT + N_INDEX_BITS > (8 * PR_BYTES_PER_WORD))
 685 #error "index bit overflow"
 686 #endif
 687
 688     // This class serves as a generational wrapper around a pldhash
 689     // table: a subset of generation zero lives in mCache, the
 690     // remainder spill into the mBackingStore hashtable. The idea is
 691     // to get a higher hit rate and greater locality of reference for
 692     // generation zero, in which the vast majority of suspect/forget
 693     // calls annihilate one another.
 694
 695     nsCycleCollectorParams &mParams;
 696 #ifdef DEBUG_CC
 697     nsCycleCollectorStats &mStats;
 698 #endif
 699     void* mCache[N_POINTERS];
 700     PRUint32 mCurrGen;
 701     PointerSetWithGeneration mBackingStore;
 702
 703 #ifdef DEBUG_CC
 704     nsPurpleBuffer(nsCycleCollectorParams &params,
 705                    nsCycleCollectorStats &stats)
 706         : mParams(params),
 707           mStats(stats),
 708           mCurrGen(0)
 709     {
 710         Init();
 711     }
 712 #else
 713     nsPurpleBuffer(nsCycleCollectorParams &params)
 714         : mParams(params),
 715           mCurrGen(0)
 716     {
 717         Init();
 718     }
 719 #endif
 720
 721     ~nsPurpleBuffer()
 722     {
 723         memset(mCache, 0, sizeof(mCache));
 724         mBackingStore.Clear();
 725     }
 726
 727     void Init()
 728     {
 729         memset(mCache, 0, sizeof(mCache));
 730         mBackingStore.Init();
 731     }
 732
 733     void BumpGeneration();
 734     void SelectAgedPointers(GCGraphBuilder &builder);
 735
 736     PRBool Exists(void *p)
 737     {
 738         PRUint32 idx = POINTER_INDEX(p);
 739         for (PRUint32 i = 0; i < ASSOCIATIVITY; ++i) {
 740             if (mCache[idx+i] == p)
 741                 return PR_TRUE;
 742         }
 743         PRUint32 gen;
 744         return mBackingStore.Get(p, &gen);
 745     }
 746
 747     void Put(void *p)
 748     {
 749         PRUint32 idx = POINTER_INDEX(p);
 750         for (PRUint32 i = 0; i < ASSOCIATIVITY; ++i) {
 751             if (!mCache[idx+i]) {
 752                 mCache[idx+i] = p;
 753                 return;
 754             }
 755         }
 756 #ifdef DEBUG_CC
 757         mStats.mSpills++;
 758 #endif
 759         SpillOne(p);
 760     }
 761
 762     void Remove(void *p)
 763     {
 764         PRUint32 idx = POINTER_INDEX(p);
 765         for (PRUint32 i = 0; i < ASSOCIATIVITY; ++i) {
 766             if (mCache[idx+i] == p) {
 767                 mCache[idx+i] = (void*)0;
 768                 return;
 769             }
 770         }
 771         mBackingStore.Remove(p);
 772     }
 773
 774     void SpillOne(void* &p)
 775     {
 776         mBackingStore.Put(p, mCurrGen);
 777         p = (void*)0;
 778     }
 779
 780     void SpillAll()
 781     {
 782         for (PRUint32 i = 0; i < N_POINTERS; ++i) {
 783             if (mCache[i]) {
 784                 SpillOne(mCache[i]);
 785             }
 786         }
 787     }
 788
 789     PRUint32 Count()
 790     {
 791         PRUint32 count = mBackingStore.Count();
 792         for (PRUint32 i = 0; i < N_POINTERS; ++i) {
 793             if (mCache[i]) {
 794                 ++count;
 795             }
 796         }
 797         return count;
 798     }
 799 };
 800
 801 static PLDHashOperator
 802 zeroGenerationCallback(const void*  ptr,
 803                        PRUint32&    generation,
 804                        void*        userArg)
 805 {
 806 #ifdef DEBUG_CC
 807     nsPurpleBuffer *purp = static_cast<nsPurpleBuffer*>(userArg);
 808     purp->mStats.mZeroGeneration++;
 809 #endif
 810     generation = 0;
 811     return PL_DHASH_NEXT;
 812 }
 813
 814 void nsPurpleBuffer::BumpGeneration()
 815 {
 816     SpillAll();
 817     if (mCurrGen == 0xffffffff) {
 818         mBackingStore.Enumerate(zeroGenerationCallback, this);
 819         mCurrGen = 0;
 820     } else {
 821         ++mCurrGen;
 822     }
 823 #ifdef DEBUG_CC
 824     mStats.mBumpGeneration++;
 825 #endif
 826 }
 827
 828 static inline PRBool
 829 SufficientlyAged(PRUint32 generation, nsPurpleBuffer *p)
 830 {
 831     return generation + p->mParams.mScanDelay < p->mCurrGen;
 832 }
 833
 834 struct CallbackClosure
 835 {
 836     CallbackClosure(nsPurpleBuffer *aPurpleBuffer, GCGraphBuilder &aBuilder)
 837         : mPurpleBuffer(aPurpleBuffer),
 838           mBuilder(aBuilder)
 839     {
 840     }
 841     nsPurpleBuffer *mPurpleBuffer;
 842     GCGraphBuilder &mBuilder;
 843 };
 844
 845 static PRBool
 846 AddPurpleRoot(GCGraphBuilder &builder, nsISupports *root);
 847
 848 static PLDHashOperator
 849 ageSelectionCallback(const void*  ptr,
 850                      PRUint32&    generation,
 851                      void*        userArg)
 852 {
 853     CallbackClosure *closure = static_cast<CallbackClosure*>(userArg);
 854     if (SufficientlyAged(generation, closure->mPurpleBuffer) &&
 855         AddPurpleRoot(closure->mBuilder,
 856                       static_cast<nsISupports *>(const_cast<void*>(ptr))))
 857         return PL_DHASH_REMOVE;
 858
 859     return PL_DHASH_NEXT;
 860 }
 861
 862 void
 863 nsPurpleBuffer::SelectAgedPointers(GCGraphBuilder &aBuilder)
 864 {
 865     // Rely on our caller having done a BumpGeneration first, which in
 866     // turn calls SpillAll.
 867     CallbackClosure closure(this, aBuilder);
 868     mBackingStore.Enumerate(ageSelectionCallback, &closure);
 869 }
 870
 871
 872
 873 ////////////////////////////////////////////////////////////////////////
 874 // Implement the LanguageRuntime interface for C++/XPCOM
 875 ////////////////////////////////////////////////////////////////////////
 876
 877
 878 struct nsCycleCollectionXPCOMRuntime :
 879     public nsCycleCollectionLanguageRuntime
 880 {
 881     nsresult BeginCycleCollection(nsCycleCollectionTraversalCallback &cb)
 882     {
 883         return NS_OK;
 884     }
 885
 886     nsresult FinishCycleCollection()
 887     {
 888         return NS_OK;
 889     }
 890
 891     inline nsCycleCollectionParticipant *ToParticipant(void *p);
 892
 893 #ifdef DEBUG_CC
 894     virtual void PrintAllReferencesTo(void *p) {}
 895 #endif
 896 };
 897
 898 struct nsCycleCollector
 899 {
 900     PRBool mCollectionInProgress;
 901     PRBool mScanInProgress;
 902     PRBool mFollowupCollection;
 903     PRUint32 mCollectedObjects;
 904
 905     nsCycleCollectionLanguageRuntime *mRuntimes[nsIProgrammingLanguage::MAX+1];
 906     nsCycleCollectionXPCOMRuntime mXPCOMRuntime;
 907
 908     GCGraph mGraph;
 909
 910     nsCycleCollectorParams mParams;
 911
 912     nsTPtrArray<PtrInfo> *mWhiteNodes;
 913     PRUint32 mWhiteNodeCount;
 914
 915     nsPurpleBuffer mPurpleBuf;
 916
 917     void RegisterRuntime(PRUint32 langID,
 918                          nsCycleCollectionLanguageRuntime *rt);
 919     void ForgetRuntime(PRUint32 langID);
 920
 921     void SelectPurple(GCGraphBuilder &builder);
 922     void MarkRoots(GCGraphBuilder &builder);
 923     void ScanRoots();
 924     void RootWhite();
 925     PRBool CollectWhite(); // returns whether anything was collected
 926
 927     nsCycleCollector();
 928     ~nsCycleCollector();
 929
 930     PRBool Suspect(nsISupports *n);
 931     PRBool Forget(nsISupports *n);
 932     PRUint32 Collect(PRUint32 aTryCollections = 1);
 933     PRBool BeginCollection();
 934     PRBool FinishCollection();
 935     PRUint32 SuspectedCount();
 936     void Shutdown();
 937
 938     void ClearGraph()
 939     {
 940         mGraph.mNodes.Clear();
 941         mGraph.mEdges.Clear();
 942         mGraph.mRootCount = 0;
 943     }
 944
 945 #ifdef DEBUG_CC
 946     nsCycleCollectorStats mStats;
 947
 948     FILE *mPtrLog;
 949
 950     void MaybeDrawGraphs();
 951     void Allocated(void *n, size_t sz);
 952     void Freed(void *n);
 953
 954     void ExplainLiveExpectedGarbage();
 955     PRBool CreateReversedEdges();
 956     void DestroyReversedEdges();
 957     void ShouldBeFreed(nsISupports *n);
 958     void WasFreed(nsISupports *n);
 959     PointerSet mExpectedGarbage;
 960 #endif
 961 };
 962
 963
 964 class GraphWalker
 965 {
 966 private:
 967     void DoWalk(nsDeque &aQueue);
 968
 969 public:
 970     void Walk(PtrInfo *s0);
 971     void WalkFromRoots(GCGraph &aGraph);
 972
 973     // Provided by concrete walker subtypes.
 974     virtual PRBool ShouldVisitNode(PtrInfo const *pi) = 0;
 975     virtual void VisitNode(PtrInfo *pi) = 0;
 976 };
 977
 978
 979 ////////////////////////////////////////////////////////////////////////
 980 // The static collector object
 981 ////////////////////////////////////////////////////////////////////////
 982
 983
 984 static nsCycleCollector *sCollector = nsnull;
 985
 986
 987 ////////////////////////////////////////////////////////////////////////
 988 // Utility functions
 989 ////////////////////////////////////////////////////////////////////////
 990
 991 class CCRunnableFaultReport : public nsRunnable {
 992 public:
 993     CCRunnableFaultReport(const nsCString& report)
 994     {
 995         CopyUTF8toUTF16(report, mReport);
 996     }
 997
 998     NS_IMETHOD Run() {
 999         nsCOMPtr<nsIObserverService> obs =
1000             do_GetService(NS_OBSERVERSERVICE_CONTRACTID);
1001         if (obs) {
1002             obs->NotifyObservers(nsnull, "cycle-collector-fault",
1003                                  mReport.get());
1004         }
1005
1006         nsCOMPtr<nsIConsoleService> cons =
1007             do_GetService(NS_CONSOLESERVICE_CONTRACTID);
1008         if (cons) {
1009             cons->LogStringMessage(mReport.get());
1010         }
1011         return NS_OK;
1012     }
1013
1014 private:
1015     nsString mReport;
1016 };
1017
1018 static void
1019 Fault(const char *msg, const void *ptr=nsnull)
1020 {
1021 #ifdef DEBUG_CC
1022     // This should be nearly impossible, but just in case.
1023     if (!sCollector)
1024         return;
1025
1026     if (sCollector->mParams.mFaultIsFatal) {
1027
1028         if (ptr)
1029             printf("Fatal fault in cycle collector: %s (ptr: %p)\n", msg, ptr);
1030         else
1031             printf("Fatal fault in cycle collector: %s\n", msg);
1032
1033
1034         if (sCollector->mGraph.mRootCount > 0) {
1035             FILE *stream;
1036 #ifdef WIN32
1037             const char fname[] = "c:\\fault-graph.dot";
1038 #else
1039             const char fname[] = "/tmp/fault-graph.dot";
1040 #endif
1041             printf("depositing faulting cycle-collection graph in %s\n", fname);
1042             stream = fopen(fname, "w+");
1043             WriteGraph(stream, sCollector->mGraph, ptr);
1044             fclose(stream);
1045         }
1046
1047         exit(1);
1048     }
1049 #endif
1050
1051     nsPrintfCString str(256, "Fault in cycle collector: %s (ptr: %p)\n",
1052                         msg, ptr);
1053     NS_NOTREACHED(str.get());
1054
1055     // When faults are not fatal, we assume we're running in a
1056     // production environment and we therefore want to disable the
1057     // collector on a fault. This will unfortunately cause the browser
1058     // to leak pretty fast wherever creates cyclical garbage, but it's
1059     // probably a better user experience than crashing. Besides, we
1060     // *should* never hit a fault.
1061
1062     sCollector->mParams.mDoNothing = PR_TRUE;
1063
1064     // Report to observers off an event so we don't run JS under GC
1065     // (which is where we might be right now).
1066     nsCOMPtr<nsIRunnable> ev = new CCRunnableFaultReport(str);
1067     NS_DispatchToCurrentThread(ev);
1068 }
1069
1070 #ifdef DEBUG_CC
1071 static void
1072 Fault(const char *msg, PtrInfo *pi)
1073 {
1074     printf("Fault in cycle collector: %s\n"
1075            "  while operating on pointer %p %s\n",
1076            msg, pi->mPointer, pi->mName);
1077     if (pi->mInternalRefs) {
1078         printf("  which has internal references from:\n");
1079         NodePool::Enumerator queue(sCollector->mGraph.mNodes);
1080         while (!queue.IsDone()) {
1081             PtrInfo *ppi = queue.GetNext();
1082             for (EdgePool::Iterator e = ppi->mFirstChild, e_end = ppi->mLastChild;
1083                  e != e_end; ++e) {
1084                 if (*e == pi) {
1085                     printf("    %p %s\n", ppi->mPointer, ppi->mName);
1086                 }
1087             }
1088         }
1089     }
1090
1091     Fault(msg, pi->mPointer);
1092 }
1093 #else
1094 inline void
1095 Fault(const char *msg, PtrInfo *pi)
1096 {
1097     Fault(msg, pi->mPointer);
1098 }
1099 #endif
1100
1101
1102
1103 static nsISupports *
1104 canonicalize(nsISupports *in)
1105 {
1106     nsCOMPtr<nsISupports> child;
1107     in->QueryInterface(NS_GET_IID(nsCycleCollectionISupports),
1108                        getter_AddRefs(child));
1109     return child.get();
1110 }
1111
1112 static inline void
1113 ToParticipant(nsISupports *s, nsXPCOMCycleCollectionParticipant **cp)
1114 {
1115     // We use QI to move from an nsISupports to an
1116     // nsXPCOMCycleCollectionParticipant, which is a per-class singleton helper
1117     // object that implements traversal and unlinking logic for the nsISupports
1118     // in question.
1119     CallQueryInterface(s, cp);
1120 #ifdef DEBUG_CC
1121     if (cp)
1122         ++sCollector->mStats.mSuccessfulQI;
1123     else
1124         ++sCollector->mStats.mFailedQI;
1125 #endif
1126 }
1127
1128 nsCycleCollectionParticipant *
1129 nsCycleCollectionXPCOMRuntime::ToParticipant(void *p)
1130 {
1131     nsXPCOMCycleCollectionParticipant *cp;
1132     ::ToParticipant(static_cast<nsISupports*>(p), &cp);
1133     return cp;
1134 }
1135
1136
1137 void
1138 GraphWalker::Walk(PtrInfo *s0)
1139 {
1140     nsDeque queue;
1141     queue.Push(s0);
1142     DoWalk(queue);
1143 }
1144
1145 void
1146 GraphWalker::WalkFromRoots(GCGraph& aGraph)
1147 {
1148     nsDeque queue;
1149     NodePool::Enumerator etor(aGraph.mNodes);
1150     for (PRUint32 i = 0; i < aGraph.mRootCount; ++i) {
1151         queue.Push(etor.GetNext());
1152     }
1153     DoWalk(queue);
1154 }
1155
1156 void
1157 GraphWalker::DoWalk(nsDeque &aQueue)
1158 {
1159     // Use a aQueue to match the breadth-first traversal used when we
1160     // built the graph, for hopefully-better locality.
1161     while (aQueue.GetSize() > 0) {
1162         PtrInfo *pi = static_cast<PtrInfo*>(aQueue.PopFront());
1163
1164         if (this->ShouldVisitNode(pi)) {
1165             this->VisitNode(pi);
1166             for (EdgePool::Iterator child = pi->mFirstChild,
1167                                 child_end = pi->mLastChild;
1168                  child != child_end; ++child) {
1169                 aQueue.Push(*child);
1170             }
1171         }
1172     };
1173
1174 #ifdef DEBUG_CC
1175     sCollector->mStats.mWalkedGraph++;
1176 #endif
1177 }
1178
1179
1180 ////////////////////////////////////////////////////////////////////////
1181 // Bacon & Rajan's |MarkRoots| routine.
1182 ////////////////////////////////////////////////////////////////////////
1183
1184 struct PtrToNodeEntry : public PLDHashEntryHdr
1185 {
1186     // The key is mNode->mPointer
1187     PtrInfo *mNode;
1188 };
1189
1190 static PRBool
1191 PtrToNodeMatchEntry(PLDHashTable *table,
1192                     const PLDHashEntryHdr *entry,
1193                     const void *key)
1194 {
1195     const PtrToNodeEntry *n = static_cast<const PtrToNodeEntry*>(entry);
1196     return n->mNode->mPointer == key;
1197 }
1198
1199 static PLDHashTableOps PtrNodeOps = {
1200     PL_DHashAllocTable,
1201     PL_DHashFreeTable,
1202     PL_DHashVoidPtrKeyStub,
1203     PtrToNodeMatchEntry,
1204     PL_DHashMoveEntryStub,
1205     PL_DHashClearEntryStub,
1206     PL_DHashFinalizeStub,
1207     nsnull
1208 };
1209
1210 class GCGraphBuilder : public nsCycleCollectionTraversalCallback
1211 {
1212 private:
1213     NodePool::Builder mNodeBuilder;
1214     EdgePool::Builder mEdgeBuilder;
1215     PLDHashTable mPtrToNodeMap;
1216     PtrInfo *mCurrPi;
1217     nsCycleCollectionLanguageRuntime **mRuntimes; // weak, from nsCycleCollector
1218 #ifdef DEBUG_CC
1219     nsCString mNextEdgeName;
1220 #endif
1221
1222 public:
1223     GCGraphBuilder(GCGraph &aGraph,
1224                    nsCycleCollectionLanguageRuntime **aRuntimes);
1225     ~GCGraphBuilder();
1226
1227     PRUint32 Count() const { return mPtrToNodeMap.entryCount; }
1228
1229 #ifdef DEBUG_CC
1230     PtrInfo* AddNode(void *s, nsCycleCollectionParticipant *aParticipant,
1231                      PRUint32 aLangID);
1232 #else
1233     PtrInfo* AddNode(void *s, nsCycleCollectionParticipant *aParticipant);
1234     PtrInfo* AddNode(void *s, nsCycleCollectionParticipant *aParticipant,
1235                      PRUint32 aLangID)
1236     {
1237         return AddNode(s, aParticipant);
1238     }
1239 #endif
1240     void Traverse(PtrInfo* aPtrInfo);
1241
1242     // nsCycleCollectionTraversalCallback methods.
1243     NS_IMETHOD_(void) NoteXPCOMRoot(nsISupports *root);
1244
1245 private:
1246 #ifdef DEBUG_CC
1247     NS_IMETHOD_(void) DescribeNode(CCNodeType type, nsrefcnt refCount,
1248                                    size_t objSz, const char *objName);
1249 #else
1250     NS_IMETHOD_(void) DescribeNode(CCNodeType type, nsrefcnt refCount);
1251 #endif
1252     NS_IMETHOD_(void) NoteRoot(PRUint32 langID, void *child,
1253                                nsCycleCollectionParticipant* participant);
1254     NS_IMETHOD_(void) NoteXPCOMChild(nsISupports *child);
1255     NS_IMETHOD_(void) NoteNativeChild(void *child,
1256                                      nsCycleCollectionParticipant *participant);
1257     NS_IMETHOD_(void) NoteScriptChild(PRUint32 langID, void *child);
1258 #ifdef DEBUG_CC
1259     NS_IMETHOD_(void) NoteNextEdgeName(const char* name);
1260 #endif
1261 };
1262
1263 GCGraphBuilder::GCGraphBuilder(GCGraph &aGraph,
1264                                nsCycleCollectionLanguageRuntime **aRuntimes)
1265     : mNodeBuilder(aGraph.mNodes),
1266       mEdgeBuilder(aGraph.mEdges),
1267       mRuntimes(aRuntimes)
1268 {
1269     if (!PL_DHashTableInit(&mPtrToNodeMap, &PtrNodeOps, nsnull,
1270                            sizeof(PtrToNodeEntry), 32768))
1271         mPtrToNodeMap.ops = nsnull;
1272 }
1273
1274 GCGraphBuilder::~GCGraphBuilder()
1275 {
1276     if (mPtrToNodeMap.ops)
1277         PL_DHashTableFinish(&mPtrToNodeMap);
1278 }
1279
1280 PtrInfo*
1281 GCGraphBuilder::AddNode(void *s, nsCycleCollectionParticipant *aParticipant
1282                         IF_DEBUG_CC_PARAM(PRUint32 aLangID)
1283                        )
1284 {
1285     PtrToNodeEntry *e = static_cast<PtrToNodeEntry*>(PL_DHashTableOperate(&mPtrToNodeMap, s, PL_DHASH_ADD));
1286     PtrInfo *result;
1287     if (!e->mNode) {
1288         // New entry.
1289         result = mNodeBuilder.Add(s, aParticipant
1290                                   IF_DEBUG_CC_PARAM(aLangID)
1291                                  );
1292         if (!result) {
1293             PL_DHashTableRawRemove(&mPtrToNodeMap, e);
1294             return nsnull;
1295         }
1296         e->mNode = result;
1297     } else {
1298         result = e->mNode;
1299         NS_ASSERTION(result->mParticipant == aParticipant,
1300                      "nsCycleCollectionParticipant shouldn't change!");
1301     }
1302     return result;
1303 }
1304
1305 void
1306 GCGraphBuilder::Traverse(PtrInfo* aPtrInfo)
1307 {
1308     mCurrPi = aPtrInfo;
1309
1310 #ifdef DEBUG_CC
1311     if (!mCurrPi->mParticipant) {
1312         Fault("unknown pointer during walk", aPtrInfo);
1313         return;
1314     }
1315 #endif
1316
1317     mCurrPi->mFirstChild = mEdgeBuilder.Mark();
1318
1319     nsresult rv = aPtrInfo->mParticipant->Traverse(aPtrInfo->mPointer, *this);
1320     if (NS_FAILED(rv)) {
1321         Fault("script pointer traversal failed", aPtrInfo);
1322     }
1323
1324     mCurrPi->mLastChild = mEdgeBuilder.Mark();
1325 }
1326
1327 NS_IMETHODIMP_(void)
1328 GCGraphBuilder::NoteXPCOMRoot(nsISupports *root)
1329 {
1330     root = canonicalize(root);
1331     NS_ASSERTION(root,
1332                  "Don't add objects that don't participate in collection!");
1333
1334 #ifdef DEBUG_CC
1335     if (nsCycleCollector_shouldSuppress(root))
1336         return;
1337 #endif
1338
1339     nsXPCOMCycleCollectionParticipant *cp;
1340     ToParticipant(root, &cp);
1341
1342     NoteRoot(nsIProgrammingLanguage::CPLUSPLUS, root, cp);
1343 }
1344
1345
1346 NS_IMETHODIMP_(void)
1347 GCGraphBuilder::NoteRoot(PRUint32 langID, void *root,
1348                          nsCycleCollectionParticipant* participant)
1349 {
1350     NS_ASSERTION(root, "Don't add a null root!");
1351
1352     if (langID > nsIProgrammingLanguage::MAX || !mRuntimes[langID]) {
1353         Fault("adding root for unregistered language", root);
1354         return;
1355     }
1356
1357     AddNode(root, participant, langID);
1358 }
1359
1360 NS_IMETHODIMP_(void)
1361 #ifdef DEBUG_CC
1362 GCGraphBuilder::DescribeNode(CCNodeType type, nsrefcnt refCount,
1363                              size_t objSz, const char *objName)
1364 #else
1365 GCGraphBuilder::DescribeNode(CCNodeType type, nsrefcnt refCount)
1366 #endif
1367 {
1368 #ifdef DEBUG_CC
1369     mCurrPi->mBytes = objSz;
1370     mCurrPi->mName = PL_strdup(objName);
1371 #endif
1372
1373     if (type == RefCounted) {
1374         if (refCount == 0 || refCount == PR_UINT32_MAX)
1375             Fault("zero or overflowing refcount", mCurrPi);
1376
1377         mCurrPi->mRefCount = refCount;
1378     }
1379     else {
1380         mCurrPi->mRefCount = type == GCMarked ? PR_UINT32_MAX : 0;
1381     }
1382 #ifdef DEBUG_CC
1383     sCollector->mStats.mVisitedNode++;
1384 #endif
1385 }
1386
1387 NS_IMETHODIMP_(void)
1388 GCGraphBuilder::NoteXPCOMChild(nsISupports *child)
1389 {
1390 #ifdef DEBUG_CC
1391     nsCString edgeName(mNextEdgeName);
1392     mNextEdgeName.Truncate();
1393 #endif
1394     if (!child || !(child = canonicalize(child)))
1395         return;
1396
1397 #ifdef DEBUG_CC
1398     if (nsCycleCollector_shouldSuppress(child))
1399         return;
1400 #endif
1401
1402     nsXPCOMCycleCollectionParticipant *cp;
1403     ToParticipant(child, &cp);
1404     if (cp) {
1405         PtrInfo *childPi = AddNode(child, cp, nsIProgrammingLanguage::CPLUSPLUS);
1406         if (!childPi)
1407             return;
1408         mEdgeBuilder.Add(childPi);
1409 #ifdef DEBUG_CC
1410         mCurrPi->mEdgeNames.AppendCString(edgeName);
1411 #endif
1412         ++childPi->mInternalRefs;
1413     }
1414 }
1415
1416 NS_IMETHODIMP_(void)
1417 GCGraphBuilder::NoteNativeChild(void *child,
1418                                 nsCycleCollectionParticipant *participant)
1419 {
1420 #ifdef DEBUG_CC
1421     nsCString edgeName(mNextEdgeName);
1422     mNextEdgeName.Truncate();
1423 #endif
1424     if (!child)
1425         return;
1426
1427     NS_ASSERTION(participant, "Need a nsCycleCollectionParticipant!");
1428
1429     PtrInfo *childPi = AddNode(child, participant, nsIProgrammingLanguage::CPLUSPLUS);
1430     if (!childPi)
1431         return;
1432     mEdgeBuilder.Add(childPi);
1433 #ifdef DEBUG_CC
1434     mCurrPi->mEdgeNames.AppendCString(edgeName);
1435 #endif
1436     ++childPi->mInternalRefs;
1437 }
1438
1439 NS_IMETHODIMP_(void)
1440 GCGraphBuilder::NoteScriptChild(PRUint32 langID, void *child)
1441 {
1442 #ifdef DEBUG_CC
1443     nsCString edgeName(mNextEdgeName);
1444     mNextEdgeName.Truncate();
1445 #endif
1446     if (!child)
1447         return;
1448
1449     if (langID > nsIProgrammingLanguage::MAX) {
1450         Fault("traversing pointer for unknown language", child);
1451         return;
1452     }
1453
1454     if (!mRuntimes[langID]) {
1455         NS_WARNING("Not collecting cycles involving objects for scripting "
1456                    "languages that don't participate in cycle collection.");
1457         return;
1458     }
1459
1460     nsCycleCollectionParticipant *cp = mRuntimes[langID]->ToParticipant(child);
1461     if (!cp)
1462         return;
1463
1464     PtrInfo *childPi = AddNode(child, cp, langID);
1465     if (!childPi)
1466         return;
1467     mEdgeBuilder.Add(childPi);
1468 #ifdef DEBUG_CC
1469     mCurrPi->mEdgeNames.AppendCString(edgeName);
1470 #endif
1471     ++childPi->mInternalRefs;
1472 }
1473
1474 #ifdef DEBUG_CC
1475 NS_IMETHODIMP_(void)
1476 GCGraphBuilder::NoteNextEdgeName(const char* name)
1477 {
1478     mNextEdgeName = name;
1479 }
1480 #endif
1481
1482 static PRBool
1483 AddPurpleRoot(GCGraphBuilder &builder, nsISupports *root)
1484 {
1485     root = canonicalize(root);
1486     NS_ASSERTION(root,
1487                  "Don't add objects that don't participate in collection!");
1488
1489     nsXPCOMCycleCollectionParticipant *cp;
1490     ToParticipant(root, &cp);
1491
1492     PtrInfo *pinfo = builder.AddNode(root, cp,
1493                                      nsIProgrammingLanguage::CPLUSPLUS);
1494     if (!pinfo) {
1495         return PR_FALSE;
1496     }
1497
1498     cp->UnmarkPurple(root);
1499
1500     return PR_TRUE;
1501 }
1502
1503 void
1504 nsCycleCollector::SelectPurple(GCGraphBuilder &builder)
1505 {
1506     mPurpleBuf.BumpGeneration();
1507     mPurpleBuf.SelectAgedPointers(builder);
1508 }
1509
1510 void
1511 nsCycleCollector::MarkRoots(GCGraphBuilder &builder)
1512 {
1513     mGraph.mRootCount = builder.Count();
1514
1515     // read the PtrInfo out of the graph that we are building
1516     NodePool::Enumerator queue(mGraph.mNodes);
1517     while (!queue.IsDone()) {
1518         PtrInfo *pi = queue.GetNext();
1519         builder.Traverse(pi);
1520     }
1521 }
1522
1523
1524 ////////////////////////////////////////////////////////////////////////
1525 // Bacon & Rajan's |ScanRoots| routine.
1526 ////////////////////////////////////////////////////////////////////////
1527
1528
1529 struct ScanBlackWalker : public GraphWalker
1530 {
1531     ScanBlackWalker(PRUint32 &aWhiteNodeCount) : mWhiteNodeCount(aWhiteNodeCount)
1532     {
1533     }
1534
1535     PRBool ShouldVisitNode(PtrInfo const *pi)
1536     {
1537         return pi->mColor != black;
1538     }
1539
1540     void VisitNode(PtrInfo *pi)
1541     {
1542         if (pi->mColor == white)
1543             --mWhiteNodeCount;
1544         pi->mColor = black;
1545 #ifdef DEBUG_CC
1546         sCollector->mStats.mSetColorBlack++;
1547 #endif
1548     }
1549
1550     PRUint32 &mWhiteNodeCount;
1551 };
1552
1553
1554 struct scanWalker : public GraphWalker
1555 {
1556     scanWalker(PRUint32 &aWhiteNodeCount) : mWhiteNodeCount(aWhiteNodeCount)
1557     {
1558     }
1559
1560     PRBool ShouldVisitNode(PtrInfo const *pi)
1561     {
1562         return pi->mColor == grey;
1563     }
1564
1565     void VisitNode(PtrInfo *pi)
1566     {
1567         if (pi->mInternalRefs > pi->mRefCount && pi->mRefCount > 0)
1568             Fault("traversed refs exceed refcount", pi);
1569
1570         if (pi->mInternalRefs == pi->mRefCount || pi->mRefCount == 0) {
1571             pi->mColor = white;
1572             ++mWhiteNodeCount;
1573 #ifdef DEBUG_CC
1574             sCollector->mStats.mSetColorWhite++;
1575 #endif
1576         } else {
1577             ScanBlackWalker(mWhiteNodeCount).Walk(pi);
1578             NS_ASSERTION(pi->mColor == black,
1579                          "Why didn't ScanBlackWalker make pi black?");
1580         }
1581     }
1582
1583     PRUint32 &mWhiteNodeCount;
1584 };
1585
1586 void
1587 nsCycleCollector::ScanRoots()
1588 {
1589     mWhiteNodeCount = 0;
1590
1591     // On the assumption that most nodes will be black, it's
1592     // probably faster to use a GraphWalker than a
1593     // NodePool::Enumerator.
1594     scanWalker(mWhiteNodeCount).WalkFromRoots(mGraph);
1595
1596 #ifdef DEBUG_CC
1597     // Sanity check: scan should have colored all grey nodes black or
1598     // white. So we ensure we have no grey nodes at this point.
1599     NodePool::Enumerator etor(mGraph.mNodes);
1600     while (!etor.IsDone())
1601     {
1602         PtrInfo *pinfo = etor.GetNext();
1603         if (pinfo->mColor == grey) {
1604             Fault("valid grey node after scanning", pinfo);
1605         }
1606     }
1607 #endif
1608 }
1609
1610
1611 ////////////////////////////////////////////////////////////////////////
1612 // Bacon & Rajan's |CollectWhite| routine, somewhat modified.
1613 ////////////////////////////////////////////////////////////////////////
1614
1615 void
1616 nsCycleCollector::RootWhite()
1617 {
1618     // Explanation of "somewhat modified": we have no way to collect the
1619     // set of whites "all at once", we have to ask each of them to drop
1620     // their outgoing links and assume this will cause the garbage cycle
1621     // to *mostly* self-destruct (except for the reference we continue
1622     // to hold).
1623     //
1624     // To do this "safely" we must make sure that the white nodes we're
1625     // operating on are stable for the duration of our operation. So we
1626     // make 3 sets of calls to language runtimes:
1627     //
1628     //   - Root(whites), which should pin the whites in memory.
1629     //   - Unlink(whites), which drops outgoing links on each white.
1630     //   - Unroot(whites), which returns the whites to normal GC.
1631
1632     nsresult rv;
1633
1634     NS_ASSERTION(mWhiteNodes->IsEmpty(),
1635                  "FinishCollection wasn't called?");
1636
1637     mWhiteNodes->SetCapacity(mWhiteNodeCount);
1638
1639     NodePool::Enumerator etor(mGraph.mNodes);
1640     while (!etor.IsDone())
1641     {
1642         PtrInfo *pinfo = etor.GetNext();
1643         if (pinfo->mColor == white && mWhiteNodes->AppendElement(pinfo)) {
1644             rv = pinfo->mParticipant->RootAndUnlinkJSObjects(pinfo->mPointer);
1645             if (NS_FAILED(rv)) {
1646                 Fault("Failed root call while unlinking", pinfo);
1647                 mWhiteNodes->RemoveElementAt(mWhiteNodes->Length() - 1);
1648             }
1649         }
1650     }
1651 }
1652
1653 PRBool
1654 nsCycleCollector::CollectWhite()
1655 {
1656     nsresult rv;
1657
1658 #if defined(DEBUG_CC) && !defined(__MINGW32__) && defined(WIN32)
1659     struct _CrtMemState ms1, ms2;
1660     _CrtMemCheckpoint(&ms1);
1661 #endif
1662
1663     PRUint32 i, count = mWhiteNodes->Length();
1664     for (i = 0; i < count; ++i) {
1665         PtrInfo *pinfo = mWhiteNodes->ElementAt(i);
1666         rv = pinfo->mParticipant->Unlink(pinfo->mPointer);
1667         if (NS_FAILED(rv)) {
1668             Fault("Failed unlink call while unlinking", pinfo);
1669 #ifdef DEBUG_CC
1670             mStats.mFailedUnlink++;
1671 #endif
1672         }
1673         else {
1674 #ifdef DEBUG_CC
1675             ++mStats.mCollectedNode;
1676 #endif
1677         }
1678     }
1679
1680     for (i = 0; i < count; ++i) {
1681         PtrInfo *pinfo = mWhiteNodes->ElementAt(i);
1682         rv = pinfo->mParticipant->Unroot(pinfo->mPointer);
1683         if (NS_FAILED(rv))
1684             Fault("Failed unroot call while unlinking", pinfo);
1685     }
1686
1687 #if defined(DEBUG_CC) && !defined(__MINGW32__) && defined(WIN32)
1688     _CrtMemCheckpoint(&ms2);
1689     if (ms2.lTotalCount < ms1.lTotalCount)
1690         mStats.mFreedBytes += (ms1.lTotalCount - ms2.lTotalCount);
1691 #endif
1692
1693     mCollectedObjects += count;
1694     return count > 0;
1695 }
1696
1697
1698 #ifdef DEBUG_CC
1699 ////////////////////////////////////////////////////////////////////////
1700 // Memory-hooking stuff
1701 // When debugging wild pointers, it sometimes helps to hook malloc and
1702 // free. This stuff is disabled unless you set an environment variable.
1703 ////////////////////////////////////////////////////////////////////////
1704
1705 static PRBool hookedMalloc = PR_FALSE;
1706
1707 #if defined(__GLIBC__) && !defined(__UCLIBC__)
1708 #include <malloc.h>
1709
1710 static void* (*old_memalign_hook)(size_t, size_t, const void *);
1711 static void* (*old_realloc_hook)(void *, size_t, const void *);
1712 static void* (*old_malloc_hook)(size_t, const void *);
1713 static void (*old_free_hook)(void *, const void *);
1714
1715 static void* my_memalign_hook(size_t, size_t, const void *);
1716 static void* my_realloc_hook(void *, size_t, const void *);
1717 static void* my_malloc_hook(size_t, const void *);
1718 static void my_free_hook(void *, const void *);
1719
1720 static inline void
1721 install_old_hooks()
1722 {
1723     __memalign_hook = old_memalign_hook;
1724     __realloc_hook = old_realloc_hook;
1725     __malloc_hook = old_malloc_hook;
1726     __free_hook = old_free_hook;
1727 }
1728
1729 static inline void
1730 save_old_hooks()
1731 {
1732     // Glibc docs recommend re-saving old hooks on
1733     // return from recursive calls. Strangely when
1734     // we do this, we find ourselves in infinite
1735     // recursion.
1736
1737     //     old_memalign_hook = __memalign_hook;
1738     //     old_realloc_hook = __realloc_hook;
1739     //     old_malloc_hook = __malloc_hook;
1740     //     old_free_hook = __free_hook;
1741 }
1742
1743 static inline void
1744 install_new_hooks()
1745 {
1746     __memalign_hook = my_memalign_hook;
1747     __realloc_hook = my_realloc_hook;
1748     __malloc_hook = my_malloc_hook;
1749     __free_hook = my_free_hook;
1750 }
1751
1752 static void*
1753 my_realloc_hook(void *ptr, size_t size, const void *caller)
1754 {
1755     void *result;
1756
1757     install_old_hooks();
1758     result = realloc(ptr, size);
1759     save_old_hooks();
1760
1761     if (sCollector) {
1762         sCollector->Freed(ptr);
1763         sCollector->Allocated(result, size);
1764     }
1765
1766     install_new_hooks();
1767
1768     return result;
1769 }
1770
1771
1772 static void*
1773 my_memalign_hook(size_t size, size_t alignment, const void *caller)
1774 {
1775     void *result;
1776
1777     install_old_hooks();
1778     result = memalign(size, alignment);
1779     save_old_hooks();
1780
1781     if (sCollector)
1782         sCollector->Allocated(result, size);
1783
1784     install_new_hooks();
1785
1786     return result;
1787 }
1788
1789
1790 static void
1791 my_free_hook (void *ptr, const void *caller)
1792 {
1793     install_old_hooks();
1794     free(ptr);
1795     save_old_hooks();
1796
1797     if (sCollector)
1798         sCollector->Freed(ptr);
1799
1800     install_new_hooks();
1801 }
1802
1803
1804 static void*
1805 my_malloc_hook (size_t size, const void *caller)
1806 {
1807     void *result;
1808
1809     install_old_hooks();
1810     result = malloc (size);
1811     save_old_hooks();
1812
1813     if (sCollector)
1814         sCollector->Allocated(result, size);
1815
1816     install_new_hooks();
1817
1818     return result;
1819 }
1820
1821
1822 static void
1823 InitMemHook(void)
1824 {
1825     if (!hookedMalloc) {
1826         save_old_hooks();
1827         install_new_hooks();
1828         hookedMalloc = PR_TRUE;
1829     }
1830 }
1831
1832 #elif defined(WIN32)
1833 #ifndef __MINGW32__
1834
1835 static int
1836 AllocHook(int allocType, void *userData, size_t size, int
1837           blockType, long requestNumber, const unsigned char *filename, int
1838           lineNumber)
1839 {
1840     if (allocType == _HOOK_FREE)
1841         sCollector->Freed(userData);
1842     return 1;
1843 }
1844
1845
1846 static void InitMemHook(void)
1847 {
1848     if (!hookedMalloc) {
1849         _CrtSetAllocHook (AllocHook);
1850         hookedMalloc = PR_TRUE;
1851     }
1852 }
1853 #endif // __MINGW32__
1854
1855 #elif 0 // defined(XP_MACOSX)
1856
1857 #include <malloc/malloc.h>
1858
1859 static void (*old_free)(struct _malloc_zone_t *zone, void *ptr);
1860
1861 static void
1862 freehook(struct _malloc_zone_t *zone, void *ptr)
1863 {
1864     if (sCollector)
1865         sCollector->Freed(ptr);
1866     old_free(zone, ptr);
1867 }
1868
1869
1870 static void
1871 InitMemHook(void)
1872 {
1873     if (!hookedMalloc) {
1874         malloc_zone_t *default_zone = malloc_default_zone();
1875         old_free = default_zone->free;
1876         default_zone->free = freehook;
1877         hookedMalloc = PR_TRUE;
1878     }
1879 }
1880
1881
1882 #else
1883
1884 static void
1885 InitMemHook(void)
1886 {
1887 }
1888
1889 #endif // GLIBC / WIN32 / OSX
1890 #endif // DEBUG_CC
1891
1892 ////////////////////////////////////////////////////////////////////////
1893 // Collector implementation
1894 ////////////////////////////////////////////////////////////////////////
1895
1896 nsCycleCollector::nsCycleCollector() :
1897     mCollectionInProgress(PR_FALSE),
1898     mScanInProgress(PR_FALSE),
1899     mCollectedObjects(0),
1900     mWhiteNodes(nsnull),
1901     mWhiteNodeCount(0),
1902 #ifdef DEBUG_CC
1903     mPurpleBuf(mParams, mStats),
1904     mPtrLog(nsnull)
1905 #else
1906     mPurpleBuf(mParams)
1907 #endif
1908 {
1909 #ifdef DEBUG_CC
1910     mExpectedGarbage.Init();
1911 #endif
1912
1913     memset(mRuntimes, 0, sizeof(mRuntimes));
1914     mRuntimes[nsIProgrammingLanguage::CPLUSPLUS] = &mXPCOMRuntime;
1915 }
1916
1917
1918 nsCycleCollector::~nsCycleCollector()
1919 {
1920 }
1921
1922
1923 void
1924 nsCycleCollector::RegisterRuntime(PRUint32 langID,
1925                                   nsCycleCollectionLanguageRuntime *rt)
1926 {
1927     if (mParams.mDoNothing)
1928         return;
1929
1930     if (langID > nsIProgrammingLanguage::MAX)
1931         Fault("unknown language runtime in registration");
1932
1933     if (mRuntimes[langID])
1934         Fault("multiple registrations of language runtime", rt);
1935
1936     mRuntimes[langID] = rt;
1937 }
1938
1939
1940 void
1941 nsCycleCollector::ForgetRuntime(PRUint32 langID)
1942 {
1943     if (mParams.mDoNothing)
1944         return;
1945
1946     if (langID > nsIProgrammingLanguage::MAX)
1947         Fault("unknown language runtime in deregistration");
1948
1949     if (! mRuntimes[langID])
1950         Fault("forgetting non-registered language runtime");
1951
1952     mRuntimes[langID] = nsnull;
1953 }
1954
1955
1956 #ifdef DEBUG_CC
1957 static void
1958 WriteGraph(FILE *stream, GCGraph &graph, const void *redPtr)
1959 {
1960     fprintf(stream,
1961             "digraph collection {\n"
1962             "rankdir=LR\n"
1963             "node [fontname=fixed, fontsize=10, style=filled, shape=box]\n"
1964             );
1965
1966     NodePool::Enumerator etor(graph.mNodes);
1967     while (!etor.IsDone()) {
1968         PtrInfo *pi = etor.GetNext();
1969         const void *p = pi->mPointer;
1970         fprintf(stream,
1971                 "n%p [label=\"%s\\n%p\\n",
1972                 p,
1973                 pi->mName,
1974                 p);
1975         if (pi->mRefCount != 0 && pi->mRefCount != PR_UINT32_MAX) {
1976             fprintf(stream,
1977                     "%u/%u refs found",
1978                     pi->mInternalRefs, pi->mRefCount);
1979         }
1980         fprintf(stream,
1981                 "\", fillcolor=%s, fontcolor=%s]\n",
1982                 (redPtr && redPtr == p ? "red" : (pi->mColor == black ? "black" : "white")),
1983                 (pi->mColor == black ? "white" : "black"));
1984         for (EdgePool::Iterator child = pi->mFirstChild,
1985                  child_end = pi->mLastChild;
1986              child != child_end; ++child) {
1987             fprintf(stream, "n%p -> n%p\n", p, (*child)->mPointer);
1988         }
1989     }
1990
1991     fprintf(stream, "\n}\n");
1992 }
1993
1994
1995 void
1996 nsCycleCollector::MaybeDrawGraphs()
1997 {
1998     if (mParams.mDrawGraphs) {
1999         // We draw graphs only if there were any white nodes.
2000         PRBool anyWhites = PR_FALSE;
2001         NodePool::Enumerator fwetor(mGraph.mNodes);
2002         while (!fwetor.IsDone())
2003         {
2004             PtrInfo *pinfo = fwetor.GetNext();
2005             if (pinfo->mColor == white) {
2006                 anyWhites = PR_TRUE;
2007                 break;
2008             }
2009         }
2010
2011         if (anyWhites) {
2012             // We can't just use _popen here because graphviz-for-windows
2013             // doesn't set up its stdin stream properly, sigh.
2014             FILE *stream;
2015 #ifdef WIN32
2016             stream = fopen("c:\\cycle-graph.dot", "w+");
2017 #else
2018             stream = popen("dotty -", "w");
2019 #endif
2020             WriteGraph(stream, mGraph, nsnull);
2021 #ifdef WIN32
2022             fclose(stream);
2023             // Even dotty doesn't work terribly well on windows, since
2024             // they execute lefty asynchronously. So we'll just run
2025             // lefty ourselves.
2026             _spawnlp(_P_WAIT,
2027                      "lefty",
2028                      "lefty",
2029                      "-e",
2030                      "\"load('dotty.lefty');"
2031                      "dotty.simple('c:\\cycle-graph.dot');\"",
2032                      NULL);
2033             unlink("c:\\cycle-graph.dot");
2034 #else
2035             pclose(stream);
2036 #endif
2037         }
2038     }
2039 }
2040
2041 class Suppressor :
2042     public nsCycleCollectionTraversalCallback
2043 {
2044 protected:
2045     static char *sSuppressionList;
2046     static PRBool sInitialized;
2047     PRBool mSuppressThisNode;
2048 public:
2049     Suppressor()
2050     {
2051     }
2052
2053     PRBool shouldSuppress(nsISupports *s)
2054     {
2055         if (!sInitialized) {
2056             sSuppressionList = PR_GetEnv("XPCOM_CC_SUPPRESS");
2057             sInitialized = PR_TRUE;
2058         }
2059         if (sSuppressionList == nsnull) {
2060             mSuppressThisNode = PR_FALSE;
2061         } else {
2062             nsresult rv;
2063             nsXPCOMCycleCollectionParticipant *cp;
2064             rv = CallQueryInterface(s, &cp);
2065             if (NS_FAILED(rv)) {
2066                 Fault("checking suppression on wrong type of pointer", s);
2067                 return PR_TRUE;
2068             }
2069             cp->Traverse(s, *this);
2070         }
2071         return mSuppressThisNode;
2072     }
2073
2074     NS_IMETHOD_(void) DescribeNode(CCNodeType type, nsrefcnt refCount,
2075                                    size_t objSz, const char *objName)
2076     {
2077         mSuppressThisNode = (PL_strstr(sSuppressionList, objName) != nsnull);
2078     }
2079
2080     NS_IMETHOD_(void) NoteXPCOMRoot(nsISupports *root) {};
2081     NS_IMETHOD_(void) NoteRoot(PRUint32 langID, void *root,
2082                                nsCycleCollectionParticipant* participant) {};
2083     NS_IMETHOD_(void) NoteXPCOMChild(nsISupports *child) {}
2084     NS_IMETHOD_(void) NoteScriptChild(PRUint32 langID, void *child) {}
2085     NS_IMETHOD_(void) NoteNativeChild(void *child,
2086                                      nsCycleCollectionParticipant *participant) {}
2087     NS_IMETHOD_(void) NoteNextEdgeName(const char* name) {}
2088 };
2089
2090 char *Suppressor::sSuppressionList = nsnull;
2091 PRBool Suppressor::sInitialized = PR_FALSE;
2092
2093 static PRBool
2094 nsCycleCollector_shouldSuppress(nsISupports *s)
2095 {
2096     Suppressor supp;
2097     return supp.shouldSuppress(s);
2098 }
2099 #endif
2100
2101 #ifdef DEBUG
2102 static PRBool
2103 nsCycleCollector_isScanSafe(nsISupports *s)
2104 {
2105     if (!s)
2106         return PR_FALSE;
2107
2108     nsXPCOMCycleCollectionParticipant *cp;
2109     ToParticipant(s, &cp);
2110
2111     return cp != nsnull;
2112 }
2113 #endif
2114
2115 PRBool
2116 nsCycleCollector::Suspect(nsISupports *n)
2117 {
2118     // Re-entering ::Suspect during collection used to be a fault, but
2119     // we are canonicalizing nsISupports pointers using QI, so we will
2120     // see some spurious refcount traffic here.
2121
2122     if (mScanInProgress)
2123         return PR_FALSE;
2124
2125     NS_ASSERTION(nsCycleCollector_isScanSafe(n),
2126                  "suspected a non-scansafe pointer");
2127     NS_ASSERTION(NS_IsMainThread(), "trying to suspect from non-main thread");
2128
2129     if (mParams.mDoNothing)
2130         return PR_FALSE;
2131
2132 #ifdef DEBUG_CC
2133     mStats.mSuspectNode++;
2134
2135     if (nsCycleCollector_shouldSuppress(n))
2136         return PR_FALSE;
2137
2138 #ifndef __MINGW32__
2139     if (mParams.mHookMalloc)
2140         InitMemHook();
2141 #endif
2142
2143     if (mParams.mLogPointers) {
2144         if (!mPtrLog)
2145             mPtrLog = fopen("pointer_log", "w");
2146         fprintf(mPtrLog, "S %p\n", static_cast<void*>(n));
2147     }
2148 #endif
2149
2150     mPurpleBuf.Put(n);
2151
2152     return PR_TRUE;
2153 }
2154
2155
2156 PRBool
2157 nsCycleCollector::Forget(nsISupports *n)
2158 {
2159     // Re-entering ::Forget during collection used to be a fault, but
2160     // we are canonicalizing nsISupports pointers using QI, so we will
2161     // see some spurious refcount traffic here.
2162
2163     if (mScanInProgress)
2164         return PR_FALSE;
2165
2166     NS_ASSERTION(NS_IsMainThread(), "trying to forget from non-main thread");
2167
2168     if (mParams.mDoNothing)
2169         return PR_TRUE; // it's as good as forgotten
2170
2171 #ifdef DEBUG_CC
2172     mStats.mForgetNode++;
2173
2174 #ifndef __MINGW32__
2175     if (mParams.mHookMalloc)
2176         InitMemHook();
2177 #endif
2178
2179     if (mParams.mLogPointers) {
2180         if (!mPtrLog)
2181             mPtrLog = fopen("pointer_log", "w");
2182         fprintf(mPtrLog, "F %p\n", static_cast<void*>(n));
2183     }
2184 #endif
2185
2186     mPurpleBuf.Remove(n);
2187     return PR_TRUE;
2188 }
2189
2190 #ifdef DEBUG_CC
2191 void
2192 nsCycleCollector::Allocated(void *n, size_t sz)
2193 {
2194 }
2195
2196 void
2197 nsCycleCollector::Freed(void *n)
2198 {
2199     mStats.mFreeCalls++;
2200
2201     if (!n) {
2202         // Ignore null pointers coming through
2203         return;
2204     }
2205
2206     if (mPurpleBuf.Exists(n)) {
2207         mStats.mForgetNode++;
2208         mStats.mFreedWhilePurple++;
2209         Fault("freed while purple", n);
2210         mPurpleBuf.Remove(n);
2211
2212         if (mParams.mLogPointers) {
2213             if (!mPtrLog)
2214                 mPtrLog = fopen("pointer_log", "w");
2215             fprintf(mPtrLog, "R %p\n", n);
2216         }
2217     }
2218 }
2219 #endif
2220
2221 PRUint32
2222 nsCycleCollector::Collect(PRUint32 aTryCollections)
2223 {
2224 #if defined(DEBUG_CC) && !defined(__MINGW32__)
2225     if (!mParams.mDoNothing && mParams.mHookMalloc)
2226         InitMemHook();
2227 #endif
2228
2229     // This can legitimately happen in a few cases. See bug 383651.
2230     if (mCollectionInProgress)
2231         return 0;
2232
2233 #ifdef COLLECT_TIME_DEBUG
2234     printf("cc: Starting nsCycleCollector::Collect(%d)\n", aTryCollections);
2235     PRTime start = PR_Now();
2236 #endif
2237
2238     mCollectionInProgress = PR_TRUE;
2239
2240     nsCOMPtr<nsIObserverService> obs =
2241       do_GetService("@mozilla.org/observer-service;1");
2242     if (obs) {
2243         obs->NotifyObservers(nsnull, "cycle-collector-begin", nsnull);
2244     }
2245
2246     mFollowupCollection = PR_FALSE;
2247     mCollectedObjects = 0;
2248     nsAutoTPtrArray<PtrInfo, 4000> whiteNodes;
2249     mWhiteNodes = &whiteNodes;
2250
2251     PRUint32 totalCollections = 0;
2252     while (aTryCollections > totalCollections) {
2253         PRBool collected;
2254         if (mRuntimes[nsIProgrammingLanguage::JAVASCRIPT]) {
2255             collected = static_cast<nsCycleCollectionJSRuntime*>
2256                 (mRuntimes[nsIProgrammingLanguage::JAVASCRIPT])->Collect();
2257         }
2258         else {
2259             collected = BeginCollection() && FinishCollection();
2260         }
2261
2262 #ifdef DEBUG_CC
2263         // We wait until after FinishCollection to check the white nodes because
2264         // some objects may outlive CollectWhite but then be freed by
2265         // FinishCycleCollection (like XPConnect's deferred release of native
2266         // objects).
2267         PRUint32 i, count = mWhiteNodes->Length();
2268         for (i = 0; i < count; ++i) {
2269             PtrInfo *pinfo = mWhiteNodes->ElementAt(i);
2270             if (pinfo->mLangID == nsIProgrammingLanguage::CPLUSPLUS &&
2271                 mPurpleBuf.Exists(pinfo->mPointer)) {
2272                 printf("nsCycleCollector: %s object @%p is still alive after\n"
2273                        "  calling RootAndUnlinkJSObjects, Unlink, and Unroot on"
2274                        " it!  This probably\n"
2275                        "  means the Unlink implementation was insufficient.\n",
2276                        pinfo->mName, pinfo->mPointer);
2277             }
2278         }
2279 #endif
2280         mWhiteNodes->Clear();
2281         ClearGraph();
2282
2283         if (!collected)
2284             break;
2285
2286         ++totalCollections;
2287     }
2288
2289     mWhiteNodes = nsnull;
2290
2291     mCollectionInProgress = PR_FALSE;
2292
2293 #ifdef XP_OS2
2294     // Now that the cycle collector has freed some memory, we can try to
2295     // force the C library to give back as much memory to the system as
2296     // possible.
2297     _heapmin();
2298 #endif
2299
2300 #ifdef COLLECT_TIME_DEBUG
2301     printf("cc: Collect() took %lldms\n",
2302            (PR_Now() - start) / PR_USEC_PER_MSEC);
2303 #endif
2304 #ifdef DEBUG_CC
2305     ExplainLiveExpectedGarbage();
2306 #endif
2307     return mCollectedObjects;
2308 }
2309
2310 PRBool
2311 nsCycleCollector::BeginCollection()
2312 {
2313     if (mParams.mDoNothing)
2314         return PR_FALSE;
2315
2316     GCGraphBuilder builder(mGraph, mRuntimes);
2317
2318 #ifdef COLLECT_TIME_DEBUG
2319     PRTime now = PR_Now();
2320 #endif
2321     for (PRUint32 i = 0; i <= nsIProgrammingLanguage::MAX; ++i) {
2322         if (mRuntimes[i])
2323             mRuntimes[i]->BeginCycleCollection(builder);
2324     }
2325
2326 #ifdef COLLECT_TIME_DEBUG
2327     printf("cc: mRuntimes[*]->BeginCycleCollection() took %lldms\n",
2328            (PR_Now() - now) / PR_USEC_PER_MSEC);
2329
2330     now = PR_Now();
2331 #endif
2332
2333 #ifdef DEBUG_CC
2334     PRUint32 purpleStart = builder.Count();
2335 #endif
2336     mScanInProgress = PR_TRUE;
2337     SelectPurple(builder);
2338 #ifdef DEBUG_CC
2339     PRUint32 purpleEnd = builder.Count();
2340
2341     if (purpleStart != purpleEnd) {
2342 #ifndef __MINGW32__
2343         if (mParams.mHookMalloc)
2344             InitMemHook();
2345 #endif
2346         if (mParams.mLogPointers && !mPtrLog)
2347             mPtrLog = fopen("pointer_log", "w");
2348
2349         PRUint32 i = 0;
2350         NodePool::Enumerator queue(mGraph.mNodes);
2351         while (i++ < purpleStart) {
2352             queue.GetNext();
2353         }
2354         while (i++ < purpleEnd) {
2355             mStats.mForgetNode++;
2356             if (mParams.mLogPointers)
2357                 fprintf(mPtrLog, "F %p\n", queue.GetNext()->mPointer);
2358         }
2359     }
2360 #endif
2361
2362 #ifdef COLLECT_TIME_DEBUG
2363     printf("cc: SelectPurple() took %lldms\n",
2364            (PR_Now() - now) / PR_USEC_PER_MSEC);
2365 #endif
2366
2367     if (builder.Count() > 0) {
2368         // The main Bacon & Rajan collection algorithm.
2369
2370 #ifdef COLLECT_TIME_DEBUG
2371         now = PR_Now();
2372 #endif
2373
2374         MarkRoots(builder);
2375
2376 #ifdef COLLECT_TIME_DEBUG
2377         {
2378             PRTime then = PR_Now();
2379             printf("cc: MarkRoots() took %lldms\n",
2380                    (then - now) / PR_USEC_PER_MSEC);
2381             now = then;
2382         }
2383 #endif
2384
2385         ScanRoots();
2386
2387 #ifdef COLLECT_TIME_DEBUG
2388         printf("cc: ScanRoots() took %lldms\n",
2389                (PR_Now() - now) / PR_USEC_PER_MSEC);
2390 #endif
2391
2392 #ifdef DEBUG_CC
2393         MaybeDrawGraphs();
2394 #endif
2395
2396         mScanInProgress = PR_FALSE;
2397
2398 #ifdef DEBUG_CC
2399         if (mFollowupCollection && purpleStart != purpleEnd) {
2400             PRUint32 i = 0;
2401             NodePool::Enumerator queue(mGraph.mNodes);
2402             while (i++ < purpleStart) {
2403                 queue.GetNext();
2404             }
2405             while (i++ < purpleEnd) {
2406                 PtrInfo *pi = queue.GetNext();
2407                 if (pi->mColor == white) {
2408                     printf("nsCycleCollector: a later shutdown collection collected the additional\n"
2409                            "  suspect %p %s\n"
2410                            "  (which could be fixed by improving traversal)\n",
2411                            pi->mPointer, pi->mName);
2412                 }
2413             }
2414         }
2415 #endif
2416
2417 #ifdef COLLECT_TIME_DEBUG
2418         now = PR_Now();
2419 #endif
2420         RootWhite();
2421
2422 #ifdef COLLECT_TIME_DEBUG
2423         printf("cc: RootWhite() took %lldms\n",
2424                (PR_Now() - now) / PR_USEC_PER_MSEC);
2425 #endif
2426     }
2427     else {
2428         mScanInProgress = PR_FALSE;
2429     }
2430
2431     return PR_TRUE;
2432 }
2433
2434 PRBool
2435 nsCycleCollector::FinishCollection()
2436 {
2437 #ifdef COLLECT_TIME_DEBUG
2438     PRTime now = PR_Now();
2439 #endif
2440     PRBool collected = CollectWhite();
2441
2442 #ifdef COLLECT_TIME_DEBUG
2443     printf("cc: CollectWhite() took %lldms\n",
2444            (PR_Now() - now) / PR_USEC_PER_MSEC);
2445 #endif
2446
2447 #ifdef DEBUG_CC
2448     mStats.mCollection++;
2449     if (mParams.mReportStats)
2450         mStats.Dump();
2451 #endif
2452
2453     for (PRUint32 i = 0; i <= nsIProgrammingLanguage::MAX; ++i) {
2454         if (mRuntimes[i])
2455             mRuntimes[i]->FinishCycleCollection();
2456     }
2457
2458     mFollowupCollection = PR_TRUE;
2459
2460     return collected;
2461 }
2462
2463 PRUint32
2464 nsCycleCollector::SuspectedCount()
2465 {
2466     return mPurpleBuf.Count();
2467 }
2468
2469 void
2470 nsCycleCollector::Shutdown()
2471 {
2472     // Here we want to run a final collection on everything we've seen
2473     // buffered, irrespective of age; then permanently disable
2474     // the collector because the program is shutting down.
2475
2476     mParams.mScanDelay = 0;
2477     Collect(SHUTDOWN_COLLECTIONS(mParams));
2478
2479 #ifdef DEBUG_CC
2480     GCGraphBuilder builder(mGraph, mRuntimes);
2481     mScanInProgress = PR_TRUE;
2482     SelectPurple(builder);
2483     mScanInProgress = PR_FALSE;
2484     if (builder.Count() != 0) {
2485         printf("Might have been able to release more cycles if the cycle collector would "
2486                "run once more at shutdown.\n");
2487     }
2488     ClearGraph();
2489 #endif
2490     mParams.mDoNothing = PR_TRUE;
2491 }
2492
2493 #ifdef DEBUG_CC
2494
2495 static PLDHashOperator
2496 AddExpectedGarbage(nsVoidPtrHashKey *p, void *arg)
2497 {
2498     GCGraphBuilder *builder = static_cast<GCGraphBuilder*>(arg);
2499     nsISupports *root =
2500       static_cast<nsISupports*>(const_cast<void*>(p->GetKey()));
2501     builder->NoteXPCOMRoot(root);
2502     return PL_DHASH_NEXT;
2503 }
2504
2505 struct SetSCCWalker : public GraphWalker
2506 {
2507     SetSCCWalker(PRUint32 aIndex) : mIndex(aIndex) {}
2508     PRBool ShouldVisitNode(PtrInfo const *pi) { return pi->mSCCIndex == 0; }
2509     void VisitNode(PtrInfo *pi) { pi->mSCCIndex = mIndex; }
2510 private:
2511     PRUint32 mIndex;
2512 };
2513
2514 struct SetNonRootGreyWalker : public GraphWalker
2515 {
2516     PRBool ShouldVisitNode(PtrInfo const *pi) { return pi->mColor == white; }
2517     void VisitNode(PtrInfo *pi) { pi->mColor = grey; }
2518 };
2519
2520 static void
2521 PrintPathToExpectedGarbage(PtrInfo *pi)
2522 {
2523     printf("  An object expected to be garbage could be "
2524            "reached from it by the path:\n");
2525     for (PtrInfo *path = pi, *prev = nsnull; prev != path;
2526          prev = path,
2527          path = path->mShortestPathToExpectedGarbage) {
2528         if (prev) {
2529             nsCString *edgeName = prev
2530                 ->mShortestPathToExpectedGarbageEdgeName;
2531             printf("        via %s\n",
2532                    edgeName->IsEmpty() ? "<unknown edge>"
2533                                        : edgeName->get());
2534         }
2535         printf("    %s %p\n", path->mName, path->mPointer);
2536     }
2537 }
2538
2539 void
2540 nsCycleCollector::ExplainLiveExpectedGarbage()
2541 {
2542     if (mScanInProgress || mCollectionInProgress)
2543         Fault("can't explain expected garbage during collection itself");
2544
2545     if (mParams.mDoNothing) {
2546         printf("nsCycleCollector: not explaining expected garbage since\n"
2547                "  cycle collection disabled\n");
2548         return;
2549     }
2550
2551     mCollectionInProgress = PR_TRUE;
2552     mScanInProgress = PR_TRUE;
2553
2554     {
2555         GCGraphBuilder builder(mGraph, mRuntimes);
2556
2557         for (PRUint32 i = 0; i <= nsIProgrammingLanguage::MAX; ++i) {
2558             if (mRuntimes[i])
2559                 mRuntimes[i]->BeginCycleCollection(builder);
2560         }
2561
2562         // This might fail to explain expected garbage that's also in
2563         // the set of roots added by the runtimes (what used to be
2564         // called suspectCurrent), but that seems pretty unlikely.
2565         PRUint32 suspectCurrentCount = builder.Count();
2566
2567         // Instead of adding roots from the purple buffer, we add them
2568         // from the list of nodes we were expected to collect.
2569         mExpectedGarbage.EnumerateEntries(&AddExpectedGarbage, &builder);
2570
2571         MarkRoots(builder);
2572         ScanRoots();
2573
2574         mScanInProgress = PR_FALSE;
2575
2576         PRBool describeExtraRefcounts = PR_FALSE;
2577         PRBool findCycleRoots = PR_FALSE;
2578         {
2579             NodePool::Enumerator queue(mGraph.mNodes);
2580             PRUint32 i = 0;
2581             while (!queue.IsDone()) {
2582                 PtrInfo *pi = queue.GetNext();
2583                 if (pi->mColor == white) {
2584                     findCycleRoots = PR_TRUE;
2585                 }
2586
2587                 if (pi->mInternalRefs != pi->mRefCount && i >= suspectCurrentCount) {
2588                     describeExtraRefcounts = PR_TRUE;
2589                 }
2590                 ++i;
2591             }
2592         }
2593
2594         if ((describeExtraRefcounts || findCycleRoots) &&
2595             CreateReversedEdges()) {
2596             // Note that the external references may have been external
2597             // to a different node in the cycle collection that just
2598             // happened, if that different node was purple and then
2599             // black.
2600
2601             // Use mSCCIndex temporarily to track whether we've reached
2602             // nodes in the breadth-first search.
2603             const PRUint32 INDEX_UNREACHED = 0;
2604             const PRUint32 INDEX_REACHED = 1;
2605             NodePool::Enumerator etor_clear(mGraph.mNodes);
2606             while (!etor_clear.IsDone()) {
2607                 PtrInfo *pi = etor_clear.GetNext();
2608                 pi->mSCCIndex = INDEX_UNREACHED;
2609             }
2610
2611             nsDeque queue; // for breadth-first search
2612             NodePool::Enumerator etor_roots(mGraph.mNodes);
2613             for (PRUint32 i = 0; i < mGraph.mRootCount; ++i) {
2614                 PtrInfo *root_pi = etor_roots.GetNext();
2615                 if (i >= suspectCurrentCount) {
2616                     root_pi->mSCCIndex = INDEX_REACHED;
2617                     root_pi->mShortestPathToExpectedGarbage = root_pi;
2618                     queue.Push(root_pi);
2619                 }
2620             }
2621
2622             while (queue.GetSize() > 0) {
2623                 PtrInfo *pi = (PtrInfo*)queue.PopFront();
2624                 for (ReversedEdge *e = pi->mReversedEdges; e; e = e->mNext) {
2625                     if (e->mTarget->mSCCIndex == INDEX_UNREACHED) {
2626                         e->mTarget->mSCCIndex = INDEX_REACHED;
2627                         PtrInfo *target = e->mTarget;
2628                         if (!target->mShortestPathToExpectedGarbage) {
2629                             target->mShortestPathToExpectedGarbage = pi;
2630                             target->mShortestPathToExpectedGarbageEdgeName =
2631                                 e->mEdgeName;
2632                         }
2633                         queue.Push(target);
2634                     }
2635                 }
2636
2637                 if (pi->mRefCount == PR_UINT32_MAX ||
2638                     (pi->mInternalRefs != pi->mRefCount && pi->mRefCount > 0)) {
2639                     if (pi->mRefCount == PR_UINT32_MAX) {
2640                         printf("nsCycleCollector: %s %p was not collected due "
2641                            "to \n"
2642                            "  external references\n",
2643                            pi->mName, pi->mPointer);
2644                     }
2645                     else {
2646                         printf("nsCycleCollector: %s %p was not collected due "
2647                                "to %d\n"
2648                                "  external references (%d total - %d known)\n",
2649                                pi->mName, pi->mPointer,
2650                                pi->mRefCount - pi->mInternalRefs,
2651                                pi->mRefCount, pi->mInternalRefs);
2652                     }
2653
2654                     PrintPathToExpectedGarbage(pi);
2655
2656                     if (pi->mRefCount == PR_UINT32_MAX) {
2657                         printf("  The known references to it were from:\n");
2658                     }
2659                     else {
2660                         printf("  The %d known references to it were from:\n",
2661                                pi->mInternalRefs);
2662                     }
2663                     for (ReversedEdge *e = pi->mReversedEdges;
2664                          e; e = e->mNext) {
2665                         printf("    %s %p",
2666                                e->mTarget->mName, e->mTarget->mPointer);
2667                         if (!e->mEdgeName->IsEmpty()) {
2668                             printf(" via %s", e->mEdgeName->get());
2669                         }
2670                         printf("\n");
2671                     }
2672                     mRuntimes[pi->mLangID]->PrintAllReferencesTo(pi->mPointer);
2673                 }
2674             }
2675
2676             if (findCycleRoots) {
2677                 // NOTE: This code changes the white nodes that are not
2678                 // roots to gray.
2679
2680                 // Put the nodes in post-order traversal order from a
2681                 // depth-first search.
2682                 nsDeque DFSPostOrder;
2683
2684                 {
2685                     // Use mSCCIndex temporarily to track the DFS numbering:
2686                     const PRUint32 INDEX_UNREACHED = 0;
2687                     const PRUint32 INDEX_TRAVERSING = 1;
2688                     const PRUint32 INDEX_NUMBERED = 2;
2689
2690                     NodePool::Enumerator etor_clear(mGraph.mNodes);
2691                     while (!etor_clear.IsDone()) {
2692                         PtrInfo *pi = etor_clear.GetNext();
2693                         pi->mSCCIndex = INDEX_UNREACHED;
2694                     }
2695
2696                     nsDeque stack;
2697
2698                     NodePool::Enumerator etor_roots(mGraph.mNodes);
2699                     for (PRUint32 i = 0; i < mGraph.mRootCount; ++i) {
2700                         PtrInfo *root_pi = etor_roots.GetNext();
2701                         stack.Push(root_pi);
2702                     }
2703
2704                     while (stack.GetSize() > 0) {
2705                         PtrInfo *pi = (PtrInfo*)stack.Peek();
2706                         if (pi->mSCCIndex == INDEX_UNREACHED) {
2707                             pi->mSCCIndex = INDEX_TRAVERSING;
2708                             for (EdgePool::Iterator child = pi->mFirstChild,
2709                                                 child_end = pi->mLastChild;
2710                                  child != child_end; ++child) {
2711                                 stack.Push(*child);
2712                             }
2713                         } else {
2714                             stack.Pop();
2715                             // Somebody else might have numbered it already
2716                             // (since this is depth-first, not breadth-first).
2717                             // This happens if a node is pushed on the stack
2718                             // a second time while it is on the stack in
2719                             // UNREACHED state.
2720                             if (pi->mSCCIndex == INDEX_TRAVERSING) {
2721                                 pi->mSCCIndex = INDEX_NUMBERED;
2722                                 DFSPostOrder.Push(pi);
2723                             }
2724                         }
2725                     }
2726                 }
2727
2728                 // Put the nodes into strongly-connected components.
2729                 {
2730                     NodePool::Enumerator etor_clear(mGraph.mNodes);
2731                     while (!etor_clear.IsDone()) {
2732                         PtrInfo *pi = etor_clear.GetNext();
2733                         pi->mSCCIndex = 0;
2734                     }
2735
2736                     PRUint32 currentSCC = 1;
2737
2738                     while (DFSPostOrder.GetSize() > 0) {
2739                         SetSCCWalker(currentSCC).Walk((PtrInfo*)DFSPostOrder.PopFront());
2740                         ++currentSCC;
2741                     }
2742                 }
2743
2744                 // Mark any white nodes reachable from other components as
2745                 // grey.
2746                 {
2747                     NodePool::Enumerator queue(mGraph.mNodes);
2748                     while (!queue.IsDone()) {
2749                         PtrInfo *pi = queue.GetNext();
2750                         if (pi->mColor != white)
2751                             continue;
2752                         for (EdgePool::Iterator child = pi->mFirstChild,
2753                                             child_end = pi->mLastChild;
2754                              child != child_end; ++child) {
2755                             if ((*child)->mSCCIndex != pi->mSCCIndex) {
2756                                 SetNonRootGreyWalker().Walk(*child);
2757                             }
2758                         }
2759                     }
2760                 }
2761
2762                 {
2763                     NodePool::Enumerator queue(mGraph.mNodes);
2764                     while (!queue.IsDone()) {
2765                         PtrInfo *pi = queue.GetNext();
2766                         if (pi->mColor == white) {
2767                             printf("nsCycleCollector: %s %p in component %d\n"
2768                                    "  was not collected due to missing call to "
2769                                    "suspect, failure to unlink,\n"
2770                                    "  or deficiency in traverse that causes "
2771                                    "cycles referenced only from other\n"
2772                                    "  cycles to require multiple rounds of cycle "
2773                                    "collection\n",
2774                                    pi->mName, pi->mPointer, pi->mSCCIndex);
2775                             if (pi->mShortestPathToExpectedGarbage)
2776                                 PrintPathToExpectedGarbage(pi);
2777                         }
2778                     }
2779                 }
2780             }
2781
2782             DestroyReversedEdges();
2783         }
2784     }
2785
2786     ClearGraph();
2787
2788     mCollectionInProgress = PR_FALSE;
2789
2790     for (PRUint32 i = 0; i <= nsIProgrammingLanguage::MAX; ++i) {
2791         if (mRuntimes[i])
2792             mRuntimes[i]->FinishCycleCollection();
2793     }
2794 }
2795
2796 PRBool
2797 nsCycleCollector::CreateReversedEdges()
2798 {
2799     // Count the edges in the graph.
2800     PRUint32 edgeCount = 0;
2801     NodePool::Enumerator countQueue(mGraph.mNodes);
2802     while (!countQueue.IsDone()) {
2803         PtrInfo *pi = countQueue.GetNext();
2804         for (EdgePool::Iterator e = pi->mFirstChild, e_end = pi->mLastChild;
2805              e != e_end; ++e, ++edgeCount) {
2806         }
2807     }
2808
2809     // Allocate a pool to hold all of the edges.
2810     mGraph.mReversedEdges = new ReversedEdge[edgeCount];
2811     if (mGraph.mReversedEdges == nsnull) {
2812         NS_NOTREACHED("allocation failure creating reversed edges");
2813         return PR_FALSE;
2814     }
2815
2816     // Fill in the reversed edges by scanning all forward edges.
2817     ReversedEdge *current = mGraph.mReversedEdges;
2818     NodePool::Enumerator buildQueue(mGraph.mNodes);
2819     while (!buildQueue.IsDone()) {
2820         PtrInfo *pi = buildQueue.GetNext();
2821         PRInt32 i = 0;
2822         for (EdgePool::Iterator e = pi->mFirstChild, e_end = pi->mLastChild;
2823              e != e_end; ++e) {
2824             current->mTarget = pi;
2825             current->mEdgeName = pi->mEdgeNames.CStringAt(i);
2826             current->mNext = (*e)->mReversedEdges;
2827             (*e)->mReversedEdges = current;
2828             ++current;
2829             ++i;
2830         }
2831     }
2832     NS_ASSERTION(current - mGraph.mReversedEdges == ptrdiff_t(edgeCount),
2833                  "misallocation");
2834     return PR_TRUE;
2835 }
2836
2837 void
2838 nsCycleCollector::DestroyReversedEdges()
2839 {
2840     NodePool::Enumerator queue(mGraph.mNodes);
2841     while (!queue.IsDone()) {
2842         PtrInfo *pi = queue.GetNext();
2843         pi->mReversedEdges = nsnull;
2844     }
2845
2846     delete mGraph.mReversedEdges;
2847     mGraph.mReversedEdges = nsnull;
2848 }
2849
2850 void
2851 nsCycleCollector::ShouldBeFreed(nsISupports *n)
2852 {
2853     mExpectedGarbage.PutEntry(n);
2854 }
2855
2856 void
2857 nsCycleCollector::WasFreed(nsISupports *n)
2858 {
2859     mExpectedGarbage.RemoveEntry(n);
2860 }
2861 #endif
2862
2863 ////////////////////////////////////////////////////////////////////////
2864 // Module public API (exported in nsCycleCollector.h)
2865 // Just functions that redirect into the singleton, once it's built.
2866 ////////////////////////////////////////////////////////////////////////
2867
2868 void
2869 nsCycleCollector_registerRuntime(PRUint32 langID,
2870                                  nsCycleCollectionLanguageRuntime *rt)
2871 {
2872     if (sCollector)
2873         sCollector->RegisterRuntime(langID, rt);
2874 }
2875
2876
2877 void
2878 nsCycleCollector_forgetRuntime(PRUint32 langID)
2879 {
2880     if (sCollector)
2881         sCollector->ForgetRuntime(langID);
2882 }
2883
2884
2885 PRBool
2886 NS_CycleCollectorSuspect(nsISupports *n)
2887 {
2888     if (sCollector)
2889         return sCollector->Suspect(n);
2890     return PR_FALSE;
2891 }
2892
2893
2894 PRBool
2895 NS_CycleCollectorForget(nsISupports *n)
2896 {
2897     return sCollector ? sCollector->Forget(n) : PR_TRUE;
2898 }
2899
2900
2901 PRUint32
2902 nsCycleCollector_collect()
2903 {
2904     return sCollector ? sCollector->Collect() : 0;
2905 }
2906
2907 PRUint32
2908 nsCycleCollector_suspectedCount()
2909 {
2910     return sCollector ? sCollector->SuspectedCount() : 0;
2911 }
2912
2913 PRBool
2914 nsCycleCollector_beginCollection()
2915 {
2916     return sCollector ? sCollector->BeginCollection() : PR_FALSE;
2917 }
2918
2919 PRBool
2920 nsCycleCollector_finishCollection()
2921 {
2922     return sCollector ? sCollector->FinishCollection() : PR_FALSE;
2923 }
2924
2925 nsresult
2926 nsCycleCollector_startup()
2927 {
2928     NS_ASSERTION(!sCollector, "Forgot to call nsCycleCollector_shutdown?");
2929
2930     sCollector = new nsCycleCollector();
2931     return sCollector ? NS_OK : NS_ERROR_OUT_OF_MEMORY;
2932 }
2933
2934 void
2935 nsCycleCollector_shutdown()
2936 {
2937     if (sCollector) {
2938         sCollector->Shutdown();
2939         delete sCollector;
2940         sCollector = nsnull;
2941     }
2942 }
2943
2944 #ifdef DEBUG
2945 void
2946 nsCycleCollector_DEBUG_shouldBeFreed(nsISupports *n)
2947 {
2948 #ifdef DEBUG_CC
2949     if (sCollector)
2950         sCollector->ShouldBeFreed(n);
2951 #endif
2952 }
2953
2954 void
2955 nsCycleCollector_DEBUG_wasFreed(nsISupports *n)
2956 {
2957 #ifdef DEBUG_CC
2958     if (sCollector)
2959         sCollector->WasFreed(n);
2960 #endif
2961 }
2962 #endif