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