"Assertion failure: rt->nativeIteratorStates" during GC

VERIFIED FIXED in mozilla1.9beta4

Status

()

Core
JavaScript Engine
P1
major
VERIFIED FIXED
10 years ago
3 years ago

People

(Reporter: Jesse Ruderman, Assigned: Igor Bukanov)

Tracking

(Blocks: 1 bug, {assertion, testcase})

Trunk
mozilla1.9beta4
assertion, testcase
Points:
---
Dependency tree / graph
Bug Flags:
blocking1.9 +
in-testsuite ?
in-litmus -

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(6 attachments, 1 obsolete attachment)

(Reporter)

Description

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

Assertion failure: rt->nativeIteratorStates, at jsobj.c:4231
Flags: blocking1.9?
(Assignee)

Updated

10 years ago
Assignee: general → igor

Updated

10 years ago
Flags: tracking1.9? → blocking1.9?
(Assignee)

Comment 1

10 years ago
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. 
Blocks: 322889
(Assignee)

Comment 2

10 years ago
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
 
(Assignee)

Comment 3

10 years ago
Created attachment 306417 [details] [diff] [review]
v 0.1

Here is a backup of something that compiles. As always, holes bring complexity.
See also bug 419878 -- ilooping as Igor predicted.

/be
Flags: blocking1.9? → blocking1.9+
OS: Mac OS X → All
Priority: -- → P1
Hardware: PC → All
Target Milestone: --- → mozilla1.9beta4
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
(Assignee)

Comment 6

10 years ago
Created attachment 306477 [details]
regression and coverage test for the patch

This is a test case that tries to explore all paths in array_enumerate and freinds.
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?
(Assignee)

Comment 8

10 years ago
(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.
(Assignee)

Comment 9

10 years ago
Created attachment 306520 [details] [diff] [review]
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.
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

10 years ago
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?)
(Assignee)

Comment 12

10 years ago
(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 :(. 

(Assignee)

Comment 13

10 years ago
(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.  
(Assignee)

Updated

10 years ago
Attachment #306520 - Flags: review?(brendan)
(Assignee)

Comment 14

10 years ago
Comment on attachment 306520 [details] [diff] [review]
v1

Asking for a review as the patch has passed both the test suite and mochi tests.
Attachment #306520 - Flags: review?(shaver)

Updated

10 years ago
Duplicate of this bug: 419878
(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 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
Attachment #306520 - Flags: review?(brendan)
Attachment #306520 - Flags: review+
Attachment #306520 - Flags: approval1.9b4?
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
Status: NEW → ASSIGNED
(Assignee)

Comment 19

10 years ago
Created attachment 306692 [details] [diff] [review]
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.
  */
Attachment #306520 - Attachment is obsolete: true
Attachment #306692 - Flags: review+
Attachment #306692 - Flags: approval1.9b4?
Attachment #306520 - Flags: review?(shaver)
Attachment #306520 - Flags: approval1.9b4?
(Assignee)

Updated

10 years ago
Attachment #306692 - Flags: review?(shaver)

Updated

10 years ago
Attachment #306692 - Flags: approval1.9b4? → approval1.9b4+
(Assignee)

Comment 20

10 years ago
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
Status: ASSIGNED → RESOLVED
Last Resolved: 10 years ago
Resolution: --- → FIXED
(Assignee)

Updated

10 years ago
Depends on: 420639
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 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!)
Attachment #306692 - Flags: review?(shaver) → review+

Comment 23

10 years ago
Created attachment 312532 [details]
js1_7/iterable/regress-418737-01.js

Comment 24

10 years ago
Created attachment 312533 [details]
js1_7/iterable/regress-418737-02.js

Comment 25

10 years ago
Created attachment 312534 [details]
js1_7/iterable/regress-418737-03.js

Updated

10 years ago
Flags: in-testsuite+
Flags: in-litmus-

Comment 26

10 years ago
v 1.9.0
Status: RESOLVED → VERIFIED

Comment 27

8 years ago
when this bug is opened, the test should be checked in.
Flags: in-testsuite+ → in-testsuite?
Group: core-security
You need to log in before you can comment on or make changes to this bug.