Global nsICycleCollector service

Problem overview

When multiple XPCOM objects form a cycle but are otherwise disconnected from any live roots (pointers which a thread can find transitively from its static and local variables) it is considered a garbage cycle. Currently XPCOM cannot collect garbage cycles. This is a proposal to produce a collector for such cycles.

Common sources of garbage cycles in XPCOM appear to be cycles between javascript objects and browser objects, particularly DOM objects.

Variouis requirements

Any cycle-collecting algorithm must satisfy a few constraints imposed by the environment.

• Some objects will never be upgraded to participate in cycle collection. The mechanism must not break if it is applied to only a subset of the objects in the graph.
• XPCOM objects cannot generally be freed in any consistent fashion, such as by calling "operator delete". Objects should be made to "self destruct" by having all their incoming edges drop.
• Adding gratuitous new interfaces, vtables, or pointer state is probably too expensive.

A basic cycle collection algorithm

A "concurrent" cycle collection algorithm is presented here: http://citeseer.ist.psu.edu/paz03fly.html

We may wish to implement the simpler, non-concurrent ("stop the world") variant, which avoids using orange and red markers.

A sketch of an implementation in XPCOM

• nsICycleCollector.idl
• nsIClassInfo2.idl
• nsCycleCollector.cpp
• nsISupportsImpl.h changes

Some notes on the implementation:

• The implementation requires that each participating XPCOM class implement nsIClassInfo2. The two methods on this interface must be correct: it is better not to implement nsIClassInfo2 than to implement it wrong.
  • unlink(obj) should disconnect all outgoing XPCOM references held by obj.
  • traverse(obj,refcount,childcount,children) should return the refcount for obj, as well as the count and an array of outgoing XPCOM references from obj.
• An object implementing nsIClassInfo2 should also use the NS_IMPL_CYCLE_COLLECTING_* macros in the nsISupportsImpl header; these implementations hook the appropriate refcount operations to communicate with the global cycle collector.
• The implementation commandeers a single bit from the refcount stored in nsAutoRefCnt. This is not strictly necessary, but should cut down significantly on pointless traffic to the cycle collector.
• The global cycle collector service is kept as a singleton pointer in nsAutoRefCnt. This poses potential problems during shutdown. Advice on how to handle this safely would be appreciated.