226507 - [patch] No recursion check in js_EmitTree

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Igor Bukanov]

js_EmitTree from jsemit.c while calling itself recursively does not check for
allowed stack depth which deliberately constructed scripts can use to cause
stack overflow and segmentation fault.

Comment 1

[Igor Bukanov]

Attachment: Test case: deep nesting of finally

Although emitter somewhat protected against stack overflow by recursion checks
in the parser, some recursion sequences consumes more stack space then
corresponding code in the parser and still can cause stack overflow.

For example, with N in the test  set to 35, I got on my RedHat Linux 10 box a
segmentation fault from js after setting the stack limit to 100K. When I set
the stack limit to 20K I still got the segmentation fault, only after -s was
changed to 15K too deep recursion was detected:

 
~/w/js/x> ulimit -s
100
~/w/js/x> js  fintest.js 
Segmentation fault
~/w/js/x> js -S $((20*1024)) fintest.js 
Segmentation fault
~/w/js/x> js -S $((15*1024)) fintest.js 
fintest.js:19: InternalError: too much recursion


After playing with numbers it seems that while processing try/finally the
recursion in js_Emit takes 10 times more space the corresponding recursion in
the parser.

Comment 2

[Igor Bukanov]

Attachment: Fix: check for stack limit in js_Emit

With the patch I have on my box for a debug build of js:

~/w/js/x> ulimit -s
100
~/w/js/x> js -S $((90*1024)) fintest.js 
fintest.js:19: InternalError: too much recursion
~/w/js/x> js -S $((91*1024)) fintest.js 
fintest.js:19: InternalError: too much recursion
~/w/js/x> js -S $((92*1024)) fintest.js 
Segmentation fault

or for session with stack limitted to 1000K:

~/w/js/x> ulimit -s
1000
~/w/js/x> js -S $((990*1024)) fintest.js 
fintest.js:19: InternalError: too much recursion
~/w/js/x> js -S $((992*1024)) fintest.js 
Segmentation fault

which tells that on RedHat 10 K system stack consumes about 8-9 K and since
this number remains the same, there is no unaccounted recursion at least for
this test case.

Comment 3

[Igor Bukanov]

Although the patch seems to fix the problem, I am still curious what exactly
causes consumtion of over 3K of stack space in js_EmitTree per recusrion.

Comment 4

[Igor Bukanov]

The actual number is about 1500 bytes between recursive js_EmitTree invocations,
or 375 4-byte variables and it is hard to see where they come from.

Comment 5

[Mike Shaver (:shaver emeritus)]

1K of it comes from
http://lxr.mozilla.org/seamonkey/source/js/src/jsemit.c#2233.  The rest will
come from the sum of the various local declarations; gcc doesn't reuse stack
slots very well, so pretty much every local declared (whether function- or
block-scoped) will add to the total.  StmtInfos are 32 bytes a piece, and there
are two of those, etc.  Putting the intmap onto the heap or into a pool would
help a lot, I think.

Comment 6

[Igor Bukanov]

But what about then moving processing of the whole TOK_SWITCH into a separated
function? It has a few locals besides intmap_space and allocating of 1K on stack
for intmap_space does not seems to be a good idea as well.  

Comment 7

[Igor Bukanov]

Attachment: Prev patch + moving switch generation into a separated function

The patch changes stack space consumtion between recursive js_EmitTree
invocations down to 304 bytes (from about 1500).

Comment 8

[Igor Bukanov]

Even with the last patch recursion detection still happens in js_EmitTree, not
during pasing, but now N in the test increases from 31 to 148 before the test
case hits 100K barier of stack space. 

Comment 9

[Brendan Eich [:brendan]]

Can probably get this into 1.6b.

/be

Comment 10

[Brendan Eich [:brendan]]

Attachment: my version of last patch

A few nits about variables decl/init order picked, plus a comment typo fix,
plus there's no need for the ptop out param.

/be

Comment 11

[Brendan Eich [:brendan]]

Comment on attachment 136242 [details] [diff] [review]
my version of last patch

Shaver should bless this, as it's really mostly code motion plus Igor's
changes, with a few of mine.  So a third party review would be good.

/be

Comment 12

[Mike Shaver (:shaver emeritus)]

Comment on attachment 136242 [details] [diff] [review]
my version of last patch

