Closed Bug 347155 Opened 18 years ago Closed 17 years ago

Crash due to too much recursion [@ js_FoldConstants] with deeply nested e4x literal

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
critical

Tracking

()

VERIFIED FIXED

People

(Reporter: jruderman, Assigned: crowderbt)

Details

(4 keywords)

Crash Data

Attachments

(3 files)

 
Attached file testcase
I've found two spots where nested XML elements can crash:

1. For large nesting levels (as in the testcase) there is a chain of XMLElementOrList <-> XMLElementContent calls that will eventually overflow the stack.

2. Smaller nesting levels pass the first stage and then overflow the stack when ParseNodeToXML calls itself.

Patch coming up next.
OS: Mac OS X 10.4 → All
Hardware: Macintosh → All
Attachment #250831 - Flags: review?(brendan)
Comment on attachment 250831 [details] [diff] [review]
Add recursion checks

Looks good to me, but I'd rather defer to a peer for review and landing.  Thanks for the patch!  

Does the limit seem generous enough, given the stack size limit, or should we work harder to reduce stack consumption in order to handle more deeply-nested XML?

/be
Attachment #250831 - Flags: review?(brendan) → review?(crowder)
Assignee: general → crowder
Status: NEW → ASSIGNED
On my MBP, using this testcase, I am still able to get something like 5500 stack-frames worth of XML parsing before hitting this error.  Brendan, have you got any intuition or evidence that that is not enough?
Sounds like more than enough to me.  Never mind!

/be
Comment on attachment 250831 [details] [diff] [review]
Add recursion checks

Great.  I'll land this on trunk momentarily.  Good for branches, too?
Attachment #250831 - Flags: review?(crowder)
Attachment #250831 - Flags: review+
Attachment #250831 - Flags: approval1.8.1.2?
Attachment #250831 - Flags: approval1.8.0.10?
Checking in jsparse.c;
/cvsroot/mozilla/js/src/jsparse.c,v  <--  jsparse.c
new revision: 3.266; previous revision: 3.265
done
Checking in jsxml.c;
/cvsroot/mozilla/js/src/jsxml.c,v  <--  jsxml.c
new revision: 3.137; previous revision: 3.136
done
Comment on attachment 250831 [details] [diff] [review]
Add recursion checks

Approved for both branches, a=jay for drivers.
Attachment #250831 - Flags: approval1.8.1.2?
Attachment #250831 - Flags: approval1.8.1.2+
Attachment #250831 - Flags: approval1.8.0.10?
Attachment #250831 - Flags: approval1.8.0.10+
MOZILLA_1_8_BRANCH:

Checking in jsparse.c;
/cvsroot/mozilla/js/src/jsparse.c,v  <--  jsparse.c
new revision: 3.142.2.73; previous revision: 3.142.2.72
done
Checking in jsxml.c;
/cvsroot/mozilla/js/src/jsxml.c,v  <--  jsxml.c
new revision: 3.50.2.58; previous revision: 3.50.2.57
done


MOZILLA_1_8_0_BRANCH:

Checking in jsparse.c;
/cvsroot/mozilla/js/src/jsparse.c,v  <--  jsparse.c
new revision: 3.142.2.6.2.12; previous revision: 3.142.2.6.2.11
done
Checking in jsxml.c;
/cvsroot/mozilla/js/src/jsxml.c,v  <--  jsxml.c
new revision: 3.50.2.15.2.29; previous revision: 3.50.2.15.2.28
done
Status: ASSIGNED → RESOLVED
Closed: 18 years ago
Resolution: --- → FIXED
Verified fixed for 1.8.1.2 and 1.8.0.10 with Mozilla/5.0 (Windows; U; Windows NT 5.2; en-US; rv:1.8.1.2pre) Gecko/20070109 BonEcho/2.0.0.2pre and Mozilla/5.0 (Windows; U; Windows NT 5.2; en-US; rv:1.8.0.10pre) Gecko/20070109 Firefox/1.5.0.10pre and on Linux Fedora FC 6
Status: RESOLVED → VERIFIED
/cvsroot/mozilla/js/tests/e4x/Regress/regress-347155.js,v  <--  regress-347155.js
initial revision: 1.1
Flags: in-testsuite+
Not sure this should be marked VERIFIED for 1.8.0.10, because the patch did not land there. Instead I see

