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 go: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.ptrdata == 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
  80         memmove(to, from, copymem)
  81
  82         return to
  83 }
  84
  85 func makeslice(et *_type, len, cap int) unsafe.Pointer {
  86         mem, overflow := math.MulUintptr(et.size, uintptr(cap))
  87         if overflow || mem > maxAlloc || len < 0 || len > cap {
  88                 // NOTE: Produce a 'len out of range' error instead of a
  89                 // 'cap out of range' error when someone does make([]T, bignumber).
  90                 // 'cap out of range' is true too, but since the cap is only being
  91                 // supplied implicitly, saying len is clearer.
  92                 // See golang.org/issue/4085.
  93                 mem, overflow := math.MulUintptr(et.size, uintptr(len))
  94                 if overflow || mem > maxAlloc || len < 0 {
  95                         panicmakeslicelen()
  96                 }
  97                 panicmakeslicecap()
  98         }
  99
 100         return mallocgc(mem, et, true)
 101 }
 102
 103 func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {
 104         len := int(len64)
 105         if int64(len) != len64 {
 106                 panicmakeslicelen()
 107         }
 108
 109         cap := int(cap64)
 110         if int64(cap) != cap64 {
 111                 panicmakeslicecap()
 112         }
 113
 114         return makeslice(et, len, cap)
 115 }
 116
 117 func unsafeslice(et *_type, ptr unsafe.Pointer, len int) {
 118         if len == 0 {
 119                 return
 120         }
 121
 122         if ptr == nil {
 123                 panic(errorString("unsafe.Slice: ptr is nil and len is not zero"))
 124         }
 125
 126         mem, overflow := math.MulUintptr(et.size, uintptr(len))
 127         if overflow || mem > maxAlloc || len < 0 {
 128                 panicunsafeslicelen()
 129         }
 130 }
 131
 132 func unsafeslice64(et *_type, ptr unsafe.Pointer, len64 int64) {
 133         len := int(len64)
 134         if int64(len) != len64 {
 135                 panicunsafeslicelen()
 136         }
 137         unsafeslice(et, ptr, len)
 138 }
 139
 140 func unsafeslicecheckptr(et *_type, ptr unsafe.Pointer, len64 int64) {
 141         unsafeslice64(et, ptr, len64)
 142
 143         // Check that underlying array doesn't straddle multiple heap objects.
 144         // unsafeslice64 has already checked for overflow.
 145         if checkptrStraddles(ptr, uintptr(len64)*et.size) {
 146                 throw("checkptr: unsafe.Slice result straddles multiple allocations")
 147         }
 148 }
 149
 150 func panicunsafeslicelen() {
 151         panic(errorString("unsafe.Slice: len out of range"))
 152 }
 153
 154 // growslice handles slice growth during append.
 155 // It is passed the slice element type, the old slice, and the desired new minimum capacity,
 156 // and it returns a new slice with at least that capacity, with the old data
 157 // copied into it.
 158 // The new slice's length is set to the old slice's length,
 159 // NOT to the new requested capacity.
 160 // This is for codegen convenience. The old slice's length is used immediately
 161 // to calculate where to write new values during an append.
 162 // TODO: When the old backend is gone, reconsider this decision.
 163 // The SSA backend might prefer the new length or to return only ptr/cap and save stack space.
 164 func growslice(et *_type, old slice, cap int) slice {
 165         if raceenabled {
 166                 callerpc := getcallerpc()
 167                 racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, abi.FuncPCABIInternal(growslice))
 168         }
 169         if msanenabled {
 170                 msanread(old.array, uintptr(old.len*int(et.size)))
 171         }
 172
 173         if cap < old.cap {
 174                 panic(errorString("growslice: cap out of range"))
 175         }
 176
 177         if et.size == 0 {
 178                 // append should not create a slice with nil pointer but non-zero len.
 179                 // We assume that append doesn't need to preserve old.array in this case.
 180                 return slice{unsafe.Pointer(&zerobase), old.len, cap}
 181         }
 182
 183         newcap := old.cap
 184         doublecap := newcap + newcap
 185         if cap > doublecap {
 186                 newcap = cap
 187         } else {
 188                 if old.cap < 1024 {
 189                         newcap = doublecap
 190                 } else {
 191                         // Check 0 < newcap to detect overflow
 192                         // and prevent an infinite loop.
 193                         for 0 < newcap && newcap < cap {
 194                                 newcap += newcap / 4
 195                         }
 196                         // Set newcap to the requested cap when
 197                         // the newcap calculation overflowed.
 198                         if newcap <= 0 {
 199                                 newcap = cap
 200                         }
 201                 }
 202         }
 203
 204         var overflow bool
 205         var lenmem, newlenmem, capmem uintptr
 206         // Specialize for common values of et.size.
 207         // For 1 we don't need any division/multiplication.
 208         // For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
 209         // For powers of 2, use a variable shift.
 210         switch {
 211         case et.size == 1:
 212                 lenmem = uintptr(old.len)
 213                 newlenmem = uintptr(cap)
 214                 capmem = roundupsize(uintptr(newcap))
 215                 overflow = uintptr(newcap) > maxAlloc
 216                 newcap = int(capmem)
 217         case et.size == goarch.PtrSize:
 218                 lenmem = uintptr(old.len) * goarch.PtrSize
 219                 newlenmem = uintptr(cap) * goarch.PtrSize
 220                 capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
 221                 overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
 222                 newcap = int(capmem / goarch.PtrSize)
 223         case isPowerOfTwo(et.size):
 224                 var shift uintptr
 225                 if goarch.PtrSize == 8 {
 226                         // Mask shift for better code generation.
 227                         shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
 228                 } else {
 229                         shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
 230                 }
 231                 lenmem = uintptr(old.len) << shift
 232                 newlenmem = uintptr(cap) << shift
 233                 capmem = roundupsize(uintptr(newcap) << shift)
 234                 overflow = uintptr(newcap) > (maxAlloc >> shift)
 235                 newcap = int(capmem >> shift)
 236         default:
 237                 lenmem = uintptr(old.len) * et.size
 238                 newlenmem = uintptr(cap) * et.size
 239                 capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
 240                 capmem = roundupsize(capmem)
 241                 newcap = int(capmem / et.size)
 242         }
 243
 244         // The check of overflow in addition to capmem > maxAlloc is needed
 245         // to prevent an overflow which can be used to trigger a segfault
 246         // on 32bit architectures with this example program:
 247         //
 248         // type T [1<<27 + 1]int64
 249         //
 250         // var d T
 251         // var s []T
 252         //
 253         // func main() {
 254         //   s = append(s, d, d, d, d)
 255         //   print(len(s), "\n")
 256         // }
 257         if overflow || capmem > maxAlloc {
 258                 panic(errorString("growslice: cap out of range"))
 259         }
 260
 261         var p unsafe.Pointer
 262         if et.ptrdata == 0 {
 263                 p = mallocgc(capmem, nil, false)
 264                 // The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
 265                 // Only clear the part that will not be overwritten.
 266                 memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
 267         } else {
 268                 // Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
 269                 p = mallocgc(capmem, et, true)
 270                 if lenmem > 0 && writeBarrier.enabled {
 271                         // Only shade the pointers in old.array since we know the destination slice p
 272                         // only contains nil pointers because it has been cleared during alloc.
 273                         bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
 274                 }
 275         }
 276         memmove(p, old.array, lenmem)
 277
 278         return slice{p, old.len, newcap}
 279 }
 280
 281 func isPowerOfTwo(x uintptr) bool {
 282         return x&(x-1) == 0
 283 }
 284
 285 // slicecopy is used to copy from a string or slice of pointerless elements into a slice.
 286 func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
 287         if fromLen == 0 || toLen == 0 {
 288                 return 0
 289         }
 290
 291         n := fromLen
 292         if toLen < n {
 293                 n = toLen
 294         }
 295
 296         if width == 0 {
 297                 return n
 298         }
 299
 300         size := uintptr(n) * width
 301         if raceenabled {
 302                 callerpc := getcallerpc()
 303                 pc := abi.FuncPCABIInternal(slicecopy)
 304                 racereadrangepc(fromPtr, size, callerpc, pc)
 305                 racewriterangepc(toPtr, size, callerpc, pc)
 306         }
 307         if msanenabled {
 308                 msanread(fromPtr, size)
 309                 msanwrite(toPtr, size)
 310         }
 311
 312         if size == 1 { // common case worth about 2x to do here
 313                 // TODO: is this still worth it with new memmove impl?
 314                 *(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
 315         } else {
 316                 memmove(toPtr, fromPtr, size)
 317         }
 318         return n
 319 }