Last Comment Bug 707313 - gcWeakMapList can become circular
: gcWeakMapList can become circular
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: -- normal (vote)
: mozilla12
Assigned To: Andrew McCreight [:mccr8]
:
Mentors:
Depends on: 673551
Blocks: 497543 WeakMap 669240
  Show dependency treegraph
 
Reported: 2011-12-02 14:08 PST by Jason Orendorff [:jorendorff]
Modified: 2012-01-27 00:43 PST (History)
8 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
use NULL next pointers as sentinels to avoid infinite loops, wip (3.95 KB, patch)
2011-12-22 19:50 PST, Andrew McCreight [:mccr8]
ttaubert: feedback+
Details | Diff | Review
distinguish values in the list from those not in the list (5.61 KB, patch)
2011-12-23 11:04 PST, Andrew McCreight [:mccr8]
jimb: review+
ttaubert: feedback+
Details | Diff | Review

Description Jason Orendorff [:jorendorff] 2011-12-02 14:08:31 PST
I just happend to stumble across this one while trying to use jorendb.js to debug 10 MB of Smalltalk I had compiled to JS...

js::Debugger::traceObject mustn't be called more than once per GC cycle. But it can happen, if the GC runs out of mark stack.

Breakpoint 7, js::Debugger::trace (this=0x100b23b50, trc=0x7fff5fbd9b30) at Debugger.cpp:1179
1179	    if (uncaughtExceptionHook)
(gdb) p trc->context->runtime->gcWeakMapList 
$30 = ('js::WeakMapBase' *) 0x0
(gdb) p trc->context->runtime->gcCurrentCompartment 
$31 = (JSCompartment *) 0x0
(gdb) bt 6
#0  js::Debugger::trace (this=0x100b23b50, trc=0x7fff5fbd9b30) at Debugger.cpp:1179
#1  0x00000001002b937f in js::Debugger::traceObject (trc=0x7fff5fbd9b30, obj=0x100e22a28) at Debugger.cpp:1173
#2  0x0000000100105d42 in ScanObject (gcmarker=0x7fff5fbd9b30, obj=0x100e22a28) at jsgcmark.cpp:791
#3  0x00000001001066b2 in js::GCMarker::drainMarkStack (this=0x7fff5fbd9b30) at jsgcmark.cpp:1049
#4  0x00000001000ebd75 in MarkAndSweep (cx=0x100b154f0, gckind=GC_NORMAL) at jsgc.cpp:2697
#5  0x00000001000ec101 in GCCycle (cx=0x100b154f0, comp=0x0, gckind=GC_NORMAL) at jsgc.cpp:2929
(More stack frames follow...)
(gdb) c
Continuing.

Breakpoint 7, js::Debugger::trace (this=0x100b23b50, trc=0x7fff5fbd9b30) at Debugger.cpp:1179
1179	    if (uncaughtExceptionHook)
(gdb) p trc->context->runtime->gcWeakMapList 
$32 = ('js::WeakMapBase' *) 0x100b23ca0
(gdb) p trc->context->runtime->gcCurrentCompartment 
$33 = (JSCompartment *) 0x0
(gdb) bt 6
#0  js::Debugger::trace (this=0x100b23b50, trc=0x7fff5fbd9b30) at Debugger.cpp:1179
#1  0x00000001002b937f in js::Debugger::traceObject (trc=0x7fff5fbd9b30, obj=0x100e22a28) at Debugger.cpp:1173
#2  0x0000000100107401 in js::gc::MarkChildren (trc=0x7fff5fbd9b30, obj=0x100e22a28) at jsgcmark.cpp:868
#3  0x0000000100107570 in js::TraceChildren (trc=0x7fff5fbd9b30, thing=0x100e22a28, kind=JSTRACE_OBJECT) at jsgcmark.cpp:1080
#4  0x0000000100045b29 in JS_TraceChildren (trc=0x7fff5fbd9b30, thing=0x100e22a28, kind=JSTRACE_OBJECT) at jsapi.cpp:2330
#5  0x00000001000e6663 in MarkDelayedChildren (trc=0x7fff5fbd9b30, a=0x100e22000) at jsgc.cpp:1795
(More stack frames follow...)
(gdb) n
1190	    for (FrameMap::Range r = frames.all(); !r.empty(); r.popFront()) {
(gdb) 
1197	    objects.trace(trc);
(gdb) 
1200	    scripts.trace(trc);
(gdb) 
1201	}
(gdb) p trc->context->runtime->gcWeakMapList 
$34 = ('js::WeakMapBase' *) 0x100b23ca0
(gdb) p $34->next
$35 = ('js::WeakMapBase' *) 0x100b23c30
(gdb) p $35->next
$36 = ('js::WeakMapBase' *) 0x100b23ca0
(gdb)

jimb wrote: “it seems like 1) distinct end-of-list and not-in-list values, 2) a conditional in WeakMapBase::trace, and 3) actually zeroing the links when we reset the weak map list at the top of MarkAndSweep should be fine.”
Comment 1 Kyle Huey [:khuey] (khuey@mozilla.com) (Away until 6/13) 2011-12-22 07:33:15 PST
ttaubert and I are both seeing this with XPCWrappedNative keys.
Comment 2 Andrew McCreight [:mccr8] 2011-12-22 19:37:05 PST
Arr I forgot about this bug.
Comment 3 Andrew McCreight [:mccr8] 2011-12-22 19:50:30 PST
Created attachment 583999 [details] [diff] [review]
use NULL next pointers as sentinels to avoid infinite loops, wip

I wrote this on a plane.  No promises, except that it compiles.  Let me know if this helps.

