557180 - [HTML5] [Crash] Stack overflow in documents with excessively nested tags [@ nsRuleNode::GetStyleData(nsStyleStructID, nsStyleContext*, int) ]

Status: RESOLVED DUPLICATE of bug 323394

(Core :: DOM: HTML Parser, defect, P2)

Description

[Arisu]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2) Gecko/20100115 Firefox/3.6 (.NET CLR 3.5.30729)
Build Identifier: 

With HTML5 enabled, trying to load a document that contains excessively nested
tags results in a stack overflow because the nsCSSFrameConstructor does a
recursive call for every level of nesting, which quickly exhausts the available
stack space. This bug affects both 1.9.2 and trunk.

Example of such a call chain with <div> tags:
    nsCSSFrameConstructor::ConstructFramesFromItemList() <───────────────┐
    └─> nsCSSFrameConstructor::ConstructFramesFromItem()                 │
        └─> nsCSSFrameConstructor::ConstructFrameFromItemInternal()      │
            └─> nsCSSFrameConstructor::ConstructNonScrollableBlock()     │
                └─> nsCSSFrameConstructor::ConstructBlock()              │
                    └─> nsCSSFrameConstructor::ProcessChildren()         │
                        └────────────────────────────────────────────────┘

The combined size of their frames is about 488 bytes, so if there were no other
calls, this alone would exceed Windows's default 1 MiB stack after 2148
nestings.

In practice, this will happen much sooner because the stack isn't empty to
begin with and there a lot of intermediate calls being done - especially in
nsCSSFrameConstructor::ConstructFramesFromItem() which indirectly triggers
another recursion, namely nsRuleNode::WalkRuleTree(), by invoking
styleContext->GetStyleText(), so this is where most of your crashes will occur.

While testing, I could sometimes reproduce this crash for a nesting level only
slightly over 1000, making this crash observable in some real websites too;
see this bug's URL for an example.

I don't have enough understanding of how this code works, so I can't take this
bug, but I'll attach:
    - A test case containing 2000 levels of <div> nesting
    - A full NTSD memory dump (including code sections) of the latest nightly;
      it was produced by loading the test case

Noteworthy is that without HTML5 enabled, I can't seem to get stack overflows
with even millions of nested tags - even though the code path looks similar.
Also, this bug is actually a dupe of Bug 519726 (which is closed, however).

Reproducible: Sometimes

Comment 1

[Arisu]

Attachment: Test case reproducing this bug

Comment 2

[Arisu]

And here's the crash dump I promised, produced by the 2010-04-04 Win32 nightly:
http://www.mediafire.com/?gnxygd0h5iq

Comment 3

[(mostly gone) XtC4UaLL [:xtc4uall]]

Signature	nsRuleNode::GetStyleData(nsStyleStructID, nsStyleContext*, int)
UUID	11489c17-879a-4406-8f19-cf8fd2100405
Time 	2010-04-05 06:14:10.801012
Uptime	68
Last Crash	890532 seconds before submission
Product	Firefox
Version	3.7a4pre
Build ID	20100404051307
Branch	1.9.3
OS	Windows NT
OS Version	5.1.2600 Service Pack 3
CPU	x86
CPU Info	GenuineIntel family 15 model 2 stepping 9
Crash Reason	EXCEPTION_STACK_OVERFLOW
Crash Address	0x100882a4
User Comments	Bug 557180

Crashing Thread
Frame 	Module 	Signature 	Source
0 	xul.dll 	nsRuleNode::GetStyleData(nsStyleStructID,nsStyleContext*,int) 	layout/style/nsRuleNode.cpp:6078
1 	xul.dll 	nsRuleNode::WalkRuleTree(nsStyleStructID,nsStyleContext*,nsRuleData*,nsCSSStruct*) 	layout/style/nsRuleNode.cpp:2039
2 	xul.dll 	nsRuleNode::GetStyleData(nsStyleStructID,nsStyleContext*,int) 	layout/style/nsStyleStructList.h:89
3 	xul.dll 	nsRuleNode::WalkRuleTree(nsStyleStructID,nsStyleContext*,nsRuleData*,nsCSSStruct*) 	layout/style/nsRuleNode.cpp:2039
4 	xul.dll 	nsRuleNode::GetStyleData(nsStyleStructID,nsStyleContext*,int) 	layout/style/nsStyleStructList.h:89
5 	xul.dll 	nsRuleNode::WalkRuleTree(nsStyleStructID,nsStyleContext*,nsRuleData*,nsCSSStruct*) 	layout/style/nsRuleNode.cpp:2039
6 	xul.dll 	nsRuleNode::GetStyleData(nsStyleStructID,nsStyleContext*,int) 	layout/style/nsStyleStructList.h:89
7 	xul.dll 	nsRuleNode::WalkRuleTree(nsStyleStructID,nsStyleContext*,nsRuleData*,nsCSSStruct*) 	layout/style/nsRuleNode.cpp:2039
8 	xul.dll 	nsRuleNode::GetStyleData(nsStyleStructID,nsStyleContext*,int) 	layout/style/nsStyleStructList.h:89
9 	xul.dll 	nsRuleNode::WalkRuleTree(nsStyleStructID,nsStyleContext*,nsRuleData*,nsCSSStruct*) 	layout/style/nsRuleNode.cpp:2039
10 	xul.dll 	nsRuleNode::GetStyleData(nsStyleStructID,nsStyleContext*,int) 	layout/style/nsStyleStructList.h:89
11 	xul.dll 	nsRuleNode::WalkRuleTree(nsStyleStructID,nsStyleContext*,nsRuleData*,nsCSSStruct*) 	layout/style/nsRuleNode.cpp:2039
12 	xul.dll 	nsRuleNode::GetStyleData(nsStyleStructID,nsStyleContext*,int) 	layout/style/nsStyleStructList.h:89
13 	xul.dll 	nsRuleNode::WalkRuleTree(nsStyleStructID,nsStyleContext*,nsRuleData*,nsCSSStruct*) 	layout/style/nsRuleNode.cpp:2039
14 	xul.dll 	nsRuleNode::GetStyleData(nsStyleStructID,nsStyleContext*,int) 	layout/style/nsStyleStructList.h:89
15 	xul.dll 	nsRuleNode::WalkRuleTree(nsStyleStructID,nsStyleContext*,nsRuleData*,nsCSSStruct*) 	layout/style/nsRuleNode.cpp:2039
16 	xul.dll 	nsRuleNode::GetStyleData(nsStyleStructID,nsStyleContext*,int) 	layout/style/nsStyleStructList.h:89
17 	xul.dll 	nsRuleNode::WalkRuleTree(nsStyleStructID,nsStyleContext*,nsRuleData*,nsCSSStruct*) 	layout/style/nsRuleNode.cpp:2039
18 	xul.dll 	nsRuleNode::GetStyleData(nsStyleStructID,nsStyleContext*,int) 	layout/style/nsStyleStructList.h:89
19 	xul.dll 	nsRuleNode::WalkRuleTree(nsStyleStructID,nsStyleContext*,nsRuleData*,nsCSSStruct*) 	layout/style/nsRuleNode.cpp:2039
20 	xul.dll 	nsRuleNode::GetStyleData(nsStyleStructID,nsStyleContext*,int) 	layout/style/nsStyleStructList.h:89
21 	xul.dll 	nsRuleNode::WalkRuleTree(nsStyleStructID,nsStyleContext*,nsRuleData*,nsCSSStruct*) 	layout/style/nsRuleNode.cpp:2039
22 	xul.dll 	nsRuleNode::GetTextData(nsStyleContext*) 	layout/style/nsRuleNode.cpp:1601
23 	xul.dll 	nsRuleNode::GetStyleText(nsStyleContext*,int) 	layout/style/nsStyleStructList.h:89
24 	xul.dll 	nsStyleContext::DoGetStyleText(int) 	obj-firefox/dist/include/nsStyleStructList.h:89
25 	xul.dll 	nsStyleContext::GetStyleText() 	obj-firefox/dist/include/nsStyleStructList.h:89
26 	xul.dll 	nsCSSFrameConstructor::ConstructFramesFromItem(nsFrameConstructorState&,nsCSSFrameConstructor::FrameConstructionItemList::Iterator&,nsIFrame*,nsFrameItems&) 	layout/base/nsCSSFrameConstructor.cpp:5396
27 	xul.dll 	nsCSSFrameConstructor::ConstructFramesFromItemList(nsFrameConstructorState&,nsCSSFrameConstructor::FrameConstructionItemList&,nsIFrame*,nsFrameItems&) 	layout/base/nsCSSFrameConstructor.cpp:8995
28 	xul.dll 	nsCSSFrameConstructor::ProcessChildren(nsFrameConstructorState&,nsIContent*,nsStyleContext*,nsIFrame*,int,nsFrameItems&,int,PendingBinding*) 	layout/base/nsCSSFrameConstructor.cpp:9103
29 	xul.dll 	nsCSSFrameConstructor::ConstructBlock(nsFrameConstructorState&,nsStyleDisplay const*,nsIContent*,nsIFrame*,nsIFrame*,nsStyleContext*,nsIFrame**,nsFrameItems&,int,PendingBinding*) 	layout/base/nsCSSFrameConstructor.cpp:10153
30 	xul.dll 	nsCSSFrameConstructor::ConstructNonScrollableBlock(nsFrameConstructorState&,nsCSSFrameConstructor::FrameConstructionItem&,nsIFrame*,nsStyleDisplay const*,nsFrameItems&,nsIFrame**) 	layout/base/nsCSSFrameConstructor.cpp:4491
31 	xul.dll 	nsIContent::IsInHTMLDocument() 	obj-firefox/dist/include/nsIContent.h:260
32 	xul.dll 	nsNodeInfo::Release() 	content/base/src/nsNodeInfo.cpp:141
33 	xul.dll 	nsStyleSet::ProbePseudoElementStyle(nsIContent*,nsCSSPseudoElements::Type,nsStyleContext*) 	layout/style/nsStyleSet.cpp:991
34 	xul.dll 	nsCSSFrameConstructor::ProcessChildren(nsFrameConstructorState&,nsIContent*,nsStyleContext*,nsIFrame*,int,nsFrameItems&,int,PendingBinding*) 	layout/base/nsCSSFrameConstructor.cpp:9103
35 		@0x6d1327f 	
36 	xul.dll 	combine_difference_ca 	obj-firefox/gfx/cairo/libpixman/src/pixman-combine.c.template:751
37 	xul.dll 	nsContentSink::NotifyAppend(nsIContent*,unsigned int) 	content/base/src/nsContentSink.cpp:1351

Comment 4

[Henri Sivonen (:hsivonen) (away from Bugzilla until 2025-12-29)]

This looks bad. Bug 555899 was supposed to fix this.

Comment 5

[Arisu]

(In reply to comment #4)
The crash occurs before nsHtml5TreeBuilder::[silent]Push() is called at all:
    0:000> bp xul!nsHtml5TreeBuilder::push
    0:000> bp xul!nsHtml5TreeBuilder::silentPush
    0:000> g [and switching back to Firefox, opening the test case]
    (650.424): Stack overflow - code c00000fd (first chance)

But there's more: I'm now getting stack overflows with HTML5 disabled as well.
This happened just now as I'm writing this and never did before in my previous
tests so I was quite puzzled, but then I noticed that my original test files
had .html as extension while the file I uploaded to Bugzilla is .xhtml.

Based on that, I could then make these new observations:
    - With HTML5 enabled, the browser crashes for both .html and .xhtml files
    - With HTML5 disabled, the browser crashes only with .xhtml test cases

This holds true for trunk, 1.9.2, 1.9.1, 1.9.0 and maybe others, so this isn't
directly the fault of the HTML5 code after all. Should this be reassigned to
the layout component?

Comment 6

[Henri Sivonen (:hsivonen) (away from Bugzilla until 2025-12-29)]

The fix for bug 561874 will avoid the crash in the HTML case here. The attached test case doesn't crash on XP for me, but the root cause here is in the layout code (bug 323394). The parsers can only take steps to generate the wrong DOM to avoid triggering the layout crash.