The Tor Browser / file revision

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-

  * vim: set ts=8 sts=4 et sw=4 tw=99:

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

 /* JS Garbage Collector. */

 #ifndef jsgc_h

 #define jsgc_h

 #include "mozilla/DebugOnly.h"

 #include "mozilla/MemoryReporting.h"

 #include "jslock.h"

 #include "jsobj.h"

 #include "js/GCAPI.h"

 #include "js/SliceBudget.h"

 #include "js/Vector.h"

 class JSAtom;

 struct JSCompartment;

 class JSFlatString;

 class JSLinearString;

 namespace js {

 class ArgumentsObject;

 class ArrayBufferObject;

 class ArrayBufferViewObject;

 class SharedArrayBufferObject;

 class BaseShape;

 class DebugScopeObject;

 class GCHelperThread;

 class GlobalObject;

 class LazyScript;

 class Nursery;

 class PropertyName;

 class ScopeObject;

 class Shape;

 class UnownedBaseShape;

 unsigned GetCPUCount();

 enum HeapState {

     Idle,             // doing nothing with the GC heap

     Tracing,          // tracing the GC heap without collecting, e.g. IterateCompartments()

     MajorCollecting,  // doing a GC of the major heap

     MinorCollecting   // doing a GC of the minor heap (nursery)

 };

 namespace jit {

     class JitCode;

 }

 namespace gc {

 enum State {

     NO_INCREMENTAL,

     MARK_ROOTS,

     MARK,

     SWEEP,

     INVALID

 };

 class ChunkPool {

     Chunk   *emptyChunkListHead;

     size_t  emptyCount;

   public:

     ChunkPool()

       : emptyChunkListHead(nullptr),

         emptyCount(0) { }

     size_t getEmptyCount() const {

         return emptyCount;

     }

     inline bool wantBackgroundAllocation(JSRuntime *rt) const;

     /* Must be called with the GC lock taken. */

     inline Chunk *get(JSRuntime *rt);

     /* Must be called either during the GC or with the GC lock taken. */

     inline void put(Chunk *chunk);

     /*

      * Return the list of chunks that can be released outside the GC lock.

      * Must be called either during the GC or with the GC lock taken.

      */

     Chunk *expire(JSRuntime *rt, bool releaseAll);

     /* Must be called with the GC lock taken. */

     void expireAndFree(JSRuntime *rt, bool releaseAll);

 };

 static inline JSGCTraceKind

 MapAllocToTraceKind(AllocKind kind)

 {

     static const JSGCTraceKind map[] = {

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT0 */

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT0_BACKGROUND */

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT2 */

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT2_BACKGROUND */

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT4 */

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT4_BACKGROUND */

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT8 */

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT8_BACKGROUND */

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT12 */

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT12_BACKGROUND */

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT16 */

         JSTRACE_OBJECT,     /* FINALIZE_OBJECT16_BACKGROUND */

         JSTRACE_SCRIPT,     /* FINALIZE_SCRIPT */

         JSTRACE_LAZY_SCRIPT,/* FINALIZE_LAZY_SCRIPT */

         JSTRACE_SHAPE,      /* FINALIZE_SHAPE */

         JSTRACE_BASE_SHAPE, /* FINALIZE_BASE_SHAPE */

         JSTRACE_TYPE_OBJECT,/* FINALIZE_TYPE_OBJECT */

         JSTRACE_STRING,     /* FINALIZE_FAT_INLINE_STRING */

         JSTRACE_STRING,     /* FINALIZE_STRING */

         JSTRACE_STRING,     /* FINALIZE_EXTERNAL_STRING */

         JSTRACE_JITCODE,    /* FINALIZE_JITCODE */

     };

     JS_STATIC_ASSERT(JS_ARRAY_LENGTH(map) == FINALIZE_LIMIT);

     return map[kind];

 }

 template <typename T> struct MapTypeToTraceKind {};

 template <> struct MapTypeToTraceKind<ObjectImpl>       { static const JSGCTraceKind kind = JSTRACE_OBJECT; };

 template <> struct MapTypeToTraceKind<JSObject>         { static const JSGCTraceKind kind = JSTRACE_OBJECT; };

 template <> struct MapTypeToTraceKind<JSFunction>       { static const JSGCTraceKind kind = JSTRACE_OBJECT; };

 template <> struct MapTypeToTraceKind<ArgumentsObject>  { static const JSGCTraceKind kind = JSTRACE_OBJECT; };

 template <> struct MapTypeToTraceKind<ArrayBufferObject>{ static const JSGCTraceKind kind = JSTRACE_OBJECT; };

 template <> struct MapTypeToTraceKind<ArrayBufferViewObject>{ static const JSGCTraceKind kind = JSTRACE_OBJECT; };

 template <> struct MapTypeToTraceKind<SharedArrayBufferObject>{ static const JSGCTraceKind kind = JSTRACE_OBJECT; };

 template <> struct MapTypeToTraceKind<DebugScopeObject> { static const JSGCTraceKind kind = JSTRACE_OBJECT; };

 template <> struct MapTypeToTraceKind<GlobalObject>     { static const JSGCTraceKind kind = JSTRACE_OBJECT; };

 template <> struct MapTypeToTraceKind<ScopeObject>      { static const JSGCTraceKind kind = JSTRACE_OBJECT; };

 template <> struct MapTypeToTraceKind<JSScript>         { static const JSGCTraceKind kind = JSTRACE_SCRIPT; };

 template <> struct MapTypeToTraceKind<LazyScript>       { static const JSGCTraceKind kind = JSTRACE_LAZY_SCRIPT; };

 template <> struct MapTypeToTraceKind<Shape>            { static const JSGCTraceKind kind = JSTRACE_SHAPE; };

 template <> struct MapTypeToTraceKind<BaseShape>        { static const JSGCTraceKind kind = JSTRACE_BASE_SHAPE; };

 template <> struct MapTypeToTraceKind<UnownedBaseShape> { static const JSGCTraceKind kind = JSTRACE_BASE_SHAPE; };

 template <> struct MapTypeToTraceKind<types::TypeObject>{ static const JSGCTraceKind kind = JSTRACE_TYPE_OBJECT; };

 template <> struct MapTypeToTraceKind<JSAtom>           { static const JSGCTraceKind kind = JSTRACE_STRING; };

 template <> struct MapTypeToTraceKind<JSString>         { static const JSGCTraceKind kind = JSTRACE_STRING; };

 template <> struct MapTypeToTraceKind<JSFlatString>     { static const JSGCTraceKind kind = JSTRACE_STRING; };

 template <> struct MapTypeToTraceKind<JSLinearString>   { static const JSGCTraceKind kind = JSTRACE_STRING; };

 template <> struct MapTypeToTraceKind<PropertyName>     { static const JSGCTraceKind kind = JSTRACE_STRING; };

 template <> struct MapTypeToTraceKind<jit::JitCode>     { static const JSGCTraceKind kind = JSTRACE_JITCODE; };

 /* Map from C++ type to finalize kind. JSObject does not have a 1:1 mapping, so must use Arena::thingSize. */

 template <typename T> struct MapTypeToFinalizeKind {};

 template <> struct MapTypeToFinalizeKind<JSScript>          { static const AllocKind kind = FINALIZE_SCRIPT; };

 template <> struct MapTypeToFinalizeKind<LazyScript>        { static const AllocKind kind = FINALIZE_LAZY_SCRIPT; };

 template <> struct MapTypeToFinalizeKind<Shape>             { static const AllocKind kind = FINALIZE_SHAPE; };

 template <> struct MapTypeToFinalizeKind<BaseShape>         { static const AllocKind kind = FINALIZE_BASE_SHAPE; };

 template <> struct MapTypeToFinalizeKind<types::TypeObject> { static const AllocKind kind = FINALIZE_TYPE_OBJECT; };

 template <> struct MapTypeToFinalizeKind<JSFatInlineString> { static const AllocKind kind = FINALIZE_FAT_INLINE_STRING; };

 template <> struct MapTypeToFinalizeKind<JSString>          { static const AllocKind kind = FINALIZE_STRING; };

 template <> struct MapTypeToFinalizeKind<JSExternalString>  { static const AllocKind kind = FINALIZE_EXTERNAL_STRING; };

 template <> struct MapTypeToFinalizeKind<jit::JitCode>      { static const AllocKind kind = FINALIZE_JITCODE; };

 #if defined(JSGC_GENERATIONAL) || defined(DEBUG)

 static inline bool

 IsNurseryAllocable(AllocKind kind)

 {

     JS_ASSERT(kind >= 0 && unsigned(kind) < FINALIZE_LIMIT);

     static const bool map[] = {

         false,     /* FINALIZE_OBJECT0 */

         true,      /* FINALIZE_OBJECT0_BACKGROUND */

         false,     /* FINALIZE_OBJECT2 */

         true,      /* FINALIZE_OBJECT2_BACKGROUND */

         false,     /* FINALIZE_OBJECT4 */

         true,      /* FINALIZE_OBJECT4_BACKGROUND */

         false,     /* FINALIZE_OBJECT8 */

         true,      /* FINALIZE_OBJECT8_BACKGROUND */

         false,     /* FINALIZE_OBJECT12 */

         true,      /* FINALIZE_OBJECT12_BACKGROUND */

         false,     /* FINALIZE_OBJECT16 */

         true,      /* FINALIZE_OBJECT16_BACKGROUND */

         false,     /* FINALIZE_SCRIPT */

         false,     /* FINALIZE_LAZY_SCRIPT */

         false,     /* FINALIZE_SHAPE */

         false,     /* FINALIZE_BASE_SHAPE */

         false,     /* FINALIZE_TYPE_OBJECT */

         false,     /* FINALIZE_FAT_INLINE_STRING */

         false,     /* FINALIZE_STRING */

         false,     /* FINALIZE_EXTERNAL_STRING */

         false,     /* FINALIZE_JITCODE */

     };

     JS_STATIC_ASSERT(JS_ARRAY_LENGTH(map) == FINALIZE_LIMIT);

     return map[kind];

 }

 #endif

 static inline bool

 IsBackgroundFinalized(AllocKind kind)

 {

     JS_ASSERT(kind >= 0 && unsigned(kind) < FINALIZE_LIMIT);

     static const bool map[] = {

         false,     /* FINALIZE_OBJECT0 */

         true,      /* FINALIZE_OBJECT0_BACKGROUND */

         false,     /* FINALIZE_OBJECT2 */

         true,      /* FINALIZE_OBJECT2_BACKGROUND */

         false,     /* FINALIZE_OBJECT4 */

         true,      /* FINALIZE_OBJECT4_BACKGROUND */

         false,     /* FINALIZE_OBJECT8 */

         true,      /* FINALIZE_OBJECT8_BACKGROUND */

         false,     /* FINALIZE_OBJECT12 */

         true,      /* FINALIZE_OBJECT12_BACKGROUND */

         false,     /* FINALIZE_OBJECT16 */

         true,      /* FINALIZE_OBJECT16_BACKGROUND */

         false,     /* FINALIZE_SCRIPT */

         false,     /* FINALIZE_LAZY_SCRIPT */

         true,      /* FINALIZE_SHAPE */

         true,      /* FINALIZE_BASE_SHAPE */

         true,      /* FINALIZE_TYPE_OBJECT */

         true,      /* FINALIZE_FAT_INLINE_STRING */

         true,      /* FINALIZE_STRING */

         false,     /* FINALIZE_EXTERNAL_STRING */

         false,     /* FINALIZE_JITCODE */

     };

     JS_STATIC_ASSERT(JS_ARRAY_LENGTH(map) == FINALIZE_LIMIT);

     return map[kind];

 }

 static inline bool

 CanBeFinalizedInBackground(gc::AllocKind kind, const Class *clasp)

 {

     JS_ASSERT(kind <= gc::FINALIZE_OBJECT_LAST);

     /* If the class has no finalizer or a finalizer that is safe to call on

      * a different thread, we change the finalize kind. For example,

      * FINALIZE_OBJECT0 calls the finalizer on the main thread,

      * FINALIZE_OBJECT0_BACKGROUND calls the finalizer on the gcHelperThread.

      * IsBackgroundFinalized is called to prevent recursively incrementing

      * the finalize kind; kind may already be a background finalize kind.

      */

     return (!gc::IsBackgroundFinalized(kind) &&

             (!clasp->finalize || (clasp->flags & JSCLASS_BACKGROUND_FINALIZE)));

 }

 inline JSGCTraceKind

 GetGCThingTraceKind(const void *thing);

 /* Capacity for slotsToThingKind */

 const size_t SLOTS_TO_THING_KIND_LIMIT = 17;

 extern const AllocKind slotsToThingKind[];

 /* Get the best kind to use when making an object with the given slot count. */

 static inline AllocKind

 GetGCObjectKind(size_t numSlots)

 {

     if (numSlots >= SLOTS_TO_THING_KIND_LIMIT)

         return FINALIZE_OBJECT16;

     return slotsToThingKind[numSlots];

 }

 /* As for GetGCObjectKind, but for dense array allocation. */

 static inline AllocKind

 GetGCArrayKind(size_t numSlots)

 {

     /*

      * Dense arrays can use their fixed slots to hold their elements array

      * (less two Values worth of ObjectElements header), but if more than the

      * maximum number of fixed slots is needed then the fixed slots will be

      * unused.

      */

     JS_STATIC_ASSERT(ObjectElements::VALUES_PER_HEADER == 2);

     if (numSlots > JSObject::NELEMENTS_LIMIT || numSlots + 2 >= SLOTS_TO_THING_KIND_LIMIT)

         return FINALIZE_OBJECT2;

     return slotsToThingKind[numSlots + 2];

 }

 static inline AllocKind

 GetGCObjectFixedSlotsKind(size_t numFixedSlots)

 {

     JS_ASSERT(numFixedSlots < SLOTS_TO_THING_KIND_LIMIT);

     return slotsToThingKind[numFixedSlots];

 }

 static inline AllocKind

 GetBackgroundAllocKind(AllocKind kind)

 {

     JS_ASSERT(!IsBackgroundFinalized(kind));

     JS_ASSERT(kind <= FINALIZE_OBJECT_LAST);

     return (AllocKind) (kind + 1);

 }

 /*

  * Try to get the next larger size for an object, keeping BACKGROUND

  * consistent.

  */

 static inline bool

 TryIncrementAllocKind(AllocKind *kindp)

 {

     size_t next = size_t(*kindp) + 2;

     if (next >= size_t(FINALIZE_OBJECT_LIMIT))

         return false;

     *kindp = AllocKind(next);

     return true;

 }

 /* Get the number of fixed slots and initial capacity associated with a kind. */

 static inline size_t

 GetGCKindSlots(AllocKind thingKind)

 {

     /* Using a switch in hopes that thingKind will usually be a compile-time constant. */

     switch (thingKind) {

       case FINALIZE_OBJECT0:

       case FINALIZE_OBJECT0_BACKGROUND:

         return 0;

       case FINALIZE_OBJECT2:

       case FINALIZE_OBJECT2_BACKGROUND:

         return 2;

       case FINALIZE_OBJECT4:

       case FINALIZE_OBJECT4_BACKGROUND:

         return 4;

       case FINALIZE_OBJECT8:

       case FINALIZE_OBJECT8_BACKGROUND:

         return 8;

       case FINALIZE_OBJECT12:

       case FINALIZE_OBJECT12_BACKGROUND:

         return 12;

       case FINALIZE_OBJECT16:

       case FINALIZE_OBJECT16_BACKGROUND:

         return 16;

       default:

         MOZ_ASSUME_UNREACHABLE("Bad object finalize kind");

     }

 }

 static inline size_t

 GetGCKindSlots(AllocKind thingKind, const Class *clasp)

 {

     size_t nslots = GetGCKindSlots(thingKind);

     /* An object's private data uses the space taken by its last fixed slot. */

     if (clasp->flags & JSCLASS_HAS_PRIVATE) {

         JS_ASSERT(nslots > 0);

         nslots--;

     }

     /*

      * Functions have a larger finalize kind than FINALIZE_OBJECT to reserve

      * space for the extra fields in JSFunction, but have no fixed slots.

      */

     if (clasp == FunctionClassPtr)

         nslots = 0;

     return nslots;

 }

 /*

  * ArenaList::head points to the start of the list. Normally cursor points

  * to the first arena in the list with some free things and all arenas

  * before cursor are fully allocated. However, as the arena currently being

  * allocated from is considered full while its list of free spans is moved

  * into the freeList, during the GC or cell enumeration, when an

  * unallocated freeList is moved back to the arena, we can see an arena

  * with some free cells before the cursor. The cursor is an indirect

  * pointer to allow for efficient list insertion at the cursor point and

  * other list manipulations.

  */

 struct ArenaList {

     ArenaHeader     *head;

     ArenaHeader     **cursor;

     ArenaList() {

         clear();

     }

     void clear() {

         head = nullptr;

         cursor = &head;

     }

     void insert(ArenaHeader *arena);

 };

 class ArenaLists

 {

     /*

      * For each arena kind its free list is represented as the first span with

      * free things. Initially all the spans are initialized as empty. After we

      * find a new arena with available things we move its first free span into

      * the list and set the arena as fully allocated. way we do not need to

      * update the arena header after the initial allocation. When starting the

      * GC we only move the head of the of the list of spans back to the arena

      * only for the arena that was not fully allocated.

      */

     FreeSpan       freeLists[FINALIZE_LIMIT];

     ArenaList      arenaLists[FINALIZE_LIMIT];

     /*

      * The background finalization adds the finalized arenas to the list at

      * the *cursor position. backgroundFinalizeState controls the interaction

      * between the GC lock and the access to the list from the allocation

      * thread.

      *

      * BFS_DONE indicates that the finalizations is not running or cannot

      * affect this arena list. The allocation thread can access the list

      * outside the GC lock.

      *

      * In BFS_RUN and BFS_JUST_FINISHED the allocation thread must take the

      * lock. The former indicates that the finalization still runs. The latter

      * signals that finalization just added to the list finalized arenas. In

      * that case the lock effectively serves as a read barrier to ensure that

      * the allocation thread see all the writes done during finalization.

      */

     enum BackgroundFinalizeState {

         BFS_DONE,

         BFS_RUN,

         BFS_JUST_FINISHED

     };

     volatile uintptr_t backgroundFinalizeState[FINALIZE_LIMIT];

   public:

     /* For each arena kind, a list of arenas remaining to be swept. */

     ArenaHeader *arenaListsToSweep[FINALIZE_LIMIT];

     /* Shape arenas to be swept in the foreground. */

     ArenaHeader *gcShapeArenasToSweep;

   public:

     ArenaLists() {

         for (size_t i = 0; i != FINALIZE_LIMIT; ++i)

             freeLists[i].initAsEmpty();

         for (size_t i = 0; i != FINALIZE_LIMIT; ++i)

             backgroundFinalizeState[i] = BFS_DONE;

         for (size_t i = 0; i != FINALIZE_LIMIT; ++i)

             arenaListsToSweep[i] = nullptr;

         gcShapeArenasToSweep = nullptr;

     }

     ~ArenaLists() {

         for (size_t i = 0; i != FINALIZE_LIMIT; ++i) {

             /*

              * We can only call this during the shutdown after the last GC when

              * the background finalization is disabled.

              */

             JS_ASSERT(backgroundFinalizeState[i] == BFS_DONE);

             ArenaHeader **headp = &arenaLists[i].head;

             while (ArenaHeader *aheader = *headp) {

                 *headp = aheader->next;

                 aheader->chunk()->releaseArena(aheader);

             }

         }

     }

     static uintptr_t getFreeListOffset(AllocKind thingKind) {

         uintptr_t offset = offsetof(ArenaLists, freeLists);

         return offset + thingKind * sizeof(FreeSpan);

     }

     const FreeSpan *getFreeList(AllocKind thingKind) const {

         return &freeLists[thingKind];

     }

     ArenaHeader *getFirstArena(AllocKind thingKind) const {

         return arenaLists[thingKind].head;

     }

     ArenaHeader *getFirstArenaToSweep(AllocKind thingKind) const {

         return arenaListsToSweep[thingKind];

     }

     bool arenaListsAreEmpty() const {

         for (size_t i = 0; i != FINALIZE_LIMIT; ++i) {

             /*

              * The arena cannot be empty if the background finalization is not yet

              * done.

              */

             if (backgroundFinalizeState[i] != BFS_DONE)

                 return false;

             if (arenaLists[i].head)

                 return false;

         }

         return true;

     }

     bool arenasAreFull(AllocKind thingKind) const {

         return !*arenaLists[thingKind].cursor;

     }

     void unmarkAll() {

         for (size_t i = 0; i != FINALIZE_LIMIT; ++i) {

             /* The background finalization must have stopped at this point. */

             JS_ASSERT(backgroundFinalizeState[i] == BFS_DONE ||

                       backgroundFinalizeState[i] == BFS_JUST_FINISHED);

             for (ArenaHeader *aheader = arenaLists[i].head; aheader; aheader = aheader->next) {

                 uintptr_t *word = aheader->chunk()->bitmap.arenaBits(aheader);

                 memset(word, 0, ArenaBitmapWords * sizeof(uintptr_t));

             }

         }

     }

     bool doneBackgroundFinalize(AllocKind kind) const {

         return backgroundFinalizeState[kind] == BFS_DONE ||

                backgroundFinalizeState[kind] == BFS_JUST_FINISHED;

     }

     bool needBackgroundFinalizeWait(AllocKind kind) const {

         return backgroundFinalizeState[kind] != BFS_DONE;

     }

     /*

      * Return the free list back to the arena so the GC finalization will not

      * run the finalizers over unitialized bytes from free things.

      */

     void purge() {

         for (size_t i = 0; i != FINALIZE_LIMIT; ++i)

             purge(AllocKind(i));

     }

     void purge(AllocKind i) {

         FreeSpan *headSpan = &freeLists[i];

         if (!headSpan->isEmpty()) {

             ArenaHeader *aheader = headSpan->arenaHeader();

             aheader->setFirstFreeSpan(headSpan);

             headSpan->initAsEmpty();

         }

     }

     inline void prepareForIncrementalGC(JSRuntime *rt);

     /*

      * Temporarily copy the free list heads to the arenas so the code can see

      * the proper value in ArenaHeader::freeList when accessing the latter

      * outside the GC.

      */

     void copyFreeListsToArenas() {

         for (size_t i = 0; i != FINALIZE_LIMIT; ++i)

             copyFreeListToArena(AllocKind(i));

     }

     void copyFreeListToArena(AllocKind thingKind) {

         FreeSpan *headSpan = &freeLists[thingKind];

         if (!headSpan->isEmpty()) {

             ArenaHeader *aheader = headSpan->arenaHeader();

             JS_ASSERT(!aheader->hasFreeThings());

             aheader->setFirstFreeSpan(headSpan);

         }

     }

     /*

      * Clear the free lists in arenas that were temporarily set there using

      * copyToArenas.

      */

     void clearFreeListsInArenas() {

         for (size_t i = 0; i != FINALIZE_LIMIT; ++i)

             clearFreeListInArena(AllocKind(i));

     }

     void clearFreeListInArena(AllocKind kind) {

         FreeSpan *headSpan = &freeLists[kind];

         if (!headSpan->isEmpty()) {

             ArenaHeader *aheader = headSpan->arenaHeader();

             JS_ASSERT(aheader->getFirstFreeSpan().isSameNonEmptySpan(headSpan));

             aheader->setAsFullyUsed();

         }

     }

     /*

      * Check that the free list is either empty or were synchronized with the

      * arena using copyToArena().

      */

     bool isSynchronizedFreeList(AllocKind kind) {

         FreeSpan *headSpan = &freeLists[kind];

         if (headSpan->isEmpty())

             return true;

         ArenaHeader *aheader = headSpan->arenaHeader();

         if (aheader->hasFreeThings()) {

             /*

              * If the arena has a free list, it must be the same as one in

              * lists.

              */

             JS_ASSERT(aheader->getFirstFreeSpan().isSameNonEmptySpan(headSpan));

             return true;

         }

         return false;

     }

     MOZ_ALWAYS_INLINE void *allocateFromFreeList(AllocKind thingKind, size_t thingSize) {

         return freeLists[thingKind].allocate(thingSize);

     }

     template <AllowGC allowGC>

     static void *refillFreeList(ThreadSafeContext *cx, AllocKind thingKind);

     /*

      * Moves all arenas from |fromArenaLists| into |this|.  In

      * parallel blocks, we temporarily create one ArenaLists per

      * parallel thread.  When the parallel block ends, we move

      * whatever allocations may have been performed back into the

      * compartment's main arena list using this function.

      */

     void adoptArenas(JSRuntime *runtime, ArenaLists *fromArenaLists);

     /* True if the ArenaHeader in question is found in this ArenaLists */

     bool containsArena(JSRuntime *runtime, ArenaHeader *arenaHeader);

     void checkEmptyFreeLists() {

 #ifdef DEBUG

         for (size_t i = 0; i < mozilla::ArrayLength(freeLists); ++i)

             JS_ASSERT(freeLists[i].isEmpty());

 #endif

     }

     void checkEmptyFreeList(AllocKind kind) {

         JS_ASSERT(freeLists[kind].isEmpty());

     }

     void queueObjectsForSweep(FreeOp *fop);

     void queueStringsForSweep(FreeOp *fop);

     void queueShapesForSweep(FreeOp *fop);

     void queueScriptsForSweep(FreeOp *fop);

     void queueJitCodeForSweep(FreeOp *fop);

     bool foregroundFinalize(FreeOp *fop, AllocKind thingKind, SliceBudget &sliceBudget);

     static void backgroundFinalize(FreeOp *fop, ArenaHeader *listHead, bool onBackgroundThread);

     void wipeDuringParallelExecution(JSRuntime *rt);

   private:

     inline void finalizeNow(FreeOp *fop, AllocKind thingKind);

     inline void forceFinalizeNow(FreeOp *fop, AllocKind thingKind);

     inline void queueForForegroundSweep(FreeOp *fop, AllocKind thingKind);

     inline void queueForBackgroundSweep(FreeOp *fop, AllocKind thingKind);

     void *allocateFromArena(JS::Zone *zone, AllocKind thingKind);

     inline void *allocateFromArenaInline(JS::Zone *zone, AllocKind thingKind);

     inline void normalizeBackgroundFinalizeState(AllocKind thingKind);

     friend class js::Nursery;

 };

 /*

  * Initial allocation size for data structures holding chunks is set to hold

  * chunks with total capacity of 16MB to avoid buffer resizes during browser

  * startup.

  */

 const size_t INITIAL_CHUNK_CAPACITY = 16 * 1024 * 1024 / ChunkSize;

 /* The number of GC cycles an empty chunk can survive before been released. */

 const size_t MAX_EMPTY_CHUNK_AGE = 4;

 } /* namespace gc */

 typedef enum JSGCRootType {

     JS_GC_ROOT_VALUE_PTR,

     JS_GC_ROOT_STRING_PTR,

     JS_GC_ROOT_OBJECT_PTR,

     JS_GC_ROOT_SCRIPT_PTR

 } JSGCRootType;

 struct RootInfo {

     RootInfo() {}

     RootInfo(const char *name, JSGCRootType type) : name(name), type(type) {}

     const char *name;

     JSGCRootType type;

 };

 typedef js::HashMap<void *,

                     RootInfo,

                     js::DefaultHasher<void *>,

                     js::SystemAllocPolicy> RootedValueMap;

 extern bool

 AddValueRoot(JSContext *cx, js::Value *vp, const char *name);

 extern bool

 AddValueRootRT(JSRuntime *rt, js::Value *vp, const char *name);

 extern bool

 AddStringRoot(JSContext *cx, JSString **rp, const char *name);

 extern bool

 AddObjectRoot(JSContext *cx, JSObject **rp, const char *name);

 extern bool

 AddObjectRoot(JSRuntime *rt, JSObject **rp, const char *name);

 extern bool

 AddScriptRoot(JSContext *cx, JSScript **rp, const char *name);

 extern void

 RemoveRoot(JSRuntime *rt, void *rp);

 } /* namespace js */

 extern bool

 js_InitGC(JSRuntime *rt, uint32_t maxbytes);

 extern void

 js_FinishGC(JSRuntime *rt);

 namespace js {

 class InterpreterFrame;

 extern void

 MarkCompartmentActive(js::InterpreterFrame *fp);

 extern void

 TraceRuntime(JSTracer *trc);

 /* Must be called with GC lock taken. */

 extern bool

 TriggerGC(JSRuntime *rt, JS::gcreason::Reason reason);

 /* Must be called with GC lock taken. */

 extern bool

 TriggerZoneGC(Zone *zone, JS::gcreason::Reason reason);

 extern void

 MaybeGC(JSContext *cx);

 extern void

 ReleaseAllJITCode(FreeOp *op);

 /*

  * Kinds of js_GC invocation.

  */

 typedef enum JSGCInvocationKind {

     /* Normal invocation. */

     GC_NORMAL           = 0,

     /* Minimize GC triggers and release empty GC chunks right away. */

     GC_SHRINK             = 1

 } JSGCInvocationKind;

 extern void

 GC(JSRuntime *rt, JSGCInvocationKind gckind, JS::gcreason::Reason reason);

 extern void

 GCSlice(JSRuntime *rt, JSGCInvocationKind gckind, JS::gcreason::Reason reason, int64_t millis = 0);

 extern void

 GCFinalSlice(JSRuntime *rt, JSGCInvocationKind gckind, JS::gcreason::Reason reason);

 extern void

 GCDebugSlice(JSRuntime *rt, bool limit, int64_t objCount);

 extern void

 PrepareForDebugGC(JSRuntime *rt);

 extern void

 MinorGC(JSRuntime *rt, JS::gcreason::Reason reason);

 extern void

 MinorGC(JSContext *cx, JS::gcreason::Reason reason);

 #ifdef JS_GC_ZEAL

 extern void

 SetGCZeal(JSRuntime *rt, uint8_t zeal, uint32_t frequency);

 #endif

 /* Functions for managing cross compartment gray pointers. */

 extern void

 DelayCrossCompartmentGrayMarking(JSObject *src);

 extern void

 NotifyGCNukeWrapper(JSObject *o);

 extern unsigned

 NotifyGCPreSwap(JSObject *a, JSObject *b);

 extern void

 NotifyGCPostSwap(JSObject *a, JSObject *b, unsigned preResult);

 /*

  * Helper that implements sweeping and allocation for kinds that can be swept

  * and allocated off the main thread.

  *

  * In non-threadsafe builds, all actual sweeping and allocation is performed

  * on the main thread, but GCHelperThread encapsulates this from clients as

  * much as possible.

  */

 class GCHelperThread {

     enum State {

         IDLE,

         SWEEPING,

         ALLOCATING,

         CANCEL_ALLOCATION,

         SHUTDOWN

     };

     /*

      * During the finalization we do not free immediately. Rather we add the

      * corresponding pointers to a buffer which we later release on a

      * separated thread.

      *

      * The buffer is implemented as a vector of 64K arrays of pointers, not as

      * a simple vector, to avoid realloc calls during the vector growth and to

      * not bloat the binary size of the inlined freeLater method. Any OOM

      * during buffer growth results in the pointer being freed immediately.

      */

     static const size_t FREE_ARRAY_SIZE = size_t(1) << 16;

     static const size_t FREE_ARRAY_LENGTH = FREE_ARRAY_SIZE / sizeof(void *);

     JSRuntime         *const rt;

     PRThread          *thread;

     PRCondVar         *wakeup;

     PRCondVar         *done;

     volatile State    state;

     void wait(PRCondVar *which);

     bool              sweepFlag;

     bool              shrinkFlag;

     Vector<void **, 16, js::SystemAllocPolicy> freeVector;

     void            **freeCursor;

     void            **freeCursorEnd;

     bool              backgroundAllocation;

     friend class js::gc::ArenaLists;

     void

     replenishAndFreeLater(void *ptr);

     static void freeElementsAndArray(void **array, void **end) {

         JS_ASSERT(array <= end);

         for (void **p = array; p != end; ++p)

             js_free(*p);

         js_free(array);

     }

     static void threadMain(void* arg);

     void threadLoop();

     /* Must be called with the GC lock taken. */

     void doSweep();

   public:

     GCHelperThread(JSRuntime *rt)

       : rt(rt),

         thread(nullptr),

         wakeup(nullptr),

         done(nullptr),

         state(IDLE),

         sweepFlag(false),

         shrinkFlag(false),

         freeCursor(nullptr),

         freeCursorEnd(nullptr),

         backgroundAllocation(true)

     { }

     bool init();

     void finish();

     /* Must be called with the GC lock taken. */

     void startBackgroundSweep(bool shouldShrink);

     /* Must be called with the GC lock taken. */

     void startBackgroundShrink();

     /* Must be called without the GC lock taken. */

     void waitBackgroundSweepEnd();

     /* Must be called without the GC lock taken. */

     void waitBackgroundSweepOrAllocEnd();

     /* Must be called with the GC lock taken. */

     inline void startBackgroundAllocationIfIdle();

     bool canBackgroundAllocate() const {

         return backgroundAllocation;

     }

     void disableBackgroundAllocation() {

         backgroundAllocation = false;

     }

     PRThread *getThread() const {

         return thread;

     }

     bool onBackgroundThread();

     /*

      * Outside the GC lock may give true answer when in fact the sweeping has

      * been done.

      */

     bool sweeping() const {

         return state == SWEEPING;

     }

     bool shouldShrink() const {

         JS_ASSERT(sweeping());

         return shrinkFlag;

     }

     void freeLater(void *ptr) {

         JS_ASSERT(!sweeping());

         if (freeCursor != freeCursorEnd)

             *freeCursor++ = ptr;

         else

             replenishAndFreeLater(ptr);

     }

 };

 struct GCChunkHasher {

     typedef gc::Chunk *Lookup;

     /*

      * Strip zeros for better distribution after multiplying by the golden

      * ratio.

      */

     static HashNumber hash(gc::Chunk *chunk) {

         JS_ASSERT(!(uintptr_t(chunk) & gc::ChunkMask));

         return HashNumber(uintptr_t(chunk) >> gc::ChunkShift);

     }

     static bool match(gc::Chunk *k, gc::Chunk *l) {

         JS_ASSERT(!(uintptr_t(k) & gc::ChunkMask));

         JS_ASSERT(!(uintptr_t(l) & gc::ChunkMask));

         return k == l;

     }

 };

 typedef HashSet<js::gc::Chunk *, GCChunkHasher, SystemAllocPolicy> GCChunkSet;

 struct GrayRoot {

     void *thing;

     JSGCTraceKind kind;

 #ifdef DEBUG

     JSTraceNamePrinter debugPrinter;

     const void *debugPrintArg;

     size_t debugPrintIndex;

 #endif

     GrayRoot(void *thing, JSGCTraceKind kind)

         : thing(thing), kind(kind) {}

 };

 void

 MarkStackRangeConservatively(JSTracer *trc, Value *begin, Value *end);

 typedef void (*IterateChunkCallback)(JSRuntime *rt, void *data, gc::Chunk *chunk);

 typedef void (*IterateZoneCallback)(JSRuntime *rt, void *data, JS::Zone *zone);

 typedef void (*IterateArenaCallback)(JSRuntime *rt, void *data, gc::Arena *arena,

                                      JSGCTraceKind traceKind, size_t thingSize);

 typedef void (*IterateCellCallback)(JSRuntime *rt, void *data, void *thing,

                                     JSGCTraceKind traceKind, size_t thingSize);

 /*

  * This function calls |zoneCallback| on every zone, |compartmentCallback| on

  * every compartment, |arenaCallback| on every in-use arena, and |cellCallback|

  * on every in-use cell in the GC heap.

  */

 extern void

 IterateZonesCompartmentsArenasCells(JSRuntime *rt, void *data,

                                     IterateZoneCallback zoneCallback,

                                     JSIterateCompartmentCallback compartmentCallback,

                                     IterateArenaCallback arenaCallback,

                                     IterateCellCallback cellCallback);

 /*

  * This function is like IterateZonesCompartmentsArenasCells, but does it for a

  * single zone.

  */

 extern void

 IterateZoneCompartmentsArenasCells(JSRuntime *rt, Zone *zone, void *data,

                                    IterateZoneCallback zoneCallback,

                                    JSIterateCompartmentCallback compartmentCallback,

                                    IterateArenaCallback arenaCallback,

                                    IterateCellCallback cellCallback);

 /*

  * Invoke chunkCallback on every in-use chunk.

  */

 extern void

 IterateChunks(JSRuntime *rt, void *data, IterateChunkCallback chunkCallback);

 typedef void (*IterateScriptCallback)(JSRuntime *rt, void *data, JSScript *script);

 /*

  * Invoke scriptCallback on every in-use script for

  * the given compartment or for all compartments if it is null.

  */

 extern void

 IterateScripts(JSRuntime *rt, JSCompartment *compartment,

                void *data, IterateScriptCallback scriptCallback);

 } /* namespace js */

 extern void

 js_FinalizeStringRT(JSRuntime *rt, JSString *str);

 namespace js {

 JSCompartment *

 NewCompartment(JSContext *cx, JS::Zone *zone, JSPrincipals *principals,

                const JS::CompartmentOptions &options);

 namespace gc {

 extern void

 GCIfNeeded(JSContext *cx);

 /* Tries to run a GC no matter what (used for GC zeal). */

 void

 RunDebugGC(JSContext *cx);

 void

 SetDeterministicGC(JSContext *cx, bool enabled);

 void

 SetValidateGC(JSContext *cx, bool enabled);

 void

 SetFullCompartmentChecks(JSContext *cx, bool enabled);

 /* Wait for the background thread to finish sweeping if it is running. */

 void

 FinishBackgroundFinalize(JSRuntime *rt);

 /*

  * Merge all contents of source into target. This can only be used if source is

  * the only compartment in its zone.

  */

 void

 MergeCompartments(JSCompartment *source, JSCompartment *target);

 const int ZealPokeValue = 1;

 const int ZealAllocValue = 2;

 const int ZealFrameGCValue = 3;

 const int ZealVerifierPreValue = 4;

 const int ZealFrameVerifierPreValue = 5;

 const int ZealStackRootingValue = 6;

 const int ZealGenerationalGCValue = 7;

 const int ZealIncrementalRootsThenFinish = 8;

 const int ZealIncrementalMarkAllThenFinish = 9;

 const int ZealIncrementalMultipleSlices = 10;

 const int ZealVerifierPostValue = 11;

 const int ZealFrameVerifierPostValue = 12;

 const int ZealCheckHashTablesOnMinorGC = 13;

 const int ZealLimit = 13;

 enum VerifierType {

     PreBarrierVerifier,

     PostBarrierVerifier

 };

 #ifdef JS_GC_ZEAL

 /* Check that write barriers have been used correctly. See jsgc.cpp. */

 void

 VerifyBarriers(JSRuntime *rt, VerifierType type);

 void

 MaybeVerifyBarriers(JSContext *cx, bool always = false);

 #else

 static inline void

 VerifyBarriers(JSRuntime *rt, VerifierType type)

 {

 }

 static inline void

 MaybeVerifyBarriers(JSContext *cx, bool always = false)

 {

 }

 #endif

 /*

  * Instances of this class set the |JSRuntime::suppressGC| flag for the duration

  * that they are live. Use of this class is highly discouraged. Please carefully

  * read the comment in jscntxt.h above |suppressGC| and take all appropriate

  * precautions before instantiating this class.

  */

 class AutoSuppressGC

 {

     int32_t &suppressGC_;

   public:

     AutoSuppressGC(ExclusiveContext *cx);

     AutoSuppressGC(JSCompartment *comp);

     AutoSuppressGC(JSRuntime *rt);

     ~AutoSuppressGC()

     {

         suppressGC_--;

     }

 };

 #ifdef DEBUG

 /* Disable OOM testing in sections which are not OOM safe. */

 class AutoEnterOOMUnsafeRegion

 {

     uint32_t saved_;

   public:

     AutoEnterOOMUnsafeRegion() : saved_(OOM_maxAllocations) {

         OOM_maxAllocations = UINT32_MAX;

     }

     ~AutoEnterOOMUnsafeRegion() {

         OOM_maxAllocations = saved_;

     }

 };

 #else

 class AutoEnterOOMUnsafeRegion {};

 #endif /* DEBUG */

 } /* namespace gc */

 #ifdef DEBUG

 /* Use this to avoid assertions when manipulating the wrapper map. */

 class AutoDisableProxyCheck

 {

     MOZ_DECL_USE_GUARD_OBJECT_NOTIFIER;

     uintptr_t &count;

   public:

     AutoDisableProxyCheck(JSRuntime *rt

                           MOZ_GUARD_OBJECT_NOTIFIER_PARAM);

     ~AutoDisableProxyCheck() {

         count--;

     }

 };

 #else

 struct AutoDisableProxyCheck

 {

     AutoDisableProxyCheck(JSRuntime *rt) {}

 };

 #endif

 void

 PurgeJITCaches(JS::Zone *zone);

 // This is the same as IsInsideNursery, but not inlined.

 bool

 UninlinedIsInsideNursery(JSRuntime *rt, const void *thing);

 } /* namespace js */

 #endif /* jsgc_h */