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.

Sign up for GitHub

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

Jump to bottom

cmd/compile: bad escape analysis for linked data structures captured in closure #13799

Closed
sqs opened this issue Jan 2, 2016 · 5 comments
Closed

cmd/compile: bad escape analysis for linked data structures captured in closure #13799

sqs opened this issue Jan 2, 2016 · 5 comments
Labels
FrozenDueToAge
Milestone
Go1.6

Comments

@sqs
Copy link

sqs commented Jan 2, 2016

What version of Go are you using (go version)? What operating system and processor architecture are you using?

  • Go 1.5.2 on darwin and linux amd64
  • Go 1.6beta1 on darwin and linux amd64

What did you do?

Run the following program:

package main

import "fmt"

func main() {
    // Just run test over and over again. This main func is just for
    // convenience; if test were the main func, we could also trigger
    // the panic just by running the program over and over again
    // (sometimes it takes 1 time, sometimes it takes ~4,000+).
    for iter := 0; ; iter++ {
        if iter%50 == 0 {
            fmt.Println(iter)
        }
        test(iter)
    }
}

func test(iter int) {

    const maxI = 500
    m := make(map[int][]int)

    // The panic seems to be triggered when m is modified inside a
    // closure that is both recursively called and reassigned to in a
    // loop.
    var fn func()
    for i := 0; i < maxI; i++ {
        j := 0
        fn = func() {
            m[i] = append(m[i], 0)
            if j < 25 {
                j++
                fn()
            }
        }
        fn()
    }

    if len(m) != maxI {
        panic(fmt.Sprintf("iter %d: maxI = %d, len(m) = %d", iter, maxI, len(m)))
    }
}

Note: The constants are not special; as long as they are sufficiently large (above ~5), the behavior is exhibited.

What did you expect to see?

The program should continue iterating indefinitely without triggering the panic at the end of func test, and indeed without panicking at all.

What did you see instead?

On Go 1.5.2 and Go 1.6beta1 on darwin-amd64 and linux-amd64, the panic at the bottom of func test is triggered after anywhere between 1 and 4,000 iterations. Sometimes some other panics are seen (see "Clues" below).

This is a possible compiler bug.

It continues iterating indefinitely without panics (as expected) on gccgo 4.9.1 on linux-amd64 and on GopherJS.

Thanks to @shurcooL for help in reproducing and isolating this issue.
@sqs
Copy link
Author

sqs commented Jan 2, 2016

Clues

If you move the var fn func() declaration to inside the loop, it reliably succeeds.

