1 // Copyright 2009 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: sweeping 6 7 // The sweeper consists of two different algorithms: 8 // 9 // * The object reclaimer finds and frees unmarked slots in spans. It 10 // can free a whole span if none of the objects are marked, but that 11 // isn't its goal. This can be driven either synchronously by 12 // mcentral.cacheSpan for mcentral spans, or asynchronously by 13 // sweepone from the list of all in-use spans in mheap_.sweepSpans. 14 // 15 // * The span reclaimer looks for spans that contain no marked objects 16 // and frees whole spans. This is a separate algorithm because 17 // freeing whole spans is the hardest task for the object reclaimer, 18 // but is critical when allocating new spans. The entry point for 19 // this is mheap_.reclaim and it's driven by a sequential scan of 20 // the page marks bitmap in the heap arenas. 21 // 22 // Both algorithms ultimately call mspan.sweep, which sweeps a single 23 // heap span. 24 25 package runtime 26 27 import ( 28 "runtime/internal/atomic" 29 "unsafe" 30 ) 31 32 var sweep sweepdata 33 34 // State of background sweep. 35 type sweepdata struct { 36 lock mutex 37 g *g 38 parked bool 39 started bool 40 41 nbgsweep uint32 42 npausesweep uint32 43 } 44 45 // finishsweep_m ensures that all spans are swept. 46 // 47 // The world must be stopped. This ensures there are no sweeps in 48 // progress. 49 // 50 //go:nowritebarrier 51 func finishsweep_m() { 52 // Sweeping must be complete before marking commences, so 53 // sweep any unswept spans. If this is a concurrent GC, there 54 // shouldn't be any spans left to sweep, so this should finish 55 // instantly. If GC was forced before the concurrent sweep 56 // finished, there may be spans to sweep. 57 for sweepone() != ^uintptr(0) { 58 sweep.npausesweep++ 59 } 60 61 nextMarkBitArenaEpoch() 62 } 63 64 func bgsweep(c chan int) { 65 sweep.g = getg() 66 67 lock(&sweep.lock) 68 sweep.parked = true 69 c <- 1 70 goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1) 71 72 for { 73 for sweepone() != ^uintptr(0) { 74 sweep.nbgsweep++ 75 Gosched() 76 } 77 for freeSomeWbufs(true) { 78 Gosched() 79 } 80 lock(&sweep.lock) 81 if !isSweepDone() { 82 // This can happen if a GC runs between 83 // gosweepone returning ^0 above 84 // and the lock being acquired. 85 unlock(&sweep.lock) 86 continue 87 } 88 sweep.parked = true 89 goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1) 90 } 91 } 92 93 // sweepone sweeps some unswept heap span and returns the number of pages returned 94 // to the heap, or ^uintptr(0) if there was nothing to sweep. 95 func sweepone() uintptr { 96 _g_ := getg() 97 sweepRatio := mheap_.sweepPagesPerByte // For debugging 98 99 // increment locks to ensure that the goroutine is not preempted 100 // in the middle of sweep thus leaving the span in an inconsistent state for next GC 101 _g_.m.locks++ 102 if atomic.Load(&mheap_.sweepdone) != 0 { 103 _g_.m.locks-- 104 return ^uintptr(0) 105 } 106 atomic.Xadd(&mheap_.sweepers, +1) 107 108 // Find a span to sweep. 109 var s *mspan 110 sg := mheap_.sweepgen 111 for { 112 s = mheap_.sweepSpans[1-sg/2%2].pop() 113 if s == nil { 114 atomic.Store(&mheap_.sweepdone, 1) 115 break 116 } 117 if s.state != mSpanInUse { 118 // This can happen if direct sweeping already 119 // swept this span, but in that case the sweep 120 // generation should always be up-to-date. 121 if !(s.sweepgen == sg || s.sweepgen == sg+3) { 122 print("runtime: bad span s.state=", s.state, " s.sweepgen=", s.sweepgen, " sweepgen=", sg, "\n") 123 throw("non in-use span in unswept list") 124 } 125 continue 126 } 127 if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) { 128 break 129 } 130 } 131 132 // Sweep the span we found. 133 npages := ^uintptr(0) 134 if s != nil { 135 npages = s.npages 136 if s.sweep(false) { 137 // Whole span was freed. Count it toward the 138 // page reclaimer credit since these pages can 139 // now be used for span allocation. 140 atomic.Xadduintptr(&mheap_.reclaimCredit, npages) 141 } else { 142 // Span is still in-use, so this returned no 143 // pages to the heap and the span needs to 144 // move to the swept in-use list. 145 npages = 0 146 } 147 } 148 149 // Decrement the number of active sweepers and if this is the 150 // last one print trace information. 151 if atomic.Xadd(&mheap_.sweepers, -1) == 0 && atomic.Load(&mheap_.sweepdone) != 0 { 152 if debug.gcpacertrace > 0 { 153 print("pacer: sweep done at heap size ", memstats.heap_live>>20, "MB; allocated ", (memstats.heap_live-mheap_.sweepHeapLiveBasis)>>20, "MB during sweep; swept ", mheap_.pagesSwept, " pages at ", sweepRatio, " pages/byte\n") 154 } 155 } 156 _g_.m.locks-- 157 return npages 158 } 159 160 // isSweepDone reports whether all spans are swept or currently being swept. 161 // 162 // Note that this condition may transition from false to true at any 163 // time as the sweeper runs. It may transition from true to false if a 164 // GC runs; to prevent that the caller must be non-preemptible or must 165 // somehow block GC progress. 166 func isSweepDone() bool { 167 return mheap_.sweepdone != 0 168 } 169 170 // Returns only when span s has been swept. 171 //go:nowritebarrier 172 func (s *mspan) ensureSwept() { 173 // Caller must disable preemption. 174 // Otherwise when this function returns the span can become unswept again 175 // (if GC is triggered on another goroutine). 176 _g_ := getg() 177 if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 { 178 throw("mspan.ensureSwept: m is not locked") 179 } 180 181 sg := mheap_.sweepgen 182 spangen := atomic.Load(&s.sweepgen) 183 if spangen == sg || spangen == sg+3 { 184 return 185 } 186 // The caller must be sure that the span is a mSpanInUse span. 187 if atomic.Cas(&s.sweepgen, sg-2, sg-1) { 188 s.sweep(false) 189 return 190 } 191 // unfortunate condition, and we don't have efficient means to wait 192 for { 193 spangen := atomic.Load(&s.sweepgen) 194 if spangen == sg || spangen == sg+3 { 195 break 196 } 197 osyield() 198 } 199 } 200 201 // Sweep frees or collects finalizers for blocks not marked in the mark phase. 202 // It clears the mark bits in preparation for the next GC round. 203 // Returns true if the span was returned to heap. 204 // If preserve=true, don't return it to heap nor relink in mcentral lists; 205 // caller takes care of it. 206 //TODO go:nowritebarrier 207 func (s *mspan) sweep(preserve bool) bool { 208 // It's critical that we enter this function with preemption disabled, 209 // GC must not start while we are in the middle of this function. 210 _g_ := getg() 211 if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 { 212 throw("mspan.sweep: m is not locked") 213 } 214 sweepgen := mheap_.sweepgen 215 if s.state != mSpanInUse || s.sweepgen != sweepgen-1 { 216 print("mspan.sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n") 217 throw("mspan.sweep: bad span state") 218 } 219 220 if trace.enabled { 221 traceGCSweepSpan(s.npages * _PageSize) 222 } 223 224 atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages)) 225 226 spc := s.spanclass 227 size := s.elemsize 228 res := false 229 230 c := _g_.m.mcache 231 freeToHeap := false 232 233 // The allocBits indicate which unmarked objects don't need to be 234 // processed since they were free at the end of the last GC cycle 235 // and were not allocated since then. 236 // If the allocBits index is >= s.freeindex and the bit 237 // is not marked then the object remains unallocated 238 // since the last GC. 239 // This situation is analogous to being on a freelist. 240 241 // Unlink & free special records for any objects we're about to free. 242 // Two complications here: 243 // 1. An object can have both finalizer and profile special records. 244 // In such case we need to queue finalizer for execution, 245 // mark the object as live and preserve the profile special. 246 // 2. A tiny object can have several finalizers setup for different offsets. 247 // If such object is not marked, we need to queue all finalizers at once. 248 // Both 1 and 2 are possible at the same time. 249 specialp := &s.specials 250 special := *specialp 251 for special != nil { 252 // A finalizer can be set for an inner byte of an object, find object beginning. 253 objIndex := uintptr(special.offset) / size 254 p := s.base() + objIndex*size 255 mbits := s.markBitsForIndex(objIndex) 256 if !mbits.isMarked() { 257 // This object is not marked and has at least one special record. 258 // Pass 1: see if it has at least one finalizer. 259 hasFin := false 260 endOffset := p - s.base() + size 261 for tmp := special; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next { 262 if tmp.kind == _KindSpecialFinalizer { 263 // Stop freeing of object if it has a finalizer. 264 mbits.setMarkedNonAtomic() 265 hasFin = true 266 break 267 } 268 } 269 // Pass 2: queue all finalizers _or_ handle profile record. 270 for special != nil && uintptr(special.offset) < endOffset { 271 // Find the exact byte for which the special was setup 272 // (as opposed to object beginning). 273 p := s.base() + uintptr(special.offset) 274 if special.kind == _KindSpecialFinalizer || !hasFin { 275 // Splice out special record. 276 y := special 277 special = special.next 278 *specialp = special 279 freespecial(y, unsafe.Pointer(p), size) 280 } else { 281 // This is profile record, but the object has finalizers (so kept alive). 282 // Keep special record. 283 specialp = &special.next 284 special = *specialp 285 } 286 } 287 } else { 288 // object is still live: keep special record 289 specialp = &special.next 290 special = *specialp 291 } 292 } 293 294 if debug.allocfreetrace != 0 || debug.clobberfree != 0 || raceenabled || msanenabled { 295 // Find all newly freed objects. This doesn't have to 296 // efficient; allocfreetrace has massive overhead. 297 mbits := s.markBitsForBase() 298 abits := s.allocBitsForIndex(0) 299 for i := uintptr(0); i < s.nelems; i++ { 300 if !mbits.isMarked() && (abits.index < s.freeindex || abits.isMarked()) { 301 x := s.base() + i*s.elemsize 302 if debug.allocfreetrace != 0 { 303 tracefree(unsafe.Pointer(x), size) 304 } 305 if debug.clobberfree != 0 { 306 clobberfree(unsafe.Pointer(x), size) 307 } 308 if raceenabled { 309 racefree(unsafe.Pointer(x), size) 310 } 311 if msanenabled { 312 msanfree(unsafe.Pointer(x), size) 313 } 314 } 315 mbits.advance() 316 abits.advance() 317 } 318 } 319 320 // Count the number of free objects in this span. 321 nalloc := uint16(s.countAlloc()) 322 if spc.sizeclass() == 0 && nalloc == 0 { 323 s.needzero = 1 324 freeToHeap = true 325 } 326 nfreed := s.allocCount - nalloc 327 if nalloc > s.allocCount { 328 print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n") 329 throw("sweep increased allocation count") 330 } 331 332 s.allocCount = nalloc 333 wasempty := s.nextFreeIndex() == s.nelems 334 s.freeindex = 0 // reset allocation index to start of span. 335 if trace.enabled { 336 getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize 337 } 338 339 // gcmarkBits becomes the allocBits. 340 // get a fresh cleared gcmarkBits in preparation for next GC 341 s.allocBits = s.gcmarkBits 342 s.gcmarkBits = newMarkBits(s.nelems) 343 344 // Initialize alloc bits cache. 345 s.refillAllocCache(0) 346 347 // We need to set s.sweepgen = h.sweepgen only when all blocks are swept, 348 // because of the potential for a concurrent free/SetFinalizer. 349 // But we need to set it before we make the span available for allocation 350 // (return it to heap or mcentral), because allocation code assumes that a 351 // span is already swept if available for allocation. 352 if freeToHeap || nfreed == 0 { 353 // The span must be in our exclusive ownership until we update sweepgen, 354 // check for potential races. 355 if s.state != mSpanInUse || s.sweepgen != sweepgen-1 { 356 print("mspan.sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n") 357 throw("mspan.sweep: bad span state after sweep") 358 } 359 // Serialization point. 360 // At this point the mark bits are cleared and allocation ready 361 // to go so release the span. 362 atomic.Store(&s.sweepgen, sweepgen) 363 } 364 365 if nfreed > 0 && spc.sizeclass() != 0 { 366 c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed) 367 res = mheap_.central[spc].mcentral.freeSpan(s, preserve, wasempty) 368 // mcentral.freeSpan updates sweepgen 369 } else if freeToHeap { 370 // Free large span to heap 371 372 // NOTE(rsc,dvyukov): The original implementation of efence 373 // in CL 22060046 used sysFree instead of sysFault, so that 374 // the operating system would eventually give the memory 375 // back to us again, so that an efence program could run 376 // longer without running out of memory. Unfortunately, 377 // calling sysFree here without any kind of adjustment of the 378 // heap data structures means that when the memory does 379 // come back to us, we have the wrong metadata for it, either in 380 // the mspan structures or in the garbage collection bitmap. 381 // Using sysFault here means that the program will run out of 382 // memory fairly quickly in efence mode, but at least it won't 383 // have mysterious crashes due to confused memory reuse. 384 // It should be possible to switch back to sysFree if we also 385 // implement and then call some kind of mheap.deleteSpan. 386 if debug.efence > 0 { 387 s.limit = 0 // prevent mlookup from finding this span 388 sysFault(unsafe.Pointer(s.base()), size) 389 } else { 390 mheap_.freeSpan(s, true) 391 } 392 c.local_nlargefree++ 393 c.local_largefree += size 394 res = true 395 } 396 if !res { 397 // The span has been swept and is still in-use, so put 398 // it on the swept in-use list. 399 mheap_.sweepSpans[sweepgen/2%2].push(s) 400 } 401 return res 402 } 403 404 // deductSweepCredit deducts sweep credit for allocating a span of 405 // size spanBytes. This must be performed *before* the span is 406 // allocated to ensure the system has enough credit. If necessary, it 407 // performs sweeping to prevent going in to debt. If the caller will 408 // also sweep pages (e.g., for a large allocation), it can pass a 409 // non-zero callerSweepPages to leave that many pages unswept. 410 // 411 // deductSweepCredit makes a worst-case assumption that all spanBytes 412 // bytes of the ultimately allocated span will be available for object 413 // allocation. 414 // 415 // deductSweepCredit is the core of the "proportional sweep" system. 416 // It uses statistics gathered by the garbage collector to perform 417 // enough sweeping so that all pages are swept during the concurrent 418 // sweep phase between GC cycles. 419 // 420 // mheap_ must NOT be locked. 421 func deductSweepCredit(spanBytes uintptr, callerSweepPages uintptr) { 422 if mheap_.sweepPagesPerByte == 0 { 423 // Proportional sweep is done or disabled. 424 return 425 } 426 427 if trace.enabled { 428 traceGCSweepStart() 429 } 430 431 retry: 432 sweptBasis := atomic.Load64(&mheap_.pagesSweptBasis) 433 434 // Fix debt if necessary. 435 newHeapLive := uintptr(atomic.Load64(&memstats.heap_live)-mheap_.sweepHeapLiveBasis) + spanBytes 436 pagesTarget := int64(mheap_.sweepPagesPerByte*float64(newHeapLive)) - int64(callerSweepPages) 437 for pagesTarget > int64(atomic.Load64(&mheap_.pagesSwept)-sweptBasis) { 438 if sweepone() == ^uintptr(0) { 439 mheap_.sweepPagesPerByte = 0 440 break 441 } 442 if atomic.Load64(&mheap_.pagesSweptBasis) != sweptBasis { 443 // Sweep pacing changed. Recompute debt. 444 goto retry 445 } 446 } 447 448 if trace.enabled { 449 traceGCSweepDone() 450 } 451 } 452 453 // clobberfree sets the memory content at x to bad content, for debugging 454 // purposes. 455 func clobberfree(x unsafe.Pointer, size uintptr) { 456 // size (span.elemsize) is always a multiple of 4. 457 for i := uintptr(0); i < size; i += 4 { 458 *(*uint32)(add(x, i)) = 0xdeadbeef 459 } 460 } 461
View as plain text