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