Bug 83405 – REGRESSION(r105057): Infinite loop inside SVGTextLayoutEngine::currentLogicalCharacterMetrics

• Component: SVG
• Status: RESOLVED FIXED

[Tim Horton]

Created attachment 136076 [details]
repro

Using the attached testcase, hover over one of the points in the graph. WebKit spins inside SVGTextLayoutEngine::currentLogicalCharacterMetrics, forever.

<rdar://problem/10853526>

I'll attach a sample momentarily. I believe this is a regression from Niko's text engine rework, but I have to re-determine which of the couple of patches broke this.

[Tim Horton]

Created attachment 136078 [details]
sample

[Tim Horton]

Here's the spin, if this makes it blindingly obvious what's wrong. It's hard to reduce because of highcharts being so complicated.

Start here:

bool SVGTextLayoutEngine::currentLogicalCharacterMetrics(SVGTextLayoutAttributes*& logicalAttributes, SVGTextMetrics& logicalMetrics)
{
    Vector<SVGTextMetrics>* textMetricsValues = &logicalAttributes->textMetricsValues();
    unsigned textMetricsSize = textMetricsValues->size();
    while (true) {
        if (m_logicalMetricsListOffset /* 0 */ == textMetricsSize /* 0 */) {
            if (!currentLogicalCharacterAttributes(logicalAttributes)) /* jump below; always returns true */
                return false;

            textMetricsValues = &logicalAttributes->textMetricsValues() /* this never changes */;
            textMetricsSize = textMetricsValues->size() /* 0 */;
            continue;
        }
        ...
    }
    ...
}

bool SVGTextLayoutEngine::currentLogicalCharacterAttributes(SVGTextLayoutAttributes*& logicalAttributes)
{
    if (m_layoutAttributesPosition /* 0 */ == m_layoutAttributes.size() /* 4 */)
        return false;

    logicalAttributes = m_layoutAttributes[m_layoutAttributesPosition]; /* m_layoutAttributesPosition never changes so this is always the same */

    if (m_logicalCharacterOffset /* 0 */ != logicalAttributes->context()->textLength() /* 1 */)
        return true;

    ...
}

[Stephen Chenney]

*** Bug 83479 has been marked as a duplicate of this bug. ***

[Nikolas Zimmermann]

I have a new reduction without high charts usage (took me a day to reduce this!).
Patch coming today.

[Nikolas Zimmermann]

Created attachment 140752 [details]
Patch

[Stephen Chenney]

Comment on attachment 140752 [details]
Patch

Always good when the person that wrote the code comes back to fix the code. :-) Much better than our piecemeal fixes. Could you please make sure that there are no Skipped tests from previous security patches in this code (changes from Philip or myself)? I want to be sure that we do have maximal test coverage.

FWIW, I would r+ this but I am not allowed.

[Darin Adler]

Comment on attachment 140752 [details]
Patch

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

> Source/WebCore/rendering/svg/RenderSVGInlineText.cpp:86
> +    textRenderer->subtreeChildWasDestroyed(this, affectedAttributes);

This function doesn’t seem to be named right. As I understand it, at this point, the subtreeChild was not yet destroyed. It won’t be destroyed until after we return.

> Source/WebCore/rendering/svg/RenderSVGText.cpp:122
> +static inline void recursiveUpdateMetrics(RenderObject* start, SVGTextLayoutAttributesBuilder& builder)
> +{
> +    if (start->isSVGInlineText()) {
> +        builder.rebuildMetricsForTextRenderer(toRenderSVGInlineText(start));
> +        return;
> +    }
> +
> +    for (RenderObject* child = start->firstChild(); child; child = child->nextSibling())
> +        recursiveUpdateMetrics(child, builder);
> +}

There is no need to write a function like this recursively. It can be written iteratively using the nextInPreOrder and nextInPreOrderAfterChildren functions.

> Source/WebCore/rendering/svg/RenderSVGText.cpp:204
> +    unsigned position = m_layoutAttributes.find(currentLayoutAttributes);

This should be size_t, not unsigned.

> Source/WebCore/rendering/svg/RenderSVGText.cpp:205
> +    ASSERT(position != notFound);

This assertion will never fire on a 64-bit system because position is a 32-bit unsigned and notFound is a 64-bit size_t constant.

> Source/WebCore/rendering/svg/RenderSVGText.cpp:221
> +static inline void recursiveCollectLayoutAttributes(RenderObject* start, Vector<SVGTextLayoutAttributes*>& attributes)
> +{
> +    for (RenderObject* child = start->firstChild(); child; child = child->nextSibling()) {
> +        if (child->isSVGInlineText()) {
> +            attributes.append(toRenderSVGInlineText(child)->layoutAttributes());
> +            continue;
> +        }
> +
> +        recursiveCollectLayoutAttributes(child, attributes);
> +    }
> +}

Same comment about the fact that this can be written non-recursively easily using nextInPreOrder.

> Source/WebCore/rendering/svg/RenderSVGText.cpp:242
> +    unsigned size = affectedAttributes.size();

Should be size_t.

[Rob Buis]

It looks ok to me, I think the tests should have a line describing what it does specifically.

[Nikolas Zimmermann]

