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

View as plain text