From 38e7177c949016c3d74411fa7ea1c300ae85c0fa Mon Sep 17 00:00:00 2001
From: =?utf8?q?Martin=20M=C3=B6hrmann?= <moehrmann@google.com>
Date: Thu, 13 Dec 2018 17:55:52 +0100
Subject: [PATCH] cmd/compile: fix length overflow when appending elements to a
 slice
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

Instead of testing len(slice)+numNewElements > cap(slice) use
uint(len(slice)+numNewElements) > uint(cap(slice)) to test
if a slice needs to be grown in an append operation.

This prevents a possible overflow when len(slice) is near the maximum
int value and the addition of a constant number of new elements
makes it overflow and wrap around to a negative number which is
smaller than the capacity of the slice.

Appending a slice to a slice with append(s1, s2...) already used
a uint comparison to test slice capacity and therefore was not
vulnerable to the same overflow issue.

Fixes: #29190

Change-Id: I41733895838b4f80a44f827bf900ce931d8be5ca
Reviewed-on: https://go-review.googlesource.com/c/154037
Run-TryBot: Martin Möhrmann <moehrmann@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
---
 src/cmd/compile/internal/gc/ssa.go |  4 ++--
 test/fixedbugs/issue29190.go       | 37 ++++++++++++++++++++++++++++++
 test/prove.go                      |  2 +-
 3 files changed, 40 insertions(+), 3 deletions(-)
 create mode 100644 test/fixedbugs/issue29190.go

diff --git a/src/cmd/compile/internal/gc/ssa.go b/src/cmd/compile/internal/gc/ssa.go
index dcb9841042..2eeea79ff9 100644
--- a/src/cmd/compile/internal/gc/ssa.go
+++ b/src/cmd/compile/internal/gc/ssa.go
@@ -2416,7 +2416,7 @@ func (s *state) append(n *Node, inplace bool) *ssa.Value {
 	// a := &s
 	// ptr, len, cap := s
 	// newlen := len + 3
-	// if newlen > cap {
+	// if uint(newlen) > uint(cap) {
 	//    newptr, len, newcap = growslice(ptr, len, cap, newlen)
 	//    vardef(a)       // if necessary, advise liveness we are writing a new a
 	//    *a.cap = newcap // write before ptr to avoid a spill
@@ -2454,7 +2454,7 @@ func (s *state) append(n *Node, inplace bool) *ssa.Value {
 	c := s.newValue1(ssa.OpSliceCap, types.Types[TINT], slice)
 	nl := s.newValue2(s.ssaOp(OADD, types.Types[TINT]), types.Types[TINT], l, s.constInt(types.Types[TINT], nargs))
 
-	cmp := s.newValue2(s.ssaOp(OGT, types.Types[TINT]), types.Types[TBOOL], nl, c)
+	cmp := s.newValue2(s.ssaOp(OGT, types.Types[TUINT]), types.Types[TBOOL], nl, c)
 	s.vars[&ptrVar] = p
 
 	if !inplace {
diff --git a/test/fixedbugs/issue29190.go b/test/fixedbugs/issue29190.go
new file mode 100644
index 0000000000..c0c4bb12b4
--- /dev/null
+++ b/test/fixedbugs/issue29190.go
@@ -0,0 +1,37 @@
+// 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 (
+	"strings"
+)
+
+type T struct{}
+
+const maxInt = int(^uint(0) >> 1)
+
+func main() {
+	s := make([]T, maxInt)
+	shouldPanic("cap out of range", func() { s = append(s, T{}) })
+	var oneElem = make([]T, 1)
+	shouldPanic("cap out of range", func() { s = append(s, oneElem...) })
+}
+
+func shouldPanic(str string, f func()) {
+	defer func() {
+		err := recover()
+		if err == nil {
+			panic("did not panic")
+		}
+		s := err.(error).Error()
+		if !strings.Contains(s, str) {
+			panic("got panic " + s + ", want " + str)
+		}
+	}()
+
+	f()
+}
diff --git a/test/prove.go b/test/prove.go
index 0de6bd63b4..a881b2d6e2 100644
--- a/test/prove.go
+++ b/test/prove.go
@@ -530,7 +530,7 @@ func fence1(b []int, x, y int) {
 	}
 	if len(b) < cap(b) {
 		// This eliminates the growslice path.
-		b = append(b, 1) // ERROR "Disproved Greater64$"
+		b = append(b, 1) // ERROR "Disproved Greater64U$"
 	}
 }
 
-- 
2.50.0