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 r *stackObjectRecord // info of the object (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.r = r, but with no write barrier. 161 //go:nowritebarrier 162 func (obj *stackObject) setRecord(r *stackObjectRecord) { 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.r)) = uintptr(unsafe.Pointer(r)) 166 } 167 168 // A stackScanState keeps track of the state used during the GC walk 169 // of a goroutine. 170 type stackScanState struct { 171 cache pcvalueCache 172 173 // stack limits 174 stack stack 175 176 // conservative indicates that the next frame must be scanned conservatively. 177 // This applies only to the innermost frame at an async safe-point. 178 conservative bool 179 180 // buf contains the set of possible pointers to stack objects. 181 // Organized as a LIFO linked list of buffers. 182 // All buffers except possibly the head buffer are full. 183 buf *stackWorkBuf 184 freeBuf *stackWorkBuf // keep around one free buffer for allocation hysteresis 185 186 // cbuf contains conservative pointers to stack objects. If 187 // all pointers to a stack object are obtained via 188 // conservative scanning, then the stack object may be dead 189 // and may contain dead pointers, so it must be scanned 190 // defensively. 191 cbuf *stackWorkBuf 192 193 // list of stack objects 194 // Objects are in increasing address order. 195 head *stackObjectBuf 196 tail *stackObjectBuf 197 nobjs int 198 199 // root of binary tree for fast object lookup by address 200 // Initialized by buildIndex. 201 root *stackObject 202 } 203 204 // Add p as a potential pointer to a stack object. 205 // p must be a stack address. 206 func (s *stackScanState) putPtr(p uintptr, conservative bool) { 207 if p < s.stack.lo || p >= s.stack.hi { 208 throw("address not a stack address") 209 } 210 head := &s.buf 211 if conservative { 212 head = &s.cbuf 213 } 214 buf := *head 215 if buf == nil { 216 // Initial setup. 217 buf = (*stackWorkBuf)(unsafe.Pointer(getempty())) 218 buf.nobj = 0 219 buf.next = nil 220 *head = buf 221 } else if buf.nobj == len(buf.obj) { 222 if s.freeBuf != nil { 223 buf = s.freeBuf 224 s.freeBuf = nil 225 } else { 226 buf = (*stackWorkBuf)(unsafe.Pointer(getempty())) 227 } 228 buf.nobj = 0 229 buf.next = *head 230 *head = buf 231 } 232 buf.obj[buf.nobj] = p 233 buf.nobj++ 234 } 235 236 // Remove and return a potential pointer to a stack object. 237 // Returns 0 if there are no more pointers available. 238 // 239 // This prefers non-conservative pointers so we scan stack objects 240 // precisely if there are any non-conservative pointers to them. 241 func (s *stackScanState) getPtr() (p uintptr, conservative bool) { 242 for _, head := range []**stackWorkBuf{&s.buf, &s.cbuf} { 243 buf := *head 244 if buf == nil { 245 // Never had any data. 246 continue 247 } 248 if buf.nobj == 0 { 249 if s.freeBuf != nil { 250 // Free old freeBuf. 251 putempty((*workbuf)(unsafe.Pointer(s.freeBuf))) 252 } 253 // Move buf to the freeBuf. 254 s.freeBuf = buf 255 buf = buf.next 256 *head = buf 257 if buf == nil { 258 // No more data in this list. 259 continue 260 } 261 } 262 buf.nobj-- 263 return buf.obj[buf.nobj], head == &s.cbuf 264 } 265 // No more data in either list. 266 if s.freeBuf != nil { 267 putempty((*workbuf)(unsafe.Pointer(s.freeBuf))) 268 s.freeBuf = nil 269 } 270 return 0, false 271 } 272 273 // addObject adds a stack object at addr of type typ to the set of stack objects. 274 func (s *stackScanState) addObject(addr uintptr, r *stackObjectRecord) { 275 x := s.tail 276 if x == nil { 277 // initial setup 278 x = (*stackObjectBuf)(unsafe.Pointer(getempty())) 279 x.next = nil 280 s.head = x 281 s.tail = x 282 } 283 if x.nobj > 0 && uint32(addr-s.stack.lo) < x.obj[x.nobj-1].off+x.obj[x.nobj-1].size { 284 throw("objects added out of order or overlapping") 285 } 286 if x.nobj == len(x.obj) { 287 // full buffer - allocate a new buffer, add to end of linked list 288 y := (*stackObjectBuf)(unsafe.Pointer(getempty())) 289 y.next = nil 290 x.next = y 291 s.tail = y 292 x = y 293 } 294 obj := &x.obj[x.nobj] 295 x.nobj++ 296 obj.off = uint32(addr - s.stack.lo) 297 obj.size = uint32(r.size) 298 obj.setRecord(r) 299 // obj.left and obj.right will be initialized by buildIndex before use. 300 s.nobjs++ 301 } 302 303 // buildIndex initializes s.root to a binary search tree. 304 // It should be called after all addObject calls but before 305 // any call of findObject. 306 func (s *stackScanState) buildIndex() { 307 s.root, _, _ = binarySearchTree(s.head, 0, s.nobjs) 308 } 309 310 // Build a binary search tree with the n objects in the list 311 // x.obj[idx], x.obj[idx+1], ..., x.next.obj[0], ... 312 // Returns the root of that tree, and the buf+idx of the nth object after x.obj[idx]. 313 // (The first object that was not included in the binary search tree.) 314 // If n == 0, returns nil, x. 315 func binarySearchTree(x *stackObjectBuf, idx int, n int) (root *stackObject, restBuf *stackObjectBuf, restIdx int) { 316 if n == 0 { 317 return nil, x, idx 318 } 319 var left, right *stackObject 320 left, x, idx = binarySearchTree(x, idx, n/2) 321 root = &x.obj[idx] 322 idx++ 323 if idx == len(x.obj) { 324 x = x.next 325 idx = 0 326 } 327 right, x, idx = binarySearchTree(x, idx, n-n/2-1) 328 root.left = left 329 root.right = right 330 return root, x, idx 331 } 332 333 // findObject returns the stack object containing address a, if any. 334 // Must have called buildIndex previously. 335 func (s *stackScanState) findObject(a uintptr) *stackObject { 336 off := uint32(a - s.stack.lo) 337 obj := s.root 338 for { 339 if obj == nil { 340 return nil 341 } 342 if off < obj.off { 343 obj = obj.left 344 continue 345 } 346 if off >= obj.off+obj.size { 347 obj = obj.right 348 continue 349 } 350 return obj 351 } 352 } 353