601046 - "Assertion failure: t->freelist < slotSpan"

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jesse Ruderman]

var f = function(){};
for (var p in f);
Object.defineProperty(f, "j", ({configurable: true, value: "a"}));
Object.defineProperty(f, "k", ({configurable: true, value: "b"}));
Object.defineProperty(f, "j", ({configurable: true, get: function() {}}));
delete f.k;
Object.defineProperty(f, "j", ({configurable: false}));

Assertion failure: t->freelist < slotSpan, at jsscope.h:365

Comment 1

[Jesse Ruderman]

The first bad revision is:
changeset:   8deef18e795a
user:        Brendan Eich
date:        Tue Sep 21 00:04:25 2010 -0700
summary:     Fix slot leak that leads to allocSlot assert botch (bug 597945, r=jorendorff).

Comment 2

[David Mandelin [:dmandelin]]

I looked at this a while today and I have some information. It looks to me like the slotSpan computation is wrong here, but I'm not sure about the intent of everything yet.

The assert happens while doing the last defineProperty. Just before that point, f is this:

object 01008118
class 01868350 Function
flags: own_shape inDictionaryMode hasPropertyTable
properties:
    readonly getter shared "j": slot -1
    permanent "caller": slot 7
    permanent "arguments": slot 6
    readonly permanent "name": slot 5
    readonly permanent "arity": slot 4
    readonly permanent "length": slot 3
    permanent "prototype": slot 2
proto <unnamed function at 01003050 (JSFunction at 01003050)>
parent <global object at 01002028>
private 01006DC0
slots:
   0 (reserved) = undefined
   1 (reserved) = undefined
   2 = <Object at 01002168>
   3 = 0
   4 = undefined
   5 = undefined
   6 = undefined
   7 = undefined
   8 = 2.122e-314
   9 = undefined

Note that the last property on f is "j", which has a slot of -1 because it has a getter. It has 10 slots because of its history--it originally had 10 slots from "k" and "j", but "k" got deleted and "j" got converted to a getter. So now it is only using 8 slots but has memory for 10.

In the last defineProperty, we are changing the property for "j". To do this, we create a new dictionary shape. Its parent is a shape that has "caller" as last property, with slot 7, and slotSpan 8. So, to compute the slotSpan, we take the max of the parent's slotSpan, 8; and the lastprop's slot, -1. Thus the max is 8. This seems wrong to me--the object is allocated for 10 slots, and I think slotSpan is supposed to say how much slot memory is allocated.

Right after creating that new shape, we go to set a table on it (with setTable). That table has freeslot 8, and we trip the assert. I haven't found out what a table's freeslot means yet, so I don't know if 8 is the right value here.

Comment 3

[David Mandelin [:dmandelin]]

I understand a bit more now. At least now I know that obj->slotSpan is one more than the largest slot number in use by a property of obj. Based on that, I've found a few things that seem wrong here. I'm not sure exactly which point should be fixed yet.

Breaking down the test case by parts, first we run:

  var f = function(){};
  for (var p in f);
  Object.defineProperty(f, "j", ({configurable: true, value: "a"}));
  Object.defineProperty(f, "k", ({configurable: true, value: "b"}));
  Object.defineProperty(f, "j", ({configurable: true, get: function() {}}));

  "j" is slotless, because it has a getter (but was originally slot 8)
  "k" is slot 9
  f->slotSpan is 10, because slot 9 is highest in use
  f->lastProp->table->freelist is 8, -1 (i.e., 8 is the only slot on freelist)

Continue execution:

  delete f.k;

  "j" is slotless
  [PROBLEM1] f->slotSpan is 10; this is wrong--it should be 8, because 7 is
             now the highest slot in use
  [PROBLEM2] f->lastProp->table->freelist is still 8, -1; this seems wrong as
             well. If slotSpan truly should be 10, then 9 is also free, so it
             should be 8, 9, -1. If slotSpan should be 8, then the freelist
              should now be empty.

Continue:

  Object.defineProperty(f, "j", ({configurable: false}));

  [PROBLEM3] We assert in setTable. At this point, we have come up with a shape
             that has slotSpan 8. This seems right, assuming "j" is still
             slotless. But we are trying to stick the same old table in it,
             with freelist 8, -1. Clearly, the table we put into this shape
             should have an empty freelist.

It seems to me that we start going wrong with PROBLEM1. But maybe not. There is this code in JSObject::removeProperty:

                /*
                 * If the dictionary table's freelist is non-empty, we must
                 * preserve lastProp->slotSpan. We can't reduce slotSpan even
                 * by one or we might lose non-decreasing slotSpan order.
                 */
                if (table->freelist != SHAPE_INVALID_SLOT)
                    lastProp->slotSpan = shape->slotSpan;
 
I haven't figured out what that's for yet. But maybe it is intended to keep slotSpan "too high" at certain points, although other comments about slotSpan seem to say it should be exact.

If PROBLEM1 is in fact a problem, then of course we should already update freelist at the point of PROBLEM2, because freelist (if not empty) must always be less than slotSpan. From that point, we would be fine when we get to the final setTable, because the freelist would be empty, so the invariant can't be violated there.

If PROBLEM1 is the bug, then I'm also still not sure exactly where to fix that. Modifying the code quoted above would be my first guess. I think we would also need new code to update the freelist.

If slotSpan is supposed to be "too high", then PROBLEM2 still seems like a problem, because the freelist should have another element. In addition, there is a bug near PROBLEM3: when we are trying to put that table into the new shape, we should realize that it has a freelist that is now outside slotSpan, which means the freelist is nugatory and we should empty it out at this point.

Comment 4

[David Mandelin [:dmandelin]]

Attachment: Patch, first try

First, a new description of (part of) the problem. Say we have an object using 10 slots, where slot 8 was "j", a property that got changed to a getter (thus now slot -1) and slot 9 is "k". So:

 object/shape:
  slot 8       (free)
  slot 9       "k"

  slotSpan     10
  freelist     [ 8 ]

Now we delete "k". It seems natural to put slotSpan down to 8 and empty the free list. But there is code in JSObject::removeProperty (call it "Q") that prevents slotSpan from decreasing here, with a comment saying it is required to maintain non-decreasing slotSpan order. 

OK, so slotSpan must remain 10. Then, to keep our invariants, we should put slot 9 onto the freelist. This would normally be done at the top of JSObject::removeProperty, inside a call to JSObject::freeSlot. But freeSlot doesn't put the last property onto the freelist, because it expects other code to shrink the object later. And we are in the last-property case here. The problem is that we don't shrink because of Q, which runs later.

It seems like this should be fixable by making JSObject::freeSlot aware of Q, and put the object onto the freelist in that case. But that's kind of annoying, because Q has moderately complicated conditions. Also, making those parts collaborate so closely seems annoying.

It also seems like this should be fixable by making Q fix up the freelist if necessary at that point. It still seems kind of twitchy--I think we'd have to search the freelist (since the slot might already be on there) and put the slot on the freelist if it's not. The searching seems bad.

So, I'm offering the Gordian-knot approach of simply nuking the freelist if it is possible this condition has occurred. This avoids new complexity and also avoids the freelist search. The cost is that we don't get to reuse the old slots anymore--for new properties we'll have to grow the object. I'm assuming this is all pretty rare so it will cost insignificant amounts of memory in practice.

Comment 5

[David Mandelin [:dmandelin]]

Comment on attachment 493849 [details] [diff] [review]
Patch, first try

I think this patch is a little wrong. New one coming soon.

Comment 6

[David Mandelin [:dmandelin]]

Attachment: Patch

Passes try. The two things I question most about this patch:

1. use of const_cast. It's required to do in-place update in changeProperty. There is code in jsdbgapi that gets a const shape from nativeLookup and then passes it to changeProperty, so it kind of seems like the api wants to keep the input to changeProperty const. Maybe that's too sketchy, though.

2. Shape number update stuff at the end of the new path. I did the new changeProperty path based mostly on putProperty, but I kept that end piece. I figured changeProperty knew what it was doing.

Comment 7

[Brendan Eich [:brendan]]

Comment on attachment 494565 [details] [diff] [review]
Patch

Looks good, nits except for one question about shape-number regeneration. The const-ipation was my fault, I will clean up later.

>+/*
>+ * Return true iff the freed slot was added to the dictionary-mode
>+ * freelist.
>+ */
..12345678901234567890123456789012345678901234567890123456789012345678901234567890

Rewrap to fit in 80 columns, and move to jsobj.h where it counts for more? Seems like readers of this short function can tell what the r.v. signals but someone going by the .h file prototypes is left guessing or reading the .cpp too

>+    /*
>+     * Dictionary-mode objects exclusively own their mutable shape
>+     * structs, so we simply modify in place.

Could rewrap here to match other comment margins.

>+        NormalizeGetterAndSetter(cx, this, shape->id, attrs, shape->flags, getter, setter);

Was lack of this a bug? Maybe worth a testcase?

>+        updateShape(cx);

This is otherwise called only when lastProp is being updated. But since you are mutating a shape in a dictionary object, you need to regenerate that shape's shape-number directly. Assuming anything is actually changing, of course (useless changeProperty calls can be penalized, not worth checking).

So I think you want what putProperty does in the mutate-in-place case:

        lastProp->shape = js_GenerateShape(cx, false);
        clearOwnShape();

with a comment citing the putProperty case.

>+                if (table->freelist != SHAPE_INVALID_SLOT) {
>                     lastProp->slotSpan = shape->slotSpan;
>+                     /* Add the slot to the freelist if it wasn't added in freeSlot. */

Nit: extra space before comment, instead make the first space on this line a newline to avoid crunching a comment taking one or more lines after a line not ending in a left brace.

r=me with the shape regen fix and nits picked. Thanks for fixing this one, I owe you.

/be

Comment 8

[David Mandelin [:dmandelin]]

(In reply to comment #7)
> Comment on attachment 494565 [details] [diff] [review]
> r=me with the shape regen fix and nits picked. Thanks for fixing this one, I
> owe you.

Thanks for the clarification on shape renumbering--makes sense now. I removed the call to NormalizeGetterAndSetter: I added that during an early phase of development to fix a test failure, but now it is unnecessary. I also re-added the test case, which accidentally got left out of that version of the patch.

Comment 9

[David Mandelin [:dmandelin]]

Attachment: Patch, as landed

So no one gets confused thinking the previous version landed. (Note: I also added an extra newline before the comment in jsobj.h, which this patch still doesn't show.)

Comment 10

[David Mandelin [:dmandelin]]

http://hg.mozilla.org/tracemonkey/rev/8cd47ad6b71d
http://hg.mozilla.org/tracemonkey/rev/4e41063ec08f (whitespace fix)

Comment 11

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/8cd47ad6b71d

Comment 12

[Brendan Eich [:brendan]]

Cool -- I made a followup comment tweak:

http://hg.mozilla.org/tracemonkey/rev/37acb2ee51b1

Once again the bleeding obvious occurs to me only after I review a patch: why not just have JSObject::changeProperty call putProperty unless !inDictionaryMode() && shape == lastProp? Isolate the mutate-the-shape-in-the-dict to one place.

I'll do this in one of my cleanup shapes followups, or file a targeted bug.

/be

Comment 13

[Christian Holler (:decoder)]

A testcase for this bug was automatically identified at js/src/jit-test/tests/basic/bug601046.js.