1000606 - Differential Testing: Different output message involving Math.round, Math.fround and Math.log2

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

function f() {
    print(Math.round(Math.fround(Math.log2(Math.fround(Math.hypot(1, 1))))))
}
f()
f()


$ ./js-opt-64-dm-ts-darwin-33ca5e321046 --fuzzing-safe --ion-parallel-compile=off 3058.js0
0

$ ./js-opt-64-dm-ts-darwin-33ca5e321046 --fuzzing-safe --ion-parallel-compile=off --ion-eager 3058.js
0
1

(Tested this on 64-bit Mac js opt threadsafe deterministic shell off m-c rev 33ca5e321046, and I think it also reproduces on Linux)

My configure flags (Mac) are:

CC="clang -Qunused-arguments" CXX="clang++ -Qunused-arguments" AR=ar sh /Users/skywalker/trees/mozilla-central/js/src/configure --target=x86_64-apple-darwin12.5.0 --enable-optimize --disable-debug --enable-profiling --enable-gczeal --enable-debug-symbols --disable-tests --enable-more-deterministic --with-ccache --enable-threadsafe <other NSPR options>

autoBisect shows this is probably related to the following changeset:

The first bad revision is:
changeset:   http://hg.mozilla.org/mozilla-central/rev/a07b45e32644
user:        Benjamin Bouvier
date:        Fri Feb 28 12:07:40 2014 +0100
summary:     Bug 930477: Implemented roundf for all platforms; r=waldo

Benjamin, is bug 930477 likely regressor?

===

function f() {
    print(Math.round(Math.fround(Math.exp(Math.log2(65536)))))
}
f()
f()

$ ./js-opt-64-dm-ts-darwin-33ca5e321046 --fuzzing-safe --ion-parallel-compile=off 1241.js
8886111
8886111

$   ./js-opt-64-dm-ts-darwin-33ca5e321046 --fuzzing-safe --ion-parallel-compile=off --ion-eager 1241.js
8886111
8886112

is a similar testcase that also points to bug 930477.

Comment 1

[Benjamin Bouvier [:bbouvier] (inactive)]

Investigating. Seems like there are some differences between roundf and the assembler rountine.

function f() {
    var d = Math.fround(0.4999999701976776);
    return Math.round(d)
}
assertEq(f(), f());

function g() {
    var c = Math.fround(8886111)
    return Math.round(c)
}
assertEq(g(), g())

Comment 2

[Benjamin Bouvier [:bbouvier] (inactive)]

For what it's worth, it's not limited to Float32, Double show the same kind of issue:

function f() {
    var x = 0.499999999999999944488848768742172978818416595458984375; // this is the biggest double less than 0.5
    return Math.round(x);
}
assertEq(f(), f()); // fails with --ion-eager --ion-parallel-compile=off

The assembly routine for Round adds 0.5 to the input and then rounds. A comment in MacroAssembler-arm lets think that it should be 0.5 for negative values, BiggestDoubleLessThan(0.5) for positive values. Note that it also happens on ARM. I am working on a fix.

Comment 3

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Patch + tests

TL;DR: congrats to fuzzers. In the rounding algorithm used in SpiderMonkey (floor(x + 0.5)), instead of adding 0.5, should we add the biggest value strictly less than .5 when x >= 0?

