From bdc7d5677edd1dab21cdaa1f6498e0c2a6c9d7bf Mon Sep 17 00:00:00 2001 From: David Chase Date: Tue, 4 Dec 2018 10:00:16 -0500 Subject: [PATCH] [release-branch.go1.11] cmd/compile: check for negative upper bound to IsSliceInBounds IsSliceInBounds(x, y) asserts that y is not negative, but there were cases where this is not true. Change code generation to ensure that this is true when it's not obviously true. Prove phase cleans a few of these out. With this change the compiler text section is 0.06% larger, that is, not very much. Benchmarking still TBD, may need to wait for access to a benchmarking box (next week). Also corrected run.go to handle '?' in -update_errors output. Fixes #28799. Change-Id: Ia8af90bc50a91ae6e934ef973def8d3f398fac7b Reviewed-on: https://go-review.googlesource.com/c/152477 Run-TryBot: David Chase Reviewed-by: Keith Randall TryBot-Result: Gobot Gobot (cherry picked from commit ea6259d5e9d57f247b7d877d4d04602b74ae5155) Reviewed-on: https://go-review.googlesource.com/c/153638 --- src/cmd/compile/internal/gc/ssa.go | 21 +++++++ test/fixedbugs/issue28797.go | 53 +++++++++++++++++ test/loopbce.go | 94 +++++++++++++++--------------- test/prove.go | 18 +++--- test/run.go | 2 +- 5 files changed, 131 insertions(+), 57 deletions(-) create mode 100644 test/fixedbugs/issue28797.go diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go index af43da6275..5b84a0a5bb 100644 --- a/src/cmd/compile/internal/gc/ssa.go +++ b/src/cmd/compile/internal/gc/ssa.go @@ -3863,6 +3863,18 @@ func (s *state) boundsCheck(idx, len *ssa.Value) { s.check(cmp, panicindex) } +func couldBeNegative(v *ssa.Value) bool { + switch v.Op { + case ssa.OpSliceLen, ssa.OpSliceCap, ssa.OpStringLen: + return false + case ssa.OpConst64: + return v.AuxInt < 0 + case ssa.OpConst32: + return int32(v.AuxInt) < 0 + } + return true +} + // sliceBoundsCheck generates slice bounds checking code. Checks if 0 <= idx <= len, branches to exit if not. // Starts a new block on return. // idx and len are already converted to full int width. @@ -3870,6 +3882,15 @@ func (s *state) sliceBoundsCheck(idx, len *ssa.Value) { if Debug['B'] != 0 { return } + if couldBeNegative(len) { + // OpIsSliceInBounds requires second arg not negative; if it's not obviously true, must check. + cmpop := ssa.OpGeq64 + if len.Type.Size() == 4 { + cmpop = ssa.OpGeq32 + } + cmp := s.newValue2(cmpop, types.Types[TBOOL], len, s.zeroVal(len.Type)) + s.check(cmp, panicslice) + } // bounds check cmp := s.newValue2(ssa.OpIsSliceInBounds, types.Types[TBOOL], idx, len) diff --git a/test/fixedbugs/issue28797.go b/test/fixedbugs/issue28797.go new file mode 100644 index 0000000000..480c1059b8 --- /dev/null +++ b/test/fixedbugs/issue28797.go @@ -0,0 +1,53 @@ +// run + +// Copyright 2018 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package main + +import ( + "fmt" +) + +// test expects f to panic, but not to run out of memory, +// which is a non-panic fatal error. OOM results from failure +// to properly check negative limit. +func test(f func()) { + defer func() { + r := recover() + if r == nil { + panic("panic wasn't recoverable") + } + }() + f() +} + +//go:noinline +func id(x int) int { + return x +} + +func main() { + test(foo) + test(bar) +} + +func foo() { + b := make([]byte, 0) + b = append(b, 1) + id(len(b)) + id(len(b) - 2) + s := string(b[1 : len(b)-2]) + fmt.Println(s) +} + +func bar() { + b := make([]byte, 1) + b = append(b, 1) + i := id(-1) + if i < len(b) { // establish value is not too large. + s := string(b[1:i]) // should check for negative also. + fmt.Println(s) + } +} diff --git a/test/loopbce.go b/test/loopbce.go index b4bf797497..81f2524e95 100644 --- a/test/loopbce.go +++ b/test/loopbce.go @@ -6,7 +6,7 @@ package main func f0a(a []int) int { x := 0 for i := range a { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - x += a[i] // ERROR "Proved IsInBounds$" + x += a[i] // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return x } @@ -14,7 +14,7 @@ func f0a(a []int) int { func f0b(a []int) int { x := 0 for i := range a { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - b := a[i:] // ERROR "Proved IsSliceInBounds$" + b := a[i:] // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" x += b[0] } return x @@ -23,7 +23,7 @@ func f0b(a []int) int { func f0c(a []int) int { x := 0 for i := range a { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - b := a[:i+1] // ERROR "Proved IsSliceInBounds$" + b := a[:i+1] // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" x += b[0] } return x @@ -40,7 +40,7 @@ func f1(a []int) int { func f2(a []int) int { x := 0 for i := 1; i < len(a); i++ { // ERROR "Induction variable: limits \[1,\?\), increment 1$" - x += a[i] // ERROR "Proved IsInBounds$" + x += a[i] // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return x } @@ -48,7 +48,7 @@ func f2(a []int) int { func f4(a [10]int) int { x := 0 for i := 0; i < len(a); i += 2 { // ERROR "Induction variable: limits \[0,10\), increment 2$" - x += a[i] // ERROR "Proved IsInBounds$" + x += a[i] // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return x } @@ -63,7 +63,7 @@ func f5(a [10]int) int { func f6(a []int) { for i := range a { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - b := a[0:i] // ERROR "Proved IsSliceInBounds$" + b := a[0:i] // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" "(\([0-9]+\) )?Proved Geq64$" f6(b) } } @@ -71,7 +71,7 @@ func f6(a []int) { func g0a(a string) int { x := 0 for i := 0; i < len(a); i++ { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - x += int(a[i]) // ERROR "Proved IsInBounds$" + x += int(a[i]) // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return x } @@ -79,7 +79,7 @@ func g0a(a string) int { func g0b(a string) int { x := 0 for i := 0; len(a) > i; i++ { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - x += int(a[i]) // ERROR "Proved IsInBounds$" + x += int(a[i]) // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return x } @@ -87,7 +87,7 @@ func g0b(a string) int { func g0c(a string) int { x := 0 for i := len(a); i > 0; i-- { // ERROR "Induction variable: limits \(0,\?\], increment 1$" - x += int(a[i-1]) // ERROR "Proved IsInBounds$" + x += int(a[i-1]) // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return x } @@ -95,7 +95,7 @@ func g0c(a string) int { func g0d(a string) int { x := 0 for i := len(a); 0 < i; i-- { // ERROR "Induction variable: limits \(0,\?\], increment 1$" - x += int(a[i-1]) // ERROR "Proved IsInBounds$" + x += int(a[i-1]) // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return x } @@ -103,7 +103,7 @@ func g0d(a string) int { func g0e(a string) int { x := 0 for i := len(a) - 1; i >= 0; i-- { // ERROR "Induction variable: limits \[0,\?\], increment 1$" - x += int(a[i]) // ERROR "Proved IsInBounds$" + x += int(a[i]) // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return x } @@ -111,7 +111,7 @@ func g0e(a string) int { func g0f(a string) int { x := 0 for i := len(a) - 1; 0 <= i; i-- { // ERROR "Induction variable: limits \[0,\?\], increment 1$" - x += int(a[i]) // ERROR "Proved IsInBounds$" + x += int(a[i]) // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return x } @@ -120,7 +120,7 @@ func g1() int { a := "evenlength" x := 0 for i := 0; i < len(a); i += 2 { // ERROR "Induction variable: limits \[0,10\), increment 2$" - x += int(a[i]) // ERROR "Proved IsInBounds$" + x += int(a[i]) // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return x } @@ -130,7 +130,7 @@ func g2() int { x := 0 for i := 0; i < len(a); i += 2 { // ERROR "Induction variable: limits \[0,10\), increment 2$" j := i - if a[i] == 'e' { // ERROR "Proved IsInBounds$" + if a[i] == 'e' { // ERROR "(\([0-9]+\) )?Proved IsInBounds$" j = j + 1 } x += int(a[j]) @@ -141,27 +141,27 @@ func g2() int { func g3a() { a := "this string has length 25" for i := 0; i < len(a); i += 5 { // ERROR "Induction variable: limits \[0,25\), increment 5$" - useString(a[i:]) // ERROR "Proved IsSliceInBounds$" + useString(a[i:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" useString(a[:i+3]) } } func g3b(a string) { for i := 0; i < len(a); i++ { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - useString(a[i+1:]) // ERROR "Proved IsSliceInBounds$" + useString(a[i+1:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" } } func g3c(a string) { for i := 0; i < len(a); i++ { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - useString(a[:i+1]) // ERROR "Proved IsSliceInBounds$" + useString(a[:i+1]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" } } func h1(a []byte) { c := a[:128] for i := range c { // ERROR "Induction variable: limits \[0,128\), increment 1$" - c[i] = byte(i) // ERROR "Proved IsInBounds$" + c[i] = byte(i) // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } } @@ -174,11 +174,11 @@ func h2(a []byte) { func k0(a [100]int) [100]int { for i := 10; i < 90; i++ { // ERROR "Induction variable: limits \[10,90\), increment 1$" a[i-11] = i - a[i-10] = i // ERROR "Proved IsInBounds$" - a[i-5] = i // ERROR "Proved IsInBounds$" - a[i] = i // ERROR "Proved IsInBounds$" - a[i+5] = i // ERROR "Proved IsInBounds$" - a[i+10] = i // ERROR "Proved IsInBounds$" + a[i-10] = i // ERROR "(\([0-9]+\) )?Proved IsInBounds$" + a[i-5] = i // ERROR "(\([0-9]+\) )?Proved IsInBounds$" + a[i] = i // ERROR "(\([0-9]+\) )?Proved IsInBounds$" + a[i+5] = i // ERROR "(\([0-9]+\) )?Proved IsInBounds$" + a[i+10] = i // ERROR "(\([0-9]+\) )?Proved IsInBounds$" a[i+11] = i } return a @@ -186,13 +186,13 @@ func k0(a [100]int) [100]int { func k1(a [100]int) [100]int { for i := 10; i < 90; i++ { // ERROR "Induction variable: limits \[10,90\), increment 1$" - useSlice(a[:i-11]) - useSlice(a[:i-10]) // ERROR "Proved IsSliceInBounds$" - useSlice(a[:i-5]) // ERROR "Proved IsSliceInBounds$" - useSlice(a[:i]) // ERROR "Proved IsSliceInBounds$" - useSlice(a[:i+5]) // ERROR "Proved IsSliceInBounds$" - useSlice(a[:i+10]) // ERROR "Proved IsSliceInBounds$" - useSlice(a[:i+11]) // ERROR "Proved IsSliceInBounds$" + useSlice(a[:i-11]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" + useSlice(a[:i-10]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" + useSlice(a[:i-5]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" + useSlice(a[:i]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" "(\([0-9]+\) )?Proved Geq64$" + useSlice(a[:i+5]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" + useSlice(a[:i+10]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" + useSlice(a[:i+11]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" useSlice(a[:i+12]) } @@ -202,12 +202,12 @@ func k1(a [100]int) [100]int { func k2(a [100]int) [100]int { for i := 10; i < 90; i++ { // ERROR "Induction variable: limits \[10,90\), increment 1$" useSlice(a[i-11:]) - useSlice(a[i-10:]) // ERROR "Proved IsSliceInBounds$" - useSlice(a[i-5:]) // ERROR "Proved IsSliceInBounds$" - useSlice(a[i:]) // ERROR "Proved IsSliceInBounds$" - useSlice(a[i+5:]) // ERROR "Proved IsSliceInBounds$" - useSlice(a[i+10:]) // ERROR "Proved IsSliceInBounds$" - useSlice(a[i+11:]) // ERROR "Proved IsSliceInBounds$" + useSlice(a[i-10:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" + useSlice(a[i-5:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" + useSlice(a[i:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" + useSlice(a[i+5:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" + useSlice(a[i+10:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" + useSlice(a[i+11:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" useSlice(a[i+12:]) } return a @@ -216,7 +216,7 @@ func k2(a [100]int) [100]int { func k3(a [100]int) [100]int { for i := -10; i < 90; i++ { // ERROR "Induction variable: limits \[-10,90\), increment 1$" a[i+9] = i - a[i+10] = i // ERROR "Proved IsInBounds$" + a[i+10] = i // ERROR "(\([0-9]+\) )?Proved IsInBounds$" a[i+11] = i } return a @@ -225,7 +225,7 @@ func k3(a [100]int) [100]int { func k3neg(a [100]int) [100]int { for i := 89; i > -11; i-- { // ERROR "Induction variable: limits \(-11,89\], increment 1$" a[i+9] = i - a[i+10] = i // ERROR "Proved IsInBounds$" + a[i+10] = i // ERROR "(\([0-9]+\) )?Proved IsInBounds$" a[i+11] = i } return a @@ -234,7 +234,7 @@ func k3neg(a [100]int) [100]int { func k3neg2(a [100]int) [100]int { for i := 89; i >= -10; i-- { // ERROR "Induction variable: limits \[-10,89\], increment 1$" a[i+9] = i - a[i+10] = i // ERROR "Proved IsInBounds$" + a[i+10] = i // ERROR "(\([0-9]+\) )?Proved IsInBounds$" a[i+11] = i } return a @@ -243,16 +243,16 @@ func k3neg2(a [100]int) [100]int { func k4(a [100]int) [100]int { min := (-1) << 63 for i := min; i < min+50; i++ { // ERROR "Induction variable: limits \[-9223372036854775808,-9223372036854775758\), increment 1$" - a[i-min] = i // ERROR "Proved IsInBounds$" + a[i-min] = i // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return a } func k5(a [100]int) [100]int { max := (1 << 63) - 1 - for i := max - 50; i < max; i++ { // ERROR "Induction variable: limits \[9223372036854775757,9223372036854775807\), increment 1" - a[i-max+50] = i // ERROR "Proved IsInBounds$" - a[i-(max-70)] = i // ERROR "Proved IsInBounds$" + for i := max - 50; i < max; i++ { // ERROR "Induction variable: limits \[9223372036854775757,9223372036854775807\), increment 1$" + a[i-max+50] = i // ERROR "(\([0-9]+\) )?Proved IsInBounds$" + a[i-(max-70)] = i // ERROR "(\([0-9]+\) )?Proved IsInBounds$" } return a } @@ -275,17 +275,17 @@ func nobce1() { func nobce2(a string) { for i := int64(0); i < int64(len(a)); i++ { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - useString(a[i:]) // ERROR "Proved IsSliceInBounds$" + useString(a[i:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" } for i := int64(0); i < int64(len(a))-31337; i++ { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - useString(a[i:]) // ERROR "Proved IsSliceInBounds$" + useString(a[i:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" } for i := int64(0); i < int64(len(a))+int64(-1<<63); i++ { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - useString(a[i:]) // ERROR "Proved IsSliceInBounds$" + useString(a[i:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" } j := int64(len(a)) - 123 for i := int64(0); i < j+123+int64(-1<<63); i++ { // ERROR "Induction variable: limits \[0,\?\), increment 1$" - useString(a[i:]) // ERROR "Proved IsSliceInBounds$" + useString(a[i:]) // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" } for i := int64(0); i < j+122+int64(-1<<63); i++ { // ERROR "Induction variable: limits \[0,\?\), increment 1$" // len(a)-123+122+MinInt overflows when len(a) == 0, so a bound check is needed here diff --git a/test/prove.go b/test/prove.go index 79256893b3..0de6bd63b4 100644 --- a/test/prove.go +++ b/test/prove.go @@ -62,7 +62,7 @@ func f1c(a []int, i int64) int { } func f2(a []int) int { - for i := range a { // ERROR "Induction variable: limits \[0,\?\), increment 1" + for i := range a { // ERROR "Induction variable: limits \[0,\?\), increment 1$" a[i+1] = i a[i+1] = i // ERROR "Proved IsInBounds$" } @@ -269,7 +269,7 @@ func f11b(a []int, i int) { func f11c(a []int, i int) { useSlice(a[:i]) - useSlice(a[:i]) // ERROR "Proved IsSliceInBounds$" + useSlice(a[:i]) // ERROR "Proved Geq64$" "Proved IsSliceInBounds$" } func f11d(a []int, i int) { @@ -464,12 +464,12 @@ func f16(s []int) []int { } func f17(b []int) { - for i := 0; i < len(b); i++ { // ERROR "Induction variable: limits \[0,\?\), increment 1" + for i := 0; i < len(b); i++ { // ERROR "Induction variable: limits \[0,\?\), increment 1$" // This tests for i <= cap, which we can only prove // using the derived relation between len and cap. // This depends on finding the contradiction, since we // don't query this condition directly. - useSlice(b[:i]) // ERROR "Proved IsSliceInBounds$" + useSlice(b[:i]) // ERROR "Proved Geq64$" "Proved IsSliceInBounds$" } } @@ -579,18 +579,18 @@ func fence4(x, y int64) { func trans1(x, y int64) { if x > 5 { if y > x { - if y > 2 { // ERROR "Proved Greater64" + if y > 2 { // ERROR "Proved Greater64$" return } } else if y == x { - if y > 5 { // ERROR "Proved Greater64" + if y > 5 { // ERROR "Proved Greater64$" return } } } if x >= 10 { if y > x { - if y > 10 { // ERROR "Proved Greater64" + if y > 10 { // ERROR "Proved Greater64$" return } } @@ -624,7 +624,7 @@ func natcmp(x, y []uint) (r int) { } i := m - 1 - for i > 0 && // ERROR "Induction variable: limits \(0,\?\], increment 1" + for i > 0 && // ERROR "Induction variable: limits \(0,\?\], increment 1$" x[i] == // ERROR "Proved IsInBounds$" y[i] { // ERROR "Proved IsInBounds$" i-- @@ -686,7 +686,7 @@ func range2(b [][32]int) { if i < len(b) { // ERROR "Proved Less64$" println("x") } - if i >= 0 { // ERROR "Proved Geq64" + if i >= 0 { // ERROR "Proved Geq64$" println("x") } } diff --git a/test/run.go b/test/run.go index 99ef79feb1..5a81da8d67 100644 --- a/test/run.go +++ b/test/run.go @@ -1180,7 +1180,7 @@ func (t *test) updateErrors(out, file string) { msg := errStr[colon2+2:] msg = strings.Replace(msg, file, base, -1) // normalize file mentions in error itself msg = strings.TrimLeft(msg, " \t") - for _, r := range []string{`\`, `*`, `+`, `[`, `]`, `(`, `)`} { + for _, r := range []string{`\`, `*`, `+`, `?`, `[`, `]`, `(`, `)`} { msg = strings.Replace(msg, r, `\`+r, -1) } msg = strings.Replace(msg, `"`, `.`, -1) -- 2.48.1