Source file src/runtime/type.go

     1  // Copyright 2009 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Runtime type representation.
     6  
     7  package runtime
     8  
     9  import (
    10  	"internal/abi"
    11  	"unsafe"
    12  )
    13  
    14  type nameOff = abi.NameOff
    15  type typeOff = abi.TypeOff
    16  type textOff = abi.TextOff
    17  
    18  type _type = abi.Type
    19  
    20  // rtype is a wrapper that allows us to define additional methods.
    21  type rtype struct {
    22  	*abi.Type // embedding is okay here (unlike reflect) because none of this is public
    23  }
    24  
    25  func (t rtype) string() string {
    26  	s := t.nameOff(t.Str).Name()
    27  	if t.TFlag&abi.TFlagExtraStar != 0 {
    28  		return s[1:]
    29  	}
    30  	return s
    31  }
    32  
    33  func (t rtype) uncommon() *uncommontype {
    34  	return t.Uncommon()
    35  }
    36  
    37  func (t rtype) name() string {
    38  	if t.TFlag&abi.TFlagNamed == 0 {
    39  		return ""
    40  	}
    41  	s := t.string()
    42  	i := len(s) - 1
    43  	sqBrackets := 0
    44  	for i >= 0 && (s[i] != '.' || sqBrackets != 0) {
    45  		switch s[i] {
    46  		case ']':
    47  			sqBrackets++
    48  		case '[':
    49  			sqBrackets--
    50  		}
    51  		i--
    52  	}
    53  	return s[i+1:]
    54  }
    55  
    56  // pkgpath returns the path of the package where t was defined, if
    57  // available. This is not the same as the reflect package's PkgPath
    58  // method, in that it returns the package path for struct and interface
    59  // types, not just named types.
    60  func (t rtype) pkgpath() string {
    61  	if u := t.uncommon(); u != nil {
    62  		return t.nameOff(u.PkgPath).Name()
    63  	}
    64  	switch t.Kind_ & kindMask {
    65  	case kindStruct:
    66  		st := (*structtype)(unsafe.Pointer(t.Type))
    67  		return st.PkgPath.Name()
    68  	case kindInterface:
    69  		it := (*interfacetype)(unsafe.Pointer(t.Type))
    70  		return it.PkgPath.Name()
    71  	}
    72  	return ""
    73  }
    74  
    75  // reflectOffs holds type offsets defined at run time by the reflect package.
    76  //
    77  // When a type is defined at run time, its *rtype data lives on the heap.
    78  // There are a wide range of possible addresses the heap may use, that
    79  // may not be representable as a 32-bit offset. Moreover the GC may
    80  // one day start moving heap memory, in which case there is no stable
    81  // offset that can be defined.
    82  //
    83  // To provide stable offsets, we add pin *rtype objects in a global map
    84  // and treat the offset as an identifier. We use negative offsets that
    85  // do not overlap with any compile-time module offsets.
    86  //
    87  // Entries are created by reflect.addReflectOff.
    88  var reflectOffs struct {
    89  	lock mutex
    90  	next int32
    91  	m    map[int32]unsafe.Pointer
    92  	minv map[unsafe.Pointer]int32
    93  }
    94  
    95  func reflectOffsLock() {
    96  	lock(&reflectOffs.lock)
    97  	if raceenabled {
    98  		raceacquire(unsafe.Pointer(&reflectOffs.lock))
    99  	}
   100  }
   101  
   102  func reflectOffsUnlock() {
   103  	if raceenabled {
   104  		racerelease(unsafe.Pointer(&reflectOffs.lock))
   105  	}
   106  	unlock(&reflectOffs.lock)
   107  }
   108  
   109  func resolveNameOff(ptrInModule unsafe.Pointer, off nameOff) name {
   110  	if off == 0 {
   111  		return name{}
   112  	}
   113  	base := uintptr(ptrInModule)
   114  	for md := &firstmoduledata; md != nil; md = md.next {
   115  		if base >= md.types && base < md.etypes {
   116  			res := md.types + uintptr(off)
   117  			if res > md.etypes {
   118  				println("runtime: nameOff", hex(off), "out of range", hex(md.types), "-", hex(md.etypes))
   119  				throw("runtime: name offset out of range")
   120  			}
   121  			return name{Bytes: (*byte)(unsafe.Pointer(res))}
   122  		}
   123  	}
   124  
   125  	// No module found. see if it is a run time name.
   126  	reflectOffsLock()
   127  	res, found := reflectOffs.m[int32(off)]
   128  	reflectOffsUnlock()
   129  	if !found {
   130  		println("runtime: nameOff", hex(off), "base", hex(base), "not in ranges:")
   131  		for next := &firstmoduledata; next != nil; next = next.next {
   132  			println("\ttypes", hex(next.types), "etypes", hex(next.etypes))
   133  		}
   134  		throw("runtime: name offset base pointer out of range")
   135  	}
   136  	return name{Bytes: (*byte)(res)}
   137  }
   138  
   139  func (t rtype) nameOff(off nameOff) name {
   140  	return resolveNameOff(unsafe.Pointer(t.Type), off)
   141  }
   142  
   143  func resolveTypeOff(ptrInModule unsafe.Pointer, off typeOff) *_type {
   144  	if off == 0 || off == -1 {
   145  		// -1 is the sentinel value for unreachable code.
   146  		// See cmd/link/internal/ld/data.go:relocsym.
   147  		return nil
   148  	}
   149  	base := uintptr(ptrInModule)
   150  	var md *moduledata
   151  	for next := &firstmoduledata; next != nil; next = next.next {
   152  		if base >= next.types && base < next.etypes {
   153  			md = next
   154  			break
   155  		}
   156  	}
   157  	if md == nil {
   158  		reflectOffsLock()
   159  		res := reflectOffs.m[int32(off)]
   160  		reflectOffsUnlock()
   161  		if res == nil {
   162  			println("runtime: typeOff", hex(off), "base", hex(base), "not in ranges:")
   163  			for next := &firstmoduledata; next != nil; next = next.next {
   164  				println("\ttypes", hex(next.types), "etypes", hex(next.etypes))
   165  			}
   166  			throw("runtime: type offset base pointer out of range")
   167  		}
   168  		return (*_type)(res)
   169  	}
   170  	if t := md.typemap[off]; t != nil {
   171  		return t
   172  	}
   173  	res := md.types + uintptr(off)
   174  	if res > md.etypes {
   175  		println("runtime: typeOff", hex(off), "out of range", hex(md.types), "-", hex(md.etypes))
   176  		throw("runtime: type offset out of range")
   177  	}
   178  	return (*_type)(unsafe.Pointer(res))
   179  }
   180  
   181  func (t rtype) typeOff(off typeOff) *_type {
   182  	return resolveTypeOff(unsafe.Pointer(t.Type), off)
   183  }
   184  
   185  func (t rtype) textOff(off textOff) unsafe.Pointer {
   186  	if off == -1 {
   187  		// -1 is the sentinel value for unreachable code.
   188  		// See cmd/link/internal/ld/data.go:relocsym.
   189  		return unsafe.Pointer(abi.FuncPCABIInternal(unreachableMethod))
   190  	}
   191  	base := uintptr(unsafe.Pointer(t.Type))
   192  	var md *moduledata
   193  	for next := &firstmoduledata; next != nil; next = next.next {
   194  		if base >= next.types && base < next.etypes {
   195  			md = next
   196  			break
   197  		}
   198  	}
   199  	if md == nil {
   200  		reflectOffsLock()
   201  		res := reflectOffs.m[int32(off)]
   202  		reflectOffsUnlock()
   203  		if res == nil {
   204  			println("runtime: textOff", hex(off), "base", hex(base), "not in ranges:")
   205  			for next := &firstmoduledata; next != nil; next = next.next {
   206  				println("\ttypes", hex(next.types), "etypes", hex(next.etypes))
   207  			}
   208  			throw("runtime: text offset base pointer out of range")
   209  		}
   210  		return res
   211  	}
   212  	res := md.textAddr(uint32(off))
   213  	return unsafe.Pointer(res)
   214  }
   215  
   216  type uncommontype = abi.UncommonType
   217  
   218  type interfacetype = abi.InterfaceType
   219  
   220  type maptype = abi.MapType
   221  
   222  type arraytype = abi.ArrayType
   223  
   224  type chantype = abi.ChanType
   225  
   226  type slicetype = abi.SliceType
   227  
   228  type functype = abi.FuncType
   229  
   230  type ptrtype = abi.PtrType
   231  
   232  type name = abi.Name
   233  
   234  type structtype = abi.StructType
   235  
   236  func pkgPath(n name) string {
   237  	if n.Bytes == nil || *n.Data(0)&(1<<2) == 0 {
   238  		return ""
   239  	}
   240  	i, l := n.ReadVarint(1)
   241  	off := 1 + i + l
   242  	if *n.Data(0)&(1<<1) != 0 {
   243  		i2, l2 := n.ReadVarint(off)
   244  		off += i2 + l2
   245  	}
   246  	var nameOff nameOff
   247  	copy((*[4]byte)(unsafe.Pointer(&nameOff))[:], (*[4]byte)(unsafe.Pointer(n.Data(off)))[:])
   248  	pkgPathName := resolveNameOff(unsafe.Pointer(n.Bytes), nameOff)
   249  	return pkgPathName.Name()
   250  }
   251  
   252  // typelinksinit scans the types from extra modules and builds the
   253  // moduledata typemap used to de-duplicate type pointers.
   254  func typelinksinit() {
   255  	if firstmoduledata.next == nil {
   256  		return
   257  	}
   258  	typehash := make(map[uint32][]*_type, len(firstmoduledata.typelinks))
   259  
   260  	modules := activeModules()
   261  	prev := modules[0]
   262  	for _, md := range modules[1:] {
   263  		// Collect types from the previous module into typehash.
   264  	collect:
   265  		for _, tl := range prev.typelinks {
   266  			var t *_type
   267  			if prev.typemap == nil {
   268  				t = (*_type)(unsafe.Pointer(prev.types + uintptr(tl)))
   269  			} else {
   270  				t = prev.typemap[typeOff(tl)]
   271  			}
   272  			// Add to typehash if not seen before.
   273  			tlist := typehash[t.Hash]
   274  			for _, tcur := range tlist {
   275  				if tcur == t {
   276  					continue collect
   277  				}
   278  			}
   279  			typehash[t.Hash] = append(tlist, t)
   280  		}
   281  
   282  		if md.typemap == nil {
   283  			// If any of this module's typelinks match a type from a
   284  			// prior module, prefer that prior type by adding the offset
   285  			// to this module's typemap.
   286  			tm := make(map[typeOff]*_type, len(md.typelinks))
   287  			pinnedTypemaps = append(pinnedTypemaps, tm)
   288  			md.typemap = tm
   289  			for _, tl := range md.typelinks {
   290  				t := (*_type)(unsafe.Pointer(md.types + uintptr(tl)))
   291  				for _, candidate := range typehash[t.Hash] {
   292  					seen := map[_typePair]struct{}{}
   293  					if typesEqual(t, candidate, seen) {
   294  						t = candidate
   295  						break
   296  					}
   297  				}
   298  				md.typemap[typeOff(tl)] = t
   299  			}
   300  		}
   301  
   302  		prev = md
   303  	}
   304  }
   305  
   306  type _typePair struct {
   307  	t1 *_type
   308  	t2 *_type
   309  }
   310  
   311  func toRType(t *abi.Type) rtype {
   312  	return rtype{t}
   313  }
   314  
   315  // typesEqual reports whether two types are equal.
   316  //
   317  // Everywhere in the runtime and reflect packages, it is assumed that
   318  // there is exactly one *_type per Go type, so that pointer equality
   319  // can be used to test if types are equal. There is one place that
   320  // breaks this assumption: buildmode=shared. In this case a type can
   321  // appear as two different pieces of memory. This is hidden from the
   322  // runtime and reflect package by the per-module typemap built in
   323  // typelinksinit. It uses typesEqual to map types from later modules
   324  // back into earlier ones.
   325  //
   326  // Only typelinksinit needs this function.
   327  func typesEqual(t, v *_type, seen map[_typePair]struct{}) bool {
   328  	tp := _typePair{t, v}
   329  	if _, ok := seen[tp]; ok {
   330  		return true
   331  	}
   332  
   333  	// mark these types as seen, and thus equivalent which prevents an infinite loop if
   334  	// the two types are identical, but recursively defined and loaded from
   335  	// different modules
   336  	seen[tp] = struct{}{}
   337  
   338  	if t == v {
   339  		return true
   340  	}
   341  	kind := t.Kind_ & kindMask
   342  	if kind != v.Kind_&kindMask {
   343  		return false
   344  	}
   345  	rt, rv := toRType(t), toRType(v)
   346  	if rt.string() != rv.string() {
   347  		return false
   348  	}
   349  	ut := t.Uncommon()
   350  	uv := v.Uncommon()
   351  	if ut != nil || uv != nil {
   352  		if ut == nil || uv == nil {
   353  			return false
   354  		}
   355  		pkgpatht := rt.nameOff(ut.PkgPath).Name()
   356  		pkgpathv := rv.nameOff(uv.PkgPath).Name()
   357  		if pkgpatht != pkgpathv {
   358  			return false
   359  		}
   360  	}
   361  	if kindBool <= kind && kind <= kindComplex128 {
   362  		return true
   363  	}
   364  	switch kind {
   365  	case kindString, kindUnsafePointer:
   366  		return true
   367  	case kindArray:
   368  		at := (*arraytype)(unsafe.Pointer(t))
   369  		av := (*arraytype)(unsafe.Pointer(v))
   370  		return typesEqual(at.Elem, av.Elem, seen) && at.Len == av.Len
   371  	case kindChan:
   372  		ct := (*chantype)(unsafe.Pointer(t))
   373  		cv := (*chantype)(unsafe.Pointer(v))
   374  		return ct.Dir == cv.Dir && typesEqual(ct.Elem, cv.Elem, seen)
   375  	case kindFunc:
   376  		ft := (*functype)(unsafe.Pointer(t))
   377  		fv := (*functype)(unsafe.Pointer(v))
   378  		if ft.OutCount != fv.OutCount || ft.InCount != fv.InCount {
   379  			return false
   380  		}
   381  		tin, vin := ft.InSlice(), fv.InSlice()
   382  		for i := 0; i < len(tin); i++ {
   383  			if !typesEqual(tin[i], vin[i], seen) {
   384  				return false
   385  			}
   386  		}
   387  		tout, vout := ft.OutSlice(), fv.OutSlice()
   388  		for i := 0; i < len(tout); i++ {
   389  			if !typesEqual(tout[i], vout[i], seen) {
   390  				return false
   391  			}
   392  		}
   393  		return true
   394  	case kindInterface:
   395  		it := (*interfacetype)(unsafe.Pointer(t))
   396  		iv := (*interfacetype)(unsafe.Pointer(v))
   397  		if it.PkgPath.Name() != iv.PkgPath.Name() {
   398  			return false
   399  		}
   400  		if len(it.Methods) != len(iv.Methods) {
   401  			return false
   402  		}
   403  		for i := range it.Methods {
   404  			tm := &it.Methods[i]
   405  			vm := &iv.Methods[i]
   406  			// Note the mhdr array can be relocated from
   407  			// another module. See #17724.
   408  			tname := resolveNameOff(unsafe.Pointer(tm), tm.Name)
   409  			vname := resolveNameOff(unsafe.Pointer(vm), vm.Name)
   410  			if tname.Name() != vname.Name() {
   411  				return false
   412  			}
   413  			if pkgPath(tname) != pkgPath(vname) {
   414  				return false
   415  			}
   416  			tityp := resolveTypeOff(unsafe.Pointer(tm), tm.Typ)
   417  			vityp := resolveTypeOff(unsafe.Pointer(vm), vm.Typ)
   418  			if !typesEqual(tityp, vityp, seen) {
   419  				return false
   420  			}
   421  		}
   422  		return true
   423  	case kindMap:
   424  		mt := (*maptype)(unsafe.Pointer(t))
   425  		mv := (*maptype)(unsafe.Pointer(v))
   426  		return typesEqual(mt.Key, mv.Key, seen) && typesEqual(mt.Elem, mv.Elem, seen)
   427  	case kindPtr:
   428  		pt := (*ptrtype)(unsafe.Pointer(t))
   429  		pv := (*ptrtype)(unsafe.Pointer(v))
   430  		return typesEqual(pt.Elem, pv.Elem, seen)
   431  	case kindSlice:
   432  		st := (*slicetype)(unsafe.Pointer(t))
   433  		sv := (*slicetype)(unsafe.Pointer(v))
   434  		return typesEqual(st.Elem, sv.Elem, seen)
   435  	case kindStruct:
   436  		st := (*structtype)(unsafe.Pointer(t))
   437  		sv := (*structtype)(unsafe.Pointer(v))
   438  		if len(st.Fields) != len(sv.Fields) {
   439  			return false
   440  		}
   441  		if st.PkgPath.Name() != sv.PkgPath.Name() {
   442  			return false
   443  		}
   444  		for i := range st.Fields {
   445  			tf := &st.Fields[i]
   446  			vf := &sv.Fields[i]
   447  			if tf.Name.Name() != vf.Name.Name() {
   448  				return false
   449  			}
   450  			if !typesEqual(tf.Typ, vf.Typ, seen) {
   451  				return false
   452  			}
   453  			if tf.Name.Tag() != vf.Name.Tag() {
   454  				return false
   455  			}
   456  			if tf.Offset != vf.Offset {
   457  				return false
   458  			}
   459  			if tf.Name.IsEmbedded() != vf.Name.IsEmbedded() {
   460  				return false
   461  			}
   462  		}
   463  		return true
   464  	default:
   465  		println("runtime: impossible type kind", kind)
   466  		throw("runtime: impossible type kind")
   467  		return false
   468  	}
   469  }
   470  

View as plain text