418737 - "Assertion failure: rt->nativeIteratorStates" during GC

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Jesse Ruderman]

a = [1];
Iterator(a);
a.b = 3;
gc();

Assertion failure: rt->nativeIteratorStates, at jsobj.c:4231

Comment 1

[Igor Bukanov]

This is a regression from bug 322889. In the test case Iterator(a) will be created for a fast array. a.b mutates it into a slow mode. Then gc(); collects the iterator. That eventually will call slowarray_enumerate with enum_op set to JSENUMERATE_DESTROY. At this stage *statep still contains the array object. As such the code calls js_Enumerate directly passing an invalid state object to it. 

Comment 2

[Igor Bukanov]

There is another problem with array enumeration methods. The enumerator for objects and slow arrays collects the indexes before the iterator starts. The subsequent mutations of the object does not affect the indexes the iterator operates over. Yet the current code does not follow that and the following will loop infinitely:

var a_fast = [1];
iter = Iterator(a_fast);
iterations = 0;
for (i in iter) {
    a_fast.push(0);
    ++iterations;
}

Here a_fast.push() increases the length of the array. Since the current code compares the iteration index with array length, each push prolongs the iteration. So array_enumerate must capture the current length of the array.

Here is a more complete test case of expected behavior:

~/m/ff/mozilla/js/src $ cat ~/m/y.js
var o = {'a': 1};
var iter = Iterator(o);
delete o.b;
var iterations = 0;
for (i in iter)
    ++iterations;
if (iterations != 1)
    throw "Mutations affected the object iterator";

var a_slow = [];
a_slow.a = 1;
iter = Iterator(a_slow);
iterations = 0;
for (i in iter) {
    a_slow.push(0);
    ++iterations;
}
if (iterations != 1)
    throw "Mutations affected the slow array iterator";

a_fast = [1];
iter = Iterator(a_fast);
delete a_fast[0];
iterations = 0;
for (i in iter) {
    a_fast.push(0);
    ++iterations;
}
if (iterations != 1)
    throw "Mutations affected the fast array iterator";

var a_fast = [1];
iter = Iterator(a_fast);
iterations = 0;
for (i in iter) {
    a_fast.push(0);
    ++iterations;
}
if (iterations != 1)
    throw "Mutations affected the fast array iterator";
~/m/ff/mozilla/js/src $ ~/m/ff/mozilla/js/src/Linux_All_DBG.OBJ/js ~/m/y.js
uncaught exception: Mutations affected the fast array iterator
 

Comment 3

[Igor Bukanov]

Attachment: v 0.1

Here is a backup of something that compiles. As always, holes bring complexity.

Comment 4

[Brendan Eich [:brendan]]

See also bug 419878 -- ilooping as Igor predicted.

/be

Comment 5

[Brendan Eich [:brendan]]

Comment on attachment 306417 [details] [diff] [review]
v 0.1

Nits early: JSVAL_BOOLEAN_TO_UINT_PAIR => BOOLEAN_JSVAL_TO_... and vice versa -- BOOLEAN modifies the JSVAL noun.

Let me know when ready for review, shaver too.

/be

Comment 6

[Igor Bukanov]

Attachment: regression and coverage test for the patch

This is a test case that tries to explore all paths in array_enumerate and freinds.

Comment 7

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

I'm not sure why we need to defend against holes being filled during enumeration; if we sample length beforehand, then holes being filled can't lead to an iloop, since in the worst case they degenerate to it having been a fully-dense array beforehand for which we have to visit 0..length-1 times.

So I contend that we should just sample length so that it does not grow unbounded, ensure that we are not exceeding length during enumeration in case it shrinks, and be done?

Comment 8

[Igor Bukanov]

