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 s.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=", s.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  //TODO go:nowritebarrier
   207  func (s *mspan) sweep(preserve bool) bool {
   208  	// It's critical that we enter this function with preemption disabled,
   209  	// GC must not start while we are in the middle of this function.
   210  	_g_ := getg()
   211  	if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
   212  		throw("mspan.sweep: m is not locked")
   213  	}
   214  	sweepgen := mheap_.sweepgen
   215  	if s.state != mSpanInUse || s.sweepgen != sweepgen-1 {
   216  		print("mspan.sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
   217  		throw("mspan.sweep: bad span state")
   218  	}
   219  
   220  	if trace.enabled {
   221  		traceGCSweepSpan(s.npages * _PageSize)
   222  	}
   223  
   224  	atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages))
   225  
   226  	spc := s.spanclass
   227  	size := s.elemsize
   228  	res := false
   229  
   230  	c := _g_.m.mcache
   231  	freeToHeap := false
   232  
   233  	// The allocBits indicate which unmarked objects don't need to be
   234  	// processed since they were free at the end of the last GC cycle
   235  	// and were not allocated since then.
   236  	// If the allocBits index is >= s.freeindex and the bit
   237  	// is not marked then the object remains unallocated
   238  	// since the last GC.
   239  	// This situation is analogous to being on a freelist.
   240  
   241  	// Unlink & free special records for any objects we're about to free.
   242  	// Two complications here:
   243  	// 1. An object can have both finalizer and profile special records.
   244  	//    In such case we need to queue finalizer for execution,
   245  	//    mark the object as live and preserve the profile special.
   246  	// 2. A tiny object can have several finalizers setup for different offsets.
   247  	//    If such object is not marked, we need to queue all finalizers at once.
   248  	// Both 1 and 2 are possible at the same time.
   249  	specialp := &s.specials
   250  	special := *specialp
   251  	for special != nil {
   252  		// A finalizer can be set for an inner byte of an object, find object beginning.
   253  		objIndex := uintptr(special.offset) / size
   254  		p := s.base() + objIndex*size
   255  		mbits := s.markBitsForIndex(objIndex)
   256  		if !mbits.isMarked() {
   257  			// This object is not marked and has at least one special record.
   258  			// Pass 1: see if it has at least one finalizer.
   259  			hasFin := false
   260  			endOffset := p - s.base() + size
   261  			for tmp := special; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next {
   262  				if tmp.kind == _KindSpecialFinalizer {
   263  					// Stop freeing of object if it has a finalizer.
   264  					mbits.setMarkedNonAtomic()
   265  					hasFin = true
   266  					break
   267  				}
   268  			}
   269  			// Pass 2: queue all finalizers _or_ handle profile record.
   270  			for special != nil && uintptr(special.offset) < endOffset {
   271  				// Find the exact byte for which the special was setup
   272  				// (as opposed to object beginning).
   273  				p := s.base() + uintptr(special.offset)
   274  				if special.kind == _KindSpecialFinalizer || !hasFin {
   275  					// Splice out special record.
   276  					y := special
   277  					special = special.next
   278  					*specialp = special
   279  					freespecial(y, unsafe.Pointer(p), size)
   280  				} else {
   281  					// This is profile record, but the object has finalizers (so kept alive).
   282  					// Keep special record.
   283  					specialp = &special.next
   284  					special = *specialp
   285  				}
   286  			}
   287  		} else {
   288  			// object is still live: keep special record
   289  			specialp = &special.next
   290  			special = *specialp
   291  		}
   292  	}
   293  
   294  	if debug.allocfreetrace != 0 || debug.clobberfree != 0 || raceenabled || msanenabled {
   295  		// Find all newly freed objects. This doesn't have to
   296  		// efficient; allocfreetrace has massive overhead.
   297  		mbits := s.markBitsForBase()
   298  		abits := s.allocBitsForIndex(0)
   299  		for i := uintptr(0); i < s.nelems; i++ {
   300  			if !mbits.isMarked() && (abits.index < s.freeindex || abits.isMarked()) {
   301  				x := s.base() + i*s.elemsize
   302  				if debug.allocfreetrace != 0 {
   303  					tracefree(unsafe.Pointer(x), size)
   304  				}
   305  				if debug.clobberfree != 0 {
   306  					clobberfree(unsafe.Pointer(x), size)
   307  				}
   308  				if raceenabled {
   309  					racefree(unsafe.Pointer(x), size)
   310  				}
   311  				if msanenabled {
   312  					msanfree(unsafe.Pointer(x), size)
   313  				}
   314  			}
   315  			mbits.advance()
   316  			abits.advance()
   317  		}
   318  	}
   319  
   320  	// Count the number of free objects in this span.
   321  	nalloc := uint16(s.countAlloc())
   322  	if spc.sizeclass() == 0 && nalloc == 0 {
   323  		s.needzero = 1
   324  		freeToHeap = true
   325  	}
   326  	nfreed := s.allocCount - nalloc
   327  	if nalloc > s.allocCount {
   328  		print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n")
   329  		throw("sweep increased allocation count")
   330  	}
   331  
   332  	s.allocCount = nalloc
   333  	wasempty := s.nextFreeIndex() == s.nelems
   334  	s.freeindex = 0 // reset allocation index to start of span.
   335  	if trace.enabled {
   336  		getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize
   337  	}
   338  
   339  	// gcmarkBits becomes the allocBits.
   340  	// get a fresh cleared gcmarkBits in preparation for next GC
   341  	s.allocBits = s.gcmarkBits
   342  	s.gcmarkBits = newMarkBits(s.nelems)
   343  
   344  	// Initialize alloc bits cache.
   345  	s.refillAllocCache(0)
   346  
   347  	// We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
   348  	// because of the potential for a concurrent free/SetFinalizer.
   349  	// But we need to set it before we make the span available for allocation
   350  	// (return it to heap or mcentral), because allocation code assumes that a
   351  	// span is already swept if available for allocation.
   352  	if freeToHeap || nfreed == 0 {
   353  		// The span must be in our exclusive ownership until we update sweepgen,
   354  		// check for potential races.
   355  		if s.state != mSpanInUse || s.sweepgen != sweepgen-1 {
   356  			print("mspan.sweep: state=", s.state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
   357  			throw("mspan.sweep: bad span state after sweep")
   358  		}
   359  		// Serialization point.
   360  		// At this point the mark bits are cleared and allocation ready
   361  		// to go so release the span.
   362  		atomic.Store(&s.sweepgen, sweepgen)
   363  	}
   364  
   365  	if nfreed > 0 && spc.sizeclass() != 0 {
   366  		c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed)
   367  		res = mheap_.central[spc].mcentral.freeSpan(s, preserve, wasempty)
   368  		// mcentral.freeSpan updates sweepgen
   369  	} else if freeToHeap {
   370  		// Free large span to heap
   371  
   372  		// NOTE(rsc,dvyukov): The original implementation of efence
   373  		// in CL 22060046 used sysFree instead of sysFault, so that
   374  		// the operating system would eventually give the memory
   375  		// back to us again, so that an efence program could run
   376  		// longer without running out of memory. Unfortunately,
   377  		// calling sysFree here without any kind of adjustment of the
   378  		// heap data structures means that when the memory does
   379  		// come back to us, we have the wrong metadata for it, either in
   380  		// the mspan structures or in the garbage collection bitmap.
   381  		// Using sysFault here means that the program will run out of
   382  		// memory fairly quickly in efence mode, but at least it won't
   383  		// have mysterious crashes due to confused memory reuse.
   384  		// It should be possible to switch back to sysFree if we also
   385  		// implement and then call some kind of mheap.deleteSpan.
   386  		if debug.efence > 0 {
   387  			s.limit = 0 // prevent mlookup from finding this span
   388  			sysFault(unsafe.Pointer(s.base()), size)
   389  		} else {
   390  			mheap_.freeSpan(s, true)
   391  		}
   392  		c.local_nlargefree++
   393  		c.local_largefree += size
   394  		res = true
   395  	}
   396  	if !res {
   397  		// The span has been swept and is still in-use, so put
   398  		// it on the swept in-use list.
   399  		mheap_.sweepSpans[sweepgen/2%2].push(s)
   400  	}
   401  	return res
   402  }
   403  
   404  // deductSweepCredit deducts sweep credit for allocating a span of
   405  // size spanBytes. This must be performed *before* the span is
   406  // allocated to ensure the system has enough credit. If necessary, it
   407  // performs sweeping to prevent going in to debt. If the caller will
   408  // also sweep pages (e.g., for a large allocation), it can pass a
   409  // non-zero callerSweepPages to leave that many pages unswept.
   410  //
   411  // deductSweepCredit makes a worst-case assumption that all spanBytes
   412  // bytes of the ultimately allocated span will be available for object
   413  // allocation.
   414  //
   415  // deductSweepCredit is the core of the "proportional sweep" system.
   416  // It uses statistics gathered by the garbage collector to perform
   417  // enough sweeping so that all pages are swept during the concurrent
   418  // sweep phase between GC cycles.
   419  //
   420  // mheap_ must NOT be locked.
   421  func deductSweepCredit(spanBytes uintptr, callerSweepPages uintptr) {
   422  	if mheap_.sweepPagesPerByte == 0 {
   423  		// Proportional sweep is done or disabled.
   424  		return
   425  	}
   426  
   427  	if trace.enabled {
   428  		traceGCSweepStart()
   429  	}
   430  
   431  retry:
   432  	sweptBasis := atomic.Load64(&mheap_.pagesSweptBasis)
   433  
   434  	// Fix debt if necessary.
   435  	newHeapLive := uintptr(atomic.Load64(&memstats.heap_live)-mheap_.sweepHeapLiveBasis) + spanBytes
   436  	pagesTarget := int64(mheap_.sweepPagesPerByte*float64(newHeapLive)) - int64(callerSweepPages)
   437  	for pagesTarget > int64(atomic.Load64(&mheap_.pagesSwept)-sweptBasis) {
   438  		if sweepone() == ^uintptr(0) {
   439  			mheap_.sweepPagesPerByte = 0
   440  			break
   441  		}
   442  		if atomic.Load64(&mheap_.pagesSweptBasis) != sweptBasis {
   443  			// Sweep pacing changed. Recompute debt.
   444  			goto retry
   445  		}
   446  	}
   447  
   448  	if trace.enabled {
   449  		traceGCSweepDone()
   450  	}
   451  }
   452  
   453  // clobberfree sets the memory content at x to bad content, for debugging
   454  // purposes.
   455  func clobberfree(x unsafe.Pointer, size uintptr) {
   456  	// size (span.elemsize) is always a multiple of 4.
   457  	for i := uintptr(0); i < size; i += 4 {
   458  		*(*uint32)(add(x, i)) = 0xdeadbeef
   459  	}
   460  }
   461
View as plain text