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         "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
  20 type 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.
  27 type 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.
  35 var 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.
  48 func maxSliceCap(elemsize uintptr) uintptr {
  49         if elemsize < uintptr(len(maxElems)) {
  50                 return maxElems[elemsize]
  51         }
  52         return _MaxMem / elemsize
  53 }
  54
  55 func 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
  74 func 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.
  93 func 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
 196 func 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
 231 func 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 }