Bug 58695 – Creating copy of ContainerNode's when inserting or removing is inefficient

• Component: WebCore JavaScript
• Status: RESOLVED FIXED

[Michael Saboff]

Two separate but possibly related changes to Source/WebCore/dom/ContainerNode.cpp involve copying nodes as a way to ensure integrity.  This is inefficient over appropriate uses of RefPtr.

The original changes are from https://bugs.webkit.org/show_bug.cgi?id=49237 and https://bugs.webkit.org/show_bug.cgi?id=57265.

[Michael Saboff]

Created attachment 89857 [details]
Patch to re-implement Node handling without making copies

[Eric Seidel (no email)]

Comment on attachment 89857 [details]
Patch to re-implement Node handling without making copies

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

> Source/WebCore/dom/ContainerNode.cpp:371
> +    for (RefPtr<Node> child = firstChild(); child; child = child->nextSibling())
> +        child->willRemove();

What will happen to the 3rd child, if calling willRemove on the 1st removes the 2nd?  Won't it get left out in the cold? (aka, never get a willRemove()?)

[Adam Barth]

Comment on attachment 89857 [details]
Patch to re-implement Node handling without making copies

Is there are particular benchmark you're optimizing?  The pattern you're introducing in this patch is much more dangerous than the existing code.  I suspect this patch introduces security vulnerabilities, but I don't have a proof-of-concept exploit to demonstrate that belief.

[Adam Barth]

+dglazkov b/c he's had fun exploring these sorts of tree-integrity issues before.

[Justin Schuh]

Yeah, we've had numerous issues in ContainerNode where reentrant manipulation of siblings or children resulted in a variety of stale pointer conditions. So, I'm apprehensive about any patch that would move us back in the other direction. But, offhand the only thing that jumps out at me is is the case Eric pointed out.

[Michael Saboff]

The benchmark in question is dromaeo?dom.  The proposed patch is worth ~2% overall due to a ~4% speed up in dom-modify.

I accept Eric's contention that there is an issue with in the third child case.

The proposed willRemove() code does need a check like:
    if (child->parentNode() != this) // Check for child being removed from subtree while reparenting.
           break;

This stops the handling of the next sibling through a deleted sibling node is a safe way.

Let me suggest that the current code is incorrect as well.  The proposed patch doesn't call "willRemove()" or "insertedIntoDocument()" for nodes after deleted nodes, but the current code calls those methods for nodes even if they have been deleted.

Therefore the proposed patch (or a slight modification) has better performance and is arguably just as correct for this corner case.

A more correct solution would be to queue up all modifying actions (e.g. run script) to be handled after the tree has been notified of the removals or insertions and then immediately process those actions.  This is similar to "attach" processing.  This would simplify the handling of side effects and provide a "correct" implementation.

I would like to proceed at this point with the faster "not necessarily correct" version of the current slower "but not correct" version.  And then work on the longer term version.

[Adam Barth]

> Therefore the proposed patch (or a slight modification) has better performance and is arguably just as correct for this corner case.

Please add a test for this case.

> I would like to proceed at this point with the faster "not necessarily correct" version of the current slower "but not correct" version.  And then work on the longer term version.

That's fine as long as we can convince ourselves that the (potential) correctness issues in the new version don't include security vulnerabilities.

[Adam Barth]

Comment on attachment 89857 [details]
Patch to re-implement Node handling without making copies

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

> Source/WebCore/dom/ContainerNode.cpp:368
> +    RefPtr<Node> protect = this;

This protect is new in this code, right?  Does that mean we're fixing a crash?  Have you looked at all callers of this function to make sure they understand that |this| might be deleted after this operation?

> Source/WebCore/dom/ContainerNode.cpp:743
> +    // NOTE: Since insertedIntoDocument can cause arbitrary changes to the 
> +    // document, we need to guard our data with RefPtrs and guard each operation
> +    // with checks for mutation.
> +    RefPtr<Node> protect = this;

Same question here.  If we're fixing crashes, we should have tests that document that.

[Adam Barth]

Comment on attachment 89857 [details]
Patch to re-implement Node handling without making copies

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

>> Source/WebCore/dom/ContainerNode.cpp:371
>> +    for (RefPtr<Node> child = firstChild(); child; child = child->nextSibling())
>> +        child->willRemove();
> 
> What will happen to the 3rd child, if calling willRemove on the 1st removes the 2nd?  Won't it get left out in the cold? (aka, never get a willRemove()?)

What will happen if one of these nodes gets moved to another parent during this operation?  It seems like we'll call willRemove on nodes that aren't actually going to be removed.

> Source/WebCore/dom/ContainerNode.cpp:752
> +        if (child->parentNode() != this) // Check for child being removed from subtree while reparenting.
> +            break;

What if child N gets moved to the first or last sibling position during this operation?  It seems like we'll either call insertedIntoDocument too many or too few times in that case, which could cause problems.