(In reply to comment #7)
> So I contend that we should just sample length so that it does not grow
> unbounded, ensure that we are not exceeding length during enumeration in case
> it shrinks, and be done?

The object and slow array enumerator records existing properties during initialization and iterates over them no matter what happens with the original object/array. In particular, it never includes newly added properties. Without sampling the holes the fast array just can not emulate that since it would not know if a particular element was a hole before iterating. I would not be surprised if there are sites that relies on that. So I suggest to make sure that the fast array enumerator matches *exactly* the slow array semantics.

Comment 9

[Igor Bukanov]

Attachment: v1

This is more-or-less the final version with all things in place. I can not test it with js shell suite as it hangs currently when doing RegExp tests like ./ecma_3/RegExp/regress-307456.js with-or-without the patch. So I will try mochi tests at least.

Comment 10

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Do other browsers have that behaviour?  What about the case in which the prototype gains properties during enumeration?  I would be surprised to see dependence on hole-filling behaviour, personally (and Iintend to make our hole-related behaviour different when fixing the elision-in-literals bug, hopefully for 1.9 still).

I think you should fix the iloop for b4, and then we can decide how closely we need to match historical implementation artifacts here; the latter doesn't block b4, and b4 feedback will help us judge the scale of the need.

Comment 11

[Brian Crowder]

I think this is not a hang.  regress-307456 is one of the slow-n.tests for a reason.  If you run it with JSOPTION_RELIMIT turned on, though, it does return in more managable time (probably also returns quickly with the branch-limit turned on?)

Comment 12

[Igor Bukanov]

(In reply to comment #11)
> regress-307456 is one of the slow-n.tests for a reason.

It turned out I have typed -l slow-n.tests and not -L slow-n.tests when running the tests :(. 

Comment 13

[Igor Bukanov]

(In reply to comment #10)
> I think you should fix the iloop for b4, and then we can decide how closely we
> need to match historical implementation artifacts here;

What ever the resolution of this the last thing I would like to have is semantic differences in behavior between slow and fast arrays. Currently the slow array enumerator ignores additions of any element including the additions that fill holes. As far as I can see it is much more simpler to emulate this behavior in the fast array enumerator then to emulate the proposed fast array behavior in a slow enumerator.  

Comment 14

[Igor Bukanov]

Comment on attachment 306520 [details] [diff] [review]
v1

Asking for a review as the patch has passed both the test suite and mochi tests.

Comment 16

[Brendan Eich [:brendan]]

(In reply to comment #13)
> (In reply to comment #10)
> > I think you should fix the iloop for b4, and then we can decide how closely we
> > need to match historical implementation artifacts here;
> 
> What ever the resolution of this the last thing I would like to have is
> semantic differences in behavior between slow and fast arrays.

I agree with this.

/be

Comment 17

[Brendan Eich [:brendan]]

Comment on attachment 306520 [details] [diff] [review]
v1

>+/*
>+ * JSObjectOps.enumerate implementation.
>+ *
>+ * For a fast array JSENUMERATE_INIT captures in the enumeration state both

Nit: comma after "array".

>+ * the length of the array and the bitmap indicating the positions of holes in
>+ * the array. This ensures that adding or deleting array elements does not
>+ * affect the sequence of indexes JSENUMERATE_NEXT returns.
>+ *
>+ * For a common case of an array without holes to represent the state we pack

Comma after "holes".

>+ * the (nextEnumerationIndex, arrayLength) pair as a pseudo-boolean jsval.
>+ * This is possible when length <= PACKED_UINT_PAIR_BITS. For arrays with
>+ * bigger length or with holes we allocate the JSIndexIterState structure and

Suggest "greater" rather than "bigger", and no need for second "with" (the one before "holes").

>+ * store it as an int-tagged private pointer jsval. For a slow array we
>+ * delegate the enumeration implementation to js_Emumerate in

js_Enumerate misspelled.

>+ * slowarray_enumerate.
>+ *
>+ * Array mutations can turn a fast array into a slow one after the enumeration
>+ * starts. When this happens, slowarray_enumerate receives a state created
>+ * when the array was fast. To distinguish such fast state from a slow state,
>+ * which is an int-tagged pointer that js_Enumerate creates, we set not one
>+ * but two lowest bits when tagging a JSIndexIterState pointer, see

Nit: suggest -- before "see".

>+ * INDEX_ITER_TAG usage below. Thus, when slowarray_enumerate receives a state
>+ * tagged with JSVAL_BOOLEAN or with two lowest bits set, it knows that this
>+ * is a fast state and calls array_enumerate to continue enumerating the

Suggest "so it calls array_enumerate" instead of "and ...".

Rest looks great, thanks for fixing!

/be

Comment 18

[Brendan Eich [:brendan]]

Suggest we get this in ASAP, shaver can r+ before or after but js/src single review rule says this patch is ready for approval by endgame driver.

/be

Comment 19

[Igor Bukanov]

Attachment: v1b

The new version addresses the nits from the comment 17 and removes various trailing spaces from jsarray.c. Here is the nit-fixing changes:

 /*
  * JSObjectOps.enumerate implementation.
  *
- * For a fast array JSENUMERATE_INIT captures in the enumeration state both
+ * For a fast array, JSENUMERATE_INIT captures in the enumeration state both
  * the length of the array and the bitmap indicating the positions of holes in
  * the array. This ensures that adding or deleting array elements does not
  * affect the sequence of indexes JSENUMERATE_NEXT returns.
  *
- * For a common case of an array without holes to represent the state we pack
+ * For a common case of an array without holes, to represent the state we pack
  * the (nextEnumerationIndex, arrayLength) pair as a pseudo-boolean jsval.
  * This is possible when length <= PACKED_UINT_PAIR_BITS. For arrays with
- * bigger length or with holes we allocate the JSIndexIterState structure and
+ * greater length or holes we allocate the JSIndexIterState structure and
  * store it as an int-tagged private pointer jsval. For a slow array we
- * delegate the enumeration implementation to js_Emumerate in
+ * delegate the enumeration implementation to js_Enumerate in
  * slowarray_enumerate.
  *
  * Array mutations can turn a fast array into a slow one after the enumeration
  * starts. When this happens, slowarray_enumerate receives a state created
  * when the array was fast. To distinguish such fast state from a slow state,
  * which is an int-tagged pointer that js_Enumerate creates, we set not one
- * but two lowest bits when tagging a JSIndexIterState pointer, see
+ * but two lowest bits when tagging a JSIndexIterState pointer -- see
  * INDEX_ITER_TAG usage below. Thus, when slowarray_enumerate receives a state
  * tagged with JSVAL_BOOLEAN or with two lowest bits set, it knows that this
- * is a fast state and calls array_enumerate to continue enumerating the
+ * is a fast state so it calls array_enumerate to continue enumerating the
  * indexes present in the original fast array.
  */

Comment 20

[Igor Bukanov]

I checked in the patch from comment 19 to the trunk:

http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&branch=HEAD&cvsroot=%2Fcvsroot&date=explicit&mindate=1204479801&maxdate=1204479940&who=igor%25mir2.org

Comment 21

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Just remembered that I wanted to ask something about this:

Would it be faster to check for holes by comparing COUNT to LENGTH-1?

Comment 22

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Comment on attachment 306692 [details] [diff] [review]
v1b

r=shaver here; I wanted to see us compare COUNT and DENSE_LENGTH to see if we had holes, but the chunked allocation of DENSE_LENGTH makes that hard.  Could do with LENGTH, perhaps, but we can do that later.  (After we audit COUNT setting in some other cases!)

Comment 23

[Bob Clary [:bc] (inactive)]

Attachment: js1_7/iterable/regress-418737-01.js

Comment 24

[Bob Clary [:bc] (inactive)]

Attachment: js1_7/iterable/regress-418737-02.js

Comment 25

[Bob Clary [:bc] (inactive)]

Attachment: js1_7/iterable/regress-418737-03.js

Comment 26

[Bob Clary [:bc] (inactive)]

v 1.9.0

Comment 27

[Bob Clary [:bc] (inactive)]

when this bug is opened, the test should be checked in.