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.

Martin, do you think this test is correct?

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. ***

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?)

(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

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.

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

Addressing the nits

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.)?

Fix with proper iterator rooting.

Comment on attachment 227716 [details] [diff] [review] Fix for OOM on push v3 sr=me, thanks again. /be

I committed the patch from comment 13 to the trunk. I keep the bug open until at least out-of-memory issues are addressed.

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?

The previous patch broke array_sort which this version fixes.

(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'?

(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.

In the previous patch I forgot to initialize hashKey in js_GetExistingStringAtom, this version fixes this.

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

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

(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

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.

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

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.

Patch to commit with whitespace and spelling nits addressed.

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

Addressing more whitespace and comments nits

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

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.

Hole preservation is important, and this unblocks bug 334935. Thanks again, /be

(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.

This fixes the problems that this patch caused. We almost caught these problems in review, but this ain't horeshoes.

Comment on attachment 232841 [details] [diff] [review] Fixed patch I should have seen this need to expand local roots!

Comment on attachment 232781 [details] [diff] [review] Fix for OOM for Array instances v3c Please renominate once this lands properly on trunk.

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?

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); > }

Patch with the array_unshift fixes.

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.

(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.

I committed the patch from comment 44 to the trunk.

Comment on attachment 233205 [details] [diff] [review] Fix for OOM for Array instances v6 a=drivers for the 181 branch

I committed the patch from comment 44 to MOZILLA_1_8_BRANCH.

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.

(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

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