Closed Bug 466905 Opened 11 years ago Closed 11 years ago

Fix JSOP_NEWARRAY to be not-buggy and use it

Categories

(Core :: JavaScript Engine, defect, P1, critical)

defect

Tracking

()

VERIFIED FIXED

People

(Reporter: jruderman, Assigned: Waldo)

References

(Blocks 1 open bug)

Details

(Keywords: assertion, testcase, verified1.9.1, Whiteboard: fixed-in-tracemonkey)

Attachments

(1 file, 4 obsolete files)

function f(a) { for each (let c in a) [(c > 5) ? 'A' : 'B']; }
f([true, 8]);
f([2]);

Assertion failure: v_ins->isCall() && v_ins->callInfo() == &js_FastNewArray_ci, at ../jstracer.cpp:6981

This testcase doesn't crash opt, but a more complicated one does.
Flags: blocking1.9.1?
Flags: blocking1.9.1? → blocking1.9.1+
Assignee: general → jwalden+bmo
Priority: -- → P1
A simpler testcase:

for (var i = 0; i < 5; i++)
  [(i > 3) ? 'a' : 'b'];

The particular instruction referred to in the assertion is a LIR_ld.  I'm not entirely sure where it's coming from yet, but it almost looks like we're entering a trace after the array has been constructed.  More investigation to do yet...
Status: NEW → ASSIGNED
So this is kind of whacked, we're creating an array both by 1str and by FastNewArray, not just 1str.  More investigation to do still...

    obj
    js_FastNewArray1 = js_FastNewArray ( cx obj )

    eq1 = eq js_FastNewArray1, 0
    xt1: xt eq1 -> 0:11 sp+0 rp+0

