-
Notifications
You must be signed in to change notification settings - Fork 17.9k
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: compiler can unexpectedly preserve memory #22350
Comments
Here is a smaller reproduction which grows linearly on my machine
|
I think this is not a bug since |
@mattn i'm sorry I don't understand what you mean. I've stared at this code a bunch, and it looks like to me that on each iteration curr is replaced with curr.next, so the previous value of curr is no longer referenced.
And so on. I'm sure i'm missing something, so I'd appreciate someone helping me understand what I'm missing. |
At least @davecheney 's version is an interesting result of compiler optimization. The very first call to Basically 1) the fact that you use the same Go variable doesn't mean that the compiler does the same; 2) the fact that you call Not sure whether or how to fix this. Does it come up in a real program? CC @randall77 |
As long as curr.next holds the reference of package main
import (
"runtime"
"unsafe"
)
type Node struct {
next uintptr
payload [64]byte
}
func main() {
curr := new(Node)
for {
curr.next = uintptr(unsafe.Pointer(new(Node)))
curr = (*Node)(unsafe.Pointer(curr.next))
runtime.GC()
}
} Of course this is a dangerous code. Because the value indicated by |
But |
@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. |
@davecheney |
@davecheney It GC collect the unreferenced-value immediately as you mentioned, following code can not make linked-list. package main
type Node struct {
next *Node
payload [64]byte
}
func NewNode(curr *Node) *Node {
newnode := new(Node)
newnode.next = curr
return newnode
}
func main() {
curr := NewNode(nil)
curr = NewNode(curr)
curr = NewNode(curr)
} |
On 20 Oct 2017, at 17:00, mattn ***@***.***> wrote:
@davecheney
curr is overwritten but not overwritten the memory block pointed by curr.
pointer is a reference just not a value. if something refer the memory block, GC can sweep for marking.
That’s what I’m saying, curr = curr.next means that the value previously pointed to by curr is now no longer visible.
… —
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub, or mute the thread.
|
On 20 Oct 2017, at 17:07, mattn ***@***.***> wrote:
@davecheney It GC collect the unreferenced-value immediately as you mentioned, following code can not make linked-list.
This is a valid linked list. The previous value of curr is captured in the next field of the value returned from NewNode.
… package main
type Node struct {
next *Node
payload [64]byte
}
func NewNode(curr *Node) *Node {
newnode := new(Node)
newnode.next = curr
return newnode
}
func main() {
curr := NewNode(nil)
curr = NewNode(curr)
curr = NewNode(curr)
}
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub, or mute the thread.
|
@davecheney do you mean we can't make linked-list with following code? curr := new(Node)
for i := 0; i < 5; i++ {
curr.next = new(Node)
curr = curr.next
}
// now curr is top of linked-list |
Yes, that is a linked list, however on every iteration, `curr` points to
the _tail_ of the linked list, and curr's next pointer is nil. So, it's not
a very useful linked list.
But more importantly, this bug is about the previous chains in the linked
list, curr's predecessors. They are garbage because no live reference
points to them. However, because of escape analysis the original location
of curr on the stack remains live, keeping the entire linked list alive.
This is a bug.
…On Fri, Oct 20, 2017 at 4:30 PM, mattn ***@***.***> wrote:
@davecheney <https://github.com/davecheney> do you mean we can't make
linked-list with following code?
curr := new(Node)
for i := 0; i < 5; i++ {
curr.next = new(Node)
curr = curr.next
}
// now curr is top of linked-list
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#22350 (comment)>, or mute
the thread
<https://github.com/notifications/unsubscribe-auth/AAAcA0ZNPc5iHQpOXsGGnzYy7ar3GFVUks5suD3zgaJpZM4QAIYl>
.
|
No. this is not a bug. This works as intended. And changing this behavior is language change. |
I'm sorry, I don't understand what you are suggesting with that link. I
don't think there is anything further I can add to this discussion. Thank
you for your time.
…On Fri, Oct 20, 2017 at 5:35 PM, mattn ***@***.***> wrote:
No. this is not a bug. This works as intended. And changing this behavior
is language change.
See https://golang.org/src/container/ring/ring.go#L61
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#22350 (comment)>, or mute
the thread
<https://github.com/notifications/unsubscribe-auth/AAAcA7rv1LSLcA_4TyxVC2iLGdW6YdRxks5suE1HgaJpZM4QAIYl>
.
|
https://golang.org/src/container/ring/ring.go#L69 @mattn Have you ever seen {prev: p}? |
As far as i know, this is usual/general way to make linked list which have size. |
@mattn Your example is doubly linked-list, but the bug of this issue is singly linked-list. They are completely different |
In your thought, BTW, how garbages will be corrected? update |
@mattn
|
Ah, Sorry, I was confused. :( This code doesn't have top of the chain. So un-referenced curr should be garbage-collected. |
As Ian pointed out, the first Node is allocated on stack. You cannot garbage collect stack memory, but that stack-allocated Node references transitively all other Nodes allocated later in heap. |
package main
type Node struct {
next *Node
payload [64]byte
}
func NewNode() *Node {
return &Node{}
}
func main() {
curr := NewNode()
for {
curr.next = NewNode()
curr = curr.next
}
} This is replaced inline(stack) operation? |
I don't know, it's different code. I think there's a compiler flag that tells what's escaping or not, so you can test both versions and look for differences, if any. |
@cznic This probably won't be particularly helpful, but the commit that introduced stack allocation for non-escaping calls to |
One way to view this class of problems is that a pointer P to a value V is allocated on the stack, but that P dies and nothing else points to V, so V should die. If V were allocated on the heap all would work as programmers intuitively expect, but because V is allocated on the stack it in effect remains live until the function returns. So the first question is: can we detect that there are no pointers to V? I believe the answer may be yes. On the assumption that pointers to the stack can only be found on the stack, we could build a liveness map of the stack during GC stack scanning, and use that to find all values on the stack that are dead. This would require the stack map to record not only pointer positions, but also object sizes, since liveness is per-object, not per-pointer. I think we could do this by using two bits per word in the stack map, as opposed to the single bit we currently use. The second question: is there anything we can do? The answer there is definitely yes: when we find that V is dead, we can zero it out. If this is possible, then the obvious downside is slower stack scanning. I think we will only defeat programmer intuition with objects that appear to be heap allocated, but are stack allocated because they do not escape, that themselves contain pointers into the heap. Perhaps the compiler can mark these cases such that the runtime only has to do this special scanning if they exist. |
I recently encountered an issue of increased memory usage after minor refactoring of existing code using a closure and @mdempsky pointed me to this issue. So I am adding my example here. https://play.golang.org/p/zA9iHzDIYi Basically, the function closure here that contains a reference to the byte slice is stack allocated, so the byte slice remains alive until G returns. GC makes no guarantees about when the memory is garbage collected, thus it's not incorrect behavior. But it's rather surprising and it was hard to diagnose. |
Then you can just eliminate the GC completely. Can such language be still called "garbage collected"? I don't think so. IMO, a garbage collected language rutnime must guarantee at minimum that OOM will not happen when there's enough of non reachable allocations to reclaim that can satisfy the current allocation request. edit: typos |
@cznic It's hard to make that specification precisely. Consider:
So can the memory pointed to by |
@randall77 To be fair, in @hyangah's repro, the issue is the goroutine is stuck at I agree any definition of "GC correctness" probably shouldn't rely on knowing ahead of time which branch path will be taken, but it seems like if no branch could possibly reference a variable, it should be GC'd. (That said, regardless of whether we define this as an issue or not, I'm not sure how to effectively address it at the moment.) |
In general whether an object is reachable from some point in a program is
not decidable. Everything after that is simply the implementation doing the
best it can. A big part of that is getting the tools into the hands of the
practitioner so they can more easily understand their code.
…On Mon, Oct 30, 2017 at 1:43 PM, cznic ***@***.***> wrote:
GC makes no guarantees about when the memory is garbage collected, thus
it's not incorrect behavior.
The you can just eliminate the GC completely. Can such language be still
called "garbage collected"? I don't think so. IMO, a garbage collected
language rutnime *must* guarantee at minimum that OOM will not happen
when there's enough on non reachable allocations to reclaim that can
satisfy the current allocation request.
—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
<#22350 (comment)>, or mute
the thread
<https://github.com/notifications/unsubscribe-auth/AA7WnwOvy3fsLrkSuWLiQqyreAPcBRHsks5sxgrBgaJpZM4QAIYl>
.
|
I'd not say it's fuzzy, IMO. Using/not using DCE makes it into two different programs, from GC's POV, but the cut is still clear: Unreachable memory is memory which cannot be transitively reached from any root observable by the program as a whole, including the runtime. This issue is about a particular setup where heap allocations are not transitively reachable from any root observable by the program but still not eligible for collection.
Did you mean 'statically not decidable'? Anyway, this issue is, I believe, not about what can be said statically about liveness. IIUC, the stack is a GC root, but at the same time the stack contains unreachable (stack allocated) memory transitively pointing to heap. I think that's what's relevant here. If static analysis can improve things, all good, but the proper solution will/should IMO work without any static analysis. It's just the assumption that stack is in its entirety a GC root that does not hold - and enables this issue to demonstrate itself. edit: typos |
I agree, and that is the problem. The question is, what should the spec say about my example? Does the spec say that My argument is we can't add anything to the spec that fixes whether |
Note that this suggestion does not fix the case reported by @hyangah . In her example the function closure being held on the stack is not reassigned anywhere. |
As you know, the current GC treats the entire stack as a root. So by that definition the heap allocation is transitively reachable from a root. I assume that what you are trying to get at is that we shouldn't treat the entire stack as a root. That seems similar to what @mdempsky suggested above:
|
I did a little bit of exploring in the stdlib to see how often things like this happen. I wrote a go/ast program to look through the stdlib for occurrences of
There were about 100 of these. I then merged this list with the output of the compiler's
The The So TL;DR this issue doesn't happen in the stdlib (caveat: I didn't check the test packages). Hard to know exactly what to conclude from this, but at least we have some evidence that this isssue is fairly rare. |
Can you please use your program program to check the corpus? Or, even better, make the code available somewhere? |
Here's the program:
(Replace 28 with the right constant for your current working directory.) Get the list of std packages with
Run the program above with
Find all the non-escaping allocations in the std lib
Merge the results and find matching positions:
From the output you can eyeball all of the places where the assignments match a "does not escape" message. |
From what i read, I think this issue related to #19469, and that issue cost me hours to debug. It's really hard for newcomer like me. |
naive question: given @randall77's code, is this being considered for go vet? |
@kklobe, probably not. Vet requires a very low false positive rate, as it is run by default. vet errors in the stdlib are a no-go. (Assuming the false positives my code generates can't be fixed.) Possibly something for go/lint, although that's more for style than substance. But in any case I'm not sure anyone knows what the right algorithm might be. Mine was kind of a hack. |
I ran into this problem in prod/ It resulted in OOM kill and some nasty refactoring and hackery to make it behave properly. In our case we were able to work around it somewhat, but it is still pretty annoying. |
Did your bug fit the pattern
or was it something more obfuscated than that? |
It was quite a bit more obfuscated than that, but fit the general pattern. |
Change https://golang.org/cl/134155 mentions this issue: |
Change https://golang.org/cl/134156 mentions this issue: |
Rework how the compiler+runtime handles stack-allocated variables whose address is taken. Direct references to such variables work as before. References through pointers, however, use a new mechanism. The new mechanism is more precise than the old "ambiguously live" mechanism. It computes liveness at runtime based on the actual references among objects on the stack. Each function records all of its address-taken objects in a FUNCDATA. These are called "stack objects". The runtime then uses that information while scanning a stack to find all of the stack objects on a stack. It then does a mark phase on the stack objects, using all the pointers found on the stack (and ancillary structures, like defer records) as the root set. Only stack objects which are found to be live during this mark phase will be scanned and thus retain any heap objects they point to. A subsequent CL will remove all the "ambiguously live" logic from the compiler, so that the stack object tracing will be required. For this CL, the stack tracing is all redundant with the current ambiguously live logic. Update #22350 Change-Id: Ide19f1f71a5b6ec8c4d54f8f66f0e9a98344772f Reviewed-on: https://go-review.googlesource.com/c/134155 Reviewed-by: Austin Clements <austin@google.com>
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.
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. -_-The text was updated successfully, but these errors were encountered: