1 //go:build gc.precise
2 3 // This implements the block-based GC as a partially precise GC. This means that
4 // for most heap allocations it is known which words contain a pointer and which
5 // don't. This should in theory make the GC faster (because it can skip
6 // non-pointer object) and have fewer false positives in a GC cycle. It does
7 // however use a bit more RAM to store the layout of each object.
8 //
9 // The pointer/non-pointer information for objects is stored in the first word
10 // of the object. It is described below but in essence it contains a bitstring
11 // of a particular size. This size does not indicate the size of the object:
12 // instead the allocated object is a multiple of the bitstring size. This is so
13 // that arrays and slices can store the size of the object efficiently. The
14 // bitstring indicates where the pointers are in the object (the bit is set when
15 // the value may be a pointer, and cleared when it certainly isn't a pointer).
16 // Some examples (assuming a 32-bit system for the moment):
17 //
18 // | object type | size | bitstring | note
19 // |-------------|------|-----------|------
20 // | int | 1 | 0 | no pointers in this object
21 // | string | 2 | 01 | {pointer, len} pair so there is one pointer
22 // | []int | 3 | 001 | {pointer, len, cap}
23 // | [4]*int | 1 | 1 | even though it contains 4 pointers, an array repeats so it can be stored with size=1
24 // | [30]byte | 1 | 0 | there are no pointers so the layout is very simple
25 //
26 // The garbage collector scans objects by starting at the first word value in
27 // the object. If the least significant bit of the bitstring is clear, it is
28 // skipped (it's not a pointer). If the bit is set, it is treated as if it could
29 // be a pointer. The garbage collector continues by scanning further words in
30 // the object and checking them against the corresponding bit in the bitstring.
31 // Once it reaches the end of the bitstring, it wraps around (for arrays,
32 // slices, strings, etc).
33 //
34 // The layout as passed to the runtime.alloc function and stored in the object
35 // is a pointer-sized value. If the least significant bit of the value is set,
36 // the bitstring is contained directly inside the value, of the form
37 // pppp_pppp_ppps_sss1.
38 // * The 'p' bits indicate which parts of the object are a pointer.
39 // * The 's' bits indicate the size of the object. In this case, there are 11
40 // pointer bits so four bits are enough for the size (0-15).
41 // * The lowest bit is always set to distinguish this value from a pointer.
42 // This example is for a 16-bit architecture. For example, 32-bit architectures
43 // use a layout format of pppppppp_pppppppp_pppppppp_ppsssss1 (26 bits for
44 // pointer/non-pointer information, 5 size bits, and one bit that's always set).
45 //
46 // For larger objects that don't fit in an uintptr, the layout value is a
47 // pointer to a global with a format as follows:
48 // struct {
49 // size uintptr
50 // bits [...]uint8
51 // }
52 // The 'size' field is the number of bits in the bitstring. The 'bits' field is
53 // a byte array that contains the bitstring itself, in little endian form. The
54 // length of the bits array is ceil(size/8).
55 56 package runtime
57 58 import "unsafe"
59 60 const sizeFieldBits = 4 + (unsafe.Sizeof(uintptr(0)) / 4)
61 62 // parseGCLayout stores the layout information passed to alloc into a gcLayout value.
63 func parseGCLayout(layout unsafe.Pointer) gcLayout {
64 return gcLayout(layout)
65 }
66 67 // gcLayout tracks pointer locations in a heap object.
68 type gcLayout uintptr
69 70 func (layout gcLayout) pointerFree() bool {
71 return layout&1 != 0 && layout>>(sizeFieldBits+1) == 0
72 }
73 74 // scan an object with this element layout.
75 // The starting address must be valid and pointer-aligned.
76 // The length is rounded down to a multiple of the element size.
77 func (layout gcLayout) scan(start, len uintptr) {
78 switch {
79 case layout == 0:
80 // This is an unknown layout.
81 // Scan conservatively.
82 // NOTE: This is *NOT* equivalent to a slice of pointers on AVR.
83 scanConservative(start, len)
84 85 case layout&1 != 0:
86 // The layout is stored directly in the integer value.
87 // Extract the bitfields.
88 size := uintptr(layout>>1) & (1<<sizeFieldBits - 1)
89 mask := uintptr(layout) >> (1 + sizeFieldBits)
90 91 // Scan with the extracted mask.
92 scanSimple(start, len, size*unsafe.Alignof(start), mask)
93 94 default:
95 // The layout is stored seperately in a global object.
96 // Extract the size and bitmap.
97 layoutAddr := unsafe.Pointer(layout)
98 size := *(*uintptr)(layoutAddr)
99 bitmapPtr := unsafe.Add(layoutAddr, unsafe.Sizeof(uintptr(0)))
100 bitmapLen := (size + 7) / 8
101 bitmap := unsafe.Slice((*byte)(bitmapPtr), bitmapLen)
102 103 // Scan with the bitmap.
104 scanComplex(start, len, size*unsafe.Alignof(start), bitmap)
105 }
106 }
107 108 // scanSimple scans an object with an integer bitmask of pointer locations.
109 // The starting address must be valid and pointer-aligned.
110 func scanSimple(start, len, size, mask uintptr) {
111 for len >= size {
112 // Scan this element.
113 scanWithMask(start, mask)
114 115 // Move to the next element.
116 start += size
117 len -= size
118 }
119 }
120 121 // scanComplex scans an object with a bitmap of pointer locations.
122 // The starting address must be valid and pointer-aligned.
123 func scanComplex(start, len, size uintptr, bitmap []byte) {
124 for len >= size {
125 // Scan this element.
126 for i, mask := range bitmap {
127 addr := start + 8*unsafe.Alignof(start)*uintptr(i)
128 scanWithMask(addr, uintptr(mask))
129 }
130 131 // Move to the next element.
132 start += size
133 len -= size
134 }
135 }
136 137 // scanWithMask scans a portion of an object with a mask of pointer locations.
138 // The address must be valid and pointer-aligned.
139 func scanWithMask(addr, mask uintptr) {
140 // TODO: use ctz when available
141 for mask != 0 {
142 if mask&1 != 0 {
143 // Load and mark this pointer.
144 root := *(*uintptr)(unsafe.Pointer(addr))
145 markRoot(addr, root)
146 }
147 148 // Move to the next offset.
149 mask >>= 1
150 addr += unsafe.Alignof(addr)
151 }
152 }
153