1336467 - CC weakmap fixup blackens weakmap keys with black delegates even when the map is gray

Status: RESOLVED FIXED

(Core :: JavaScript: GC, defect)

Description

[Jon Coppeard (:jonco)]

A delegate object causes a weakmap key to be marked if it is marked itself.  This  is checked when the weakmap is being marked (or if the key is subsequently marked during weakmap marking).  If this happens during gray marking (e.g. the weakmap is gray and the key is unmarked) however then we can create a black->gray edge if the delegate is black.

Comment 1

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

Let me see if I understand this. You have an O in compartment C1 that is used as a key in a CC-reachable GC-unreachable weakmap in compartment C2, which means there is a key K (whose delegate is O) in the weakmap. You mark O black, then mark the weakmap gray, and during that marking you iterate over the keys and find K, which has not yet been marked. Its delegate is marked (black), so you mark the key (gray).

Which is the black->gray edge? From O->K? What considers that to be an edge?

I can see a similar problem if the value for this key is also gray. To modify it slightly, let's say that O is black, but both the weakmap and the value are gray. Now there is sort of an edge from O->value, and that is black->gray.

Comment 2

[Jon Coppeard (:jonco)]

(In reply to Steve Fink [:sfink] [:s:] from comment #1)

> Which is the black->gray edge? From O->K? What considers that to be an edge?

Yes, from O->K.  The CC's weak mapping gray marking fixup does here:

http://searchfox.org/mozilla-central/source/xpcom/base/CycleCollectedJSContext.cpp#261

> I can see a similar problem if the value for this key is also gray.

As I understand it the CC only expects the value to be black if both the key AND the weakmap are black.  But Andrew will know for sure about this.

Comment 3

[Jon Coppeard (:jonco)]

Attachment: add-weakmap-tests

Here's the test code I mentioned.

I'm not sure whether we should check this in until we understand and fix the issue.  Or maybe we should just check in the parts that work for now.

Comment 4

[Jon Coppeard (:jonco)]

Andrew, can you confirm whether the following is correct?

1) Keys in a gray weakmap need to be marked black if they have a black delegate

2) Values in a weakmap only need to be marked black if both key and weakmap are marked black (i.e. if either key or map is gray then then value is gray)

Comment 5

[Andrew McCreight [:mccr8]]

The rules the CC uses are encoded in nsCycleCollector::ScanWeakMaps(), though they should be somehow analogous to those used by the GC. ie gray : dead :: black : live.

(In reply to Jon Coppeard (:jonco) from comment #4)
> 1) Keys in a gray weakmap need to be marked black if they have a black
> delegate

I think the key gets marked black due to the delegate only if both the delegate and map are black.

> 2) Values in a weakmap only need to be marked black if both key and weakmap
> are marked black (i.e. if either key or map is gray then then value is gray)

Yes. (After considering rule 1 of course.)

Comment 6

[Jon Coppeard (:jonco)]

