1290579 - Float32 RadixSort ignores typed array byte offsets

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect)

Description

[André Bargull [:anba]]

Test case:
---
ab = new ArrayBuffer(257 * Float32Array.BYTES_PER_ELEMENT);
ta = new Float32Array(ab, Float32Array.BYTES_PER_ELEMENT, 256);
ta2 = new Float32Array(ab, 0, 1);

ta2[0] = 1;

ta.sort();

print(ta2[0]);
---

Expected: Prints "1"
Actual: Prints "0"

Comment 1

[Sumit Tiwari]

Andre: I have a fix that, by exposing TypedArray_byteOffsetGetter in SelfHosting.cpp, gets the byteOffset which can then be used to construct the underlying Int32Array object in RadixSort.

```
let byteOffset = 0;
byteOffset = callFunction(std_TypedArray_byteOffset, array);
view = new Int32Array(buffer, byteOffset, len);
```

As always, I can't comment on the performance issues that might arise from this approach, but all the TypedArray tests pass atleast. Your thoughts?

Comment 2

[André Bargull [:anba]]

Yes, that approach looks good to me. :-)

Comment 3

[Jeff Walden [:Waldo]]

It might be preferable to use UnsafeGetInt32FromReservedSlot(array, JS_TYPEDARRAYLAYOUT_BYTEOFFSET_SLOT).  That should optimize/inline better than calling a getter function that I don't believe we inline right now.  We *would* have to be careful, tho, about being sure |array| was a typed array, and never possibly a *wrapped* typed array from another global.  Something to be cautious about.

