439184 - stack overflow when large numbers of CSS rules match a single node [@ nsStyleSet::AddImportantRules]

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[tempeml4bugzilla]

User-Agent:       Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; .NET CLR 1.1.4322; FDM; .NET CLR 3.0.04506.30; .NET CLR 2.0.50727; .NET CLR 3.0.04506.648; .NET CLR 3.5.21022)
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.1a1pre) Gecko/2008061303 Minefield/3.1a1pre

While testing for a limit to CSS declarations, I had generated a CSS file containing over 50k unique declarations to a single ID, plus one declaration for another ID at the end of the CSS file.  File Size was 1,000,016 bytes (977kb).  Loading the page causes a crash in both the latest/fully updated FF2 and Minefield at the time of posting.

Reproducible: Always

Steps to Reproduce:
1.Visit Page.
2.Crash.
3.
Actual Results:  
Browser crashes.

Expected Results:  
The page should have rendered and presented two lines containing "Test" and two buttons to obtain the color styles.  "I Color" button is for the 50k declarations. That button should return the limit (I hope there isn't one) or a value of color:#999980 (or equivalent) as the last declared color for id="i". "Z Color" was to test if there was a filesize issue as well and should have returned Green or equivalent.

Fresh and unconfigured installations, as per W3C testing standards for CSS.
I have (Hopefully) attached the HTML page and the CSS file.  If you want the test itself to work (The buttons to produce results) You'll need to put Prototype.js in the same directory as the html file.  Prototype.js not included for obvious security reasons.

This test was originally designed for IE, which returns a filesize issue (Z was undefined) with a unique declaration to a single id limit of 4096 declarations (in which the file was shortened to that + Z and Z was defined as green).

Minefield Report:
Add-ons: {972ce4c6-7e08-4474-a285-3208198ce6fd}:3.1a1pre
BuildID: 2008061303
CrashTime: 1213413996
Email: 
InstallTime: 1213411680
ProductName: Firefox
SecondsSinceLastCrash: 2267
StartupTime: 1213412996
Theme: classic/1.0
UserID: 18a0ee35-f60a-474a-aafb-307af8ec1994
Vendor: Mozilla
Version: 3.1a1pre

Comment 1

[tempeml4bugzilla]

Attachment: The HTML Test that causes the crash.

Needs the CSS file as well.
Prototype.js not included, but useful if you want to extract results from the buttons.

Comment 2

[tempeml4bugzilla]

Comment on attachment 325063 [details]
The HTML Test that causes the crash.

Basically needs
http://rapidshare.com/files/122296773/CSSFSLimit.css.html because it's too large for bugzilla (977kb)

Comment 3

[Matthias Versen [:Matti]]

Please type about:crashes and provide the crash IDs from this cras

Comment 4

[Régis Caspar]

Confirmed with Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9pre) Gecko/2008061305 Minefield/3.0pre ID:2008061305

Crash report: http://crash-stats.mozilla.com/report/pending/6c861878-39fa-11dd-80a9-0013211cbf8a

Comment 5

[Régis Caspar]

Attachment: Crash info (call stack, etc)

Comment 6

[Matthias Versen [:Matti]]

confirming a bug in Firefox:General is usually a very bad idea but thanks for the crash id.

-> Core:CSS

Stack overflow: 
0  	xul.dll  	nsStyleSet::AddImportantRules  	 mozilla/layout/style/nsStyleSet.cpp:434
1 	xul.dll 	nsStyleSet::AddImportantRules 	mozilla/layout/style/nsStyleSet.cpp:434
2 	xul.dll 	nsStyleSet::AddImportantRules 	mozilla/layout/style/nsStyleSet.cpp:434
3 	xul.dll 	nsStyleSet::AddImportantRules 	mozilla/layout/style/nsStyleSet.cpp:434
4 	xul.dll 	nsStyleSet::AddImportantRules 	mozilla/layout/style/nsStyleSet.cpp:434
5 	xul.dll 	nsStyleSet::AddImportantRules 	mozilla/layout/style/nsStyleSet.cpp:434

Comment 7

[Régis Caspar]

Thanks Matthias, I forgot to change the component :/ sorry.
Adding the reporter testcase in URL (one single HTML file ~1Mo).

Comment 8

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 1: make AddImportantRules, etc., use iteration and its own stack

needs more tests

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 2: remove nsRuleList

patch 3 is not written yet (it will use a destroy queue to destroy rule nodes)

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 4: test for this bug

Comment 11

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 3: use a queue to destroy rule node children

Comment 12

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch 1: make AddImportantRules, etc., use iteration and its own stack

with test for cascading added

Comment 13

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 325113 [details] [diff] [review]
patch 4: test for this bug

This test is pretty slow; not sure if there's anything we ought to do about that.  I think I do want to test a bit more than currently causes the bug.

Comment 14

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

For a quick overview:  the case of a very large number of rules matching the same element triggered stack overflows in two different ways:

 patch 1 fixes the one in AddImportantRules

 patch 3 fixes the one in rule node destruction

 patch 2 is preparatory cleanup for patch 3, and patch 4 is a test for this bug

Comment 15

[fantasai]

Comment on attachment 325334 [details] [diff] [review]
patch 1: make AddImportantRules, etc., use iteration and its own stack

I don't really understand why the zIndex keeps being incremented in your tests rather than just using two fixed numbers. But it looks correct. r=fantasai on code and tests if you document your do_test function (state what it does, what each argument means, and what values are valid)

Comment 16

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 325334 [details] [diff] [review]
patch 1: make AddImportantRules, etc., use iteration and its own stack

> nsStyleSet::AddImportantRules(nsRuleNode* aCurrLevelNode,
>                               nsRuleNode* aLastPrevLevelNode)

The changes here seem OK, but do we want to use some sort of auto-array to avoid heap-allocation if there aren't too many important rules?

> nsStyleSet::AssertNoCSSRules(nsRuleNode* aCurrLevelNode,
>   if (!aCurrLevelNode || aCurrLevelNode == aLastPrevLevelNode)

The second check can go away just like in the other two functions, right?

I guess a crashtest for this would just be too big, right?

sr=bzbarsky

Comment 17

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 325112 [details] [diff] [review]
patch 2: remove nsRuleList

r+sr=bzbarsky

Comment 18

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 325113 [details] [diff] [review]
patch 4: test for this bug

Ah, here's the crashtest!  ;)

Comment 19

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 325143 [details] [diff] [review]
patch 3: use a queue to destroy rule node children

>+  // aDestroyQueueTail is for internal use only.
>+  NS_HIDDEN_(void) Destroy(nsRuleNode ***aDestroyQueueTail = nsnull);

Just create a private overload instead of trying to enforce hiding via comments?

Also, this fixes situations in which we have a bunch of rulenodes all of which have at least enough kids to hash and the depth is too deep, right?  Can we add a crashtest for this too?

r+sr=bzbarsky with those.

Comment 20

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to comment #19)
> (From update of attachment 325143 [details] [diff] [review])
> >+  // aDestroyQueueTail is for internal use only.
> >+  NS_HIDDEN_(void) Destroy(nsRuleNode ***aDestroyQueueTail = nsnull);
> 
> Just create a private overload instead of trying to enforce hiding via
> comments?

No need for an overload; I'll call the internal one DestroyInternal and drop the default param.  Good point, though.

> Also, this fixes situations in which we have a bunch of rulenodes all of which
> have at least enough kids to hash and the depth is too deep, right?  Can we add
> a crashtest for this too?

Let's see if this crashtest survives first; it's slow enough, and that one would be a few orders of magnitude slower (if we don't want to make too many assumptions about the switch-to-hash constant).

Comment 21

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I had to revert the crashtest because it was too slow, but the rest is landed:

http://hg.mozilla.org/mozilla-central/index.cgi/rev/a00c120d4a6e
http://hg.mozilla.org/mozilla-central/index.cgi/rev/5b6fa5bcaccd
http://hg.mozilla.org/mozilla-central/index.cgi/rev/571dbbcf60bf
http://hg.mozilla.org/mozilla-central/index.cgi/rev/6a513bc88338
http://hg.mozilla.org/mozilla-central/index.cgi/rev/4c0aae446b52

Comment 23

[Samuel Sidler (old account; do not CC)]

dbaron: Is this likely the same as these other crashes with the same top frame?

  bp-321475b0-a418-11dd-88cb-001cc45a2ce4
  bp-dc729691-a41a-11dd-8d7b-001321b13766
  bp-8706a799-a420-11dd-8427-001cc45a2c28
  bp-16860311-a446-11dd-b6e9-001cc45a2ce4
  bp-44f8b86e-a456-11dd-bcfc-001321b13766
  bp-102f5707-a46c-11dd-89dc-001a4bd43ed6

If so that would make this crash a 3.0.3 topcrash. Currently number 8. Can you see if your patch applies to 1.9.0 and requested approval1.9.0.5 on it?

Comment 24

[Daniel Veditz [:dveditz]]

Blocking on the assumption that this is, in fact, the fix for the topcrash.

Comment 25

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

This would not fix any of the crashes in comment 23.  This is a stack overflow.

Comment 26

[Samuel Sidler (old account; do not CC)]

Renominating based on comment 25.

Comment 27

[Samuel Sidler (old account; do not CC)]

For what it's worth, we've seen this stack a handful of times on the 1.9.0 branch. It might be worth fixing there, though I doubt it.

Comment 28

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Please reread comment 25 more carefully.

Comment 29

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I filed bug 466024 on that crash so you stop commenting here.

Comment 30

[Samuel Sidler (old account; do not CC)]

David, I've read comment 25 very carefully and filed bug 466021 prior to commenting here. Please re-read my comment 27 which says that I've seen a handful of *this* stack (a stack overflow) on the 1.9.0 branch.

Specifically:
  bp-6555beec-cb64-4459-84af-927e20081120
  bp-663220b0-d9bb-4bcc-8f86-cd4520081119

Comment 31

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Yep, sorry.