Do the code-a-motion with meeeee!

bless=shaver

Comment 13

[Brendan Eich [:brendan]]

Comment on attachment 136242 [details] [diff] [review]
my version of last patch

This is the definition of a safe fix.  The substantive change adds a stack
overflow check that we know works uniformly (it's used in the parser and
interpreter).  The rest if taking code out of line, and cosmetics.  Risk <
epsilon.

/be

Comment 14

[Brendan Eich [:brendan]]

Attachment: left-justified, canonical brace diff of new and old EmitSwitch

showing just var decl/init reordering.

/be

Comment 15

[Brendan Eich [:brendan]]

Fixed, thanks.

/be

Comment 16

[Phil Schwartau]

Igor's testcase added to JS testsuite:

      mozilla/js/tests/js1_5/Regress/regress-226507.js

Comment 17

[Phil Schwartau]

On my WinNT4.0 box, after the fix, an optimized JS shell gives
InternalError: too much recursion if I set the stack size too low,
but a debug JS shell crashes, just as it did before the fix:


NTDLL! 77f7645c()
CheckStackGrowthDirection(int * 0x0012ee90, unsigned long 2148728632) line 1772
+ 39 bytes
JS_SetThreadStackLimit(JSContext * 0x00301c60, unsigned long 2148728632) line
1783 + 13 bytes
Process(JSContext * 0x00301c60, JSObject * 0x002fb348, char * 0x00301f28) line
331 + 14 bytes
ProcessArgs(JSContext * 0x00301c60, JSObject * 0x002fb348, char * * 0x00301ec4,
int 6) line 544 + 23 bytes
main(int 6, char * * 0x00301ec4, char * * 0x00300e70) line 2318 + 21 bytes
JS! mainCRTStartup + 227 bytes
KERNEL32! 77f1bbb5()


CRASHPOINT:

#ifdef DEBUG
static void
CheckStackGrowthDirection(int *dummy1addr, jsuword limitAddr)
{
    int dummy2;

#if JS_STACK_GROWTH_DIRECTION > 0
    JS_ASSERT(dummy1addr < &dummy2);
    JS_ASSERT((jsuword)&dummy2 < limitAddr);
#else
    /* Stack grows downward, the common case on modern architectures. */
    JS_ASSERT(&dummy2 < dummy1addr);
    JS_ASSERT(limitAddr < (jsuword)&dummy2); <<<----------------CRASHED HERE
#endif
}
#endif



Here is the exact method using the test driver's -o option to 
pass the -S option to the JS shell:

-S 10^32 PASSES (because there's enough stack ???):
perl jsDriver.pl -e smdebug -fTEST.html
-o "-S 100000000000000000000000000000000" -k -l js1_5/Regress/regress-226507.js

-S 10^31 CRASHES (in debug shell):
perl jsDriver.pl -e smdebug -fTEST.html
-o "-S 10000000000000000000000000000000"  -k -l js1_5/Regress/regress-226507.js



I have two questions:

1. Is the debug crash of any importance, or should I mark this bug verified?

2. The number 10^32 seems absurdly high, doesn't it? Does my box have 
   that much stack ???

Comment 18

[Asa Dotzler [:asa]]

Comment on attachment 136242 [details] [diff] [review]
my version of last patch

a=asa (on behalf of drivers) for checkin to 1.6beta

Comment 19

[Asa Dotzler [:asa]]

oops, sorry 'bout that belated and redundant approval. We don't yet have
collision warnings for attachment updates.

Comment 20

[Brendan Eich [:brendan]]

[~/src/trunk-opt/mozilla/js/src]$ ./t 10000000000000000000000000000000
2147483647
[~/src/trunk-opt/mozilla/js/src]$ ./t 100000000000000000000000000000000
2147483647
[~/src/trunk-opt/mozilla/js/src]$ ./t 10000000000000000000000000000000
2147483647
[~/src/trunk-opt/mozilla/js/src]$ ./t 1000000000000000000000000000000
2147483647
[~/src/trunk-opt/mozilla/js/src]$ cat t.c
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv) {
    printf("%d\n", atoi(argv[1]));
    return 0;
}

Phil: all overlarge inputs to atoi (after strtol) should result in LONG_MAX,
2147483647, being returned.

So I don't see why you get different results in the two cases you show. Can you
debug a bit, see what the return value from atoi is?

