Garbage collection

Design overview

SpiderMonkey has a mark-sweep garbage collection (GC) with an optionally enabled incremental marking mode. The mark phase uses a mark stack, as required by incremental marking. Sweeping of objects without finalizers is deferred to a background thread.

Work is underway to build a generational GC and a compacting GC.

Principal data structures

Cell

A Cell is the unit of memory that is allocated and collected by the GC, as used externally. In other words, from the point of view of the rest of the engine, the job of the GC is to allocate cells and automatically collect them.

Cell is the base class for all classes that are allocated by the GC, e.g., JSObject.

Allocation Kind

Cells are classified by allocation kind. The allocation kind determines the size of the object and the finalization behavior. Allocation kind is defined by enum AllocKind.

Arenas always hold objects of the same allocation kind. Thus, an arena holds objects all of the same size and finalization behavior.

Compartment

The JS heap is partitioned into compartments. Some key properties of compartments are:

• Every cell (JS heap object) belongs to exactly one compartment. (This is equivalent to saying that the heap is partitioned into compartments.)
• An object may not hold a direct pointer to an object in another compartment. Instead, it must store a wrapper for the other object. This allows compartments to be used for security checks: objects in the same compartment have the same access requirements, so no checks are needed, but checks may be done when traversing cross-compartment wrappers.
• The engine may GC a single compartment without GCing the others. The engine can also GC a set of compartments without GCing the rest. Cross-compartment wrappers are used as roots for single- and multi-compartment GCs.

Compartments are a fundamental cross-cutting concept in SpiderMonkey, especially for anything related to memory, including (or especially) GC. See also Compartments.

JSCompartment contains several important GC-related fields:

ArenaLists arenas

This structure records two lists of arenas for each allocation kind: a list of free arenas and a list of allocated arenas.

bool needsBarrier

True if a GC on this compartment needs to run incremental barriers, i.e., if this compartment is currently doing an incremental GC.

CompartmentGCState gcState

Whether this compartment is currently running a GC, and if not, whether it has scheduled a GC.

size_t gcBytes, gcTriggerBytes, gcMallocBytes, gcMaxMallocBytes

Accounting data used to schedule GCs.

WrapperMap crossCompartmentWrappers

Wrappers of objects in this compartment. The map key is the object, the value is the wrapper. The mapping is required so that if a wrapper is requested for the same object multiple times, the engine can return the same wrapper every time. The set of wrapped objects is also required for single- and multi-compartment (i.e., non-global) GCs.

Zone

Introduced in SpiderMonkey 24, a zone is a collection of compartments. Zones mainly serve as boundaries for GCs: the garbage collector collects at the level of a zone, not an individual compartment. Unlike compartments, zones have no special security properties. Some properties of zones are:

• Every compartment belongs to exactly one zone
• Every zone contains at least one compartment.
• Every JS heap object belongs to exactly one zone.
• Objects from the same zone but different compartments can share an arena.
• Objects from different zones cannot be stored in the same arena. 
• A zone remains alive as long as any JS heap objects in the zone are alive.

Chunk

A Chunk is the largest internal unit of memory allocation.

A chunk is 1MB and contains Arenas, padding, the mark bitmap (ChunkBitmap), a bitmap of decommitted arenas, and a chunk header (ChunkInfo).

The ChunkInfo contains a list of unallocated Arenas, starting at ChunkInfo::freeArenasHead and linked through ArenaHeader::next. The ChunkInfo also contains some basic stats, such as the number of free arenas.

TODO ChunkInfo next/prev

Arena

An Arena is an internal unit of memory allocation.

An Arena is one page (4096 bytes on almost all platforms) and contains an ArenaHeader, a few pad bytes, and then an array of aligned elements. All elements in an Arena have the same allocation kind and size.

Every Arena maintains a list of free spans, starting at ArenaHeader::firstFreeSpanOffets. The last cell in each free span (except the last one) holds a FreeSpan for the next free span.

