compiler, runtime, reflect: generate unique type descriptors

    
    Currently, the compiler already generates common symbols for type
    descriptors, so the type descriptors are unique. However, when a
    type is created through reflection, it is not deduplicated with
    compiler-generated types. As a consequence, we cannot assume type
    descriptors are unique, and cannot use pointer equality to
    compare them. Also, when constructing a reflect.Type, it has to
    go through a canonicalization map, which introduces overhead to
    reflect.TypeOf, and lock contentions in concurrent programs.
    
    In order for the reflect package to deduplicate types with
    compiler-created types, we register all the compiler-created type
    descriptors at startup time. The reflect package, when it needs
    to create a type, looks up the registry of compiler-created types
    before creates a new one. There is no lock contention since the
    registry is read-only after initialization.
    
    This lets us get rid of the canonicalization map, and also makes
    it possible to compare type descriptors with pointer equality.
    
    Reviewed-on: https://go-review.googlesource.com/c/gofrontend/+/179598

From-SVN: r271894

2 files changed, 130 insertions, 79 deletions

diff --git a/libgo/go/reflect/type.go b/libgo/go/reflect/type.go
index fb2e5d4..8493d87 100644
--- a/libgo/go/reflect/type.go
+++ b/libgo/go/reflect/type.go
@@ -1105,15 +1105,14 @@ func (t *rtype) ptrTo() *rtype {
 		return &pi.(*ptrType).rtype
 	}
 
+	// Look in known types.
 	s := "*" + *t.string
-
-	canonicalTypeLock.RLock()
-	r, ok := canonicalType[s]
-	canonicalTypeLock.RUnlock()
-	if ok {
-		p := (*ptrType)(unsafe.Pointer(r.(*rtype)))
-		pi, _ := ptrMap.LoadOrStore(t, p)
-		return &pi.(*ptrType).rtype
+	if tt := lookupType(s); tt != nil {
+		p := (*ptrType)(unsafe.Pointer(tt))
+		if p.elem == t {
+			pi, _ := ptrMap.LoadOrStore(t, p)
+			return &pi.(*ptrType).rtype
+		}
 	}
 
 	// Create a new ptrType starting with the description
@@ -1138,10 +1137,7 @@ func (t *rtype) ptrTo() *rtype {
 	pp.ptrToThis = nil
 	pp.elem = t
 
-	q := canonicalize(&pp.rtype)
-	p := (*ptrType)(unsafe.Pointer(q.(*rtype)))
-
-	pi, _ := ptrMap.LoadOrStore(t, p)
+	pi, _ := ptrMap.LoadOrStore(t, &pp)
 	return &pi.(*ptrType).rtype
 }
 
@@ -1447,6 +1443,13 @@ func ChanOf(dir ChanDir, t Type) Type {
 	case BothDir:
 		s = "chan " + *typ.string
 	}
+	if tt := lookupType(s); tt != nil {
+		ch := (*chanType)(unsafe.Pointer(tt))
+		if ch.elem == typ && ch.dir == uintptr(dir) {
+			ti, _ := lookupCache.LoadOrStore(ckey, tt)
+			return ti.(Type)
+		}
+	}
 
 	// Make a channel type.
 	var ichan interface{} = (chan unsafe.Pointer)(nil)
@@ -1472,10 +1475,8 @@ func ChanOf(dir ChanDir, t Type) Type {
 	ch.uncommonType = nil
 	ch.ptrToThis = nil
 
-	// Canonicalize before storing in lookupCache
-	ti := toType(&ch.rtype)
-	lookupCache.Store(ckey, ti.(*rtype))
-	return ti
+	ti, _ := lookupCache.LoadOrStore(ckey, &ch.rtype)
+	return ti.(Type)
 }
 
 func ismapkey(*rtype) bool // implemented in runtime
@@ -1502,6 +1503,13 @@ func MapOf(key, elem Type) Type {
 
 	// Look in known types.
 	s := "map[" + *ktyp.string + "]" + *etyp.string
+	if tt := lookupType(s); tt != nil {
+		mt := (*mapType)(unsafe.Pointer(tt))
+		if mt.key == ktyp && mt.elem == etyp {
+			ti, _ := lookupCache.LoadOrStore(ckey, tt)
+			return ti.(Type)
+		}
+	}
 
 	// Make a map type.
 	// Note: flag values must match those used in the TMAP case
@@ -1544,10 +1552,8 @@ func MapOf(key, elem Type) Type {
 		mt.flags |= 16
 	}
 
-	// Canonicalize before storing in lookupCache
-	ti := toType(&mt.rtype)
-	lookupCache.Store(ckey, ti.(*rtype))
-	return ti
+	ti, _ := lookupCache.LoadOrStore(ckey, &mt.rtype)
+	return ti.(Type)
 }
 
 // FuncOf returns the function type with the given argument and result types.
@@ -1625,15 +1631,17 @@ func FuncOf(in, out []Type, variadic bool) Type {
 	}
 
 	str := funcStr(ft)
+	if tt := lookupType(str); tt != nil {
+		if haveIdenticalUnderlyingType(&ft.rtype, tt, true) {
+			return addToCache(tt)
+		}
+	}
 
 	// Populate the remaining fields of ft and store in cache.
 	ft.string = &str
 	ft.uncommonType = nil
 	ft.ptrToThis = nil
-
-	// Canonicalize before storing in funcLookupCache
-	tc := toType(&ft.rtype)
-	return addToCache(tc.(*rtype))
+	return addToCache(&ft.rtype)
 }
 
 // funcStr builds a string representation of a funcType.
@@ -1873,6 +1881,13 @@ func SliceOf(t Type) Type {
 
 	// Look in known types.
 	s := "[]" + *typ.string
+	if tt := lookupType(s); tt != nil {
+		slice := (*sliceType)(unsafe.Pointer(tt))
+		if slice.elem == typ {
+			ti, _ := lookupCache.LoadOrStore(ckey, tt)
+			return ti.(Type)
+		}
+	}
 
 	// Make a slice type.
 	var islice interface{} = ([]unsafe.Pointer)(nil)
@@ -1888,10 +1903,8 @@ func SliceOf(t Type) Type {
 	slice.uncommonType = nil
 	slice.ptrToThis = nil
 
-	// Canonicalize before storing in lookupCache
-	ti := toType(&slice.rtype)
-	lookupCache.Store(ckey, ti.(*rtype))
-	return ti
+	ti, _ := lookupCache.LoadOrStore(ckey, &slice.rtype)
+	return ti.(Type)
 }
 
 // The structLookupCache caches StructOf lookups.
@@ -2106,6 +2119,13 @@ func StructOf(fields []StructField) Type {
 		return t
 	}
 
+	// Look in known types.
+	if tt := lookupType(str); tt != nil {
+		if haveIdenticalUnderlyingType(&typ.rtype, tt, true) {
+			return addToCache(tt)
+		}
+	}
+
 	typ.string = &str
 	typ.hash = hash
 	typ.size = size
@@ -2214,10 +2234,7 @@ func StructOf(fields []StructField) Type {
 
 	typ.uncommonType = nil
 	typ.ptrToThis = nil
-
-	// Canonicalize before storing in structLookupCache
-	ti := toType(&typ.rtype)
-	return addToCache(ti.(*rtype))
+	return addToCache(&typ.rtype)
 }
 
 func runtimeStructField(field StructField) structField {
@@ -2300,6 +2317,13 @@ func ArrayOf(count int, elem Type) Type {
 
 	// Look in known types.
 	s := "[" + strconv.Itoa(count) + "]" + *typ.string
+	if tt := lookupType(s); tt != nil {
+		array := (*arrayType)(unsafe.Pointer(tt))
+		if array.elem == typ {
+			ti, _ := lookupCache.LoadOrStore(ckey, tt)
+			return ti.(Type)
+		}
+	}
 
 	// Make an array type.
 	var iarray interface{} = [1]unsafe.Pointer{}
@@ -2451,10 +2475,8 @@ func ArrayOf(count int, elem Type) Type {
 		}
 	}
 
-	// Canonicalize before storing in lookupCache
-	ti := toType(&array.rtype)
-	lookupCache.Store(ckey, ti.(*rtype))
-	return ti
+	ti, _ := lookupCache.LoadOrStore(ckey, &array.rtype)
+	return ti.(Type)
 }
 
 func appendVarint(x []byte, v uintptr) []byte {
@@ -2466,42 +2488,19 @@ func appendVarint(x []byte, v uintptr) []byte {
 }
 
 // toType converts from a *rtype to a Type that can be returned
-// to the client of package reflect. In gc, the only concern is that
-// a nil *rtype must be replaced by a nil Type, but in gccgo this
-// function takes care of ensuring that multiple *rtype for the same
-// type are coalesced into a single Type.
-var canonicalType = make(map[string]Type)
-
-var canonicalTypeLock sync.RWMutex
-
-func canonicalize(t Type) Type {
-	if t == nil {
-		return nil
-	}
-	s := t.rawString()
-	canonicalTypeLock.RLock()
-	if r, ok := canonicalType[s]; ok {
-		canonicalTypeLock.RUnlock()
-		return r
-	}
-	canonicalTypeLock.RUnlock()
-	canonicalTypeLock.Lock()
-	if r, ok := canonicalType[s]; ok {
-		canonicalTypeLock.Unlock()
-		return r
-	}
-	canonicalType[s] = t
-	canonicalTypeLock.Unlock()
-	return t
-}
-
+// to the client of package reflect. The only concern is that
+// a nil *rtype must be replaced by a nil Type.
 func toType(p *rtype) Type {
 	if p == nil {
 		return nil
 	}
-	return canonicalize(p)
+	return p
 }
 
+// Look up a compiler-generated type descriptor.
+// Implemented in runtime.
+func lookupType(s string) *rtype
+
 // ifaceIndir reports whether t is stored indirectly in an interface value.
 func ifaceIndir(t *rtype) bool {
 	return t.kind&kindDirectIface == 0
diff --git a/libgo/go/runtime/type.go b/libgo/go/runtime/type.go
index 5cafa38..3bdb8f1 100644
--- a/libgo/go/runtime/type.go
+++ b/libgo/go/runtime/type.go
@@ -6,7 +6,11 @@
 
 package runtime
 
-import "unsafe"
+import (
+	"runtime/internal/atomic"
+	"runtime/internal/sys"
+	"unsafe"
+)
 
 type _type struct {
 	size       uintptr
@@ -45,19 +49,8 @@ func (t *_type) pkgpath() string {
 }
 
 // Return whether two type descriptors are equal.
-// This is gccgo-specific, as gccgo, unlike gc, permits multiple
-// independent descriptors for a single type.
 func eqtype(t1, t2 *_type) bool {
-	switch {
-	case t1 == t2:
-		return true
-	case t1 == nil || t2 == nil:
-		return false
-	case t1.kind != t2.kind || t1.hash != t2.hash:
-		return false
-	default:
-		return t1.string() == t2.string()
-	}
+	return t1 == t2
 }
 
 type method struct {
@@ -164,3 +157,62 @@ type structtype struct {
 	typ    _type
 	fields []structfield
 }
+
+// typeDescriptorList holds a list of type descriptors generated
+// by the compiler. This is used for the compiler to register
+// type descriptors to the runtime.
+// The layout is known to the compiler.
+//go:notinheap
+type typeDescriptorList struct {
+	count int
+	types [1]uintptr // variable length
+}
+
+// typelist holds all type descriptors generated by the comiler.
+// This is for the reflect package to deduplicate type descriptors
+// when it creates a type that is also a compiler-generated type.
+var typelist struct {
+	initialized uint32
+	lists       []*typeDescriptorList // one element per package
+	types       map[string]uintptr    // map from a type's string to *_type, lazily populated
+	// TODO: use a sorted array instead?
+}
+var typelistLock mutex
+
+// The compiler generates a call of this function in the main
+// package's init function, to register compiler-generated
+// type descriptors.
+// p points to a list of *typeDescriptorList, n is the length
+// of the list.
+//go:linkname registerTypeDescriptors runtime.registerTypeDescriptors
+func registerTypeDescriptors(n int, p unsafe.Pointer) {
+	*(*slice)(unsafe.Pointer(&typelist.lists)) = slice{p, n, n}
+}
+
+// The reflect package uses this function to look up a compiler-
+// generated type descriptor.
+//go:linkname reflect_lookupType reflect.lookupType
+func reflect_lookupType(s string) *_type {
+	// Lazy initialization. We don't need to do this if we never create
+	// types through reflection.
+	if atomic.Load(&typelist.initialized) == 0 {
+		lock(&typelistLock)
+		if atomic.Load(&typelist.initialized) == 0 {
+			n := 0
+			for _, list := range typelist.lists {
+				n += list.count
+			}
+			typelist.types = make(map[string]uintptr, n)
+			for _, list := range typelist.lists {
+				for i := 0; i < list.count; i++ {
+					typ := *(**_type)(add(unsafe.Pointer(&list.types), uintptr(i)*sys.PtrSize))
+					typelist.types[typ.string()] = uintptr(unsafe.Pointer(typ))
+				}
+			}
+			atomic.Store(&typelist.initialized, 1)
+		}
+		unlock(&typelistLock)
+	}
+
+	return (*_type)(unsafe.Pointer(typelist.types[s]))
+}