Bug 98725 - [V8] DOM wrapper objects should be collected in minor GC cycles
Summary: [V8] DOM wrapper objects should be collected in minor GC cycles
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Kentaro Hara
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2012-10-08 23:21 PDT by Kentaro Hara
Modified: 2012-11-14 00:55 PST (History)
10 users (show)

See Also:


Attachments
WIP: not for review (11.47 KB, patch)
2012-10-08 23:27 PDT, Kentaro Hara
no flags Details | Formatted Diff | Diff
Fixed all crashes (10.93 KB, patch)
2012-10-10 22:16 PDT, Kentaro Hara
no flags Details | Formatted Diff | Diff
pathological test cases (2.33 KB, text/html)
2012-10-11 01:04 PDT, Kentaro Hara
no flags Details
Updated pathological test cases (2.25 KB, text/html)
2012-10-18 21:33 PDT, Kentaro Hara
no flags Details
Patch (9.90 KB, patch)
2012-11-07 04:38 PST, Kentaro Hara
no flags Details | Formatted Diff | Diff
patch for landing (10.14 KB, patch)
2012-11-07 11:28 PST, Kentaro Hara
no flags Details | Formatted Diff | Diff
patch for landing (12.03 KB, patch)
2012-11-08 01:43 PST, Kentaro Hara
no flags Details | Formatted Diff | Diff
patch for landing (11.17 KB, patch)
2012-11-14 00:24 PST, Kentaro Hara
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Kentaro Hara 2012-10-08 23:21:03 PDT
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/).
Comment 1 Kentaro Hara 2012-10-08 23:27:54 PDT
Created attachment 167696 [details]
WIP: not for review

A detailed explanation and perf & memory evaluation results will be coming soon.
Comment 2 Adam Barth 2012-10-09 00:26:44 PDT
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?
Comment 3 Kentaro Hara 2012-10-09 00:43:27 PDT
(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().
Comment 4 Kentaro Hara 2012-10-10 22:16:38 PDT
Created attachment 168144 [details]
Fixed all crashes
Comment 5 Kentaro Hara 2012-10-10 22:18:11 PDT
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.
Comment 6 Kentaro Hara 2012-10-10 22:22:52 PDT
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.
Comment 7 Kentaro Hara 2012-10-11 01:04:23 PDT
Created attachment 168157 [details]
pathological test cases
Comment 8 Kentaro Hara 2012-10-18 21:33:56 PDT
Created attachment 169542 [details]
Updated pathological test cases

I'll upload the perf results in hours.
Comment 9 Kentaro Hara 2012-10-19 02:52:43 PDT
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.
Comment 10 Geoffrey Garen 2012-10-19 12:11:03 PDT
> "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.
Comment 11 Adam Barth 2012-10-19 12:50:59 PDT
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.
Comment 12 Kentaro Hara 2012-10-19 20:25:06 PDT
(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.
Comment 13 Kentaro Hara 2012-11-07 04:38:48 PST
Created attachment 172758 [details]
Patch
Comment 14 WebKit Review Bot 2012-11-07 05:10:47 PST
Comment on attachment 172758 [details]
Patch

Attachment 172758 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/14761288
Comment 15 Peter Beverloo (cr-android ews) 2012-11-07 05:19:53 PST
Comment on attachment 172758 [details]
Patch

Attachment 172758 [details] did not pass cr-android-ews (chromium-android):
Output: http://queues.webkit.org/results/14744724
Comment 16 Kentaro Hara 2012-11-07 05:31:05 PST
It looks like I need to update DEPs of bots.
Comment 17 Adam Barth 2012-11-07 09:52:49 PST
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())
Comment 18 Kentaro Hara 2012-11-07 11:28:42 PST
Created attachment 172847 [details]
patch for landing
Comment 19 Kentaro Hara 2012-11-07 11:30:01 PST
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.
Comment 20 Adam Barth 2012-11-07 11:38:14 PST
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)
Comment 21 Kentaro Hara 2012-11-08 01:43:03 PST
Created attachment 172962 [details]
patch for landing
Comment 22 Kentaro Hara 2012-11-08 01:46:06 PST
All comments addressed. Thanks.
Comment 23 WebKit Review Bot 2012-11-08 02:22:42 PST
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
Comment 24 Kentaro Hara 2012-11-08 02:36:13 PST
ah, the V8 roll was reverted. I need to wait for the next V8 roll.
Comment 25 Peter Beverloo (cr-android ews) 2012-11-08 04:19:31 PST
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
Comment 26 WebKit Review Bot 2012-11-08 10:08:52 PST
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
Comment 27 Adam Barth 2012-11-08 12:50:31 PST
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.
Comment 28 Kentaro Hara 2012-11-11 16:14:30 PST
(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.
Comment 29 Kentaro Hara 2012-11-13 01:10:30 PST
The V8 roll including the V8 side patch was again reverted... Stay tuned.
Comment 30 Kentaro Hara 2012-11-14 00:24:01 PST
Created attachment 174092 [details]
patch for landing
Comment 31 WebKit Review Bot 2012-11-14 00:55:20 PST
Comment on attachment 174092 [details]
patch for landing

Clearing flags on attachment: 174092

Committed r134569: <http://trac.webkit.org/changeset/134569>
Comment 32 WebKit Review Bot 2012-11-14 00:55:26 PST
All reviewed patches have been landed.  Closing bug.