VM: Fix WeakProperty processing during parallel marking.

VM: Fix WeakProperty processing during parallel marking.

Previously if one marker marked the weak property and another marker marked its key then the first marker might stop marking before it sees that the key was marked.

Here is a possible concurrent execution, assuming P is a WeakProperty and K is P.key:

    (Marker A)                        (Marker B)
        |                                  |
[ mark property P     ]                    |
        |                                  |
[ drain marking stack ]                    |
[ no more work to do  ]                    |
        |                       [ mark K               ]
        |                       [ draing marking stack ]
        |                       [ no more work to do   ]
        |                                  |
        |                                  |
       ...                                ...
        |                                  |
    [Finalize]                         [Finalize]
        |
    [Clear P]

In this execution we end up clearing P even though P.key is marked.

To fix this issue without reintroducing central WeakProperty processing
we change the marking phase loop in such a way that markers consider the
marking done only if all of them agree that they have no more weak properties
with marked keys.

Essentially the marking loop now has a separate phase where all markers check
their pending weak properties. The decision to proceed to the next marking phase
(weak handles processing) is done in lock step using barrier - either all threads
advance to the next stage or one of the threads finds a weak property
with marked key and unmarked value and all threads resume marking.

BUG=
R=asiva@google.com

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

[Vyacheslav Egorov (Google), 2016-06-08 16:25:29]

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

[Vyacheslav Egorov (Google), 2016-06-08 16:25:29]

PTAL

[Vyacheslav Egorov (Google), 2016-06-08 16:28:32]

Description was changed from

==========
VM: Fix WeakProperty processing during parallel marking.

Previously if one marker marked the weak property and another marker marked its
key then the first marker might stop marking before it sees that the key was
marked.

Here is a possible concurrent execution, assuming P is a WeakProperty and K is
P.key:

    (Marker A)                        (Marker B)
        |                                  |
[ mark property P     ]                    |
        |                                  |
[ drain marking stack ]                    |
[ no more work to do  ]                    |
        |                       [ mark K               ]
        |                       [ draing marking stack ]
        |                       [ no more work to do   ]
        |                                  |
        |                                  |
       ...                                ...
        |                                  |
    [Finalize]                         [Finalize]
        |
    [Clear P]

In this execution we end up clearing P even though P.key is marked.

To fix this issue without reintroducing central WeakProperty processing
we change the marking phase loop in such a way that markers consider the
marking done only if all of them agree that they have no more weak properties
with marked keys.

Essentially the marking loop now has a separate phase where all markers check
their pending weak properties. The decision to proceed to the next marking phase
(weak handles processing) is done in lock step using barrier - either all
threads
advance to the next stage or one of the threads finds a weak property
with marked key and unmarked value and all threads resume marking.

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

to

==========
VM: Fix WeakProperty processing during parallel marking.

Previously if one marker marked the weak property and another marker marked its
key then the first marker might stop marking before it sees that the key was
marked.

Here is a possible concurrent execution, assuming P is a WeakProperty and K is
P.key:

    (Marker A)                        (Marker B)
        |                                  |
[ mark property P     ]                    |
        |                                  |
[ drain marking stack ]                    |
[ no more work to do  ]                    |
        |                       [ mark K               ]
        |                       [ draing marking stack ]
        |                       [ no more work to do   ]
        |                                  |
        |                                  |
       ...                                ...
        |                                  |
    [Finalize]                         [Finalize]
        |
    [Clear P]

In this execution we end up clearing P even though P.key is marked.

To fix this issue without reintroducing central WeakProperty processing
we change the marking phase loop in such a way that markers consider the
marking done only if all of them agree that they have no more weak properties
with marked keys.

Essentially the marking loop now has a separate phase where all markers check
their pending weak properties. The decision to proceed to the next marking phase
(weak handles processing) is done in lock step using barrier - either all
threads
advance to the next stage or one of the threads finds a weak property
with marked key and unmarked value and all threads resume marking.

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

[Vyacheslav Egorov (Google), 2016-06-08 16:28:43]

+iposva fyi

[siva, 2016-06-08 19:45:21]

lgtm with some questions.

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

https://codereview.chromium.org/2041413005/diff/20001/runtime/vm/gc_marker.cc...
runtime/vm/gc_marker.cc:630: barrier_->Sync();
Why is this barrier_->Sync() necessary? At this point it has been established
that at least one person has more work to do and so everybody needs to iterate
over again, couldn't they just start iterating again without doing the sync?

https://codereview.chromium.org/2041413005/diff/20001/runtime/vm/gc_marker.cc...
runtime/vm/gc_marker.cc:738: barrier.Sync();
back to back barrier.Sync() calls with no code between them?

https://codereview.chromium.org/2041413005/diff/20001/runtime/vm/gc_marker.cc...
runtime/vm/gc_marker.cc:741: } while (more_to_mark);
Is this loop necessary could we just assert after the first barrier.Sync() that
AtomicOperations::LoadRelaxed(&num_busy) == 0 because the MarkTask.Run method
exits only after AtomicOperations::LoadRelaxed(num_busy_) is 0.

[Vyacheslav Egorov (Google), 2016-06-09 08:17:06]

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

https://codereview.chromium.org/2041413005/diff/20001/runtime/vm/gc_marker.cc...
runtime/vm/gc_marker.cc:630: barrier_->Sync();
On 2016/06/08 19:45:20, siva wrote:
> Why is this barrier_->Sync() necessary? At this point it has been established
> that at least one person has more work to do and so everybody needs to iterate
> over again, couldn't they just start iterating again without doing the sync?

Because strictly speaking one thread that has work can rush, while other threads
are descheduled, drain it's marking stack and decrement num_busy_ back. At this
point other threads are resumed check num_busy_ and see zero. This is a possible
though unlikely execution, but when writing concurrent code we have to think
about *all* possible concurrent executions:

   Marker A                  Marker B

1. more_to_mark = true       more_to_mark = false
2. lock inc num_busy         -- not running -----   num_busy = 1
3. Sync                      Sync
4. DrainMarkingStack         -- not running -----
5. lock dec num_busy_        -- not running -----   num_busy = 0 
6. -- not running -----      load num_busy_ -> 0
7. -- not running -----      more_to_mark = false

In this case Marker B does not realize that Marker A was running and potentially
did some work.

https://codereview.chromium.org/2041413005/diff/20001/runtime/vm/gc_marker.cc...
runtime/vm/gc_marker.cc:738: barrier.Sync();
On 2016/06/08 19:45:20, siva wrote:
> back to back barrier.Sync() calls with no code between them?

These barriers correspond to barriers in the marker threads - there must be in
one to one correspondence. 

ThreadBarrier::Sync pauses the thread until all threads (that includes the main
thread) reach ::Sync. That is why there must be 1-1 correspondence between the
barriers.

https://codereview.chromium.org/2041413005/diff/20001/runtime/vm/gc_marker.cc...
runtime/vm/gc_marker.cc:741: } while (more_to_mark);
On 2016/06/08 19:45:20, siva wrote:
> Is this loop necessary could we just assert after the first barrier.Sync()
that
> AtomicOperations::LoadRelaxed(&num_busy) == 0 because the MarkTask.Run method
> exits only after AtomicOperations::LoadRelaxed(num_busy_) is 0.

Yes, the loop is necessary, because there is a loop in the marker task - so we
must guarantee that we execute barriers in 1-1 correspondence. See above.

[siva, 2016-06-09 16:39:53]

LGTM

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

https://codereview.chromium.org/2041413005/diff/20001/runtime/vm/gc_marker.cc...
runtime/vm/gc_marker.cc:630: barrier_->Sync();
On 2016/06/09 08:17:05, Vyacheslav Egorov (Google) wrote:
> On 2016/06/08 19:45:20, siva wrote:
> > Why is this barrier_->Sync() necessary? At this point it has been
established
> > that at least one person has more work to do and so everybody needs to
iterate
> > over again, couldn't they just start iterating again without doing the sync?
> 
> Because strictly speaking one thread that has work can rush, while other
threads
> are descheduled, drain it's marking stack and decrement num_busy_ back. At
this
> point other threads are resumed check num_busy_ and see zero. This is a
possible
> though unlikely execution, but when writing concurrent code we have to think
> about *all* possible concurrent executions:
> 
>    Marker A                  Marker B
> 
> 1. more_to_mark = true       more_to_mark = false
> 2. lock inc num_busy         -- not running -----   num_busy = 1
> 3. Sync                      Sync
> 4. DrainMarkingStack         -- not running -----
> 5. lock dec num_busy_        -- not running -----   num_busy = 0 
> 6. -- not running -----      load num_busy_ -> 0
> 7. -- not running -----      more_to_mark = false
> 
> In this case Marker B does not realize that Marker A was running and
potentially
> did some work. 
> 
> 
> 
> 

