1199345 - Assertion failure: i < (1 << 24), at mozilla-central/js/src/jsopcode.h:214

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[André Bargull [:anba]]

Test case:
---
Function(`return [${",".repeat(16777215 + 1)}].length`)()
---

Assertion failure: i < (1 << 24), at /home/andre/hg/mozilla-central/js/src/jsopcode.h:214


Stack trace:
---
#0  0x0000000000666de2 in SET_UINT24 (pc=0x7ffff3c16800 "Z", i=16777216) at /home/andre/hg/mozilla-central/js/src/jsopcode.h:214
#1  0x00000000006a2509 in js::frontend::BytecodeEmitter::emitArray (this=0x7fffffffbbf8, pn=0x7ffff698a178, count=16777216, op=JSOP_NEWARRAY)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeEmitter.cpp:7267
#2  0x00000000006a4ab5 in js::frontend::BytecodeEmitter::emitTree (this=0x7fffffffbbf8, pn=0x7ffff698a140)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeEmitter.cpp:8005
#3  0x0000000000691b8b in js::frontend::BytecodeEmitter::emitPropLHS (this=0x7fffffffbbf8, pn=0x7fffb7485f70)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeEmitter.cpp:2578
#4  0x0000000000691c89 in js::frontend::BytecodeEmitter::emitPropOp (this=0x7fffffffbbf8, pn=0x7fffb7485f70, op=JSOP_GETPROP)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeEmitter.cpp:2598
#5  0x00000000006a4506 in js::frontend::BytecodeEmitter::emitTree (this=0x7fffffffbbf8, pn=0x7fffb7485f70)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeEmitter.cpp:7879
#6  0x000000000069e121 in js::frontend::BytecodeEmitter::emitReturn (this=0x7fffffffbbf8, pn=0x7fffb7485fa8)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeEmitter.cpp:6096
#7  0x00000000006a3f37 in js::frontend::BytecodeEmitter::emitTree (this=0x7fffffffbbf8, pn=0x7fffb7485fa8)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeEmitter.cpp:7711
#8  0x000000000069f431 in js::frontend::BytecodeEmitter::emitStatementList (this=0x7fffffffbbf8, pn=0x7ffff698a108, top=0)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeEmitter.cpp:6373
#9  0x00000000006a3fe0 in js::frontend::BytecodeEmitter::emitTree (this=0x7fffffffbbf8, pn=0x7ffff698a108)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeEmitter.cpp:7728
#10 0x00000000006a3d15 in js::frontend::BytecodeEmitter::emitTree (this=0x7fffffffbbf8, pn=0x7ffff698a058)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeEmitter.cpp:7658
#11 0x0000000000694c62 in js::frontend::BytecodeEmitter::emitFunctionScript (this=0x7fffffffbbf8, body=0x7ffff698a058)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeEmitter.cpp:3437
#12 0x000000000068876d in BytecodeCompiler::compileFunctionBody (this=0x7fffffffaf40, fun=..., formals=..., generatorKind=js::NotGenerator)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeCompiler.cpp:703
#13 0x0000000000689789 in CompileFunctionBody (cx=0x7ffff6908c00, fun=..., options=..., formals=..., srcBuf=..., enclosingStaticScope=..., 
    generatorKind=js::NotGenerator) at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeCompiler.cpp:896
#14 0x0000000000689802 in js::frontend::CompileFunctionBody (cx=0x7ffff6908c00, fun=..., options=..., formals=..., srcBuf=..., enclosingStaticScope=...)
    at /home/andre/hg/mozilla-central/js/src/frontend/BytecodeCompiler.cpp:906
#15 0x0000000000d94d80 in FunctionConstructor (cx=0x7ffff6908c00, argc=1, vp=0x7ffff3df60a8, generatorKind=js::NotGenerator)
    at /home/andre/hg/mozilla-central/js/src/jsfun.cpp:1927
#16 0x0000000000d94ece in js::Function (cx=0x7ffff6908c00, argc=1, vp=0x7ffff3df60a8) at /home/andre/hg/mozilla-central/js/src/jsfun.cpp:1935
#17 0x0000000000768362 in js::CallJSNative (cx=0x7ffff6908c00, native=0xd94ea3 <js::Function(JSContext*, unsigned int, JS::Value*)>, args=...)
    at /home/andre/hg/mozilla-central/js/src/jscntxtinlines.h:235