$ cvs diff -r3.142.2.6.2.1{1,2} jsparse.c
Index: jsparse.c
===================================================================
RCS file: /cvsroot/mozilla/js/src/jsparse.c,v
retrieving revision 3.142.2.6.2.11
retrieving revision 3.142.2.6.2.12
diff -p -u -8 -r3.142.2.6.2.11 -r3.142.2.6.2.12
--- jsparse.c   19 Dec 2006 23:46:36 -0000      3.142.2.6.2.11
+++ jsparse.c   9 Jan 2007 00:27:44 -0000       3.142.2.6.2.12
@@ -3500,16 +3500,18 @@ XMLElementOrList(JSContext *cx, JSTokenS
 static JSBool
 XMLElementContent(JSContext *cx, JSTokenStream *ts, JSParseNode *pn,
                   JSTreeContext *tc)
 {
     JSTokenType tt;
     JSParseNode *pn2;
     JSAtom *textAtom;
 
+    CHECK_RECURSION();
+
     ts->flags &= ~TSF_XMLTAGMODE;
     for (;;) {
         ts->flags |= TSF_XMLTEXTMODE;
         tt = js_GetToken(cx, ts);
         ts->flags &= ~TSF_XMLTEXTMODE;
         XML_CHECK_FOR_ERROR_AND_EOF(tt, JS_FALSE);
 
         JS_ASSERT(tt == TOK_XMLSPACE || tt == TOK_XMLTEXT);

which results in a GCC warning about the return NULL hidden in CHECK_RECURSION vs. JSBool return type.

/be
Status: VERIFIED → REOPENED
Resolution: FIXED → ---
Either manually did the original branch patch wrong or patch broke on me.  Probably the former.  This corrects my mistake.  Sorry.
Attachment #251835 - Flags: review?(brendan)
Attachment #251835 - Flags: approval1.8.0.10?
Comment on attachment 251835 [details] [diff] [review]
moving recursion check to the right place

If the bug was verified1.8.0.10 perhaps the test doesn't cover this case in jsparse.c?

/be
Attachment #251835 - Flags: review?(brendan) → review+
(In reply to comment #15)
> (From update of attachment 251835 [details] [diff] [review])
> If the bug was verified1.8.0.10 perhaps the test doesn't cover this case in
> jsparse.c?

Oh, I see -- the misplaced CHECK_RECURSION which added a warning nevertheless would fix the bug.

Jay, we still want this followup fix for 1.8.0.10, to get rid of the warning and make the fix match 1.8 branch and trunk.

/be
Would a recursion check (albeit a badly written one) in XMLElementContent not yield the same (or very similar) results?
(In reply to comment #15)
> (From update of attachment 251835 [details] [diff] [review])
> If the bug was verified1.8.0.10 perhaps the test doesn't cover this case in
> jsparse.c?
> 

The crash doesn't appear in the shell or browser in 1.8.0, but "something" is wrong since the shell fails to load the referenced files in 1.8.0, but works fine in 1.8.1 and 1.9.0.

$ /work/mozilla/builds/1.8.0/mozilla/js/src/WINNT5.1_DBG.OBJ/js -f ../shell.js -f regress-347155.js
can't open ../shell.js: No such file or directory
can't open regress-347155.js: No such file or directory

$ /work/mozilla/builds/1.8.1/mozilla/js/src/WINNT5.1_DBG.OBJ/js -f ../shell.js -f regress-347155.js
BUGNUMBER: 347155
STATUS: Do not crash with deeply nested e4x literal
PASSED! 1

Well, if I run the command line you suggest with tests/e4x/Regress as my directory, I don't have trouble with loading the files.  I AM, however, hitting a different crash (not overflowing the stack):

#0  0x000ab237 in js_CompareStrings (str1=0xbf8001b0, str2=0x1805240) at jsstr.c:2838
#1  0x00017225 in js_compare_atom_keys (k1=0xbf8001b4, k2=0x1805244) at jsatom.c:190
#2  0x00047da8 in JS_HashTableRawLookup (ht=0x5002e0, keyHash=120, key=0xbf8001b4) at jshash.c:179
#3  0x00018b5b in js_AtomizeString (cx=0x500170, str=0xbf8001b0, flags=128) at jsatom.c:657
#4  0x00018dd5 in js_AtomizeChars (cx=0x500170, chars=0x191b938, length=1, flags=0) at jsatom.c:755
#5  0x0009a1c2 in js_GetToken (cx=0x500170, ts=0x191b610) at jsscan.c:1247
#6  0x0009d0f7 in js_MatchToken (cx=0x500170, ts=0x191b610, tt=TOK_XMLSPACE) at jsscan.c:2166
#7  0x00087995 in XMLElementOrList (cx=0x500170, ts=0x191b610, tc=0xbfffdcac, allowList=0) at jsparse.c:3578
#8  0x0008778f in XMLElementContent (cx=0x500170, ts=0x191b610, pn=0x2b284e0, tc=0xbfffdcac) at jsparse.c:3537
#9  0x00087d52 in XMLElementOrList (cx=0x500170, ts=0x191b610, tc=0xbfffdcac, allowList=0) at jsparse.c:3637
#10 0x0008778f in XMLElementContent (cx=0x500170, ts=0x191b610, pn=0x2b28468, tc=0xbfffdcac) at jsparse.c:3537
#11 0x00087d52 in XMLElementOrList (cx=0x500170, ts=0x191b610, tc=0xbfffdcac, allowList=0) at jsparse.c:3637
#12 0x0008778f in XMLElementContent (cx=0x500170, ts=0x191b610, pn=0x2b283f0, tc=0xbfffdcac) at jsparse.c:3537
The bottom of the stack I just pasted is this:

#104701 0x00087d52 in XMLElementOrList (cx=0x500170, ts=0x191b610, tc=0xbfffdcac, allowList=0) at jsparse.c:3637
#104702 0x0008778f in XMLElementContent (cx=0x500170, ts=0x191b610, pn=0x1914060, tc=0xbfffdcac) at jsparse.c:3537
#104703 0x00087d52 in XMLElementOrList (cx=0x500170, ts=0x191b610, tc=0xbfffdcac, allowList=0) at jsparse.c:3637
#104704 0x0008778f in XMLElementContent (cx=0x500170, ts=0x191b610, pn=0x191b9e0, tc=0xbfffdcac) at jsparse.c:3537
#104705 0x00087d52 in XMLElementOrList (cx=0x500170, ts=0x191b610, tc=0xbfffdcac, allowList=1) at jsparse.c:3637
#104706 0x000881a7 in XMLElementOrListRoot (cx=0x500170, ts=0x191b610, tc=0xbfffdcac, allowList=1) at jsparse.c:3724
#104707 0x000890d2 in PrimaryExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:4061
#104708 0x000862ff in MemberExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac, allowCallSyntax=1) at jsparse.c:2931
#104709 0x00085ef3 in UnaryExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2847
#104710 0x00085773 in MulExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2696
#104711 0x00085683 in AddExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2678
#104712 0x000855cc in ShiftExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2663
#104713 0x000854a3 in RelExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2631
#104714 0x000853cc in EqExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2607
#104715 0x00085334 in BitAndExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2595
#104716 0x0008529c in BitXorExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2582
#104717 0x00085204 in BitOrExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2569
#104718 0x0008516e in AndExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2558
#104719 0x000850d8 in OrExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2547
#104720 0x00084f40 in CondExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2507
#104721 0x00084d13 in AssignExpr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2443
#104722 0x00084b85 in Expr (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2415
#104723 0x00083d82 in Statement (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:2094
#104724 0x00080fab in Statements (cx=0x500170, ts=0x191b610, tc=0xbfffdcac) at jsparse.c:1084
#104725 0x0007f8c6 in js_CompileTokenStream (cx=0x500170, chain=0x1804bc8, ts=0x191b610, cg=0xbfffdcac) at jsparse.c:472
#104726 0x0000f646 in CompileTokenStream (cx=0x500170, obj=0x1804bc8, ts=0x191b610, tempMark=0x5001b8, eofp=0x0) at jsapi.c:3606
#104727 0x0000f8c1 in JS_CompileUCScriptForPrincipals (cx=0x500170, obj=0x1804bc8, principals=0x0, chars=0x1008000, length=700001, filename=0x508691 "regress-347155.js", lineno=59) at jsapi.c:3705
#104728 0x0006aa22 in obj_eval (cx=0x500170, obj=0x1804bc8, argc=1, argv=0x181ae30, rval=0xbfffdf44) at jsobj.c:1309
#104729 0x00049d3c in js_Invoke (cx=0x500170, argc=1, flags=0) at jsinterp.c:1187
#104730 0x0005a0ee in js_Interpret (cx=0x500170, pc=0x5087f8 "y", result=0xbfffe8b0) at jsinterp.c:3606
#104731 0x0004a6d5 in js_Execute (cx=0x500170, chain=0x1804bc8, script=0x508740, down=0x0, flags=0, result=0xbffff994) at jsinterp.c:1444
#104732 0x000104e8 in JS_ExecuteScript (cx=0x500170, obj=0x1804bc8, script=0x508740, rval=0xbffff994) at jsapi.c:4024
#104733 0x00001ad5 in Process (cx=0x500170, obj=0x1804bc8, filename=0xbffffbdc "regress-347155.js") at js.c:226
#104734 0x00002490 in ProcessArgs (cx=0x500170, obj=0x1804bc8, argv=0xbffffb10, argc=4) at js.c:429
#104735 0x00006045 in main (argc=4, argv=0xbffffb10, envp=0xbffffb24) at js.c:2621
Which of course is caused by my not setting a stack-limit.

~/jscvs/js/src/Darwin_DBG.OBJ/js -S 50000 -f ../shell.js -f regress-347155.js
BUGNUMBER: 347155
STATUS: Do not crash with deeply nested e4x literal
PASSED! 1

This will be fixed on the branch as soon as I get an a+ ...
Status: REOPENED → RESOLVED
Closed: 18 years ago17 years ago
Resolution: --- → FIXED
Comment on attachment 251835 [details] [diff] [review]
moving recursion check to the right place

Approved for 1.8.0 branch, a=jay for drivers.  Thanks for the follow up on this Brendan and Brian.
Attachment #251835 - Flags: approval1.8.0.10? → approval1.8.0.10+
1_8_0:

Checking in jsparse.c;
/cvsroot/mozilla/js/src/jsparse.c,v  <--  jsparse.c
new revision: 3.142.2.6.2.13; previous revision: 3.142.2.6.2.12
done

Landed.  Apologies for the mayhem.  :)
Keywords: fixed1.8.0.10
verified fixed 1.8.0, 1.8.1, 1.9.0 2007-01-23 win/mac*/linux
Status: RESOLVED → VERIFIED
Crash Signature: [@ js_FoldConstants]
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: