Last Comment Bug 324650 - infinite loop in switch-statement with 1800 cases
: infinite loop in switch-statement with 1800 cases
Status: VERIFIED FIXED
[rft-dl]
: hang, testcase, verified1.8.0.2, verified1.8.1
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: x86 Linux
: P1 critical (vote)
: mozilla1.9alpha1
Assigned To: Brendan Eich [:brendan]
:
: Jason Orendorff [:jorendorff]
Mentors:
http://members.chello.at/philipp.vogt...
Depends on:
Blocks: js1.6rc1
  Show dependency treegraph
 
Reported: 2006-01-25 08:00 PST by Philipp Vogt
Modified: 2008-03-26 13:22 PDT (History)
5 users (show)
brendan: blocking1.8.1+
brendan: blocking1.8.0.2-
bob: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
switch with 1800 cases (109.04 KB, text/html)
2006-01-25 08:01 PST, Philipp Vogt
no flags Details
Handle JOF_LOOKUPSWITCHX in BuildSpanDepTable (2.22 KB, patch)
2006-01-25 15:44 PST, James Ross
no flags Details | Diff | Splinter Review
fix (5.68 KB, patch)
2006-01-25 16:41 PST, Brendan Eich [:brendan]
mrbkap: review+
shaver: superreview+
brendan: approval‑branch‑1.8.1+
dveditz: approval1.8.0.2+
Details | Diff | Splinter Review
js shell testcase (158.60 KB, text/plain)
2006-01-25 16:44 PST, Brendan Eich [:brendan]
no flags Details

Description Philipp Vogt 2006-01-25 08:00:22 PST
User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.10) Gecko/20050925 Firefox/1.0.4 (Debian package 1.0.4-2sarge5)
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.10) Gecko/20050925 Firefox/1.0.4 (Debian package 1.0.4-2sarge5)

I built a switch-statement with 1800 cases which should generate a JSOP_LOOKUPSWITCHX. But it hangs in BuildSpanDepTable(JSContext *cx, JSCodeGenerator *cg) (in jsemit.c) in an infinite loop.

Reproducible: Always

Steps to Reproduce:
1. load html with big switch-statement
2.
3.

Actual Results:  
infinite loop

Expected Results:  
changed picture

Infinite loop in:
- 1.0pre (debug Linux/Windows XP)
- 1.0.4 (Debian Sarge)
- 1.5 (Windows)
Comment 1 Philipp Vogt 2006-01-25 08:01:40 PST
Created attachment 209584 [details]
switch with 1800 cases

This example causes an infinite loop.
Comment 2 James Ross 2006-01-25 08:05:45 PST
This hangs in BuildSpanDepTable in trunk, because at line 556 of http://lxr.mozilla.org/mozilla/source/js/src/jsemit.c#552 |len| is -1 and |op| is JSOP_LOOKUPSWITCHX (148), which causes it to go back a step.

I think it just needs a case for JOF_LOOKUPSWITCHX at http://lxr.mozilla.org/mozilla/source/js/src/jsemit.c#588 like the code at http://lxr.mozilla.org/mozilla/source/js/src/jsopcode.c#233
Comment 3 James Ross 2006-01-25 09:13:58 PST
I tried to fix it by copying that code, but it's now behaving oddly. The first time it goes past the JOF_LOOKUPSWITCHX, everything is fine. The second time, it gets an |npairs| of ~45,000, and after going through about 10,000 of them finally crashes in AddJumpTarget with a bogus |jt| pointer.
Comment 4 James Ross 2006-01-25 12:44:49 PST
This is really hard to follow, but here's some more information.

I arrive in BuildSpanDepTable a few times, and everything goes ok, with |npairs| being 1799 (for this bug's testcase), as expected. OptimizeSpanDeps gets called twice, once after emitting the JSOP_SWITCH stuff, and then later after at least one of the BREAKs have been patched up. It's after the second call that things go a little funny. Here I am in BuildSpanDepTable again (patching a BREAK), and I have a |pc| of 0x04bfb710, with the following dump of memory:
  94 00 01 b0 43 b0 43 07 07 00 05 2a 31 2a 31 00 

94          is JOF_LOOKUPSWITCHX - good.
00 01 b0 43 is the longjump to the end of the switch code - good.

Now we're stuffed. We've got b0 43 again, which is definately NOT the number of items in the switch - that is 07 07!

It looks to me like the switch has been extended to the X version twice, or something like that. I don't pretend to actually understand all the code here, though, but it looks very much like it's got an extra two bytes it shouldn't have.

Some information from the reporter (over IRC) was that this bug does not appear to occur if there is only the large switch - you need at least normal (small) one after it to cause it.

I hope that's useful to someone, because I'm really not sure what to prod at this stage. I can put the patch I've used to get this far on the bug if that would be helpful to anyone.
Comment 5 Brendan Eich [:brendan] 2006-01-25 14:22:52 PST
Taking -- Silver, thanks a ton for the diagnosis.  Feel free to attach your stuff.

/be
Comment 6 Brendan Eich [:brendan] 2006-01-25 15:30:48 PST
This is just a dumb logic bug, lack of coordination between the spandep stuff and the incremental compilation magic in jsparse.c:Statements, which compiles each top-level statement and moves on to the next, appending bytecode (no backward goto across top-levels in JS, so we can do this).  The spandep optimization state for the previous top-level statement is cleared, but backpatch state in the cg is not reset after codegen.  D'oh!

/be
Comment 7 James Ross 2006-01-25 15:44:22 PST
Created attachment 209637 [details] [diff] [review]
Handle JOF_LOOKUPSWITCHX in BuildSpanDepTable

This is the patch I was running whilest getting the results in comment 4 (without the patch, it just hangs with an infinite loop as described in comment 2).
Comment 8 Brendan Eich [:brendan] 2006-01-25 16:41:42 PST
Created attachment 209645 [details] [diff] [review]
fix

Fix is straightforward, but while testing a js shell version of the testcase, I found an unrelated bug: cg->main.lastNoteOffset (aka CG_LAST_NOTE_OFFSET(cg) most of the time) was not advanced in OptimizeSpanDeps to account for growth due to extended jump offsets before the last note's offset.  Who tested this crap! :-P

/be
Comment 9 Brendan Eich [:brendan] 2006-01-25 16:44:31 PST
Created attachment 209646 [details]
js shell testcase

This has a bug in it:

spandepbug.js:5420: TypeError: document.images[0] has no properties

but this symptom pointed pretty directly to the failure of OptimizeSpanDeps to update cg->main.lastNoteOffset.

/be
Comment 10 Brendan Eich [:brendan] 2006-01-25 23:32:02 PST
(In reply to comment #9)
> Created an attachment (id=209646) [edit]
> js shell testcase
> 
> This has a bug in it:
> 
> spandepbug.js:5420: TypeError: document.images[0] has no properties
> 
> but this symptom pointed pretty directly to the failure of OptimizeSpanDeps to
> update cg->main.lastNoteOffset.

To clarify, with the bug (without attachment 209645 [details] [diff] [review]), you would get

spandepbug.js:5416: TypeError: undefined has no properties

/be
Comment 11 Brendan Eich [:brendan] 2006-01-25 23:34:04 PST
(In reply to comment #10)
> To clarify, with the bug (without attachment 209645 [details] [diff] [review] [edit]), you would get
> 
> spandepbug.js:5416: TypeError: undefined has no properties

Sorry, I'm too tired to be trusted right now.  I meant with the patch, but without its fix to update cg->main.lastNoteOffset (+= growth).

/be
Comment 12 Blake Kaplan (:mrbkap) 2006-01-26 11:39:53 PST
Comment on attachment 209645 [details] [diff] [review]
fix

r=mrbkap
Comment 13 Brendan Eich [:brendan] 2006-01-26 13:06:38 PST
Fixed on trunk.  I'll nominate the patch for the branch when shaver reviews it.

/be
Comment 14 Bob Clary [:bc:] 2006-02-13 16:21:07 PST
I am going to mark this testcase- since I don't know of a way to terminate the test when it fails in the shell. 

verified fixed 2006-02-11/winxp/shell&browser.
Comment 15 Daniel Veditz [:dveditz] 2006-02-26 12:31:44 PST
It's getting late for 1.8.0.2, moving request along
Comment 16 Brendan Eich [:brendan] 2006-02-27 17:08:46 PST
Comment on attachment 209645 [details] [diff] [review]
fix

Renominating -- this testcase shows a hang, but i'm concerned that crashes are possible with variations.  Also, fix is well-baked and understood.

/be
Comment 17 Daniel Veditz [:dveditz] 2006-02-27 17:18:36 PST
Comment on attachment 209645 [details] [diff] [review]
fix

approved for 1.8.0 branch, a=dveditz
Comment 18 Brendan Eich [:brendan] 2006-02-27 18:02:02 PST
Fixed on the 1.8* branches.

/be
Comment 19 Mike Shaver (:shaver -- probably not reading bugmail closely) 2006-02-27 18:22:26 PST
Comment on attachment 209645 [details] [diff] [review]
fix

sr=shaver
Comment 20 Tracy Walker [:tracy] 2006-03-06 13:39:08 PST
no hang on Firefox 1.5.0.2 Windows or Linux builds from 20060306
Comment 21 Bob Clary [:bc:] 2006-07-20 15:36:21 PDT
Checking in regress-324650.js;
/cvsroot/mozilla/js/tests/ecma_3/Statements/regress-324650.js,v  <--  regress-324650.js
initial revision: 1.1
Comment 22 Bob Clary [:bc:] 2006-07-25 00:28:07 PDT
verified fixed 1.8.1 20060723 win/linux/mac(ppc|tel)
Comment 23 Bob Clary [:bc:] 2008-03-26 13:22:08 PDT
remove unneeded image foo from test

/cvsroot/mozilla/js/tests/ecma_3/Statements/regress-324650.js,v  <--  regress-324650.js
new revision: 1.3; previous revision: 1.2

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