basically this implements jimb's plan.  One wrinkle is that if you only have one thing in the list, then you try to mark it again, the next pointer will still be NULL, so you'll end up creating an infinite list anyways.  I work around this by checking if the weak map list is equal to the current node, and skipping.  I guess you could also check post-facto if you created an infinite list.
Comment 4 Tim Taubert [:ttaubert] 2011-12-23 04:32:45 PST
Comment on attachment 583999 [details] [diff] [review]
use NULL next pointers as sentinels to avoid infinite loops, wip

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

No local hangs for me anymore. Try runs are green as well. Thanks!
Comment 5 Andrew McCreight [:mccr8] 2011-12-23 06:29:17 PST
Hmm.  This isn't actually right.  The last element in the list will always have a next of NULL, even if it isn't the head of the list.  I guess I'll have to use a more heavyweight method, like a non-NULL list terminator.
Comment 6 Andrew McCreight [:mccr8] 2011-12-23 11:04:02 PST
Created attachment 584089 [details] [diff] [review]
distinguish values in the list from those not in the list

This new version uses NULL to terminate the weak map list, and the value 1 in the next field of maps that aren't in the list.
Comment 7 Tim Taubert [:ttaubert] 2011-12-24 01:27:41 PST
Comment on attachment 584089 [details] [diff] [review]
distinguish values in the list from those not in the list

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

Works for me, thanks!
Comment 8 :Ms2ger 2011-12-24 01:31:13 PST
Comment on attachment 584089 [details] [diff] [review]
distinguish values in the list from those not in the list

>--- a/js/src/jsweakmap.cpp
>+++ b/js/src/jsweakmap.cpp
>+void
>+WeakMapBase::resetWeakMapList(JSRuntime *rt)
>+{
>+    JS_ASSERT(WeakMapNotInList != NULL);

Can this be a MOZ_STATIC_ASSERT?
Comment 9 Igor Bukanov 2011-12-24 05:36:56 PST
(In reply to Ms2ger from comment #8)
> >+    JS_ASSERT(WeakMapNotInList != NULL);
> 
> Can this be a MOZ_STATIC_ASSERT?

WeakMapNotInList is not a static const as its definition includes reinterpret_cast.
Comment 10 Andrew McCreight [:mccr8] 2011-12-24 05:38:44 PST
(In reply to Igor Bukanov from comment #9)
> WeakMapNotInList is not a static const as its definition includes
> reinterpret_cast.

Yeah, I tried but it gave a quite unintelligible error message.
Comment 11 Jim Blandy :jimb 2012-01-05 14:31:43 PST
Comment on attachment 584089 [details] [diff] [review]
distinguish values in the list from those not in the list

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

Looks good!

::: js/src/jsweakmap.h
@@ +106,5 @@
>  // provides default types for WeakMap's TracePolicy template parameter.
>  template <class Key, class Value> class DefaultTracePolicy;
>  
> +// The value for the next pointer for maps not in the map list.
> +static WeakMapBase * const WeakMapNotInList = reinterpret_cast<WeakMapBase *>(1);

Well, that's nice: it seems like GCC will actually generate a compile-time initialization for this, and inline the value 1, even though the language definition doesn't consider it a constant.

@@ +125,5 @@
>              JS_ASSERT(!tracer->eagerlyTraceWeakMaps);
> +
> +            // Don't add ourselves to the list if we are already in the list. This can
> +            // happen if the weak map is marked more than once due delayed marking.
> +            if (next != WeakMapNotInList)

Nit, if you happen to agree: I think it would be clearer to write this as:

if (next == WeakMapNotInList) {
     ... wibble the list ...
}

That reads logically: If we're not in the list, add us to it. And it means that control continues out of the IS_GC_MARKING_TRACER 'if', which seems natural.

@@ +156,5 @@
>  
>      // Trace all delayed weak map bindings. Used by the cycle collector.
>      static void traceAllMappings(WeakMapTracer *tracer);
>  
> +    // Reset the next pointer of all weak maps in the list to avoid infinite lists.

Nit: if you agree: I think the comment should be, "Mark all WeakMaps in the list as no longer being in the list."
Comment 12 Andrew McCreight [:mccr8] 2012-01-05 16:36:42 PST
trying it out on try: https://tbpl.mozilla.org/?tree=Try&rev=24e4bb523c56
Comment 13 Andrew McCreight [:mccr8] 2012-01-05 16:37:28 PST
I more or less went along with your comments, Jim.  For the reset comment, I just put a more high level comment instead.
Comment 14 Andrew McCreight [:mccr8] 2012-01-06 11:34:12 PST
https://hg.mozilla.org/integration/mozilla-inbound/rev/ebd93b75749b
Comment 15 Andrew McCreight [:mccr8] 2012-01-09 11:09:40 PST
https://hg.mozilla.org/mozilla-central/rev/ebd93b75749b

This was merged on Saturday but the bug didn't get updated.
Comment 16 Jesse Ruderman 2012-01-26 17:20:29 PST
What would a testcase for this bug look like? Is there a "make the GC run out of space" pattern I should add to the fuzzer, or a "tell the GC to run in non-stack-using mode" thing we should add to give us an easy way to test that code?
Comment 17 Andrew McCreight [:mccr8] 2012-01-26 17:42:09 PST
There's a bug about making it always do delayed marking somewhere but it hasn't gotten much traction.
Comment 18 Jason Orendorff [:jorendorff] 2012-01-27 00:43:56 PST
Jesse, thanks for asking. Bug 673551 requests a "make the GC run out of space" knob.

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