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

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

quality97%

¤ Dauer der Verarbeitung: 0.70 Sekunden (vorverarbeitet) ¤

vorgegebene Sprache:

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.