Go: cmd/compile: invalid algorithm table for some types

[randall77]

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]

Josh, may be related to your change https://github.com/golang/go/commit/a6abc1cd

[ianlancetaylor]

Nice bug. Elegant.

[randall77]

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

[randall77]

@ianlancetaylor Nice comment. Succinct.

[josharian]

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]

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

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]

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]

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

[mdempsky]

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

[gopherbot]

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