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: invalid algorithm table for some types #17752

Closed
randall77 opened this issue Nov 2, 2016 · 11 comments
Closed

cmd/compile: invalid algorithm table for some types #17752

randall77 opened this issue Nov 2, 2016 · 11 comments
Assignees
Milestone

Comments

@randall77
Copy link
Contributor

@randall77 randall77 commented Nov 2, 2016

package main

func f(m map[string]int) int {
	return m["a"]
}

func g(m map[[8]string]int) int {
	return m[[8]string{"a", "a", "a", "a", "a", "a", "a", "a"}]
}

func main() {
	m := map[[8]string]int{}
	println(g(m))
}

With f commented out, the example program runs fine (prints 0) in all versions of Go I tested.

With f not commented out, I get behavior all over the map.
1.2, 1.4: integer divide by zero panic
1.5, 1.6: success!
1.7, tip: fatal error: runtime.makemap: unsupported map key type

The failures at 1.7 & tip are the result of explicit checks; the code barfs because the key does not have a hash algorithm.

I suspect the problem is that during compilation of f, we construct a type [8]string as part of the map bucket. That type is marked as not needing an algorithm table. Later, when compiling g, we construct a map with key type [8]string and that type does need an algorithm table. Maybe the former decision is overriding the latter?

@dsnet @dr2chase @crawshaw @josharian

@randall77 randall77 added this to the Go1.8 milestone Nov 2, 2016
@dsnet dsnet added the NeedsFix label Nov 2, 2016
@randall77
Copy link
Contributor Author

@randall77 randall77 commented Nov 2, 2016

Josh, may be related to your change a6abc1c

@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Nov 2, 2016

Nice bug. Elegant.

@randall77
Copy link
Contributor Author

@randall77 randall77 commented Nov 2, 2016

Commenting out the Noalg=true statements in cmd/compile/internal/gc/reflect.go fixes the bug. Probably not the permanent fix, but illustrative.

@randall77
Copy link
Contributor Author

@randall77 randall77 commented Nov 2, 2016

@ianlancetaylor Nice comment. Succinct.

@mdempsky mdempsky self-assigned this Nov 2, 2016
@josharian
Copy link
Contributor

@josharian josharian commented Nov 3, 2016

Drat. The tests in CL 22399 were supposed to catch this kind of thing.

@mdempsky since you've self-assigned it, I'm not going to look into a fix. Let me know if that should change, and I'm happy to jump back in.

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Nov 3, 2016

@josharian No, I'm happy to dig into this.

So the issue is when we're writing out reflect metadata for types, we use the same link symbol regardless of whether Noalg is set, but we generate different contents depending on Noalg (namely whether we provide hash/eq function pointers). The consequence is everywhere we set Noalg on compiler-generated types, we're potentially poisoning any user types that happen to be identical.

It's just that the types we set Noalg on are rarely used as map keys or stored into interfaces and compared for equality, assuming they collide at all. Aside from the bucket arrays discovered above, the other instances are all structs (and one slice, but Noalg is redundant on slices anyway).

I think making Noalg work 100% correctly requires linker support. We probably need to generate separate symbols for the Noalg variants. Later at link-time we could recognize if we have both Noalg and !Noalg variants, and use only the !Noalg variant.

In the mean time, I think the quick fix is to just not set Noalg on the bucket arrays. I'll send a CL.

@randall77
Copy link
Contributor Author

@randall77 randall77 commented Nov 3, 2016

Instead, could we add names to the noalg types? That would make them distinct from any user types.

It would cost some space for the names, but we would save the space for the hash/eq code which is probably larger.

We'd need unique names, but that shouldn't be too hard (noalg.# where # is a unique id in the package).

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Nov 3, 2016

Adding unique names should work too, but the naive solution would cause map[int]A, map[int]B, ... to each use separate named types for their [8]int buckets.

@crawshaw
Copy link
Contributor

@crawshaw crawshaw commented Nov 3, 2016

Can't you add a "..noalg" suffix if Noalg is true, then the bucket types are shared?

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Nov 3, 2016

@crawshaw Yeah, that's what I'm playing with now.

@gopherbot
Copy link

@gopherbot gopherbot commented Nov 3, 2016

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

@gopherbot gopherbot closed this in 3797446 Nov 4, 2016
@golang golang locked and limited conversation to collaborators Nov 4, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants
You can’t perform that action at this time.