Source file src/pkg/runtime/iface.go

     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