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

/*

* This code implements an incremental mark-and-sweep garbage collector, with

* most sweeping carried out in the background on a parallel thread.

*

* Full vs. zone GC

* ----------------

*

* The collector can collect all zones at once, or a subset. These types of

* collection are referred to as a full GC and a zone GC respectively.

*

* The atoms zone is only collected in a full GC since objects in any zone may

* have pointers to atoms, and these are not recorded in the cross compartment

* pointer map. Also, the atoms zone is not collected if any thread has an

* AutoKeepAtoms instance on the stack, or there are any exclusive threads using

* the runtime.

*

* It is possible for an incremental collection that started out as a full GC to

* become a zone GC if new zones are created during the course of the

* collection.

*

* Incremental collection

* ----------------------

*

* For a collection to be carried out incrementally the following conditions

* must be met:

* - the collection must be run by calling js::GCSlice() rather than js::GC()

* - the GC mode must have been set to JSGC_MODE_INCREMENTAL with

* JS_SetGCParameter()

* - no thread may have an AutoKeepAtoms instance on the stack

*

* The last condition is an engine-internal mechanism to ensure that incremental

* collection is not carried out without the correct barriers being implemented.

* For more information see 'Incremental marking' below.

*

* If the collection is not incremental, all foreground activity happens inside

* a single call to GC() or GCSlice(). However the collection is not complete

* until the background sweeping activity has finished.

*

* An incremental collection proceeds as a series of slices, interleaved with

* mutator activity, i.e. running JavaScript code. Slices are limited by a time

* budget. The slice finishes as soon as possible after the requested time has

* passed.

*

* Collector states

* ----------------

*

* The collector proceeds through the following states, the current state being

* held in JSRuntime::gcIncrementalState:

*

* - MARK_ROOTS - marks the stack and other roots

* - MARK - incrementally marks reachable things

* - SWEEP - sweeps zones in groups and continues marking unswept zones

*

* The MARK_ROOTS activity always takes place in the first slice. The next two

* states can take place over one or more slices.

*

* In other words an incremental collection proceeds like this:

*

* Slice 1: MARK_ROOTS: Roots pushed onto the mark stack.

* MARK: The mark stack is processed by popping an element,

* marking it, and pushing its children.

*

* ... JS code runs ...

*

* Slice 2: MARK: More mark stack processing.

*

* ... JS code runs ...

*

* Slice n-1: MARK: More mark stack processing.

*

* ... JS code runs ...

*

* Slice n: MARK: Mark stack is completely drained.

* SWEEP: Select first group of zones to sweep and sweep them.

*

* ... JS code runs ...

*

* Slice n+1: SWEEP: Mark objects in unswept zones that were newly

* identified as alive (see below). Then sweep more zone

* groups.

*

* ... JS code runs ...

*

* Slice n+2: SWEEP: Mark objects in unswept zones that were newly

* identified as alive. Then sweep more zone groups.

*

* ... JS code runs ...

*

* Slice m: SWEEP: Sweeping is finished, and background sweeping

* started on the helper thread.

*

* ... JS code runs, remaining sweeping done on background thread ...

*

* When background sweeping finishes the GC is complete.

*

* Incremental marking

* -------------------

*

* Incremental collection requires close collaboration with the mutator (i.e.,

* JS code) to guarantee correctness.

*

* - During an incremental GC, if a memory location (except a root) is written

* to, then the value it previously held must be marked. Write barriers

* ensure this.

*

* - Any object that is allocated during incremental GC must start out marked.

*

* - Roots are marked in the first slice and hence don't need write barriers.

* Roots are things like the C stack and the VM stack.

*

* The problem that write barriers solve is that between slices the mutator can

* change the object graph. We must ensure that it cannot do this in such a way

* that makes us fail to mark a reachable object (marking an unreachable object

* is tolerable).

*

* We use a snapshot-at-the-beginning algorithm to do this. This means that we

* promise to mark at least everything that is reachable at the beginning of

* collection. To implement it we mark the old contents of every non-root memory

* location written to by the mutator while the collection is in progress, using

* write barriers. This is described in gc/Barrier.h.

*

* Incremental sweeping

* --------------------

*

* Sweeping is difficult to do incrementally because object finalizers must be

* run at the start of sweeping, before any mutator code runs. The reason is

* that some objects use their finalizers to remove themselves from caches. If

* mutator code was allowed to run after the start of sweeping, it could observe

* the state of the cache and create a new reference to an object that was just

* about to be destroyed.

*

* Sweeping all finalizable objects in one go would introduce long pauses, so

* instead sweeping broken up into groups of zones. Zones which are not yet

* being swept are still marked, so the issue above does not apply.

*

* The order of sweeping is restricted by cross compartment pointers - for

* example say that object |a| from zone A points to object |b| in zone B and

* neither object was marked when we transitioned to the SWEEP phase. Imagine we

* sweep B first and then return to the mutator. It's possible that the mutator

* could cause |a| to become alive through a read barrier (perhaps it was a

* shape that was accessed via a shape table). Then we would need to mark |b|,

* which |a| points to, but |b| has already been swept.

*

* So if there is such a pointer then marking of zone B must not finish before

* marking of zone A. Pointers which form a cycle between zones therefore

* restrict those zones to being swept at the same time, and these are found

* using Tarjan's algorithm for finding the strongly connected components of a

* graph.

*

* GC things without finalizers, and things with finalizers that are able to run

* in the background, are swept on the background thread. This accounts for most

* of the sweeping work.

*

* Reset

* -----

*

* During incremental collection it is possible, although unlikely, for

* conditions to change such that incremental collection is no longer safe. In

* this case, the collection is 'reset' by ResetIncrementalGC(). If we are in

* the mark state, this just stops marking, but if we have started sweeping

* already, we continue until we have swept the current zone group. Following a

* reset, a new non-incremental collection is started.

*

* Compacting GC

* -------------

*

* Compacting GC happens at the end of a major GC as part of the last slice.

* There are three parts:

*

* - Arenas are selected for compaction.

* - The contents of those arenas are moved to new arenas.

* - All references to moved things are updated.

*/

