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
runtime: bad pointer due to map iteration #9384
Comments
Ah, I just noticed that the map values are empty structs. Easy to believe a pointer to one might actually be pointing beyond the end of the underlying array. |
Yes, that looks like the problem. A pointer to &bucket.value[5] might be at the end of the bucket if the values are 0-sized. This seems to be a generic problem with taking the address of zero-sized things. I can manufacture a pointer to the end of an object like this: package main type T struct { var t *T func main() {
} prints That last pointer points to the next object. We could solve this one in the compiler, replacing &(zero-sized thing) with a pointer to the zero object. But it's an ugly pile of special-case code in the hashmap implementation :( |
A) Fix the compiler to convert &x where x is of a zero-sized type to a pointer to the zero object. Make sure to preserve the side-effects of x, if any. |
Another option is to add a FlagZeroTail or some such to each type that ends in a zero-sized object. In malloc.go, do "if flags & FlagZeroTail { size++ }" |
This basically is what Austin and I were just discussing. An extra word of On Thursday, December 18, 2014, Keith Randall notifications@github.com
|
It seems that solution will make struct{} type less useful as it |
Let's start by fixing the map code. |
If we do the size++ trick we don't need to fix the map code. struct{} will sometimes use a byte of memory, but often won't. For instance, make(chan struct{}, 100) will only need sizeof(chan header) + 1 bytes, not sizeof(chan header) + 100 bytes. Same thing for maps, the padding only needs to go at the end of the bucket array, not between every bucket. |
What is the use case for a struct{} type? Are they common or critical to On Thu, Dec 18, 2014 at 8:10 PM, Minux Ma notifications@github.com wrote:
|
We use empty structs as values in a map in order to implement a set type, e.g. |
It's also common to use a buffered |
Also map[keyType]struct{} is a popular way to implement a set of keyTypes If we just add one byte to each channel/map with zero-sized types, then I'm |
The issue here is that map code is broken for value = struct{}. In general things do work fine with struct{}. For example new(struct{}) is fine. Map code is the exception here, maps with struct{} values are very common, and we need a simple, targeted fix for this specific problem for Go 1.4.1. It is true that if you have a non-zero-size struct type that has a final zero-sized field, taking the address of that field can give you a pointer beyond the allocation. That's really a separate issue and is a much less common case. Please discuss this more general problem on #9401 and leave this issue for the map problem. Thanks. |
@randall77 as a first pass, could we just do the size++ trick directly in the map code allocations? (I went to go try this out myself, but I have been unable to write a test that reproduces the original bug. Not sure what I'm missing.) |
If the value size is zero, I believe we can leave it.value == nil and the bug is fixed. There's no need to change the allocation behavior for this fix (and doing so is risky enough that I wouldn't want it in 1.4.1). |
Proposed fix at https://go-review.googlesource.com/#/c/1869/ |
… of bucket Pointers to zero-sized values may end up pointing to the next object in memory, and possibly off the end of a span. This can cause memory leaks and/or confuse the garbage collector. By putting the overflow pointer at the end of the bucket, we make sure that pointers to any zero-sized keys or values don't accidentally point to the next object in memory. fixes #9384 Change-Id: I5d434df176984cb0210b4d0195dd106d6eb28f73 Reviewed-on: https://go-review.googlesource.com/1869 Reviewed-by: Russ Cox <rsc@golang.org> (cherry picked from commit fbc56cf) Reviewed-on: https://go-review.googlesource.com/2801 Reviewed-by: Andrew Gerrand <adg@golang.org>
Due to a bug in Go1.4 (see golang/go#9384), using an empty struct as the value in a map can cause a crash. This CL works around the issue by using the boolean "true" as the map value. The workaround will not be required after Go1.4.1. Change-Id: Id8d51f4b78226780d1513d1978dfdd5071bcaab5
… of bucket Pointers to zero-sized values may end up pointing to the next object in memory, and possibly off the end of a span. This can cause memory leaks and/or confuse the garbage collector. By putting the overflow pointer at the end of the bucket, we make sure that pointers to any zero-sized keys or values don't accidentally point to the next object in memory. fixes golang#9384 Change-Id: I5d434df176984cb0210b4d0195dd106d6eb28f73 Reviewed-on: https://go-review.googlesource.com/1869 Reviewed-by: Russ Cox <rsc@golang.org> (cherry picked from commit fbc56cf) Reviewed-on: https://go-review.googlesource.com/2801 Reviewed-by: Andrew Gerrand <adg@golang.org>
… of bucket Pointers to zero-sized values may end up pointing to the next object in memory, and possibly off the end of a span. This can cause memory leaks and/or confuse the garbage collector. By putting the overflow pointer at the end of the bucket, we make sure that pointers to any zero-sized keys or values don't accidentally point to the next object in memory. fixes golang#9384 Change-Id: I5d434df176984cb0210b4d0195dd106d6eb28f73 Reviewed-on: https://go-review.googlesource.com/1869 Reviewed-by: Russ Cox <rsc@golang.org> (cherry picked from commit fbc56cf) Reviewed-on: https://go-review.googlesource.com/2801 Reviewed-by: Andrew Gerrand <adg@golang.org>
… of bucket Pointers to zero-sized values may end up pointing to the next object in memory, and possibly off the end of a span. This can cause memory leaks and/or confuse the garbage collector. By putting the overflow pointer at the end of the bucket, we make sure that pointers to any zero-sized keys or values don't accidentally point to the next object in memory. fixes golang#9384 Change-Id: I5d434df176984cb0210b4d0195dd106d6eb28f73 Reviewed-on: https://go-review.googlesource.com/1869 Reviewed-by: Russ Cox <rsc@golang.org> (cherry picked from commit fbc56cf) Reviewed-on: https://go-review.googlesource.com/2801 Reviewed-by: Andrew Gerrand <adg@golang.org>
… of bucket Pointers to zero-sized values may end up pointing to the next object in memory, and possibly off the end of a span. This can cause memory leaks and/or confuse the garbage collector. By putting the overflow pointer at the end of the bucket, we make sure that pointers to any zero-sized keys or values don't accidentally point to the next object in memory. fixes golang#9384 Change-Id: I5d434df176984cb0210b4d0195dd106d6eb28f73 Reviewed-on: https://go-review.googlesource.com/1869 Reviewed-by: Russ Cox <rsc@golang.org> (cherry picked from commit fbc56cf) Reviewed-on: https://go-review.googlesource.com/2801 Reviewed-by: Andrew Gerrand <adg@golang.org>
… of bucket Pointers to zero-sized values may end up pointing to the next object in memory, and possibly off the end of a span. This can cause memory leaks and/or confuse the garbage collector. By putting the overflow pointer at the end of the bucket, we make sure that pointers to any zero-sized keys or values don't accidentally point to the next object in memory. fixes golang#9384 Change-Id: I5d434df176984cb0210b4d0195dd106d6eb28f73 Reviewed-on: https://go-review.googlesource.com/1869 Reviewed-by: Russ Cox <rsc@golang.org> (cherry picked from commit fbc56cf) Reviewed-on: https://go-review.googlesource.com/2801 Reviewed-by: Andrew Gerrand <adg@golang.org>
An internal Google program is executing code like the below and getting occasional runtime crashes during garbage collection:
A garbage collection happens on the marked line. During the scan of the stack frame corresponding to this function, the garbage collector finds an invalid heap pointer and crashes the program. The invalid heap pointer is at 0x1f8(SP). The map iterator for the loop being executed start at 0x1f0(SP), making this the second word in the iterator, it.value.
The error I am looking at says:
The actual stack frame is sp=0xc20805ebc0, giving the extra 0x60+0x198 = 0x1f8.
This is the generated code for the creation of allDeps and then that loop:
The bad pointer is 0xc2080f7000 and the span summary is 0xc2080ee000-0xc2080f7000-0xc2080f8000, meaning that s.limit == 0xc2080f7000. The conclusion seems to be that mapiternext (or mapiterinit, which calls mapiternext) can leave it.value pointing at the end of the underlying map data array.
I don't see how that can happen by reading mapiternext, but it seems to be possible somehow. Should probably fix for Go 1.4.1.
The text was updated successfully, but these errors were encountered: