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