#include "jsgcinlines.h"

#include "mozilla/ArrayUtils.h"

#include "mozilla/DebugOnly.h"

#include "mozilla/MacroForEach.h"

#include "mozilla/MemoryReporting.h"

#include "mozilla/Move.h"

#include <ctype.h>

#include <string.h>

#ifndef XP_WIN

# include <sys/mman.h>

# include <unistd.h>

#endif

#include "jsapi.h"

#include "jsatom.h"

#include "jscntxt.h"

#include "jscompartment.h"

#include "jsfriendapi.h"

#include "jsobj.h"

#include "jsprf.h"

#include "jsscript.h"

#include "jstypes.h"

#include "jsutil.h"

#include "jswatchpoint.h"

#include "jsweakmap.h"

#ifdef XP_WIN

# include "jswin.h"

#endif

#include "gc/FindSCCs.h"

#include "gc/GCInternals.h"

#include "gc/GCTrace.h"

#include "gc/Marking.h"

#include "gc/Memory.h"

#include "jit/BaselineJIT.h"

#include "jit/IonCode.h"

#include "jit/JitcodeMap.h"

#include "js/SliceBudget.h"

#include "proxy/DeadObjectProxy.h"

#include "vm/Debugger.h"

#include "vm/ProxyObject.h"

#include "vm/Shape.h"

#include "vm/String.h"

#include "vm/Symbol.h"

#include "vm/Time.h"

#include "vm/TraceLogging.h"

#include "vm/WrapperObject.h"

#include "jsobjinlines.h"

#include "jsscriptinlines.h"

#include "vm/Stack-inl.h"

#include "vm/String-inl.h"

using namespace js;

using namespace js::gc;

/* for GetCPUCount() */

#include <stdio.h>

#include <sys/param.h>

#include <sys/sysctl.h>

using mozilla::ArrayLength;

using mozilla::HashCodeScrambler;

using mozilla::Maybe;

using mozilla::Swap;

using JS::AutoGCRooter;

/* Perform a Full GC every 20 seconds if MaybeGC is called */

static const uint64_t GC_IDLE_FULL_SPAN = 20 * 1000 * 1000;

/* Increase the IGC marking slice time if we are in highFrequencyGC mode. */

static const int IGC_MARK_SLICE_MULTIPLIER = 2;

const AllocKind gc::slotsToThingKind[] = {

/* 0 */ AllocKind::OBJECT0, AllocKind::OBJECT2, AllocKind::OBJECT2, AllocKind::OBJECT4,

/* 4 */ AllocKind::OBJECT4, AllocKind::OBJECT8, AllocKind::OBJECT8, AllocKind::OBJECT8,

/* 8 */ AllocKind::OBJECT8, AllocKind::OBJECT12, AllocKind::OBJECT12, AllocKind::OBJECT12,

/* 12 */ AllocKind::OBJECT12, AllocKind::OBJECT16, AllocKind::OBJECT16, AllocKind::OBJECT16,

/* 16 */ AllocKind::OBJECT16

};

static_assert(JS_ARRAY_LENGTH(slotsToThingKind) == SLOTS_TO_THING_KIND_LIMIT,

"We have defined a slot count for each kind.");

// Assert that SortedArenaList::MinThingSize is <= the real minimum thing size.