Feel free to ask more questions here or (somewhat preferably, if you can be on at a time coinciding with approximate working hours in the US -- but either's fine) in #jsapi on Mozilla's IRC servers if you have them.

Comment 4

[André Bargull [:anba]]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #3)
> We *would* have to be careful, tho, about being sure |array| was a typed array,
> and never possibly a *wrapped* typed array from another global.

It's possible for |array| to be a wrapped typed array, TypedArraySort doesn't use CallTypedArrayMethodIfWrapped to unwrap itself.

Comment 5

[Sumit Tiwari]

Thank you Jeff and Andre for your inputs. This is my first time with these APIs so please bear with my naivete.

Would something like this work? All TypedArray tests pass and everything seems to work:

```
// Find the offset of the buffer based on whether array is typed or not
 let offset = 0;
 var isTypedArray = IsObject(array) && IsTypedArray(array);
 if (isTypedArray) {
    offset = UnsafeGetInt32FromReservedSlot(array, 2 /*JS_TYPEDARRAYLAYOUT_BYTEOFFSET_SLOT*/);
 } else {
    offset = callFunction(CallTypedArrayMethodIfWrapped, array, "TypedArrayByteOffset");
 }
view = new Int32Array(buffer, offset, len);
```

Note that we do find out if the object is a TypedArray or not in TypedArray.js, so we can pass that information to the RadixSort method, but that would just increase the number of arguments so I am not too sure about that approach.
Also, I think I am unable to hit the 'else' condition with any existing test.

Comment 6

[Sumit Tiwari]

Attachment: Bug 1290579 - Float32 RadixSort ignores typed array byte offsets

Review commit: https://reviewboard.mozilla.org/r/77764/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/77764/

Comment 7

[André Bargull [:anba]]

This test asserts when the patch is applied:
---
var ab = new ArrayBuffer(257 * Float32Array.BYTES_PER_ELEMENT);
var ta = new Float32Array(ab, Float32Array.BYTES_PER_ELEMENT, 256);
var ta2 = new Float32Array(ab, 0, 1);

ta2[0] = 1;

// Use the sort() method of a different global.
newGlobal().Float32Array.prototype.sort.call(ta);

print(ta2[0]);
---

Assertion error:
---
Assertion failure: args.length() == 1, at /home/andre/git/mozilla-central/js/src/vm/SelfHosting.cpp:1126
Segmentation fault (core dumped)
---

Fortunately it's quite simple to fix the error. This line:
---
offset = callFunction(CallTypedArrayMethodIfWrapped, array, "TypedArrayByteOffset");
---

needs to be changed to:
---
offset = callFunction(CallTypedArrayMethodIfWrapped, array, array, "TypedArrayByteOffset");
---

The first |array| parameter is needed to select the correct global, and the second |array| parameter is the argument to TypedArrayByteOffset. (http://hg.mozilla.org/mozilla-central/file/644b3de5d7a1/js/src/builtin/TypedArray.js#l57 is another example of this invocation pattern.)

Comment 8

[Sumit Tiwari]

Comment on attachment 8789610 [details]
Bug 1290579 - Float32 RadixSort ignores typed array byte offsets

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/77764/diff/1-2/

Comment 9

[Sumit Tiwari]

Thank you Andre for the correction. I knew I was missing something, I just didn't fully understand that API. Please review the patch and redirect to the proper authority, if necessary.

Comment 10

[André Bargull [:anba]]

Comment on attachment 8789610 [details]
Bug 1290579 - Float32 RadixSort ignores typed array byte offsets

https://reviewboard.mozilla.org/r/77764/#review76970

::: js/src/builtin/Sorting.js:122
(Diff revision 2)
>          }
>  
>          // Verify that the buffer is non-null
>          assert(buffer !== null, "Attached data buffer should be reified when array length is >= 128.");
>  
> -        view = new Int32Array(buffer);
> +        // Find the offset of the buffer based on whether array is typed or not

I think I prefer this version
```js
// |array| is either a typed array or a cross-compartment wrapper for one.
let offset;
if (IsTypedArray(array)) {
    offset = TypedArrayByteOffset(array);
} else {
    offset = callFunction(CallTypedArrayMethodIfWrapped, array, array, "TypedArrayByteOffset");
}
```

We can skip the `IsObject(array)` call because `array` should always be a typed array or wrapped typed array. If that's not the case, it means something is horribly broken. ;-)

Maybe we should document this by adding
```js
assert(IsPossiblyWrappedTypedArray(array), "typed arrays must be passed to RadixSort");
```
as the first statement in RadixSort.

::: js/src/tests/ecma_6/TypedArray/sort_byteoffset.js:17
(Diff revision 2)
> +    Int32Array,
> +    Uint32Array,
> +    Float32Array,
> +    Float64Array ];
> +
> +for (var ctor of constructors) {

Can you duplicate this loop to test the cross-compartment case? (Using `newGlobal().Float32Array.prototype.sort.call(ta);` instead of `ta.sort()`.)

Comment 11

[André Bargull [:anba]]

I think this looks good, but I'll let Waldo decide. :-)

Comment 12

[Jeff Walden [:Waldo]]

Comment on attachment 8789610 [details]
Bug 1290579 - Float32 RadixSort ignores typed array byte offsets

https://reviewboard.mozilla.org/r/77764/#review77036

Looks good, just one mini-fix and I can stamp this.

::: js/src/builtin/Sorting.js:125
(Diff revision 2)
>          assert(buffer !== null, "Attached data buffer should be reified when array length is >= 128.");
>  
> -        view = new Int32Array(buffer);
> +        // Find the offset of the buffer based on whether array is typed or not
> +        let offset = 0;
> +        var isTypedArray = IsObject(array) && IsTypedArray(array);
> +        if (isTypedArray) {

Yeah, no need for IsObject.  At that point, you should just make it a ternary expression:

    let offset = IsTypedArray(array)
                 ? TypedArrayByteOffset(array)
                 : callFunction(CallTypedArrayMethodIfWrapped, array, array,
                                "TypedArrayByteOffset");

Comment 13

[Sumit Tiwari]

Comment on attachment 8789610 [details]
Bug 1290579 - Float32 RadixSort ignores typed array byte offsets

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/77764/diff/2-3/

Comment 14

[Jeff Walden [:Waldo]]

Comment on attachment 8789610 [details]
Bug 1290579 - Float32 RadixSort ignores typed array byte offsets

https://reviewboard.mozilla.org/r/77764/#review77168

Comment 15

[André Bargull [:anba]]

Attachment: bug1290579.patch

Updated Sumit Tiwari's patch to apply cleanly on inbound. Also added the assertions mentioned in comment #10 and changed the test case to include tests with cross-compartment wrapped typed arrays per comment #10. Carrying r+ from Waldo.

Comment 16

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=de0a3a0dc4e40076356c589e23860fa74f1a2e64

Comment 17

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e9fc43e54c99
Float32 RadixSort ignores typed array byte offsets. r=Waldo

Comment 18

[Dorel Luca [:dluca]]

Backed out 1 changesets (bug 1290579) for spidermonkey cgc failure at js/src/jsgc.cpp:7634 on a CLOSED TREE

https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=e9fc43e54c998e0f98755d0479e607d2841d912d

https://treeherder.mozilla.org/logviewer.html#?job_id=146465540&repo=mozilla-inbound&lineNumber=54425

https://hg.mozilla.org/integration/mozilla-inbound/rev/cc39a82c2bf45fb8d6592bf065f038caec7ae826

Comment 19

[André Bargull [:anba]]

Hi :jonco, 

this patch for self-hosted JS code changed some GC timings, resulting in a test failure for the testGCRootsRemoved test in testGCHooks.cpp. Adding AutoLeaveZeal made the test failure go away, but I don't know if that's the correct approach for this test. Can you take a look?


JS_GC_ZEAL=IncrementalMultipleSlices gdb --args dist/bin/jsapi-tests testGCRootsRemoved
---
testGCRootsRemoved
Assertion failure: !isIncrementalGCInProgress(), at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:7634

Thread 1 "jsapi-tests" received signal SIGSEGV, Segmentation fault.
0x0000000000ca43ad in js::gc::GCRuntime::startDebugGC (this=0x7ffff5f16748, gckind=GC_SHRINK, budget=...) at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:7634
7634        MOZ_ASSERT(!isIncrementalGCInProgress());
---


Stack trace:
---
#0  0x0000000000ca43ad in js::gc::GCRuntime::startDebugGC (this=0x7ffff5f16748, gckind=GC_SHRINK, budget=...) at /home/andre/hg/mozilla-inbound/js/src/jsgc.cpp:7634
#1  0x000000000049cc5c in cls_testGCRootsRemoved::run (this=0x28d07e0 <cls_testGCRootsRemoved_instance>, global=...) at /home/andre/hg/mozilla-inbound/js/src/jsapi-tests/testGCHooks.cpp:81
#2  0x0000000000563f29 in main (argc=2, argv=0x7fffffffd8b8) at /home/andre/hg/mozilla-inbound/js/src/jsapi-tests/tests.cpp:132
---

Comment 20

[Jon Coppeard (:jonco)]

(In reply to André Bargull [:anba] from comment #19)
> Adding
> AutoLeaveZeal made the test failure go away, but I don't know if that's the
> correct approach for this test. 

Yes, you can add AutoLeaveZeal at the start of the testGCRootsRemoved test.  The test tries to start a GC, and this fails if zeal has already started a GC.

Comment 21

[André Bargull [:anba]]

Attachment: bug1290579-part2-gc-zeal.patch

(In reply to Jon Coppeard (:jonco) from comment #20)
> (In reply to André Bargull [:anba] from comment #19)
> > Adding
> > AutoLeaveZeal made the test failure go away, but I don't know if that's the
> > correct approach for this test. 
> 
> Yes, you can add AutoLeaveZeal at the start of the testGCRootsRemoved test. 
> The test tries to start a GC, and this fails if zeal has already started a
> GC.

Great! I've attached a patch with this change.

Comment 22

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=badd1585f635dff770b73fc8d8bf811d5c6bba4b

Comment 23

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/81ee4253265c
Float32 RadixSort ignores typed array byte offsets. r=Waldo
https://hg.mozilla.org/integration/mozilla-inbound/rev/adff34fe23b4
Part 2: Add AutoZeal to GC test to avoid starting GC too early. r=jonco

Comment 24

[Cristian Brindusan [:cbrindusan]]

https://hg.mozilla.org/mozilla-central/rev/81ee4253265c
https://hg.mozilla.org/mozilla-central/rev/adff34fe23b4