The DEBUG-only crash should be fixed, but I'd rather this bug not be reopened.
File a new one?

/be

Comment 21

[Igor Bukanov]

Phil, did you use the original test case with N set to 35 to get crash under the
debug build? I used N=35 to cause SM to hit on Linux 100K of stack consumption
without the patch. As far as I remember the default stack size on Windows is
arround 100K  so assuming that VisualC can not eliminate 1K of switch array data
and given that the test case causes 2 recursions of EmitTree per each N, 100K of
stack space can be exhausted on Windows as well without the patch.

With the patch it should be arround N * 2 * 300 = 21000 or less if VisualC can
recycle some locals and it explains success of the optimized build. To explain
the problem with the debug build, some information about stack size of debug
builds on Windows is required. Or perhaps debug builds uses 2 pages per frame =
8K to detect buffer overflows?

Try to run test case with -S set to 15000, then both builds should report too
deep recursion errors.     

Comment 22

[Phil Schwartau]

Here are the results of the test program on WinNT and Win2K:

[D:/JS_TRUNK/mozilla/js]./t 1000000000000000000000000000000       (10^30)
1073741824
[D:/JS_TRUNK/mozilla/js]./t 10000000000000000000000000000000      (10^31)
-2147483648
[D:/JS_TRUNK/mozilla/js]./t 100000000000000000000000000000000     (10^32)
0
[D:/JS_TRUNK/mozilla/js]./t 1000000000000000000000000000000000    (10^33)
0
[D:/JS_TRUNK/mozilla/js]./t 10000000000000000000000000000000000   (10^34)
0


So that explains the earlier change in behavior I noticed at 10^32.

Comment 23

[Phil Schwartau]

Results from my Win2K machine, before and after the patch.
Note the value passed to -S to avoid "too much recursion":


-------------------------- BEFORE PATCH --------------------------
 
(OPTIMIZED SHELL)
[ ] perl jsDriver.pl -e smopt -fTEST.html -o "-S 10000 "
                     -k -l js1_5/Regress/regress-226507.js
