1802897 - Initial implementation of parallel marking

Status: RESOLVED FIXED

(Core :: JavaScript: GC, task, P3)

Description

[Jon Coppeard (:jonco)]

This bug is to a land an initial implementation of parallel marking for evaluation. It will be disabled by default can be enabled at runtime through a preference.

Comment 1

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 1: Add a pref for parallel marking, disabled by default r?sfink

Comment 2

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 2: Give GCRuntime a vector of GCMarkers r?sfink

These will hold the mark stacks of different marking threads used by parallel
marking between slices. For everything else the first marker is used.

Depends on D163461

Comment 3

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 3: Create multiple GCMarkers r?sfink

This adds GCRuntime::markingWorkerCount() which determines how many markers get
created. This is currently capped at a maximum of two. The markers vector is
updated whenever the GC parameters affecting its length change.

Depends on D163462

Comment 4

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 4: Move delayed marking list to the GCRuntime r?sfink

Each arena can only be on one list so having a delayed marking list per marker
doesn't work. This is only used on OOM so we don't need to worry about
performance so we can move this state to the GCRuntime. We'll make access to it
synchronised in later patches.

Depends on D163463

Comment 5

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 5: Add methods to update the mark bitmap atomically r?sfink

The mark bitmap is represented using relaxed atomics. Currently we update this
using separate load and store operations where possible as this is more
efficient but this is only possible if there are no concurrent writes.

Parallel marking will perform concurrent writes to the marking bitmap so
requires updates to be performed atomically.

The patch adds methods that are correct in the face of multiple writes
(different threads won't stomp over each others' updates) however the
markIfUnmarkedAtomic method can return false positives. It works out faster
overall to allow this and tolerate multiple threads trying to mark the same
thing at the same time occasionally than to have the extra synchronisation
overhead of avoiding it.

Depends on D163464

Comment 6

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 6: Add parallel MarkingOption which uses atomic marking operations r?sfink

This adds a new marking option which calls the atomic version of the
markIfUnmarked method.

Comment 7

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 7: Only mark implicit edges from the normal marking path r?sfink

Even though this doesn't do anything during parallel marking (because the check
only when we're in weak marking mode), this made a surprising different to the
performance of parallel marking.

The patch adds a marking option for this and only includes it in the normal
marking path. It also had to be moved from traceChildren methods into GCMarker.

Depends on D163488

Comment 8

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 8: Allow accessing the atom marking bitmap from more than one thread r?sfink

This would otherwise assert during parallel marking. It's safe to check the
mark bits concurrently as we don't mutate anything.

This adds 'readonlyThreadsafe' methods to SparseBitmap along the same lines as
those in mozilla::HashMap.

Depends on D163490

Comment 9

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 9: Implement parallel marking r?sfink

This adds the classes ParallelMarker and ParallelMarkTask. The former
coordinates parallel marking between multiple threads each running the latter
task.

This uses a form of work stealing. Each task marks while has work (and budget)
and then adds itself to a list of waiting tasks. While marking we check for
waiting tasks and if any are present we transfer some work to the waiting task
and resume it.

Synchronisation is acomplished using the GC lock except for checking for
waiting tasks which uses a relaxed atomic.

The main parts of marking are converted to use parallel marking if enabled.

Depends on D163491

Comment 10

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 10: Relax some assertions that that failed when marking in parallel r?sfink

The allows some hash table lookups to occur in parallel which is safe since we
are not mutating anything.

Depends on D163493

Comment 11

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 11: Add locks where necessary while marking in parallel r?sfink

This patch makes us take the GC lock during parallel marking in a few places
where it's necessary, notably while marking weak maps.

Depends on D163494

Comment 12

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 12: Make gray unmarking work with parallel marking r?sfink

When we mark a gray GC thing black during GC and it has children in uncollected
zones we must make sure they end up black too otherwise we will have created a
black to gray edge.

This happens using the standard gray unmarking path, and this can call back
into GC marking if it reaches a GC thing that is in a zone being collected.
All of this needs to work with parallel marking.

The patch moves the gray unmarking stack to GCMarker so there is a separate one
available per parallel task and uses atomic marking function in case we're
running in parallel. It would be slightly better to only use the atomic
accesses if we are marking in parallel, but I haven't done that here.

Depends on D163495

Comment 13

[Jon Coppeard (:jonco)]

Attachment: Bug 1802897 - Part 13: Enable parallel marking for some shell tests r?sfink

This enables parallel marking for the tsan and compacting test jobs, which
should get us some decent coverage for the shell.

Comment 14

[Phabricator Automation]

Comment on attachment 9306483 [details]
Bug 1802897 - Part 13: Enable parallel marking for some shell tests r?sfink

Revision D163740 was moved to bug 1804272. Setting attachment 9306483 [details] to obsolete.

