420869 - Script stack space in Firefox 3.0b4pre much smaller than it was in Firefox 2.0.0.12

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Michael Kraft [:morac]]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9b4pre) Gecko/2008030305 Minefield/3.0b4pre
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9b4pre) Gecko/2008030305 Minefield/3.0b4pre

I found that one of my extensions was occasionally generating "script stack space is exhausted" errors in the Firefox 3.0 betas, where it ran fine in Firefox 2.0.0.12.

I tracked this down to the fact that Firefox 2.0.0.12 appears to limit the stack space to available memory, while Firefox 3.0 limits it to around 620,000.   Firefox 2.0.0.12 can handle values 4 times as great as that.  Because my code handles very large strings, I ended up having to put a work around to handle this.

I put together an example based on code that was in my extension.

Reproducible: Always

Steps to Reproduce:
1. Try to run a javascript test function against a string of 640,000 characters in length where the RegExp generated is of that length.

Actual Results:  
Throws an exception.

Expected Results:  
Firefox 2.0.0.12 won't throw an exception on a string of that length so I would expect Firefox 3.0 to handle it as well.

I don't know if this is technically a bug or a side effect of the new memory management functionality in Firefox 3.0.  If it's the later, the new limit seems kind of low.

Comment 1

[Michael Kraft [:morac]]

Attachment: Test case

Running this test case in Firefox 2.0.0.12 results in no errors.  If I bump of the char limit to about 4,000,000 Firefox 2.0.0.12 will generate an out of memory error, but it can easily handle the 2,000,000 limit currently specified.  Firefox 3.0b4pre cannot.

Comment 2

[Michael Kraft [:morac]]

Someone filed my bug and test case under Bug 420874.  One should be duped to the other.

Comment 4

[Brendan Eich [:brendan]]

Igor, can you take this one? Thanks,

/be

Comment 5

[Igor Bukanov]

