Bug 25703 – Stack overflow crash rendering element with mega-huge number of background layers

• Status: NEW
• Component: Layout and Rendering

[Jeff Walden (remove +bwo to email)]

Woohoo, I can crash WebKit, aren't I special.  Logging so it's on the radar but clearly not all that important to fix by yesterday given its esoteric nature...

[Mark Rowe (bdash)]

<rdar://problem/6877778>

[Hans Wennborg]

Created attachment 57315 [details]
Patch

[Hans Wennborg]

Uploaded patch that changes the functions that cause this stack overflow to be iterative instead of recursive.

[Jeremy Orlow]

Comment on attachment 57315 [details]
Patch

I'm not qualified to officially review this, but it seems fairly sound.  A couple nits though.


LayoutTests/css3/many-background-layers.html:12
 +        for (var i = 0; i < 100000; i++)
Nit: ++i
Nit: Maybe put 100000 in a constant and initialize that constant with 100*1000 to make it easier to read?

WebCore/rendering/RenderBox.cpp:765
 +      for (size_t i = layers.size(); i > 0; i--)
nit: --i

This isn't the most elegant code, but I don't have a better answer off the top of my head.

[Hans Wennborg]

(In reply to comment #4)
> (From update of attachment 57315 [details])
> I'm not qualified to officially review this, but it seems fairly sound.  A couple nits though.
> 
> 
> LayoutTests/css3/many-background-layers.html:12
>  +        for (var i = 0; i < 100000; i++)
> Nit: ++i
> Nit: Maybe put 100000 in a constant and initialize that constant with 100*1000 to make it easier to read?
Done.

> WebCore/rendering/RenderBox.cpp:765
>  +      for (size_t i = layers.size(); i > 0; i--)
> nit: --i
Done.

>
> This isn't the most elegant code, but I don't have a better answer off the top of my head.

[Hans Wennborg]

Created attachment 57333 [details]
Patch

[David Levin]

Comment on attachment 57333 [details]
Patch

WebKit uses 4 space indent.

Note when I made comments below, I often only pointed out one instance of the issue but it may occur in several places, so please check your code throughout for the same issue.


> diff --git a/WebCore/ChangeLog b/WebCore/ChangeLog
> +        Test: css3/many-background-layers.html
> +
> +        * rendering/RenderBox.cpp:
> +        (WebCore::RenderBox::paintFillLayers):

Note that this is where per function comments go.

> +        * rendering/style/FillLayer.h:
> +        (WebCore::FillLayer::hasImage):
> +        (WebCore::FillLayer::hasFixedImage):
> +
>  2010-05-27  Kwang Yul Seo  <[e-mail]>
>  
>          Reviewed by Darin Adler.

> diff --git a/WebCore/rendering/RenderBox.cpp b/WebCore/rendering/RenderBox.cpp
>  void RenderBox::paintFillLayers(const PaintInfo& paintInfo, const Color& c, const FillLayer* fillLayer, int tx, int ty, int width, int height, CompositeOperator op, RenderObject* backgroundObject)
>  {
> -    if (!fillLayer)
> -        return;
> +    WTF::Vector<const FillLayer*, 8> layers;

Why 8? (Ideally the ChangeLog would have a comment about this function and the magic number "8".)


> +    for (size_t i = layers.size(); i > 0; --i)
> +      paintFillLayer(paintInfo, c, layers[i-1], tx, ty, width, height, op, backgroundObject);

There should be spaces around operators: "layers[i - 1]"



> diff --git a/WebCore/rendering/style/FillLayer.h b/WebCore/rendering/style/FillLayer.h
>      bool hasImage() const
>      {
> -        if (m_image)
> +        for (const FillLayer *layer = this; layer; layer = layer->m_next)

This should have {} around the body (see http://webkit.org/coding/coding-style.html).

The * is in the wrong place (should be "FillLayer* layer").



Doesn't ~FillLayer have the same problem?

[Hans Wennborg]

(In reply to comment #7)
> (From update of attachment 57333 [details])
Thanks for the review.

> WebKit uses 4 space indent.
Done. Sorry about that.

> 
> Note when I made comments below, I often only pointed out one instance of the issue but it may occur in several places, so please check your code throughout for the same issue.
> 
> 
> > diff --git a/WebCore/ChangeLog b/WebCore/ChangeLog
> > +        Test: css3/many-background-layers.html
> > +
> > +        * rendering/RenderBox.cpp:
> > +        (WebCore::RenderBox::paintFillLayers):
> 
> Note that this is where per function comments go.
Added. Are these mandatory, or is it more for things that really need commenting, such as the magic number 8 below?

> 
> > +        * rendering/style/FillLayer.h:
> > +        (WebCore::FillLayer::hasImage):
> > +        (WebCore::FillLayer::hasFixedImage):
> > +
> >  2010-05-27  Kwang Yul Seo  <[e-mail]>
> >  
> >          Reviewed by Darin Adler.
> 
> > diff --git a/WebCore/rendering/RenderBox.cpp b/WebCore/rendering/RenderBox.cpp
> >  void RenderBox::paintFillLayers(const PaintInfo& paintInfo, const Color& c, const FillLayer* fillLayer, int tx, int ty, int width, int height, CompositeOperator op, RenderObject* backgroundObject)
> >  {
> > -    if (!fillLayer)
> > -        return;
> > +    WTF::Vector<const FillLayer*, 8> layers;
> 
> Why 8? (Ideally the ChangeLog would have a comment about this function and the magic number "8".)
Added comment in the ChangeLog about this.

> 
> 
> > +    for (size_t i = layers.size(); i > 0; --i)
> > +      paintFillLayer(paintInfo, c, layers[i-1], tx, ty, width, height, op, backgroundObject);
> 
> There should be spaces around operators: "layers[i - 1]"
Done.

> 
> 
> > diff --git a/WebCore/rendering/style/FillLayer.h b/WebCore/rendering/style/FillLayer.h
> >      bool hasImage() const
> >      {
> > -        if (m_image)
> > +        for (const FillLayer *layer = this; layer; layer = layer->m_next)
> 
> This should have {} around the body (see http://webkit.org/coding/coding-style.html).
Done.

> The * is in the wrong place (should be "FillLayer* layer").
Done.

> 
> Doesn't ~FillLayer have the same problem?
Yes it does; thanks for spotting it. I also found that the FillLayer copy constructor, equality operator and containsImage() share the problem. Those are now fixed, but I have to say that it takes away quite a bit of the elegance that the recursive versions had. Suggestions for nicer ways to implement it are very welcome.

[Hans Wennborg]

Created attachment 57648 [details]
Patch

[David Levin]

Comment on attachment 57648 [details]
Patch

Ok almost there!


---------------------------------
http://wkrietveld.appspot.com/25703/diff/1/2
File LayoutTests/ChangeLog (right):

http://wkrietveld.appspot.com/25703/diff/1/2#newcode5
LayoutTests/ChangeLog:5: Stack overflow crash rendering element with mega-huge number of background layers
"mega-huge" -- gianormous even?

How about "very large" (or even just put a number here like 100K)?

http://wkrietveld.appspot.com/25703/diff/1/2#newcode8
LayoutTests/ChangeLog:8: Adding layout test with huge number of background layers to make sure
a/huge number of/100k/

http://wkrietveld.appspot.com/25703/diff/1/2#newcode9
LayoutTests/ChangeLog:9: it does not cause stack overflow crash.
s/cause stack/cause a stack/

http://wkrietveld.appspot.com/25703/diff/1/4
File LayoutTests/css3/many-background-layers.html (right):

http://wkrietveld.appspot.com/25703/diff/1/4#newcode1
LayoutTests/css3/many-background-layers.html:1: <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
I think this test only verifies that RenderBox::paintFillLayers is correct (since that is all you fixed you you first had this test).

Is there any way to expand it to cover the other methods that you fixed?

http://wkrietveld.appspot.com/25703/diff/1/4#newcode4
LayoutTests/css3/many-background-layers.html:4: <title>Huge amout of background layers</title>
s/amout/amount/
I would use "number" here anyway.

http://wkrietveld.appspot.com/25703/diff/1/4#newcode21
LayoutTests/css3/many-background-layers.html:21: If you can read this, I have not crashed.
Something like
  "If this has not crashed, then the test passed."
would be more typical.

http://wkrietveld.appspot.com/25703/diff/1/5
File WebCore/ChangeLog (right):

http://wkrietveld.appspot.com/25703/diff/1/5#newcode8
WebCore/ChangeLog:8: Having a large amount of background layers triggered a stack overflow
s/amount/number/

http://wkrietveld.appspot.com/25703/diff/1/5#newcode15
WebCore/ChangeLog:15: (WebCore::RenderBox::paintFillLayers): Iterate, rather than recurse, over subsequent layers. Use WTF::Vector with inline capacity of 8 so that heap allocation is not needed unless the number of layers is high.
Typically lines are wrapped by hand in the ChangeLog (see other entries).

Also, I don't understand why 8 is considered high. Why not 4 or 16? (Should it be a constant defined in the file?)

Lastly, have you done any perf testing of this change?

http://wkrietveld.appspot.com/25703/diff/1/5#newcode18
WebCore/ChangeLog:18: (WebCore::FillLayer::~FillLayer): Remove recursion.
If you have the same comment as before, "Ditto." works.

http://wkrietveld.appspot.com/25703/diff/1/6
File WebCore/rendering/RenderBox.cpp (right):

http://wkrietveld.appspot.com/25703/diff/1/6#newcode761
WebCore/rendering/RenderBox.cpp:761: WTF::Vector<const FillLayer*, 8> layers;
The WTF prefix isn't needed (and is discouraged).

http://wkrietveld.appspot.com/25703/diff/1/7
File WebCore/rendering/style/FillLayer.cpp (right):

http://wkrietveld.appspot.com/25703/diff/1/7#newcode77
WebCore/rendering/style/FillLayer.cpp:77: if (!shallowCopy) {
Return quickly.

If (shallowCopy)
    return;

http://wkrietveld.appspot.com/25703/diff/1/7#newcode140
WebCore/rendering/style/FillLayer.cpp:140: // to propagate patterns into layers.  All layer comparisons happen after values have all been filled in anyway.
I know it was this way before but a single space after a period is preferred.

http://wkrietveld.appspot.com/25703/diff/1/7#newcode156
WebCore/rendering/style/FillLayer.cpp:156: if (thisLayer->m_next && otherLayer->m_next) {
Consider returning early.

if (!thisLayer->m_next || !otherLayer->m_next)
    return thisLayer->m_next == otherLayer->m_next;

thisLayer = thisLayer->m_next;
otherLayer = otherLayer->m_next;

http://wkrietveld.appspot.com/25703/diff/1/8
File WebCore/rendering/style/FillLayer.h (right):

http://wkrietveld.appspot.com/25703/diff/1/8#newcode121
WebCore/rendering/style/FillLayer.h:121: FillLayer(const FillLayer& o, bool shallowCopy = false);
This extra bool parameter bothers me but after considering several other possibilities, I guess it is ok.

Normally, for bool parameters, we'd like to change them to be enums but it is only set from within the constructor.

Also I considered removing it and just calling the empty constructor with copying everything manually and not setting it using the initialize syntax but that didn't seem as elegant and likely had other minor side effects (like m_image getting initialized to 0 and then to another value.

So in the end... ok.

[Hans Wennborg]

(In reply to comment #10)
> (From update of attachment 57648 [details])
> Ok almost there!
Thank you for the thorough review.

> 
> 
> ---------------------------------
> http://wkrietveld.appspot.com/25703/diff/1/2
> File LayoutTests/ChangeLog (right):
> 
> http://wkrietveld.appspot.com/25703/diff/1/2#newcode5
> LayoutTests/ChangeLog:5: Stack overflow crash rendering element with mega-huge number of background layers
> "mega-huge" -- gianormous even?
> 
> How about "very large" (or even just put a number here like 100K)?
Done.

> 
> http://wkrietveld.appspot.com/25703/diff/1/2#newcode8
> LayoutTests/ChangeLog:8: Adding layout test with huge number of background layers to make sure
> a/huge number of/100k/
Going for "very large" here as well.

> 
> http://wkrietveld.appspot.com/25703/diff/1/2#newcode9
> LayoutTests/ChangeLog:9: it does not cause stack overflow crash.
> s/cause stack/cause a stack/
Done.

> 
> http://wkrietveld.appspot.com/25703/diff/1/4
> File LayoutTests/css3/many-background-layers.html (right):
> 
> http://wkrietveld.appspot.com/25703/diff/1/4#newcode1
> LayoutTests/css3/many-background-layers.html:1: <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
> I think this test only verifies that RenderBox::paintFillLayers is correct (since that is all you fixed you you first had this test).
> 
> Is there any way to expand it to cover the other methods that you fixed?
I have tried this, but it is not straight-forward, at least not the way the test works now. The problem is that for example ~FillLayer() requires a higher number of layers to crash (350k on my machine), making the layout test impractical to have in the test suite. I am not sure how much trouble it is worth to have automatic tests for them.

> 
> http://wkrietveld.appspot.com/25703/diff/1/4#newcode4
> LayoutTests/css3/many-background-layers.html:4: <title>Huge amout of background layers</title>
> s/amout/amount/
> I would use "number" here anyway.
Done.

> 
> http://wkrietveld.appspot.com/25703/diff/1/4#newcode21
> LayoutTests/css3/many-background-layers.html:21: If you can read this, I have not crashed.
> Something like
>   "If this has not crashed, then the test passed."
> would be more typical.
Done.

> 
> http://wkrietveld.appspot.com/25703/diff/1/5
> File WebCore/ChangeLog (right):
> 
> http://wkrietveld.appspot.com/25703/diff/1/5#newcode8
> WebCore/ChangeLog:8: Having a large amount of background layers triggered a stack overflow
> s/amount/number/
Done.

> 
> http://wkrietveld.appspot.com/25703/diff/1/5#newcode15
> WebCore/ChangeLog:15: (WebCore::RenderBox::paintFillLayers): Iterate, rather than recurse, over subsequent layers. Use WTF::Vector with inline capacity of 8 so that heap allocation is not needed unless the number of layers is high.
> Typically lines are wrapped by hand in the ChangeLog (see other entries).
Done.

> 
> Also, I don't understand why 8 is considered high. Why not 4 or 16? (Should it be a constant defined in the file?)
I have done some experiments using the Chrome page cycler tests and the layout tests. I hit this function about 120k times. Nine layers occurred once, four layers about 20 times, two layers about 60 times, and the rest of the time the number of layers was one. So I believe 8 is high enough to accommodate all common cases. Changing the ChangeLog text slightly to make it more clear, and also added a comment about this to the source.

> 
> Lastly, have you done any perf testing of this change?
Running the Chrome page cyclers, I have not been able to detect any change in performance with this patch.

> 
> http://wkrietveld.appspot.com/25703/diff/1/5#newcode18
> WebCore/ChangeLog:18: (WebCore::FillLayer::~FillLayer): Remove recursion.
> If you have the same comment as before, "Ditto." works.
Done.

> 
> http://wkrietveld.appspot.com/25703/diff/1/6
> File WebCore/rendering/RenderBox.cpp (right):
> 
> http://wkrietveld.appspot.com/25703/diff/1/6#newcode761
> WebCore/rendering/RenderBox.cpp:761: WTF::Vector<const FillLayer*, 8> layers;
> The WTF prefix isn't needed (and is discouraged).
Done.

> 
> http://wkrietveld.appspot.com/25703/diff/1/7
> File WebCore/rendering/style/FillLayer.cpp (right):
> 
> http://wkrietveld.appspot.com/25703/diff/1/7#newcode77
> WebCore/rendering/style/FillLayer.cpp:77: if (!shallowCopy) {
> Return quickly.
> 
> If (shallowCopy)
>     return;
Done.

> 
> http://wkrietveld.appspot.com/25703/diff/1/7#newcode140
> WebCore/rendering/style/FillLayer.cpp:140: // to propagate patterns into layers.  All layer comparisons happen after values have all been filled in anyway.
> I know it was this way before but a single space after a period is preferred.
Done.

> 
> http://wkrietveld.appspot.com/25703/diff/1/7#newcode156
> WebCore/rendering/style/FillLayer.cpp:156: if (thisLayer->m_next && otherLayer->m_next) {
> Consider returning early.
> 
> if (!thisLayer->m_next || !otherLayer->m_next)
>     return thisLayer->m_next == otherLayer->m_next;
> 
> thisLayer = thisLayer->m_next;
> otherLayer = otherLayer->m_next;
Done.

> 
> http://wkrietveld.appspot.com/25703/diff/1/8
> File WebCore/rendering/style/FillLayer.h (right):
> 
> http://wkrietveld.appspot.com/25703/diff/1/8#newcode121
> WebCore/rendering/style/FillLayer.h:121: FillLayer(const FillLayer& o, bool shallowCopy = false);
> This extra bool parameter bothers me but after considering several other possibilities, I guess it is ok.
> 
> Normally, for bool parameters, we'd like to change them to be enums but it is only set from within the constructor.
> 
> Also I considered removing it and just calling the empty constructor with copying everything manually and not setting it using the initialize syntax but that didn't seem as elegant and likely had other minor side effects (like m_image getting initialized to 0 and then to another value.
> 
> So in the end... ok.
Ok.

[Hans Wennborg]

Created attachment 59116 [details]
Patch

[Adam Barth]

Comment on attachment 59116 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=59116&action=review

R- for readability.

> WebCore/rendering/RenderBox.cpp:761
> +    Vector<const FillLayer*, 8> layers; // Situations with more than 8 layers are extremely rare.

Do we have data to support this claim?

> WebCore/rendering/style/FillLayer.cpp:53
> +FillLayer::FillLayer(const FillLayer& o, bool shallowCopy)

Please don't use "o" as a variable name.  It looks too much like 0.

> WebCore/rendering/style/FillLayer.cpp:81
> +    const FillLayer* otherLayer = &o;

Perhaps "otherLayer" is a better name for o.

> WebCore/rendering/style/FillLayer.cpp:84
> +        thisLayer->m_next = new FillLayer(*otherLayer->m_next, true);

passing explicit true/false is hard to read.  :(

> WebCore/rendering/style/FillLayer.cpp:96
> +        delete layer;

Perhaps this should be an OwnPtr ?  Manual new/delete is bad times.