Quelle  nsCycleCollector.cpp   Sprache: C

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

//
// This file implements a garbage-cycle collector based on the paper
//
//   Concurrent Cycle Collection in Reference Counted Systems
//   Bacon & Rajan (2001), ECOOP 2001 / Springer LNCS vol 2072
//
// We are not using the concurrent or acyclic cases of that paper; so
// the green, red and orange colors are not used.
//
// The collector is based on tracking pointers of four colors:
//
// Black nodes are definitely live. If we ever determine a node is
// black, it's ok to forget about, drop from our records.
//
// White nodes are definitely garbage cycles. Once we finish with our
// scanning, we unlink all the white nodes and expect that by
// unlinking them they will self-destruct (since a garbage cycle is
// only keeping itself alive with internal links, by definition).
//
// Snow-white is an addition to the original algorithm. A snow-white node
// has reference count zero and is just waiting for deletion.
//
// Grey nodes are being scanned. Nodes that turn grey will turn
// either black if we determine that they're live, or white if we
// determine that they're a garbage cycle. After the main collection
// algorithm there should be no grey nodes.
//
// Purple nodes are *candidates* for being scanned. They are nodes we
// haven't begun scanning yet because they're not old enough, or we're
// still partway through the algorithm.
//
// XPCOM objects participating in garbage-cycle collection are obliged
// to inform us when they ought to turn purple; that is, when their
// refcount transitions from N+1 -> N, for nonzero N. Furthermore we
// require that *after* an XPCOM object has informed us of turning
// purple, they will tell us when they either transition back to being
// black (incremented refcount) or are ultimately deleted.

// Incremental cycle collection
//
// Beyond the simple state machine required to implement incremental
// collection, the CC needs to be able to compensate for things the browser
// is doing during the collection. There are two kinds of problems. For each
// of these, there are two cases to deal with: purple-buffered C++ objects
// and JS objects.

// The first problem is that an object in the CC's graph can become garbage.
// This is bad because the CC touches the objects in its graph at every
// stage of its operation.
//
// All cycle collected C++ objects that die during a cycle collection
// will end up actually getting deleted by the SnowWhiteKiller. Before
// the SWK deletes an object, it checks if an ICC is running, and if so,
// if the object is in the graph. If it is, the CC clears mPointer and
// mParticipant so it does not point to the raw object any more. Because
// objects could die any time the CC returns to the mutator, any time the CC
// accesses a PtrInfo it must perform a null check on mParticipant to
// ensure the object has not gone away.
//
// JS objects don't always run finalizers, so the CC can't remove them from
// the graph when they die. Fortunately, JS objects can only die during a GC,
// so if a GC is begun during an ICC, the browser synchronously finishes off
// the ICC, which clears the entire CC graph. If the GC and CC are scheduled
// properly, this should be rare.
//
// The second problem is that objects in the graph can be changed, say by
// being addrefed or released, or by having a field updated, after the object
// has been added to the graph. The problem is that ICC can miss a newly
// created reference to an object, and end up unlinking an object that is
// actually alive.
//
// The basic idea of the solution, from "An on-the-fly Reference Counting
// Garbage Collector for Java" by Levanoni and Petrank, is to notice if an
// object has had an additional reference to it created during the collection,
// and if so, don't collect it during the current collection. This avoids having
// to rerun the scan as in Bacon & Rajan 2001.
//
// For cycle collected C++ objects, we modify AddRef to place the object in
// the purple buffer, in addition to Release. Then, in the CC, we treat any
// objects in the purple buffer as being alive, after graph building has
// completed. Because they are in the purple buffer, they will be suspected
// in the next CC, so there's no danger of leaks. This is imprecise, because
// we will treat as live an object that has been Released but not AddRefed
// during graph building, but that's probably rare enough that the additional
// bookkeeping overhead is not worthwhile.
//
// For JS objects, the cycle collector is only looking at gray objects. If a
// gray object is touched during ICC, it will be made black by UnmarkGray.
// Thus, if a JS object has become black during the ICC, we treat it as live.
// Merged JS zones have to be handled specially: we scan all zone globals.
// If any are black, we treat the zone as being black.

// Safety
//
// An XPCOM object is either scan-safe or scan-unsafe, purple-safe or
// purple-unsafe.
//
// An nsISupports object is scan-safe if:
//
//  - It can be QI'ed to |nsXPCOMCycleCollectionParticipant|, though
//    this operation loses ISupports identity (like nsIClassInfo).
//  - Additionally, the operation |traverse| on the resulting
//    nsXPCOMCycleCollectionParticipant does not cause *any* refcount
//    adjustment to occur (no AddRef / Release calls).
//
// A non-nsISupports ("native") object is scan-safe by explicitly
// providing its nsCycleCollectionParticipant.
//
// An object is purple-safe if it satisfies the following properties:
//
//  - The object is scan-safe.
//
// When we receive a pointer |ptr| via
// |nsCycleCollector::suspect(ptr)|, we assume it is purple-safe. We
// can check the scan-safety, but have no way to ensure the
// purple-safety; objects must obey, or else the entire system falls
// apart. Don't involve an object in this scheme if you can't
// guarantee its purple-safety. The easiest way to ensure that an
// object is purple-safe is to use nsCycleCollectingAutoRefCnt.
//
// When we have a scannable set of purple nodes ready, we begin
// our walks. During the walks, the nodes we |traverse| should only
// feed us more scan-safe nodes, and should not adjust the refcounts
// of those nodes.
//
// We do not |AddRef| or |Release| any objects during scanning. We
// rely on the purple-safety of the roots that call |suspect| to
// hold, such that we will clear the pointer from the purple buffer
// entry to the object before it is destroyed. The pointers that are
// merely scan-safe we hold only for the duration of scanning, and
// there should be no objects released from the scan-safe set during
// the scan.
//
// We *do* call |Root| and |Unroot| on every white object, on
// either side of the calls to |Unlink|. This keeps the set of white
// objects alive during the unlinking.
//

#if !defined(__MINGW32__)
#  ifdef WIN32
#    include <crtdbg.h>
#    include <errno.h>
#  endif
#endif

#include "base/process_util.h"

#include "mozilla/ArrayUtils.h"
#include "mozilla/AutoRestore.h"
#include "mozilla/CycleCollectedJSContext.h"
#include "mozilla/CycleCollectedJSRuntime.h"
#include "mozilla/CycleCollectorStats.h"
#include "mozilla/DebugOnly.h"
#include "mozilla/HashFunctions.h"
#include "mozilla/HashTable.h"
#include "mozilla/HoldDropJSObjects.h"
#include "mozilla/Maybe.h"
/* This must occur *after* base/process_util.h to avoid typedefs conflicts. */
#include <stdint.h>
#include <stdio.h>

#include <utility>

#include "js/SliceBudget.h"
#include "mozilla/Attributes.h"
#include "mozilla/Likely.h"
#include "mozilla/LinkedList.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/MruCache.h"
#include "mozilla/PoisonIOInterposer.h"
#include "mozilla/ProfilerLabels.h"
#include "mozilla/ProfilerMarkers.h"
#include "mozilla/SegmentedVector.h"
#include "mozilla/glean/XpcomMetrics.h"
#include "mozilla/ThreadLocal.h"
#include "mozilla/UniquePtr.h"
#include "mozilla/Unused.h"
#include "nsContentUtils.h"
#include "nsCycleCollectionNoteRootCallback.h"
#include "nsCycleCollectionParticipant.h"
#include "nsCycleCollector.h"
#include "nsDeque.h"
#include "nsDumpUtils.h"
#include "nsExceptionHandler.h"
#include "nsIConsoleService.h"
#include "nsICycleCollectorListener.h"
#include "nsIFile.h"
#include "nsIMemoryReporter.h"
#include "nsISerialEventTarget.h"
#include "nsPrintfCString.h"
#include "nsTArray.h"
#include "nsThreadUtils.h"
#include "nsXULAppAPI.h"
#include "prenv.h"
#include "xpcpublic.h"

using namespace mozilla;

using JS::SliceBudget;

struct NurseryPurpleBufferEntry {
  void* mPtr;
  nsCycleCollectionParticipant* mParticipant;
  nsCycleCollectingAutoRefCnt* mRefCnt;
};

#define NURSERY_PURPLE_BUFFER_SIZE 2048
bool gNurseryPurpleBufferEnabled = true;
NurseryPurpleBufferEntry gNurseryPurpleBufferEntry[NURSERY_PURPLE_BUFFER_SIZE];
uint32_t gNurseryPurpleBufferEntryCount = 0;

void ClearNurseryPurpleBuffer();

static void SuspectUsingNurseryPurpleBuffer(
    void* aPtr, nsCycleCollectionParticipant* aCp,
    nsCycleCollectingAutoRefCnt* aRefCnt) {
  MOZ_ASSERT(NS_IsMainThread(), "Wrong thread!");
  MOZ_ASSERT(gNurseryPurpleBufferEnabled);
  if (gNurseryPurpleBufferEntryCount == NURSERY_PURPLE_BUFFER_SIZE) {
    ClearNurseryPurpleBuffer();
  }

  gNurseryPurpleBufferEntry[gNurseryPurpleBufferEntryCount] = {aPtr, aCp,
                                                               aRefCnt};
  ++gNurseryPurpleBufferEntryCount;
}

// #define COLLECT_TIME_DEBUG

// Enable assertions that are useful for diagnosing errors in graph
// construction.
// #define DEBUG_CC_GRAPH

#define DEFAULT_SHUTDOWN_COLLECTIONS 5

// One to do the freeing, then another to detect there is no more work to do.
#define NORMAL_SHUTDOWN_COLLECTIONS 2

