Bug 41129 – CSSSelector: Avoid chaining tagHistory of CSSSelector, which causes stack overflow.

• Component: CSS
• Status: RESOLVED FIXED

[Hayato Ito]

Created attachment 59611 [details]
Deeply nested CSS Selector

Try the attached HTML, which contains deeply nested CSS Selector.

In this case, chaining destructor calls of WebCore::CSSSelector cause stack overflow.

[Hayato Ito]

Created attachment 59764 [details]
fix-crash-avoid-recursive-destructor

[Hayato Ito]

I could also fix WebCore::CSSSelector::specificity() function so that it is not recursive one, but I've left it as is because I cannot find a test case where such recursive specificity() function causes stack overflow.

It seems specificity() is only used when an element is matched with CSS Selector. Because WebKit seems to limit nested level of DOM elements, it is unlikely that recursive specificity() method causes stack overflow.

[Hayato Ito]

Otherwise, it might be just enough to set a limit of nested level for CSSSelector when parsing CSS selector.
I am not sure which is better one.

[Hayato Ito]

Created attachment 60013 [details]
fix-crash-by-settting-limit-selectors-chaining

[Hayato Ito]

I've posted another patch.
In this patch, we set the limit for the length of CSS selectors chaining in parsing phase.
I guess this approach is better than the previous approach.

[Shinichiro Hamaji]

Comment on attachment 60013 [details]
fix-crash-by-settting-limit-selectors-chaining

WebCore/css/CSSParser.cpp:5106
 +      const static int maxChainingLength = 2048;
Is this number OK even for embeded devices where stack would be smaller than PCs?

WebCore/css/CSSParser.cpp:5106
 +      const static int maxChainingLength = 2048;
We usually use "static const", not "const static"

[Hayato Ito]

Created attachment 60089 [details]
fix-crash-by-settting-limit-selectors-chaining-2

[Hayato Ito]

Thank you for the review.

