Slice(原理)

1
2
3
4
5
6

// A notInHeapSlice is a slice backed by go:notinheap memory.
type notInHeapSlice struct {
    array *notInHeap    // 指向一个起始地址
    len   int
    cap   int
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// notInHeap is off-heap memory allocated by a lower-level allocator
// like sysAlloc or persistentAlloc.
//
// In general, it's better to use real types marked as go:notinheap,
// but this serves as a generic type for situations where that isn't
// possible (like in the allocators).
//
// TODO: Use this as the return type of sysAlloc, persistentAlloc, etc?
//
//go:notinheap
type notInHeap struct{}

1
2
3
4

func (p *notInHeap) add(bytes uintptr) *notInHeap {
    // p + bytes
    return (*notInHeap)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) + bytes))
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// The make built-in function allocates and initializes an object of type
// slice, map, or chan (only). Like new, the first argument is a type, not a
// value. Unlike new, make's return type is the same as the type of its
// argument, not a pointer to it. The specification of the result depends on
// the type:
//	Slice: The size specifies the length. The capacity of the slice is
//	equal to its length. A second integer argument may be provided to
//	specify a different capacity; it must be no smaller than the
//	length. For example, make([]int, 0, 10) allocates an underlying array
//	of size 10 and returns a slice of length 0 and capacity 10 that is
//	backed by this underlying array.
//	Map: An empty map is allocated with enough space to hold the
//	specified number of elements. The size may be omitted, in which case
//	a small starting size is allocated.
//	Channel: The channel's buffer is initialized with the specified
//	buffer capacity. If zero, or the size is omitted, the channel is
//	unbuffered.
func make(t Type, size ...IntegerType) Type

 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

func makeslice(et *_type, len, cap int) unsafe.Pointer {
    // 1）判断et.size * uintptr(cap)是否造成内存溢出
    mem, overflow := math.MulUintptr(et.size, uintptr(cap)) // 按照cap计算的
    //  1. 【overflow == true】：溢出
    //  2. 【mem > maxAlloc】：超过操作系统最大内存
    //  3. 【len < 0】：错误的len参数
    //  4. 【len > cap】：长度大于容量
    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.
        // 
        // 当有人 make([]T, bignumber) 时，产生一个 'len out of range' 错误而不是 'cap out of range' 错误提示
        // 当 'cap out of range' 也是太长了，由于cap只是隐式地提供，所以说len更清楚的提示。
        mem, overflow := math.MulUintptr(et.size, uintptr(len))	// 根据len计算
        if overflow || mem > maxAlloc || len < 0 {
            panicmakeslicelen() // painc 'len out of range'
        }
        panicmakeslicecap() // panic 'cap out of range'
    }

    // 2）向操作系统申请mem大小的内存块，返回申请到内存块的首地址
    return mallocgc(mem, et, true)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {
    len := int(len64) // 32位系统下转换会丢失部分数据
    if int64(len) != len64 {
        panicmakeslicelen() // painc 'len out of range'
    }

    cap := int(cap64)
    if int64(cap) != cap64 {
        panicmakeslicecap() // panic 'cap out of range'
    }

    return makeslice(et, len, cap)
}

1
2
3
4

// 伪代码示例
func len(array []T) int {
    return array.len   
}

1
2
3
4

// 伪代码示例
func cap(array []T) int {
    return array.cap
}

1
2
3
4
5
6

// The copy built-in function copies elements from a source slice into a
// destination slice. (As a special case, it also will copy bytes from a
// string to a slice of bytes.) The source and destination may overlap. Copy
// returns the number of elements copied, which will be the minimum of
// len(src) and len(dst).
func copy(dst, src []Type) int

 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

