1 // Copyright 2018 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 // Garbage collector: stack objects and stack tracing 6 // See the design doc at https://docs.google.com/document/d/1un-Jn47yByHL7I0aVIP_uVCMxjdM5mpelJhiKlIqxkE/edit?usp=sharing 7 // Also see issue 22350. 8 9 // Stack tracing solves the problem of determining which parts of the 10 // stack are live and should be scanned. It runs as part of scanning 11 // a single goroutine stack. 12 // 13 // Normally determining which parts of the stack are live is easy to 14 // do statically, as user code has explicit references (reads and 15 // writes) to stack variables. The compiler can do a simple dataflow 16 // analysis to determine liveness of stack variables at every point in 17 // the code. See cmd/compile/internal/gc/plive.go for that analysis. 18 // 19 // However, when we take the address of a stack variable, determining 20 // whether that variable is still live is less clear. We can still 21 // look for static accesses, but accesses through a pointer to the 22 // variable are difficult in general to track statically. That pointer 23 // can be passed among functions on the stack, conditionally retained, 24 // etc. 25 // 26 // Instead, we will track pointers to stack variables dynamically. 27 // All pointers to stack-allocated variables will themselves be on the 28 // stack somewhere (or in associated locations, like defer records), so 29 // we can find them all efficiently. 30 // 31 // Stack tracing is organized as a mini garbage collection tracing 32 // pass. The objects in this garbage collection are all the variables 33 // on the stack whose address is taken, and which themselves contain a 34 // pointer. We call these variables "stack objects". 35 // 36 // We begin by determining all the stack objects on the stack and all 37 // the statically live pointers that may point into the stack. We then 38 // process each pointer to see if it points to a stack object. If it 39 // does, we scan that stack object. It may contain pointers into the 40 // heap, in which case those pointers are passed to the main garbage 41 // collection. It may also contain pointers into the stack, in which 42 // case we add them to our set of stack pointers. 43 // 44 // Once we're done processing all the pointers (including the ones we 45 // added during processing), we've found all the stack objects that 46 // are live. Any dead stack objects are not scanned and their contents 47 // will not keep heap objects live. Unlike the main garbage 48 // collection, we can't sweep the dead stack objects; they live on in 49 // a moribund state until the stack frame that contains them is 50 // popped. 51 // 52 // A stack can look like this: 53 // 54 // +----------+ 55 // | foo() | 56 // | +------+ | 57 // | | A | | <---\ 58 // | +------+ | | 59 // | | | 60 // | +------+ | | 61 // | | B | | | 62 // | +------+ | | 63 // | | | 64 // +----------+ | 65 // | bar() | | 66 // | +------+ | | 67 // | | C | | <-\ | 68 // | +----|-+ | | | 69 // | | | | | 70 // | +----v-+ | | | 71 // | | D ---------/ 72 // | +------+ | | 73 // | | | 74 // +----------+ | 75 // | baz() | | 76 // | +------+ | | 77 // | | E -------/ 78 // | +------+ | 79 // | ^ | 80 // | F: --/ | 81 // | | 82 // +----------+ 83 // 84 // foo() calls bar() calls baz(). Each has a frame on the stack. 85 // foo() has stack objects A and B. 86 // bar() has stack objects C and D, with C pointing to D and D pointing to A. 87 // baz() has a stack object E pointing to C, and a local variable F pointing to E. 88 // 89 // Starting from the pointer in local variable F, we will eventually 90 // scan all of E, C, D, and A (in that order). B is never scanned 91 // because there is no live pointer to it. If B is also statically 92 // dead (meaning that foo() never accesses B again after it calls 93 // bar()), then B's pointers into the heap are not considered live. 94 95 package runtime 96 97 import ( 98 "runtime/internal/sys" 99 "unsafe" 100 ) 101 102 const stackTraceDebug = false 103 104 // Buffer for pointers found during stack tracing. 105 // Must be smaller than or equal to workbuf. 106 // 107 //go:notinheap 108 type stackWorkBuf struct { 109 stackWorkBufHdr 110 obj [(_WorkbufSize - unsafe.Sizeof(stackWorkBufHdr{})) / sys.PtrSize]uintptr 111 } 112 113 // Header declaration must come after the buf declaration above, because of issue #14620. 114 // 115 //go:notinheap 116 type stackWorkBufHdr struct { 117 workbufhdr 118 next *stackWorkBuf // linked list of workbufs 119 // Note: we could theoretically repurpose lfnode.next as this next pointer. 120 // It would save 1 word, but that probably isn't worth busting open 121 // the lfnode API. 122 } 123 124 // Buffer for stack objects found on a goroutine stack. 125 // Must be smaller than or equal to workbuf. 126 // 127 //go:notinheap 128 type stackObjectBuf struct { 129 stackObjectBufHdr 130 obj [(_WorkbufSize - unsafe.Sizeof(stackObjectBufHdr{})) / unsafe.Sizeof(stackObject{})]stackObject 131 } 132 133 //go:notinheap 134 type stackObjectBufHdr struct { 135 workbufhdr 136 next *stackObjectBuf 137 } 138 139 func init() { 140 if unsafe.Sizeof(stackWorkBuf{}) > unsafe.Sizeof(workbuf{}) { 141 panic("stackWorkBuf too big") 142 } 143 if unsafe.Sizeof(stackObjectBuf{}) > unsafe.Sizeof(workbuf{}) { 144 panic("stackObjectBuf too big") 145 } 146 } 147 148 // A stackObject represents a variable on the stack that has had 149 // its address taken. 150 // 151 //go:notinheap 152 type stackObject struct { 153 off uint32 // offset above stack.lo 154 size uint32 // size of object 155 typ *_type // type info (for ptr/nonptr bits). nil if object has been scanned. 156 left *stackObject // objects with lower addresses 157 right *stackObject // objects with higher addresses 158 } 159 160 // obj.typ = typ, but with no write barrier. 161 //go:nowritebarrier 162 func (obj *stackObject) setType(typ *_type) { 163 // Types of stack objects are always in read-only memory, not the heap. 164 // So not using a write barrier is ok. 165 *(*uintptr)(unsafe.Pointer(&obj.typ)) = uintptr(unsafe.Pointer(typ)) 166 } 167 168 // A stackScanState keeps track of the state used during the GC walk 169 // of a goroutine. 170 // 171 //go:notinheap 172 type stackScanState struct { 173 cache pcvalueCache 174 175 // stack limits 176 stack stack 177 178 // buf contains the set of possible pointers to stack objects. 179 // Organized as a LIFO linked list of buffers. 180 // All buffers except possibly the head buffer are full. 181 buf *stackWorkBuf 182 freeBuf *stackWorkBuf // keep around one free buffer for allocation hysteresis 183 184 // list of stack objects 185 // Objects are in increasing address order. 186 head *stackObjectBuf 187 tail *stackObjectBuf 188 nobjs int 189 190 // root of binary tree for fast object lookup by address 191 // Initialized by buildIndex. 192 root *stackObject 193 } 194 195 // Add p as a potential pointer to a stack object. 196 // p must be a stack address. 197 func (s *stackScanState) putPtr(p uintptr) { 198 if p < s.stack.lo || p >= s.stack.hi { 199 throw("address not a stack address") 200 } 201 buf := s.buf 202 if buf == nil { 203 // Initial setup. 204 buf = (*stackWorkBuf)(unsafe.Pointer(getempty())) 205 buf.nobj = 0 206 buf.next = nil 207 s.buf = buf 208 } else if buf.nobj == len(buf.obj) { 209 if s.freeBuf != nil { 210 buf = s.freeBuf 211 s.freeBuf = nil 212 } else { 213 buf = (*stackWorkBuf)(unsafe.Pointer(getempty())) 214 } 215 buf.nobj = 0 216 buf.next = s.buf 217 s.buf = buf 218 } 219 buf.obj[buf.nobj] = p 220 buf.nobj++ 221 } 222 223 // Remove and return a potential pointer to a stack object. 224 // Returns 0 if there are no more pointers available. 225 func (s *stackScanState) getPtr() uintptr { 226 buf := s.buf 227 if buf == nil { 228 // Never had any data. 229 return 0 230 } 231 if buf.nobj == 0 { 232 if s.freeBuf != nil { 233 // Free old freeBuf. 234 putempty((*workbuf)(unsafe.Pointer(s.freeBuf))) 235 } 236 // Move buf to the freeBuf. 237 s.freeBuf = buf 238 buf = buf.next 239 s.buf = buf 240 if buf == nil { 241 // No more data. 242 putempty((*workbuf)(unsafe.Pointer(s.freeBuf))) 243 s.freeBuf = nil 244 return 0 245 } 246 } 247 buf.nobj-- 248 return buf.obj[buf.nobj] 249 } 250 251 // addObject adds a stack object at addr of type typ to the set of stack objects. 252 func (s *stackScanState) addObject(addr uintptr, typ *_type) { 253 x := s.tail 254 if x == nil { 255 // initial setup 256 x = (*stackObjectBuf)(unsafe.Pointer(getempty())) 257 x.next = nil 258 s.head = x 259 s.tail = x 260 } 261 if x.nobj > 0 && uint32(addr-s.stack.lo) < x.obj[x.nobj-1].off+x.obj[x.nobj-1].size { 262 throw("objects added out of order or overlapping") 263 } 264 if x.nobj == len(x.obj) { 265 // full buffer - allocate a new buffer, add to end of linked list 266 y := (*stackObjectBuf)(unsafe.Pointer(getempty())) 267 y.next = nil 268 x.next = y 269 s.tail = y 270 x = y 271 } 272 obj := &x.obj[x.nobj] 273 x.nobj++ 274 obj.off = uint32(addr - s.stack.lo) 275 obj.size = uint32(typ.size) 276 obj.setType(typ) 277 // obj.left and obj.right will be initialized by buildIndex before use. 278 s.nobjs++ 279 } 280 281 // buildIndex initializes s.root to a binary search tree. 282 // It should be called after all addObject calls but before 283 // any call of findObject. 284 func (s *stackScanState) buildIndex() { 285 s.root, _, _ = binarySearchTree(s.head, 0, s.nobjs) 286 } 287 288 // Build a binary search tree with the n objects in the list 289 // x.obj[idx], x.obj[idx+1], ..., x.next.obj[0], ... 290 // Returns the root of that tree, and the buf+idx of the nth object after x.obj[idx]. 291 // (The first object that was not included in the binary search tree.) 292 // If n == 0, returns nil, x. 293 func binarySearchTree(x *stackObjectBuf, idx int, n int) (root *stackObject, restBuf *stackObjectBuf, restIdx int) { 294 if n == 0 { 295 return nil, x, idx 296 } 297 var left, right *stackObject 298 left, x, idx = binarySearchTree(x, idx, n/2) 299 root = &x.obj[idx] 300 idx++ 301 if idx == len(x.obj) { 302 x = x.next 303 idx = 0 304 } 305 right, x, idx = binarySearchTree(x, idx, n-n/2-1) 306 root.left = left 307 root.right = right 308 return root, x, idx 309 } 310 311 // findObject returns the stack object containing address a, if any. 312 // Must have called buildIndex previously. 313 func (s *stackScanState) findObject(a uintptr) *stackObject { 314 off := uint32(a - s.stack.lo) 315 obj := s.root 316 for { 317 if obj == nil { 318 return nil 319 } 320 if off < obj.off { 321 obj = obj.left 322 continue 323 } 324 if off >= obj.off+obj.size { 325 obj = obj.right 326 continue 327 } 328 return obj 329 } 330 } 331