685841 - Add WeakCache (like WeakMap, but entry life is based on the value mark instead of the key)

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicolas B. Pierron [:nbp]]

Current WeakMap implementation only support to mark entry as live if the key is marked.  This issue suggest to add the other case where an entry is kept alive if the value is marked.

This is necessary in Bug 680315 to map VM function to their wrappers (which are created for unique in each compartment).  The interest is to garbage collect wrapper code if all references of the wrapper are garbage collected.

The concept of marking the key instead of value implies that Bug 684595 must be reverted.  But for the use case of Bug 680315, this is not necessary because the key is a static variable pointer, which cannot be marked.

Comment 1

[Andrew McCreight [:mccr8]]

markEntry is used by non-marking tracers (the name could probably be better) to enumerate things reachable from a WeakMap.  Even if the value is used to keep the entry alive instead of the key, you still can't reach the keys contained in a WeakMap.

To do what you are suggesting requires changing markEntryIfLive, which is used by the GC and still takes both key and value, so I think it should be fine as-is.

Comment 2

[Nicolas B. Pierron [:nbp]]

(In reply to Andrew McCreight [:mccr8] from comment #1)
> markEntry is used by non-marking tracers (the name could probably be better)
> to enumerate things reachable from a WeakMap.  Even if the value is used to
> keep the entry alive instead of the key, you still can't reach the keys
> contained in a WeakMap.

Thus what was the Key argument removed from Bug 684595, cannot it be used to mark the Key?  Unless you mean that the Key used by the WeakMap to map to the Entry cannot be reached and thus marked?  Could it be marked by WeakMap::markInteractively if the entry is marked?

> To do what you are suggesting requires changing markEntryIfLive, which is
> used by the GC and still takes both key and value, so I think it should be
> fine as-is.

I did a patch locally (reason why I assign it to me), I still need to separate it from others modifications and improve comments.

To change the rule for collecting entries, I introduced a SweepPolicy parameter as well as MarkKeyPolicy.

The patch also introduces a MarkOf parametric class to factor:

    static bool marked(JSContext *cx, const Value &v);
    static bool mark(JSTracer *trc, Value &v, const char *name);

Also, I replaced the JSTracer by a JSContext to follow mark & sweep functions arguments.

Comment 3

[Andrew McCreight [:mccr8]]

(In reply to Nicolas B. Pierron [:pierron] from comment #2)
> Thus what was the Key argument removed from Bug 684595, cannot it be used to
> mark the Key?  Unless you mean that the Key used by the WeakMap to map to
> the Entry cannot be reached and thus marked?  Could it be marked by
> WeakMap::markInteractively if the entry is marked?

markEntry, despite its name, does not actually mark anything.  It is never called by the GC.  It is only called from nonMarkingTrace.  It is used by non-GC tracers, like the cycle collector, xpc_UnmarkGrayObjectRecursive and JS_DumpHeap.

markEntryIfLive, on the other hand, is called from WeakMap::markIteratively, and is called by the GC.  This function decides if an entry is live, and marks things if it is.

If you want values to keep entries alive, instead of keys, you'd want a markEntryIfLive like this (in the case of JSObjects for keys and values):

    bool markEntryIfLive(JSObject *k, JSObject *v) {
        if (valueMarked(v) && !keyMarked(k)) {
            js::gc::MarkObject(tracer, *k, "WeakMap key");
            return true;
        }
        return false;
    }

The markEntry function would just be the same:
    void markEntry(JSObject *v) {
        js::gc::MarkObject(tracer, *v, "WeakMap entry value");
    }

> > To do what you are suggesting requires changing markEntryIfLive, which is
> > used by the GC and still takes both key and value, so I think it should be
> > fine as-is.
> 
> I did a patch locally (reason why I assign it to me), I still need to
> separate it from others modifications and improve comments.
> 
> To change the rule for collecting entries, I introduced a SweepPolicy
> parameter as well as MarkKeyPolicy.

Do you really need a whole new SweepPolicy?  I'd think you could just add an entryIsLive method to MarkPolicy, that takes a key and value and returns a boolean.  Then the loop in sweep could be something like:

        for (Enum e(*this); !e.empty(); e.popFront()) {
            if (!t.entryIsLive(e.front().key, e.front().value))
                e.removeFront();
        }

For the existing cases, entryIsLive checks if the key is marked.  For your case, it would check if the value is marked.

> The patch also introduces a MarkOf parametric class to factor:
> 
>     static bool marked(JSContext *cx, const Value &v);
>     static bool mark(JSTracer *trc, Value &v, const char *name);

I'm not sure what you mean here, or why these are needed.

> Also, I replaced the JSTracer by a JSContext to follow mark & sweep
> functions arguments.

I don't understand why you need to do that.  The JSTracer is needed for markIteratively and sweep, and contains a context.

Comment 4

[Nicolas B. Pierron [:nbp]]

(In reply to Andrew McCreight [:mccr8] from comment #3)
> (In reply to Nicolas B. Pierron [:pierron] from comment #2)
> > Thus what was the Key argument removed from Bug 684595, cannot it be used to
> > mark the Key?  Unless you mean that the Key used by the WeakMap to map to
> > the Entry cannot be reached and thus marked?  Could it be marked by
> > WeakMap::markInteractively if the entry is marked?
> 
> markEntry, despite its name, does not actually mark anything.  It is never
> called by the GC.  It is only called from nonMarkingTrace.  It is used by
> non-GC tracers, like the cycle collector, xpc_UnmarkGrayObjectRecursive and
> JS_DumpHeap.

So markEntry should be renamed visitEntry, or more precisely visitValue.

> markEntryIfLive, on the other hand, is called from WeakMap::markIteratively,
> and is called by the GC.  This function decides if an entry is live, and
> marks things if it is.
> 
> If you want values to keep entries alive, instead of keys, you'd want a
> markEntryIfLive like this (in the case of JSObjects for keys and values):
> 
>     bool markEntryIfLive(JSObject *k, JSObject *v) {
>         if (valueMarked(v) && !keyMarked(k)) {
>             js::gc::MarkObject(tracer, *k, "WeakMap key");
>             return true;
>         }
>         return false;
>     }

I did.

> The markEntry function would just be the same:
>     void markEntry(JSObject *v) {
>         js::gc::MarkObject(tracer, *v, "WeakMap entry value");
>     }

ok.

> > > To do what you are suggesting requires changing markEntryIfLive, which is
> > > used by the GC and still takes both key and value, so I think it should be
> > > fine as-is.
> > 
> > I did a patch locally (reason why I assign it to me), I still need to
> > separate it from others modifications and improve comments.
> > 
> > To change the rule for collecting entries, I introduced a SweepPolicy
> > parameter as well as MarkKeyPolicy.
> 
> Do you really need a whole new SweepPolicy?  I'd think you could just add an
> entryIsLive method to MarkPolicy, that takes a key and value and returns a
> boolean.  Then the loop in sweep could be something like:
> 
>         for (Enum e(*this); !e.empty(); e.popFront()) {
>             if (!t.entryIsLive(e.front().key, e.front().value))
>                 e.removeFront();
>         }

In fact I don't need the sweep policy but this seems more consistent with the markPolicy class.

> For the existing cases, entryIsLive checks if the key is marked.  For your
> case, it would check if the value is marked.
> 
> > The patch also introduces a MarkOf parametric class to factor:
> > 
> >     static bool marked(JSContext *cx, const Value &v);
> >     static bool mark(JSTracer *trc, Value &v, const char *name);
> 
> I'm not sure what you mean here, or why these are needed.

These are needed to abstract the policy from their objects. Thus you don't need to re-implement a policy for each pair of type.  Thus adding a new Key/Value type (which is my case in IonMonkey, a structure and a IonCode) implies specializing the MarkOf class where this is needed.  The following class can apply without copying it for each pair of type:

template <class Key, class Value>
class DefaultMarkPolicy {
  protected:
    JSTracer *tracer;
  public:
    DefaultMarkPolicy(JSTracer *t) : tracer(t) { }
    bool keyMarked(Key k)     { return MarkOf<Key>::marked(tracer->context, k); }
    bool valueMarked(Value v) { return MarkOf<Value>::marked(tracer->context, v); }
    bool markEntryIfLive(Key k, Value v) {
        if (keyMarked(k) && !valueMarked(v)) {
            MarkOf<Value>::mark(tracer, v, "WeakMap entry value");
            return true;
        }
        return false;
    }
    void markEntry(Key k, Value v) {
        MarkOf<Key>::  mark(tracer, k, "WeakMap entry key");
        MarkOf<Value>::mark(tracer, v, "WeakMap entry value");
    }
};


> > Also, I replaced the JSTracer by a JSContext to follow mark & sweep
> > functions arguments.
> 
> I don't understand why you need to do that.  The JSTracer is needed for
> markIteratively and sweep, and contains a context.

I needed that to initialize properly the sweepPolicy

    bool markIteratively(JSTracer *tracer) {
        MarkPolicy t(tracer);
        ...
    }

    void sweep(JSContext *cx) {
        SweepPolicy s(cx);
        ...
    }

Comment 5

[Andrew McCreight [:mccr8]]

(In reply to Nicolas B. Pierron [:pierron] from comment #4)
> So markEntry should be renamed visitEntry, or more precisely visitValue.

traceEntry or traceValue would be more consistent, but yeah, something like that.  Maybe even nonMarkingTraceEntry, though that's a bit long.

> In fact I don't need the sweep policy but this seems more consistent with
> the markPolicy class.

Well, we could rename markPolicy to markSweepPolicy and they could just be combined.

I guess I don't fully understand all of what you are doing.  Could you attach the current version of your patch so I can just see the whole thing?  Maybe that will help me.

Comment 6

[Nicolas B. Pierron [:nbp]]

Attachment: Draft.

In the current draft, you should have a look at js/src/jsweakmap.h for the initial patch and at js/src/ion/IonCompartment.h for a use case with different type than JSOject * and Value.

Comment 7

[Andrew McCreight [:mccr8]]

One problem I can see is that it looks like you never trace functionWrappers.  I think that needs to be done in IonCompartment::mark.  Otherwise it will never mark or sweep the WeakMap.

Comment 8

[Nicolas B. Pierron [:nbp]]

(In reply to Andrew McCreight [:mccr8] from comment #7)
> One problem I can see is that it looks like you never trace
> functionWrappers.  I think that needs to be done in IonCompartment::mark. 
> Otherwise it will never mark or sweep the WeakMap.

I tried to mark it, but the function used for marking WeakMap is private, and used inside WeakMapBase::markAllIteratively, which use a list of WeakMap to do the marking for all the WeakMap.

Comment 9

[Andrew McCreight [:mccr8]]

You want to use WeakMapBase::trace.  This will add the weak map to the list that markAllIteratively will later use.

Comment 10

[Nicolas B. Pierron [:nbp]]

Attachment: [0001] Add MarkOf

Comment 11

[Nicolas B. Pierron [:nbp]]

Attachment: [0002] Add sweepEntry function.

Comment 12

[Nicolas B. Pierron [:nbp]]

Attachment: [0003] Add Mark Key policy.

Comment 13

[Nicolas B. Pierron [:nbp]]

The current patches may not apply on the top-level due to the modification of Bug 684595, but it should not be hard to merge the modifications, only replicates markEntry modification to the patches.

Comment 14

[Nicolas B. Pierron [:nbp]]

Attachment: [0002] Add sweepEntry function.

Comment 15

[Nicolas B. Pierron [:nbp]]

Attachment: [0003] Add Mark Key policy.

Comment 16

[Andrew McCreight [:mccr8]]

Do you want a review on the [0001] patch?  You should probably also put it into its own bug, as I think it would be an improvement independent of the value marking thing.

Comment 17

[Nicolas B. Pierron [:nbp]]

(In reply to Andrew McCreight [:mccr8] from comment #16)
> Do you want a review on the [0001] patch?  You should probably also put it
> into its own bug, as I think it would be an improvement independent of the
> value marking thing.

Do you have any idea who should I CC to this new bug, I feel that this is more general than the WeakMap use case.

I have to admit that I tempted to get the MarkOf patch landed to avoid blocking other modifications / doing the same modification without the MarkOf class.  Can we land temporary modification, or should I open 2 bugs for it (one for minimal, and another for the refined version)?

Comment 18

[Andrew McCreight [:mccr8]]

Just clone this bug to make the new one (link at the bottom right of this page).  I think most people who have been working on the WeakMap code are CCed to this one now.

I think the MarkOf stuff is a good change, so we should land it separately.  It would be good to have a patch that refactors things a bit, but does not change behavior.  I need to sit down and spend some time thinking about whether using the value to keep things alive will cause problems with any invariants of the GC or CC.

Comment 19

[Andrew McCreight [:mccr8]]

Are there no other ways to do weak references in the JS engine?  It seems like what you really want is just a mapping from whatever keys you are using to weak references to the data.  Though that will leak entries.  I'm just a little nervous about using weak maps to implement something that isn't a weak map.

Comment 20

[Nicolas B. Pierron [:nbp]]

(In reply to Andrew McCreight [:mccr8] from comment #19)
> Are there no other ways to do weak references in the JS engine?  It seems
> like what you really want is just a mapping from whatever keys you are using
> to weak references to the data.  Though that will leak entries.

And I need a map with way to either discard an entry or check that the memory is no longer used by the weak reference.

Comment 21

[Andrew McCreight [:mccr8]]

Sure, well, a weak reference gives you way to check whether the referent is still alive or not.  I guess you can avoid leaking entries by periodically scanning the map and removing entries where the value is not alive.  I guess there aren't any in the JS engine, or they'd show up in the GC somewhere.

Comment 22

[Nicolas B. Pierron [:nbp]]

I don't really see what you mean by weak reference (do you have pointers the to WeakRef<Type> class), unless you mean not marking the values and sweeping the entries which are not marked.

I think the later option can be implemented instead of the current implementation based on WeakMap but I find it a little sad to deliberately avoid marking some markable fields of a class.

Comment 23

[Andrew McCreight [:mccr8]]

Sorry I've been taking so long thinking about this.  I think in the particular case of the GC, anything would probably work, but I'd like to think about what exactly the semantics of this new map are supposed to be.  Depending on what they are, it may require additional work to support cycle collector integration in general, but that can be worked around.

For the purposes of the discussion, let's call these new variants of weak maps "weak caches".  Probably a terrible name (redundant if nothing else), but whatever.

What exactly is the reachability relation for weak caches?  For this particular case, there seem to be 4 entities of interest: the map, the key, the value, and the entry.  The entry is the actual representation in the map of the key-value binding.  The entry may not be very interesting, but it is actively managed during the sweep, so maybe it will be useful to think about it.

For a normal map, if the map is reachable, then the entry, key and value are all reachable.

For a weak map, if the map and the key are both reachable, then the entry and value are both reachable.

For a weak cache, if the map and value are reachable, then the entry is reachable.  What about the key?  Does the map and value being reachable imply that the key is reachable?  It doesn't seem like the map and value being reachable should imply that the key should be reachable, as there's no way to get to the key from there, but at the same time, having an entry sitting around with a dead pointer seems silly.

Therefore, maybe the semantics for a weak cache should be that if the map, key and value are all reachable, then the entry is reachable.  Thus the weak cache is really only managing the lifetime of the entry.

Comment 24

[Nicolas B. Pierron [:nbp]]

Attachment: [0003] Add Mark Cache policy.

Cache may not be a good name, because a weak map is a persistent weak cache.

Comment 25

[Andrew McCreight [:mccr8]]

I think that if Comment 23 is right, then the cycle collector can ignore weak caches entirely, as they only result in entries staying alive, which can't be part of cycles.

Comment 26

[Andrew McCreight [:mccr8]]

Comment on attachment 560371 [details] [diff] [review]
[0002] Add sweepEntry function.

Sorry for dropping the ball here, though I think this wasn't rebased to deal with Bug 687843 anyways.  As I said in there, Bill is also working on a similar refactoring for the MarkOf stuff, so once you and he work something out for that, we can revisit this caching stuff.

Comment 27

[Nicolas B. Pierron [:nbp]]

Attachment: [0001] Add sweepEntry function.

- MarkOf patch is obsolete since it has been moved to its own bug (Bug 687843).
- Update sweep entry patch.

Comment 28

[Nicolas B. Pierron [:nbp]]

Attachment: [0002] Add Mark Cache policy.

Follow updates.

Comment 29

[Andrew McCreight [:mccr8]]

Do you have an example of how this is used?  I looked at your patches in bug 680315, but I didn't find anything with the word "cache" in it.

Comment 30

[Nicolas B. Pierron [:nbp]]

Attachment: [0001] Add sweepEntry function.

rebase.

Comment 31

[Nicolas B. Pierron [:nbp]]

Attachment: [0002] Add Mark Cache policy.

rebase.

Comment 32

[Andrew McCreight [:mccr8]]

Comment on attachment 567792 [details] [diff] [review]
[0001] Add sweepEntry function.

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

r=me with my comments addressed.

::: js/src/jsweakmap.h
@@ +129,5 @@
>  //   SpiderMonkey type combinations.
>  
>  // A policy template holding default marking algorithms for common type combinations. This
> +// provides default types for WeakMap's MarkPolicy template parameter.  It Marks the
> +// mapped value and sweep the entry if the key is not marked.

Please add a new section in the comment above here that describes sweepEntry, like the one for markEntry (the section that starts with "Mark the table entry's value v as reachable by the collector.")

@@ +290,5 @@
>      bool valueMarked(Value v) { return getMark(tracer->context, v); }
>      void markEntry(Value v) {
>          setMark(tracer, v, "WeakMap entry value");
>      }
> +    bool sweepEntry(Key k, DebugOnly<Value> v)

v shouldn't be debug only, as we always pass it the value in the sweep function above.  This probably won't compile in an opt build. ;)

Comment 33

[Andrew McCreight [:mccr8]]

Comment on attachment 567793 [details] [diff] [review]
[0002] Add Mark Cache policy.

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

Looks good.  I like how simple this ended up being.

r=me with my review comments addressed.

::: js/src/jsweakmap.h
@@ +368,5 @@
>          return false;
>      }
>  };
>  
> +// Marking policy.

Please add a short description here about what kind of marking policy this is, and what it is useful for.

@@ +371,5 @@
>  
> +// Marking policy.
> +//
> +// Mark the key if the value is marked and sweep the entry if the value is
> +// not marked.

This comment is not accurate any more and should be fixed.

@@ +374,5 @@
> +// Mark the key if the value is marked and sweep the entry if the value is
> +// not marked.
> +template <class Key, class Value>
> +class MarkCachePolicy : public MarkPolicyBase<Key, Value> {
> +    typedef MarkPolicyBase<Key, Value> base;

Maybe a name like CacheMarkPolicy would be better?  This is a mark policy, not a cache policy, I think.

@@ +381,5 @@
> +    MarkCachePolicy(JSTracer *t) : base(t) { }
> +
> +    bool isEntryAlive(Key k, Value v) {
> +        return valueMarked(v) && keyMarked(k);
> +    }

isEntryAlive should be private (or at least protected, if you think you might extend this class later).

Comment 34

[Nicolas B. Pierron [:nbp]]

(In reply to Andrew McCreight [:mccr8] from comment #32)
> @@ +290,5 @@
> >      bool valueMarked(Value v) { return getMark(tracer->context, v); }
> >      void markEntry(Value v) {
> >          setMark(tracer, v, "WeakMap entry value");
> >      }
> > +    bool sweepEntry(Key k, DebugOnly<Value> v)
> 
> v shouldn't be debug only, as we always pass it the value in the sweep
> function above.  This probably won't compile in an opt build. ;)

It compiles in opt builds.  The reason it compiles is that the argument still exists.  The argument is a DebugOnly<T> which means that in optimized code, this still consume one argument space and that the value given as argument is still computed.  But you cannot use the content of the value.

The only way to remove the computation of  e.front().value  would be to add #ifdef DEBUG instead of DebugOnly<T>.

Comment 35

[Nicolas B. Pierron [:nbp]]

Attachment: [0001] Add sweepEntry function.

(old patch + modifications: r=mccr8)

Comment sweepEntry function excepted to be provided by MarkPolicies.

Comment 36

[Nicolas B. Pierron [:nbp]]

Attachment: [0002] Add Mark Cache policy.

(old patch + modifications: r=mccr8)

- Document Cache marking policy.
- Make isEntryAlive private.

Comment 37

[Nicolas B. Pierron [:nbp]]

Attachment: [0001] Add sweepEntry function.

Comment 38

[Nicolas B. Pierron [:nbp]]

Attachment: [0002] Add Mark Cache policy.

Comment 39

[Andrew McCreight [:mccr8]]

(In reply to Nicolas B. Pierron [:pierron] from comment #34)
> It compiles in opt builds.  The reason it compiles is that the argument
> still exists.  The argument is a DebugOnly<T> which means that in optimized
> code, this still consume one argument space and that the value given as
> argument is still computed.  But you cannot use the content of the value.

Ah, neat!

> The only way to remove the computation of  e.front().value  would be to add
> #ifdef DEBUG instead of DebugOnly<T>.

Probably not a big deal.  The compiler might inline everything to the point where it can figure out it doesn't need to call value anyways.

Nits for this comment in your revised patch:
"This policy make the weak map react as a cache (key -> value) which discard a cache entry as soon as either its value or its key are no longer marked at the sweep phase."

"make the weak map" should be "makes the weak map"
"which discard" should be "which discards"
"are no longer marked at the sweep phase" should either be "are no longer marked during the marking phase" or more simply "are no longer live"

Otherwise, looks great.

Comment 40

[Andrew McCreight [:mccr8]]

Oh, I see what you mean by "at the sweep phase".  You mean "by the time of the sweep phase" or something.  Just saying the key or value are no longer live might be more direct.  That kind of implies that they are no longer live at the time of the sweep phase, without getting into the gritty details.

Comment 41

[Nicolas B. Pierron [:nbp]]

Attachment: [0002] Add Mark Cache policy.

Comment 42

[Jim Blandy :jimb]

I'm coming into this discussion a bit late, but it does seem strange to have WeakMaps doing this job. Certainly anything could be templatized to work any way one pleases, but I wonder how much value the common code provides, over just copying jsweakmap.h, renaming, and writing what you really want.

(I don't understand things well enough yet, but intuitively it seems like the use case wants something else entirely...)

Comment 43

[Jim Blandy :jimb]

Sorry, that's a really vague and un-actionable comment. To be clear, I have no objections to the patch or the plan. I'll read bug 680315 and talk with npierron and mccr8 on IRC to clear up my concerns.

Comment 44

[Nicolas B. Pierron [:nbp]]

Attachment: Add WeakCache class.

Follow jimb comment and create a class which map a key to a value and which keep the entry live as long as both key & value are live.

Comment 45

[Jim Blandy :jimb]

Comment on attachment 569982 [details] [diff] [review]
Add WeakCache class.

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

Looks good.

::: js/src/jscache.h
@@ +50,5 @@
> +namespace js {
> +
> +// A WeakCache is used to map a key to a value similar to an HashMap except
> +// that its entries are garbage collect.  An entry is kept as long as
> +// the key or the value is live (marked).

I think this comment is wrong and the code is correct: an entry is kept as long as both the key and value are marked.

In the only use for this template we have at present, the key (a C++ function pointer) doesn't have a mark bit --- isn't that so?

One of the things the WeakMap type does (via the WeakMapBase class) is keep a list of all WeakMap instances that the garbage collector can walk at the appropriate time to clean things up. WeakCache has no need to participate in the 'markAllIteratively' phase, but it seems to me that it must participate in the sweepAll phase, so something analogous has to happen there. However, in the use we know of, there is one instance of this template per compartment, is that correct? So the 'sweep' method can be easily called from JSCompartment::sweep.

@@ +67,5 @@
> +
> +  public:
> +    // Does not do anything, but the declaration of it is used to be
> +    // consistent with the default interface of GC objects which are
> +    // providing both mark and sweep functions.

I think you could leave this out for now.

Comment 46

[Nicolas B. Pierron [:nbp]]

(In reply to Jim Blandy :jimb from comment #45)
> Comment on attachment 569982 [details] [diff] [review] [diff] [details] [review]
> Add WeakCache class.
> 
> Review of attachment 569982 [details] [diff] [review] [diff] [details] [review]:
> -----------------------------------------------------------------
> 
> Looks good.
> 
> ::: js/src/jscache.h
> @@ +50,5 @@
> > +namespace js {
> > +
> > +// A WeakCache is used to map a key to a value similar to an HashMap except
> > +// that its entries are garbage collect.  An entry is kept as long as
> > +// the key or the value is live (marked).
> 
> I think this comment is wrong and the code is correct: an entry is kept as
> long as both the key and value are marked.

Indeed.

> In the only use for this template we have at present, the key (a C++
> function pointer) doesn't have a mark bit --- isn't that so?

Yes, the pointer is a pointer to the static part of the program.  It is not handled by the GC.  The key is always considered as marked because it is analogous to a root of the GC.

Thus for the only use-case, I needed to have a Cache which determine the liveness of an entry based on the value.  As Andrew (comment #23) explained, the key should also be considered because if the key is no longer alive, then the cache is pointless.

> One of the things the WeakMap type does (via the WeakMapBase class) is keep
> a list of all WeakMap instances that the garbage collector can walk at the
> appropriate time to clean things up. WeakCache has no need to participate in
> the 'markAllIteratively' phase, but it seems to me that it must participate
> in the sweepAll phase, so something analogous has to happen there. However,
> in the use we know of, there is one instance of this template per
> compartment, is that correct? So the 'sweep' method can be easily called
> from JSCompartment::sweep.

The sweepAll phase is only a call to all WeakMap::sweep registered into the list of WeakMap by the call of the trace function during the marking phase.  In fact I don't see any reason to have this sweepAll function and I would prefer to have the sweep function of WeakMap as public.

> @@ +67,5 @@
> > +
> > +  public:
> > +    // Does not do anything, but the declaration of it is used to be
> > +    // consistent with the default interface of GC objects which are
> > +    // providing both mark and sweep functions.
> 
> I think you could leave this out for now.

This is only for the sake of consistency, the compiler, by seeing this non-virtual mark function will just inline (remove) the call of the mark function.  And I think this would be weird to readers to see a field only swept and not marked.

Comment 47

[Jim Blandy :jimb]

(In reply to Nicolas B. Pierron [:pierron] from comment #46)
> > @@ +67,5 @@
> > > +
> > > +  public:
> > > +    // Does not do anything, but the declaration of it is used to be
> > > +    // consistent with the default interface of GC objects which are
> > > +    // providing both mark and sweep functions.
> > 
> > I think you could leave this out for now.
> 
> This is only for the sake of consistency, the compiler, by seeing this
> non-virtual mark function will just inline (remove) the call of the mark
> function.  And I think this would be weird to readers to see a field only
> swept and not marked.

The fact that it is swept and not marked is the defining characteristic of a weak reference. WeakMaps are oddly named ("Weak Map" was chosen over the inventors' term, "Ephemeron Table"); in most languages, a weak reference is an object pointer that is cleared to 'null' when there are no non-weak references to the object. In other words, a weak reference is one that does not participate in the mark phase, and is cleared in the sweep phase if its referent was not marked.

So while it might be surprising, the reader would be noticing the essential property of the type. The broken symmetry is what it's all about. The best thing would be a comment saying, "We don't mark along this sort of edge here"; an effect-free function call that a casual reader would assume does mark something is the wrong direction.

So, I hope you'll change the patch, but feel free to commit it either with or without this change; it doesn't affect my r+.

Comment 48

[Andrew McCreight [:mccr8]]

I agree with Jim.  I think you should just remove the mark function.  The entire point of this class is that it does not mark! :)  Like Jim said, add a comment explaining why we don't have a mark function.

Also, your copyright notice isn't quite right:
* Portions created by the Initial Developer are Copyright (C) 2009

That should be 2011.  I'm not sure if the weak map file is actually from 2009 (maybe it should be 2010), but this new file is certainly from 2011.

The Spidermonkey 1.9 release in 2008 part is probably out of date?  It is often better to just grab the license stuff from here: http://www.mozilla.org/MPL/boilerplate-1.1/ rather than copying it from other files.

How do you intend for the sweep function to be invoked?  Are you going to manually invoke it from whatever structure is going to hold this function?

I agree with Nicolas about having the mark function for keys.  For the intended use case, this will just be a function that returns true, but if you are going to have a templated class, then generically checking the mark is the thing to do.

Comment 49

[Nicolas B. Pierron [:nbp]]

Attachment: Add WeakCache class.

Apply recommended modifications (remove mark function, fix header).  Fix sweep function comments.

Comment 50

[Nicolas B. Pierron [:nbp]]

(In reply to Andrew McCreight [:mccr8] from comment #48)
> How do you intend for the sweep function to be invoked?  Are you going to
> manually invoke it from whatever structure is going to hold this function?

The holder of the WeakCache is currently responsible for calling the sweep function.  The sweepAll function does not seems to be a good choice after all, because it implies more code and more code to be executed.

Comment 51

[Andrew McCreight [:mccr8]]

Comment on attachment 570831 [details] [diff] [review]
Add WeakCache class.

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

Just a few minor comment nits.  Looks good.

::: js/src/jscache.h
@@ +48,5 @@
> +
> +namespace js {
> +
> +// A WeakCache is used to map a key to a value similar to an HashMap except
> +// that its entries are garbage collect.  An entry is kept as long as

should be "garbage collected"

@@ +52,5 @@
> +// that its entries are garbage collect.  An entry is kept as long as
> +// both the key and value are marked.
> +//
> +// No mark function is provided with this weak container.  However, this weak
> +// container should take part into the sweep phase.

"into" should be "in"

Comment 52

[Andrew McCreight [:mccr8]]

(In reply to Nicolas B. Pierron [:pierron] from comment #50)
> The holder of the WeakCache is currently responsible for calling the sweep
> function.  The sweepAll function does not seems to be a good choice after
> all, because it implies more code and more code to be executed.
Yes, I think that's the right way to go, as this is being used as a C++ container.

Comment 53

[Nicolas B. Pierron [:nbp]]

Attachment: Add WeakCache class.

Fix typos in comments.

Comment 54

[David Anderson [:dvander] - inactive, e-mail if emergency]

https://hg.mozilla.org/projects/ionmonkey/rev/fadc027ca1ec