-#- Executing 1 test(s).
*-* Testcase js1_5/Regress/regress-226507.js failed:
Expected exit code 0, got 3
Testcase terminated with signal 0
Complete testcase output was:
./js1_5/Regress/regress-226507.js:151: InternalError: too much recursion:
./js1_5/Regress/regress-226507.js:151: try { f(); } finally {
./js1_5/Regress/regress-226507.js:151: ......^

-#- Wrote results to 'TEST.html'.
-#- 1 test(s) failed


[ ]perl jsDriver.pl -e smopt -fTEST.html -o "-S 11000 "
                    -k -l js1_5/Regress/regress-226507.js
-#- Executing 1 test(s).
-#- Wrote results to 'TEST.html'.
-#- 0 test(s) failed


(DEBUG SHELL)
[ ] perl jsDriver.pl -e smdebug -fTEST.html -o "-S 15000 "
-k -l js1_5/Regress/regress-226507.js
-#- Executing 1 test(s).
*-* Testcase js1_5/Regress/regress-226507.js failed:
Expected exit code 0, got 3
Testcase terminated with signal 0
Complete testcase output was:
./js1_5/Regress/regress-226507.js:119: InternalError: too much recursion

-#- Wrote results to 'TEST.html'.
-#- 1 test(s) failed


[ ] perl jsDriver.pl -e smdebug -fTEST.html -o "-S 16000 "
                     -k -l js1_5/Regress/regress-226507.js
-#- Executing 1 test(s).
-#- Wrote results to 'TEST.html'.
-#- 0 test(s) failed




-------------------------- AFTER PATCH -------------------------- 

(OPTIMIZED SHELL)
[ ] perl jsDriver.pl -e smopt -fTEST.html -o "-S 15000 "
                     -k -l js1_5/Regress/regress-226507.js
-#- Executing 1 test(s).
*-* Testcase js1_5/Regress/regress-226507.js failed:
Expected exit code 0, got 3
Testcase terminated with signal 0
Complete testcase output was:
./js1_5/Regress/regress-226507.js:119: InternalError: too much recursion

-#- Wrote results to 'TEST.html'.
-#- 1 test(s) failed


[ ] perl jsDriver.pl -e smopt -fTEST.html -o "-S 16000 "
                     -k -l js1_5/Regress/regress-226507.js
-#- Executing 1 test(s).
-#- Wrote results to 'TEST.html'.
-#- 0 test(s) failed



(DEBUG SHELL)
[ ] perl jsDriver.pl -e smdebug -fTEST.html -o "-S 32000 "
                     -k -l js1_5/Regress/regress-226507.js
-#- Executing 1 test(s).
*-* Testcase js1_5/Regress/regress-226507.js failed:
Expected exit code 0, got 3
Testcase terminated with signal 0
Complete testcase output was:
./js1_5/Regress/regress-226507.js:119: InternalError: too much recursion

-#- Wrote results to 'TEST.html'.
-#- 1 test(s) failed


[ ] perl jsDriver.pl -e smdebug -fTEST.html -o "-S 33000 "
                     -k -l js1_5/Regress/regress-226507.js
-#- Executing 1 test(s).
-#- Wrote results to 'TEST.html'.
-#- 0 test(s) failed

Comment 24

[Phil Schwartau]

                          Win2K SUMMARY

The patch has forced me to increase the amount of stacksize provided
to the JS shell in order to make the testcase pass. Here are my findings 
from above in condensed form. I am showing the rough "division point"
between the testcase failing from too much recursion, vs. passing:


-------------------------- BEFORE PATCH --------------------------
(OPTIMIZED SHELL)
-S 10000 fail
-S 11000 pass

(DEBUG SHELL)
-S 15000 fail
-S 16000 pass


-------------------------- AFTER PATCH -------------------------- 
(OPTIMIZED SHELL)
-S 15000 fail
-S 16000 pass

(DEBUG SHELL)
-S 32000 fail
-S 33000 pass


Do these results look good?

Comment 25

[Igor Bukanov]

The results are perfectly OK. 

Since recursion in the parser uses less space then recursion in the emitter,
without the check in the emitter the shell detects only maximum reached in the
parser which is less then 11000 so -S 11000 does not trigger an exception.

With the patch the additional check in the emitter will see the real stack
consumtion, that is more then 15000 so execution should trigger an exception
when -S 15000 is passed.

Notice that before the patch it was parser that complained with -S 10000 so you
see line and column in the error output:

/js1_5/Regress/regress-226507.js:151: InternalError: too much recursion:
./js1_5/Regress/regress-226507.js:151: try { f(); } finally {
./js1_5/Regress/regress-226507.js:151: ......^

After the patch it was the emitter turn to complain about stack overflow after
the parser made the tree while staying within the stack bound given by -S 15000
(no line source or column info):

./js1_5/Regress/regress-226507.js:119: InternalError: too much recursion

The same holds for the debug build.

Comment 26

[Phil Schwartau]

Igor: thank you for such a clear explanation! Marking Verified FIXED.

I filed bug 226782, "Crash in debug JS shell with certain stack sizes set",
for the issue I raised in Comment #17

Comment 27

[Bob Clary [:bc] (inactive)]

<http://test.bclary.com/tests/mozilla.org/js/js-test-driver-standards.html?test=js1_5/Regress/regress-226507.js;language=language;javascript>

Note this passes in the shell in windows/mac/linux with stack 524288 and in the browser on windows and mac but fails in linux. This failure goes back to at least 2005-12-02 on 1.8/1.9. Unfortunately I just trashed my old logs and don't have earlier results. 

Comment 28

[Bob Clary [:bc] (inactive)]

(In reply to comment #27)
to clarify, this fails in the browser on linux 1.8.*, 1.9 optimized builds only. Should I file a new bug on this, or is it just noise?

Comment 29

[Brendan Eich [:brendan]]

(In reply to comment #28)
> (In reply to comment #27)
> to clarify, this fails in the browser on linux 1.8.*, 1.9 optimized builds
> only. Should I file a new bug on this, or is it just noise?

Fails, as in crashes?  What's the stack (top 20 or so frames, at least)?

/be

Comment 30

[Bob Clary [:bc] (inactive)]

(In reply to comment #29)
fails as in does not catch the recursion error.

Comment 31

[Bob Clary [:bc] (inactive)]

attempt to catch the exception if it exists.
/cvsroot/mozilla/js/tests/js1_5/extensions/regress-226507.js,v  <--  regress-226507.js
new revision: 1.3; previous revision: 1.2