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