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  // An 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  func makeslice(et *_type, len, cap int) unsafe.Pointer {
    35  	mem, overflow := math.MulUintptr(et.size, uintptr(cap))
    36  	if overflow || mem > maxAlloc || len < 0 || len > cap {
    37  		// NOTE: Produce a 'len out of range' error instead of a
    38  		// 'cap out of range' error when someone does make([]T, bignumber).
    39  		// 'cap out of range' is true too, but since the cap is only being
    40  		// supplied implicitly, saying len is clearer.
    41  		// See golang.org/issue/4085.
    42  		mem, overflow := math.MulUintptr(et.size, uintptr(len))
    43  		if overflow || mem > maxAlloc || len < 0 {
    44  			panicmakeslicelen()
    45  		}
    46  		panicmakeslicecap()
    47  	}
    48  
    49  	return mallocgc(mem, et, true)
    50  }
    51  
    52  func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {
    53  	len := int(len64)
    54  	if int64(len) != len64 {
    55  		panicmakeslicelen()
    56  	}
    57  
    58  	cap := int(cap64)
    59  	if int64(cap) != cap64 {
    60  		panicmakeslicecap()
    61  	}
    62  
    63  	return makeslice(et, len, cap)
    64  }
    65  
    66  // growslice handles slice growth during append.
    67  // It is passed the slice element type, the old slice, and the desired new minimum capacity,
    68  // and it returns a new slice with at least that capacity, with the old data
    69  // copied into it.
    70  // The new slice's length is set to the old slice's length,
    71  // NOT to the new requested capacity.
    72  // This is for codegen convenience. The old slice's length is used immediately
    73  // to calculate where to write new values during an append.
    74  // TODO: When the old backend is gone, reconsider this decision.
    75  // The SSA backend might prefer the new length or to return only ptr/cap and save stack space.
    76  func growslice(et *_type, old slice, cap int) slice {
    77  	if raceenabled {
    78  		callerpc := getcallerpc()
    79  		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
    80  	}
    81  	if msanenabled {
    82  		msanread(old.array, uintptr(old.len*int(et.size)))
    83  	}
    84  
    85  	if cap < old.cap {
    86  		panic(errorString("growslice: cap out of range"))
    87  	}
    88  
    89  	if et.size == 0 {
    90  		// append should not create a slice with nil pointer but non-zero len.
    91  		// We assume that append doesn't need to preserve old.array in this case.
    92  		return slice{unsafe.Pointer(&zerobase), old.len, cap}
    93  	}
    94  
    95  	newcap := old.cap
    96  	doublecap := newcap + newcap
    97  	if cap > doublecap {
    98  		newcap = cap
    99  	} else {
   100  		if old.len < 1024 {
   101  			newcap = doublecap
   102  		} else {
   103  			// Check 0 < newcap to detect overflow
   104  			// and prevent an infinite loop.
   105  			for 0 < newcap && newcap < cap {
   106  				newcap += newcap / 4
   107  			}
   108  			// Set newcap to the requested cap when
   109  			// the newcap calculation overflowed.
   110  			if newcap <= 0 {
   111  				newcap = cap
   112  			}
   113  		}
   114  	}
   115  
   116  	var overflow bool
   117  	var lenmem, newlenmem, capmem uintptr
   118  	// Specialize for common values of et.size.
   119  	// For 1 we don't need any division/multiplication.
   120  	// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
   121  	// For powers of 2, use a variable shift.
   122  	switch {
   123  	case et.size == 1:
   124  		lenmem = uintptr(old.len)
   125  		newlenmem = uintptr(cap)
   126  		capmem = roundupsize(uintptr(newcap))
   127  		overflow = uintptr(newcap) > maxAlloc
   128  		newcap = int(capmem)
   129  	case et.size == sys.PtrSize:
   130  		lenmem = uintptr(old.len) * sys.PtrSize
   131  		newlenmem = uintptr(cap) * sys.PtrSize
   132  		capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
   133  		overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
   134  		newcap = int(capmem / sys.PtrSize)
   135  	case isPowerOfTwo(et.size):
   136  		var shift uintptr
   137  		if sys.PtrSize == 8 {
   138  			// Mask shift for better code generation.
   139  			shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
   140  		} else {
   141  			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
   142  		}
   143  		lenmem = uintptr(old.len) << shift
   144  		newlenmem = uintptr(cap) << shift
   145  		capmem = roundupsize(uintptr(newcap) << shift)
   146  		overflow = uintptr(newcap) > (maxAlloc >> shift)
   147  		newcap = int(capmem >> shift)
   148  	default:
   149  		lenmem = uintptr(old.len) * et.size
   150  		newlenmem = uintptr(cap) * et.size
   151  		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
   152  		capmem = roundupsize(capmem)
   153  		newcap = int(capmem / et.size)
   154  	}
   155  
   156  	// The check of overflow in addition to capmem > maxAlloc is needed
   157  	// to prevent an overflow which can be used to trigger a segfault
   158  	// on 32bit architectures with this example program:
   159  	//
   160  	// type T [1<<27 + 1]int64
   161  	//
   162  	// var d T
   163  	// var s []T
   164  	//
   165  	// func main() {
   166  	//   s = append(s, d, d, d, d)
   167  	//   print(len(s), "\n")
   168  	// }
   169  	if overflow || capmem > maxAlloc {
   170  		panic(errorString("growslice: cap out of range"))
   171  	}
   172  
   173  	var p unsafe.Pointer
   174  	if et.kind&kindNoPointers != 0 {
   175  		p = mallocgc(capmem, nil, false)
   176  		// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
   177  		// Only clear the part that will not be overwritten.
   178  		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
   179  	} else {
   180  		// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
   181  		p = mallocgc(capmem, et, true)
   182  		if writeBarrier.enabled {
   183  			// Only shade the pointers in old.array since we know the destination slice p
   184  			// only contains nil pointers because it has been cleared during alloc.
   185  			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
   186  		}
   187  	}
   188  	memmove(p, old.array, lenmem)
   189  
   190  	return slice{p, old.len, newcap}
   191  }
   192  
   193  func isPowerOfTwo(x uintptr) bool {
   194  	return x&(x-1) == 0
   195  }
   196  
   197  func slicecopy(to, fm slice, width uintptr) int {
   198  	if fm.len == 0 || to.len == 0 {
   199  		return 0
   200  	}
   201  
   202  	n := fm.len
   203  	if to.len < n {
   204  		n = to.len
   205  	}
   206  
   207  	if width == 0 {
   208  		return n
   209  	}
   210  
   211  	if raceenabled {
   212  		callerpc := getcallerpc()
   213  		pc := funcPC(slicecopy)
   214  		racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
   215  		racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
   216  	}
   217  	if msanenabled {
   218  		msanwrite(to.array, uintptr(n*int(width)))
   219  		msanread(fm.array, uintptr(n*int(width)))
   220  	}
   221  
   222  	size := uintptr(n) * width
   223  	if size == 1 { // common case worth about 2x to do here
   224  		// TODO: is this still worth it with new memmove impl?
   225  		*(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
   226  	} else {
   227  		memmove(to.array, fm.array, size)
   228  	}
   229  	return n
   230  }
   231  
   232  func slicestringcopy(to []byte, fm string) int {
   233  	if len(fm) == 0 || len(to) == 0 {
   234  		return 0
   235  	}
   236  
   237  	n := len(fm)
   238  	if len(to) < n {
   239  		n = len(to)
   240  	}
   241  
   242  	if raceenabled {
   243  		callerpc := getcallerpc()
   244  		pc := funcPC(slicestringcopy)
   245  		racewriterangepc(unsafe.Pointer(&to[0]), uintptr(n), callerpc, pc)
   246  	}
   247  	if msanenabled {
   248  		msanwrite(unsafe.Pointer(&to[0]), uintptr(n))
   249  	}
   250  
   251  	memmove(unsafe.Pointer(&to[0]), stringStructOf(&fm).str, uintptr(n))
   252  	return n
   253  }
   254
View as plain text