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