// Cycle collector environment variables
//
// MOZ_CC_ALL_TRACES: If set to "all", any cycle collector logging done will be
// WantAllTraces, which disables various cycle collector optimizations to give a
// fuller picture of the heap. If set to "shutdown", only shutdown logging will
// be WantAllTraces. The default is none.
//
// MOZ_CC_RUN_DURING_SHUTDOWN: In non-NS_FREE_PERMANENT_DATA builds, if this is
// set, run cycle collections at shutdown.
//
// MOZ_CC_LOG_ALL: If defined, always log cycle collector heaps.
//
// MOZ_CC_LOG_SHUTDOWN: If defined, log cycle collector heaps at shutdown.
//
// MOZ_CC_LOG_SHUTDOWN_SKIP: If set to a non-negative integer value n, then skip
// logging for the first n shutdown CCs. This implies MOZ_CC_LOG_SHUTDOWN. The
// first log or two are much larger than the rest, so it can be useful to reduce
// the total size of logs if you know already that the initial logs aren't
// interesting.
//
// MOZ_CC_LOG_WINDOW_ONLY: If this is set, only log CCs where at least one DOM
// window is still alive, as determined by GetCurrentInnerOrOuterWindowCount().
// The purpose of this is to avoid useless logs when investigating intermittent
// window leaks. Note that this count is only updated in DEBUG builds, and will
// only be read on the main thread.
//
// MOZ_CC_LOG_THREAD: If set to "main", only automatically log main thread
// CCs. If set to "worker", only automatically log worker CCs. If set to "all",
// log either. The default value is "all". This must be used with either
// MOZ_CC_LOG_ALL or MOZ_CC_LOG_SHUTDOWN for it to do anything.
//
// MOZ_CC_LOG_PROCESS: If set to "main", only automatically log main process
// CCs. If set to "content", only automatically log tab CCs. If set to "all",
// log everything. The default value is "all". This must be used with either
// MOZ_CC_LOG_ALL or MOZ_CC_LOG_SHUTDOWN for it to do anything.
//
// MOZ_CC_LOG_DIRECTORY: The directory in which logs are placed (such as
// logs from MOZ_CC_LOG_ALL and MOZ_CC_LOG_SHUTDOWN, or other uses
// of nsICycleCollectorListener)
//
// MOZ_CC_DISABLE_GC_LOG: If defined, don't make a GC log whenever we make a
// cycle collector log. This can be useful for leaks that go away when shutdown
// gets slower, when the JS heap is not involved in the leak. The default is to
// make the GC log.

// Various parameters of this collector can be tuned using environment
// variables.

struct nsCycleCollectorParams {
  bool mLogAll;
  bool mLogShutdown;
  bool mAllTracesAll;
  bool mAllTracesShutdown;
  bool mLogThisThread;
  bool mLogGC;
  bool mLogWindowOnly;
  int32_t mLogShutdownSkip = 0;

  nsCycleCollectorParams()
      : mLogAll(PR_GetEnv("MOZ_CC_LOG_ALL") != nullptr),
        mLogShutdown(PR_GetEnv("MOZ_CC_LOG_SHUTDOWN") != nullptr),
        mAllTracesAll(false),
        mAllTracesShutdown(false),
        mLogGC(!PR_GetEnv("MOZ_CC_DISABLE_GC_LOG")),
        mLogWindowOnly(PR_GetEnv("MOZ_CC_LOG_WINDOW_ONLY")) {
    if (const char* lssEnv = PR_GetEnv("MOZ_CC_LOG_SHUTDOWN_SKIP")) {
      mLogShutdown = true;
      nsDependentCString lssString(lssEnv);
      nsresult rv;
      int32_t lss = lssString.ToInteger(&rv);
      if (NS_SUCCEEDED(rv) && lss >= 0) {
        mLogShutdownSkip = lss;
      }
    }

    const char* logThreadEnv = PR_GetEnv("MOZ_CC_LOG_THREAD");
    bool threadLogging = true;
    if (logThreadEnv && !!strcmp(logThreadEnv, "all")) {
      if (NS_IsMainThread()) {
        threadLogging = !strcmp(logThreadEnv, "main");
      } else {
        threadLogging = !strcmp(logThreadEnv, "worker");
      }
    }

    const char* logProcessEnv = PR_GetEnv("MOZ_CC_LOG_PROCESS");
    bool processLogging = true;
    if (logProcessEnv && !!strcmp(logProcessEnv, "all")) {
      switch (XRE_GetProcessType()) {
        case GeckoProcessType_Default:
          processLogging = !strcmp(logProcessEnv, "main");
          break;
        case GeckoProcessType_Content:
          processLogging = !strcmp(logProcessEnv, "content");
          break;
        default:
          processLogging = false;
          break;
      }
    }
    mLogThisThread = threadLogging && processLogging;

    const char* allTracesEnv = PR_GetEnv("MOZ_CC_ALL_TRACES");
    if (allTracesEnv) {
      if (!strcmp(allTracesEnv, "all")) {
        mAllTracesAll = true;
      } else if (!strcmp(allTracesEnv, "shutdown")) {
        mAllTracesShutdown = true;
      }
    }
  }

  // aShutdownCount is how many shutdown CCs we've started.
  // For non-shutdown CCs, we'll pass in 0.
  // For the first shutdown CC, we'll pass in 1.
  bool LogThisCC(int32_t aShutdownCount) {
#ifdef DEBUG
    if (mLogWindowOnly && NS_IsMainThread() &&
        nsContentUtils::GetCurrentInnerOrOuterWindowCount() == 0) {
      return false;
    }
#endif
    if (mLogAll) {
      return mLogThisThread;
    }
    if (aShutdownCount == 0 || !mLogShutdown) {
      return false;
    }
    if (aShutdownCount <= mLogShutdownSkip) {
      return false;
    }
    return mLogThisThread;
  }

  bool AllTracesThisCC(bool aIsShutdown) {
    return mAllTracesAll || (aIsShutdown && mAllTracesShutdown);
  }

  bool LogThisGC() const { return mLogGC; }
};

#ifdef COLLECT_TIME_DEBUG
class TimeLog {
 public:
  TimeLog() : mLastCheckpoint(TimeStamp::Now()) {}

  void Checkpoint(const char* aEvent) {
    TimeStamp now = TimeStamp::Now();
    double dur = (now - mLastCheckpoint).ToMilliseconds();
    if (dur >= 0.5) {
      printf("cc: %s took %.1fms\n", aEvent, dur);
    }
    mLastCheckpoint = now;
  }

 private:
  TimeStamp mLastCheckpoint;
};
#else
class TimeLog {
 public:
  TimeLog() = default;
  void Checkpoint(const char* aEvent) {}
};
#endif

////////////////////////////////////////////////////////////////////////
// Base types
////////////////////////////////////////////////////////////////////////

class PtrInfo;

class EdgePool {
 public:
  // EdgePool allocates arrays of void*, primarily to hold PtrInfo*.
  // However, at the end of a block, the last two pointers are a null
  // and then a void** pointing to the next block.  This allows
  // EdgePool::Iterators to be a single word but still capable of crossing
  // block boundaries.

  EdgePool() {
    mSentinelAndBlocks[0].block = nullptr;
    mSentinelAndBlocks[1].block = nullptr;
  }

  ~EdgePool() {
    MOZ_ASSERT(!mSentinelAndBlocks[0].block && !mSentinelAndBlocks[1].block,
               "Didn't call Clear()?");
  }

  void Clear() {
    EdgeBlock* b = EdgeBlocks();
    while (b) {
      EdgeBlock* next = b->Next();
      delete b;
      b = next;
    }

    mSentinelAndBlocks[0].block = nullptr;
    mSentinelAndBlocks[1].block = nullptr;
  }

#ifdef DEBUG
  bool IsEmpty() {
    return !mSentinelAndBlocks[0].block && !mSentinelAndBlocks[1].block;
  }
#endif

 private:
  struct EdgeBlock;
  union PtrInfoOrBlock {
    // Use a union to avoid reinterpret_cast and the ensuing
    // potential aliasing bugs.
    PtrInfo* ptrInfo;
    EdgeBlock* block;
  };
  struct EdgeBlock {
    enum { EdgeBlockSize = 16 * 1024 };

    PtrInfoOrBlock mPointers[EdgeBlockSize];
    EdgeBlock() {
      mPointers[EdgeBlockSize - 2].block = nullptr;  // sentinel
      mPointers[EdgeBlockSize - 1].block = nullptr;  // next block pointer
    }
    EdgeBlock*& Next() { return mPointers[EdgeBlockSize - 1].block; }
    PtrInfoOrBlock* Start() { return &mPointers[0]; }
    PtrInfoOrBlock* End() { return &mPointers[EdgeBlockSize - 2]; }
  };

  // Store the null sentinel so that we can have valid iterators
  // before adding any edges and without adding any blocks.
  PtrInfoOrBlock mSentinelAndBlocks[2];

  EdgeBlock*& EdgeBlocks() { return mSentinelAndBlocks[1].block; }
  EdgeBlock* EdgeBlocks() const { return mSentinelAndBlocks[1].block; }

 public:
  class Iterator {
   public:
    Iterator() : mPointer(nullptr) {}
    explicit Iterator(PtrInfoOrBlock* aPointer) : mPointer(aPointer) {}
    Iterator(const Iterator& aOther) = default;

    Iterator& operator++() {
      if (!mPointer->ptrInfo) {
        // Null pointer is a sentinel for link to the next block.
        mPointer = (mPointer + 1)->block->mPointers;
      }
      ++mPointer;
      return *this;
    }

