src/runtime/slice.go

   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         "internal/abi"
   9         "internal/goarch"
  10         "runtime/internal/math"
  11         "runtime/internal/sys"
  12         "unsafe"
  13 )
  14
  15 type slice struct {
  16         array unsafe.Pointer
  17         len   int
  18         cap   int
  19 }
  20
  21 // A notInHeapSlice is a slice backed by runtime/internal/sys.NotInHeap memory.
  22 type notInHeapSlice struct {
  23         array *notInHeap
  24         len   int
  25         cap   int
  26 }
  27
  28 func panicmakeslicelen() {
  29         panic(errorString("makeslice: len out of range"))
  30 }
  31
  32 func panicmakeslicecap() {
  33         panic(errorString("makeslice: cap out of range"))
  34 }
  35
  36 // makeslicecopy allocates a slice of "tolen" elements of type "et",
  37 // then copies "fromlen" elements of type "et" into that new allocation from "from".
  38 func makeslicecopy(et *_type, tolen int, fromlen int, from unsafe.Pointer) unsafe.Pointer {
  39         var tomem, copymem uintptr
  40         if uintptr(tolen) > uintptr(fromlen) {
  41                 var overflow bool
  42                 tomem, overflow = math.MulUintptr(et.Size_, uintptr(tolen))
  43                 if overflow || tomem > maxAlloc || tolen < 0 {
  44                         panicmakeslicelen()
  45                 }
  46                 copymem = et.Size_ * uintptr(fromlen)
  47         } else {
  48                 // fromlen is a known good length providing and equal or greater than tolen,
  49                 // thereby making tolen a good slice length too as from and to slices have the
  50                 // same element width.
  51                 tomem = et.Size_ * uintptr(tolen)
  52                 copymem = tomem
  53         }
  54
  55         var to unsafe.Pointer
  56         if et.PtrBytes == 0 {
  57                 to = mallocgc(tomem, nil, false)
  58                 if copymem < tomem {
  59                         memclrNoHeapPointers(add(to, copymem), tomem-copymem)
  60                 }
  61         } else {
  62                 // Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
  63                 to = mallocgc(tomem, et, true)
  64                 if copymem > 0 && writeBarrier.enabled {
  65                         // Only shade the pointers in old.array since we know the destination slice to
  66                         // only contains nil pointers because it has been cleared during alloc.
  67                         bulkBarrierPreWriteSrcOnly(uintptr(to), uintptr(from), copymem)
  68                 }
  69         }
  70
  71         if raceenabled {
  72                 callerpc := getcallerpc()
  73                 pc := abi.FuncPCABIInternal(makeslicecopy)
  74                 racereadrangepc(from, copymem, callerpc, pc)
  75         }
  76         if msanenabled {
  77                 msanread(from, copymem)
  78         }
  79         if asanenabled {
  80                 asanread(from, copymem)
  81         }
  82
  83         memmove(to, from, copymem)
  84
  85         return to
  86 }
  87
  88 func makeslice(et *_type, len, cap int) unsafe.Pointer {
  89         mem, overflow := math.MulUintptr(et.Size_, uintptr(cap))
  90         if overflow || mem > maxAlloc || len < 0 || len > cap {
  91                 // NOTE: Produce a 'len out of range' error instead of a
  92                 // 'cap out of range' error when someone does make([]T, bignumber).
  93                 // 'cap out of range' is true too, but since the cap is only being
  94                 // supplied implicitly, saying len is clearer.
  95                 // See golang.org/issue/4085.
  96                 mem, overflow := math.MulUintptr(et.Size_, uintptr(len))
  97                 if overflow || mem > maxAlloc || len < 0 {
  98                         panicmakeslicelen()
  99                 }
 100                 panicmakeslicecap()
 101         }
 102
 103         return mallocgc(mem, et, true)
 104 }
 105
 106 func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {
 107         len := int(len64)
 108         if int64(len) != len64 {
 109                 panicmakeslicelen()
 110         }
 111
 112         cap := int(cap64)
 113         if int64(cap) != cap64 {
 114                 panicmakeslicecap()
 115         }
 116
 117         return makeslice(et, len, cap)
 118 }
 119
 120 // growslice allocates new backing store for a slice.
 121 //
 122 // arguments:
 123 //
 124 //      oldPtr = pointer to the slice's backing array
 125 //      newLen = new length (= oldLen + num)
 126 //      oldCap = original slice's capacity.
 127 //         num = number of elements being added
 128 //          et = element type
 129 //
 130 // return values:
 131 //
 132 //      newPtr = pointer to the new backing store
 133 //      newLen = same value as the argument
 134 //      newCap = capacity of the new backing store
 135 //
 136 // Requires that uint(newLen) > uint(oldCap).
 137 // Assumes the original slice length is newLen - num
 138 //
 139 // A new backing store is allocated with space for at least newLen elements.
 140 // Existing entries [0, oldLen) are copied over to the new backing store.
 141 // Added entries [oldLen, newLen) are not initialized by growslice
 142 // (although for pointer-containing element types, they are zeroed). They
 143 // must be initialized by the caller.
 144 // Trailing entries [newLen, newCap) are zeroed.
 145 //
 146 // growslice's odd calling convention makes the generated code that calls
 147 // this function simpler. In particular, it accepts and returns the
 148 // new length so that the old length is not live (does not need to be
 149 // spilled/restored) and the new length is returned (also does not need
 150 // to be spilled/restored).
 151 func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
 152         oldLen := newLen - num
 153         if raceenabled {
 154                 callerpc := getcallerpc()
 155                 racereadrangepc(oldPtr, uintptr(oldLen*int(et.Size_)), callerpc, abi.FuncPCABIInternal(growslice))
 156         }
 157         if msanenabled {
 158                 msanread(oldPtr, uintptr(oldLen*int(et.Size_)))
 159         }
 160         if asanenabled {
 161                 asanread(oldPtr, uintptr(oldLen*int(et.Size_)))
 162         }
 163
 164         if newLen < 0 {
 165                 panic(errorString("growslice: len out of range"))
 166         }
 167
 168         if et.Size_ == 0 {
 169                 // append should not create a slice with nil pointer but non-zero len.
 170                 // We assume that append doesn't need to preserve oldPtr in this case.
 171                 return slice{unsafe.Pointer(&zerobase), newLen, newLen}
 172         }
 173
 174         newcap := nextslicecap(newLen, oldCap)
 175
 176         var overflow bool
 177         var lenmem, newlenmem, capmem uintptr
 178         // Specialize for common values of et.Size.
 179         // For 1 we don't need any division/multiplication.
 180         // For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
 181         // For powers of 2, use a variable shift.
 182         switch {
 183         case et.Size_ == 1:
 184                 lenmem = uintptr(oldLen)
 185                 newlenmem = uintptr(newLen)
 186                 capmem = roundupsize(uintptr(newcap))
 187                 overflow = uintptr(newcap) > maxAlloc
 188                 newcap = int(capmem)
 189         case et.Size_ == goarch.PtrSize:
 190                 lenmem = uintptr(oldLen) * goarch.PtrSize
 191                 newlenmem = uintptr(newLen) * goarch.PtrSize
 192                 capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
 193                 overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
 194                 newcap = int(capmem / goarch.PtrSize)
 195         case isPowerOfTwo(et.Size_):
 196                 var shift uintptr
 197                 if goarch.PtrSize == 8 {
 198                         // Mask shift for better code generation.
 199                         shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63
 200                 } else {
 201                         shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31
 202                 }
 203                 lenmem = uintptr(oldLen) << shift
 204                 newlenmem = uintptr(newLen) << shift
 205                 capmem = roundupsize(uintptr(newcap) << shift)
 206                 overflow = uintptr(newcap) > (maxAlloc >> shift)
 207                 newcap = int(capmem >> shift)
 208                 capmem = uintptr(newcap) << shift
 209         default:
 210                 lenmem = uintptr(oldLen) * et.Size_
 211                 newlenmem = uintptr(newLen) * et.Size_
 212                 capmem, overflow = math.MulUintptr(et.Size_, uintptr(newcap))
 213                 capmem = roundupsize(capmem)
 214                 newcap = int(capmem / et.Size_)
 215                 capmem = uintptr(newcap) * et.Size_
 216         }
 217
 218         // The check of overflow in addition to capmem > maxAlloc is needed
 219         // to prevent an overflow which can be used to trigger a segfault
 220         // on 32bit architectures with this example program:
 221         //
 222         // type T [1<<27 + 1]int64
 223         //
 224         // var d T
 225         // var s []T
 226         //
 227         // func main() {
 228         //   s = append(s, d, d, d, d)
 229         //   print(len(s), "\n")
 230         // }
 231         if overflow || capmem > maxAlloc {
 232                 panic(errorString("growslice: len out of range"))
 233         }
 234
 235         var p unsafe.Pointer
 236         if et.PtrBytes == 0 {
 237                 p = mallocgc(capmem, nil, false)
 238                 // The append() that calls growslice is going to overwrite from oldLen to newLen.
 239                 // Only clear the part that will not be overwritten.
 240                 // The reflect_growslice() that calls growslice will manually clear
 241                 // the region not cleared here.
 242                 memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
 243         } else {
 244                 // Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
 245                 p = mallocgc(capmem, et, true)
 246                 if lenmem > 0 && writeBarrier.enabled {
 247                         // Only shade the pointers in oldPtr since we know the destination slice p
 248                         // only contains nil pointers because it has been cleared during alloc.
 249                         bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.Size_+et.PtrBytes)
 250                 }
 251         }
 252         memmove(p, oldPtr, lenmem)
 253
 254         return slice{p, newLen, newcap}
 255 }
 256
 257 // nextslicecap computes the next appropriate slice length.
 258 func nextslicecap(newLen, oldCap int) int {
 259         newcap := oldCap
 260         doublecap := newcap + newcap
 261         if newLen > doublecap {
 262                 return newLen
 263         }
 264
 265         const threshold = 256
 266         if oldCap < threshold {
 267                 return doublecap
 268         }
 269         for {
 270                 // Transition from growing 2x for small slices
 271                 // to growing 1.25x for large slices. This formula
 272                 // gives a smooth-ish transition between the two.
 273                 newcap += (newcap + 3*threshold) >> 2
 274
 275                 // We need to check `newcap >= newLen` and whether `newcap` overflowed.
 276                 // newLen is guaranteed to be larger than zero, hence
 277                 // when newcap overflows then `uint(newcap) > uint(newLen)`.
 278                 // This allows to check for both with the same comparison.
 279                 if uint(newcap) >= uint(newLen) {
 280                         break
 281                 }
 282         }
 283
 284         // Set newcap to the requested cap when
 285         // the newcap calculation overflowed.
 286         if newcap <= 0 {
 287                 return newLen
 288         }
 289         return newcap
 290 }
 291
 292 //go:linkname reflect_growslice reflect.growslice
 293 func reflect_growslice(et *_type, old slice, num int) slice {
 294         // Semantically equivalent to slices.Grow, except that the caller
 295         // is responsible for ensuring that old.len+num > old.cap.
 296         num -= old.cap - old.len // preserve memory of old[old.len:old.cap]
 297         new := growslice(old.array, old.cap+num, old.cap, num, et)
 298         // growslice does not zero out new[old.cap:new.len] since it assumes that
 299         // the memory will be overwritten by an append() that called growslice.
 300         // Since the caller of reflect_growslice is not append(),
 301         // zero out this region before returning the slice to the reflect package.
 302         if et.PtrBytes == 0 {
 303                 oldcapmem := uintptr(old.cap) * et.Size_
 304                 newlenmem := uintptr(new.len) * et.Size_
 305                 memclrNoHeapPointers(add(new.array, oldcapmem), newlenmem-oldcapmem)
 306         }
 307         new.len = old.len // preserve the old length
 308         return new
 309 }
 310
 311 func isPowerOfTwo(x uintptr) bool {
 312         return x&(x-1) == 0
 313 }
 314
 315 // slicecopy is used to copy from a string or slice of pointerless elements into a slice.
 316 func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
 317         if fromLen == 0 || toLen == 0 {
 318                 return 0
 319         }
 320
 321         n := fromLen
 322         if toLen < n {
 323                 n = toLen
 324         }
 325
 326         if width == 0 {
 327                 return n
 328         }
 329
 330         size := uintptr(n) * width
 331         if raceenabled {
 332                 callerpc := getcallerpc()
 333                 pc := abi.FuncPCABIInternal(slicecopy)
 334                 racereadrangepc(fromPtr, size, callerpc, pc)
 335                 racewriterangepc(toPtr, size, callerpc, pc)
 336         }
 337         if msanenabled {
 338                 msanread(fromPtr, size)
 339                 msanwrite(toPtr, size)
 340         }
 341         if asanenabled {
 342                 asanread(fromPtr, size)
 343                 asanwrite(toPtr, size)
 344         }
 345
 346         if size == 1 { // common case worth about 2x to do here
 347                 // TODO: is this still worth it with new memmove impl?
 348                 *(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
 349         } else {
 350                 memmove(toPtr, fromPtr, size)
 351         }
 352         return n
 353 }
 354
 355 //go:linkname bytealg_MakeNoZero internal/bytealg.MakeNoZero
 356 func bytealg_MakeNoZero(len int) []byte {
 357         if uintptr(len) > maxAlloc {
 358                 panicmakeslicelen()
 359         }
 360         return unsafe.Slice((*byte)(mallocgc(uintptr(len), nil, false)), len)
 361 }