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.
10 "runtime/internal/atomic"
11 "runtime/internal/sys"
15 const itabInitSize = 512
18 itabLock mutex // lock for accessing itab table
19 itabTable = &itabTableInit // pointer to current table
20 itabTableInit = itabTableType{size: itabInitSize} // starter table
23 // Note: change the formula in the mallocgc call in itabAdd if you change these fields.
24 type itabTableType struct {
25 size uintptr // length of entries array. Always a power of 2.
26 count uintptr // current number of filled entries.
27 entries [itabInitSize]*itab // really [size] large
30 func itabHashFunc(inter *interfacetype, typ *_type) uintptr {
31 // compiler has provided some good hash codes for us.
32 return uintptr(inter.Type.Hash ^ typ.Hash)
35 func getitab(inter *interfacetype, typ *_type, canfail bool) *itab {
36 if len(inter.Methods) == 0 {
37 throw("internal error - misuse of itab")
41 if typ.TFlag&abi.TFlagUncommon == 0 {
45 name := toRType(&inter.Type).nameOff(inter.Methods[0].Name)
46 panic(&TypeAssertionError{nil, typ, &inter.Type, name.Name()})
51 // First, look in the existing table to see if we can find the itab we need.
52 // This is by far the most common case, so do it without locks.
53 // Use atomic to ensure we see any previous writes done by the thread
54 // that updates the itabTable field (with atomic.Storep in itabAdd).
55 t := (*itabTableType)(atomic.Loadp(unsafe.Pointer(&itabTable)))
56 if m = t.find(inter, typ); m != nil {
60 // Not found. Grab the lock and try again.
62 if m = itabTable.find(inter, typ); m != nil {
67 // Entry doesn't exist yet. Make a new entry & add it.
68 m = (*itab)(persistentalloc(unsafe.Sizeof(itab{})+uintptr(len(inter.Methods)-1)*goarch.PtrSize, 0, &memstats.other_sys))
71 // The hash is used in type switches. However, compiler statically generates itab's
72 // for all interface/type pairs used in switches (which are added to itabTable
73 // in itabsinit). The dynamically-generated itab's never participate in type switches,
74 // and thus the hash is irrelevant.
75 // Note: m.hash is _not_ the hash used for the runtime itabTable hash table.
87 // this can only happen if the conversion
88 // was already done once using the , ok form
89 // and we have a cached negative result.
90 // The cached result doesn't record which
91 // interface function was missing, so initialize
92 // the itab again to get the missing function name.
93 panic(&TypeAssertionError{concrete: typ, asserted: &inter.Type, missingMethod: m.init()})
96 // find finds the given interface/type pair in t.
97 // Returns nil if the given interface/type pair isn't present.
98 func (t *itabTableType) find(inter *interfacetype, typ *_type) *itab {
99 // Implemented using quadratic probing.
100 // Probe sequence is h(i) = h0 + i*(i+1)/2 mod 2^k.
101 // We're guaranteed to hit all table entries using this probe sequence.
103 h := itabHashFunc(inter, typ) & mask
104 for i := uintptr(1); ; i++ {
105 p := (**itab)(add(unsafe.Pointer(&t.entries), h*goarch.PtrSize))
106 // Use atomic read here so if we see m != nil, we also see
107 // the initializations of the fields of m.
109 m := (*itab)(atomic.Loadp(unsafe.Pointer(p)))
113 if m.inter == inter && m._type == typ {
121 // itabAdd adds the given itab to the itab hash table.
122 // itabLock must be held.
123 func itabAdd(m *itab) {
124 // Bugs can lead to calling this while mallocing is set,
125 // typically because this is called while panicking.
126 // Crash reliably, rather than only when we need to grow
128 if getg().m.mallocing != 0 {
129 throw("malloc deadlock")
133 if t.count >= 3*(t.size/4) { // 75% load factor
135 // t2 = new(itabTableType) + some additional entries
136 // We lie and tell malloc we want pointer-free memory because
137 // all the pointed-to values are not in the heap.
138 t2 := (*itabTableType)(mallocgc((2+2*t.size)*goarch.PtrSize, nil, true))
141 // Copy over entries.
142 // Note: while copying, other threads may look for an itab and
143 // fail to find it. That's ok, they will then try to get the itab lock
144 // and as a consequence wait until this copying is complete.
145 iterate_itabs(t2.add)
146 if t2.count != t.count {
147 throw("mismatched count during itab table copy")
149 // Publish new hash table. Use an atomic write: see comment in getitab.
150 atomicstorep(unsafe.Pointer(&itabTable), unsafe.Pointer(t2))
151 // Adopt the new table as our own.
153 // Note: the old table can be GC'ed here.
158 // add adds the given itab to itab table t.
159 // itabLock must be held.
160 func (t *itabTableType) add(m *itab) {
161 // See comment in find about the probe sequence.
162 // Insert new itab in the first empty spot in the probe sequence.
164 h := itabHashFunc(m.inter, m._type) & mask
165 for i := uintptr(1); ; i++ {
166 p := (**itab)(add(unsafe.Pointer(&t.entries), h*goarch.PtrSize))
169 // A given itab may be used in more than one module
170 // and thanks to the way global symbol resolution works, the
171 // pointed-to itab may already have been inserted into the
176 // Use atomic write here so if a reader sees m, it also
177 // sees the correctly initialized fields of m.
178 // NoWB is ok because m is not in heap memory.
180 atomic.StorepNoWB(unsafe.Pointer(p), unsafe.Pointer(m))
189 // init fills in the m.fun array with all the code pointers for
190 // the m.inter/m._type pair. If the type does not implement the interface,
191 // it sets m.fun[0] to 0 and returns the name of an interface function that is missing.
192 // It is ok to call this multiple times on the same m, even concurrently.
193 func (m *itab) init() string {
198 // both inter and typ have method sorted by name,
199 // and interface names are unique,
200 // so can iterate over both in lock step;
201 // the loop is O(ni+nt) not O(ni*nt).
202 ni := len(inter.Methods)
204 xmhdr := (*[1 << 16]abi.Method)(add(unsafe.Pointer(x), uintptr(x.Moff)))[:nt:nt]
206 methods := (*[1 << 16]unsafe.Pointer)(unsafe.Pointer(&m.fun[0]))[:ni:ni]
207 var fun0 unsafe.Pointer
209 for k := 0; k < ni; k++ {
210 i := &inter.Methods[k]
211 itype := toRType(&inter.Type).typeOff(i.Typ)
212 name := toRType(&inter.Type).nameOff(i.Name)
214 ipkg := pkgPath(name)
216 ipkg = inter.PkgPath.Name()
221 tname := rtyp.nameOff(t.Name)
222 if rtyp.typeOff(t.Mtyp) == itype && tname.Name() == iname {
223 pkgPath := pkgPath(tname)
225 pkgPath = rtyp.nameOff(x.PkgPath).Name()
227 if tname.IsExported() || pkgPath == ipkg {
229 ifn := rtyp.textOff(t.Ifn)
231 fun0 = ifn // we'll set m.fun[0] at the end
240 // didn't find method
244 m.fun[0] = uintptr(fun0)
249 lockInit(&itabLock, lockRankItab)
251 for _, md := range activeModules() {
252 for _, i := range md.itablinks {
259 // panicdottypeE is called when doing an e.(T) conversion and the conversion fails.
260 // have = the dynamic type we have.
261 // want = the static type we're trying to convert to.
262 // iface = the static type we're converting from.
263 func panicdottypeE(have, want, iface *_type) {
264 panic(&TypeAssertionError{iface, have, want, ""})
267 // panicdottypeI is called when doing an i.(T) conversion and the conversion fails.
268 // Same args as panicdottypeE, but "have" is the dynamic itab we have.
269 func panicdottypeI(have *itab, want, iface *_type) {
274 panicdottypeE(t, want, iface)
277 // panicnildottype is called when doing an i.(T) conversion and the interface i is nil.
278 // want = the static type we're trying to convert to.
279 func panicnildottype(want *_type) {
280 panic(&TypeAssertionError{nil, nil, want, ""})
281 // TODO: Add the static type we're converting from as well.
282 // It might generate a better error message.
283 // Just to match other nil conversion errors, we don't for now.
286 // The specialized convTx routines need a type descriptor to use when calling mallocgc.
287 // We don't need the type to be exact, just to have the correct size, alignment, and pointer-ness.
288 // However, when debugging, it'd be nice to have some indication in mallocgc where the types came from,
289 // so we use named types here.
290 // We then construct interface values of these types,
291 // and then extract the type word to use as needed.
293 uint16InterfacePtr uint16
294 uint32InterfacePtr uint32
295 uint64InterfacePtr uint64
296 stringInterfacePtr string
297 sliceInterfacePtr []byte
301 uint16Eface any = uint16InterfacePtr(0)
302 uint32Eface any = uint32InterfacePtr(0)
303 uint64Eface any = uint64InterfacePtr(0)
304 stringEface any = stringInterfacePtr("")
305 sliceEface any = sliceInterfacePtr(nil)
307 uint16Type *_type = efaceOf(&uint16Eface)._type
308 uint32Type *_type = efaceOf(&uint32Eface)._type
309 uint64Type *_type = efaceOf(&uint64Eface)._type
310 stringType *_type = efaceOf(&stringEface)._type
311 sliceType *_type = efaceOf(&sliceEface)._type
314 // The conv and assert functions below do very similar things.
315 // The convXXX functions are guaranteed by the compiler to succeed.
316 // The assertXXX functions may fail (either panicking or returning false,
317 // depending on whether they are 1-result or 2-result).
318 // The convXXX functions succeed on a nil input, whereas the assertXXX
319 // functions fail on a nil input.
321 // convT converts a value of type t, which is pointed to by v, to a pointer that can
322 // be used as the second word of an interface value.
323 func convT(t *_type, v unsafe.Pointer) unsafe.Pointer {
325 raceReadObjectPC(t, v, getcallerpc(), abi.FuncPCABIInternal(convT))
333 x := mallocgc(t.Size_, t, true)
334 typedmemmove(t, x, v)
337 func convTnoptr(t *_type, v unsafe.Pointer) unsafe.Pointer {
338 // TODO: maybe take size instead of type?
340 raceReadObjectPC(t, v, getcallerpc(), abi.FuncPCABIInternal(convTnoptr))
349 x := mallocgc(t.Size_, t, false)
350 memmove(x, v, t.Size_)
354 func convT16(val uint16) (x unsafe.Pointer) {
355 if val < uint16(len(staticuint64s)) {
356 x = unsafe.Pointer(&staticuint64s[val])
357 if goarch.BigEndian {
361 x = mallocgc(2, uint16Type, false)
367 func convT32(val uint32) (x unsafe.Pointer) {
368 if val < uint32(len(staticuint64s)) {
369 x = unsafe.Pointer(&staticuint64s[val])
370 if goarch.BigEndian {
374 x = mallocgc(4, uint32Type, false)
380 func convT64(val uint64) (x unsafe.Pointer) {
381 if val < uint64(len(staticuint64s)) {
382 x = unsafe.Pointer(&staticuint64s[val])
384 x = mallocgc(8, uint64Type, false)
390 func convTstring(val string) (x unsafe.Pointer) {
392 x = unsafe.Pointer(&zeroVal[0])
394 x = mallocgc(unsafe.Sizeof(val), stringType, true)
400 func convTslice(val []byte) (x unsafe.Pointer) {
401 // Note: this must work for any element type, not just byte.
402 if (*slice)(unsafe.Pointer(&val)).array == nil {
403 x = unsafe.Pointer(&zeroVal[0])
405 x = mallocgc(unsafe.Sizeof(val), sliceType, true)
411 // convI2I returns the new itab to be used for the destination value
412 // when converting a value with itab src to the dst interface.
413 func convI2I(dst *interfacetype, src *itab) *itab {
417 return getitab(dst, src._type, false)
420 func assertE2I(inter *interfacetype, t *_type) *itab {
422 // explicit conversions require non-nil interface value.
423 panic(&TypeAssertionError{nil, nil, &inter.Type, ""})
425 return getitab(inter, t, false)
428 func assertE2I2(inter *interfacetype, t *_type) *itab {
432 return getitab(inter, t, true)
435 // typeAssert builds an itab for the concrete type t and the
436 // interface type s.Inter. If the conversion is not possible it
437 // panics if s.CanFail is false and returns nil if s.CanFail is true.
438 func typeAssert(s *abi.TypeAssert, t *_type) *itab {
443 panic(&TypeAssertionError{nil, nil, &s.Inter.Type, ""})
445 return getitab(s.Inter, t, s.CanFail)
448 // interfaceSwitch compares t against the list of cases in s.
449 // If t matches case i, interfaceSwitch returns the case index i and
450 // an itab for the pair <t, s.Cases[i]>.
451 // If there is no match, return N,nil, where N is the number
453 func interfaceSwitch(s *abi.InterfaceSwitch, t *_type) (int, *itab) {
454 cases := unsafe.Slice(&s.Cases[0], s.NCases)
456 // Results if we don't find a match.
460 // Look through each case in order.
461 for i, c := range cases {
462 tab = getitab(c, t, true)
469 if !abi.UseInterfaceSwitchCache(GOARCH) {
473 // Maybe update the cache, so the next time the generated code
474 // doesn't need to call into the runtime.
475 if fastrand()&1023 != 0 {
476 // Only bother updating the cache ~1 in 1000 times.
477 // This ensures we don't waste memory on switches, or
478 // switch arguments, that only happen a few times.
481 // Load the current cache.
482 oldC := (*abi.InterfaceSwitchCache)(atomic.Loadp(unsafe.Pointer(&s.Cache)))
484 if fastrand()&uint32(oldC.Mask) != 0 {
485 // As cache gets larger, choose to update it less often
486 // so we can amortize the cost of building a new cache
487 // (that cost is linear in oldc.Mask).
492 newC := buildInterfaceSwitchCache(oldC, t, case_, tab)
494 // Update cache. Use compare-and-swap so if multiple threads
495 // are fighting to update the cache, at least one of their
496 // updates will stick.
497 atomic_casPointer((*unsafe.Pointer)(unsafe.Pointer(&s.Cache)), unsafe.Pointer(oldC), unsafe.Pointer(newC))
502 // buildInterfaceSwitchCache constructs a interface switch cache
503 // containing all the entries from oldC plus the new entry
505 func buildInterfaceSwitchCache(oldC *abi.InterfaceSwitchCache, typ *_type, case_ int, tab *itab) *abi.InterfaceSwitchCache {
506 oldEntries := unsafe.Slice(&oldC.Entries[0], oldC.Mask+1)
508 // Count the number of entries we need.
510 for _, e := range oldEntries {
516 // Figure out how big a table we need.
517 // We need at least one more slot than the number of entries
518 // so that we are guaranteed an empty slot (for termination).
519 newN := n * 2 // make it at most 50% full
520 newN = 1 << sys.Len64(uint64(newN-1)) // round up to a power of 2
522 // Allocate the new table.
523 newSize := unsafe.Sizeof(abi.InterfaceSwitchCache{}) + uintptr(newN-1)*unsafe.Sizeof(abi.InterfaceSwitchCacheEntry{})
524 newC := (*abi.InterfaceSwitchCache)(mallocgc(newSize, nil, true))
525 newC.Mask = uintptr(newN - 1)
526 newEntries := unsafe.Slice(&newC.Entries[0], newN)
528 // Fill the new table.
529 addEntry := func(typ *_type, case_ int, tab *itab) {
530 h := int(typ.Hash) & (newN - 1)
532 if newEntries[h].Typ == 0 {
533 newEntries[h].Typ = uintptr(unsafe.Pointer(typ))
534 newEntries[h].Case = case_
535 newEntries[h].Itab = uintptr(unsafe.Pointer(tab))
538 h = (h + 1) & (newN - 1)
541 for _, e := range oldEntries {
543 addEntry((*_type)(unsafe.Pointer(e.Typ)), e.Case, (*itab)(unsafe.Pointer(e.Itab)))
546 addEntry(typ, case_, tab)
551 // Empty interface switch cache. Contains one entry with a nil Typ (which
552 // causes a cache lookup to fail immediately.)
553 var emptyInterfaceSwitchCache = abi.InterfaceSwitchCache{Mask: 0}
555 //go:linkname reflect_ifaceE2I reflect.ifaceE2I
556 func reflect_ifaceE2I(inter *interfacetype, e eface, dst *iface) {
557 *dst = iface{assertE2I(inter, e._type), e.data}
560 //go:linkname reflectlite_ifaceE2I internal/reflectlite.ifaceE2I
561 func reflectlite_ifaceE2I(inter *interfacetype, e eface, dst *iface) {
562 *dst = iface{assertE2I(inter, e._type), e.data}
565 func iterate_itabs(fn func(*itab)) {
566 // Note: only runs during stop the world or with itabLock held,
567 // so no other locks/atomics needed.
569 for i := uintptr(0); i < t.size; i++ {
570 m := *(**itab)(add(unsafe.Pointer(&t.entries), i*goarch.PtrSize))
577 // staticuint64s is used to avoid allocating in convTx for small integer values.
578 var staticuint64s = [...]uint64{
579 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
580 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
581 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
582 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
583 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
584 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
585 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
586 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
587 0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
588 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f,
589 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
590 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
591 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
592 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
593 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
594 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
595 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
596 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
597 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
598 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
599 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
600 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
601 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
602 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
603 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
604 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
605 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
606 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
607 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
608 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
609 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
610 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,
613 // The linker redirects a reference of a method that it determined
614 // unreachable to a reference to this function, so it will throw if
616 func unreachableMethod() {
617 throw("unreachable method called. linker bug?")