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 "unsafe"
    10	
    11	// tflag is documented in reflect/type.go.
    12	//
    13	// tflag values must be kept in sync with copies in:
    14	//	cmd/compile/internal/gc/reflect.go
    15	//	cmd/link/internal/ld/decodesym.go
    16	//	reflect/type.go
    17	type tflag uint8
    18	
    19	const (
    20		tflagUncommon  tflag = 1 << 0
    21		tflagExtraStar tflag = 1 << 1
    22		tflagNamed     tflag = 1 << 2
    23	)
    24	
    25	// Needs to be in sync with ../cmd/link/internal/ld/decodesym.go:/^func.commonsize,
    26	// ../cmd/compile/internal/gc/reflect.go:/^func.dcommontype and
    27	// ../reflect/type.go:/^type.rtype.
    28	type _type struct {
    29		size       uintptr
    30		ptrdata    uintptr // size of memory prefix holding all pointers
    31		hash       uint32
    32		tflag      tflag
    33		align      uint8
    34		fieldalign uint8
    35		kind       uint8
    36		alg        *typeAlg
    37		// gcdata stores the GC type data for the garbage collector.
    38		// If the KindGCProg bit is set in kind, gcdata is a GC program.
    39		// Otherwise it is a ptrmask bitmap. See mbitmap.go for details.
    40		gcdata    *byte
    41		str       nameOff
    42		ptrToThis typeOff
    43	}
    44	
    45	func (t *_type) string() string {
    46		s := t.nameOff(t.str).name()
    47		if t.tflag&tflagExtraStar != 0 {
    48			return s[1:]
    49		}
    50		return s
    51	}
    52	
    53	func (t *_type) uncommon() *uncommontype {
    54		if t.tflag&tflagUncommon == 0 {
    55			return nil
    56		}
    57		switch t.kind & kindMask {
    58		case kindStruct:
    59			type u struct {
    60				structtype
    61				u uncommontype
    62			}
    63			return &(*u)(unsafe.Pointer(t)).u
    64		case kindPtr:
    65			type u struct {
    66				ptrtype
    67				u uncommontype
    68			}
    69			return &(*u)(unsafe.Pointer(t)).u
    70		case kindFunc:
    71			type u struct {
    72				functype
    73				u uncommontype
    74			}
    75			return &(*u)(unsafe.Pointer(t)).u
    76		case kindSlice:
    77			type u struct {
    78				slicetype
    79				u uncommontype
    80			}
    81			return &(*u)(unsafe.Pointer(t)).u
    82		case kindArray:
    83			type u struct {
    84				arraytype
    85				u uncommontype
    86			}
    87			return &(*u)(unsafe.Pointer(t)).u
    88		case kindChan:
    89			type u struct {
    90				chantype
    91				u uncommontype
    92			}
    93			return &(*u)(unsafe.Pointer(t)).u
    94		case kindMap:
    95			type u struct {
    96				maptype
    97				u uncommontype
    98			}
    99			return &(*u)(unsafe.Pointer(t)).u
   100		case kindInterface:
   101			type u struct {
   102				interfacetype
   103				u uncommontype
   104			}
   105			return &(*u)(unsafe.Pointer(t)).u
   106		default:
   107			type u struct {
   108				_type
   109				u uncommontype
   110			}
   111			return &(*u)(unsafe.Pointer(t)).u
   112		}
   113	}
   114	
   115	func (t *_type) name() string {
   116		if t.tflag&tflagNamed == 0 {
   117			return ""
   118		}
   119		s := t.string()
   120		i := len(s) - 1
   121		for i >= 0 && s[i] != '.' {
   122			i--
   123		}
   124		return s[i+1:]
   125	}
   126	
   127	// pkgpath returns the path of the package where t was defined, if
   128	// available. This is not the same as the reflect package's PkgPath
   129	// method, in that it returns the package path for struct and interface
   130	// types, not just named types.
   131	func (t *_type) pkgpath() string {
   132		if u := t.uncommon(); u != nil {
   133			return t.nameOff(u.pkgpath).name()
   134		}
   135		switch t.kind & kindMask {
   136		case kindStruct:
   137			st := (*structtype)(unsafe.Pointer(t))
   138			return st.pkgPath.name()
   139		case kindInterface:
   140			it := (*interfacetype)(unsafe.Pointer(t))
   141			return it.pkgpath.name()
   142		}
   143		return ""
   144	}
   145	
   146	// reflectOffs holds type offsets defined at run time by the reflect package.
   147	//
   148	// When a type is defined at run time, its *rtype data lives on the heap.
   149	// There are a wide range of possible addresses the heap may use, that
   150	// may not be representable as a 32-bit offset. Moreover the GC may
   151	// one day start moving heap memory, in which case there is no stable
   152	// offset that can be defined.
   153	//
   154	// To provide stable offsets, we add pin *rtype objects in a global map
   155	// and treat the offset as an identifier. We use negative offsets that
   156	// do not overlap with any compile-time module offsets.
   157	//
   158	// Entries are created by reflect.addReflectOff.
   159	var reflectOffs struct {
   160		lock mutex
   161		next int32
   162		m    map[int32]unsafe.Pointer
   163		minv map[unsafe.Pointer]int32
   164	}
   165	
   166	func reflectOffsLock() {
   167		lock(&reflectOffs.lock)
   168		if raceenabled {
   169			raceacquire(unsafe.Pointer(&reflectOffs.lock))
   170		}
   171	}
   172	
   173	func reflectOffsUnlock() {
   174		if raceenabled {
   175			racerelease(unsafe.Pointer(&reflectOffs.lock))
   176		}
   177		unlock(&reflectOffs.lock)
   178	}
   179	
   180	func resolveNameOff(ptrInModule unsafe.Pointer, off nameOff) name {
   181		if off == 0 {
   182			return name{}
   183		}
   184		base := uintptr(ptrInModule)
   185		for md := &firstmoduledata; md != nil; md = md.next {
   186			if base >= md.types && base < md.etypes {
   187				res := md.types + uintptr(off)
   188				if res > md.etypes {
   189					println("runtime: nameOff", hex(off), "out of range", hex(md.types), "-", hex(md.etypes))
   190					throw("runtime: name offset out of range")
   191				}
   192				return name{(*byte)(unsafe.Pointer(res))}
   193			}
   194		}
   195	
   196		// No module found. see if it is a run time name.
   197		reflectOffsLock()
   198		res, found := reflectOffs.m[int32(off)]
   199		reflectOffsUnlock()
   200		if !found {
   201			println("runtime: nameOff", hex(off), "base", hex(base), "not in ranges:")
   202			for next := &firstmoduledata; next != nil; next = next.next {
   203				println("\ttypes", hex(next.types), "etypes", hex(next.etypes))
   204			}
   205			throw("runtime: name offset base pointer out of range")
   206		}
   207		return name{(*byte)(res)}
   208	}
   209	
   210	func (t *_type) nameOff(off nameOff) name {
   211		return resolveNameOff(unsafe.Pointer(t), off)
   212	}
   213	
   214	func resolveTypeOff(ptrInModule unsafe.Pointer, off typeOff) *_type {
   215		if off == 0 {
   216			return nil
   217		}
   218		base := uintptr(ptrInModule)
   219		var md *moduledata
   220		for next := &firstmoduledata; next != nil; next = next.next {
   221			if base >= next.types && base < next.etypes {
   222				md = next
   223				break
   224			}
   225		}
   226		if md == nil {
   227			reflectOffsLock()
   228			res := reflectOffs.m[int32(off)]
   229			reflectOffsUnlock()
   230			if res == nil {
   231				println("runtime: typeOff", hex(off), "base", hex(base), "not in ranges:")
   232				for next := &firstmoduledata; next != nil; next = next.next {
   233					println("\ttypes", hex(next.types), "etypes", hex(next.etypes))
   234				}
   235				throw("runtime: type offset base pointer out of range")
   236			}
   237			return (*_type)(res)
   238		}
   239		if t := md.typemap[off]; t != nil {
   240			return t
   241		}
   242		res := md.types + uintptr(off)
   243		if res > md.etypes {
   244			println("runtime: typeOff", hex(off), "out of range", hex(md.types), "-", hex(md.etypes))
   245			throw("runtime: type offset out of range")
   246		}
   247		return (*_type)(unsafe.Pointer(res))
   248	}
   249	
   250	func (t *_type) typeOff(off typeOff) *_type {
   251		return resolveTypeOff(unsafe.Pointer(t), off)
   252	}
   253	
   254	func (t *_type) textOff(off textOff) unsafe.Pointer {
   255		base := uintptr(unsafe.Pointer(t))
   256		var md *moduledata
   257		for next := &firstmoduledata; next != nil; next = next.next {
   258			if base >= next.types && base < next.etypes {
   259				md = next
   260				break
   261			}
   262		}
   263		if md == nil {
   264			reflectOffsLock()
   265			res := reflectOffs.m[int32(off)]
   266			reflectOffsUnlock()
   267			if res == nil {
   268				println("runtime: textOff", hex(off), "base", hex(base), "not in ranges:")
   269				for next := &firstmoduledata; next != nil; next = next.next {
   270					println("\ttypes", hex(next.types), "etypes", hex(next.etypes))
   271				}
   272				throw("runtime: text offset base pointer out of range")
   273			}
   274			return res
   275		}
   276		res := uintptr(0)
   277	
   278		// The text, or instruction stream is generated as one large buffer.  The off (offset) for a method is
   279		// its offset within this buffer.  If the total text size gets too large, there can be issues on platforms like ppc64 if
   280		// the target of calls are too far for the call instruction.  To resolve the large text issue, the text is split
   281		// into multiple text sections to allow the linker to generate long calls when necessary.  When this happens, the vaddr
   282		// for each text section is set to its offset within the text.  Each method's offset is compared against the section
   283		// vaddrs and sizes to determine the containing section.  Then the section relative offset is added to the section's
   284		// relocated baseaddr to compute the method addess.
   285	
   286		if len(md.textsectmap) > 1 {
   287			for i := range md.textsectmap {
   288				sectaddr := md.textsectmap[i].vaddr
   289				sectlen := md.textsectmap[i].length
   290				if uintptr(off) >= sectaddr && uintptr(off) < sectaddr+sectlen {
   291					res = md.textsectmap[i].baseaddr + uintptr(off) - uintptr(md.textsectmap[i].vaddr)
   292					break
   293				}
   294			}
   295		} else {
   296			// single text section
   297			res = md.text + uintptr(off)
   298		}
   299	
   300		if res > md.etext && GOARCH != "wasm" { // on wasm, functions do not live in the same address space as the linear memory
   301			println("runtime: textOff", hex(off), "out of range", hex(md.text), "-", hex(md.etext))
   302			throw("runtime: text offset out of range")
   303		}
   304		return unsafe.Pointer(res)
   305	}
   306	
   307	func (t *functype) in() []*_type {
   308		// See funcType in reflect/type.go for details on data layout.
   309		uadd := uintptr(unsafe.Sizeof(functype{}))
   310		if t.typ.tflag&tflagUncommon != 0 {
   311			uadd += unsafe.Sizeof(uncommontype{})
   312		}
   313		return (*[1 << 20]*_type)(add(unsafe.Pointer(t), uadd))[:t.inCount]
   314	}
   315	
   316	func (t *functype) out() []*_type {
   317		// See funcType in reflect/type.go for details on data layout.
   318		uadd := uintptr(unsafe.Sizeof(functype{}))
   319		if t.typ.tflag&tflagUncommon != 0 {
   320			uadd += unsafe.Sizeof(uncommontype{})
   321		}
   322		outCount := t.outCount & (1<<15 - 1)
   323		return (*[1 << 20]*_type)(add(unsafe.Pointer(t), uadd))[t.inCount : t.inCount+outCount]
   324	}
   325	
   326	func (t *functype) dotdotdot() bool {
   327		return t.outCount&(1<<15) != 0
   328	}
   329	
   330	type nameOff int32
   331	type typeOff int32
   332	type textOff int32
   333	
   334	type method struct {
   335		name nameOff
   336		mtyp typeOff
   337		ifn  textOff
   338		tfn  textOff
   339	}
   340	
   341	type uncommontype struct {
   342		pkgpath nameOff
   343		mcount  uint16 // number of methods
   344		xcount  uint16 // number of exported methods
   345		moff    uint32 // offset from this uncommontype to [mcount]method
   346		_       uint32 // unused
   347	}
   348	
   349	type imethod struct {
   350		name nameOff
   351		ityp typeOff
   352	}
   353	
   354	type interfacetype struct {
   355		typ     _type
   356		pkgpath name
   357		mhdr    []imethod
   358	}
   359	
   360	type maptype struct {
   361		typ        _type
   362		key        *_type
   363		elem       *_type
   364		bucket     *_type // internal type representing a hash bucket
   365		keysize    uint8  // size of key slot
   366		elemsize   uint8  // size of elem slot
   367		bucketsize uint16 // size of bucket
   368		flags      uint32
   369	}
   370	
   371	// Note: flag values must match those used in the TMAP case
   372	// in ../cmd/compile/internal/gc/reflect.go:dtypesym.
   373	func (mt *maptype) indirectkey() bool { // store ptr to key instead of key itself
   374		return mt.flags&1 != 0
   375	}
   376	func (mt *maptype) indirectelem() bool { // store ptr to elem instead of elem itself
   377		return mt.flags&2 != 0
   378	}
   379	func (mt *maptype) reflexivekey() bool { // true if k==k for all keys
   380		return mt.flags&4 != 0
   381	}
   382	func (mt *maptype) needkeyupdate() bool { // true if we need to update key on an overwrite
   383		return mt.flags&8 != 0
   384	}
   385	func (mt *maptype) hashMightPanic() bool { // true if hash function might panic
   386		return mt.flags&16 != 0
   387	}
   388	
   389	type arraytype struct {
   390		typ   _type
   391		elem  *_type
   392		slice *_type
   393		len   uintptr
   394	}
   395	
   396	type chantype struct {
   397		typ  _type
   398		elem *_type
   399		dir  uintptr
   400	}
   401	
   402	type slicetype struct {
   403		typ  _type
   404		elem *_type
   405	}
   406	
   407	type functype struct {
   408		typ      _type
   409		inCount  uint16
   410		outCount uint16
   411	}
   412	
   413	type ptrtype struct {
   414		typ  _type
   415		elem *_type
   416	}
   417	
   418	type structfield struct {
   419		name       name
   420		typ        *_type
   421		offsetAnon uintptr
   422	}
   423	
   424	func (f *structfield) offset() uintptr {
   425		return f.offsetAnon >> 1
   426	}
   427	
   428	type structtype struct {
   429		typ     _type
   430		pkgPath name
   431		fields  []structfield
   432	}
   433	
   434	// name is an encoded type name with optional extra data.
   435	// See reflect/type.go for details.
   436	type name struct {
   437		bytes *byte
   438	}
   439	
   440	func (n name) data(off int) *byte {
   441		return (*byte)(add(unsafe.Pointer(n.bytes), uintptr(off)))
   442	}
   443	
   444	func (n name) isExported() bool {
   445		return (*n.bytes)&(1<<0) != 0
   446	}
   447	
   448	func (n name) nameLen() int {
   449		return int(uint16(*n.data(1))<<8 | uint16(*n.data(2)))
   450	}
   451	
   452	func (n name) tagLen() int {
   453		if *n.data(0)&(1<<1) == 0 {
   454			return 0
   455		}
   456		off := 3 + n.nameLen()
   457		return int(uint16(*n.data(off))<<8 | uint16(*n.data(off + 1)))
   458	}
   459	
   460	func (n name) name() (s string) {
   461		if n.bytes == nil {
   462			return ""
   463		}
   464		nl := n.nameLen()
   465		if nl == 0 {
   466			return ""
   467		}
   468		hdr := (*stringStruct)(unsafe.Pointer(&s))
   469		hdr.str = unsafe.Pointer(n.data(3))
   470		hdr.len = nl
   471		return s
   472	}
   473	
   474	func (n name) tag() (s string) {
   475		tl := n.tagLen()
   476		if tl == 0 {
   477			return ""
   478		}
   479		nl := n.nameLen()
   480		hdr := (*stringStruct)(unsafe.Pointer(&s))
   481		hdr.str = unsafe.Pointer(n.data(3 + nl + 2))
   482		hdr.len = tl
   483		return s
   484	}
   485	
   486	func (n name) pkgPath() string {
   487		if n.bytes == nil || *n.data(0)&(1<<2) == 0 {
   488			return ""
   489		}
   490		off := 3 + n.nameLen()
   491		if tl := n.tagLen(); tl > 0 {
   492			off += 2 + tl
   493		}
   494		var nameOff nameOff
   495		copy((*[4]byte)(unsafe.Pointer(&nameOff))[:], (*[4]byte)(unsafe.Pointer(n.data(off)))[:])
   496		pkgPathName := resolveNameOff(unsafe.Pointer(n.bytes), nameOff)
   497		return pkgPathName.name()
   498	}
   499	
   500	// typelinksinit scans the types from extra modules and builds the
   501	// moduledata typemap used to de-duplicate type pointers.
   502	func typelinksinit() {
   503		if firstmoduledata.next == nil {
   504			return
   505		}
   506		typehash := make(map[uint32][]*_type, len(firstmoduledata.typelinks))
   507	
   508		modules := activeModules()
   509		prev := modules[0]
   510		for _, md := range modules[1:] {
   511			// Collect types from the previous module into typehash.
   512		collect:
   513			for _, tl := range prev.typelinks {
   514				var t *_type
   515				if prev.typemap == nil {
   516					t = (*_type)(unsafe.Pointer(prev.types + uintptr(tl)))
   517				} else {
   518					t = prev.typemap[typeOff(tl)]
   519				}
   520				// Add to typehash if not seen before.
   521				tlist := typehash[t.hash]
   522				for _, tcur := range tlist {
   523					if tcur == t {
   524						continue collect
   525					}
   526				}
   527				typehash[t.hash] = append(tlist, t)
   528			}
   529	
   530			if md.typemap == nil {
   531				// If any of this module's typelinks match a type from a
   532				// prior module, prefer that prior type by adding the offset
   533				// to this module's typemap.
   534				tm := make(map[typeOff]*_type, len(md.typelinks))
   535				pinnedTypemaps = append(pinnedTypemaps, tm)
   536				md.typemap = tm
   537				for _, tl := range md.typelinks {
   538					t := (*_type)(unsafe.Pointer(md.types + uintptr(tl)))
   539					for _, candidate := range typehash[t.hash] {
   540						seen := map[_typePair]struct{}{}
   541						if typesEqual(t, candidate, seen) {
   542							t = candidate
   543							break
   544						}
   545					}
   546					md.typemap[typeOff(tl)] = t
   547				}
   548			}
   549	
   550			prev = md
   551		}
   552	}
   553	
   554	type _typePair struct {
   555		t1 *_type
   556		t2 *_type
   557	}
   558	
   559	// typesEqual reports whether two types are equal.
   560	//
   561	// Everywhere in the runtime and reflect packages, it is assumed that
   562	// there is exactly one *_type per Go type, so that pointer equality
   563	// can be used to test if types are equal. There is one place that
   564	// breaks this assumption: buildmode=shared. In this case a type can
   565	// appear as two different pieces of memory. This is hidden from the
   566	// runtime and reflect package by the per-module typemap built in
   567	// typelinksinit. It uses typesEqual to map types from later modules
   568	// back into earlier ones.
   569	//
   570	// Only typelinksinit needs this function.
   571	func typesEqual(t, v *_type, seen map[_typePair]struct{}) bool {
   572		tp := _typePair{t, v}
   573		if _, ok := seen[tp]; ok {
   574			return true
   575		}
   576	
   577		// mark these types as seen, and thus equivalent which prevents an infinite loop if
   578		// the two types are identical, but recursively defined and loaded from
   579		// different modules
   580		seen[tp] = struct{}{}
   581	
   582		if t == v {
   583			return true
   584		}
   585		kind := t.kind & kindMask
   586		if kind != v.kind&kindMask {
   587			return false
   588		}
   589		if t.string() != v.string() {
   590			return false
   591		}
   592		ut := t.uncommon()
   593		uv := v.uncommon()
   594		if ut != nil || uv != nil {
   595			if ut == nil || uv == nil {
   596				return false
   597			}
   598			pkgpatht := t.nameOff(ut.pkgpath).name()
   599			pkgpathv := v.nameOff(uv.pkgpath).name()
   600			if pkgpatht != pkgpathv {
   601				return false
   602			}
   603		}
   604		if kindBool <= kind && kind <= kindComplex128 {
   605			return true
   606		}
   607		switch kind {
   608		case kindString, kindUnsafePointer:
   609			return true
   610		case kindArray:
   611			at := (*arraytype)(unsafe.Pointer(t))
   612			av := (*arraytype)(unsafe.Pointer(v))
   613			return typesEqual(at.elem, av.elem, seen) && at.len == av.len
   614		case kindChan:
   615			ct := (*chantype)(unsafe.Pointer(t))
   616			cv := (*chantype)(unsafe.Pointer(v))
   617			return ct.dir == cv.dir && typesEqual(ct.elem, cv.elem, seen)
   618		case kindFunc:
   619			ft := (*functype)(unsafe.Pointer(t))
   620			fv := (*functype)(unsafe.Pointer(v))
   621			if ft.outCount != fv.outCount || ft.inCount != fv.inCount {
   622				return false
   623			}
   624			tin, vin := ft.in(), fv.in()
   625			for i := 0; i < len(tin); i++ {
   626				if !typesEqual(tin[i], vin[i], seen) {
   627					return false
   628				}
   629			}
   630			tout, vout := ft.out(), fv.out()
   631			for i := 0; i < len(tout); i++ {
   632				if !typesEqual(tout[i], vout[i], seen) {
   633					return false
   634				}
   635			}
   636			return true
   637		case kindInterface:
   638			it := (*interfacetype)(unsafe.Pointer(t))
   639			iv := (*interfacetype)(unsafe.Pointer(v))
   640			if it.pkgpath.name() != iv.pkgpath.name() {
   641				return false
   642			}
   643			if len(it.mhdr) != len(iv.mhdr) {
   644				return false
   645			}
   646			for i := range it.mhdr {
   647				tm := &it.mhdr[i]
   648				vm := &iv.mhdr[i]
   649				// Note the mhdr array can be relocated from
   650				// another module. See #17724.
   651				tname := resolveNameOff(unsafe.Pointer(tm), tm.name)
   652				vname := resolveNameOff(unsafe.Pointer(vm), vm.name)
   653				if tname.name() != vname.name() {
   654					return false
   655				}
   656				if tname.pkgPath() != vname.pkgPath() {
   657					return false
   658				}
   659				tityp := resolveTypeOff(unsafe.Pointer(tm), tm.ityp)
   660				vityp := resolveTypeOff(unsafe.Pointer(vm), vm.ityp)
   661				if !typesEqual(tityp, vityp, seen) {
   662					return false
   663				}
   664			}
   665			return true
   666		case kindMap:
   667			mt := (*maptype)(unsafe.Pointer(t))
   668			mv := (*maptype)(unsafe.Pointer(v))
   669			return typesEqual(mt.key, mv.key, seen) && typesEqual(mt.elem, mv.elem, seen)
   670		case kindPtr:
   671			pt := (*ptrtype)(unsafe.Pointer(t))
   672			pv := (*ptrtype)(unsafe.Pointer(v))
   673			return typesEqual(pt.elem, pv.elem, seen)
   674		case kindSlice:
   675			st := (*slicetype)(unsafe.Pointer(t))
   676			sv := (*slicetype)(unsafe.Pointer(v))
   677			return typesEqual(st.elem, sv.elem, seen)
   678		case kindStruct:
   679			st := (*structtype)(unsafe.Pointer(t))
   680			sv := (*structtype)(unsafe.Pointer(v))
   681			if len(st.fields) != len(sv.fields) {
   682				return false
   683			}
   684			if st.pkgPath.name() != sv.pkgPath.name() {
   685				return false
   686			}
   687			for i := range st.fields {
   688				tf := &st.fields[i]
   689				vf := &sv.fields[i]
   690				if tf.name.name() != vf.name.name() {
   691					return false
   692				}
   693				if !typesEqual(tf.typ, vf.typ, seen) {
   694					return false
   695				}
   696				if tf.name.tag() != vf.name.tag() {
   697					return false
   698				}
   699				if tf.offsetAnon != vf.offsetAnon {
   700					return false
   701				}
   702			}
   703			return true
   704		default:
   705			println("runtime: impossible type kind", kind)
   706			throw("runtime: impossible type kind")
   707			return false
   708		}
   709	}
   710	

View as plain text