(In reply to comment #6)
> (From update of attachment 60013 [details])
> WebCore/css/CSSParser.cpp:5106
>  +      const static int maxChainingLength = 2048;
> Is this number OK even for embeded devices where stack would be smaller than PCs?

I think 2048 is dangerous for such devices. I've changed the value from 2048 to 256, which is enough for authors of CSS and has less risk for stack overflow. I am not sure this is best value, but it might be okay.

> 
> WebCore/css/CSSParser.cpp:5106
>  +      const static int maxChainingLength = 2048;
> We usually use "static const", not "const static"

Done

[Hayato Ito]

Created attachment 60092 [details]
fix-crash-by-settting-limit-selectors-chaining-2-fix-typo

[Hayato Ito]

Hamaji-san,

Could you review the patch?

[Shinichiro Hamaji]

Comment on attachment 60092 [details]
fix-crash-by-settting-limit-selectors-chaining-2-fix-typo

WebCore/css/CSSParser.h:172
 +          CSSSelector* connectFloatingSelector(CSSSelector* ownerSelector, CSSSelector* sinkingSelector, CSSSelector::Relation);
Do we need to return a value?


WebCore/css/CSSParser.cpp:185
 +      deleteAllKeys(m_floatingSelectors);
I'm not sure, but now it seems we don't sink floating selectors, so all selectors will be deleted when a parser is destructed?

[Darin Adler]

The chain itself is OK. There's nothing wrong with a linked list.

What we need to fix this is to add an iterative algorithm for destroying the chain, not to eliminate it entirely. I think I did this already in one of my OwnPtr patches; can’t find it at the moment. We need code that to loops through the list releasing the next pointer before destroying the previous one.

[Hayato Ito]

Created attachment 61475 [details]
fix-crach-by-setting-limit-selectors-chaining-3

[Hayato Ito]

(In reply to comment #11)
> (From update of attachment 60092 [details])
> WebCore/css/CSSParser.h:172
>  +          CSSSelector* connectFloatingSelector(CSSSelector* ownerSelector, CSSSelector* sinkingSelector, CSSSelector::Relation);
> Do we need to return a value?

We don't need a return value. Done.

> 
> 
> WebCore/css/CSSParser.cpp:185
>  +      deleteAllKeys(m_floatingSelectors);
> I'm not sure, but now it seems we don't sink floating selectors, so all selectors will be deleted when a parser is destructed?

A sinkingSelector is actually 'sinked' implicitly by m_floatingSelectors.take(..) in the following line.

    int newChainingLength = m_floatingSelectors.get(ownerSelector) + m_floatingSelectors.take(sinkingSelector);

That line could be rewritten as follows if we explicitly sink a sinkingSelector:

    int newChainingLength = m_floatingSelectors.get(ownerSelector) + m_floatingSelectors.get(sinkingSelector);
    sinkFloatingSelector(sinkingSelector);

I think the former is better than the latter because we lookup the key in HashTable only once in the former.
I've added a comment to avoid confusiong a reader.

[Hayato Ito]

(In reply to comment #12)
> The chain itself is OK. There's nothing wrong with a linked list.
> 
> What we need to fix this is to add an iterative algorithm for destroying the chain, not to eliminate it entirely. I think I did this already in one of my OwnPtr patches; can’t find it at the moment. We need code that to loops through the list releasing the next pointer before destroying the previous one.

Hi Darin,
Thank you for the comment.

I actually tried to fix it to add an iterative algorithm for destroying the chain in the patch https://bugs.webkit.org/attachment.cgi?id=59764.

To be precise, it's destroying the tree, not the linked list.
Is this a proper way? If so, could you take a look at the patch?
Your OwnPrt patche affects the patch, doesn't it?

[Darin Adler]

(In reply to comment #15)
> Your OwnPrt patche affects the patch, doesn't it?

I’m not sure. I started the OwnPtr work a while back and had to work on other things since, so I’m not even sure where it is.

[Darin Adler]

I don’t fully understand the approach taken in the more recent patches. I’ve read it multiple times and I just don’t get it.

[Darin Adler]

Comment on attachment 59764 [details]
fix-crash-avoid-recursive-destructor

I think this patch takes the right basic approach.

> +    Deque<CSSSelector*> selectorsToBeDeleted;

1) Since the order of deletion does not matter, I would use a single local variable for the next selector to delete and only use the general purpose data structure in the unusual case where we have both m_tagHistory and m_simpleSelector.

2) We can keep the Deque a lot smaller by doing the null checking at append time instead of when the selector is taken out of the Deque.

1) Because the length of the chain is usually short, I think our WTF::Deque is not the right data structure. Our Deque implementation is not particularly efficient when the vector is short, as it almost always should be in these cases. Instead, I would use a Vector with a fixed capacity on the stack. This would use more memory in the case where there is a long chain, but would be considerably faster in the normal case, avoiding allocation altogether.

If you did all of these, then I think we'd end up with code like this, but consierably more efficient. One of the best ways to do this would be to make your own class:

    class SelectorDeque {
    public:
        bool isEmpty() const;
        PassOwnPtr<CSSSelector> takeFirst();
        void append(PassOwnPtr<CSSSelector>);
    };

We could then leave the code as is, except you could remove the null check on the result of takeFirst.

Please give it a try; I think this is the way to go!

[Darin Adler]

(In reply to comment #18)
>     class SelectorDeque {
>     public:
>         bool isEmpty() const;
>         PassOwnPtr<CSSSelector> takeFirst();
>         void append(PassOwnPtr<CSSSelector>);
>     };

Oops, but it would not be a Deque, so it should be named something more like SelectorBag.

[Darin Adler]

Here’s my cut at SelectorBag.

class SelectorBag : public Noncopyable {
public:
    bool isEmpty() const;
    PassOwnPtr<CSSSelector> takeAny();
    void append(PassOwnPtr<CSSSelector>);

private:
    SelectorBag();
    ~SelectorBag();

    OwnPtr<CSSSelector> m_oneSelector;
    Vector<CSSSelector*> m_overflowSelectors;
    size_t m_overflowSelectorIndex;
};

SelectorBag::SelectorBag()

inline bool SelectorBag::isEmpty() const
{
    return !m_oneSelector && m_overflowSelectorIndex < m_overflowSelectors.size();
}

inline PassOwnPtr<CSSSelector> SelectorBag::takeAny()
{
    ASSERT(!isEmpty());
    if (m_oneSelector)
        return m_oneSelector.release();
    return adoptPtr(m_overflowSelectors[m_overflowSelectorIndex++]);
}

inline void append(PassOwnPtr<CSSSelector> selector)
{
    if (!m_oneSelector) {
        m_oneSelector = selector;
        return;
    }

    if (m_overflowSelectorIndex == m_overflowSelectors.size())

}

[Darin Adler]

inline SelectorBag::SelectorBag()
    : m_overflowSelectorIndex(0)
{
}

inline SelectorBag::~SelectorBag()
{
    size_t size = m_overflowSelectors.size();
    for (size_t i = m_overflowSelectorIndex; i < size; ++i)
        delete m_overflowSelectors[i];
}

void append(PassOwnPtr<CSSSelector> selector)
{
    if (!m_oneSelector) {
        m_oneSelector = selector;
        return;
    }

    if (m_overflowSelectorIndex < m_overflowSelectors.size()) {
        m_overflowSelectors.append(selector.leakPtr());
        return;
    }

    m_overflowSelectorIndex = 0;
    m_overflowSelectors.resize(1);
    m_overflowSelectors[0] = selector.leakPtr();
}

Actually, should probably be Vector<CSSSelector*, 16> too.

Something like the above.

[Hayato Ito]

Created attachment 61775 [details]
iterative-delete

[Hayato Ito]

(In reply to comment #21)
> inline SelectorBag::SelectorBag()

Hi Darin,

Thank you for the review. I appreciate your help.

I have one question. To implement CSSSelectorBag as you suggested, using Vector as 'Stack' is better than using it like a 'Deque', isn't it?
Because order of delete doesn't matter, we don't have to use the Vector like a 'deque'.

I've posted a patch for the review. Could you review it?

[Hayato Ito]

Created attachment 61781 [details]
iterative-delete-2

[Darin Adler]

(In reply to comment #23)
> I have one question. To implement CSSSelectorBag as you suggested, using Vector as 'Stack' is better than using it like a 'Deque', isn't it?

Yes, you are right!

[Darin Adler]

Comment on attachment 61781 [details]
iterative-delete-2

Thanks, this looks like a good approach!

I’d like CSSSelectorBag to be entirely in the .cpp file. There's no need to have it exposed in the header since it's used only internally.

Typically compilers cope with inline functions best if they come before the use of those functions. Thus, the CSSSelectorBag implementation should be at the top of the file, before the CSSSelector destructor.

> +    if (m_hasRareData) {
> +        if (!m_data.m_rareData)
> +            return;
> +    } else if (!m_data.m_tagHistory)
> +        return;

Do we really need to optimize this case? I think the code should be quite fast without a special case and early exit.

> +        if (m_data.m_rareData->m_tagHistory)
> +            selectorsToBeDeleted.append(m_data.m_rareData->m_tagHistory.release());
> +        if (m_data.m_rareData->m_simpleSelector)
> +            selectorsToBeDeleted.append(m_data.m_rareData->m_simpleSelector.release());

I'd prefer to see the null check inside the append function instead of having a null check at each call site.

> +            selector->m_data.m_rareData = 0;

Why clear out this pointer? The selector is about to be deleted anyway.

> +            selector->m_data.m_tagHistory = 0;

Same comment here.

> +inline CSSSelectorBag::CSSSelectorBag()
> +        : m_oneSelector()
> +        , m_overflowSelectors() {}

There is no need to define and explicitly implement this constructor. The compiler will do this automatically and get it right as long as you don’t declare it.

> +inline CSSSelectorBag::~CSSSelectorBag()
> +{
> +    size_t size = m_overflowSelectors.size();
> +    for (size_t i = 0; i < size; ++i)
> +        delete m_overflowSelectors[i];
> +}

You can use the deleteAllValues function instead of writing the loop explicitly. The only reason I wrote the loop last time was that I was doing the Deque thing.

> +inline PassOwnPtr<CSSSelector> CSSSelectorBag::takeAny()
> +{
> +    ASSERT(!isEmpty());
> +    if (m_oneSelector)
> +        return m_oneSelector.release();
> +    OwnPtr<CSSSelector> selector = adoptPtr(m_overflowSelectors.last());
> +    m_overflowSelectors.removeLast();
> +    return selector.release();
> +}

I don't think the m_oneSelector optimization is needed now that you are using a stack. You can just rip out all the m_oneSelector code and rename m_overflowSelectors to m_selectors or m_vector or even m_stack.

[Hayato Ito]

Created attachment 62034 [details]
iterative-delete-3

[Hayato Ito]

Created attachment 62035 [details]
iterative-delete-4

[Hayato Ito]

Hi Darin,
Thank you for the review.

(In reply to comment #26)
> (From update of attachment 61781 [details])
> Thanks, this looks like a good approach!
> 
> I’d like CSSSelectorBag to be entirely in the .cpp file. There's no need to have it exposed in the header since it's used only internally.
> 
> Typically compilers cope with inline functions best if they come before the use of those functions. Thus, the CSSSelectorBag implementation should be at the top of the file, before the CSSSelector destructor.

Done. Thank you.
I'd like to use anonymous namespace to hide this class completely in linking, but it doesn't seem WebKit's convention requires such a hiding as far as I can see.
So I've just moved CSSSelectorBag entirely to .cpp. If there is a problem, let me know it.


> 
> > +    if (m_hasRareData) {
> > +        if (!m_data.m_rareData)
> > +            return;
> > +    } else if (!m_data.m_tagHistory)
> > +        return;
> 
> Do we really need to optimize this case? I think the code should be quite fast without a special case and early exit.

Though I am not sure that how much this early exit contributes the performance, let me explain the intension of this 'early exit'.
By this early exit, we can avoid creating CSSSelectorBag in most cases.
Suppose we have the chain of CSSSelectors, which has length of 10. If we exit early, we create CSSSelectorBag at once only when deleting the root of chain.
If we don't exit early, we have to create CSSSelectorBag 10 times. 9 out of 10 are unnecessary ones.


> 
> > +        if (m_data.m_rareData->m_tagHistory)
> > +            selectorsToBeDeleted.append(m_data.m_rareData->m_tagHistory.release());
> > +        if (m_data.m_rareData->m_simpleSelector)
> > +            selectorsToBeDeleted.append(m_data.m_rareData->m_simpleSelector.release());
> 
> I'd prefer to see the null check inside the append function instead of having a null check at each call site.

Done. Thank you.

> 
> > +            selector->m_data.m_rareData = 0;
> 
> Why clear out this pointer? The selector is about to be deleted anyway.
> 
> > +            selector->m_data.m_tagHistory = 0;
> 
> Same comment here.

We need to clear out the pointer. Clearing it out acts as a 'flag' which means we already put the children of that selector in the 'queue', which is required to avoid recursion. If we don't clear it out, we have some problems. Let me explain. Suppose that we omit clearing m_data.m_rareData out here, 

           delete selector->m_data.m_rareData;
           // Comment out... selector->m_data.m_rareData = 0;

In this case, when a destructor will be called for that selector, the selector's m_data.m_rareData was already deleted, but m_data.m_radeData has a non-null value. As a result, we'll refer the selector's m_data.m_radeData wrongly in deleting that selector.

           // We refer the selector's m_data.m_rareData, which is already deleted.
           selectorsToBeDeleted.append(m_data.m_rareData->m_tagHistory.release()); 


> 
> > +inline CSSSelectorBag::CSSSelectorBag()
> > +        : m_oneSelector()
> > +        , m_overflowSelectors() {}
> 
> There is no need to define and explicitly implement this constructor. The compiler will do this automatically and get it right as long as you don’t declare it.

Done. Thank you.

> 
> > +inline CSSSelectorBag::~CSSSelectorBag()
> > +{
> > +    size_t size = m_overflowSelectors.size();
> > +    for (size_t i = 0; i < size; ++i)
> > +        delete m_overflowSelectors[i];
> > +}
> 
> You can use the deleteAllValues function instead of writing the loop explicitly. The only reason I wrote the loop last time was that I was doing the Deque thing.

Done. That is just what I was looking for!

> 
> > +inline PassOwnPtr<CSSSelector> CSSSelectorBag::takeAny()
> > +{
> > +    ASSERT(!isEmpty());
> > +    if (m_oneSelector)
> > +        return m_oneSelector.release();
> > +    OwnPtr<CSSSelector> selector = adoptPtr(m_overflowSelectors.last());
> > +    m_overflowSelectors.removeLast();
> > +    return selector.release();
> > +}
> 
> I don't think the m_oneSelector optimization is needed now that you are using a stack. You can just rip out all the m_oneSelector code and rename m_overflowSelectors to m_selectors or m_vector or even m_stack.

Done.
In fact, I've tried to remove m_oneSelector before sending a patch, but I wonder this optimization might still work. So I left it as is.
Now, I totally agree the we don't need it anymore. Thank you!

[Darin Adler]

Comment on attachment 62035 [details]
iterative-delete-4

I don't think CSSSelectorBag needs a comment. The fact that it's a helper class and the fact that it holds CSS selectors are both things that are clear from the context without a comment.

> +    void append(PassOwnPtr<CSSSelector> selector)

Should probably be named add instead of append.

> +    // We should avoid a recursive destructor call, which causes stack overflow
> +    // if CSS Selectors are deeply nested.

I would just say "selectors" here in this comment instead of "CSS Selectors".

> +    // Early exit if we have already processed the children of this selector.
> +    if (m_hasRareData) {
> +        if (!m_data.m_rareData)
> +            return;
> +    } else if (!m_data.m_tagHistory)
> +        return;

I think it would be slightly better to inline this part of the destructor. Then we could have a separate function named deleteChildren for the rest of the destruction process. That would be more like the old code, in fact, which did have the destructor compiled inline.

> +    if (m_hasRareData) {
> +        selectorsToBeDeleted.append(m_data.m_rareData->m_tagHistory.release());
> +        selectorsToBeDeleted.append(m_data.m_rareData->m_simpleSelector.release());
> +        delete m_data.m_rareData;
> +    } else
> +        selectorsToBeDeleted.append(adoptPtr(m_data.m_tagHistory));

The only difference between this and the code in the body of the loop is that in the loop we need to zero out the fields. It might be better to have a helper function that takes a bag and a selector to do this work, so we don't have to repeat this logic once outside the loop and once inside. We can inline the function if we like. The only cost to using such a function is that the zeroing would either have to be repeated, or be done separately outside the function.

> +    // FIXME: Avoid recursive calls to prevent possible stack overflow.
>      if (CSSSelector* tagHistory = this->tagHistory())
>          s += tagHistory->specificity();

Are you going to tackle this next? Is there a way to construct a regression test that shows the problem?

r=me as is -- The comments above give some possible future improvements.

[WebKit Commit Bot]

Comment on attachment 62035 [details]
iterative-delete-4

Clearing flags on attachment: 62035

Committed r63747: <http://trac.webkit.org/changeset/63747>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Hayato Ito]

Thank you for the review and landing it.

Let me try to address your comments here: https://bugs.webkit.org/show_bug.cgi?id=42726
I don't think it is difficult.

As for specifity() function, I couldn't construct a regression test when I tried to do it before. But I'll try it later and file a bug. Thank you.

(In reply to comment #30)
> (From update of attachment 62035 [details])
> I don't think CSSSelectorBag needs a comment. The fact that it's a helper class and the fact that it holds CSS selectors are both things that are clear from the context without a comment.
> 
> > +    void append(PassOwnPtr<CSSSelector> selector)
> 
> Should probably be named add instead of append.
> 
> > +    // We should avoid a recursive destructor call, which causes stack overflow
> > +    // if CSS Selectors are deeply nested.
> 
> I would just say "selectors" here in this comment instead of "CSS Selectors".
> 
> > +    // Early exit if we have already processed the children of this selector.
> > +    if (m_hasRareData) {
> > +        if (!m_data.m_rareData)
> > +            return;
> > +    } else if (!m_data.m_tagHistory)
> > +        return;
> 
> I think it would be slightly better to inline this part of the destructor. Then we could have a separate function named deleteChildren for the rest of the destruction process. That would be more like the old code, in fact, which did have the destructor compiled inline.
> 
> > +    if (m_hasRareData) {
> > +        selectorsToBeDeleted.append(m_data.m_rareData->m_tagHistory.release());
> > +        selectorsToBeDeleted.append(m_data.m_rareData->m_simpleSelector.release());
> > +        delete m_data.m_rareData;
> > +    } else
> > +        selectorsToBeDeleted.append(adoptPtr(m_data.m_tagHistory));
> 
> The only difference between this and the code in the body of the loop is that in the loop we need to zero out the fields. It might be better to have a helper function that takes a bag and a selector to do this work, so we don't have to repeat this logic once outside the loop and once inside. We can inline the function if we like. The only cost to using such a function is that the zeroing would either have to be repeated, or be done separately outside the function.
> 
> > +    // FIXME: Avoid recursive calls to prevent possible stack overflow.
> >      if (CSSSelector* tagHistory = this->tagHistory())
> >          s += tagHistory->specificity();
> 
> Are you going to tackle this next? Is there a way to construct a regression test that shows the problem?
> 
> r=me as is -- The comments above give some possible future improvements.