Home | History | Annotate | Download | only in runtime 
      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 type slice struct {
     12 	array unsafe.Pointer
     13 	len   int
     14 	cap   int
     15 }
     16 
     17 // maxElems is a lookup table containing the maximum capacity for a slice.
     18 // The index is the size of the slice element.
     19 var maxElems = [...]uintptr{
     20 	^uintptr(0),
     21 	_MaxMem / 1, _MaxMem / 2, _MaxMem / 3, _MaxMem / 4,
     22 	_MaxMem / 5, _MaxMem / 6, _MaxMem / 7, _MaxMem / 8,
     23 	_MaxMem / 9, _MaxMem / 10, _MaxMem / 11, _MaxMem / 12,
     24 	_MaxMem / 13, _MaxMem / 14, _MaxMem / 15, _MaxMem / 16,
     25 	_MaxMem / 17, _MaxMem / 18, _MaxMem / 19, _MaxMem / 20,
     26 	_MaxMem / 21, _MaxMem / 22, _MaxMem / 23, _MaxMem / 24,
     27 	_MaxMem / 25, _MaxMem / 26, _MaxMem / 27, _MaxMem / 28,
     28 	_MaxMem / 29, _MaxMem / 30, _MaxMem / 31, _MaxMem / 32,
     29 }
     30 
     31 // maxSliceCap returns the maximum capacity for a slice.
     32 func maxSliceCap(elemsize uintptr) uintptr {
     33 	if elemsize < uintptr(len(maxElems)) {
     34 		return maxElems[elemsize]
     35 	}
     36 	return _MaxMem / elemsize
     37 }
     38 
     39 func makeslice(et *_type, len, cap int) slice {
     40 	// NOTE: The len > maxElements check here is not strictly necessary,
     41 	// but it produces a 'len out of range' error instead of a 'cap out of range' error
     42 	// when someone does make([]T, bignumber). 'cap out of range' is true too,
     43 	// but since the cap is only being supplied implicitly, saying len is clearer.
     44 	// See issue 4085.
     45 	maxElements := maxSliceCap(et.size)
     46 	if len < 0 || uintptr(len) > maxElements {
     47 		panic(errorString("makeslice: len out of range"))
     48 	}
     49 
     50 	if cap < len || uintptr(cap) > maxElements {
     51 		panic(errorString("makeslice: cap out of range"))
     52 	}
     53 
     54 	p := mallocgc(et.size*uintptr(cap), et, true)
     55 	return slice{p, len, cap}
     56 }
     57 
     58 func makeslice64(et *_type, len64, cap64 int64) slice {
     59 	len := int(len64)
     60 	if int64(len) != len64 {
     61 		panic(errorString("makeslice: len out of range"))
     62 	}
     63 
     64 	cap := int(cap64)
     65 	if int64(cap) != cap64 {
     66 		panic(errorString("makeslice: cap out of range"))
     67 	}
     68 
     69 	return makeslice(et, len, cap)
     70 }
     71 
     72 // growslice handles slice growth during append.
     73 // It is passed the slice element type, the old slice, and the desired new minimum capacity,
     74 // and it returns a new slice with at least that capacity, with the old data
     75 // copied into it.
     76 // The new slice's length is set to the old slice's length,
     77 // NOT to the new requested capacity.
     78 // This is for codegen convenience. The old slice's length is used immediately
     79 // to calculate where to write new values during an append.
     80 // TODO: When the old backend is gone, reconsider this decision.
     81 // The SSA backend might prefer the new length or to return only ptr/cap and save stack space.
     82 func growslice(et *_type, old slice, cap int) slice {
     83 	if raceenabled {
     84 		callerpc := getcallerpc(unsafe.Pointer(&et))
     85 		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
     86 	}
     87 	if msanenabled {
     88 		msanread(old.array, uintptr(old.len*int(et.size)))
     89 	}
     90 
     91 	if et.size == 0 {
     92 		if cap < old.cap {
     93 			panic(errorString("growslice: cap out of range"))
     94 		}
     95 		// append should not create a slice with nil pointer but non-zero len.
     96 		// We assume that append doesn't need to preserve old.array in this case.
     97 		return slice{unsafe.Pointer(&zerobase), old.len, cap}
     98 	}
     99 
    100 	newcap := old.cap
    101 	doublecap := newcap + newcap
    102 	if cap > doublecap {
    103 		newcap = cap
    104 	} else {
    105 		if old.len < 1024 {
    106 			newcap = doublecap
    107 		} else {
    108 			for newcap < cap {
    109 				newcap += newcap / 4
    110 			}
    111 		}
    112 	}
    113 
    114 	var lenmem, newlenmem, capmem uintptr
    115 	const ptrSize = unsafe.Sizeof((*byte)(nil))
    116 	switch et.size {
    117 	case 1:
    118 		lenmem = uintptr(old.len)
    119 		newlenmem = uintptr(cap)
    120 		capmem = roundupsize(uintptr(newcap))
    121 		newcap = int(capmem)
    122 	case ptrSize:
    123 		lenmem = uintptr(old.len) * ptrSize
    124 		newlenmem = uintptr(cap) * ptrSize
    125 		capmem = roundupsize(uintptr(newcap) * ptrSize)
    126 		newcap = int(capmem / ptrSize)
    127 	default:
    128 		lenmem = uintptr(old.len) * et.size
    129 		newlenmem = uintptr(cap) * et.size
    130 		capmem = roundupsize(uintptr(newcap) * et.size)
    131 		newcap = int(capmem / et.size)
    132 	}
    133 
    134 	if cap < old.cap || uintptr(newcap) > maxSliceCap(et.size) {
    135 		panic(errorString("growslice: cap out of range"))
    136 	}
    137 
    138 	var p unsafe.Pointer
    139 	if et.kind&kindNoPointers != 0 {
    140 		p = mallocgc(capmem, nil, false)
    141 		memmove(p, old.array, lenmem)
    142 		// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
    143 		// Only clear the part that will not be overwritten.
    144 		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    145 	} else {
    146 		// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
    147 		p = mallocgc(capmem, et, true)
    148 		if !writeBarrier.enabled {
    149 			memmove(p, old.array, lenmem)
    150 		} else {
    151 			for i := uintptr(0); i < lenmem; i += et.size {
    152 				typedmemmove(et, add(p, i), add(old.array, i))
    153 			}
    154 		}
    155 	}
    156 
    157 	return slice{p, old.len, newcap}
    158 }
    159 
    160 func slicecopy(to, fm slice, width uintptr) int {
    161 	if fm.len == 0 || to.len == 0 {
    162 		return 0
    163 	}
    164 
    165 	n := fm.len
    166 	if to.len < n {
    167 		n = to.len
    168 	}
    169 
    170 	if width == 0 {
    171 		return n
    172 	}
    173 
    174 	if raceenabled {
    175 		callerpc := getcallerpc(unsafe.Pointer(&to))
    176 		pc := funcPC(slicecopy)
    177 		racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
    178 		racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
    179 	}
    180 	if msanenabled {
    181 		msanwrite(to.array, uintptr(n*int(width)))
    182 		msanread(fm.array, uintptr(n*int(width)))
    183 	}
    184 
    185 	size := uintptr(n) * width
    186 	if size == 1 { // common case worth about 2x to do here
    187 		// TODO: is this still worth it with new memmove impl?
    188 		*(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
    189 	} else {
    190 		memmove(to.array, fm.array, size)
    191 	}
    192 	return n
    193 }
    194 
    195 func slicestringcopy(to []byte, fm string) int {
    196 	if len(fm) == 0 || len(to) == 0 {
    197 		return 0
    198 	}
    199 
    200 	n := len(fm)
    201 	if len(to) < n {
    202 		n = len(to)
    203 	}
    204 
    205 	if raceenabled {
    206 		callerpc := getcallerpc(unsafe.Pointer(&to))
    207 		pc := funcPC(slicestringcopy)
    208 		racewriterangepc(unsafe.Pointer(&to[0]), uintptr(n), callerpc, pc)
    209 	}
    210 	if msanenabled {
    211 		msanwrite(unsafe.Pointer(&to[0]), uintptr(n))
    212 	}
    213 
    214 	memmove(unsafe.Pointer(&to[0]), stringStructOf(&fm).str, uintptr(n))
    215 	return n
    216 }
    217