283129 - mechanism for preserving JS properties on elements is bad for GC

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect, P1)

Description

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

The problem of how to deal with garbage collection in a system where:
 1. the GC runtime contains lazily-created wrappers for other data structures
    not participating in the GC,
 2. where those data structures are reachable from each other in a way that
    is reflected through the wrappers, and
 3. where the wrappers can carry additional information that is not in the
    wrapped object
is a difficult one.  XPConnect is such a system.  It creates wrappers around
native objects that do not participate in the JS GC and which are reachable from
each other outside of the knowledge of the JS engine (but through getters or
functions that are accessible to JS users) and it allows these wrappers to be
decorated with JS properties.  It is worth noting one very important use case
for our toolkit:  XBL, which uses JS properties on the bound element for storing
fields, methods, etc.

Our current solution to it is far from ideal, and takes two forms (I'll call
them A and B), each of which has a major problem:

Form A: For DOM nodes (this includes the XBL case), the instant a JS property is
set on the wrapper, we call nsDocument::AddReference on the element.  This roots
the wrapper for the lifetime of the document, which ensures that the wrapper is
not garbage-collected, even if the node is removed from the document and thus
unreachable by both the native and the JS data structures.

Problem with Form A: This effectively defeats the point of garbage collection,
and its implications on garbage collection are quite painful for things like
<tabbrowser>, which is a complex XBL binding whose members refer to large data
structures.

Form B: For everything else, we let users set properties on wrappers but do
nothing to protect those wrappers from garbage collection.

Problem with Form B: This means that we're leaving things wide open for users of
our APIs to write code that relies on setting JS properties but breaks when GC
happens at certain points.


The solution to problem B is simple, assuming it's not too big a break with API
compatibility:  for objects where we don't preserve JS properties set on
wrappers, we simply shouldn't allow those properties to be set in the first
place.  This at least protects users of our toolkit and web authors (for
example, those dealing with stylesheet objects) from dealing with
hard-to-reproduce GC-related bugs.


The solution to problem A is much harder, and that's what this bug is about.  I
don't see any way to solve this without incorporating knowledge about
reachability within the underlying data structures into the Mark phase of the
GC.  The only saving grace here is that we can optimize based on the assumption
that reachability in the is usually transitive.  In fact, if we only care about
DOM nodes, it's always transitive.

Thus we can optimize an algorithm that would require walking the entire graph by
picking a reference node for each strongly connected component (i.e., component
of the graph in which reachibility is transitive).  For DOM nodes, the obvious
choice is the result of walking up the |parentNode| chain (either a Document, a
DocumentFragment, or some other Node that's not attached to one of those).

Doing this would require that XPConnect expose or use (perhaps via nsIClassInfo)
an API for special mark operations.  (JS already does -- the mark member of
JSObjectOps.)  The table currently maintained by nsDocument::AddReference
(perhaps now in nsJSEnvironment?) would maintain a list of all the wrappers
associated with each reference node and a mark bit for that list (which could be
cleared for each new GC in DOMGCCallback).  When one of the wrappers was marked,
the special mark callback would use an API (via nsIClassInfo?) for mapping
wrapped object to reference node, map reference node to list of wrappers, and if
the mark bit on that list was unset, set the mark bit and mark all the wrappers.
 (And, if we were dealing with a set of objects where reachability was not
exactly transitive, it would also ask for the set of reachable strongly
connected components and mark those components as well.)

This is only a very rough sketch.  Is it crazy?  I think we do need to look at
solving this problem.

Comment 1

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to comment #0)
> The table currently maintained by nsDocument::AddReference
> (perhaps now in nsJSEnvironment?) would maintain a list of all the wrappers
> associated with each reference node and a mark bit for that list

Oops, it would only need to track the wrappers on which JS properties were set.

Comment 2

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Brendan pointed out that I wrote transitive where I meant symmetric.

Comment 3

[Benjamin Smedberg]

Let me rewrite the proposal to see if I understand it correctly:

XPCOM objects that wish to allow arbitrary JS properties set on them should
implement an interface (nsIXPCGCParticipant) which will be called during GC to
mark objects which are reachable through that XPCOM object. If an XPCOM object
does not implement this interface, code will not be allowed to set "custom" JS
properties on it.

1) What sort of rules will the nsIXPCGCParticipant.mark method have to prevent
xpconnect reentrancy?

2) What about XPCOM objects implemented in JS? Is it important to allow custom
properties on these? Will xpconnect implement nsIXPCGCParticipant for them?

Comment 4

[Mike Shaver (:shaver emeritus)]

What forms of "XPConnect reentrancy" do you think we need to prevent?  We should
probably make a list, if it's a concern.

Comment 5

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to comment #3)
> 2) What about XPCOM objects implemented in JS? Is it important to allow custom
> properties on these? Will xpconnect implement nsIXPCGCParticipant for them?

If they're double-wrapped, I think the answer is no.

Comment 6

[timeless]

so, dom extensibility comes to mind. currently i can't seem to add properties to
window.sidebar, but perhaps i should be able to, or perhaps for xmlhttprequest
or some other random dom extension that is implemented in js.

Comment 7

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

We'll need the asymmetric reachibility handling to fix bug 241518, I think.

Comment 8

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I've started poking at patching this (after some discussions with jst over the
past week).

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: sketch

This doesn't get to all of the callers of nsDocument::AddReference, so it
doesn't compile yet.  It also doesn't really leave a good way open to solving
the event listener issues (bug 241518).

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: testcase patch

A testcase is to apply this patch and see if the ++DOMWINDOW leaks caused by
this patch when opening and closing tabs are fixed by the GC changes.

Comment 11

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

This passes the testcase (attachment 178057 [details] [diff] [review]), and doesn't seem to crash in a
few minutes.

The change I made to provide a hook for XBL to nsDOMClassInfo (via
nsIScriptGlobalObject, which unfortunately has 3 implementations) is a bit
ugly.

I definitely want to put some printfs in and make sure that this is actually
doing what I think it is...

Comment 12

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: testcase for wrapper property preservation outside of document

Comment 13

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

With debugging printfs as well.

Comment 14

[Brendan Eich [:brendan]]

Comment on attachment 178059 [details] [diff] [review]
patch


