[heap] Black allocation.

[heap] Black allocation.

When black allocation is active, all objects allocated in old space are allocated black. Important: With that change, you cannot assume anymore that new objects are white right after their allocation. Currently, black allocation is enabled when incremental marking is started.

This feature can be turned off via flag: --noblack-allocation

BUG=chromium:561449
LOG=n

Committed: https://crrev.com/ad51e8b1e8d6b28604ec9c9569f49f5c29f868e6
Cr-Commit-Position: refs/heads/master@{#34743}

[Hannes Payer (out of office), 2016-01-29 09:04:18]

Description was changed from

==========
[heap] Black allocation.

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

to

==========
[heap] Black allocation.

Missing pieces to fully support black allocation:
- Handle all of code space, c.f. todo
- Handle new space

BUG=chromium:561449
==========

[Hannes Payer (out of office), 2016-01-29 09:26:30]

Description was changed from

==========
[heap] Black allocation.

Missing pieces to fully support black allocation:
- Handle all of code space, c.f. todo
- Handle new space

BUG=chromium:561449
==========

to

==========
[heap] Black allocation.

Missing pieces to fully support black allocation:
- Handle all of code space, c.f. todo
- Handle new space

BUG=chromium:561449
LOG=n
==========

[Hannes Payer (out of office), 2016-02-04 14:11:16]

Description was changed from

==========
[heap] Black allocation.

Missing pieces to fully support black allocation:
- Handle all of code space, c.f. todo
- Handle new space

BUG=chromium:561449
LOG=n
==========

to

==========
[heap] Black allocation.

When black allocation is active, all objects allocated in old space are
allocated black. Important: With that change, you cannot assume anymore that new
objects are white right after their allocation. Currently, black allocation is
enabled when incremental marking is started.

This feature can be turned off via flag: --noblack-allocation

BUG=chromium:561449
LOG=n
==========

[Hannes Payer (out of office), 2016-02-04 14:11:17]

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

[Michael Lippautz, 2016-02-04 17:59:51]

Two questions, otherwise just nits. 

Well spread out over the whole code base ;)

https://codereview.chromium.org/1420423009/diff/380001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1420423009/diff/380001/src/heap/heap.cc#newco...
src/heap/heap.cc:3376: // We have to iterate over over the object and process
its pointers when
nit: -over

