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.