// 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 {
    // 1) 拷贝或被拷贝长度为0直接返回
    if fromLen == 0 || toLen == 0 {
        return 0
    }

    // 2) 拷贝元素的个数取决于拷贝或被拷贝的最小长度
    n := fromLen
    if toLen < n {
        n = toLen
    }

    // 3) 拷贝的元素大小为0，直接返回n
    if width == 0 {	// []struct{}
        return n
    }

    // 4) size 需要拷贝的总内存大小/字节。
    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)
    }

    // 一般情况下，这里的值大约是2x（只有1字节需要拷贝）
    // 	to := make([]byte, 1); copy(to, "hello")
    // 【[]byte】 OR 【[]uint8】 OR 【[]int8】 OR 【[]bool】
    if size == 1 { // common case worth about 2x to do here
        // TODO: is this still worth it with new memmove impl?
        // 
        // TODO: 使用新的memmove impl，这仍然值得吗?
        // 已知fromPtr和toPtr是 byte 指针
        *(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
    } else {
        memmove(toPtr, fromPtr, size)   // 拷贝数据
    }
    return n
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// memmove copies n bytes from "from" to "to".
//
// memmove ensures that any pointer in "from" is written to "to" with
// an indivisible write, so that racy reads cannot observe a
// half-written pointer. This is necessary to prevent the garbage
// collector from observing invalid pointers, and differs from memmove
// in unmanaged languages. However, memmove is only required to do
// this if "from" and "to" may contain pointers, which can only be the
// case if "from", "to", and "n" are all be word-aligned.
//
// Implementations are in memmove_*.s.
//
//go:noescape
func memmove(to, from unsafe.Pointer, n uintptr)

 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

TEXT runtime·memmove<ABIInternal>(SB), NOSPLIT, $0-24
    // AX = to
    // BX = from
    // CX = n
    MOVQ    AX, DI
    MOVQ    BX, SI
    MOVQ    CX, BX
    
tail:
    // TEST指令用于对BX寄存器的内容和自身进行按位与操作，但是不改变寄存器的内容。
    TESTQ   BX, BX # 检查BX是否为0
    // 检查上一条指令（TEST）执行后是否设置了零标志（ZF）
    JEQ move_0  # Jump if Equal
    // 这是一个比较指令，用于比较BX寄存器中的值和立即数2。
    // 具体来说，它会将BX寄存器的值和2相减，但不改变任何寄存器的值，只是根据结果设置状态标志。
    CMPQ    BX, $2
    // BX <= 2 成立
    JBE move_1or2 # Jump if Below or Equal
    CMPQ    BX, $4 # <= 4
    JB  move_3
    JBE move_4
    CMPQ    BX, $8 # <= 8
    JB  move_5through7
    JE  move_8
    CMPQ    BX, $16
    JBE move_9through16
    CMPQ    BX, $32
    JBE move_17through32
    CMPQ    BX, $64
    JBE move_33through64
    CMPQ    BX, $128
    JBE move_65through128
    CMPQ    BX, $256
    JBE move_129through256

    TESTB   $1, runtime·useAVXmemmove(SB)
    JNZ avxUnaligned
    
    //... ...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// The append built-in function appends elements to the end of a slice. If
// it has sufficient capacity, the destination is resliced to accommodate the
// new elements. If it does not, a new underlying array will be allocated.
// Append returns the updated slice. It is therefore necessary to store the
// result of append, often in the variable holding the slice itself:
//
//	slice = append(slice, elem1, elem2)
//	slice = append(slice, anotherSlice...)
//
// As a special case, it is legal to append a string to a byte slice, like this:
//
//	slice = append([]byte("hello "), "world"...)
func append(slice []Type, elems ...Type) []Type

  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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

// 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 {
    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)))
    }

    // 1) 切片长度溢出判断
    if cap < old.cap {
        panic(errorString("growslice: cap out of range"))
    }

    // 2) 切片元素类型 占用内存为零 情况
    // 这种情况出现在：
    //      var s []struct{}
    //      s = append(s, struct{}{}, struct{}{})
    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.
        //
        // Append不应该创建一个指针为nil的切片，而是一个len为non-zero的切片。
        // 在这种情况下，我们假设append不需要保存old.array。
        // 赋值slice.array指定地址，为了确保slice不是nil
        // slice为nil的判断条件是，只要slice.array==0x00,不管len和cap的值为多少都为nil
        return slice{unsafe.Pointer(&zerobase), old.len, cap}
    }

    // 3) 评估扩容后的容量
    // ---+-------+-----------------------------------------------------------------------------------
    // 预 |   if  | oldCap * 2 < cap ------> newCap = cap               使用cap值
    // 估 |-------+-----------------------------------------------------------------------------------
    // 规 |  else | oldCap < 256     ------> newCap = oldCap * 2        翻倍扩容
    // 则 |       | oldCap >= 256    ------> newCap = oldCap * 5/4 + 256 * 3/4 在原容量上扩容1/4在扩容192
    // ---+-------+-----------------------------------------------------------------------------------
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        // 2倍旧容量 < cap时，则按照cap算。
        newcap = cap
    } else {
        const threshold = 256
        if old.cap < threshold {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            //
            // 检查 0 < newcap 以检测溢出并防止无限循环。
            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
            }
        }
    }

    // 4) 内存规格匹配
    
    // 内存是否溢出 true.溢出 false.没有溢出
    var overflow bool	
    // lenmem 旧切片元素占用的内存大小
    //      该值用于迁移旧数据的依据/字节
    // newlenmem 翻倍后切片元素占用的内存大小
    //      该值是当前扩容后实际占用的大小/字节
    //      因此capmem-newlenmem这部分内存是多余的，不会被用到。
    // capmem 翻倍后新容量占用的内存大小，
    //      用于向操作系统申请的内存大小/字节
    //      这部分内存可能大于newlenmem的值，因为Go的内存申请是有规格的。
    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.
    //
    // 专门用于 et.size 的共同值。
    // 对于1，我们不需要任何除法/乘法
    // 对于 goarch.PtrSize，编译器将除法/乘法 优化为一个常量的位移
    // 对于2的幂次方，使用可变位移
    switch {
        // 倘若数组元素的大小为 1，则新容量大小为 1 * newcap.
        // 同时会针对 span class 进行取整
    case et.size == 1:  // 1字节
        lenmem = uintptr(old.len)
        newlenmem = uintptr(cap)
        capmem = roundupsize(uintptr(newcap))   // 匹配最近接的内存块规格
        overflow = uintptr(newcap) > maxAlloc   // 是否内存溢出
        newcap = int(capmem)                    // 从新调整翻倍后新容量
        // 倘若数组元素为指针类型，则根据指针占用空间结合元素个数计算空间大小
        // 并会针对 span class 进行取整
    case et.size == goarch.PtrSize: // 4或8字节
        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)
        // 倘若元素大小为 2 的指数，则直接通过位运算进行空间大小的计算  
    case isPowerOfTwo(et.size): // 2的幂次方
        var shift uintptr
        if goarch.PtrSize == 8 {
            // Mask shift for better code generation.
            //
            // 掩码移位以更好地生成代码。
            // sys.Ctz64函数计数尾部(低阶)零，如果全部为零，则为64。
            // 比如 et.size 是2^8也就是 1_0000_0000，也就是8个零
            shift = uintptr(sys.Ctz64(uint64(et.size))) & 63    // 64位
        } else {
            shift = uintptr(sys.Ctz32(uint32(et.size))) & 31    // 32位
        }
        lenmem = uintptr(old.len) << shift
        newlenmem = uintptr(cap) << shift
        capmem = roundupsize(uintptr(newcap) << shift)
        overflow = uintptr(newcap) > (maxAlloc >> shift)
        newcap = int(capmem >> shift)
        // 兜底分支：根据元素大小乘以元素个数
        // 再针对 span class 进行取整     
    default:
        lenmem = uintptr(old.len) * et.size
        newlenmem = uintptr(cap) * et.size
        // math.MulUintptr 返回 capmem = et.size * uintptr(newcap); overflow 是否溢出
        capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
        capmem = roundupsize(capmem)
        newcap = int(capmem / et.size)
    }
    // 以上代码因为会去匹配内存规格，所以会从新计算newcap这个翻倍后的值

    // 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:
    //
    // 除了capmem > maxAlloc之外，还需要检查溢出，以防止溢出，
    // 该溢出可用于在32位体系结构上触发段故障，示例程序如下:
    //
    // 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")
    // }
    // 4*(1<<27 + 1)*8
    if overflow || capmem > maxAlloc {
        panic(errorString("growslice: cap out of range"))
    }

    // 申请到的内存首地址
    var p unsafe.Pointer
    if et.ptrdata == 0 { // 切片元素类型不包含指针
        // capmem 申请的内存; nil 类型元类型用于判断是否为指针类型; false 是否重置内存为零值;
        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.
        //
        // 调用 growslice 的 append() 方法会将 old.len 覆盖到 cap(这将是新的长度)。
        // 只清除不会被覆盖的部分。
        // 清零capmem-newlenmem这块内存，这快内存是多余的，不会被用到。
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)	
    } else { // 切片元素类型包含指针
        // Note: can't use rawmem (which avoids zeroing of memory), 
        // because then GC can scan uninitialized memory.
        // 
        // Note: 不能使用rawmem(它可以避免内存归零)，因为这样GC会扫描未初始化的内存。
        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.
            //
            // 在 old.array 中只对指针进行 shade 处理，因为我们知道目标切片 p 只包含nil指针，
            // 因为它在alloc期间已被清除。
            // lenmem-et.size+et.ptrdata 刚好是old.array存在的都是指针
            //      -et.size：减去最后一个元素的内存
            //      +et.ptrdata：再加上最后一个元素的指针
            // 刚好处理完最后一个元素后面不是指针的部分内存。
            // [dst, dst+size]
            bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)	
        }
    }
    // 从old.array中迁移lenmem大小内存数据到p中
    memmove(p, old.array, lenmem)

    // 注意：这里返回的是 old.len，因为此时还是之前的旧数据
    return slice{p, old.len, newcap}
}

 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

