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