Debug garbage collector does not correctly remove cross-gen garbage

Modifies the debug garbage collector (CollectAllGarbage()) to correctly remove inter-generational garbage by evacuating all of new space.

Adds tests to check if this issue has been correctly resolved.

Updates the WeakProperty_PreserveCrossGen test to call for one new and one old space collection instead of CollectAllGarbage(). Otherwise, all weak properties are swept as garbage.

DETAILS:

ISSUE

Specifically, the following arrangements in a heap resulted
in garbage surviving a GC.

- Dead object in old space pointing to dead object in new space results
  in the new space object surviving.
- A cycle between two dead objects, one in each space, results in the
  cycle surviving until all objects are in the old space.

BUG=
R=rmacnak@google.com

Committed: https://github.com/dart-lang/sdk/commit/abf40fc8d221530cf589a7d7af11324fed48a823

[rmacnak, 2017-06-08 21:23:47]

rmacnak@google.com changed reviewers:
+ rmacnak@google.com

[rmacnak, 2017-06-08 21:23:48]

https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc
File runtime/vm/gc_marker.cc (right):

https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
runtime/vm/gc_marker.cc:266: ASSERT(raw_weak->IsOldObject());
Update (visiting new-space weak properties now).

https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
runtime/vm/gc_marker.cc:277: if (raw_key->IsHeapObject() &&
raw_key->IsOldObject() &&
Update (not all new-space objects are survivors)

https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
runtime/vm/gc_marker.cc:436: if (!raw_obj->IsOldObject()) {
Update (not all new-space objects are survivors)

https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
runtime/vm/gc_marker.cc:528: if (raw_obj->IsOldObject() && !raw_obj->IsMarked())
{
Update (not all new-space objects are survivors)

https://codereview.chromium.org/2930943002/diff/1/runtime/vm/heap.h
File runtime/vm/heap.h (right):

https://codereview.chromium.org/2930943002/diff/1/runtime/vm/heap.h#newcode248
runtime/vm/heap.h:248: bool IsDebugCollection() { return debug_gc_in_progress_;
}
Unused

[danunez, 2017-06-08 21:32:15]

On 2017/06/08 21:23:48, rmacnak wrote:
> https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc
> File runtime/vm/gc_marker.cc (right):
> 
>
https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
> runtime/vm/gc_marker.cc:266: ASSERT(raw_weak->IsOldObject());
> Update (visiting new-space weak properties now).
> 
>
https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
> runtime/vm/gc_marker.cc:277: if (raw_key->IsHeapObject() &&
> raw_key->IsOldObject() &&
> Update (not all new-space objects are survivors)
> 
>
https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
> runtime/vm/gc_marker.cc:436: if (!raw_obj->IsOldObject()) {
> Update (not all new-space objects are survivors)
> 
>
https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
> runtime/vm/gc_marker.cc:528: if (raw_obj->IsOldObject() &&
!raw_obj->IsMarked())
> {
> Update (not all new-space objects are survivors)

Yes. That makes sense. I will get on those.

> 
> https://codereview.chromium.org/2930943002/diff/1/runtime/vm/heap.h
> File runtime/vm/heap.h (right):
> 
> https://codereview.chromium.org/2930943002/diff/1/runtime/vm/heap.h#newcode248
> runtime/vm/heap.h:248: bool IsDebugCollection() { return
debug_gc_in_progress_;
> }
> Unused

Currently, yes. I am holding onto that function for the final cl. Regular old
GCs
should behave as they did prior to this change. I want to use this flag to
ensure
that.

[danunez, 2017-06-14 19:50:34]

On 2017/06/08 21:32:15, danunez wrote:
> On 2017/06/08 21:23:48, rmacnak wrote:
> > https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc
> > File runtime/vm/gc_marker.cc (right):
> > 
> >
>
https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
> > runtime/vm/gc_marker.cc:266: ASSERT(raw_weak->IsOldObject());
> > Update (visiting new-space weak properties now).
> > 
> >
>
https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
> > runtime/vm/gc_marker.cc:277: if (raw_key->IsHeapObject() &&
> > raw_key->IsOldObject() &&
> > Update (not all new-space objects are survivors)
> > 
> >
>
https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
> > runtime/vm/gc_marker.cc:436: if (!raw_obj->IsOldObject()) {
> > Update (not all new-space objects are survivors)
> > 
> >
>
https://codereview.chromium.org/2930943002/diff/1/runtime/vm/gc_marker.cc#new...
> > runtime/vm/gc_marker.cc:528: if (raw_obj->IsOldObject() &&
> !raw_obj->IsMarked())
> > {
> > Update (not all new-space objects are survivors)
> 
> Yes. That makes sense. I will get on those.
> 
> > 
> > https://codereview.chromium.org/2930943002/diff/1/runtime/vm/heap.h
> > File runtime/vm/heap.h (right):
> > 
> >
https://codereview.chromium.org/2930943002/diff/1/runtime/vm/heap.h#newcode248
> > runtime/vm/heap.h:248: bool IsDebugCollection() { return
> debug_gc_in_progress_;
> > }
> > Unused
> 
> Currently, yes. I am holding onto that function for the final cl. Regular old
> GCs
> should behave as they did prior to this change. I want to use this flag to
> ensure
> that.

For prosperity, Ryan found out that the VerifyPointersVisitor is searching the
entire new space. However, all objects were manually unmarked, including dead
new space objects. These objects were never swept away, unlike the dead old
space objects with their sweep tasks. Therefore, the VerifyPointersVisitor
visited a dead array, pointing to an object that the GC considered dead.

Fixing this error with the current machinery would involve an invasive change to
the GC (e.g. add FreeListElements to the new space in place of dead objects) or
change some assumptions about the new space that other visitors assume (e.g. no
dead/marked/forwarded objects in the new space after any collection).

Instead, we will evacuate the new space into the old space  and follow up with
an old space collection. This will be slower than the current method (it's
adding an extra new space collection and allocations to the old space), but will
definitely remove all garbage after collection.

[danunez, 2017-06-16 23:14:55]

Description was changed from

==========
Modifies the garbage collector to correctly remove inter-generational
garbage. Currently compiles, but verifier after GC reports an error.

ISSUE

Specifically, the following arrangements in a heap resulted
in garbage surviving a GC.

- Dead object in old space pointing to dead object in new space results
  in the new space object surviving.
- A cycle between two dead objects, one in each space, results in the
  cycle surviving until all objects are in the old space.

CHANGES

runtime/vm/heap_test.cc
- Adds a set of tests to check for the issue
  as well as some basic configurations. These tests are:
  - Dead object in old space pointing to dead object in new space.
  - Dead object in new space pointing to dead object in old space.
  - Dead object in new space and dead object in old space point to each
    other.
  - Live object in new space pointing to object in old space.
  - Live object in old space pointing to object in new space.
  - Old object is live. New object is dead.
  - Old object is dead. New object is live.

runtime/vm/heap.h
- Adds declaration of flag debug_gc_in_progress.

runtime/vm/heap.cc
- Flips order of collection in CollectsAllGarbage().
- Sets the flag debug_gc_in_progress when constructing the Heap.
- Sets the flag debug_gc_in_progress at start of CollectsAllGarbage().
- Unsets the flag debug_gc_in_progress at end of CollectsAllGarbage().

runtime/vm/scavenger.cc
- Adds method UnmarkNewSpace() to clear mark bit in ToSpace objects.

runtime/vm/gc_marker.cc
- Edits MarkVisitorBase so new space objects can be added to the
  marking stack and fully traversed. As a result, MarkSweep now marks
  through the SemiSpace.

runtime/vm/pages.cc
- Adds call to Scavenger::UnmarkNewSpace() after sweeping the
  LargePages and ExecutablePages in PageSpace::MarkSweep().

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

to

==========
Modifies the garbage collector to correctly remove inter-generational
garbage by evacuating all of new space.

Adds tests to check if this issue has been correctly resolved.

Updates the WeakProperty_PreserveCrossGen test to call for one new and one old
space collection instead of CollectAllGarbage(). Otherwise, all weak properties
are swept as garbage.

DETAILS:

ISSUE

Specifically, the following arrangements in a heap resulted
in garbage surviving a GC.

- Dead object in old space pointing to dead object in new space results
  in the new space object surviving.
- A cycle between two dead objects, one in each space, results in the
  cycle surviving until all objects are in the old space.

CHANGES

runtime/vm/heap_test.cc
- Adds a set of tests to check for the issue
  as well as some basic configurations. These tests are:
  - Dead object in old space pointing to dead object in new space.
  - Dead object in new space pointing to dead object in old space.
  - Dead object in new space and dead object in old space point to each
    other.
  - Live object in new space pointing to object in old space.
  - Live object in old space pointing to object in new space.
  - Old object is live. New object is dead.
  - Old object is dead. New object is live.

runtime/vm/heap.h
- Adds declaration of flag debug_gc_in_progress.

runtime/vm/heap.cc
- Forces a new collection started by CollectAllGarbage() to Evacuate()
  instead of Scavenge().
- Sets the flag debug_gc_in_progress when constructing the Heap.
- Sets the flag debug_gc_in_progress at start of CollectsAllGarbage().
- Unsets the flag debug_gc_in_progress at end of CollectsAllGarbage().

runtime/vm/scavenger.cc
- Adds a flag failed_to_promote_, which is flipped to true only if
  an object cannot be promoted.
- Forces synchronization at the start of Evacuate()
- Updates assertion to check if any objects that remain in new space
  after evacuation because they could not be promoted.

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

[danunez, 2017-06-16 23:20:48]

danunez@google.com changed reviewers:
+ asiva@google.com

[rmacnak, 2017-06-19 19:29:00]

https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/heap.cc
File runtime/vm/heap.cc (right):

https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/heap.cc#newc...
runtime/vm/heap.cc:452: debug_gc_in_progress_ = true;
Can this be

new_space_.Evacuate();
CollectOldSpaceGarbage(thread, kInvokeApiCallbacks, kFull);

? Without introducing a new state on the heap?

https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/heap_test.cc
File runtime/vm/heap_test.cc (right):

https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/heap_test.cc...
runtime/vm/heap_test.cc:365: 
Two lines between functions in cc files.

https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/object_test.cc
File runtime/vm/object_test.cc (right):

https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/object_test....
runtime/vm/object_test.cc:3367: isolate->heap()->CollectGarbage(Heap::kNew);
These shouldn't need to change.

https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/scavenger.cc
File runtime/vm/scavenger.cc (right):

https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/scavenger.cc...
runtime/vm/scavenger.cc:905: Scavenge();
Can't we just update the promotion threshold and scavenge once?

Something like

survivor_end_ = top_;
Scavenge();

[danunez, 2017-06-19 19:41:24]

On 2017/06/19 19:29:00, rmacnak wrote:
> https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/heap.cc
> File runtime/vm/heap.cc (right):
> 
>
https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/heap.cc#newc...
> runtime/vm/heap.cc:452: debug_gc_in_progress_ = true;
> Can this be
> 
> new_space_.Evacuate();
> CollectOldSpaceGarbage(thread, kInvokeApiCallbacks, kFull);
> 
> ? Without introducing a new state on the heap?
> 

That is true, especially since the state is never used elsewhere. I'll try it
and see what happens.

> https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/heap_test.cc
> File runtime/vm/heap_test.cc (right):
> 
>
https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/heap_test.cc...
> runtime/vm/heap_test.cc:365: 
> Two lines between functions in cc files.
> 
>
https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/object_test.cc
> File runtime/vm/object_test.cc (right):
> 
>
https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/object_test....
> runtime/vm/object_test.cc:3367: isolate->heap()->CollectGarbage(Heap::kNew);
> These shouldn't need to change.

My understanding is the test ensures that the property and value live through a
GC only because of the cross generational pointer.

Whereas the old debug collector will not promote whatever was just placed in new
space, the new debug collection will force the weak property and value into old
space. Since they are weak, the old collector will now collect them as garbage.

> 
> https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/scavenger.cc
> File runtime/vm/scavenger.cc (right):
> 
>
https://codereview.chromium.org/2930943002/diff/40001/runtime/vm/scavenger.cc...
> runtime/vm/scavenger.cc:905: Scavenge();
> Can't we just update the promotion threshold and scavenge once?
> 
> Something like
> 
> survivor_end_ = top_;
> Scavenge();

The first Scavenge() forces everything that is live and isn't promoted into the
survivor set. This would bypass an entire scan. Sounds good. I'll give this a
shot.

[rmacnak, 2017-06-22 21:59:33]

LGTM w/ comments

Also please update the commit message to clarify that this fixes
CollectAllGarbage, not regular GC. Regular GC will /eventually/ collect this
garbage, just a cycle later than it could.

https://codereview.chromium.org/2930943002/diff/60001/runtime/vm/heap.cc
File runtime/vm/heap.cc (right):

https://codereview.chromium.org/2930943002/diff/60001/runtime/vm/heap.cc#newc...
runtime/vm/heap.cc:447: new_space_.Evacuate();
Add a comment here that we evacuate new space to deal with dead objects that
have a cross-generational incoming pointer.

https://codereview.chromium.org/2930943002/diff/60001/runtime/vm/scavenger.cc
File runtime/vm/scavenger.cc (right):

https://codereview.chromium.org/2930943002/diff/60001/runtime/vm/scavenger.cc...
runtime/vm/scavenger.cc:915: survivor_end_ = top_;
Add a comment that this forces promotion of all survivors.

https://codereview.chromium.org/2930943002/diff/60001/runtime/vm/scavenger.cc...
runtime/vm/scavenger.cc:920: ASSERT(UsedInWords() == 0 || failed_to_promote_);
(UsedInWords() == 0)

[danunez, 2017-06-22 22:07:48]

Expect new patchset soon.

https://codereview.chromium.org/2930943002/diff/60001/runtime/vm/heap.cc
File runtime/vm/heap.cc (right):

https://codereview.chromium.org/2930943002/diff/60001/runtime/vm/heap.cc#newc...
runtime/vm/heap.cc:447: new_space_.Evacuate();
On 2017/06/22 21:59:33, rmacnak wrote:
> Add a comment here that we evacuate new space to deal with dead objects that
> have a cross-generational incoming pointer.

Done.

https://codereview.chromium.org/2930943002/diff/60001/runtime/vm/scavenger.cc
File runtime/vm/scavenger.cc (right):

https://codereview.chromium.org/2930943002/diff/60001/runtime/vm/scavenger.cc...
runtime/vm/scavenger.cc:915: survivor_end_ = top_;
On 2017/06/22 21:59:33, rmacnak wrote:
> Add a comment that this forces promotion of all survivors.

Done.

https://codereview.chromium.org/2930943002/diff/60001/runtime/vm/scavenger.cc...
runtime/vm/scavenger.cc:920: ASSERT(UsedInWords() == 0 || failed_to_promote_);
On 2017/06/22 21:59:33, rmacnak wrote:
> (UsedInWords() == 0)

Add parens. Got it.

[danunez, 2017-06-22 22:10:16]

Description was changed from

==========
Modifies the garbage collector to correctly remove inter-generational
garbage by evacuating all of new space.

Adds tests to check if this issue has been correctly resolved.

Updates the WeakProperty_PreserveCrossGen test to call for one new and one old
space collection instead of CollectAllGarbage(). Otherwise, all weak properties
are swept as garbage.

DETAILS:

ISSUE

Specifically, the following arrangements in a heap resulted
in garbage surviving a GC.

- Dead object in old space pointing to dead object in new space results
  in the new space object surviving.
- A cycle between two dead objects, one in each space, results in the
  cycle surviving until all objects are in the old space.

CHANGES

runtime/vm/heap_test.cc
- Adds a set of tests to check for the issue
  as well as some basic configurations. These tests are:
  - Dead object in old space pointing to dead object in new space.
  - Dead object in new space pointing to dead object in old space.
  - Dead object in new space and dead object in old space point to each
    other.
  - Live object in new space pointing to object in old space.
  - Live object in old space pointing to object in new space.
  - Old object is live. New object is dead.
  - Old object is dead. New object is live.

runtime/vm/heap.h
- Adds declaration of flag debug_gc_in_progress.

runtime/vm/heap.cc
- Forces a new collection started by CollectAllGarbage() to Evacuate()
  instead of Scavenge().
- Sets the flag debug_gc_in_progress when constructing the Heap.
- Sets the flag debug_gc_in_progress at start of CollectsAllGarbage().
- Unsets the flag debug_gc_in_progress at end of CollectsAllGarbage().

runtime/vm/scavenger.cc
- Adds a flag failed_to_promote_, which is flipped to true only if
  an object cannot be promoted.
- Forces synchronization at the start of Evacuate()
- Updates assertion to check if any objects that remain in new space
  after evacuation because they could not be promoted.

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

to

==========
Modifies the debug garbage collector (CollectAllGarbage()) to correctly remove
inter-generational garbage by evacuating all of new space.

Adds tests to check if this issue has been correctly resolved.

Updates the WeakProperty_PreserveCrossGen test to call for one new and one old
space collection instead of CollectAllGarbage(). Otherwise, all weak properties
are swept as garbage.

DETAILS:

ISSUE

Specifically, the following arrangements in a heap resulted
in garbage surviving a GC.

- Dead object in old space pointing to dead object in new space results
  in the new space object surviving.
- A cycle between two dead objects, one in each space, results in the
  cycle surviving until all objects are in the old space.

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

[danunez, 2017-06-27 21:00:49]

Description was changed from

==========
Modifies the debug garbage collector (CollectAllGarbage()) to correctly remove
inter-generational garbage by evacuating all of new space.

Adds tests to check if this issue has been correctly resolved.

Updates the WeakProperty_PreserveCrossGen test to call for one new and one old
space collection instead of CollectAllGarbage(). Otherwise, all weak properties
are swept as garbage.

DETAILS:

ISSUE

Specifically, the following arrangements in a heap resulted
in garbage surviving a GC.

- Dead object in old space pointing to dead object in new space results
  in the new space object surviving.
- A cycle between two dead objects, one in each space, results in the
  cycle surviving until all objects are in the old space.

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

to

==========
Modifies the debug garbage collector (CollectAllGarbage()) to correctly remove
inter-generational garbage by evacuating all of new space.

Adds tests to check if this issue has been correctly resolved.

Updates the WeakProperty_PreserveCrossGen test to call for one new and one old
space collection instead of CollectAllGarbage(). Otherwise, all weak properties
are swept as garbage.

DETAILS:

ISSUE

Specifically, the following arrangements in a heap resulted
in garbage surviving a GC.

- Dead object in old space pointing to dead object in new space results
  in the new space object surviving.
- A cycle between two dead objects, one in each space, results in the
  cycle surviving until all objects are in the old space.

BUG=
R=rmacnak@google.com

Committed:
https://github.com/dart-lang/sdk/commit/abf40fc8d221530cf589a7d7af11324fed48a823
==========

[danunez, 2017-06-27 21:00:50]

Committed patchset #5 (id:80001) manually as
abf40fc8d221530cf589a7d7af11324fed48a823 (presubmit successful).

[danunez, 2017-06-28 20:58:39]

Description was changed from

==========
Modifies the debug garbage collector (CollectAllGarbage()) to correctly remove
inter-generational garbage by evacuating all of new space.

Adds tests to check if this issue has been correctly resolved.

Updates the WeakProperty_PreserveCrossGen test to call for one new and one old
space collection instead of CollectAllGarbage(). Otherwise, all weak properties
are swept as garbage.

DETAILS:

ISSUE

Specifically, the following arrangements in a heap resulted
in garbage surviving a GC.

- Dead object in old space pointing to dead object in new space results
  in the new space object surviving.
- A cycle between two dead objects, one in each space, results in the
  cycle surviving until all objects are in the old space.

BUG=
R=rmacnak@google.com

Committed:
https://github.com/dart-lang/sdk/commit/abf40fc8d221530cf589a7d7af11324fed48a823
==========

to

==========
Modifies the debug garbage collector (CollectAllGarbage()) to correctly remove
inter-generational garbage by evacuating all of new space.

Adds tests to check if this issue has been correctly resolved.

Updates the WeakProperty_PreserveCrossGen test to call for one new and one old
space collection instead of CollectAllGarbage(). Otherwise, all weak properties
are swept as garbage.

DETAILS:

ISSUE

Specifically, the following arrangements in a heap resulted
in garbage surviving a GC.

- Dead object in old space pointing to dead object in new space results
  in the new space object surviving.
- A cycle between two dead objects, one in each space, results in the
  cycle surviving until all objects are in the old space.

BUG=
R=rmacnak@google.com

Committed:
https://github.com/dart-lang/sdk/commit/abf40fc8d221530cf589a7d7af11324fed48a823
==========