Bug 14771 – Unbounded memory growth in KJS::UString when repeatedly slicing and prepending/appending

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[David Smith]

Clicking the "go" button in the nightly build for r24594 either hangs the browser (and to a certain extent the computer) for a long time, or crashes.

[Matt Lilek]

Thread 0 Crashed:
0   <<00000000>> 	0xffff8aec __memcpy + 844 (cpu_capabilities.h:189)
1   com.apple.JavaScriptCore 	0x005aa6cc KJS::UString::UString[in-charge](KJS::UString const&, KJS::UString const&) + 496 (ustring.cpp:453)
2   com.apple.JavaScriptCore 	0x00609d14 KJS::operator+(KJS::UString const&, KJS::UString const&) + 52 (ustring.h:472)
3   com.apple.JavaScriptCore 	0x005aeb1c KJS::add(KJS::ExecState*, KJS::JSValue*, KJS::JSValue*, char) + 300 (operations.cpp:228)
4   com.apple.JavaScriptCore 	0x005aeda8 KJS::AddNode::evaluate(KJS::ExecState*) + 356 (nodes.cpp:1213)
5   com.apple.JavaScriptCore 	0x005be49c KJS::AssignResolveNode::evaluate(KJS::ExecState*) + 420 (nodes.cpp:1463)
6   com.apple.JavaScriptCore 	0x0059f890 KJS::ExprStatementNode::execute(KJS::ExecState*) + 220 (nodes.cpp:1764)
7   com.apple.JavaScriptCore 	0x0059bfb8 KJS::SourceElementsNode::execute(KJS::ExecState*) + 624 (nodes.cpp:2570)
8   com.apple.JavaScriptCore 	0x0059fab4 KJS::BlockNode::execute(KJS::ExecState*) + 216 (nodes.cpp:1741)
9   com.apple.JavaScriptCore 	0x0059e674 KJS::ForNode::execute(KJS::ExecState*) + 1008 (nodes.cpp:1912)
10  com.apple.JavaScriptCore 	0x0059bfb8 KJS::SourceElementsNode::execute(KJS::ExecState*) + 624 (nodes.cpp:2570)
11  com.apple.JavaScriptCore 	0x0059fab4 KJS::BlockNode::execute(KJS::ExecState*) + 216 (nodes.cpp:1741)
12  com.apple.JavaScriptCore 	0x005a0694 KJS::DeclaredFunctionImp::execute(KJS::ExecState*) + 92 (function.cpp:321)
13  com.apple.JavaScriptCore 	0x005a101c KJS::FunctionImp::callAsFunction(KJS::ExecState*, KJS::JSObject*, KJS::List const&) + 688 (function.cpp:109)
14  com.apple.JavaScriptCore 	0x00593ce0 KJS::JSObject::call(KJS::ExecState*, KJS::JSObject*, KJS::List const&) + 288 (object.cpp:98)
15  com.apple.JavaScriptCore 	0x005b42a8 KJS::FunctionCallResolveNode::evaluate(KJS::ExecState*) + 792 (nodes.cpp:695)
16  com.apple.JavaScriptCore 	0x0059f890 KJS::ExprStatementNode::execute(KJS::ExecState*) + 220 (nodes.cpp:1764)
17  com.apple.JavaScriptCore 	0x0059be64 KJS::SourceElementsNode::execute(KJS::ExecState*) + 284 (nodes.cpp:2564)
18  com.apple.JavaScriptCore 	0x0059fab4 KJS::BlockNode::execute(KJS::ExecState*) + 216 (nodes.cpp:1741)
19  com.apple.JavaScriptCore 	0x005a0694 KJS::DeclaredFunctionImp::execute(KJS::ExecState*) + 92 (function.cpp:321)
20  com.apple.JavaScriptCore 	0x005a101c KJS::FunctionImp::callAsFunction(KJS::ExecState*, KJS::JSObject*, KJS::List const&) + 688 (function.cpp:109)
21  com.apple.JavaScriptCore 	0x00593ce0 KJS::JSObject::call(KJS::ExecState*, KJS::JSObject*, KJS::List const&) + 288 (object.cpp:98)
22  com.apple.WebCore        	0x012c3664 WebCore::JSAbstractEventListener::handleEvent(WebCore::Event*, bool) + 760 (kjs_events.cpp:116)
23  com.apple.WebCore        	0x012887e4 WebCore::EventTargetNode::handleLocalEvents(WebCore::Event*, bool) + 548 (EventTargetNode.cpp:166)
24  com.apple.WebCore        	0x012892fc WebCore::EventTargetNode::dispatchGenericEvent(WTF::PassRefPtr<WebCore::Event>, int&, bool) + 1524 (EventTargetNode.cpp:224)
25  com.apple.WebCore        	0x01289dcc WebCore::EventTargetNode::dispatchEvent(WTF::PassRefPtr<WebCore::Event>, int&, bool, WebCore::EventTarget*) + 396 (EventTargetNode.cpp:308)
26  com.apple.WebCore        	0x01289e60 WebCore::EventTargetNode::dispatchEvent(WTF::PassRefPtr<WebCore::Event>, int&, bool) + 80 (EventTargetNode.cpp:292)
27  com.apple.WebCore        	0x0128ad40 WebCore::EventTargetNode::dispatchMouseEvent(WebCore::AtomicString const&, int, int, int, int, int, int, bool, bool, bool, bool, bool, WebCore::Node*, WTF::PassRefPtr<WebCore::Event>) + 724 (EventTargetNode.cpp:480)
28  com.apple.WebCore        	0x0128b5a0 WebCore::EventTargetNode::dispatchMouseEvent(WebCore::PlatformMouseEvent const&, WebCore::AtomicString const&, int, WebCore::Node*) + 560 (EventTargetNode.cpp:397)
29  com.apple.WebCore        	0x014b7a38 WebCore::EventHandler::dispatchMouseEvent(WebCore::AtomicString const&, WebCore::Node*, bool, int, WebCore::PlatformMouseEvent const&, bool) + 212 (EventHandler.cpp:1202)
30  com.apple.WebCore        	0x014b84e4 WebCore::EventHandler::handleMouseReleaseEvent(WebCore::PlatformMouseEvent const&) + 1028 (EventHandler.cpp:1036)
31  com.apple.WebCore        	0x014af120 WebCore::EventHandler::mouseUp(NSEvent*) + 500 (EventHandlerMac.mm:523)
32  com.apple.WebKit         	0x00352bdc -[WebHTMLView mouseUp:] + 372 (WebHTMLView.mm:2987)
33  com.apple.AppKit         	0x937f9900 -[NSWindow sendEvent:] + 4728
34  com.apple.Safari         	0x000ab334 0x1000 + 697140
35  com.apple.AppKit         	0x937a28d4 -[NSApplication sendEvent:] + 4172
36  com.apple.Safari         	0x00016444 0x1000 + 87108
37  com.apple.AppKit         	0x93799d10 -[NSApplication run] + 508
38  com.apple.AppKit         	0x9388a87c NSApplicationMain + 452
39  com.apple.Safari         	0x0000246c 0x1000 + 5228
40  com.apple.Safari         	0x0004f1b0 0x1000 + 319920

