...
Run Format

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

View as plain text