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 from the list of all in-use spans in mheap_.sweepSpans.
    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  
    45  // finishsweep_m ensures that all spans are swept.
    46  //
    47  // The world must be stopped. This ensures there are no sweeps in
    48  // progress.
    49  //
    50  //go:nowritebarrier
    51  func finishsweep_m() {
    52  	// Sweeping must be complete before marking commences, so
    53  	// sweep any unswept spans. If this is a concurrent GC, there
    54  	// shouldn't be any spans left to sweep, so this should finish
    55  	// instantly. If GC was forced before the concurrent sweep
    56  	// finished, there may be spans to sweep.
    57  	for sweepone() != ^uintptr(0) {
    58  		sweep.npausesweep++
    59  	}
    60  
    61  	nextMarkBitArenaEpoch()
    62  }
    63  
    64  func bgsweep(c chan int) {
    65  	sweep.g = getg()
    66  
    67  	lock(&sweep.lock)
    68  	sweep.parked = true
    69  	c <- 1
    70  	goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1)
    71  
    72  	for {
    73  		for sweepone() != ^uintptr(0) {
    74  			sweep.nbgsweep++
    75  			Gosched()
    76  		}
    77  		for freeSomeWbufs(true) {
    78  			Gosched()
    79  		}
    80  		lock(&sweep.lock)
    81  		if !isSweepDone() {
    82  			// This can happen if a GC runs between
    83  			// gosweepone returning ^0 above
    84  			// and the lock being acquired.
    85  			unlock(&sweep.lock)
    86  			continue
    87  		}
    88  		sweep.parked = true
    89  		goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1)
    90  	}
    91  }
    92  
    93  // sweepone sweeps some unswept heap span and returns the number of pages returned
    94  // to the heap, or ^uintptr(0) if there was nothing to sweep.
    95  func sweepone() uintptr {
    96  	_g_ := getg()
    97  	sweepRatio := mheap_.sweepPagesPerByte // For debugging
    98  
    99  	// increment locks to ensure that the goroutine is not preempted
   100  	// in the middle of sweep thus leaving the span in an inconsistent state for next GC
   101  	_g_.m.locks++
   102  	if atomic.Load(&mheap_.sweepdone) != 0 {
   103  		_g_.m.locks--
   104  		return ^uintptr(0)
   105  	}
   106  	atomic.Xadd(&mheap_.sweepers, +1)
   107  
   108  	// Find a span to sweep.
   109  	var s *mspan
   110  	sg := mheap_.sweepgen
   111  	for {
   112  		s = mheap_.sweepSpans[1-sg/2%2].pop()
   113  		if s == nil {
   114  			atomic.Store(&mheap_.sweepdone, 1)
   115  			break
   116  		}
   117  		if state := s.state.get(); state != mSpanInUse {
   118  			// This can happen if direct sweeping already
   119  			// swept this span, but in that case the sweep
   120  			// generation should always be up-to-date.
   121  			if !(s.sweepgen == sg || s.sweepgen == sg+3) {
   122  				print("runtime: bad span s.state=", state, " s.sweepgen=", s.sweepgen, " sweepgen=", sg, "\n")
   123  				throw("non in-use span in unswept list")
   124  			}
   125  			continue
   126  		}
   127  		if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
   128  			break
   129  		}
   130  	}
   131  
   132  	// Sweep the span we found.
   133  	npages := ^uintptr(0)
   134  	if s != nil {
   135  		npages = s.npages
   136  		if s.sweep(false) {
   137  			// Whole span was freed. Count it toward the
   138  			// page reclaimer credit since these pages can
   139  			// now be used for span allocation.
   140  			atomic.Xadduintptr(&mheap_.reclaimCredit, npages)
   141  		} else {
   142  			// Span is still in-use, so this returned no
   143  			// pages to the heap and the span needs to
   144  			// move to the swept in-use list.
   145  			npages = 0
   146  		}
   147  	}
   148  
   149  	// Decrement the number of active sweepers and if this is the
   150  	// last one print trace information.
   151  	if atomic.Xadd(&mheap_.sweepers, -1) == 0 && atomic.Load(&mheap_.sweepdone) != 0 {
   152  		if debug.gcpacertrace > 0 {
   153  			print("pacer: sweep done at heap size ", memstats.heap_live>>20, "MB; allocated ", (memstats.heap_live-mheap_.sweepHeapLiveBasis)>>20, "MB during sweep; swept ", mheap_.pagesSwept, " pages at ", sweepRatio, " pages/byte\n")
   154  		}
   155  	}
   156  	_g_.m.locks--
   157  	return npages
   158  }
   159  
   160  // isSweepDone reports whether all spans are swept or currently being swept.
   161  //
   162  // Note that this condition may transition from false to true at any
   163  // time as the sweeper runs. It may transition from true to false if a
   164  // GC runs; to prevent that the caller must be non-preemptible or must
   165  // somehow block GC progress.
   166  func isSweepDone() bool {
   167  	return mheap_.sweepdone != 0
   168  }
   169  
   170  // Returns only when span s has been swept.
   171  //go:nowritebarrier
   172  func (s *mspan) ensureSwept() {
   173  	// Caller must disable preemption.
   174  	// Otherwise when this function returns the span can become unswept again
   175  	// (if GC is triggered on another goroutine).
   176  	_g_ := getg()
   177  	if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
   178  		throw("mspan.ensureSwept: m is not locked")
   179  	}
   180  
   181  	sg := mheap_.sweepgen
   182  	spangen := atomic.Load(&s.sweepgen)
   183  	if spangen == sg || spangen == sg+3 {
   184  		return
   185  	}
   186  	// The caller must be sure that the span is a mSpanInUse span.
   187  	if atomic.Cas(&s.sweepgen, sg-2, sg-1) {
   188  		s.sweep(false)
   189  		return
   190  	}
   191  	// unfortunate condition, and we don't have efficient means to wait
   192  	for {
   193  		spangen := atomic.Load(&s.sweepgen)
   194  		if spangen == sg || spangen == sg+3 {
   195  			break
   196  		}
   197  		osyield()
   198  	}
   199  }
   200  
   201  // Sweep frees or collects finalizers for blocks not marked in the mark phase.
   202  // It clears the mark bits in preparation for the next GC round.
   203  // Returns true if the span was returned to heap.
   204  // If preserve=true, don't return it to heap nor relink in mcentral lists;
   205  // caller takes care of it.
   206  func (s *mspan) sweep(preserve bool) bool {
   207  	// It's critical that we enter this function with preemption disabled,
   208  	// GC must not start while we are in the middle of this function.
   209  	_g_ := getg()
   210  	if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
   211  		throw("mspan.sweep: m is not locked")
   212  	}
   213  	sweepgen := mheap_.sweepgen
   214  	if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
   215  		print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
   216  		throw("mspan.sweep: bad span state")
   217  	}
   218  
   219  	if trace.enabled {
   220  		traceGCSweepSpan(s.npages * _PageSize)
   221  	}
   222  
   223  	atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages))
   224  
   225  	spc := s.spanclass
   226  	size := s.elemsize
   227  	res := false
   228  
   229  	c := _g_.m.mcache
   230  	freeToHeap := false
   231  
   232  	// The allocBits indicate which unmarked objects don't need to be
   233  	// processed since they were free at the end of the last GC cycle
   234  	// and were not allocated since then.
   235  	// If the allocBits index is >= s.freeindex and the bit
   236  	// is not marked then the object remains unallocated
   237  	// since the last GC.
   238  	// This situation is analogous to being on a freelist.
   239  
   240  	// Unlink & free special records for any objects we're about to free.
   241  	// Two complications here:
   242  	// 1. An object can have both finalizer and profile special records.
   243  	//    In such case we need to queue finalizer for execution,
   244  	//    mark the object as live and preserve the profile special.
   245  	// 2. A tiny object can have several finalizers setup for different offsets.
   246  	//    If such object is not marked, we need to queue all finalizers at once.
   247  	// Both 1 and 2 are possible at the same time.
   248  	specialp := &s.specials
   249  	special := *specialp
   250  	for special != nil {
   251  		// A finalizer can be set for an inner byte of an object, find object beginning.
   252  		objIndex := uintptr(special.offset) / size
   253  		p := s.base() + objIndex*size
   254  		mbits := s.markBitsForIndex(objIndex)
   255  		if !mbits.isMarked() {
   256  			// This object is not marked and has at least one special record.
   257  			// Pass 1: see if it has at least one finalizer.
   258  			hasFin := false
   259  			endOffset := p - s.base() + size
   260  			for tmp := special; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next {
   261  				if tmp.kind == _KindSpecialFinalizer {
   262  					// Stop freeing of object if it has a finalizer.
   263  					mbits.setMarkedNonAtomic()
   264  					hasFin = true
   265  					break
   266  				}
   267  			}
   268  			// Pass 2: queue all finalizers _or_ handle profile record.
   269  			for special != nil && uintptr(special.offset) < endOffset {
   270  				// Find the exact byte for which the special was setup
   271  				// (as opposed to object beginning).
   272  				p := s.base() + uintptr(special.offset)
   273  				if special.kind == _KindSpecialFinalizer || !hasFin {
   274  					// Splice out special record.
   275  					y := special
   276  					special = special.next
   277  					*specialp = special
   278  					freespecial(y, unsafe.Pointer(p), size)
   279  				} else {
   280  					// This is profile record, but the object has finalizers (so kept alive).
   281  					// Keep special record.
   282  					specialp = &special.next
   283  					special = *specialp
   284  				}
   285  			}
   286  		} else {
   287  			// object is still live: keep special record
   288  			specialp = &special.next
   289  			special = *specialp
   290  		}
   291  	}
   292  
   293  	if debug.allocfreetrace != 0 || debug.clobberfree != 0 || raceenabled || msanenabled {
   294  		// Find all newly freed objects. This doesn't have to
   295  		// efficient; allocfreetrace has massive overhead.
   296  		mbits := s.markBitsForBase()
   297  		abits := s.allocBitsForIndex(0)
   298  		for i := uintptr(0); i < s.nelems; i++ {
   299  			if !mbits.isMarked() && (abits.index < s.freeindex || abits.isMarked()) {
   300  				x := s.base() + i*s.elemsize
   301  				if debug.allocfreetrace != 0 {
   302  					tracefree(unsafe.Pointer(x), size)
   303  				}
   304  				if debug.clobberfree != 0 {
   305  					clobberfree(unsafe.Pointer(x), size)
   306  				}
   307  				if raceenabled {
   308  					racefree(unsafe.Pointer(x), size)
   309  				}
   310  				if msanenabled {
   311  					msanfree(unsafe.Pointer(x), size)
   312  				}
   313  			}
   314  			mbits.advance()
   315  			abits.advance()
   316  		}
   317  	}
   318  
   319  	// Count the number of free objects in this span.
   320  	nalloc := uint16(s.countAlloc())
   321  	if spc.sizeclass() == 0 && nalloc == 0 {
   322  		s.needzero = 1
   323  		freeToHeap = true
   324  	}
   325  	nfreed := s.allocCount - nalloc
   326  	if nalloc > s.allocCount {
   327  		print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n")
   328  		throw("sweep increased allocation count")
   329  	}
   330  
   331  	s.allocCount = nalloc
   332  	wasempty := s.nextFreeIndex() == s.nelems
   333  	s.freeindex = 0 // reset allocation index to start of span.
   334  	if trace.enabled {
   335  		getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize
   336  	}
   337  
   338  	// gcmarkBits becomes the allocBits.
   339  	// get a fresh cleared gcmarkBits in preparation for next GC
   340  	s.allocBits = s.gcmarkBits
   341  	s.gcmarkBits = newMarkBits(s.nelems)
   342  
   343  	// Initialize alloc bits cache.
   344  	s.refillAllocCache(0)
   345  
   346  	// We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
   347  	// because of the potential for a concurrent free/SetFinalizer.
   348  	// But we need to set it before we make the span available for allocation
   349  	// (return it to heap or mcentral), because allocation code assumes that a
   350  	// span is already swept if available for allocation.
   351  	if freeToHeap || nfreed == 0 {
   352  		// The span must be in our exclusive ownership until we update sweepgen,
   353  		// check for potential races.
   354  		if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
   355  			print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
   356  			throw("mspan.sweep: bad span state after sweep")
   357  		}
   358  		// Serialization point.
   359  		// At this point the mark bits are cleared and allocation ready
   360  		// to go so release the span.
   361  		atomic.Store(&s.sweepgen, sweepgen)
   362  	}
   363  
   364  	if nfreed > 0 && spc.sizeclass() != 0 {
   365  		c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed)
   366  		res = mheap_.central[spc].mcentral.freeSpan(s, preserve, wasempty)
   367  		// mcentral.freeSpan updates sweepgen
   368  	} else if freeToHeap {
   369  		// Free large span to heap
   370  
   371  		// NOTE(rsc,dvyukov): The original implementation of efence
   372  		// in CL 22060046 used sysFree instead of sysFault, so that
   373  		// the operating system would eventually give the memory
   374  		// back to us again, so that an efence program could run
   375  		// longer without running out of memory. Unfortunately,
   376  		// calling sysFree here without any kind of adjustment of the
   377  		// heap data structures means that when the memory does
   378  		// come back to us, we have the wrong metadata for it, either in
   379  		// the mspan structures or in the garbage collection bitmap.
   380  		// Using sysFault here means that the program will run out of
   381  		// memory fairly quickly in efence mode, but at least it won't
   382  		// have mysterious crashes due to confused memory reuse.
   383  		// It should be possible to switch back to sysFree if we also
   384  		// implement and then call some kind of mheap.deleteSpan.
   385  		if debug.efence > 0 {
   386  			s.limit = 0 // prevent mlookup from finding this span
   387  			sysFault(unsafe.Pointer(s.base()), size)
   388  		} else {
   389  			mheap_.freeSpan(s)
   390  		}
   391  		c.local_nlargefree++
   392  		c.local_largefree += size
   393  		res = true
   394  	}
   395  	if !res {
   396  		// The span has been swept and is still in-use, so put
   397  		// it on the swept in-use list.
   398  		mheap_.sweepSpans[sweepgen/2%2].push(s)
   399  	}
   400  	return res
   401  }
   402  
   403  // deductSweepCredit deducts sweep credit for allocating a span of
   404  // size spanBytes. This must be performed *before* the span is
   405  // allocated to ensure the system has enough credit. If necessary, it
   406  // performs sweeping to prevent going in to debt. If the caller will
   407  // also sweep pages (e.g., for a large allocation), it can pass a
   408  // non-zero callerSweepPages to leave that many pages unswept.
   409  //
   410  // deductSweepCredit makes a worst-case assumption that all spanBytes
   411  // bytes of the ultimately allocated span will be available for object
   412  // allocation.
   413  //
   414  // deductSweepCredit is the core of the "proportional sweep" system.
   415  // It uses statistics gathered by the garbage collector to perform
   416  // enough sweeping so that all pages are swept during the concurrent
   417  // sweep phase between GC cycles.
   418  //
   419  // mheap_ must NOT be locked.
   420  func deductSweepCredit(spanBytes uintptr, callerSweepPages uintptr) {
   421  	if mheap_.sweepPagesPerByte == 0 {
   422  		// Proportional sweep is done or disabled.
   423  		return
   424  	}
   425  
   426  	if trace.enabled {
   427  		traceGCSweepStart()
   428  	}
   429  
   430  retry:
   431  	sweptBasis := atomic.Load64(&mheap_.pagesSweptBasis)
   432  
   433  	// Fix debt if necessary.
   434  	newHeapLive := uintptr(atomic.Load64(&memstats.heap_live)-mheap_.sweepHeapLiveBasis) + spanBytes
   435  	pagesTarget := int64(mheap_.sweepPagesPerByte*float64(newHeapLive)) - int64(callerSweepPages)
   436  	for pagesTarget > int64(atomic.Load64(&mheap_.pagesSwept)-sweptBasis) {
   437  		if sweepone() == ^uintptr(0) {
   438  			mheap_.sweepPagesPerByte = 0
   439  			break
   440  		}
   441  		if atomic.Load64(&mheap_.pagesSweptBasis) != sweptBasis {
   442  			// Sweep pacing changed. Recompute debt.
   443  			goto retry
   444  		}
   445  	}
   446  
   447  	if trace.enabled {
   448  		traceGCSweepDone()
   449  	}
   450  }
   451  
   452  // clobberfree sets the memory content at x to bad content, for debugging
   453  // purposes.
   454  func clobberfree(x unsafe.Pointer, size uintptr) {
   455  	// size (span.elemsize) is always a multiple of 4.
   456  	for i := uintptr(0); i < size; i += 4 {
   457  		*(*uint32)(add(x, i)) = 0xdeadbeef
   458  	}
   459  }
   460
View as plain text