Closed Bug 995817 Opened 10 years ago Closed 10 years ago

Differential Testing: Incorrect result when division-by-zero is used in an indirectly-truncated context

Categories

(Core :: JavaScript Engine: JIT, defect)

x86_64
macOS
defect
Not set
major

Tracking

()

VERIFIED FIXED
mozilla31
Tracking Status
firefox29 --- wontfix
firefox30 --- verified
firefox31 --- verified
firefox-esr24 --- unaffected
b2g-v1.3 --- unaffected
b2g-v1.4 --- fixed
b2g-v2.0 --- fixed
seamonkey2.26 --- wontfix

People

(Reporter: gkw, Assigned: nbp)

References

Details

(Keywords: regression, sec-critical, testcase, Whiteboard: [adv-main30+])

Attachments

(1 file, 3 obsolete files)

setJitCompilerOption('baseline.usecount.trigger', 1)
let r;
(function() {
    function f() {
        return (1 + -1 / 0) << null
    }
    print(f())
    print(f())
})()

$ ./js-opt-64-dm-ts-darwin-ebdf2740dc3e --fuzzing-safe --ion-parallel-compile=off 5098.js
0
0

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

(Tested this on 64-bit Mac js opt threadsafe deterministic shell off m-c rev ebdf2740dc3e)

My configure flags 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/f98f80d2126c
user:        Jan de Mooij
date:        Sat Sep 28 11:45:21 2013 +0200
summary:     Bug 915763 - Remove TypeScript::dynamicList and dynamic Monitor functions. r=bhackett

