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