Source file src/runtime/iface.go

     1  // Copyright 2014 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  package runtime
     6  
     7  import (
     8  	"internal/abi"
     9  	"internal/goarch"
    10  	"runtime/internal/atomic"
    11  	"unsafe"
    12  )
    13  
    14  const itabInitSize = 512
    15  
    16  var (
    17  	itabLock      mutex                               // lock for accessing itab table
    18  	itabTable     = &itabTableInit                    // pointer to current table
    19  	itabTableInit = itabTableType{size: itabInitSize} // starter table
    20  )
    21  
    22  // Note: change the formula in the mallocgc call in itabAdd if you change these fields.
    23  type itabTableType struct {
    24  	size    uintptr             // length of entries array. Always a power of 2.
    25  	count   uintptr             // current number of filled entries.
    26  	entries [itabInitSize]*itab // really [size] large
    27  }
    28  
    29  func itabHashFunc(inter *interfacetype, typ *_type) uintptr {
    30  	// compiler has provided some good hash codes for us.
    31  	return uintptr(inter.Type.Hash ^ typ.Hash)
    32  }
    33  
    34  func getitab(inter *interfacetype, typ *_type, canfail bool) *itab {
    35  	if len(inter.Methods) == 0 {
    36  		throw("internal error - misuse of itab")
    37  	}
    38  
    39  	// easy case
    40  	if typ.TFlag&abi.TFlagUncommon == 0 {
    41  		if canfail {
    42  			return nil
    43  		}
    44  		name := toRType(&inter.Type).nameOff(inter.Methods[0].Name)
    45  		panic(&TypeAssertionError{nil, typ, &inter.Type, name.Name()})
    46  	}
    47  
    48  	var m *itab
    49  
    50  	// First, look in the existing table to see if we can find the itab we need.
    51  	// This is by far the most common case, so do it without locks.
    52  	// Use atomic to ensure we see any previous writes done by the thread
    53  	// that updates the itabTable field (with atomic.Storep in itabAdd).
    54  	t := (*itabTableType)(atomic.Loadp(unsafe.Pointer(&itabTable)))
    55  	if m = t.find(inter, typ); m != nil {
    56  		goto finish
    57  	}
    58  
    59  	// Not found.  Grab the lock and try again.
    60  	lock(&itabLock)
    61  	if m = itabTable.find(inter, typ); m != nil {
    62  		unlock(&itabLock)
    63  		goto finish
    64  	}
    65  
    66  	// Entry doesn't exist yet. Make a new entry & add it.
    67  	m = (*itab)(persistentalloc(unsafe.Sizeof(itab{})+uintptr(len(inter.Methods)-1)*goarch.PtrSize, 0, &memstats.other_sys))
    68  	m.inter = inter
    69  	m._type = typ
    70  	// The hash is used in type switches. However, compiler statically generates itab's
    71  	// for all interface/type pairs used in switches (which are added to itabTable
    72  	// in itabsinit). The dynamically-generated itab's never participate in type switches,
    73  	// and thus the hash is irrelevant.
    74  	// Note: m.hash is _not_ the hash used for the runtime itabTable hash table.
    75  	m.hash = 0
    76  	m.init()
    77  	itabAdd(m)
    78  	unlock(&itabLock)
    79  finish:
    80  	if m.fun[0] != 0 {
    81  		return m
    82  	}
    83  	if canfail {
    84  		return nil
    85  	}
    86  	// this can only happen if the conversion
    87  	// was already done once using the , ok form
    88  	// and we have a cached negative result.
    89  	// The cached result doesn't record which
    90  	// interface function was missing, so initialize
    91  	// the itab again to get the missing function name.
    92  	panic(&TypeAssertionError{concrete: typ, asserted: &inter.Type, missingMethod: m.init()})
    93  }
    94  
    95  // find finds the given interface/type pair in t.
    96  // Returns nil if the given interface/type pair isn't present.
    97  func (t *itabTableType) find(inter *interfacetype, typ *_type) *itab {
    98  	// Implemented using quadratic probing.
    99  	// Probe sequence is h(i) = h0 + i*(i+1)/2 mod 2^k.
   100  	// We're guaranteed to hit all table entries using this probe sequence.
   101  	mask := t.size - 1
   102  	h := itabHashFunc(inter, typ) & mask
   103  	for i := uintptr(1); ; i++ {
   104  		p := (**itab)(add(unsafe.Pointer(&t.entries), h*goarch.PtrSize))
   105  		// Use atomic read here so if we see m != nil, we also see
   106  		// the initializations of the fields of m.
   107  		// m := *p
   108  		m := (*itab)(atomic.Loadp(unsafe.Pointer(p)))
   109  		if m == nil {
   110  			return nil
   111  		}
   112  		if m.inter == inter && m._type == typ {
   113  			return m
   114  		}
   115  		h += i
   116  		h &= mask
   117  	}
   118  }
   119  
   120  // itabAdd adds the given itab to the itab hash table.
   121  // itabLock must be held.
   122  func itabAdd(m *itab) {
   123  	// Bugs can lead to calling this while mallocing is set,
   124  	// typically because this is called while panicking.
   125  	// Crash reliably, rather than only when we need to grow
   126  	// the hash table.
   127  	if getg().m.mallocing != 0 {
   128  		throw("malloc deadlock")
   129  	}
   130  
   131  	t := itabTable
   132  	if t.count >= 3*(t.size/4) { // 75% load factor
   133  		// Grow hash table.
   134  		// t2 = new(itabTableType) + some additional entries
   135  		// We lie and tell malloc we want pointer-free memory because
   136  		// all the pointed-to values are not in the heap.
   137  		t2 := (*itabTableType)(mallocgc((2+2*t.size)*goarch.PtrSize, nil, true))
   138  		t2.size = t.size * 2
   139  
   140  		// Copy over entries.
   141  		// Note: while copying, other threads may look for an itab and
   142  		// fail to find it. That's ok, they will then try to get the itab lock
   143  		// and as a consequence wait until this copying is complete.
   144  		iterate_itabs(t2.add)
   145  		if t2.count != t.count {
   146  			throw("mismatched count during itab table copy")
   147  		}
   148  		// Publish new hash table. Use an atomic write: see comment in getitab.
   149  		atomicstorep(unsafe.Pointer(&itabTable), unsafe.Pointer(t2))
   150  		// Adopt the new table as our own.
   151  		t = itabTable
   152  		// Note: the old table can be GC'ed here.
   153  	}
   154  	t.add(m)
   155  }
   156  
   157  // add adds the given itab to itab table t.
   158  // itabLock must be held.
   159  func (t *itabTableType) add(m *itab) {
   160  	// See comment in find about the probe sequence.
   161  	// Insert new itab in the first empty spot in the probe sequence.
   162  	mask := t.size - 1
   163  	h := itabHashFunc(m.inter, m._type) & mask
   164  	for i := uintptr(1); ; i++ {
   165  		p := (**itab)(add(unsafe.Pointer(&t.entries), h*goarch.PtrSize))
   166  		m2 := *p
   167  		if m2 == m {
   168  			// A given itab may be used in more than one module
   169  			// and thanks to the way global symbol resolution works, the
   170  			// pointed-to itab may already have been inserted into the
   171  			// global 'hash'.
   172  			return
   173  		}
   174  		if m2 == nil {
   175  			// Use atomic write here so if a reader sees m, it also
   176  			// sees the correctly initialized fields of m.
   177  			// NoWB is ok because m is not in heap memory.
   178  			// *p = m
   179  			atomic.StorepNoWB(unsafe.Pointer(p), unsafe.Pointer(m))
   180  			t.count++
   181  			return
   182  		}
   183  		h += i
   184  		h &= mask
   185  	}
   186  }
   187  
   188  // init fills in the m.fun array with all the code pointers for
   189  // the m.inter/m._type pair. If the type does not implement the interface,
   190  // it sets m.fun[0] to 0 and returns the name of an interface function that is missing.
   191  // It is ok to call this multiple times on the same m, even concurrently.
   192  func (m *itab) init() string {
   193  	inter := m.inter
   194  	typ := m._type
   195  	x := typ.Uncommon()
   196  
   197  	// both inter and typ have method sorted by name,
   198  	// and interface names are unique,
   199  	// so can iterate over both in lock step;
   200  	// the loop is O(ni+nt) not O(ni*nt).
   201  	ni := len(inter.Methods)
   202  	nt := int(x.Mcount)
   203  	xmhdr := (*[1 << 16]abi.Method)(add(unsafe.Pointer(x), uintptr(x.Moff)))[:nt:nt]
   204  	j := 0
   205  	methods := (*[1 << 16]unsafe.Pointer)(unsafe.Pointer(&m.fun[0]))[:ni:ni]
   206  	var fun0 unsafe.Pointer
   207  imethods:
   208  	for k := 0; k < ni; k++ {
   209  		i := &inter.Methods[k]
   210  		itype := toRType(&inter.Type).typeOff(i.Typ)
   211  		name := toRType(&inter.Type).nameOff(i.Name)
   212  		iname := name.Name()
   213  		ipkg := pkgPath(name)
   214  		if ipkg == "" {
   215  			ipkg = inter.PkgPath.Name()
   216  		}
   217  		for ; j < nt; j++ {
   218  			t := &xmhdr[j]
   219  			rtyp := toRType(typ)
   220  			tname := rtyp.nameOff(t.Name)
   221  			if rtyp.typeOff(t.Mtyp) == itype && tname.Name() == iname {
   222  				pkgPath := pkgPath(tname)
   223  				if pkgPath == "" {
   224  					pkgPath = rtyp.nameOff(x.PkgPath).Name()
   225  				}
   226  				if tname.IsExported() || pkgPath == ipkg {
   227  					if m != nil {
   228  						ifn := rtyp.textOff(t.Ifn)
   229  						if k == 0 {
   230  							fun0 = ifn // we'll set m.fun[0] at the end
   231  						} else {
   232  							methods[k] = ifn
   233  						}
   234  					}
   235  					continue imethods
   236  				}
   237  			}
   238  		}
   239  		// didn't find method
   240  		m.fun[0] = 0
   241  		return iname
   242  	}
   243  	m.fun[0] = uintptr(fun0)
   244  	return ""
   245  }
   246  
   247  func itabsinit() {
   248  	lockInit(&itabLock, lockRankItab)
   249  	lock(&itabLock)
   250  	for _, md := range activeModules() {
   251  		for _, i := range md.itablinks {
   252  			itabAdd(i)
   253  		}
   254  	}
   255  	unlock(&itabLock)
   256  }
   257  
   258  // panicdottypeE is called when doing an e.(T) conversion and the conversion fails.
   259  // have = the dynamic type we have.
   260  // want = the static type we're trying to convert to.
   261  // iface = the static type we're converting from.
   262  func panicdottypeE(have, want, iface *_type) {
   263  	panic(&TypeAssertionError{iface, have, want, ""})
   264  }
   265  
   266  // panicdottypeI is called when doing an i.(T) conversion and the conversion fails.
   267  // Same args as panicdottypeE, but "have" is the dynamic itab we have.
   268  func panicdottypeI(have *itab, want, iface *_type) {
   269  	var t *_type
   270  	if have != nil {
   271  		t = have._type
   272  	}
   273  	panicdottypeE(t, want, iface)
   274  }
   275  
   276  // panicnildottype is called when doing an i.(T) conversion and the interface i is nil.
   277  // want = the static type we're trying to convert to.
   278  func panicnildottype(want *_type) {
   279  	panic(&TypeAssertionError{nil, nil, want, ""})
   280  	// TODO: Add the static type we're converting from as well.
   281  	// It might generate a better error message.
   282  	// Just to match other nil conversion errors, we don't for now.
   283  }
   284  
   285  // The specialized convTx routines need a type descriptor to use when calling mallocgc.
   286  // We don't need the type to be exact, just to have the correct size, alignment, and pointer-ness.
   287  // However, when debugging, it'd be nice to have some indication in mallocgc where the types came from,
   288  // so we use named types here.
   289  // We then construct interface values of these types,
   290  // and then extract the type word to use as needed.
   291  type (
   292  	uint16InterfacePtr uint16
   293  	uint32InterfacePtr uint32
   294  	uint64InterfacePtr uint64
   295  	stringInterfacePtr string
   296  	sliceInterfacePtr  []byte
   297  )
   298  
   299  var (
   300  	uint16Eface any = uint16InterfacePtr(0)
   301  	uint32Eface any = uint32InterfacePtr(0)
   302  	uint64Eface any = uint64InterfacePtr(0)
   303  	stringEface any = stringInterfacePtr("")
   304  	sliceEface  any = sliceInterfacePtr(nil)
   305  
   306  	uint16Type *_type = efaceOf(&uint16Eface)._type
   307  	uint32Type *_type = efaceOf(&uint32Eface)._type
   308  	uint64Type *_type = efaceOf(&uint64Eface)._type
   309  	stringType *_type = efaceOf(&stringEface)._type
   310  	sliceType  *_type = efaceOf(&sliceEface)._type
   311  )
   312  
   313  // The conv and assert functions below do very similar things.
   314  // The convXXX functions are guaranteed by the compiler to succeed.
   315  // The assertXXX functions may fail (either panicking or returning false,
   316  // depending on whether they are 1-result or 2-result).
   317  // The convXXX functions succeed on a nil input, whereas the assertXXX
   318  // functions fail on a nil input.
   319  
   320  // convT converts a value of type t, which is pointed to by v, to a pointer that can
   321  // be used as the second word of an interface value.
   322  func convT(t *_type, v unsafe.Pointer) unsafe.Pointer {
   323  	if raceenabled {
   324  		raceReadObjectPC(t, v, getcallerpc(), abi.FuncPCABIInternal(convT))
   325  	}
   326  	if msanenabled {
   327  		msanread(v, t.Size_)
   328  	}
   329  	if asanenabled {
   330  		asanread(v, t.Size_)
   331  	}
   332  	x := mallocgc(t.Size_, t, true)
   333  	typedmemmove(t, x, v)
   334  	return x
   335  }
   336  func convTnoptr(t *_type, v unsafe.Pointer) unsafe.Pointer {
   337  	// TODO: maybe take size instead of type?
   338  	if raceenabled {
   339  		raceReadObjectPC(t, v, getcallerpc(), abi.FuncPCABIInternal(convTnoptr))
   340  	}
   341  	if msanenabled {
   342  		msanread(v, t.Size_)
   343  	}
   344  	if asanenabled {
   345  		asanread(v, t.Size_)
   346  	}
   347  
   348  	x := mallocgc(t.Size_, t, false)
   349  	memmove(x, v, t.Size_)
   350  	return x
   351  }
   352  
   353  func convT16(val uint16) (x unsafe.Pointer) {
   354  	if val < uint16(len(staticuint64s)) {
   355  		x = unsafe.Pointer(&staticuint64s[val])
   356  		if goarch.BigEndian {
   357  			x = add(x, 6)
   358  		}
   359  	} else {
   360  		x = mallocgc(2, uint16Type, false)
   361  		*(*uint16)(x) = val
   362  	}
   363  	return
   364  }
   365  
   366  func convT32(val uint32) (x unsafe.Pointer) {
   367  	if val < uint32(len(staticuint64s)) {
   368  		x = unsafe.Pointer(&staticuint64s[val])
   369  		if goarch.BigEndian {
   370  			x = add(x, 4)
   371  		}
   372  	} else {
   373  		x = mallocgc(4, uint32Type, false)
   374  		*(*uint32)(x) = val
   375  	}
   376  	return
   377  }
   378  
   379  func convT64(val uint64) (x unsafe.Pointer) {
   380  	if val < uint64(len(staticuint64s)) {
   381  		x = unsafe.Pointer(&staticuint64s[val])
   382  	} else {
   383  		x = mallocgc(8, uint64Type, false)
   384  		*(*uint64)(x) = val
   385  	}
   386  	return
   387  }
   388  
   389  func convTstring(val string) (x unsafe.Pointer) {
   390  	if val == "" {
   391  		x = unsafe.Pointer(&zeroVal[0])
   392  	} else {
   393  		x = mallocgc(unsafe.Sizeof(val), stringType, true)
   394  		*(*string)(x) = val
   395  	}
   396  	return
   397  }
   398  
   399  func convTslice(val []byte) (x unsafe.Pointer) {
   400  	// Note: this must work for any element type, not just byte.
   401  	if (*slice)(unsafe.Pointer(&val)).array == nil {
   402  		x = unsafe.Pointer(&zeroVal[0])
   403  	} else {
   404  		x = mallocgc(unsafe.Sizeof(val), sliceType, true)
   405  		*(*[]byte)(x) = val
   406  	}
   407  	return
   408  }
   409  
   410  // convI2I returns the new itab to be used for the destination value
   411  // when converting a value with itab src to the dst interface.
   412  func convI2I(dst *interfacetype, src *itab) *itab {
   413  	if src == nil {
   414  		return nil
   415  	}
   416  	if src.inter == dst {
   417  		return src
   418  	}
   419  	return getitab(dst, src._type, false)
   420  }
   421  
   422  func assertI2I(inter *interfacetype, tab *itab) *itab {
   423  	if tab == nil {
   424  		// explicit conversions require non-nil interface value.
   425  		panic(&TypeAssertionError{nil, nil, &inter.Type, ""})
   426  	}
   427  	if tab.inter == inter {
   428  		return tab
   429  	}
   430  	return getitab(inter, tab._type, false)
   431  }
   432  
   433  func assertI2I2(inter *interfacetype, i iface) (r iface) {
   434  	tab := i.tab
   435  	if tab == nil {
   436  		return
   437  	}
   438  	if tab.inter != inter {
   439  		tab = getitab(inter, tab._type, true)
   440  		if tab == nil {
   441  			return
   442  		}
   443  	}
   444  	r.tab = tab
   445  	r.data = i.data
   446  	return
   447  }
   448  
   449  func assertE2I(inter *interfacetype, t *_type) *itab {
   450  	if t == nil {
   451  		// explicit conversions require non-nil interface value.
   452  		panic(&TypeAssertionError{nil, nil, &inter.Type, ""})
   453  	}
   454  	return getitab(inter, t, false)
   455  }
   456  
   457  func assertE2I2(inter *interfacetype, e eface) (r iface) {
   458  	t := e._type
   459  	if t == nil {
   460  		return
   461  	}
   462  	tab := getitab(inter, t, true)
   463  	if tab == nil {
   464  		return
   465  	}
   466  	r.tab = tab
   467  	r.data = e.data
   468  	return
   469  }
   470  
   471  //go:linkname reflect_ifaceE2I reflect.ifaceE2I
   472  func reflect_ifaceE2I(inter *interfacetype, e eface, dst *iface) {
   473  	*dst = iface{assertE2I(inter, e._type), e.data}
   474  }
   475  
   476  //go:linkname reflectlite_ifaceE2I internal/reflectlite.ifaceE2I
   477  func reflectlite_ifaceE2I(inter *interfacetype, e eface, dst *iface) {
   478  	*dst = iface{assertE2I(inter, e._type), e.data}
   479  }
   480  
   481  func iterate_itabs(fn func(*itab)) {
   482  	// Note: only runs during stop the world or with itabLock held,
   483  	// so no other locks/atomics needed.
   484  	t := itabTable
   485  	for i := uintptr(0); i < t.size; i++ {
   486  		m := *(**itab)(add(unsafe.Pointer(&t.entries), i*goarch.PtrSize))
   487  		if m != nil {
   488  			fn(m)
   489  		}
   490  	}
   491  }
   492  
   493  // staticuint64s is used to avoid allocating in convTx for small integer values.
   494  var staticuint64s = [...]uint64{
   495  	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
   496  	0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
   497  	0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
   498  	0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
   499  	0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
   500  	0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
   501  	0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
   502  	0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
   503  	0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
   504  	0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
   505  	0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
   506  	0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
   507  	0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
   508  	0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
   509  	0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
   510  	0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
   511  	0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
   512  	0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
   513  	0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
   514  	0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
   515  	0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
   516  	0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
   517  	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
   518  	0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
   519  	0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
   520  	0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
   521  	0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
   522  	0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
   523  	0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
   524  	0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
   525  	0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
   526  	0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
   527  }
   528  
   529  // The linker redirects a reference of a method that it determined
   530  // unreachable to a reference to this function, so it will throw if
   531  // ever called.
   532  func unreachableMethod() {
   533  	throw("unreachable method called. linker bug?")
   534  }
   535  

View as plain text