XPCOM: Detecting Reference Cycles, or Switching to GC?
Brendan proposes to break XPCOM reference cycles using cycle-detection algorithms.
I must admit that I’m skeptical: in order to break reference cycles you need to know what strong references an object is holding: to do that you either have to ask the object (which must implement a special interface), or you have to have special knowledge about the internal form of an object (presumably provided through some specialization of classinfo).
IMHO it would be a better use of our time and energy to develop a mark-and-sweep garbage collection for XPCOM objects:
interface nsIGCThing
{
void mark();
void QueryInterface(in nsIIDRef uuid, [iid_is(uuid),retval] out nsQIResult result);
};
Note that this interface does not inherit from nsISupports! It is a parallel interface hierarchy built on a mark-and-sweep GC model.
Each class would have a per-class object to perform “sweeping”:
interface nsIGCParticipant : nsIGCThing {
void sweep();
};
XPCOM would implement the following service which would be used to initialize GC:
interface nsIGCService : nsISupports {
void GC();
void registerGCParticipant(nsIGCParticipant);
void unregisterGCParticipant(nsIGCParticipant);
void registerGCRoot(nsIGCThing);
void unregisterGCRoot(nsIGCThing);
};
A typical DOM object would continue to implement both the existing frozen nsISupports-based interfaces (for backwards compatibility with existing code) as well as parallel GC-based interfaces. The reference count and the mark-sweep indicator could be combined as a union on a single word: if the refcnt was above zero, the object is automatically a root and would be marked during mark phase of collection.
This system has the potential to greatly simplify a lot of our DOM and docshell code; it has the additional advantage that it can be completed incrementally. In addition, xpconnect wrappers (and hopefully javaxpcom and pyxpcom wrappers) can participate in a unified GC.
February 19th, 2006 at 6:42 am
Any cycle-collecting method is going to require an interface to enumerate the strong references from an object. Your nsIGCThing is just a particularly simple form of such an interface, which avoids exposing the iteration to the caller. If this were fleshed out into a real implementation, you might encounter stack overflows due to very long chains of object references. In that case you would likely have to make the interface more complicated, and you would be quite likely to end up exposing the outgoing strong references to the caller in some way. It might make more sense to just expose a general mechanism to enumerate the outgoing strong references.
Whatever we do, I think we really want to avoid adding a new fundamental interface; it would require an extra vtable pointer and associated thunks in a whole lot of objects. We’ll have to extend nsISupports.
February 19th, 2006 at 9:44 pm
Roc points out the stack overflow hazard with recursive marking — it’s real, we have had to work hard to defeat it in SpiderMonkey. Doing so means either a Deutsch-Schorr-Waite iterative spanning tree mark algorithm, which requires the ability to number all outgoing edges in each node, and tag one as reversed; or else switching from an implicit mark stack to a mark queue, but ideally without extra allocation overhead per queued GC-thing.
The plan I’ve discussed with Graydon is to extend nsIClassInfo (nsIClassInfo2, at this point) to include a static method (or two) that expose outgoing acyclic (and cyclic, if two) edges in the reference graph.
I don’t think general GC for XPCOM is a good idea. It breaks eager Release, which will break actual Release and operator delete implementations in our codebase. What’s more, it will increase average memory pressure, make data cache utilization worse, and put us on the slippery slope toward making the GC fancier over time. That means retrofitting such abstractions as a write barrier, which requires monitoring all writes of references into XPCOM objects. Let’s keep what is good about XPCOM (eager free), and fix what is broken (cycles leak without OOB protocols).
/be
February 19th, 2006 at 9:52 pm
Just in case readers are not up on nsIClassInfo: it’s a singleton per concrete XPCOM class, which can be found from any instance (no matter what its dynamic type) via QueryInterface. Thus it is an intentional violation of XPCOM’s identity rule: you can’t QI back to the instance from which you QI’d to nsIClassInfo. This impurity is calculated: it allows us to make static methods (in the C++ or Java sense) available from each instance without requiring another interface (meaning another mix-in vptr per instance), or else extending nsISupports (a major version compatibility break for XPCOM).
So the proposed nsIClassInfo2 getChildEdges and getCyclicEdges methods, or whatever we call them, would take an initial nsISupports self (a.k.a. |this|) parameter, to denote the instance being scanned.
/be
February 19th, 2006 at 10:45 pm
I think I have to agree with Robert; I don’t see the interface you’re proposing as anything much different from an expensive and opaque reference-enumerating scheme (which is incorrect anyways). We can do better.
Certainly avoiding stack overflow and new vtbl pointers is important. More important is getting the semantics correct. In your proposal, you suggest making all nonzero-refcount objects roots. This doesn’t work: it will register garbage cycles as roots, and not collect them. Collecting them is the whole point.
The Bacon paper Brendan linked to repeats some important observations.
First, that refcounts work fine for acyclic structures, and your only concern is finding garbage cycles.
Second, that garbage cycles can be detected by starting inside any potential garbage-cycle node, walking through the graph decrementing refcounts on reachable nodes, and checking to see if they’re still live after the scan. This reduces the scanned graph from the whole live heap to the subgraph you believe to be a potential garbage cycle.
Third, that garbage cycles only ever form on a particular refcount event: only the refcount transition from N+1 to N for nonzero N. So you can pick your candidates by hooking into that event: just instrument the refcounted object to post that particular event to the cycle collector, and run your scans from those candidates.
Fourth, if the cycle collector coalesces such events across a few “generations”, and object destruction clears them from the coalescing buffer, most potential garbage-cycle members will eliminate themselves.
February 19th, 2006 at 11:19 pm
Brendan: what is “eager release”? Do you just mean that the object deletes itself (or is at least allowed to delete itself) immediately when its last reference is released? xpconnect GC already gives most objects a lifecycle that depends on spidermonkey GC.
Graydon: what’s a “garbage cycle”? In my proposal the ordinary case would be for an object to have a refcount of zero: nsIGCThing-based interfaces are not refcounted. The only time an object would have a non-zero refcount is when it is held on a nsISupports-based interface (backwards compatibility interfaces).
Perhaps I don’t understand which problem we’re trying to solve with refcount-cycle-detection: are we trying to solve the common problem of XPCOM<->xpconnect interactions that form reference cycles, or some more limited problem? The only “pure XPCOM” reference-cycle leaks I’ve seen could and have been easily solved with proper design: the big problems that we have solved with layers of hacks have been the XPCOM<->xpconnect cycle problems; which I thought, perhaps naively, could be solved by making native DOM objects participate in meta-GC with JS objects.
February 20th, 2006 at 12:04 am
The pointers and objects in a program make a directed graph. General directed graphs can contain cycles. An object in the pointer/object graph is garbage if it can’t be reached from roots. When subgraphs of the pointer/object graph become garbage, we want to collect them.
Refcounting will collect garbage subgraphs which are acyclic. That leaves cyclic subgraphs — garbage cycles — which plain refcounting will not collect. Mark/sweep will collect all garbage, of course, but we already have a way to collect half the garbage, and are bound by backward-compatibility to continue supporting that technique (besides which, it has some decent locality and amortization properties). The problem being addressed is how to collect the other half (we don’t know how much it is by volume; it might be significantly more or less than half).
I did not understand that you were proposing to have GC-participating objects avoid refcounting altogether. It’s not clear to me whether this would work or not. It seems to me like it might work, but would only collect cycles which were entirely within the GC regime, which makes it equivalent to (only less efficient than) a collector which focuses on garbage cycle formation events.
A pure JS cycle is already detected and destroyed by the JS collector, which is precise mark/sweep. You are correct in thinking that the JS mark/sweep collector could be extended to collect through the XPCOM graph, viewing XPCOM as an opaque map from incoming to outgoing JSObject pointers. But that is not the only possible view. An XPCOM cycle collector can also see the entire JS engine as an opaque map from incoming to outgoing XPCOM pointers. When such a collector sees a garbage cycle in XPCOM objects — possibly including edges which pass through JS — it can delete the cyclic edges outside JS, unroot the xpconnect roots, and let the JS collector clean up its own garbage on its own time.
I believe this latter view is more likely compatible with multiple garbage collectors (Java, Python, etc.) for three reasons. First, each of them will prefer to collect their own internal objects. Second, the service requests they respond to are non-mutating and do not need to interface with any particular style of GC (copying, mark/sweep, refcount-hybrid). Third, the service requests they respond to will involve strictly less graph tracing than participating in a coordinated mark/sweep.
February 20th, 2006 at 2:46 pm
For just cycles through XPConnect, this sounds a lot like the nsIDOMGCParticipant interface dbaron introduced…
February 22nd, 2006 at 8:09 pm
Benjamin: by “eager release” I mean the same thing Graydon means by “(… it has some decent locality and amortization properties)”. Linus Torvalds has a well-known argument/flame against GC in the GCC list, for its “bad laziness” in terms of cache and memory overuse. That’s well-known and well-studied in the literature. Work such as Cliff Click’s stack-based GC with “escape analysis” is motivated entirely by the costs of leaving garbage uncollected, in the memory system, especially in the typical sliding window that the d-cache forms on the whole of the VM space.
We are not going to throw away XPCOM except for legacy nsISupports. That’s a rewrite, plus the cost of keeping the old stuff going. It is not necessary to avoid cycle-caused leaks.
BTW, “good design” is still hard to come by even in pure XPCOM programming. Yes, we should improve nsIObserver. And sure, our hard leaks now involve the JS GC and XPCOM objects forming cycles. But not all XPCOM objects will be subject to GC. Dbaron’s work on nsIDOMGCParticipant helps only for those XPCOM objects that are well-connected DOM objects. And there are potentially many places that would need to implement nsIDOMGCParticipant, even if we cared only about DOM objects.
Boris: that’s only good for cycles involving DOM strong components. Not all XPConnected objects are such DOM objects. But yeah, a generalization of dbaron’s work leads to the Bacon, et al., approach.
/be
February 22nd, 2006 at 8:14 pm
Graydon’s final paragraph is spot-on, and was prefigured long ago by roc’s http://www-2.cs.cmu.edu/~roc/HetGC.html. We’re building such a super-GC, because we are not .NET: we don’t have one GC and one VM supporting multiple programming languages, we have many VMs talking through an XPCOM “hub”.
GC is not something to dive into lightly. Besides the memory trade-offs, there are execution model and finalization protocol issues to sweat. For acyclic structures, and “well-designed” possibly cyclic ones where an OOB protocol helps break cycles, XPCOM is fine. Well, good enough. Er, worse is better!
/be