Closed Bug 592556 Opened 14 years ago Closed 14 years ago

Eliminate JSObject::freeslot via monotonic lastProp->freeslot

Categories

(Core :: JavaScript Engine, defect, P1)

defect

Tracking

()

RESOLVED FIXED
mozilla2.0b7
Tracking Status
blocking2.0 --- final+

People

(Reporter: brendan, Assigned: brendan)

References

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(4 files, 15 obsolete files)

29.71 KB, patch
brendan
: review+
Details | Diff | Splinter Review
13.36 KB, patch
dvander
: review+
Details | Diff | Splinter Review
60.63 KB, patch
brendan
: review+
Details | Diff | Splinter Review
2.77 KB, patch
sayrer
: review+
Details | Diff | Splinter Review
A bit tricky, looks doable. Would help bug 561506 and add-property code in TM.

/be
Attached patch proposed fix (obsolete) — Splinter Review
This wasn't too bad, after I surveyed all uses of freeslot, fixed some bogus ones (via containsSlot usage, or removing a vacuous assertion). The key idea is laid out in the big comment before Shape::setParent in jsscope.h.

Passes shell trace-test and jsreftests, pushing to try after some home-built jstestbrowser and mochitest success.

/be
Attachment #471429 - Flags: review?(jorendorff)
Blocks: 593129
Wanted for bug 561506 still, high priority with me.

/be
Status: NEW → ASSIGNED
Priority: P2 → P1
Attachment #471429 - Attachment is obsolete: true
Attachment #471429 - Flags: review?(jorendorff)
Attached patch proposed fix, fixed (obsolete) — Splinter Review
The assertion that we only ever allocate a slot with undefined as its value is hard to maintain, and it will become harder when we stop initializing slots. I got rid of it. Still testing this change, wanted to solicit comments sooner.

/be
Attachment #471656 - Flags: review?(jorendorff)
Comment on attachment 471656 [details] [diff] [review]
proposed fix, fixed


In jsobj.h, struct JSObject:
>+        NSLOTS_BITS     = 29,

Why 29?

In jsobj.cpp, JSObject::ensureInstanceReservedSlots:
>-    JS_ASSERT(freeslot >= JSSLOT_START(clasp));
>-    JS_ASSERT(freeslot <= JSSLOT_FREE(clasp));

Keep the assertions?

In JSObject::allocSlot:
>-    /* JSObject::growSlots or JSObject::freeSlot should set the free slots to void. */
>-    JS_ASSERT(getSlot(freeslot).isUndefined());
>-    *slotp = freeslot++;
>+    *slotp = slot;

And this one?

