/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- * vim: set ts=8 sw=4 et tw=78: * * 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 Mark-and-Sweep Garbage Collector. */ #include "mozilla/Attributes.h" #include "mozilla/Util.h" /* * This code implements a mark-and-sweep garbage collector. The mark phase is * incremental. Most sweeping is done on a background thread. A GC is divided * into slices as follows: * * Slice 1: Roots pushed onto the mark stack. The mark stack is processed by * popping an element, marking it, and pushing its children. * ... JS code runs ... * Slice 2: More mark stack processing. * ... JS code runs ... * Slice n-1: More mark stack processing. * ... JS code runs ... * Slice n: Mark stack is completely drained. Some sweeping is done. * ... JS code runs, remaining sweeping done on background thread ... * * When background sweeping finishes the GC is complete. * * Incremental GC requires close collaboration with the mutator (i.e., JS code): * * 1. 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. * 2. Any object that is allocated during incremental GC must start out marked. * 3. Roots are special memory locations that don't need write * barriers. However, they must be marked in the first slice. Roots are things * like the C stack and the VM stack, since it would be too expensive to put * barriers on them. */ #include #include /* for memset used when DEBUG */ #include "jstypes.h" #include "jsutil.h" #include "jsclist.h" #include "jsprf.h" #include "jsapi.h" #include "jsatom.h" #include "jscompartment.h" #include "jscrashreport.h" #include "jscrashformat.h" #include "jscntxt.h" #include "jsversion.h" #include "jsdbgapi.h" #include "jsexn.h" #include "jsfun.h" #include "jsgc.h" #include "jsinterp.h" #include "jsiter.h" #include "jslock.h" #include "jsnum.h" #include "jsobj.h" #include "jsprobes.h" #include "jsproxy.h" #include "jsscope.h" #include "jsscript.h" #include "jswatchpoint.h" #include "jsweakmap.h" #if JS_HAS_XML_SUPPORT #include "jsxml.h" #endif #include "builtin/MapObject.h" #include "frontend/Parser.h" #include "gc/Marking.h" #include "gc/Memory.h" #include "methodjit/MethodJIT.h" #include "vm/Debugger.h" #include "vm/String.h" #include "jsinterpinlines.h" #include "jsobjinlines.h" #include "vm/ScopeObject-inl.h" #include "vm/String-inl.h" #ifdef MOZ_VALGRIND # define JS_VALGRIND #endif #ifdef JS_VALGRIND # include #endif #ifdef XP_WIN # include "jswin.h" #else # include #endif using namespace mozilla; using namespace js; using namespace js::gc; namespace js { namespace gc { /* * Lower limit after which we limit the heap growth */ const size_t GC_ALLOCATION_THRESHOLD = 30 * 1024 * 1024; /* 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. */ const int IGC_MARK_SLICE_MULTIPLIER = 2; #ifdef JS_GC_ZEAL static void StartVerifyPreBarriers(JSRuntime *rt); static void EndVerifyPreBarriers(JSRuntime *rt); static void StartVerifyPostBarriers(JSRuntime *rt); static void EndVerifyPostBarriers(JSRuntime *rt); void FinishVerifier(JSRuntime *rt); #endif /* This array should be const, but that doesn't link right under GCC. */ AllocKind slotsToThingKind[] = { /* 0 */ FINALIZE_OBJECT0, FINALIZE_OBJECT2, FINALIZE_OBJECT2, FINALIZE_OBJECT4, /* 4 */ FINALIZE_OBJECT4, FINALIZE_OBJECT8, FINALIZE_OBJECT8, FINALIZE_OBJECT8, /* 8 */ FINALIZE_OBJECT8, FINALIZE_OBJECT12, FINALIZE_OBJECT12, FINALIZE_OBJECT12, /* 12 */ FINALIZE_OBJECT12, FINALIZE_OBJECT16, FINALIZE_OBJECT16, FINALIZE_OBJECT16, /* 16 */ FINALIZE_OBJECT16 }; JS_STATIC_ASSERT(JS_ARRAY_LENGTH(slotsToThingKind) == SLOTS_TO_THING_KIND_LIMIT); const uint32_t Arena::ThingSizes[] = { sizeof(JSObject), /* FINALIZE_OBJECT0 */ sizeof(JSObject), /* FINALIZE_OBJECT0_BACKGROUND */ sizeof(JSObject_Slots2), /* FINALIZE_OBJECT2 */ sizeof(JSObject_Slots2), /* FINALIZE_OBJECT2_BACKGROUND */ sizeof(JSObject_Slots4), /* FINALIZE_OBJECT4 */ sizeof(JSObject_Slots4), /* FINALIZE_OBJECT4_BACKGROUND */ sizeof(JSObject_Slots8), /* FINALIZE_OBJECT8 */ sizeof(JSObject_Slots8), /* FINALIZE_OBJECT8_BACKGROUND */ sizeof(JSObject_Slots12), /* FINALIZE_OBJECT12 */ sizeof(JSObject_Slots12), /* FINALIZE_OBJECT12_BACKGROUND */ sizeof(JSObject_Slots16), /* FINALIZE_OBJECT16 */ sizeof(JSObject_Slots16), /* FINALIZE_OBJECT16_BACKGROUND */ sizeof(JSScript), /* FINALIZE_SCRIPT */ sizeof(Shape), /* FINALIZE_SHAPE */ sizeof(BaseShape), /* FINALIZE_BASE_SHAPE */ sizeof(types::TypeObject), /* FINALIZE_TYPE_OBJECT */ #if JS_HAS_XML_SUPPORT sizeof(JSXML), /* FINALIZE_XML */ #endif sizeof(JSShortString), /* FINALIZE_SHORT_STRING */ sizeof(JSString), /* FINALIZE_STRING */ sizeof(JSExternalString), /* FINALIZE_EXTERNAL_STRING */ }; #define OFFSET(type) uint32_t(sizeof(ArenaHeader) + (ArenaSize - sizeof(ArenaHeader)) % sizeof(type)) const uint32_t Arena::FirstThingOffsets[] = { OFFSET(JSObject), /* FINALIZE_OBJECT0 */ OFFSET(JSObject), /* FINALIZE_OBJECT0_BACKGROUND */ OFFSET(JSObject_Slots2), /* FINALIZE_OBJECT2 */ OFFSET(JSObject_Slots2), /* FINALIZE_OBJECT2_BACKGROUND */ OFFSET(JSObject_Slots4), /* FINALIZE_OBJECT4 */ OFFSET(JSObject_Slots4), /* FINALIZE_OBJECT4_BACKGROUND */ OFFSET(JSObject_Slots8), /* FINALIZE_OBJECT8 */ OFFSET(JSObject_Slots8), /* FINALIZE_OBJECT8_BACKGROUND */ OFFSET(JSObject_Slots12), /* FINALIZE_OBJECT12 */ OFFSET(JSObject_Slots12), /* FINALIZE_OBJECT12_BACKGROUND */ OFFSET(JSObject_Slots16), /* FINALIZE_OBJECT16 */ OFFSET(JSObject_Slots16), /* FINALIZE_OBJECT16_BACKGROUND */ OFFSET(JSScript), /* FINALIZE_SCRIPT */ OFFSET(Shape), /* FINALIZE_SHAPE */ OFFSET(BaseShape), /* FINALIZE_BASE_SHAPE */ OFFSET(types::TypeObject), /* FINALIZE_TYPE_OBJECT */ #if JS_HAS_XML_SUPPORT OFFSET(JSXML), /* FINALIZE_XML */ #endif OFFSET(JSShortString), /* FINALIZE_SHORT_STRING */ OFFSET(JSString), /* FINALIZE_STRING */ OFFSET(JSExternalString), /* FINALIZE_EXTERNAL_STRING */ }; #undef OFFSET /* * Finalization order for incrementally swept things. */ static const AllocKind FinalizePhaseShapes[] = { FINALIZE_SHAPE, FINALIZE_BASE_SHAPE, FINALIZE_TYPE_OBJECT }; static const AllocKind* FinalizePhases[] = { FinalizePhaseShapes }; static const int FinalizePhaseCount = sizeof(FinalizePhases) / sizeof(AllocKind*); static const int FinalizePhaseLength[] = { sizeof(FinalizePhaseShapes) / sizeof(AllocKind) }; static const gcstats::Phase FinalizePhaseStatsPhase[] = { gcstats::PHASE_SWEEP_SHAPE }; /* * Finalization order for things swept in the background. */ static const AllocKind BackgroundPhaseObjects[] = { FINALIZE_OBJECT0_BACKGROUND, FINALIZE_OBJECT2_BACKGROUND, FINALIZE_OBJECT4_BACKGROUND, FINALIZE_OBJECT8_BACKGROUND, FINALIZE_OBJECT12_BACKGROUND, FINALIZE_OBJECT16_BACKGROUND }; static const AllocKind BackgroundPhaseStrings[] = { FINALIZE_SHORT_STRING, FINALIZE_STRING }; static const AllocKind* BackgroundPhases[] = { BackgroundPhaseObjects, BackgroundPhaseStrings }; static const int BackgroundPhaseCount = sizeof(BackgroundPhases) / sizeof(AllocKind*); static const int BackgroundPhaseLength[] = { sizeof(BackgroundPhaseObjects) / sizeof(AllocKind), sizeof(BackgroundPhaseStrings) / sizeof(AllocKind) }; #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. */ JS_ASSERT(allocated()); /* * We can be called from the background finalization thread when the free * list in the compartment can mutate at any moment. We cannot do any * checks in this case. */ if (!compartment->rt->isHeapBusy()) return; FreeSpan firstSpan = FreeSpan::decodeOffsets(arenaAddress(), firstFreeSpanOffsets); if (firstSpan.isEmpty()) return; const FreeSpan *list = compartment->arenas.getFreeList(getAllocKind()); if (list->isEmpty() || firstSpan.arenaAddress() != list->arenaAddress()) return; /* * Here this arena has free things, FreeList::lists[thingKind] is not * empty and also points to this arena. Thus they must the same. */ JS_ASSERT(firstSpan.isSameNonEmptySpan(list)); } #endif /* static */ void Arena::staticAsserts() { JS_STATIC_ASSERT(sizeof(Arena) == ArenaSize); JS_STATIC_ASSERT(JS_ARRAY_LENGTH(ThingSizes) == FINALIZE_LIMIT); JS_STATIC_ASSERT(JS_ARRAY_LENGTH(FirstThingOffsets) == FINALIZE_LIMIT); } template inline bool Arena::finalize(FreeOp *fop, AllocKind thingKind, size_t thingSize) { /* Enforce requirements on size of T. */ JS_ASSERT(thingSize % Cell::CellSize == 0); JS_ASSERT(thingSize <= 255); JS_ASSERT(aheader.allocated()); JS_ASSERT(thingKind == aheader.getAllocKind()); JS_ASSERT(thingSize == aheader.getThingSize()); JS_ASSERT(!aheader.hasDelayedMarking); JS_ASSERT(!aheader.markOverflow); JS_ASSERT(!aheader.allocatedDuringIncremental); uintptr_t thing = thingsStart(thingKind); uintptr_t lastByte = thingsEnd() - 1; FreeSpan nextFree(aheader.getFirstFreeSpan()); nextFree.checkSpan(); FreeSpan newListHead; FreeSpan *newListTail = &newListHead; uintptr_t newFreeSpanStart = 0; bool allClear = true; DebugOnly nmarked = 0; for (;; thing += thingSize) { JS_ASSERT(thing <= lastByte + 1); if (thing == nextFree.first) { JS_ASSERT(nextFree.last <= lastByte); if (nextFree.last == lastByte) break; JS_ASSERT(Arena::isAligned(nextFree.last, thingSize)); if (!newFreeSpanStart) newFreeSpanStart = thing; thing = nextFree.last; nextFree = *nextFree.nextSpan(); nextFree.checkSpan(); } else { T *t = reinterpret_cast(thing); if (t->isMarked()) { allClear = false; nmarked++; if (newFreeSpanStart) { JS_ASSERT(thing >= thingsStart(thingKind) + thingSize); newListTail->first = newFreeSpanStart; newListTail->last = thing - thingSize; newListTail = newListTail->nextSpanUnchecked(thingSize); newFreeSpanStart = 0; } } else { if (!newFreeSpanStart) newFreeSpanStart = thing; t->finalize(fop); JS_POISON(t, JS_FREE_PATTERN, thingSize); } } } if (allClear) { JS_ASSERT(newListTail == &newListHead); JS_ASSERT(newFreeSpanStart == thingsStart(thingKind)); return true; } newListTail->first = newFreeSpanStart ? newFreeSpanStart : nextFree.first; JS_ASSERT(Arena::isAligned(newListTail->first, thingSize)); newListTail->last = lastByte; #ifdef DEBUG size_t nfree = 0; for (const FreeSpan *span = &newListHead; span != newListTail; span = span->nextSpan()) { span->checkSpan(); JS_ASSERT(Arena::isAligned(span->first, thingSize)); JS_ASSERT(Arena::isAligned(span->last, thingSize)); nfree += (span->last - span->first) / thingSize + 1; JS_ASSERT(nfree + nmarked <= thingsPerArena(thingSize)); } nfree += (newListTail->last + 1 - newListTail->first) / thingSize; JS_ASSERT(nfree + nmarked == thingsPerArena(thingSize)); #endif aheader.setFirstFreeSpan(&newListHead); return false; } /* * Insert an arena into the list in appropriate position and update the cursor * to ensure that any arena before the cursor is full. */ void ArenaList::insert(ArenaHeader *a) { JS_ASSERT(a); JS_ASSERT_IF(!head, cursor == &head); a->next = *cursor; *cursor = a; if (!a->hasFreeThings()) cursor = &a->next; } template inline bool FinalizeTypedArenas(FreeOp *fop, ArenaHeader **src, ArenaList &dest, AllocKind thingKind, SliceBudget &budget) { /* * Finalize arenas from src list, releasing empty arenas and inserting the * others into dest in an appropriate position. */ size_t thingSize = Arena::thingSize(thingKind); while (ArenaHeader *aheader = *src) { *src = aheader->next; bool allClear = aheader->getArena()->finalize(fop, thingKind, thingSize); if (allClear) aheader->chunk()->releaseArena(aheader); else dest.insert(aheader); budget.step(Arena::thingsPerArena(thingSize)); if (budget.isOverBudget()) return false; } return true; } /* * Finalize the list. On return al->cursor points to the first non-empty arena * after the al->head. */ static bool FinalizeArenas(FreeOp *fop, ArenaHeader **src, ArenaList &dest, AllocKind thingKind, SliceBudget &budget) { switch(thingKind) { case FINALIZE_OBJECT0: case FINALIZE_OBJECT0_BACKGROUND: case FINALIZE_OBJECT2: case FINALIZE_OBJECT2_BACKGROUND: case FINALIZE_OBJECT4: case FINALIZE_OBJECT4_BACKGROUND: case FINALIZE_OBJECT8: case FINALIZE_OBJECT8_BACKGROUND: case FINALIZE_OBJECT12: case FINALIZE_OBJECT12_BACKGROUND: case FINALIZE_OBJECT16: case FINALIZE_OBJECT16_BACKGROUND: return FinalizeTypedArenas(fop, src, dest, thingKind, budget); case FINALIZE_SCRIPT: return FinalizeTypedArenas(fop, src, dest, thingKind, budget); case FINALIZE_SHAPE: return FinalizeTypedArenas(fop, src, dest, thingKind, budget); case FINALIZE_BASE_SHAPE: return FinalizeTypedArenas(fop, src, dest, thingKind, budget); case FINALIZE_TYPE_OBJECT: return FinalizeTypedArenas(fop, src, dest, thingKind, budget); #if JS_HAS_XML_SUPPORT case FINALIZE_XML: return FinalizeTypedArenas(fop, src, dest, thingKind, budget); #endif case FINALIZE_STRING: return FinalizeTypedArenas(fop, src, dest, thingKind, budget); case FINALIZE_SHORT_STRING: return FinalizeTypedArenas(fop, src, dest, thingKind, budget); case FINALIZE_EXTERNAL_STRING: return FinalizeTypedArenas(fop, src, dest, thingKind, budget); default: JS_NOT_REACHED("Invalid alloc kind"); return true; } } static inline Chunk * AllocChunk() { return static_cast(MapAlignedPages(ChunkSize, ChunkSize)); } static inline void FreeChunk(Chunk *p) { UnmapPages(static_cast(p), ChunkSize); } inline bool ChunkPool::wantBackgroundAllocation(JSRuntime *rt) const { /* * To minimize memory waste we do not want to run the background chunk * allocation if we have empty chunks or when the runtime needs just few * of them. */ return rt->gcHelperThread.canBackgroundAllocate() && emptyCount == 0 && rt->gcChunkSet.count() >= 4; } /* Must be called with the GC lock taken. */ inline Chunk * ChunkPool::get(JSRuntime *rt) { JS_ASSERT(this == &rt->gcChunkPool); Chunk *chunk = emptyChunkListHead; if (chunk) { JS_ASSERT(emptyCount); emptyChunkListHead = chunk->info.next; --emptyCount; } else { JS_ASSERT(!emptyCount); chunk = Chunk::allocate(rt); if (!chunk) return NULL; JS_ASSERT(chunk->info.numArenasFreeCommitted == ArenasPerChunk); rt->gcNumArenasFreeCommitted += ArenasPerChunk; } JS_ASSERT(chunk->unused()); JS_ASSERT(!rt->gcChunkSet.has(chunk)); if (wantBackgroundAllocation(rt)) rt->gcHelperThread.startBackgroundAllocationIfIdle(); return chunk; } /* Must be called either during the GC or with the GC lock taken. */ inline void ChunkPool::put(Chunk *chunk) { chunk->info.age = 0; chunk->info.next = emptyChunkListHead; emptyChunkListHead = chunk; emptyCount++; } /* Must be called either during the GC or with the GC lock taken. */ Chunk * ChunkPool::expire(JSRuntime *rt, bool releaseAll) { JS_ASSERT(this == &rt->gcChunkPool); /* * 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. */ Chunk *freeList = NULL; for (Chunk **chunkp = &emptyChunkListHead; *chunkp; ) { JS_ASSERT(emptyCount); Chunk *chunk = *chunkp; JS_ASSERT(chunk->unused()); JS_ASSERT(!rt->gcChunkSet.has(chunk)); JS_ASSERT(chunk->info.age <= MAX_EMPTY_CHUNK_AGE); if (releaseAll || chunk->info.age == MAX_EMPTY_CHUNK_AGE) { *chunkp = chunk->info.next; --emptyCount; chunk->prepareToBeFreed(rt); chunk->info.next = freeList; freeList = chunk; } else { /* Keep the chunk but increase its age. */ ++chunk->info.age; chunkp = &chunk->info.next; } } JS_ASSERT_IF(releaseAll, !emptyCount); return freeList; } static void FreeChunkList(Chunk *chunkListHead) { while (Chunk *chunk = chunkListHead) { JS_ASSERT(!chunk->info.numArenasFreeCommitted); chunkListHead = chunk->info.next; FreeChunk(chunk); } } void ChunkPool::expireAndFree(JSRuntime *rt, bool releaseAll) { FreeChunkList(expire(rt, releaseAll)); } /* static */ Chunk * Chunk::allocate(JSRuntime *rt) { Chunk *chunk = static_cast(AllocChunk()); #ifdef JSGC_ROOT_ANALYSIS // Our poison pointers are not guaranteed to be invalid on 64-bit // architectures, and often are valid. We can't just reserve the full // poison range, because it might already have been taken up by something // else (shared library, previous allocation). So we'll just loop and // discard poison pointers until we get something valid. // // This leaks all of these poisoned pointers. It would be better if they // were marked as uncommitted, but it's a little complicated to avoid // clobbering pre-existing unrelated mappings. while (IsPoisonedPtr(chunk)) chunk = static_cast(AllocChunk()); #endif if (!chunk) return NULL; chunk->init(); rt->gcStats.count(gcstats::STAT_NEW_CHUNK); return chunk; } /* Must be called with the GC lock taken. */ /* static */ inline void Chunk::release(JSRuntime *rt, Chunk *chunk) { JS_ASSERT(chunk); chunk->prepareToBeFreed(rt); FreeChunk(chunk); } inline void Chunk::prepareToBeFreed(JSRuntime *rt) { JS_ASSERT(rt->gcNumArenasFreeCommitted >= info.numArenasFreeCommitted); rt->gcNumArenasFreeCommitted -= info.numArenasFreeCommitted; rt->gcStats.count(gcstats::STAT_DESTROY_CHUNK); #ifdef DEBUG /* * Let FreeChunkList detect a missing prepareToBeFreed call before it * frees chunk. */ info.numArenasFreeCommitted = 0; #endif } void Chunk::init() { JS_POISON(this, JS_FREE_PATTERN, ChunkSize); /* * We clear the bitmap to guard against xpc_IsGrayGCThing being called on * uninitialized data, which would happen before the first GC cycle. */ bitmap.clear(); /* Initialize the arena tracking bitmap. */ decommittedArenas.clear(false); /* Initialize the chunk info. */ info.freeArenasHead = &arenas[0].aheader; info.lastDecommittedArenaOffset = 0; info.numArenasFree = ArenasPerChunk; info.numArenasFreeCommitted = ArenasPerChunk; info.age = 0; /* Initialize the arena header state. */ for (unsigned i = 0; i < ArenasPerChunk; i++) { arenas[i].aheader.setAsNotAllocated(); arenas[i].aheader.next = (i + 1 < ArenasPerChunk) ? &arenas[i + 1].aheader : NULL; } /* The rest of info fields are initialized in PickChunk. */ } inline Chunk ** GetAvailableChunkList(JSCompartment *comp) { JSRuntime *rt = comp->rt; return comp->isSystemCompartment ? &rt->gcSystemAvailableChunkListHead : &rt->gcUserAvailableChunkListHead; } inline void Chunk::addToAvailableList(JSCompartment *comp) { insertToAvailableList(GetAvailableChunkList(comp)); } inline void Chunk::insertToAvailableList(Chunk **insertPoint) { JS_ASSERT(hasAvailableArenas()); JS_ASSERT(!info.prevp); JS_ASSERT(!info.next); info.prevp = insertPoint; Chunk *insertBefore = *insertPoint; if (insertBefore) { JS_ASSERT(insertBefore->info.prevp == insertPoint); insertBefore->info.prevp = &info.next; } info.next = insertBefore; *insertPoint = this; } inline void Chunk::removeFromAvailableList() { JS_ASSERT(info.prevp); *info.prevp = info.next; if (info.next) { JS_ASSERT(info.next->info.prevp == &info.next); info.next->info.prevp = info.prevp; } info.prevp = NULL; info.next = NULL; } /* * 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; JS_NOT_REACHED("No decommitted arenas found."); return -1; } ArenaHeader * Chunk::fetchNextDecommittedArena() { JS_ASSERT(info.numArenasFreeCommitted == 0); JS_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 ArenaHeader * Chunk::fetchNextFreeArena(JSRuntime *rt) { JS_ASSERT(info.numArenasFreeCommitted > 0); JS_ASSERT(info.numArenasFreeCommitted <= info.numArenasFree); JS_ASSERT(info.numArenasFreeCommitted <= rt->gcNumArenasFreeCommitted); ArenaHeader *aheader = info.freeArenasHead; info.freeArenasHead = aheader->next; --info.numArenasFreeCommitted; --info.numArenasFree; --rt->gcNumArenasFreeCommitted; return aheader; } ArenaHeader * Chunk::allocateArena(JSCompartment *comp, AllocKind thingKind) { JS_ASSERT(hasAvailableArenas()); JSRuntime *rt = comp->rt; JS_ASSERT(rt->gcBytes <= rt->gcMaxBytes); if (rt->gcMaxBytes - rt->gcBytes < ArenaSize) return NULL; ArenaHeader *aheader = JS_LIKELY(info.numArenasFreeCommitted > 0) ? fetchNextFreeArena(rt) : fetchNextDecommittedArena(); aheader->init(comp, thingKind); if (JS_UNLIKELY(!hasAvailableArenas())) removeFromAvailableList(); Probes::resizeHeap(comp, rt->gcBytes, rt->gcBytes + ArenaSize); rt->gcBytes += ArenaSize; comp->gcBytes += ArenaSize; if (comp->gcBytes >= comp->gcTriggerBytes) TriggerCompartmentGC(comp, gcreason::ALLOC_TRIGGER); return aheader; } inline void Chunk::addArenaToFreeList(JSRuntime *rt, ArenaHeader *aheader) { JS_ASSERT(!aheader->allocated()); aheader->next = info.freeArenasHead; info.freeArenasHead = aheader; ++info.numArenasFreeCommitted; ++info.numArenasFree; ++rt->gcNumArenasFreeCommitted; } void Chunk::releaseArena(ArenaHeader *aheader) { JS_ASSERT(aheader->allocated()); JS_ASSERT(!aheader->hasDelayedMarking); JSCompartment *comp = aheader->compartment; JSRuntime *rt = comp->rt; AutoLockGC maybeLock; if (rt->gcHelperThread.sweeping()) maybeLock.lock(rt); Probes::resizeHeap(comp, rt->gcBytes, rt->gcBytes - ArenaSize); JS_ASSERT(rt->gcBytes >= ArenaSize); JS_ASSERT(comp->gcBytes >= ArenaSize); if (rt->gcHelperThread.sweeping()) comp->reduceGCTriggerBytes(comp->gcHeapGrowthFactor * ArenaSize); rt->gcBytes -= ArenaSize; comp->gcBytes -= ArenaSize; aheader->setAsNotAllocated(); addArenaToFreeList(rt, aheader); if (info.numArenasFree == 1) { JS_ASSERT(!info.prevp); JS_ASSERT(!info.next); addToAvailableList(comp); } else if (!unused()) { JS_ASSERT(info.prevp); } else { rt->gcChunkSet.remove(this); removeFromAvailableList(); rt->gcChunkPool.put(this); } } } /* namespace gc */ } /* namespace js */ /* The caller must hold the GC lock. */ static Chunk * PickChunk(JSCompartment *comp) { JSRuntime *rt = comp->rt; Chunk **listHeadp = GetAvailableChunkList(comp); Chunk *chunk = *listHeadp; if (chunk) return chunk; chunk = rt->gcChunkPool.get(rt); if (!chunk) return NULL; rt->gcChunkAllocationSinceLastGC = true; /* * FIXME bug 583732 - chunk is newly allocated and cannot be present in * the table so using ordinary lookupForAdd is suboptimal here. */ GCChunkSet::AddPtr p = rt->gcChunkSet.lookupForAdd(chunk); JS_ASSERT(!p); if (!rt->gcChunkSet.add(p, chunk)) { Chunk::release(rt, chunk); return NULL; } chunk->info.prevp = NULL; chunk->info.next = NULL; chunk->addToAvailableList(comp); return chunk; } /* Lifetime for type sets attached to scripts containing observed types. */ static const int64_t JIT_SCRIPT_RELEASE_TYPES_INTERVAL = 60 * 1000 * 1000; JSBool js_InitGC(JSRuntime *rt, uint32_t maxbytes) { if (!rt->gcChunkSet.init(INITIAL_CHUNK_CAPACITY)) return false; if (!rt->gcRootsHash.init(256)) return false; if (!rt->gcLocksHash.init(256)) return false; #ifdef JS_THREADSAFE rt->gcLock = PR_NewLock(); if (!rt->gcLock) return false; #endif if (!rt->gcHelperThread.init()) return false; /* * Separate gcMaxMallocBytes from gcMaxBytes but initialize to maxbytes * for default backward API compatibility. */ rt->gcMaxBytes = maxbytes; rt->setGCMaxMallocBytes(maxbytes); #ifndef JS_MORE_DETERMINISTIC rt->gcJitReleaseTime = PRMJ_Now() + JIT_SCRIPT_RELEASE_TYPES_INTERVAL; #endif return true; } namespace js { inline bool InFreeList(ArenaHeader *aheader, uintptr_t addr) { if (!aheader->hasFreeThings()) return false; FreeSpan firstSpan(aheader->getFirstFreeSpan()); for (const FreeSpan *span = &firstSpan;;) { /* If the thing comes fore the current span, it's not free. */ if (addr < span->first) return false; /* * If we find it inside the span, it's dead. We use here "<=" and not * "<" even for the last span as we know that thing is inside the * arena. Thus for the last span thing < span->end. */ if (addr <= span->last) return true; /* * The last possible empty span is an the end of the arena. Here * span->end < thing < thingsEnd and so we must have more spans. */ span = span->nextSpan(); } } #ifdef JSGC_USE_EXACT_ROOTING static void MarkExactStackRoots(JSTracer *trc) { for (ContextIter cx(trc->runtime); !cx.done(); cx.next()) { for (unsigned i = 0; i < THING_ROOT_LIMIT; i++) { Rooted *rooter = cx->thingGCRooters[i]; while (rooter) { void **addr = (void **)rooter->address(); if (*addr) { if (i == THING_ROOT_OBJECT) { MarkObjectRoot(trc, (JSObject **)addr, "exact stackroot object"); } else if (i == THING_ROOT_STRING) { MarkStringRoot(trc, (JSString **)addr, "exact stackroot string"); } else if (i == THING_ROOT_ID) { MarkIdRoot(trc, (jsid *)addr, "exact stackroot id"); } else if (i == THING_ROOT_PROPERTY_ID) { MarkIdRoot(trc, &((PropertyId *)addr)->asId(), "exact stackroot property id"); } else if (i == THING_ROOT_VALUE) { MarkValueRoot(trc, (Value *)addr, "exact stackroot value"); } else if (i == THING_ROOT_TYPE) { MarkTypeRoot(trc, (types::Type *)addr, "exact stackroot type"); } else if (i == THING_ROOT_SHAPE) { MarkShapeRoot(trc, (Shape **)addr, "exact stackroot shape"); } else if (i == THING_ROOT_BASE_SHAPE) { MarkBaseShapeRoot(trc, (BaseShape **)addr, "exact stackroot baseshape"); } else if (i == THING_ROOT_TYPE_OBJECT) { MarkTypeObjectRoot(trc, (types::TypeObject **)addr, "exact stackroot typeobject"); } else if (i == THING_ROOT_SCRIPT) { MarkScriptRoot(trc, (JSScript **)addr, "exact stackroot script"); } else if (i == THING_ROOT_XML) { MarkXMLRoot(trc, (JSXML **)addr, "exact stackroot xml"); } else { JS_NOT_REACHED("Invalid thing root kind."); } } rooter = rooter->previous(); } } } } #endif /* JSGC_USE_EXACT_ROOTING */ enum ConservativeGCTest { CGCT_VALID, CGCT_LOWBITSET, /* excluded because one of the low bits was set */ CGCT_NOTARENA, /* not within arena range in a chunk */ CGCT_OTHERCOMPARTMENT, /* in another compartment */ CGCT_NOTCHUNK, /* not within a valid chunk */ CGCT_FREEARENA, /* within arena containing only free things */ CGCT_NOTLIVE, /* gcthing is not allocated */ CGCT_END }; /* * Tests whether w is a (possibly dead) GC thing. Returns CGCT_VALID and * details about the thing if so. On failure, returns the reason for rejection. */ inline ConservativeGCTest IsAddressableGCThing(JSRuntime *rt, uintptr_t w, bool skipUncollectedCompartments, gc::AllocKind *thingKindPtr, ArenaHeader **arenaHeader, void **thing) { /* * We assume that the compiler never uses sub-word alignment to store * pointers and does not tag pointers on its own. Additionally, the value * representation for all values and the jsid representation for GC-things * do not touch the low two bits. Thus any word with the low two bits set * is not a valid GC-thing. */ JS_STATIC_ASSERT(JSID_TYPE_STRING == 0 && JSID_TYPE_OBJECT == 4); if (w & 0x3) return CGCT_LOWBITSET; /* * An object jsid has its low bits tagged. In the value representation on * 64-bit, the high bits are tagged. */ const uintptr_t JSID_PAYLOAD_MASK = ~uintptr_t(JSID_TYPE_MASK); #if JS_BITS_PER_WORD == 32 uintptr_t addr = w & JSID_PAYLOAD_MASK; #elif JS_BITS_PER_WORD == 64 uintptr_t addr = w & JSID_PAYLOAD_MASK & JSVAL_PAYLOAD_MASK; #endif Chunk *chunk = Chunk::fromAddress(addr); if (!rt->gcChunkSet.has(chunk)) return CGCT_NOTCHUNK; /* * We query for pointers outside the arena array after checking for an * allocated chunk. Such pointers are rare and we want to reject them * after doing more likely rejections. */ if (!Chunk::withinArenasRange(addr)) return CGCT_NOTARENA; /* If the arena is not currently allocated, don't access the header. */ size_t arenaOffset = Chunk::arenaIndex(addr); if (chunk->decommittedArenas.get(arenaOffset)) return CGCT_FREEARENA; ArenaHeader *aheader = &chunk->arenas[arenaOffset].aheader; if (!aheader->allocated()) return CGCT_FREEARENA; if (skipUncollectedCompartments && !aheader->compartment->isCollecting()) return CGCT_OTHERCOMPARTMENT; AllocKind thingKind = aheader->getAllocKind(); uintptr_t offset = addr & ArenaMask; uintptr_t minOffset = Arena::firstThingOffset(thingKind); if (offset < minOffset) return CGCT_NOTARENA; /* addr can point inside the thing so we must align the address. */ uintptr_t shift = (offset - minOffset) % Arena::thingSize(thingKind); addr -= shift; if (thing) *thing = reinterpret_cast(addr); if (arenaHeader) *arenaHeader = aheader; if (thingKindPtr) *thingKindPtr = thingKind; return CGCT_VALID; } /* * Returns CGCT_VALID and mark it if the w can be a live GC thing and sets * thingKind accordingly. Otherwise returns the reason for rejection. */ inline ConservativeGCTest MarkIfGCThingWord(JSTracer *trc, uintptr_t w) { void *thing; ArenaHeader *aheader; AllocKind thingKind; ConservativeGCTest status = IsAddressableGCThing(trc->runtime, w, IS_GC_MARKING_TRACER(trc), &thingKind, &aheader, &thing); if (status != CGCT_VALID) return status; /* * Check if the thing is free. We must use the list of free spans as at * this point we no longer have the mark bits from the previous GC run and * we must account for newly allocated things. */ if (InFreeList(aheader, uintptr_t(thing))) return CGCT_NOTLIVE; JSGCTraceKind traceKind = MapAllocToTraceKind(thingKind); #ifdef DEBUG const char pattern[] = "machine_stack %p"; char nameBuf[sizeof(pattern) - 2 + sizeof(thing) * 2]; JS_snprintf(nameBuf, sizeof(nameBuf), pattern, thing); JS_SET_TRACING_NAME(trc, nameBuf); #endif JS_SET_TRACING_LOCATION(trc, (void *)w); void *tmp = thing; MarkKind(trc, &tmp, traceKind); JS_ASSERT(tmp == thing); #ifdef DEBUG if (trc->runtime->gcIncrementalState == MARK_ROOTS) trc->runtime->gcSavedRoots.append(JSRuntime::SavedGCRoot(thing, traceKind)); #endif return CGCT_VALID; } static void MarkWordConservatively(JSTracer *trc, uintptr_t w) { /* * The conservative scanner may access words that valgrind considers as * undefined. To avoid false positives and not to alter valgrind view of * the memory we make as memcheck-defined the argument, a copy of the * original word. See bug 572678. */ #ifdef JS_VALGRIND JS_SILENCE_UNUSED_VALUE_IN_EXPR(VALGRIND_MAKE_MEM_DEFINED(&w, sizeof(w))); #endif MarkIfGCThingWord(trc, w); } MOZ_ASAN_BLACKLIST static void MarkRangeConservatively(JSTracer *trc, const uintptr_t *begin, const uintptr_t *end) { JS_ASSERT(begin <= end); for (const uintptr_t *i = begin; i < end; ++i) MarkWordConservatively(trc, *i); } #ifndef JSGC_USE_EXACT_ROOTING static JS_NEVER_INLINE void MarkConservativeStackRoots(JSTracer *trc, bool useSavedRoots) { JSRuntime *rt = trc->runtime; #ifdef DEBUG if (useSavedRoots) { for (JSRuntime::SavedGCRoot *root = rt->gcSavedRoots.begin(); root != rt->gcSavedRoots.end(); root++) { JS_SET_TRACING_NAME(trc, "cstack"); MarkKind(trc, &root->thing, root->kind); } return; } if (rt->gcIncrementalState == MARK_ROOTS) rt->gcSavedRoots.clearAndFree(); #endif ConservativeGCData *cgcd = &rt->conservativeGC; if (!cgcd->hasStackToScan()) { #ifdef JS_THREADSAFE JS_ASSERT(!rt->suspendCount); JS_ASSERT(!rt->requestDepth); #endif return; } uintptr_t *stackMin, *stackEnd; #if JS_STACK_GROWTH_DIRECTION > 0 stackMin = rt->nativeStackBase; stackEnd = cgcd->nativeStackTop; #else stackMin = cgcd->nativeStackTop + 1; stackEnd = reinterpret_cast(rt->nativeStackBase); #endif JS_ASSERT(stackMin <= stackEnd); MarkRangeConservatively(trc, stackMin, stackEnd); MarkRangeConservatively(trc, cgcd->registerSnapshot.words, ArrayEnd(cgcd->registerSnapshot.words)); } #endif /* JSGC_USE_EXACT_ROOTING */ void MarkStackRangeConservatively(JSTracer *trc, Value *beginv, Value *endv) { const uintptr_t *begin = beginv->payloadUIntPtr(); const uintptr_t *end = endv->payloadUIntPtr(); #ifdef JS_NUNBOX32 /* * With 64-bit jsvals on 32-bit systems, we can optimize a bit by * scanning only the payloads. */ JS_ASSERT(begin <= end); for (const uintptr_t *i = begin; i < end; i += sizeof(Value) / sizeof(uintptr_t)) MarkWordConservatively(trc, *i); #else MarkRangeConservatively(trc, begin, end); #endif } JS_NEVER_INLINE void ConservativeGCData::recordStackTop() { /* Update the native stack pointer if it points to a bigger stack. */ uintptr_t dummy; nativeStackTop = &dummy; /* * To record and update the register snapshot for the conservative scanning * with the latest values we use setjmp. */ #if defined(_MSC_VER) # pragma warning(push) # pragma warning(disable: 4611) #endif (void) setjmp(registerSnapshot.jmpbuf); #if defined(_MSC_VER) # pragma warning(pop) #endif } static void RecordNativeStackTopForGC(JSRuntime *rt) { ConservativeGCData *cgcd = &rt->conservativeGC; #ifdef JS_THREADSAFE /* Record the stack top here only if we are called from a request. */ if (!rt->requestDepth) return; #endif cgcd->recordStackTop(); } } /* namespace js */ bool js_IsAddressableGCThing(JSRuntime *rt, uintptr_t w, gc::AllocKind *thingKind, void **thing) { rt->gcHelperThread.waitBackgroundSweepOrAllocEnd(); return js::IsAddressableGCThing(rt, w, false, thingKind, NULL, thing) == CGCT_VALID; } #ifdef DEBUG static void CheckLeakedRoots(JSRuntime *rt); #endif void js_FinishGC(JSRuntime *rt) { /* * Wait until the background finalization stops and the helper thread * shuts down before we forcefully release any remaining GC memory. */ rt->gcHelperThread.finish(); #ifdef JS_GC_ZEAL /* Free memory associated with GC verification. */ FinishVerifier(rt); #endif /* Delete all remaining Compartments. */ for (CompartmentsIter c(rt); !c.done(); c.next()) Foreground::delete_(c.get()); rt->compartments.clear(); rt->atomsCompartment = NULL; rt->gcSystemAvailableChunkListHead = NULL; rt->gcUserAvailableChunkListHead = NULL; for (GCChunkSet::Range r(rt->gcChunkSet.all()); !r.empty(); r.popFront()) Chunk::release(rt, r.front()); rt->gcChunkSet.clear(); rt->gcChunkPool.expireAndFree(rt, true); #ifdef DEBUG if (!rt->gcRootsHash.empty()) CheckLeakedRoots(rt); #endif rt->gcRootsHash.clear(); rt->gcLocksHash.clear(); } JSBool js_AddRoot(JSContext *cx, Value *vp, const char *name) { JSBool ok = js_AddRootRT(cx->runtime, vp, name); if (!ok) JS_ReportOutOfMemory(cx); return ok; } JSBool js_AddGCThingRoot(JSContext *cx, void **rp, const char *name) { JSBool ok = js_AddGCThingRootRT(cx->runtime, rp, name); if (!ok) JS_ReportOutOfMemory(cx); return ok; } JS_FRIEND_API(JSBool) js_AddRootRT(JSRuntime *rt, jsval *vp, const char *name) { /* * Sometimes Firefox will hold weak references to objects and then convert * them to strong references by calling AddRoot (e.g., via PreserveWrapper, * or ModifyBusyCount in workers). We need a read barrier to cover these * cases. */ if (rt->gcIncrementalState == MARK) IncrementalValueBarrier(*vp); return !!rt->gcRootsHash.put((void *)vp, RootInfo(name, JS_GC_ROOT_VALUE_PTR)); } JS_FRIEND_API(JSBool) js_AddGCThingRootRT(JSRuntime *rt, void **rp, const char *name) { /* * Sometimes Firefox will hold weak references to objects and then convert * them to strong references by calling AddRoot (e.g., via PreserveWrapper, * or ModifyBusyCount in workers). We need a read barrier to cover these * cases. */ if (rt->gcIncrementalState == MARK) IncrementalReferenceBarrier(*rp); return !!rt->gcRootsHash.put((void *)rp, RootInfo(name, JS_GC_ROOT_GCTHING_PTR)); } JS_FRIEND_API(void) js_RemoveRoot(JSRuntime *rt, void *rp) { rt->gcRootsHash.remove(rp); rt->gcPoke = true; } typedef RootedValueMap::Range RootRange; typedef RootedValueMap::Entry RootEntry; typedef RootedValueMap::Enum RootEnum; #ifdef DEBUG static void CheckLeakedRoots(JSRuntime *rt) { uint32_t leakedroots = 0; /* Warn (but don't assert) debug builds of any remaining roots. */ for (RootRange r = rt->gcRootsHash.all(); !r.empty(); r.popFront()) { RootEntry &entry = r.front(); leakedroots++; fprintf(stderr, "JS engine warning: leaking GC root \'%s\' at %p\n", entry.value.name ? entry.value.name : "", entry.key); } if (leakedroots > 0) { if (leakedroots == 1) { fprintf(stderr, "JS engine warning: 1 GC root remains after destroying the JSRuntime at %p.\n" " This root may point to freed memory. Objects reachable\n" " through it have not been finalized.\n", (void *) rt); } else { fprintf(stderr, "JS engine warning: %lu GC roots remain after destroying the JSRuntime at %p.\n" " These roots may point to freed memory. Objects reachable\n" " through them have not been finalized.\n", (unsigned long) leakedroots, (void *) rt); } } } void js_DumpNamedRoots(JSRuntime *rt, void (*dump)(const char *name, void *rp, JSGCRootType type, void *data), void *data) { for (RootRange r = rt->gcRootsHash.all(); !r.empty(); r.popFront()) { RootEntry &entry = r.front(); if (const char *name = entry.value.name) dump(name, entry.key, entry.value.type, data); } } #endif /* DEBUG */ uint32_t js_MapGCRoots(JSRuntime *rt, JSGCRootMapFun map, void *data) { int ct = 0; for (RootEnum e(rt->gcRootsHash); !e.empty(); e.popFront()) { RootEntry &entry = e.front(); ct++; int mapflags = map(entry.key, entry.value.type, entry.value.name, data); if (mapflags & JS_MAP_GCROOT_REMOVE) e.removeFront(); if (mapflags & JS_MAP_GCROOT_STOP) break; } return ct; } static size_t ComputeTriggerBytes(JSCompartment *comp, size_t lastBytes, size_t maxBytes, JSGCInvocationKind gckind) { size_t base = gckind == GC_SHRINK ? lastBytes : Max(lastBytes, GC_ALLOCATION_THRESHOLD); float trigger = float(base) * comp->gcHeapGrowthFactor; return size_t(Min(float(maxBytes), trigger)); } void JSCompartment::setGCLastBytes(size_t lastBytes, size_t lastMallocBytes, JSGCInvocationKind gckind) { /* * The heap growth factor depends on the heap size after a GC and the GC frequency. * For low frequency GCs (more than 1sec between GCs) we let the heap grow to 150%. * For high frequency GCs we let the heap grow depending on the heap size: * lastBytes < highFrequencyLowLimit: 300% * lastBytes > highFrequencyHighLimit: 150% * otherwise: linear interpolation between 150% and 300% based on lastBytes */ if (!rt->gcDynamicHeapGrowth) { gcHeapGrowthFactor = 3.0; } else if (lastBytes < 1 * 1024 * 1024) { gcHeapGrowthFactor = rt->gcLowFrequencyHeapGrowth; } else { JS_ASSERT(rt->gcHighFrequencyHighLimitBytes > rt->gcHighFrequencyLowLimitBytes); uint64_t now = PRMJ_Now(); if (rt->gcLastGCTime && rt->gcLastGCTime + rt->gcHighFrequencyTimeThreshold * PRMJ_USEC_PER_MSEC > now) { if (lastBytes <= rt->gcHighFrequencyLowLimitBytes) { gcHeapGrowthFactor = rt->gcHighFrequencyHeapGrowthMax; } else if (lastBytes >= rt->gcHighFrequencyHighLimitBytes) { gcHeapGrowthFactor = rt->gcHighFrequencyHeapGrowthMin; } else { double k = (rt->gcHighFrequencyHeapGrowthMin - rt->gcHighFrequencyHeapGrowthMax) / (double)(rt->gcHighFrequencyHighLimitBytes - rt->gcHighFrequencyLowLimitBytes); gcHeapGrowthFactor = (k * (lastBytes - rt->gcHighFrequencyLowLimitBytes) + rt->gcHighFrequencyHeapGrowthMax); JS_ASSERT(gcHeapGrowthFactor <= rt->gcHighFrequencyHeapGrowthMax && gcHeapGrowthFactor >= rt->gcHighFrequencyHeapGrowthMin); } rt->gcHighFrequencyGC = true; } else { gcHeapGrowthFactor = rt->gcLowFrequencyHeapGrowth; rt->gcHighFrequencyGC = false; } } gcTriggerBytes = ComputeTriggerBytes(this, lastBytes, rt->gcMaxBytes, gckind); gcTriggerMallocAndFreeBytes = ComputeTriggerBytes(this, lastMallocBytes, SIZE_MAX, gckind); } void JSCompartment::reduceGCTriggerBytes(size_t amount) { JS_ASSERT(amount > 0); JS_ASSERT(gcTriggerBytes >= amount); if (gcTriggerBytes - amount < GC_ALLOCATION_THRESHOLD * gcHeapGrowthFactor) return; gcTriggerBytes -= amount; } namespace js { namespace gc { inline void ArenaLists::prepareForIncrementalGC(JSRuntime *rt) { for (size_t i = 0; i != FINALIZE_LIMIT; ++i) { FreeSpan *headSpan = &freeLists[i]; if (!headSpan->isEmpty()) { ArenaHeader *aheader = headSpan->arenaHeader(); aheader->allocatedDuringIncremental = true; rt->gcMarker.delayMarkingArena(aheader); } } } static inline void PushArenaAllocatedDuringSweep(JSRuntime *runtime, ArenaHeader *arena) { arena->setNextAllocDuringSweep(runtime->gcArenasAllocatedDuringSweep); runtime->gcArenasAllocatedDuringSweep = arena; } inline void * ArenaLists::allocateFromArena(JSCompartment *comp, AllocKind thingKind) { Chunk *chunk = NULL; ArenaList *al = &arenaLists[thingKind]; AutoLockGC maybeLock; #ifdef JS_THREADSAFE volatile uintptr_t *bfs = &backgroundFinalizeState[thingKind]; if (*bfs != BFS_DONE) { /* * We cannot search the arena list for free things while the * background finalization runs and can modify head or cursor at any * moment. So we always allocate a new arena in that case. */ maybeLock.lock(comp->rt); if (*bfs == BFS_RUN) { JS_ASSERT(!*al->cursor); chunk = PickChunk(comp); if (!chunk) { /* * Let the caller to wait for the background allocation to * finish and restart the allocation attempt. */ return NULL; } } else if (*bfs == BFS_JUST_FINISHED) { /* See comments before BackgroundFinalizeState definition. */ *bfs = BFS_DONE; } else { JS_ASSERT(*bfs == BFS_DONE); } } #endif /* JS_THREADSAFE */ if (!chunk) { if (ArenaHeader *aheader = *al->cursor) { JS_ASSERT(aheader->hasFreeThings()); /* * The empty arenas are returned to the chunk and should not present on * the list. */ JS_ASSERT(!aheader->isEmpty()); al->cursor = &aheader->next; /* * Move the free span stored in the arena to the free list and * allocate from it. */ freeLists[thingKind] = aheader->getFirstFreeSpan(); aheader->setAsFullyUsed(); if (JS_UNLIKELY(comp->wasGCStarted())) { if (comp->needsBarrier()) { aheader->allocatedDuringIncremental = true; comp->rt->gcMarker.delayMarkingArena(aheader); } else if (comp->isGCSweeping()) { PushArenaAllocatedDuringSweep(comp->rt, aheader); } } return freeLists[thingKind].infallibleAllocate(Arena::thingSize(thingKind)); } /* Make sure we hold the GC lock before we call PickChunk. */ if (!maybeLock.locked()) maybeLock.lock(comp->rt); chunk = PickChunk(comp); if (!chunk) return NULL; } /* * While we still hold the GC lock get an arena from some chunk, mark it * as full as its single free span is moved to the free lits, and insert * it to the list as a fully allocated arena. * * We add the arena before the the head, not after the tail pointed by the * cursor, so after the GC the most recently added arena will be used first * for allocations improving cache locality. */ JS_ASSERT(!*al->cursor); ArenaHeader *aheader = chunk->allocateArena(comp, thingKind); if (!aheader) return NULL; if (JS_UNLIKELY(comp->wasGCStarted())) { if (comp->needsBarrier()) { aheader->allocatedDuringIncremental = true; comp->rt->gcMarker.delayMarkingArena(aheader); } else if (comp->isGCSweeping()) { PushArenaAllocatedDuringSweep(comp->rt, aheader); } } aheader->next = al->head; if (!al->head) { JS_ASSERT(al->cursor == &al->head); al->cursor = &aheader->next; } al->head = aheader; /* See comments before allocateFromNewArena about this assert. */ JS_ASSERT(!aheader->hasFreeThings()); uintptr_t arenaAddr = aheader->arenaAddress(); return freeLists[thingKind].allocateFromNewArena(arenaAddr, Arena::firstThingOffset(thingKind), Arena::thingSize(thingKind)); } void ArenaLists::finalizeNow(FreeOp *fop, AllocKind thingKind) { JS_ASSERT(!IsBackgroundFinalized(thingKind)); JS_ASSERT(backgroundFinalizeState[thingKind] == BFS_DONE || backgroundFinalizeState[thingKind] == BFS_JUST_FINISHED); ArenaHeader *arenas = arenaLists[thingKind].head; arenaLists[thingKind].clear(); SliceBudget budget; FinalizeArenas(fop, &arenas, arenaLists[thingKind], thingKind, budget); JS_ASSERT(!arenas); } void ArenaLists::queueForForegroundSweep(FreeOp *fop, AllocKind thingKind) { JS_ASSERT(!IsBackgroundFinalized(thingKind)); JS_ASSERT(backgroundFinalizeState[thingKind] == BFS_DONE); JS_ASSERT(!arenaListsToSweep[thingKind]); arenaListsToSweep[thingKind] = arenaLists[thingKind].head; arenaLists[thingKind].clear(); } inline void ArenaLists::queueForBackgroundSweep(FreeOp *fop, AllocKind thingKind) { JS_ASSERT(IsBackgroundFinalized(thingKind)); #ifdef JS_THREADSAFE JS_ASSERT(!fop->runtime()->gcHelperThread.sweeping()); #endif ArenaList *al = &arenaLists[thingKind]; if (!al->head) { JS_ASSERT(backgroundFinalizeState[thingKind] == BFS_DONE); JS_ASSERT(al->cursor == &al->head); return; } /* * The state can be done, or just-finished if we have not allocated any GC * things from the arena list after the previous background finalization. */ JS_ASSERT(backgroundFinalizeState[thingKind] == BFS_DONE || backgroundFinalizeState[thingKind] == BFS_JUST_FINISHED); arenaListsToSweep[thingKind] = al->head; al->clear(); backgroundFinalizeState[thingKind] = BFS_RUN; } /*static*/ void ArenaLists::backgroundFinalize(FreeOp *fop, ArenaHeader *listHead, bool onBackgroundThread) { JS_ASSERT(listHead); AllocKind thingKind = listHead->getAllocKind(); JSCompartment *comp = listHead->compartment; ArenaList finalized; SliceBudget budget; FinalizeArenas(fop, &listHead, finalized, thingKind, budget); JS_ASSERT(!listHead); /* * After we finish the finalization al->cursor must point to the end of * the head list as we emptied the list before the background finalization * and the allocation adds new arenas before the cursor. */ ArenaLists *lists = &comp->arenas; ArenaList *al = &lists->arenaLists[thingKind]; AutoLockGC lock(fop->runtime()); JS_ASSERT(lists->backgroundFinalizeState[thingKind] == BFS_RUN); JS_ASSERT(!*al->cursor); if (finalized.head) { *al->cursor = finalized.head; if (finalized.cursor != &finalized.head) al->cursor = finalized.cursor; } /* * We must set the state to BFS_JUST_FINISHED if we are running on the * background thread and we have touched arenaList list, even if we add to * the list only fully allocated arenas without any free things. It ensures * that the allocation thread takes the GC lock and all writes to the free * list elements are propagated. As we always take the GC lock when * allocating new arenas from the chunks we can set the state to BFS_DONE if * we have released all finalized arenas back to their chunks. */ if (onBackgroundThread && finalized.head) lists->backgroundFinalizeState[thingKind] = BFS_JUST_FINISHED; else lists->backgroundFinalizeState[thingKind] = BFS_DONE; lists->arenaListsToSweep[thingKind] = NULL; } void ArenaLists::queueObjectsForSweep(FreeOp *fop) { gcstats::AutoPhase ap(fop->runtime()->gcStats, gcstats::PHASE_SWEEP_OBJECT); finalizeNow(fop, FINALIZE_OBJECT0); finalizeNow(fop, FINALIZE_OBJECT2); finalizeNow(fop, FINALIZE_OBJECT4); finalizeNow(fop, FINALIZE_OBJECT8); finalizeNow(fop, FINALIZE_OBJECT12); finalizeNow(fop, FINALIZE_OBJECT16); queueForBackgroundSweep(fop, FINALIZE_OBJECT0_BACKGROUND); queueForBackgroundSweep(fop, FINALIZE_OBJECT2_BACKGROUND); queueForBackgroundSweep(fop, FINALIZE_OBJECT4_BACKGROUND); queueForBackgroundSweep(fop, FINALIZE_OBJECT8_BACKGROUND); queueForBackgroundSweep(fop, FINALIZE_OBJECT12_BACKGROUND); queueForBackgroundSweep(fop, FINALIZE_OBJECT16_BACKGROUND); #if JS_HAS_XML_SUPPORT finalizeNow(fop, FINALIZE_XML); #endif } void ArenaLists::queueStringsForSweep(FreeOp *fop) { gcstats::AutoPhase ap(fop->runtime()->gcStats, gcstats::PHASE_SWEEP_STRING); queueForBackgroundSweep(fop, FINALIZE_SHORT_STRING); queueForBackgroundSweep(fop, FINALIZE_STRING); finalizeNow(fop, FINALIZE_EXTERNAL_STRING); } void ArenaLists::queueScriptsForSweep(FreeOp *fop) { gcstats::AutoPhase ap(fop->runtime()->gcStats, gcstats::PHASE_SWEEP_SCRIPT); finalizeNow(fop, FINALIZE_SCRIPT); } void ArenaLists::queueShapesForSweep(FreeOp *fop) { gcstats::AutoPhase ap(fop->runtime()->gcStats, gcstats::PHASE_SWEEP_SHAPE); queueForForegroundSweep(fop, FINALIZE_SHAPE); queueForForegroundSweep(fop, FINALIZE_BASE_SHAPE); queueForForegroundSweep(fop, FINALIZE_TYPE_OBJECT); } static void RunLastDitchGC(JSContext *cx, gcreason::Reason reason) { JSRuntime *rt = cx->runtime; /* The last ditch GC preserves all atoms. */ AutoKeepAtoms keep(rt); GC(rt, GC_NORMAL, reason); } /* static */ void * ArenaLists::refillFreeList(JSContext *cx, AllocKind thingKind) { JS_ASSERT(cx->compartment->arenas.freeLists[thingKind].isEmpty()); JSCompartment *comp = cx->compartment; JSRuntime *rt = comp->rt; JS_ASSERT(!rt->isHeapBusy()); bool runGC = rt->gcIncrementalState != NO_INCREMENTAL && comp->gcBytes > comp->gcTriggerBytes; for (;;) { if (JS_UNLIKELY(runGC)) { PrepareCompartmentForGC(comp); RunLastDitchGC(cx, gcreason::LAST_DITCH); /* * The JSGC_END callback can legitimately allocate new GC * things and populate the free list. If that happens, just * return that list head. */ size_t thingSize = Arena::thingSize(thingKind); if (void *thing = comp->arenas.allocateFromFreeList(thingKind, thingSize)) return thing; } /* * allocateFromArena may fail while the background finalization still * run. In that case we want to wait for it to finish and restart. * However, checking for that is racy as the background finalization * could free some things after allocateFromArena decided to fail but * at this point it may have already stopped. To avoid this race we * always try to allocate twice. */ for (bool secondAttempt = false; ; secondAttempt = true) { void *thing = comp->arenas.allocateFromArena(comp, thingKind); if (JS_LIKELY(!!thing)) return thing; if (secondAttempt) break; rt->gcHelperThread.waitBackgroundSweepEnd(); } /* * We failed to allocate. Run the GC if we haven't done it already. * Otherwise report OOM. */ if (runGC) break; runGC = true; } js_ReportOutOfMemory(cx); return NULL; } } /* namespace gc */ } /* namespace js */ JSGCTraceKind js_GetGCThingTraceKind(void *thing) { return GetGCThingTraceKind(thing); } JSBool js_LockGCThingRT(JSRuntime *rt, void *thing) { if (!thing) return true; /* * Sometimes Firefox will hold weak references to objects and then convert * them to strong references by calling AddRoot (e.g., via PreserveWrapper, * or ModifyBusyCount in workers). We need a read barrier to cover these * cases. */ if (rt->gcIncrementalState == MARK) IncrementalReferenceBarrier(thing); if (GCLocks::Ptr p = rt->gcLocksHash.lookupWithDefault(thing, 0)) { p->value++; return true; } return false; } void js_UnlockGCThingRT(JSRuntime *rt, void *thing) { if (!thing) return; if (GCLocks::Ptr p = rt->gcLocksHash.lookup(thing)) { rt->gcPoke = true; if (--p->value == 0) rt->gcLocksHash.remove(p); } } namespace js { void InitTracer(JSTracer *trc, JSRuntime *rt, JSTraceCallback callback) { trc->runtime = rt; trc->callback = callback; trc->debugPrinter = NULL; trc->debugPrintArg = NULL; trc->debugPrintIndex = size_t(-1); trc->eagerlyTraceWeakMaps = true; #ifdef JS_GC_ZEAL trc->realLocation = NULL; #endif } /* static */ int64_t SliceBudget::TimeBudget(int64_t millis) { return millis * PRMJ_USEC_PER_MSEC; } /* static */ int64_t SliceBudget::WorkBudget(int64_t work) { /* For work = 0 not to mean Unlimited, we subtract 1. */ return -work - 1; } SliceBudget::SliceBudget() : deadline(INT64_MAX), counter(INTPTR_MAX) { } SliceBudget::SliceBudget(int64_t budget) { if (budget == Unlimited) { deadline = INT64_MAX; counter = INTPTR_MAX; } else if (budget > 0) { deadline = PRMJ_Now() + budget; counter = CounterReset; } else { deadline = 0; counter = -budget - 1; } } bool SliceBudget::checkOverBudget() { bool over = PRMJ_Now() > deadline; if (!over) counter = CounterReset; return over; } GCMarker::GCMarker() : stack(size_t(-1)), color(BLACK), started(false), unmarkedArenaStackTop(NULL), markLaterArenas(0), grayFailed(false) { } bool GCMarker::init() { return stack.init(MARK_STACK_LENGTH); } void GCMarker::start(JSRuntime *rt) { InitTracer(this, rt, NULL); JS_ASSERT(!started); started = true; color = BLACK; JS_ASSERT(!unmarkedArenaStackTop); JS_ASSERT(markLaterArenas == 0); JS_ASSERT(grayRoots.empty()); JS_ASSERT(!grayFailed); /* * The GC is recomputing the liveness of WeakMap entries, so we delay * visting entries. */ eagerlyTraceWeakMaps = JS_FALSE; } void GCMarker::stop() { JS_ASSERT(isDrained()); JS_ASSERT(started); started = false; JS_ASSERT(!unmarkedArenaStackTop); JS_ASSERT(markLaterArenas == 0); JS_ASSERT(grayRoots.empty()); grayFailed = false; /* Free non-ballast stack memory. */ stack.reset(); grayRoots.clearAndFree(); } void GCMarker::reset() { color = BLACK; stack.reset(); JS_ASSERT(isMarkStackEmpty()); while (unmarkedArenaStackTop) { ArenaHeader *aheader = unmarkedArenaStackTop; JS_ASSERT(aheader->hasDelayedMarking); JS_ASSERT(markLaterArenas); unmarkedArenaStackTop = aheader->getNextDelayedMarking(); aheader->unsetDelayedMarking(); aheader->markOverflow = 0; aheader->allocatedDuringIncremental = 0; markLaterArenas--; } JS_ASSERT(isDrained()); JS_ASSERT(!markLaterArenas); grayRoots.clearAndFree(); grayFailed = false; } /* * When the native stack is low, the GC does not call JS_TraceChildren to mark * the reachable "children" of the thing. Rather the thing is put aside and * JS_TraceChildren is called later with more space on the C stack. * * To implement such delayed marking of the children with minimal overhead for * the normal case of sufficient native stack, the code adds a field per * arena. The field markingDelay->link links all arenas with delayed things * into a stack list with the pointer to stack top in * GCMarker::unmarkedArenaStackTop. delayMarkingChildren adds * arenas to the stack as necessary while markDelayedChildren pops the arenas * from the stack until it empties. */ inline void GCMarker::delayMarkingArena(ArenaHeader *aheader) { if (aheader->hasDelayedMarking) { /* Arena already scheduled to be marked later */ return; } aheader->setNextDelayedMarking(unmarkedArenaStackTop); unmarkedArenaStackTop = aheader; markLaterArenas++; } void GCMarker::delayMarkingChildren(const void *thing) { const Cell *cell = reinterpret_cast(thing); cell->arenaHeader()->markOverflow = 1; delayMarkingArena(cell->arenaHeader()); } void GCMarker::markDelayedChildren(ArenaHeader *aheader) { if (aheader->markOverflow) { bool always = aheader->allocatedDuringIncremental; aheader->markOverflow = 0; for (CellIterUnderGC i(aheader); !i.done(); i.next()) { Cell *t = i.getCell(); if (always || t->isMarked()) { t->markIfUnmarked(); JS_TraceChildren(this, t, MapAllocToTraceKind(aheader->getAllocKind())); } } } else { JS_ASSERT(aheader->allocatedDuringIncremental); PushArena(this, aheader); } aheader->allocatedDuringIncremental = 0; /* * Note that during an incremental GC we may still be allocating into * aheader. However, prepareForIncrementalGC sets the * allocatedDuringIncremental flag if we continue marking. */ } bool GCMarker::markDelayedChildren(SliceBudget &budget) { gcstats::AutoPhase ap(runtime->gcStats, gcstats::PHASE_MARK_DELAYED); JS_ASSERT(unmarkedArenaStackTop); do { /* * If marking gets delayed at the same arena again, we must repeat * marking of its things. For that we pop arena from the stack and * clear its hasDelayedMarking flag before we begin the marking. */ ArenaHeader *aheader = unmarkedArenaStackTop; JS_ASSERT(aheader->hasDelayedMarking); JS_ASSERT(markLaterArenas); unmarkedArenaStackTop = aheader->getNextDelayedMarking(); aheader->unsetDelayedMarking(); markLaterArenas--; markDelayedChildren(aheader); budget.step(150); if (budget.isOverBudget()) return false; } while (unmarkedArenaStackTop); JS_ASSERT(!markLaterArenas); return true; } #ifdef DEBUG void GCMarker::checkCompartment(void *p) { JS_ASSERT(started); JS_ASSERT(static_cast(p)->compartment()->isCollecting()); } #endif bool GCMarker::hasBufferedGrayRoots() const { return !grayFailed; } void GCMarker::startBufferingGrayRoots() { JS_ASSERT(!callback); callback = GrayCallback; JS_ASSERT(IS_GC_MARKING_TRACER(this)); } void GCMarker::endBufferingGrayRoots() { JS_ASSERT(callback == GrayCallback); callback = NULL; JS_ASSERT(IS_GC_MARKING_TRACER(this)); } void GCMarker::markBufferedGrayRoots() { JS_ASSERT(!grayFailed); for (GrayRoot *elem = grayRoots.begin(); elem != grayRoots.end(); elem++) { #ifdef DEBUG debugPrinter = elem->debugPrinter; debugPrintArg = elem->debugPrintArg; debugPrintIndex = elem->debugPrintIndex; #endif JS_SET_TRACING_LOCATION(this, (void *)&elem->thing); void *tmp = elem->thing; MarkKind(this, &tmp, elem->kind); JS_ASSERT(tmp == elem->thing); } grayRoots.clearAndFree(); } void GCMarker::appendGrayRoot(void *thing, JSGCTraceKind kind) { JS_ASSERT(started); if (grayFailed) return; GrayRoot root(thing, kind); #ifdef DEBUG root.debugPrinter = debugPrinter; root.debugPrintArg = debugPrintArg; root.debugPrintIndex = debugPrintIndex; #endif if (!grayRoots.append(root)) { grayRoots.clearAndFree(); grayFailed = true; } } void GCMarker::GrayCallback(JSTracer *trc, void **thingp, JSGCTraceKind kind) { GCMarker *gcmarker = static_cast(trc); gcmarker->appendGrayRoot(*thingp, kind); } size_t GCMarker::sizeOfExcludingThis(JSMallocSizeOfFun mallocSizeOf) const { return stack.sizeOfExcludingThis(mallocSizeOf) + grayRoots.sizeOfExcludingThis(mallocSizeOf); } void SetMarkStackLimit(JSRuntime *rt, size_t limit) { JS_ASSERT(!rt->isHeapBusy()); rt->gcMarker.setSizeLimit(limit); } } /* namespace js */ static void gc_root_traversal(JSTracer *trc, const RootEntry &entry) { const char *name = entry.value.name ? entry.value.name : "root"; if (entry.value.type == JS_GC_ROOT_GCTHING_PTR) MarkGCThingRoot(trc, reinterpret_cast(entry.key), name); else MarkValueRoot(trc, reinterpret_cast(entry.key), name); } static void gc_lock_traversal(const GCLocks::Entry &entry, JSTracer *trc) { JS_ASSERT(entry.value >= 1); JS_SET_TRACING_LOCATION(trc, (void *)&entry.key); void *tmp = entry.key; MarkGCThingRoot(trc, &tmp, "locked object"); JS_ASSERT(tmp == entry.key); } namespace js { void MarkCompartmentActive(StackFrame *fp) { fp->script()->compartment()->active = true; } } /* namespace js */ void AutoIdArray::trace(JSTracer *trc) { JS_ASSERT(tag == IDARRAY); gc::MarkIdRange(trc, idArray->length, idArray->vector, "JSAutoIdArray.idArray"); } void AutoEnumStateRooter::trace(JSTracer *trc) { } inline void AutoGCRooter::trace(JSTracer *trc) { switch (tag) { case JSVAL: MarkValueRoot(trc, &static_cast(this)->val, "JS::AutoValueRooter.val"); return; case PARSER: static_cast(this)->trace(trc); return; case ENUMERATOR: static_cast(this)->trace(trc); return; case IDARRAY: { JSIdArray *ida = static_cast(this)->idArray; MarkIdRange(trc, ida->length, ida->vector, "JS::AutoIdArray.idArray"); return; } case DESCRIPTORS: { PropDescArray &descriptors = static_cast(this)->descriptors; for (size_t i = 0, len = descriptors.length(); i < len; i++) { PropDesc &desc = descriptors[i]; MarkValueRoot(trc, &desc.pd_, "PropDesc::pd_"); MarkValueRoot(trc, &desc.value_, "PropDesc::value_"); MarkValueRoot(trc, &desc.get_, "PropDesc::get_"); MarkValueRoot(trc, &desc.set_, "PropDesc::set_"); } return; } case DESCRIPTOR : { PropertyDescriptor &desc = *static_cast(this); if (desc.obj) MarkObjectRoot(trc, &desc.obj, "Descriptor::obj"); MarkValueRoot(trc, &desc.value, "Descriptor::value"); if ((desc.attrs & JSPROP_GETTER) && desc.getter) { JSObject *tmp = JS_FUNC_TO_DATA_PTR(JSObject *, desc.getter); MarkObjectRoot(trc, &tmp, "Descriptor::get"); desc.getter = JS_DATA_TO_FUNC_PTR(JSPropertyOp, tmp); } if (desc.attrs & JSPROP_SETTER && desc.setter) { JSObject *tmp = JS_FUNC_TO_DATA_PTR(JSObject *, desc.setter); MarkObjectRoot(trc, &tmp, "Descriptor::set"); desc.setter = JS_DATA_TO_FUNC_PTR(JSStrictPropertyOp, tmp); } return; } #if JS_HAS_XML_SUPPORT case NAMESPACES: { JSXMLArray &array = static_cast(this)->array; MarkObjectRange(trc, array.length, array.vector, "JSXMLArray.vector"); js_XMLArrayCursorTrace(trc, array.cursors); return; } case XML: js_TraceXML(trc, static_cast(this)->xml); return; #endif case OBJECT: if (static_cast(this)->obj) MarkObjectRoot(trc, &static_cast(this)->obj, "JS::AutoObjectRooter.obj"); return; case ID: MarkIdRoot(trc, &static_cast(this)->id_, "JS::AutoIdRooter.id_"); return; case VALVECTOR: { AutoValueVector::VectorImpl &vector = static_cast(this)->vector; MarkValueRootRange(trc, vector.length(), vector.begin(), "js::AutoValueVector.vector"); return; } case STRING: if (static_cast(this)->str) MarkStringRoot(trc, &static_cast(this)->str, "JS::AutoStringRooter.str"); return; case IDVECTOR: { AutoIdVector::VectorImpl &vector = static_cast(this)->vector; MarkIdRootRange(trc, vector.length(), vector.begin(), "js::AutoIdVector.vector"); return; } case SHAPEVECTOR: { AutoShapeVector::VectorImpl &vector = static_cast(this)->vector; MarkShapeRootRange(trc, vector.length(), const_cast(vector.begin()), "js::AutoShapeVector.vector"); return; } case OBJVECTOR: { AutoObjectVector::VectorImpl &vector = static_cast(this)->vector; MarkObjectRootRange(trc, vector.length(), vector.begin(), "js::AutoObjectVector.vector"); return; } case STRINGVECTOR: { AutoStringVector::VectorImpl &vector = static_cast(this)->vector; MarkStringRootRange(trc, vector.length(), vector.begin(), "js::AutoStringVector.vector"); return; } case NAMEVECTOR: { AutoNameVector::VectorImpl &vector = static_cast(this)->vector; MarkStringRootRange(trc, vector.length(), vector.begin(), "js::AutoNameVector.vector"); return; } case VALARRAY: { AutoValueArray *array = static_cast(this); MarkValueRootRange(trc, array->length(), array->start(), "js::AutoValueArray"); return; } case SCRIPTVECTOR: { AutoScriptVector::VectorImpl &vector = static_cast(this)->vector; for (size_t i = 0; i < vector.length(); i++) MarkScriptRoot(trc, &vector[i], "AutoScriptVector element"); return; } case PROPDESC: { PropDesc::AutoRooter *rooter = static_cast(this); MarkValueRoot(trc, &rooter->pd->pd_, "PropDesc::AutoRooter pd"); MarkValueRoot(trc, &rooter->pd->value_, "PropDesc::AutoRooter value"); MarkValueRoot(trc, &rooter->pd->get_, "PropDesc::AutoRooter get"); MarkValueRoot(trc, &rooter->pd->set_, "PropDesc::AutoRooter set"); return; } case SHAPERANGE: { Shape::Range::AutoRooter *rooter = static_cast(this); rooter->trace(trc); return; } case STACKSHAPE: { StackShape::AutoRooter *rooter = static_cast(this); if (rooter->shape->base) MarkBaseShapeRoot(trc, (BaseShape**) &rooter->shape->base, "StackShape::AutoRooter base"); MarkIdRoot(trc, (jsid*) &rooter->shape->propid, "StackShape::AutoRooter id"); return; } case STACKBASESHAPE: { StackBaseShape::AutoRooter *rooter = static_cast(this); if (rooter->base->parent) MarkObjectRoot(trc, (JSObject**) &rooter->base->parent, "StackBaseShape::AutoRooter parent"); if ((rooter->base->flags & BaseShape::HAS_GETTER_OBJECT) && rooter->base->rawGetter) { MarkObjectRoot(trc, (JSObject**) &rooter->base->rawGetter, "StackBaseShape::AutoRooter getter"); } if ((rooter->base->flags & BaseShape::HAS_SETTER_OBJECT) && rooter->base->rawSetter) { MarkObjectRoot(trc, (JSObject**) &rooter->base->rawSetter, "StackBaseShape::AutoRooter setter"); } return; } case BINDINGS: { Bindings::AutoRooter *rooter = static_cast(this); rooter->trace(trc); return; } case GETTERSETTER: { AutoRooterGetterSetter::Inner *rooter = static_cast(this); if ((rooter->attrs & JSPROP_GETTER) && *rooter->pgetter) MarkObjectRoot(trc, (JSObject**) rooter->pgetter, "AutoRooterGetterSetter getter"); if ((rooter->attrs & JSPROP_SETTER) && *rooter->psetter) MarkObjectRoot(trc, (JSObject**) rooter->psetter, "AutoRooterGetterSetter setter"); return; } case REGEXPSTATICS: { /* RegExpStatics::AutoRooter *rooter = static_cast(this); rooter->trace(trc); */ return; } case HASHABLEVALUE: { /* HashableValue::AutoRooter *rooter = static_cast(this); rooter->trace(trc); */ return; } } JS_ASSERT(tag >= 0); MarkValueRootRange(trc, tag, static_cast(this)->array, "JS::AutoArrayRooter.array"); } /* static */ void AutoGCRooter::traceAll(JSTracer *trc) { for (js::AutoGCRooter *gcr = trc->runtime->autoGCRooters; gcr; gcr = gcr->down) gcr->trace(trc); } void Shape::Range::AutoRooter::trace(JSTracer *trc) { if (r->cursor) MarkShapeRoot(trc, const_cast(&r->cursor), "Shape::Range::AutoRooter"); } void Bindings::AutoRooter::trace(JSTracer *trc) { bindings->trace(trc); } void RegExpStatics::AutoRooter::trace(JSTracer *trc) { if (statics->matchPairsInput) MarkStringRoot(trc, reinterpret_cast(&statics->matchPairsInput), "RegExpStatics::AutoRooter matchPairsInput"); if (statics->pendingInput) MarkStringRoot(trc, reinterpret_cast(&statics->pendingInput), "RegExpStatics::AutoRooter pendingInput"); } void HashableValue::AutoRooter::trace(JSTracer *trc) { MarkValueRoot(trc, reinterpret_cast(&v->value), "HashableValue::AutoRooter"); } namespace js { static void MarkRuntime(JSTracer *trc, bool useSavedRoots = false) { JSRuntime *rt = trc->runtime; JS_ASSERT(trc->callback != GCMarker::GrayCallback); if (IS_GC_MARKING_TRACER(trc)) { for (CompartmentsIter c(rt); !c.done(); c.next()) { if (!c->isCollecting()) c->markCrossCompartmentWrappers(trc); } Debugger::markCrossCompartmentDebuggerObjectReferents(trc); } AutoGCRooter::traceAll(trc); if (rt->hasContexts()) { #ifdef JSGC_USE_EXACT_ROOTING MarkExactStackRoots(trc); #else MarkConservativeStackRoots(trc, useSavedRoots); #endif rt->markSelfHostedGlobal(trc); } for (RootRange r = rt->gcRootsHash.all(); !r.empty(); r.popFront()) gc_root_traversal(trc, r.front()); for (GCLocks::Range r = rt->gcLocksHash.all(); !r.empty(); r.popFront()) gc_lock_traversal(r.front(), trc); if (rt->scriptAndCountsVector) { ScriptAndCountsVector &vec = *rt->scriptAndCountsVector; for (size_t i = 0; i < vec.length(); i++) MarkScriptRoot(trc, &vec[i].script, "scriptAndCountsVector"); } if (!IS_GC_MARKING_TRACER(trc) || rt->atomsCompartment->isCollecting()) MarkAtomState(trc); rt->staticStrings.trace(trc); for (ContextIter acx(rt); !acx.done(); acx.next()) acx->mark(trc); /* We can't use GCCompartmentsIter if we're called from TraceRuntime. */ for (CompartmentsIter c(rt); !c.done(); c.next()) { if (IS_GC_MARKING_TRACER(trc) && !c->isCollecting()) continue; if ((c->activeAnalysis || c->isPreservingCode()) && IS_GC_MARKING_TRACER(trc)) { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_MARK_TYPES); c->markTypes(trc); } /* During a GC, these are treated as weak pointers. */ if (!IS_GC_MARKING_TRACER(trc)) { if (c->watchpointMap) c->watchpointMap->markAll(trc); } /* Do not discard scripts with counts while profiling. */ if (rt->profilingScripts) { for (CellIterUnderGC i(c, FINALIZE_SCRIPT); !i.done(); i.next()) { JSScript *script = i.get(); if (script->hasScriptCounts) { MarkScriptRoot(trc, &script, "profilingScripts"); JS_ASSERT(script == i.get()); } } } } #ifdef JS_METHODJIT /* We need to expand inline frames before stack scanning. */ for (CompartmentsIter c(rt); !c.done(); c.next()) mjit::ExpandInlineFrames(c); #endif rt->stackSpace.markAndClobber(trc); rt->debugScopes->mark(trc); /* The embedding can register additional roots here. */ if (JSTraceDataOp op = rt->gcBlackRootsTraceOp) (*op)(trc, rt->gcBlackRootsData); /* During GC, this buffers up the gray roots and doesn't mark them. */ if (JSTraceDataOp op = rt->gcGrayRootsTraceOp) { if (IS_GC_MARKING_TRACER(trc)) { GCMarker *gcmarker = static_cast(trc); gcmarker->startBufferingGrayRoots(); (*op)(trc, rt->gcGrayRootsData); gcmarker->endBufferingGrayRoots(); } else { (*op)(trc, rt->gcGrayRootsData); } } } static void TriggerOperationCallback(JSRuntime *rt, gcreason::Reason reason) { if (rt->gcIsNeeded) return; rt->gcIsNeeded = true; rt->gcTriggerReason = reason; rt->triggerOperationCallback(); } void TriggerGC(JSRuntime *rt, gcreason::Reason reason) { JS_ASSERT(rt->onOwnerThread()); if (rt->isHeapBusy()) return; PrepareForFullGC(rt); TriggerOperationCallback(rt, reason); } void TriggerCompartmentGC(JSCompartment *comp, gcreason::Reason reason) { JSRuntime *rt = comp->rt; JS_ASSERT(rt->onOwnerThread()); if (rt->isHeapBusy()) return; if (rt->gcZeal() == ZealAllocValue) { TriggerGC(rt, reason); return; } if (comp == rt->atomsCompartment) { /* We can't do a compartmental GC of the default compartment. */ TriggerGC(rt, reason); return; } PrepareCompartmentForGC(comp); TriggerOperationCallback(rt, reason); } void MaybeGC(JSContext *cx) { JSRuntime *rt = cx->runtime; JS_ASSERT(rt->onOwnerThread()); if (rt->gcZeal() == ZealAllocValue || rt->gcZeal() == ZealPokeValue) { PrepareForFullGC(rt); GC(rt, GC_NORMAL, gcreason::MAYBEGC); return; } if (rt->gcIsNeeded) { GCSlice(rt, GC_NORMAL, gcreason::MAYBEGC); return; } double factor = rt->gcHighFrequencyGC ? 0.75 : 0.9; JSCompartment *comp = cx->compartment; if (comp->gcBytes > 1024 * 1024 && comp->gcBytes >= factor * comp->gcTriggerBytes && rt->gcIncrementalState == NO_INCREMENTAL && !rt->gcHelperThread.sweeping()) { PrepareCompartmentForGC(comp); GCSlice(rt, GC_NORMAL, gcreason::MAYBEGC); return; } if (comp->gcMallocAndFreeBytes > comp->gcTriggerMallocAndFreeBytes) { PrepareCompartmentForGC(comp); GCSlice(rt, GC_NORMAL, gcreason::MAYBEGC); return; } #ifndef JS_MORE_DETERMINISTIC /* * Access to the counters and, on 32 bit, setting gcNextFullGCTime below * is not atomic and a race condition could trigger or suppress the GC. We * tolerate this. */ int64_t now = PRMJ_Now(); if (rt->gcNextFullGCTime && rt->gcNextFullGCTime <= now) { if (rt->gcChunkAllocationSinceLastGC || rt->gcNumArenasFreeCommitted > FreeCommittedArenasThreshold) { PrepareForFullGC(rt); GCSlice(rt, GC_SHRINK, gcreason::MAYBEGC); } else { rt->gcNextFullGCTime = now + GC_IDLE_FULL_SPAN; } } #endif } static void DecommitArenasFromAvailableList(JSRuntime *rt, Chunk **availableListHeadp) { Chunk *chunk = *availableListHeadp; if (!chunk) return; /* * Decommit is expensive so we avoid holding the GC lock while calling it. * * We decommit from the tail of the list to minimize interference with the * main thread that may start to allocate things at this point. * * The arena that is been decommitted outside the GC lock must not be * available for allocations either via the free list or via the * decommittedArenas bitmap. For that we just fetch the arena from the * free list before the decommit pretending as it was allocated. If this * arena also is the single free arena in the chunk, then we must remove * from the available list before we release the lock so the allocation * thread would not see chunks with no free arenas on the available list. * * After we retake the lock, we mark the arena as free and decommitted if * the decommit was successful. We must also add the chunk back to the * available list if we removed it previously or when the main thread * have allocated all remaining free arenas in the chunk. * * We also must make sure that the aheader is not accessed again after we * decommit the arena. */ JS_ASSERT(chunk->info.prevp == availableListHeadp); while (Chunk *next = chunk->info.next) { JS_ASSERT(next->info.prevp == &chunk->info.next); chunk = next; } for (;;) { while (chunk->info.numArenasFreeCommitted != 0) { ArenaHeader *aheader = chunk->fetchNextFreeArena(rt); Chunk **savedPrevp = chunk->info.prevp; if (!chunk->hasAvailableArenas()) chunk->removeFromAvailableList(); size_t arenaIndex = Chunk::arenaIndex(aheader->arenaAddress()); bool ok; { /* * If the main thread waits for the decommit to finish, skip * potentially expensive unlock/lock pair on the contested * lock. */ Maybe maybeUnlock; if (!rt->isHeapBusy()) maybeUnlock.construct(rt); ok = MarkPagesUnused(aheader->getArena(), ArenaSize); } if (ok) { ++chunk->info.numArenasFree; chunk->decommittedArenas.set(arenaIndex); } else { chunk->addArenaToFreeList(rt, aheader); } JS_ASSERT(chunk->hasAvailableArenas()); JS_ASSERT(!chunk->unused()); if (chunk->info.numArenasFree == 1) { /* * Put the chunk back to the available list either at the * point where it was before to preserve the available list * that we enumerate, or, when the allocation thread has fully * used all the previous chunks, at the beginning of the * available list. */ Chunk **insertPoint = savedPrevp; if (savedPrevp != availableListHeadp) { Chunk *prev = Chunk::fromPointerToNext(savedPrevp); if (!prev->hasAvailableArenas()) insertPoint = availableListHeadp; } chunk->insertToAvailableList(insertPoint); } else { JS_ASSERT(chunk->info.prevp); } if (rt->gcChunkAllocationSinceLastGC) { /* * The allocator thread has started to get new chunks. We should stop * to avoid decommitting arenas in just allocated chunks. */ return; } } /* * chunk->info.prevp becomes null when the allocator thread consumed * all chunks from the available list. */ JS_ASSERT_IF(chunk->info.prevp, *chunk->info.prevp == chunk); if (chunk->info.prevp == availableListHeadp || !chunk->info.prevp) break; /* * prevp exists and is not the list head. It must point to the next * field of the previous chunk. */ chunk = chunk->getPrevious(); } } static void DecommitArenas(JSRuntime *rt) { DecommitArenasFromAvailableList(rt, &rt->gcSystemAvailableChunkListHead); DecommitArenasFromAvailableList(rt, &rt->gcUserAvailableChunkListHead); } /* Must be called with the GC lock taken. */ static void ExpireChunksAndArenas(JSRuntime *rt, bool shouldShrink) { if (Chunk *toFree = rt->gcChunkPool.expire(rt, shouldShrink)) { AutoUnlockGC unlock(rt); FreeChunkList(toFree); } if (shouldShrink) DecommitArenas(rt); } static void SweepBackgroundThings(JSRuntime* rt, bool onBackgroundThread) { /* * We must finalize in the correct order, see comments in * finalizeObjects. */ FreeOp fop(rt, false); for (int phase = 0 ; phase < BackgroundPhaseCount ; ++phase) { for (JSCompartment *c = rt->gcSweepingCompartments; c; c = c->gcNextCompartment) { for (int index = 0 ; index < BackgroundPhaseLength[phase] ; ++index) { AllocKind kind = BackgroundPhases[phase][index]; ArenaHeader *arenas = c->arenas.arenaListsToSweep[kind]; if (arenas) { ArenaLists::backgroundFinalize(&fop, arenas, onBackgroundThread); } } } } while (JSCompartment *c = rt->gcSweepingCompartments) { rt->gcSweepingCompartments = c->gcNextCompartment; c->gcNextCompartment = NULL; } } #ifdef JS_THREADSAFE static void AssertBackgroundSweepingFinished(JSRuntime *rt) { for (CompartmentsIter c(rt); !c.done(); c.next()) { JS_ASSERT(!c->gcNextCompartment); for (unsigned i = 0 ; i < FINALIZE_LIMIT ; ++i) { JS_ASSERT(!c->arenas.arenaListsToSweep[i]); JS_ASSERT(c->arenas.doneBackgroundFinalize(AllocKind(i))); } } } static unsigned GetCPUCount() { static unsigned ncpus = 0; if (ncpus == 0) { # ifdef XP_WIN SYSTEM_INFO sysinfo; GetSystemInfo(&sysinfo); ncpus = unsigned(sysinfo.dwNumberOfProcessors); # else long n = sysconf(_SC_NPROCESSORS_ONLN); ncpus = (n > 0) ? unsigned(n) : 1; # endif } return ncpus; } #endif /* JS_THREADSAFE */ bool GCHelperThread::init() { #ifdef JS_THREADSAFE if (!(wakeup = PR_NewCondVar(rt->gcLock))) return false; if (!(done = PR_NewCondVar(rt->gcLock))) return false; thread = PR_CreateThread(PR_USER_THREAD, threadMain, this, PR_PRIORITY_NORMAL, PR_GLOBAL_THREAD, PR_JOINABLE_THREAD, 0); if (!thread) return false; backgroundAllocation = (GetCPUCount() >= 2); #else backgroundAllocation = false; #endif /* JS_THREADSAFE */ return true; } void GCHelperThread::finish() { #ifdef JS_THREADSAFE PRThread *join = NULL; { AutoLockGC lock(rt); if (thread && state != SHUTDOWN) { /* * We cannot be in the ALLOCATING or CANCEL_ALLOCATION states as * the allocations should have been stopped during the last GC. */ JS_ASSERT(state == IDLE || state == SWEEPING); if (state == IDLE) PR_NotifyCondVar(wakeup); state = SHUTDOWN; join = thread; } } if (join) { /* PR_DestroyThread is not necessary. */ PR_JoinThread(join); } if (wakeup) PR_DestroyCondVar(wakeup); if (done) PR_DestroyCondVar(done); #else /* * In non-threadsafe configurations, we do all work synchronously, so we must be IDLE */ JS_ASSERT(state == IDLE); #endif /* JS_THREADSAFE */ } #ifdef JS_THREADSAFE /* static */ void GCHelperThread::threadMain(void *arg) { PR_SetCurrentThreadName("JS GC Helper"); static_cast(arg)->threadLoop(); } void GCHelperThread::threadLoop() { AutoLockGC lock(rt); /* * Even on the first iteration the state can be SHUTDOWN or SWEEPING if * the stop request or the GC and the corresponding startBackgroundSweep call * happen before this thread has a chance to run. */ for (;;) { switch (state) { case SHUTDOWN: return; case IDLE: PR_WaitCondVar(wakeup, PR_INTERVAL_NO_TIMEOUT); break; case SWEEPING: doSweep(); if (state == SWEEPING) state = IDLE; PR_NotifyAllCondVar(done); break; case ALLOCATING: do { Chunk *chunk; { AutoUnlockGC unlock(rt); chunk = Chunk::allocate(rt); } /* OOM stops the background allocation. */ if (!chunk) break; JS_ASSERT(chunk->info.numArenasFreeCommitted == ArenasPerChunk); rt->gcNumArenasFreeCommitted += ArenasPerChunk; rt->gcChunkPool.put(chunk); } while (state == ALLOCATING && rt->gcChunkPool.wantBackgroundAllocation(rt)); if (state == ALLOCATING) state = IDLE; break; case CANCEL_ALLOCATION: state = IDLE; PR_NotifyAllCondVar(done); break; } } } #endif /* JS_THREADSAFE */ void GCHelperThread::startBackgroundSweep(bool shouldShrink) { #ifdef JS_THREADSAFE AutoLockGC lock(rt); JS_ASSERT(state == IDLE); JS_ASSERT(!sweepFlag); sweepFlag = true; shrinkFlag = shouldShrink; state = SWEEPING; PR_NotifyCondVar(wakeup); #else JS_NOT_REACHED("No background sweep if !JS_THREADSAFE"); #endif /* JS_THREADSAFE */ } #ifdef JS_THREADSAFE /* Must be called with the GC lock taken. */ void GCHelperThread::startBackgroundShrink() { switch (state) { case IDLE: JS_ASSERT(!sweepFlag); shrinkFlag = true; state = SWEEPING; PR_NotifyCondVar(wakeup); break; case SWEEPING: shrinkFlag = true; break; case ALLOCATING: case CANCEL_ALLOCATION: /* * If we have started background allocation there is nothing to * shrink. */ break; case SHUTDOWN: JS_NOT_REACHED("No shrink on shutdown"); } } #endif /* JS_THREADSAFE */ void GCHelperThread::waitBackgroundSweepEnd() { #ifdef JS_THREADSAFE AutoLockGC lock(rt); while (state == SWEEPING) PR_WaitCondVar(done, PR_INTERVAL_NO_TIMEOUT); if (rt->gcIncrementalState == NO_INCREMENTAL) AssertBackgroundSweepingFinished(rt); #else JS_ASSERT(state == IDLE); #endif /* JS_THREADSAFE */ } void GCHelperThread::waitBackgroundSweepOrAllocEnd() { #ifdef JS_THREADSAFE AutoLockGC lock(rt); if (state == ALLOCATING) state = CANCEL_ALLOCATION; while (state == SWEEPING || state == CANCEL_ALLOCATION) PR_WaitCondVar(done, PR_INTERVAL_NO_TIMEOUT); if (rt->gcIncrementalState == NO_INCREMENTAL) AssertBackgroundSweepingFinished(rt); #else JS_ASSERT(state == IDLE); #endif /* JS_THREADSAFE */ } /* Must be called with the GC lock taken. */ inline void GCHelperThread::startBackgroundAllocationIfIdle() { #ifdef JS_THREADSAFE if (state == IDLE) { state = ALLOCATING; PR_NotifyCondVar(wakeup); } #else JS_ASSERT(state == IDLE); #endif /* JS_THREADSAFE */ } JS_FRIEND_API(void) GCHelperThread::replenishAndFreeLater(void *ptr) { JS_ASSERT(freeCursor == freeCursorEnd); do { if (freeCursor && !freeVector.append(freeCursorEnd - FREE_ARRAY_LENGTH)) break; freeCursor = (void **) OffTheBooks::malloc_(FREE_ARRAY_SIZE); if (!freeCursor) { freeCursorEnd = NULL; break; } freeCursorEnd = freeCursor + FREE_ARRAY_LENGTH; *freeCursor++ = ptr; return; } while (false); Foreground::free_(ptr); } #ifdef JS_THREADSAFE /* Must be called with the GC lock taken. */ void GCHelperThread::doSweep() { if (sweepFlag) { sweepFlag = false; AutoUnlockGC unlock(rt); SweepBackgroundThings(rt, true); if (freeCursor) { void **array = freeCursorEnd - FREE_ARRAY_LENGTH; freeElementsAndArray(array, freeCursor); freeCursor = freeCursorEnd = NULL; } else { JS_ASSERT(!freeCursorEnd); } for (void ***iter = freeVector.begin(); iter != freeVector.end(); ++iter) { void **array = *iter; freeElementsAndArray(array, array + FREE_ARRAY_LENGTH); } freeVector.resize(0); rt->freeLifoAlloc.freeAll(); } bool shrinking = shrinkFlag; ExpireChunksAndArenas(rt, shrinking); /* * The main thread may have called ShrinkGCBuffers while * ExpireChunksAndArenas(rt, false) was running, so we recheck the flag * afterwards. */ if (!shrinking && shrinkFlag) { shrinkFlag = false; ExpireChunksAndArenas(rt, true); } } #endif /* JS_THREADSAFE */ } /* namespace js */ static bool ReleaseObservedTypes(JSRuntime *rt) { bool releaseTypes = rt->gcZeal() != 0; #ifndef JS_MORE_DETERMINISTIC int64_t now = PRMJ_Now(); if (now >= rt->gcJitReleaseTime) releaseTypes = true; if (releaseTypes) rt->gcJitReleaseTime = now + JIT_SCRIPT_RELEASE_TYPES_INTERVAL; #endif return releaseTypes; } static void SweepCompartments(FreeOp *fop, gcreason::Reason gcReason) { JSRuntime *rt = fop->runtime(); JS_ASSERT_IF(gcReason == gcreason::LAST_CONTEXT, !rt->hasContexts()); JSDestroyCompartmentCallback callback = rt->destroyCompartmentCallback; /* Skip the atomsCompartment. */ JSCompartment **read = rt->compartments.begin() + 1; JSCompartment **end = rt->compartments.end(); JSCompartment **write = read; JS_ASSERT(rt->compartments.length() >= 1); JS_ASSERT(*rt->compartments.begin() == rt->atomsCompartment); while (read < end) { JSCompartment *compartment = *read++; if (!compartment->hold && compartment->wasGCStarted() && (compartment->arenas.arenaListsAreEmpty() || gcReason == gcreason::LAST_CONTEXT)) { compartment->arenas.checkEmptyFreeLists(); if (callback) callback(fop, compartment); if (compartment->principals) JS_DropPrincipals(rt, compartment->principals); fop->delete_(compartment); continue; } *write++ = compartment; } rt->compartments.resize(write - rt->compartments.begin()); } static void PurgeRuntime(JSRuntime *rt) { for (GCCompartmentsIter c(rt); !c.done(); c.next()) c->purge(); rt->freeLifoAlloc.transferUnusedFrom(&rt->tempLifoAlloc); rt->gsnCache.purge(); rt->propertyCache.purge(rt); rt->newObjectCache.purge(); rt->nativeIterCache.purge(); rt->sourceDataCache.purge(); rt->evalCache.clear(); for (ContextIter acx(rt); !acx.done(); acx.next()) acx->purge(); } static bool ShouldPreserveJITCode(JSCompartment *c, int64_t currentTime) { if (c->rt->gcShouldCleanUpEverything || !c->types.inferenceEnabled) return false; if (c->rt->alwaysPreserveCode) return true; if (c->lastAnimationTime + PRMJ_USEC_PER_SEC >= currentTime && c->lastCodeRelease + (PRMJ_USEC_PER_SEC * 300) >= currentTime) { return true; } c->lastCodeRelease = currentTime; return false; } static void BeginMarkPhase(JSRuntime *rt) { int64_t currentTime = PRMJ_Now(); rt->gcIsFull = true; DebugOnly any = false; for (CompartmentsIter c(rt); !c.done(); c.next()) { /* Assert that compartment state is as we expect */ JS_ASSERT(!c->isCollecting()); for (unsigned i = 0; i < FINALIZE_LIMIT; ++i) JS_ASSERT(!c->arenas.arenaListsToSweep[i]); /* Set up which compartments will be collected. */ if (c->isGCScheduled()) { any = true; if (c != rt->atomsCompartment) c->setGCState(JSCompartment::Mark); } else { rt->gcIsFull = false; } c->setPreservingCode(ShouldPreserveJITCode(c, currentTime)); } /* Check that at least one compartment is scheduled for collection. */ JS_ASSERT(any); /* * Atoms are not in the cross-compartment map. So if there are any * compartments that are not being collected, we are not allowed to collect * atoms. Otherwise, the non-collected compartments could contain pointers * to atoms that we would miss. */ if (rt->atomsCompartment->isGCScheduled() && rt->gcIsFull && !rt->gcKeepAtoms) rt->atomsCompartment->setGCState(JSCompartment::Mark); /* * At the end of each incremental slice, we call prepareForIncrementalGC, * which marks objects in all arenas that we're currently allocating * into. This can cause leaks if unreachable objects are in these * arenas. This purge call ensures that we only mark arenas that have had * allocations after the incremental GC started. */ if (rt->gcIsIncremental) { for (GCCompartmentsIter c(rt); !c.done(); c.next()) c->arenas.purge(); } rt->gcMarker.start(rt); JS_ASSERT(!rt->gcMarker.callback); JS_ASSERT(IS_GC_MARKING_TRACER(&rt->gcMarker)); /* For non-incremental GC the following sweep discards the jit code. */ if (rt->gcIsIncremental) { for (GCCompartmentsIter c(rt); !c.done(); c.next()) { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_MARK_DISCARD_CODE); c->discardJitCode(rt->defaultFreeOp(), false); } } GCMarker *gcmarker = &rt->gcMarker; rt->gcStartNumber = rt->gcNumber; /* Reset weak map list. */ WeakMapBase::resetWeakMapList(rt); /* * We must purge the runtime at the beginning of an incremental GC. The * danger if we purge later is that the snapshot invariant of incremental * GC will be broken, as follows. If some object is reachable only through * some cache (say the dtoaCache) then it will not be part of the snapshot. * If we purge after root marking, then the mutator could obtain a pointer * to the object and start using it. This object might never be marked, so * a GC hazard would exist. */ { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_PURGE); PurgeRuntime(rt); } /* * Mark phase. */ gcstats::AutoPhase ap1(rt->gcStats, gcstats::PHASE_MARK); gcstats::AutoPhase ap2(rt->gcStats, gcstats::PHASE_MARK_ROOTS); /* Unmark everything in the compartments being collected. */ for (GCCompartmentsIter c(rt); !c.done(); c.next()) c->arenas.unmarkAll(); MarkRuntime(gcmarker); } void MarkWeakReferences(GCMarker *gcmarker) { JS_ASSERT(gcmarker->isDrained()); while (WatchpointMap::markAllIteratively(gcmarker) || WeakMapBase::markAllIteratively(gcmarker) || Debugger::markAllIteratively(gcmarker)) { SliceBudget budget; gcmarker->drainMarkStack(budget); } JS_ASSERT(gcmarker->isDrained()); } static void MarkGrayAndWeak(JSRuntime *rt) { GCMarker *gcmarker = &rt->gcMarker; { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_MARK_WEAK); JS_ASSERT(gcmarker->isDrained()); MarkWeakReferences(gcmarker); } { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_MARK_GRAY); gcmarker->setMarkColorGray(); if (gcmarker->hasBufferedGrayRoots()) { gcmarker->markBufferedGrayRoots(); } else { if (JSTraceDataOp op = rt->gcGrayRootsTraceOp) (*op)(gcmarker, rt->gcGrayRootsData); } SliceBudget budget; gcmarker->drainMarkStack(budget); } { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_MARK_GRAY_WEAK); MarkWeakReferences(gcmarker); } JS_ASSERT(gcmarker->isDrained()); } #ifdef DEBUG static void ValidateIncrementalMarking(JSRuntime *rt); #endif static void EndMarkPhase(JSRuntime *rt) { { gcstats::AutoPhase ap1(rt->gcStats, gcstats::PHASE_MARK); MarkGrayAndWeak(rt); } JS_ASSERT(rt->gcMarker.isDrained()); #ifdef DEBUG if (rt->gcIsIncremental && rt->gcValidate) ValidateIncrementalMarking(rt); #endif /* * Having black->gray edges violates our promise to the cycle * collector. This can happen if we're collecting a compartment and it has * an edge to an uncollected compartment: it's possible that the source and * destination of the cross-compartment edge should be gray, but the source * was marked black by the conservative scanner. */ bool foundBlackGray = false; for (GCCompartmentsIter c(rt); !c.done(); c.next()) { for (WrapperMap::Enum e(c->crossCompartmentWrappers); !e.empty(); e.popFront()) { Cell *dst = e.front().key.wrapped; Cell *src = ToMarkable(e.front().value); JS_ASSERT(src->compartment() == c.get()); if (IsCellMarked(&src) && !src->isMarked(GRAY) && dst->isMarked(GRAY)) { JS_ASSERT(!dst->compartment()->isCollecting()); foundBlackGray = true; } } } /* * To avoid the black->gray edge, we completely clear the mark bits of all * uncollected compartments. This is safe, although it may prevent the * cycle collector from collecting some dead objects. */ if (foundBlackGray) { for (CompartmentsIter c(rt); !c.done(); c.next()) { if (!c->isCollecting()) c->arenas.unmarkAll(); } } /* We do not discard JIT here code as the following sweeping does that. */ } #ifdef DEBUG static void ValidateIncrementalMarking(JSRuntime *rt) { typedef HashMap BitmapMap; BitmapMap map; if (!map.init()) return; GCMarker *gcmarker = &rt->gcMarker; /* Save existing mark bits. */ for (GCChunkSet::Range r(rt->gcChunkSet.all()); !r.empty(); r.popFront()) { ChunkBitmap *bitmap = &r.front()->bitmap; uintptr_t *entry = (uintptr_t *)js_malloc(sizeof(bitmap->bitmap)); if (!entry) return; memcpy(entry, bitmap->bitmap, sizeof(bitmap->bitmap)); if (!map.putNew(r.front(), entry)) return; } /* Save the existing weakmaps. */ WeakMapVector weakmaps; if (!WeakMapBase::saveWeakMapList(rt, weakmaps)) return; /* * After this point, the function should run to completion, so we shouldn't * do anything fallible. */ /* Re-do all the marking, but non-incrementally. */ js::gc::State state = rt->gcIncrementalState; rt->gcIncrementalState = MARK_ROOTS; /* As we're re-doing marking, we need to reset the weak map list. */ WeakMapBase::resetWeakMapList(rt); JS_ASSERT(gcmarker->isDrained()); gcmarker->reset(); for (GCChunkSet::Range r(rt->gcChunkSet.all()); !r.empty(); r.popFront()) r.front()->bitmap.clear(); MarkRuntime(gcmarker, true); SliceBudget budget; rt->gcIncrementalState = MARK; rt->gcMarker.drainMarkStack(budget); MarkGrayAndWeak(rt); /* Now verify that we have the same mark bits as before. */ for (GCChunkSet::Range r(rt->gcChunkSet.all()); !r.empty(); r.popFront()) { Chunk *chunk = r.front(); ChunkBitmap *bitmap = &chunk->bitmap; uintptr_t *entry = map.lookup(r.front())->value; ChunkBitmap incBitmap; memcpy(incBitmap.bitmap, entry, sizeof(incBitmap.bitmap)); js_free(entry); for (size_t i = 0; i < ArenasPerChunk; i++) { if (chunk->decommittedArenas.get(i)) continue; Arena *arena = &chunk->arenas[i]; if (!arena->aheader.allocated()) continue; if (!arena->aheader.compartment->isCollecting()) continue; if (arena->aheader.allocatedDuringIncremental) continue; AllocKind kind = arena->aheader.getAllocKind(); uintptr_t thing = arena->thingsStart(kind); uintptr_t end = arena->thingsEnd(); while (thing < end) { Cell *cell = (Cell *)thing; JS_ASSERT_IF(bitmap->isMarked(cell, BLACK), incBitmap.isMarked(cell, BLACK)); thing += Arena::thingSize(kind); } } memcpy(bitmap->bitmap, incBitmap.bitmap, sizeof(incBitmap.bitmap)); } /* Restore the weak map list. */ WeakMapBase::resetWeakMapList(rt); WeakMapBase::restoreWeakMapList(rt, weakmaps); rt->gcIncrementalState = state; } #endif /* * If compartment A has an edge to an unmarked object in compartment B, then we * must not sweep A in a later slice than we sweep B. That's because a write * barrier in A that could lead to the unmarked object in B becoming * marked. However, if we had already swept that object, we would be in trouble. * * If we consider these dependencies as a graph, then all the compartments in * any strongly-connected component of this graph must be swept in the same * slice. This class is used to compute these strongly connected components via * Tarjan's algorithm. */ class PartitionCompartments { typedef unsigned Node; typedef Vector NodeVector; typedef Vector BoolVector; static const Node Undefined = Node(-1); JSRuntime *runtime; /* * The value of clock ticks monotonically upward as each new compartment is * discovered by the algorithm. When a new SCC is found, it is assigned a * number from nextSCC. */ Node clock, nextSCC; /* * Compartments have an index based on their order in rt->compartments. The * index is used as a subscript into the arrays below. * * discoveryTime[comp]: The |clock| value when comp was first explored. * lowLink[comp]: The minimal discovery time of any compartment reachable * from |comp|. * stack: List of explored compartments that haven't been assigned to an SCC. * scc[comp]: SCC number that |comp| is in. * onStack[comp]: Whether |comp| in in |stack|. */ NodeVector discoveryTime, lowLink, stack, scc; BoolVector onStack; bool fail_; void processNode(Node v); void fail() { fail_ = true; } bool failed() { return fail_; } public: PartitionCompartments(JSRuntime *rt); void partition(); unsigned getSCC(JSCompartment *comp) { return failed() ? 0 : scc[comp->index]; } }; const PartitionCompartments::Node PartitionCompartments::Undefined; PartitionCompartments::PartitionCompartments(JSRuntime *rt) : runtime(rt), clock(0), nextSCC(0), fail_(false) { size_t n = runtime->compartments.length(); if (!discoveryTime.reserve(n) || !lowLink.reserve(n) || !scc.reserve(n) || !onStack.reserve(n) || !stack.reserve(n)) { fail(); return; } for (Node v = 0; v < runtime->compartments.length(); v++) { runtime->compartments[v]->index = v; discoveryTime.infallibleAppend(Undefined); lowLink.infallibleAppend(Undefined); scc.infallibleAppend(Undefined); onStack.infallibleAppend(false); } } /* See the Wikipedia article "Tarjan's strongly connected components algorithm". */ void PartitionCompartments::processNode(Node v) { int stackDummy; if (failed() || !JS_CHECK_STACK_SIZE(js::GetNativeStackLimit(runtime), &stackDummy)) { fail(); return; } discoveryTime[v] = clock; lowLink[v] = clock; clock++; stack.infallibleAppend(v); onStack[v] = true; JSCompartment *comp = runtime->compartments[v]; for (WrapperMap::Enum e(comp->crossCompartmentWrappers); !e.empty(); e.popFront()) { if (e.front().key.kind == CrossCompartmentKey::StringWrapper) continue; Cell *other = e.front().key.wrapped; if (other->isMarked(BLACK) && !other->isMarked(GRAY)) continue; Node w = other->compartment()->index; if (discoveryTime[w] == Undefined) { processNode(w); lowLink[v] = Min(lowLink[v], lowLink[w]); } else if (onStack[w]) { lowLink[v] = Min(lowLink[v], discoveryTime[w]); } } if (lowLink[v] == discoveryTime[v]) { Node w; do { w = stack.popCopy(); onStack[w] = false; scc[w] = nextSCC; } while (w != v); nextSCC++; } } void PartitionCompartments::partition() { for (Node n = 0; n < runtime->compartments.length(); n++) { if (discoveryTime[n] == Undefined) processNode(n); } } static void BeginSweepPhase(JSRuntime *rt) { /* * Sweep phase. * * Finalize as we sweep, outside of rt->gcLock but with rt->isHeapBusy() * true so that any attempt to allocate a GC-thing from a finalizer will * fail, rather than nest badly and leave the unmarked newborn to be swept. * * We first sweep atom state so we can use IsAboutToBeFinalized on * JSString held in a hashtable to check if the hashtable entry can be * freed. Note that even after the entry is freed, JSObject finalizers can * continue to access the corresponding JSString* assuming that they are * unique. This works since the atomization API must not be called during * the GC. */ gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_SWEEP); /* * Although there is a runtime-wide gcIsFull flag, it is set in * BeginMarkPhase. More compartments may have been created since then. */ bool isFull = true; for (CompartmentsIter c(rt); !c.done(); c.next()) { if (c->isCollecting()) { if (c != rt->atomsCompartment) c->setGCState(JSCompartment::Sweep); } else { isFull = false; } } JS_ASSERT_IF(isFull, rt->gcIsFull); #ifdef JS_THREADSAFE rt->gcSweepOnBackgroundThread = rt->hasContexts(); #endif /* Purge the ArenaLists before sweeping. */ for (GCCompartmentsIter c(rt); !c.done(); c.next()) { if (c->isGCSweeping()) c->arenas.purge(); } FreeOp fop(rt, rt->gcSweepOnBackgroundThread); { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_FINALIZE_START); if (rt->gcFinalizeCallback) rt->gcFinalizeCallback(&fop, JSFINALIZE_START, !isFull); } /* Finalize unreachable (key,value) pairs in all weak maps. */ WeakMapBase::sweepAll(&rt->gcMarker); rt->debugScopes->sweep(); /* Collect watch points associated with unreachable objects. */ WatchpointMap::sweepAll(rt); /* Detach unreachable debuggers and global objects from each other. */ Debugger::sweepAll(&fop); PartitionCompartments partition(rt); partition.partition(); { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_SWEEP_COMPARTMENTS); /* * Eliminate any garbage values from the VM stack that may have been * left by the JIT in between incremental GC slices. We need to do this * before discarding analysis data during JSCompartment::sweep. */ rt->stackSpace.markAndClobber(NULL); bool releaseTypes = ReleaseObservedTypes(rt); for (CompartmentsIter c(rt); !c.done(); c.next()) { gcstats::AutoSCC scc(rt->gcStats, partition.getSCC(c)); if (c->isCollecting()) c->sweep(&fop, releaseTypes); else c->sweepCrossCompartmentWrappers(); } } /* * Queue all GC things in all compartments for sweeping, either in the * foreground or on the background thread. * * Note that order is important here for the background case. * * Objects are finalized immediately but this may change in the future. */ for (GCCompartmentsIter c(rt); !c.done(); c.next()) { if (c->isGCSweeping()) { gcstats::AutoSCC scc(rt->gcStats, partition.getSCC(c)); c->arenas.queueObjectsForSweep(&fop); } } for (GCCompartmentsIter c(rt); !c.done(); c.next()) { if (c->isGCSweeping()) { gcstats::AutoSCC scc(rt->gcStats, partition.getSCC(c)); c->arenas.queueStringsForSweep(&fop); } } for (GCCompartmentsIter c(rt); !c.done(); c.next()) { if (c->isGCSweeping()) { gcstats::AutoSCC scc(rt->gcStats, partition.getSCC(c)); c->arenas.queueScriptsForSweep(&fop); } } for (GCCompartmentsIter c(rt); !c.done(); c.next()) { if (c->isGCSweeping()) { gcstats::AutoSCC scc(rt->gcStats, partition.getSCC(c)); c->arenas.queueShapesForSweep(&fop); } } rt->gcSweepPhase = 0; rt->gcSweepCompartmentIndex = 0; rt->gcSweepKindIndex = 0; { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_FINALIZE_END); if (rt->gcFinalizeCallback) rt->gcFinalizeCallback(&fop, JSFINALIZE_END, !isFull); } } bool ArenaLists::foregroundFinalize(FreeOp *fop, AllocKind thingKind, SliceBudget &sliceBudget) { if (!arenaListsToSweep[thingKind]) return true; ArenaList &dest = arenaLists[thingKind]; return FinalizeArenas(fop, &arenaListsToSweep[thingKind], dest, thingKind, sliceBudget); } static bool SweepPhase(JSRuntime *rt, SliceBudget &sliceBudget) { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_SWEEP); FreeOp fop(rt, rt->gcSweepOnBackgroundThread); for (; rt->gcSweepPhase < FinalizePhaseCount ; ++rt->gcSweepPhase) { gcstats::AutoPhase ap(rt->gcStats, FinalizePhaseStatsPhase[rt->gcSweepPhase]); ptrdiff_t len = rt->compartments.end() - rt->compartments.begin(); for (; rt->gcSweepCompartmentIndex < len ; ++rt->gcSweepCompartmentIndex) { JSCompartment *c = rt->compartments.begin()[rt->gcSweepCompartmentIndex]; if (c->wasGCStarted()) { while (rt->gcSweepKindIndex < FinalizePhaseLength[rt->gcSweepPhase]) { AllocKind kind = FinalizePhases[rt->gcSweepPhase][rt->gcSweepKindIndex]; if (!c->arenas.foregroundFinalize(&fop, kind, sliceBudget)) return false; ++rt->gcSweepKindIndex; } } rt->gcSweepKindIndex = 0; } rt->gcSweepCompartmentIndex = 0; } return true; } static void SweepAtomsCompartment(JSRuntime *rt) { JSCompartment *c = rt->atomsCompartment; JS_ASSERT(rt->gcMarker.isDrained()); JS_ASSERT(c->isGCMarking()); c->setGCState(JSCompartment::Sweep); c->arenas.purge(); { gcstats::AutoPhase ap2(rt->gcStats, gcstats::PHASE_SWEEP_ATOMS); SweepAtomState(rt); } FreeOp fop(rt, rt->gcSweepOnBackgroundThread); c->arenas.queueStringsForSweep(&fop); } static void EndSweepPhase(JSRuntime *rt, JSGCInvocationKind gckind, gcreason::Reason gcReason) { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_SWEEP); FreeOp fop(rt, rt->gcSweepOnBackgroundThread); JS_ASSERT(rt->gcMarker.isDrained()); rt->gcMarker.stop(); #ifdef DEBUG PropertyTree::dumpShapes(rt); #endif /* * Set up list of compartments for sweeping of background things. */ JS_ASSERT(!rt->gcSweepingCompartments); for (GCCompartmentsIter c(rt); !c.done(); c.next()) { c->gcNextCompartment = rt->gcSweepingCompartments; rt->gcSweepingCompartments = c; } { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_DESTROY); if (!rt->gcSweepOnBackgroundThread) { rt->freeLifoAlloc.freeAll(); SweepBackgroundThings(rt, false); } /* * Sweep script filenames after sweeping functions in the generic loop * above. In this way when a scripted function's finalizer destroys the * script and calls rt->destroyScriptHook, the hook can still access the * script's filename. See bug 323267. */ if (rt->gcIsFull) SweepScriptFilenames(rt); /* * This removes compartments from rt->compartment, so we do it last to make * sure we don't miss sweeping any compartments. */ SweepCompartments(&fop, gcReason); #ifndef JS_THREADSAFE /* * Destroy arenas after we finished the sweeping so finalizers can safely * use IsAboutToBeFinalized(). * This is done on the GCHelperThread if JS_THREADSAFE is defined. */ ExpireChunksAndArenas(rt, gckind == GC_SHRINK); #endif } /* * Reset the list of arenas marked as being allocated during sweep phase. */ while (ArenaHeader *arena = rt->gcArenasAllocatedDuringSweep) { rt->gcArenasAllocatedDuringSweep = arena->getNextAllocDuringSweep(); arena->unsetAllocDuringSweep(); } for (CompartmentsIter c(rt); !c.done(); c.next()) { c->setGCLastBytes(c->gcBytes, c->gcMallocAndFreeBytes, gckind); if (c->wasGCStarted()) c->setGCState(JSCompartment::NoGC); JS_ASSERT(!c->isCollecting()); JS_ASSERT(!c->wasGCStarted()); for (unsigned i = 0 ; i < FINALIZE_LIMIT ; ++i) { JS_ASSERT_IF(!IsBackgroundFinalized(AllocKind(i)) || !rt->gcSweepOnBackgroundThread, !c->arenas.arenaListsToSweep[i]); } } rt->gcLastGCTime = PRMJ_Now(); } /* * This class should be used by any code that needs to exclusive access to the * heap in order to trace through it... */ class AutoTraceSession { public: AutoTraceSession(JSRuntime *rt, JSRuntime::HeapState state = JSRuntime::Tracing); ~AutoTraceSession(); protected: JSRuntime *runtime; private: AutoTraceSession(const AutoTraceSession&) MOZ_DELETE; void operator=(const AutoTraceSession&) MOZ_DELETE; JSRuntime::HeapState prevState; }; /* ...while this class is to be used only for garbage collection. */ class AutoGCSession : AutoTraceSession { public: explicit AutoGCSession(JSRuntime *rt); ~AutoGCSession(); }; /* Start a new heap session. */ AutoTraceSession::AutoTraceSession(JSRuntime *rt, JSRuntime::HeapState heapState) : runtime(rt), prevState(rt->heapState) { JS_ASSERT(!rt->noGCOrAllocationCheck); JS_ASSERT(!rt->isHeapBusy()); JS_ASSERT(heapState == JSRuntime::Collecting || heapState == JSRuntime::Tracing); rt->heapState = heapState; } AutoTraceSession::~AutoTraceSession() { JS_ASSERT(runtime->isHeapBusy()); runtime->heapState = prevState; } AutoGCSession::AutoGCSession(JSRuntime *rt) : AutoTraceSession(rt, JSRuntime::Collecting) { runtime->gcIsNeeded = false; runtime->gcInterFrameGC = true; runtime->gcNumber++; } AutoGCSession::~AutoGCSession() { #ifndef JS_MORE_DETERMINISTIC runtime->gcNextFullGCTime = PRMJ_Now() + GC_IDLE_FULL_SPAN; #endif runtime->gcChunkAllocationSinceLastGC = false; #ifdef JS_GC_ZEAL /* Keeping these around after a GC is dangerous. */ runtime->gcSelectedForMarking.clearAndFree(); #endif /* Clear gcMallocBytes for all compartments */ for (CompartmentsIter c(runtime); !c.done(); c.next()) { c->resetGCMallocBytes(); c->unscheduleGC(); } runtime->resetGCMallocBytes(); } static void IncrementalCollectSlice(JSRuntime *rt, int64_t budget, gcreason::Reason gcReason, JSGCInvocationKind gcKind); static void ResetIncrementalGC(JSRuntime *rt, const char *reason) { if (rt->gcIncrementalState == NO_INCREMENTAL) return; /* Cancel and ongoing marking. */ bool wasMarking = false; for (GCCompartmentsIter c(rt); !c.done(); c.next()) { if (c->isGCMarking()) { c->setNeedsBarrier(false); c->setGCState(JSCompartment::NoGC); wasMarking = true; } } if (wasMarking) rt->gcMarker.reset(); if (rt->gcIncrementalState >= SWEEP) { /* If we had started sweeping then sweep to completion here. */ IncrementalCollectSlice(rt, SliceBudget::Unlimited, gcreason::RESET, GC_NORMAL); gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_WAIT_BACKGROUND_THREAD); rt->gcHelperThread.waitBackgroundSweepOrAllocEnd(); } else { JS_ASSERT(rt->gcIncrementalState == MARK); rt->gcIncrementalState = NO_INCREMENTAL; rt->gcMarker.stop(); JS_ASSERT(!rt->gcStrictCompartmentChecking); rt->gcStats.reset(reason); } #ifdef DEBUG for (GCCompartmentsIter c(rt); !c.done(); c.next()) { JS_ASSERT(c->isCollecting()); JS_ASSERT(!c->needsBarrier()); JS_ASSERT(!c->gcNextCompartment); for (unsigned i = 0 ; i < FINALIZE_LIMIT ; ++i) JS_ASSERT(!c->arenas.arenaListsToSweep[i]); } #endif } class AutoGCSlice { public: AutoGCSlice(JSRuntime *rt); ~AutoGCSlice(); private: JSRuntime *runtime; }; AutoGCSlice::AutoGCSlice(JSRuntime *rt) : runtime(rt) { /* * During incremental GC, the compartment's active flag determines whether * there are stack frames active for any of its scripts. Normally this flag * is set at the beginning of the mark phase. During incremental GC, we also * set it at the start of every phase. */ rt->stackSpace.markActiveCompartments(); for (GCCompartmentsIter c(rt); !c.done(); c.next()) { /* Clear this early so we don't do any write barriers during GC. */ if (c->isGCMarking()) { JS_ASSERT(c->needsBarrier()); c->setNeedsBarrier(false); } else { JS_ASSERT(!c->needsBarrier()); } } } AutoGCSlice::~AutoGCSlice() { for (GCCompartmentsIter c(runtime); !c.done(); c.next()) { if (c->isGCMarking()) { c->setNeedsBarrier(true); c->arenas.prepareForIncrementalGC(runtime); } else { JS_ASSERT(c->isGCSweeping()); c->setNeedsBarrier(false); } } } class AutoCopyFreeListToArenas { JSRuntime *rt; public: AutoCopyFreeListToArenas(JSRuntime *rt) : rt(rt) { for (CompartmentsIter c(rt); !c.done(); c.next()) c->arenas.copyFreeListsToArenas(); } ~AutoCopyFreeListToArenas() { for (CompartmentsIter c(rt); !c.done(); c.next()) c->arenas.clearFreeListsInArenas(); } }; static void PushZealSelectedObjects(JSRuntime *rt) { #ifdef JS_GC_ZEAL /* Push selected objects onto the mark stack and clear the list. */ for (JSObject **obj = rt->gcSelectedForMarking.begin(); obj != rt->gcSelectedForMarking.end(); obj++) { MarkObjectUnbarriered(&rt->gcMarker, obj, "selected obj"); } #endif } static bool DrainMarkStack(JSRuntime *rt, SliceBudget &sliceBudget) { /* Run a marking slice and return whether the stack is now empty. */ gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_MARK); return rt->gcMarker.drainMarkStack(sliceBudget); } static void IncrementalCollectSlice(JSRuntime *rt, int64_t budget, gcreason::Reason reason, JSGCInvocationKind gckind) { AutoCopyFreeListToArenas copy(rt); AutoGCSlice slice(rt); gc::State initialState = rt->gcIncrementalState; SliceBudget sliceBudget(budget); int zeal = 0; #ifdef JS_GC_ZEAL if (reason == gcreason::DEBUG_GC && budget != SliceBudget::Unlimited) { /* * Do the incremental collection type specified by zeal mode if the * collection was triggered by RunDebugGC() and incremental GC has not * been cancelled by ResetIncrementalGC. */ zeal = rt->gcZeal(); } #endif rt->gcIsIncremental = budget != SliceBudget::Unlimited; if (zeal == ZealIncrementalRootsThenFinish || zeal == ZealIncrementalMarkAllThenFinish) { /* * Yields between slices occurs at predetermined points in these * modes. sliceBudget is not used. */ sliceBudget.reset(); } if (rt->gcIncrementalState == NO_INCREMENTAL) { rt->gcIncrementalState = MARK_ROOTS; rt->gcLastMarkSlice = false; } switch (rt->gcIncrementalState) { case MARK_ROOTS: BeginMarkPhase(rt); PushZealSelectedObjects(rt); rt->gcIncrementalState = MARK; if (zeal == ZealIncrementalRootsThenFinish) break; /* fall through */ case MARK: { /* If we needed delayed marking for gray roots, then collect until done. */ if (!rt->gcMarker.hasBufferedGrayRoots()) sliceBudget.reset(); bool finished = DrainMarkStack(rt, sliceBudget); if (!finished) break; JS_ASSERT(rt->gcMarker.isDrained()); if (!rt->gcLastMarkSlice && ((initialState == MARK && budget != SliceBudget::Unlimited) || zeal == ZealIncrementalMarkAllThenFinish)) { /* * Yield with the aim of starting the sweep in the next * slice. We will need to mark anything new on the stack * when we resume, so we stay in MARK state. */ rt->gcLastMarkSlice = true; break; } EndMarkPhase(rt); rt->gcIncrementalState = SWEEP; /* * This runs to completion, but we don't continue if the budget is * now exhasted. */ BeginSweepPhase(rt); if (sliceBudget.isOverBudget()) break; /* * Always yield here when running in incremental multi-slice zeal * mode, so RunDebugGC can reset the slice buget. */ if (budget != SliceBudget::Unlimited && zeal == ZealIncrementalMultipleSlices) break; /* fall through */ } case SWEEP: { bool finished = SweepPhase(rt, sliceBudget); if (!finished) break; rt->gcIncrementalState = SWEEP_END; if (rt->gcIsIncremental) break; } case SWEEP_END: if (rt->atomsCompartment->isGCMarking()) { bool finished = DrainMarkStack(rt, sliceBudget); if (!finished) break; SweepAtomsCompartment(rt); if (rt->gcIsIncremental) break; } EndSweepPhase(rt, gckind, reason); if (rt->gcSweepOnBackgroundThread) rt->gcHelperThread.startBackgroundSweep(gckind == GC_SHRINK); rt->gcIncrementalState = NO_INCREMENTAL; break; default: JS_ASSERT(false); } } class IncrementalSafety { const char *reason_; IncrementalSafety(const char *reason) : reason_(reason) {} public: static IncrementalSafety Safe() { return IncrementalSafety(NULL); } static IncrementalSafety Unsafe(const char *reason) { return IncrementalSafety(reason); } typedef void (IncrementalSafety::* ConvertibleToBool)(); void nonNull() {} operator ConvertibleToBool() const { return reason_ == NULL ? &IncrementalSafety::nonNull : 0; } const char *reason() { JS_ASSERT(reason_); return reason_; } }; static IncrementalSafety IsIncrementalGCSafe(JSRuntime *rt) { if (rt->gcKeepAtoms) return IncrementalSafety::Unsafe("gcKeepAtoms set"); for (CompartmentsIter c(rt); !c.done(); c.next()) { if (c->activeAnalysis) return IncrementalSafety::Unsafe("activeAnalysis set"); } if (!rt->gcIncrementalEnabled) return IncrementalSafety::Unsafe("incremental permanently disabled"); return IncrementalSafety::Safe(); } static void BudgetIncrementalGC(JSRuntime *rt, int64_t *budget) { IncrementalSafety safe = IsIncrementalGCSafe(rt); if (!safe) { ResetIncrementalGC(rt, safe.reason()); *budget = SliceBudget::Unlimited; rt->gcStats.nonincremental(safe.reason()); return; } if (rt->gcMode != JSGC_MODE_INCREMENTAL) { ResetIncrementalGC(rt, "GC mode change"); *budget = SliceBudget::Unlimited; rt->gcStats.nonincremental("GC mode"); return; } if (rt->isTooMuchMalloc()) { *budget = SliceBudget::Unlimited; rt->gcStats.nonincremental("malloc bytes trigger"); } bool reset = false; for (CompartmentsIter c(rt); !c.done(); c.next()) { if (c->gcBytes >= c->gcTriggerBytes) { *budget = SliceBudget::Unlimited; rt->gcStats.nonincremental("allocation trigger"); } if (c->isTooMuchMalloc()) { *budget = SliceBudget::Unlimited; rt->gcStats.nonincremental("malloc bytes trigger"); } if (rt->gcIncrementalState != NO_INCREMENTAL && c->isGCScheduled() != c->wasGCStarted()) { reset = true; } } if (reset) ResetIncrementalGC(rt, "compartment change"); } /* * GC, repeatedly if necessary, until we think we have not created any new * garbage. We disable inlining to ensure that the bottom of the stack with * possible GC roots recorded in MarkRuntime excludes any pointers we use during * the marking implementation. */ static JS_NEVER_INLINE void GCCycle(JSRuntime *rt, bool incremental, int64_t budget, JSGCInvocationKind gckind, gcreason::Reason reason) { #ifdef DEBUG for (CompartmentsIter c(rt); !c.done(); c.next()) JS_ASSERT_IF(rt->gcMode == JSGC_MODE_GLOBAL, c->isGCScheduled()); #endif /* Recursive GC is no-op. */ if (rt->isHeapBusy()) return; /* Don't GC if we are reporting an OOM. */ if (rt->inOOMReport) return; AutoGCSession gcsession(rt); /* * As we about to purge caches and clear the mark bits we must wait for * any background finalization to finish. We must also wait for the * background allocation to finish so we can avoid taking the GC lock * when manipulating the chunks during the GC. */ { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_WAIT_BACKGROUND_THREAD); rt->gcHelperThread.waitBackgroundSweepOrAllocEnd(); } { if (!incremental) { /* If non-incremental GC was requested, reset incremental GC. */ ResetIncrementalGC(rt, "requested"); rt->gcStats.nonincremental("requested"); budget = SliceBudget::Unlimited; } else { BudgetIncrementalGC(rt, &budget); } IncrementalCollectSlice(rt, budget, reason, gckind); } } #ifdef JS_GC_ZEAL static bool IsDeterministicGCReason(gcreason::Reason reason) { if (reason > gcreason::DEBUG_GC && reason != gcreason::CC_FORCED) return false; if (reason == gcreason::MAYBEGC) return false; return true; } #endif static bool ShouldCleanUpEverything(JSRuntime *rt, gcreason::Reason reason) { // During shutdown, we must clean everything up, for the sake of leak // detection. When a runtime has no contexts, or we're doing a GC before a // shutdown CC, those are strong indications that we're shutting down. // // DEBUG_MODE_GC indicates we're discarding code because the debug mode // has changed; debug mode affects the results of bytecode analysis, so // we need to clear everything away. return !rt->hasContexts() || reason == gcreason::SHUTDOWN_CC || reason == gcreason::DEBUG_MODE_GC; } static void Collect(JSRuntime *rt, bool incremental, int64_t budget, JSGCInvocationKind gckind, gcreason::Reason reason) { JS_AbortIfWrongThread(rt); ContextIter cx(rt); if (!cx.done()) MaybeCheckStackRoots(cx); #ifdef JS_GC_ZEAL if (rt->gcDeterministicOnly && !IsDeterministicGCReason(reason)) return; #endif JS_ASSERT_IF(!incremental || budget != SliceBudget::Unlimited, JSGC_INCREMENTAL); #ifdef JS_GC_ZEAL bool isShutdown = reason == gcreason::SHUTDOWN_CC || !rt->hasContexts(); struct AutoVerifyBarriers { JSRuntime *runtime; bool restartPreVerifier; bool restartPostVerifier; AutoVerifyBarriers(JSRuntime *rt, bool isShutdown) : runtime(rt) { restartPreVerifier = !isShutdown && rt->gcVerifyPreData; restartPostVerifier = !isShutdown && rt->gcVerifyPostData; if (rt->gcVerifyPreData) EndVerifyPreBarriers(rt); if (rt->gcVerifyPostData) EndVerifyPostBarriers(rt); } ~AutoVerifyBarriers() { if (restartPreVerifier) StartVerifyPreBarriers(runtime); if (restartPostVerifier) StartVerifyPostBarriers(runtime); } } av(rt, isShutdown); #endif RecordNativeStackTopForGC(rt); int compartmentCount = 0; int collectedCount = 0; for (CompartmentsIter c(rt); !c.done(); c.next()) { if (rt->gcMode == JSGC_MODE_GLOBAL) c->scheduleGC(); /* This is a heuristic to avoid resets. */ if (rt->gcIncrementalState != NO_INCREMENTAL && c->needsBarrier()) c->scheduleGC(); compartmentCount++; if (c->isGCScheduled()) collectedCount++; } rt->gcShouldCleanUpEverything = ShouldCleanUpEverything(rt, reason); gcstats::AutoGCSlice agc(rt->gcStats, collectedCount, compartmentCount, reason); do { /* * Let the API user decide to defer a GC if it wants to (unless this * is the last context). Invoke the callback regardless. */ if (rt->gcIncrementalState == NO_INCREMENTAL) { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_GC_BEGIN); if (JSGCCallback callback = rt->gcCallback) callback(rt, JSGC_BEGIN); } rt->gcPoke = false; GCCycle(rt, incremental, budget, gckind, reason); if (rt->gcIncrementalState == NO_INCREMENTAL) { gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_GC_END); if (JSGCCallback callback = rt->gcCallback) callback(rt, JSGC_END); } /* Need to re-schedule all compartments for GC. */ if (rt->gcPoke && rt->gcShouldCleanUpEverything) PrepareForFullGC(rt); /* * On shutdown, iterate until finalizers or the JSGC_END callback * stop creating garbage. */ } while (rt->gcPoke && rt->gcShouldCleanUpEverything); } namespace js { void GC(JSRuntime *rt, JSGCInvocationKind gckind, gcreason::Reason reason) { Collect(rt, false, SliceBudget::Unlimited, gckind, reason); } void GCSlice(JSRuntime *rt, JSGCInvocationKind gckind, gcreason::Reason reason, int64_t millis) { int64_t sliceBudget; if (millis) sliceBudget = SliceBudget::TimeBudget(millis); else if (rt->gcHighFrequencyGC && rt->gcDynamicMarkSlice) sliceBudget = rt->gcSliceBudget * IGC_MARK_SLICE_MULTIPLIER; else sliceBudget = rt->gcSliceBudget; Collect(rt, true, sliceBudget, gckind, reason); } void GCFinalSlice(JSRuntime *rt, JSGCInvocationKind gckind, gcreason::Reason reason) { Collect(rt, true, SliceBudget::Unlimited, gckind, reason); } void GCDebugSlice(JSRuntime *rt, bool limit, int64_t objCount) { int64_t budget = limit ? SliceBudget::WorkBudget(objCount) : SliceBudget::Unlimited; PrepareForDebugGC(rt); Collect(rt, true, budget, GC_NORMAL, gcreason::API); } /* Schedule a full GC unless a compartment will already be collected. */ void PrepareForDebugGC(JSRuntime *rt) { for (CompartmentsIter c(rt); !c.done(); c.next()) { if (c->isGCScheduled()) return; } PrepareForFullGC(rt); } void ShrinkGCBuffers(JSRuntime *rt) { AutoLockGC lock(rt); JS_ASSERT(!rt->isHeapBusy()); #ifndef JS_THREADSAFE ExpireChunksAndArenas(rt, true); #else rt->gcHelperThread.startBackgroundShrink(); #endif } struct AutoFinishGC { AutoFinishGC(JSRuntime *rt) { if (rt->gcIncrementalState != NO_INCREMENTAL && !rt->gcVerifyPreData) { PrepareForIncrementalGC(rt); FinishIncrementalGC(rt, gcreason::API); } rt->gcHelperThread.waitBackgroundSweepEnd(); } }; struct AutoPrepareForTracing { AutoFinishGC finish; AutoTraceSession session; AutoCopyFreeListToArenas copy; AutoPrepareForTracing(JSRuntime *rt) : finish(rt), session(rt), copy(rt) {} }; void TraceRuntime(JSTracer *trc) { JS_ASSERT(!IS_GC_MARKING_TRACER(trc)); AutoPrepareForTracing prep(trc->runtime); RecordNativeStackTopForGC(trc->runtime); MarkRuntime(trc); } struct IterateArenaCallbackOp { JSRuntime *rt; void *data; IterateArenaCallback callback; JSGCTraceKind traceKind; size_t thingSize; IterateArenaCallbackOp(JSRuntime *rt, void *data, IterateArenaCallback callback, JSGCTraceKind traceKind, size_t thingSize) : rt(rt), data(data), callback(callback), traceKind(traceKind), thingSize(thingSize) {} void operator()(Arena *arena) { (*callback)(rt, data, arena, traceKind, thingSize); } }; struct IterateCellCallbackOp { JSRuntime *rt; void *data; IterateCellCallback callback; JSGCTraceKind traceKind; size_t thingSize; IterateCellCallbackOp(JSRuntime *rt, void *data, IterateCellCallback callback, JSGCTraceKind traceKind, size_t thingSize) : rt(rt), data(data), callback(callback), traceKind(traceKind), thingSize(thingSize) {} void operator()(Cell *cell) { (*callback)(rt, data, cell, traceKind, thingSize); } }; void IterateCompartmentsArenasCells(JSRuntime *rt, void *data, JSIterateCompartmentCallback compartmentCallback, IterateArenaCallback arenaCallback, IterateCellCallback cellCallback) { AutoPrepareForTracing prop(rt); for (CompartmentsIter c(rt); !c.done(); c.next()) { (*compartmentCallback)(rt, data, c); for (size_t thingKind = 0; thingKind != FINALIZE_LIMIT; thingKind++) { JSGCTraceKind traceKind = MapAllocToTraceKind(AllocKind(thingKind)); size_t thingSize = Arena::thingSize(AllocKind(thingKind)); IterateArenaCallbackOp arenaOp(rt, data, arenaCallback, traceKind, thingSize); IterateCellCallbackOp cellOp(rt, data, cellCallback, traceKind, thingSize); ForEachArenaAndCell(c, AllocKind(thingKind), arenaOp, cellOp); } } } void IterateChunks(JSRuntime *rt, void *data, IterateChunkCallback chunkCallback) { AutoPrepareForTracing prep(rt); for (js::GCChunkSet::Range r = rt->gcChunkSet.all(); !r.empty(); r.popFront()) chunkCallback(rt, data, r.front()); } void IterateCells(JSRuntime *rt, JSCompartment *compartment, AllocKind thingKind, void *data, IterateCellCallback cellCallback) { AutoPrepareForTracing prep(rt); JSGCTraceKind traceKind = MapAllocToTraceKind(thingKind); size_t thingSize = Arena::thingSize(thingKind); if (compartment) { for (CellIterUnderGC i(compartment, thingKind); !i.done(); i.next()) cellCallback(rt, data, i.getCell(), traceKind, thingSize); } else { for (CompartmentsIter c(rt); !c.done(); c.next()) { for (CellIterUnderGC i(c, thingKind); !i.done(); i.next()) cellCallback(rt, data, i.getCell(), traceKind, thingSize); } } } void IterateGrayObjects(JSCompartment *compartment, GCThingCallback *cellCallback, void *data) { JS_ASSERT(compartment); AutoPrepareForTracing prep(compartment->rt); for (size_t finalizeKind = 0; finalizeKind <= FINALIZE_OBJECT_LAST; finalizeKind++) { for (CellIterUnderGC i(compartment, AllocKind(finalizeKind)); !i.done(); i.next()) { Cell *cell = i.getCell(); if (cell->isMarked(GRAY)) cellCallback(data, cell); } } } namespace gc { JSCompartment * NewCompartment(JSContext *cx, JSPrincipals *principals) { JSRuntime *rt = cx->runtime; JS_AbortIfWrongThread(rt); JSCompartment *compartment = cx->new_(rt); if (compartment && compartment->init(cx)) { // Set up the principals. JS_SetCompartmentPrincipals(compartment, principals); compartment->setGCLastBytes(8192, 8192, GC_NORMAL); /* * Before reporting the OOM condition, |lock| needs to be cleaned up, * hence the scoping. */ { AutoLockGC lock(rt); if (rt->compartments.append(compartment)) return compartment; } js_ReportOutOfMemory(cx); } Foreground::delete_(compartment); return NULL; } void RunDebugGC(JSContext *cx) { #ifdef JS_GC_ZEAL JSRuntime *rt = cx->runtime; PrepareForDebugGC(cx->runtime); int type = rt->gcZeal(); if (type == ZealIncrementalRootsThenFinish || type == ZealIncrementalMarkAllThenFinish || type == ZealIncrementalMultipleSlices) { js::gc::State initialState = rt->gcIncrementalState; int64_t budget; if (type == ZealIncrementalMultipleSlices) { /* * Start with a small slice limit and double it every slice. This * ensure that we get multiple slices, and collection runs to * completion. */ if (initialState == NO_INCREMENTAL) rt->gcIncrementalLimit = rt->gcZealFrequency / 2; else rt->gcIncrementalLimit *= 2; budget = SliceBudget::WorkBudget(rt->gcIncrementalLimit); } else { // This triggers incremental GC but is actually ignored by IncrementalMarkSlice. budget = SliceBudget::WorkBudget(1); } Collect(rt, true, budget, GC_NORMAL, gcreason::DEBUG_GC); /* * For multi-slice zeal, reset the slice size when we get to the sweep * phase. */ if (type == ZealIncrementalMultipleSlices && initialState == MARK && rt->gcIncrementalState == SWEEP) { rt->gcIncrementalLimit = rt->gcZealFrequency / 2; } } else if (type == ZealPurgeAnalysisValue) { if (!cx->compartment->activeAnalysis) cx->compartment->types.maybePurgeAnalysis(cx, /* force = */ true); } else { Collect(rt, false, SliceBudget::Unlimited, GC_NORMAL, gcreason::DEBUG_GC); } #endif } void SetDeterministicGC(JSContext *cx, bool enabled) { #ifdef JS_GC_ZEAL JSRuntime *rt = cx->runtime; rt->gcDeterministicOnly = enabled; #endif } void SetValidateGC(JSContext *cx, bool enabled) { JSRuntime *rt = cx->runtime; rt->gcValidate = enabled; } } /* namespace gc */ } /* namespace js */ #if defined(DEBUG) && defined(JS_GC_ZEAL) && defined(JSGC_ROOT_ANALYSIS) && !defined(JS_THREADSAFE) static void CheckStackRoot(JSTracer *trc, uintptr_t *w) { /* Mark memory as defined for valgrind, as in MarkWordConservatively. */ #ifdef JS_VALGRIND VALGRIND_MAKE_MEM_DEFINED(&w, sizeof(w)); #endif ConservativeGCTest test = MarkIfGCThingWord(trc, *w); if (test == CGCT_VALID) { bool matched = false; JSRuntime *rt = trc->runtime; for (ContextIter cx(rt); !cx.done(); cx.next()) { for (unsigned i = 0; i < THING_ROOT_LIMIT; i++) { Rooted *rooter = cx->thingGCRooters[i]; while (rooter) { if (rooter->address() == static_cast(w)) matched = true; rooter = rooter->previous(); } } SkipRoot *skip = cx->skipGCRooters; while (skip) { if (skip->contains(reinterpret_cast(w), sizeof(w))) matched = true; skip = skip->previous(); } } if (!matched) { /* * Only poison the last byte in the word. It is easy to get * accidental collisions when a value that does not occupy a full * word is used to overwrite a now-dead GC thing pointer. In this * case we want to avoid damaging the smaller value. */ PoisonPtr(w); } } } static void CheckStackRootsRange(JSTracer *trc, uintptr_t *begin, uintptr_t *end) { JS_ASSERT(begin <= end); for (uintptr_t *i = begin; i != end; ++i) CheckStackRoot(trc, i); } static void EmptyMarkCallback(JSTracer *jstrc, void **thingp, JSGCTraceKind kind) {} void JS::CheckStackRoots(JSContext *cx) { JSRuntime *rt = cx->runtime; if (rt->gcZeal_ != ZealStackRootingSafeValue && rt->gcZeal_ != ZealStackRootingValue) return; if (rt->gcZeal_ == ZealStackRootingSafeValue && !rt->gcExactScanningEnabled) return; // If this assertion fails, it means that an AssertRootingUnnecessary was // placed around code that could trigger GC, and is therefore wrong. The // AssertRootingUnnecessary should be removed and the code it was guarding // should be modified to properly root any gcthings, and very possibly any // code calling that function should also be modified if it was improperly // assuming that GC could not happen at all within the called function. // (The latter may not apply if the AssertRootingUnnecessary only protected // a portion of a function, so the callers were already assuming that GC // could happen.) JS_ASSERT(!cx->rootingUnnecessary); // GCs can't happen when analysis/inference/compilation are active. if (cx->compartment->activeAnalysis) return; // Can switch to the atoms compartment during analysis. if (IsAtomsCompartment(cx->compartment)) { for (CompartmentsIter c(rt); !c.done(); c.next()) { if (c.get()->activeAnalysis) return; } } AutoCopyFreeListToArenas copy(rt); JSTracer checker; JS_TracerInit(&checker, rt, EmptyMarkCallback); ConservativeGCData *cgcd = &rt->conservativeGC; cgcd->recordStackTop(); JS_ASSERT(cgcd->hasStackToScan()); uintptr_t *stackMin, *stackEnd; #if JS_STACK_GROWTH_DIRECTION > 0 stackMin = rt->nativeStackBase; stackEnd = cgcd->nativeStackTop; #else stackMin = cgcd->nativeStackTop + 1; stackEnd = reinterpret_cast(rt->nativeStackBase); uintptr_t *&oldStackMin = cgcd->oldStackMin, *&oldStackEnd = cgcd->oldStackEnd; uintptr_t *&oldStackData = cgcd->oldStackData; uintptr_t &oldStackCapacity = cgcd->oldStackCapacity; /* * Adjust the stack to remove regions which have not changed since the * stack was last scanned, and update the last scanned state. */ if (stackEnd != oldStackEnd) { rt->free_(oldStackData); oldStackCapacity = rt->nativeStackQuota / sizeof(uintptr_t); oldStackData = (uintptr_t *) rt->malloc_(oldStackCapacity * sizeof(uintptr_t)); if (!oldStackData) { oldStackCapacity = 0; } else { uintptr_t *existing = stackEnd - 1, *copy = oldStackData; while (existing >= stackMin && size_t(copy - oldStackData) < oldStackCapacity) *copy++ = *existing--; oldStackEnd = stackEnd; oldStackMin = existing + 1; } } else { uintptr_t *existing = stackEnd - 1, *copy = oldStackData; while (existing >= stackMin && existing >= oldStackMin && *existing == *copy) { copy++; existing--; } stackEnd = existing + 1; while (existing >= stackMin && size_t(copy - oldStackData) < oldStackCapacity) *copy++ = *existing--; oldStackMin = existing + 1; } #endif JS_ASSERT(stackMin <= stackEnd); CheckStackRootsRange(&checker, stackMin, stackEnd); CheckStackRootsRange(&checker, cgcd->registerSnapshot.words, ArrayEnd(cgcd->registerSnapshot.words)); } #endif /* DEBUG && JS_GC_ZEAL && JSGC_ROOT_ANALYSIS && !JS_THREADSAFE */ namespace js { namespace gc { #ifdef JS_GC_ZEAL /* * Write barrier verification * * The next few functions are for write barrier verification. * * The VerifyBarriers function is a shorthand. It checks if a verification phase * is currently running. If not, it starts one. Otherwise, it ends the current * phase and starts a new one. * * The user can adjust the frequency of verifications, which causes * VerifyBarriers to be a no-op all but one out of N calls. However, if the * |always| parameter is true, it starts a new phase no matter what. * * Pre-Barrier Verifier: * When StartVerifyBarriers is called, a snapshot is taken of all objects in * the GC heap and saved in an explicit graph data structure. Later, * EndVerifyBarriers traverses the heap again. Any pointer values that were in * the snapshot and are no longer found must be marked; otherwise an assertion * triggers. Note that we must not GC in between starting and finishing a * verification phase. * * Post-Barrier Verifier: * When StartVerifyBarriers is called, we create a virtual "Nursery Set" which * future allocations are recorded in and turn on the StoreBuffer. Later, * EndVerifyBarriers traverses the heap and ensures that the set of cross- * generational pointers we find is a subset of the pointers recorded in our * StoreBuffer. */ struct EdgeValue { void *thing; JSGCTraceKind kind; char *label; }; struct VerifyNode { void *thing; JSGCTraceKind kind; uint32_t count; EdgeValue edges[1]; }; typedef HashMap, SystemAllocPolicy> NodeMap; /* * The verifier data structures are simple. The entire graph is stored in a * single block of memory. At the beginning is a VerifyNode for the root * node. It is followed by a sequence of EdgeValues--the exact number is given * in the node. After the edges come more nodes and their edges. * * The edgeptr and term fields are used to allocate out of the block of memory * for the graph. If we run out of memory (i.e., if edgeptr goes beyond term), * we just abandon the verification. * * The nodemap field is a hashtable that maps from the address of the GC thing * to the VerifyNode that represents it. */ struct VerifyPreTracer : JSTracer { /* The gcNumber when the verification began. */ uint64_t number; /* This counts up to gcZealFrequency to decide whether to verify. */ int count; /* This graph represents the initial GC "snapshot". */ VerifyNode *curnode; VerifyNode *root; char *edgeptr; char *term; NodeMap nodemap; VerifyPreTracer() : root(NULL) {} ~VerifyPreTracer() { js_free(root); } }; /* * This function builds up the heap snapshot by adding edges to the current * node. */ static void AccumulateEdge(JSTracer *jstrc, void **thingp, JSGCTraceKind kind) { VerifyPreTracer *trc = (VerifyPreTracer *)jstrc; trc->edgeptr += sizeof(EdgeValue); if (trc->edgeptr >= trc->term) { trc->edgeptr = trc->term; return; } VerifyNode *node = trc->curnode; uint32_t i = node->count; node->edges[i].thing = *thingp; node->edges[i].kind = kind; node->edges[i].label = trc->debugPrinter ? NULL : (char *)trc->debugPrintArg; node->count++; } static VerifyNode * MakeNode(VerifyPreTracer *trc, void *thing, JSGCTraceKind kind) { NodeMap::AddPtr p = trc->nodemap.lookupForAdd(thing); if (!p) { VerifyNode *node = (VerifyNode *)trc->edgeptr; trc->edgeptr += sizeof(VerifyNode) - sizeof(EdgeValue); if (trc->edgeptr >= trc->term) { trc->edgeptr = trc->term; return NULL; } node->thing = thing; node->count = 0; node->kind = kind; trc->nodemap.add(p, thing, node); return node; } return NULL; } static VerifyNode * NextNode(VerifyNode *node) { if (node->count == 0) return (VerifyNode *)((char *)node + sizeof(VerifyNode) - sizeof(EdgeValue)); else return (VerifyNode *)((char *)node + sizeof(VerifyNode) + sizeof(EdgeValue)*(node->count - 1)); } static void StartVerifyPreBarriers(JSRuntime *rt) { if (rt->gcVerifyPreData || rt->gcIncrementalState != NO_INCREMENTAL) return; AutoTraceSession session(rt); if (!IsIncrementalGCSafe(rt)) return; rt->gcHelperThread.waitBackgroundSweepOrAllocEnd(); AutoCopyFreeListToArenas copy(rt); RecordNativeStackTopForGC(rt); for (GCChunkSet::Range r(rt->gcChunkSet.all()); !r.empty(); r.popFront()) r.front()->bitmap.clear(); VerifyPreTracer *trc = new (js_malloc(sizeof(VerifyPreTracer))) VerifyPreTracer; rt->gcNumber++; trc->number = rt->gcNumber; trc->count = 0; JS_TracerInit(trc, rt, AccumulateEdge); const size_t size = 64 * 1024 * 1024; trc->root = (VerifyNode *)js_malloc(size); JS_ASSERT(trc->root); trc->edgeptr = (char *)trc->root; trc->term = trc->edgeptr + size; if (!trc->nodemap.init()) return; /* Create the root node. */ trc->curnode = MakeNode(trc, NULL, JSGCTraceKind(0)); /* We want MarkRuntime to save the roots to gcSavedRoots. */ rt->gcIncrementalState = MARK_ROOTS; /* Make all the roots be edges emanating from the root node. */ MarkRuntime(trc); VerifyNode *node = trc->curnode; if (trc->edgeptr == trc->term) goto oom; /* For each edge, make a node for it if one doesn't already exist. */ while ((char *)node < trc->edgeptr) { for (uint32_t i = 0; i < node->count; i++) { EdgeValue &e = node->edges[i]; VerifyNode *child = MakeNode(trc, e.thing, e.kind); if (child) { trc->curnode = child; JS_TraceChildren(trc, e.thing, e.kind); } if (trc->edgeptr == trc->term) goto oom; } node = NextNode(node); } rt->gcVerifyPreData = trc; rt->gcIncrementalState = MARK; rt->gcMarker.start(rt); for (CompartmentsIter c(rt); !c.done(); c.next()) { c->setNeedsBarrier(true); c->arenas.purge(); } return; oom: rt->gcIncrementalState = NO_INCREMENTAL; trc->~VerifyPreTracer(); js_free(trc); } static bool IsMarkedOrAllocated(Cell *cell) { return cell->isMarked() || cell->arenaHeader()->allocatedDuringIncremental; } const static uint32_t MAX_VERIFIER_EDGES = 1000; /* * This function is called by EndVerifyBarriers for every heap edge. If the edge * already existed in the original snapshot, we "cancel it out" by overwriting * it with NULL. EndVerifyBarriers later asserts that the remaining non-NULL * edges (i.e., the ones from the original snapshot that must have been * modified) must point to marked objects. */ static void CheckEdge(JSTracer *jstrc, void **thingp, JSGCTraceKind kind) { VerifyPreTracer *trc = (VerifyPreTracer *)jstrc; VerifyNode *node = trc->curnode; /* Avoid n^2 behavior. */ if (node->count > MAX_VERIFIER_EDGES) return; for (uint32_t i = 0; i < node->count; i++) { if (node->edges[i].thing == *thingp) { JS_ASSERT(node->edges[i].kind == kind); node->edges[i].thing = NULL; return; } } } static void AssertMarkedOrAllocated(const EdgeValue &edge) { if (!edge.thing || IsMarkedOrAllocated(static_cast(edge.thing))) return; char msgbuf[1024]; const char *label = edge.label ? edge.label : ""; JS_snprintf(msgbuf, sizeof(msgbuf), "[barrier verifier] Unmarked edge: %s", label); MOZ_ReportAssertionFailure(msgbuf, __FILE__, __LINE__); MOZ_CRASH(); } static void EndVerifyPreBarriers(JSRuntime *rt) { AutoTraceSession session(rt); rt->gcHelperThread.waitBackgroundSweepOrAllocEnd(); AutoCopyFreeListToArenas copy(rt); RecordNativeStackTopForGC(rt); VerifyPreTracer *trc = (VerifyPreTracer *)rt->gcVerifyPreData; if (!trc) return; bool compartmentCreated = false; /* We need to disable barriers before tracing, which may invoke barriers. */ for (CompartmentsIter c(rt); !c.done(); c.next()) { if (!c->needsBarrier()) compartmentCreated = true; c->setNeedsBarrier(false); } /* * We need to bump gcNumber so that the methodjit knows that jitcode has * been discarded. */ JS_ASSERT(trc->number == rt->gcNumber); rt->gcNumber++; rt->gcVerifyPreData = NULL; rt->gcIncrementalState = NO_INCREMENTAL; if (!compartmentCreated && IsIncrementalGCSafe(rt)) { JS_TracerInit(trc, rt, CheckEdge); /* Start after the roots. */ VerifyNode *node = NextNode(trc->root); while ((char *)node < trc->edgeptr) { trc->curnode = node; JS_TraceChildren(trc, node->thing, node->kind); if (node->count <= MAX_VERIFIER_EDGES) { for (uint32_t i = 0; i < node->count; i++) AssertMarkedOrAllocated(node->edges[i]); } node = NextNode(node); } } rt->gcMarker.reset(); rt->gcMarker.stop(); trc->~VerifyPreTracer(); js_free(trc); } /*** Post-Barrier Verifyier ***/ struct VerifyPostTracer : JSTracer { /* The gcNumber when the verification began. */ uint64_t number; /* This counts up to gcZealFrequency to decide whether to verify. */ int count; }; /* * The post-barrier verifier runs the full store buffer and a fake nursery when * running and when it stops, walks the full heap to ensure that all the * important edges were inserted into the storebuffer. */ static void StartVerifyPostBarriers(JSRuntime *rt) { #ifdef JSGC_GENERATIONAL if (!rt->gcExactScanningEnabled || rt->gcVerifyPostData || rt->gcIncrementalState != NO_INCREMENTAL) { return; } VerifyPostTracer *trc = new (js_malloc(sizeof(VerifyPostTracer))) VerifyPostTracer; rt->gcVerifyPostData = trc; rt->gcNumber++; trc->number = rt->gcNumber; trc->count = 0; for (CompartmentsIter c(rt); !c.done(); c.next()) { if (IsAtomsCompartment(c)) continue; if (!c->gcNursery.enable()) goto oom; if (!c->gcStoreBuffer.enable()) goto oom; } return; oom: trc->~VerifyPostTracer(); js_free(trc); rt->gcVerifyPostData = NULL; for (CompartmentsIter c(rt); !c.done(); c.next()) { c->gcNursery.disable(); c->gcStoreBuffer.disable(); } #endif } #ifdef JSGC_GENERATIONAL static void AssertStoreBufferContainsEdge(StoreBuffer *storebuf, void *loc, void *dst) { if (storebuf->containsEdgeAt(loc)) return; char msgbuf[1024]; JS_snprintf(msgbuf, sizeof(msgbuf), "[post-barrier verifier] Missing edge @ %p to %p", loc, dst); MOZ_ReportAssertionFailure(msgbuf, __FILE__, __LINE__); MOZ_CRASH(); } static void PostVerifierVisitEdge(JSTracer *jstrc, void **thingp, JSGCTraceKind kind) { VerifyPostTracer *trc = (VerifyPostTracer *)jstrc; Cell *dst = (Cell *)*thingp; JSCompartment *comp = dst->compartment(); /* * Note: watchpoint markAll will give us cross-compartment pointers into the * atoms compartment. */ if (IsAtomsCompartment(comp)) return; /* Filter out non cross-generational edges. */ if (!comp->gcNursery.isInside(dst)) return; /* * Note: since Value travels through the stack to get Cell**, we need to use * the annotated location in the tracer instead of the indirect location for * these edges. */ Cell *loc = (Cell *)(trc->realLocation != NULL ? trc->realLocation : thingp); AssertStoreBufferContainsEdge(&comp->gcStoreBuffer, loc, dst); } #endif static void EndVerifyPostBarriers(JSRuntime *rt) { #ifdef JSGC_GENERATIONAL AutoTraceSession session(rt); rt->gcHelperThread.waitBackgroundSweepOrAllocEnd(); AutoCopyFreeListToArenas copy(rt); RecordNativeStackTopForGC(rt); VerifyPostTracer *trc = (VerifyPostTracer *)rt->gcVerifyPostData; JS_TracerInit(trc, rt, PostVerifierVisitEdge); trc->count = 0; if (!rt->gcExactScanningEnabled) goto oom; for (CompartmentsIter c(rt); !c.done(); c.next()) { if (c->gcStoreBuffer.hasOverflowed()) continue; if (!c->gcStoreBuffer.coalesceForVerification()) goto oom; } /* Walk the heap. */ for (CompartmentsIter c(rt); !c.done(); c.next()) { if (!c->gcStoreBuffer.isEnabled() || c->gcStoreBuffer.hasOverflowed() || IsAtomsCompartment(c)) { continue; } if (c->watchpointMap) c->watchpointMap->markAll(trc); for (size_t kind = 0; kind < FINALIZE_LIMIT; ++kind) { for (CellIterUnderGC cells(c, AllocKind(kind)); !cells.done(); cells.next()) { Cell *src = cells.getCell(); if (!c->gcNursery.isInside(src)) JS_TraceChildren(trc, src, MapAllocToTraceKind(AllocKind(kind))); } } } oom: trc->~VerifyPostTracer(); js_free(trc); rt->gcVerifyPostData = NULL; for (CompartmentsIter c(rt); !c.done(); c.next()) { c->gcNursery.disable(); c->gcStoreBuffer.disable(); c->gcStoreBuffer.releaseVerificationData(); } #endif } /*** Barrier Verifier Scheduling ***/ static void VerifyPreBarriers(JSRuntime *rt) { if (rt->gcVerifyPreData) EndVerifyPreBarriers(rt); else StartVerifyPreBarriers(rt); } static void VerifyPostBarriers(JSRuntime *rt) { if (rt->gcVerifyPostData) EndVerifyPostBarriers(rt); else StartVerifyPostBarriers(rt); } void VerifyBarriers(JSRuntime *rt, VerifierType type) { if (type == PreBarrierVerifier) VerifyPreBarriers(rt); else VerifyPostBarriers(rt); } static void MaybeVerifyPreBarriers(JSRuntime *rt, bool always) { if (rt->gcZeal() != ZealVerifierPreValue) return; if (VerifyPreTracer *trc = (VerifyPreTracer *)rt->gcVerifyPreData) { if (++trc->count < rt->gcZealFrequency && !always) return; EndVerifyPreBarriers(rt); } StartVerifyPreBarriers(rt); } static void MaybeVerifyPostBarriers(JSRuntime *rt, bool always) { if (rt->gcZeal() != ZealVerifierPostValue) return; if (VerifyPostTracer *trc = (VerifyPostTracer *)rt->gcVerifyPostData) { if (++trc->count < rt->gcZealFrequency && !always) return; EndVerifyPostBarriers(rt); } StartVerifyPostBarriers(rt); } void MaybeVerifyBarriers(JSContext *cx, bool always) { MaybeVerifyPreBarriers(cx->runtime, always); MaybeVerifyPostBarriers(cx->runtime, always); } void FinishVerifier(JSRuntime *rt) { if (VerifyPreTracer *trc = (VerifyPreTracer *)rt->gcVerifyPreData) { trc->~VerifyPreTracer(); js_free(trc); } #ifdef JSGC_GENERATIONAL if (VerifyPostTracer *trc = (VerifyPostTracer *)rt->gcVerifyPostData) { trc->~VerifyPostTracer(); js_free(trc); for (CompartmentsIter c(rt); !c.done(); c.next()) { c->gcNursery.disable(); c->gcStoreBuffer.disable(); } } #endif } #endif /* JS_GC_ZEAL */ } /* namespace gc */ void ReleaseAllJITCode(FreeOp *fop) { #ifdef JS_METHODJIT for (CompartmentsIter c(fop->runtime()); !c.done(); c.next()) { mjit::ClearAllFrames(c); for (CellIter i(c, FINALIZE_SCRIPT); !i.done(); i.next()) { JSScript *script = i.get(); mjit::ReleaseScriptCode(fop, script); } } #endif } /* * There are three possible PCCount profiling states: * * 1. None: Neither scripts nor the runtime have count information. * 2. Profile: Active scripts have count information, the runtime does not. * 3. Query: Scripts do not have count information, the runtime does. * * When starting to profile scripts, counting begins immediately, with all JIT * code discarded and recompiled with counts as necessary. Active interpreter * frames will not begin profiling until they begin executing another script * (via a call or return). * * The below API functions manage transitions to new states, according * to the table below. * * Old State * ------------------------- * Function None Profile Query * -------- * StartPCCountProfiling Profile Profile Profile * StopPCCountProfiling None Query Query * PurgePCCounts None None None */ static void ReleaseScriptCounts(FreeOp *fop) { JSRuntime *rt = fop->runtime(); JS_ASSERT(rt->scriptAndCountsVector); ScriptAndCountsVector &vec = *rt->scriptAndCountsVector; for (size_t i = 0; i < vec.length(); i++) vec[i].scriptCounts.destroy(fop); fop->delete_(rt->scriptAndCountsVector); rt->scriptAndCountsVector = NULL; } JS_FRIEND_API(void) StartPCCountProfiling(JSContext *cx) { JSRuntime *rt = cx->runtime; if (rt->profilingScripts) return; if (rt->scriptAndCountsVector) ReleaseScriptCounts(rt->defaultFreeOp()); ReleaseAllJITCode(rt->defaultFreeOp()); rt->profilingScripts = true; } JS_FRIEND_API(void) StopPCCountProfiling(JSContext *cx) { JSRuntime *rt = cx->runtime; if (!rt->profilingScripts) return; JS_ASSERT(!rt->scriptAndCountsVector); ReleaseAllJITCode(rt->defaultFreeOp()); ScriptAndCountsVector *vec = cx->new_(SystemAllocPolicy()); if (!vec) return; for (CompartmentsIter c(rt); !c.done(); c.next()) { for (CellIter i(c, FINALIZE_SCRIPT); !i.done(); i.next()) { JSScript *script = i.get(); if (script->hasScriptCounts && script->types) { ScriptAndCounts sac; sac.script = script; sac.scriptCounts.set(script->releaseScriptCounts()); if (!vec->append(sac)) sac.scriptCounts.destroy(rt->defaultFreeOp()); } } } rt->profilingScripts = false; rt->scriptAndCountsVector = vec; } JS_FRIEND_API(void) PurgePCCounts(JSContext *cx) { JSRuntime *rt = cx->runtime; if (!rt->scriptAndCountsVector) return; JS_ASSERT(!rt->profilingScripts); ReleaseScriptCounts(rt->defaultFreeOp()); } } /* namespace js */ JS_PUBLIC_API(void) JS_IterateCompartments(JSRuntime *rt, void *data, JSIterateCompartmentCallback compartmentCallback) { JS_ASSERT(!rt->isHeapBusy()); AutoTraceSession session(rt); rt->gcHelperThread.waitBackgroundSweepOrAllocEnd(); for (CompartmentsIter c(rt); !c.done(); c.next()) (*compartmentCallback)(rt, data, c); } #if JS_HAS_XML_SUPPORT extern size_t sE4XObjectsCreated; JSXML * js_NewGCXML(JSContext *cx) { if (!cx->runningWithTrustedPrincipals()) ++sE4XObjectsCreated; return NewGCThing(cx, js::gc::FINALIZE_XML, sizeof(JSXML)); } #endif