Boris Zbarsky [:bzbarsky] Reporter
	Description • 15 years ago

See bug 497788 comment 10 and the testcase linked to there (in the url field of this bug).  

I'll try to minimize the testcase some, but basically the patch for bug 497789 only seems to help until the first gc.  After that we go back to quickly aborting several times in a row on inner tree trying to grow.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 1 • 15 years ago

This looks like the smallest testcase that triggers the problem for me.  The this.x set in DHTMLBall() is key.  The original testcase had a different prop being set, but the set is the important part.

For N < 4, I don't get the inner tree abort.  For N > 97, I see a tree getting blacklisted.  The original testcase here has N == 128, of course.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 2 • 15 years ago

Here's what looks like the relevant part:

leaving trace at /Users/bzbarsky/foopy.js:18@118, op=callprop, lr=0x2731a4, exitType=0, sp=1, calldepth=0, cycles=27575
stack0=object<0x2b79a0:Object> 
global0=object<0x2b7140:Array> global1=int<2> global2=int<3> global3=int<4> 
Abort recording of tree /Users/bzbarsky/foopy.js:16@97 at /Users/bzbarsky/foopy.js:18@118: Inner tree is trying to grow, abort outer recording.

And

    About to try emitting guard code for SideExit=0x2731a4 exitType=0
    shape = ld JSVAL_ERROR_COOKIE[16]
    14
    guard(kshape)(test_property_cache) = eq shape, 14
    xf22: xf guard(kshape)(test_property_cache) -> pc=0x30dbde imacpc=0x0 sp+8 rp+0

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 3 • 15 years ago

Possibly more interesting, when N == 128, I see 4465 branch exits on this guard:

    About to try emitting guard code for SideExit=0x2ee5d0 exitType=0
    shape = ld ld591[16]
    45
    guard(kshape)(test_property_cache) = eq shape, 45
    xf363: xf guard(kshape)(test_property_cache) -> pc=0x30dbdf imacpc=0x0 sp+8 rp+0

and at least some of the aborts on inner tree trying to grow come after that exit.  Other aborts come after exits on:

    About to try emitting guard code for SideExit=0x2ef6bc exitType=0
    shape = ld ld573[16]
    44
    guard(kshape)(test_property_cache) = eq shape, 44
    xf352: xf guard(kshape)(test_property_cache) -> pc=0x30dbdf imacpc=0x0 sp+8 rp+0

    About to try emitting guard code for SideExit=0x2f07a8 exitType=0
    shape = ld ld555[16]
    43
    guard(kshape)(test_property_cache) = eq shape, 43
    xf341: xf guard(kshape)(test_property_cache) -> pc=0x30dbdf imacpc=0x0 sp+8 rp+0

    About to try emitting guard code for SideExit=0x2f2894 exitType=0
    shape = ld ld537[16]
    42
    guard(kshape)(test_property_cache) = eq shape, 42
    xf330: xf guard(kshape)(test_property_cache) -> pc=0x30dbdf imacpc=0x0 sp+8 rp+0

etc.  Those are listed backwards from their order in the log file, for what it's worth.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 4 • 15 years ago

OK, so if I run the testcase until right after I gc and then breakpoint in js_GenerateShape, I see it hit with a stack like so:

#0  js_GenerateShape (cx=0x30bc80) at jsinterp.cpp:94
#1  0x0009c70f in js_MakeScopeShapeUnique (cx=0x30bc80, scope=0x30dd40) at jsscope.h:345
#2  0x0009cb79 in js_FillPropertyCache (cx=0x30bc80, obj=0x2b7160, scopeIndex=0, protoIndex=1, pobj=0x2b7100, sprop=0x8106d0, adding=0) at jsinterp.cpp:238
#3  0x000ad218 in js_GetPropertyHelper (cx=0x30bc80, obj=0x2b7160, id=2856540, cacheResult=1, vp=0xbfffeab8) at ../jsobj.cpp:4328
#4  0x000ad2bb in js_GetMethod (cx=0x30bc80, obj=0x2b7160, id=2856540, cacheResult=1, vp=0xbfffeab8) at ../jsobj.cpp:4350
#5  0x000817d9 in js_Interpret (cx=0x30bc80) at ../jsinterp.cpp:4591

but only once...

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 5 • 15 years ago

And if I breakpoint in js_GenerateShape after setting up the DHTMLBall prototype but before doing anything else, I only see three calls to js_GenerateShape: 2 via FillPropertyCache and one via AddScopeProperty.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 6 • 15 years ago

The AddScopeProperty is the obvious thing: setting .x on the first DHTMLBall I create.

So I guess the question is where all these kshapes are coming from...

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 7 • 15 years ago

OK, I talked to igor about this stuff, and the upshot is that the shape-renumbering we do during GC is just broken.  The relevant code in js_TraceObject is:

5751                 shape = js_RegenerateShapeForGC(cx);
5752                 if (!(sprop->flags & SPROP_MARK)) {
5753                     oldshape = sprop->shape;
5754                     sprop->shape = shape;
5755                     sprop->flags |= SPROP_FLAG_SHAPE_REGEN;
5756                     if (scope->shape != oldshape)
5757                         shape = js_RegenerateShapeForGC(cx);
5758                 }
5759 
5760                 scope->shape = shape;

Now in this testcase we have a bunch of objects all of which have the same shape, but distinct scopes.  All the scopes have the same lastProp, though (since shape is the same).  The scope shape matches lastProp's shape.

When we gc, the first time we enter this function for one of these objects we have !(sprop->flags & SPROP_MARK).  So we reshape the scope's lastProp, set the scope shape to the same shape as the lastProp, and are done.  But we aso mark all the scope props.  So for all the rest of the objects, we don't enter that if block above and just stamp a brand-new shape on the scope.  So after gc every single one of these objects has a different shape, and tracing the loop in the testcase loses.

The obvious fix is to change this to something more like:

                if (scope->hasOwnShape())
                    scope->setShape(js_RegenerateShapeForGC(cx));
                else {
                    if (!(sprop->flags & SPROP_FLAG_SHAPE_REGEN)) {
                        sprop->shape = js_RegenerateShapeForGC(cx);
                        sprop->flags |= SPROP_FLAG_SHAPE_REGEN;
                    }
                    scope->setShape(sprop->shape);
                }

and just rely on js_SweepScopeProperties to reshape sprops for cases when scope has an ownShape.  The hard part is making sure that hasOwnShape() is accurate...

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 8 • 15 years ago

Brendan, Igor, not sure which of you (or both) should be reviewing this.

I've verified that this patch catches all setters; patch that enforces that by making the members private coming up also.

	Brendan Eich [:brendan] Assignee
	Comment 10 • 15 years ago

Comment on attachment 384686 [details] [diff] [review]
Proposed fix

>         js_ExtendScopeShape(cx, scope, sprop);
>-        ++scope->entryCount;
>-        scope->lastProp = sprop;

Commoning these into js_ExtendScopeShape is ok but you should assert in that inline function that sprop->parent == scope->lastProp before updating the latter.

We want js_ExtendScopeShape to be scope->extendShape, but that can be done in a followup patch.

>                     JS_ASSERT(!scope->lastProp ||
>                               scope->shape == scope->lastProp->shape);
>+                    JS_ASSERT(!scope->lastProp || !scope->hasOwnShape());

This code may not pre-date JS_ASSERT_IF, but in any case it should use that macro:

                    JS_ASSERT_IF(scope->lastProp, scope->shape == scope->lastProp->shape);
                    JS_ASSERT_IF(scope->lastProp, !scope->hasOwnShape());

Separate assertions ok, even though predicate is the same; clarify over DEBUG build efficiency.

