Prior Exploration

Table of Contents

I contributed to some file read/write APIs used by Mozilla Firefox a while back. My work did not involve making changes to their GCs' code, however, I had to familiarize myself with the workings of their GCs to understand and make a reasonable working contribution.

This page details some of what I understood and has some code samples as well. There are two GCs at work in the code I wrote, one of them was the GC of Spidermonkey, the JavaScript engine used. The other one was a GC written to find and break cycles in their C++ smart pointers.

1 Spidermonkey's GC

The write API I made was called from JavaScript and thus had JS Objects as the in- and out-parameters, which were collected by the GC, and thus the rooting had to be handled carefully.

The GC is

  • Mark and Sweep: on each collection, it goes through the objects and marks them for collection, and then collects them when done. An object is eligible for collection if nothing refers to that object – not another object, nothing on the stack/in global variables etc.
  • Exact: A conservative GC is one that scans the stack etc for anything that looks like a pointer, and then doesn't collect anything at the location marked. An exact collector makes it the user's responsibility to "register" anything they want to use with the GC, and everything else is collected.
  • Generational: it has been observed that most objects have small lifetimes, and the ones that make it past the initial few collections are likely to be long-lived. Thus, there are two sorts of GC operations: a fast GC operation on the small set of new objects which is also responsible for "tenuring" objects to the long-lived set, and the slower GC operation on the both sets.
  • Compacting: the GC occasionally moves objects (and changes pointers) from one location of the heap to another to reduce empty spaces in the heap.

The following discussion goes into some SpiderMonkey specifics.

Some terminology that I will use:

  • GC Thing: Anything that's been allocated memory by the GC
  • GC Thing Pointer/GC Pointer: A pointer type referring to some GC Thing

There is a set of GC Thing Pointers that are called the "roots" – this is where the GC start its scans. Any GC Thing pointed to by the roots – directly or indirectly – will not be collected, and everything else will be.

To make sure that an object is not collected, we need to either add its GC Pointer to an already reachable GC Thing, or add it to the set of roots. I used the second method, code of the following sort:

void methodName() {
  // ...
  JS::Rooted<JSObject*> obj(jsContext, nullptr);
  // ...

void someMethodCall(JS::Handle<JSObject*> arg) { }

This is said to be rooted on the C Stack. Anything rooted on the C Stack must be un-rooted in LIFO order, and using the Rooted<T> type does that for me automatically. The type can also be casted to Handle<T> implicitly, for use in methods that are on top of the stack of the method where the object that was first rooted, since it is faster than creating another root, and works okay with the LIFO restriction.

Further reading, code:

2 Cycle Collector

The code used smart pointers instead of raw pointers to make memory management easier. I used RefPtr<T> (similar to std::shared_ptr), and it takes care of adding and removing references automatically in most cases, calling T's destructor when there are no references left.

However, what's problematic is cyclic references, which need to be dealt with separately. T might also be a pointer to an object on the JavaScript heap, and C++-JS cycles might exist along with just C++ cycles.

There are various ways to break cycles, including making it the programmers' job to break cycles themselves, but in the Firefox code, a cycle collector is used. I have tried to explain the methods it uses below.

  • The refcount of an object is the number of edges to it from other objects with more than zero references. When the refcount is incremented, an object is never eligible for collection. When a refcount is decremented to zero, an object is already garbage. Thus, the only time an object is possibly in a cycle is when it is decremented to a number greater than zero. The object, and possibly other objects reachable from it may be garbage. Such an object is called a candidate root.
  • On finding such a candidate root, it is possible to start traversing all objects reachable from it, and decrement their refcounts by 1. Note that when the refcount of any object is decremented to zero, objects to which it has an edge also need to decrement their refcounts. Any object which now has a refcount of 0 is only referred to by the cycle, and is thus garbage.
  • Doing this for a large number of collections is wasteful, so candidate roots can be queued and then scanned only when there is pressing need. The roots might have their refcounts incremented/decremented to zero after being added to the queue, so they might even become ineligible to scan, saving us even more work.
  • Suppose the head of the queue is a cycle, but has one external pointer to it from the object at the tail of the queue. This will lead to the head being scanned twice before collection. This can be even worse when there's a pointer from tail to tail+1 to tail+2 … till the head. Instead, we can decrement the refcounts of each of the subgraphs individually, but scan for zeroes together. This means that we need to scan the entire graph once. In other words, we scan the transitive closure of the candidate roots.

The cycle collecter is roughly based on this last approach.

Further reading:

Author: Milind Luthra

Emacs 25.3.1 (Org mode 8.2.10)