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
|
//go:build gc.precise
// This implements the block-based GC as a partially precise GC. This means that
// for most heap allocations it is known which words contain a pointer and which
// don't. This should in theory make the GC faster (because it can skip
// non-pointer object) and have fewer false positives in a GC cycle. It does
// however use a bit more RAM to store the layout of each object.
//
// The pointer/non-pointer information for objects is stored in the first word
// of the object. It is described below but in essence it contains a bitstring
// of a particular size. This size does not indicate the size of the object:
// instead the allocated object is a multiple of the bitstring size. This is so
// that arrays and slices can store the size of the object efficiently. The
// bitstring indicates where the pointers are in the object (the bit is set when
// the value may be a pointer, and cleared when it certainly isn't a pointer).
// Some examples (assuming a 32-bit system for the moment):
//
// | object type | size | bitstring | note
// |-------------|------|-----------|------
// | int | 1 | 0 | no pointers in this object
// | string | 2 | 01 | {pointer, len} pair so there is one pointer
// | []int | 3 | 001 | {pointer, len, cap}
// | [4]*int | 1 | 1 | even though it contains 4 pointers, an array repeats so it can be stored with size=1
// | [30]byte | 1 | 0 | there are no pointers so the layout is very simple
//
// The garbage collector scans objects by starting at the first word value in
// the object. If the least significant bit of the bitstring is clear, it is
// skipped (it's not a pointer). If the bit is set, it is treated as if it could
// be a pointer. The garbage collector continues by scanning further words in
// the object and checking them against the corresponding bit in the bitstring.
// Once it reaches the end of the bitstring, it wraps around (for arrays,
// slices, strings, etc).
//
// The layout as passed to the runtime.alloc function and stored in the object
// is a pointer-sized value. If the least significant bit of the value is set,
// the bitstring is contained directly inside the value, of the form
// pppp_pppp_ppps_sss1.
// * The 'p' bits indicate which parts of the object are a pointer.
// * The 's' bits indicate the size of the object. In this case, there are 11
// pointer bits so four bits are enough for the size (0-15).
// * The lowest bit is always set to distinguish this value from a pointer.
// This example is for a 16-bit architecture. For example, 32-bit architectures
// use a layout format of pppppppp_pppppppp_pppppppp_ppsssss1 (26 bits for
// pointer/non-pointer information, 5 size bits, and one bit that's always set).
//
// For larger objects that don't fit in an uintptr, the layout value is a
// pointer to a global with a format as follows:
// struct {
// size uintptr
// bits [...]uint8
// }
// The 'size' field is the number of bits in the bitstring. The 'bits' field is
// a byte array that contains the bitstring itself, in little endian form. The
// length of the bits array is ceil(size/8).
package runtime
import "unsafe"
const preciseHeap = true
type gcObjectScanner struct {
index uintptr
size uintptr
bitmap uintptr
bitmapAddr unsafe.Pointer
}
func newGCObjectScanner(block gcBlock) gcObjectScanner {
if gcAsserts && block != block.findHead() {
runtimePanic("gc: object scanner must start at head")
}
scanner := gcObjectScanner{}
layout := *(*uintptr)(unsafe.Pointer(block.address()))
if layout == 0 {
// Unknown layout. Assume all words in the object could be pointers.
// This layout value below corresponds to a slice of pointers like:
// make(*byte, N)
scanner.size = 1
scanner.bitmap = 1
} else if layout&1 != 0 {
// Layout is stored directly in the integer value.
// Determine format of bitfields in the integer.
const layoutBits = uint64(unsafe.Sizeof(layout) * 8)
var sizeFieldBits uint64
switch layoutBits { // note: this switch should be resolved at compile time
case 16:
sizeFieldBits = 4
case 32:
sizeFieldBits = 5
case 64:
sizeFieldBits = 6
default:
runtimePanic("unknown pointer size")
}
// Extract values from the bitfields.
// See comment at the top of this file for more information.
scanner.size = (layout >> 1) & (1<<sizeFieldBits - 1)
scanner.bitmap = layout >> (1 + sizeFieldBits)
} else {
// Layout is stored separately in a global object.
layoutAddr := unsafe.Pointer(layout)
scanner.size = *(*uintptr)(layoutAddr)
scanner.bitmapAddr = unsafe.Add(layoutAddr, unsafe.Sizeof(uintptr(0)))
}
return scanner
}
func (scanner *gcObjectScanner) pointerFree() bool {
if scanner.bitmapAddr != nil {
// While the format allows for large objects without pointers, this is
// optimized by the compiler so if bitmapAddr is set, we know that there
// are at least some pointers in the object.
return false
}
// If the bitmap is zero, there are definitely no pointers in the object.
return scanner.bitmap == 0
}
func (scanner *gcObjectScanner) nextIsPointer(word, parent, addrOfWord uintptr) bool {
index := scanner.index
scanner.index++
if scanner.index == scanner.size {
scanner.index = 0
}
if !isOnHeap(word) {
// Definitely isn't a pointer.
return false
}
// Might be a pointer. Now look at the object layout to know for sure.
if scanner.bitmapAddr != nil {
if (*(*uint8)(unsafe.Add(scanner.bitmapAddr, index/8))>>(index%8))&1 == 0 {
return false
}
return true
}
if (scanner.bitmap>>index)&1 == 0 {
// not a pointer!
return false
}
// Probably a pointer.
return true
}
|
