Source file src/runtime/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, which looks at all the mcentral lists.
    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  	// centralIndex is the current unswept span class.
    45  	// It represents an index into the mcentral span
    46  	// sets. Accessed and updated via its load and
    47  	// update methods. Not protected by a lock.
    48  	//
    49  	// Reset at mark termination.
    50  	// Used by mheap.nextSpanForSweep.
    51  	centralIndex sweepClass
    52  }
    53  
    54  // sweepClass is a spanClass and one bit to represent whether we're currently
    55  // sweeping partial or full spans.
    56  type sweepClass uint32
    57  
    58  const (
    59  	numSweepClasses            = numSpanClasses * 2
    60  	sweepClassDone  sweepClass = sweepClass(^uint32(0))
    61  )
    62  
    63  func (s *sweepClass) load() sweepClass {
    64  	return sweepClass(atomic.Load((*uint32)(s)))
    65  }
    66  
    67  func (s *sweepClass) update(sNew sweepClass) {
    68  	// Only update *s if its current value is less than sNew,
    69  	// since *s increases monotonically.
    70  	sOld := s.load()
    71  	for sOld < sNew && !atomic.Cas((*uint32)(s), uint32(sOld), uint32(sNew)) {
    72  		sOld = s.load()
    73  	}
    74  	// TODO(mknyszek): This isn't the only place we have
    75  	// an atomic monotonically increasing counter. It would
    76  	// be nice to have an "atomic max" which is just implemented
    77  	// as the above on most architectures. Some architectures
    78  	// like RISC-V however have native support for an atomic max.
    79  }
    80  
    81  func (s *sweepClass) clear() {
    82  	atomic.Store((*uint32)(s), 0)
    83  }
    84  
    85  // split returns the underlying span class as well as
    86  // whether we're interested in the full or partial
    87  // unswept lists for that class, indicated as a boolean
    88  // (true means "full").
    89  func (s sweepClass) split() (spc spanClass, full bool) {
    90  	return spanClass(s >> 1), s&1 == 0
    91  }
    92  
    93  // nextSpanForSweep finds and pops the next span for sweeping from the
    94  // central sweep buffers. It returns ownership of the span to the caller.
    95  // Returns nil if no such span exists.
    96  func (h *mheap) nextSpanForSweep() *mspan {
    97  	sg := h.sweepgen
    98  	for sc := sweep.centralIndex.load(); sc < numSweepClasses; sc++ {
    99  		spc, full := sc.split()
   100  		c := &h.central[spc].mcentral
   101  		var s *mspan
   102  		if full {
   103  			s = c.fullUnswept(sg).pop()
   104  		} else {
   105  			s = c.partialUnswept(sg).pop()
   106  		}
   107  		if s != nil {
   108  			// Write down that we found something so future sweepers
   109  			// can start from here.
   110  			sweep.centralIndex.update(sc)
   111  			return s
   112  		}
   113  	}
   114  	// Write down that we found nothing.
   115  	sweep.centralIndex.update(sweepClassDone)
   116  	return nil
   117  }
   118  
   119  // finishsweep_m ensures that all spans are swept.
   120  //
   121  // The world must be stopped. This ensures there are no sweeps in
   122  // progress.
   123  //
   124  //go:nowritebarrier
   125  func finishsweep_m() {
   126  	// Sweeping must be complete before marking commences, so
   127  	// sweep any unswept spans. If this is a concurrent GC, there
   128  	// shouldn't be any spans left to sweep, so this should finish
   129  	// instantly. If GC was forced before the concurrent sweep
   130  	// finished, there may be spans to sweep.
   131  	for sweepone() != ^uintptr(0) {
   132  		sweep.npausesweep++
   133  	}
   134  
   135  	if go115NewMCentralImpl {
   136  		// Reset all the unswept buffers, which should be empty.
   137  		// Do this in sweep termination as opposed to mark termination
   138  		// so that we can catch unswept spans and reclaim blocks as
   139  		// soon as possible.
   140  		sg := mheap_.sweepgen
   141  		for i := range mheap_.central {
   142  			c := &mheap_.central[i].mcentral
   143  			c.partialUnswept(sg).reset()
   144  			c.fullUnswept(sg).reset()
   145  		}
   146  	}
   147  
   148  	// Sweeping is done, so if the scavenger isn't already awake,
   149  	// wake it up. There's definitely work for it to do at this
   150  	// point.
   151  	wakeScavenger()
   152  
   153  	nextMarkBitArenaEpoch()
   154  }
   155  
   156  func bgsweep(c chan int) {
   157  	sweep.g = getg()
   158  
   159  	lockInit(&sweep.lock, lockRankSweep)
   160  	lock(&sweep.lock)
   161  	sweep.parked = true
   162  	c <- 1
   163  	goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1)
   164  
   165  	for {
   166  		for sweepone() != ^uintptr(0) {
   167  			sweep.nbgsweep++
   168  			Gosched()
   169  		}
   170  		for freeSomeWbufs(true) {
   171  			Gosched()
   172  		}
   173  		lock(&sweep.lock)
   174  		if !isSweepDone() {
   175  			// This can happen if a GC runs between
   176  			// gosweepone returning ^0 above
   177  			// and the lock being acquired.
   178  			unlock(&sweep.lock)
   179  			continue
   180  		}
   181  		sweep.parked = true
   182  		goparkunlock(&sweep.lock, waitReasonGCSweepWait, traceEvGoBlock, 1)
   183  	}
   184  }
   185  
   186  // sweepone sweeps some unswept heap span and returns the number of pages returned
   187  // to the heap, or ^uintptr(0) if there was nothing to sweep.
   188  func sweepone() uintptr {
   189  	_g_ := getg()
   190  	sweepRatio := mheap_.sweepPagesPerByte // For debugging
   191  
   192  	// increment locks to ensure that the goroutine is not preempted
   193  	// in the middle of sweep thus leaving the span in an inconsistent state for next GC
   194  	_g_.m.locks++
   195  	if atomic.Load(&mheap_.sweepdone) != 0 {
   196  		_g_.m.locks--
   197  		return ^uintptr(0)
   198  	}
   199  	atomic.Xadd(&mheap_.sweepers, +1)
   200  
   201  	// Find a span to sweep.
   202  	var s *mspan
   203  	sg := mheap_.sweepgen
   204  	for {
   205  		if go115NewMCentralImpl {
   206  			s = mheap_.nextSpanForSweep()
   207  		} else {
   208  			s = mheap_.sweepSpans[1-sg/2%2].pop()
   209  		}
   210  		if s == nil {
   211  			atomic.Store(&mheap_.sweepdone, 1)
   212  			break
   213  		}
   214  		if state := s.state.get(); state != mSpanInUse {
   215  			// This can happen if direct sweeping already
   216  			// swept this span, but in that case the sweep
   217  			// generation should always be up-to-date.
   218  			if !(s.sweepgen == sg || s.sweepgen == sg+3) {
   219  				print("runtime: bad span s.state=", state, " s.sweepgen=", s.sweepgen, " sweepgen=", sg, "\n")
   220  				throw("non in-use span in unswept list")
   221  			}
   222  			continue
   223  		}
   224  		if s.sweepgen == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
   225  			break
   226  		}
   227  	}
   228  
   229  	// Sweep the span we found.
   230  	npages := ^uintptr(0)
   231  	if s != nil {
   232  		npages = s.npages
   233  		if s.sweep(false) {
   234  			// Whole span was freed. Count it toward the
   235  			// page reclaimer credit since these pages can
   236  			// now be used for span allocation.
   237  			atomic.Xadduintptr(&mheap_.reclaimCredit, npages)
   238  		} else {
   239  			// Span is still in-use, so this returned no
   240  			// pages to the heap and the span needs to
   241  			// move to the swept in-use list.
   242  			npages = 0
   243  		}
   244  	}
   245  
   246  	// Decrement the number of active sweepers and if this is the
   247  	// last one print trace information.
   248  	if atomic.Xadd(&mheap_.sweepers, -1) == 0 && atomic.Load(&mheap_.sweepdone) != 0 {
   249  		// Since the sweeper is done, move the scavenge gen forward (signalling
   250  		// that there's new work to do) and wake the scavenger.
   251  		//
   252  		// The scavenger is signaled by the last sweeper because once
   253  		// sweeping is done, we will definitely have useful work for
   254  		// the scavenger to do, since the scavenger only runs over the
   255  		// heap once per GC cyle. This update is not done during sweep
   256  		// termination because in some cases there may be a long delay
   257  		// between sweep done and sweep termination (e.g. not enough
   258  		// allocations to trigger a GC) which would be nice to fill in
   259  		// with scavenging work.
   260  		systemstack(func() {
   261  			lock(&mheap_.lock)
   262  			mheap_.pages.scavengeStartGen()
   263  			unlock(&mheap_.lock)
   264  		})
   265  		// Since we might sweep in an allocation path, it's not possible
   266  		// for us to wake the scavenger directly via wakeScavenger, since
   267  		// it could allocate. Ask sysmon to do it for us instead.
   268  		readyForScavenger()
   269  
   270  		if debug.gcpacertrace > 0 {
   271  			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")
   272  		}
   273  	}
   274  	_g_.m.locks--
   275  	return npages
   276  }
   277  
   278  // isSweepDone reports whether all spans are swept or currently being swept.
   279  //
   280  // Note that this condition may transition from false to true at any
   281  // time as the sweeper runs. It may transition from true to false if a
   282  // GC runs; to prevent that the caller must be non-preemptible or must
   283  // somehow block GC progress.
   284  func isSweepDone() bool {
   285  	return mheap_.sweepdone != 0
   286  }
   287  
   288  // Returns only when span s has been swept.
   289  //go:nowritebarrier
   290  func (s *mspan) ensureSwept() {
   291  	// Caller must disable preemption.
   292  	// Otherwise when this function returns the span can become unswept again
   293  	// (if GC is triggered on another goroutine).
   294  	_g_ := getg()
   295  	if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
   296  		throw("mspan.ensureSwept: m is not locked")
   297  	}
   298  
   299  	sg := mheap_.sweepgen
   300  	spangen := atomic.Load(&s.sweepgen)
   301  	if spangen == sg || spangen == sg+3 {
   302  		return
   303  	}
   304  	// The caller must be sure that the span is a mSpanInUse span.
   305  	if atomic.Cas(&s.sweepgen, sg-2, sg-1) {
   306  		s.sweep(false)
   307  		return
   308  	}
   309  	// unfortunate condition, and we don't have efficient means to wait
   310  	for {
   311  		spangen := atomic.Load(&s.sweepgen)
   312  		if spangen == sg || spangen == sg+3 {
   313  			break
   314  		}
   315  		osyield()
   316  	}
   317  }
   318  
   319  // Sweep frees or collects finalizers for blocks not marked in the mark phase.
   320  // It clears the mark bits in preparation for the next GC round.
   321  // Returns true if the span was returned to heap.
   322  // If preserve=true, don't return it to heap nor relink in mcentral lists;
   323  // caller takes care of it.
   324  func (s *mspan) sweep(preserve bool) bool {
   325  	if !go115NewMCentralImpl {
   326  		return s.oldSweep(preserve)
   327  	}
   328  	// It's critical that we enter this function with preemption disabled,
   329  	// GC must not start while we are in the middle of this function.
   330  	_g_ := getg()
   331  	if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
   332  		throw("mspan.sweep: m is not locked")
   333  	}
   334  	sweepgen := mheap_.sweepgen
   335  	if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
   336  		print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
   337  		throw("mspan.sweep: bad span state")
   338  	}
   339  
   340  	if trace.enabled {
   341  		traceGCSweepSpan(s.npages * _PageSize)
   342  	}
   343  
   344  	atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages))
   345  
   346  	spc := s.spanclass
   347  	size := s.elemsize
   348  
   349  	c := _g_.m.p.ptr().mcache
   350  
   351  	// The allocBits indicate which unmarked objects don't need to be
   352  	// processed since they were free at the end of the last GC cycle
   353  	// and were not allocated since then.
   354  	// If the allocBits index is >= s.freeindex and the bit
   355  	// is not marked then the object remains unallocated
   356  	// since the last GC.
   357  	// This situation is analogous to being on a freelist.
   358  
   359  	// Unlink & free special records for any objects we're about to free.
   360  	// Two complications here:
   361  	// 1. An object can have both finalizer and profile special records.
   362  	//    In such case we need to queue finalizer for execution,
   363  	//    mark the object as live and preserve the profile special.
   364  	// 2. A tiny object can have several finalizers setup for different offsets.
   365  	//    If such object is not marked, we need to queue all finalizers at once.
   366  	// Both 1 and 2 are possible at the same time.
   367  	hadSpecials := s.specials != nil
   368  	specialp := &s.specials
   369  	special := *specialp
   370  	for special != nil {
   371  		// A finalizer can be set for an inner byte of an object, find object beginning.
   372  		objIndex := uintptr(special.offset) / size
   373  		p := s.base() + objIndex*size
   374  		mbits := s.markBitsForIndex(objIndex)
   375  		if !mbits.isMarked() {
   376  			// This object is not marked and has at least one special record.
   377  			// Pass 1: see if it has at least one finalizer.
   378  			hasFin := false
   379  			endOffset := p - s.base() + size
   380  			for tmp := special; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next {
   381  				if tmp.kind == _KindSpecialFinalizer {
   382  					// Stop freeing of object if it has a finalizer.
   383  					mbits.setMarkedNonAtomic()
   384  					hasFin = true
   385  					break
   386  				}
   387  			}
   388  			// Pass 2: queue all finalizers _or_ handle profile record.
   389  			for special != nil && uintptr(special.offset) < endOffset {
   390  				// Find the exact byte for which the special was setup
   391  				// (as opposed to object beginning).
   392  				p := s.base() + uintptr(special.offset)
   393  				if special.kind == _KindSpecialFinalizer || !hasFin {
   394  					// Splice out special record.
   395  					y := special
   396  					special = special.next
   397  					*specialp = special
   398  					freespecial(y, unsafe.Pointer(p), size)
   399  				} else {
   400  					// This is profile record, but the object has finalizers (so kept alive).
   401  					// Keep special record.
   402  					specialp = &special.next
   403  					special = *specialp
   404  				}
   405  			}
   406  		} else {
   407  			// object is still live: keep special record
   408  			specialp = &special.next
   409  			special = *specialp
   410  		}
   411  	}
   412  	if hadSpecials && s.specials == nil {
   413  		spanHasNoSpecials(s)
   414  	}
   415  
   416  	if debug.allocfreetrace != 0 || debug.clobberfree != 0 || raceenabled || msanenabled {
   417  		// Find all newly freed objects. This doesn't have to
   418  		// efficient; allocfreetrace has massive overhead.
   419  		mbits := s.markBitsForBase()
   420  		abits := s.allocBitsForIndex(0)
   421  		for i := uintptr(0); i < s.nelems; i++ {
   422  			if !mbits.isMarked() && (abits.index < s.freeindex || abits.isMarked()) {
   423  				x := s.base() + i*s.elemsize
   424  				if debug.allocfreetrace != 0 {
   425  					tracefree(unsafe.Pointer(x), size)
   426  				}
   427  				if debug.clobberfree != 0 {
   428  					clobberfree(unsafe.Pointer(x), size)
   429  				}
   430  				if raceenabled {
   431  					racefree(unsafe.Pointer(x), size)
   432  				}
   433  				if msanenabled {
   434  					msanfree(unsafe.Pointer(x), size)
   435  				}
   436  			}
   437  			mbits.advance()
   438  			abits.advance()
   439  		}
   440  	}
   441  
   442  	// Check for zombie objects.
   443  	if s.freeindex < s.nelems {
   444  		// Everything < freeindex is allocated and hence
   445  		// cannot be zombies.
   446  		//
   447  		// Check the first bitmap byte, where we have to be
   448  		// careful with freeindex.
   449  		obj := s.freeindex
   450  		if (*s.gcmarkBits.bytep(obj / 8)&^*s.allocBits.bytep(obj / 8))>>(obj%8) != 0 {
   451  			s.reportZombies()
   452  		}
   453  		// Check remaining bytes.
   454  		for i := obj/8 + 1; i < divRoundUp(s.nelems, 8); i++ {
   455  			if *s.gcmarkBits.bytep(i)&^*s.allocBits.bytep(i) != 0 {
   456  				s.reportZombies()
   457  			}
   458  		}
   459  	}
   460  
   461  	// Count the number of free objects in this span.
   462  	nalloc := uint16(s.countAlloc())
   463  	nfreed := s.allocCount - nalloc
   464  	if nalloc > s.allocCount {
   465  		// The zombie check above should have caught this in
   466  		// more detail.
   467  		print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n")
   468  		throw("sweep increased allocation count")
   469  	}
   470  
   471  	s.allocCount = nalloc
   472  	s.freeindex = 0 // reset allocation index to start of span.
   473  	if trace.enabled {
   474  		getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize
   475  	}
   476  
   477  	// gcmarkBits becomes the allocBits.
   478  	// get a fresh cleared gcmarkBits in preparation for next GC
   479  	s.allocBits = s.gcmarkBits
   480  	s.gcmarkBits = newMarkBits(s.nelems)
   481  
   482  	// Initialize alloc bits cache.
   483  	s.refillAllocCache(0)
   484  
   485  	// The span must be in our exclusive ownership until we update sweepgen,
   486  	// check for potential races.
   487  	if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
   488  		print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
   489  		throw("mspan.sweep: bad span state after sweep")
   490  	}
   491  	if s.sweepgen == sweepgen+1 || s.sweepgen == sweepgen+3 {
   492  		throw("swept cached span")
   493  	}
   494  
   495  	// We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
   496  	// because of the potential for a concurrent free/SetFinalizer.
   497  	//
   498  	// But we need to set it before we make the span available for allocation
   499  	// (return it to heap or mcentral), because allocation code assumes that a
   500  	// span is already swept if available for allocation.
   501  	//
   502  	// Serialization point.
   503  	// At this point the mark bits are cleared and allocation ready
   504  	// to go so release the span.
   505  	atomic.Store(&s.sweepgen, sweepgen)
   506  
   507  	if spc.sizeclass() != 0 {
   508  		// Handle spans for small objects.
   509  		if nfreed > 0 {
   510  			// Only mark the span as needing zeroing if we've freed any
   511  			// objects, because a fresh span that had been allocated into,
   512  			// wasn't totally filled, but then swept, still has all of its
   513  			// free slots zeroed.
   514  			s.needzero = 1
   515  			c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed)
   516  		}
   517  		if !preserve {
   518  			// The caller may not have removed this span from whatever
   519  			// unswept set its on but taken ownership of the span for
   520  			// sweeping by updating sweepgen. If this span still is in
   521  			// an unswept set, then the mcentral will pop it off the
   522  			// set, check its sweepgen, and ignore it.
   523  			if nalloc == 0 {
   524  				// Free totally free span directly back to the heap.
   525  				mheap_.freeSpan(s)
   526  				return true
   527  			}
   528  			// Return span back to the right mcentral list.
   529  			if uintptr(nalloc) == s.nelems {
   530  				mheap_.central[spc].mcentral.fullSwept(sweepgen).push(s)
   531  			} else {
   532  				mheap_.central[spc].mcentral.partialSwept(sweepgen).push(s)
   533  			}
   534  		}
   535  	} else if !preserve {
   536  		// Handle spans for large objects.
   537  		if nfreed != 0 {
   538  			// Free large object span to heap.
   539  
   540  			// NOTE(rsc,dvyukov): The original implementation of efence
   541  			// in CL 22060046 used sysFree instead of sysFault, so that
   542  			// the operating system would eventually give the memory
   543  			// back to us again, so that an efence program could run
   544  			// longer without running out of memory. Unfortunately,
   545  			// calling sysFree here without any kind of adjustment of the
   546  			// heap data structures means that when the memory does
   547  			// come back to us, we have the wrong metadata for it, either in
   548  			// the mspan structures or in the garbage collection bitmap.
   549  			// Using sysFault here means that the program will run out of
   550  			// memory fairly quickly in efence mode, but at least it won't
   551  			// have mysterious crashes due to confused memory reuse.
   552  			// It should be possible to switch back to sysFree if we also
   553  			// implement and then call some kind of mheap.deleteSpan.
   554  			if debug.efence > 0 {
   555  				s.limit = 0 // prevent mlookup from finding this span
   556  				sysFault(unsafe.Pointer(s.base()), size)
   557  			} else {
   558  				mheap_.freeSpan(s)
   559  			}
   560  			c.local_nlargefree++
   561  			c.local_largefree += size
   562  			return true
   563  		}
   564  
   565  		// Add a large span directly onto the full+swept list.
   566  		mheap_.central[spc].mcentral.fullSwept(sweepgen).push(s)
   567  	}
   568  	return false
   569  }
   570  
   571  // Sweep frees or collects finalizers for blocks not marked in the mark phase.
   572  // It clears the mark bits in preparation for the next GC round.
   573  // Returns true if the span was returned to heap.
   574  // If preserve=true, don't return it to heap nor relink in mcentral lists;
   575  // caller takes care of it.
   576  //
   577  // For !go115NewMCentralImpl.
   578  func (s *mspan) oldSweep(preserve bool) bool {
   579  	// It's critical that we enter this function with preemption disabled,
   580  	// GC must not start while we are in the middle of this function.
   581  	_g_ := getg()
   582  	if _g_.m.locks == 0 && _g_.m.mallocing == 0 && _g_ != _g_.m.g0 {
   583  		throw("mspan.sweep: m is not locked")
   584  	}
   585  	sweepgen := mheap_.sweepgen
   586  	if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
   587  		print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
   588  		throw("mspan.sweep: bad span state")
   589  	}
   590  
   591  	if trace.enabled {
   592  		traceGCSweepSpan(s.npages * _PageSize)
   593  	}
   594  
   595  	atomic.Xadd64(&mheap_.pagesSwept, int64(s.npages))
   596  
   597  	spc := s.spanclass
   598  	size := s.elemsize
   599  	res := false
   600  
   601  	c := _g_.m.p.ptr().mcache
   602  	freeToHeap := false
   603  
   604  	// The allocBits indicate which unmarked objects don't need to be
   605  	// processed since they were free at the end of the last GC cycle
   606  	// and were not allocated since then.
   607  	// If the allocBits index is >= s.freeindex and the bit
   608  	// is not marked then the object remains unallocated
   609  	// since the last GC.
   610  	// This situation is analogous to being on a freelist.
   611  
   612  	// Unlink & free special records for any objects we're about to free.
   613  	// Two complications here:
   614  	// 1. An object can have both finalizer and profile special records.
   615  	//    In such case we need to queue finalizer for execution,
   616  	//    mark the object as live and preserve the profile special.
   617  	// 2. A tiny object can have several finalizers setup for different offsets.
   618  	//    If such object is not marked, we need to queue all finalizers at once.
   619  	// Both 1 and 2 are possible at the same time.
   620  	hadSpecials := s.specials != nil
   621  	specialp := &s.specials
   622  	special := *specialp
   623  	for special != nil {
   624  		// A finalizer can be set for an inner byte of an object, find object beginning.
   625  		objIndex := uintptr(special.offset) / size
   626  		p := s.base() + objIndex*size
   627  		mbits := s.markBitsForIndex(objIndex)
   628  		if !mbits.isMarked() {
   629  			// This object is not marked and has at least one special record.
   630  			// Pass 1: see if it has at least one finalizer.
   631  			hasFin := false
   632  			endOffset := p - s.base() + size
   633  			for tmp := special; tmp != nil && uintptr(tmp.offset) < endOffset; tmp = tmp.next {
   634  				if tmp.kind == _KindSpecialFinalizer {
   635  					// Stop freeing of object if it has a finalizer.
   636  					mbits.setMarkedNonAtomic()
   637  					hasFin = true
   638  					break
   639  				}
   640  			}
   641  			// Pass 2: queue all finalizers _or_ handle profile record.
   642  			for special != nil && uintptr(special.offset) < endOffset {
   643  				// Find the exact byte for which the special was setup
   644  				// (as opposed to object beginning).
   645  				p := s.base() + uintptr(special.offset)
   646  				if special.kind == _KindSpecialFinalizer || !hasFin {
   647  					// Splice out special record.
   648  					y := special
   649  					special = special.next
   650  					*specialp = special
   651  					freespecial(y, unsafe.Pointer(p), size)
   652  				} else {
   653  					// This is profile record, but the object has finalizers (so kept alive).
   654  					// Keep special record.
   655  					specialp = &special.next
   656  					special = *specialp
   657  				}
   658  			}
   659  		} else {
   660  			// object is still live: keep special record
   661  			specialp = &special.next
   662  			special = *specialp
   663  		}
   664  	}
   665  	if go115NewMarkrootSpans && hadSpecials && s.specials == nil {
   666  		spanHasNoSpecials(s)
   667  	}
   668  
   669  	if debug.allocfreetrace != 0 || debug.clobberfree != 0 || raceenabled || msanenabled {
   670  		// Find all newly freed objects. This doesn't have to
   671  		// efficient; allocfreetrace has massive overhead.
   672  		mbits := s.markBitsForBase()
   673  		abits := s.allocBitsForIndex(0)
   674  		for i := uintptr(0); i < s.nelems; i++ {
   675  			if !mbits.isMarked() && (abits.index < s.freeindex || abits.isMarked()) {
   676  				x := s.base() + i*s.elemsize
   677  				if debug.allocfreetrace != 0 {
   678  					tracefree(unsafe.Pointer(x), size)
   679  				}
   680  				if debug.clobberfree != 0 {
   681  					clobberfree(unsafe.Pointer(x), size)
   682  				}
   683  				if raceenabled {
   684  					racefree(unsafe.Pointer(x), size)
   685  				}
   686  				if msanenabled {
   687  					msanfree(unsafe.Pointer(x), size)
   688  				}
   689  			}
   690  			mbits.advance()
   691  			abits.advance()
   692  		}
   693  	}
   694  
   695  	// Count the number of free objects in this span.
   696  	nalloc := uint16(s.countAlloc())
   697  	if spc.sizeclass() == 0 && nalloc == 0 {
   698  		s.needzero = 1
   699  		freeToHeap = true
   700  	}
   701  	nfreed := s.allocCount - nalloc
   702  	if nalloc > s.allocCount {
   703  		print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n")
   704  		throw("sweep increased allocation count")
   705  	}
   706  
   707  	s.allocCount = nalloc
   708  	wasempty := s.nextFreeIndex() == s.nelems
   709  	s.freeindex = 0 // reset allocation index to start of span.
   710  	if trace.enabled {
   711  		getg().m.p.ptr().traceReclaimed += uintptr(nfreed) * s.elemsize
   712  	}
   713  
   714  	// gcmarkBits becomes the allocBits.
   715  	// get a fresh cleared gcmarkBits in preparation for next GC
   716  	s.allocBits = s.gcmarkBits
   717  	s.gcmarkBits = newMarkBits(s.nelems)
   718  
   719  	// Initialize alloc bits cache.
   720  	s.refillAllocCache(0)
   721  
   722  	// We need to set s.sweepgen = h.sweepgen only when all blocks are swept,
   723  	// because of the potential for a concurrent free/SetFinalizer.
   724  	// But we need to set it before we make the span available for allocation
   725  	// (return it to heap or mcentral), because allocation code assumes that a
   726  	// span is already swept if available for allocation.
   727  	if freeToHeap || nfreed == 0 {
   728  		// The span must be in our exclusive ownership until we update sweepgen,
   729  		// check for potential races.
   730  		if state := s.state.get(); state != mSpanInUse || s.sweepgen != sweepgen-1 {
   731  			print("mspan.sweep: state=", state, " sweepgen=", s.sweepgen, " mheap.sweepgen=", sweepgen, "\n")
   732  			throw("mspan.sweep: bad span state after sweep")
   733  		}
   734  		// Serialization point.
   735  		// At this point the mark bits are cleared and allocation ready
   736  		// to go so release the span.
   737  		atomic.Store(&s.sweepgen, sweepgen)
   738  	}
   739  
   740  	if nfreed > 0 && spc.sizeclass() != 0 {
   741  		c.local_nsmallfree[spc.sizeclass()] += uintptr(nfreed)
   742  		res = mheap_.central[spc].mcentral.freeSpan(s, preserve, wasempty)
   743  		// mcentral.freeSpan updates sweepgen
   744  	} else if freeToHeap {
   745  		// Free large span to heap
   746  
   747  		// NOTE(rsc,dvyukov): The original implementation of efence
   748  		// in CL 22060046 used sysFree instead of sysFault, so that
   749  		// the operating system would eventually give the memory
   750  		// back to us again, so that an efence program could run
   751  		// longer without running out of memory. Unfortunately,
   752  		// calling sysFree here without any kind of adjustment of the
   753  		// heap data structures means that when the memory does
   754  		// come back to us, we have the wrong metadata for it, either in
   755  		// the mspan structures or in the garbage collection bitmap.
   756  		// Using sysFault here means that the program will run out of
   757  		// memory fairly quickly in efence mode, but at least it won't
   758  		// have mysterious crashes due to confused memory reuse.
   759  		// It should be possible to switch back to sysFree if we also
   760  		// implement and then call some kind of mheap.deleteSpan.
   761  		if debug.efence > 0 {
   762  			s.limit = 0 // prevent mlookup from finding this span
   763  			sysFault(unsafe.Pointer(s.base()), size)
   764  		} else {
   765  			mheap_.freeSpan(s)
   766  		}
   767  		c.local_nlargefree++
   768  		c.local_largefree += size
   769  		res = true
   770  	}
   771  	if !res {
   772  		// The span has been swept and is still in-use, so put
   773  		// it on the swept in-use list.
   774  		mheap_.sweepSpans[sweepgen/2%2].push(s)
   775  	}
   776  	return res
   777  }
   778  
   779  // reportZombies reports any marked but free objects in s and throws.
   780  //
   781  // This generally means one of the following:
   782  //
   783  // 1. User code converted a pointer to a uintptr and then back
   784  // unsafely, and a GC ran while the uintptr was the only reference to
   785  // an object.
   786  //
   787  // 2. User code (or a compiler bug) constructed a bad pointer that
   788  // points to a free slot, often a past-the-end pointer.
   789  //
   790  // 3. The GC two cycles ago missed a pointer and freed a live object,
   791  // but it was still live in the last cycle, so this GC cycle found a
   792  // pointer to that object and marked it.
   793  func (s *mspan) reportZombies() {
   794  	printlock()
   795  	print("runtime: marked free object in span ", s, ", elemsize=", s.elemsize, " freeindex=", s.freeindex, " (bad use of unsafe.Pointer? try -d=checkptr)\n")
   796  	mbits := s.markBitsForBase()
   797  	abits := s.allocBitsForIndex(0)
   798  	for i := uintptr(0); i < s.nelems; i++ {
   799  		addr := s.base() + i*s.elemsize
   800  		print(hex(addr))
   801  		alloc := i < s.freeindex || abits.isMarked()
   802  		if alloc {
   803  			print(" alloc")
   804  		} else {
   805  			print(" free ")
   806  		}
   807  		if mbits.isMarked() {
   808  			print(" marked  ")
   809  		} else {
   810  			print(" unmarked")
   811  		}
   812  		zombie := mbits.isMarked() && !alloc
   813  		if zombie {
   814  			print(" zombie")
   815  		}
   816  		print("\n")
   817  		if zombie {
   818  			length := s.elemsize
   819  			if length > 1024 {
   820  				length = 1024
   821  			}
   822  			hexdumpWords(addr, addr+length, nil)
   823  		}
   824  		mbits.advance()
   825  		abits.advance()
   826  	}
   827  	throw("found pointer to free object")
   828  }
   829  
   830  // deductSweepCredit deducts sweep credit for allocating a span of
   831  // size spanBytes. This must be performed *before* the span is
   832  // allocated to ensure the system has enough credit. If necessary, it
   833  // performs sweeping to prevent going in to debt. If the caller will
   834  // also sweep pages (e.g., for a large allocation), it can pass a
   835  // non-zero callerSweepPages to leave that many pages unswept.
   836  //
   837  // deductSweepCredit makes a worst-case assumption that all spanBytes
   838  // bytes of the ultimately allocated span will be available for object
   839  // allocation.
   840  //
   841  // deductSweepCredit is the core of the "proportional sweep" system.
   842  // It uses statistics gathered by the garbage collector to perform
   843  // enough sweeping so that all pages are swept during the concurrent
   844  // sweep phase between GC cycles.
   845  //
   846  // mheap_ must NOT be locked.
   847  func deductSweepCredit(spanBytes uintptr, callerSweepPages uintptr) {
   848  	if mheap_.sweepPagesPerByte == 0 {
   849  		// Proportional sweep is done or disabled.
   850  		return
   851  	}
   852  
   853  	if trace.enabled {
   854  		traceGCSweepStart()
   855  	}
   856  
   857  retry:
   858  	sweptBasis := atomic.Load64(&mheap_.pagesSweptBasis)
   859  
   860  	// Fix debt if necessary.
   861  	newHeapLive := uintptr(atomic.Load64(&memstats.heap_live)-mheap_.sweepHeapLiveBasis) + spanBytes
   862  	pagesTarget := int64(mheap_.sweepPagesPerByte*float64(newHeapLive)) - int64(callerSweepPages)
   863  	for pagesTarget > int64(atomic.Load64(&mheap_.pagesSwept)-sweptBasis) {
   864  		if sweepone() == ^uintptr(0) {
   865  			mheap_.sweepPagesPerByte = 0
   866  			break
   867  		}
   868  		if atomic.Load64(&mheap_.pagesSweptBasis) != sweptBasis {
   869  			// Sweep pacing changed. Recompute debt.
   870  			goto retry
   871  		}
   872  	}
   873  
   874  	if trace.enabled {
   875  		traceGCSweepDone()
   876  	}
   877  }
   878  
   879  // clobberfree sets the memory content at x to bad content, for debugging
   880  // purposes.
   881  func clobberfree(x unsafe.Pointer, size uintptr) {
   882  	// size (span.elemsize) is always a multiple of 4.
   883  	for i := uintptr(0); i < size; i += 4 {
   884  		*(*uint32)(add(x, i)) = 0xdeadbeef
   885  	}
   886  }
   887  

View as plain text