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 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 lock(&itabLock) 300 if m = itabTable.find(lhsi, rhs); m != nil { 301 unlock(&itabLock) 302 goto finish 303 } 304 305 // Entry doesn't exist yet. Make a new entry & add it. 306 m = (*itab)(persistentalloc(unsafe.Sizeof(itab{})+uintptr(len(lhsi.methods)-1)*sys.PtrSize, 0, &memstats.other_sys)) 307 m.inter = lhsi 308 m.methods[0] = unsafe.Pointer(rhs) 309 m.init() 310 itabAdd(m) 311 unlock(&itabLock) 312finish: 313 if m.methods[1] != nil { 314 return unsafe.Pointer(&m.methods[0]) 315 } 316 if canfail { 317 return nil 318 } 319 // this can only happen if the conversion 320 // was already done once using the , ok form 321 // and we have a cached negative result. 322 // The cached result doesn't record which 323 // interface function was missing, so initialize 324 // the itab again to get the missing function name. 325 panic(&TypeAssertionError{nil, rhs, lhs, m.init()}) 326} 327 328// Return the interface method table for a value of type rhs converted 329// to an interface of type lhs. Panics if the conversion is impossible. 330func requireitab(lhs, rhs *_type) unsafe.Pointer { 331 return getitab(lhs, rhs, false) 332} 333 334// Return the interface method table for a value of type rhs converted 335// to an interface of type lhs. Panics if the conversion is 336// impossible or if the rhs type is nil. 337func assertitab(lhs, rhs *_type) unsafe.Pointer { 338 if rhs == nil { 339 panic(&TypeAssertionError{nil, nil, lhs, ""}) 340 } 341 342 if lhs.kind&kindMask != kindInterface { 343 throw("assertitab called for non-interface type") 344 } 345 346 lhsi := (*interfacetype)(unsafe.Pointer(lhs)) 347 348 if len(lhsi.methods) == 0 { 349 return unsafe.Pointer(rhs) 350 } 351 352 return getitab(lhs, rhs, false) 353} 354 355// panicdottype is called when doing an i.(T) conversion and the conversion fails. 356func panicdottype(lhs, rhs, inter *_type) { 357 panic(&TypeAssertionError{inter, rhs, lhs, ""}) 358} 359 360// Convert an empty interface to an empty interface, for a comma-ok 361// type assertion. 362func ifaceE2E2(e eface) (eface, bool) { 363 return e, e._type != nil 364} 365 366// Convert a non-empty interface to an empty interface, for a comma-ok 367// type assertion. 368func ifaceI2E2(i iface) (eface, bool) { 369 if i.tab == nil { 370 return eface{nil, nil}, false 371 } else { 372 return eface{*(**_type)(i.tab), i.data}, true 373 } 374} 375 376// Convert an empty interface to a non-empty interface, for a comma-ok 377// type assertion. 378func ifaceE2I2(inter *_type, e eface) (iface, bool) { 379 if e._type == nil { 380 return iface{nil, nil}, false 381 } else { 382 itab := getitab(inter, e._type, true) 383 if itab == nil { 384 return iface{nil, nil}, false 385 } else { 386 return iface{itab, e.data}, true 387 } 388 } 389} 390 391// Convert a non-empty interface to a non-empty interface, for a 392// comma-ok type assertion. 393func ifaceI2I2(inter *_type, i iface) (iface, bool) { 394 if i.tab == nil { 395 return iface{nil, nil}, false 396 } else { 397 itab := getitab(inter, *(**_type)(i.tab), true) 398 if itab == nil { 399 return iface{nil, nil}, false 400 } else { 401 return iface{itab, i.data}, true 402 } 403 } 404} 405 406// Convert an empty interface to a pointer non-interface type. 407func ifaceE2T2P(t *_type, e eface) (unsafe.Pointer, bool) { 408 if t != e._type { 409 return nil, false 410 } else { 411 return e.data, true 412 } 413} 414 415// Convert a non-empty interface to a pointer non-interface type. 416func ifaceI2T2P(t *_type, i iface) (unsafe.Pointer, bool) { 417 if i.tab == nil || t != *(**_type)(i.tab) { 418 return nil, false 419 } else { 420 return i.data, true 421 } 422} 423 424// Convert an empty interface to a non-pointer non-interface type. 425func ifaceE2T2(t *_type, e eface, ret unsafe.Pointer) bool { 426 if t != e._type { 427 typedmemclr(t, ret) 428 return false 429 } else { 430 if isDirectIface(t) { 431 *(*unsafe.Pointer)(ret) = e.data 432 } else { 433 typedmemmove(t, ret, e.data) 434 } 435 return true 436 } 437} 438 439// Convert a non-empty interface to a non-pointer non-interface type. 440func ifaceI2T2(t *_type, i iface, ret unsafe.Pointer) bool { 441 if i.tab == nil || t != *(**_type)(i.tab) { 442 typedmemclr(t, ret) 443 return false 444 } else { 445 if isDirectIface(t) { 446 *(*unsafe.Pointer)(ret) = i.data 447 } else { 448 typedmemmove(t, ret, i.data) 449 } 450 return true 451 } 452} 453 454// Return whether we can convert a type to an interface type. 455func ifaceT2Ip(to, from *_type) bool { 456 if from == nil { 457 return false 458 } 459 460 if to.kind&kindMask != kindInterface { 461 throw("ifaceT2Ip called with non-interface type") 462 } 463 toi := (*interfacetype)(unsafe.Pointer(to)) 464 465 if from.uncommontype == nil || len(from.methods) == 0 { 466 return len(toi.methods) == 0 467 } 468 469 ri := 0 470 for li := range toi.methods { 471 toMethod := &toi.methods[li] 472 var fromMethod *method 473 for { 474 if ri >= len(from.methods) { 475 return false 476 } 477 478 fromMethod = &from.methods[ri] 479 if (toMethod.name == fromMethod.name || *toMethod.name == *fromMethod.name) && 480 (toMethod.pkgPath == fromMethod.pkgPath || *toMethod.pkgPath == *fromMethod.pkgPath) { 481 break 482 } 483 484 ri++ 485 } 486 487 if fromMethod.mtyp != toMethod.typ { 488 return false 489 } 490 491 ri++ 492 } 493 494 return true 495} 496 497//go:linkname reflect_ifaceE2I reflect.ifaceE2I 498func reflect_ifaceE2I(inter *interfacetype, e eface, dst *iface) { 499 t := e._type 500 if t == nil { 501 panic(TypeAssertionError{nil, nil, &inter.typ, ""}) 502 } 503 dst.tab = requireitab((*_type)(unsafe.Pointer(inter)), t) 504 dst.data = e.data 505} 506 507//go:linkname reflectlite_ifaceE2I internal..z2freflectlite.ifaceE2I 508func reflectlite_ifaceE2I(inter *interfacetype, e eface, dst *iface) { 509 t := e._type 510 if t == nil { 511 panic(TypeAssertionError{nil, nil, &inter.typ, ""}) 512 } 513 dst.tab = requireitab((*_type)(unsafe.Pointer(inter)), t) 514 dst.data = e.data 515} 516 517// staticbytes is used to avoid convT2E for byte-sized values. 518var staticbytes = [...]byte{ 519 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 520 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 521 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 522 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 523 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 524 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 525 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 526 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 527 0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 528 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f, 529 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 530 0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 531 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 532 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 533 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 534 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 535 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 536 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, 537 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 538 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 539 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 540 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 541 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 542 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 543 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 544 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 545 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 546 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, 547 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 548 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 549 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 550 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff, 551} 552