Bug 710492 - add special cycle collector shape tracing path. r=bhackett
authorAndrew McCreight <amccreight@mozilla.com>
Mon, 19 Dec 2011 10:24:56 -0800
changeset 83068 721897529f74dfed5c5dd5363cd376cc47264943
parent 83067 dd2f9236b59198fafabe851c80c0d4fad4fc5244
child 83069 b4d859a1e3386d97a2af75bebaf9d2a3656e9d6e
push idunknown
push userunknown
push dateunknown
reviewersbhackett
bugs710492
milestone11.0a1
Bug 710492 - add special cycle collector shape tracing path. r=bhackett
js/src/jsfriendapi.cpp
js/src/jsfriendapi.h
js/src/jsgcmark.cpp
js/src/jsgcmark.h
js/xpconnect/src/nsXPConnect.cpp
--- a/js/src/jsfriendapi.cpp
+++ b/js/src/jsfriendapi.cpp
@@ -138,20 +138,20 @@ JS_GetCompartmentPrincipals(JSCompartmen
 }
 
 JS_FRIEND_API(JSBool)
 JS_WrapPropertyDescriptor(JSContext *cx, js::PropertyDescriptor *desc)
 {
     return cx->compartment->wrap(cx, desc);
 }
 
-JS_FRIEND_API(void *)
-JS_TraceShapeChildrenAcyclic(JSTracer *trc, void *shape)
+JS_FRIEND_API(void)
+JS_TraceShapeCycleCollectorChildren(JSTracer *trc, void *shape)
 {
-    return (void *)MarkShapeChildrenAcyclic(trc, (const Shape *)shape);
+    MarkCycleCollectorChildren(trc, (const Shape *)shape);
 }
 
 AutoPreserveCompartment::AutoPreserveCompartment(JSContext *cx
                                                  JS_GUARD_OBJECT_NOTIFIER_PARAM_NO_INIT)
   : cx(cx), oldCompartment(cx->compartment)
 {
     JS_GUARD_OBJECT_NOTIFIER_INIT;
 }
--- a/js/src/jsfriendapi.h
+++ b/js/src/jsfriendapi.h
@@ -81,21 +81,22 @@ JS_SetProtoCalled(JSContext *cx);
 
 extern JS_FRIEND_API(size_t)
 JS_GetCustomIteratorCount(JSContext *cx);
 
 extern JS_FRIEND_API(JSBool)
 JS_NondeterministicGetWeakMapKeys(JSContext *cx, JSObject *obj, JSObject **ret);
 
 /*
- * Marks all the children of a shape except the parent, which avoids using
- * unbounded stack space. Returns the parent.
+ * Used by the cycle collector to trace through the shape and all
+ * shapes it reaches, marking all non-shape children found in the
+ * process. Uses bounded stack space.
  */
-extern JS_FRIEND_API(void *)
-JS_TraceShapeChildrenAcyclic(JSTracer *trc, void *shape);
+extern JS_FRIEND_API(void)
+JS_TraceShapeCycleCollectorChildren(JSTracer *trc, void *shape);
 
 enum {
     JS_TELEMETRY_GC_REASON,
     JS_TELEMETRY_GC_IS_COMPARTMENTAL,
     JS_TELEMETRY_GC_IS_SHAPE_REGEN,
     JS_TELEMETRY_GC_MS,
     JS_TELEMETRY_GC_MARK_MS,
     JS_TELEMETRY_GC_SWEEP_MS
--- a/js/src/jsgcmark.cpp
+++ b/js/src/jsgcmark.cpp
@@ -905,63 +905,97 @@ MarkChildren(JSTracer *trc, JSScript *sc
 
     if (script->types)
         script->types->trace(trc);
 
     if (script->hasAnyBreakpointsOrStepMode())
         script->markTrapClosures(trc);
 }
 
-const Shape *
-MarkShapeChildrenAcyclic(JSTracer *trc, const Shape *shape)
-{
-    /*
-     * This function is used by the cycle collector to ensure that we use O(1)
-     * stack space when building the CC graph. It must avoid traversing through
-     * an unbounded number of shapes before reaching an object. (Objects are
-     * added to the CC graph, so reaching one terminates the recursion.)
-     *
-     * Traversing through shape->base() will use bounded space. All but one of
-     * the fields of BaseShape is an object, and objects terminate the
-     * recursion. An owned BaseShape may point to an unowned BaseShape, but
-     * unowned BaseShapes will not point to any other shapes. So the recursion
-     * is bounded.
-     */
-    MarkBaseShapeUnbarriered(trc, shape->base(), "base");
-    MarkIdUnbarriered(trc, shape->maybePropid(), "propid");
-    return shape->previous();
-}
-
 void
 MarkChildren(JSTracer *trc, const Shape *shape)
 {
-    /*
-     * We ignore the return value of MarkShapeChildrenAcyclic and use
-     * shape->previous() instead so that the return value has MarkablePtr type.
-     */
-    MarkShapeChildrenAcyclic(trc, shape);
+    MarkBaseShapeUnbarriered(trc, shape->base(), "base");
+    MarkIdUnbarriered(trc, shape->maybePropid(), "propid");
     if (shape->previous())
         MarkShape(trc, shape->previous(), "parent");
 }
 
+inline void
+MarkBaseShapeGetterSetter(JSTracer *trc, BaseShape *base)
+{
+    if (base->hasGetterObject())
+        MarkObjectUnbarriered(trc, base->getterObject(), "getter");
+    if (base->hasSetterObject())
+        MarkObjectUnbarriered(trc, base->setterObject(), "setter");
+}
+
 void
 MarkChildren(JSTracer *trc, BaseShape *base)
 {
-    if (base->hasGetterObject())
-        MarkObjectUnbarriered(trc, base->getterObject(), "getter");
-    if (base->hasSetterObject())
-        MarkObjectUnbarriered(trc, base->setterObject(), "setter");
-
+    MarkBaseShapeGetterSetter(trc, base);
     if (base->isOwned())
         MarkBaseShapeUnbarriered(trc, base->baseUnowned(), "base");
 
     if (JSObject *parent = base->getObjectParent())
         MarkObjectUnbarriered(trc, parent, "parent");
 }
 
+/*
+ * This function is used by the cycle collector to trace through the
+ * children of a BaseShape (and its baseUnowned(), if any). The cycle
+ * collector does not directly care about BaseShapes, so only the
+ * getter, setter, and parent are marked. Furthermore, the parent is
+ * marked only if it isn't the same as prevParent, which will be
+ * updated to the current shape's parent.
+ */
+inline void
+MarkCycleCollectorChildren(JSTracer *trc, BaseShape *base, JSObject **prevParent)
+{
+    JS_ASSERT(base);
+
+    MarkBaseShapeGetterSetter(trc, base);
+
+    JSObject *parent = base->getObjectParent();
+    if (parent && parent != *prevParent) {
+        MarkObjectUnbarriered(trc, parent, "parent");
+        *prevParent = parent;
+    }
+
+    // An owned base shape has the same parent, getter and setter as
+    // its baseUnowned().
+#ifdef DEBUG
+    if (base->isOwned()) {
+        UnownedBaseShape *unowned = base->baseUnowned();
+        JS_ASSERT_IF(base->hasGetterObject(), base->getterObject() == unowned->getterObject());
+        JS_ASSERT_IF(base->hasSetterObject(), base->setterObject() == unowned->setterObject());
+        JS_ASSERT(base->getObjectParent() == unowned->getObjectParent());
+    }
+#endif
+}
+
+/*
+ * This function is used by the cycle collector to trace through a
+ * shape. The cycle collector does not care about shapes or base
+ * shapes, so those are not marked. Instead, any shapes or base shapes
+ * that are encountered have their children marked. Stack space is
+ * bounded. If two shapes in a row have the same parent pointer, the
+ * parent pointer will only be marked once.
+ */
+void
+MarkCycleCollectorChildren(JSTracer *trc, const Shape *shape)
+{
+    JSObject *prevParent = NULL;
+    do {
+        MarkCycleCollectorChildren(trc, shape->base(), &prevParent);
+        MarkIdUnbarriered(trc, shape->maybePropid(), "propid");
+        shape = shape->previous();
+    } while (shape);
+}
+
 static void
 ScanTypeObject(GCMarker *gcmarker, types::TypeObject *type)
 {
     if (!type->singleton) {
         unsigned count = type->getPropertyCount();
         for (unsigned i = 0; i < count; i++) {
             types::Property *prop = type->getProperty(i);
             if (prop && JSID_IS_STRING(prop->id))
--- a/js/src/jsgcmark.h
+++ b/js/src/jsgcmark.h
@@ -192,21 +192,21 @@ MarkChildren(JSTracer *trc, const Shape 
 
 void
 MarkChildren(JSTracer *trc, JSScript *script);
 
 void
 MarkChildren(JSTracer *trc, JSXML *xml);
 
 /*
- * Marks all the children of a shape except the parent, which avoids using
- * unbounded stack space. Returns the parent.
+ * Trace through the shape and any shapes it contains to mark
+ * non-shape children.
  */
-const Shape *
-MarkShapeChildrenAcyclic(JSTracer *trc, const Shape *shape);
+void
+MarkCycleCollectorChildren(JSTracer *trc, const Shape *shape);
 
 /*
  * Use function overloading to decide which function should be called based on
  * the type of the object. The static type is used at compile time to link to
  * the corresponding Mark/IsMarked function.
  */
 inline void
 Mark(JSTracer *trc, const js::HeapValue &v, const char *name)
--- a/js/xpconnect/src/nsXPConnect.cpp
+++ b/js/xpconnect/src/nsXPConnect.cpp
@@ -796,19 +796,17 @@ NoteJSChild(JSTracer *trc, void *thing, 
                 tracer->cb.NoteNextEdgeName(buffer);
             } else {
                 tracer->cb.NoteNextEdgeName(static_cast<const char*>(tracer->debugPrintArg));
             }
         }
 #endif
         tracer->cb.NoteScriptChild(nsIProgrammingLanguage::JAVASCRIPT, thing);
     } else if (kind == JSTRACE_SHAPE) {
-        do {
-            thing = JS_TraceShapeChildrenAcyclic(trc, thing);
-        } while (thing);
+        JS_TraceShapeCycleCollectorChildren(trc, thing);
     } else if (kind != JSTRACE_STRING) {
         JS_TraceChildren(trc, thing, kind);
     }
 }
 
 static JSBool
 WrapperIsNotMainThreadOnly(XPCWrappedNative *wrapper)
 {