1// Copyright 2009 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	"unsafe"
9)
10
11// For gccgo, use go:linkname to rename compiler-called functions to
12// themselves, so that the compiler will export them.
13//
14//go:linkname makeslice runtime.makeslice
15//go:linkname makeslice64 runtime.makeslice64
16//go:linkname growslice runtime.growslice
17//go:linkname slicecopy runtime.slicecopy
18//go:linkname slicestringcopy runtime.slicestringcopy
19
20type slice struct {
21	array unsafe.Pointer
22	len   int
23	cap   int
24}
25
26// An notInHeapSlice is a slice backed by go:notinheap memory.
27type notInHeapSlice struct {
28	array *notInHeap
29	len   int
30	cap   int
31}
32
33// maxElems is a lookup table containing the maximum capacity for a slice.
34// The index is the size of the slice element.
35var maxElems = [...]uintptr{
36	^uintptr(0),
37	_MaxMem / 1, _MaxMem / 2, _MaxMem / 3, _MaxMem / 4,
38	_MaxMem / 5, _MaxMem / 6, _MaxMem / 7, _MaxMem / 8,
39	_MaxMem / 9, _MaxMem / 10, _MaxMem / 11, _MaxMem / 12,
40	_MaxMem / 13, _MaxMem / 14, _MaxMem / 15, _MaxMem / 16,
41	_MaxMem / 17, _MaxMem / 18, _MaxMem / 19, _MaxMem / 20,
42	_MaxMem / 21, _MaxMem / 22, _MaxMem / 23, _MaxMem / 24,
43	_MaxMem / 25, _MaxMem / 26, _MaxMem / 27, _MaxMem / 28,
44	_MaxMem / 29, _MaxMem / 30, _MaxMem / 31, _MaxMem / 32,
45}
46
47// maxSliceCap returns the maximum capacity for a slice.
48func maxSliceCap(elemsize uintptr) uintptr {
49	if elemsize < uintptr(len(maxElems)) {
50		return maxElems[elemsize]
51	}
52	return _MaxMem / elemsize
53}
54
55func makeslice(et *_type, len, cap int) slice {
56	// NOTE: The len > maxElements check here is not strictly necessary,
57	// but it produces a 'len out of range' error instead of a 'cap out of range' error
58	// when someone does make([]T, bignumber). 'cap out of range' is true too,
59	// but since the cap is only being supplied implicitly, saying len is clearer.
60	// See issue 4085.
61	maxElements := maxSliceCap(et.size)
62	if len < 0 || uintptr(len) > maxElements {
63		panic(errorString("makeslice: len out of range"))
64	}
65
66	if cap < len || uintptr(cap) > maxElements {
67		panic(errorString("makeslice: cap out of range"))
68	}
69
70	p := mallocgc(et.size*uintptr(cap), et, true)
71	return slice{p, len, cap}
72}
73
74func makeslice64(et *_type, len64, cap64 int64) slice {
75	len := int(len64)
76	if int64(len) != len64 {
77		panic(errorString("makeslice: len out of range"))
78	}
79
80	cap := int(cap64)
81	if int64(cap) != cap64 {
82		panic(errorString("makeslice: cap out of range"))
83	}
84
85	return makeslice(et, len, cap)
86}
87
88// growslice handles slice growth during append.
89// It is passed the slice element type, the old slice, and the desired new minimum capacity,
90// and it returns a new slice with at least that capacity, with the old data
91// copied into it.
92// The new slice's length is set to the requested capacity.
93func growslice(et *_type, old slice, cap int) slice {
94	if raceenabled {
95		callerpc := getcallerpc()
96		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
97	}
98	if msanenabled {
99		msanread(old.array, uintptr(old.len*int(et.size)))
100	}
101
102	if et.size == 0 {
103		if cap < old.cap {
104			panic(errorString("growslice: cap out of range"))
105		}
106		// append should not create a slice with nil pointer but non-zero len.
107		// We assume that append doesn't need to preserve old.array in this case.
108		return slice{unsafe.Pointer(&zerobase), cap, cap}
109	}
110
111	newcap := old.cap
112	doublecap := newcap + newcap
113	if cap > doublecap {
114		newcap = cap
115	} else {
116		if old.len < 1024 {
117			newcap = doublecap
118		} else {
119			// Check 0 < newcap to detect overflow
120			// and prevent an infinite loop.
121			for 0 < newcap && newcap < cap {
122				newcap += newcap / 4
123			}
124			// Set newcap to the requested cap when
125			// the newcap calculation overflowed.
126			if newcap <= 0 {
127				newcap = cap
128			}
129		}
130	}
131
132	var overflow bool
133	var lenmem, newlenmem, capmem uintptr
134	const ptrSize = unsafe.Sizeof((*byte)(nil))
135	switch et.size {
136	case 1:
137		lenmem = uintptr(old.len)
138		newlenmem = uintptr(cap)
139		capmem = roundupsize(uintptr(newcap))
140		overflow = uintptr(newcap) > _MaxMem
141		newcap = int(capmem)
142	case ptrSize:
143		lenmem = uintptr(old.len) * ptrSize
144		newlenmem = uintptr(cap) * ptrSize
145		capmem = roundupsize(uintptr(newcap) * ptrSize)
146		overflow = uintptr(newcap) > _MaxMem/ptrSize
147		newcap = int(capmem / ptrSize)
148	default:
149		lenmem = uintptr(old.len) * et.size
150		newlenmem = uintptr(cap) * et.size
151		capmem = roundupsize(uintptr(newcap) * et.size)
152		overflow = uintptr(newcap) > maxSliceCap(et.size)
153		newcap = int(capmem / et.size)
154	}
155
156	// The check of overflow (uintptr(newcap) > maxSliceCap(et.size))
157	// in addition to capmem > _MaxMem is needed to prevent an overflow
158	// which can be used to trigger a segfault on 32bit architectures
159	// with this example program:
160	//
161	// type T [1<<27 + 1]int64
162	//
163	// var d T
164	// var s []T
165	//
166	// func main() {
167	//   s = append(s, d, d, d, d)
168	//   print(len(s), "\n")
169	// }
170	if cap < old.cap || overflow || capmem > _MaxMem {
171		panic(errorString("growslice: cap out of range"))
172	}
173
174	var p unsafe.Pointer
175	if et.kind&kindNoPointers != 0 {
176		p = mallocgc(capmem, nil, false)
177		memmove(p, old.array, lenmem)
178		// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
179		// Only clear the part that will not be overwritten.
180		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
181	} else {
182		// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
183		p = mallocgc(capmem, et, true)
184		if !writeBarrier.enabled {
185			memmove(p, old.array, lenmem)
186		} else {
187			for i := uintptr(0); i < lenmem; i += et.size {
188				typedmemmove(et, add(p, i), add(old.array, i))
189			}
190		}
191	}
192
193	return slice{p, cap, newcap}
194}
195
196func slicecopy(to, fm slice, width uintptr) int {
197	if fm.len == 0 || to.len == 0 {
198		return 0
199	}
200
201	n := fm.len
202	if to.len < n {
203		n = to.len
204	}
205
206	if width == 0 {
207		return n
208	}
209
210	if raceenabled {
211		callerpc := getcallerpc()
212		pc := funcPC(slicecopy)
213		racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
214		racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
215	}
216	if msanenabled {
217		msanwrite(to.array, uintptr(n*int(width)))
218		msanread(fm.array, uintptr(n*int(width)))
219	}
220
221	size := uintptr(n) * width
222	if size == 1 { // common case worth about 2x to do here
223		// TODO: is this still worth it with new memmove impl?
224		*(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
225	} else {
226		memmove(to.array, fm.array, size)
227	}
228	return n
229}
230
231func slicestringcopy(to []byte, fm string) int {
232	if len(fm) == 0 || len(to) == 0 {
233		return 0
234	}
235
236	n := len(fm)
237	if len(to) < n {
238		n = len(to)
239	}
240
241	if raceenabled {
242		callerpc := getcallerpc()
243		pc := funcPC(slicestringcopy)
244		racewriterangepc(unsafe.Pointer(&to[0]), uintptr(n), callerpc, pc)
245	}
246	if msanenabled {
247		msanwrite(unsafe.Pointer(&to[0]), uintptr(n))
248	}
249
250	memmove(unsafe.Pointer(&to[0]), stringStructOf(&fm).str, uintptr(n))
251	return n
252}
253