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: bad liveness map #20029

Closed
randall77 opened this issue Apr 18, 2017 · 8 comments

Comments

Projects
None yet
4 participants
@randall77
Copy link
Contributor

commented Apr 18, 2017

package main

import "runtime"

func f(m map[int]int) {
outer:
        for i := 0; i < 10; i++ {
                for k := range m {
                        if k == 5 {
                                continue outer
                        }
                }
                runtime.GC()
                break
        }
        runtime.GC()
}
$ go tool compile -live tmp1.go
tmp1.go:5:18: live at entry to f: m
tmp1.go:8:12: live at call to mapiterinit: m .autotmp_4
tmp1.go:8:12: live at call to mapiternext: m .autotmp_4
tmp1.go:16:12: f: .autotmp_4 (type map.iter[int]int) is ambiguously live
tmp1.go:16:12: live at call to GC: .autotmp_4

The hiter for the inner loop (.autotmp_4) should not be live at the outer runtime.GC. It is live because liveness analysis sort of gives up on it (the "ambiguously live" comment there).
That's not so bad in and of itself; it's just imprecise.

But at the end of the inner loop we issue a VARKILL of .autotmp_4, so it definitely isn't live at the first runtime.GC (nothing with a pointer is live at that call, so it isn't even listed by -live). That means .autotmp_4 is live, then it isn't, then it is again. The first runtime.GC will free m, as nothing is holding m live at this point. The second runtime.GC finds m inside .autotmp_4 and tries to scan an already freed map. Boom.

This seems like a bad interaction between ambiguously live and VARKILL. Maybe fundamentally bad. Time to put my pondering cap on...

@aclements

@randall77 randall77 self-assigned this Apr 18, 2017

@randall77 randall77 added this to the Go1.9 milestone Apr 18, 2017

@randall77

This comment has been minimized.

Copy link
Contributor Author

commented Apr 18, 2017

1.9 for now. Likely will be promoted to 1.8.2.

@randall77

This comment has been minimized.

Copy link
Contributor Author

commented Apr 18, 2017

Maybe VARKILL for ambiguously live variables should do an explicit zeroing?

@randall77

This comment has been minimized.

Copy link
Contributor Author

commented Apr 18, 2017

Another fix would be to somehow get a VARKILL of the hiter at the "continue outer" statement. I'm not sure if that would be a complete fix. It's also hard to generate such a kill in order.go.

@randall77

This comment has been minimized.

Copy link
Contributor Author

commented Apr 18, 2017

I hacked up a fix to explicitly zero at VARKILLs of ambiguously live variables.

The hack is definitely a hack. The challenge here is that we don't know a variable is ambiguously live until very late in compilation, after regalloc & friends. So, for example, we can't clobber any registers to do the zeroing. And it is after lowering, so we'd need to repeat the logic for each architecture. Maybe we could push liveness analysis (or at least ambiguity analysis) earlier, but I suspect that would be hard. Maybe VARKILL can clobber a few registers on architectures that need it.

It only triggers once during make.bash and once more during go test std (in (*Checker).caseTypes and TestMapSparseIterOrder, in case you were wondering) so I'm not worried about efficiency very much. Just something simple should be adequate.

I'll see if I can get a CL out tomorrow.

@gopherbot gopherbot closed this in 38dee12 Apr 20, 2017

@randall77 randall77 modified the milestones: Go1.8.2, Go1.9 Apr 21, 2017

@randall77 randall77 reopened this Apr 21, 2017

@randall77

This comment has been minimized.

Copy link
Contributor Author

commented Apr 21, 2017

Reopening for 1.8.2 consideration.

@gopherbot

This comment has been minimized.

Copy link

commented Apr 21, 2017

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

@bradfitz bradfitz modified the milestones: Go1.8.2, Go1.8.3 May 18, 2017

@broady

This comment has been minimized.

Copy link
Member

commented May 23, 2017

The change doesn't apply cleanly to the 1.8 branch. @randall77, can you PTAL?

@gopherbot

This comment has been minimized.

Copy link

commented May 23, 2017

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

gopherbot pushed a commit that referenced this issue May 24, 2017

[release-branch.go1.8] cmd/compile: zero ambiguously live variables a…
…t VARKILLs

This is a redo of CL 41076 backported to the 1.8 release branch.
There were major conflicts, so I had to basically rewrite it again
from scratch.  The way Progs are allocated changed.  Liveness analysis
and Prog generation got reordered.  Liveness analysis changed from
running on gc.BasicBlock to ssa.Block.  All that makes the logic quite
a bit different.

Please review carefully.

From CL 41076:

At VARKILLs, zero a variable if it is ambiguously live.
After the VARKILL anything this variable references
might be collected. If it were to become live again later,
the GC will see references to already-collected objects.

We don't know a variable is ambiguously live until very
late in compilation (after lowering, register allocation, ...),
so it is hard to generate the code in an arch-independent way.
We also have to be careful not to clobber any registers.
Fortunately, this almost never happens so performance is ~irrelevant.

There are only 2 instances where this triggers in the stdlib.

Fixes #20029

Change-Id: Ibb757eec58ee07f40df5e561b19d315684dc4bda
Reviewed-on: https://go-review.googlesource.com/43998
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

@broady broady closed this May 24, 2017

@golang golang locked and limited conversation to collaborators May 24, 2018

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
You can’t perform that action at this time.