    PtrInfo* operator*() const {
      if (!mPointer->ptrInfo) {
        // Null pointer is a sentinel for link to the next block.
        return (mPointer + 1)->block->mPointers->ptrInfo;
      }
      return mPointer->ptrInfo;
    }
    bool operator==(const Iterator& aOther) const {
      return mPointer == aOther.mPointer;
    }
    bool operator!=(const Iterator& aOther) const {
      return mPointer != aOther.mPointer;
    }

#ifdef DEBUG_CC_GRAPH
    bool Initialized() const { return mPointer != nullptr; }
#endif

   private:
    PtrInfoOrBlock* mPointer;
  };

  class Builder;
  friend class Builder;
  class Builder {
   public:
    explicit Builder(EdgePool& aPool)
        : mCurrent(&aPool.mSentinelAndBlocks[0]),
          mBlockEnd(&aPool.mSentinelAndBlocks[0]),
          mNextBlockPtr(&aPool.EdgeBlocks()) {}

    Iterator Mark() { return Iterator(mCurrent); }

    void Add(PtrInfo* aEdge) {
      if (mCurrent == mBlockEnd) {
        EdgeBlock* b = new EdgeBlock();
        *mNextBlockPtr = b;
        mCurrent = b->Start();
        mBlockEnd = b->End();
        mNextBlockPtr = &b->Next();
      }
      (mCurrent++)->ptrInfo = aEdge;
    }

   private:
    // mBlockEnd points to space for null sentinel
    PtrInfoOrBlock* mCurrent;
    PtrInfoOrBlock* mBlockEnd;
    EdgeBlock** mNextBlockPtr;
  };

  size_t SizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
    size_t n = 0;
    EdgeBlock* b = EdgeBlocks();
    while (b) {
      n += aMallocSizeOf(b);
      b = b->Next();
    }
    return n;
  }
};

#ifdef DEBUG_CC_GRAPH
#  define CC_GRAPH_ASSERT(b) MOZ_ASSERT(b)
#else
#  define CC_GRAPH_ASSERT(b)
#endif

enum NodeColor { black, white, grey };

// This structure should be kept as small as possible; we may expect
// hundreds of thousands of them to be allocated and touched
// repeatedly during each cycle collection.
class PtrInfo final {
 public:
  // mParticipant knows a more concrete type.
  void* mPointer;
  nsCycleCollectionParticipant* mParticipant;
  uint32_t mColor : 2;
  uint32_t mInternalRefs : 30;
  uint32_t mRefCount;

 private:
  EdgePool::Iterator mFirstChild;

  static const uint32_t kInitialRefCount = UINT32_MAX - 1;

 public:
  PtrInfo(void* aPointer, nsCycleCollectionParticipant* aParticipant)
      : mPointer(aPointer),
        mParticipant(aParticipant),
        mColor(grey),
        mInternalRefs(0),
        mRefCount(kInitialRefCount) {
    MOZ_ASSERT(aParticipant);

    // We initialize mRefCount to a large non-zero value so
    // that it doesn't look like a JS object to the cycle collector
    // in the case where the object dies before being traversed.
    MOZ_ASSERT(!IsGrayJS() && !IsBlackJS());
  }

  // Allow NodePool::NodeBlock's constructor to compile.
  PtrInfo()
      : mPointer{nullptr},
        mParticipant{nullptr},
        mColor{0},
        mInternalRefs{0},
        mRefCount{0} {
    MOZ_ASSERT_UNREACHABLE("should never be called");
  }

  bool IsGrayJS() const { return mRefCount == 0; }

  bool IsBlackJS() const { return mRefCount == UINT32_MAX; }

  bool WasTraversed() const { return mRefCount != kInitialRefCount; }

  EdgePool::Iterator FirstChild() const {
    CC_GRAPH_ASSERT(mFirstChild.Initialized());
    return mFirstChild;
  }

  // this PtrInfo must be part of a NodePool
  EdgePool::Iterator LastChild() const {
    CC_GRAPH_ASSERT((this + 1)->mFirstChild.Initialized());
    return (this + 1)->mFirstChild;
  }

  void SetFirstChild(EdgePool::Iterator aFirstChild) {
    CC_GRAPH_ASSERT(aFirstChild.Initialized());
    mFirstChild = aFirstChild;
  }

  // this PtrInfo must be part of a NodePool
  void SetLastChild(EdgePool::Iterator aLastChild) {
    CC_GRAPH_ASSERT(aLastChild.Initialized());
    (this + 1)->mFirstChild = aLastChild;
  }

  void AnnotatedReleaseAssert(bool aCondition, const char* aMessage);
};

void PtrInfo::AnnotatedReleaseAssert(bool aCondition, const char* aMessage) {
  if (aCondition) {
    return;
  }

  const char* piName = "Unknown";
  if (mParticipant) {
    piName = mParticipant->ClassName();
  }
  nsPrintfCString msg("%s, for class %s", aMessage, piName);
  NS_WARNING(msg.get());
  CrashReporter::RecordAnnotationNSCString(
      CrashReporter::Annotation::CycleCollector, msg);

  MOZ_CRASH();
}

/**
 * A structure designed to be used like a linked list of PtrInfo, except
 * it allocates many PtrInfos at a time.
 */
class NodePool {
 private:
  // The -2 allows us to use |NodeBlockSize + 1| for |mEntries|, and fit
  // |mNext|, all without causing slop.
  enum { NodeBlockSize = 4 * 1024 - 2 };

  struct NodeBlock {
    // We create and destroy NodeBlock using moz_xmalloc/free rather than new
    // and delete to avoid calling its constructor and destructor.
    NodeBlock() : mNext{nullptr} {
      MOZ_ASSERT_UNREACHABLE("should never be called");

      // Ensure NodeBlock is the right size (see the comment on NodeBlockSize
      // above).
      static_assert(
          sizeof(NodeBlock) == 81904 ||  // 32-bit; equals 19.996 x 4 KiB pages
              sizeof(NodeBlock) ==
                  131048,  // 64-bit; equals 31.994 x 4 KiB pages
          "ill-sized NodeBlock");
    }
    ~NodeBlock() { MOZ_ASSERT_UNREACHABLE("should never be called"); }

    NodeBlock* mNext;
    PtrInfo mEntries[NodeBlockSize + 1];  // +1 to store last child of last node
  };

 public:
  NodePool() : mBlocks(nullptr), mLast(nullptr) {}

  ~NodePool() { MOZ_ASSERT(!mBlocks, "Didn't call Clear()?"); }

  void Clear() {
    NodeBlock* b = mBlocks;
    while (b) {
      NodeBlock* n = b->mNext;
      free(b);
      b = n;
    }

    mBlocks = nullptr;
    mLast = nullptr;
  }

#ifdef DEBUG
  bool IsEmpty() { return !mBlocks && !mLast; }
#endif

  class Builder;
  friend class Builder;
  class Builder {
   public:
    explicit Builder(NodePool& aPool)
        : mNextBlock(&aPool.mBlocks), mNext(aPool.mLast), mBlockEnd(nullptr) {
      MOZ_ASSERT(!aPool.mBlocks && !aPool.mLast, "pool not empty");
    }
    PtrInfo* Add(void* aPointer, nsCycleCollectionParticipant* aParticipant) {
      if (mNext == mBlockEnd) {
        NodeBlock* block = static_cast<NodeBlock*>(malloc(sizeof(NodeBlock)));
        if (!block) {
          return nullptr;
        }

        *mNextBlock = block;
        mNext = block->mEntries;
        mBlockEnd = block->mEntries + NodeBlockSize;
        block->mNext = nullptr;
        mNextBlock = &block->mNext;
      }
      return new (mozilla::KnownNotNull, mNext++)
          PtrInfo(aPointer, aParticipant);
    }

   private:
    NodeBlock** mNextBlock;
    PtrInfo*& mNext;
    PtrInfo* mBlockEnd;
  };

  class Enumerator;
  friend class Enumerator;
  class Enumerator {
   public:
    explicit Enumerator(NodePool& aPool)
        : mFirstBlock(aPool.mBlocks),
          mCurBlock(nullptr),
          mNext(nullptr),
          mBlockEnd(nullptr),
          mLast(aPool.mLast) {}

    bool IsDone() const { return mNext == mLast; }

    bool AtBlockEnd() const { return mNext == mBlockEnd; }

    PtrInfo* GetNext() {
      MOZ_ASSERT(!IsDone(), "calling GetNext when done");
      if (mNext == mBlockEnd) {
        NodeBlock* nextBlock = mCurBlock ? mCurBlock->mNext : mFirstBlock;
        mNext = nextBlock->mEntries;
        mBlockEnd = mNext + NodeBlockSize;
        mCurBlock = nextBlock;
      }
      return mNext++;
    }

   private:
    // mFirstBlock is a reference to allow an Enumerator to be constructed
    // for an empty graph.
    NodeBlock*& mFirstBlock;
    NodeBlock* mCurBlock;
    // mNext is the next value we want to return, unless mNext == mBlockEnd
    // NB: mLast is a reference to allow enumerating while building!
    PtrInfo* mNext;
    PtrInfo* mBlockEnd;
    PtrInfo*& mLast;
  };

  size_t SizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
    // We don't measure the things pointed to by mEntries[] because those
    // pointers are non-owning.
    size_t n = 0;
    NodeBlock* b = mBlocks;
    while (b) {
      n += aMallocSizeOf(b);
      b = b->mNext;
    }
    return n;
  }

 private:
  NodeBlock* mBlocks;
  PtrInfo* mLast;
};

