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  	"internal/abi"
     9  	"internal/goarch"
    10  	"runtime/internal/math"
    11  	"runtime/internal/sys"
    12  	"unsafe"
    13  )
    14  
    15  type slice struct {
    16  	array unsafe.Pointer
    17  	len   int
    18  	cap   int
    19  }
    20  
    21  // A notInHeapSlice is a slice backed by go:notinheap memory.
    22  type notInHeapSlice struct {
    23  	array *notInHeap
    24  	len   int
    25  	cap   int
    26  }
    27  
    28  func panicmakeslicelen() {
    29  	panic(errorString("makeslice: len out of range"))
    30  }
    31  
    32  func panicmakeslicecap() {
    33  	panic(errorString("makeslice: cap out of range"))
    34  }
    35  
    36  // makeslicecopy allocates a slice of "tolen" elements of type "et",
    37  // then copies "fromlen" elements of type "et" into that new allocation from "from".
    38  func makeslicecopy(et *_type, tolen int, fromlen int, from unsafe.Pointer) unsafe.Pointer {
    39  	var tomem, copymem uintptr
    40  	if uintptr(tolen) > uintptr(fromlen) {
    41  		var overflow bool
    42  		tomem, overflow = math.MulUintptr(et.size, uintptr(tolen))
    43  		if overflow || tomem > maxAlloc || tolen < 0 {
    44  			panicmakeslicelen()
    45  		}
    46  		copymem = et.size * uintptr(fromlen)
    47  	} else {
    48  		// fromlen is a known good length providing and equal or greater than tolen,
    49  		// thereby making tolen a good slice length too as from and to slices have the
    50  		// same element width.
    51  		tomem = et.size * uintptr(tolen)
    52  		copymem = tomem
    53  	}
    54  
    55  	var to unsafe.Pointer
    56  	if et.ptrdata == 0 {
    57  		to = mallocgc(tomem, nil, false)
    58  		if copymem < tomem {
    59  			memclrNoHeapPointers(add(to, copymem), tomem-copymem)
    60  		}
    61  	} else {
    62  		// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
    63  		to = mallocgc(tomem, et, true)
    64  		if copymem > 0 && writeBarrier.enabled {
    65  			// Only shade the pointers in old.array since we know the destination slice to
    66  			// only contains nil pointers because it has been cleared during alloc.
    67  			bulkBarrierPreWriteSrcOnly(uintptr(to), uintptr(from), copymem)
    68  		}
    69  	}
    70  
    71  	if raceenabled {
    72  		callerpc := getcallerpc()
    73  		pc := abi.FuncPCABIInternal(makeslicecopy)
    74  		racereadrangepc(from, copymem, callerpc, pc)
    75  	}
    76  	if msanenabled {
    77  		msanread(from, copymem)
    78  	}
    79  	if asanenabled {
    80  		asanread(from, copymem)
    81  	}
    82  
    83  	memmove(to, from, copymem)
    84  
    85  	return to
    86  }
    87  
    88  func makeslice(et *_type, len, cap int) unsafe.Pointer {
    89  	mem, overflow := math.MulUintptr(et.size, uintptr(cap))
    90  	if overflow || mem > maxAlloc || len < 0 || len > cap {
    91  		// NOTE: Produce a 'len out of range' error instead of a
    92  		// 'cap out of range' error when someone does make([]T, bignumber).
    93  		// 'cap out of range' is true too, but since the cap is only being
    94  		// supplied implicitly, saying len is clearer.
    95  		// See golang.org/issue/4085.
    96  		mem, overflow := math.MulUintptr(et.size, uintptr(len))
    97  		if overflow || mem > maxAlloc || len < 0 {
    98  			panicmakeslicelen()
    99  		}
   100  		panicmakeslicecap()
   101  	}
   102  
   103  	return mallocgc(mem, et, true)
   104  }
   105  
   106  func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {
   107  	len := int(len64)
   108  	if int64(len) != len64 {
   109  		panicmakeslicelen()
   110  	}
   111  
   112  	cap := int(cap64)
   113  	if int64(cap) != cap64 {
   114  		panicmakeslicecap()
   115  	}
   116  
   117  	return makeslice(et, len, cap)
   118  }
   119  
   120  func unsafeslice(et *_type, ptr unsafe.Pointer, len int) {
   121  	if len < 0 {
   122  		panicunsafeslicelen()
   123  	}
   124  
   125  	mem, overflow := math.MulUintptr(et.size, uintptr(len))
   126  	if overflow || mem > -uintptr(ptr) {
   127  		if ptr == nil {
   128  			panic(errorString("unsafe.Slice: ptr is nil and len is not zero"))
   129  		}
   130  		panicunsafeslicelen()
   131  	}
   132  }
   133  
   134  func unsafeslice64(et *_type, ptr unsafe.Pointer, len64 int64) {
   135  	len := int(len64)
   136  	if int64(len) != len64 {
   137  		panicunsafeslicelen()
   138  	}
   139  	unsafeslice(et, ptr, len)
   140  }
   141  
   142  func unsafeslicecheckptr(et *_type, ptr unsafe.Pointer, len64 int64) {
   143  	unsafeslice64(et, ptr, len64)
   144  
   145  	// Check that underlying array doesn't straddle multiple heap objects.
   146  	// unsafeslice64 has already checked for overflow.
   147  	if checkptrStraddles(ptr, uintptr(len64)*et.size) {
   148  		throw("checkptr: unsafe.Slice result straddles multiple allocations")
   149  	}
   150  }
   151  
   152  func panicunsafeslicelen() {
   153  	panic(errorString("unsafe.Slice: len out of range"))
   154  }
   155  
   156  // growslice handles slice growth during append.
   157  // It is passed the slice element type, the old slice, and the desired new minimum capacity,
   158  // and it returns a new slice with at least that capacity, with the old data
   159  // copied into it.
   160  // The new slice's length is set to the old slice's length,
   161  // NOT to the new requested capacity.
   162  // This is for codegen convenience. The old slice's length is used immediately
   163  // to calculate where to write new values during an append.
   164  // TODO: When the old backend is gone, reconsider this decision.
   165  // The SSA backend might prefer the new length or to return only ptr/cap and save stack space.
   166  func growslice(et *_type, old slice, cap int) slice {
   167  	if raceenabled {
   168  		callerpc := getcallerpc()
   169  		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, abi.FuncPCABIInternal(growslice))
   170  	}
   171  	if msanenabled {
   172  		msanread(old.array, uintptr(old.len*int(et.size)))
   173  	}
   174  	if asanenabled {
   175  		asanread(old.array, uintptr(old.len*int(et.size)))
   176  	}
   177  
   178  	if cap < old.cap {
   179  		panic(errorString("growslice: cap out of range"))
   180  	}
   181  
   182  	if et.size == 0 {
   183  		// append should not create a slice with nil pointer but non-zero len.
   184  		// We assume that append doesn't need to preserve old.array in this case.
   185  		return slice{unsafe.Pointer(&zerobase), old.len, cap}
   186  	}
   187  
   188  	newcap := old.cap
   189  	doublecap := newcap + newcap
   190  	if cap > doublecap {
   191  		newcap = cap
   192  	} else {
   193  		const threshold = 256
   194  		if old.cap < threshold {
   195  			newcap = doublecap
   196  		} else {
   197  			// Check 0 < newcap to detect overflow
   198  			// and prevent an infinite loop.
   199  			for 0 < newcap && newcap < cap {
   200  				// Transition from growing 2x for small slices
   201  				// to growing 1.25x for large slices. This formula
   202  				// gives a smooth-ish transition between the two.
   203  				newcap += (newcap + 3*threshold) / 4
   204  			}
   205  			// Set newcap to the requested cap when
   206  			// the newcap calculation overflowed.
   207  			if newcap <= 0 {
   208  				newcap = cap
   209  			}
   210  		}
   211  	}
   212  
   213  	var overflow bool
   214  	var lenmem, newlenmem, capmem uintptr
   215  	// Specialize for common values of et.size.
   216  	// For 1 we don't need any division/multiplication.
   217  	// For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
   218  	// For powers of 2, use a variable shift.
   219  	switch {
   220  	case et.size == 1:
   221  		lenmem = uintptr(old.len)
   222  		newlenmem = uintptr(cap)
   223  		capmem = roundupsize(uintptr(newcap))
   224  		overflow = uintptr(newcap) > maxAlloc
   225  		newcap = int(capmem)
   226  	case et.size == goarch.PtrSize:
   227  		lenmem = uintptr(old.len) * goarch.PtrSize
   228  		newlenmem = uintptr(cap) * goarch.PtrSize
   229  		capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
   230  		overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
   231  		newcap = int(capmem / goarch.PtrSize)
   232  	case isPowerOfTwo(et.size):
   233  		var shift uintptr
   234  		if goarch.PtrSize == 8 {
   235  			// Mask shift for better code generation.
   236  			shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
   237  		} else {
   238  			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
   239  		}
   240  		lenmem = uintptr(old.len) << shift
   241  		newlenmem = uintptr(cap) << shift
   242  		capmem = roundupsize(uintptr(newcap) << shift)
   243  		overflow = uintptr(newcap) > (maxAlloc >> shift)
   244  		newcap = int(capmem >> shift)
   245  	default:
   246  		lenmem = uintptr(old.len) * et.size
   247  		newlenmem = uintptr(cap) * et.size
   248  		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
   249  		capmem = roundupsize(capmem)
   250  		newcap = int(capmem / et.size)
   251  	}
   252  
   253  	// The check of overflow in addition to capmem > maxAlloc is needed
   254  	// to prevent an overflow which can be used to trigger a segfault
   255  	// on 32bit architectures with this example program:
   256  	//
   257  	// type T [1<<27 + 1]int64
   258  	//
   259  	// var d T
   260  	// var s []T
   261  	//
   262  	// func main() {
   263  	//   s = append(s, d, d, d, d)
   264  	//   print(len(s), "\n")
   265  	// }
   266  	if overflow || capmem > maxAlloc {
   267  		panic(errorString("growslice: cap out of range"))
   268  	}
   269  
   270  	var p unsafe.Pointer
   271  	if et.ptrdata == 0 {
   272  		p = mallocgc(capmem, nil, false)
   273  		// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
   274  		// Only clear the part that will not be overwritten.
   275  		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
   276  	} else {
   277  		// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
   278  		p = mallocgc(capmem, et, true)
   279  		if lenmem > 0 && writeBarrier.enabled {
   280  			// Only shade the pointers in old.array since we know the destination slice p
   281  			// only contains nil pointers because it has been cleared during alloc.
   282  			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
   283  		}
   284  	}
   285  	memmove(p, old.array, lenmem)
   286  
   287  	return slice{p, old.len, newcap}
   288  }
   289  
   290  func isPowerOfTwo(x uintptr) bool {
   291  	return x&(x-1) == 0
   292  }
   293  
   294  // slicecopy is used to copy from a string or slice of pointerless elements into a slice.
   295  func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
   296  	if fromLen == 0 || toLen == 0 {
   297  		return 0
   298  	}
   299  
   300  	n := fromLen
   301  	if toLen < n {
   302  		n = toLen
   303  	}
   304  
   305  	if width == 0 {
   306  		return n
   307  	}
   308  
   309  	size := uintptr(n) * width
   310  	if raceenabled {
   311  		callerpc := getcallerpc()
   312  		pc := abi.FuncPCABIInternal(slicecopy)
   313  		racereadrangepc(fromPtr, size, callerpc, pc)
   314  		racewriterangepc(toPtr, size, callerpc, pc)
   315  	}
   316  	if msanenabled {
   317  		msanread(fromPtr, size)
   318  		msanwrite(toPtr, size)
   319  	}
   320  	if asanenabled {
   321  		asanread(fromPtr, size)
   322  		asanwrite(toPtr, size)
   323  	}
   324  
   325  	if size == 1 { // common case worth about 2x to do here
   326  		// TODO: is this still worth it with new memmove impl?
   327  		*(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
   328  	} else {
   329  		memmove(toPtr, fromPtr, size)
   330  	}
   331  	return n
   332  }
   333
View as plain text