In JSObject::freeSlot:
>+         * Freeing the last slotfull property added to this object (there could

Spelling nit: "slotful", I think, like "powerful", "truthful", "peaceful".

>+        if (inDictionaryMode() && lastProp->table) {
>+            JS_ASSERT_IF(lastProp->table->freeslot != SHAPE_INVALID_SLOT,
>+                         lastProp->table->freeslot < slot);
>+
>+            for (Shape *shape = lastProp; shape; shape = shape->parent) {
>+                JS_ASSERT(shape->freeslot <= limit);
>+                JS_ASSERT_IF(shape->slot != SHAPE_INVALID_SLOT, shape->slot <= slot);
>+
>+                shape->freeslot = slot;
>+            }
>+        }

This loop could stop at the first (i.e. last) slotful property other than the
one we're deleting.

In jsscope.h, Shape::setParent:
>+     * If we maintained shape paths such that parent slot was always one less
>+     * than child slot, possibly with an exception for SHAPE_INVALID_SLOT slot
>+     * values where we would use another way of computing freeslot based on the
>+     * PropertyTable (as JSC does), then we would not need to store freeslot in
>+     * Shape (to be precise, in its base struct, JSobjectMap).
>+     *
>+     * But we currently scramble slots along shape paths due to resolve-based
>+     * creation of shapes mapping reserved slots, [...]

Another operation that breaks "parent slot is always one less than child slot"
is property deletion. (And addition, when it uses the freelist.)

>+    void setParent(js::Shape *p) {
>+        if (p)
>+            freeslot = JS_MAX(p->freeslot, slot + 1);
>+        parent = p;
>+    }

Might as well assert that freeslot is in range after this.

In struct Shape:
>-    Shape(jsid id, js::PropertyOp getter, js::PropertyOp setter, uint32 slot,
>-          uintN attrs, uintN flags, intN shortid);
>+    Shape(jsid id, js::PropertyOp getter, js::PropertyOp setter, uint32 slot, uintN attrs,
>+          uintN flags, intN shortid,
>+          uint32 shape = INVALID_SHAPE, uint32 freeslot = SHAPE_INVALID_SLOT);

I think in every case where this constructor is used, the caller then calls
PropertyTree::insertChild or Shape::insertIntoDictionary, both of which call
setParent, which sets freeslot, for nonempty shapes. So I think the freeslot
parameter here can be dropped.

Either way, the default value here doesn't read like good code --
SHAPE_INVALID_SLOT isn't a valid value for freeslot.
(In reply to comment #4)
> Comment on attachment 471656 [details] [diff] [review]
> proposed fix, fixed
> 
> 
> In jsobj.h, struct JSObject:
> >+        NSLOTS_BITS     = 29,
> 
> Why 29?
> 
> In jsobj.cpp, JSObject::ensureInstanceReservedSlots:
> >-    JS_ASSERT(freeslot >= JSSLOT_START(clasp));
> >-    JS_ASSERT(freeslot <= JSSLOT_FREE(clasp));
> 
> Keep the assertions?
> 
> In JSObject::allocSlot:
> >-    /* JSObject::growSlots or JSObject::freeSlot should set the free slots to void. */
> >-    JS_ASSERT(getSlot(freeslot).isUndefined());
> >-    *slotp = freeslot++;
> >+    *slotp = slot;
> 
> And this one?
> 
> In JSObject::freeSlot:
> >+         * Freeing the last slotfull property added to this object (there could
> 
> Spelling nit: "slotful", I think, like "powerful", "truthful", "peaceful".
> 
> >+        if (inDictionaryMode() && lastProp->table) {
> >+            JS_ASSERT_IF(lastProp->table->freeslot != SHAPE_INVALID_SLOT,
> >+                         lastProp->table->freeslot < slot);
> >+
> >+            for (Shape *shape = lastProp; shape; shape = shape->parent) {
> >+                JS_ASSERT(shape->freeslot <= limit);
> >+                JS_ASSERT_IF(shape->slot != SHAPE_INVALID_SLOT, shape->slot <= slot);
> >+
> >+                shape->freeslot = slot;
> >+            }
> >+        }
> 
> This loop could stop at the first (i.e. last) slotful property other than the
> one we're deleting.

Right, good point (as suggested on IRC). My O(n^2) temptation!

> In jsscope.h, Shape::setParent:
> >+     * If we maintained shape paths such that parent slot was always one less
> >+     * than child slot, possibly with an exception for SHAPE_INVALID_SLOT slot
> >+     * values where we would use another way of computing freeslot based on the
> >+     * PropertyTable (as JSC does), then we would not need to store freeslot in
> >+     * Shape (to be precise, in its base struct, JSobjectMap).
> >+     *
> >+     * But we currently scramble slots along shape paths due to resolve-based
> >+     * creation of shapes mapping reserved slots, [...]
> 
> Another operation that breaks "parent slot is always one less than child slot"
> is property deletion. (And addition, when it uses the freelist.)

Right, but deletion always switches the object to dictionary-mode, which gives us the table to enable an exceptional or auxiliary means of computing slotSpan. I will fix the comment wording to advert to this.

> >+    void setParent(js::Shape *p) {
> >+        if (p)
> >+            freeslot = JS_MAX(p->freeslot, slot + 1);
> >+        parent = p;
> >+    }
> 
> Might as well assert that freeslot is in range after this.

Oh, you mean NSLOT_LIMIT? Ok.

> In struct Shape:
> >-    Shape(jsid id, js::PropertyOp getter, js::PropertyOp setter, uint32 slot,
> >-          uintN attrs, uintN flags, intN shortid);
> >+    Shape(jsid id, js::PropertyOp getter, js::PropertyOp setter, uint32 slot, uintN attrs,
> >+          uintN flags, intN shortid,
> >+          uint32 shape = INVALID_SHAPE, uint32 freeslot = SHAPE_INVALID_SLOT);
> 
> I think in every case where this constructor is used, the caller then calls
> PropertyTree::insertChild or Shape::insertIntoDictionary, both of which call
> setParent, which sets freeslot, for nonempty shapes. So I think the freeslot
> parameter here can be dropped.

Yes, it's a holdover. Thanks.

> Either way, the default value here doesn't read like good code --
> SHAPE_INVALID_SLOT isn't a valid value for freeslot.

I had an assert that was not held over, if you get what I mean.

New patch in a few minutes.

/be
Argh, text area resizing without scrolling to top.

(In reply to comment #4)
> In jsobj.h, struct JSObject:
> >+        NSLOTS_BITS     = 29,
> 
> Why 29?

Same as INDEX_TOO_BIG's hardcoded check (jsarray.cpp, pre-patch).

A sane upper bound, no longer required by INT jsval repr but still worth keeping I think. And I want to match the dense array index limit.

> In jsobj.cpp, JSObject::ensureInstanceReservedSlots:
> >-    JS_ASSERT(freeslot >= JSSLOT_START(clasp));
> >-    JS_ASSERT(freeslot <= JSSLOT_FREE(clasp));
> 
> Keep the assertions?

Ok.

> In JSObject::allocSlot:
> >-    /* JSObject::growSlots or JSObject::freeSlot should set the free slots to void. */
> >-    JS_ASSERT(getSlot(freeslot).isUndefined());
> >-    *slotp = freeslot++;
> >+    *slotp = slot;
> 
> And this one?

No, this was the one I said I couldn't keep without adding setUndefined to a bunch of places that remove a shape from its list, en route to adding a new shape (changeProperty, putProperty). It's also going to get harder with the followup fix to "rotate" slot alloc and free out of jsshape.cpp code, so the methods there can be Shape not JSObject methods.

> In JSObject::freeSlot:
> >+         * Freeing the last slotfull property added to this object (there could
> 
> Spelling nit: "slotful", I think, like "powerful", "truthful", "peaceful".

I kept writing "slot-ful" but it looked wrong. Ok, "slotful".

/be
Comment on attachment 471656 [details] [diff] [review]
proposed fix, fixed

In jsscope.cpp, JSObject::ensureClassReservedSlotsForEmptyObject:
>-     * (b) have at least JSSLOT_FREE(this->clasp) >= JS_INITIAL_NSLOTS.
>-     *
>-     * Note that (b) depends on fine-tuning of JS_INITIAL_NSLOTS (3).
>+     * (b) protect their instance-reserved slots with shapes, at least a custom
>+     * empty shape with the right freeslot member.

Nice improvement to this comment.

r=me with the nits picked.
Attachment #471656 - Flags: review?(jorendorff) → review+
(In reply to comment #7)
> Comment on attachment 471656 [details] [diff] [review]
> proposed fix, fixed
> 
> In jsscope.cpp, JSObject::ensureClassReservedSlotsForEmptyObject:
> >-     * (b) have at least JSSLOT_FREE(this->clasp) >= JS_INITIAL_NSLOTS.
> >-     *
> >-     * Note that (b) depends on fine-tuning of JS_INITIAL_NSLOTS (3).
> >+     * (b) protect their instance-reserved slots with shapes, at least a custom
> >+     * empty shape with the right freeslot member.
> 
> Nice improvement to this comment.

D'oh, of course this comment shows that the second assertion you wanted back:

> In jsobj.cpp, JSObject::ensureInstanceReservedSlots:
> >-    JS_ASSERT(freeslot >= JSSLOT_START(clasp));
> >-    JS_ASSERT(freeslot <= JSSLOT_FREE(clasp));
> 
> Keep the assertions?

cannot make a come-back. Callers of ensureInstanceReservedSlots have set map and (when there are actual slots to reserve) always to a shape with higher slot than JSSLOT_FREE(clasp).

/be
(In reply to comment #8)
> > >-    JS_ASSERT(freeslot >= JSSLOT_START(clasp));
> > >-    JS_ASSERT(freeslot <= JSSLOT_FREE(clasp));
> > 
> > Keep the assertions?
> 
> cannot make a come-back. Callers of ensureInstanceReservedSlots have set map
> and (when there are actual slots to reserve) always to a shape with higher slot
> than JSSLOT_FREE(clasp).

So I assert now only that freeslot() >= JSSLOT_FREE(clasp). Turns out Call and Proxy users of JSObject::ensureInstanceReservedSlots call with nreserved = 0.

/be
Attached patch with review comments addressed (obsolete) — Splinter Review
Attachment #471656 - Attachment is obsolete: true
Attachment #472033 - Flags: review+
Note that I kept the uint32 freeslot trailing param to Shape's main constructor, but default it to 0. The call in newDictionaryShape indeed passes child.freeslot and this is important when copying from shape-tree to dictionary-list shapes.

/be
Attached patch revised patch (obsolete) — Splinter Review
I'll try to create an interdiff. Enough changed here to warrant re-review. More in a bit.

/be
Attachment #472033 - Attachment is obsolete: true
Attachment #472034 - Attachment is obsolete: true
Attachment #472694 - Flags: review?(jorendorff)
153a154,175
> @@ -429,19 +429,19 @@ WrapEscapingClosure(JSContext *cx, JSSta
>          /* FIXME should copy JSOP_TRAP? */
>          JSOp op = js_GetOpcode(cx, wscript, pc);
>          const JSCodeSpec *cs = &js_CodeSpec[op];
>          ptrdiff_t oplen = cs->length;
>          if (oplen < 0)
>              oplen = js_GetVariableBytecodeLength(pc);
>  
>          /*
> -         * Rewrite JSOP_{GET,CALL}DSLOT as JSOP_{GET,CALL}UPVAR_DBG for the
> +         * Rewrite JSOP_{GET,CALL}FCSLOT as JSOP_{GET,CALL}UPVAR_DBG for the
>           * case where fun is an escaping flat closure. This works because the
> -         * UPVAR and DSLOT ops by design have the same format: an upvar index
> +         * UPVAR and FCSLOT ops by design have the same format: an upvar index
>           * immediate operand.
>           */
>          switch (op) {
>            case JSOP_GETUPVAR:       *pc = JSOP_GETUPVAR_DBG; break;
>            case JSOP_CALLUPVAR:      *pc = JSOP_CALLUPVAR_DBG; break;
>            case JSOP_GETFCSLOT:      *pc = JSOP_GETUPVAR_DBG; break;
>            case JSOP_CALLFCSLOT:     *pc = JSOP_CALLUPVAR_DBG; break;
>            case JSOP_DEFFUN_FC:      *pc = JSOP_DEFFUN_DBGFC; break;

Ride-along JSOP_*DSLOT -> JSOP_*FCSLOT name fix (followup comment fix to bug 558451).

504c526,529
< @@ -3605,20 +3605,17 @@ JSObject::ensureInstanceReservedSlots(JS
---
> @@ -3602,24 +3602,17 @@ JSObject::shrinkSlots(JSContext *cx, siz
>  bool
>  JSObject::ensureInstanceReservedSlots(JSContext *cx, size_t nreserved)
>  {
510,512c535,537
<      if (nslots > numSlots() && !allocSlots(cx, nslots))
<          return false;
<  
---
> -    if (nslots > numSlots() && !allocSlots(cx, nslots))
> -        return false;
> -
517,518c542,543
< +    JS_ASSERT(freeslot() >= JSSLOT_FREE(clasp));
<      return true;
---
> -    return true;
> +    return nslots <= numSlots() || allocSlots(cx, nslots);

Simplified to one line (plus assertion).

547a574
> +#ifdef DEBUG
548a576,579
> +            uint32 next = getSlot(last).toPrivateUint32();
> +            JS_ASSERT_IF(next != SHAPE_INVALID_SLOT, next < slot);
> +#endif
> +

Without adding the overhead of the forthcoming CHECK_SHAPE_CONSISTENCY code, it
helped to have O(1) slot-freelist sanity checking.

562c593
< -    /* JSObject::growSlots or JSObject::freeSlot should set the free slots to void. */
---
>      /* JSObject::growSlots or JSObject::freeSlot should set the free slots to void. */
565a597
> +    JS_ASSERT(getSlot(slot).isUndefined());

You were right to ask for this back, it is worth keeping. See below.

580c612,628
< +    if (slot + 1 == limit) {
---
> -    } else {
> -        if (inDictionaryMode() && lastProp->table) {
> +    if (inDictionaryMode() && lastProp->table) {
> +        if (slot + 1 < limit) {
> +            /*
> +             * If this object is in dictionary mode, push slot onto the
> +             * property table's freelist.
> +             */
>              uint32 &last = lastProp->table->freeslot;
>  
> -            JS_ASSERT_IF(last != SHAPE_INVALID_SLOT, last < freeslot);
> +            JS_ASSERT_IF(last != SHAPE_INVALID_SLOT, last < freeslot());
>              vref.setPrivateUint32(last);
>              last = slot;
>              return;
>          }
> +
597,599c645,646
< +        if (inDictionaryMode() && lastProp->table) {
< +            JS_ASSERT_IF(lastProp->table->freeslot != SHAPE_INVALID_SLOT,
< +                         lastProp->table->freeslot < slot);
---
> +        JS_ASSERT_IF(lastProp->table->freeslot != SHAPE_INVALID_SLOT,
> +                     lastProp->table->freeslot < slot);
601,607c648,653
< +            for (Shape *shape = lastProp; shape; shape = shape->parent) {
< +                JS_ASSERT(shape->freeslot <= limit);
< +                shape->freeslot = slot;
< +                if (shape->slot != SHAPE_INVALID_SLOT && shape->slot != slot) {
< +                    JS_ASSERT(shape->slot < slot);
< +                    break;
< +                }
---
> +        for (Shape *shape = lastProp; shape; shape = shape->parent) {
> +            JS_ASSERT(shape->freeslot <= limit);
> +            shape->freeslot = slot;
> +            if (shape->slot != SHAPE_INVALID_SLOT && shape->slot != slot) {
> +                JS_ASSERT(shape->slot < slot);
> +                break;
610,623d655
<      } else {
< +        /*
< +         * If this object is in dictionary mode, push slot onto the property
< +         * table's freelist.
< +         */
<          if (inDictionaryMode() && lastProp->table) {
<              uint32 &last = lastProp->table->freeslot;
<  
< -            JS_ASSERT_IF(last != SHAPE_INVALID_SLOT, last < freeslot);
< +            JS_ASSERT_IF(last != SHAPE_INVALID_SLOT, last < freeslot());
<              vref.setPrivateUint32(last);
<              last = slot;
<              return;
<          }

Hard to read, better to see the new diff colorized, but I swapped the outer if
with the inner ifs in the then and else clauses, since the inner ifs tested the
same (inDictionaryMode() && lastProp->table) condition and that's the condition
tested in JSObject::allocSlot at top level. So allocSlot and freeSlot now have
more parallel control structure.

1146c1182,1207
< @@ -839,31 +836,32 @@ JSObject::changeProperty(JSContext *cx, 
---
> @@ -785,16 +782,24 @@ JSObject::putProperty(JSContext *cx, jsi
>              if (!toDictionaryMode(cx))
>                  return NULL;
>              spp = nativeSearch(id);
>              shape = SHAPE_FETCH(spp);
>          }
>          shape->removeFromDictionary(this);
>      }
>  
> +#ifdef DEBUG
> +    if (shape == oldLastProp && shape->hasSlot()) {
> +        JS_ASSERT(shape->slot < shape->freeslot);
> +        JS_ASSERT(lastProp->freeslot <= shape->slot);
> +        getSlotRef(lastProp->freeslot).setUndefined();
> +    }
> +#endif
> +

More O(1) sanity checking without opt-in beyond DEBUG.

>      /*
>       * If we fail later on trying to find or create a new shape, we will
>       * restore *spp from |overwriting|. Note that we don't bother to keep
>       * table->removedCount in sync, because we will fix up both *spp and
>       * table->entryCount shortly.
>       */
>      if (table)
>          SHAPE_STORE_PRESERVING_COLLISION(spp, NULL);
> @@ -839,31 +844,32 @@ JSObject::changeProperty(JSContext *cx, 
1156c1217
< +    /* Allow only shared (slot-less) => unshared (slotful) transition. */
---
> +    /* Allow only shared (slotless) => unshared (slotful) transition. */
1179a1241,1268
> @@ -974,19 +980,25 @@ JSObject::removeProperty(JSContext *cx, 

Here, we are removing a shape from a dictionary.

>  
>          /*
>           * Remove shape from its non-circular doubly linked list, setting this
>           * object's shape first if shape is not lastProp so the updateShape(cx)
>           * after this if-else will generate a fresh shape for this scope.
>           */
>          if (shape != lastProp)
>              setOwnShape(lastProp->shape);
> -        shape->setTable(NULL);
>          shape->removeFromDictionary(this);
> -        lastProp->setTable(table);
> +        if (table) {
> +            if (shape->table == table && table->freeslot != SHAPE_INVALID_SLOT) {
> +                JS_ASSERT(shape->parent == lastProp);
> +                lastProp->freeslot = shape->freeslot;
> +            }
> +            shape->setTable(NULL);
> +            lastProp->setTable(table);
> +        }

First, I test table to avoid useless work for a table-free dictionary-list.

Second, and this is the real fix: if moving table up one parent hop because the
shape being removed is lastProp, and there are slots on table's freelist, then
make sure we do cover any freelist slots by advancing lastProp->freelist (now
that lastProp has been updated) to equal the removed shape's freeslot.

This completes the incrementalization of the O(n^2)-hazardous change you caught
me trying to make in JSObject::freeSlot, where I had a patch that set all the
dict-shape's freeslots to the maximum freeslot. My previous patch did as we
agreed, and stopped iterating up the parent link at the first slotful prop, but
that presumes that the JS code only deletes from the end and either eventually
reaches that prop, and only thereby drops obj->freeslot() to uncover slots that
must no longer be on table's freelist; or never deletes that far.

But what if the shape being removed here has a low slot but a high freeslot?
Then JSObject::freeSlot won't find slot + 1 == limit, so won't preserve, on all
tail shapes up to the previous slotful one, the high freeslot needed to cover
all slots potentially on the table's freelist.

I don't bother testing for a low shape->slot here, to keep the code simpler.
This means it overlaps the case freeSlot does cover, where slot + 1 == limit.
Comments welcome on this overlap.

>      } else {
>          /*
>           * Non-dictionary-mode property tables are shared immutables, so all we
>           * need do is retract lastProp and we'll either get or else lazily make
>           * via a later maybeHash the exact table for the new property lineage.
>           */
>          JS_ASSERT(shape == lastProp);
>          removeLastProperty();
1202c1291,1293
< @@ -355,16 +357,64 @@ struct Shape : public JSObjectMap
---
> @@ -353,17 +355,68 @@ struct Shape : public JSObjectMap
>  
>      inline void removeFromDictionary(JSObject *obj) const;
1209,1210c1300,1305
<      void setTable(js::PropertyTable *t) const { table = t; }
<  
---
> -    void setTable(js::PropertyTable *t) const { table = t; }
> +    void setTable(js::PropertyTable *t) const {
> +        JS_ASSERT_IF(t && t->freeslot != SHAPE_INVALID_SLOT, t->freeslot < freeslot);

More tolerable O(1) sanity assertion, but of course it can miss higher slots
later in the freelist as noted above. I added this first in hopes of catching
the bug, but kept it anyway.

> +        table = t;
> +    }
> +
1258c1353
< +
---
>  
1266,1267c1361
<      }
< @@ -431,18 +481,18 @@ struct Shape : public JSObjectMap
---
> @@ -431,18 +484,18 @@ struct Shape : public JSObjectMap
1288c1382
< @@ -701,17 +751,17 @@ Shape::insertIntoDictionary(js::Shape **
---
> @@ -701,17 +754,17 @@ Shape::insertIntoDictionary(js::Shape **

/be
> make sure we do cover any freelist slots by advancing lastProp->freelist (now

s/lastProp->freelist/lastProp->freeslot/

Better naming prevails over in bug 593256: table->freelist, shape->slotSpan.

/be
(In reply to comment #13)

(re: changes in JSObject::freeSlot)
> Hard to read, better to see the new diff colorized, but I swapped the outer if
> with the inner ifs in the then and else clauses, since the inner ifs tested the
> same (inDictionaryMode() && lastProp->table) condition and that's the condition
> tested in JSObject::allocSlot at top level. So allocSlot and freeSlot now have
> more parallel control structure.

This change looks correct. Comment nit: the If part of "If this object is in dictionary mode, push slot onto the property table's freelist" is redundant with this refactoring.

> [...]
> Second, and this is the real fix: if moving table up one parent hop because the
> shape being removed is lastProp, and there are slots on table's freelist, then
> make sure we do cover any freelist slots by advancing lastProp->freelist (now
> that lastProp has been updated) to equal the removed shape's freeslot.

Wow. I see why this is necessary and the change seems correct. I hope you don't mind a few testing-oriented questions. What does this bug look like? Without this fix, can you hit the assertion in allocSlot() when the bogus freelist entry is consumed? It seems worth checking in such a test.

r=me with that or a suitable excuse ;-)

The more fixes you make, the more treacherous this code seems to me. JSObject now seems to be full of methods that do only part of a job, enforcing some invariants while leaving others broken in various ways, relying on the caller to get the big picture right.
Attachment #472694 - Flags: review?(jorendorff) → review+
(In reply to comment #15)
> > Second, and this is the real fix: if moving table up one parent hop because the
> > shape being removed is lastProp, and there are slots on table's freelist, then
> > make sure we do cover any freelist slots by advancing lastProp->freelist (now
> > that lastProp has been updated) to equal the removed shape's freeslot.
> 
> Wow. I see why this is necessary and the change seems correct. I hope you don't
> mind a few testing-oriented questions. What does this bug look like?

make SOLO_FILE=test_leftpane_corruption_handling.js -C browser/components/places/tests check-one

caught the final problem, fixed by the JSObject::removeProperty code you're referring to here.

> Without
> this fix, can you hit the assertion in allocSlot() when the bogus freelist
> entry is consumed?

Assertion failure: lastProp->table->freelist < slot, at ../../../js/src/jsobj.cpp:3947

> It seems worth checking in such a test.
> 
> r=me with that or a suitable excuse ;-)

I will try to reduce a testcase from the xpcshell-test but it'll take time. Have to keep other balls in the air too.

> The more fixes you make, the more treacherous this code seems to me. JSObject
> now seems to be full of methods that do only part of a job, enforcing some
> invariants while leaving others broken in various ways, relying on the caller
> to get the big picture right.

Not true of JSObject::allocSlot, JSObject::freeSlot, or JSObject::removeProperty (or I am missing something -- please say what if I am), but this is definitely true of the lower-level Shape::insertIntoDictionary, Shape::removeFromDIctionary, JSObject::removeLastProperty, and others. In particular these list-y mutators do not deal with PropertyTable issues, leaving that to their callers.

We talked about this recently (IRC or bug 558451, I forget -- possibly both). I thought I filed a bug on it, but now I can't find it. I made reference to one of the tasks: moving slot allocation and freeing out of otherwise-Shape-methods currently defined in jsscope.cpp, over in in bug 592556 comment 6.

Really, I want AbstractShape, PropertyShape, DictionaryShape, and tail splitting for best branch prediction, instead of the current tail commoning with later forking done in jsscope.cpp. If you remember a bug I filed but lost track of by failing to take assignment, please remind me.

This is important to fix. I wish I had time to do it all in the patch queue for bug 558451, but I'll get to it. Hope you are game for reviewing!

/be
(In reply to comment #16)
> Not true of JSObject::allocSlot, JSObject::freeSlot,

Oops, definitely true of freeSlot with respect to the slotSpan issue! Typed too quickly there.

/be
Aha! I failed to self-assign bug 593129. That is the one in which to plug all the abstraction leaks and seal the varying invariant gaps.

/be
(In reply to comment #13)
> I don't bother testing for a low shape->slot here, to keep the code simpler.
> This means it overlaps the case freeSlot does cover, where slot + 1 == limit.
> Comments welcome on this overlap.

This overlap bugged me so I tested and analyzed the code harder. The farbling done by JSObject::freeSlot of tail shapes' slotSpan (in this patch still misnamed freeslot) members is unnecessary in light of the code in JSObject::removeProperty to propagate the slotSpan of the shape being removed from lastProp.

Recall that Shape::setParent ensures that slotSpan is monotonically increasing from oldest (empty shape) to youngest (obj->lastProp).

The challenge with dictionary-mode objects is to preserve not only order, but also (s < lastProp->slotSpan) for all free slots s on lastProp->table->freelist. (Again I'm using the new names from the second patch for bug 593256).

Since JSObject::slotSpan() is map->slotSpan for all objects, and for native objects map is lastProp, we need only ensure that any slot s put in the freelist is always < lastProp->slotSpan.

Thus except in the case where s is slotSpan - 1, leaving no gap in which free slots could hide, we must copy lastProp->slotSpan up to its parent when removing lastProp. This is what the removeProperty code added in the last patch does (for all s, even where s + 1 == slotSpan; see below).

Therefore I removed the tail-shape-farbling code from JSObject::freeSlot, and thus cleaned up the JSObject::{alloc,free}Slot methods so they only allocate or free a slot, possibly from or to a lastProp dictionary-shape table's freelist. They do not mutate direct shape data members.

Separation of concerns, yay. freeSlot is *a lot* simpler.

As noted above, the removeProperty code is suboptimal, however: it hands off slotSpan from the removed lastProp to its parent, even if the shape removed at lastProp owns the final slot (shape->slot + 1 == shape->slotSpan). Therefore it "leaks" that slot -- the slot won't be on the freelist because freeSlot does not push s where s + 1 == slotSpan.

The leak occurs because we propagate slotSpan instead of letting the new lastProp (parent of the old one that was removed) keep its own slotSpan, which in the case at hand (of the shape being removed having a slot) must be at least one less than the removed shape's slotSpan. I fixed this bug too.

There could be an ALIAS, though. These nasty creatures do not own their slots and they must outlive the non-aliased property that does own the slot. I noticed a pre-existing bug in removeProperty: it will call freeSlot on an alias's slot. So I fixed that bug, as well. (Aliased properties are slated for extinction in bug 576034.)

The good news is that all dictionary-table-only farbling of slotSpan members is isolated to the the one jsscope.cpp JSObject method that calls freeSlot, namely removeProperty. This is one step in the right direction. More to follow soon.

/be
Monotonicity of shape->slotSpan is good. It depends only on setParent monitoring, which depends on insertion happening only at lastProp (can't have a slotful shape inserted between two slotless ones of == slotSpan).

Deletion requires not only monotonic slotSpan but additionally, preservation of lastProp->slotSpan if lastProp->table has a non-empty freelist and removeProperty didn't just free the last slot (note the slightly tighter condition there: the freed slot must not only be one less than its shape's slotSpan -- it must also fill the unit gap between adjacent shapes' slotSpans for it to be safe to let this->slotSpan() decrease).

Getting to a better world here, patch by patch. Help me out with one more review, if you can stand it? Thanks,

/be
Attachment #472694 - Attachment is obsolete: true
Attachment #472924 - Flags: review?(jorendorff)
\o/ Bugzilla interdiff works!

/be
> The leak occurs because we propagate slotSpan instead of letting the new
> lastProp (parent of the old one that was removed) keep its own slotSpan, which
> in the case at hand (of the shape being removed having a slot) must be at least
> one less than the removed shape's slotSpan.

I wrote this while I was writing the code, but ended up asserting only monoticity:

                    JS_ASSERT(shape->slotSpan >= lastProp->slotSpan);

(shape is the old lastProp here, shape->parent == lastProp). Monotonic means what it means and no more. Once we preserve dictionary-mode lastProp->slotSpan to cover freelist-entrained slots, we may have old and new lastProps with the same (covering) slotSpan. So >=, not > as my words cited above implied.

/be
If we can unscramble free slots, we might eliminate slotSpan and use shape->slot, and match the JSC design: shape->slot is monotonic, actually strictly increasing, until it isn't (a transition other than to the next property, whether data or accessor [they use a slot to reference an allocated getter/setter cell]).

As noted before, eliminating slotSpan is not be a space win due to alignment and rounding. There's a complexity trade-off: every transition that would reorder slots requires pinning a property hashmap in JSC. We can let the property table for a given shape come and go as an optimization (although for dictionary-mode objects it must only be on lastProp).

Either way, with monotonic number of slots available in the shape or "structure" of an object, slot storage allocation can be rotated out of the shape code, which is still a near-term goal (bug 593129).

I haven't looked at V8 in too long, should check their hidden class transition machinery -- anyone familiar, please jump in.

/be
And as noted on IRC, our main source of shape->slot scrambling ignoring delete-created dictionary-mode objects is the global object, due to lazy class init, which maps reserved slots on demand in any order.

Andreas a while ago suggested a fast copy-plus-pointer-fixup scheme for init'ing builtins when the global object is created. That looks increasingly in reach, but will need compartment GC love and other work that does not seem required for Fx4, so again: not a good reason to seek to eliminate slotSpan in favor of monotonic-till-you-have-to-pin-a-property-table shape->slot order.

/be
> reach, but will need compartment GC love and other work that does not seem
> required for Fx4

Sorry, confusion: compartmental GC *is* required for Fx4; other work to make eager builtin object/function init performant, probably not so much.

/be
This is on top of the main patch.

[10:15am] brendan: the shapes must cover allocated slots once the freeslot data member of JSObject goes
[10:15am] brendan: for natives
[10:17am] brendan: the native builtins used to violate this and depend on freeslot, but those that could grow expandos after any instance-reserved slots were added needed shape coverage too, hence the Call shape path precompilation, and (more recently) the custom empty shape per bound function with pre-args
[10:17am] jorendorff: ...yes.
[10:17am] brendan: but Block objects, i forgot about
[10:17am] brendan: sure enough, the patch for 592556 seems good except on a jsreftest that manages to gc during compilation
[10:17am] brendan: js_TraceObject sees a block object
[10:18am] brendan: it has shapes but they are JSPROP_SHARED
[10:18am] brendan: so their slotSpans are all 2, as is the emptyBlockShape's
[10:18am] brendan: so it trims dslots
[10:18am] jorendorff: "gc during compilation" *facepalm*
[10:18am] brendan: nice null - 8 deref crash
[10:18am] brendan: it happens, that's why js::Compiler traces stuff
[10:18am] brendan: but tracing isn't enough to stop dslots trimming
[10:18am] brendan: the real bug here is the left-over special case for Block objects
[10:18am] jorendorff: yup

/be
Attachment #473229 - Flags: review?(jorendorff)
Attachment #473229 - Attachment description: fix bug loss of freeslot caused to-do with Block objects → fix bug caused by loss of the JSObject::freeslot data member that bit Block objects
(In reply to comment #20)
> note the slightly tighter condition [here]: the freed slot must not only be one
> less than its shape's slotSpan -- it must also fill the unit gap between
> adjacent shapes' slotSpans for it to be safe to let this->slotSpan() decrease).

The condition in question is in JSObject::removeProperty, shape has just been unlinked from lastProp, and we are trying to decide that shape->slot is the only free slot in between old and new slotSpan, and that it was not put on the table's freelist by JSObject::removeSlot:

                    if (shape->freeslot == lastProp->freeslot + 1)

but this assumes that shape->slot == shape->freeslot - 1, which ain't necessarily so -- shape->slot could be a lot lower, so the table freelist could contain slots >= lastProp->freelist. Some of the mochitests cover this scenario.

We need to strangle the removed shape's slot:

                    if (shape->slot == lastProp->freeslot)

By the Shape::setParent induction, if this condition holds then shape->freeslot is == shape_slot + 1 and freeSlot indeed did not put shape->slot on the table's freelist, and further more, any slots on the freelist are lower than shape->slot and therefore covered by the new lastProp->freelist. Whew!

/be
Attachment #472924 - Attachment is obsolete: true
Attachment #473351 - Flags: review?(jorendorff)
Attachment #472924 - Flags: review?(jorendorff)
This updates the "fix bug caused by loss of the JSObject::freeslot data member that bit Block objects" patch. Should interdiff cleanly.

Luke blessed the change to jsvector.h, found en passant but not needed by the jsobj.cpp change, in the end.

/be
Attachment #473229 - Attachment is obsolete: true
Attachment #473419 - Flags: review?(jorendorff)
Attachment #473229 - Flags: review?(jorendorff)
(In reply to comment #29)
> Created attachment 473419 [details] [diff] [review]
> fix js_XDRBlockObject to preserve parallel slot/shortid order
> 
> This updates the "fix bug caused by loss of the JSObject::freeslot data member
> that bit Block objects" patch. Should interdiff cleanly.

Also fixes final param of many-adic Shape ctor (uint32 typo'ed as uint -- only Windows tryservers seemed to care).

/be
This coupling between removeProperty and freeSlot is my Kryptonite, want to get rid of it but not in this bug's patch set.

/be
Attachment #473351 - Attachment is obsolete: true
Attachment #473577 - Flags: review?(jorendorff)
Attachment #473351 - Flags: review?(jorendorff)
Attachment #473419 - Attachment is obsolete: true
Attachment #473591 - Flags: review?(jorendorff)
Attachment #473419 - Flags: review?(jorendorff)
Why is it OK to update lastProp->slotSpan in JSObject::removeProperty() only if hadSlot is true? I am trying to write a test case for this now.

I get these complaints from MSVC:

d:\dev\reviewmonkey\js\src\jsscope.h(211) : warning C4307: '+' : integral constant overflow

d:\dev\reviewmonkey\js\src\jswrapper.h(108) : warning C4275: non dll-interface class 'JSWrapper' used as base for dll-interface class 'JSCrossCompartmentWrapper'
        d:\dev\reviewmonkey\js\src\jswrapper.h(49) : see declaration of 'JSWrapper'
        d:\dev\reviewmonkey\js\src\jswrapper.h(108) : see declaration of 'JSCrossCompartmentWrapper'

d:\dev\reviewmonkey\js\src\jsscopeinlines.h(149) : error C2511: 'js::Shape::Shape(jsid,js::PropertyOp,js::PropertyOp,uint32,uintN,uintN,intN,uint32,uint32)' : overloaded member function not found in 'js::Shape'
        d:\dev\reviewmonkey\js\src\jsscope.h(289) : see declaration of 'js::Shape'

The last one is an error--the patch doesn't compile. The last parameter is declared uint but defined uint32.
If an object doesn't have a PropertyTable yet, and deletes happen, slots leak.

  var obj = {a: 0, b: 1, c: 2};
  for (var i = 0; i < 20; i++) {
      delete obj.b;
      obj.b = 3;
      delete obj.c;
      obj.c = 4;
  }
  dumpObject(obj);  // shows many unused slots

Creating a table doesn't recover the leaked slots.

(If we care enough to fix this, it would be nice to add an assertion somewhere that would trip if we waste this many slots, then add this code to js/src/tests.)
(In reply to comment #33)
> Why is it OK to update lastProp->slotSpan in JSObject::removeProperty() only
> if hadSlot is true? I am trying to write a test case for this now.

Here it is:

var obj = {a: 0, b: 1, c: 2};
delete obj.b;  // switch to dictionary mode
Object.defineProperty(obj, 'g',
                      {get: function () { return -1; }, configurable: true});
for (var i = 3; i < 20; i++)
    obj['x' + i] = i;  // get property table
for (var i = 3; i < 20; i++)
    delete obj['x' + i]; // add to freelist
delete obj.g;
(In reply to comment #34)
> If an object doesn't have a PropertyTable yet, and deletes happen, slots leak.

This leak is not introduced by the patch; we've always had it. Filed bug 594899.
Attached patch fixed to pass Jason's test (obsolete) — Splinter Review
Thanks, the hadSlot condition came in late, I should have known better. Having a slot does not mean an object's slot span goes down when removing the last shape, and not having a slot does not mean the span does not go down when removing the last shape. I will write this 100x on a blackboard....

/be
Attachment #473577 - Attachment is obsolete: true
Attachment #473688 - Flags: review?(jorendorff)
Attachment #473577 - Flags: review?(jorendorff)
(In reply to comment #33)
> Why is it OK to update lastProp->slotSpan in JSObject::removeProperty() only if
> hadSlot is true? I am trying to write a test case for this now.

Thanks again -- need some help from code-friends to get by, at this point.

> I get these complaints from MSVC:
> 
> d:\dev\reviewmonkey\js\src\jsscope.h(211) : warning C4307: '+' : integral
> constant overflow

I want overflow (wraparound), but I could rewrite it to avoid that warning.

We seem to ignore MSVC warnings too much.

'js::Shape::Shape(jsid,js::PropertyOp,js::PropertyOp,uint32,uintN,uintN,intN,uint32,uint32)'
> : overloaded member function not found in 'js::Shape'
>         d:\dev\reviewmonkey\js\src\jsscope.h(289) : see declaration of
> 'js::Shape'
> 
> The last one is an error--the patch doesn't compile. The last parameter is
> declared uint but defined uint32.

I did fix this, but in the second (Block object) patch. Failed to qpop enough ;-).

/be
Attached patch rebased Block object patch (obsolete) — Splinter Review
Attachment #473591 - Attachment is obsolete: true
Attachment #473692 - Flags: review?(jorendorff)
Attachment #473591 - Flags: review?(jorendorff)
(In reply to comment #33)
> d:\dev\reviewmonkey\js\src\jswrapper.h(108) : warning C4275: non dll-interface
> class 'JSWrapper' used as base for dll-interface class
> 'JSCrossCompartmentWrapper'
>         d:\dev\reviewmonkey\js\src\jswrapper.h(49) : see declaration of
> 'JSWrapper'
>         d:\dev\reviewmonkey\js\src\jswrapper.h(108) : see declaration of
> 'JSCrossCompartmentWrapper'
Bug 589022 is filed for this one already.

(In reply to comment #38)
> We seem to ignore MSVC warnings too much.
Yep, not sure why I bother filing them, honestly.
Attachment #473688 - Flags: review?(jorendorff) → review+
Comment on attachment 473692 [details] [diff] [review]
rebased Block object patch

In js_CloneBlockObject, ensureInstanceReservedSlots seems like a misnomer now,
since the slots we're allocating aren't really "reserved slots". But I can live
with that.

In jsinterp.cpp, CASE(JSOP_ENTERBLOCK):
>     LOAD_OBJECT(0, obj);
>-    JS_ASSERT(!OBJ_IS_CLONED_BLOCK(obj));
>+    JS_ASSERT(!obj->isClonedBlock());

This might as well assert obj->isBlock() too.

>         JSObject *youngestProto = obj2->getProto();
>-        JS_ASSERT(!OBJ_IS_CLONED_BLOCK(youngestProto));
>+        JS_ASSERT(!youngestProto->isClonedBlock());

Same here.

Also in the two corresponding places in stubs::EnterBlock.

In jsparse.cpp, BindLet:
>      * Store pn temporarily in what would be reserved slots in a cloned block
>      * object (once the prototype's final population is known, after all 'let'
>-     * bindings for this block have been parsed). We will free these reserved
>-     * slots in jsemit.cpp:EmitEnterBlock.
>+     * bindings for this block have been parsed).

They're not reserved slots anymore.

Also, the sentence you deleted is still true, right?

r=me.
Attachment #473692 - Flags: review?(jorendorff) → review+
(In reply to comment #41)
> Comment on attachment 473692 [details] [diff] [review]
> rebased Block object patch
> 
> In js_CloneBlockObject, ensureInstanceReservedSlots seems like a misnomer now,
> since the slots we're allocating aren't really "reserved slots". But I can live
> with that.

What's a better term to distinguish these from class-fixed reserved slots?

> In jsinterp.cpp, CASE(JSOP_ENTERBLOCK):
> >     LOAD_OBJECT(0, obj);
> >-    JS_ASSERT(!OBJ_IS_CLONED_BLOCK(obj));
> >+    JS_ASSERT(!obj->isClonedBlock());
> 
> This might as well assert obj->isBlock() too.
> 
> >         JSObject *youngestProto = obj2->getProto();
> >-        JS_ASSERT(!OBJ_IS_CLONED_BLOCK(youngestProto));
> >+        JS_ASSERT(!youngestProto->isClonedBlock());
> 
> Same here.
> 
> Also in the two corresponding places in stubs::EnterBlock.

Thanks -- I added a JSObject::isStaticBlock (best name I could think of in a hurry) to pair with JSObject::isClonedBlock.
> 
> In jsparse.cpp, BindLet:
> >      * Store pn temporarily in what would be reserved slots in a cloned block
> >      * object (once the prototype's final population is known, after all 'let'
> >-     * bindings for this block have been parsed). We will free these reserved
> >-     * slots in jsemit.cpp:EmitEnterBlock.
> >+     * bindings for this block have been parsed).
> 
> They're not reserved slots anymore.

Good point. I revised the comments. Also, to reduce coupling and duplication, I changed JSObject::defineBlockVariable to return const Shape * so that this one call-site can use shape->slot instead of JSCLASS_FREE(&js_BlockClass) + n as the parameter to blockObj->setSlot(..., PrivateValue(pn)).

> Also, the sentence you deleted is still true, right?

Oops, didn't mean to delete that -- restored. Thanks!

/be
Attachment #473692 - Attachment is obsolete: true
Attachment #473866 - Flags: review+
This is on top of the first patch ("fixed to pass Jason's test").

/be
Attachment #473891 - Flags: review?(dvander)
Attachment #473891 - Flags: review?(dvander) → review+
With crucial fix to SetPropCompiler::generateStub to update obj->flags to include METHOD_BARRIER when adding a property and shape->isMethod().

/be
Attachment #473891 - Attachment is obsolete: true
Attachment #473965 - Flags: review?(dvander)
Attachment #473965 - Flags: review?(dvander) → review+
Have to load and bitwise-or flags, can't impute them as an immediate based on shape (this matters for more than DELEGATE -- METHOD_BARRIER can and should be set without reshaping -- load/or/store beats a joined method function-object clone so it's all still good).

/be
Attachment #473965 - Attachment is obsolete: true
Attachment #474093 - Flags: review?(dvander)
"nuke flagsAndFreeslot, flagsOffset and their methodjit codegen, v3" also fixes an overflow warning in methodjit/PolyIC.cpp (use ptrdiff_t cast of sizeof(Value) before applying unary minus), plus some formatting nit-picks for multiline exprs.

/be
Attachment #474093 - Flags: review?(dvander) → review+
Why was JSObject::removeProperty still trying to reduce the lastProp->freeslot below the previous (removed) lastProp->freeslot? Monotonicity!

/be
Attachment #474383 - Flags: review+
Attachment #473688 - Attachment is obsolete: true
http://hg.mozilla.org/tracemonkey/rev/b1facf8ba54e

/be
Whiteboard: fixed-in-tracemonkey
Summary: Eliminate JSObject::freeslot via lastProp->slot (or dictionary entry count) → Eliminate JSObject::freeslot via monotonic lastProp->freeslot
blocking2.0: --- → final+
It looks like this patch caused a big Ts regression. Can we back it out?
I've been up late trying to fix bugs that followed the tm -> m-c merge, not caused by this patch. How about a little shark or equivalent help in return before a back-out?

/be
This is trivial refactoring, duplicates a loop to specialize away if-encode and if-decode clauses in its body, and more important, to create the vector needed to reverse block shape path only when encoding.

/be
Attachment #474532 - Flags: review?(sayrer)
"Can we back it out" was said on IRC about all of tm landing on m-c...

This bugs patches are hard to back out with the followup google maps fixes. If the patch I just attached doesn't help, profiling before stabbing at possible causes will be required. The patch should probably go in anyway, since the code size savings isn't worth the cost to decoding block objects (and our XUL JS does use let).

I'm going to run out of time soon but I may land this patch on tm to optimize for the possibility that it fixes the Ts problem.

/be
Rob, what link do I follow to see the Ts regression? I don't see one via

http://graphs.mozilla.org/graph.html#tests=[[16,4,443]]

If the js_XDRBlockObject followup does fix Ts, please land it on m-c. Really afk now and most of today.

/be
Attachment #474532 - Flags: review?(sayrer) → review+
I think Brendan fixed this startup regression with attachment 474532 [details] [diff] [review]. Nice.
http://hg.mozilla.org/mozilla-central/rev/f7c46270db80

Previously:

http://hg.mozilla.org/mozilla-central/rev/b1facf8ba54e (qfold'ed all-in-one patch)

/be
Status: ASSIGNED → RESOLVED
Closed: 14 years ago
Resolution: --- → FIXED
Blocks: 595693
Depends on: 596805
Depends on: 596873
You need to log in before you can comment on or make changes to this bug.