struct PtrToNodeHashPolicy {
  using Key = PtrInfo*;
  using Lookup = void*;

  static js::HashNumber hash(const Lookup& aLookup) {
    return mozilla::HashGeneric(aLookup);
  }

  static bool match(const Key& aKey, const Lookup& aLookup) {
    return aKey->mPointer == aLookup;
  }
};

struct WeakMapping {
  // map and key will be null if the corresponding objects are GC marked
  PtrInfo* mMap;
  PtrInfo* mKey;
  PtrInfo* mKeyDelegate;
  PtrInfo* mVal;
};

class CCGraphBuilder;

struct CCGraph {
  NodePool mNodes;
  EdgePool mEdges;
  nsTArray<WeakMapping> mWeakMaps;
  uint32_t mRootCount;

 private:
  friend CCGraphBuilder;

  mozilla::HashSet<PtrInfo*, PtrToNodeHashPolicy> mPtrInfoMap;

  bool mOutOfMemory;

  static const uint32_t kInitialMapLength = 16384;

 public:
  CCGraph()
      : mRootCount(0), mPtrInfoMap(kInitialMapLength), mOutOfMemory(false) {}

  ~CCGraph() = default;

  void Init() { MOZ_ASSERT(IsEmpty(), "Failed to call CCGraph::Clear"); }

  void Clear() {
    mNodes.Clear();
    mEdges.Clear();
    mWeakMaps.Clear();
    mRootCount = 0;
    mPtrInfoMap.clearAndCompact();
    mOutOfMemory = false;
  }

#ifdef DEBUG
  bool IsEmpty() {
    return mNodes.IsEmpty() && mEdges.IsEmpty() && mWeakMaps.IsEmpty() &&
           mRootCount == 0 && mPtrInfoMap.empty();
  }
#endif

  PtrInfo* FindNode(void* aPtr);
  void RemoveObjectFromMap(void* aObject);

  uint32_t MapCount() const { return mPtrInfoMap.count(); }

  size_t SizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
    size_t n = 0;

    n += mNodes.SizeOfExcludingThis(aMallocSizeOf);
    n += mEdges.SizeOfExcludingThis(aMallocSizeOf);

    // We don't measure what the WeakMappings point to, because the
    // pointers are non-owning.
    n += mWeakMaps.ShallowSizeOfExcludingThis(aMallocSizeOf);

    n += mPtrInfoMap.shallowSizeOfExcludingThis(aMallocSizeOf);

    return n;
  }
};

PtrInfo* CCGraph::FindNode(void* aPtr) {
  auto p = mPtrInfoMap.lookup(aPtr);
  return p ? *p : nullptr;
}

void CCGraph::RemoveObjectFromMap(void* aObj) {
  auto p = mPtrInfoMap.lookup(aObj);
  if (p) {
    PtrInfo* pinfo = *p;
    pinfo->mPointer = nullptr;
    pinfo->mParticipant = nullptr;
    mPtrInfoMap.remove(p);
  }
}

static nsISupports* CanonicalizeXPCOMParticipant(nsISupports* aIn) {
  nsISupports* out = nullptr;
  aIn->QueryInterface(NS_GET_IID(nsCycleCollectionISupports),
                      reinterpret_cast<void**>(&out));
  return out;
}

struct nsPurpleBufferEntry {
  nsPurpleBufferEntry(void* aObject, nsCycleCollectingAutoRefCnt* aRefCnt,
                      nsCycleCollectionParticipant* aParticipant)
      : mObject(aObject), mRefCnt(aRefCnt), mParticipant(aParticipant) {}

  nsPurpleBufferEntry(nsPurpleBufferEntry&& aOther)
      : mObject(nullptr), mRefCnt(nullptr), mParticipant(nullptr) {
    Swap(aOther);
  }

  void Swap(nsPurpleBufferEntry& aOther) {
    std::swap(mObject, aOther.mObject);
    std::swap(mRefCnt, aOther.mRefCnt);
    std::swap(mParticipant, aOther.mParticipant);
  }

  void Clear() {
    mRefCnt->RemoveFromPurpleBuffer();
    mRefCnt = nullptr;
    mObject = nullptr;
    mParticipant = nullptr;
  }

  ~nsPurpleBufferEntry() {
    if (mRefCnt) {
      mRefCnt->RemoveFromPurpleBuffer();
    }
  }

  void* mObject;
  nsCycleCollectingAutoRefCnt* mRefCnt;
  nsCycleCollectionParticipant* mParticipant;  // nullptr for nsISupports
};

class nsCycleCollector;

struct nsPurpleBuffer {
 private:
  uint32_t mCount;

  // Try to match the size of a jemalloc bucket, to minimize slop bytes.
  // - On 32-bit platforms sizeof(nsPurpleBufferEntry) is 12, so mEntries'
  //   Segment is 16,372 bytes.
  // - On 64-bit platforms sizeof(nsPurpleBufferEntry) is 24, so mEntries'
  //   Segment is 32,760 bytes.
  static const uint32_t kEntriesPerSegment = 1365;
  static const size_t kSegmentSize =
      sizeof(nsPurpleBufferEntry) * kEntriesPerSegment;
  typedef SegmentedVector<nsPurpleBufferEntry, kSegmentSize,
                          InfallibleAllocPolicy>
      PurpleBufferVector;
  PurpleBufferVector mEntries;

 public:
  nsPurpleBuffer() : mCount(0) {
    static_assert(
        sizeof(PurpleBufferVector::Segment) == 16372 ||      // 32-bit
            sizeof(PurpleBufferVector::Segment) == 32760 ||  // 64-bit
            sizeof(PurpleBufferVector::Segment) == 32744,    // 64-bit Windows
        "ill-sized nsPurpleBuffer::mEntries");
  }

  ~nsPurpleBuffer() = default;

  // This method compacts mEntries.
  template <class PurpleVisitor>
  void VisitEntries(PurpleVisitor& aVisitor) {
    Maybe<AutoRestore<bool>> ar;
    if (NS_IsMainThread()) {
      ar.emplace(gNurseryPurpleBufferEnabled);
      gNurseryPurpleBufferEnabled = false;
      ClearNurseryPurpleBuffer();
    }

    if (mEntries.IsEmpty()) {
      return;
    }

    uint32_t oldLength = mEntries.Length();
    uint32_t keptLength = 0;
    auto revIter = mEntries.IterFromLast();
    auto iter = mEntries.Iter();
    // After iteration this points to the first empty entry.
    auto firstEmptyIter = mEntries.Iter();
    auto iterFromLastEntry = mEntries.IterFromLast();
    for (; !iter.Done(); iter.Next()) {
      nsPurpleBufferEntry& e = iter.Get();
      if (e.mObject) {
        if (!aVisitor.Visit(*this, &e)) {
          return;
        }
      }

      // Visit call above may have cleared the entry, or the entry was empty
      // already.
      if (!e.mObject) {
        // Try to find a non-empty entry from the end of the vector.
        for (; !revIter.Done(); revIter.Prev()) {
          nsPurpleBufferEntry& otherEntry = revIter.Get();
          if (&e == &otherEntry) {
            break;
          }
          if (otherEntry.mObject) {
            if (!aVisitor.Visit(*this, &otherEntry)) {
              return;
            }
            // Visit may have cleared otherEntry.
            if (otherEntry.mObject) {
              e.Swap(otherEntry);
              revIter.Prev();  // We've swapped this now empty entry.
              break;
            }
          }
        }
      }

      // Entry is non-empty even after the Visit call, ensure it is kept
      // in mEntries.
      if (e.mObject) {
        firstEmptyIter.Next();
        ++keptLength;
      }

      if (&e == &revIter.Get()) {
        break;
      }
    }

    // There were some empty entries.
    if (oldLength != keptLength) {
      // While visiting entries, some new ones were possibly added. This can
      // happen during CanSkip. Move all such new entries to be after other
      // entries. Note, we don't call Visit on newly added entries!
      if (&iterFromLastEntry.Get() != &mEntries.GetLast()) {
        iterFromLastEntry.Next();  // Now pointing to the first added entry.
        auto& iterForNewEntries = iterFromLastEntry;
        while (!iterForNewEntries.Done()) {
          MOZ_ASSERT(!firstEmptyIter.Done());
          MOZ_ASSERT(!firstEmptyIter.Get().mObject);
          firstEmptyIter.Get().Swap(iterForNewEntries.Get());
          firstEmptyIter.Next();
          iterForNewEntries.Next();
        }
      }

      mEntries.PopLastN(oldLength - keptLength);
    }
  }

  void FreeBlocks() {
    mCount = 0;
    mEntries.Clear();
  }

  void SelectPointers(CCGraphBuilder& aBuilder);

  // RemoveSkippable removes entries from the purple buffer synchronously
  // (1) if !aAsyncSnowWhiteFreeing and nsPurpleBufferEntry::mRefCnt is 0 or
  // (2) if nsXPCOMCycleCollectionParticipant::CanSkip() for the obj or
  // (3) if nsPurpleBufferEntry::mRefCnt->IsPurple() is false.
  // (4) If aRemoveChildlessNodes is true, then any nodes in the purple buffer
  //     that will have no children in the cycle collector graph will also be
  //     removed. CanSkip() may be run on these children.
  void RemoveSkippable(nsCycleCollector* aCollector, SliceBudget& aBudget,
                       bool aRemoveChildlessNodes, bool aAsyncSnowWhiteFreeing,
                       CC_ForgetSkippableCallback aCb);

  MOZ_ALWAYS_INLINE void Put(void* aObject, nsCycleCollectionParticipant* aCp,
                             nsCycleCollectingAutoRefCnt* aRefCnt) {
    nsPurpleBufferEntry entry(aObject, aRefCnt, aCp);
    Unused << mEntries.Append(std::move(entry));
    MOZ_ASSERT(!entry.mRefCnt, "Move didn't work!");
    ++mCount;
  }

  void Remove(nsPurpleBufferEntry* aEntry) {
    MOZ_ASSERT(mCount != 0, "must have entries");
    --mCount;
    aEntry->Clear();
  }

  uint32_t Count() const { return mCount; }

  size_t SizeOfExcludingThis(MallocSizeOf aMallocSizeOf) const {
    return mEntries.SizeOfExcludingThis(aMallocSizeOf);
  }
};

static bool AddPurpleRoot(CCGraphBuilder& aBuilder, void* aRoot,
                          nsCycleCollectionParticipant* aParti);

struct SelectPointersVisitor {
  explicit SelectPointersVisitor(CCGraphBuilder& aBuilder)
      : mBuilder(aBuilder) {}

  bool Visit(nsPurpleBuffer& aBuffer, nsPurpleBufferEntry* aEntry) {
    MOZ_ASSERT(aEntry->mObject, "Null object in purple buffer");
    MOZ_ASSERT(aEntry->mRefCnt->get() != 0,
               "SelectPointersVisitor: snow-white object in the purple buffer");
    if (!aEntry->mRefCnt->IsPurple() ||
        AddPurpleRoot(mBuilder, aEntry->mObject, aEntry->mParticipant)) {
      aBuffer.Remove(aEntry);
    }
    return true;
  }

 private:
  CCGraphBuilder& mBuilder;
};

void nsPurpleBuffer::SelectPointers(CCGraphBuilder& aBuilder) {
  SelectPointersVisitor visitor(aBuilder);
  VisitEntries(visitor);

  MOZ_ASSERT(mCount == 0, "AddPurpleRoot failed");
  if (mCount == 0) {
    FreeBlocks();
  }
}

enum ccPhase {
  IdlePhase,
  GraphBuildingPhase,
  ScanAndCollectWhitePhase,
  CleanupPhase
};

enum ccIsManual { CCIsNotManual = false, CCIsManual = true };

////////////////////////////////////////////////////////////////////////
// Top level structure for the cycle collector.
////////////////////////////////////////////////////////////////////////

class JSPurpleBuffer;

class nsCycleCollector : public nsIMemoryReporter {
 public:
  NS_DECL_ISUPPORTS
  NS_DECL_NSIMEMORYREPORTER

 private:
  bool mActivelyCollecting;
  bool mFreeingSnowWhite;
  // mScanInProgress should be false when we're collecting white objects.
  bool mScanInProgress;
  CycleCollectorResults mResults;
  TimeStamp mCollectionStart;

  CycleCollectedJSRuntime* mCCJSRuntime;

  ccPhase mIncrementalPhase;
  int32_t mShutdownCount = 0;
  CCGraph mGraph;
  UniquePtr<CCGraphBuilder> mBuilder;
  RefPtr<nsCycleCollectorLogger> mLogger;

#ifdef DEBUG
  nsISerialEventTarget* mEventTarget;
#endif

  nsCycleCollectorParams mParams;

  uint32_t mWhiteNodeCount;

  CC_BeforeUnlinkCallback mBeforeUnlinkCB;
  CC_ForgetSkippableCallback mForgetSkippableCB;

  nsPurpleBuffer mPurpleBuf;

  uint32_t mUnmergedNeeded;
  uint32_t mMergedInARow;

  RefPtr<JSPurpleBuffer> mJSPurpleBuffer;

 private:
  virtual ~nsCycleCollector();

 public:
  nsCycleCollector();

  void SetCCJSRuntime(CycleCollectedJSRuntime* aCCRuntime);
  void ClearCCJSRuntime();

  void SetBeforeUnlinkCallback(CC_BeforeUnlinkCallback aBeforeUnlinkCB) {
    CheckThreadSafety();
    mBeforeUnlinkCB = aBeforeUnlinkCB;
  }

  void SetForgetSkippableCallback(
      CC_ForgetSkippableCallback aForgetSkippableCB) {
    CheckThreadSafety();
    mForgetSkippableCB = aForgetSkippableCB;
  }

  void Suspect(void* aPtr, nsCycleCollectionParticipant* aCp,
               nsCycleCollectingAutoRefCnt* aRefCnt);
  void SuspectNurseryEntries();
  uint32_t SuspectedCount();
  void ForgetSkippable(SliceBudget& aBudget, bool aRemoveChildlessNodes,
                       bool aAsyncSnowWhiteFreeing);
  bool FreeSnowWhite(bool aUntilNoSWInPurpleBuffer);
  bool FreeSnowWhiteWithBudget(SliceBudget& aBudget);

  // This method assumes its argument is already canonicalized.
  void RemoveObjectFromGraph(void* aPtr);

  void PrepareForGarbageCollection();
  void FinishAnyCurrentCollection(CCReason aReason);

  bool Collect(CCReason aReason, ccIsManual aIsManual, SliceBudget& aBudget,
               nsICycleCollectorListener* aManualListener,
               bool aPreferShorterSlices = false);
  MOZ_CAN_RUN_SCRIPT
  void Shutdown(bool aDoCollect);

  bool IsIdle() const { return mIncrementalPhase == IdlePhase; }

  void SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf,
                           size_t* aObjectSize, size_t* aGraphSize,
                           size_t* aPurpleBufferSize) const;

  JSPurpleBuffer* GetJSPurpleBuffer();

  CycleCollectedJSRuntime* Runtime() { return mCCJSRuntime; }

 private:
  void CheckThreadSafety();
  MOZ_CAN_RUN_SCRIPT
  void ShutdownCollect();

  void FixGrayBits(bool aIsShutdown, TimeLog& aTimeLog);
  bool IsIncrementalGCInProgress();
  void FinishAnyIncrementalGCInProgress();
  bool ShouldMergeZones(ccIsManual aIsManual);
  void MaybeInitLogger(bool aIsShutdown, bool aForGC);

  void BeginCollection(CCReason aReason, ccIsManual aIsManual,
                       nsICycleCollectorListener* aManualListener);
  void MarkRoots(SliceBudget& aBudget);
  void ScanRoots(bool aFullySynchGraphBuild);
  void ScanIncrementalRoots();
  void ScanWhiteNodes(bool aFullySynchGraphBuild);
  void ScanBlackNodes();
  void ScanWeakMaps();

  // returns whether anything was collected
  bool CollectWhite();

  void CleanupAfterCollection();
};

NS_IMPL_ISUPPORTS(nsCycleCollector, nsIMemoryReporter)

/**
 * GraphWalker is templatized over a Visitor class that must provide
 * the following two methods:
 *
 * bool ShouldVisitNode(PtrInfo const *pi);
 * void VisitNode(PtrInfo *pi);
 */
template <class Visitor>
class GraphWalker {
 private:
  Visitor mVisitor;

  void DoWalk(nsDeque<PtrInfo>& aQueue);

  void CheckedPush(nsDeque<PtrInfo>& aQueue, PtrInfo* aPi) {
    if (!aPi) {
      MOZ_CRASH();
    }
    if (!aQueue.Push(aPi, fallible)) {
      mVisitor.Failed();
    }
  }

 public:
  void Walk(PtrInfo* aPi);
  void WalkFromRoots(CCGraph& aGraph);
  // copy-constructing the visitor should be cheap, and less
  // indirection than using a reference
  explicit GraphWalker(const Visitor aVisitor) : mVisitor(aVisitor) {}
};

////////////////////////////////////////////////////////////////////////
// The static collector struct
////////////////////////////////////////////////////////////////////////

struct CollectorData {
  RefPtr<nsCycleCollector> mCollector;
  CycleCollectedJSContext* mContext;
  UniquePtr<mozilla::CycleCollectorStats> mStats;
};

static MOZ_THREAD_LOCAL(CollectorData*) sCollectorData;

mozilla::CycleCollectorStats* CycleCollectorStats::Get() {
  MOZ_ASSERT(sCollectorData.get());
  return sCollectorData.get()->mStats.get();
}

////////////////////////////////////////////////////////////////////////
// Profiler & ETW markers
////////////////////////////////////////////////////////////////////////

namespace geckoprofiler::markers {
struct CCIntervalMarker : public mozilla::BaseMarkerType<CCIntervalMarker> {
  static constexpr const char* Name = "CC";
  static constexpr const char* Description =
      "Summary data for the core part of a cycle collection, possibly "
      "encompassing a set of incremental slices. The thread is not "
      "blocked for the entire major CC interval, only for the individual "
      "slices.";

  using MS = mozilla::MarkerSchema;
  static constexpr MS::PayloadField PayloadFields[] = {
      {"mReason", MS::InputType::CString, "Reason", MS::Format::String,
       MS::PayloadFlags::Searchable},
      {"mMaxSliceTime", MS::InputType::TimeDuration, "Max Slice Time",
       MS::Format::Duration},
      {"mSuspected", MS::InputType::Uint32, "Suspected Objects",
       MS::Format::Integer},
      {"mSlices", MS::InputType::Uint32, "Number of Slices",
       MS::Format::Integer},
      {"mAnyManual", MS::InputType::Boolean, "Manually Triggered",
       MS::Format::Integer},
      {"mForcedGC", MS::InputType::Boolean, "GC Forced", MS::Format::Integer},
      {"mMergedZones", MS::InputType::Boolean, "Zones Merged",
       MS::Format::Integer},
      {"mForgetSkippable", MS::InputType::Uint32, "Forget Skippables",
       MS::Format::Integer},
      {"mVisitedRefCounted", MS::InputType::Uint32,
       "Refcounted Objects Visited", MS::Format::Integer},
      {"mVisitedGCed", MS::InputType::Uint32, "GC Objects Visited",
       MS::Format::Integer},
      {"mFreedRefCounted", MS::InputType::Uint32, "Refcounted Objects Freed",
       MS::Format::Integer},
      {"mFreedGCed", MS::InputType::Uint32, "GC Objects Freed",
       MS::Format::Integer},
      {"mFreedJSZones", MS::InputType::Uint32, "JS Zones Freed",
       MS::Format::Integer},
      {"mRemovedPurples", MS::InputType::Uint32,
       "Objects Removed From Purple Buffer", MS::Format::Integer}};

