go: cmd/compile: compiler can unexpectedly preserve memory

Please answer these questions before submitting your issue. Thanks!

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

go1.9.1

Does this issue reproduce with the latest release?

yes. every release.

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

GOARCH=amd64 GOBIN=C:\Go\bin GOEXE=.exe GOHOSTARCH=amd64 GOHOSTOS=windows GOOS=windows GOPATH=D:\golang GORACE= GOROOT=C:\Go GOTOOLDIR=C:\Go\pkg\tool\windows_amd64 GCCGO=gccgo CC=gcc GOGCCFLAGS=-m64 -fmessage-length=0 -fdebug-prefix-map=C:\Users\zhalei\AppData\Local\Temp\go-build309785515=/tmp/go-build -gno-record-gcc-switches CXX=g++ CGO_ENABLED=1 PKG_CONFIG=pkg-config CGO_CFLAGS=-g -O2 CGO_CPPFLAGS= CGO_CXXFLAGS=-g -O2 CGO_FFLAGS=-g -O2 CGO_LDFLAGS=-g -O2

What did you do?

Write codes for test GC of golang. Here is what i use to test.

package main

import "fmt"
import "time"

type Node struct {
	next     *Node
	payload  [64]byte
}

func main() {
	root := new(Node)
	curr := root
	i := 0
	
	lastTime := time.Now()
	for {
		currTime := time.Now()
		elapsed := currTime.Sub(lastTime)
		lastTime = currTime
		// 10ms = 10000000ns
		if elapsed > 10000000 {
			fmt.Println("StopTime:", elapsed)
		}
		
		curr.next = new(Node)
		curr = curr.next
		
		i++
		//3000 nodes max
		if i >= 3000 {
			i = 0
			root = curr
		}
	}
}

What did you expect to see?

the program run well.

What did you see instead?

memory never be released until everything stop work. and then, i take my pc power off. -_-

About this issue

  • Original URL
  • State: closed
  • Created 7 years ago
  • Reactions: 1
  • Comments: 68 (59 by maintainers)

Commits related to this issue

Most upvoted comments

Here is a smaller reproduction which grows linearly on my machine

package main

type Node struct {
        next    *Node
        payload [64]byte
}

func main() {
        curr := new(Node)
        for {
                curr.next = new(Node)
                curr = curr.next
        }
}

We need to be careful about using the word “correctness” here. Even with this bug, the program is still by some definition correct. And it takes a carefully written special case for this bug to manifest as using up all of memory. Of course we all agree that correctness takes priority over performance, but this program is not quite behaving incorrectly. It just has terrible and unacceptable side effects. It still must be fixed somehow, of course.

The solutions we’ve thought of so far would have drastic performance implications, and would cause far more bugs to be filed than this one. @cznic you suggest that we adopt @randall77 's suggestion, but he himself says that that “is liable to cause more problems than it solves.”

Of course, we can’t think of everything. Please do keep making suggestions for ways to address this.

@davecheney This bug could certainly cause some memory to be unexpectedly held across a loop. Even if we fix this bug, there will be other ways that that can happen. It’s true today, and it will be true after this bug is fixed, that there will be cases where the program will appear to have no references to some object but there will be live references that aren’t clearly visible in the program’s source. Think of it as the reverse of the problem described in the runtime.SetFinalizer docs. There isn’t a precise match between liveness in the source code and liveness in the generated code. Normally, that is fine. It takes a special case like this one to expose a problem.

The autotmp needs to potentially be kept alive even after the curr = curr.next assignment if it first gets copied into another non-escaping live value.

It seems like the crux of the issue is during escape analysis we currently only worry about whether a variable’s lifetime can exceed the function call. However, if it contains pointers, we really need to statically know exactly when it’s still live throughout the function, otherwise moving it to the stack potentially interferes with GC.

Google’s Go compiler and runtime folks met earlier today and we discussed this issue at some length. At the moment, we have some brainstorm-y ideas on how to address this (see below), but they all seem very expensive and would negatively impact other Go programs. For now, we’re going to keep this issue open until we have examples of this affecting real programs without easy workaround.

A few options tossed around:

  1. Always heap allocate variables that contain pointers and whose address are taken. This is safe and trivial to implement, but would drastically hinder the effectiveness of escape analysis.

  2. Unified escape analysis and liveness tracking. If we could precisely determine a stack-allocated object’s lifetime, we could set the stackmaps correctly. Then only ambiguously-live objects need to be heap allocated. However, 1) escape analysis and liveness tracking are already two of the more complicated and subtle parts of the compiler, and 2) they run at entirely different stages of the compiler (escape analysis is before SSA begins, liveness is after SSA ends), so it’s unclear how or even if this would work.

  3. Partial GC scanning of stacks. Instead of recording stack autotmps’ liveness in stackmaps, we could leave it up to GC to identify them and trace them out. This would require the compiler to generate additional stackmap-like data structures, and additional GC algorithms for scanning stacks.

