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         p := mallocgc(et.size*uintptr(cap), et, true)
  64         return slice{p, len, cap}
  65 }
  66
  67 func makeslice64(et *_type, len64, cap64 int64) slice {
  68         len := int(len64)
  69         if int64(len) != len64 {
  70                 panic(errorString("makeslice: len out of range"))
  71         }
  72
  73         cap := int(cap64)
  74         if int64(cap) != cap64 {
  75                 panic(errorString("makeslice: cap out of range"))
  76         }
  77
  78         return makeslice(et, len, cap)
  79 }
  80
  81 // growslice handles slice growth during append.
  82 // It is passed the slice element type, the old slice, and the desired new minimum capacity,
  83 // and it returns a new slice with at least that capacity, with the old data
  84 // copied into it.
  85 // The new slice's length is set to the requested capacity.
  86 func growslice(et *_type, old slice, cap int) slice {
  87         if raceenabled {
  88                 callerpc := getcallerpc(unsafe.Pointer(&et))
  89                 racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
  90         }
  91         if msanenabled {
  92                 msanread(old.array, uintptr(old.len*int(et.size)))
  93         }
  94
  95         if et.size == 0 {
  96                 if cap < old.cap {
  97                         panic(errorString("growslice: cap out of range"))
  98                 }
  99                 // append should not create a slice with nil pointer but non-zero len.
 100                 // We assume that append doesn't need to preserve old.array in this case.
 101                 return slice{unsafe.Pointer(&zerobase), cap, cap}
 102         }
 103
 104         newcap := old.cap
 105         doublecap := newcap + newcap
 106         if cap > doublecap {
 107                 newcap = cap
 108         } else {
 109                 if old.len < 1024 {
 110                         newcap = doublecap
 111                 } else {
 112                         for newcap < cap {
 113                                 newcap += newcap / 4
 114                         }
 115                 }
 116         }
 117
 118         var lenmem, newlenmem, capmem uintptr
 119         const ptrSize = unsafe.Sizeof((*byte)(nil))
 120         switch et.size {
 121         case 1:
 122                 lenmem = uintptr(old.len)
 123                 newlenmem = uintptr(cap)
 124                 capmem = roundupsize(uintptr(newcap))
 125                 newcap = int(capmem)
 126         case ptrSize:
 127                 lenmem = uintptr(old.len) * ptrSize
 128                 newlenmem = uintptr(cap) * ptrSize
 129                 capmem = roundupsize(uintptr(newcap) * ptrSize)
 130                 newcap = int(capmem / ptrSize)
 131         default:
 132                 lenmem = uintptr(old.len) * et.size
 133                 newlenmem = uintptr(cap) * et.size
 134                 capmem = roundupsize(uintptr(newcap) * et.size)
 135                 newcap = int(capmem / et.size)
 136         }
 137
 138         if cap < old.cap || uintptr(newcap) > maxSliceCap(et.size) {
 139                 panic(errorString("growslice: cap out of range"))
 140         }
 141
 142         var p unsafe.Pointer
 143         if et.kind&kindNoPointers != 0 {
 144                 p = mallocgc(capmem, nil, false)
 145                 memmove(p, old.array, lenmem)
 146                 // The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
 147                 // Only clear the part that will not be overwritten.
 148                 memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
 149         } else {
 150                 // Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
 151                 p = mallocgc(capmem, et, true)
 152                 if !writeBarrier.enabled {
 153                         memmove(p, old.array, lenmem)
 154                 } else {
 155                         for i := uintptr(0); i < lenmem; i += et.size {
 156                                 typedmemmove(et, add(p, i), add(old.array, i))
 157                         }
 158                 }
 159         }
 160
 161         return slice{p, cap, newcap}
 162 }
 163
 164 func slicecopy(to, fm slice, width uintptr) int {
 165         if fm.len == 0 || to.len == 0 {
 166                 return 0
 167         }
 168
 169         n := fm.len
 170         if to.len < n {
 171                 n = to.len
 172         }
 173
 174         if width == 0 {
 175                 return n
 176         }
 177
 178         if raceenabled {
 179                 callerpc := getcallerpc(unsafe.Pointer(&to))
 180                 pc := funcPC(slicecopy)
 181                 racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
 182                 racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
 183         }
 184         if msanenabled {
 185                 msanwrite(to.array, uintptr(n*int(width)))
 186                 msanread(fm.array, uintptr(n*int(width)))
 187         }
 188
 189         size := uintptr(n) * width
 190         if size == 1 { // common case worth about 2x to do here
 191                 // TODO: is this still worth it with new memmove impl?
 192                 *(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
 193         } else {
 194                 memmove(to.array, fm.array, size)
 195         }
 196         return n
 197 }
 198
 199 func slicestringcopy(to []byte, fm string) int {
 200         if len(fm) == 0 || len(to) == 0 {
 201                 return 0
 202         }
 203
 204         n := len(fm)
 205         if len(to) < n {
 206                 n = len(to)
 207         }
 208
 209         if raceenabled {
 210                 callerpc := getcallerpc(unsafe.Pointer(&to))
 211                 pc := funcPC(slicestringcopy)
 212                 racewriterangepc(unsafe.Pointer(&to[0]), uintptr(n), callerpc, pc)
 213         }
 214         if msanenabled {
 215                 msanwrite(unsafe.Pointer(&to[0]), uintptr(n))
 216         }
 217
 218         memmove(unsafe.Pointer(&to[0]), stringStructOf(&fm).str, uintptr(n))
 219         return n
 220 }