916612 - JS engine cannot execute large JS scripts with a lot of local variables.

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jukka Jylänki]

Attachment: manylocalvars.py

User Agent: Mozilla/5.0 (Windows NT 6.2; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/29.0.1547.66 Safari/537.36

Steps to reproduce:

To create a test case, run the attached .py script and pipe the output to a .js file, create a .html stub to run the .js file in a <script> tag in the browser.


Actual results:

If a JS function contains more than 65536 local variables, the script engine will not execute the function, but aborts with an error 'too many local variables'.


Expected results:

The script should execute.

Testing other browsers, IE has a limit of 250k local variables in a function, Chrome and Opera have a limit of 131071 local variables in a function, and Firefox bails out already at 65536.

For context on this, see also a very similar bug report https://bugzilla.mozilla.org/show_bug.cgi?id=916564 . Large Emscripten-compiled applications can contain asm.js modules with well over 64k global variables, and this hard limit is blocking the ability to port large native codebases. Would it be possible to increase this variable limit to 32bits instead of the apparent 16bits restriction?

Comment 2

[Luke Wagner [:luke]]

This is definitely doable but, after a quick check when I filed bug 913191, it's unfortunately not a trivial change since the uint16 restriction extends into the bytecode format.

Comment 3

[Alon Zakai (:azakai)]

I don't think I understand yet what the *source* of all the vars is, in the testcase you saw this on. Was it "global" vars (in the asm module itself) or "local" vars (inside a single compiled C function)?

Comment 4

[jonas echterhoff]

Would like to see a fix for this as well, as we are running into it when compiling our codebase with Emscripten, too (to many functions being generated as local variables in the main asm.js module).

Comment 5

[Jukka Jylänki]

Jonas, we noticed that this can happen when the codebase is compiled with -s ASM_JS=1, but the asm.js module fails to validate in Firefox at runtime. As a temporary workaround, disabling asm.js compilation with -s ASM_JS=0 would sidestep this, since there wouldn't be a asm.js module generated.

Try doublechecking if Firefox really fails asm.js module validation of your app at startup time, and see if you could fix that directly. We noticed that if asm.js does validate properly, the whole asm.js module is run in OdinMonkey instead, which does not have this 64k locals limit at all, and therefore no issue.

Comment 6

[jonas echterhoff]

Disabling asm.js won't help in our case - our code base simply has more then 64k functions (which are treated as local variables in the main module, regardless of using asm.js or not). I don't see any message about asm.js validation failing.

Comment 7

[jonas echterhoff]

Actually, ignore that, disabling asm.js does in fact fix it (ran a wrong build when I tried it before). But then, if the problem is failing validation, it would still be very helpful to be able to see the error messages about it when asm.js is enabled (I currently only see the "Too many local variables" error).

Comment 8

[Jukka Jylänki]

You can try validating your output file on the command line if you have spidermonkey on your system by running

python %EMSCRIPTEN%\tools\validate_asmjs.py path\to\outputfile.(html or js)

It could be possible that the too many locals error hides the asm.js validation error, or something similar.

If you use CMake to build, you can add the above command as a post-build step to test validation with https://github.com/kripken/emscripten/blob/master/cmake/Platform/Emscripten.cmake#L139 . I use that in my builds to unit-test against regressions in the compiler, and to confirm that validation was ok after release builds.

Comment 9

[Alon Zakai (:azakai)]

In an asm.js build, you should always see a validation message in the web console, either success or failure. If not, make sure there is 'use asm' in the build output? If it isn't there, might be an emscripten bug, and if it is, then might be a firefox bug.

The too many locals error should happen *after* asm.js validation fails, or is never attempted.

Comment 10

[jonas echterhoff]

That does not seem to be the case. My js does contain "use asm", but all I see in the console is the too many locals error, no asm.js validation message (which I was getting before I ran into this error).

Hmm. that was in FF 24. I just tried Nightly, and that will actually give me a successful validation message and then move on with the code without complaining about locals. So I probably shouldn't actually worry about this for now.

Comment 11

[Luke Wagner [:luke]]

Oof, the uint16 restriction reached somewhat far and wide.  I broke this fix down into 9 patches, most pretty small and some doing cleanup.  I ended up examining all uses of 'uint16_t', 'unsigned', '.*UINT16.*', 'JOF_LOCAL' to make sure I hadn't missed anywhere.  We tend to use 'unsigned' to mean "holds some small integer", whereas 'uint32_t' to mean "holds a full (or close) 32-bit int", which is why I converted a bunch of unsigned to uint32_t even though they are probably the same on all major platforms.

Comment 12

[Luke Wagner [:luke]]

Attachment: rm-crud

Remove some needless old macros.

Comment 13

[Luke Wagner [:luke]]

Attachment: rm-nfixed

script->nfixed would have to be inflated to uint32_t as well, but it turns out it's totally redundant these days, so I removed it instead.

Comment 14

[Luke Wagner [:luke]]

Attachment: rm-jof-types

More dead code.

Comment 15

[Luke Wagner [:luke]]

Attachment: rm-short-id

The fact that we store the slot index (of variables in the CallObject) as a shortid in Shapes *would* be another limitation, but it turns out this isn't necessary any more either, after the big scope refactoring.

Comment 16

[Luke Wagner [:luke]]

Attachment: inflate-scope-coord

This patch inflates ScopeCoordinate/UpvarCookie to allow a 24-bit index.  This patch also shrinks the "hops" (number of hops up the scope chain to find an aliased variable) to an 8-bit value.  The reasoning behind this is:
 - >256 hops up the scope chain means >256 nested functions, by which time we're getting close to failing compilation do to over-recursion in the parser
 - >256 hops up the scope chain is going to be really slow
 - this keeps UpvarCookie 1 word.  Making UpvarCookie makes ParseNode bigger since we work hard to keep this small since we make so many

Comment 17

[Luke Wagner [:luke]]

Attachment: inflate-try-notes

Stack depths can be > 16-bits now, so try notes need a uint32_t stack depth.

Comment 18

[Luke Wagner [:luke]]

Attachment: move-too-many-check

Move this check to a more natural place.

Comment 19

[Luke Wagner [:luke]]

Attachment: tweak-baseline

This patch is basically reverting bug 918603, since now it can dynamically fail.

Comment 20

[Luke Wagner [:luke]]

Attachment: widen-var-index

This patch loosens the limit.  It only loosens it for locals, not formal arguments, since the uint16_t argument limitation is even *more* widespread and would require us to bloat even more data structures (e.g., JSFunction::nargs).

Comment 21

[Luke Wagner [:luke]]

Attachment: widen-var-index v.2

Comment 22

[Andy Wingo [:wingo]]

Comment on attachment 8360737 [details] [diff] [review]
rm-nfixed

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

::: js/src/jsscript.cpp
@@ +552,5 @@
>      if (!xdr->codeUint32(&scriptBits))
>          return false;
>  
>      if (mode == XDR_DECODE) {
>          /* Note: version is packed into the 32b space with another 16b value. */

This comment no longer applies, correct?

Comment 23

[Andy Wingo [:wingo]]

Comment on attachment 8360738 [details] [diff] [review]
rm-jof-types

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

Nice :)

::: js/src/jsopcode.cpp
@@ -1035,2 @@
>        {
>          int i;

I had no idea one could have a case label inside a block.

Comment 24

[Andy Wingo [:wingo]]

Comment on attachment 8360740 [details] [diff] [review]
rm-short-id

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

::: js/src/jsscript.cpp
@@ -98,5 @@
>      JS_STATIC_ASSERT(CallObject::RESERVED_SLOTS == 2);
>      gc::AllocKind allocKind = gc::FINALIZE_OBJECT2_BACKGROUND;
>      JS_ASSERT(gc::GetGCKindSlots(allocKind) == CallObject::RESERVED_SLOTS);
>      RootedShape initial(cx,
> -        EmptyShape::getInitialShape(cx, &CallObject::class_, nullptr, cx->global(), nullptr,

I don't really understand this change; why would the global be passed for the metadata before but not after?  Granted, I don't understand the shape code very well.

@@ +133,5 @@
>  
>          RootedId id(cx, NameToId(bi->name()));
>          unsigned attrs = JSPROP_PERMANENT | JSPROP_ENUMERATE |
>                           (bi->kind() == CONSTANT ? JSPROP_READONLY : 0);
> +        StackShape child(nbase, id, slot++, 0, attrs, 0, 0);

I guess the shortid was just an optimization here?  Cool.

Comment 25

[Luke Wagner [:luke]]

(In reply to Andy Wingo [:wingo] from comment #22)
> This comment no longer applies, correct?

Correct!

(In reply to Andy Wingo [:wingo] from comment #23)

How else would one write Duff's device ? ;)

(In reply to Andy Wingo [:wingo] from comment #24)
> I don't really understand this change; why would the global be passed for
> the metadata before but not after?  Granted, I don't understand the shape
> code very well.

Oh sorry, I should've explained that hunk, as it's an unrelated cleanup.  This code must've originally passed cx->global() as the 'parent' but then, when the metadata hook was added, the nullptr was added in the wrong place and so cx->global() became the metadata and thus the parent became null.  (What exactly "parent" even *means* for CallObjects is unclear since 'parent' is decreasingly relevant and should be removed (bug 773488), but evidently noone cares about the parent of CallObjects which makes sense; it's an internal scope, not a real object.)  So the cleanup is just to remove the spurious metadata arg, while keeping the null-ness of parent.

> I guess the shortid was just an optimization here?  Cool.

shortid is, at this point, mostly only useful to JSAPI clients: they get to specify the shortid of a property when they add it and this shortid gets passed to the getter/setter.  It's useful if the property ends up being lookuped up in an array whose index is determined by the property name.  Before the big scope changes last year, CallObjects had getters/setters for all properties that either accessed the slot or the stack frame and they needed the shortid for this purpose.  With these getters/setters gone, noone needs the shortid anymore.  Block objects apparently still use the shortid for a few purposes (hence the remaining uint16 limitation on num-block-bindings), but I suspect those uses could be removed as well.

Comment 26

[Andy Wingo [:wingo]]

Comment on attachment 8360745 [details] [diff] [review]
inflate-scope-coord

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

Changes look correct; some notes about uint8 range footguns below.  Not sure about the 256-deep scope limit though; you might want to run that one by someone else.

::: js/src/vm/ScopeObject.h
@@ +101,5 @@
>   * main ScopeCoordinate struct: use ScopeCoordinate{BlockChain,Name} instead.
>   */
>  struct ScopeCoordinate
>  {
> +    unsigned hops;

The range of hops seems to be 0-255; mentioning this somehow would be nice.

Is this reduction in scope nesting depth going to hurt?  I could imagine hitting the limit.  A test case might be a good idea.  Or perhaps there is one already?

Also I might consider hiding hops and slot behind an accessor, now that manipulating them directly could yield invalid values that wouldn't be caught by EmitAliasedVarOp.

Comment 27

[Luke Wagner [:luke]]

(In reply to Andy Wingo [:wingo] from comment #26)
I was also initially doubting this change, but then I came up with the justifications in comment 16.  I also ran it by jorendorff on irc.

I'll add the accessors and a better comment as you suggest.

Comment 28

[Andy Wingo [:wingo]]

Comment on attachment 8360747 [details] [diff] [review]
move-too-many-check

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

LGTM with one thing to fix or comment.

::: js/src/frontend/Parser.cpp
@@ +156,1 @@
>          if (name == ts.names().empty)

There's another caller of args_.append(), the SyntaxParseHandler define() handler.  It's probably worth it to have a similar check there, if I understand correctly.

Comment 29

[Luke Wagner [:luke]]

(In reply to Andy Wingo [:wingo] from comment #28)
Nice catch!

Comment 30

[Andy Wingo [:wingo]]

Comment on attachment 8360801 [details] [diff] [review]
widen-var-index v.2

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

::: js/src/frontend/Parser.cpp
@@ +306,5 @@
> +    /*
> +     * Avoid pathological edge cases by explicitly limiting the total number of
> +     * bindings to what will fit in a uint32_t.
> +     */
> +    if (UINT32_MAX - args_.length() <= vars_.length())

Potential size_t vs uint32_t issue?  Extraordinarily unlikely though.  And can't this be caught by a static_assert instead, that ARGNO_LIMIT+LOCALNO_LIMIT <= UINT32_MAX ?

::: js/src/jsscript.h
@@ +649,5 @@
>      uint32_t        mainOffset_;/* offset of main entry point from code, after
>                                     predef'ing prolog */
>  
>      uint32_t        natoms_;    /* length of atoms array */
> +    uint32_t        nslots_;    /* vars plus maximum stack depth */

Last time I mucked about with JSScript size I ran into some issue about alignment on Win32.  THis thing has to have an 8-byte aligned size, no?.  I'm a bit paranoid, but if there is some padding that is now available relative to the beginning of the patch series it would be nice to see it explicitly as a padding member.  As you like though :)

::: js/src/vm/Interpreter.cpp
@@ +2921,5 @@
>  
>  CASE(JSOP_GETLOCAL)
>  CASE(JSOP_CALLLOCAL)
>  {
> +    unsigned i = GET_LOCALNO(REGS.pc);

uint32_t if you are really being consistent, no? :)

Comment 31

[Luke Wagner [:luke]]

(In reply to Andy Wingo [:wingo] from comment #30)
> Potential size_t vs uint32_t issue?

Given the preconditions (asserted above) about (vars_,args_).length(), I don't think so.

> And can't this be caught by a static_assert instead, that
> ARGNO_LIMIT+LOCALNO_LIMIT <= UINT32_MAX ?

Since argno is a 16-bit value and localno is a 24-bit, then they could overflow a 32-bit int.

> Last time I mucked about with JSScript size I ran into some issue about
> alignment on Win32.

Yeah, try server pointed out I needed to also take out JSScript::padding0 so that sizeof(JSScript) % 8 == 0 (statically asserted below).

> uint32_t if you are really being consistent, no? :)

Verily

Comment 32

[Andy Wingo [:wingo]]

(In reply to Luke Wagner [:luke] from comment #25)

Thanks, these comments explain it perfectly.  Cheers :)

Comment 33

[Luke Wagner [:luke]]

Thanks for the expedient review!

Comment 34

[Andy Wingo [:wingo]]

(In reply to Luke Wagner [:luke] from comment #27)
> (In reply to Andy Wingo [:wingo] from comment #26)
> I was also initially doubting this change, but then I came up with the
> justifications in comment 16.  I also ran it by jorendorff on irc.
> 
> I'll add the accessors and a better comment as you suggest.

(In reply to Luke Wagner [:luke] from comment #16)
> Created attachment 8360745 [details] [diff] [review]
> inflate-scope-coord
> 
> This patch inflates ScopeCoordinate/UpvarCookie to allow a 24-bit index. 
> This patch also shrinks the "hops" (number of hops up the scope chain to
> find an aliased variable) to an 8-bit value.  The reasoning behind this is:
>  - >256 hops up the scope chain means >256 nested functions, by which time
> we're getting close to failing compilation do to over-recursion in the parser
>  - >256 hops up the scope chain is going to be really slow
>  - this keeps UpvarCookie 1 word.  Making UpvarCookie makes ParseNode bigger
> since we work hard to keep this small since we make so many

A test:

js> function scope(n,str) { return '(function(){var v'+n+'='+n+';'+(n==0?str:('return '+scope(n-1,str)+'()'))+'})' }
js> var f = eval(scope(300, 'return function(s){(function(){eval(s)})(); return v300}'))()
js> print(disassemble(f))
flags: LAMBDA HEAVYWEIGHT
loc     op
-----   --
00000:  arguments
00001:  setaliasedvar "arguments" (hops = 0, slot = 3)
00006:  pop
main:
00007:  lambda (function (){eval(s)})
00012:  undefined
00013:  call 0
00016:  pop
00017:  getaliasedvar "v300" (hops = 301, slot = 2)
00022:  return
00023:  retrval

Source notes:
 ofs line    pc  delta desc     args
---- ---- ----- ------ -------- ------
  0:    5     7 [   7] colspan 9425
  4:    5    17 [  10] xdelta  
  5:    5    17 [   0] colspan 24
  7:    5    23 [   6] colspan 11

Comment 35

[Luke Wagner [:luke]]

Yeah, but it looks like scope(400) fails.  Also, this is going to fluctuate build-by-build since it depends on C stack frame size.

Comment 36

[Luke Wagner [:luke]]

We can see if anyone complains.  If so, a reasonable recourse would be to increase SOURCECOORD_HOPS_BITS to 9 and decrease SOURCECOORD_SLOT_BITS to 27.

https://hg.mozilla.org/integration/mozilla-inbound/rev/de211a1a43dc
https://hg.mozilla.org/integration/mozilla-inbound/rev/d3de98bef32f
https://hg.mozilla.org/integration/mozilla-inbound/rev/21599b817254
https://hg.mozilla.org/integration/mozilla-inbound/rev/e046db9b732a
https://hg.mozilla.org/integration/mozilla-inbound/rev/4a0c81bd7fed
https://hg.mozilla.org/integration/mozilla-inbound/rev/9845c94f44ff
https://hg.mozilla.org/integration/mozilla-inbound/rev/a15cee5da933
https://hg.mozilla.org/integration/mozilla-inbound/rev/556ddac71fd8
https://hg.mozilla.org/integration/mozilla-inbound/rev/d2eca1d56402

Comment 37

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

https://hg.mozilla.org/mozilla-central/rev/de211a1a43dc
https://hg.mozilla.org/mozilla-central/rev/d3de98bef32f
https://hg.mozilla.org/mozilla-central/rev/21599b817254
https://hg.mozilla.org/mozilla-central/rev/e046db9b732a
https://hg.mozilla.org/mozilla-central/rev/4a0c81bd7fed
https://hg.mozilla.org/mozilla-central/rev/9845c94f44ff
https://hg.mozilla.org/mozilla-central/rev/a15cee5da933
https://hg.mozilla.org/mozilla-central/rev/556ddac71fd8
https://hg.mozilla.org/mozilla-central/rev/d2eca1d56402