398085 - Crash with large switch statement [@ js_Interpret]

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Carsten Book [:Tomcat]]

Mozilla/5.0 (Windows; U; Windows NT 5.2; en-US; rv:1.9a9pre) Gecko/2007092705 Minefield/3.0a9pre ID:2007092705 and latest 1.8 Nightly Crash when http://www.investors.com/newsResearchAnalysis.asp is loaded

http://crash-stats.mozilla.com/report/index/c621f76b-6f9a-11dc-b93c-001a4bd43ed6?date=2007-09-30-21

Stack of Crashing Thread
frame 	signature 	source
0 	js_Interpret 	mozilla/js/src/jsinterp.c:4515
1 	js_Execute 	mozilla/js/src/jsinterp.c:1622
2 	JS_EvaluateUCScriptForPrincipals 	mozilla/js/src/jsapi.c:4878
3 	nsJSContext::EvaluateString(nsAString_internal const&, void*, nsIPrincipal*, char const*, unsigned int, unsigned int, nsAString_internal*, int*) 	mozilla/dom/src/base/nsJSEnvironment.cpp:1389
4 	nsScriptLoader::EvaluateScript(nsScriptLoadRequest*, nsString const&) 	mozilla/content/base/src/nsScriptLoader.cpp:607
5 	nsScriptLoader::ProcessRequest(nsScriptLoadRequest*) 	mozilla/content/base/src/nsScriptLoader.cpp:521
6 	nsScriptLoader::ProcessScriptElement(nsIScriptElement*) 	mozilla/content/base/src/nsScriptLoader.cpp:486
7 	nsScriptElement::MaybeProcessScript() 	mozilla/content/base/src/nsScriptElement.cpp:188
8 	nsHTMLScriptElement::MaybeProcessScript() 	mozilla/content/html/content/src/nsHTMLScriptElement.cpp:536
9 	nsHTMLScriptElement::DoneAddingChildren(int) 	mozilla/content/html/content/src/nsHTMLScriptElement.cpp:482
10 	HTMLContentSink::ProcessSCRIPTEndTag(nsGenericHTMLElement*, int) 	mozilla/content/html/document/src/nsHTMLContentSink.cpp:3141
11 	SinkContext::CloseContainer(nsHTMLTag, int) 	mozilla/content/html/document/src/nsHTMLContentSink.cpp:1008
12 	HTMLContentSink::CloseContainer(nsHTMLTag) 	mozilla/content/html/document/src/nsHTMLContentSink.cpp:2406
13 	CNavDTD::CloseContainer(nsHTMLTag, int) 	mozilla/parser/htmlparser/src/CNavDTD.cpp:2686
14 	CNavDTD::HandleEndToken(CToken*) 	mozilla/parser/htmlparser/src/CNavDTD.cpp:1590
15 	CNavDTD::HandleToken(CToken*, nsIParser*) 	mozilla/parser/htmlparser/src/CNavDTD.cpp:705
16 	CNavDTD::BuildModel(nsIParser*, nsITokenizer*, nsITokenObserver*, nsIContentSink*) 	mozilla/parser/htmlparser/src/CNavDTD.cpp:331
17 	nsParser::BuildModel() 	mozilla/parser/htmlparser/src/nsParser.cpp:1717
18 	nsParser::ResumeParse(int, int, int) 	mozilla/parser/htmlparser/src/nsParser.cpp:1594
19 	nsParser::ContinueInterruptedParsing() 	mozilla/parser/htmlparser/src/nsParser.cpp:1118
20 	nsContentSink::ContinueInterruptedParsingIfEnabled() 	mozilla/content/base/src/nsContentSink.cpp:1494
21 	nsRunnableMethod<nsContentSink>::Run() 	nsThreadUtils.h:261
22 	nsThread::ProcessNextEvent(int, int*) 	mozilla/xpcom/threads/nsThread.cpp:490
23 	NS_ProcessNextEvent_P(nsIThread*, int) 	nsThreadUtils.cpp:227
24 	nsBaseAppShell::Run() 	mozilla/widget/src/xpwidgets/nsBaseAppShell.cpp:154
25 	nsAppStartup::Run() 	mozilla/toolkit/components/startup/src/nsAppStartup.cpp:170
26 	XRE_main 	mozilla/toolkit/xre/nsAppRunner.cpp:3114
27 	main 	mozilla/browser/app/nsBrowserApp.cpp:153
28 	WinMain 	mozilla/browser/app/nsBrowserApp.cpp:166
29 	__tmainCRTStartup 	crtexe.c:589
30 	kernel32.dll@0x27d29

