Bug 98725 – [V8] DOM wrapper objects should be collected in minor GC cycles

• Status: RESOLVED
• Resolution: FIXED
• Component: DOM

[Kentaro Hara]

V8 implements a generational GC, but V8 cannot collect any (dependent) DOM wrapper objects in minor GC cycles. All (dependent) DOM wrapper objects have to survive two minor GC cycles, be promoted to the old space, and wait for a heavy major GC cycle. We should fix the poor behavior.

You can find more detailed discussion in bug 88834. In bug 88834, we had tried to fix the behavior by introducing a new DOM reference counting. However, we could not land the DOM reference counting because there was no definite benefit on other ports like JSC. So we started to seek for another algorithm that affects V8 and V8 binding only, with little change in WebCore/dom.

This work requires a WebKit side fix and a V8 side fix. The WebKit side fix is tracked in this bug. The V8 side fix is tracked here (https://chromiumcodereview.appspot.com/11085015/).

[Kentaro Hara]

Created attachment 167696 [details]
WIP: not for review

A detailed explanation and perf & memory evaluation results will be coming soon.

[Adam Barth]

Comment on attachment 167696 [details]
WIP: not for review

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

> Source/WebCore/bindings/v8/V8GCController.cpp:388
> +    root->ref();
> +    root->deref();

Why ref() and then deref() the root?

[Kentaro Hara]

(In reply to comment #2)
> (From update of attachment 167696 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=167696&action=review
> 
> > Source/WebCore/bindings/v8/V8GCController.cpp:388
> > +    root->ref();
> > +    root->deref();
> 
> Why ref() and then deref() the root?

That's the tricky part.

- Ideally, m_edenNodes should be Vector<RefPtr<Node>>.

- But we want to implement m_edenNodes as Vector<Node*>. This is because (1) we want to avoid the overhead of ref() and deref(), and because (2) we cannot ref() a Node at the point where we push the Node to m_edenNodes. The Node is pushed to m_edenNodes inside the Node constructor. We should not call ref() inside the Node constructor because the Node is not yet adoptRef()ed.

- In order to implement m_edenNodes as Vector<Node*>, we add the following trick:

--- If an eden bit is set on a Node, we consider that the Node is ref()ed regardless of its reference count. In other words, even if the reference count is decremented to 0, we don't call removedLastRef() as long as an eden bit is set.

--- That being said, with the trick, we might fail calling removedLastRef(). To avoid that, we need to explicitly call removedLastRef() for a root node of each DOM tree. root->ref() and root->deref() do that. In other words, if the reference count of root is 0, it will trigger removedLastRef().

[Kentaro Hara]

Created attachment 168144 [details]
Fixed all crashes

[Kentaro Hara]

No perf regression for Dromaeo DOM tests. Rather, +5% for Dromaeo/dom-modify thanks to the minor GC efforts. More detailed perf & memory results will be coming soon.

[Kentaro Hara]

The minor GC suggested by this change is sometimes more conservative and sometimes less conservative than the minor GC suggested in bug 88834. I'll investigate the statistics again for real world web sites.

[Kentaro Hara]

Created attachment 168157 [details]
pathological test cases

[Kentaro Hara]

Created attachment 169542 [details]
Updated pathological test cases

I'll upload the perf results in hours.

[Kentaro Hara]

I wrote up a design document for the GC algorithm.

A design document:
https://docs.google.com/a/google.com/document/d/16DeHrzkm3cO9XCPT1aK3Y5qgUxXB3RFmueqQWYmN2rI/edit#

Summary: First, the algorithm is politically simple in that it affects V8 and V8 binding only. Second, the algorithm is technically simple. Third, performance & memory experiments demonstrated promising results; for real world applications, minor GC cycles reclaimed a substantial amount of memory (24 MB for Facebook, 235 MB for Google Calendar) with acceptable overhead (~10 ms per minor GC cycle).

You can find more detailed results of performance & memory investigations:
https://docs.google.com/a/google.com/document/d/1h0-EsHu7T0sSMuZm5eE0r1e8sCAzY3weLvsDUpOSngE/edit#


Once the V8 side patch (https://chromiumcodereview.appspot.com/11085015/) is landed, I'd like to set r? on the WebKit patch.

[Geoffrey Garen]

> "Three months ago, we invented an algorithm to solve the problem. However, the algorithm required to change a core logic of DOM lifetime management in WebKIt. Consequently, we could not convince reviewers of other ports like JSC and failed to land the patch."

> "First, the algorithm is politically simple in that it affects V8 and V8 binding only."

Kentaro, it's a shame that this was your take-away from our review process. The WebKit Open Source project uses peer review to maintain a standard of quality in engineering. Peer review of your previous algorithms uncovered serious correctness, security, and performance problems. I personally devoted a lot of time to that peer review; so did other JSC and non-JSC WebKit engineers. *That's* why the algorithm needed improvement -- not because of some vague notion of politics.

[Adam Barth]

I think it's fair to say that the previous approach had the disadvantage that it imposed costs on users of WebKit that did not receive counterbalancing benefits.  This approach better aligns the costs and benefits.

[Kentaro Hara]

(In reply to comment #10)
> Kentaro, it's a shame that this was your take-away from our review process. The WebKit Open Source project uses peer review to maintain a standard of quality in engineering. Peer review of your previous algorithms uncovered serious correctness, security, and performance problems. I personally devoted a lot of time to that peer review; so did other JSC and non-JSC WebKit engineers. *That's* why the algorithm needed improvement -- not because of some vague notion of politics.

I didn't mean that we gave up the previous patch because you rejected the patch. I just wanted to mean that there were little benefit in other ports and thus we could not convince communities to make a change to the core logic of WebKit. I reworded the sentences in the document. I would appreciate your constructive feedbacks in bug 88834.

[Kentaro Hara]

Created attachment 172758 [details]
Patch

[WebKit Review Bot]

Comment on attachment 172758 [details]
Patch

Attachment 172758 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/14761288

[Peter Beverloo (cr-android ews)]

Comment on attachment 172758 [details]
Patch

Attachment 172758 [details] did not pass cr-android-ews (chromium-android):
Output: http://queues.webkit.org/results/14744724

[Kentaro Hara]

It looks like I need to update DEPs of bots.

[Adam Barth]

Comment on attachment 172758 [details]
Patch

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

> Source/WebCore/bindings/v8/IntrusiveDOMWrapperMap.h:51
> +        V8GCController::newWrapperBorn(key);

Oh noes!  I'm about to delete this function in order to generalize IntrusiveDOMWrapperMap to all ScriptWrappable objects.  We'll figure something out.

> Source/WebCore/bindings/v8/V8GCController.cpp:238
> +Vector<Node*> V8GCController::m_edenNodes;

Does this create a static initializer?  Typically we put these sorts of things inside functions to initialize them lazily.

> Source/WebCore/bindings/v8/V8GCController.cpp:242
> +    Vector<v8::Persistent<v8::Value>, 11> newSpaceWrappers;

11 -> ??

> Source/WebCore/bindings/v8/V8GCController.cpp:255
> +    while (true) {
> +        ASSERT(node);
> +        if (traverseStarted && node == startNode)
> +            break;
> +        traverseStarted = true;

Why not just use a do { ... } while loop?

> Source/WebCore/bindings/v8/V8GCController.cpp:265
> +            // A once traversed node is evacuated from the Eden space.

evacuated -> removed

> Source/WebCore/bindings/v8/V8GCController.cpp:280
> +        if (node->firstChild()) {
> +            node = node->firstChild();
> +            continue;
> +        }
> +        while (!node->nextSibling()) {
> +            if (!node->parentNode())
> +                break;
> +            node = node->parentNode();
> +        }
> +        if (node->parentNode())
> +            node = node->nextSibling();

Isn't there a node->traverseNext function that does this work for us?

> Source/WebCore/bindings/v8/V8GCController.cpp:286
> +    for (unsigned i = 0; i < newSpaceWrappers.size(); i++)

unsigned -> size_t

> Source/WebCore/bindings/v8/V8GCController.cpp:302
> +    if (m_edenNodes.size() <= 10000) {

10000 -> can we name this constant?

> Source/WebCore/bindings/v8/V8GCController.cpp:311
> +    minorGCPrologue();

We do the minorGCPrologue even for major GCs?

> Source/WebCore/bindings/v8/V8GCController.cpp:324
> +    for (unsigned i = 0; i < m_edenNodes.size(); i++) {

unsigned -> size_t

> Source/WebCore/bindings/v8/V8GCController.cpp:325
> +        ASSERT(m_edenNodes[i]->wrapper());

ASSERT(!m_edenNodes[i]->wrapper().IsEmpty())

[Kentaro Hara]

Created attachment 172847 [details]
patch for landing

[Kentaro Hara]

Comment on attachment 172758 [details]
Patch

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

I will wait to land the patch until I can roll out chromium-deps of the bots.

>> Source/WebCore/bindings/v8/V8GCController.cpp:238
>> +Vector<Node*> V8GCController::m_edenNodes;
> 
> Does this create a static initializer?  Typically we put these sorts of things inside functions to initialize them lazily.

Fixed, but would you check if I'm doing the right thing?

>> Source/WebCore/bindings/v8/V8GCController.cpp:242
>> +    Vector<v8::Persistent<v8::Value>, 11> newSpaceWrappers;
> 
> 11 -> ??

In a discussion somewhere, we concluded that the best number to collect nodes in a DOM tree would be 11. ContainerNode.h has "typedef Vector<RefPtr<Node>, 11> NodeVector".

>> Source/WebCore/bindings/v8/V8GCController.cpp:255
>> +        traverseStarted = true;
> 
> Why not just use a do { ... } while loop?

Done.

>> Source/WebCore/bindings/v8/V8GCController.cpp:265
>> +            // A once traversed node is evacuated from the Eden space.
> 
> evacuated -> removed

Done.

>> Source/WebCore/bindings/v8/V8GCController.cpp:280
>> +            node = node->nextSibling();
> 
> Isn't there a node->traverseNext function that does this work for us?

It's a bit different from node->traverseNextNode(). traverseNextNode() assumes that it starts traversing from the root node and ends at the root node. On the other hand, here we want to start traversing from any node until the DFS traversal comes back to the original node. Also, the above code is a bit faster than traverseNextNode().

>> Source/WebCore/bindings/v8/V8GCController.cpp:286
>> +    for (unsigned i = 0; i < newSpaceWrappers.size(); i++)
> 
> unsigned -> size_t

Done.

>> Source/WebCore/bindings/v8/V8GCController.cpp:302
>> +    if (m_edenNodes.size() <= 10000) {
> 
> 10000 -> can we name this constant?

Done.

>> Source/WebCore/bindings/v8/V8GCController.cpp:311
>> +    minorGCPrologue();
> 
> We do the minorGCPrologue even for major GCs?

Done.

>> Source/WebCore/bindings/v8/V8GCController.cpp:324
>> +    for (unsigned i = 0; i < m_edenNodes.size(); i++) {
> 
> unsigned -> size_t

Done.

>> Source/WebCore/bindings/v8/V8GCController.cpp:325
>> +        ASSERT(m_edenNodes[i]->wrapper());
> 
> ASSERT(!m_edenNodes[i]->wrapper().IsEmpty())

Done.

[Adam Barth]

Comment on attachment 172847 [details]
patch for landing

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

> Source/WebCore/bindings/v8/IntrusiveDOMWrapperMap.h:51
> +        V8GCController::newWrapperBorn(key);

newWrapperBorn sounds like it should return a new object.  Perhaps didCreateWrapperForNode ?

> Source/WebCore/bindings/v8/V8GCController.cpp:243
> +    Vector<v8::Persistent<v8::Value>, 11> newSpaceWrappers;

Can you add a comment referencing the connection between this constant and the one in ContainerNodeAlorithms?  It might be valuable to name the constant and share it that way.

> Source/WebCore/bindings/v8/V8GCController.cpp:299
> +        m_edenNodes = new Vector<Node*>();

Idiomatically we might want to write:

adoptPtr(new Vector<Node*>()).leakPtr()

That amounts to the same thing, but it makes it clear that we know that we're leaking this vector on purpose.

> Source/WebCore/bindings/v8/V8GCController.cpp:314
> +    if (isMainThreadOrGCThread() && m_edenNodes) {

Is it safe to touch m_edenNodes on the GC thread?

> Source/WebCore/bindings/v8/V8GCController.cpp:324
> +            ASSERT((*m_edenNodes)[i]->wrapper().IsEmpty());

(*m_edenNodes)[i] can bet written nicely as m_edenNodes->at(i)

[Kentaro Hara]

Created attachment 172962 [details]
patch for landing

[Kentaro Hara]

All comments addressed. Thanks.

[WebKit Review Bot]

Comment on attachment 172962 [details]
patch for landing

Rejecting attachment 172962 [details] from commit-queue.

Failed to run "['/mnt/git/webkit-commit-queue/Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '-..." exit_code: 2

Last 500 characters of output:
ntroller.o
Source/WebCore/bindings/v8/V8GCController.cpp: In function 'void WebCore::gcTree(WebCore::Node*)':
Source/WebCore/bindings/v8/V8GCController.cpp:281: error: 'struct v8::Persistent<v8::Value>' has no member named 'MarkPartiallyDependent'
  CXX(target) out/Release/obj.target/webcore_remaining/Source/WebCore/bindings/v8/V8HiddenPropertyName.o
make: *** [out/Release/obj.target/webcore_remaining/Source/WebCore/bindings/v8/V8GCController.o] Error 1
make: *** Waiting for unfinished jobs....

Full output: http://queues.webkit.org/results/14763483

[Kentaro Hara]

ah, the V8 roll was reverted. I need to wait for the next V8 roll.

[Peter Beverloo (cr-android ews)]

Comment on attachment 172962 [details]
patch for landing

Attachment 172962 [details] did not pass cr-android-ews (chromium-android):
Output: http://queues.webkit.org/results/14763533

[WebKit Review Bot]

Comment on attachment 172962 [details]
patch for landing

Attachment 172962 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/14762734

[Adam Barth]

Comment on attachment 172962 [details]
patch for landing

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

> Source/WebCore/bindings/v8/DOMDataStore.h:114
> +        wrapper.MakeWeak(object, weakCallbackForNode);

We don't need to introduce weakCallbackForNode.  Instead, we can just pass static_cast<ScriptWrappable*>(object) as the first argument.

[Kentaro Hara]

(In reply to comment #27)
> We don't need to introduce weakCallbackForNode.  Instead, we can just pass static_cast<ScriptWrappable*>(object) as the first argument.

Will fix. It looks like the V8 roll is not yet done.

[Kentaro Hara]

The V8 roll including the V8 side patch was again reverted... Stay tuned.

[Kentaro Hara]

Created attachment 174092 [details]
patch for landing

[WebKit Review Bot]

Comment on attachment 174092 [details]
patch for landing

Clearing flags on attachment: 174092

Committed r134569: <http://trac.webkit.org/changeset/134569>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.