diff options
Diffstat (limited to 'src/runtime')
| -rw-r--r-- | src/runtime/slice.go | 92 |
1 files changed, 56 insertions, 36 deletions
diff --git a/src/runtime/slice.go b/src/runtime/slice.go index 0a203e4101..284ee1f484 100644 --- a/src/runtime/slice.go +++ b/src/runtime/slice.go @@ -123,50 +123,70 @@ func mulUintptr(a, b uintptr) (uintptr, bool) { return math.MulUintptr(a, b) } -// growslice handles slice growth during append. -// It is passed the slice element type, the old slice, and the desired new minimum capacity, -// and it returns a new slice with at least that capacity, with the old data -// copied into it. -// The new slice's length is set to the old slice's length, -// NOT to the new requested capacity. -// This is for codegen convenience. The old slice's length is used immediately -// to calculate where to write new values during an append. -// TODO: When the old backend is gone, reconsider this decision. -// The SSA backend might prefer the new length or to return only ptr/cap and save stack space. -func growslice(et *_type, old slice, cap int) slice { +// growslice allocates new backing store for a slice. +// +// arguments: +// oldPtr = pointer to the slice's backing array +// newLen = new length (= oldLen + num) +// oldCap = original slice's capacity. +// num = number of elements being added +// et = element type +// +// return values: +// newPtr = pointer to the new backing store +// newLen = same value as the argument +// newCap = capacity of the new backing store +// +// Requires that uint(newLen) > uint(oldCap). +// Assumes the original slice length is newLen - num +// +// A new backing store is allocated with space for at least newLen elements. +// Existing entries [0, oldLen) are copied over to the new backing store. +// Added entries [oldLen, newLen) are not initialized by growslice +// (although for pointer-containing element types, they are zeroed). They +// must be initialized by the caller. +// Trailing entries [newLen, newCap) are zeroed. +// +// growslice's odd calling convention makes the generated code that calls +// this function simpler. In particular, it accepts and returns the +// new length so that the old length is not live (does not need to be +// spilled/restored) and the new length is returned (also does not need +// to be spilled/restored). +func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice { + oldLen := newLen - num if raceenabled { callerpc := getcallerpc() - racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, abi.FuncPCABIInternal(growslice)) + racereadrangepc(oldPtr, uintptr(oldLen*int(et.size)), callerpc, abi.FuncPCABIInternal(growslice)) } if msanenabled { - msanread(old.array, uintptr(old.len*int(et.size))) + msanread(oldPtr, uintptr(oldLen*int(et.size))) } if asanenabled { - asanread(old.array, uintptr(old.len*int(et.size))) + asanread(oldPtr, uintptr(oldLen*int(et.size))) } - if cap < old.cap { + if newLen < 0 { panic(errorString("growslice: len out of range")) } if et.size == 0 { // append should not create a slice with nil pointer but non-zero len. - // We assume that append doesn't need to preserve old.array in this case. - return slice{unsafe.Pointer(&zerobase), old.len, cap} + // We assume that append doesn't need to preserve oldPtr in this case. + return slice{unsafe.Pointer(&zerobase), newLen, newLen} } - newcap := old.cap + newcap := oldCap doublecap := newcap + newcap - if cap > doublecap { - newcap = cap + if newLen > doublecap { + newcap = newLen } else { const threshold = 256 - if old.cap < threshold { + if oldCap < threshold { newcap = doublecap } else { // Check 0 < newcap to detect overflow // and prevent an infinite loop. - for 0 < newcap && newcap < cap { + for 0 < newcap && newcap < newLen { // Transition from growing 2x for small slices // to growing 1.25x for large slices. This formula // gives a smooth-ish transition between the two. @@ -175,7 +195,7 @@ func growslice(et *_type, old slice, cap int) slice { // Set newcap to the requested cap when // the newcap calculation overflowed. if newcap <= 0 { - newcap = cap + newcap = newLen } } } @@ -188,14 +208,14 @@ func growslice(et *_type, old slice, cap int) slice { // For powers of 2, use a variable shift. switch { case et.size == 1: - lenmem = uintptr(old.len) - newlenmem = uintptr(cap) + lenmem = uintptr(oldLen) + newlenmem = uintptr(newLen) capmem = roundupsize(uintptr(newcap)) overflow = uintptr(newcap) > maxAlloc newcap = int(capmem) case et.size == goarch.PtrSize: - lenmem = uintptr(old.len) * goarch.PtrSize - newlenmem = uintptr(cap) * goarch.PtrSize + lenmem = uintptr(oldLen) * goarch.PtrSize + newlenmem = uintptr(newLen) * goarch.PtrSize capmem = roundupsize(uintptr(newcap) * goarch.PtrSize) overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize newcap = int(capmem / goarch.PtrSize) @@ -207,15 +227,15 @@ func growslice(et *_type, old slice, cap int) slice { } else { shift = uintptr(sys.Ctz32(uint32(et.size))) & 31 } - lenmem = uintptr(old.len) << shift - newlenmem = uintptr(cap) << shift + lenmem = uintptr(oldLen) << shift + newlenmem = uintptr(newLen) << shift capmem = roundupsize(uintptr(newcap) << shift) overflow = uintptr(newcap) > (maxAlloc >> shift) newcap = int(capmem >> shift) capmem = uintptr(newcap) << shift default: - lenmem = uintptr(old.len) * et.size - newlenmem = uintptr(cap) * et.size + lenmem = uintptr(oldLen) * et.size + newlenmem = uintptr(newLen) * et.size capmem, overflow = math.MulUintptr(et.size, uintptr(newcap)) capmem = roundupsize(capmem) newcap = int(capmem / et.size) @@ -242,21 +262,21 @@ func growslice(et *_type, old slice, cap int) slice { var p unsafe.Pointer if et.ptrdata == 0 { p = mallocgc(capmem, nil, false) - // The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length). + // The append() that calls growslice is going to overwrite from oldLen to newLen. // Only clear the part that will not be overwritten. memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem) } else { // Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory. p = mallocgc(capmem, et, true) if lenmem > 0 && writeBarrier.enabled { - // Only shade the pointers in old.array since we know the destination slice p + // Only shade the pointers in oldPtr since we know the destination slice p // only contains nil pointers because it has been cleared during alloc. - bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata) + bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.size+et.ptrdata) } } - memmove(p, old.array, lenmem) + memmove(p, oldPtr, lenmem) - return slice{p, old.len, newcap} + return slice{p, newLen, newcap} } func isPowerOfTwo(x uintptr) bool { |