When you have GC pointers (pointers to JS objects, strings, etc.; anything stored directly in the GC heap), you need to handle them specially if they could ever be stored during a collection. I'll first describe what you need to do, then how to do it, and finally why and what happens if you get it wrong.
tracing - strong GC references must be traced so that the GC knows what to keep alive.
pre-write barriers aka delete barrier - if you overwrite a GC pointer, you'll need to let the GC know.
post-write barriers - after storing a GC pointer somewhere, you need to inform the GC of the new value (or more specifically, the address of the new value.)
read barriers - some GC pointers have different rules that make the above 3 mechanisms inadequate, and must be read-barriered instead (or in addition). In Gecko, these are GC pointers that participate in cycle collection (i.e., it is possible for a cycle to pass through these GC cells), or weak GC references. You need to inform the GC whenever you read one of these.
tracing - Tracing can be either unconditional or conditional. Unconditional tracing (or "rooting") is when you know that something is live for reasons other than it being pointed to by the GC heap. Conditional tracing is when you know that something is live because its containing GC thing is live. The two require different mechanisms.
- stack rooting - If a GC pointer of type T is on the stack (eg it's in a local variable), hold onto it with a Rooted, an RAII class that will add it to a list that will be unconditionally traced if and only if there is a GC within that Rooted's lifetime. If the type T is not a GC cell subtype, you must also define a trace() function; see "regular tracing", below. Rooteds must nest properly; if that is not doable (eg due to Maybe<> or similar), use PersistentRooted instead. It's a little slower, may be used on the heap as well as the stack, and is much riskier in terms of accidentally keeping too much alive. (PersistentRooted is unconditionally traced, so it will keep things alive as long as it is alive.)
When using Rooted, you will want to use Handle as a parameter type. Handle is basically T* (so Handle<JSObject*> is JSObject**), but wrapped in a C++ class so that the type system knows it points to a rooted pointer. Locals are Rooted, parameters are Handle, and return values are T (that are frequently stored immediately into a Rooted local.) Pointers to rooted values that you will want to change -- outparams, basically -- are MutableHandle.
- heap rooting - Register a callback with the GC to be invoked at the beginning of a collection. In this callback, trace everything you know to be live. (Typically, this will involve iterating through your own (non-GC-heap) data structures to trace the GC pointers found therein.) For simple cases, use PersistenRooted your data structures; no callback is needed, as the GC knows to trace all PersistentRooteds itself.
Various callbacks registration APIs are available depending on exactly which phase of GC requires your roots to be known:
- JS_SetGCCallback
- JS::SetGCSliceCallback
- JS::SetDoCycleCollectionCallback
- JS_AddExtraGCRootsTracer (and JS_RemoveExtraGCRootsTracer)
and for weak references
- JS_AddWeakPointerZonesCallback / JS_RemoveWeakPointerZonesCallback
- JS_AddWeakPointerCompartmentCallback / JS_RemoveWeakPointerCompartmentCallback
Use JS::TraceEdge to trace each GC pointer. Note that this takes a Heap* or TenuredHeap* because you nearly always need to barrier your GC pointers too. In the cases where this is not appropriate, you may need UnsafeTraceRoot or UnsafeTraceManuallyBarrieredEdge.
For weak pointers, call JS_UpdateWeakPointerAfterGC for Heap<JSObject*> or JS_UpdateWeakPointerAfterGCUnbarriered for JSObject** during your callback (that was registered with JS_AddWeakPointer{Zones,Compartment}Callback).
Store your GC pointers in a Heap to have the appropriate write barriers fire automatically. If you know that what you are storing will never be nursery-allocated, TenuredHeap will be a little faster because it can skip post-write barriers.
TODO read barriers TODO
TODO (GCVector, GCHashMap, GCHashSet)
The GC needs to know what is alive and what isn't, and figures that out by starting from a set of roots and tracing through everything reachable in the heap.
Pre-write barriers (deletion barriers) are for incremental GC. The GC needs to trace through the entire heap, but it's mutating as we traverse it. So we start from a set of roots and advance methodically, but if the graph is mutated so that we can't get to part of the live heap, we'll incorrectly discard the portion we can't get to.
But to be part of the live heap, you must have come from somewhere. The only possibilities are things that were allocated since we started the incremental collection, and things that have been read out of a different part of the heap. We handle the first by saying that everything you allocate since the start of the incremental GC is live. We handle the second by observing that things you read out of the heap will eventually get marked, unless the pre-existing edge to them is removed from the graph (probably by being overwritten with something else.) So whenever we remove an edge (i.e., write to a location in the heap), we mark it.
Post-write barriers (insertion barriers) are for generational GC. The GC wants to be able to throw out garbage in the nursery quickly, by only tracing live cells (we want nursery collection time to be proportional to the number of live cells and independent of the number of garbage cells). We can do this if we know all roots pointing into the nursery, as well as any pointers from the tenured heap into the nursery. The former is done simply by tracing all roots. The latter is the job of the insertion barrier: whenever you write into a tenured cell, we check if that cell is in the nursery, and if so add it to a "store buffer". When doing a minor (nursery) collection, we trace through all roots, followed by everything in the store buffer, recursing until we encounter a tenured pointer or run out of work.
The cycle collector (CC) needs to be able to detect garbage cycles that pass through the GC heap. After marking all live objects black, we do another traversal from "gray roots" to mark everything that is reachable and non-black as "CC-gray" (GC literature commonly uses "gray" to refer to the frontier between the unmarked and marked portions of the GC heap; this is different.) Then when looking for cycles, the CC will traverse only CC-gray objects in the GC heap.
But a problem occurs if a CC-gray object is read out of one place in the heap and inserted as the child of a live object, or perhaps stored into some C++ (non-GC) object that is reachable from a regular root. We do not barrier such writes, so the CC could trace through this object, find out that it is a member of a cycle that is the only thing holding the cycle pieces alive, and free it. To prevent this, we barrier all reads from within Gecko. If we read a CC-gray object, we un-gray it (recursively).
By definition, a weak reference should not hold a target live by itself. That means that we can't trace weak references when we encounter them during tracing. Instead, we append them to a list. After marking everything live we scan through the list to null out references to garbage.
But this also means that pre-barriers are inadequate to prevent incremental GC from missing edges due to graph mutation. Live cells will be marked either because they're reachable or because they were marked by a pre-barrier before being removed from the graph. But weak references aren't traced! So you could read one out and write it behind the frontier and there's no removal that could trigger an emergency marking as with strong refs and pre-barriers. So we barrier the read instead; if you ever read a weak reference in the middle of an ongoing incremental GC, then the target of the weak ref will be marked.
Rooted needs to know how to trace its contained T. For builtin types (eg JSObject*, JS::Value), it uses JS::MapTypeToRootKind to look up an appropriate root sublist to insert onto, and then at collection time it will perform the appropriate action for each sublist.
For anything else, JS::MapTypeToRootKind::kind will be set to JS::RootKind::Traceable, in which case the root lists will store a trace function alongside each rooted value. The trace function will be determined by the relevant specialization of JS::GCPolicy, specifically it will be JS::GCPolicy::trace. You can specialize this however you like for your own types, though usually you will want to stick with the default, which is to invoke a trace(JSTracer*) function on your struct.
Rooted is cheap. It is a singly-linked list append. Most of the time, you will not actually GC within its scope, so the total cost is one insertion and one deletion.
Pre-barriers are only needed when in the midst of an incremental collection, so most of the time they should be a single predictable branch.
Post-barriers store the addresses of locations containing GC pointers, and are given both the previous and new values, so if the previous value was already a nursery thing, they don't need to do anything. But they'll remove the store buffer entry (the store buffer is where these pointers to GC pointers are stored) if you transition from storing a nursery -> tenured pointer. Which all just means that the common case is looking up whether the old and new values are in the nursery or not, which is done by masking the address and loading in a footer. So two memory reads, probably far enough from the pointers that they won't be on the same cache line, plus a few branches.