From 39c0aa5f74be114ec472a97a12409067b74ac0dc Mon Sep 17 00:00:00 2001 From: Ian Lance Taylor Date: Mon, 3 Jun 2019 23:37:04 +0000 Subject: 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 --- libgo/go/reflect/type.go | 131 +++++++++++++++++++++++------------------------ libgo/go/runtime/type.go | 78 +++++++++++++++++++++++----- 2 files changed, 130 insertions(+), 79 deletions(-) (limited to 'libgo/go') 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])) +} -- cgit v1.1