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
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/
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
16 * The Original Code is mozilla.org code.
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.
24 * L. David Baron <dbaron@dbaron.org>, Mozilla Corporation
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.
38 * ***** END LICENSE BLOCK ***** */
41 // This file implements a garbage-cycle collector based on the paper
43 // Concurrent Cycle Collection in Reference Counted Systems
44 // Bacon & Rajan (2001), ECOOP 2001 / Springer LNCS vol 2072
46 // We are not using the concurrent or acyclic cases of that paper; so
47 // the green, red and orange colors are not used.
49 // The collector is based on tracking pointers of four colors:
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.
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).
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.
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.
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.
78 // An XPCOM object is either scan-safe or scan-unsafe, purple-safe or
81 // An object is scan-safe if:
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).
89 // An object is purple-safe if it satisfies the following properties:
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.
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.
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
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).
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.
121 #if !defined(__MINGW32__) && !defined(WINCE)
128 #include "nsCycleCollectionParticipant.h"
129 #include "nsIProgrammingLanguage.h"
130 #include "nsBaseHashtable.h"
131 #include "nsHashKeys.h"
133 #include "nsCycleCollector.h"
134 #include "nsThreadUtils.h"
139 #include "nsPrintfCString.h"
140 #include "nsTArray.h"
141 #include "mozilla/FunctionTimer.h"
142 #include "nsIObserverService.h"
143 #include "nsIConsoleService.h"
144 #include "nsServiceManagerUtils.h"
145 #include "nsThreadUtils.h"
146 #include "nsTPtrArray.h"
147 #include "nsTArray.h"
148 #include "mozilla/Services.h"
149 #include "nsICycleCollectorListener.h"
158 //#define COLLECT_TIME_DEBUG
161 #define IF_DEBUG_CC_PARAM(_p) , _p
162 #define IF_DEBUG_CC_ONLY_PARAM(_p) _p
164 #define IF_DEBUG_CC_PARAM(_p)
165 #define IF_DEBUG_CC_ONLY_PARAM(_p)
168 #define DEFAULT_SHUTDOWN_COLLECTIONS 5
170 #define SHUTDOWN_COLLECTIONS(params) params.mShutdownCollections
172 #define SHUTDOWN_COLLECTIONS(params) DEFAULT_SHUTDOWN_COLLECTIONS
175 // Various parameters of this collector can be tuned using environment
178 struct nsCycleCollectorParams
185 PRBool mFaultIsFatal
;
188 PRUint32 mShutdownCollections
;
191 nsCycleCollectorParams() :
193 mDoNothing (PR_GetEnv("XPCOM_CC_DO_NOTHING") != NULL
),
194 mReportStats (PR_GetEnv("XPCOM_CC_REPORT_STATS") != NULL
),
195 mHookMalloc (PR_GetEnv("XPCOM_CC_HOOK_MALLOC") != NULL
),
196 mDrawGraphs (PR_GetEnv("XPCOM_CC_DRAW_GRAPHS") != NULL
),
197 mFaultIsFatal (PR_GetEnv("XPCOM_CC_FAULT_IS_FATAL") != NULL
),
198 mLogPointers (PR_GetEnv("XPCOM_CC_LOG_POINTERS") != NULL
),
200 mShutdownCollections(DEFAULT_SHUTDOWN_COLLECTIONS
)
202 mDoNothing (PR_FALSE
)
206 char *s
= PR_GetEnv("XPCOM_CC_SHUTDOWN_COLLECTIONS");
208 PR_sscanf(s
, "%d", &mShutdownCollections
);
214 // Various operations involving the collector are recorded in a
215 // statistics table. These are for diagnostics.
217 struct nsCycleCollectorStats
220 PRUint32 mSuccessfulQI
;
222 PRUint32 mVisitedNode
;
223 PRUint32 mWalkedGraph
;
224 PRUint32 mCollectedBytes
;
226 PRUint32 mFreedBytes
;
228 PRUint32 mSetColorGrey
;
229 PRUint32 mSetColorBlack
;
230 PRUint32 mSetColorWhite
;
232 PRUint32 mFailedUnlink
;
233 PRUint32 mCollectedNode
;
235 PRUint32 mSuspectNode
;
236 PRUint32 mForgetNode
;
237 PRUint32 mFreedWhilePurple
;
239 PRUint32 mCollection
;
241 nsCycleCollectorStats()
243 memset(this, 0, sizeof(nsCycleCollectorStats
));
248 fprintf(stderr
, "\f\n");
249 #define DUMP(entry) fprintf(stderr, "%30.30s: %-20.20d\n", #entry, entry)
255 DUMP(mCollectedBytes
);
260 DUMP(mSetColorBlack
);
261 DUMP(mSetColorWhite
);
264 DUMP(mCollectedNode
);
268 DUMP(mFreedWhilePurple
);
277 static PRBool
nsCycleCollector_shouldSuppress(nsISupports
*s
);
278 static void InitMemHook(void);
281 ////////////////////////////////////////////////////////////////////////
283 ////////////////////////////////////////////////////////////////////////
290 // EdgePool allocates arrays of void*, primarily to hold PtrInfo*.
291 // However, at the end of a block, the last two pointers are a null
292 // and then a void** pointing to the next block. This allows
293 // EdgePool::Iterators to be a single word but still capable of crossing
298 mSentinelAndBlocks
[0].block
= nsnull
;
299 mSentinelAndBlocks
[1].block
= nsnull
;
304 NS_ASSERTION(!mSentinelAndBlocks
[0].block
&&
305 !mSentinelAndBlocks
[1].block
,
306 "Didn't call Clear()?");
313 Block
*next
= b
->Next();
318 mSentinelAndBlocks
[0].block
= nsnull
;
319 mSentinelAndBlocks
[1].block
= nsnull
;
324 union PtrInfoOrBlock
{
325 // Use a union to avoid reinterpret_cast and the ensuing
326 // potential aliasing bugs.
331 enum { BlockSize
= 64 * 1024 };
333 PtrInfoOrBlock mPointers
[BlockSize
];
335 mPointers
[BlockSize
- 2].block
= nsnull
; // sentinel
336 mPointers
[BlockSize
- 1].block
= nsnull
; // next block pointer
339 { return mPointers
[BlockSize
- 1].block
; }
340 PtrInfoOrBlock
* Start()
341 { return &mPointers
[0]; }
342 PtrInfoOrBlock
* End()
343 { return &mPointers
[BlockSize
- 2]; }
346 // Store the null sentinel so that we can have valid iterators
347 // before adding any edges and without adding any blocks.
348 PtrInfoOrBlock mSentinelAndBlocks
[2];
350 Block
*& Blocks() { return mSentinelAndBlocks
[1].block
; }
356 Iterator() : mPointer(nsnull
) {}
357 Iterator(PtrInfoOrBlock
*aPointer
) : mPointer(aPointer
) {}
358 Iterator(const Iterator
& aOther
) : mPointer(aOther
.mPointer
) {}
360 Iterator
& operator++()
362 if (mPointer
->ptrInfo
== nsnull
) {
363 // Null pointer is a sentinel for link to the next block.
364 mPointer
= (mPointer
+ 1)->block
->mPointers
;
370 PtrInfo
* operator*() const
372 if (mPointer
->ptrInfo
== nsnull
) {
373 // Null pointer is a sentinel for link to the next block.
374 return (mPointer
+ 1)->block
->mPointers
->ptrInfo
;
376 return mPointer
->ptrInfo
;
378 PRBool
operator==(const Iterator
& aOther
) const
379 { return mPointer
== aOther
.mPointer
; }
380 PRBool
operator!=(const Iterator
& aOther
) const
381 { return mPointer
!= aOther
.mPointer
; }
384 PtrInfoOrBlock
*mPointer
;
388 friend class Builder
;
391 Builder(EdgePool
&aPool
)
392 : mCurrent(&aPool
.mSentinelAndBlocks
[0]),
393 mBlockEnd(&aPool
.mSentinelAndBlocks
[0]),
394 mNextBlockPtr(&aPool
.Blocks())
398 Iterator
Mark() { return Iterator(mCurrent
); }
400 void Add(PtrInfo
* aEdge
) {
401 if (mCurrent
== mBlockEnd
) {
402 Block
*b
= new Block();
404 // This means we just won't collect (some) cycles.
405 NS_NOTREACHED("out of memory, ignoring edges");
409 mCurrent
= b
->Start();
410 mBlockEnd
= b
->End();
411 mNextBlockPtr
= &b
->Next();
413 (mCurrent
++)->ptrInfo
= aEdge
;
416 // mBlockEnd points to space for null sentinel
417 PtrInfoOrBlock
*mCurrent
, *mBlockEnd
;
418 Block
**mNextBlockPtr
;
425 struct ReversedEdge
{
427 nsCString
*mEdgeName
;
434 enum NodeColor
{ black
, white
, grey
};
436 // This structure should be kept as small as possible; we may expect
437 // a million of them to be allocated and touched repeatedly during
438 // each cycle collection.
443 nsCycleCollectionParticipant
*mParticipant
;
445 PRUint32 mInternalRefs
: 30;
447 EdgePool::Iterator mFirstChild
; // first
448 EdgePool::Iterator mLastChild
; // one after last
455 // For finding roots in ExplainLiveExpectedGarbage (when there are
456 // missing calls to suspect or failures to unlink).
457 PRUint32 mSCCIndex
; // strongly connected component
459 // For finding roots in ExplainLiveExpectedGarbage (when nodes
460 // expected to be garbage are black).
461 ReversedEdge
* mReversedEdges
; // linked list
462 PtrInfo
* mShortestPathToExpectedGarbage
;
463 nsCString
* mShortestPathToExpectedGarbageEdgeName
;
465 nsTArray
<nsCString
> mEdgeNames
;
468 PtrInfo(void *aPointer
, nsCycleCollectionParticipant
*aParticipant
469 IF_DEBUG_CC_PARAM(PRUint32 aLangID
)
471 : mPointer(aPointer
),
472 mParticipant(aParticipant
),
483 mReversedEdges(nsnull
),
484 mShortestPathToExpectedGarbage(nsnull
),
485 mShortestPathToExpectedGarbageEdgeName(nsnull
)
493 mEdgeNames
.~nsTArray
<nsCString
>();
497 // Allow NodePool::Block's constructor to compile.
499 NS_NOTREACHED("should never be called");
504 * A structure designed to be used like a linked list of PtrInfo, except
505 * that allocates the PtrInfo 32K-at-a-time.
510 enum { BlockSize
= 32 * 1024 }; // could be int template parameter
513 // We create and destroy Block using NS_Alloc/NS_Free rather
514 // than new and delete to avoid calling its constructor and
516 Block() { NS_NOTREACHED("should never be called"); }
517 ~Block() { NS_NOTREACHED("should never be called"); }
520 PtrInfo mEntries
[BlockSize
];
532 NS_ASSERTION(!mBlocks
, "Didn't call Clear()?");
539 Enumerator
queue(*this);
540 while (!queue
.IsDone()) {
541 queue
.GetNext()->Destroy();
557 friend class Builder
;
560 Builder(NodePool
& aPool
)
561 : mNextBlock(&aPool
.mBlocks
),
565 NS_ASSERTION(aPool
.mBlocks
== nsnull
&& aPool
.mLast
== nsnull
,
568 PtrInfo
*Add(void *aPointer
, nsCycleCollectionParticipant
*aParticipant
569 IF_DEBUG_CC_PARAM(PRUint32 aLangID
)
572 if (mNext
== mBlockEnd
) {
574 if (!(*mNextBlock
= block
=
575 static_cast<Block
*>(NS_Alloc(sizeof(Block
)))))
577 mNext
= block
->mEntries
;
578 mBlockEnd
= block
->mEntries
+ BlockSize
;
579 block
->mNext
= nsnull
;
580 mNextBlock
= &block
->mNext
;
582 return new (mNext
++) PtrInfo(aPointer
, aParticipant
583 IF_DEBUG_CC_PARAM(aLangID
)
593 friend class Enumerator
;
596 Enumerator(NodePool
& aPool
)
597 : mFirstBlock(aPool
.mBlocks
),
605 PRBool
IsDone() const
607 return mNext
== mLast
;
612 NS_ASSERTION(!IsDone(), "calling GetNext when done");
613 if (mNext
== mBlockEnd
) {
614 Block
*nextBlock
= mCurBlock
? mCurBlock
->mNext
: mFirstBlock
;
615 mNext
= nextBlock
->mEntries
;
616 mBlockEnd
= mNext
+ BlockSize
;
617 mCurBlock
= nextBlock
;
622 Block
*mFirstBlock
, *mCurBlock
;
623 // mNext is the next value we want to return, unless mNext == mBlockEnd
624 // NB: mLast is a reference to allow enumerating while building!
625 PtrInfo
*mNext
, *mBlockEnd
, *&mLast
;
634 class GCGraphBuilder
;
642 ReversedEdge
*mReversedEdges
;
645 GCGraph() : mRootCount(0) {
651 // XXX Would be nice to have an nsHashSet<KeyType> API that has
652 // Add/Remove/Has rather than PutEntry/RemoveEntry/GetEntry.
653 typedef nsTHashtable
<nsVoidPtrHashKey
> PointerSet
;
656 ToParticipant(nsISupports
*s
, nsXPCOMCycleCollectionParticipant
**cp
);
658 struct nsPurpleBuffer
663 nsPurpleBufferEntry mEntries
[128];
665 Block() : mNext(nsnull
) {}
668 // This class wraps a linked list of the elements in the purple
671 nsCycleCollectorParams
&mParams
;
674 nsPurpleBufferEntry
*mFreeList
;
676 // For objects compiled against Gecko 1.9 and 1.9.1.
677 PointerSet mCompatObjects
;
679 PointerSet mNormalObjects
; // duplicates our blocks
680 nsCycleCollectorStats
&mStats
;
684 nsPurpleBuffer(nsCycleCollectorParams
¶ms
,
685 nsCycleCollectorStats
&stats
)
690 mNormalObjects
.Init();
691 mCompatObjects
.Init();
694 nsPurpleBuffer(nsCycleCollectorParams
¶ms
)
698 mCompatObjects
.Init();
711 StartBlock(&mFirstBlock
);
714 void StartBlock(Block
*aBlock
)
716 NS_ABORT_IF_FALSE(!mFreeList
, "should not have free list");
718 // Put all the entries in the block on the free list.
719 nsPurpleBufferEntry
*entries
= aBlock
->mEntries
;
721 for (PRUint32 i
= 1; i
< NS_ARRAY_LENGTH(aBlock
->mEntries
); ++i
) {
722 entries
[i
- 1].mNextInFreeList
=
723 (nsPurpleBufferEntry
*)(PRUword(entries
+ i
) | 1);
725 entries
[NS_ARRAY_LENGTH(aBlock
->mEntries
) - 1].mNextInFreeList
=
726 (nsPurpleBufferEntry
*)1;
732 UnmarkRemainingPurple(&mFirstBlock
);
733 Block
*b
= mFirstBlock
.mNext
;
736 UnmarkRemainingPurple(b
);
737 Block
*next
= b
->mNext
;
741 mFirstBlock
.mNext
= nsnull
;
744 void UnmarkRemainingPurple(Block
*b
)
746 for (nsPurpleBufferEntry
*e
= b
->mEntries
,
747 *eEnd
= e
+ NS_ARRAY_LENGTH(b
->mEntries
);
749 if (!(PRUword(e
->mObject
) & PRUword(1))) {
750 // This is a real entry (rather than something on the
753 nsXPCOMCycleCollectionParticipant
*cp
;
754 ToParticipant(e
->mObject
, &cp
);
756 cp
->UnmarkPurple(e
->mObject
);
765 void SelectPointers(GCGraphBuilder
&builder
);
768 void NoteAll(GCGraphBuilder
&builder
);
770 PRBool
Exists(void *p
) const
772 return mNormalObjects
.GetEntry(p
) || mCompatObjects
.GetEntry(p
);
776 nsPurpleBufferEntry
* NewEntry()
779 Block
*b
= new Block
;
785 // Add the new block as the second block in the list.
786 b
->mNext
= mFirstBlock
.mNext
;
787 mFirstBlock
.mNext
= b
;
790 nsPurpleBufferEntry
*e
= mFreeList
;
791 mFreeList
= (nsPurpleBufferEntry
*)
792 (PRUword(mFreeList
->mNextInFreeList
) & ~PRUword(1));
796 nsPurpleBufferEntry
* Put(nsISupports
*p
)
798 nsPurpleBufferEntry
*e
= NewEntry();
808 mNormalObjects
.PutEntry(p
);
811 // Caller is responsible for filling in result's mRefCnt.
815 void Remove(nsPurpleBufferEntry
*e
)
817 NS_ASSERTION(mCount
!= 0, "must have entries");
820 mNormalObjects
.RemoveEntry(e
->mObject
);
824 (nsPurpleBufferEntry
*)(PRUword(mFreeList
) | PRUword(1));
830 PRBool
PutCompatObject(nsISupports
*p
)
833 return !!mCompatObjects
.PutEntry(p
);
836 void RemoveCompatObject(nsISupports
*p
)
839 mCompatObjects
.RemoveEntry(p
);
842 PRUint32
Count() const
848 struct CallbackClosure
850 CallbackClosure(nsPurpleBuffer
*aPurpleBuffer
, GCGraphBuilder
&aBuilder
)
851 : mPurpleBuffer(aPurpleBuffer
),
855 nsPurpleBuffer
*mPurpleBuffer
;
856 GCGraphBuilder
&mBuilder
;
860 AddPurpleRoot(GCGraphBuilder
&builder
, nsISupports
*root
);
862 static PLDHashOperator
863 selectionCallback(nsVoidPtrHashKey
* key
, void* userArg
)
865 CallbackClosure
*closure
= static_cast<CallbackClosure
*>(userArg
);
866 if (AddPurpleRoot(closure
->mBuilder
,
867 static_cast<nsISupports
*>(
868 const_cast<void*>(key
->GetKey()))))
869 return PL_DHASH_REMOVE
;
871 return PL_DHASH_NEXT
;
875 nsPurpleBuffer::SelectPointers(GCGraphBuilder
&aBuilder
)
878 NS_ABORT_IF_FALSE(mCompatObjects
.Count() + mNormalObjects
.Count() ==
880 "count out of sync");
883 if (mCompatObjects
.Count()) {
884 mCount
-= mCompatObjects
.Count();
885 CallbackClosure
closure(this, aBuilder
);
886 mCompatObjects
.EnumerateEntries(selectionCallback
, &closure
);
887 mCount
+= mCompatObjects
.Count(); // in case of allocation failure
890 // Walk through all the blocks.
891 for (Block
*b
= &mFirstBlock
; b
; b
= b
->mNext
) {
892 for (nsPurpleBufferEntry
*e
= b
->mEntries
,
893 *eEnd
= e
+ NS_ARRAY_LENGTH(b
->mEntries
);
895 if (!(PRUword(e
->mObject
) & PRUword(1))) {
896 // This is a real entry (rather than something on the
898 if (!e
->mObject
|| AddPurpleRoot(aBuilder
, e
->mObject
)) {
900 mNormalObjects
.RemoveEntry(e
->mObject
);
903 // Put this entry on the free list in case some
904 // call to AddPurpleRoot fails and we don't rebuild
905 // the free list below.
906 e
->mNextInFreeList
= (nsPurpleBufferEntry
*)
907 (PRUword(mFreeList
) | PRUword(1));
914 NS_WARN_IF_FALSE(mCount
== 0, "AddPurpleRoot failed");
923 ////////////////////////////////////////////////////////////////////////
924 // Implement the LanguageRuntime interface for C++/XPCOM
925 ////////////////////////////////////////////////////////////////////////
928 struct nsCycleCollectionXPCOMRuntime
:
929 public nsCycleCollectionLanguageRuntime
931 nsresult
BeginCycleCollection(nsCycleCollectionTraversalCallback
&cb
,
932 bool explainLiveExpectedGarbage
)
937 nsresult
FinishCycleCollection()
942 inline nsCycleCollectionParticipant
*ToParticipant(void *p
);
945 virtual void PrintAllReferencesTo(void *p
) {}
949 struct nsCycleCollector
951 PRBool mCollectionInProgress
;
952 PRBool mScanInProgress
;
953 PRBool mFollowupCollection
;
954 PRUint32 mCollectedObjects
;
955 PRBool mFirstCollection
;
957 nsCycleCollectionLanguageRuntime
*mRuntimes
[nsIProgrammingLanguage::MAX
+1];
958 nsCycleCollectionXPCOMRuntime mXPCOMRuntime
;
962 nsCycleCollectorParams mParams
;
964 nsTPtrArray
<PtrInfo
> *mWhiteNodes
;
965 PRUint32 mWhiteNodeCount
;
967 nsPurpleBuffer mPurpleBuf
;
969 void RegisterRuntime(PRUint32 langID
,
970 nsCycleCollectionLanguageRuntime
*rt
);
971 nsCycleCollectionLanguageRuntime
* GetRuntime(PRUint32 langID
);
972 void ForgetRuntime(PRUint32 langID
);
974 void SelectPurple(GCGraphBuilder
&builder
);
975 void MarkRoots(GCGraphBuilder
&builder
);
978 PRBool
CollectWhite(); // returns whether anything was collected
983 // The first pair of Suspect and Forget functions are only used by
984 // old XPCOM binary components.
985 PRBool
Suspect(nsISupports
*n
);
986 PRBool
Forget(nsISupports
*n
);
987 nsPurpleBufferEntry
* Suspect2(nsISupports
*n
);
988 PRBool
Forget2(nsPurpleBufferEntry
*e
);
990 PRUint32
Collect(PRUint32 aTryCollections
,
991 nsICycleCollectorListener
*aListener
);
992 PRBool
BeginCollection(nsICycleCollectorListener
*aListener
);
993 PRBool
FinishCollection();
994 PRUint32
SuspectedCount();
999 mGraph
.mNodes
.Clear();
1000 mGraph
.mEdges
.Clear();
1001 mGraph
.mRootCount
= 0;
1005 nsCycleCollectorStats mStats
;
1009 void Allocated(void *n
, size_t sz
);
1010 void Freed(void *n
);
1012 void ExplainLiveExpectedGarbage();
1013 PRBool
CreateReversedEdges();
1014 void DestroyReversedEdges();
1015 void ShouldBeFreed(nsISupports
*n
);
1016 void WasFreed(nsISupports
*n
);
1017 PointerSet mExpectedGarbage
;
1023 * GraphWalker is templatized over a Visitor class that must provide
1024 * the following two methods:
1026 * PRBool ShouldVisitNode(PtrInfo const *pi);
1027 * void VisitNode(PtrInfo *pi);
1029 template <class Visitor
>
1035 void DoWalk(nsDeque
&aQueue
);
1038 void Walk(PtrInfo
*s0
);
1039 void WalkFromRoots(GCGraph
&aGraph
);
1040 // copy-constructing the visitor should be cheap, and less
1041 // indirection than using a reference
1042 GraphWalker(const Visitor aVisitor
) : mVisitor(aVisitor
) {}
1046 ////////////////////////////////////////////////////////////////////////
1047 // The static collector object
1048 ////////////////////////////////////////////////////////////////////////
1051 static nsCycleCollector
*sCollector
= nsnull
;
1054 ////////////////////////////////////////////////////////////////////////
1055 // Utility functions
1056 ////////////////////////////////////////////////////////////////////////
1058 class CCRunnableFaultReport
: public nsRunnable
{
1060 CCRunnableFaultReport(const nsCString
& report
)
1062 CopyUTF8toUTF16(report
, mReport
);
1066 nsCOMPtr
<nsIObserverService
> obs
=
1067 do_GetService(NS_OBSERVERSERVICE_CONTRACTID
);
1069 obs
->NotifyObservers(nsnull
, "cycle-collector-fault",
1073 nsCOMPtr
<nsIConsoleService
> cons
=
1074 do_GetService(NS_CONSOLESERVICE_CONTRACTID
);
1076 cons
->LogStringMessage(mReport
.get());
1086 Fault(const char *msg
, const void *ptr
=nsnull
)
1089 // This should be nearly impossible, but just in case.
1093 if (sCollector
->mParams
.mFaultIsFatal
) {
1096 printf("Fatal fault in cycle collector: %s (ptr: %p)\n", msg
, ptr
);
1098 printf("Fatal fault in cycle collector: %s\n", msg
);
1104 nsPrintfCString
str(256, "Fault in cycle collector: %s (ptr: %p)\n",
1106 NS_NOTREACHED(str
.get());
1108 // When faults are not fatal, we assume we're running in a
1109 // production environment and we therefore want to disable the
1110 // collector on a fault. This will unfortunately cause the browser
1111 // to leak pretty fast wherever creates cyclical garbage, but it's
1112 // probably a better user experience than crashing. Besides, we
1113 // *should* never hit a fault.
1115 sCollector
->mParams
.mDoNothing
= PR_TRUE
;
1117 // Report to observers off an event so we don't run JS under GC
1118 // (which is where we might be right now).
1119 nsCOMPtr
<nsIRunnable
> ev
= new CCRunnableFaultReport(str
);
1120 NS_DispatchToMainThread(ev
);
1125 Fault(const char *msg
, PtrInfo
*pi
)
1127 printf("Fault in cycle collector: %s\n"
1128 " while operating on pointer %p %s\n",
1129 msg
, pi
->mPointer
, pi
->mName
);
1130 if (pi
->mInternalRefs
) {
1131 printf(" which has internal references from:\n");
1132 NodePool::Enumerator
queue(sCollector
->mGraph
.mNodes
);
1133 while (!queue
.IsDone()) {
1134 PtrInfo
*ppi
= queue
.GetNext();
1135 for (EdgePool::Iterator e
= ppi
->mFirstChild
, e_end
= ppi
->mLastChild
;
1138 printf(" %p %s\n", ppi
->mPointer
, ppi
->mName
);
1144 Fault(msg
, pi
->mPointer
);
1148 Fault(const char *msg
, PtrInfo
*pi
)
1150 Fault(msg
, pi
->mPointer
);
1155 AbortIfOffMainThreadIfCheckFast()
1157 #if defined(XP_WIN) || defined(NS_TLS)
1158 if (!NS_IsMainThread()) {
1159 NS_RUNTIMEABORT("Main-thread-only object used off the main thread");
1164 static nsISupports
*
1165 canonicalize(nsISupports
*in
)
1167 nsCOMPtr
<nsISupports
> child
;
1168 in
->QueryInterface(NS_GET_IID(nsCycleCollectionISupports
),
1169 getter_AddRefs(child
));
1174 ToParticipant(nsISupports
*s
, nsXPCOMCycleCollectionParticipant
**cp
)
1176 // We use QI to move from an nsISupports to an
1177 // nsXPCOMCycleCollectionParticipant, which is a per-class singleton helper
1178 // object that implements traversal and unlinking logic for the nsISupports
1180 CallQueryInterface(s
, cp
);
1183 ++sCollector
->mStats
.mSuccessfulQI
;
1185 ++sCollector
->mStats
.mFailedQI
;
1189 nsCycleCollectionParticipant
*
1190 nsCycleCollectionXPCOMRuntime::ToParticipant(void *p
)
1192 nsXPCOMCycleCollectionParticipant
*cp
;
1193 ::ToParticipant(static_cast<nsISupports
*>(p
), &cp
);
1198 template <class Visitor
>
1200 GraphWalker
<Visitor
>::Walk(PtrInfo
*s0
)
1207 template <class Visitor
>
1209 GraphWalker
<Visitor
>::WalkFromRoots(GCGraph
& aGraph
)
1212 NodePool::Enumerator
etor(aGraph
.mNodes
);
1213 for (PRUint32 i
= 0; i
< aGraph
.mRootCount
; ++i
) {
1214 queue
.Push(etor
.GetNext());
1219 template <class Visitor
>
1221 GraphWalker
<Visitor
>::DoWalk(nsDeque
&aQueue
)
1223 // Use a aQueue to match the breadth-first traversal used when we
1224 // built the graph, for hopefully-better locality.
1225 while (aQueue
.GetSize() > 0) {
1226 PtrInfo
*pi
= static_cast<PtrInfo
*>(aQueue
.PopFront());
1228 if (mVisitor
.ShouldVisitNode(pi
)) {
1229 mVisitor
.VisitNode(pi
);
1230 for (EdgePool::Iterator child
= pi
->mFirstChild
,
1231 child_end
= pi
->mLastChild
;
1232 child
!= child_end
; ++child
) {
1233 aQueue
.Push(*child
);
1239 sCollector
->mStats
.mWalkedGraph
++;
1244 class nsCycleCollectorLogger
: public nsICycleCollectorListener
1247 nsCycleCollectorLogger() : mStream(nsnull
)
1250 ~nsCycleCollectorLogger()
1261 sprintf(name
, "cc-edges-%d.log", ++gLogCounter
);
1262 mStream
= fopen(name
, "w");
1264 return mStream
? NS_OK
: NS_ERROR_FAILURE
;
1266 NS_IMETHOD
NoteObject(PRUint64 aAddress
, const char *aObjectDescription
)
1268 fprintf(mStream
, "%p %s\n", (void*)aAddress
, aObjectDescription
);
1272 NS_IMETHOD
NoteEdge(PRUint64 aFromAddress
, PRUint64 aToAddress
,
1273 const char *aEdgeName
)
1275 fprintf(mStream
, "> %p %s\n", (void*)aToAddress
, aEdgeName
);
1279 NS_IMETHOD
BeginDescriptions()
1281 fputs("==========\n", mStream
);
1285 NS_IMETHOD
DescribeRefcountedObject(PRUint64 aAddress
, PRUint32 aKnownEdges
,
1286 PRUint32 aTotalEdges
)
1288 PRBool root
= aKnownEdges
!= aTotalEdges
;
1289 fprintf(mStream
, "%p", (void*)aAddress
);
1291 fprintf(mStream
, " [root] [%u/%u]", aKnownEdges
, aTotalEdges
);
1293 fputc('\n', mStream
);
1297 NS_IMETHOD
DescribeGCedObject(PRUint64 aAddress
, PRBool aMarked
)
1299 fprintf(mStream
, "%p%s\n", (void*)aAddress
, aMarked
? " [root]" : "");
1314 static PRUint32 gLogCounter
;
1317 NS_IMPL_ISUPPORTS1(nsCycleCollectorLogger
, nsICycleCollectorListener
)
1319 PRUint32
nsCycleCollectorLogger::gLogCounter
= 0;
1322 nsCycleCollectorLoggerConstructor(nsISupports
* aOuter
,
1324 void* *aInstancePtr
)
1326 NS_ENSURE_TRUE(!aOuter
, NS_ERROR_NO_AGGREGATION
);
1328 nsISupports
*logger
= new nsCycleCollectorLogger();
1330 return logger
->QueryInterface(aIID
, aInstancePtr
);
1333 ////////////////////////////////////////////////////////////////////////
1334 // Bacon & Rajan's |MarkRoots| routine.
1335 ////////////////////////////////////////////////////////////////////////
1337 struct PtrToNodeEntry
: public PLDHashEntryHdr
1339 // The key is mNode->mPointer
1344 PtrToNodeMatchEntry(PLDHashTable
*table
,
1345 const PLDHashEntryHdr
*entry
,
1348 const PtrToNodeEntry
*n
= static_cast<const PtrToNodeEntry
*>(entry
);
1349 return n
->mNode
->mPointer
== key
;
1352 static PLDHashTableOps PtrNodeOps
= {
1355 PL_DHashVoidPtrKeyStub
,
1356 PtrToNodeMatchEntry
,
1357 PL_DHashMoveEntryStub
,
1358 PL_DHashClearEntryStub
,
1359 PL_DHashFinalizeStub
,
1363 class GCGraphBuilder
: public nsCycleCollectionTraversalCallback
1366 NodePool::Builder mNodeBuilder
;
1367 EdgePool::Builder mEdgeBuilder
;
1368 PLDHashTable mPtrToNodeMap
;
1370 nsCycleCollectionLanguageRuntime
**mRuntimes
; // weak, from nsCycleCollector
1371 nsCString mNextEdgeName
;
1372 nsCOMPtr
<nsICycleCollectorListener
> mListener
;
1375 GCGraphBuilder(GCGraph
&aGraph
,
1376 nsCycleCollectionLanguageRuntime
**aRuntimes
,
1377 nsICycleCollectorListener
*aListener
);
1381 PRUint32
Count() const { return mPtrToNodeMap
.entryCount
; }
1384 PtrInfo
* AddNode(void *s
, nsCycleCollectionParticipant
*aParticipant
,
1387 PtrInfo
* AddNode(void *s
, nsCycleCollectionParticipant
*aParticipant
);
1388 PtrInfo
* AddNode(void *s
, nsCycleCollectionParticipant
*aParticipant
,
1391 return AddNode(s
, aParticipant
);
1394 void Traverse(PtrInfo
* aPtrInfo
);
1396 // nsCycleCollectionTraversalCallback methods.
1397 NS_IMETHOD_(void) NoteXPCOMRoot(nsISupports
*root
);
1400 NS_IMETHOD_(void) DescribeNode(CCNodeType type
, nsrefcnt refCount
,
1401 size_t objSz
, const char *objName
);
1402 NS_IMETHOD_(void) NoteRoot(PRUint32 langID
, void *child
,
1403 nsCycleCollectionParticipant
* participant
);
1404 NS_IMETHOD_(void) NoteXPCOMChild(nsISupports
*child
);
1405 NS_IMETHOD_(void) NoteNativeChild(void *child
,
1406 nsCycleCollectionParticipant
*participant
);
1407 NS_IMETHOD_(void) NoteScriptChild(PRUint32 langID
, void *child
);
1408 NS_IMETHOD_(void) NoteNextEdgeName(const char* name
);
1411 GCGraphBuilder::GCGraphBuilder(GCGraph
&aGraph
,
1412 nsCycleCollectionLanguageRuntime
**aRuntimes
,
1413 nsICycleCollectorListener
*aListener
)
1414 : mNodeBuilder(aGraph
.mNodes
),
1415 mEdgeBuilder(aGraph
.mEdges
),
1416 mRuntimes(aRuntimes
),
1417 mListener(aListener
)
1419 if (!PL_DHashTableInit(&mPtrToNodeMap
, &PtrNodeOps
, nsnull
,
1420 sizeof(PtrToNodeEntry
), 32768))
1421 mPtrToNodeMap
.ops
= nsnull
;
1422 // We want all edges and all info if DEBUG_CC is set or if we have a
1423 // listener. Do we want them all the time?
1428 mFlags
|= nsCycleCollectionTraversalCallback::WANT_DEBUG_INFO
|
1429 nsCycleCollectionTraversalCallback::WANT_ALL_TRACES
;
1433 GCGraphBuilder::~GCGraphBuilder()
1435 if (mPtrToNodeMap
.ops
)
1436 PL_DHashTableFinish(&mPtrToNodeMap
);
1440 GCGraphBuilder::Initialized()
1442 return !!mPtrToNodeMap
.ops
;
1446 GCGraphBuilder::AddNode(void *s
, nsCycleCollectionParticipant
*aParticipant
1447 IF_DEBUG_CC_PARAM(PRUint32 aLangID
)
1450 PtrToNodeEntry
*e
= static_cast<PtrToNodeEntry
*>(PL_DHashTableOperate(&mPtrToNodeMap
, s
, PL_DHASH_ADD
));
1457 result
= mNodeBuilder
.Add(s
, aParticipant
1458 IF_DEBUG_CC_PARAM(aLangID
)
1461 PL_DHashTableRawRemove(&mPtrToNodeMap
, e
);
1467 NS_ASSERTION(result
->mParticipant
== aParticipant
,
1468 "nsCycleCollectionParticipant shouldn't change!");
1474 GCGraphBuilder::Traverse(PtrInfo
* aPtrInfo
)
1479 if (!mCurrPi
->mParticipant
) {
1480 Fault("unknown pointer during walk", aPtrInfo
);
1485 mCurrPi
->mFirstChild
= mEdgeBuilder
.Mark();
1487 nsresult rv
= aPtrInfo
->mParticipant
->Traverse(aPtrInfo
->mPointer
, *this);
1488 if (NS_FAILED(rv
)) {
1489 Fault("script pointer traversal failed", aPtrInfo
);
1492 mCurrPi
->mLastChild
= mEdgeBuilder
.Mark();
1495 NS_IMETHODIMP_(void)
1496 GCGraphBuilder::NoteXPCOMRoot(nsISupports
*root
)
1498 root
= canonicalize(root
);
1500 "Don't add objects that don't participate in collection!");
1503 if (nsCycleCollector_shouldSuppress(root
))
1507 nsXPCOMCycleCollectionParticipant
*cp
;
1508 ToParticipant(root
, &cp
);
1510 NoteRoot(nsIProgrammingLanguage::CPLUSPLUS
, root
, cp
);
1514 NS_IMETHODIMP_(void)
1515 GCGraphBuilder::NoteRoot(PRUint32 langID
, void *root
,
1516 nsCycleCollectionParticipant
* participant
)
1518 NS_ASSERTION(root
, "Don't add a null root!");
1520 if (langID
> nsIProgrammingLanguage::MAX
|| !mRuntimes
[langID
]) {
1521 Fault("adding root for unregistered language", root
);
1525 AddNode(root
, participant
, langID
);
1528 NS_IMETHODIMP_(void)
1529 GCGraphBuilder::DescribeNode(CCNodeType type
, nsrefcnt refCount
,
1530 size_t objSz
, const char *objName
)
1533 mCurrPi
->mBytes
= objSz
;
1534 mCurrPi
->mName
= PL_strdup(objName
);
1538 mListener
->NoteObject((PRUint64
)mCurrPi
->mPointer
, objName
);
1541 if (type
== RefCounted
) {
1542 if (refCount
== 0 || refCount
== PR_UINT32_MAX
)
1543 Fault("zero or overflowing refcount", mCurrPi
);
1545 mCurrPi
->mRefCount
= refCount
;
1548 mCurrPi
->mRefCount
= type
== GCMarked
? PR_UINT32_MAX
: 0;
1551 sCollector
->mStats
.mVisitedNode
++;
1555 NS_IMETHODIMP_(void)
1556 GCGraphBuilder::NoteXPCOMChild(nsISupports
*child
)
1559 if (WantDebugInfo()) {
1560 edgeName
.Assign(mNextEdgeName
);
1561 mNextEdgeName
.Truncate();
1563 if (!child
|| !(child
= canonicalize(child
)))
1567 if (nsCycleCollector_shouldSuppress(child
))
1571 nsXPCOMCycleCollectionParticipant
*cp
;
1572 ToParticipant(child
, &cp
);
1574 PtrInfo
*childPi
= AddNode(child
, cp
, nsIProgrammingLanguage::CPLUSPLUS
);
1577 mEdgeBuilder
.Add(childPi
);
1579 mCurrPi
->mEdgeNames
.AppendElement(edgeName
);
1582 mListener
->NoteEdge((PRUint64
)mCurrPi
->mPointer
, (PRUint64
)child
,
1585 ++childPi
->mInternalRefs
;
1589 NS_IMETHODIMP_(void)
1590 GCGraphBuilder::NoteNativeChild(void *child
,
1591 nsCycleCollectionParticipant
*participant
)
1594 if (WantDebugInfo()) {
1595 edgeName
.Assign(mNextEdgeName
);
1596 mNextEdgeName
.Truncate();
1601 NS_ASSERTION(participant
, "Need a nsCycleCollectionParticipant!");
1603 PtrInfo
*childPi
= AddNode(child
, participant
, nsIProgrammingLanguage::CPLUSPLUS
);
1606 mEdgeBuilder
.Add(childPi
);
1608 mCurrPi
->mEdgeNames
.AppendElement(edgeName
);
1611 mListener
->NoteEdge((PRUint64
)mCurrPi
->mPointer
, (PRUint64
)child
,
1614 ++childPi
->mInternalRefs
;
1617 NS_IMETHODIMP_(void)
1618 GCGraphBuilder::NoteScriptChild(PRUint32 langID
, void *child
)
1621 if (WantDebugInfo()) {
1622 edgeName
.Assign(mNextEdgeName
);
1623 mNextEdgeName
.Truncate();
1628 if (langID
> nsIProgrammingLanguage::MAX
) {
1629 Fault("traversing pointer for unknown language", child
);
1633 if (!mRuntimes
[langID
]) {
1634 NS_WARNING("Not collecting cycles involving objects for scripting "
1635 "languages that don't participate in cycle collection.");
1639 nsCycleCollectionParticipant
*cp
= mRuntimes
[langID
]->ToParticipant(child
);
1643 PtrInfo
*childPi
= AddNode(child
, cp
, langID
);
1646 mEdgeBuilder
.Add(childPi
);
1648 mCurrPi
->mEdgeNames
.AppendElement(edgeName
);
1651 mListener
->NoteEdge((PRUint64
)mCurrPi
->mPointer
, (PRUint64
)child
,
1654 ++childPi
->mInternalRefs
;
1657 NS_IMETHODIMP_(void)
1658 GCGraphBuilder::NoteNextEdgeName(const char* name
)
1660 if (WantDebugInfo()) {
1661 mNextEdgeName
= name
;
1666 AddPurpleRoot(GCGraphBuilder
&builder
, nsISupports
*root
)
1668 root
= canonicalize(root
);
1670 "Don't add objects that don't participate in collection!");
1672 nsXPCOMCycleCollectionParticipant
*cp
;
1673 ToParticipant(root
, &cp
);
1675 PtrInfo
*pinfo
= builder
.AddNode(root
, cp
,
1676 nsIProgrammingLanguage::CPLUSPLUS
);
1681 cp
->UnmarkPurple(root
);
1687 static PLDHashOperator
1688 noteAllCallback(nsVoidPtrHashKey
* key
, void* userArg
)
1690 GCGraphBuilder
*builder
= static_cast<GCGraphBuilder
*>(userArg
);
1691 builder
->NoteXPCOMRoot(
1692 static_cast<nsISupports
*>(const_cast<void*>(key
->GetKey())));
1693 return PL_DHASH_NEXT
;
1697 nsPurpleBuffer::NoteAll(GCGraphBuilder
&builder
)
1699 mCompatObjects
.EnumerateEntries(noteAllCallback
, &builder
);
1701 for (Block
*b
= &mFirstBlock
; b
; b
= b
->mNext
) {
1702 for (nsPurpleBufferEntry
*e
= b
->mEntries
,
1703 *eEnd
= e
+ NS_ARRAY_LENGTH(b
->mEntries
);
1705 if (!(PRUword(e
->mObject
) & PRUword(1)) && e
->mObject
) {
1706 builder
.NoteXPCOMRoot(e
->mObject
);
1714 nsCycleCollector::SelectPurple(GCGraphBuilder
&builder
)
1716 mPurpleBuf
.SelectPointers(builder
);
1720 nsCycleCollector::MarkRoots(GCGraphBuilder
&builder
)
1722 mGraph
.mRootCount
= builder
.Count();
1724 // read the PtrInfo out of the graph that we are building
1725 NodePool::Enumerator
queue(mGraph
.mNodes
);
1726 while (!queue
.IsDone()) {
1727 PtrInfo
*pi
= queue
.GetNext();
1728 builder
.Traverse(pi
);
1733 ////////////////////////////////////////////////////////////////////////
1734 // Bacon & Rajan's |ScanRoots| routine.
1735 ////////////////////////////////////////////////////////////////////////
1738 struct ScanBlackVisitor
1740 ScanBlackVisitor(PRUint32
&aWhiteNodeCount
)
1741 : mWhiteNodeCount(aWhiteNodeCount
)
1745 PRBool
ShouldVisitNode(PtrInfo
const *pi
)
1747 return pi
->mColor
!= black
;
1750 void VisitNode(PtrInfo
*pi
)
1752 if (pi
->mColor
== white
)
1756 sCollector
->mStats
.mSetColorBlack
++;
1760 PRUint32
&mWhiteNodeCount
;
1766 scanVisitor(PRUint32
&aWhiteNodeCount
) : mWhiteNodeCount(aWhiteNodeCount
)
1770 PRBool
ShouldVisitNode(PtrInfo
const *pi
)
1772 return pi
->mColor
== grey
;
1775 void VisitNode(PtrInfo
*pi
)
1777 if (pi
->mInternalRefs
> pi
->mRefCount
&& pi
->mRefCount
> 0)
1778 Fault("traversed refs exceed refcount", pi
);
1780 if (pi
->mInternalRefs
== pi
->mRefCount
|| pi
->mRefCount
== 0) {
1784 sCollector
->mStats
.mSetColorWhite
++;
1787 GraphWalker
<ScanBlackVisitor
>(ScanBlackVisitor(mWhiteNodeCount
)).Walk(pi
);
1788 NS_ASSERTION(pi
->mColor
== black
,
1789 "Why didn't ScanBlackVisitor make pi black?");
1793 PRUint32
&mWhiteNodeCount
;
1797 nsCycleCollector::ScanRoots()
1799 mWhiteNodeCount
= 0;
1801 // On the assumption that most nodes will be black, it's
1802 // probably faster to use a GraphWalker than a
1803 // NodePool::Enumerator.
1804 GraphWalker
<scanVisitor
>(scanVisitor(mWhiteNodeCount
)).WalkFromRoots(mGraph
);
1807 // Sanity check: scan should have colored all grey nodes black or
1808 // white. So we ensure we have no grey nodes at this point.
1809 NodePool::Enumerator
etor(mGraph
.mNodes
);
1810 while (!etor
.IsDone())
1812 PtrInfo
*pinfo
= etor
.GetNext();
1813 if (pinfo
->mColor
== grey
) {
1814 Fault("valid grey node after scanning", pinfo
);
1821 ////////////////////////////////////////////////////////////////////////
1822 // Bacon & Rajan's |CollectWhite| routine, somewhat modified.
1823 ////////////////////////////////////////////////////////////////////////
1826 nsCycleCollector::RootWhite()
1828 // Explanation of "somewhat modified": we have no way to collect the
1829 // set of whites "all at once", we have to ask each of them to drop
1830 // their outgoing links and assume this will cause the garbage cycle
1831 // to *mostly* self-destruct (except for the reference we continue
1834 // To do this "safely" we must make sure that the white nodes we're
1835 // operating on are stable for the duration of our operation. So we
1836 // make 3 sets of calls to language runtimes:
1838 // - Root(whites), which should pin the whites in memory.
1839 // - Unlink(whites), which drops outgoing links on each white.
1840 // - Unroot(whites), which returns the whites to normal GC.
1844 NS_ASSERTION(mWhiteNodes
->IsEmpty(),
1845 "FinishCollection wasn't called?");
1847 mWhiteNodes
->SetCapacity(mWhiteNodeCount
);
1849 NodePool::Enumerator
etor(mGraph
.mNodes
);
1850 while (!etor
.IsDone())
1852 PtrInfo
*pinfo
= etor
.GetNext();
1853 if (pinfo
->mColor
== white
&& mWhiteNodes
->AppendElement(pinfo
)) {
1854 rv
= pinfo
->mParticipant
->RootAndUnlinkJSObjects(pinfo
->mPointer
);
1855 if (NS_FAILED(rv
)) {
1856 Fault("Failed root call while unlinking", pinfo
);
1857 mWhiteNodes
->RemoveElementAt(mWhiteNodes
->Length() - 1);
1864 nsCycleCollector::CollectWhite()
1868 #if defined(DEBUG_CC) && !defined(__MINGW32__) && defined(WIN32)
1869 struct _CrtMemState ms1
, ms2
;
1870 _CrtMemCheckpoint(&ms1
);
1873 PRUint32 i
, count
= mWhiteNodes
->Length();
1874 for (i
= 0; i
< count
; ++i
) {
1875 PtrInfo
*pinfo
= mWhiteNodes
->ElementAt(i
);
1876 rv
= pinfo
->mParticipant
->Unlink(pinfo
->mPointer
);
1877 if (NS_FAILED(rv
)) {
1878 Fault("Failed unlink call while unlinking", pinfo
);
1880 mStats
.mFailedUnlink
++;
1885 ++mStats
.mCollectedNode
;
1890 for (i
= 0; i
< count
; ++i
) {
1891 PtrInfo
*pinfo
= mWhiteNodes
->ElementAt(i
);
1892 rv
= pinfo
->mParticipant
->Unroot(pinfo
->mPointer
);
1894 Fault("Failed unroot call while unlinking", pinfo
);
1897 #if defined(DEBUG_CC) && !defined(__MINGW32__) && defined(WIN32)
1898 _CrtMemCheckpoint(&ms2
);
1899 if (ms2
.lTotalCount
< ms1
.lTotalCount
)
1900 mStats
.mFreedBytes
+= (ms1
.lTotalCount
- ms2
.lTotalCount
);
1903 mCollectedObjects
+= count
;
1909 ////////////////////////////////////////////////////////////////////////
1910 // Memory-hooking stuff
1911 // When debugging wild pointers, it sometimes helps to hook malloc and
1912 // free. This stuff is disabled unless you set an environment variable.
1913 ////////////////////////////////////////////////////////////////////////
1915 static PRBool hookedMalloc
= PR_FALSE
;
1917 #if defined(__GLIBC__) && !defined(__UCLIBC__)
1920 static void* (*old_memalign_hook
)(size_t, size_t, const void *);
1921 static void* (*old_realloc_hook
)(void *, size_t, const void *);
1922 static void* (*old_malloc_hook
)(size_t, const void *);
1923 static void (*old_free_hook
)(void *, const void *);
1925 static void* my_memalign_hook(size_t, size_t, const void *);
1926 static void* my_realloc_hook(void *, size_t, const void *);
1927 static void* my_malloc_hook(size_t, const void *);
1928 static void my_free_hook(void *, const void *);
1933 __memalign_hook
= old_memalign_hook
;
1934 __realloc_hook
= old_realloc_hook
;
1935 __malloc_hook
= old_malloc_hook
;
1936 __free_hook
= old_free_hook
;
1942 // Glibc docs recommend re-saving old hooks on
1943 // return from recursive calls. Strangely when
1944 // we do this, we find ourselves in infinite
1947 // old_memalign_hook = __memalign_hook;
1948 // old_realloc_hook = __realloc_hook;
1949 // old_malloc_hook = __malloc_hook;
1950 // old_free_hook = __free_hook;
1956 __memalign_hook
= my_memalign_hook
;
1957 __realloc_hook
= my_realloc_hook
;
1958 __malloc_hook
= my_malloc_hook
;
1959 __free_hook
= my_free_hook
;
1963 my_realloc_hook(void *ptr
, size_t size
, const void *caller
)
1967 install_old_hooks();
1968 result
= realloc(ptr
, size
);
1972 sCollector
->Freed(ptr
);
1973 sCollector
->Allocated(result
, size
);
1976 install_new_hooks();
1983 my_memalign_hook(size_t size
, size_t alignment
, const void *caller
)
1987 install_old_hooks();
1988 result
= memalign(size
, alignment
);
1992 sCollector
->Allocated(result
, size
);
1994 install_new_hooks();
2001 my_free_hook (void *ptr
, const void *caller
)
2003 install_old_hooks();
2008 sCollector
->Freed(ptr
);
2010 install_new_hooks();
2015 my_malloc_hook (size_t size
, const void *caller
)
2019 install_old_hooks();
2020 result
= malloc (size
);
2024 sCollector
->Allocated(result
, size
);
2026 install_new_hooks();
2035 if (!hookedMalloc
) {
2037 install_new_hooks();
2038 hookedMalloc
= PR_TRUE
;
2042 #elif defined(WIN32)
2046 AllocHook(int allocType
, void *userData
, size_t size
, int
2047 blockType
, long requestNumber
, const unsigned char *filename
, int
2050 if (allocType
== _HOOK_FREE
)
2051 sCollector
->Freed(userData
);
2056 static void InitMemHook(void)
2058 if (!hookedMalloc
) {
2059 _CrtSetAllocHook (AllocHook
);
2060 hookedMalloc
= PR_TRUE
;
2063 #endif // __MINGW32__
2065 #elif 0 // defined(XP_MACOSX)
2067 #include <malloc/malloc.h>
2069 static void (*old_free
)(struct _malloc_zone_t
*zone
, void *ptr
);
2072 freehook(struct _malloc_zone_t
*zone
, void *ptr
)
2075 sCollector
->Freed(ptr
);
2076 old_free(zone
, ptr
);
2083 if (!hookedMalloc
) {
2084 malloc_zone_t
*default_zone
= malloc_default_zone();
2085 old_free
= default_zone
->free
;
2086 default_zone
->free
= freehook
;
2087 hookedMalloc
= PR_TRUE
;
2099 #endif // GLIBC / WIN32 / OSX
2102 ////////////////////////////////////////////////////////////////////////
2103 // Collector implementation
2104 ////////////////////////////////////////////////////////////////////////
2106 nsCycleCollector::nsCycleCollector() :
2107 mCollectionInProgress(PR_FALSE
),
2108 mScanInProgress(PR_FALSE
),
2109 mCollectedObjects(0),
2110 mFirstCollection(PR_TRUE
),
2111 mWhiteNodes(nsnull
),
2114 mPurpleBuf(mParams
, mStats
),
2121 mExpectedGarbage
.Init();
2124 memset(mRuntimes
, 0, sizeof(mRuntimes
));
2125 mRuntimes
[nsIProgrammingLanguage::CPLUSPLUS
] = &mXPCOMRuntime
;
2129 nsCycleCollector::~nsCycleCollector()
2135 nsCycleCollector::RegisterRuntime(PRUint32 langID
,
2136 nsCycleCollectionLanguageRuntime
*rt
)
2138 if (mParams
.mDoNothing
)
2141 if (langID
> nsIProgrammingLanguage::MAX
)
2142 Fault("unknown language runtime in registration");
2144 if (mRuntimes
[langID
])
2145 Fault("multiple registrations of language runtime", rt
);
2147 mRuntimes
[langID
] = rt
;
2150 nsCycleCollectionLanguageRuntime
*
2151 nsCycleCollector::GetRuntime(PRUint32 langID
)
2153 if (langID
> nsIProgrammingLanguage::MAX
)
2156 return mRuntimes
[langID
];
2160 nsCycleCollector::ForgetRuntime(PRUint32 langID
)
2162 if (mParams
.mDoNothing
)
2165 if (langID
> nsIProgrammingLanguage::MAX
)
2166 Fault("unknown language runtime in deregistration");
2168 if (! mRuntimes
[langID
])
2169 Fault("forgetting non-registered language runtime");
2171 mRuntimes
[langID
] = nsnull
;
2177 public nsCycleCollectionTraversalCallback
2180 static char *sSuppressionList
;
2181 static PRBool sInitialized
;
2182 PRBool mSuppressThisNode
;
2188 PRBool
shouldSuppress(nsISupports
*s
)
2190 if (!sInitialized
) {
2191 sSuppressionList
= PR_GetEnv("XPCOM_CC_SUPPRESS");
2192 sInitialized
= PR_TRUE
;
2194 if (sSuppressionList
== nsnull
) {
2195 mSuppressThisNode
= PR_FALSE
;
2198 nsXPCOMCycleCollectionParticipant
*cp
;
2199 rv
= CallQueryInterface(s
, &cp
);
2200 if (NS_FAILED(rv
)) {
2201 Fault("checking suppression on wrong type of pointer", s
);
2204 cp
->Traverse(s
, *this);
2206 return mSuppressThisNode
;
2209 NS_IMETHOD_(void) DescribeNode(CCNodeType type
, nsrefcnt refCount
,
2210 size_t objSz
, const char *objName
)
2212 mSuppressThisNode
= (PL_strstr(sSuppressionList
, objName
) != nsnull
);
2215 NS_IMETHOD_(void) NoteXPCOMRoot(nsISupports
*root
) {};
2216 NS_IMETHOD_(void) NoteRoot(PRUint32 langID
, void *root
,
2217 nsCycleCollectionParticipant
* participant
) {};
2218 NS_IMETHOD_(void) NoteXPCOMChild(nsISupports
*child
) {}
2219 NS_IMETHOD_(void) NoteScriptChild(PRUint32 langID
, void *child
) {}
2220 NS_IMETHOD_(void) NoteNativeChild(void *child
,
2221 nsCycleCollectionParticipant
*participant
) {}
2222 NS_IMETHOD_(void) NoteNextEdgeName(const char* name
) {}
2225 char *Suppressor::sSuppressionList
= nsnull
;
2226 PRBool
Suppressor::sInitialized
= PR_FALSE
;
2229 nsCycleCollector_shouldSuppress(nsISupports
*s
)
2232 return supp
.shouldSuppress(s
);
2238 nsCycleCollector_isScanSafe(nsISupports
*s
)
2243 nsXPCOMCycleCollectionParticipant
*cp
;
2244 ToParticipant(s
, &cp
);
2246 return cp
!= nsnull
;
2251 nsCycleCollector::Suspect(nsISupports
*n
)
2253 AbortIfOffMainThreadIfCheckFast();
2255 // Re-entering ::Suspect during collection used to be a fault, but
2256 // we are canonicalizing nsISupports pointers using QI, so we will
2257 // see some spurious refcount traffic here.
2259 if (mScanInProgress
)
2262 NS_ASSERTION(nsCycleCollector_isScanSafe(n
),
2263 "suspected a non-scansafe pointer");
2265 if (mParams
.mDoNothing
)
2269 mStats
.mSuspectNode
++;
2271 if (nsCycleCollector_shouldSuppress(n
))
2275 if (mParams
.mHookMalloc
)
2279 if (mParams
.mLogPointers
) {
2281 mPtrLog
= fopen("pointer_log", "w");
2282 fprintf(mPtrLog
, "S %p\n", static_cast<void*>(n
));
2286 return mPurpleBuf
.PutCompatObject(n
);
2291 nsCycleCollector::Forget(nsISupports
*n
)
2293 AbortIfOffMainThreadIfCheckFast();
2295 // Re-entering ::Forget during collection used to be a fault, but
2296 // we are canonicalizing nsISupports pointers using QI, so we will
2297 // see some spurious refcount traffic here.
2299 if (mScanInProgress
)
2302 if (mParams
.mDoNothing
)
2303 return PR_TRUE
; // it's as good as forgotten
2306 mStats
.mForgetNode
++;
2309 if (mParams
.mHookMalloc
)
2313 if (mParams
.mLogPointers
) {
2315 mPtrLog
= fopen("pointer_log", "w");
2316 fprintf(mPtrLog
, "F %p\n", static_cast<void*>(n
));
2320 mPurpleBuf
.RemoveCompatObject(n
);
2324 nsPurpleBufferEntry
*
2325 nsCycleCollector::Suspect2(nsISupports
*n
)
2327 AbortIfOffMainThreadIfCheckFast();
2329 // Re-entering ::Suspect during collection used to be a fault, but
2330 // we are canonicalizing nsISupports pointers using QI, so we will
2331 // see some spurious refcount traffic here.
2333 if (mScanInProgress
)
2336 NS_ASSERTION(nsCycleCollector_isScanSafe(n
),
2337 "suspected a non-scansafe pointer");
2339 if (mParams
.mDoNothing
)
2343 mStats
.mSuspectNode
++;
2345 if (nsCycleCollector_shouldSuppress(n
))
2349 if (mParams
.mHookMalloc
)
2353 if (mParams
.mLogPointers
) {
2355 mPtrLog
= fopen("pointer_log", "w");
2356 fprintf(mPtrLog
, "S %p\n", static_cast<void*>(n
));
2360 // Caller is responsible for filling in result's mRefCnt.
2361 return mPurpleBuf
.Put(n
);
2366 nsCycleCollector::Forget2(nsPurpleBufferEntry
*e
)
2368 AbortIfOffMainThreadIfCheckFast();
2370 // Re-entering ::Forget during collection used to be a fault, but
2371 // we are canonicalizing nsISupports pointers using QI, so we will
2372 // see some spurious refcount traffic here.
2374 if (mScanInProgress
)
2378 mStats
.mForgetNode
++;
2381 if (mParams
.mHookMalloc
)
2385 if (mParams
.mLogPointers
) {
2387 mPtrLog
= fopen("pointer_log", "w");
2388 fprintf(mPtrLog
, "F %p\n", static_cast<void*>(e
->mObject
));
2392 mPurpleBuf
.Remove(e
);
2398 nsCycleCollector::Allocated(void *n
, size_t sz
)
2403 nsCycleCollector::Freed(void *n
)
2405 mStats
.mFreeCalls
++;
2408 // Ignore null pointers coming through
2412 if (mPurpleBuf
.Exists(n
)) {
2413 mStats
.mForgetNode
++;
2414 mStats
.mFreedWhilePurple
++;
2415 Fault("freed while purple", n
);
2417 if (mParams
.mLogPointers
) {
2419 mPtrLog
= fopen("pointer_log", "w");
2420 fprintf(mPtrLog
, "R %p\n", n
);
2427 nsCycleCollector::Collect(PRUint32 aTryCollections
,
2428 nsICycleCollectorListener
*aListener
)
2430 #if defined(DEBUG_CC) && !defined(__MINGW32__)
2431 if (!mParams
.mDoNothing
&& mParams
.mHookMalloc
)
2435 // This can legitimately happen in a few cases. See bug 383651.
2436 if (mCollectionInProgress
)
2441 #ifdef COLLECT_TIME_DEBUG
2442 printf("cc: Starting nsCycleCollector::Collect(%d)\n", aTryCollections
);
2443 PRTime start
= PR_Now();
2447 if (!aListener
&& mParams
.mDrawGraphs
) {
2448 aListener
= new nsCycleCollectorLogger();
2452 mCollectionInProgress
= PR_TRUE
;
2454 nsCOMPtr
<nsIObserverService
> obs
=
2455 mozilla::services::GetObserverService();
2457 obs
->NotifyObservers(nsnull
, "cycle-collector-begin", nsnull
);
2459 mFollowupCollection
= PR_FALSE
;
2460 mCollectedObjects
= 0;
2461 nsAutoTPtrArray
<PtrInfo
, 4000> whiteNodes
;
2462 mWhiteNodes
= &whiteNodes
;
2464 PRUint32 totalCollections
= 0;
2465 while (aTryCollections
> totalCollections
) {
2466 // The cycle collector uses the mark bitmap to discover what JS objects
2467 // were reachable only from XPConnect roots that might participate in
2468 // cycles. If this is the first cycle collection after startup force
2469 // a garbage collection, otherwise the GC might not have run yet and
2470 // the bitmap is invalid.
2471 // Also force a JS GC if we are doing our infamous shutdown dance
2472 // (aTryCollections > 1).
2473 if ((mFirstCollection
|| aTryCollections
> 1) &&
2474 mRuntimes
[nsIProgrammingLanguage::JAVASCRIPT
]) {
2475 #ifdef COLLECT_TIME_DEBUG
2476 PRTime start
= PR_Now();
2478 static_cast<nsCycleCollectionJSRuntime
*>
2479 (mRuntimes
[nsIProgrammingLanguage::JAVASCRIPT
])->Collect();
2480 mFirstCollection
= PR_FALSE
;
2481 #ifdef COLLECT_TIME_DEBUG
2482 printf("cc: GC() took %lldms\n", (PR_Now() - start
) / PR_USEC_PER_MSEC
);
2486 PRBool collected
= BeginCollection(aListener
) && FinishCollection();
2489 // We wait until after FinishCollection to check the white nodes because
2490 // some objects may outlive CollectWhite but then be freed by
2491 // FinishCycleCollection (like XPConnect's deferred release of native
2493 PRUint32 i
, count
= mWhiteNodes
->Length();
2494 for (i
= 0; i
< count
; ++i
) {
2495 PtrInfo
*pinfo
= mWhiteNodes
->ElementAt(i
);
2496 if (pinfo
->mLangID
== nsIProgrammingLanguage::CPLUSPLUS
&&
2497 mPurpleBuf
.Exists(pinfo
->mPointer
)) {
2498 printf("nsCycleCollector: %s object @%p is still alive after\n"
2499 " calling RootAndUnlinkJSObjects, Unlink, and Unroot on"
2500 " it! This probably\n"
2501 " means the Unlink implementation was insufficient.\n",
2502 pinfo
->mName
, pinfo
->mPointer
);
2506 mWhiteNodes
->Clear();
2509 mParams
.mDoNothing
= PR_FALSE
;
2517 mWhiteNodes
= nsnull
;
2519 mCollectionInProgress
= PR_FALSE
;
2522 // Now that the cycle collector has freed some memory, we can try to
2523 // force the C library to give back as much memory to the system as
2528 #ifdef COLLECT_TIME_DEBUG
2529 printf("cc: Collect() took %lldms\n",
2530 (PR_Now() - start
) / PR_USEC_PER_MSEC
);
2533 ExplainLiveExpectedGarbage();
2535 return mCollectedObjects
;
2539 nsCycleCollector::BeginCollection(nsICycleCollectorListener
*aListener
)
2541 if (mParams
.mDoNothing
)
2544 if (aListener
&& NS_FAILED(aListener
->Begin())) {
2548 GCGraphBuilder
builder(mGraph
, mRuntimes
, aListener
);
2549 if (!builder
.Initialized())
2552 #ifdef COLLECT_TIME_DEBUG
2553 PRTime now
= PR_Now();
2555 for (PRUint32 i
= 0; i
<= nsIProgrammingLanguage::MAX
; ++i
) {
2557 mRuntimes
[i
]->BeginCycleCollection(builder
, false);
2560 #ifdef COLLECT_TIME_DEBUG
2561 printf("cc: mRuntimes[*]->BeginCycleCollection() took %lldms\n",
2562 (PR_Now() - now
) / PR_USEC_PER_MSEC
);
2568 PRUint32 purpleStart
= builder
.Count();
2570 mScanInProgress
= PR_TRUE
;
2571 SelectPurple(builder
);
2573 PRUint32 purpleEnd
= builder
.Count();
2575 if (purpleStart
!= purpleEnd
) {
2577 if (mParams
.mHookMalloc
)
2580 if (mParams
.mLogPointers
&& !mPtrLog
)
2581 mPtrLog
= fopen("pointer_log", "w");
2584 NodePool::Enumerator
queue(mGraph
.mNodes
);
2585 while (i
++ < purpleStart
) {
2588 while (i
++ < purpleEnd
) {
2589 mStats
.mForgetNode
++;
2590 if (mParams
.mLogPointers
)
2591 fprintf(mPtrLog
, "F %p\n", queue
.GetNext()->mPointer
);
2596 #ifdef COLLECT_TIME_DEBUG
2597 printf("cc: SelectPurple() took %lldms\n",
2598 (PR_Now() - now
) / PR_USEC_PER_MSEC
);
2601 if (builder
.Count() > 0) {
2602 // The main Bacon & Rajan collection algorithm.
2604 #ifdef COLLECT_TIME_DEBUG
2610 #ifdef COLLECT_TIME_DEBUG
2612 PRTime then
= PR_Now();
2613 printf("cc: MarkRoots() took %lldms\n",
2614 (then
- now
) / PR_USEC_PER_MSEC
);
2621 #ifdef COLLECT_TIME_DEBUG
2622 printf("cc: ScanRoots() took %lldms\n",
2623 (PR_Now() - now
) / PR_USEC_PER_MSEC
);
2626 mScanInProgress
= PR_FALSE
;
2629 aListener
->BeginDescriptions();
2631 NodePool::Enumerator
etor(mGraph
.mNodes
);
2632 while (!etor
.IsDone()) {
2633 PtrInfo
*pi
= etor
.GetNext();
2634 if (pi
->mColor
== black
) {
2635 PRUint64 p
= (PRUint64
)pi
->mPointer
;
2636 if (pi
->mRefCount
> 0 && pi
->mRefCount
< PR_UINT32_MAX
) {
2637 aListener
->DescribeRefcountedObject(p
, pi
->mInternalRefs
,
2641 aListener
->DescribeGCedObject(p
, pi
->mRefCount
!= 0);
2650 if (mFollowupCollection
&& purpleStart
!= purpleEnd
) {
2652 NodePool::Enumerator
queue(mGraph
.mNodes
);
2653 while (i
++ < purpleStart
) {
2656 while (i
++ < purpleEnd
) {
2657 PtrInfo
*pi
= queue
.GetNext();
2658 if (pi
->mColor
== white
) {
2659 printf("nsCycleCollector: a later shutdown collection collected the additional\n"
2661 " (which could be fixed by improving traversal)\n",
2662 pi
->mPointer
, pi
->mName
);
2668 #ifdef COLLECT_TIME_DEBUG
2673 #ifdef COLLECT_TIME_DEBUG
2674 printf("cc: RootWhite() took %lldms\n",
2675 (PR_Now() - now
) / PR_USEC_PER_MSEC
);
2679 mScanInProgress
= PR_FALSE
;
2686 nsCycleCollector::FinishCollection()
2688 #ifdef COLLECT_TIME_DEBUG
2689 PRTime now
= PR_Now();
2691 PRBool collected
= CollectWhite();
2693 #ifdef COLLECT_TIME_DEBUG
2694 printf("cc: CollectWhite() took %lldms\n",
2695 (PR_Now() - now
) / PR_USEC_PER_MSEC
);
2699 mStats
.mCollection
++;
2700 if (mParams
.mReportStats
)
2704 for (PRUint32 i
= 0; i
<= nsIProgrammingLanguage::MAX
; ++i
) {
2706 mRuntimes
[i
]->FinishCycleCollection();
2709 mFollowupCollection
= PR_TRUE
;
2715 nsCycleCollector::SuspectedCount()
2717 return mPurpleBuf
.Count();
2721 nsCycleCollector::Shutdown()
2723 // Here we want to run a final collection and then permanently
2724 // disable the collector because the program is shutting down.
2726 Collect(SHUTDOWN_COLLECTIONS(mParams
), nsnull
);
2729 GCGraphBuilder
builder(mGraph
, mRuntimes
, nsnull
);
2730 mScanInProgress
= PR_TRUE
;
2731 SelectPurple(builder
);
2732 mScanInProgress
= PR_FALSE
;
2733 if (builder
.Count() != 0) {
2734 printf("Might have been able to release more cycles if the cycle collector would "
2735 "run once more at shutdown.\n");
2739 mParams
.mDoNothing
= PR_TRUE
;
2744 static PLDHashOperator
2745 AddExpectedGarbage(nsVoidPtrHashKey
*p
, void *arg
)
2747 GCGraphBuilder
*builder
= static_cast<GCGraphBuilder
*>(arg
);
2749 static_cast<nsISupports
*>(const_cast<void*>(p
->GetKey()));
2750 builder
->NoteXPCOMRoot(root
);
2751 return PL_DHASH_NEXT
;
2754 struct SetSCCVisitor
2756 SetSCCVisitor(PRUint32 aIndex
) : mIndex(aIndex
) {}
2757 PRBool
ShouldVisitNode(PtrInfo
const *pi
) { return pi
->mSCCIndex
== 0; }
2758 void VisitNode(PtrInfo
*pi
) { pi
->mSCCIndex
= mIndex
; }
2763 struct SetNonRootGreyVisitor
2765 PRBool
ShouldVisitNode(PtrInfo
const *pi
) { return pi
->mColor
== white
; }
2766 void VisitNode(PtrInfo
*pi
) { pi
->mColor
= grey
; }
2770 PrintPathToExpectedGarbage(PtrInfo
*pi
)
2772 printf(" An object expected to be garbage could be "
2773 "reached from it by the path:\n");
2774 for (PtrInfo
*path
= pi
, *prev
= nsnull
; prev
!= path
;
2776 path
= path
->mShortestPathToExpectedGarbage
) {
2778 nsCString
*edgeName
= prev
2779 ->mShortestPathToExpectedGarbageEdgeName
;
2781 edgeName
->IsEmpty() ? "<unknown edge>"
2784 printf(" %s %p\n", path
->mName
, path
->mPointer
);
2789 nsCycleCollector::ExplainLiveExpectedGarbage()
2791 if (mScanInProgress
|| mCollectionInProgress
)
2792 Fault("can't explain expected garbage during collection itself");
2794 if (mParams
.mDoNothing
) {
2795 printf("nsCycleCollector: not explaining expected garbage since\n"
2796 " cycle collection disabled\n");
2800 mCollectionInProgress
= PR_TRUE
;
2801 mScanInProgress
= PR_TRUE
;
2804 GCGraphBuilder
builder(mGraph
, mRuntimes
, nsnull
);
2806 // Instead of adding roots from the purple buffer, we add them
2807 // from the list of nodes we were expected to collect.
2808 // Put the expected garbage in *before* calling
2809 // BeginCycleCollection so that we can separate the expected
2810 // garbage from the NoteRoot calls in such a way that something
2811 // that's in both is considered expected garbage.
2812 mExpectedGarbage
.EnumerateEntries(&AddExpectedGarbage
, &builder
);
2814 PRUint32 expectedGarbageCount
= builder
.Count();
2816 for (PRUint32 i
= 0; i
<= nsIProgrammingLanguage::MAX
; ++i
) {
2818 mRuntimes
[i
]->BeginCycleCollection(builder
, true);
2821 // But just for extra information, add entries from the purple
2822 // buffer too, since it may give us extra information about
2823 // traversal deficiencies.
2824 mPurpleBuf
.NoteAll(builder
);
2829 mScanInProgress
= PR_FALSE
;
2831 PRBool describeExtraRefcounts
= PR_FALSE
;
2832 PRBool findCycleRoots
= PR_FALSE
;
2834 NodePool::Enumerator
queue(mGraph
.mNodes
);
2836 while (!queue
.IsDone()) {
2837 PtrInfo
*pi
= queue
.GetNext();
2838 if (pi
->mColor
== white
) {
2839 findCycleRoots
= PR_TRUE
;
2842 if (pi
->mInternalRefs
!= pi
->mRefCount
&&
2843 (i
< expectedGarbageCount
|| i
>= mGraph
.mRootCount
)) {
2844 // This check isn't particularly useful anymore
2845 // given that we need to enter this part for i >=
2846 // mGraph.mRootCount and there are plenty of
2848 describeExtraRefcounts
= PR_TRUE
;
2854 if ((describeExtraRefcounts
|| findCycleRoots
) &&
2855 CreateReversedEdges()) {
2856 // Note that the external references may have been external
2857 // to a different node in the cycle collection that just
2858 // happened, if that different node was purple and then
2861 // Use mSCCIndex temporarily to track whether we've reached
2862 // nodes in the breadth-first search.
2863 const PRUint32 INDEX_UNREACHED
= 0;
2864 const PRUint32 INDEX_REACHED
= 1;
2865 NodePool::Enumerator
etor_clear(mGraph
.mNodes
);
2866 while (!etor_clear
.IsDone()) {
2867 PtrInfo
*pi
= etor_clear
.GetNext();
2868 pi
->mSCCIndex
= INDEX_UNREACHED
;
2871 nsDeque queue
; // for breadth-first search
2872 NodePool::Enumerator
etor_roots(mGraph
.mNodes
);
2873 for (PRUint32 i
= 0; i
< mGraph
.mRootCount
; ++i
) {
2874 PtrInfo
*root_pi
= etor_roots
.GetNext();
2875 if (i
< expectedGarbageCount
) {
2876 root_pi
->mSCCIndex
= INDEX_REACHED
;
2877 root_pi
->mShortestPathToExpectedGarbage
= root_pi
;
2878 queue
.Push(root_pi
);
2882 while (queue
.GetSize() > 0) {
2883 PtrInfo
*pi
= (PtrInfo
*)queue
.PopFront();
2884 for (ReversedEdge
*e
= pi
->mReversedEdges
; e
; e
= e
->mNext
) {
2885 if (e
->mTarget
->mSCCIndex
== INDEX_UNREACHED
) {
2886 e
->mTarget
->mSCCIndex
= INDEX_REACHED
;
2887 PtrInfo
*target
= e
->mTarget
;
2888 if (!target
->mShortestPathToExpectedGarbage
) {
2889 target
->mShortestPathToExpectedGarbage
= pi
;
2890 target
->mShortestPathToExpectedGarbageEdgeName
=
2897 if (pi
->mRefCount
== PR_UINT32_MAX
||
2898 (pi
->mInternalRefs
!= pi
->mRefCount
&& pi
->mRefCount
> 0)) {
2899 if (pi
->mRefCount
== PR_UINT32_MAX
) {
2900 printf("nsCycleCollector: %s %p was not collected due "
2902 " external references\n",
2903 pi
->mName
, pi
->mPointer
);
2906 printf("nsCycleCollector: %s %p was not collected due "
2908 " external references (%d total - %d known)\n",
2909 pi
->mName
, pi
->mPointer
,
2910 pi
->mRefCount
- pi
->mInternalRefs
,
2911 pi
->mRefCount
, pi
->mInternalRefs
);
2914 PrintPathToExpectedGarbage(pi
);
2916 if (pi
->mRefCount
== PR_UINT32_MAX
) {
2917 printf(" The known references to it were from:\n");
2920 printf(" The %d known references to it were from:\n",
2923 for (ReversedEdge
*e
= pi
->mReversedEdges
;
2926 e
->mTarget
->mName
, e
->mTarget
->mPointer
);
2927 if (!e
->mEdgeName
->IsEmpty()) {
2928 printf(" via %s", e
->mEdgeName
->get());
2932 mRuntimes
[pi
->mLangID
]->PrintAllReferencesTo(pi
->mPointer
);
2936 if (findCycleRoots
) {
2937 // NOTE: This code changes the white nodes that are not
2940 // Put the nodes in post-order traversal order from a
2941 // depth-first search.
2942 nsDeque DFSPostOrder
;
2945 // Use mSCCIndex temporarily to track the DFS numbering:
2946 const PRUint32 INDEX_UNREACHED
= 0;
2947 const PRUint32 INDEX_TRAVERSING
= 1;
2948 const PRUint32 INDEX_NUMBERED
= 2;
2950 NodePool::Enumerator
etor_clear(mGraph
.mNodes
);
2951 while (!etor_clear
.IsDone()) {
2952 PtrInfo
*pi
= etor_clear
.GetNext();
2953 pi
->mSCCIndex
= INDEX_UNREACHED
;
2958 NodePool::Enumerator
etor_roots(mGraph
.mNodes
);
2959 for (PRUint32 i
= 0; i
< mGraph
.mRootCount
; ++i
) {
2960 PtrInfo
*root_pi
= etor_roots
.GetNext();
2961 stack
.Push(root_pi
);
2964 while (stack
.GetSize() > 0) {
2965 PtrInfo
*pi
= (PtrInfo
*)stack
.Peek();
2966 if (pi
->mSCCIndex
== INDEX_UNREACHED
) {
2967 pi
->mSCCIndex
= INDEX_TRAVERSING
;
2968 for (EdgePool::Iterator child
= pi
->mFirstChild
,
2969 child_end
= pi
->mLastChild
;
2970 child
!= child_end
; ++child
) {
2975 // Somebody else might have numbered it already
2976 // (since this is depth-first, not breadth-first).
2977 // This happens if a node is pushed on the stack
2978 // a second time while it is on the stack in
2980 if (pi
->mSCCIndex
== INDEX_TRAVERSING
) {
2981 pi
->mSCCIndex
= INDEX_NUMBERED
;
2982 DFSPostOrder
.Push(pi
);
2988 // Put the nodes into strongly-connected components.
2990 NodePool::Enumerator
etor_clear(mGraph
.mNodes
);
2991 while (!etor_clear
.IsDone()) {
2992 PtrInfo
*pi
= etor_clear
.GetNext();
2996 PRUint32 currentSCC
= 1;
2998 while (DFSPostOrder
.GetSize() > 0) {
2999 GraphWalker
<SetSCCVisitor
>(SetSCCVisitor(currentSCC
)).Walk((PtrInfo
*)DFSPostOrder
.PopFront());
3004 // Mark any white nodes reachable from other components as
3007 NodePool::Enumerator
queue(mGraph
.mNodes
);
3008 while (!queue
.IsDone()) {
3009 PtrInfo
*pi
= queue
.GetNext();
3010 if (pi
->mColor
!= white
)
3012 for (EdgePool::Iterator child
= pi
->mFirstChild
,
3013 child_end
= pi
->mLastChild
;
3014 child
!= child_end
; ++child
) {
3015 if ((*child
)->mSCCIndex
!= pi
->mSCCIndex
) {
3016 GraphWalker
<SetNonRootGreyVisitor
>(SetNonRootGreyVisitor()).Walk(*child
);
3023 NodePool::Enumerator
queue(mGraph
.mNodes
);
3024 while (!queue
.IsDone()) {
3025 PtrInfo
*pi
= queue
.GetNext();
3026 if (pi
->mColor
== white
) {
3028 nsIProgrammingLanguage::CPLUSPLUS
&&
3029 mPurpleBuf
.Exists(pi
->mPointer
)) {
3031 "nsCycleCollector: %s %p in component %d\n"
3032 " which was reference counted during the root/unlink/unroot phase of the\n"
3033 " last collection was not collected due to failure to unlink (see other\n"
3034 " warnings) or deficiency in traverse that causes cycles referenced only\n"
3035 " from other cycles to require multiple rounds of cycle collection in which\n"
3036 " this object was likely the reachable object\n",
3037 pi
->mName
, pi
->mPointer
, pi
->mSCCIndex
);
3040 "nsCycleCollector: %s %p in component %d\n"
3041 " was not collected due to missing call to suspect, failure to unlink (see\n"
3042 " other warnings), or deficiency in traverse that causes cycles referenced\n"
3043 " only from other cycles to require multiple rounds of cycle collection\n",
3044 pi
->mName
, pi
->mPointer
, pi
->mSCCIndex
);
3046 if (pi
->mShortestPathToExpectedGarbage
)
3047 PrintPathToExpectedGarbage(pi
);
3053 DestroyReversedEdges();
3059 mCollectionInProgress
= PR_FALSE
;
3061 for (PRUint32 i
= 0; i
<= nsIProgrammingLanguage::MAX
; ++i
) {
3063 mRuntimes
[i
]->FinishCycleCollection();
3068 nsCycleCollector::CreateReversedEdges()
3070 // Count the edges in the graph.
3071 PRUint32 edgeCount
= 0;
3072 NodePool::Enumerator
countQueue(mGraph
.mNodes
);
3073 while (!countQueue
.IsDone()) {
3074 PtrInfo
*pi
= countQueue
.GetNext();
3075 for (EdgePool::Iterator e
= pi
->mFirstChild
, e_end
= pi
->mLastChild
;
3076 e
!= e_end
; ++e
, ++edgeCount
) {
3080 // Allocate a pool to hold all of the edges.
3081 mGraph
.mReversedEdges
= new ReversedEdge
[edgeCount
];
3082 if (mGraph
.mReversedEdges
== nsnull
) {
3083 NS_NOTREACHED("allocation failure creating reversed edges");
3087 // Fill in the reversed edges by scanning all forward edges.
3088 ReversedEdge
*current
= mGraph
.mReversedEdges
;
3089 NodePool::Enumerator
buildQueue(mGraph
.mNodes
);
3090 while (!buildQueue
.IsDone()) {
3091 PtrInfo
*pi
= buildQueue
.GetNext();
3093 for (EdgePool::Iterator e
= pi
->mFirstChild
, e_end
= pi
->mLastChild
;
3095 current
->mTarget
= pi
;
3096 current
->mEdgeName
= &pi
->mEdgeNames
[i
];
3097 current
->mNext
= (*e
)->mReversedEdges
;
3098 (*e
)->mReversedEdges
= current
;
3103 NS_ASSERTION(current
- mGraph
.mReversedEdges
== ptrdiff_t(edgeCount
),
3109 nsCycleCollector::DestroyReversedEdges()
3111 NodePool::Enumerator
queue(mGraph
.mNodes
);
3112 while (!queue
.IsDone()) {
3113 PtrInfo
*pi
= queue
.GetNext();
3114 pi
->mReversedEdges
= nsnull
;
3117 delete mGraph
.mReversedEdges
;
3118 mGraph
.mReversedEdges
= nsnull
;
3122 nsCycleCollector::ShouldBeFreed(nsISupports
*n
)
3125 mExpectedGarbage
.PutEntry(n
);
3130 nsCycleCollector::WasFreed(nsISupports
*n
)
3133 mExpectedGarbage
.RemoveEntry(n
);
3138 ////////////////////////////////////////////////////////////////////////
3139 // Module public API (exported in nsCycleCollector.h)
3140 // Just functions that redirect into the singleton, once it's built.
3141 ////////////////////////////////////////////////////////////////////////
3144 nsCycleCollector_registerRuntime(PRUint32 langID
,
3145 nsCycleCollectionLanguageRuntime
*rt
)
3148 sCollector
->RegisterRuntime(langID
, rt
);
3151 nsCycleCollectionLanguageRuntime
*
3152 nsCycleCollector_getRuntime(PRUint32 langID
)
3155 sCollector
->GetRuntime(langID
);
3160 nsCycleCollector_forgetRuntime(PRUint32 langID
)
3163 sCollector
->ForgetRuntime(langID
);
3168 NS_CycleCollectorSuspect(nsISupports
*n
)
3171 return sCollector
->Suspect(n
);
3176 NS_CycleCollectorForget(nsISupports
*n
)
3178 return sCollector
? sCollector
->Forget(n
) : PR_TRUE
;
3181 nsPurpleBufferEntry
*
3182 NS_CycleCollectorSuspect2(nsISupports
*n
)
3185 return sCollector
->Suspect2(n
);
3190 NS_CycleCollectorForget2(nsPurpleBufferEntry
*e
)
3192 return sCollector
? sCollector
->Forget2(e
) : PR_TRUE
;
3197 nsCycleCollector_collect(nsICycleCollectorListener
*aListener
)
3199 return sCollector
? sCollector
->Collect(1, aListener
) : 0;
3203 nsCycleCollector_suspectedCount()
3205 return sCollector
? sCollector
->SuspectedCount() : 0;
3209 nsCycleCollector_startup()
3211 NS_ASSERTION(!sCollector
, "Forgot to call nsCycleCollector_shutdown?");
3213 sCollector
= new nsCycleCollector();
3214 return sCollector
? NS_OK
: NS_ERROR_OUT_OF_MEMORY
;
3218 nsCycleCollector_shutdown()
3221 sCollector
->Shutdown();
3223 sCollector
= nsnull
;
3229 nsCycleCollector_DEBUG_shouldBeFreed(nsISupports
*n
)
3233 sCollector
->ShouldBeFreed(n
);
3238 nsCycleCollector_DEBUG_wasFreed(nsISupports
*n
)
3242 sCollector
->WasFreed(n
);