#18 0x0000000000732f28 in js::Invoke (cx=0x7ffff6908c00, args=..., construct=js::NO_CONSTRUCT)
    at /home/andre/hg/mozilla-central/js/src/vm/Interpreter.cpp:763
#19 0x0000000000742899 in Interpret (cx=0x7ffff6908c00, state=...) at /home/andre/hg/mozilla-central/js/src/vm/Interpreter.cpp:3054
#20 0x0000000000732b66 in js::RunScript (cx=0x7ffff6908c00, state=...) at /home/andre/hg/mozilla-central/js/src/vm/Interpreter.cpp:704
#21 0x000000000073420b in js::ExecuteKernel (cx=0x7ffff6908c00, script=..., scopeChainArg=..., thisv=..., newTargetValue=..., type=js::EXECUTE_GLOBAL, 
    evalInFrame=..., result=0x7fffffffd420) at /home/andre/hg/mozilla-central/js/src/vm/Interpreter.cpp:978
#22 0x0000000000734510 in js::Execute (cx=0x7ffff6908c00, script=..., scopeChainArg=..., rval=0x7fffffffd420)
    at /home/andre/hg/mozilla-central/js/src/vm/Interpreter.cpp:1012
#23 0x0000000000d39775 in ExecuteScript (cx=0x7ffff6908c00, scope=..., script=..., rval=0x7fffffffd420)
    at /home/andre/hg/mozilla-central/js/src/jsapi.cpp:4353
#24 0x0000000000d39b08 in JS_ExecuteScript (cx=0x7ffff6908c00, scriptArg=..., rval=...) at /home/andre/hg/mozilla-central/js/src/jsapi.cpp:4378
#25 0x000000000042ff7c in EvalAndPrint (cx=0x7ffff6908c00, 
    bytes=0x7ffff3dfdcc0 "Function(`return [${\",\".repeat(16777215 + 1)}].length`)()\n\245\245\245\245\245\245", length=58, lineno=1, compileOnly=false, 
    out=0x7ffff6f6a740 <_IO_2_1_stdout_>) at /home/andre/hg/mozilla-central/js/src/shell/js.cpp:486
#26 0x0000000000430442 in ReadEvalPrintLoop (cx=0x7ffff6908c00, in=0x7ffff6f69980 <_IO_2_1_stdin_>, out=0x7ffff6f6a740 <_IO_2_1_stdout_>, 
    compileOnly=false) at /home/andre/hg/mozilla-central/js/src/shell/js.cpp:550
#27 0x0000000000430605 in Process (cx=0x7ffff6908c00, filename=0x0, forceTTY=true) at /home/andre/hg/mozilla-central/js/src/shell/js.cpp:581
#28 0x00000000004451d4 in ProcessArgs (cx=0x7ffff6908c00, op=0x7fffffffd940) at /home/andre/hg/mozilla-central/js/src/shell/js.cpp:5800
#29 0x000000000044641c in Shell (cx=0x7ffff6908c00, op=0x7fffffffd940, envp=0x7fffffffdb48) at /home/andre/hg/mozilla-central/js/src/shell/js.cpp:6109
#30 0x0000000000447736 in main (argc=1, argv=0x7fffffffdb38, envp=0x7fffffffdb48) at /home/andre/hg/mozilla-central/js/src/shell/js.cpp:6455
---

Comment 1

[Benjamin Bouvier [:bbouvier] (inactive)]

arai, it seems you added the call to SET_UINT24 and you have experience with the BytecodeEmitter. Any chance you would be interested in solving this? :)

Comment 2

[Tooru Fujisawa [:arai]]

Looks like a regression from bug 686274.  There the limit of array literal length is changed form 491519 to 2**28-1, that overflows from JSOP_NEWARRAY's 24bit operand.  It also means that elements after 2**24 are not initialized correctly when JSOP_NEWARRAY_COPYONWRITE is not usable, because JSOP_INITELEM_ARRAY's operand is also 24bit.

There will be some solutions:
  (a) limit the array literal length to 2**24-1
  (b) if length overflows from 24bit, use 0xffffff for JSOP_NEWARRAY operand and use JSOP_INITELEM_INC for remaining elements
  (c) extend operand of JSOP_NEWARRAY, JSOP_INITELEM_ARRAY, and JSOP_SPREADCALLARRAY to 32bit

