Global nsICycleCollector service
== Problem overview ==When multiple XPCOM objects form a cycle but are otherwise disconnected from any live roots (pointers not embedded in XPCOM objects that a thread can find transitively from its static and local variables, e.g. local nsCOMPtr 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.== Various 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.htmlWe 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 changesSome 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.