Black Lives Matter. Support the Equal Justice Initiative.

Source file src/runtime/iface.go

Documentation: runtime

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

View as plain text