Jan, is bug 915763 a possible regressor?
Flags: needinfo?(jdemooij)
(In reply to Gary Kwong [:gkw] [:nth10sd] from comment #0)
> Jan, is bug 915763 a possible regressor?

No it just exposed this probably.

It looks like here:

    return (1 + -1 / 0) << null

In CodeGeneratorX86Shared::visitDivI, we think the Div is truncated, and always return 0. But this is bogus, we should invalidate and then return -Infinity.

Nicolas, hg annotate on MDiv::truncate points to bug 841666, so can you take a look?
No longer blocks: 915763
Flags: needinfo?(jdemooij) → needinfo?(nicolas.b.pierron)
This patch prevent keeping the Int32 specialization coming from the operands if the operation cannot be replaced by a constant at the time of the BinaryArithInstruction::infer.

The Int32 specialization caused the Range Analysis to assume that the front-end knew better and that it was fine to truncate this operation.  We just cannot assume anything except if Range Analysis prove it, or if we know better.
Assignee: nobody → nicolas.b.pierron
Status: NEW → ASSIGNED
Attachment #8406179 - Flags: review?(sunfish)
Flags: needinfo?(nicolas.b.pierron)
Specializing almost all int32 divs as double seems wrong. I'm pretty sure we have benchmarks with int32 divisions that never bail, and which would now use double division...
Comment on attachment 8406179 [details] [diff] [review]
Do not eagerly specialize MDiv to Int32.

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

The underlying problem seems to be that the div is being marked as truncated, while it is not actually fully truncated.

The following code in RangeAnalysis.cpp's CanTruncate makes what appears to be the key decision:

    // Special case integer division: the result of a/b can be infinite
    // but cannot actually have rounding errors induced by truncation.
    if (candidate->isDiv() && candidate->toDiv()->specialization() == MIRType_Int32)
        canHaveRoundingErrors = false;

    if (canHaveRoundingErrors)
        return false;

Integer division returning infinite is perhaps not a rouding concern per se, but it seems that CanTruncate ought to handle it in a similar manner.
Attachment #8406179 - Flags: review?(sunfish) → review-
Currently Truncated is used as:
 1. Ignore Infinity (? / 0) and substitute them by 0.
 2. Ignore overflow (INT_MIN / -1 == INT_MAX --> 0)
 3. Ignore negative zeros. (-0 --> 0)
 4. Ignore remainder. (0.2 --> 0)

I think we should distinguish (1) & (4) from (2) & (3), as the later are keeping the same meaning in modulo 2³² arithmetic, which is what the truncation made by Range Analysis is used for.

(1) does not respect modulo 2³² arithmetic, as the above example highlight.
(4) does not respect modulo 2³² arithmetic, as (3/4 + 3/4) | 0 highlight (see test case).
Attachment #8406809 - Flags: review?(sunfish)
Attachment #8406809 - Flags: feedback?(mrosenberg)
Attachment #8406179 - Attachment is obsolete: true
Comment on attachment 8406809 [details] [diff] [review]
MDiv only truncates operation which are valid in the 2^32 range.

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

::: js/src/jit/arm/CodeGenerator-arm.cpp
@@ +535,2 @@
>          masm.ma_cmp(rhs, Imm32(0));
> +        if (mir->mir->canTruncateInfinities()) {

nit: I fixed this typo locally.
Comment on attachment 8406809 [details] [diff] [review]
MDiv only truncates operation which are valid in the 2^32 range.

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

js> (Math.pow(2,31) / (-1))|0
-2147483648


If we cared about perf of this type of case, what we could do is replace the truncate with a label, and rather than bailing out on \infty, just setting the correct register to zero, and branching to the truncate label.

::: js/src/jit/arm/CodeGenerator-arm.cpp
@@ +550,5 @@
> +    // Handle negative 0.
> +    if (!mir->isTruncated() && mir->canBeNegativeZero()) {
> +        Label nonzero;
> +        masm.ma_cmp(lhs, Imm32(0));
> +        masm.ma_b(&skip, Assembler::NotEqual);

Is the label skip even in scope here?

@@ +551,5 @@
> +    if (!mir->isTruncated() && mir->canBeNegativeZero()) {
> +        Label nonzero;
> +        masm.ma_cmp(lhs, Imm32(0));
> +        masm.ma_b(&skip, Assembler::NotEqual);
> +        masm.ma_cmp(rhs, Imm32(0));

I also suspect that chained compares are faster than compare; branch; compare.
Attachment #8406809 - Flags: feedback?(mrosenberg) → feedback+
(In reply to Marty Rosenberg [:mjrosenb] from comment #7)
> Comment on attachment 8406809 [details] [diff] [review]
> MDiv only truncates operation which are valid in the 2^32 range.
> 
> Review of attachment 8406809 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> js> (Math.pow(2,31) / (-1))|0
> -2147483648
> 
> 
> If we cared about perf of this type of case, what we could do is replace the
> truncate with a label, and rather than bailing out on \infty, just setting
> the correct register to zero, and branching to the truncate label.

In which case we would need a maybeLabel, but yes, we can reduce the code size by jumping to unique truncate path.

> ::: js/src/jit/arm/CodeGenerator-arm.cpp
> @@ +550,5 @@
> > +    // Handle negative 0.
> > +    if (!mir->isTruncated() && mir->canBeNegativeZero()) {
> > +        Label nonzero;
> > +        masm.ma_cmp(lhs, Imm32(0));
> > +        masm.ma_b(&skip, Assembler::NotEqual);
> 
> Is the label skip even in scope here?

Indeed, tbpl caught this one and I fixed it locally too.  I will try it on the simulator.

> @@ +551,5 @@
> > +    if (!mir->isTruncated() && mir->canBeNegativeZero()) {
> > +        Label nonzero;
> > +        masm.ma_cmp(lhs, Imm32(0));
> > +        masm.ma_b(&skip, Assembler::NotEqual);
> > +        masm.ma_cmp(rhs, Imm32(0));
> 
> I also suspect that chained compares are faster than compare; branch;
> compare.

oh would you do so? something like that:

  masm.ma_cmp(lhs, Imm32(0));
  masm.ma_cmp(rhs, Imm32(0), Assembler::NotEqual);
  if (!bailoutIf(Assembler::LessThan, snapshot))
      return false;

?
Comment on attachment 8406809 [details] [diff] [review]
MDiv only truncates operation which are valid in the 2^32 range.

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

::: js/src/jit/MIR.h
@@ +4069,5 @@
>      bool canBeNegativeOverflow_;
>      bool canBeDivideByZero_;
>      bool canBeNegativeDividend_;
> +    bool canTruncateInfinities_;
> +    bool canTruncateRemainder_;

Currently these two new flags always have the same value. Are you planning for future changes which will set only one of these flags? If not, it'd be nice to merge them, if a satisfactory name can be found :-).

@@ +4105,3 @@
>              div->setTruncated(true);
> +            div->setCanTruncateInfinities(true);
> +            div->setCanTruncateRemainder(true);

This is currently the only place where these are set to true. That means only asm.js gets these optimizations right now.

Would it be practical to extend this patch to teach range analysis how to set these flags when all of a divide's users are actual full truncates?

::: js/src/jit/shared/CodeGenerator-x86-shared.cpp
@@ +926,5 @@
>  
>      // Handle divide by zero.
>      if (mir->canBeDivideByZero()) {
>          masm.testl(rhs, rhs);
> +        if (mir->canTruncateInfinities()) {

This is pretty subtle. Previously, I understood isTruncated() to mean that one could choose to run the value through |0 and it wouldn't affect correctness. Now, it's awkward to charactarize the semantics of isTruncated().

I'd prefer to see isTruncated() keep its original meaning, and have a new flag for this new kind of weaker truncation. Range analysis' truncation logic could then be taught to set this new flag instead of isTruncated() for these cases where the value isn't fully truncated in all senses. Do you think this makes sense and is practical?
Attachment #8406809 - Flags: review?(sunfish) → review-
This should answer most of your concerns.

I added one flag, and set this flag to true when MDiv is indirectly truncated by the range analysis.

I also added a check to see if the division result only flows in bitwise instructions, in which cases we can safely truncate it as we used to do.

I will open a follow-up bug, as I think we can do better use of the Range Analysis, by moving the edge case analysis of MDiv to the range analysis.
Attachment #8406809 - Attachment is obsolete: true
Attachment #8407067 - Flags: review?(sunfish)
Attachment #8407067 - Attachment is obsolete: true
Attachment #8407067 - Flags: review?(sunfish)
Attachment #8407070 - Flags: review?(sunfish)
Comment on attachment 8407070 [details] [diff] [review]
MDiv only truncates operation which are valid in the 2^32 range.

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

::: js/src/jit/MIR.h
@@ +4072,5 @@
>      bool unsigned_;
>  
> +    // A Division can be truncated in 4 differents ways:
> +    //   1. Ignore Infinities (x / 0 --> 0).
> +    //   2. Ignore overflow (INT_MIN / -1 == (INT_MAX + 1) --> 0)

INT_MIN/-1 is truncated to INT_MIN, not 0.

@@ +4083,5 @@
> +    //
> +    // (1) is not safe, as Infinities would have absorbed other math operations.
> +    //
> +    // (4) is not safe, as the remainders of multiple numbers can add up to
> +    // integers.

Could you also add a note here saying that Div is the only operator which can produce Infinities and remainders when given Int32 inputs? That would help explain why Div is being handled differently from the other operators.

::: js/src/jit/RangeAnalysis.cpp
@@ +2228,5 @@
> +              case MDefinition::Op_BitOr:
> +              case MDefinition::Op_BitXor:
> +              case MDefinition::Op_Lsh:
> +              case MDefinition::Op_Rsh:
> +              case MDefinition::Op_Ursh:

Perhaps doing this "properly" might entail changing isOperandTruncated() into getOperandTruncationKind() which returns an enum indicating whether there is direct, indirect, or no truncation. But, I realize that's a much broader change, and I don't think it's necessary to do this all at once.
Attachment #8407070 - Flags: review?(sunfish) → review+
Comment on attachment 8407070 [details] [diff] [review]
MDiv only truncates operation which are valid in the 2^32 range.

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

::: js/src/jit/MIR.cpp
@@ +1525,5 @@
>  
>  bool
>  MDiv::fallible() const
>  {
> +    return !isTruncated() || !isTruncatedIndirectly();

self-nit: I replaced this by only "!isTruncated()".

::: js/src/jit/arm/CodeGenerator-arm.cpp
@@ +515,5 @@
>          // Handle INT32_MIN / -1;
>          // The integer division will give INT32_MIN, but we want -(double)INT32_MIN.
>          masm.ma_cmp(lhs, Imm32(INT32_MIN)); // sets EQ if lhs == INT32_MIN
>          masm.ma_cmp(rhs, Imm32(-1), Assembler::Equal); // if EQ (LHS == INT32_MIN), sets EQ if rhs == -1
> +        if (mir->canBeNegativeOverflow()) {

self-nit: this should be mir->canTruncateOverflow(), as it is on x86.
https://hg.mozilla.org/integration/mozilla-inbound/rev/35e57f348ddf

rankov: This patch is changing MDivI such as we use more descriptive canTruncate* functions instead of isTruncated.  As isTruncated is still available, you might want to redo the same modification as on x86 / arm codegen
Flags: needinfo?(branislav.rankov)
https://hg.mozilla.org/mozilla-central/rev/35e57f348ddf
Status: ASSIGNED → RESOLVED
Closed: 10 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla31
(In reply to Nicolas B. Pierron [:nbp] from comment #14)
> rankov: This patch is changing MDivI such as we use more descriptive
> canTruncate* functions instead of isTruncated.  As isTruncated is still
> available, you might want to redo the same modification as on x86 / arm
> codegen

Thanks for letting me know. I will update my patch for CodeGenerator-mips.
Flags: needinfo?(branislav.rankov)
Comment on attachment 8407070 [details] [diff] [review]
MDiv only truncates operation which are valid in the 2^32 range.

[Approval Request Comment]
Bug caused by (feature/regressing bug #): 841666
User impact if declined: Sec-critical bug
Testing completed (on m-c, etc.): on m-c
Risk to taking this patch (and alternatives if risky): Moderate to low. It's fixing a very subtle bug, but we have a good explanation for what's going on.
String or IDL/UUID changes made by this patch: None.
Attachment #8407070 - Flags: approval-mozilla-aurora?
Setting s-s per :sunfish's request.
Group: core-security
(In reply to Gary Kwong [:gkw] [:nth10sd] from comment #19)
> Setting s-s per :sunfish's request.

He also says assume the worst for now, so setting sec-critical.
Keywords: sec-critical
Attachment #8407070 - Flags: approval-mozilla-aurora? → approval-mozilla-aurora+
Summary: Differential Testing: Different output message involving 'baseline.usecount.trigger' → Differential Testing: Incorrect result when division-by-zero is used in an indirectly-truncated context
Whiteboard: [adv-main30+]
Confirmed issue on 2014-04-04, Fx30.
Verified fixed on 2014-06-03, Fx30 and Fx31.
Status: RESOLVED → VERIFIED
Actually, removing verified status. Needs to be verified in build made with --enable-more-deterministic. Gary will do this.
Status: VERIFIED → RESOLVED
Closed: 10 years ago10 years ago
Flags: needinfo?(gary)
Verified on mozilla-central (32), mozilla-aurora (31) and mozilla-beta (30).
Status: RESOLVED → VERIFIED
Flags: needinfo?(gary)
trying to apply this to SeaMonkey 2.26.1 (Gecko 29) resulted in patch conflicts, and due to the nature of this patchset it seems like I won't be able to take it.
Group: core-security
You need to log in before you can comment on or make changes to this bug.