Last Comment Bug 653248 - WeakMap values reachable only from DOM are marked black
: WeakMap values reachable only from DOM are marked black
Status: RESOLVED FIXED
[MemShrink:P2] [bad leaks in new feat...
: mlk, testcase
Product: Core
Classification: Components
Component: DOM (show other bugs)
: Trunk
: All All
: -- normal (vote)
: mozilla11
Assigned To: Andrew McCreight [:mccr8]
:
: Andrew Overholt [:overholt]
Mentors:
Depends on: 667011 668855 685593 692884
Blocks: 326633 WeakMap mlk-fx6
  Show dependency treegraph
 
Reported: 2011-04-27 14:45 PDT by Jesse Ruderman
Modified: 2012-02-01 13:56 PST (History)
23 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---
-
-
-
-


Attachments
testcase (311 bytes, text/html)
2011-04-27 14:45 PDT, Jesse Ruderman
no flags Details
mark gray any weak references reachable from XPCOM (5.08 KB, patch)
2011-06-13 17:24 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
mark any weak references reachable from XPCOM gray, not black (5.21 KB, patch)
2011-06-14 19:37 PDT, Andrew McCreight [:mccr8]
gal: review+
Details | Diff | Splinter Review
mark any weak references reachable from XPCOM gray, not black (3.88 KB, patch)
2011-06-15 11:39 PDT, Andrew McCreight [:mccr8]
continuation: review+
Details | Diff | Splinter Review
In GC, separate JS_SetExtraGCRoots marking and grey-marking passes, so that WeakMap-like edges are properly traced in each pass. (10.60 KB, patch)
2011-07-07 15:36 PDT, Jim Blandy :jimb
no flags Details | Diff | Splinter Review
In GC, separate marking passes, so that WeakMap-like edges are properly traced in each pass. (12.11 KB, patch)
2011-07-07 19:10 PDT, Jim Blandy :jimb
no flags Details | Diff | Splinter Review
In GC, separate marking passes, so that WeakMap-like edges are properly traced in each pass. (12.92 KB, patch)
2011-07-09 19:02 PDT, Jim Blandy :jimb
no flags Details | Diff | Splinter Review
In GC, separate marking passes, so that WeakMap-like edges are properly traced in each pass. (12.56 KB, patch)
2011-07-11 16:12 PDT, Jim Blandy :jimb
no flags Details | Diff | Splinter Review
mark values reachable only from XPConnect roots gray (4.55 KB, patch)
2011-09-09 11:22 PDT, Andrew McCreight [:mccr8]
continuation: review+
Details | Diff | Splinter Review
mark values reachable only from XPConnect roots gray (3.86 KB, patch)
2011-10-10 13:57 PDT, Andrew McCreight [:mccr8]
wmccloskey: review+
Details | Diff | Splinter Review
mark values reachable only from XPConnect roots gray (3.34 KB, patch)
2011-10-10 17:29 PDT, Andrew McCreight [:mccr8]
wmccloskey: review+
Details | Diff | Splinter Review

Description Jesse Ruderman 2011-04-27 14:45:15 PDT
Created attachment 528712 [details]
testcase

Steps:
1. Run Firefox with leak logging (e.g. debug build + XPCOM_MEM_LEAK_LOG=2).
2. Load the testcase.
3. Close Firefox.

Result: leak 1 nsDocument and 2 nsGlobalWindow.

If I replace "setUserData" with "addEventListener", it still leaks.  But if I use an expando property of the div instead, it doesn't leak.
Comment 1 Andreas Gal :gal 2011-04-27 14:47:17 PDT
Great initiative Jesse. Thanks!
Comment 2 Kyle Huey [:khuey] (Exited; not receiving bugmail, email if necessary) 2011-05-15 20:28:31 PDT
Do we need to fix this before shipping WeakMaps?  It seems like an easy leak to hit if you can get it with addEventListener ...
Comment 3 Andreas Gal :gal 2011-05-15 20:48:16 PDT
There is a large number of ways to make the browser leak, this doesn't seem to be a particularly bad or dangerous way to do it. WeakMaps aren't being used much yet, so I don't think we have to fix this under pressure. I am comfortable shipping this as a first draft as is (cc'ing Brendan for 2nd opinion since I am personally invested).
Comment 4 Olli Pettay [:smaug] 2011-05-16 03:07:43 PDT
(In reply to comment #3)
> There is a large number of ways to make the browser leak,
Large number of known ways to make browser leak?
Really?
Comment 5 Jesse Ruderman 2011-05-16 04:13:59 PDT
This is the only ways I know to make the browser reproducibly leak windows+documents all the way through shutdown from content.  The other big fuzz leak bugs (about 20 of them) have been fixed.

This doesn't stop me from finding other leak bugs, just other leak bugs that involve WeakMap.
Comment 6 Jason Orendorff [:jorendorff] 2011-05-16 12:55:44 PDT
The leaking code is:

  var map = new WeakMap();
  var div = document.createElementNS("http://www.w3.org/1999/xhtml", "div");
  var key = {};
  div.setUserData("entrain", {m:map, k:key}, null);
  map.set(key, div);

To me, it looks like there is an edge from {m:map, k:key} to div that the cycle collector does not see. Two thoughts:

1) This seems like a general concern about the CC and conditionally-strong references. Is there anything else like that in the product? Watchpoints, maybe?

2) I think I would feel OK about shipping this bug if we knew how we were going to fix it.
Comment 7 Andrew McCreight [:mccr8] 2011-06-12 11:08:21 PDT
One thing to note about this example is that treating the weak references as strong reference would fix the leak, but wouldn't really solve the problem, as it would just make the lifetime of the contents of a weak map as long as the container.  It might be handy to have a privileged JS function that can examine the true state of a weak map.  Even just a thing that returns the number of bindings would allow test scripts to tell if the contents have been collected.

Anyways, I ran this example using cycle collector logging leak tools, which results in this:
> 0x128442e40 [XPCVariant]
>    --[]-> 0x127578088 [JS Object (Object) (global=12754b088)]
>    --[m]-> 0x12754b1a8 [JS Object (WeakMap) (global=12754b088)]
>
>    Root 0x128442e40 is a ref counted object.

The more complete contents of these objects from the CC logs are as follows (with my own comments indicated by //):
0x128442e40 [rc=1] XPCVariant
> 0x127578088     // {m:map, k:key}
> 0x1284430e0     // XPCWrappedJS

0x1284430e0 [rc=2] nsXPCWrappedJS (nsISupports)
> 0x1284430e0     // magic self-reference
> 0x127578088     // {m:map, k:key}

// {m:map, k:key}
0x127578088 [gc] JS Object (Object) (global=12754b088)
> 0x1275490d0 proto
> 0x12754b088 parent
> 0x12754b1a8 m   // weak map
> 0x12755a0f8 k   // empty object key

// weak map
0x12754b1a8 [gc] JS Object (WeakMap) (global=12754b088)
> 0x12754b160 proto
> 0x12754b088 parent
> 0x12755a0f8 key

// empty object key
0x12755a0f8 [gc] JS Object (Object) (global=12754b088)
> 0x1275490d0 proto
> 0x12754b088 parent

From this, it looks to me that from the cycle collector's perspective, the weak map has a reference to the key, but not to its value.
Comment 8 Jesse Ruderman 2011-06-12 13:01:46 PDT
> It might be handy to have a privileged JS function that can examine the true 
> state of a weak map.  Even just a thing that returns the number of bindings
> would allow test scripts to tell if the contents have been collected.

fwiw, the js shell's solution for this kind of GC testing is makeFinalizeObserver + finalizeCount.  It's more general, even for WeakMap, because it lets you test what happens when you drop the reference to the WeakMap itself.
Comment 9 Andrew McCreight [:mccr8] 2011-06-12 22:56:39 PDT
I ran the example again using the CC leak tools, except with WANT_ALL_TRACES enabled.  When it is enabled, marked JS objects are traversed.

When this is done, the value shows up.  For some reason, it is marked, but the key isn't.  It is actually the marked value that is rooting the weakmap.  I don't think the value should be marked.

0x1252f6a28 [JS Object (HTMLDivElement) (global=1252f3088)]
    --[xpc_GetJSPrivate(obj)]-> 0x12776b260 [nsGenericElement (xhtml) div]
    --[[user data (or handler)]]-> 0x12776bc50 [XPCVariant]
    --[]-> 0x12776bcc0 [nsXPCWrappedJS (nsISupports)]
    --[]-> 0x128928088 [JS Object (Object) (global=1252f3088)]
    --[m]-> 0x1252f31a8 [JS Object (WeakMap) (global=1252f3088)]

    Root 0x1252f6a28 is a marked GC object.


0x1252f31a8 [gc] JS Object (WeakMap) (global=1252f3088)
> 0x1252f3160 proto
> 0x1252f3088 parent
> 0x1289080f8 key
> 0x1252f6a28 value

// key
0x1289080f8 [gc] JS Object (Object) (global=1252f3088)
> 0x1252f10d0 proto
> 0x1252f3088 parent

// value
0x1252f6a28 [gc.marked] JS Object (HTMLDivElement) (global=1252f3088)
> 0x1252f6818 proto
> 0x1252f6450 parent
> 0x1252f6818 XPCWrappedNativeProto::mJSProtoObject
> 0x12776b260 xpc_GetJSPrivate(obj)
Comment 10 Andrew McCreight [:mccr8] 2011-06-13 10:38:06 PDT
I think I've figured out why this is leaking.

The sequence of events in MarkAndSweep is:
(1) regular marking (black)
(2) MarkRuntime
    - set marking color to gray
    - mark things strongly reachable from XPConnect
    - set marking color to black
(3) MarkAndSweep calls WeakMap::markIteratively

What happens in the example leaking code is that |map| gets added to the WeakMap list in step (2), and |map| and |key| are marked gray.  Then in step 3, |value| gets marked (because the key is live), but it is incorrectly marked black because that is the current color.  The CC sees that |value| is strongly held by JS, and roots everything it is connected to, causing the leak.

In addition to the leaking problem, it feels off to me that the CC gray marking is done before the JS black marking is really done in step 3.  I don't know offhand if there may be any invariants of gray marking violated by this.

To fix this, I think we need to change the sequence to something like this:
(1) MarkAndSweep does its regular marking
(2) MarkAndSweep calls WeakMap::markIteratively to mark things held from JS roots.  Reset the weak map list (if that doesn't happen already).
(3) MarkAndSweep calls MarkNative
(4) somebody calls WeakMap::markIteratively again, except with the color set to gray.

I'm not sure where the second call to markIteratively should live.  On the one hand, jsgc.cpp doesn't really know about gray right now, so it feels like it should be doen inside MarkNative.  On the other hand, I'm not sure MarkNative knows about gcmarker.drainMarkStack(), which needs to be done after markIteratively.

This same problem could probably exist with watchpoints, assuming that they are basically like weak maps in terms of owning things.  I don't know anything about them.
Comment 11 Andrew McCreight [:mccr8] 2011-06-13 17:24:29 PDT
Created attachment 539063 [details] [diff] [review]
mark gray any weak references reachable from XPCOM

First pass at a patch.  I'm able to browse Techcrunch for a minute or two, and it doesn't leak any WeakMaps on the testcase, at least according to the CC graph.

The basic idea is to mark weak references black once right before we mark XPCOM roots, and then mark weak references gray afterwards.  No cycle collector changes are needed.

This will make WeakMap values reachable only via XPCOM roots gray instead of black.  WeakMap values reachable from both XPCOM and JS roots should be black, as they are now.

It is a little messy.  It further bleeds out the dual-mode IS_GC_MARKING_TRACER(trc) splitting into MarkRuntime().  XPCJSRuntime::TraceJS calls back into the JS GC to do js::MarkWeakReferences (I guess that should really be in the GC namespace somehow).

I went on the conservative side with sprinkling drainMarkStacks around.

I also took the liberty of changing the signature of markIteratively from taking a JSTracer* to taking a GCMarker*, because only the GCMarker delays tracing weak references.

I think that the eager traversal of WeakMaps by non-GC_MARKING_TRACERS has the potential of causing incorrect traversals for JSTracers that run when the mark bits are in a broken state and/or don't respect the mark bits when traversing.  This won't be a problem for the cycle collector, but it looks like there are a few other JSTracers I am unfamiliar with.

Comments welcome, as I'm not super familiar with the JS GC.
Comment 12 Bill McCloskey (:billm) 2011-06-13 17:34:24 PDT
It looks okay to me. This code will change a lot if/when we land incremental GC, and I think it might get a little bit prettier.
Comment 13 Andrew McCreight [:mccr8] 2011-06-14 19:37:47 PDT
Created attachment 539407 [details] [diff] [review]
mark any weak references reachable from XPCOM gray, not black

Fixed a minor Windows build bustage, rewrote an existing comment.  Non-windows and Windows debug have had clean try runs.  Just waiting on Windows Opt.
Comment 14 Andrew McCreight [:mccr8] 2011-06-14 19:44:28 PDT
Comment on attachment 539407 [details] [diff] [review]
mark any weak references reachable from XPCOM gray, not black

This is going to collide with Bug 660039, so I'll have to fix up the patch.  Doesn't look like anything too severe.  I'll do that tomorrow.
Comment 15 Andreas Gal :gal 2011-06-14 20:10:45 PDT
Comment on attachment 539407 [details] [diff] [review]
mark any weak references reachable from XPCOM gray, not black

># HG changeset patch
># User Andrew McCreight <amccreight@mozilla.com>
># Date 1308098907 25200
># Node ID d58785933e476a6c5cb969c99acb675bf4ff81c8
># Parent  215f8773178afacfc7c0ffa3be6017a4ddd47e6a
>Bug 653248 - Mark any weak references reachable from XPCOM gray, not black. r=gal
>
>diff --git a/js/src/jsgc.cpp b/js/src/jsgc.cpp
>--- a/js/src/jsgc.cpp
>+++ b/js/src/jsgc.cpp
>@@ -1805,16 +1805,27 @@ MarkContext(JSTracer *trc, JSContext *ac
>         gcr->trace(trc);
> 
>     if (acx->sharpObjectMap.depth > 0)
>         js_TraceSharpMap(trc, &acx->sharpObjectMap);
> 
>     MarkValue(trc, acx->iterValue, "iterValue");
> }
> 
>+void
>+MarkWeakReferences(GCMarker *trc)
>+{
>+    trc->drainMarkStack();

This should probably assert here that the stack is empty instead.

>+    while (true) {
>+        if (!js_TraceWatchPoints(trc) && !WeakMap::markIteratively(trc))
>+            break;
>+        trc->drainMarkStack();
>+    }
>+}
>+
> JS_REQUIRES_STACK void
> MarkRuntime(JSTracer *trc)
> {
>     JSRuntime *rt = trc->context->runtime;
> 
>     if (rt->state != JSRTS_LANDING)
>         MarkConservativeStackRoots(trc);
> 
>@@ -1834,19 +1845,24 @@ MarkRuntime(JSTracer *trc)
> #ifdef JS_TRACER
>     for (JSCompartment **c = rt->compartments.begin(); c != rt->compartments.end(); ++c)
>         (*c)->traceMonitor.mark(trc);
> #endif
> 
>     for (ThreadDataIter i(rt); !i.empty(); i.popFront())
>         i.threadData()->mark(trc);
> 
>+    if (IS_GC_MARKING_TRACER(trc)) {
>+        GCMarker *gcmarker = static_cast<GCMarker *>(trc);
>+        MarkWeakReferences(gcmarker);
>+    }
>+
>     /*
>-     * We mark extra roots at the last thing so it can use use additional
>-     * colors to implement cycle collection.
>+     * We mark extra roots at the end so additional colors can be used
>+     * to implement cycle collection.
>      */
>     if (rt->gcExtraRootsTraceOp)
>         rt->gcExtraRootsTraceOp(trc, rt->gcExtraRootsData);
> 
> #ifdef DEBUG
>     if (rt->functionMeterFilename) {
>         for (int k = 0; k < 2; k++) {
>             typedef JSRuntime::FunctionCountMap HM;
>@@ -2276,25 +2292,16 @@ MarkAndSweep(JSContext *cx, JSCompartmen
>     } else {
>         js_MarkScriptFilenames(rt);
>     }
> 
>     MarkRuntime(&gcmarker);
> 
>     gcmarker.drainMarkStack();
> 
>-    /*
>-     * Mark weak roots.
>-     */
>-    while (true) {
>-        if (!js_TraceWatchPoints(&gcmarker) && !WeakMap::markIteratively(&gcmarker))
>-            break;
>-        gcmarker.drainMarkStack();
>-    }
>-
>     rt->gcMarkingTracer = NULL;
> 
>     if (rt->gcCallback)
>         (void) rt->gcCallback(cx, JSGC_MARK_END);
> 
> #ifdef DEBUG
>     /* Make sure that we didn't mark an object in another compartment */
>     if (comp) {
>diff --git a/js/src/jsgc.h b/js/src/jsgc.h
>--- a/js/src/jsgc.h
>+++ b/js/src/jsgc.h
>@@ -1229,16 +1229,19 @@ struct GCMarker : public JSTracer {
>     }
> 
>     void pushXML(JSXML *xml) {
>         if (!xmlStack.push(xml))
>             delayMarkingChildren(xml);
>     }
> };
> 
>+JS_FRIEND_API(void)
>+MarkWeakReferences(GCMarker *trc);
>+
> void
> MarkStackRangeConservatively(JSTracer *trc, Value *begin, Value *end);
> 
> static inline uint64
> TraceKindMask(unsigned kind)
> {
>     return uint64(1) << kind;
> }
>diff --git a/js/src/jsweakmap.cpp b/js/src/jsweakmap.cpp
>--- a/js/src/jsweakmap.cpp
>+++ b/js/src/jsweakmap.cpp
>@@ -239,20 +239,21 @@ WeakMap::mark(JSTracer *trc, JSObject *o
>                 js::gc::MarkValue(trc, value, "value");
>             }
>         }
>     }
> }
> 
> /*
>  * Walk through the previously collected list of tables and mark rows
>- * iteratively.
>+ * iteratively.  GCMarker is the only tracer that delays tracing weak
>+ * references.
>  */
> bool
>-WeakMap::markIteratively(JSTracer *trc)
>+WeakMap::markIteratively(GCMarker *trc)
> {
>     JSContext *cx = trc->context;
>     JSRuntime *rt = cx->runtime;
> 
>     bool again = false;
>     JSObject *obj = rt->gcWeakMapList;
>     while (obj) {
>         WeakMap *table = fromJSObject(obj);
>diff --git a/js/src/jsweakmap.h b/js/src/jsweakmap.h
>--- a/js/src/jsweakmap.h
>+++ b/js/src/jsweakmap.h
>@@ -66,17 +66,17 @@ class WeakMap {
>     static void mark(JSTracer *trc, JSObject *obj);
>     static void finalize(JSContext *cx, JSObject *obj);
> 
>   public:
>     WeakMap(JSContext *cx);
> 
>     static JSBool construct(JSContext *cx, uintN argc, Value *vp);
> 
>-    static bool markIteratively(JSTracer *trc);
>+    static bool markIteratively(GCMarker *trc);
>     static void sweep(JSContext *cx);
> 
>     static Class jsclass;
>     static JSFunctionSpec methods[];
> };
> 
> }
> 
>diff --git a/js/src/xpconnect/src/xpcjsruntime.cpp b/js/src/xpconnect/src/xpcjsruntime.cpp
>--- a/js/src/xpconnect/src/xpcjsruntime.cpp
>+++ b/js/src/xpconnect/src/xpcjsruntime.cpp
>@@ -368,18 +368,20 @@ void XPCJSRuntime::TraceJS(JSTracer* trc
>     // Mark these roots as gray so the CC can walk them later.
>     js::GCMarker *gcmarker = NULL;
>     if (IS_GC_MARKING_TRACER(trc)) {
>         gcmarker = static_cast<js::GCMarker *>(trc);
>         JS_ASSERT(gcmarker->getMarkColor() == XPC_GC_COLOR_BLACK);
>         gcmarker->setMarkColor(XPC_GC_COLOR_GRAY);
>     }
>     self->TraceXPConnectRoots(trc);
>-    if (gcmarker)
>+    if (gcmarker) {
>+        js::MarkWeakReferences(gcmarker);
>         gcmarker->setMarkColor(XPC_GC_COLOR_BLACK);
>+    }
> }
> 
> static void
> TraceJSObject(PRUint32 aLangID, void *aScriptThing, const char *name,
>               void *aClosure)
> {
>     if(aLangID == nsIProgrammingLanguage::JAVASCRIPT)
>     {

Great work. Thanks!
Comment 16 Andrew McCreight [:mccr8] 2011-06-15 11:39:08 PDT
Created attachment 539602 [details] [diff] [review]
mark any weak references reachable from XPCOM gray, not black

Patch fixup, mostly to make it compatible with Bug 660039.  The changes are pretty minor, but I'm going to do a try server run just in case.  http://tbpl.mozilla.org/?tree=Try&rev=f83a32db3bb1

> This should probably assert here that the stack is empty instead.

It doesn't look to me like the stack is going to be drained before either call to MarkWeakReferences.  I do think the last thing that MarkRuntime always does is MarkWeakReferences, so the drainMarkStack after the call to that could probably be changed to an assert, though that seems a little fragile to me, so I'm just going to leave it as is.  It only saves you one stack empty check per GC.


- Cleanup: I refactored the while loop from |while(true) {if(foo()) break; bar();}| to |while(!foo()) bar();| because that seemed simpler.

- For Bug 660039, the call to |WeakMap::markIteratively(trc)| is now a call to |WeakMapBase::markAllIteratively(trc))|.  Same thing, more or less, with a different name.

- For Bug 660039, I undid my changes to the argument type of markIteratively (had changed it from JSTracer* to GCMarker*) because with the new more general interface I suppose other kinds of tracers could be used that also delay marking.  Thus there are no changes at all now in my patch to jsweakmap.{h,cpp}.  MarkWeakReferences still requires a GCMarker.
Comment 17 Andrew McCreight [:mccr8] 2011-06-15 19:21:29 PDT
Comment on attachment 539602 [details] [diff] [review]
mark any weak references reachable from XPCOM gray, not black

This had a clean try run, so I'll get it landed in Tracemonkey.
Comment 18 Andrew McCreight [:mccr8] 2011-06-15 19:22:21 PDT
(carrying forward gal's r+)
Comment 19 Dave Herman [:dherman] 2011-06-16 10:11:39 PDT
http://hg.mozilla.org/tracemonkey/rev/0c1bdce6b0d2
Comment 20 Andrew McCreight [:mccr8] 2011-06-20 12:47:58 PDT
One subtle point I failed to realize at first for why this works is that the list of weak maps found during the black marking phase must be kept around and re-examined during the gray marking phase.

Consider the following case: we have a black reference to a weak map, and a grey reference to a key in the map, and no other reference to the value associated with the key.  During the black marking phase, the weak map is added to the weak map list, but the key isn't reachable, so nothing happens with the key.  Then, during the grey marking phase, we mark the key grey.  Then we look at the weak map list again, and because it isn't cleared yet, the value will be marked grey.  If we had cleared the weak map list after the black marking phase, then the key would not be marked, and thus incorrectly treated as garbage.

Fortunately, the weak map list is not wiped until the end of the sweep phase, so it is okay.
Comment 21 Andreas Gal :gal 2011-06-20 12:50:32 PDT
++andrew and try to make a testcase for this
Comment 22 Chris Leary [:cdleary] (not checking bugmail) 2011-06-20 17:07:45 PDT
cdleary-bot mozilla-central merge info:
http://hg.mozilla.org/mozilla-central/rev/0c1bdce6b0d2
Comment 23 Andrew McCreight [:mccr8] 2011-06-28 20:02:40 PDT
Backed out on inbound due to Bug 667011.

http://hg.mozilla.org/integration/mozilla-inbound/rev/7fff9bc0c776
Comment 24 Marco Bonardo [::mak] 2011-06-29 02:25:25 PDT
merged backout to central http://hg.mozilla.org/mozilla-central/rev/7fff9bc0c776
Comment 25 Andrew McCreight [:mccr8] 2011-07-01 13:54:51 PDT
backout in Tracemonkey http://hg.mozilla.org/tracemonkey/rev/9b5a70a74209
Comment 26 Chris Leary [:cdleary] (not checking bugmail) 2011-07-05 18:06:12 PDT
cdleary-bot mozilla-central merge info:
http://hg.mozilla.org/mozilla-central/rev/9b5a70a74209 (backout)
Note: not marking as fixed because last changeset is a backout.
Comment 27 Andrew McCreight [:mccr8] 2011-07-07 10:40:20 PDT
jimb pointed out that the gcmarker.drainMarkStack() in MarkAndSweep is dangerous looking, because any call to drainMarkStack can potentially find a new WeakMap, so we need to iterate over WeakMaps any time a drainMarkStack is done.

Looking over the code, I think that the markStack will always be empty at this point, so that drainMarkStack can be deleted, but I should probably add in some JS_ASSERTS to check that the mark stack is actually empty, maybe when we leave MarkRuntime.
Comment 28 Jim Blandy :jimb 2011-07-07 15:36:55 PDT
Created attachment 544639 [details] [diff] [review]
In GC, separate JS_SetExtraGCRoots marking and grey-marking passes, so that WeakMap-like edges are properly traced in each pass.

[not tested; just posted for general comments on the idea; read the changes to jsapi.h and jsgc.h to get the gist.]

At present, the black and gray marking passes are triggered in a rather
obscure way. In jsgc.cpp, MarkAndSweep calls MarkRuntime, which invokes the
callback XPConnect registered via JS_SetExtraGCRoots, which is
XPCJSRuntime::TraceJS, which calls js::GCMarker::setMarkColor, which, on
the grounds that switching colors with a non-empty marking stack would be
bad, calls drainMarkStack, causing the black marking traversal to run to
completion.

It's rather surprising when a function which appears to simply be marking
roots and priming the marking stack (MarkRuntime) calls another function
which appears to be similarly innocent (TraceJS), which calls another
innocent-looking function (setMarkColor), which then does all the work.

In fact, the iterative marking pass --- the loop which calls
js_TraceWatchPoints and WeakMapBase::markAllIteratively, and resumes the
traversal if they mark anything new --- sits after the call to MarkRuntime.
This means that we scan tracepoints and WeakMaps only after the grey
marking phase has completed. This is incorrect. Each marking pass, black
and gray, must walk all tracepoints and WeakMaps to ensure that table
entries found to be live in that pass are marked with the correct color.
The tracepoint/WeakMap traversal is an essential part of finding all
objects reachable from a given set of roots.

Jason Orendorff and I have been working in that area of the code recently,
and never noticed that the loop was misplaced. This is clearly because this
major feature of the collector, the distinct black and gray mark passes, is
hidden inside three levels of functions with misleading names, instead of
appearing in the control flow of MarkAndSweep, as it should.

THE POINT, I'M GETTING TO IT

This patch adds a new JSAPI entry point, JS_SetNextGCMarkColorCallback,
which embeddings can use to request additional mark passes with new mark
colors, and changes XPConnect to use that instead of forcing the black pass
to complete immediately in its JS_SetExtraGCRoots callback.
Comment 29 Jim Blandy :jimb 2011-07-07 15:38:30 PDT
billm: How will this fit in with your work?
Comment 30 Jim Blandy :jimb 2011-07-07 15:40:32 PDT
I should probably be clearer: the goal of this patch is to get things properly marked black or gray in the presence of WeakMaps. I don't know if it fixes the original bug. But the code as it stands is completely wrong, so something with an effect similar to this patch is necessary in any case.
Comment 31 Bill McCloskey (:billm) 2011-07-07 15:58:21 PDT
This looks fine with regard to incremental marking. It also seems clearer to do it this way.

I do have a few general comments about the patch. I don't really like the fact that NextGCMarkColor tracks its state via the current mark color, and the fact that it leaves it gray at the end. Also, the name doesn't seem great.

How about this instead: Embedders would be allowed to register any number of root trace hooks. Each would have an associated color. We would store them in a vector in the runtime. Then the XPConnect code would have a nice structure:
  JS_AddRootTracingCallback(rt, MarkBlackRoots, BLACK);
  JS_AddRootTracingCallback(rt, MarkGrayRoots, GRAY);

And the GC code could just loop over these. Depending on whether it's a GC tracer, we would change the color or not. It would take care of mark stack draining and weak marking here as your patch does.
Comment 32 Jim Blandy :jimb 2011-07-07 16:23:38 PDT
(In reply to comment #31)
> This looks fine with regard to incremental marking. It also seems clearer to
> do it this way.

Okay, great.

> How about this instead: Embedders would be allowed to register any number of
> root trace hooks. Each would have an associated color. We would store them
> in a vector in the runtime. Then the XPConnect code would have a nice
> structure:
>   JS_AddRootTracingCallback(rt, MarkBlackRoots, BLACK);
>   JS_AddRootTracingCallback(rt, MarkGrayRoots, GRAY);
> 
> And the GC code could just loop over these. Depending on whether it's a GC
> tracer, we would change the color or not. It would take care of mark stack
> draining and weak marking here as your patch does.

I'm not attached to the name, but I'm sensitive to the fact that we have exactly one client for this, which needs exactly one additional pass. I don't want to write too many lines of code for generality we don't need. But what you propose certainly makes the intent of the XPConnect code clear, and avoids the weird little conditionals I needed to put the XPConnect roots in the black pass for non-GC traversals.
Comment 33 Jim Blandy :jimb 2011-07-07 17:45:30 PDT
I would expect this patch (as written) to break the cycle collector's "ExplainLiveExpectedGarbage" diagnostic, enabled when DEBUG_CC is #defined. Via these calls:

nsCycleCollector::CleanupAfterCollection
-> nsCycleCollector::ExplainLiveExpectedGarbage
   -> nsXPConnect::BeginCycleCollection
      -> JS_TraceRuntime
         -> TraceRuntime
            -> MarkRuntime
               -> rt->gcExtraRootsTraceOp
                  -> XPCJSRuntime::TraceJS
                     -> js::GCMarker::setMarkColor

I think the cycle collector is expecting the call to MarkRuntime to actually run the collection. At least, I don't see anything else in nsXPConnect::BeginCycleCollection that would drain the mark stack.

Although --- that can't be right, because XPCJSRuntime::TraceJS doesn't switch colors for non-GC tracers, which is what nsXPConnect::BeginCycleCollection is passing it. I need to see this code running to figure out what's going on.
Comment 34 Andrew McCreight [:mccr8] 2011-07-07 17:55:23 PDT
JS_TraceRuntime isn't going to use a GC tracer, right?  So there's no mark stack to drain.  Mark stacks are only used internally in the GC.
Comment 35 Jim Blandy :jimb 2011-07-07 18:01:12 PDT
My last comment is really confused.

1) the bug it's worried about would have been introduced by a new, currently unattached draft of the patch incorporating the suggestions in comment 31, not in comment 28's patch.

2) non-GC tracers recurse explicitly; they don't use the marking stack. I always forget this.

So it doubly doesn't apply to comment 28's patch.
Comment 36 Jim Blandy :jimb 2011-07-07 19:10:15 PDT
Created attachment 544682 [details] [diff] [review]
In GC, separate marking passes, so that WeakMap-like edges are properly traced in each pass.

billm, here's another untested patch that implements your idea. What do you think?
Comment 37 Bill McCloskey (:billm) 2011-07-07 20:04:21 PDT
Thanks Jim, this looks great. How about factoring the drainMarkStack piece with the weak marking into a separate function? Then you could call it once before the loop over the passes and once within the loop, which would get rid of the for (pass=-1; ...) stuff. This seems clearer to me.
Comment 38 Jim Blandy :jimb 2011-07-08 16:19:48 PDT
Maybe just move the WeakMap stuff right into drainMarkStack...
Comment 39 Andrew McCreight [:mccr8] 2011-07-08 16:24:40 PDT
The problem with that is that it will make all of the WeakMaps found thus far scanned every time drainMarkStack is called, and I believe it is called a bunch of times elsewhere.
Comment 40 Jim Blandy :jimb 2011-07-09 19:02:46 PDT
Created attachment 545040 [details] [diff] [review]
In GC, separate marking passes, so that WeakMap-like edges are properly traced in each pass.

Okay, here's another iteration. It incorporates the JS_AddGCMarkPass API, and also folds the WeakMap and tracepoint handling into the drainMarkStack function (where, I'd argue, it always belonged). With billm's suggestions, it seems pretty clean, both on its own merits and compared to the current code.

Naturally, this shouldn't land until bug 667011 is sorted out, but here it is, for what it's worth. I've verified that a gray key in a WeakMap results in a gray value.
Comment 41 Jim Blandy :jimb 2011-07-11 16:12:45 PDT
Created attachment 545282 [details] [diff] [review]
In GC, separate marking passes, so that WeakMap-like edges are properly traced in each pass.

This iteration doesn't delete the old JS_SetExtraGCRoots JSAPI function; it just adds the new JS_AddGCMarkPass function. Friendlier for other embeddings (unless they're doing multi-pass collections and not using XPConnect).

Andrew, I'm going to leave this patch and bug to you, so I can concentrate on Debugger stuff, but I'll be happy to answer questions if any arise. It seems like you're taking care of all the hard stuff in bug 668855.
Comment 42 Asa Dotzler [:asa] 2011-07-17 22:49:20 PDT
This bug has a grand Cc: list so I'm asking you all: We've been tracking this for Firefox 6 for most of its lifetime. Are the kinds of fixes we're looking at here the kinds of fixes we'd risk late in Beta? If not, are we OK with these leaks shipping in 6?
Comment 43 Andreas Gal :gal 2011-07-17 22:55:33 PDT
WeakMaps is a new feature. No FF code depends on it. I think we can survive the leak and fix it in 7.
Comment 44 Asa Dotzler [:asa] 2011-08-25 14:36:36 PDT
If there are indications that this is more important because its use is growing out on the web or something like that, then please re-nominate. It's not clear why release drivers should be tracking this anywhere.
Comment 45 Andrew McCreight [:mccr8] 2011-09-09 11:22:56 PDT
Created attachment 559521 [details] [diff] [review]
mark values reachable only from XPConnect roots gray

Rebasing my previous patch.  The only real change is that the glob of code for visiting weak roots that I move up to MarkWeakReferences has changed a bit.  Carrying forward gal's review.
Comment 46 Andrew McCreight [:mccr8] 2011-10-10 13:57:50 PDT
Created attachment 566026 [details] [diff] [review]
mark values reachable only from XPConnect roots gray

Bill split apart black and gray marking of XPConnect roots in Bug 692884, which requires some minor readjustment of this patch.  Same idea as before (mark weak roots twice, once after black marking, once after gray marking while the color is still gray), but now mark color changing is done entirely in the JS GC.

This patch also changes setMarkColor(uint32 newColor) to setMarkColorGray().  With this patch, the only valid color transition is changing black to gray, so changing the GCMarker interface in this way reduces footgun potential.

This is intended to be landed on top of the patches in Bug 668855.
Comment 47 Bill McCloskey (:billm) 2011-10-10 16:34:32 PDT
Comment on attachment 566026 [details] [diff] [review]
mark values reachable only from XPConnect roots gray

Review of attachment 566026 [details] [diff] [review]:
-----------------------------------------------------------------

I'm glad to see the assert go in so quickly!

::: js/src/jsgc.cpp
@@ +1936,5 @@
>      MarkValue(trc, acx->iterValue, "iterValue");
>  }
>  
> +void
> +MarkWeakReferences(GCMarker *trc)

Could you call it gcmarker instead of trc? This is the style elsewhere.

@@ +1944,5 @@
> +           WeakMapBase::markAllIteratively(trc) ||
> +           Debugger::markAllIteratively(trc))
> +    {
> +        trc->drainMarkStack();
> +    }

