Garbage collection

  • Revision slug: SpiderMonkey/Internals/Garbage_collection
  • Revision title: Garbage collection
  • Revision id: 9388
  • Created:
  • Creator: Sheppy
  • Is current revision? No
  • Comment copy edit; have to stop because Firefox is crashy on me trying to edit some of this; 48 words added, 43 words removed

Revision Content

About this article: This is a rough draft on SpiderMonkey GC internals. It may be out of date or inaccurate.

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 an generational GC.

GC roots

In standard CS terminology, the root set is the set of GC pointers (pointers to a GC-controlled locations) values that are immediately accessible to the program. The mark phase begins with the root set. In an exact GC system, the root set is something like the set of live GC-pointer-typed stack and global variables. In a conservative GC system, the root set contains all values stored in machine registers or stack that are addresses within GC-controlled memory regions.

The common definition as given above leaves some ambiguity about exactly what the type of a root is. Because roots are used for marking traversal, it's natural to assume that a root is a GC-pointer value, e.g., a value of type JSObject *. In SpiderMonkey, "roots" are for more than just traversal, they are also updated if the GC moves the pointed-to object. Thus, a SpiderMonkey root is more like the location of a GC-pointer value, or perhaps a GC-pointer lvalue, e.g., a JSObject ** or JSObject *&, as you like it.

Conservative scanning

Warning: SpiderMonkey has a conservative stack scanner that works just as above, but it should not be relied upon in new code. We plan to move away from the conservative scanner to an explicit rooting system in order to better support generational GC.

Explicit rooting

SpiderMonkey also has an API for registering GC roots explicitly. Moving GC (generational GC and compacting GC) will require explicit rooting, because the GC needs to know exactly which values are GC pointers so that it can update those values, and only those values, when the object moves. In the explicit rooting system, making something a GC root:

  • Notifies the GC that during marking, it should mark the pointed-to object and everything reachable from it. Failure to do so would allow the GC to collect the object, leaving the pointer dangling.
  • Allows the GC to update the pointer value if the pointed-to object is moved. Failure to do so would allow the GC to move the object without updating the pointer, again leaving the pointer dangling.
Note: In order to get moving GC, we will have to move the engine and its browser client to the explicit rooting API. Once that's done, explicit rooting is required in order not to crash, as above. However, for now we are still using the conservative stack scanner. In the current configuration, explicit rooting is only used to verify that explicit rooting is being done correctly, in order to prepare for actually using explicit rooting.

Explicit rooting API

Any GC pointer must be rooted during any call that may trigger a GC. There is no explicit list of calls that can trigger a GC, so any fallible API call should be considered GC-triggering. Client code roots GC pointers using the rooting API defined in GC/Root.h. The rooting classes are all template <typename T>, where T is a GC-pointer type (e.g., JSObject *) or a type that can hold a GC pointer (e.g., Value), and they root the location of a T.

The rooting classes are as follows:

RootedVar
A RootedVar<T> is used exactly like a T, except that it is rooted. Thus, instead of unsafe JSObject *obj, you can safely write RootedVarObject obj. This is the preferred way to root local variables.
Root
A Root<T> roots the location of a T stack variable. This is useful if the variable needs to be rooted only on a rare path.
Handle
A Handle<T> represents a pointer to T that has elsewhere been registered as a root. This is primarily useful as a function parameter type. The Handle value can be assumed to be rooted, and no other explicit rooting is required. The class is set up so that a Handle can usually be constructed only from a Root or RootedVar. There is also a static constructor method fromMarkedLocation() that creates a Handle from a raw location. This is used to make Handles for scope chain objects, which aren't explicitly rooted themselves, but are always reachable from the implicit stack roots.
Note: Handle does not root objects but helps maintain rooting invariants.

Rooting verification mode

TODO

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 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 actually 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 overwitten. 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'.

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 compartment->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 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. TODO explain why this is.

Sweeping

TODO

Generational GC

TODO

GC statistics

SpiderMonkey tracks GCs and their performance per-context using struct Statistics.

The environment variable MOZ_GCTIMER controls text dumping of GC stats. MOZ_GCTIMER may be none, stderr, stdout, or a filename. If a filename is given, data is appended to that file.

The browser preference javascript.options.mem.log controls dumping of GC stats messages to the developer console.

Source files

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

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.

How much do we need Root? It seems like it should be used rarely.

Handle is pretty nonstandard terminology.

Revision Source