Free Span

struct FreeSpan represents a contiguous sequence of free cells [first,last] within an Arena. FreeSpan contains functions to allocate from the free span.

Mark Bitmap

The mark bitmap is represented by ChunkBitmap.

The mark bitmap has one bit per GC cell. Thus, an object comprising multiple cells uses multiple bits in the bitmap.

Exact Stack Rooting API

This information has been split out into a separate article: Exact Stack Rooting.

Marking

TODO

Incremental marking

Incremental marking means being able to do a bit of marking work, then let the mutator (JavaScript program) run a bit, then do another bit of marking work. Thus, instead of one long pause for marking, the GC does a series of short pauses. The pauses can be set to be 10ms or less.

There is always a possibility that a long pause will be required. If the allocation rate is high during incremental GC, the engine may run out of memory before finishing the incremental GC. If so, the engine must immediately restart a full, non-incremental GC in order to reclaim some memory and continue execution.

Incremental write barrier

The problem that requires a write barrier

Incremental GC requires a write barrier for correctness.

TODO decent diagrams for basic problem

The basic problem is as follows (see Dictionary for color terms). Say object A is black and contains a pointer field. Let object B be white. Now let the incremental slice stop, so the mutator resumes. If the mutator stores B into A, so that A contains a pointer to B, and deletes all existing pointers to B, then:

• B is live, because A is black and contains a pointer to B.
• B will not be marked, because B is only reachable through A and we are all done with A, because A is black.
• Thus, B is live but will be collected.

The write barrier is a piece of code that runs just before a pointer store occurs and records just enough information to make sure that live objects don't get collected.

The SpiderMonkey incremental write barrier

SpiderMonkey uses a (relatively!) simple, common incremental write barrier called a snapshot-at-the-beginning allocate-black barrier.

To understand how this barrier works, first assume that we're going to do an incremental GC during which no new objects are allocated, just to keep things simple. How do we make sure the GC doesn't collect any live objects? One way would be to make sure that every object that was live at the beginning of the incremental GC gets marked. (This means if an object has all references to it dropped during this incremental GC, it will be collected on the next incremental GC.) This is called snapshot-at-the-beginning because it is conceptually equivalent to taking a snapshot of live objects at the beginning of the incremental GC and marking all those objects. No such snapshot is physically taken--doing so would require a full nonincremental mark!

The implementation of the snapshot-at-the-beginning barrier is simple. The barrier fires whenever the mutator is about to overwrite a location that holds a GC pointer. The barrier simply makes the pointed-to object black. The key observation is that the only way an object can get 'lost' and not marked is if all pointers to the object are overwritten. Thus, if whenever we're about to overwrite a pointer to an object we mark the object black first, then no objects can get 'lost'.

FIXME: It seems like making just the pointed-to object black wouldn't be good enough. What if there's another unmarked object hanging off of it? Seems like you need to add it to the mark stack too. Unless "makes the pointed-to object black" is meant to imply "recursively mark the pointed-to object black"?

Now let's handle allocations correctly too. A newly allocated object wasn't present at the beginning of the GC, so the snapshot-at-the-beginning barrier doesn't do it any good. But we do need to make sure the object doesn't get collected if it's live. This is easily done by simply marking new objects immediately upon allocation during an incremental GC, thus the name allocate-black.

The SpiderMonkey incremental read barrier

The textbook version of incremental GC has only a write barrier. SpiderMonkey also needs a read barrier for weak pointers (see Dictionary).

TODO finish

Implementation details

Write barriers have a runtime cost, so SpiderMonkey tries to skip them when an incremental GC cycle is not active. Each compartment has a flag needsBarrier() that indicates whether barriers are required.

For each type T such that fields of type T* need a write barrier, there is a functionT::writeBarrierPre(old). For example, fields of type JSObject* need a write barrier, so there is a function ObjectImpl::writeBarrierPre(ObjectImpl *old). (JSObject inherits from ObjectImpl.) If zone->needsBarrier(), then writeBarrierPre() marks old black. That's it.