(In reply to Andrew McCreight [:mccr8] from comment #5)
> I think the key gets marked black due to the delegate only if both the
> delegate and map are black.

The logic in FixWeakMappingGrayBitsTracer::trace doesn't check the state of the map when deciding whether to unmark the key in this case though - do you think it should?

Comment 7

[Andrew McCreight [:mccr8]]

(In reply to Jon Coppeard (:jonco) from comment #6)
> The logic in FixWeakMappingGrayBitsTracer::trace doesn't check the state of
> the map when deciding whether to unmark the key in this case though - do you
> think it should?

Sorry for the delay here. It is a little concerning to me that these two places are inconsistent.

It seems like the liveness of the key delegate should be conditional on that of the map. If you consider a key k, key delegate d, map m and value v, where v holds m alive, then we don't want d to hold alive k (and thus v and m) by itself. I'm not sure how the GC handles it.

Comment 8

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

(In reply to Andrew McCreight [:mccr8] from comment #7)
> (In reply to Jon Coppeard (:jonco) from comment #6)
> > The logic in FixWeakMappingGrayBitsTracer::trace doesn't check the state of
> > the map when deciding whether to unmark the key in this case though - do you
> > think it should?
> 
> Sorry for the delay here. It is a little concerning to me that these two
> places are inconsistent.
> 
> It seems like the liveness of the key delegate should be conditional on that
> of the map. If you consider a key k, key delegate d, map m and value v,
> where v holds m alive, then we don't want d to hold alive k (and thus v and
> m) by itself. I'm not sure how the GC handles it.

If I'm understanding correctly, v would never get marked in this situation (assuming nothing else is keeping it or m alive.) m would never get marked. So even if d marks k, k getting marked has no effect unless m is also marked.

But as to whether d should mark k, in the best case it wouldn't, because k could hold a bunch of stuff live without involving the weakmap at all, and the fact that k is sitting in a dead weakmap shouldn't really prevent us from discarding all of the stuff hanging off of k.

I like mccr8's invariant from IRC: "an object should be marked black if it is live when considering only black roots. an object should be marked gray if it shouldn't be marked black, but it is live when considering both black and gray roots."

By that, a delegate should not mark its key at all unless the map is marked. A black key and black map should mark the value black; any other gray/black combination should only mark the value gray (unless it is otherwise marked black).

And saying that makes me realize that we're not tracking the full information here -- WeakMapObject can be black or gray, but the weak maps themselves are storing only a single 'marked' bit. So we can't distinguish gray vs black weak maps right now. Which is fine, since that is inferrable from the mark color -- while black marking, we will only encounter weakmaps that should be black. During gray marking, we may mark additional weakmaps gray, but the only possible result of that is to mark things (keys from delegates, and values from keys) gray. And that is correct in both cases. (Which is not magic; it's just that black marking finds all black-reachable stuff, and gray marking finds everything left over.)

This is nowhere close to what FixWeakMappingGrayBitsTracer::trace is doing. If the value is gray, it will be blackened if either the key or the map is black. Why is that needed/wanted? If both are black, the value will already be black. Otherwise, it can stay gray.

Ok, now what is confusing me is the key -> delegate direction. The current logic in FixWeakMappingGrayBitsTracer::trace says

  if (key is gray and delegate is black)
    mark key black

Why? If you have a gray root that points to that gray key, then why should the delegate keep the key alive all by itself?

I need to ponder more.

Comment 9

[Jon Coppeard (:jonco)]

It seems that the JS engine does the right thing after all, and that the problem is that the CC's weakmap fixup doesn't check whether the map is marked when doing gray unmarking on weakmap keys that have black delegates.  It should only do this if the map is black too.

Comment 10

[Jon Coppeard (:jonco)]

Attachment: bug1336467-cc-gray-fixup

Patch to check the whether the map is black before blackening the key.

Comment 11

[Jon Coppeard (:jonco)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/ddef07d1ef6c7389726c63a165f89f70b33ae57b

Comment 12

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

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

Comment 13

[Ryan VanderMeulen [:RyanVM]]

Please request Aurora/Beta approval on this when you get a chance.

Comment 14

[Jon Coppeard (:jonco)]

(In reply to Ryan VanderMeulen [:RyanVM] from comment #13)
> Please request Aurora/Beta approval on this when you get a chance.

Although it's bad that the code was inconsistent, I don't think we have any direct evidence that this was causing crashes.  Blackening objects unnecessarily is more likely to cause leaks than crashes, although this is a sensitive area and problems like this can have unforeseen effects.

I'd rather let this one ride the trains unless you or Andrew think otherwise.

Comment 15

[Ryan VanderMeulen [:RyanVM]]

Happy to defer to you and Andrew on that :)

Comment 16

[Andrew McCreight [:mccr8]]

Sounds fine to me.

Comment 18

[Andrew McCreight [:mccr8]]

Jon, it looks like your patch fixed at least one kind of bad leak (bug 1283264), so if you could backport this to Aurora and maybe Beta that would be nice. Thanks!

Comment 19

[Jon Coppeard (:jonco)]

Great news, will do!

Comment 20

[Jon Coppeard (:jonco)]

Comment on attachment 8837664 [details] [diff] [review]
bug1336467-cc-gray-fixup

Approval Request Comment
[Feature/Bug causing the regression]: This has been in the CC for ages.  The last bug that touched this was bug 1167453.
[User impact if declined]: Possible memory leaks (e.g. bug 1283264)
[Is this code covered by automated tests?]: Yes.
[Has the fix been verified in Nightly?]: Yes.
[Needs manual test from QE? If yes, steps to reproduce]: No.
[List of other uplifts needed for the feature/fix]: None.
[Is the change risky?]: No.
[Why is the change risky/not risky?]: This is a sensitive area but this patch has been in nightly since 16th Feb and hasn't caused problems.
[String changes made/needed]: None.

Comment 21

[Julien Cristau [:jcristau]]

Comment on attachment 8837664 [details] [diff] [review]
bug1336467-cc-gray-fixup

fix a memory leak, aurora53+ and beta52+

Comment 22

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/3707c5162a5a
https://hg.mozilla.org/releases/mozilla-beta/rev/e48cd1b9b444

Comment 23

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-esr52/rev/e48cd1b9b444

Comment 24

[Andrei Vaida [:avaida]]

Setting qe-verify- based on Jon's assessment on manual testing needs (see Comment 20) and the fact that this fix has automated coverage.