Bug 30898 – Browser crash by deeply nested elements

• Status: RESOLVED
• Resolution: DUPLICATE
• Component: Layout and Rendering

[Kent Tamura]

Environment:
  Windows Vista
  Safari 4.0.3 (531.9.1)

1. try to open http://fs.org.ua/oops.svg
2. The browser crashes

This is also reproduced with Chrome4/Windows, and NOT reproduced with Safari4/Mac and Chrome/Mac.

http://crbug.com/18830 has some more information.  It seems a stack overflow.

[Kent Tamura]

I think we have 4 choices:
 A) limit element depth in HTML/XML parsers
 B) limit renderer depth
 C) limit recursion depth in the renderer code
 D) not use recursions in the renderer code

B, C and D seem hard to implement.

[Kent Tamura]

>  A) limit element depth in HTML/XML parsers
>  B) limit renderer depth
>  C) limit recursion depth in the renderer code
>  D) not use recursions in the renderer code
> 
> B, C and D seem hard to implement.

A doesn't work well because JavaScript code can make deep trees.

[Kent Tamura]

Created attachment 42845 [details]
HTML example

[Kent Tamura]

As for http://fs.org.ua/oops.svg
  This crashes Safari and Chromium on only Windows
  The data is 33,000 nested <a> elements.
  It's a stack overflow at verticalPosition() and verticalPositionFromCache()
  I confirmed this was solved by increasing the stack size.

chrome_62f30000!WebCore::RenderObject::isInline(void)+0x3
chrome_62f30000!WebCore::RenderBoxModelObject::verticalPosition(bool firstLine = false)+0x24
chrome_62f30000!WebCore::RenderInline::verticalPositionFromCache(bool firstLine = false)+0x5b
chrome_62f30000!WebCore::RenderBoxModelObject::verticalPosition(bool firstLine = false)+0x13b
chrome_62f30000!WebCore::RenderInline::verticalPositionFromCache(bool firstLine = false)+0x5b
chrome_62f30000!WebCore::RenderBoxModelObject::verticalPosition(bool firstLine = false)+0x13b
chrome_62f30000!WebCore::RenderInline::verticalPositionFromCache(bool firstLine = false)+0x5b
chrome_62f30000!WebCore::RenderBoxModelObject::verticalPosition(bool firstLine = false)+0x13b
chrome_62f30000!WebCore::RenderInline::verticalPositionFromCache(bool firstLine = false)+0x5b
chrome_62f30000!WebCore::RenderBoxModelObject::verticalPosition(bool firstLine = false)+0x13b
chrome_62f30000!WebCore::RenderInline::verticalPositionFromCache(bool firstLine = false)+0x5b


As for the attached HTML
  This crashes Safari on not only Windows but also Mac OS.
  The data is 33,000 nested DIV elements.
  It seems a stack overflow at layout() / layoutBlock() / layoutBlockChildren().

0   com.apple.WebCore             	0x90beea5c WebCore::RenderBlock::layoutBlock(bool) + 12
1   com.apple.WebCore             	0x90beea18 WebCore::RenderBlock::layout() + 40
2   com.apple.WebCore             	0x90bf0744 WebCore::RenderBlock::layoutBlockChildren(bool, int&) + 932
3   com.apple.WebCore             	0x90bef28d WebCore::RenderBlock::layoutBlock(bool) + 2109
4   com.apple.WebCore             	0x90beea18 WebCore::RenderBlock::layout() + 40
5   com.apple.WebCore             	0x90bf0744 WebCore::RenderBlock::layoutBlockChildren(bool, int&) + 932
6   com.apple.WebCore             	0x90bef28d WebCore::RenderBlock::layoutBlock(bool) + 2109
7   com.apple.WebCore             	0x90beea18 WebCore::RenderBlock::layout() + 40
8   com.apple.WebCore             	0x90bf0744 WebCore::RenderBlock::layoutBlockChildren(bool, int&) + 932
9   com.apple.WebCore             	0x90bef28d WebCore::RenderBlock::layoutBlock(bool) + 2109
10  com.apple.WebCore             	0x90beea18 WebCore::RenderBlock::layout() + 40
11  com.apple.WebCore             	0x90bf0744 WebCore::RenderBlock::layoutBlockChildren(bool, int&) + 932
12  com.apple.WebCore             	0x90bef28d WebCore::RenderBlock::layoutBlock(bool) + 2109
13  com.apple.WebCore             	0x90beea18 WebCore::RenderBlock::layout() + 40

[Kent Tamura]

Created attachment 42847 [details]
A demo patch

The patch introduces the limitation of renderer tree depth.
It resolves both of the .svg case and the HTML case.

I'm not sure whether adding a new field to RenderObject is reasonable or not.

[Kent Tamura]

Created attachment 42940 [details]
Proposed patch

We can avoid the stack overflow by this patch.  However,
 * It adds 1 int field to RenderObject.  It'll increase memory consumption.
 * The test is always timed out.

[Dave Hyatt]

Comment on attachment 42940 [details]
Proposed patch

Your ChangeLog comment says 4096, but then your #define is 8192.

Your ifdef is in Node, but if you're really talking about renderobject depth limiting and not DOM limiting, then it should be over in RenderObject files.

You cannot add a field to RenderObject.  That's not an acceptable memory hit to take.

[Kent Tamura]

(In reply to comment #7)
> You cannot add a field to RenderObject.  That's not an acceptable memory hit to
> take.

Do you have other ideas to limit renderer tree depth?
  Adding depth field to DOM nodes must not be acceptable too.
  Measuring a depth in tree building process hits performance.
  Limiting the depth in HTML/XML parsers is not a complete way because of JavaScript.

[Kent Tamura]

I changed verticalPositionFromCache() -> verticalPosition() -> verticalPositionFromCache() -> ... recursion to a loop.  It solved the stack overflow at that point, but I saw another stack overflow at another code path.
We need to rewrite all of recursive calls.  This way is not practical.

[Keith Kyzivat]

This is a duplicate of bug 18282

[Keith Kyzivat]

I have a proposed patch that I've had done for a while now, was just trying to think if there would be any better way to do it.

It caps the tree in the parser when parser adds a node, and also in Javascript when a node is appended.
There is no memory consumption increase, but there is a hit in performance, since depth of node to be added/appended to is calculated, for each add/append.

Since there is a performance hit, I added a build flag to turn it on, and specify the maximum depth.  Under standard desktop browsers with large max stack size, this can be omitted, since the maximum depth is generally in the hundreds of thousands.  For low-memory devices, this is a bigger deal, and thus they may configure webkit with --enable-domtree-maxdepth=<value>.

Patch coming shortly.

[Kent Tamura]

*** This bug has been marked as a duplicate of bug 18282 ***