This might work better as a do..while loop, but it's up to you which is more readable.

@@ +1987,5 @@
>          (*op)(trc, rt->gcBlackRootsData);
>  
> +    if (IS_GC_MARKING_TRACER(trc)) {
> +        GCMarker *gcmarker = static_cast<GCMarker *>(trc);
> +        MarkWeakReferences(gcmarker);

I would rather that the MarkWeakReferences call here go at the beginning of EndMarkPhase. It fits in better for incremental GC this way, and you also can avoid the IS_GC_MARKING_TRACER check.

@@ +2416,1 @@
>          gcmarker->drainMarkStack();

Isn't this last drainMarkStack unnecessary? Also, could you add an assert that the mark stack is empty? This could go right before the |rt->gcMarkingTracer = NULL| statement below (outside the conditional).
Comment 48 Andrew McCreight [:mccr8] 2011-10-10 17:24:45 PDT
(In reply to Bill McCloskey (:billm) from comment #47)
> This might work better as a do..while loop, but it's up to you which is more
> readable.

I ended up changing it to just a while loop.  This keeps us from doing drainMarkStack a second time in a row at the start of EndMarkPhase.

> > +    if (IS_GC_MARKING_TRACER(trc)) {
> > +        GCMarker *gcmarker = static_cast<GCMarker *>(trc);
> > +        MarkWeakReferences(gcmarker);
> 
> I would rather that the MarkWeakReferences call here go at the beginning of
> EndMarkPhase. It fits in better for incremental GC this way, and you also
> can avoid the IS_GC_MARKING_TRACER check.
Ah, good point, that's better.  Though we have to do the IS_GC_MARKING_TRACER check anyways for the other path. ;)

> @@ +2416,1 @@
> >          gcmarker->drainMarkStack();
> 
> Isn't this last drainMarkStack unnecessary? Also, could you add an assert
> that the mark stack is empty? This could go right before the
> |rt->gcMarkingTracer = NULL| statement below (outside the conditional).

I added a bunch of asserts for this.
Comment 49 Andrew McCreight [:mccr8] 2011-10-10 17:29:00 PDT
Created attachment 566091 [details] [diff] [review]
mark values reachable only from XPConnect roots gray

Addressed review comments.  I flagged this for re-review because I ended up changing MarkWeakReferences so that it won't do a drainMarkStack at the beginning.  I also added a bunch of assertions so we can be sure this is okay.  jsgc.h is the same as before.
Comment 50 Bill McCloskey (:billm) 2011-10-10 17:32:25 PDT
Comment on attachment 566091 [details] [diff] [review]
mark values reachable only from XPConnect roots gray

Thanks.
Comment 51 Andrew McCreight [:mccr8] 2011-11-24 04:55:33 PST
https://hg.mozilla.org/integration/mozilla-inbound/rev/5f7ce475ab06
Comment 52 Ed Morley [:emorley] 2011-11-24 08:14:16 PST
https://hg.mozilla.org/mozilla-central/rev/5f7ce475ab06

Note You need to log in before you can comment on or make changes to this bug.