Bug 26276 – Need a mechanism to determine stack extent on Windows, SOLARIS, OPENBSD, HAIKU platforms

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Oliver Hunt]

There are many places where we have arbitrary (and conservative) recursion count based limits.  A better approach would be to have a guard based on the actual extent of the stack.

[Xan Lopez]

(In reply to comment #0)
> There are many places where we have arbitrary (and conservative) recursion count based limits.  A better approach would be to have a guard based on the actual extent of the stack.

Would the limit based on the stack extent by also arbitrary, or is there a way to get reasonable values, say, per platform?

[Oliver Hunt]

(In reply to comment #1)
> (In reply to comment #0)
> > There are many places where we have arbitrary (and conservative) recursion count based limits.  A better approach would be to have a guard based on the actual extent of the stack.
> 
> Would the limit based on the stack extent by also arbitrary, or is there a way to get reasonable values, say, per platform?

There doesn't seem to be any reliable way to get the thread stack size on *nix at least -- it's dependent on the attribute being set through pthreads, and i'm not sure if the attribute is required to correlate  to reality.

In the new parser I took a different approach and simply put a size limit by subtracting 512k (or something) from the first time we enter the parser on a given thread -- this assumes that the very first time we parse something we aren't already using too much stack space.  It also causes problems on platforms that have very low stack sizes :-/

[Xan Lopez]

(In reply to comment #2)
> In the new parser I took a different approach and simply put a size limit by subtracting 512k (or something) from the first time we enter the parser on a given thread -- this assumes that the very first time we parse something we aren't already using too much stack space.  It also causes problems on platforms that have very low stack sizes :-/

(... after reading that code ...)

I see.

So I assume that even if it's less than perfect this is still better than the mechanisms used in, say, Interpreter.cpp?

BTW, just for fun I added an ASSERT in JSParser.cpp::canRecurse(), like


         char sample = 0;
         ASSERT(m_endAddress);
+        ASSERT(&sample > m_endAddress);
         return &sample > m_endAddress;

and, if I'm not messing up, it does not seem to be triggered even once running LayoutTests/fast/js or the JSC tests. Do we have any reasonable test for the stack overflow business? :)

[Oliver Hunt]

> BTW, just for fun I added an ASSERT in JSParser.cpp::canRecurse(), like
> 
> 
>          char sample = 0;
>          ASSERT(m_endAddress);
> +        ASSERT(&sample > m_endAddress);
>          return &sample > m_endAddress;
> 
> and, if I'm not messing up, it does not seem to be triggered even once running LayoutTests/fast/js or the JSC tests. Do we have any reasonable test for the stack overflow business? :)

Seems like we could have some tests for that, file a bug on it and land a large number of tests for "recursive" bits of the grammar.

heavily nested functions, ()'s, etc should all eventually trigger this... (i'm sure i made tests for this though :-/)

[Xan Lopez]

Created attachment 66474 [details]
interpreteroverflow.diff

First crack at this.

I'm using the same idiom that JSParser uses. I copied the value to calculate an end address from there, since I'm unsure of whether we want to share it or not. If we do, we should probably have it in some header (where?), if we want a different value here we just need to change it.

WRT tests, there's actually a few tests that check for stack overflow in parsing, execution, ...(eg, js1_5/Regress/regress-192414.js, js1_5/Regress/regress-192465.js ), but we could write more if you think our coverage is not enough. In any case, no regressions here with this patch.

[Xan Lopez]

btw, I didn't remove m_reentryDepth because its value is still used in one place inside ::execute:

    if (m_reentryDepth && lastGlobalObject && globalObject != lastGlobalObject)
        lastGlobalObject->copyGlobalsTo(m_registerFile);

[Xan Lopez]

Ping?

[Eric Seidel (no email)]

CCing some JSC folks will help get a review. :)

[Gavin Barraclough]

Created attachment 76981 [details]
The patch

Does not fix the problem (Need a mechanism to determine stack extent), but gives us a common place (StackBounds) to do so.

[WebKit Review Bot]

Attachment 76981 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/7268058

[Gavin Barraclough]

Comment on attachment 66474 [details]
interpreteroverflow.diff

Hey xan,

Out of coincidence I've hit a similar issue, I need to improve the bytecompiler's recursion guards.  As such I think we could do with some more of this code in a common place, where it can be shared.

I'm going to give this an r- for now, since I think this change can be much simpler when my patch lands – you can basically just call globalData->stack().recursionCheck().  However I think in making this change we should also address one question slightly more thoroughly – how much machine stack space so we need to nest iterations of the VM? (the new recursionCheck() method defaults to checking that 4k of stack is available, but a different limit can be specified, and nesting entries into Interpreter::execute might take more than this – with the interpreter enabled the frame size for privateExecute is large).

I'd suggest we should perform a couple of quick empirical tests to set a sensible value for the minimum amount of space to require upon entry into Interpreter::execute.  We could write some test code that causes nested entries into JIT code & into private execute (we should test with the interpreter too), and measure the difference in the stack position at these points.  This may give us some guide as the to depth of stack space needed, but I guess this may be flawed – this may not be representative of a use case that uses the most stack space.

A better experiment might be to write a tool to dump the processes vm map on exit, run some test cases, and look at how much of the stack has been mapped in resident (we could do this on OS X using vmmap) - this would be harder, but would give us a better indication of common stack usage in JSC.  Maybe there is an easier way to produce similar information.

What do you think? - do you think you can come up with some form of test to pick a sensible amount of stack space to require to permit reentry?  If not, I suggest we at least hard code a constant to demand a more significant chunk of stack space be available to permit reentry, say, passing 16k/32k to recursionCheck().

cheers,
G.

[Gavin Barraclough]

Ooops, will add added files to other makefiles in the morning.

[Build Bot]

Attachment 76981 [details] did not build on win:
Build output: http://queues.webkit.org/results/7295064

[Early Warning System Bot]

Attachment 76981 [details] did not build on qt:
Build output: http://queues.webkit.org/results/7236080

[WebKit Review Bot]

Attachment 76981 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/7309067

[Xan Lopez]

(In reply to comment #11)
> A better experiment might be to write a tool to dump the processes vm map on exit, run some test cases, and look at how much of the stack has been mapped in resident (we could do this on OS X using vmmap) - this would be harder, but would give us a better indication of common stack usage in JSC.  Maybe there is an easier way to produce similar information.

It seems reasonably easy to dump the process vm map on exit and check how much of the stack has been mapped in resident, although not in a portable way. I can hack jsc or whatever to add an option to do this in Linux, if you want, and then you can fill in the OSX bits.

> 
> What do you think? - do you think you can come up with some form of test to pick a sensible amount of stack space to require to permit reentry?  If not, I suggest we at least hard code a constant to demand a more significant chunk of stack space be available to permit reentry, say, passing 16k/32k to recursionCheck().

My only question is what set of programs would we run to figure out what's a reasonable limit.
 
> 
> cheers,
> G.

[Gavin Barraclough]

Created attachment 77027 [details]
The patch (fix makefiles)

[Gavin Barraclough]

Created attachment 77028 [details]
The patch (ooops, fix fwding headers)

[Gavin Barraclough]

Created attachment 77029 [details]
Gah, fix StackBounds.h, too.

[WebKit Review Bot]

Attachment 77029 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/7258068

[Oliver Hunt]

Comment on attachment 77029 [details]
Gah, fix StackBounds.h, too.

View in context: https://bugs.webkit.org/attachment.cgi?id=77029&action=review

There should be a follow on bug to separate JavaScriptCore/wtf/StackBounds.cpp into platform specific files.

> JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj:-2460
> -			developmentRegion = English;

Please to be updating your copy of xcode.

[Early Warning System Bot]

Attachment 77029 [details] did not build on qt:
Build output: http://queues.webkit.org/results/7309077

[Gavin Barraclough]

StackBounds landed in r74360.

[Gavin Barraclough]

Hey xan,

Hmmm, sure, I'm beginning to question my own suggestion here.  There is a problem with the vm map based approach, in that it will measure the stack depth used by the lexer/parser & byte compiler.  We don't want to include these, since they check stack usage themselves.

So maybe we should just measure the depth from vm entry  to vm entry (write a test case to call a host function, say, array sort, that can call back out to a JS function, and measure difference in stack depth between the two entries).

> My only question is what set of programs would we run to figure out what's a reasonable limit.

If we're going to take this approach, then you just need to write a test that will cause a nested entry into JS language code.  We should measure with & without the JIT, since we believe Interpreter::privateExecute to have a huge callframe.

It would be better to find a way to measure the deepest route through the VM, but I can't think of a good way to do so, without including the parser/bytecompiler stack depth.  If you have any bright ideas here, my suggestion would be run the fast/js LayoutTests & javascriptcore-tests – in order to find the longest route through the VM we need to try different routes through the VM, and this will give us good coverage.

But maybe we should just stick to the simpler suggestion.  Any empirical test will be better than what we currently have, which is a wild guess! :-)

cheers,
G.

[Tony Gentilcore]

I think this may have broken the chromium mac compile:

CompileC ../../WebKit/chromium/xcodebuild/JavaScriptCore.build/Release/wtf.build/Objects-normal/i386/StackBounds.o /Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp/../wtf/StackBounds.cpp normal i386 c++ com.apple.compilers.gcc.4_2
    cd /Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp
    /Developer/usr/bin/gcc-4.2 -x c++ -arch i386 -fmessage-length=0 -pipe -Wno-trigraphs -fno-exceptions -fno-rtti -O3 -Wnewline-eof -DCHROMIUM_BUILD -DENABLE_REMOTING=1 -DENABLE_GPU=1 -DENABLE_3D_CANVAS=1 -DENABLE_3D_RENDERING=1 -DENABLE_ACCELERATED_2D_CANVAS=1 -DENABLE_BLOB=1 -DENABLE_BLOB_SLICE=1 -DENABLE_CHANNEL_MESSAGING=1 -DENABLE_CLIENT_BASED_GEOLOCATION=1 -DENABLE_DASHBOARD_SUPPORT=0 -DENABLE_DATABASE=1 -DENABLE_DATAGRID=0 -DENABLE_DEVICE_ORIENTATION=1 -DENABLE_DIRECTORY_UPLOAD=1 -DENABLE_DOM_STORAGE=1 -DENABLE_EVENTSOURCE=1 -DENABLE_FILE_SYSTEM=1 -DENABLE_FILTERS=1 -DENABLE_GEOLOCATION=1 -DENABLE_ICONDATABASE=0 -DENABLE_INDEXED_DATABASE=1 -DENABLE_INPUT_SPEECH=1 -DENABLE_JAVASCRIPT_DEBUGGER=1 -DENABLE_JSC_MULTIPLE_THREADS=0 -DENABLE_LINK_PREFETCH=1 -DENABLE_MATHML=0 -DENABLE_METER_TAG=1 -DENABLE_NOTIFICATIONS=1 -DENABLE_OFFLINE_WEB_APPLICATIONS=1 -DENABLE_OPENTYPE_SANITIZER=1 -DENABLE_ORIENTATION_EVENTS=0 -DENABLE_PROGRESS_TAG=1 -DENABLE_SHARED_WORKERS=1 -DENABLE_SVG=1 -DENABLE_SVG_ANIMATION=1 -DENABLE_SVG_AS_IMAGE=1 -DENABLE_SVG_FONTS=1 -DENABLE_SVG_FOREIGN_OBJECT=1 -DENABLE_SVG_USE=1 -DENABLE_TOUCH_EVENTS=1 -DENABLE_V8_SCRIPT_DEBUG_SERVER=1 -DENABLE_VIDEO=1 -DENABLE_WEB_AUDIO=0 -DENABLE_WEB_SOCKETS=1 -DENABLE_WEB_TIMING=1 -DENABLE_WORKERS=1 -DENABLE_XHR_RESPONSE_BLOB=1 -DENABLE_XPATH=1 -DENABLE_XSLT=1 -DWTF_USE_ACCELERATED_COMPOSITING=1 -DWTF_USE_WEBP=1 -DWTF_USE_WEBKIT_IMAGE_DECODERS=1 -DBUILDING_CHROMIUM__=1 -DUSE_SYSTEM_MALLOC=1 -DWTF_USE_NEW_THEME=1 -DNDEBUG -DNVALGRIND -DDYNAMIC_ANNOTATIONS_ENABLED=0 -isysroot /Developer/SDKs/MacOSX10.5.sdk -fvisibility=hidden -fvisibility-inlines-hidden -fno-threadsafe-statics -mmacosx-version-min=10.5 -gdwarf-2 -Wendif-labels -Wno-unused-parameter -Wno-missing-field-initializers -F/Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp/../../WebKit/chromium/xcodebuild/Release -I/Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp/../../WebKit/chromium/xcodebuild/Release/include -I../../WebKit/chromium/third_party/icu/public/common -I../../WebKit/chromium/third_party/icu/public/i18n -I.. -I../wtf -I../wtf/unicode -I/Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp/../../WebKit/chromium/xcodebuild/JavaScriptCore.build/Release/wtf.build/DerivedSources -c /Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp/../wtf/StackBounds.cpp -o /Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp/../../WebKit/chromium/xcodebuild/JavaScriptCore.build/Release/wtf.build/Objects-normal/i386/StackBounds.o
/Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp/../wtf/StackBounds.cpp: In member function ‘void WTF::StackBounds::initialize()’:
/Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp/../wtf/StackBounds.cpp:72: error: ‘pthread_t’ was not declared in this scope
/Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp/../wtf/StackBounds.cpp:72: error: expected `;' before ‘thread’
/Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp/../wtf/StackBounds.cpp:73: error: ‘thread’ was not declared in this scope
/Users/cltbld/Desktop/BuildSlaveData/WebKit-BuildSlave/chromium-mac-release/build/JavaScriptCore/JavaScriptCore.gyp/../wtf/StackBounds.cpp:73: error: ‘pthread_get_stackaddr_np’ was not declared in this scope

[Tony Gentilcore]

(In reply to comment #25)
> I think this may have broken the chromium mac compile:

Patch for chromium mac compile: https://bugs.webkit.org/show_bug.cgi?id=51356

[Gavin Barraclough]

xan - fyi https://bugs.webkit.org/show_bug.cgi?id=51358.

[Gavin Barraclough]

Created attachment 77059 [details]
Fix stack size detection on DARWIN, WINDOWS, QNX, UNIX

Still needs fixes for SOLARIS, OPENBSD, SYMBIAN, HAIKU, WINCE, these can follow on after this change.

[Oliver Hunt]

Comment on attachment 77059 [details]
Fix stack size detection on DARWIN, WINDOWS, QNX, UNIX

r=me

[Gavin Barraclough]

Fixed in r74402 for DARWIN, WINDOWS, QNX, UNIX.
Leaving bug open to track SOLARIS, OPENBSD, SYMBIAN, HAIKU, WINCE.
Updating bug title to reflect this.

[Eric Seidel (no email)]

Attachment 77059 [details] was posted by a committer and has review+, assigning to Gavin Barraclough for commit.

[Gavin Barraclough]

(In reply to comment #31)
> Attachment 77059 [details] was posted by a committer and has review+, assigning to Gavin Barraclough for commit.

Hi eric, 77059 is already committed in r74402, per comment #30.

I'm not sure that setting an assignee is apt for this particular bug, since both xan and I are working on different aspects of the problem.  I'm going to reset assignee, since I'm expecting the next patches to come from xan - I hope this seems reasonable.

cheers,
G.

[Gavin Barraclough]

Relanded in r74455, minus Windows support, since this broke Windows 7.
Unclear why StackLimit is not our friend on this platform.  Will explore.

[Ryosuke Niwa]

http://build.webkit.org/changes/24047 seems to have caused a persistent test failure on Leopard bots:

http://build.webkit.org/results/Leopard%20Intel%20Release%20(Tests)/r74460%20(25800)/results.html
http://build.webkit.org/results/Leopard%20Intel%20Release%20(Tests)/r74461%20(25801)/results.html

[Gavin Barraclough]

The crash in inspector/console-log-before-inspector-open.html is unexpected, I'll investigate.

I'll get some platform specific expected results checked in for fast/js/large-expressions.html - looks like we're going to have different results here now due to different stack sizes running on 32/64 bit platforms.

[Patrick R. Gansterer]

Created attachment 77721 [details]
Patch for WinCE

This needs bug 51778.

[WebKit Review Bot]

Attachment 77721 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'JavaScriptCore/ChangeLog', u'JavaScriptCore/wtf/StackBounds.cpp']" exit_code: 1
JavaScriptCore/wtf/StackBounds.cpp:68:  One or more unexpected \r (^M) found; better to use only a \n  [whitespace/carriage_return] [1]
Suppressing further [whitespace/carriage_return] reports for this file.
Total errors found: 35 in 2 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Gavin Barraclough]

Comment on attachment 77721 [details]
Patch for WinCE

Hi Patrick, patch looks great, but r- for the style-bot issues.  Please resubmit without '\r's & I'll be happy to r+.
cheers, G.

[Patrick R. Gansterer]

Created attachment 77776 [details]
Patch for WinCE (fixed line endings)

[Patrick R. Gansterer]

Comment on attachment 77721 [details]
Patch for WinCE

(In reply to comment #38)
> (From update of attachment 77721 [details])
> Hi Patrick, patch looks great, but r- for the style-bot issues.  Please resubmit without '\r's & I'll be happy to r+.
> cheers, G.
Ok, now I know the problem: StackBounds.cpp has _no_ svn:eol-style=natvie _and_ CRLF (That's the reason why the second patch does not apply!).
If you r+ I'll commit it manually and add the svn:eol-style property.

[James Robinson]

It looks like this code is specific to JavaScriptCore, is there any reason the code in WTFThreadData was added outside the #if USE(JSC) guards?  This causes a few uesless pthread_* calls on ports that don't use JSC currently.

[James Robinson]

(In reply to comment #41)
> It looks like this code is specific to JavaScriptCore, is there any reason the code in WTFThreadData was added outside the #if USE(JSC) guards?  This causes a few uesless pthread_* calls on ports that don't use JSC currently.

https://bugs.webkit.org/show_bug.cgi?id=51881

[Patrick R. Gansterer]

Created attachment 78133 [details]
Patch for WinCE (with detectGrowingDownward)

Can you please r+ this patch?
It only added the required detectGrowingDownward function.

Diff to the already reviewed patch:

+static bool detectGrowingDownward(void* previousFrame)
+{
+    // Find the address of this stack frame by taking the address of a local variable.
+    int thisFrame;
+    return previousFrame > &thisFrame;
+}
+

[WebKit Review Bot]

Attachment 78133 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source/JavaScriptCore/wtf/StackBounds.cpp']" exit_code: 1
Source/JavaScriptCore/wtf/StackBounds.cpp:68:  One or more unexpected \r (^M) found; better to use only a \n  [whitespace/carriage_return] [1]
Suppressing further [whitespace/carriage_return] reports for this file.
Total errors found: 42 in 2 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[WebKit Review Bot]

http://trac.webkit.org/changeset/75180 might have broken Chromium Mac Release

[Patrick R. Gansterer]

Comment on attachment 78133 [details]
Patch for WinCE (with detectGrowingDownward)

Clearing flags on attachment: 78133

Manually committed r75180: <http://trac.webkit.org/changeset/75180>

[Gavin Barraclough]

Created attachment 78272 [details]
Fix for win32.

[WebKit Review Bot]

Attachment 78272 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source/JavaScriptCore/wtf/StackBounds.cpp']" exit_code: 1
Source/JavaScriptCore/wtf/StackBounds.cpp:33:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 1 in 2 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Geoffrey Garen]

Comment on attachment 78272 [details]
Fix for win32.

View in context: https://bugs.webkit.org/attachment.cgi?id=78272&action=review

> Source/JavaScriptCore/wtf/StackBounds.cpp:33
> +#include <stdio.h>

Alphabetical sort, please.

[Gavin Barraclough]

(In reply to comment #49)
> (From update of attachment 78272 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=78272&action=review
> 
> > Source/JavaScriptCore/wtf/StackBounds.cpp:33
> > +#include <stdio.h>
> 
> Alphabetical sort, please.

Oops! - better still, include removed!
Fixed for win32 in r75289.

[Adam Roben (:aroben)]

Comment on attachment 78272 [details]
Fix for win32.

I rolled this out in r75405. See bug 52156.

[Siddharth Mathur]

Symbian fixed in Bug 52842. Updating title.

[Eric Seidel (no email)]

Comment on attachment 77721 [details]
Patch for WinCE

Cleared Gavin Barraclough's review+ from obsolete attachment 77721 [details] so that this bug does not appear in http://webkit.org/pending-commit.

[Eric Seidel (no email)]

Attachment 78272 [details] was posted by a committer and has review+, assigning to Gavin Barraclough for commit.

[Gavin Barraclough]

Comment on attachment 78272 [details]
Fix for win32.

Clearing all review flags; 78272 was landed but rolled out.

[Gavin Barraclough]

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

[Gavin Barraclough]

Updating title to reflect windows patch having been rolled out.

[Gavin Barraclough]

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