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