1966196 - AJV validator hits JSMSG_TOO_DEEP when V8 doesn't

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Jeff Muizelaar [:jrmuizel]]

Attachment: nesting.html

See https://bug1965201.bmoattachments.org/attachment.cgi?id=9487375 from bug 1965201

Comment 1

[Daniel Holbert [:dholbert]]

Attachment: testcase 2 (with visual indication of success/failure)

Here's an amended version of Jeff's testcase.

STR:

1. Load this testcase.
2. (optional) Check your Web Console.

ACTUAL RESULTS:

• "FAILURE" shows in the body of the page.
• Web console shows:

Uncaught InternalError: function nested too deeply

EXPECTED RESULTS:

• "SUCCESS" should show in the body of the page.
• No uncaught InternalError: in web console.

Comment 2

[Daniel Holbert [:dholbert]]

Attachment: Bug 1966196: Use a 16-bit value (rather than 8) to store 'hops' in JS, to support a higher function nesting depth. r?#spidermonkey-reviewers

Comment 3

[Daniel Holbert [:dholbert]]

Attachment: testcase 3 (more compact, 700 levels of nesting, fails in Firefox and Chrome)

Here's a testcase that's a bit more declarative about how it sets up the nesting here, by just repeating this pattern to 300 levels of nesting:

let someCondition = Math.random() > 0.5;

if (someCondition) {
  let foo;
  if (someCondition) {
    let foo;
    [...]
  }
}

This is sufficient to trigger the Uncaught InternalError: function nested too deeply error in Firefox.

In Chrome, it completes just fine with this testcase. However, if I increase the nesting level to 700, then Chrome triggers Uncaught RangeError: Maximum call stack size exceeded

Comment 4

[Daniel Holbert [:dholbert]]

Comment on attachment 9488126 [details]
testcase 3 (more compact, 700 levels of nesting, fails in Firefox and Chrome)

er whoops, that was the version with 700 levels which fails in both Firefox and Chrome. I'll adjust the title to make that clearer and reattach a 300-nesting-level one that only fails in Firefox.

Comment 5

[Daniel Holbert [:dholbert]]

Attachment: testcase 4 (more compact, 300 levels of nesting, only fails in Firefox)

Comment 6

[Daniel Holbert [:dholbert]]

I'm going to unassign this and abandon the phab revision, since this is more complex than just "add more bits to make the limit bigger".

(It's maybe approximately that complex, but there's a lot of places where this same value (or something with "hops" in the name) gets read-from/stored-to an 8-bit value, and I don't know Spidermonkey well enough to know which to adjust).

I'm hoping this might be much more trivial for a Spidermonkey expert (who knows more about the "hops" data here) to pick up and fix. Feel free to co-opt and complete my patch, if it's a helpful starting point.

Comment 7

[Nicolas B. Pierron [:nbp] {away}]

This sounds like a self-inflicted limitation coming from the way we encode scope chains:

https://searchfox.org/mozilla-central/rev/06e32c3ea654f5a74e08cc1040b52a3646d639a7/js/src/frontend/EmitterScope.cpp#67-69

Comment 8

[Daniel Holbert [:dholbert]]

(In reply to Nicolas B. Pierron [:nbp] from comment #7)

This sounds like a self-inflicted limitation coming from the way we encode scope chains:

https://searchfox.org/mozilla-central/rev/06e32c3ea654f5a74e08cc1040b52a3646d639a7/js/src/frontend/EmitterScope.cpp#67-69

Yup, that's exactly right. The code there is:

if (hops >= ENVCOORD_HOPS_LIMIT - 1) {
  bce->reportError(nullptr, JSMSG_TOO_DEEP, "function");
  return false;

and my abandoned patch ( https://phabricator.services.mozilla.com/D249124 ) gets us past that specific check by increasing ENVCOORD_HOPS_LIMIT.

That's almost certainly the right thing to do, but there's just a bunch of additional work that's needed in order to make that change sound, since the limit is based on the number of bits that we use to represent this "hops" thing -- and to increase the number of bits, we need to change a bunch of types/macros/etc. in a bunch of other places (which got a bit out of my depth, hence the patch being abandoned per comment 6).

For anyone who picks this up - one useful suggestion that came up in review (for my abandoned patch) was: rather than just increasing ENVCOORD_HOPS_LIMIT, we should also add an about:config pref-check there to let us preserve existing behavior, so that we can test the newly broadened type without necessarily changing user-facing behavior right away. More details in
https://phabricator.services.mozilla.com/D249124#8611832
https://phabricator.services.mozilla.com/D249124#8612023

Comment 9

[Bryan Thrall [:bthrall]]

I'm planning on taking a look at this in the next couple of weeks.

Comment 10

[Nicolas B. Pierron [:nbp] {away}]

One alternative would be to make a variant of the bytecode where 255 implies that 4 bytes are used to all the parameters of the opcode.
This would add a branch as part of the opcode, but it should be easy to predict for the branch predictor.

While adding branches is not good, this remains in the interpreter / baseline-interpreter, and would vanish once we switch to the baseline compiled version of the same function.

Comment 11

[Bryan Thrall [:bthrall]]

Attachment: Bug 1966196 - Expand EnvironmentCoordinate hops bitwidth to 16 r=nbp!

16 bits allows JSOp::EnvCallee to support more than 255 hops, but that means
GetAliasedVar, GetAliasedDebugVar, SetAliasedVar, InitAliasedLexical, and
CheckAliasedLexical also increase their length to make hops 16 bits.

Tests breakpoint-dot-generator.js and bug1368736.js needed to adjust their
bytecode offsets to mach the new operation bytelengths.

Test super-in-nested-eval.js no longer runs into the limit on environment chain
lengths (which was 255 and is now 65535), so I set the maximum depth to 300 to
show the 255 limit can now be broken, and verified that large enough depth will
throw InternalError, rather than crashing, by using a ridiculously large
number.

Comment 12

[Bryan Thrall [:bthrall]]

I'm waiting to land this until after Firefox 145 releases so we can get a lot of time with it in Nightly in case I missed something.

Comment 13

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/f0c591856b14
https://hg.mozilla.org/integration/autoland/rev/477b8f5ef6b4
Expand EnvironmentCoordinate hops bitwidth to 16 r=nbp

Comment 14

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/310a64d8d882
https://hg.mozilla.org/integration/autoland/rev/110f199bac6f
Revert "Bug 1966196 - Expand EnvironmentCoordinate hops bitwidth to 16 r=nbp" for causing spidermonkey bustages.

Comment 15

[agoloman]

Backed out for causing spidermonkey bustages.

• Backout link
• Push with failures
• Failure Log @bug1782468-ptrdiff-veclen.js
• Failure Log @Frame-this-06.js.

Comment 16

[agoloman]

Relanded because it is not the regressor.

Comment 17

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/38a774e604ab
https://hg.mozilla.org/integration/autoland/rev/89313c06df5e
Expand EnvironmentCoordinate hops bitwidth to 16 r=nbp

Comment 18

[Sandor Molnar[:smolnar]]

https://hg.mozilla.org/mozilla-central/rev/89313c06df5e