Bug 195776 – Reduce the size of Node::deref by eliminating an explicit parentNode check

• Component: DOM
• Status: RESOLVED FIXED

[Ryosuke Niwa]

As discussed in https://bugs.webkit.org/show_bug.cgi?id=195661,
we can use the same strategy as String and use the lowest bit of Node::m_refCount
to indicate the pretense of a parent node.

This will reduce the load in Node::def. We can also avoid writing to m_refCount
in the case of calling removedLastRef() as we've done for RefCounted<T> in https://trac.webkit.org/r30042.

[Ryosuke Niwa]

This seems to reduce the binary size of WebCore from 61260928 to 61213824 in my local builds at r242965.

[Ryosuke Niwa]

Created attachment 364715 [details]
Patch

[Ryosuke Niwa]

Created attachment 364721 [details]
Patch

[EWS Watchlist]

Comment on attachment 364721 [details]
Patch

Attachment 364721 [details] did not pass mac-ews (mac):
Output: https://webkit-queues.webkit.org/results/11510518

New failing tests:
fast/repaint/simple-line-layout-shrinking-content.html
accessibility/mac/aria-liveregions-addedelement.html

[EWS Watchlist]

Created attachment 364738 [details]
Archive of layout-test-results from ews103 for mac-highsierra

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews103  Port: mac-highsierra  Platform: Mac OS X 10.13.6

[Ryosuke Niwa]

Simon and I discussed the idea of using the highest bit instead to avoid having to hard-code 2 everywhere, and in fact I wrote such a patch but it has one downside that the highest bit can also be overridden by the regular ref-counting and we may make m_refCount to 0 in the case of overflow.

Using the lowest bit is slightly more secure as long as the node has a parent, which is more common case anyway. So let's just define a constexpr somewhere for 2 and use the lowest bit.

[EWS Watchlist]

Comment on attachment 364721 [details]
Patch

Attachment 364721 [details] did not pass mac-wk2-ews (mac-wk2):
Output: https://webkit-queues.webkit.org/results/11511189

New failing tests:
fast/repaint/simple-line-layout-shrinking-content.html
accessibility/mac/aria-liveregions-addedelement.html

[EWS Watchlist]

Created attachment 364748 [details]
Archive of layout-test-results from ews104 for mac-highsierra-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews104  Port: mac-highsierra-wk2  Platform: Mac OS X 10.13.6

[EWS Watchlist]

Comment on attachment 364721 [details]
Patch

Attachment 364721 [details] did not pass mac-debug-ews (mac):
Output: https://webkit-queues.webkit.org/results/11511165

New failing tests:
fast/repaint/simple-line-layout-shrinking-content.html
accessibility/mac/aria-liveregions-addedelement.html

[EWS Watchlist]

Created attachment 364752 [details]
Archive of layout-test-results from ews113 for mac-highsierra

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews113  Port: mac-highsierra  Platform: Mac OS X 10.13.6

[Darin Adler]

Comment on attachment 364721 [details]
Patch

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

> Source/WebCore/dom/Node.h:723
> -    return m_refCount == 1;
> +    return m_refCount >= 2;

This seems wrong. The point of this is function to return true only if Node has no more than one ref and no less than one ref. Not to return 1 if it has more than one ref. I think the correct implementation is one of these:

    return (m_refCount >> 1) == 1;
    return (m_refCount & ~1) == 2;

[EWS Watchlist]

Comment on attachment 364721 [details]
Patch

Attachment 364721 [details] did not pass win-ews (win):
Output: https://webkit-queues.webkit.org/results/11512677

New failing tests:
fast/repaint/simple-line-layout-shrinking-content.html

[EWS Watchlist]

Created attachment 364767 [details]
Archive of layout-test-results from ews204 for win-future

The attached test failures were seen while running run-webkit-tests on the win-ews.
Bot: ews204  Port: win-future  Platform: CYGWIN_NT-6.1-2.10.0-0.325-5-3-x86_64-64bit

[Ryosuke Niwa]

