324650 - infinite loop in switch-statement with 1800 cases

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Philipp Vogt]

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]

Attachment: switch with 1800 cases

This example causes an infinite loop.

Comment 2

[James Ross]

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]

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]

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]]

Taking -- Silver, thanks a ton for the diagnosis.  Feel free to attach your stuff.

/be

Comment 6

[Brendan Eich [:brendan]]

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]

Attachment: 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]]

Attachment: 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]]

Attachment: 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]]

(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]]

(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) (inactive)]

Comment on attachment 209645 [details] [diff] [review]
fix

r=mrbkap

Comment 13

[Brendan Eich [:brendan]]

Fixed on trunk.  I'll nominate the patch for the branch when shaver reviews it.

/be

Comment 14

[Bob Clary [:bc] (inactive)]

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]]

It's getting late for 1.8.0.2, moving request along

Comment 16

[Brendan Eich [:brendan]]

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]]

Comment on attachment 209645 [details] [diff] [review]
fix

approved for 1.8.0 branch, a=dveditz

Comment 18

[Brendan Eich [:brendan]]

Fixed on the 1.8* branches.

/be

Comment 19

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Comment on attachment 209645 [details] [diff] [review]
fix

sr=shaver

Comment 20

[Tracy Walker [:tracy]]

no hang on Firefox 1.5.0.2 Windows or Linux builds from 20060306

Comment 21

[Bob Clary [:bc] (inactive)]

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] (inactive)]

verified fixed 1.8.1 20060723 win/linux/mac(ppc|tel)

Comment 23

[Bob Clary [:bc] (inactive)]

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