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 13// For gccgo, use go:linkname to export compiler-called functions. 14// 15//go:linkname requireitab 16//go:linkname assertitab 17//go:linkname panicdottype 18//go:linkname ifaceE2E2 19//go:linkname ifaceI2E2 20//go:linkname ifaceE2I2 21//go:linkname ifaceI2I2 22//go:linkname ifaceE2T2P 23//go:linkname ifaceI2T2P 24//go:linkname ifaceE2T2 25//go:linkname ifaceI2T2 26//go:linkname ifaceT2Ip 27// Temporary for C code to call: 28//go:linkname getitab 29 30// The gccgo itab structure is different than the gc one. 31// 32// Both gccgo and gc represent empty interfaces the same way: 33// a two field struct, where the first field points to a type descriptor 34// (a *_type) and the second field is the data pointer. 35// 36// Non-empty interfaces are also two-field structs, and the second 37// field is the data pointer. However, for gccgo, the first field, the 38// itab field, is different. The itab field points to the interface 39// method table, which is the implemention of a specific interface 40// type for a specific dynamic non-interface type. An interface 41// method table is a list of pointer values. The first pointer is the 42// type descriptor (a *_type) for the dynamic type. The subsequent 43// pointers are pointers to function code, which implement the methods 44// required by the interface. The pointers are sorted by name. 45// 46// The method pointers in the itab are C function pointers, not Go 47// function pointers; they may be called directly, and they have no 48// closures. The receiver is always passed as a pointer, and it is 49// always the same pointer stored in the interface value. A value 50// method starts by copying the receiver value out of the pointer into 51// a local variable. 52// 53// A method call on an interface value is by definition calling a 54// method at a known index m in the list of methods. Given a non-empty 55// interface value i, the call i.m(args) looks like 56// i.itab[m+1](i.iface, args) 57 58// Both an empty interface and a non-empty interface have a data 59// pointer field. The meaning of this field is determined by the 60// kindDirectIface bit in the `kind` field of the type descriptor of 61// the value stored in the interface. If kindDirectIface is set, then 62// the data pointer field in the interface value is exactly the value 63// stored in the interface. Otherwise, the data pointer field is a 64// pointer to memory that holds the value. It follows from this that 65// kindDirectIface can only be set for a type whose representation is 66// simply a pointer. In the current gccgo implementation, this is set 67// for types that are pointer-shaped, including unsafe.Pointer, channels, 68// maps, functions, single-field structs and single-element arrays whose 69// single field is simply a pointer-shaped type. 70 71// For a nil interface value both fields in the interface struct are nil. 72 73// itabs are statically allocated or persistently allocated. They are 74// never freed. For itabs allocated at run time, they are cached in 75// itabTable, so we reuse the same itab for the same (interface, concrete) 76// type pair. The gc runtime prepopulates the cache with statically 77// allocated itabs. Currently we don't do that as we don't have a way to 78// find all the statically allocated itabs. 79 80const itabInitSize = 512 81 82var ( 83 itabLock mutex // lock for accessing itab table 84 itabTable = &itabTableInit // pointer to current table 85 itabTableInit = itabTableType{size: itabInitSize} // starter table 86) 87 88// Cache entry type of itab table. 89// For gccgo, this is not the data type we used in the interface header. 90type itab struct { 91 inter *interfacetype 92 methods [2]unsafe.Pointer // method table. variable sized. first entry is the type descriptor. 93} 94 95func (m *itab) _type() *_type { 96 return (*_type)(m.methods[0]) 97} 98 99// Note: change the formula in the mallocgc call in itabAdd if you change these fields. 100type itabTableType struct { 101 size uintptr // length of entries array. Always a power of 2. 102 count uintptr // current number of filled entries. 103 entries [itabInitSize]*itab // really [size] large 104} 105 106func itabHashFunc(inter *interfacetype, typ *_type) uintptr { 107 // compiler has provided some good hash codes for us. 108 return uintptr(inter.typ.hash ^ typ.hash) 109} 110 111// find finds the given interface/type pair in t. 112// Returns nil if the given interface/type pair isn't present. 113func (t *itabTableType) find(inter *interfacetype, typ *_type) *itab { 114 // Implemented using quadratic probing. 115 // Probe sequence is h(i) = h0 + i*(i+1)/2 mod 2^k. 116 // We're guaranteed to hit all table entries using this probe sequence. 117 mask := t.size - 1 118 h := itabHashFunc(inter, typ) & mask 119 for i := uintptr(1); ; i++ { 120 p := (**itab)(add(unsafe.Pointer(&t.entries), h*sys.PtrSize)) 121 // Use atomic read here so if we see m != nil, we also see 122 // the initializations of the fields of m. 123 // m := *p 124 m := (*itab)(atomic.Loadp(unsafe.Pointer(p))) 125 if m == nil { 126 return nil 127 } 128 if m.inter == inter && m._type() == typ { 129 return m 130 } 131 h += i 132 h &= mask 133 } 134} 135 136// itabAdd adds the given itab to the itab hash table. 137// itabLock must be held. 138func itabAdd(m *itab) { 139 // Bugs can lead to calling this while mallocing is set, 140 // typically because this is called while panicing. 141 // Crash reliably, rather than only when we need to grow 142 // the hash table. 143 if getg().m.mallocing != 0 { 144 throw("malloc deadlock") 145 } 146 147 t := itabTable 148 if t.count >= 3*(t.size/4) { // 75% load factor 149 // Grow hash table. 150 // t2 = new(itabTableType) + some additional entries 151 // We lie and tell malloc we want pointer-free memory because 152 // all the pointed-to values are not in the heap. 153 t2 := (*itabTableType)(mallocgc((2+2*t.size)*sys.PtrSize, nil, true)) 154 t2.size = t.size * 2 155 156 // Copy over entries. 157 // Note: while copying, other threads may look for an itab and 158 // fail to find it. That's ok, they will then try to get the itab lock 159 // and as a consequence wait until this copying is complete. 160 iterate_itabs(t2.add) 161 if t2.count != t.count { 162 throw("mismatched count during itab table copy") 163 } 164 // Publish new hash table. Use an atomic write: see comment in getitab. 165 atomicstorep(unsafe.Pointer(&itabTable), unsafe.Pointer(t2)) 166 // Adopt the new table as our own. 167 t = itabTable 168 // Note: the old table can be GC'ed here. 169 } 170 t.add(m) 171} 172 173// add adds the given itab to itab table t. 174// itabLock must be held. 175func (t *itabTableType) add(m *itab) { 176 // See comment in find about the probe sequence. 177 // Insert new itab in the first empty spot in the probe sequence. 178 mask := t.size - 1 179 h := itabHashFunc(m.inter, m._type()) & mask 180 for i := uintptr(1); ; i++ { 181 p := (**itab)(add(unsafe.Pointer(&t.entries), h*sys.PtrSize)) 182 m2 := *p 183 if m2 == m { 184 // A given itab may be used in more than one module 185 // and thanks to the way global symbol resolution works, the 186 // pointed-to itab may already have been inserted into the 187 // global 'hash'. 188 return 189 } 190 if m2 == nil { 191 // Use atomic write here so if a reader sees m, it also 192 // sees the correctly initialized fields of m. 193 // NoWB is ok because m is not in heap memory. 194 // *p = m 195 atomic.StorepNoWB(unsafe.Pointer(p), unsafe.Pointer(m)) 196 t.count++ 197 return 198 } 199 h += i 200 h &= mask 201 } 202} 203 204// init fills in the m.methods array with all the code pointers for 205// the m.inter/m._type pair. If the type does not implement the interface, 206// it sets m.methods[1] to nil and returns the name of an interface function that is missing. 207// It is ok to call this multiple times on the same m, even concurrently. 208func (m *itab) init() string { 209 inter := m.inter 210 typ := m._type() 211 ni := len(inter.methods) + 1 212 methods := (*[1 << 16]unsafe.Pointer)(unsafe.Pointer(&m.methods[0]))[:ni:ni] 213 var m1 unsafe.Pointer 214 215 ri := 0 216 for li := range inter.methods { 217 lhsMethod := &inter.methods[li] 218 var rhsMethod *method 219 220 for { 221 if ri >= len(typ.methods) { 222 m.methods[1] = nil 223 return *lhsMethod.name 224 } 225 226 rhsMethod = &typ.methods[ri] 227 if (lhsMethod.name == rhsMethod.name || *lhsMethod.name == *rhsMethod.name) && 228 (lhsMethod.pkgPath == rhsMethod.pkgPath || *lhsMethod.pkgPath == *rhsMethod.pkgPath) { 229 break 230 } 231 232 ri++ 233 } 234 235 if !eqtype(lhsMethod.typ, rhsMethod.mtyp) { 236 m.methods[1] = nil 237 return *lhsMethod.name 238 } 239 240 if li == 0 { 241 m1 = rhsMethod.tfn // we'll set m.methods[1] at the end 242 } else { 243 methods[li+1] = rhsMethod.tfn 244 } 245 ri++ 246 } 247 m.methods[1] = m1 248 return "" 249} 250 251func iterate_itabs(fn func(*itab)) { 252 // Note: only runs during stop the world or with itabLock held, 253 // so no other locks/atomics needed. 254 t := itabTable 255 for i := uintptr(0); i < t.size; i++ { 256 m := *(**itab)(add(unsafe.Pointer(&t.entries), i*sys.PtrSize)) 257 if m != nil { 258 fn(m) 259 } 260 } 261} 262 263// Return the interface method table for a value of type rhs converted 264// to an interface of type lhs. 265func getitab(lhs, rhs *_type, canfail bool) unsafe.Pointer { 266 if rhs == nil { 267 return nil 268 } 269 270 if lhs.kind&kindMask != kindInterface { 271 throw("getitab called for non-interface type") 272 } 273 274 lhsi := (*interfacetype)(unsafe.Pointer(lhs)) 275 276 if len(lhsi.methods) == 0 { 277 throw("getitab called for empty interface type") 278 } 279 280 if rhs.uncommontype == nil || len(rhs.methods) == 0 { 281 if canfail { 282 return nil 283 } 284 panic(&TypeAssertionError{nil, rhs, lhs, *lhsi.methods[0].name}) 285 } 286 287 var m *itab 288 289 // First, look in the existing table to see if we can find the itab we need. 290 // This is by far the most common case, so do it without locks. 291 // Use atomic to ensure we see any previous writes done by the thread 292 // that updates the itabTable field (with atomic.Storep in itabAdd). 293 t := (*itabTableType)(atomic.Loadp(unsafe.Pointer(&itabTable))) 294 if m = t.find(lhsi, rhs); m != nil { 295 goto finish 296 } 297 298 // Not found. Grab the lock and try again. 299 lockInit(&itabLock, lockRankItab) 300 lock(&itabLock) 301 if m = itabTable.find(lhsi, rhs); m != nil { 302 unlock(&itabLock) 303 goto finish 304 } 305 306 // Entry doesn't exist yet. Make a new entry & add it. 307 m = (*itab)(persistentalloc(unsafe.Sizeof(itab{})+uintptr(len(lhsi.methods)-1)*sys.PtrSize, 0, &memstats.other_sys)) 308 m.inter = lhsi 309 m.methods[0] = unsafe.Pointer(rhs) 310 m.init() 311 itabAdd(m) 312 unlock(&itabLock) 313finish: 314 if m.methods[1] != nil { 315 return unsafe.Pointer(&m.methods[0]) 316 } 317 if canfail { 318 return nil 319 } 320 // this can only happen if the conversion 321 // was already done once using the , ok form 322 // and we have a cached negative result. 323 // The cached result doesn't record which 324 // interface function was missing, so initialize 325 // the itab again to get the missing function name. 326 panic(&TypeAssertionError{nil, rhs, lhs, m.init()}) 327} 328 329// Return the interface method table for a value of type rhs converted 330// to an interface of type lhs. Panics if the conversion is impossible. 331func requireitab(lhs, rhs *_type) unsafe.Pointer { 332 return getitab(lhs, rhs, false) 333} 334 335// Return the interface method table for a value of type rhs converted 336// to an interface of type lhs. Panics if the conversion is 337// impossible or if the rhs type is nil. 338func assertitab(lhs, rhs *_type) unsafe.Pointer { 339 if rhs == nil { 340 panic(&TypeAssertionError{nil, nil, lhs, ""}) 341 } 342 343 if lhs.kind&kindMask != kindInterface { 344 throw("assertitab called for non-interface type") 345 } 346 347 lhsi := (*interfacetype)(unsafe.Pointer(lhs)) 348 349 if len(lhsi.methods) == 0 { 350 return unsafe.Pointer(rhs) 351 } 352 353 return getitab(lhs, rhs, false) 354} 355 356// panicdottype is called when doing an i.(T) conversion and the conversion fails. 357func panicdottype(lhs, rhs, inter *_type) { 358 panic(&TypeAssertionError{inter, rhs, lhs, ""}) 359} 360 361// Convert an empty interface to an empty interface, for a comma-ok 362// type assertion. 363func ifaceE2E2(e eface) (eface, bool) { 364 return e, e._type != nil 365} 366 367// Convert a non-empty interface to an empty interface, for a comma-ok 368// type assertion. 369func ifaceI2E2(i iface) (eface, bool) { 370 if i.tab == nil { 371 return eface{nil, nil}, false 372 } else { 373 return eface{*(**_type)(i.tab), i.data}, true 374 } 375} 376 377// Convert an empty interface to a non-empty interface, for a comma-ok 378// type assertion. 379func ifaceE2I2(inter *_type, e eface) (iface, bool) { 380 if e._type == nil { 381 return iface{nil, nil}, false 382 } else { 383 itab := getitab(inter, e._type, true) 384 if itab == nil { 385 return iface{nil, nil}, false 386 } else { 387 return iface{itab, e.data}, true 388 } 389 } 390} 391 392// Convert a non-empty interface to a non-empty interface, for a 393// comma-ok type assertion. 394func ifaceI2I2(inter *_type, i iface) (iface, bool) { 395 if i.tab == nil { 396 return iface{nil, nil}, false 397 } else { 398 itab := getitab(inter, *(**_type)(i.tab), true) 399 if itab == nil { 400 return iface{nil, nil}, false 401 } else { 402 return iface{itab, i.data}, true 403 } 404 } 405} 406 407// Convert an empty interface to a pointer non-interface type. 408func ifaceE2T2P(t *_type, e eface) (unsafe.Pointer, bool) { 409 if !eqtype(t, e._type) { 410 return nil, false 411 } else { 412 return e.data, true 413 } 414} 415 416// Convert a non-empty interface to a pointer non-interface type. 417func ifaceI2T2P(t *_type, i iface) (unsafe.Pointer, bool) { 418 if i.tab == nil || !eqtype(t, *(**_type)(i.tab)) { 419 return nil, false 420 } else { 421 return i.data, true 422 } 423} 424 425// Convert an empty interface to a non-pointer non-interface type. 426func ifaceE2T2(t *_type, e eface, ret unsafe.Pointer) bool { 427 if !eqtype(t, e._type) { 428 typedmemclr(t, ret) 429 return false 430 } else { 431 if isDirectIface(t) { 432 *(*unsafe.Pointer)(ret) = e.data 433 } else { 434 typedmemmove(t, ret, e.data) 435 } 436 return true 437 } 438} 439 440// Convert a non-empty interface to a non-pointer non-interface type. 441func ifaceI2T2(t *_type, i iface, ret unsafe.Pointer) bool { 442 if i.tab == nil || !eqtype(t, *(**_type)(i.tab)) { 443 typedmemclr(t, ret) 444 return false 445 } else { 446 if isDirectIface(t) { 447 *(*unsafe.Pointer)(ret) = i.data 448 } else { 449 typedmemmove(t, ret, i.data) 450 } 451 return true 452 } 453} 454 455// Return whether we can convert a type to an interface type. 456func ifaceT2Ip(to, from *_type) bool { 457 if from == nil { 458 return false 459 } 460 461 if to.kind&kindMask != kindInterface { 462 throw("ifaceT2Ip called with non-interface type") 463 } 464 toi := (*interfacetype)(unsafe.Pointer(to)) 465 466 if from.uncommontype == nil || len(from.methods) == 0 { 467 return len(toi.methods) == 0 468 } 469 470 ri := 0 471 for li := range toi.methods { 472 toMethod := &toi.methods[li] 473 var fromMethod *method 474 for { 475 if ri >= len(from.methods) { 476 return false 477 } 478 479 fromMethod = &from.methods[ri] 480 if (toMethod.name == fromMethod.name || *toMethod.name == *fromMethod.name) && 481 (toMethod.pkgPath == fromMethod.pkgPath || *toMethod.pkgPath == *fromMethod.pkgPath) { 482 break 483 } 484 485 ri++ 486 } 487 488 if !eqtype(fromMethod.mtyp, toMethod.typ) { 489 return false 490 } 491 492 ri++ 493 } 494 495 return true 496} 497 498//go:linkname reflect_ifaceE2I reflect.ifaceE2I 499func reflect_ifaceE2I(inter *interfacetype, e eface, dst *iface) { 500 t := e._type 501 if t == nil { 502 panic(TypeAssertionError{nil, nil, &inter.typ, ""}) 503 } 504 dst.tab = requireitab((*_type)(unsafe.Pointer(inter)), t) 505 dst.data = e.data 506} 507 508//go:linkname reflectlite_ifaceE2I internal_1reflectlite.ifaceE2I 509func reflectlite_ifaceE2I(inter *interfacetype, e eface, dst *iface) { 510 t := e._type 511 if t == nil { 512 panic(TypeAssertionError{nil, nil, &inter.typ, ""}) 513 } 514 dst.tab = requireitab((*_type)(unsafe.Pointer(inter)), t) 515 dst.data = e.data 516} 517 518// staticuint64s is used to avoid allocating in convTx for small integer values. 519var staticuint64s = [...]uint64{ 520 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 521 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 522 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 523 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 524 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 525 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 526 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 527 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 528 0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 529 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f, 530 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 531 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 532 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 533 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 534 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 535 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 536 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 537 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, 538 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 539 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 540 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 541 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 542 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 543 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 544 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 545 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 546 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 547 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, 548 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 549 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 550 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 551 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff, 552} 553