Closed Bug 667126 Opened 8 years ago Closed 8 years ago

js::WeakMap's MarkPolicy should mark entire entries, not just values

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla8

People

(Reporter: jimb, Assigned: jimb)

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(1 file, 1 obsolete file)

As designed, js::WeakMap cannot be used to implement maps where 1) the criterion for retaining a table entry is something other than "the key is marked", and 2) marking the value does not cause the key to be marked (because, perhaps, the value does not refer to the key).

A WeakMap's MarkPolicy's 'keyMarked' member function determines whether an entry is retained. However, it is plausible to want WeakMaps where key equality depends on some property of the key, not the key itself, in which case one will need to retain table entries whose keys are as of yet unmarked. However, WeakMap currently assumes that, if a table entry has been selected to survive the collection cycle, its key must have been marked.
Attachment #541873 - Flags: review?(jorendorff)
OS: Linux → All
Hardware: x86_64 → All
Comment on attachment 541873 [details] [diff] [review]
Allow WeakMaps where the criterion for retaining an entry does not imply that the entry's key has been marked.

Review of attachment 541873 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsweakmap.h
@@ +200,5 @@
>          bool markedAny = false;
>          for (Range r = Base::all(); !r.empty(); r.popFront()) {
>              /* If the key is alive, mark the value if needed. */
> +            if (!t.valueMarked(r.front().value) && t.entryLive(r.front().key)) {
> +                t.markLiveEntry(r.front().key, r.front().value, "live WeakMap entry");

This is no good, because the plan in bug 655297 involves a mark policy that looks at an entry and says, "well, this key isn't marked yet, due to an optimization, but since it is a wrapper that's a WeakMap key, I need to keep it alive".

The above code wouldn't be able to do that; if the value happens to be marked, the key is never examined, and markLiveEntry is definitely not called.

Here's my proposed solution. WeakMap::markIteratively will just say:

    bool markedAny = false;
    for (Range r = ....each entry...) {
        markedAny |= t.markIteratively(r.front().key, r.front().value);

letting the mark policy consider both the key and the value in deciding whether to mark anything; after that we can add the following sanity check:

        // The mark policy must not leave us in a state where we would keep
        // an entry with a dead value.
        JS_ASSERT_IF(t.keyMarked(r.front().key), t.valueMarked(r.front().value));
    }

I believe the t.entryLive() function would then be unnecessary (t.markIteratively() subsumes its complexity and a good deal more).
Attachment #541873 - Flags: review?(jorendorff)
I don't quite understand the use case here.  Is the JS GC managing the keys and values but not the maps themselves (which are instead allocated as maybe C++ objects and cannot themselves be a key or value in a WeakMap)?

I'm just trying to think about how cycle collection of WeakMaps can be done correctly, and markEntry isn't really strong enough for that, as the CC needs to know what map contains the binding, because if the CC decides that the weak map is dead, then that affects what bindings are live.  But if your WeakMaps can't be in WeakMaps, then that makes things simpler.  Maybe I need a third interface for the CC...
Revised as suggested.
Assignee: general → jimb
Attachment #541873 - Attachment is obsolete: true
Status: NEW → ASSIGNED
Attachment #542272 - Flags: review?(jorendorff)
(In reply to comment #2)
> I don't quite understand the use case here.  Is the JS GC managing the keys
> and values but not the maps themselves (which are instead allocated as maybe
> C++ objects and cannot themselves be a key or value in a WeakMap)?

What we have here is a C++ class template that is used as the guts of the JavaScript WeakMap object. The comments atop jsweakmap.h are supposed to explain how it interacts with the GC; do they help at all?

> I'm just trying to think about how cycle collection of WeakMaps can be done
> correctly, and markEntry isn't really strong enough for that, as the CC
> needs to know what map contains the binding, because if the CC decides that
> the weak map is dead, then that affects what bindings are live.  But if your
> WeakMaps can't be in WeakMaps, then that makes things simpler.  Maybe I need
> a third interface for the CC...

WeakMaps can certainly be referred to by WeakMaps. All sorts of cycles are supposed to be supported. A WeakMap's 'mark' method should never be called unless the map has been discovered to be live, so a WeakMap will never invoke its MarkPolicy's markEntryIfLive member function (in the revised patch) unless the map itself is live.
Comment on attachment 542272 [details] [diff] [review]
Allow WeakMaps where the criterion for retaining an entry does not imply that the entry's key has been marked.

Review of attachment 542272 [details] [diff] [review]:
-----------------------------------------------------------------

r=me with a couple of nits. Looks good.

::: js/src/jsweakmap.h
@@ +207,2 @@
>                  /* We revived a value with children, we have to iterate again. */
>                  markedAny = true;

Style nit: Either move the comment or give the if-statement curly braces.

@@ +212,5 @@
>      }
>  
>      void sweep(JSTracer *tracer) {
>          MarkPolicy t(tracer);
> +        /* Remove all entries whose keys remain unmarked. */

Style nit: blank line before a comment (that isn't the first thing in a block).
Attachment #542272 - Flags: review?(jorendorff) → review+
http://hg.mozilla.org/tracemonkey/rev/c2e5e424e6c3
Whiteboard: fixed-in-tracemonkey
Sorry, I understand Andrew's concern here better now.

The cycle collector effectively makes its own copy of the graph of object references, and then analyzes that copy to decide what is really alive. The analysis is not one of the commonly encountered ones: unlike a tracing collector that starts with an assumption that all objects are dead and then discovers that some are live, the cycle collector starts with the assumption that all objects are live but then proves that some are dead (by tentatively breaking cycles and seeing what happens??).

The upshot is that the cycle collector really needs to know about the semantics of WeakMaps --- that entries hold values strongly only if their keys are live --- and we need to figure out how that plays out in the drastically different CC algorithm. Having an object's liveness depend on *two* other objects' liveness is an interesting change, and needs to be thought through by someone who understands the algorithm.
Right.  In terms of this bug, what I need to do is to make it so that the non-marking tracer doesn't actually do anything.  I think I can do that by making markEntry into a no-op, though that seems like an inefficient way to do nothing.
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla8
You need to log in before you can comment on or make changes to this bug.