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

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>

3 files changed, 94 insertions, 2 deletions

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.