Comment 2

[Marcia Knous [:marcia]]

I see this crash on Mac as well - Changing to all and noting that is crashes the latest Bon Echo branch as well.

Comment 3

[Daniel Veditz [:dveditz]]

I don't think we can block 1.8.1.8 on this since we don't even have the beginnings of a fix.

Can you try to save the page locally (complete) and see if the crash is still reproducible? If so then zip that and attach to the bug, just in case the investorsdaily page changes. Reproducible testcases are like gold, don't lose this one.

Comment 4

[Carsten Book [:Tomcat]]

Attachment: locally saved html file as testcase - crash on load

Comment 5

[Carsten Book [:Tomcat]]

Attachment: saved webpage

Comment 6

[:Gavin Sharp [email: [e-mail]]]

Attachment: smaller testcase (crashes on load)

I'm not sure whether this is minimal, but reducing the size of the switch statement any further seems to cause the crash to disappear.

Comment 7

[:Gavin Sharp [email: [e-mail]]]

I crash with relatively recent trunk and 1.8 branch builds, on Windows.

Comment 8

[:Gavin Sharp [email: [e-mail]]]

I don't crash if I pass arguments to long_switch that don't match a "case" in the switch, or if I remove some of the duplicated statements inside the switches.

Comment 9

[Peter van der Woude [:Peter6]]

looks like the crash on http://www.investors.com/editorial/cartoon.asp

bp-9d4acaee-70ec-11dc-8623-001a4bd43ef6

Comment 10

[Brendan Eich [:brendan]]

Regressed when?

/be

Comment 11

[Peter van der Woude [:Peter6]]

(In reply to comment #10)
> Regressed when?
> 
> /be
> 
I'll look for that later today

Comment 12

[Peter van der Woude [:Peter6]]

sorry, i'm unable to reproduce the crash on either of the 2 pages so i can't get a regressionwindow.
I tried with both my daily and a new profile, no crash.

Comment 13

[Peter van der Woude [:Peter6]]

the 3rd testcase crashes on all my builds, all the way back till 20060401

Comment 14

[Aiko]

Attachment: simplified testcase

I've looked at the disassembly of this testcase and the previous one and here's what happening AFAICS:

1. During compilation, if a JSOP_LOOKUPSWITCH is generated inside a JSOP_LOOKUPSWITCHX more than 32KB after the JSOP_LOOKUPSWITCHX opcode, then SpiderMonkey will erronously emit 32-bit offsets for the JSOP_LOOKUPSWITCH!
2. When the interpreter executes this JSOP_LOOKUPSWITCH and finds the match, these 32 bit offsets are looked up with GET_JUMP_OFFSET (the 16-bit version).
3. This leads to len == 0 in jsinterp.c line 4534. 
4. len is added to the current PC, which means the same JSOP_LOOKUPSWITCH is executed again, but this time it will pop some random garbage from the stack and use that garbage as its lval. This crashes sooner or later...

I could try to locate the bug in the emitter but I don't know this code at all so don't hold your breath; it could take ages. Perhaps this information is enough for one of the regulars to come up with a quick fix.

Comment 15

[timeless]

http://mxr.landfill.bugzilla.org/js/search?find=%2Fjs%2Fsrc%2F&string=JSOP_LOOKUPSWITCH

not too much to read :)

Comment 16

[Aiko]

That analysis was a bit wrong, let's try again. If the switch statement (doesn't matter if it uses lookupswitch or tableswitch) comes more than 32K after the start of the function, then all jump offsets are 0. These 32K code can be anything, it's only important that cg->spanDeps is not null, then js_SetJumpOffset generates 0 offsets.