@ianlancetaylor thanks for the explanation. I think, irrespective of if this comes up in real code or not, it’s still quite a serious bug.

Here’s the program:

package main

import (
	"fmt"
	"go/ast"
	"go/parser"
	"go/token"
	"os"
)

func main() {
	for _, pkg := range os.Args[1:] {
		doPkg(pkg)
	}
}

func doPkg(pkg string) {
	fset := token.NewFileSet()
	pkgs, err := parser.ParseDir(fset, pkg, func(os.FileInfo) bool { return true }, 0)
	if err != nil {
		panic(err)
	}
	for _, p := range pkgs {
		for _, f := range p.Files {
			for _, d := range f.Decls {
				if fn, ok := d.(*ast.FuncDecl); ok {
					checkFn(fn, fset)
				}
			}
		}
	}
}

func checkFn(fn *ast.FuncDecl, fset *token.FileSet) {
	// Count number of assignments to each variable.
	assignments := map[*ast.Object]int{}
	ast.Inspect(fn, func(n ast.Node) bool {
		switch x := n.(type) {
		case *ast.AssignStmt:
			for _, y := range x.Lhs {
				if id, ok := y.(*ast.Ident); ok {
					assignments[id.Obj]++
				}
			}
		}
		return true
	})

	ast.Inspect(fn, func(n ast.Node) bool {
		switch x := n.(type) {
		case *ast.AssignStmt:
			for i, r := range x.Rhs {
				c, ok := r.(*ast.CallExpr)
				if !ok {
					continue
				}
				name, ok := c.Fun.(*ast.Ident)
				if !ok {
					continue
				}
				if name.Name != "new" {
					continue
				}
				l := x.Lhs[i]
				if id, ok := l.(*ast.Ident); ok && assignments[id.Obj] > 1 {
					fmt.Printf("%s %s XXX\n", fset.Position(x.TokPos).String()[28:], id)
				}
			}
		}
		return true
	})
}

(Replace 28 with the right constant for your current working directory.)

Get the list of std packages with

go list ./... | cut -d_ -f2- > pkgs

Run the program above with

cat pkgs | xargs ./program > log

Find all the non-escaping allocations in the std lib

GO_GCFLAGS=-m ./make.bash 2>&1 | cat > log2

Merge the results and find matching positions:

cat log log2 | sort | grep -C1 XXX

From the output you can eyeball all of the places where the assignments match a “does not escape” message.

Yes, this looks pretty unfortunate.

We might consider disabling stack allocation for x := new(...) if there is any reassignment of x elsewhere in the function (or just in a loop?). That seems pretty harsh, though, and is liable to cause more problems than it solves.

naive question: given @randall77’s code, is this being considered for go vet?

Two different workarounds, for the original program.

package main

import "fmt"
import "time"

type Node struct {
	next    *Node
	payload [64]byte
}

var sink *Node // Workaround #1, part 1 of 3

func main() {
	root := new(Node)
	sink = root   // Workaround #1, part 2 of 3
	sink = nil    // Workaround #1, part 3 of 3
	root0 := root // Workaround #2, part 1 of 2
	curr := root
	i := 0

	lastTime := time.Now()
	for {
		currTime := time.Now()
		elapsed := currTime.Sub(lastTime)
		lastTime = currTime
		// 10ms = 10000000ns
		if elapsed > 10000000 {
			fmt.Println("StopTime:", elapsed)
		}

		curr.next = new(Node)
		curr = curr.next

		i++
		//3000 nodes max
		if i >= 3000 {
			i = 0
			root = curr
			root0.next = nil // Workaround #2, part 2 of 2
		}
	}
}

Shouldn’t this be considered a liveness issue (bug)? If I understand this correctly, using @davecheney simpler example, curr gets split into into variables as a side-effect of the escape analysis, one of which really is not live anymore after the 2nd assignment to curr, but that information is somehow lost when translating to SSA. So perhaps there needs to be some explicit “kill” information flowing into the construction of the SSA when a so-duplicated variable becomes dead. Presumably this situation can happen anytime a variable containing pointers gets “duplicated”.

Ah, Sorry, I was confused. 😦

This code doesn’t have top of the chain. So un-referenced curr should be garbage-collected.