>+void
>+nsDOMClassInfo::MarkPreservedWrappersFor(nsIDOMNode *aDOMNode, JSContext *cx,
>+                                         void *arg)
>+{
>+  // Magic value indicating we've had OOM earlier in this GC.
>+  if (sWrapperSCCTable.ops == (void*)1)
>+    return;
>+
>+  if (!sWrapperSCCTable.ops) {
>+    if (!nsDOMClassInfo::SortWrappers()) {
>+      sWrapperSCCTable.ops = (PLDHashTableOps*)1;
>+
>+      // We're out of memory, so just mark all the preserved wrappers.
>+      // It won't help the GC free up memory, but there's nothing better
>+      // to do.
>+      MarkAllWrappersData data;
>+      data.cx = cx;
>+      data.arg = arg;
>+      PL_DHashTableEnumerate(&sPreservedWrapperTable, MarkAllWrappers, &data);

Don't you want to return here?

>+    }

Hmm, or here -- or combine if (A) if (B) {...} into if (A && B) {...; return;}
?

>+  }
>+
>+  WrapperSCCEntry *entry = NS_STATIC_CAST(WrapperSCCEntry*,
>+    PL_DHashTableOperate(&sWrapperSCCTable, GetSCCRootFor(aDOMNode),
>+                         PL_DHASH_LOOKUP));

If you need a JSGC_MARK_BEGIN notification for DOMGCCallback, just let me know.
 It looks like laziness here means less code, though -- if so, the comment
could note that win and lack of requirement for JSGC_MARK_BEGIN?

/be

Comment 15

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

Better function names and comments.

Comment 16

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

Oops, didn't see brendan's comment until after submitting the previous patch. 
Missing return added, and nested ifs merged.

(In reply to comment #14)
> If you need a JSGC_MARK_BEGIN notification for DOMGCCallback, just let me
know.
>  It looks like laziness here means less code, though -- if so, the comment
> could note that win and lack of requirement for JSGC_MARK_BEGIN?

It's not less code, but it's not more either, so I don't think there's any
need.

Comment 17

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I'm wondering if these reachability tests miss some reachability via XBL APIs,
or perhaps something else.  (There's probably nothing we could do about C++ code
holding on to something for a long time, though.)

Comment 18

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

This uses a simpler hack to give XBL access to nsDOMClassInfo::PreserveWrapper
and fixes some missing ops checks on sPreservedWrapperTable.

Comment 19

[Johnny Stenback (:jst)]

Comment on attachment 178073 [details] [diff] [review]
patch

- In dom/public/nsIScriptGlobalObject.h:

+
+  virtual nsresult PreserveWrapper(nsIDOMNode *aDOMNode,
+				    nsIXPConnectWrappedNative *aWrapper) = 0;

As you suggested (in person) you might just want to not do this and have the
callers of this simply #include nsDOMClassInfo.h directly.

- In dom/src/base/nsDOMClassInfo.cpp:

+static nsIDOMNode* GetSCCRootFor(nsIDOMNode *aDOMNode)
+{
+  nsCOMPtr<nsIDOMNode> cur(aDOMNode), next;
+  for (;;) {
+    cur->GetParentNode(getter_AddRefs(next));
+    if (!next)
+      return cur;
+    next.swap(cur);
+  }
+}

This, and maybe some other code in this patch could be *faster* if you'd use
nsIContent in favor of nsIDOMNode to save cycles on refcounting etc, but you'll
probably pay in code size due to the fact that you'll need to deal with the
fact that documents don't implement nsIContent. That way you you wouldn't
always need to walk up the tree to find the root if the node is in a document
(GetCurrentDoc()), but since XUL is broken and lies about the current doc,
you'd need to special-case XUL here. May very well not be worth it...

+  // The JS engine doesn't have a notification for the beginning of
+  // the mark phase.  However, we can determine that the mark phase
+  // has begun by detecting the first mark and lazily call
+  // BeginGCMark.

Doesn't JSGC_BEGIN work as a notification of the mark phase beginning in this
case? Not that it matters since this works just as well.

- In nsNodeSH::AddProperty():

+  // XXX What happens if this fails?
+  return nsDOMClassInfo::PreserveWrapper(node, wrapper);

XPConnect will convert the return value into a JS exception, so this should be
fine.

- In content/base/public/nsIDocument.h:

-  virtual void AddReference(void *aKey, nsISupports *aReference) = 0;
-  virtual already_AddRefed<nsISupports> RemoveReference(void *aKey) = 0;

You should bump the IID in nsIDocument.h since you're changing the interface
here...

r=jst, thanks for fixing.

Comment 20

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to comment #19)
> Doesn't JSGC_BEGIN work as a notification of the mark phase beginning in this
> case? Not that it matters since this works just as well.

No, since the mark phase could begin multiple times (if finalization triggers
another GC).

Also, I think there are some XBL-related problems caused by GetSCCRootFor being
too simple, so I'll probably be posting a new patch once I figure that out...

Comment 21

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

This mainly contains a little more debugging code I used to convince myself
that there weren't problems with anonymous content.

Comment 22

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

OK, why don't I address jst's previous round of comments before requesting
reviews again? :-)

Comment 23

[Peter Van der Beken [:peterv]]

(In reply to comment #0)
> Thus we can optimize an algorithm that would require walking the entire graph by
> picking a reference node for each strongly connected component (i.e., component
> of the graph in which reachibility is transitive).  For DOM nodes, the obvious
> choice is the result of walking up the |parentNode| chain (either a Document, a
> DocumentFragment, or some other Node that's not attached to one of those).

Will this fail for attribute nodes? Their parentNode is null even when they're
attached to an element. It might not be a problem now because they're not
cached, but we're looking into changing that (see bug 235512).

Comment 24

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Yeah, it isn't a problem now (and in fact, given the current code, we're better
off leaving it since it reduces leaks), but it would be a problem once that's fixed.

Comment 25

[Johnny Stenback (:jst)]

Comment on attachment 178318 [details] [diff] [review]
patch

+#ifdef DEBUG_dbaron
+#define DEBUG_PRESERVE_WRAPPERS
+#endif

Me too! Please add DEBUG_jst to that this :)

r=jst

Comment 26

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Filed bug 288004 on the attributes issue (comment 23 and comment 24).

Comment 27

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I renamed |SortWrapper| to |ClassifyWrapper| since it's not really a sort. 
(Anyone have any better ideas?)

Comment 28

[Brendan Eich [:brendan]]

Comment on attachment 178318 [details] [diff] [review]
patch

I wonder whether we should expose PreserveWrapper on some interface that XBL
could use.

I'm also wondering whether http://www-2.cs.cmu.edu/~roc/HetGC.html sheds light.

sr=me.

/be

Comment 29

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I tried exposing PreserveWrapper on an interface (see comment 11), but it wasn't
worth it.

Fix checked in to trunk, 2005-03-29 15:26 -0800.

Comment 30

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I just filed bug 310620 on "Problem with Form B" from comment 0.

Comment 31

[Andrés G. Aragoneses]

This documentation page [1] still has a link to this bug as if it was a problem. Since it's now FIXED, can someone with expertise on this update that page? Thanks.

[1] https://developer.mozilla.org/en/Using_XPCOM_in_JavaScript_without_leaking