Bug 14886 - Stack overflow due to deeply nested parse tree doing repeated string concatentation
Summary: Stack overflow due to deeply nested parse tree doing repeated string concaten...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 523.x (Safari 3)
Hardware: All All
: P1 Normal
Assignee: Darin Adler
URL:
Keywords: HasReduction, InRadar
Depends on:
Blocks:
 
Reported: 2007-08-05 15:07 PDT by Michael A. Puls II
Modified: 2008-11-09 17:28 PST (History)
5 users (show)

See Also:


Attachments
TC that will crash Safari (3.90 KB, application/zip)
2007-08-05 15:08 PDT, Michael A. Puls II
no flags Details
work in progress (62.67 KB, patch)
2008-11-07 18:05 PST, Darin Adler
no flags Details | Formatted Diff | Diff
patch (69.61 KB, patch)
2008-11-08 11:58 PST, Darin Adler
no flags Details | Formatted Diff | Diff
improved patch (70.00 KB, patch)
2008-11-09 11:59 PST, Darin Adler
sam: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Michael A. Puls II 2007-08-05 15:07:26 PDT
If you do:

var x = "string1" + "string2" + "stringN" etc. where you're adding an insane amount of strings together, Safari will crash.

IE will crash also.
Opera throws an exception.
Firefox handles it.
Comment 1 Michael A. Puls II 2007-08-05 15:08:50 PDT
Created attachment 15844 [details]
TC that will crash Safari

If the situation cannot be handled, an exception should be thrown instead of crashing.
Comment 2 Adam Roben (:aroben) 2007-08-05 15:18:43 PDT
Thanks for the bug report, Michael! Can you tell us what version(s) of Safari you tested with?
Comment 3 Michael A. Puls II 2007-08-05 16:12:56 PDT
Safari 3.0.2(522.13.1) and that Safari with WebKit-SVN-r24872
Comment 4 Adam Roben (:aroben) 2007-08-05 17:10:25 PDT
Could you attach a crash log as described at <http://webkit.org/quality/crashlogs.html>?
Comment 5 Michael A. Puls II 2007-08-05 17:53:27 PDT
(In reply to comment #4)
> Could you attach a crash log as described at
> <http://webkit.org/quality/crashlogs.html>?
> 

Tried, but it does not produce a crash log or memory dump. This is a silent crash where Safari just dies.
Comment 6 Matt Lilek 2007-08-05 18:09:18 PDT
My local debug build of r24875 gives me this back trace:

Thread: 0

Exception:  EXC_BAD_ACCESS (0x0001)
Codes:      KERN_INVALID_ADDRESS (0x0001) at 0xbf7fffd0

Thread 0 Crashed:
0   com.apple.JavaScriptCore       	0x005b72f4 KJS::AddNode::evaluate(KJS::ExecState*) + 12 (nodes.cpp:1205)
1   com.apple.JavaScriptCore       	0x005b733c KJS::AddNode::evaluate(KJS::ExecState*) + 84 (nodes.cpp:1207)
[it repeats frame 1 for ~500 frames]
Comment 7 Mark Rowe (bdash) 2007-08-06 02:26:58 PDT
This is not specific to strings, nor really to the + operation.  The parse tree that's generated by the input leads to a stack overflow during the recursive evaluation.  It should also be reproducible with numbers, and with various other operators such as -, /, and *.
Comment 8 Mark Rowe (bdash) 2007-08-06 02:27:37 PDT
<rdar://problem/5387997>
Comment 9 Eric Seidel (no email) 2008-07-03 22:49:28 PDT
This may be fixed with SquirellFish?
Comment 10 Michael A. Puls II 2008-07-04 00:48:44 PDT
(In reply to comment #9)
> This may be fixed with SquirellFish?
> 

Well, Safari still silently dies with the latest webkit nightly.
Comment 11 Darin Adler 2008-11-06 09:32:39 PST
I have a patch mostly done, starting with Chris Brichford's patch from another bug. I'm figuring out what the limit should be -- 1000 was too large and I crashed while destroying the AST. And making a regression test. Should be done shortly.
Comment 12 Darin Adler 2008-11-07 18:05:45 PST
Created attachment 24981 [details]
work in progress

This patch works, but I also need to make the test case into a regression test ready to check in and write change log.
Comment 13 Darin Adler 2008-11-08 11:58:25 PST
Created attachment 24995 [details]
patch
Comment 14 Darin Adler 2008-11-09 11:59:50 PST
Created attachment 25004 [details]
improved patch
Comment 15 Sam Weinig 2008-11-09 16:20:35 PST
Comment on attachment 25004 [details]
improved patch

Looks good.  My only concern is that "Expression too deep" is a little vague, but I am short on better alternatives.

r=me
Comment 16 Maciej Stachowiak 2008-11-09 16:33:00 PST
Comment on attachment 25004 [details]
improved patch

> void NodeReleaser::adopt(PassRefPtr<ParserRefCounted> node)

1) This is a bit of a funny name, perhaps it should be called release()? Or markForRelease()? Or something? It's true that the releaser is meant to take ownership of the node, but it feels a little funny to focus on that instead of the intended side effect that it will get freed.

2) It took me a while to understand how this works, and while I get it now, it was very unclear at first and I am not sure it was what you intended. In particular, NodeReleaser::adopt looks like it expects to take ownership of an existing reference, but instead of a PassRefPtr it is given a RefPtr, at call sites like this:

> ArrayNode::releaseNodes(NodeReleaser& releaser)
> {
>    releaser.adopt(m_element);
> }

Constructing a PassRefPtr from a RefPtr doesn't release the original reference. I was expecting to see m_element.release() here. I understand now that this prevents recursive invocation of destructors, because the child nodes end up having two refs, and the parent's ref is removed first, then the one from the Vector. This seems awfully subtle, and leads to refcount thrash of every node at destruction time, which is extra unfortunate due to the external refcount hashtable. Was it what you meant?

I will r+ anyway since the patch works, but please at least add an explanatory comment, explain in the ChangeLog why it was done this way, and clarify whether any perf testing was done to see if the extra cost of destruction costs us anything here.

Or if this was not on purpose, it would be good to do it the more straightforward way.
Comment 17 Darin Adler 2008-11-09 16:37:10 PST
(In reply to comment #16)
> 1) This is a bit of a funny name, perhaps it should be called release()? Or
> markForRelease()?

I think releaseSoon would be a good name. If I can find you on IRC we can talk about other names.

> NodeReleaser::adopt looks like it expects to take ownership of an
> existing reference, but instead of a PassRefPtr it is given a RefPtr, at call
> sites like this:
> 
> > ArrayNode::releaseNodes(NodeReleaser& releaser)
> > {
> >    releaser.adopt(m_element);
> > }
> 
> Constructing a PassRefPtr from a RefPtr doesn't release the original reference.
> I was expecting to see m_element.release() here. I understand now that this
> prevents recursive invocation of destructors, because the child nodes end up
> having two refs, and the parent's ref is removed first, then the one from the
> Vector.

No, that's not how it works. The way it actually works is that adopt is a function that takes a RefPtr& and does the release. I can change the name of adopt to releaseSoon if you think that is clearer.

The confusion is due to the fact that I named two different functions adopt. You're looking at the private one that's an implementation detail.

> Or if this was not on purpose, it would be good to do it the more
> straightforward way.

I'm sorry the code isn't clear. I can make it better. But the scheme actually is the simpler one you're talking about.
Comment 18 Darin Adler 2008-11-09 17:28:43 PST
http://trac.webkit.org/changeset/38247