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: big array not allocated on heap, which make program panic. #20021

Open
go101 opened this issue Apr 18, 2017 · 23 comments
Open

cmd/compile: big array not allocated on heap, which make program panic. #20021

go101 opened this issue Apr 18, 2017 · 23 comments
Labels
Milestone

Comments

@go101
Copy link

@go101 go101 commented Apr 18, 2017

Please answer these questions before submitting your issue. Thanks!

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

go version go1.8.1 linux/amd64

What did you do?

package main

const N = 1000 * 1000 * 537
var a [N]byte

func main() {
	// this will stack overflow
	for _, v := range a {
	  _ = v
	}

	// edit: blow solo also stack overflow
	var x [N]byte
	var y [N]byte
	_, _ = x, y
}

[edit]: now(Go SDK 1.12.2), the above program doesn't crash. But below @agnivade shows one case which will still crash.

What did you expect to see?

runs ok

What did you see instead?

crash

runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

runtime stack:
runtime.throw(0x469cdc, 0xe)
	/sdks/go/src/runtime/panic.go:596 +0x95
runtime.newstack(0x0)
	/sdks/go/src/runtime/stack.go:1089 +0x3f2
runtime.morestack()
	/sdks/go/src/runtime/asm_amd64.s:398 +0x86

goroutine 1 [running]:
main.main()
	/tmp/main.go:6 +0x88 fp=0xc460057f88 sp=0xc460057f80
runtime.main()
	/sdks/go/src/runtime/proc.go:185 +0x20a fp=0xc460057fe0 sp=0xc460057f88
runtime.goexit()
	/sdks/go/src/runtime/asm_amd64.s:2197 +0x1 fp=0xc460057fe8 sp=0xc460057fe0
exit status 2
@mvdan
Copy link
Member

@mvdan mvdan commented Apr 18, 2017

Worth noting that the spec does not talk of heap nor stack, so if this is a bug it would likely be a compiler one.

Did you try forcing an allocation at run-time, like a := make([]byte, 1000 * 1000 * 537)?

Loading

@ianlancetaylor ianlancetaylor changed the title big array not allocated on heap, which make program panic. cmd/compile: big array not allocated on heap, which make program panic. Apr 18, 2017
@ianlancetaylor ianlancetaylor added this to the Go1.9Maybe milestone Apr 18, 2017
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Apr 18, 2017

Loading

@go101
Copy link
Author

@go101 go101 commented Apr 18, 2017

@mvdan

package main

const N = 1000 * 1000 * 537

func main() {
	// make is ok
	p := make([]byte, N)
	q := make([]byte, N)
	_, _ = p, q

	// new is also ok
	var u = new([N]byte)
	var v = new([N]byte)
	_, _ = u, v
	
	// blow also stack overflow
	var x [N]byte
	var y [N]byte
	_, _ = x, y
}

Loading

@josharian
Copy link
Contributor

@josharian josharian commented Apr 18, 2017

Related: #10936 and comments on CL 10268.

cc @dr2chase for escape analysis

Loading

@valyala
Copy link
Contributor

@valyala valyala commented Apr 18, 2017

package main

const N = 1000 * 1000 * 537
var a [N]byte

func main() {
	for _, v := range a {
	  _ = v
	}
}

