Bug 101821 – Track subframe count to avoid traversing the tree when there's no subframes

• Component: New Bugs
• Status: RESOLVED FIXED

[Elliott Sprehn]

Track subframe count to avoid traversing the tree when there's no subframes

[Elliott Sprehn]

Created attachment 173419 [details]
Patch

[Elliott Sprehn]

@ojan

This is the whole patch, it needs to be split into two with the SubframeLoadingDisabler refactored out.

There's also an overflow bug right now because the number of iframes you insert can be over 1024 (10bits) and we increment that counter on Node::insertedInto() not when you get a Frame* so the 1000 limit doesn't apply.

We either need to use an unsigned 32bit int and assume you run out of heap space before you overflow the count in trying to create 2^32 <iframe> elements or we need to change the code to walk up the tree only when you get assigned a Frame*.

Anyway, I'm posting the patch so it's at least somewhere instead of on my machine. :)

[Elliott Sprehn]

Other unfinished tasks in this patch like I just noticed:

- I walk one level of the tree even when there's no subframes

- Walking the NodeVector in willRemoveChildren() is wrong since you could have changed the children and we'd miss some nodes for disconnection.

I'll post another patch on Monday.

[Ojan Vafai]

Comment on attachment 173419 [details]
Patch

Removing the r? since the patch needs work.

[Alexey Proskuryakov]

Do you expect this to be a performance improvement in any real life situations?

[Elliott Sprehn]

