Source file src/pkg/runtime/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		"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.ptrdata == 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 lenmem > 0 && 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