https://codereview.chromium.org/1420423009/diff/380001/src/heap/heap.cc#newco...
src/heap/heap.cc:4570: void Heap::IteratePointersToFromSpace(HeapObject* target,
int size,
This naming is now also misleading.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/incremental-m...
File src/heap/incremental-marking.cc (right):

https://codereview.chromium.org/1420423009/diff/380001/src/heap/incremental-m...
src/heap/incremental-marking.cc:604: StartBlackAllocation();
Did you try to enable it later than that?

https://codereview.chromium.org/1420423009/diff/380001/src/heap/incremental-m...
src/heap/incremental-marking.cc:826: MarkBit mark_bit_dest =
Marking::MarkBitFrom(dest);
Please provide more context on this fixup.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/incremental-m...
src/heap/incremental-marking.cc:927: if (state() == MARKING ||
Scary...

https://codereview.chromium.org/1420423009/diff/380001/src/heap/mark-compact.cc
File src/heap/mark-compact.cc (right):

https://codereview.chromium.org/1420423009/diff/380001/src/heap/mark-compact....
src/heap/mark-compact.cc:2932: // easiliy. We just return true but do not set
the out_object.
.. forcing additional checks in the caller.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/mark-compact....
src/heap/mark-compact.cc:3056: // If the slot is on a black page, the object
will be live.
Technically, the object could've been left/right trimmed and the slot will not
be live anymore (?) The memory will be unusable until the next cycle so this is
sane.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/mark-compact.h
File src/heap/mark-compact.h (right):

https://codereview.chromium.org/1420423009/diff/380001/src/heap/mark-compact....
src/heap/mark-compact.h:163: if
(Page::FromAddress(to->address())->IsFlagSet(Page::BLACK_PAGE))
Why are you not transferring the markbit here (although you return true).

https://codereview.chromium.org/1420423009/diff/380001/src/heap/spaces.h
File src/heap/spaces.h (right):

https://codereview.chromium.org/1420423009/diff/380001/src/heap/spaces.h#newc...
src/heap/spaces.h:320: // cannot be iterated because it is not swept.
Add: Live bytes are also not updated on those pages.

https://codereview.chromium.org/1420423009/diff/380001/test/cctest/heap/test-...
File test/cctest/heap/test-heap.cc (right):

https://codereview.chromium.org/1420423009/diff/380001/test/cctest/heap/test-...
test/cctest/heap/test-heap.cc:4944: heap->CollectAllGarbage();
Please also add comment for black allocated objects here.

[Hannes Payer (out of office), 2016-02-06 08:50:16]

https://codereview.chromium.org/1420423009/diff/380001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1420423009/diff/380001/src/heap/heap.cc#newco...
src/heap/heap.cc:3376: // We have to iterate over over the object and process
its pointers when
On 2016/02/04 17:59:50, Michael Lippautz wrote:
> nit: -over

Done.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/heap.cc#newco...
src/heap/heap.cc:4570: void Heap::IteratePointersToFromSpace(HeapObject* target,
int size,
On 2016/02/04 17:59:50, Michael Lippautz wrote:
> This naming is now also misleading.

Done.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/incremental-m...
File src/heap/incremental-marking.cc (right):

https://codereview.chromium.org/1420423009/diff/380001/src/heap/incremental-m...
src/heap/incremental-marking.cc:604: StartBlackAllocation();
On 2016/02/04 17:59:50, Michael Lippautz wrote:
> Did you try to enable it later than that?

Nope, but it is possible to enable from start of marking time until finalization
of marking. We can play with that heuristic later.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/incremental-m...
src/heap/incremental-marking.cc:826: MarkBit mark_bit_dest =
Marking::MarkBitFrom(dest);
On 2016/02/04 17:59:50, Michael Lippautz wrote:
> Please provide more context on this fixup.

When I follow the forwarding pointer while processing the promoted objects, I
may be able to avoid that case here.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/incremental-m...
src/heap/incremental-marking.cc:927: if (state() == MARKING ||
On 2016/02/04 17:59:51, Michael Lippautz wrote:
> Scary...

Simplified the check. COMPLETE and non-empty marking deque may only happen if
scavenges are forced from cctests after completing incremental marking.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/mark-compact.cc
File src/heap/mark-compact.cc (right):

https://codereview.chromium.org/1420423009/diff/380001/src/heap/mark-compact....
src/heap/mark-compact.cc:2932: // easiliy. We just return true but do not set
the out_object.
On 2016/02/04 17:59:51, Michael Lippautz wrote:
> .. forcing additional checks in the caller.

I just realized that we always have to return an out_object when we return true,
because we have to check if the recorded slot is still valid. It may not be
valid because of double unboxing. I don't see a clean and efficient way to fix
that now.

A) Dirty fix: turn off double unboxing when black allocation is one. Not sure if
we actually can do that.
B) Wait for new remembered set filtering implementation. There, we do not have
to scan the object anymore.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/mark-compact....
src/heap/mark-compact.cc:3056: // If the slot is on a black page, the object
will be live.
On 2016/02/04 17:59:51, Michael Lippautz wrote:
> Technically, the object could've been left/right trimmed and the slot will not
> be live anymore (?) The memory will be unusable until the next cycle so this
is
> sane.

Correct, left and right trimming is not an issue. But there are other problems
see comment above.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/mark-compact.h
File src/heap/mark-compact.h (right):

https://codereview.chromium.org/1420423009/diff/380001/src/heap/mark-compact....
src/heap/mark-compact.h:163: if
(Page::FromAddress(to->address())->IsFlagSet(Page::BLACK_PAGE))
On 2016/02/04 17:59:51, Michael Lippautz wrote:
> Why are you not transferring the markbit here (although you return true).

Because to lives on a black page. It will always be black.

https://codereview.chromium.org/1420423009/diff/380001/src/heap/spaces.h
File src/heap/spaces.h (right):

https://codereview.chromium.org/1420423009/diff/380001/src/heap/spaces.h#newc...
src/heap/spaces.h:320: // cannot be iterated because it is not swept.
On 2016/02/04 17:59:51, Michael Lippautz wrote:
> Add: Live bytes are also not updated on those pages.

Done.

https://codereview.chromium.org/1420423009/diff/380001/test/cctest/heap/test-...
File test/cctest/heap/test-heap.cc (right):

https://codereview.chromium.org/1420423009/diff/380001/test/cctest/heap/test-...
test/cctest/heap/test-heap.cc:4944: heap->CollectAllGarbage();
On 2016/02/04 17:59:51, Michael Lippautz wrote:
> Please also add comment for black allocated objects here.

Note that I changed the test case.

[ulan, 2016-02-10 10:27:39]

Exciting stuff! High level comments:

https://codereview.chromium.org/1420423009/diff/420001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1420423009/diff/420001/src/heap/heap.cc#newco...
src/heap/heap.cc:1181: perform_gc = true;
How about not starting black allocation if deserializer is enabled?
Otherwise, we cannot guarantee progress.

https://codereview.chromium.org/1420423009/diff/420001/src/heap/heap.cc#newco...
src/heap/heap.cc:3380: incremental_marking()->IterateBlackCode(new_code);
How about making this more generic "allocation barrier":
incremental_marking()->RecordUnsafeAllocation(new_code).

Unsafe allocation would be any allocation in old generation that skips write
barriers.

RecordUnsafeAllocation would check black_allocation() and BLACK_PAGE, invoke the
marking visitor and in debug mode check the marking invariant.

https://codereview.chromium.org/1420423009/diff/420001/src/heap/heap.cc#newco...
src/heap/heap.cc:4531: IncrementalMarking::MarkObject(this,
HeapObject::cast(target));
This ignores all the special handling that the marking visitor might have for
this object. In particular weak slots and maintaining  global lists, e.g.
JSFunction list for code flushing.

We need to either make marking vistiors of all new space object trivial or
invoke the non-trivial marking visitor on promotion to black pages.

https://codereview.chromium.org/1420423009/diff/420001/src/heap/mark-compact.cc
File src/heap/mark-compact.cc (right):

https://codereview.chromium.org/1420423009/diff/420001/src/heap/mark-compact....
src/heap/mark-compact.cc:149: }
It would be great to verify coloring invariant for black pages too.

How about adding black page handling to VerifyMarking? 
On a black page it wouldn't use marking bits but instead advance the current
pointer by current + object->Size() and stops before the linear allocation area.

https://codereview.chromium.org/1420423009/diff/420001/src/objects-inl.h
File src/objects-inl.h (right):

https://codereview.chromium.org/1420423009/diff/420001/src/objects-inl.h#newc...
src/objects-inl.h:2046: ? UPDATE_WRITE_BARRIER
Invoking the marking visitor of the weak cell might be more consistent.

The same holds for TransitionArray, WeakCollection, JSArrayBuffer, JSFunction,
SharedFunctionInfo, Map

[Hannes Payer (out of office), 2016-02-11 18:18:07]

https://codereview.chromium.org/1420423009/diff/420001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1420423009/diff/420001/src/heap/heap.cc#newco...
src/heap/heap.cc:1181: perform_gc = true;
On 2016/02/10 10:27:39, ulan wrote:
> How about not starting black allocation if deserializer is enabled?
> Otherwise, we cannot guarantee progress.

I don't think it would be an issue since there should be enough slack between a
fresh GC and reaching the allocation limit. Anyhow, let's play safe. I changed
the black allocation start logic. When the serializer is enabled, we don't start
it. We may start it later when performing an incremental marking step.

https://codereview.chromium.org/1420423009/diff/420001/src/heap/heap.cc#newco...
src/heap/heap.cc:3380: incremental_marking()->IterateBlackCode(new_code);
On 2016/02/10 10:27:39, ulan wrote:
> How about making this more generic "allocation barrier":
> incremental_marking()->RecordUnsafeAllocation(new_code).
> 
> Unsafe allocation would be any allocation in old generation that skips write
> barriers.
> 
> RecordUnsafeAllocation would check black_allocation() and BLACK_PAGE, invoke
the
> marking visitor and in debug mode check the marking invariant.

I like it. It will be also called when processing the promotion queue. I call it
IterateBlackObject.

https://codereview.chromium.org/1420423009/diff/420001/src/heap/heap.cc#newco...
src/heap/heap.cc:4531: IncrementalMarking::MarkObject(this,
HeapObject::cast(target));
On 2016/02/10 10:27:39, ulan wrote:
> This ignores all the special handling that the marking visitor might have for
> this object. In particular weak slots and maintaining  global lists, e.g.
> JSFunction list for code flushing.
> 
> We need to either make marking vistiors of all new space object trivial or
> invoke the non-trivial marking visitor on promotion to black pages.

Weakness during black allocation is special, i.e. in the current GC a weak
references becomes strong (c.f. WeakCell::initialize). However, missing other
side effects of the visitors will be problematic. I decided to do another
iteration over the objects using the regular visitor. Ideally, we would just do
one pass over the object, not two. I left a TODO for a follow-up CL.

https://codereview.chromium.org/1420423009/diff/420001/src/heap/mark-compact.cc
File src/heap/mark-compact.cc (right):

https://codereview.chromium.org/1420423009/diff/420001/src/heap/mark-compact....
src/heap/mark-compact.cc:149: }
On 2016/02/10 10:27:39, ulan wrote:
> It would be great to verify coloring invariant for black pages too.
> 
> How about adding black page handling to VerifyMarking? 
> On a black page it wouldn't use marking bits but instead advance the current
> pointer by current + object->Size() and stops before the linear allocation
area.