(In reply to comment #5)
> Do you expect this to be a performance improvement in any real life situations?

Yes. It skips a subtree traversal when there's no frames in the subtree in removeChild. This should improve performance on things like changing views in web apps where they swap out a large chunk of DOM on url change.

[Alexey Proskuryakov]

Where will the improvement come from? We have a DOM traversal anyway to dispatch removedFrom() on every node.

Historically, the frame count in document has been causing a number of issues due to incorrect counting. Whenever there are two ways of storing the same information, they inevitably get out of sync. The benefit should be larger than the cost of bugs (including security bugs).

[Hajime Morrita]

(In reply to comment #7)
> Where will the improvement come from? We have a DOM traversal anyway to dispatch removedFrom() on every node.

Just FYI, the traversal to be removed is pre-removal one.
Node::removedFrom() is post-removal traversal.

It was once called Node::willRemove().
I inlined it by de-virtualizing them: http://trac.webkit.org/changeset/116629

[Elliott Sprehn]

Created attachment 174365 [details]
Patch

Simplified approach that is more tightly coupled to the lifecycle of the Frame objects.

[Elliott Sprehn]

(In reply to comment #9)
> Created an attachment (id=174365) [details]
> Patch
> 
> Simplified approach that is more tightly coupled to the lifecycle of the Frame objects.

This approach uses the new setContentFrame() method to only increment when there really are connected frames and then decrements when being disconnected. This removes all the confusing lifecycle management that was from overriding insertedInto() and removedFrom().

I also added a compile assert about the bitfield and I made the change more incremental instead of just ditching the existing ChildFrameDisconnector as in the original patch.

[Ojan Vafai]

(In reply to comment #7)
> Where will the improvement come from? We have a DOM traversal anyway to dispatch removedFrom() on every node.

Is that we do two traversals. Historically, we've found that any code that walks lots of nodes in a tight loop will blow out the CPU cache and there is a non-trivial measurable improvement by avoiding doing the extra loop. For example, there was a patch a while back that added another loop over the vector of nodes to be removed in removeChildren that regressed performance by %6 in one benchmark.

> Historically, the frame count in document has been causing a number of issues due to incorrect counting. Whenever there are two ways of storing the same information, they inevitably get out of sync. The benefit should be larger than the cost of bugs (including security bugs).

That's a fair concern. Elliot has simplified some of the frame creation logic in preparation for this patch. The new code seems safer and more maintainable to me.

Long-term, I think we should consider instead keeping a count of frames with beforeunload/unload handlers since those are the only ones we care about, but since that's a more invasive patch, I think this is a good incremental step in that direction.

[Ojan Vafai]

Comment on attachment 174365 [details]
Patch

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

> Source/WebCore/dom/ContainerNodeAlgorithms.h:274
> +    void disconnectChildren();
>      void disconnect();

I would kind of prefer just having one method here that takes ShouldIncludeRoot as an argument. It took me a while of looking around the code to understand why we needed both of these methods. WDYT?

> Source/WebCore/dom/ContainerNodeAlgorithms.h:279
> +    void collectFrameOwners(Node* root);
> +    void collectFrameOwners(ElementShadow*);
> +    void disconnectCollectedFrameOwners();

These names are much more clear!

> Source/WebCore/dom/ContainerNodeAlgorithms.h:301
> +inline void ChildFrameDisconnector::collectFrameOwners(Node* root)

Not sure if we care that this used to be iterative and is now recursive.

> Source/WebCore/dom/ContainerNodeAlgorithms.h:306
> +    if (root->isElementNode() && root->isFrameOwnerElement())

Lets keep the hasCustomCallbacks in here for now and remove it in a followup patch. That way if it still does somehow affect performance, we can identify it separately from the performance impact of the rest of the change and not have to revert the whole change.

> Source/WebCore/dom/NodeRareData.h:349
> +COMPILE_ASSERT(Page::maxNumberOfFrames < 1024, Frame_limit_should_fit_in_rare_data_count);

<3 this assert.

> Source/WebCore/html/HTMLFrameOwnerElement.cpp:70
> +    // This causes an unload event in the subframe so it cannot be a part of
> +    // removedFrom() because the unload handler in a same domain frame must be
> +    // able to reach upward into the owner document.

Thanks for making this more clear.

[Alexey Proskuryakov]

I think that I'm convinced about the idea of this patch, except for one detail:

> Long-term, I think we should consider instead keeping a count of frames with beforeunload/unload handlers since those are the only ones we care about, but since that's a more invasive patch, I think this is a good incremental step in that direction.

If that's the only purpose of the traversal, can we get the same benefits in practice by starting from the existing count of unload and beforeunload handlers in DOMWindow that is used to disable sudden termination? Most pages don't have any unload handlers, so counting them in each frame may be overkill.

[Elliott Sprehn]

(In reply to comment #13)
> I think that I'm convinced about the idea of this patch, except for one detail:
> 
> > Long-term, I think we should consider instead keeping a count of frames with beforeunload/unload handlers since those are the only ones we care about, but since that's a more invasive patch, I think this is a good incremental step in that direction.
> 
> If that's the only purpose of the traversal, can we get the same benefits in practice by starting from the existing count of unload and beforeunload handlers in DOMWindow that is used to disable sudden termination? Most pages don't have any unload handlers, so counting them in each frame may be overkill.

The count is not transitive so it wouldn't work as is. We'd also still need to propagate the count up the parent node hierarchy like in this patch.

Since that approach is just more optimization on top of the one here I'd rather land this and then make another patch that implements that approach since it requires much of the same code I have here.

[Elliott Sprehn]

(In reply to comment #12)
> (From update of attachment 174365 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=174365&action=review
> 
> > Source/WebCore/dom/ContainerNodeAlgorithms.h:274
> > +    void disconnectChildren();
> >      void disconnect();
> 
> I would kind of prefer just having one method here that takes ShouldIncludeRoot as an argument. It took me a while of looking around the code to understand why we needed both of these methods. WDYT?

I'm not a big fan of methods with enums that change the behavior like that, but using one here does reduce the number of lines and code duplication so I'll go back to it.

> 
> > Source/WebCore/dom/ContainerNodeAlgorithms.h:301
> > +inline void ChildFrameDisconnector::collectFrameOwners(Node* root)
> 
> Not sure if we care that this used to be iterative and is now recursive.

I don't think it should matter. attach() and detach() are recursive so if you were going to run out stack space it should have happened long before this.

[Elliott Sprehn]

Created attachment 174482 [details]
Patch

[Ojan Vafai]

Comment on attachment 174482 [details]
Patch

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

Do we have test cases of nested frames inside frames ensuring their unload handlers get called before we remove them from the DOM? Mind adding one just to be sure we're not regressing that.

> Source/WebCore/dom/ContainerNodeAlgorithms.h:336
> +inline void ChildFrameDisconnector::disconnect(DisconnectPolicy policy)

I agree this code with the enum argument is a bit less elegant, but it's more clear what's going on...at least to me. :)

[Ojan Vafai]

(In reply to comment #14)
> (In reply to comment #13)
> > I think that I'm convinced about the idea of this patch, except for one detail:
> > 
> > > Long-term, I think we should consider instead keeping a count of frames with beforeunload/unload handlers since those are the only ones we care about, but since that's a more invasive patch, I think this is a good incremental step in that direction.
> > 
> > If that's the only purpose of the traversal, can we get the same benefits in practice by starting from the existing count of unload and beforeunload handlers in DOMWindow that is used to disable sudden termination? Most pages don't have any unload handlers, so counting them in each frame may be overkill.
> 
> The count is not transitive so it wouldn't work as is. We'd also still need to propagate the count up the parent node hierarchy like in this patch.
> 
> Since that approach is just more optimization on top of the one here I'd rather land this and then make another patch that implements that approach since it requires much of the same code I have here.

To expand on this. The end result I have in my head is that we'll eventually replace the frame count with an unload handler count that is recursive and have this replace the unload stuff on DOMWindow.

[Ojan Vafai]

Comment on attachment 174482 [details]
Patch

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

> Source/WebCore/dom/Node.cpp:2834
> +    ASSERT(isContainerNode());

Seems weird to me to have this assert here, but not in decrementConnectedSubframeCount.

[Elliott Sprehn]

(In reply to comment #17)
> (From update of attachment 174482 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=174482&action=review
> 
> Do we have test cases of nested frames inside frames ensuring their unload handlers get called before we remove them from the DOM? Mind adding one just to be sure we're not regressing that.
> 

I can add a test, but this isn't related to that at all since the counting is per document so for the nested unload handler not to get called the parent frame's unload would have to have never been called which we do have tests for.

Such a test would be necessary if we want to track unload handling later though.

[Elliott Sprehn]

(In reply to comment #19)
> (From update of attachment 174482 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=174482&action=review
> 
> > Source/WebCore/dom/Node.cpp:2834
> > +    ASSERT(isContainerNode());
> 
> Seems weird to me to have this assert here, but not in decrementConnectedSubframeCount.

I'll add it to decrement. I hadn't done that since decrement asserts if the value is not > 0, so you would have had to have called increment first but I guess you can go into the rare data and skip the increment assert.

[Ojan Vafai]

Comment on attachment 174482 [details]
Patch

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

>>> Source/WebCore/dom/Node.cpp:2834
>>> +    ASSERT(isContainerNode());
>> 
>> Seems weird to me to have this assert here, but not in decrementConnectedSubframeCount.
> 
> I'll add it to decrement. I hadn't done that since decrement asserts if the value is not > 0, so you would have had to have called increment first but I guess you can go into the rare data and skip the increment assert.

Oh. I see. That's fine too.

[Ojan Vafai]

(In reply to comment #20)
> (In reply to comment #17)
> > (From update of attachment 174482 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=174482&action=review
> > 
> > Do we have test cases of nested frames inside frames ensuring their unload handlers get called before we remove them from the DOM? Mind adding one just to be sure we're not regressing that.
> > 
> 
> I can add a test, but this isn't related to that at all since the counting is per document so for the nested unload handler not to get called the parent frame's unload would have to have never been called which we do have tests for.
> 
> Such a test would be necessary if we want to track unload handling later though.

You're right. Nevermind.

[Alexey Proskuryakov]

> The end result I have in my head is that we'll eventually replace the frame count with an unload handler count that is recursive and have this replace the unload stuff on DOMWindow.

I'm not sure if we are on the same page yet. The tracking in DOMWindow is not just recursive, it's actually per-process.

[WebKit Review Bot]

Comment on attachment 174482 [details]
Patch

Clearing flags on attachment: 174482

Committed r134817: <http://trac.webkit.org/changeset/134817>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Ojan Vafai]

(In reply to comment #24)
> > The end result I have in my head is that we'll eventually replace the frame count with an unload handler count that is recursive and have this replace the unload stuff on DOMWindow.
> 
> I'm not sure if we are on the same page yet. The tracking in DOMWindow is not just recursive, it's actually per-process.

Whoops. Sorry. You're right. We could add the unload handler check in addition to what just got committed actually or we can rollout if you still object.

One advantage of tracking this per Node is that even in cases where we have unload handlers, we don't have to walk the whole subtree. We only walk down to each frame and prune the rest of the traversal. In the end result I'm envisioning, we'd only walk down to the frames that have unload handlers.

[Ojan Vafai]

Hmmm. Maybe we don't need any of this complexity actually. It looks like Gecko fires unload handlers after it has removed the frame from the DOM. If we did the same, we would never need to do this pre-removal traversal.

https://bugs.webkit.org/show_bug.cgi?id=102012#c10

[Elliott Sprehn]

(In reply to comment #28)
> Hmmm. Maybe we don't need any of this complexity actually. It looks like Gecko fires unload handlers after it has removed the frame from the DOM. If we did the same, we would never need to do this pre-removal traversal.
> 
> https://bugs.webkit.org/show_bug.cgi?id=102012#c10

Yeah, I think we can collect the frames to call disconnect on during the removedFrom() traversal. We could use a set like SubframeLoadingDisabler does and in HTMLFrameOwnerElement::removedFrom() we add ourself to the nearest ancestor removal list. That would remove the need for SubframeLoadingDisabler and the counting in this patch.

I'd like to leave this patch in and see what it does to the page cyclers and perf tests though.

[Ojan Vafai]

(In reply to comment #27)
> (In reply to comment #24)
> > > The end result I have in my head is that we'll eventually replace the frame count with an unload handler count that is recursive and have this replace the unload stuff on DOMWindow.
> > 
> > I'm not sure if we are on the same page yet. The tracking in DOMWindow is not just recursive, it's actually per-process.
> 
> Whoops. Sorry. You're right. We could add the unload handler check in addition to what just got committed actually or we can rollout if you still object.
> 
> One advantage of tracking this per Node is that even in cases where we have unload handlers, we don't have to walk the whole subtree. We only walk down to each frame and prune the rest of the traversal. In the end result I'm envisioning, we'd only walk down to the frames that have unload handlers.

As I think about it more, I increasingly feel that the frame count approach is worth it. Otherwise, large high-profile sites like Gmail, Facebook, etc won't get any of the speed benefit here since they all have unload handlers.

That said, we could add the unload count check in addition to get extra perf benefit for pages without unload handlers, but I'm not sure it would buy us real performance improvements given that we're already doing a heavily pruned traversal of the tree.

[WebKit Review Bot]

Re-opened since this is blocked by bug 102576

[Elliott Sprehn]

(In reply to comment #31)
> Re-opened since this is blocked by bug 102576

So it seems we must override insertedInto() and removedFrom() to handle parser mutations that may remove us from the tree and put us elsewhere without actually doing a disconnect(). We could also make parserRemoveChild() decrement all ancestors by the removed child's count, and we can make parserAppendChild() and parserInsertBefore() increment all ancestors by our current count.

[Ojan Vafai]

(In reply to comment #32)
> (In reply to comment #31)
> > Re-opened since this is blocked by bug 102576
> 
> So it seems we must override insertedInto() and removedFrom() to handle parser mutations that may remove us from the tree and put us elsewhere without actually doing a disconnect(). We could also make parserRemoveChild() decrement all ancestors by the removed child's count, and we can make parserAppendChild() and parserInsertBefore() increment all ancestors by our current count.

This makes me thing we should just jump to the final solution of tracking beforeunload/unload handlers since the two solutions are now diverging. beforeunload/unload handler tracking won't need this extra handling for parser mutations, right?

[Elliott Sprehn]

(In reply to comment #33)
> (In reply to comment #32)
> > (In reply to comment #31)
> > > Re-opened since this is blocked by bug 102576
> > 
> > So it seems we must override insertedInto() and removedFrom() to handle parser mutations that may remove us from the tree and put us elsewhere without actually doing a disconnect(). We could also make parserRemoveChild() decrement all ancestors by the removed child's count, and we can make parserAppendChild() and parserInsertBefore() increment all ancestors by our current count.
> 
> This makes me thing we should just jump to the final solution of tracking beforeunload/unload handlers since the two solutions are now diverging. beforeunload/unload handler tracking won't need this extra handling for parser mutations, right?

 There's no divergence, we still need this change for parser mutations. :)

Imagine the tree:

A
  \
   B
     \
      <iframe src="javascript:onunload=...">

and then the parser moves it into the tree:

C
  \
   D

it'll do so without unloading the frame so we still need the same logic that walks up the tree and decrements the frame count for B and A on parserRemove, and then increments the frame count for D and C on parserAppend.

We should fix the parser mutations and reland this patch since we need almost the exact same logic for unload handler counting.

[Ojan Vafai]

javascript urls! I suppose the same effect could be achieved with a script element immediately after the iframe.

> So it seems we must override insertedInto() and removedFrom() to handle parser mutations that may remove us from the tree and put us elsewhere without actually doing a disconnect(). We could also make parserRemoveChild() decrement all ancestors by the removed child's count, and we can make parserAppendChild() and parserInsertBefore() increment all ancestors by our current count.

The latter sounds better to me at first glance, but it's not clear to me which is the better way to handle this. For the most part, I don't think it would slow down parsing since it would just be a single if-statement on the hasRareData boolean the vast majority of the time. 

What would the insertedInto/removedFrom version look like? I suppose it would be like the first patch on this bug?

[Elliott Sprehn]

Created attachment 177693 [details]
Patch

[Elliott Sprehn]

(In reply to comment #36)
> Created an attachment (id=177693) [details]
> Patch

Added the fix for parser based mutations and a test. :)

[Eric Seidel (no email)]

Comment on attachment 177693 [details]
Patch

This seems trivial to overfloe

[Elliott Sprehn]

(In reply to comment #38)
> (From update of attachment 177693 [details])
> This seems trivial to overfloe

You shouldn't be able to overflow it because of the Page::maxNumberOfFrames limit which is 1000. If you hit that we stop creating new Frame instances and your iframes fail to load. That's how ojan and I picked 10 bits for the count. See the COMPILE_ASSERT I added in NodeRareData.h :)

[Ojan Vafai]

Comment on attachment 177693 [details]
Patch

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

> Source/WebCore/html/HTMLFrameOwnerElement.cpp:69
> +    // FIXME: This causes an unload event in the subframe which could execute
> +    // script that would reach into up into this document.

What's the fix here? Not clear to me what the problem is from this description.

> LayoutTests/fast/frames/parser-append-subframe-count.html:15
> +    This test should not cause crash or asserts decrementing the connected

nit: s/crash/crashes/

[Elliott Sprehn]

Created attachment 183339 [details]
Patch

[Elliott Sprehn]

(In reply to comment #40)
> (From update of attachment 177693 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=177693&action=review
> 
> > Source/WebCore/html/HTMLFrameOwnerElement.cpp:69
> > +    // FIXME: This causes an unload event in the subframe which could execute
> > +    // script that would reach into up into this document.
> 
> What's the fix here? Not clear to me what the problem is from this description.

I added more explanation.

[Elliott Sprehn]

Created attachment 183344 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 183344 [details]
Patch for landing

Clearing flags on attachment: 183344

Committed r140090: <http://trac.webkit.org/changeset/140090>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Alexey Proskuryakov]

Comment on attachment 183344 [details]
Patch for landing

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

> Source/WebCore/dom/NodeRareData.h:309
> +    unsigned connectedSubframeCount() const { return m_connectedFrameCount; }

It would be helpful to assert that the cached value matches actual one here.

[Elliott Sprehn]

Comment on attachment 183344 [details]
Patch for landing

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

>> Source/WebCore/dom/NodeRareData.h:309
>> +    unsigned connectedSubframeCount() const { return m_connectedFrameCount; }
> 
> It would be helpful to assert that the cached value matches actual one here.

Can you explain what you mean by cached value and actual value? I'm not sure what you want to assert.

[Alexey Proskuryakov]

Is there a way to calculate connectedSubframeCount() by traversing the three? I'd assert that this result matches m_connectedFrameCount.

[Alexey Proskuryakov]

the tree*

[Elliott Sprehn]

(In reply to comment #48)
> Is there a way to calculate connectedSubframeCount() by traversing the tree? I'd assert that this result matches m_connectedFrameCount.

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