infinite loop in switch-statement with 1800 cases

VERIFIED FIXED in mozilla1.9alpha1

Status

()

Core
JavaScript Engine
P1
critical
VERIFIED FIXED
11 years ago
9 years ago

People

(Reporter: Philipp Vogt, Assigned: brendan)

Tracking

(4 keywords)

Trunk
mozilla1.9alpha1
x86
Linux
hang, testcase, verified1.8.0.2, verified1.8.1
Points:
---
Bug Flags:
blocking1.8.1 +
blocking1.8.0.2 -
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [rft-dl], URL)

Attachments

(4 attachments)

(Reporter)

Description

11 years ago
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)
(Reporter)

Comment 1

11 years ago
Created attachment 209584 [details]
switch with 1800 cases

This example causes an infinite loop.

Comment 2

11 years ago
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

Updated

11 years ago
Keywords: testcase

Updated

11 years ago
Keywords: hang

Updated

11 years ago
Status: UNCONFIRMED → NEW
Ever confirmed: true

Comment 3

11 years ago
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

11 years ago
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.
(Assignee)

Comment 5

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

/be
Assignee: general → brendan
Priority: -- → P1
Target Milestone: --- → mozilla1.9alpha
(Assignee)

Comment 6

11 years ago
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
Blocks: 309169
Status: NEW → ASSIGNED
Flags: blocking1.8.1+
Flags: blocking1.8.0.2?

Comment 7

11 years ago
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).
(Assignee)

Comment 8

11 years ago
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
Attachment #209645 - Flags: superreview?(shaver)
Attachment #209645 - Flags: review?(mrbkap)
(Assignee)

Comment 9

11 years ago
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
(Assignee)

Comment 10

11 years ago
(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
(Assignee)

Comment 11

11 years ago
(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 on attachment 209645 [details] [diff] [review]
fix

r=mrbkap
Attachment #209645 - Flags: review?(mrbkap) → review+
(Assignee)

Comment 13

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

/be
Status: ASSIGNED → RESOLVED
Last Resolved: 11 years ago
Resolution: --- → FIXED

Comment 14

11 years ago
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.
Status: RESOLVED → VERIFIED
Flags: testcase-
Flags: blocking1.8.0.2? → blocking1.8.0.2+
It's getting late for 1.8.0.2, moving request along
Flags: blocking1.8.0.3?
Flags: blocking1.8.0.2-
Flags: blocking1.8.0.2+
(Assignee)

Comment 16

11 years ago
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
Attachment #209645 - Flags: approval1.8.0.2?
Attachment #209645 - Flags: approval-branch-1.8.1+
Flags: blocking1.8.0.3?
Flags: blocking1.8.0.2-
Flags: blocking1.8.0.2+
Comment on attachment 209645 [details] [diff] [review]
fix

approved for 1.8.0 branch, a=dveditz
Attachment #209645 - Flags: approval1.8.0.2? → approval1.8.0.2+
(Assignee)

Comment 18

11 years ago
Fixed on the 1.8* branches.

/be
Flags: blocking1.8.0.2+ → blocking1.8.0.2-
Keywords: fixed1.8.0.2, fixed1.8.1
Comment on attachment 209645 [details] [diff] [review]
fix

sr=shaver
Attachment #209645 - Flags: superreview?(shaver) → superreview+

Updated

11 years ago
Whiteboard: [rft-dl]
no hang on Firefox 1.5.0.2 Windows or Linux builds from 20060306
Keywords: fixed1.8.0.2 → verified1.8.0.2

Comment 21

11 years ago
Checking in regress-324650.js;
/cvsroot/mozilla/js/tests/ecma_3/Statements/regress-324650.js,v  <--  regress-324650.js
initial revision: 1.1
Flags: in-testsuite- → in-testsuite+

Comment 22

11 years ago
verified fixed 1.8.1 20060723 win/linux/mac(ppc|tel)
Keywords: fixed1.8.1 → verified1.8.1

Comment 23

9 years ago
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
You need to log in before you can comment on or make changes to this bug.