Bug 667126: Allow WeakMaps where the criterion for retaining an entry does not imply that the entry's key has been marked. r=jorendorff
authorJim Blandy <jimb@mozilla.com>
Wed, 29 Jun 2011 02:27:47 -0700
changeset 72358 c2e5e424e6c36922a38e0bedd38862a23781d288
parent 72357 756abc094eb18c5bd5c6645225d6108691392a27
child 72359 38322c7498ff46cfeed002028b7ff18618e89b52
push id20706
push usercleary@mozilla.com
push dateWed, 06 Jul 2011 00:33:23 +0000
treeherdermozilla-central@6840fbf4dcdd [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjorendorff
bugs667126
milestone7.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 667126: Allow WeakMaps where the criterion for retaining an entry does not imply that the entry's key has been marked. r=jorendorff This patch replaces the 'markKey' and 'markValue' member functions of the MarkPolicy template parameter with two functions: - markEntryIfLive determines if a map entry should be retained, and, if so ensures its key and value have been marked. - markEntry simply marks an entry's key and value, unconditionally. The comments describe these in more detail.
js/src/jsweakmap.h
--- a/js/src/jsweakmap.h
+++ b/js/src/jsweakmap.h
@@ -80,25 +80,56 @@ namespace js {
 // - Optional fourth template parameter is a class MarkPolicy, with the following constructor:
 //   
 //     MarkPolicy(JSTracer *)
 //
 //   and the following static member functions:
 //
 //     bool keyMarked(Key &k)
 //     bool valueMarked(Value &v)
-//        Return true if k/v has been marked as reachable by the collector, false otherwise.
-//     void markKey(Key &k, const char *description)
-//     void markValue(Value &v, const char *description)
-//        Mark k/v as reachable by the collector, using trc. Use description to identify
-//        k/v in debugging. (markKey is used only for non-marking tracers, other code
-//        using the GC heap tracing functions to map the heap for some purpose or other.)
+//        Return true if k/v has been marked as live by the garbage collector.
+//
+//     bool markEntryIfLive(Key &k, Value &v)
+//        If a table entry whose key is k should be retained, ensure its key and
+//        value are marked. Return true if any previously unmarked objects
+//        became marked.
+//
+//        To ensure that the WeakMap's behavior isn't visibly affected by
+//        garbage collection, this should leave k unmarked only when no key
+//        matching k could ever be produced after this GC cycle completes ---
+//        removing entries whose keys this function leaves unmarked should never
+//        make future lookups fail.
+//
+//        A typical definition of markIteratively would be:
 //
-//   If omitted, this parameter defaults to js::DefaultMarkPolicy<Key, Value>, a policy
-//   template with the obvious definitions for some typical SpiderMonkey type combinations.
+//          if (keyMarked(k) && !valueMarked(v)) {
+//              markObject(*v, "WeakMap entry value");
+//              return true;
+//          }
+//          return false;
+//
+//        This meets the above constraint when, for example, Key is JSObject *:
+//        if k isn't marked, it won't exist once the collection cycle completes,
+//        and thus can't be supplied as a key.
+//
+//        Note that this may mark entries where keyMarked(k) is not initially
+//        true. For example, you could have a table whose keys match when the
+//        values of one of their properties are equal: k1.x === k2.x. An entry
+//        in such a table could be live even when its key is not marked. The
+//        markEntryIfLive function for such a table would generally mark both k and v.
+//
+//     void markEntry(Key &k, Value &v)
+//        Mark the table entry's key and value, k and v, as reachable by the
+//        collector. WeakMap uses this function for non-marking tracers: other
+//        code using the GC heap tracing functions to map the heap for some
+//        purpose or other.
+//
+//   If omitted, the MarkPolicy parameter defaults to js::DefaultMarkPolicy<Key,
+//   Value>, a policy template with the obvious definitions for some typical
+//   SpiderMonkey type combinations.
 
 // A policy template holding default marking algorithms for common type combinations. This
 // provides default types for WeakMap's MarkPolicy template parameter.
 template <class Key, class Value> class DefaultMarkPolicy;
 
 // Common base class for all WeakMap specializations. The collector uses this to call
 // their markIteratively and sweep methods.
 class WeakMapBase {
@@ -158,44 +189,48 @@ class WeakMap : public HashMap<Key, Valu
     typedef typename Base::Enum Enum;
 
   public:
     WeakMap(JSContext *cx) : Base(cx) { }
 
   private:
     void nonMarkingTrace(JSTracer *tracer) {
         MarkPolicy t(tracer);
-        for (Range r = Base::all(); !r.empty(); r.popFront()) {
-            t.markKey(r.front().key, "WeakMap entry key");
-            t.markValue(r.front().value, "WeakMap entry value");
-        }
+        for (Range r = Base::all(); !r.empty(); r.popFront())
+            t.markEntry(r.front().key, r.front().value);
     }
 
     bool markIteratively(JSTracer *tracer) {
         MarkPolicy t(tracer);
         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.keyMarked(r.front().key)) {
-                t.markValue(r.front().value, "WeakMap entry with live key");
+            /* If the entry is live, ensure its key and value are marked. */
+            if (t.markEntryIfLive(r.front().key, r.front().value)) {
                 /* We revived a value with children, we have to iterate again. */
                 markedAny = true;
             }
+            JS_ASSERT_IF(t.keyMarked(r.front().key), t.valueMarked(r.front().value));
         }
         return markedAny;
     }
 
     void sweep(JSTracer *tracer) {
         MarkPolicy t(tracer);
+
+        /* Remove all entries whose keys remain unmarked. */
         for (Enum e(*this); !e.empty(); e.popFront()) {
             if (!t.keyMarked(e.front().key))
                 e.removeFront();
         }
+
 #if DEBUG
-        // Once we've swept, all edges should stay within the known-live part of the graph.
+        /* 
+         * Once we've swept, all remaining edges should stay within the
+         * known-live part of the graph.
+         */
         for (Range r = Base::all(); !r.empty(); r.popFront()) {
             JS_ASSERT(t.keyMarked(r.front().key));
             JS_ASSERT(t.valueMarked(r.front().value));
         }
 #endif
     }
 };
 
@@ -207,21 +242,26 @@ class DefaultMarkPolicy<JSObject *, Valu
   public:
     DefaultMarkPolicy(JSTracer *t) : tracer(t) { }
     bool keyMarked(JSObject *k) { return !IsAboutToBeFinalized(tracer->context, k); }
     bool valueMarked(const Value &v) {
         if (v.isMarkable())
             return !IsAboutToBeFinalized(tracer->context, v.toGCThing());
         return true;
     }
-    void markKey(JSObject *k, const char *description) {
-        js::gc::MarkObject(tracer, *k, description);
+    bool markEntryIfLive(JSObject *k, const Value &v) {
+        if (keyMarked(k) && !valueMarked(v)) {
+            js::gc::MarkValue(tracer, v, "WeakMap entry value");
+            return true;
+        }
+        return false;
     }
-    void markValue(const Value &v, const char *description) {
-        js::gc::MarkValue(tracer, v, description);
+    void markEntry(JSObject *k, const Value &v) {
+        js::gc::MarkObject(tracer, *k, "WeakMap entry key");
+        js::gc::MarkValue(tracer, v, "WeakMap entry value");
     }
 };
 
 // The class of JavaScript WeakMap objects.
 extern Class WeakMapClass;
 
 }