[David Kilzer (:ddkilzer)]

Crashers are P1.

[David Kilzer (:ddkilzer)]

<rdar://problem/5364695>

[John Moe]

Two simpler(?) examples of the same problem:
var x = "0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789";

for (var i = 0; i < 100000000; i++) {
   x = 'aaaaaaaaaaaaaaaaaaaa' + x.slice(0,x.length-20);
}

and

var x = "0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789";

for (var i = 0; i < 100000000; i++) {
   x = x.slice(20,x.length) + 'aaaaaaaaaaaaaaaaaaaa';
}

[John Moe]

Created attachment 15724 [details]
Possibly A Patch?

A tenth was picked for no good reason.

[Mark Rowe (bdash)]

I've been doing some work on a related bug over the last few days.  The crash seen here is a result of multiple issues.

The issue that John's patch aims to address is that the repeated slicing and concatenation which should result in the strings memory usage remaining more or less constant currently leads to linear growth in memory usage.  This is because we are too aggressive in sharing the underlying string representation.  In the test cases mentioned in this bug report we end up with a 150 character string sitting at the end of a several hundred MB string representation (KJS::UString::Rep) with the large area before it now unused.

The fact that we hit a crash at all is due to the fact that many places in the UString implementation assume that fastMalloc/fastRealloc will never fail.  When you're dealing with string representations that are several hundred MBs in size, this is an unsafe assumption.  Updating UString to deal with this gracefully is being tracked by <rdar://problem/5352887>.