Done.

https://codereview.chromium.org/1420423009/diff/420001/src/objects-inl.h
File src/objects-inl.h (right):

https://codereview.chromium.org/1420423009/diff/420001/src/objects-inl.h#newc...
src/objects-inl.h:2046: ? UPDATE_WRITE_BARRIER
On 2016/02/10 10:27:39, ulan wrote:
> Invoking the marking visitor of the weak cell might be more consistent.
> 
> The same holds for TransitionArray, WeakCollection, JSArrayBuffer, JSFunction,
> SharedFunctionInfo, Map

As discussed offline, this change was done on purpose. WeakCells on black pages
become strong. If floating garbage increases significantly because of that
change, we have to look into that problem.

[ulan, 2016-02-16 10:38:09]

Looks good!

How do we ensure that JSWeakCollections and ArrayBuffers are not pretenured?

https://codereview.chromium.org/1420423009/diff/590001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1420423009/diff/590001/src/heap/heap.cc#newco...
src/heap/heap.cc:4583: // TODO(hpayer): Right now we are also going to process
black objects
This could be a problem if the non-pure marking visitor is not idempotent. For
example, this could lead to registering the same object twice in the same list.

https://codereview.chromium.org/1420423009/diff/590001/src/heap/heap.cc#newco...
src/heap/heap.cc:4586:
heap_->incremental_marking()->IterateBlackObject(target_);
I think this should be called in line 4546, not here, because we want to invoke
marking visitor once per promoted object if black allocation is on.

