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