96128 - stack overflow crash with infinite recursion

Status: RESOLVED DUPLICATE of bug 220408

(Core :: JavaScript Engine, defect)

Description

[John Bandhauer]

The JS infinite recursion protection is built into the bytecode interpreter 
loop is not catching some cases. See: 
http://lxr.mozilla.org/seamonkey/ident?i=MAX_INTERP_LEVEL

On NT4 the simple code...

  function T(){return new T();}; T() 

...causes a stack overflow crash in debug builds of both the browser and the 
shell. In the release builds this is safely caught by the "too much recursion" 
mechanism. If I remove the 'new' from the code above this is safely caught in 
both debug and release builds. The 'new' causes a lookup for the Constructor 
name and seems to (at least) double the number of items on the C stack for the 
given interpLevel depth.

I suspect we are simply running afoul of the number chosen for the hard limit 
here and should lower the #define'd value of MAX_INTERP_LEVEL. I'm not clear on 
exactly what cases the inline call stuff is kicked in, so I don't know if 
MAX_INLINE_CALL_COUNT is at issue also.

Changing MAX_INTERP_LEVEL to 250 makes it not crash for me. (Changing it to 500 
did not fix the crash). Such a change may simply be a bandaid; there may be a 
more appropriate fix.

Comment 1

[Brendan Eich [:brendan]]

Ick.  This number might have to be tuned for different OSes, or even for
different versions of the same OS!  Perhaps we should just reduce (if not
eliminate) interpreter recursion, _a la_ the inline_call: stuff.

/be

Comment 2

[Phil Schwartau]

Reassigning to khanson - 

Comment 3

[Phil Schwartau]

jband's testcase added to JS test suite:

          mozilla/js/tests/js1_5/Regress/regress-96128-n.js


On WinNT, I experience what jband saw: the debug JS shell crashes,
but the optimized JS shell gracefully errors with exit code 3 and
this message:

          InternalError: too much recursion


On Linux, I am getting the graceful error in both the debug and
optimized JS shells...

Comment 4

[Kenton Hanson (gone)]

targeting for 9.9.

Comment 5

[Kenton Hanson (gone)]

Attachment: Proposed patch

Sets the MAX_INTERP_LEVEL to 320.  For the Mac the level is also screened for a
low stack space dynamically using a call to StackSpace ().  For the test case
above, the Mac halts at a level of 99.	It would be very useful to find a
function like StackSpace () for the non Mac version.

Comment 6

[Brendan Eich [:brendan]]

Is 16K based on anything, or just a SWAG?  It seems big for a "red zone", but I
don't know what else to use -- my gut would favor 8K.  Can we measure, perhaps
disassemble compiled to see frame sizes by finding stack pointer adjustment code?

/be

Comment 7

[Kenton Hanson (gone)]

I tried 10k and it crashed.  It is the value used by a similar code snippet in
jsregexp.c.

Comment 8

[Brendan Eich [:brendan]]

Oh, I hadn't seen that jsregexp.c code.  Rogerl, how'd you come up with that
magic 16K?  Should we enshrine it with a common macro so khanson can use it in
jsinterp.c?

/be

Comment 9

[John Bandhauer]

I know of no StackSize equiv for Win32 or Linux. There is an article about Win32
stacks at:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dllproc/prothred_0b8l.asp

The normal way to deal with this sort of problem on Win32 is reactive rather
than proactive: wrap the doubtful code with a structured exception handler and
handle the case where the system was unable to give you more stack space. *How*
you go about handling it and what state things are left in is a messy problem
though.

It appears that a Win32 version of StackSize would not be hard to write. The
Platform SDK has headers for NT_TIB (thread info block) which has members:
StackBase and StackLimit. Apparently this block is always pointed to by an
offset from the FS register. Of course the current stack pointer is always in a
register. I *assume* that the limit it refers to is the *reserved* memory limit.
So, it is possible that actually committing stack memory might fail before the
limit is reached. I don't know if these things are identical across Win32
platforms (e.g. Win95 v. Win200 etc).

Again, if it *really* makes sense to try to adaptively cope with stack overflow
in the js interp loop for Win32 then appropriately placed structured exception
handling may be worth investigating.

On the issue of the choice of magic numbers... I would expect less per function
stack use in a release build... We should not limit the release builds with 'red
zones' sized for debug builds. Do we have a reasonable way to estimate limiting
stack requirements at the interp loop level? Or is it 'OK' to just try it with
some arbitrary bit of nesting code?

Comment 10

[Kenton Hanson (gone)]

I will try to determine the correct size of the red zone in various
environments.  Note, it should be large enough to provide the stack and heap
necessary for a graceful exit.

Comment 11

[Phil Schwartau]

*** Bug 157434 has been marked as a duplicate of this bug. ***

Comment 12

[rogerl (gone)]

(Sorry - on vacation, so not checking email very often).
The stack sniffing code came from Beard & Waldemar. I'm not sure, but I think 
the 16K is the default stack size given to a Mac application by the Finder (back 
in the good old days). The (candidate) new engine doesn't use the same code 
since it doesn't recurse on the stack, but macro-fying the code snippet seems 
like a handy thing to do for the major recursion sensitive passes.

Comment 13

[Igor Bukanov]

I reported a similar bugs unchecked stack overflow during recursion in parser,
regexp parser and toSource implementation: see bug 192414 and bug 192465.

It seems having StackSize available would be a proper remedy for this.

Comment 14

[Brendan Eich [:brendan]]

Igor, sorry this dropped off my radar.  Can it wait till 1.6alpha?

/be

Comment 15

[Igor Bukanov]

Attachment: Using StackSpace on Mac when setting default stack size limit in js_NewContext

Perhaps it makes sence to use SpaceSize on Mac when limitting maximal  stack
consumption instead of compilation-time limit set by
JS_DEFAULT_STACK_SIZE_LIMIT?

This is completely untested since I do not have access to any MAC.

Comment 16

[Simon Fraser [no longer active]]

I don't know that StackSpace() returns anything useful in Mach-O. It might not.
Can we measure stack depth by referring to the address of some variable on the
stack in the frame for a non-recursing function?

Comment 17

[Brendan Eich [:brendan]]

This is now a dup of bug 220408.

/be

*** This bug has been marked as a duplicate of 220408 ***