348986 - Missed recursion check in Decompile from jsopcode.c

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

Decompile from jsopcode.c is a recursive function but it does not check for a C stack overflow.

Comment 1

[Igor Bukanov]

Attachment: Fix v1

Comment 2

[Igor Bukanov]

I will try to make a test case that can show the stack overflow without hitting a stack overflow in the parser.

Comment 3

[Igor Bukanov]

Attachment: Test case for jsshell

Since the parser AFAICS consumes more stack space than the decompiler, the test case consists of 2 parts. First it builds the source of the form "function f(){function f() ..}}" and compiles it. Second it run another recursive code which at the recursion bottom calls toSource on the compiled function.

With the test case on i386 Ubuntu 6.06 after I set the stack limit to 510K and run the optimized build of jsshell assuming the deault internal stack limit for jsshell of 500000 bytes I got without the patch:

~> ulimit -s 510
...
~> ~/m/trunk/mozilla/js/src/Linux_All_OPT.OBJ/js ~/s/decompile_recursion_check.js 
Segmentation fault

With the patch:
~> ulimit -s
510
...
~> ~/m/trunk/mozilla/js/src/Linux_All_OPT.OBJ/js ~/s/decompile_recursion_check.js 
success=true

Comment 4

[Brendan Eich [:brendan]]

IIRC the parser avoids consuming linear stack space in number of chained if-then statements, while the decompiler calls itself recursively to decompile then parts. You might be able to use this asymmetry.

/be

Comment 5

[Brendan Eich [:brendan]]

Comment on attachment 234201 [details] [diff] [review]
Fix v1

r=me, thanks.

/be

Comment 6

[Mike Schroepfer]

Putting on the 1.8.1/FF2 radar...

Comment 7

[Igor Bukanov]

(In reply to comment #4)
> IIRC the parser avoids consuming linear stack space in number of chained
> if-then statements, while the decompiler calls itself recursively to decompile
> then parts. You might be able to use this asymmetry.

Here is the relevant code from Statement in jsparse.c:

Statement(JSContext *cx, JSTokenStream *ts, JSTreeContext *tc)
{
  ...
      case TOK_IF:
        /* An IF node has three kids: condition, then, and optional else. */
        pn = NewParseNode(cx, ts, PN_TERNARY, tc);
        if (!pn)
            return NULL;
        pn1 = Condition(cx, ts, tc);
        if (!pn1)
            return NULL;
        js_PushStatement(tc, &stmtInfo, STMT_IF, -1);
        pn2 = Statement(cx, ts, tc);
        if (!pn2)
            return NULL;
        if (js_MatchToken(cx, ts, TOK_ELSE)) {
            stmtInfo.type = STMT_ELSE;
            pn3 = Statement(cx, ts, tc);

I.e. it recurses exactly in the same way as Decompile does. Moreover, number of locals in both functions are on the same scale and I do not want a test case to depend on the ability of the compiler to optimize them.

Comment 8

[Bob Clary [:bc] (inactive)]

Igor, is this ready for the trunk?

Comment 9

[Bob Clary [:bc] (inactive)]

Checking in regress-348986.js;
/cvsroot/mozilla/js/tests/js1_5/Function/regress-348986.js,v  <--  regress-348986.js
initial revision: 1.1

Comment 10

[Igor Bukanov]

(In reply to comment #8)
> Igor, is this ready for the trunk?
> 
Yes, but the tinderbox is red. Or should I just consider Firefox tinderbox?

Comment 11

[Bob Clary [:bc] (inactive)]

(In reply to comment #10)

Except for balsa on seamonkey-ports, it *looks* green to me, but wait until you are ready and sure everything is ok. I'll kill my builds and wait for you to check in later.

Comment 12

[Igor Bukanov]

Attachment: Better test case

This test case deduces the stack limit automatically and prepare the sources in a such way so stack a overflow exception must be thrown.

Comment 13

[Igor Bukanov]

I committed the patch from comment 1 to the trunk.

Comment 14

[Bob Clary [:bc] (inactive)]

Checking in regress-348986.js;
/cvsroot/mozilla/js/tests/js1_5/Function/regress-348986.js,v  <--  regress-348986.js
new revision: 1.2; previous revision: 1.1
 with minor edits.

Comment 15

[Brendan Eich [:brendan]]

(In reply to comment #7)
> I.e. it recurses exactly in the same way as Decompile does. Moreover, number of
> locals in both functions are on the same scale and I do not want a test case to
> depend on the ability of the compiler to optimize them.

Argh, I was thinking of the code generator.  Sorry, have to do better next time with by-memory shooting from the hip.

/be

Comment 16

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 234201 [details] [diff] [review]
Fix v1

a=beltzner on behalf of drivers.

Comment 17

[Brendan Eich [:brendan]]

(In reply to comment #12)
> Created an attachment (id=234404) [edit]
> Better test case
> 
> This test case deduces the stack limit automatically and prepare the sources in
> a such way so stack a overflow exception must be thrown.

Clever!  The testsuite could use more of this kind of auto-sensing goodness.

/be

Comment 18

[Daniel Veditz [:dveditz]]

Comment on attachment 234201 [details] [diff] [review]
Fix v1

approved for 1.8.0 branch, a=dveditz for drivers

Comment 19

[Igor Bukanov]

I committed the patch from comment 1 to MOZILLA_1_8_BRANCH

Comment 20

[Igor Bukanov]

Attachment: Fix for 1.8.0 branch

The version for 1.8.0 branch that removes 3 junk trailing white spaces to stay close to post 1.8.0 versions.

Comment 21

[Daniel Veditz [:dveditz]]

Comment on attachment 234516 [details] [diff] [review]
Fix for 1.8.0 branch

a=dveditz

Comment 22

[Igor Bukanov]

I committed the patch from comment 20 to MOZILLA_1_8_0_BRANCH

Comment 23

[Bob Clary [:bc] (inactive)]

verified fixed 1.8, 1.9 20060821 windows/mac*/linux

Comment 24

[Bob Clary [:bc] (inactive)]

verified fixed 1.8.0.7 20060824 windows/mac*/linux no crash
JavaScript Error: ./js1_5/Function/regress-348986.js:64: too much recursion.