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)
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)
12.39 KB,
patch
|
sunfish
:
review+
lsblakk
:
approval-mozilla-aurora+
|
Details | Diff | Splinter Review |
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)
Comment 1•10 years ago
|
||
(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)
Assignee | ||
Comment 2•10 years ago
|
||
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)
Comment 3•10 years ago
|
||
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 4•10 years ago
|
||
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-
Assignee | ||
Comment 5•10 years ago
|
||
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)
Assignee | ||
Updated•10 years ago
|
Attachment #8406179 -
Attachment is obsolete: true
Assignee | ||
Comment 6•10 years ago
|
||
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 7•10 years ago
|
||
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+
Assignee | ||
Comment 8•10 years ago
|
||
(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 9•10 years ago
|
||
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-
Assignee | ||
Comment 10•10 years ago
|
||
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)
Assignee | ||
Comment 11•10 years ago
|
||
Attachment #8407067 -
Attachment is obsolete: true
Attachment #8407067 -
Flags: review?(sunfish)
Attachment #8407070 -
Flags: review?(sunfish)
Comment 12•10 years ago
|
||
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+
Assignee | ||
Comment 13•10 years ago
|
||
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.
Assignee | ||
Comment 14•10 years ago
|
||
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)
Comment 15•10 years ago
|
||
https://hg.mozilla.org/mozilla-central/rev/35e57f348ddf
Status: ASSIGNED → RESOLVED
Closed: 10 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla31
Comment 17•10 years ago
|
||
(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)
Updated•10 years ago
|
status-b2g-v1.3:
--- → unaffected
status-b2g-v1.4:
--- → affected
status-b2g-v2.0:
--- → fixed
status-firefox29:
--- → wontfix
status-firefox30:
--- → affected
Comment 18•10 years ago
|
||
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?
Reporter | ||
Comment 20•10 years ago
|
||
(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
Updated•10 years ago
|
Attachment #8407070 -
Flags: approval-mozilla-aurora? → approval-mozilla-aurora+
Updated•10 years ago
|
status-firefox-esr24:
--- → unaffected
Updated•10 years ago
|
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
Updated•10 years ago
|
Whiteboard: [adv-main30+]
Comment 22•10 years ago
|
||
Confirmed issue on 2014-04-04, Fx30. Verified fixed on 2014-06-03, Fx30 and Fx31.
Comment 23•10 years ago
|
||
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 ago → 10 years ago
Flags: needinfo?(gary)
Reporter | ||
Comment 24•10 years ago
|
||
Verified on mozilla-central (32), mozilla-aurora (31) and mozilla-beta (30).
Status: RESOLVED → VERIFIED
Flags: needinfo?(gary)
Comment 25•10 years ago
|
||
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.
status-seamonkey2.26:
--- → wontfix
Updated•9 years ago
|
Group: core-security
You need to log in
before you can comment on or make changes to this bug.
Description
•