[heap] Implement simple concurrent marking deque.

[heap] Implement simple concurrent marking deque.

This patch adds a concurrent marking deque that exposes the same interface
for the main thread as the existing marking deque.

The matching interface makes the concurrent marking deque a drop-in
replacement for the sequential marking deque without any change in
mark-compactor and incremental marker.

BUG=chromium:694255
Review-Url: https://codereview.chromium.org/2810893002
Cr-Commit-Position: refs/heads/master@{#45042}
Committed: https://chromium.googlesource.com/v8/v8/+/c6816cd87d1d31dd78218a5f004d6db6202fb1fc

[ulan, 2017-04-27 17:48:55]

Description was changed from

==========
[heap] Add concurrent marking deque.

BUG=
==========

to

==========
[heap] Implement simple concurrent marking deque.

This patch add a concurrent marking deque that exposes the same interface
for the main thread as the existing marking deque.
The existing marking deque is renamed to SequentalMarkingDeque and
extracted into a separate file.

The matching interface makes the concurrent marking deque a drop-in
replacement for the sequential marking deque without any change in
mark-compactor and incremental marker.

BUG=chromium:694255
==========

[ulan, 2017-04-27 17:49:38]

ulan@chromium.org changed reviewers:
+ hpayer@chromium.org, mlippautz@chromium.org

[ulan, 2017-04-27 17:49:39]

ptal

https://codereview.chromium.org/2810893002/diff/80001/src/heap/incremental-ma...
File src/heap/incremental-marking.cc (left):

https://codereview.chromium.org/2810893002/diff/80001/src/heap/incremental-ma...
src/heap/incremental-marking.cc:772: int current = marking_deque->bottom();
We no longer can assume contiguous structure of the marking deque.
MarkingDeque::Update method abstracts away iteration, filtering and compaction
of the marking deque.

https://codereview.chromium.org/2810893002/diff/80001/src/heap/incremental-ma...
File src/heap/incremental-marking.cc (right):

https://codereview.chromium.org/2810893002/diff/80001/src/heap/incremental-ma...
src/heap/incremental-marking.cc:727:
heap_->mark_compact_collector()->marking_deque()->Size() +
This changes behavior.

https://codereview.chromium.org/2810893002/diff/80001/src/heap/mark-compact.cc
File src/heap/mark-compact.cc (left):

https://codereview.chromium.org/2810893002/diff/80001/src/heap/mark-compact.c...
src/heap/mark-compact.cc:2238: void MarkingDeque::SetUp() {
This is moved to sequential-marking-deque.cc

https://codereview.chromium.org/2810893002/diff/80001/src/heap/mark-compact.h
File src/heap/mark-compact.h (left):

https://codereview.chromium.org/2810893002/diff/80001/src/heap/mark-compact.h...
src/heap/mark-compact.h:111: //
----------------------------------------------------------------------------
This is moved to sequential-marking-deque.h

[Michael Lippautz, 2017-05-02 09:29:11]

In general this already looks good to me.

Would it make things easier if you created 3 CLs:
- Separating out MarkingDeque and adding the Update() function
- Changing the behavior when computing bytes
- Plugging in the concurrent marking deque
?

[Michael Lippautz, 2017-05-02 09:39:31]

https://codereview.chromium.org/2810893002/diff/100001/test/cctest/heap/test-...
File test/cctest/heap/test-mark-compact.cc (right):

https://codereview.chromium.org/2810893002/diff/100001/test/cctest/heap/test-...
test/cctest/heap/test-mark-compact.cc:56: TEST(ConcurrentMarkingDeque) {
nit: Could be a unit test.

https://codereview.chromium.org/2810893002/diff/100001/test/cctest/heap/test-...
test/cctest/heap/test-mark-compact.cc:76: TEST(SequentialMarkingDeque) {
nit: Similarly, this could also be a unit test.

[ulan, 2017-05-02 13:18:27]

Description was changed from

==========
[heap] Implement simple concurrent marking deque.

This patch add a concurrent marking deque that exposes the same interface
for the main thread as the existing marking deque.
The existing marking deque is renamed to SequentalMarkingDeque and
extracted into a separate file.

The matching interface makes the concurrent marking deque a drop-in
replacement for the sequential marking deque without any change in
mark-compactor and incremental marker.

BUG=chromium:694255
==========

to

==========
[heap] Implement simple concurrent marking deque.

This patch add a concurrent marking deque that exposes the same interface
for the main thread as the existing marking deque.

The matching interface makes the concurrent marking deque a drop-in
replacement for the sequential marking deque without any change in
mark-compactor and incremental marker.

BUG=chromium:694255
==========

[ulan, 2017-05-02 13:19:53]

Thanks, Michael.

I extracted smaller unrelated parts into separate CLs.

This CL now is only about adding concurrent marking deque.

https://codereview.chromium.org/2810893002/diff/100001/test/cctest/heap/test-...
File test/cctest/heap/test-mark-compact.cc (right):

https://codereview.chromium.org/2810893002/diff/100001/test/cctest/heap/test-...
test/cctest/heap/test-mark-compact.cc:56: TEST(ConcurrentMarkingDeque) {
On 2017/05/02 09:39:31, Michael Lippautz wrote:
> nit: Could be a unit test.

Done. Converted it to unit test.

https://codereview.chromium.org/2810893002/diff/100001/test/cctest/heap/test-...
test/cctest/heap/test-mark-compact.cc:76: TEST(SequentialMarkingDeque) {
On 2017/05/02 09:39:31, Michael Lippautz wrote:
> nit: Similarly, this could also be a unit test.

I am keeping it here because it depends on cancelable tasks and will be removed
in future anyway.

[Michael Lippautz, 2017-05-02 13:30:20]

LGTM.

[ulan, 2017-05-02 14:29:29]

Description was changed from

==========
[heap] Implement simple concurrent marking deque.

This patch add a concurrent marking deque that exposes the same interface
for the main thread as the existing marking deque.

The matching interface makes the concurrent marking deque a drop-in
replacement for the sequential marking deque without any change in
mark-compactor and incremental marker.

BUG=chromium:694255
==========

to

==========
[heap] Implement simple concurrent marking deque.

This patch adds a concurrent marking deque that exposes the same interface
for the main thread as the existing marking deque.

The matching interface makes the concurrent marking deque a drop-in
replacement for the sequential marking deque without any change in
mark-compactor and incremental marker.

BUG=chromium:694255
==========

[Hannes Payer (out of office), 2017-05-02 15:53:20]

lgtm

https://codereview.chromium.org/2810893002/diff/160001/src/heap/concurrent-ma...
File src/heap/concurrent-marking-deque.h (right):

https://codereview.chromium.org/2810893002/diff/160001/src/heap/concurrent-ma...
src/heap/concurrent-marking-deque.h:24: // (main and concurrent) and two deques
(shared and bailout).
it is implemented using two deques.

https://codereview.chromium.org/2810893002/diff/160001/src/heap/concurrent-ma...
File src/heap/concurrent-marking.cc (right):

https://codereview.chromium.org/2810893002/diff/160001/src/heap/concurrent-ma...
src/heap/concurrent-marking.cc:160: deque_(deque),
Policy question: Should we free the passed in deque somewhere or are we planning
to always use the same instance?

[ulan, 2017-05-02 16:33:04]

https://codereview.chromium.org/2810893002/diff/160001/src/heap/concurrent-ma...
File src/heap/concurrent-marking-deque.h (right):

https://codereview.chromium.org/2810893002/diff/160001/src/heap/concurrent-ma...
src/heap/concurrent-marking-deque.h:24: // (main and concurrent) and two deques
(shared and bailout).
On 2017/05/02 15:53:20, Hannes Payer wrote:
> it is implemented using two deques.

Done.

https://codereview.chromium.org/2810893002/diff/160001/src/heap/concurrent-ma...
File src/heap/concurrent-marking.cc (right):

https://codereview.chromium.org/2810893002/diff/160001/src/heap/concurrent-ma...
src/heap/concurrent-marking.cc:160: deque_(deque),
On 2017/05/02 15:53:20, Hannes Payer wrote:
> Policy question: Should we free the passed in deque somewhere or are we
planning
> to always use the same instance?

The caller is responsible for free the deque since it is shared between two
markers: incremental and concurrent.

[ulan, 2017-05-02 16:33:10]

The CQ bit was checked by ulan@chromium.org

[ulan, 2017-05-02 16:33:10]

The patchset sent to the CQ was uploaded after l-g-t-m from hpayer@chromium.org,
mlippautz@chromium.org
Link to the patchset: https://codereview.chromium.org/2810893002/#ps180001
(title: "Fix comment")

[commit-bot: I haz the power, 2017-05-02 16:33:13]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-05-02 17:03:33]

CQ is committing da patch.

Bot data: {"patchset_id": 180001, "attempt_start_ts": 1493742790097650,
"parent_rev": "66f69540641f47c7078e77daf649788d6c50670f", "commit_rev":
"c6816cd87d1d31dd78218a5f004d6db6202fb1fc"}

[commit-bot: I haz the power, 2017-05-02 17:03:40]

Description was changed from

==========
[heap] Implement simple concurrent marking deque.

This patch adds a concurrent marking deque that exposes the same interface
for the main thread as the existing marking deque.

The matching interface makes the concurrent marking deque a drop-in
replacement for the sequential marking deque without any change in
mark-compactor and incremental marker.

BUG=chromium:694255
==========

to

==========
[heap] Implement simple concurrent marking deque.

This patch adds a concurrent marking deque that exposes the same interface
for the main thread as the existing marking deque.

The matching interface makes the concurrent marking deque a drop-in
replacement for the sequential marking deque without any change in
mark-compactor and incremental marker.

BUG=chromium:694255

Review-Url: https://codereview.chromium.org/2810893002
Cr-Commit-Position: refs/heads/master@{#45042}
Committed:
https://chromium.googlesource.com/v8/v8/+/c6816cd87d1d31dd78218a5f004d6db6202...
==========

[commit-bot: I haz the power, 2017-05-02 17:03:41]

Committed patchset #10 (id:180001) as
https://chromium.googlesource.com/v8/v8/+/c6816cd87d1d31dd78218a5f004d6db6202...

[Michael Achenbach, 2017-05-04 09:54:24]

machenbach@chromium.org changed reviewers:
+ machenbach@chromium.org

[Michael Achenbach, 2017-05-04 09:54:24]

This makes js-tests timeout on Android:
http://shortn/_aXU19j0aCE

But I assume
https://chromium.googlesource.com/v8/v8/+/c31c9ee0048b7445fb99e68c9a9c6152a0a...
might fix that? Still backlog and the bots didn't get there...

[ulan, 2017-05-04 10:03:48]

On 2017/05/04 09:54:24, Michael Achenbach wrote:
> This makes js-tests timeout on Android:
> http://shortn/_aXU19j0aCE
> 
> But I assume
>
https://chromium.googlesource.com/v8/v8/+/c31c9ee0048b7445fb99e68c9a9c6152a0a...
> might fix that? Still backlog and the bots didn't get there...

Yes, that's the fix.