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