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