Go's Sweeper: Lazy Reclamation of Dead Spans

TL;DR: Marking tells the collector what is dead; sweeping is what actually reclaims it. Go’s sweeper never stops the world to do it. Instead, every span carries a sweep generation, and spans from a previous generation are swept lazily — by whichever mutator happens to need a span, or by a low-priority background goroutine. Freeing a span to the heap is not the same as returning it to the OS; that is the scavenger’s job, and it runs on its own schedule with its own goal.

The mark phase of a garbage collector answers one question: what is dead? It does not answer the question that actually matters to your program: when does the memory come back?

There are two separate answers in Go, and they are handled by two separate pieces of machinery:

The sweeper reclaims dead objects and dead spans, returning them to the runtime’s free lists so they can be allocated again.
The scavenger returns the underlying pages to the operating system, so that RSS goes down and the memory is actually available to other processes.

Both are lazy, both are distributed, and both are paced. This is a walk through how they work in the Go 1.28 development tree.

Two reclaimers, one file

The sweeper’s own header comment draws the distinction that the rest of the implementation follows:

go
// src/runtime/mgcsweep.go:7
// The sweeper consists of two different algorithms:
//
// * The object reclaimer finds and frees unmarked slots in spans. It
//   can free a whole span if none of the objects are marked, but that
//   isn't its goal. This can be driven either synchronously by
//   mcentral.cacheSpan for mcentral spans, or asynchronously by
//   sweepone, which looks at all the mcentral lists.
//
// * The span reclaimer looks for spans that contain no marked objects
//   and frees whole spans. This is a separate algorithm because
//   freeing whole spans is the hardest task for the object reclaimer,
//   but is critical when allocating new spans. The entry point for
//   this is mheap_.reclaim and it's driven by a sequential scan of
//   the page marks bitmap in the heap arenas.
//
// Both algorithms ultimately call mspan.sweep, which sweeps a single
// heap span.

The object reclaimer is what most people think of as “the sweeper”. It walks the objects of a span, finds the ones that were not marked, and makes their slots available again. The span reclaimer is the one that actually gives pages back to the heap, and it works at a completely different granularity: a span is either entirely live or entirely dead.

The sweep generation

How does the runtime know which spans are stale? With a counter. The heap has a global sweep generation, and every span remembers the generation it was last swept in:

go
// src/runtime/mheap.go:494
	// sweep generation:
	// if sweepgen == h->sweepgen - 2, the span needs sweeping
	// if sweepgen == h->sweepgen - 1, the span is currently being swept
	// if sweepgen == h->sweepgen, the span is swept and ready to use
	// if sweepgen == h->sweepgen + 1, the span was cached before sweep began and is still cached, and needs sweeping
	// if sweepgen == h->sweepgen + 3, the span was swept and then cached and is still cached
	// h->sweepgen is incremented by 2 after every GC

	sweepgen              uint32

Five states, one integer. The counter is bumped by two at the start of each sweep phase:

