slice.go

Documentation: 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  	"runtime/internal/sys"
     9  	"unsafe"
    10  )
    11  
    12  type slice struct {
    13  	array unsafe.Pointer
    14  	len   int
    15  	cap   int
    16  }
    17  
    18  // An notInHeapSlice is a slice backed by go:notinheap memory.
    19  type notInHeapSlice struct {
    20  	array *notInHeap
    21  	len   int
    22  	cap   int
    23  }
    24  
    25  // maxElems is a lookup table containing the maximum capacity for a slice.
    26  // The index is the size of the slice element.
    27  var maxElems = [...]uintptr{
    28  	^uintptr(0),
    29  	maxAlloc / 1, maxAlloc / 2, maxAlloc / 3, maxAlloc / 4,
    30  	maxAlloc / 5, maxAlloc / 6, maxAlloc / 7, maxAlloc / 8,
    31  	maxAlloc / 9, maxAlloc / 10, maxAlloc / 11, maxAlloc / 12,
    32  	maxAlloc / 13, maxAlloc / 14, maxAlloc / 15, maxAlloc / 16,
    33  	maxAlloc / 17, maxAlloc / 18, maxAlloc / 19, maxAlloc / 20,
    34  	maxAlloc / 21, maxAlloc / 22, maxAlloc / 23, maxAlloc / 24,
    35  	maxAlloc / 25, maxAlloc / 26, maxAlloc / 27, maxAlloc / 28,
    36  	maxAlloc / 29, maxAlloc / 30, maxAlloc / 31, maxAlloc / 32,
    37  }
    38  
    39  // maxSliceCap returns the maximum capacity for a slice.
    40  func maxSliceCap(elemsize uintptr) uintptr {
    41  	if elemsize < uintptr(len(maxElems)) {
    42  		return maxElems[elemsize]
    43  	}
    44  	return maxAlloc / elemsize
    45  }
    46  
    47  func panicmakeslicelen() {
    48  	panic(errorString("makeslice: len out of range"))
    49  }
    50  
    51  func panicmakeslicecap() {
    52  	panic(errorString("makeslice: cap out of range"))
    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  		panicmakeslicelen()
    64  	}
    65  
    66  	if cap < len || uintptr(cap) > maxElements {
    67  		panicmakeslicecap()
    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  		panicmakeslicelen()
    78  	}
    79  
    80  	cap := int(cap64)
    81  	if int64(cap) != cap64 {
    82  		panicmakeslicecap()
    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 old slice's length,
    93  // NOT to the new requested capacity.
    94  // This is for codegen convenience. The old slice's length is used immediately
    95  // to calculate where to write new values during an append.
    96  // TODO: When the old backend is gone, reconsider this decision.
    97  // The SSA backend might prefer the new length or to return only ptr/cap and save stack space.
    98  func growslice(et *_type, old slice, cap int) slice {
    99  	if raceenabled {
   100  		callerpc := getcallerpc()
   101  		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
   102  	}
   103  	if msanenabled {
   104  		msanread(old.array, uintptr(old.len*int(et.size)))
   105  	}
   106  
   107  	if et.size == 0 {
   108  		if cap < old.cap {
   109  			panic(errorString("growslice: cap out of range"))
   110  		}
   111  		// append should not create a slice with nil pointer but non-zero len.
   112  		// We assume that append doesn't need to preserve old.array in this case.
   113  		return slice{unsafe.Pointer(&zerobase), old.len, cap}
   114  	}
   115  
   116  	newcap := old.cap
   117  	doublecap := newcap + newcap
   118  	if cap > doublecap {
   119  		newcap = cap
   120  	} else {
   121  		if old.len < 1024 {
   122  			newcap = doublecap
   123  		} else {
   124  			// Check 0 < newcap to detect overflow
   125  			// and prevent an infinite loop.
   126  			for 0 < newcap && newcap < cap {
   127  				newcap += newcap / 4
   128  			}
   129  			// Set newcap to the requested cap when
   130  			// the newcap calculation overflowed.
   131  			if newcap <= 0 {
   132  				newcap = cap
   133  			}
   134  		}
   135  	}
   136  
   137  	var overflow bool
   138  	var lenmem, newlenmem, capmem uintptr
   139  	// Specialize for common values of et.size.
   140  	// For 1 we don't need any division/multiplication.
   141  	// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
   142  	// For powers of 2, use a variable shift.
   143  	switch {
   144  	case et.size == 1:
   145  		lenmem = uintptr(old.len)
   146  		newlenmem = uintptr(cap)
   147  		capmem = roundupsize(uintptr(newcap))
   148  		overflow = uintptr(newcap) > maxAlloc
   149  		newcap = int(capmem)
   150  	case et.size == sys.PtrSize:
   151  		lenmem = uintptr(old.len) * sys.PtrSize
   152  		newlenmem = uintptr(cap) * sys.PtrSize
   153  		capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
   154  		overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
   155  		newcap = int(capmem / sys.PtrSize)
   156  	case isPowerOfTwo(et.size):
   157  		var shift uintptr
   158  		if sys.PtrSize == 8 {
   159  			// Mask shift for better code generation.
   160  			shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
   161  		} else {
   162  			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
   163  		}
   164  		lenmem = uintptr(old.len) << shift
   165  		newlenmem = uintptr(cap) << shift
   166  		capmem = roundupsize(uintptr(newcap) << shift)
   167  		overflow = uintptr(newcap) > (maxAlloc >> shift)
   168  		newcap = int(capmem >> shift)
   169  	default:
   170  		lenmem = uintptr(old.len) * et.size
   171  		newlenmem = uintptr(cap) * et.size
   172  		capmem = roundupsize(uintptr(newcap) * et.size)
   173  		overflow = uintptr(newcap) > maxSliceCap(et.size)
   174  		newcap = int(capmem / et.size)
   175  	}
   176  
   177  	// The check of overflow (uintptr(newcap) > maxSliceCap(et.size))
   178  	// in addition to capmem > _MaxMem is needed to prevent an overflow
   179  	// which can be used to trigger a segfault on 32bit architectures
   180  	// with this example program:
   181  	//
   182  	// type T [1<<27 + 1]int64
   183  	//
   184  	// var d T
   185  	// var s []T
   186  	//
   187  	// func main() {
   188  	//   s = append(s, d, d, d, d)
   189  	//   print(len(s), "\n")
   190  	// }
   191  	if cap < old.cap || overflow || capmem > maxAlloc {
   192  		panic(errorString("growslice: cap out of range"))
   193  	}
   194  
   195  	var p unsafe.Pointer
   196  	if et.kind&kindNoPointers != 0 {
   197  		p = mallocgc(capmem, nil, false)
   198  		memmove(p, old.array, lenmem)
   199  		// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
   200  		// Only clear the part that will not be overwritten.
   201  		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
   202  	} else {
   203  		// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
   204  		p = mallocgc(capmem, et, true)
   205  		if !writeBarrier.enabled {
   206  			memmove(p, old.array, lenmem)
   207  		} else {
   208  			for i := uintptr(0); i < lenmem; i += et.size {
   209  				typedmemmove(et, add(p, i), add(old.array, i))
   210  			}
   211  		}
   212  	}
   213  
   214  	return slice{p, old.len, newcap}
   215  }
   216  
   217  func isPowerOfTwo(x uintptr) bool {
   218  	return x&(x-1) == 0
   219  }
   220  
   221  func slicecopy(to, fm slice, width uintptr) int {
   222  	if fm.len == 0 || to.len == 0 {
   223  		return 0
   224  	}
   225  
   226  	n := fm.len
   227  	if to.len < n {
   228  		n = to.len
   229  	}
   230  
   231  	if width == 0 {
   232  		return n
   233  	}
   234  
   235  	if raceenabled {
   236  		callerpc := getcallerpc()
   237  		pc := funcPC(slicecopy)
   238  		racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
   239  		racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
   240  	}
   241  	if msanenabled {
   242  		msanwrite(to.array, uintptr(n*int(width)))
   243  		msanread(fm.array, uintptr(n*int(width)))
   244  	}
   245  
   246  	size := uintptr(n) * width
   247  	if size == 1 { // common case worth about 2x to do here
   248  		// TODO: is this still worth it with new memmove impl?
   249  		*(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
   250  	} else {
   251  		memmove(to.array, fm.array, size)
   252  	}
   253  	return n
   254  }
   255  
   256  func slicestringcopy(to []byte, fm string) int {
   257  	if len(fm) == 0 || len(to) == 0 {
   258  		return 0
   259  	}
   260  
   261  	n := len(fm)
   262  	if len(to) < n {
   263  		n = len(to)
   264  	}
   265  
   266  	if raceenabled {
   267  		callerpc := getcallerpc()
   268  		pc := funcPC(slicestringcopy)
   269  		racewriterangepc(unsafe.Pointer(&to[0]), uintptr(n), callerpc, pc)
   270  	}
   271  	if msanenabled {
   272  		msanwrite(unsafe.Pointer(&to[0]), uintptr(n))
   273  	}
   274  
   275  	memmove(unsafe.Pointer(&to[0]), stringStructOf(&fm).str, uintptr(n))
   276  	return n
   277  }
   278
View as plain text