  static constexpr MS::Location Locations[] = {MS::Location::MarkerChart,
                                               MS::Location::MarkerTable,
                                               MS::Location::TimelineMemory};
  static constexpr MS::ETWMarkerGroup Group = MS::ETWMarkerGroup::Memory;

  static void TranslateMarkerInputToSchema(
      void* aContext, bool aIsStart,
      const mozilla::ProfilerString8View& aReason,
      uint32_t aForgetSkippableBeforeCC, uint32_t aSuspectedAtCCStart,
      uint32_t aRemovedPurples, bool aForcedGC, bool aMergedZones,
      bool aAnyManual, uint32_t aVisitedRefCounted, uint32_t aVisitedGCed,
      uint32_t aFreedRefCounted, uint32_t aFreedGCed, uint32_t aFreedJSZones,
      uint32_t aNumSlices, const mozilla::TimeDuration& aMaxSliceTime) {
    uint32_t none = 0;
    if (aIsStart) {
      ETW::OutputMarkerSchema(aContext, CCIntervalMarker{}, aReason,
                              mozilla::TimeDuration{}, aSuspectedAtCCStart,
                              none, false, false, false,
                              aForgetSkippableBeforeCC, none, none, none, none,
                              none, aRemovedPurples);
    } else {
      ETW::OutputMarkerSchema(
          aContext, CCIntervalMarker{}, mozilla::ProfilerStringView(""),
          aMaxSliceTime, none, aNumSlices, aAnyManual, aForcedGC, aMergedZones,
          none, aVisitedRefCounted, aVisitedGCed, aFreedRefCounted, aFreedGCed,
          aFreedJSZones, none);
    }
  }

  static void StreamJSONMarkerData(
      mozilla::baseprofiler::SpliceableJSONWriter& aWriter, bool aIsStart,
      const mozilla::ProfilerString8View& aReason,
      uint32_t aForgetSkippableBeforeCC, uint32_t aSuspectedAtCCStart,
      uint32_t aRemovedPurples, bool aForcedGC, bool aMergedZones,
      bool aAnyManual, uint32_t aVisitedRefCounted, uint32_t aVisitedGCed,
      uint32_t aFreedRefCounted, uint32_t aFreedGCed, uint32_t aFreedJSZones,
      uint32_t aNumSlices, mozilla::TimeDuration aMaxSliceTime) {
    if (aIsStart) {
      aWriter.StringProperty("mReason", aReason);
      aWriter.IntProperty("mSuspected", aSuspectedAtCCStart);
      aWriter.IntProperty("mForgetSkippable", aForgetSkippableBeforeCC);
      aWriter.IntProperty("mRemovedPurples", aRemovedPurples);
    } else {
      aWriter.TimeDoubleMsProperty("mMaxSliceTime",
                                   aMaxSliceTime.ToMilliseconds());
      aWriter.IntProperty("mSlices", aNumSlices);

      aWriter.BoolProperty("mAnyManual", aAnyManual);
      aWriter.BoolProperty("mForcedGC", aForcedGC);
      aWriter.BoolProperty("mMergedZones", aMergedZones);
      aWriter.IntProperty("mVisitedRefCounted", aVisitedRefCounted);
      aWriter.IntProperty("mVisitedGCed", aVisitedGCed);
      aWriter.IntProperty("mFreedRefCounted", aFreedRefCounted);
      aWriter.IntProperty("mFreedGCed", aFreedGCed);
      aWriter.IntProperty("mFreedJSZones", aFreedJSZones);
    }
  }
};
}  // namespace geckoprofiler::markers

////////////////////////////////////////////////////////////////////////
// Utility functions
////////////////////////////////////////////////////////////////////////

static inline void ToParticipant(nsISupports* aPtr,
                                 nsXPCOMCycleCollectionParticipant** aCp) {
  // We use QI to move from an nsISupports to an
  // nsXPCOMCycleCollectionParticipant, which is a per-class singleton helper
  // object that implements traversal and unlinking logic for the nsISupports
  // in question.
  *aCp = nullptr;
  CallQueryInterface(aPtr, aCp);
}

static void ToParticipant(void* aParti, nsCycleCollectionParticipant** aCp) {
  // If the participant is null, this is an nsISupports participant,
  // so we must QI to get the real participant.

  if (!*aCp) {
    nsISupports* nsparti = static_cast<nsISupports*>(aParti);
    MOZ_ASSERT(CanonicalizeXPCOMParticipant(nsparti) == nsparti);
    nsXPCOMCycleCollectionParticipant* xcp;
    ToParticipant(nsparti, &xcp);
    *aCp = xcp;
  }
}

template <class Visitor>
MOZ_NEVER_INLINE void GraphWalker<Visitor>::Walk(PtrInfo* aPi) {
  nsDeque<PtrInfo> queue;
  CheckedPush(queue, aPi);
  DoWalk(queue);
}

template <class Visitor>
MOZ_NEVER_INLINE void GraphWalker<Visitor>::WalkFromRoots(CCGraph& aGraph) {
  nsDeque<PtrInfo> queue;
  NodePool::Enumerator etor(aGraph.mNodes);
  for (uint32_t i = 0; i < aGraph.mRootCount; ++i) {
    CheckedPush(queue, etor.GetNext());
  }
  DoWalk(queue);
}

template <class Visitor>
MOZ_NEVER_INLINE void GraphWalker<Visitor>::DoWalk(nsDeque<PtrInfo>& aQueue) {
  // Use a aQueue to match the breadth-first traversal used when we
  // built the graph, for hopefully-better locality.
  while (aQueue.GetSize() > 0) {
    PtrInfo* pi = aQueue.PopFront();

    if (pi->WasTraversed() && mVisitor.ShouldVisitNode(pi)) {
      mVisitor.VisitNode(pi);
      for (EdgePool::Iterator child = pi->FirstChild(),
                              child_end = pi->LastChild();
           child != child_end; ++child) {
        CheckedPush(aQueue, *child);
      }
    }
  }
}

struct CCGraphDescriber : public LinkedListElement<CCGraphDescriber> {
  CCGraphDescriber() : mAddress("0x"), mCnt(0), mType(eUnknown) {}

  enum Type {
    eRefCountedObject,
    eGCedObject,
    eGCMarkedObject,
    eEdge,
    eRoot,
    eGarbage,
    eUnknown
  };

  nsCString mAddress;
  nsCString mName;
  nsCString mCompartmentOrToAddress;
  uint32_t mCnt;
  Type mType;
};

class LogStringMessageAsync : public DiscardableRunnable {
 public:
  explicit LogStringMessageAsync(const nsAString& aMsg)
      : mozilla::DiscardableRunnable("LogStringMessageAsync"), mMsg(aMsg) {}

  NS_IMETHOD Run() override {
    nsCOMPtr<nsIConsoleService> cs =
        do_GetService(NS_CONSOLESERVICE_CONTRACTID);
    if (cs) {
      cs->LogStringMessage(mMsg.get());
    }
    return NS_OK;
  }

 private:
  nsString mMsg;
};

class nsCycleCollectorLogSinkToFile final : public nsICycleCollectorLogSink {
 public:
  NS_DECL_ISUPPORTS

  explicit nsCycleCollectorLogSinkToFile(bool aLogGC)
      : mProcessIdentifier(base::GetCurrentProcId()), mCCLog("cc-edges") {
    if (aLogGC) {
      mGCLog.emplace("gc-edges");
    }
  }

  NS_IMETHOD GetFilenameIdentifier(nsAString& aIdentifier) override {
    aIdentifier = mFilenameIdentifier;
    return NS_OK;
  }

  NS_IMETHOD SetFilenameIdentifier(const nsAString& aIdentifier) override {
    mFilenameIdentifier = aIdentifier;
    return NS_OK;
  }

  NS_IMETHOD GetProcessIdentifier(int32_t* aIdentifier) override {
    *aIdentifier = mProcessIdentifier;
    return NS_OK;
  }

  NS_IMETHOD SetProcessIdentifier(int32_t aIdentifier) override {
    mProcessIdentifier = aIdentifier;
    return NS_OK;
  }

  NS_IMETHOD GetGcLog(nsIFile** aPath) override {
    if (mGCLog.isNothing()) {
      return NS_ERROR_UNEXPECTED;
    }
    NS_IF_ADDREF(*aPath = mGCLog.ref().mFile);
    return NS_OK;
  }

  NS_IMETHOD GetCcLog(nsIFile** aPath) override {
    NS_IF_ADDREF(*aPath = mCCLog.mFile);
    return NS_OK;
  }