(In reply to comment #7)
> > Source/WebCore/rendering/svg/RenderSVGInlineText.cpp:86
> > +    textRenderer->subtreeChildWasDestroyed(this, affectedAttributes);
> 
> This function doesn’t seem to be named right. As I understand it, at this point, the subtreeChild was not yet destroyed. It won’t be destroyed until after we return.
No that's not correct. There are both subtreeChildWillBeDestroyed, and subtreeChildWasDestroyed.
RenderSVGInlineText::willBeDestroyed, uses it like this:
    Vector<SVGTextLayoutAttributes*> affectedAttributes;
    textRenderer->subtreeChildWillBeDestroyed(this, affectedAttributes);
    RenderText::willBeDestroyed();
    textRenderer->subtreeChildWasDestroyed(this, affectedAttributes);

Once subtreeChildWasDestroyed() is called, the RenderSVGInlineText is no longer part of the tree.
I could name it subtreeChildRemovedFromTree, but I thought it would be more consistent this way.
If you still have concerns with it, I can fix it in a follow-up patch.


> > +static inline void recursiveUpdateMetrics(RenderObject* start, SVGTextLayoutAttributesBuilder& builder)
> There is no need to write a function like this recursively. It can be written iteratively using the nextInPreOrder and nextInPreOrderAfterChildren functions.
Excellent suggestion! I'm used to this recursive idiom since ages, I forgot that there are iterative ways to achieve the same goal. Going to play with that now, to avoid all the recursiveCollect/recursiveUpdate... methods.
 
> > Source/WebCore/rendering/svg/RenderSVGText.cpp:204
> > +    unsigned position = m_layoutAttributes.find(currentLayoutAttributes);
> 
> This should be size_t, not unsigned.
Good catch!

> 
> > Source/WebCore/rendering/svg/RenderSVGText.cpp:205
> > +    ASSERT(position != notFound);
> 
> This assertion will never fire on a 64-bit system because position is a 32-bit unsigned and notFound is a 64-bit size_t constant.
Yickes! I just checked the rest of the SVG code for this, and fortunately the existing code is correct, and always compares the result of finds() with size_t's. Glad you spotted this one.

> 
> > Source/WebCore/rendering/svg/RenderSVGText.cpp:221
> Same comment about the fact that this can be written non-recursively easily using nextInPreOrder.
Fixing.

> > Source/WebCore/rendering/svg/RenderSVGText.cpp:242
> > +    unsigned size = affectedAttributes.size();
> 
> Should be size_t.
You're saying this should be size_t. Last time I've heard that all of WTF/ is going to move to unsigned, and we shouldn't use size_t anymore. I used to store the result of size() in size_t's until I was told to stop that.
Can't remember who said that though and on which bug report, but I can look it up.

I'll fix for this for now as well.

(In reply to comment #8)
> It looks ok to me, I think the tests should have a line describing what it does specifically.
Done.

[Nikolas Zimmermann]

I've included all fixes Darin & Rob asked for - landing now.

[Nikolas Zimmermann]

Committed r116498: <http://trac.webkit.org/changeset/116498>

[Darin Adler]

(In reply to comment #9)
>     Vector<SVGTextLayoutAttributes*> affectedAttributes;
>     textRenderer->subtreeChildWillBeDestroyed(this, affectedAttributes);
>     RenderText::willBeDestroyed();
>     textRenderer->subtreeChildWasDestroyed(this, affectedAttributes);

Let me reiterate for later fixing: The names here are not good. At no point is this code calling a function named “destroy” and yet somehow right after calling a “will be destroyed” it’s correct to call “was destroyed”. Given this, one of the names is wrong. I don’t know which is wrong. Either the “will be destroyed” function does destruction despite its name or the “was destroyed” function is called before destruction despite its name.

> If you still have concerns with it, I can fix it in a follow-up patch.

I do have concerns about these names. We should figure out which name is misleading.

> Can't remember who said that though and on which bug report, but I can look it up.

Please do find that. I’d like to learn more about the plan and weigh in on a good way to do the transition.

I agree that we may, at this point, be using 64-bit integers in many places where 32-bit integers would suffice. A new approach would be OK with me, but this has to be done carefully to avoid introducing bugs like buffer overflows.

[WebKit Review Bot]

Re-opened since this is blocked by 86251

[Stephen Chenney]

This patch was rolled out in r116801: <http://trac.webkit.org/changeset/116801>

See https://bugs.webkit.org/show_bug.cgi?id=86251

[Nikolas Zimmermann]

I've reworked this patch, fixing the security problems it introduced and Darins comments regarding subtreeChildWillBeDestroyed/WasDestroyed. I'm no longer relying on willBeDestroyed(), but instead listen for removeChild() calls, handling the layout attributes updating much earlier.

[Nikolas Zimmermann]

Created attachment 141956 [details]
Patch v2

[Nikolas Zimmermann]

Comment on attachment 141956 [details]
Patch v2

Oops, Patch v2 doesn't contain the new high charts testcase, reuploading in a minute.

[Nikolas Zimmermann]

Created attachment 141967 [details]
Patch v3

[Build Bot]

Comment on attachment 141967 [details]
Patch v3

Attachment 141967 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/12685788

[Nikolas Zimmermann]

Created attachment 141980 [details]
Patch v4

[Nikolas Zimmermann]

Patch v4 will fix release builds as well.

[Rob Buis]

Comment on attachment 141980 [details]
Patch v4

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

Tests look good. Some minor points to fix.

> Source/WebCore/ChangeLog:10
> +        the managment of all caches (text positioning element cache / metrics map / layout attributes) in

Typo: management.

> Source/WebCore/rendering/svg/RenderSVGBlock.h:38
> +    virtual void willBeDestroyed();

Better use OVERRIDE.

> Source/WebCore/rendering/svg/RenderSVGText.cpp:203
> +#ifndef  NDEBUG

Two spaces.

> Source/WebCore/rendering/svg/RenderSVGText.cpp:204
> +    // Verify that m_layoutAttributes only differs by maxium one entry.

Typo: maximum

> Source/WebCore/rendering/svg/RenderSVGText.cpp:214
> +#ifndef NDEBUG

Could the method be debug-only?

> Source/WebCore/rendering/svg/RenderSVGText.cpp:293
> +        ASSERT(!m_layoutAttributesBuilder.numberOfTextPositioningElements());

We are doing this a lot, a helper method possible?

> Source/WebCore/rendering/svg/RenderSVGText.cpp:376
> +        // If the root layout size changed (eg. window size changes) or or the transform to the root

or or? :)

[Nikolas Zimmermann]

(In reply to comment #22)
> (From update of attachment 141980 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=141980&action=review
> 
> Tests look good. Some minor points to fix.
Thanks, fixed all typos.

> Could the method be debug-only?
I'd need to guard all call-sites with #ifndef NDEBUG then, I'd rather let the compiler optimize away the empty inline function call in release builds.

> > Source/WebCore/rendering/svg/RenderSVGText.cpp:293
> > +        ASSERT(!m_layoutAttributesBuilder.numberOfTextPositioningElements());
> 
> We are doing this a lot, a helper method possible?
Good idea, will do that.

[Nikolas Zimmermann]

Created attachment 141986 [details]
Patch v5

[Nikolas Zimmermann]

I'd like to hear both Darins & Stephens okay on this before landing :-)

[Rob Buis]

Comment on attachment 141986 [details]
Patch v5

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

This looks pretty good to me. I'll wait for comments from others though.

> Source/WebCore/rendering/svg/RenderSVGText.h:80
> +    virtual void removeChild(RenderObject*);

I think this needs OVERRIDE? Please check others as well.

> Source/WebCore/rendering/svg/RenderSVGText.h:93
> +    bool shallHandleSubtreeMutations() const;

shall sounds a bit strange. How about canHandleSubtreeMutations()?

> Source/WebCore/rendering/svg/SVGTextLayoutAttributesBuilder.cpp:-30
> -#define DUMP_TEXT_LAYOUT_ATTRIBUTES 0

Isn't this a helpful debug tool anymore?

> Source/WebCore/rendering/svg/SVGTextLayoutAttributesBuilder.h:46
> +    bool buildLayoutAttributesForWholeTree(RenderSVGText*);

I am not sure about WholeTree in the name, can it be improved?

[Darin Adler]

Comment on attachment 141986 [details]
Patch v5

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

A lot to review here, but it all looks good to me. r=me

> Source/WebCore/rendering/svg/RenderSVGInline.cpp:136
> +    RenderSVGText* textRenderer = RenderSVGText::locateRenderSVGTextAncestor(this);
> +    if (!child->isSVGInlineText() || !textRenderer) {
> +        RenderInline::removeChild(child);
> +        return;
> +    }

Seems a shame to call RenderSVGText::locateRenderSVGTextAncestor when !child->isSVGInlineText(). I suggest restructuring the code so we don’t do that. One way is to write this:

    RenderSVGText* textRenderer = child->isSVGInlineText() ? RenderSVGText::locateRenderSVGTextAncestor(this) : 0;
    if (!textRenderer)

But there may also be a clean way to write it.

> Source/WebCore/rendering/svg/RenderSVGInline.h:62
> +    virtual void removeChild(RenderObject*);

Please add OVERRIDE.

> Source/WebCore/rendering/svg/RenderSVGText.cpp:184
> +    if (newLayoutAttributes.isEmpty()) {
> +        m_layoutAttributes.clear();
> +        return;
> +    }

This special case does not seem more optimal than falling into the general case below. I suggest leaving it out unless there is something I am missing.

>> Source/WebCore/rendering/svg/RenderSVGText.h:80
>> +    virtual void removeChild(RenderObject*);
> 
> I think this needs OVERRIDE? Please check others as well.

Please add OVERRIDE.

> Source/WebCore/rendering/svg/RenderSVGText.h:81
> +    virtual void willBeDestroyed();

Please add OVERRIDE.

>> Source/WebCore/rendering/svg/RenderSVGText.h:93
>> +    bool shallHandleSubtreeMutations() const;
> 
> shall sounds a bit strange. How about canHandleSubtreeMutations()?

We normally use “should” for functions like this, and I think it would work fine here.

[Darin Adler]

Rob and I reviewed, but I see now that Stephen did not yet.

[Stephen Chenney]

Chromium issues to close when this lands:
http://code.google.com/p/chromium/issues/detail?id=127722
http://code.google.com/p/chromium/issues/detail?id=127679
http://code.google.com/p/chromium/issues/detail?id=127418

[Stephen Chenney]

Comment on attachment 141986 [details]
Patch v5

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

>> Source/WebCore/rendering/svg/RenderSVGInline.cpp:136
>> +    }
> 
> Seems a shame to call RenderSVGText::locateRenderSVGTextAncestor when !child->isSVGInlineText(). I suggest restructuring the code so we don’t do that. One way is to write this:
> 
>     RenderSVGText* textRenderer = child->isSVGInlineText() ? RenderSVGText::locateRenderSVGTextAncestor(this) : 0;
>     if (!textRenderer)
> 
> But there may also be a clean way to write it.

I'm with Darin on this.

> Source/WebCore/rendering/svg/RenderSVGText.cpp:172
> +        return;

It would be clearer to move documentBeingDestroyed() into shallHandleSubtreeMutations(), if we can. See comment below where this is used again.

>> Source/WebCore/rendering/svg/RenderSVGText.cpp:184
>> +    }
> 
> This special case does not seem more optimal than falling into the general case below. I suggest leaving it out unless there is something I am missing.

I also find this confusing. It seems like the logic is such that newLayoutAttributes can only be empty if the child is not inline text and there are no other children that are. Is that right? But then shouldn't you fall through as Darin suggests and then assert that m_layoutAttributes is already empty?

> Source/WebCore/rendering/svg/RenderSVGText.cpp:241
> +        return;

Could you explain why it is not necessary here to check documentBeingDestroyed? Why execute the next few lines before checking?

> Source/WebCore/rendering/svg/RenderSVGText.cpp:375
> +

Looks like this could be cleaned up to share code with updateFontInAllDescendents, which would make it clearer and make it easier to avoid future problems.

>>> Source/WebCore/rendering/svg/RenderSVGText.h:93
>>> +    bool shallHandleSubtreeMutations() const;
>> 
>> shall sounds a bit strange. How about canHandleSubtreeMutations()?
> 
> We normally use “should” for functions like this, and I think it would work fine here.

I'm with Darin.

>> Source/WebCore/rendering/svg/SVGTextLayoutAttributesBuilder.h:46
>> +    bool buildLayoutAttributesForWholeTree(RenderSVGText*);
> 
> I am not sure about WholeTree in the name, can it be improved?

buildLayoutAttributesForSubtree? That seems to be what it's doing.

[Rob Buis]

(In reply to comment #30)
> (From update of attachment 141986 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=141986&action=review
> 
> >> Source/WebCore/rendering/svg/SVGTextLayoutAttributesBuilder.h:46
> >> +    bool buildLayoutAttributesForWholeTree(RenderSVGText*);
> > 
> > I am not sure about WholeTree in the name, can it be improved?
> 
> buildLayoutAttributesForSubtree? That seems to be what it's doing.

That was my first thought as well, I would be ok with that name.

[Nikolas Zimmermann]

Thanks Rob, Darin & Stephen for your comments. Some comments regarding issues, that I did not fix:

> > Source/WebCore/rendering/svg/SVGTextLayoutAttributesBuilder.cpp:-30
> > -#define DUMP_TEXT_LAYOUT_ATTRIBUTES 0
> 
> Isn't this a helpful debug tool anymore?
While this might be useful, SVGCharacterData::dump() doesn't exist anymore, so this code doesn't build (as usual with ifdef'ed code after a while..). We can always resurrect this code from the Attic (or for the not so old school ppl: from SVN history ;-)
 
> > Source/WebCore/rendering/svg/SVGTextLayoutAttributesBuilder.h:46
> > +    bool buildLayoutAttributesForWholeTree(RenderSVGText*);
> 
> I am not sure about WholeTree in the name, can it be improved?
Yes, good idea, you're on the same track as Stephen - I'll name it buildLayoutAttributesForSubtree.

(In reply to comment #30)

> 
> > Source/WebCore/rendering/svg/RenderSVGText.cpp:172
> > +        return;
> 
> It would be clearer to move documentBeingDestroyed() into shallHandleSubtreeMutations(), if we can. See comment below where this is used again.
I wantd to do that as well, though I can't fold the documentBeingDestroyed() check into shallHandleSubtreeMutations() because subtreeChildWillBeRemoved() still needs to update the m_layoutAttributes Vector even though the document is being destroyed, otherwise the assertion ASSERT(m_layoutAttribbutes.isEmpty()) in the RenderSVGText destructor will fire. I've left it as-is.

> 
> >> Source/WebCore/rendering/svg/RenderSVGText.cpp:184
> >> +    }
> > 
> > This special case does not seem more optimal than falling into the general case below. I suggest leaving it out unless there is something I am missing.
> 
> I also find this confusing. It seems like the logic is such that newLayoutAttributes can only be empty if the child is not inline text and there are no other children that are. Is that right? But then shouldn't you fall through as Darin suggests and then assert that m_layoutAttributes is already empty?

While Darins suggestions is valid and would work just fine, you're approach is even better. If the layout attributes are empty, _after_ calling subtreeChildWasAdded, then eg. a <tspan> element w/o children was added to the <text> subtree. The layout attributes stay (!) empty in that case. I can just ASSERT(m_layoutAttributes.isEmpty()) if newLayoutAttributes is empty.


> > Source/WebCore/rendering/svg/RenderSVGText.cpp:241
> > +        return;
> 
> Could you explain why it is not necessary here to check documentBeingDestroyed? Why execute the next few lines before checking?
I answered that above - m_layoutAttributes should always stay in-sync with the render tree state, even if the document is destructing (We need to avoid dangling pointers in the m_layoutAttributes vector).

> > Source/WebCore/rendering/svg/RenderSVGText.cpp:375
> > +
> 
> Looks like this could be cleaned up to share code with updateFontInAllDescendents, which would make it clearer and make it easier to avoid future problems.
Good idea:
static inline void updateFontInAllDescendants(RenderObject* start, bool rebuildMetrics = false)
{
    for (RenderObject* descendant = start; descendant; descendant = descendant->nextInPreOrder(start)) {
        if (!descendant->isSVGInlineText())
            continue;
        toRenderSVGInlineText(descendant)->updateScaledFont();
        if (rebuildMetrics)
            m_layoutAttributesBuilder.rebuildMetricsForTextRenderer(text);
    }
}

> >> Source/WebCore/rendering/svg/SVGTextLayoutAttributesBuilder.h:46
> >> +    bool buildLayoutAttributesForWholeTree(RenderSVGText*);
> > 
> > I am not sure about WholeTree in the name, can it be improved?
> 
> buildLayoutAttributesForSubtree? That seems to be what it's doing.
Agreed.

[Nikolas Zimmermann]

(In reply to comment #32)
> Good idea:
> static inline void updateFontInAllDescendants(RenderObject* start, bool rebuildMetrics = false)

Yikes, wrong paste. m_layoutAttributesBuilder is not available in a static function. I'm going for:
static inline void updateFontInAllDescendants(RenderObject* start, SVGTextLayoutAttributesBuilder* builder = 0)
{
    for (RenderObject* descendant = start; descendant; descendant = descendant->nextInPreOrder(start)) {
        if (!descendant->isSVGInlineText())
            continue;
        RenderSVGInlineText* text = toRenderSVGInlineText(descendant);
        text->updateScaledFont();
        if (builder)
            builder->rebuildMetricsForTextRenderer(text);
    }
}

If there's a builder passed, metrics will be rebuilt.

[Nikolas Zimmermann]

Committed r117225: <http://trac.webkit.org/changeset/117225>