1694538 - Change WeakMap marking algorithm from an implicit entry edges to implicit value edges

Status: RESOLVED FIXED

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

Description

[Steve Fink [:sfink] [:s:]]

Something that has bothered me for a long time about my linear-time weakmap marking algorithm is that when you mark a WeakMap and find unmarked keys (which will possibly be marked later), I store <weakmap, key> tuples in gcWeakKeys indexed by the key. Then when the key gets marked later, it is looked up in this table and each tuple found is re-looked up in its weakmap (one object could be used as a key in several weakmaps). That lookup is unfortunate for performance reasons, and also turns out to complicate things quite a bit.

A simpler approach would be to record the value in gcWeakKeys, skipping the extra lookup to find it again. I didn't do this for at least three reasons:

• the value associated with that key might have changed.
• compartments mean that the key might be a CCW around a delegate in another compartment, and as long as the delegate is alive it keep the associated weakmap entry alive (both the key and the value)
• CCWs can be nuked and then un-nuked, and that requires switching the gcWeakKeys entry between the key and the delegate

The first is just bogus. Jon pointed this out when removing the insertion barrier. Snapshot at the beginning means that if the value is changed, the new value will already have to be alive for it to end up in the weakmap.

The third can be resolved similarly: when bad things like nuking and un-nuking happen, we can conservatively mark the values associated via gcWeakKeys with the thing that is going away. That better maintains snapshot at the beginning too; it can be extended to cover things that are alive via WeakMap entries.

I was maintaining a more precise notion of liveness than snapshot at the beginning because I needed the guarantee that I could always recover a WeakMap entry from a <weakmap, key> tuple. If I stop storing that, then being conservative is simpler and safer. Hopefully we're ok with stuff keyed off of nuked things living another GC. (Why do I feel like I'm foreshadowing an imminent bug report here?)

The second one can be resolved by recording two edges when a key has a delegate: one from the delegate to the value (which is similar to the simpler non-delegate key -> value case), and another edge from the delegate to the key. The CCW itself will provide an edge from key -> delegate. This can be stored in the same gcWeakKeys table, which should perhaps be renamed now.

Comment 1

[Steve Fink [:sfink] [:s:]]

Attachment: Bug 1694538 - Convert gcWeakKeys from <weakmap, key> tuples that require an extra lookup, to <ptr to color, target> tuples that simplify the code substantially

Comment 2

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/625e672375a6
Convert gcWeakKeys from <weakmap, key> tuples that require an extra lookup, to <ptr to color, target> tuples that simplify the code substantially r=jonco

Comment 3

[Natalia Csoregi [:nataliaCs]]

Backed out for assertion failures on Marking.cpp and other bustages.

backout: https://hg.mozilla.org/integration/autoland/rev/2cf47050b0cc1089935543ba5b559ebc5dbd8fcd

push: https://treeherder.mozilla.org/jobs?repo=autoland&revision=625e672375a63ec0747a127ebb9b318869d473f6&group_state=expanded

failure log e.g.: https://treeherder.mozilla.org/logviewer?job_id=331638966&repo=autoland&lineNumber=2178

[task 2021-03-01T19:05:21.447Z] 19:05:21 INFO - JavaScript error: resource://specialpowers/AppTestDelegateParent.jsm, line 10: NS_ERROR_NOT_AVAILABLE:
[task 2021-03-01T19:05:21.567Z] 19:05:21 INFO - Assertion failure: thing->isMarkedAny(), at /builds/worker/checkouts/gecko/js/src/gc/Marking.cpp:1026
[task 2021-03-01T19:05:21.638Z] 19:05:21 INFO - [Parent 1427, Breakpad Server] WARNING: Resource acquired is being released in non-LIFO order; why?
[task 2021-03-01T19:05:21.639Z] 19:05:21 INFO - : file /builds/worker/checkouts/gecko/xpcom/threads/BlockingResourceBase.cpp:292
[task 2021-03-01T19:05:21.639Z] 19:05:21 INFO - --- Mutex : dumpSafetyLock (currently acquired)
[task 2021-03-01T19:05:21.640Z] 19:05:21 INFO - calling context
[task 2021-03-01T19:05:21.640Z] 19:05:21 INFO - [stack trace unavailable]
[task 2021-03-01T19:05:21.675Z] 19:05:21 INFO - [Parent 1427, Main Thread] WARNING: IPC message discarded: actor cannot send: file /builds/worker/checkouts/gecko/ipc/glue/ProtocolUtils.cpp:512
[task 2021-03-01T19:05:21.676Z] 19:05:21 INFO - [Parent 1427, Main Thread] WARNING: IPC message discarded: actor cannot send: file /builds/worker/checkouts/gecko/ipc/glue/ProtocolUtils.cpp:512
[task 2021-03-01T19:05:21.677Z] 19:05:21 ERROR - A content process crashed and MOZ_CRASHREPORTER_SHUTDOWN is set, shutting down

Comment 4

[BugBot [:suhaib / :marco/ :calixte]]

There's a r+ patch which didn't land and no activity in this bug for 2 weeks.
:sfink, could you have a look please?
For more information, please visit auto_nag documentation.

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/f7b553bd9c0b
Convert gcWeakKeys from <weakmap, key> tuples that require an extra lookup, to <ptr to color, target> tuples that simplify the code substantially r=jonco

Comment 6

[Sandor Molnar[:smolnar]]

https://hg.mozilla.org/mozilla-central/rev/f7b553bd9c0b