Last Comment Bug 398085 - Crash with large switch statement [@ js_Interpret]
: Crash with large switch statement [@ js_Interpret]
Status: VERIFIED FIXED
[sg:critical]
: crash, fixed1.8.0.15, testcase, verified1.8.1.12
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: -- critical (vote)
: ---
Assigned To: Igor Bukanov
:
Mentors:
http://www.investors.com/newsResearch...
: 398122 (view as bug list)
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2007-09-30 14:24 PDT by Carsten Book [:Tomcat]
Modified: 2012-01-23 18:49 PST (History)
18 users (show)
dveditz: blocking1.8.1.12+
dveditz: wanted1.8.1.x+
asac: blocking1.8.0.next+
bob: in‑testsuite+
bob: in‑litmus-
See Also:
Crash Signature:
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
locally saved html file as testcase - crash on load (88.55 KB, text/html)
2007-10-01 16:01 PDT, Carsten Book [:Tomcat]
no flags Details
saved webpage (71.56 KB, application/octet-stream)
2007-10-01 16:13 PDT, Carsten Book [:Tomcat]
no flags Details
smaller testcase (crashes on load) (230.70 KB, text/html)
2007-10-01 20:29 PDT, :Gavin Sharp [email: gavin@gavinsharp.com]
no flags Details
simplified testcase (40.11 KB, text/html)
2007-10-29 15:24 PDT, Aiko
no flags Details
another testcase (36.50 KB, text/html)
2007-10-30 10:13 PDT, Aiko
no flags Details
fix v1 (4.69 KB, patch)
2007-11-01 14:18 PDT, Igor Bukanov
brendan: review+
brendan: approval1.9+
Details | Diff | Splinter Review
fix v2 (5.12 KB, patch)
2007-11-04 15:20 PST, Igor Bukanov
brendan: review+
mbeltzner: approvalM9+
brendan: approval1.9+
Details | Diff | Splinter Review
js1_5/Regress/regress-398085-01.js (38.18 KB, text/plain)
2007-11-09 15:23 PST, Bob Clary [:bc:]
no flags Details
js1_5/Regress/regress-398085-02.js (37.43 KB, text/plain)
2007-11-09 15:24 PST, Bob Clary [:bc:]
no flags Details
fix for 1.8.1 v1 (5.14 KB, patch)
2007-12-21 11:25 PST, Igor Bukanov
igor: review+
dveditz: approval1.8.1.12+
Details | Diff | Splinter Review
diff between trunk and 1.8.1 versions of the fix (1.15 KB, text/plain)
2007-12-21 11:29 PST, Igor Bukanov
no flags Details
for 1.8.0 (5.30 KB, patch)
2008-03-12 09:02 PDT, Alexander Sack
igor: review+
asac: approval1.8.0.next+
Details | Diff | Splinter Review
diff between 1.8.1 and 1.8.0 version of this patch (3.18 KB, patch)
2008-03-18 03:31 PDT, Alexander Sack
no flags Details | Diff | Splinter Review
1.8.1 to 1.8.0 diff (plain style) (2.14 KB, patch)
2008-03-18 03:36 PDT, Alexander Sack
no flags Details | Diff | Splinter Review

Description Carsten Book [:Tomcat] 2007-09-30 14:24:05 PDT
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 1 Marcia Knous [:marcia - use ni] 2007-10-01 11:48:27 PDT
*** Bug 398122 has been marked as a duplicate of this bug. ***
Comment 2 Marcia Knous [:marcia - use ni] 2007-10-01 11:50:04 PDT
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] 2007-10-01 14:43:57 PDT
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] 2007-10-01 16:01:07 PDT
Created attachment 283078 [details]
locally saved html file as testcase - crash on load
Comment 5 Carsten Book [:Tomcat] 2007-10-01 16:13:29 PDT
Created attachment 283079 [details]
saved webpage
Comment 6 :Gavin Sharp [email: gavin@gavinsharp.com] 2007-10-01 20:29:57 PDT
Created attachment 283125 [details]
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: gavin@gavinsharp.com] 2007-10-01 20:43:56 PDT
I crash with relatively recent trunk and 1.8 branch builds, on Windows.
Comment 8 :Gavin Sharp [email: gavin@gavinsharp.com] 2007-10-01 20:46:10 PDT
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] 2007-10-02 15:13:21 PDT
looks like the crash on http://www.investors.com/editorial/cartoon.asp

