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 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	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 s.state != mSpanInUse || s.sweepgen != sweepgen-1 {
   215			print("mspan.sweep: state=", s.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 s.state != mSpanInUse || s.sweepgen != sweepgen-1 {
   355				print("mspan.sweep: state=", s.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, true)
   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