Closed Bug 937751 Opened 6 years ago Closed 6 years ago

ICC: Incrementalize Collect and MarkRoots

Categories

(Core :: XPCOM, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla28

People

(Reporter: mccr8, Assigned: mccr8)

References

Details

(Whiteboard: [qa-])

Attachments

(7 files)

These patches allow Collect (the top level cycle collector method) and MarkRoots to be run, stopped, then run some more, based on a time budget that is passed in.

Note that these patches do not make it safe to actually run the rest of the browser in between these chunks of work, and they also do not actually schedule the work to be run incrementally.  That will happen in other patches.
Cycle collection protects against reentrancy by setting a flag to indicate a collection
is in progress. With synchronous CC, it is okay to set this in BeginCollection, and
clear it in CleanupAfterCollection. With ICC, this must be set and cleared in every
slice, so I moved the fixing of it to Collect.  I also changed the name of the variable,
because we can be in the middle of an ICC without the CC being actively running,
and it is only the latter we are worried about here.
Attachment #8336413 - Flags: review?(bugs)
This patch makes it so that Collect takes a time budget that describes
how much longer the collection can be run for. Then we run the current phase.
Once this is done, we check whether we have exceeded our time budget or
if we have finished a collection. If neither of those have happened, we
run the cycle collector some more.

If we're a manually triggered CC, and we were in the middle of an ICC when
the CC started, then once the current CC is complete, we start a new CC
immediately. This is needed to ensure that a manually specified listener
is used, and to ensure that any garbage objects the caller expects to be
collected are in fact collected.

Note that in this patch we are always passing in an unlimited budget to
Collect, so cycle collections will always be run to completion.
Attachment #8336415 - Flags: review?(bugs)
For debugging purposes, it can be useful to see what ICC is currently
being run.
Attachment #8336416 - Flags: review?(bugs)
To make nsCycleCollector::MarkRoots incremental, we have to store all of its state on
the heap, so we can resume it.  The only remaining state to convert is the NodePool
enumerator.
Attachment #8336417 - Flags: review?(bugs)
Now that all of MarkRoots's state is stored on the heap, it can be run
incrementally. Like with Collect, it takes a budget to determine how
long it can run. Any residual budget will be available to the caller.

One difference is that Collect calls checkOverBudget() which always checks
the time, but MarkRoots uses isOverBudget() to determine if there is
any time remaining. This only checks the current time every
kNumNodesBetweenTimeChecks nodes, to reduce the overhead of checking.
Attachment #8336418 - Flags: review?(bugs)
Attachment #8336412 - Flags: review?(wmccloskey) → review+
Comment on attachment 8336411 [details] [diff] [review]
part 1 - Add and set incremental cycle collection phases. r=smaug

># HG changeset patch
># User Andrew McCreight <continuation@gmail.com>
>
>Bug 937751, part 1 - Add and set incremental cycle collection phases. r=smaug
>
>diff --git a/xpcom/base/nsCycleCollector.cpp b/xpcom/base/nsCycleCollector.cpp
>index 7b09c29..bde071c 100644
>--- a/xpcom/base/nsCycleCollector.cpp
>+++ b/xpcom/base/nsCycleCollector.cpp
>@@ -965,16 +965,23 @@ nsPurpleBuffer::SelectPointers(GCGraphBuilder &aBuilder)
> 
>     NS_ASSERTION(mCount == 0, "AddPurpleRoot failed");
>     if (mCount == 0) {
>         FreeBlocks();
>         InitBlocks();
>     }
> }
> 
>+enum ccPhase {
>+    IdlePhase,
>+    GraphBuildingPhase,
>+    ScanAndCollectWhitePhase,
>+    CleanupPhase
>+};
>+
> enum ccType {
>     ScheduledCC, /* Automatically triggered, based on time or the purple buffer. */
>     ManualCC,    /* Explicitly triggered. */
>     ShutdownCC   /* Shutdown CC, used for finding leaks. */
> };
> 
> #ifdef MOZ_NUWA_PROCESS
> #include "ipc/Nuwa.h"
>@@ -989,16 +996,17 @@ class nsCycleCollector
>     bool mCollectionInProgress;
>     // mScanInProgress should be false when we're collecting white objects.
>     bool mScanInProgress;
>     CycleCollectorResults mResults;
>     TimeStamp mCollectionStart;
> 
>     CycleCollectedJSRuntime *mJSRuntime;
> 
>+    ccPhase mIncrementalPhase;
>     GCGraph mGraph;
>     nsAutoPtr<GCGraphBuilder> mBuilder;
>     nsCOMPtr<nsICycleCollectorListener> mListener;
> 
>     nsIThread* mThread;
> 
>     nsCycleCollectorParams mParams;
> 
>@@ -2183,16 +2191,17 @@ nsCycleCollector::ForgetSkippable(bool aRemoveChildlessNodes,
> 
> MOZ_NEVER_INLINE void
> nsCycleCollector::MarkRoots()
> {
>     TimeLog timeLog;
>     AutoRestore<bool> ar(mScanInProgress);
>     MOZ_ASSERT(!mScanInProgress);
>     mScanInProgress = true;
>+    MOZ_ASSERT(mIncrementalPhase == GraphBuildingPhase);
> 
>     // read the PtrInfo out of the graph that we are building
>     NodePool::Enumerator queue(mGraph.mNodes);
>     while (!queue.IsDone()) {
>         PtrInfo *pi = queue.GetNext();
>         CC_AbortIfNull(pi);
>         mBuilder->Traverse(pi);
>         if (queue.AtBlockEnd()) {
>@@ -2204,16 +2213,17 @@ nsCycleCollector::MarkRoots()
>     }
> 
>     if (mBuilder->RanOutOfMemory()) {
>         MOZ_ASSERT(false, "Ran out of memory while building cycle collector graph");
>         CC_TELEMETRY(_OOM, true);
>     }
> 
>     mBuilder = nullptr;
>+    mIncrementalPhase = ScanAndCollectWhitePhase;
>     timeLog.Checkpoint("MarkRoots()");
> }
> 
> 
> ////////////////////////////////////////////////////////////////////////
> // Bacon & Rajan's |ScanRoots| routine.
> ////////////////////////////////////////////////////////////////////////
> 
>@@ -2332,16 +2342,17 @@ nsCycleCollector::ScanWeakMaps()
> void
> nsCycleCollector::ScanRoots()
> {
>     TimeLog timeLog;
>     AutoRestore<bool> ar(mScanInProgress);
>     MOZ_ASSERT(!mScanInProgress);
>     mScanInProgress = true;
>     mWhiteNodeCount = 0;
>+    MOZ_ASSERT(mIncrementalPhase == ScanAndCollectWhitePhase);
> 
>     // On the assumption that most nodes will be black, it's
>     // probably faster to use a GraphWalker than a
>     // NodePool::Enumerator.
>     bool failed = false;
>     GraphWalker<scanVisitor>(scanVisitor(mWhiteNodeCount, failed)).WalkFromRoots(mGraph);
> 
>     if (failed) {
>@@ -2373,16 +2384,17 @@ nsCycleCollector::ScanRoots()
>                 // scanning if it is only reachable from an object that gets freed.
>                 break;
>             }
>         }
> 
>         mListener->End();
>         mListener = nullptr;
>     }
>+
>     timeLog.Checkpoint("ScanRoots()");
> }
> 
> 
> ////////////////////////////////////////////////////////////////////////
> // Bacon & Rajan's |CollectWhite| routine, somewhat modified.
> ////////////////////////////////////////////////////////////////////////
> 
>@@ -2401,16 +2413,18 @@ nsCycleCollector::CollectWhite()
>     //
>     //   - Root(whites), which should pin the whites in memory.
>     //   - Unlink(whites), which drops outgoing links on each white.
>     //   - Unroot(whites), which returns the whites to normal GC.
> 
>     TimeLog timeLog;
>     nsAutoTArray<PtrInfo*, 4000> whiteNodes;
> 
>+    MOZ_ASSERT(mIncrementalPhase == ScanAndCollectWhitePhase);
>+
>     whiteNodes.SetCapacity(mWhiteNodeCount);
>     uint32_t numWhiteGCed = 0;
> 
>     NodePool::Enumerator etor(mGraph.mNodes);
>     while (!etor.IsDone())
>     {
>         PtrInfo *pinfo = etor.GetNext();
>         if (pinfo->mColor == white) {
>@@ -2449,16 +2463,17 @@ nsCycleCollector::CollectWhite()
> 
>     for (uint32_t i = 0; i < count; ++i) {
>         PtrInfo *pinfo = whiteNodes.ElementAt(i);
>         pinfo->mParticipant->Unroot(pinfo->mPointer);
>     }
>     timeLog.Checkpoint("CollectWhite::Unroot");
> 
>     nsCycleCollector_dispatchDeferredDeletion(false);
>+    mIncrementalPhase = CleanupPhase;
> 
>     return count > 0;
> }
> 
> 
> ////////////////////////
> // Memory reporter
> ////////////////////////
>@@ -2530,16 +2545,17 @@ class CycleCollectorReporter MOZ_FINAL : public MemoryMultiReporter
> ////////////////////////////////////////////////////////////////////////
> // Collector implementation
> ////////////////////////////////////////////////////////////////////////
> 
> nsCycleCollector::nsCycleCollector() :
>     mCollectionInProgress(false),
>     mScanInProgress(false),
>     mJSRuntime(nullptr),
>+    mIncrementalPhase(IdlePhase),
>     mThread(NS_GetCurrentThread()),
>     mWhiteNodeCount(0),
>     mBeforeUnlinkCB(nullptr),
>     mForgetSkippableCB(nullptr),
>     mReporter(nullptr),
>     mUnmergedNeeded(0),
>     mMergedInARow(0)
> {
>@@ -2652,16 +2668,17 @@ nsCycleCollector::FixGrayBits(bool aForceGC)
>     TimeLog timeLog;
>     mJSRuntime->Collect(aForceGC ? JS::gcreason::SHUTDOWN_CC : JS::gcreason::CC_FORCED);
>     timeLog.Checkpoint("GC()");
> }
> 
> void
> nsCycleCollector::CleanupAfterCollection()
> {
>+    MOZ_ASSERT(mIncrementalPhase == CleanupPhase);
>     mGraph.Clear();
>     mCollectionInProgress = false;
> 
> #ifdef XP_OS2
>     // Now that the cycle collector has freed some memory, we can try to
>     // force the C library to give back as much memory to the system as
>     // possible.
>     _heapmin();
>@@ -2678,16 +2695,17 @@ nsCycleCollector::CleanupAfterCollection()
>     CC_TELEMETRY( , interval);
>     CC_TELEMETRY(_VISITED_REF_COUNTED, mResults.mVisitedRefCounted);
>     CC_TELEMETRY(_VISITED_GCED, mResults.mVisitedGCed);
>     CC_TELEMETRY(_COLLECTED, mWhiteNodeCount);
> 
>     if (mJSRuntime) {
>         mJSRuntime->EndCycleCollectionCallback(mResults);
>     }
>+    mIncrementalPhase = IdlePhase;
> }
> 
> void
> nsCycleCollector::ShutdownCollect()
> {
>     for (uint32_t i = 0; i < DEFAULT_SHUTDOWN_COLLECTIONS; ++i) {
>         NS_ASSERTION(i < NORMAL_SHUTDOWN_COLLECTIONS, "Extra shutdown CC");
>         if (!Collect(ShutdownCC, nullptr)) {
>@@ -2702,21 +2720,26 @@ nsCycleCollector::Collect(ccType aCCType,
> {
>     CheckThreadSafety();
> 
>     // This can legitimately happen in a few cases. See bug 383651.
>     if (mCollectionInProgress) {
>         return false;
>     }
> 
>+    MOZ_ASSERT(mIncrementalPhase == IdlePhase);
>+
>     BeginCollection(aCCType, aManualListener);
>     MarkRoots();
>     ScanRoots();
>     bool collectedAny = CollectWhite();
>     CleanupAfterCollection();
>+
>+    MOZ_ASSERT(mIncrementalPhase == IdlePhase);
>+
>     return collectedAny;
> }
> 
> // Don't merge too many times in a row, and do at least a minimum
> // number of unmerged CCs in a row.
> static const uint32_t kMinConsecutiveUnmerged = 3;
> static const uint32_t kMaxConsecutiveMerged = 3;
> 
>@@ -2750,16 +2773,17 @@ nsCycleCollector::ShouldMergeZones(ccType aCCType)
>     }
> }
> 
> void
> nsCycleCollector::BeginCollection(ccType aCCType,
>                                   nsICycleCollectorListener *aManualListener)
> {
>     TimeLog timeLog;
>+    MOZ_ASSERT(mIncrementalPhase == IdlePhase);
> 
>     mCollectionStart = TimeStamp::Now();
> 
>     mCollectionInProgress = true;
> 
>     if (mJSRuntime) {
>         mJSRuntime->BeginCycleCollectionCallback();
>         timeLog.Checkpoint("BeginCycleCollectionCallback()");
>@@ -2813,16 +2837,18 @@ nsCycleCollector::BeginCollection(ccType aCCType,
>     AutoRestore<bool> ar(mScanInProgress);
>     MOZ_ASSERT(!mScanInProgress);
>     mScanInProgress = true;
>     mPurpleBuf.SelectPointers(*mBuilder);
>     timeLog.Checkpoint("SelectPointers()");
> 
>     // We've finished adding roots, and everything in the graph is a root.
>     mGraph.mRootCount = mGraph.MapCount();
>+
>+    mIncrementalPhase = GraphBuildingPhase;
> }
> 
> uint32_t
> nsCycleCollector::SuspectedCount()
> {
>     CheckThreadSafety();
>     return mPurpleBuf.Count();
> }
Attachment #8336411 - Flags: review?(bugs) → review+
Attachment #8336413 - Flags: review?(bugs) → review+
Comment on attachment 8336415 [details] [diff] [review]
part 4 - Incrementalize nsCycleCollector::Collect. r=smaug

>+    if (mIncrementalPhase != IdlePhase) {
perhaps !startedIdle

>+        FreeSnowWhite(true);
>+    }
but this could use a comment why we want to kill snow white only in !startedIdle
Attachment #8336415 - Flags: review?(bugs) → review+
Attachment #8336416 - Flags: review?(bugs) → review+
Attachment #8336417 - Flags: review?(bugs) → review+
Comment on attachment 8336418 [details] [diff] [review]
part 7 - Incrementalize nsCycleCollector::MarkRoots. r=smaug

>-nsCycleCollector::MarkRoots()
>+nsCycleCollector::MarkRoots(SliceBudget &aBudget)
> {
>+    const intptr_t kNumNodesBetweenTimeChecks = 100;
100 only? Did you test higher numbers? I'd expect something like 1000 to be still ok.
But I guess we can tweak this later.
Attachment #8336418 - Flags: review?(bugs) → review+
(In reply to Olli Pettay [:smaug] from comment #10)
> perhaps !startedIdle
done

> but this could use a comment why we want to kill snow white only in
> !startedIdle
done

> 100 only? Did you test higher numbers? I'd expect something like 1000 to be
> still ok.
I bumped it up to 1000.  Having it lower doesn't buy us anything right now, except slightly more overhead. Performance re-tuning can come later.
I'll add some comments to the beginning of the file in a later bug, where we start to actually do weird stuff to guard against mutator activity during CC.
This busted clang versions that complain about |struct S;| followed by a definition with different visibility.  Patch built locally, pushed:

https://hg.mozilla.org/integration/mozilla-inbound/rev/5036242b2d53
Whiteboard: [qa-]
You need to log in before you can comment on or make changes to this bug.