>             /* Regenerate property cache shape ids if GC'ing. */
>             if (IS_GC_MARKING_TRACER(trc)) {
>-                uint32 shape, oldshape;
>-
>-                shape = js_RegenerateShapeForGC(cx);
>-                if (!(sprop->flags & SPROP_MARK)) {
>-                    oldshape = sprop->shape;
>-                    sprop->shape = shape;
>-                    sprop->flags |= SPROP_FLAG_SHAPE_REGEN;
>-                    if (scope->shape != oldshape)
>-                        shape = js_RegenerateShapeForGC(cx);
>-                }
>-
>-                scope->shape = shape;
>+                if (scope->hasOwnShape())
>+                    scope->shape = js_RegenerateShapeForGC(cx);
>+                else {

Nit: brace all controlled clauses if any of them or the condition of an if or loop control flow construct requires more than one line.

>+                    if (!(sprop->flags & SPROP_FLAG_SHAPE_REGEN)) {
>+                        sprop->shape = js_RegenerateShapeForGC(cx);
>+                        sprop->flags |= SPROP_FLAG_SHAPE_REGEN;
>+                    }
>+                    scope->shape = sprop->shape;
>+                }

Good fix, wish I had not tried to avoid the scope flag originally.

> InitMinimalScope(JSContext *cx, JSScope *scope)
> {
>     JSObject *obj = scope->object;
>     js_LeaveTraceIfGlobalObject(cx, obj);
> 
>-    JSObject *proto = OBJ_GET_PROTO(cx, obj);
>-    scope->shape = (proto && OBJ_IS_NATIVE(proto)) ? OBJ_SHAPE(proto) : 0;
>-
>     scope->hashShift = JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2;
>     scope->entryCount = scope->removedCount = 0;
>     scope->table = NULL;
>-    scope->lastProp = NULL;
>+    JSObject *proto = OBJ_GET_PROTO(cx, obj);
>+    scope->setLastPropAndShape(NULL,
>+                               (proto && OBJ_IS_NATIVE(proto)) ?
>+                                 OBJ_SHAPE(proto) : 0);

Yikes, you have bits of my patch for bug 497789 mixed in here.

>     if (newsprop) {
>         js_LeaveTraceIfGlobalObject(cx, scope->object);
>-        if (scope->shape == sprop->shape)
>-            scope->shape = newsprop->shape;
>-        else
>+
>+        if (scope->shape == sprop->shape) {
>+            scope->setShape(newsprop->shape);
>+        } else
>             js_MakeScopeShapeUnique(cx, scope);

Don't overbrace here.

> /* Scope flags and some macros to hide them from other files than jsscope.c. */
> #define SCOPE_MIDDLE_DELETE             0x0001
> #define SCOPE_SEALED                    0x0002
> #define SCOPE_BRANDED                   0x0004
> #define SCOPE_INDEXED_PROPERTIES        0x0008

Blank line here.

>+/*
>+ * A scope has own shape if its shape is not the same as the shape of its
>+ * lastProp.  This is set if and only if
>+ *
>+ *   !scope->lastProp || scope->shape != scope->lastProp->shape
>+ *
>+ * except during global reshaping.
>+ */
>+#define SCOPE_OWN_SHAPE                 0x0010
> 
> #define SCOPE_HAD_MIDDLE_DELETE(scope)  ((scope)->flags & SCOPE_MIDDLE_DELETE)
> #define SCOPE_SET_MIDDLE_DELETE(scope)  ((scope)->flags |= SCOPE_MIDDLE_DELETE)
> #define SCOPE_CLR_MIDDLE_DELETE(scope)  ((scope)->flags &= ~SCOPE_MIDDLE_DELETE)
> #define SCOPE_HAS_INDEXED_PROPERTIES(scope)  ((scope)->flags & SCOPE_INDEXED_PROPERTIES)
> #define SCOPE_SET_INDEXED_PROPERTIES(scope)  ((scope)->flags |= SCOPE_INDEXED_PROPERTIES)
> 
> #define SCOPE_IS_SEALED(scope)          ((scope)->flags & SCOPE_SEALED)
>@@ -253,18 +285,19 @@ struct JSScope {
> #define SCOPE_SET_BRANDED(scope)        ((scope)->flags |= SCOPE_BRANDED)
> #define SCOPE_CLR_BRANDED(scope)        ((scope)->flags &= ~SCOPE_BRANDED)
> 
> /*
>  * A little information hiding for scope->lastProp, in case it ever becomes
>  * a tagged pointer again.
>  */
> #define SCOPE_LAST_PROP(scope)          ((scope)->lastProp)
>-#define SCOPE_REMOVE_LAST_PROP(scope)   ((scope)->lastProp =                  \
>-                                         (scope)->lastProp->parent)
>+
>+#define SCOPE_REMOVE_LAST_PROP(scope)                   \
>+    (scope)->setLastProp((scope)->lastProp->parent)

Nit: backslash in column 79.

The above really should all go away in a followup patch, though -- inline methods >> macros.

> static inline void
> js_MakeScopeShapeUnique(JSContext *cx, JSScope *scope)
> {
>     js_LeaveTraceIfGlobalObject(cx, scope->object);
>-    scope->shape = js_GenerateShape(cx, JS_FALSE);
>+    scope->setShape(js_GenerateShape(cx, JS_FALSE));
> }

These functions should be scope methods, in a followup.

> static inline void
> js_ExtendScopeShape(JSContext *cx, JSScope *scope, JSScopeProperty *sprop)
> {
>     js_LeaveTraceIfGlobalObject(cx, scope->object);
>-    if (!scope->lastProp ||
>-        scope->shape == scope->lastProp->shape) {
>-        scope->shape = sprop->shape;
>+    uint32 shape;
>+    if (scope->lastProp && scope->hasOwnShape()) {
>+        shape = js_GenerateShape(cx, JS_FALSE);
>     } else {
>-        scope->shape = js_GenerateShape(cx, JS_FALSE);
>+        shape = sprop->shape;
>     }
>+
>+    scope->setLastPropAndShape(sprop, shape);

The assertion I mentioned early in this review wants to go in the lowest-level setLastProp helper, it seems.

>+JSScope::updateOwnShape()
>+{
>+    if (!lastProp || shape != lastProp->shape) {
>+        flags |= SCOPE_OWN_SHAPE;
>+    } else {
>+        flags &= ~SCOPE_OWN_SHAPE;
>+    }

Don't overbrace.

>+}
>+
>+inline JSBool
>+JSScope::hasOwnShape()
>+{
>+    return !!(flags & SCOPE_OWN_SHAPE);
>+}

This should use bool and thereby lose the !!, in the new world C++ order. JSBool is necessary for some ABI reasons, but not AFAIK for inline helpers such as this method.

/be

	Igor Bukanov
	Comment 11 • 15 years ago

(In reply to comment #9)
> Created an attachment (id=384687) [details]
> Make the members private; this should probably be non-branch

I suggest not to worry about it. If necessary, we can add extra #ifdef __cplusplus он 1.9.0 то address liveconnect issues if any.

	Igor Bukanov
	Comment 12 • 15 years ago

(In reply to comment #11)
> (In reply to comment #9)
> > Created an attachment (id=384687) [details] [details]
> > Make the members private; this should probably be non-branch
> 
> I suggest not to worry about it. If necessary, we can add extra #ifdef
> __cplusplus он 1.9.0 то address liveconnect issues if any.

I meant 1.9.1

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 13 • 15 years ago

> We want js_ExtendScopeShape to be scope->extendShape, but that can be done in a
> followup patch.

Yeah.

> Yikes, you have bits of my patch for bug 497789 mixed in here.

Well...  It's earlier in my mq than this one, since without that patch this one isn't needed on bubblemark because we don't trace it anyway.

I can pop that off and merge this one onto a tree without it if we want, but it makes sense to me to land them in this order at least on m-c/t-m.  Not sure about 1.9.1.

> Don't overbrace here.

There used to be more code there.  Will fix.

> The above really should all go away in a followup patch, though

Sure; I was trying to not get too carried away here.

Will address the comments and post the updated patch.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 14 • 15 years ago

> assert in that inline function that sprop->parent == scope->lastProp

That assertion crashes when |sprop| is null and fails when |sprop->parent| is null but scope->lastProp is non-null.  Here's a stack to the latter:

1  0x0010392d in js_ChangeScopePropertyAttrs (cx=0x30bc90, scope=0x30f760, sprop=0x810910, attrs=113, mask=97, getter=0x2b8260, setter=0x2b8240) at ../jsscope.cpp:1439
#2  0x000af235 in js_DefineNativeProperty (cx=0x30bc90, obj=0x2b8220, id=2860644, value=22, getter=0x2b8260, setter=0xdd74 <JS_PropertyStub>, attrs=81, flags=0, shortid=0, propp=0x0, defineHow=0) at ../jsobj.cpp:3683
#3  0x000b0502 in js_DefineProperty (cx=0x30bc90, obj=0x2b8220, id=2860644, value=22, getter=0x2b8260, setter=0xdd74 <JS_PropertyStub>, attrs=81, propp=0x0) at ../jsobj.cpp:3608

That's us setting newsprop as the lastProp of the scope.

I'll condition the assert on both of those things.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 15 • 15 years ago

And in fact, the real issue is that from js_ChangeScopePropertyAttrs we have newsprop->parent == lastProp->parent.  I guess I'll try to assert that.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 16 • 15 years ago

This is still on top of bug 497789; at least for this testcase this patch makes no sense without that one...

	Igor Bukanov
	Comment 17 • 15 years ago

Comment on attachment 384801 [details] [diff] [review]
With review comments addressed, private members folded in

>diff --git a/js/src/jsbuiltins.cpp b/js/src/jsbuiltins.cpp
>--- a/js/src/jsbuiltins.cpp
>+++ b/js/src/jsbuiltins.cpp
>@@ -253,33 +253,31 @@ js_AddProperty(JSContext* cx, JSObject* 
> 
>         js_ExtendScopeShape(cx, scope, sprop);
>-        ++scope->entryCount;
>-        scope->lastProp = sprop;
>diff --git a/js/src/jsinterp.cpp b/js/src/jsinterp.cpp
>--- a/js/src/jsinterp.cpp
>+++ b/js/src/jsinterp.cpp
>@@ -256,18 +256,18 @@ js_FillPropertyCache(JSContext *cx, JSOb
>             SPROP_HAS_STUB_GETTER(sprop) &&
>             SPROP_HAS_VALID_SLOT(sprop, scope)) {
>             /* Great, let's cache sprop's slot and use it on cache hit. */
>             vword = SLOT_TO_PCVAL(sprop->slot);
>         } else {
>             /* Best we can do is to cache sprop (still a nice speedup). */
>             vword = SPROP_TO_PCVAL(sprop);
>             if (adding &&
>-                sprop == scope->lastProp &&
>-                scope->shape == sprop->shape) {
>+                sprop == scope->lastProp() &&
>+                scope->shape() == sprop->shape) {

Nit: for clarity add a utility method like scope->hasShape(sprop) to replace the scope->shape() == sprop->shape check

>@@ -6489,35 +6487,35 @@ js_Interpret(JSContext *cx)
...
>-                    JS_ASSERT(!scope->lastProp ||
>-                              scope->shape == scope->lastProp->shape);
>+                    JS_ASSERT_IF(scope->lastProp(),
>+                                 scope->shape() == scope->lastProp()->shape);
>+                    JS_ASSERT_IF(scope->lastProp(), !scope->hasOwnShape());

Nit: use that hasShape here as well.

>                     if (scope->table) {
>                         JSScopeProperty *sprop2 =
>                             js_AddScopeProperty(cx, scope, sprop->id,
>                                                 sprop->getter, sprop->setter,
>                                                 slot, sprop->attrs,
>                                                 sprop->flags, sprop->shortid);
>                         if (!sprop2) {
>                             js_FreeSlot(cx, obj, slot);
>                             JS_UNLOCK_SCOPE(cx, scope);
>                             goto error;
>                         }
>                         JS_ASSERT(sprop2 == sprop);
>                     } else {
>                         js_LeaveTraceIfGlobalObject(cx, scope->object);
>-                        scope->shape = sprop->shape;
>+                        scope->setLastPropAndShape(sprop, sprop->shape);
>                         ++scope->entryCount;
>-                        scope->lastProp = sprop;
>                     }
> 
>                     GC_WRITE_BARRIER(cx, scope,
>                                      LOCKED_OBJ_GET_SLOT(obj, slot),
>                                      rval);
>                     TRACE_2(SetPropHit, entry, sprop);
>                     LOCKED_OBJ_SET_SLOT(obj, slot, rval);
>                     JS_UNLOCK_SCOPE(cx, scope);

>@@ -151,18 +151,18 @@ CreateScopeTable(JSContext *cx, JSScope 
>     if (!scope->table) {
>         if (report)
>             JS_ReportOutOfMemory(cx);
>         return JS_FALSE;
>     }
>     js_UpdateMallocCounter(cx, JS_BIT(sizeLog2) * sizeof(JSScopeProperty *));
> 
>     scope->hashShift = JS_DHASH_BITS - sizeLog2;
>-    for (sprop = scope->lastProp; sprop; sprop = sprop->parent) {
>-        spp = js_SearchScope(scope, sprop->id, JS_TRUE);
>+    for (sprop = scope->lastProp(); sprop; sprop = sprop->parent) {
>+        spp = scope->searchScope(sprop->id, JS_TRUE);

Nit: replace everywhere in the patch searchScope(JS_TRUE/JS_FALSE) with searchScope(true/false)

>@@ -275,78 +275,78 @@ JS_STATIC_ASSERT(sizeof(jsid) == JS_BYTE
>+JSScope::searchScope(jsid id, JSBool adding)

I think the method should be named just search.

> {
>     JSHashNumber hash0, hash1, hash2;
>-    int hashShift, sizeLog2;
>+    int localHashShift, sizeLog2;
...
>+    localHashShift = hashShift;

Nit: remove localHashShift here and let the compiler to optimize access to this->hashShift as it finds fit.


>     if (newsprop) {
>         js_LeaveTraceIfGlobalObject(cx, scope->object);
>-        if (scope->shape == sprop->shape)
>-            scope->shape = newsprop->shape;
>+
>+        if (scope->shape() == sprop->shape)

Use that scope->hasShape(sprop) here.

>diff --git a/js/src/jsscope.h b/js/src/jsscope.h
>--- a/js/src/jsscope.h
>+++ b/js/src/jsscope.h
>@@ -198,41 +198,82 @@ JS_BEGIN_EXTERN_C
> struct JSScope {
>     JSObjectMap     map;                /* base class state */
> #ifdef JS_THREADSAFE
>     JSTitle         title;              /* lock state */
> #endif
>     JSObject        *object;            /* object that owns this scope */
>     jsrefcount      nrefs;              /* count of all referencing objects */
>     uint32          freeslot;           /* index of next free slot in object */
>-    uint32          shape;              /* property cache shape identifier */
>+private:
>+    uint32          mShape;             /* property cache shape identifier */
>+public:
>     uint8           flags;              /* flags, see below */
>     int8            hashShift;          /* multiplicative hash shift */
>     uint16          spare;              /* reserved */
>     uint32          entryCount;         /* number of entries in table */
>     uint32          removedCount;       /* removed entry sentinels in table */
>     JSScopeProperty **table;            /* table of ptrs to shared tree nodes */
>-    JSScopeProperty *lastProp;          /* pointer to last property added */
>+private:
>+    JSScopeProperty *mLastProp;         /* pointer to last property added */
>+public:
>+
>+    // Give tracer access to mShape
>+    friend class TraceRecorder;
>+
>+    void setShape(uint32 newshape) {
>+        mShape = newshape;
>+        updateOwnShape();
>+    }
>+    uint32 shape() const { assertOwnShape(); return mShape; }
>+    
>+    JSScopeProperty* lastProp() const { assertOwnShape(); return mLastProp; }
>+
>+    /* Not inlined here directly because JSScopeProperty is defined below and
>+       we need to know it has a parent member. */

Nit: follow the defualt style for multiline comments. Also combine this and the following comments into one block.

>+    inline void setLastProp(JSScopeProperty* sprop);
>+    inline void setLastPropAndShape(JSScopeProperty* sprop, uint32 newshape);
>+
>+    /* Not inlined here directly because JSScopeProperty is defined below and
>+       we need to know it has a shape member. */
>+    inline void updateOwnShape();
>+
>+    /* Similar because SCOPE_OWN_SHAPE is defined below. */
>+    inline bool hasOwnShape();
>+
>+    inline void assertOwnShape() const;
>+
>+    JSScopeProperty ** searchScope(jsid id, JSBool adding);
> };
> 
> #define JS_IS_SCOPE_LOCKED(cx, scope)   JS_IS_TITLE_LOCKED(cx, &(scope)->title)
> 
> #define OBJ_SCOPE(obj)                  (JS_ASSERT(OBJ_IS_NATIVE(obj)),       \
>                                          (JSScope *) (obj)->map)
>-#define OBJ_SHAPE(obj)                  (OBJ_SCOPE(obj)->shape)
>+#define OBJ_SHAPE(obj)                  (OBJ_SCOPE(obj)->shape())
> 
> /* By definition, hashShift = JS_DHASH_BITS - log2(capacity). */
> #define SCOPE_CAPACITY(scope)           JS_BIT(JS_DHASH_BITS-(scope)->hashShift)
> 
> /* Scope flags and some macros to hide them from other files than jsscope.c. */
> #define SCOPE_MIDDLE_DELETE             0x0001
> #define SCOPE_SEALED                    0x0002
> #define SCOPE_BRANDED                   0x0004
> #define SCOPE_INDEXED_PROPERTIES        0x0008
> 
>+/*
>+ * A scope has own shape if its shape is not the same as the shape of its
>+ * lastProp.  This is set if and only if

Nit: remove double space here.

>@@ -337,29 +379,32 @@ struct JSScopeProperty {
> 
> #define SPROP_HAS_STUB_GETTER(sprop)    (!(sprop)->getter)
> #define SPROP_HAS_STUB_SETTER(sprop)    (!(sprop)->setter)
> 
> static inline void
> js_MakeScopeShapeUnique(JSContext *cx, JSScope *scope)
> {
>     js_LeaveTraceIfGlobalObject(cx, scope->object);
>-    scope->shape = js_GenerateShape(cx, JS_FALSE);
>+    scope->setShape(js_GenerateShape(cx, JS_FALSE));

s/JS_FALSE/false

> }
> 
> static inline void
> js_ExtendScopeShape(JSContext *cx, JSScope *scope, JSScopeProperty *sprop)
> {
>     js_LeaveTraceIfGlobalObject(cx, scope->object);
>-    if (!scope->lastProp ||
>-        scope->shape == scope->lastProp->shape) {
>-        scope->shape = sprop->shape;
>+    uint32 shape;
>+    if (scope->lastProp() && scope->hasOwnShape()) {
>+        shape = js_GenerateShape(cx, JS_FALSE);
>     } else {

Nit: add an assert that (scope->lastProp() || scope->hasOwnShape()) == (scope->shape() != 0); s/JS_FALSE/false.

>+inline void
>+JSScope::updateOwnShape()
>+{
>+    /* Don't use our accessors here, since they assert the state we're
>+       updating. */

Nit: follow SM style for comments.

r+ with this nits addressed.

	Brendan Eich [:brendan] Assignee
	Comment 18 • 15 years ago

I like Igor's suggestions -- bz, hit me with r? on a revised patch, I will look at it gladly. Thanks,

/be

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 19 • 15 years ago

This comment:

  add an assert that (scope->lastProp() || scope->hasOwnShape()) ==
                     (scope->shape() != 0)

makes no sense to me so I haven't added such an assert.  LHS should always be true there, so it's just asserting shape != 0.  What did you actually want me to assert?

	Igor Bukanov
	Comment 20 • 15 years ago

(In reply to comment #19)
> This comment:
> 
>   add an assert that (scope->lastProp() || scope->hasOwnShape()) ==
>                      (scope->shape() != 0)

I meant 

assert_if(scope->shape() == 0, scope->hasOwnShape());
assert_if(scope->shape() == 0, !scope->lastProp());

But given the patch, the last of these two conditions is not true. With the patch empty scope starts in scope->hasOwnShape() state with shape == 0 and then transition into !scope->hasOwnShape() on the first addition of the property. It seems this is suboptimal. For example, js_ExtendScopeShape with the patch contains:

if (scope->lastProp() && scope->hasOwnShape())
    shape = js_GenerateShape(cx, false);
else
    ...

If hasOwnShape logic would be changed so it will be false for empty scope (which must have 0 shape), then the above condition will be simply:

if (scope->hasOwnShape()
    shape = js_GenerateShape(cx, false);
else
    ...

Here few more nits: the patch should use bool, not JSBool, for the adding argument of searchScope. And IMO 

  scope->search(id, ...) 

reads better than 

  scope->searchScope(id, ...)


Similarly, and again just IMO 

  scope->hasShape(sprop) 

reads better than 

  scope->hasSameShapeAs(sprop) 

For me the latter gives a hint that the shape of the scope and sprop are the same thing.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 21 • 15 years ago

> If hasOwnShape logic would be changed so it will be false for empty scope

That would be a scope with a null lastProp, right?  We could certainly do that, but would need to be more careful in the jsobj.cpp code where we reshape scopes.  Presumably we wouldn't want to reshape empty scopes, right?

> (which must have 0 shape)

Is this always true?  Can't brand an empty scope or some such?  I guess if someone did then js_ExtendScopeShape would clobber that... OK.

> the patch should use bool, not JSBool, for the adding argument of searchScope

OK.  Will do.

>  scope->search(id, ...) 

OK.

To me, hasSameShapeAs() conveys exactly what's being tested, but maybe to someone more familiar with this code hasShape() does a better job of that...  I really don't feel that strongly about it; I'm more interested in not spending as much time as I have been iterating the various sub-patches I'm maintaining for this so we can have a minimal 1.9.1 fix available...  I'll go ahead and make this change too.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 22 • 15 years ago

Brendan suggested I use scope->shapedLike(sprop).  I'll do that.  Will also do the search() thing and address the bool nits, as well as the hashShift nit I missed before.

I still don't quite buy the business with 0 shape.  InitMinimalScope happily sets up scopes with null lastProp and possibly nonzero shapes, as long as scope->object has a non-null proto.  If such scopes can persist, I'm not sure whether they should be reporting hasOwnShape or not, but certainly asserting stuff about shape 0 is a bit weird there, no?

Also, if such scopes do persist, shouldn't gc reshaping leave them shaped like proto's scope?

Or do such scopes not hang around?  That is, do we always set lastProp pretty immediately after InitMinimalScope?

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 23 • 15 years ago

I'm happy to change the behavior here however, if someone can tell me what invariants I can assume to hold.  What's implemented here assumes nothing hidden about JSScope invariants: the scope only claims to be sharing its lastProp's shape if it actually is.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 24 • 15 years ago

Oh, and the assert I was asked to add in comment 10 fails during Firefox startup:

#0  JS_Assert (s=0x419df8 "sprop->parent == mLastProp || sprop->parent == mLastProp->parent", file=0x40e92c "/Users/bzbarsky/mozilla/tracemonkey/mozilla/js/src/jsscope.h", ln=539) at /Users/bzbarsky/mozilla/tracemonkey/mozilla/js/src/jsutil.cpp:69
#1  0x00371202 in JSScope::setLastProp (this=0x14d73a70, sprop=0x12c2850) at jsscope.h:538
#2  0x0036ff58 in js_AddScopeProperty (cx=0x1050c00, scope=0x14d73a70, id=347276596, getter=0x14bcda00, setter=0x14bcdc00, slot=4294967295, attrs=113, flags=0, shortid=0) at /Users/bzbarsky/mozilla/tracemonkey/mozilla/js/src/jsscope.cpp:1249
#3  0x003705bc in js_ChangeScopePropertyAttrs (cx=0x1050c00, scope=0x14d73a70, sprop=0x12c2370, attrs=113, mask=81, getter=0x14bcda00, setter=0x14bcdc00) at /Users/bzbarsky/mozilla/tracemonkey/mozilla/js/src/jsscope.cpp:1446
#4  0x0031bab3 in js_DefineNativeProperty (cx=0x1050c00, obj=0x14bcd780, id=347276596, value=22, getter=0x27b21a <JS_PropertyStub>, setter=0x14bcdc00, attrs=97, flags=0, shortid=0, propp=0x0, defineHow=0) at /Users/bzbarsky/mozilla/tracemonkey/mozilla/js/src/jsobj.cpp:3683
#5  0x0031cf08 in js_DefineProperty (cx=0x1050c00, obj=0x14bcd780, id=347276596, value=22, getter=0x27b21a <JS_PropertyStub>, setter=0x14bcdc00, attrs=97, propp=0x0) at /Users/bzbarsky/mozilla/tracemonkey/mozilla/js/src/jsobj.cpp:3608

I'm going to remove that assert, since it's clearly bogus.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 25 • 15 years ago

And more worryingly, JSScope::assertOwnShape is actually firing the assert sometimes.  I managed to catch it in gdb once: it was during js_TraceObject.  The scope had an mLastProp, neither the scope nor its mLastProp had any flags set, the scope did not have the own-shape flag set, but the shapes of the scope and the sprop differed by 1...

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 26 • 15 years ago

OK, I think I see how that could happen.  If scope->hasOwnShape(), we could generate a new shape for it and set it on the scope...  This _might_ just happen to match the shape sprop already has, and we'll clear the has-own-shape bit.  Then later the sprop gets reshaped from sweep, and we lose.

So I'm changing the jsobj.cpp code to look like this:

                bool hasOwnShape = scope->hasOwnShape();
                if (!(sprop->flags & SPROP_FLAG_SHAPE_REGEN)) {
                    sprop->shape = js_RegenerateShapeForGC(cx);
                    sprop->flags |= SPROP_FLAG_SHAPE_REGEN;
                }
                if (hasOwnShape)
                    scope->setShape(js_RegenerateShapeForGC(cx));
                else
                    scope->setShape(sprop->shape);

	Igor Bukanov
	Comment 28 • 15 years ago

(In reply to comment #23)
> Created an attachment (id=385047) [details]
> With all the nits except the behavior of the lastProp == NULL case addressed
> 
> I'm happy to change the behavior here however, if someone can tell me what
> invariants I can assume to hold.

I suggest to make sure that an empty scope has the zero shape and is in the !hasOwnShape state until the explicit transition to the hasOwnShape state. Also, AFAICS a code would be simpler if the scope would remain hasOwnShape even if all its properties are deleted. That is, the idea is to allow only transitions from !hasOwnShape -> hasOwnShape where the later always has a unique, non-zero shape. The GC should preserve this. 

I also suspect that hasOwnShape and branded can be merged with this schema, but that has to be verified.

	Brendan Eich [:brendan] Assignee
	Comment 29 • 15 years ago

Igor, bz's patch here builds on my patch for bug 497789, which gives only Object.prototype a shape of 0. Other objects inherit initial (no own properties) shape from their prototype, to defeat foreshadowing and enable shape-keyed cache entries for deep (vcap tag > 1) property hits.

Branding a scope makes the GC_WRITE_BARRIER more expensive, so should not be done lightly. Therefore separating the flag for own-shape seems worth doing, although of course BRANDED => OWN_SHAPE.

/be

	Igor Bukanov
	Comment 30 • 15 years ago

(In reply to comment #29)
> Igor, bz's patch here builds on my patch for bug 497789, which gives only
> Object.prototype a shape of 0. 

Right, so the suggestion about 0 is bogus one. But still I do not see why an empty scope should be in hasOwnShape state. It will simplify checks when adding properties for the price of extra work during initialization.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 31 • 15 years ago

So just to be clear... my goal with hasOwnShape was to make sure it exactly matched what the |scope->shape != scope->lastProp->shape| check would have returned before gc started and we started changing shapes in a random order.

Now the check above clearly makes no sense for empty scopes.  And in fact, for empty scopes we do not currently reshape js_TraceObject.  All the reshaping code is conditioned on SCOPE_LAST_PROP returning non-null.

Now that I think about that, this looks incorrect.  If an empty scope inherits proto's shape, then it needs to continue doing that across gc, right?  We need to make that happen somehow.  The obvious way to me is to reorder js_TraceObject to trace the proto before tracing the scope, so we'll know that the proto's shape has been updated by the time we're trying to set our scope's shape.  I assume that JS_CallTracer() won't call back into js_TraceObject if the object had been traced before, so we won't reshape the proto more than once...

_If_ we do the above, I'm pretty happy to change he meaning of hasOwnShape to "during reshaping needs to get its very own shape".  So if lastProp it would return true iff scope->shape != lastProp->shape at start of gc and if !lastProp it would return true iff scope->shape != proto->scope->shape at start of gc.  I don't know enough about how deleting works (e.g. whether on last prop delete we can in fact end up with the proto shape again) to say whether this would give the behavior Igor wants in comment 28 end of first paragraph, but it would at least give a sensible behavior that would allow gc to preserve exactly the situation we had when it started.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 32 • 15 years ago

Oh, and I guess if a scope is at shape 0 at start of gc it needs to stay shape 0?  If so, then we could in fact have hasOwnShape() false for this case, and also make sure to not reshape the scope in js_TraceObject...

	Brendan Eich [:brendan] Assignee
	Comment 33 • 15 years ago

Comment on attachment 385053 [details] [diff] [review]
With those changes

Bit-rotted due to patches landed by jorendorff, and superseded mostly by the patch in bug 488731. Boris, I'm sorry I didn't look here rather than bug 497789 for any lightweight abstractions that you think are important -- but I'm not sure we need the particular ones you added here. Thoughts?

/be

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 34 • 15 years ago

The abstractions we need here are ones that guarantee two things:

1)  If two scopes have the same shape before gc they have the same shape after
    gc.
2)  If two scopes have different shapes before gc they have different shapes
    after gc.

The abstractions I added in this bug basically allowed me to enforce those conditions, under the assumptions that:

a) Scopes without a lastProp never changed shape during gc
b) Any scope that didn't have the same shape as its lastProp had a unique shape
   not shared by any other scope.

Any setup which prevents arbitrary writes to shape and lastProp and makes sure that the "scope should have the same shape as lastProp" bit is set before gc starts renumbering things in all cases where the scope shape matches the lastProp shape will work here.

It looks like neither of the bugs cited in comment 33 makes lastProp or shape private, which is a bit unfortunate.  It also looks like bug 497789 makes shape-evolution happen via a well-defined set of cases (the *ShapeChange functions), which generally seem to make sense.  Those are probably the right abstraction; slightly higher-level than what I did here.

	Boris Zbarsky [:bzbarsky] Reporter
	Comment 35 • 15 years ago

So at first glance, it looks like the patch in bug 488731 fixed this, right?  Brendan?

	Brendan Eich [:brendan] Assignee
	Comment 36 • 15 years ago

Yes, this is fixed. I'll note that directly rather than dup'ing if that's ok.

/be