524122 - Incorrect optimization for integers in numeric sort

Status: RESOLVED FIXED

(Tamarin Graveyard :: Virtual Machine, defect, P3)

Description

[Lars T Hansen]

The case in ArraySort::NumericCompare that compares integers is vulnerable to overflow; overflowing results frequently have the wrong sign, thus breaking the sort.

Comment 1

[Lars T Hansen]

Attachment: Test case

The test case must be compiled with ASC.  Attaching pre-compiled ABC too.

Comment 2

[Lars T Hansen]

Attachment: Test case, ABC

Comment 3

[Lars T Hansen]

Attachment: Obvious fix

Patch will require versioning.

Comment 4

[Steven Johnson]

Comment on attachment 408017 [details] [diff] [review]
Obvious fix

Heh, nope, actually, int atoms can be > 32 bits on 64-bit builds... see https://bugzilla.mozilla.org/show_bug.cgi?id=521353 for more info.

but just return the int32 casts (doing an intptr_t subtraction) and I think that will be right.

Comment 5

[Lars T Hansen]

(In reply to comment #4)
> (From update of attachment 408017 [details] [diff] [review])
> Heh, nope, actually, int atoms can be > 32 bits on 64-bit builds... see
> https://bugzilla.mozilla.org/show_bug.cgi?id=521353 for more info.
> 
> but just return the int32 casts (doing an intptr_t subtraction) and I think
> that will be right.

Presumably you mean s/return/remove/ .... brain fart on my part.  Will attach a new patch.

Comment 6

[Lars T Hansen]

Attachment: Obvious fix v2 :-)

Comment 7

[Michael Kohler [:mkohler]]

This is a mass change. Every comment has "assigned-to-new" in it.

I didn't look through the bugs, so I'm sorry if I change a bug which shouldn't be changed. But I guess these bugs are just bugs that were once assigned and people forgot to change the Status back when unassigning.

Comment 8

[William Maddox]

Any reason this hasn't landed?

Comment 9

[Lars T Hansen]

(In reply to comment #8)
> Any reason this hasn't landed?

It needs to be properly versioned and the patch predates all that.  Me fix.

Comment 10

[Lars T Hansen]

Attachment: Patch, with versioning and versioned test cases

Same fix but revised with versioning.  Note the test is in ecma3/Array, even though it uses 'import' and passes a non-Ecma argument to Array.prototype.sort().  Opinions on that choice would be welcomed.

Comment 11

[Edwin Smith]

my opinion is such a test only works on as3 and thus belongs under as3/Array

Comment 12

[Steven Johnson]

Comment on attachment 469419 [details] [diff] [review]
Patch, with versioning and versioned test cases

Looks fine, with one caveat: I'd like to see a performance test to ensure adding the check hasn't caused a perf regression due to the test-in-the-inner-loop this introduces. (Simple enough to fix if so, just add a new NumericCompare proc and select it based on the bugCompatibility flag)

Comment 13

[Lars T Hansen]

(Thinking out loud.)

A reasonable test would be to sort integer arrays of three lengths with Array.NUMERIC: short (say, five elements), medium (50), and long (5000).

The baseline cannot be the original code because it gets the result wrong so it may not perform the correct number of operations.

Instead, I will have to compare the code I propose to land and the code that has a separate NumericCompare proc, and select the second if it is faster.

Comment 14

[Lars T Hansen]

Results suggest that it is significantly faster across the board to have two functions, one correct and one compatible.  The reason is easy to understand: AvmCore::currentBugCompatibility mucks around to get the code context.  I had forgotten that, I thought of it as a simple inlined getter.

I'll refine the patch and offer a new patch for review (with the test cases rewritten to the new regime and moved to their appropriate places).

Comment 15

[Lars T Hansen]

Attachment: Patch, updated

Comment 16

[Steven Johnson]

(In reply to comment #14)
> AvmCore::currentBugCompatibility mucks around to get the code context.  I had
> forgotten that, I thought of it as a simple inlined getter.

Yeah, the guidelines for using it are that it's cheap, but not free: don't call it in the inner loop.

Comment 17

[Lars T Hansen]

tamarin-redux changeset:   5154:1da8c00e0dfb

Comment 18

[Lars T Hansen]

Attachment: Compile fix

This was pushed as 5155:f4a0efbffbe7, but I'd like a post-hoc review just to be on the safe side.  The logic is that since the input values are atoms then their intptr_t representations carry values that are in the int32_t range, thus converting from intptr_t to int is always lossless (int is at least as large as int32_t).

The use of 'int' is in the existing API, which we should clean up at some point.

Comment 19

[Lars T Hansen]

Reopening because the expected result for the old incorrect code is different on 32-bit and 64-bit systems - the test case probably needs refining.  The issue is that atoms carry integer values outside the 32-bit range.  As a consequence the int cast I just inserted in the compile fix may be too naive a fix.

Comment 20

[Lars T Hansen]

Attachment: Test fix, better compile fix

Updates test case to deal with different incorrect results on 32-bit and 64-bit systems.

Updates the new code to avoid a cast from intptr_t to int on 64-bit systems.

Was pushed as tamarin-redux changeset: 5156:5ecff2fedcb2, review still required.

Comment 21

[Steven Johnson]

Comment on attachment 471439 [details] [diff] [review]
Test fix, better compile fix

At first I was concerned that the difference in return result could cause subtle issues with user code, but the values never percolate out to AS3, so I think we're safe.