Comment on attachment 364721 [details]
Patch

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

>> Source/WebCore/dom/Node.h:723
>> +    return m_refCount >= 2;
> 
> This seems wrong. The point of this is function to return true only if Node has no more than one ref and no less than one ref. Not to return 1 if it has more than one ref. I think the correct implementation is one of these:
> 
>     return (m_refCount >> 1) == 1;
>     return (m_refCount & ~1) == 2;

Oh oops, you're right.

> Source/WebCore/dom/Node.h:728
>      return m_refCount;

This also needs to be fixed.

[Ryosuke Niwa]

Comment on attachment 364721 [details]
Patch

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

>> Source/WebCore/dom/Node.h:728
>>      return m_refCount;
> 
> This also needs to be fixed.

This was the cause of the test failures. With refCount() returning non-zero value,
the optimization in replaceChildrenWithFragment to avoid replacing the text node was disabled.

[Ryosuke Niwa]

Created attachment 364771 [details]
Fixed the tests

[Ryosuke Niwa]

Created attachment 364772 [details]
Fixed the tests

[Ryosuke Niwa]

Comment on attachment 364772 [details]
Fixed the tests

Oh what the heck. I forgot to remove parentNode() check I added back for debugging :(

[Ryosuke Niwa]

Created attachment 364773 [details]
Patch

[Geoffrey Garen]

Comment on attachment 364773 [details]
Patch

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

> Source/WebCore/dom/Node.cpp:2533
> +        m_refCount = 0; // Document needs m_refCount to be 0 here due to m_referencingNodeCount.

I didn't fully understand this comment or the related ChangeLog explanation.

Can we make a nice API so that Document's use of m_refCount works without this unique behavior?

We are calling Document::removedLastRef(). Is that a strong enough signal to the Document that it really has no referencing nodes?

> Source/WebCore/dom/Node.cpp:-2537
> -    m_refCount = 1; // Avoid double destruction through use of RefPtr<T>. (This is a security mitigation in case of programmer error. It will ASSERT in debug builds.)

Why don't we need this anymore?

Why does Document still do this if Node doesn't?

> Source/WebCore/dom/Node.h:621
> +    static constexpr uint32_t s_refCountIncrementUnit = 2;

Let's call this s_refCountIncrement to match StringImpl.

> Source/WebCore/dom/Node.h:669
> +    uint32_t m_refCount { s_refCountIncrementUnit };

This probably needs a better name, like m_refCountAndParentBit.

> Source/WebCore/dom/Node.h:730
> +    return m_refCount >> 1;

We probably want an s_refCountShift instead of a hard-coded 1.

> Source/WebCore/dom/Node.h:744
> +    auto refCountWithoutParentBit = m_refCount & ~0x1;

We probably want an s_refCountMask instead of a hard-coded 1.

[Ryosuke Niwa]

(In reply to Geoffrey Garen from comment #20)
> Comment on attachment 364773 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=364773&action=review
> 
> > Source/WebCore/dom/Node.cpp:2533
> > +        m_refCount = 0; // Document needs m_refCount to be 0 here due to m_referencingNodeCount.
> 
> I didn't fully understand this comment or the related ChangeLog explanation.
> 
> Can we make a nice API so that Document's use of m_refCount works without
> this unique behavior?

We can't because if m_refCount is not 0 here when m_referencingNodeCount is not zero, Document::removedLastRef doesn't delete document. Instead, it gets deleted when m_referencingNodeCount becomes 0 in decrementReferencingNodeCount. But it deletes Document only when m_refCount is also zero. If we didn't decrement m_refCount here, then we won't be able to tell in decrementReferencingNodeCount whether m_refCount is actually 2, or it would have been reached 0 but we simply didn't decrement.

> We are calling Document::removedLastRef(). Is that a strong enough signal to
> the Document that it really has no referencing nodes?

No. There could be nodes in the document which still references such a Document. This is kept track by m_referencingNodeCount but Document::removedLastRef still needs to run some cleanup steps so that it can remove any Ref/RefPtr Document itself holds.

> > Source/WebCore/dom/Node.cpp:-2537
> > -    m_refCount = 1; // Avoid double destruction through use of RefPtr<T>. (This is a security mitigation in case of programmer error. It will ASSERT in debug builds.)
> 
> Why don't we need this anymore?

Because we would never decrement m_refCount to 0 in Node::Derek.

> Why does Document still do this if Node doesn't?

Because Document has the issue above. That means we still DO need to decrement m_refCount to 0 when the last de-ref is called so we'd have to set it back to 2 before calling delete.

> > Source/WebCore/dom/Node.h:621
> > +    static constexpr uint32_t s_refCountIncrementUnit = 2;
> 
> Let's call this s_refCountIncrement to match StringImpl.

Sure.

> > Source/WebCore/dom/Node.h:669
> > +    uint32_t m_refCount { s_refCountIncrementUnit };
> 
> This probably needs a better name, like m_refCountAndParentBit.

Will rename.

> > Source/WebCore/dom/Node.h:730
> > +    return m_refCount >> 1;
> 
> We probably want an s_refCountShift instead of a hard-coded 1.

Sure. Will do.

> > Source/WebCore/dom/Node.h:744
> > +    auto refCountWithoutParentBit = m_refCount & ~0x1;
> 
> We probably want an s_refCountMask instead of a hard-coded 1.

Okay, will do.

[Geoffrey Garen]

Comment on attachment 364773 [details]
Patch

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

r=me with comments already discussed, and one new suggestion

>>> Source/WebCore/dom/Node.cpp:2533
>>> +        m_refCount = 0; // Document needs m_refCount to be 0 here due to m_referencingNodeCount.
>> 
>> I didn't fully understand this comment or the related ChangeLog explanation.
>> 
>> Can we make a nice API so that Document's use of m_refCount works without this unique behavior?
>> 
>> We are calling Document::removedLastRef(). Is that a strong enough signal to the Document that it really has no referencing nodes?
> 
> We can't because if m_refCount is not 0 here when m_referencingNodeCount is not zero, Document::removedLastRef doesn't delete document. Instead, it gets deleted when m_referencingNodeCount becomes 0 in decrementReferencingNodeCount. But it deletes Document only when m_refCount is also zero. If we didn't decrement m_refCount here, then we won't be able to tell in decrementReferencingNodeCount whether m_refCount is actually 2, or it would have been reached 0 but we simply didn't decrement.

Would it work to move this assignment of 0 into Document::removedLastRef?

Document::removedLastRef could include a comment that said "Node::removedLastRef doesn't set refCount() to zero because it's not observable. But we need to remember that our refCount reached zero in subsequent calls to decrementReferencingNodeCount()."

How does that sound?

[Ryosuke Niwa]

(In reply to Geoffrey Garen from comment #22)
> Comment on attachment 364773 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=364773&action=review
> 
> r=me with comments already discussed, and one new suggestion
> 
> >>> Source/WebCore/dom/Node.cpp:2533
> >>> +        m_refCount = 0; // Document needs m_refCount to be 0 here due to m_referencingNodeCount.
> >> 
> >> I didn't fully understand this comment or the related ChangeLog explanation.
> >> 
> >> Can we make a nice API so that Document's use of m_refCount works without this unique behavior?
> >> 
> >> We are calling Document::removedLastRef(). Is that a strong enough signal to the Document that it really has no referencing nodes?
> > 
> > We can't because if m_refCount is not 0 here when m_referencingNodeCount is not zero, Document::removedLastRef doesn't delete document. Instead, it gets deleted when m_referencingNodeCount becomes 0 in decrementReferencingNodeCount. But it deletes Document only when m_refCount is also zero. If we didn't decrement m_refCount here, then we won't be able to tell in decrementReferencingNodeCount whether m_refCount is actually 2, or it would have been reached 0 but we simply didn't decrement.
> 
> Would it work to move this assignment of 0 into Document::removedLastRef?
> 
> Document::removedLastRef could include a comment that said
> "Node::removedLastRef doesn't set refCount() to zero because it's not
> observable. But we need to remember that our refCount reached zero in
> subsequent calls to decrementReferencingNodeCount()."

Sure, will do.

[Ryosuke Niwa]

Created attachment 364900 [details]
Patch for landing

[Ryosuke Niwa]

Comment on attachment 364900 [details]
Patch for landing

Wait for EWS.

[WebKit Commit Bot]

Comment on attachment 364900 [details]
Patch for landing

Clearing flags on attachment: 364900

Committed r243037: <https://trac.webkit.org/changeset/243037>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Radar WebKit Bug Importer]

<rdar://problem/48950994>

[Ryan Haddad]

This change broke the Windows build:

c:\cygwin\home\buildbot\worker\win10-release\build\source\webcore\dom\node.h(622): error C2220: warning treated as error - no 'object' file generated (compiling source file C:\cygwin\home\buildbot\worker\win10-release\build\Source\WebCore\html\track\TextTrackCueGeneric.cpp) [C:\cygwin\home\buildbot\worker\win10-release\build\WebKitBuild\Release\Source\WebCore\WebCore.vcxproj]
c:\cygwin\home\buildbot\worker\win10-release\build\source\webcore\dom\node.h(622): warning C4245: 'initializing': conversion from 'int' to 'const uint32_t', signed/unsigned mismatch (compiling source file C:\cygwin\home\buildbot\worker\win10-release\build\Source\WebCore\html\track\TextTrackCueGeneric.cpp) [C:\cygwin\home\buildbot\worker\win10-release\build\WebKitBuild\Release\Source\WebCore\WebCore.vcxproj]

https://build.webkit.org/builders/Apple%20Win%2010%20Release%20%28Build%29/builds/2928

[Ryan Haddad]

Reverted r243037 for reason:

Broke the Windows build

Committed r243075: <https://trac.webkit.org/changeset/243075>

[Ryosuke Niwa]

Created attachment 365036 [details]
Wait for EWS

[Ryosuke Niwa]

Why is EWS so insanely slow?

[Ryosuke Niwa]

Comment on attachment 365036 [details]
Wait for EWS

Clearing flags on attachment: 365036

Committed r243122: <https://trac.webkit.org/changeset/243122>

[Ryosuke Niwa]

All reviewed patches have been landed.  Closing bug.

[Darin Adler]

Comment on attachment 365036 [details]
Wait for EWS

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

A few things I noticed after this was landed.

> Source/WebCore/dom/Document.cpp:673
> +        // But we need to remember that our refCount reached zero in subsequent calls to decrementReferencingNodeCount()

No period at the end of this line.

> Source/WebCore/dom/Node.cpp:335
>      // This is a security mitigation in case of programmer errorm (caught by a debug assertion).

"errorm"

A little peculiar that this is not worded the same as the comment with identical purpose in Document.h.

> Source/WebCore/dom/Node.cpp:2527
> +    // This avoids double destruction even when there is a programming error to use Ref<T> / RefPtr<T> on this node.
> +    // There are debug assertions in Node::ref() / Node::deref() to catch such a programming error.
> +    ASSERT(m_refCountAndParentBit == s_refCountIncrement);

Really confusing that this comment claims that an *assertion* avoids double destruction. The correct claim is that this strategy avoids double destruction, but it’s strange to have the comment on an assertion.

> Source/WebCore/dom/Node.h:622
> +    static constexpr uint32_t s_refCountIncrement = 2;
> +    static constexpr uint32_t s_refCountMask = ~static_cast<uint32_t>(0x1);

Kind of funny to use just "2" but then "0x1". Why not just "1"?

Or could write the increment as "1 << 1" and the mask as "~0 << 1" and even consider having a constant for the shift amount of 1, and use that instead of division by s_refCountIncrement.

> Source/WebCore/dom/Node.h:711
> +    auto tempRefCount = m_refCountAndParentBit - s_refCountIncrement;

I think this should be called "updatedRefCount" rather than "tempRefCount".

> Source/WebCore/dom/Node.h:717
> +        return;

This seems more like the place we should have the comment about making double destruction safe, not elsewhere in the functions that make assertions.

> Source/WebCore/dom/Node.h:746
> +    auto refCountWithoutParentBit = m_refCountAndParentBit & s_refCountMask;
> +    m_refCountAndParentBit = refCountWithoutParentBit | !!parent;

I think I would find this more readable either in a single expression or with a much shorter variable name.

[Ryosuke Niwa]

(In reply to Darin Adler from comment #35)
> Comment on attachment 365036 [details]
> Wait for EWS
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=365036&action=review
> 
> A few things I noticed after this was landed.
> 
> > Source/WebCore/dom/Document.cpp:673
> > +        // But we need to remember that our refCount reached zero in subsequent calls to decrementReferencingNodeCount()
> 
> No period at the end of this line.

Fixed.

> > Source/WebCore/dom/Node.cpp:335
> >      // This is a security mitigation in case of programmer errorm (caught by a debug assertion).
> 
> "errorm"
>
> A little peculiar that this is not worded the same as the comment with
> identical purpose in Document.h.

I removed this comment in favor of the one in Node.h

> > Source/WebCore/dom/Node.cpp:2527
> > +    // This avoids double destruction even when there is a programming error to use Ref<T> / RefPtr<T> on this node.
> > +    // There are debug assertions in Node::ref() / Node::deref() to catch such a programming error.
> > +    ASSERT(m_refCountAndParentBit == s_refCountIncrement);
> 
> Really confusing that this comment claims that an *assertion* avoids double
> destruction. The correct claim is that this strategy avoids double
> destruction, but it’s strange to have the comment on an assertion.

I removed this comment and added the same one as Document.h in Node.h where we avoid decrementing m_refCountAndParentBit.

> > Source/WebCore/dom/Node.h:622
> > +    static constexpr uint32_t s_refCountIncrement = 2;
> > +    static constexpr uint32_t s_refCountMask = ~static_cast<uint32_t>(0x1);
> 
> Kind of funny to use just "2" but then "0x1". Why not just "1"?

Sure, I'd just use 2 & 1.

> > Source/WebCore/dom/Node.h:711
> > +    auto tempRefCount = m_refCountAndParentBit - s_refCountIncrement;
> 
> I think this should be called "updatedRefCount" rather than "tempRefCount".

Done.

> > Source/WebCore/dom/Node.h:717
> > +        return;
> 
> This seems more like the place we should have the comment about making
> double destruction safe, not elsewhere in the functions that make assertions.

Done that.

> > Source/WebCore/dom/Node.h:746
> > +    auto refCountWithoutParentBit = m_refCountAndParentBit & s_refCountMask;
> > +    m_refCountAndParentBit = refCountWithoutParentBit | !!parent;
> 
> I think I would find this more readable either in a single expression or
> with a much shorter variable name.

Sure, replaced it with a single line expression.

[Ryosuke Niwa]

Reopening to attach new patch.

[Ryosuke Niwa]

Created attachment 366352 [details]
Address Darin's comments

[WebKit Commit Bot]

Comment on attachment 366352 [details]
Address Darin's comments

Clearing flags on attachment: 366352

Committed r243686: <https://trac.webkit.org/changeset/243686>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Darin Adler]

Comment on attachment 366352 [details]
Address Darin's comments

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

> Source/WebCore/dom/Node.h:621
> +    static constexpr uint32_t s_refCountMask = ~static_cast<uint32_t>(1);

Did you try just ~1 or did that result in a warning?

[Ryosuke Niwa]

(In reply to Darin Adler from comment #41)
> Comment on attachment 366352 [details]
> Address Darin's comments
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=366352&action=review
> 
> > Source/WebCore/dom/Node.h:621
> > +    static constexpr uint32_t s_refCountMask = ~static_cast<uint32_t>(1);
> 
> Did you try just ~1 or did that result in a warning?

That doesn't work on Windows :(