bp-9d4acaee-70ec-11dc-8623-001a4bd43ef6
Comment 10 Brendan Eich [:brendan] 2007-10-06 00:09:13 PDT
Regressed when?

/be
Comment 11 Peter van der Woude [:Peter6] 2007-10-06 00:15:55 PDT
(In reply to comment #10)
> Regressed when?
> 
> /be
> 
I'll look for that later today
Comment 12 Peter van der Woude [:Peter6] 2007-10-06 09:07:55 PDT
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] 2007-10-06 09:51:43 PDT
the 3rd testcase crashes on all my builds, all the way back till 20060401
Comment 14 Aiko 2007-10-29 15:24:39 PDT
Created attachment 286614 [details]
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 16 Aiko 2007-10-30 03:32:40 PDT
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 2007-10-30 10:13:52 PDT
Created attachment 286699 [details]
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 2007-10-30 10:47:28 PDT
(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 2007-11-01 06:45:49 PDT
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 2007-11-01 14:18:19 PDT
Created attachment 287014 [details] [diff] [review]
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 2007-11-01 14:19:28 PDT
(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] 2007-11-02 10:15:21 PDT
Comment on attachment 287014 [details] [diff] [review]
fix v1

Can't approve unreviewed patches :(
Comment 23 Brian Crowder 2007-11-02 10:21:51 PDT
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: gavin@gavinsharp.com] 2007-11-02 10:29:15 PDT
(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 2007-11-02 16:26:54 PDT
(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] 2007-11-04 01:55:31 PDT
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 2007-11-04 15:20:30 PST
Created attachment 287339 [details] [diff] [review]
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] 2007-11-05 18:22:20 PST
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] 2007-11-06 10:37:43 PST
Comment on attachment 287339 [details] [diff] [review]
fix v2

a=endgame drivers for M9
Comment 31 Bob Clary [:bc:] 2007-11-09 15:23:48 PST
Created attachment 288062 [details]
js1_5/Regress/regress-398085-01.js
Comment 32 Bob Clary [:bc:] 2007-11-09 15:24:33 PST
Created attachment 288063 [details]
js1_5/Regress/regress-398085-02.js
Comment 33 Bob Clary [:bc:] 2007-11-18 14:24:22 PST
verified fixed 1.9.0 linux|mac|win
Comment 34 Daniel Veditz [:dveditz] 2007-12-17 11:50:18 PST
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 2007-12-21 11:25:27 PST
Created attachment 294254 [details] [diff] [review]
fix for 1.8.1 v1

This is hand-merge of the trunk fix.
Comment 36 Igor Bukanov 2007-12-21 11:29:54 PST
Created attachment 294255 [details]
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 2007-12-21 11:31:09 PST
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] 2007-12-21 12:10:24 PST
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 2007-12-21 12:16:32 PST
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:] 2008-01-09 06:59:48 PST
verified fixed 1.8.1 linux/mac/win
Comment 41 Alexander Sack 2008-03-12 09:01:26 PDT
distro patch block 1.8.0.15
Comment 42 Alexander Sack 2008-03-12 09:02:58 PDT
Created attachment 308877 [details] [diff] [review]
for 1.8.0

igor, please review if this patch still makes sense on the 1.8.0 branch.
Comment 43 Igor Bukanov 2008-03-12 09:21:16 PDT
(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 2008-03-18 03:31:43 PDT
Created attachment 310208 [details] [diff] [review]
diff between 1.8.1 and 1.8.0 version of this patch
Comment 45 Alexander Sack 2008-03-18 03:34:14 PDT
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 2008-03-18 03:36:55 PDT
Created attachment 310213 [details] [diff] [review]
1.8.1 to 1.8.0 diff (plain style)

ok, now i see what you ment by _plain_ diff.
Comment 47 Igor Bukanov 2008-03-18 03:50:21 PDT
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 2008-03-18 04:05:34 PDT
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) 2008-03-20 13:43:56 PDT
Committed to the 1.8.0 branch
Comment 50 Bob Clary [:bc:] 2008-03-29 15:37:54 PDT
/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

Note You need to log in before you can comment on or make changes to this bug.