(a) should be the simplest, but it might be a breaking change (I think it's super rare case tho)
I'll also investigate about (c).

Waldo, how do you think?

Comment 3

[Tooru Fujisawa [:arai]]

Looks like extending opcodes to 32bit works
  https://treeherder.mozilla.org/#/jobs?repo=try&revision=19804c1395fe

Comment 4

[Jeff Walden [:Waldo]]

Go with c.

Comment 5

[Tooru Fujisawa [:arai]]

Attachment: Extend JSOP_NEWARRAY/JSOP_INITELEM_ARRAY/JSOP_SPREADCALLARRAY operand to uint32.

Added test code in comment #0, but it takes long time if --ion-eager or --baseline-eager is specified.

  time taken by long-array-literal.js
     time | options
    ------+---------------
      2.3 | ""
     11.8 | "--ion-eager --ion-offthread-compile=off"
     12.0 | "--ion-eager --ion-offthread-compile=off --non-writable-jitcode --ion-check-range-analysis --ion-extra-checks --no-sse3 --no-threads"
     11.6 | "--baseline-eager"
     11.7 | "--baseline-eager --no-fpu"
      2.2 | "--no-baseline --no-ion"

Are these acceptable?

Comment 6

[Jeff Walden [:Waldo]]

Comment on attachment 8655175 [details] [diff] [review]
Extend JSOP_NEWARRAY/JSOP_INITELEM_ARRAY/JSOP_SPREADCALLARRAY operand to uint32.

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

An 11-second test doesn't horribly bother me.  I'd say it's fine landing it.

::: js/src/jit/BaselineIC.cpp
@@ +4156,1 @@
>          if (!InitArrayElemOperation(cx, pc, obj, index.toInt32(), rhs))

The context here is:

    // Check the old capacity
    uint32_t oldCapacity = 0;
    uint32_t oldInitLength = 0;
    if (index.isInt32() && index.toInt32() >= 0) {
        oldCapacity = GetAnyBoxedOrUnboxedCapacity(obj);
        oldInitLength = GetAnyBoxedOrUnboxedInitializedLength(obj);
    }

    if (op == JSOP_INITELEM) {
        if (!InitElemOperation(cx, obj, index, rhs))
            return false;
    } else if (op == JSOP_INITELEM_ARRAY) {
        MOZ_ASSERT(uint32_t(index.toInt32()) == GET_UINT24(pc));
        if (!InitArrayElemOperation(cx, pc, obj, index.toInt32(), rhs))
            return false;

We're passing a uint32_t here, as an int32_t, and relying on modular wraparound.  But that |index.toInt32() >= 0| above treats negative indexes as *actually* negative.  And if I look further on, there seem to be a bunch of places that are going to get in trouble of various sorts if oldCapacity/etc. are wrong, or if index is a negative int32_t, in ways that don't obviously appear "okay".  (Certainly some places will just deopt, but I'm not sure all of them will.)

So I think we still need a limit, besides UINT32_MAX here.  I think you should also (in addition to this 32-bit offset thing in the bytecode) add to the parser code to ensure we error out with some sort of too-large notification if the array literal grows too big.  2**24 wasn't a bad limit, but might as well bump it all the way to INT32_MAX while you're here.  But definitely we need an actual check, to avoid overflowing the new 31-bit boundary instead of the old 24-bit boundary.  (Maybe we could rely on the JS heap never growing that big, but I'd rather not.  :-) )

::: js/src/jit/IonBuilder.cpp
@@ +6838,5 @@
>          }
>      }
>  
>      if (needStub) {
> +        MCallInitElementArray* store = MCallInitElementArray::New(alloc(), obj, GET_UINT32(pc), value);

Split out GET_UINT32(pc) into a |uint32_t index| and use that in these two places.

Comment 7

[Tooru Fujisawa [:arai]]

Attachment: Extend JSOP_NEWARRAY/JSOP_INITELEM_ARRAY/JSOP_SPREADCALLARRAY operand to uint32.

Added 31-bit boundary check in several places.
Currently the length of the array literal is limited to NativeObject::NELEMENTS_LIMIT in parser, and overflow is reported there, so added check for |NativeObject::NELEMENTS_LIMIT <= INT32_MAX| to catch the change there in future.
Also, changed |jsatomid atomIndex;| to |uint32_t index;| in BytecodeEmitter::emitArray, as that's not an atom but just an index.

Comment 8

[Jeff Walden [:Waldo]]

Comment on attachment 8657385 [details] [diff] [review]
Extend JSOP_NEWARRAY/JSOP_INITELEM_ARRAY/JSOP_SPREADCALLARRAY operand to uint32.

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

::: js/src/frontend/BytecodeEmitter.cpp
@@ +7271,5 @@
>  
> +    // Array literal's length is limited to NELEMENTS_LIMIT in parser.
> +    static_assert(NativeObject::NELEMENTS_LIMIT <= INT32_MAX,
> +                  "Array literal's maximum length shouldn't be greater than INT32_MAX");
> +    MOZ_ASSERT(count <= INT32_MAX);

Move this down after the spread-loop, because it's relevant to the emitUint32Operand call, not to the loop after this.  The reason-string should be something like, "array literals' maximum length must not exceed limits required by BaselineCompiler::emit_JSOP_NEWARRAY, BaselineCompiler::emit_JSOP_INITELEM_ARRAY, and DoSetElemFallback's handling of JSOP_INITELEM_ARRAY" -- point at the sibling code that depends upon this.

Good to see nspread made a uint32_t in passing.

Further on that, please also add MOZ_ASSERT(count >= nspread) as a sanity check against underflow.

::: js/src/jit-test/tests/arrays/long-array-literal.js
@@ +1,3 @@
> +function test() {
> +  let x = 42;
> +  let a = eval(`[${",".repeat(16777215 + 1)}x];`);

Do we want a similar version of this that tests the spreadcallarray stuff as well (I guess by tacking ', ...[]' onto the end of the literal)?  Seems like yes.

::: js/src/jit/BaselineCompiler.cpp
@@ +1781,5 @@
>  {
>      frame.syncStack(0);
>  
> +    uint32_t length = GET_UINT32(pc);
> +    MOZ_ASSERT(length <= INT32_MAX);

Augment this with a reason similar to what I mention for BaselineIC.cpp.

@@ +1786,3 @@
>  
>      // Pass length in R0.
>      masm.move32(Imm32(length), R0.scratchReg());

Use AssertedCast<int32_t>(length), from mozilla/Casting.h.

@@ +1839,5 @@
>  
>      // Load object in R0, index in R1.
>      masm.loadValue(frame.addressOfStackValue(frame.peek(-2)), R0);
> +    uint32_t index = GET_UINT32(pc);
> +    MOZ_ASSERT(index <= INT32_MAX);

Similar reason-adding.

::: js/src/jit/BaselineIC.cpp
@@ +4152,5 @@
>          if (!InitElemOperation(cx, obj, index, rhs))
>              return false;
>      } else if (op == JSOP_INITELEM_ARRAY) {
> +        MOZ_ASSERT(uint32_t(index.toInt32()) == GET_UINT32(pc));
> +        MOZ_ASSERT(uint32_t(index.toInt32()) <= INT32_MAX);

Add an explanation to the second assertion:

        MOZ_ASSERT(uint32_t(index.toInt32()) <= INT32_MAX,
                   "the bytecode emitter must fail to compile code that would "
                   "produce JSOP_INITELEM_ARRAY with an index exceeding "
                   int32_t range");

Also, do this assertion before doing the equals-index-in-bytecode assertion.  First check that the given value is in the right range.  *Then* check that the value now known to be in the right range, corresponds with the value burned into the script.  If uint32_t(index) doesn't make sense because index is negative, a comparison to it makes even less sense.  See what I mean?

I kind of want to say just ignore |index| entirely (except for purposes of assertions) and use GET_UINT32(pc) instead, but it feels to me like the |pc| argument to this function should eventually die, so I"m not going to suggest it.

::: js/src/jit/IonBuilder.cpp
@@ +6712,5 @@
>  
>  bool
>  IonBuilder::jsop_newarray(uint32_t count)
>  {
> +    MOZ_ASSERT(count <= INT32_MAX);

This one, and the one below it, I'd say we should remove.

The distinction is that *if* you passed in a bigger int32_t here, nothing would go wrong (you'd allocation-overflow, but that's not *wrong* behavior).  We should only assert <= INT32_MAX when the code will do a wrong thing if the assertion failed.  But here, and just below (and in the interpreter case), there's no mis-interpretation of uint32_t(-1) as -1 or whatever.  If at some time we made lengths > INT32_MAX actually work, this code would need no changes to support it.

::: js/src/vm/Interpreter.cpp
@@ +3604,5 @@
>  CASE(JSOP_NEWARRAY)
>  CASE(JSOP_SPREADCALLARRAY)
>  {
> +    uint32_t length = GET_UINT32(REGS.pc);
> +    MOZ_ASSERT(length <= INT32_MAX);

Remove this assertion and the similar one below, IMO -- nothing goes wrong if a non-int32_t is passed in here, the APIs accept uint32_t and don't do anything wrong if passed a super-big uint32_t.  (They'd throw allocation-overflow, but that's not wrong or misinterpreting a uint32_t as int32_t or whatever.)

::: js/src/vm/Opcodes.h
@@ +844,5 @@
>      /*
>       * Pushes newly created array onto the stack.
>       *
>       * This opcode takes the final length, which is preallocated.
> +     * 'length' should be less than or equal to INT32_MAX.

So actually, I'm not sure I'd put this in here.  (Same for all the other comments in this file's changes.)

That this will fail at runtime isn't a characteristic of the bytecode format.  It's just an extra restriction applied to the semantics of bytecode emission for certain source text.  I think it's perfectly fine to not state this, to not assert it, and to leave the not-too-large checks to runtime tests (such checks being necessary for other reasons, we're not adding any extra code for them).

Comment 9

[Jeff Walden [:Waldo]]

Comment on attachment 8657385 [details] [diff] [review]
Extend JSOP_NEWARRAY/JSOP_INITELEM_ARRAY/JSOP_SPREADCALLARRAY operand to uint32.

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

::: js/src/frontend/BytecodeEmitter.cpp
@@ +7271,5 @@
>  
> +    // Array literal's length is limited to NELEMENTS_LIMIT in parser.
> +    static_assert(NativeObject::NELEMENTS_LIMIT <= INT32_MAX,
> +                  "Array literal's maximum length shouldn't be greater than INT32_MAX");
> +    MOZ_ASSERT(count <= INT32_MAX);

Actually, forgot to mention it, but make this MOZ_ASSERT(count <= NativeObject::NELEMENTS_LIMIT).  That's the real limit observable here, and something's just as wrong in our understanding (and desirous of an assertion to note it) if we get a count still int32_t but greater than this limit.

Comment 10

[Tooru Fujisawa [:arai]]

Thank you for reviewing :)

Then, another trouble happens. The test takes so much RAM, maybe 4GB or 5GB per single js process.

The test hits OOM on try server (c3.xlarge, 7.5GB RAM)
  https://treeherder.mozilla.org/#/jobs?repo=try&revision=485a94c22c98

Also, it hits timeout on my linux box (4GB RAM).  sorry, I should've tested on this too :P
Setting longer timeout hits OOM after 1000sec, and so much swap happens.
Longer timeout and running sequentially (-j1) doesn't hit OOM, but still takes too long (600sec totally, with 6 variants for single test).

comment #5 was the result on iMac Late 2013 (16GB RAM) it doesn't hit OOM nor timeout.  but I saw single js process takes 4.7GB while testing with -j4.

So, Looks like we shouldn't enable test for this bug by default, even on opt build :/
Do you think it's okay to add |slow|?  or we should just remove the test?

Comment 11

[Jeff Walden [:Waldo]]

Hm, even for slow is probably a nasty surprise.  I think that runs on tinderbox but not locally, but even tinderbox infra may not like a 5GB allocation.  And certainly I'd be in trouble, sometimes, if a 5GB allocation spontaneously happened on my system.  I guess just don't land a test.

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #9)
> > +    // Array literal's length is limited to NELEMENTS_LIMIT in parser.
> > +    static_assert(NativeObject::NELEMENTS_LIMIT <= INT32_MAX,
> > +                  "Array literal's maximum length shouldn't be greater than INT32_MAX");
> > +    MOZ_ASSERT(count <= INT32_MAX);
> 
> Actually, forgot to mention it, but make this MOZ_ASSERT(count <=
> NativeObject::NELEMENTS_LIMIT).

Er, count < NELEMENTS_LIMIT, that should be.  Unless we change its name/meaning at some point before this patchwork lands, at least.

Comment 12

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/15f4976a4937

Comment 13

[Tooru Fujisawa [:arai]]

backed out to backout depending patches.
https://hg.mozilla.org/integration/mozilla-inbound/rev/92c771c3f3e2

Comment 14

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/f46afea54f1c

Comment 15

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/f46afea54f1c