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 // maxElems is a lookup table containing the maximum capacity for a slice.
  27 // The index is the size of the slice element.
  28 var maxElems = [...]uintptr{
  29         ^uintptr(0),
  30         _MaxMem / 1, _MaxMem / 2, _MaxMem / 3, _MaxMem / 4,
  31         _MaxMem / 5, _MaxMem / 6, _MaxMem / 7, _MaxMem / 8,
  32         _MaxMem / 9, _MaxMem / 10, _MaxMem / 11, _MaxMem / 12,
  33         _MaxMem / 13, _MaxMem / 14, _MaxMem / 15, _MaxMem / 16,
  34         _MaxMem / 17, _MaxMem / 18, _MaxMem / 19, _MaxMem / 20,
  35         _MaxMem / 21, _MaxMem / 22, _MaxMem / 23, _MaxMem / 24,
  36         _MaxMem / 25, _MaxMem / 26, _MaxMem / 27, _MaxMem / 28,
  37         _MaxMem / 29, _MaxMem / 30, _MaxMem / 31, _MaxMem / 32,
  38 }
  39
  40 // maxSliceCap returns the maximum capacity for a slice.
  41 func maxSliceCap(elemsize uintptr) uintptr {
  42         if elemsize < uintptr(len(maxElems)) {
  43                 return maxElems[elemsize]
  44         }
  45         return _MaxMem / elemsize
  46 }
  47
  48 func makeslice(et *_type, len, cap int) slice {
  49         // NOTE: The len > maxElements check here is not strictly necessary,
  50         // but it produces a 'len out of range' error instead of a 'cap out of range' error
  51         // when someone does make([]T, bignumber). 'cap out of range' is true too,
  52         // but since the cap is only being supplied implicitly, saying len is clearer.
  53         // See issue 4085.
  54         maxElements := maxSliceCap(et.size)
  55         if len < 0 || uintptr(len) > maxElements {
  56                 panic(errorString("makeslice: len out of range"))
  57         }
  58
  59         if cap < len || uintptr(cap) > maxElements {
  60                 panic(errorString("makeslice: cap out of range"))
  61         }
  62
  63         // gccgo's current garbage collector requires using newarray,
  64         // not mallocgc here.  This can change back to mallocgc when
  65         // we port the garbage collector.
  66         p := newarray(et, cap)
  67         return slice{p, len, cap}
  68 }
  69
  70 func makeslice64(et *_type, len64, cap64 int64) slice {
  71         len := int(len64)
  72         if int64(len) != len64 {
  73                 panic(errorString("makeslice: len out of range"))
  74         }
  75
  76         cap := int(cap64)
  77         if int64(cap) != cap64 {
  78                 panic(errorString("makeslice: cap out of range"))
  79         }
  80
  81         return makeslice(et, len, cap)
  82 }
  83
  84 // growslice handles slice growth during append.
  85 // It is passed the slice element type, the old slice, and the desired new minimum capacity,
  86 // and it returns a new slice with at least that capacity, with the old data
  87 // copied into it.
  88 // The new slice's length is set to the requested capacity.
  89 func growslice(et *_type, old slice, cap int) slice {
  90         if raceenabled {
  91                 callerpc := getcallerpc(unsafe.Pointer(&et))
  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), cap, 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                         for newcap < cap {
 116                                 newcap += newcap / 4
 117                         }
 118                 }
 119         }
 120
 121         var lenmem, newlenmem, capmem uintptr
 122         const ptrSize = unsafe.Sizeof((*byte)(nil))
 123         switch et.size {
 124         case 1:
 125                 lenmem = uintptr(old.len)
 126                 newlenmem = uintptr(cap)
 127                 capmem = roundupsize(uintptr(newcap))
 128                 newcap = int(capmem)
 129         case ptrSize:
 130                 lenmem = uintptr(old.len) * ptrSize
 131                 newlenmem = uintptr(cap) * ptrSize
 132                 capmem = roundupsize(uintptr(newcap) * ptrSize)
 133                 newcap = int(capmem / ptrSize)
 134         default:
 135                 lenmem = uintptr(old.len) * et.size
 136                 newlenmem = uintptr(cap) * et.size
 137                 capmem = roundupsize(uintptr(newcap) * et.size)
 138                 newcap = int(capmem / et.size)
 139         }
 140
 141         if cap < old.cap || uintptr(newcap) > maxSliceCap(et.size) {
 142                 panic(errorString("growslice: cap out of range"))
 143         }
 144
 145         var p unsafe.Pointer
 146         if et.kind&kindNoPointers != 0 {
 147                 // gccgo's current GC requires newarray, not mallocgc.
 148                 p = newarray(et, newcap)
 149                 memmove(p, old.array, lenmem)
 150                 // The call to memclr is not needed for gccgo since
 151                 // the newarray function will zero the memory.
 152                 // Calling memclr is also wrong since we allocated
 153                 // newcap*et.size bytes, which is not the same as capmem.
 154                 // The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
 155                 // Only clear the part that will not be overwritten.
 156                 // memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
 157                 _ = newlenmem
 158         } else {
 159                 // Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
 160                 // gccgo's current GC requires newarray, not mallocgc.
 161                 p = newarray(et, newcap)
 162                 if !writeBarrier.enabled {
 163                         memmove(p, old.array, lenmem)
 164                 } else {
 165                         for i := uintptr(0); i < lenmem; i += et.size {
 166                                 typedmemmove(et, add(p, i), add(old.array, i))
 167                         }
 168                 }
 169         }
 170
 171         return slice{p, cap, newcap}
 172 }
 173
 174 func slicecopy(to, fm slice, width uintptr) int {
 175         if fm.len == 0 || to.len == 0 {
 176                 return 0
 177         }
 178
 179         n := fm.len
 180         if to.len < n {
 181                 n = to.len
 182         }
 183
 184         if width == 0 {
 185                 return n
 186         }
 187
 188         if raceenabled {
 189                 callerpc := getcallerpc(unsafe.Pointer(&to))
 190                 pc := funcPC(slicecopy)
 191                 racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
 192                 racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
 193         }
 194         if msanenabled {
 195                 msanwrite(to.array, uintptr(n*int(width)))
 196                 msanread(fm.array, uintptr(n*int(width)))
 197         }
 198
 199         size := uintptr(n) * width
 200         if size == 1 { // common case worth about 2x to do here
 201                 // TODO: is this still worth it with new memmove impl?
 202                 *(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
 203         } else {
 204                 memmove(to.array, fm.array, size)
 205         }
 206         return n
 207 }
 208
 209 func slicestringcopy(to []byte, fm string) int {
 210         if len(fm) == 0 || len(to) == 0 {
 211                 return 0
 212         }
 213
 214         n := len(fm)
 215         if len(to) < n {
 216                 n = len(to)
 217         }
 218
 219         if raceenabled {
 220                 callerpc := getcallerpc(unsafe.Pointer(&to))
 221                 pc := funcPC(slicestringcopy)
 222                 racewriterangepc(unsafe.Pointer(&to[0]), uintptr(n), callerpc, pc)
 223         }
 224         if msanenabled {
 225                 msanwrite(unsafe.Pointer(&to[0]), uintptr(n))
 226         }
 227
 228         memmove(unsafe.Pointer(&to[0]), stringStructOf(&fm).str, uintptr(n))
 229         return n
 230 }