  NS_IMETHOD Open(FILE** aGCLog, FILE** aCCLog) override {
    nsresult rv;

    if (mCCLog.mStream) {
      return NS_ERROR_UNEXPECTED;
    }

    if (mGCLog.isSome()) {
      if (mGCLog.ref().mStream) {
        return NS_ERROR_UNEXPECTED;
      }

      rv = OpenLog(&mGCLog.ref());
      NS_ENSURE_SUCCESS(rv, rv);
      *aGCLog = mGCLog.ref().mStream;
    } else {
      *aGCLog = nullptr;
    }

    rv = OpenLog(&mCCLog);
    NS_ENSURE_SUCCESS(rv, rv);
    *aCCLog = mCCLog.mStream;

    return NS_OK;
  }

  NS_IMETHOD CloseGCLog() override {
    if (mGCLog.isNothing()) {
      return NS_OK;
    }
    if (!mGCLog.ref().mStream) {
      return NS_ERROR_UNEXPECTED;
    }
    CloseLog(&mGCLog.ref(), u"Garbage"_ns);
    return NS_OK;
  }

  NS_IMETHOD CloseCCLog() override {
    if (!mCCLog.mStream) {
      return NS_ERROR_UNEXPECTED;
    }
    CloseLog(&mCCLog, u"Cycle"_ns);
    return NS_OK;
  }

 private:
  ~nsCycleCollectorLogSinkToFile() {
    if (mGCLog.isSome() && mGCLog.ref().mStream) {
      MozillaUnRegisterDebugFILE(mGCLog.ref().mStream);
      fclose(mGCLog.ref().mStream);
    }
    if (mCCLog.mStream) {
      MozillaUnRegisterDebugFILE(mCCLog.mStream);
      fclose(mCCLog.mStream);
    }
  }

  struct FileInfo {
    const char* const mPrefix;
    nsCOMPtr<nsIFile> mFile;
    FILE* mStream;

    explicit FileInfo(const char* aPrefix)
        : mPrefix(aPrefix), mStream(nullptr) {}
  };

  /**
   * Create a new file named something like aPrefix.$PID.$IDENTIFIER.log in
   * $MOZ_CC_LOG_DIRECTORY or in the system's temp directory.  No existing
   * file will be overwritten; if aPrefix.$PID.$IDENTIFIER.log exists, we'll
   * try a file named something like aPrefix.$PID.$IDENTIFIER-1.log, and so
   * on.
   */
  already_AddRefed<nsIFile> CreateTempFile(const char* aPrefix) {
    nsPrintfCString filename("%s.%d%s%s.log", aPrefix, mProcessIdentifier,
                             mFilenameIdentifier.IsEmpty() ? "" : ".",
                             NS_ConvertUTF16toUTF8(mFilenameIdentifier).get());

    // Get the log directory either from $MOZ_CC_LOG_DIRECTORY or from
    // the fallback directories in OpenTempFile.  We don't use an nsCOMPtr
    // here because OpenTempFile uses an in/out param and getter_AddRefs
    // wouldn't work.
    nsIFile* logFile = nullptr;
    if (char* env = PR_GetEnv("MOZ_CC_LOG_DIRECTORY")) {
      Unused << NS_WARN_IF(
          NS_FAILED(NS_NewNativeLocalFile(nsCString(env), &logFile)));
    }

    // On Android or B2G, this function will open a file named
    // aFilename under a memory-reporting-specific folder
    // (/data/local/tmp/memory-reports). Otherwise, it will open a
    // file named aFilename under "NS_OS_TEMP_DIR".
    nsresult rv =
        nsDumpUtils::OpenTempFile(filename, &logFile, "memory-reports"_ns);
    if (NS_FAILED(rv)) {
      NS_IF_RELEASE(logFile);
      return nullptr;
    }

    return dont_AddRef(logFile);
  }

  nsresult OpenLog(FileInfo* aLog) {
    // Initially create the log in a file starting with "incomplete-".
    // We'll move the file and strip off the "incomplete-" once the dump
    // completes.  (We do this because we don't want scripts which poll
    // the filesystem looking for GC/CC dumps to grab a file before we're
    // finished writing to it.)
    nsAutoCString incomplete;
    incomplete += "incomplete-";
    incomplete += aLog->mPrefix;
    MOZ_ASSERT(!aLog->mFile);
    aLog->mFile = CreateTempFile(incomplete.get());
    if (NS_WARN_IF(!aLog->mFile)) {
      return NS_ERROR_UNEXPECTED;
    }

    MOZ_ASSERT(!aLog->mStream);
    nsresult rv = aLog->mFile->OpenANSIFileDesc("w", &aLog->mStream);
    if (NS_WARN_IF(NS_FAILED(rv))) {
      return NS_ERROR_UNEXPECTED;
    }
    MozillaRegisterDebugFILE(aLog->mStream);
    return NS_OK;
  }

  nsresult CloseLog(FileInfo* aLog, const nsAString& aCollectorKind) {
    MOZ_ASSERT(aLog->mStream);
    MOZ_ASSERT(aLog->mFile);

    MozillaUnRegisterDebugFILE(aLog->mStream);
    fclose(aLog->mStream);
    aLog->mStream = nullptr;

    // Strip off "incomplete-".
    nsCOMPtr<nsIFile> logFileFinalDestination = CreateTempFile(aLog->mPrefix);
    if (NS_WARN_IF(!logFileFinalDestination)) {
      return NS_ERROR_UNEXPECTED;
    }

    nsAutoString logFileFinalDestinationName;
    logFileFinalDestination->GetLeafName(logFileFinalDestinationName);
    if (NS_WARN_IF(logFileFinalDestinationName.IsEmpty())) {
      return NS_ERROR_UNEXPECTED;
    }

    if (NS_SUCCEEDED(aLog->mFile->MoveTo(/* directory */ nullptr,
                                         logFileFinalDestinationName))) {
      // Save the file path.
      aLog->mFile = logFileFinalDestination;
    }

    // Log to the error console.
    nsAutoString logPath;
    aLog->mFile->GetPath(logPath);
    nsAutoString msg =
        aCollectorKind + u" Collector log dumped to "_ns + logPath;

    // We don't want any JS to run between ScanRoots and CollectWhite calls,
    // and since ScanRoots calls this method, better to log the message
    // asynchronously.
    RefPtr<LogStringMessageAsync> log = new LogStringMessageAsync(msg);
    NS_DispatchToCurrentThread(log);
    return NS_OK;
  }

  int32_t mProcessIdentifier;
  nsString mFilenameIdentifier;
  Maybe<FileInfo> mGCLog;
  FileInfo mCCLog;
};

NS_IMPL_ISUPPORTS(nsCycleCollectorLogSinkToFile, nsICycleCollectorLogSink)

class nsCycleCollectorLogger final : public nsICycleCollectorListener {
  ~nsCycleCollectorLogger() { ClearDescribers(); }

 public:
  explicit nsCycleCollectorLogger(bool aLogGC)
      : mLogSink(nsCycleCollector_createLogSink(aLogGC)),
        mWantAllTraces(false),
        mDisableLog(false),
        mWantAfterProcessing(false),
        mCCLog(nullptr) {}

  NS_DECL_ISUPPORTS

  void SetAllTraces() { mWantAllTraces = true; }

  bool IsAllTraces() { return mWantAllTraces; }

  NS_IMETHOD AllTraces(nsICycleCollectorListener** aListener) override {
    SetAllTraces();
    NS_ADDREF(*aListener = this);
    return NS_OK;
  }

  NS_IMETHOD GetWantAllTraces(bool* aAllTraces) override {
    *aAllTraces = mWantAllTraces;
    return NS_OK;
  }

  NS_IMETHOD GetDisableLog(bool* aDisableLog) override {
    *aDisableLog = mDisableLog;
    return NS_OK;
  }

  NS_IMETHOD SetDisableLog(bool aDisableLog) override {
    mDisableLog = aDisableLog;
    return NS_OK;
  }

  NS_IMETHOD GetWantAfterProcessing(bool* aWantAfterProcessing) override {
    *aWantAfterProcessing = mWantAfterProcessing;
    return NS_OK;
  }

  NS_IMETHOD SetWantAfterProcessing(bool aWantAfterProcessing) override {
    mWantAfterProcessing = aWantAfterProcessing;
    return NS_OK;
  }

  NS_IMETHOD GetLogSink(nsICycleCollectorLogSink** aLogSink) override {
    NS_ADDREF(*aLogSink = mLogSink);
    return NS_OK;
  }

  NS_IMETHOD SetLogSink(nsICycleCollectorLogSink* aLogSink) override {
    if (!aLogSink) {
      return NS_ERROR_INVALID_ARG;
    }
    mLogSink = aLogSink;
    return NS_OK;
  }

