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

Jump to bottom

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
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone
Go1.8

Comments

@randall77
Copy link
Contributor 

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 The path to resolution is known, but the work has not been done. label Nov 2, 2016
@randall77
Copy link
Contributor Author

Josh, may be related to your change a6abc1cd

@ianlancetaylor
Copy link
Contributor

Nice bug. Elegant.

@randall77
Copy link
Contributor Author

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

@ianlancetaylor Nice comment. Succinct.

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

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 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

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 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
Member

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 commented Nov 3, 2016

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

@gopherbot
Copy link

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

@ALTree ALTree mentioned this issue Jan 13, 2017
Closed
@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.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Milestone
Go1.8
Development

No branches or pull requests
7 participants
@mdempsky @josharian @crawshaw @ianlancetaylor @dsnet @randall77 @gopherbot