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

View as plain text