import vp=0x200bb2c name=$global0 type=int flags=0
    sti sp[0] = js_FastNewArray1
    #0:0 /* 0 */
    sti sp[8] = 0
    632
    ld1 = ld gp[632]
    $global0 = i2f ld1
    sti sp[16] = ld1
    #40080000:0 /* 3 */
    3
    sti sp[24] = 3
    gt1 = gt ld1, 3
    xt2: xt gt1 -> 0:19 sp+32 rp+0

    sti sp[16] = gt1
    ATOM_TO_STRING(atom)
    sti sp[16] = ATOM_TO_STRING(atom)
    #0x81d5c4
    ld2 = ld js_FastNewArray1[JSVAL_STRING]
    -4
    and1 = and ld2, -4
    clasp
    guard(class is Array) = eq and1, clasp
    xf1: xf guard(class is Array) -> 0:32 sp+24 rp+0

    js_Array_dense_setelem1 = js_Array_dense_setelem ( cx js_FastNewArray1 0 #0x81d5c4 )
    eq2 = eq js_Array_dense_setelem1, 0
    xt3: xt eq2 -> 0:32 sp+24 rp+0

    js_Array_1str1 = js_Array_1str ( cx obj ATOM_TO_STRING(atom) )
    sti sp[0] = js_Array_1str1
    #3FF00000:0 /* 1 */
    1
    add1 = add ld1, 1
    ov1 = ov add1
    xt4: xt ov1 -> 0:35 sp+0 rp+0
Okay, that's just a whack optimization because we don't have JSOP_NEWARRAY, or so saith the comment in JSOP_ENDINIT.  I knew we should have had two opcodes for the different literals when I implemented JSOP_NEWINIT.  :-P  Still more to go, but maybe it makes sense to implement that now if that's the root of the problem here...
Okay, so...

We trace through the loop when i is too low, then we start trying to trace the loop when i > 3 (I think when we hit i==4, after side-exiting twice there), but since that's after a side exit we have to load the array value created by record_JSOP_NEWINIT from memory, so of course it's not something where we had the original js_FastNewArray call instruction to inspect.  Since we need that to do the 1str rewrite (to get the JSProto, it seems -- but that's kinda bogus, why does js_FastNewArray even require that?  it's given the cx, should be able to look up Array.prototype given that), without the instruction being a js_FastNewArray call we can't optimize here.

I think we have a couple choices.  We could do JSOP_NEWARRAY now and optimize more sanely.  We could also make the various Array native methods not require passing in a proto so we can just recalculate from the cx, in which case we wouldn't need to require having the original js_FastNewArray call around.  We could also only apply the optimization if the instruction's not a js_FastNewArray call, as occurs here when we're following a side exit from the original trace.  Not sure yet which makes the most sense...
Thoughts on comment 4 appreciated.  I think I lean toward JSOP_NEWARRAY right now...
I think we should do the Array-methods-don't-need-proto thing too, but perhaps not necessarily for this bug but rather just for general code simplicity reasons.
Please do try to get JSOP_NEWARRAY selected (see the FIXME -- one line change) in the emitter. Test heavily on Windows. Latent bug shaver and I never figured out, may be fixed by now.

Andreas reminded me a while back that looking upstream for a certain built-in to identify a source form such as an initialiser is not safe in general -- SSA means you could be looking back across some propagated copy of a constant. Anyway, this was back in the apply hacking days of August or September. js_Array_1str is from then (ugly name is tell-tale). We should clean this up sooner, not later.

/be
Summary: TM: "Assertion failure: v_ins->isCall() && v_ins->callInfo() == &js_FastNewArray_ci" → Fix JSOP_NEWARRAY to be not-buggy and use it
Attached patch Beginnings of a patch (obsolete) — Splinter Review
This crashes in trace-test.js in joinTest (and quite possibly in other tests, too), so there's more things to fix still.  The recording of JSOP_NEWARRAY is rather braindead now, and it may be worth rewriting to JS_malloc a dslots array and populate it to swap directly into place and avoid a whole lot of function calls, but that's conceivably followup-land (or at least not first-pass material in a preliminary patch).
Obvious mistake in previous, need to box_jsval the value to be set in the array.  Now time for decompiler love...
I think this is done based on what I've seen on OS X, but the original JSOP_NEWARRAY problems were on Windows, so need to test there.  I also still need to run the full testsuite, but this addresses the problems raised by a full run against the previous patch, which bodes well for this patch's readiness.

Test fodder (note the last two cases in particular, since the very last one is a bug in current source):

js> [                                
function() { return []; },
function() { return [1]; },
function() { return [1, ]; },
function() { return [1, 2]; },
function() { return [1, , 3]; },
function() { return [1, , 3, ]; },
function() { return [(a, b)]; },
function() { return foo((a, b)); },
]
function () {
    return [];
},function () {
    return [1];
},function () {
    return [1, ];
},function () {
    return [1, 2];
},function () {
    return [1, , 3];
},function () {
    return [1, , 3, ];
},function () {
    return [(a, b)];
},function () {
    return foo((a, b));
}
Attachment #355623 - Attachment is obsolete: true
Comment on attachment 355710 [details] [diff] [review]
Patch, still need to run testsuite and test on Windows

>+                    char** argv = (char **)

Already have char **argv at top level of Decompile (old-school, C code), no need for this (yet -- C++ beautification in general can wait, particular wins ok but this ain't one of them).

>+                    i = argc;
>+                    while (i-- > 0) {

Nit: --i >= 0 is better, although the compiler should rewrite for you (i and argc are jsint; pre-decrement avoids a temp).

Looks good otherwise (I need to read record_JSOP_NEWARRAY when I'm not tired).

/be
I don't like --i >= 0 because it's buggy if i ever changes from signed to unsigned; i-- > 0 does not have this problem.  They optimize to the same thing anyway, so I think (potential) correctness concerns should trump here.

This iteration modifies dslots directly in the same manner that call/apply tracing does, so there's no longer any per-element function call overhead.  It also moves op-setting a little closer to the implicit (ugh) use of the definition in call/newarray decompilation.

I still think proto-passing behavior for the array-creation functions needs to go away, and the box_jsval change suggests that unbox_jsval should be made failsafe too, but those should be separate cleanup bugs.
Attachment #355710 - Attachment is obsolete: true
Attachment #355855 - Flags: review?(brendan)
(In reply to comment #12)
> Created an attachment (id=355855) [details]
> Still needs Windows testing but otherwise good to go
> 
> I don't like --i >= 0 because it's buggy if i ever changes from signed to
> unsigned;

Don't do that (why would you?).

"Dr., it hurts when I do this" (hits self on head with hammer)...

> i-- > 0 does not have this problem.  They optimize to the same thing
> anyway, so I think (potential) correctness concerns should trump here.

The mental optimization is a burden for some. Used postfix increment/decrement expressions are generally frowned upon in SpiderMonkey.

> I still think proto-passing behavior for the array-creation functions needs to
> go away,

Why? Or: how? The right prototype must be picked at runtime.

> and the box_jsval change suggests that unbox_jsval should be made
> failsafe too, but those should be separate cleanup bugs.

Please file.

/be
Attached patch Again (obsolete) — Splinter Review
(In reply to comment #13)
> Don't do that (why would you?).

argc and derived variables are counts that are inherently unsigned values, which makes me think of them as such regardless of their concrete type.

> The mental optimization is a burden for some. Used postfix increment/decrement
> expressions are generally frowned upon in SpiderMonkey.

How's the change here instead, which avoids pre-decrement:

> -                while (i-- > 0) {
> -                    argv[i] = JS_strdup(cx, POP_STR());
> +                while (i > 0) {
> +                    argv[--i] = JS_strdup(cx, POP_STR());
>                      if (!argv[i])
>                          ok = JS_FALSE;
>                  }


> Why? Or: how? The right prototype must be picked at runtime.

We already pass the context in, we should derive it form that in the native functions, rather than forcing every caller to do that.  When I last looked all callers were passing the same prototype, so this simplify life for them.
Attachment #355855 - Attachment is obsolete: true
Attachment #355879 - Flags: review?(brendan)
Attachment #355855 - Flags: review?(brendan)
Comment on attachment 355879 [details] [diff] [review]
Again

>From: Jeff Walden <jwalden@mit.edu>
>
>+                argv = (char **) JS_malloc(cx, size_t(argc) * sizeof(*argv));

Nit: don't change sizeof expr style (by parenthesizing sizeof's operand).

No whining from me about the C++ size_t(argc) cast tho ;-).

>+                i = argc;
>+                while (i > 0) {
>+                    argv[--i] = JS_strdup(cx, POP_STR());

Better, no problem since i is not used on the RHS.

>+                sn = js_GetSrcNote(jp->script, pc);
>+                if (sn && SN_TYPE(sn) == SRC_CONTINUE &&
>+                    SprintCString(&ss->sprinter, ", ") < 0)
>+                    return NULL;

Prevailing style overbraces then- and else-clauses if any of condition, then, or else takes more than one line. But here you could use the tw=99 new world order and fit on one line, no?

>+/**

What's this Java-based noise? :-P

Seriously, why?

>+ * Constructs

Better style to say "Construct", use imperative mood.

>               a new dense array whose contents are the values provided on the
>+ * stack, consuming those values and replacing them with the newly-constructed
>+ * array.  The topmost value is the last value in the new array, and the
>+ * bottommost value is the first value in the array; the array length is a
>+ * 24-bit operand to the instruction.

s/operand/immediate &/

>  */
> OPDEF(JSOP_NEWARRAY,      230, "newarray",     NULL,  4, -1,  1, 19,  JOF_UINT24)
>+
>+/**
>+ * Pushes

Ditto.

            a JSVAL_HOLE value onto the stack, representing a property which is

"that is" -- "that" not "which" for defining clauses (see Strunk&White, Barzun, others).

> TraceRecorder::record_JSOP_NEWARRAY()
> {
>-    return false;
>+    JSObject* proto;
>+    const CallInfo* ci = &js_NewUninitializedArray_ci;
>+    if (!js_GetClassPrototype(cx, globalObj, INT_TO_JSID(JSProto_Array), &proto))
>+        return false;

I mentioned this but I think I got the problem backward, and jorendorff and I have been over this before, but I don't remember a followup bug being filed. If we burn the Array.prototype as an immediate into the trace:

>+    uint32 len = GET_UINT24(cx->fp->regs->pc);
>+    LIns* args[] = { lir->insImm(len), INS_CONSTPTR(proto), cx_ins };

Then when the trace is triggered for a different global object (of the required shape) we'll make an array with the wrong proto -- possibly an XSS hole here. Comments?

/be
find-waldo-now:~/moz/shell-js/js/src jwalden$ ./js -j
js> function createArray()
{
  var a;                
  for (var i = 0; i < 10; i++)
    a = [1, 2, 3, 4, 5];
  return a;
}
js> var sandbox = evalcx("lazy");
js> sandbox.createArray = createArray; undefined
js> var p1 = Object.getPrototypeOf(createArray());
js> var p2 = Object.getPrototypeOf(evalcx("createArray()", sandbox));
js> print(p1 === p2)


My intuition fails me on this last statement; should the answer be true?  (It is currently.)  I think so, but I'm not sure.

I'm having trouble getting two sandboxes with the same shape to try to test the trace-triggering question.  I have no idea how to explain this problem; hopefuly the problem is obvious, so could someone point it out?

find-waldo-now:~/moz/shell-js/js/src jwalden$ ./js -j
js> var s1 = evalcx("lazy"), s2 = evalcx("lazy");
js> shapeOf(s1)
12
js> shapeOf(s2)
13
I like /**-style comments because the ** serves as a very lightweight form of sectioning (for cases where you have sections -- between opcodes here, before methods but not within them, &c.), in my opinion, but I don't care that strongly.

This Mochitests well on Windows, and I think it's ready to go.
Attachment #355879 - Attachment is obsolete: true
Attachment #356267 - Flags: review?(brendan)
Attachment #355879 - Flags: review?(brendan)
(The evalcx problem mentioned before was fixed in a rubberstamp commit, the problem being we were destroying the sandbox context and GCing, which bumped the shape of the object.  After more discussion I think we agree that the proto burned in is the correct one, so I think we're good on that account.)
Bug 419743 was about a similar op, JSOP_CONCATN, that was bitten by the undiagnosed Windows-only stack budgeting bug. Maybe it is WFM now too?
Comment on attachment 356267 [details] [diff] [review]
Now with Windows testing

>+                ok = JS_TRUE;
>+                i = argc;
>+                while (i > 0) {
>+                    argv[--i] = JS_strdup(cx, POP_STR());
>+                    if (!argv[i])
>+                        ok = JS_FALSE;
>+                }
>+
>+                todo = SprintCString(&ss->sprinter, "[");
>+                if (todo < 0)
>+                    break;
>+
>+                for (i = 0; i < argc; i++) {
>+                    if (!argv[i] ||
>+                        Sprint(&ss->sprinter, ss_format,
>+                               argv[i], (i < argc - 1) ? ", " : "") < 0) {
>+                        ok = JS_FALSE;

Duh for not noticing sooner, but we could either (a) avoid 'if (!argv[i]) ok = JS_FALSE;' up above and make the JS_strdup loop a two-liner; or (b) put a big if (ok) { ... } around the two paragraphs that follow (ending just before the JS_free loop).

>+                        break;
>+                    }
>+                }
>+
>+                for (i = 0; i < argc; i++) {
>+                    if (argv[i])
>+                        JS_free(cx, argv[i]);

This can be a two-line loop too, since JS_free is null-safe.

Please shrink the code a bit here and for JSOP_CALL/EVAL/APPLY -- my vote is for two-line strdup and free loops, since OOM is rare, to minimize code size and indentation. In fact that's more than a vote, it's clearly better than a big if (ok) { ... } that overindents the common case and worrys about OOM too early.

r=me with this.

/be
Fixed in TM:

http://hg.mozilla.org/tracemonkey/rev/6475993319c4
http://hg.mozilla.org/tracemonkey/rev/71e7b627ed31
OS: Mac OS X → All
Hardware: x86 → All
Whiteboard: fixed-in-tracemonkey
Depends on: 473096
Attachment #356267 - Flags: review?(brendan) → review+
http://hg.mozilla.org/mozilla-central/rev/6475993319c4
Status: ASSIGNED → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
(In reply to comment #10)
> 
> Test fodder (note the last two cases in particular, since the very last one is
> a bug in current source):

Waldo, what is the success/failure criteria for this?
If you convert the given array to a string (implicitly done by the shell in the example, note the array is typed at a shell prompt), you get the printed values demonstrated there.  The array's not the important part here, it's just the container for decompiling more than one function at once -- each function should decompile as demonstrated there, with the usual munging to ignore whitespace and such.
http://hg.mozilla.org/mozilla-central/rev/0e1a5ffcfac1
Flags: in-testsuite+
Flags: in-litmus-
js1_8_1/regress/regress-466905-01.js
js1_8_1/regress/regress-466905-02.js
js1_8_1/decompilation/regress-466905-03.js
js1_8_1/extensions/regress-466905-04.js
js1_8_1/extensions/regress-466905-05.js

v 1.9.1, 1.9.2
Status: RESOLVED → VERIFIED
You need to log in before you can comment on or make changes to this bug.