cmd/compile: fatal error: out of memory on reslice with negative index

[alistanis]

What version of Go are you using (go version)?

$ go version
go version go1.11.2 darwin/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/ccooper/Library/Caches/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOOS="darwin"
GOPATH="/Users/ccooper/work/polaris"
GOPROXY=""
GORACE=""
GOROOT="/usr/local/go"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/darwin_amd64"
GCCGO="gccgo"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/kz/p8_8brl12k1gjbc79cjvpdtr0000gn/T/go-build092783061=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

Performed a reslice with a negative index.

https://play.golang.org/p/6TIXJwN55zR

What did you expect to see?

1
-1
panic: runtime error: slice bounds out of range

What did you see instead?

1
-1
fatal error: out of memory

runtime stack:
runtime.throw(0x10c30b4, 0xd)
/usr/local/go/src/runtime/panic.go:608 +0x72
runtime.largeAlloc(0xfffffffffffffffe, 0x1040100, 0x11be000)
/usr/local/go/src/runtime/malloc.go:1007 +0x181
runtime.mallocgc.func1()
/usr/local/go/src/runtime/malloc.go:914 +0x46
runtime.systemstack(0x0)
/usr/local/go/src/runtime/asm_amd64.s:351 +0x66
runtime.mstart()
/usr/local/go/src/runtime/proc.go:1229

goroutine 1 [running]:
runtime.systemstack_switch()
/usr/local/go/src/runtime/asm_amd64.s:311 fp=0xc00007ae18 sp=0xc00007ae10 pc=0x104eae0
runtime.mallocgc(0xfffffffffffffffe, 0x0, 0x0, 0x0)
/usr/local/go/src/runtime/malloc.go:913 +0x896 fp=0xc00007aeb8 sp=0xc00007ae18 pc=0x100aaa6
runtime.slicebytetostring(0x0, 0xc000014099, 0xfffffffffffffffe, 0x7, 0x0, 0x0)
/usr/local/go/src/runtime/string.go:102 +0x9f fp=0xc00007aee8 sp=0xc00007aeb8 pc=0x103e9af
main.main()
/Users/ccooper/work/polaris/src/github.com/alistanis/oom/main.go:12 +0x173 fp=0xc00007af98 sp=0xc00007aee8 pc=0x10910c3
runtime.main()
/usr/local/go/src/runtime/proc.go:201 +0x207 fp=0xc00007afe0 sp=0xc00007af98 pc=0x10287c7
runtime.goexit()
/usr/local/go/src/runtime/asm_amd64.s:1333 +0x1 fp=0xc00007afe8 sp=0xc00007afe0 pc=0x1050a21
exit status 2

I would expect this to fail in either case, but I was surprised by the error message. I found it when I mistakenly missed a bounds check on a reslice and thought I had actually reached an out of memory issue - the machine I was using had ~200MB of free RAM so I thought that was actually the case at first.

[randall77]

Your playground link doesn't work. Could you paste the code here directly?

[alistanis]

My apologies:

https://play.golang.org/p/6TIXJwN55zR

package main

import (
"fmt"
)

func main() {
	b := make([]byte, 0)
	b = append(b, 1)
	fmt.Println(len(b))
	fmt.Println(len(b) - 2)
	s := string(b[1:len(b) - 2])
	fmt.Println(s)
}

[randall77]

Indeed, looks bad.
The bug starts with 1.11, 1.10 and earlier work correctly.

[alistanis]

@randall77 thanks for confirming so quickly 👍

[randall77]

Looks like the prove pass is removing the bounds check incorrectly.
@brtzsnr @rasky

[randall77]

@gopherbot, please open a backport issue for 1.11.

[gopherbot]

Backport issue(s) opened: #28799 (for 1.11).

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

[go101]

mac only? Why is this OS dependent?

[go101]

It looks it is ok for Go 1.11.2 on Linux amd64, but bad for Go 1.11 and 1.11.1 on Linux amd64.

[randall77]

It fails for me on 1.11, 1.11.1, 1.11.2, and tip on both linux and darwin.

[go101]

Ah, yes, you are right.
I forgot I temporarily set Go 1.9 as the default Go version and misthought it was 1.11.2. :)

[DenWav]

Via git bisect, e0d37a3 introduced this bug.

[odeke-em]

Thanks for the bisection @DemonWav!

Kindly paging @rasky @dr2chase @josharian

[dr2chase]

If this is like the last one, (un)signedness is involved.
Not looking at this quite yet.

[gopherbot]

Change https://golang.org/cl/151978 mentions this issue: cmd/compile: working on bug 28797, important logging change

[dr2chase]

@randall77, wouldn't mind your opinion on this.
Root cause seems to actually be not in prove.go.
If you look at the description for OpIsSliceInBounds, it says:

{name: "IsSliceInBounds", argLength: 2, typ: "Bool"}, // 0 <= arg0 <= arg1. arg1 is guaranteed >= 0.

and we generate code based on that assumption, using an unsigned comparison -- this will fail if AX below happens to be a negative number (and of course it is).

v149 00090 (+12) MOVQ	""..autotmp_55-72(SP), AX
v156 00091 (12) CMPQ	AX, $1
b11 .  00092 (12) JCS	142

The source code is

s := string(b[1 : len(b)-2])

I think our two choices for fixing this are either to remove the assumption from prove, or in ssa.go to catch the case where arg1 of OpIsSliceInBounds might be negative and explicitly check for that.

I favor the explicit extra check, since as it happens we compile this to code that would not do the correct thing if fed a negative number. Here's another test case making the trick more explicit:

package main

import (
	"fmt"
)

//go:noinline
func id(x int) int {
	return x
}

func main() {
	b := make([]byte, 1)
	b = append(b, 1)
	i := id(-1)
	if i < len(b) {
		s := string(b[1:i])
		fmt.Println(s)
	}
}

One possibility for improving code for the unoptimized case is to only insert the extra explicit test when phase "prove" is enabled.

[gopherbot]

Change https://golang.org/cl/152477 mentions this issue: cmd/compile: check for negative upper bound to IsSliceInBounds

[alistanis]

Thanks guys!

[gopherbot]

Change https://golang.org/cl/166377 mentions this issue: cmd/compile: reverse order of slice bounds checks