golang源码分析-slice篇

1
2
3
4
5
6
7
8

type slice struct {
	// 底层数组的引用
	array unsafe.Pointer
	// 切片长度
	len   int
	// 切片容量
	cap   int
}

1
2
3
4
5

// 声明一个slice, 每个元素类型是int
var list []int

// 使用内置的make函数创建一个slice, 每个元素类型是int, 长度为1, 最多可容纳5个元素。使用该种方法生成的切片元素具有默认值
list := make([]int, 1, 5)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 创建一个slice
// 请求参数, et: 元素类型, len: 长度, cap: 容量
func makeslice(et *_type, len, cap int) unsafe.Pointer {
	// 计算出创建切片所占用的内存大小(每个元素类型所占用的大小*容量)
	mem, overflow := math.MulUintptr(et.size, uintptr(cap))
	// 判断切片所占用内存是否溢出、是否超过最大可分配大小、长度是否小于0、长度是否比容量大
	// 如果满足其中一个条件，则panic
	if overflow || mem > maxAlloc || len < 0 || len > cap {
		// NOTE: Produce a 'len out of range' error instead of a
		// 'cap out of range' error when someone does make([]T, bignumber).
		// 'cap out of range' is true too, but since the cap is only being
		// supplied implicitly, saying len is clearer.
		// See golang.org/issue/4085.
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			// 细分异常类型, 这个分支抛出长度限制异常
			panicmakeslicelen()
		}
		// 报出容量限制的异常
		panicmakeslicecap()
	}

	// 分配切片的内存
	return mallocgc(mem, et, true)
}

1
2
3

arr1 := []int{1,2,3}
arr2 := make([]int, 3)
copy(arr2, arr1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

// 该方法可以从字符串或一个切片中拷贝到新的切片内
// 请求参数: toPtr: 新切片的引用, toLen: 新切片的长度, fromPtr: 旧切片的指针, fromLen: 旧切片的长度, width: 切片单个元素的占用大小
// slicecopy is used to copy from a string or slice of pointerless elements into a slice.
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
	// 长度校验，如果旧切片或者新切片的长度有一个为0，那么没必要复制了，直接返回
	if fromLen == 0 || toLen == 0 {
		return 0
	}

	// 定义n, n为两个切片较短的长度
	// 该函数会复制切片，复制的结果取决于较短的切片，当较短的切片复制完成整个操作也就结束。
	// 所以需要n来记录较短切片的长度
	n := fromLen
	if toLen < n {
		n = toLen
	}

	// 如果单个元素不占用内存大小, 那么也没必要复制了, 直接返回较短的长度
	if width == 0 {
		return n
	}

	// 计算切片所占用的内存大小(切片长度*每个元素所占用的内存大小)
	size := uintptr(n) * width
	// 竞争检测
	if raceenabled {
		callerpc := getcallerpc()
		pc := abi.FuncPCABIInternal(slicecopy)
		racereadrangepc(fromPtr, size, callerpc, pc)
		racewriterangepc(toPtr, size, callerpc, pc)
	}
	if msanenabled {
		msanread(fromPtr, size)
		msanwrite(toPtr, size)
	}
	if asanenabled {
		asanread(fromPtr, size)
		asanwrite(toPtr, size)
	}

	// 如果切片占用为1字节，直接值拷贝过去
	if size == 1 { // common case worth about 2x to do here
		// TODO: is this still worth it with new memmove impl?
		*(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
	} else {
		// 否则调用memmove函数，拷贝数据
		memmove(toPtr, fromPtr, size)
	}
	return n
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

// 在append期间处理切片的增长
// 请其参数: et: 切片的元素类型, old: 扩容前的slice, cap: 扩容后切片的容量
func growslice(et *_type, old slice, cap int) slice {
	// 开启竞争检测
	if raceenabled {
		callerpc := getcallerpc()
		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, abi.FuncPCABIInternal(growslice))
	}
	if msanenabled {
		msanread(old.array, uintptr(old.len*int(et.size)))
	}
	if asanenabled {
		asanread(old.array, uintptr(old.len*int(et.size)))
	}

	if cap < old.cap {
		// 如果扩容后的容量比扩容前还小，panic
		panic(errorString("growslice: cap 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.
		// 如果元素所占用内存的大小为0，则new一个slice返回，底层数组指向空的数组
		return slice{unsafe.Pointer(&zerobase), old.len, cap}
	}

	newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {
		// 如果新容量比旧容量的两倍还大，则按新容量扩容
		newcap = cap
	} else {
		const threshold = 256
		if old.cap < threshold {
			// 旧容量比256小，则按两倍旧容量扩容
			newcap = doublecap
		} else {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			// 否则每次增长1.25倍容量，知道newcap大于等于cap才结束
			for 0 < newcap && newcap < cap {
				// Transition from growing 2x for small slices
				// to growing 1.25x for large slices. This formula
				// gives a smooth-ish transition between the two.
				newcap += (newcap + 3*threshold) / 4
			}
			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	// Specialize for common values of et.size.
	// For 1 we don't need any division/multiplication.
	// For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
	// For powers of 2, use a variable shift.
	// 根据切片元素类型所占用的大小，进行以下判断
	// 计算新切片的容量和长度
	switch {
	case et.size == 1:
		lenmem = uintptr(old.len)
		newlenmem = uintptr(cap)
		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
		capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
		newcap = int(capmem / goarch.PtrSize)
	case isPowerOfTwo(et.size):
		var shift uintptr
		if goarch.PtrSize == 8 {
			// Mask shift for better code generation.
			shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
		} else {
			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
		}
		lenmem = uintptr(old.len) << shift
		newlenmem = uintptr(cap) << shift
		capmem = roundupsize(uintptr(newcap) << shift)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
	default:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
		capmem = roundupsize(capmem)
		newcap = int(capmem / et.size)
	}

	// The check of overflow in addition to capmem > maxAlloc is needed
	// to prevent an overflow which can be used to trigger a segfault
	// on 32bit architectures with this example program:
	//
	// type T [1<<27 + 1]int64
	//
	// var d T
	// var s []T
	//
	// func main() {
	//   s = append(s, d, d, d, d)
	//   print(len(s), "\n")
	// }
	// 判断分配后是否溢出以及是否超出最大的可分配大小
	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: cap out of range"))
	}

	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).
		// 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 contains nil pointers because it has been cleared during alloc.
			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
		}
	}
	// 分配
	memmove(p, old.array, lenmem)

	return slice{p, old.len, newcap}
}