[Mark Rowe (bdash)]

Comment on attachment 15724 [details]
Possibly A Patch?

I'm going to mark this r-.  I spoke with Maciej on IRC about the general approach this patch takes, and he said:

07:04 <othermaciej> bdash: upon further thought - I think the right rule should be "don't use shared substring append on a string that is only a small part of its current buffer"
07:04 <oothermaciej> bdash: I think the patch might actually implement something close to that (it looks at post-append length though)

It should be simple to adjust the patch to this slightly different strategy.  It would also be a good idea to see if we can't come up with some decent criteria for "small part of its current buffer" that's not just picking a magic number out of thin air :-)

My other concern is that "10 * length" looks like we're asking for overflow to happen when dealing with large strings.

[John Moe]

After doing some tests, 1/10 seems to be not optimal.  Between 1/4 and 1/2 seems to be about the fastest on the tests I've run (for example improved from about 13.9 ms to about 8.1 ms on the Celtic Kane Javascript string test on my computer).  I would say pick 1/4 as it is closest to what is being done now.  Thoughts?

[John Moe]

Created attachment 15834 [details]
better patch?

[Mark Rowe (bdash)]

Comment on attachment 15834 [details]
better patch?

Hrm, those conditions are getting rather hairy!  Is there any way to factor them out to make it clearer what they're testing and why, without cluttering up the method body itself?  It would be great if you could include the bug title as well as the URL in the ChangeLog entry as well, to make it obvious at a glance what the issue is that is being resolved.

[Mark Rowe (bdash)]

Retitling and adjusting priority as this no longer crashes in ToT.

[John Moe]

It bothers me a bit that there are other quite similar chunks of Javascript that should not use enormous amounts, but currently will.  For example:

var lastChars = new Array();
for (var i = 0; i < 10000; i++) {
   var s = "x";
   for (var j = 0; j < 19; j++) {
      s += s;
   }
   lastChars[i] = s.slice(s.length-1,s.length);
}

This wouldn't have to ever use more than about 272 thousand chars, but will end up using over 2.6 billion chars.

Is it worth fixing only one of several ways to cause this UString unbounded and unused memory problem?

[Mark Rowe (bdash)]

it would be great if we could fix all instances of this issue.  Now that it does not cause a crash it is not such a serious issue, but such excessive memory use is clearly not desirable.

[Maciej Stachowiak]

Comment on attachment 15834 [details]
better patch?

I'd like to take this fix, but I think two issues need addressing:

1) The conditions to check whether append or prepend is allowed should be factored out into some separate inline functions with good clear names. They are getting complicated enough that it's hard to tell what the actual condition is.

2) There are other code paths that do similar checks for append, which I think should be given the same treatment. Let's update all of them at once. In particular, the three versions of UString::append should be updated.

3) It would be nice to include a test case that would show the unbounded memory growth without this fix.

Thanks for the fix! I'm looking forward to the updated version.

[Alexey Proskuryakov]

According to Radar, this was fixed in r24820.

[Geoffrey Garen]

Marking as fixed based on Alexey's comment.