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, i iface) (r iface) {
   451  	tab := i.tab
   452  	if tab == nil {
   453  		// explicit conversions require non-nil interface value.
   454  		panic(&TypeAssertionError{nil, nil, &inter.typ, ""})
   455  	}
   456  	if tab.inter == inter {
   457  		r.tab = tab
   458  		r.data = i.data
   459  		return
   460  	}
   461  	r.tab = getitab(inter, tab._type, false)
   462  	r.data = i.data
   463  	return
   464  }
   465  
   466  func assertI2I2(inter *interfacetype, i iface) (r iface, b bool) {
   467  	tab := i.tab
   468  	if tab == nil {
   469  		return
   470  	}
   471  	if tab.inter != inter {
   472  		tab = getitab(inter, tab._type, true)
   473  		if tab == nil {
   474  			return
   475  		}
   476  	}
   477  	r.tab = tab
   478  	r.data = i.data
   479  	b = true
   480  	return
   481  }
   482  
   483  func assertE2I(inter *interfacetype, e eface) (r iface) {
   484  	t := e._type
   485  	if t == nil {
   486  		// explicit conversions require non-nil interface value.
   487  		panic(&TypeAssertionError{nil, nil, &inter.typ, ""})
   488  	}
   489  	r.tab = getitab(inter, t, false)
   490  	r.data = e.data
   491  	return
   492  }
   493  
   494  func assertE2I2(inter *interfacetype, e eface) (r iface, b bool) {
   495  	t := e._type
   496  	if t == nil {
   497  		return
   498  	}
   499  	tab := getitab(inter, t, true)
   500  	if tab == nil {
   501  		return
   502  	}
   503  	r.tab = tab
   504  	r.data = e.data
   505  	b = true
   506  	return
   507  }
   508  
   509  //go:linkname reflect_ifaceE2I reflect.ifaceE2I
   510  func reflect_ifaceE2I(inter *interfacetype, e eface, dst *iface) {
   511  	*dst = assertE2I(inter, e)
   512  }
   513  
   514  //go:linkname reflectlite_ifaceE2I internal/reflectlite.ifaceE2I
   515  func reflectlite_ifaceE2I(inter *interfacetype, e eface, dst *iface) {
   516  	*dst = assertE2I(inter, e)
   517  }
   518  
   519  func iterate_itabs(fn func(*itab)) {
   520  	// Note: only runs during stop the world or with itabLock held,
   521  	// so no other locks/atomics needed.
   522  	t := itabTable
   523  	for i := uintptr(0); i < t.size; i++ {
   524  		m := *(**itab)(add(unsafe.Pointer(&t.entries), i*sys.PtrSize))
   525  		if m != nil {
   526  			fn(m)
   527  		}
   528  	}
   529  }
   530  
   531  // staticuint64s is used to avoid allocating in convTx for small integer values.
   532  var staticuint64s = [...]uint64{
   533  	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
   534  	0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
   535  	0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
   536  	0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
   537  	0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
   538  	0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
   539  	0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
   540  	0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
   541  	0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
   542  	0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
   543  	0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
   544  	0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
   545  	0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
   546  	0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
   547  	0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
   548  	0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
   549  	0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
   550  	0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
   551  	0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
   552  	0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
   553  	0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
   554  	0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
   555  	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
   556  	0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
   557  	0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
   558  	0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
   559  	0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
   560  	0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
   561  	0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
   562  	0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
   563  	0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
   564  	0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
   565  }
   566  

View as plain text