Closed Bug 1290974 Opened 4 years ago Closed 3 years ago

RSH in QuickSort/Partition can generate negative indices

Categories

(Core :: JavaScript: Standard Library, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla53
Tracking Status
firefox51 --- wontfix
firefox53 --- fixed

People

(Reporter: anba, Assigned: anba)

References

Details

Attachments

(1 file, 1 obsolete file)

Test case:
---
ta = new Int8Array(0x60000000);
ta.fill(1);
ta.sort(function(a, b){ var d = a - b; return d; });

for (var i = 0; i < ta.length; ++i) {
    if (ta[i] !== 1) {
        print("check failed", i);
        break;
    }
}
---

Expected: Does not print any failure messages.
Actual: Prints "check failed 805306368".
Blocks: 1291005
Attached patch index.diff (obsolete) — Splinter Review
Attachment #8778505 - Flags: review?(jorendorff)
(In reply to Morgan Phillips [:mrrrgn] from comment #1)
> Created attachment 8778505 [details] [diff] [review]
> index.diff

Switching from signed to unsigned right-shift is probably the easiest way to fix this issue.
  `var medianIndex = (from + to) >>> 1;`

Alternatively we could go with this version which avoids exceeding the max-int32 limit when adding |from| and |to|. (I'm too lazy to read the assembler code to find out whether or not the JIT inserts an overflow check for `(from + to) >>> 1`. ;-) )
  `var medianIndex = from + ((to - from) >> 1);`


And maybe we should also add an assertion to the QuickSort function to ensure that the |len| parameter is a (positive) int32 value.
Attached patch bug1290974.patchSplinter Review
Assignee: nobody → andrebargull
Attachment #8778505 - Attachment is obsolete: true
Status: NEW → ASSIGNED
Attachment #8778505 - Flags: review?(jorendorff)
Attachment #8825068 - Flags: review?(evilpies)
Comment on attachment 8825068 [details] [diff] [review]
bug1290974.patch

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

Can we land the test or is that too slow?
Attachment #8825068 - Flags: review?(evilpies) → review+
(In reply to Tom Schuster [:evilpie] from comment #4)
> Can we land the test or is that too slow?

It's too slow, it needs several minutes to finish in an opt-build.
Pushed by ryanvm@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/60088a811479
Avoid exceeding max-int32 when computing the range in quicksort/partition. r=evilpie
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/60088a811479
Status: ASSIGNED → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla53
We've built 51 RC. This is too late for 51. Mark 51 won't fix.
You need to log in before you can comment on or make changes to this bug.