Comment 17

[Aiko]

Attachment: another testcase

Switch statements in large functions is quite broken. In this testcase the switch can't be reached but its mere presence causes the emitter to generate the wrong bytecode for the 'if' statement. It should be 'ifeqx 32804', but it is 'ifeq 14' instead.

With this trick an attacker could get the engine to execute arbitrary bytecodes so this might be security sensitive?

Comment 18

[Igor Bukanov]

(In reply to comment #17)
> With this trick an attacker could get the engine to execute arbitrary bytecodes
> so this might be security sensitive?

Yes, this is a security hazard.

Comment 19

[Igor Bukanov]

here is a test case for the shell:

var N = 6000;

// Array(N).join('a.x;') generates (N+1)*(5+1) bytes in bytecode
// where 5 comes getargprop and one from pop.

var src = 'if (a) {'+Array(N).join('a.x;')+'return "Bug"; }'+
          'return 1; '+
          ' switch (a) { case 1: ; case 2: return; }';

var f = Function('a', src);

var result = f(false);
if (result !== 1)
    throw "Bogus compilation is detected";

Comment 20

[Igor Bukanov]

Attachment: fix v1

The reason for the bug is that EmitSwitch from jsemit.c calls js_SetJumpOffset on the switch jumps without making sure that span dependencies are added for the jumps. js_SetJumpOffset only adds span dependencies for the already emitted code on the first big jump when cg->spanDeps is null. Thus when cg->spanDeps is not null before the switch (this is exactly the situation that the test case triggers) the code must call AddSpanDep on all the jumps. 

Without the fix the code will treat 0 recorded at the jump offset as an index into the first span dependency record eventually overwriting it with the relative jumps for the switch.

Comment 21

[Igor Bukanov]

(In reply to comment #17)
> Created an attachment (id=286699) [details]
> another testcase

Thanks for the test cases! With them fixing the bug was just a matter of spending time.

Comment 22

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 287014 [details] [diff] [review]
fix v1

Can't approve unreviewed patches :(

Comment 23

[Brian Crowder]

Would it be too optimistic to leave the request flags, in the hopes that brendan -will- approve this patch soon?  :)

Comment 24

[:Gavin Sharp [email: [e-mail]]]

(In reply to comment #23)
> Would it be too optimistic to leave the request flags, in the hopes that
> brendan -will- approve this patch soon?  :)

Clearing the flag allows drivers to keep the outstanding request list minimal, which makes it easier to notice new additions and track progress of approval triage.

Comment 25

[Igor Bukanov]

(In reply to comment #24)
> Clearing the flag allows drivers to keep the outstanding request list minimal,
> which makes it easier to notice new additions and track progress of approval
> triage.

So the right thing to do is to set blocking flags for the bug which has already been done.

Comment 26

[Brendan Eich [:brendan]]

Comment on attachment 287014 [details] [diff] [review]
fix v1

>+AddSwitchSpanDep(JSContext *cx, JSCodeGenerator *cg, jsbytecode *pc)

Call this AddSwitchSpanDeps.

>+{
>+    JSOp op;
>+    jsbytecode *pc2;
>+    ptrdiff_t off;
>+    jsint low, high;
>+    uintN njumps, indexLen;

Nutty style consistency rule would favor indexlen (since Len is not a word, it's not Length) here.

>         /*
>          * After this point, all control flow involving JSOP_TABLESWITCH
>          * must set ok and goto out to exit this function.  To keep things
>          * simple, all switchOp cases exit that way.
>          */
>+

Not sure that blank line is worth it.

>+        if (cg->spanDeps) {
>+            /*
>+             * We already generated at least one big jump so we must
>+             * explicitly add span dependencies for the switch jumps.
>+             * Called below js_SetJumpOffset can only do it when patching

Comma aftert "Called below", could even say "When called below, ..." here.

r/a=me.

/be

Comment 27

[Igor Bukanov]

Attachment: fix v2

The previous version of my patch has a bug in AddSwitchSpanDeps where it returns JS_FALSE, not -1, to indicate a failure. In the new version I, besides addressing the nits, use jsbytecode * as a return type for the function to simplify BuildSpanDepTable.

Comment 28

[Brendan Eich [:brendan]]

Comment on attachment 287339 [details] [diff] [review]
fix v2

Good for M9 if there's time.

/be

Comment 29

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 287339 [details] [diff] [review]
fix v2

a=endgame drivers for M9

Comment 30

[Igor Bukanov]

I checked in the patch from comment 27 to the CVS trunk:

http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&branch=HEAD&cvsroot=%2Fcvsroot&date=explicit&mindate=1194378060&maxdate=1194378091&who=igor%mir2.org

Comment 31

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/Regress/regress-398085-01.js

Comment 32

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/Regress/regress-398085-02.js

Comment 33

[Bob Clary [:bc] (inactive)]

verified fixed 1.9.0 linux|mac|win

Comment 34

[Daniel Veditz [:dveditz]]

Do we need a separate patch for the 1.8 branch or does this one apply? If this one works please ask for approval1.8.1.12 on it, or else please create the branch version of this patch.

Comment 35

[Igor Bukanov]

Attachment: fix for 1.8.1 v1

This is hand-merge of the trunk fix.

Comment 36

[Igor Bukanov]

Attachment: diff between trunk and 1.8.1 versions of the fix

1.8.1 version of the fix required a hand merge as a trunk version uses UINT16_LEN and INDEX_LEN constants that do not exist on 1.8.1 branch.

Comment 37

[Igor Bukanov]

Comment on attachment 294254 [details] [diff] [review]
fix for 1.8.1 v1

r+ is based on triviality of hand-merge.

Comment 38

[Daniel Veditz [:dveditz]]

Comment on attachment 294254 [details] [diff] [review]
fix for 1.8.1 v1

approved for 1.8.1.12, a=dveditz for release-drivers

Comment 39

[Igor Bukanov]

I checked in the patch from comment 35 to MOZILLA_1_8_BRANCH:

Checking in jsemit.c;
/cvsroot/mozilla/js/src/jsemit.c,v  <--  jsemit.c
new revision: 3.128.2.74; previous revision: 3.128.2.73
done

Comment 40

[Bob Clary [:bc] (inactive)]

verified fixed 1.8.1 linux/mac/win

Comment 41

[Alexander Sack]

distro patch block 1.8.0.15

Comment 42

[Alexander Sack]

Attachment: for 1.8.0

igor, please review if this patch still makes sense on the 1.8.0 branch.

Comment 43

[Igor Bukanov]

(In reply to comment #42)
> Created an attachment (id=308877) [details]
> for 1.8.0
> 
> igor, please review if this patch still makes sense on the 1.8.0 branch.

Could you attach a plain diff between 1.8.1 and 1.8.0 versions? 

Comment 44

[Alexander Sack]

Attachment: diff between 1.8.1 and 1.8.0 version of this patch

Comment 45

[Alexander Sack]

Comment on attachment 310208 [details] [diff] [review]
diff between 1.8.1 and 1.8.0 version of this patch


if that helps i can also post an excerpt of the diffed code section _after_ applying the 1.8.0 patch

Comment 46

[Alexander Sack]

Attachment: 1.8.1 to 1.8.0 diff (plain style)

ok, now i see what you ment by _plain_ diff.

Comment 47

[Igor Bukanov]

Comment on attachment 310213 [details] [diff] [review]
1.8.1 to 1.8.0 diff (plain style)

This is a helper attachment and should not bear any flags.

Comment 48

[Alexander Sack]

Comment on attachment 308877 [details] [diff] [review]
for 1.8.0

a=asac for 1.8.0.15

Comment 49

[Christopher Aillon (sabbatical, not receiving bugmail)]

Committed to the 1.8.0 branch

Comment 50

[Bob Clary [:bc] (inactive)]

/cvsroot/mozilla/js/tests/js1_5/Regress/regress-398085-01.js,v  <--  regress-398085-01.js
initial revision: 1.1
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-398085-02.js,v  <--  regress-398085-02.js
initial revision: 1.1