Closed Bug 660039 Opened 13 years ago Closed 13 years ago

SpiderMonkey needs a WeakMap usable from C++

Categories

(Core :: JavaScript Engine, defect)

x86_64
Linux
defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: jimb, Assigned: jimb)

References

(Blocks 1 open bug)

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(1 file, 4 obsolete files)

Various places in SpiderMonkey would like to have tables that behave like JavaScript WeakMaps --- that have collectable keys and hold their values strongly only when their keys are strongly held --- but can hold arbitrary C++ values. In particular, we need these in the Debug object, which can't use a WeakMap directly because the keys are in a different compartment.

I'd like to add a class template to jsweakmap.h that can be used not only by the WeakMap implementation itself, but by everyone else as well.
Blocks: 636907
Attached patch Minor cleanups to WeakMap. (obsolete) — Splinter Review
Attachment #535564 - Flags: review?(jorendorff)
Builds; not tested.

Not ready for review yet, but comments on general approach very welcome.
This one's reviewable.
Assignee: general → jimb
Attachment #535565 - Attachment is obsolete: true
Status: NEW → ASSIGNED
Attachment #535809 - Flags: review?(jorendorff)
Comment on attachment 535809 [details] [diff] [review]
Provide a WeakMap usable from C++.

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

r- due to a bug that probably needs a new test. I'd like to re-review in order to look at the test. Otherwise this is exactly what we need.

::: js/src/jsapi.cpp
@@ +643,5 @@
>  #endif
>  
>  JSRuntime::JSRuntime()
> +    : gcWeakMapList(NULL),
> +      gcChunkAllocator(&defaultGCChunkAllocator)

Two spaces before the colon (as it was before your change) is more usual, according to naive grepping.

::: js/src/jsweakmap.cpp
@@ +65,5 @@
> +        if (m->markIteratively(tracer))
> +            markedAny = true;
> +    }
> +    return markedAny;
> +}

This costs a virtual method call per WeakMap during GC (and another one during sweep).

We could do this without any virtual method calls. JSRuntime would have several gcWeakMapLists:

  struct JSRuntime {
      ...
      ObjectWeakMap *gcObjectWeakMapList;
      FrameWeakMap  *gcFrameWeakMapList;
      ...

      // support for the WeakMap template
      void getWeakMapList(ObjectWeakMap ***listpp) { *listpp = &gcObjectWeakMapList; }
      void getWeakMapList(FrameWeakMap ***listpp) { *listpp = &gcFrameWeakMapList; }
      ...
  }

GC would run faster, I think, and WeakMapBase would go away. The downside is, the set of allowed WeakMap template instantiations would basically be hardcoded in several places; each time a C++ user starts using a new instantiation of js::WeakMap, that would require more work than just declaring the type and using it. The hardest parts would still be templatized.

r=me on the prettier slower approach, unless it draws a veto from Andreas or Gregor.

::: js/src/jsweakmap.h
@@ +50,5 @@
>  
> +// A C++ weak table, implemented as a subclass of js::HashMap. Keys and values can be
> +// garbage-collected values, and when a key is collected, the table entry disappears. More
> +// precisely, each entry in this table holds its value strongly only when its key is
> +// strongly held.

Phew. There really is no good way to describe this thing, is there.

Some random thoughts, take them or leave them; I have no idea if they are in any way better or worse than what you've written here:

1. Your audience probably mainly wants an explanation of what this tool does, which is your "Keys and values can..." sentence. You could instead say, which amounts to the same thing:

// This is just like a traditional weak-key map, except GC doesn't cause WeakMap entries
// to vanish randomly, just because they haven't been used for a while. Instead, they
// vanish when -- and only when -- the key is GC'd.

2. What was most helpful to me, I think, was to understand how you'd specify the mark-phase behavior (what your "More precisely" sentence does). It might be even better to visually set this off as something formal, like a definition in a math book.

// More precisely, the rule that explains how GC affects WeakMaps is:
//
//     A WeakMap entry is collected if and only if either the WeakMap or the entry's key
//     is collected. If an entry is not collected, it remains in the WeakMap and it has a
//     strong reference to the value.

@@ +95,5 @@
> +// Common base class for all WeakMap specializations. The collector uses this to call
> +// their markIteratively and sweep methods.
> +class WeakMapBase {
> +  public:
> +    WeakMapBase() : next() { }

That next() seems like unnecessary use of a fairly obscure C++ feature. Splurge and say next(NULL)?

@@ +182,5 @@
> +        for (Enum e(*this); !e.empty(); e.popFront()) {
> +            JS_ASSERT(!t.keyMarked(e.front().key) ==
> +                      !t.valueMarked(e.front().value));
> +            if (!t.valueMarked(e.front().value))
> +                e.removeFront();

The value can be marked even if the key is dead. The existing WeakMap::sweep code checks to see if the key was marked, and it does not contain the assertion. That is correct. The new code could fail to sweep an entry when the key is dead.

(js::Debug::sweepAll currently has this assertion, but that's because in that case we additionally know that the value has a strong reference to the key. That does not hold more generally.)

If this passed tests, I think a new test is necessary!

@@ -52,4 @@
>  
>  class JSWeakMap {
>      ObjectValueMap map;
> -    JSObject *next;

Please go a little further and delete class JSWeakMap. I think only an `extern Class WeakMapClass;` needs to be in the header. All the rest can be file-scope in jsweakmap.cpp.
Attachment #535809 - Flags: review?(jorendorff) → review-
Comment on attachment 535563 [details] [diff] [review]
Rename WeakMap to JSWeakMap; plain WeakMap will be the general-purpose C++ class template.

Clearing review flag here; the change is unnecessary if we delete this class. :)
Attachment #535563 - Flags: review?(jorendorff)
Comment on attachment 535564 [details] [diff] [review]
Minor cleanups to WeakMap.

OK.
Attachment #535564 - Flags: review?(jorendorff) → review+
Thanks for the careful review!
(In reply to comment #5)
> Two spaces before the colon (as it was before your change) is more usual,
> according to naive grepping.

Fixed.

> r=me on the prettier slower approach, unless it draws a veto from Andreas or
> Gregor.

It's a virtual call, but probably a pretty predictable one.
> 1. Your audience probably mainly wants an explanation of what this tool
> does, which is your "Keys and values can..." sentence. You could instead
> say, which amounts to the same thing:
> 
> // This is just like a traditional weak-key map, except GC doesn't cause
> WeakMap entries
> // to vanish randomly, just because they haven't been used for a while.
> Instead, they
> // vanish when -- and only when -- the key is GC'd.

I have never heard of a traditional weak-key map in which entries vanish randomly, just because they haven't been used in a while. This description is really confusing.

> 2. What was most helpful to me, I think, was to understand how you'd specify
> the mark-phase behavior (what your "More precisely" sentence does). It might
> be even better to visually set this off as something formal, like a
> definition in a math book.
> 
> // More precisely, the rule that explains how GC affects WeakMaps is:
> //
> //     A WeakMap entry is collected if and only if either the WeakMap or the
> entry's key
> //     is collected. If an entry is not collected, it remains in the WeakMap
> and it has a
> //     strong reference to the value.

I like this, however. I've changed the comment.

> @@ +95,5 @@
> > +// Common base class for all WeakMap specializations. The collector uses this to call
> > +// their markIteratively and sweep methods.
> > +class WeakMapBase {
> > +  public:
> > +    WeakMapBase() : next() { }
> 
> That next() seems like unnecessary use of a fairly obscure C++ feature.
> Splurge and say next(NULL)?

Obscure to you! :D (I'll add the NULL).

> @@ +182,5 @@
> > +        for (Enum e(*this); !e.empty(); e.popFront()) {
> > +            JS_ASSERT(!t.keyMarked(e.front().key) ==
> > +                      !t.valueMarked(e.front().value));
> > +            if (!t.valueMarked(e.front().value))
> > +                e.removeFront();
> 
> The value can be marked even if the key is dead. The existing WeakMap::sweep
> code checks to see if the key was marked, and it does not contain the
> assertion. That is correct. The new code could fail to sweep an entry when
> the key is dead.

This is a flat-out typo, 'value' for 'key'. Thanks very much for catching it. A test should have caught this.

I carelessly lifted the assertion from the Debug code, where it does hold. A test should have caught this, too.

The code now reads:

    void sweep(JSTracer *tracer) {
        MarkPolicy t(tracer);
        for (Enum e(*this); !e.empty(); e.popFront()) {
            if (!t.keyMarked(e.front().value))
                e.removeFront();
        }
    }

> Please go a little further and delete class JSWeakMap. I think only an
> `extern Class WeakMapClass;` needs to be in the header. All the rest can be
> file-scope in jsweakmap.cpp.

Done.

I'll work on the tests.
Err, the code now reads:

    void sweep(JSTracer *tracer) {
        MarkPolicy t(tracer);
        for (Enum e(*this); !e.empty(); e.popFront()) {
            if (!t.keyMarked(e.front().key))
                e.removeFront();
        }
    }
Attachment #535563 - Attachment is obsolete: true
[This patch should address all review comments, and is rebased to depend on the patches for Bug 661567, which needs some of the same cleanups and is possibly more urgent.]

Remove WeakMap class; implement the JavaScript object using functions static to jsweakmap.cpp.

Define a new WeakMap class template, parameterized by Key and Value types,
and accepting a MarkPolicy argument saying how to mark them.

Add assertions to check that we check and set the right mark bits, and
tests that trip them in the presence of mistakes in earlier revisions of
this patch.
Attachment #535564 - Attachment is obsolete: true
Attachment #535809 - Attachment is obsolete: true
Attachment #537820 - Flags: review?(gal)
Hi, Andreas. Review ping? This is pretty simple, and I need it on the Debugger branch.
Comment on attachment 537820 [details] [diff] [review]
Provide a WeakMap usable from C++.

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

r=me.

::: js/src/jsapi.cpp
@@ +643,5 @@
>  #endif
>  
>  JSRuntime::JSRuntime()
> +  : gcWeakMapList(NULL),
> +    gcChunkAllocator(&defaultGCChunkAllocator)

Don't bother. JSRuntime has many fields which must be initialized to NULL. We just memset it somewhere.

I know, disgusting, but that's how it's done.

::: js/src/jsweakmap.cpp
@@ +88,5 @@
>  
> +typedef WeakMap<JSObject *, Value, DefaultHasher<JSObject *>, RuntimeAllocPolicy> ObjectValueMap;
> +
> +static ObjectValueMap *
> +GetObjectMap(JSObject *obj)

These shouldn't be in namespace js, right? Just file-scope seems better. (This is what nameless namespaces are for, but we don't use them...)

@@ +105,5 @@
>      return &vp->toObject();
>  }
>  
> +static JSBool
> +WeakMapHas(JSContext *cx, uintN argc, Value *vp)

I think the prevailing style is to use an underscore in such names: WeakMap_has.

@@ +258,4 @@
>  {
> +    ObjectValueMap *map = GetObjectMap(obj);
> +    if (map)
> +        cx->delete_(map);

Pre-existing nit: JSContext::delete_ allows a non-null pointer, so drop the if.

::: js/src/jsweakmap.h
@@ +134,4 @@
>  
>    protected:
> +    // Instance member functions called by the above. Specializations of WeakMap override
> +    // these with definitions appropriate for their Key and Value types.

Instantiations of WeakMap, not specializations.

@@ +136,5 @@
> +    // Instance member functions called by the above. Specializations of WeakMap override
> +    // these with definitions appropriate for their Key and Value types.
> +    virtual void nonMarkingTrace(JSTracer *tracer) = 0;
> +    virtual bool markIteratively(JSTracer *tracer) = 0;
> +    virtual void sweep(JSTracer *tracer) = 0;

I expressed some concern about GC perf, but I really *really* don't think it's an issue. If we find that it is, we know how to fix it; bring on the follow-up bug.

@@ +148,5 @@
> +template <class Key, class Value,
> +          class HashPolicy = DefaultHasher<Key>,
> +          class AllocPolicy = ContextAllocPolicy,
> +          class MarkPolicy = DefaultMarkPolicy<Key, Value> >
> +class WeakMap : public HashMap<Key, Value, HashPolicy, AllocPolicy>, public WeakMapBase {

Consider getting rid of the AllocPolicy parameter and always using SystemAllocPolicy as the parameter to HashMap. (If you do this, remember to change the comment that says that MarkPolicy is the "fifth template parameter".)
Attachment #537820 - Flags: review?(gal) → review+
http://hg.mozilla.org/tracemonkey/rev/4e6f886b7f2b
Whiteboard: fixed-in-tracemonkey
Sorry for the late comment but removing the WeakMap:: class namespace seems a bit gratuitous. We use it elsewhere too, so this seems a step back.
Let's chat about it on IRC. Jim's first patch in this bug retained class WeakMap, renaming it to JSWeakMap (comment 1), but there were no longer any WeakMap objects being created anywhere, and it was almost empty, plus now we had WeakMapBase, so I asked him to remove it. Jim's on vacation, but let me know what you need and we'll fix it up.
Let me know what you decide to do, as I'm currently working on getting a WeakMap leak fix tested and landed in Bug 653248.  Thanks.  (I don't have any  opinion about the namespace.)
(In this bug is okay...)
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.