This is a typical trap that the #19817 should address. The workaround is to rewrite the line with range to:

	for _, v := range a[:] {

Loading

@bradfitz bradfitz removed this from the Go1.9Maybe milestone Jul 20, 2017
@bradfitz bradfitz added this to the Go1.10 milestone Jul 20, 2017
@bradfitz bradfitz added this to the Go1.10 milestone Jul 20, 2017
@bradfitz bradfitz removed this from the Go1.9Maybe milestone Jul 20, 2017
@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Nov 29, 2017

Go tip (as of 992ce90) has a better error message:

$ go run x.go
# command-line-arguments
./x.go:6:6: stack frame too large (>1GB)

So, some progress. But bumping to Go 1.11.

Loading

@bradfitz bradfitz removed this from the Go1.10 milestone Nov 29, 2017
@bradfitz bradfitz added this to the Go1.11 milestone Nov 29, 2017
@gopherbot gopherbot removed this from the Go1.11 milestone May 23, 2018
@gopherbot gopherbot added this to the Unplanned milestone May 23, 2018
@agnivade
Copy link
Contributor

@agnivade agnivade commented Apr 10, 2019

As of Go 1.12, it does not crash if the code is

	for _, v := range a {
		_ = v
	}

But if the variable is assigned to something else and printed later -

package main

import "fmt"

const N = 1000 * 1000 * 537

var a [N]byte
var tmp byte

func main() {
	for _, v := range a {
		tmp = v
	}
	fmt.Println(tmp)
}

it goes back to the original error

runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

runtime stack:
runtime.throw(0x4b917b, 0xe)
	/usr/local/go/src/runtime/panic.go:617 +0x72
runtime.newstack()
	/usr/local/go/src/runtime/stack.go:1041 +0x6f0
runtime.morestack()
	/usr/local/go/src/runtime/asm_amd64.s:429 +0x8f

goroutine 1 [running]:
main.main()
	/home/agniva/play/go/src/bigint.go:10 +0xfa fp=0xc043ffff98 sp=0xc043ffff90 pc=0x486aba
runtime.main()
	/usr/local/go/src/runtime/proc.go:200 +0x20c fp=0xc043ffffe0 sp=0xc043ffff98 pc=0x4294ec
runtime.goexit()
	/usr/local/go/src/runtime/asm_amd64.s:1337 +0x1 fp=0xc043ffffe8 sp=0xc043ffffe0 pc=0x450ad1
exit status 2

Same behavior with tip (go version devel +f947c4dcfe Fri Apr 5 00:52:55 2019 +0000 linux/amd64)

Loading

@randall77
Copy link
Contributor

@randall77 randall77 commented Apr 10, 2019

I believe this is, or is closely related to, #27447.

Loading

@go101
Copy link
Author

@go101 go101 commented Oct 19, 2020

It looks this problem has already been fixed. Anyone may close it if it is verified.

Loading

@go101
Copy link
Author

@go101 go101 commented Jun 25, 2021

It looks there are still some cases which might be hard to detected at compile time.
In the following example, large array arguments passed to interface{} parameters will be still allocated on stack.

An example:

package main

const N = 1000 * 1000 * 100
var a [N]byte

var n int

func g(x interface{}, n int) {
	type _ int // avoid g being inlined
	if n > 0 {
		var y = a // moved to heap: y
		g(y, n-1) // y does not escape
	}
}

func main() {
	var x = a // moved to heap: x
	g(x, 4) // x does not escape
}

But the following program doesn't overflow stack:

package main

const N = 1000 * 1000 * 100
var a [N]byte

var n int

func g(x interface{}, n int) {
	type _ int // avoid g being inlined
	if n > 0 {
		g(a, n-1) // a does not escape
	}
}

func main() {
	g(a, 100) // a does not escape
}

Loading

@go101
Copy link
Author

@go101 go101 commented Jun 25, 2021

A simpler one, which almost makes my 8g notetbook hang.

package main

const N = 1000 * 1000 * 513
var a [N]byte

func g(vs ...interface{}) {
	type _ int // avoid g being inlined
	println(len(vs))
}

func main() {
	g(a, a, a, a, a)
}

Loading

@davecheney
Copy link
Contributor

@davecheney davecheney commented Jun 25, 2021

Every assignment in Go is a copy, passing a into g five times is going to make 5 copies of a on the heap, which will also require paging a into ram each time to copy from it. I’d say the heap would probably grow to at least 5Gb during this process.

It would be interesting to see the output of env GODEBUG=gctrace=1

Loading

@go101
Copy link
Author

@go101 go101 commented Jun 25, 2021

It would be better to allocate the 5 copies of a to heap.
In fact, this is the intention of this issue.

However, go build -gcflags=-m shows the 5 copies are allocated on stack (go1.17beta1).

It looks the gc compiler has changed the strategy much since version 1.8.
For example, the x and y variables will be allocated heap by the recent compiler versions (they they were allocated on stack by version 1.8).
But there are still some missing scenarios in which big arrays should be allocated on heap, such as the scenario described in the last example.

Loading

@go101
Copy link
Author

@go101 go101 commented Jun 25, 2021

BTW, maybe the compiler should make an optimization for g(a, a, a, a, a), by rewriting it as

var i interface{} = a
g(i, i, i, i, i)

Loading

@davecheney
Copy link
Contributor

@davecheney davecheney commented Jun 25, 2021

However, go build -gcflags=-m shows the 5 copies are allocated on stack (go1.17beta1).

I think this might be a reporting error, 512mb values are too large for the stack.

Loading

@go101
Copy link
Author

@go101 go101 commented Jun 25, 2021

You are right, which could be proved by the following code.
It looks the stack never grew.

package main

import t "testing"

const N = 1000 * 1000 * 1 // 513
var a [N]byte
var k int

func g(vs ...interface{}) {
	type _ int // avoid g being inlined
	_ = vs[k]
}

func main() {
	var y int
	println(&y) // 0xc000045f60
	x := t.AllocsPerRun(1, func() {
		g(a, a, a, a)
	})
	println(int(x)) // 4
	println(&y) // 0xc000045f60
}

One wired thing is, if g(a, a, a, a) is changed to g(a, a, a), then it prints 5 instead of 3.

Loading

@go101
Copy link
Author

@go101 go101 commented Jun 25, 2021

So many weird things in the following code:

package main

import t "testing"

const N = 1000 * 1000 * 100
var a [N]byte

var n int

func g(x interface{}, n int) {
	type _ int // avoid g being inlined
	var y = a // moved to heap: y
	if n > 0 {
		g(y, n-1) // y does not escape
		panic("unreachable")
	}
}

func main() {
	var x int
	println(&x) // 0xc000045f68
	z := t.AllocsPerRun(1, func() {
		g(nil, 0)
	})
	println(int(z)) // 2
	println(&x) // 0xc00dffbf68
}

Weirdness 1: why 2 allocations in the call g(nil, 0), I could only find one: var y = a
Weirdness 2: change g(nil, 0) to g(a, 0), there are still 2 allocations. Doesn't passing the argument a cause a new allocation?
Weirdness 3: if all allocations happen on heap, why does the stack grow? (which is reflected by the address change of x).
Weirdness 4: if the order of g(y, n-1) and panic("unreachable") is reversed, then the stack doesn't grow, and

  • when g(nil, 0) is called, there is only one allocation.
  • when g(a, 0) is called, there are 3 allocations.

Loading

@randall77
Copy link
Contributor

@randall77 randall77 commented Jun 25, 2021

Weirdness 1: why 2 allocations in the call g(nil, 0), I could only find one: var y = a

I only get 1 when I run your code. (There is a second allocation site for converting y to an interface{} in the recursive call, but that doesn't get executed because n==0.)

Weirdness 3: if all allocations happen on heap, why does the stack grow? (which is reflected by the address change of x).

Probably because t.AllocsPerRun uses a bunch of stack. Rename main to main2 and introduce a new main which calls main2 twice. See what happens then.

Loading

@go101
Copy link
Author

@go101 go101 commented Jun 25, 2021

I only get 1 when I run your code.

It is always 2 on my machine. But if I change the first argument of AllocsPerRun to a value larger than 1, then it is always 1.

Rename main to main2 and introduce a new main which calls main2 twice. See what happens then.

It prints:

0xc000045f58
2
0xc010093f58
0xc010093f58
1
0xc010093f58

The second run only allocates once.

If I add a runtime.GC() call between the two main2() calls, then it prints:

0xc000093f58
2
0xc01409ff58
0xc0020bff58
1
0xc01801ff58

Loading

@go101
Copy link
Author

@go101 go101 commented Jun 25, 2021

Probably because t.AllocsPerRun uses a bunch of stack.

Remove the t.AllocsPerRun call and call g(nil, 0) directly still makes stack grow.

Loading

@martisch
Copy link
Contributor

@martisch martisch commented Jun 25, 2021

However, go build -gcflags=-m shows the 5 copies are allocated on stack (go1.17beta1).

Note that "a does not escape" AFAIK does not mean there is an allocation on the stack.

By looking at go tool objdump -s main BINARYNAME I dont think a in the example is allocated on the stack.

Each time a is put in an interface{} there runtime.convT2Enoptr is called which makes a copy of a to the heap.

Loading

@martisch
Copy link
Contributor

@martisch martisch commented Jun 25, 2021

Remove the t.AllocsPerRun call and call g(nil, 0) directly still makes stack grow.

g itself uses a huge amount of stack:
"".g STEXT size=229 args=0x18 locals=0x5f5e120 funcid=0x0

looking at GOSSAFUNC=g go build what I think could be happening is g(y, n-1) creates a copy of a on stack to then call runtime.convT2Enoptr to create a copy of it to the heap. Even when the branch is not taken go gc always reserves all the stack upfront for all possible branches and does not dynamically grow the stack within a function which would explain the stack growth even if the branch is not taken. Whether the copy of a on stack is needed to begin with is a valid question and this should likely be avoided by the compiler.

This would also explain why moving panic before g(y, n-1) avoids the stack growth. The compiler will not compile in the call for g knowing it is unreachable and therefore no copy of a is made.

00018 (+15) LEAQ ""..autotmp_3-100000000(SP), DI
00019 (15) MOVQ AX, SI
00020 (15) MOVL $12500000, CX
00021 (15) REP
00022 (15) MOVSQ
00023 (15) LEAQ type.[100000000]uint8(SB), AX
00024 (15) LEAQ ""..autotmp_3-100000000(SP), BX
00025 (15) PCDATA $1, $0
00026 (15) CALL runtime.convT2Enoptr(SB)
00027 (15) MOVQ "".n+16(SP), DX
00028 (15) LEAQ -1(DX), CX
00029 (15) CALL "".g(SB)

Loading

@go101
Copy link
Author

@go101 go101 commented Jun 29, 2021

The following program sometimes prints 1, sometimes prints 2 on my machine. AllocsPerRun(2, f) always returns 1.

package main

import "testing"

const N = 10 * 1024 * 1024 // 10M

func declare10Mplus1() {
	var a [N+1]byte // moved to heap: a
	_ = a
}

func main() {
	stat := func( f func() ) int {
		allocs := testing.AllocsPerRun(1, f)
		return int(allocs)
	}
	println(stat(declare10Mplus1))
}

Loading

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet