1290566 - RadixSort must not access the array buffer through a plain property access

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect)

Description

[André Bargull [:anba]]

Test case:
---
ta = new Float32Array(256).map((k, i) => i).reverse();
Object.defineProperty(ta, "buffer", {value: new ArrayBuffer(0)});
ta.sort();
print([].toString.call(ta.slice(0, 10)));
---

Expected: Prints "0,1,2,3,4,5,6,7,8,9"
Actual: Prints "255,254,253,252,251,250,249,248,247,246"

Comment 1

[Sumit Tiwari]

I am willing to take this one up; but I don't know of an elegant solution just yet. From a preliminary investigation, I can only think of recreating the array with the correct buffer. So instead of

view = new Int32Array(array.buffer);

we can have

view = new Int32Array((new Float32Array(array)).buffer);

which gets the job done but isn't very efficient, I would assume. I am quite certain there is a better way of achieving the same thing.

Comment 2

[Sumit Tiwari]

So I was able to do something a little more cleaner: the RadixSort function is called from within the TypedArraySort function in TypedArray.js, which also finds out the attached buffer for the object. If we pass in this buffer to the RadixSort method, then we never have to read the buffer property on the array directly. This saves us the extra computation but we do incur the cost of passing an extra argument to the function. Also, I am not sure if this breaks something else somewhere (afaik it doesn't break anything, and we don't have to change a lot of files either).

Comment 3

[Morgan Phillips [:mrrrgn]]

(In reply to Sumit Tiwari from comment #2)
> So I was able to do something a little more cleaner: the RadixSort function
> is called from within the TypedArraySort function in TypedArray.js, which
> also finds out the attached buffer for the object. If we pass in this buffer
> to the RadixSort method, then we never have to read the buffer property on
> the array directly. This saves us the extra computation but we do incur the
> cost of passing an extra argument to the function. Also, I am not sure if
> this breaks something else somewhere (afaik it doesn't break anything, and
> we don't have to change a lot of files either).

I really like the idea of just passing the buffer into the sort. Look forward to seeing the patch.

Comment 4

[Sumit Tiwari]

Attachment: Bug 1290566 - RadixSort must not access buffer directly through properties

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

Comment 5

[Sumit Tiwari]

None of the JIT tests failed, and there was no performance regression either. I could not run the jstests suite entirely because my machine was taking waaay too long, but I don't suspect any failures there.

Comment 6

[André Bargull [:anba]]

(In reply to Sumit Tiwari from comment #5)
> I could not run the jstests suite entirely because my machine was
> taking waaay too long, but I don't suspect any failures there.

I can confirm this, there were no jstests regressions when I applied the attached patch. 

Apart from that: I think it'd be nice to assert that the buffer is reified when we use radix sort. That means after the |if (len < 128)| if-statement in RadixSort, add the following assertion:
```
assert(buffer !== null, "buffer should be reified when array length >= 128");
```

Comment 7

[Sumit Tiwari]

(In reply to André Bargull from comment #6)
> (In reply to Sumit Tiwari from comment #5)
> > I could not run the jstests suite entirely because my machine was
> > taking waaay too long, but I don't suspect any failures there.
> 
> I can confirm this, there were no jstests regressions when I applied the
> attached patch. 

Thanks for confirming that. I also think that since there is no test case that locks down this particular behavior that you found, we should probably add one in an existing test file.

> Apart from that: I think it'd be nice to assert that the buffer is reified
> when we use radix sort. That means after the |if (len < 128)| if-statement
> in RadixSort, add the following assertion:
> ```
> assert(buffer !== null, "buffer should be reified when array length >= 128");

That's a great idea; I just didn't know what the assert syntax was for the self-hosted files, but I did look it up and I can add that after I incorporate the other feedback from the review. 
> ```

Comment 8

[Morgan Phillips [:mrrrgn]]

Comment on attachment 8779606 [details]
Bug 1290566 - RadixSort must not access buffer directly through properties

This looks great! Before I can + can we have a patch with tests and the reification check that andré mentioned?

Comment 9

[Morgan Phillips [:mrrrgn]]

You should add the test to js/src/tests/ecma_6/TypedArray/sort_basics.js

Comment 10

[Morgan Phillips [:mrrrgn]]

btw when you run jstests feel free to only run the ecma_6/TypedArray/sort_* tests! :)

Comment 11

[Jeff Walden [:Waldo]]

I'd prefer if you had a separate test specifically for this problem, than to add to an existing test.  Adding to existing tests makes for tests that run longer, and are harder to debug when they fail (because you often have to start carefully reading the test to figure out where/how the failure happened).  Also having one test file per test means you can have more-specific, more-readable names for the test files.

So I'd add this as ecma_6/TypedArray/dont-access-buffer-through-plain-property-when-sorting.js or similar.

Comment 12

[Sumit Tiwari]

I thought maybe adding another function in the file that Morgan mentioned might be a good idea, because it already has local helper functions to create random buffers and such, so I wouldn't have to duplicate the same thing in another test file. But if everyone agrees that adding a new test is the way to go, then I'll just mirror the same functionality and throw in the few cases that I can think of.

Comment 13

[Morgan Phillips [:mrrrgn]]

I think a separate file is fine. I think you can get away with not using the helpers from sort_basics.js Some hand-made buffers should be okay here, no need to create anything too complex.

Comment 14

[Jeff Walden [:Waldo]]

Frankly, given the nature of the underlying problem, I'd just make sure you invoke the incorrect by-property access and not worry about exhaustiveness.  In my view this test below is entirely adequate, and you don't need any of the helpers from sort_basics.js.  Indeed it's *better* not to use helpers, because they just make the test harder to read/understand/debug for anyone who breaks it.

[Float32Array,
 // This test invokes originally-buggy code in RadixSort.  To call RadixSort,
 // we must have a 16-bit, 32-bit or float32 array.  To reach the buggy code
 // in RadixSort itself, we have to have a floating-point type.  So technically
 // only Float32Array is needed here, but it doesn't hurt to lightly test the
 // others.
 Float64Array,
 Uint8Array, Int8Array, Uint8ClampedArray,
 Uint16Array, Int16Array,
 Uint32Array, Int32Array].forEach(function(ctor)
{
  // Avoid the QuickSort fast-path in RadixSort, generously so in case the
  // actual |len < 128| condition ever changes.
  var tarray = new ctor(1024);
  Object.defineProperty(tarray, "buffer", { get() { throw 42; } });

  tarray.sort();
});

Comment 15

[Sumit Tiwari]

Thank you for all the feedback, Jeff and Morgan. I'll create the test and update the review board ASAP.

Comment 16

[Sumit Tiwari]

Comment on attachment 8779606 [details]
Bug 1290566 - RadixSort must not access buffer directly through properties

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

Comment 17

[Morgan Phillips [:mrrrgn]]

Comment on attachment 8779606 [details]
Bug 1290566 - RadixSort must not access buffer directly through properties

LGTM: try push before landing https://treeherder.mozilla.org/#/jobs?repo=try&revision=61a605a3a300

Comment 18

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/f3c3c5beafc7
RadixSort must not access buffer directly through properties; r=mrrrgn

Comment 19

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/f3c3c5beafc7