If you add the following before the if len(m) != maxI { check, it reliably succeeds.

v := fmt.Sprint(m)
_ = v

Also, sometimes instead of the usual panic at the end of func test, I see this panic:

...
1250
1300
fatal error: concurrent map read and map write

goroutine 1 [running]:
runtime.throw(0x118780, 0x21)
    /usr/local/go/src/runtime/panic.go:530 +0x90 fp=0xc8201c9ae0 sp=0xc8201c9ac8
runtime.mapaccess1_fast64(0xb7e60, 0xc820313d28, 0x1a, 0xfa0000c8201b8048)
    /usr/local/go/src/runtime/hashmap_fast.go:112 +0x5a fp=0xc8201c9b00 sp=0xc8201c9ae0
main.test.func1()
    /Users/sqs/src/sourcegraph.com/sourcegraph/srclib/qqqq.go:28 +0x63 fp=0xc8201c9b98 sp=0xc8201c9b00
main.test.func1()
    /Users/sqs/src/sourcegraph.com/sourcegraph/srclib/qqqq.go:31 +0x10f fp=0xc8201c9c30 sp=0xc8201c9b98
main.test(0x51c)
    /Users/sqs/src/sourcegraph.com/sourcegraph/srclib/qqqq.go:34 +0x1e3 fp=0xc8201c9ee0 sp=0xc8201c9c30
main.main()
    /Users/sqs/src/sourcegraph.com/sourcegraph/srclib/qqqq.go:13 +0x119 fp=0xc8201c9f60 sp=0xc8201c9ee0
runtime.main()
    /usr/local/go/src/runtime/proc.go:185 +0x2b0 fp=0xc8201c9fb0 sp=0xc8201c9f60
runtime.goexit()
    /usr/local/go/src/runtime/asm_amd64.s:1998 +0x1 fp=0xc8201c9fb8 sp=0xc8201c9fb0

I have also seen the following panic (less common):

SIGILL: illegal instruction
PC=0x9a2b m=0

goroutine 1 [running]:
runtime.mapassign1(0xc0740, 0xc8200bdd88, 0xc8201f7b30, 0xc8201f7b50)
    /usr/local/go/src/runtime/hashmap.go:446 +0x1fb fp=0xc8201f7af0 sp=0xc8201f7a48

@dmitshur
Copy link
Contributor

dmitshur commented Jan 2, 2016

I'll add some more details that haven't been mentioned already.

We've tried running with -race flag to enable race detector, and it did not catch issues. Which is not surprising since there's no concurrency in the sample program.

However, some of the panics/errors like "fatal error: concurrent map read and map write" make it sound as if concurrency is somehow involved.

Another note. Since func test operates on local variables only, it should be safe to run it concurrently (if I'm not mistaken):

for iter := 0; ; iter += 4 {
    if iter%48 == 0 {
        fmt.Println(iter)
    }
    go test(iter)
    go test(iter + 1)
    go test(iter + 2)
    test(iter + 3)
}

In my testing, doing that makes the gc compiler result in a panic much, much sooner (well under 50 iterations in most cases). The 2 other compilers I've tried (gccgo and gopherjs) continue to work without panics, so it's only gc compiler that is exhibiting this behavior.

@ianlancetaylor ianlancetaylor added this to the Go1.6 milestone Jan 2, 2016
@ianlancetaylor
Copy link
Contributor

CC @dr2chase

Could possibly be an escape analysis problem.

@dr2chase dr2chase self-assigned this Jan 2, 2016
@dr2chase
Copy link
Contributor

dr2chase commented Jan 4, 2016

This is weird.

Here's the escape report (-gcflags -m) for the failing version and not-failing version, with common
lines intended

drchase-macbookair:tmp drchase$ go build -gcflags -m b13799.go
# command-line-arguments
   ./b13799.go:41: iter escapes to heap
   ./b13799.go:41: maxI escapes to heap
   ./b13799.go:41: len(m) escapes to heap
./b13799.go:30: func literal escapes to heap
./b13799.go:30: func literal escapes to heap
./b13799.go:27: moved to heap: i
./b13799.go:31: &i escapes to heap
./b13799.go:29: moved to heap: j
./b13799.go:32: &j escapes to heap
./b13799.go:26: moved to heap: fn
./b13799.go:34: &fn escapes to heap
./b13799.go:30: func literal escapes to heap
./b13799.go:30: func literal escapes to heap
./b13799.go:31: &i escapes to heap
./b13799.go:32: &j escapes to heap
./b13799.go:34: &fn escapes to heap
   ./b13799.go:21: test make(map[int][]int) does not escape
   ./b13799.go:41: test ... argument does not escape
   ./b13799.go:12: iter escapes to heap
   ./b13799.go:12: main ... argument does not escape

(this is the working one)

drchase-macbookair:tmp drchase$ go build -gcflags -m b13799.go
# command-line-arguments
   ./b13799.go:41: iter escapes to heap
   ./b13799.go:41: maxI escapes to heap
   ./b13799.go:41: len(m) escapes to heap
   ./b13799.go:21: test make(map[int][]int) does not escape
./b13799.go:30: test func literal does not escape
   ./b13799.go:41: test ... argument does not escape
   ./b13799.go:12: iter escapes to heap
   ./b13799.go:12: main ... argument does not escape

My guess is that the bug occurs when the function escapes to heap but the map does not, and then the stack moves (because of recursion) and the heap-allocated closure is not updated.

@gopherbot
Copy link

CL https://golang.org/cl/18234 mentions this issue.

@rsc rsc changed the title cmd/compile: loop & recursion in named closure yields panic or unexpected behavior cmd/compile: bad escape analysis for linked data structures captured in closure Jan 6, 2016
@golang golang locked and limited conversation to collaborators Jan 13, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
Go1.6
Development

No branches or pull requests
5 participants
@sqs @dmitshur @dr2chase @ianlancetaylor @gopherbot