Closed Bug 1290566 Opened 3 years ago Closed 3 years ago

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

Categories

(Core :: JavaScript: Standard Library, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla51
Tracking Status
firefox50 --- affected
firefox51 --- fixed

People

(Reporter: anba, Assigned: sumi29, Mentored)

References

Details

Attachments

(1 file)

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"
Blocks: 1291005
Mentor: winter2718
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.
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).
(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.
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.
(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");
```
Assignee: nobody → sumi29
Status: NEW → ASSIGNED
(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 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?
Attachment #8779606 - Flags: review?(winter2718)
You should add the test to js/src/tests/ecma_6/TypedArray/sort_basics.js
btw when you run jstests feel free to only run the ecma_6/TypedArray/sort_* tests! :)
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.
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.
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.
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();
});
Thank you for all the feedback, Jeff and Morgan. I'll create the test and update the review board ASAP.
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
Attachment #8779606 - Flags: review?(winter2718) → review+
Pushed by mphillips@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/f3c3c5beafc7
RadixSort must not access buffer directly through properties; r=mrrrgn
https://hg.mozilla.org/mozilla-central/rev/f3c3c5beafc7
Status: ASSIGNED → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla51
Depends on: 1295034
You need to log in before you can comment on or make changes to this bug.