Summary: | Browser crash by deeply nested elements | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Product: | WebKit | Reporter: | Kent Tamura <tkent> | ||||||||
Component: | Layout and Rendering | Assignee: | Nobody <webkit-unassigned> | ||||||||
Status: | RESOLVED DUPLICATE | ||||||||||
Severity: | Critical | CC: | ggaren, hyatt, kamaji, laszlo.gombos, mitz | ||||||||
Priority: | P1 | ||||||||||
Version: | 528+ (Nightly build) | ||||||||||
Hardware: | All | ||||||||||
OS: | All | ||||||||||
URL: | http://fs.org.ua/oops.svg | ||||||||||
Attachments: |
|
Description
Kent Tamura
2009-10-28 22:51:51 PDT
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. > 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.
Created attachment 42845 [details]
HTML example
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 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.
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.
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.
(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. 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. This is a duplicate of bug 18282 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. *** This bug has been marked as a duplicate of bug 18282 *** |