Source file src/runtime/mgcsweep.go

Documentation: runtime

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

View as plain text