Last Comment Bug 707017 - JS Correctness: enumeration order (on native objects which have an enumerate hook) depends on whether TI is enabled
: JS Correctness: enumeration order (on native objects which have an enumerate ...
Status: RESOLVED FIXED
: testcase
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: x86_64 Linux
: -- critical (vote)
: mozilla11
Assigned To: Brian Hackett (:bhackett)
:
Mentors:
Depends on:
Blocks: langfuzz 708794
  Show dependency treegraph
 
Reported: 2011-12-01 15:51 PST by Christian Holler (:decoder)
Modified: 2011-12-11 01:26 PST (History)
8 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
patch (2.86 KB, patch)
2011-12-07 12:33 PST, Brian Hackett (:bhackett)
luke: review+
Details | Diff | Review
Updated patch (2.28 KB, patch)
2011-12-08 12:13 PST, Christian Holler (:decoder)
luke: review+
Details | Diff | Review
Updated patch (2.31 KB, patch)
2011-12-08 12:40 PST, Christian Holler (:decoder)
choller: review+
Details | Diff | Review

Description Christian Holler (:decoder) 2011-12-01 15:51:48 PST
The following test produces different output with options "-m -a" vs. "-m -n -a" using mozilla-central revision ca140190529a:


function SameValue(v1, v2) { 
  return v1 === v2;
}
function arraysEqual(a1, a2) {
  var len1 = a1.length, len2 = a2.length;
  for (var i = 0; i < len1; i++)
    if (!SameValue(a1[i], a2[i]))
  return true;
}
function strictNestedShadowEval() {
  return arguments;
}
a1 = strictNestedShadowEval("1", 2);
arraysEqual(a1, ["1", 2])
assertEq(a1,null);


Output:

$ $JS -m -a min.js 
min.js:15: Error: Assertion failed: got ({0:"1", 1:2}), expected null
$ $JS -m -a -n min.js 
min.js:15: Error: Assertion failed: got ({1:2, 0:"1"}), expected null


I'm not sure if this is really a bug or not, but if it's not, then it's producing false positives for me during the testing and it would be good if it could get fixed.
Comment 1 David Mandelin [:dmandelin] 2011-12-02 16:29:31 PST
Brian, do you know why this happens?
Comment 2 Brian Hackett (:bhackett) 2011-12-02 16:34:03 PST
No, I want to investigate this and the other correctness bugs early next week.
Comment 3 Brian Hackett (:bhackett) 2011-12-05 12:43:00 PST
This seems to be an issue with enumerate hooks and lazy resolution on native classes (similar issues have cropped up with global objects before).  Resolving a property of the object installs it as a native property, and whether or not that resolution actually happens depends on how the code is executed (interp/jit/etc.).  When it comes time to enumerate all properties of the object for a snapshot (as is done before iterating on an object, or in this case before toSource'ing it), all properties are installed on the object but any new ones will be installed after ones which are already in place.

This has been this way for a while I'd wager and would be tricky to fix.  It's not a bug vs. the JS language spec (which leaves enumeration order unspecified), and barring some user complaining it would be probably best to leave it as is.

For fuzzing, you can avoid inconsistent behavior due to different enumeration order by adding some code at the end of Snapshot in jsiter.cpp to sort the array of ids if a --more-deterministic flag is set somewhere.  Doing this would break websites, however, so the sorting should not happen if the flag is not set.
Comment 4 Gary Kwong [:gkw] [:nth10sd] 2011-12-05 13:00:33 PST
Also see bug 626596 comment 2 and comment 4, might be related.
Comment 5 Jesse Ruderman 2011-12-05 13:09:02 PST
Here's a simpler testcase that shows the behavior difference:

var a = (function(){return arguments;})(7, 7);
a[1];
for (var p in a)
  print(p);

Why does [whether resolution happens] depend on execution mode?

How likely is this bug to affect web site behavior?  Does it affect any objects other than |arguments|?
Comment 6 Brian Hackett (:bhackett) 2011-12-05 17:59:03 PST
(In reply to Jesse Ruderman from comment #5)
> Here's a simpler testcase that shows the behavior difference:
> 
> var a = (function(){return arguments;})(7, 7);
> a[1];
> for (var p in a)
>   print(p);
> 
> Why does [whether resolution happens] depend on execution mode?

In this case, when accesses on arguments objects happen in certain JIT stubs (but not all JIT stubs) they do a property lookup which causes the resolution to happen, while in other JIT paths and in the interpreter arguments objects are checked for and a lookup performed that avoids the resolution.

> How likely is this bug to affect web site behavior?  Does it affect any
> objects other than |arguments|?

It can affect any native objects which have an enumerate hook.  The only other one I know of which works in this way are global objects; standard classes get resolved lazily, and the order they are resolved determines the enumeration order.  This was the issue in bug 626596.
Comment 7 Christian Holler (:decoder) 2011-12-07 11:30:39 PST
Is this bug still a WONTFIX? If so, can any JS dev help me to implement that sorting mentioned in comment 3? We already have a compile time flag to enable more determinism (bug 706433) for differential testing, so it would just be adding code within "#ifdef JS_MORE_DETERMINISTIC".
Comment 8 Gary Kwong [:gkw] [:nth10sd] 2011-12-07 11:33:56 PST
(In reply to Christian Holler (:decoder) from comment #7)
> Is this bug still a WONTFIX? If so, can any JS dev help me to implement that
> sorting mentioned in comment 3? We already have a compile time flag to
> enable more determinism (bug 706433) for differential testing, so it would
> just be adding code within "#ifdef JS_MORE_DETERMINISTIC".

File a new bug and reference this one as well as bug 626596 ?
Comment 9 Brian Hackett (:bhackett) 2011-12-07 12:33:30 PST
Created attachment 579792 [details] [diff] [review]
patch

This should keep the id arrays sorted if the shell is compiled with a deterministic configuration.  Decoder, can you see if this works as you expect?
Comment 10 Christian Holler (:decoder) 2011-12-07 17:18:52 PST
(In reply to Brian Hackett (:bhackett) from comment #9)
> Created attachment 579792 [details] [diff] [review] [diff] [details] [review]
> patch
> 
> This should keep the id arrays sorted if the shell is compiled with a
> deterministic configuration.  Decoder, can you see if this works as you
> expect?


Unfortunately the patch blows up on 64 bit and I haven't been able to figure out why yet. I'll try tomorrow again. In case it helps, here is a valgrind trace:

==22434== Invalid write of size 8
==22434==    at 0x510F4D: void js::detail::CopyNonEmptyArray<jsid>(jsid*, jsid const*, unsigned long) (Sort.h:56)
==22434==    by 0x5110E3: bool js::detail::MergeArrayRuns<jsid, SortComparatorIds>(jsid*, jsid const*, unsigned long, unsigned long, SortComparatorIds) (Sort.h:94)
==22434==    by 0x5102AC: bool js::MergeSort<jsid, SortComparatorIds>(jsid*, unsigned long, jsid*, SortComparatorIds) (Sort.h:156)
==22434==    by 0x50ADCC: Snapshot(JSContext*, JSObject*, unsigned int, js::AutoIdVector*) (jsiter.cpp:373)
==22434==    by 0x50AF32: js::GetPropertyNames(JSContext*, JSObject*, unsigned int, js::AutoIdVector*) (jsiter.cpp:403)
==22434==    by 0x57E341: JSObject::preventExtensions(JSContext*, js::AutoIdVector*) (jsscope.cpp:1176)
==22434==    by 0x523F7D: JSObject::sealOrFreeze(JSContext*, JSObject::ImmutabilityType) (jsobj.cpp:2694)
==22434==    by 0x441EC9: JSObject::freeze(JSContext*) (jsobj.h:961)
==22434==    by 0x437459: JS_FreezeObject (jsapi.cpp:3261)
==22434==    by 0x753E00: JS::RegisterPerfMeasurement(JSContext*, JSObject*) (jsperf.cpp:274)
==22434==    by 0x40FE7D: NewGlobalObject(JSContext*, CompartmentKind) (js.cpp:4997)
==22434==    by 0x41070D: Shell(JSContext*, js::cli::OptionParser*, char**) (js.cpp:5138)
==22434==  Address 0x5e11580 is 0 bytes after a block of size 256 alloc'd
==22434==    at 0x4C26FDE: malloc (vg_replace_malloc.c:236)
==22434==    by 0x41A0AD: js_malloc (Utility.h:166)
==22434==    by 0x41B9D9: js::TempAllocPolicy::malloc_(unsigned long) (jsalloc.h:99)
==22434==    by 0x5128E2: js::VectorImpl<jsid, 8ul, js::TempAllocPolicy, false>::growTo(js::Vector<jsid, 8ul, js::TempAllocPolicy>&, unsigned long) (Vector.h:115)
==22434==    by 0x512438: js::Vector<jsid, 8ul, js::TempAllocPolicy>::growHeapStorageBy(unsigned long) (Vector.h:599)
==22434==    by 0x511A5B: js::Vector<jsid, 8ul, js::TempAllocPolicy>::growStorageBy(unsigned long) (Vector.h:639)
==22434==    by 0x510BF0: bool js::Vector<jsid, 8ul, js::TempAllocPolicy>::append<jsid>(jsid) (Vector.h:759)
==22434==    by 0x50FF8C: js::AutoVectorRooter<jsid>::append(jsid const&) (jscntxt.h:2202)
==22434==    by 0x50A54F: Enumerate(JSContext*, JSObject*, JSObject*, jsid, bool, unsigned int, js::HashSet<jsid, IdHashPolicy, js::TempAllocPolicy>&, js::AutoIdVector*) (jsiter.cpp:210)
==22434==    by 0x50A639: EnumerateNativeProperties(JSContext*, JSObject*, JSObject*, unsigned int, js::HashSet<jsid, IdHashPolicy, js::TempAllocPolicy>&, js::AutoIdVector*) (jsiter.cpp:225)
==22434==    by 0x50A95B: Snapshot(JSContext*, JSObject*, unsigned int, js::AutoIdVector*) (jsiter.cpp:303)
==22434==    by 0x50AF32: js::GetPropertyNames(JSContext*, JSObject*, unsigned int, js::AutoIdVector*) (jsiter.cpp:403)
Comment 11 Luke Wagner [:luke] 2011-12-07 17:31:16 PST
Comment on attachment 579792 [details] [diff] [review]
patch

Review of attachment 579792 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsiter.cpp
@@ +270,5 @@
> +    {
> +        /* Pick an arbitrary total order on jsids that is stable across executions. */
> +        JSString *astr = IdToString(cx, a);
> +        JSString *bstr = IdToString(cx, b);
> +        if (!astr || !bstr)

Need to null-check 'astr' before computing IdToString for 'bstr'.
Comment 12 Christian Holler (:decoder) 2011-12-08 04:06:49 PST
(In reply to Luke Wagner [:luke] from comment #11)
> Comment on attachment 579792 [details] [diff] [review]
> patch
> 
> Review of attachment 579792 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jsiter.cpp
> @@ +270,5 @@
> > +    {
> > +        /* Pick an arbitrary total order on jsids that is stable across executions. */
> > +        JSString *astr = IdToString(cx, a);
> > +        JSString *bstr = IdToString(cx, b);
> > +        if (!astr || !bstr)
> 
> Need to null-check 'astr' before computing IdToString for 'bstr'.

I tried rewriting this to returning false after the first IdToString if astr is null (and then a second null check for bstr after the second IdToString) but it does not solve the crash issue i posted for 64 bit.
Comment 13 Christian Holler (:decoder) 2011-12-08 04:32:06 PST
I think I found the problem. I managed to fix this by doing:

  375     jsid *tmp = (jsid*) js_malloc(sizeof(jsid) * n);
  376     if (!MergeSort(ids, n, tmp, SortComparatorIds(cx)))
  377         return false;

I read the MergeSort comment and was wondering why the patch passes "ids + n" as a temporary scratch, so I tried allocating temporary storage to see if it solves the issue and that seems to be the case. Is this right?
Comment 14 Brian Hackett (:bhackett) 2011-12-08 06:37:23 PST
(In reply to Christian Holler (:decoder) from comment #13)
> I think I found the problem. I managed to fix this by doing:
> 
>   375     jsid *tmp = (jsid*) js_malloc(sizeof(jsid) * n);
>   376     if (!MergeSort(ids, n, tmp, SortComparatorIds(cx)))
>   377         return false;
> 
> I read the MergeSort comment and was wondering why the patch passes "ids +
> n" as a temporary scratch, so I tried allocating temporary storage to see if
> it solves the issue and that seems to be the case. Is this right?

Oops, yes.  I went by an example in jsarray.cpp and didn't read the code closely enough.
Comment 15 Christian Holler (:decoder) 2011-12-08 12:13:50 PST
Created attachment 580138 [details] [diff] [review]
Updated patch

Here's an updated patch that uses a js::Vector for temporary space for sorting and does the null checks of a and b separately (not sure if this is correct, I'm a JS engine noob^^).

I ran this through jstests and got the following failures:

e4x/extensions/json-stringify-dropping-xml-elements.js
ecma_5/JSON/stringify.js
ecma_5/JSON/stringify-dropping-elements.js
ecma_5/JSON/stringify-ignore-noncallable-toJSON.js
ecma_5/JSON/stringify-replacer.js
ecma_5/Object/15.2.3.7-01.js
ecma_5/Object/15.2.3.14-01.js
js1_5/extensions/regress-381304.js
js1_5/Regress/regress-465013.js

All of these failures are related to enumeration order (where the current order is hardcoded in the test somehow), except for ecma_5/Object/15.2.3.7-01.js where I am not sure what's wrong. It would be cool if one of you could have a quick look that nothing is broken and this is to be expected.
Comment 16 Jeff Walden [:Waldo] (remove +bmo to email) 2011-12-08 12:19:12 PST
Tests shouldn't be doing that, relying on enumeration order.  (I usually watch out for this, but it looks like I dropped the ball on some of these.)  File a followup to fix them, or fix them here, or something?
Comment 17 Luke Wagner [:luke] 2011-12-08 12:27:21 PST
Comment on attachment 580138 [details] [diff] [review]
Updated patch

Need to test for OOM from resizeUnitialized.  Other than that, r+.
Comment 18 Christian Holler (:decoder) 2011-12-08 12:40:15 PST
Created attachment 580148 [details] [diff] [review]
Updated patch

Check for resizeUninitialized OOM as requested, r+ taken from last patch. This needs checkin.
Comment 19 Brian Hackett (:bhackett) 2011-12-08 19:29:27 PST
https://hg.mozilla.org/integration/mozilla-inbound/rev/d87f60b6c99d
Comment 20 Ed Morley [:emorley] 2011-12-10 20:45:57 PST
https://hg.mozilla.org/mozilla-central/rev/d87f60b6c99d
Comment 21 :Ms2ger 2011-12-11 01:26:11 PST
Comment on attachment 580148 [details] [diff] [review]
Updated patch

>--- a/js/src/jsiter.cpp	Wed Dec 07 12:11:23 2011 -0800
>+++ b/js/src/jsiter.cpp	Fri Dec 09 05:38:14 2011 +0100
>+        /* Pick an arbitrary total order on jsids that is stable across executions. */
>+        JSString *astr = IdToString(cx, a);
>+	if (!astr)

Whoops, tab.

Note You need to log in before you can comment on or make changes to this bug.