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