True if we let the threads run we get into a scenario of wanting the value of
num_busy corresponding to the iteration a thread is in.
With this sync you are ensuring that all threads will only be looking at the
value for the same iteration.

https://codereview.chromium.org/2041413005/diff/20001/runtime/vm/gc_marker.cc...
runtime/vm/gc_marker.cc:738: barrier.Sync();
On 2016/06/09 08:17:06, Vyacheslav Egorov (Google) wrote:
> On 2016/06/08 19:45:20, siva wrote:
> > back to back barrier.Sync() calls with no code between them?
> 
> These barriers correspond to barriers in the marker threads - there must be in
> one to one correspondence. 
> 
> ThreadBarrier::Sync pauses the thread until all threads (that includes the
main
> thread) reach ::Sync. That is why there must be 1-1 correspondence between the
> barriers.

Acknowledged.

https://codereview.chromium.org/2041413005/diff/20001/runtime/vm/gc_marker.cc...
runtime/vm/gc_marker.cc:741: } while (more_to_mark);
On 2016/06/09 08:17:05, Vyacheslav Egorov (Google) wrote:
> On 2016/06/08 19:45:20, siva wrote:
> > Is this loop necessary could we just assert after the first barrier.Sync()
> that
> > AtomicOperations::LoadRelaxed(&num_busy) == 0 because the MarkTask.Run
method
> > exits only after AtomicOperations::LoadRelaxed(num_busy_) is 0.
> 
> Yes, the loop is necessary, because there is a loop in the marker task - so we
> must guarantee that we execute barriers in 1-1 correspondence. See above.

Acknowledged.

[Vyacheslav Egorov (Google), 2016-06-09 16:50:24]

Description was changed from

==========
VM: Fix WeakProperty processing during parallel marking.

Previously if one marker marked the weak property and another marker marked its
key then the first marker might stop marking before it sees that the key was
marked.

Here is a possible concurrent execution, assuming P is a WeakProperty and K is
P.key:

    (Marker A)                        (Marker B)
        |                                  |
[ mark property P     ]                    |
        |                                  |
[ drain marking stack ]                    |
[ no more work to do  ]                    |
        |                       [ mark K               ]
        |                       [ draing marking stack ]
        |                       [ no more work to do   ]
        |                                  |
        |                                  |
       ...                                ...
        |                                  |
    [Finalize]                         [Finalize]
        |
    [Clear P]

In this execution we end up clearing P even though P.key is marked.

To fix this issue without reintroducing central WeakProperty processing
we change the marking phase loop in such a way that markers consider the
marking done only if all of them agree that they have no more weak properties
with marked keys.

Essentially the marking loop now has a separate phase where all markers check
their pending weak properties. The decision to proceed to the next marking phase
(weak handles processing) is done in lock step using barrier - either all
threads
advance to the next stage or one of the threads finds a weak property
with marked key and unmarked value and all threads resume marking.

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

to

==========
VM: Fix WeakProperty processing during parallel marking.

Previously if one marker marked the weak property and another marker marked its
key then the first marker might stop marking before it sees that the key was
marked.

Here is a possible concurrent execution, assuming P is a WeakProperty and K is
P.key:

    (Marker A)                        (Marker B)
        |                                  |
[ mark property P     ]                    |
        |                                  |
[ drain marking stack ]                    |
[ no more work to do  ]                    |
        |                       [ mark K               ]
        |                       [ draing marking stack ]
        |                       [ no more work to do   ]
        |                                  |
        |                                  |
       ...                                ...
        |                                  |
    [Finalize]                         [Finalize]
        |
    [Clear P]

In this execution we end up clearing P even though P.key is marked.

To fix this issue without reintroducing central WeakProperty processing
we change the marking phase loop in such a way that markers consider the
marking done only if all of them agree that they have no more weak properties
with marked keys.

Essentially the marking loop now has a separate phase where all markers check
their pending weak properties. The decision to proceed to the next marking phase
(weak handles processing) is done in lock step using barrier - either all
threads
advance to the next stage or one of the threads finds a weak property
with marked key and unmarked value and all threads resume marking.

BUG=
R=asiva@google.com

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

[Vyacheslav Egorov (Google), 2016-06-09 16:50:26]

Committed patchset #2 (id:20001) manually as
97a8c4caffd2e758c60a3e4502f07d6886ee0363 (presubmit successful).