  nsresult Begin() {
    nsresult rv;

    mCurrentAddress.AssignLiteral("0x");
    ClearDescribers();
    if (mDisableLog) {
      return NS_OK;
    }

    FILE* gcLog;
    rv = mLogSink->Open(&gcLog, &mCCLog);
    NS_ENSURE_SUCCESS(rv, rv);
    // Dump the JS heap.
    if (gcLog) {
      CollectorData* data = sCollectorData.get();
      if (data && data->mContext) {
        data->mContext->Runtime()->DumpJSHeap(gcLog);
      }
      rv = mLogSink->CloseGCLog();
      NS_ENSURE_SUCCESS(rv, rv);
    }
    fprintf(mCCLog, "# WantAllTraces=%s\n", mWantAllTraces ? "true" : "false");
    return NS_OK;
  }
  void NoteRefCountedObject(uint64_t aAddress, uint32_t aRefCount,
                            const char* aObjectDescription) {
    if (!mDisableLog) {
      fprintf(mCCLog, "%p [rc=%u] %s\n", (void*)aAddress, aRefCount,
              aObjectDescription);
    }
    if (mWantAfterProcessing) {
      CCGraphDescriber* d = new CCGraphDescriber();
      mDescribers.insertBack(d);
      mCurrentAddress.AssignLiteral("0x");
      mCurrentAddress.AppendInt(aAddress, 16);
      d->mType = CCGraphDescriber::eRefCountedObject;
      d->mAddress = mCurrentAddress;
      d->mCnt = aRefCount;
      d->mName.Append(aObjectDescription);
    }
  }
  void NoteGCedObject(uint64_t aAddress, bool aMarked,
                      const char* aObjectDescription,
                      uint64_t aCompartmentAddress) {
    if (!mDisableLog) {
      fprintf(mCCLog, "%p [gc%s] %s\n", (void*)aAddress,
              aMarked ? ".marked" : "", aObjectDescription);
    }
    if (mWantAfterProcessing) {
      CCGraphDescriber* d = new CCGraphDescriber();
      mDescribers.insertBack(d);
      mCurrentAddress.AssignLiteral("0x");
      mCurrentAddress.AppendInt(aAddress, 16);
      d->mType = aMarked ? CCGraphDescriber::eGCMarkedObject
                         : CCGraphDescriber::eGCedObject;
      d->mAddress = mCurrentAddress;
      d->mName.Append(aObjectDescription);
      if (aCompartmentAddress) {
        d->mCompartmentOrToAddress.AssignLiteral("0x");
        d->mCompartmentOrToAddress.AppendInt(aCompartmentAddress, 16);
      } else {
        d->mCompartmentOrToAddress.SetIsVoid(true);
      }
    }
  }
  void NoteEdge(uint64_t aToAddress, const char* aEdgeName) {
    if (!mDisableLog) {
      fprintf(mCCLog, "> %p %s\n", (void*)aToAddress, aEdgeName);
    }
    if (mWantAfterProcessing) {
      CCGraphDescriber* d = new CCGraphDescriber();
      mDescribers.insertBack(d);
      d->mType = CCGraphDescriber::eEdge;
      d->mAddress = mCurrentAddress;
      d->mCompartmentOrToAddress.AssignLiteral("0x");
      d->mCompartmentOrToAddress.AppendInt(aToAddress, 16);
      d->mName.Append(aEdgeName);
    }
  }
  void NoteWeakMapEntry(uint64_t aMap, uint64_t aKey, uint64_t aKeyDelegate,
                        uint64_t aValue) {
    if (!mDisableLog) {
      fprintf(mCCLog, "WeakMapEntry map=%p key=%p keyDelegate=%p value=%p\n",
              (void*)aMap, (void*)aKey, (void*)aKeyDelegate, (void*)aValue);
    }
    // We don't support after-processing for weak map entries.
  }
  void NoteIncrementalRoot(uint64_t aAddress) {
    if (!mDisableLog) {
      fprintf(mCCLog, "IncrementalRoot %p\n", (void*)aAddress);
    }
    // We don't support after-processing for incremental roots.
  }
  void BeginResults() {
    if (!mDisableLog) {
      fputs("==========\n", mCCLog);
    }
  }
  void DescribeRoot(uint64_t aAddress, uint32_t aKnownEdges) {
    if (!mDisableLog) {
      fprintf(mCCLog, "%p [known=%u]\n", (void*)aAddress, aKnownEdges);
    }
    if (mWantAfterProcessing) {
      CCGraphDescriber* d = new CCGraphDescriber();
      mDescribers.insertBack(d);
      d->mType = CCGraphDescriber::eRoot;
      d->mAddress.AppendInt(aAddress, 16);
      d->mCnt = aKnownEdges;
    }
  }
  void DescribeGarbage(uint64_t aAddress) {
    if (!mDisableLog) {
      fprintf(mCCLog, "%p [garbage]\n", (void*)aAddress);
    }
    if (mWantAfterProcessing) {
      CCGraphDescriber* d = new CCGraphDescriber();
      mDescribers.insertBack(d);
      d->mType = CCGraphDescriber::eGarbage;
      d->mAddress.AppendInt(aAddress, 16);
    }
  }
  void End() {
    if (!mDisableLog) {
      mCCLog = nullptr;
      Unused << NS_WARN_IF(NS_FAILED(mLogSink->CloseCCLog()));
    }
  }
  NS_IMETHOD ProcessNext(nsICycleCollectorHandler* aHandler,
                         bool* aCanContinue) override {
    if (NS_WARN_IF(!aHandler) || NS_WARN_IF(!mWantAfterProcessing)) {
      return NS_ERROR_UNEXPECTED;
    }
    CCGraphDescriber* d = mDescribers.popFirst();
    if (d) {
      switch (d->mType) {
        case CCGraphDescriber::eRefCountedObject:
          aHandler->NoteRefCountedObject(d->mAddress, d->mCnt, d->mName);
          break;
        case CCGraphDescriber::eGCedObject:
        case CCGraphDescriber::eGCMarkedObject:
          aHandler->NoteGCedObject(
              d->mAddress, d->mType == CCGraphDescriber::eGCMarkedObject,
              d->mName, d->mCompartmentOrToAddress);
          break;
        case CCGraphDescriber::eEdge:
          aHandler->NoteEdge(d->mAddress, d->mCompartmentOrToAddress, d->mName);
          break;
        case CCGraphDescriber::eRoot:
          aHandler->DescribeRoot(d->mAddress, d->mCnt);
          break;
        case CCGraphDescriber::eGarbage:
          aHandler->DescribeGarbage(d->mAddress);
          break;
        case CCGraphDescriber::eUnknown:
          MOZ_ASSERT_UNREACHABLE("CCGraphDescriber::eUnknown");
          break;
      }
      delete d;
    }
    if (!(*aCanContinue = !mDescribers.isEmpty())) {
      mCurrentAddress.AssignLiteral("0x");
    }
    return NS_OK;
  }
  NS_IMETHOD AsLogger(nsCycleCollectorLogger** aRetVal) override {
    RefPtr<nsCycleCollectorLogger> rval = this;
    rval.forget(aRetVal);
    return NS_OK;
  }

 private:
  void ClearDescribers() {
    CCGraphDescriber* d;
    while ((d = mDescribers.popFirst())) {
      delete d;
    }
  }

  nsCOMPtr<nsICycleCollectorLogSink> mLogSink;
  bool mWantAllTraces;
  bool mDisableLog;
  bool mWantAfterProcessing;
  nsCString mCurrentAddress;
  mozilla::LinkedList<CCGraphDescriber> mDescribers;
  FILE* mCCLog;
};

NS_IMPL_ISUPPORTS(nsCycleCollectorLogger, nsICycleCollectorListener)

already_AddRefed<nsICycleCollectorListener> nsCycleCollector_createLogger() {
  nsCOMPtr<nsICycleCollectorListener> logger =
      new nsCycleCollectorLogger(/* aLogGC = */ true);
  return logger.forget();
}

static bool GCThingIsGrayCCThing(JS::GCCellPtr thing) {
  return JS::IsCCTraceKind(thing.kind()) && JS::GCThingIsMarkedGrayInCC(thing);
}

static bool ValueIsGrayCCThing(const JS::Value& value) {
  return JS::IsCCTraceKind(value.traceKind()) &&
         JS::GCThingIsMarkedGray(value.toGCCellPtr());
}

////////////////////////////////////////////////////////////////////////
// Bacon & Rajan's |MarkRoots| routine.
////////////////////////////////////////////////////////////////////////

class CCGraphBuilder final : public nsCycleCollectionTraversalCallback,
                             public nsCycleCollectionNoteRootCallback {
 private:
  CCGraph& mGraph;
  CycleCollectorResults& mResults;
  NodePool::Builder mNodeBuilder;
  EdgePool::Builder mEdgeBuilder;
  MOZ_INIT_OUTSIDE_CTOR PtrInfo* mCurrPi;
  nsCycleCollectionParticipant* mJSParticipant;
  nsCycleCollectionParticipant* mJSZoneParticipant;
  nsCString mNextEdgeName;
  RefPtr<nsCycleCollectorLogger> mLogger;
  bool mMergeZones;
  UniquePtr<NodePool::Enumerator> mCurrNode;
  uint32_t mNoteChildCount;

  struct PtrInfoCache : public MruCache<void*, PtrInfo*, PtrInfoCache, 491> {
    static HashNumber Hash(const void* aKey) { return HashGeneric(aKey); }
    static bool Match(const void* aKey, const PtrInfo* aVal) {
      return aVal->mPointer == aKey;
    }
  };

  PtrInfoCache mGraphCache;

 public:
  CCGraphBuilder(CCGraph& aGraph, CycleCollectorResults& aResults,
                 CycleCollectedJSRuntime* aCCRuntime,
                 nsCycleCollectorLogger* aLogger, bool aMergeZones);
  virtual ~CCGraphBuilder();

  bool WantAllTraces() const {
    return nsCycleCollectionNoteRootCallback::WantAllTraces();
  }

  bool AddPurpleRoot(void* aRoot, nsCycleCollectionParticipant* aParti);

  // This is called when all roots have been added to the graph, to prepare for
  // BuildGraph().
  void DoneAddingRoots();

  // Do some work traversing nodes in the graph. Returns true if this graph
  // building is finished.
  bool BuildGraph(SliceBudget& aBudget);

  void RemoveCachedEntry(void* aPtr) { mGraphCache.Remove(aPtr); }

 private:
  PtrInfo* AddNode(void* aPtr, nsCycleCollectionParticipant* aParticipant);
  PtrInfo* AddWeakMapNode(JS::GCCellPtr aThing);
  PtrInfo* AddWeakMapNode(JSObject* aObject);

--> --------------------

--> maximum size reached

--> --------------------