[Hannes Payer (out of office), 2016-03-11 14:20:48]

https://codereview.chromium.org/1420423009/diff/590001/src/heap/heap.cc
File src/heap/heap.cc (right):

https://codereview.chromium.org/1420423009/diff/590001/src/heap/heap.cc#newco...
src/heap/heap.cc:4583: // TODO(hpayer): Right now we are also going to process
black objects
On 2016/02/16 10:38:09, ulan wrote:
> This could be a problem if the non-pure marking visitor is not idempotent. For
> example, this could lead to registering the same object twice in the same
list.

As discussed offline, we are not going to process already marked black objects
(in new space). Done.

https://codereview.chromium.org/1420423009/diff/590001/src/heap/heap.cc#newco...
src/heap/heap.cc:4586:
heap_->incremental_marking()->IterateBlackObject(target_);
On 2016/02/16 10:38:09, ulan wrote:
> I think this should be called in line 4546, not here, because we want to
invoke
> marking visitor once per promoted object if black allocation is on.

Done.

[Hannes Payer (out of office), 2016-03-11 14:21:09]

hpayer@chromium.org changed reviewers:
+ yangguo@chromium.org

[Yang, 2016-03-11 14:24:08]

On 2016/03/11 14:21:10, Hannes Payer - slow wrote:

serializer lgtm, if RegisterReservationsForBlackAllocation does what I think it
does, and if you fix the merge issue.

[Hannes Payer (out of office), 2016-03-11 15:49:36]

https://codereview.chromium.org/1420423009/diff/670001/src/heap/mark-compact-...
File src/heap/mark-compact-inl.h (right):

https://codereview.chromium.org/1420423009/diff/670001/src/heap/mark-compact-...
src/heap/mark-compact-inl.h:146: if (T == kGreyObjectsOnBlackPage) {
We need that when we transition from black to grey and overflow the marking
deque. May happen when we call RecordWrites.

[ulan, 2016-03-14 09:56:57]

LGTM

[Hannes Payer (out of office), 2016-03-14 14:00:12]

The CQ bit was checked by hpayer@chromium.org

[Hannes Payer (out of office), 2016-03-14 14:00:12]

The patchset sent to the CQ was uploaded after l-g-t-m from
yangguo@chromium.org, ulan@chromium.org
Link to the patchset: https://codereview.chromium.org/1420423009/#ps750001
(title: " ")

[commit-bot: I haz the power, 2016-03-14 14:00:20]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1420423009/750001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1420423009/750001

[Hannes Payer (out of office), 2016-03-14 14:01:09]

The CQ bit was unchecked by hpayer@chromium.org

[Hannes Payer (out of office), 2016-03-14 14:01:15]

The CQ bit was checked by hpayer@chromium.org

[commit-bot: I haz the power, 2016-03-14 14:01:21]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1420423009/750001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1420423009/750001

[commit-bot: I haz the power, 2016-03-14 14:02:27]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-03-14 14:02:29]

Failed to apply the patch.

[commit-bot: I haz the power, 2016-03-14 14:03:05]

Description was changed from

==========
[heap] Black allocation.

When black allocation is active, all objects allocated in old space are
allocated black. Important: With that change, you cannot assume anymore that new
objects are white right after their allocation. Currently, black allocation is
enabled when incremental marking is started.

This feature can be turned off via flag: --noblack-allocation

BUG=chromium:561449
LOG=n
==========

to

==========
[heap] Black allocation.

When black allocation is active, all objects allocated in old space are
allocated black. Important: With that change, you cannot assume anymore that new
objects are white right after their allocation. Currently, black allocation is
enabled when incremental marking is started.

This feature can be turned off via flag: --noblack-allocation

BUG=chromium:561449
LOG=n

Committed: https://crrev.com/ad51e8b1e8d6b28604ec9c9569f49f5c29f868e6
Cr-Commit-Position: refs/heads/master@{#34743}
==========

[commit-bot: I haz the power, 2016-03-14 14:03:07]

Patchset 39 (id:??) landed as
https://crrev.com/ad51e8b1e8d6b28604ec9c9569f49f5c29f868e6
Cr-Commit-Position: refs/heads/master@{#34743}