go
// src/runtime/mgc.go:2065
func gcSweep(mode gcMode) bool {
	assertWorldStopped()

	if gcphase != _GCoff {
		throw("gcSweep being done but phase is not GCoff")
	}

	lock(&mheap_.lock)
	mheap_.sweepgen += 2
	sweep.active.reset()
	mheap_.pagesSwept.Store(0)
	mheap_.sweepArenas = mheap_.heapArenas
	mheap_.reclaimIndex.Store(0)
	mheap_.reclaimCredit.Store(0)
	unlock(&mheap_.lock)

	sweep.centralIndex.clear()

Adding two rather than one keeps the states two apart, so a span that needs sweeping (sweepgen-2) is never confused with one currently being swept (sweepgen-1) or one that is already swept (sweepgen). It also makes the parity of the cycle available: the central lists select between their swept and unswept sets with sweepgen/2%2, which flips every cycle.

mcentral: two lists per size class

The central free lists are the middle layer between the sweeper and the allocator. Each size class has an mcentral, and each mcentral keeps four span sets: partial and full, each in a swept and an unswept variant.

go
// src/runtime/mcentral.go:22
type mcentral struct {
	_         sys.NotInHeap
	spanclass spanClass

	// partial and full contain two mspan sets: one of swept in-use
	// spans, and one of unswept in-use spans. These two trade
	// roles on each GC cycle. The unswept set is drained either by
	// allocation or by the background sweeper in every GC cycle,
	// so only two roles are necessary.
	//
	// sweepgen is increased by 2 on each GC cycle, so the swept
	// spans are in partial[sweepgen/2%2] and the unswept spans are in
	// partial[1-sweepgen/2%2]. Sweeping pops spans from the
	// unswept set and pushes spans that are still in-use on the
	// swept set. Likewise, allocating an in-use span pushes it
	// on the swept set.
	//
	// Some parts of the sweeper can sweep arbitrary spans, and hence
	// can't remove them from the unswept set, but will add the span
	// to the appropriate swept list. As a result, the parts of the
	// sweeper and mcentral that do consume from the unswept list may
	// encounter swept spans, and these should be ignored.
	partial [2]spanSet // list of spans with a free object
	full    [2]spanSet // list of spans with no free objects
}

The parity trick again: sweepgen/2%2 selects the swept set, 1-sweepgen/2%2 selects the unswept set. The accessors are one-liners:

go
// src/runtime/mcentral.go:57
// partialUnswept returns the spanSet which holds partially-filled
// unswept spans for this sweepgen.
func (c *mcentral) partialUnswept(sweepgen uint32) *spanSet {
	return &c.partial[1-sweepgen/2%2]
}

The consequence is a beautifully small invariant: there are only two roles, and they swap every cycle. A span that is swept this cycle is unswept next cycle, and vice versa. No per-span state machine, no lists to rebuild.

Sweeping a span

The heart of it is mspan.sweep, which walks the span’s objects, compares the mark bits against the allocation bits, and rebuilds the free lists.

The bookkeeping at the end is the interesting part, because it is where the mark bits and the allocation bits swap roles:

go
// src/runtime/mgcsweep.go:698
	// Count the number of free objects in this span.
	nalloc := uint16(s.countAlloc())
	nfreed := s.allocCount - nalloc
	if nalloc > s.allocCount {
		// The zombie check above should have caught this in
		// more detail.
		print("runtime: nelems=", s.nelems, " nalloc=", nalloc, " previous allocCount=", s.allocCount, " nfreed=", nfreed, "\n")
		throw("sweep increased allocation count")
	}

	s.allocCount = nalloc
	s.freeindex = 0 // reset allocation index to start of span.
	s.freeIndexForScan = 0
	if traceEnabled() {
		getg().m.p.ptr().trace.reclaimed += uintptr(nfreed) * s.elemsize
	}

	// gcmarkBits becomes the allocBits.
	// get a fresh cleared gcmarkBits in preparation for next GC
	s.allocBits = s.gcmarkBits
	s.gcmarkBits = newMarkBits(uintptr(s.nelems))

That is the whole trick. The allocation bitmap says which slots were handed out to the program. The mark bitmap says which of those the collector found live. After the sweep, the difference — the slots that were allocated but are not live — is exactly the set of free slots. So the runtime throws away the old allocation bitmap, keeps the mark bitmap as the new allocation bitmap, and allocates a fresh zeroed mark bitmap for next time. No separate “compute the free list” pass is needed; the free list is the difference.

(With the Green Tea GC experiment enabled, there is a step before this to fold the span’s inline mark bits into the heap-wide mark bitmap.)

And then the span goes back where it came from:

go
// src/runtime/mgcsweep.go:785
	if spc.sizeclass() != 0 {
		// Handle spans for small objects.
		if nfreed > 0 {
			// Only mark the span as needing zeroing if we've freed any
			// objects, because a fresh span that had been allocated into,
			// wasn't totally filled, but then swept, still has all of its
			// free slots zeroed.
			s.needzero = 1
			stats := memstats.heapStats.acquire()
			atomic.Xadd64(&stats.smallFreeCount[spc.sizeclass()], int64(nfreed))
			memstats.heapStats.release()

			// Count the frees in the inconsistent, internal stats.
			gcController.totalFree.Add(int64(nfreed) * int64(s.elemsize))
		}
		if !preserve {
			// The caller may not have removed this span from whatever
			// unswept set its on but taken ownership of the span for
			// sweeping by updating sweepgen. If this span still is in
			// an unswept set, then the mcentral will pop it off the
			// set, check its sweepgen, and ignore it.
			if nalloc == 0 {
				// Free totally free span directly back to the heap.
				mheap_.freeSpan(s)
				return true
			}
			// Return span back to the right mcentral list.
			if nalloc == s.nelems {
				mheap_.central[spc].mcentral.fullSwept(sweepgen).push(s)
			} else {
				mheap_.central[spc].mcentral.partialSwept(sweepgen).push(s)
			}
		}
	} else if !preserve {

A span with nothing live in it goes straight back to the heap. A span with some free slots goes on the partial list. A span with no free slots goes on the full list, where it waits for the objects in it to die.

Sweeping is lazy and distributed

Two things drive the sweeper.

The mutator. When a P needs a new span of a given size class, the mcentral asks for one, and if there is no swept span available, it sweeps one itself:

go
// src/runtime/mcentral.go:112
	// Try partial swept spans first.
	sg := mheap_.sweepgen
	if s = c.partialSwept(sg).pop(); s != nil {
		goto havespan
	}

	sl = sweep.active.begin()
	if sl.valid {
		// Now try partial unswept spans.
		for ; spanBudget >= 0; spanBudget-- {
			s = c.partialUnswept(sg).pop()
			if s == nil {
				break
			}
			if s, ok := sl.tryAcquire(s); ok {
				// We got ownership of the span, so let's sweep it and use it.
				s.sweep(true)
				sweep.active.end(sl)
				goto havespan
			}

Note the spanBudget: the mutator will sweep at most a hundred spans looking for free space before giving up and allocating a fresh one. The comment above it explains why:

go
// src/runtime/mcentral.go:94
	// If we sweep spanBudget spans without finding any free
	// space, just allocate a fresh span. This limits the amount
	// of time we can spend trying to find free space and
	// amortizes the cost of small object sweeping over the
	// benefit of having a full free span to allocate from. By
	// setting this to 100, we limit the space overhead to 1%.

The background sweeper. A dedicated goroutine sweeps whatever is left over, in batches, yielding between them:

go
// src/runtime/mgcsweep.go:294
	for {
		// bgsweep attempts to be a "low priority" goroutine by intentionally
		// yielding time. It's OK if it doesn't run, because goroutines allocating
		// memory will sweep and ensure that all spans are swept before the next
		// GC cycle. We really only want to run when we're idle.
		//
		// However, calling Gosched after each span swept produces a tremendous
		// amount of tracing events, sometimes up to 50% of events in a trace. It's
		// also inefficient to call into the scheduler so much because sweeping a
		// single span is in general a very fast operation, taking as little as 30 ns
		// on modern hardware. (See #54767.)
		//
		// As a result, bgsweep sweeps in batches, and only calls into the scheduler
		// at the end of every batch. Furthermore, it only yields its time if there
		// isn't spare idle time available on other cores. If there's available idle
		// time, helping to sweep can reduce allocation latencies by getting ahead of
		// the proportional sweeper and having spans ready to go for allocation.
		const sweepBatchSize = 10
		nSwept := 0
		for sweepone() != ^uintptr(0) {
			nSwept++
			if nSwept%sweepBatchSize == 0 {
				goschedIfBusy()
			}
		}

This is the “lazy and distributed” part in a nutshell: the sweeper is not a phase that the GC waits for. It is a background activity that must finish before the next GC cycle starts, and the mutator helps out along the way.

Proportional sweep

How much sweeping has to happen? The collector works it out from the allocation rate. The rule is: sweep enough pages that the sweeper finishes just as the heap reaches the GC trigger.

go
// src/runtime/mgcsweep.go:1002
func gcPaceSweeper(trigger uint64) {
	assertWorldStoppedOrLockHeld(&mheap_.lock)

	// Update sweep pacing.
	if isSweepDone() {
		mheap_.sweepPagesPerByte = 0
	} else {
		// Concurrent sweep needs to sweep all of the in-use
		// pages by the time the allocated heap reaches the GC
		// trigger. Compute the ratio of in-use pages to sweep
		// per byte allocated, accounting for the fact that
		// some might already be swept.
		heapLiveBasis := gcController.heapLive.Load()
		heapDistance := int64(trigger) - int64(heapLiveBasis)
		// Add a little margin so rounding errors and
		// concurrent sweep are less likely to leave pages
		// unswept when GC starts.
		heapDistance -= 1024 * 1024
		if heapDistance < pageSize {
			// Avoid setting the sweep ratio extremely high
			heapDistance = pageSize
		}
		pagesSwept := mheap_.pagesSwept.Load()
		pagesInUse := mheap_.pagesInUse.Load()
		sweepDistancePages := int64(pagesInUse) - int64(pagesSwept)
		if sweepDistancePages <= 0 {
			mheap_.sweepPagesPerByte = 0
		} else {
			mheap_.sweepPagesPerByte = float64(sweepDistancePages) / float64(heapDistance)
			mheap_.sweepHeapLiveBasis = heapLiveBasis
			// Write pagesSweptBasis last, since this
			// signals concurrent sweeps to recompute
			// their debt.
			mheap_.pagesSweptBasis.Store(pagesSwept)
		}
	}
}

sweepPagesPerByte is pages-to-sweep per byte allocated. And the allocator pays that debt as it goes, in deductSweepCredit:

go
// src/runtime/mgcsweep.go:945
	// Fix debt if necessary.
retry:
	sweptBasis := mheap_.pagesSweptBasis.Load()
	live := gcController.heapLive.Load()
	liveBasis := mheap_.sweepHeapLiveBasis
	newHeapLive := spanBytes
	if liveBasis < live {
		// Only do this subtraction when we don't overflow. Otherwise, pagesTarget
		// might be computed as something really huge, causing us to get stuck
		// sweeping here until the next mark phase.
		//
		// Overflow can happen here if gcPaceSweeper is called concurrently with
		// sweeping (i.e. not during a STW, like it usually is) because this code
		// is intentionally racy. A concurrent call to gcPaceSweeper can happen
		// if a GC tuning parameter is modified and we read an older value of
		// heapLive than what was used to set the basis.
		//
		// This state should be transient, so it's fine to just let newHeapLive
		// be a relatively small number. We'll probably just skip this attempt to
		// sweep.
		//
		// See issue #57523.
		newHeapLive += uintptr(live - liveBasis)
	}
	pagesTarget := int64(mheap_.sweepPagesPerByte*float64(newHeapLive)) - int64(callerSweepPages)
	for pagesTarget > int64(mheap_.pagesSwept.Load()-sweptBasis) {
		if sweepone() == ^uintptr(0) {
			mheap_.sweepPagesPerByte = 0
			break
		}
		if mheap_.pagesSweptBasis.Load() != sweptBasis {
			// Sweep pacing changed. Recompute debt.
			goto retry
		}
	}

The mutator sweeps on its own account when it is behind. The result is that sweeping is never a separate, visible phase: it is spread across the allocation path and the idle time of the system.

The “sweep everything” pass

There are two situations where the runtime does not do it lazily.

The first is the end of a mark cycle, when everything has to be consistent before the next cycle begins. finishsweep_m drains the sweep queues completely, with the world stopped:

go
// src/runtime/mgcsweep.go:231
func finishsweep_m() {
	assertWorldStopped()

	// Sweeping must be complete before marking commences.
	//
	// gcStart picks up any unswept spans prior to commencing, which
	// ensures there are no unswept spans in the presence of a single GC.
	// However, in the case of gcStart racing with another GC, there are
	// edge cases that allow finishsweep_m to observe unswept spans. For
	// example,
	//
	// - gcStart sweeps remaining spans prior to taking work.startSema.
	//   While blocked waiting, another goroutine could take the lock and
	//   complete an entire GC cycle. When the original goroutine finally
	//   unblocks there are now unswept spans from the subsequent GC cycle.
	//
	// - Mark termination makes most sweep work prior to startTheWorld, but
	//   it calls prepareForSweep after restarting the world, which adds more
	//   work. A concurrent gcStart call could finish all of the initial work
	//   before prepareForSweep adds more, and thus gcStart doesn't see it
	//   until after taking work.startSema.
	for sweepone() != ^uintptr(0) {
	}

The second is when sweeping is not concurrent at all — a forced, stop-the-world collection:

go
// src/runtime/mgc.go:2083
	if !concurrentSweep || mode == gcForceBlockMode {
		// Special case synchronous sweep.
		// Record that no proportional sweeping has to happen.
		lock(&mheap_.lock)
		mheap_.sweepPagesPerByte = 0
		unlock(&mheap_.lock)
		// Flush all mcaches.
		for _, pp := range allp {
			pp.mcache.prepareForSweep()
		}
		// Sweep all spans eagerly.
		for sweepone() != ^uintptr(0) {
		}
		// Free workbufs and span rings eagerly.
		prepareFreeWorkbufs()
		for freeSomeWbufs(false) {
		}
		freeDeadSpanSPMCs()

That is the “sweep the whole heap” pass: one loop, sweepone() until it says there is nothing left, with the world stopped. It is what GODEBUG=gcstoptheworld=2 and runtime.GC() do.

The cached-span problem

There is one wrinkle: a span cached in an mcache is invisible to the sweeper. The runtime handles it with the two odd-looking sweep generation values (+1 and +3):

go
// src/runtime/mcache.go:214
	// Indicate that this span is cached and prevent asynchronous
	// sweeping in the next sweep phase.
	s.sweepgen = mheap_.sweepgen + 3

A cached span is marked sweepgen+3, meaning “swept, then cached, and still cached”. When the cache flushes it back to the central list, the mcentral decides whether it is stale:

go
// src/runtime/mcentral.go:210
	sg := mheap_.sweepgen
	stale := s.sweepgen == sg+1

	// Fix up sweepgen.
	if stale {
		// Span was cached before sweep began. It's our
		// responsibility to sweep it.
		//
		// Set sweepgen to indicate it's not cached but needs
		// sweeping and can't be allocated from. sweep will
		// set s.sweepgen to indicate s is swept.
		atomic.Store(&s.sweepgen, sg-1)
	} else {
		// Indicate that s is no longer cached.
		atomic.Store(&s.sweepgen, sg)
	}

sg+1 means the span was cached before the sweep began, so it was never swept in this cycle; it has to be swept now. sg+3 means it was swept and then cached, so it is fine.

Freeing pages back to the OS

Everything above returns memory to the runtime. The pages are still mapped. To give them back to the operating system, the scavenger has to unmap them — and that is a separate, slower, more dangerous operation, because unmapped pages must be faulted back in on the next allocation.

The scavenger has its own goal, which is not the heap goal but something closer to an RSS target:

go
// src/runtime/mgcscavenge.go:100
const (
	// The background scavenger is paced according to these parameters.
	//
	// scavengePercent represents the portion of mutator time we're willing
	// to spend on scavenging in percent.
	scavengePercent = 1 // 1%

	// retainExtraPercent represents the amount of memory over the heap goal
	// that the scavenger should keep as a buffer space for the allocator.
	// This constant is used when we do not have a memory limit set.
	//
	// The purpose of maintaining this overhead is to have a greater pool of
	// unscavenged memory available for allocation (since using scavenged memory
	// incurs an additional cost), to account for heap fragmentation and
	// the ever-changing layout of the heap.
	retainExtraPercent = 10

One percent of mutator time is the budget, and the scavenger keeps ten percent more than the heap goal in memory so that the allocator does not have to keep faulting pages back in.

The two goals — the GOGC one and the GOMEMLIMIT one — are computed in gcPaceScavenger, and the memory-limit one is the important one:

go
// src/runtime/mgcscavenge.go:174
	// We want to target retaining (100-reduceExtraPercent)% of the heap.
	memoryLimitGoal := uint64(float64(memoryLimit) * (1 - reduceExtraPercent/100.0))

Five percent under the limit, so that the scavenger is always working hard enough to stay under it.

The actual unmapping is done by the page allocator, which keeps an index of which chunks of the address space hold free pages:

go
// src/runtime/mgcscavenge.go:674
func (p *pageAlloc) scavenge(nbytes uintptr, shouldStop func() bool, force bool) uintptr {
	released := uintptr(0)
	for released < nbytes {
		ci, pageIdx := p.scav.index.find(force)
		if ci == 0 {
			break
		}
		systemstack(func() {
			released += p.scavengeOne(ci, pageIdx, nbytes-released)
		})
		if shouldStop != nil && shouldStop() {
			break
		}
	}
	return released
}

and the index is generation-based too. Chunks that were densely used in one cycle are skipped in the next, because the memory is probably going to be used again:

go
// src/runtime/mgcscavenge.go:1172
func (s *scavengeIndex) nextGen() {
	s.gen++
	searchAddr, _ := s.searchAddrBg.Load()
	if (offAddr{searchAddr}).lessThan(s.freeHWM) {
		s.searchAddrBg.StoreMarked(s.freeHWM.addr())
	}
	s.freeHWM = minOffAddr
}

nextGen is called once per GC cycle, at the moment of peak heap usage:

go
// src/runtime/mgc.go:1477
	// Increment the scavenge generation now.
	//
	// This moment represents peak heap in use because we're
	// about to start sweeping.
	mheap_.pages.scav.index.nextGen()

A chunk only becomes eligible for scavenging if its occupancy stayed below a threshold for a whole cycle. That is the scavenger’s version of the same idea as the sweeper’s generation counter: memory that was recently hot is probably still hot, and unmapping it would only cost you a page fault later.

Trade-offs

What laziness buys: no stop-the-world pause for reclamation, and the sweep work is spread over thousands of ordinary allocations instead of one big burst. The mutator pays a little, but only when it happens to need a span anyway.

What laziness costs: memory that the program has logically freed may still be sitting in the heap, unavailable for reuse, for an indefinite time. GODEBUG=gccheckmark=1 and the /gc/heap/frees:bytes metric tell you what has been reclaimed; the RSS tells you what the operating system thinks.

What the generation counter buys: constant-time decisions. “Is this span stale?” is an integer comparison, not a scan of a list.

What it costs: five states to reason about instead of two, and the +1/+3 special cases for cached spans.

What the scavenger buys: RSS that actually goes down. Without it, Go’s heap is a high-water-mark allocator: memory freed by the GC stays mapped forever.

What it costs: page faults on the way back in, which is why the scavenger deliberately keeps a buffer of unscavenged memory above the heap goal.

Caveats

Sweeping does not reduce RSS. If you are watching your RSS, you are watching the scavenger, not the sweeper. runtime/debug.FreeOSMemory() forces an eager scavenge.

A span can be fully allocated and still be live. fullSwept does not mean “dead”; it means “no free slots right now”. The objects in it may all still be reachable.

The spanBudget of 100 in cacheSpan is a heuristic. In the worst case the mutator sweeps a hundred spans, finds one free slot in the hundredth, and takes it — terrible throughput, bounded latency. The comment in the source admits this.

Sweeping is not free. A span sweep scans the span’s allocation bitmap to count what is still allocated, and — when the race detector, ASan or MSan are enabled — walks every freed object individually to poison it. On a production build the per-object work is skipped entirely.

The zombie check is a real safety net. If the collector finds a marked object in a free slot, it throws — that usually means a uintptr-to-pointer conversion that went wrong, and the runtime would rather die loudly than corrupt its own metadata.

Wrapping up

The one thing to remember: marking decides what is dead; sweeping reclaims it; scavenging returns it to the operating system. Three different mechanisms, three different schedules, and only the first one happens while your program is running.

The part people get wrong: “the GC freed the memory” almost never means the memory went back to the OS. The sweeper returns it to the runtime’s free lists. Until the scavenger unmaps it, your RSS stays where it was.

What to go do about it: if RSS is your problem, look at GOMEMLIMIT and at runtime/debug.FreeOSMemory(), not at GOGC. GOGC controls how much the collector collects; the scavenger controls how much the OS gives back. If allocation latency is your problem, look at the sweeper’s spanBudget and at whether you are allocating in a size class with a lot of churn.