(In reply to Benjamin Bouvier [:bbouvier] from comment #2)
> function f() {
>     var x = 0.499999999999999944488848768742172978818416595458984375; //
> this is the biggest double less than 0.5
>     return Math.round(x);
> }

Let D the biggest double less than double(0.5), i.e. the value in the example above. After some investigation work:
- Fun: Math.round(D) is wrong in the interpreter, as Math.round(D) is implemented as floor(D + .5), and D + .5 == 1 (because of rounding, I assume), so Math.round(D) == 1 instead of 0 (the correct value). v8 and native programs state Math.round(D) == 0, not 1.
- There's a test for that value in jit-tests/tests/ion/mathRound. It's checking that the result of Math.round(D) == 1, which is the incorrect result.
- I made a C program that checks if the property of rounding is true for all doubles. So far, it has only found D as a counter-example of the above property, in the meaningful range (which is the range of doubles such that adding 0.5 doesn't return the same value, see comment in math_round_impl).
- MRound (i.e. Math.round in the JIT) has the same issue for this value D.
- For floats, it's way worse, as adding .5f rounds up more easily (that's the second case found by the fuzzer). For values less than but very close to .5f, it's also the case (first case found by the fuzzer).

I think this can happen only for positive numbers, so I would tend to follow marty's comment in MacroAssembler-arm.cpp and simply use the biggest value strictly less than .5 (resp. .5f) in the rounding algorithms. Does it make sense?

In the JITs, it implies loading 0.5 or the biggest value less than 0.5 in a register with respect to the sign of the input (=> more instructions and more constants => bigger code, but that looks like the price to pay for correctness).

Asking feedback to Waldo and Marty for opinions about the general thinking + implementations (Waldo for GetBiggestNumberLessThan / interpreter, Marty for the JIT / ARM parts).

Comment 4

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Patch + tests

Better with all tests. See previous upload for comments.

Comment 6

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Waldo/Marty, feedback ping please?

Comment 7

[Jeff Walden [:Waldo]]

Comment on attachment 8411885 [details] [diff] [review]
Patch + tests

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

Sorry for delay, extremely nitpicky/tricky/complicated security bugs hated me.

::: js/src/jit-test/tests/ion/bug1000606.js
@@ +1,1 @@
> +function f(x) {

Rename this to froundThenRound.  Single-letter variable names are to be avoided for anything but loop variables and, for simple functions, argument names.

@@ +3,5 @@
> +    return Math.round(d);
> +}
> +
> +var x = 0.4999999701976776;
> +assertEq(f(x), f(x));

var biggestFloatLessThanHalf = 0.5 - Math.pow(2, -25);
assertEq(new Float32Array([0.5 - Math.pow(2, -26)])[0], 0.5,
         "correct greatest-less-than-0.5 value tested");
assertEq(froundThenRound(biggestFloatLessThanHalf),
         froundThenRound(biggestFloatLessThanHalf));

to reassure the untrusting reader (as every reader of a constant like this should be!).

@@ +10,5 @@
> +assertEq(f(y), f(y));
> +
> +function g(x) {
> +    return Math.round(x);
> +}

Rename this to MathRound.

@@ +13,5 @@
> +    return Math.round(x);
> +}
> +// biggest double less than 0.5
> +var z = 0.499999999999999944488848768742172978818416595458984375;
> +assertEq(g(z), g(z));

var biggestDoubleLessThanHalf = 0.5 - Math.pow(2, -54);
assertEq(0.5 - Math.pow(2, -55), 0.5,
         "correct value computed above");
assertEq(g(biggestDoubleLessThanHalf), g(biggestDoubleLessThanHalf));

::: js/src/jit-test/tests/ion/mathRound.js
@@ -2,5 @@
>  // Requires --ion-eager to enter at the top of each loop.
>  
>  var roundDTests = [
>  	[-0, -0],
> -	[0.49999999999999997, 1],

Scumbag ion/mathRound.js.  Implement using the specs, peoples!

::: js/src/jit/arm/MacroAssembler-arm.cpp
@@ +4218,5 @@
>      // Since it is known to be > 0.0, explicitly convert to a larger range,
>      // then a value that rounds to INT_MAX is explicitly different from an
>      // argument that clamps to INT_MAX
> +
> +    // Add 0.49999999999999999 to positive numbers, store the result into tmp

// Add the biggest number less than 0.5 (not 0.5, because adding that to the
// biggest number less than 0.5 would undesirably round up to 1), and store
// the result into tmp.

@@ +4240,5 @@
>      bind(&handleNeg);
>      // Negative case, negate, then start dancing.  This number may be positive, since we added 0.5
> +
> +    // Add 0.5 to negative numbers, store the result into tmp
> +    ma_vimm(GetBiggestNumberLessThan(0.5), ScratchFloatReg);

This comment and this code are not in sync.  I don't understand enough ARM assembly to comment on whether the change is correct, but it seems...dubious, given that the x86 algorithm uses 0.5 here (and I read through it and it looked like the right value to use).

@@ +4286,5 @@
>      // Since it is known to be > 0.0, explicitly convert to a larger range,
>      // then a value that rounds to INT_MAX is explicitly different from an
>      // argument that clamps to INT_MAX
> +
> +    // Add 0.49999999999999999 to positive numbers, store the result into tmp

Same comment change.

@@ +4307,5 @@
>  
>      bind(&handleNeg);
> +
> +    // Add 0.5 to negative numbers, storing the result into tmp.
> +    ma_vimm_f32(0.5f, ScratchFloatReg);

Um, so round and roundf do things differently for this bit of the algorithm?  Skeptical jwalden is even *more* skeptical.

::: js/src/jit/shared/CodeGenerator-x86-shared.cpp
@@ +1707,5 @@
>      masm.branchNegativeZero(input, output, &bailout);
>      if (!bailoutFrom(&bailout, lir->snapshot()))
>          return false;
>  
> +    // Input is non-negative. Add the biggest double less than 0.5 and truncate,

I'd like to see an explanation for why not 0.5, here.  Something like "(because if the input is the biggest double less than 0.5, adding 0.5 would undesirably round up to 1)".

@@ +1793,5 @@
>      masm.branchNegativeZeroFloat32(input, output, &bailout);
>      if (!bailoutFrom(&bailout, lir->snapshot()))
>          return false;
>  
> +    // Input is non-negative. Add the biggest float less than 0.5 and truncate,

Again "(because if the input is the biggest float less than 0.5, adding 0.5 would undesirably round up to 1)".

::: js/src/jsmath.cpp
@@ +765,5 @@
>      return true;
>  }
>  
> +template<typename T>
> +T

Just a note, but if you don't have inline on the definition of a templated method you want to be inline, things can fall over and die in various ways, last I knew.  A quirk of how inline interacts with templated methods.

@@ +768,5 @@
> +template<typename T>
> +T
> +js::GetBiggestNumberLessThan(T x)
> +{
> +    typedef typename mozilla::SelectTrait<T>::Bits Bits;

SelectTrait probably should be in detail, it's not really the public API for this.  You want FloatingPoint.

@@ +779,5 @@
> +    u.asT = x;
> +    mozilla::DebugOnly<Bits> formerBits = u.bits;
> +    u.bits -= 1;
> +    JS_ASSERT(formerBits > u.bits); // underflow check
> +    return u.asT;

typedef typename mozilla::FloatingPoint<T>::Bits Bits;
Bits bits = mozilla::BitwiseCast<Bits>(x);
MOZ_ASSERT(bits > 0, "will underflow");
return mozilla::BitwiseCast<T>(bits - 1);

I think we should also MOZ_ASSERT(!mozilla::IsNegative(x)) and MOZ_ASSERT(mozilla::IsFinite(x)) here as well.  There are really a bunch of different constraints on when this method makes any sense, and we should assert all of them.

Comment 8

[Marty Rosenberg [:mjrosenb]]

Comment on attachment 8411885 [details] [diff] [review]
Patch + tests

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

::: js/src/jit/arm/MacroAssembler-arm.cpp
@@ +4240,5 @@
>      bind(&handleNeg);
>      // Negative case, negate, then start dancing.  This number may be positive, since we added 0.5
> +
> +    // Add 0.5 to negative numbers, store the result into tmp
> +    ma_vimm(GetBiggestNumberLessThan(0.5), ScratchFloatReg);

I agree, this looks like it should just be 0.5.

Comment 9

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Benjamin, just wondering if there is any movement on this?

Comment 10

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to Gary Kwong [:gkw] [:nth10sd] PTO Jul 19 to 27 from comment #9)
> Benjamin, just wondering if there is any movement on this?

I can certainly finish it in the next few days.

Comment 11

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Patch and test, v2

Thanks for the feedback! Fixed the nits (there was indeed something wrong in the ARM implementation, probably due to a bad copy pasto :/).

Comment 12

[Benjamin Bouvier [:bbouvier] (inactive)]

Try build for sanity:
https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=556d6929856f

Comment 13

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Patch and test, v3

Just changed the GetBiggest... function to not be inline. It didn't make sense to have the function inline but defined in another file + gcc was warning that the inline templated function wasn't ever instantiated, despite the explicit instantiation in jsmath.cpp.

Comment 14

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Just wondering, is this now ready to land?

Comment 15

[Benjamin Bouvier [:bbouvier] (inactive)]

Good question:
https://tbpl.mozilla.org/?tree=Try&rev=a40730d4768a

Comment 16

[Benjamin Bouvier [:bbouvier] (inactive)]

And the answer is yes:
https://hg.mozilla.org/integration/mozilla-inbound/rev/d227e849d2a5

Comment 17

[Ryan VanderMeulen [:RyanVM]]

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