Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: miscompilation of some arithmetic and conditionals on arm #42876

Closed
zx2c4 opened this issue Nov 29, 2020 · 15 comments
Closed

cmd/compile: miscompilation of some arithmetic and conditionals on arm #42876

zx2c4 opened this issue Nov 29, 2020 · 15 comments
Labels
arch-arm Issues solely affecting the 32-bit arm architecture. FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@zx2c4
Copy link
Contributor

zx2c4 commented Nov 29, 2020

@FiloSottile suggested that a recent mailing list post be moved to an issue, so here goes:

Jan Mercl reports that this code will miscompile on ARM:

package main

import "fmt"

var x = [4]int32{((-0x7fffffff - 1) / 2), 0x7fffffff, 2, 4} /* 20041210-1.c:5:5 */

func main() { /* 20041210-1.c:8:1: */
        if x[0] < x[1] {
                if x[2]&x[3] < 0 {
                        panic(fmt.Errorf("%v & %v = %v, < 0 ? %v", x[2], x[3], x[2]&x[3], x[2]&x[3] < 0))
                }
        }
}

Running the same code on 386 vs arm shows success on 386 and panics on arm. I've confirmed this is the case with 1.15.5, and Meng Zhuo confirmed it to be happening on 1.13, so it is at least a somewhat oldish bug.

The current issue title is vague because I haven't looked into what's actually happening yet. And I haven't yet assessed the security implications, either, but one can start imagining worrisome corner cases.

CC @rsc @cherrymui @ianlancetaylor @aclements

@zx2c4
Copy link
Contributor Author

zx2c4 commented Nov 29, 2020

This seems to have come from this gcc test:

/* The FR-V port used to fail this test because the andcc patterns
   wrongly claimed to set the C and V flags.  */
#include <limits.h>
int x[4] = { INT_MIN / 2, INT_MAX, 2, 4 };
int
main ()
{
  if (x[0] < x[1])
    if ((x[2] & x[3]) < 0)
      abort ();
  exit (0);
}

@zx2c4
Copy link
Contributor Author

zx2c4 commented Nov 29, 2020

Here's a simpler example:

package main
  
var x = [4]int32{-0x7fffffff, 0x7fffffff, 2, 4}

func main() {
        if x[0] > x[1] {
                panic("fail 1")
        }
        if x[2]&x[3] < 0 {
                panic("fail 2") // Fails here
        }
}

It looks like the basic issue is that the first comparison uses CMP, which subtracts them and sets the V condition flag since it overflows, and then the second comparison calls TST, which ands the results and updates N and Z, but not V, and then uses BLT, which checks N!=V. Since the TST did not update V, that BLT winds up using the value of V set by the previous CMP.

@zx2c4
Copy link
Contributor Author

zx2c4 commented Nov 29, 2020

I've never looked at this compiler before, so excuse the noise if this is way off, but:

src/cmd/compile/internal/ssa/gen/ARM.rules:

(LT (CMPconst [0] l:(AND x y)) yes no) && l.Uses==1 => (LT (TST x y) yes no)

@FiloSottile FiloSottile changed the title arm: miscompilation of some arithmetic and conditionals cmd/compile: miscompilation of some arithmetic and conditionals on arm Nov 29, 2020
@FiloSottile FiloSottile added the arch-arm Issues solely affecting the 32-bit arm architecture. label Nov 29, 2020
@mengzhuo
Copy link
Contributor

I've contacted the origin auther @benshi001 about this.
I'm testing other comparsion like LT,LE,GT,GE and I will upload fix soon.

@zx2c4
Copy link
Contributor Author

zx2c4 commented Nov 30, 2020

So, I "fixed" it:

diff --git a/src/cmd/compile/internal/ssa/gen/ARM.rules b/src/cmd/compile/internal/ssa/gen/ARM.rules
index 946acd4ccc..61a410dad3 100644
--- a/src/cmd/compile/internal/ssa/gen/ARM.rules
+++ b/src/cmd/compile/internal/ssa/gen/ARM.rules
@@ -1369,7 +1369,6 @@
 (LE (CMPconst [0] l:(ADDshiftLLreg x y z)) yes no) && l.Uses==1 => (LEnoov (CMNshiftLLreg x y z) yes no)
 (LE (CMPconst [0] l:(ADDshiftRLreg x y z)) yes no) && l.Uses==1 => (LEnoov (CMNshiftRLreg x y z) yes no)
 (LE (CMPconst [0] l:(ADDshiftRAreg x y z)) yes no) && l.Uses==1 => (LEnoov (CMNshiftRAreg x y z) yes no)
-(LT (CMPconst [0] l:(AND x y)) yes no) && l.Uses==1 => (LT (TST x y) yes no)
 (LT (CMPconst [0] l:(ANDconst [c] x)) yes no) && l.Uses==1 => (LT (TSTconst [c] x) yes no)
 (LT (CMPconst [0] l:(ANDshiftLL x y [c])) yes no) && l.Uses==1 => (LT (TSTshiftLL x y [c]) yes no)
 (LT (CMPconst [0] l:(ANDshiftRL x y [c])) yes no) && l.Uses==1 => (LT (TSTshiftRL x y [c]) yes no)
diff --git a/src/cmd/compile/internal/ssa/rewriteARM.go b/src/cmd/compile/internal/ssa/rewriteARM.go
index 47fd0a94cc..bca648e9ad 100644
--- a/src/cmd/compile/internal/ssa/rewriteARM.go
+++ b/src/cmd/compile/internal/ssa/rewriteARM.go
@@ -20226,34 +20226,6 @@ func rewriteBlockARM(b *Block) bool {
 			b.resetWithControl(BlockARMLTnoov, v0)
 			return true
 		}
