/* -*- 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. Snow-white object

// 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/DebugOnly.h"

#include "mozilla/HashFunctions.h"

#include "mozilla/HashTable.h"

#include "mozilla/HoldDropJSObjects.h"

/* This must occur *after* base/process_util.h to avoid typedefs conflicts. */

#include "mozilla/LinkedList.h"

#include "mozilla/MemoryReporting.h"

#include "mozilla/Move.h"

#include "mozilla/MruCache.h"

#include "mozilla/SegmentedVector.h"

#include "nsCycleCollectionParticipant.h"

#include "nsCycleCollectionNoteRootCallback.h"

#include "nsDeque.h"

#include "nsExceptionHandler.h"

#include "nsCycleCollector.h"

#include "nsThreadUtils.h"

#include "nsXULAppAPI.h"

#include "prenv.h"

#include "nsPrintfCString.h"

#include "nsTArray.h"

#include "nsIConsoleService.h"

#include "mozilla/Attributes.h"

#include "nsICycleCollectorListener.h"

#include "nsISerialEventTarget.h"

#include "nsIMemoryReporter.h"

#include "nsIFile.h"

#include "nsDumpUtils.h"

#include "xpcpublic.h"

#include "GeckoProfiler.h"

#include <stdint.h>

#include <stdio.h>

#include "mozilla/AutoGlobalTimelineMarker.h"

#include "mozilla/Likely.h"

#include "mozilla/PoisonIOInterposer.h"

#include "mozilla/Telemetry.h"

#include "mozilla/ThreadLocal.h"

using namespace mozilla;

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();

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_LOG_ALL: If defined, always log cycle collector heaps.

//

// MOZ_CC_LOG_SHUTDOWN: If defined, log cycle collector heaps at shutdown.

//

// 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

// "plugins", only automatically log plugin 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_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-DEBUG or builds, if this is set,

// run cycle collections at shutdown.

//

// 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)

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

// variables.

struct nsCycleCollectorParams

{

  bool mLogAll;

  bool mLogShutdown;

  bool mAllTracesAll;

  bool mAllTracesShutdown;

  bool mLogThisThread;

  nsCycleCollectorParams() :

    mLogAll(PR_GetEnv("MOZ_CC_LOG_ALL") != nullptr),

    mLogShutdown(PR_GetEnv("MOZ_CC_LOG_SHUTDOWN") != nullptr),

    mAllTracesAll(false),

    mAllTracesShutdown(false)

  {

    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_Plugin:

          processLogging = !strcmp(logProcessEnv, "plugins");

          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;

      }

    }

  }

  bool LogThisCC(bool aIsShutdown)

  {

    return (mLogAll || (aIsShutdown && mLogShutdown)) && mLogThisThread;

  }

  bool AllTracesThisCC(bool aIsShutdown)

  {

    return mAllTracesAll || (aIsShutdown && mAllTracesShutdown);

  }

};

#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()

  {

  }

  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) : mPointer(aOther.mPointer) {}

    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

#define CC_TELEMETRY(_name, _value)                                            \

    do {                                                                       \

    if (NS_IsMainThread()) {                                                   \

      Telemetry::Accumulate(Telemetry::CYCLE_COLLECTOR##_name, _value);        \

    } else {                                                                   \

      Telemetry::Accumulate(Telemetry::CYCLE_COLLECTOR_WORKER##_name, _value); \

    }                                                                          \

    } while(0)

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:

  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),

      mFirstChild()

  {

    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);

  CrashReporter::AnnotateCrashReport(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() {}

  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) {