[release-branch.go1.14] runtime: make typehash match compiler generated hashes exactly

If typehash (used by reflect) does not match the built-in map's hash,
then problems occur. If a map is built using reflect, and then
assigned to a variable of map type, the hash function can change. That
causes very bad things.

This issue is rare. MapOf consults a cache of all types that occur in
the binary before making a new one. To make a true new map type (with
a hash function derived from typehash) that map type must not occur in
the binary anywhere. But to cause the bug, we need a variable of that
type in order to assign to it. The only way to make that work is to
use a named map type for the variable, so it is distinct from the
unnamed version that MapOf looks for.

Fixes #37721

Change-Id: I3537bfceca8cbfa1af84202f432f3c06953fe0ed
Reviewed-on: https://go-review.googlesource.com/c/go/+/222357
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Cherry Zhang <cherryyz@google.com>
(cherry picked from commit 2b8e60d464515634462ca472ca09c791e2cbf6ae)
Reviewed-on: https://go-review.googlesource.com/c/go/+/222778

5 files changed, 127 insertions, 2 deletions

diff --git a/src/cmd/compile/internal/gc/alg.go b/src/cmd/compile/internal/gc/alg.go
index 4759b60412..c83badaa86 100644
--- a/src/cmd/compile/internal/gc/alg.go
+++ b/src/cmd/compile/internal/gc/alg.go
@@ -186,6 +186,7 @@ func algtype1(t *types.Type) (AlgKind, *types.Type) {
 
 // genhash returns a symbol which is the closure used to compute
 // the hash of a value of type t.
+// Note: the generated function must match runtime.typehash exactly.
 func genhash(t *types.Type) *obj.LSym {
 	switch algtype(t) {
 	default:
diff --git a/src/runtime/alg.go b/src/runtime/alg.go
index 5a0656513d..0af48ab25c 100644
--- a/src/runtime/alg.go
+++ b/src/runtime/alg.go
@@ -158,6 +158,8 @@ func nilinterhash(p unsafe.Pointer, h uintptr) uintptr {
 // is slower but more general and is used for hashing interface types
 // (called from interhash or nilinterhash, above) or for hashing in
 // maps generated by reflect.MapOf (reflect_typehash, below).
+// Note: this function must match the compiler generated
+// functions exactly. See issue 37716.
 func typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr {
 	if t.tflag&tflagRegularMemory != 0 {
 		// Handle ptr sizes specially, see issue 37086.
@@ -195,12 +197,28 @@ func typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr {
 		return h
 	case kindStruct:
 		s := (*structtype)(unsafe.Pointer(t))
+		memStart := uintptr(0)
+		memEnd := uintptr(0)
 		for _, f := range s.fields {
-			// TODO: maybe we could hash several contiguous fields all at once.
+			if memEnd > memStart && (f.name.isBlank() || f.offset() != memEnd || f.typ.tflag&tflagRegularMemory == 0) {
+				// flush any pending regular memory hashing
+				h = memhash(add(p, memStart), h, memEnd-memStart)
+				memStart = memEnd
+			}
 			if f.name.isBlank() {
 				continue
 			}
-			h = typehash(f.typ, add(p, f.offset()), h)
+			if f.typ.tflag&tflagRegularMemory == 0 {
+				h = typehash(f.typ, add(p, f.offset()), h)
+				continue
+			}
+			if memStart == memEnd {
+				memStart = f.offset()
+			}
+			memEnd = f.offset() + f.typ.size
+		}
+		if memEnd > memStart {
+			h = memhash(add(p, memStart), h, memEnd-memStart)
 		}
 		return h
 	default:
diff --git a/src/runtime/export_test.go b/src/runtime/export_test.go
index 88cb1acc5b..6a8d00c60d 100644
--- a/src/runtime/export_test.go
+++ b/src/runtime/export_test.go
@@ -950,3 +950,28 @@ func SemNwait(addr *uint32) uint32 {
 	root := semroot(addr)
 	return atomic.Load(&root.nwait)
 }
+
+// MapHashCheck computes the hash of the key k for the map m, twice.
+// Method 1 uses the built-in hasher for the map.
+// Method 2 uses the typehash function (the one used by reflect).
+// Returns the two hash values, which should always be equal.
+func MapHashCheck(m interface{}, k interface{}) (uintptr, uintptr) {
+	// Unpack m.
+	mt := (*maptype)(unsafe.Pointer(efaceOf(&m)._type))
+	mh := (*hmap)(efaceOf(&m).data)
+
+	// Unpack k.
+	kt := efaceOf(&k)._type
+	var p unsafe.Pointer
+	if isDirectIface(kt) {
+		q := efaceOf(&k).data
+		p = unsafe.Pointer(&q)
+	} else {
+		p = efaceOf(&k).data
+	}
+
+	// Compute the hash functions.
+	x := mt.hasher(noescape(p), uintptr(mh.hash0))
+	y := typehash(kt, noescape(p), uintptr(mh.hash0))
+	return x, y
+}
diff --git a/src/runtime/hash_test.go b/src/runtime/hash_test.go
index fe25a7f84b..655ca18f11 100644
--- a/src/runtime/hash_test.go
+++ b/src/runtime/hash_test.go
@@ -8,6 +8,7 @@ import (
 	"fmt"
 	"math"
 	"math/rand"
+	"reflect"
 	. "runtime"
 	"strings"
 	"testing"
@@ -48,6 +49,54 @@ func TestMemHash64Equality(t *testing.T) {
 	}
 }
 
+func TestCompilerVsRuntimeHash(t *testing.T) {
+	// Test to make sure the compiler's hash function and the runtime's hash function agree.
+	// See issue 37716.
+	for _, m := range []interface{}{
+		map[bool]int{},
+		map[int8]int{},
+		map[uint8]int{},
+		map[int16]int{},
+		map[uint16]int{},
+		map[int32]int{},
+		map[uint32]int{},
+		map[int64]int{},
+		map[uint64]int{},
+		map[int]int{},
+		map[uint]int{},
+		map[uintptr]int{},
+		map[*byte]int{},
+		map[chan int]int{},
+		map[unsafe.Pointer]int{},
+		map[float32]int{},
+		map[float64]int{},
+		map[complex64]int{},
+		map[complex128]int{},
+		map[string]int{},
+		//map[interface{}]int{},
+		//map[interface{F()}]int{},
+		map[[8]uint64]int{},
+		map[[8]string]int{},
+		map[struct{ a, b, c, d int32 }]int{}, // Note: tests AMEM128
+		map[struct{ a, b, _, d int32 }]int{},
+		map[struct {
+			a, b int32
+			c    float32
+			d, e [8]byte
+		}]int{},
+		map[struct {
+			a int16
+			b int64
+		}]int{},
+	} {
+		k := reflect.New(reflect.TypeOf(m).Key()).Elem().Interface() // the zero key
+		x, y := MapHashCheck(m, k)
+		if x != y {
+			t.Errorf("hashes did not match (%x vs %x) for map %T", x, y, m)
+		}
+	}
+}
+
 // Smhasher is a torture test for hash functions.
 // https://code.google.com/p/smhasher/
 // This code is a port of some of the Smhasher tests to Go.
diff --git a/test/fixedbugs/issue37716.go b/test/fixedbugs/issue37716.go
new file mode 100644
index 0000000000..42d66dff1b
--- /dev/null
+++ b/test/fixedbugs/issue37716.go
@@ -0,0 +1,32 @@
+// run
+
+// Copyright 2020 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package main
+
+import "reflect"
+
+// complicated enough to require a compile-generated hash function
+type K struct {
+	a, b int32 // these get merged by the compiler into a single field, something typehash doesn't do
+	c    float64
+}
+
+func main() {
+	k := K{a: 1, b: 2, c: 3}
+
+	// Make a reflect map.
+	m := reflect.MakeMap(reflect.MapOf(reflect.TypeOf(K{}), reflect.TypeOf(true)))
+	m.SetMapIndex(reflect.ValueOf(k), reflect.ValueOf(true))
+
+	// The binary must not contain the type map[K]bool anywhere, or reflect.MapOf
+	// will use that type instead of making a new one. So use an equivalent named type.
+	type M map[K]bool
+	var x M
+	reflect.ValueOf(&x).Elem().Set(m)
+	if !x[k] {
+		panic("key not found")
+	}
+}