-		// match: (LT (CMPconst [0] l:(AND x y)) yes no)
-		// cond: l.Uses==1
-		// result: (LT (TST x y) yes no)
-		for b.Controls[0].Op == OpARMCMPconst {
-			v_0 := b.Controls[0]
-			if auxIntToInt32(v_0.AuxInt) != 0 {
-				break
-			}
-			l := v_0.Args[0]
-			if l.Op != OpARMAND {
-				break
-			}
-			_ = l.Args[1]
-			l_0 := l.Args[0]
-			l_1 := l.Args[1]
-			for _i0 := 0; _i0 <= 1; _i0, l_0, l_1 = _i0+1, l_1, l_0 {
-				x := l_0
-				y := l_1
-				if !(l.Uses == 1) {
-					continue
-				}
-				v0 := b.NewValue0(v_0.Pos, OpARMTST, types.TypeFlags)
-				v0.AddArg2(x, y)
-				b.resetWithControl(BlockARMLT, v0)
-				return true
-			}
-			break
-		}
 		// match: (LT (CMPconst [0] l:(ANDconst [c] x)) yes no)
 		// cond: l.Uses==1
 		// result: (LT (TSTconst [c] x) yes no)

This is obviously an incomplete fix, but it does generate code that actually works (for that one case):

Before my fix:

TST             R0, R1
BLT             loc_6C164

After my fix:

AND             R0, R0, R1
CMP             R0, #0
BLT             loc_6C168

Basically, the bug is that the original replacement rules assumed that TST set V, but TST does not set V, so CMP might be a better fit.

So, the cudgel fix might be just deleting all those errant replacement rules.

@gopherbot
Copy link

Change https://golang.org/cl/274026 mentions this issue: cmd/compile: do not assume TST and TEQ set V

@zx2c4
Copy link
Contributor Author

zx2c4 commented Nov 30, 2020

I've contacted the origin auther @benshi001 about this.
I'm testing other comparsion like LT,LE,GT,GE and I will upload fix soon.

I think I've got something working and posted on Gerrit already, but I'd appreciate your review and comments you might have. Feel free to jump in: https://golang.org/cl/274026

@zx2c4
Copy link
Contributor Author

zx2c4 commented Dec 1, 2020

@gopherbot please backport this because compiler bugs in bitmath seem worrisome

@gopherbot
Copy link

Backport issue(s) opened: #42929 (for 1.14), #42930 (for 1.15).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://golang.org/wiki/MinorReleases.

@mengzhuo
Copy link
Contributor

mengzhuo commented Dec 2, 2020

Sorry for the delay, I was working on other project. you've submit the CL, which LGTM.
However this SSA optimazation can be apply to uint since arm32 TST only change Z flag as far as I know.

@dmitshur dmitshur added the NeedsFix The path to resolution is known, but the work has not been done. label Dec 3, 2020
@dmitshur dmitshur added this to the Go1.16 milestone Dec 3, 2020
@aclements
Copy link
Member

@zx2c4 , would you mind preparing backport CLs for 1.15 and 1.14?

@zx2c4
Copy link
Contributor Author

zx2c4 commented Jan 7, 2021

I can backport it. But...

I had started doing that before because I initially thought it was a very worrying bug. Indeed it smells Very Very Bad. What if crypto code hits this! What about security code! What if!!

So I added a line to the compiler to panic if it ever got to generating the bad code, and then scripted walking through github and building all of the go code I could find, sorted by repo popularity. I let this run for a few hours and... nothing triggered it.

Maybe it's not as big of a deal as previously thought, then?

@gopherbot
Copy link

Change https://golang.org/cl/282432 mentions this issue: [release-branch.go1.15] cmd/compile: do not assume TST and TEQ set V on arm

@cagedmantis
Copy link
Contributor

@zx2c4, would you mind preparing a backport CLs for 1.14?

@gopherbot
Copy link

Change https://golang.org/cl/289009 mentions this issue: [release-branch.go1.14] cmd/compile: do not assume TST and TEQ set V on arm

gopherbot pushed a commit that referenced this issue Mar 1, 2021
…on arm

These replacement rules assume that TST and TEQ set V. But TST and
TEQ do not set V. This is a problem because instructions like LT are
actually checking for N!=V. But with TST and TEQ not setting V, LT
doesn't do anything meaningful. It's possible to construct trivial
miscompilations from this, such as:

    package main

    var x = [4]int32{-0x7fffffff, 0x7fffffff, 2, 4}

    func main() {
        if x[0] > x[1] {
            panic("fail 1")
        }
        if x[2]&x[3] < 0 {
            panic("fail 2") // Fails here
        }
    }

That first comparison sets V, via the CMP that subtracts the values
causing the overflow. Then the second comparison operation thinks that
it uses the result of TST, when it actually uses the V from CMP.

Before this fix:

    TST             R0, R1
    BLT             loc_6C164

After this fix:

    TST             R0, R1
    BMI             loc_6C164

The BMI instruction checks the N flag, which TST sets.  This commit
fixes the issue by using [LG][TE]noov instead of vanilla [LG][TE], and
also adds a test case for the direct issue.

Updates #42876.
Fixes #42930.

Change-Id: I13c62c88d18574247ad002b671b38d2d0b0fc6fa
Reviewed-on: https://go-review.googlesource.com/c/go/+/282432
Trust: Jason A. Donenfeld <Jason@zx2c4.com>
Run-TryBot: Jason A. Donenfeld <Jason@zx2c4.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
@golang golang locked and limited conversation to collaborators Feb 3, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
arch-arm Issues solely affecting the 32-bit arm architecture. FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Development

No branches or pull requests

8 participants
@zx2c4 @cagedmantis @mengzhuo @FiloSottile @dmitshur @aclements @gopherbot and others