calling push method on array with maximum length (2^32-1 = 4294967295) causes Spidermonkey to run out of memory

VERIFIED FIXED in mozilla1.9alpha1

Status

()

Core
JavaScript Engine
P2
normal
VERIFIED FIXED
13 years ago
12 years ago

People

(Reporter: Martin Honnen, Assigned: Igor Bukanov)

Tracking

({verified1.8.1})

Trunk
mozilla1.9alpha1
verified1.8.1
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments, 11 obsolete attachments)

2.62 KB, patch
mrbkap
: review+
brendan
: superreview+
Details | Diff | Splinter Review
42.62 KB, patch
mrbkap
: review+
brendan
: superreview+
beltzner
: approval1.8.1+
Details | Diff | Splinter Review
(Reporter)

Description

13 years ago
With the code

var a = new Array(4294967295);
'push yields: ' + a.push('Kibo') + '\r\nlength: ' + a.length + '\r\na[\'4294967295\']: ' + a['4294967295']

Spidermonkey (shell build on Windows XP with all changes pulled via CVS today) runs out of memory.

It it not quite clear what should happen, see the debate in
<http://groups.google.com/group/netscape.public.mozilla.jseng/browse_frm/thread/b5305e1e370c8099/2716412ecc2fd544?tvc=1&hl=en#2716412ecc2fd544>
Opera and MS JScript throw no error and simply give

push yields: 0
length: 0
a['4294967295']: Kibo

Rhino (1.6 R2 shell) throws an error "Inappropriate array length".

Spidermonkey should not run out of memory but set the property with the name '4294967295' to the string 'Kibo' and then either do what Rhino does (throw an error on setting the length to 4294967296) or do what JScript/Opera do (set the length to 0 and return that as the result of the push call), depending on what step
  5. Increase n by 1.
in ECMAScript edition 3 section "15.4.4.7 Array.prototype.push" is meant to do with n being 4294967295.
I think it should throw a RangeError due to step 13 of 15.4.5.1 when it tries to set the length of the array. It does seem funny that you can set the value at that location before you throw the error though, but that is what it seems to say.
Created attachment 207368 [details]
ecma_3/Array/regress-322135

Martin, do you think this test is correct?
Attachment #207368 - Flags: review?(Martin.Honnen)

Comment 3

13 years ago
Hi,

The tricky part is to interpret how should behave the arithmetic operations on the result of To[U]int{16,32} operations.

A strict lecture of the standard gives (at least to me) the impression that arithmetic operations should behave as with any other js number (ie, these numbers are still double). But this seems to break other productions in the standard, as the family of bitwise operations. So I guess that the intent of the standard is for To[U]int{16,32} operations to return an [unsigned] [short] int (ie, most probably, to just do a C cast).

If that is indeed the case, opera and jscript are right and no exception should be raised.

Cheers,
*** Bug 322152 has been marked as a duplicate of this bug. ***

Updated

13 years ago
OS: Windows XP → All
Priority: -- → P2
Hardware: PC → All
Target Milestone: --- → mozilla1.9alpha
From bug 322152 comment 0:

The same length += ...; in push occurs in unshift, splice, and concat.

jsarray.c could really be sped up a lot by using a hybrid native object mapped
approach a la jsxml.c, where the Array class implmeents getObjectOps and
thereby avoids some of the inefficiencies and bug opportunities of the current
code.

/be
MSIE6/Opera 8.51/Firefox trunk winxp
Checking in regress-322135-01.js (push)

MSIE|Opera:
    Expected value 'RangeError', Actual value 'No error'
    Expected value '4294967295', Actual value '0'

Firefox:
    out of memory

Checking in regress-322135-02.js (concat)
MSIE: 
    out of memory

Opera:
    Expected value 'RangeError', Actual value 'No error'
    Type mismatch, expected type undefined, actual type object
    Expected value 'undefined', Actual value ''

Firefox:
    Hang

Checking in regress-322135-03.js (splice)
MSIE:
    Expected value 'RangeError', Actual value 'No error'
    Type mismatch, expected type string, actual type object
    Expected value '4294967295', Actual value '1'