The class HeapPtr<T> is provided to make it easy to invoke write barriers. A HeapPtr<T> encapsulates a T* and invokes the write barrier whenever assigned to. Thus, object fields of GC-pointer type should normally be defined as type HeapPtr<T>. The class HeapValue does the same thing for Value. HeapSlot (and the related class HeapSlotArray) is the same, but for object slots. HeapId is the same, but for jsid. TODO: why HeapValue vs HeapSlot?

Object private fields must be handled specially. The private field itself is opaque to the engine, but it may point to things that need to be marked, e.g., an array of JSObject pointers. In this example, if the private field is overwritten, the JSObject pointers could be 'lost', so a write barrier must be invoked to mark them. ObjectImpl::privateWriteBarrierPre takes care of this by invoking the JSObject's class trace hook before the private field is set.

Another detail is that write barriers can be skipped when initializing fields of newly allocated objects, because no pointer is being overwritten.

Sweeping

TODO

Generational GC

TODO

GC Statistics API

You can access the light statistics the GC keeps at runtime through the GC Statistics API.

Source files

jsgc{.h,inlines.h,.cpp}  Defines GC internal API functions, including entry points to trigger GC.

jsgcstats.{h,cpp}  Defines struct ConservativeGCStats for collecting stats about conservative stack scanning. TODO cut out when removed

gc/Barrier[-inl].h  Implements incremental and generational write barriers.

gc/Heap.h  Defines Chunk, ChunkInfo, ChunkBitmap, Arena, ArenaHeader, Cell, and FreeSpan structures that define the heart of the GC heap's structures.

gc/Marking.{h,cpp}  Defines all marking functions for the various garbage-collected things.

gc/Memory.{h,cpp}  Contains a few functions for mapping and unmapping pages, along with platform-specific implementations. The map/unmap functions are used by jsgc.cpp to allocate and release chunks. There are also functions to commit or decommit memory, i.e., tell the OS that certain pages are not being used and can be thrown away instead of paged to disk.

gc/Root.h  Defines classes for noting variables as GC roots.

gc/Statistics.{h,cpp}  Defines struct Statistics, which stores SpiderMonkey GC performance counters.

Dictionary of terms

TODO verify that color terms are accurate about SpiderMonkey implementation.

black  In common CS terminology, an object is black during the mark phase if it has been marked and its children are gray (have been queued for marking). An object is black after the mark phase if it has been marked. In SpiderMonkey, an object is black if its mark bit is set.

gray  In common CS terminology, an object is gray during the mark phase if it has been queued for marking. In SpiderMonkey, an object is gray if it is a child of an object in the mark stack and it is not black. Thus, gray objects are not represented explictly.

Handle  In our GC, a Handle is a pointer that has elsewhere been registered by a root.

root TODO: copy from above.

weak pointer  In common CS terminology, a weak pointer is one that doesn't keep the pointed-to value live for GC purposes. Typically, a weak pointer value has a get() method that returns a null pointer if the object has been GC'd. In Gecko/SpiderMonkey, a weak pointer is a pointer to an object that can be GC'd that is not marked through. Thus, there is no get() method and no protection against the pointed-to value getting GC'd--the programmer must ensure that the lifetime of the pointed-to object contains the lifetime of the weak pointer. TODO make sure this is correct.

white  In common CS terminology, an object is white during the mark phase if it has not been seen yet. An object is white after the mark phase if it has not been marked. In SpiderMonkey, an object is white if it is not gray or black; i.e., it is not black and it is not a child of an object in the mark stack.

Possible cleanups

MarkPagesInUse is a no-op on all platforms.

merge the stats files

ArenaLists::refillFreeLists seems badly named--it looks like it's trying to allocate a cell even if the arena free lists aren't full.