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  	lock(&itabLock)
   247  	for _, md := range activeModules() {
   248  		for _, i := range md.itablinks {
   249  			itabAdd(i)
   250  		}
   251  	}
   252  	unlock(&itabLock)
   253  }
   254  
   255  // panicdottypeE is called when doing an e.(T) conversion and the conversion fails.
   256  // have = the dynamic type we have.
   257  // want = the static type we're trying to convert to.
   258  // iface = the static type we're converting from.
   259  func panicdottypeE(have, want, iface *_type) {
   260  	panic(&TypeAssertionError{iface, have, want, ""})
   261  }
   262  
   263  // panicdottypeI is called when doing an i.(T) conversion and the conversion fails.
   264  // Same args as panicdottypeE, but "have" is the dynamic itab we have.
   265  func panicdottypeI(have *itab, want, iface *_type) {
   266  	var t *_type
   267  	if have != nil {
   268  		t = have._type
   269  	}
   270  	panicdottypeE(t, want, iface)
   271  }
   272  
   273  // panicnildottype is called when doing a i.(T) conversion and the interface i is nil.
   274  // want = the static type we're trying to convert to.
   275  func panicnildottype(want *_type) {
   276  	panic(&TypeAssertionError{nil, nil, want, ""})
   277  	// TODO: Add the static type we're converting from as well.
   278  	// It might generate a better error message.
   279  	// Just to match other nil conversion errors, we don't for now.
   280  }
   281  
   282  // The specialized convTx routines need a type descriptor to use when calling mallocgc.
   283  // We don't need the type to be exact, just to have the correct size, alignment, and pointer-ness.
   284  // However, when debugging, it'd be nice to have some indication in mallocgc where the types came from,
   285  // so we use named types here.
   286  // We then construct interface values of these types,
   287  // and then extract the type word to use as needed.
   288  type (
   289  	uint16InterfacePtr uint16
   290  	uint32InterfacePtr uint32
   291  	uint64InterfacePtr uint64
   292  	stringInterfacePtr string
   293  	sliceInterfacePtr  []byte
   294  )
   295  
   296  var (
   297  	uint16Eface interface{} = uint16InterfacePtr(0)
   298  	uint32Eface interface{} = uint32InterfacePtr(0)
   299  	uint64Eface interface{} = uint64InterfacePtr(0)
   300  	stringEface interface{} = stringInterfacePtr("")
   301  	sliceEface  interface{} = sliceInterfacePtr(nil)
   302  
   303  	uint16Type *_type = efaceOf(&uint16Eface)._type
   304  	uint32Type *_type = efaceOf(&uint32Eface)._type
   305  	uint64Type *_type = efaceOf(&uint64Eface)._type
   306  	stringType *_type = efaceOf(&stringEface)._type
   307  	sliceType  *_type = efaceOf(&sliceEface)._type
   308  )
   309  
   310  // The conv and assert functions below do very similar things.
   311  // The convXXX functions are guaranteed by the compiler to succeed.
   312  // The assertXXX functions may fail (either panicking or returning false,
   313  // depending on whether they are 1-result or 2-result).
   314  // The convXXX functions succeed on a nil input, whereas the assertXXX
   315  // functions fail on a nil input.
   316  
   317  func convT2E(t *_type, elem unsafe.Pointer) (e eface) {
   318  	if raceenabled {
   319  		raceReadObjectPC(t, elem, getcallerpc(), funcPC(convT2E))
   320  	}
   321  	if msanenabled {
   322  		msanread(elem, t.size)
   323  	}
   324  	x := mallocgc(t.size, t, true)
   325  	// TODO: We allocate a zeroed object only to overwrite it with actual data.
   326  	// Figure out how to avoid zeroing. Also below in convT2Eslice, convT2I, convT2Islice.
   327  	typedmemmove(t, x, elem)
   328  	e._type = t
   329  	e.data = x
   330  	return
   331  }
   332  
   333  func convT16(val uint16) (x unsafe.Pointer) {
   334  	if val == 0 {
   335  		x = unsafe.Pointer(&zeroVal[0])
   336  	} else {
   337  		x = mallocgc(2, uint16Type, false)
   338  		*(*uint16)(x) = val
   339  	}
   340  	return
   341  }
   342  
   343  func convT32(val uint32) (x unsafe.Pointer) {
   344  	if val == 0 {
   345  		x = unsafe.Pointer(&zeroVal[0])
   346  	} else {
   347  		x = mallocgc(4, uint32Type, false)
   348  		*(*uint32)(x) = val
   349  	}
   350  	return
   351  }
   352  
   353  func convT64(val uint64) (x unsafe.Pointer) {
   354  	if val == 0 {
   355  		x = unsafe.Pointer(&zeroVal[0])
   356  	} else {
   357  		x = mallocgc(8, uint64Type, false)
   358  		*(*uint64)(x) = val
   359  	}
   360  	return
   361  }
   362  
   363  func convTstring(val string) (x unsafe.Pointer) {
   364  	if val == "" {
   365  		x = unsafe.Pointer(&zeroVal[0])
   366  	} else {
   367  		x = mallocgc(unsafe.Sizeof(val), stringType, true)
   368  		*(*string)(x) = val
   369  	}
   370  	return
   371  }
   372  
   373  func convTslice(val []byte) (x unsafe.Pointer) {
   374  	// Note: this must work for any element type, not just byte.
   375  	if (*slice)(unsafe.Pointer(&val)).array == nil {
   376  		x = unsafe.Pointer(&zeroVal[0])
   377  	} else {
   378  		x = mallocgc(unsafe.Sizeof(val), sliceType, true)
   379  		*(*[]byte)(x) = val
   380  	}
   381  	return
   382  }
   383  
   384  func convT2Enoptr(t *_type, elem unsafe.Pointer) (e eface) {
   385  	if raceenabled {
   386  		raceReadObjectPC(t, elem, getcallerpc(), funcPC(convT2Enoptr))
   387  	}
   388  	if msanenabled {
   389  		msanread(elem, t.size)
   390  	}
   391  	x := mallocgc(t.size, t, false)
   392  	memmove(x, elem, t.size)
   393  	e._type = t
   394  	e.data = x
   395  	return
   396  }
   397  
   398  func convT2I(tab *itab, elem unsafe.Pointer) (i iface) {
   399  	t := tab._type
   400  	if raceenabled {
   401  		raceReadObjectPC(t, elem, getcallerpc(), funcPC(convT2I))
   402  	}
   403  	if msanenabled {
   404  		msanread(elem, t.size)
   405  	}
   406  	x := mallocgc(t.size, t, true)
   407  	typedmemmove(t, x, elem)
   408  	i.tab = tab
   409  	i.data = x
   410  	return
   411  }
   412  
   413  func convT2Inoptr(tab *itab, elem unsafe.Pointer) (i iface) {
   414  	t := tab._type
   415  	if raceenabled {
   416  		raceReadObjectPC(t, elem, getcallerpc(), funcPC(convT2Inoptr))
   417  	}
   418  	if msanenabled {
   419  		msanread(elem, t.size)
   420  	}
   421  	x := mallocgc(t.size, t, false)
   422  	memmove(x, elem, t.size)
   423  	i.tab = tab
   424  	i.data = x
   425  	return
   426  }
   427  
   428  func convI2I(inter *interfacetype, i iface) (r iface) {
   429  	tab := i.tab
   430  	if tab == nil {
   431  		return
   432  	}
   433  	if tab.inter == inter {
   434  		r.tab = tab
   435  		r.data = i.data
   436  		return
   437  	}
   438  	r.tab = getitab(inter, tab._type, false)
   439  	r.data = i.data
   440  	return
   441  }
   442  
   443  func assertI2I(inter *interfacetype, i iface) (r iface) {
   444  	tab := i.tab
   445  	if tab == nil {
   446  		// explicit conversions require non-nil interface value.
   447  		panic(&TypeAssertionError{nil, nil, &inter.typ, ""})
   448  	}
   449  	if tab.inter == inter {
   450  		r.tab = tab
   451  		r.data = i.data
   452  		return
   453  	}
   454  	r.tab = getitab(inter, tab._type, false)
   455  	r.data = i.data
   456  	return
   457  }
   458  
   459  func assertI2I2(inter *interfacetype, i iface) (r iface, b bool) {
   460  	tab := i.tab
   461  	if tab == nil {
   462  		return
   463  	}
   464  	if tab.inter != inter {
   465  		tab = getitab(inter, tab._type, true)
   466  		if tab == nil {
   467  			return
   468  		}
   469  	}
   470  	r.tab = tab
   471  	r.data = i.data
   472  	b = true
   473  	return
   474  }
   475  
   476  func assertE2I(inter *interfacetype, e eface) (r iface) {
   477  	t := e._type
   478  	if t == nil {
   479  		// explicit conversions require non-nil interface value.
   480  		panic(&TypeAssertionError{nil, nil, &inter.typ, ""})
   481  	}
   482  	r.tab = getitab(inter, t, false)
   483  	r.data = e.data
   484  	return
   485  }
   486  
   487  func assertE2I2(inter *interfacetype, e eface) (r iface, b bool) {
   488  	t := e._type
   489  	if t == nil {
   490  		return
   491  	}
   492  	tab := getitab(inter, t, true)
   493  	if tab == nil {
   494  		return
   495  	}
   496  	r.tab = tab
   497  	r.data = e.data
   498  	b = true
   499  	return
   500  }
   501  
   502  //go:linkname reflect_ifaceE2I reflect.ifaceE2I
   503  func reflect_ifaceE2I(inter *interfacetype, e eface, dst *iface) {
   504  	*dst = assertE2I(inter, e)
   505  }
   506  
   507  //go:linkname reflectlite_ifaceE2I internal/reflectlite.ifaceE2I
   508  func reflectlite_ifaceE2I(inter *interfacetype, e eface, dst *iface) {
   509  	*dst = assertE2I(inter, e)
   510  }
   511  
   512  func iterate_itabs(fn func(*itab)) {
   513  	// Note: only runs during stop the world or with itabLock held,
   514  	// so no other locks/atomics needed.
   515  	t := itabTable
   516  	for i := uintptr(0); i < t.size; i++ {
   517  		m := *(**itab)(add(unsafe.Pointer(&t.entries), i*sys.PtrSize))
   518  		if m != nil {
   519  			fn(m)
   520  		}
   521  	}
   522  }
   523  
   524  // staticbytes is used to avoid convT2E for byte-sized values.
   525  var staticbytes = [...]byte{
   526  	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
   527  	0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
   528  	0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
   529  	0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
   530  	0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
   531  	0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
   532  	0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
   533  	0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
   534  	0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
   535  	0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
   536  	0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
   537  	0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
   538  	0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
   539  	0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
   540  	0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
   541  	0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
   542  	0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
   543  	0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
   544  	0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
   545  	0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
   546  	0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
   547  	0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
   548  	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
   549  	0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
   550  	0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
   551  	0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
   552  	0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
   553  	0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
   554  	0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
   555  	0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
   556  	0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
   557  	0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
   558  }
   559  

View as plain text