July 19, 2012
Cycle Collection

We don’t really have a comprehensive and current overview of the cycle collector and how to use it anywhere, so I wrote this.  This is probably part 1 of a multipart series, as I’ve only convered the simple cases here.

What?

The cycle collector is sort of like a garbage collector for C++.  It solves the fundamental problem of reference counting: cycles.  In a naive reference counting system, if A owns B and B owns A, neither A nor B will ever be freed.  Some structures in Gecko are inherently cyclic (e.g. a node tree) or can very easily be made cyclic by code beyond our control (e.g. most DOM objects can form cycles with expando properties added by content script).

The cycle collector operates on C++ objects that “opt-in” to cycle collection and all JS objects.  It runs a heavily modified version of Bacon and Rajan’s synchronous cycle collection algorithm. C++ objects opt-in by notifying the cycle collector when they may be garbage.  When the cycle collector wakes up it inspects the C++ objects (with help from the objects themselves) and builds a graph of the heap that participates in cycle collection.  It then finds the garbage cycles in this graph and breaks them, allowing the memory to be reclaimed.

Why?

The cycle collector makes developing Gecko much simpler at the cost of some runtime overhead to collect cycles.  Without a cycle collector, we would have to either a) manually break cycles when appropriate or b) use weak pointers to avoid ownership cycles.  These add significant complexity to modifying code and make avoiding memory leaks and use-after-free errors much harder. 

When?

C++ objects need to participate in cycle collection whenever they can be part of a reference cycle that is not guaranteed to be broken through other means.  C++ objects also need to participate in cycle collection if they hold direct references to objects that are managed by the JavaScript garbage collector (a jsval, JS::Value, JSObject*, etc.).

In practice, this means most DOM objects need to be cycle collected.

  • Does the object inherit from nsWrapperCache (directly or indirectly)?  If so, it must be cycle collected.
  • Does the object have direct references to JavaScript values (jsval, JS::Value, JSObject*, etc)?  If so, it must be cycle collected.  Note that interface pointers to interfaces implemented by JavaScript (e.g. nsIDOMEventListener) do *not* count here.
  • Does the object hold no strong references (e.g. it has no member variables of type nsCOMPtr or nsRefPtr, it has no arrays of those (nsTArray<nsCOMPtr>, nsTArray<nsRefPtr>, or nsCOMArray), no hashtables of them (nsInterfaceHashtable, nsRefPtrHashtable), and does not directly own any object that has these (via new/delete or nsAutoPtr))?  If so, it does not need to be cycle collected.
  • Is the object threadsafe (e.g. an nsRunnable, or something that uses the threadsafe AddRef/Release macros)?  Threadsafe objects cannot participate in cycle collection and must break ownership cycles manually.
  • Is the object a service or other long lived object?  Long lived objects should break ownership cycles manually.  Adding cycle collection may prevent shutdown leaks, but it will just replace that with a leak until shutdown, which is just as bad but doesn’t show up on our tools.
  • Does the object hold strong references to other things that are cycle collected?  If so, and the object does not have a well-defined lifetime (e.g. it can be accessed from Javascript) it must be cycle collected.
  • Does the object have strong references only to other things that are not cycle collected (e.g. interfaces from XPCOM, Necko, etc)?  If so, it probably does not need to be cycle collected.
  • Can the object be accessed from Javascript?  Then it probably needs to be cycle collected.

The last two are kind of vague on purpose.  Determining exactly when a class needs to participate in cycle collection is a bit tricky and involves some engineering judgement.  If you’re not sure, ask your reviewer or relevant peers/module owners.

How?

C++ objects participate in cycle collection by:

  1. Modifying their reference counting to use the cycle collector.
  2. Implementing a “cycle collection participant”, a set of functions that tell the cycle collector how to inspect the object.
  3. Modifying their QueryInterface implementation to return the participant when asked.

Like many things in Gecko, this involves lots of macros.

The reference counting is modified by replacing existing macros:

  • NS_DECL_ISUPPORTS becomes NS_DECL_CYCLE_COLLECTING_ISUPPORTS.
  • NS_IMPL_ADDREF becomes NS_IMPL_CYCLE_COLLECTING_ADDREF.
  • NS_IMPL_RELEASE becomes NS_IMPL_CYCLE_COLLECTING_RELEASE.

The cycle collection participant is a helper class that provides up to three functions:

  • A ‘Trace’ function is provided by participants that represent objects that use direct JavaScript object references.  It reports those JavaScript references to the cycle collector.
  • A ‘Traverse’ function is provided by all participants.  It reports strong C++ references to the cycle collector,
  • An ‘Unlink’ function is provided by (virtually) all participants.  It clears out both JavaScript and C++ references, breaking the cycle.

The cycle collection participant is implemented by placing one of the following macros in the header:

  • NS_DECL_CYCLE_COLLECTION_CLASS is the normal choice.  It is used for classes that only have C++ references to report.  This participant has Traverse and Unlink functions.
  • NS_DECL_CYCLE_COLLECTION_CLASS_AMBIGUOUS is a version of the previous macro for classes that multiply inherit from nsISupports.
  • NS_DECL_CYCLE_COLLECTION_SCRIPT_HOLDER_CLASS is used for classes that have JS references or a mix of JS and C++ references to report.  This participant has Trace, Traverse, and Unlink methods.
  • NS_DECL_CYCLE_COLLECTION_SCRIPT_HOLDER_CLASS_AMBIGUOUS is the ambiguous version of the previous macro.

And by doing one of the following in the cpp file:

  • For very simple classes, that don’t have JS references and only have nsCOMPtrs, you can use the NS_IMPL_CYCLE_COLLECTION_N macros, where N is the number of nsCOMPtrs the class has.
  • For classes that almost meet the above requirements, but inherit from nsWrapperCache, you can use the NS_IMPL_CYCLE_COLLECTION_WRAPPERCACHE_N macros, where N is the number of nsCOMPtrs the class has.
  • Otherwise, use the NS_IMPL_CYCLE_COLLECTION_CLASS macro and separate macros to implement the Traverse, Unlink, and Trace (if appropriate) methods.  To implement those, use the NS_IMPL_CYCLE_COLLECTION_[TRAVERSE|UNLINK|TRACE]_* macros to construct Traverse, Unlink, and Trace methods.

blog comments powered by Disqus