// bulkBarrierPreWriteSrcOnly is like bulkBarrierPreWrite but
// does not execute write barriers for [dst, dst+size).
//
// In addition to the requirements of bulkBarrierPreWrite
// callers need to ensure [dst, dst+size) is zeroed.
//
// This is used for special cases where e.g. dst was just
// created and zeroed with malloc.
//
// The type of the space can be provided purely as an optimization,
// however it is not used with GOEXPERIMENT=noallocheaders.
//
//go:nosplit
func bulkBarrierPreWriteSrcOnly(dst, src, size uintptr, _ *abi.Type) {
    // GC并发标记阶段，这里需要处理混合写屏障相关事项，因为在拷贝指针数据
    if (dst|src|size)&(goarch.PtrSize-1) != 0 {
        throw("bulkBarrierPreWrite: unaligned arguments")
    }
    if !writeBarrier.enabled {
        return // 并发标记已结束
    }
    buf := &getg().m.p.ptr().wbBuf // 写屏障缓冲区
    h := heapBitsForAddr(dst, size)
    for {
        var addr uintptr
        if h, addr = h.next(); addr == 0 {
            break
        }
        srcx := (*uintptr)(unsafe.Pointer(addr - dst + src))
        p := buf.get1()
        p[0] = *srcx
    }
}