[Michael Saboff]

Created attachment 90652 [details]
Updated patch

This patch adds the "child's parent not me" check to willRemove().

Concerning various questions raised with the initial patch:

> > Therefore the proposed patch (or a slight modification) has better performance and is arguably just as correct for this corner case.
> 
> Please add a test for this case.

As I stated above, the existing code and proposed code have similar correctness issues.  In both cases the correctness issues happen when the tree is modified during the insertion or removal.  The existing code notifies nodes that are (will be) no longer part of the tree that they are being inserted.  The proposed code stops notifying later sibling nodes when it encounters a node that has been removed as a side effect. Existing tests verify the correctness and no regression on the earlier crashing problems.

> > I would like to proceed at this point with the faster "not necessarily correct" version of the current slower "but not correct" version.  And then work on the longer term version.
>
> That's fine as long as we can convince ourselves that the (potential) correctness issues in the new version don't include security vulnerabilities.

Given that we use RefPtr's as well as other sanity checks we solved for the original use after free issues.  This is as evident by removing these safeguards and running tests added with the earlier fixes and seeing the crashes.  We Ref a parent node, which will has the side effect of holding a ref to the chain of children which allows us to safely traverse them.

> > Source/WebCore/dom/ContainerNode.cpp:368
> > +    RefPtr<Node> protect = this;
> 
> This protect is new in this code, right?  Does that mean we're fixing a crash?  Have you looked at all callers of this function to make sure they understand that |this| might be deleted after this operation?
> 
> > Source/WebCore/dom/ContainerNode.cpp:743
> > +    // NOTE: Since insertedIntoDocument can cause arbitrary changes to the 
> > +    // document, we need to guard our data with RefPtrs and guard each operation
> > +    // with checks for mutation.
> > +    RefPtr<Node> protect = this;
> 
> Same question here.  If we're fixing crashes, we should have tests that document that.

These ref's allows us to safely access the parent node and its children.  It wasn't add to fix a crash, but to prevent one.

> >> Source/WebCore/dom/ContainerNode.cpp:371
> >> +    for (RefPtr<Node> child = firstChild(); child; child = child->nextSibling())
> >> +        child->willRemove();
> > 
> > What will happen to the 3rd child, if calling willRemove on the 1st removes the 2nd?  Won't it get left out in the cold? (aka, never get a willRemove()?)
> 
> What will happen if one of these nodes gets moved to another parent during this operation?  It seems like we'll call willRemove on nodes that aren't actually going to be removed.
> 
> > Source/WebCore/dom/ContainerNode.cpp:752
> > +        if (child->parentNode() != this) // Check for child being removed from subtree while reparenting.
> > +            break;
> 
> What if child N gets moved to the first or last sibling position during this operation?  It seems like we'll either call insertedIntoDocument too many or too few times in that case, which could cause problems.

The current code calls insertedIntoDocument too many times while the proposed patch could call too few times.  Both behaviors are incorrect.  We need to deal with the correctness issue by queueing up the notify calls while traversing the tree and then making the notify calls in order.

I will be filing a separate bug for the correctness issue with an outline of the proposed fix.

[Maciej Stachowiak]

Comment on attachment 90652 [details]
Updated patch

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

r=me but please consider the style comments and ideally explain why the guards here are safe and sufficient.

> Source/WebCore/dom/ContainerNode.cpp:372
> +    RefPtr<Node> protect = this;

I suggest the following as the more common WebKit idiom:

RefPtr<Node> protect(this);

> Source/WebCore/dom/ContainerNode.cpp:378
> +    for (RefPtr<Node> child = firstChild(); child; child = child->nextSibling()) {
> +        if (child->parentNode() != this) // Check for child being removed from subtree while removing.
> +            break;
> +        child->willRemove();
> +    }

Won't this possibly change behavior for nodes inserted into the subtree while removing? Is that ok? Doesn't seem like the old code is particularly sensible either). Also, is it really correct that we won't send willRemove() for any other children if one has been removed? That seems like it could be problematic.

> Source/WebCore/dom/ContainerNode.cpp:755
> +    // NOTE: Since insertedIntoDocument can cause arbitrary changes to the 
> +    // document, we need to guard our data with RefPtrs and guard each operation
> +    // with checks for mutation.
> +    RefPtr<Node> protect = this;

Again I suggest

RefPtr<Node> protect(this);

Also, it might be nice to abbreviate the comment a little. The self-protecting RefPtr is a common WebKit idiom, it is not necessary to explain the idiom, just briefly note why self-destruction is possible. The guard after each operation is also already explained below.

> Source/WebCore/dom/ContainerNode.cpp:764
> +        if (child->parentNode() != this) // Check for child being removed from subtree while reparenting.
> +            break;

Is it really right that we won't call insertedIntoDocument() on any subsequent children if even one has been removed?

[Michael Saboff]

Committed r84701: <http://trac.webkit.org/changeset/84701>