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 5package runtime 6 7import ( 8 "runtime/internal/atomic" 9 "runtime/internal/sys" 10 "unsafe" 11) 12 13const itabInitSize = 512 14 15var ( 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. 22type 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 28func 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 33func 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) 78finish: 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. 96func (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. 121func 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. 158func (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. 191func (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 206imethods: 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 245func 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. 259func 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. 265func 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. 275func 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. 288type ( 289 uint16InterfacePtr uint16 290 uint32InterfacePtr uint32 291 uint64InterfacePtr uint64 292 stringInterfacePtr string 293 sliceInterfacePtr []byte 294) 295 296var ( 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 317func 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 333func 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 343func 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 353func 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 363func 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 373func 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 384func 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 398func 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 413func 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 428func 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 443func 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 459func 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 476func 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 487func 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 503func reflect_ifaceE2I(inter *interfacetype, e eface, dst *iface) { 504 *dst = assertE2I(inter, e) 505} 506 507//go:linkname reflectlite_ifaceE2I internal/reflectlite.ifaceE2I 508func reflectlite_ifaceE2I(inter *interfacetype, e eface, dst *iface) { 509 *dst = assertE2I(inter, e) 510} 511 512func 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. 525var 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