Comment 15

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/28c061eb2993
Part 1: Add a pref for parallel marking, disabled by default r=sfink
https://hg.mozilla.org/integration/autoland/rev/73ad67b6e4f6
Part 2: Give GCRuntime a vector of GCMarkers r=sfink
https://hg.mozilla.org/integration/autoland/rev/68880308ca96
Part 3: Create multiple GCMarkers r=sfink
https://hg.mozilla.org/integration/autoland/rev/f98def4568e6
Part 4: Move delayed marking list to the GCRuntime r=sfink
https://hg.mozilla.org/integration/autoland/rev/ab00bd1ada69
Part 5: Add methods to update the mark bitmap atomically r=sfink
https://hg.mozilla.org/integration/autoland/rev/d6c6eaa2508a
Part 6: Add parallel MarkingOption which uses atomic marking operations r=sfink
https://hg.mozilla.org/integration/autoland/rev/f21b54985888
Part 7: Only mark implicit edges from the normal marking path r=sfink
https://hg.mozilla.org/integration/autoland/rev/9fcff7ae8aac
Part 8: Allow accessing the atom marking bitmap from more than one thread r=sfink
https://hg.mozilla.org/integration/autoland/rev/b3e82a32e13e
Part 9: Implement parallel marking r=sfink
https://hg.mozilla.org/integration/autoland/rev/bf236f6a197c
Part 10: Relax some assertions that that failed when marking in parallel r=sfink
https://hg.mozilla.org/integration/autoland/rev/1b2d9c4afee8
Part 11: Add locks where necessary while marking in parallel r=sfink
https://hg.mozilla.org/integration/autoland/rev/5c3c2afd76af
Part 12: Make gray unmarking work with parallel marking r=sfink

Comment 16

[Cristian Tuns]

Backed out for causing build bustages on Marking.cpp

• Backout link
• Push with failures
• Failure Log
• Failure line: /builds/worker/checkouts/gecko/js/src/gc/Marking.cpp:1359:19: error: constexpr if condition evaluates to 2, which cannot be narrowed to type 'bool' [-Wc++11-narrowing]

Comment 17

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/8700caa2ba0d
Part 1: Add a pref for parallel marking, disabled by default r=sfink
https://hg.mozilla.org/integration/autoland/rev/4c918a83a58a
Part 2: Give GCRuntime a vector of GCMarkers r=sfink
https://hg.mozilla.org/integration/autoland/rev/e9d012cf0a17
Part 3: Create multiple GCMarkers r=sfink
https://hg.mozilla.org/integration/autoland/rev/b46dce3f55cf
Part 4: Move delayed marking list to the GCRuntime r=sfink
https://hg.mozilla.org/integration/autoland/rev/4b71f2915682
Part 5: Add methods to update the mark bitmap atomically r=sfink
https://hg.mozilla.org/integration/autoland/rev/122ddd142e5c
Part 6: Add parallel MarkingOption which uses atomic marking operations r=sfink
https://hg.mozilla.org/integration/autoland/rev/805404aeaae8
Part 7: Only mark implicit edges from the normal marking path r=sfink
https://hg.mozilla.org/integration/autoland/rev/cdf0c1609e11
Part 8: Allow accessing the atom marking bitmap from more than one thread r=sfink
https://hg.mozilla.org/integration/autoland/rev/91cff8916db3
Part 9: Implement parallel marking r=sfink
https://hg.mozilla.org/integration/autoland/rev/dcfea8bcfa2c
Part 10: Relax some assertions that that failed when marking in parallel r=sfink
https://hg.mozilla.org/integration/autoland/rev/dc838ec18940
Part 11: Add locks where necessary while marking in parallel r=sfink
https://hg.mozilla.org/integration/autoland/rev/5474e6f89982
Part 12: Make gray unmarking work with parallel marking r=sfink

Comment 18

[Iulian Moraru]

https://hg.mozilla.org/mozilla-central/rev/8700caa2ba0d
https://hg.mozilla.org/mozilla-central/rev/4c918a83a58a
https://hg.mozilla.org/mozilla-central/rev/e9d012cf0a17
https://hg.mozilla.org/mozilla-central/rev/b46dce3f55cf
https://hg.mozilla.org/mozilla-central/rev/4b71f2915682
https://hg.mozilla.org/mozilla-central/rev/122ddd142e5c
https://hg.mozilla.org/mozilla-central/rev/805404aeaae8
https://hg.mozilla.org/mozilla-central/rev/cdf0c1609e11
https://hg.mozilla.org/mozilla-central/rev/91cff8916db3
https://hg.mozilla.org/mozilla-central/rev/dcfea8bcfa2c
https://hg.mozilla.org/mozilla-central/rev/dc838ec18940
https://hg.mozilla.org/mozilla-central/rev/5474e6f89982