<div class="note"><strong>About this article: This is a rough draft on SpiderMonkey GC internals. It may be out of date or inaccurate.</strong></div>
<h2>Design overview</h2>
<p>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.</p>
<p>Work is underway to build an generational GC.</p>
<h2>GC roots</h2>
<p>In standard CS terminology, the <strong>root set</strong> is the set of GC pointers (pointers to a GC-controlled locations) values that are immediately accessible to the program. The mark phase begins with the root set. In an exact GC system, the root set is something like the set of live GC-pointer-typed stack and global variables. In a conservative GC system, the root set contains all values stored in machine registers or stack that are addresses within GC-controlled memory regions.</p>
<p>The common definition as given above leaves some ambiguity about exactly what the type of a root is. Because roots are used for marking traversal, it's natural to assume that a root is a GC-pointer value, e.g., a value of type JSObject *. In SpiderMonkey, "roots" are for more than just traversal, they are also updated if the GC moves the pointed-to object. Thus, a SpiderMonkey root is more like the location of a GC-pointer value, or perhaps a GC-pointer lvalue, e.g., a JSObject ** or JSObject *&amp;, as you like it.</p>
<h3>Conservative scanning</h3>
<div class="warning"><strong>Warning:</strong> SpiderMonkey has a conservative stack scanner that works just as above, but it should not be relied upon in new code. We plan to move away from the conservative scanner to an explicit rooting system in order to better support generational GC.</div>
<h3 class="warning">Explicit rooting</h3>
<p>SpiderMonkey also has an API for registering GC roots explicitly. Moving GC (generational GC and compacting GC) will require explicit rooting, because the GC needs to know exactly which values are GC pointers so that it can update those values, and only those values, when the object moves. In the explicit rooting system, making something a GC root:</p>
<ul> <li>Notifies the GC that during marking, it should mark the pointed-to object and everything reachable from it. Failure to do so would allow the GC to collect the object, leaving the pointer dangling.</li> <li>Allows the GC to update the pointer value if the pointed-to object is moved. Failure to do so would allow the GC to move the object without updating the pointer, again leaving the pointer dangling.</li>
</ul>
<div class="note"><strong>Note:</strong> In order to get moving GC, we will have to move the engine and its browser client to the explicit rooting API. Once that's done, explicit rooting is required in order not to crash, as above. However, for now we are still using the conservative stack scanner. In the current configuration, explicit rooting is only used to verify that explicit rooting is being done correctly, in order to prepare for actually using explicit rooting.</div>
<h4>Explicit rooting API</h4>
<p>Any GC pointer must be rooted during any call that may trigger a GC. There is no explicit list of calls that can trigger a GC, so any fallible API call should be considered GC-triggering. Client code roots GC pointers using the rooting API defined in <strong>GC/Root.h</strong>. The rooting classes are all<strong> template &lt;typename T&gt;</strong>, where T is a GC-pointer type (e.g., JSObject *) or a type that can hold a GC pointer (e.g., Value), and they root the <em>location </em>of a T.</p>
<p>The rooting classes are as follows:</p>
<dl> <dt><code>RootedVar</code></dt> <dd>A <code>RootedVar&lt;T&gt;</code> is used exactly like a <code>T</code>, except that it is rooted. Thus, instead of unsafe <code>JSObject *obj</code>, you can safely write <code>RootedVarObject obj</code>. This is the preferred way to root local variables.</dd>
</dl>
<dl> <dt><code><strong>Root</strong></code></dt> <dd>A <code>Root&lt;T&gt;</code> roots the location of a <code>T</code> stack variable. This is useful if the variable needs to be rooted only on a rare path.</dd> <dt><code>Handle</code></dt> <dd>A <code>Handle&lt;T&gt;</code> represents a pointer to <code>T</code> that has elsewhere been registered as a root. This is primarily useful as a function parameter type. The <code>Handle</code> value can be assumed to be rooted, and no other explicit rooting is required. The class is set up so that a <code>Handle</code> can usually be constructed only from a Root or <code>RootedVar</code>. There is also a static constructor method <code>fromMarkedLocation()</code> that creates a <code>Handle</code> from a raw location. This is used to make Handles for scope chain objects, which aren't explicitly rooted themselves, but are always reachable from the implicit stack roots.</dd>
</dl>
<div class="note"><strong>Note</strong>: <code>Handle</code> does not root objects but helps maintain rooting invariants.</div>
<h4>Rooting verification mode</h4>
<p>TODO</p>
<h2>Marking</h2>
<p>TODO</p>
<h2>Incremental marking</h2>
<p>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.</p>
<p>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.</p>
<h3>Incremental write barrier</h3>
<h4>The problem that requires a write barrier</h4>
<p>Incremental GC requires a write barrier for correctness.</p>
<p>TODO diagrams for basic problem</p>
<p>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:</p>
<ul> <li>B is live, because A is black and contains a pointer to B.</li> <li>B will not be marked, because B is only reachable through A and we are all done with A, because A is black.</li> <li>Thus, B is live but will be collected.</li>
</ul>
<p>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.</p>
<h4>The SpiderMonkey incremental write barrier</h4>
<p>SpiderMonkey uses a (relatively!) simple, common incremental write barrier called a <strong>snapshot-at-the-beginning allocate-black barrier</strong>.</p>
<p>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 <em>next </em>incremental GC.) This is called <strong>snapshot-at-the-beginning</strong> because it is <em>conceptually</em> 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 actually require a full nonincremental mark!</p>
<p style="margin-left: ;">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 overwitten. 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'.</p>
<p>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 <strong>allocate-black</strong>.</p>
<h4>The SpiderMonkey incremental read barrier</h4>
<p>The textbook version of incremental GC has only a write barrier. SpiderMonkey also needs a read barrier for weak pointers (see Dictionary).</p>
<p>TODO finish</p>
<h4>Implementation details</h4>
<p>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 <code>needsBarrier()</code> that indicates whether barriers are required.</p>
<p>For each type <code>T</code> such that fields of type <code>T*</code> need a write barrier, there is a function<code>T::writeBarrierPre(old)</code>. For example, fields of type <code>JSObject*</code> need a write barrier, so there is a function <code>ObjectImpl::writeBarrierPre(ObjectImpl *old)</code>. (<code>JSObject</code> inherits from <code>ObjectImpl</code>.) If <code><strong>compartment-&gt;needsBarrier()</strong></code>, then <code>writeBarrierPre()</code> marks <code>old </code>black. That's it.</p>
<p>The class <code>HeapPtr&lt;T&gt;</code> is provided to make it easy to invoke write barriers. A <code>HeapPtr&lt;T&gt;</code> encapsulates a <strong>T*</strong> and invokes the write barrier whenever assigned to. Thus, object fields of GC-pointer type should normally be defined as type HeapPtr&lt;T&gt;. The class <strong>HeapValue </strong>does the same thing for Value. <strong>HeapSlot </strong>(and the related class <strong>HeapSlotArray</strong>) is the same, but for object slots. <strong>HeapId </strong>is the same, but for jsid. TODO: why HeapValue vs HeapSlot?</p>
<p>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 a write barrier must be invoked to mark them. <strong>ObjectImpl::privateWriteBarrierPre</strong> takes care of this by invoking the JSObject's class trace hook before the private field is set.</p>
<p>Another detail is that write barriers can be skipped when initializing fields of newly allocated objects. TODO explain why this is.</p>
<h2>Sweeping</h2>
<p>TODO</p>
<h2>Generational GC</h2>
<p>TODO</p>
<h2>GC statistics</h2>
<p>SpiderMonkey tracks GCs and their performance per-context using <strong>struct Statistics</strong>.</p>
<p>The environment variable <strong>MOZ_GCTIMER </strong>controls text dumping of GC stats. <strong>MOZ_GCTIMER</strong> may be <strong>none</strong>, <strong>stderr</strong>, <strong>stdout</strong>, or a filename. If a filename is given, data is appended to that file.</p>
<p>The browser preference<strong> javascript.options.mem.log</strong> controls dumping of GC stats messages to the developer console.</p>
<h2>Source files</h2>
<p><strong>gc/Barrier[-inl].h</strong>  Implements incremental and generational write barriers.</p>
<p><strong>gc/Memory.{h,cpp}</strong>  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.</p>
<p><strong>gc/Root.h</strong>  Defines classes for noting variables as GC roots.</p>
<p><strong>gc/Statistics.{h,cpp}</strong>  Defines <strong>struct Statistics</strong>, which stores SpiderMonkey GC performance counters.</p>
<h2>Dictionary of terms</h2>
<p>TODO verify that color terms are accurate about SpiderMonkey implementation.</p>
<p><strong>black  </strong>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.</p>
<p><strong>gray  </strong>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.</p>
<p><strong>Handle</strong>  In our GC, a <strong>Handle </strong>is a pointer that has elsewhere been registered by a root.</p>
<p><strong>root </strong>TODO: copy from above.</p>
<p><strong>weak pointer </strong> 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.</p>
<p><strong>white  </strong>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.</p>
<h2>Possible cleanups</h2>
<p><strong>MarkPagesInUse </strong>is a no-op on all platforms.</p>
<p>How much do we need <strong>Root</strong>? It seems like it should be used rarely.</p>
<p><strong>Handle </strong>is pretty nonstandard terminology.</p>
Revert to this revision