495958 - "Assertion failure: isInt32(*p)" with type-unstable loops and undeclared global

Status: RESOLVED FIXED

Description

[Jesse Ruderman]

// b must be undeclared global?
for each (var a in [new Number(1), new Number(1), {}, {}, new Number(1)]) {
    for each (b in [2, "", 2, "", "", ""]) {
        for each (var c in [{}, {}, 3, 3, 3, 3, {}, {}]) {
            4 + a;
        }
    }
}

Assertion failure: isInt32(*p), at ../jstracer.cpp:2008

Before I reduced it, the assertion was different:

Assertion failure: isNumber(*p) == (t == JSVAL_DOUBLE), at ../jstracer.cpp:2016

Comment 1

[Gary Kwong [:gkw] [:nth10sd]]

autoBisect shows this is probably related to bug 479110 :

The first bad revision is:
changeset:   26780:790c0eda3122
user:        Andreas Gal
date:        Sat Apr 04 17:23:34 2009 -0400
summary:     Bug 479110 - TM: avoid frequent mismatch exits. r=brendan

Comment 2

[Mike Beltzner [:beltzner, not reading bugmail]]

Our of curiousity, if this regressed in April, why are we just finding it now, in June? Jesse, are your fuzzers only just getting to this point ..?

Comment 3

[Gary Kwong [:gkw] [:nth10sd]]

