Bug 14886 – Stack overflow due to deeply nested parse tree doing repeated string concatentation

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

[Michael A. Puls II]

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.

[Michael A. Puls II]

Created attachment 15844 [details]
TC that will crash Safari

If the situation cannot be handled, an exception should be thrown instead of crashing.

[Adam Roben (:aroben)]

Thanks for the bug report, Michael! Can you tell us what version(s) of Safari you tested with?

[Michael A. Puls II]

Safari 3.0.2(522.13.1) and that Safari with WebKit-SVN-r24872

[Adam Roben (:aroben)]

Could you attach a crash log as described at <http://webkit.org/quality/crashlogs.html>?

[Michael A. Puls II]

(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.

[Matt Lilek]

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]

[Mark Rowe (bdash)]

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 *.

[Mark Rowe (bdash)]

<rdar://problem/5387997>

[Eric Seidel (no email)]

This may be fixed with SquirellFish?

[Michael A. Puls II]

(In reply to comment #9)
> This may be fixed with SquirellFish?
> 

Well, Safari still silently dies with the latest webkit nightly.

[Darin Adler]

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.

[Darin Adler]

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.

[Darin Adler]

Created attachment 24995 [details]
patch

[Darin Adler]

Created attachment 25004 [details]
improved patch

[Sam Weinig]

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

[Maciej Stachowiak]

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.

[Darin Adler]

(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.

[Darin Adler]

http://trac.webkit.org/changeset/38247