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, which looks at all the mcentral lists. 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 "internal/abi" 29 "internal/goexperiment" 30 "runtime/internal/atomic" 31 "unsafe" 32 ) 33 34 var sweep sweepdata 35 36 // State of background sweep. 37 type sweepdata struct { 38 lock mutex 39 g *g 40 parked bool 41 42 // active tracks outstanding sweepers and the sweep 43 // termination condition. 44 active activeSweep 45 46 // centralIndex is the current unswept span class. 47 // It represents an index into the mcentral span 48 // sets. Accessed and updated via its load and 49 // update methods. Not protected by a lock. 50 // 51 // Reset at mark termination. 52 // Used by mheap.nextSpanForSweep. 53 centralIndex sweepClass 54 } 55 56 // sweepClass is a spanClass and one bit to represent whether we're currently 57 // sweeping partial or full spans. 58 type sweepClass uint32 59 60 const ( 61 numSweepClasses = numSpanClasses * 2 62 sweepClassDone sweepClass = sweepClass(^uint32(0)) 63 ) 64 65 func (s *sweepClass) load() sweepClass { 66 return sweepClass(atomic.Load((*uint32)(s))) 67 } 68 69 func (s *sweepClass) update(sNew sweepClass) { 70 // Only update *s if its current value is less than sNew, 71 // since *s increases monotonically. 72 sOld := s.load() 73 for sOld < sNew && !atomic.Cas((*uint32)(s), uint32(sOld), uint32(sNew)) { 74 sOld = s.load() 75 } 76 // TODO(mknyszek): This isn't the only place we have 77 // an atomic monotonically increasing counter. It would 78 // be nice to have an "atomic max" which is just implemented 79 // as the above on most architectures. Some architectures 80 // like RISC-V however have native support for an atomic max. 81 } 82 83 func (s *sweepClass) clear() { 84 atomic.Store((*uint32)(s), 0) 85 } 86 87 // split returns the underlying span class as well as 88 // whether we're interested in the full or partial 89 // unswept lists for that class, indicated as a boolean 90 // (true means "full"). 91 func (s sweepClass) split() (spc spanClass, full bool) { 92 return spanClass(s >> 1), s&1 == 0 93 } 94 95 // nextSpanForSweep finds and pops the next span for sweeping from the 96 // central sweep buffers. It returns ownership of the span to the caller. 97 // Returns nil if no such span exists. 98 func (h *mheap) nextSpanForSweep() *mspan { 99 sg := h.sweepgen 100 for sc := sweep.centralIndex.load(); sc < numSweepClasses; sc++ { 101 spc, full := sc.split() 102 c := &h.central[spc].mcentral 103 var s *mspan 104 if full { 105 s = c.fullUnswept(sg).pop() 106 } else { 107 s = c.partialUnswept(sg).pop() 108 } 109 if s != nil { 110 // Write down that we found something so future sweepers 111 // can start from here. 112 sweep.centralIndex.update(sc) 113 return s 114 } 115 } 116 // Write down that we found nothing. 117 sweep.centralIndex.update(sweepClassDone) 118 return nil 119 } 120 121 const sweepDrainedMask = 1 << 31 122 123 // activeSweep is a type that captures whether sweeping 124 // is done, and whether there are any outstanding sweepers. 125 // 126 // Every potential sweeper must call begin() before they look 127 // for work, and end() after they've finished sweeping. 128 type activeSweep struct { 129 // state is divided into two parts. 130 // 131 // The top bit (masked by sweepDrainedMask) is a boolean 132 // value indicating whether all the sweep work has been 133 // drained from the queue. 134 // 135 // The rest of the bits are a counter, indicating the 136 // number of outstanding concurrent sweepers. 137 state atomic.Uint32 138 } 139 140 // begin registers a new sweeper. Returns a sweepLocker 141 // for acquiring spans for sweeping. Any outstanding sweeper blocks 142 // sweep termination. 143 // 144 // If the sweepLocker is invalid, the caller can be sure that all 145 // outstanding sweep work has been drained, so there is nothing left 146 // to sweep. Note that there may be sweepers currently running, so 147 // this does not indicate that all sweeping has completed. 148 // 149 // Even if the sweepLocker is invalid, its sweepGen is always valid. 150 func (a *activeSweep) begin() sweepLocker { 151 for { 152 state := a.state.Load() 153 if state&sweepDrainedMask != 0 { 154 return sweepLocker{mheap_.sweepgen, false} 155 } 156 if a.state.CompareAndSwap(state, state+1) { 157 return sweepLocker{mheap_.sweepgen, true} 158 } 159 } 160 } 161 162 // end deregisters a sweeper. Must be called once for each time 163 // begin is called if the sweepLocker is valid. 164 func (a *activeSweep) end(sl sweepLocker) { 165 if sl.sweepGen != mheap_.sweepgen { 166 throw("sweeper left outstanding across sweep generations") 167 } 168 for { 169 state := a.state.Load() 170 if (state&^sweepDrainedMask)-1 >= sweepDrainedMask { 171 throw("mismatched begin/end of activeSweep") 172 } 173 if a.state.CompareAndSwap(state, state-1) { 174 if state != sweepDrainedMask { 175 return 176 } 177 if debug.gcpacertrace > 0 { 178 live := gcController.heapLive.Load() 179 print("pacer: sweep done at heap size ", live>>20, "MB; allocated ", (live-mheap_.sweepHeapLiveBasis)>>20, "MB during sweep; swept ", mheap_.pagesSwept.Load(), " pages at ", mheap_.sweepPagesPerByte, " pages/byte\n") 180 } 181 return 182 } 183 } 184 } 185 186 // markDrained marks the active sweep cycle as having drained 187 // all remaining work. This is safe to be called concurrently 188 // with all other methods of activeSweep, though may race. 189 // 190 // Returns true if this call was the one that actually performed 191 // the mark. 192 func (a *activeSweep) markDrained() bool { 193 for { 194 state := a.state.Load() 195 if state&sweepDrainedMask != 0 { 196 return false 197 } 198 if a.state.CompareAndSwap(state, state|sweepDrainedMask) { 199 return true 200 } 201 } 202 } 203 204 // sweepers returns the current number of active sweepers. 205 func (a *activeSweep) sweepers() uint32 { 206 return a.state.Load() &^ sweepDrainedMask 207 } 208 209 // isDone returns true if all sweep work has been drained and no more 210 // outstanding sweepers exist. That is, when the sweep phase is 211 // completely done. 212 func (a *activeSweep) isDone() bool { 213 return a.state.Load() == sweepDrainedMask 214 } 215 216 // reset sets up the activeSweep for the next sweep cycle. 217 // 218 // The world must be stopped. 219 func (a *activeSweep) reset() { 220 assertWorldStopped() 221 a.state.Store(0) 222 } 223 224 // finishsweep_m ensures that all spans are swept. 225 // 226 // The world must be stopped. This ensures there are no sweeps in 227 // progress. 228 // 229 //go:nowritebarrier 230 func finishsweep_m() { 231 assertWorldStopped() 232 233 // Sweeping must be complete before marking commences, so 234 // sweep any unswept spans. If this is a concurrent GC, there 235 // shouldn't be any spans left to sweep, so this should finish 236 // instantly. If GC was forced before the concurrent sweep 237 // finished, there may be spans to sweep. 238 for sweepone() != ^uintptr(0) { 239 } 240 241 // Make sure there aren't any outstanding sweepers left. 242 // At this point, with the world stopped, it means one of two 243 // things. Either we were able to preempt a sweeper, or that 244 // a sweeper didn't call sweep.active.end when it should have. 245 // Both cases indicate a bug, so throw. 246 if sweep.active.sweepers() != 0 { 247 throw("active sweepers found at start of mark phase") 248 } 249 250 // Reset all the unswept buffers, which should be empty. 251 // Do this in sweep termination as opposed to mark termination 252 // so that we can catch unswept spans and reclaim blocks as 253 // soon as possible. 254 sg := mheap_.sweepgen 255 for i := range mheap_.central { 256 c := &mheap_.central[i].mcentral 257 c.partialUnswept(sg).reset() 258 c.fullUnswept(sg).reset() 259 } 260 261 // Sweeping is done, so there won't be any new memory to 262 // scavenge for a bit. 263 // 264 // If the scavenger isn't already awake, wake it up. There's 265 // definitely work for it to do at this point. 266 scavenger.wake() 267 268 nextMarkBitArenaEpoch() 269 } 270 271 func bgsweep(c chan int) { 272 sweep.g = getg() 273 274 lockInit(&sweep.lock, lockRankSweep) 275 lock(&sweep.lock) 276 sweep.parked = true 277 c <- 1 278 goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceBlockGCSweep, 1) 279 280 for { 281 // bgsweep attempts to be a "low priority" goroutine by intentionally 282 // yielding time. It's OK if it doesn't run, because goroutines allocating 283 // memory will sweep and ensure that all spans are swept before the next 284 // GC cycle. We really only want to run when we're idle. 285 // 286 // However, calling Gosched after each span swept produces a tremendous 287 // amount of tracing events, sometimes up to 50% of events in a trace. It's 288 // also inefficient to call into the scheduler so much because sweeping a 289 // single span is in general a very fast operation, taking as little as 30 ns 290 // on modern hardware. (See #54767.) 291 // 292 // As a result, bgsweep sweeps in batches, and only calls into the scheduler 293 // at the end of every batch. Furthermore, it only yields its time if there 294 // isn't spare idle time available on other cores. If there's available idle 295 // time, helping to sweep can reduce allocation latencies by getting ahead of 296 // the proportional sweeper and having spans ready to go for allocation. 297 const sweepBatchSize = 10 298 nSwept := 0 299 for sweepone() != ^uintptr(0) { 300 nSwept++ 301 if nSwept%sweepBatchSize == 0 { 302 goschedIfBusy() 303 } 304 } 305 for freeSomeWbufs(true) { 306 // N.B. freeSomeWbufs is already batched internally. 307 goschedIfBusy() 308 } 309 lock(&sweep.lock) 310 if !isSweepDone() { 311 // This can happen if a GC runs between 312 // gosweepone returning ^0 above 313 // and the lock being acquired. 314 unlock(&sweep.lock) 315 continue 316 } 317 sweep.parked = true 318 goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceBlockGCSweep, 1) 319 } 320 } 321 322 // sweepLocker acquires sweep ownership of spans. 323 type sweepLocker struct { 324 // sweepGen is the sweep generation of the heap. 325 sweepGen uint32 326 valid bool 327 } 328 329 // sweepLocked represents sweep ownership of a span. 330 type sweepLocked struct { 331 *mspan 332 } 333 334 // tryAcquire attempts to acquire sweep ownership of span s. If it 335 // successfully acquires ownership, it blocks sweep completion. 336 func (l *sweepLocker) tryAcquire(s *mspan) (sweepLocked, bool) { 337 if !l.valid { 338 throw("use of invalid sweepLocker") 339 } 340 // Check before attempting to CAS. 341 if atomic.Load(&s.sweepgen) != l.sweepGen-2 { 342 return sweepLocked{}, false 343 } 344 // Attempt to acquire sweep ownership of s. 345 if !atomic.Cas(&s.sweepgen, l.sweepGen-2, l.sweepGen-1) { 346 return sweepLocked{}, false 347 } 348 return sweepLocked{s}, true 349 } 350 351 // sweepone sweeps some unswept heap span and returns the number of pages returned 352 // to the heap, or ^uintptr(0) if there was nothing to sweep. 353 func sweepone() uintptr { 354 gp := getg() 355 356 // Increment locks to ensure that the goroutine is not preempted 357 // in the middle of sweep thus leaving the span in an inconsistent state for next GC 358 gp.m.locks++ 359 360 // TODO(austin): sweepone is almost always called in a loop; 361 // lift the sweepLocker into its callers. 362 sl := sweep.active.begin() 363 if !sl.valid { 364 gp.m.locks-- 365 return ^uintptr(0) 366 } 367 368 // Find a span to sweep. 369 npages := ^uintptr(0) 370 var noMoreWork bool 371 for { 372 s := mheap_.nextSpanForSweep() 373 if s == nil { 374 noMoreWork = sweep.active.markDrained() 375 break 376 } 377 if state := s.state.get(); state != mSpanInUse { 378 // This can happen if direct sweeping already 379 // swept this span, but in that case the sweep 380 // generation should always be up-to-date. 381 if !(s.sweepgen == sl.sweepGen || s.sweepgen == sl.sweepGen+3) { 382 print("runtime: bad span s.state=", state, " s.sweepgen=", s.sweepgen, " sweepgen=", sl.sweepGen, "\n") 383 throw("non in-use span in unswept list") 384 } 385 continue 386 } 387 if s, ok := sl.tryAcquire(s); ok { 388 // Sweep the span we found. 389 npages = s.npages 390 if s.sweep(false) { 391 // Whole span was freed. Count it toward the 392 // page reclaimer credit since these pages can 393 // now be used for span allocation. 394 mheap_.reclaimCredit.Add(npages) 395 } else { 396 // Span is still in-use, so this returned no 397 // pages to the heap and the span needs to 398 // move to the swept in-use list. 399 npages = 0 400 } 401 break 402 } 403 } 404 sweep.active.end(sl) 405 406 if noMoreWork { 407 // The sweep list is empty. There may still be 408 // concurrent sweeps running, but we're at least very 409 // close to done sweeping. 410 411 // Move the scavenge gen forward (signaling 412 // that there's new work to do) and wake the scavenger. 413 // 414 // The scavenger is signaled by the last sweeper because once 415 // sweeping is done, we will definitely have useful work for 416 // the scavenger to do, since the scavenger only runs over the 417 // heap once per GC cycle. This update is not done during sweep 418 // termination because in some cases there may be a long delay 419 // between sweep done and sweep termination (e.g. not enough 420 // allocations to trigger a GC) which would be nice to fill in 421 // with scavenging work. 422 if debug.scavtrace > 0 { 423 systemstack(func() { 424 lock(&mheap_.lock) 425 426 // Get released stats. 427 releasedBg := mheap_.pages.scav.releasedBg.Load() 428 releasedEager := mheap_.pages.scav.releasedEager.Load() 429 430 // Print the line. 431 printScavTrace(releasedBg, releasedEager, false) 432 433 // Update the stats. 434 mheap_.pages.scav.releasedBg.Add(-releasedBg) 435 mheap_.pages.scav.releasedEager.Add(-releasedEager) 436 unlock(&mheap_.lock) 437 }) 438 } 439 scavenger.ready() 440 } 441 442 gp.m.locks-- 443 return npages 444 } 445 446 // isSweepDone reports whether all spans are swept. 447 // 448 // Note that this condition may transition from false to true at any 449 // time as the sweeper runs. It may transition from true to false if a 450 // GC runs; to prevent that the caller must be non-preemptible or must 451 // somehow block GC progress. 452 func isSweepDone() bool { 453 return sweep.active.isDone() 454 } 455 456 // Returns only when span s has been swept. 457 // 458 //go:nowritebarrier 459 func (s *mspan) ensureSwept() { 460 // Caller must disable preemption. 461 // Otherwise when this function returns the span can become unswept again 462 // (if GC is triggered on another goroutine). 463 gp := getg() 464 if gp.m.locks == 0 && gp.m.mallocing == 0 && gp != gp.m.g0 { 465 throw("mspan.ensureSwept: m is not locked") 466 } 467 468 // If this operation fails, then that means that there are 469 // no more spans to be swept. In this case, either s has already 470 // been swept, or is about to be acquired for sweeping and swept. 471 sl := sweep.active.begin() 472 if sl.valid { 473 // The caller must be sure that the span is a mSpanInUse span. 474 if s, ok := sl.tryAcquire(s); ok { 475 s.sweep(false) 476 sweep.active.end(sl) 477 return 478 } 479 sweep.active.end(sl) 480 } 481 482 // Unfortunately we can't sweep the span ourselves. Somebody else 483 // got to it first. We don't have efficient means to wait, but that's 484 // OK, it will be swept fairly soon. 485 for { 486 spangen := atomic.Load(&s.sweepgen) 487 if spangen == sl.sweepGen || spangen == sl.sweepGen+3 { 488 break 489 } 490 osyield() 491 } 492 } 493 494 // sweep frees or collects finalizers for blocks not marked in the mark phase. 495 // It clears the mark bits in preparation for the next GC round. 496 // Returns true if the span was returned to heap. 497 // If preserve=true, don't return it to heap nor relink in mcentral lists; 498 // caller takes care of it. 499 func (sl *sweepLocked) sweep(preserve bool) bool { 500 // It's critical that we enter this function with preemption disabled, 501 // GC must not start while we are in the middle of this function. 502 gp := getg() 503 if gp.m.locks == 0 && gp.m.mallocing == 0 && gp != gp.m.g0 { 504 throw("mspan.sweep: m is not locked") 505 } 506 507 s := sl.mspan 508 if !preserve { 509 // We'll release ownership of this span. Nil it out to 510 // prevent the caller from accidentally using it. 511 sl.mspan = nil 512 } 513 514 sweepgen := mheap_.sweepgen 515 if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 { 516 print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n") 517 throw("mspan.sweep: bad span state") 518 } 519 520 trace := traceAcquire() 521 if trace.ok() { 522 trace.GCSweepSpan(s.npages * _PageSize) 523 traceRelease(trace) 524 } 525 526 mheap_.pagesSwept.Add(int64(s.npages)) 527 528 spc := s.spanclass 529 size := s.elemsize 530 531 // The allocBits indicate which unmarked objects don't need to be 532 // processed since they were free at the end of the last GC cycle 533 // and were not allocated since then. 534 // If the allocBits index is >= s.freeindex and the bit 535 // is not marked then the object remains unallocated 536 // since the last GC. 537 // This situation is analogous to being on a freelist. 538 539 // Unlink & free special records for any objects we're about to free. 540 // Two complications here: 541 // 1. An object can have both finalizer and profile special records. 542 // In such case we need to queue finalizer for execution, 543 // mark the object as live and preserve the profile special. 544 // 2. A tiny object can have several finalizers setup for different offsets. 545 // If such object is not marked, we need to queue all finalizers at once. 546 // Both 1 and 2 are possible at the same time. 547 hadSpecials := s.specials != nil 548 siter := newSpecialsIter(s) 549 for siter.valid() { 550 // A finalizer can be set for an inner byte of an object, find object beginning. 551 objIndex := uintptr(siter.s.offset) / size 552 p := s.base() + objIndex*size 553 mbits := s.markBitsForIndex(objIndex) 554 if !mbits.isMarked() { 555 // This object is not marked and has at least one special record. 556 // Pass 1: see if it has at least one finalizer. 557 hasFin := false 558 endOffset := p - s.base() + size 559 for tmp := siter.s; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next { 560 if tmp.kind == _KindSpecialFinalizer { 561 // Stop freeing of object if it has a finalizer. 562 mbits.setMarkedNonAtomic() 563 hasFin = true 564 break 565 } 566 } 567 // Pass 2: queue all finalizers _or_ handle profile record. 568 for siter.valid() && uintptr(siter.s.offset) < endOffset { 569 // Find the exact byte for which the special was setup 570 // (as opposed to object beginning). 571 special := siter.s 572 p := s.base() + uintptr(special.offset) 573 if special.kind == _KindSpecialFinalizer || !hasFin { 574 siter.unlinkAndNext() 575 freeSpecial(special, unsafe.Pointer(p), size) 576 } else { 577 // The object has finalizers, so we're keeping it alive. 578 // All other specials only apply when an object is freed, 579 // so just keep the special record. 580 siter.next() 581 } 582 } 583 } else { 584 // object is still live 585 if siter.s.kind == _KindSpecialReachable { 586 special := siter.unlinkAndNext() 587 (*specialReachable)(unsafe.Pointer(special)).reachable = true 588 freeSpecial(special, unsafe.Pointer(p), size) 589 } else { 590 // keep special record 591 siter.next() 592 } 593 } 594 } 595 if hadSpecials && s.specials == nil { 596 spanHasNoSpecials(s) 597 } 598 599 if debug.allocfreetrace != 0 || debug.clobberfree != 0 || raceenabled || msanenabled || asanenabled { 600 // Find all newly freed objects. This doesn't have to 601 // efficient; allocfreetrace has massive overhead. 602 mbits := s.markBitsForBase() 603 abits := s.allocBitsForIndex(0) 604 for i := uintptr(0); i < uintptr(s.nelems); i++ { 605 if !mbits.isMarked() && (abits.index < uintptr(s.freeindex) || abits.isMarked()) { 606 x := s.base() + i*s.elemsize 607 if debug.allocfreetrace != 0 { 608 tracefree(unsafe.Pointer(x), size) 609 } 610 if debug.clobberfree != 0 { 611 clobberfree(unsafe.Pointer(x), size) 612 } 613 // User arenas are handled on explicit free. 614 if raceenabled && !s.isUserArenaChunk { 615 racefree(unsafe.Pointer(x), size) 616 } 617 if msanenabled && !s.isUserArenaChunk { 618 msanfree(unsafe.Pointer(x), size) 619 } 620 if asanenabled && !s.isUserArenaChunk { 621 asanpoison(unsafe.Pointer(x), size) 622 } 623 } 624 mbits.advance() 625 abits.advance() 626 } 627 } 628 629 // Check for zombie objects. 630 if s.freeindex < s.nelems { 631 // Everything < freeindex is allocated and hence 632 // cannot be zombies. 633 // 634 // Check the first bitmap byte, where we have to be 635 // careful with freeindex. 636 obj := uintptr(s.freeindex) 637 if (*s.gcmarkBits.bytep(obj / 8)&^*s.allocBits.bytep(obj / 8))>>(obj%8) != 0 { 638 s.reportZombies() 639 } 640 // Check remaining bytes. 641 for i := obj/8 + 1; i < divRoundUp(uintptr(s.nelems), 8); i++ { 642 if *s.gcmarkBits.bytep(i)&^*s.allocBits.bytep(i) != 0 { 643 s.reportZombies() 644 } 645 } 646 } 647 648 // Count the number of free objects in this span. 649 nalloc := uint16(s.countAlloc()) 650 nfreed := s.allocCount - nalloc 651 if nalloc > s.allocCount { 652 // The zombie check above should have caught this in 653 // more detail. 654 print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n") 655 throw("sweep increased allocation count") 656 } 657 658 s.allocCount = nalloc 659 s.freeindex = 0 // reset allocation index to start of span. 660 s.freeIndexForScan = 0 661 if traceEnabled() { 662 getg().m.p.ptr().trace.reclaimed += uintptr(nfreed) * s.elemsize 663 } 664 665 // gcmarkBits becomes the allocBits. 666 // get a fresh cleared gcmarkBits in preparation for next GC 667 s.allocBits = s.gcmarkBits 668 s.gcmarkBits = newMarkBits(uintptr(s.nelems)) 669 670 // refresh pinnerBits if they exists 671 if s.pinnerBits != nil { 672 s.refreshPinnerBits() 673 } 674 675 // Initialize alloc bits cache. 676 s.refillAllocCache(0) 677 678 // The span must be in our exclusive ownership until we update sweepgen, 679 // check for potential races. 680 if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 { 681 print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n") 682 throw("mspan.sweep: bad span state after sweep") 683 } 684 if s.sweepgen == sweepgen+1 || s.sweepgen == sweepgen+3 { 685 throw("swept cached span") 686 } 687 688 // We need to set s.sweepgen = h.sweepgen only when all blocks are swept, 689 // because of the potential for a concurrent free/SetFinalizer. 690 // 691 // But we need to set it before we make the span available for allocation 692 // (return it to heap or mcentral), because allocation code assumes that a 693 // span is already swept if available for allocation. 694 // 695 // Serialization point. 696 // At this point the mark bits are cleared and allocation ready 697 // to go so release the span. 698 atomic.Store(&s.sweepgen, sweepgen) 699 700 if s.isUserArenaChunk { 701 if preserve { 702 // This is a case that should never be handled by a sweeper that 703 // preserves the span for reuse. 704 throw("sweep: tried to preserve a user arena span") 705 } 706 if nalloc > 0 { 707 // There still exist pointers into the span or the span hasn't been 708 // freed yet. It's not ready to be reused. Put it back on the 709 // full swept list for the next cycle. 710 mheap_.central[spc].mcentral.fullSwept(sweepgen).push(s) 711 return false 712 } 713 714 // It's only at this point that the sweeper doesn't actually need to look 715 // at this arena anymore, so subtract from pagesInUse now. 716 mheap_.pagesInUse.Add(-s.npages) 717 s.state.set(mSpanDead) 718 719 // The arena is ready to be recycled. Remove it from the quarantine list 720 // and place it on the ready list. Don't add it back to any sweep lists. 721 systemstack(func() { 722 // It's the arena code's responsibility to get the chunk on the quarantine 723 // list by the time all references to the chunk are gone. 724 if s.list != &mheap_.userArena.quarantineList { 725 throw("user arena span is on the wrong list") 726 } 727 lock(&mheap_.lock) 728 mheap_.userArena.quarantineList.remove(s) 729 mheap_.userArena.readyList.insert(s) 730 unlock(&mheap_.lock) 731 }) 732 return false 733 } 734 735 if spc.sizeclass() != 0 { 736 // Handle spans for small objects. 737 if nfreed > 0 { 738 // Only mark the span as needing zeroing if we've freed any 739 // objects, because a fresh span that had been allocated into, 740 // wasn't totally filled, but then swept, still has all of its 741 // free slots zeroed. 742 s.needzero = 1 743 stats := memstats.heapStats.acquire() 744 atomic.Xadd64(&stats.smallFreeCount[spc.sizeclass()], int64(nfreed)) 745 memstats.heapStats.release() 746 747 // Count the frees in the inconsistent, internal stats. 748 gcController.totalFree.Add(int64(nfreed) * int64(s.elemsize)) 749 } 750 if !preserve { 751 // The caller may not have removed this span from whatever 752 // unswept set its on but taken ownership of the span for 753 // sweeping by updating sweepgen. If this span still is in 754 // an unswept set, then the mcentral will pop it off the 755 // set, check its sweepgen, and ignore it. 756 if nalloc == 0 { 757 // Free totally free span directly back to the heap. 758 mheap_.freeSpan(s) 759 return true 760 } 761 // Return span back to the right mcentral list. 762 if nalloc == s.nelems { 763 mheap_.central[spc].mcentral.fullSwept(sweepgen).push(s) 764 } else { 765 mheap_.central[spc].mcentral.partialSwept(sweepgen).push(s) 766 } 767 } 768 } else if !preserve { 769 // Handle spans for large objects. 770 if nfreed != 0 { 771 // Free large object span to heap. 772 773 // Count the free in the consistent, external stats. 774 // 775 // Do this before freeSpan, which might update heapStats' inHeap 776 // value. If it does so, then metrics that subtract object footprint 777 // from inHeap might overflow. See #67019. 778 stats := memstats.heapStats.acquire() 779 atomic.Xadd64(&stats.largeFreeCount, 1) 780 atomic.Xadd64(&stats.largeFree, int64(size)) 781 memstats.heapStats.release() 782 783 // Count the free in the inconsistent, internal stats. 784 gcController.totalFree.Add(int64(size)) 785 786 // NOTE(rsc,dvyukov): The original implementation of efence 787 // in CL 22060046 used sysFree instead of sysFault, so that 788 // the operating system would eventually give the memory 789 // back to us again, so that an efence program could run 790 // longer without running out of memory. Unfortunately, 791 // calling sysFree here without any kind of adjustment of the 792 // heap data structures means that when the memory does 793 // come back to us, we have the wrong metadata for it, either in 794 // the mspan structures or in the garbage collection bitmap. 795 // Using sysFault here means that the program will run out of 796 // memory fairly quickly in efence mode, but at least it won't 797 // have mysterious crashes due to confused memory reuse. 798 // It should be possible to switch back to sysFree if we also 799 // implement and then call some kind of mheap.deleteSpan. 800 if debug.efence > 0 { 801 s.limit = 0 // prevent mlookup from finding this span 802 sysFault(unsafe.Pointer(s.base()), size) 803 } else { 804 mheap_.freeSpan(s) 805 } 806 if goexperiment.AllocHeaders && s.largeType != nil && s.largeType.TFlag&abi.TFlagUnrolledBitmap != 0 { 807 // In the allocheaders experiment, the unrolled GCProg bitmap is allocated separately. 808 // Free the space for the unrolled bitmap. 809 systemstack(func() { 810 s := spanOf(uintptr(unsafe.Pointer(s.largeType))) 811 mheap_.freeManual(s, spanAllocPtrScalarBits) 812 }) 813 // Make sure to zero this pointer without putting the old 814 // value in a write buffer, as the old value might be an 815 // invalid pointer. See arena.go:(*mheap).allocUserArenaChunk. 816 *(*uintptr)(unsafe.Pointer(&s.largeType)) = 0 817 } 818 return true 819 } 820 821 // Add a large span directly onto the full+swept list. 822 mheap_.central[spc].mcentral.fullSwept(sweepgen).push(s) 823 } 824 return false 825 } 826 827 // reportZombies reports any marked but free objects in s and throws. 828 // 829 // This generally means one of the following: 830 // 831 // 1. User code converted a pointer to a uintptr and then back 832 // unsafely, and a GC ran while the uintptr was the only reference to 833 // an object. 834 // 835 // 2. User code (or a compiler bug) constructed a bad pointer that 836 // points to a free slot, often a past-the-end pointer. 837 // 838 // 3. The GC two cycles ago missed a pointer and freed a live object, 839 // but it was still live in the last cycle, so this GC cycle found a 840 // pointer to that object and marked it. 841 func (s *mspan) reportZombies() { 842 printlock() 843 print("runtime: marked free object in span ", s, ", elemsize=", s.elemsize, " freeindex=", s.freeindex, " (bad use of unsafe.Pointer? try -d=checkptr)\n") 844 mbits := s.markBitsForBase() 845 abits := s.allocBitsForIndex(0) 846 for i := uintptr(0); i < uintptr(s.nelems); i++ { 847 addr := s.base() + i*s.elemsize 848 print(hex(addr)) 849 alloc := i < uintptr(s.freeindex) || abits.isMarked() 850 if alloc { 851 print(" alloc") 852 } else { 853 print(" free ") 854 } 855 if mbits.isMarked() { 856 print(" marked ") 857 } else { 858 print(" unmarked") 859 } 860 zombie := mbits.isMarked() && !alloc 861 if zombie { 862 print(" zombie") 863 } 864 print("\n") 865 if zombie { 866 length := s.elemsize 867 if length > 1024 { 868 length = 1024 869 } 870 hexdumpWords(addr, addr+length, nil) 871 } 872 mbits.advance() 873 abits.advance() 874 } 875 throw("found pointer to free object") 876 } 877 878 // deductSweepCredit deducts sweep credit for allocating a span of 879 // size spanBytes. This must be performed *before* the span is 880 // allocated to ensure the system has enough credit. If necessary, it 881 // performs sweeping to prevent going in to debt. If the caller will 882 // also sweep pages (e.g., for a large allocation), it can pass a 883 // non-zero callerSweepPages to leave that many pages unswept. 884 // 885 // deductSweepCredit makes a worst-case assumption that all spanBytes 886 // bytes of the ultimately allocated span will be available for object 887 // allocation. 888 // 889 // deductSweepCredit is the core of the "proportional sweep" system. 890 // It uses statistics gathered by the garbage collector to perform 891 // enough sweeping so that all pages are swept during the concurrent 892 // sweep phase between GC cycles. 893 // 894 // mheap_ must NOT be locked. 895 func deductSweepCredit(spanBytes uintptr, callerSweepPages uintptr) { 896 if mheap_.sweepPagesPerByte == 0 { 897 // Proportional sweep is done or disabled. 898 return 899 } 900 901 trace := traceAcquire() 902 if trace.ok() { 903 trace.GCSweepStart() 904 traceRelease(trace) 905 } 906 907 // Fix debt if necessary. 908 retry: 909 sweptBasis := mheap_.pagesSweptBasis.Load() 910 live := gcController.heapLive.Load() 911 liveBasis := mheap_.sweepHeapLiveBasis 912 newHeapLive := spanBytes 913 if liveBasis < live { 914 // Only do this subtraction when we don't overflow. Otherwise, pagesTarget 915 // might be computed as something really huge, causing us to get stuck 916 // sweeping here until the next mark phase. 917 // 918 // Overflow can happen here if gcPaceSweeper is called concurrently with 919 // sweeping (i.e. not during a STW, like it usually is) because this code 920 // is intentionally racy. A concurrent call to gcPaceSweeper can happen 921 // if a GC tuning parameter is modified and we read an older value of 922 // heapLive than what was used to set the basis. 923 // 924 // This state should be transient, so it's fine to just let newHeapLive 925 // be a relatively small number. We'll probably just skip this attempt to 926 // sweep. 927 // 928 // See issue #57523. 929 newHeapLive += uintptr(live - liveBasis) 930 } 931 pagesTarget := int64(mheap_.sweepPagesPerByte*float64(newHeapLive)) - int64(callerSweepPages) 932 for pagesTarget > int64(mheap_.pagesSwept.Load()-sweptBasis) { 933 if sweepone() == ^uintptr(0) { 934 mheap_.sweepPagesPerByte = 0 935 break 936 } 937 if mheap_.pagesSweptBasis.Load() != sweptBasis { 938 // Sweep pacing changed. Recompute debt. 939 goto retry 940 } 941 } 942 943 trace = traceAcquire() 944 if trace.ok() { 945 trace.GCSweepDone() 946 traceRelease(trace) 947 } 948 } 949 950 // clobberfree sets the memory content at x to bad content, for debugging 951 // purposes. 952 func clobberfree(x unsafe.Pointer, size uintptr) { 953 // size (span.elemsize) is always a multiple of 4. 954 for i := uintptr(0); i < size; i += 4 { 955 *(*uint32)(add(x, i)) = 0xdeadbeef 956 } 957 } 958 959 // gcPaceSweeper updates the sweeper's pacing parameters. 960 // 961 // Must be called whenever the GC's pacing is updated. 962 // 963 // The world must be stopped, or mheap_.lock must be held. 964 func gcPaceSweeper(trigger uint64) { 965 assertWorldStoppedOrLockHeld(&mheap_.lock) 966 967 // Update sweep pacing. 968 if isSweepDone() { 969 mheap_.sweepPagesPerByte = 0 970 } else { 971 // Concurrent sweep needs to sweep all of the in-use 972 // pages by the time the allocated heap reaches the GC 973 // trigger. Compute the ratio of in-use pages to sweep 974 // per byte allocated, accounting for the fact that 975 // some might already be swept. 976 heapLiveBasis := gcController.heapLive.Load() 977 heapDistance := int64(trigger) - int64(heapLiveBasis) 978 // Add a little margin so rounding errors and 979 // concurrent sweep are less likely to leave pages 980 // unswept when GC starts. 981 heapDistance -= 1024 * 1024 982 if heapDistance < _PageSize { 983 // Avoid setting the sweep ratio extremely high 984 heapDistance = _PageSize 985 } 986 pagesSwept := mheap_.pagesSwept.Load() 987 pagesInUse := mheap_.pagesInUse.Load() 988 sweepDistancePages := int64(pagesInUse) - int64(pagesSwept) 989 if sweepDistancePages <= 0 { 990 mheap_.sweepPagesPerByte = 0 991 } else { 992 mheap_.sweepPagesPerByte = float64(sweepDistancePages) / float64(heapDistance) 993 mheap_.sweepHeapLiveBasis = heapLiveBasis 994 // Write pagesSweptBasis last, since this 995 // signals concurrent sweeps to recompute 996 // their debt. 997 mheap_.pagesSweptBasis.Store(pagesSwept) 998 } 999 } 1000 } 1001