1
2

// base address for all 0-byte allocations
var zerobase uintptr

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

// Returns size of the memory block that mallocgc will allocate if you ask for the size.
func roundupsize(size uintptr) uintptr {
    // _MaxSmallSize = 32768
    if size < _MaxSmallSize {
        // smallSizeMax = 1024
        if size <= smallSizeMax-8 { // 以最下8B倍数对齐
            // smallSizeDiv = 8，divRoundUp 等价于 ceil(size/8)
            // size_to_class8和class_to_size 记录着 size 的映射关系
            return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
        } else {    // 以最小128B倍数对齐
            // largeSizeDiv = 128
            return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
        }
    }
    // _PageSize = 8192
    if size+_PageSize < size {
        return size
    }
    return alignUp(size, _PageSize) // 对齐8KB
}

1
2
3
4

// alignUp rounds n up to a multiple of a. a must be a power of 2.
func alignUp(n, a uintptr) uintptr {
    return (n + a - 1) &^ (a - 1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// MulUintptr returns a * b and whether the multiplication overflowed.
// On supported platforms this is an intrinsic lowered by the compiler.
func MulUintptr(a, b uintptr) (uintptr, bool) {
    // a|b < 1<<16 || a|b < 1<<32
    if a|b < 1<<(4*goarch.PtrSize) || a == 0 {
        return a * b, false
    }
    // const MaxUintptr = ^uintptr(0)
    overflow := b > MaxUintptr/a
    return a * b, overflow
}