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