#define CHECK_MIN_THING_SIZE_INNER(x_) \

static_assert(x_ >= SortedArenaList::MinThingSize, \

#x_ " is less than SortedArenaList::MinThingSize!");

#define CHECK_MIN_THING_SIZE(...) { __VA_ARGS__ }; /* Define the array. */ \

MOZ_FOR_EACH(CHECK_MIN_THING_SIZE_INNER, (), (__VA_ARGS__ UINT32_MAX))

const uint32_t Arena::ThingSizes[] = CHECK_MIN_THING_SIZE(

sizeof(JSFunction), /* AllocKind::FUNCTION */

sizeof(FunctionExtended), /* AllocKind::FUNCTION_EXTENDED */

sizeof(JSObject_Slots0), /* AllocKind::OBJECT0 */

sizeof(JSObject_Slots0), /* AllocKind::OBJECT0_BACKGROUND */

sizeof(JSObject_Slots2), /* AllocKind::OBJECT2 */

sizeof(JSObject_Slots2), /* AllocKind::OBJECT2_BACKGROUND */

sizeof(JSObject_Slots4), /* AllocKind::OBJECT4 */

sizeof(JSObject_Slots4), /* AllocKind::OBJECT4_BACKGROUND */

sizeof(JSObject_Slots8), /* AllocKind::OBJECT8 */

sizeof(JSObject_Slots8), /* AllocKind::OBJECT8_BACKGROUND */

sizeof(JSObject_Slots12), /* AllocKind::OBJECT12 */

sizeof(JSObject_Slots12), /* AllocKind::OBJECT12_BACKGROUND */

sizeof(JSObject_Slots16), /* AllocKind::OBJECT16 */

sizeof(JSObject_Slots16), /* AllocKind::OBJECT16_BACKGROUND */

sizeof(JSScript), /* AllocKind::SCRIPT */

sizeof(LazyScript), /* AllocKind::LAZY_SCRIPT */

sizeof(Shape), /* AllocKind::SHAPE */

sizeof(AccessorShape), /* AllocKind::ACCESSOR_SHAPE */

sizeof(BaseShape), /* AllocKind::BASE_SHAPE */

sizeof(ObjectGroup), /* AllocKind::OBJECT_GROUP */

sizeof(JSFatInlineString), /* AllocKind::FAT_INLINE_STRING */

sizeof(JSString), /* AllocKind::STRING */

sizeof(JSExternalString), /* AllocKind::EXTERNAL_STRING */

sizeof(js::FatInlineAtom), /* AllocKind::FAT_INLINE_ATOM */

sizeof(js::NormalAtom), /* AllocKind::ATOM */

sizeof(JS::Symbol), /* AllocKind::SYMBOL */

sizeof(jit::JitCode), /* AllocKind::JITCODE */

);

#undef CHECK_MIN_THING_SIZE_INNER

#undef CHECK_MIN_THING_SIZE

#define OFFSET(type) uint32_t(sizeof(ArenaHeader) + (ArenaSize - sizeof(ArenaHeader)) % sizeof(type))

const uint32_t Arena::FirstThingOffsets[] = {

OFFSET(JSFunction), /* AllocKind::FUNCTION */

OFFSET(FunctionExtended), /* AllocKind::FUNCTION_EXTENDED */

OFFSET(JSObject_Slots0), /* AllocKind::OBJECT0 */

OFFSET(JSObject_Slots0), /* AllocKind::OBJECT0_BACKGROUND */

OFFSET(JSObject_Slots2), /* AllocKind::OBJECT2 */

OFFSET(JSObject_Slots2), /* AllocKind::OBJECT2_BACKGROUND */

OFFSET(JSObject_Slots4), /* AllocKind::OBJECT4 */

OFFSET(JSObject_Slots4), /* AllocKind::OBJECT4_BACKGROUND */

OFFSET(JSObject_Slots8), /* AllocKind::OBJECT8 */

OFFSET(JSObject_Slots8), /* AllocKind::OBJECT8_BACKGROUND */

OFFSET(JSObject_Slots12), /* AllocKind::OBJECT12 */

OFFSET(JSObject_Slots12), /* AllocKind::OBJECT12_BACKGROUND */

OFFSET(JSObject_Slots16), /* AllocKind::OBJECT16 */

OFFSET(JSObject_Slots16), /* AllocKind::OBJECT16_BACKGROUND */

OFFSET(JSScript), /* AllocKind::SCRIPT */

OFFSET(LazyScript), /* AllocKind::LAZY_SCRIPT */

OFFSET(Shape), /* AllocKind::SHAPE */

OFFSET(AccessorShape), /* AllocKind::ACCESSOR_SHAPE */

OFFSET(BaseShape), /* AllocKind::BASE_SHAPE */

OFFSET(ObjectGroup), /* AllocKind::OBJECT_GROUP */

OFFSET(JSFatInlineString), /* AllocKind::FAT_INLINE_STRING */

OFFSET(JSString), /* AllocKind::STRING */

OFFSET(JSExternalString), /* AllocKind::EXTERNAL_STRING */

OFFSET(js::FatInlineAtom), /* AllocKind::FAT_INLINE_ATOM */

OFFSET(js::NormalAtom), /* AllocKind::ATOM */

OFFSET(JS::Symbol), /* AllocKind::SYMBOL */

OFFSET(jit::JitCode), /* AllocKind::JITCODE */

};

#undef OFFSET

struct js::gc::FinalizePhase

{

size_t length;

const AllocKind* kinds;

gcstats::Phase statsPhase;

};

#define PHASE(x, p) { ArrayLength(x), x, p }

/*

* Finalization order for incrementally swept things.

*/

static const AllocKind IncrementalPhaseStrings[] = {

AllocKind::EXTERNAL_STRING

};

static const AllocKind IncrementalPhaseScripts[] = {

AllocKind::SCRIPT,

AllocKind::LAZY_SCRIPT

};

static const AllocKind IncrementalPhaseJitCode[] = {

AllocKind::JITCODE

};

static const FinalizePhase IncrementalFinalizePhases[] = {

PHASE(IncrementalPhaseStrings, gcstats::PHASE_SWEEP_STRING),

PHASE(IncrementalPhaseScripts, gcstats::PHASE_SWEEP_SCRIPT),

PHASE(IncrementalPhaseJitCode, gcstats::PHASE_SWEEP_JITCODE)

};

/*

* Finalization order for things swept in the background.

*/

static const AllocKind BackgroundPhaseObjects[] = {

AllocKind::FUNCTION,

AllocKind::FUNCTION_EXTENDED,

AllocKind::OBJECT0_BACKGROUND,

AllocKind::OBJECT2_BACKGROUND,

AllocKind::OBJECT4_BACKGROUND,

AllocKind::OBJECT8_BACKGROUND,

AllocKind::OBJECT12_BACKGROUND,

AllocKind::OBJECT16_BACKGROUND

};

static const AllocKind BackgroundPhaseStringsAndSymbols[] = {

AllocKind::FAT_INLINE_STRING,

AllocKind::STRING,

AllocKind::FAT_INLINE_ATOM,

AllocKind::ATOM,

AllocKind::SYMBOL

};

static const AllocKind BackgroundPhaseShapes[] = {

AllocKind::SHAPE,

AllocKind::ACCESSOR_SHAPE,

AllocKind::BASE_SHAPE,

AllocKind::OBJECT_GROUP

};

static const FinalizePhase BackgroundFinalizePhases[] = {

PHASE(BackgroundPhaseObjects, gcstats::PHASE_SWEEP_OBJECT),

PHASE(BackgroundPhaseStringsAndSymbols, gcstats::PHASE_SWEEP_STRING),

PHASE(BackgroundPhaseShapes, gcstats::PHASE_SWEEP_SHAPE)

};

#undef PHASE

template<>

JSObject*

ArenaCellIterImpl::get<JSObject>() const

{

MOZ_ASSERT(!done());

return reinterpret_cast<JSObject*>(getCell());

}

#ifdef DEBUG

void

ArenaHeader::checkSynchronizedWithFreeList() const

{

/*

* Do not allow to access the free list when its real head is still stored

* in FreeLists and is not synchronized with this one.

*/

MOZ_ASSERT(allocated());

/*

* We can be called from the background finalization thread when the free

* list in the zone can mutate at any moment. We cannot do any

* checks in this case.

*/

if (IsBackgroundFinalized(getAllocKind()) && zone->runtimeFromAnyThread()->gc.onBackgroundThread())

return;

FreeSpan firstSpan = firstFreeSpan.decompact(arenaAddress());

if (firstSpan.isEmpty())

return;

const FreeList* freeList = zone->arenas.getFreeList(getAllocKind());

if (freeList->isEmpty() || firstSpan.arenaAddress() != freeList->arenaAddress())

return;

/*

* Here this arena has free things, FreeList::lists[thingKind] is not

* empty and also points to this arena. Thus they must be the same.

*/

MOZ_ASSERT(freeList->isSameNonEmptySpan(firstSpan));

}

#endif

void

ArenaHeader::unmarkAll()

{

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

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

}

/* static */ void

Arena::staticAsserts()

{

static_assert(JS_ARRAY_LENGTH(ThingSizes) == size_t(AllocKind::LIMIT),

"We haven't defined all thing sizes.");

static_assert(JS_ARRAY_LENGTH(FirstThingOffsets) == size_t(AllocKind::LIMIT),

"We haven't defined all offsets.");

}

void

Arena::setAsFullyUnused(AllocKind thingKind)

{

FreeSpan fullSpan;

size_t thingSize = Arena::thingSize(thingKind);

fullSpan.initFinal(thingsStart(thingKind), thingsEnd() - thingSize, thingSize);

aheader.setFirstFreeSpan(&fullSpan);

}

template<typename T>

inline size_t

Arena::finalize(FreeOp* fop, AllocKind thingKind, size_t thingSize)

{

/* Enforce requirements on size of T. */

MOZ_ASSERT(thingSize % CellSize == 0);

MOZ_ASSERT(thingSize <= 255);

MOZ_ASSERT(aheader.allocated());

MOZ_ASSERT(thingKind == aheader.getAllocKind());

MOZ_ASSERT(thingSize == aheader.getThingSize());

MOZ_ASSERT(!aheader.hasDelayedMarking);

MOZ_ASSERT(!aheader.markOverflow);

MOZ_ASSERT(!aheader.allocatedDuringIncremental);

uintptr_t firstThing = thingsStart(thingKind);

uintptr_t firstThingOrSuccessorOfLastMarkedThing = firstThing;

uintptr_t lastThing = thingsEnd() - thingSize;

FreeSpan newListHead;

FreeSpan* newListTail = &newListHead;

size_t nmarked = 0;

if (MOZ_UNLIKELY(MemProfiler::enabled())) {

for (ArenaCellIterUnderFinalize i(&aheader); !i.done(); i.next()) {

T* t = i.get<T>();

if (t->asTenured().isMarked())

MemProfiler::MarkTenured(reinterpret_cast<void*>(t));

}

}

for (ArenaCellIterUnderFinalize i(&aheader); !i.done(); i.next()) {

T* t = i.get<T>();

if (t->asTenured().isMarked()) {

uintptr_t thing = reinterpret_cast<uintptr_t>(t);

if (thing != firstThingOrSuccessorOfLastMarkedThing) {

// We just finished passing over one or more free things,

// so record a new FreeSpan.

newListTail->initBoundsUnchecked(firstThingOrSuccessorOfLastMarkedThing,

thing - thingSize);

newListTail = newListTail->nextSpanUnchecked();

}

firstThingOrSuccessorOfLastMarkedThing = thing + thingSize;

nmarked++;

} else {

t->finalize(fop);

JS_POISON(t, JS_SWEPT_TENURED_PATTERN, thingSize);

TraceTenuredFinalize(t);

}

}

if (nmarked == 0) {

// Do nothing. The caller will update the arena header appropriately.

MOZ_ASSERT(newListTail == &newListHead);

JS_EXTRA_POISON(data, JS_SWEPT_TENURED_PATTERN, sizeof(data));

return nmarked;

}

MOZ_ASSERT(firstThingOrSuccessorOfLastMarkedThing != firstThing);

uintptr_t lastMarkedThing = firstThingOrSuccessorOfLastMarkedThing - thingSize;

if (lastThing == lastMarkedThing) {

// If the last thing was marked, we will have already set the bounds of

// the final span, and we just need to terminate the list.

newListTail->initAsEmpty();

} else {

// Otherwise, end the list with a span that covers the final stretch of free things.

newListTail->initFinal(firstThingOrSuccessorOfLastMarkedThing, lastThing, thingSize);

}

#ifdef DEBUG

size_t nfree = 0;

for (const FreeSpan* span = &newListHead; !span->isEmpty(); span = span->nextSpan())

nfree += span->length(thingSize);

MOZ_ASSERT(nfree + nmarked == thingsPerArena(thingSize));

#endif

aheader.setFirstFreeSpan(&newListHead);

return nmarked;

}

// Finalize arenas from src list, releasing empty arenas if keepArenas wasn't

// specified and inserting the others into the appropriate destination size

// bins.

template<typename T>

static inline bool

FinalizeTypedArenas(FreeOp* fop,

ArenaHeader** src,

SortedArenaList& dest,

AllocKind thingKind,

SliceBudget& budget,

ArenaLists::KeepArenasEnum keepArenas)

{

// When operating in the foreground, take the lock at the top.

Maybe<AutoLockGC> maybeLock;

if (!fop->onBackgroundThread())

maybeLock.emplace(fop->runtime());

// During background sweeping free arenas are released later on in

// sweepBackgroundThings().

MOZ_ASSERT_IF(fop->onBackgroundThread(), keepArenas == ArenaLists::KEEP_ARENAS);

size_t thingSize = Arena::thingSize(thingKind);

size_t thingsPerArena = Arena::thingsPerArena(thingSize);

while (ArenaHeader* aheader = *src) {

*src = aheader->next;

size_t nmarked = aheader->getArena()->finalize<T>(fop, thingKind, thingSize);

size_t nfree = thingsPerArena - nmarked;

if (nmarked)

dest.insertAt(aheader, nfree);

else if (keepArenas == ArenaLists::KEEP_ARENAS)

aheader->chunk()->recycleArena(aheader, dest, thingKind, thingsPerArena);

else

fop->runtime()->gc.releaseArena(aheader, maybeLock.ref());

budget.step(thingsPerArena);

if (budget.isOverBudget())

return false;

}

return true;

}

/*

* Finalize the list. On return, |al|'s cursor points to the first non-empty

* arena in the list (which may be null if all arenas are full).

*/

static bool

FinalizeArenas(FreeOp* fop,

ArenaHeader** src,

SortedArenaList& dest,

AllocKind thingKind,

SliceBudget& budget,

ArenaLists::KeepArenasEnum keepArenas)

{

switch (thingKind) {

case AllocKind::FUNCTION:

case AllocKind::FUNCTION_EXTENDED:

case AllocKind::OBJECT0:

case AllocKind::OBJECT0_BACKGROUND:

case AllocKind::OBJECT2:

case AllocKind::OBJECT2_BACKGROUND:

case AllocKind::OBJECT4:

case AllocKind::OBJECT4_BACKGROUND:

case AllocKind::OBJECT8:

case AllocKind::OBJECT8_BACKGROUND:

case AllocKind::OBJECT12:

case AllocKind::OBJECT12_BACKGROUND:

case AllocKind::OBJECT16:

case AllocKind::OBJECT16_BACKGROUND:

return FinalizeTypedArenas<JSObject>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::SCRIPT:

return FinalizeTypedArenas<JSScript>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::LAZY_SCRIPT:

return FinalizeTypedArenas<LazyScript>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::SHAPE:

return FinalizeTypedArenas<Shape>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::ACCESSOR_SHAPE:

return FinalizeTypedArenas<AccessorShape>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::BASE_SHAPE:

return FinalizeTypedArenas<BaseShape>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::OBJECT_GROUP:

return FinalizeTypedArenas<ObjectGroup>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::STRING:

return FinalizeTypedArenas<JSString>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::FAT_INLINE_STRING:

return FinalizeTypedArenas<JSFatInlineString>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::EXTERNAL_STRING:

return FinalizeTypedArenas<JSExternalString>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::FAT_INLINE_ATOM:

return FinalizeTypedArenas<js::FatInlineAtom>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::ATOM:

return FinalizeTypedArenas<js::NormalAtom>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::SYMBOL:

return FinalizeTypedArenas<JS::Symbol>(fop, src, dest, thingKind, budget, keepArenas);

case AllocKind::JITCODE:

return FinalizeTypedArenas<jit::JitCode>(fop, src, dest, thingKind, budget, keepArenas);

default:

MOZ_CRASH("Invalid alloc kind");

}

}

Chunk*

ChunkPool::pop()

{

MOZ_ASSERT(bool(head_) == bool(count_));

if (!count_)

return nullptr;

return remove(head_);

}

void

ChunkPool::push(Chunk* chunk)

{

MOZ_ASSERT(!chunk->info.next);

MOZ_ASSERT(!chunk->info.prev);

chunk->info.age = 0;

chunk->info.next = head_;

if (head_)

head_->info.prev = chunk;

head_ = chunk;

++count_;

MOZ_ASSERT(verify());

}

Chunk*

ChunkPool::remove(Chunk* chunk)

{

MOZ_ASSERT(count_ > 0);

MOZ_ASSERT(contains(chunk));

if (head_ == chunk)

head_ = chunk->info.next;

if (chunk->info.prev)

chunk->info.prev->info.next = chunk->info.next;

if (chunk->info.next)

chunk->info.next->info.prev = chunk->info.prev;

chunk->info.next = chunk->info.prev = nullptr;

--count_;

MOZ_ASSERT(verify());

return chunk;

}

#ifdef DEBUG

bool

ChunkPool::contains(Chunk* chunk) const

{

verify();

for (Chunk* cursor = head_; cursor; cursor = cursor->info.next) {

if (cursor == chunk)

return true;

}

return false;

}

bool

ChunkPool::verify() const

{

MOZ_ASSERT(bool(head_) == bool(count_));

uint32_t count = 0;

for (Chunk* cursor = head_; cursor; cursor = cursor->info.next, ++count) {

MOZ_ASSERT_IF(cursor->info.prev, cursor->info.prev->info.next == cursor);

MOZ_ASSERT_IF(cursor->info.next, cursor->info.next->info.prev == cursor);

}

MOZ_ASSERT(count_ == count);

return true;

}

#endif

void

ChunkPool::Iter::next()

{

MOZ_ASSERT(!done());

current_ = current_->info.next;

}

ChunkPool

GCRuntime::expireEmptyChunkPool(bool shrinkBuffers, const AutoLockGC& lock)

{

/*

* Return old empty chunks to the system while preserving the order of

* other chunks in the list. This way, if the GC runs several times

* without emptying the list, the older chunks will stay at the tail

* and are more likely to reach the max age.

*/

MOZ_ASSERT(emptyChunks(lock).verify());

ChunkPool expired;

unsigned freeChunkCount = 0;

for (ChunkPool::Iter iter(emptyChunks(lock)); !iter.done();) {

Chunk* chunk = iter.get();

iter.next();

MOZ_ASSERT(chunk->unused());

MOZ_ASSERT(!fullChunks(lock).contains(chunk));

MOZ_ASSERT(!availableChunks(lock).contains(chunk));

if (freeChunkCount >= tunables.maxEmptyChunkCount() ||

(freeChunkCount >= tunables.minEmptyChunkCount(lock) &&

(shrinkBuffers || chunk->info.age == MAX_EMPTY_CHUNK_AGE)))

{

emptyChunks(lock).remove(chunk);

prepareToFreeChunk(chunk->info);

expired.push(chunk);

} else {

/* Keep the chunk but increase its age. */

++freeChunkCount;

++chunk->info.age;

}

}

MOZ_ASSERT(expired.verify());

MOZ_ASSERT(emptyChunks(lock).verify());

MOZ_ASSERT(emptyChunks(lock).count() <= tunables.maxEmptyChunkCount());

MOZ_ASSERT_IF(shrinkBuffers, emptyChunks(lock).count() <= tunables.minEmptyChunkCount(lock));

return expired;

}

static void

FreeChunkPool(JSRuntime* rt, ChunkPool& pool)

{

for (ChunkPool::Iter iter(pool); !iter.done();) {

Chunk* chunk = iter.get();

iter.next();

pool.remove(chunk);

MOZ_ASSERT(!chunk->info.numArenasFreeCommitted);

UnmapPages(static_cast<void*>(chunk), ChunkSize);

}

MOZ_ASSERT(pool.count() == 0);

}

void

GCRuntime::freeEmptyChunks(JSRuntime* rt, const AutoLockGC& lock)

{

FreeChunkPool(rt, emptyChunks(lock));

}

/* static */ Chunk*

Chunk::allocate(JSRuntime* rt)

{

Chunk* chunk = static_cast<Chunk*>(MapAlignedPages(ChunkSize, ChunkSize));

if (!chunk)

return nullptr;

chunk->init(rt);

rt->gc.stats.count(gcstats::STAT_NEW_CHUNK);

return chunk;

}

inline void

GCRuntime::prepareToFreeChunk(ChunkInfo& info)

{

MOZ_ASSERT(numArenasFreeCommitted >= info.numArenasFreeCommitted);

numArenasFreeCommitted -= info.numArenasFreeCommitted;

stats.count(gcstats::STAT_DESTROY_CHUNK);

#ifdef DEBUG

/*

* Let FreeChunkPool detect a missing prepareToFreeChunk call before it

* frees chunk.

*/

info.numArenasFreeCommitted = 0;

#endif

}

void Chunk::decommitAllArenas(JSRuntime* rt)

{

decommittedArenas.clear(true);

MarkPagesUnused(&arenas[0], ArenasPerChunk * ArenaSize);

info.freeArenasHead = nullptr;

info.lastDecommittedArenaOffset = 0;

info.numArenasFree = ArenasPerChunk;

info.numArenasFreeCommitted = 0;

}

void

Chunk::init(JSRuntime* rt)

{

JS_POISON(this, JS_FRESH_TENURED_PATTERN, ChunkSize);

/*

* We clear the bitmap to guard against JS::GCThingIsMarkedGray being called

* on uninitialized data, which would happen before the first GC cycle.

*/

bitmap.clear();

/*

* Decommit the arenas. We do this after poisoning so that if the OS does

* not have to recycle the pages, we still get the benefit of poisoning.

*/

decommitAllArenas(rt);

/* Initialize the chunk info. */

info.init();

new (&info.trailer) ChunkTrailer(rt);

/* The rest of info fields are initialized in pickChunk. */

}

/*

* Search for and return the next decommitted Arena. Our goal is to keep

* lastDecommittedArenaOffset "close" to a free arena. We do this by setting

* it to the most recently freed arena when we free, and forcing it to

* the last alloc + 1 when we allocate.

*/

uint32_t

Chunk::findDecommittedArenaOffset()

{

/* Note: lastFreeArenaOffset can be past the end of the list. */

for (unsigned i = info.lastDecommittedArenaOffset; i < ArenasPerChunk; i++)

if (decommittedArenas.get(i))

return i;

for (unsigned i = 0; i < info.lastDecommittedArenaOffset; i++)

if (decommittedArenas.get(i))

return i;

MOZ_CRASH("No decommitted arenas found.");

}

ArenaHeader*

Chunk::fetchNextDecommittedArena()

{

MOZ_ASSERT(info.numArenasFreeCommitted == 0);

MOZ_ASSERT(info.numArenasFree > 0);

unsigned offset = findDecommittedArenaOffset();

info.lastDecommittedArenaOffset = offset + 1;

--info.numArenasFree;

decommittedArenas.unset(offset);

Arena* arena = &arenas[offset];

MarkPagesInUse(arena, ArenaSize);

arena->aheader.setAsNotAllocated();

return &arena->aheader;

}

inline void

GCRuntime::updateOnFreeArenaAlloc(const ChunkInfo& info)

{

MOZ_ASSERT(info.numArenasFreeCommitted <= numArenasFreeCommitted);

--numArenasFreeCommitted;

}

inline ArenaHeader*

Chunk::fetchNextFreeArena(JSRuntime* rt)

{

MOZ_ASSERT(info.numArenasFreeCommitted > 0);

MOZ_ASSERT(info.numArenasFreeCommitted <= info.numArenasFree);

ArenaHeader* aheader = info.freeArenasHead;

info.freeArenasHead = aheader->next;

--info.numArenasFreeCommitted;

--info.numArenasFree;

rt->gc.updateOnFreeArenaAlloc(info);

return aheader;

}

ArenaHeader*

Chunk::allocateArena(JSRuntime* rt, Zone* zone, AllocKind thingKind, const AutoLockGC& lock)

{

ArenaHeader* aheader = info.numArenasFreeCommitted > 0

? fetchNextFreeArena(rt)

: fetchNextDecommittedArena();

aheader->init(zone, thingKind);

updateChunkListAfterAlloc(rt, lock);

return aheader;

}

inline void

GCRuntime::updateOnArenaFree(const ChunkInfo& info)

{

++numArenasFreeCommitted;

}

void

Chunk::addArenaToFreeList(JSRuntime* rt, ArenaHeader* aheader)

{

MOZ_ASSERT(!aheader->allocated());

aheader->next = info.freeArenasHead;

info.freeArenasHead = aheader;

++info.numArenasFreeCommitted;

++info.numArenasFree;

rt->gc.updateOnArenaFree(info);

}

void

Chunk::addArenaToDecommittedList(JSRuntime* rt, const ArenaHeader* aheader)

{

++info.numArenasFree;

decommittedArenas.set(Chunk::arenaIndex(aheader->arenaAddress()));

}

void

Chunk::recycleArena(ArenaHeader* aheader, SortedArenaList& dest, AllocKind thingKind,

size_t thingsPerArena)

{

aheader->getArena()->setAsFullyUnused(thingKind);

dest.insertAt(aheader, thingsPerArena);

}

void

Chunk::releaseArena(JSRuntime* rt, ArenaHeader* aheader, const AutoLockGC& lock)

{

MOZ_ASSERT(aheader->allocated());

MOZ_ASSERT(!aheader->hasDelayedMarking);

aheader->setAsNotAllocated();

addArenaToFreeList(rt, aheader);

updateChunkListAfterFree(rt, lock);

}

bool

Chunk::decommitOneFreeArena(JSRuntime* rt, AutoLockGC& lock)

{

MOZ_ASSERT(info.numArenasFreeCommitted > 0);

ArenaHeader* aheader = fetchNextFreeArena(rt);

updateChunkListAfterAlloc(rt, lock);

bool ok;

{

AutoUnlockGC unlock(lock);

ok = MarkPagesUnused(aheader->getArena(), ArenaSize);

}

if (ok)

addArenaToDecommittedList(rt, aheader);

else

addArenaToFreeList(rt, aheader);

updateChunkListAfterFree(rt, lock);

return ok;

}

void

Chunk::decommitAllArenasWithoutUnlocking(const AutoLockGC& lock)

{

for (size_t i = 0; i < ArenasPerChunk; ++i) {

if (decommittedArenas.get(i) || arenas[i].aheader.allocated())

continue;

if (MarkPagesUnused(&arenas[i], ArenaSize)) {

info.numArenasFreeCommitted--;