493512 - js_GetUpvarOnTrace compares skip to callDepth, miscalculates callDepth

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Brendan Eich [:brendan]]

Will have a testcase and patch tomorrow. This is something dmandelin and I talked about but the code still has

    uintN skip = UPVAR_FRAME_SKIP(cookie);
    InterpState* state = cx->interpState;
    uintN callDepth = state->rp - state->callstackBase;

    /*
     * If we are skipping past all frames that are part of active traces,
     * then we simply get the value from the interpreter state.
     */
    if (skip > callDepth) {
        jsval v = js_GetUpvar(cx, level, cookie);

yet callDepth is (a) dynamic frame chain length in dimensionality, not static nesting level (delta); (b) missing all the frames inlined in the innermost tree, which do not advance state->rp.

Fixing (a) requires searching back in the FrameInfo pointers from the top of state->callstackBase down, looking for matching static level.

Fixing (b), which the fix for (a) depends on to find the true top of the FrameInfo* stack, requires passing the recorder's callDepth into the builtin, which makes me sad (another param). Unless someone has a better idea.

This should block.

/be

Comment 1

[Brendan Eich [:brendan]]

It's really hard to test this bug! The existing code, while wrong, generally does the right thing given common upvar patterns.

/be

Comment 2

[Blake Kaplan (:mrbkap) (inactive)]

I thought we decided that the code was conservatively incorrect (i.e. we'd bail if we were about to do the wrong thing and consequently do the right thing).

Comment 3

[Brendan Eich [:brendan]]

(In reply to comment #2)
> I thought we decided that the code was conservatively incorrect (i.e. we'd bail
> if we were about to do the wrong thing and consequently do the right thing).

I think we were wrong. Problem (b) is bad because we will use the wrong FrameInfo, and (a) means we will misjudge skip <= callDepth if outer tree frames outnumber static nesting levels by enough.

But if you can prove (like, induction and stuff ;-) that the code is safe, lay it on us. The dimensional analysis is broken, so I think we are just lucky.

/be

Comment 4

[Brendan Eich [:brendan]]

Attachment: work in progress

Comment 5

[David Mandelin [:dmandelin]]

Attachment: Patch

This is just the original patch with a test case. 

The test case appears not to test the expected failure mode, which is using the wrong access code (interpreter vs. native). Instead, it seems that when callDepth > skip, because we are using the wrong callDepth (because rp is not up to date), we look in the wrong frame and get the wrong value. 

perf on the original shell test case for go is about 10% worse than before (still much faster than non-tracing). I think the nested loops could be avoided in js_GetUpVarOnTrace but I think we have more important things to worry about right now.

Comment 6

[Jason Orendorff [:jorendorff]]

With the patch, the test below fails with -j.

crasher.js:21: TypeError: Assertion failed: got "50,100,5555,5555,", expected "50,100,150,200,"

For some reason js_GetUpvarOnTrace is getting a instead of k.


var actual = '';

function f(a, b, c, k) {
    function g() {
        var sum = 0;
        for (var i = 0; i < 5; ++i)
            sum += k;
        actual = actual + sum + ',';
    }
    g();
}

function test() {
    for (var i = 10; i < 50; i += 10)
        f(1111, 2, 3, i);
    assertEq(actual, '50,100,150,200,');
}

test();

Comment 7

[David Mandelin [:dmandelin]]

Attachment: Patch v2

It seems to have required just some fixing of the arithmetic to fix jorendorff's bug. That bug is also present on tip.

Comment 8

[Andreas Gal :gal]

Comment on attachment 378756 [details] [diff] [review]
Patch v2

>diff -r 429aa7a066c0 js/src/jstracer.cpp
>--- a/js/src/jstracer.cpp    Wed May 20 10:10:03 2009 -0500
>+++ b/js/src/jstracer.cpp    Wed May 20 18:11:26 2009 -0700
>@@ -1839,49 +1839,59 @@ FlushNativeGlobalFrame(JSContext* cx, un
> }
> 
> /*
>  * Builtin to get an upvar on trace. See js_GetUpvar for the meaning
>  * of the first three arguments. The value of the upvar is stored in
>  * *result as an unboxed native. The return value is the typemap type.
>  */
> uint32 JS_FASTCALL
>-js_GetUpvarOnTrace(JSContext *cx, uint32 level, uint32 cookie, double* result)
>+js_GetUpvarOnTrace(JSContext* cx, uint32 level, uint32 cookie, uint32 callDepth, double* result)
> {
>     uintN skip = UPVAR_FRAME_SKIP(cookie);
>+    uintN upvarLevel = level - skip;
>     InterpState* state = cx->interpState;
>-    uintN callDepth = state->rp - state->callstackBase;
>-
>-    /*
>-     * If we are skipping past all frames that are part of active traces,
>+    FrameInfo** fip = state->rp + callDepth;
>+
>+    /*
>+     * First search the FrameInfo call stack for an entry containing
>+     * our upvar, namely one with staticLevel == upvarLevel.
>+     */
>+    while (--fip >= state->callstackBase) {
>+        FrameInfo* fi = *fip;
>+        JSFunction* fun = GET_FUNCTION_PRIVATE(cx, fi->callee);
>+        uintN calleeLevel = fun->u.i.script->staticLevel;
>+        if (calleeLevel == upvarLevel) {
>+            /*
>+             * Now find the upvar's value in the native stack.
>+             * nativeStackFramePos is the offset of the start of the 
>+             * activation record corresponding to *fip in the native
>+             * stack.
>+             */
>+            uintN nativeStackFramePos = state->callstackBase[0]->caller_argc;
>+            for (FrameInfo** fip2 = state->callstackBase; fip2 <= fip; fip2++)
>+                nativeStackFramePos += (*fip2)->s.spdist;
>+            nativeStackFramePos -= (2 + (*fip)->s.argc);
>+            uint8* typemap = (uint8*) (fi+1);
>+
>+            uintN slot = UPVAR_FRAME_SLOT(cookie);
>+            slot = (slot == CALLEE_UPVAR_SLOT) ? 0 : 2/*callee,this*/ + slot;
>+            *result = state->stackBase[nativeStackFramePos + slot];
>+            return typemap[slot];
>+        }
>+    }
>+
>+    /*
>+     * If we did not find the upvar in the frames for the active traces,
>      * then we simply get the value from the interpreter state.
>      */
>-    if (skip > callDepth) {
>-        jsval v = js_GetUpvar(cx, level, cookie);
>-        uint8 type = getCoercedType(v);
>-        ValueToNative(cx, v, type, result);
>-        return type;
>-    }
>-
>-    /*
>-     * The value we need is logically in a stack frame that is part of
>-     * an active trace. We reconstruct the value we need from the tracer
>-     * stack records.
>-     */
>-    uintN frameIndex = callDepth - skip; // pos of target frame in rp stack
>-    uintN nativeStackFramePos = 0; // pos of target stack frame in sp stack
>-    for (uintN i = 0; i < frameIndex; ++i)
>-        nativeStackFramePos += state->callstackBase[i]->s.spdist;
>-    FrameInfo* fi = state->callstackBase[frameIndex];
>-    uint8* typemap = (uint8*) (fi+1);
>-
>-    uintN slot = UPVAR_FRAME_SLOT(cookie);
>-    slot = slot == CALLEE_UPVAR_SLOT ? 0 : slot + 2;
>-    *result = state->stackBase[nativeStackFramePos + slot];
>-    return typemap[slot];
>+    jsval v = js_GetUpvar(cx, level, cookie);
>+    uint8 type = getCoercedType(v);
>+    ValueToNative(cx, v, type, result);
>+    return type;
> }
> 
> /**
>  * Box the given native stack frame into the virtual machine stack. This
>  * is infallible.
>  *
>  * @param callDepth the distance between the entry frame into our trace and
>  *                  cx->fp when we make this call.  If this is not called as a
>@@ -8364,17 +8374,18 @@ TraceRecorder::record_JSOP_CALLNAME()
> 
>     JS_ASSERT(HAS_FUNCTION_CLASS(PCVAL_TO_OBJECT(pcval)));
> 
>     stack(0, INS_CONSTPTR(PCVAL_TO_OBJECT(pcval)));
>     stack(1, obj_ins);
>     return JSRS_CONTINUE;
> }
> 
>-JS_DEFINE_CALLINFO_4(extern, UINT32, js_GetUpvarOnTrace, CONTEXT, UINT32, UINT32, DOUBLEPTR, 0, 0)
>+JS_DEFINE_CALLINFO_5(extern, UINT32, js_GetUpvarOnTrace, CONTEXT, UINT32, UINT32, UINT32,
>+                     DOUBLEPTR, 0, 0)
> 
> JS_REQUIRES_STACK JSRecordingStatus
> TraceRecorder::record_JSOP_GETUPVAR()
> {
>     uintN index = GET_UINT16(cx->fp->regs->pc);
>     JSScript *script = cx->fp->script;
> 
>     JSUpvarArray* uva = JS_SCRIPT_UPVARS(script);
>@@ -8392,18 +8403,19 @@ TraceRecorder::record_JSOP_GETUPVAR()
> 
>     /*
>      * The upvar is not in the current trace, so get the upvar value 
>      * exactly as the interpreter does and unbox.
>      */
>     LIns* outp = lir->insAlloc(sizeof(double));
>     LIns* args[] = { 
>         outp,
>-        lir->insImm(uva->vector[index]), 
>-        lir->insImm(script->staticLevel), 
>+        INS_CONST(callDepth),
>+        INS_CONST(uva->vector[index]), 
>+        INS_CONST(script->staticLevel), 
>         cx_ins 
>     };
>     const CallInfo* ci = &js_GetUpvarOnTrace_ci;
>     LIns* call_ins = lir->insCall(ci, args);
>     uint8 type = getCoercedType(v);
>     guard(true,
>           addName(lir->ins2(LIR_eq, call_ins, lir->insImm(type)),
>                   "guard(type-stable upvar)"),
>@@ -8525,16 +8537,17 @@ TraceRecorder::interpretedFunctionCall(j
>         ABORT_TRACE("too many arguments");
> 
>     fi->callee = JSVAL_TO_OBJECT(fval);
>     fi->block = fp->blockChain;
>     fi->pc = fp->regs->pc;
>     fi->imacpc = fp->imacpc;
>     fi->s.spdist = fp->regs->sp - fp->slots;
>     fi->s.argc = argc | (constructing ? 0x8000 : 0);
>+    fi->caller_argc = 2 + fp->argc;

caller_argc is a bad name, since its argc + 2.

> 
>     unsigned callDepth = getCallDepth();
>     if (callDepth >= treeInfo->maxCallDepth)
>         treeInfo->maxCallDepth = callDepth + 1;
> 
>     lir->insStorei(INS_CONSTPTR(fi), lirbuf->rp, callDepth * sizeof(FrameInfo*));
> 
>     atoms = fun->u.i.script->atomMap.vector;
>diff -r 429aa7a066c0 js/src/jstracer.h
>--- a/js/src/jstracer.h    Wed May 20 10:10:03 2009 -0500
>+++ b/js/src/jstracer.h    Wed May 20 18:11:26 2009 -0700
>@@ -293,16 +293,17 @@ struct FrameInfo {
>     jsbytecode*     imacpc;     // caller fp->imacpc
>     union {
>         struct {
>             uint16  spdist;     // distance from fp->slots to fp->regs->sp at JSOP_CALL
>             uint16  argc;       // actual argument count, may be < fun->nargs
>         } s;
>         uint32      word;       // for spdist/argc LIR store in record_JSOP_CALL
>     };
>+    uint32          caller_argc;   // fp->argv - stackBase
> };
> 
> struct UnstableExit
> {
>     nanojit::Fragment* fragment;
>     VMSideExit* exit;
>     UnstableExit* next;
> };
>diff -r 429aa7a066c0 js/tests/js1_8_1/regress/regress-493512-1.js
>--- /dev/null    Thu Jan 01 00:00:00 1970 +0000
>+++ b/js/tests/js1_8_1/regress/regress-493512-1.js    Wed May 20 18:11:26 2009 -0700
>@@ -0,0 +1,76 @@
>+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
>+/* ***** BEGIN LICENSE BLOCK *****
>+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
>+ *
>+ * The contents of this file are subject to the Mozilla Public License Version
>+ * 1.1 (the "License"); you may not use this file except in compliance with
>+ * the License. You may obtain a copy of the License at
>+ * http://www.mozilla.org/MPL/
>+ *
>+ * Software distributed under the License is distributed on an "AS IS" basis,
>+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
>+ * for the specific language governing rights and limitations under the
>+ * License.
>+ *
>+ * The Original Code is JavaScript Engine testing utilities.
>+ *
>+ * The Initial Developer of the Original Code is
>+ * Mozilla Foundation.
>+ * Portions created by the Initial Developer are Copyright (C) 2007
>+ * the Initial Developer. All Rights Reserved.
>+ *
>+ * Contributor(s): Dave Mandelin
>+ *
>+ * Alternatively, the contents of this file may be used under the terms of
>+ * either the GNU General Public License Version 2 or later (the "GPL"), or
>+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
>+ * in which case the provisions of the GPL or the LGPL are applicable instead
>+ * of those above. If you wish to allow use of your version of this file only
>+ * under the terms of either the GPL or the LGPL, and not to allow others to
>+ * use your version of this file under the terms of the MPL, indicate your
>+ * decision by deleting the provisions above and replace them with the notice
>+ * and other provisions required by the GPL or the LGPL. If you do not delete
>+ * the provisions above, a recipient may use your version of this file under
>+ * the terms of any one of the MPL, the GPL or the LGPL.
>+ *
>+ * ***** END LICENSE BLOCK ***** */
>+
>+var gTestfile = 'regress-493512-1.js';
>+//-----------------------------------------------------------------------------
>+var BUGNUMBER = 493512;
>+var summary = 'Incorrect selection of upvar access code in js_GetUpVarTrace';
>+var actual = ''
>+var expect = '50,100,150,200,';
>+
>+
>+//-----------------------------------------------------------------------------
>+function f(k) {
>+  function g() {
>+    var sum = 0;
>+    for (var i = 0; i < 5; ++i)
>+      sum += k;
>+    actual = actual + sum + ',';
>+  }
>+
>+  g();
>+}
>+
>+test();
>+//-----------------------------------------------------------------------------
>+
>+function test()
>+{
>+  enterFunc ('test');
>+  printBugNumber(BUGNUMBER);
>+  printStatus (summary);
>+
>+  jit(true);
>+  for (var i = 10; i < 50; i += 10) {
>+    f(i);
>+  }
>+  jit(false);
>+
>+  reportCompare(expect, actual, summary);
>+
>+  exitFunc ('test');
>+}
>diff -r 429aa7a066c0 js/tests/js1_8_1/regress/regress-493512-2.js
>--- /dev/null    Thu Jan 01 00:00:00 1970 +0000
>+++ b/js/tests/js1_8_1/regress/regress-493512-2.js    Wed May 20 18:11:26 2009 -0700
>@@ -0,0 +1,76 @@
>+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
>+/* ***** BEGIN LICENSE BLOCK *****
>+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
>+ *
>+ * The contents of this file are subject to the Mozilla Public License Version
>+ * 1.1 (the "License"); you may not use this file except in compliance with
>+ * the License. You may obtain a copy of the License at
>+ * http://www.mozilla.org/MPL/
>+ *
>+ * Software distributed under the License is distributed on an "AS IS" basis,
>+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
>+ * for the specific language governing rights and limitations under the
>+ * License.
>+ *
>+ * The Original Code is JavaScript Engine testing utilities.
>+ *
>+ * The Initial Developer of the Original Code is
>+ * Mozilla Foundation.
>+ * Portions created by the Initial Developer are Copyright (C) 2007
>+ * the Initial Developer. All Rights Reserved.
>+ *
>+ * Contributor(s): Dave Mandelin
>+ *
>+ * Alternatively, the contents of this file may be used under the terms of
>+ * either the GNU General Public License Version 2 or later (the "GPL"), or
>+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
>+ * in which case the provisions of the GPL or the LGPL are applicable instead
>+ * of those above. If you wish to allow use of your version of this file only
>+ * under the terms of either the GPL or the LGPL, and not to allow others to
>+ * use your version of this file under the terms of the MPL, indicate your
>+ * decision by deleting the provisions above and replace them with the notice
>+ * and other provisions required by the GPL or the LGPL. If you do not delete
>+ * the provisions above, a recipient may use your version of this file under
>+ * the terms of any one of the MPL, the GPL or the LGPL.
>+ *
>+ * ***** END LICENSE BLOCK ***** */
>+
>+var gTestfile = 'regress-493512-2.js';
>+//-----------------------------------------------------------------------------
>+var BUGNUMBER = 493512;
>+var summary = 'Incorrect selection of upvar access code in js_GetUpVarTrace';
>+var actual = ''
>+var expect = '50,100,150,200,';
>+
>+
>+//-----------------------------------------------------------------------------
>+function f(a, b, c, k) {
>+  function g() {
>+    var sum = 0;
>+    for (var i = 0; i < 5; ++i)
>+      sum += k;
>+    actual = actual + sum + ',';
>+  }
>+
>+  g();
>+}
>+
>+test();
>+//-----------------------------------------------------------------------------
>+
>+function test()
>+{
>+  enterFunc ('test');
>+  printBugNumber(BUGNUMBER);
>+  printStatus (summary);
>+
>+  jit(true);
>+  for (var i = 10; i < 50; i += 10) {
>+    f(1111, 2, 3, i);
>+  }
>+  jit(false);
>+
>+  reportCompare(expect, actual, summary);
>+
>+  exitFunc ('test');
>+}

Comment 9

[David Mandelin [:dmandelin]]

Arg. Pushed to TM as f8604711e560 because I didn't see gal wanted a rename in all that diff spew. I guess anyone can suggest a name and/or patch the code.

For posterity, I documented the TM native stack layout: 
http://people.mozilla.org/~dmandelin/tmact.pdf

Comment 10

[Brendan Eich [:brendan]]

Canonical name is vplen given vp = argv - 2. But no vp in sight here. gross_argc?

/be

Comment 11

[Andreas Gal :gal]

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

Comment 12

[Brendan Eich [:brendan]]

Argh, that union with the uint32 word overlaying the bit-fields is archaic, from when we didn't memoize FrameInfo, rather emitted LIR to store it when inlining on trace. That should all get ripped out, along with the caller_argc renaming (vplen is probably the right name). New bug?

/be

Comment 13

[Andreas Gal :gal]

This passes trace-tests on x86. Trying arm next.

Comment 14

[Andreas Gal :gal]

The failure on ARM looks very strongly like a backend bug.

We are not hitting the asm_add_imm path here for some reason.

                       if (arg->isop(LIR_alloc)) {
                            asm_add_imm(r, FP, d);
                        } else {
                            LDR(r, FP, d);
                        }

We can unblock for FF 3.5rc1/x86 on this. I will try to get final confirmation shortly.

Comment 15

[Robert Sayre]

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

Comment 16

[Robert Sayre]

http://hg.mozilla.org/releases/mozilla-1.9.1/rev/52ff5a22a46a

Comment 17

[Bob Clary [:bc] (inactive)]

dmandlin, did you forget the tests?


> >+++ b/js/tests/js1_8_1/regress/regress-493512-1.js    Wed May 20 18:11:26 
> >+++ b/js/tests/js1_8_1/regress/regress-493512-2.js    Wed May 20 18:11:26