Opera:
    Expected value 'RangeError', Actual value 'No error'
    Type mismatch, expected type string, actual type undefined
    Expected value 'Kibo', Actual value 'undefined'
    Expected value '4294967295', Actual value '0'

Checking in regress-322135-04.js (unshift)
MSIE:
    hang?

Opera:
    Expected value 'RangeError', Actual value 'No error'
    Type mismatch, expected type string, actual type undefined
    Expected value 'Kibo', Actual value 'undefined'
    Expected value '4294967295', Actual value '0'

Firefox:
    Crash (bug 317815?)
Flags: testcase+
Attachment #207368 - Attachment is obsolete: true
Attachment #207368 - Flags: review?(Martin.Honnen)
(In reply to comment #5)
> jsarray.c could really be sped up a lot by using a hybrid native object mapped
> approach a la jsxml.c, where the Array class implmeents getObjectOps and
> thereby avoids some of the inefficiencies and bug opportunities of the current
> code.

See bug 322889.

/be

Updated

12 years ago
Blocks: 334935
(Assignee)

Comment 8

12 years ago
Created attachment 227677 [details] [diff] [review]
Fix for OOM on push

The patch changes set_length hook to iterate over existing properties when removing a large chunk of them. With the patch Array.prototype.push in SM matches MSIE/Opera behavior.
Attachment #227677 - Flags: superreview?(brendan)
Attachment #227677 - Flags: review?(mrbkap)
(Assignee)

Updated

12 years ago
Attachment #227677 - Attachment description: Fix for OEM on push → Fix for OOM on push
(Assignee)

Comment 9

12 years ago
OEM problems with the current code comes from the fact that when indexes exceeds JSVAL_INT_MAX, the code starts to allocate atoms for the indexes. Since such atoms can not be GC-ed due to the last-ditch GC protection, they form a permanent garbage that leads to eventual OOM during those 2^32 loops.

AFAICS a simple reordering of element access in jsarray.c  would made the code safe against collecting of atoms on the last-ditch-gc attempts. Surely such fix would not address the inherent problem of inefficient handling of spare arrays in jsarray.c, but at least OOM would not show any longer and loops would eventually terminate.
Comment on attachment 227677 [details] [diff] [review]
Fix for OOM on push

>-    jsuint newlen, oldlen, slot;
>+    jsuint newlen, oldlen;
>     jsid id2;
>     jsval junk;
>+    JSObject *iter;
>+    jsuint index;

Might combine index decl with newlen and oldlen.  See below for more.

>+            /*
>+             * We are going to remove a lot of indexes in a presumably spare

s/spare/sparse/

>+             * array. So instead of looping through indexes between newlen and
>+             * oldlen we iterate through all properties and remove those that

Add comma after "oldlen" before "we".

>+             * corresponds to indexes from the [newlen, oldlen) range.

"correspond" singular.

>+                if (js_IdIsIndex(id2, &index) &&
>+                    newlen <= index && index < oldlen) {

Could test (index - newlen < oldlen - newlen) and hoist right operand of < via new local variable.

Good fix -- don't mind my picking nits.

/be
(Assignee)

Comment 11

12 years ago
Created attachment 227708 [details] [diff] [review]
Fix for OOM on push v2

Addressing the nits
Attachment #227677 - Attachment is obsolete: true
Attachment #227708 - Flags: superreview?(brendan)
Attachment #227708 - Flags: review?(mrbkap)
Attachment #227677 - Flags: superreview?(brendan)
Attachment #227677 - Flags: review?(mrbkap)
Comment on attachment 227708 [details] [diff] [review]
Fix for OOM on push v2

>+            iter = JS_NewPropertyIterator(cx, obj);
...
>+                    if (!OBJ_DELETE_PROPERTY(cx, obj, id2, &junk))

Hmmm, so iter is a GC thing. What keeps it alive over this OBJ_DELETE_PROPERTY call (which could call into xpconnect, etc.)?
(Assignee)

Comment 13

12 years ago
Created attachment 227716 [details] [diff] [review]
Fix for OOM on push v3

Fix with proper iterator rooting.
Attachment #227708 - Attachment is obsolete: true
Attachment #227716 - Flags: superreview?(brendan)
Attachment #227716 - Flags: review?(mrbkap)
Attachment #227708 - Flags: superreview?(brendan)
Attachment #227708 - Flags: review?(mrbkap)
Attachment #227716 - Flags: review?(mrbkap) → review+
Comment on attachment 227716 [details] [diff] [review]
Fix for OOM on push v3

sr=me, thanks again.

/be
Attachment #227716 - Flags: superreview?(brendan) → superreview+
(Assignee)

Comment 15

12 years ago
I committed the patch from comment 13 to the trunk. I keep the bug open until at least out-of-memory issues are addressed.
(Assignee)

Comment 16

12 years ago
Created attachment 230729 [details] [diff] [review]
Fix for OOM for Array instances

The main idea behind the patch is to skip the atomization of a large index when there is no corresponding atom. That is, for indexes above JSVAL_INT_MAX for objects without resolve hooks or custom getters/setters  we know that the property does not exist if there is no corresponding atom. In the current form the patch checks for the optimization possibility with very conservative ArrayClass check, what would be the right thing to do not to miss the optimization for other objects?
Attachment #230729 - Flags: superreview?(brendan)
Attachment #230729 - Flags: review?(mrbkap)
(Assignee)

Comment 17

12 years ago
Created attachment 230773 [details] [diff] [review]
Fix for OOM for Array instances v2

The previous patch broke array_sort which this version fixes.
Attachment #230729 - Attachment is obsolete: true
Attachment #230773 - Flags: superreview?(brendan)
Attachment #230773 - Flags: review?(mrbkap)
Attachment #230729 - Flags: superreview?(brendan)
Attachment #230729 - Flags: review?(mrbkap)
(In reply to comment #16)
> The main idea behind the patch is to skip the atomization of a large index when
> there is no corresponding atom.

If I set mArray[4294967295] = 'foo' and then have my script and go do other things, triggering enough branch callbacks that it calls JS_GC, will a subsequent toString call show my 'foo'?
(Assignee)

Comment 19

12 years ago
(In reply to comment #18)
> (In reply to comment #16)
> > The main idea behind the patch is to skip the atomization of a large index when
> > there is no corresponding atom.
> 
> If I set mArray[4294967295] = 'foo' and then have my script and go do other
> things, triggering enough branch callbacks that it calls JS_GC, will a
> subsequent toString call show my 'foo'?

After mArray[4294967295] = 'foo' the atom with "4294967295" string is rooted through mArray reference so GC can not collect it. In fact the patch does not change anything for such assignment since the optimization is applied only for get and delete cases. 

In these 2 cases array[largeIndex] does not exist if largeIndex is not atomized so get and delete can be skipped. This works since the array is live and so all its properties and if there is no atom, then there is no such property.

Of cause this only works for standard objetcs and this is the area where the patch can be improved. I.e. instead of checking just for Array JSClass the code can check for JSClass members to see if they are known to allow the optimization. But I am not sure if checking for JSClass.getProperty, JSClass.resolve and JSClass.delProperty is enough.
(In reply to comment #19)
> After mArray[4294967295] = 'foo' the atom with "4294967295" string is rooted
> through mArray reference

Oh, through the property tree! Sorry, I missed that. OK, I'll finish reviewing tomorrow.
Comment on attachment 230773 [details] [diff] [review]
Fix for OOM for Array instances v2

>+     * the array to relive the memory pressure from VM in case of many 

I think you want to "relieve" the memory pressure, though reliving it sounds fun too. :-)

This looks totally awesome.
Attachment #230773 - Flags: review?(mrbkap) → review+
(Assignee)

Comment 22

12 years ago
Created attachment 231987 [details] [diff] [review]
Fix for OOM for Array instances v3

In the previous patch I forgot to initialize hashKey in js_GetExistingStringAtom, this version fixes this.
Attachment #230773 - Attachment is obsolete: true
Attachment #231987 - Flags: superreview?(brendan)
Attachment #231987 - Flags: review?(mrbkap)
Attachment #230773 - Flags: superreview?(brendan)
Attachment #231987 - Flags: review?(mrbkap) → review+
(Assignee)

Comment 23

12 years ago
Ping: I would like the patch to go to FF2 as it should change many Out-Of-Memory denial of service problems to just unstoppable loops, but first it would be nice to get SR on the trunk. 
Reviewing shortly.

/be
Assignee: general → igor.bukanov
Comment on attachment 231987 [details] [diff] [review]
Fix for OOM for Array instances v3

>+#define JS_ARRAY_SIZE(array) (sizeof (array) / sizeof (array)[0])
>+#define JS_ARRAY_END(array) (array + JS_ARRAY_SIZE(array))

Nit: aligh macro definitions.

> static JSBool
>-IndexToId(JSContext *cx, jsuint index, jsid *idp)
>+ConvertBigIndexToId(JSContext *cx, JSObject *obj, jsuint index,
>+                    JSBool createAtom, jsid *idp)

Nit: prevailing style and brevity favor losing the "Convert" verb in the name: BigIndexToId.

>+    JS_STATIC_ASSERT((jsuint)-1 <= 4294967295U);

This seems almost vacuous since jsuint is uint32 (it could be strengthened to use ==).

>+    if (!createAtom && ((clasp = OBJ_GET_CLASS(cx, obj)) == &js_ArrayClass ||
>+                        clasp == &js_ArgumentsClass))
>+    {

Nit: prevailing style and general readability favor breaking after &&, and not underhanging || operands by an arbitrary indentation.  That might make pulling the { up to be on the last line of the condition more visually appealing, to boot.

>-        *idp = ATOM_TO_JSID(atom);
>-
>     }
>+    *idp = ATOM_TO_JSID(atom);
>+
>     return JS_TRUE;
> }

Nit: group the *idp = ...; and the return, with blank line before both, as a single code-paragraph?

>+/*
>+ * If the property at the given index exists, get its value into location
>+ * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
>+ * to JSVAL_VOID. The function assumes that location pointed by vp is properly
>+ * rooted and can be used as GC-protected storage for temporaries.

"This function assumes that the location...."

>+SetOrDeleteArrayElement(JSContext *cx, JSObject *obj, jsuint index,
>+                        JSBool hole, jsval v)
>+{
>+    return (hole)
>+           ? (JS_ASSERT(v == JSVAL_VOID), DeleteArrayElement(cx, obj, index))
>+           : SetArrayElement(cx, obj, index, v);

Nit: hole without parens to left of ? is ok by local style.

But more significant: isn't this really better written as an if/else, or if (hole) {... return DeleteArrayElement(...); } return SetArrayElement(...)?

>-        if (op != TO_SOURCE && (JSVAL_IS_VOID(v) || JSVAL_IS_NULL(v))) {
>+        if (hole || (op != TO_SOURCE &&
>+                     (JSVAL_IS_VOID(v) || JSVAL_IS_NULL(v)))) {

Another case where standard indentation seems less arbitrary about indenting to me -- but the brace is well-placed ;-).

>     /*
>      * Initialize vec as a root. We will clear elements of vec one by
>-     * one while increasing fp->nvars when we know that the property at
>+     * one while increasing tvr.count when we know that the property at
>      * the corresponding index exists and its value must be rooted.
>      *
>      * In this way when sorting a huge mostly sparse array we will not
>      * access the tail of vec corresponding to properties that do not
>      * exist allowing OS to avoiding committing RAM for it. See bug 330812.

Comma after "exist", and could lose "for it" to make room.

>+            /* Broken realloc that can not shrink. */

BSD realloc reportedly can or could do this (size-classifier, it's fast but fragmenty, so it can run out of space for smaller classes).  Perhaps "Broken" is apt but not p.c.

> /*
>+ * Find an existing atom for the given char array.
>+ */
>+extern JSAtom *
>+js_GetExistingStringAtom(JSContext *cx, const jschar *chars, size_t length);

Comment that null return means no such atom, not error.

r+me with nits picked as appropriate.  This is great, looking forward to it going in -- sorry I misplaced the review request.

/be
Attachment #231987 - Flags: superreview?(brendan) → superreview+
(Assignee)

Comment 26

12 years ago
(In reply to comment #25)
> (From update of attachment 231987 [details] [diff] [review] [edit])
> >+#define JS_ARRAY_SIZE(array) (sizeof (array) / sizeof (array)[0])
> >+#define JS_ARRAY_END(array) (array + JS_ARRAY_SIZE(array))
> 
> Nit: aligh macro definitions.

So thiese macros pass the review, perhaps it would better to move them to some header ;)?  

> >+    JS_STATIC_ASSERT((jsuint)-1 <= 4294967295U);
> This seems almost vacuous since jsuint is uint32 (it could be strengthened to
> use ==).

Initial version of the patch for bug 341956 that included such explicit sprintf optimization already had JS_STATIC_ASSERT((jsuint)-1 == 4294967295U), but I was asked to change that to use "<=" for extra compatibility.  

> >+    if (!createAtom && ((clasp = OBJ_GET_CLASS(cx, obj)) == &js_ArrayClass ||
> >+                        clasp == &js_ArgumentsClass))
> >+    {

Is it possible to have a universal class-independent check here? I.e. such optimization should work for any class that does not define custom resolve hook or getProperty method, right?

> But more significant: isn't this really better written as an if/else, or if
> (hole) {... return DeleteArrayElement(...); } return SetArrayElement(...)?

Without SetOrDeleteArrayElement the body for reverse loop would be chnaged from

if (!GetArrayElement(cx, obj, i, &hole, tmproot) ||
    !GetArrayElement(cx, obj, len - i - 1, &hole2, tmproot2) ||
    !SetOrDeleteArrayElement(cx, obj, len - i - 1, hole, *tmproot) ||
    !SetOrDeleteArrayElement(cx, obj, i, hole2, *tmproot2)) {
    return JS_FALSE;
}

to          
 
if (!GetArrayElement(cx, obj, i, &hole, tmproot) ||
    !GetArrayElement(cx, obj, len - i - 1, &hole2, tmproot2) ||
    !(hole 
      ? DeleteArrayElement(cx, obj, len - i - 1)
      : SetArrayElement(cx, obj, len - i - 1, *tmproot)) ||
    !(hole2
      ? DeleteArrayElement(cx, obj, i)
      : SetArrayElement(cx, obj, i, tmproot2))) {
    return JS_FALSE;
}

or even bigger code with more ifs. The version with SetOrDeleteArrayElement looks so much better for me.
(In reply to comment #26)
> (In reply to comment #25)
> > (From update of attachment 231987 [details] [diff] [review] [edit] [edit])
> > >+#define JS_ARRAY_SIZE(array) (sizeof (array) / sizeof (array)[0])
> > >+#define JS_ARRAY_END(array) (array + JS_ARRAY_SIZE(array))
> > 
> > Nit: aligh macro definitions.
> 
> So thiese macros pass the review, perhaps it would better to move them to some
> header ;)?  

Forgot to nit-pick SIZE where I think LENGTH is better.

How about jstypes.h with that name change?

> Initial version of the patch for bug 341956 that included such explicit sprintf
> optimization already had JS_STATIC_ASSERT((jsuint)-1 == 4294967295U), but I was
> asked to change that to use "<=" for extra compatibility.  

Not sure how it helps, since right-hand side is unsigned and we don't support 16-bit Windows any longer.

> > >+    if (!createAtom && ((clasp = OBJ_GET_CLASS(cx, obj)) == &js_ArrayClass ||
> > >+                        clasp == &js_ArgumentsClass))
> > >+    {
> 
> Is it possible to have a universal class-independent check here? I.e. such
> optimization should work for any class that does not define custom resolve hook
> or getProperty method, right?

Something like that.  So far we are using js_IsArrayLike, maybe it can be used here, or a macro it uses?

We need to pin down "array-like" using structural types in ES4/JS2, perhaps via

type ArrayLike = {length: uint};

But that doesn't say enough.

> or even bigger code with more ifs. The version with SetOrDeleteArrayElement
> looks so much better for me.

Oh, sure -- I didn't mean to inline it.  I just was suggesting using if statement instead of ?: in the implementation of that function.

/be
(Assignee)

Comment 28

12 years ago
Created attachment 232695 [details] [diff] [review]
Fix for OOM for Array instances v3

Changes compared with v2:

1. JS_ARRAY_LENGTH and JS_ARRAY_END is moved to jstypes.h
2. Renamed BigIndexToId check for js_ObjectClass as well. Note that the check there has nothing to do with checking for array-like objects. Instead the check is supposed to verify that the object store big index atoms together with elements so an existing element means existing atom.
3. Nits are addressed.
Attachment #231987 - Attachment is obsolete: true
Attachment #232695 - Flags: superreview?(brendan)
Attachment #232695 - Flags: review?(mrbkap)
Comment on attachment 232695 [details] [diff] [review]
Fix for OOM for Array instances v3

>+/***********************************************************************
>+** MACROS:      JS_ARRAY_LENGTH
>+**              JS_ARRAY_END
>+** DESCRIPTION:
>+**      Macros to get number of elements and the pointer to one pass the last

"one past".

>+#define JS_ARRAY_LENGTH(array) (sizeof (array) / sizeof (array)[0])

We should see about using this in other places, maybe an easy followup bug.

Still looks great, sr=me -- mrbkap is recovering from his Vegas trip, I hope he didn't lose too much.

/be
Attachment #232695 - Flags: superreview?(brendan) → superreview+
Comment on attachment 232695 [details] [diff] [review]
Fix for OOM for Array instances v3

>+    if (hole) {
>+           JS_ASSERT(v == JSVAL_VOID);
>+           return DeleteArrayElement(cx, obj, index);

Wacky indentation.

>+**      element of C array.  Use them like this:

Need an article here: "element of a C array". r=mrbkap with those nits fixed.
Attachment #232695 - Flags: review?(mrbkap) → review+
(Assignee)

Comment 31

12 years ago
Created attachment 232773 [details] [diff] [review]
Fix for OOM for Array instances v3b

Patch to commit with whitespace and spelling nits addressed.
Attachment #232695 - Attachment is obsolete: true
Comment on attachment 232773 [details] [diff] [review]
Fix for OOM for Array instances v3b


> /*
>+ * Return an existing atom for the given char array or null if currently the
>+ * char sequence is not atomized.

Nit: "currently" after "is" reads slightly better.

>+/***********************************************************************
>+** MACROS:      JS_ARRAY_LENGTH
>+**              JS_ARRAY_END
>+** DESCRIPTION:
>+**      Macros to get the number of elements and the pointer to one past the
>+**      last element of a C array. Use them like this:
>+**
>+**      char buffer[10];
>+**      ...
>+**
>+**      snprintf(buffer, JS_ARRAY_LENGTH(buffer), ...)
>+**      buf_end = JS_ARRAY_END(buffer)

But C standard stipulates that sizeof(char) == 1, so sizeof suffices in these cases.  Better comment example would use a jschar buffer[], or jsval vec[].

Sorry for late-breaking nits, fix if you can.

/be
(Assignee)

Comment 33

12 years ago
Created attachment 232781 [details] [diff] [review]
Fix for OOM for Array instances v3c

Addressing more whitespace and comments nits
Attachment #232773 - Attachment is obsolete: true
Comment on attachment 232781 [details] [diff] [review]
Fix for OOM for Array instances v3c

Taking liberty of marking review+ and nominating. We will want to land this on the trunk ASAP.  It should bake for a couple of days, and I think it should go into Firefox 2 beta 2 to get maximum exposure.  It's a big win for our testsuite, and it should help with hard case DOS attacks that surface in bugzilla now and then, so are probably in the wild.

/be
Attachment #232781 - Flags: superreview+
Attachment #232781 - Flags: review+
Attachment #232781 - Flags: approval1.8.1?
(Assignee)

Comment 35

12 years ago
I committed to the trunk the patch from comment 33.

I mark this bug as fixed since now the test cases should not cause out-of-memory. Yes, they still take hours to execute and you can not interrupt them, but at least they should not consume all the memory and should eventually finish.
Status: NEW → RESOLVED
Last Resolved: 12 years ago
Resolution: --- → FIXED
Hole preservation is important, and this unblocks bug 334935.  Thanks again,

/be

Comment 37

12 years ago
(In reply to comment #35)
> I committed to the trunk the patch from comment 33.

This turned a bunch of tinderboxen on the Firefox tree orange, and probably a tinderbox on SeaMonkey as well.
I backed this out to fix the tinderbox orange.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Created attachment 232841 [details] [diff] [review]
Fixed patch

This fixes the problems that this patch caused. We almost caught these problems in review, but this ain't horeshoes.
Attachment #232841 - Flags: superreview?(igor.bukanov)
Attachment #232841 - Flags: review+
(Assignee)

Comment 40

12 years ago
Comment on attachment 232841 [details] [diff] [review]
Fixed patch

I should have seen this need to expand local roots!
Attachment #232841 - Flags: superreview?(igor.bukanov) → superreview+
Comment on attachment 232781 [details] [diff] [review]
Fix for OOM for Array instances v3c

Please renominate once this lands properly on trunk.
Attachment #232781 - Flags: approval1.8.1?
Created attachment 233033 [details] [diff] [review]
Even more fixed patch

I ran the last patch through the testsuite before checking it in and found that Array.prototype.unshift was broken, bugzilla's interdiff should show the fix.

I noticed one other problem, however: with this patch, when one of the array functions adds elements to the array, we'll happily overflow the current length and call js_SetLengthProperty with an extremely small length (I believe this has the side-effect of nuking all of the properties). Is this something we want to fix, or is it good enough?
Attachment #232841 - Attachment is obsolete: true
Attachment #233033 - Flags: superreview?(brendan)
Attachment #233033 - Flags: review?(igor.bukanov)
(Assignee)

Comment 43

12 years ago
Comment on attachment 233033 [details] [diff] [review]
Even more fixed patch


My changes to unshift was so broken that simply changin the ewhile part of do-loop was not enough. Here is the right version:

>         /* Slide up the array to make room for argc at the bottom. */
>         if (length > 0) {
>             last = length;
...
>+            vp = argv + argc;   /* local root */
>+            do {
                  --last;  
>+                if (!GetArrayElement(cx, obj, last, &hole, vp) ||
>+                    !SetOrDeleteArrayElement(cx, obj, last + argc, hole, *vp)) {
>                     return JS_FALSE;
>-                if (id == JSID_HOLE) {
>-                    if (!OBJ_DELETE_PROPERTY(cx, obj, id2, &junk))
>-                        return JS_FALSE;
>-                } else {
>-                    if (!OBJ_SET_PROPERTY(cx, obj, id2, vp))
>-                        return JS_FALSE;
>                 }
              } while (last != 0);
>         }
Attachment #233033 - Flags: review?(igor.bukanov) → review-
(Assignee)

Comment 44

12 years ago
Created attachment 233205 [details] [diff] [review]
Fix for OOM for Array instances v6

Patch with the array_unshift fixes.
Attachment #232781 - Attachment is obsolete: true
Attachment #233033 - Attachment is obsolete: true
Attachment #233205 - Flags: superreview?(brendan)
Attachment #233205 - Flags: review?(mrbkap)
Attachment #233033 - Flags: superreview?(brendan)
Comment on attachment 233205 [details] [diff] [review]
Fix for OOM for Array instances v6

Looks good. It might be worth running through the .../Array/... tests in the JS testsuite before landing and verifying again that all of the failures you get are expected.
Attachment #233205 - Flags: review?(mrbkap) → review+
(Assignee)

Comment 46

12 years ago
(In reply to comment #45)
> It might be worth running through the .../Array/... tests in the JS
> testsuite before landing and verifying again that all of the failures you get
> are expected.

With the latest patch there is no regressions against Array tests.

Updated

12 years ago
Attachment #233205 - Flags: superreview?(brendan)
Attachment #233205 - Flags: superreview+
Attachment #233205 - Flags: approval1.8.1?
(Assignee)

Comment 47

12 years ago
I committed the patch from comment 44 to the trunk.
(Assignee)

Updated

12 years ago
Status: REOPENED → RESOLVED
Last Resolved: 12 years ago12 years ago
Resolution: --- → FIXED
Comment on attachment 233205 [details] [diff] [review]
Fix for OOM for Array instances v6

a=drivers for the 181 branch
Attachment #233205 - Flags: approval1.8.1? → approval1.8.1+
(Assignee)

Comment 49

12 years ago
I committed the patch from comment 44 to MOZILLA_1_8_BRANCH.
Keywords: fixed1.8.1
Igor, the tests give

Expected value 'RangeError', Actual value 'No error' 
array length unchanged Expected value '4294967295', Actual value '0' 

is that expected behavior?
more details:

ecma_3/Array/regress-322135-01.js, 1.8,1.9, browser/shell, all platforms,
reason: Array.prototype.push on Array with length 2^32-1: RangeError Expected value 'RangeError', Actual value 'No error' 

reason: Array.prototype.push on Array with length 2^32-1: array length unchanged Expected value '4294967295', Actual value '0' 

ecma_3/Array/regress-322135-02.js, windows/mac(ppc|tel), shell
Array.prototype.concat on Array with length 2^32-1: RangeError FAILED!: Expected value 'RangeError', Actual value 'No error' FAILED!:  FAILED!: Array.prototype.concat on Array with length 2^32-1: concat does not return FAILED!: Type mismatch, expected type undefined, actual type object FAILED!: Expected value 'undefined', Actual value '' FAILED!:

the others timed out after 900 seconds. 
(Assignee)

Comment 52

12 years ago
(In reply to comment #50)
> Igor, the tests give
> 
> Expected value 'RangeError', Actual value 'No error' 
> array length unchanged Expected value '4294967295', Actual value '0' 
> 
> is that expected behavior?
> 

The patch does not change the current behavior regarding length overflow. What it addresses is the problem in the bug title, that is Out-Of-Memory when calling push and other Array methods on sparse arrays. After the patch the memory consumption should remain constant during the tests so Firefox behaves at least on pair with MSIE.

When I run unshift in the shell, it eventually finished, but it took an hour or so.
(In reply to comment #52)

Ok, I will remove those aspects of the tests.
Checking in ecma_3/Array/regress-322135-01.js;
/cvsroot/mozilla/js/tests/ecma_3/Array/regress-322135-01.js,v  <--  regress-322135-01.js
new revision: 1.2; previous revision: 1.1
done
Checking in ecma_3/Array/regress-322135-02.js;
/cvsroot/mozilla/js/tests/ecma_3/Array/regress-322135-02.js,v  <--  regress-322135-02.js
new revision: 1.2; previous revision: 1.1
verified fixed 1.8, 1.9 20060827 windows/mac*/linux
Status: RESOLVED → VERIFIED
Keywords: fixed1.8.1 → verified1.8.1
remove length tests per comment 52
Checking in regress-322135-01.js;
/cvsroot/mozilla/js/tests/ecma_3/Array/regress-322135-01.js,v  <--  regress-322135-01.js
new revision: 1.3; previous revision: 1.2
done
Checking in regress-322135-02.js;
/cvsroot/mozilla/js/tests/ecma_3/Array/regress-322135-02.js,v  <--  regress-322135-02.js
new revision: 1.3; previous revision: 1.2
done
Checking in regress-322135-03.js;
/cvsroot/mozilla/js/tests/ecma_3/Array/regress-322135-03.js,v  <--  regress-322135-03.js
new revision: 1.2; previous revision: 1.1
done
Checking in regress-322135-04.js;
/cvsroot/mozilla/js/tests/ecma_3/Array/regress-322135-04.js,v  <--  regress-322135-04.js
new revision: 1.2; previous revision: 1.1
You need to log in before you can comment on or make changes to this bug.