(In reply to comment #2)
> Our of curiousity, if this regressed in April, why are we just finding it now,
> in June? Jesse, are your fuzzers only just getting to this point ..?

Beltzner: fuzzers find bugs randomly, and how often the bugs are found depends on various factors that can be unpredictable. I have occasionally found fuzzer bugs that show up many weeks/months after the offending patch landed, even though machines have been fuzzing continuously 24/7.

I won't be surprised if fuzzers continue to find assertions / crashes _after_ 3.5 is released.

Comment 4

[Jesse Ruderman]

Not sure why I haven't hit this specific bug before.  I haven't changed this fuzzer lately, and I have run it for a decent number hours.  My guess is that this bug just requires a fairly specific and complicated testcase.

Comment 5

[Andreas Gal :gal]

This might be a dup of the bug I am working on, but it can't hurt if we look at the two cases in parallel.

Comment 6

[Andreas Gal :gal]

Not a dup, unfortunately.

Comment 7

[Andreas Gal :gal]

The blamed changeset is a red herring. We just didn't trace all of the loop before, now we do.

Comment 8

[Andreas Gal :gal]

We are extending a tree, but the typemap of the side exit isn't compatible with the current VM state.

(gdb) bt
#0  JS_Assert (s=0x1bebe4 "isInt32(*p)", file=0x1bd8a9 "../jstracer.cpp", ln=2031) at ../jsutil.cpp:69
#1  0x0013cee0 in TraceRecorder::import (this=0x313ff0, base=0x42fa54, offset=820, p=0x811764, t=1 '\001', prefix=0x1a7aba "global", index=2, fp=0x0) at ../jstracer.cpp:2031
#2  0x001541d0 in TraceRecorder::import (this=0x313ff0, treeInfo=0x312520, sp=0x42fa74, stackSlots=7, ngslots=3, callDepth=0, typeMap=0x313e20 "") at ../jstracer.cpp:2139
#3  0x001550f8 in TraceRecorder::TraceRecorder (this=0x313ff0, cx=0x30bc70, _anchor=0x438124, _fragment=0x313c60, ti=0x312520, stackSlots=7, ngslots=2, typeMap=0x313e20 "", innermostNestedGuard=0x2de834, outer=0x0, outerArgc=0) at ../jstracer.cpp:1410
#4  0x0015b783 in js_StartRecorder (cx=0x30bc70, anchor=0x438124, f=0x313c60, ti=0x312520, stackSlots=7, ngslots=2, typeMap=0x313e20 "", expectedInnerExit=0x2de834, outer=0x0, outerArgc=0) at ../jstracer.cpp:3511
#5  0x0015bab5 in js_AttemptToExtendTree (cx=0x30bc70, anchor=0x438124, exitedFrom=0x2de834, outer=0x0) at ../jstracer.cpp:4017
#6  0x00161548 in js_MonitorLoopEdge (cx=0x30bc70, inlineCallCount=@0xbffff278) at ../jstracer.cpp:4802
#7  0x0006fd2e in js_Interpret (cx=0x30bc70) at ../jsinterp.cpp:3300
#8  0x0009a345 in js_Execute (cx=0x30bc70, chain=0x2bd000, script=0x30d9f0, down=0x0, flags=0, result=0x0) at jsinterp.cpp:1622
#9  0x00010588 in JS_ExecuteScript (cx=0x30bc70, obj=0x2bd000, script=0x30d9f0, rval=0x0) at ../jsapi.cpp:5046
#10 0x00009a60 in Process (cx=0x30bc70, obj=0x2bd000, filename=0xbffff98c "x.js", forceTTY=0) at ../../shell/js.cpp:412
#11 0x0000a776 in ProcessArgs (cx=0x30bc70, obj=0x2bd000, argv=0xbffff88c, argc=2) at ../../shell/js.cpp:806
#12 0x0000ab43 in main (argc=2, argv=0xbffff88c, envp=0xbffff898) at ../../shell/js.cpp:4729

Comment 9

[Andreas Gal :gal]

This is slightly simplified. It doesn't look a lot simpler but it generates less code.

function boom()
{
    var f = function(){};
    var g = function(){};
    g.prototype.__proto__ = {};
    iq(f);
    iq(f);
    iq(f);
    iq(f);
    iq(g);
}

function iq(obj)
{
    for (var i = 0; i < 10; ++i)
	"" + obj["prototype"];
}

boom();

Comment 10

[Andreas Gal :gal]

(#9 was wrong the wrong bug)

Comment 11

[Gary Kwong [:gkw] [:nth10sd]]

(In reply to comment #9)
> This is slightly simplified. It doesn't look a lot simpler but it generates
> less code.
> 
> function boom()
> {
>     var f = function(){};
>     var g = function(){};
>     g.prototype.__proto__ = {};
>     iq(f);
>     iq(f);
>     iq(f);
>     iq(f);
>     iq(g);
> }
> 
> function iq(obj)
> {
>     for (var i = 0; i < 10; ++i)
>     "" + obj["prototype"];
> }
> 
> boom();

Meant for bug 496054 ?

Comment 12

[Andreas Gal :gal]

Ok, so here is what happens:

(gdb) list
1405	    /* If we came from exit, we might not have enough global types. */
1406	    if (ti->globalSlots->length() > ti->nGlobalTypes())
1407	        specializeTreesToMissingGlobals(cx, ti);
1408	
1409	    /* read into registers all values on the stack and all globals we know so far */
1410	    import(treeInfo, lirbuf->sp, stackSlots, ngslots, callDepth, typeMap);
1411	
1412	    if (fragment == fragment->root) {
1413	        /*
1414	         * We poll the operation callback request flag. It is updated asynchronously whenever 
(gdb) p ti->nGlobalTypes()
$1 = 3
(gdb) p ti->globalSlots->length()
$2 = 3
(gdb) p ngslots
$3 = 2

We are extending a side exit. The original side exit knows only about 2 globals. The tree has grown another one, which has been added to the tree entry type map.

We then call import() to read all the values currently alive. Since there is a missing type in the map, import completes the typemap:

    uint8* globalTypeMap = typeMap + stackSlots;
    unsigned length = treeInfo->nGlobalTypes();

    /*                                                                                                                                                                          
     * This is potentially the typemap of the side exit and thus shorter than the tree's                                                                                        
     * global type map.                                                                                                                                                         
     */
    if (ngslots < length) {
        mergeTypeMaps(&globalTypeMap/*out param*/, &ngslots/*out param*/,
                      treeInfo->globalTypeMap(), length,
                      (uint8*)alloca(sizeof(uint8) * length));
    }
    JS_ASSERT(ngslots == treeInfo->nGlobalTypes());

It uses the entry type map to do so. This is correct when recording a fresh tree, but its bogus when extending a tree. The extended tree might simply have different types for global slots at this location. So we copy a bogus type from the entry map into this location, recorder and interpreter disagree, hilarity ensues.

Fix:

import() is used during the initial importing, but also in side exit continuations. We have to move the typemap merging code out of import. When extending side exits, we have to capture the actual types instead of using the entry type map of the tree to complete the type map. More tomorrow.

Comment 13

[Andreas Gal :gal]

Putting bug back in the pool until I wake up again.

Comment 14

[Jason Orendorff [:jorendorff]]

I'm curious about something else here. Early in the debug spew, I get this:

leaving trace at crasher.js:11@201, op=loop, lr=0xb7c64254, exitType=8, sp=6, calldepth=0, cycles=132885
stack0=object<0x83bf300:Iterator> stack1=object<0x83bf140:Number> stack2=object<0x83bf320:Iterator> stack3=int<2> stack4=object<0x83bf340:Iterator> stack5=double<3> 

Now double<3> here is not inherently wrong, because the jsval in question is an INT jsval being copied to a native slot of type double. But how did this trace ever get recorded?  stack5 is never a double jsval in the interpreter.

Comment 15

[Andreas Gal :gal]

Attachment: work in progress

Comment 16

[Andreas Gal :gal]

#14: we always read doubles from arrays at the moment when we read a number. I have a patch to fix that, but its often not a speedup either. Specializing to int when reading from arrays makes crypto ridiculously slow since the tree explodes as it uses the 32nd bit all the time.

Comment 17

[Andreas Gal :gal]

Attachment: fixes test case, breaks everything else

Comment 18

[Andreas Gal :gal]

Attachment: patch, working

Comment 19

[Graydon Hoare :graydon]

Comment on attachment 381351 [details] [diff] [review]
patch, working

Looks good, though we ought to clean Queue up a ways. I'll file a separate patch.

Comment 20

[Andreas Gal :gal]

This patch didn't go through the try server. Feeling lucky and landing on TM directly.

http://hg.mozilla.org/tracemonkey/rev/2ad658e9f42a

Comment 21

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/2ad658e9f42a

Comment 22

[Robert Sayre]

http://hg.mozilla.org/releases/mozilla-1.9.1/rev/5bb3a53e5ddd

Comment 23

[Andreas Gal :gal]

The analysis and the patch are wrong. This causes bug 496185.

The real bug here is as follows:

#3  0x00156084 in TraceRecorder::TraceRecorder (this=0x313ff0, cx=0x30bc70, _anchor=0x458124, _fragment=0x313c60, ti=0x312520, stackSlots=7, ngslots=2, typeMap=0x313e20 "", innermostNestedGuard=0x2df834, outer=0x0, outerArgc=0) at ../jstracer.cpp:1410
1410	    import(treeInfo, lirbuf->sp, stackSlots, ngslots, callDepth, typeMap);
(gdb) p ngslots
$11 = 2
(gdb) p *anchor  
$12 = {
  <nanojit::SideExit> = {
    guards = 0x458184, 
    from = 0x312350, 
    target = 0x313c60, 
    switchInfo = 0x0
  }, 
  members of VMSideExit: 
  block = 0x0, 
  pc = 0x30db08 "\b??ML\b??ML\b??Mû\003?\001g\004?`\004?`\004\027\a{4", 
  imacpc = 0x0, 
  sp_adj = 56, 
  rp_adj = 0, 
  calldepth = 0, 
  numGlobalSlots = 3, 
  numStackSlots = 7, 
  numStackSlotsBelowCurrentFrame = 0, 
  exitType = NESTED_EXIT, 
  nativeCalleeWord = 0
}

We import with ngslots == 2, but in reality the anchor has 3 slots and it knows its a string. We merge in an int from the entry, which causes the assert die on.

Comment 24

[Andreas Gal :gal]

And the real bug is ...

Starting program: /Users/gal/workspace/tracemonkey-repository/js/src/Darwin_DBG.OBJ/js -j x.js
Reading symbols for shared libraries . done

Breakpoint 1, js_AttemptToExtendTree (cx=0x30bc70, anchor=0x458124, exitedFrom=0x2e1834, outer=0x0) at ../jstracer.cpp:4009
4009	            fullMap.add(getStackTypeMap(e1), e1->numStackSlotsBelowCurrentFrame);
(gdb) p *e1
$1 = {
  <nanojit::SideExit> = {
    guards = 0x458184, 
    from = 0x312350, 
    target = 0x313c60, 
    switchInfo = 0x0
  }, 
  members of VMSideExit: 
  block = 0x0, 
  pc = 0x30db08 "\b??ML\b??ML\b??Mû\003?\001g\004?`\004?`\004\027\a{4", 
  imacpc = 0x0, 
  sp_adj = 56, 
  rp_adj = 0, 
  calldepth = 0, 
  numGlobalSlots = 3, 
  numStackSlots = 7, 
  numStackSlotsBelowCurrentFrame = 0, 
  exitType = NESTED_EXIT, 
  nativeCalleeWord = 0
}
(gdb) p *e2
$2 = {
  <nanojit::SideExit> = {
    guards = 0x2e1894, 
    from = 0x30f030, 
    target = 0x0, 
    switchInfo = 0x0
  }, 
  members of VMSideExit: 
  block = 0x0, 
  pc = 0x30db08 "\b??ML\b??ML\b??Mû\003?\001g\004?`\004?`\004\027\a{4", 
  imacpc = 0x0, 
  sp_adj = 56, 
  rp_adj = 0, 
  calldepth = 0, 
  numGlobalSlots = 2, 
  numStackSlots = 7, 
  numStackSlotsBelowCurrentFrame = 0, 
  exitType = LOOP_EXIT, 
  nativeCalleeWord = 0
}
(gdb) 

We merge the type maps e1 and e2 and take e2's globals, but e2 happens to know about fewer globals (2), so we merge from the entry (giving us an int) instead of using the exit state, which is string.

            VMSideExit* e1 = anchor;
            VMSideExit* e2 = exitedFrom;
            fullMap.add(getStackTypeMap(e1), e1->numStackSlotsBelowCurrentFrame);
            fullMap.add(getStackTypeMap(e2), e2->numStackSlots);
            stackSlots = fullMap.length();
            fullMap.add(getGlobalTypeMap(e2), e2->numGlobalSlots);
            ngslots = e2->numGlobalSlots;
            typeMap = fullMap.data();

Comment 25

[Andreas Gal :gal]

Attachment: patch, with lots of help from graydon and danderson

Comment 27

[Andreas Gal :gal]

Pushed to TM.

http://hg.mozilla.org/tracemonkey/rev/ea72bb61b701

Comment 28

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/ea72bb61b701

Comment 29

[Henrik Skupin (:whimboo) [⌚️UTC+2]]

I have removed the fixed1.9.1 keyword due to the missing checkin of the followup patch.

Comment 30

[Andreas Gal :gal]

The original patch was backed out of TM and has to be removed from m-c and branch as well. Re-opening until thats confirmed.

http://hg.mozilla.org/tracemonkey/rev/47ae3c6dcf9e

Comment 31

[Robert Sayre]

backout on mozilla-central last night:
http://hg.mozilla.org/mozilla-central/rev/47ae3c6dcf9e

backout on 191 today:
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/bb49f28e12ad

Comment 32

[Robert Sayre]

final fix:
http://hg.mozilla.org/mozilla-central/rev/ea72bb61b701
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/a4629227dcc0

Comment 34

[Andreas Gal :gal]

Switching e2 and e1 causes this case to fail:

for each(c in [new Boolean(true), new Number(), new String, new Boolean(true),
new String(), new Boolean(true), new Boolean(true), new Number()]) {
    for each(a in [new String(), new String]) {
        print(c += (0 > c))
    }
}

Switching it back makes it pass. So we have to resolve the incompatibility here. Investigating.

Comment 35

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: merge two typemaps

It can happen that the innermost guard exits with different types than the outermost guard. In this case we should use all of the innermost types before using the missing outer types.

Comment 36

[Andreas Gal :gal]

Comment on attachment 381912 [details] [diff] [review]
merge two typemaps

the two global typemaps might have incompatible ordering. we have to be cautious how we merge them.

Comment 37

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: orders

Comment 38

[Andreas Gal :gal]

Comment on attachment 381916 [details] [diff] [review]
orders

>diff -r 42531a24b8c0 js/src/jstracer.cpp
>--- a/js/src/jstracer.cpp    Fri Jun 05 13:55:51 2009 -0700
>+++ b/js/src/jstracer.cpp    Sat Jun 06 02:22:10 2009 -0700
>@@ -4009,8 +4009,28 @@
>             fullMap.add(getStackTypeMap(e1), e1->numStackSlotsBelowCurrentFrame);
>             fullMap.add(getStackTypeMap(e2), e2->numStackSlots);
>             stackSlots = fullMap.length();
>+            /* Get initial globals */
>+            TreeInfo* ti_outer = (TreeInfo*)f->vmprivate;
>+            TreeInfo* ti_inner = (TreeInfo*)e2->from->root->vmprivate;
>             fullMap.add(getGlobalTypeMap(e1), e1->numGlobalSlots);
>-            ngslots = e1->numGlobalSlots;
>+            fullMap.captureMissingGlobalTypes(cx, *ti_outer->globalSlots, stackSlots);
>+            /* For each slot in e2 not in e1, add to e2's slotlist */

use inner and outer instead of e2 and e1.

>+            for (uint32 i = 0; i < ti_inner->globalSlots->length(); i++) {
>+                uint16 slot = ti_inner->globalSlots->data()[i];
>+                if (ti_outer->globalSlots->contains(slot))
>+                    continue;

At this point we know the slot is missing in the outer, and we know the index in outer, so we could just grab the type from there and add it to inner? (append)

>+                ti_outer->globalSlots->add(slot);
>+            }
>+            /* Merge e2's types in */
>+            uint32 pos;
>+            uint32 limit = JS_MIN(e2->numGlobalSlots, ti_inner->globalSlots->length());
>+            for (uint32 i = 0; i < limit; i++) {
>+                uint16 slot = ti_inner->globalSlots->data()[i];
>+                assert(ti_outer->globalSlots->contains(slot));
>+                ti_outer->globalSlots->find(slot, &pos);
>+                fullMap.data()[stackSlots + pos] = *(getGlobalTypeMap(e2) + i);
>+            }
>+            ngslots = ti_outer->globalSlots->length();
>             typeMap = fullMap.data();
>         }
>         JS_ASSERT(ngslots >= anchor->numGlobalSlots);
>diff -r 42531a24b8c0 js/src/jstracer.h
>--- a/js/src/jstracer.h    Fri Jun 05 13:55:51 2009 -0700
>+++ b/js/src/jstracer.h    Sat Jun 06 02:22:10 2009 -0700
>@@ -88,6 +88,16 @@
>         return false;
>     }
> 
>+    bool find(T a, unsigned* pos) {
>+        for (unsigned n = 0; n < _len; ++n) {
>+            if (_data[n] == a) {
>+                *pos = n;
>+                return true;
>+            }
>+        }
>+        return false;
>+    }
>+
>     void add(T a) {
>         ensure(_len + 1);
>         JS_ASSERT(_len <= _max);

Pretty close. Needs a little bit more work. Thanks for helping with this.

Comment 39

[Andreas Gal :gal]

Attachment: patch, broken

Comment 40

[David Anderson [:dvander] - inactive, e-mail if emergency]

Attachment: less confusing names

Comment 41

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

If there's a fix on m-c, isn't this bug FIXED?  Would be clearer to have another bug for follow-on work (esp for those of us tracking blockers).

Comment 42

[Andreas Gal :gal]

Fine by my either way. sayrer we land the patch. maybe jesse and gary could do some additional fuzzing to make sure we fixed it this time for real.

Comment 43

[Andreas Gal :gal]

Comment on attachment 381912 [details] [diff] [review]
merge two typemaps

The slot list is shared between related trees, so this should work after all.

Comment 44

[Andreas Gal :gal]

Comment on attachment 381969 [details] [diff] [review]
less confusing names

Order is fixed. No need for this more complicated patch.

Comment 45

[Andreas Gal :gal]

Followup patch is in bug 496743.

Comment 46

[Bob Clary [:bc:]]

testFewerGlobalsInInnerTree