(In reply to comment #4)
> Igor, can you take this one? Thanks,

right, this a matter of bumping the script stack quota. When implementing quota support, I set JS_DEFAULT_SCRIPT_STACK_QUOTA to 2**25 (32MB) just to make sure the tests for jsshell does not regress. I guess the real web requires bigger number.

Comment 6

[Bob Clary [:bc] (inactive)]

Attachment: known stack space errors

I should have whined about these before. I just _ass_umed it was intended. Sorry.

Comment 7

[Brendan Eich [:brendan]]

Does the patch fix those tests, and the addon authors' reported cases? I'm only a little worried there's a bug that leaks quota space or otherwise makes the error fire too soon.

/be

Comment 8

[Michael Kraft [:morac]]

(In reply to comment #5)
> I guess the real web requires bigger number.

To be fair, my extension was doing some rather extreme RegExp matching which could result in matches way over 32 MB.  I would think in normal usage this would not occur.  I've since re-written my code to not generate large RegExp results.

My main issue was that what was working under Firefox 2.0.0.12, didn't work under Firefox 3.0 so if bumping the quota size up doesn't hurt anything, I think it should be done.

Comment 9

[Chris]

Attachment: Real World Example

Note that I tested this (accidentally, came here when googling the error) on
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9b3) Gecko/2008021416 Firefox/3.0b3
which I installed through Ubuntu's repositories.

It's probably not worth looking at my attachment (don't... I suck at javascript, this is my first real step into it and I was coding for fun as a toy so it's real sloppy)

I was playing around thinking about a simple library for an uncommon and new kind of encryption for private use on a local area network. As I said I'm not very good with javascript so excuse my sloppy code, it's full of comments so should be very readable.

I had just made a simple substitution cipher with some nice prospects for expandability/upgradability (some array manipulations and salting) and POW the page came up blank. Error console complained loudly...
"Error: script stack space quota is exhausted"


Anyway my life story's not important of course and I'm sure my attachment doesn't help but it's a real-world example of a user hitting this limit.

I know we're supposed to only submit patches and test cases but hey, it can't hurt I hope.

Thanks, guys.

Comment 10

[Alexander Svyazin]

Online task manager www.rememberthemilk.com doesn't show my task list in Firefox 3.0 :( and error console shows this "stack space quota" message

It works in Firefox 2 and other browsers (Opera, Safari) though

Comment 11

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

This should block b5 -- we need beta exposure to see if we need to loosen again.

Comment 12

[Igor Bukanov]

(In reply to comment #9)
> Created an attachment (id=308103) [details]
> Real World Example

The example contains:

String.prototype.exchange = function(){
...
}

...
String.prototype.exchange = function(){
//swap the symbol tables
var $in2 = $in;
$in = $out;
$out = $in2;
var $unexchanged = this.exchange();
...
}


This triggers infinite recursion through the "exchange" function. The JS engine correctly throws an exception when this happens. 

Comment 13

[Igor Bukanov]

(In reply to comment #1)
> Created an attachment (id=307232) [details]
> Test case
> 
> Running this test case in Firefox 2.0.0.12 results in no errors.  If I bump of
> the char limit to about 4,000,000 Firefox 2.0.0.12 will generate an out of
> memory error, but it can easily handle the 2,000,000 limit currently specified.
>  Firefox 3.0b4pre cannot.

To handle the test case the script quota must grow from the current 32 MB to 300MB or so. This makes the infinite recursion detection rather slow. For example, with the limit set to 300MB under Linux with my 1/.1 GHz Pentium-M laptop I have for a thread-safe build of JS shell:

~/m/ff/mozilla/js/src $ time ./Linux_All_OPT.OBJ/js -e 'function f(i) {if (i == 0) return 1; return i*f(i-1);}; f()'
-e:1: InternalError: script stack space quota is exhausted
1.646 secs

Still I think the pause of 1-2 seconds is not that bad since for while (true) {}  it will be 10 seconds.

Comment 14

[Igor Bukanov]

Attachment: v1

The fix uses JS_SetScriptStackQuota to bump the quota to 300MB.

Comment 15

[Michael Kraft [:morac]]

Well I arbitrarily picked 2,000,000 bytes in my test case since it was a nice round number.  If you think that's too high you could lower it to 1,500,000 or 1,000,000, which would lower the script quota and make detection faster.  With a 32 MB quota, my test case failed at around 640 KB which is a lot less than 2 MB.

Personally though I don't think a wait of <2 seconds is too bad if that's what it would be.

I typed "function f(i) {if (i ==0) return 1; return i*f(i-1);}; f()" into the error console in Firefox 3.0.2008031705 running on a Pentium 4 3 GHz PC running Windows XP SP2 and it took about 2 seconds to return the stack space quota exhausted error.  If this is with the 32 MB limit, then I'm assuming it will take longer with the 300 MB limit.

Comment 16

[Brendan Eich [:brendan]]

300MB is too big, my gut says. Something between 64M and 128M?

/be

Comment 17

[Igor Bukanov]

(In reply to comment #16)
> 300MB is too big, my gut says. Something between 64M and 128M?

Any number that is not backed up by some measurements is unsound. 300MB makes a particular test case that fails now working again as it was in FF2. Since a script can allocate more than 300MB using GC-things, the new limit does not add new denial-of-service vectors. Thus the issue is whether the limit affects the usability of infinite recursion detection. I will test this in a browser.

Comment 18

[Brendan Eich [:brendan]]

Tuning the quota for one benchmark on one machine running one OS seems not too sound, but I'm not throwing stones. However I'm missing something: we used to have a 500K or so thread-stack limit and a 1000 inline call limit, IIRC. How does the latter equate to 300M of inline call stack space? The numbers don't add up, or I am missing something big.

/be

Comment 19

[Igor Bukanov]

Attachment: timing measurements for infinite recursion detection

Here is the number I got with the test when the script stack quota is set to different sizes. This is for a browser build under Fedora-8 on 1.1 GHz Pentium-M notebook.

quota, MB   time, s
32          1.874
64          6.768
96          14.662
128         24.186
256         90.388

This tells that setting the limit to 300MB clearly affects the usability. As such I suggest to set the limit to, say, 100MB. If this will still affect the real-world examples, then an artificial restriction on the number of JS frames should be reintroduced. 

This also points out that making regexp to consume less memory in pathological cases will allow to decrease the quota.

Comment 20

[Michael Kraft [:morac]]

A 1.1 GHz Pentium-M is about on par with a 2.2 GHz Pentium 4, I think maybe bumping the limit up to 64 MB might be more prudent in case someone has a less powerful machine or Firefox 3 is ported to a mobile device.  


(In reply to comment #19)
> This also points out that making regexp to consume less memory in pathological
> cases will allow to decrease the quota.
> 

Considering that's the only javascript function I've noticed that has a problem with long strings, that might be the best idea.

I'm not sure why a 300 MB quota is required to pass my original test case in the first place though since a 32 MB quota is capable of handling RegExp string match of around 640 KB.  One would think that doubling the script quota should at least double possible match size.

In any case when I originally went to file this bug I searched for the string "script stack space is exhausted" and found no results.  This would seem to indicate that no one else had any issues with this, so most likely there are no other real world examples of this being a problem (other than my extension, which I fixed).

Comment 21

[Igor Bukanov]

(In reply to comment #18)
> However I'm missing something: we used to
> have a 500K or so thread-stack limit and a 1000 inline call limit, IIRC. How
> does the latter equate to 300M of inline call stack space?

The regexp arena is bounded by the same quota as the arenas for the interpreter. In the test case from the comment 1 the regexp is run against a string with 2e6 characters resulting in allocating of almost 300MB for regexp backtrack space.

Comment 22

[Brendan Eich [:brendan]]

I re-read the bug and saw the regexp connection just after asking that dumb question, sorry. This does seem like the change to mitigate.

Compatibility is hard, especially with low-level resource limits coupled to user code only indirectly or in obscure/buggy implementation-dependent ways.

/be

Comment 23

[Igor Bukanov]

Attachment: v2

Ideally the size of quota should be a preference, but reading the preferences from the xpconnect code requires non-trivial efforts AFAICS. For now I suggest to bump the quota to 100MB.

Comment 24

[Brendan Eich [:brendan]]

Comment on attachment 310330 [details] [diff] [review]
v2

Ok, hope this is enough for 1.9/fx3.

/be

Comment 25

[x0]

Wouldn't it be better to increase the limit in JS_DEFAULT_SCRIPT_STACK_QUOTA? In the browser, it would be best to make the limit dependent on the size of physical memory. In the js shell, a command line option is missing, and huge scripts fail before they are able to call stackQuota(), so the default shouldn't be too small (currently a script with about 16 MB size fails to load).

Comment 26

[Igor Bukanov]

(In reply to comment #25)
> Wouldn't it be better to increase the limit in JS_DEFAULT_SCRIPT_STACK_QUOTA?

Too generous JS_DEFAULT_SCRIPT_STACK_QUOTA may affect other embeddings. If anything, it should be decreased. 

Comment 27

[Mike Schroepfer]

Comment on attachment 310330 [details] [diff] [review]
v2

already blocking so doesn't require approval - clear to land.

Comment 28

[Igor Bukanov]

(In reply to comment #25)
> In the browser, it would be best to make the limit dependent on the size of
> physical memory.

The purpose of the quota is to prevent denial-of-service, not to limit the amount of available memory. In particular, the quota does not account for GC-heap allocated things. Even with the disabled quota management the code still must properly recover from out-of-memory conditions.

As such the size of the quota should be ideally CPU/memory speed bound, but that is for another bug.

Comment 29

[Igor Bukanov]

I cannot watch tinderbox myself before b5 freeze.

Comment 30

[Brendan Eich [:brendan]]

Reed, could you help land this bug's patch? Thanks,

/be

Comment 31

[Reed Loden [:reed]]

Checking in js/src/xpconnect/src/xpcjsruntime.cpp;
/cvsroot/mozilla/js/src/xpconnect/src/xpcjsruntime.cpp,v  <--  xpcjsruntime.cpp
new revision: 1.74; previous revision: 1.73
done

Comment 32

[Bob Clary [:bc] (inactive)]

/cvsroot/mozilla/js/tests/js1_5/extensions/regress-420869-01.js,v  <--  regress-420869-01.js
initial revision: 1.1

Comment 33

[Bob Clary [:bc] (inactive)]

Note: this test is dependent upon architecture and available memory. On a x86_64 machine with 2G and a 64bit build, it will fail with InternalError: script stack space quota is exhausted however on a x86_64 with 4G and a 64bit build it will pass.

Comment 34

[Bob Clary [:bc] (inactive)]

v 1.9.0

Comment 35

[Bob C]

I've logged an error that occurs with Microsoft Infopath web forms that seems to be related to this.  Was okay at FF 3.0.x, upgraded to 3.6 and Infopath no longer works. Get Error: script stack space quota is exhausted in the Error Console.

Comment 36

[Brendan Eich [:brendan]]

(In reply to comment #35)
> I've logged an error that occurs with Microsoft Infopath web forms that seems
> to be related to this.  Was okay at FF 3.0.x, upgraded to 3.6 and Infopath no
> longer works. Get Error: script stack space quota is exhausted in the Error
> Console.

Bob filed bug 547967.

/be

Comment 37

[Jerry Lugert]

I'm seeing a similar problem with largish (15 open tabs), but reasonable lucidchart usage. Mac 3.6.10. "Script stack space quota is exhausted." 

Note: http://entanglednetworks.com/foo
fx  = 1.25M
chrome = 105M


Jerry